 Applied Mathematics, 2013, 4, 1526-1530 Published Online November 2013 (http://www.scirp.org/journal/am) http://dx.doi.org/10.4236/am.2013.411206 Open Access AM Algorithms for Computing Some Invariants for Discrete Knots Gabriela Hinojosa, David Torres, Rogelio Valdez Facultad de Ciencias, Universidad Autónoma del Estado de Morelos, Cuernavaca, México Email: gabriela@uaem.mx, david.tormor@gmail.com, valdez@uaem.mx Received April 18, 2013; revised May 18, 2013; accepted May 25, 2013 Copyright © 2013 Gabriela Hinojosa et al. This is an open access article distributed under the Creative Commons Attribution Li-cense, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. ABSTRACT Given a cubic knot K, there exists a projection of the Euclidean space onto a suitable plane such that p(K) is a knot diagram and it can be described in a discrete way as a cycle permutation. Using this fact, we develop an algorithm for computing some invariants for K: its fundamental group, the genus of its Seifert surface and its Jones polynomial. 3:pP33P Keywords: Cubic Knots; Discrete Knots; Algorithms 1. Introduction Considering the set consists of the lattice and all the straight lines parallel to the coordinate axis and passing through points in , we say that a knot 3S333K is a cubic knot if it is contained in . In  it was shown that any classical knot is isotopic to a cubic knot and by  we know that there exists a generic pro-jection p of any cubic knot into a suitable plane. If we combine these two results, we have that p(K) is a dia-gram of K and it can be described in a discrete way as a cyclic permutation of points S,,,nw12ww (with some restrictions). This allows us to develop an algorithm for computing the fundamental group of K, the genus of its Seifert surface and its Jones polynomial. 2. Discrete Knots and Some Invariants Consider an oriented cubic knot K. In  it was proved that we can associate to K a unique sequence of points such that , ij, 12,, ,nv v v3ivvv1,ij n, i is joined to 1i by a unit edge, nv is likewise joined to 1 by a unit edge, and the numbering of the i’s is compatible with the orientation of K. Henceforth, we will assume that all the coordinates of the points in K are positive. vvvvAn advantage of cubic knots is that there exists a ca-nonical generic projection p (for details see ). In fact, let , where is the well-known tran-scendental number. Let P be the plane through the origin in orthogonal to N and consider the orthogonal pro-jection . Then 21, π,πNPπ33:p3p is injective. Let ˆKpK be its projection into the plane P. Thus ˆK is a polygonal curve contained in P with some self-in- tersections called inessential vertices or crossings. The crossings are not contained in 3:Ppp K and are transverse, hence p is regular. The projections of the vertices of K are contained in P, and are called verti-ces. Hence we can write ˆK as a cyclic permutation of points 12,,,ww wnn where iP, ij, w ww1,ijw and i is joined to 1i by a straight line segment whose preimage is a unit edge and in the same way is likewise joined to (for details see ). wwn1Definition 2.1. A discrete knot K̂ is the equivalence class of the n cyclic permutations of n points w,,,nw12 in Pww P such that the ’s satisfy the above assumptions. iwˆNext we will describe the crossings of K. Consider an orthonormal basis β of the plane , given by 3P23 2π,π,1 π110,ABπ,1, where 2π1A and 2462π2ππ1Bw4ˆiwK. Con-sider four points 1i, 2i, 3i and whose coordinates with respect to the basis β are w wy,jijj. The following lemma gives us a criteria to know when the line segment wx12iiintersects the line segment ww34ii. Notice that for the computing algorithm purpose, we just need to consider only the quadruples of points ww G. HINOJOSA ET AL. 1527where and (see ). 21 43Lemma 2.2. Let 3i and , whose coordinates are jij. Let rs and consider the 2 × 2 matrices, , 1ii1,3 4,3u1ii1i, 2iw, w,jwxy3,1 2,1Cu uw4ˆiwKiuw4,3uDu,rs iw32,AuBu, and . 4,12,1uThen the line segment 12ii intersects the line seg-ment ww34iiww if and only if  det det0AB and .  detCdet 0D Algorithm 1. Projection and crossings Require: List of points at , 312,,,nLv vv, where , list of points at P, ,,iiiivabc112,,Lww,nw, an empty set I, the constant numbers A and B given above. for all do svL 23 2πππ π,ssss sssababccw AB for all do 1 Create matrices ,ikww L , 11ik kkMwwww  , 1kjk kNww ww  , 1kiikOwwww  11kk ikPww ww  where ,ssswxy and ,srsrsrwwxxy y  if and  det detMN0det det0OP then if and ,ijI,jiI then add ,ij to I Suppose that the line segment 1iiilw intersects the line segment w1kkk. We will determine which crosses “over” the other. Since, the line segments i and k are the image under the projection p of two segments whose endpoints are 1i, i and 1k, k, respec-tively, we have that these both segments are parallel to two different canonical coordinate vectors. Let y 1kk k kkk. If ilwwl,,ylvizvv vvx1,,ii i iiuv v xykuv zxx,,iivaba, then we compare the first coordinate of the vectors ii and , i.e., we compare and ak. Thus, c,,kbkkvakci If ai < ak we say that kl crosses over il (over crossing).  If ak < ai we say that kl crosses under il (under crossing). If ik, then we compare the second coordinate of the vectors i y k, and we have the same criteria of the previous case changing a by b. The last case zi = zk is analogous to the previous one. yyv vLet c be a crossing point of the segment over the segment . Consider the vectors 1iii, and construct the 2 × 2-matrix klwil1uwkkuw wkkiMuu. Thus we have two possible configurations: If det(M) > 0, we say that c is a positive crossing; If det(M) < 0, then c is a negative crossing. Algorithm 2. Crossing criteria Require: The list of indexes of intersection points 112 2,,,,,,rrIik ikik3 and the list of points in 12,,,nLv vv, where and ,,iiiivabc112,,,nLwww. for all ,ijI do where 1,,ssssssv xyzuvvuv 1iii 1kkvkuv if ikxx then if ai < ak then print 1iiww crosses under else print 1kkww crosses under if ikyy then if bi < bk then print 1iiww crosses under else print 1kkww crosses under if ikzz then if ci < ck then print 1iiww crosses under else print 1kkww crosses under 2.1. Fundamental Group Let 12ˆ,,,nKww w,,,rc be an oriented discrete knot and 12 be its crossings. We will compute the fun-damental group K denoted by cc1KP, using the Wirt-inger presentation (see [3,4]). We will start describing the set of generators of 1KP (see ). Suppose that jc is the crossing point of the linear segment 1jjkklwwjkover the linear segment 1jjjiiiings lww. Now we are going to rearrange the cross- jc in such a way that 12 r. Let i be the segment of ii i gˆK whose endpoints are and ic1ic (where 1rc1c). Thus , 11 11,2, ,ii 2ig,i222 31, where each index 1, 2ii, ,,, gg1, 2,rr riiiji is considered mod n. We know by Wirtinger presentation that there exists a bijection be-tween the set of segments and the set of generators of ,1,,iirg1KP, so the set of generators of 1KP is 1,,aarAgain, by the Wirtinger presentation we know that for each . jjjikclllal corresponds a relation among the generators , 1a and sa, where the indexes s and l satisfy that jskg and jlig. So  If 11det 0jjj jiikkww ww, then we have the relation given by . lR1ls slaa aa If 11det 0jjj jiikkww ww, then we write the relation given by lR1sllaaa as. Open Access AM G. HINOJOSA ET AL. 1528 Therefore 111,, ,,rrKRRPaa. Algorithm 3. Fundamental group Require: The list of indexes of intersection points  112 2,,, ,,,rrIikikik. Create lists 11 1222 2311,2,,1,2, ,1,2,,rr rii iii iii i  ggg for all do ,jjik L Search r and l such that jskg and jlig. Create a matrix, 11jjjjii kkAw www  if then det 0A print 1sllaasaa else print 1ls slaa aa2.2. Seifert Surface Given a knot K there exists an algorithm to construct its Seifert surface via an oriented diagram of it (for details see [3,4]). Roughly speaking, suppose that the corre-sponding diagram has r crossings, then the crossings are replaced by two disjoint arcs respecting the orientation. At the end, we obtain a collection of s simple closed curves called Seifert curves. We construct a Seifert sur-face F for K considering each Seifert curve as the bound-ary of a disk. The disks are connected at each crossing by a twisted band (so we need r bands). The genus of F is 12sr. The Seifert genus of a knot is the minimal ge- nus possible for a Seifert surface of that knot. Next, we apply the above algorithm to our case. As in the previous section, 12ˆ,,,nKww w12,,,rcc c denotes an oriented discrete knot and are its crossings, where jc is as above. Let 1rAii,,12,,,nnww wAlB and . In  it was defined the bijective map , given by if and , 1,,12:,wwllrBk k,,s1wwswl1slkwws if slis, or if 1sliwwslk. This permutation can be expressed as a product of s disjoint cycles, where each cycle represents a Seifert curve. Hence we can compute the Seifert genus g. Algorithm 4. Seifert surface Require: The set or indexes 1,,rAii and such that 1,,rBk k1jjiwiw crosses under 1jjkk. The empty sets , and ww12,,,nLLL 1r and the genus of the knot . 0g Create a function  where l is an index if and lB 1llwwslA  If slA li so that w1slkws If slB lk so that 1sliwws Now we will form cycles for 11srriLL L do Add si L to and rsmi while sim do Add m to and rLmm r++ print 12 rLL L 2sr1g  print g 2.3. Jones Polynomi al The Jones polynomial is a very important invariant of an oriented knot K. We compute the Jones polynomial of a cubic knot K using the method described on “The knot atlas website” () applied to our case. Let 12ˆ,,,nKww w be as above. Let ,jjik be pairs of indexes such that jk crosses over ljil, 1,j,r. Consider the sequence 1,,1r rkk111 1,1,,1,,rri kki,ici and up to re-arrangement, we can assume that 1112 22,1,, 1,,l lll2,kklCl is an increasing se-quence. Consider the segments of curves 11 121,2, ,Cl ll , ,···, 22 231,2,,Cl ll 22 21,2,,kk kCl l 1l, where the index n + 1 is equal to 1. For each pair ,ssik , consider the segments as , , cs and ds such that is  Ccs, is + 1  Cas, ks  Cds and ks + 1  Cbs. Now we take the following expres-sions CbsC CC If 11det 0ssssii kkwwww, then we con- sider 1,, ,,Aas dsbscsAasbscsds,  if 0wwww11det ssssii kk, then we con- sider 1,, ,,Aas dscsdsAas dsbscs, as formal sums, where A denotes a variable and s = 1, ···, r. Notice that in the above expressions the order does not matter; for instance, the expressions [as, ds] and [ds, as] are equal. Now, we compute the formal product of all the above expressions to obtain a new expression Q. We calculate the Kauffman bracket, denoted by tA from Q replacing first ,,as bsbs cs by ,as cs and afterward replace ,as as2 by 2AA . Next we com-pute the writhe number denoted by w, which is equal to the number of positive crossings minus the number of negative crossings. Finally, the Jones polynomial Jq is equal to 131441122wqtJqqqq, Open Access AM G. HINOJOSA ET AL. 1529where q denotes a variable, 14tq is the Kauffman bracket evaluated at 14q and w is the writhe number. Algorithm 5. Jones polynomial Require: The list of indexes of intersection points  112 2,,, ,,,rrIikikik, bracketKauffman, poly-nomJones and writhe ← 0. Create array 111 1,1,,1,, ,1,,1rrr rcii kkiikk  Sort C and produces 12 n,, ,Clll where 12 n Take curve segments ll l 11 1222 2311,2, ,1,2,,1,2, ,nn nCl llCl llCl ll   for all do ,ssik L Take sliC, sm1kC, sn1iC, sp such that l, m, n, p are the labels of the edges around kC that crossing, starting from the incoming lower edge l and proceeding counterclockwise direction. Example: ,,,lmnp such that m is next to l in counterclockwi- se direction, n is next to m in counterclockwise direc tion, etc. Save ,,,lmnp Replace each 1,,,, ,npAlp mnAlmnp,,lm bracketKauffman ← Multiply all replacements bracketKauffman←Replace ,, ,as bsbs csas cs and  2,,as bsas as bracketKauffman  Replace and simplify 22,as asAA  print t(A) = bracketKauffman for all do ,ssik L Create matrix 11ssssii kkUwww w  if then det 0U writhe++ else writhe-- PolynomJones ← 322writheAtAAA PolynomJones ← replace and simplify 14Aq print Jq = PolynomJones 3. Examples 3.1. Left-Handed Trefoil Knot Considering the left-handed trefoil knot as a cubic knot, see Figure 1, where you can see the corresponding vec-tors vi’s; . 1,,24iNow, we apply our program to compute its fundamen-tal group, genus Seifert and Jones polynomial. See Fig-ure 2. In this case, its fundamental group has 3 genera-tors a1, a2, a3; and relations: a3a2 = a2a1, a1a3 = a3a2, a2a1 = a1a3. Its genus surface is one and its Jones poly-nomial is 43qqqJq. 3.2. Figure Eight Knot Considering the figure eight knot as a cubic knot, in this case, we have 40 vertices. See Figure 3. We now compute its fundamental group, its genus sur-face and its Jones polynomial. Thus, its fundamental group has 4 generators a1, a2, a3, a4; and relations: a2a4 = a1a2, a1a3 = a3a2, a4a2 = a3a4, a3a1 = a1a4. Its genus surface is one and its Jones polynomial is 211qqq qJq 2. See Figure 4. Figure 1. Cubic left-handed trefoil knot. Figure 2. Left-handed trefoil knot invariants. Figure 3. Cubic eight knot. Open Access AM G. HINOJOSA ET AL. Open Access AM 1530 REFERENCES  M. Boege, G. Hinojosa and A. Verjovsky, “Any Smooth Knot Sn  ℝn+2 Is Isotopic to a Cubic Knot Contained in the Canonical Scaffolding of n+2,” Revista Matemática Complutense, Vol. 24, No. 1, 2011, pp. 1-13. http://dx.doi.org/10.1007/s13163-010-0037-4  G. Hinojosa, A. Verjovsky and C. V. Marcotte, “Cubu-lated Moves and Discrete Knots,” 2013, pp. 1-40. http://arxiv.org/abs/1302.2133  D. Rolfsen, “Knots and Links,” AMS Chelsea Publishing, American Mathematical Society, Providence Rhode Is-land, 2003.  R. H. Fox, “A Quick Trip through Knot Theory. Topol-ogy of 3-Manifolds and Related Topics,” Prentice-Hall, Inc., Upper Saddle River, 1962.  “The Knot Atlas,” 2013. http://katlas.math.toronto.edu Figure 4. Figure eight knot invariants. 4. Acknowledgements Gabriela Hinojosa thanks CONACyT (México), for its financial support CB-2009-129939 and all the authors thank PROMEP (México) for supporting the publication of this paper.