The Gyarmati-Hennecart-Ruzsa sum-difference constant

Fact	Value	Source
Best lower bound with an explicit value (constant 3a)	1.1935968* [Syl2026] — Finite instantiation of [K2026b, Prop.	Tao's optimization constants
Best lower bound with an explicit value, independently verified (constant 3a)	1.1835129324 [MI2026] — Base-33 digit construction with exact counting certificate.	Tao's optimization constants
Best upper bound with an explicit value (constant 3a)	1.312373302115 [K2026c] — First improvement on [GHR2007]'s 4/3.	Tao's optimization constants

Description of constant

$C_{3 a}$ is the largest constant such that there exist arbitrarily large sets $A, B$ of integers such that $∣ A + B ∣ ≪ ∣ A ∣$ and $∣ A - B ∣ ≫ ∣ A + B ∣^{C_{3 a}} .$

Known upper bounds

Bound	Reference	Comments
$4/3 = 1.333 \dots$	[GHR2007]
$\frac{13524 e - 7359}{9451 e - 3286} = 1.312373302115 \dots$	[K2026c]	First improvement on [GHR2007]'s $4/3$ . Proved via an improved two-set sum-difference exponent, $∣ X - Y ∣ \leq ∣ X + Y ∣^{λ}$ 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{l o g 6}{l o g 7} = 1.0792 \dots$	[Ru96]	Elementary construction from $U = 0, 1, 3$ , which has $∣ U + U ∣ = 6$ and $∣ U - U ∣ = 7$ ; reported in [GHR2007, §1].
$1.1078 \dots$	[GHR2007]	The lemma below applied to $U = 0, 1, 3, 6, 13, 17, 21$ , with $∣ U + U ∣ = 26$ , $∣ U - U ∣ = 39$ and $q = 43$ . Found by exhaustive search to be optimal over all $U$ with $∣ U ∣ \leq 11$ .
$1.1165 \dots$	[GHR2007]	Projection to $Z$ of the simplex set $V (m, L) = x \in N^{m} : x_{1} + \dots + x_{m} \leq L$ of [HRY1999], with $m = 8$ , $L = 9$ : $∣ U + U ∣ = 1562275$ , $∣ U - U ∣ = 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: $∣ U + U ∣ = (9 23) = 817190$ , $∣ U - U ∣ = 12494233$ , $q = 542817927$ .
$1.14465$	[GHR2007]	Theorem 1 of [GHR2007]. Same construction with $m = 11$ , $L = 7$ and the condition $L_{j} > L L_{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 $θ = 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 $θ (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 = ⟨ 1518, 1524, 1587, 2024, 2032, 2116 ⟩ \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 = ⟨ 1971, 2016, 2100, 2628, 2688, 2800 ⟩ \cap [0, 26972]$ in base $27022$ and Lean-formalized explicit finite construction of $1.19102809$ with $M = ⟨ 1518, 1524, 1587, 2024, 2032, 2116 ⟩ \cap [0, 17032]$ in base $34065$ using $1 0^{13}$ digits. Also includes formalization of necessary results from [GHR2007].
$1.19230254$ *	[M2026]	Explicit finite construction at depth $N = 1 0^{13}$ on $V = 2 U$ in odd controlled-carry base $q = 27995 < 2 B + 1$ via residue-bijective mod- $q$ difference pruning (`residue_word_injective`): for $M = ⟨ 1518, 1524, 1587, 2024, 2032, 2116 ⟩ \cap [0, 17086]$ ( $∣ M ∣ = 3153$ , $∣ M + M ∣ = 18835$ ), selecting the minimum digit-sum representative $κ (d)$ from each complementary residue pair $r, q - r (mod q)$ yields a complete residue system $D \subseteq M - M$ ( $∣ D_{+} ∣ = 13997$ , $∣ D ∣ = 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_{3 a} (V) > 1.1923025406835$ (and $1.1922990483828$ on the [K2026] mask $B = 17032$ , $∣ M ∣ = 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 = 2 U$ : mask $M = ⟨ 1971, 2016, 2100, 2628, 2688, 2800 ⟩ \cap [0, 26972]$ , base $q = 27022$ , $x = 9004870224628742/ 2^{53}$ (`0x1.ffde1bafccc06p-1`), $ℓ = 1 0^{18}$ blocks of two digits ( $2 \times 1 0^{18}$ digits), no blocks at the self-inverse residue $q^{2} /2$ , type counts $N_{r} = ⌊ ℓ x^{c_{2} (r)} / Z_{2} (x)⌋$ 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$ ; $∣ M ∣ = 5869$ , $∣ M + M ∣ = 31274$ . Directed-rounding certificate (MPFR and Robbins bounds) plus two independent checkers and two independent histogram builders. The limit of the same family as $ℓ \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 = 2 U$ : mask $M = ⟨ 1971, 2016, 2100, 2628, 2688, 2800 ⟩ \cap [0, 26972]$ , base $q = 27022$ , $x = 9004879181054557/ 2^{53}$ (`0x1.ffde3d0d5025dp-1`), $ℓ = 1 0^{24}$ blocks of three digits ( $3 \times 1 0^{24}$ digits), no blocks at the self-inverse residue $q^{3} /2$ , type counts $N_{r} = ⌊ ℓ x^{c_{3} (r)} / Z_{3} (x)⌋$ 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$ ; $∣ M ∣ = 5869$ , $∣ M + M ∣ = 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 $ℓ \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 $∣ U - U ∣ < 2 max (U) + 1$ yields

$C_{3 a} \geq 1 + lo g (∣ U - U ∣ / ∣ U + U ∣) / lo g (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 $θ (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 $∣ U + U ∣ = 4455634$ , $∣ U - U ∣ = 110205905$ and $q = 2 max U + 1 = 5723906483$ , and the exponent is stated as $θ = 1.144655$ (Theorem 1 asserts $θ_{0} > 1.14465$ ). Substituting those three values into the lemma gives $1 + lo g (110205905/4455634) / lo g (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 $Λ$ 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 $⟨ 506, 508, 529 ⟩ = 23 ⟨ 22, 23 ⟩ + 508 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 = 2 B + 1 = 34065$ to odd controlled-carry bases $q < 2 B + 1$ by pruning $M - M$ to a single minimum-cost representative per complementary residue pair $r, q - r (mod q)$ and doubling $V = 2 U$ to preserve $∣ V - V ∣ < 2 max (V) + 1$ .
AlphaEvolve repository page for this problem
[K2026c] proves $∣ X - Y ∣ \leq ∣ X + Y ∣^{λ}$ for every pair of finite sets in any abelian group, with $λ = (9451 e - 3286) / (5378 e + 787) = 1.454277448906 \dots$ , improving the classical exponent $3/2$ , and the transfer $C_{3 a} \leq 2 - 1/ λ$ .

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_{3 a}$ , 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 = 1 0^{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_{3 a} > 1.19359680$ (and $C_{3 a} > 1.19281555$ ), theorem note, certificate and checkers (the $k = 2$ instance as first submitted: artefact commit ad16a46), submitted to this repository (2026).

What counts as progress

A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
A formal proof (Lean) of a known bound, or a precise error in a claimed one.
New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 87b4ebbd426f, Apache License 2.0; reformatted for this page. New records should also be reported there.

The Gyarmati-Hennecart-Ruzsa sum-difference constant

Current state (tracked automatically)

Nobody has worked on this problem here yet

Current state

The problem