A roadmap to computing with space

I don’t know yet what exactly is “computing with space”, but I almost know. Further is a description of the road to this goal, along with an invitation to join.

Before starting this description, maybe is better to write what this explanation is NOT about.  I have arrived to the idea of “computing with space”  by branching from a beautiful geometry subject: sub-riemannian geometry. The main interest I have in this subject consists in giving an intrinsic (i.e. by using a minimal bag of tools) description of the differential structure of a sub-riemannian space. The fascinating part is that these spaces, although being  locally topologically trivial, have a differential calculus which is not amenable to the usual differential calculus on manifolds, in the same way as the hyperbolic space, say, is not a kind of euclidean space, geometrically. I consider very important and yet not well known  the discovery of the fact that there are spaces where we can define an intrinsic differential calculus fundamentally different than the usual one (locally, not globally, as it is the case with manifolds which admits different GLOBAL differential structures, although at the local level they are just pieces of an euclidean space). But in this post I shall NOT go to explain this. The road to computing with space branches from this one, however there are paths represented by mathematical hints which are criss-crossing  both these roads.

Let’s start.

1. In “Dilatation structures I. Fundamentals” I propose, in section 4 “Binary decorated trees and dilatations” a formalism for making easy various calculations with dilation structures (or “dilatation structures”, as I called them at the moment; notice that dilation vs dilatation is a battle won by dilations in math, but by dilatation in other fields, although the correct word historically is dilatations).

This formalism works with moves acting on binary decorated trees, with the leaves decorated with elements of a metric space. It was extremely puzzling that in fact the formalism worked without needing to know which metric space I use. It was also amazing to me that reasoning  with moves acting on binary trees gave proofs of generalizations of results  involving elaborate calculations with pseudo-differential operators and alike. At a close inspection it looked like somewhere in the background there is an abstract nonsense machine which is just applied to this particular case of metric spaces.

Here is an example of the formalism. The moves are (I use the names from graphic lambda calculus):




Define the following tree (and think about it as being the graphical representation of an operation):


Think that it represents u+v, with respect to the base point x.  Then we can prove that


which is a kind of associativity relation.  The proof by binary trees has nothing to do with sub-riemannian geometry, right? An indirect confirmation is that the same formalism works very well on the ultrametric space given by the boundary of the infinite dyadic tree, see  Self-similar dilatation structures and automata.

As a conclusion for this part, it seemed that  in order to unravel the abstract nonsense machine from the background, I needed to:

  • find a way to get rid of  mentioning metric spaces, so in particular to get rid of decorations of the leaves of binary trees by points in in some space, (or maybe use these decorations as a kind of names)
  • express this proof based on moves applied to binary trees as a computation, (i.e. as something like a reduction procedure).

Otherwise said, there was a need for a kind of logic, but which one?


16 thoughts on “A roadmap to computing with space”

    1. Thanks! I shall look closer, that’s new for me (Peirce? I like that). I arrived eventually to a formalism which I call “graphic lambda calculus”, see the tutorial page on this blog.
      The example I give in the post is in fact the proof that the operation of addition of tangent vectors at the point x is associative. Apparently it has nothing to do with logic, or at least for a geometer who is naive in logic, like most of us geometers. (As a side notice, one cannot prove that the said operation is commutative, in fact it’s not, unless one introduces the barycentric move. In general, the operation is non-commutative but nilpotent, in the realm of Lie groups.)

      1. The other name for it would be Differential Geometry Over GF(2). Naturally, there a many weird things that happen in that characteristic, but it’s not as bad as many people think.

        There are connections to Combinators and Lambda Calculus via the Propositions As Types analogy. See the link further down on that Bib page.

      2. Thank you, it looks very interesting, maybe we can do things together. (I want to avoid the situation from a short story, I forgot the author(s), maybe Strugatsky brothers, where there’s a research institute where everybody has an amazing theory to communicate but everybody wants others to listen and nobody wants to just listen. The situation out of this is maybe to do both, in time.)

        What is GF(2)? Link please? I see that’s Z/2Z. Can you pass to other finite fields?

    1. No, Chow-Rashevskii says basically that if you have a finite collection of vectorfields in a real n dimensional manifold with the property that they produce by repeated brackets n vectorfields which are independent when evaluated in each point of the manifold (and moreover the dimensions of the spaces generated in each tangent space by the vectorfields produced in the intermediary steps are constant wrt base points) then you may join any two sufficiently closed points by a curve which is almost everywhere tangent to a linear combination of the initial vectorfields. Otherwise said, the group generated by the flows associated to those initial vectorfields is (locally) transitive. In my treatment of sub-riemannian geometry I use a hypothesis which is a discretisation of this transitivity, so I use the conclusion of the Chow-Rashevskii. The hypothesis of this theorem is expressed in terms of brackets of vectorfields and that is a problem because that is an operation which produces a loss of regularity, a priori, so it may happen that in low regularity you cannot repeat it. Moreover, brackets (as well as Lie brackets) are commutative objects for me, they make no sense by the classical definition. On the classical front, Sergei Vodopyanov from the Sobolev Institute worked on such generalizations for low regularity.

      1. … but mind you that I use this “Chow-Rashevskii as hypothesis” only to show that the rescaled length functional converges (in the variational sense) to the length functional in the tangent space. Dilation structures in their generality do not need any such hypothesis, see for example the case of ultrametric spaces mentioned in the post, where the CR theorem does not make any sense (because they are totally disconnected spaces).

      2. Btw, to finish with Chow-Rashevskii, the other name used for sub-riemannian spaces is “Carnot-Caratheodory” spaces. And that’s because Caratheodory, in his mathematical treatment of thermodynamics, proved the existence of entropy as a corollary of a theorem which is the contrapositive of Chow-Rashevskii theorem in the particular case of n-1 vectorfields.

      3. Apparently I cannot stop: this particular case of Chow-Rashevskii, i.e. the (contrapositive of the) Caratheodory case, have the name “contact manifold” and appears in geometric quantization of a symplectic manifold. The states of a bycicle form a sub-riemannian manifold (but not contact), if you have a bike which never slips. The conclusion of Chow-Rashevskii means in this case that you can park your bike in any position you like. The states of a qubit form a contact manifold, i.e. a qubit is a very special case of a sub-riemannian manifold, which is also a real projective space.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s