A sum-difference construction

Let $A$ be a finite set in an abelian group. A rich seam of questions in additive combinatorics concerns the relationship between the sizes of $A$ under simple arithmetic operations. For example, consider the doubling constant $\sigma=\abs{A+A}/\abs{A}$ and the difference constant is $\delta=\abs{A-A}/\abs{A}$. Ruzsa [Ru96] proved that $\delta\leq \sigma^2$. The exponent $2$ here is the best possible; this is demonstrated by taking $A$ to be the lattice points in a $d$-dimensional simplex, whence $\sigma\approx 2^d$ and $\delta\approx \binom{2d}{d}$. (This example originated in work of Freiman and Pigaev [FrPi73].)

The Plünnecke-Ruzsa inequalities imply a similar converse inequality $\sigma\leq \delta^2$. Despite a wealth of examples and constructions for similar-looking inequalities (many of them by Ruzsa, see e.g. Chapter 2 of his lecture notes), it was unknown whether $\sigma\leq \delta^c$ for some $c<2$ is possible.

The new construction of Lin, Li, and the Hyra AI research model [LiLi26] proves that the exponent cannot be improved past $2$. The previous record for this problem was achieved by Penman and Wells [PeWe13], who constructed arbitrarily large $A$ for which

\[\sigma\geq \delta^{1.0305\cdots}.\]

This was done by producing a single finite example (of size $67$) and using the tensor power trick of replacing $A\subseteq G$ by $A^d\subseteq G^d$ and noting that the quantities $\sigma$ and $\delta$ are replaced by $\sigma^d$ and $\delta^d$.

The new construction

Lin, Li, and Hyra

For arbitrarily large $K$ there exists $A$ (a finite set in some abelian group) such that $\abs{A+A}\gg K\abs{A}$ and $\abs{A-A} \ll K^{1/2}\abs{A}$.

The description in [LiLi26] is longer than it needs to be (in part because of their desire to construct an example in $\mathbb{Z}$, which is redundant via the machinery of Freiman isomorphisms, and in part because of the tracking of explicit constants, which is not needed). I'll present a simplified digest of the idea. Roughly speaking, the largeness of $A+A$ comes from the largeness of $S+S$, where $S$ is a Sidon set. To prevent $A-A$ also blowing up we 'twist' $S$ with a set $B$ where $\abs{B+B}$ is much larger than $\abs{B-B}$. Finally, since we are concerned not just with $\abs{A+A}$ and $\abs{A-A}$ but their size relative to $\abs{A}$, we throw in some large group component to make sure $\abs{A}$ grows suitably also.

Let $G$ and $H$ be two abelian groups, of sizes $L$ and $K$ respectively. Let $S\subset H$ be a Sidon set of size $\asymp K^{1/2}$ (this is easily constructed in a number of ways). Let $B\subseteq G$ be a set to be chosen later, and let

\[A=(G\times \{0\})\cup (B\times S).\]

The size, doubling constant, and difference constant of $A$ are easily estimated:

\[\lvert A\rvert\asymp L+\lvert B\rvert K^{1/2}\asymp L,\]

say, provided $\lvert B\rvert\ll L/K^{1/2}$. Secondly, since $\lvert S+S\rvert \gg K$,

\[\frac{\lvert A+A\rvert}{\lvert A\rvert}\gg \frac{\lvert B+B\rvert\lvert S+S\rvert}{L}\asymp K,\]

provided $\abs{B+B}\gg L$. Finally, using the trivial $\abs{S-S}\leq K$,

\[\frac{\lvert A-A\rvert}{\lvert A\rvert} \ll \frac{L+\lvert B-B\rvert K+L\lvert S\rvert}{\lvert A\rvert}\asymp K^{1/2}\]

provided $\lvert B-B\rvert \ll LK^{-1/2}$.

This set $A$ therefore provides the required example, as long as we can find some suitable $B\subseteq G$ with $\abs{B+B}\gg \lvert G\rvert$ and $\lvert B-B\rvert\ll \abs{G}K^{-1/2}$ (note the second condition automatically implies $\abs{B}\ll \abs{G}K^{-1/2}$ also). This can be provided by taking any fixed candidate $B'\subseteq G'$ in which $B'+B'=G'$ and $B'-B'\neq G'$ and blowing up using the tensor power trick, so taking $B=(B')^d$. Then $\abs{G}=\lvert G'\rvert^d$ and $\lvert B-B\rvert=(\frac{\lvert B'-B'\rvert}{\lvert B'+B'\rvert})^d\abs{G}\asymp K^{-1/2}\abs{G}$, say, and $K$ can be made arbitrarily large by taking $d\to \infty$. Examples of such $B'$ can be found via computation; [LiLi26] uses the example

\[B=\{0,1,2,4,5,9\}\subseteq \bbz/12\bbz.\]

Note that one could try to use $B$ itself to get a construction with large doubling constant and small difference constant; the advantage of the 'twisted' construction given above is that we don't need to worry at all about what the size of $\lvert B\rvert$ is!

Generalisations

This same idea can be used more widely: in general, let $B\subseteq G$ and $S\subset H$ be any set of size $K$ which is dissociated. Let $l_1,l_2,k_1,k_2\in \bbz$ (not both zero). Let $A$ be defined as above with $\abs{A}\asymp L=\abs{G}$, valid provided $\abs{B}\ll L/K$. Since $S$ is dissociated, $\abs{l_1S-k_1S}\gg K^{l_1+k_1}$ and so, by the calculation above,

\[\frac{\abs{l_1A-k_1A}}{\abs{A}}\gg K^{k_1+l_1}\]

provided $\abs{l_1B-k_1B}\gg L$, and similarly

\[\frac{\abs{l_2A-k_2A}}{\abs{A}}\ll K^{k_2+l_2-1}\]

provided $\abs{l_2B-k_2B}\ll L/K$. Constructing $B$ as above, by taking any fixed example and taking arbitrarily large powers, yields the following.

Let $l_1,l_2,k_1,k_2\in \bbz$ be such that there exists some finite $B\subseteq G$ where $l_1B-k_1B=G$ and $l_2B-k_2B\neq G$. Then for arbitrarily large $K$ there exists $A$ (a finite set in some abelian group) such that

\[\abs{l_1A-k_1A}\gg K^{k_1+l_1}\abs{A}\]

and

\[\abs{l_2A-k_2A} \ll K^{k_2+l_2-1}\abs{A}.\]

For example, if we choose $B=\{0,1,3\}\subset \bbf_7$ then $B-B=\bbf_7$ but $B+B=\{0,1,2,3,4,6\}$, so this construction yields arbitrarily large $K$ with associated $A$ for which $\abs{A-A}\gg K^2\abs{A}$ and $\abs{A+A}\ll K\abs{A}$. This provides another construction which shows that $\delta \ll \sigma^2$ cannot be improved -- in fact this is superior to the simplex construction, which actually has $\delta \gg \frac{\sigma^2}{\sqrt{\log \sigma}}$ (rather than $\delta \gg \sigma^2$ as in this construction). This therefore answers (in the negative) a question of Ruzsa which asked whether $\delta \leq \sigma^2$ can be improved by some factor of the shape $(\log \sigma)^c$.

As another example, if one takes $B=\{0,1,2\}\subset \bbf_7$ then $B+B+B=\bbf_7$ but $B+B=\{0,1,2,3,4\}$, and so this construction yields arbitrarily large $K$ with associated $A$ for which

\[\abs{A+A+A}\gg K^3\abs{A}\]

and

\[\abs{A+A}\ll K\abs{A}.\]

Sets with this property were already constructed by Ruzsa, but this offers an alternative (and perhaps simpler) construction.

This raises the interesting question of characterising those quadruples $l_1,l_2,k_1,k_2\in \bbz$ for which there exists some finite $B\subseteq G$ where $l_1B-k_1B=G$ and $l_2B-k_2B\neq G$. This is clearly impossible if $l_2\geq l_1$ and $k_2\geq k_1$; this is probably the only obstruction. It is easy to construct such sets if $k_1+l_1>k_2+l_2$.

EDIT: In fact recent work by Kravitz [Kr26] proves that such quadruples are precisely those for which $\min(k_2,l_2)>\min(k_1,l_1)$ or $\max(k_2,l_2)>\max(k_1,l_2)$.