Tag Archives: Ruzsa inequality

Geometric Ruzsa inequality on groupoids and deformations

This is a continuation of  Geometric Ruzsa triangle inequalities and metric spaces with dilations .  Proposition 1 from that post may be applied to groupoids. Let’s see what we get.

Definition 1. A groupoid is a set G, whose elements are called arrows, together with a partially defined composition operation

(g,h) \in G^{(2)} \subset G \times G \mapsto gh \in G

and a unary “inverse” operation:

g \in G \mapsto g^{-1} \in G

which satisfy the following:

  •  (associativity of arrow composition) if (a,b) \in G^{(2)} and (b,c) \in G^{(2)}  then (a, bc) \in G^{(2)} and  (ab, c) \in G^{(2)} and moreover  we have a(bc) = (ab)c,
  •  (inverses and objects)   (a,a^{-1}) \in G^{(2)} and (a^{-1}, a) \in G^{(2)}  ; for any a \in G we define the origin of the arrow a to be  \alpha(a) = a^{-1} a and  the target of a to be  \omega(a) = a a^{-1};  origins and targets of arrows form the set of objects of the groupoid Ob(G),
  • (inverses again) if (a,b) \in G^{(2)} then a b b^{-1} = a  a^{-1} a b = b.

____________________

The definition is a bit unnecessary restrictive in the sense that I take groupoids to have sets of arrows and sets of objects. Of course there exist larger groupoids, but for the purpose of this post we don’t need them.

The most familiar examples of groupoids are:

  • the trivial groupoid associated to a non-empty set X is G = X \times X, with composition (x,y) (y,z) = (x,z) and inverse (x,y)^{-1} = (y,x). It is straightforward to notice that \alpha(x,y) = (y,y) and \omega(x,y) = (x,x), which is a way to say that the set of objects can be identified with X and the origin of the arrow (x,y) is y and the target of (x,y) is x.
  • any group G is a groupoid,  with the arrow operation being the group multiplication and the inverse being the group inverse. Let e be the neutral element of the group G. Then for any “arrow$ g \in G we have \alpha(g) = \omega(g) = e, therefore this groupoid has only one object,  e. The converse is true, namely groupoids with only one object are groups.
  • take a group G which acts at left on the set X  , with the action (g,x) \in G \times X \mapsto gx \in X   such that g(hx) = (gh)x and ex = x. Then G \times X is a groupoid with operation (h, gx) (g,x) = (hg, x) and inverse (g,x)^{-1} = (g^{-1}, gx).   We have \alpha(g,x) = (e,x), which can be identified with x \in X, and \omega(g,x) = (e,gx), which can be identified with gx \in X. This groupoid has therefore X as the set of objects.

For the relations between groupoids and dilation structures see arXiv:1107.2823  . The case of the trivial groupoid, which will be relevant soon, has been discussed in the post  The origin of emergent algebras (part III).

____________________

The following operation is well defined for any pair of arrows (g,h) \in G with \alpha(g) = \alpha(h) :

\Delta(g,h) = h g^{-1}

Let A, B, C \subset G be three subsets of a groupoid G with the property that there exists an object e \in Ob(G) such that for any arrow g \in A \cup B \cup C we have \alpha(g) = e.  We can define the sets \Delta(C,A)\Delta(B,C) and \Delta(B,A) .

Let us define now the hard functions f: \Delta(C,A) \rightarrow C and g: \Delta(C,A) \rightarrow A with the property: for any z \in \Delta(C,A) we have

(1)     \Delta(f(z), g(z)) = z

(The name “hard functions” comes from the fact that \Delta should be seen as an easy operation, while the decomposition (1) of an arrow into a “product” of another two arrows should be seen as hard.)

The following is a corollary of Proposition 1 from the post  Geometric Ruzsa triangle inequalities and metric spaces with dilations:

Corollary 1.  The function i: \Delta(C,A) \times B \rightarrow \Delta(B,C) \times \Delta(B,A)  defined by

i(z,b) = (f(z) b^{-1} , g(z) b^{-1})

is injective. In particular, if the sets A, B, C are finite then

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

____________________

Proof.   With the hypothesis that all arrows from the three sets have the same origin, we notice that \Delta satisfies the conditions 1, 2 from Proposition 1, that is

  1. \Delta( \Delta(b,c), \Delta(b,a)) = \Delta(c,a)
  2. the function b \mapsto \Delta(b,a) is injective.

As a consequence, the proof of Proposition 1 may be applied verbatim. For the convenience of the readers, I rewrite the proof as a recipe about how to recover (z, b) from i(z,b). The following figure is useful.

bellaiche_5

We have f(z) b^{-1} and g(z) b^{-1} and we want to recover z and b. We use (1) and property 1 of \Delta in order to recover z. With z comes f(z). From f(z) and f(z) b^{-1} we recover b, via the property 2 of the operation \Delta. That’s it.

____________________

There are now some interesting things to mention.

Fact 1.  The proof of Proposition 2 from the Geometric Ruzsa post is related to this. Indeed, in order to properly understand what is happening, please read again   The origin of emergent algebras (part III)  . There you’ll see that a metric space with dilations can be seen as a family of defirmations of  the trivial groupoid. In the following I took one of the figures from the “origin III” post and modified it a bit.

bellaiche_4

Under the deformation of arrows given by  \delta_{\varepsilon}(y,x) = (\delta^{x}_{\varepsilon} y , x)    the operation \Delta((z,e)(y,e)) becomes the red arrow

(\Delta^{e}_{\varepsilon}(z,y), \delta^{e}_{\varepsilon} z)

The operation acting on points (not arrows of the trivial groupoid) which appears in Proposition 2  is \Delta^{e}_{\varepsilon}(z,y), but Proposition 2 does not come straightforward from Corollary 1 from this post. That is because in Proposition 2 we use only targets of arrows, so the information at our disposal is less than the one from Corrolary 1. This is supplemented by the separation hypothesis of Proposition 2. This works like this. If we deform the operation \Delta on the trivial groupoid by using dilations, then we mess the first image of this post, because the deformation keeps the origins of arrows but it does not keep the targets. So we could apply the Corollary 1 proof directly to the deformed groupoid, but the information available to us consists only in targets of the relevant arrow and not the origins. That is why we use the separation hypotheses in order to “move” all unknown arrow to others which have the same target, but origin now in e. The proof then proceeds as previously.

In this way, we obtain a statement about  algebraic operations (like additions, see Fact 2.) from the trivial groupoid operation. 

Fact 2.  It is not mentioned in the “geometric Ruzsa” post, but the geometric Ruzsa inequality contains the classical inequality, as well as it’s extension to Carnot groups. Indeed, it is enough to apply it for particular dilation structures, like the one of a real vectorspace, or the one of a Carnot group.

Fact 3.  Let’s see what Corollary 1 says in the particular case of a trivial groupoid. In this case the operation \Delta is trivial

\Delta((a,e), (c,e)) = (a,c)

and the “hard functions$ are trivial as well

f(a,c) = (c,e) and g(a,c) =(a,e)

The conclusion of the Corollary 1 is trivial as well, because \mid \Delta(C,A) \mid = \mid C \mid \mid A \mid (and so on …) therefore the conclusion is

\mid C \mid \mid A \mid \mid B \mid \leq \mid B \mid^{2} \mid A \mid \mid C \mid

However, by the magic of deformations provided by dilations structures, from this uninteresting “trivial groupoid Ruzsa inequality” we get the more interesting original one!

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.