REVIEW 3 major objections 5 minor 4 references
Sums and differences of sets: a further improvement over AlphaEvolve
T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper claims a new lower bound θ ≥ 1.173077 for the sums-and-differences exponent, improving the previous best known value 1.173050.
desk verdict The claimed bound is likely right, but the proof as written contains a false counting equality that must be repaired before the theorem can stand. read the letter →
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 central object is $W(m,L,B)$, the set of $m$-dimensional nonnegative integer vectors whose entries are each at most $B$ and whose sum is at most $L$. The proof uses the identities $|U+U|=|W(m,2L,2B)|$ and $|U-U|=\sum_{k=0}^{\min(m,L)} \binom{m}{k}|W(k,L-k,B-1)|\,|W(m-k,L,B)|$, together with the large-deviation rate function $I(c,B)=\sup_t\{tc-\log((1+e^t+\cdots+e^{Bt})/(B+1))\}$, which controls the exponential growth of $|W(m,\lfloor rm\rfloor,B)|$. These ingredients convert the finite-set construction into the parameter formula that is optimized to yield $\theta \geq 1.173077$.
What would settle it
Evaluate the asserted identity at $m=5,k=2$: $\binom{5}{2}=10$ whereas $|W(5,2,1)|=\sum_{j=0}^{2}\binom{5}{j}=16$, so the equality used in the proof is not true; checking whether any correct lower bound on the binomial factor of the same exponential strength exists would settle the proof of the stated constant.
Extended reading notes
Core claim
The paper's central claim is Theorem 1: for the sums and differences of sets problem, the attainable exponent satisfies $\theta \geq 1.173077$. Following an established construction line, the author takes the set $W(m,L,B)$ of $m$-tuples of nonnegative integers with each coordinate at most $B$ and coordinate sum at most $L$, encodes the tuples as integers via a base-$(2B+1)$ expansion, and calls the image $U$. Known identities express $|U+U|$ and $|U-U|$ through counts of such restricted-vector sets; the new ingredient is a large-deviation analysis that gives the exponential growth rate of $|W(m,\lfloor rm\rfloor,B)|$ for fixed $B$ and varying $r$. Splitting the difference-set count into a binomial factor and two $W$-counts, and optimizing the resulting formula numerically, the paper obtains the stated constant, with the maximum occurring at $B=5$.
Load-bearing premise
The proof of the final bound relies on treating the binomial coefficient $\binom{m}{k}$ as equal to $|W(m,k,1)|$, the number of binary vectors with at most $k$ ones; that equality is false, and the paper supplies no substitute that gives the required lower bound on the binomial factor.
Editorial extensions
If this is right
- For any small $\varepsilon>0$, the constructed sequence gives finite sets $A,B$ with $|A-B|\geq c|A+B|^{1.173077-\varepsilon}$ and $|A+B|$ arbitrarily large, subject to the growth constraint in the problem.
- The value $1.173077$ supersedes the prior explicit bound $1.173050$ and all earlier bounds, making it the best known lower bound if the proof is correct.
- The numerical table shows the maximum at $B=5$ is stable to fifteen decimal places as the optimization tolerance is tightened, so the reported constant is not an artifact of loose numerical search.
- The construction yields a sequence of sets of growing size, so the improved exponent is obtained in the limit rather than from a single finite set.
Reading between the lines
- Extension: the flawed step identifying $\binom{m}{k}$ with $|W(m,k,1)|$ might be repairable by a direct lower bound on the binomial coefficient from standard tail or entropy estimates; a correct replacement could preserve the constant, but the paper does not supply it.
- Extension: the numerical optimization was restricted to $B=1,\ldots,10$, $r\in(0.5,2)$, and $a$ in a fixed interval, so a wider search over these parameters could push the constant higher; $1.173077$ is a lower bound for this construction family, not a proven maximum over all possible choices.
- Extension: the same large-deviation counting of coordinate-bounded vectors should transfer to other additive-combinatorics problems where sums and differences of structured integer sets are measured, such as higher-dimensional analogues or sets defined by several linear constraints.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims a new lower bound θ ≥ 1.173077 for the sums and differences of sets problem, improving on the previous best θ = 1.173050. The construction takes U to be the image of W(m, L, B) = {x ∈ [0,B]^m : Σ x_i ≤ L} under the base-(2B+1) encoding, and uses large-deviation estimates (Cramér's theorem) to asymptotically count |U+U| and |U−U|. The resulting lower bound is then optimized numerically over parameters B, r, and a using MATLAB routines fminbnd and fminunc. A table reports optimized values for B = 3,...,10, with the B = 5 entry supporting the headline constant 1.173077.
Significance. If Theorem 1 were established rigorously, the paper would give the best known lower bound for the exponent θ in the sums and differences problem, a small but genuine improvement over the recent construction of Gerbicz. The use of large-deviation estimates to count the constrained integer partitions W(m,L,B) is a natural and potentially useful addition to the existing framework, and the manuscript includes its MATLAB code for reproducibility. However, the proof as written contains a false combinatorial counting step that invalidates the key binomial estimate, and the numerical maximization is not presented as a rigorous computation. The overall approach appears salvageable, but the central claim is not supported in the current form.
major comments (3)
- [Section 3, Table 1] The assertion 'in the set W(m,k,1), exactly k of the m coordinates are 1, and the rest are 0, so C(m,k) = W(m,k,1)' is false: by the definition W(m,L,B), the set W(m,k,1) consists of all binary vectors with at most k ones, not exactly k ones. The correct identity is C(m,k) = |W(m,k,1)| − |W(m,k−1,1)|. As a consequence, the claimed asymptotic lower bound (log C(m,k))/m ≥ log 2 − I(ar,1) is only valid for ar ≤ 1/2; for ar > 1/2 the true rate is the binary entropy H(ar), which is strictly smaller than log 2. The proof imposes no restriction ar ≤ 1/2 and does not report the optimizing parameters, so the derivation of Eq. (7) and the conclusion θ ≥ 1.173077 are not supported as written. A repair exists: for c < ar ≤ 1/2 one can use C(m,k) ≥ C(m,⌊cm⌋) ≥ |W(m,⌊cm⌋,1)|/(⌊cm⌋+1), which yields the same rate; this replacement and the condition ar ≤ 1/2 must be made explicit.
- [Section 3, Table 1] The final numerical constant 1.173077 is produced by applying fminbnd and fminunc with finite tolerances (ϵ down to 10^{-10}) to a nonlinear optimization problem. The manuscript provides no interval-arithmetic bounds, no certified global maximum, and no reporting of the maximizing triple (B,r,a). Even if the counting error in Eq. (5) were repaired, this numerical computation would still not constitute a rigorous proof of the displayed inequality. To make Theorem 1 rigorous, the authors should either exhibit one explicit triple (B,r,a) for which the expression exceeds 1.173077 and evaluate it with a certified method, or provide rigorous enclosures for the supremum.
- [Section 2, Lemma 1 proof] In the case r < B/2, the proof states lim_{m→∞} (1/m) log P(x_1 + ... + x_m ≤ mB/2) = −I(r,B). This is not the event defining W(m,⌊rm⌋,B); the correct statement should be P(x_1 + ... + x_m ≤ mr). As written, the displayed identity is false unless r = B/2. This appears to be a typographical slip, but Lemma 1 is used throughout the proof of Theorem 1, so the intended statement and its derivation must be corrected.
minor comments (5)
- [Section 3, Eq. (7)] The line 'Adding (5), (4) and (6) we get lim inf_{m→∞} d(U)/m ≥ ...' should read 'lim inf_{m→∞} (log d(U))/m ≥ ...'; as written the dimensions do not match the preceding estimates.
- [Section 4, MATLAB code] In the function theta(B), the fourth tolerance is set to 1e-4, but the text and Table 1 indicate it should be 1e-10.
- [Section 4, MATLAB code] The code comment describes a function logW(c,B,eps), but the actual function definition is 'function ret = I(c, B, eps)'. Since the main routine calls logW, the code as listed would not run unless an additional alias is defined.
- [Section 2, proof of Lemma 1] The citation for Cramér's theorem appears as '[ ?]' and should be '[3]'.
- [Throughout] Typos: 'supreme' should be 'supremum'; 'yetrelevant' should be 'yet relevant'; the phrase 'marked in blue' refers to colors not present in the printed text.
Circularity Check
No significant circularity: the proof applies external prior results and optimizes an independently derived lower bound; the W(m,k,1)=C(m,k) issue is a correctness defect, not circularity.
full rationale
The derivation chain is self-contained against external benchmarks. The core lower-bound formula θ ≥ 1 + (log d(U) - log s(U))/log q(U) is taken from Gyarmati–Hennecart–Ruzsa [2], and the explicit formulas s(U)=W(m,2L,2B) and d(U)=Σ C(m,k)|W(k,L−k,B−1)||W(m−k,L,B)| are quoted from Gerbicz [1]; neither citation is by the present author, so no self-citation is load-bearing. Lemma 1 invokes Cramér's theorem, an external probability result, and the numerical optimization over (B,r,a) is applied after the lower-bound expression is derived. Maximizing a validly derived bound is not fitting an input as a prediction, and no step assumes the target constant θ=1.173077. The paper's false assertion that C(m,k)=W(m,k,1) in inequality (5) is a concrete mathematical defect and a correctness risk, but it is not circularity: the claimed bound does not reduce, by construction, to an input or to a self-citation chain. Therefore the circularity score is 0.
Assumptions & free parameters
free parameters (3)
- B =
5 (integer base coordinate bound, best in Table 1)
- r =
not reported (optimized in (0.5,2))
- a =
not reported (optimized in (0,min(1,1/r)))
assumptions (4)
- standard math Cramer's theorem for iid uniform random variables on {0,...,B}
- domain assumption The inequality theta >= 1 + log(|U-U|/|U+U|)/log(2max(U)+1) for finite U containing 0
- domain assumption The formulas s(U)=W(m,2L,2B) and d(U)=sum_k C(m,k)|W(k,L-k,B-1)||W(m-k,L,B)|
- domain assumption The base-(2B+1) encoding g is injective on sums and differences since coordinates and their pairwise sums are below the base
Cite this review
Pith. "Pith review of Sums and differences of sets: a further improvement over AlphaEvolve." pith.science (2026). https://pith.science/paper/BIIZNC2L
@misc{pith2026250601896,
author = {Pith},
title = {Pith review of: Sums and differences of sets: a further improvement over AlphaEvolve},
year = {2026},
howpublished = {\url{https://pith.science/paper/BIIZNC2L}},
note = {Machine review of arXiv:2506.01896}
}
abstract
We present a new advancement in the sum and difference of sets problem, which improves upon recent results by both DeepMind's AlphaEvolve ($\theta = 1.1584$) and subsequent explicit constructions ($\theta = 1.173050$). In this work, we construct a sequence of $U$ sets which in the limit establishes a new lower bound of $\theta = 1.173077$.
Reference graph
Works this paper leans on
-
[1]
https://arxiv.org/abs/2505.16105
Robert Gerbicz, Sums and differences of sets (improvement over AlphaE- volve), arXiv preprint arXiv:2505.16105, 2025. https://arxiv.org/abs/2505.16105
arXiv 2025
-
[2]
K. Gyarmati, F. Hennecart, and I. Z. Ruzsa, Sums and differences of finite sets , Functiones et Approximatio Commentarii Mathematici, 37(1):175–186, 2007. https://gyarmatikati.web.elte.hu/publ/sumdiffv.pdf
work page 2007
-
[3]
Achim Klenke, Probability Theory, Springer, Berlin, 2008, pp. 508. ISBN: 978-1-84800-047-6. DOI: 10.1007/978-1-84800-048-3
-
[4]
Alexander Novikov, Ngˆ an Vu, Marvin Eisenberger, Emilien Dupont, Po- Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog, AlphaEvolve: A coding agent for scientific and alg...
work page 2025
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.