# 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. 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. 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!

# The origin of emergent algebras (part II)

I continue from the post “The origin of emergent algebras“, which revolves around the last sections of Bellaiche paper The tangent space in sub-riemannian geometry, in the book Sub-riemannian geometry, eds. A. Bellaiche, J.-J. Risler, Progress in Mathematics 144, Birkhauser 1996.

In this post we shall see how Bellaiche proposes to extract the algebraic structure of the metric  tangent space $T_{p}M$ at a point $p \in M$, where $M$ is a regular sub-riemannian manifold. Remember that the metric tangent space is defined up to arbitrary isometries fixing one point, as the limit in the Gromov-Hausdorff topology over isometry classes of compact pointed metric spaces

$[T_{p} M, d^{p}, p] = \lim_{\varepsilon \rightarrow 0} [\bar{B}(p, \varepsilon), \frac{1}{\varepsilon} d, p]$

where $[X, d, p]$ is the isometry class of the compact  metric space $(X,d)$ with a marked point $p \in X$. (Bellaiche’s notation is less precise but his previous explanations clarify that his relations (83), (84) are meaning exactly what I have written above).

A very important point is that moreover, this convergence is uniform with respect to the point $p \in M$. According to Gromov’s hint mentioned  by  Bellaiche, this is the central point of the matter. By using this and the structure of the trivial pair groupoid $M \times M$, Bellaiche proposes to recover the Carnot group algebraic structure of $T_{p}M$.

From this point on I shall pass to a personal interpretation of the  section 8.2 “A purely metric derivation of the group structure in $T_{p}M$ for regular $p$” of Bellaiche article. [We don’t have to worry about “regular” points because I already supposed that the manifold is “regular”, although Bellaiche’s results are more general, in the sense that they apply also to sub-riemannian manifolds which are not regular, like the Grushin plane.]

In order to exploit the limit in the sense of Gromov-Hausdorff, he needs first an embodiment of the abstract isometry classes of pointed metric spaces. More precisely, for any $\varepsilon > 0$ (but sufficiently small), he uses a function denoted by $\phi_{x}$, which he states that it is defined on $T_{x} M$ with values in $M$. But doing so would be contradictory with the goal of constructing the tangent space from the structure of the trivial pair groupoid and dilations. For the moment there is no intrinsic meaning of $T_{x} M$, although there is one from differential geometry, which we are not allowed to use, because it is not intrinsic to the problem.  Nevertheless, Bellaiche already has the functions $\phi_{x}$, by way of his lengthy proof (but up to date the best proof) of the existence of adapted coordinates. For a detailed discussion see my article “Dilatation structures in sub-riemannian geometry” arXiv:0708.4298.

Moreover, later he mentions “dilations”, but which ones? The natural dilations he has from the vector space structure of the tangent space in the usual differential geometric sense? This would have no meaning, when compared to his assertion that the structure of a Carnot group of the metric tangent space is concealed in dilations.  The correct choice is again to use his adapted coordinate systems and use intrinsic dilations.  In fewer words, what Bellaiche probably means is that his functions $\phi_{x}$ are also decorated with the scale  parameter $\varepsilon >0$, so they should deserve the better notation $\phi_{\varepsilon}^{x}$,  and that these functions behave like dilations.

A natural alternative to Bellaiche’s proposal would be to use an embodiment of the isometry class $[\bar{B}(x, \varepsilon), \frac{1}{\varepsilon} d, x]$ on the space $M$, instead of the differential geometric tangent space $T_{x}M$.  With this choice, what Bellaiche is saying is that we should consider dilation like functions $\delta^{x}_{\varepsilon}$ defined locally from $M$ to $M$ such that:

• they preserve the point $x$ (which will become the “$0$” of the metric tangent space): $\delta^{x}_{\varepsilon} x = x$
• they form a one-parameter group with respect to the scale: $\delta^{x}_{\varepsilon} \delta^{x}_{\mu} y = \delta^{x}_{\varepsilon \mu} y$ and $\delta^{x}_{1} y = y$,
• for any $y, z$ at a finite distance from $x$ (measured with the sub-riemannian distance $d$, more specifically such that  $d(x,y), d(x,z) \leq 1$) we have

$d^{x}(y,z) = \frac{1}{\varepsilon} d( \delta^{x}_{\varepsilon} y, \delta^{x}_{\varepsilon}z) + O(\varepsilon)$

