Additive energy amplification

In this note we give a proof of the following result of Katz and Koester. The statement in [KaKo] is slightly weaker, with $17/18$ replaced by $36/37$, but the following is essentially an identical proof, just slightly more optimised. The main point is that this exponent is $1-\epsilon$ for some absolute $\epsilon>0$: a simple application of the Cauchy-Schwarz inequality implies that $A$ itself satisfies $E(A)\geq K^{-1}\lvert A\rvert^3$.

We note that Schoen and Shkredov [ScSh, Theorem 61] also found a more optimised form of the Katz-Koester argument, which they used to deliver the exponent of $21/22$. The below is the most optimised form I have found thus far - it is an interesting challenge to improve this exponent further. Considering the additive energy of balls in high-dimensional Euclidean space (which as I learnt from the thesis of Przemysław Mazur is, in normalised form in $\mathbb{R}^d$, $\approx (4/3\sqrt{3})^d$, and which Shao has shown is best possible amongst all $d$-dimensional sets) leads to the fact that the best possible exponent is $\geq \log(3\sqrt{3}/4)/\log(2)\approx 0.3774\cdots$. This may well be best possible, but at $17/18$ we are still some way short.

We also remark that the proof below easily delivers stronger conclusions if we're happy to exit with asymmetric energy -- for example, we can find large $A,B\subset A-A$ such that $E(A,B) \gg K^{-3/4}\Abs{A}\Abs{B}^2$. There is, however, a much stronger statement possible for asymmetric energy due to Schoen, which we discuss below.

The key idea of the proof are the following observations, which has since become known as the 'Katz-Koester tricks': the first is that if $A_t=A\cap (A+t)$ then \[\textrm{if }x\in A_t-A\textrm{ then }t\in (A-A)_{x}.\] This is easily checked: let $x=a-b$ where $a\in A\cap (A+t)$, say $a=c+t$. It follows that $t=b-c+x\in (A-A)+x$, and since $A_t\neq \emptyset$ we also have $t\in A-A$ as required. The second is the similar identity \[A-B_t\subset (A-B)_t\] (and so, for example, $\Abs{A-A_t}\leq 1_{A-A}\circ 1_{A-A}(t)$.) Before embarking on the proof proper, we note the very useful fact that the size of $A_t$ is easily controlled since it is precisely $1_A\circ 1_A(t)$.

The Proof

The proof combines several techniques for finding different sets $A'$ with large additive energy, each of which is effective in different regimes. The final result follows by balancing these possibilities against each other. We will make liberal use of dyadic pigeonholing, and so use the notation $\ll$ and $\approx$ to hide losses of not only only constants, but also $(\log K)^{O(1)}$. It's also convenient to use the normalised notation $e(A)=E(A)/\Abs{A}^3$.

