第 5 章：半线性集合、格点与多面体

直觉

Presburger 公式用等式、不等式、同余、布尔连接词和量词描述整数点。半线性表示则换一种方式：从有限多个基点出发，把有限多个固定周期向量分别重复非负整数次，再对有限多个这样的集合取并。

这两种语言揭示了同一个关键结构：Presburger 可定义集合可以有非凸分支和无限重复的周期图样，但这种重复由有限数据生成。它远比“单个凸多面体的全部整数点”丰富，又不像含变量乘法的任意整数集合那样失去周期控制。

本章要特别分清四类对象：

1. 连续空间 $\mathbb R^d$ 中的单个有理凸多面体 $P$；
2. 该多面体的整数点集 $P\cap\mathbb Z^d$；
3. 有限并 $\bigcup_r(P_r\cap\mathbb Z^d)$；
4. 一般 Presburger 可定义集合，也即适当定义下的半线性集合。

取整数点后的后三类之间有包含关系，但它们不是同一个概念；连续的 $P$ 不应塞进这条离散对象的包含链。尤其是，同余能在无限范围内周期性地挖洞，普通线性不等式的有限并一般做不到这一点。

形式定义

线性集与半线性集

本节先在非负整数域上工作，并约定

$$ \mathbb N=\{0,1,2,\ldots\}. $$

给定基向量 $b\in\mathbb N^d$ 与周期向量 $p_1,\ldots,p_k\in\mathbb N^d$，线性集定义为

$$ L(b;p_1,\ldots,p_k) =\left\{b+n_1p_1+\cdots+n_kp_k\mid n_1,\ldots,n_k\in\mathbb N\right\}. $$

这里“线性”是半群意义的术语，不是线性代数中的子空间：系数只能取非负整数，集合有一个基点，也不要求对加法逆元封闭。若 $k=0$，约定 $L(b;)=\{b\}$。

有限多个线性集的并称为半线性集：

$$ S=\bigcup_{r=1}^{s}L(b_r;p_{r1},\ldots,p_{rk_r}), \qquad s<\infty. $$

“有限”限制的是基点和周期生成元的描述数量，不是集合中点的数量。一个线性集通常已经是无限的。

有理凸多面体及其整数点

本教程把有理凸多面体写成

$$ P=\{x\in\mathbb R^d\mid Ax\le b\}, \qquad A\in\mathbb Q^{m\times d},\ b\in\mathbb Q^m. $$

这里沿用 polyhedral-model 文献中的宽泛用法，允许 $P$ 无界；若强调有界，则称有理凸多胞体（polytope）。凸性意味着任意 $x,y\in P$ 与 $0\le\lambda\le1$ 都满足 $\lambda x+(1-\lambda)y\in P$。

$P$ 是连续对象，循环实例对应的离散对象是

$$ P_{\mathbb Z}=P\cap\mathbb Z^d. $$

清除有理不等式的分母后，$P_{\mathbb Z}$ 可由整数系数线性不等式定义，因此是 Presburger 可定义集合。有限并

$$ \bigcup_{r=1}^{s}(P_r\cap\mathbb Z^d) $$

也因有限析取而 Presburger 可定义。本章把它简称为“有限并整数多面体点集”；这不是说并集本身仍是单个凸多面体，也不是说它已经覆盖所有 Presburger 集合。

还要区分整数点集与整数凸包：

$$ P\cap\mathbb Z^d \quad\text{是离散点集，而}\quad \operatorname{conv}(P\cap\mathbb Z^d) \quad\text{是连续凸集}. $$

即使后者恰好等于 $P$，两者仍因所在对象类别不同而不能互换。

从周期生成元读出集合

一维周期集合

非负偶数集合是

$$ E=L(0;2)=\{2n\mid n\in\mathbb N\}. $$

所有模 3 余 1 的非负整数是

$$ C=L(1;3)=\{1+3n\mid n\in\mathbb N\}. $$

两者的并

$$ S=L(0;2)\cup L(1;3) $$

是半线性的。它可以写成 Presburger 析取

$$ x\ge0\land\bigl(x\equiv0\pmod2\lor x\equiv1\pmod3\bigr). $$

前几个点是

$$ 0,1,2,4,6,7,8,10,12,13,14,\ldots $$

这不是一个连续区间的整数点：3、5、9、11 等位置形成由两个模条件叠加产生的周期孔洞。

