Tag Archives: approximate structures

How not to get bored, by reading Gromov and Tao

This is a continuation of the previous post Gromov’s ergobrain, triggered by the update of Gromov paper on July 27. It is also related to the series of posts by Tao on the Hilbert’s fifth problem.

To put you in the right frame of mind, both Gromov and Tao set the stage for upcoming, hopefully extremely interesting (or “beautiful” on Gromov’s scale: interesting, amusing, amazing, funny and beautiful) developments of their work on “ergosystems” and “approximate groups” respectively.

What can be the link between those? In my opinion, both works refer to the unexplored ground between discrete (with not so many elements) and continuous (or going to the limit with the number of elements of a discrete world).

Indeed, along with my excuses for simplifying too much a very rich text, let me start with the example of the bug on a leaf, sections 2.12, 2.13 in Gromov’s paper). I understand that the bug, as any other “ergosystem” (like one’s brain) would get bored to behave like a finite state automaton crawling on a “co-labeled graph” (in particular on a Cayley graph of a discretely generated group). The implication seems to be that an ergosystem has a different behaviour.

I hardly refrain to copy-paste the whole page 96 of Gromov’s paper, please use the link and read it instead, especially the part related to downsides of Turing modeling (it is not geometrical, in few words). I shall just paste here the end:

The two ergo-lessons one may draw from Turing models are mutually contradictory.
1. A repeated application of a simple operation(s) may lead to something unexpectedly complicated and interesting.
2. If you do not resent the command “repete” and/or are not getting bored by doing the same thing over and over again, you will spend your life in a “Turing loop” of an endless walk in a circular tunnel.

That is because the “stop-function” associated to a class of Turing machines

may grow faster than anything you can imagine, faster than anything expressible by any conceivable formula – the exponential and double exponential functions that appeared so big to you seem as tiny specks of dust compared to this monstrous stop-function. (page 95)

Have I said “Cayley graph”? This brings me to discrete groups and to the work of Tao (and Ben Green and many others). According to Tao, there is something to be learned from the solution of the Hilbert’s fifth problem, in the benefit of understanding approximate groups. (I am looking forward to see this!) There are some things that I understood from the posts of Tao, especially that a central concept is a Gleason metric and its relations with group commutators. In previous posts (last is this) I argue that Gleason metrics are very unlike sub-riemannian distances. It has been unsaid, but obvious to specialists, that sub-riemannian metrics are just like distances on Cayley graphs, so as a consequence Gleason metrics are only a commutative “shadow” of what happens in a Cayley graph when looked from afar. Moreover, in this post concerning the problem of a non-commutative Baker-Campbell-Hausdorff formula it is said that (in the more general world of groups with dilations, relevant soon in this post) the link between the Lie bracket and group commutators is shallow and due to the commutativity of the group operation in the tangent space.

So let me explain, by using Gromov’s idea of boredom, how not to get bored in a Cayley graph. Remember that I quoted a paragraph (from Gromov paper, previous version), stating that an ergosystem “would be bored to death” to add large numbers? Equivalently, an ergosystem would be bored to add (by using the group operation) elements of the group expressed as very long words with letters representing the generators of the group. Just by using “finite state automata” type of reasoning with the relations between generators (expressed by commutators and finitary versions of Gleason like metrics) an ergosystem would get easily bored. What else can be done?

Suppose that we crawl in the Cayley graph of a group with polynomial growth, therefore we know (by a famous result of Gromov) that seen from afar the group is a nilpotent one, more precisely a group with the algebraic structure completely specified by its dilations. Take one such dilation, of coefficient 10^{-30} say, and (by an yet unknown “finitization” procedure) associate to it a “discrete shadow”, that is an “approximate dilation” acting on the discrete group itself. As this is a genuinely non-commutative object, probably the algorithm for defining it (by using relations between growth and commutators) would be very much resource consuming. But suppose we just have it, inferred from “looking at the forrest” as an ergosystem.

What a great object would that be. Indeed, instead of getting bored by adding two group elements, the first expressed as product of 200034156998123039234534530081 generators, the second expressed as a product of 311340006349200600380943586878 generators, we shall first reduce the elements (apply the dilation of coefficient 10^{-30}) to a couple of elements, first expressed as a product of 2 generators, second expressed as a product of 3 generators, then we do the addition 2+3 = 5 (and use the relations between generators), then we use the inverse dilation (which is a dilation of coefficient 10^{30}) to obtain the “approximate sum” of the two elements!

In practice, we probably have a dilation of coefficient 1/2 which could simplify the computation of products of group elements of length 2^{4} at most, for example.

But it looks like a solution to the problem of not getting bored, at least to me.

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.

Escape property of the Gleason metric and sub-riemannian distances again

