A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space

A counterexample to a strong variant of the polynomial Freiman-Ruzsa conjecture, Discrete Analysis 2017:8, 6 pp.

Given a finite set $A$ of integers, define its sumset $A+A$ to be the set $\{x+y:x,y\in A\}$. A central question in additive combinatorics is the following: what can we say about a set $A$ if its sumset is small?

A remarkable theorem of Freiman, later given a different and very influential proof by Imre Ruzsa, gives a complete answer to this question, at least qualitatively speaking, when “small” is interpreted as “of size at most $C|A|$” for an absolute constant $C$. An easy observation is that if $A$ is an arithmetic progression, then $|A+A|=2|A|-1$. Another easy observation is that if $|A+A|\leq C|A|$ and $B\subset A$ is a subset with $|B|\geq c|A|$, then $|B+B|\leq c^{-1}C|B|$. A slightly less easy observation is that “higher-dimensional progressions” have small sumsets: for example, a set $A$ of the form $\{a_0+d_1x+d_2y: 0 \leq x < m_1, 0 \leq y < m_2 \}$, which is a 2-dimensional arithmetic progression, has a sumset of size at most $4|A|$, roughly speaking because it expands by a factor 2 in each direction. Freiman’s theorem is the much less obvious statement that these observations give all examples: every set with a small sumset is a large subset of a low-dimensional arithmetic progression.

Freiman’s original argument gave very weak bounds. Although these were substantially improved by Ruzsa, and improved further by Chang, the theorem nevertheless had the following drawback. If you start with a set $A$ with a sumset of size at most $C|A|$ and apply Freiman’s theorem, then you obtain the information that $A$ is contained in an arithmetic progression of size at most $K|A|$ and dimension at most $d$, for constants $K$ and $d$ that depend on $C$. But if you use just this information and go back in the other direction, then all you can deduce is that such a set has sumset of size at most $2^dK|A|$, and even with Chang’s bounds for $d$ and $K$, $2^dK$ is far bigger than $C$. Thus, there is a sense in which Freiman’s theorem does not capture the full structure of a set $A$ with small sumset.

This situation was radically improved in 2010 by Sanders, who obtained a quasipolynomial version of the theorem: that is, if you apply the theorem and its trivial converse, you recover a constant that is at most $\exp((\log C)^t)$ for an absolute constant $t$. However, the holy grail is to obtain a characterization of sets with small sumset (or, as they are often called, sets with small doubling), that worsens the constant by at most a polynomial.

The polynomial Freiman-Ruzsa conjecture would, if true, give a characterization of this kind. To state it, we need the notion of a symmetric convex lattice set: that is, the intersection of a lattice with a symmetric convex body. If a convex lattice set has dimension $d$, it can be shown that its doubling constant is at most $5^d$. One can project a convex lattice set into a lower dimension and preserve this property, which gives a class of sets of small doubling that is more general than multidimensional arithmetic progressions: a multidimensional arithmetic progression is a projected convex lattice set for which the lattice is $\mathbb Z^d$ and the convex body intersecting it is an axis-aligned cuboid. If $B$ is a projected convex lattice set of bounded dimension, and $X$ is a set of bounded size, then $B+X$ still has small doubling, and the polynomial Freiman-Ruzsa conjecture is roughly that every set $A$ with $|A+A|\leq C|A|$ is contained in such a set, with the sizes of $B$ and $X$ and the dimension of the lattice being such that from this information alone one can recover a doubling constant of $P(C)$ for some fixed polynomial $P$.

Above, we observed that projections of convex lattice sets give us a more general class of sets of small doubling than multidimensional arithmetic progressions. But do we need this extra generality, given that we can also pass to large subsets? In a qualitative sense, we do not, by Freiman’s theorem (or by a direct argument using Minkowski’s second theorem). However, if we want a characterization that gives only a polynomial loss, then it is not obvious whether the extra generality is needed. That is the question addressed by this paper. (The paper deals with subsets of $\mathbb R^n$ rather than sets of integers but this makes no difference.) The authors prove that if one strengthens the polynomial Freiman-Ruzsa conjecture by insisting that the projected lattice convex bodies are multidimensional arithmetic progressions, then the resulting statement is false.

This answers a question of Ben Green. In some ways, the result is not surprising: Green expected the strengthened statement to be false, and if it is to be false, then the natural place to look for counterexamples is convex lattice sets that are as dissimilar as possible to aligned cuboids. So the authors’ counterexample – the intersection of a random lattice with a Euclidean ball – is a natural one. However, it is not clear how to prove that examples of this kind really are counterexamples. The main achievement of this paper is to observe that a recent result (a “reverse Minkowski theorem” due to the second author and Noah Stephens-Davidowitz) can be used to give a short proof, thereby confirming that the statement of the polynomial Freiman-Ruzsa conjecture is the “correct” one.