Additive Energy of Real Point Sets

Over the years, more and more interactions between Discrete Geometry and Additive Combinatorics are being exposed. These include results such as the Green–Tao ordinary lines theorem and Solymosi’s sum-product bound. One reason for this connection is that both fields study the structure and symmetries of various objects (such as sets of points or subsets of additive groups). In this post I will discuss one of the simplest connections between the two fields — studying the additive energy of a set of points in a real space ${\mathbb R}^d$. The main goal of the post is to present two open problems that involve the additive energy of such sets. I heard one of these problems from Nets Katz and the other from Ciprian Demeter. In future posts we might discuss more involved interactions between the two fields.

Ciprian Demeter and Nets Katz.

We will start by describing two of the basic objects of Additive Combinatorics. If you are already familiar with additive combinatorics, you might like to skip this part. Given an additive group ${\mathcal G}$ and a finite subset $A\subset {\mathcal G}$, the sum set of $A$ is defined as

$A+A =\{a+b :\, a,b\in A\}.$

The additive energy of $A$ is defined as

$E(A) = |\{(a,b,c,d)\in A^4 :\, a+b=c+d\}|.$

Note that the size of the sum set $A+A$ is at least $|A|$ and at most $|A|^2$. A small sum set such as $|A+A|=O(|A|)$, implies that $A$ has “additive structure”. The meaning of this structure depends on the containing group ${\mathcal G}$. For example, Freiman’s theorem states that if $A\subset {\mathbb Z}$ then a small sum set implies that $A$ is contained in a generalized arithmetic progression of bounded size and dimension.

Next, notice that the additive energy of a finite set $A$ is larger than $|A|^2$ and at most $|A|^3$. A simple Cauchy-Schwarz argument shows that a small sum set $A+A$ implies a large additive energy $E(A)$. Similarly, one variant of the Balog-Szemerédi-Gowers theorem states that a large energy $E(A)$ implies the existence of a large subset $A'\subset A$ that has a small sum set. That is, there is a strong correlation between having a large energy and containing a large subset with additive structure.

One type of connection between the above definitions and discrete geometry occurs when $A$ is a set of points in a real space ${\mathbb R}^d$. In this case $(A+A)/2$ is the set of midpoints of pairs of points from $A$, so we may think of $|A+A|$ as the number of distinct midpoints that are determined by the points of $A$. Bourgain and Demeter studied the additive energy of some restricted point sets in ${\mathbb R}^d$, since these can be viewed as discrete Fourier restriction problems (for example, see this paper). Later, I extended their ideas to derive lower bounds for incidence problems with hypersurfaces in ${\mathbb R}^d$. The proof was based on double counting the additive energy of a point set $\cal P$ that is the intersection of the integer lattice ${\mathbb Z}^d$ with a specific truncated paraboloid. A lower bound for this energy can be derived by a Fourier argument, while an upper bound can be derived from point-hyperplane incidence bounds. That is, the additive energy was used to connect an incidence problem and a Fourier argument.

The works of Bourgain and Demeter contain a variety of open problems concerning additive energy of point sets. The following seems to be one of the main problems. I heard it in several talks by Ciprian, and it can also be found in this survey. Let ${\mathbb S}^d$ denote the hypersphere in ${\mathbb R}^{d+1}$ that is centered at the origin and has a radius of one.

Problem 1. Prove or disprove: For every $\varepsilon>0$ and every set $\cal P$ of $n$ points on ${\mathbb S}^2$, we have $E({\cal P})= O(n^{2+\varepsilon})$.

Problem 1 is interesting for several different reasons. From the perspective of Discrete Geometry and Additive Combinatorics, proving the claim in the problem would imply that a set of points on a sphere cannot have a lot of additive structure. The problem is also related to the open problem of point-circle incidences in ${\mathbb R}^2$. On the other hand, Problem 1 has applications to Fourier restriction problems (for example, see here), and is also related to number theory (see here).

The current best bound for Problem 1 is $E({\cal P})= O(n^{7/3})$. Moreover, it is known that the bound $E({\cal P})= O(n^{2+\varepsilon})$ holds when replacing ${\mathbb S}^2$ with the truncated paraboloid $\{(x,y,z)\in {\mathbb R}^3 :\, z= x^2+y^2, \ |x|,|y|\le 1/2 \}$ (for both of the above statements, see here). Bombieri and Bourgain reduced a variant of the problem to the unit distances problem. In this variant, the points are on a circle in the plane, and the definition of energy involves six-tuples rather than four-tuples.

We now move to the second open problem, which is related to the distinct distances problem. One of the main open problems related to distinct distances is the characterization of sets of $n$ points in ${\mathbb R}^2$ that span $O(n/\sqrt{\log n})$ distinct distances. I have already written several posts about about the state of this problem (for example, see here and here). In one sentence: Embarrassingly we hardly know anything about such point sets. In last year’s reunion of the IPAM polynomial method program, Nets Katz asked the following question. This question suggests one strategy for studying sets that span few distinct distances.

Problem 2.Prove or disprove: If is a set $\cal P$ of $n$ points in ${\mathbb R}^2$ spans $O(n/\sqrt{\log n})$ distinct distances, then $E({\cal P})$ is large.

In the Statement of Problem 2 I did not write what “large” means. A straightforward guess would be $\Theta(n^3)$, possibly up to factors that are sub-polynomial in $n$. Proving the assertion of the problem would provide a lot of information about the point set. For example, it would imply that there exists a large subset of the point set that determines few distinct midpoints. In a previous post we have seen a large family of sets that determine $O(n/\sqrt{\log n})$ distinct distances, and indeed all of these sets satisfy $E({\cal P})=\Theta(n^3)$.