In
additive combinatorics
Additive combinatorics is an area of combinatorics in mathematics. One major area of study in additive combinatorics are ''inverse problems'': given the size of the sumset ''A'' + ''B'' is small, what can we say about the structures of A ...
, 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),
and is so named for its resemblance to the
triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side.
This statement permits the inclusion of degenerate triangles, but ...
. It is an important lemma in the proof of the
Plünnecke-Ruzsa inequality.
Statement
If
and
are subsets of a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
, then the
sumset In additive combinatorics, the sumset (also called the Minkowski sum) of two subsets A and B of an abelian group G (written additively) is defined to be the set of all sums of an element from A with an element from B. That is,
:A + B = \.
The n-f ...
notation
is used to denote
. Similarly,
denotes
. Then, the Ruzsa triangle inequality states the following.
An alternate formulation involves the notion of the ''Ruzsa distance''.
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:
This formulation resembles the triangle inequality for a
metric space
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
; however, the Ruzsa distance does not define a metric space since
is not always zero.
Proof
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
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
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
{{reflist
Additive combinatorics