What’s the difference between uniform and coarse structures? (I)

See this, if you need: uniform structure and coarse structure.

Given a set $X$, endowed with an uniform structure or with a coarse structure, Instead of working with subsets of $X^{2}$, I prefer to think about the trivial groupoid $X \times X$.

Groupoids. Recall that a groupoid is a small category with all arrows invertible. We may define a groupoid in term of it’s collection of arrows, as follows: a set $G$ endowed with a partially defined operation $m: G^{(2)} \subset G \times G \rightarrow G$, $m(g,h) = gh$, and an inverse operation $inv: G \rightarrow G$, $inv(g) = g^{-1}$, satisfying some well known properties (associativity, inverse, identity).

The set $Ob(G)$ is the set of objects of the groupoid, $\alpha , \omega: G \rightarrow Ob(G)$ are the source and target functions, defined as:

– the source fonction is $\alpha(g) = g^{-1} g$,

– the target function is $\omega(g) = g g^{-1}$,

– the set of objects is $Ob(G)$ consists of all elements of $G$ with the form $g g^{-1}$.

Trivial groupoid. An example of a groupoid is $G = X \times X$, the trivial groupoid of the set $X$. The operations , source, target and objects are

$(x,y) (y,z) = (x,z)$, $(x,y)^{-1} = (y,x)$

$\alpha(x,y) = (y,y)$, $\omega(x,y) = (x,x)$,

– objects $(x,x)$ for all $x \in X$.

In terms of groupoids, here is the definition of an uniform structure.

Definition 1. (groupoid with uniform structure) Let $G$ be a groupoid. An uniformity $\Phi$ on $G$ is a set $\Phi \subset 2^{G}$ such that:

1. for any $U \in \Phi$ we have $Ob(G) \subset U$,

2. if $U \in \Phi$ and $U \subset V \subset G$ then $V \in \Phi$,

3. if $U,V \in \Phi$ then $U \cap V \in \Phi$,

4. for any $U \in \Phi$ there is $V \in \Phi$ such that $VV \subset U$,  where $VV$ is the set of all $gh$ with $g, h \in V$ and moreover $(g,h) \in G^{(2)}$,

5. if $U \in \Phi$ then $U^{-1} \in \Phi$.

Here is a definition for a coarse structure on a groupoid (adapted from the usual one, seen on the trivial groupoid).

Definition 2.(groupoid with coarse structure) Let $G$ be a groupoid. A coarse structure  $\chi$ on $G$ is a set $\chi \subset 2^{G}$ such that:

1′. $Ob(G) \in \chi$,

2′. if $U \in \chi$ and $V \subset U$ then $V \in \chi$,

3′. if $U,V \in \chi$ then $U \cup V \in \chi$,

4′. for any $U \in \chi$ there is $V \in \chi$ such that $UU \subset V$,  where $UU$ is the set of all $gh$ with $g, h \in U$ and moreover $(g,h) \in G^{(2)}$,

5′. if $U \in \chi$ then $U^{-1} \in \chi$.

Look pretty much the same, right? But they are not, we shall see the difference when we take into consideration how we generate such structures.

Question. Have you seen before such structures defined like this, on groupoids? It seems trivial to do so, but I cannot find this anywhere (maybe because I am ignorant).

UPDATE (01.08.2012): Just found this interesting paper  Coarse structures on groups, by Andrew Nicas and David Rosenthal, where they already did on groups something related to what I want to explain on groupoids. I shall be back on this.

Approximate groupoids may be useful

____________________________________

I appreciated yesterday the talk of Harald Helfgott, here is the link to the arxiv paper which was the subject of his communication: On the diameter of permutation groups (with Á. Seress).

At the end of his talk Harald stated as a conclusion that (if I well understood) the approximate groups field should be regarded as the study of

“stable configurations under the action of a group”

where “stable configuration” means a set (or a family…) with some controlled behaviour of its growth under the “action of a group”, understood maybe in a lax, approximate sense.

This applies to approximate groups, he said, where the action is by left translations, but it could apply to the conjugate action as well, and evenin  more general settings, where one has a space where a group acts.

