2 added 1651 characters in body

More background:

• "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).

• 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 multiplication operation is the one of the addition of vectors, much less than matrix multiplication).

2.2. When m=2, the simplest example is the Heisenberg group

2.3. The group of invertible, $n \times n$ upper triangular matrices, has $m=n−1$, $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.)

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, see link in the question. 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).

• 1

# Computational complexity of multiplication in a nilpotent group?

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 $[V_{i}, V_{j}] \subset V_{i+j}$ if $i+j \leq m$, 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}$?