where $O (\varepsilon)$ is uniform w.r.t. (does not depend on) $x, y , z$ in compact sets.

Moreover, we have to keep in mind that the “dilation”  $\delta^{x}_{\varepsilon}$ is defined only locally, so we have to avoid to go far from $x$, for example we have to avoid to apply the dilation for $\varepsilon$ very big to points at finite distance from $x$.

Again, the main thing to keep in mind is the uniformity assumption. The choice of the embodiment provided by “dilations” is not essential, we may take them otherwise as we please, with the condition that at the limit $\varepsilon \rightarrow 0$ certain combinations of dilations converge uniformly. This idea suggested by Bellaiche reflects the hint by Gromov.  In fact this is what is left from the idea of a manifold in the realm of sub-riemannian geometry  (because adapted coordinates cannot be used for building manifold structures, due to the fact that “local” and “infinitesimal” are not the same in sub-riemannian geometry, a thing rather easy to misunderstand until you get used to it).

Let me come back to Bellaiche reasoning, in the setting I just explained. His purpose is to construct the operation in the tangent space, i.e. the addition of vectors. Only that the addition has to recover the structure of a Carnot group, as proven by Bellaiche. This means that the addition is not a commutative, but a noncommutative  nilpotent operation.

OK, so we have the base point $x \in M$ and two near points $y$ and $z$, which are fixed. The problem is how to construct an intrinsic addition of $y$ and $z$ with respect to $x$. Let us denote by $y +_{x} z$ the result we are seeking. (The link with the trivial pair groupoid is that we want to define an operation which takes $(x,y)$ and $(x,z)$ as input and spills $(x, y+_{x} z)$ as output.)

The relevant figure is the following one, which is an improved version of the Figure 5, page 76 of Bellaiche paper.

Bellaiche’s recipe has to do with the points in blue. He says that first we have to go far from $x$, by dilating the point $z$ w.r.t. the point $x$, with the coefficient $\varepsilon^{-1}$. Here $\varepsilon$ is considered to be small (it will go to $0$), therefore $\varepsilon^{-1}$ is big.  The result is the blue point $A$. Then, we dilate (or rather contract) the point $A$  by the coefficient $\varepsilon$ w.r.t. the point $y$. The result is the blue point $B$.

Bellaiche claims that when $\varepsilon$ goes to $0$ the point $B$ converges to the sum $y +_{x} z$. Also, from this intrinsic definition of addition, all the other properties (Carnot group structure) of the operation may be deduced from the uniformity of this convergence. He does not give a proof of this fact.

The idea of Bellaiche is partially correct (in regards to the emergence of the algebraic properties of the operation from uniformity of the convergence of its definition) and partially wrong (this is not the correct definition of the operation). Let me start with the second part. The definition of the operation has the obvious default that it uses the point $A$ which is far from $x$. This is in contradiction with the local character of the definition of the metric tangent space (and in contradiction with the local definition of dilations).  But he is wrong from interesting reasons, as we shall see.

Instead, a slightly different path could be followed, figured by the red points $C, D, E$. Indeed, instead of going far away first (the blue point $A$), then coming back at finite distance from $x$ (the blue point $B$), we may first come close to $x$ (by using  the red points $C, D$), then inflate the point $D$ to finite distance from $x$ and get the point $E$. The recipe is a bit more complicated, it involves three dilations instead of two, but I can prove that it works (and leads to the definition of dilation structures and later to the definition of emergent algebras).

The interesting part is that if we draw, as in the figure here,  the constructions in the euclidean plane, then we get $E = B$, so actually in this case there is no difference between the outcome of these constructions. At further examination this looks like an affine feature, right? But in fact this is true in non-affine situations, for example in the case of intrinsic dilations in Carnot groups, see the examples from the post “Emergent algebra as combinatory logic (part I)“.

Let’s think again about these dilations, which are central to our discussion, as being operations. We may change the notations like this:

$\delta^{x}_{\varepsilon} y = x \circ_{\varepsilon} y$

Then, it is easy to verify that the equality between the red point $E$ and the blue point $B$ is a consequence of the fact that in usual vector spaces (as well as in their non-commutative version, which are Carnot groups), the dilations, seen as operations, are self-distributive! That is why Bellaiche is actually right in his definition of the tangent space addition operation, provided that it is used only for self-distributive dilation operations. (But this choice limits the applications of his definition of addition operation only to Carnot groups).

