Let’s use the zipper

I shall use the zipper macro for improving  upon the computation done in “Emergent sums and differences in graphic lambda calculus”  as an example of computation in graphic lambda calculus.

We have to glue the following graphs, by respecting the red labels


in order to obtain the graph which is the subject of manipulation in  the mentioned post:


Zippers are for this. We shall use a 4-zipper.


I shall let you glue all graphs in the right places indicated by the red labels. It is funny to see here a mixture of lambdas, applications and emergent algebras dilation gates.

Peer-review is Cinderella’s lost shoe

Scientific publishers are in some respects like Cinderella. They used to provide an immense service to the scientific world, by disseminating  new results and archiving old results into books. Before the internet era, like Cinderella at the ball, they were everybody’s darling.

Enters the net. At the last moment, Cinderella tries to run from this new, strange world.


(image taken from here)

Cinderella does not understand  what happened so fast. She was used with the scarcity (of economic goods), to the point that she believed everything will be like this all her life!

What to do now, Cinderella? Will you sell open access for gold? [UPDATE: or will you apeal to court?]


(image found here)

But wait! Cinderella forgot something. Her lost shoe, the one she discarded when she ran out from the ball.

In the scientific publishers world, peer-review is the lost shoe. (As well, we may say that up to now, researchers who are writing peer-reviews are like Cinderella too, their work is completely unrewarded and neglected.)

In the internet era the author of a scientific research paper is free to share his results with the scientific world by archiving a preprint version of her/his paper in free access repositories.  The author, moreover, HAS to do this  because the net offers a much better dissemination of results than any old-time publisher. In order (for the author’s ideas) to survive, making a research paper scarce by constructing pay-walls around it is clearly a very bad idea.  The only thing which the gold open access  does better than green open access is that the authors pay the publisher for doing the peer review (while in the case of arxiv.org, say, the archived articles are not peer-reviewed).

Let’s face it: the publisher cannot artificially make scarce the articles, it is a bad idea. What a publisher can do, is to let the articles to be free and to offer the peer-review service.

Like Cinderella’s lost shoe, in this moment the publisher throws away the peer-reviews (made gratis by fellow researchers) and tries to sell the article which has acceptable peer-review reports.

Why not the inverse? The same publisher, using the infrastructure it has, may try to sell the peer-review reports of freely archived articles AFTER. There is a large quantity of articles which are freely available, in open access repositories like arxiv.org. They are “published” already, according to the new rules of the game. Only that they are not reviewed.

Let the publishers do this! It would be a service that is needed, contrary to the dissemination of knowledge service which is clearly obsolete. (See also Peer-review turned on its head has market value.)

Emergent sums and differences in graphic lambda calculus

See the page Graphic lambda calculus for background.

Here I want to discuss the treatment of one identity concerning approximate sums and differences in emergent algebras. The identity is the following:

\Delta^{x}_{\varepsilon}(u, \Sigma^{x}_{\varepsilon}(u,v)) = v

The approximate sum (maybe emergent sum would be a better name) \Sigma^{x}_{\varepsilon}(u,w) has the following associated graph in $GRAPH$:


The letters in red “x, u, w, \Sigma” are there only for the convenience of the reader.

Likewise, the graph in GRAPH which corresponds to the approximate difference (or emergent difference) \Delta^{x}_{\varepsilon}(u,w) is the following:


The graph which corresponds to \Delta^{x}_{\varepsilon}(u, \Sigma^{x}_{\varepsilon}(u,v)) is this one:


By a succession of CO-ASSOC moves we arrive to this graph:


We are ready to apply an R2 move to get:


We use now an ext2 move at the node marked by “1”


followed by local pruning


Here comes the funny part! We cannot continue unless we work with a graph where at the edges marked by the red letters “x, u” we put two disjoint (not connected by edges) graphs in GRAPH, say X, U:


Let us suppose that from the beginning we had X, U connected at the edges marked by the red letters x, u, and proceed further. My claim is that by three  GLOBAL FAN-OUT  moves we can make the following move


We use this move and we obtain:


As previously, we use an R2 move and another ext2 move to finally obtain this:


which is the answer we were looking for. We could use GLOBAL PRUNING to get rid of the part of the graph which ends by a termination gate.

Approximate groupoids again

This post is for future (google) reference for my project of relating approximate groups with emergent algebras. I would appreciate any constructive comment which could validate (or invalidate) this path of research.

Here is the path I would like to pursue further. The notion of approximate groupoid (see here for the definition) is not complete, because it is flattened, i.e. the set of arrows K should be seen as a set of variables. What I think is that the correct notion of approximate groupoid is a polynomial functor over groupoids (precisely a specific family of such functors). The category Grpd is cartesian closed,  so it has an associated model of (typed) lambda calculus. By using this observation I could apply emergent algebra techniques (under the form of my graphic lambda calculus, which was developed with — and partially funded by —  this application in mind) to approximate groupoids and hope  to obtain streamlined proofs of Breuillard-Green-Tao type results.

The origin of emergent algebras

