# An Algorithm for Generating a Family of Alternating Knots

Authors: Carlos Velarde; Ernesto Bribiesca; Wendy Aguilar
Journal: ISRN Algebra
 (2012)

---

## Abstract

An algorithm for generating a family of alternating knots (which are described by means of a chain code) is presented. The family of alternating knots is represented on the cubic lattice, that is, each alternating knot is composed of constant orthogonal straight-line segments and is described by means of a chain code. This chain code is represented by a numerical string of finite length over a finite alphabet, allowing the usage of formal-language techniques for alternating-knot representation. When an alternating knot is described by a chain, it is possible to obtain its mirroring image in an easy way. Also, we have a compression efficiency for representing alternating knots, because chain codes preserve information and allow a considerable data reduction.


---

## Body

## 1. Introduction

In 1993, Livingston [1] stated that “knot theory remains a lively topic today. Many of the basic questions, some dating to Tailt’s first paper in the subject, remain open. At the other extreme, the results of recent years promise to provide many new insights’’. Knot theory is a branch of algebraic topology. The three main techniques of knot theory are: geometric techniques, combinatorial methods, and algebraic tools. A knot K is a simple closed polygonal curve in three-dimensional Euclidean space ℜ3 [1]. Knots are cataloged in order of increasing complexity. One measure of complexity that is often used is the crossing number, that is, the number of double points in the simplest planar projection of the knot. There is only one knot with crossing number of three (ignoring mirror reflections) the trefoil. The figure-eight knot is the only knot with a crossing number of four. There are two knots with a crossing number of five, three knots with a crossing number of six, and seven knots with a crossing number of seven. From there on the numbers increase dramatically. There are 12,965 knots with a crossing number of 13 or fewer crossings in a minimal projection. A complex knot is a knot with a huge crossing numbers. Imagine, how many knots are there in an alternating knot which is represented by a complex knot with a crossing number of 1200? This paper deals with complex knots of this order of crossing numbers. Z3 is a more computer-friendly place for generating knots. In ℜ3, every point in space has coordinates drawn from the set of real numbers. Thus, the generation of complex knots in ℜ3 produces a very complex computation. On the other hand, in Z3 all points have integer coordinates. Thus, we represent complex knots which are embedded on the cubic lattice. Complex knots are composed of constant orthogonal straight-line segments and are represented by means of a chain code [2] which produces a numerical string of finite length over a finite alphabet, allowing the usage of grammatical techniques for alternating-knot representation. The above mentioned generates a very simple computation.Several authors have analyzed knots on the cubic lattice. In 1993, Diao presented the minimal knotted polygons on the cubic lattice [3] and, in 1994, the number of smallest knots on the cubic lattice [4]. van Rensburg and Promislow define the minimal knots in the cubic lattice [5]. Hayes [6] presents the “Square Knots" on the cubic lattice, which are simple closed polygonal curves embedded in Z3. Other interesting theories: Kauffman [7] introduces the “Virtual Knot Theory”, which includes general Gauss codes. Nakamura and Rosenfeld [8] define the “Digital Knots” which represent an initial effort at the study of the concepts of knottedness and linkedness for digital objects. Complex knots are embedded on the cubic lattice. Thus, these knots are composed of constant orthogonal straight-line segments and are represented by chain coding [2]. In order to have a self-contained paper, Appendix A describes the used chain code. The left-hand side of Figure 1 shows an example of a complex knot in a continuous representation. The right-hand side of Figure 1 illustrates the same knot embedded on the cubic lattice. In the content of this work, knots are represented as ropes. This improves the understanding of the figures.Figure 1
An example of a complex knot: its continuous and discrete version, respectively.This paper is organized as follows: Section2 describes the proposed family of rectangular alternating links. In Section 3, we present some results. Section 4 gives some conclusions. Finally, we present Appendix A which describes the used chain code and Appendix B which presents the program of the proposed algorithm.


## 2. A Family of Rectangular Alternating Links

