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.
are subsets of a group, then the sumset notation
Then, the Ruzsa triangle inequality states the following.
Theorem (Ruzsa triangle inequality) — If
are finite subsets of a group, then An alternate formulation involves the notion of the Ruzsa distance.
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
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
To prove the statement, it suffices to construct an injection from the set
{\displaystyle (A-B)\times (A-C)}
{\displaystyle \phi :A\times (B-C)\rightarrow (A-B)\times (A-C)}
{\displaystyle (a-b(x),a-c(x))}
{\displaystyle (A-B)\times (A-C)}
maps every point in
{\displaystyle (A-B)\times (A-C)}
{\displaystyle (A-B)\times (A-C)}
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
are finite subsets of an abelian group, then Proof.
The proof uses the following lemma from the proof of the Plünnecke-Ruzsa inequality.
be finite subsets of an abelian group
is a nonempty subset that minimizes the value of
is the empty set, then the left side of the inequality becomes
, applying the above lemma gives Rearranging gives the Ruzsa sum triangle inequality.
in the Ruzsa triangle inequality and the Ruzsa sum triangle inequality with
as needed, a more general result can be obtained: If
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.