A question of Bukh on sums of dilates
- University of Georgia (GA)
- More about Brandon Hanson
- University of Georgia (GA)
- More about Giorgis Petridis
Editorial introduction
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∈A and b∈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+⋯+A). It is trivial that K(A)≥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 Z of size n, then |A+A|≤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|≤C|A|, then |rA−sA|≤Cr+s|A| for every r,s. In particular, |A+A+A|≤C3|A|.
This inequality has the following trivial consequence. Write 2.A for the dilate {2a:a∈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⊂A+A, and therefore if |A+A|≤C|A|, we can deduce that |A+2.A|≤C3|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|≤C3|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,…,r}. Then take a three-dimensional grid of the form [r]3 and add to it the three one-dimensional sets [s]×{0}×{0}, {0}×[s]×{0}, and {0}×{0}×[s]. Calling this set A, and assuming that r<s<r3, we have that |A|∼r3, |A+A|∼r2s, and |A+A+A|∼s3, where ∼ here means “equals up to an absolute constant”. Therefore, if we take s to be Cr, we have that |A|∼r3, |A+A|∼Cr3 and |A+A+A|∼C3r3, showing that this is indeed an extremal example.
Boris Bukh asked whether there was some α<3 such that if |A+A|≤C|A|, then |2.A+A|≤Cα|A|. Note that for Ruzsa’s example, |2.A+A|∼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 α – the authors manage to obtain α=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),…,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 ∑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|≤C|A| and |A−A|≤C|A|.