Tag Archives: reidemeister moves

How space is born (0)

This opens a new series of posts, which will turn us back to the “computing with space” theme, the main interest here at chorasimilarity.

Look again at the move R2 of graphic lambda calculus.

 

r2move

The epsilon and mu are, originally, elements of a commutative group. Suggestions have been made repeatedly that the commutative group can be anything.

The epsilon and mu are port names, just like the red 1, 2, 3 from the figure.

In the more recent drawing conventions (not that that matters for the formalism) the port names are in blue.

Here is again the same move, but without the epsilon and mu.

r2_newm

Of course, the green node is the fanout, in the chemlambda version.

Yes, eventually, everything is related to everything in this open notebook.

In the next posts I shall take it step by step.

________________________________________________________________

 

 

 

 

 

 

 

 

Zipper logic and knot diagrams

In this post I want to show how to do zipper logic with knot diagrams. Otherwise said, I want to define zippers and their moves in the realm of knot diagrams.

Knot diagrams, it’s a way of saying, in fact I shall use oriented tangle diagrams (i.e. the wires are oriented and there might be in or out wires) which moreover are only locally planar (i.e. we admit also “virtual crossings”, in the sense that the wires may cross without creating a crossing 4-valent node) and not, as usual, globally planar.

Here is the half zippers definition:

zipper_loop_1

As you see, each half zipper has some arrows which are not numbered, that is because we don’t need this information, which can be deduced from the given numbering, just by following the arrows.

We have to define now the CLICK move. For the zippers from chemlambda, that was easy, the move CLICK is trivial there. No longer here:

zipper_loop_2

The figure illustrates a CLICK move between a (-m)Z and a (+n)Z with m>n.  It’s clear how to define CLICK for the other cases m = n and m<n.

Finally, the ZIP move is nothing by repeated application of a R2 move:

zipper_loop_3

It works very nice and it has a number of very interesting consequences, which will be presented in future posts.

For the moment, let me close by recalling the post Two halves of beta, two halves of chora.

______________________________

SPLICE and SWITCH for tangle diagrams in the chemical concrete machine

Knot diagrams can be implemented in the chemical concrete machine.  This result has been already touched in the post  Local FAN-IN eliminates GLOBAL FAN-OUT (II). Here I shall give a short and clear exposition.

1. Oriented knot diagrams.  I shall describe the larger collection of oriented tangle diagrams. A knot is a proper embedding of an oriented circle in 3D space. A tangle is a proper  embedding of a finite collection of  oriented 1D segments (arcs) and circles  in 3D space. A tangle diagram represents a projection of a tangle in general position on a plane (i.e. so that different pieces of arcs or circles do not project on tangent curves in the plane), along with supplementary information at the crossings of the projections (i.e. when the  projections of two pieces of arcs cross, there is more information about which piece passes over).  In this description, a tangle diagram is a 4-valent, locally planar graph, made by two elementary nodes, called “crossings” (usually tangle diagrams are defined as being globally planar graphs made by crossings), and by loops.

chem_cross_0

2. Oriented Reidemeister moves. Two (globally planar) tangle diagrams represent the same 3D tangle up to regular deformations in 3D if and only if we can pass from one tangle diagram to another by a finite sequence of oriented Reidemeister moves (I use here, as previously, the names from   Michael Polyak “Minimal generating sets of Reidemeister moves“, excepting that I use  the letter “R” instead of the letter “\Omega“) .

reidemeister_1

reidemeister_2

reidemeister_3

These are 16 local graph rewrites (local moves) acting on the collection of tangle diagrams.

 3.   My purpose now is to give an implementation of tangle diagrams (not especially globally planar ones, but the more general locally planar ones)  in the chemical concrete machine formalism. For this I have to define the elementary nodes of tangle diagrams as molecules in the chemical concrete machine formalism. This is easy: the loops are the same as in the chemical concrete machine, the crossings are defined as in the following figure:

chem_cross

Each oriented tangle diagram is translated into a molecule from the chemical concrete machine, by using this definition of crossings.  As a consequence, each oriented Reidemeister move becomes a local move in the chemical concrete machine, simply by translating the LHS and RHS tangle diagrams into molecules.

4. I have to prove that these translations of the oriented Reidemeister moves are compatible with the moves from the chemical concrete machine in the following sense: each translation of a Reidemeister move can be obtained as a finite chain of moves from the chemical concrete machine.

