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 , whose elements are called arrows, together with a partially defined composition operation

and a unary “inverse” operation:

which satisfy the following:

•  (associativity of arrow composition) if and   then and  and moreover  we have ,
•  (inverses and objects)   and   ; for any we define the origin of the arrow to be  and  the target of to be  ;  origins and targets of arrows form the set of objects of the groupoid ,
• (inverses again) if then   .

____________________

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 is , with composition and inverse . It is straightforward to notice that and , which is a way to say that the set of objects can be identified with and the origin of the arrow is and the target of is .
• any group is a groupoid,  with the arrow operation being the group multiplication and the inverse being the group inverse. Let be the neutral element of the group . Then for any “arrow$ we have , therefore this groupoid has only one object,  . The converse is true, namely groupoids with only one object are groups.
• take a group which acts at left on the set   , with the action   such that and . Then is a groupoid with operation and inverse .   We have , which can be identified with , and , which can be identified with . This groupoid has therefore 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 with :

Let be three subsets of a groupoid with the property that there exists an object such that for any arrow we have .  We can define the sets ,  and .

Let us define now the hard functions and with the property: for any we have

(1)    

(The name “hard functions” comes from the fact that 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   defined by

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

.

____________________

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

1. 
2. the function 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 from . The following figure is useful.

We have and and we want to recover and . We use (1) and property 1 of in order to recover . With comes . From and we recover , via the property 2 of the operation . 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.

Under the deformation of arrows given by     the operation becomes the red arrow

The operation acting on points (not arrows of the trivial groupoid) which appears in Proposition 2  is , 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 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 . 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 is trivial

and the “hard functions$ are trivial as well

and

The conclusion of the Corollary 1 is trivial as well, because (and so on …) therefore the conclusion is

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

Towards geometric Plünnecke graphs

This post is related to “Geometric Ruzsa triangle inequalities and metric spaces with dilations“. This time the effort goes into understanding the article  arXiv:1101.2532   Plünnecke’s Inequality by  Giorgis Petridis,   but this post is only a first step towards a geometric approach to Plünnecke’s inequality in spaces with dilations (it will be eventually applied for Carnot groups). Here I shall define a class of decorated binary trees and a notion of closeness.

I shall use binary decorated trees and the moves R1a and R2a, like in the post “A roadmap to computing with space“:

To these move I add the “linearity moves”

Definition 1.  These moves act on the set of binary trees with nodes decorated with two colours (black and white) and leaves decorated with elements of the infinite set of “variable names” .  I shall denote by … such trees and by … elements of .

The edges of the trees are oriented upward. By convention we admit to be a subset of , thinking about as an edge pointing upwards which is also a leaf decorated with .

The moves act locally, i.e. they can be used for any portion of a tree from which looks like one of the patterns from the moves, with the understanding that the rest of the respective tree is left unchanged.

____________________

Definition 2.  The class of finite trees  is the smallest subset of with the  properties:

• ,
• if then   , where is the tree

• if then , where is the tree

• if and we can pass from to by one of the moves then .

____________________

The class of finite trees is closed also with respect to other operations.

Proposition 1.  If   then

Let us denote by the tree from the LHS of the first row, by the tree from the middle of the first row and by the tree from the LHS of the second row.

Corollary 1.   If then , and .

Proof: If then . By Proposition 1  the trees and can be transformed into , therefore they belong to . Also, by the same proposition the tree can be transformed into , which we proved that it belongs to . Therefore .

____________________

I define now when two graphs are close.

Definition 3. Two graphs    are close, denoted by , if there is such that can be moved into .

Proposition 3.  The closeness relation is an equivalence.

Proof:  By the move R1a we have for any .  Take now , therefore there is such that can be moved into . We know that by Corollary 1. On the other hand we can prove that can be moved into , therefore .

Finally, let   , so there’s a such that can be moved into   , and let , so there’s such that can be moved into . Let now given by . Check that can be moved into , therefore .

 Question: do you think this  proof is more easy to understand than an equivalent proof given by drawings?

A roadmap to computing with space

I don’t know yet what exactly is “computing with space”, but I almost know. Further is a description of the road to this goal, along with an invitation to join.

Before starting this description, maybe is better to write what this explanation is NOT about.  I have arrived to the idea of “computing with space”  by branching from a beautiful geometry subject: sub-riemannian geometry. The main interest I have in this subject consists in giving an intrinsic (i.e. by using a minimal bag of tools) description of the differential structure of a sub-riemannian space. The fascinating part is that these spaces, although being  locally topologically trivial, have a differential calculus which is not amenable to the usual differential calculus on manifolds, in the same way as the hyperbolic space, say, is not a kind of euclidean space, geometrically. I consider very important and yet not well known  the discovery of the fact that there are spaces where we can define an intrinsic differential calculus fundamentally different than the usual one (locally, not globally, as it is the case with manifolds which admits different GLOBAL differential structures, although at the local level they are just pieces of an euclidean space). But in this post I shall NOT go to explain this. The road to computing with space branches from this one, however there are paths represented by mathematical hints which are criss-crossing  both these roads.

Let’s start.

1. In “Dilatation structures I. Fundamentals” I propose, in section 4 “Binary decorated trees and dilatations” a formalism for making easy various calculations with dilation structures (or “dilatation structures”, as I called them at the moment; notice that dilation vs dilatation is a battle won by dilations in math, but by dilatation in other fields, although the correct word historically is dilatations).

This formalism works with moves acting on binary decorated trees, with the leaves decorated with elements of a metric space. It was extremely puzzling that in fact the formalism worked without needing to know which metric space I use. It was also amazing to me that reasoning  with moves acting on binary trees gave proofs of generalizations of results  involving elaborate calculations with pseudo-differential operators and alike. At a close inspection it looked like somewhere in the background there is an abstract nonsense machine which is just applied to this particular case of metric spaces.

Here is an example of the formalism. The moves are (I use the names from graphic lambda calculus):

 

 

Define the following tree (and think about it as being the graphical representation of an operation):

Think that it represents , with respect to the base point .  Then we can prove that

which is a kind of associativity relation.  The proof by binary trees has nothing to do with sub-riemannian geometry, right? An indirect confirmation is that the same formalism works very well on the ultrametric space given by the boundary of the infinite dyadic tree, see  Self-similar dilatation structures and automata.

As a conclusion for this part, it seemed that  in order to unravel the abstract nonsense machine from the background, I needed to:

• find a way to get rid of  mentioning metric spaces, so in particular to get rid of decorations of the leaves of binary trees by points in in some space, (or maybe use these decorations as a kind of names)
• express this proof based on moves applied to binary trees as a computation, (i.e. as something like a reduction procedure).

Otherwise said, there was a need for a kind of logic, but which one?

Scale is a place in the brain

… and dilation structures might exist, physically, in some parts of the brain. (See also section 2.4.  in “Computing with space …”   arXiv:1103.6007 .)   I will surely come back to this subject, after learning more, but here are some facts.

The primary source of this post is the article “From A to Z: a potential role for grid cells in spatial navigation”   Neural Syst Circuits. 2012; 2: 6. by Caswell Barry and Daniel Bush.

From wikipedia entry for grid cell:

A grid cell is a type of neuron that has been found in the brains of rats, mice, bats, and monkeys; and it is likely to exist in other animals including humans.^{[1][2][3][4][5]} In a typical experimental study, an electrode capable of recording the activity of an individual neuron is implanted in the cerebral cortex of a rat, in a part called the dorsomedial entorhinal cortex, and recordings are made as the rat moves around freely in an open arena. For a grid cell, if a dot is placed at the location of the rat’s head every time the neuron emits an action potential, then as illustrated in the adjoining figure, these dots build up over time to form a set of small clusters, and the clusters form the vertices of a grid of equilateral triangles. This regular triangle-pattern is what distinguishes grid cells from other types of cells that show spatial firing correlates. By contrast, if a place cell from the rat hippocampus is examined in the same way (i.e., by placing a dot at the location of the rat’s head whenever the cell emits an action potential), then the dots build up to form small clusters, but frequently there is only one cluster (one “place field”) in a given environment, and even when multiple clusters are seen, there is no perceptible regularity in their arrangement.

So, there are place cells and grid cells. Here is what wikipedia says about place cells:

Place cells are neurons in the hippocampus that exhibit a high rate of firing whenever an animal is in a specific location in an environment corresponding to the cell’s “place field”. These neurons are distinct from other neurons with spatial firing properties, such as grid cells, border cells, barrier cells,^[1] conjunctive cells,^[2] head direction cells, and spatial view cells. In the CA1 and CA3 hippocampal subfields, place cells are believed to be pyramidal cells, while those in the dentate gyrus are believed to be granule cells.^[3]

The behaviour of these cells is explained in the Figure 1 from the mentioned article by Barry and Bush:

(Copyright ©2012 Barry and Bush; licensee BioMed Central Ltd.)

The explanation of the Figure 1 reads:

Single unit recordings made from the hippocampal formation. a) CA1 place cell recorded from a rat. The left-hand figure shows the raw data: the black line being the animal’s path as it foraged for rice in a 1m² arena for 20minutes; superimposed green dots indicating the animal’s location each time the place cell fired an action potential. Right, the same data processed to show firing rate (number of spike divided by dwell time) per spatial bin. Red indicates bins with high firing rate and blue indicates low firing rate, white bins are unvisited, and peak firing rate is shown above the map. b) Raw data and corresponding rate map for a single mEC grid cell showing the multiple firing fields arranged in a hexagonal lattice. c) Three co-recorded grid cells, the center of each firing field indicated by a cross with different colors corresponding to each cell. The firing pattern of each cell is effectively a translation of the other co-recorded cells as shown by superposition of the crosses (right). d) Changes made to the geometry of a familiar environment cause grid cell firing to be distorted (rescale) demonstrating that grid firing is, at least, partially controlled by environmental cues, in this case the location of the arena’s walls. Raw data are shown on the left and the corresponding rate maps on the right. The rat was familiar with the 1 m² arena (outlined in red). Changing the shape of the familiar arena by sliding the walls past each other produced a commensurate change in the scale of grid firing. For example, shortening the x-axis to 70cm from 100cm (top right) caused grid firing in the x-axis to reduce to 78% of its previous scale, while grid scale in the Y-axis was relatively unaffected. Numbers next to the rate maps indicate the proportional change in grid scale measured along that axis (figure adapted from reference [28]).

