AFTD Auto-Formalizing Theoretical Domains

周报 · 2026-W42 · 2026年10月12日至18日

负面额邮票扩大邮资范围,互信息次可加性不成立

English

一分钟看本周

本周解决了离散数学与信息论领域的数个未决问题。研究证实,允许负面额能严格增加邮票组合所能覆盖的连续整数范围。在信息论中,互信息的次可加性在赫林格距离与四分之一次方散度下被否定。在图论方面,新成果分类了团数谱界的成立条件,解答了由图跳跃生成的置换群的相关问题,并确定了圈图各次幂的精确覆盖数。

  • 3 证明
  • 2 否定
  • 1 部分结果
  • 1 新结果
  • 4 形式化验证
  • 5 仍未解决

本周故事

负面额邮票扩大8枚邮票所能覆盖的连续邮资范围

设想这样一个邮政系统:每个包裹必须从固定的4种面额(其中一种可以为0)中最多选用8枚邮票,贴出准确的总面值。数学家研究的是,在遇到第一个无法支付的金额之前,连续整数邮资能够不间断地延伸多远。

当所有邮票面额都必须为正时,穷举搜索表明,4种面额所能达到的最长连续区间涵盖了从0到89的每个整数,由面额0、1、9和14实现。长期以来人们认为,允许负面额——实际上相当于让收件人能够找零——在如此小规模的系统中无法提高这一上限。

这一预期在8枚邮票的情况下落空了。一项最新验证的构造表明,选取-4、1、13和14这4种面额,可以形成一条一路延伸至99的连续有效金额链。

允许单个负面额所带来的额外灵活性,超越了同等大小的任何纯正数面额集合,证明了负面额能够严格增大4面额集合的覆盖跨度。

本周全部结果

  1. 证明

    含一个负面额的4种邮票可达到99个连续邮资额

    在4种邮票中允许一个负值,可让8枚邮票达到的连续总值多于任何4种正邮票类型。

  2. 形式化验证

    通过极小零和界定二维整数盒的达文波特常数

    二维整数网格中的长序列在达到某一精确长度之前,可以避免出现和为零的子序列。

  3. 证明

    当圈长模4余2时圈图三次幂的等价覆盖数等于4

    当圈的长度除以4余2时,用等价关系覆盖圈图三次幂的所有边需要4个关系。

  4. 形式化验证

    7个矩形的蒙德里安分割可无穷多次达到缺陷值280

    用7个互不相同的整数矩形密铺大正方形,可将最大与最小图块的面积差控制在280。

  5. 证明

    五块图强谱团数界的完全分类

    通过矩阵特征值界定最大完全子图规模的强公式,在五块图上除3个无限族外均成立。

  6. 否定

    含偶圈的皮划艇桨图绝不生成对称或交错跳跃群

    当由一条路径连接2个圈构成的图含有偶圈时,其跳步置换无法生成全置换群。

  7. 部分结果

    当一侧可传递时竞赛图有向连接的反转值具有对称性

    若其中一个竞赛图可传递,无论连接顺序如何,将2个竞赛图单向连接后变为无圈所需的反转次数都相同。

  8. 否定

    赫林格散度与四分之一次方散度的互信息次可加性不成立

    在2个条件独立观测中共享的信源信息,可以严格大于各个单独共享的信息之和。

  9. 形式化验证

    确定性带截止时间分页的竞争比下界为k加1/2

    管理带截止时间内存缓存的算法,其性能无法优于离线最优解的k加1/2倍。

  10. 形式化验证

    确定性公平分配不存在时仍存在两全其美的公平抽签

    即使没有任何单一物品分配能够做到,物品分配的抽签也能同时保证平均和最坏情况下的公平。

仍未解决

本文由模型(gemini-3.8-flash)根据本期经 Lean 验证的结果撰写,并从英文版翻译而来。文中提到的每个定理都经过 Lean 检查;本摘要只是阅读辅助,本身未经机器检查。