A question of Bukh on sums of dilates

Abstract

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|$.

Locations

• Discrete Analysis - View - PDF
• DOAJ (DOAJ: Directory of Open Access Journals) - View