The alternating link diagrams of the type illustrated in Figure2 are used here to construct links like that shown in Figure 1. Each diagram is a set of rectilinear polygons and can be characterized in terms of two positive integers a and b. In what follows we present such a characterization, from which we obtain some properties of the family of polygons, useful to construct an algorithm for generating a chain code representation of the corresponding link.Figure 2
An alternating link diagram composed of a set of rectilinear polygons with vertices on the 2-dimensional integer lattice. The polygons are bounded by an axis-aligned square,Sa, which has side length a and has the origin at lower left corner. They are also inscribed in a rectangle, Ra,b, which has its sides parallel to the diagonals of Sa, is symmetric with respect to the central point of Sa, and has sides through the points (0,a-b) and (0,a-b+1). The vertices of the polygons are the lattice nodes lying on the sides of Ra,b and they are numbered from 0 to 2a+1.Leta and b be integers such that 0<b≤a. Let Sa be a square on the 2-dimensional integer lattice, with one corner at the origin and another at the point (a,a). Let Ra,b be the rectangle with sides parallel to the diagonals of Sa, symmetric with respect to the central point of Sa, and with sides through the points (0,a-b) and (0,a-b+1).The2(a+1) grid nodes lying on the edges of Ra,b serve as vertices of a set 𝒫a,b of rectilinear polygons, each of whose sides is the vertical or horizontal line segment that joins a corresponding pair of nodes. In Figure 2 those vertices appear counterclockwise enumerated from 0 to 2a+1, beginning with the node at coordinates (0,a-b). Accordingly, let Va={0,1,…,2a+1} be the set of vertices of 𝒫a,b.Letv:Va→Va be the function such that v(i) is the vertex of 𝒫a,b vertically opposed to vertex i. As a consequence of the way the enumeration of the vertices was done, we have that i+v(i)=2a+1. Then, from this equation and defining n=2(a+1), we arrive to(2.1)v(i)=n-1-i.Now, leth:Va→Va be the function such that h(i) is the vertex horizontally opposed to vertex i. There are two cases: i+h(i)=2a-2b+1=n-2b-1, if i≤2a-2b+1, and i+h(i)=4a-2b+3=2n-2b-1, otherwise. Taking into account that h(i)<n, in both cases we obtain(2.2)h(i)=(-2b-1-i)mod⁡n.Remark 2.1.
(1) The functions v and h are bijections, they are self-inverse, and each one maps odd numbers to even numbers and vice versa.
(2) By the above remark, also the function composition v∘h:Va→Va is bijective, but preserves the parity of its argument.
(3) The functions v, h, and v∘h, being bijections, are elements of the group SVa of symmetries of Va. In particular, we call attention to 〈v∘h〉—the cyclic subgroup generated by v∘h on SVa—and to its (induced) action over Va.
(4) Along any polygon P∈𝒫a,b, the horizontal sides alternate with the vertical ones. Thus, the consecutive vertices of P can be obtained by iterating alternate applications of h and v. For example, with a=9 and b=4 (which is the particular case presented in Figure 2), for the polygon through vertex 0, the corresponding iteration produces the (periodic) sequence
(2.3)0,h(0),v(h(0)),h(v(h(0))),…
which has
(2.4)0,11,8,3,16,15,4,7,12,19
as a shortest period.
(5) From the first remark, it follows that in sequences like those just presented the elements alternate in parity. So, if U is the set of even (odd) vertices of P, then h(U) and v(U) both are equal to the set of odd (even) vertices of P.Now, to count the number of polygons in𝒫a,b, it is useful to interpret this set as a graph, in the obvious way, and then proceed to count the number of cycles in this graph.Definition 2.2.
Leta,b,Va,v, andh, be as above.Ga,b=(Va,Ea,b)is the graph with vertex-setVaand edge-setEa,b={{i,v(i)}∣i∈Va}∪{{i,h(i)}∣i∈Va}.
We can see Figure2 also as a drawing of Ga,b. Since each vertex is an end point of exactly two edges, Ga,b is a regular graph of degree 2. Therefore, every component of Ga,b is a cycle [9]. Now we will see how many components have G and how long they are.Lemma 2.3.
The graphGa,b defined above is composed of c=gcd(a+1,b) cycles of length n/c, and all the vertices 0,1,…,c-1 belong to distinct cycles.Proof.
From (2.1) and (2.2) we have that v(h(i))=n-1-(-2b-1-i)modn=(2b+i)modn, that is
(2.5)(v∘h)(i)=(2b+i)mod⁡n.
Now, to analyze the action of 〈v∘h〉 over Va (see Remark 2.1(3)), it is useful the embedding of Va into the additive group ℤ/n. From (2.5) it follows that (v∘h)q(0)=q(2b)modn, for q∈ℕ. Hence, the orbit of 0 under the action of 〈v∘h〉 is the (finite) set {q(2b)modn∣q=0,1,2,…} which is the (cyclic) subgroup of ℤ/n generated by 2b. Then, this subgroup has c′=gcd(n,2b) as its least generator, it is of order n/c′ [10, Section  6.5-6],  and the set {[i]|0≤i<c′} of its c′ cosets coincide with the set of orbits of 〈v∘h〉 on ℤ/n. But the set of vertices of a cycle of Ga,b is equal to the union of two of these orbits (see Remark 2.1(5)). Hence, there are c=c′/2=gcd(n,2b)/2=gcd(a+1,b) cycles in Ga,b, each one of length 2(n/c′)=n/c. Now, in terms of cosets, the set of vertices of a cycle of Ga,b is equal to a union of the form [i]∪v([i]), with 0≤i<c′. By (2.1), and because n-1-i and c′-1-i are in the same coset, we obtain that
(2.6)v([i])=[v(i)]=[n-1-i]=[c′-1-i].
Therefore, the c cycles have, respectively, the following sets of vertices:
(2.7)[i]∪[(c′-1)-i],for0≤i<c′2=c.Next, we will define a linkℒa,b for the alternating link diagram 𝒫a,b. Figure 3(a) shows ℒ9,4. To begin with, we state some additional observations on Figure 2.Figure 3
(a) A link for the alternating link diagram shown in Figure2, (b) a section of the link, and (c) the pieces of a section.Remark 2.4.
(1) There are b and a+1-b vertices of 𝒫a,b in the upper left side and in the lower left side of Ra,b, respectively. Let
(2.8)b′=min⁡(b,a+1-b).
Since c=gcd(a+1,b)=gcd(a+1,b′)≤b′, the vertices 0,1,…,c-1 lie on the lower left side of Ra,b.
(2) Let e be an edge of a polygon P∈𝒫a,b. If the end points of e lie on parallel sides of Ra,b, then e is of even length 2b′, otherwise e has odd length. Furthermore, e has odd length if and only if e is at distance d<b′ from a side of Sa parallel to e, and in this case e is of length 2d+1. Thus, the lengths of the vertical and horizontal edges through the vertex i are, respectively, given by the functions lv,lh:Va→ℕ such that
(2.9)lv(i)={2j+1,ifj<b′,2(a-j)+1,ifj>a-b′,withj=imod⁡(a+1),2b′,otherwise,(2.10)lh(i)=lv(i+b).
For example, the alternate application of lh and lv to the vertices obtained for the polygon P in Remark 2.1(4) gives the following sequence of edge lengths:
(2.11)8,3,5,7,1,8,3,5,7,1.
(3) If e has even length, then its adjacent edges lie on distinct semiplanes with respect to the line containing e, otherwise they are to the same side of such a line.
The linkℒa,b is constructed in such a way that 𝒫a,b is the projection of ℒa,b on the plane x=0, under the mapping (x,y,z)↦(0,y,z). Let Ki∈ℒa,b be the component knot whose projection is the polygon Pi∈𝒫a,b trough vertex i∈{0,1,…,c-1}, with c as defined in the preceding lemma. We orient Pi by departing from i to the right, that is, following the cycle i,h(i),…,i. The knot Ki is an axis-aligned polygon whose vertices lie on the planes x=0 and x=1/2, with i as the starting vertex. In turn, this polygon is a concatenation of “sections,’’ which are planar polygonal curves corresponding to the edges of Pi, similar to that shown in Figure 3(b).
The sections related to a directed edge e is a concatenation of |e| “pieces’’ like the three shown in Figure 3(c); s begins with a horizontal piece, which belongs either to the plane x=0 or to the plane x=1/2 and is followed by |e|-1 alternate occurrences of the other two pieces. If we split the first piece at its midpoint, s can be seen as a directed polygonal composed of line segments of constant length (1/2), as delineated in Figure 4(a) which also shows the code obtained by means of (A.1) for each vertex apart from the first and fourth ones, whose codes p and q remain unknown until we have the placement of s along the knot (but q≠0 since q labels a right angle). Thus, in formal language terminology, a section is a chain over Σ={0,1,2,3,4} of the form either p0 or p00q2(042)⋆, where p,q∈Σ and q≠0, with the interpretation given in A. Figures 4(b)–4(f) show some configurations that correspond to five of the 20 possible values for the pair (p,q). Next we will prove that only the first two illustrated cases occur in Ki.Figure 4
(a) Chain code for a section of a link. To calculatep and q, a corresponding right angle of reference is needed; the configurations (b) to (f) illustrate the cases (p,q)=(4,1), (3,1), (4,3), (1,3); and (2,3).Lemma 2.5.
Lete be an edge of Pi and let s be the section of Ki corresponding to e. Then, s has p=3 or 4, and, if |e|>1, q=1.Proof.
The proof goes by induction on the position ofs along Ki. If s is the first section of Ki, then its initial point is vertex i which, by Remark 2.4(2.1), lies on the lower left side of Ra,b. Thus, the right angle previous to i along Ki must belong to one of the two configurations shown in Figures 4(b)-4(c), depending on the length d′ of the edge of Pi previous to e; if d′=1, then p=4, and if d′>1, then p=3. Furthermore, if |e|>1 (thus there is a point for q in s), q=1 in both cases.
Now, suppose by induction that a sections satisfies the lemma. We want to show that the section s′′ next to s also satisfies the lemma. Let s′ be the section previous to s. The induction hypothesis implies that the configuration for s′ and s must be one of those in Figures 4(b)-4(c), up to a rotation. Suppose |e| is odd; then, as a consequence of Remark 2.4(3), s′ and s′′ are to the same side of the plane containing s and, since s jumps |e|-1 times between the planes x=0 and x=1/2, the end points of s lie both in the same of these planes; therefore, the configuration determined by s and s′′ must be also, up to a rotation, one of those shown in Figures 4(b)-4(c). On the other hand, if |e| is even, from the same remark it follows that s′ and s′′ are in opposite sides of the plane of s and, since now |e|-1 is odd, the end points of s lie one in the plane x=0 and the other in the plane x=1/2, facts that lead to the same conclusion obtained in the first case.Corollary 2.6.
Lete′ and e be two successive edges of Pi, of lengths d′ and d, respectively. Then the chain code of the section s in Ki corresponding to e is given by the following function:
(2.12)κ(d′,d)={40ifd′=1,d=1,30ifd′>1,d=1,40012(042)d-2ifd′=1,d>1,30012(042)d-2ifd′>1,d>1.The following program, written inHaskell language [11, 12], is a computable version of the function κ:(2.13)section(d′,d)=concat((ifd′==1then“40”else“30”):take(d-1)(“012”:repeat“042”)),For example, section(1,8) evaluates to “40012042042042042042042”. The next function calculates the chain code forKi:(2.14)chaini=concat[section(d′,d)∣(d′,d)⟵side_length_pairsi],
where side_length_pairsi gives the list of pairs (d′,d) needed to compute the successive sections of Ki. The definitions of these functions, as well as those for v, h, lv, lh, n, c, and b′, are local to the main function, which computes the list of strings of code for the c cycles of the link ℒa,b:(2.15)carpetab=[chaini∣i⟵[0…c-1]],
The complete definition of this program is presented in Appendix B.


## 3. Results

In order to probe our proposed method, we present some examples of alternating-knot generation. Figure5 illustrates an example of an alternating knot of 22×12 (a=22, b=12).Figure 5
An example of an alternating knot of22×12.The chain of the alternating knot shown in Figure5 is as follows:40012042042042042042042042042042042042042042042042042042042042300120423001204204204204204204204204204204204204204204204204204230012042042042300120420420420420420420420420420420420420420420423001204204204204204230012042042042042042042042042042042042042042300120420420420420420420423001204204204204204204204204204204204230012042042042042042042042042042300120420420420420420420420420423001204204204204204204204204204204204230012042042042042042042042300120420420420420420420420420420420420420423001204204204204204230012042042042042042042042042042042042042042042042300120420420423001204204204204204204204204204204204204204204204204204230012042300120420420420420420420420420420420420420420420420420420420423040012042042042042042042042042042042042042042042042042042042042042304001204204204204204204204204204204204204204204204204204204204230012042300120420420420420420420420420420420420420420420420420423001204204204230012042042042042042042042042042042042042042042042300120420420420420423001204204204204204204204204204204204204204230012042042042042042042042300120420420420420420420420420420420423001204204204204204204204204204230012042042042042042042042042042300120420420420420420420420420420420423001204204204204204204204230012042042042042042042042042042042042042042300120420420420420423001204204204204204204204204204204204204204204204230012042042042300120420420420420420420420420420420420420420420420420423001204230012042042042042042042042042042042042042042042042042042042042304001204204204204204204204204204204204204204204204204204204204204230.If we replace the chain elements 1 by the chain elements 3 and vice versa in the above-mentioned chain, we obtain the mirroring image [2] of the alternating knot illustrated in Figure 5.Figure6 illustrates another example of an alternating knot of 50×25 using the proposed method.Figure 6
An example of an alternating knot of50×25.


## 4. Conclusions

We have presented a modest attempt for generating alternating knots which are represented by means of chain coding. The chain-code representation of alternating knots preserves information and allows a considerable data reduction. Also, the mirror images of alternating knots are obtained in an easy way.



---

*Source: 804829-2012-01-26.xml*