随机生成元的期望 Frobenius 数 · 公开问题 08

问题

在 [1,n] 中均匀随机取 k 个互素生成元（或条件于 gcd 为 1），问 Frobenius 数 F 与亏格 g 的期望与分布。Arnol'd（1989）对固定 k、生成元范围趋于无穷的情形给出期望的渐近主项（n^1−1/k 型的 «临界» 标度，与 «随机丢番都逼近» 的机制相符）；分布的精细形状（方差、极限律）以及 «固定生成元范围、k→∞» 的对偶情形都未完成。本条目给出可完整证明的确定性骨架（子半群比较原理与上界），并交代概率侧的文献口径。

主要概念

子半群比较原理

若 S ⊆ S′（半群包含），则可表示集更大，故 F(S′) ≤ F(S) 且 g(S′) ≤ g(S)。特别地 ⟨a₁,a_k⟩ ⊆ S ⟹ F(S) ≤ a₁a_k−a₁−a_k：随机情形立即得 F ≤ n² 的一致上界。反过来，«所有生成元都大» 的事件给出下界：min 生成元 > M ⟹ [1,M]∖S 非空 ⟹ F ≥ M−1 的变体（精确：一切 ≤ M 的数都是间隙 ⟹ F ≥ M）。这两条夹逼给出期望的正确标度区间。

Arnol'd 的临界标度

固定 k、生成元均匀于 [1,n]：典型情形最小生成元 a₁ ~ n/(k+1) 量级，F 的主项由 «多重格点覆盖» 的临界现象决定——Arnol'd 计算出期望的 n^1−1/k·C_k 型主项（对 «归一化» 后的量；原始 F 的标度随参数化方式而异，文献中不同 «归一化» 并存，阅读时须核对设定）。分布侧：极限律的存在性与形状（Gumbel 型？稳定律？）开放。

主要命题与证明

命题 1（比较原理与一致性上界；完整证明）　若 gcd(a₁,…,a_k) = 1 且 a₁ ≤ … ≤ a_k，则 F(a₁,…,a_k) ≤ a₁a_k − a₁ − a_k ≤ n²（生成元 ≤ n 时）。相应地亏格 g ≤ (a₁−1)(a_k−1)/2 ≤ n²/4。

证明　⟨a₁,a_k⟩ ⊆ ⟨a₁,…,a_k⟩ = S（子半群），可表示集包含 ⟹ 间隙集被包含 ⟹ F(S) ≤ F(⟨a₁,a_k⟩) = a₁a_k−a₁−a_k（01 号命题 2 的两生成元公式）。a₁,a_k ≤ n 得上界。g(S) ≤ g(⟨a₁,a_k⟩) = (a₁−1)(a_k−1)/2（Sylvester 计数，01 号）同理。□

命题 2（期望的初等夹逼；完整证明）　生成元独立均匀于 [2,n]（条件于整体 gcd 为 1）。则 E[F] ≤ n²，且 E[F] ≥ (n/2)·ℙ(min 生成元 > n/2) = (n/2)·(1/2)^k（无条件版；条件概率版本常数相应调整）。

证明　上界：E[F] ≤ max F ≤ n²（命题 1）。下界：所有生成元 > n/2 的事件 E 上，[1, ⌊n/2⌋] 中每个正整数都不是生成元的非负组合（任何非空组合 ≥ 最小生成元 > n/2），故 1,…,⌊n/2⌋ 全是间隙，F ≥ ⌊n/2⌋。于是 E[F] ≥ E[F·1_E] ≥ ⌊n/2⌋·ℙ(E) = ⌊n/2⌋·(1/2)^k（独立性）。□

命题 3（Arnol'd 渐近与开放层；文献口径陈述）　固定 k ≥ 2：Arnol'd（1989）对相应归一化的期望给出 n^1−1/k 型主项与显式常数（对 k=2 可与两生成元公式 ⟨a,b⟩ 的 F ~ ab 的 «条件期望» 版本交叉验证）。开放：（i）分布的极限律与方差渐近；（ii）对偶情形——生成元范围固定、k → ∞（此时 F 的 «相变»：生成元个数超过某阈值后 F 骤降，阈值附近的标度行为无结果）；（iii）亏格 g 的期望公式（与 02 号计数耦合：随机半群 vs 半群随机）。

现状说明　概率侧的技术瓶颈与 «随机丢番都逼近» 共享：临界覆盖现象的 «多重尺度» 分析在 k ≥ 3 时需要高维格点计数的精细渐近，现有工具（第二矩、 Poisson 克隆）只给出部分层。对偶情形 (k→∞) 则是 «覆盖阈值» 问题，与加法组合的覆盖系统（如 ⟨2,3,…,⟩ 密度阈值）呼应但无定理。□

进展与文献

Arnol'd 关于 Frobenius 问题统计的系列工作（1989；精确条目见 Ramírez Alfonsín 专著《The Diophantine Frobenius Problem》的随机章节综述）；Ramírez Alfonsín 专著《The Diophantine Frobenius Problem》的随机章节；Bourgain–Chen 的相关均值估计。开放核心：极限分布律；对偶 (k→∞) 相变；随机半群的其它不变量（type、弹性，与 09、40 号耦合）的期望。