README for KhoHo version 0.9.3.5, 19 December 2004 ================================================== KhoHo is a program for computing and studying Khovanov homology. It is written by Alexander Shumakovitch and can be freely downloaded from http://www.geometrie.ch/KhoHo and redistributed under the terms of GPL v.2 (see 'copyright' file for details). I. Links and references. -------------------------- Detailed information about Khovanov homology can be obtained from 1. Dror Bar-Natan, On Khovanov's categorification of the Jones polynomial, Algebr. Geom. Topol. 2 (2002), 337--370; arXiv:math.QA/0201043; http://www.math.toronto.edu/~drorbn/papers/Categorification/ 2. Stavros Garoufalidis, A conjecture on Khovanov's invariants, preprint 2001 3. Mikhail Khovanov, A categorification of the Jones polynomial, Duke Math. J. 101 (2000), no. 3, 359--426; arXiv:math.QA/9908171 4. Mikhail Khovanov, Patterns in knot cohomology I, arXiv:math.QA/0201306 5. Mikhail Khovanov, Categorifications of the colored Jones polynomial, arXiv:math.QA/0302060 6. Eun Soo Lee, The support of the Khovanov's invariants for alternating knots, arXiv:math.GT/0201105 7. Eun Soo Lee, On Khovanov invariant for alternating links, arXiv:math.GT/0210213 8. Oleg Viro, Remarks on definition of Khovanov homology, arXiv:math.GT/0202199 9. Stephan Wehrli, Khovanov Homology and Conway Mutation, arXiv:math.GT/0301312 II. System requirements. ------------------------ a) PARI/GP version 2.2.0 or higher (2.2.5 or higher recommended). Can be freely downloaded from http://www.parigp-home.de PARI/GP is a software package for computer-aided number theory. Although its symbolic computational power pales in comparison with the one of Maple or Mathematica, PARI is significantly faster than these two programs and its data management is much more efficient and transparent. Since the core of KhoHo is a PARI/GP script, it is essential to have this package installed before making any attempts to run KhoHo. Note that KhoHo requires the development (as of this writing) version 2.2.* of PARI/GP. Versions up to 2.2.3 had a nasty memory leak bug. It is therefore recommended to install version 2.2.5 or higher. b) Standard GNU development environment including GNU C Compiler 'gcc' and GNU 'make' utility. Remark: KhoHo should work on any U*ix operating system. It was tested on Debian GNU/Linux 3.0 (woody) and Compaq True64 only, though. Please report any problems and/or success stories on other platforms to Shurik@Dartmouth.edu III. Installation. ------------------ a) Download the latest version of KhoHo from http://www.geometrie.ch/KhoHo Place the file called KhoHo.tar.gz somewhere in your home directory and unpack it with 'tar xfzv KhoHo.tar.gz' command. Directory KhoHo-x.y.z should appear, where x.y.z is the version downloaded. Go into this directory with 'cd KhoHo-x.y.z' command. b) Make sure that an appropriate version of PARI/GP is installed and its header files are available in one of the standard places like /usr/include/pari or /usr/local/include/pari If it is impossible to install PARI there, change Makefile accordingly. c) Run 'make' command. If everything worked out fine, there should be three new library files created: nicematr.so, print_ranks.so, and sparreduce.so The first two contain some auxiliary functions and are not essential for KhoHo operation. But sparreduce.so is crucial. It implements a chain complex reduction algorithm, on which KhoHo is based. d) Download from http://www.geometrie.ch/KhoHo any knot and link tables you like. The basic set include KTable_11, LTable_11 and SpecialLinks. IV. How to run (for impatient or excited). ------------------------------------------ a) Start PARI's programmable calculator: $ gp b) Read KhoHo and main tables of knots and links: (12:00) gp > read(KH) c) Take a knot from the table: (12:02) gp > knot = KTable(3, 1) d) Compute its rational and torsion Khovanov polynomial: (12:03) gp > KhPol(knot) e) Enjoy the result: [((q^8 + q^6)*t^3 + q^4*t + 1)/(q^9*t^3), 1/(Q^7*t^2)] Remarks: 1) KTable(n, m) returns the knot number m with n crossings. LTable does the same for links. For knots with 11 crossings or more as well as for all links, it should be specified whether the knot or link is alternating or not. I.e. KTable("11n", 123) or LTable("4a", 1). If m is negative, the mirror image of the knot or link number -m is returned. 2) KhPol returns a vector with two entries, that contain rational and torsion polynomials, respectively. To access them separately use (12:04) gp > pols = KhPol(knot) (12:04) gp > pols[1] time = 0 ms. %13 = (t^3*q^8 + t^3*q^6 + t*q^4 + 1)/(t^3*q^9) (12:04) gp > pols[2] time = 0 ms. %14 = 1/(Q^7*t^2) V. How to run (for interested or impressed). -------------------------------------------- a) Start PARI's programmable calculator: $ gp b) Read KhoHo: (12:00) gp > read(KhoHo) c) Define a link diagram as a 4 times the number of crossings matrix in Bar-Natan's notation: (12:02) gp > diagr = [6, 1, 7, 2; 8, 3, 5, 4; 2, 5, 3, 6; 4, 7, 1, 8] d) Check that the diagram is correct (i.e. represents a 4-valent graph): (12:03) gp > check_diagr(diagr) e) Prepare the diagram for further consumption by KhoHo. A string (acting as a diagram's name) should be supplied. This name is used to identify the diagram for which various invariants are computed. (12:05) gp > link = preplink(diagr, "what a wonderful link!") f) Compute Betti numbers of the link's Khovanov homology: (12:07) gp > Betti(link) g) Compute torsions of the link's Khovanov chain complex differentials: (12:10) gp > D_tors(link) i) Create a TeX table combining all the results together and stare at it in amusement: (12:12) gp > TeXview(link, "the best link ever", "file4link") j) Read sources of KhoHo through to learn even more (it's thought to be well-documented). Remark: Since version 0.9.1 KhoHo supports calculation of the reduced Khovanov homology. To use this feature execute (12:15) gp > set_H_reduced() immediately after reading KhoHo. To return back to `normal' homology use (12:15) gp > set_H_standard() VI. Further capabilities. ------------------------- Using KhoHo one can a) take the mirror image or a link with 'mirror'; b) take the connected sum or the disjoin union of two knots with 'connsum' and 'disunion', respectively; c) get the linking matrix of a link with 'get_lk_matrix'; d) given the Khovanov polynomial of a link, figure out how many diagonals it occupies with 'pol_diags'; e) given the Khovanov polynomial of a knot, check whether it satisfies Conjecture 1 by Bar-Natan with 'check_conj1' ... f) ... and whether it's H- or T-thick with 'check_H_thick' and 'check_T_thick', respectively; g) do e) and f) for links and the corresponding extension of Conjecture 1 (due to Lee) with the help of 'conj1_factor'; h) cyclically reorder components of a link diagram with 'comp_reorder' to compute the reduced Khovanov homology with respect to an arbitrary one; i) compute signature of a nonsplit link with, well, 'signature'; j) combine the ranks of standard and reduced homology into a single TeX table using 'TeX_H_print' or 'TeX_H_view'. VII. Known bugs. ---------------- a) KhoHo assumes that the number of non-zero entries (i.e. adjacencies) in the matrix of a Khovanov chain complex differential is never bigger than 5 times the sum of matrix sizes. It is true for small knots and links, but is false in general. If you see something like the following error *** array index (5853) out of allowed range [1-5852]: *** ...T];diff_matrices_s[j_ST][m_ptr-1]=tT_gen;diff ^-------------------- you've been bitten by this assumption. Try to increase this constant 5 in the function initDmatrices from KhoHo_chain then. On the other hands, setting it too big could result in insufficient memory or bug b). b) PARI/GP can't handle vectors with more than 2^24-2 elements on a 32-bit architecture. Although this number seems to be huge, the constrain means that the sum of sizes of differential matrices can't be bigger than 1'677'721 (or even less if the constant 5 from bug a) has been increased). The (2, 16) torus link has a 2'018'016x2'018'016 matrix already. The (2, 15) torus knot barely fits with a 630'630x756'756 matrix. This problem doesn't appear on 64-bit architectures. VIII. Feedbacks. ---------------- Please send any suggestions, remarks, bug reports, patches, and wishes concerning KhoHo to Shurik@Dartmouth.edu IX. Appendix: a simple session. ------------------------------- It takes less than 3 minutes and requires less than 20MB of memory to compute Khovanov homology of the (2, 11) torus knot on a 600MHz computer. $ gp GP/PARI CALCULATOR Version 2.2.4 (alpha) i686 running linux (ix86 kernel) 32-bit version (readline v4.3 enabled, extended help available) Copyright (C) 2002 The PARI Group PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER. Type ? for help, \q to quit. Type ?12 for how to get moral (and possibly technical) support. realprecision = 28 significant digits seriesprecision = 16 significant terms format = g0.28 parisize = 50000000, primelimit = 5000 (02:26) gp > read(KH) Loading the table of knots with up to 11 crossings ... done. Loading the table of links with up to 11 crossings ... done. Loading some special knots and links ... done. time = 140 ms. (02:26) gp > knot = KTable("11a", 367) time = 0 ms. %1 = [[12, 2, 13, 1; 14, 4, 15, 3; 16, 6, 17, 5; 18, 8, 19, 7; 20, 10, 21, 9; %22, 12, 1, 11; 2, 14, 3, 13; 4, 16, 5, 15; 6, 18, 7, 17; 8, 20, 9, 19; 10, %22, 11, 21], "tknot11a_367", 11, 22, 11, 0, 11, 12, -1, 34, 18, 1] (02:27) gp > KhPol (knot) Computing differential ranks and torsions ... Reducing the chain complex first ... Computing the list of generators ... done. Primary grading: 0. Computing matrices of differentials ... done. Primary grading: 1. Computing matrices of differentials ... done. Primary grading: 2. Computing matrices of differentials ... done. Primary grading: 3. Computing matrices of differentials ... done. Primary grading: 4. Computing matrices of differentials ... done. Primary grading: 5. Computing matrices of differentials ... done. Primary grading: 6. Computing matrices of differentials ... done. Primary grading: 7. Computing matrices of differentials ... done. Primary grading: 8. Computing matrices of differentials ... done. Primary grading: 9. Computing matrices of differentials ... done. Primary grading: 10. Computing matrices of differentials ... done. Secondary grading: 33. Reducing the chain complex ... done. Secondary grading: 31. Reducing the chain complex ... done. Secondary grading: 29. Reducing the chain complex ... done. Secondary grading: 27. Reducing the chain complex ... done. Secondary grading: 25. Reducing the chain complex ... done. Secondary grading: 23. Reducing the chain complex ... done. Secondary grading: 21. Reducing the chain complex ... done. Secondary grading: 19. Reducing the chain complex ... done. Secondary grading: 17. Reducing the chain complex ... done. Secondary grading: 15. Reducing the chain complex ... done. Secondary grading: 13. Reducing the chain complex ... done. Secondary grading: 11. Reducing the chain complex ... done. Secondary grading: 9. Reducing the chain complex ... done. Secondary grading: 7. Reducing the chain complex ... done. Secondary grading: 5. Reducing the chain complex ... done. Secondary grading: 3. Reducing the chain complex ... done. Secondary grading: 1. Reducing the chain complex ... done. Secondary grading: -1. Reducing the chain complex ... done. done with the reduction. ... done with computing ranks and torsions. Computing Betti numbers ... ... done with computing Betti numbers. time = 2mn, 43,960 ms. %2 = [q^33*t^11 + q^29*t^10 + q^29*t^9 + q^25*t^8 + q^25*t^7 + q^21*t^6 + q^21*t^5 + q^17*t^4 + q^17*t^3 + q^13*t^2 + (q^11 + q^9), Q^31*t^11 + Q^27*t^9 + Q^23*t^7 + Q^19*t^5 + Q^15*t^3] (02:29) gp >