跳到正文
Hacker News· mcmoor·· 9 天前AI 评分21

社区将 OpenAI 整数乘法 FFT 证明的指数改进推至 10^-4 以上

Community pushed OpenAI FFT proof to over 10^-4

AI 导读

社区研究者在 OpenAI #109 框架基础上，将整数乘法 FFT 证明的指数节省 κ 推进到 4.609169×10^-4，由 icekylinx 在 PR #144 中贡献，采用配对立方体与共享核心构造。

正文 · AI 翻译

整数乘法的更锐指数

由 Douglas Colkitt 维护的社区研究——以原始 OpenAI #109 框架为条件。

当前经评审的结果：配对立方与共享核心

由 icekylinx 在 PR #144 中贡献、基于 PR #130 的构造给出

$$ T(n)=O!\left(n(\log n)^{1-\kappa}\right),\qquad \kappa=\frac{4609169}{10000000000}=4.609169\times10^{-4}. $$

一个带符号的配对立方生成器与坐标星中心使用原始源寄存器补全该恒等式。完成的脏核心在三个正交块上复用一个辅助库，采用 an664 的 PR #128 共享原则。位分支从保留的 PR #97 / Swapnil 字中选择经认证的规范。所有局部转移、复制中心、补码调用、有限路由器和稀有类回退均计入开销。解析、均匀递归和固定纸带假设均保留。

这是此前经评审的主要节省的 9.03 倍，约为 2^-11.0832：高于 2^-12 且低于 2^-11。它衡量的是渐近指数节省，而非实际运行时加速。

维护者评审与验证范围 · 当前结果记录 · 证明来源 · 精确证书 · 增量复现

make paired-cube-verify

此前三阶段覆盖扩展

由 icekylinx 贡献、扩展 PR #115 的构造给出

$$ T(n)=O!\left(n(\log n)^{1-\kappa}\right),\qquad \kappa=\frac{3146011}{10000000000}=3.146011\times10^{-4}. $$

在正则 Cayley 覆盖上的三个带符号剪切对齐所有级间数据帧。复分支将 eumemic 的 PR #117 局部 DAG 与任意子空间 Clifford 帧结合；位分支保留 PR #97 / Swapnil 物理字并使用批量加权 q-adic 覆盖。局部转移、复制中心、稀有类回退、有限路由器和内部行借用均计入开销。保留的解析和固定纸带假设仍然适用。

证明来源 · 精确证书 · 增量复现

make three-stage-cover-verify

此前部分规范扩展

由 icekylinx 贡献、扩展 PR #104 的构造给出

$$ T(n)=O!\left(n(\log n)^{1-\kappa}\right),\qquad \kappa=\frac{7237}{78125000}=9.26336\times10^{-5}. $$

它将停止的全投影器位接口应用于 Zhihao Chen 的 PR #97 的物理延迟字，基于 Swapnil Jain 的见证。新的复生成器结合循环区间收缩、配对优先立方组装、兼容帧放大和部分源规范。每个残差、端点校正和目标数据转移均计入开销。该界保留此前构造的解析和固定纸带假设。

证明来源 · 精确证书 · 增量复现

make partial-gauge-verify

此前停止的乘积环扩展

由 icekylinx 贡献、扩展已合并的 PR #36 的新构造给出

$$ T(n)=O!\left(n(\log n)^{1-\kappa}\right),\qquad \kappa=\frac{194869}{2500000000}=7.79476\times10^{-5}. $$

它将 (23,23) 上的停用产品环位交换与 (24,24) 上的全不相交有理中心复网络结合在一起。新的通用对岸因式分解为每个投影仪秩支付一个反向子节点；原子适配器、普通叶节点、端点副本以及精确的分母为 21 的网格都包含在证明中。该界保留了原有的解析假设和固定磁带假设。

证明来源 · 精确证书 · 增量复现

make stopped-product-verify

下面这个经维护者审核的社区检查点仍是其自身的结果和验证记录。

历史审核社区检查点

经审核的社区见证给出

