Dávid Matolcsi, Imre Ruzsa, Dmitrii 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 . For instance, if and is a positive integer, we have
If is not an arithmetic progression, it is known that
and so we obtain
whenever is a compact subset of . 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 , which will not obtain the growth in (1). For a legitimate dimensional set, one can take an arithmetic progression alongside random points and will grow only linearly in . There are some situations when we can establish (1). For instance, if contains , then Green and Tao showed
Freiman (see chapter 5 of Tao and Vu) also showed if such that every hyperplane intersects in points, then
We also mention the work of Gardner and Gronchi, who prove inequalities for general -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 dimensional set is a quasi-cube if where , where , with a hyperplane and are themselves quasi-cubes. A cube is a quasi-cube. Also, the trapezoid:
is a quasi-cube.
Theorem 1: Let be finite. Suppose that contains which a subset of a quasi-cube. Then
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 , we have
and for are compact, we have
Both can be proved in the same way: by finding a translate of and a translate of in that are almost disjoint. In the continuous setting (3) is used to establish a functional analog. For compactly support and bounded we define
Then the Prékopa-Leindler inequality implies that
When and , we obtain a weaker variant of (3):
To go in the other direction, one applies (3) to the level sets of and . 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 be compactly supported. Then Prékopa showed that
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 with fixed. Doing this, one obtains, for compactly support and bounded
A slight generalization of this inequality quickly implies the Brunn-Minkowski inequality. In the discrete setting, the present in both (2) and (5) are quite a nuisance, particularly in the tensorization step. To get around this, we observe that
of size 2. It turns out one has
as was originally observed by Prékopa himself. One has an easier time tensorizing this, and following this one can obtain
In our work, we take an abstract approach, defining
Note that . Indeed, is intended to be a replacement of the usual notion of the doubling constant, . It turns out for certain large dimensional sets, we can accurately estimate . For instance, we show that if is a subset of a quasi-cube then
which quickly implies Theorem 1. The upper bound follows immediately from the definition of , 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 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
where . The cases were already known but for other values of 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).