And now, the surprise: scale is indeed a place in the brain. Let’s see Figure 2. from the same article:

(Copyright ©2012 Barry and Bush; licensee BioMed Central Ltd.)

The caption of this figure is:

Grid scale increases along a dorso-ventral gradient in the mEC. Two grid cells recorded from the same animal but at different times are shown, both cells were recorded in a familiar 1m² arena. Approximate recording locations in the mEC are indicated. The more ventral cell exhibits a considerably larger size of firing fields and distance between firing fields than the dorsal cell.

… and, from the article,  (boldfaced by me):

The scale of the grid pattern, measured as the distance between neighboring peaks, increases along the dorso-ventral mEC gradient, mirroring a similar trend in hippocampal place fields [15,25]. The smallest, most dorsal, scale is typically 20 to 25cm in the rat, reaching in excess of several meters in the intermediate region of the gradient [15,26] (Figure ​(Figure2).2). This may explain how this remarkable pattern was missed by early electrophysiology studies, which targeted ventral mEC and found only broadly tuned spatial firing (for example, [27]). Interestingly, grid scale increases in discontinuous increments and the increment ratio, at least between the smaller scales, is constant [28]. Grid cells recorded from the same electrode, which are, therefore, proximate in the brain, typically have a common scale and orientation but a random offset relative to each other and the environment [15]. As such, their firing patterns are effectively identical translations of one another and a small number of cells will ‘tile’ the complete environment (Figure ​(Figure1c).1c). It also appears that grids of different scale recorded ipsilaterally have a common orientation, such that the hexagonal arrangement of their firing fields share the same three axes, albeit with some localized distortions [15,28,29].

