Ehrhart 伸缩计数定理

把一张图形放大两倍，面积乘四，格点数却不恰好乘四：边界和原点也有贡献。若顶点坐标是有理数，边界还会周期性地经过格点。Ehrhart定理说明，这些误差不是任意波动，而由有限组多项式精确控制。

形式陈述

输入、有理分母与计数函数

设 $P\subset\mathbb R^d$ 为非空有理多胞形，仿射维数为 $r$ 。有理表示全部顶点坐标属于 $\mathbb Q$ ；多胞形有界，故每个伸缩只含有限多个标准格点。

取正整数 $q$ 使 $qP$ 的顶点全为整数。最小这样的 $q$ 称为 $P$ 的分母，等于所有顶点坐标既约分母的最小公倍数。对整数 $t\ge0$ 定义

L_P(t)=|tP\cap\mathbb Z^d|, \qquad tP=\{tx:x\in P\}.

Ehrhart定理断言：存在 $q$ 个有理系数多项式 $f_0,\ldots,f_{q-1}$ ，使

\boxed{L_P(qk+s)=f_s(k)\qquad (k\ge0,\ 0\le s<q).}

各 $f_s$ 的次数至多为 $r$ ，其中最大次数恰为 $r$ 。这样的函数称为准多项式；等价地， $L_P(t)=c_r(t)t^r+\cdots+c_0(t)$ ，各系数 $c_j$ 都是整数变量上的周期函数。

$q$ 是一个可用周期，最小周期可能更小；精确地说，最小周期整除 $q$ 。若顶点全为整数，可取 $q=1$ ，于是 $L_P$ 是次数 $r$ 的一个普通多项式。由于 $0P=\{0\}$ ，总有 $L_P(0)=1$ 。这里结论从零开始成立，不只是“大到一定程度后成立”。

若 $r=d$ ，每个剩余类以 $t$ 为变量时的最高项系数都等于普通体积 $\operatorname{vol}_d(P)$ 。低维有理多胞形可能在某些剩余类完全没有格点，不能把这一句不加修改地照搬。

一个有限的生成函数证书

证明还给出普通生成函数

E_P(z)=\sum_{t\ge0}L_P(t)z^t =\frac{H(z)}{(1-z^q)^{r+1}}, \qquad H(z)=\sum_{h=0}^{q(r+1)-1}a_hz^h, \tag{1}

其中 $a_h$ 为非负整数。分子由若干半开基本域的有限格点计数得到，不需要猜测多项式。

由 $(1-w)^{-r-1}=\sum_{j\ge0}\binom{j+r}{r}w^j$ 抽系数，可直接恢复

\boxed{f_s(k)=\sum_{j=0}^{r}a_{s+qj} \binom{k-j+r}{r}.} \tag{2}

这里二项式写成次数 $r$ 的多项式。若 $0\le k<j\le r$ ，其上参数在 $0,\ldots,r-1$ 之间，乘积本身为零；因此公式连最初几项也正确。

直觉

多放一个坐标，把放大次数变成高度

令 $v_i$ 为顶点，把它们改成整向量

u_i=(qv_i,q)\in\mathbb Z^{d+1}.

它们生成的闭圆锥 $C$ 在高度 $t>0$ 的截面恰为 $tP\times\{t\}$ ，高度零只有原点。于是数所有伸缩图形，等于逐层数同一个圆锥。

若一个小锥由 $r+1$ 条线性无关整向量生成，将每个坐标拆为非负整数部分和基本区间中的剩余部分，就把无限计数缩成有限计数。每沿任一生成元走一步，高度增加 $q$ ，因此出现 $r+1$ 个因子 $(1-z^q)^{-1}$ 。

切块时，边界必须只归一块

闭三角形可以共用一条边。若直接把各块的闭点数相加，这条边会重复；若把每块全部边界删掉，共用边又会漏掉。正确办法是选一个统一的微小移动方向，让共享边界上的每一点只归给移动后进入的那一块。

