# 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?

# What’s the difference between uniform and coarse structures? (I)

See this, if you need: uniform structure and coarse structure.

Given a set $X$, endowed with an uniform structure or with a coarse structure, Instead of working with subsets of $X^{2}$, I prefer to think about the trivial groupoid $X \times X$.

Groupoids. Recall that a groupoid is a small category with all arrows invertible. We may define a groupoid in term of it’s collection of arrows, as follows: a set $G$ endowed with a partially defined operation $m: G^{(2)} \subset G \times G \rightarrow G$, $m(g,h) = gh$, and an inverse operation $inv: G \rightarrow G$, $inv(g) = g^{-1}$, satisfying some well known properties (associativity, inverse, identity).

The set $Ob(G)$ is the set of objects of the groupoid, $\alpha , \omega: G \rightarrow Ob(G)$ are the source and target functions, defined as:

– the source fonction is $\alpha(g) = g^{-1} g$,

– the target function is $\omega(g) = g g^{-1}$,

– the set of objects is $Ob(G)$ consists of all elements of $G$ with the form $g g^{-1}$.

Trivial groupoid. An example of a groupoid is $G = X \times X$, the trivial groupoid of the set $X$. The operations , source, target and objects are

$(x,y) (y,z) = (x,z)$, $(x,y)^{-1} = (y,x)$

$\alpha(x,y) = (y,y)$, $\omega(x,y) = (x,x)$,

– objects $(x,x)$ for all $x \in X$.

In terms of groupoids, here is the definition of an uniform structure.

Definition 1. (groupoid with uniform structure) Let $G$ be a groupoid. An uniformity $\Phi$ on $G$ is a set $\Phi \subset 2^{G}$ such that:

1. for any $U \in \Phi$ we have $Ob(G) \subset U$,

2. if $U \in \Phi$ and $U \subset V \subset G$ then $V \in \Phi$,

3. if $U,V \in \Phi$ then $U \cap V \in \Phi$,

4. for any $U \in \Phi$ there is $V \in \Phi$ such that $VV \subset U$,  where $VV$ is the set of all $gh$ with $g, h \in V$ and moreover $(g,h) \in G^{(2)}$,

5. if $U \in \Phi$ then $U^{-1} \in \Phi$.

Here is a definition for a coarse structure on a groupoid (adapted from the usual one, seen on the trivial groupoid).

Definition 2.(groupoid with coarse structure) Let $G$ be a groupoid. A coarse structure  $\chi$ on $G$ is a set $\chi \subset 2^{G}$ such that:

1′. $Ob(G) \in \chi$,

2′. if $U \in \chi$ and $V \subset U$ then $V \in \chi$,

3′. if $U,V \in \chi$ then $U \cup V \in \chi$,

4′. for any $U \in \chi$ there is $V \in \chi$ such that $UU \subset V$,  where $UU$ is the set of all $gh$ with $g, h \in U$ and moreover $(g,h) \in G^{(2)}$,

5′. if $U \in \chi$ then $U^{-1} \in \chi$.

Look pretty much the same, right? But they are not, we shall see the difference when we take into consideration how we generate such structures.

Question. Have you seen before such structures defined like this, on groupoids? It seems trivial to do so, but I cannot find this anywhere (maybe because I am ignorant).

UPDATE (01.08.2012): Just found this interesting paper  Coarse structures on groups, by Andrew Nicas and David Rosenthal, where they already did on groups something related to what I want to explain on groupoids. I shall be back on this.

# Approximate groupoids may be useful

____________________________________

I appreciated yesterday the talk of Harald Helfgott, here is the link to the arxiv paper which was the subject of his communication: On the diameter of permutation groups (with Á. Seress).

At the end of his talk Harald stated as a conclusion that (if I well understood) the approximate groups field should be regarded as the study of

“stable configurations under the action of a group”

where “stable configuration” means a set (or a family…) with some controlled behaviour of its growth under the “action of a group”, understood maybe in a lax, approximate sense.

This applies to approximate groups, he said, where the action is by left translations, but it could apply to the conjugate action as well, and evenin  more general settings, where one has a space where a group acts.

My understanding of this bold claim is that Harald suggests that the approximate groups theory is a kind of geometry in the sense of Felix Klein: the (approximate, in this case) study of stable configuratiuons under the action of a group.

Today I just remembered a comment that I have made last november on the blog of Tao, where I proposed to study “approximate groupoids”.

Why is this related?

Because a group acting on a set is just a particular type of groupoid, an action groupoid.

Here is the comment (link), reproduced further.