二维格点射线与格点锥

取基点 $b=(1,2)$ 和周期向量 $p=(2,1)$，则

$$ L((1,2);(2,1)) =\{(1+2n,2+n)\mid n\in\mathbb N\} $$

是一条从 $(1,2)$ 出发、沿 $(2,1)$ 方向前进的离散格点射线。它满足线性等式

$$ x-2y=-3 $$

以及 $y\ge2$，同时只取射线上的整数点。

再加入周期 $q=(1,3)$，得到

$$ L((1,2);(2,1),(1,3)) =\{(1+2n_1+n_2,\ 2+n_1+3n_2)\mid n_1,n_2\in\mathbb N\}. $$

这是由两个离散射线方向生成的平移格点半群。它位于相应实锥内，但不应未经证明就等同于该实锥的所有整数点：生成元可能只覆盖其中某些剩余类，形成格点孔洞。

三角域：多面体整数点也是 Presburger 集合

参数上下文 $C(N):N\ge0$ 下，

$$ T_N=\{(i,j)\in\mathbb Z^2\mid0\le i\le j<N\} $$

在每个固定 $N\ge1$ 时是有理凸多面体

$$ P_N=\{(x,y)\in\mathbb R^2\mid0\le x\le y\le N-1\} $$

的整数点集 $P_N\cap\mathbb Z^2$。对固定 $N$，它是有限集，因而当然半线性：最直接的表示是把每个点作为一个零周期线性集。这个表示只证明每个纤维的存在性，并不一定是适合计算的紧凑表示。

若把参数也作为坐标，整个非空参数化族其实有一个统一线性表示：

$$ \{(N,i,j)\in\mathbb N^3\mid N\ge1\land0\le i\le j<N\} =L\bigl((1,0,0);(1,1,1),(1,0,1),(1,0,0)\bigr), $$

也就是

$$ (N,i,j)=(1,0,0)+a(1,1,1)+b(1,0,1)+c(1,0,0), \qquad a,b,c\in\mathbb N. $$

正向取 $a=i$、$b=j-i$、$c=N-1-j$：三个系数非负，代回即得该等式。反向展开则有

$$ i=a,\qquad j=a+b,\qquad N=1+a+b+c, $$

所以 $N\ge1$ 且 $0\le i\le j<N$。因此这不是只对每个固定 $N$ 逐点列举的表示。$N=0$ 时原定义要求 $0\le i\le j<0$，故该纤维为空；上式第一坐标恒至少为 $1$，也恰好不产生 $N=0$ 的点。

若再要求 $i\equiv j\pmod2$，得到的集合仍是 Presburger/半线性集合，但不再是整个 $P_N\cap\mathbb Z^2$；它在同一个三角区域中按奇偶类选择格点。参数化且无界的类似约束会持续产生周期孔洞。

Presburger 可定义集与半线性集的等价

一手结论直接位于 $\mathbb N^d$

Ginsburg–Spanier 的原始结论应按其直接论域和语法陈述。该文第 3–4 页令论域为 $\mathbb N$，把原子式限制为两边均为非负整数系数线性组合的等式

$$ t_0+\sum_r t_rx_r=t'_0+\sum_r t'_rx_r, \qquad t_0,t'_0,t_r,t'_r\in\mathbb N, $$

再闭包于 $\land$、$\lor$、$\neg$ 和存在量词。作者的脚注说明：这严格说是 modified Presburger formulas，原始 Presburger formulas 的论域是全体整数。在这个 modified 语法下，他们的 Theorem 1.3 说：$\mathbb N^d$ 上的 Presburger 集合与半线性集合恰好相同，且两种描述可有效互算。参见 Ginsburg 与 Spanier (1966), Semigroups, Presburger Formulas, and Languages（DOI）。

本教程第 2 章的自然数版只是更方便书写的等表达扩展，而不是未经定义地换用另一个定理。对该章公式在 $\mathbb N$ 上逐项整理即可回到上述语法：

• 任意整数系数等式把负系数和负常数移到另一边，成为两边非负系数的等式；反向包含显然成立。
• 不等式 $s\le t$ 可写成 $\exists q\in\mathbb N:\ s+q=t$，再按上一项移项。严格序是整数上的缩写，也可先改写为 $s+1\le t$。
• 固定模数同余 $s\equiv t\pmod m$ 可写成 $\exists q_+,q_-\in\mathbb N:\ s+m q_+=t+m q_-$，其中 $m>0$ 固定；这避免把可能为负的商误当作自然数变量。
• 全称量词是 $\forall x\,\varphi\equiv\neg\exists x\,\neg\varphi$，其余布尔连接词已经在原语法中。

