Lecture 6 (13.10.2015)

Last time we introduced the concept of 3-colourability of a diagram (Def. 2.1). This concept is interesting because it is an invariant:

Proposition 2.2: 3-colourability is a link invariant.

For the proof of this fact, we need to check that 3-colourability is unchanged under the Reidemeister moves 0-III. The necessary diagrams are contained in the following pdf file, together with the demonstration that – as an example – the diagram

3-col1

is not 3-colourable.

Example of a non-trivial knot that is not 3-colourable, and diagrams for the proof of Proposition 2.2 (pdf)

Note that the diagrams in these slides do not provide the full proof of the proposition – they must be accompanied with the necessary explanations about which colours lie at the boundary of the diagrams etc, as given in the lecture. See also the proof of Prop. 2.5 below.

Now that we know that 3-colourability is a link invariant, it is meaningful to say that a link (instead of a diagram) is 3-colourable: This means that one (and thus all) of its diagrams are 3-colourable in the sense of the previous definition. This procedure of defining a property of diagrams, then checking that it is invariant under Reidemeister moves, and then using it as a property of links as well, will always be followed in the future.

Let us write down some consequences of Prop. 2.2. Here and in the following, we will say that a link with $n$ components (that is, an $n$-link) is non-trivial if it is not equivalent to the $n$-unlink (that is, the link with $n$ components that has a diagram consisting of $n$ circles in the plane, without any crossings). Conversely, an $n$-link is called trivial if it is equivalent to the $n$-unlink.

Corollary 2.3:

  • Any knot that is 3-colourable is non-trivial.
  • Let $n\geq2$. Then any $n$-link that is not 3-colourable is non-trivial.
  • The trefoil is non-trivial. The Hopf link is non-trivial.

Proof: We have shown last time that the unknot is not 3-colourable. As 3-colourability is a link invariant, any knot that is equivalent to the unknot (i.e., any trivial knot) must be not 3-colourable as well. In other words, a knot that is 3-colourable is non-trivial.

(Of course, if we have two knots which are both 3-colourable it does not follow that they are equivalent. That would require a complete invariant, and 3-colourability is not complete. It splits the family of all links into two disjoint subfamilies, those that are 3-colourable, and those that are not. No link from the first family is equivalent to a link of the second family. But between links which are either both 3-colourable or both not 3-colourable, this invariant can not distinguish.)

For the second part, we observe that the $n$-unlink, $n\geq2$, is 3-colourable. For example, let $n=2$ and consider the 2-unlink in its usual diagram:

2-unlink-col

The above colouring uses at least two colours (namely, exactly two), and since there are no crossings, also the second condition of Def. 2.1 is not violated. Hence the 2-unlink is 3-colourable, and similarly, an $n$-unlink with $n\geq2$ is 3-colourable.

Taking into account that 3-colourability is a link invariant, it now follows that any $n$-link, with $n\geq2$, which is not 3-colourable is non-trivial.

The third part follows by application of the first two parts: The trefoil is 3-colourable (see last lecture), hence it is non-trivial. The Hopf-link, on the other hand, is not 3-colourable, as can be seen from its coloured diagram

Hopf-3col

which violates rule 2 of Def. 2.1. Thus, by part two of this corollary, the Hopf link is non-trivial.

 

Problem 5 and Problem 6a contain exercises about 3-colourability.

 

We now want to improve the 3-colourability invariant in two ways. First, we want “stronger” invariants. (By a strong invariant we mean an invariant that can distinguish many links. 3-Colourability can only distinguish links in two classes, which is very weak.) And second, we want an invariant that we can compute efficiently and systematically. Both wishes will be fulfilled by the following generalisation of 3-colourability.

In a first step, we replace our three colours red, green, blue by the three numbers 0, 1, and 2. As before, we assign numbers to arcs of diagrams in such a way that not all numbers assigned are the same (rule 1 of Def. 2.1). The second rule of Def. 2.1 is more interesting to translate to numbers. Let us look at a labeled crossing

abc-crossing

