One-sentence Summary

Researchers from Tencent Hunyuan and Carnegie Mellon University, with assistance from the AI agent Hyra (based on Hy3), settle the optimal exponent in sum–difference inequalities by constructing explicit sets $A _ { K } \subset \mathbb { Z }$AK​⊂Z such that $\frac {\log \sigma (A _ {K})}{\log \delta (A _ {K})} \longrightarrow 2$logδ(AK​)logσ(AK​)​⟶2, proving the exponent $1/2$1/2 in $\sigma (A) ^ {1 / 2} \leqslant \delta (A)$σ(A)1/2⩽δ(A) is optimal.

Key Contributions

• An explicit infinite family of finite integer sets $A_K$AK​ is constructed that drives the log-ratio $\log\sigma(A)/\log\delta(A)$logσ(A)/logδ(A) arbitrarily close to 2, settling the previously open optimality of the exponent $1/2$1/2 in the classical sum-difference inequality $\sigma(A)^{1/2}\le\delta(A)$σ(A)1/2≤δ(A).
• The construction and its proof were developed with the assistance of the AI research agent Hyra (based on the Hy3 model), which autonomously optimized set constructions under a SimpleTES evaluation loop, raising the best found $C(A)$C(A) value from approximately 1.14 to 1.21 before human refinement.
• The supremum of $C(A)$C(A) over all finite nonempty integer sets is formally proved to be exactly 2, approached but not attained; a self-contained mathematical argument and a Lean 4 formal verification of the proof are provided.

Introduction

The authors address the classical sum–difference inequalities in additive combinatorics, which relate the relative sizes of a finite set’s sumset and difference set. For nonempty subsets of an abelian group, it is known that the difference-set ratio cannot exceed the square of the sumset ratio, and that this quadratic upper bound is sharp. However, the corresponding lower bound (the square root of the sumset ratio) had not been shown to be optimal.

Prior work left open whether the exponent 1/2 in that lower bound could be improved. The authors settle this question by constructing an explicit family of integer sets whose sumset and difference-set ratios asymptotically approach the extreme where the difference-set ratio is the square of the sumset ratio. Their construction combines a base-12 digit gadget with a symmetric additive basis in a cyclic group, joined via the Chinese remainder theorem, and the analysis uses a carry-propagation model to track the difference set’s growth.

Method

The authors construct a finite integer set $A_K$AK​ whose sumset is much larger than its difference set, providing a counterexample to the conjecture that $|A+A| \leq |A-A|$∣A+A∣≤∣A−A∣ for all finite sets of integers. The construction proceeds in three stages: a base-12 digit gadget, a symmetric additive basis in a cyclic group, and a Chinese remainder theorem (CRT) product that combines them.

The base-12 gadget uses a digit set $W = \{0, 1, 2, 4, 5, 9\} \subset \mathbb{Z}$W={0,1,2,4,5,9}⊂Z. Modulo 12, this set satisfies $(W + W) \bmod 12 = \mathbb{Z}/12\mathbb{Z}$(W+W)mod12=Z/12Z and $(W - W) \bmod 12 = (\mathbb{Z}/12\mathbb{Z}) \setminus \{6\}$(W−W)mod12=(Z/12Z)∖{6}. The authors then build sets $Y_j$Yj​ by concatenating $j$j digits from $W$W in base 12, so $Y_j \subseteq \{0, 1, \dots, 12^j - 1\}$Yj​⊆{0,1,…,12j−1} and $|Y_j| = 6^j$∣Yj​∣=6j. Lemma 2.1 shows that $(Y_j + Y_j) \bmod 12^j$(Yj​+Yj​)mod12j is the full cyclic group. The difference set modulo $12^j$12j is more restricted; its size $t_j = |(Y_j - Y_j) \bmod 12^j|$tj​=∣(Yj​−Yj​)mod12j∣ satisfies a linear recurrence $t_{j+2} = 13 t_{j+1} - 16 t_j$tj+2​=13tj+1​−16tj​, and $t_j$tj​ grows asymptotically like $\lambda^j$λj where $\lambda = (13 + \sqrt{105})/2 \approx 12.46$λ=(13+105​)/2≈12.46. Crucially, $\lambda/12 < 31/32$λ/12<31/32, so the difference set modulo $n = 12^d$n=12d is a sparse subset of the full group.

For the second component, fix a positive even integer $K$K and set $s = 2^K + 1$s=2K+1, $Q = s^2$Q=s2, and $m = (s-1)/2$m=(s−1)/2. Inside $\mathbb{Z}/Q\mathbb{Z}$Z/QZ, define $H = \{-m, \dots, m\}$H={−m,…,m} and $V = \{0, s, 2s, \dots, (s-1)s\}$V={0,s,2s,…,(s−1)s}. The set $I = H \cup V$I=H∪V is symmetric and forms an additive basis: $I + I = \mathbb{Z}/Q\mathbb{Z}$I+I=Z/QZ. Removing zero gives $B = I \setminus \{0\}$B=I∖{0}, and every element outside $I$I lies in both $B+B$B+B and $B-B$B−B.

