\documentclass[12pt]{article} %\usepackage{amssymb} %\usepackage{amsthm} \usepackage{amscd} \usepackage{amsfonts} \usepackage{hyperref} \usepackage{makeidx} % allows for index generation \usepackage{url} \usepackage{xspace} \usepackage{fancyvrb} \usepackage{moreverb} \usepackage{graphicx, amsmath} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{axiom}{Axiom} \newtheorem{oq}{Open Question} \newtheorem{remark}{Remark} \newtheorem{exercise}{Exercise}[section] \def\ppp{{\mathbb{P}}} \def\hhh{{\mathbb{H}}} \def\aaa{{\mathbb{A}}} \def\fff{{\mathbb{F}}} \def\qqq{\mathbb{Q}} \def\rrr{\mathbb{R}} \def\ccc{\mathbb{C}} \def\zzz{\mathbb{Z}} \def\nnn{\mathbb{N}} \def\pf{{\bf proof}:\ } \def\qed{$\Box$} \def\wt{{\rm wt}} \def\supp{{\rm supp}} \newcommand{\SAGE}{{\sf SAGE}\ } \newcommand{\sage}{\SAGE} \makeindex \begin{document} \author{David Joyner\thanks{wdjoyner@gmail.com; Math Dept, USNA, Annapolis, MD. These notes are licensed under the Attribution-ShareAlike Creative Commons license, \url{http://creativecommons.org/about/licenses/meet-the-licenses}. }} \title{Duursma zeta functions - a survey\\ (11th draft)} \date{5-24-2008} \maketitle \begin{abstract} This is a purely expository survey paper on the Duursma zeta function of a linear block code. \sage code is used to compute examples. \end{abstract} \vskip .2in \tableofcontents \vskip .4in Let $C$ be an $[n,k,d]_q$ code, ie a linear code over $GF(q)$ of length $n$, dimension $k$, and minimum distance $d$. Motivated by analogies with local class field theory, in \cite{D1} Iwan Duursma introduced the {\it zeta function} $Z=Z_C$ associated to a linear code $C$ over a finite field, \begin{equation} \label{eqn:zeta} Z(T)=\frac{P(T)}{(1-T)(1-qT)}, \end{equation} where $P(T)$ is a polynomial of degree $n+2-d-d^\perp$, called the {\it zeta polynomial}\footnote{In general, if $C$ is an $[n,k,d]$-code then we use $[n,k^\perp,d^\perp]$ for the parameters of the dual code, $C^\perp$. It is a consequence of Singleton's bound that $n+2-d-d^\perp\geq $, with equality when $C$ is an MDS code.}. This paper will explore some of the properties of the zeta function and give examples using the software package \sage \cite{S}. \section{Introduction} \label{sec:intro} A linear code $C$ is called a $[n,k,d]_q$-code if it is a $k$-dimensional subspace of $GF(q)^n$ having minimum distance $d$, \[ d = \min_{c\in C,c\not= 0} \wt(c), \] where $\wt$ is the Hamming weight of a codeword. The dual code of $C$, denoted $C^\perp$, has parameters $[n,n-k,d^\perp]$, for some $d^\perp \geq 1$. If $C=C^\perp$ then the code is called {\it self-dual}. The {\it genus} of an $[n,k,d]_q$-code $C$ is defined by \index{genus of a linear code} \index{code!self-dual} \[ \gamma(C) = n+1-k -d. \] This measures how ``far away the code is from being MDS''. If $C$ is an AG code constructed from the Riemann-Roch space of an algebraic curve over $GF(q)$ then it often is equal to the genus of the curve (see \cite{TV} for details). Note that if $C$ is a self-dual code then its genus satisfies $\gamma = n/2+1-d$. The {\it (Hamming) weight enumerator polynomial} $A_C$ is defined by \index{weight enumerator!polynomial (Hamming)} \[ A_C(x,y) = \sum_{i=0}^n A_i x^{n-i}y^i = x^n + A_dx^{n-d}y^d+\dots +A_ny^n, \] where \[ A_i = |\{c\in C\ |\ \wt(c)=i\}| \] denotes the number of codewords of weight $i$. The {\it support of $C$} is the set $\supp(C)=\{i\ |\ A_i\not= 0\}$. If $A_C(x,y)=A_{C^\perp}(x,y)$ then $C$ is called a {\it formally self-dual code}. The {\it spectrum of $C$} is the list of coefficients of $A_C$: %\index{formally self-dual code} \index{spectrum} \index{code!formally self-dual} \index{support} \[ spec(C)=[A_0,\dots ,A_{n}]. \] We say two codes are {\it formally equivalent} if they have the same spectrum. \index{code!formally equivalent} \begin{example} Here is a code $C$ which is formally self-dual. Let \[ G = \left( \begin{array}{rrrrrrrrrr} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{array} \right) \] and let $G$ be the binary code generated by $G$. This code has spectrum $[1, 0, 0, 0, 15, 0, 15, 0, 0, 0, 1]$ and satisfies the ``Riemann hypothesis'' (see Definition \ref{defn:RH} below for this term). Here is the \sage code verifying this. \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: MS = MatrixSpace(GF(2),5,10) sage: G = MS([[1,1,1,1,0,0,0,0,0,0],[0,0,0,0,1,1,1,1,1,1],[1,0,0,0,1,1,1,0,0,0],\ ....: [0,1,0,0,1,1,0,1,0,0],[0,0,1,0,1,0,1,0,1,0]]) sage: C = LinearCode(G) sage: C Linear code of length 10, dimension 5 over Finite Field of size 2 sage: C.spectrum() [1, 0, 0, 0, 15, 0, 15, 0, 0, 0, 1] sage: P = C.zeta_polynomial() sage: P 2/7*T^4 + 2/7*T^3 + 3/14*T^2 + 1/7*T + 1/14 sage: RT = PolynomialRing(CC,"T") sage: rts = RT(P).roots() sage: [z[0].abs() for z in rts] [0.707106781186548, 0.707106781186546, 0.707106781186548, 0.707106781186548] sage: Cd = C.dual_code() sage: Cd.spectrum() [1, 0, 0, 0, 15, 0, 15, 0, 0, 0, 1] \end{Verbatim} \end{example} Saying two codes are formally equivalent is stronger than saying that the codes are {\it isometric}, i.e., that there is a bijective linear transformation between then that preserves the weight function. \index{code!isometric} In fact, it is known that two codes are permtation equivalent if and only if they are isometric (by a result of MacWilliams). \vskip .2in \begin{oq} Given a homogeneous polynomial $F(x,y)= x^n + \sum_{i=1}^n f_ix^{n-i}y^i$ of degree $n$ with non-negative integer coefficients, find necessary and sufficient conditions (short of enumerating all weight enumerators of linear codes with length $n$) which determine whether or not $F(x,y)=A_C(x,y)$ for some linear code $C$ of length $n$. \end{oq} \subsection{Divisible codes} If $b>1$ is an integer and $\supp(C)\subset b\zzz$ then the code $C$ is called {\it $b$-divisible}. \index{divisible!code} \index{code!divisible} \begin{definition} {\rm Let $C$ be a $b$-divisible code. If $C$ and $C^\perp$ both binary and contain the all-ones codeword then $C$ is said to be {\it Type 2 divisible}. We say $C$ is {\it Type 1 divisible} if $C$ is not of Type 2. } \end{definition} \index{Type 2 divisible code} \index{Type 1 divisible code} \begin{lemma} \label{lemma:bounds} If $C$ is Type 1 divisible then \[ d+bd^\perp \leq n+b(b+1). \] If $C$ is Type 2 divisible then \[ 2d+bd^\perp \leq n+b(b+2). \] \end{lemma} \pf See Theorem 1 in Duursma \cite{D3}. \qed \vskip .1in The Gleason-Pierce Theorem\footnote{See Theorem 2.5.1 in \cite{NRS}, also Theorem \ref{thrm:GPAM} below.} basically says that, other than a family of uninteresting examples, the formally self-dual divisible codes fall into one of the following four types. \index{Gleason-Pierce Theorem} \begin{definition} \label{defn:sdtype} {\rm Let $C$ be a fsd $b$-divisible $[n,k,d]_q$-code. We say $C$ is {\it Type I} if $q=b=2$, and $n$ is even. We say $C$ is {\it Type II} if $q=2$, $b=4$, and $8|n$. We say $C$ is {\it Type III} if $q=b=3$, and $4|n$. If $q=4$, $b=2$, and $n$ is even then $C$ is said to be {\it Type IV}. } \end{definition} For example, if $C$ is a binary self-dual code, then it must be $2$-divisible (since each codeword must be orthogonal to itself, hence have even weight). This implies that $C^\perp$ contains the all-ones vector. But $C=C^\perp$, so $C$ must be Type $2$. \begin{lemma} (upper bounds) \label{lemma:bounds2} If $C$ is sd then \[ d \leq \left\{ \begin{array}{ll} 2[n/8]+2, & {\rm if\ }C{\rm \ is\ Type\ I},\\ 4[n/24]+4, & {\rm if\ }C{\rm \ is\ Type\ II},\\ 3[n/12]+3, & {\rm if\ }C{\rm \ is\ Type\ III},\\ 2[n/6]+2, & {\rm if\ }C{\rm \ is\ Type\ IV}. \end{array} \right. \] \end{lemma} \pf This is Theorem 9.3.1 in \cite{HP}. \qed These upper bounds are sometimes referred to as the {\it Mallows-Sloane bounds}. In fact, the ``Type I bound'' \index{Mallows-Sloane bounds} even holds for formally self-dual codes (see Theorem 9.3.1 in \cite{HP}, \S 11.1 in \cite{NRS}). \vskip .1in A code is called {\it optimal} if its minimum distance is maximal among all linear codes of that length and dimension. A code $C$ is called {\it extremal} if the bound in Lemma \ref{lemma:bounds2} holds with equality. \index{code!optimal} \index{code!extremal} \begin{remark} {\rm (1) It is known that any two extremal codes (if they exist) have the same weight enumerator polynomial (in fact, they are essentially determined in Duursma \cite{D3}). (2) It is known that there exist only finitely many extremal codes (see \S 11.1 in \cite{NRS} or Huffman and Pless \cite{HP}, p 345). } \end{remark} \vskip .1in \noindent If $C^\perp$ denotes the dual code of $C$, with parameters $[n,n-k,d^\perp]$, then the MacWilliams identity\footnote{This is proven in the appendix below.} relates the weight enumerator of $C^\perp$ to that of $C$: \index{MacWilliams identity} \[ A_{C^\perp}(x,y) = |C|^{-1}A_C(x+(q-1)y,x-y). \] In particular, $C$ is formally self-dual if and only if $F=A_C$ satisfies the invariance condition \begin{equation} \label{eqn:fsd} F(x,y) = F(\frac{x+(q-1)y}{\sqrt{q}},\frac{x-y}{\sqrt{q}}). \end{equation} \begin{example} \label{example:WEs} {\rm The following examples are taken from Sloane \cite{Sl}. The notation is as in \cite{Sl} and will be used in the statement of Theorem \ref{thrm:types} below. \begin{enumerate} \item $W_1(x,y)=x^2+y^2$ is the weight enumerator of the Type I code $C=\{(0,0),(1,1)\}$. \item % $W_2(x,y)=x^3+y^3$ % $W_3(x,y)=x^3+3xy^2$ % $W_4(x,y)=x^7+7x^4y^3+7x^3y^4+y^7$ $W_5(x,y) = x^8+14x^4y^4+y^8$ is the weight enumerator of the Type II $[8,4,4]$ code $C$ constructed by extending the binary $[7,4,3]$ Hamming code by a check bit. This is the smallest Type II code. \item $W_6(x,y)=x^{24}+759x^{16}y^8+2576x^{12}y^{12}+759x^8y^{16}+y^{24}$ is the weight enumerator of the binary Golay code with parameters $[23,12,8]$. \item % $W_7(x,y)=$ $W_8(x,y)=x^{48}+17296(x^{36}y^{12}+x^{12}y^{36})+ 535095(x^{32}y^{16}+x^{16}y^{32})+ 3995376(x^{28}y^{20}+x^{20}y^{28})+ 7681680x^{24}y^{24}$ is the weight enumerator of the extended binary quadratic residue code of associated to $p=47$ with parameters $[48,24,16]$. \item $W_{9}(x,y)=x^4+8xy^3$ is the weight enumerator of the Type III ternary code $C$ with generator matrix \[ G = \left( \begin{array}{cccc} 1 & 1 & 1 & 0\\ 0 & 1 & -1 & 1 \end{array} \right) \] and parameters $[4,2,3]$. \item $W_{10}(x,y)=x^{12}+264x^6y^6+440x^3y^9+24y^{12}$ is the weight enumerator of the Type III ternary Golay code with parameters $[12,6,6]$. \item $W_{11}(x,y)=x^2+3y^2$ is the weight enumerator of the Type IV code $C=\{(0,0),(1,1),(\alpha,\alpha),(\alpha^2,\alpha^2)\}$, with parameters $[2,1,2]$. Here $\alpha$ is a generator of $GF(4)$, $\alpha^2+\alpha+1=0$. \item $W_{12}(x,y)=x^6+45x^2y^4+18y^6$ is the weight enumerator of the Type IV code $C$ with generator matrix \[ G = \left( \begin{array}{cccccc} 1 & 0 & 0 & 1 & \alpha & \alpha\\ 0 & 1 & 0 & \alpha & 1 & \alpha\\ 0 & 0 & 1 & \alpha & \alpha & 1 \end{array} \right) \] with parameters $[6,3,4]$. Here $\alpha$ is a generator of $GF(4)$, $\alpha^2+\alpha+1=0$. \end{enumerate} } \end{example} \subsection{Some invariants} The following result collects together several facts from \S 8.1 in Sloane \cite{Sl}. \begin{theorem} \label{thrm:types} {\rm Assume $C$ is a formally self-dual divisible code of Type I, II, III, or IV. \begin{itemize} \item{I.} If $C$ is Type I then $A_C(x,y)$ is invariant under the group \[ G_I=\langle \frac{1}{\sqrt{2}} \left( \begin{array}{cc} 1 & 1\\ 1 & -1 \end{array} \right), \left( \begin{array}{cc} 1 & 0\\ 0 & -1 \end{array} \right) \rangle \] of order $16$. Moreover, $\ccc [x,y]^{G_I}=\ccc [W_1,W_5]$. \item{II.} If $C$ is Type II then $A_C(x,y)$ is invariant under the group \[ G_{II}=\langle \frac{1}{\sqrt{2}} \left( \begin{array}{cc} 1 & 1\\ 1 & -1 \end{array} \right), \left( \begin{array}{cc} 1 & 0\\ 0 & i \end{array} \right) \rangle \] of order $192$. Moreover, $\ccc [x,y]^{G_{II}}=\ccc [W_5,W_6]$. \item{III.} If $C$ is Type III then $A_C(x,y)$ is invariant under the group \[ G_{III}=\langle \sigma, \left( \begin{array}{cc} 1 & 0\\ 0 & \omega \end{array} \right) \rangle, \ \ \ \ \ \sigma = \frac{1}{\sqrt{3}} \left( \begin{array}{cc} 1 & 1\\ 2 & -1 \end{array} \right), \] of order $48$, where $\omega\in GF(9)-\{1\}$, $\omega^3=1$. Moreover, $\ccc [x,y]^{G_{III}}=\ccc [W_9,W_{10}]$. \item{IV.} If $C$ is Type IV then $A_C(x,y)$ is invariant under the group \[ G_{IV}=\langle \frac{1}{2} \left( \begin{array}{cc} 1 & 1\\ 3 & -1 \end{array} \right), \left( \begin{array}{cc} 1 & 0\\ 0 & -1 \end{array} \right) \rangle \] of order $12$. Moreover, $\ccc [x,y]^{G_{II}}=\ccc [W_{11},W_{12}]$. \end{itemize} } \end{theorem} Here are some computations ilustrating the above theorem. \begin{example} {\rm Here is some \sage code for computing the invariants of the group $G$ generated by $g_1 = \left( \begin{array}{cc} 1/\sqrt{q} & 1/\sqrt{q}\\ (q-1)/\sqrt{q} & -1/\sqrt{q} \end{array} \right)$ with $q=2$, $g_2 = \left( \begin{array}{cc} -1 & 0\\ 0 & 1 \end{array} \right)$, and $g_3 = \left( \begin{array}{cc} 1 & 0\\ 0 & -1 \end{array} \right)$. The \sage method \verb+invariant_generators+ calls Singular \cite{GPS}, which has methods implements (by Simon King) to compute group invariants. } \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: F = CyclotomicField(8) sage: z = F.gen() sage: a = z+1/z sage: a^2 2 sage: MS = MatrixSpace(F,2,2) sage: b = -1 sage: g1 = MS([[1/a,1/a],[1/a,-1/a]]) sage: g2 = MS([[1,0],[0,b]]) sage: g3 = MS([[b,0],[0,1]]) sage: G = MatrixGroup([g1,g2,g3]) sage: G.invariant_generators() [x1^2 + x2^2, x1^8 + 28/9*x1^6*x2^2 + 70/9*x1^4*x2^4 + 28/9*x1^2*x2^6 + x2^8] \end{Verbatim} {\rm It is not hard to check that this is equivalent with part I of Theorem \ref{thrm:types}. } \end{example} \begin{example} {\rm Here is some \sage code for computing the invariants of the group $G$ generated by $g_1 = \left( \begin{array}{cc} 1/\sqrt{q} & (q-1)/\sqrt{q}\\ 1/\sqrt{q} & -1/\sqrt{q} \end{array} \right)$ with $q=2$, $g_2 = \left( \begin{array}{cc} i & 0\\ 0 & 1 \end{array} \right)$, and $g_3 = \left( \begin{array}{cc} 1 & 0\\ 0 & i \end{array} \right)$. } \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: F = CyclotomicField(8) sage: z = F.gen() sage: a = z+1/z sage: b = z^2 sage: MS = MatrixSpace(F,2,2) sage: g1 = MS([[1/a,1/a],[1/a,-1/a]]) sage: g2 = MS([[1,0],[0,b]]) sage: g3 = MS([[b,0],[0,1]]) sage: G = MatrixGroup([g1,g2,g3]) sage: G.order() 192 sage: G.invariant_generators() [x1^8 + 14*x1^4*x2^4 + x2^8, x1^24 + 10626/1025*x1^20*x2^4 + 735471/1025*x1^16*x2^8\ + 2704156/1025*x1^12*x2^12 + 735471/1025*x1^8*x2^16\ + 10626/1025*x1^4*x2^20 + x2^24] \end{Verbatim} \vskip .2in {\rm The above group $G$ which leaves invariant the weight enumerator of any self-dual doubly even binary code. The above result implies that any such weight enumerator must be a polynomial in $x^8+14x^4y^4+y^8$ and $1025x^{24}+10626x^{20}y^4+735471x^{16}y^8+2704156x^{12}y^{12}+ 735471x^8y^{16}+10626x^4y^{20}+1025y^{24}$. Using \sage's Gr\"obner bases algorithms, it is not hard to check that this is equivalent with part II of Theorem \ref{thrm:types}. The details are omitted. } \end{example} \begin{example} {\rm Here is some \sage code for computing the invariants of the group $G$ generated by $g_1 = \left( \begin{array}{cc} 1/\sqrt{q} & 1/\sqrt{q}\\ (q-1)/\sqrt{q} & -1/\sqrt{q} \end{array} \right)$ with $q=3$, $g_2 = \left( \begin{array}{cc} \omega & 0\\ 0 & 1 \end{array} \right)$, and $g_3 = \left( \begin{array}{cc} 1 & 0\\ 0 & \omega \end{array} \right)$. } \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: F = CyclotomicField(12) sage: z = F.gen() sage: a = z+1/z sage: b = z^4 sage: a^2; b^3 3 1 sage: MS = MatrixSpace(F,2,2) sage: g1 = MS([[1/a,1/a],[2/a,-1/a]]) sage: g2 = MS([[1,0],[0,b]]) sage: g3 = MS([[b,0],[0,1]]) sage: G = MatrixGroup([g1,g2,g3]) sage: G.order() 144 sage: G.invariant_generators() [x1^12 + (-55/2)*x1^9*x2^3 + 231/16*x1^6*x2^6 + (-55/128)*x1^3*x2^9 + 61/1024*x2^12, x1^12 + 4*x1^9*x2^3 + 21/8*x1^6*x2^6 + 67/64*x1^3*x2^9 + (-1/512)*x2^12] \end{Verbatim} \end{example} \begin{example} {\rm Here is some \sage code for computing the invariants of the group $G$ generated by $g_1 = \left( \begin{array}{cc} 1/\sqrt{q} & 1/\sqrt{q}\\ (q-1)/\sqrt{q} & -1/\sqrt{q} \end{array} \right)$ with $q=4$, $g_2 = \left( \begin{array}{cc} -1 & 0\\ 0 & 1 \end{array} \right)$, and $g_3 = \left( \begin{array}{cc} 1 & 0\\ 0 & -1 \end{array} \right)$. } \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: q = 4; a = 2 sage: MS = MatrixSpace(QQ, 2, 2) sage: g1 = MS([[1/a,1/a],[(q-1)/a, -1/a]]) sage: g2 = MS([[1,0],[0,-1]]) sage: g3 = MS([[-1,0],[0,1]]) sage: G = MatrixGroup([g1,g2,g3]) sage: G.order() 12 sage: G.invariant_generators() [x1^2 + 1/3*x2^2, x1^6 + 5/3*x1^4*x2^2 + 5/27*x1^2*x2^4 + 11/243*x2^6] \end{Verbatim} \vskip .2in \end{example} For the reader interested in more examples along these lines, we refer to Harada and Tagami \cite{HT}. (We shall discuss this paper more below.) \subsection{Virtual weight enumerators} \begin{definition} \label{defn:we} {\rm A homogeneous polynomial $F(x,y)=x^n+\sum_{i=1}^n f_ix^{n-i}y^i$ of degree $n$ with complex coefficients is called a {\it virtual weight enumerator} (or VWE) with {\it support} $\supp(F)=\{i\ |\ f_i\not= 0\}$. If $F(x,y)= x^n + \sum_{i=d}^n A_i x^{n-i}y^i$ with $A_d\not= 0$ then we call $n$ the {\it length} of $F$ and $d$ the {\it minimum distance} of $F$. Such an $F$ of even degree satisfying (\ref{eqn:fsd}), is called a {\it virtually self-dual weight enumerator} (or VSDWE for short) {\it over $GF(q)$} having {\it genus} \index{weight enumerator!virtually self-dual} \index{weight enumerator!length} \index{weight enumerator!genus} \index{weight enumerator!minimum distance} \[ \gamma(F) = n/2+1-d. \] If $b>1$ is an integer and $\supp(F)\subset b\zzz$ then the VWE $F$ is called {\it $b$-divisible}. } \end{definition} \index{weight enumerator!divisible} The classification of non-trivial formally self-dual divisible codes into the four Types has a VSDWE analog. In other words, the Gleason-Pierce theorem has a strengthening where the hypothesis does not require the existence of a code, only a form which certain invariance properties. \begin{theorem} (Gleason-Pierce-Assmus-Mattson) \label{thrm:GPAM} Let $F$ be a $b$-divisible VSDWE over $G(q)$. Then either \begin{itemize} \item[I.] $q=b=2$, \item[II.] $q=2$, $b=4$, \item[III.] $q=b=3$, \item[IV.] $q=4$, $b=2$, \item[V.] $q$ is arbitrary, $b=2$, and $F(x,y)=(x^2+(q-1)y^2)^{n/2}$. \end{itemize} \end{theorem} \pf The proof (or proofs - there are now two of them) is due to Assmus and Mattson. The easiest place to access the argument is in the survey paper Sloane \cite{Sl}. The rough idea is as follows (for details, please see Sloane's paper). Let $G$ denote the subgroup of $GL(2,\ccc)$ generated by the matrix of the ``MacWilliams transform'' \[ F(x,y) \longmapsto F(\frac{x+(q-1)y}{\sqrt{q}},\frac{x-y}{\sqrt{q}}) \] together with the diagonal matrices having $b$-th roots of unity on the diagonal (since $F(x,y) \longmapsto F(\zeta x,y)$ and $F(x,y) \longmapsto F(x, \zeta y)$ both fix $F$, if $\zeta\in F$ is any $b$-th roots of unity). Let $G'$ denote its image in $PGL(2,\ccc)$. Think of $F(x,y)$ as a function $f(z)$ of $z=x/y$ on $\ppp^1$. Let $m$ denotes the number of zeros of $f$ (not counting multiplicity). By the invariance properties, $m=1$ is impossible. If $m=2$ then the invariance properties implies (V). If $m>3$ then $G'$ must be finite. The classification of finite subgroups of $PGL(2,\ccc)$ results in the remaining possibilities (I), \dots , (IV). \qed Next we give the virtual weight enumerator analog of Definition \ref{defn:sdtype} above. \begin{definition} {\rm \begin{itemize} \item Let $F(x,y)$ be a VSDWE. If $b>1$ is an integer and $\supp(F)\subset b\zzz$ then $F$ is called {\it $b$-divisible}. \index{divisible!weight enumerator} \item If $F$ is a $b$-divisible VSDWE over $GF(q)$ then $F$ is called \[ \left\{ \begin{array}{ll} {\it Type\ I}, & {\rm if\ }q=b=2, \ 2|n,\\ {\it Type\ II}, & {\rm if\ }q=2,\ b=4, \ 8|n,\\ {\it Type\ III}, & {\rm if\ }q=b=3, \ 4|n,\\ {\it Type\ IV}, & {\rm if\ }q=4,\ b=2, \ 2|n. \end{array} \right. \] \index{code!Type I s.d.} \index{code!Type II s.d.} \index{code!Type III s.d.} \index{code!Type VI s.d.} \end{itemize} } \end{definition} \begin{theorem} (Sloane-Mallows-Duursma) \label{thrm:bounds3} If $F$ is a $b$-divisible VSDWE with length $n$ and minimum distance $d$ then \begin{equation} \label{eqn:divbound} d \leq \left\{ \begin{array}{ll} c[\frac{n}{c(c+1)}]+c, & {\rm if\ }F{\rm \ is\ Type\ 1},\\ c[\frac{n}{c(c+2)}]+c, & {\rm if\ }F{\rm \ is\ Type\ 2}. \end{array} \right. \end{equation} In particular, \[ d \leq \left\{ \begin{array}{ll} 2[n/8]+2, & {\rm if\ }F{\rm \ is\ Type\ I},\\ 4[n/24]+4, & {\rm if\ }F{\rm \ is\ Type\ II},\\ 3[n/12]+3, & {\rm if\ }F{\rm \ is\ Type\ III},\\ 2[n/6]+2, & {\rm if\ }F{\rm \ is\ Type\ IV}. \end{array} \right. \] \end{theorem} \pf This is only stated for self-dual codes, but proof of Theorem 1 and the argument in \S 1.1 of Duursma \cite{D3} hold more generally for VSDWEs. A complete proof is given in the appendix below. \qed A VSDWE $F$ is called {\it extremal} if the bound in Theorem \ref{thrm:bounds3} holds with equality. \index{weight enumerator!extremal formally self-dual} \begin{remark} {\rm \begin{itemize} \item Here is a more general definition. Let $G$ be a subgroup of $GL(2,\ccc)$ containing $\sigma =\frac{1}{\sqrt{q}} \left( \begin{array}{cc} 1 & q-1\\ 1 & -1 \end{array} \right)$, acting on $\ccc[x,y]$ by $\sigma : F(x,y)\longmapsto F(\sigma (x,y)^t)$, and $\chi:G\rightarrow \ccc^\times$ a character. Call a virtual weight enumerator $F$ of length $n$ a {\it formally $\chi$-self-dual weight enumerator}, or a {\it VSDWE twisted by $\chi$}, if\footnote{This ``twisted'' terminology is motivated by terminology in automorphic forms and arithmetical algebraic geometry for analogous objects.} \[ F(x,y) = \chi(\sigma)F(\frac{x+(q-1)y}{\sqrt{q}},\frac{x-y}{\sqrt{q}}). \] The VSDWE definition above is the special case when $\chi$ is a trivial. This ``twisted'' definition also covers, for example, the case of Ozeki's ``formal weight enumerators'' in \cite{O}. For brevity, we call $F$ a {\it twisted VSDWE} if it satisfies \index{weight enumerator!twisted virtually self-dual} \begin{equation} \label{eqn:afsd} F(x,y) = -F(\frac{x+(q-1)y}{\sqrt{q}},\frac{x-y}{\sqrt{q}}). \end{equation} \noindent Much of the theory of zeta functions for VSDWE's also applies to twisted VSDWE's. See Chinen \cite{C1}, \cite{C2} and \S \ref{sec:chinen} below. \item Note that a virtual weight enumerator does not depend on a prime power $q$ but a VSDWE does depend on $q$ through (\ref{eqn:fsd}). \end{itemize} } \end{remark} \vskip .2in {\rm \begin{definition} A virtual weight enumerator $F$ is formally identified with an object we call a {\it virtual code} $C$ subject only to the following condition: we formally extend the definition of $C\longmapsto A_C$ to all virtual codes by $A_C=F$. Of course, if $F$ is the weight enumerator of an actual code, $C'$ say, then we have $A_C=F=A_{C'}$. In other words, a virtual code is only well-defined up to formal equivalence. If $C_1$ and $C_2$ are virtual codes then we define $C_1+C_2$ to be the virtual code associated to the VWE $A_{C_1}(x,y)+A_{C_2}(x,y)$. \end{definition} } \vskip .2in \begin{oq} Given a VSDWE, find necessary and sufficient conditions (short of enumeration) which determine whether or not it arises as the weight enumerator of some self-dual code $C$. \end{oq} %\vskip .1in \section{The zeta polynomial} We shall give three definitions of the zeta polynomial, all due to Duursma. \subsection{First definition} \begin{definition} \label{defn:1} {\rm A polynomial $P(T)$ for which \[ \frac{(xT+(1-T)y)^n}{(1-T)(1-qT)}P(T)=\dots +\frac{A_C(x,y)-x^n}{q-1}T^{n-d}+\dots \ . \] is called a {\it Duursma zeta polynomial of $C$}. } \end{definition} %\index{Duursma zeta polynomial} \index{zeta polynomial of a code} The {\it Duursma zeta function} is defined in terms of the zeta polynomial by means of (\ref{eqn:zeta}) above. \index{Duursma zeta function} \begin{lemma} The Duursma zeta polynomial $P=P_C$ exists and is unique, provided $d^\perp\geq 2$. \end{lemma} \pf This is proven in the appendix to Chinen \cite{C2}. Here is the rough idea. If we expand $\frac{(xT+y(1-T))^n}{(1-T)(1-qT)}$ in powers of $T$, we find it is equal to \[ \begin{array}{l} b_{0,0}y^nT^0+ (b_{1,0}xy^{n-1}+b_{1,1}y^n)T^1+ (b_{2,0}x^2y^{n-2}+b_{2,1}xy^{n-1}+b_{2,2}y^n)T^2+ ...\\ \ \ \ \ \ \ \ \ \ +(b_{n-d,0}x^{n-d}y^{d}+b_{n-d,1}x^{n-d-1}y^{d+1}+...+b_{n-d,n-d}y^n)T^{n-d}+...\ . \end{array} \] The Duursma polynomial is a polynomial of degree $n+2-d-d^\perp$. Provided $d^\perp \geq 2$, we can write the Duursma polynomial as $P(T)=a_0+a_1T+...+a_{n-d}T^{n-d}$ and rewrite \[ \frac{(xT+y(1-T))^n}{(1-T)(1-qT)}P(T) =...+\frac{A_C(x,y)-x^n}{q-1}T^{n-d}+...\ \] by means of the matrix equation $B\cdot \vec{a}=\vec{A}$ given by \[ \left( \begin{array}{cccc} b_{n-d.0} & b_{n-d.1} & \dots & b_{n-d.n-d} \\ 0 & b_{n-d-1.0} & \dots & b_{n-d-1.n-d-1} \\ 0 & 0 & b_{n-d-2.0} & \dots \\ \vdots & & \ddots & \vdots \\ 0 & \dots & 0 & b_{0,0} \end{array} \right) \left( \begin{array}{c} a_{n-d}\\ a_{n-d-1}\\ \vdots \\ a_0 \end{array} \right) = \left( \begin{array}{c} A_{n}/(q-1)\\ A_{n-1}/(q-1)\\ \vdots \\ A_d/(q-1) \end{array} \right). \] The diagonal entries of this matrix are binomial coefficients, hence are non-zero. Therefore the matrix is invertible and the existence is established. \qed {\small{ \begin{example} {\rm Consider the self-dual code $C$ of length $n=6$, dimension $k=3$, and minimum distance $d=2$. This is unique up to equivalence and has weight enumerator $W(x,y) = x^6+ 3x^4y^2+3x^2y^4+y^6$. The \sage commands \vskip .2in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: q,T,x,y = var("q,T,x,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)) \end{Verbatim} \vskip .2in \noindent compute the first $6$ terms (as a power series in $T$) of the series $\frac{(xT+y(1-T))^n}{(1-T)(1-qT)}P(T)$ when $q=2$, $n=6$, $k=3$, and $d=2$. Next, we compute the coefficients and read off the matrix $B$: \vskip .2in \begin{Verbatim}[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] \end{Verbatim} \vskip .2in \noindent Note that the diagonal entries are binomial coefficients. Finally, we computes the vector $\vec{A}$, and solve the equation $B\cdot \vec{a}=\vec{A}$: \vskip .2in \begin{Verbatim}[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] \end{Verbatim} \vskip .2in \noindent This implies that the zeta function of $C$ is given by $P(T) = \frac{1}{5}+{4}{5}T^4$. } \end{example} }} Duursma has given several definitions (all equivalent of course) of $P(T)$. Before stating another one, we need the following definition and lemma. \begin{definition} \label{defn:mds} {\rm Define $c_j$ by \[ \frac{(xT+(1-T)y)^n}{(1-T)(1-qT)} = \sum_{k=0}^\infty c_k(x,y)T^k . \] Define $M_{n,\delta}$ by \[ M_{n,\delta}(x,y) = x^n +(q-1)c_{n-\delta}(x,y). \] This is called the {\it MDS virtual weight enumerator of length $n$ and distance $\delta$}. } \end{definition} \index{weight enumerator!virtual MDS} It is not hard to see that \[ \frac{1}{(1-T)(1-qT)} = \sum_{j=0}^\infty \frac{q^{j+1}-1}{q-1}T^j , \] and of course \[ (xT+(1-T)y)^n = \sum_{i=0}^n \left( \begin{matrix} n\\ i \end{matrix} \right) y^{n-i}(x-y)^{i}T^i . \] Therefore, \[ c_k(x,y)=\sum_{i+j=k} \frac{q^{j+1}-1}{q-1}\left( \begin{matrix} n\\ i \end{matrix} \right) y^{n-i}(x-y)^{i}. \] \begin{example} We use \SAGE \cite{S} to compute examples. When $q=2$, \[ M_{10,5}(x,y)= -34y^{10} + 220xy^9 - 585x^2y^8 + 840x^3y^7 - 630x^4y^6 + 252x^5y^5 + x^{10} \] and when $q=3$, \[ \begin{array}{ll} M_{12,5}(x,y) =& -48y^{12} + 1152xy^{11} - 2376x^2y^{10} + 8360x^3y^9 - 7920x^4y^8 +\\ & + 9504x^5y^7 - 3696x^6y^6 + 1584x^7y^5 + x^{12}. \end{array} \] The negative coefficients in these polynomials are consistent with the fact that for codes of dimension greater than $1$, the length of an MDS code satisfies the bound $n\leq q+k-1$ (see for example, pages 12-13 in \cite{TV}). In the first example, a $[10,6,5]_2$ code must satisfy $10\leq 2+6-1$ (so it doesn't exist) and, in the second example, a $[12,8,5]_3$ code must satisfy $12\leq 3+8-1$ (so it doesn't exist). On the other hand, when $q=13$, \[ \begin{array}{ll} M_{12,5}(x,y)&= 312177312y^{12} + 312178752xy^{11} + 143076384x^2y^{10} +\\ & + 39755760x^3y^9 + 7436880x^4y^8 + 1007424x^5y^7 + \\ & +88704x^6y^6 + 9504x^7y^5 + x^{12}. \end{array} \] Indeed, according to \sage's {\tt ReedSolomonCode} command, there is an MDS code $C$ having parameters $[12,8,5]_{13}$: \vskip .2in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = ReedSolomonCode(12,8,GF(13)) sage: C.spectrum() [1, 0, 0, 0, 0, 9504, 88704, 1007424, 7436880, 39755760, 143076384, 312178752, 312177312] \end{Verbatim} \vskip .2in \noindent This \sage session tells us that \[ \begin{array}{ll} spec(C) = & [ 1, 0, 0, 0, 0, 9504, 88704, 1007424, 7436880,\\ & 39755760, 143076384, 312178752, 312177312 ], \end{array} \] as the above (independently obtained) computation implies. These virtual weight enumerators are computed using the following \SAGE code \vskip .2in \begin{Verbatim}[fontsize=\small,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: R = PolynomialRing(QQ,2,"xy") sage: x,y = R.gens() sage: f = lambda q,n,m :\ (x*T+y*(1-T))^(n)*sum([T^i for i in range(m)])\ *sum([(q*T)^i for i in range(m)]) sage: M = lambda q,n,d,m : (f(q,n,m).list())[d]*(q-1)+x^n \end{Verbatim} \vskip .1in \noindent As long as {\tt m} is taken to be sufficiently large, this code will return the correct value of $M_{n,d}$. \end{example} A version of the following result is stated in Duursma's \cite{D5} (see his equation (9)). \begin{lemma} \label{lemma:mds} If $F$ is a virtual weight enumerator of length $n$ and minimum distance $d$ then there are coefficients $c\in \qqq$ and $a_i=a_j(F)\in \qqq$ such that \begin{equation} \label{eqn:*} F(x,y) = cx^n+a_0M_{n,d}(x,y)+a_{1}M_{n,d+1}(x,y)+\dots +a_{r}M_{n,d+r}(x,y), \end{equation} for some $r$, $0\leq r\leq n-d$. In fact, $c=1-a_0-\dots -a_r$. \end{lemma} \pf The functions $M_{n,d+i}(x,y)-x^n$ form a basis for the vector space $V=\{\sum_{i=d}^n b_ix^{n-i}y^i\ |\ b_i\in \qqq\}$. Consider the equation \[ F(x,y)-x^n = a_0(M_{n,d}(x,y)-x^n)+a_{1}(M_{n,d+1}(x,y)-x^n)+\dots + a_{r}(M_{n,d+r}(x,y)-x^n). \] If $r={\rm dim}(V)-1$ then one can solve for the $a_0,\dots ,a_r$. Without loss of generality, we may take $r\geq 0$ to be as small as possible. We have then \[ F(x,y) = (1-a_0-\dots -a_r)x^n+a_0M_{n,d}(x,y)+a_1M_{n,d+1}(x,y)+\dots +a_rM_{n,d+r}(x,y). \] \qed \begin{example} {\rm Duursma zeta function of the $[2^r-1,2^r-r-1,3]$-Hamming code, $Ham(r,GF(2))$, can be computed using the following \SAGE commands: \vskip .2in \begin{Verbatim}[fontsize=\small,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = HammingCode(3,GF(2)) sage: C.zeta_function() (2/5*T^2 + 2/5*T + 1/5)/(2*T^2 - 3*T + 1) sage: C = HammingCode(4,GF(2)) sage: C.zeta_function() (16/429*T^6 + 16/143*T^5 + 80/429*T^4 + 32/143*T^3\ + 30/143*T^2 + 2/13*T + 1/13)/(2*T^2 - 3*T + 1) \end{Verbatim} \vskip .1in \noindent In other words, \[ Z_{Ham(3,GF(2))}(T)= \frac{\frac{1}{5}(2T^2 + 2T + 1)}{2T^2 - 3T + 1}, \] and \[ Z_{Ham(4,GF(2))}(T)= \frac{\frac{1}{429}(16T^6 + 48T^5 + 80T^4 + 96T^3 +90T^2 + 66T + 33)}{2T^2 - 3T + 1}. \] } \end{example} \begin{example} {\rm Duursma zeta function of the maximal binary linear self-dual doubly even code of length $8$ can be computed using the following different \SAGE commands: \vskip .2in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: MS = MatrixSpace(GF(2),4,8) sage: G = MS([[1,1,1,1,0,0,0,0],[0,0,1,1,1,1,0,0],[0,0,0,0,1,1,1,1],[1,0,1,0,1,0,1,0]]) sage: C = LinearCode(G) sage: C Linear code of length 8, dimension 4 over Finite Field of size 2 sage: C.zeta_function() (2/5*T^2 + 2/5*T + 1/5)/(2*T^2 - 3*T + 1) sage: C.sd_zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: C == C.dual_code() True \end{Verbatim} \vskip .1in \noindent In other words, \[ P_{C}(T)= (2T^2+2T+1)/5. \] } \end{example} \subsection{Second definition} Here is Duursma's second definition of the zeta polynomial. \begin{definition} \label{defn:2} {\rm Let $F=A_C$ denote the weight enumerator of a $[n,k,d]_q$-code $C$. %Assuming the coefficients $a_j=a_j(F)$ of (\ref{eqn:*}) %satisfy $a_0+\dots +a_r=1$, define Using the coefficients $a_j=a_j(F)$ of (\ref{eqn:*}), define \[ P(T)=P_C(T)=a_0+a_1T+\dots +a_rT^r. \] This $P(T)$ is the {\it Duursma zeta polynomial of $C$}. More generally, if $F$ is an virtual weight enumerator and the coefficients $a_j=a_j(F)$ are as in (\ref{eqn:*}), define $P(T)=P_F(T)=a_0+a_1T+\dots +a_rT^r$. } \end{definition} \index{zeta polynomial of a code} Note that by comparing coefficients of $x^n$ on both sides of (\ref{eqn:*}), we see $a_0+\dots +a_r=1$ is equivalent to $P(1)=1$. \begin{example} \label{example:mds} Note that if $C$ is a MDS code of length $n$ and minimum distance $d$ over $GF(q)$ then $A_C = M_{n,d}$ (this is proven as part of the discussion in \S 2 of Duursma \cite{D2}). This forces $c=0$, $a_0=1$ in (\ref{eqn:*}), so\footnote{See also Duursma's Proposition 1 in \cite{D5} and Chinen's Theorem 3.2 in \cite{C3}.} $P(t) = 1$. \end{example} \begin{remark} {\rm Note $[n,k,d]$ makes sense as parameters of a virtual weight enumerator is when $F$ is a WE of an actual code $C$ (so $F=A_C$) or when $F$ is a VSDWE (so $\gamma=n/2-d+1$, where $n$ and $d$ are as in Definition \ref{defn:we}) or a (virtual) MDS code (so $k=n+1-d$). } \end{remark} \begin{lemma} The Duursma zeta function of Definition \ref{defn:1} is the same as the Duursma zeta function of Definition \ref{defn:2}. \end{lemma} \pf By Definition \ref{defn:mds}, the zeta polynomial of Definition \ref{defn:1} associated to $F=A_C$ is $T^r$ if you replace $F=A_C$ by $F=M_{n,d+j}$: \[ \frac{(xT+(1-T)y)^n}{(1-T)(1-qT)}T^j =\dots +\frac{M_{n,d+j}(x,y)-x^n}{q-1}T^{n-d}+\dots \ . \] Multiply by $a_j$ and sum both sides over $j\in \{0,\dots ,r\}$ to obtain Definition \ref{defn:2}. Therefore, $P(T)$ satisfying Definition \ref{defn:1} also satisfies Definition \ref{defn:2}. \qed \vskip .1in \subsection{Third definition} \label{sec:3rd-defn} In preparation for the third definition, which originated in \S 7 of Duursma \cite{D1}, we introduce some notation. Let $C$ be an $[n,k,d]_q$ code, let $S\subset \{1,2,\dots ,n\}$ be a subset, let $C_S$ denote the subcode of $C$ of codewords with support contained in $S$, and let $k_S=k_S(C)$ denote the dimension of $C_S$. \begin{lemma} The dimension $k_S$ satisfies \[ k_S= \left\{ \begin{array}{ll} \ \ \ \ \ 0, & {\rm for}\ 0\leq |S|n^2$, $2\leq d$ and $d+d^\perp< n+2$. If $n>3$ then the Duursma zeta polynomial is not a constant and does not satisfy the RH. \end{corollary} This is an easy consequence of the Proposition \ref{prop:roots} (assume the RH is true and $q>n^2$, then show the hypothesis contradicts the trivial estimate $q-d\leq \big{|}\sum_{i} \rho_i^{-1} \big{|}\leq r\sqrt{q} =(n+2-d-d^\perp)\sqrt{q}$) and the proof is left to the reader. \begin{example} It is clear from Example \ref{example:mds} above that the Duursma zeta function may have no zeros (i.e., may be constant). Indeed, this is true for all MDS codes, including some formally self-dual ones\footnote{Formally self-dual MDS codes exist - see Example 12 in \cite{JKT}, which gives a fsd $[42,21,22]$-code over a very large extension of $GF(7)$. (In fact, this code even has $A_5$ as its permutation automorphism group.) Even better, in Kim and Lee \cite{KL}, a self-dual MDS code with parameters $[10,5,6]_{41}$ is constructed.}. \end{example} \begin{remark} Let $F$ denote a VSDWE as in Proposition \ref{prop:fcnaleqn} and let $r(T)=z_F(T/\sqrt{q})$. The functional equation implies $r(T)$ is a self-reciprocal function: $r(1/T)=r(T)$. The RH is the statement that all $2\gamma$ zeros of $r(T)$ lie on the ``critical line'' $|T|=1$. If $r_0(\theta)=r(e^{i\theta})$ then the functional equation, and the fact that $r$ has rational coefficients, implies \[ r_0(\theta)=r_0(-\theta)=\overline{r_0(\theta)}. \] In other words, $r_0(\theta)$ is real-valued. \end{remark} \begin{conjecture} (Duursma) For all extremal virtual weight enumerators $F$, the zeta function $Z=Z_F$ satisfies the Riemann hypothesis. \end{conjecture} \begin{lemma} Let $F$ denote a VSDWE of genus $\gamma$ as above and let $P=P_F$ denote the associated zeta polynomial. It is known that $P(T^2/q)=T^{2\gamma}f(T+T^{-1})$, where $f\in \rrr[x]$ is a polynomial of degree $2\gamma$ with real coefficiates. \end{lemma} \pf See Duursma \cite{D3}, Theorem 7 and Lemma 10. \qed \begin{remark} {\rm Lemma 2.1.1 in \cite{DH} classifies those polynomials of even degree in $\rrr[x]$ which have all its roots on the unit circle. That result allows us to reformulate the RH (a statement about the complex roots of $P$) as a statement about the real roots of $f(x)$ in $-2\leq x\leq 2$. } \end{remark} \section{Examples} \subsection{Komichi's example} In \cite{HT}, the authors mention an example which occured in the master's thesis\footnote{This appears to be unpublished and I have not seen it myself.} of A. Komichi. It is claimed that the Duursma zeta function of the code $C = H_8\oplus H_8\oplus H_8$, where $H_8$ is the self-dual extended Hamming $[8,4,4]$-code, violates the Riemann hypothesis. We verify this using \sage. \vskip .2in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: MS = MatrixSpace(GF(2), 12, 24) sage: G = MS([\ ....: [ 1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ],\ ....: [ 0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ],\ ....: [ 0,0,1,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ],\ ....: [ 0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ],\ ....: [ 0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0 ],\ ....: [ 0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0 ],\ ....: [ 0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0,0,0,0,0,0 ],\ ....: [ 0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0 ],\ ....: [ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1 ],\ ....: [ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0 ],\ ....: [ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1 ],\ ....: [ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0 ]\ ....: ]) sage: C = LinearCode(G) sage: Cd = C.dual_code(); C == Cd True sage: R = PolynomialRing(CC,"T") sage: T = R.gen() sage: C.zeta_polynomial() 512/253*T^18 + 512/253*T^17 + 256/253*T^16 - 148736/245157*T^14 - 66048/81719*T^13 - 185536/245157*T^12 - 49408/81719*T^11 - 43088/96577*T^10 - 1808/5681*T^9 - 21544/96577*T^8 - 12352/81719*T^7 - 23192/245157*T^6 - 4128/81719*T^5 - 4648/245157*T^4 + 2/253*T^2 + 2/253*T + 1/253 sage: f = R(C.zeta_polynomial()) sage: print [z[0].abs() for z in f.roots()] [0.963950810639179, 0.707106781186546, 0.707106781186548, 0.707106781186546, 0.518698666447988, 0.707106781186548, 0.707106781186542, 0.707106781186548, 0.707106781186550, 0.707106781186551, 0.707106781186547, 0.707106781186546, 0.707106781186548, 0.707106781186544, 0.707106781186548, 0.707106781186549, 0.707106781186548, 0.707106781186549] sage: P1 = list_plot([(z[0].real(),z[0].imag()) for z in f.roots()]) sage: t = var("t") sage: pts = lambda t: [cos(t)/sqrt(2),sin(t)/sqrt(2)] sage: P2 = parametric_plot(pts(t),0,2*pi,linestyle="--",rgbcolor=(1,0,0)) sage: show(P1+P2) \end{Verbatim} \vskip .1in \noindent The plot computed in the last line is shown below: %\newpage \begin{figure}[h!] \begin{minipage}{\textwidth} \begin{center} \includegraphics[height=7cm,width=7cm]{chinen-24-12-4-sd-noRH.eps} \end{center} \end{minipage} \caption{Roots of the zeta polynomial for a self-dual $[24,12,4]$ binary code.} \label{fig:chinen-24-12-4-sd-noRH} \end{figure} \subsection{The extremal case} \label{sec:extremal} We shall summaries the some results of Duursma \cite{D3} and Harada and Tagami \cite{HT} in this section. If $F$ is an extremal VSDWE then the zeta function $Z=Z_F$ can be explicitly computed. First, some notation. If $F$ is a VSDWE of minimum distance $d$ and $P=P_F$ is its zeta polynomial then define \[ Q(T) = \left\{ \begin{array}{ll} P(T),& {\rm Type \ I},\\ P(T)(1-2T+2T^2),& {\rm Type \ II},\\ P(T)(1+3T^2),& {\rm Type \ III},\\ P(T)(1+2T),& {\rm Type \ IV}. \end{array} \right. \] Let $(a)_m = a(a+1)\dots (a+m-1)$ denote the {\it rising generalized factorial} \index{rising generalized factorial} and write $Q(T)=\sum_j q_jT^j$, for some $q_j\in \qqq$. Let \[ \gamma_1(n,d,b) = (n-d)(d-b)_{b+1}A_d/(n-b-1)_{b+2}, \] and \[ \gamma_2(n,d,b,q) = (d-b)_{b+1}\frac{A_d}{(q-1)(n-b)_{b+1}}, \] where recall $A_d$ denoted the coefficient of $x^{n-d}y^d$ in the virtual weight enumerator $F(x,y)$. \begin{theorem} \label{thrm:extremal} (Duursma \cite{D3}) If $F$ is an extremal VSDWE then the coefficients of $Q(T)$ are determined as follows. \begin{itemize} \item[(a)] If $F$ is Type I then \[ \sum_{i=0}^{2m+2\nu} \left( \begin{array}{c} 4m+2\nu \\ m+i \end{array} \right) q_iT^i = \gamma_1(n,d,2)\cdot (1+T)^m(1+2T)^m(1+2T+2T^2)^\nu, \] where $m=d-3$, $4m+2\nu = n-4$, $b=q=2$, $0\leq \nu \leq 3$. \item[(b)] If $F$ is Type II then \[ \sum_{i=0}^{4m+8\nu} \left( \begin{array}{c} 6m+8\nu \\ m+i \end{array} \right) q_iT^i = \gamma_1(n,d,2)\cdot (1+T)^m(1+2T)^m(1+2T+2T^2)^m B(T)^\nu, \] where $m=d-5$, $6m+8\nu = n-6$, $b=4$, $q=2$, $0\leq \nu \leq 2$, and $B(T)=W_5(1+T,T)$, where $W_5$ is as in Example \ref{example:WEs}. \item[(c)] If $F$ is Type III then \[ \sum_{i=0}^{2m+4\nu} \left( \begin{array}{c} 4m+4\nu \\ m+i \end{array} \right) q_iT^i = \gamma_2(n,d,3,3)\cdot (1+3T+3T^2)^m B(T)^\nu, \] where $m=d-4$, $4m+4\nu = n-4$, $b=q=3$, $0\leq \nu \leq 2$, and $B(T)=W_9(1+T,T)$, where $W_9$ is as in Example \ref{example:WEs}. \item[(d)] If $F$ is Type VI then \[ \sum_{i=0}^{m+2\nu} \left( \begin{array}{c} 3m+2\nu \\ m+i \end{array} \right) q_iT^i = \gamma_2(n,d,2,4)\cdot (1+2T)^m(1+2T+4T^2)^\nu, \] where $m=d-3$, $3m+2\nu = n-3$, $b=2$, $q=4$, and $0\leq \nu \leq 2$. \end{itemize} \end{theorem} It is easy to determine (especially with a computer algebra system such as \sage) the coefficients $q_j$ and $p_j$ from these expressions. Define the {\bf ultraspherical polynomial} $C_n^m(x)$ on the interval $(-1,1)$ by \[ C_n^m(\cos \theta)= \sum_{\begin{array}{c} 0\leq k, \ell \leq n\\ k+\ell=n \end{array} } \big(\begin{array}{c} m+k\\ k \end{array} \big) \big(\begin{array}{c} m+\ell\\ \ell \end{array} \big) \cos(k-\ell)\theta. \] \begin{theorem} (Duursma \cite{D3}, section 5.2\footnote{A typo in \cite{D3}, \S 5.2, is corrected here.}) is due to If $P$ is the Duursma zeta polynomial of an extremal Type IV virtual self-dual weight enumerator of length $n=3m+3$ and minimum distance $d=m+3$ then \[ Q(T^2/2)=\frac{m!^2}{(3m)!}T^mC_m^{m+1}(\frac{T+T^{-1}}{2}). \] (Recall that, in this case, $Q(T)=P(T)(1+2T)$.) \end{theorem} It's known that all the roots of ultraspherical polynomials $C_n^m$ lie on the interval $(-1,1)$. The polynomial $C_n^m$ is degree $n$ and so there are $n$ such roots. Replace $T$ by $e^{i\theta}$ in the equation displayed in the Theorem above to obtain \[ Q(e^{2i\theta}/2)=\frac{m!^2}{(3m)!}e^{i\theta m}C_m^{m+1}(\cos\theta). \] Hence, all the roots of $Q$, therefore also $P$, lie on the circle of radius $1/\sqrt{q}=1/2$. Indeed, the RH holds for all zeta functions associated to an extremal Type IV VSDWE (Duursma \cite{D3}). Using computer computations, Harada and Tagami \cite{HT} (among other things) that RH holds for all zeta functions associated to extremal Type I, II, III VSDWEs of degree $\leq 200$. \subsection{``Random divisible codes''} Following Theorem 4 in Duursma \cite{D5}, we show that the Duursma zeta function of a ``random divisible code'' satisfies the RH. Define the {\it (virtual) weight enumerator of the $[n,k]_q$ random $b$-divisible code} by \[ F(x,y) = x^n + c\sum_{i=1}^{n/b} \left( \begin{array}{c} n\\ bi \end{array} \right) (q-1)^{bi}x^{n-bi}y^{bi}, \] where $c$ is choosen so that $F(1,1)=q^k$ and $n$ is a multiple of $b$. \index{code!random divisible} Of course, by the classification of $b$-divisible codes (see Theorem \ref{thrm:GPAM}), this weight enumerator may not correspond to an actual linear code. Duursma shows that in the following cases the zeta function $Z_F(T)$ satisfies the RH: $n$ is even, $k=n/2$ and \begin{itemize} \item $q=2$, $b=4$, \item $q=3$, $b=3$, \item $q=4$, $b=2$. \end{itemize} For details, see Duursma \cite{D5}, Theorem 4. \subsection{A fsd $[26,13,6]_2$-code} Moreover, in this case the Riemann hypothesis is not valid for optimal codes (which may or may not be extremal) in general, as the following example illustrates. \begin{example} Consider the $[26,13,6]_{2}$ code with weight distribution \[ [1, 0, 0, 0, 0, 0, 39, 0, 455, 0, 1196, 0, 2405, 0, 2405, 0, 1196, 0, 455, 0, 39, 0, 0, 0, 0, 0, 1]. \] This is (by coding theory tables, as included in \sage \cite{S}) an optimal formally self-dual code. This code $C$ has zeta polynomial %{\small{ \begin{align*} P(T)&= \frac{3}{17710} + \frac{6}{8855}T + \frac{611}{336490}T^2 + \frac{9}{2185}T^3 + \frac{3441}{408595}T^4 + \frac{6448}{408595}T^5 + \frac{44499}{1634380}T^6 \\ &+ \frac{22539}{520030}T^7 + \frac{66303}{1040060}T^8 + \frac{22539}{260015}T^9 + \frac{44499}{408595}T^{10} + \frac{51584}{408595}T^{11} \\ & +\frac{55056}{408595}T^{12} + \frac{288}{2185}T^{13} + \frac{19552}{168245}T^{14} + \frac{768}{8855}T^{15} + \frac{384}{8855}T^{16}. \end{align*} %}} Using \sage, it can be checked that only 8 of the 12 zeros of this function have absolute value $\sqrt{2}$. \end{example} \subsection{Extremal codes of short length} In this section, we give some examples using \sage. These do not satisfy $P(1)=1$ but use the formulas in Theorem \ref{thrm:extremal} above: For the $[24, 12, 8]_2$ VSDWE: \[ \begin{array}{ll} P(T) = & \frac{2}{969}T^{10} + \frac{2}{323}T^9 + \frac{10}{969}T^8 + \frac{4}{323}T^7 + \frac{197}{16796}T^6 + \\ &+\frac{9}{988}T^5 + \frac{197}{33592}T^4 + \frac{1}{323}T^3 + \frac{5}{3876}T^2 + \frac{1}{2584}T + \frac{1}{15504}. \end{array} \] For the $[26, 13, 8]_2$ VSDWE: \begin{eqnarray*} P(T) =& \frac{32}{13167}T^{12} + \frac{32}{4389}T^{11} + \frac{4}{323}T^{10} + \frac{496}{31977}T^9 + \\ &+\frac{393}{24871}T^8 + \frac{31}{2261}T^7 + \frac{281}{27132}T^6 + \frac{31}{4522}T^5 + \\ &+\frac{393}{99484}T^4 + \frac{62}{31977}T^3 + \frac{1}{1292}T^2 + \frac{1}{4389}T + \frac{1}{26334} \end{eqnarray*} For the $[28, 14, 8]_2$ VSDWE: \[ \begin{array}{ll} P(T)=& \frac{16}{5313}T^{14} + \frac{16}{1771}T^{13} + \frac{224}{14421}T^{12} + \frac{96}{4807}T^{11} + \\ &+\frac{3469}{163438}T^{10} + \frac{291}{14858}T^9 + \frac{23}{1428}T^8 + \frac{622}{52003}T^7 + \\ &+\frac{23}{2856}T^6 + \frac{291}{59432}T^5 + \frac{3469}{1307504}T^4 + \frac{6}{4807}T^3 + \\ &+\frac{7}{14421}T^2 + \frac{1}{7084}T + \frac{1}{42504} \end{array} \] %\sage code for this can be found at \cite{J}. \subsection{Non-self-dual examples} Consider the optimal binary code $C$ having parameters $[6,2,4]$ and generator matrix \[ G = \left( \begin{array}{rrrrrr} 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \end{array} \right) . \] This has zeta polynomial $P(T) = (2T^2 + 2T + 1)/5$, as the following \sage computation shows. \vskip .2in \begin{Verbatim}[fontsize=\footnotesize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: R_CC = PolynomialRing(CC,"T") sage: n = 6; k = 2; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: [abs(z[0]) for z in R_CC(C.zeta_polynomial()).roots()] [0.707106781186548, 0.707106781186548] sage: C.weight_enumerator() x^6 + 3*x^2*y^4 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: Cd.weight_enumerator() x^6 + 3*x^4*y^2 + 8*x^3*y^3 + 3*x^2*y^4 + y^6 sage: n = 7; k = 4; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: C.weight_enumerator() x^7 + 7*x^4*y^3 + 7*x^3*y^4 + y^7 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: Cd.weight_enumerator() x^7 + 7*x^3*y^4 sage: n = 8; k = 4; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: C.weight_enumerator() x^8 + 14*x^4*y^4 + y^8 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: Cd.weight_enumerator() x^8 + 14*x^4*y^4 + y^8 \end{Verbatim} Indeed, the optimal $[6,2,4]$ code has the same zeta polynomial as the Hamming $[7,4,3]$ code. This satisfies the RH even though it is not even formally self-dual. However, it does have the same zeta polynomial as the optimal self-dual $[8,4,4]$ code. \section{Chinen zeta functions} \label{sec:chinen} \index{Chinen zeta functions} In the sections above, a virtual weight enumerator $F$ is associated with a zeta function $Z=Z_F$. In this section, two related zeta functions were constructed by Koji Chinen. First, he constructed a zeta function $Z=Z_F$, which we call a ``twisted Chinen zeta function'', associated to a twisted VSDWE $F$. (What we call a ``twisted VSDWE'' he calls a ``formal weight enumerator''.) Next, he constructed a zeta function associated to any code $C$, which we call a ``Chinen zeta function'', which is essentially defined by combining the Duursma zeta function of $C$ with that of its dual $C^\perp$ (some care is required to insure that the functional equation leads to an extra symmetry property). Here are the analogous result for Chinen zeta functions of the results above. Let $C$ be any $[n,k,d]$ code over $GF(q)$ and let $[n,n-k,d^\perp]$ denote the parameters of the dual code $C^\perp$. We assume they satisfy $d\geq 2$ and $d^\perp \geq 2$. Define the {\it invariant weight enumerator} by \index{weight enumerator!invariant} \[ \tilde{A}_C(x,y)= \frac{A_C(x,y)+q^{k-n/2}A_{C^\perp}(x,y)}{1+q^{k-n/2}}. \] Note that $\tilde{A}_C=\tilde{A}_{C^\perp}=\tilde{A}_C\circ \sigma_q$, by the MacWilliams identity. The {\it Chinen zeta polynomial} $\tilde{P}_C$ is the zeta polynomial $P_F$ associated to the virtual weight enumerator $F=\tilde{A}_C$. \index{Chinen zeta polynomial} The {\it Chinen zeta function} is defined in terms of the zeta polynomial by means of the following equation. \begin{equation} \label{eqn:czeta} \tilde{P}_C(T) = \frac{T^{\max(0,d-d^\perp)}}{1+q^{k-n/2}}\left( P_C(T)+ q^{n/2-d+1}T^{n-2d+2}P_C(1/qT) \right). \end{equation} \begin{theorem} \label{thrm:chinen} (K. Chinen \cite{C3}) The Chinen zeta polynomial given by (\ref{eqn:czeta}) above has degree $2\tilde{g}=n+2-2\min(d,d^\perp)$ and satisfies the functional equation \[ \tilde{P}_C(T)=q^{\tilde{g}}T^{2\tilde{g}}\tilde{P}_C(1/qT). \] \end{theorem} By the functional equation, if $d>d^\perp$ then $\tilde{P}_C(T) =\frac{q^{k-n/2}P_{C^\perp}(T)+ T^{d-d^\perp}P_C(T)}{1+q^{k-n/2}}$; if $d2"%m M = int(m/2) A = [[0]*2*i+[1]*4+[0]*(m-4-2*i) for i in range(M-1)] MS = MatrixSpace(GF(2), M-1, m) return MS(A) \end{Verbatim} \noindent For example, \[ D_{14} = \left( \begin{array}{rrrrrrrrrrrrrr} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array} \right) \] and the binary code generated by this matrix is a $[14,6,4]$ code. You can see it's Chinen zeta function does not satisfy the RH: \vskip .2in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: n = 14; G = d_matrix(n); C = LinearCode(G); C Linear code of length 14, dimension 6 over Finite Field of size 2 sage: C.spectrum() [1, 0, 0, 0, 21, 0, 0, 0, 35, 0, 0, 0, 7, 0, 0] sage: PT = PolynomialRing(CC,"T") sage: PC = C.chinen_polynomial(); rts = PT(PC).roots() sage: PC 64/39*t^12 - 32/429*t^10 - 32/429*t^9 - 160/1287*t^8 - 64/429*t^7 - 160/1287*t^6 - 32/429*t^5 - 40/1287*t^4 - 4/429*t^3 - 2/429*t^2 + 1/39 sage: [z[0].abs() for z in rts] [0.707106781186548, 0.707106781186548, 0.707106781186548, 0.707106781186547, 0.707106781186548, 0.707106781186548, 0.707106781186549, 0.707106781186548, 0.707106781186547, 0.707106781186548, 0.814795710093010, 0.613650751723920] \end{Verbatim} \noindent In particular, the RH for the Chinen zeta function is not true for all indecomposible codes. } \end{example} \subsection{Hamming codes} Chinen \cite{C3} computed the zeta polynomial of the Hamming codes. Consider the Hamming code $C=C_{r,q}$ having parameters $[n=\frac{q^r-1}{q-1}, n-r,3]$ over $GF(q)$, with $r\geq 3$. (When $r=2$ the Hamming code is MDS and so has already been computed.) The Duursma zeta polynomial of the dual code is given by \[ P_{C^\perp}(T)= c\cdot [1+\sum_{j=1}^{n-d-1} ( \left( \begin{array}{c} j+d-1\\ d-1 \end{array} \right) -q\left( \begin{array}{c} j+d-2\\ d-1 \end{array} \right) )T^j], \] where the constant $c=c_{r,q}$ is chosen so that $P(1)=1$. This is Proposition 4.4 in \cite{C3}. The Chinen zeta polynomial of the Hamming codes $C_{r,q}$ ($r\geq 3$, $q\geq 2$) is given by \begin{equation} \label{eqn:chinen} \tilde{P}_C(T) = \frac{c}{1+q^{r-n/2}}(F_1(T)-qF_2(T)), \end{equation} where \[ F_1(T) = \sum_{j=0}^{n-d-1} \left( \begin{array}{c} n-i-2\\ d-1 \end{array} \right) q^{i+2-n/2}T^i + \sum_{j=d-3}^{n-4} \left( \begin{array}{c} i+2\\ d-1 \end{array} \right) T^i, \] and \[ F_2(T) = \sum_{j=0}^{n-d-2} \left( \begin{array}{c} n-i-3\\ d-1 \end{array} \right) q^{i+2-n/2}T^i + \sum_{j=d-2}^{n-4} \left( \begin{array}{c} i+1\\ d-1 \end{array} \right) T^i. \] This is Theorem 4.5 in \cite{C3}. \begin{example} {\rm Here is the Chinen zeta polynomial of the Hamming $[7,4,3]$ code: \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = HammingCode(3,GF(2)) sage: C.chinin_polynomial() (2*T^2/5 + 2*sqrt(2)*T*(T^2/5 + T/5 + 1/10) + 2*T/5 + 1/5)/(sqrt(2) + 1) \end{Verbatim} } \end{example} \begin{theorem} (Chinen) \label{thrm:RHhamming} The Chinen zeta polynomial of the Hamming codes $C_{r,q}$ ($r\geq 3$, $q\geq 4$) satisfies the RH. \end{theorem} This theorem is also true when $r=2$ ($q \geq 2$), as a corollary to equation (3.3) in \cite{C3}, since then $C$ is MDS. Chinen's proof of this theorem is too beautiful to omit at least a brief sketch. We need the following remarkable result. \begin{lemma} (Chinen) If $f(T)$ is a degree $m$ polynomial of ``decreasing symmetric form'' \[ f(T) = a_0 + a_1T + \dots + a_kT^k + a_kT^{m-k} + a_{k-1}T^{m-k-1}+\dots + a_0T^m, \] with $a_0>a_1>\dots >a_k>0$ then all roots of $f(T)$ lie on the unit circle $|T|=1$. \end{lemma} To prove Theorem \ref{thrm:RHhamming}, Chinen explicitly computes the coefficients $a_i$ of a normalized Chinen zeta polynomial $f$ of $C=C_{r,q}$ and proves that it has the above decreasing symmetric form. This implies the RH, as desired, The proof of the above lemma and the explicit computation of the coefficients are carefully worked out in \cite{C3}, which we refer to for details. \subsection{Golay codes} This section summarizes some of the results in Chinen \cite{C3}, \S 7. The Chinen zeta polynomial of the $[11,6,5]$ Golay code $C$ over $GF(3)$ is \[ \tilde{P}_C(T)= \frac{\sqrt{3}-1}{14}(\sqrt{3}T+1)(3T^2+3T+1). \] Chinen also presents an explicit expression but complicated expression for the Chinen zeta polynomial of the $[23,12,7]$ Golay code $C$ over $GF(2)$. He also shows that both of these Chinen zeta functions satisfy the ``Riemann hypothesis''. The proof is by explicitly computing zeros, verifying the RH numerically. \subsection{Examples} We begin with a random example: \vskip .2in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: RT = PolynomialRing(CC,"T") sage: MS = MatrixSpace(GF(2), 3, 8) sage: G = MS([[1,0,0,1,0,1,1,0],[0,1,0,1,0,0,0,1],[0,0,1,0,1,1,1,0]]) sage: C = LinearCode(G) sage: C.minimum_distance() 3 sage: Cd = C.dual_code(); Cd.minimum_distance() 2 sage: f = RT(C.chinen_polynomial()) sage: print [z[0].abs() for z in f.roots()] [0.707106781186548, 0.707106781186548, 0.707106781186548, 0.707106781186548, 0.707106781186547, 0.707106781186547] sage: C.gen_mat() [1 0 0 1 0 1 1 0] [0 1 0 1 0 0 0 1] [0 0 1 0 1 1 1 0] sage: C.spectrum() [1, 0, 0, 1, 3, 2, 0, 1, 0] sage: Cd.spectrum() [1, 0, 3, 10, 7, 4, 5, 2, 0] sage: C.chinen_polynomial() 2/7*t^6 + 4/21*t^5 + 13/70*t^4 + 17/105*t^3 + 13/140*t^2 + 1/21*t + 1/28 sage: C.zeta_polynomial() 3/7*T^5 + 3/14*T^4 + 11/70*T^3 + 17/140*T^2 + 17/280*T + 1/56 sage: f = RT(C.zeta_polynomial()) sage: print [z[0].abs() for z in f.roots()] [0.644472635143760, 0.644472635143761, 0.458731710756610, 0.476718789722295, 0.458731710756610] \end{Verbatim} \vskip .1in \noindent This next example is also random: \vskip .2in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: C = RandomLinearCode(8,3,GF(2)); C.minimum_distance() 3 sage: Cd = C.dual_code(); Cd.minimum_distance() 2 sage: C.spectrum() [1, 0, 0, 1, 3, 2, 0, 1, 0] sage: Cd.spectrum() [1, 0, 3, 6, 11, 8, 1, 2, 0] sage: C.chinen_polynomial() 2/7*t^6 + 4/21*t^5 + 13/70*t^4 + 17/105*t^3 + 13/140*t^2 + 1/21*t + 1/28 sage: C.gen_mat() [1 0 0 1 1 0 0 1] [0 1 0 0 0 1 1 0] [0 0 1 1 0 0 1 1] sage: C.zeta_polynomial() 3/7*T^5 + 3/14*T^4 + 11/70*T^3 + 17/140*T^2 + 17/280*T + 1/56 \end{Verbatim} The next example concerns a code which is formally self-dual but not self-dual. \vskip .2in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: RT = PolynomialRing(CC,"T") sage: MS = MatrixSpace(GF(2), 4, 8) sage: G = MS([[1,0,0,0,0,1,1,0],[0,1,0,0,1,1,1,0], [0,0,1,0,1,1,1,1],[0,0,0,1,0,0,1,0]]) sage: C = LinearCode(G) sage: C.minimum_distance() 2 sage: Cd = C.dual_code(); Cd.minimum_distance() 2 sage: f = RT(C.chinen_polynomial()) sage: print [z[0].abs() for z in f.roots()] [0.707106781186549, 0.707106781186547, 0.707106781186547, 0.707106781186546, 0.707106781186547, 0.707106781186547] sage: C.gen_mat() [1 0 0 0 0 1 1 0] [0 1 0 0 1 1 1 0] [0 0 1 0 1 1 1 1] [0 0 0 1 0 0 1 0] sage: C.chinen_polynomial() 2/7*t^6 + 2/7*t^5 + 11/70*t^4 + 3/35*t^3 + 11/140*t^2 + 1/14*t + 1/28 sage: C.spectrum() [1, 0, 1, 4, 3, 4, 3, 0, 0] sage: Cd = C.dual_code(); Cd.minimum_distance() 2 sage: Cd.spectrum() [1, 0, 1, 4, 3, 4, 3, 0, 0] sage: list_plot([(z[0].real(),z[0].imag()) for z in f.roots()]) \end{Verbatim} \vskip .1in \noindent The last command gives a plot of the roots: %\newpage \begin{figure}[h!] \begin{minipage}{\textwidth} \begin{center} \includegraphics[height=7cm,width=7cm]{chinen-8-4-2-fsd-RH.eps} \end{center} \end{minipage} \caption{Roots of the Chinen zeta polynomial for a formally self-dual $[8,4,2]$ binary code.} \label{fig:chinen-8-4-2-fsd-RH} \end{figure} Our last example is one for which the RH is false. \vskip .2in \begin{Verbatim}[fontsize=\scriptsize,fontfamily=courier,fontshape=tt,frame=single,label=\sage] sage: RT = PolynomialRing(CC,"T") sage: MS = MatrixSpace(GF(2), 4, 8) sage: G = MS([[1,1,0,0,0,0,1,1],[0,0,1,0,0,1,0,1],[0,0,0,1,0,1,1,0],[0,0,0,0,1,1,1,1]]) sage: C = LinearCode(G) sage: C.chinen_polynomial() 1/7*t^6 + 1/7*t^5 + 39/140*t^4 + 17/70*t^3 + 39/280*t^2 + 1/28*t + 1/56 sage: C.spectrum() [1, 0, 0, 4, 6, 4, 0, 0, 1] sage: Cd = C.dual_code(); Cd.minimum_distance() 2 sage: Cd.spectrum() [1, 0, 1, 0, 11, 0, 3, 0, 0] sage: C.minimum_distance() 3 sage: Cd = C.dual_code(); Cd.minimum_distance() 2 sage: f = RT(C.chinen_polynomial()) sage: print [z[0].abs() for z in f.roots()] [1.19773471696883, 1.19773471696883, 0.707106781186547, 0.707106781186547, 0.417454710894058, 0.417454710894058] sage: print [z[0] for z in f.roots()] [0.0528116723604142 + 1.19656983895421*I, 0.0528116723604137 - 1.19656983895421*I, -0.571218487412783 + 0.416784644196318*I, -0.571218487412783 - 0.416784644196317*I, 0.0184068150523700 + 0.417048707955401*I, 0.0184068150523701 - 0.417048707955401*I] sage: C.gen_mat() [1 1 0 0 0 0 1 1] [0 0 1 0 0 1 0 1] [0 0 0 1 0 1 1 0] [0 0 0 0 1 1 1 1] sage: C.chinen_polynomial() 1/7*t^6 + 1/7*t^5 + 39/140*t^4 + 17/70*t^3 + 39/280*t^2 + 1/28*t + 1/56 sage: list_plot([(z[0].real(),z[0].imag()) for z in f.roots()]) \end{Verbatim} \vskip .1in \noindent The last command gives a plot of the roots: \begin{figure}[h!] \begin{minipage}{\textwidth} \begin{center} \includegraphics[height=7cm,width=7cm]{chinen-8-4-3-noRH.eps} \end{center} \end{minipage} \caption{Roots of the Chinen zeta polynomial for a $[8,4,3]$ binary code violating the RH.} \label{fig:chinen-8-4-3-noRH} \end{figure} \section{Appendix: Proofs} \subsection{MacWilliam's identity} \begin{theorem} (MacWilliams' identity): If $C$ is a linear code over $GF(q)$ then \[ A_{C^\perp}(x,y) = |C|^{-1}A_C(x+(q-1)y,x-y). \] \end{theorem} \index{MacWilliams identity} \vskip .1in Before proving this we need a few definitions. Index the finite field $GF(q)$ in some fixed way: $GF(q)=\{\omega_0=0,\omega_1,\dots ,\omega_{q-1}\}$. The {\bf composition} of $v = (v_1,\dots ,v_n)\in GF(q)^n$ is defined by \index{composition} \[ {\rm comp}(v) = (s_0,\dots ,s_{q-1}), \] where $s_j=s_j(v)$ denotes the number of components of $v$ equal to $\omega_j$. Clearly, $\sum_{i=0}^{q-1} s_i(v)=n$, for each $v\in GF(q)^n$. For $s = (s_0,\dots ,s_{q-1})\in \zzz^q$, let $T_C(s)$ denote the number of codewords $c\in C$ with ${\rm comp}(c)=s$. Define the {\it complete weight enumerator} by \index{weight enumerator!complete} \[ W_C(z_0,\dots ,z_{q-1})=\sum_{c\in C} z_0^{s_0(c)}\dots z_{q-1}^{s_{q-1}(c)}=\sum_{s\in \zzz^q} T_C(s)z_0^{s_0}\dots z_{q-1}^{s_{q-1}}. \] Sometimes, when it is convenient, we identify the variables $z_i$ with the variables $z_{\omega_i}$. This enumerator is related to the Hamming weight enumerator as follows: \[ A_C(x,y)=W_C(x,y,\dots ,y). \] Let $\{1,\alpha,\alpha^2,\dots ,,\alpha^{m-1}\}$ denote a power basis of $GF(q)/GF(p)$. Let $\zeta=\zeta_p=e^{2\pi i/p}$ denote a $p$-th root of unity. If $\beta,\gamma\in GF(q)$ are written $\beta = \beta_0+\beta_1\alpha + \dots + \beta_{m-1}\alpha^{m-1}$ and $\gamma = \gamma_0+\gamma_1\alpha + \dots + \gamma_{m-1}\alpha^{m-1}$ ($\beta_i\in GF(p)$, $\gamma_j\in GF(p)$), then we define the character $\chi_\beta:GF(q)\rightarrow \ccc^\times$ by \[ \chi_\beta(\gamma) = \zeta^{\beta_0\gamma_0+\dots +\beta_{q-1}\gamma_{q-1}}. \] Each character $\chi$ of $GF(q)$ is of this form, $\chi=\chi_\beta$, for some unique $\beta \in GF(q)$. In particular, \[ \chi_1(\gamma) = \zeta^{\gamma_0}, \] which is for all $\gamma\in GF(q)$ (hence also for $\gamma\in GF(p)$). For $u,v\in GF(q)^n$, define \[ \chi_u(v) = \chi_1(u\cdot v), \] and define the {\it Fourier transform} by \index{Fourier transform} \[ \hat{f}(u)=\sum_{v\in GF(q)^n} \chi_u(v)f(v), \] for any function $f$ on $GF(q)^n$. \index{Poisson's summation formula} If $u=(u_1,\dots ,u_n)\in GF(q)^n$, $v=(v_1,\dots ,v_n)\in GF(q)^n$, then $\chi_u(v)=\prod_{i=1}^n \chi_{u_i}(v_i)$ This means that if $f(u)=\prod_{I=1}^n f_i(u_i)$ is a ``factorizable'' function then \[ \hat{f}(u)=\prod_{i=1}^n \hat{f_i}(u_i). \] \begin{lemma} (Poisson's summation formula) If $C$ is an $[n,k]$ code over $GF(q)$ then \[ \sum_{c\in C^\perp}f(c) = \frac{1}{|C|} \sum_{c\in C}f(c). \] \end{lemma} Now we can start with proof of the MacWilliams identity. Define \[ f(u) = z_0^{s_0(u)}\dots \, z_{q-1}^{s_{q-1}(u)}, \] so \[ f(u) = z_0^{s_{0,i}}\dots \, z_{q-1}^{s_{q-1,i}} =\prod_{i=1}^n f_i(u_i), \] where $s_{k,i}=1$ if $u_i=\omega_k$ and $=0$ otherwise. Another way to define $f(u)$ is as follows: \[ f(u) = \prod_{i=1}^n z_{u_i}=\prod_{i=1}^n f_i(u_i). \] We have then \[ \begin{array}{ll} \hat{f}(u) & = \sum_{v\in GF(q)^n} \chi_u(v)f(v)\\ & = \prod_{i-1}^n \hat{f_i}(u_i)\\ & =\prod_{i-1}^n (F_q\cdot (z_0,\dots ,z_{q-1}))_i, \end{array} \] where $F_q$ is a $q\times q$ circulant matrix of elements of $GF(q)$ and $(F_q\cdot z)_i$ denotes its $i$-th component: \[ (F_q\cdot (z_0,\dots ,z_{q-1}))_i = \sum_{\omega\in GF(q)} \chi_{\omega_i}(\omega) z_\omega = \sum_{\omega\in GF(q)} \chi_{1}(\omega_i \omega) z_\omega . \] Poisson's summation formula implies \[ W_{C^\perp}(z_0,\dots ,z_{q-1}) =\frac{1}{|C|} W_C(F_q\cdot (z_0,\dots ,z_{q-1})). \] Let $x=z_0$ and $y=z_1=\dots =z_{q-1}$. It remains to note \[ \sum_{b=1}^{q-1} \chi_{a}(b)= \left\{ \begin{array}{ll} q-1, & {\rm if}\ a=0,\\ -1, & {\rm if}\ a\not= 0, \end{array} \right. \] \qed \subsection{Mallows-Sloane-Duursma bounds} We sketch a proof of Theorem \ref{thrm:bounds3} following Duursma \cite{D3}. We shall restrict to the Type 1 case for simplicity. (The Type 2 case is similar, but follow modifications as indicated in \cite{D3}, \S 2.) We shall also assume that $F$ contains the term $y^n$ (the analog of the assumption that $C$ contains the all $1$'s codeword). Some notation. If $p(x,y)\in \ccc[x,y]$ then we define \[ p(x,y)(D)=p(\frac{\partial}{\partial x},\frac{\partial}{\partial y}). \] If $\sigma$ is any invertible $2\times 2$ matrix and $(u,v)=(x,y)\sigma$ then \begin{equation} \label{eqn:lemma1} p((u,v)\sigma^t)(D)F(u,v) = p(x,y)(D)F((x,y)\sigma). \end{equation} \begin{lemma} \label{lemma:prod-rule} Fix a homogeneous function $f(x,y)$. For all $i$ with $1\leq i\leq e$, let $a_i\not= 0$, $b_i$, $c_i\not= $, and $d_i$ be complex numbers satisfying $(a_ix+b_iy)^m|(c_ix+d_iy)(D)f(x,y)$, for some integer $m>1$. Then \[ \prod_{i=1}^e (a_ix+b_iy)^{m-e+1}|( \prod_{i=1}^e c_ix+d_iy)(D)f(x,y). \] \end{lemma} {\it Note}: This implies the result that Duursma claims in \cite{D3}, (5) (where his equation, in his special case, has $m=d^{\perp}-1$ and $e=c$). \vskip .1in \pf Using (\ref{eqn:lemma1}), we may assume without loss of generality that $d_i=0$, for all $i$, after making a suitable linear change of coordinates. Under the coordinate transformation $z=x/y$, $f(x,y)$ may be regarded as a polynomial $F(z)$ on $\ppp^1$. If $f(x,y) = x^ky^{n-k}$ then $F(x) = z^k$, and an explicit calculation allows one to check that $D_xf(x,y)$ corresponds to $D_zF(z)$. The hypothesis $(a_ix+b_iy)^m|(c_ix)(D)f(x,y)$ can be rephrased as saying that the derivative of $F$ under has roots of multiplicity $m$ at certain points. Therefore the $e$-th order derivative of $F$ gives a function which has zeros at these points of order at least $m-e+1$. \qed Let $F$ be any VSDWE of length $n$ and minimum distance $d$. Note that if $F$ is as above then \begin{equation} \label{eqn:(3)} y^{d-1}|y(D)F(x,y). \end{equation} These equations (\ref{eqn:lemma1}) and (\ref{eqn:(3)}) imply \[ (u-v)^{d-1}|((q-1)u-v)(D)F(u,v). \] Taking $u = x$ and $v=\zeta y$, we have \[ (x-\zeta y)^{d-1}|((q-1)x-\zeta y)(D)F(x,y). \] By Lemma \ref{lemma:prod-rule}, this implies \begin{equation} \label{eqn:(5)} (x^b- y^b)^{d-b}|((q-1)^bx^b - y^b)(D)F(x,y). \end{equation} Using equations (\ref{eqn:(3)}) and (\ref{eqn:(5)}) and reasoning similar to that used in the proof of Lemma \ref{lemma:prod-rule}, we obtain \[ a(x,y)|p(x,y)(D)F(x,y), \] where $a(x,y)=y^{d-b-1}(x^b-y^b)^{d-b-1}$ and $p(x,y)=y((q-1)^bx^b - y^b)$. Comparing highest order terms in $y$ in $p(x,y)(D)F(x,y)$ (recall we assumed $F$ contains $y^n$), we obtain $d-b-1+b(d-b-1)\leq n-b-1$. From this, (\ref{eqn:divbound}) follows in the Type 1 case. This is the first part of Theorem \ref{thrm:bounds3}. The second part follows from the first using properties of the greatest integer function in a straightforward way. \qed \vskip .2in {\it Acknowledgements}: I am very grateful to Thann Ward for the reference to \cite{Sl}, Koji Chinen for many interesting emails about his work, and to Cary Huffman and Iwan Duursma for very interesting conversations on this topic. \begin{thebibliography}{99} \bibitem[C1]{C1} K. Chinen, {\it Zeta functions for formal weight enumerators and the extremal property}, Proc. Japan Acad. Ser. A Math. Sci. vol. 81, Number 10 (2005), 168-173. \bibitem[C2]{C2} ------, {\it Zeta functions for formal weight enumerators and an analogue of the Mallows-Sloane bound}, \verb+http://arxiv.org/pdf/math/0510182+, \verb+http://front.math.ucdavis.edu/math.NT/0510182+ \bibitem[C3]{C3} ------, ``An abundance of invariant polynomials satisfying the Riemann hypothesis,'' \verb+http://arxiv.org/abs/0704.3903+ \bibitem[DH]{DH} S. DiPippo, E. Howe, {\it Real polynomials with all roots on the unit circle and abelian varieties over finite fields}, J. Number Theory 78(1998)426-450. \newline Available: \url{http://arxiv.org/abs/math/9803097} \bibitem[D1]{D1} I. Duursma, {\it Combinatorics of the two-variable zeta function}, in {\bf Finite fields and applications}, 109--136, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004. \bibitem[D2]{D2} ------, {\it Results on zeta functions for codes}, Fifth Conference on Algebraic Geometry, Number Theory, Coding Theory and Cryptography, University of Tokyo, January 17-19, 2003. \bibitem[D3]{D3} ------, {\it Extremal weight enumerators and ultraspherical polynomials}, Discrete Mathematics, vol. 268, no. 1-3, pp. 103-127, July 2003. \bibitem[D4]{D4} ------, {\it A Riemann hypothesis analogue for self-dual codes}, In: {\bf Codes and Association schemes}, Eds. Barg and Litsyn, AMS Dimacs Series, vol. 56, pp. 115-124, 2001. \bibitem[D5]{D5} ------, {\it From weight enumerators to zeta functions}, in {\bf Discrete Applied Mathematics}, vol. 111, no. 1-2, pp. 55-73, 2001. \bibitem[D6]{D6} ------, {\it Weight distributions of geometric Goppa codes}, Transactions of the AMS, vol. 351, pp. 3609-3639, September 1999. \bibitem[Dw]{Dw} B. Dwork, {\it On the rationality of the zeta function of an algebraic variety}, Amer. J. Math., vol. 82 ( 1960 ), pp. 631-648. \bibitem[FR]{FR} D. Faifman, Z. Rudnick, {\it Statistics of the zeros of zeta functions in families of hyperelliptic curves over a finite field}, \newline Available: \url{http://front.math.ucdavis.edu/0803.3534} \bibitem[G]{G} The GAP Group, {\tt GAP} -- Groups, Algorithms, and Programming, Version 4.4.9; 2006. \url{http://www.gap-system.org}. \bibitem[GPS]{GPS} G.-M. Greuel, G. Pfister, and H. Sch\"onemann. {\sc Singular} 3.0. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern (2005). \url{http://www.singular.uni-kl.de}. \bibitem[HT]{HT} T. Harada, M. Tagami, {\it A Riemann hypothesis analogue for invariant rings}, Discrete Mathematics, vol. 307, pp. 2552-2568, 2007. \bibitem[HP]{HP} W. C. Huffman and V. Pless, {\bf Fundamentals of error-correcting codes}, Cambridge Univ. Press, 2003. %\bibitem[J]{J} D. Joyner, \sage code for extremal Duursma zeta functions, at %\newline %\url{http://sage.math.washington.edu/home/wdj/research/zeta-fcn.sage} \bibitem[JKT]{JKT} D. Joyner, A. Ksir, W. Traves, {\it Automorphism Groups of Generalized Reed-Solomon Codes} in {\bf Advances in coding theory and cryptology}, (edited by T Shaska, W C Huffman, D Joyner \& V Ustimenko) Series on Coding Theory and Cryptology - Vol. 3, World Scientific, 2007. \bibitem[KL]{KL} J.-L. Kim and Y. Lee, {\it Euclidean and Hermitian self-dual MDS codes over large finite fields}, J. Combinatorial Theory, Ser. A, 105 (2004) pp. 79-95. \bibitem[NRS]{NRS} G. Nebe, E. Rains, N. Sloane, {\bf Self-dual codes and invariant theory}, Springer-Verlag, 2006. \bibitem[O]{O} M. Ozeki, {\it On the notion of Jacobi polynomials for codes}, Math. Proc. Cambridge Phil. Soc. 121(1997)15-30. \bibitem[S]{S} The \sage Group, \sage: {\it Mathematical software}, version 2.10. \newline \url{http://www.sagemath.org/} %\verb+http://modular.math.washington.edu/sage/+ %\newline %\url{http://sage.scipy.org/} %\verb+http://sage.scipy.org/+ \bibitem[Sc]{Sc} W. Schmidt, {\bf Equations over finite fields: an elementary approach}, 2nd ed., Kendrick Press, 2004. \bibitem[Sl]{Sl} N. J. A. Sloane, {\it Self-dual codes and lattices}, in {\bf Relations Between Combinatorics and Other Parts of Mathematics}., Proc. Symp. Pure Math., Vol. 34, American Mathematical Society, Providence, RI, 1979, pp. 273-308. \bibitem[TV]{TV} M. A. Tsfasman and S. G. Vladut, {\bf Algebraic-geometric codes}, Mathematics and its Applications, Kluwer Academic Publishers, Dordrechet 1991. %\bibitem[]{} %\bibitem[]{} \end{thebibliography} \printindex \end{document} R_CC = PolynomialRing(CC,"T") C = best_known_linear_code(n,k,GF(q)) C.zeta_polynomial() C.weight_enumerator() Cd = C.dual_code() Cd.zeta_polynomial() Cd.weight_enumerator() sage: n = 6; k = 2; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: [abs(z[0]) for z in R_CC(C.zeta_polynomial()).roots()] [0.707106781186548, 0.707106781186548] sage: C.weight_enumerator() x^6 + 3*x^2*y^4 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: Cd.weight_enumerator() x^6 + 3*x^4*y^2 + 8*x^3*y^3 + 3*x^2*y^4 + y^6 sage: n = 6; k = 3; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: C.weight_enumerator() x^6 + 4*x^3*y^3 + 3*x^2*y^4 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: Cd.weight_enumerator() x^6 + 4*x^3*y^3 + 3*x^2*y^4 sage: n = 6; k = 4; q = 2 is a bad example (d or dperp=1) sage: n = 7; k = 2; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 10/21*T^3 + 12/35*T^2 + 16/105*T + 1/35 sage: [abs(z[0]) for z in R_CC(C.zeta_polynomial()).roots()] [0.311239502524417, 0.439064444146946, 0.439064444146946] sage: C.weight_enumerator() x^7 + x^3*y^4 + 2*x^2*y^5 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 4/35*T^3 + 32/105*T^2 + 12/35*T + 5/21 sage: [abs(z[0]) for z in R_CC(Cd.zeta_polynomial()).roots()] [1.60647988428389, 1.13878499310379, 1.13878499310379] sage: Cd.weight_enumerator() x^7 + 5*x^5*y^2 + 12*x^4*y^3 + 7*x^3*y^4 + 4*x^2*y^5 + 3*x*y^6 sage: n = 7; k = 3; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: C.weight_enumerator() x^7 + 7*x^3*y^4 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: Cd.weight_enumerator() x^7 + 7*x^4*y^3 + 7*x^3*y^4 + y^7 sage: n = 7; k = 4; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: C.weight_enumerator() x^7 + 7*x^4*y^3 + 7*x^3*y^4 + y^7 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: Cd.weight_enumerator() x^7 + 7*x^3*y^4 sage: sage: n = 7; k = 5; q = 2 is a bad example (d or dperp=1) sage: n = 8; k = 2; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 1/2*T^3 + 9/28*T^2 + 1/7*T + 1/28 sage: [abs(z[0]) for z in R_CC(C.zeta_polynomial()).roots()] [0.383505906932875, 0.431568713841709, 0.431568713841709] sage: C.weight_enumerator() x^8 + 2*x^3*y^5 + x^2*y^6 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 1/7*T^3 + 2/7*T^2 + 9/28*T + 1/4 sage: [abs(z[0]) for z in R_CC(Cd.zeta_polynomial()).roots()] [1.30376088336891, 1.15856405704003, 1.15856405704003] sage: Cd.weight_enumerator() x^8 + 7*x^6*y^2 + 18*x^5*y^3 + 15*x^4*y^4 + 12*x^3*y^5 + 9*x^2*y^6 + 2*x*y^7 sage: sage: n = 8; k = 3; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 4/7*T^4 + 6/35*T^2 + 6/35*T + 3/35 sage: [abs(z[0]) for z in R_CC(C.zeta_polynomial()).roots()] [0.486469512726416, 0.796141021150801, 0.486469512726416, 0.796141021150801] sage: C.weight_enumerator() x^8 + 6*x^4*y^4 + y^8 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 12/35*T^4 + 12/35*T^3 + 6/35*T^2 + 1/7 sage: [abs(z[0]) for z in R_CC(Cd.zeta_polynomial()).roots()] [1.02781363871654, 0.628029440409016, 1.02781363871654, 0.628029440409016] sage: Cd.weight_enumerator() x^8 + 4*x^6*y^2 + 22*x^4*y^4 + 4*x^2*y^6 + y^8 sage: sage: n = 8; k = 4; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: C.weight_enumerator() x^8 + 14*x^4*y^4 + y^8 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 2/5*T^2 + 2/5*T + 1/5 sage: Cd.weight_enumerator() x^8 + 14*x^4*y^4 + y^8 sage: n = 8; k = 5; q = 2 is a bad example (d or dperp=1) sage: n = 8; k = 6; q = 2 is a bad example (d or dperp=1) sage: n = 9; k = 2; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 1/2*T^3 + 9/28*T^2 + 1/7*T + 1/28 sage: C.weight_enumerator() x^9 + 3*x^3*y^6 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 1/7*T^3 + 2/7*T^2 + 9/28*T + 1/4 sage: Cd.weight_enumerator() x^9 + 9*x^7*y^2 + 27*x^6*y^3 + 27*x^5*y^4 + 27*x^4*y^5 + 27*x^3*y^6 + 9*x^2*y^7 + y^9 sage: n = 9; k = 3; q = 2 is a bad example (d or dperp=1) sage: n = 9; k = 4; q = 2 is a bad example (d or dperp=1) sage: n = 9; k = 5; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 4/21*T^4 + 20/63*T^3 + 2/7*T^2 + 10/63*T + 1/21 sage: C.weight_enumerator() x^9 + 4*x^6*y^3 + 14*x^5*y^4 + 8*x^4*y^5 + 4*x^2*y^7 + x*y^8 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 4/21*T^4 + 20/63*T^3 + 2/7*T^2 + 10/63*T + 1/21 sage: Cd.weight_enumerator() x^9 + 6*x^5*y^4 + 8*x^4*y^5 + x*y^8 sage: n = 9; k = 6; q = 2 is a bad example (d or dperp=1) sage: n = 9; k = 7; q = 2 is a bad example (d or dperp=1) sage: n = 10; k = 2; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 8/15*T^4 + 3/10*T^3 + 53/420*T^2 + 1/28*T + 1/210 sage: C.weight_enumerator() x^10 + x^4*y^6 + 2*x^3*y^7 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 4/105*T^4 + 1/7*T^3 + 53/210*T^2 + 3/10*T + 4/15 sage: Cd.weight_enumerator() x^10 + 12*x^8*y^2 + 36*x^7*y^3 + 46*x^6*y^4 + 60*x^5*y^5 + 60*x^4*y^6 + 28*x^3*y^7 + 9*x^2*y^8 + 4*x*y^9 sage: sage: n = 10; k = 3; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 16/45*T^5 + 4/15*T^4 + 59/315*T^3 + 37/315*T^2 + 2/35*T + 1/63 sage: C.weight_enumerator() x^10 + 4*x^5*y^5 + 2*x^4*y^6 + x^2*y^8 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 8/63*T^5 + 8/35*T^4 + 74/315*T^3 + 59/315*T^2 + 2/15*T + 4/45 sage: Cd.weight_enumerator() x^10 + 4*x^8*y^2 + 16*x^7*y^3 + 30*x^6*y^4 + 32*x^5*y^5 + 20*x^4*y^6 + 16*x^3*y^7 + 9*x^2*y^8 sage: sage: n = 10; k = 4; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 8/15*T^6 + 2/15*T^5 + 1/21*T^4 + 8/105*T^3 + 2/21*T^2 + 8/105*T + 4/105 sage: C.weight_enumerator() x^10 + 8*x^6*y^4 + 4*x^4*y^6 + 3*x^2*y^8 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 32/105*T^6 + 32/105*T^5 + 4/21*T^4 + 8/105*T^3 + 1/42*T^2 + 1/30*T + 1/15 sage: Cd.weight_enumerator() x^10 + 3*x^8*y^2 + 4*x^7*y^3 + 12*x^6*y^4 + 24*x^5*y^5 + 12*x^4*y^6 + 4*x^3*y^7 + 3*x^2*y^8 + y^10 sage: sage: sage: n = 10; k = 5; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 16/45*T^6 + 8/315*T^4 + 16/105*T^3 + 22/105*T^2 + 6/35*T + 3/35 sage: C.weight_enumerator() x^10 + 18*x^6*y^4 + 8*x^4*y^6 + 5*x^2*y^8 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 12/35*T^6 + 12/35*T^5 + 22/105*T^4 + 8/105*T^3 + 2/315*T^2 + 1/45 sage: Cd.weight_enumerator() x^10 + x^8*y^2 + 6*x^6*y^4 + 16*x^5*y^5 + 6*x^4*y^6 + x^2*y^8 + y^10 sage: sage: n = 10; k = 6; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: C.zeta_polynomial() 8/105*T^5 + 64/315*T^4 + 4/15*T^3 + 74/315*T^2 + 16/105*T + 1/15 sage: [abs(z[0]) for z in R_CC(C.zeta_polynomial()).roots()] [1.03982576114306, 0.843975247800926, 0.843975247800926, 1.03982576114306, 1.13612858850368] sage: C.weight_enumerator() x^10 + 8*x^7*y^3 + 18*x^6*y^4 + 16*x^5*y^5 + 8*x^4*y^6 + 8*x^3*y^7 + 5*x^2*y^8 sage: Cd = C.dual_code() sage: Cd.zeta_polynomial() 4/15*T^5 + 32/105*T^4 + 74/315*T^3 + 2/15*T^2 + 16/315*T + 1/105 sage: [abs(z[0]) for z in R_CC(Cd.zeta_polynomial()).roots()] [0.480849791074959, 0.592434436084242, 0.480849791074959, 0.440091029360079, 0.592434436084242] sage: Cd.weight_enumerator() x^10 + 2*x^6*y^4 + 8*x^5*y^5 + 4*x^4*y^6 + x^2*y^8 sage: n = 10; k = 7; q = 2 is a bad example (d or dperp=1) C = best_known_linear_code(n,k,GF(q)) P = C.chinen_polynomial() [RR(abs(z[0])) for z in P.roots()] sage: n = 9; k = 2; q = 2 sage: C = best_known_linear_code(n,k,GF(q)) sage: P = C.chinen_polynomial() sage: [RR(abs(z[0])) for z in P.roots()] [0.431568713841709, 0.431568713841709, 0.383505906932874, 0.500000000000000, 0.000000000000000]