Duursma zeta function of a graph

I’m going to start off with two big caveats:

  1. This is not Duursma‘s definition, it’s mine.
  2. 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 C be an [n,k,d]_q code, ie a linear code over GF(q) of length n, dimension k, and minimum distance d. In general, if C is an [n,k,d]_q-code then we use [n,k^\perp,d^\perp]_q 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. Motivated by analogies with local class field theory, in [Du] Iwan Duursma introduced the (Duursma) zeta function \zeta=\zeta_C:

\zeta_C(T)=\frac{P(T)}{(1-T)(1-qT)},
where P(T)=P_C(T) is a polynomial of degree n+2-d-d^\perp, called the zeta polynomial of C. We next sketch the definition of the zeta polynomial.

If C^\perp denotes the dual code of C, with parameters [n,n-k,d^\perp] then the MacWilliams identity relates the weight enumerator A_{C^\perp} of C^\perp to the weight enumerator A_{C} of C:

A_{C^\perp}(x,y) = |C|^{-1}A_C(x+(q-1)y,x-y).
A polynomial P(T)=P_C(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 a (Duursma) zeta polynomial of C.

Theorem (Duursma): If C be an [n,k,d]_q code with d\geq 2 and d^\perp\geq 2 then the Duursma zeta polynomial P=P_C exists and is unique.

See the papers of Duursma for interesting properties and conjectures.

Duursma zeta function of a graph

Let \Gamma=(V,E) be a graph having |V(\Gamma)| vertices and |E(\Gamma)| edges. We define the zeta function of \Gamma via the Duursma zeta function of the binary linear code defined by the cycle space of \Gamma.

Theorem (see [DKR], [HB], [JV]): The binary code B=B_\Gamma generated by the rows of the incidence matrix of \Gamma is the cocycle space of \Gamma over GF(2), and the dual code B^\perp is the cycle space Z=Z_\Gamma of \Gamma:

B_\Gamma^\perp = Z_\Gamma.
Moreover,
(a) the length of B_\Gamma is |E|, dimension of B_\Gamma is |V|-1, and the minimum distance of B_\Gamma is the edge-connectivity of \Gamma,
(b) length of Z_\Gamma is |E|, dimension of Z_\Gamma is |E|-|V|+1, and the minimum distance of Z_\Gamma is the girth of \Gamma.

Call Z_\Gamma the cycle code and B_\Gamma the cocycle code.

Finally, we can introduce the (Duursma) zeta function \Gamma:

\zeta_\Gamma(T)=\zeta_{Z_\Gamma} =\frac{P(T)}{(1-T)(1-qT)},
where P=P_\Gamma=P_{Z_\Gamma} is the Duursma polynomial of \Gamma.

Example: Using SageMath, when \Gamma = W_5, the wheel graph on 5 vertices, we have

P_\Gamma(T) = \frac{2}{7}T^4 + \frac{2}{7}T^3 + \frac{3}{14}T^2 + \frac{1}{7}T + \frac{1}{14}.
All its zeros are of absolute value 1/\sqrt{2}.

References

[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.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s