Tag Archives: positional system

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?

Gromov’s Ergobrain

Misha Gromov updated his very interesting “ergobrain” paper

Structures, Learning and Ergosystems: Chapters 1-4, 6 

Two quotes I liked: (my emphasis)

The concept of the distance between, say, two locations on Earth looks simple enough, you do not think you need a mathematician to tell you what distance is. However, if you try to explain what you think you understand so well to a computer program you will be stuck at every step.  (page 76)

Our ergosystems will have no explicit knowledge of numbers, except may be for a few small ones, say two, three and four. On the contrary, neurobrains, being physical systems, are run by numbers which is reflected in their models, such as neural networks which sequentially compose addition of numbers with functions in one variable.

An unrestricted addition is the essential feature of “physical numbers”, such as mass, energy, entropy, electric charge. For example, if you bring together \displaystyle 10^{30}  atoms, then, amazingly, their masses add up […]

Our ergosytems will lack this ability. Definitely, they would be bored to death if they had to add one number to another \displaystyle 10^{30} times. But the \displaystyle 10^{30} -addition, you may object, can be implemented by \displaystyle log_{2} 10^{30} \sim 100 additions with a use of binary bracketing; yet, the latter is a non-trivial structure in its own right that our systems, a priori, do not have.  Besides, sequentially performing even 10 additions is boring. (It is unclear how Nature performs “physical addition” without being bored in the process.) (page 84)

Where is this going? I look forward to learn.