Single-set sum-difference exponent — open problem in combinatorics

Description of constant

For a finite nonempty subset $A$ of an abelian group, write

$σ (A) := \frac{∣ A + A ∣}{∣ A ∣}, δ (A) := \frac{∣ A - A ∣}{∣ A ∣}$

for the doubling and difference constants. Ruzsa [Ru96] proved $δ \leq σ^{2}$ , and the Plünnecke–Ruzsa inequalities give the converse $σ \leq δ^{2}$ [Bl26].

For $∣ A ∣ \geq 2$ with $δ (A) > 1$ , set $C (A) := lo g σ (A) / lo g δ (A)$ , and define

$C_{3 d} := A sup C (A)$

over all such finite $A$ ; equivalently, $C_{3 d}$ is the least exponent $θ$ for which $σ (A) \leq δ (A)^{θ}$ holds for every finite $A$ . The Plünnecke–Ruzsa bound is exactly the assertion $C_{3 d} \leq 2$ , and the question — open until 2026 — was whether $σ \leq δ^{c}$ is possible for some $c < 2$ .

Sums and differences are not interchangeable for a single set, so this is a genuinely one-sided question; the optimality of the exponent $2$ in the companion inequality $δ \leq σ^{2}$ was already known (see below). The problem is now solved: $C_{3 d} = 2$ , by [LiLi26]. The value is approached but not attained by the known constructions.

The supremum is the same whether $A$ ranges over finite subsets of $Z$ or over finite subsets of arbitrary abelian groups, since a finite subset of an abelian group is Freiman-isomorphic to a subset of $Z$ [Bl26].

Known upper bounds

Bound	Reference	Comments
$2$	[Ru96]	$σ \leq δ^{2}$ . Attributed to [Ru96, Theorem 4.1] in [GGSWT2025, Problem 6.42]; [Bl26] describes it as a consequence of the Plünnecke–Ruzsa inequalities.

Known lower bounds

Bound	Reference	Comments
$\frac{l o g ( 59/17 )}{l o g ( 55/17 )} = 1.059793 \dots$	[FrPi73]	From the $17$ -element set $A = 0, 1, 2, 4, 5, 9, 12, 13, 14, 16, 17, 21, 24, 25, 26, 28, 29$ , which has $∣ A + A ∣ = 59$ and $∣ A - A ∣ = 55$ [GGSWT2025, Problem 6.42]. Used as the baseline in [GGSWT2025] and quoted as such by [LiLi26].
$\frac{l o g ( 32/5 )}{l o g ( 26/5 )} = 1.125944426 \dots$	[PeWe13]	Theorem 21 of [PeWe13]: the supremum of $C (Q_{j})$ over their family $Q_{j}$ , approached as $j \to \infty$ but not attained. From their Corollary 13, $∣ Q_{j} ∣ = 5 j + 17$ , $∣ Q_{j} + Q_{j} ∣ = 32 j + 63$ and $∣ Q_{j} - Q_{j} ∣ = 26 j + 61$ , whence $σ \to 32/5$ and $δ \to 26/5$ . This held the record until [LiLi26].
$\approx 1.1219$	[GGSWT2025]	This constant is Problem 6.42 of [GGSWT2025], where AlphaEvolve found $A = A_{1} \cup A_{2}$ with $A_{1} = - 159, - 158, \dots, 111$ and $A_{2}$ an explicit $38$ -element set, with no human hints. Inferior to the Penman–Wells record.
$2$	[LiLi26]	Solves the problem: $C_{3 d} = 2$ . Explicit family with $σ ≫ K$ and $δ ≪ K^{1/2}$ for arbitrarily large $K$ ; [LiLi26] states it as $C (A_{K}) > \frac{2 K}{K + 3}$ for every positive even $K$ .

Additional comments and links

The construction. [Bl26] gives a short digest, in a form cleaner than the original. Let $G, H$ be abelian groups of sizes $L, K$ , let $S \subset H$ be a Sidon set of size $≍ K^{1/2}$ , let $B \subseteq G$ , and set $A = (G \times {0}) \cup (B \times S) .$ Then $∣ A ∣ ≍ L$ provided $∣ B ∣ ≪ L / K^{1/2}$ ; the largeness of $A + A$ comes from $∣ S + S ∣ ≍ K$ , giving $σ ≫ ∣ B + B ∣ ∣ S + S ∣ / L ≍ K$ provided $∣ B + B ∣ ≫ L$ ; and the trivial $∣ S - S ∣ \leq K$ gives $δ ≪ K^{1/2}$ provided $∣ B - B ∣ ≪ L K^{- 1/2}$ . Hence $σ ≫ δ^{2}$ up to constants, and $C (A) \to 2$ as $K \to \infty$ .

