Skip to main content
SpringerLink
Log in

Self-dual codes over the Kleinian four group

  • Published:
Mathematische Annalen Aims and scope Submit manuscript

Abstract.

We introduce self-dual codes over the Kleinian four group K=Z 2×Z 2 for a natural quadratic form on K n and develop the theory. Topics studied are: weight enumerators, mass formulas, classification up to length 8, neighbourhood graphs, extremal codes, shadows, generalized t-designs, lexicographic codes, the Hexacode and its odd and shorter cousin, automorphism groups, marked codes. Kleinian codes form a new and natural fourth step in a series of analogies between binary codes, lattices and vertex operator algebras. This analogy will be emphasized and explained in detail.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Assmus, E.F., Mattson, H.F.: New 5-designs. J. Combinatorial Theory 6, 122–151 (1969)

    MATH  Google Scholar 

  2. Bachoc, C.: Harmonic weight enumerators of nonbinary codes and MacWilliams identities. Codes and association schemes (Piscataway, NY 1999). 135–149, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 56, Amer. Math. Soc., Providence, RI, 2001

  3. Bacher, R.: Unimodular lattices without nontrivial automorphisms. Internat. Math. Res. Notices 2, 91–95 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bachoc, C.: On harmonic weight enumerators of binary codes. Des. Codes Cryptogr. 18, 11–28 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bannai, E.: Positive definite unimodular lattices with trivial automorphism groups. Ph.D. thesis, Ohio State Univ., 1988

  6. Bose, R.C., Connor, W.S.: Combinatorial properties of group divisible incomplete block designs. Ann. Math. Statist. 23, 367–383 (1952)

    MathSciNet  MATH  Google Scholar 

  7. Borcherds, R.E., Conway, J.H., Queen, L.: The Cellular Structure of the Leech Lattice. [CS93b], Chapter~25, pp. 515–523

  8. Bannai, E., Damerell, R.M.: Tight spherical designs. I. J. Math. Soc. Japan 31, 199–207 (1979)

    MathSciNet  MATH  Google Scholar 

  9. Bannai, E., Damerell, R.M.: Tight spherical designs. II. J. London Math. Soc. (2) 21, 13–30 (1980)

    Google Scholar 

  10. Bachoc, C., Gaborit, P.: On Extremal Additive GF(4) codes of Length 10 to 18. J. Théor. Nombres Bordeaux 12, 255–271 (2000)

    MATH  Google Scholar 

  11. Bose, R.C., Nair, K.R.: Partially balanced incomplete block designs. Sankhy¯a 4, 337–372 (1939)

    MATH  Google Scholar 

  12. Borcherds, R.E.: The Leech lattice and other lattices. Ph.D. thesis, Cambridge University, 1984

  13. Borcherds, R.E.: The 24-dimensional odd unimodular lattices. [CS93b], (see also~[Bor84]), pp. 421–426

  14. Borcherds, R.E.: Automorphic forms with singularities on Grassmannians. Invent. Math. 132, 491–562 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  15. Bremner, A.: A Diophantine equation arising from tight 4-designs. Osaka J. Math. 16, 353–356 (1979)

    MathSciNet  MATH  Google Scholar 

  16. Carmichael, R.D.: Tactical configurations of rank two. Amer. J. Math. 53, 217–240 (1931)

    MATH  Google Scholar 

  17. Conway, J.H., Odlyzko, A.M., Sloane, N.J.A.: Extremal self-dual lattices exist only in dimensions 1 to 8, 12, 14, 15, 23 and 24. Mathematika 25, 36–43 (1978), see Chapter~19 in~[CS93b]

    MathSciNet  MATH  Google Scholar 

  18. Conway, J.H., Pless, V.: On the enumeration of self-dual codes. J. Combinatoial Theory, Ser. A 28, 26–53 (1980)

    Google Scholar 

  19. Conway, J.H., Pless, V., Sloane, N.J.A.: Self-dual codes over GF(3) and GF(4) of length not exceeding 16. IEEE Trans. Inform. Theory 25, 312–322 (1979)

    MATH  Google Scholar 

  20. Conway, J.H., Parker, R.A., Sloane, N.J.A.: The covering radius of the Leech lattice. Proc. Royal Soc. A380, 261–290 (1982), see Chapter~23 in~[CS93b]

  21. Conway, J.H., Pless, V., Sloane, N.J.A.: The binary self-dual codes of length up to 32: A revised enumeration. J. Combinatorial Theory, Ser. A 60, 183–195 (1992)

    Google Scholar 

  22. Calderbank, A.R., Rains, E.M., Shor, P.W., Sloane, N.J.A.: Quantum error correction via codes over GF(4). IEEE Trans. Inform. Theory 44, 1369–1387 (1998)

    Article  MATH  Google Scholar 

  23. Conway, J.H., Sloane, N.J.A.: Laminated lattices. Ann. Math. 116, 593–620 (1982), see~Chapter~6 in~[CS93b]

    MathSciNet  MATH  Google Scholar 

  24. Conway, J.H., Sloane, N.J.A.: The unimodular lattices of dimension up to 23 and the Minkowski-Siegel mass constants. Eur. J. Combinatorics 3, 219–231 (1982), see Chapter~16 in~[CS93b]

    MathSciNet  MATH  Google Scholar 

  25. Conway, J.H., Sloane, N.J.A.: Complex and integral laminated lattices. Trans. AMS 280, 463–490 (1983)

    MathSciNet  Google Scholar 

  26. Conway, J.H., Sloane, N.J.A.: Lexicographic codes: error correcting codes from game theory. IEEE Trans. Inform. Theory 32, 337–348 (1986)

    MathSciNet  MATH  Google Scholar 

  27. Cheng, Y., Sloane, N.J.A.: The Automorphism group of an [18,9,8] quaternary code. Discrete Math. 83, 205–212 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  28. Conway, J.H., Sloane, N.J.A.: A new upper bound for the minimum of an integral lattice of determinant 1. Bull. Amer. Math. Society (New Series) 23, 383–387 (1990)

    MATH  Google Scholar 

  29. Conway, J.H., Sloane, N.J.A.: A New Upper bound on the Minimal Distance of Self-Dual Codes. IEEE Trans. Inform. Theory 36, 1319–1333 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  30. Conway, J.H., Sloane, N.J.A.: Orbit and coset analysis of the Golay and related codes. IEEE Trans. Inform. Theory 35, 1038–1050 (1990)

    Article  MathSciNet  Google Scholar 

  31. Conway, J.H., Sloane, N.J.A.: Erratum: A new upper bound for the minimum of an integral lattice of determinant 1. Bull. Amer. Math. Society (New Series) 24, 479 (1991)

    MATH  Google Scholar 

  32. Conway, J.H., Sloane, N.J.A.: Self-dual codes over the integers modulo 4. J. Combinatorial Theory, Ser. A 62, 30–45 (1993)

    Google Scholar 

  33. Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups. second ed., Grundlehren der Mathematischen Wissenschaften Band 290, Springer-Verlag, New~York, 1993

  34. Delsarte, P.: Four fundamental parameters of a code and their combinatorial significance. Inform. Control 23, 407–438 (1973)

    MATH  Google Scholar 

  35. Dong, C., Griess, R., Höhn, G.: Framed vertex operator algebras, codes and the moonshine module. Comm. Math. Phys. 193, 407–448 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  36. Delsarte, P., Goethals, J.-M., Seidel, J.J.: Spherical codes and designs. Geometriae Dedicata 6, 363–388 (1977)

    MATH  Google Scholar 

  37. Dong, C., Lepowsky, J.: Generalized Vertex Algebras and Relative Vertex Operators. Progress in Mathematics, Birkhäuser, Boston, 1993

  38. Delsarte, P., Levenshtein, V.I.: Association schemes and coding theory. IEEE Trans. Inform. Theory 44, 2477–2504 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  39. Dunkel, C.F.: A Krawtchouk polynomial addition theorem and wreath products of symmetric groups. Indiana Univ. Math. J. 25, 335–358 (1976)

    Google Scholar 

  40. Elkies, N.D.: A characterization of the Z n lattice. Math. Research Letters 2, 321–326 (1995)

    MathSciNet  MATH  Google Scholar 

  41. Elkies, N.D.: Lattices and codes with long shadows. Math. Res. Lett. 2, 643–651 (1995)

    MathSciNet  MATH  Google Scholar 

  42. Frenkel, I.B., Huang, Y.-Z., Lepowsky, J.: On Axiomatic Approaches to Vertex Operator Algebras and Modules. Memoirs of the AMS, Band 104, Nr. 494, American Mathmeatical Society, Providence, 1993

  43. Frenkel, I., Lepowsky, J., Meuerman, A.: Vertex operator algebras and the monster. Academic Press, San Diego, 1988

  44. Frenkel, I.B., Zhu, Y.: Vertex operator algebras associated to representations of affine and virasoro algebras. Duke Math. J. 66, 123–168 (1992)

    Google Scholar 

  45. Griess, R., Höhn, G.: Virasoro Frames and their Stabilizers for the E 8 Lattice type Vertex Operator Algebra. 2000, to appear in: Journal für die reine und angewandte Mathematik (Crelle)

  46. Gaborit, P., Huffman, W.C., Kim, J.-L., Pless, V.: On Additive Codes over GF(4). Codes and association schemes (Piscataway, NY 1999). 1–23, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 56, Amer. Math. Soc., Providence, RI, 2001

  47. Gaborit, P., Huffman, W.C., Kim, J.-L., Pless, V.: On the Classification of Extremal Additive Codes over GF(4). Proceedings of the 37th Allerton conference on communication, control and computing, UIUC, Sep. 1999, pp. 535–544

  48. Gleason, A.M.: Weight polynomials of self-dual codes and the MacWilliams identities. Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 3, Gauthier-Villars, Paris, 1971, pp. 211–215

  49. Goddard, P.: Meromorphic Conformal Field Theory. In Kac [Kac89], pp. 556–587

  50. Goethals, J.-M., Seidel, J.J.: Spherical Designs. Am. Math. Soc., Providence, 1987, pp. 255–272

  51. Höhn, G.: Classification of self-dual Vertex Operator Super Algebras with Rank smaller than 24. In preparation

  52. Höhn, G.: Genera of Vertex Operator Algebras and three dimensional Topological Quantum Field Theories. To appear in the Volume Vertex Operator Algebras in Mathematics and Physics. Fields Institute Communications, American Mathematical Society, Providence, RI

  53. Höhn, G.: Selbstduale Vertexoperatorsuperalgebren und das Babymonster. Ph.D. thesis, Universität Bonn, 1995, see: Bonner Mathematische Schriften 286

  54. Höhn, G.: Letter to Prof. F. Hirzebruch, 1996

  55. Höhn, G.: Self-dual vertex operator superalgebras with shadows of large minimal weight. Internat. Math. Res. Notices 13, 613–621 (1997)

    Article  Google Scholar 

  56. Huffman, W.C., Sloane, N.J.A.: Most primitive groups have messy invariants. Adv. Math. 32, 118–127 (1979)

    MathSciNet  MATH  Google Scholar 

  57. Huffman, W.C.: On extremal self-dual quaternary codes of lengths 18 to 28, I. IEEE Trans. Inform. Theory 36, 651–660 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  58. Huffman, W.C.: On extremal self-dual quaternary codes of lengths 18 to 28, II. IEEE Trans. Inform. Theory 37, 1206–1216 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  59. Kac, V.G. (ed.): Infinite Dimensional Lie Algebras and Lie Groups: Proceedings of the Conference Held at CIRM, Luminy, 1988. Adv. Ser. Math. Phys. 7, World Scientific, Singapore, 1989

  60. Kac, V.: Vertex algebras for beginners. University Lecture Series, vol. 10, American Mathematical Society, Providence, RI, 1997

  61. Krasikov, I., Litsyn, S.: Linear programming bounds for doubly-even self-dual codes. IEEE Trans. Inform. Theory 43, 1238–1244 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  62. Krasikov, I., Litsyn, S.: An improved upper bound on the minimum distance of doubly-even self-dual codes. IEEE Trans. Inform. Theory 46, 274–278 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  63. Kneser, M.: Klassenzahlen definiter quadratische Formen. Archiv der Mathematik 8, 241–250 (1957)

    MathSciNet  MATH  Google Scholar 

  64. Lam, C.W.H., Pless, V.: There is no (24,12,10) self-dual quaternary code. IEEE Trans. Inform. Theory 36, 1153–1156 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  65. Mathieu, É.: Mémoire sur l'étude des fonctions de plusieurs quantités, sur la manière de les former et sur les substitutions qui les laissent invariables. J. de Math. Pures et. Appl. (Ser. 2) 6, 241–323 (1861)

    MATH  Google Scholar 

  66. Milnor, J., Husemoller, D.: Symmetric Bilinear Forms. Ergebnisse der Mathematik und ihrer Grenzgebiete Band 73, Springer-Verlag, Berlin, Heidelberg, New York, 1973

  67. Minkowski, H.: Grundlagen für eine Theorie der quadratischen Formen mit ganzzahligen Koeffizienten. Mém. près. par divers savants á l'Acadèmie des Sci. Inst. nat. de France 29, (1884)

  68. Monroe, L.: Self-orthogonal greedy codes. Des. Codes Cryptogr. 9, 79–83 (1996), Second Upper Michigan Combinatorics Workshop on Designs, Codes and Geometries (Houghton, MI, 1994)

    MathSciNet  MATH  Google Scholar 

  69. Mallows, C.L., Odlyzko, A.M., Sloane, N.J.A.: Upper bounds for modular forms, lattices, and codes. J. Algebra 36, 68–76 (1975)

    MATH  Google Scholar 

  70. MacWilliams, F.J., Odlyzko, A.M., Sloane, N.J.A., Ward, H.N.: Self-dual codes over GF(4). J. Combinatorial Theory, Ser. A 25, 288–318 (1978)

    Google Scholar 

  71. Mallows, C.L., Sloane, N.J.A.: An upper bound for self-dual codes. Inform. Control 22, 188–200 (1973)

    Google Scholar 

  72. MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. Elsevier Science publishers B.V., Amsterdam, 1977

  73. MacWilliams, F.J., Sloane, N.J.A., Thompson, J.G.: Good self dual Codes exist. Discrete Math. 3, 153–162 (1972)

    Article  MATH  Google Scholar 

  74. Niemeier, H.-V.: Definite quadratische Formen der Dimension 24 und Diskriminante 1. J. Number Theory 5, 142–178 (1973)

    MATH  Google Scholar 

  75. Nikulin, V.V.: Integral symmetric bilinear forms and some of their applications. Math. USSR Izvestija 14, 103–167 (1980)

    MATH  Google Scholar 

  76. Oral, H., Phelps, K.T.: Almost all self-dual codes are rigid. J. Combinatorial Theory, Ser. A 60, 264–276 (1992)

    Google Scholar 

  77. Pless, V.: A Classification of self-orthogonal codes over GF(2). Discrete Math. 3, 209–246 (1972)

    Article  MATH  Google Scholar 

  78. Plesken, W., Pohst, M.: Constructing integral lattices with prescribed minimum, I. Math. Comput. 45, 209–221 (1985)

    MathSciNet  MATH  Google Scholar 

  79. Pless, V., Sloane, N.J.A.: On the classification and enumeration of self-dual codes. J. Combinatorial Theory, Ser. A 18, 313–335 (1975)

    Google Scholar 

  80. Rains, E.M.: Shadow bounds for self-dual codes. IEEE Trans. Inform. Theory 44, 134–139 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  81. Ray-Chaudhuri, D.K., Wilson, R.M.: On t-designs. Osaka J. Math. 12, 747–744 (1975)

    Google Scholar 

  82. Rains, E.M., Sloane, N.J.A.: Self-dual codes. Handbook of coding theory, Vol. I, II, North-Holland, Amsterdam, 1998, pp. 177–294

  83. Rains, E.M., Sloane, N.J.A.: The shadow theory of modular and unimodular lattices. J. Number Theory 73, 359–389 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  84. Ran, M., Snyders, J.: On cyclic reversible self-dual additive codes with odd length over Z 2 2. IEEE Trans. Inform. Theory 46, 1056–1059 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  85. Schellekens, A.N.: Meromorphic c=24 conformal field theories. Commun. Math. Phys. 153, 159–185 (1993)

    MathSciNet  MATH  Google Scholar 

  86. Serre, J.-P.: A course in Arithmetic. Graduate texts in mathematics, 7, Springer-Verlag, New York, Heidelberg, Berlin, 1973

  87. Siegel, C.L.: Über die analytische Theorie der quadratischen Formen. Ann. Math. 36, 527–606 (1935)

    MATH  Google Scholar 

  88. Siegel, C.L.: Berechnung von Zetafunktionen an ganzzahligen Stellen. Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 10, 87–102 (1969)

    Google Scholar 

  89. Sloane, N.J.A.: Codes over GF(4) and complex lattices. J. Algebra 52, 168–181 (1978)

    MATH  Google Scholar 

  90. Sloane, N.J.A.: Self-dual codes and lattices. Relations between combinatorics and other parts of mathematics (Proc. Sympos. Pure Math., Ohio State Univ., Columbus, Ohio, 1978), Proc. Sympos. Pure Math., XXXIV, Amer. Math. Soc., Providence, R.I., 1979, pp. 273–308.

  91. Tarnanen, H., Aaltonen, M.J., Goethals, J.-M.: On the nonbinary Johnson scheme. Eur. J. Combinatorics 6, 279–285 (1985)

    MathSciNet  MATH  Google Scholar 

  92. Tietäváinen, A.: On the nonexistence of perfect codes over finite fields. SIAM J. Appl. Math. 24, 88–96 (1973)

    Google Scholar 

  93. Turaev, V.G.: Quantum Invariants of Knots and 3-Manifolds. de Gruyter Studies in Mathematics, Walter de Gruyter, Berlin, New York, 1994

  94. Venkov, B.B.: Even unimodular extremal lattices. Trudy Mat. Inst. Steklov 165, 43–48 (1984)

    MathSciNet  MATH  Google Scholar 

  95. Ward, H.N.: A restriction on the weight enumerator of a self-dual code. J. Combinatorial Theory, Ser. A 21, 253–255 (1976)

    Google Scholar 

  96. Zhu, Y.: Vertex Operator Algebras, Elliptic Functions, and Modular Forms. Ph.D. thesis, Yale University, 1990, appeared as: Modular invariance of characters of vertex operator algebras. J. Amer. Math. Soc 9 (1996)

Download references

Author information

Authors and Affiliations

  1. Mathematisches Institut der Universität Freiburg Eckerstraße 1, 79104, Freiburg, Germany

    Gerald Höhn

Authors
  1. Gerald Höhn
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gerald Höhn.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Höhn, G. Self-dual codes over the Kleinian four group. Math. Ann. 327, 227–255 (2003). https://doi.org/10.1007/s00208-003-0440-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00208-003-0440-y

Keywords

Search

Navigation