Additive energies on discrete cubes

Abstract

One definition of additive combinatorics is that it is the study of subsets of (usually Abelian) groups. Two much studied parameters associated with a subset $A$ are the size of its sumset $A+A=\{a+b:a,b\in A\}$ (or the product set $A.A=\{a.b:a,b\in A\}$ in the non-Abelian case) and its additive energy, which is the number of quadruples $(a,b,c,d)\in A^4$ such that $a+b=c+d$ (or in the non-Abelian case the number of quadruples such that $ab^{-1}cd^{-1}$ equals the identity). However, sometimes it is interesting to look at subsets of structures that have group-like features but are not actually groups. A natural such structure is the Boolean hypercube $\{0,1\}^n$ considered as a subset of $\mathbb Z^n$ (as opposed to being considered as the group $\mathbb F_2^n$). Obviously, a subset $A$ of $\{0,1\}^n$ is a subset of a group in the sense that it is a subset of $\mathbb Z^n$. However, it is more natural to think of $\{0,1\}^n$ as the "ambient set" in this case, and to look at how it affects the additive properties of $A$. For instance, an obvious question is how small $A+A$ can be if $A\subset\{0,1\}^n$ and $|A|=N$. If $N=2^m$, then the example one might expect to be best possible is the set $\{0,1\}^m$, which has a sumset of size $3^m=N^{\log 3/\log 2}$, and this does indeed turn out to be the best possible. This is a result of Bourgain, Dilworth, Ford, Konyagin and Kutzarova. A more general construction that gives the same bound is any _geometric subspace_: that is, a subset defined by some collection of relations of the form $x_i=0$, $x_i=1$, $x_i=x_j$, or $x_i+x_j=1$, so that some coordinates are fixed, and some pairs of coordinates either have to be equal or have to be unequal. (One can also characterize geometric subspaces as those subsets of $\{0,1\}^n$ that are Freiman isomorphic to sets of the form $\{0,1\}^m$.) More recently, Kane and Tao obtained a lower bound for the additive energy of a subset (of given size) of $\{0,1\}^n$. Again, when the size of the subset is a power of 2, the best bound is given by sets of the form $\{0,1\}^m$, or more generally by geometric subspaces. The additive energy of the set $\{0,1\}$ is easily checked to be 6, so the bound they obtained was $6^m$, or more generally $N^{\log 6/\log 2}$. The way such results are typically proved is to take the set $A$ and split it into two subsets $A_0$ and $A_1$ according to the value of the first coordinate. If one devises a suitable inductive hypothesis involving functions taking values in $[0,1]$ rather than simply in $\{0,1\}$, most of the proof ends up being straightforward, but one is left needing an inequality for the real numbers, which often turns out to be surprisingly delicate and surprisingly hard to prove. That is the pattern in this paper. Here the authors generalize the result of Kane and Tao in various directions (the "higher energies" of the title). The additive energy of a set has two natural generalizations, depending on whether one looks on the physical side or the Fourier side. On the physical side, the additive energy of a set $A$ is equal to $\|\chi_A*\chi_{-A}\|_2^2$ (where $\chi_A$ is the characteristic function of $A$). The obvious generalization here is to $\|\chi_A*\chi_{-A}\|_p^p$ for other values of $p$. In particular, if $p$ is a positive integer $k$, we obtain a quantity with a combinatorial interpretation: it is the number of $2k$-tuples $(a_1,\dots,a_{2k})\in A^{2k}$ such that $a_1-a_2=a_3-a_4=\dots=a_{2k-1}-a_{2k}$. On the Fourier side, the additive energy is equal to $\|\hat\chi_A\|_4^4$, where $\hat\chi_A$ is the Fourier transform of $\chi_A$. Again, one can look at $\|\hat\chi_A\|_p^p$ for other values of $p$, and when $p=2k$ for a positive integer $k$, one obtains another quantity with a combinatorial interpretation: this time it is the number of $2k$-tuples $(a_1,\dots,a_{2k})\in A^{2k}$ such that $a_1+\dots+a_k=a_{k+1}+\dots+a_{2k}$. The authors prove that once again these quantities are maximized, for sets of size $2^m$, by sets of the form $\{0,1\}^m$. This gives bounds of $(2^k+2)^m$ and $\binom{2k}2^m$, respectively. As with earlier results, the proof is inductive and goes via the obvious splitting of the set into two layers. And again the inequalities the authors end up needing to prove are far from straightforward. Somewhat surprisingly, the inequality they need for the second result involves Legendre polynomials. The authors go on to discuss what can be said about the additive energy of subsets of $\{0,1,\dots,r-1\}^n$ -- that is, subsets of high-dimensional grids. Here there is a significant additional difficulty, which is that the extremal sets are no longer the obvious ones, even when $r=3$, which makes it unlikely that exact bounds can be obtained, except perhaps in a few special cases. It is not very easy to write down an example that illustrates this. The authors provide one by formulating a different problem, which they call the _discrete extension problem_, and showing that the best bounds for that problem directly relate to the best bounds for the additive energy of a subset of the grid. Since the exponent they obtain for the discrete extension problem is strictly larger than the log of the additive energy of the set $\{0,1,2\}$ divided by $\log 3$, the result is established that sets of the form $\{0,1,2\}^m$ do not maximize additive energy. In principle one can read out an actual counterexample from this argument, but it would be less illuminating than the argument the authors already give, which explains where the example comes from.