Closing remark: I was sensible to these two last sections of Bellaiche’s paper because I was prepared by one of my previous obsessions, namely how to construct differentiability only from topological data.  This was the subject of my first paper, see the story told in the post “Topological substratum of the derivative“, there is still some mystery to it, see arXiv:0911.4619.

# Emergent algebras as combinatory logic (Part I)

At some point this new thread I am starting now will meet the Towards qubits thread.

Definition 1.  Let $\Gamma$  be a commutative group with neutral element denoted by $1$ and operation denoted multiplicatively. A $\Gamma$ idempotent quasigroup is a set $X$ endowed with a family of operations $\circ_{\varepsilon}: X \times X \rightarrow X$,  indexed by $\varepsilon \in \Gamma$, such that:

1. For any $\varepsilon \in \Gamma$ the pair $(X, \circ_{\varepsilon})$ is an idempotent quasigroup,
2. The operation $\circ_{1}$ is trivial: for any $x,y \in X$ we have $x \circ_{1} y = y$,
3. For any $x, y \in X$ and any $\varepsilon, \mu \in \Gamma$ we have:  $x \circ_{\varepsilon} ( x \circ_{\mu} y) = x \circ_{\varepsilon \mu} y$.

This definition may look strange, let me give some examples of $\Gamma$ idempotent quasigroups.

Example 1.  Real vector spaces: let $X$ be a real vector space, $\Gamma = (0,+\infty)$ with multiplication of reals as operation. We define, for any $\varepsilon > 0$ the following quasigroup operation:

$x \circ_{\varepsilon} y = (1-\varepsilon) x + \varepsilon y$

These operations give to $X$ the structure of a $(0,+\infty)$ idempotent quasigroup.  Notice that $x \circ_{\varepsilon}y$ is the dilation based at $x$, of coefficient $\varepsilon$, applied to $y$.

Example 2. Complex vector spaces: if $X$ is a complex vector space then we may take $\Gamma = \mathbb{C}^{*}$ and we continue as previously, obtaining an example of a $\mathbb{C}^{*}$ idempotent quasigroup.

Example 3.  Contractible groups: let $G$ be a group endowed with a group morphism $\phi: G \rightarrow G$. Let $\Gamma = \mathbb{Z}$ with the operation of addition of integers (thus we may adapt Definition 1 to this example by using “$\varepsilon + \mu$” instead of “$\varepsilon \mu$” and “$0$” instead of “$1$” as the name of the neutral element of $\Gamma$).  For any $\varepsilon \in \mathbb{Z}$ let

$x \circ_{\varepsilon} y = x \phi^{\varepsilon}(x^{-1} y)$

This a $\mathbb{Z}$ idempotent quasigroup. The most interesting case (relevant also for Definition 3 below) is the one when $\phi$ is an uniformly contractive automorphism of the topological group $G$. The structure of these groups is an active exploration area, see for example arXiv:0704.3737 by  Helge Glockner   and the bibliography therein  (a fundamental result here is Siebert article Contractive automorphisms on locally compact groups, Mathematische Zeitschrift 1986, Volume 191, Issue 1, pp 73-90).  See also conical groups and relations between contractive and conical groups introduced in arXiv:0804.0135,  shortly explained in arXiv:1005.5031.

Example 4.  Carnot groups: these are a particular example of a conical group. The most trivial noncommutative Carnot group is the Heisenberg group.

Example 5. A group with an invertible self-mapping $\phi: G \rightarrow G$  such that $\phi(e) =e$, where $e$ is the identity of the group $G$. In this case the construction from Example 3 works here as well because there is no need for $\phi$ to be a group morphism.

Example 6. Local versions. We may accept that there is a way (definitely needing care to well formulate, but intuitively cleart) to define a local version of the notion of a $\Gamma$  idempotent quasigroup. With such a definition, for example, a convex subset of a real vector space gives a local $(0,+\infty)$ idempotent quasigroup (as in Example 1) and a neighbourhood of the identity of a topological group $G$, with an identity preserving, locally defined invertible self map (as in Example 5) gives a $\mathbb{Z}$ local idempotent quasigroup.

Example 7. A particular case of Example 6, is a Lie group $G$ with the operations  defined for any $\varepsilon \in (0,+\infty)$ by

$x \circ_{\varepsilon} y = x \exp ( \varepsilon \log (x^{-1} y) )$