where $a,b,c\in\{0,1,2\}$ are now numbers instead of colours (no orientation of the crossing is considered here). Let us consider the case that $a,b,c$ are all different. Then we are in one of the following three situations: (possibly with $b$ and $c$ exchanged, which however does not matter here)

2abc

 

Observe that in the first case, we have $2a-b-c=0$, in the second case we have $2a-b-c=3$ and in the third case, we have $2a-b-c=-3$. Also note that in the “monochromatic” situation $a=b=c$, we have $2a-b-c=0$. So the result of $2a-b-c$ is not always the same, but it is always divisible by $3$. In other words, rule 2 of Def. 2.1 is equivalent to requiring that $$2a-b-c=0\;\mod 3$$ at each crossing of the diagram, where $a$ is the number attached to the overarc of the crossing, and $b,c$ are the numbers attached to the two underarcs of the crossing.

A natural generalisation is to replace $3$ by some different integer $p$. For reasons that will become clear later, $p$ will usually be restricted to the odd primes, i.e. $p\in\{3,5,7,11,13,17,…\}$.

Definition 2.4: Let $p$ be an odd prime. A diagram $D$ is called $p$-colourable if one can assign variables $x_1,x_2,…,x_{|D|}\in\{0,1,…,p-1\}$ to its arcs (recall that a diagram with no closed loops has the same number of arcs and crossings, namely, $|D|$) such that

  • Not all $x_i$ coincide, i.e. we do not have $x_1=x_2=…=x_{|D|}$.
  • At each crossing of the diagram, there holds the equation $$2a-b-c=0\,\mod p,$$where $a$ is the number attached to the overarc of the crossing, and $b,c$ are the numbers attached to the two underarcs of the crossing. (That is, $a,b,c\in\{x_1,…,x_{|D|}\}$, which $x_i$ equals for example $a$ depends on the considered crossing.)

In the following, we will sometimes refer to the two conditions on the labeling as “Rule 1” (the condition that not all $x_i$ are the identical) and “Rule 2” (the equations to be satisfied at each crossing).

Two questions immediately come up: 1) Is $p$-colourability a link invariant? 2) Can we systematically compute if a given diagram is $p$-colourable? The answers are yes and yes.

Before showing that, some more remarks:

  • For $p=3$, Def. 2.4 coincides with Def. 2.1, as shown earlier.
  • For $p\neq 3$, $p$-colourability means something different than colouring a diagram with $p$ colours. It is best to forget about colours at this stage, despite the name “$p$-colourability”.
  • Why do we ask that $p$ is an odd prime? Here are two reasons: If a diagram is $p$-colourable, then it is also $n\cdot p$-colourable for any integer $n$. To see this, just multiply all variables with $n$. And: No knot is 2-colourable (why?).

Recall that an equation of the form $a=b\mod p$ with $a,b,p\in\mathbb Z$ integers means that $a-b$ is divisible by $p$, or, equivalently, that when “dividing with remainder” (Euclidean division) the remainder of the division $a:p$ coincides with the remainder of the division $b:p$, or, again equivalently, that $a=b+n\cdot p$ for some integer $n$. Some more aspects of working modulo $p$ will be recalled in the next lecture.

Proposition 2.5: $p$-Colourability is a link invariant.

Proof: As always, we have to check that $p$-colourability is preserved under the Reidemeister moves to show that it is a link invariant.

Move 0 does not change the crossings or arcs, just the shapes of the arcs. Thus any assignment of variables $x_1,…,x_{|D|}$ directly carries over from one diagram to another one which is deformed by planar isotopy (move 0). Since no variables are changed, both conditions of Def. 2.4 hold after the move if and only if they hold before the move.

With the remaining “real” Reidemeister moves I-III, we have to check three things for each move:

  1. The variables at the boundary of the circles are the same before and after the move. This ensures that if one partial diagram fits into the big link diagram surrounding it, then also the other partial diagram (the one obtained after carrying out the move) will fit, and vice versa.
  2. The diagram after the move is monochromatic (i.e. all appearing variables coincide) if and only if the diagram before the move is monochromatic. This ensures that Rule 1 of Def. 2.4 is left invariant by the move.
  3. Both diagrams, before and after the move, satisfy Rule 2 of Def. 2.4.