My understanding of this bold claim is that Harald suggests that the approximate groups theory is a kind of geometry in the sense of Felix Klein: the (approximate, in this case) study of stable configuratiuons under the action of a group.

Today I just remembered a comment that I have made last november on the blog of Tao, where I proposed to study “approximate groupoids”.

Why is this related?

Because a group acting on a set is just a particular type of groupoid, an action groupoid.

Here is the comment (link), reproduced further.

“Question (please erase if not appropriate): as a metric space is just a particular example of a normed groupoid, could you point me to papers where “approximate groupoids” are studied? For starters, something like an extension of your paper “Product set estimates for non-commutative groups”, along the lines in the introduction “one also consider partial sum sets …”, could be relevant, but I am unable to locate any. Following your proofs could be straightforward, but lengthy. Has this been done?

For example, a $k$  approximate groupoid $A \subset G$ of a groupoid  $G$ (where $G$ denotes the set of arrows) could be a

(i)- symmetric subset of $G$: $A = A^{-1}$, for any $x \in Ob(G)$  $id_{x} \in A$  and

(ii)- there is another, symmetric subset $K \subset G$ such that for any   $(u,v) \in (A \times A) \cap G^{(2)}$  there are $(w,g) \in (A \times K) \cap G^{(2)}$  such that $uv = wg$,

(iii)- for any $x \in Ob(G)$  we have $\mid K_{x} \mid \leq k$.

One may replace the cardinal, as you did, by a measure (or random walk kernel, etc), or even by a norm.”

UPDATE (28.10.2012): Apparently unaware about the classical proof of Ronald Brown,  by way of groupoids, of the Van Kampen theorem on the fundamental group of a union of spaces, Terence Tao has a post about this subject. I wonder if he is after some applications of his results on approximate groups in the realm of groupoids.

Gromov on entropy and Souriau

Gromov just posted on his page the paper In a Search for a Structure, Part 1: On Entropy. June 19, 2012.   With much interest I started to read it and my first impression is that I have seen something like this before (but I might be wrong, please excuse me if so) in the HUGE last paper (book)

Grammaire de la nature (version du 8 juillet 2007)

by Jean-Marie Souriau, the inventor of symplectic geometry and geometric quantization, among others.

Specifically, I refer to  the way Souriau treats probabilities in “CLE 8: Calcul des Hasards”, p. 209.

The book is a must-read! It is a summum of Souriau mathematical view of Nature, specifically concerning symmetry, entropy, relativity and quantum mechanics.

Gromov, with his enormous geometrical knowledge (different than Souriau’ though)  points to sofic groups, this  I need a lot of time to understand.

UPDATE: I am starting to understand the sofic group notion of Gromov and learning to appreciate it, it’s related to constructions with approximate groups, apparently.

Intrinsic characterizations of riemannian and sub-riemannian spaces (I)

In this post I explain what is the problem of intrinsic characterization of riemannian manifolds, in what sense has been solved in full generality by Nikolaev, then I shall comment on the proof of the Hilbert’s fifth problem by Tao.

In the next post there will be then some comments about Gromov’s problem of giving an intrinsic characterization of sub-riemannian manifolds, in what sense I solved this problem by adding a bit of algebra to it. Finally, I shall return to the characterization of riemannian manifolds, seen as particular sub-riemannian manifolds, and comment on the differences between this characterization and Nikolaev’ one.

1. History of the problem for riemannian manifolds. The problem of giving an intrinsic characterization of riemannian manifolds is a classic and fertile one.

Problem: give a metric description of a Riemannian manifold.

Background: A complete riemannian manifold is a length metric space (or geodesic, or intrinsic metric space) by Hopf-Rinow theorem. The problem asks for the recovery of the manifold structure from the distance function (associated to the length functional).

For 2-dim riemannian manifolds the problem has been solved by A. Wald [Begrundung einer koordinatenlosen Differentialgeometrie der Flachen, Erg. Math. Colloq. 7 (1936), 24-46] (“Begrundung” with umlaut u, “Flachen” with umlaut a, sorry for this).