这产生的块通常是半开的：有些面保留，有些面删除。半开块是计数的分工方式，不等于原多胞形的内部；下一页的互反正要利用两种不同边界规则之间的关系。

例子与边界

六个剩余类，而非一个普通多项式

取

P=\{(x,y):x,y\ge0,\ 2x+3y\le1\}.

顶点为 $(0,0),(1/2,0),(0,1/3)$ ，分母六。对固定 $t$ ，加入整数松弛量 $w=t-2x-3y\ge0$ ，就有

E_P(z)=\frac1{(1-z)(1-z^2)(1-z^3)}.

统一分母得

H(z)=(1+z+\cdots+z^5)(1+z^2+z^4)(1+z^3), \qquad E_P(z)=\frac{H(z)}{(1-z^6)^3}.

将 $t=6k+s$ 代入式(2)，或直接计算

L_P(t)=\sum_{y=0}^{\lfloor t/3\rfloor} \left(\left\lfloor\frac{t-3y}{2}\right\rfloor+1\right),

得到

\boxed{L_P(6k+s)=3k^2+(s+3)k+c_s,\quad (c_0,\ldots,c_5)=(1,1,2,3,4,5).} \tag{3}

例如 $L_P(6)=7,L_P(7)=8,L_P(8)=10$ 。以原变量 $t$ 写时，二次项都是 $t^2/12$ ，一次项都是 $t/2$ ，常数项依次为

1,\quad\frac5{12},\quad\frac23,\quad\frac34, \quad\frac23,\quad\frac5{12}.

这个周期常数只有每六步一次取值一，故最小周期确为六；面积为 $1/12$ 也与首项吻合。

分母二，也可能完全没有周期振荡

取 $Q=\operatorname{conv}\{(0,0),(2,0),(0,1/2)\}$ 。它的分母为二，但

L_Q(t)=\sum_{y=0}^{\lfloor t/2\rfloor}(2t-4y+1) =\frac{(t+1)(t+2)}2.

若 $t=2k$ ，和为 $(k+1)(2k+1)$ ；若 $t=2k+1$ ，和为 $(k+1)(2k+3)$ ，两者都化为上面同一个多项式。这称为周期折叠，说明定理只能保证最小周期整除分母。

低维有理切片会空掉整个剩余类

在 $\mathbb R^2$ 中取竖线段

S=\{(1/2,y):0\le y\le1\}.

它的仿射维数为一，然而

L_S(t)=\begin{cases}t+1,&t\text{ 偶},\\0,&t\text{ 奇}.\end{cases}

奇数伸缩时，整条线仍在半整数横坐标上。这不违背次数为一的结论：它指各剩余类次数的最大值。若改成零维点 $\{1/2\}\subset\mathbb R$ ，计数则为偶数一、奇数零，次数为零。

有理性、整数参数与有界性各有用途

对无理区间 $[0,\sqrt2]$ ，计数为 $\lfloor t\sqrt2\rfloor+1$ ，不可能有有限准周期。否则在 $t=qk$ 这一列上，它因线性增长只能是一阶多项式；连续整数 $k$ 处的差是整数，斜率必须为整数，但增长极限给斜率 $q\sqrt2$ ，矛盾。

即使顶点为整数，也不能把多项式在任意实数 $t$ 处的值当成点数。例如 $P=[0,1]$ 的公式为 $t+1$ ，在 $t=1/2$ 处给 $3/2$ ，真实格点数为一。无界多面体则可能有无穷多格点，不能使用这里的有限计数生成函数。空集的计数恒零，应单独处理，不满足本页非空对象的常数项一。

推论与应用

第一步：只用原顶点做三角剖分

