REVIEW 3 major objections 4 minor 16 references
Improved Upper Bounds on Key Invariants of Erd\H{o}s-R\'enyi Numerical Semigroups
T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read 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.
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 2, proof of Theorem 2.1] 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 2, statement vs. proof of Theorem 2.1] 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.
- [Sections 3–4, Propositions 3.4, 3.5, and Theorem 1.6] 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.
minor comments (4)
- [Introduction, after Theorem 1.6] The word "asympototic" is a typographical error for "asymptotic".
- [Section 2, proof of Theorem 2.1] 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 3, proof of Lemma 3.2] 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 3, proof of Proposition 3.1] The inequality Pr[¬D1] = (1−p)^{N(p)} ≤ e^{N(p)} should read ≤ e^{−pN(p)}; otherwise the displayed bound is incorrect in direction.
Circularity Check
No circularity: the main upper bounds are derived from independent probabilistic and number-theoretic tools, not from fitting or self-referential definitions.
full rationale
The paper's derivation chain is self-contained against external benchmarks. The primary upper bounds in Theorem 1.6 follow from conditioning on the events D1, D2, and D3, whose failure probabilities are bounded separately: D1 uses the prime number theorem and a union bound, D2 uses Chernoff's inequality conditioned on D1, and D3 uses Theorem 2.1, a probabilistic additive combinatorics statement proved from scratch via the second moment method with a uniform random subset of Z_q. The constants b = 6 and the interval multiplier 6 are absolute and are chosen for algebraic convenience; they are not fitted to the target upper bound and do not encode the conclusion. The only external numerical semigroup facts invoked are standard textbook results from Rosales-Garcia-Sanchez, such as the two-generator Frobenius formula and the relation F(S) = max Ap(S,m) - m, which are independent of the result being proven. No parameter is fitted to a subset of data and then renamed a prediction, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled in via self-citation. The only self-citation in the paper, [Mor23], concerns experimental plots and the unproved Conjecture 5.1, and it is not load-bearing for any theorem. Whether Theorem 2.1's proof contains a gap in its variance estimate is a correctness concern, not a circularity concern, and it is not evidence that the claimed result is equivalent to its inputs by construction. Therefore no circular step is present and the circularity score is 0.
Assumptions & free parameters
free parameters (3)
- b (sumset size multiplier) =
6
- c (prime interval multiplier) =
6
- K (constant in u(p)) =
unspecified large constant
assumptions (7)
- standard math Prime number theorem: π(x) ~ x / ln x, with interval prime counts [x, cx] ~ (c-1)x / ln x.
- standard math Chernoff bound for sums of independent Bernoulli random variables.
- standard math Second moment (Chebyshev) inequality for nonnegative integer random variables.
- domain assumption Apéry set formula: for any nonzero m in S, F(S) < max Ap(S,m).
- domain assumption Frobenius number of a two-generator semigroup: F(⟨a,b⟩) = (a-1)(b-1)-1 for coprime a,b.
- domain assumption Independence of the sampling of generators, and the fact that membership of numbers ≤ u depends only on generators ≤ u.
- domain assumption The model S(p) is cofinite almost surely and the relevant expectations exist.
Cite this review
Pith. "Pith review of Improved Upper Bounds on Key Invariants of Erd\H{o}s-R\'enyi Numerical Semigroups." pith.science (2026). https://pith.science/paper/V2VBGHXR
@misc{pith2026241113767,
author = {Pith},
title = {Pith review of: Improved Upper Bounds on Key Invariants of Erd\Hos-R\'enyi Numerical Semigroups},
year = {2026},
howpublished = {\url{https://pith.science/paper/V2VBGHXR}},
note = {Machine review of arXiv:2411.13767}
}
read the original abstract
De Loera, O'Neill and Wilburne introduced a general model for random numerical semigroups in which each positive integer is chosen independently with some probability p to be a generator, and proved upper and lower bounds on the expected Frobenius number and expected embedding dimensions. We use a range of probabilistic methods to improve the upper bounds to within a polylogarithmic factor of the lower bounds in each case. As one of the tools to do this, we prove that for any prime q, if A is a random subset of the cyclic group Z_q whose size is of order log(q) and k is also of order log(q), then with high probability the k-fold sumset kA is all of Z_q.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
Abdallah Assi, Marco D'Anna, and Pedro A Garc \' a-S \'a nchez, Numerical semigroups and applications, vol. 3, Springer Nature, 2020
work page 2020
- [2]
-
[3]
Iskander Aliev, Martin Henk, and Aicke Hinrichs, Expected F robenius numbers , Journal of Combinatorial Theory, Series A 118 (2011), no. 2, 525--531
work page 2011
-
[4]
Vladimir Igorevich Arnold, Weak asymptotics for the numbers of solutions of D iophantine problems , Functional Analysis and Its Applications 33 (1999), no. 4, 292--293
work page 1999
-
[5]
Vladimir I Arnold, A rnold's problems , Springer, 2004
work page 2004
-
[6]
Noga Alon and Joel H Spencer, The P robabilistic M ethod , John Wiley & Sons, 2016
work page 2016
-
[7]
J \"o rgen Backelin, On the number of semigroups of natural numbers, Mathematica Scandinavica (1990), 197--215
work page 1990
-
[8]
Manuel Delgado, Conjecture of W ilf: a survey , Numerical semigroups, Springer INdAM Ser., vol. 40, Springer, Cham, 2020, pp. 39--62
work page 2020
Show all 16 references
-
[9]
Jesus De Loera, Christopher O'Neill, and Dane Wilburne, Random numerical semigroups and a simplicial complex of irreducible semigroups, The Electronic Journal of Combinatorics (2018), P4--37
2018
-
[10]
Sang June Lee and Jun Seok Oh, On zero-sum free sequences contained in random subsets of finite cyclic groups, Discrete Applied Mathematics 330 (2023), 118--127
2023
-
[11]
Santiago Morales, randnumsgps, https://github.com/smoralesduarte/randnumsgps, 2023
2023
-
[12]
5, 469--473
James E Nymann, On the probability that k positive integers are relatively prime, Journal of Number Theory 4 (1972), no. 5, 469--473
1972
-
[13]
Jos \'e Carlos Rosales and Pedro A Garc \' a-S \'a nchez, Numerical semigroups, Springer, 2009
2009
-
[14]
1, 211--232
Barkley Rosser, Explicit bounds for some functions of prime numbers, American Journal of Mathematics 63 (1941), no. 1, 211--232
1941
-
[15]
105, Cambridge University Press, 2006
Terence Tao and Van H Vu, Additive combinatorics, vol. 105, Cambridge University Press, 2006
2006
-
[16]
money-changing problem
Herbert S Wilf, A circle-of-lights algorithm for the “money-changing problem”, The American Mathematical Monthly 85 (1978), no. 7, 562--565
1978
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.