7
$\begingroup$

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}$?

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

$\endgroup$
17
  • 2
    $\begingroup$ can you clarify please how do you measure the complexity and what is input and output. Otherwise, if it realized a matrix group - multiplication is multiplication of matrices, so complexity is N^3, where N is size of faithful representation, which i think (not sure ) exists by Ado theorem + exponentiation $\endgroup$ Sep 11, 2012 at 11:43
  • 1
    $\begingroup$ PS what are examples of Carnot groups to keep in mind ? $\endgroup$ Sep 11, 2012 at 11:45
  • $\begingroup$ Computational complexity as an estimate for the running time of an algorithm for performing the multiplication. Examples of Carnot groups: 1. - m=1, this is a real vector space and the multiplication operation is just addition of vectors. 2. - m=2, the simplest example is the Heisenberg group 3. - the group of invertible, $n \times n$ upper triangular matrices, has $m=n-1$, $dim V_{i}$ = n-i$. 4. - any Carnot group can be seen as a subgroup of the group from example 3. 5. - Carnot groups appear as metric tangent spaces for sub-riemannian, manifolds, see link in the question. $\endgroup$ Sep 11, 2012 at 11:56
  • 5
    $\begingroup$ 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. I'm not sure what the best trade-off one can prove is, as one transitions from vector addition to matrix multiplication. $\endgroup$
    – Henry Cohn
    Sep 13, 2012 at 23:40
  • 1
    $\begingroup$ The reduction is not a homomorphism. 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, and $B'$ has $B$ as the middle right $n \times n$ block. Then $A'B'$ has $AB$ as its upper right 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). $\endgroup$
    – Henry Cohn
    Sep 20, 2012 at 12:43

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.