The CRT construction ties these pieces together. With $d = 22(K+2)$d=22(K+2), $n = 12^d$n=12d, and $q = Qn$q=Qn, the modulus $Q$Q and $n$n are coprime. In the product group $\mathbb{Z}/q\mathbb{Z} \cong \mathbb{Z}/Q\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$Z/qZ≅Z/QZ×Z/nZ, the set $\mathcal{R}$R consists of a full zero row $\{0\} \times \mathbb{Z}/n\mathbb{Z}${0}×Z/nZ together with rows $\{b\} \times Y_d${b}×Yd​ for each $b \in B$b∈B. The integer set $R$R is the lift of $\mathcal{R}$R to $\{0, 1, \dots, q-1\}${0,1,…,q−1}. Finally, the construction is doubled: $A_K = R \cup (R + q) = R + q\{0,1\}$AK​=R∪(R+q)=R+q{0,1}. This doubling step is essential for amplifying the sumset while controlling the difference set.

The exact modular counts are established in Lemma 2.5 and Lemma 2.6. Modulo $q$q, the sumset $(R+R) \bmod q$(R+R)modq is the entire group of size $q = Qn$q=Qn. The difference set $(R-R) \bmod q$(R−R)modq has cardinality $\rho n + (Q - \rho)t$ρn+(Q−ρ)t, where $\rho = |I| = 2s-1$ρ=∣I∣=2s−1 and $t = t_d$t=td​. The outer coordinates in $I$I contribute full inner fibers of size $n$n, while the $Q-\rho$Q−ρ outer coordinates outside $I$I each contribute only $t$t elements from the base-12 difference gadget.

Lemma 2.7 lifts these modular counts to the integer set $A = R + q\{0,1\}$A=R+q{0,1}. The block sums from $q\{0,1\} + q\{0,1\}$q{0,1}+q{0,1} produce three distinct quotient indices $\{0,1,2\}${0,1,2}, so each modular sum residue expands to at least three integers, giving $|A+A| \geq 3|(R+R) \bmod q|$∣A+A∣≥3∣(R+R)modq∣. For differences, the block differences have indices $\{-1,0,1\}${−1,0,1} while the ordinary representatives in $R-R$R−R have indices in a subset of $\{-1,0\}${−1,0}; their sum has at most four elements, yielding $|A-A| \leq 4|(R-R) \bmod q|$∣A−A∣≤4∣(R−R)modq∣. The multiplicative gap between the exponential growth of $n$n and the sub-exponential growth of $t$t ultimately forces $|A+A|$∣A+A∣ to exceed $|A-A|$∣A−A∣ for sufficiently large $K$K.

Experiment

The evaluation setup combines explicit finite-set constructions with an AI-assisted search guided by the SimpleTES framework and Hyra to optimize the exponent relating sumsets and difference sets. The construction validates that the exponent can be pushed arbitrarily close to 2 from below, while the classical upper bound confirms that 2 is sufficient. Overall, the experiments demonstrate that the optimal universal exponent is exactly 2, with the supremum approached but not attained by any admissible integer set.

The table compares lower bounds on the sumset–difference set exponent from published mathematical constructions and AI agent searches. Historical human-designed sets gradually improved the ratio from about 1.03 to 1.13, while an AI agent (AlphaEvolve) reached 1.12. The manuscript's AI-guided optimization achieved a value around 1.21, surpassing all prior published results and highlighting the growing role of LLM-driven search in mathematical discovery. The earliest recorded construction, an eight-point MSTD set by Conway, gives a ratio of 1.0344, while the Penman–Wells family (2013) reaches 1.1259, the highest among published mathematical constructions. AlphaEvolve, using Gemini 2.0 Pro and Flash, found a construction with ratio 1.1219, slightly below the best human-designed family. The manuscript's autonomous search with Hyra (powered by Hy3 and guided by GPT-5.6 Sol) raised the best value from approximately 1.14 to 1.21, exceeding all previous published bounds. The theoretical result proves the optimal exponent is 2, with a family of sets approaching this limit arbitrarily closely; the table focuses on concrete finite-set lower bounds that remain far from this asymptotic optimum.

The evaluation compares lower bounds on the sumset–difference set exponent from historical human constructions, an AI agent, and an LLM-driven autonomous search. Human-designed sets gradually improved the ratio over decades, while the AI agent AlphaEvolve reached a value just below the best published mathematical family. The manuscript's Hyra system, guided by GPT-5.6 Sol, then pushed the bound significantly higher, surpassing all previous published results and underscoring the growing potential of large language models to accelerate mathematical discovery, even though these concrete finite-set bounds remain far from the theoretical asymptotic optimum.