Low Dimensional Topology

July 8, 2013

Tangle Machines- Part 1

Filed under: Combinatorics,Misc. — dmoskovich @ 11:27 am

In today’s post, I will define tangle machines. In subsequent posts, I’ll realize them topologically and describe how we study them and more about what they mean.

To connect to what we already know, as a rough first approximation, a tangle machine is an algebraic structure obtained from taking a knot diagram coloured by a rack, then building a graph whose vertices correspond to the arcs of the diagram and whose edges correspond to crossings (the overcrossing arc is a single unit- so it “acts on” one undercrossing arc to change its colour and to convert it into another undercrossing arc). Such considerations give rise to a combinatorial diagrammatic-algebraic setup, and tangle machines are what comes from taking this setup seriously. One dream is that this setup is well-suited to modeling mutually interacting processes which satisfy a natural `conservation law’- and to move in a very applied direction of actually identifying tangle machine inside data.

To whet your appetite, below is a pretty figure illustrating a 9_{26} knot hiding inside a synthetic collection of phase transitions between anyons (an artificial and unrealistic collection; the hope is to find such things inside real-world data):

9_26 example

A single interaction

The basic unit I’d like to consider is

single interaction

Here, an input x is acted on by an operator y to become an output x\triangleright y. This process is called an interaction.

In the above picture there are 3 registers (i.e. vertices of a graph) each of which contains a colour x, y, or z in a set of colours Q. The interaction is by way of a binary operation \triangleright on Q. So, for instance, if Q were \mathbb{Z}/5\mathbb{Z} (integers modulo 5), and if \triangleright were defined as a\triangleright b\, \stackrel{\textup{\tiny def}}{=}\, (2b-a) \bmod 5, then

modulo 5 example

would be an example of an interaction.

Note that there does not exist a `time’ parameter in the definition of an interaction. The input does not occur `before’ the output.

I want you to think of registers as representing real-world objects (elementary particles in physics, employees in a firm, physical units of computer memory) and of their colours in Q as representing the relevant data which they contain and which we are interested in (wave function, wave field, role, phase, state). So

single interaction

means that the operator register causes the input register to become the output register, whose colour becomes x\triangleright y.

An alternative figure for the interaction is

singleinteraction

that depicts a line (the input) passing through a cylinder (the operator) in dimension 4, to become the output.

Conservation law

The operation \triangleright on Q must satisfy one axiom, that is the conservation law. It says that the function \bullet\triangleright w\colon\, Q\rightarrow Q sending each x\in Q to x\triangleright w\in Q is an automorphism of Q. In particular, \bullet\triangleright w sends the set of elements of Q bijectively onto itself (for any colour z there exists a colour x such that x\triangleright w=z). This requirement is called global conservation or Reidemeister 2. It is also a bijection on relations, which means that (x\triangleright w)\triangleright(y\triangleright w)= z\triangleright w if and only if x\triangleright y = z. This requirement is called local conservation or Reidemeister 3.

So (Q,\triangleright) is a mathematical structure called a rack or an automorphic set. The above description, due to Brieskorn, makes it clear how natural the axiom is (Q acting on itself loses no information), and how it has nothing at all to do with topology, even if later we’ll see that global and local conservation correspond to invariance of a diagram under the classical Reidemeister moves. There is no creatio ex nihilo- every state must have arisen from another state, and every relation must have arisen from another relation, bijectively.

Global conservation means in particular that \triangleright has a set-theoretical inverse operation, which we call \triangleleft. Thus our possible interactions are

bdlinteraction

not to mention cases in which some or all of the registers in an interaction happen to coincide, such as

an isthmus

I also want to have a `nothing happens’ edge to work with:

identity edge

A special property which is satisfied in all of the applications which we are currently studying, and which is worthy of special consideration philosophically and mathematically as well, is the property that x\triangleright x=x for all x\in Q. In other words, this is the property that the action of an operator on itself is trivial- a colour cannot add information to itself (one setting in which I could imagine this failing would be for applications to machine learning- maybe a self-interaction could add information to the machine. But I haven’t thought about this enough to have a convincing specific example of this happening). If the property x\triangleright x=x is satisfied for all x in a rack Q, then Q is said to me a quandle.

Multiplication

Output for one interaction can be input for another interaction. So we can `multiply’ or `compose’ interactions to form patterns such as

trefoils

These correspond to a braid which closes to a coloured trefoil, and to a coloured trefoil knot, correspondingly (see if you can figure out how before it is explained below).

Notive that operators are themselved coloured, and so it makes sense to to use them as inputs or as outputs for interactions. Objects which act on other objects may in turn be acted on.

I’m going to want to call the structures discussed above tangle machines, and my next step is going to be to justify that language, and related terminology which may be used to discuss them.

