An Analytic Approach to the Cardinality of Sumsets

Dávid Matolcsi, Imre RuzsaDmitrii Zhelezov and I just uploaded our paper, “An analytic approach to cardinalities of sumsets” to the arXiv. Alongside Ben Green, we also uploaded a follow up paper, “A weighted Prékopa-Leindler inequality and sumsets with quasi-cubes.”

Our focus is sumsets of finite subsets of {\mathbb{Z}^d}. For instance, if {A \subset \mathbb{Z}} and {d} is a positive integer, we have 

\displaystyle |A^d + A^d| =|A+A|^d.

If {A} is not an arithmetic progression, it is known that 

\displaystyle |A+A| \geq 2|A|,

and so we obtain 

\displaystyle |A^d + A^d| \geq 2^d |A|.\ \ \ \ \ (1)

It is natural to look to obtain analogs of (1) for more general subsets of {\mathbb{Z}^d}. For instance, the Brunn-Minkowski inequality implies the continuous analog, 

\displaystyle \mu(X+X) \geq 2^d \mu(X),

whenever {X} is a compact subset of {\mathbb{R}^d}. In the discrete setting such a result is not true. First of all, the notion of cardinality does not distinguish dimension. Thus we can take a one dimensional arithmetic progression and place in {\mathbb{Z}^d}, which will not obtain the growth in (1). For a legitimate {d} dimensional set, one can take an arithmetic progression alongside {d-1} random points and {|A+A| / |A|} will grow only linearly in {d}. There are some situations when we can establish (1). For instance, if {A} contains {\{0,1\}^d}, then Green and Tao showed

\displaystyle |A+A| \geq 2^{d/2} |A|.

Freiman (see chapter 5 of Tao and Vu) also showed if {A \subset \mathbb{Z}^d} such that every hyperplane intersects {A} in {\ll_{d, \epsilon} |A|} points, then 

\displaystyle |A+A| \geq (2^d - \epsilon) |A|.

We also mention the work of Gardner and Gronchi, who prove inequalities for general {d}-dimensional sets. The drawback there is that the extremal examples are nearly one dimensional, and particular they only derive growth that is linear in the dimension. We provide a result in a similar spirt to Green and Tao. To state our result, we need a definition. We define a quasi-cube inductively (on the dimension). Any two point set is a 1-dimensional quasi-cube. A {d} dimensional set {U} is a quasi-cube if {U = U_0 \cup U_1} where {U_0 ,U_1}, where {U_j = (x_j + L_j) \cap U}, with {x_j \in \mathbb{Z}^d}, {L_j} a hyperplane and {U_0,U_1} are themselves quasi-cubes. A cube is a quasi-cube. Also, the trapezoid: 

\displaystyle U = \{(0,0) , (1,0), (0,1) , (1,x)\} , \ \ \ \text{with} \ \ x \neq 0,

is a quasi-cube.

{\ } Theorem 1: Let {A \subset \mathbb{Z}^d} be finite. Suppose that A contains U which a subset of a quasi-cube. Then 

\displaystyle |A+A| \geq |U|^{1/2} |A|, \ \ \ \spadesuit.{\ }

This has applications to the sum-product problem via the Bourgain-Chang argument and will be explored in a future paper of Pálvölgyi and Zhelezov. We discuss some of the ideas. As mentioned above, Theorem 1 can be thought of as a discrete analog of the Brunn-Minkowski inequality. The Brunn-Minksowski inequality can be proved using the Prékopa-Leindler inequality, and this is the viewpoint we adopt. 

To start, for {A,B \subset \mathbb{Z}}, we have 

\displaystyle |A+B| \geq |A| + |B| - 1,\ \ \ \ \ (2)

and for {X,Y \subset \mathbb{R}^d} are compact, we have 

\displaystyle \mu(X+Y) \geq \mu(X) + \mu(Y).\ \ \ \ \ (3)

Both can be proved in the same way: by finding a translate of {X} and a translate of {Y} in {X+Y} that are almost disjoint. In the continuous setting (3) is used to establish a functional analog. For compactly support and bounded {f,g:\mathbb{R} \rightarrow \mathbb{R}_{\geq 0}} we define