Example 8. A less symmetric example is the one of $X$ being a riemannian manifold, with associated operations  defined for any $\varepsilon \in (0,+\infty)$ by

$x \circ_{\varepsilon}y = \exp_{x}( \varepsilon \log_{x}(y))$

Example 9. More generally, any metric space with dilations  (introduced in  arXiv:math/0608536[MG] )  is a local idempotent quasigroup.

Example 10.  One parameter deformations of quandles. A quandle is a self-distributive quasigroup. Take now a one-parameter family of quandles (indexed by $\varepsilon \in \Gamma$) which satisfies moreover points 2. and 3. from Definition 1. What is interesting about this example is that quandles appear as decorations of knot diagrams, which are preserved by the Reidemeister moves.  At closer examination, examples 1-4 are all particular cases of one parameter quandle deformations!

________________

I shall define now the operations of approximate sum and approximate difference associated to a $\Gamma$  idempotent quasigroup.

For any $\varepsilon \in \Gamma$, let use define $x \bullet_{\varepsilon} y = x \circ_{\varepsilon^{-1}} y$.

Definition 2.  The approximate sum operation is (for any $\varepsilon \in \Gamma$)

$\Sigma_{\varepsilon}^{x}(y,z) = x \bullet_{\varepsilon} ( (x \circ_{\varepsilon} y) \circ_{\varepsilon} z)$

The approximate difference operation is (for any $\varepsilon \in \Gamma$)

$\Delta_{\varepsilon}^{x}(y,z) = (x \circ_{\varepsilon} y) \bullet_{\varepsilon} (x \circ_{\varepsilon} z)$

_________________

Suppose now that $X$ is a separable uniform space.  Let us suppose that the commutative group $\Gamma$ is a topological group endowed with an absolute, i.e. with an invariant topological filter, denoted by $0$. We write $\varepsilon \rightarrow 0$ for a net in $\latex \Gamma$ which converges to the filter $0$. The image to have in mind is $\Gamma = (0, + \infty)$ with multiplication of reals as operation and with the filter $0$ as the filter generated by sets $(0, a)$ with $a> 0$. This filter is the restriction to the set $(0,\infty) \subset \Gamma$ of the filter of  neighbourhoods of the number $0 \in \mathbb{R}$.  Another example is $\Gamma = \mathbb{Z}$ with addition of integers as operation, seen as a discrete topological group, with the absolute generated by sets $\left\{ n \in \mathbb{Z} \, \, : \, \, n \leq M \right\}$ for all $M \in \mathbb{Z}$. For this example the neutral element (denoted by $1$ in Definition 1) is the integer $0$, therefore in this case we can change notations from multiplication to addition, $1$ becomes $0$, the absolute $0$ becomes $- \infty$ , and so on.

Definition 3. An emergent algebra (or uniform idempotent quasigroup) is a $\Gamma$ idempotent quasigroup  $X$, as in Definition 1, which satisfies the following topological conditions:

1. The family of operations $\circ_{\varepsilon}$ is compactly contractive, i.e. for any compact set $K \subset X$, for any $x \in K$ and for any open neighbourhood $U$ of $x$, there is an open set $A(K,U) \subset \Gamma$ which belongs to the absolute $0$ such that for any $u \in K$ and $\varepsilon \in A(K,U)$ we have $x \circ_{\varepsilon} u \in U$.
2. As $\varepsilon \rightarrow 0$ there exist the limits

$\lim_{\varepsilon \rightarrow 0} \Sigma^{x}_{\varepsilon} (y,z) = \Sigma^{x} (y,z)$  and $\lim_{\varepsilon \rightarrow 0} \Delta^{x}_{\varepsilon} (y,z) = \Delta^{x} (y,z)$

and moreover these limits are uniform with respect to $x,y,z$ in compact sets.

The structure theorem of emergent algebras is the following:

Theorem 1.  Let $X$ be  a $\Gamma$ emergent algebra. Then for any $x \in X$ the pair $(X, \Sigma^{x}(\cdot, \cdot))$ is a conical group.

In the next post on this subject I shall explain why this is true, in the language of graphic lambda calculus.

# Is there a positional numeral system for Carnot groups?

I advertise here a question I posed on mathoverflow, then I shall give a motivation for this question.

In the following is a reproduction of  the question (thanks for all useful comments, read them at mathoverflow) (slight modification of the title of the question here)

What is the computational complexity of multiplication in a Carnot group?