The last post of Tao from his series of posts on the Hilbert’s fifth problem contains interesting results which can be used for understanding the differences between Gleason distances and sub-riemannian distances or, more general, norms on groups with dilations.

For normed groups with dilations see my previous post (where links to articles are also provided). Check my homepage for more details (finally I am online again).

There is also another post of mine on the Gleason metric (distance) and the CC (or sub-riemannian) distance, where I explain why the commutator estimate (definition 3, relation (2) from the last post of Tao) forces “commutativity”, in the sense that a sub-riemannian left invariant distance on a Lie group which has the commutator estimate must be a riemannian distance.

What about the escape property (Definition 3, relation (1) from the post of Tao)?

From his Proposition 10 we see that the escape property implies the commutator estimate, therefore a sub-riemannian left invariant distance with the escape property must be riemannian.

An explanation of this phenomenon can be deduced by using the notion of “coherent projection”, section 9 of the paper

A characterization of sub-riemannian spaces as length dilation structures constructed via coherent projections, Commun. Math. Anal. 11 (2011), No. 2, pp. 70-111

in the very particular case of sub-riemannian Lie groups (or for that matter normed groups with dilations).

Suppose we have a normed group with dilations (G, \delta) which has another left invariant dilation structure on it (in the paper this is denoted by a “\delta bar”, here I shall use the notation \alpha for this supplementary dilation structure).

There is one such a dilation structure available for any Lie group (notice that I am not trying to give a proof of the H5 problem), namely for any \varepsilon > 0 (but not too big)

\alpha_{\varepsilon} g = \exp ( \varepsilon \log (g))

(maybe interesting: which famous lemma is equivalent with the fact that (G,\alpha) is a group with dilations?)
Take \delta to be a dilation structure coming from a left-invariant distribution on the group . Then \delta commutes with \alpha and moreover

(*) \lim_{\varepsilon \rightarrow 0} \alpha_{\varepsilon}^{-1} \delta_{\varepsilon} x = Q(x)

where Q is a projection: Q(Q(x)) = x for any x \in G.

It is straightforward to check that (the left-translation of) Q (over the whole group) is a coherent projection, more precisely it is the projection on the distribution!

Exercise: denote by \varepsilon = 1/n and use (*) to prove that the escape property of Tao implies that Q is (locally) injective. This implies in turn that Q = id, therefore the distribution is the tangent bundle, therefore the distance is riemannian!

UPDATE:    See the recent post 254A, Notes 4: Bulding metrics on groups, and the Gleason-Yamabe theorem by Terence Tao, for understanding in detail the role of the escape property in the proof of the Hilbert 5th problem.

Gleason metric and CC distance

In the series of posts on Hilbert’s fifth problem, Terence Tao defines a Gleason metric, definition 4 here, which is a very important ingredient of the proof of the solution to H5 problem.

Here is Remark 1. from the post:

The escape and commutator properties are meant to capture “Euclidean-like” structure of the group. Other metrics, such as Carnot-Carathéodory metrics on Carnot Lie groups such as the Heisenberg group, usually fail one or both of these properties.

I want to explain why this is true. Look at the proof of theorem 7. The problem comes from the commutator estimate (1). I shall reproduce the relevant part of the proof because I don’t yet know how to write good-looking latex posts:

From the commutator estimate (1) and the triangle inequality we also obtain a conjugation estimate

\displaystyle  \| ghg^{-1} \| \sim \|h\|

whenever {\|g\|, \|h\| \leq \epsilon}. Since left-invariance gives

\displaystyle  d(g,h) = \| g^{-1} h \|

we then conclude an approximate right invariance

\displaystyle  d(gk,hk) \sim d(g,h)

whenever {\|g\|, \|h\|, \|k\| \leq \epsilon}.

The conclusion is that the right translations in the group are Lipschitz (with respect to the Gleason metric). Because this distance (I use “distance” instead of “metric”) is also left invariant, it follows that left and right translations are Lipschitz.

Let now G be a connected Lie group with a left-invariant distribution, obtained by left translates of a vector space D included in the Lie algebra of G. The distribution is completely non-integrable if D generates the Lie algebra by using the + and Lie bracket operations. We put an euclidean norm on D and we get a CC distance on the group defined by: the CC distance between two elements of the group equals the infimum of lengths of horizontal (a.e. derivable, with the tangent in the distribution) curves joining the said points.

The remark 1 of Tao is a consequence of the following fact: if the CC distance is right invariant then D equals the Lie algebra of the group, therefore the distance is riemannian.

