{"id":"395ed36b-b6b9-4a2e-a384-1c60e7574bfa","arxiv_id":"2411.13767","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"The authors prove upper bounds O((log 1/p)^3) and O((1/p)(log 1/p)^3) for expected embedding dimension and Frobenius number of Erdős-Rényi random numerical semigroups, improving on prior 1/p and 1/p^2 bounds.","lead":"Random numerical semigroups, where each number is included as a generator with probability p, are now known to have expected Frobenius number and embedding dimension much closer to their lower bounds than previously proven. The paper's upper bounds are within a polylogarithmic factor of the lower bounds, but the proof's key sumset lemma appears to contain a counting error.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.1's second-moment proof omits the C(k,j) choice of common subset, so the claimed o(p^4) failure probability for D3 and the main bounds are not established as written.","rationale":"The reader's verdict correctly identifies the load-bearing flaw. The central result, Theorem 1.6, is obtained by conditioning on the event D3, and the only source of the o(p^4) failure probability for D3 is Theorem 2.1 via Proposition 3.4. The second-moment argument in Theorem 2.1 undercounts the number of intersecting pairs (K,L) by omitting the C(k,j) factor, and it also does not correctly account for the sum constraint. With the missing factor, the variance is not small enough for the Chebyshev-plus-union-bound route to deliver the claimed O(q^{−(b−2)} log q) failure probability. The concern is specific and localized; it may be repairable by a different concentration argument, but as written the proof does not go through. The paper contains useful ideas and the D1 probability calculation appears to be a typographical issue rather than a substantive error, but the Theorem 2.1 gap is decisive for the main theorem.","tokens_in":10626,"tokens_out":34356,"duration_ms":317329,"concrete_test":"Re-derive the second moment in Theorem 2.1 by counting, for fixed K∈N_z^k, the L∈N_z^k with |K∩L|=j: there are C(k,j) choices of I=K∩L, and for each, roughly C(q−k,k−j)/q choices of B=L\\I satisfying sum(B)=z−sum(I). This yields ∆_j/E^2≈C(k,j)^2/C(2k,k) for j<k. Then compute the corrected Chebyshev bound on Pr[X_z=0] and the union bound over z for k=2⌈6 log2 q⌉. If the resulting failure probability is not O(q^{−(b−2)} log q), the proof of Theorem 2.1 fails as written.","verdict_should_be":"REJECT","load_bearing_attack":"In the proof of Theorem 2.1, for fixed K∈N_z^k, the number of L with |K∩L|=j and sum(L)=z is at least the number of choices of I=K∩L (C(k,j) choices) times the number of B⊂Z_q\\K of size k−j with sum(B)=z−sum(I). The displayed bound counts only the choice of B, omitting C(k,j). This is not harmless: for k=2⌈b log2 q⌉ and j≈k/2, C(k,j)≈2^k/√k≈q^{2b}/√k is much larger than q, so the paper's ∆_j can be smaller than the true covariance by a factor far exceeding q. Once the missing C(k,j) is inserted, the second moment ratio becomes of order C(k,j)^2/C(2k,k) for each j, and Σ_j C(k,j)^2/C(2k,k)=1. Chebyshev then gives only Pr[X_z=0]≤1+o(1), not the O(q^{−(b−2)}) needed for the union bound. Since Proposition 3.4 and Corollary 3.5 rely on the o(p^4) failure probability from Theorem 2.1, the main upper bounds in Theorem 1.6 are unsupported by the argument given.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Erdős–Rényi-type random numerical semigroups S(p), where each positive integer is included as a generator independently with probability p. It claims improved upper bounds on the expected embedding dimension, genus, and Frobenius number, bringing them to within polylogarithmic factors of the lower bounds established by De Loera, O'Neill, and Wilburne. The main probabilistic tool is a new theorem (Theorem 2.1) asserting that for a prime q, a random subset A of Z_q of size O(log q) has its k-fold sumset equal to all of Z_q with high probability when k = O(log q). The authors use this to control an Apéry-set event and then condition on a high-probability good event to bound the expected Frobenius number and embedding dimension. The paper concludes with numerical experiments and a conjecture that the true behavior is one log factor above the lower bounds.","tokens_in":10888,"tokens_out":10364,"duration_ms":103235,"significance":"If the main results were valid, they would constitute a substantial improvement over prior work: the expected Frobenius number would drop from O(1/p^2) to O((1/p) log^3(1/p)) and the expected embedding dimension to O(log^3(1/p)), nearly matching the known lower bounds. The sumset theorem is also potentially of independent interest. The paper's overall strategy—separating the random selection of generators from the algebraic sumset process—is sound in outline, and Lemma 4.1's conditioning argument is a useful and correct component. However, the central sumset estimate is not proven as written, and because every subsequent claim depends on it, the significance is conditional on a substantial repair.","major_comments":[{"comment":"The displayed bound on Δ_j undercounts the number of ordered pairs (K,L) with |K∩L|=j. For a fixed K, after choosing the intersection-free part B ⊂ Z_q\\K of size k−j, one must also choose which j elements of K lie in L; there are C(k,j) choices. The bound C(q−k, k−j) alone therefore omits a factor C(k,j). Inserting this factor changes the subsequent ratio to Δ_j/E[X_z]^2 ≈ q·C(k,j)^2/C(2k,k) when s=2k. Summing over j gives Δ/E[X_z]^2 ≈ q, since Σ_j C(k,j)^2 = C(2k,k). Chebyshev then yields only Pr[X_z=0] ≤ 1/E[X_z] + q, not the claimed O(q^{−(b−2)}). Thus Theorem 2.1 is not established.","section":"Section 2, proof of Theorem 2.1"},{"comment":"There is a parameter mismatch between the theorem statement and its proof. The theorem states that |A| = 2⌈b log2 q⌉ and the sumset is (b log2 q)A, but the proof sets the number of summands to k = 2⌈b log2 q⌉ and takes |A| = s = 2k = 4⌈b log2 q⌉. The proof therefore concerns a different pair of parameters; even if the counting error above were fixed, it would not imply the theorem as stated. This discrepancy also affects the application in Proposition 3.4, where the constant b=6 is used with a specific sumset size.","section":"Section 2, statement vs. proof of Theorem 2.1"},{"comment":"The entire proof of the main theorem relies on Corollary 3.5, which asserts Pr[¬D3] = o(p^4). This in turn rests on Proposition 3.4, whose proof is the application of Theorem 2.1. Since Theorem 2.1 is not established, the error term Pr[¬D3] is not controlled at the required o(p^4). Consequently the final estimates in Theorem 1.6 for E[F(S)] and E[e(S)] do not follow from the argument given.","section":"Sections 3–4, Propositions 3.4, 3.5, and Theorem 1.6"}],"minor_comments":[{"comment":"The word \"asympototic\" is a typographical error for \"asymptotic\".","section":"Introduction, after Theorem 1.6"},{"comment":"The definition of Δ_j is partially garbled: the summation over pairs (K,L) with K,L ∈ N^k_z and |K∩L|=j should be written explicitly, and the notation \"L∈N K_z\" is ambiguous.","section":"Section 2, proof of Theorem 2.1"},{"comment":"In the denominator of the conditional probability computation, p(1−p)^{n−k} should presumably be p(1−p)^{n−j}; as written the variable k is undefined there.","section":"Section 3, proof of Lemma 3.2"},{"comment":"The inequality Pr[¬D1] = (1−p)^{N(p)} ≤ e^{N(p)} should read ≤ e^{−pN(p)}; otherwise the displayed bound is incorrect in direction.","section":"Section 3, proof of Proposition 3.1"}],"recommendation":"reject","confidential_remarks":"The central combinatorial estimate in Theorem 2.1 has a concrete undercounting error that is not a typo: adding the missing C(k,j) factor destroys the second-moment bound. This is not a local fix, because the resulting variance-to-mean-squared ratio is too large for the Chebyshev argument to yield the needed failure probability. Combined with the additional parameter mismatch between the theorem statement and proof, the main results are unsupported as written. A different approach to the sumset problem or a different decomposition of the Apéry-set event would be needed to salvage the paper."},"author_rebuttal":null,"desk_editor":null,"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["20M14","05D40","11B30"],"pacs":[],"model":"deepseek-v4-flash","headline":"Random numerical semigroups have expected Frobenius number and genus $O((1/p)(\\ln(1/p))^3)$ and expected embedding dimension $O((\\ln(1/p))^3)$, tightening the known bounds to within a polylogarithmic factor.\n\n","keywords":["random numerical semigroup","Frobenius number","embedding dimension","genus","k-fold sumset","Erdős–Rényi model","Apéry set","probabilistic method"],"falsifier":"Compute the failure probability $\\Pr[(\\lceil b\\log_2 q\\rceil)A\\neq\\mathbb{Z}_q]$ for a uniform random subset $A$ of size $2\\lceil b\\log_2 q\\rceil$ at, say, $b=6$, either by exact enumeration for small primes or by direct simulation for large ones. If the probability is not $O(q^{-4}\\log q)$ for a sequence of primes $q\\to\\infty$, then the event $D_3$ does not fail with probability $o(p^4)$ and the proof of the main theorem needs a different typical-case argument.","tokens_in":10407,"feed_emoji":"🎲","tokens_out":11348,"duration_ms":99925,"temperature":0.7,"pith_summary":"This paper tightens the upper bounds for the three basic statistics of an Erdős–Rényi random numerical semigroup: expected Frobenius number, expected genus, and expected embedding dimension. The result is that, as the generator probability $p$ tends to zero, the first two are at most a constant times $(1/p)(\\ln(1/p))^3$ and the third is at most a constant times $(\\ln(1/p))^3$. This puts the upper bounds within a polylogarithmic factor of the known lower bounds, shrinking the gap from a factor of order $1/p$ to a factor of order $(\\ln(1/p))^3$. A reader should care because these invariants control how large and how complex a random semigroup is, and the proof introduces a reusable probabilistic fact: a random subset of a prime cyclic group of size about $\\log q$ additively covers the whole group when summed $O(\\log q)$ times.\n\n","feed_headline":"Random semigroup bounds close gap to polylog of lower bounds","feed_subtitle":"Frobenius number and embedding dimension now sit within (ln 1/p)^3 of lower bounds.","key_machinery":"The load-bearing object is the new sumset theorem (Theorem 2.1): if $q$ is prime and $A\\subset\\mathbb{Z}_q$ is a uniform random subset of size $2\\lceil b\\log_2 q\\rceil$, then $\\lceil b\\log_2 q\\rceil A=\\mathbb{Z}_q$ with failure probability at most $O(q^{-(b-2)}\\log q)$. This feeds the paper's main 'typical generation' event $D_3$: with a large prime generator $q$ and $12\\log_2 q$ extra generators below $q$, the Apéry set of $q$ in the generated subsemigroup has maximum at most $6q\\log_2 q$, and the identity $F(S)=\\max\\operatorname{Ap}(S,q)-q$ turns that into the Frobenius bound. The proof also uses a second-moment inequality for indicators in the sumset argument, and a tail bound based on the exact Frobenius number of a two-generator semigroup, $(n_1-1)(n_2-1)-1$, to handle the rare event that the typical generation fails.\n\n","core_discovery":"The central claim is Theorem 1.6: in the unconstrained Erdős–Rényi model where every positive integer is chosen independently with probability $p$, the expected embedding dimension satisfies $\\mathbb{E}[e(S(p))] = O((\\ln(1/p))^3)$ and the expected genus is at most the expected Frobenius number, which satisfies $\\mathbb{E}[F(S(p))] = O((1/p)(\\ln(1/p))^3)$. The proof works by isolating a 'typical' event that occurs with failure probability $o(p^4)$: a prime $q$ near $(1/p)(\\ln(1/p))^2$ is selected as a generator, along with about $\\log q$ smaller generators, and these smaller generators make the $k$-fold sumset reach every residue class modulo $q$. When that happens the Apéry set of $q$ has small maximum and the Frobenius number is bounded by $O((1/p)(\\ln(1/p))^3)$; in the rare failure case, a separate argument waits for two consecutive generators and controls the tail. The same high-probability event, plus the inequality $e(S)\\leq 2F(S)$, yields the embedding-dimension bound.\n\n","pith_inferences":["The paper's own experiments suggest the true orders are $(1/p)\\ln(1/p)$ for the Frobenius number and $\\ln(1/p)$ for the embedding dimension; if so, the new upper bounds are still two log factors too large, and the extra factors likely come from waiting for a prime at scale $(1/p)(\\ln(1/p))^2$ rather than using the first small generator.","The tail argument that waits for two consecutive generators to appear could be applied to other random additive semigroup models as a generic 'second chance' bound when the main high-probability event fails.","The explicit failure probability in Theorem 2.1 may find uses beyond numerical semigroups, for instance in problems on random Cayley digraphs or random additive bases, where covering a cyclic group by a logarithmic-size sumset is the key step."],"forward_implications":["If Theorem 1.6 is correct, the expected Frobenius number and genus of a random semigroup are, for small $p$, within a factor of order $(\\ln(1/p))^3$ of the known lower bounds, instead of a factor of order $1/p$.","The typical random semigroup is governed by a moderate prime generator plus about $\\log(1/p)$ small generators: except with probability $o(p^4)$, the Frobenius number is controlled by the Apéry set of that prime.","The embedding-dimension bound follows from the Frobenius bound through the general inequality $e(S)\\leq 2F(S)$, combined with the fact that, when the Frobenius number is small, all minimal generators are at most twice that size.","Because the paper works in the unconstrained model $S(p)$ and the earlier model $S(M,p)$ converges to it as $M\\to\\infty$, the improved bounds transfer to the original bounded model and can be compared directly with earlier results.","The sumset theorem is a standalone statement about random subsets of prime cyclic groups: a logarithmic-size random subset, added to itself a logarithmic number of times, covers the group with polynomially small failure probability."],"supporting_citations":[{"why":"Defines the Erdős–Rényi-type random semigroup model and supplies the lower bounds and constant-$p$ comparison bounds that Theorem 1.6 improves.","marker":"[DLOW18]"},{"why":"Provides the second-moment inequality that the proof of Theorem 2.1 applies to the sumset indicators.","marker":"[AS16]"},{"why":"Gives the Apéry-set definition and the formula $F(\\langle n_1,n_2\\rangle)=(n_1-1)(n_2-1)-1$ used in the tail bound.","marker":"[RGS09]"},{"why":"Defines $k$-fold sumsets, the object that Theorem 2.1 analyzes in random subsets of $\\mathbb{Z}_q$.","marker":"[TV06]"}],"fun_headline_variants":["Random semigroup invariants now within polylog of bounds","Frobenius number and embedding dimension: polylog gap closed","Erdos-Renyi semigroup bounds tightened to (ln 1/p)^3","Polylog factor achieved for random semigroup upper bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument depends on the claim that about $\\log q$ randomly chosen residue classes modulo a prime $q$, summed with themselves about $\\log q$ times, cover every residue with high probability; if that coverage claim fails, the typical-case bound on the Frobenius number loses its main support.","fun_headline_variants_meta":{"raw":{"variants":["Random semigroup invariants now within polylog of bounds","Frobenius number and embedding dimension: polylog gap closed","Erdos-Renyi semigroup bounds tightened to (ln 1/p)^3","Polylog factor achieved for random semigroup upper bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000593,"raw_usage":{"total_tokens":2772,"prompt_tokens":932,"completion_tokens":1840,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":548,"completion_tokens_details":{"reasoning_tokens":1763}},"tokens_in":548,"tokens_out":1840,"duration_ms":15116,"temperature":1.0,"reasoning_tokens":1763,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:55:22.742309+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the failure probability $\\Pr[(\\lceil b\\log_2 q\\rceil)A\\neq\\mathbb{Z}_q]$ for a uniform random subset $A$ of size $2\\lceil b\\log_2 q\\rceil$ at, say, $b=6$, either by exact enumeration for small primes or by direct simulation for large ones. If the probability is not $O(q^{-4}\\log q)$ for a sequence of primes $q\\to\\infty$, then the event $D_3$ does not fail with probability $o(p^4)$ and the proof of the main theorem needs a different typical-case argument.","supporting_citations":[],"review_version":1}