In 1948 A.D. Alexandrov [Intrinsic geometry of convex surfaces, various editions] introduces its famous curvature (which uses comparison triangles)  and proves that, under mild smoothness conditions  on this curvature, one is capable to recover the differential structure and the metric of the 2-dim riemannian manifold. In 1982 Alexandrov proposes as a conjecture that a characterization of a riemannian manifold (of any dimension) is possible in terms of metric (sectional) curvatures (of the type introduced by Alexandrov) and weak smoothness assumptions formulated in metric way (as for example Holder smoothness). Many other results deserve to be mentioned (by Reshetnyak, for example).

2. Solution of the problem by Nikolaev. In 1998 I.G. Nikolaev [A metric characterization of riemannian spaces, Siberian Adv. Math. , 9 (1999), 1-58] solves the general problem of intrinsic characterization of $C^{m,\alpha}$ riemannian spaces:

every locally compact length metric space $M$, not linear at one of its points,  with $\alpha$ Holder continuous metric sectional curvature of the “generalized tangent bundle” $T^{m}(M)$ (for some $m=1,2,…$, which admits local geodesic extendability, is isometric to a $C^{m+2}$ smooth riemannian manifold..

Therefore:

• he defines a generalized tangent bundle in metric sense
• he defines a notion of sectional curvature
• he asks some metric smoothness of this curvature

and he gets the result.

3. Gleason metrics and Hilbert’s fifth problem. Let us compare this with the formulation of the solution of the Hilbert’s fifth problem by Terence Tao. THe problem is somehow similar, namely recover the differential structure of a Lie group from its algebraic structure. This time the “intrinsic” object is the group operation, not the distance, as previously.

Tao shows that the proof of the solution may be formulated in metric terms. Namely, he introduces a Gleason metric (definition 4 in the linked post), which will turn to be a left invariant riemannian metric on the (topological) group. I shall not insist on this, instead read the post of Tao and also, for the riemannian metric description, read this previous post by me.

Rules of lambda epsilon calculus

I updated the paper on lambda epsilon calculus.  See the link to the actual version (updated daily) or check the arxiv article, which will be updated as soon as a stable version will emerge.

Here are the rules of this calculus:

(beta *)   $(x \lambda A) \varepsilon B= (y \lambda (A[x:=B])) \varepsilon B$ for any fresh variable $y$,

(R1) (Reidemeister one) if $x \not \in FV(A)$ then $(x \lambda A) \varepsilon A = A$

(R2) (Reidemeister two) if $x \not \in FV(B)$ then $(x \lambda ( B \mu x)) \varepsilon A = B (\varepsilon \mu ) A$

(ext1) (extensionality one)  if  $x \not \in FV(A)$ then $x \lambda (A 1 x) = A$

(ext2) (extensionality two) if  $x \not \in FV(B)$ then $(x \lambda B) 1 A = B$

These are taken together with usual substitution and $\alpha$-conversion.

The relation between the operations from $\lambda \varepsilon$ calculus and emergent algebras is illustrated in the next figure.

Lambda epsilon calculus, an attempt for a language of “computing with space”

Just posted on the arxiv the paper Lambda calculus combined with emergent algebras.   Also, I updated my page on emergent algebras and computing with space, taking into consideration what I try to do in the mentioned paper. Here are some excerpts (from the mentioned page) about what I think now “computing with space” may be:

 Let’s look at some examples of spaces, like: the real world or a virtual world of a game, as seen by a fly or by a human, “abstract” mathematical spaces as manifolds, fractals, symmetric spaces, groups, linear spaces. To know what a space is, to define it mathematically, is less interesting than to know what one can do in such a space. I try to look at spaces from a kind of a “computational viewpoint”. A model of such a computation could be the following process: Alice and Bob share a class of primitives of spaces (like a common language which Alice can use in order to communicate to Bob what she sees when exploring the unknown space). Alice explores an unknown territory and sends to Bob the operational content of the exploration (i.e. maps of what she sees and how she moves, expresses in the common language ). Then Bob, who is placed in a familiar space, tries to make sense of the maps received from Alice. Usually, he can’t put together in the familiar the received information (for example because there is a limit of accuracy of maps of the unknown territory into the familiar one). Instead, Bob tries to simulate the operational content of Alice exploration by interpreting the messages from Alice (remember, expressed in a language of primitives of space) in his space. A language of space primitives could be (or contain as a part) the emergent algebras. Ideally, such a language of primitives should be described by: A – a class of gates (operations), which represent the “map-making” relation, with an abstract scale parameter attached, maybe also with supplementary operations (like lambda abstraction?), B – a class of variables (names) which represent generic points of a space, and a small class of terms (words) expressed in terms of variables and gates from (A) (resembling to combinators in lambda calculus?). These are the “generators” of the space and they have the emergent algebras property, namely that as the scale goes to zero, uniformly with respect to the variables, the output converges to a new operation. C – a class of rewriting rules saying that some simple assemblies of generators of space have equivalent function, or saying that relations between those simple assemblies converge to relations of the space as the scale goes to zero.

The article on lambda epsilon calculus is a first for me in this field, I would be grateful for any comments and suggestions of improvements.

Three problems and a disclaimer

In this post I want to summarize the list of problems I am currently thinking about. This is not a list of regular mathematical problems, see the disclaimer on style written at the end of the post.

Here is the list:

1. what is “computing with space“? There is something happening in the brain (of a human or of a fly) which is akin to a computation, but is not a logical computation: vision. I call this “computing with space”. In the head there are a bunch of neurons chirping one to another, that’s all. There is no euclidean geometry, there are no a priori coordinates (or other extensive properties), there are no problems to solve for them neurons, there is  no homunculus and no outer space, only a dynamical network of gates (neurons and their connections). I think that a part of an answer is the idea of emergent algebras (albeit there should be something more than this).  Mathematically, a closely related problem is this: Alice is exploring a unknown space and then sends to Bob enough information so that Bob could “simulate” the space in the lab. See this, or this, or this.

Application: give the smallest hint of a purely relational  model of vision  without using any a priori knowledge of the (euclidean or other) geometry of outer space or any  pre-defined charting of the visual system (don’t give names to neurons, don’t give them “tasks”, they are not engineers).

2. non-commutative Baker-Campbell-Hausdorff formula. From the solution of the Hilbert’s fifth problem we know that any locally compact topological group without small subgroups can be endowed with the structure of a “infinitesimally commutative” normed group with dilations. This is true because  one parameter sub-groups  and Gleason metrics are used to solve the problem.  The BCH formula solves then another problem: from the infinitesimal structure of a (Lie) group (that is the vector space structure of the tangent space at the identity and the maniflod structure of the Lie group) and from supplementary infinitesimal data (that is the Lie bracket), construct the group operation.

The problem of the non-commutative BCH is the following: suppose you are in a normed group with dilations. Then construct the group operation from the infinitesimal data (the conical group structure of the tangent space at identity and the dilation structure) and supplementary data (the halfbracket).

The classical BCH formula corresponds to the choice of the dilation structure coming from the manifold structure of the Lie group.

In the case of a Carnot group (or a conical group), the non-commutative BCH formula should be trivial (i.e. $x y = x \cdot y$, the equivalent of $xy = x+y$ in the case of a commutative Lie group, where by convention we neglect all “exp” and “log” in formulae).

3. give a notion of curvature which is meaningful for sub-riemannian spaces. I propose the pair curvdimension- curvature of a metric profile. There is a connection with problem 1: there is a link between the curvature of the metric profile and the “emergent Reidemeister 3 move” explained in section 6 of the computing with space paper. Indeed, at page 36 there is this figure. Yes, $R^{x}_{\epsilon \mu \lambda} (u,v) w$ is a curvature!

Disclaimer on style. I am not a problem solver, in the sense that I don’t usually like to find the solution of an already formulated problem. Instead, what I do like to do is to understand some phenomenon and prove something about it in the simplest way possible.  When thinking about a subject, I like to polish the partial understanding I have by renouncing to use any “impure” tools, that is any (mathematical) fact which is strange to the subject. I know that this is not the usual way of doing the job, but sometimes less is more.