On Duursma Zeta Functions of Type IV Virtual Codes
Midn Sarah Catalano
4-21-2008

# Motivation

1. Considerable work has been devoted to the study of self-dual codes. Iwan M. Duursma has written numerous papers on the matter (see [D1]-[D6]) and the greater part of this project is centered on his ground breaking work in the field. In 1999, Iwan M. Duursma defined the zeta function for a linear code as a generating function of its Hamming weight enumerator. The modest goal of this project is to go through Duursma's papers and evaluate its relevance for formally self-dual codes. Duursma's work in Extremal Weight Enumerators and Ultraspherical Polynomials will be extended to formally self-dual codes. More specifically, the project expands Duursma's work in this paper to zeta functions of formally self-dual codes of Type IV. (In fact, Duursma's work extends to the even broader class of virtual self-dual weight enumerators of Type IV. Theorems 9 and 11 below are extended to the weight enumerator case. See the remark before Definition 12 in §3 for details.)

2. The final and more ambitious goal of the project is to study the formulation for a Riemann hypothesis analog. The unsolved Riemann hypothesis has been a mystery since Riemann's work in the 1800's. The search for an analog for linear codes arose in the 1990's. This hypothesis deals with the nature of non-trivial zeros for zeta functions. The main result of this project, which deals with the Riemann hypothesis analog in a special case, is Theorem 16 below.

3. Examples of Duursma Zeta functions of self-dual codes of small length are computed in §4 with the help of the mathematical software program SAGE[S].

# Introduction

Studying error correcting codes is necessary in advancing technology. The safe and reliable transfer of information depends on coding theory. The problem of transferring dependable information is important and this research project attempts to continue incremental progress in this field.

This project has value because the study of error correcting codes is relatively new. Profound advancement can be made in this field and is necessary for the transfer of reliable and safe information. The study of error correcting codes, as conducted in this research project, is specifically related to reliable communications. This is especially pertinent to Naval Reactors as nuke power begins to rely more heavily on computer communications. The need for such communication to be reliable is paramount. Error correcting codes are vital to systems, such as nuclear reactors, that depend upon computers and cannot be allowed to miscommunicate. More knowledge of this topic is crucial to the overarching goals of the Navy. This is especially true if the Navy continues with its plans for unmanned ships. The military depends upon reliable, fault-tolerant communication and this research project aims to continue research in the pertinent field of coding theory.

## General Background

Let denote a finite field with elements, where is a power of a prime. A linear code is a subspace of for some . This integer is called the length of . Let be a linear code of length over . If then the code is called binary. Similarly, if then the code is called ternary and if then the code is called quaternary. Throughout, assume that has been given the standard basis , , ..., and the usual dot product. The dimension of is denoted , so the number of elements of is equal to .

Another important parameter associated to the code is the number of errors which it can, in principle, correct. The Hamming metric is useful for quantifying such errors. For any two , let denote the number of coordinates where these two vectors differ:

 (1)

Define the weight of to be the number of non-zero entries of . Note, because the vector has non-zero entries only at locations where and differ. The smallest distance between distinct codewords in a linear code is the minimum distance of :

 (2)

(for details see [HILL] Theorem 5.2). Call a linear code of length , dimension , and minimum distance an code, or code if we wish to disregard the minimum distance. The Singleton Bound states that if an linear code over exists, then . An MDS Code, or Maximum Distance Seperable, is one where the equality holds.

A linear code of length and dimension over has a basis of vectors of length . If those vectors are arranged as rows of a matrix , call the matrix a generator matrix for .

The dual code of is the vector space of all code words in which are orthogonal to each codeword in ;

is self-dual if .

Example 1   Let

be the generator matrix of a code . This is a binary self-dual code. In fact, this is an extremal Type II code (these terms will be defined below).

Example 2   Let

be the generator matrix of a code . This is a ternary self-dual code. In fact, this is an extremal Type III code (these terms will be defined below).

Example 3   Define the finite field of four elements as follows. Let denote a root of the quadratic polynomial , where denotes the polynomial ring in the indeterminate . Let . This set is a field of characteristic . Let

be the generator matrix of a code . This is a quaternary self-dual code and is referred to as the hexacode. In fact, this is an extremal Type IV code (these terms will be defined below). Note that this code is MDS.

The dual code of has parameters . Moreover, denote the minimum distance of the dual code by . For future reference, note that if then (equating dimensions) , forcing to be even and . The genus of an -code is defined by

This measures how far away the code is from being MDS''.

Lemma 4   If is a self-dual code then its genus satisfies .

proof: It suffices to show that if . But this was observed in the discussion above.