所以只有在量词和赋值均限制到 $\mathbb N$ 时，才可把本教程的等式、序、不等式、全称量词和固定同余桥接为 Ginsburg–Spanier 的 modified 语法；一般变量乘变量仍不在其中。

这条定理不是“任意整数集合都半线性”，也不是“半线性集等于单个凸多面体”。它说的是特定逻辑可定义性与有限个基点/周期生成元表示之间的等价，而且原文直接工作的坐标域是 $\mathbb N^d$，不是未经说明的 $\mathbb Z^d$。

从两个方向看，等价的直觉是：

• 一个线性集可用存在变量 $n_r\ge0$ 和等式 $x=b+\sum_rn_rp_r$ 定义，有限并对应有限析取；
• 反方向更深：任意允许量词和布尔组合的 modified Presburger 公式，最终仍能分解为有限个带周期生成元的线性集。

第二点是定理内容，不能用几个例子代替证明。

从 $\mathbb N^d$ 搬运到 $\mathbb Z^d$：显式差编码

要得到整数坐标版本，必须另做编码。对每个 $z_\ell\in\mathbb Z$，引入

$$ u_\ell,v_\ell\in\mathbb N, \qquad z_\ell=u_\ell-v_\ell. $$

向量形式记为线性映射

$$ \pi:\mathbb N^{2d}\to\mathbb Z^d, \qquad \pi(u,v)=u-v. $$

这个表示不唯一，例如 $1=1-0=2-1$，但存在量化只需要至少一个表示，非唯一性不影响集合像。搬运过程分两步。

从整数公式到整数半线性表示。 设 $A\subseteq\mathbb Z^d$ 由整数 Presburger 公式 $\varphi(z)$ 定义。对自由变量和量词约束的整数变量都分别引入一对非负变量，以 $z=u-v$ 替换每个整数变量，并把含负系数的线性项移到等式或不等式另一侧；再按上一节的移项、松弛变量、双非负商和 $\neg\exists\neg$ 规则，把所得自然数公式规范为 modified 语法。于是得到 $\mathbb N^{2d}$ 上的集合描述

$$ E=\{(u,v)\in\mathbb N^{2d}\mid\varphi(u-v)\}. $$

由 $\mathbb N^{2d}$ 上的 Ginsburg–Spanier 结论，$E$ 是有限个线性集之并。对每个线性分量施加 $\pi$：

$$ \pi\bigl(L(b;p_1,\ldots,p_k)\bigr) =L(\pi(b);\pi(p_1),\ldots,\pi(p_k)), $$

其中像后的基点和周期向量属于 $\mathbb Z^d$，系数仍属于 $\mathbb N$。因此

$$ A=\pi(E) $$

是 $\mathbb Z^d$ 上有限个这类线性集之并。

从整数半线性表示到整数公式。 反过来，把 $\mathbb Z^d$ 上的线性集定义为

$$ L_{\mathbb Z}(b;p_1,\ldots,p_k) =\{b+n_1p_1+\cdots+n_kp_k\mid n_r\in\mathbb N\}, $$

其中 $b,p_r\in\mathbb Z^d$。它由整数 Presburger 公式

$$ \exists n_1,\ldots,n_k:\ \bigwedge_r n_r\ge0 \land x=b+\sum_rn_rp_r $$

定义，因为 $p_r$ 都是固定整数向量，只出现常数乘变量。有限并仍由有限析取定义。

所以，整数版“Presburger 可定义集等于半线性集”是通过差编码、线性像和上述反向公式从 $\mathbb N^d$ 结论搬运得到的；它不是把 Ginsburg–Spanier 原文的论域直接改写成 $\mathbb Z^d$。Cooper 的整数消元工作提供整数公式处理的另一条经典背景，参见 Cooper (1972)。

例如整个整数轴可写成

$$ \mathbb Z=L_{\mathbb Z}(0;1)\cup L_{\mathbb Z}(-1;-1). $$

第一个线性集覆盖非负方向，第二个覆盖负方向；非负系数并不要求周期向量本身在整数版中为正。

