{"id":"816209e5-39ef-45dd-9d3b-ef8bbd528992","arxiv_id":"2509.07750","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The central theorem claiming S_k-sets of size near (n!)^{1/k} in S_n is invalid due to a permanent-counting error; several independent digraph extremal results remain.","lead":"This paper studies Sidon-type sets in noncommutative groups and claims that the trivial size bound is tight in symmetric groups for every k. The proof of that headline result contains a counting error that makes the derived lower bound exceed the trivial upper bound; the remaining graph-theoretic applications are separate.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the permanent lower bound in Theorem 3 is sufficient, and the reader's Bregman-cap concern misreads the O(n/log n) term.","rationale":"The reader's rejection rests on the claim that the proof of Theorem 3 incorrectly assumes the permanent can be exponentially close to a^n. This misreads the notation. The proof only uses the valid lower bound per(M) >= a^n n!/n^n. Substituting a = c n^{1/k} and applying Stirling, the bound is c^n n^{n/k} e^{-n+O(log n)}, i.e. (n!)^{1/k} e^{-D n+O(log n)} for D = 1-1/k-log c. Since D is a positive constant, this is (n!)^{1/k-D/log n+o(1/log n)}, which is precisely a lower bound of the form (n!)^{1/k-O(1/log n)}. The theorem asserts equality in the exponent with error O(1/log n), so this lower bound is sufficient. The apparent 'e^{n/k} excess' comes from comparing n^{n/k} to (n!)^{1/k}; that difference is itself n^{O(n/log n)}, hence within the claimed error term. Bregman's upper bound is irrelevant because the argument needs only a lower bound on the permanent, and the lower bound used is not close to a^n. The proof is notationally compressed: the O(n/log n) term in a^{n-O(n/log n)} hides a constant at least k, and the plus/minus signs in the displayed chains should be read with implicit constants. These are presentation issues, not mathematical obstructions. The central claim therefore holds up under scrutiny, and the reader's high-confidence rejection is not supported. Other results in the paper were not independently reassessed, but they are not the identified load-bearing failure.","tokens_in":22089,"tokens_out":34982,"duration_ms":264638,"concrete_test":"Recompute the chain in §3.2 with explicit constants: for a = c n^{1/k}, verify that log(a^n n!/n^n) = (1/k)log(n!) - D n + O(log n) with D = 1-1/k-log c, and check D > 0 for c = k^{-(1+1/k)}. If D > 0, the lower bound is (n!)^{1/k-O(1/log n)}, which suffices for Theorem 3; if D <= 0, the bound would be too weak to prove the claimed exponent.","verdict_should_be":"ACCEPT","load_bearing_attack":"The reader's load-bearing attack on Theorem 3 does not land. In §3.2 the lower bound is |A'| >= per(M) >= a^n n!/n^n. For a >= c n^{1/k}, a^{n-O(n/log n)} = a^n e^{-O(n/k)}, which is a^n e^{-Theta(n)}, not a^n e^{-o(n)}. Stirling gives n!/n^n = e^{-n+O(log n)}, so |A'| >= c^n n^{n/k} e^{-n+O(log n)} = (n!)^{1/k} e^{-(1-1/k-log c)n+O(log n)}. This equals (n!)^{1/k-D/log n} with D = 1-1/k-log c > 0, exactly the form needed for M_k(S_n) = (n!)^{1/k+O(1/log n)}. The permanent is never asserted to be close to a^n; the Egorychev-Falikman lower bound and Bregman upper bound both give about (a/e)^n, so they are consistent. The proof compresses the asymptotic constants, but the central theorem follows. No load-bearing flaw identified.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies nonabelian Sidon sets S_k and S'_k in groups, with focus on the symmetric group S_n and related groups. It claims explicit constructions of large S_k-sets in S_n, S_2-sets in S_n x S_n and A_n x A_n, probabilistic constructions in 'nice' groups, and improved upper bounds on M_k(Gamma) for groups with abelian subgroups. It also connects these sets to directed extremal graph theory: it determines up to a constant factor the minimum semidegree that forces certain even cycles, improves an upper bound on Hamilton paths creating two-part cycles, and claims that a directed version of the Erdős--Simonovits compactness conjecture is false. The main theorem (Theorem 3) asserts M_k(S_n) = (n!)^{1/k+O(1/log n)} via a permanent-based construction.","tokens_in":22140,"tokens_out":50299,"duration_ms":409548,"significance":"If the central constructions were valid, the paper would give a substantial improvement over the previously known lower bounds for Sidon-type sets in symmetric groups, and the directed graph applications in Theorems 7 and 8 are interesting and appear to be independent contributions. The explicit nature of the constructions and the connections drawn between additive combinatorics and extremal graph theory are valuable. However, the proof of the headline lower bound for S_k-sets in S_n contains a fundamental gap: the set A' constructed by the permanent method is not shown to be an S_k-set. This undermines the paper's main advertised claim.","major_comments":[{"comment":"The step 'By the definition of A', there exist a_1,...,a_k,b_1,...,b_k in A such that alpha_k(x)=x a_k, beta_k(x)=x b_k, etc.' is not legitimate. For pi in A', the element a_x = x^{-1} pi(x) is allowed to depend on x. In the composition alpha_1 ... alpha_k(x), the multiplier used by alpha_i is evaluated at the current point alpha_{i+1} ... alpha_k(x), which varies with x; it cannot be represented by a single fixed element a_i. Consequently the equality x a_k ... a_1 = x b_k ... b_1 does not follow, and the argument that A' is an S_k-set collapses. The lower bound M_k(S_n) >= (n!)^{1/k+O(1/log n)} is therefore not proved. This is a load-bearing error in the paper's central construction.","section":"Section 3.2, proof of Theorem 3"},{"comment":"Lemma 1 is false as stated for arbitrary real vectors. For K = Z_2, the vector x = (-1/2, -1/2) satisfies sum_k x_k x_{k^{-1}g} = 1/2 for every g, but x_1 = -1/2, not 1/2. The proof uses 'Thus A_1^2 = 1 so A_1 = 1' without justification; A_1 could be -1. The lemma becomes true if the hypothesis x in [0,infty)^K is added, which is the case in the application to Theorem 5, but the statement as written needs correction.","section":"Section 6, Lemma 1"},{"comment":"The claimed disproof of the directed Erdős--Simonovits compactness conjecture is not a consequence of Theorems 7 and 8 as stated. The notation C_{k,k} is used both for a single digraph and for the family {C_{2,2},...,C_{k,k}}. The theorems give m_0(n,F_k) = Theta(n^{1/k}) and m_0(n,C_{ell,ell}) = Theta(n^{1/2}), but the needed inequality m_0(n,C_{k,k}) = o(n^{1/2}) for the family is not proved; the available upper bound is only O(n^{1/2}). If the intended family is F_k instead, the argument must address every member of F_k, which is not done and is not immediate because F_k contains digraphs with no C_{ell,ell} subgraph.","section":"Section 7, final paragraph"}],"minor_comments":[{"comment":"The symbol C_{k,k} is used for both a single digraph and the family {C_{2,2},...,C_{k,k}}; this ambiguity is particularly confusing in the final compactness paragraph and should be resolved with separate notation.","section":"Throughout"},{"comment":"The inequality chain per(M) >= a^n n!/n^n >= a^{n-O(n/log n)} should state explicitly that the O(n/log n) term is negative and of size Theta(n/log n); as written it invites the misinterpretation that the lower bound is n^{n/k+o(n)}, which would contradict the trivial upper bound.","section":"Section 3.2"},{"comment":"The statement should clarify that the O(1/log n) is in the exponent, and note that the proof gives only the lower bound n!^{1/k-O(1/log n)}, with the upper bound being the trivial n!^{1/k}.","section":"Theorem 3 statement"}],"recommendation":"reject","confidential_remarks":"The main obstacle is the invalid proof of Theorem 3: the permanent construction does not preserve the S_k property as claimed. The earlier reader concern about the O(n/log n) term is not the actual issue; the issue is the dependence of the right-multiplier on the argument of each permutation. The paper contains other potentially valuable results (Theorems 4, 7, 8, and the probabilistic bounds), but the headline claim for S_n is unproven. A revision would need a fundamentally new construction or a corrected argument for the S_k property."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nI read the Byrne–Tait paper with the referee's concerns in hand, and I think the reject verdict is too hasty. The reader is right that the statement of Theorem 3 as written — M_k(S_n) = (n!)^{1/k} + O(1/log n) — is not what the proof establishes, and on a literal reading it is false. But the proof's final display concludes (n!)^{1/k+O(1/log n)}, and in that exponent form the argument goes through. The point the reader missed is that the factor n!/n^n from Egorychev–Falikman is not dropped; it is absorbed into the exponent error. For a = c n^{1/k}, per(M) ≥ a^n n!/n^n = c^n n^{n/k} e^{-n+O(log n)}, and writing this as (n!)^{1/k - D/log n} with D = 1 - 1/k - log c > 0 is legitimate because (n!)^{-D/log n} = e^{-D n}. So the central claim, reasonably interpreted, is not unsupported. The theorem statement needs to be corrected, and the line 'per(M) ≥ a^n n!/n^n ≥ a^{n-O(n/log n)}' invites exactly the misreading the referee made; it is only true with a sufficiently large implicit constant. That is a genuine presentation flaw, not a fatal one.\n\nWhat is actually new: the permanent embedding from an S_k-set in a group of order n into S_n is a fresh idea, and the conjugacy construction of S_2-sets in S_n × S_n (Theorem 4, Proposition 2) is clean and exact. The digraph section is the strongest part. Theorems 7 and 8 give order-of-magnitude determinations of the minimum-semidegree Turán functions for F_k and C_{ℓ,ℓ}, which are new and use the Cayley graph connection to S_k-sets sensibly. The directed Erdős–Simonovits counterexample is a nice application of the comparison between those two theorems. Corollary 1's improvement on even-cycle-creating Hamilton paths is also solid. I did not find circularity or citation problems; the Odlyzko–Smith and Egorychev–Falikman uses are appropriate.\n\nSoft spots beyond the Theorem 3 statement: the lower bound only gives M_k ≥ (n!)^{1/k-o(1)}, so calling it 'tightness of the trivial bound' oversells it; the gap is e^{Θ(n)}. Also, the proof of Theorem 3 is compressed in a way that would trip up any careful reader, and the paper would benefit from an explicit display of the Stirling computation.\n\nVerdict: worth sending to referees after the authors fix the statement and the permanent estimate. The digraph results alone justify referee time.","headline":"Theorem 3's printed statement is a trap, but the exponent-level claim survives; the digraph work is the genuinely valuable part.","tokens_in":22857,"tokens_out":14387,"would_cite":true,"duration_ms":113005,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D05","05C35","05C20","20B30","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the largest $S_k$-set in $S_n$ attains the trivial upper bound $(n!)^{1/k}$ up to $O(1/\\log n)$, and uses these constructions to settle directed Turán-type problems.","keywords":["nonabelian Sidon sets","S_k-sets","symmetric group","permanents","Cayley graphs","extremal digraph theory","minimum semidegree","Hamilton paths"],"falsifier":"For $k=2$ and a concrete seed $S_2$-set of size $a$ in a group of order $n=(p^2-1)2$, compute the permanent of the incidence matrix $M$; since this permanent is exactly the number of permutations produced by the construction, an exponential gap between $\\operatorname{per}(M)$ and $a^n n!/n^n$ as $n$ grows would make the constructed family too small to match $(n!)^{1/k}+O(1/\\log n)$.","tokens_in":21700,"feed_emoji":"🎲","tokens_out":18146,"duration_ms":150368,"temperature":0.7,"pith_summary":"This paper is trying to establish that the naive counting upper bound for nonabelian Sidon sets is often tight, and that these sets are a usable tool for extremal graph theory. Its headline result is that for every fixed $k$, the largest $S_k$-set in the symmetric group $S_n$ has size $(n!)^{1/k} + O(1/\\log n)$, matching the trivial bound obtained by counting $k$-fold products. It also constructs $S_2$-sets of size $(n-1)!$ in $S_n \\times S_n$ and $(n-1)!/2$ in $A_n \\times A_n$, gives probabilistic lower bounds for $S_2$-sets and $S_2'$-sets in 'nice' groups, and proves upper bounds that improve the trivial constant when the group has a normal abelian subgroup of bounded index. On the graph side, the paper determines up to a constant factor the minimum semidegree that forces two distinct directed walks of length $k$ with the same endpoints, shows that forbidding a single $C_{\\ell,\\ell}$ forces $\\Theta(n^{1/2})$ in this minimum-degree sense, improves the upper bound on Hamilton paths that create two-part cycles, and disproves a directed version of the Erdős-Simonovits compactness conjecture.","feed_headline":"Symmetric group hits the trivial Sidon-set bound","feed_subtitle":"For every k, S_n contains S_k-sets of size (n!)^{1/k} up to a 1/log n error.","key_machinery":"The machinery has three parts. First, the lifting construction: given an $S_k$-set $A$ in a finite group $\\Gamma$, the permutations $\\pi$ of $\\Gamma$ with $\\pi(x)\\in xA$ for all $x$ are themselves an $S_k$-set in $S_\\Gamma$, and their number is the permanent of the 0-1 matrix $M_{x,y}=1$ if and only if $x^{-1}y\\in A$. The permanent lower bound for doubly stochastic matrices, applied to $M/a$, is the estimate that makes the count reach $(n!)^{1/k+o(1)}$ after choosing $|\\Gamma|$ near $n$ using primes in short intervals. Second, the conjugacy recipe: for a fixed $\\pi$, the set $\\{(\\alpha,\\alpha\\pi): \\alpha\\in A\\}$ in $\\Gamma\\times\\Gamma$ is an $S_2$-set with parameter $g$ whenever every element of $\\Gamma$ has at most $g$ preimages under the conjugation map $\\alpha\\mapsto\\alpha\\pi\\alpha^{-1}$; point stabilizers in $S_n$ make $g=1$ or small, yielding exact factorial-sized sets. Third, for the digraph results, a random partition of vertices into $2k$ parts keeps only edges from part $i$ to part $i+1$, producing a spanning subgraph with a constant fraction of the minimum degree in which every closed walk of length at most $2k-1$ is balanced; this removes short unbalanced cycles and makes the remaining graph $F_k$-free.","core_discovery":"Stated on the paper's own terms, the central discovery is that the trivial product-counting bound $M_k(\\Gamma) \\le |\\Gamma|^{1/k}$ can be asymptotically attained in the symmetric group: $M_k(S_n) = (n!)^{1/k} + O(1/\\log n)$. The proof lifts an $S_k$-set $A$ in a smaller group $\\Gamma$ of order near $n$ to the set of all permutations of $\\Gamma$ that send each element $x$ into $xA$; the number of such permutations is a permanent of the 0-1 incidence matrix of $A$, and the permanent lower bound for doubly stochastic matrices is used to estimate it. A second, exact construction produces $S_2$-sets in $\\Gamma \\times \\Gamma$ from a conjugacy class: if at most $g$ conjugates of $\\pi$ by elements of $A$ can coincide, then $\\{(\\alpha,\\alpha\\pi): \\alpha\\in A\\}$ is an $S_2$-set allowing at most $g$ words per product, and taking $A$ to be a point stabilizer in $S_n$ yields sets of size $(n-1)!$ in $S_n \\times S_n$ and $(n-1)!/2$ in $A_n \\times A_n$. The same families are then fed into Cayley graphs to show that the minimum semidegree forcing the directed subgraph family $F_k$ is $\\Theta(n^{1/k})$, that a single $C_{\\ell,\\ell}$ forces $\\Theta(n^{1/2})$, and that the directed compactness conjecture fails.","pith_inferences":["A testable extension the authors do not pursue is to use the conjugacy recipe in other permutation groups with a large conjugacy class, such as wreath products; Proposition 3 already shows the mechanism transfers whenever a large conjugacy class exists, so the factorial-size phenomenon may be more general than $S_n$.","The permanent-counting step is the sensitive spot of Theorem 3; sharper estimates for permanents of regular 0-1 matrices, or a different counting argument, would either certify the $O(1/\\log n)$ error or force a smaller lower bound, and this is the first place to look if the theorem is pushed to other groups.","Comparing Theorems 7 and 8 suggests an interpolation question: what is the smallest family of orientations whose minimum-semidegree Turán function passes from $\\Theta(n^{1/k})$ to $\\Theta(n^{1/2})$ as the family grows? Neither the paper's constructions nor its upper bounds answer this, and it is directly testable with the same Cayley-set method.","The Hamilton-path upper bound rests on the vertex-transitive-graph lemma, so the same counting argument should apply to any vertex-transitive graph whose vertices are structured objects and whose edges are 'creates a forbidden subgraph' relations; applying it to other forbidden subgraphs is a natural next step."],"forward_implications":["For every fixed $k$, the largest $S_k$-set in $S_n$ has size $(n!)^{1/k}+O(1/\\log n)$, so the trivial product-counting bound is asymptotically exact in the symmetric group.","$S_2$-sets of size $(n-1)!$ exist in $S_n\\times S_n$, and of size $(n-1)!/2$ in $A_n\\times A_n$; these are within a factor of $n$ of the trivial bound $n!$ for the product group.","The minimum semidegree that guarantees two distinct directed walks of length $k$ with the same endpoints lies between $(1/(k^{1+1/k})-o(1))n^{1/k}$ and $(2k+o(1))n^{1/k}$; for a single $C_{\\ell,\\ell}$, the range is between $(1/(2\\ell-2)^{1/2}-o(1))n^{1/2}$ and $(2\\ell+o(1))n^{1/2}$.","For even $\\ell\\ge 4$, the maximum number of Hamilton paths on $[n]$ no two of which create a two-part cycle of length $\\ell$ is at most $(n!)^{1/2+O(1/\\log n)}$.","The directed analogue of the Erdős-Simonovits compactness conjecture is false: for the family $C_{k,k}$ of two internally disjoint directed paths, the ratio $m_0(n,H)/m_0(n,C_{k,k})$ tends to infinity for every member $H$."],"supporting_citations":[{"why":"supplies the explicit $S_k$-set in a group of order $(p^k-1)k$ that is lifted to $S_n$ in the proof of Theorem 3 and used to build the Cayley graphs in Theorem 7.","marker":"[35]"},{"why":"proves the permanent lower bound for doubly stochastic matrices that counts the lifted permutations in Theorem 3.","marker":"[14]"},{"why":"gives the independent proof of the same permanent lower bound cited alongside [14].","marker":"[17]"},{"why":"provides primes in short intervals, used to pass from special orders $(p^k-1)k$ to every large $n$ in Theorem 3 and Theorem 7.","marker":"[3]"},{"why":"establishes the strict inequality $M_k(\\Gamma)<|\\Gamma|^{1/k}$ that Theorem 5 extends to a stability-style bound when $\\Gamma$ has a normal abelian subgroup of index $h$.","marker":"[13]"},{"why":"the even cycle theorem supplies the general upper bound $M'_k(\\Gamma)=O(|\\Gamma|^{1/k})$ and motivates the directed cycle problems in Section 7.","marker":"[6]"},{"why":"the BEST theorem counts Eulerian circuits used to enumerate Hamilton cycles in the graph $G_{r,m}$ for Corollary 1.","marker":"[39]"},{"why":"the vertex-transitive graph lemma converts an independent family of Hamilton paths into the upper bound on $\\hat{M}(n,\\ell)$.","marker":"[19]"}],"fun_headline_variants":["Symmetric groups attain Sidon size bound","S_n has Sidon sets of size (n!)^{1/k}","Permanent trick builds large Sidon sets","New Sidon sets in symmetric groups","Optimal Sidon sets in S_n up to log factor"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the headline lower bound counts the constructed permutations by the permanent of a 0-1 matrix and relies on that count being within a subexponential factor of $a^n$, where $a$ is the size of the seed $S_k$-set; if the true maximum permanent for such regular matrices is exponentially smaller, the counting step cannot deliver $(n!)^{1/k}$.","fun_headline_variants_meta":{"raw":{"variants":["Symmetric groups attain Sidon size bound","S_n has Sidon sets of size (n!)^{1/k}","Permanent trick builds large Sidon sets","New Sidon sets in symmetric groups","Optimal Sidon sets in S_n up to log factor"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000305,"raw_usage":{"total_tokens":1874,"prompt_tokens":1196,"completion_tokens":678,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":812,"completion_tokens_details":{"reasoning_tokens":602}},"tokens_in":812,"tokens_out":678,"duration_ms":6728,"temperature":1.0,"reasoning_tokens":602,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:21:48.306076+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $k=2$ and a concrete seed $S_2$-set of size $a$ in a group of order $n=(p^2-1)2$, compute the permanent of the incidence matrix $M$; since this permanent is exactly the number of permutations produced by the construction, an exponential gap between $\\operatorname{per}(M)$ and $a^n n!/n^n$ as $n$ grows would make the constructed family too small to match $(n!)^{1/k}+O(1/\\log n)$.","supporting_citations":[{"cited_title":"Nonabelian sets with distinctk-sums","cited_arxiv_id":null,"evidence_quote":"supplies the explicit $S_k$-set in a group of order $(p^k-1)k$ that is lifted to $S_n$ in the proof of Theorem 3 and used to build the Cayley graphs in Theorem 7."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"proves the permanent lower bound for doubly stochastic matrices that counts the lifted permutations in Theorem 3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the independent proof of the same permanent lower bound cited alongside [14]."},{"cited_title":"The exceptional set for goldbach’s problem in short intervals.London Mathematical Society Lecture Note Series, pages 1–54, 1996","cited_arxiv_id":null,"evidence_quote":"provides primes in short intervals, used to pass from special orders $(p^k-1)k$ to every large $n$ in Theorem 3 and Theorem 7."},{"cited_title":"Groups with unique product structures.Journal of Algebra, 146(1):205–209, 1992","cited_arxiv_id":null,"evidence_quote":"establishes the strict inequality $M_k(\\Gamma)<|\\Gamma|^{1/k}$ that Theorem 5 extends to a stability-style bound when $\\Gamma$ has a normal abelian subgroup of index $h$."},{"cited_title":"Cycles of even length in graphs.Journal of Combinatorial Theory, Series B, 16(2):97–105, 1974","cited_arxiv_id":null,"evidence_quote":"the even cycle theorem supplies the general upper bound $M'_k(\\Gamma)=O(|\\Gamma|^{1/k})$ and motivates the directed cycle problems in Section 7."},{"cited_title":"Circuits and trees in oriented linear graphs.Classic papers in combinatorics, pages 149–163, 1987","cited_arxiv_id":null,"evidence_quote":"the BEST theorem counts Eulerian circuits used to enumerate Hamilton cycles in the graph $G_{r,m}$ for Corollary 1."},{"cited_title":"Springer Science & Business Media, 2001","cited_arxiv_id":null,"evidence_quote":"the vertex-transitive graph lemma converts an independent family of Hamilton paths into the upper bound on $\\hat{M}(n,\\ell)$."}],"review_version":2}