Printer Friendly

Minimum number of colors: the Turk's Head Knots case study.

An r-coloring of a knot diagram is an assignment of integers modulo r to the arcs of the diagram such that at each crossing, twice the the number assigned to the over-arc equals the sum of the numbers assigned to the under-arcs, modulo r. The number of r-colorings is a knot invariant i.e., for each knot, it does not depend on the diagram we are using for counting them. In this article we calculate the number of r-colorings for the so-called Turk's Head Knots, for each modulus r. Furthermore, it is also known that whenever a knot admits an r-coloring using more than one color then all other diagrams of the same knot admit such r-colorings (called non-trivial r-colorings). This leads to the question of what is the minimum number of colors it takes to assemble such an r-coloring for the knot at issue. In this article we also estimate and sometimes calculate exactly what is the minimum numbers of colors for each of the Turk's Head Knots, for each relevant modulus r.

Keywords: Knots, Turk's head knots, colorings, colors, minimum number of colors

1 Introduction

Given an integer r > 1 and a knot diagram, [D.sub.K], of a given knot K, a (Fox) r-coloring of [D.sub.K] (Fox (1961)) is an assignment of integers mod r (i.e., numbers from [Z.sub.r] = {0, 1, 2,..., r - 1} mod r) to the arcs of the diagram such that, at each crossing of [D.sub.K], the equality "twice the color on the over-arc equals the sum of the colors on the under-arcs" holds (mod r). The Fox r-colorings can be alternatively envisaged as follows. Assign a variable to each arc of [D.sub.K] and at each crossing read off the equation 2y - x - z = 0 where y is the variable assigned to the over-arc and x and z are the variables assigned to the under-arcs (Figure 1).

A system of linear homogeneous equations is thus associated to each knot diagram. The solutions of this system of equations mod r constitute the r-colorings of [D.sub.K]. There are always the trivial colorings i.e., the colorings where each arc is assigned the same color. Upon performing a Reidemeister move on [D.sub.K] endowed with an r-coloring, we can consistently assign colors to the arcs on the transformed portion of diagram in a unique way so that we obtain an r-coloring on the new diagram. Furthermore, if we undo this Reidemeister move, we can reassign colors so that we obtain the original r-coloring on [D.sub.K]. There is thus a bijection between the r-colorings of two knot diagrams related by a finite number of Reidemeister moves (Lopes (2003)). Hence, the number of r-colorings is a knot invariant. Furthermore, this consistent assignment or reassignment of colors upon the performance of Reidemeister moves on colored diagrams takes trivial r-colorings to trivial r-colorings and non-trivial r-colorings to non-trivial r-colorings (non-trivial r-colorings being those that use at least two colors). In this way, the existence or not of non-trivial r-colorings is also a knot invariant.

[FIGURE 1 OMITTED]

Assume, then, a knot admits non-trivial r-colorings. What is the minimum number of colors needed to set up a non-trivial coloring over all diagrams of this knot?

Definition 1.1 Let r be an integer greater than 1. Let K be a knot, [D.sub.K] one of its diagrams. Assume K admits non-trivial r-colorings and let [??] stand for the least number of colors it takes to set up a non-trivial r-coloring of [D.sub.K]. We call

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

the minimum number of colors of K mod r, and denote it [mincol.sub.r] (K).

This is tautologically a knot invariant. Since to each knot there correspond infinitely many diagrams, the calculation of minimum number of colors by direct application of the definition is impossible. Nonetheless in this article we are able to make reasonable estimates and sometimes even calculate exactly the minimum number of colors of the knots at issue.

We remarked before that r-colorings of a knot K can be regarded as the solutions of a system of linear homogeneous equations over [Z.sub.r] read off the diagram of K under study. Upon performance of Reidemeister moves on this diagram, the matrix of the coefficients of the linear homogeneous system of equations undergoes elementary transformations as described in Lickorish (1997) on page 50. In this way, the equivalence class of the matrix of the coefficients modulo elementary transformations is a knot invariant. Furthermore, due to the fact that any row vector (respect., column vector) is a linear combination of the other row vectors (respect., column vectors), it turns out that the absolute value of any first minor of this matrix yields the same value and is thus also a knot invariant. This first minor is called the determinant of the knot K, and is denoted det K. See also Lopes and Matias (2012) and Kauffman and Lopes (2009).

The topic of minimum number of colors was set forth in Harary and Kauffman (1999) where the Kauffman-Harary conjecture was presented. Given a prime p, this conjecture states that a non-trivial p-coloring on a reduced diagram of an alternating knot of prime determinant p, assigns different colors to different arcs. This conjecture has now been proven in Mattman and Solis (2009).

There are other articles on minimum number of colors addressing the actual minimum for a given r-coloring. Satoh (Satoh (2009)) shows that any non-trivial 5-coloring can be realized with 4 colors; Oshiro (Oshiro (2010)) shows that any 7-coloring can be realized with 4 colors. On the other hand, Saito (Saito (2010)) gives a condition for the minimum number of colors in a non-trivial p-coloring to be greater than 4, for prime p > 7. In Lopes and Matias (2012) it is conjectured that the minimum number of colors modulo r of a given knot K depends on the least common prime factor to r and det K. To support it, it is proved that this is true when this common prime factor is 2, 3, 5, and 7 with the minima 2, 3, 4, and 4, respectively.

In Kauffman and Lopes (2008), the torus knots of type (2, n), the T(2, n)'s, were investigated. A formula for the number of r-colorings was established for each n, thereby allowing one to realize for which pairs (r, n) there are non-trivial r-colorings of T(2, n). For these cases, and relying on the features of modular arithmetic, estimates and sometimes actual minima were presented for the minimum number of colors. Furthermore, a sequence of transformations on the standard diagrams of the T(2, n)'s were defined that helped on further decreasing the number of colors in infinitely many cases.

For each n [member of] [Z.sup.+], the Turk's head knot on 3 strands, denoted THK(3, n), is the closure of the braid [([[sigma].sub.2] [[sigma].sub.1.sup.-1]).sup.n] [member of] [B.sub.3]. Figure 2 illustrates THK(3, 2) along with [[sigma].sub.1], [[sigma].sub.2], and their inverses.

[FIGURE 2 OMITTED]

See Birman (1974) for further information on braids. The knot diagrams of THK(3, n) obtained by the braid closure of [([[sigma].sub.2] [[sigma].sub.1.sup.-1]).sup.n] [member of] [B.sub.3], will be called standard diagrams of THK(3, n), in the sequel.

The present article is a study of the Turk's Head knots on three strands in the spirit of Kauffman and Lopes (2008). The fact that the THK(3, n)'s are more complex than the T(2, n)'s turned this article into a harder project when compared to Kauffman and Lopes (2008). We remark in particular that the integration of a system of linear homogeneous equations over the modular integers falls outside the standard techniques of Linear Algebra, since in general the modular integers do not constitute a field. Nonetheless we are able to present a formula (see Theorem 1.1) for the number of r-colorings for the knot THK(3, n), for any positive integers n and r > 1. This corresponds to the integration of each system of linear homogeneous equations from an infinite family of such systems, over a generic ring of modular integers.

Here are the main results in this article. We remark that given two positive integers a, b, we let gcd(a, b) stand for their greatest common divisor. We further let a | b stand for a divides b and a | b stand for a does not divide b.

