Recall Plünnecke’s inequality which states the following. We write for all of the –fold sums of .
Theorem (Plun): Let be a finite subset of an abelian group. Let be the doubling constant. Then
We describe one natural attempt to prove Theorem (Plun). Suppose that
for some small . Then
This motivates the following definition.
Definition (Cov): Let be a finite subset of an abelian group. We let
Clearly , since we may choose . Note that
and so this would have implications to Plünnecke’s inequality.
The truth is one cannot reverse (2). We give an example due to Ruzsa.
Example: We construct a set in via
We have the following properties of :
Note that comes from the sum of a line of size with the box, while comes from the sum of two perpendicular lines of size . The point is that one cannot efficiently cover a two dimensional object with either a one dimensional object or a three dimensional object, even in the presence of additive structure.
We do have statistically in the following sense.
Proposition (Stat): Let
This should be compared to this post of Tao, where he talks about an entropy version of Plünnecke’s inequality.
Proof: We choose uniformly at random of size . Let . Then for ,
We choose . If , the Proposition follows from taking and so we assume the opposite. Let be the random variable that denotes the number of not covered by . By the union bound,
Thus there is a choice of so that and thus
On the other hand, we can bound in terms of the doubling constant if we are allowed to take a subset of the smoother .
Proposition (Smooth): Let be a finite subset of an abelian group. Then where and . Thus can be covered by translates of .
The proof of Proposition (Smooth) is similar to that of Proposition (Stat), so we omit it.
This is related to the following annoying question. We let be the dilate of by . We know from Plünnecke’s inequality that
This inequality came up in Lemma 5.1 of the almost periodicity paper of Croot and Sisask.
Question (aplus2a): Does there exist a such that
This was asked in a paper of Bukh and appears on his website. Note that both of the inequalities in (3) can be basically tight. For the first one, consider and arithmetic progression, and for the second, the example given above.
We now give a construction that shows one cannot take too small in Question (aplus2a), even for large , using the tensor power trick.
Example: Consider . Then and . This example shows that one cannot take smaller than
To make large examples, consider for some large .