The (Hamming) weight enumerator polynomial is defined by

where

denotes the number of codewords of weight . Let , so therefore . The support of is the set . If then is called a formally self-dual code. The spectrum of is the list of coefficients of :

Two codes are formally equivalent if they have the same spectrum.

## MacWilliams Identity

The goal of this section is to prove the MacWilliams identity (for simplicity, restricted to the binary case). This identity is necessary to verify the functional equation (4) for the Duursma Zeta Function. Several lemmas are needed to prove this identity. The proof given below follows Hill Ch. 13 [HILL].

Lemma 5   Let be a binary linear code.
1. Fix . As ranges over the vector space , the quantity takes the value 0 and equally often.
2. The following identity holds:

proof: Part 1: Let and . Let be a codeword of C such that . Let . Then , for if , then . Similarly . Hence, . Thus, .

Part 2: If , then for all , and so . If then by Part 1, as ranges over the vector space , the quantity takes the value 0 and equally often, giving .

Lemma 6   For each the following polynomial identity holds:

proof:

since , if , and , if .

Theorem 7 (MacWilliams' identity)   : If is a linear code over any finite field of order then

This is the general statement of the MacWilliams identity. This proof will restrict to the binary case.

proof: Now, express the polynomial in two ways.

On one hand, Lemma 6 implies

On the other hand, reversing the order of summation gives

Replace by in the above gives

Since this polynomial is homogeneous in degree , multiplying both sides by gives the theorem in the binary case.

If , then . Therefore, the MacWilliam's Identity can be rewritten in this case as

where .

# Duursma Zeta Function

## Definition

The following definition generalizes the idea of the weight enumerator polynomial of a code.

Definition 8   A homogeneous polynomial of degree with complex coefficients is called a virtual weight enumerator (or VWE) with support . If with then call the length of and the minimum distance of . Such an of even degree satisfying the invariance condition

is called a virtual self-dual weight enumerator (or VSDWE for short) over having genus.

If is an integer and then the VWE is called -divisible.

An example of a virtual weight enumerator is the Hamming weight enumerator of a code . In fact, in case the length of is the length of the code and the minimum distance of is the minimum distance of the code . An example of a virtual self-dual weight enumerator is the Hamming weight enumerator of a self-dual code.

It is amazing that the -divisible virtual self-dual weight enumerators can be classified.

Theorem 9 (Gleason-Pierce-Assmus-Mattson)   Let be a -divisible VSDWE over .

Then either

I.
,

II.
, ,

III.
,

IV.
, ,

V.
is arbitrary, , and .

For Assmus and Mattsons proof of this theorem, please see Sloane [Sl].

Next, in order to carefully define the problem that this paper addresses, the notion of Types of weight enumerators are introduced. Theorem 9 motivates the following definition.

Definition 10

If is a -divisible VSDWE over then is called

The divisibility condition is extremely restricting and, for example, forces the length to be even. The next sections concentrate on Duursma zeta functions for certain weight enumerators of Type IV.

Theorem 11 (Sloane-Mallows-Duursma)   If is a -divisible VSDWE with length and minimum distance then

For a proof, see Duursma [D3].

An extremal -divisible virtual self-dual weight enumerator is one for which equality holds in the above theorem. The next section focuses on the Type IV extremal case. With Theorems 9 and 11, the foundations of Duursma's paper [D3] extend from self-dual codes to virtual self-dual weight enumerators. This is because the coding-theoretic versions of the Theorem 9 and 11, used by Duursma, in fact hold for virtual self-dual weight enumerators.

Definition 12 (Duursma [D1])   Assume is a virtual weight enumerator polynomial of length and minimum distance . A polynomial of degree for which

is called a Duursma zeta polynomial of .

Proposition 13   If and then there exists a unique Duurzma zeta polynomial of degree .

proof: This is proven in the appendix to Chinen [C2]. Here is the rough idea. Expand in powers of to get

where are coefficients which may depend on . The Duursma polynomial is a polynomial of degree . Provided , the Duursma polynomial can be written as . Now, rewrite the terms of degree

by means of the matrix equation given by

The diagonal entries of this matrix are binomial coefficients, hence are non-zero. Therefore the matrix is invertible and the existence is established.

To establish uniqueness, suppose that

and

hold. Subtracting these gives

This forces .

An example will be given in §4.

The Duursma zeta function of is defined in terms of the zeta polynomial by means of

 (3)

In case of ambiguity denote this function by . Define the Riemann hypothesis to be the following statement: all (complex) zeros of satisfy . This is the analog for linear codes of the still unsolved conjecture regarding the Riemann zeta function.

The Duursma zeta function satisfies an analog of the functional equation for the Riemann zeta function. But before stating the functional equation, new notation is needed.

Define by , where

Then there is a functional equation relating and (and hence also and ). Note that even though may not depend on , (and hence ) does.

Proposition 14

The Duursma zeta function satisfies the functional equation

 (4)

Analogously, the zeta polynomial satisfies the functional equation

 (5)

where and .

This paper concerns the zeros of the zeta function in the case where is an extremal virtual -divisible self-dual weight enumerator of type IV.

## Extremal Virtual Self-Dual Weight Enumerators

Following Duursma [D3], define the ultraspherical polynomial on the interval by

The following theorem1 is due to Duursma [D3], section 5.2.

Theorem 15

Where and is the Duursma zeta polynomial of an extremal Type IV virtual self-dual weight enumerator of length and minimum distance .

The main result is stated below.

Theorem 16   The Duursma zeta function of an extremal self-dual weight enumerator of Type IV with length divisible by 3 satisfies the Riemann hypothesis.

proof: It's a known fact [Sz] that all the roots of ultraspherical polynomials lie on the interval . This polynomial is degree and so there are such roots. In the theorem above, replacing by gives

Therefore, all the roots of the degree polynomial , hence the roots of , lie on the circle of radius . According to Duursma [D3], §4.4, all other Type IV extremal virtual self-dual weight enumerators have length of the form or . This verifies the Riemann hypothesis in the case with length divisible by .

# Examples

The first example below computes a Duursma zeta function by hand'' in a simple case.

Example 17   Consider the binary self-dual code of length , dimension , and minimum distance . This is unique up to equivalence and has weight enumerator . The SAGEcommands

[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage]

sage: q = var("q")
sage: T = var("T")
sage: x = var("x")
sage: y = var("y")
sage: f1 = lambda q,T,N: sum([ sum([q^i for i in range(k+1)])*T^k for k in range(N)])
sage: f2 = lambda x,y,T,n: sum([ binomial(n,j)*(x-y)^j*y^(n-j)*T^j for j in range(n+1)])
sage: a0,a1,a2,a3,a4 = var("a0,a1,a2,a3,a4")
sage: F = expand(f1(2,T,6)*f2(x,y,T,6)*(a0+a1*T+a2*T^2+a3*T^3+a4*T^4))


compute the first terms (as a power series in ) of the series when , , , and . Next, SAGEcomputes the coefficients and read off the matrix :

[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage]

sage: aa = (F.coeff("T^4")).coeffs("x")
sage: v = [expand(aa[i][0]/y^(6-i)) for i in range(5)]
sage: B0 = [v[0].coeff("a%s"%str(i)) for i in range(5)]
sage: B1 = [v[1].coeff("a%s"%str(i)) for i in range(5)]
sage: B2 = [v[2].coeff("a%s"%str(i)) for i in range(5)]
sage: B3 = [v[3].coeff("a%s"%str(i)) for i in range(5)]
sage: B4 = [v[4].coeff("a%s"%str(i)) for i in range(5)]
sage: B0.reverse(); B1.reverse(); B2.reverse(); B3.reverse(); B4.reverse()
sage: B = matrix([B0,B1,B2,B3,B4])
sage: B

[  1  -3   4  -2   1]
[  0   6 -12  12   0]
[  0   0  15 -15  15]
[  0   0   0  20   0]
[  0   0   0   0  15]


Note that the diagonal entries are binomial coefficients.

Finally, the vector is determined by solving the equation :

[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage]

sage: Wmx6 = 3*x^4*y^2+3*x^2*y^4+y^6
sage: c = [Wmx6(1,y).coeff("y^%s"%str(i)) for i in range(2,7)]
sage: c.reverse()
sage: cc = vector(c)
sage: (B^(-1)*cc).list()
[4/5, 0, 0, 0, 1/5]

This implies that the zeta polynomial of is given by .

The next example illustrates the computation of the Duursma zeta function for a quaternary code.

Example 18   The hexacode is an MDS code. In general, it is true that the Duursma zeta function of any MDS code is .

Here is a more interesting example. Let denote the same element as was defined in Example 3. Let

be a generator matrix of a code . This is an extremal Type IV code over a field with four elements. According to SAGE, the zeta polynomial for this code is . It can be checked directly, using SAGE, that this satisfies the Riemann hypothesis.
[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage]

sage: F.<z> = GF(4,"z")
sage: MS = MatrixSpace(F, 9, 18)
sage: G = MS([
....: [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, z^2, 1, 1, z, 1, 1, z^2, z],\
....: [0, 1, 0, 0, 0, 0, 0, 0, 0, z^2, z^2, 0, z, 0, 1, z, z^2, z^2],\
....: [0, 0, 1, 0, 0, 0, 0, 0, 0, z^2, 1, 0, z^2, z^2, z^2, z, 0, z],\
....: [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, z^2, 1, 0, z^2, z^2, z^2, z, z],\
....: [0, 0, 0, 0, 1, 0, 0, 0, 0, z, 1, 1, z^2, z^2, 1, 1, z, 1],\
....: [0, 0, 0, 0, 0, 1, 0, 0, 0, z, z^2, z^2, z^2, 0, 1, z^2, 0, z],\
....: [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, z, z^2, z^2, z^2, 0, 1, z^2, z],\
....: [0, 0, 0, 0, 0, 0, 0, 1, 0, z^2, z, 1, 0, z, 0, z^2, z^2, z^2],\
....: [0, 0, 0, 0, 0, 0, 0, 0, 1, z^2, 1, 1, z, 1, 1, z^2, 1, z]])
sage: C = LinearCode(G)
sage: print C.spectrum()
[1, 0, 0, 0, 0, 0, 0, 0, 2754, 0, 18360, 0, 77112, 0, 110160, 0, 50949, 0, 2808]
sage: R.<T> = PolynomialRing(CC,"T")
sage: P = C.sd_zeta_polynomial(4)
sage: P
48/143*T^4 + 48/143*T^3 + 32/143*T^2 + 12/143*T + 3/143
sage: rts = R(P).roots()
sage: [abs(r[0]) for r in rts]
[0.500000000000000, 0.500000000000000, 0.500000000000000, 0.500000000000000]


Background Information: SAGEis a computer algebra program whose open source kernel is written in the Python programming language.

Acknowledgements: I thank the readers of this honors project for their helpful suggestion that improved this presentation. The SAGEexamples are due to my advisor. I also thank Prof. Philippe Gaborit for the generator matrix of the last example and Prof. Thann Ward for the reference to Sloane [Sl].

## Bibliography

C1
K. Chinen, Zeta functions for formal weight enumerators and the extremal property, Proc. Japan Acad. Ser. A Math. Sci. vol. 81, Number 10 (2005), 168-173.

C2
---, Zeta functions for formal weight enumerators and an analogue of the Mallows-Sloane bound, http://arxiv.org/pdf/math/0510182, http://front.math.ucdavis.edu/math.NT/0510182

C3
---, An abundance of invariant polynomials satisfying the Riemann hypothesis,'' http://arxiv.org/abs/0704.3903`

D1
I. Duursma, Combinatorics of the two-variable zeta function, in Finite fields and applications, 109-136, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004.

D2
---, Results on zeta functions for codes, Fifth Conference on Algebraic Geometry, Number Theory, Coding Theory and Cryptography, University of Tokyo, January 17-19, 2003.

D3
---, Extremal weight enumerators and ultraspherical polynomials, Discrete Mathematics, vol. 268, no. 1-3, pp. 103-127, July 2003.

D4
---, A Riemann hypothesis analogue for self-dual codes, In: Codes and Association schemes, Eds. Barg and Litsyn, AMS Dimacs Series, vol. 56, pp. 115-124, 2001.

D5
---, From weight enumerators to zeta functions, in Discrete Applied Mathematics, vol. 111, no. 1-2, pp. 55-73, 2001.

D6
---, Weight distributions of geometric Goppa codes, Transactions of the AMS, vol. 351, pp. 3609-3639, September 1999.

HILL
R. Hill A First Course In Coding Theory, Oxford University Press. (1986).

HP
W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge Univ. Press, 2003.

MS
F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-correcting Codes. North-Holland. (1983)

S
The SAGEGroup, SAGE: Mathematical software, version 2.11
http://www.sagemath.org/

Sl
N. J. A. Sloane, Self-dual codes and lattices, in Relations Between Combinatorics and Other Parts of Mathematics., Proc. Symp. Pure Math., Vol. 34, American Mathematical Society, Providence, RI, 1979, pp. 273-308.

Sz
G. Szegö, Orthogonal Polynomials Vol XXIII, American Mathematical Society, 4th Edition, Colloquium Publications, Providence, RI, 1975.

The command line arguments were:
latex2html -t 'S. Catalano Math Honors Thesis 2007-2008' -no_navigation -split 0 CatalanoHonorsFinal.tex

The translation was initiated by david joyner on 2008-04-21

#### Footnotes

... theorem1
Be careful of typos in section 5.2 of Duursma, which are corrected below.

david joyner 2008-04-21