The EM term rewrite system repository

I just opened the GitHub repository EM, which contains work for the EM (emergent algebras) term rewrite system. It is an article (pdflatex), at this moment (22-05-2018) has about 20 pages, about 1/5 of the work done. I welcome and encourage everybody to contribute, review, etc. Maybe, I don’t know, we can produce collaboratively something better than I can do alone. All contributions will be acknowledged, consistent contributions will lead to co-authorship.

Please comment here, for more informal discussions. You can send me a direct mail, you can open issues at the repository and, the best and the most rigorous: pull requests.

There is a lot of accumulated work, there are many questions. This is part of the final goal to unite (articles, proofs, programs) into a string of repositories chemlambda, needs, em (for the moment).

Advertisements

Groups are numbers (2). Pattern matching

As in divination, pattern matching. Continues from Groups are numbers (1).

We start from elementary variables, then we define number terms by two operations: substraction and multiplication.

accept_0_0

  • Variables are terms.
  • Substraction (the first line): a is a variable and b is a term, then a-b is a term.
  • Multiplication (2nd line): a, b are terms, then ab is a term.

 

By pattern matching we can prove for example this:

accept_4

[update: figure replaced, the initial one was wrong by pattern matching only. The difference is that in this correct figure appears “(a-b)d” instead of the wrong “d(a-b)”]

What does it mean? These are just binary trees. Well let’s take a typing convention

accept_0_1

where e, x, … are elements of a vector space and the variables are invertible scalars. Moreover take e = 0 for simplicity.

Then the previous pattern matching dream says that

(1-(a-b))c x + (a-b)(c-d) x = (c - (a-b)d)x

which is true, but from all the irrelevant reasons (vector space, associativity and commutativity  of addition, distributivity, etc):

(c- ac + bc + ac -ad - bc + bd) x = (c - ad + bd) x = (c - (a-b)d)x 

What about this one, which is also by pattern matching:

accept_5

With the previous typing conventions it reads:

(c-(a-b))x = (1-b)(c-a)x + b(1- a^{-1})(c-a) x + (bc a^{-1})x

which is true because the right hand side is:

((1-b)(c-a) + b(1- a^{-1})(c-a) + bc a^{-1} )x =

= (c-a-bc+ab+bc-ab-bca^{-1} +b+bc a^{-1}) x = (c-a+b) x = (c-(a-b))x

Which is funny because it does not make any sense.

Groups are numbers (1), the shuffle trick and brackets

What I call the shuffle trick is this rewrite. It involves, at left, a pattern of 3 decorated nodes, with 5 ports (the root and 1, 2, 3, 4). At the right there is almost the same pattern, only that the decorations of the nodes changed and the ports 2, 3 are shuffled.

shuffle_1

I have not specified what is the orientation of the edges, nor what the decorations (here the letters “a”, “b”) are. As previously with chemlambda or emergent algebras, these graphs are in the family of trivalent oriented ribbon graphs. You can find them everywhere, in physics, topology, knot theory or interaction graphs. Usually they are defined as a pair of two permutations, A and B, over the set of “half-edges” (which are really half edges). The permutation A has the property that AAA=id and the orbits of A are the nodes of the graph. Translated, this gives a circular order of the edges incident to a node. The permutation B is such that BB=id and the orbits are the unoriented edges. Indeed, an edge is made by to half edges. The orientation of the edges is made by picking one of the half edges which make an edge, or equivalently by replacing the set of two half edges, say half-edge and B(half-edge), by a list of the two half edges.

I prefer though another description of these graphs, by using sticks and rings, or, just the same, by using a partially defined SUCC function (which defines the sticks or rings) and a GLUE permutation with GLUE GLUE = id. That is why I use behind the description of the chemlambda strings and what you can grasp by looking at the needs repository.

With the sticks and rings notation, here is an example of the shuffle trick:

shuffle

The shuffle trick is very important in chemlambda. It is this one, in a static diagram. You see that the decoration of the nodes are “FO” and “FOE” and that actually, in chemlambda, this is achieved via two rewrites.

shuffle_2

More about the chemlambda shuffle trick in the all-in-one illustrated shuffle trick post. where is explain why the shuffle trick is so important for duplication. An animation taken from there is this one, the dynamical version of the previous static picture. [The molecule used is this, you can see it live here.]

shuffle

But the shuffle trick is relevant to emergent algebras as well. This time we play with oriented binary trees, with nodes which can be white or black, decorated with “a”, “b” from a commutative group. To refresh a bit your memory, here are the rules of the game for emergent algebras, look at the first two columns and ignore the third one (because this is old notation from graphic lambda calculus). An emergent algebra over a set X is a collection of operations indexed with a parameter in a commutative group. We can represent these operations by using oriented trivalent ribbon graphs (left side) or just binary trees (right side), here with leaves at the right and the root at the left.

 

shuffle_0

(image taken from this post).   (Image changed)

In this post we’ll use Reidemeister moves (they are related to the true Reidemeister moves).

shuffle_5

(Emergent algebras have one more property, but for this we need to have an uniform structure on X, because we need to take limits wrt the parameter which are uniform wrt the leaves… not needed here for the moment.)

Further I’ll use the representation with binary trees, i.e. I’ll not draw the orientation of the edges, recall: from the leaves, at right, to the root, at left.

By using the Reidemester 2 move twice, we can make the following version of a shuffle trick (in the figure below the orientation of the edges is from right to left, or from the leaves 1, 2, 3, 4 to the root)

 

shuffle_3

Encircled is a graph which quantifies the difference between the left and right sides of the original shuffle trick. So if we want to have a real shuffle trick in emergent algebras, then we would like this graph to transform to an edge, i.e. the following rewrite

shuffle_4

If this rewrite is possible in an emergent algebra, then we’d have a shuffle trick for it. Conversely, if the shuffle trick would be valid, then the graph from the left would transform to the one from the right by that shuffle trick and two Reidemeister 2 moves.

But look closer at this graph: reading from right to left, it looks like a bracket, or commutator in a group. It has the form b^{-1} a^{-1} b a , or almost!

This is because we can prove that indeed it is an approximate version of the commutator and that the shuffle trick in emergent algebras is possible only in a commutative case. We shall apply this further for chemlambda, to show that it is in a sense valid in a commutative frame. Also, we can work non-commutatively as well, the first example being the Heisenberg group. Lot of fun!