跳到正文
Hacker News· GPUboy·· 10 天前AI 评分12

整数乘法问题上界 PR 被合并:T(n) = O(n (log n)^(1 − κ)),κ = 3.850771033 × 10⁻⁵

They just merged my PR for the bound on the integer multiplication problem

AI 导读

Rohan Arun 借助 OpenAI Codex 的协助,将 icekylinx 的 copied-center 调度与 James Chang 的反向边界族在维度 (23,25) 上组合,把整数乘法问题上界的条件指数 κ 提升至 3.850771033 × 10⁻⁵,较 #36 报告的 κ 改进 0.132122792%。

正文 · AI 翻译

在保留的解析与固定有限字母多带假设下,

T(n) = O(n (log n)^(1 − κ)),其中 κ = 3850771033/10^14 = 3.850771033 × 10⁻⁵ > 2⁻¹⁵。

这将 icekylinx 的复制中心调度(#36,11817cc)与 James Chang 的反向边界族(#34,7fecbe3)在维度 (23,25) 下以及所归属的 RaD 平衡装配组合在一起。它将 #36 报告的 κ 改进了 0.132122792%;这比较的是条件指数节省量,而非实测运行时间。

变更与证明

数据剖面变为 9 个单例 + [21,17,481],取代 11 个单例 + [21,15,481]。每个复制中心变换以及全部 4,073,300 次付费秩一端点修正均保留。原始生产者选择、角色体积、总秩和最大子项均保持不变。新的秩一清理补集包含在同一公共基论证中。

精确比特节省为 962729831/25000000000000。未改变的 #36 复数节省为 717/10^7。语义包络明确保留标量门电荷 G;C1=1 且乘积行度为 2000。全部 47 个严格约束和七个裕度均通过,最终吸收间隙为正。

提交前已检查

  • 全部 25 个受控排列完成、两棵限制树、实际局部/辅助收缩、全部 47 个秩切割,以及三个精确有理枢轴见证。
  • 完整的物理核算与独立的逐类重建;旧剖面在新的节省量下因严格的低阶矩界而失败。
  • 在任意脏输入上双向的复制中心调度,包括相位复制方向和付费端点修正;包含限定范围的独立代理审查。
  • 12 个聚焦测试通过,包括损坏的源/秩切割控制、保秩子列表损坏、旧精度包络、无效行以及下一网格下界排除。
  • 聚焦补丁从固定的 用于条件 kappa = 3.84569e-5 的复制保留中心与两阶段装配 #36 逐字节重建 19 个文件。

完整重跑通过:make verify 在研究提交 cb86e50e9a07685068874d8e4174b2e6c209b95c 上成功完成:182 个测试、新选定的 h28/d19 复数生产者、继承的 h25/h23/h57 标量与正标签检查、历史复数 h28 重建,以及全部 18 个历史补丁检查。新的 12 个聚焦测试也通过。验证回执记录了完成情况和日志 SHA-256 020a0bb269ff326b34056e893484eb408ce0c06c3cae9ced920f64ba1f491f2e。仅生成了继承的 JSON 键顺序差异;已验证精确解析相等性并恢复了固定的历史文件。验证后续仅更改文档和回执,不更改科学源文件。刷新后的聚焦补丁重建 20 个文件。可供审查;未声称形式化验证或外部专家认可。

从 证明与复现指南 开始。运行 make copied-reversed-check、make copied-reversed-producer 和 make verify。继承的解析、磁带、路由、恢复、构造性设置和最终阈值假设保持明确。

归属

Rohan Arun 在 OpenAI Codex 的大量协助下提供了本作品及各项检查。致谢 icekylinx(#36 复制的中心/复杂图及更早的产出者)、James Chang(#34 反转族)、RaD/hipotures(均衡路由/语义/批量传输)、Dominik Scholz(#33)、Rohan Arun/Codex(#31)、Zhihao Chen(#29/#21/#23)、Aurel Prosz/Paureel、Swapnil Jain、eumemic、Douglas Colkitt、OpenAI、Harvey–van der Hoeven 以及所有保留的源声明。此处不主张所继承的技术为新增。Apache-2.0;原始许可证与 AI 协助披露保持不变。

来源:Hacker News · github.com