$$ T(n)=O!\left(n(\log n)^{1-\kappa}\right),\qquad \boxed{\kappa=\frac{25508460085039}{500000000000000000} =5.1016920170078\times10^{-5}>2^{-15}}. $$

这比之前的 PR #49 版本高出 23.71%，且仍低于 2^-14。 这是渐近指数节省方面的改进，而非实测运行时间的加速。该模型和一般归约继承自 OpenAI 的 Integer multiplication below n log n。

维护者审核与贡献台账 · 有限电路证明 · 选定参数证书 · 独立算术检查

变更内容

Avi Eisenberg 的区间条带与核心感知配对组装（#62）安排加法以允许更多物理线路复用。结合 eumemic 的联合帧编译器（#57），这产生了本批次中最强的有限网络。 Alejandro Zarzuelo Urdiales 的精确参数细化与限定范围 Lean 证书（#61）提供了选定的数值。

该位网络有 m=575 和 137,151,806 个物理角色；其经认证的递归节省为 102039046058023/2000000000000000000。该复网络保留节省 717/10^7。所有递归子节点、工作区恢复、复制的中心以及端点成本仍被计入。七个最终指数裕度严格为正。

之前由 Avi 的跳过前缀条带（#53）、Rohan Gupta 的双后缀布局（#55）、eumemic 的编译器以及 Chafik Boukhalfa 的组合与排序回收（#58/#60）组成的组合也完全保留并经过审核。

其他经审核的贡献即使其数值见证被取代也予以保留：RaD 的扩大帧与克隆机制（#51）、Rohan Arun 的正帧组合与顺序搜索（#52/#56）、Rohan Gupta 的并行顺序搜索（#50）、Chafik 的原始包络克隆（#54）以及 Rohan Garg 的分割对递归（#59）。审核记录了每项贡献的确切验证范围。

署名

以下名称标识 GitHub 贡献者；它们不是经过验证的 Twitter 账号。

  • Avi Eisenberg (ikeboy)：跳过前缀与区间条带、核心感知配对组装（#53、#62）。
  • Rohan Gupta (gupt1156)：双后缀条带与并行顺序改进（#50、#55）。
  • eumemic：联合帧编译与付费回收（#57）；早期的复电路、高斯重采样与源帧。
  • Chafik Boukhalfa (chafreaky)：精确恢复、独立检查器、重排序求和、付费克隆以及联合编译器组合/精化（#43/#46/#48/#54/#58/#60）。
  • Rohan Arun (rohanarun)：角几何、固定基组合、加权匹配、顺序搜索和正框架组合（#49、#52、#56）。
  • Rohan Garg (rohangar1)：分裂对递归、顺序精化和付费克隆组合（#59）。
  • Alejandro Zarzuelo Urdiales (alejandrozu)：高斯奇偶性和有限张量证明、矩阵/搜索工具、精确精化和作用域 Lean 算术（#45、#61）。
  • RaD 项目 (hipotures)：语义精度、路由、相位单元反转、批量重采样、交替生产者、物理编译器和扩大框架/克隆机制（#41、#51）。
  • icekylinx：停止递归、三阶段覆盖、加权局部环编译、配对立方体构造和选定的集成（#104、#115、#130、#144）；早期的批处理、部分交换和复制中心。
  • an664：完成核心工作区共享（#128），这是当前结果的重要依赖。
  • eumemic：配对立方体构造所使用的受限正生产者（#117），以及上文已致谢的早期工作。
  • Zhihao Chen 和 Swapnil Jain：延迟物理位账本（#97）以及所选位构造所使用的底层冻结字和提升框架。
  • Zhihao Chen (jacklightChen)：受控基、平移框架、语义/批量兼容性和两阶段集成。
  • James Chang (jamesyc)：反转两阶段几何和精确控制。
  • Aurel Prosz (Paureel) 和 Swapnil Jain：归属的两阶段开发和付费复制流端点。
  • Dominik Scholz：维度、参数和固定基精化。
  • Ryan S (princezuda)：历史 Lean 证书、代数契约和独立电路检查（#26）。
  • Andrew Barnes (Bortlesboat) 和 David Leen (dleen)：对齐配对、保留总计和共享。

