整数上的量词消除
《Journal of Symbolic Computation》:Quantifier elimination over the integers
【字体:
大
中
小
】
时间:2026年09月24日
来源:Journal of Symbolic Computation 0.9
编辑推荐:
# 摘要
本文探讨了Presburger算术中量词消除问题的代数方面。首先,我们在一个统一的框架中重新审视了多面体几何中能够支持整数域上量词消除的不同技术。其次,我们通过利用多元线性同余方程组的参数系统,讨论了其中一种技术的优化方法。第三,我们报告了在Presburger算
# 摘要
本文探讨了Presburger算术中量词消除问题的代数方面。首先,我们在一个统一的框架中重新审视了多面体几何中能够支持整数域上量词消除的不同技术。其次,我们通过利用多元线性同余方程组的参数系统,讨论了其中一种技术的优化方法。第三,我们报告了在Presburger算术中对这些不同量词消除策略的比较实现结果。第四,我们应用上述结果,提出了一种用于参数整数线性规划的新型算法,并报告了其实现情况。
# 引言
尽管量词消除(QE)固有的时间复杂度为双重指数级 [Fischer and Rabin, 1974; Davenport and Heintz, 1988; Brown and Davenport, 2007],它仍然被广泛使用:(i) 在代数几何中,用于处理实数上多项式约束构成的一阶逻辑公式;(ii) 在多面体几何中,用于处理整数上线性约束构成的公式。对于第二种情形,即线性整数算术(LIA),始于 Stansifer (1984) 和 Cooper (1972) 的工作,Pugh (1991) 和 Verdoolaege 等人 (2007) 开发的有效方法支持了多个领域。在这些领域之中,值得一提的是程序验证(参见 CompCert 项目 [Leroy et al., 2016] 和斯坦福 Pascal 验证器 [Luckham and von Henke, 1981])、优化编译器(参见 GCC 的 Graphite [Pop et al., 2006] 和 LLVM 的 Polly [Grosser et al., 2012])以及定理证明(参见 SAT/SMT 求解器 Z3 [de Moura and Bj?rner, 2008] 和 CVC5 [Barbosa et al., 2022],以及证明助手 Coq [Bertot and Castéran, 2004]、Isabelle [Nipkow et al., 2002]、HOL Light [Harrison, 1996] 和 Lean [de Moura, 2016])。
然而,为了应对实际中感兴趣且当前软件力所不及的问题,仍存在改进的空间。其中一个这样的问题是去线性化(delinearization),这是一种用于恢复以一元数组编码的多维数组访问之多维特性的技术 [Vadim, 1992; Grosser et al., 2015]。该编译器技术用作依赖分析之前的必要预处理步骤。去线性化可以表述为整数域上的一个量词消除问题,同时涉及全称量词和存在量词。公式无量词部分的某些原子在编译时是非线性的,仅在运行时才变为线性。因此,去线性化是一个困难的问题,必须在运行时解决,从而需要在极短的时间内完成。基于所有这些原因,去线性化是线性整数算术(LIA)的一个重要但具有挑战性的应用,也是本文的主要驱动应用之一。
尽管 Pugh (1991) 和 Verdoolaege 等人 (2007) 中所提出方法的首要目标是对多面体集进行操作(分别用于测试非空性和计数整数点),但它们可以作为量词消除软件工具的核心程序,与可满足性模理论(SMT)技术结合使用。我们也认为,改进多面体几何中的关键算法对于线性整数算术至关重要,这也是本文的动机所在。
考虑一个前束范式的 Presburger 公式 $F$:
$$F = Q_1 x_1 \cdots Q_m x_m \, \varphi(x_1, \ldots, x_m, y_1, \ldots, y_n),$$
其中:
1. $Q_1 x_1 \cdots Q_m x_m$ 是量词(存在量词或全称量词)和约束变量的序列;
2. $\varphi(x_1, \ldots, x_m, y_1, \ldots, y_n)$ 是无量词公式;
3. $y_1, \ldots, y_n$ 是自由变量。注意,所有这些变量均取整数值。我们的目标是确定集合 $D(y_1, \ldots, y_n)$,它由所有使 $F$ 为真的整数元组 $(y_1, \ldots, y_n)$ 组成。利用量词的 De Morgan 定律,可以将其简化为所有量词 $Q_1, \ldots, Q_m$ 均为存在量词的情形。
我们通过定理 2 观察到,如果 $\varphi(x_1, \ldots, x_m, y_1, \ldots, y_n)$ 是若干线性不等式系统的析取,那么 $D(y_1, \ldots, y_n)$ 也可以由若干线性不等式系统的析取给出。如果一组量词的消除是通过某种参数多面体整数点计数算法完成的——例如 Verdoolaege 等人 (2007) 的算法或我们在 Jing 等人 (2024) 中提出的算法——就会出现这种情况。
如果 $\varphi(x_1, \ldots, x_m, y_1, \ldots, y_n)$ 包含同余关系,则可以使用 Cooper 的算法,其中输入 Presburger 公式的原子可以是不等式、同余关系或同余关系的否定。该算法已在 ML 编程语言中实现,以支持 Harrison (2003)、Norrish (2003) 以及 Chaieb and Nipkow, 2003, Chaieb and Nipkow, 2005 的定理证明器。也有在 ML 方言 F# 中的实现,目的是对 Cooper 算法进行并行化 [Dung and Hansen, 2011]。所有这些实现都仅限于消除单个存在量词,因此 Cooper 程序的实用影响不如前述 Pugh 和 Verdoolaege 的工作显著。
同余关系的一种替代方案是格成员关系,实验表明后者可以提供更紧凑的输出。这是本文所遵循的观点。
我们从 Jing and Moreno Maza, 2017a, Jing and Moreno Maza, 2017b 开始对 Presburger 算术的研究,在其中我们提出了一种算法用于测试 $\mathbb{Z}$-多面体是否为空,若不为空,则以紧凑方式描述其点。该算法在 Maple 中实现为我们 PolyhedralSets 库中的 IntegerPointDecomposition 命令,依赖于 Pugh 的 Omega 测试 [Pugh, 1991]。当时我们的主要改进在于整数域上线性方程组的求解。在某些技术假设下,算法 IntegerPointDecomposition 相对于环境空间的维度以单次指数时间运行。尽管这些假设在实践中通常成立,但相对容易构造不满足这些假设的输入系统。因此,据我们所知,当所有量词 $Q_1, \ldots, Q_m$ 均为存在量词时,不存在已知的算法能以单次指数时间计算集合 $D(y_1, \ldots, y_n)$。然而,判断 $D(y_1, \ldots, y_n)$ 是否为空的问题,以及在 $D(y_1, \ldots, y_n)$ 非空时计算其某些点的问题(同样在所有量词 $Q_1, \ldots, Q_m$ 均为存在量词的情况下),可以以单次指数时间完成,如 Haase 等人 (2024) 中 Christoph Haase 等人所示。
我们注意到,在实闭域上,存在比整数域上更为有利的结果,参见 Saugata Basu 等人的工作 [Basu et al., 1996]。尽管如此,Christopher W. Brown 和 James H. Davenport 给出了一个简洁且构造性的证明 [Brown and Davenport, 2007],表明即使在只有一个自由变量且量化输入中所有多项式均为线性的情况下,实代数中的量词消除也是双重指数的。
在本文中,我们进一步改进了在 Jing and Moreno Maza, 2017a, Jing and Moreno Maza, 2017b 中提出的计算集合 $D(y_1, \ldots, y_n)$ 的方法。此外,我们不仅局限于所有量词 $Q_1, \ldots, Q_m$ 均为存在量词的情形。首先,我们利用格,受 Seghir 等人 (2012) 工作的启发。其次,我们在第 5.3 节中观察到,当我们消除一个量化变量时,通过求解多元线性同余方程组的参数系统,可以大幅减少需要考虑的格的数量,我们在第 3.1 节对此进行了研究。
本文的另一个贡献是在统一框架下呈现不同的整数投影方法,参见第 5 节。除了 Cooper 和 Pugh 的投影之外,我们回顾了 Williams and Hooker (2016); Williams (1976) 的投影方法。这种比较表明 Pugh 的投影所进行的切割(Williams and Hooker, 2016 中研究的概念)少于其他投影,参见定理 3。此外,我们通过定理 4 证明了 Cooper 和 Williams 的投影本质上是相同的。
本文的第三个贡献是对整数域上两种量词消除(QE)策略的实验比较。为此,我们在 Maple 中开发了一个量词消除引擎,它接受一个执行整数投影的算法作为输入参数。在我们的实验中,我们使用了最新版本的 IntegerPointDecomposition(因此使用格)和 NumberOfIntegerPoints(Jing 等人,2024)。后者基于 Barvinok (1994); Barvinok and Pommersheim (1999); De Loera 等人 (2004) 的工作。该实验比较在第 6 节中报告,结果表明对于足够困难的实例,基于 IntegerPointDecomposition 的量词消除优于基于 NumberOfIntegerPoints 的量词消除。我们的代码已公开可用,地址为:github.com/MarcMorenoMaza/PolyhedralSets/tree/main/QuantifierEliminationOverTheIntegers,使用 git 版本 2.43.0。
自我们发表 ISSAC 2025 论文 (Jing 等人,2025) 以来,我们一直在拓展对 Presburger 算术的研究,特别是在参数整数线性规划(PILP)方面。Presburger 算术中的量词消除与 PILP 密切相关,参见 Friedrich Eisenbrand 和 Gennady Shmonin 的论文 (Eisenbrand and Shmonin, 2008)。PILP 也是开发优化编译器的基本工具,特别是用于自动并行化和局部性优化问题,参见 ISL 项目 (Verdoolaege, 2010) 和 PLUTO 项目 (Bondhugula 等人, 2008a, Bondhugula 等人, 2008b)。在第 7 节中,我们介绍了一种执行 PILP 的新方法。我们依赖于第 2 节和第 5 节中提出的思想和技术,特别是 IntegerPointDecomposition 算法以及该算法所产生 $\mathbb{Z}$-多面体的性质。这些性质使我们能够在参数空间的不同区域上计算目标函数的取值范围,从而优化参数 $\mathbb{Z}$-多面体上的目标函数。
据我们所知,另有两种执行 PILP 的算法有公开可用的实现:基于单纯形算法改编的 Feautrier (1988) 算法,以及基于 Barvinok 算法 (Barvinok, 1994) 的 Verdoolaege (2010) 算法。在第 8 节中,我们针对 ISL 库中的各种例子,对三种 PILP 算法(Feautrier 的、Verdoolaege 的和我们的)进行了说明和比较。
# 章节片段
## 基本概念
第 2.1、2.3 和 2.5 节是对多面体几何的回顾,我们遵循 Alexander Schrijver 的著作 Rajan (1990) 中的概念和记号。第 2.2 和 2.4 节回顾了整数矩阵的基本材料。通常,我们用 $\mathbb{Z}$、$\mathbb{Q}$ 和 $\mathbb{R}$ 分别表示整数环、有理数域和实数域。除非另有说明,所有矩阵和向量的系数均取自 $\mathbb{Z}$。
## 多元线性同余方程组的参数系统
在本节中,我们讨论多元且线性的同余方程组。我们在第 3.1 节从经典一元中国剩余定理(CRT)的自然多元推广开始,参见公式 (11)。在第 3.2 节中,我们允许额外的约束条件,指定未知数属于整数格。
## Presburger 算术
1929 年,Moj?esz Presburger 证明了普通 Presburger 算术的语言(即带有加法的一阶整数理论),在扩展以可整除性谓词 $D_k : x \mapsto k \mid x$(对于每个正整数 $k$)之后,可以进行量词消除。参见 Stansifer (1984) 获取 Presburger 原始论文的带注释译文。另参见 Christoph Haase 的 Presburger 算术生存指南 (Haase, 2018) 作为该主题的入门介绍。
考虑一个 Presburger 公式……
## 整数投影
再次考虑第 4 节中的公式 (24),假设在本节中 $m = 1$ 成立。因此,我们必须消除单个量词,并且有鉴于 De Morgan 定律,我们假设该量词为存在量词。我们定义 $x = x_1$,$\mathbf{y} = (y_1, \ldots, y_n)$,并将这 $n+1$ 个变量排序为 $x > y_n > \cdots > y_1$。因此,公式 (24) 可以转换为如下形式:
$$\varphi(x, y_1, \ldots, y_n) = \bigvee_i \varphi_i(x, y_1, \ldots, y_n),$$
其中 $\varphi_i(x, y_1, \ldots, y_n)$ 是同余关系和非严格不等式的合取。回顾我们的目标是……
## 整数上的量词消除实验
我们在 Maple 2024 中实现了一个 Presburger 算术的量词消除引擎。该过程以投影算法为参数,即以公式 (30) 为输入计算 $D(\mathbf{y})$ 的算法。我们使用两种投影方法测试了该量词消除引擎:IntegerPointDecomposition 和 NumberOfIntegerPoints,分别简称为 IPD 和 NIP。这两种方法已在第 2 节和第 4 节中讨论。
我们实验中所用的测试用例在第 6.1 节中描述。三分之一……
## 参数整数线性规划
在本节中,我们介绍参数整数线性规划(PILP)的算法。我们依赖于前几节中提出的思想和技术,特别是第 2 节和第 5 节。我们的重点在于:给定参数 $\mathbb{Z}$-多面体定义的约束条件,以及由线性多项式给出的目标函数,如何找到该目标函数的最大值。
第8节提供了各种示例,用以说明我们的算法以及Feautrier(1988)和Verdoolaege(2010)的对应算法。参数化整数线性规划的示例目前,已有两个库——ISL和Barvinok(Verdoolaege, 2010)——基于Paul Feautrier和Sven Verdoolaege的工作被开发出来。它们都提供了解决参数化整数规划问题的命令,并用C语言实现,而我们的程序则使用Maple开发。我们仍可使用ISL和Barvinok的PIP测试输入来评估我们的程序。尽管部分输出规模相当庞大,因此难以直接比较,但我们已获得了足够数量的结论。我们处理了Presburger算术中存在量词消去问题的代数问题。这些问题包括:1. 有量化公式中矩阵(即无量词公式部分)的输入和输出格式。该格式由范数类型(析取范式或否定范式)以及原子公式的选择所确定。2. 对线性不等式组或多元线性同余方程组进行投影的技术。3. 性能。CRediT作者贡献声明:Jing Rui-Juan:撰写——初稿、可视化、验证、监督、软件、资源、方法论、调查、数据整理、概念化。Lei Yuzhuo:撰写——审阅与编辑、撰写——初稿、可视化、验证、软件、资源、项目管理、方法论、调查、形式化分析、数据整理、概念化。Marc Moreno Maza:撰写——审阅与编辑、撰写——初稿、监督、软件、资源、项目。致谢我们感谢审稿人和编辑提供的详尽报告和富有建设性的建议。Jing Rui-Juan | Lei Yuzhuo | Marc Moreno Maza | Chirantan Mukherjee