Ruzsa triangle inequality

If ${\displaystyle A}$ and ${\displaystyle B}$ are subsets of a group, then the sumset notation ${\displaystyle A+B}$ is used to denote ${\displaystyle \{a+b:a\in A,b\in B\}}$. Similarly, ${\displaystyle A-B}$ denotes ${\displaystyle \{a-b:a\in A,b\in B\}}$. Then, the Ruzsa triangle inequality states the following.

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

Definition. If ${\displaystyle A}$ and ${\displaystyle B}$ are finite subsets of a group, then the Ruzsa distance between these two sets, denoted ${\displaystyle d(A,B)}$, is defined to be

${\displaystyle d(A,B)=\log {\frac {|A-B|}{\sqrt {|A||B|}}}.}$

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

This formulation resembles the triangle inequality for a metric space; however, the Ruzsa distance does not define a metric space since ${\displaystyle d(A,A)}$ is not always zero.

To prove the statement, it suffices to construct an injection from the set ${\displaystyle A\times (B-C)}$ to the set ${\displaystyle (A-B)\times (A-C)}$. Define a function ${\displaystyle \phi }$ as follows. For each ${\displaystyle x\in B-C}$ choose a ${\displaystyle b(x)\in B}$ and a ${\displaystyle c(x)\in C}$ such that ${\displaystyle x=b(x)-c(x)}$. By the definition of ${\displaystyle B-C}$, this can always be done. Let ${\displaystyle \phi :A\times (B-C)\rightarrow (A-B)\times (A-C)}$ be the function that sends ${\displaystyle (a,x)}$ to ${\displaystyle (a-b(x),a-c(x))}$. For every point ${\displaystyle \phi (a,x)=(y,z)}$ in the set is ${\displaystyle (A-B)\times (A-C)}$, it must be the case that ${\displaystyle x=z-y}$ and ${\displaystyle a=y+b(x)}$. Hence, ${\displaystyle \phi }$ maps every point in ${\displaystyle A\times (B-C)}$ to a distinct point in ${\displaystyle (A-B)\times (A-C)}$ and is thus an injection. In particular, there must be at least as many points in ${\displaystyle (A-B)\times (A-C)}$ as in ${\displaystyle A\times (B-C)}$. Therefore,

${\displaystyle |A||B-C|=|A\times (B-C)|\leq |(A-B)\times (A-C)|=|A-B||A-C|,}$

completing the proof.

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).

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

Lemma. Let ${\displaystyle A}$ and ${\displaystyle B}$ be finite subsets of an abelian group ${\displaystyle G}$. If ${\displaystyle X\subseteq A}$ is a nonempty subset that minimizes the value of ${\displaystyle K'=|X+B|/|X|}$, then for all finite subsets ${\displaystyle C\subset G,}$

${\displaystyle |X+B+C|\leq K'|X+C|.}$

If ${\displaystyle A}$ is the empty set, then the left side of the inequality becomes ${\displaystyle 0}$, so the inequality is true. Otherwise, let ${\displaystyle X}$ be a subset of ${\displaystyle A}$ that minimizes ${\displaystyle K'=|X+B|/|X|}$. Let ${\displaystyle K=|A+B|/|A|}$. The definition of ${\displaystyle X}$ implies that ${\displaystyle K'\leq K.}$ Because ${\displaystyle X\subset A}$, applying the above lemma gives

${\displaystyle |B+C|\leq |X+B+C|\leq K'|X+C|\leq K'|A+C|\leq K|A+C|={\frac {|A+B||A+C|}{|A|}}.}$

Rearranging gives the Ruzsa sum triangle inequality.

By replacing ${\displaystyle B}$ and ${\displaystyle C}$ in the Ruzsa triangle inequality and the Ruzsa sum triangle inequality with ${\displaystyle -B}$ and ${\displaystyle -C}$ as needed, a more general result can be obtained: If ${\displaystyle A}$, ${\displaystyle B}$, and ${\displaystyle C}$ are finite subsets of an abelian group then

${\displaystyle |A||B\pm C|\leq |A\pm B||A\pm C|,}$

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