结果族 114：Approximate counting of common integer polymatroid bases · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
仓库里有 R 吨货要分进 n 个仓格，公司两个部门各有一套”任意几格合计最多装多少”的规章，两套规章都有”越多越不划算”的递减脾气；要数的是同时过两套关、恰好分完 R 吨的分法总数。麻烦在于 R 用二进制书写——可能是 2^100 这样的天文数字，挨个数一遍绝无可能。本文的随机算法耗时只随”数字写下来有几位”多项式增长，给出相对误差 ε 的计数估计。
关键词卡片
看个具体例子
取两个仓格 E={1,2}、R=3 吨；规章一：1 号格至多 2；规章二：2 号格至多 2。合法分法只有 (1,2) 与 (2,1)，故 Z=2。定理的数字版：@@M@@\Pr[(1-\epsilon)Z\le\hat Z\le(1+\epsilon)Z]\ge1-\delta@@。若把 R 换成 @@M@@2^{100}@@（编码仅 101 位），耗时仍多项式于位数，而合法分法数可达指数级——”数得动”靠的是估计，不是枚举。
为什么值得关心
它填上”两个多拟阵、容量二进制编码”这最后一格，把拟阵交计数与带容量运输计数统一覆盖，而且每次执行（不只平均）都有最坏情形多项式界；每个整数向量恰计一次。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的”仓库分货”可以改述为：把总量 R 的货分进 n 个仓格，两个部门各持一套”任意几格合计至多装多少”的规章，两套规章都有装得越多、边际越小的递减脾气；要数的是恰好分完且同时过两套关的整数分法。真正的麻烦在规模：R 以二进制书写，可能是 2 的一百次方，逐格枚举绝无可能，必须只随”数字有几位”耗时。
第二级台阶
用本科术语精确化。设 E 有 n 个元素，秩函数 r 从子集映到非负整数，满足归一、单调与子模性（边际递减的代数形式）；单个 r 的可行整数分配构成整多拟阵，两个同总秩 r₁(E)=r₂(E)=R 的整多拟阵的公共整数基，就是同时满足两套约束且总量恰为 R 的非负整数向量。FPRAS 指耗时多项式于 n、二进制编码长 ℓ、ε⁻¹ 与 log δ⁻¹ 的随机近似计数格式。
第三级台阶
定理在这样的语境下陈述：输入为二进制的 R 与两个精确秩值预言机——查询是 n 位子集指示、回答是二进制整数，不给分解、显式不等式表或任何采样装置——存在单一随机算法输出落中 (1±ε)Z 的 ̂Z，概率至少 1−δ；Z=0 时每次执行必输出零。核心加强在于界是”每次执行”而非仅期望：预言机调用与全部位操作都被 n、ℓ、ε⁻¹、log δ⁻¹ 的固定多项式控制。”秩值预言机”挡住了输入端作弊；”每个向量权重为一”挡住了把容量展开成带标签元素的路——那样既爆规模又改权重。结论用导读的话说：天文数字的容量，”数得动”靠估计。
本文证明：对两个由精确秩值预言机给出的同总秩整多拟阵，其公共整数基的计数存在完全多项式随机近似格式（FPRAS）——预言机调用与比特运算在每次执行中都只以地面集大小和容量二进制编码长度的多项式为界，且每个整数向量恰计一次。
整多拟阵（integral polymatroid）刻画带子模（submodular）容量约束的非负整数分配。设 @@M@@E=\{1,\dots,n\}@@，秩函数 @@M@@r_i@@ 归一、单调、子模且总秩相同 @@M@@r_1(E)=r_2(E)=R@@，要数的是同时满足两套约束的整数基——这是拟阵交（matroid intersection）与带容量运输问题的共同推广。多拟阵论源自 Edmonds 1970 年的工作：在秩值预言机下，可行性与优化都能多项式求解，计数却长期没有算法。障碍有二：其一，总秩与容量按二进制编码，单个坐标可取随 @@M@@R@@ 指数增多的值；其二，若把每单位容量展开成带标签元素（Helgason 的 hypermatroid 表示），实例规模与每个向量的带标签实现数（二项系数之积）同时爆炸，计数权被彻底改变。此前结果或固定维数（列联表方向：Dyer–Kannan–Mount、Cryan–Dyer、Bezáková–Bhatnagar–Vigoda 等），或含 @@M@@2^{O(r)}@@ 因子（Anari–Oveis Gharan–Vinzant 对公共基）。本文补上了”容量二进制编码、两个多拟阵任意”这一格。
定理 1.1（thm:main）：存在单一的一致随机算法，输入二进制给出的 @@M@@R@@、两个精确秩值预言机 @@M@@r_1,r_2@@（查询为 @@M@@n@@ 位子集指示，回答为二进制整数）及有理数 @@M@@\varepsilon,\delta\in(0,1)@@，输出非负有理数 @@M@@\widehat Z@@，满足
@@M@@D\mathbb P\bigl((1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z\bigr)\ge1-\delta,@@
其中 @@M@@Z@@ 是公共整数基集 @@M@@\Omega(r_1,r_2)=\{x\in\mathbb Z_{\ge0}^E:\ x(E)=R,\ x(A)\le r_i(A)\ \forall A\subseteq E,\ i\in\{1,2\}\}@@ 的基数，每个向量权重为一。若 @@M@@Z=0@@，算法每次执行都输出零。核心保证是：在每次执行（而非仅仅期望）中，预言机调用次数与其余比特运算都被 @@M@@n,\ell,\varepsilon^{-1},\log(\delta^{-1})@@ 的一个固定多项式界定（@@M@@\ell@@ 为 @@M@@n,R,\varepsilon,\delta@@ 的二进制编码长）。算法直接处理二进制容量，不展开为带标签副本。作者明言多项式的固定指数很大——重点是依赖关系，不是运行时间。
先做确定性准备：用子模极小化与有理分离—优化理论（Grötschel–Lovász–Schrijver）精确判定可行性，并用行列式替换构造公共基多面体的有理中心（rational center）。中心附近近似紧的秩不等式诱导 @@M@@E@@ 的两个划分，各部分总量被限制在中心周围多项式长的整数区间内——这些”端口”（port）就是算法保留的离散变量。
再消去其余自由度。在两个划分的关联二部图上取生成树，非树边坐标充当自由变量；其范围随 @@M@@R@@ 的数值增大，于是对秩违反施加凸的软惩罚，然后对自由坐标积分（Prékopa 边际定理保持对数凹性），得到关于端口总量的正的对数凹块权。几何端的比较论证（方向对数凹性加小同伦缩放）证明这个加权和以相对误差 @@M@@O(N^{-7})@@ 逼近 @@M@@JZ@@，其中 @@M@@J@@ 是一个可高精度计算的平移求和归一化因子。
但对数凹性不足以给出计数链所需的离散二次签名（signature）不等式。论文把积分权与紧支撑光滑核卷积，再乘以小的严格凹二次因子；导数估计控制离散二阶差分与连续 Hessian 的偏差，严格曲率在所有退火幂 @@M@@h^s@@（@@M@@0\le s\le1@@）下压住误差，使加性（addition）与省略（omission）两种签名检验在每一相位都通过。
最后组装计数。每个长 @@M@@d_v@@ 的端口用 @@M@@d_v@@ 对带标签元素表示，并定义两个阶乘修正权 @@M@@f,\widetilde f@@：在横截集（每对恰选一元）上二者的多重性因子严格抵消，平衡质量恰为未标记端口轮廓的质量。验证 @@M@@f@@ 具省略性质、@@M@@\widetilde f@@ 具加性性质且两者在缺陷类上相互可比之后，调用姊妹篇证明的运输不等式与迹链（trace chain）框架：沿 @@M@@k_j=(2^{-U}h)^{j/H_o}@@ 的乘方表退火，封顶重启提供热起始，链上观测估计相邻相位质量比与缺陷类频率以学习乘子 @@M@@w_{il}@@，连乘除以 @@M@@J@@ 的估计得到 @@M@@\widehat Z@@；每次权重评估由 Dyer–Frieze–Kannan 凸体积随机算法多项式完成。所有大型展开（展开拟阵、几何细分、运输流）只是证明装置，实际被采样的显式实例只含 @@M@@2p@@ 个元素。
本文暂无形式化证明。它站在两篇同族姊妹篇之上：母篇《Approximate counting of common bases of two matroids》（主结果已 Lean 形式化）提供正秩亏权、运输不等式与迹链混合的通用框架；cell-bounded 列联表篇提供双阶乘提升与封顶退火实现。本文的独立贡献是把二进制容量实例归约到显式规模为多项式的实例，并在积分之后重建所需的离散二次不等式。按 OpenAI 官方声明，未经形式化的结果可能有问题，本文结论请以社区核验为准。
问 1：证明里最关键也最脆弱的一步是哪里？
答：在积分之后重建离散二次签名不等式。自由坐标被软惩罚积分掉（Prékopa 边际定理只保住普通对数凹性），但姊妹篇的计数链需要的是离散的二阶差分不等式；本文把积分权与紧支撑光滑核卷积、再乘一个小的严格凹二次因子，靠导数估计控制离散二阶差分与连续 Hessian 的偏差，并要求严格曲率在所有退火幂 h^s（0≤s≤1）下压住误差（引言 Proof strategy 第四段）。任何一处曲率与偏差的常数比较失守，加性与省略两种签名检验就会在某个相位同时失效。
问 2：为什么不能把二进制容量展开成带标签元素再用拟阵交计数？
答：Helgason 的 hypermatroid 表示保持可行占用向量，但直接构造规模可达 nR，且一个占用向量带着二项系数之积那么多的带标签实现——计数权被彻底改变（引言开篇明言这两个困难）。而本文的问题恰好给每个整数向量权重一，展开后的计数对象根本不是原来的 Z。
问 3：与已有工作相比真正的新意是什么？
答：三个邻居都不够：ALOV 与 Lorentzian 多项式处理单个拟阵/多拟阵，取公共基会破坏交换性且阶乘归一化加权不均匀；AOV2021 对两个拟阵的公共基只有 2^{O(r)} 因子近似；列联表方向的结果或固定行数（DKM、Cryan–Dyer、CDR）或限 0/1 表（BBV）。本文首次对”两个任意整多拟阵＋二进制容量＋秩值预言机”给出相对误差 FPRAS，且每次执行都有多项式位界。
问 4：这个结果最可能以什么模式出错？
答：级联风险排第一：运输不等式与迹链混合整个引用姊妹篇《Parent》的特定陈述，双阶乘提升引用 cell-bounded 篇——虽然母篇主结果已 Lean 形式化，本文引用的具体接口条款未必都在形式化范围内。其次是连续—离散接口的比较常数：块权以相对误差 O(N⁻⁷) 逼近 JZ、DFK 凸体积算法的有理预言机实现精度，这些数值链条一旦有一环松动，签名验证的前提就不成立。本文自身无形式化证明。
问 5：为什么强调”每次执行”的多项式界，而不是通常的期望界？
答：因为二进制模型下尾风险与主体同阶：算法内部要调用凸体积随机算法评估权重、还要生成随机比特，若只控制期望时间，单次超长执行会破坏”位操作被固定多项式界定”的承诺。定理 1.1 特意把预言机调用数与其余位操作分开列出，且预言机计算本身不计费、写查询读回答计费——这是最干净的输入—计算分界。
问 6：谁会用到它？
答：它是拟阵交计数与带容量运输计数的公共上界：凡能把可行集写成两个子模系统的公共整数基的计数问题（多类分配、网络流整数解、列联表的推广）都自动获得 FPRAS。方法学上，”端口归约＋积分后重建签名”是把固定维数技术推广到二进制容量的可复制模板。
总评
本文填上了”两个多拟阵、容量二进制编码”这一格，覆盖面是三代列联表与拟阵交工作的真并集；最大风险在于它是一座三脚塔——自身的卷积签名论证加两篇姊妹篇的进口条款，任何一脚都未经完整形式化。