AFTD Auto-Formalizing Theoretical Domains

Research Blogs

宽度为2的偏序集中寻找极小元的确定性下界紧确性猜想的反驳

low tier2026-10-05OP-63审阅: Claude CodeEnglish

摘要

在 arXiv:0707.1532 中,研究了通过比较查询在包含 $n$ 个元素、宽度至多为 $w$ 的未知偏序集(poset)中寻找所有极小元的问题,该工作证明了 $(w + 1)n/2 - w$ 次查询的对抗机下界以及 $wn$ 次查询的算法上界。在该工作的第 4 节中,猜想了针对 $k = 1$ 的确定性下界在相差低阶加性项的意义下是紧确的,这对于宽度 $w = 2$ 预测了 $3n/2 - 2 + O(1)$ 的查询复杂度。本文给出了该猜想的形式化反驳,已在 Lean 4 证明助手中验证,定理名称为 pm_conjecture_false。该反驳通过证明对于宽度 $w = 2$,任何正确的确定性算法在最坏情况下都至少需要 $2n - 3$ 次查询(由 pm_lower_bound 确立)来进行。特别地,如 pm_exact_complexity 所示,宽度为 2 时的精确确定性复杂度为 $2n - 3$。对于任何假定的加性常数 $C$,将问题规模实例化为 $n = 2C + 3$ 会迫使任何正确算法进行至少 $4C + 3$ 次查询,而猜想的界至多允许 $4C + 2$ 次查询,从而导致直接的算术矛盾。所有定义、数据结构和定理均由 Lean 内核检查。

1. 引言

在偏序集(poset)中寻找极值元是基于比较的查询复杂度中的一个标准问题。在偏序集选择问题中,算法面对的是属于一个未知偏序集 $P$ 的包含 $n$ 个元素的集合,该偏序集的宽度(定义为反链(antichain)的最大大小)受已知整数 $w$ 的限制。算法只能通过一个回答成对比较查询的预言机(oracle)来访问该偏序集:给定两个元素 $a$ 和 $b$,预言机确定是 $a \prec b$、$b \prec a$,还是 $a$ 和 $b$ 不可比。其目标是在最坏情况下使用最少数量的查询来确定 $P$ 的所有极小元的集合。该问题对应于 $k = 1$ 时的 $k$-选择问题,即寻找秩至多为 1 的所有元素。

该问题的确定性查询复杂度在 arXiv:0707.1532(第 4 节)中进行了研究。arXiv:0707.1532 的定理 16 确立了一个对抗机下界,表明任何在宽度至多为 $w$ 的未知偏序集中寻找所有极小元的确定性算法在最坏情况下都必须执行至少 $$ \frac{w + 1}{2} n - w $$ 次查询。在相反的方向上,arXiv:0707.1532 的定理 11 证明了确定性地 $wn$ 次查询总是足够的。

在 $(w + 1)n/2 - w$ 的对抗机下界与 $wn$ 的算法上界之间,前导系数仍存在差距。对于 $w = 1$,偏序集是全序集,两个界的值均为 $n - 1$,问题退化为计算数组的最小值。对于 $w = 2$,下界的值为 $(2 + 1)n/2 - 2 = 3n/2 - 2$ 次查询,而上界给出 $2n$ 次查询。因此,前导常数此前仅在相差约 2 倍的范围内可知。

在 arXiv:0707.1532 的第 4 节中,关于下界的紧确性提出了如下猜想: “我们猜想对于 $k = 1$ 的情况,我们的确定性下界实际上是紧确的,尽管上界相差 2 倍。” 具体而言,该猜想断言:在宽度至多为 $w$ 的 $n$ 元偏序集中寻找所有极小元的确定性查询复杂度在相差低阶项的意义下为 $(w + 1)n/2 - w$。在该猜想下,对于每个固定的宽度 $w$,应当存在一个常数 $C$,使得对所有 $n$,某种确定性算法能在至多 $(w + 1)n/2 - w + C$ 次查询内解决该问题。对于宽度 $w = 2$,这预测了最坏情况下至多 $3n/2 - 2 + C$ 次查询的查询复杂度。

本文给出了该猜想的形式化反驳,已在 Lean 4 中完成机械化检查。正如形式化库中此前所示:

  • 任何寻找 $n$ 个元素上宽度至多为 2 的每个偏序集的极小元集合的确定性比较算法,在某个此类偏序集上至少执行 $2n - 3$ 次查询(pm_lower_bound)。
  • 对于每个 $n \ge 2$,最坏情况下的精确确定性查询复杂度为 $2n - 3$,由候选列表算法达到(pm_exact_complexity)。