“Question (please erase if not appropriate): as a metric space is just a particular example of a normed groupoid, could you point me to papers where “approximate groupoids” are studied? For starters, something like an extension of your paper “Product set estimates for non-commutative groups”, along the lines in the introduction “one also consider partial sum sets …”, could be relevant, but I am unable to locate any. Following your proofs could be straightforward, but lengthy. Has this been done?

For example, a $k$  approximate groupoid $A \subset G$ of a groupoid  $G$ (where $G$ denotes the set of arrows) could be a

(i)- symmetric subset of $G$: $A = A^{-1}$, for any $x \in Ob(G)$  $id_{x} \in A$  and

(ii)- there is another, symmetric subset $K \subset G$ such that for any   $(u,v) \in (A \times A) \cap G^{(2)}$  there are $(w,g) \in (A \times K) \cap G^{(2)}$  such that $uv = wg$,

(iii)- for any $x \in Ob(G)$  we have $\mid K_{x} \mid \leq k$.

One may replace the cardinal, as you did, by a measure (or random walk kernel, etc), or even by a norm.”

UPDATE (28.10.2012): Apparently unaware about the classical proof of Ronald Brown,  by way of groupoids, of the Van Kampen theorem on the fundamental group of a union of spaces, Terence Tao has a post about this subject. I wonder if he is after some applications of his results on approximate groups in the realm of groupoids.

# Approximate algebraic structures, emergent algebras

I updated and submitted for publication the paper “Emergent algebras“.

This is the first paper where emergent algebras appear. The subject is further developed in the paper “Braided spaces with dilations and sub-riemannian symmetric spaces“.

I strongly believe this is a very important notion, because it shows how  both the differential and algebraic realms  emerge naturally, from abstract nonsense. It is a “low tech” approach, meaning that I don’t use in the construction any “high tech” mathematical object, everything is growing from the grass.

One interesting fact, apart from the strange ideas of the paper (it is already verified that reading the paper algebraists will not understand easily the strength of the axiom concerning uniform convergence and analysts will not care enough about the occurrence of algebraic structure very much alike quandles and racks), is that an emergent algebra can also be seen as an approximate algebraic structure! But in a different sense than approximate groups.  The operations themselves are approximately associative, for example.

And my next question is: is this a really different notion of approximate algebraic structure than approximate groups? Or there is a way to see, for example, an approximate group (btw, why not an approximate symmetric space in the sense of Loos, whatever this could mean?) as an emergent algebra?

My hope is that the answer is YES.

UPDATE:   No, in fact there are reasons to think that there is a complementarity, there is a mathematical object standing over both, which may be called POSITIONAL SYSTEM, more soon, but see also this previous post of mine.

Here is the abstract of the paper:

“Inspired from research subjects in sub-riemannian geometry and metric geometry, we propose uniform idempotent right quasigroups and emergent algebras as an alternative to differentiable algebras.
Idempotent right quasigroups (irqs) are related with racks and quandles, which appear in knot theory (the axioms of a irq correspond to the first two Reidemeister moves). To any uniform idempotent right quasigroup can be associated an approximate differential calculus, with Pansu differential calculus in sub-riemannian geometry as an example.
An emergent algebra A over a uniform idempotent right quasigroup X is a collection of operations such that each operation emerges from X, meaning that it can be realized as a combination of the operations of the uniform irq X, possibly by taking limits which are uniform with respect to a set of parameters.
Two applications are considered: we prove a bijection between contractible groups and distributive uniform irqs (uniform quandles) and that some symmetric spaces in the sense of Loos may be seen as uniform quasigroups with a distributivity property. “

# Proof mining and approximate groups, announcement

The last weeks have been very busy for personal reasons. I shall come back to writing on this blog in short time.

With Laurentiu Leustean we won (a month ago, but the project has been submitted this Spring) the financing for our research project

“Proof mining in metric anaysis, geometric group theory and ergodic theory”

(project PN-II-ID-PCE-2011-3-0383). Laurentiu is a specialist in proof mining with applications to geodesic spaces and ergodic theory; I am interested in emergent algebras, particularly in dilation structures, so one of our aims (in this project) is to understand why nilpotent like structures appear in the famous Gromov theorem on groups of polynomial growth, as well in approximate groups, by using proof mining techniques for “finitizing” emergent algebras, roughly.

This program is very close to one of the programs of Terence Tao, who continues his outstanding research on approximate groups. The following post

Ultraproducts as a bridge between hard analysis and soft analysis

made me happy because it looks like confirming that our dreams (for the moment) have a correspondent in reality and probably ideas like this are floating in the air.