That’s just amazing!

Concerning the hypothesis (Hafting, T.; Fyhn, M.; Molden, S.; Moser, M. -B.; Moser, E. I. (2005). “Microstructure of a spatial map in the entorhinal cortex”. Nature 436 (7052): 801–806. Bibcode:2005Natur.436..801H. doi:10.1038/nature03721.) that the grid cells firing fields encode the abstract structure of an euclidean space, I think this is not following from the observations. My argument is that the translation-invariance (of firing patterns in this particular case) emerge by the mechanism of dilation structures and it is, at least up to my actual understanding, an evidence for the existence of these structures in the brain. But of course, there is much to learn and think about.

Curvature and halfbrackets, part III

I continue from “Curvature and halfbrackets, part II“.  This post is dedicated to the application of the previously introduced notions to the case of a sub-riemannian Lie group.

_______________

1. I start with the definition of a sub-riemannian Lie group. If you look in the literature, the first reference to “sub-riemannian Lie groups” which I am aware about is the series Sub-riemannian geometry and Lie groups  arXiv:math/0210189, part II arXiv:math/0307342 , part III arXiv:math/0407099 .    However, that work predates the introduction of dilation structures, therefore there is a need to properly define this  object within the actual state of matters.

Definition 1. A sub-riemannian Lie group is a locally compact topological group with the following supplementary structure:

• together with the dilation structure coming from it’s one-parameter groups (by the Montgomery-Zippin construction), it has a group norm which induce a tempered dilation structure,
• it has a left-invariant dilation structure (with dilations and group norm denoted by ) which, paired with the tempered dilation structure mentioned previously, it satisfies the hypothesis of “Sub-riemannian geometry from intrinsic viewpoint” Theorem 12.9,  arXiv:1206.3093

Remarks:

1. there is no assumption on the tempered group norm to come from a Riemannian left-invariant distance on the group. For this reason, some people use the name sub-finsler  arXiv:1204.1613  instead of sub-riemannian, but I believe this is not a serious distinction, because the structure of a scalar product which induces the distance is simply not needed for understanding  sub-riemannian Lie groups.
2. by Theorem 12.9, it follows that the left-invariant field of dilations induces a length dilation structure. I shall use this further. Length dilation structures are maybe a more useful object than simply dilation structures, because they explain how the length functional behaves at different scales, which is a much more detailed information about the microscopic structure of a length metric space than just the information about how the distance behaves at different scales.

This definition looks a bit mysterious, unless you read the course notes cited inside the definition. Probably, when I shall find the interest to pursue it, it would be really useful to just apply, step by step, the constructions from arXiv:1206.3093 to sub-riemannian Lie groups.

__________________

2. With the notations from the last post, I want to compute the quantities . We already know that is related to the curvature of with respect to it’s sub-riemannian (sub-finsler if you like it more) distance, as introduced previously via metric profiles.  We also know that is controlled by and . But let’s see the expressions of these three quantities for sub-riemannian Lie groups.

I denote by the left invariant sub-riemannian distance, therefore we have .

Now, , where   by definition.  Notice also that , where  is the deformed group operation at scale , i.e. it is defined by the relation:

With all this, it follows that:

–

– .

A similar computation leads us to the expression for the curvature related quantity

.

Finally,

. This last quantity is controlled by a halfbracket, via a norm inequality.

The expressions of make transparent that the curvature-related is the sum of and . In the next post I shall use the length dilation structure of the sub-riemannian Lie group in order to show that is controlled by , which in turn is controlled by a norm of a halfbracket. Then I shall apply all this to , as an example.

Carry propagation-free number systems and a kind of approximate groups (I)

Avizienis introduced a signed-digit number representation which allows fast, carry propagation-free addition (A. Avizienis, Signed-digit number representation for fast parallel arithmetic, IRE Trans. Comput., vol. EC-10, pp. 389-400, 1961, see also B. Parhami, Carry-Free Addition of Recoded Binary Signed-Digit Numbers, IEEE Trans. Computers, Vol. 37, No. 11, pp. 1470-1476, November 1988.)

Here, just for fun, I shall use a kind of approximate groups to define a carry-free addition-like operation.

1. The hypothesis is: you have three finite sets , , , all sitting in a group . I shall suppose that the group is commutative, although it seems that’s not really needed further if one takes a bit of care. In order to reflect this, I shall use  for the group operation on , but I shall write   for the set of all elements of the form  with and .

We know the following about the three (non-empty, of course) sets :

1. ,
2. , , , , ,
3.    (where is the cardinal of the finite set ),
4.   (that’s what qualifies as a kind of an approximate group).

Let now choose a bijective function and two functions and such that

(1)   for any and any we have .

______________

