A question of Bukh on sums of dilates

A question of Bukh on sums of dilates, Discrete Analysis 2021:13, 21 pp.

Let \(A\) and \(B\) be subsets of an Abelian group. Their sumset \(A+B\) is defined to be the set of all \(a+b\) such that \(a\in A\) and \(b\in B\). Many questions in additive combinatorics concern what can be said about the sets \(A\) and \(B\) given the cardinalities of \(A\), \(B\) and \(A+B\). In particular, if \(A+B\) is small, there are several results that show that \(A\) and \(B\) must have some kind of additive structure that explains this smallness.

If \(A\) is finite, then the doubling constant \(K(A)\) of \(A\) is defined to be \(|2A|/|A|\), where \(2A\) is standard shorthand for \(A+A\) (and more generally \(kA\) denotes the \(k\)-fold sum \(A+A+\dots+A\)). It is trivial that \(K(A)\geq 1\), and a simple exercise to show that equality holds if and only if \(A\) is a coset of a subgroup. (Another fairly simple exercise is that if \(A\) is a subset of \(\mathbb Z\) of size \(n\), then \(|A+A|\leq 2n-1\), with equality if and only if \(A\) is an arithmetic progression.)

A theorem of Plünnecke, which plays a central role in additive combinatorics, states that if \(|A+A|\leq C|A|\), then \(|rA-sA|\leq C^{r+s}|A|\) for every \(r,s\). In particular, \(|A+A+A|\leq C^3|A|\).

This inequality has the following trivial consequence. Write \(2.A\) for the dilate \(\{2a:a\in A\}\). (The notation \(2A\) might seem more natural, but sumsets arise more frequently than dilates, so it is preferable to reserve the more convenient notation for \(A+A\).) Then \(2.A\subset A+A\), and therefore if \(|A+A|\leq C|A|\), we can deduce that \(|A+2.A|\leq C^3|A|\). However, the set \(2.A\) is just a subset of \(A+A\), so it is natural to wonder whether this bound can be significantly improved.

A first point to note is that the bound \(|A+A+A|\leq C^3|A|\) is sharp up to an absolute constant. An example that shows this is the following simple construction of Imre Ruzsa. As usual, let \([r]\) denote the set \(\{1,2,\dots,r\}\). Then take a three-dimensional grid of the form \([r]^3\) and add to it the three one-dimensional sets \([s]\times\{0\}\times\{0\}\), \(\{0\}\times[s]\times\{0\}\), and \(\{0\}\times\{0\}\times[s]\). Calling this set \(A\), and assuming that \(r<s<r^3\), we have that \(|A|\sim r^3\), \(|A+A|\sim r^2s\), and \(|A+A+A|\sim s^3\), where \(\sim\) here means “equals up to an absolute constant”. Therefore, if we take \(s\) to be \(Cr\), we have that \(|A|\sim r^3\), \(|A+A|\sim Cr^3\) and \(|A+A+A|\sim C^3r^3\), showing that this is indeed an extremal example.

Boris Bukh asked whether there was some \(\alpha<3\) such that if \(|A+A|\leq C|A|\), then \(|2.A+A|\leq C^\alpha|A|\). Note that for Ruzsa’s example, \(|2.A+A|\sim C|A|\), so it is nowhere near to giving a negative answer to this question. And indeed, the main result of this paper is that there is such an \(\alpha\) – the authors manage to obtain \(\alpha=3-1/20\). Their proof uses a variety of tools and ideas from additive combinatorics: Plünnecke’s inequality (but in a less trivial way, and making particular use of the main idea of a proof of the inequality by the second author), the Balog-Szemerédi-Gowers theorem, the Katz-Koester inclusion, and a structure/randomness dichotomy. The basic structure of the proof is to start with a subtle covering lemma, which yields a partition of \(A\) into carefully chosen sets \(B^{(1)},\dots,B^{(k)}\), each of which has at least one of three properties (it is here that there is a contrast between structure and randomness) and to show using these properties and the tools mentioned above that the sum \(\sum_i|A+2.B^{(i)}|\) is small.

The authors also prove other results that follow from the same ideas: for instance, they obtain a similar result for \(2.A-A\) under the assumption that both \(|A+A|\leq C|A|\) and \(|A-A|\leq C|A|\).