Theorem 1.1 Given positive integers n and r > 1, the number of r-colorings of THK(3, n), denoted [sharp][col.sub.r]THK(3, n), is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [u.sub.n] is the solution of the linear recurrence problem with "initial values"

-[U.sub.n] + [3u.sub.n]-2 - [u.sub.n]-4 = 0, [u.sub.-3] = -1, [u.sub.-2] = -1, [u.sub.-1] = 0, [u.sub.0] = 1.

We remark that the solution of this problem is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Corollary 1.1

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In particular, the determinant of a knot classifies the knots in the THK(3, n) family. Furthermore, for any k [member of] [Z.sup.+], 5 | det THK(3, 2k) and 5 [??] det THK (3, 2k + 1).

Corollary 1.2 There are non-trivial r-colorings of THK (3, n) if, and only if,

* gcd([u.sub.n - 1]) > 1 or

* n is even and 5 | r

Theorem 1.2 Let n and r be positive integers.

1.

2 | r and 3 | n if, and only if, [mincol.sub.r] THK (3, n) = 2.

2.

(2 [??] r or 3 [??] n) and 3 | r and 4 | n if, and only if, [mincol.sub.r] THK(3, n) = 3.

Minimum Number of Colors for THK(3, n)

3.

(2 [??] r or 3 [??] n ) and (3 [??] r or 4 [??] n) and (5 | r and 2 | n) or (7 | r and 8 | n)

if, and only if, [mincol.sub.r] THK(3, n) = 4.

4. If

(2 [??] r or 3 [??] n ) and (3 [??] r or 4 [??] n ) and (5 [??] r or 2 [??] n ) and (7 [??] r or 8 [??] n)

and (11 | r and 5 | n) than [mincol.sub.r] THK (3, n) = 5.

It is easy to see that each statement in Theorem 1.2 gives rise to infinitely many knots for which the minimum number of colors modulo infinitely many r's is exactly determined. For example, according to the statement 4., for any positive integers m and l, we have:

[mincol.sub.11 x 13], THK (3, 5 x [17.sup.m]) = 5.

We introduce the mapping [psi] which associates to each modulus r, the least positive integer n such that r | [u.sub.n - 1].

Definition 1.2 For any integer r > 1 set

[psi](r) := min{q [member of] [Z.sup.+] | r | [u.sub.q - 1] }.

When r is a prime other than 5, [psi](r) is the least number of [[sigma].sub.2][[sigma].sub.1.sup.-1] that should be juxtaposed in order to obtain a non trivial r-coloring, namely in THK(Z, [psi](r)). The first few values of the [psi] function are displayed in Table 2, right after the References to this article.

Theorem 1.3 Let p be a prime greater than 11.

1. Assume [psi](p) is odd.

(a) If 5[[p-1]/[2]] [equivalent to] -1, then [mincol.sub.p] THK(3, [psi](p)) [less than or equal to] [[p+1]/[2]] (mod p).

(b) If 5[[p-1]/[2]] = 1, then [mincol.sub.p] THK(3, [psi](p)) [less than or equal to] [[p-1]/[2]] (mod p).

2. Assume [psi](p) is even.

(a) If 4 | [psi](p), then [mincol.sub.p] THK (3, [psi](p)) [less than or equal to] [psi](P) - 1.

(b) If 4 | [psi](p), then [mincol.sub.p] THK(3, [psi](p)) [less than or equal to] [psi](p) - 5.

Definition 1.3 For any positive integers n and r, such that gcd([u.sub.n]_1, r) > 1, set to be the least common prime factor (greater than 5) of r and [u.sub.n - 1], which minimizes [psi].

Corollary 1.3 Let r and n be positive integers such that gcd([u.sub.n - 1], r) > 1. Set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then,

1. Assume [psi](p) is odd.

(a) If 5[[p-1]/[2]] [equivalent to] -1, the [nmincol.sub.r] THK (3, n) [less than or equal to] [[p+1]/[2]] (mod p).

(b) If [[p-1]/[2]] [equivalent to] 1, then [mincol.sub.r] THK (3, n) [less than or equal to] [[p-1]/[2]] (mod p).

2. Assume [psi](p) is even.

(a) If 4 | [psi](p), then [mincol.sub.r] THK (3, n) [less than or equal to] [psi](p) - 1.

(b) If 4 | [psi](p), then [mincol.sub.r] THK (3, n) [less than or equal to] [psi](p) - 5.

We establish below (Corollary 2.4) that, for prime p [not equal to] 5, if [psi](p) is odd then it is bounded above by (p + l)/2, whereas if [psi](p) is even, it is bounded above by p + 1. Then, for the odd p case, Theorem 1.3 provides good estimates, roughly half the number of colors available (p). On the other hand, for the even [psi](p) case, the estimates are coarser. The worst case is [psi](p) = p + 1 where the results provide an estimate which equals the number of colors available (which is p).

We then ran a program in Mathematica to have an idea of how many times this [psi](p) = p + 1 situation occurs over all primes p. Our program did this for the first 100,000 primes in steps of 10,000. The results are displayed in Table 1. This seems to indicate that around 40% of the primes, p, lead to [psi](p) = p + 1.
[N.sup.P]                     10,000       20,000        30,000
[N.sub.[psi](p)]               3,969         7910        11,853
[N.sub.[psi](p)]/[N.sup.p]         0.3969       0.3955        0.3951

[N.sup.P]                     40,000       50,000        60,000
[N.sub.[psi](p)]              15,760       19,738        23,661
[N.sub.[psi](p)]/[N.sup.p]         0.394        0.39476       0.39435


[N.sup.P]                     70,000          80,000
[N.sub.[psi](p)]              27,589          31,499
[N.sub.[psi](p)]/[N.sup.p]         0.394129        0.393738


[N.sup.P]                     90,000         100,000
[N.sub.[psi](p)]              35,404          39,343
[N.sub.[psi](p)]/[N.sup.p]         0.393378        0.39343

Tab. 1: [N.sup.p] is the number of consecutive primes; [N.sub.[psi](p)]
is the number of primes p for which [psi](p) = p + 1.


We ran another program to realize what is the percentage of distinct colors used over the total number of colors for the colorings we used in this situation. These colorings were induced by introducing either colors 0, 1, 0 or colors 1, 2, 0 on the top of the standard diagram of the THK(Z, [psi](p)) for each of these p's such that [psi](p) = p + 1 and > 7. For the first 100,000 such cases there was a minimum of 69.2308% and a maximum of 75.0004% of colors used.

In Section 2 we prove Theorems 1.1, 1.2, and 1.3, along with their corollaries.

2 Proofs

In this Section we provide the proofs of the results stated in the Introduction.

2.1 Proof of Theorem 1.1

In this Subsection we prove Theorem 1.1, which yields a formula for the number of r-colorings of THK(3, n), along with its corollaries. For that, we start by studying the propagation of colors a, 6, c of an r-coloring, down [([[sigma].sub.2][[sigma].sub.1.sup.-1]).sup.n] (in Figure 3 the case n = 1 is displayed). We recall that this means that at each crossing, the equation "twice the color on the over-arc equals the sum of colors on the under-arcs" is satisfied modulo r. At each crossing, we use this rule to write the color of the lower under-arc in terms of the color of over-arc and of the color of the upper under-arc.