手算示例

下面用对象对照、奇数反例和两个一维集合，把连续凸性、有限非凸分段与无限周期结构的边界逐一算清。

四类对象对照

表中前两行“不允许并”说的是表示类别只准一个 $P$，不是否认可以在集合论中另行做并。第二行也只说由单个凸 $P$ 截取全部格点，并不暗示 $P=\operatorname{conv}(P\cap\mathbb Z^d)$。取格点造成的离散性不等于模约束：比如直线 $x=2y$ 的整数点在几何上稀疏，但它们是该凸集合的全部格点；集合 $\{x\in\mathbb Z\mid x\equiv1\pmod2\}$ 则在一维凸包内部主动排除了所有偶数格点。

由定义立刻得到

$$ \{P\cap\mathbb Z^d\} \subseteq \left\{\bigcup_{r=1}^{s}(P_r\cap\mathbb Z^d)\right\} \subseteq \{\text{Presburger 可定义集合}\}. $$

这里花括号表示“这一类集合”。第二个包含在一般情形下是严格的，因为同余可以产生有限并普通多面体无法持续表达的周期孔洞。

奇数集合反例

考虑非负奇数集合

$$ O=\{x\in\mathbb Z\mid x\ge1\land x\equiv1\pmod2\} =L_{\mathbb Z}(1;2). $$

它既是 Presburger 可定义集，也是一个线性集。假设存在单个凸多面体 $P\subseteq\mathbb R$ 使

$$ P\cap\mathbb Z=O. $$

因为 $1,3\in O$，所以 $1,3\in P$。凸性要求它们的中点

$$ 2=\tfrac12\cdot1+\tfrac12\cdot3 $$

也属于 $P$。但 $2\in\mathbb Z$，于是 $2\in P\cap\mathbb Z$，与 $2\notin O$ 矛盾。因此“Presburger 可定义”不等于“某个凸多面体的全部整数点”。

这个例子甚至不能写成有限多个一维有理凸多面体的整数点之并。一维凸多面体是区间、射线、直线或点；有限并若包含任意大的奇数，就至少有一个无界分量包含某条实射线，从而也包含所有充分大的偶数。要逐个保留奇数而排除偶数，需要无限多个单点/小区间，或直接使用周期 2；有限多面体并做不到。

非凸不等于周期

以下两个集合展示两个独立维度：

$$ A=([-3,-1]\cup[1,3])\cap\mathbb Z $$

是非凸的，但仅有两个有限多面体分支，没有无限周期结构。相反，

$$ B=\{x\in\mathbb Z\mid x\ge0\land x\equiv0\pmod3\} $$

只有一个周期方向，却在整个非负射线上永久跳过两个剩余类。不能因为两者都可写成析取，就把有限几何分段与无限模周期视为同一现象。

编译器用途

1. 迭代域的几何内核。 规则矩形域、三角域和仿射边界通常直接写成 $P\cap\mathbb Z^d$，便于使用多面体算法。
2. 步长和对齐。 i += 2、向量对齐、银行映射等条件自然产生同余类；半线性/Presburger 视角不会把这些周期信息从凸包中抹掉。
3. 控制流析取。 多分支语句域可能是有限并整数多面体点集；若分支还含 modulo guard，则需要 basic set 加同余或局部存在变量，而不是只保存连续凸包。
4. 投影后的周期。 即使原约束以等式和存在变量给出，消去局部坐标也可能暴露出整除条件。例如 $\exists q:x=3q+1$ 投影后就是 $x\equiv1\pmod3$。
5. 算法边界。 许多调度和扫描算法选择多面体子类，是为了获得有限线性不等式、凸优化或逐分支处理能力；这是一种算法设计选择，不是一般 Presburger 集合突然都变成了单个凸多面体。

工程工具里的 “basic set” 或 “union set” 是具体表示对象，其允许的局部 div、同余和规范化规则要以官方文档为准。以 isl 为例，集合、映射及其 union/basic 对象的 API 语义参见 isl 官方手册；该手册是工具语义来源，不替代 Ginsburg–Spanier 的数学定理。

常见误区