完整贡献记录分别列出已纳入、并行、被取代和待处理的工作。Douglas Colkitt 维护项目、原创研究、评审和集成，并得到 OpenAI Codex 的协助。OpenAI 的原始手稿和 Harvey–van der Hoeven 的分析工作保留其署名。贡献者特定的 AI 披露保留在 NOTICE 中。

证据与局限

第二轮评审扩展了此前的后续审计和PR #39 转移评审。原始 #109 框架和保留的全尺寸接口仍是假设。这不是完整形式验证、独立人工同行评审、全球优先权主张或实用乘法基准。

新的检查覆盖完整的已发射词和脏基向量、物理帧转换、精确固定基剖面、保留几何的全部 4,073,300 个数据对，以及独立的有理递推/组装算术。形式化包验证了其声明的有限/算术契约。PR #61 的集成公理审计包含 169 个不同的声明，其中包括 11 个具体的前沿定理；其输入行绑定到重放的有限剖面。它们并未形式化整个乘法算法。

审查回执区分了维护者的新检查与贡献者提供的证据。先前的见证、补丁和归属仍然可用。#62 之后的提交不在本次检查点的审查范围内；确切审查的头部记录在账本中。

复现

make verify-pair
make verify-joint
make verify-positive
make formal-matrix-verify
# Complete arithmetic, producer, historical and unit-test suite:
make verify

完整算术套件需要 Python 3.11+、C++17 编译器和 Boost 头文件。形式化目标使用其固定的 Lean 版本。参见复现详情和CI 布局。

历史见证与独立补丁

每个补丁独立应用于未修改的固定源；它们是替代方案，而不是要一起应用的序列。结果历史记录了较早的机制和限定范围的上限。保留的研究索引收集了中间压缩、路由、Fano 和核心搜索，包括限定范围的负面结果和可复现的证书。

补丁 条件节省 范围
frozen-154 2^-154 原始网络和递推指数
balanced-153 2^-153 平衡组装参数
same-network-129 2^-129 原始网络，更精细的递推比较
h46-111 2^-111 更小的网络，二进参数
h46-109 2^-109 有理递推节省，严格的最终余量
h46-108 2^-108 可变停止指数
h46-rational 5.8e-33 提供的最强仅参数见证
nonadjacent-layout 保留原始参数 仅路由证明和修订布局成本
frozen-nonadjacent-107 2^-107 直接路由，原始网络和递推指数
h46-nonadjacent-78 2^-78 使用 h = 46 网络的直接路由
h46-nonadjacent-76 2^-76 使用调优维度和停止参数的直接路由
h46-shared-side-75 2^-75 阶段 1/阶段 3 侧角色共享、路由和参数调优
h46-incidence-67 2^-67 矩形关联电路、完全辅助共享、路由和参数调优
h46-dag-63 2^-63 共享中间和与可逆角色分配
h46-shared-point 13*2^-66 跨组共享
h50-paired-59 2^-59 配对和、停止保护与更紧的高斯设置
compact-control-34 83/10^12 > 2^-34 紧凑控制、完整预留、局部修复和独立复数元数
complex-compression-31 2^-31 加权复数电路、二进制相位帧和完全辅助共享
ternary-30 2^-30 三进制五子集电路、有理帧和固定字母表互换

引用与许可

使用 CITATION.cff，引用所使用的各项贡献，并包含仓库版本或提交。CONTRIBUTORS.md、NOTICE 和源特定清单保留了依赖项署名。

本项目采用 Apache-2.0 许可。捆绑的 RaD 源代码保留其单独的 CC0 许可和声明。固定的原始 OpenAI 手稿在 upstream/ 下保持不变；其源哈希位于 upstream/manifest.json。 本项目并非 OpenAI 官方发布或认可。

来源：Hacker News · github.com

OpenAI / ChatGPT开源生态数据与训练论文研究#论文/研究#开源/仓库#数据/训练#OpenAI