Jump to content

Ruzsa triangle inequality

From Wikipedia, the free encyclopedia

In additive combinatorics, the Ruzsa triangle inequality, also known as the Ruzsa difference triangle inequality to differentiate it from some of its variants, bounds the size of the difference of two sets in terms of the sizes of both their differences with a third set. It was proven by Imre Ruzsa (1996),[1] and is so named for its resemblance to the triangle inequality. It is an important lemma in the proof of the Plünnecke-Ruzsa inequality.

Statement

[edit]

If and are subsets of a group, then the sumset notation is used to denote . Similarly, denotes . Then, the Ruzsa triangle inequality states the following.

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

An alternate formulation involves the notion of the Ruzsa distance.[2]

Definition. If and are finite subsets of a group, then the Ruzsa distance between these two sets, denoted , is defined to be

Then, the Ruzsa triangle inequality has the following equivalent formulation:

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

This formulation resembles the triangle inequality for a metric space; however, the Ruzsa distance does not define a metric space since is not always zero.

Proof

[edit]

To prove the statement, it suffices to construct an injection from the set to the set . Define a function as follows. For each choose a and a such that . By the definition of , this can always be done. Let be the function that sends to . For every point in the set is , it must be the case that and . Hence, maps every point in to a distinct point in and is thus an injection. In particular, there must be at least as many points in as in . Therefore,

completing the proof.

Variants of the Ruzsa triangle inequality

[edit]

The Ruzsa sum triangle inequality is a corollary of the Plünnecke-Ruzsa inequality (which is in turn proved using the ordinary Ruzsa triangle inequality).

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

Proof. The proof uses the following lemma from the proof of the Plünnecke-Ruzsa inequality.

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

If is the empty set, then the left side of the inequality becomes , so the inequality is true. Otherwise, let be a subset of that minimizes . Let . The definition of implies that Because , applying the above lemma gives

Rearranging gives the Ruzsa sum triangle inequality.


By replacing and in the Ruzsa triangle inequality and the Ruzsa sum triangle inequality with and as needed, a more general result can be obtained: If , , and are finite subsets of an abelian group then

where all eight possible configurations of signs hold. These results are also sometimes known collectively as the Ruzsa triangle inequalities.

References

[edit]
  1. ^ Ruzsa, I. (1996). "Sums of finite sets". Number Theory: New York Seminar 1991-1995: 281–293. doi:10.1007/978-1-4612-2418-1_21. ISBN 978-0-387-94826-3.
  2. ^ Tao, T.; Vu, V. (2006). Additive Combinatorics. Cambridge: Cambridge University Press. ISBN 978-0-521-85386-6.