1. 把 Ginsburg–Spanier 的论域直接写成 $\mathbb Z^d$。 原始结论直接在 $\mathbb N^d$ 上；整数版需要显式的正负部分/差编码与搬运论证。
2. 把线性集当向量子空间。 系数属于 $\mathbb N$，有基点且通常没有加法逆元。
3. 把“有限并”误作“无限周期”。 有限个凸分支能表达非凸，但普通不等式分支不能自动表达沿无界方向持续出现的模孔洞。
4. 把 $P$ 与 $P\cap\mathbb Z^d$ 混用。 前者连续，后者离散；循环实例和数组下标属于后者。
5. 把整数点集与整数凸包混用。 $P\cap\mathbb Z^d$ 是点集，$\operatorname{conv}(P\cap\mathbb Z^d)$ 是连续凸集。
6. 看到格点稀疏就断言有周期孔洞。 低维仿射子空间与 $\mathbb Z^d$ 相交也会稀疏；周期孔洞是相对于相关格点结构主动排除剩余类。
7. 把所有 Presburger 表示都交给凸多面体算法而不分支。 析取和同余若只取实凸包，可能加入原集合不存在的整数实例。
8. 把定理上的可表示性等同于紧凑性。 有限集按单点并总能半线性表示，但大小可能随参数增长，未必提供统一、紧凑的参数化表示。

练习

练习 EX05-B01｜同余类的线性集表示（基础）

把 $\{x\in\mathbb N\mid x\equiv2\pmod5\}$ 写成线性集，并写出对应的 Presburger 公式。

答案索引： ANS-EX05-B01

练习 EX05-D01｜二维生成元枚举与成员见证（推导）

列出 $L((0,1);(2,0),(0,3))\subseteq\mathbb N^2$ 在 $0\le n_1+n_2\le3$ 下生成的点。随后回到不带该截断条件的完整线性集，判断 $(4,7)$ 与 $(3,7)$ 是否属于它，并给出系数见证或不可能性证明。

答案索引： ANS-EX05-D01

练习 EX05-D02｜从整数到自然数的差编码（推导）

用差编码 $z=u-v$ 把整数公式 $z\le-2\land z\equiv1\pmod3$ 搬到非负整数变量上。注意把负系数移到关系另一侧，并处理同余见证中的整数商。

答案索引： ANS-EX05-D02

练习 EX05-C01｜$\mathbb Z^2$ 的有限半线性分解（综合）

证明 $\mathbb Z^2$ 可写成有限个 $\mathbb Z^2$ 上的线性集之并；可以按四个象限及坐标轴分解，也可以寻找更紧凑的生成元表示。

答案索引： ANS-EX05-C01

练习 EX05-C02｜四类对象与表示成本（综合）

判断下列离散对象分别属于本章四类对象中的哪些类：$\{0,2,4,6\}$、$\{2n\mid n\in\mathbb N\}$、固定参数 $N$ 的三角域 $T_N$，以及

$$ \bigl(([0,1]\times[0,1])\cup([3,4]\times[0,1])\bigr)\cap\mathbb Z^2. $$

说明“属于后一个大类”为什么不意味着有相同的表示成本。

答案索引： ANS-EX05-C02

练习 EX05-C03｜单个同余类不是单凸多面体格点集（综合）

推广奇数反例：对 $m\ge2$ 与规范化剩余 $0\le r<m$，证明单个同余类 $\{x\in\mathbb Z\mid x\ge0\land x\equiv r\pmod m\}$ 不能是某个一维凸多面体的全部整数点。

答案索引： ANS-EX05-C03

本章小结

• 在 $\mathbb N^d$ 上，线性集是 $b+\sum_r n_rp_r$（$n_r\in\mathbb N$），半线性集是有限多个线性集的并。
• Ginsburg–Spanier 的直接结论位于 $\mathbb N^d$：modified Presburger formulas 定义的集合恰好是半线性集。
• $\mathbb Z^d$ 版本需把每个整数坐标编码成 $u-v$，在 $\mathbb N^{2d}$ 上应用定理，再经线性像搬运；不能悄然改写原定理的论域。
• 单个有理凸多面体 $P$、整数点集 $P\cap\mathbb Z^d$、有限并整数多面体点集与一般 Presburger/半线性集合是不同对象。
• 多面体整数点和它们的有限并都是 Presburger 可定义的，但一般 Presburger 集合还能表达无限周期孔洞；非负奇数集合给出严格反例。
• 编译器使用多面体子类是为了算法结构和成本；同余、析取或投影产生的周期信息必须显式保留，不能只看连续凸包。