Algorithmic Invariants for Alexander Modules

ALGORITHMIC INVARIANTS FOR ALEXANDER MODULES J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, AND J.M. UCHA-ENR´ IQUEZ Abstract. Let Gbe a group given by generators and relations. It is possible to compute a presentation matrix of a module over a ring through Fox’s differential calculus. We show how to use Gr¨obner bases as an algorithmic tool to compare the chains of elementary ideals defined by the matrix. We apply this technique to classical examples of groups and to compute the elementary ideals of Alexander matrix of knots up to 11 crossings with the same Alexander polynomial. 1. Introduction Let G=hx:ribe a group given by generators and relations, where x= (x1, . . . , xn) is a base of the free group Fand r= (r1, . . . , rm) are the relations. Through Fox’s differential calculus [Crowell et al.(1977)] it is possible to compute the presentation matrix of the Alexander module of the group. We review briefly these concepts. We build from Gthe ring of the group ZG. A derivation over the group ring is a map D:ZG→ZGsuch that D(ν1+ν2) = Dν1+Dν2, D(ν1ν2) = (Dν1)t(ν2) + ν1Dν2, where tis the trivializer and ν1, ν2∈ZG. For elements in G, the second condition is D(g1g2) = Dg1+g1Dg2. Then a derivation can be seen as the unique linear extension to ZGof a map D:G→ZGthat verifies the previous condition. It is known that each generator xjin the group Gdefines a unique derivation Dj=∂/∂xjin ZG, such that ∂xi ∂xj =δij. Let Hbe the abelianized group of G. Considering the group rings we have the composition of maps ZFDj −→ ZFγ −→ ZGa −→ ZH, where γis the projection and ais the abelianizer. The Alexander matrix from G is A= (aij), where aij =aγ∂rj ∂xi. 2000 Mathematics Subject Classification. Primary 13P10, 57M05; Secondary 57M27. Key words and phrases. Gr¨obner bases, Elementary ideals, invariants of knots. All authors partially supported by MTM2004-01165 and FQM-333. 1 2 J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, AND J.M. UCHA-ENR´ IQUEZ Note that this matrix is the transposed of the matrix defined by [Crowell et al.(1977)]. The Alexander matrix presents a module over the ring ZH. If two groups are isomorphic then the modules are isomorphic. A finite presentation for Mis an exact sequence Rnα →RmΦ →M→0 where Rnand Rmare free R-modules with respective bases f1,...,fnand e1, . . . em. If αis represented by the matrix Awith respect to these bases then the m×nmatrix Ais a presentation matrix for M. Theorem 1. [Lickorish(1998), Thm. 6.1] If A1and A2are presentation matrices of a module Mthen they are related by a sequence of matrix transformations of the following form and their inverses: (1) Permutation of rows and columns. (2) Replacement of the matrix A1by A10 0 1 . (3) Addition of an extra column of zeros to the matrix A1. (4) Addition of a scalar multiple of a row (column) to another row (column). We say that A1and A2are Fitting equivalents. Definition 1. Let Mbe a Rmodule, with an m×npresentation matrix A. The rth elementary ideal Frof Mis the ideal generated by all the (m−r+1)×(m−r+1) minors of A. By convention, Fr(M) = Rwhen r > m and Fr(M) = 0 if r≤0. They form an ascending chain Fk(M)⊂Fk+1(M). The elementary ideals are independent of the presentation matrix chosen to evaluate them. 2. Algorithms in the ring group The ring ZHis commutative, because His an abelian group, and it has a special form. Proposition 1. The ring ZHis isomorphic to Z[x± 1, . . . , x± n]/J, where Jis the ideal generated by the relations r1, . . . , rmunder commutativity. Proof. Through the abelianizer, all the relations have the form Qxei i= 1, so Jis generated by the elements Qxei i−1.  Corollary 1. There is an algorithm to compare ideals in ZH. Proof. Through the bijection between ideals in Z[x± 1, . . . , x± n]/J and ideals in R= Z[x± 1, . . . , x± n] that contains J, the problem is reduced to compare ideals in R. In this ring we can compute Gr¨obner bases [Sims(1994), Pauer et al.(1999)], or by the isomorphism R≃Z[x1, . . . , xn, w]/hx1· · · xnw−1i[Adams et al.(1994)].  There is no known algorithm to decide whether two matrices present isomorphic modules. There are other invariants as the ideal row (column) class [Fox et al.(1964)] or the Nakanishi index [Kawauchi(1996)]. However we do not know algorithms to compute them and ad hoc arguments are needed to give their values for specific matrices [Fox et al.(1964), Kearton et al.(2003)]. ALGORITHMIC INVARIANTS FOR ALEXANDER MODULES 3 Example 1.Let consider the groups given by the presentations D8=hx, y|x4= 1, y2= 1, yxy−1=x−1i, Q8=hx, y|x4= 1, x2=y2, y−1xy =x−1i. D8is the dihedral group of order 8 (symmetry group of the square) and Q8is the quaternion group. A classical exercise in group theory is to show that these two groups are not isomorphic. Let see how can this be accomplished with elementary ideals. Let ribe the the relations in D8: r1:x4= 1, r2:y2= 1, r3:yxy−1x= 1. Then ∂r1 ∂x = 1 + x+x2+x3,∂r2 ∂x = 0,∂r3 ∂x =y+x−1, ∂r1 ∂y = 0,∂r2 ∂y = 1 + y, ∂r3 ∂y = 1 −x−1 In the abelianized group we add the relation xy =yx, so x2= 1, y2= 1. The Alexander module of the group has a presentation matrix M(D8) = 2+2x0x+y 0y+ 1 1 −x, over the ring Z[x±, y±]/hx2−1, y2−1i. We proceed in an analogous way with Q8. We write the relations s1:x4= 1, s2:x2y−2= 1, s3:xy−1xy = 1, and ∂s1 ∂x = 1 + x+x2+x3,∂s2 ∂x = 1 + x, ∂s3 ∂x = 1 + xy−1, ∂s1 ∂y = 0,∂s2 ∂y =−x2(1 + y),∂s3 ∂y =−xy−1+y−1 As before, in the abelianized group the relations are reduced to x2= 1, y2= 1 and a presentation matrix of the Alexander module is M(Q8) = 2+2x1 + x1 + xy 0−1−y−xy +y over the ring Z[x±, y±]/hx2−1, y2−1i. We compute a Gr¨obner basis in Z[x±, y±] of the second elementary ideal. Adding the polynomials x2−1, y2−1, we get F2(M(D8)) = h4,1 + y, 1−xi, F2(M(Q8)) = h2,1 + x, 1 + yi. They are different so the groups are not isomorphic. Example 2.In [Kanenobu(1986)] it is defined a class of knots Kp,q, with p, q ∈N, that has the Alexander matrix Ap,q =t2−3t+ 1 (p−q)t 0t2−3t+ 1 . Lemma 2 of [Kanenobu(1986)] asserts that Kp,q and Kp0,q0have isomorphic Alexander modules if and only if |p−q|=|p0−q0|. Let us show how to apply our approach to give a new proof of this lemma. If the modules are isomorphic then the second elementary ideals F2must coincide. A Gr¨obner basis of the ideal is equal to {t2−3t+ 1, p −q}, so F2(Ap,q) = F2(Ap0,q0) if and only if |p−q|=|p0−q0|. 4 J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, AND J.M. UCHA-ENR´ IQUEZ 3. An application to knot theory One of the main invariants in knot theory is the fundamental group of the knot complement. The Alexander matrix can be computed from the Seifert matrix, and with the tables listed in [Burde et al.(1985)] and [Livingston(2004)] we can get the Alexander matrix of knots up to 11 crossings. As an application of the algorithm described before we give a list of knots with the same Alexander polynomial (grouped by boxes) and where the elementary ideals give more information to distinguish knots (see Table 1). For example, from Table 1 we deduce that 11a102 and 11a181 are different, but we cannot say anything about 11a102 and 11a199. The first step was to compute the Alexander matrix of the knot and reduce it through the transformations given by Theorem 1. In all cases we have got at most a 2 ×2 presentation matrix, so F3is always equal to R. The Gr¨obner bases were computed over the ring Z[t, w], adjoining to the ideals the polynomial tw −1. References Adams et al.(1994). W.W. Adams, P. Loustaunau, An introduction to Gr¨obner bases, volume 3 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, 1994. Burde et al.(1985). G. Burde, H. Zieschang, Knots, volume 5 of de Gruyter Studies in Mathematics, Walter de Gruyter, Berlin and New York, 1985. Crowell et al.(1977). R.H. Crowell, R.H. Fox, Introduction to Knot Theory, volume 57 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1977. Fox et al.(1964). R.H. Fox, N. Smythe, An ideal class invariant of knots, Proc. Amer. Math. Soc., 15:707–709, 1964. Kanenobu(1986). T. Kanenobu, Infinitely many knots with the same polynomial invariant, Trans. Amer. Math. Soc., 97:158–162, 1986. Kawauchi(1996). A. Kawauchi, A survey of knot theory, Birkh¨auser Verlag, Basel, 1996. Kearton et al.(2003). C. Kearton, S.M.J. Wilson, Knot modules and the Nakanishi index, Proc. Amer. Math. Soc., 131:655–663, 2003. Lickorish(1998). W.B.R. Lickorish, An introduction to knot theory, volume 175 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1998. Livingston(2004). C. Livingston, Table of knot invariants at http://www.indiana.edu/~knotinfo/. Pauer et al.(1999). F. Pauer, A. Unterkircher, Gr¨obner Bases for Ideals in Laurent Polynomials Rings and their Application to Systems of Difference Equations, Appl. Algebra Engrg. Comm. Comput., 9:271–291, 1999. Sims(1994). C.C. Sims, Computation with finitely presented groups, volume 48 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1994. Depto. de ´ Algebra, Universidad de Sevilla. Apdo. 1160, E-41080 Sevilla (Spain) E-mail address:[email protected] Depto. de Matem´ aticas, Universidad de C´ adiz. Apdo. 40, E-11510 Puerto Real (Spain) E-mail address:[email protected] Depto. de ´ Algebra, Universidad de Sevilla. Apdo. 1160, E-41080 Sevilla (Spain) E-mail address:[email protected] ALGORITHMIC INVARIANTS FOR ALEXANDER MODULES 5 Table 1. Elementary ideals Name Elem. ideal F2 11n100 R 937 h3, t −2i 11n97 R 61R 946 h3, t + 1i 11a102 R 11a181 h3, t −2i 11a199 R 10113 R 11a107 h2, t2+t+ 1i 11a347 h2, t2+t+ 1i 11a187 R 11a249 h3, t −2i 11a38 R 11a8R 11a132 h2, t2+t+ 1i 11a352 h3, t2−t+ 1i 11a6R 1065 h2, t2+t+ 1i 1077 R 11n71 h−t2+t−1i 11n75 h−t2+t−1i 10103 h5, t + 1i 1040 R Name Elem. ideal F2 10140 h2, t2−t+ 1i 11n73 ht2−t+ 1i 11n74 ht2−t+ 1i 11n116 R 11n49 h2, t2+t+ 1i 11n1R 948 h3, t + 1i 10155 ht+ 1,5i 11n37 R 89R 11n164 ht2−t+ 1i 11n85 R 818 ht2−t+ 1i 924 R 10163 h2, t2+t+ 1i 11n87 R 928 R 929 R 1059 R 11n66 R 940 ht2−3t+ 1i 1042 R 1075 h3, t + 1i Name Elem. ideal F2 1060 R 11n165 h2, t2+t+ 1i 11a223 R 11n148 h5, t2+ 2t+ 1i 11a108 R 11a139 R 11a231 ht2−t+ 1i 11a57 ht2−t+ 1i 11a88 R 11a109 R 11a44 ht2−t+ 1i 11a47 ht2−t+ 1i 10123 ht4−3t3+ 3t2−3t+ 1i 11a28 R 1087 R 1098 h1−t+t2i 11a165 h2,1−t+t2i 11a58 R 11n72 h1−t+t2i 10144 h2,1−t+t2i 11n99 R 11n83 h2, t2+t+ 1i 941 h7,1 + ti 6 J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, AND J.M. UCHA-ENR´ IQUEZ Name Elem. ideal F2 11n162 h2, t2+t+ 1i 939 R 11a31 R 11a317 ht+ 1,5i 1067 R 1074 h3, t + 1i 11n68 R 11a157 h2, t4+t2+ 1i 11a264 R 11a305 R 11a80 R 1063 h2, t2+t+ 1i 938 R 11a277 ht+ 1,3i 11a99 R 11a196 h7, t + 1i 11a216 R 11a286 R