Background:  A Carnot group is a real nilpotent Lie group $N$ whose Lie algebra $Lie(N)$ admits a direct sum decomposition

$Lie(N) = V_{1}+ ... + V_{m}$

such that if $i+j \leq m$ then  $[V_{i}, V_{j}] \subset V_{i+j}$,   otherwise $[V_{i}, V_{j}] = 0$.

Moreover, it is required that $V_{1}$ generates the whole Lie algebra $Lie(N)$.

Detailed question: What is the computational complexity of multiplication  in $N$, as a function of $m$, $dim V_{1}$, … , $dim V_{m}$?

More background:

1. “Computational complexity” means giving an estimate for the running time of an algorithm for performing the multiplication operation.I am looking for nontrivial estimates, better than, for example, the one coming from matrix multiplication.Exponentiation and logarithms are not taken into account (one variant of thinking is to use BCH formula for multiplication, with a finite number of terms due to nilpotency, other variant would be to use the remark from example 2.4 below and think about multiplication as matrix multiplication).

2. Examples of Carnot groups:

2.1. When $m=1$, this is a real vector space and the multiplication operation is just addition of vectors (thus the complexity of the  multiplication operation is the one of the addition of vectors, much less than the one of matrix multiplication).

2.2. When $m=2$, the simplest example is the Heisenberg group [see posts here about it] .

2.3. The group of invertible, $n \times n$  upper triangular matrices, has $m = n-1$ and $dim V_{i} = n-i$. Is there any better estimate than $n^{3}$ in this case? (I think so, but cannot find a reference to an answer.) [In fact Henry Cohn answered to this:

“The exponent for multiplication of upper triangular matrices is the same as that for full matrix multiplication. Specifically, you can reduce $n \times n$ matrix multiplication to the $3n \times 3n$ upper triangular case. (Use nine $n \times n$  blocks, with identity matrices on the diagonal and a zero matrix in the upper right corner.) So for that case the best exponent that’s known is 2.373, the same as for the general case.

The reduction is not a morphism. Suppose $A$  and $B$ are any $n \times n$  matrices (not necessarily invertible), and define $3n \times 3n$ matrices $A'$ and $B'$ as follows. Both are the identity matrix, except for one $n \times n$ block. Specifically, $A'$ has $A$ as the middle top $n \times n$ block [i.e. the $(1,2)$ block is $A$, the diagonal blocks are $n \times n$ identity matrices, all other blocks are $n \times n$  $O$ matrices], and $B'$ has $B$ as the middle right $n \times n$  block [i.e. the $(2,1)$ block is $B$, the diagonal blocks are $n \times n$ identity matrices, all other blocks are $n \times n$  $O$ matrices]. Then $A'B'$ has $AB$  as its upper right block [i.e. the $(3,3)$ block]. These larger matrices are upper triangular, so if you can efficiently multiply upper triangular matrices, then you can efficiently multiply arbitrary matrices (of one third the size).”

2.4. Any Carnot group can be seen as a subgroup of the group from example 2.3.

2.5. Carnot groups appear as metric tangent spaces for sub-riemannian, manifolds. As such, they are a kind of noncommutative vector spaces, with the “trivial” exception when they are commutative, like in the case of riemannian manifolds, when the tangent space is like in example 2.1  (other “simple” example being the metric contact manifolds, with the tangent space like in 2.2).”

What is my motivation behind this question? Actually, I wrote about this in the post “Combinatorics versus geometric …“.

Indeed, a positional numeral system can be seen from two related viewpoints:

1. as the basic ingredient for the algorithm of computing the “multiplication” operation in the abelian group of integers (or reals) (that’s like in the example 2.1 above),

2. as a “positional system” in the geometric sense, by exploiting the self-similarity of the group of integers (or reals), something which has not much to do with numbers. Let me explain: I am now in Europe, Romania, Bucharest. This is a positional notation for the place where I am, because Romania is a country in Europe and Bucharest is a city in Romania. Likewise, the number 123 (in decimal basis) is that number which is “in the continent $100$“, in the “country $20$” and in the “city $3$“.  What makes such a positional notation useful for numbers is the self-similarity (manifested by the system of orders of magnitude) of the “world of numbers”.

Let us just put all together: is there a “positional numeral system” for Carnot groups which can give fast algorithms for computing the multiplication operation (in a Carnot group), by exploiting the self-similarity of a Carnot group?