Here is why: in a sub-riemannian group (that is a group with a distribution and CC distance as explained previously) the left translations are Lipschitz (they are isometries) but not all right translations are Lipschitz, unless D equals the Lie algebra of G. Indeed, let us suppose that all right translations are Lipschitz. Then, by Margulis-Mostow version (see also this) of the Rademacher theorem , the right translation by an element “a” is Pansu derivable almost everywhere. It follows that the Pansu derivative of the right translation by “a” (in almost every point) preserves the distribution. A simple calculus based on invariance (truly, some explanations are needed here) shows that by consequence the adjoint action of “a” preserves D. Because “a” is arbitrary, this implies that D is an ideal of the Lie algebra. But D generates the Lie algebra, therefore D equals the Lie algebra of G.

If you know a shorter proof please let me know.

UPDATE: See the recent post 254A, Notes 4: Bulding metrics on groups, and the Gleason-Yamabe theorem by Terence Tao, for details of the role of the Gleason metric  in the proof of the Hilbert 5th problem.

A difference which makes four differences, in two ways

Gregory Bateson , speaking about the map-territory relation

“What is in the territory that gets onto the map? […] What gets onto the map, in fact, is difference.

A difference is a very peculiar and obscure concept. It is certainly not a thing or an event. This piece of paper is different from the wood of this lectern. There are many differences between them, […] but if we start to ask about the localization of those differences, we get into trouble. Obviously the difference between the paper and the wood is not in the paper; it is obviously not in the wood; it is obviously not in the space between them .

A difference, then, is an abstract matter.

Difference travels from the wood and paper into my retina. It then gets picked up and worked on by this fancy piece of computing machinery in my head.

… what we mean by information — the elementary unit of information — is a difference which makes a difference.

(from “Form, Substance and Difference”, Nineteenth Annual Korzybski Memorial
Lecture delivered by Bateson on January 9, 1970, under the auspices of the Institute of General Semantics, re-printed from the General Semantics Bulletin, no.
37, 1970, in Steps to an Ecology of Mind (1972))

This “difference which makes a difference” statement is quite famous, although sometimes considered only a figure of speach.

I think it is not, let me show you why!

For me a difference can be interpreted as an operator which relates images of the same thing (from the territory) viewed in two different maps, like in the following picture:

This figure is taken from “Computing with space…” , see section 1 “The map is the territory” for drawing conventions.

Forget now about maps and territories and concentrate on this diagram viewed as a decorated tangle. The rules of decorations are the following: arcs are decorated with “x,y,…”, points from a space, and the crossings are decorated with epsilons, elements of a commutative group (secretly we use an emergent algebra, or an uniform idempotent right quasigroup, to decorate arcs AND crossings of a tangle diagram).

What we see is a tangle which appears in the Reidemeister move 3 from knot theory. When epsilons are fixed, this diagram defines a function called (approximate) difference.

Is this a difference which makes a difference?

Yes, in two ways:

1. We could add to this diagram an elementary unknot passing under all arcs, thus obtaining the diagram

Now we see four differences in this equivalent tangle: the initial one is made by three others.
The fact that a difference is selfsimilar is equivalent with the associativity of the INVERSE of the approximate difference operation, called approximate sum.

2. Let us add an elementary unknot over the arcs of the tangle diagram, like in the following figure

called “difference inside a chora” (you have to read the paper to see why). According to the rules of tangle diagrams, adding unknots does not change the tangle topologically (although this is not quite true in the realm of emergent algebras, where the Reidemeister move 3 is an acceptable move only in the limit, when passing with the crossing decorations to “zero”).

By using only Reidemeister moves 1 and 2, we can turn this diagram into the celtic looking figure

which shows again four differences: the initial one in the center and three others around.

This time we got a statement saying that a difference is preserved under “infinitesimal parallel transport”.

So, indeed, a difference makes four differences, in at least two ways, for a mathematician.

If you want to understand more from this crazy post, read the paper 🙂

Rigidity of algebraic structure: principle of common cause

I follow with a lot of interest the stream of posts by Terence Tao on the Hilbert’s fifth problem and I am waiting impatiently to see how it connects with the field of approximate groups.

In his latest post Tao writes that

… Hilbert’s fifth problem is a manifestation of the “rigidity” of algebraic structure (in this case, group structure), which turns weak regularity (continuity) into strong regularity (smoothness).

This is something amazing and worthy of exploration!
I propose the following “explanation” of this phenomenon, taking the form of the:

Principle of common cause: an uniformly continuous algebraic structure has a smooth structure because both structures can be constructed from an underlying emergent algebra (introduced here).

Here are more explanations (adapted from the first paper on emergent algebras):

A differentiable algebra, is an algebra (set of operations A) over a manifold X with the property that all the operations of the algebra are differentiable with respect to the manifold structure of X. Let us denote by D the differential structure of the manifold X.
From a more computational viewpoint, we may think about the calculus which can be
done in a differentiable algebra as being generated by the elements of a toolbox with two compartments “A” and “D”:

– “A” contains the algebraic information, that is the operations of the algebra, as
well as algebraic relations (like for example ”the operation ∗ is associative”, or ”the operation ∗ is commutative”, and so on),
– “D” contains the differential structure informations, that is the information needed in order to formulate the statement ”the function f is differentiable”.
The compartments “A” and “D” are compatible, in the sense that any operation from “A” is differentiable according to “D”.

I propose a generalization of differentiable algebras, where the underlying differential structure is replaced by a uniform idempotent right quasigroup (irq).

Algebraically, irqs are related with racks and quandles, which appear in knot theory (the axioms of a irq correspond to the first two Reidemeister moves). An uniform  irq is a family of irqs indexed by elements of a commutative group (with an absolute), such that  the third Reidemeister move is related to a statement in terms of uniform limits of composites of operations of the family of irqs.

An emergent algebra is an algebra A over the uniform irq X such that all operations and algebraic relations from A can be constructed or deduced from combinations of operations in the uniform irq, possibly by taking limits which are uniform with respect to a set of parameters. In this approach, the usual compatibility condition between algebraic information and differential information, expressed as the differentiability of algebraic operations with respect to the differential structure, is replaced by the “emergence” of algebraic operations and relations from the minimal structure of a uniform irq.

Thus, for example, algebraic operations and the differentiation operation (taking   the triple (x,y,f) to Df(x)y , where “x, y” are  points and “f” is a function) are expressed as uniform limits of composites of more elementary operations. The algebraic operations appear to be differentiable because of algebraic abstract nonsense (obtained by exploitation of the Reidemeister moves) and because of the uniformity assumptions which allow us to freely permute limits with respect to parameters in the commutative group (as they tend to the absolute), due to the uniformity assumptions.

Hilbert fifth’s problem without one parameter subgroups

Further I reproduce, with small modifications, a comment   to the post

Locally compact groups with faithful finite-dimensional representations

by Terence Tao.

My motivation lies in the  project   described first time in public here.  In fact, one of the reasons to start this blog is to have a place where I can leisurely explain stuff.

Background:    The answer to the  Hilbert fifth’s problem  is: a connected locally compact group without small subgroups is a Lie group.

The key idea of the proof is to study the space of one parameter subgroups of the topological group. This space turns out to be a good model of the tangent space at the neutral element of the group (eventually) and the effort goes towards turning upside-down this fact, namely to prove that this space is a locally compact topological vector space and the “exponential map”  gives a chart  of  (a neighbourhood of the neutral element of ) the group into this space.

Because I am a fan of differential structures   (well, I think they are only the commutative, boring side of dilation structures  or here or emergent algebras)   I know a situation when one can prove the fact that a topological group is a Lie group without using the one parameter subgroups!

Here starts the original comment, slightly modified:

Contractive automorphisms may be as relevant as one-parameter subgroups for building a Lie group structure (or even more), as shown by the following result from E. Siebert, Contractive Automorphisms on Locally Compact Groups, Math. Z. 191, 73-90 (1986)

5.4. Proposition. For a locally compact group G the following assertions are equivalent:
(i) G admits a contractive automorphism group;
(ii) G is a simply connected Lie group whose Lie algebra g admits a positive graduation.

The corresponding result for local groups is proved in L. van den Dries, I. Goldbring, Locally Compact Contractive Local Groups, arXiv:0909.4565v2.

I used Siebert result for proving the Lie algebraic structure of the metric tangent space to a sub-riemannian manifold in M. Buliga, Infinitesimal affine geometry of metric spaces endowed with a dilatation structure, Houston Journal of Mathematics, 36, 1 (2010), 91-136. arXiv:0804.0135v2

(added here: see  in Corollary 6.3 from “Infinitesimal affine …” paper, as well as Proposition 5.9 and Remark 5.10 from the paper  A characterization of sub-riemannian spaces as length dilation structures constructed via coherent projections, Commun. Math. Anal. 11 (2011), No. 2, pp. 70-111 , arXiv:0810.5042v4 )

When saying that contractive automorphisms, or approximately contractive automorphisms [i.e. dilation structures], may be more relevant than one-parameter subgroups, I am thinking about sub-riemannian geometry again, where a one-parameter subgroup of a group, endowed with a left-invariant distribution and a corresponding Carnot-Caratheodory distance, is “smooth” (with respect to Pansu-type derivative) if and only if the generator is in the distribution. Metrically speaking, if the generator  is not in the distribution then any trajectory of the one-parameter group has Hausdorff dimension greater than one. That means lots of problems with the definition of the exponential and any reasoning based on differentiating flows.