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] | |
| $\frac{13524e-7359}{9451e-3286} = 1.312373302115\dots$ | [K2026c] | First improvement on [GHR2007]’s $4/3$. Proved via an improved two-set sum-difference exponent, $\lvert X-Y\rvert \le \lvert X+Y\rvert^{\lambda}$ for all finite $X,Y$ in an abelian group, together with a multiscale transfer. Lean 4 formalization and proof paper supplied, registered as PALOMAR-2026-09-30-000021 v1 (trust level high; theorem SumDifferenceResults.multiscale_bound at pinned commit 9bd88c1). |
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. |
| $1.19102809$ ($1.19519192$*) | [K2026b] | Lean-formalized proof of $1.19519192$* via controlled-carry masked-digit limit construction with $M=\langle1971,2016,2100,2628,2688,2800\rangle\cap[0,26972]$ in base $27022$ and Lean-formalized explicit finite construction of $1.19102809$ with $M=\langle1518,1524,1587,2024,2032,2116\rangle\cap[0,17032]$ in base $34065$ using $10^{13}$ digits. Also includes formalization of necessary results from [GHR2007]. |
| $1.19230254$* | [M2026] | Explicit finite construction at depth $N = 10^{13}$ on $V = 2U$ in odd controlled-carry base $q = 27995 < 2B+1$ via residue-bijective mod-$q$ difference pruning (residue_word_injective): for $M = \langle 1518,1524,1587,2024,2032,2116\rangle \cap [0,17086]$ ($\lvert M\rvert = 3153$, $\lvert M+M\rvert = 18835$), selecting the minimum digit-sum representative $\kappa(d)$ from each complementary residue pair $\{r, q-r\} \pmod{q}$ yields a complete residue system $\widetilde{D} \subseteq M-M$ ($\lvert\widetilde{D}_+\rvert = 13997$, $\lvert\widetilde{D}\rvert = 27995 = q$); with $n_0 = 17074745018$, $L = 50031092045455301$ and $x_f = 0.9996683050229444$, both 60-digit interval arithmetic and pure integer-interval Stirling bounds certify $C_{3a}(V) > 1.1923025406835$ (and $1.1922990483828$ on the [K2026] mask $B=17032$, $\lvert M\rvert=3121$ at $q=27995$). |
| $1.19281555$* | [Syl2026] | Finite instantiation of [K2026b, Prop. 3] at block length $k=2$, applied through the lemma below to $V=2U$: mask $M=\langle1971,2016,2100,2628,2688,2800\rangle\cap[0,26972]$, base $q=27022$, $x=9004870224628742/2^{53}$ (0x1.ffde1bafccc06p-1), $\ell=10^{18}$ blocks of two digits ($2\times10^{18}$ digits), no blocks at the self-inverse residue $q^2/2$, type counts $N_r=\lfloor \ell x^{c_2(r)}/Z_2(x)\rfloor$ where $c_2(r)$ is the minimum witness cost of the residue $r$ mod $q^2$ (26540 distinct values), giving $n_0=3362808316958$ blocks at residue $0$ and total cost $C=26096544438312721237750$; $\lvert M\rvert=5869$, $\lvert M+M\rvert=31274$. Directed-rounding certificate (MPFR and Robbins bounds) plus two independent checkers and two independent histogram builders. The limit of the same family as $\ell\to\infty$ at this $x$ is $1.19281555778\dots$*, and this $x$ maximizes that limit, so $1.19281555$ is the best eight-decimal value of this certificate at $k=2$. Asterisked: self-archived artefact, verification package (SHA256SUMS sha256 08d8c3770ea4c8b459954efe122241eac39c1ae5d5c5bda3bc2c89e1a339ce84). |
| $1.19359680$* | [Syl2026] | Finite instantiation of [K2026b, Prop. 3] at block length $k=3$, applied through the lemma below to $V=2U$: mask $M=\langle1971,2016,2100,2628,2688,2800\rangle\cap[0,26972]$, base $q=27022$, $x=9004879181054557/2^{53}$ (0x1.ffde3d0d5025dp-1), $\ell=10^{24}$ blocks of three digits ($3\times10^{24}$ digits), no blocks at the self-inverse residue $q^3/2$, type counts $N_r=\lfloor \ell x^{c_3(r)}/Z_3(x)\rfloor$ where $c_3(r)$ is the minimum witness cost of the residue $r$ mod $q^3$ (54099 distinct values, computed exactly by a two-state carry automaton), giving $n_0=5794476231064238$ blocks at residue $0$ and total cost $C=39290318538006294714264853344$; $\lvert M\rvert=5869$, $\lvert M+M\rvert=31274$. Directed-rounding certificate (MPFR and Robbins bounds), a secondary interval-arithmetic checker and two histogram builders with byte-identical output. The limit of the same family as $\ell\to\infty$ at this $x$ is $1.19359680913\dots$*, so $1.19359680$ is the best eight-decimal value of this certificate at $k=3$. The same package also certifies $1.19281555$ at $k=2$. Asterisked: self-archived artefact, verification package (SHA256SUMS sha256 fb38267cbec0462d47453223aa9e7219ed443e8e4014a3776a7e92f112923c22). |
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$.
- [K2026b] generalizes [K2026] and [Z2025] by allowing constructions in arbitrary bases greater than the maximum element of the digit mask and accounting for carrying. The record mask is different from that of [K2026], but the semigroup generators again form a product grid.
- [M2026] extends the finite-depth injectivity lemma of [K2026b] (
residue_word_injective) from the carry-free base $Q = 2B+1 = 34065$ to odd controlled-carry bases $q < 2B+1$ by pruning $M-M$ to a single minimum-cost representative per complementary residue pair $\{r, q-r\} \pmod{q}$ and doubling $V = 2U$ to preserve $\lvert V-V\rvert < 2\max(V)+1$. - AlphaEvolve repository page for this problem
- [K2026c] proves $\lvert X-Y\rvert\le\lvert X+Y\rvert^{\lambda}$ for every pair of finite sets in any abelian group, with $\lambda=(9451e-3286)/(5378e+787)=1.454277448906\dots$, improving the classical exponent $3/2$, and the transfer $C_{3a}\le 2-1/\lambda$.
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).
- [K2026b] Kleinwaks, Logan. Improved lower bound for the Gyarmati–Hennecart–Ruzsa sum–difference constant using masked digits and controlled carries, proof, verification package, and Lean formalization, submitted to this repository (2026).
- [K2026c] Kleinwaks, Logan J. Improved sum–difference inequalities in abelian groups, proof paper and Lean formalization, PALOMAR-2026-09-30-000021 v1, submitted to this repository (2026).
- [M2026] mizopl, Claude (Anthropic), and Gemini (Google DeepMind). Explicit finite-depth ($N=10^{13}$) odd-base ($q=27995$) lower bound for the Gyarmati–Hennecart–Ruzsa sum–difference constant, proof paper, certificates, and verification package (2026).
- [Syl2026] Sylla. Finite $k=3$ (and $k=2$) controlled-carry certificates for $C_{3a} > 1.19359680$ (and $C_{3a} > 1.19281555$), theorem note, certificate and checkers (the $k=2$ instance as first submitted: artefact commit ad16a46), submitted to this repository (2026).