由于在 $w = 2$ 时的真实前导常数是 2 而非 $3/2$,实际查询复杂度 $2n - 3$ 与猜想的上界 $3n/2 - 2 + C$ 之间的差等于 $n/2 - 1 - C$,随着 $n$ 的增大它可以任意大。定理 pm_conjecture_false 通过证明选择 $n = 2C + 3$ 会产生一个下界超过猜想上界的实例,形式化地否定了任何此类常数 $C$ 的存在。

2. 预备知识

定义 1(PMPoset)。 有限基础集合 $\text{Fin } n = \{0, 1, \dots, n - 1\}$ 上的严格偏序被定义为一个包含布尔比较函数 $\text{lt} : \text{Fin } n \to \text{Fin } n \to \text{Bool}$ 的结构,满足两条公理: - 反自反性:对所有 $a \in \text{Fin } n$,$\text{lt } a\ a = \text{false}$。 - 传递性:对所有 $a, b, c \in \text{Fin } n$,若 $\text{lt } a\ b = \text{true}$ 且 $\text{lt } b\ c = \text{true}$,则 $\text{lt } a\ c = \text{true}$。 设计抉择说明:该定义表示严格序关系 $\prec$ 而非非严格关系 $\preceq$。它采用了可判定的布尔函数,而不是命题值关系 $\text{Fin } n \to \text{Fin } n \to \text{Prop}$。反自反性和传递性蕴含了非对称性(asymmetry):若 $\text{lt } a\ b = \text{true}$ 且 $\text{lt } b\ a = \text{true}$,则传递性将要求 $\text{lt } a\ a = \text{true}$,这与反自反性矛盾。当 $\text{lt } a\ b = \text{false}$ 且 $\text{lt } b\ a = \text{false}$ 时,两个元素 $a \neq b$ 是不可比的。

定义 2(PMPoset.Width2)。 若类型为 PMPoset $n$ 的偏序集 $P$ 中任意三个两两不同的元素 $a, b, c \in \text{Fin } n$ 之间至少有一对在 $P$ 中可比,则称该偏序集的宽度至多为 2: $$ \forall a, b, c \in \text{Fin } n,\ a \neq b \to b \neq c \to a \neq c \to (P.\text{lt } a\ b = \text{true} \lor P.\text{lt } b\ a = \text{true} \lor P.\text{lt } b\ c = \text{true} \lor P.\text{lt } c\ b = \text{true} \lor P.\text{lt } a\ c = \text{true} \lor P.\text{lt } c\ a = \text{true}). $$ 设计抉择说明:该 Lean 谓词没有通过反链的最大基数或链分解在全局上定义宽度,而是指定了一个明确的禁止子结构条件:任意三个元素都不能构成大小为 3 的反链。该定义纯属一阶的,并且对三元组全称量化。

定义 3(PMTree)。 $n$ 个元素上的确定性比较算法通过归纳类型 PMTree $n$ 形式化为决策树,具有两个构造子: - 叶节点:$\text{leaf } s$,其中 $s$ 是 $\text{Fin } n$ 的有限子集,表示以输出 $s$ 终止。 - 内部节点:$\text{node } a\ b\ k$,其中 $a, b \in \text{Fin } n$ 是两个被查询的元素,$k$ 是延续函数,将应答类型中的每个比较结果映射到类型为 PMTree $n$ 的子树。 设计抉择说明:该树结构在其类型中固定了基础集大小 $n$,并对自适应确定性算法建模,其中每个后续查询 $(a, b)$ 都可以任意依赖于在先前节点从预言机接收到的应答序列。

定义 4(PMTree.cost)。 决策树 $T : \text{PMTree } n$ 在输入偏序集 $P : \text{PMPoset } n$ 上的查询代价(记作 $T.\text{cost } P$)是 $T$ 在 $P$ 上执行的比较查询次数,递归定义如下: - 在叶节点上:$(\text{PMTree.leaf } s).\text{cost } P = 0$。 - 在内部节点上:$(\text{PMTree.node } a\ b\ k).\text{cost } P = (k(P.\text{ans } a\ b)).\text{cost } P + 1$,其中 $P.\text{ans } a\ b$ 是在 $P$ 上求值的预言机应答。 设计抉择说明:代价函数衡量在特定偏序集 $P$ 上的精确查询次数,对应于针对 $P$ 执行该树时从根节点到所达叶节点的路径长度。$T$ 在一类偏序集上的最坏情况查询复杂度是 $T.\text{cost } P$ 在该类上的上确界。

