The Gyarmati-Hennecart-Ruzsa sum-difference constant

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]

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].

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.
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_{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).

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 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.