Move I: 

move1-x

Starting from the left hand side, we have one variable $x\in\{0,…,p-1\}$ attached to the one arc. If we put $x$ as variable for both arcs on the right hand side, it is apparent that items 1.-3. in our above check list hold. On the other hand, if we start from the right, then the only possibility is to put two identical variables $x$ on both arcs in order not to violate Rule 2. Moving back to the left, again 1.-3. hold.

Move II: 

move2-x

We again start from the left, with two variables $x,y\in\{0,1,…,p-1\}$ attached to the two arcs. If we assign the numbers as indicated on the right, then we observe that 1.-3. hold: 1) The variables in the two left “corners” are both $x$, in the two right “corners” both $y$, in both the left and right diagram. 2) The left hand side is monochromatic if and only if $x=y$, and the right hand side is monochromatic if and only if $x=y=2x-y\mod p$. Hence the left hand side is monochromatic if and only if the right hand side is. 3) Rule 2 is satisfied at each crossing. In fact, the variable $2x-y\,\mod p$ for the little arc in the middle is fixed by Rule 2: Denoting the variable of the middle arc by $z$, we need $2x-y-z=0\,\mod p$ by considering the lower crossing, which gives $z=2x-y\,\mod p$.

We thus see that, starting now from the right diagram, the only configuration of variables that is allowed by Rule 2 is the one that is specified, for certain $x,y\in\{0,1,…,p-1\}$. As before, one sees that 1.-3. hold when performing the inverse move II, going from the right to the left diagram.

Move III: The arguments for this move are very similar to the ones before. Note that the following pattern of variables is enforced by Rule 2:

move3-x

Once the variables $x,y,z$ of the three arcs touching the left boundary of the circle are fixed, all remaining variables can be calculated from Rule 2. It is now easy to check that 1.-3. hold when going from the left to the right, or vice versa.$\square$

 

Having verified that $p$-colourability is indeed a link invariant, we now address the question how to compute it. Let us first focus on Rule 2 in Def. 2.4: For each crossing in the diagram, we have a linear equation (mod $p$) to be satisfied. Since there are as many arcs as crossings (if there are crossings at all), we get a system of $|D|$ linear equations mod $p$ for $|D|$ variables $x_1,…,x_{|D|}$. As always with systems of linear equations, it is a good idea to use linear algebra (matrices) to simplify matters.

As an example, we first consider a diagram of the figure eight knot. Let us label the four crossings in some arbitrary way, and let us assign variables $x_1,x_2,x_3,x_4$ to the four arcs, again in an arbitrary way. For example, we could do it like this:

fig8-labeled

Here the red numbers label the four crossings, and the $x_i$ label the four arcs. That I wrote the crossing labels in red is just to distinguish them from the other labels (and because I like red), and has nothing to do with colouring — we have abandoned colours and now work only with numbers.

By carefully observing for each crossing which arc goes over and which two arcs go under the crossing, Rule 2 gives us the following four equations (one for each crossing):

$\begin{align*}\text{crossing 1)}\quad 2x_2-x_1-x_3&=0\,\mod p\\\text{crossing 2)}\quad 2x_1-x_2-x_4&=0\,\mod p\\\text{crossing 3)}\quad 2x_3-x_1-x_4&=0\,\mod p\\\text{crossing 4)}\quad 2x_4-x_2-x_3&=0\,\mod p\end{align*}$

Using matrix notation, we can equivalently write

$\begin{align*}\left(\begin{array}{rrrr}-1&2&-1&0\\2&-1&0&-1\\-1&0&2&-1\\0&-1&-1&2\end{array}\right)\left(\begin{array}{r}x_1\\x_2\\x_3\\x_4\end{array}\right)=0\,\mod p\,,\end{align*}$

where $0$ denotes the 0 vector with four components, and mod $p$ refers to each component.

To check if the diagram is $p$-colourable ($p$ has not been fixed yet), we need to check if this linear system has a solution $x_1,..,x_4$ such that not all $x_i$ coincide (Rule 1).