New lower bounds for cardinalities of higher dimensional difference sets and sumsets

New lower bounds for cardinalities of higher dimensional difference sets and sumsets, Discrete Analysis 2022:15, 19 pp.

Let $A$ be a finite subset of an Abelian group $G$. We define the sumset $A+A$ of $A$ to be the set $\{x+y:x,y\in A\}$ and the difference set $A-A$ to be the set $\{x-y:x,y\in A\}$. A famous result of Freiman states that for every constant $C$, if $A$ is a subset of $\mathbb Z$ and either $|A+A|$ or $|A-A|$ has size at most $C|A|$, then $A$ is contained in a $d$-dimensional arithmetic progression $P$ (that is, an affine image of the product of $d$ intervals of integers) such that $|P|\leq K|A|$, where $d$ and $K$ are constants that depend only on $C$.

Freiman’s proof appeared in a paper and a book in 1964 and 1966, respectively. It was long and complicated and its correctness was hard to verify, so it was a major development when in 1994 Imre Ruzsa found a different and significantly easier proof. Ruzsa’s proof broke up into several steps of independent interest that have gone on to become important tools in their own right.

However, Freiman’s proof also has value, especially since Yuri Bilu provided a considerably cleaned up version of it in 1999, removing any doubts there might have been about its correctness and highlighting its main ideas. One of Freiman’s lemmas is of particular interest: it gives a lower bound for the size of $|A+A|$ if we assume that $A$ is a subset of $\mathbb R^d$ that is genuinely $d$-dimensional, in the sense that it is not contained in any proper affine subspace of $\mathbb R^d$.

The bound Freiman gives is $|A+A|\geq(d+1)|A|-d(d+1)/2$, which a simple example (which can be found in this paper) shows is sharp up to an additive constant. However, sharp bounds have been harder to come by for the size of the difference set. In 1989, Freiman, Heppes and Uhrin obtained a lower bound of $(d+1)|A|-d(d+1)/2$ – that is, the same as the lower bound for $|A+A|$. However, the example that shows that the sumset bound is sharp does not do so for the difference set, except when $d\leq 2$, raising the possibility that a better lower bound is true.

The next main development was due to Stanchescu, who found an example that improved the lower bound for $|A-A|$ for all $d\geq 3$ and proved that it gave a sharp bound when $d=3$. This led to the natural conjecture that it gave a sharp bound for $d\geq 4$ as well. It is that conjecture that is proved in this paper, up to a small error term. That is, the main result of the paper is that $|A-A|$ must be at least

$\bigg(2d - 2 + \frac{1}{d-1} \bigg) |A| - O_{d}(|A|^{1- \delta})$

which compares with Stanchescu’s upper bound of

$\bigg(2d - 2 + \frac{1}{d-1} \bigg) |A| -(2d^2-4d+3)$.

While this is the headline result, the proof involves several intermediate statements of independent interest. It also provides an inverse theorem for sets for which the bound above is almost sharp. If $|A-A|$ is at most

$\bigg(2d - 2 + \frac{1}{d-1} +\frac{1}{(2d-3)(d-1)}\bigg) |A| - O_{d}(|A|^{1- \delta})$

then all but $O_d(|A|^{1-\delta})$ elements of $A$ must lie in a union of $2(d-1)$ parallel lines, $d-1$ of which must lie in a hyperplane and the other $d-1$ of which must lie in a parallel hyperplane.

In an independent development, David Conlon and Lim Jeck, building on earlier work of the author, proved the same result but without the error term – that is, they matched Stanchescu’s upper bound exactly. Thus, the problem of determining the best possible bound for difference sets of $d$-dimensional sets is now completely resolved.