[FIGURE 3 OMITTED]

In Figure 3 we illustrate the propagation of colors a, b, c down [([[sigma].sub.2][[sigma].sub.1.sup.-1]).sup.1], which, algebraically, translates into the system of equations 1.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

In the sequel, we will use the following notation.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We thus start by setting [x.sub.0] = a, [y.sub.0] = b, [z.sub.0] = c at the top of the braid, from left to right; we call this the color input. The colors [x.sub.n], [y.sub.n], [z.sub.n] (from left to right) after [([[sigma].sub.2][[sigma].sub.1.sup.-1]).sup.n] are:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this way, each r-coloring of THK (3, n) will correspond to a solution of the system of linear equations, over the modulus r:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and vice-versa.

In the sequel we simplify the matrix [C.sup.n].

Proposition 2.1 Consider THK(3, n) given by the braid closure of [([[sigma].sub.2][[sigma].sub.1.sup.-1]).sup.n]. Let n be a non-negative integer. If the top strands of [([[sigma].sub.2][[sigma].sub.1.sup.-1]).sup.n] are endowed with colors a, b and c (from left to right) then the following hold:

(i) [x.sub.n] - [y.sub.n] + [z.sub.n] = a - b + c

(ii) [x.sub.n] = [4x.sub.n-1] - [4x.sub.n-2] + [x.sub.n-3];

[y.sub.n] = [4y.sub.n-1] - [4y.sub.n-2] + [y.sub.n-3];

[z.sub.n] = [4z.sub.n-1] - [4z.sub.n-2] + [z.sub.n-3].

(iii) [x.sub.n] = [3x.sub.n-1] - [x.sub.n-2] - [x.sub.0] + [y.sub.0] - [z.sub.0];

[y.sub.n] = [3y.sub.n-1] - [y.sub.n-2] - [x.sub.0] + [y.sub.0] - [z.sub.0];

[z.sub.n] = [3z.sub.n-1] - [z.sub.n-2] - [x.sub.0] + [y.sub.0] - [z.sub.0].

Proof: To prove (i) we note that:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this way, we obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In order to prove (ii) we note that, the characteristic polynomial of C is

det(C - [I.sub.3]x) = -[x.sup.3] + [4x.sup.2] - 4x + 1.

Via the Cayley-Hamilton Theorem,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which amounts to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus yielding the indicated recurrence relations for [x.sub.n], [y.sub.n], [z.sub.n].

To prove (iii) we start by using:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where in the last equality (i) was used. This concludes the proof of Proposition 2.1.

Noting that C is invertible, the preceding recurrence relations allows us to define [x.sub.n], [y.sub.n], [z.sub.n] for negative values with the relation,

[x.sub.n-3] = [4x.sub.n-2] - [4x.sub.n-1] + [x.sub.n], (2)

and analogously for [y.sub.n] and [z.sub.n]. We may, thus, define, for any n [member of] Z,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We remark that the coefficients of a, b, c in the leftmost color (as well as in the middle and in the rightmost colors), satisfy a recurrence relation similar to the one [x.sub.n] does.

Definition 2.1 Set:

[x.sub.n] = [a.sub.n]a + [b.sub.n]b + [c.sub.n]c,

