The Gyarmati-Hennecart-Ruzsa sum-difference constant
Description of constant
$C_{3a}$ is the largest constant such that there exist arbitrarily large sets $A,B$ of integers such that \(|A+B| \ll |A|\) and \(|A-B| \gg |A+B|^{C_{3a}}.\)
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $4/3 = 1.333\dots$ | [GHR2007] |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $1$ | Trivial | |
| $2 - \frac{\log 6}{\log 7} = 1.0792\dots$ | [Ru96] | Elementary construction from $U = \{0,1,3\}$, which has $\lvert U+U\rvert = 6$ and $\lvert U-U\rvert = 7$; reported in [GHR2007, §1]. |
| $1.1078\dots$ | [GHR2007] | The lemma below applied to $U = \{0,1,3,6,13,17,21\}$, with $\lvert U+U\rvert = 26$, $\lvert U-U\rvert = 39$ and $q = 43$. Found by exhaustive search to be optimal over all $U$ with $\lvert U\rvert \le 11$. |
| $1.1165\dots$ | [GHR2007] | Projection to $\mathbb{Z}$ of the simplex set $V(m,L) = \{x \in \mathbb{N}^m : x_1 + \dots + x_m \le L\}$ of [HRY1999], with $m = 8$, $L = 9$: $\lvert U+U\rvert = 1562275$, $\lvert U-U\rvert = 23301307$, $q = 11668193551$. |
| $1.135596$ | [GHR2007] | Same construction with $m = 9$, $L = 7$ and a greedy choice of projection multipliers that preserves the number of sums: $\lvert U+U\rvert = \binom{23}{9} = 817190$, $\lvert U-U\rvert = 12494233$, $q = 542817927$. |
| $1.14465$ | [GHR2007] | Theorem 1 of [GHR2007]. Same construction with $m = 11$, $L = 7$ and the condition $L_j > LL_{j-1}$ relaxed, so that a few sums and differences are lost in the projection. See the note below on reproducing this value. |
| $1.1479$ | [GGSWT2025] | AlphaEvolve (Problem 6.44 of [GGSWT2025]), maximizing the lemma value below over a set $U_1$ of $2003$ integers. |
| $1.1584$ | [GGSWT2025] | AlphaEvolve, from a related set $U_2$ of $54265$ integers found by running the same experiment longer. This, not $1.1479$, is the final figure reported in [GGSWT2025, §6.25]. |
| $1.173050$ | [G2025] | |
| $1.173077$* | [Z2025] | “We construct a sequence of $U$ sets which in the limit establishes a new lower bound of $\theta = 1.173077$”; not certified by a finite-depth computation. |
| $1.1740744$ | [G2026] | Base-$21$ digit construction with exact counting certificate. |
| $1.1835129324$ | [MI2026] | Base-$33$ digit construction with exact counting certificate. |
| $1.187326127925948$* | [Num2026] | Capped base-$89$ digit construction (max digit $44$, sparse 29-letter alphabet); certified as the large-deviation LIMIT of the exact per-depth lemma values $\theta(U_d)$, each valid for every $d$ and increasing to the limit (the same limit-as-lower-bound principle as [Z2025]); interval-arithmetic certificate, replayable checker included. |
| $1.19102809$* | [K2026] | Base-$34065$ masked-digit limit construction with $M=\langle1518,1524,1587,2024,2032,2116\rangle\cap[0,17032]$ and a directed-rounding certificate. |
Additional comments and links
- A lemma from [GHR2007] states that a finite set $U$ of non-negative integers containing zero and satisfying $\lvert U-U\rvert<2\max(U)+1$ yields $C_{3a} \geq 1 + \log( \lvert U-U \rvert /\lvert U+U \rvert )/\log(2 \max(U)+1)$. Lower bounds obtained in this fashion cannot exceed $1.25$.
- Certified values and limits (the asterisked rows). As set out in CONTRIBUTING.md, the Bound column is meant to hold values that a reader can recompute directly. The rows marked $$ are instead *limits: each is the supremum of a sequence of per-depth lemma values $\theta(U_d)$, every one of which is itself a valid lower bound, so the limit is a valid lower bound too — but none of them is certified by a finite-depth computation, and each rests on the asymptotic analysis in its cited source. The largest value here certified by exact finite counting is $1.1835129324$ [MI2026]; per [Num2026], applying the limit principle to that same base-$33$ alphabet would already give $1.18552$.
- Reproducing the $1.14465$ of [GHR2007]. The final construction of [GHR2007, §2] is recorded there with $\lvert U+U\rvert = 4455634$, $\lvert U-U\rvert = 110205905$ and $q = 2\max U + 1 = 5723906483$, and the exponent is stated as $\theta = 1.144655$ (Theorem 1 asserts $\theta_0 > 1.14465$). Substituting those three values into the lemma gives $1 + \log(110205905/4455634)/\log(5723906483) = 1.142789\dots$, which is smaller. The same substitution reproduces the paper’s other stated exponents to six decimal places ($1.1078\dots$, $1.1165757\dots$ and $1.135589\dots$ against a printed $1.135596$), so the method of checking appears sound; the printed multiplier sequence $\Lambda$ for $m = 11$ may not be the one that produced the record. All later entries in the table exceed $1.14465$ regardless, so nothing downstream depends on this.
- [K2026] generalizes the bounded-digit limit construction in [Z2025] by replacing bounded digits with digits restricted to a finite mask.
- The record mask in [K2026] is generated by the product grid $\{3,4\}\times\{506,508,529\}$; its column semigroup is the simple gluing $\langle506,508,529\rangle=23\langle22,23\rangle+508\mathbb N_0$.
- AlphaEvolve repository page for this problem
References
- [GGSWT2025] Georgiev, Bogdan; Gómez-Serrano, Javier; Tao, Terence; Wagner, Adam Zsolt. Mathematical exploration and discovery at scale. arXiv:2511.02864
- [G2025] Gerbicz, Robert. Sums and differences of sets (improvement over AlphaEvolve), 2025. arXiv:2505.16105.
- [GHR2007] Gyarmati, Katalin; Hennecart, François; Ruzsa, Imre Z. Sums and differences of finite sets. Functiones et Approximatio Commentarii Mathematici, 37(1):175–186, 2007.
- [HRY1999] Hennecart, François; Robert, Gilles; Yudin, Alexander. On the number of sums and differences. In: Structure Theory of Set Addition, Astérisque 258 (1999), 173–178.
- [Ru96] Ruzsa, Imre Z. Sums of finite sets. In: Number Theory (New York, 1991–1995), Springer, New York, 1996, pp. 281–293.
- [MI2026] Mosaic Intelligence (@111111). Exact-count certificate for problem 3a, certificate archive, submitted to this repository (2026).
- [Num2026] Numaro (numaro.tech). Large-deviation limit certificate for a base-89 capped digit construction, certificate archive, submitted to this repository (2026).
- [Z2025] Zheng, Fan. Sums and differences of sets: a further improvement over AlphaEvolve, 2025. arXiv:2506.01896.
- [G2026] Griego, Sebastian. Base-$21$ digit construction certificate for $C_{3a}$, submitted to this repository (2026).
- [K2026] Kleinwaks, Logan. A masked-digit lower bound for the Gyarmati–Hennecart–Ruzsa sum–difference constant, proof and verification package, submitted to this repository (2026).