UPDATE 25.10: Today a new post of Tao announces the submission on arxiv of the paper by him, Emmanuel Breuillard and Ben Green, “The structure of approximate groups“. I look forward to study it, to see if they explain why nilpotent structures appear in the limit. My explanation, in a different context, “A characterization of sub-riemannian spaces…”, related also to work of Gromov, namely why in sub-riemannian geometry nilpotent groups appear as models of metric tangent spaces, is that this is a feature of an emergent algebra. See also previous posts, like Principles: randomness/structure or emergent from a common cause?.

# Combinatorics versus geometric…

… is like using roman numerals versus using a positional numeral system, like the hindu-arabic numerals we all know very well. And there is evidence that our brain is NOT using combinatorial techniques, but geometric, see further.

What is this post about? Well, it is about the problem of using knowledge concerning topological groups in order to study discrete approximate groups, as Tao proposes in his new course, it is about discrete finitely generated groups with polynomial growth which, as Gromov taught us, when seen from far away they become nilpotent Lie groups, and so on. Only that there is a long way towards these subjects, so please bear me a little bit more.

This is part of a larger project to try to understand approximate groups, as well as normed groups with dilations, in a more geometric way. One point of interest is understanding the solution to the Hilbert’s fifth problem from a more general perspective, and this passes by NOT using combinatorial techniques from the start, even if they are one of the most beautiful mathematical gems which is the solution given by Gleason-Montgomery-Zippin to the problem.

What is combinatorial about this solution? Well, it reduces (in a brilliant way) the problem to counting, by using objects which are readily at hand in any topological group, namely the one-parameter subgroups. There is nothing wrong about this, only that, from this point of view, Gromov’s theorem on groups with polynomial growth appears as magical. Where is this nilpotent structure coming from?

As written in a previous post, Hilbert’s fifth problem without one-parameter subgroups, Gromov’ theorem is saying a profound geometrical thing about a finitely generated group with polynomial growth: that seen from far away this group is self-similar, that is a conical group, or a contractible group w.r.t. any of its dilations. That is all! the rest is just a Siebert’ result. This structure is deeply hidden in the proof and one of my purposes is to understand where it is coming from. A way of NOT understanding this is to use huge chunks of mathematical candy in order to make this structure appear by magic.

I cannot claim that I understand this, that I have a complete solution, but instead, for this post, I looked for an analogy and I think I have found one.

It is the one from the first lines of the post.

Indeed, what is wrong, by analogy, with the roman numeral system? Nothing, actually, we have generators, like I, V, X, L, C, D, M, and relations, like IIII = IV, and so on (yes, they are not generators and relations exactly like in a group sense). The problems appear when we want to do complex operations, like addition of large numbers. Then we have to be really clever and use very intelligent and profound combinatorial arguments in order to efficiently manage all the cancellations and whatnot coming from the massive use of relations. Relations are at very small scale, we have to bridge the way towards large scales, therefore we have to approximate the errors by counting in different ways and to be very clever about these ways.

Another solution for this, historically preferred, was to use a positional number system, which is more geometric, because it exploits a large scale property of natural numbers, which is that their collection is (approximately) self-similar. Indeed, take (as another kind of generators, again not in a group sense), a small set, like B={0, 1, 2, …, 8, 9} and count in base 10, which goes roughly like this: take a (big, preferably) natural number $X$ and do the following

– initialize $i = 1$,

– find the smallest natural power $a_{i}$ of 10 such that $10^{-a_{i}} X$ has a norm smaller than 10, then pick the element $k_{i}$ of $B$ which minimizes the distance to $10^{-a_{i}} X$,

– substract (from the right or the left, it does not matter here because addition of natural numbers is commutative) $10^{a_{i}} k_{i}$ from $X$, and rename the result by $X$,

-repeat until $X \in B$ and finish the algorithm by taking the last digit as $X$.

In the end (remember, I said “roughly”) represent $X$ as a string which codes the string of pairs $(a_{i}, k_{i})$.

The advantage of this representation of natural numbers is that we can do, with controlled precision, the addition of big numbers, approximately. Indeed, take two very big numbers $X, Y$ and take another number, like $10$. Then for any natural $n$ define

$(X+Y)$ approx(n) $= 10^{n} ( [X]_{n} + [Y]_{n})$

where $[X]_{n}$ is the number which is represented as the truncation of the string which represents $X$ up to the first $n$ letters, counting from left to right.
If $n$ is small compared with $X, Y$, then $(X+Y)$ approx(n) is close to the true $X+Y$, but the computational effort for calculating $(X+Y)$ approx(n) is much smaller than the one for calculating $X+Y$.