It is easier to proceed the other way around, namely to ground  the reasoning in the oriented tangle diagrams universe. I shall translate back some moves from the chemical concrete machine, as seen as acting on oriented tangle diagrams.  See this post at mathoverflow for context, basically it’s almost all we need for the proof, supplemented only by the proof of the SWITCH move, as you shall see.

The graphic beta move in the chemical concrete machine translates as a SPLICE move (it has two variants) over oriented tangle diagrams. The elimination of loops becomes a LOOP move. These moves are described in the next figure.

splice_1

You can find in the mathoverflow post a proof that all oriented Reidemeister moves, with the exception of R2c, R2d, R3a, R3h, are a consequence of a finite number of SPLICE and LOOP moves.

It is left to prove that R2c, R2d, R3a, R3h can be expressed by (translations of) some chains of chemical concrete machine moves. It turns out that we can reduce all these moves to the move R2d by using SPLICE and LOOP, therefore the only thing left is to look at R2d.

chem_r2d

By SPLICE and LOOP, the left hand side of R2d becomes:

chem_r2d_1

So R2d is equivalent with the following SWITCH move:

chem_switch

Finally,  in the post   Local FAN-IN eliminates GLOBAL FAN-OUT (II)   there is a proof that the SWITCH move can be obtained from CO-COMM and FAN-IN moves. The next figure shows this.

chem_switch_2

This concludes the proof that R2d can be expressed by a chain of moves from the chemical concrete machine.

________________________

Local FAN-IN eliminates GLOBAL FAN-OUT (II)

As I wrote in   Local FAN-IN eliminates global FAN-OUT (I) , the introduction of the three moves (FAN-IN and the two DIST moves) eliminates global FAN-OUT from the lambda calculus sector of the graphic lambda calculus.  In this post we shall see that we can safely eliminate other two moves, namely R1a, R1b, as well as improving the behaviour of the crossings from the \lambda-TANGLE sector.

The equilibrium is thus established: three new moves instead of the three old moves. And there are some unexpected advantages.

______________

Proposition.

Proof.  (a) Done in the following picture.

frob_6

The proof of (b) is here:

frob_7

Finally, here is the proof of (c):

frob_8

______________

The \lambda-TANGLE sector of the graphic lambda calculus is obtained by using the lambda-crossing macros

frob_9

In Theorem 6.3   arXiv:1305.5786 [cs.LO]  I proved that all the oriented Reidemeister moves (with the crossings replaced by the respective macros), with the exception of the moves R2c, R2d, R3a and R3h, can be proved by using the graphic beta move and elimination of loops.  We can improve the theorem in the following way.

Theorem.  By using the graphic beta move, elimination of loops, FAN-IN and CO-COMM, we can prove all the 16 oriented Reidemeister moves.

Proof. The missing moves R2c, R2d, R3a and R3h are all equivalent (by using the graphic beta move and elimination of loops, see this question/answer at mathoverflow) with the following switching move, which we can prove with FAN-IN and CO-COMM:

frob_2

The proof is done.

Big sets of oriented Reidemeister moves which don’t generate all moves

The article  “Minimal generating sets of Reidemeister moves“ by Michael Polyak gives some minimal generating sets of all oriented Reidemeister moves. The question I am asking in this post is this: how big can be non-generating sets of moves?

The oriented Reidemeister moves are the following (I shall use the same names as Polyak, but with the letter \Omega  replaced by the letter R):

  • four oriented Reidemeister moves of type 1:

reidemeister_1

  • four oriented Reidemeister moves of type 2:

reidemeister_2

  • eight oriented Reidemeister moves of type 3:

reidemeister_3

Among these moves, some are more powerful than others, as witnessed by the following

Theorem. The set of twelve Reidemeister moves formed by:

  • four moves of type 1
  • two moves of type 2, namely R2a and R2b
  • six moves of type 3, namely R3b, R3c, R3d, R3e, R3f, R3g

does not generate the remaining moves R2c, R2d, R3a and R3h.

______________

I postpone the proof for another time, here I just want to emphasize that the moves R2c, R2d, R3a and R3h are more special than the rest of them. The proof which I have is via the graphic lambda calculus, but probably other proofs exists. Please tell me if you know a proof of this theorem.

UPDATE: see a proof at mathoverflow.

Axioms for projective conical spaces (towards qubits II)

