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 whose Lie algebra admits a direct sum decomposition

such that if then , otherwise .

Moreover, it is required that generates the whole Lie algebra .

* Detailed question:* What is the computational complexity of multiplication in , as a function of , , … , ?

**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 , 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 , the simplest example is the Heisenberg group [see posts here about it] .

2.3. The group of invertible, upper triangular matrices, has and . Is there any better estimate than 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 matrix multiplication to the upper triangular case. (Use nine 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 and are any matrices (not necessarily invertible), and define matrices and as follows. Both are the identity matrix, except for one block. Specifically, has as the middle top block [i.e. the block is , the diagonal blocks are identity matrices, all other blocks are matrices], and has as the middle right block [i.e. the block is , the diagonal blocks are identity matrices, all other blocks are matrices]. Then has as its upper right block [i.e. the 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 “, in the “country ” and in the “city “. 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?