2. Let be the family of functions defined on with values in , with compact support, i.e. if belongs to , then only a finite number of have the property that .  The element is defined by for any .  If with then is the smallest index with .

______________

3.  The structure introduced at 1. allows the definition of an operation on . The definition of the operation is inspired from a carry-free addition algorithm.

Definition 1. If both are equal to then . Otherwise, let be the smallest index such that one of or is different than .  The element is defined by the following algorithm:

1. for any ,
2. let ,  . Repeat:

______________

4.  We may choose the functions such that the operation is starting to become interesting. Before doing this, let’s remark that:

• the operation is commutative as a consequence of the fact that is commutative,
• the operation is conical, i.e. it admits the shift , as automorphism ( a property encountered before for dilation structures on ultrametric spaces, see  arXiv:0709.2224  )

Proposition 1.  If the functions satisfy the following:

1. 
2. for any
3. ,  for any , for any ,

then is a conical quasigroup.

Curvature and halfbrackets, part II

I continue from “Curvature and halfbrackets, part I“, with the same notations and background.

In a metric space with dilations , there are three quantities which will play a role further.

1. The first quantity is related to the “norm” function defined as

Notice that this is not a distance function, instead it is more like a norm of with respect to the basepoint , at scale . Together with the field of dilations, this “norm” function contains all the information about the local and infinitesimal behaviour of the distance . We can see this from the fact that we can recover the re-scaled distance from this “norm”, with the help of the approximate difference (for this notion see on this blog the definition of approximate difference in terms of emergent algebras here, or go to point 3. from the post The origin of emergent algebras (part III)):

(proof left to the interested reader) This identity shows that the uniform convergence of to , as goes to , is a consequence of the following pair of uniform convergences:

• that of the function which converges to
• that of  the pair (dilation, approximate difference)  to , see how this pair appears from the normed groupoid formalism, for example by reading the post from the post The origin of emergent algebras (part III).

With this definition of the “norm” function, I can now introduce the first quantity of interest, which measures the difference between the “norm” function at scale and the “norm” function at scale :

The interpretation of this quantity is easy in the particular case of a riemannian space with dilations defined by the geodesic exponentials. In this particular case

because the “norm” function equals the distance between (due to the definition of dilations with respect to the geodesic exponential).

In more general situations, for example in the case of a regular sub-riemannian space, we can’t define dilations in terms of geodesic exponentials (even if we may have at disposal geodesic exponentials). The reason has to do with the fact that the geodesic exponential in the case of a regular sub-riemannian manifold, is not intrinsically defined as a function from the tangent of the geodesic at it’s starting point. That is because geodesics in regular sub-riemannian manifolds (at least those which are classically, i.e. with respect to the differential manifold structure, smooth , are bound to have tangents only in the horizontal directions.

As another example, think about a sub-riemannian Lie group. Here, we may define a left-invariant dilation structure with the help of the Lie group exponential. In this case the quantity is certainly not equal to , excepting very particular cases, as a riemannian compact Lie group, with bi-invariant distance, where the geodesic and Lie group exponentials coincide.

_________________

2.   The second quantity is the one which is most interesting for defining (sectional like) curvature, let’s call it

.

_________________

3. Finally, the third quantity of interest is a kind of a measure of the convergence of to , but measured with the norms from the tangent spaces.  Now, a bit of notations:

for any three points ,

  for any three points   and

for any two points .

With these notations I introduce the third quantity:

.

_________________

The relation between these three quantities is the following:

Proposition.  .

_________________

Suppose that we know the following estimates:

higher order terms, with and ,

higher order terms, with and ,

higher order terms, with and ,

Lemma. Let  us sort in increasing order the list of the values and denote the sorted list by . Then .

The proof is easy. The equality from the Proposition tells us that the modules of , and can be taken as the edges of a triangle. Suppose then that , use the estimates from the hypothesis and divide by in one of the three triangle inequalities, then go with to in order to arrive at a contradiction .

_________________

The moral of the lemma is that there are at most two different coefficients in the list . The coefficient is called “curvdimension”. In the next post I shall explain why, in the case of a sub-riemannian Lie group,  the coefficient is related to the halfbracket. Moreover, we shall see that in the case of sub-riemannian Lie groups all three coefficient are equal, therefore the infinitesimal behaviour of the halfbracket determines the curvdimension.