Unnormalized single-set sum-difference exponent
Description of constant
For a finite non-empty set $A$ of integers, $C_{3e}$ is the least constant such that
\[|A - A| \le |A + A|^{C_{3e}}\]for every such $A$; equivalently, $C_{3e} = \sup_A \log\lvert A-A\rvert / \log\lvert A+A\rvert$. This is Problem 6.43 of [GGSWT2025].
It measures how much larger the difference set can be than the sumset, without normalizing by $\lvert A\rvert$ — which is what distinguishes it from $C_{3d}$, the least $\theta$ with $\lvert A+A\rvert/\lvert A\rvert \le (\lvert A-A\rvert/\lvert A\rvert)^{\theta}$. The two normalizations have different classical bounds and different records, and conflating them has caused published confusion; see the caution below.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $\frac{3}{2}$ | Elementary | Ruzsa’s triangle inequality with $X = Y = Z = A$ gives $\lvert A-A\rvert \le \lvert A+A\rvert^2/\lvert A\rvert$, and $\lvert A+A\rvert \le \lvert A\rvert^2$ gives $\lvert A\rvert \ge \lvert A+A\rvert^{1/2}$; combining yields $\lvert A-A\rvert \le \lvert A+A\rvert^{3/2}$. |
| $\frac{4}{3} = 1.3333\dots$ | [FrPi73] | The classical Freiman–Pigaev inequality $\lvert A+A\rvert^{3/4} \le \lvert A-A\rvert \le \lvert A+A\rvert^{4/3}$. Quoted in this form by [GGSWT2025, Problem 6.43] and by [PeWe13, §4]. |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $1$ | Trivial | Any arithmetic progression has $\lvert A+A\rvert = \lvert A-A\rvert = 2\lvert A\rvert - 1$. |
| $\frac{\log(1+\sqrt{2})}{\log 2} = 1.2715\dots$ | [HRY1999] | The high-dimensional simplex $A = \{(x_1,\dots,x_N) \in \mathbb{Z}_{+}^{N} : x_1 + \dots + x_N \le N/2\}$, projected to $\mathbb{Z}$. See the note below for the asymptotics that produce this value. |
| $\approx 1.21$ | [GGSWT2025] | AlphaEvolve, given no human hints, did not recover the simplex construction within a few hours and reached only about $1.21$ — one of the cases [GGSWT2025] records as not matching the literature. Inferior to [HRY1999]. |
Additional comments and links
-
Where the $\log(1+\sqrt{2})/\log 2$ comes from. For $A = V(m, m/2) := \{x \in \mathbb{N}^m : x_1 + \dots + x_m \le m/2\}$, [GHR2007, §2 Remark] records the asymptotics \(\log |2A| = (2\log 2 + o(1))m, \qquad \log |A - A| = (2\log(1+\sqrt{2}) + o(1))m\) as $m \to \infty$, whence $\log\lvert A-A\rvert / \log\lvert A+A\rvert \to \log(1+\sqrt{2})/\log 2 = 1.27155\dots$. The cardinalities themselves are given by \(|V| = \binom{m+L}{m}, \qquad |2V| = \binom{m+2L}{m}, \qquad |V - V| = \sum_{k=0}^{\min(m,L)} \binom{m}{k}^2 \binom{L+m-k}{m}\) with $L = m/2$ [GHR2007, (14)], following [HRY1999].
-
Caution: two normalizations, two constants. [PeWe13, §4] track both \(f(A) = \frac{\log \lvert A+A\rvert}{\log \lvert A-A\rvert} \qquad\text{and}\qquad g(A) = \frac{\log(\lvert A+A\rvert/\lvert A\rvert)}{\log(\lvert A-A\rvert/\lvert A\rvert)},\) with classical bounds $3/4 \le f \le 4/3$ and $1/2 \le g \le 2$. The constant on this page is $\sup_A 1/f(A)$; $C_{3d}$ is $\sup_A g(A)$; and the Penman–Wells records $\sup_A f(A) \simeq 1.030597781$ and $\sup_A g(A) \simeq 1.125944426$ are two further, distinct quantities. Quoting an $f$-value as though it were a $g$-value is a mistake that has reached print; see the corresponding note on the $C_{3d}$ page.
-
The reverse direction. The companion constant, the least $C$ with $\lvert A+A\rvert \le \lvert A-A\rvert^{C}$, is $\sup_A f(A)$. It also satisfies $\le 4/3$ by [FrPi73], and the best construction known is the Penman–Wells family with $f(Q_{10}) \simeq 1.030597781$ [PeWe13, Theorem 20]. It is not separately recorded in this repository.
-
Relation to the other constants in this family. $C_{3a}$ is the two-set Gyarmati–Hennecart–Ruzsa exponent, under the constraint $\lvert A+B\rvert \ll \lvert A\rvert$; note that its $4/3$ upper bound comes from the same circle of Plünnecke–Ruzsa estimates. $C_{3b}$ and $C_{3c}$ are the Katz–Tao arithmetic-Kakeya sum-difference constants. In the numbering of [GGSWT2025] these are Problems 6.42 ($C_{3d}$), 6.43 (this page), 6.44 ($C_{3a}$) and 6.30 ($C_{3b}$, $C_{3c}$).
References
- [FrPi73] Freiman, G. A.; Pigaev, V. P. The relation between the invariants $R$ and $T$ (Russian). 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.
- [HRY1999] Hennecart, F.; Robert, G.; Yudin, A. On the number of sums and differences. In: Structure Theory of Set Addition, Astérisque 258 (1999), 173–178.
- [GHR2007] Gyarmati, Katalin; Hennecart, François; Ruzsa, Imre Z. Sums and differences of finite sets. Functiones et Approximatio Commentarii Mathematici 37(1) (2007), 175–186.
- [PeWe13] Penman, D.; Wells, M. On sets with more restricted sums than differences. Integers 13 (2013), #A57.
- [GGSWT2025] Georgiev, Bogdan; Gómez-Serrano, Javier; Tao, Terence; Wagner, Adam Zsolt. Mathematical exploration and discovery at scale. arXiv:2511.02864. This constant is Problem 6.43, in §6.25.
Contribution notes
Prepared with assistance from Claude Opus 5, working from §6.25 of [GGSWT2025] and the AlphaEvolve repository of problems, cross-checked against [GHR2007] and [PeWe13]. The elementary $3/2$ upper bound and the limit $\log(1+\sqrt{2})/\log 2$ were derived and checked here from the cardinality formulas recorded in [GHR2007]; the $4/3$ bound of [FrPi73] was not checked against the primary source, which is a 1973 Russian volume.