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?

Does this give us a way to “normalize” tensor products between Carnot groups??

What is a tensor product between Carnot groups? (there may be more than one definition)

At this point I do not know how to write out the description! I am just fishing for a possible solution to the tensor product problem that I have encountered in my research. It is analogous to the problem in n-categories (http://202.38.126.65/oldmirrors/www.maths.usyd.edu.au/u/AusCat/abstracts/981125mb.html) and in Chu spaces (http://chu.stanford.edu/)

The question that I am trying to address is: How does one combine a pair of Stone spaces such that the result is a stone space and preserves the sense of a commensurable inner product for both. Can an exterior product do this? I am getting ideas from the way this is done for Hilbert spaces but I do not seem to be able to use the isomorphism between Hilbert spaces to solve the incommensurability problem.

In plain terms: Consider a pair of computers that are each generating a simulated landscape and that a user on each computer can alter the landscape (from their respective points of view) in some way. How do we generate new landscape that show the changes that are done by each user so that the picture that each user could see of the landscape remains consistent with the old landscape.

MMORP games such as World of Warcraft do this, but they do not do so in a way that is continuous. I am looking for a continuous version of the updating of the landscape for the multiple users.

How is this done in discrete time case?

Yes, that is the way to avoid the problem; by imposing an absolute clock, or equivalently, a global synchronization. I am looking for a continuum limit of this, the continuous time version.

Hi Stephen, could you sometime comment something useful and consistent for me on consistency models (they’re a lot and I was not aware of them)?

Hi Marius,

Thank you for the reference. I see the sentence “Consistency models define rules for the apparent order and visibility of updates, and it is a continuum with tradeoffs.” I will look into this further.

I have been investigating the consistency (and concurrency) problem by studying work on the http://en.wikipedia.org/wiki/Satisfiability_of_boolean_expressions and looking for work that considers how to alter the number of propositions of an algebra such that SAT is conserved. This is a very hard problem as one can see by looking at the lattices.

Another thought. You wrote: “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?”

How are the images of the Carnot group distinguished from each other? In a fractal, such as a Julia or a Mandelbrot, we see that there is a periodicity to the images that are similar but we must “zoom” in or out to obtain the idea of transforming the image back into itself. Is there a “length” type of measure that this implies; the “distance between one image and the same version of it at a different scale?

A Carnot group (think about the mathematicians’ Heisenberg group ), TOGETHER WITH A CONICAL GROUP NORM (like the one coming from a sub-riemannian left invariant distance), is self similar at any scale, just like the Euclidean space is.

The difference between such “smooth fractals” like the Euclidean (with an euclidean distance) or the Heisenberg group with a Koranyi norm (google it), on one side, and Mandelbrot set, say, on the other side, is that in the first case we speak about METRIC self-similarity (i.e. the “similarity” is a bijection from a set to a subset which is an isometry up to a multiplicative constant), while, in the second case, the “similarity” is a bijection from the fractal (seen as a subset of an euclidean space) to a subset of it which in general is an affine transformation (thus it does not preserve the implicitly assumed euclidean distance modulo a multiplicative term).

The matter behind is: what do you mean by “an image of a Carnot group”? In fact, such an image should be an isometric embedding of the Carnot group endowed with a sub-riemannian distance function into a more familiar space. In the case of a riemannian manifold, we know that a riemannian manifold, endowed with the distance function coming from the riemannian metric, admits an isometric embedding into an euclidean space of sufficiently high dimension. In particular, any riemannian manifold, seen as a metric space with the respective riemannian distance, can be isometrically embedded into the Hilbert space, seen as a metric space with the distance coming from the norm.

Opposed to this, non-commutative Carnot groups (endowed with a sub-riemannian left invariant distance) DO NOT EMBEDD isometrically in the Hilbert space. They admit embeddings into Banach spaces, though, but for my tastes, this is a misleading direction.

Re Stephen on consistency models: Yes, I arrived to that page from another one, cache coherence, which clearly interests me and I have the impression that you too, hence the question (and the question behind the question is: what happens when passing to the limit in space or time with each of this multitude of models?)

The closest work that I have found that looks at the continuum aspect is this: http://arxiv.org/abs/math/9805008 and http://planetmath.org/martinsaxiomandthecontinuumhypothesis

All of the work is focused in the purely abstract area – no thoughts of framing it in terms of space and time – but it seems natural to think in that direction using the computational resource requirements necessary for the achievement of bounded(?) satisfiability for some lattice (or ultrafilter of a lattice).

It seem that the first question, if the relation to the continuum holds) that must be answered is: Can the Stone–Čech compactification (http://en.wikipedia.org/wiki/Stone%E2%80%93%C4%8Cech_compactification) and/or Szemerédi’s theorem (http://en.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem) be used to ‘back engineer’ the general topological space (in some limit) from some class (?) of images (as per your comment #9 above).

A general question about “positional numeral system”. Can these be translated (isomorphisms) into graphs or matrices?

Positional number systems exists only when there is a self-similarity to exploit. And not only this, say you have a set acted by some group of “translations”, such that the set is covered by an increasing sequence of subsets and you can cover by an (universal number of) K translations of . If is a finite set then you know that the cardinal of is like . Otherwise said is like the logarithm of the cardinal of . That’s trivial, but that is the source of logarithm functions in estimates regarding information. But it is so ingrained to think about numbers as being made of digits, instead of thinking that representing numbers by a positional number system is a great recent invention (at the history scale)… that people forget to notice that there’s a geometric content of this, a “space” for counting in this way, an idea which may be applied to other groups than abelian ones. The idea can be applied to groups with polynomial growth, for sure. Funny that you ask the “translated into graphs” question. I think so, but for the moment I play with this until I’ll be sure exactly how. I am itching to post about this, but I decided to play a bit more. However see the recent posts on Ruzsa inequality, and Plunnecke.

It seems that our thoughts are similar here and yet my own are not formal or cast in stone. Alternative ways of thinking of a space (“a set with additional structure”) is required… Kevin Knuth has written some very interesting papers on this that build space up from ordered sets, but how those connect to your work is very nebulous. (I am a philosopher and not a mathematician…)

“a channel of noisy communication between two worlds”, yes. Exactly.

Have you see this? http://terrytao.wordpress.com/2009/10/27/an-entropy-plunnecke-ruzsa-inequality/

Yes, of course. Ah, you saw the channel comment. As I said, I am itching to write about 🙂 . Btw, have you seen this? Very funny, albeit unrelated. Sometimes is more about brain formatting than some mathematical technique.

http://rjlipton.wordpress.com/2013/04/18/subset-powers-of-graphs/ more fun!

also: http://gowers.wordpress.com/2011/02/10/a-new-way-of-proving-sumset-estimates/

Forgive me, did we talk about this http://en.wikipedia.org/wiki/Interactive_proof_system ?

No. It makes me think about Gordon Pask’ Interaction of Actors theory.

Ah, you know Pask. Excellent! I am trying to use bisimulation (between pairs of compuational systems) for this, but my first attempt at a formal model failed. Resently, Mike Stay has found http://en.wikipedia.org/wiki/Bicategories useful for this. See http://arxiv.org/abs/1301.1053

As to the IPS idea above, I think that it’s maturity gives us a nice model. I suspect that we could used it is there is a way to convert the asymmetry in computational resources between the prover and the verifier into a relation what is symetric, trading trustworthiness for resources (giving ability to predict/simulate the other system).

Yes, I know about Pask, there’s even a post here. Question open.

Concerning IPS, I don’t know anything, sorry.