在 $P$ 的 $r$ 维仿射包内工作。若它已经是单纯形，无须分割。否则给每个顶点 $v_i$ 选一个额外高度 $h_i$ ，考察 $(v_i,h_i)$ 的凸包。对每个由 $r+1$ 个仿射无关原顶点决定的仿射图像，要求其余抬起的顶点不落在同一图像上。这只排除有限个关于 $h_i$ 的真线性方程，因而可以选择满足要求的有理高度。

在每条竖直线上取抬起凸包的最低点，得到原 $P$ 上单值的分片仿射下表面。每个最高维下表面片恰有 $r+1$ 个顶点，否则违反高度选择；其投影因而是一个 $r$ 维单纯形。所有投影覆盖 $P$ ，两片的交来自下表面的公共面，不会在内部交叠。这给出不增加新顶点的三角剖分。

将每个单纯形同原点作锥，得到 $C$ 的有限单纯锥分割。每个锥的 $r+1$ 个生成元都选为 $(qv_i,q)$ ，所以高度统一为 $q$ 。

第二步：用同一个方向分配所有共享边界

在 $C$ 的相对内部选 $w$ ，使它不落在任何小锥的facet所张成的超平面内。因为要避开的超平面有限，这样的 $w$ 存在。对任意 $x\in C$ ，充分小的 $\varepsilon>0$ 使 $x+\varepsilon w$ 落入唯一一个小锥的相对内部；把 $x$ 分给该块。这是对每个点取足够小的扰动，不是声称一个固定步长对所有点同时有效。

在某块的基 $u_0,\ldots,u_r$ 中写

x=\sum\lambda_i u_i,\qquad w=\sum\beta_i u_i.

所有 $\beta_i\ne0$ 。该块对 $x$ 的精确条件是

\lambda_i\ge0\quad(\beta_i>0),\qquad \lambda_i>0\quad(\beta_i<0). \tag{4}

这些半开块两两不交，合起来恰为闭锥 $C$ 。因为 $w$ 的高度为正而每个 $u_i$ 高度为 $q$ ，至少一个 $\beta_i$ 为正；因此每块至少有一个非严格坐标。

第三步：把半开块分成有限基本域与非负整数步

对式(4)中非严格坐标取基本区间 $[0,1)$ ，对严格坐标取 $(0,1]$ 。分别用下取整、上取整减一，便把每个系数唯一写成

\lambda_i=n_i+\rho_i,\qquad n_i\in\mathbb Z_{\ge0},

其中 $\rho_i$ 位于相应基本区间。若 $x$ 为格点，则

p=x-\sum n_i u_i=\sum\rho_i u_i

也为格点。基本平行多面体有界，所以其中这样的 $p$ 有限；反过来，每个基本域格点加上任意非负整数步，都得到该半开块的唯一格点。

基本域点的整数高度满足 $0\le h<q(r+1)$ ：各系数至多一，且至少一个区间不含一。于是该块的生成函数为

\frac{\sum_p z^{h(p)}}{(1-z^q)^{r+1}}.

对不交的块相加，得到式(1)及非负整数分子，再由式(2)证明全部非负整数参数上的准多项式性。

次数、体积与插值能证明到哪里

$qP$ 含一个由整数顶点 $v_0,\ldots,v_r$ 构成的 $r$ 维单纯形。对所有 $n_i\ge0$ 、 $\sum_{i=1}^r n_i\le k$ ，点

kv_0+\sum_{i=1}^r n_i(v_i-v_0)

互异且位于 $kqP$ ，故 $L_P(qk)\ge\binom{k+r}{r}$ 。另一方面，选择在仿射包上单射的 $r$ 个环境坐标，伸缩后的每个坐标范围为 $O(k)$ ，所以点数为 $O(k^r)$ 。结合已证次数上界，最大次数恰为 $r$ 。

全维时，以整数点为角点的单位立方体比较 $tP$ 体积与格点数。两者的差只来自与边界相交的立方体；它们落在有限个facet的固定厚度邻域内，数量为 $O(t^{d-1})$ 。因此

L_P(t)=\operatorname{vol}_d(P)t^d+O(t^{d-1}),