Once we have this large scale self-similarity, then we may exploit it by using the more geometrical positional numeral system instead of the roman numeral system, that is my analogy. Notice that in this (almost correct) algorithm $10^{a} X$ is not understood as $X+X+....+X$ $10^{a}$ times.

Let me now explain why the positional numeral system is more geometric, by giving a neuroscience argument, besides what I wrote in this previous post: “How not to get bored, by reading Gromov and Tao” (mind the comma!).

I reproduce from the wiki page on “Subitizing and counting

Subitizing, coined in 1949 by E.L. Kaufman et al.[1] refers to the rapid, accurate, and confident judgments of number performed for small numbers of items. The term is derived from the Latin adjective subitus (meaning “sudden”) and captures a feeling of immediately knowing how many items lie within the visual scene, when the number of items present falls within the subitizing range.[1] Number judgments for larger set-sizes were referred to either as counting or estimating, depending on the number of elements present within the display, and the time given to observers in which to respond (i.e., estimation occurs if insufficient time is available for observers to accurately count all the items present).

The accuracy, speed, and confidence with which observers make judgments of the number of items are critically dependent on the number of elements to be enumerated. Judgments made for displays composed of around one to four items are rapid,[2] accurate[3] and confident.[4] However, as the number of items to be enumerated increases beyond this amount, judgments are made with decreasing accuracy and confidence.[1] In addition, response times rise in a dramatic fashion, with an extra 250–350 ms added for each additional item within the display beyond about four.[5]

This is a brain competence which is spatial (geometrical) in nature, as evidenced by Simultanagnosia:

Clinical evidence supporting the view that subitizing and counting may involve functionally and anatomically distinct brain areas comes from patients with simultanagnosia, one of the key components of Balint’s syndrome.[14] Patients with this disorder suffer from an inability to perceive visual scenes properly, being unable to localize objects in space, either by looking at the objects, pointing to them, or by verbally reporting their position.[14] Despite these dramatic symptoms, such patients are able to correctly recognize individual objects.[15] Crucially, people with simultanagnosia are unable to enumerate objects outside the subitizing range, either failing to count certain objects, or alternatively counting the same object several times.[16]

From the wiki description of simultanagnosia:

Simultanagnosia is a rare neurological disorder characterized by the inability of an individual to perceive more than a single object at a time. It is one of three major components of Bálint’s syndrome, an uncommon and incompletely understood variety of severe neuropsychological impairments involving space representation (visuospatial processing). The term “simultanagnosia” was first coined in 1924 by Wolpert to describe a condition where the affected individual could see individual details of a complex scene but failed to grasp the overall meaning of the image.[1]

I rest my case.

# Principles: randomness/structure or emergent from a common cause?

I think both.

Finally Terence Tao presented a sketch of his project relating Hilbert’ fifth problem and approximate groups. For me the most interesting part is his Theorem 12 and its relation with Gromov’ theorem on finitely generated groups with polynomial growth.

A bit dissapointing (for me) is that he seems to choose to rely on “commutative” techniques and, not surprising, he is bound to get results valid only in riemannian geometry (or spaces of Alexander type) AND also to regard the apparition of nilpotent structures as qualitatively different from smooth structures.

For clarity reasons, I copy-paste his two “broad principles”

The above three families of results exemplify two broad principles (part of what I like to call “the dichotomy between structure and randomness“):

• (Rigidity) If a group-like object exhibits a weak amount of regularity, then it (or a large portion thereof) often automatically exhibits a strong amount of regularity as well;
• (Structure) This strong regularity manifests itself either as Lie type structure (in continuous settings) or nilpotent type structure (in discrete settings). (In some cases, “nilpotent” should be replaced by sister properties such as “abelian“, “solvable“, or “polycyclic“.)

Let me contrast with my

Principle of common cause: an uniformly continuous algebraic structure has a smooth structure because both structures can be constructed from an underlying emergent algebra (introduced here).

(from this previous post).

While his “dichotomy between structure and randomness“ principle is a very profound and mysterious one, the second part (Structure) is only an illusion created by psychological choices (I guess). Indeed, both (Lie) smooth structure and nilpotence are just “noncommutative (local) linearity”, as explained previously. Both smooth structure and “conical algebraic” structure (nilpotent in particular) stem from the same underlying dilation structure. What is most mysterious, in my opinion, be it in the “exact” or “approximate” group structure, is HOW a (variant of) dilation structure appears from non-randomness (presumably as a manifestation of Tao randomness/structure principle), i.e. HOW just a little bit of approximate self-similarity bootstraps to a dilation structure, or emergent algebra, which then leads to various flavors of “smoothness” and “nilpotence”.