Plünnecke–Ruzsa inequality

(Redirected from Plünnecke-Ruzsa inequality)

In additive combinatorics, the Plünnecke–Ruzsa inequality is an inequality that bounds the size of various sumsets of a set , given that there is another set so that is not much larger than . A slightly weaker version of this inequality was originally proven and published by Helmut Plünnecke (1970).[1] Imre Ruzsa (1989)[2] later published a simpler proof of the current, more general, version of the inequality. The inequality forms a crucial step in the proof of Freiman's theorem.

Statement

edit

The following sumset notation is standard in additive combinatorics. For subsets   and   of an abelian group and a natural number  , the following are defined:

  •  
  •  
  •  

The set   is known as the sumset of   and  .

Plünnecke-Ruzsa inequality

edit

The most commonly cited version of the statement of the Plünnecke–Ruzsa inequality is the following.[3]

Theorem (Plünnecke-Ruzsa inequality) — If   and   are finite subsets of an abelian group and   is a constant so that  , then for all nonnegative integers   and  ,

 

This is often used when  , in which case the constant   is known as the doubling constant of  . In this case, the Plünnecke–Ruzsa inequality states that sumsets formed from a set with small doubling constant must also be small.

Plünnecke's inequality

edit

The version of this inequality that was originally proven by Plünnecke (1970)[1] is slightly weaker.

Theorem (Plünnecke's inequality) — Suppose   and   are finite subsets of an abelian group and   is a constant so that  . Then for all nonnegative integer  ,  

Proof

edit

Ruzsa triangle inequality

edit

The Ruzsa triangle inequality is an important tool which is used to generalize Plünnecke's inequality to the Plünnecke–Ruzsa inequality. Its statement is:

Theorem (Ruzsa triangle inequality) — If  ,  , and   are finite subsets of a group, then

 


Proof of Plünnecke-Ruzsa inequality

edit

The following simple proof of the Plünnecke–Ruzsa inequality is due to Petridis (2014).[4]

Lemma: Let   and   be finite subsets of an abelian group  . If   is a nonempty subset that minimizes the value of  , then for all finite subsets  ,

 

Proof: This is demonstrated by induction on the size of  . For the base case of  , note that   is simply a translation of   for any  , so

 

For the inductive step, assume the inequality holds for all   with   for some positive integer  . Let   be a subset of   with  , and let   for some  . (In particular, the inequality holds for  .) Finally, let  . The definition of   implies that  . Thus, by the definition of these sets,

 

Hence, considering the sizes of the sets,

 

The definition of   implies that  , so by the definition of  ,  . Thus, applying the inductive hypothesis on   and using the definition of  ,

 

To bound the right side of this inequality, let  . Suppose   and  , then there exists   such that  . Thus, by definition,  , so  . Hence, the sets   and   are disjoint. The definitions of   and   thus imply that

 

Again by definition,  , so  . Hence,

 

Putting the above two inequalities together gives

 

This completes the proof of the lemma.

To prove the Plünnecke–Ruzsa inequality, take   and   as in the statement of the lemma. It is first necessary to show that

 

This can be proved by induction. For the base case, the definitions of   and   imply that  . Thus, the definition of   implies that  . For inductive step, suppose this is true for  . Applying the lemma with   and the inductive hypothesis gives

 

This completes the induction. Finally, the Ruzsa triangle inequality gives

 

Because  , it must be the case that  . Therefore,

 

This completes the proof of the Plünnecke–Ruzsa inequality.

Plünnecke graphs

edit

Both Plünnecke's proof of Plünnecke's inequality and Ruzsa's original proof of the Plünnecke–Ruzsa inequality use the method of Plünnecke graphs. Plünnecke graphs are a way to capture the additive structure of the sets   in a graph theoretic manner[5][6]

To define a Plünnecke graph we first define commutative graphs and layered graphs:

Definition. A directed graph   is called semicommutative if, whenever there exist distinct   such that   and   are edges in   for each  , then there also exist distinct   so that   and   are edges in   for each  .

  is called commutative if it is semicommutative and the graph formed by reversing all its edges is also semicommutative.

Definition. A layered graph is a (directed) graph   whose vertex set can be partitioned   so that all edges in   are from   to  , for some  .

Definition. A Plünnecke graph is a layered graph which is commutative.

The canonical example of a Plünnecke graph is the following, which shows how the structure of the sets   form a Plünnecke graph.

Example. Let   be subsets of an abelian group. Then, let   be the layered graph so that each layer   is a copy of  , so that  ,  , ...,  . Create the edge   (where   and  ) whenever there exists   such that  . (In particular, if  , then   by definition, so every vertex has outdegree equal to the size of  .) Then   is a Plünnecke graph. For example, to check that   is semicommutative, if   and   are edges in   for each  , then  . Then, let  , so that   and  . Thus,   is semicommutative. It can be similarly checked that the graph formed by reversing all edges of   is also semicommutative, so   is a Plünnecke graph.

In a Plünnecke graph, the image of a set   in  , written  , is defined to be the set of vertices in   which can be reached by a path starting from some vertex in  . In particular, in the aforementioned example,   is just  .

The magnification ratio between   and  , denoted  , is then defined as the minimum factor by which the image of a set must exceed the size of the original set. Formally,

 

Plünnecke's theorem is the following statement about Plünnecke graphs.

Theorem (Plünnecke's theorem) — Let   be a Plünnecke graph. Then,   is decreasing in  .

The proof of Plünnecke's theorem involves a technique known as the "tensor product trick", in addition to an application of Menger's theorem.[5]

The Plünnecke–Ruzsa inequality is a fairly direct consequence of Plünnecke's theorem and the Ruzsa triangle inequality. Applying Plünnecke's theorem to the graph given in the example, at   and  , yields that if  , then there exists   so that  . Applying this result once again with   instead of  , there exists   so that  . Then, by Ruzsa's triangle inequality (on  ),

 

thus proving the Plünnecke–Ruzsa inequality.


See also

edit

References

edit
  1. ^ a b Plünnecke, Helmut (1970). "Eine zahlentheoretische Anwendung der Graphtheorie". Journal für die reine und angewandte Mathematik. 243: 171–183. doi:10.1515/crll.1970.243.171.
  2. ^ Ruzsa, Imre (1989). "An application of graph theory to additive number theory". Scientia, Series A. 3: 97–109.
  3. ^ Candela, Pablo; González-Sánchez, Diego; de Roton, Anne (2019). "A Plünnecke-Ruzsa inequality in compact abelian groups". Revista Matemática Iberoamericana. 35 (7): 2169–2186. arXiv:1712.07615. doi:10.4171/rmi/1116.
  4. ^ Petridis, Giorgis (2014). "The Plünnecke–Ruzsa Inequality: An Overview". Combinatorial and Additive Number Theory. Springer Proceedings in Mathematics & Statistics. Vol. 101. pp. 229–241. doi:10.1007/978-1-4939-1601-6_16. ISBN 978-1-4939-1600-9.
  5. ^ a b Tao, T.; Vu, V. (2006). Additive Combinatorics. Cambridge: Cambridge University Press. ISBN 978-0-521-85386-6.
  6. ^ Ruzsa, I., Sumsets and structure (PDF).