Let’s think of the Cayley graph of Q as an automaton. This graph has the elements of Q as its vertices, and a z labeled edge between x and x\triangleright z for all x,z\in Q. A process is a walk on this automaton (I think that this is consistent with automata theory usage of the word `process’- am I right?). The start point of the walk is its initial register and its endpoint is its terminal register. A machine is a collection of mutually interacting processes.

Precisely:

Definition:
A machine is a graph (V,E) each of whose connected components is either a line graph or a cycle, together with a partially-defined function \phi\colon\, E\to V\times \{\pm\} (which assigns to each edge the vertex corresponding to the operator in the interaction across that edge, with a plus sign if it’s \triangleright and a minus sign if it’s \triangleleft, and this sign is called \mathrm{sgn}(e)) and a function \rho\colon\, V\to Q (uploading a colour into each register) such that, if e is an edge from v to w then we have:

  • \rho(v)\triangleright \rho(\phi(e))=\rho(w),         If \mathrm{sgn}(e)=+;
  • \rho(v)\triangleleft \rho(\phi(e))=\rho(w),         If \mathrm{sgn}(e)=-;
  • \rho(v)=\rho(w),                        If e\notin \mathrm{Domain}(\phi).

Reidemeister moves

The conservation law implies that some local modifications of a machine do not change its information content. For instance:

Reidemeister 2

This relation says that if we perform an operation and then immediately undo it, it’s the same as not having done anything at all. This move is called Reidemeister 2, because it will be expressed as sort of a Reidemeister 2 moves when we move to a different sort of diagram.

Local conservation implies that:

Reidemeister 3 specific

The left hand side imparts the same information as the right hand side.

And, more generally:

Reidemeister 3 general

What happens here is that the `z’ label moves all the way over the local picture, without adding or taking away any information.

Philosophical aside

Because I’m trying to sell you the idea that machines pre-exist, I owe you a philosophical explanation for the Reidemeister moves in the context of machines and processes. This serves to elucidate the type of phenomena which machines might perhaps be used to model.

I think that Reidemeister 2 tells us that interactions in machines are causation rather than correlation. In statistics, we measure correlation between variables- but finding such a correlation does not tell us that one causes the other, or which causes which. There is a nice discussion on wikipedia. Conversely, in our machines the vertices are oriented clockwise or counterclockwise, as determined by whether the operation is \triangleright or \triangleleft, and this does describe causality- it tells determines a causal relation between the input, which, acted on by the operator, becomes the output; and it tells that that given the output and the operator we can reconstruct the input. This tells us that phenomena which machines can model should be phenomena in which the interactions are causal, and that given the output and operator we know the input. Causality is often viewed as being a time-related phenomenon- the cause must precede the effect- but that isn’t really true. Causality is order (orientation of vertices) as opposed to direction (orientation of edges).

I interpret Reidemeister 3 philosophically as telling us that, if we have determined a `causal web’ of causes and effects (one interaction is a sufficient `web’ for me), and then we find a more fundamental cause for everything (an operator which acts on everything), then this still preserves the causal web. So it’s a stability property of the phenomenon- the causal relationships which we have found inside the data remain causal relationships when we find more fundamental causes as well. Our model does not melt away when we peer deeper into a system.

Tangle diagrams and topological realization

I’ll say more about this next time, but tangle machines have diagrams which look a lot like knot diagrams. A picture is worth a thousand words:

Conversion to a tangle diagram

You should think of this as representing a 4 dimensional picture (at least, if Q is a quandle). So the thick line is a 2-sphere in \mathbb{R}^4, and the line is crossing `through’ it:

singleinteraction

We also want to allow a line segment to `inflate’ into a sphere with nothing coming through it, and for such a thing to deflate (else no Reidemeister 2).

So for an example of a diagram:

An example

This is quite similar to the Bar-Natan’s balloons and hoops, except that we have a lot of balloons all lined up, instead of just one per component- thanks to Dror for pointing this out!

Note (and we’ll discuss this next time) that Reidemeister 2 for machines is different from a Reidemeister 2 move in knot theory in an interesting way! (also Reidemeister 3) Namely, there is no ordering of operations along the `overstrand’ (the operator). Our Reidemeister 2 preserves information. In contrast, Reidemeister 2 in knot theory does add information. It separates the overstrand into three segments (`before’, `during’, and `after’ the local picture), and so induces an ordering of points on the overstrand which we did not have before having performed the move. It introduces an ordering along the overstrand which did not exist before. This exemplifies the difference in flavour between tangle machines and classical knot theory.

Next time I’ll say more about topological realizations, and about invariants for these things.

About these ads

2 Comments »

  1. Nice explanation – I’ll stay tuned!

    Comment by Scott Taylor — July 10, 2013 @ 12:08 pm | Reply

  2. Hi, I just discovered your blog. I am interesting for a long time in quandles, tangles and computation, shall give only one link on graphic lambda calculus. I started from tangle diagrams (and some Plato) see arXiv:1103.6007 .

    Comment by chorasimilarity — February 11, 2014 @ 6:38 pm | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 207 other followers

%d bloggers like this: