Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Toy Models for D. H. Lehmer’s Conjecture II Read chapter Read first chapter

2013 | OriginalPaper | Chapter

Weighted Generating Functions for Type II Lattices and Codes

Authors : Noam D. Elkies, Scott Duke Kominers

Published in: Quadratic and Higher Degree Forms

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We give a new structural development of harmonic polynomials on Hamming space, and harmonic weight enumerators of binary linear codes, that parallels one approach to harmonic polynomials on Euclidean space and weighted theta functions of Euclidean lattices. Namely, we use the finite-dimensional representation theory of \(\mathfrak{s}\mathfrak{l}_{2}\) to derive a decomposition theorem for the spaces of discrete homogeneous polynomials in terms of the spaces of discrete harmonic polynomials, and prove a generalized MacWilliams identity for harmonic weight enumerators. We then present several applications of harmonic weight enumerators, corresponding to some uses of weighted theta functions: an equivalent characterization of t-designs, the Assmus–Mattson Theorem in the case of extremal Type II codes, and configuration results for extremal Type II codes of lengths 8, 24, 32, 48, 56, 72, and 96.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Almost Universal Ternary Sums of Squares and Triangular Numbers
next chapter Quadratic Forms and Automorphic Forms
Footnotes
1
While the analogy between \(\Theta _{L,P}\) and W C, Q suggests calling W C, Q a “weighted weight enumerator”, the comical juxtaposition of the two senses of “weight” dissuades us from using that phrase. Since Bachoc [Bac99] had already introduced the term “harmonic weight enumerator” that avoids this juxtaposition, we happily follow her usage.
 
2
The second of these requires only the W C, Q for Q of degree 1, which coincide with Ott’s “local weight enumerators” [Ott99].
 
3
Serre [Ser73, Chap. VII] uses the notation E n for our D n  +  for all n ≡ 0 mod 8, but this notation has not been widely adopted. For n ≡ 4 mod 8 the Type I lattice D n  +  is isomorphic with \({\mathbb{Z}}^{n}\) if and only if n = 4.
 
4
That is, a modular form that vanishes at all the cusps; for \(\mathrm{SL}_{2}(\mathbb{Z})\) there is only one cusp, at \(\mathop{\mathrm{Im}}(\tau ) \rightarrow \infty \), so a modular form in \(\mathrm{SL}_{2}(\mathbb{Z})\) is a cusp form if and only if its expansion as a power series in q has constant coefficient zero. Note that the notation of [Ser73] diverges from the usual practice that we follow: our \(\mathcal{E}_{4}\), \(\mathcal{E}_{6}\), and \(\Delta \) are what Serre calls E 2, E 3 and \({(2\pi )}^{-12}\Delta \). (We use “\(\mathcal{E}\)” rather than “E ” to avoid confusion with the E 8 lattice.)
 
5
The use of \(\mathsf{\Delta }\) for this operator and \(\Delta \) for the modular form \({\eta }^{24} = q\prod _{n=1}^{\infty }{(1 - {q}^{n})}^{24}\) may be unfortunate, but should not cause confusion, despite the similarity between the two symbols, because they never appear together outside this footnote. The alternative notation L for the Laplacian would be much worse, as we regularly use L for a lattice.
 
6
This is where it becomes natural to use \(\varpi = 2\pi\) when choosing the images of the generators (2.18) of \(\mathfrak{s}\mathfrak{l}_{2}\): conjugation by G t then takes (X, H, Y) to (X − t H − t 2 Y, H + 2t Y, Y); other choices would produce more complicated coefficients.
 
7
In this setting \(\frac{n} {2} + d\) cannot be as small as 2 because n ≥ 8, but the possibility of weight 2 arises in the proof of Lemma 2.12.
 
8
With this definition ∅ is a t-design for all t. For most applications only nonempty designs are of interest; for instance it is only when D is nonempty that we can divide both sides of (2.29) by | D | to get the equivalent condition that the average of any polynomial of degree at most t over \(\Sigma _{\nu }\) can be computed by averaging it over  | D | . But we allow empty designs here, and also later in the coding-theoretic setting, because this simplifies the statements of the results relating lattices with spherical designs.
 
9
See [Del78] for explanation of the term “r-design” for this property. For D≠∅, the t-design property is one way to make precise the idea that D is “well distributed” in \(\Sigma _{\nu }\), and better distributed as t grows. One application, and the original one according to [CS99, pp. 89–90], is numerical integration on \(\Sigma _{\nu }\), using the right-hand side of (2.29) as an approximation to the left-hand side even when P is not polynomial but smooth enough to be well approximated by polynomials.
 
10
Suppose C is a self-dual code of length n. Then C contains the all-1s vector 1, because (v, v) = (v, 1) for all \(v \in \mathbb{F}_{2}^{n}\), so C ⊆ C  ⊥  implies 1 ∈ C  ⊥ . Thus C descends to a vector space of dimension (n ∕ 2) − 1 in V: = { 0, 1} ⊥  ∕ {0, 1}. Since 2∣n, the perfect pairing ( ⋅,  ⋅) descends to a perfect pairing on V, so a self-dual code is tantamount to a maximal isotropic subspace of V relative to this pairing. If 4∣n then the map \(\{0,{\mathbf{1}\}}^{\perp }\rightarrow \mathbb{F}_{2}\), v↦(wt(c) ∕ 2) mod 2 descends to a quadratic form \(\mathrm{Q}: \mathrm{V} \rightarrow \mathbb{F}_{2}\) consistent with that pairing. A Type II code is then a self-dual code C that is totally isotropic relative to Q. Such C exists if and only if (V, Q) has Arf invariant zero. But the Arf invariant is 0 or 1 according as {v ∈ V: Q(v) = 0} has size 2 n − 3 + 2(n ∕ 2) − 2 or 2 n − 3 − 2(n ∕ 2) − 2. But this count is \((1/2)\sum _{j=0}^{n/4}\left ({ n \atop 4j} \right ) = (1/8)\sum _{{\mu }^{4}=1}{(1+\mu )}^{n} = {2}^{n-3} + (1/4)\mathop{ \mathrm{Re}}{(1 + i)}^{n}\), so the result follows from the observation that (1 + i)4 =  − 4.
 
11
In this case, (c ′, v) takes the values 0 and 1 equally often (see [MS83, p. 127]). (This statement is just an instance of the well-known fact that the sum of a nontrivial character on a finite commutative group vanishes.) We could also adapt the technique we used in proving Theorem 2.1, obtaining discrete Poisson summation via the discrete Fourier expansion of the function \(z\mapsto \sum _{c\in C}f(c + z)\).
 
12
Note that this aligns with the expression
$$\displaystyle{\widehat{g_{{\ast}}}(u) =\sum _{v\in \mathbb{F}_{2}^{n}}{(-1)}^{(u,v)}g_{{\ast}}(v) = {(-1)}^{\sum _{j=1}^{n}u_{j}},}$$
obtained from the more common definition (3.2) of the discrete Fourier transform given earlier.
 
13
Delsarte [Del78] uses the ι v j basis, rather than the \({(-1)}^{v_{j}}\) basis. We depart from Delsarte’s notation because the use of the \({(-1)}^{v_{j}}\) basis greatly simplifies our development.
 
14
The notation \(\mathcal{D}_{d}^{k}\) is consistent with the notation \(\mathcal{D}_{d}^{0}\) for the space of degree-d discrete harmonic polynomials.
 
15
Here, \(\hat{Q}_{d}\) is the degree-d term of \(\hat{Q}\), as in the lemma statement.
 
16
To avoid having to adopt this convention, we could have used the slightly more standard notation \(\sum _{\ell=1}^{d}{(-1)}^{v_{j_{1}}+\cdots +\widehat{v_{j_{\ell}}}+\cdots +v_{j_{d}} }\). We opt not to use this notation because it conflicts with our usage of \(\hat{\cdot }\) for the discrete Fourier transform.
 
17
Again we allow D = ∅, which is a t-(n, w, 0)-design for all t and w. As with spherical designs, for most applications only nonempty D are of interest, but allowing empty designs simplifies the statements of the results relating codes with combinatorial designs.
 
18
These determinants were computed using the formula of Proposition 6.2. We omit the equations obtained from the zonal spherical harmonic polynomials of the largest degrees when there are more than \(\frac{w_{0}} {4} + 2\) equations obtained by this method.
 
19
In the coding context we could also show directly that W C is invariant under \(\left (\begin{array}{cc} 0 & 1\\ 1 & 0 \end{array} \right )\), that is, that W C (x, y) = W C (y, x). Any binary linear code C satisfies W C (x, y) = W C (y, x) if and only if C contains the all-1s vector 1: in the forward direction, the number of weight n codewords is W C (0, 1), while W C (1, 0) = 1 always; in the reverse direction, translation by 1 gives for each w a bijection between the codewords of weight w and the codewords of weight n − w. But we noted already that a self-dual code, whether of Type I or Type II, contains 1.
 
Literature
AM69.
Bac99.
Bac01.
C. Bachoc , Harmonic weight enumerators of non-binary codes and MacWilliams identities, Codes and Association Schemes (A. Barg and S. Litsyn, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 56, American Mathematical Society, 2001, pp. 1–24.
CD93.
A. R. Calderbank and P. Delsarte, On error-correcting codes and invariant linear forms, SIAM Journal on Discrete Mathematics 6 (1993), 1–23.MathSciNetMATHCrossRef
Con69.
CS99.
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, 3rd ed., Springer-Verlag, 1999.
CvL91.
P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and their Links, Cambridge University Press, 1991 (London Math. Society Student Texts 22).
Del78.
Ph. Delsarte, Hahn polynomials, discrete harmonics, and t-designs, SIAM Journal on Applied Mathematics 34 (1978), 157–166.MathSciNetCrossRef
Ebe02.
W. Ebeling, Lattices and codes: A course partially based on lectures by F. Hirzebruch, 2nd ed., Vieweg, 2002.
EK10.
N. D. Elkies and S. D. Kominers, On the classification of Type II codes of length 24, SIAM Journal on Discrete Mathematics 23 (2010), 2173–2177.MathSciNetCrossRef
EK12.
N. D. Elkies and S. D. Kominers , Configurations of extremal Type II codes, in preparation, 2013.
Elk00.
N. D. Elkies, Lattices, Linear Codes, and Invariants I, II, Notices of the American Mathematical Society 47 (2000), 1238–1245 and 1382–1391.
Elk12.
N. D. Elkies , On the quotient of an extremal Type II lattice of rank 40, 80, or 120 by the span of its minimal vectors, in preparation, 2013.
Gle71.
A. M. Gleason, Weight polynomials of self-dual codes and the MacWilliams identities, Actes, Congrés International de Mathématiques (Nice, 1970), vol. 3, Gauthiers-Villars, 1971, pp. 211–215.
KAL06.
L. F. Klosinski, G. L. Alexanderson, and L. C. Larson, The Sixty-Sixth William Lowell Putnam Mathematical Competition, American Mathematical Monthly 113 (2006), 733–743.MATHCrossRef
Kin03.
Koc87.
H. Koch, Unimodular lattices and self-dual codes, Proceedings of the International Congress of Mathematicians (Berkeley, Calif., 1986), American Mathematical Society, 1987, pp. 457–465.
Kom09a.
Kom09b.
Kör90.
T. W. Körner, Fourier Analysis, Cambridge University Press, 1990.
Lan75.
S. Lang, \(\mathrm{SL}_{2}(\mathbb{R})\), Addison-Wesley, 1975.
LS71.
Mac63.
F. J. MacWilliams, A theorem on the distribution of weights in a systematic code, Bell System Technical Journal 42 (1963), 79–84.MathSciNetCrossRef
MOS75.
C. L. Mallows, A. M. Odlyzko, and N. J. A. Sloane, Upper bounds for modular forms, lattices and codes, Journal of Algebra 36 (1975), 68–76.MathSciNetMATHCrossRef
MS73.
MS83.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, 3rd ed., North-Holland Mathematical Library, vol. 16, North-Holland, 1983.
Nie73.
H.-V. Niemeier, Definite quadratische Formen der Dimension 24 und Diskriminante 1, Journal of Number Theory 5 (1973), 142–178 (German).
Ott99.
Oze86a.
Oze86b.
M. Ozeki , On the configurations of even unimodular lattices of rank 48, Archiv der Mathematik 46 (1986), 54–61.
PS75.
V. Pless and N. J. A. Sloane, On the classification and enumeration of self-dual codes, Journal of Combinatorial Theory, Series A 18 (1975), 313–335.MathSciNetMATHCrossRef
Rud76.
W. Rudin, Principles of Mathematical Analysis, 3rd ed., McGraw-Hill, 1976.
Ser73.
J.-P. Serre, A Course in Arithmetic, Springer-Verlag, 1973.
Ser87.
J.-P. Serre , Complex Semisimple Lie Algebras, Springer-Verlag, 1987.
Sie69.
C. L. Siegel, Berechnung von Zetafunktionen an ganzzahligen Stellen, Nachrichten der Akademie der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse, II 1969 (1969), 87–102 [pp. 82–97 in Gesammelte Abhandlungen IV, Berlin: Springer 1979].
Slo77.
N. J. A. Sloane, Error-Correcting Codes and Invariant Theory: New Applications of a Nineteenth-Century Technique, American Mathematical Monthly 84 (1977), 82–107.MathSciNetMATHCrossRef
ST54.
Ven80.
B. B. Venkov, On the classification of integral even unimodular 24-dimensional quadratic forms, Proceedings of the Steklov Institute of Mathematics 148 (1980), 63–74, ≅ [CS99, Chapter 18].
Ven84.
B. B. Venkov , Even unimodular Euclidean lattices in dimension 32, Journal of Mathematical Sciences 26 (1984), 1860–1867.
Ven01.
B. B. Venkov , Réseaux et designs sphériques, Réseaux Euclidiens, Designs Sphériques et Formes Modulaires, Monographies de L’Enseignement Mathématique, vol. 37, Enseignement Mathematique, Genève, 2001, pp. 10–86 (French).
Metadata
Title
Weighted Generating Functions for Type II Lattices and Codes
Authors
Noam D. Elkies
Scott Duke Kominers
Copyright Year
2013
Publisher
Springer New York
Book
Quadratic and Higher Degree Forms

Print ISBN: 978-1-4614-7487-6

Electronic ISBN: 978-1-4614-7488-3

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-1-4614-7488-3_4

Premium Partner

    Image Credits