结果族 114：Approximate counting of common integer polymatroid bases · 学科：Theoretical computer science · 验证状态：主结果已 Lean 形式化
一桌宝物，两位鉴定师各有一套”哪些组合算合格”的标准——两套标准都讲道理：某组合合格则它的任何一部分也合格，且合格的组合总能在桌上换一件、扩充成件数拿满的组合。要数的是”两位都点头、件数拿满”的组合总数。二部图的完美匹配就是一例：两条标准分别是”每行至多一件、每列至多一件”。数这种公共组合，此前连快速的随机算法都没有，本文给出了 FPRAS。
关键词卡片
看个具体例子
2×2 完全二部图：行方 a₁、a₂，列方 b₁、b₂。约束一”每行恰取一条边”、约束二”每列恰取一条边”，公共基恰是完美匹配：红色对角配对 {a₁b₁, a₂b₂} 与紫色交叉配对 {a₁b₂, a₂b₁}，故 Z=2，算法输出 @@M@@2(1\pm\epsilon)@@ 附近的估计。一般拟阵没有图画，但算法只需向预言机问”合格吗”，从不要求拟阵的显式清单。
为什么值得关心
拟阵交的”优化”1970 年代就多项式可解，”计数”却一直缺算法；本文肯定回答了 Liu 博士论文记录的公开问题，还连带解决任意公共独立集的计数与采样。
已 Lean 形式化
第一级台阶
导读的”两位鉴定师数宝物”可以改述为：有一批元素，两套各自讲道理的合格性标准——合格组合的任何一部分也合格、合格的组合总能换件扩充——要数的是两套标准都点头、件数拿满的组合。算法接触标准的唯一方式是问黑箱”这个子集合格吗”，从不要求标准的显式清单。二部图的完美匹配正是特例：两条标准分别是”每行至多一件”“每列至多一件”。
第二级台阶
用本科术语精确化。拟阵是满足遗传性与增广公理的独立集族，基是极大独立集；独立集预言机是回答”查询子集是否独立”的黑箱，这是最弱、最干净的输入模型。两个同秩拟阵的公共基即同时为双方基的集合，记其数目为 Z。FPRAS 指这样的随机算法：以多项式于 n、编码长 ℓ、ε⁻¹ 与 log δ⁻¹ 的时间，输出落中 (1±ε)Z 的估计、概率至少 1−δ。
第三级台阶
定理在这样的语境下陈述：对 [n] 上任意两个由精确独立集预言机给出的秩 r 拟阵，存在单一随机算法输出落中 (1±ε)Z 的 ̂Z；Z=0 时恒输出零；且在每次执行中，预言机调用与其余位操作都被 n、ℓ、ε⁻¹、log δ⁻¹ 的固定多项式界定。”精确预言机”挡住了输入端的近似误差，”同秩”配对归约所需、不同秩情形由推论处理，”每次执行”挡住了只控期望的弱保证。结论用导读的话说：拟阵交”计数缺算法”的四十年空格被填上，连带公共独立集的计数与几乎均匀采样。
本文在独立集预言机模型下，对任意两个同秩拟阵的公共基计数给出 FPRAS，每次执行的预言机调用与比特运算均多项式有界，肯定回答了 Liu 博士论文记录的公开问题，并连带解决公共独立集的计数与采样。
拟阵（matroid）是线性无关性的组合抽象：独立集族含空集、对取子封闭并满足扩充公理；基（basis）是极大独立集。独立集预言机（independence oracle）回答查询子集是否独立。Edmonds 证明拟阵交的优化问题在预言机模型下有多项式算法，计数却艰难得多：两拟阵取同，即得单拟阵基计数；在二部图边集上对两侧顶点各施加划分拟阵约束，公共基恰为完美匹配——Jerrum–Sinclair–Vigoda 的 permanent FPRAS 正好覆盖后一特例。单拟阵计数经历了 Feder–Mihail 的均衡拟阵、强 Rayleigh 分布的快速混合，直到 Anari–Liu–Oveis Gharan–Vinzant 用对数凹多项式与高维游走彻底解决。然而两个拟阵的公共基分布一般不再具有负相关性：Anari–Oveis Gharan–Vinzant 只得到 @@M@@2^{O(r)}@@ 因子近似，Cryan–Guo–Mousa 明确提出快速收敛马氏链的存在性问题，Liu 的博士论文把它记录为公开问题。本文给出肯定回答。
定理 1.1：存在单一随机预言机算法，对 @@M@@[n]@@ 上任意两个秩 @@M@@r@@ 拟阵 @@M@@M_1,M_2@@（各由固定精确独立集预言机给出）与有理数 @@M@@\varepsilon,\delta\in(0,1)@@，输出非负有理数 @@M@@\widehat Z@@ 满足
@@M@@D\mathbb P\bigl[(1-\varepsilon)Z(M_1,M_2)\le\widehat Z\le(1+\varepsilon)Z(M_1,M_2)\bigr]\ge1-\delta,@@
其中 @@M@@Z=|\mathcal B(M_1)\cap\mathcal B(M_2)|@@；若 @@M@@Z=0@@ 恒输出零。每次执行中，预言机调用次数与其余比特运算数都被 @@M@@n,\ell,\varepsilon^{-1},\log\delta^{-1}@@ 的固定多项式界定（@@M@@\ell@@ 为 @@M@@n,r,\varepsilon,\delta@@ 的二进制编码长）。算法只用无偏随机比特，不需要任何拟阵的显式表示。推论 9.1 更进一步：两拟阵秩可以不同，指定基数、任意基数与最大基数三种公共独立集族均有 FPRAS 与几乎均匀采样器（总变差距离 @@M@@\le\theta@@），空性判定是精确的。
先做配对归约（paired reduction）：把 @@M@@[n]@@ 复制成 @@M@@n@@ 对元素 @@M@@\{x_i,y_i\}@@，取直和 @@M@@K=M_1\oplus M_2^*@@（@@M@@M_2^*@@ 为对偶拟阵），秩为 @@M@@n@@。恰含每对一元的 @@M@@n@@ 元集称为横截集（transversal），而 @@M@@A@@ 是公共基当且仅当对应横截集是 @@M@@K@@ 的基。给秩亏 @@M@@d(S)=n-\rank_K(S)@@ 赋权 @@M@@f_q(S)=q^{d(S)}@@：@@M@@q=1@@ 时横截总权已知为 @@M@@2^n@@，@@M@@q@@ 退火到指数小时非基横截的权被压没，总权趋于 @@M@@Z@@；秩值用贪婪扫描、每次至多 @@M@@n@@ 个独立集查询即可算出。
纯正权不足以给出定量混合界，于是扩充状态空间：允许恰一个空对与一个满对的缺陷态，其有序指标为缺陷类型 @@M@@ij@@，每类配一个正乘子 @@M@@w_{ij}@@ 平衡总权，链以 Metropolis 规则做单元素交换。代数输入是 Brändén–Huh 的 Lorentzian 多项式理论（齐次 Tutte 定理）：由二次签名性质——偏导加非负代换所得二次型的 Hessian 至多一个正特征值——对选元素多项式 @@M@@F@@ 与省略元素多项式 @@M@@F^\vee@@ 分别应用，经反向 Cauchy–Schwarz 得到缺陷总量间的乘性不等式；再证运输不等式（transport inequality），把缺不同槽的两个条件分布的均值差控制为符号流的能量：递归指派平衡需求，分裂槽的代价由至多一个正方向的二次型界定，最后在叶团内以流实现。由此得到横截方差界与缺陷均值转移界。
关键一步是承认局限：这些工具只控制横截上的变异与缺陷类型的均值，看不见类型内部的任意波动。因此论文对迹链（trace，记录相继回访横截）证明逆谱隙至多 @@M@@18n^4@@ 的混合，而对算法真正平均的类型指示与比值可观测量建立分区限制的 Poincaré 不等式 @@M@@\Var_\pi(\mathsf QH)\le 2000n^6\calE(H)@@；热起始（warm start）由退火表上的独立重启供给。最后沿 @@M@@q_j=\rho^j@@ 的几何退火表逐相位估计相邻质量比与类型频率，按 @@M@@w_{ij}\mapsto w_{ij}\cdot\widehat p_0/\widehat p_{ij}@@ 学习乘子，连乘得 @@M@@\widehat Z=2^n\prod_j\widehat R_j@@；有理数位长与抽样次数均设上限，多次独立运行取中位数放大成功率。
主结果（含公共独立集推论）已由 Lean 形式化（结果族 114 的形式化文档）。本文是族内母篇：姊妹篇《An FPRAS for Common Integer Polymatroid Bases with Binary Capacities》正是把本文的运输与迹链框架推广到二进制容量整多拟阵的产物（该篇暂未形式化）。按 OpenAI 官方声明，未经形式化的结果可能有问题；本文主结果已通过形式化这一关。
问 1：证明里最关键也最脆弱的一步是哪里？
答：对自身局限的”分而治之”。Lorentzian 二次签名与运输不等式只控制横截层面的变异与缺陷类型的均值，看不见类型内部的任意波动；于是论文只对迹链（记录相继回访横截）证逆谱隙 ≤18n⁴ 的混合，另对算法真正平均的类型指示与比值可观测量证分区限制的 Poincaré 不等式 Var ≤ 2000n⁶·ℰ（引言 Proof strategy 第五段）。这条双轨若有一轨的”可观测类”没盖住退火估计实际需要的量，连乘计数就会在某个相位失准——这是全文设计上最吃劲的接缝。
问 2：为什么不直接把 ALOV 的对数凹多项式游走用在公共基上？
答：因为交运算摧毁负相关性：两拟阵取同得单拟阵计数没问题，但公共基的生成多项式一般不再对数凹、不再实稳定，强 Rayleigh 型混合论证全部失效——这正是 AOV2021 只拿到 2^{O(r)} 因子（仅 r=O(log n) 时全多项式）的原因。本文改走正权＋缺陷态扩充＋学习乘子的 JSV 式路线，混合靠迹链与限制 Poincaré 而非负相关。
问 3：与已有工作相比真正的新意是什么？
答：它是第一个对任意两个独立集预言机拟阵的无秩限制 FPRAS，肯定回答 Cryan–Guo–Mousa 提出的快速收敛链存在性与 Liu 博士论文第 13.2 节问题 1。代数新部件是把 Brändén–Huh 齐次 Tutte 定理对拟阵与其对偶各用一次，经反向 Cauchy–Schwarz 得互补的缺陷总量不等式，再配缺槽运输不等式——这套”签名＋运输”组合是可迁移的框架（姊妹篇已迁往二进制容量）。
问 4：主结果已 Lean 形式化，风险还剩什么？
答：定理 1.1 与公共独立集推论均已形式化，这是强背书。剩余风险在形式化边界：Metropolis 链、迹链与位模型的定义须与论文逐字对齐（如”每次执行”的计数是否真包含随机比特生成）；且形式化证的是存在性界，常数 18 与 2000 之类只保证多项式性，不承诺任何实用运行时间——引用者若当作可用算法会失望。
问 5：配对归约为什么恰好能行？
答：把 [n] 复制成 n 对，取直和 K=M₁⊕M₂*（秩为 n）：A 是公共基当且仅当对应横截集（每对恰选一元）是 K 的基；给秩亏赋权 q^d，q=1 时横截总权恰为 2^n（已知），q 退火到指数小时非基横截权被压没、总权趋于 Z。秩值由贪婪扫描经至多 n 次独立集查询算出——闭环全靠”已知起点＋可计算权重＋可学习乘子”三件事同时成立。
问 6：谁会用到它？
答：特例即红利：M₁=M₂ 重新得到单拟阵基计数；划分拟阵特例回到二部图完美匹配（JSV 的地盘）；推论 9.1 覆盖不同秩、任意指定基数的公共独立集计数与几乎均匀采样。框架层面，运输不等式＋迹链混合被姊妹篇推广到二进制容量整多拟阵，是族 114 的母篇。
总评
这是把拟阵交从”可优化”推进到”可计数”的母篇级工作，且经 Lean 形式化背书；最大风险不在主定理本身，而在其可观测类论证的窄门——以及后续姊妹篇沿着这条窄门继续加盖时是否仍站得住。