Let $1\leq K_0\leq K$ be such that $E(A)=\Abs{A}^3/K_0$. By dyadic pigeonholing, we can assume that most of the mass of \[\Abs{A}^2=\sum_{t\in A-A}1_A\circ 1_A(t)\] must come from differences $t\in A-A$ such that $\Abs{A_t}=1_A\circ 1_A(t)\approx \Abs{A}/K_1$ for some $1\leq K_1\ll K$. This set of differences, call it $T$, must have size $\approx K_1\Abs{A}$. Note that, by the Cauchy-Schwarz inequality, we also have $K_1\gg K_0$. By dyadic pigeonholing we may assume that $\Abs{A_t-A}$ is roughly constant for $t\in T$, say $\Abs{A_t-A}\approx K_2\Abs{A}$ for all $t\in T$. By the Katz-Koester trick, $1_{A-A}\circ 1_{A-A}(t) \gg K_2\Abs{A}$ for $t\in T$, whence \[E(A-A)\gg K_2^2K_1\Abs{A}^3,\] and so $e(A-A)\gg K_2^2K_1/K^3$. This shows the existence of a large $A'\subset A-A$ (in fact $A'$ is either $A$ or $A-A$) such that \[e(A')\gg \max\Brac{K_0^{-1}, K_1K_2^2K^{-3}}.\] If $K_2$ is large we can stop here. For example, if $K_2\approx K$, the largest it could be, then using $K_1\gg K_0$ the lower bound is \[ e(A') \gg \max\Brac{ K_0^{-1}, K_0K^{-1}}\gg K^{-1/2},\] which is better than the result we're after. Unfortunately, we cannot guarantee that $K_2$ is large (indeed, it's possible that $K_0\approx K_1\approx K$ and $K_2\ll K^{1/2}$, for example, in which case we recover the trivial bound $e(A')\gg K^{-1}$). We therefore introduce an alternative method that works well when $K_2$ is small.

By the Cauchy-Schwarz inequality, for any $t\in T$, \[E(A,A_t) \geq \frac{\Abs{A_t}^2\Abs{A}^2}{\Abs{A_t-A}}\gg K_2^{-1}\Abs{A}\Abs{A_t}^2.\] It follows by pigeonholing that there exists some $1\ll K_3\ll K_2$ and some $K_4$ such that, if $S_t$ is the set of those $x$ such that $1_A\circ 1_A(x) \approx K_3K_2^{-1}\Abs{A}$ and $1_{A_t}\circ 1_{A_t}(x)\approx K_4^{-1}\Abs{A_t}$ then $\Abs{S_t} \gg K_4K_3^{-1}K_1^{-1}\Abs{A}$ (these $K_3$ and $K_4$ may, of course, be different for each $t\in T$, but we can assume they are roughly constant by dyadic pigeonholing). It immediately follows that \[e(A_t)\gg K_3^{-1}K_4^{-1}.\] We now let $S=\cup_{t\in T}S_t$, so that \[\langle 1_{S}, \sum_{t\in T}1_{S_t}\rangle\gg \Abs{T}K_1^{-1}K_3^{-1}K_4\Abs{A}\gg K_3^{-1}K_4\Abs{A}^2,\] and pigeonhole once again to find some $S'\subset S$ such that the inner sum here is $\approx K_5\Abs{A}$ for all $x\in S'$, and $\Abs{S'}\approx \frac{K_4}{K_3K_5}\Abs{A}$. As above, the Katz-Koester trick combined with the fact that $S_t\subset A_t-A_t$ implies that \[1_{A-A}\ast 1_{A-A}(x)\gg K_5\Abs{A}\] for $x\in S'$. It follows that \[e(S')e(A-A)\gg\frac{K_5^4\Abs{S'}^4\Abs{A}^4}{\Abs{A-A}^5\Abs{S'}^3}\approx \frac{K_4K_5^3}{K^5K_3}\] whence we get energy bounds again. Finally, we also observe that if $x\in S'$ then $1_A\ast 1_A(x)\approx K_3K_2^{-1}\Abs{A}$, whence \[e(S')e(A)\gg \frac{K_3^4K_2^{-4}\Abs{A}^4\Abs{S'}^4}{\Abs{A}^5\Abs{S'}^3}\approx \frac{K_3^3K_4}{K_2^4K_5}\] and so \[e(S')\gg \frac{K_0K_3^3K_4}{K_2^4K_5}.\] The proof is now complete; we have obtained large subsets with large energy in a few different ways, and it remains to see what final quantitative gain we have achieved. Summarising, we have shown the existence of a large set $A'\subset A-A$ such that \[e(A')\gg \max\Brac{K_0^{-1},K_1K_2^2K^{-3}, \frac{1}{K_3K_4}, \frac{K_4^{1/2}K_5^{3/2}}{K^{5/2}K_3^{1/2}}, \frac{K_0K_3^3K_4}{K_2^4K_5}}.\] It remains to let the dust settle and see what the worst-case bounds of these five scenarios are. Suppose we want to end up with a lower bound of $K^{-c}$; if the first possiblity does not suffice then $K_0\gg K^c$, and so \[e(A')\gg \max\Brac{K_1K_2^2K^{-3}, \frac{1}{K_3K_4}, \frac{K_4^{1/2}K_5^{3/2}}{K^{5/2}K_3^{1/2}}, \frac{K^cK_3^3K_4}{K_2^4K_5}}.\] Either the first lower bound is $\gg K^{-c}$ or $K_2\ll K^{\frac{3-2c}{2}}$. We may also assume that $K_3K_4\gg K^c$. The lower bounds then become \[e(A')\gg \max\Brac{\frac{K^{c/2-5/2}K_5^{3/2}}{K_3}, \frac{K^{6c-6}K_3^2}{K_5}}.\] If we let $\kappa=K_3^2/K_5$ then \[e(A')\gg \max\Brac{K^{c/2-5/2}K_5\kappa^{-1/2}, K^{6c-6}\kappa}.\] At this point we would like a reasonable lower bound for $K_5$. For this we return to the above analysis, and note that since $1_A\circ 1_A(x)\approx K_3K_2^{-1}\Abs{A}$ for $x\in X'$, we must have $\Abs{X'}\ll K_2^2K_3^{-2}K_0^{-1}\Abs{A}$, whence (comparing the size of $X''\subset X'$) which is $\approx K_4K_3^{-1}K_5^{-1}\Abs{A}$) we have $K_5 \gg K_0K_3K_4/K_2^2$. Using our assumed lower bounds $K_0\gg K^c$, $K_3K_4\gg K^c$, and $K_2^2\ll K^{3-2c}$, we thus have $K_5\gg K^{4c-3}$, whence \[e(A')\gg \max\Brac{K^{\frac{9c-11}{2}}\kappa^{-1/2}, K^{6c-6}\kappa}.\] Balancing leads to $K^{\frac{1}{3}-c}\approx \kappa$, whence the lower bound is $K^{5c-\frac{17}{3}}$. Balancing this against $K^{-c}$ gives $c=17/18$ as claimed.

Schoen: an asymmetric version

In this section we prove a result of Schoen, an asymmetric version of the Katz-Koester lemma, which he used to improve the bounds for Freiman's theorem. The first part of the proof is to show that there exists $B\subset A$ such that $\Abs{A-B_t}\geq K^{-\epsilon}\Abs{A-B}$ for $\Omega(\Abs{B})$ many $t$, with $\Abs{B}\gg K^{-O(2^{\epsilon})}\Abs{A}$. This set is constructed iteratively: start with $A^1=A$, and in general suppose that $A^k$ has been defined. By considering large values only, we always have, for any set $B$, that there are $\Omega(\Abs{B})$ many $t$ such that $1_B\circ 1_B(t)\gg \Abs{B}^2/\Abs{B-B}$. If there exists $t\in A^k-A^k$ such that \[1_{A^k}\circ 1_{A^k}(t)\gg \frac{\Abs{A^k}^2}{\Abs{A^k-A^k}}\gg \frac{\Abs{A^k}^2}{K\Abs{A}}\] and \[\Abs{A-A_t^k}\leq K^{-\epsilon}\Abs{A-A^k}\] then we let $A^{k+1}=A^k_t$, otherwise we are done. We let $B$ be the halting point of this procedure, so $B=A^k$. Due to the second condition and the trivial lower bound $\Abs{A-C}\geq \Abs{A}$ this must terminate after $k \ll 1/\epsilon$ steps, and each time we take a squaring density hit, so $\Abs{B}\geq K^{-O(2^{1/\epsilon})}\Abs{A}$. We now observe that, if $T$ is the set of large values, then for all $t\in T$, \[1_{A-B}\circ 1_{A-B}(t)\geq \Abs{A-B_t}\geq K^{-\epsilon}\Abs{A-B}.\] Furthermore, there are $\gg \Abs{B}^2$ many pairs whose difference lies in $T$, whence there exists $b\in B$ such that $1_B\circ 1_T(b)\gg \Abs{B}$. In particular, letting $X$ be an appropriate translate of $T$, we have \[E(X, A-B)\gg K^{-2\epsilon}\Abs{A-B}\Abs{X}^2\] as required. This lemma may be applied to obtain a Bogolyubov-Ruzsa lemma; the main point is that we can now locate a Bohr set on the $K^{-\epsilon}$ spectrum of $X$, which has rank $O(2^{1/\epsilon}K^{O(\epsilon)})$. Choosing $\epsilon \approx (\log K)^{1/2}$ this yields rank $O(\exp(\sqrt{\log K}))$.