前两天去听了一下搞代数几何的dino lorenzini在交大的两场讲座（“”,“”），在此将笔记整理一下。$\newcommand
\diag{\mathrm{diag}} \newcommand\z{\mathbb{z}} \newcommand\pic{\mathrm{pic}}
\newcommand\img{\mathrm{im}} \newcommand\di{\mathrm{div}}$
首先定义一些记号：$g$是一个连通无向图，有$n$个顶点（记为$v_1,v_2,\cdots,v_n$），$m$条边,且无自循环。$a$为$g$的领接矩阵，即为$(a_{ij})$，其中$a_{ij}$为$v_i$与$v_j$($i\not=
j$)之间边的个数，$a_{ii}=0$。图的laplacian是$d-a$,其中$d$是对角阵，$\mathrm{diag}(d_1,d_2,\cdots,d_n)$,其中$d_i$为$a_i$的度，即连接到$v_i$的边的个数。
1.图的laplacian以及smith标准型
对于一个图的laplacian来说，在代数图论中研究的大多是它的特征值。而在矩阵理论中，除了特征值以外还有其他一些不变量，比如说smith标准型。
定义1 （） 整系数矩阵$m$的smith标准型是$\mathrm{snf}=\mathrm{diag}(\delta_1,\delta_2\cdots,\delta_n)$,其中$\delta_1\cdots\delta_i=\delta_i$,其中$\delta_i$是$m$的所有$i$阶子式的最大公因数。
注意到它同样有一个等价定义，也就是说，$m\times n$阶矩阵$m$的smith标准型是$smt$,其中$s,t$分别为$m\times
m$以及$n\times
n$阶的矩阵。使得$smt$为对角阵$\mathrm{diag}(\delta_1,\delta_2\cdots,\delta_n)$,使得$\delta_1|\delta_2|\cdots
|\delta_n$,其中$\delta_i\in\mathbb{z}$。同样我们可以注意到，当$\det{m}=0$的时候，$\delta_n=0$。
我们知道，对于laplacian矩阵$m$的特征值$\lambda_1,\cdots,\lambda_n$,可以使$\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n=0$。而图的生成树的个数不是别的，就是\[\#(\mbox{生成树})=\frac{1}{n}\lambda_1\cdots\lambda_{n-1}.\]这是代数图论中经典的kirchhoff定理。通过smith标准型的第一个定义，我们同样可以容易知道\[\#(\mbox{生成树})=\delta_1\cdots\delta_{n-1}.\]（通过对kirchhoff定理的证明可以看出，图的生成树个数正是laplacian的任意一个$n-1$阶子式的行列式绝对值）
smith标准型与特征值的联系不仅限于此，如果我们定义$\mu$为相异特征值的乘积，那么如下定理成立
定理2 （smith标准型与特征值联系） $\mu\in\mathbb{z}$ $n|\mu$ $\delta_{n-1}|\mu$,但是一般来说，$\delta_{n-1}\nmid \frac{\mu}{n}$
定理的证明可见lorenzini的。
2.算术图(arithmetical graph)以及picard群
每一个图，我们都有一个laplacian矩阵$m$。而我们又知道，$m(1,1,\cdots,1)‘=0$,所以我们可否将laplacian的概念推广呢？这样就引出了“算术图”的想法。
定义3 (算术图) 算术图是三元组$(g,m,r)$使得以下成立： $g$为图 $m=c-a$,其中$a$为领接矩阵，$c$为系数为正整数的对角阵,记为$\mathrm{diag}(c_1,c_2,\cdots,c_n)$。 $r=(r_1,r_2,\cdots,r_n)‘$,其中$r_i>0$,且同有$r_i\in\mathbb{z}$，且$\gcd{(r_1,\cdots,r_n)}=1$。 $mr=0$
一个简单的例子是extended dynkin diagram赋予如下数字：
其中黑色数字代表了向量$r$赋予的值，而红色的数字则是对角阵$m$赋予的值，通过计算很容易可以验证$mr=0$如下
有了算术图的定义，我们可以定义它的不变量，即picard群。这个群来源于代数几何的想法。
定义4 （picard群）整数群$\mathbb{z}$模去$m$的像$\mathbb{z}^n/\mathrm{im}(m)$称为算术图的picard群,记为$\mathrm{pic}(g)$。同时我们定义degree map为$\deg:\mathbb{z}^n/\mathrm{im}(m)\to \mathbb{z}$,使得$(s_1,s_2,\cdots,s_n)\mapsto\sum_{i=1}^n r_i s_i$,其中$r_i$即为算术图中$r$的元素。
有了这一定义，我们就可以得到有限阿贝尔群$\phi_m=\ker(\deg)$。可以证明，如果$\diag(\delta_1,\delta_2,\cdots,\delta_{n-1},0)$为smith标准型，就有\[\phi_m\cong
\mathbb{z}/\delta_1\mathbb{z} \times
\mathbb{z}/\delta_2\mathbb{z}\times\cdots\times
\mathbb{z}/\delta_{n-1}\mathbb{z}.\]
注记：由此可以看出$\phi_m$是循环群当且仅当$\mathrm{snf}=\diag(1,\cdots,1,\delta_{n-1},0)$。
于是特别地，考虑$m$为$g$的laplacian，如果$g$的生成树的个数无平方因子，自然就有$\phi_m$是循环群。而$\phi_m$是循环群的$g$占了很大比例。以下是两个结论：
给定图$g$,存在同构的图$g‘$,由$g$的细分（至多$m-n$条边）给出，且$\phi_{m‘}$是循环群。
对于$n$点的erdos-renyi随机图，当$n\to\infty$时，
(a) $|\phi_m|$无平方因子的概率约为$48.2\%$
(b)$\phi_m$是循环群的概率约为$79.3\%$
3.算术图的不变量
(1)第一贝蒂数：$\beta(g)=m-n+1$,相当于图中不相关的“圈”的个数，就是将所有的边个数减去生成树的长度即为不相关圈的个数。
(2)亏格： $g_0(g,m,r)$，定义为\[2g_0(g)-2=\sum_{i=1}^n
r_i(d_i-2).\]注意到这样一个亏格和我们通常所说的图的亏格（可嵌入多少亏格的曲面使得边不相交）不一样。因为$k_{3,3}$和$k_5$都有图亏格$1$，但是简单计算就可发现$g_0(k_{3,3})=4$，$g_0(k_5)=6$。
简单计算可以发现，\[2g_0(g)-2\beta(g)=\sum_{i=1}^n(r_i-1)(d_i-1).\]故而有如下定理。图的亏格的几何意义可见下定理链接中的引文[7]与[8]。
定理5(,1989) $g_0(g)$为整数 $g_0(g)\ge \beta(g)\ge 0$
(3)$g$-数： $g$-数的定义如下。我们知道$\deg:\pic(g)=\z^n/\img(m)\to
\z$将$\phi_m$映射至$0$,那么$g$-数是最小的整数，满足
对于任意$\deg[d]\ge g$的代表元$[d]\in\pic(g)$,存在$v\in
\img(m)$使得$d+v$在第一卦限（也即$d+v$的各个坐标都大于$0$）
存在$\deg[d]=g-1$使得$\forall v\in\img(m)$,都有$d+v$不可能在第一卦限。
这样的$g$存在吗？存在性已经，而以下的标志性的定理找出了一般图的解：
定理6(, 2006) 若$g$为一般的图，且$r=(1,1\cdots,1)‘$,那么$g=\beta(g)$。
而这一定理同样也关乎图的黎曼-罗赫结构。两人首次提出了图上的黎曼-罗赫结构，而lorenzini则进一步提出了如下定理：
定理7（,2011）如果$g(g)=g_0(g)$,那么图上就有黎曼-罗赫结构。
黎曼-罗赫结构将在下一节提到。这节最后再给出一些对不变量关系的估计。
定理8 令$(g,m,r)$为算术树（也即算术图中的$g$为树），那么 $|\phi_m|=\prod_{i=1}^n r_i^{d_i-2} \in \mathbb{n}$ $|\phi_m|\le 4^{g_0(g)}$ 若$p$为整除$|\phi_g|$的素数，那么$p\le 2g_0(g)+1$
通过第二个等式，且我们知道$g\le g_0$，那么是否有$|\phi_m|\le
4^g$呢？现在还不得而知。对于$\phi_g$这个群生成元的估计。在普通的图$g$中，$\phi_g$可以被$\beta(g)$个元素生成。而对于一般的算术图的结果如下：
定理9 令$(g,m,r)$为无重边的算术图，且假定对于某个$i$有$r_i=1$。那么\[\mathrm{snf}(m)=\diag(\delta_1,\cdots,\delta_{n-1-\beta},\delta_{n-\beta},\cdots,\delta_{n-1},0)\]其中$\delta_{n-1-\beta}=\delta_1\cdots\delta_{n-1-\beta}$有$\delta_{n-1-\beta}|\prod_{i=1}^n r_i^{d_i-2}$
4.图上的黎曼-罗赫定理与双变量zeta函数(two-variable zeta function)
动机是来自于代数几何的黎曼罗赫定理。$x$是$\mathbb{c}$上的射影曲线（即$\mathbb{c}p^2$中齐次函数$f(x,y,z)$的解）。$f$是定义在射影曲线上的亚纯函数，且有有限个零点与极点。那么定义$f$的$\di$为
\[\di(f)=\sum_{p\in x}m(p)
p\],其中$m(p)$为重数。在$m(p)>0$为零点，$m(p)<0$为极点。而一个重要的结论是，零点与极点的个数相同！也即$\sum_p
m(p)=0$。
而类似地，我们可以定义“除子”(divisor)$d$为$d=\sum_p a_p
p$,是为关于$p$的形式和，其中$a_p\in\z$且为有限和。定义度函数\[\deg(d)=\sum_p a_p.\]从定义可以看出$\deg\circ
\di=0$。同时对于任意的除子$d$,我们可以赋予它另外一个整数$h^0(d)$,定义为\[h^0(d)=\dim_{\mathbb{c}}
h^0(x,\mathcal{o}_d),\mathcal{o}_d=\{f|f\mbox{只在}a_p\not=0\mbox{的地方有极点，且}m(p)\ge-a_p\}\]是为$\mathcal{o}_d$层的上同调群的维数。
对于这样的结构，定义$[d]$为$d$的等价类，即为$\{d‘|\exists
f,d‘=d+\di(f)\}$。那么就有经典的黎曼-罗赫定理(riemann-roch)如下
定理10(黎曼-罗赫)存在典范类(canonical class)$[k]$使得对于任意$d$都有\[h^0(d)=\deg(d)+1-g+h^0(k-d)\]
而在代数几何中，$[d]$的类构成了维数$g$的代数簇上的所有点，称为picard簇$\pic(x)$。而$[d]$满足$\deg(d)=0$的子类被称为曲线$x$的jacobian。
对应的图论中来，注意到前面我们其实已经提到了和代数几何这些结果相仿的定义，比如picard群，$\phi_m$等等。前面一直没有说明的$\phi_m$有了它的名字，称为雅可比簇(jacobian
variety)，它的阶记为$g$的生成树的个数。而典范类$[k]$定义为$[(d_1-2,\cdots,d_n-2)]$。
baker与norine首次给出了图上的黎曼-罗赫定理。他们赋予每个除子$d$(或者说picard群的元素)的$h^0(d)$，且证明了图上的黎曼-罗赫定理\[h^0(d)=\deg(d)+1-\beta(g)+h^0(k-d)\]对于$h^0(d)$的定义将在之后提到。
如果我们有了$h^0:\pic(g)\to
\z$,那么我们就可以定义一个zeta函数\[z_h(g,u,t)=\sum_{[d]\in\pic(g)}\frac{u^{h^0(d)}-1}{u-1}t^{\deg(d)}.\]而一个稍微变化的定义是\[w_h(g,x,y)=\sum_{[d]\in\pic(g)}x^{h^0(g)}y^{h^0(k-d)}.\]这个zeta函数的定理动机来自与有限域上的曲线上的zeta函数：令$p$为素数$\z/p\z=\mathbb{f}_p\le
\mathbb{f}_{p^s}$。令$x/\mathbb{f}_p$为光滑射影曲线（比如$\mathbb{p}^2$上的齐次$f(x,y,z)=0$），那么令$a_s$为在系数为$\mathbb{f}_{p^s}$中时，曲线方程解的个数。那么有限域中与黎曼zeta相对应的zeta函数为：\[z(x/\mathbb{f}_p,t)=\exp\left(\sum_{s=1}^\infty
a_s\frac{t^s}s
\right)=\sum_{[d]\in\pic(x)}\frac{p^{h(d)}-1}{p-1}t^{\deg(d)}\]与我们这里的zeta函数类似。这样的zeta函数同样又给出了图的一个不变量。
最后给出$h^0(d)$的定义以及一些性质（等价意思是相差一个$\img(m)$的元素）：
定义11（$h^0(d)$）定义$e\in \z^n$是“有效的”当$e\ge 0$,也就是$e$的每个坐标都大于等于$0$。如果$\deg(d)<0$，则令$h^0(d)=0$。如果$\deg(d)\ge 0$,定义$h^0(d)$为\[h^0(d)=\min\{\deg(e)|e\ge 0\mbox{且}d-e\mbox{不等价于一个有效的元素}\}\]
注意到这儿的定义其实类似前面我们所说的$g-$数。不过$g-$数相当于一个全局的不变量。于是我们有如下的性质：
$h^0(d)\ge 0$这个通过定义显然
若$d$不等价与一个有效的元素，那么$h^0(d)=0$,由于定义中集合包含了$e=0$。
$h^0(d)\le \deg(d)+1$,更进一步，只可能在如下图的区域内有点
我曾经问在$\deg(d)$不变的时候是否能够变量区域中竖线交的所有点，不过还没有开始计算。
若$\deg(d)\ge 2\beta(g)-1$,那么$h^0(d)=\deg(d)+1-\beta(g)$
对于不变量zeta函数，我们同样也有一些比较好的性质，定理的证明都可以在[3]中找到。
定理12 有理性，\[z_h(g,u,t)=\frac{f(u,t)}{(1-t)(1-ut)},\]其中$f(u,t)\in\z[u,t]$,有形式\[f(u,t)=1+c_1(u)t+c_2(u)t^2+\cdots+c_g(u)t^g+uc_{g-1}(u)t^{g+1}+u^2 c_{g-2}(u)t^{g+2}+u^g t^{2g}.\] $f(u,t)$在$\mathbb{c}[u,t]$中不可约。 $f(1,u)=\#g\mbox{的生成树}$。 \[z\left(u,\frac{1}{ut}\right)=(ut^2)^{1-g}z(u,t)\] 若$g$为树，则$z(g,u,t)=\frac{1}{(1-t)(1-ut)}$
最后值得注意的一点是，zeta函数，tutte多项式，smith标准型，特征值这些不变量似乎是相互无关的！可见julian clancy、timothy
leake与sam payne最近的。
ps：对于计算$h^0$,baker博客给出过一个，可供参考
拓展阅读(定理的证明大多来自这几篇)：
[1]"" by dino lorenzini,1989
[2]"" by matthew baker, serguei
norine,2006
[3]""by dino
lorenzini,2011