I am continuing from the post Towards qubits: graphic lambda calculus over conical groups and the barycentric move.  My goal here is to give a set of axioms for a “projective conical space”. Let me recall the following facts:

  • affine conical spaces are the non-commutative equivalent of affine spaces. An affine conical space is constructed over a conical group as an affine space is constructed over a vector space.  Conical groups are generalizations of Carnot groups, in the sense that in the realm of Lie groups  the basic example of a conical group is a Carnot group. A conical Lie group is a contractive Lie group and therefore, by a theorem of Siebert, if it is simply connected then it is a nilpotent Lie group with a one-parameter family of contractive automorphisms. Carnot groups (think about examples as the Heisenberg group) are conical Lie groups with a supplementary hypothesis concerning the fact that the first level in the decomposition of the Lie algebra is generating the whole algebra.
  • an affine  conical space is an usual affine space if and only if it satisfies the barycentric move. In this case and only in this case the underlying structure of the conical group is commutative.See  arXiv:0804.0135 [math.MG] for the introduction of “non-commutative affine geometry”, called here “affine conical geometry”, which generalizes results from W. Bertram  Generalized projective geometries: From linear algebra via affine algebra to projective algebra, Linear Algebra and its Applications 378 (2004), 109 – 134.
  • afine conical spaces are defined in terms of a one-parameter family of quandle operations (called dilations). More specifically an affine conical space is generated by a one-parameter family of quandles which satisfy also some topological sugar axioms (which I’ll pass). More precisely, affine conical spaces are self-distributive uniform idempotent right quasigroups.  Uniform idempotent right quasigroups were introduced and studied under the shorter name “emergent algebras” in arXiv:0907.1520 [math.RA], see also   arXiv:1005.5031 [math.GR] for the context of studying them as algebraic-topologic generalizations of dilation structures (introduced in arXiv:math/0608536 [math.MG]), as well as for the description of symmetric spaces as emergent algebras.
  • in  affine conical  geometry there is no notion of incidence or co-linearity, because of non-commutativity lurking beneath. However, there is a notion of a collinear triple of points, as well as a ratio associated to such points, but such collinear triples correspond to triples of   dilations (see further what “dilation” means) which, composed, give the identity. Such triples give the invariant of  affine conical geometry which corresponds to the ration of three collinear points in the usual affine geometry.

In the post Towards qubits I I explained (or linked to explanations) this in the language of graphic lambda calculus. Here I shall not use it fully, instead I shall use a graphical notation with variable names. But I think the correspondences between these two notations are rather clear. In particular I shall interpret identities as moves in trivalent graphs.

1. Algebraic axioms for affine conical spaces. (Topological sugar not included). We have a non-empty set X  and a commutative group of parameters (\Gamma, \cdot, 1) with operation denoted multiplicatively \cdot(\varepsilon, \mu) = \varepsilon \mu and neutral element 1. Think about \Gamma as being (0,+\infty) or even K^{*} where K is a field.

On X  is defined a function \delta: \Gamma \times X \times X \rightarrow X (Bertram uses the letter \mu instead, I am using \delta). This function is to be interpreted as a \Gamma-parametrized family of operations. Namely we denote:

\delta(\varepsilon, x, y) = \delta^{x}_{\varepsilon} y = x \circ_{\varepsilon} y

This family of operations, called dilations, satisfies a number of algebraic axioms (as well as topological axioms which I pass), making them in particular into a family of quandle operations. I shall give these axioms in a graphical form, by using the transparent, I hope, notation:

dilat_1

Combinations (i.e. compositions) of dilations appear therefore as oriented trees with trivalent planar nodes decorated by the elements of \Gamma, with leaves (but not the root) decorated with elements from X.

The algebraic axioms of affine conical spaces are stating identities between certain compositions of dilations. Graphically these identities will be representes, as I wrote, as moves applied to such oriented trees.

Here are these axioms in graphical form:

(1) this  is equivalent with the move ext2    from graphical lambda calculus: (i.e. extensionality move 2)

dilat_2

(2) this is equivalent with the move R1a from graphical lambda calculus (i.e. Reidemeister move R1a, following the notation from Michael Polyak “Minimal generating sets of Reidemeister moves“)

dilat_3

(3) this is equivalent with the move R2 from the graphical lambda calculus (i.e. Reidemeister move 2, all Reidemeister moves 2 are equivalent in this formalism)

dilat_4

(4) this is the self-distributivity axiom, which could be called move R3b with the notations of Polyak

