I’m going to start off with two big caveats:
- This is not Duursma‘s definition, it’s mine.
- I’m not convinced (yet?) that it’s a useful idea to examine such a zeta function.
So that’s your warning – you may be wasting your time reading this!
The Duursma zeta function of a linear block (error-correcting) code is due to Iwan Duursma and is a fascinating object of study. (More precisely, it’s defined for “formal” linear block codes, ie, defined via a weight enumerator polynomial with a suitable MacWilliams-like functional equation.) Sometimes it satisfies an analog of the Riemann hypothesis and sometimes it doesn’t. And sometimes that analog is still an open question.
Duursma zeta function of a code
Before we define the Duursma zeta function of a graph, we introduce the Duursma zeta function of a code.
Let be an code, ie a linear code over of length , dimension , and minimum distance . In general, if is an -code then we use for the parameters of the dual code, . It is a consequence of Singleton’s bound that , with equality when is an MDS code. Motivated by analogies with local class field theory, in [Du] Iwan Duursma introduced the (Duursma) zeta function :
where is a polynomial of degree , called the zeta polynomial of . We next sketch the definition of the zeta polynomial.
If denotes the dual code of , with parameters then the MacWilliams identity relates the weight enumerator of to the weight enumerator of :
A polynomial for which
is a (Duursma) zeta polynomial of .
Theorem (Duursma): If be an code with and then the Duursma zeta polynomial exists and is unique.
See the papers of Duursma for interesting properties and conjectures.
Duursma zeta function of a graph
Let be a graph having vertices and edges. We define the zeta function of via the Duursma zeta function of the binary linear code defined by the cycle space of .
Theorem (see [DKR], [HB], [JV]): The binary code generated by the rows of the incidence matrix of is the cocycle space of over , and the dual code is the cycle space of :
(a) the length of is , dimension of is , and the minimum distance of is the edge-connectivity of ,
(b) length of is , dimension of is , and the minimum distance of is the girth of .
Call the cycle code and the cocycle code.
Finally, we can introduce the (Duursma) zeta function :
where is the Duursma polynomial of .
Example: Using SageMath, when , the wheel graph on 5 vertices, we have
All its zeros are of absolute value .
[Du] 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.
[DKR] P. Dankelmann, J. Key, B. Rodrigues, Codes from incidence matrices of graphs, Designs, Codes and Cryptography 68 (2013) 373-393.
[HB] S. Hakimi and J. Bredeson, Graph theoretic error-correcting codes, IEEE Trans. Info. Theory 14(1968)584-591.
[JV] D. Jungnickel and S. Vanstone, Graphical codes revisited, IEEE Trans. Info. Theory 43(1997)136-146.