Everything therefore reduces to finding a fixed $B^{'} \subseteq G^{'}$ with $B^{'} + B^{'} = G^{'}$ but $B^{'} - B^{'} \neq = G^{'}$ , then setting $B = (B^{'})^{d}$ and letting $d \to \infty$ . [LiLi26] use $B^{'} = {0, 1, 2, 4, 5, 9} \subseteq Z /12 Z,$ for which $B^{'} + B^{'}$ is all of $Z /12 Z$ while $B^{'} - B^{'}$ omits the class $6$ . The "twist" by $S$ is what makes the argument insensitive to the size of $∣ B ∣$ [Bl26].

[LiLi26] present a longer, fully explicit version that builds the example inside $Z$ by a Chinese-remainder construction over base- $12$ digit strings, and tracks explicit constants; [Bl26] observes that both features are avoidable.

Two normalizations — a caution. [PeWe13, §4] track two quantities: the unnormalized $f (A) = \frac{lo g ∣ A + A ∣}{lo g ∣ A - A ∣} and g (A) = \frac{lo g (∣ A + A ∣ / ∣ A ∣)}{lo g (∣ A - A ∣ / ∣ A ∣)},$ the latter being the $C (A)$ used on this page. The classical bounds differ accordingly: $3/4 \leq f \leq 4/3$ [FrPi73] and $1/2 \leq g \leq 2$ [Gra06], and so do their records — their Theorem 20 gives $f (Q_{10}) ≃ 1.030597781$ , while their Theorem 21 gives $sup_{j} g (Q_{j}) = lo g (32/5) / lo g (26/5) ≃ 1.125944426$ . [Bl26] quotes the previous record as $σ \geq δ^{1.0305 \dots}$ , which mixes the two: $1.0305 \dots$ is the $f$ -value, whereas the exponent in $σ \geq δ^{c}$ is the $g$ -value $1.125944 \dots$ reported by [LiLi26] and recorded in the table above.

The companion direction. That the exponent $2$ in $δ \leq σ^{2}$ is optimal was classically shown by taking $A$ to be the lattice points of a $d$ -dimensional simplex, giving $σ \approx 2^{d}$ and $δ \approx (d 2 d)$ , an example originating in [FrPi73]. The same framework as above does better: taking $B^{'} = {0, 1, 3} \subset F_{7}$ , for which $B^{'} - B^{'} = F_{7}$ but $B^{'} + B^{'} \neq = F_{7}$ , yields $A$ with $∣ A - A ∣ ≫ K^{2} ∣ A ∣$ and $∣ A + A ∣ ≪ K ∣ A ∣$ , hence $δ ≫ σ^{2}$ outright. The simplex example only gives $δ ≫ σ^{2} / lo g σ$ , so this answers in the negative a question of Ruzsa asking whether $δ \leq σ^{2}$ can be improved by a factor of the shape $(lo g σ)^{c}$ [Bl26].

Generalizations. [Bl26] extends the construction to dilates: if $l_{1}, l_{2}, k_{1}, k_{2} \in Z$ admit a finite $B \subseteq G$ with $l_{1} B - k_{1} B = G$ and $l_{2} B - k_{2} B \neq = G$ , then for arbitrarily large $K$ there is $A$ with $∣ l_{1} A - k_{1} A ∣ ≫ K^{k_{1} + l_{1}} ∣ A ∣$ and $∣ l_{2} A - k_{2} A ∣ ≪ K^{k_{2} + l_{2} - 1} ∣ A ∣$ . Taking $B^{'} = {0, 1, 2} \subset F_{7}$ gives sets with $∣ A + A + A ∣ ≫ K^{3} ∣ A ∣$ and $∣ A + A ∣ ≪ K ∣ A ∣$ , recovering by a simpler route examples previously constructed by Ruzsa. [Kr26] determines exactly which quadruples $(l_{1}, l_{2}, k_{1}, k_{2})$ admit such a $B$ : precisely those with $min (k_{2}, l_{2}) > min (k_{1}, l_{1})$ or $max (k_{2}, l_{2}) > max (k_{1}, l_{1})$ .

Relation to the other constants in this family. $C_{3 a}$ is a two-set sums-versus-differences exponent under a different normalization ( $∣ A + B ∣ ≪ ∣ A ∣$ and $∣ A - B ∣ ≫ ∣ A + B ∣^{C_{3 a}}$ ); because $B \mapsto - B$ interchanges sums and differences there, it has no analogue of the one-sidedness above, and $C_{3 d} = 2$ says nothing directly about $C_{3 a} \leq 4/3$ . $C_{3 b}$ and $C_{3 c}$ are the Katz–Tao arithmetic-Kakeya sum-difference constants, in which the sumset is restricted to a graph $G \subset A \times B$ .

Thomas Bloom's note on the construction

References

[FrPi73] Freiman, G. A.; Pigaev, V. P. The relation between the invariants $r$ and $t$ . Kalinin. Gos. Univ., Moscow, 1973, pp. 172–174.
[Ru96] Ruzsa, I. Z. Sums of finite sets. In: Number Theory: New York Seminar (D. V. Chudnovsky, G. V. Chudnovsky, M. B. Nathanson, eds.), Springer-Verlag, 1996, pp. 281–293.
[PeWe13] Penman, D.; Wells, M. On sets with more restricted sums than differences. Integers 13 (2013), #A57. The relevant results are Theorems 20 and 21 of §4; see the caution on normalizations above.
[Gra06] Granville, A. An Introduction to Additive Combinatorics. Lecture notes; cited by [PeWe13] for the bounds $1/2 \leq g \leq 2$ . Published as: CRM Proceedings and Lecture Notes 43, American Mathematical Society, 2007, pp. 1–27.
[GGSWT2025] Georgiev, Bogdan; Gómez-Serrano, Javier; Tao, Terence; Wagner, Adam Zsolt. Mathematical exploration and discovery at scale. arXiv:2511.02864
[Kr26] Kravitz, N. Inequalities among higher-order difference sets, or, remarks on a construction of Ruzsa. Preprint (2026). arXiv:2606.27087
[LiLi26] Lin, Haowei; Li, Shanda. Settling the optimal exponent relating sumsets and difference sets. Preprint, 29 July 2026. arXiv:2607.27199. The construction and its proof were developed with the assistance of Hyra, an AI research agent based on the open-weights Hy3 model.
[Bl26] Bloom, T. F. A sum-difference construction. Note (2026). <https://thomasbloom.org/notes/sumdifferences.html> (accessed 31 July 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.