\displaystyle f \mathbin{\overline *} g(z) : = \sup_{x+y =z} f(x) g(y).

Then the Prékopa-Leindler inequality implies that

\displaystyle \int f \mathbin{\overline *} g \geq ||f||_2 ||g||_2.\ \ \ \ \ (4)

When {f=1_X} and {g=1_Y}, we obtain a weaker variant of (3):

\displaystyle \mu(X+Y) \geq 2 \mu(X)^{1/2} \mu(Y)^{1/2}.

To go in the other direction, one applies (3) to the level sets of {f} and {g}Gardner’s survey provides more accurate implications along these lines. Thus it is natural to ask for a functional analog of (2). Indeed, we let {a,b: \mathbb{Z} \rightarrow \mathbb{R}_{\geq 0}} be compactly supported. Then Prékopa showed that

\displaystyle ||a \mathbin{\overline *} b|| \geq 2 ||a||_2 ||b||_2 - 1.\ \ \ \ \ (5)

We invite the reader to try to discover a proof, it is rather non-trivial! In any case, the next step in Prékopa-Leindler is to tensorize, as is explained in this blog post of Tao or section 4 of the aforementioned survey of Gardner. The point is the integral inequality (4) can be obtained by induction on the dimension by applying the lower dimensional analog of (4) to functions such as {f(x_1 , \ldots , x_{d-1} , x_d)} with {x_d} fixed. Doing this, one obtains, for compactly support and bounded {f,g:\mathbb{R} \rightarrow \mathbb{R}_{\geq 0}} 

\displaystyle \int f \mathbin{\overline *} g \geq ||f||_2 ||g||_2.

A slight generalization of this inequality quickly implies the Brunn-Minkowski inequality. In the discrete setting, the {-1} present in both (2) and (5) are quite a nuisance, particularly in the tensorization step. To get around this, we observe that 

\displaystyle |A+B+U| \geq |A|+|B| \geq 2 |A|^{1/2} |B|^{1/2},

{U \subset \mathbb{Z}} of size 2. It turns out one has 

\displaystyle ||a \mathbin{\overline *} b \mathbin{\overline *} 1_U|| \geq 2 ||a||_2 ||b||_2 ,

as was originally observed by Prékopa himself. One has an easier time tensorizing this, and following this one can obtain 

\displaystyle |A+B+\{0,1\}^d| \geq |A|^{1/2} |B|^{1/2}.

In our work, we take an abstract approach, defining

\displaystyle \beta(U) = \inf_{A,B \neq \emptyset} \frac{|A+B+U|}{|A|^{1/2} |B|^{1/2}}.

Note that {\beta(U) \leq |U+U+U|/|U|}. Indeed, {\beta} is intended to be a replacement of the usual notion of the doubling constant, {|U+U|/|U|}. It turns out for certain large dimensional sets, we can accurately estimate {\beta}. For instance, we show that if {U} is a subset of a quasi-cube then

\displaystyle \beta(U) = |U|,

which quickly implies Theorem 1. The upper bound follows immediately from the definition of {\beta}, it is the lower bound that takes some work. To do this, we show that this is the same as a functional analog and that tensorization occurs in general. We also explore general properties (for instance {\beta} is independent of the ambient group) and present a bunch of conjectures (which may be interpreted as things we were unable to prove or disprove). 

The above outline nearly works for subsets of quasi-cubes, though it turns out one needs a stronger 1 dimensional inequality of the form

\displaystyle ||f \mathbin{\overline *} g \mathbin{\overline *} h_{\delta}||_1 \geq (1+\delta) ||f||_2 ||g||_2,

where {h = (1,\delta)}. The cases {\delta = 0,1} were already known but for other values of {\delta} it is tricker. There are now two proofs: in the original paper we use a variational argument while in the follow up paper we derive it from the Prékopa-Leindler inequality.

This is a sort of “tensorization plus two point inequality argument,” which is present in other works (i.e. Beckner’s inequality).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s