dilat_5

2. Algebraic axioms for projective conical spaces.  The intention is to propose a generalization of the same type, this time for projective spaces, of the one from W. Bertram Generalized projective geometries: General theory and equivalence with Jordan structures,  Advances in Geometry 3 (2002), 329-369.

This time we have a pair of spaces (X,X'). Think about the elements  x \in X as being “points” and about the elements  a \in X' as being “lines”, although, as in the case of affine conical geometry, there is no proper notion of incidence (except, of course, for the “commutative” particular case).

A pair geometry is a triple (X,X',M) where M \subset X \times X' is the set of pairs (say point-line) in general position. Compared to the more familiar case of incidence systems, the interpretation of (x,a) \in M is “the point x is not incident with the line a“.  The triple satisfies some conditions which I shall write after introducing some notations.

For any x \in X and any a \in A we denote:

V_{x} = \left\{ b \in X' \mid (x,b) \in M \right\}  and    V_{a} = \left\{ y \in X \mid (y,a) \in M \right\}.

Let also denote

D = \left\{ (x,a,y) \in X \times X' \times X \mid (x,a), (y,a) \in M \right\} and D' = \left\{ (a,x,b) \in X' \times X \times X' \mid (x,a), (x,b) \in M \right\}.

We ask:

(Pair geometry 1) for any x \in X and for any a \in X' the sets V_{x} and V_{a} are non-empty,

(Pair geometry 2) for any pair of different points x,y \in X there exists and it’s unique a line a \in X' such that (x,a) and (y,a) are not in M; dually, for any pair of different lines a,b \in X' there exists and it’s unique a point x \in X such that (x,a) and (x,b) are not in M.

Remark. This is the definition of a pair geometry given by Bertram. I shall keep further only (Pair geometry 1) because I feel that (Pair geometry 2) has too much “incidence content” which might be not non-commutative enough. So, for the moment, (Pair geometry 2) is in quarantine. As a first suggestion coming into mind, it might well turn out that it can be replaced by a more lax version saying that there is a number N such that X is covered by the reunion of N  sets V_{x} (and a similar dual formulation for X'. As it is, (Pair geometry 2) corresponds to such a formulation for N = 3.

We want the following:

  1. for any point x \in X the space V_{x} is an affine conical space,
  2. for any line a \in X' the space V_{a} is an affine conical space,
  3. these structures are glued together by some axioms.

Let’s pass through these three points of the list.

1.  that means we shall put a structure of dilation operations on every V_{x}. It is natural then to mark the dilation operations not only by elements of the group \Gamma, but also by x. More concretely that means we introduce for any \varepsilon \in \Gamma  a function

\delta_{\varepsilon}: D' \rightarrow X'

which, for any x \in X it takes a pair of lines (a,b), with a,b \in V_{x} and returns \delta_{\varepsilon}(a,x,b) \in V_{x}.

We ask that for any x \in X the dilations \varepsilon \mapsto \delta_{\varepsilon}(\cdot, x, \cdot) satisfy axioms (1), (2), (3) of affine conical spaces.

2. in the same way, we want that every V_{a} to have a structure of dilation operations. We have therefore, for any \varepsilon \in \Gamma another function (but I shall use the same letter \delta)

\delta_{\varepsilon}: D \rightarrow X

which, for any a \in X' it takes a pair of points (x,y), with x,y \in V_{a} and returns \delta_{\varepsilon}(x,a,y) \in V_{a}.

We ask that for any a \in X' the dilations \varepsilon \mapsto \delta_{\varepsilon}(\cdot, a, \cdot) satisfy axioms (1), (2), (3) of affine conical spaces.

3.  the gluing axioms are generalizations of axioms (PG1), (PG2) of Bertram. In the mentioned article, Bertram explains that these two axioms lead to eight identities. From those eight, six of them are different. From those six, Bertram is using the barycentric axiom to eliminate two of them, which leaves him with four identities. I shall not use the barycentric axiom, because otherwise I shall fall on the commutative case, but  I shall eliminate as well  these two axioms> Therefore I shall have  four  moves which will replace the Reidemeister move 3 axiom , i.e. the self-distributivity move (4) from affine conical spaces.

Remark. Bertram adds some sugar over (PG1) and (PG2) which serves to be able to construct tangent structures further. I renounce at those in favor of  my topological sugar which I pass, for the moment.

Remark. As we saw that the axioms of affine conical spaces are practically corresponding to the Reidemeister moves, it is natural to expect that the four  axioms correspond to either: the Roseman moves, or to some 2-quandle definition. I need help and suggestions here!

I shall write further the four axioms which replace the axiom (4), that is why I shall name them (4.1) … (4.4). As previously I shall use a graphical notation, which my visual brain finds more easy to understand than the notation using multiple compositions of functions with 4 arguments (however, see Bertram’s notations involving adjoint pairs). Also, there are limits to my capacity to write latex formulae which are well parsed in this blog.

So, here is the notation for dilations which I shall use for writing those four axioms:

proj_1

Let’s look at the first line. For any a \in X' we have an associated dilation operation taking as input a pair of points x,y \in V_{a}. Graphically this is represented by a node with two inputs and an output, together with a planar embedding  (i.e. the local planar embedding tells us which is the left input and which is the right output), and  with a supplementary input which points to the center of the circle (node), serving to identify the node as the dilation in the space V_{a}. Similar comments could be made about the second line of the figure.

Therefore, this time we are working with trees made by 4-valent nodes, each node having three inputs and one output and moreover with a triple of two inputs and the output with an orientation given.  The leaves, but not the root of such a tree are decorated by points or lines. There should be other constraints on this family of trees, coming from the fact that if the input which points to the center of the circle correspond to a point then the other inputs should correspond to lines, and so on. For the moment I pass over this, probably a solution would be to colour the edges, by using two colors, one for points, the other for lines, then express the constraints in terms of those colors.

As previously, the nodes are decorated by elements of the commutative group \Gamma.

(4.1)     first part of (PG1) proj_2

______________________

(4.2) second part of (PG1)

proj_3

______________________

(4.3)  first  part of (PG2)

proj_5

______________________

(4.4) second part of (PG.2)

proj_6

______________________

In a future post I shall give:

  • a theorem of characterization of projective conical spaces, of the same type as the theorem of characterization of affine conical spaces
  • examples of non-commutative projective conical spaces, in particular answering to the question: what is the natural notion of a projective space of a conical group (more particularly, if we think about Carnot groups as being non-commutative vector spaces, then who are their associated non-commutative projective spaces?).

UPDATE:  The axioms (4.1) … (4.4) take a much more simple form if we use choroi and differences, but that’s also for a future post.

 

Emergent algebra moves R1a, R1b, R2 and ext2

This is part of the Tutorial:Graphic lambda calculus.

Here are described the moves related to emergent algebras. This moves involve the gates \bar{\varepsilon}, \Upsilon and the termination gate.

See the post “3D crossings in emergent algebras” in order to understand the relation with knot diagram crossings and with Reidemeister moves for oriented knot diagrams (for those I use the notations  from the paper    “Minimal generating sets of Reidemeister moves“,  by Michael Polyak  only that I use the letter “R” from “Reidemeister” instead of “\Omega” used by Polyak).

_________

We have an abelian group \Gamma with operation denoted multiplicatively and with neutral element denoted by 1. Thus, for any \varepsilon, \mu = \mu \varepsilon \in \Gamma their product is \varepsilon \mu \in \Gamma, the inverse of \varepsilon is denoted by \varepsilon^{-1} and we have the identities: 1 \varepsilon = \varepsilon , \varepsilon \varepsilon^{-1} = 1.

For each \varepsilon \in \Gamma we have an associated gate \bar{\varepsilon}.

  • The move R1a is described in the following figure

r1amove

The reason for calling this move R1a is that is related to the move R1a from Polyak paper (also to R1d). In the papers on emergent algebras this move is called R1, that is “Reidemeister move 1”.

  • The move R1b is this:

r1bmove

This move is related to the move R1b from Polyak (and also to R1c). This move does not appear in relation with general emergent algebras, it is true only for a special subclass of them, namely uniform idempotent quasigroups.

  • The move R2 is the following:

r2move

We shall see that this is related to all Reidemeister 2 moves (using also CO-ASSOC, CO-COMM, and LOCAL PRUNING).

  • The move ext2. The notation comes from the rule (ext2) from lambda-Scale calculus. In emergent algebra language it means that the emergent algebra operation indexed by the neutral element of \Gamma is the trivial operation xy = y.

ext2r

(but for this LOCAL PRUNING is also used).

___________________________

Return to Tutorial:Graphic lambda calculus