[y.sub.n] = [a.sup.'.sub.n]a + [b.sup.'.sub.n]b + [c.sup.'.sub.n]c,

[z.sub.n] = [a.sup.".sub.n]a + [b.sup.".sub.n]b + [c.sup.".sub.n]c.

We have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Corollary 2.1 Keeping the conditions of the proposition above:

(i) [a.sub.n] = [4a.sub.n-1] - [4a.sub.n-2] + [a.sub.n-3];

[b.sub.n] = [4b.sub.n-1] - [4b.sub.n-2] + [b.sub.n-3];

[C.sub.n] = [4c.sub.n-1] - [4c.sub.n-2] + [C.sub.n-3];

(ii) [a.sub.n] = [3a.sub.n-1] - [a.sub.n-2] - 1;

[b.sub.n] = [3b.sub.n-1] - [b.sub.n-2] + 1;

[c.sub.n] = [3c.sub.n-1] - [c.sub.n-2] 1.

Proof: We will prove the proposition for the sequence [a.sub.n], since the other proofs are analogous. Consider the matrix [C.sup.n]. Then, one realizes [a.sub.n] is the leftmost color after [([[sigma].sub.2][[sigma].sub.1.sup.-1]).sup.n] when [x.sub.0] = 1, [y.sub.0] = 0, [z.sub.0] = 0 i.e., [x.sub.n] = [a.sub.n] when [x.sub.0] = 1, [y.sub.0] = 0, [z.sub.0] = 0. Applying Proposition 2.1, we obtain the desired relations.

More generally, the entries of [C.sup.n] satisfy a recurrence relation similar to the one [x.sub.n], [y.sub.n], and [z.sub.n] do, as [c.sub.ij.sup.n], the entry ij of [C.sup.n], can be interpreted as the colors of the i - th strand with the top colors equal to zero except for the j - th strand that takes 1 as initial color.

Before proceeding to the next result, let us look at the first few powers of C:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Corollary 2.2 The powers of the matrix C satisfy:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: We already saw that the entries of the matrices [C.sup.n] satisfy a specific recurrence relation, which is similar to the ones [a.sub.n], and [b.sub.n] do. So, it is enough to verify that the first 3 powers of C satisfy the expression above, and to use induction to establish the result. We leave the details to the reader.

We recall we want to establish a formula which yields the number of r-colorings of THK(3, n). In order to do that, we solve the following system of linear equations over [Z.sub.r]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

which, upon rewriting and applying Corollary 2.2 yields the following system of linear homogeneous equations over [Z.sub.r] :

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

The coefficient matrix in (4) can be further simplified as we will now show.

Corollary 2.3 For any positive integer n:

[a.sub.n] - [a.sub.n-1] - [b.sub.n] = 1

[b.sub.n] - [b.sub.n-1] - [a.sub.n-1] = -1

Proof: This follows from Corollary 2.2. We remark that [a.sub.n], [a.sub.n-1] and -[b.sub.n] are the bottom colors, from left to right, respectively, of the braid [([[sigma].sub.2][[sigma].sub.1.sup.-1]).sup.n] when [x.sub.0] = 1, [y.sub.0] = 0 and [z.sub.0] = 0. Therefore, by Proposition 2.1, we have:

[a.sub.n] - [a.sub.n-1] + (-[b.sub.n]) = 1 - 0 + 0 = 1.

Also, [b.sub.n], [b.sub.n-1] and -[a.sub.n-1] are the bottom colors, from left to right, respectively, of the strings of the braid [([[sigma].sub.2] [[sigma].sub.1.sup.-1]).sup.m] when [x.sub.0] = 0, [y.sub.0] = 1 and [z.sub.0] = 0. Again by Proposition 2.1:

[b.sub.n] - [b.sub.n-1] + (-[a.sub.n-1]) = 0 - 1 + 0 = -1.

Now, by Corollary 2.3 we may conclude that:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this way, by adding the first line to and subtracting the second line from the third line in the square matrix in (4), we obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We now define the sequences [u.sub.n] and [v.sub.n] which will relate to [a.sub.n] and [b.sub.n].

Definition 2.2 Let [u.sub.n] and [v.sub.n] be sequences defined recursively as follows:

[u.sub.-3] = -1, [u.sub.-2] = -1, [u.sub.-1] = 0, [u.sub.0] = 1, and if n [greater than or equal to] 1 [u.sub.n] = [3u.sub.n-2] - [u.sub.n-4].

and,

[u.sub.-3] = 7, [u.sub.-2] = 2, [u.sub.-1] = 3, [u.sub.0] = 1, and if n [greater than or equal to] 1 [u.sub.n] = [3u.sub.n-2] - [u.sub.n-4].

Proposition 2.2 For n [member of] N we have:

[a.sub.n] = [u.sub.n][u.sub.n], [b.sub.n] = [u.sub.n]-[2u.sub.n-1],

[a.sub.n-1] = [u.sub.n-1][u.sub.n+1], [b.sub.n-1] = [u.sub.n][u.sub.n-3].

Proof: First we need to verify the cases n = 0, 1, 2, 3, 4. We leave this task to the reader. We will prove by induction that [a.sub.n] = [u.sub.n][u.sub.n] and ([a.sub.n] - 1) = [u.sub.n-1][1u.sub.n+1]. For n [greater than or equal to] 0 we assume the validity of the hypothesis for n, n + 1, n + 2, n + 3 and n + 4 and conclude that it is also valid for n + 5. Proposition 2.1 will be used throughout the following calculations.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This ends the first part of the proof. Now, let us prove by induction that [b.sub.n] = [u.sub.n-2][u.sub.n-1] and ([b.sub.n - 1]) = [u.sub.n][u.sub.n-3]. We assume again for n [greater than or equal to] 0 the validity of the hypothesis for n, n + 1, n + 2, n + 3 and n + 4, concluding that it is valid for n + 5.

[u.sub.n]+[3u.sub.n+4] = [u.sub.n+3]([3u.sub.n+2] - [u.sub.n]) = [3b.sub.n+4] - ([b.sub.n+3] - 1) =

= [3b.sub.n+4] - [b.sub.n+3] + 1 = [b.sub.n+5].

[u.sub.n+5][u.sub.n+2] = ([3u.sub.n+3] - [u.sub.n+1])[u.sub.n+2] = [3b.sub.n+4] - [b.sub.n+3]=

=([3b.sub.n+4] - [b.sub.n+3] + 1) -1 = [b.sub.n+5] - 1.

This ends the proof.

The linear homogeneous system of equations over [Z.sub.r] is now equivalent to:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

By performing elementary operations on the lines of the matrix we obtain an even simpler coefficient matrix:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore, for n odd, the coefficient matrix in (5) simplifies to:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

We can now establish the formulas for the number of the colorings in terms of r and [u.sub.n-1] in Theorem 1.1. We state that part here again as Proposition 2.3 below for the reader's convenience. We recall we let gcd(a, b) stand for the greatest common divisor of the positive integers a and b.

Proposition 2.3 Given positive integers n and r > 1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: Let us suppose that n is odd. The color input a, b, c in [([[sigma].sub.2] [[sigma].sub.1.sup.-1]).sup.n] induces an r-coloring in THK (3, n)if and only if:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We now count the solutions of this linear homogeneous system of equations over [Z.sub.r] (see Kauffman and Lopes (2008), Claims 2.1 and 2.2). The third equation does not impose any restrictions on a, b, or c.

The second equation, [[u.sub.n-1](-b + c) =.sub.r] 0, yields b - c = k [[r]/[gcd([u.sub.n-1],r)]] for k = 0, 1,..., gcd([u.sub.n-1], r) - 1. Note that for each positive integer a,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Moreover, from the first equation, a- c = k [[r]/[gcd([u.sub.n-1],r)]]. So, both b and a have ([u.sub.n-1], r) possibilities, compatible with each of the r possibilities for c. We conclude that the indicated system of equations has r gcd[([u.sub.n-1], r).sup.2] solutions over [Z.sub.r].

Let us now suppose that n is even. The color input a, b, c in [([[sigma].sub.2][[sigma].sub.1.sup.-1]).sup.n] induces an r-coloring in THK(3, n)if and only if:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Arguing as above, we conclude that the number of solutions over [Z.sub.r] of the indicated system of equations is r x gcd([5u.sub.n-1], r) x gcd([u.sub.n-1], r), for even n. This concludes the proof.

Proposition 2.4 For n [member of] Z,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

Proof: The sequence [u.sub.n] is the solution of the linear difference equation with the "initial values":

-[u.sub.n] + [3u.sub.n-2] - [u.sub.n-4] = 0, [u.sub.-3] = -1, [u.sub.-2] = -1, [u.sub.-1] = 0, [u.sub.0] = 1.

The general method of solving this type of initial value problem can be found in Henrici (1964), for instance. We leave the details to the reader.

This concludes the proof of Theorem 1.1 and of Corollary 1.2.

The formulas for the determinants in Corollary 1.1 follow from the observation of the matrices (6) for the odd n case and (7) for the even n case; the fact that these determinants are always greater than zero follows from proving by induction that

[u.sub.n] > 0 and [u.sub.n] - [u.sub.n-2] > 0 for all n > 2.

2.2 Proof of Theorem 1.2

2.2.1 Preliminaries

We first establish Propositions 2.5, 2.6, 2.7 for they will be useful in the sequel.

Proposition 2.5 Suppose a knot admits a non-trivial s-coloring and s | r. Then this knot also admits a non-trivial r-coloring.

Proof: Since s | r, then the set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is closed with respect to the a * b := 26 - a mod r operation. Moreover, the mapping

f : [Z.sub.s] [right arrow] [Z.sub.r]

i [right arrow] i[[r]/[s]]

is injective and preserves the * operation. In this way, if ([i.sub.1], [i.sub.2],..., [i.sub.N]) is the sequence of colors mod s one should assign to the sequence of arcs in a knot diagram of the knot under study to obtain a non-trivial s-coloring, then the sequence ([i.sub.1][[r]/[s]], [i.sub.2][[r]/[s]],..., [i.sub.N][[r]/[s]]) assigned to the same sequence of arcs, represents a non-trivial r-coloring of the same knot.

Proposition 2.6 Consider the positive integers c, k, n, and integer r > 1. Suppose the standard diagram of THK(3, n) admits a non-trivial r-coloring with c colors. Then the standard diagram of THK(3, kn) also admits a non-trivial r-coloring with c colors.

Proof: If the standard diagram of THK(3, n) admits a non-trivial r-coloring with c colors, we consider this coloring in [([[sigma].sub.2] [[sigma].sub.1.sup.-1]).sup.n] i.e., before braid closure. In this way, the sequence of colors on the top arcs (from left to right) equals the sequence of colors on the bottom arcs (from left to right). We then juxtapose k copies of this colored [([[sigma].sub.2] [[sigma].sub.1.sup.-1]).sup.n]. Upon taking its closure we obtain a non-trivial r-coloring of THK(3, kn).

Definition 2.3 A knot is said split if there exist two disjoint open balls in 3-space, say [N.sub.1] and [N.sub.2], such that the knot is deformable into a knot, say K, such that

K [subset] [N.sub.1] [union] [N.sub.2], K [intersection] [N.sub.1] [not equal to] 0, K [intersection] [N.sub.2] [not equal to] 0.

Otherwise, the knot is said non-split.

Proposition 2.7 For any positive integer n, THK(3, n) is non-split.

Proof: Fix a positive integer n. If THK(3, n) were split, then for any integer r > 1, there would be at least [r.sup.2] r-colorings. Each of these [r.sdup.2] r-colorings stands for the r-coloring which results from trivially r-coloring each of the two open balls the knot splits into. But, setting r equal to a prime larger than both [u.sub.n-1] and 5, yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Hence, THK(3, n) is non-split.

2.2.2 Further analysis of the [u.sub.n] sequence and the [psi] mapping: towards the proof of Theorem 1.2

In order to prove the "if" parts in Theorem 1.2, and to prove Theorem 1.3, we analyze further the sequence [u.sub.n].

Proposition 2.8 For n [member of] Z we have:

[u.sub.2n] = [u.sub.2n] + 1 + [u.sub.2n - 1],

[u.sub.2n+1] = [[[u.sub.2n+2] + [u.sub.2n]]/[5]].

Proof: We only prove the inductive step:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proposition 2.9 (i) If m is even, or n is odd, then:

(ii) If m is even and n is odd, then:

Proof: To prove (i) let us first suppose m is an arbitrary integer, we have:

[u.sub.m+1] = [u.sub.m+1] x 1 - [u.sub.m-1] x 0 = [u.sub.m] + 1[u.sub.1] - [u.sub.m-1][u.sub.-1],

[u.sub.m+3] = [u.sub.m+1] x 3 - [u.sub.m-1] x 1 = [u.sub.m] + 1[u.sub.3] - [u.sub.m-1][u.sub.-1].

Also, if m is even, by Proposition 2.8, we have:

[u.sub.m] = [u.sub.m+1] x 1 - [u.sub.m-1] x (-1) = [u.sub.m+1][u.sub.0] - [u.sub.m-1][u.sub.2],

[u.sub.m+2] = [u.sub.m+3] + [u.sub.m+1] = [u.sub.m+1] x 4 - [u.sub.m-1] x 1 = [u.sub.m+1][u.sub.m+1][u.sub.2] - [u.sub.m-1][u.sub.0].

Now, fixed m, we will do induction on n. Let us suppose that the equation (9) is true for a given m and n = k, k + 2, then:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

So, equation (9) is also verified forn = k - 2, k + 4. From here we may conclude that when m is even equation (9) is true for every n, and when m is odd equation (9) is true for n odd.

To prove (ii) we use (i), and Proposition 2.8:

We repeat here the definition of the [psi] mapping for the reader's convenience.

Definition 2.4 For any integer r > 1 set

[psi](r) := min{q [member of] [Z.sup.+] | r | [u.sub.q-1]}.

Proposition 2.10 [psi] well-defined.

Proof: We will prove that, for any integer r > 1, {q [member of] [Z.sup.+] | r | [u.sub.q-1]} 0. Since it is a subset of [Z.sup.+], then it has a minimum.

Fix an integer r > 1 and set [U.sub.n] = ([u.sub.n], [u.sub.n+1], [u.sub.n+2], [u.sub.n+3]) a sequence in [Z.sup.4.sub.r] formed by consecutive terms of the u sequence read mod r. Let us consider the first [r.sup.4] + 1 [U.sub.i]'s, i = 0,..., [r.sup.4]. Since [Z.sup.4] has [r.sup.4] elements, by the Pigeonhole Principle, there are integers i, j, such that [U.sub.i] = [U.sub.j], 0 [less than or equal to] i < j [less than or equal to] [r.sup.4]. Hence, as [??] can be defined recursively by the previous four terms of the same sequence, we conclude that [??] (mod r) is eventually periodic with period p|(j - i). Since [u.sub.n] = [3u.sub.n-2] - [w.sub.n-4] is equivalent to [u.sub.-4] = [3u.sub.n-2] - [u.sub.n], it follows that [??] (mod r) has to be periodic with period p. Then, [[u.sub.j-i-1] [equivalent to].sub. r] [[u.sub.-1] [equivalent to].sub. r] 0 and {q [member of] [Z.sup.+] | r | [u.sub.q-1]} [??] (j - i) is non-empty, ending the proof.

Proposition 2.11 r | [u.sub.m-1] if and only if [psi](r) | m.

Proof: Upon extending [u.sub.n] to the negative integers using the recurrence relation [u.sub.-4] = [3u.sub.n-2] - [u.sub.n], we note that [u.sub.n] = -[u.sub.-n-2].

We start by verifying that [u.sub.n] = -[u.sub.-n-2]. This is done using the fact that [u.sub.1] = -[u.sub.-3] = 1, [u.sub.0] = -[u.sub.-2] = 1 and [u.sub.-1] = -[u.sub.-1] = 0. After this, we leave it as an exercise to use induction on n to obtain the desired conclusion.

Claim 2.1 If [u.sub.[psi](n)-1] - 1 | [u.sub.l-1] then [u.sub.[psi](n)-1] | [u.sub.l[+ or -][psi](n) - 1].

Proof: If [psi](n) is even or (l - 1) is odd, by Proposition 2.9 we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Otherwise, if [psi](n) is odd and (l - 1) is even, by Proposition 2.9 we have:

Either way, if [u.sub.[psi](n)-1] | [u.sub.l-1], then [u.sub.[psi](n)-1] | [u.sub.l[+ or -](n)-1]. This concludes the proof of the Claim.

Resuming the proof of Proposition 2.11, Claim 2.1 implies, by setting n = r, m = [psi](r) and using induction, that [u.sub.[psi](n)-1] | [u.sub.k[psi](r)-1]for any k [member of] Z. Since r | [u.sub.[psi](r)-1], by definition, we have thus proved that if [psi](r) | m then r | [u.sub.m-1].

Now assume r | [u.sub.m-1] and let R be the remainder of the division of m by [psi](r). Then there exists q [member of] Z such that r | [u.sub.q[psi](r)+R-1] | [u.sub.(q-1)[psi](r)+R-1] | x x x | [u.sub.R-1] invoking the Claim 2.1 in the last passages. Hence, by definition of [psi](r), we get R = 0, concluding the proof of the Proposition.

2.2.3 The proof of Theorem 1.2

The proof of Theorem 1.2 now follows easily thanks to Theorem 2.1 below. We refer the reader to Satoh (2009) and Oshiro (2010) for statement 3., and to Lopes and Matias (2012) for statement 4. We remark that, given two positive integers a, b, we let (a, b) stand for 1 if a and b are relatively prime, otherwise, we let (a, b) stand for their least common prime factor.

Theorem 2.1 Let r be an integer greater than 1.

Let L be a non-split link.

1. [??] if, and only if, [mincol.sub.r] L = 2,

2. [??] if, and only if, [mincol.sub.r] L = 3.

Furthermore, if det L [not equal to] 0 then:

3. [??] [member of] {5, 7} if, and only if, [mincol.sub.r] L = 4,

4. [??] > 7, if, and only if, [mincol.sub.r] L [greater than or equal to] 5.

Proof: (of Theorem 1.2)

1. Knowing that [psi](2) = 3,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2. Knowing that 2 [??] r or 3 [??] n and [psi](3) = 4,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3. The argument for this instance mimics the ones used in the preceding two instances. We leave the details to the reader.

4. The right-hand side of Figure 5 shows an 11-coloring of THK(3, n) with 5 colors. Hence, Proposition 2.5, Proposition 2.6 along with the preceding instances, imply that if 11 | r and 5 | n (and neither r nor n comply with the preceding instances) then [mincol.sub.r] THK (3, n) = 5.

2.3 Proof of Theorem 1.3

2.3.1 Preliminaries

After experimenting with r-colorings of the knots THK(3, n)'s for small values of r and n we came up with the following examples, displayed in Figures 4, 5, and 6. Figures 4, 5, and 6 are to be considered upon closure of the braids therein. We do not depict the closure of these braids in order not to over-burden the figures. Inspection of some cases displayed in Figures 4, 5, and 6 shows we have some control on the colors down the right hand-side of the standard diagrams with respect to the left-hand side. This allows us to decrease the number of colors needed to produce a non-trivial coloring.

Consider the 11-coloring of THK(3, 5) (right-hand side of Figure 5). The sequence of colors down the left-hand side i.e., the ([x.sub.n]) sequence for 0 [less than or equal to] n [less than or equal to] 4, call it L, is

L = (1, 2, 0, 4, 7).

The sequence of colors down the middle i.e., the ([y.sub.n]) sequence for 0 [less than or equal to] n [less than or equal to] 4, call it M, is M = (7, 1, 2, 0, 4).

Clearly, M is a circular shift of L, since [y.sub.i+1] = [x.sub.i] for i = 0, 1, 2, 3, 4, mod 5. This is a consequence of the arrangement of the arcs in any standard diagram of THK (3, n). Hence, the equality of the sequences L and M modulo circular shift is true for any such diagram.

[FIGURE 6 OMITTED]

Let us consider now the sequence of colors down the right-hand side i.e., ([z.sub.n]) for 0 [less than or equal to] n [less than or equal to] 4, call it R, of the 11-coloring of THK(3, 5) (right-hand side of Figure 5):

R= (0, 4, 7, 1, 2).

Then R is a circular shift of L but now this is not a general feature of non-trivial r-colorings on standard diagrams of THK(3, n)'s (see, for instance, the 5-coloring of THK(Z, 2) on the right-hand side of Figure 4, or the 7-coloring of THK(3, 8) in Figure 6).

Bearing in mind that if gcd(r, [u.sub.n-1]) > 1, there is a non-trivial r-coloring of THK(3, n) (Corollary 1.2), then, provided r is prime, [psi](r) yields the least number of [[sigma].sub.2] [[sigma].sub.1.sup.-1]'s we have to juxtapose in order to obtain a non-trivial r-coloring for a Turk's head knot on three strands, namely THK(3, [psi](r)). For prime r > 5 and odd [psi](r), we construct a non-trivial r-coloring on thestandard diagram of THK(3, [psi](r)) such that the R sequence is a circular shift of the L sequence (Theorem 1.3). There are, on average, two arcs per [[sigma].sub.2] [[sigma].sub.1.sup.-1] in a standard diagram of THK(Z, n). When R is a circular shift of L, we use only one color per [[sigma].sub.2] [[sigma].sub.1.sup.-1], on average i.e., we use only [psi](r) colors. This constitutes a reduction in half on the number of colors with respect to the worst case (different arcs, different colors). Moreover, we show that, for prime r > 5

[psi](r) | (r + 1) or [psi](r) | (r - 1),

so that, if [psi](r) is odd, then [psi](r) [less than or equal to] [[r+1]/[2]] or [psi](r) [less than or equal to] [[r-1]/[2]] (Corollary 2.4, below). This guarantees also that we are using roughly half of the colors available, when r > 5 is prime and [psi](r) is odd.

On the other hand, for prime r > 5 with [psi](r) even, we show below (Theorem 1.3) that the input color (0, 1, 0) induces a coloring whose number of colors is less than [psi](r) - 1. Here however, it may happen that [psi](r) = r + 1, so that the estimate equals the total number of colors available.

We develop these ideas below.

2.3.2 Further analysis of [u.sub.n]

In order to carry out the ideas expressed above, we need a deeper analysis of the sequence [u.sub.n]. This is the goal of the current Subsection.

Proposition 2.12 Let p [not equal to] 5 be an odd prime. Then:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: As [u.sub.n] is a sequence taking on integer values we may conclude that the coefficients of [??], after applying Binomial Theorem to the expression (8), will sum zero. Also, one may see that [??] if and only if j = 0, 1, 2, p, p + 1, p + 2 and [??] if and only if j = 0, p. By Fermat's Little Theorem we have [5.sup.p-1] = 1, which implies 5 [[p-1]/[2]] [equivalent to] 1 or 5[[p-1]/[2]] [equivalent to] - 1 (mod p). Therefore, modp:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is equivalent to 5 [[p-1]/[2]] [equivalent to] - 1, mod p.

Assume, now, 5[[p-1]/[2]] [equivalent to] 1, mod p. Then by Euler's Criterion there exists [alpha] [member of] Z, such that [[alpha].sup.2] [equivalent to] 5. As in (8) the coefficients of [??] will sum zero, and we obtain, mod p:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Multiplying both sides by 2[p+1]/[2] [alpha][(1 + [alpha]).sup.[[p+1]/[2]]], applying Fermat's Little Theorem and noting p [??] ([alpha] [+ or -] 1) for [[alpha].sup.2] [equivalent to] 5 [not equal to] 1:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which implies u [[p-3]/[2]] = 0, mod p, concluding the proof.

Corollary 2.4 Let p [not equal to] 5 be an odd prime. Then, mod p:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In particular, when [psi](p) is odd, then [psi](p) [less than or equal to] (p+ l)/2.

Proof: It is a straightforward application of Propositions 2.11 and 2.12

Proposition 2.13 Let p be a prime greater than 5.

1. If [psi] (p) is odd then [mincol.sub.p] THK (3, [psi](p)) [less than or equal to] [psi](p),

2. If [psi] (p) is even then,

(a) If 4 | [psi](p), then [mincol.sub.p] THK (3, [psi](p)) [less than or equal to] [psi](p) - 1.

(b) If 4 | [psi](p), then [mincol.sub.p] THK (3, [psi](p)) [less than or equal to] [psi](p) - 5.

Proof: Let us first suppose [psi](p) is odd, and set a = 1, c = 0 and b arbitrary, for the moment (Figure 7). We will show that b can be chosen so that the R sequence i.e., the sequence ([z.sub.n])|0[less than or equal to]n[less than or equal to][psi](p), is a circular

[FIGURE 7 OMITTED]

shift of the L sequence i.e., the sequence ([x.sub.n]) |0[less than or equal to]n[less than or equal to][psi](p), yielding the required result. As we saw above, in the beginning of this Subsection, this implies that the number of colors is bounded above by [psi](p).

By Proposition 2.1:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

and similarly for [y.sub.k], [z.sub.k]. In particular, the above relations tell us that any term of [x.sub.k] (respect., [z.sub.k]) is obtained from the preceding two terms of the sequence. We then focus on two consecutive terms of the x-sequence, ([x.sub.k], [x.sub.k+1]) and we will later equate a certain pair of them to ([z.sub.0], [z.sub.1]) = (0, -b) in order to obtain the equality between the R and L sequences, modulo circular shift.

The expressions in (10) lead to:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By induction one can prove that:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and taking determinants on both sides of the preceding equation we obtain:

1 = -[u.sub.2k+1][u.sub.2k-3] + [u.sub.2k.sup.2-1].

In order for L to be a circular shift of R we set [x.sub.k+1] = [z.sub.1] = -6, [x.sub.k] = [z.sub.0] = 0. Then:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which is equivalent to:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

The determinant of the coefficient matrix in (11) is given by:

-[u.sub.2k+1][u.sub.2k-3] + [u.sub.2k-1.sup.2] - [2u.sub.2k+1] - [u.sub.2k-3] + [2u.sub.2k-1] - 1=

= 1 + (-[u.sub.2k-3] + [3u.sub.2k-1] - [u.sub.2k+1]) - [u.sub.2k+1] - [u.sub.2k-1] - 1 = -([u.sub.2k+1] + [u.sub.2k-1] = -[u.sub.2k].

We then set k = [[[psi](p)-1]/[2]] SO that 2k + 1 = [psi](p). Then [u.sub.2k] [equivalent to] 0, mod p, by definition of [psi], and the kernel associated to the system (11) is non-trivial. If the non-null vectors of this kernel had equal coordinates then in particular,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and, by Proposition 2.8, as [psi](p) is odd:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now, [2U.sub.[PSI](p)-2] =p 0, only if p = 2 (in which case the proposition is easily verified, as [psi](2) = 3 [greater than or equal to] 2), or p | [u.sub.[psi](p)-2], following from Proposition 2.11 that [psi](p) | [psi](p) - 1, which implies [psi](p) = 1 and p | [u.sub.0] = 1, contradicting the fact that p is prime. We can thus assume that non-trivial elements in the indicated kernel have distinct coordinates, say (r, s) with r [not equal to] s mod p.

The vector [[((r - s).sup.-1]r, [(r - s).sup.-1]s) =.sub.p] (r', s') also belongs to this kernel and satisfies r' - s' = 1. Therefore b = s' is a solution to equation (11). We conclude that, for the top colors (1, s', 0), the rightmost and leftmost arcs have equal colors in pairs. Therefore, given the recurrence relation satisfied by the colors on each side, the colors used in the leftmost, middle, and rightmost arcs are the same and we use, at most, [psi](p) colors.

Let us now suppose that [psi](p) is even. By Proposition 2.8 we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

as p [not equal to] 5. Remember that [u.sub.0] = 1 = -[u.sub.-2]. So, for some integer [alpha] we have [u.sub.[psi](p)-2] =P [[alpha]u.sub.0] and [[u.sub.[psi](p)] =.sub.p] [[alpha]u.sub.-2] Furthermore, and as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

one can easily see that,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Then [??]. We will now show that [alpha[equivalent to]] = 1, mod p.

Assume to the contrary and suppose [alpha] [equivalent to] - 1. Then [u.sub.0] [equivalent to] - [u.sub.[psi](p)-2], [u.sub.2] [equivalent to] [3u.sub.0] - [u.sub.-2] [equivalent to] - [3u.sub.[psi](p)-2] + [u.sub.[psi](p)] [equivalent to] -[u.sub.[psi](p)-4] and, by applying Proposition 2.8 twice, we get [u.sub.1] = 1 = -[u.sub.[psi](p)-3]. Using the recurrence satisfied by [u.sub.n], we obtain,

[u.sub.-2+i] [equivalent to] -[u.sub.[psi](p)-i], i = 0, 1,..., [psi](p) + 2.

In particular, [alpha] = -1 implies [??], which contradicts the definition of [psi](p).

Thus [alpha] = 1 and [u.sub.[psi](p)-2] [equivalent to] 1 [equivalent to] -[u.sub.[psi](p)].

We note that ([x.sub.0], [y.sub.0], [z.sub.0]) = (0, 1, 0) induces a non-trivial p-coloring on THK(3, [psi] (p)), since, by definition, p | [u.sub.[psi](p)-1]. Then, ([x.sub.[psi](p)], [y.sub.[psi](p)], [z.sub.[psi](p)]) = (0, 1, 0).

Arguing as above in the odd [psi](p) case, we obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using these expressions along with [u.sub.[psi](p)-2] [equivalent to] 1 = -[u.sub.[psi](p)] and Proposition 2.8, we obtain the colors displayed in Figure 8.

By Proposition 2.1, the following hold:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [x.sub.1] = 0 = [x.sub.[psi](p)] and [x.sub.2] = 1 = [x.sub.[psi](p)-1], then, the sequence ([x.sub.i]) | 1[less than or equal to][psi](P) contains at most [[[psi](p)]/[2]] distinct terms.

[FIGURE 8 OMITTED]

Assume 4 | [psi](p) and consider the sequence ([z.sub.i]) |1[less than or equal to]i[less than or equal to] [[[psi](p)]/[2]] + 1 We have, [z.sub.1] = -1 = z[[[psi](p)]/[2]] +1 and [z.sub.2] = -2 = z [[[psi](p)]/[2]], then there are equal terms in two's. Since [[[psi](p)]/[2]] + 1 is odd, this means there is a central term, z [[[psi](p)]/[2]] + 1, and the remaining terms are equal in two's. Thus, this sequence contributes with [[[psi](p)]/[4]] + 1 distinct terms.

Now for the sequence ([z.sub.i]) \ [[[psi](p)]/[2]] + 2[less than or equal to]i[less than or equal to],[psi](p). Reasonmg as in the preceding case, this sequence has at most, [[[psi](p) - ([psi](p)/2+2)]/[2]] + 1 = [[[psi](p)]/[4]].

So, in this 4 | [psi](p) instance, the number of distinct colors is at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the -2 stems from the fact that 0 and -2 appear on both the x and the z sequences (see Figure 8).

Assume now 4 [??] [psi](p) and consider the sequence ([z.sub.i]) | 1[less than or equal to]i[less than or equal to] [[[psi](p)]/[2]] + 1 Here '[[[psi](p)]/[2]] + 1 is even, so this sequence is made up of [[[psi](p)/2+1]/[2]] pairs of equal terms. Moreover, there are two equal consecutive terms, Z[[[psi](p)/2+1]/[2]] = [[[psi](p)/2+3]/[2]] (see Figure 9, with c the common value). Given the arrangement of the arcs in these standard diagrams, this implies that the [[[psi](p)/2+1]/[2]] [equivalent to] c (see Figure 9). Using the coloring condition at the crossings and the recurrence relation [z.sub.k-2] = [3z.sub.k-1] - [z.sub.k] + 1, we obtain the other colors in Figure 9, which tell us that there are two colors in ([z.sub.i] |1[less than or equal to]i[less than or equal to] [[[psi](p)]/[2]] + 1 that already showed up in the x sequence: c and -1. Thus, the net contribution of ([z.sub.i]) |1[less than or equal to]i[less than or equal to][[[psi](p)]/[2]] + 1 is at most [[[psi](p)/2+1]/[2]] - 2.

Now, for the sequence ([z.sub.i]) |[[[psi](p)]/[2]]+2[less than or equal to]i[less than or equal to][psi](p) Again, we have an even number of terms, [[[psi](p)]/[2]] - 1, equal in two's. Since z [[[psi](p)]/[2]] + 2 [equivalent to] 0 [equivalent to] z [psi](p), which has already been accounted for in the x sequence, then we will consider only [??] pairs of terms. Moreover, there is again a phenomenon analogous to the one depicted in Figure 9, induced by the fact that there are two equal consecutive terms in the ([z.sub.i]) |[[[psi](p)]/[2]]+2[equivalent to]i[equivalent to][psi](p) sequence. This time is just the c that has to be considered. Moreover, we will now prove that this c is distinct from the c occurring in connection with the sequence ([z.sub.i]) |1[less than or equal to]i[less than or equal to][[[psi](p)]/[2]] + 1 If they were equal, since the next term in both subsequences, ([z.sub.i]) |1[less than or equal to]i[less than or equal to][[[psi](p)]/[2]]) and ([x.sub.i]) | [[[PSI](P)]/[2]] + 1[LESS THAN OR EQUAL TO]i [less than or equal to][psi](p), is - 1 (mod p), then, given the recurrence relation [z.sub.k] = [3z.sub.k-1] - [z.sub.k-2] + 1, then the subsequences would be equal. But they are not equal. Hence the net contribution of ([z.sub.i]) | [[[psi](p)]/[2]]+2[less than or equal to]i[less than or equal to][psi](p) to the total number of colors is at most [??].

Finally, the total number of colors in this 4 [??] [psi](p) instance is at most (recall that -2 shows up on both sides):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[FIGURE 9 OMITTED]

This concludes the proof for the [psi](p) even case, concluding the proof of Proposition 2.12.

2.3.3 Proof of Theorem 1.3 and Corollary 1.3

The proof of Theorem 1.3 is a straightforward application of Proposition 2.12.

As for proof of Corollary 1.3, given positive integers n and r > 1, we choose a common prime factor of r and [u.sub.n-1] (in order to ensure there are non-trivial colorings), which minimizes [psi] (in order to minimize the number of colors involved. Applying Propositions 2.6 and 2.5, we conclude the proof of Corollary 1.3.

Acknowledgements

PL. acknowledges support by the Fundacao para a Ciencia e a Tecnologia (FCT / Portugal). P.L. and J.M. acknowledge support by the Gulbenkian Foundation (Portugal) in connection with the 2008/2009 edition of the programme "Novos Talentos em Matematica".

References

M. Asaeda, J. Przytycki, and A. Sikora. Kauffman-Harary conjecture holds for Montesinos knots. J. Knot Theory Ramifications, 13(4):467-477, 2004.

J. Birman. Braids, links, and mapping class groups, volume 82 of Annals of Math. Studies. Princeton University Press, Princeton, N. J., 1974.

R. Fox. A quick trip through knot theory. In J. M. K. Fort, editor, Topology of 3-Manifolds and Related Topics, Georgia, pages 120-167. Prentice-Hall, 1961.

F. Harary and L. Kauffman. Knots and graphs I. Arc graphs and colorings. Adv. in Appl. Math., 22(3): 312-337, 1999.

P. Henrici. Elements of numerical analysis. John Wiley & Sons, Inc., New York-London-Sydney, 1964.

L. Kauffman. Knots and physics, volume 1 of Series on Knots and Everything. World Scientific Publishing Co., River Edge, NJ, 4th edition, 2013.

L. Kauffman and P. Lopes. On the minimum number of colors for knots. Adv. in Appl. Math., 40(1): 36-53, 2008.

L. Kauffman and P. Lopes. Determinants of rational knots. Discrete Math. Theor. Comput. Sci, 11(2): 111-122, 2009.

W. Lickorish. An introduction to knot theory, volume 175 of Graduate Texts in Mathematics. Springer Verlag, New York, 1997.

P. Lopes. Quandles at finite temperatures I. J. Knot Theory Ramifications, 12(2): 159-186, 2003.

P. Lopes and J. Matias. Minimum number of Fox colors for small primes. J. Knot Theory Ramifications, 21(3), 2012.

T. Mattman and P. Solis. A proof of the Kauffman-Harary conjecture. Algebr. Geom. Topol., 9:2027-2039, 2009.

K. Oshiro. Any 7-colorable knot can be colored by four colors. J. Math. Soc. Japan, 62(3):963-973, 2010.

D. Rolfsen. Knots and links. Chelsea. AMS, 1976.

M. Saito. The minimum number of Fox colors and quandle cocycle invariants. J. Knot Theory Ramifications, 19(11): 1449-1456, 2010.

S. Satoh. 5-colored knot diagram with four colors. Osaka J. Math., 46(4):939-948, 2009.

Pedro Lopes (1,2)

Joao Matias (2)

(1) Center for Mathematical Analysis, Geometry and Dynamical Systems, Instituto Superior Ticnico, University of Lisbon, Portugal

(2) Department of Mathematics, Instituto Superior Te'cnico, University of Lisbon, Portugal

received 4th Feb. 2012, revised 18th Jan. 2015, accepted 12th June 2015.
A Table of [psi]

Tab. 2: Table of [psi]. In bold: prime r's and their [psi]'s

 r   [psi](r)  r   [psi](r)   r    [psi](r)  r   [psi](r)   r  [psi](r)

 1     2     38       9      75    100     112     24     149    74
 2     3     39      28      76      9     113     38     150   300
 3     4     40      30      77     40     114     36     151    25
 4     3     41      20      78     84     115    120     152    18
 5    10     42      24      79     39     116     21     153    36
 6    12     43      44      80     60     117     84     154   120
 7     8     44      15      81    108     118     87     155    30
 8     6     45      60      82     60     119     72     156    84
 9    12     46      24      83     84     120     60     157   158
10    30     47      16      84     24     121     55     158    39
11     5     48      12      85     90     122     30     159   108
12    12     49      56      86    132     123     20     160   120
13    14     50     150      87     28     124     15     161    24
14    24     51      36      88     30     125    250     162    28
15    20     52      42      89     22     126     24     163   164
16    12     53      54      90     60     127    128     164    60
17    18     54      36      91     56     128     96     165    20
18    12     55      10      92     24     129     44     166    84
19     9     56      24      93     60     130    210     167   168
20    30     57      36      94     48     131     65     168    24
21     8     58      21      95     90     132     60     169   182
22    15     59      29      96     24     133     72     170    90
23    24     60      60      97     98     134    204     171    36
24    12     61      30      98    168     135    180     172   132
25    50     62      15      99     60     136     18     173   174
26    42     63      24     100    150     137    138     174    84
27    36     64      48     101     25     138     24     175   200
28    24     65      70     102     36     139     23     176    60
29     7     66      60     103    104     140    120     177   116
30    60     67      68     104     42     141     16     178    66
31    15     68      18     105     40     142    105     179    89
32    24     69      24     106     54     143     70     180    60
33    20     70     120     107     36     144     12     181    45
34    18     71      35     108     36     145     70     182   168
35    40     72      12     109     54     146    222     183    60
36    12     73      74     110     30     147     56     184    24
37    38     74     114     111     76     148    114     185   190
COPYRIGHT 2015 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Lopes, Pedro; Matias, Joao
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1USA
Date:Jul 1, 2015
Words:10363
Previous Article:Graph orientations and linear extensions.
Next Article:The game chromatic number of trees and forests.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters