边加权的边自由商图的Zeta函数

Edge-Weighted Zeta Functions of Edge-Free Quotients of Graphs

摘要: 为推广边自由商图的Zeta函数，本文定义了边加权的边自由商图上的Zeta函数。为方便推广后的Zeta函数的表达式的计算，利用边自由商图的性质，给出新的二项和三项行列式公式。

Abstract: Edge-weighted Zeta functions of edge-free quotients of graphs are defined to generalize the Zeta functions of edge-free quotients of graphs. Two-term and three-term determinant formulas of the edge-weighted Zeta functions are obtained with the properties of edge-free quotients of graphs, which offers a better way to calculate it.

1. 引言

Ihara [1] 定义了Ihara Zeta函数，并证明该函数为多项式的倒数。

建立在Hashimoto [2] 工作的基础上，Bass [3] 考虑一个群G在有限树X上(不翻边)的作用，其中商图X/G和稳定化子均为有限的。他将一个Zeta函数和商X/G用非交换行列式联系起来，并表为一个显式多项式的倒数。

Stark和Terras [4] 用初等方法刻画了图的Zeta函数，将图X的Ihara Zeta函数表为图X中素元的Euler积，并重新证明了Bass的结果。因此Ihara Zeta函数 $\zeta \left(u,X\right)$ 可被看成数域K上戴德金Zeta函数 $\zeta \left(u,X\right)$ 的图论类比，且满足一些相似的性质。

Stark和Terras [5] [6] 考虑图的自由Galois覆盖的Zeta函数，进一步发展了图论与数论之间的类比。利用图的性质，给出二项、三项行列式来计算相应Zeta函数。Zakharov [7] 考虑了边自由作用下商图的Ihara Zeta函数。

本文定义了边加权情形下，边自由作用的商图的Ihara Zeta函数，推广了边自由商图的Zeta函数。为计算推广后的Zeta函数，给出了新的二项和三项行列式公式。

本文为研究边自由作用下，边加权的图和商图的Zeta函数的整除关系提供了工具。后续的定义和证明会在接下来的论文中给出。本文的定义和公式对于边平凡的群图这样的一般情形同样适用。

2. 基础知识

2.1. 边平凡的群图

定义1带腿(leg)的图X由下列组成：顶点集 $V\left(X\right)$ ，半边集 $H\left(X\right)$ ，根映射 $r:H\left(X\right)\to V\left(X\right)$ ，

对合映射 $\sigma :H\left(X\right)\to H\left(X\right)$ ，使得 $\sigma \left(h\right)=\bar{h}$ 。

对合生成的群，其作用下的轨道有一个或两个元素。含两个元素的轨道 $\left\{h,\bar{h}\right\}$ 称为X的一个边，记所有边组成的集合为 $E\left(X\right)$ 。对边 $\left\{h,\bar{h}\right\}$ 定向，得有向边 $e=\left(h,\bar{h}\right)$ ，称 $i\left(e\right)=r\left(h\right)$ 为e的起点， $t\left(e\right)=r\left(\bar{h}\right)$ 为e的终点。 $\bar{e}=\left(\bar{h},h\right)$ 为与e反向的边。若 $r\left(h\right)=r\left(\bar{h}\right)$ ，称边 $e=\left(h,\bar{h}\right)$ 为环。若 $\sigma \left(h\right)=h$ ，则轨道中只有一个元素，称h为X的腿(leg)，记腿集为 $L\left(X\right)$ 。

这里只考虑连通图。下面定义边平凡的群图。

定义2图X和群 $X_v$ (对任意 $v\in V\left(X\right)$ )组成了边平凡的群图 $\mathbb{X}=\left(X,X_v\right)$ 。称 $\mathbb{X}$ 是有限的，若X是有限图且 $X_v$ 为有限群。

序列 $P=g_0{h}_1{g}_1{h}_2\cdots g_{n-1}{h}_n$ 称为 $\mathbb{X}$ 中长度 $n=l\left(P\right)$ 的路P，其中 $h_1\cdots h_n$ 为顶点 $v_0=r\left(h_1\right)$ ， $v_j=r\left(h_{j+1}\right)=r\left({\bar{h}}_j\right)$ $j=1,\cdots ,n-1$ ， $v_n=r\left({\bar{h}}_n\right)$ 的X中路， $g_j\in X_{v_j}$ $j=0,\cdots ,n-1$ 。若 $v_0=v_n$ ，称P是闭路。若P的终点等于Q的起点，可定义路的合成PQ。

对 $\mathbb{X}$ 中的路 $P=g_0{h}_1{g}_1{h}_2\cdots g_{n-1}{h}_n$ ，若 $\forall j\in \left\{1,\cdots ,n\right\}$ ，要么 $h_{j+1}\ne {\bar{h}}_j$ ，要么 $g_j\ne e$ ，称P为约化的。

路P称为本原路，若P是约化的闭路，且 $\nexists Q$ ，使得 $P=Q^k,k\ge 2$ 。任一约化路都能唯一表成本原路的次幂。

称闭路 $P=g_0{h}_1{g}_1{h}_2\cdots g_{n-1}{h}_n$ 和 $P^{\prime }={g^{\prime }}_0{h^{\prime }}_1\cdots {g^{\prime }}_{n-1}{h^{\prime }}_n$ 等价，若 $\exists m\left(0\le m\le n-1\right)$ ，有 ${g^{\prime }}_{j-1}=g_{j-1+m}$ ， ${h^{\prime }}_j=h_{j+m}$ ， $\forall j\in \left\{1,\cdots ,n\right\}$ 。等价是一个等价关系。本原路的等价类称为 $\mathbb{X}$ 中素元 $p$ ，长度 $l\left(p\right)$ 是定义良好的。给定长度的素元有有限个。

2.2. 群在图上的作用

下面考虑群在图上的作用。

定义3 $X=H\left(X\right)\cup V\left(X\right)$ 。图X的自同构f指 ${f|}_{H\left(X\right)}:H\left(X\right)\to H\left(X\right),{f|}_{V\left(X\right)}:V\left(X\right)\to V\left(X\right)$ 的双射，保持根映射和对合映射。

f将边映到边，将腿映到腿。X的所有自同构作成一个群 $Aut\left(X\right)$ 。

将同态 $\Phi :G\to Aut\left(X\right)$ 称为群在图上的作用。主要对2种群在图上的作用感兴趣。

定义4称G在X上的作用是边自由的，若G在 $H\left(X\right)$ 上自由作用。

定义5称G在X上的作用是自由的，若G在 $V\left(X\right)$ 和 $H\left(X\right)$ 上都是自由作用。因为腿的使用，放宽了原有的G不翻边( $\forall e=\left\{h,\bar{h}\right\}\in E\left(X\right)$ ， $\forall g\in G$ ，有 $g\left(h\right)\ne \bar{h}$ )的条件。

有了群在图上的作用，下面定义商图。

定义6群G在图X上作用。 $X=H\left(X\right)\cup V\left(X\right)$ 。由自同构群的性质， $H\left(X\right)$ 中轨道构成 $H\left(X\right)$ 的划分， $V\left(X\right)$ 中轨道构成 $V\left(X\right)$ 的划分。顶点集为 $V\left(X/G\right)=V\left(X\right)/G$ 为G作用下 $V\left(X\right)$ 的轨道，半边集 $H\left(X/G\right)=H\left(X\right)/G$ 为G作用下 $H\left(X\right)$ 的轨道。G的作用保持根映射和对合映射，因此由根映射 $r:H\left(X\right)\to V\left(X\right)$ ，对合映射 $\sigma :H\left(X\right)\to H\left(X\right)$ ，相应有 $r:H\left(X/G\right)\to V\left(X/G\right)$ ， $\sigma :H\left(X/G\right)\to H\left(H/G\right)$ 。记自然商映射为 $\pi :X\to X/G$ 。

3. 边加权的边自由商图的Zeta函数

3.1. 定义

下面定义边加权的群的边自由商图的Ihara Zeta函数。

设有群的图 $\mathbb{X}$ ，半边集 $H\left(\mathbb{X}\right)=\left\{h_1,\cdots ,h_m,{\bar{h}}_1,\cdots ,{\bar{h}}_m\right\}\cup \left\{l_1,\cdots ,l_l\right\}$ 。

参照文献 [8] 和文献 [9] 的加权方式， $$ ，对h加权 $x_h$ ，使得 $x_{\bar{h}}=x_h^{-1}$ 。可见对 $l\in L\left(\mathbb{X}\right)$ (即h为腿， $h=\bar{h}$ 的情形)，有 $x_l^2=1$ 。此时令 $x_l=-1$ 。

对路 $P=g_0{h}_1{g}_1{h}_2\cdots g_{n-1}{h}_n$ ，定义路的权 $w\left(P\right)=x_{h_1}\cdots x_{h_n}$ 。

定义7边加权的群的边自由商图的Ihara Zeta函数如下：

$\zeta \left(u,\mathbb{X},w\right)=\underset{p}{{\displaystyle \prod }}{\left(1-w\left(p\right)u^{l\left(p\right)}\right)}^{-1}\text{.}$

3.2. 二项行列式公式

定义半边邻接权矩阵W如下：

$W_{h{h}^{\prime }}=\{\begin{array}{ll}\left(c\left(r\left(h^{\prime }\right)\right)-1\right)x_{h^{\prime }},\hfill & h^{\prime }=\bar{h},\hfill \\ c\left(r\left(h^{\prime }\right)\right)x_{h^{\prime }},\hfill & h^{\prime }\ne \bar{h}且r\left(h^{\prime }\right)=r\left(\bar{h}\right),\hfill \\ 0,\hfill & r\left(h^{\prime }\right)\ne r\left(\bar{h}\right)\text{.}\hfill \end{array}$

其中 $c\left(v\right)$ 为顶点负荷，有 $c\left(v\right)=\text{\#}\left(X_v\right)$ 。

可见，对路 $P=g_0{h}_1{g}_1{h}_2\cdots g_{n-1}{h}_n$ ， $W_{h_1{h}_2}\cdots W_{h_n{h}_1}$ 为 $h_1\cdots h_n$ 上的闭约化路权重之和。

下面给出边加权的群的边自由商图的Ihara Zeta函数的二项行列式公式。

定理1设 $\mathbb{X}=\left(X,X_v,w\right)$ 为有限边加权的边平凡的群图，其中半边个数为k。 $\mathbb{X}$ 的Ihara Zeta函数等于

$\zeta {\left(u,\mathbb{X},w\right)}^{-1}=\det \left(I_k-Wu\right),$

其中W为 $\mathbb{X}$ 的半边邻接权矩阵。

证明：对 $\zeta \left(u,\mathbb{X},w\right)$ 取log，得

$\log \zeta \left(u,\mathbb{X},w\right)=-{\displaystyle \underset{p}{\sum }\log }\left(1-w\left(p\right)u^{l\left(p\right)}\right)={\displaystyle \underset{p}{\sum }{\displaystyle \underset{j=1}{\overset{\infty }{\sum }}\frac{1}{j}}}{\left(w\left(p\right)u^{l\left(p\right)}\right)}^j.$

对于素元 $p$ ，有 $l\left(p\right)$ 个本原路相对应，且长度均为 $l\left(p\right)$ ，可见

$\log \zeta \left(u,\mathbb{X},w\right)={\displaystyle \underset{P本原}{\sum }{\displaystyle \underset{j=1}{\overset{\infty }{\sum }}\frac{1}{l\left(P^j\right)}w}}\left(P^j\right)u^{l\left(P^j\right)}.$

由于任一闭约化路Q都可唯一表为本原路的次幂得

$\log \zeta \left(u,\mathbb{X},w\right)=\underset{Q闭约化}{{\displaystyle \sum }}\frac{1}{l\left(Q\right)}w\left(Q\right)u^{l\left(Q\right)}\triangleq \underset{n=1}{\overset{\infty }{{\displaystyle \sum }}}\frac{C_n}{n}{u}^n,$

其中 $C_n$ 为给定长度n，闭约化路权之和。

考虑半边邻接权矩阵W，可见

$C_n={\displaystyle \underset{h_j\in H\left(X\right)}{\sum }{W}_{h_1{h}_2}\cdots W_{h_n{h}_1}}={\displaystyle \underset{h\in H\left(X\right)}{\sum }{\left(W^n\right)}_{hh}}=tr{W}^n\text{.}$

因此有

$\log \zeta \left(u,\mathbb{X},w\right)=\underset{n=1}{\overset{\infty }{{\displaystyle \sum }}}\frac{tr{W}^n}{n}{u}^n=tr\underset{n=1}{\overset{\infty }{{\displaystyle \sum }}}\frac{{\left(Wu\right)}^n}{n}=tr\left(-\log \left(I_k-Wu\right)\right)=\log \det {\left(I_k-Wu\right)}^{-1}.$

综上，

$\zeta {\left(u,\mathbb{X},w\right)}^{-1}=\det \left(I_k-Wu\right)\text{.}$

3.3. 三项行列式公式

记有m条边，n个顶点，l个腿，且记半边数 $2m+l=k$ 。定义如下矩阵。

对角价矩阵Q为 $n\times n$ 矩阵，有

${\left(Q\right)}_{uv}={\delta }_{uv}val\left(v\right)\text{.}$

其中 $val\left(v\right)$ 为顶点关于根映射的原象个数，即顶点上半边个数。

邻接权和矩阵A为 $n\times n$ 矩阵，表示u到v的边权重之和，有

${\left(A\right)}_{uv}=\underset{\begin{array}{c}h\\ \text{s}\text{.t}\text{.}u=r\left(h\right)\\ 且v=r\left(\bar{h}\right)\end{array}}{{\displaystyle \sum }}{x}_h\text{.}$

对角负荷矩阵C为 $n\times n$ 矩阵表示顶点上群元素个数，如下：

${\left(C\right)}_{uv}={\delta }_{uv}c\left(v\right)\text{.}$

其中 $c\left(v\right)$ 为顶点负荷，有 $c\left(v\right)=\text{\#}\left(X_v\right)$ 。

下面给出边加权的群的边自由商图的Ihara Zeta函数的三项行列式公式。

定理2设 $\mathbb{X}=\left(X,X_v,w\right)$ 为有限边加权的边平凡的群图，其中有m条边，n个顶点，l条腿，且记半边数 $2m+l=k$ 。 $\mathbb{X}$ 的Ihara Zeta函数满足

$\zeta {\left(u,\mathbb{X},w\right)}^{-1}={\left(1-u^2\right)}^{m-n}{\left(1-u\right)}^l\det \left(I_n-CAu+\left(CQ-I_n\right)u^2\right)\text{.}$

证明：对半边排序，记 $h_{m+i}={\bar{h}}_i,\forall i\in \left\{1,\cdots ,m\right\}$ ，记 $h_{2m+j}=l_j,\forall j\in \left\{1,\cdots ,l\right\}$ 。

定义辅助矩阵如下：

定义 $n\times k$ 阶矩阵S为始矩阵，其中

${\left(S\right)}_{vh}=\{\begin{array}{ll}1,\hfill & v=r\left(h\right),\hfill \\ 0,\hfill & v\ne r\left(h\right)\text{.}\hfill \end{array}$

定义 $n\times k$ 阶矩阵T为终矩阵，其中

${\left(T\right)}_{vh}=\{\begin{array}{ll}1,\hfill & v=r\left(\bar{h}\right),\hfill \\ 0,\hfill & v\ne r\left(\bar{h}\right)\text{.}\hfill \end{array}$

定义 $k\times k$ 阶矩阵J为对合矩阵，其中

${\left(J\right)}_{h{h}^{\prime }}=\{\begin{array}{ll}1,\hfill & h^{\prime }=\bar{h},\hfill \\ 0,\hfill & h^{\prime }\ne \bar{h}\text{.}\hfill \end{array}$

定义 $k\times k$ 阶矩阵D为半边负荷矩阵，其中

${\left(D\right)}_{h{h}^{\prime }}={\delta }_{h{h}^{\prime }}c\left(r\left(h^{\prime }\right)\right)x_{h^{\prime }}\text{.}$

定义 $k\times k$ 阶矩阵L为半边权矩阵，其中

${\left(L\right)}_{h{h}^{\prime }}={\delta }_{h{h}^{\prime }}{x}_{h^{\prime }}\text{.}$

易证如下关系：

$\begin{array}{l}SJ=T,TJ=S,{\left(JL\right)}^{-1}=JL,{}^{t}J=J,J^2=I,\\ W+JL={}^{t}TSD,SD=CSL,SL{}^{t}T=A,S{}^{t}S=Q\text{.}\end{array}$

因此可知：

$CA=SD{}^{t}T,CQ=SD{L}^{-1}{}^{t}S\text{.}$

用以上关系式，证明三项行列式公式。由 $W+JL={}^{t}TSD$ ，知

$\begin{array}{c}\zeta {\left(u,\mathbb{X},w\right)}^{-1}=\det \left(I_k-Wu\right)=\det \left(I_k-\left({}^{t}TSD-JL\right)u\right)\\ =\det \left(\left(I_k+JLu\right)-{}^{t}T{\left(\left(1-u^2\right)I_n\right)}^{-1}SDu\left(1-u^2\right)\right)\text{.}\end{array}$

容易验证， $\det \left(D-C{A}^{-1}B\right)=\frac{\det \left(D\right)}{\det \left(A\right)}\det \left(A-B{D}^{-1}C\right)$ 。因此

$\zeta {\left(u,\mathbb{X},w\right)}^{-1}=\frac{\det \left(I_k+JLu\right)}{\det \left(\left(1-u^2\right)I_n\right)}\det \left(\left(1-u^2\right)I_n-SDu\left(1-u^2\right){\left(I_k+JLu\right)}^{-1}{}^{t}T\right).$

由 ${\left(JL\right)}^{-1}=JL$ ，易见 ${\left(I_k+JLu\right)}^{-1}=\frac{1}{1-u^2}\left(I_k-JLu\right)$ 。带入得

$\begin{array}{c}\zeta {\left(u,\mathbb{X},w\right)}^{-1}=\frac{\det \left(I_k+JLu\right)}{{\left(1-u^2\right)}^n}\det \left(\left(1-u^2\right)I_n-SDu\left(1-u^2\right)\frac{1}{1-u^2}\left(I_k-JLu\right){}^{t}T\right)\\ =\frac{\det \left(I_k+JLu\right)}{{\left(1-u^2\right)}^n}\det \left(\left(1-u^2\right)I_n-SD{}^{t}Tu+SDJL{}^{t}T{u}^2\right)\text{.}\end{array}$

由 $CA=SD{}^{t}T,J^2=I$ 知

$\zeta {\left(u,\mathbb{X},w\right)}^{-1}=\frac{\det \left(I_k+JLu\right)}{{\left(1-u^2\right)}^n}\det \left(\left(1-u^2\right)I_n-CAu+SDJLJJ{}^{t}T{u}^2\right)\text{.}$

由 $TJ=S,{}^{t}J=J$ 得

$\zeta {\left(u,\mathbb{X},w\right)}^{-1}=\frac{\det \left(I_k+JLu\right)}{{\left(1-u^2\right)}^n}\det \left(\left(1-u^2\right)I_n-CAu+SDJLJ{}^{t}S{u}^2\right)\text{.}$

由 ${\left(JL\right)}^{-1}=JL$ 得

$\zeta {\left(u,\mathbb{X},w\right)}^{-1}=\frac{\det \left(I_k+JLu\right)}{{\left(1-u^2\right)}^n}\det \left(\left(1-u^2\right)I_n-CAu+SD{L}^{-1}{}^{t}S{u}^2\right)\text{.}$

又 $CQ=SD{L}^{-1}{}^{t}S$ ，因此

$\begin{array}{c}\zeta {\left(u,\mathbb{X},w\right)}^{-1}=\frac{\det \left(I_k+JLu\right)}{{\left(1-u^2\right)}^n}\det \left(\left(1-u^2\right)I_n-CAu+CQ{u}^2\right)\\ =\frac{\det \left(I_k+JLu\right)}{{\left(1-u^2\right)}^n}\det \left(I_n-CAu+\left(CQ-I_n\right)u^2\right)\text{.}\end{array}$

考虑 $\det \left(I_k+JLu\right)$ 。

由半边的顺序，可记

$L=\left(\begin{array}{ccc}{L}_1& 0& 0\\ 0& L_1^{-1}& 0\\ 0& 0& L_2\end{array}\right),$

其中

$L_1=\left(\begin{array}{ccc}{x}_{h_1}& 0& 0\\ 0& \ddots & 0\\ 0& 0& x_{h_m}\end{array}\right),L_2=\left(\begin{array}{ccc}-1& 0& 0\\ 0& \ddots & 0\\ 0& 0& -1\end{array}\right)=-I_l\text{.}$

则

$I_k+JLu=\left(\begin{array}{ccc}{I}_m& L_1^{-1}u& 0\\ L_{1}u& I_m& 0\\ 0& 0& I_l\left(1-u\right)\end{array}\right),$

取行列式得

$\det \left(I_k+JLu\right)=\left|\begin{array}{cc}{I}_m& L_1^{-1}u\\ L_{1}u& I_m\end{array}\right|{\left(1-u\right)}^l={\left(1-u^2\right)}^m{\left(1-u\right)}^l\text{.}$

可见

$\zeta {\left(u,\mathbb{X},w\right)}^{-1}={\left(1-u^2\right)}^{m-n}{\left(1-u\right)}^l\det \left(I_n-CAu+\left(CQ-I_n\right)u^2\right)\text{.}$

基金项目

国家自然科学基金青年项目11901390。