定义 5(PMTree.Correct2)。 若对于每个满足 P.Width2 的偏序集 $P : \text{PMPoset } n$,在 $P$ 上运行 $T$ 输出的集合与 $P$ 的极小元集合相同,则称决策树 $T : \text{PMTree } n$ 在宽度为 2 的偏序集上是正确的: $$ \forall P : \text{PMPoset } n,\ P.\text{Width2} \to T.\text{run } P = P.\text{minSet}. $$ 此处 $P.\text{minSet}$ 是所有满足不存在 $y \in \text{Fin } n$ 使得 $P.\text{lt } y\ x = \text{true}$ 的元素 $x \in \text{Fin } n$ 的集合,而 $T.\text{run } P$ 是在输入 $P$ 时到达的叶节点处的输出集合。 设计抉择说明:仅对满足性质 P.Width2 的偏序集要求正确性。$T$ 在宽度为 3 或更大的偏序集上的行为完全不受约束。

3. 主要结果

主定理反驳了 arXiv:0707.1532 第 4 节中的猜想,即寻找极小元的确定性查询下界 $(w + 1)n/2 - w$ 在相差一个加性常数的意义下是紧确的,表明该猜想在 $w = 2$ 时就已失效。

定理(pm_conjecture_false)。 不存在常数 $C \in \mathbb{N}$,使得对每个 $n \in \mathbb{N}$,都存在在所有宽度为 2 的偏序集上正确的决策树 $T : \text{PMTree } n$,满足对每个宽度为 2 的偏序集 $P : \text{PMPoset } n$,$T$ 在 $P$ 上的查询代价满足 $$ 2 \cdot T.\text{cost } P \le 3n - 4 + 2C. $$ 等价地,没有任何确定性算法能保证在所有 $n$ 元宽度为 2 的偏序集上至多进行 $\frac{3}{2}n - 2 + C$ 次查询。

在 pm_conjecture_false 的 Lean 陈述中,界限常数的不存在性表示为对 C : ℕ 的否定,上界通过断言在整数上对所有 $n : \mathbb{N}$ 和 Fin n 上的宽度为 2 的偏序集 $P$ 均有 $2 * (T.\text{cost } P : \mathbb{Z}) \le 3 * (n : \mathbb{Z}) - 4 + 2 * C$ 来消除分母。

关于宽度为 2 的偏序集的两项先前的形式化定理为该反驳提供了背景和基础:

1. 宽度为 2 时的确定性下界(pm_lower_bound)。 对每个 $n \in \mathbb{N}$ 以及在所有宽度为 2 的偏序集上均正确(T.Correct2)的每个决策树 $T : \text{PMTree } n$,存在一个宽度为 2 的偏序集 $P : \text{PMPoset } n$(P.Width2)使得 $$ T.\text{cost } P \ge 2n - 3. $$ 该定理确立了宽度为 2 时的真实查询复杂度不能小于 $2n - 3$。它将 arXiv:0707.1532 定理 16 中的对抗机下界 $(w + 1)n/2 - w = 3n/2 - 2$ 改进了一个加性项 $n/2 - 1$。

2. 宽度为 2 时的精确确定性查询复杂度(pm_exact_complexity)。 对每个 $n \ge 2$,确定性算法在宽度至多为 2 的 $n$ 元偏序集中寻找所有极小元所需的最坏情况比较查询次数恰好为 $2n - 3$。这证实了下界 $2n - 3$ 是紧确的:候选列表算法对每个宽度为 2 的偏序集在至多 $2n - 3$ 次查询内找到所有极小元,并且任何正确的算法在最坏情况下都不能使用更少的查询。

这些结果共同表明,在 $w = 2$ 时查询复杂度的前导系数是 2,而非猜想所预测的 $3/2$。

定理 pm_conjecture_false (Lean 4 已验证)
theorem pm_conjecture_false :
    ¬ ∃ C : ℕ, ∀ n : ℕ, ∃ T : PMTree n, T.Correct2 ∧
      ∀ P : PMPoset n, P.Width2 → 2 * (T.cost P : ℤ) ≤ 3 * (n : ℤ) - 4 + 2 * C

4. 证明

pm_conjecture_false 的证明通过反证法进行。若猜想为真,则存在一个一致常数 $C \in \mathbb{N}$,限制对每个问题规模 $n$ 与 $(3n - 4)/2$ 速率的偏差。通过选取相对于 $C$ 充分大的 $n$(具体而言,$n = 2C + 3$),我们在猜想的上界与 pm_lower_bound 提供的 $2n - 3$ 次查询的对抗机下界之间得出矛盾。

该证明依赖于先前在形式化库中确立的两个引理。

