Geometric Ruzsa triangle inequalities and metric spaces with dilations

In arXiv:1212.5056 [math.CO]    “On growth in an abstract plane”  by  Nick Gill, H. A. Helfgott, Misha Rudnev ,  in lemma 4.1  is given a proof of the Ruzsa triangle inequality which intrigued me. Later on, at the end of the article the authors give a geometric Ruzsa inequality in a Desarguesian projective plane, based on similar ideas as the ones used in the proof of the Ruzsa triangle inequality.

All this made me write the following.


Let X be a non-empty set and \Delta: X \times X \rightarrow X be an operation on X which has the following two properties:

  1. for any a, b, c \in X we have \Delta(\Delta(a,b), \Delta(a,c)) = \Delta(b,c),
  2. for any a \in X   the function z \mapsto \Delta(z,a) is injective.

We may use weaker hypotheses for \Delta, namely:

  1. (weaker) there is a function F: X \times X \rightarrow X such that F(\Delta(a,b), \Delta(a,c)) = \Delta(b,c) for any a, b, c \in X,
  2. (weaker) there is a function G: X \times X \rightarrow X such that a \mapsto G(\Delta(a,b), b) is an injective function for any b \in X.

Prop. 1. Let X be a non empty set endowed with an operation \Delta which satisfies 1. and 2. (or the weaker version of those). Then for any non empty sets A, B, C \subset X there is an injection

i: \Delta(C,A) \times B \rightarrow \Delta(B,C) \times \Delta(B,A),

where we denote by \Delta(A,B) = \left\{ \Delta(a,b) \mid a \in A, b \in B \right\}

In particular, if A, B, C are finite sets, we have the Rusza triangle inequality

\mid \Delta(C,A) \mid \mid B \mid \leq \mid \Delta(B,C) \mid \mid \Delta(B,A) \mid,

where \mid A \mid denotes the cardinality of the finite set A.

I shall give the proof for hypotheses 1., 2., because the proof is the same for the weaker hypotheses. Also, this is basically the same proof as the one of the mentioned  lemma 4.1.  The proof of the Ruzsa inequality corresponds to the choice \Delta(a,b) = -a + b, where (X,+) is a group (no need to be abelian). The proof  of the geometric Ruzsa inequality corresponds to the choice \Delta(a,b) = [b,a], with the notations from the article, with the observation that this function \Delta satisfies weaker 1. and 2.

Proof.  We can choose functions f: \Delta(C,A) \rightarrow C and g: \Delta(C,A) \rightarrow A such that for any x \in \Delta(C,A) we have x = \Delta(f(x),g(x)). With the help of these functions let

i(x,b) = (\Delta(b,f(x)), \Delta(b, g(x))).

We want to prove that i is injective. Let (c,d) = i(x,b) = i(x',b'). Then, by 1. we have x = x' = \Delta(c,d).  This gives an unique e = f(x) = f(x'). Now we know that \Delta(b, e) = \Delta(b,f(x)) = c = \Delta(b', f(x')) = \Delta(b', e). By 2. we get that b = b'     qed.


In a metric space with dilations  (X, d, \delta)  we have the function  approximate difference \Delta^{e}_{\varepsilon} (a,b) based at e \in X and applied to a pair of closed points a, b \in X. This function has the property that (e,a,b) \mapsto \Delta^{e}_{\varepsilon}(a,b) converges uniformly to \Delta^{e}(a,b) as \varepsilon goes to 0. Moreover, there is a local group operation with e as neutral element such that \Delta^{e}(a,b) = -a+b, therefore the function \Delta^{e} satisfies 1. and 2.

As concerns the function \Delta^{e}_{\varepsilon}, it satisfies the following approximate version of 1.:

  1. (approximate) for any e, a, b, c \in X which are sufficiently close and for any \varepsilon \in (0,1) we have, with the notation a(\varepsilon) = \delta^{e}_{\varepsilon} a,  the relation

\Delta^{a(\varepsilon)}_{\varepsilon}(\Delta^{e}_{\varepsilon}(a,b), \Delta^{e}_{\varepsilon}(a,c)) = \Delta^{e}_{\varepsilon}(b,c).

We say that a set A \subset X is \varepsilon separated if for any x, y \in A,  the inequality  d(x,y) < \varepsilon  implies  x = y.  Further I am going to write about sets which are closed to a fixed, but arbitrary otherwise point e \in X.

Prop2.  In a metric space with dilations, let p >0 and  let A, B, C be finite sets of points included in a compact neighbourhood of e, which are closed to e \in X, such that for any  \varepsilon \in (0,p)  the sets B and \Delta^{e}_{\varepsilon}(C,A) are \mu separated. Then for any \varepsilon \leq C(\mu) there is an injective function

i: \Delta^{e}_{\varepsilon}(C,A) \times B \rightarrow \Delta^{e}_{\varepsilon}(B,C) \times \Delta^{e}_{\varepsilon}(B,A).

Proof. As previously, we choose the functions f and g. Notice that these functions depend on \varepsilon but this will not matter further.  I shall use the O(\varepsilon) notation liberally, for example y = x + O(\varepsilon) means d(x,y) \leq O(\varepsilon).  Let’s define the function i by the same formula as previously:

i(x,b) = (\Delta^{e}_{\varepsilon}(b,f(x)), \Delta^{e}_{\varepsilon}(b, g(x))).

Let (x,b) and (x',b') be pairs such that i(x,b) = i(x',b') = (c_{\varepsilon}, d_{\varepsilon}). From 1. (approximate) and from the uniform convergence mentioned previously we get that

x = x' + O(\varepsilon) = \Delta^{e}(c_{\varepsilon}, d_{\varepsilon}) + O(\varepsilon).

There is a function C(\mu)  such that \varepsilon \leq C(\mu) implies (the last from the previous relation) O (\varepsilon) < \mu.  For such a \varepsilon, by the separation  of \Delta^{e}_{\varepsilon}(C,A) we get x = x'.

Let z = f(x). From the hypothesis we have \Delta^{e}_{\varepsilon}(b, z) = \Delta^{e}_{\varepsilon}(b',z). This implies, via the structure of the function \Delta^{e} and via the uniform convergence, that b' = b + O(\varepsilon)  (by compactness, this last O(\varepsilon) does not depend on A, B, C). By the same reasoning as previously, we may choose C(\mu) such that d(b,b') < \mu if \varepsilon \leq C(\mu). This implies b = b'   qed.


3 thoughts on “Geometric Ruzsa triangle inequalities and metric spaces with dilations”

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s