Ruzsa triangle inequality

Remarks

The proof is an injection from $A \times (B - C)$ into $(A - B) \times (A - C)$. For each $d \in B - C$, fix one pair $(b_d, c_d)$ with $d = b_d - c_d$. Send $(a, d)$ to $(a - b_d, \ a - c_d)$. The difference of the two coordinates is $d$, which recovers $b_d$ and $c_d$, and then $a$. The name comes from the distance $d(A, B) = \log \big( \abs{A - B} / \sqrt{\abs{A}\abs{B}} \big)$ on nonempty finite sets. The inequality is exactly $d(B, C) \le d(B, A) + d(A, C)$. This $d$ is not a metric, since $d(A, A) > 0$ unless $A$ is a coset of a finite subgroup. For example, with $A = B = C = \set{0, 1}$ in $\Z$, the inequality reads $2 \cdot 3 \le 3 \cdot 3$.

Going deeper

For a student

The Ruzsa triangle inequality is one of the first tools of additive combinatorics. Together with the Plünnecke–Ruzsa inequality, it lets one pass between bounds on $A + A$, $A - A$ and longer sums. The same injection proves a version in nonabelian groups, with products and inverses in place of sums and differences.