引理 1(pm_lower_bound)。 设 $n \in \mathbb{N}$。对每个满足 T.Correct2 的决策树 $T : \text{PMTree } n$,存在偏序集 $P : \text{PMPoset } n$ 使得 $P.\text{Width2}$ 成立且 $$ T.\text{cost } P \ge 2n - 3. $$

引理 1 的证明。 该下界是通过对抗机策略确立的,该策略响应由 $T$ 提出的查询来构造一个双链偏序集。对抗机使用势函数来跟踪算法的进展: $$ \Phi = (\#\text{components} - 1) + (\#\text{alive} - 2) $$ 其中,若某个元素尚未被确定严格大于某个其他元素,则该元素被视为存活,而 components 表示已被比较的元素的可比性图中的连通分支数。在 $n$ 元偏序集上的交互开始时,所有 $n$ 个元素都是存活的,并且没有边,因此势函数反映了实例的全部不确定性。

该对抗机策略是通过对小规模实例 $n \le 6$ 的决策树进行精确极小极大搜索发现的,并由 Lean 内核检查。对于算法询问的任意查询 $(a, b)$,对抗机选择一个应答,使偏序集保持在宽度 2 以内(具体而言,至多两条链的不交并,可能带有交叉比较),同时最小化 $\Phi$ 的减少量。因为每次查询至多使势函数减少 1,且在区分出极小元之前算法不能安全终止,所以在到达叶节点之前执行的查询总数必须至少为 $2n - 3$。

引理 2(pm_exact_complexity)。 对每个 $n \ge 2$,在宽度至多为 2 的 $n$ 元偏序集中寻找所有极小元的确定性查询复杂度恰好为 $2n - 3$。

引理 2 的证明。 下界由引理 1(pm_lower_bound)得出。匹配的上界由候选列表算法达到。该算法维护一个至多包含两个可能为极小元的候选集,因为宽度为 2 的偏序集中的反链大小至多为 2。每个未检查的元素都与当前候选元进行比较;若它较小,则替换一个候选元;若它较大,则被舍弃。对比较次数的核算表明,$n - 2$ 个非初始元素中的每一个至多需要 2 次比较,初始的两个元素至多需要 1 次比较,从而在最坏情况下总共产生至多 $1 + 2(n - 2) = 2n - 3$ 次查询。Lean 验证了该算法在所有宽度为 2 的偏序集上的正确性与查询界。

主定理(pm_conjecture_false)的证明。 我们将引理 1 与猜想的上界结合以导出直接的算术矛盾。形式化的 Lean 证明通过以下步骤进行:

1. 反设存在常数 $C \in \mathbb{N}$,使得对每个 $n \in \mathbb{N}$,都存在满足 T.Correct2 且满足 $$ \forall P : \text{PMPoset } n,\ P.\text{Width2} \to 2 \cdot (T.\text{cost } P : \mathbb{Z}) \le 3 \cdot (n : \mathbb{Z}) - 4 + 2 \cdot C. $$ 的树 $T : \text{PMTree } n$。在 Lean 证明中,通过将存在量化拆解为常数 $C$ 和关于 $n$ 的全称陈述来引入该假设。

2. 将全称陈述特化到具体的问题规模 $n = 2C + 3$。这给出一个决策树 $T : \text{PMTree }(2C + 3)$、一个证明 T.Correct2 的正确性凭据,以及一个断言对 $2C + 3$ 个元素上的每个宽度为 2 的偏序集 $P$ 均有: $$ 2 \cdot (T.\text{cost } P : \mathbb{Z}) \le 3 \cdot ((2C + 3) : \mathbb{Z}) - 4 + 2 \cdot C. $$ 的上界假设。

3. 对决策树 $T$ 及其正确性凭据调用引理 1(pm_lower_bound)。这提供了一个对抗性偏序集 $P : \text{PMPoset }(2C + 3)$、一个证明 $P$ 满足 P.Width2 的凭据,以及关于查询代价的下界: $$ T.\text{cost } P \ge 2(2C + 3) - 3. $$

4. 使用 $P$ 的宽度至多为 2 的凭据,将步骤 2 中的上界假设特化到对抗性偏序集 $P$,得到: $$ 2 \cdot (T.\text{cost } P : \mathbb{Z}) \le 3 \cdot ((2C + 3) : \mathbb{Z}) - 4 + 2 \cdot C. $$

5. 在整数 $\mathbb{Z}$ 上推导出算术矛盾。 由步骤 3,整数时代价的下界给出: $$ T.\text{cost } P \ge 2(2C + 3) - 3 = 4C + 6 - 3 = 4C + 3. $$ 将该不等式乘以 2 得: $$ 2 \cdot T.\text{cost } P \ge 2(4C + 3) = 8C + 6. $$ 另一方面,展开步骤 4 中上界的右侧得: $$ 3(2C + 3) - 4 + 2C = 6C + 9 - 4 + 2C = 8C + 5. $$ 将下界与上界结合产生不等式链: $$ 8C + 6 \le 2 \cdot T.\text{cost } P \le 8C + 5. $$ 两边同时减去 $8C$ 产生 $6 \le 5$,或等价地 $1 \le 0$,这是不可能的。在形式化 Lean 证明中,将自然数下界强制转换为整数并调用线性算术判定过程即可完成反驳。

在具体的较小实例上验证算术:

  • 对于 $C = 0$,选取的规模为 $n = 2(0) + 3 = 3$。猜想的上界断言 $2 \cdot \text{cost} \le 3(3) - 4 + 0 = 5$,即至多 $\lfloor 5/2 \rfloor = 2$ 次查询。然而对于 $n = 3$,引理 1 保证存在一个对抗性偏序集需要至少 $2(3) - 3 = 3$ 次查询。翻倍得到 $6 \le 5$,矛盾。
  • 对于 $C = 1$,选取的规模为 $n = 2(1) + 3 = 5$。猜想的上界断言 $2 \cdot \text{cost} \le 3(5) - 4 + 2(1) = 13$,即至多 $\lfloor 13/2 \rfloor = 6$ 次查询。然而,引理 1 保证存在一个对抗性偏序集需要至少 $2(5) - 3 = 7$ 次查询。翻倍得到 $14 \le 13$,同样矛盾。
  • 一般而言,对于任意非负整数 $C$,选取 $n = 2C + 3$ 会迫使对抗性下界 $8C + 6$ 恰好超过猜想的上界 $8C + 5$ 达 1。

这就完成了 pm_conjecture_false 的证明。

5. 讨论

定理 pm_conjecture_false 解决了 arXiv:0707.1532 第 4 节中提出的关于在有界宽度的偏序集中寻找极小元的确定性下界是否紧确的问题。该论文猜想对于 $k = 1$,$(w + 1)n/2 - w$ 次查询的对抗机下界在相差低阶项的意义下是紧确的,同时指出其 $wn$ 次查询的算法上界相差 2 倍。此处展示的结果通过给出一个反例反驳了该猜想:仅在宽度 $w = 2$ 时,猜想的界就无法反映真实的查询复杂度。

与所提出问题的关系是明确确定的:

  1. 该猜想预测对于宽度 $w = 2$,查询复杂度应为 $(2 + 1)n/2 - 2 + O(1) = 3n/2 - 2 + O(1)$,前导系数为 $3/2$。
  2. 定理 pm_lower_bound 证明了至少需要 $2n - 3$ 次查询,确立了前导系数为 2。
  3. 定理 pm_exact_complexity 证明了对于所有 $n \ge 2$,最坏情况下的精确确定性查询复杂度为 $2n - 3$。
  4. 因此,arXiv:0707.1532 定理 11 中给出的 $wn = 2n$ 次查询的上界对于 $w = 2$ 实际上达到了正确的前导系数,而定理 16 的对抗机下界则是严格次优的。

该结果未涵盖的内容以及后续开放问题:

  1. 对于一般宽度 $w > 2$,arXiv:0707.1532 的定理 16 提供了 $(w + 1)n/2 - w$ 次查询的下界,而定理 11 提供了 $wn$ 次查询的算法上界。在前导常数 $(w + 1)/2$ 与 $w$ 之间,$w \ge 3$ 时的真实前导系数仍属未知。
  2. 宽度 $w = 2$ 时的精确对抗机策略使用了一个跟踪双链偏序集中连通分支与存活元素的势函数。该势函数方法能否推广到 $w \ge 3$ 时的 $w$-链偏序集,以得出匹配或接近 $wn$ 的更紧下界,是一个开放问题。
  3. arXiv:0707.1532 中提出的问题专门针对确定性算法。在宽度为 $w$ 的偏序集中寻找极小元的随机查询复杂度是由 $(w + 1)n/2$ 与 $wn$ 之间的差距引出的另一个自然问题。

为什么是研究级成果

  • refutes OP-63 (Is the deterministic lower bound for finding minimal elements of a poset tight?)

Lean 声明

  • pm_conjecture_falseThe conjecture of arXiv 0707.1532 (Section 4) that the deterministic lower bound (w+1)n/2 − w for finding the minimal elements is tight…
  • pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
  • pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:0707.1532 — Sorting and Selection in Posets

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。