并迫使所有剩余类的最高项系数相同。二维整数多边形还可直接调用Pick公式，得到面积、半边界和常数三项。

次数和周期已被证明后，每个剩余类取 $r+1$ 个值，就唯一确定其多项式。先看几个数据再拟合，却不能独自证明这些次数与周期承诺。分母可能很大，三角剖分和基本域格点也可能很多；本页的有限构造不声称在任意维数下具有多项式位复杂度。

最小周期整除 $q$ 也可直接检查。将剩余类公式改写为原变量 $t$ 的幂次式后，各周期系数由计数函数唯一决定：比较两个周期的公倍数剩余类，两个多项式在无限多点相同，其系数便相同。若这些系数同时以 $p$ 和 $q$ 为周期，Bézout整数线性组合说明它们也以 $\gcd(p,q)$ 为周期；取 $p$ 为最小周期，便得 $p\mid q$ 。

分子的非负性，不等于普通系数都非负

对 $m\ge1$ ，Reeve四面体 $R_m=\operatorname{conv}\{(0,0,0),(1,0,0),(0,1,0),(1,1,m)\}$ 的四个同高生成元为 $(v_i,1)$ 。其半开基本域中的整数点为原点，以及

(1,1,j,2),\qquad 1\le j<m.

具体地，顶端系数为 $j/m$ ，两个底面方向系数均为 $1-j/m$ ，原点方向系数为 $j/m$ ；高度总和为二。这些点列尽了基本域：第三坐标确定 $j$ ，前两坐标和高度再唯一确定其余系数。

所以

E_{R_m}(z)=\frac{1+(m-1)z^2}{(1-z)^4},

L_{R_m}(t)=\binom{t+3}{3}+(m-1)\binom{t+1}{3} =\frac m6t^3+t^2+\frac{12-m}{6}t+1.

当 $m>12$ 时一次项系数为负，但全部非负整数 $t$ 的真实点数仍然非负。生成函数分子、二项式基系数与普通幂次系数是不同的表示。

Hilbert函数也可能因加权分次保留周期，但一般Hilbert多项式只保证最终相等；本页的小参数精确性来自基本域高度的严格上界。内部互反将进一步解释同一准多项式在负整数处的含义。完整复算见格点计数综合任务。

参考资料

Matthias Beck、Sinai Robins，Computing the Continuous Discretely，第二版更新稿，2020-06-19，§3.1 Theorem3.1，pp.59–62；§3.4 Theorem3.8，pp.68–70；§3.8 Theorem3.23，pp.80–81：三角剖分、整数多项式及有理准多项式。
Matthias Beck、Raman Sanyal，Combinatorial Reciprocity Theorems，2018-10-04稿，Proposition4.5.1，pp.120–122；Theorems4.7.2、4.8.1，pp.129、131–133；§5.3 Lemma5.3.4及Corollary5.3.5，pp.166–167：周期系数、半开基本域与边界分配。
Matthias Beck、Frank Sottile，Irrational proofs for three theorems of Stanley，2005，Theorem2及§3，pp.2、5–6：有理Ehrhart级数分子的非负性。本文用同一一般方向的半开块描述，完整写出式(2)的小参数检查，不依赖数值拟合。

形式陈述 ​

输入、有理分母与计数函数 ​

一个有限的生成函数证书 ​

多放一个坐标，把放大次数变成高度 ​

切块时，边界必须只归一块 ​

六个剩余类，而非一个普通多项式 ​

分母二，也可能完全没有周期振荡 ​

低维有理切片会空掉整个剩余类 ​

有理性、整数参数与有界性各有用途 ​

第一步：只用原顶点做三角剖分 ​

第二步：用同一个方向分配所有共享边界 ​

第三步：把半开块分成有限基本域与非负整数步 ​

次数、体积与插值能证明到哪里 ​

分子的非负性，不等于普通系数都非负 ​

反向链接