In the last section “Why is the tangent space a group?” (section 8) of the great article by A. Bellaiche, The tangent space in sub-riemannian geometry*, the author explains a very interesting story, where names of Gromov and Connes appear, which is the first place, to my knowledge, where the idea of emergent algebras appear.

In a future post I shall comment more consistently on the math, but this time let me give you the relevant passages.

[p. 73] “Why is the tangent space a group at regular points? […] I have been puzzled by this question. Drawing a Lie algebra from the bracket structure of some X_{i}‘s did not seem to me the appropriate answer. I remember having, at last, asked M. Gromov about it (1982). The answer came under the form of a little apologue:

Take a map f: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}. Define its differential as

(79)              D_{x} f(u) = \lim_{\varepsilon \rightarrow 0} \varepsilon^{-1} \left[ f(x+\varepsilon u) - f(x) \right],

provided convergence holds. Then D_{x}f is certainly homogeneous:

D_{x}f(\lambda u) = \lambda D_{x}f(u),

but it need not satisfy the additivity condition

D_{x}f(u+v) = D_{x}f(u) + D_{x}f(v).

[…] However, if the convergence in (79)  is uniform on some neghbourhood of (x,0)  […]  then D_{x}f is additive, hence linear. So, uniformity was the key. The tangent space at p is a limit, in the [Gromov-]Hausdorff sense, of pointed spaces […] It certainly is a homogeneous space — in the sense of a metric space having a 1-parameter group of dilations. But when the convergence is uniform with respect to p, which is the case near regular points, in addition, it is a group.

Before giving the proof, I want to tell of another, later, hint, coming from the work of A. Connes. He has made significant use of the following observation: The tangent bundle TM to a differentiable manifold M is, like M \times M, a groupoid. […] In fact TM is simply a union of groups. In [8], II.5, it is stated that its structure may be derived from that of M \times M by blowing up the diagonal in M \times M. This suggests that, putting metrics back into the picture, one should have

(83)          TM = \lim_{\varepsilon \rightarrow 0} \varepsilon^{-1} (M \times M)

[…] in some sense to be made precise.

There is still one question. Since the differentiable structure of our manifold is the same as in Connes’ picture, why do we not get the same abelian group structure? One can answer: The differentiable structure is strongly connected to (the equivalence class of) Riemannian metrics; differentiable maps are locally Lipschitz, and Lipschitz maps are almost everywhere differentiable. There is no such connection between differentiable maps and the metric when it is sub-riemannian. Put in another way, differentiable maps have good local commutation properties with ordinary dilations, but not with sub-riemannian dilations \delta_{\lambda}.

So, one should not be abused by (83) and think that the algebraic structure of T_{p}M stems from the absolutely trivial structure of M \times M! It is concealed in dilations, as we shall now prove.

*) in the book Sub-riemannian geometry, eds. A. Bellaiche, J.-J. Risler, Progress in Mathematics 144, Birkhauser 1996

One more argument for open access publication

… and why some scientists might dislike it.


The “fugitive idiot” is inspired by Clifford Truesdell book “An Idiot’s Fugitive Essays on Science: Methods, Criticism, Training, Circumstances”, Springer-Verlag, 1984, which is a must-read for the history of classical thermodynamics, in particular.

Extensionality in graphic lambda calculus

This is part of the Tutorial:Graphic lambda calculus.

I want to discuss here the introduction of extensionality in the graphic lambda calculus. In some sense, extensionality is already present in the emergent algebra moves. Have you noticed the move “ext2”?

However, the eta-reduction from untyped lambda calculus needs a new move. I called it the ext1 move in arXiv:1207.0332 [cs.LO] paragraph 2.7. It is a global move, because in order to use it one has to check a global condition (without bound on the number of nodes and edges involved in the condition). In the mentioned paper I stated that the move applies only to graphs  which represent lambda calculus terms, but now I see no reason why it has to be confined to this sector, therefore here I shall formulate the ext1 move in more generality.

Move ext1.  If there is no oriented path from “2” to “1” outside the left hand side picture then one may replace this picture by an edge. Conversely, if there is no oriented path connecting “2” with “1” then one may replace the edge with the graph from the left hand side of the following picture:


This move acts like eta-reduction when translated back from graphs to lambda calculus terms. “Ext” comes from “extensionality”.

Let us see why we need to formulate the move like this. Suppose that we eliminate the global condition  “there is no oriented path from “2” to “1” outside the left hand side  of the previous picture”. In particular let us suppose that there is an edge from “2” to “1” which completes the graphs from the LHS of the previous picture. For this graph, which appears at left in the next figure, we may use the graphic beta move like this (numbers in red indicate how we use the graphic beta move):


If we could apply the ext 1 move to this graph, then the result would be the following:


Not only the result of this move is one loop, but it is the “wrong” loop, in the sense that this loop is obtained by closing the edge which vanishes in thin air when the graphic beta move is applied. There is no contradiction though, unless we wish to decorate the edges (i.e. to evaluate the result of the computation). It is just strange.

There is one question left: why the move called “ext2”, which is one of the emergent algebra moves, is also an extensionality move? A superficial answer is that the move ext2 says that the dilation of coefficient “1” is the identity function.


Return to Tutorial:Graphic lambda calculus