大卫·哈维评测近期关于 o(n log n) 整数乘法算法的论文

关于最近提出的 $o(n \log n)$ 整数乘法算法

David Harvey，新南威尔士大学悉尼分校 2026年10月20日

摘要

我对最近提出的、据称复杂度为 $o(n \log n)$ 位运算的整数乘法算法提出一些看法。

1 执行摘要

我没有核对大部分细节，但我认为所声称的 $o(n \log n)$ 边界是合理的。

2 声明

本笔记在编写时没有使用人工智能协助，但以下情况除外：(a) 排版（即 TeX 魔法），(b) 校对，以及最重要的是 (c) 广泛的讨论以帮助我理解新算法。整个过程中使用的主要系统是 Claude Fable 5.1。

3 引言与背景

某家美国科技公司（以下简称“该公司”）最近在 GitHub 上倾倒了大量手稿。这份“数学资料转储”包含许多惊人的主张和结果。我一直在努力寻找合适的词汇，向我那些非数学专业的同事传达这些发现的惊人之处。其中有一篇论文特别吸引了我的注意 [TC26a]。它提出了一种用于相乘的新算法

n 位整数，声称它在多磁带图灵模型或布尔电路模型中以 $o(n \log n)$ 的位运算时间运行。小写的“ o”并非笔误。更准确地说，该论文声称存在一个形式为 $O(n(\log n)^{1-\varepsilon})$ 的复杂度界限，其中 $\varepsilon$ 是某个很小的正常数。这个界限当然极其荒谬。在此之前，最好的界限是 $O(n \log n)$（大写的“ O”），并且这被普遍认为是最佳的。该转储包含许多其他荒谬的结果，但其中大多数至少应该是真的。而这个并非如此。然而，这是一家有着严肃做事记录的严肃公司，因此我们应该努力认真对待这一主张。1我想祝贺该公司，或者更准确地说其员工，创造了一个具有这些惊人能力的模型。我的理解是，这些人中实际上没有人知道该模型是如何工作的。他们绝大多数人也不理解他们刚刚公开发表的论文的内容。我还想祝贺未命名的模型本身。既为了它 brilhant 的创意，也为了它在不可思议的困难面前的坚持。我假设到目前为止，该公司员工已经意识到这一事件在我的专业界引起痛苦和深刻的失落感。我相信他们是正派且勤奋的人，他们的努力真诚地旨在使世界变得更美好。我希望并祈祷他们成功。我的一些同事认为这是一家邪恶的公司，其唯一的目的是盈利，必要时甚至以牺牲我们的社群为代价。也许这有一定道理，但我觉得这忽略了更宏大的问题。事实是，现在存在一个能够进行数学研究的自动化系统——至少是涉及“解决难题”的那部分——比任何人类都要好得多。既然这样一个系统已经得到了展示，很显然，诸如此类的结果无论如何很快就会开始出现。我不怪该公司率先抵达。谁率先抵达是一个不重要的细节，是一个历史的注脚。我相信这不是一次性的。在不久的将来，该模型或具有同等能力的模型（可能由另一家公司开发）将被公开发布。起初它会很昂贵，但随后会变便宜，甚至可能是免费的。它的能力将继续提升。更多的数学结果将以越来越高的频率出现，不仅由该公司及其同行产生，还将由能够访问这些普通人产生。我社群中的每个人都必须应对这些后果。例如，我怀疑人类在不久的将来还能被当作数学研究论文的作者认真对待，原因与我们不再接受本科生的书面作业一样。我们可能已经达到了这个节点；我们很快就会知道。这里不是深入探讨我对人工智能更广泛影响的看法的地方，但我可以推荐 Zvi Mowshowitz 的优秀博客（ https://thezvi.substack.com/ ），他对人工智能的看法与我大体相似。从他浩瀚且让人欲罢不能的文字中，我学到了大量的知识。Zvi，如果你正在阅读这篇文章，非常感谢你的付出，它们受到了极大的赞赏。现在回到 $o(n \log n)$ 整数乘法的结果。这项新工作直接建立在我本人和 Joris van der Hoeven [HvdH21] 描述的 $O(n \log n)$ 算法（以下简称“2021 算法”）的基础之上。网络上的许多评论都集中在 $(\log n)^\varepsilon$ 相对于先前 $O(n \log n)$ 纪录的改进是多么疯狂地小，特别是喋喋不休地谈论 $\varepsilon$ 那微小的数值。在最初的撰文中，$\varepsilon$ 为 $2^{-182}$，这意味着 $\log n$ 的指数大约是 $0.999999999999999999999999999999999999999999999999999999984$。

但以我来看，这实际上是一个令人震惊的巨大进步。为了说明这个差距有多大，回想一下，当弗雷尔（F¨ürer）在2007年建立他的 $O(n \log n \cdot K\log ^* n)$ 界限时，他比之前最先进的成果——即1971年具有划时代意义的Sch¨önhage–Strassen $O(n \log n \log \log n)$ 界限——所取得的改进甚至小于 $\log \log n$。而后来我和范德霍文（van der Hoeven）的工作（以及沿途的其他几篇论文）所做出的后续改进，比这还要小得多、多、多。新工作中宣称的 $(\log n)^\varepsilon$ 的改进

比所有这些都要呈指数级大。$\varepsilon$ 的实际值并不重要。这是一个巨大的差距。英语里有很多表示“大”的同义词，但对于我想表达的意思来说还远远不够。我怀疑全世界极少有人（即人类）能完全理解2021年算法的所有细节，但我恰好是其中之一。这使我处于一个罕见的位置，具备了能够立即对这项新工作进行评论的背景。

4 执行摘要（长版本）

最核心的结论是，我认为所声称的结果是合理的。我实际上并没有读过这篇论文。事实上，有三篇紧密相关的论文 [TC26a]、[TC26b]、[TC26c]，我一篇都没读。我尝试过，但不久就放弃了。这堆数学公式似乎在阐述说明方面不够强大。相反，我让 Fable 给我解释 [TC26a]。Fable 似乎理解了这个论证，并认为它是正确的。我预计在过去的两周里，全球有数千个前沿大模型实例得出了相同的结论。如果没有，我们现在肯定已经听说了。起初我并不理解 Fable 的解释。但我不断提问，接着提出更多问题，并深入挖掘问题的核心。渐渐地，我开始理解了论证的一部分。我现在看到的已经足够让我初步相信，主要结果可能是正确的（请注意我措辞非常谨慎），并且 $O(n(\log n)^\alpha)$ 的界具有正确的形态。我要强调的是，我并没有以任何严肃的详细程度去检查证明，还有很多部分我尚未完全理解。在下面的章节中，我将尝试解释我目前所学到的知识，以及为什么我倾向于认为它是正确的。顺便说一句，当我说这堆数学公式“在阐述说明方面似乎不够强大”时，我的意思仅仅是，作为该领域的人类专家，我很难理解它（特别是 [TC26a]）。我从其他人类专家那里也听到过类似的评论，针对的是这堆资料中的其他论文。但就 Fable 而言，[TC26a] 中的阐述非常清晰。所以也许问题不在于阐述本身，而在于我们人类。在人工智能出现之前，针对不同的受众，采用不同的阐述风格或水平就已经很普遍了。也许我们需要让大模型“像向人类解释那样向我解释”（ELIH）。我还想强调这种情况的另一个方面。经过两周的艰苦努力，我只勉强理解了 [TC26a] 的一小部分。当我向 Fable 询问这篇论文时，它似乎只需几分钟就能阅读并理解整篇论文，甚至是从一个新的上下文开始。我知道有些读者可能会对我的拟人化用语感到不适，但我相信“理解”这个词是准确的，因为大模型似乎能够正确、清晰地回答关于这篇论文的各种问题，包括一些非常繁琐的技术细节。这正是我用来判断人类同事是否“理解”了某事的方法。人类与大模型“思考速度”之间的这种鸿沟，至少可以说是令人不安的。如果能有一个形式化的 $o(n \log n)$ 结果证明，例如在 Lean 中，那就太好了。据我所知，目前还没有这样的证明。以目前的技术来看，这种形式化似乎是可以实现的，但仍然不容易。如果结果是正确的，我预计很快就会有形式化的版本出现。如果存在这样的形式化版本，前提是初始定义和主要定理的陈述已经由（人类？）Lean 专家检查过，我对该结果的信心将会大大增加。我要道歉，因为在这篇笔记中，我没有保持我一贯的严谨和学术水准。一切都发生得太快了。特别是，由于我的无知和/或疏忽，我要向那些在这篇笔记中使用了其工作但未给予充分归属的人致歉。也许有一天我会进行更仔细的尝试，尽管我怀疑大模型会抢在我前面。在进入解释之前，我想提及主要结果的一些推论，前提是它是正确的：

ˆ 现在有一个量，我建议称之为“整数乘法的指数”。它是实数 $\alpha \geqslant 0$ 的下确界，满足存在一个运行时间为 $O(n(\log n)^\alpha)$ 的整数乘法算法。我们此前认为 $\alpha = 1$，但该模型断言 $\alpha < 1$。已经有一些人改进了 $\alpha$ 的数值。在撰写本文时，最佳值似乎是 $\alpha \approx 0.9983$，但当你读到这里时，这个数字肯定已经过时了。事实上，$\alpha$ 可能有两个不同的版本：一个是仅考虑算术成本的“布尔电路”版本，另一个是还包含数据重排成本的“图灵机”版本。我完全不清楚这两个指数是否应该取相同的值。有些人问我，$\alpha$ 可以降到多低？我当然毫无头绪，但我想提及一个障碍。在 [HvdH21] 中，高斯重采样步骤的总耗时为

O(n(\log n)^{3/4})。正如 [HvdH21, §4.4.2] 中概述的那样，这一步骤可以改进为 O(n(\log n)^{1/2})。因此，如果不在这里作进一步改进，或者不采用不依赖于高斯重采样的新方法，似乎不可能做到比 $\alpha = 1 /2$ 更好的结果。一种不依赖于高斯重采样的方（法）是 [HvdH22] 中的变体，但不幸的是，这需要某些未经证明的数论假设。最近几周，解析数论取得了如此巨大的进展，或许值得重新审视一下。无论如何，我们距离 $1 /2$ 的极限还非常遥远，所以我建议目前不要过度思考它。

ˆ 结合 [AFKL19] 的布尔电路下界结果，这一新结果推翻了李—李网络编码猜想（Li–Li network coding conjecture）[LL04]。

ˆ 新结果并没有直接暗示在固定有限域上多项式乘法的新复杂度界，比如在 $\mathbb{F}_2[x]$ 中的乘法。该问题的目前最高水平是一个在时间 $O(n \log n 4^{\log^* n})$ [HvdH19] 内相乘度为 $n$ 的多项式的算法。我无法立即看出如何将新方法适配到该算法中。不过，[HvdH22] 的方法也适用于有限域上的多项式，并在某些数论假设下实现了更好的界 $O(n \log n)$。该算法的结构表明新技术是适用的，并且它们会将复杂度降低到

O(n(\log n)^\alpha)（但仍然是有条件的）。

ˆ 我最近关于快速枚举素数的论文 [Har26] 极大地依赖于 $\mathbb{F}_2[x]$ 中的快速乘法。也许可以通过代入刚刚提到的（有条件的）乘法算法来改进该论文的结果。我粗略看了一下，似乎4瓶颈变成了“受限乘积”的计算。所以我不确定，但这绝对让人很想去研究。需要谨慎行事，因为论文当前框架或多或少地假设乘法成本为 $\Omega(n \log n)$；如果没有这个假设，就必须从头审查整个复杂度分析。

ˆ 当 $O(n \log n)$ 整数乘法结果于 2019 年 3 月首次宣布时，Fredrik Johansson 在 Reddit 上写道：

唉，在这片排版乌托邦停留了七年之后，我们如今注定要在上标和花括号的荒原中永远流浪。或者，如果你愿意，你可以继续写 O(n log n)。你不会受到任何伤害。

5 2021 年算法

要理解新的整数乘法算法，首先必须理解 2021 年算法中的几乎所有内容。我不可能在这里把这些全部解释清楚。我将转而简要总结与理解新算法如何改变分析相关的要点。对细节感兴趣的读者应参考 [HvdH21]，各方评价都认为这是一篇极佳的论文。我们从两个 n 位整数开始。经过一系列我不会尝试解释的约简（Agarwal–Cooley CRT 重排、高斯重采样等），我们将其约简为计算大小为 r × · · · × r 的某个 ( d − 1) 维数组的 Nussbaumer 风格 DFT（离散傅里叶变换）的问题，其条目位于环 R = C[y]/(yr + 1) 中。这里 d 是一个固定维度参数（与 n 无关），r 是 2 的幂，大小约为 n1/d。系数环 R

包含一个本原 2 r 次单位根，即 y，这就是用于定义 DFT 的“合成”单位根。因此，DFT 可以通过 FFT（快速傅里叶变换）算法来计算，这相当于执行一系列“蝶形”运算，即作用于复数对的映射 ( a, b ) 7 → (a + b, a − b)，以及与 y 的幂相乘（这只是移位和求反）。复数本身表示为具有

p = O(log n) 位精度的定点近似值。（在 C 域上的）蝶形运算次数经计算很容易得出是 12 rd log 2(rd−1)。从这个蝶形计数中，已经可以看出最终复杂度界的 O(n log n) 形态。这些约简导出了 M(n)（相乘 n 位整数的成本）的递归界，形式为

M(n) < Kn n′ M(n′) + O(n log n), n′ = n 1

5关键点在于，“扩张因子” K 是一个绝对常数，与 d 无关。我们在论文中证明，可以取 K = 1728；这来自于对各种归约过程中出现的零填充和编码步骤的分析。（在 §5.4 中，我们概述了将其减小到 K = 8 的各种技术。）第一项 ( Kn/n ′) M(n′) 来自于 Nussbaumer 卷积中递归乘法的成本。只要我们选择 d > K，例如 d = 1729，展开递归就会产生一个几何级数，并能将后续递归层级的成本控制在合理范围内。为简单起见，在 [HvdH21] 中我们保持 d 不变，因为我们只需要 d > K。在新算法中，实际上需要让 d 随 n 增长。当 d 随 n 增长时，必须对某些估计更加小心，但这不会引入本质上的困难。（事实上，在编写 [HvdH21] 的初期，我们曾让 d 随 n 增长，只是在项目后期才决定固定 d。）现在至关重要的问题是 O(n log n) 这一项从何而来。在布尔电路模型中，它完全来自于蝶形算术的成本；其他一切都可以忽略不计。在图灵模型中，存在额外的数据重新排列成本（例如转置数组），这也贡献了 O(n log n)。如果你在两周前问我，对于这两项 O(n log n) 贡献之一能够得到改进的主观概率估计，我想我大概会猜数据重新排列步骤的概率是 0.01%，而算术步骤的概率则精确为零。过去，我也许有些三心二意地尝试过发明更快的矩阵转置算法。但从来、从来、甚至连做梦都没有想过要对蝶形算术发起攻势。自从几十年前我第一次了解 FFT 以来，这个壁垒似乎就一直编织在宇宙的结构中，就像光速一样是一个坚硬的物理极限。但该模型现在断言，我们实际上可以比光速更快。在接下来的章节中，我将试着解释其推理过程。一旦你相信蝶形算术可以改进，那么重新排列这一侧就显得不那么令人惊奇了。我们已经知道这两个问题之间存在着紧密的联系 [HvdH25]。因此，到目前为止，在我对新算法的研究中，我完全忽略了问题中数据重新排列的部分，而把全部精力集中在更具根本性的算术这一侧。如果你愿意的话，我只考虑布尔电路模型，暂时忽略图灵情况。这将是我在本笔记其余部分中工作的上下文。

6 线性代数与放大

我其实不是一个搞代数的人。张量积很难。深吸一口气，跟我重复：“成长型思维”。设 A 是一个 2 × 2 复矩阵。它以自然的方式作用于 C2。例如，A 可以是蝶形映射 ( 1 11 −1 )。现在设 m 是一个正整数，并考虑 ( C2)⊗m。这是 C2 的 m 次张量幂。你可以将 ( C2)⊗m ∼= C2m 的一个元素视为

作为大小为 62 × · · · × 2（$m$ 个因子）的复数 $m$ 维数组。如果 $A1, . . . , A m$ 是 $2 × 2$ 矩阵，则 $A1 ⊗ · · · ⊗ Am$ 以自然的方式作用于 $( C2)⊗m$：

A1 ⊗ · · · ⊗ Am = ( A1 ⊗ I ⊗ · · · ⊗ I)( I ⊗ A2 ⊗ · · · ⊗ I) · · · (I ⊗ I ⊗ · · · ⊗ Am)。

这种分解只是代数运算，但它同时也表达了一种应用 A1 ⊗ · · · ⊗ Am 的算法：首先对第 m 个方向的切片应用 Am，然后对第 ( m − 1) 个方向的切片应用

Am−1，依此类推。而且由于切片算子是可交换的，你可以以任意顺序执行这 m 个步骤。每个 Ai 被应用了 2 m−1 次，因此 2 × 2 矩阵应用的纸面总数为 m · 2m−1。现在让我们聚焦于 A1 = · · · = Am = A 的情况，因此我们正在研究单个 A 的张量幂 A⊗m。使用上述算法将 A⊗m 应用于 ( C2)⊗m 中的向量需要进行

m · 2m−1 次 A 的应用。例如，如果 A 是蝶形矩阵，那么这正是计算 2 × · · · × 2 数组的 DFT 所需的标准蝶形数量。现在可以想象，对于某些 A，人们或许能够使用少于

m · 2m−1 次 A 的应用来计算 A⊗m。例如，如果 A = 0 或 A = I，这显然是成立的！然而，假设 A 并非如此简单，并且有人神奇地递给我们一个用于在某个 m 下计算 A⊗m 的算法，该算法仅使用了 t 次 A 的应用，其中 t 严格小于 m · 2m−1。我们如何利用这个算法来加速 A⊗n 的计算，其中 n 远大于 m？这里有一个相当标准的方法。为简单起见，假设 n = mℓ，其中 ℓ ⩾ 1 是某个整数。那么

A⊗n = A⊗mℓ ∼= A⊗m ⊗ · · · ⊗ A⊗m (ℓ 个因子)。本质上，我们将数组原本的 n 个轴拆分成了 ℓ 个包含 m 个轴的组。所以我们可以做的是，应用我们针对 A⊗m 的快速算法，

沿第一组轴进行，然后沿第二组轴进行，依此类推。这使得 A 的应用次数从原本的 n · 2n−1 减少到了 ( t/ (m · 2m−1)) · n · 2n−1。这种节省并不是非常显著，因为无论 n 的大小如何，它仅仅是一个 t/ (m · 2m−1) 的因子。我们真正想要的是随着 n 增长的节省效果。这可以通过以下方法实现，Fable 将其称为“放大”（amplification）。（论文 [TC26a] 没有使用这个术语。它被用在配套论文中。Fable 指向了 Alman (2021)；Alman、Guan 和 Padaki (2023)；以及 Alman 和 Li (2025) 中的先前研究。我没有去追踪这些参考文献。放大技巧对我来说确实是新奇的。另见下文关于斯特拉森（Strassen）矩阵乘法方法的评论。）为了使放大起作用，我们必须假设我们针对 A⊗m 的快速算法具有某些额外的结构。让我们用 ( F2)m 表示 ( C2)⊗m ∼= C2m 的“地址”空间

, 即向量

u = ( u1, . . . , u m) ∈ Fm

指代 ( C2)⊗m 的第 ( u1, . . . , u m) 个坐标。我们仅考虑由以下两种类型的“指令”序列组成的算法：

ˆ 切片调用。对于每个 i = 1 , . . . , m ，算子 Ai := I ⊗ · · · ⊗ A ⊗ · · · ⊗ I，即 Ai 通过沿第 i 个方向应用 A 来作用于 (C2)⊗m。这相当于调用 A 2 m−1 次。

ˆ 重贴标签。对于每个矩阵 M ∈ GL m(F2)，算子 PM 通过根据 x 7 → M x（对于 x ∈ Fm

）排列条目来作用于 ( C2)⊗m。例如，如果 M 是一个交换 Fm 两个坐标的置换矩阵

, then PM just switches two axes of the array. But M could also involve more complicated transformations 7that “mix up” the axes (i.e., bits of the addresses) in interesting (linear) ways. (Of course, this setup is not general enough to allow arbitrary permutations of the 2 m coordinates of (C2)⊗m.) Note that in the Boolean circuit model, these sorts of relabellings are entirely free. In the Turing model we would have to account for their cost, but I am ignoring this here. An example of such a “program” is the obvious one A⊗m = A1A2 · · · Am that we already discussed earlier. This performs exactly m slice calls, with no relabelling steps. Suppose now that we are magically given a program for computing A⊗m that performs only g slice calls, where g is strictly less than m. Without loss of generality it has the form PM0 Ai1 PM1 Ai2 · · · Aig PMg .(Of course we could get away with just A1 if we modified the M ’s appropriately. But it is convenient to allow ourselves the extra flexibility of the Ai’s.) Let us try to use this program to speed up the computation of A⊗n, where as before n = mℓ for some ℓ ⩾ 1. First observe that

A⊗n = ( A⊗m)⊗ℓ = A⊗m ⊗ · · · ⊗ A⊗m.

In terms of arrays, the formula is splitting up the n axes into ℓ groups of m axes. Now we substitute in the program:

A⊗n = ( PM0 Ai1 PM1 Ai2 · · · Aig PMg )⊗ℓ.

Keep in mind that each of the ℓ copies of (say) Ai1 is actually operating on a different group of m

axes. We can bring the tensor product inside the composition:

A⊗n = ( PM0 )⊗ℓ(Ai1 )⊗ℓ · · · (Aig )⊗ℓ(PMg )⊗ℓ.

I don’t know about you, but at this point my head is spinning. Let’s try to decode what is happening. Consider first one of the factors ( PMj )⊗ℓ. This is applying the same relabelling map PMj (which only acts on m axes) to each of the ℓ groups of m axes. You could do them one group at a time, or all at once; in the Boolean circuit model it makes no difference, it is free. Now consider one of the factors ( Aij )⊗ℓ. This is really ( I ⊗ · · · ⊗ A ⊗ · · · ⊗ I)⊗ℓ, where we are applying A in the ij -th component. In other words, this map is applying A⊗ℓ to a subset of ℓ of the original n axes; it chooses one axis (the ij -th one) out of each group of m axes, and only operates on those. Let’s compare the total work to what would have happened if we had instead used the standard program A1 · · · Am for A⊗m. In effect, we have reduced the number of calls to A⊗ℓ by a factor of

g/m . So if we don’t use any special techniques to evaluate A⊗ℓ, then we save a factor of g/m in the total number of applications of A.But of course, if ℓ is itself a multiple of m, we can (and should!) apply this strategy to A⊗ℓ itself to save another factor of g/m . And then of course we should do it recursively: if we take n = mk

at the beginning, then overall we save a factor of ( g/m )k. This is the amplification: the additional 8structure lets us save further factors of g/m as n grows. The total number of applications of A

becomes (g/m )k · n · 2n−1 = exp

log n

log m log( g/m )

· n · 2n−1

= nα · 2n−1

where α = log g/ log m. You can see here the N (log N )α shape of the result (where N = 2 n). Notice that if g < m , then α is strictly less than 1. (The amplification trick is reminiscent of Strassen’s matrix multiplication algorithm. but notice that in Strassen’s method, k recursion levels gets you from dimension 2 to dimension 2 k, whereas here k recursion levels gets you from dimension 2 m to dimension 2 mk

, i.e., doubly instead of singly exponential in k. Fable explained the difference to me as follows: in Strassen’s method, you are “tensoring a fixed gadget with the problem”, whereas here we are “substituting the problem into the gadget as a tensor power”. So I think they are algebraically not the same thing.) Applying the preceding construction to the butterfly map A = ( 1 11 −1 ), we see that if we can find a program for A⊗m with g < m for even one single value of m, then we can compute DFTs on (C2)⊗n for large n in essentially O(N (log N )α) amount of work ( N = 2 n), with α < 1. The picture, as I have sketched it so far, is missing two main ingredients. First, as mentioned earlier, in the 2021 algorithm we don’t want to compute DFTs of size 2 × · · · × 2 over C, but rather DFTs of size r × · · · × r over R = C[y]/(yr + 1). I am pretty sure that the method will transfer to this situation. The latter problem can certainly be decomposed into butterflies over C of the right shape. I’m not sure exactly what happens to the twiddle factor multiplications (i.e., synthetic roots of unity), but these should be free in the Boolean circuit model (except possibly for chasing some signs around), and I doubt that they interfere in an essential way with the key amplification idea, which is really about how to deal with high dimensional tensor products. You can also see why we need the dimension parameter d to increase with n; we need room to allow n = mk with growing

k. All of this sounds plausible to me but I haven’t worked through it carefully yet. The second thing we are missing is that the Model has not in fact found a way of obtaining a program with g < m . (Moreover, Fable tells me this is impossible, but I do not follow the argument yet.) Instead, what it has found, as I will discuss in the next section, is a way of doing this on average when evaluating A⊗m on sufficiently many independent input arrays. More precisely, taking A to be the butterfly map, and for an integer W ⩾ 1, consider the problem of evaluating I ⊗ A⊗m on CW ⊗ (C2)⊗m. An element of CW ⊗ (C2)⊗m is just a list of W arrays of size 2 m, and evaluating I ⊗ A⊗m means applying A⊗m to each of the W arrays. The standard number of slice calls needed to evaluate I ⊗ A⊗m is W m , i.e., just transform each of the arrays separately. In the next section I will discuss how to construct a gadget that gets away with slightly less (for suitably chosen m and W ). The gadget also includes some other linear operations that “mix up” the entries of the W arrays. Note that achieving even one fewer slice call, for a fixed

m 和 W，就足以让整个论证成立。（嗯，这并不是全部情况，因为我们还必须追踪“混淆”操作的数量，这一点我还没有仔细考虑。我之所以不太担心，是因为它类比于 Strassen 矩阵乘法；关键问题是减少递归调用的次数，而其他算术运算（比如 Strassen 算法中的额外加法）希望能够自行解决。）一旦我们有了这样一个构件，修改调用框架以利用它并不难；毕竟我们确实必须执行许多独立的蝶形运算，且 W 是固定的。（寓言告诉我，你如何分配这些 W 系数的方法可能会影响指数，但我还没有深入研究这一点。）读者可能会觉得，在无法单独加速单个求值的情况下，能够加速 A⊗m 的 W 个独立求值听起来很疯狂。这确实是我的第一反应。但事实上，有一个令人信服的先例。

将一个 n × n 矩阵与单个向量 v ∈ Cn 相乘。假设该矩阵没有特殊结构，这需要 Ω( n2) 次操作。但如果你想将矩阵与 n 个独立向量相乘，这实际上是一个矩阵-矩阵乘法问题，我们从 Strassen 那里得知，我们可以比 n3 更快地完成这项工作，即平均每个向量进行 o(n2) 次操作。所以我在这里没看到任何明显的阻碍。

7 该构件

设 B 为作用于 C2 的蝶形映射 ( 1 11 −1 )。本节的目标是解释正整数 m 和 W 的构造，以及一个计算 I ⊗ B⊗m 在

CW ⊗(C2)⊗m 上的作用的“程序”，其切片调用次数少于 W m 次。如前所述，这里还有额外的加法，但我将忽略这些，我将只关注切片调用，这是驱动递归增益的参数。

7.1 归一化

首先是一些归一化。设

H := 1

√2 B = 1

√2

1 11 −1

因此 H（代表 Hadamard）只是对 B 进行缩放使其成为酉矩阵。接下来设 X := ( 0 1 1 0 ) 且

C := aI + bX =

a bb a

, a := 1 + i

2 , b := 1 − i

2 .

Then |a| = |b| = 1 /√2, and one checks that 1 + i

√2 · H = SCS where S :=

1 00 i

So we can think of C as just a version of H where we have changed basis by S on the domain and S−1 on the codomain (or maybe I have these backwards), and then thrown in a scaling by the norm-1 factor (1 + i)/√2. If we can compute C⊗m then we can easily recover the effect of B⊗m,we just have to pre- and post-multiply every coordinate by the correct powers of i, 1 + i and √2which is easy. So for the rest of the note I will forget about B and work with C.Observe that C is unitary. One checks that it is diagonalised by H, and has eigenvalues 1 and i:

C = HSH −1.

10 (Of course H−1 = H but I prefer to write H−1 to make it clear that we are using the same change of basis on both sides.) (I will just pause here to mention something I find very mysterious. The rest of the development depends crucially on the fact that the eigenvalues of C are 1 and i. But there is nothing “natural” about this; we introduced it artificially when we decided how to change bases to get from B to C.The only justification I see at the moment is that it makes everything work later on. But I have no idea why. (Update: Fable tells me this is forced by the requirements that C commutes with X,which is what makes all the Cv simultaneously diagonal in the H⊗m basis (see below), and that C

is the same as the butterfly up to free rescalings. I have not checked this.))

7.2 The Cv operators

As I said above, C is basically our butterfly expressed in terms of different bases on the domain and codomain. Now we want to graduate to C⊗m, and understand what applying C across a “slice” of (C2)⊗m looks like. The simplest case is where we just apply C on the i-th coordinate. But we will actually need something more general that this. As a notational matter, we will sometimes write elements of ( C2)⊗m as functions Fm

→ C, where

are the addresses as before. Let v ∈ Fm

, v̸ = 0. Think of v as a “direction”. For example if v = ei then this is just the i-th coordinate direction. Let Xv denote translation by v, i.e., it sends f ∈ (C2)⊗m to Xvf ∈ (C2)⊗m given by ( Xvf )( x) =

f (x + v). Since v + v = 0, you can also think of this operation as swapping x and x + v, for every

x ∈ Fm

. Then define

Cv := aI + bX v.

Thus Cv acts on ( C2)⊗m by applying C to the 2 m−1 pairs ( x, x + v). In other words it applies C

in “direction v”. For example, Cei means to apply C on all pairs in the i-th coordinate direction. In the previous section, a “slice call” was only allowed to be in a coordinate direction, i.e., of the form Cei . But we can easily reduce a general Cv to this case by inserting appropriate relabellings before and afterwards. So from now on, “slice call” is allowed to be the more general Cv. Also, one easily checks that ( Cv)−1 = CvXv, and since Xv is just a free rearrangement, we can also treat (Cv)−1 as a slice call. Although the actual algorithm works with the standard basis for ( C2)⊗m, there is a bunch of bookkeeping we need to do in a different basis, namely the basis determined by the m-dimensional Hadamard map H⊗m. Our next job is to work out what Xv and Cv look like in this basis. For Xv we have (H⊗m)−1 · Xv · H⊗m = diag(( −1) v·x),

where diag( f (x)) means the diagonal matrix with x-th entry f (x), for each x ∈ Fm

. Here v · x is the standard bilinear form on Fm

, i.e., v1x1 + · · · + vmxm ∈ F2. Sketch proof: first check it on Xei

by direct calculation, and then observe that translation by v amounts to translating by each ei for 11 which vi = 1. (The result also falls directly out of standard results about Fourier transforms on the finite group ( Z/2Z)m.) For Cv we just use the formula Cv = aI + bX v. This gives (H⊗m)−1 · Cv · H⊗m = diag( a + b(−1) v·x).

If v · x = 0 then the RHS is a + b = 1; if v · x = 1 then we get a − b = i. Therefore (H⊗m)−1 · Cv · H⊗m = diag( i[v·x]), (7.1) where for z ∈ F2 we define [ z] ∈ Z/4Z by the naive lift, i.e., 0 mod 2 gets mapped to 0 mod 4 and 1 mod 2 gets mapped to 1 mod 4. Quick numerical example as a sanity check. Take m = 3. Then Fm

= {000 , 001 , 010 , 011 , 100 , 101 , 110 , 111 }

and ( C2)⊗m ∼= C8. Take v = 011. I won’t bother to write out the 8 ×8 matrix for Cv in the standard basis, but to work it out in the H⊗m basis we first compute (v · 000 , v · 001 , . . . ) = (0 , 1, 1, 0, 0, 1, 1, 0) .

So the matrix for Cv is just diag(1 , i, i, 1, 1, i, i, 1). A really nice feature of this setup is that all of the Cv’s are diagonal in this basis. So all the Cv

互相交换，当我们把它们相乘时，对角线条目直接相乘。例如，由于 C⊗m = Ce1 · · · Cem ，我们得到 (H⊗m)−1 · C⊗m · H⊗m = diag( i[e1·x]) · · · diag( i[em·x]) = diag( iwt( x)) (7.2) 其中 wt( x) 表示 x 的权重，即等于 1 的条目数。在我们 m = 3 的例子中，C⊗m 的矩阵将是 diag(1 , i, i, −1, i, −1, −1, −i)。在引入上述机制后，我们现在大致可以看出我们目标算法的形态。假设你给我一个 CW ⊗ (C2)⊗m 的元素，即一个包含 W 个数组的列表。我想计算其中每一个的 C⊗m。标准算法是对每个数组执行 Ce1 , . . . , C em ；这相当于进行了 W m 次切片调用。但我还有其他选择。我可以将各种 Cv 应用于列表中的各种数组，并且我通过 (7.1) 知道了在 H⊗m 基底下的效果；我只需要跟踪 i 的指数如何按模 4 相加即可。为了增加一点复杂性，我还可以做一些事情，比如将一个数组加到另一个数组上，这意味着各种 Cv 实际上将“并行”作用于多个输入数组。我们的目标是以某种方式在最后每个坐标中获得正确规律的 i 的幂，即与

C⊗m 相匹配，且所有“混杂操作”都已被撤销。

7.3 构建 Fm 的非退化子空间

为了跟踪将各种 Cv 应用于 ( C2)⊗m 的效果，我们引入了以下框架。设 U ⊆ Fm

是一个子空间。我们记 U ⊥ ⊆ Fm

为关于标准点积的补空间，即 U ⊥ := {v ∈ Fm

: 对于所有 u ∈ U 都有 u · v = 0 }。秩-零化度定理表明，始终有 dim( U ⊥) = m − dim U 。12 回想一下，如果 U ∩ U ⊥ = 0，则称 U 关于点积是非退化的。这个条件等价于说 U + U ⊥ = Fm

。请注意，U 是非退化的当且仅当

U ⊥ 是非退化的。我们将在整个过程中使用非退化子空间。例如，当 m = 3 时，100 的生成张成空间是非退化的（它的补空间是 010 和 001 的生成张成空间）。但 110 的生成张成空间是退化的（因为 110 · 110 = 0，所以 110 同时位于 U 和 U ⊥ 中）。更一般地，对于任意 m，{e1, . . . , e j } 的生成张成空间对于任何 j 都是非退化的。当 U 是非退化时，定义投影算子 PU : Fm

→ U 是有意义的。我们只需将给定的 x ∈ Fm

唯一表示为 y + z，其中 y ∈ U 且 z ∈ U ⊥，然后令 PU (x) := y。现在对于任意非退化子空间 U ，定义 qU : Fm

→ Z/4Z 为

qU (x) := wt( PU x) mod 4 。

例如，q0 只是零函数，而 qFm

是返回 wt( x) (mod 4) 的函数，即恰好对应 (7.2) 中出现的指数。然后定义 ΦU := H⊗m · diag( iqU (x)) · (H⊗m)−1，

因此 Φ 0 = I，且根据 (7.2) 有 Φ Fm

= C⊗m。如果 U 和 V 是非退化的且相互正交，那么很容易看出 U + V 也是非退化的，并且 PU +V = PU + PV 。我们现在断言，在 Fm

中的正交向量上，模 4 的权重是可加的。你可以通过观察到 wt( x + y) = wt( x) + wt( y) − 2| supp x ∩ supp y| 来证明这一点（修正项来自 xi = 1 且 yi = 1 的坐标），并且如果 x · y = 0，则 | supp x ∩ supp y| 是偶数。由此可知 qU +V = qU + qV ，因为

qU +V (x) = wt( PU x + PV x) mod 4 = qU (x) + qV (x),

利用了 PU x ⊥ PV x 这一事实。最后，这意味着 Φ U +V = Φ U ΦV 。所以现在我们可以开始理解这个游戏是如何运作的：我们从 U = 0 开始，即 Φ 0 = I，然后尝试向 U 中添加一系列正交子空间，直到最终达到 Φ Fm

= C⊗m。在进行下去的过程中，我们可以通过沿途访问的中间空间

U 的维度来衡量我们评估 C⊗m 的“进度”。现在让我们研究一下“单步”是什么样子的。设 U 是非退代的，并考虑一个与 U 正交的非零向量，记为 v ∈ U ⊥。我们还需假设 ⟨v⟩ 本身是非退代的，即我们需要 wt( v) 是奇数。在这些条件下，U ′ := U + ⟨v⟩ 也是非退代的，且 ΦU ′ = Φ U Φ⟨v⟩。剩下要做的就是计算 Φ ⟨v⟩。观察到（因为 v · v = 1）

q⟨v⟩(x) = wt(( v · x)v) mod 4 = [ v · x] wt( v) mod 4 。

13 由于我们假设 wt( v) 是奇数，因此有两种情况。如果 wt( v) ≡ 1 (mod 4)，那么我们得到 q⟨v⟩(x) = [v · x] mod 4，与 (7.1) 相比，我们发现 Φ ⟨v⟩ = Cv。如果 wt( v) ≡ 3 (mod 4)，则

q⟨v⟩(x) = −[v · x] mod 4，因此 Φ ⟨v⟩ = ( Cv)−1。总之，Φ⟨v⟩ =

(

Cv, wt( v) ≡ 1 (mod 4) ，

(Cv)−1, wt( v) ≡ 3 (mod 4) 。

所以现在的情况是：如果我们从某个具有相应矩阵 Φ U 的非退代 U 开始，然后加入一个奇权重的向量序列 v1, . . . , v k，每个向量都与 U 以及之前的所有向量正交，那么 U + ⟨v1, . . . , v k⟩ 也是非退代的，并且 Φ U +⟨v1,...,v k ⟩ 简单地是乘积 Φ U C±1

· · · C±1

带有适当选择的符号（取决于 vi 的权重

模 4）。每一个 C±1

都对应一次切片调用。Fable 指出我早期的 m = 3 示例无法说明一个非平凡的向量序列，因为 F32 的唯一标准正交基就是标准正交基。它转而建议一个 m = 4 的示例，其标准正交基为 1110 , 1101 , 1011 , 0111。此时有 C⊗4 = C−11110 C−11101 C−11011 C−10111 。

7.4 程序、寄存器与子空间

在接下来的部分中，我将讨论一些“程序”，它们是一系列作用于 W 个“寄存器”数组（记为 ( r1, . . . , r W )）的指令。每个寄存器保存 ( C2)⊗m 中的一个元素。以下是允许的操作：

ˆ 我们可以将 Cv 或 C−1

应用到寄存器，替换现有的值。这些操作中的每一个都花费一次切片调用（外加数据重新排列，我提醒读者我们完全忽略了这一点）。

ˆ 我们可以将一个寄存器的标量倍数加到另一个寄存器上。例如，我可以将

r2 替换为 r2 + 12 r1。如上文（模糊地）所解释的，我忽略了这些操作的成本。每个寄存器都有一个关联的（非退代）子空间 Ui。最初，子空间 U1, . . . , U W 被设置为某些规定的值，然后在程序执行期间它们会被更新。该算法实际上并不存储或操纵子空间；它们在那里只是为了记账目的。其思考方式如下：每个寄存器 ri 都有一个“底层”值，记为 fi ∈ (C2)⊗m。“物理上”存储在 ri 中的内容（即算法实际操纵的值）是部分变换后的值 Φ Ui fi。为了使其起作用，我们必须遵循一些规则：

ˆ 假设我们想要将 Ui 扩大到 U ′

:= Ui + ⟨v⟩。为了使这被允许，我们要求 v 具有奇数权重且 v ⊥ Ui。根据上一节，若 wt( v) = 1 mod 4，则 Φ U ′

是 Φ Ui Cv，若 wt( v) = 3 mod 4，则为 Φ Ui C−1

。因此，在第一种情况下，我们将 Cv 应用到 ri，在第二种情况下，我们将 C−1

应用到 ri。无论哪种情况，寄存器中的值对于 Ui 的新值仍然是 Φ Ui fi。关键在于底层值 fi 没有改变；我们同步改变了物理表示和相关的 Ui。

ˆ 假设我们想要将 Ui 缩小到 U ′

:= Ui ∩ ⟨ v⟩⊥. (This is equivalent to enlarging U ⊥

to U ⊥

⟨v⟩.) For this to be allowed, we require that v has odd weight and that v ∈ Ui

(= U ⊥⊥

). Similarly to the previous bullet, if wt( v) = 1 mod 4 then we apply C−1

to ri, if wt( v) = 3 mod 4 we apply Cv. Again the underlying value fi does not change. 14 ˆ We are only allowed to use the “add scalar multiple” instruction on registers whose Ui are currently equal . In other words, if registers ri and rj are both currently attached to the same subspace U , with physically stored values Φ U fi and Φ U fj , then we are allowed to perform an operation such as replacing rj with rj + 12 ri. In this example we have effectively replaced fj

with fj + 12 fi. Everything stays consistent because Φ U (fj + 12 fi) = Φ U fj + 12 ΦU fi.As an example, suppose that a register begins life with Ui = 0. Since Φ 0 = I, the physically stored value is the same as the underlying value, say fi ∈ (C2)⊗m. If we apply in sequence Ce1 , . . . , C em

to the register, then Ui gets updated to Fm

, so that Φ Ui = C⊗m. At this point, the underlying value is still fi, but the value physically in the register is Φ Ui fi = C⊗mfi. So we have succeeded in computing C⊗mfi.In the program described in the next section, some registers will begin life with Ui̸ = 0. For example, they might begin with Ui = ⟨v⟩ for some odd-weight vector v. In this case, the initial underlying value is different to the initial physical value. This does not cause any problems, and in fact the algorithm does not even need to know the initial underlying values. As we will see, the possibility of starting with Ui̸ = 0 is central to making the whole gadget work.

7.5 简化版程序

在本节中，我们将描述主程序的一个简化版本。你应该将其视为一种动机/热身，而不是字面意义上的主程序子程序（主程序将在下一节中介绍）。我们在这里不使用 ( C2)⊗m，而是使用针对某个整数

h ⩾ 8 的 ( C2)⊗h，将“ m”留给主程序。令 [ h] 表示集合 {1, . . . , h }。令 T 表示 [ h] 中基数为 3 的子集集合。因此 |T| = h

.设 P 表示有序对 ( S, T ) ∈ T × T 的集合，满足 |S ∩ T | 是偶数，即 |S ∩ T |

为 0 或 2。对于每个 S ∈ T，有 3( h − 3) 种选择 T 的方式使得 |S ∩ T | = 2，且有 h−33

种选择 T 的方式使得 |S ∩ T | = 0，因此总共 |P| = h

h−33

+ 3( h − 3) 。

初始化

这里有许多寄存器，扮演着各种不同的角色。我们不把它们叫做 r1, . . . , r W，而是给它们起（稍微）更有意义的名字。它们是：

ˆ 对于每个 T ∈ T，有一个“数据”寄存器 xT 。

ˆ 对于每个 S ∈ T，有一个“数据”寄存器 yS 。

ˆ 对于每个 ( S, T ) ∈ P，有一个“辅助”寄存器 AS,T 。

ˆ 对于每个 i ∈ [h]，有一个“中央”寄存器 ci。

ˆ 最后一个“中央”寄存器 c∗。我并不完全理解这些寄存器名称的含义。寄存器的总数是

W = 2 |T| + |P| + h + 1 。

15 也许值得注意的是，如果你计算每个类别中的寄存器数量，那么从渐近意义上讲，辅助寄存器占主导地位（关于 h 的六次方），其次是数据寄存器（关于 h 的立方），最后只有少量的中央寄存器（关于 h 的线性）。初始子空间都被声明为零，除了 xT 寄存器，它们被初始化为

⟨vT ⟩。这里 vT ∈ Fh

表示索引位于 T 中的向量元素为 1，其余为 0。注意 wt( vT ) = 3，这是一个奇数。我将使用波浪号，例如 ˜ xT，来表示寄存器的初始底层值。在程序开始时，运行状态如下：寄存器当前 U 底层值

xT ⟨vT ⟩ ˜xT

yS 0 ˜yS

AS,T 0 ˜AS,T

ci 0 ˜ci

c∗ 0 ˜c∗

请记住，此时物理值与底层值相匹配，但 xT 除外，其底层值是物理值（即实际作为输入提供给程序的值）在 Φ −1

下的像。程序现在给出为 8 个步骤，标记为 step 0 到 step 7。每个步骤包含一个变换阶段（transform phase），在此阶段我们使用 slice 调用来修改附加到各个寄存器的子空间，然后是一个

混合阶段（mixup phase），在此阶段我们将线性运算应用于位于同一子空间的各个寄存器。然后我们给出一个成本字段，表示 slice 调用的次数（我们忽略混合及其他线性运算以及任何数据重排的成本），接着是一个表格，显示这些操作后所有寄存器的最终状态。

Step 0

变换：无。

混合：对于每个 ( S, T ) ∈ P，如果 |S ∩ T | = 0，则从 yS 中减去 12 AS,T；如果 |S ∩ T | = 2，则将 12 AS,T 加到 yS 中。

成本：零。

最终状态：寄存器当前 U 底层值

xT ⟨vT ⟩ ˜xT

yS 0 ˜yS − 12

˜AS,T + 12

˜AS,T

AS,T 0 ˜AS,T

ci 0 ˜ci

c∗ 0 ˜c∗

16 Step 1

变换：无。

混合：对于每个 S ∈ T，将 12 c∗ − 12

ci 加到 yS 中。

成本：零。

最终状态：寄存器当前 U 底层值

xT ⟨vT ⟩ ˜xT

yS 0 ˜yS − 12

˜AS,T + 12

˜AS,T

12 ˜c∗ − 12

˜ci

AS,T 0 ˜AS,T

ci 0 ˜ci

c∗ 0 ˜c∗

Step 2

变换：对于每个 ( S, T ) ∈ P，将 Φ ⟨vT ⟩ 应用于 AS,T。这将其子空间提升到 ⟨vT ⟩（以匹配 xT）。每对 ( S, T ) 的成本为一个 slice 调用。

混合：对于每个 ( S, T ) ∈ P，将 xT 加到 AS,T 中。（这是合法的，因为子空间现在匹配了。）

成本：|P|。

最终状态：寄存器当前 U 底层值

xT ⟨vT ⟩ ˜xT

yS 0 ˜yS − 12

˜AS,T + 12

˜AS,T

12 ˜c∗ − 12

˜ci

AS,T ⟨vT ⟩ ˜AS,T + ˜ xT

ci 0 ˜ci

c∗ 0 ˜c∗

Step 3

变换：对于每个 T ∈ T，我们希望将 Φ ⟨vT ⟩⊥ 应用于 xT，以将其子空间提升到 ⟨vT ⟩ +

⟨vT ⟩⊥ = Fh

。为了实现这一点，我们需要将 Φ ⟨vT ⟩⊥ 拆分为一系列一维步骤，这意味着我们需要为 ⟨vT ⟩⊥ 找到一个标准正交基。这里有一个显式的标准正交基。设 T = {p, q, r }，并选择任意 s / ∈ T（由于 h ⩾ 4，这是可能的）。然后取向量

ep + eq + es, ep + er + es, eq + er + es, ej，其中 j ∈ [h] \ { p, q, r, s }。

每个 T 的成本为 h − 1 次 slice 调用。（我想在此强调，如果你追溯逻辑，所有这些之所以管用，是因为权重在正交向量上是模 4 可加的，且 Cv 的对角线条目全都是阶为 4 的 i 的幂。也许这广为人知，但我从未见过，而且我认为它非常优美。）17 我们还希望将 ci 和 c∗ 提升到 Fh

。为此，我们需要 Fh 的一个标准正交基

；当然，我们只需使用标准基。每个 ci、c ∗ 的成本为 h 次 slice 调用。

混合：对于每个 T ∈ T，将 xT 加到满足 i ∈ T 的每一个 ci 中，同时也加到 c∗ 中。

成本：|T|(h − 1) + ( h + 1) h。

最终状态：寄存器当前 U 底层值

xT Fh

˜xT

yS 0 ˜yS − 12

˜AS,T + 12

˜AS,T

12 ˜c∗ − 12

˜ci

AS,T ⟨vT ⟩ ˜AS,T + ˜ xT

ci Fh

˜ci + P

˜xT

c∗ Fh

˜c∗ + P

˜xT

Step 4

Transforms : we now want to move ci, c ∗ back down to U = 0, to match with yS . This appears to be undoing some of the progress we already made, but the point is that the mixed-in values of ˜ xT

come along for the ride. To achieve this, we need to perform Φ Fh

in reverse, i.e., we do Φ −1

for each j ∈ [h]. The cost is h slice calls per ci, c ∗.

Mixups : for each S ∈ T, subtract 12 c∗ − 12

ci from yS . (This is the inverse of step 1.) This has the following effects on yS :

ˆ It cancels out the ˜ ci and ˜ c∗ terms from yS .

ˆ For each i ∈ S, the ci term contributes 12 ˜xT for each T containing i. The total contribution from all of these i is 12

|S ∩ T | ˜xT .

ˆ The c∗ term contributes − 12

˜xT .Thus, after this step, the underlying value of yS is given by ˜yS − 12

˜AS,T + 12

˜AS,T + 12

(|S ∩ T | − 1)˜ xT .

We can simplify the last sum a bit. The only case where |S ∩ T | = 3 is when T = S; this term gives

(3 − 1)˜ xS which is simply ˜ xS . Also, the terms with |S ∩ T | = 1 all vanish. So we are left with ˜yS + ˜ xS − 12

( ˜AS,T + ˜ xT ) + 12

( ˜AS,T + ˜ xT ).

Cost : ( h + 1) h.

Final state :18 register current U underlying value

xT Fh

˜xT

yS 0 ˜yS + ˜ xS − 12

( ˜AS,T + ˜ xT )+ 12

( ˜AS,T + ˜ xT )

AS,T ⟨vT ⟩ ˜AS,T + ˜ xT

ci 0 ˜ci + P

˜xT

c∗ 0 ˜c∗ + P

˜xT

Step 5

Transforms : for each S ∈ T we bring yS up to ⟨vS ⟩⊥. We use the same orthonormal basis as in step 3. The cost is h − 1 slice calls per S.Next, for each ( S, T ) ∈ P we want to bring AS,T up to ⟨vS ⟩⊥, to match yS . The crucial fact here is that vT · vS = 0 (since |T ∩ S| = 0 or 2), so vT ∈ ⟨ vS ⟩⊥. (This seems to me to be a really critical point in the argument; it feels like everything else in the gadget might have been designed around this one tiny nugget.) So ⟨vS ⟩⊥ = ⟨vT ⟩ + ⟨vS , v T ⟩⊥ (orthogonal sum), and what we need is an orthonormal basis for ⟨vS , v T ⟩⊥. We can construct one as follows:

ˆ Suppose that |S ∩ T | = 2, say S = {p, q, r } and T = {p, q, s } for r̸ = s. Then we can use

ep + er + es, eq + er + es, ej for j / ∈ { p, q, r, s }.

This is 2 + ( h − 4) = h − 2 vectors altogether.

ˆ Suppose that |S ∩ T | = 0, say S = {p, q, r } and T = {p′, q ′, r ′}, all six indices distinct. Choose distinct s, s ′ /∈ S ∪ T (possible since h ⩾ 8). Then we can use

ep + eq + es, ep + er + es, eq + er + es,ep′ + eq′ + es′ , ep′ + er′ + es′ , eq′ + er′ + es′ ,

together with ej for j / ∈ { p, q, r, s, p ′, q ′, r ′, s ′}. This is 6 + ( h − 8) = h − 2 vectors altogether. The cost is h − 2 slice calls per ( S, T ).

Mixups : for each ( S, T ) ∈ P, if |S ∩ T | = 0 then add 12 AS,T to yS , and if |S ∩ T | = 2 then subtract

AS,T from yS . This is the inverse of step 0, and has the effect of removing the ˜AS,T + ˜ xT terms from yS .

Cost : |T|(h − 1) + |P|(h − 2).

Final state :register current U underlying value

xT Fh

˜xT

yS ⟨vS ⟩⊥ ˜yS + ˜ xS

AS,T ⟨vS ⟩⊥ ˜AS,T + ˜ xT

ci 0 ˜ci + P

˜xT

c∗ 0 ˜c∗ + P

˜xT

19 Step 6

Transforms : we bring each ci, c ∗ back up to Fh

, at a cost of h slice calls for each register.

Mixups : for each T ∈ T, subtract xT from every ci for which i ∈ T , and also from c∗. This is the inverse of step 3.

Cost : ( h + 1) h.

Final state :register current U underlying value

xT Fh

˜xT

yS ⟨vS ⟩⊥ ˜yS + ˜ xS

AS,T ⟨vS ⟩⊥ ˜AS,T + ˜ xT

ci Fh

˜ci

c∗ Fh

˜c∗

Step 7

Transforms : for each ( S, T ) ∈ P, bring AS,T up to Fh

by a single application of Φ ⟨vS ⟩. The cost is one slice call per ( S, T ).

Mixups：对于每个 ( S, T ) ∈ P，从 AS,T 中减去 xT。这是步骤 2 的逆操作。

Cost : |P|。

Final state :register current U underlying value

xT Fh

˜xT

yS ⟨vS ⟩⊥ ˜yS + ˜ xS

AS,T Fh

˜AS,T

ci Fh

˜ci

c∗ Fh

˜c∗

What did the baby program achieve?

At the end of the baby program, the registers AS,T , ci and c∗ contain their original underlying values, and the attached subspaces have moved from U = 0 to U = Fh

. Thus we have succeeded in applying C⊗h to each of them. As for the data registers, we have computed the map ( x, y ) 7 → (x, x + y) on the underlying values. But we have not fully transformed the data, due to the initial subspace on xT having one extra dimension, and the final subspace on yS being one dimension short. Notice however that the ˜ xS part of the final yS register has been fully transformed. Its initial physical value was Φ ⟨vS ⟩(˜ xS ), and its final physical value is Φ ⟨vS ⟩⊥ (˜ xS ), so it has undergone an overall transformation by Φ⟨vS ⟩⊥ Φ−1

= Φ ⟨vS ⟩⊥+⟨vS ⟩Φ−2

= Φ Fh

Φ−2

20 Φ Fh

因子正好是所需的变换 C⊗h。由于 wt( vS ) = 3 (mod 4)，我们有 Φ ⟨vS ⟩ =

C−1

，因此 Φ −2

因子变为 C2

= XvS ，这是一个无害的数据重排。这个观察对于理解下一节中的主程序如何能够运作至关重要。切片调用的总数是

|P| + |T|(h − 1) + ( h + 1) h + ( h + 1) h + |T|(h − 1) + |P|(h − 2) + ( h + 1) h + |P|

= |P|h + 2 |T|(h − 1) + 3( h2 + h)。

回想起 W = 2 |T| + |P| + ( h + 1)（寄存器的总数），我们可以将切片调用次数重写为

W h − 2|T| + 2( h2 + h)。

如何理解这个公式：W h 项是切片调用的“预期”数量（每个寄存器 h 个），2 |T| 项来自于我们没有完全转换数据寄存器（每个数据寄存器只做了 h − 1 个）所带来的节省，而 2( h2 + h) 项来自于在中心寄存器上进行额外工作（“撤销进展”）带来的损耗（每个寄存器 2 h 个）。由于 |T| 关于 h 是三次方的，对于足够大的 h，节省项将超过损耗项，总数将严格小于预期的 W h 。在 Fable 对本节进行校对期间，它主动决定实现整个小型程序作为健全性检查。它针对某些随机输入确认了上述状态表中的公式，并对 h 的几个较小取值验证了上述切片调用次数的公式。我没有仔细检查代码。注意，当 h = 8 时，向量的大小为 2 8 = 256，对于实际计算来说仍然完全可以应付。对于下一节中的主程序，由于组合爆炸，此类实验将变得不可行。

7.6 主程序

如果你在上一节结束时已经头疼了，我必须警告你，情况将变得更糟。设 h 如上所述。我们将构造一个新的程序。寄存器现在将是 ( C2)⊗m 的元素，其中 m := h3。地址空间变为 Fm

= ( Fh

)⊗3。你可以将地址视为一个 h × h × h 的比特数组。（组合爆炸已经很明显了。即使对于 h = 8，我们也有 m = 512，因此向量长度为 2 512 ，远超可观测宇宙中任何物理可实现计算机的大小。）符号 T 具有与上一节相同的含义，即 [ h] 的大小为 3 的子集，记作

{1, . . . , h }

。因此 |T| = h

。类似地，P 具有与之前相同的含义。主程序使用以下寄存器：

ˆ 数据寄存器 xa1,a 2,a 3 和 ya1,a 2,a 3，其中 ( a1, a 2, a 3) ∈ T3。因此数据寄存器的数量为 2|T|3。把 x 想象成一个巨大的 |T| × | T| × | T| 立方体可能会有所帮助，其中每个条目都是一个在 ( C2)⊗m 中保存数组的寄存器。紧挨着它的是一个类似的立方体 y。21 ˆ 正如我们在下面将看到的，主程序调用了 baby 程序 3 |T|2

次变体。每次调用都需要它自己的一组暂存寄存器 AS,T 、 ci 和 c∗。因此，我们总共需要 3 |T|2(|P| + h + 1) 个暂存寄存器。因此寄存器的总数是

W := 2 |T|3 + 3 |T|2(|P| + h + 1) 。

在遍历程序的步骤之前，我们将建立一些进一步的符号，并回顾关于张量积的一些有用事实。如果我们有子空间 U ⊆ Fa

和 V ⊆ Fb

，则子空间 U ⊗ V ⊆ Fa

⊗ Fb

= Fab

是向量 u⊗v 的跨度，其中 u ∈ U ， v ∈ V 。一个经常使用的特殊情况是事实 ⟨u⟩⊗⟨ v⟩ = ⟨u⊗v⟩。我们有 (u ⊗ v) · (u′ ⊗ v′) = ( u · u′)( v · v′)， u, u ′ ∈ Fa

， v, v ′ ∈ Fb

特别是，如果 {ui} 和 {vj } 分别是 U 和 V 的标准正交基，那么 {ui ⊗ vj } 就是 U ⊗ V 的标准正交基。在本节的其余部分中，每当我们写出 U ⊕ U ′ 时，我们总是指正交直和。此外，当我们写出 U ⊥ 时，周围的空间应该始终可以从上下文中清楚看出。如果 U, V 是 Fh 的非退化子空间

，我们有用的公式 (U ⊗ V )⊥ = ( Fh

⊗ V ⊥) ⊕ (U ⊥ ⊗ V )。(7.3) 这源于以下计算 (Fh

⊗ V ⊥) ⊕ (U ⊥ ⊗ V ) ⊕ (U ⊗ V ) = ( Fh

⊗ V ⊥) ⊕ (Fh

⊗ V ) = Fh

⊗ Fh

公式 (7.3) 在张量因子调换后也成立；有时我们会这样使用它，而不做进一步说明。就个人而言，当我验证涉及 (7.3) 的公式时，与其进行代数运算，我发现拿一张纸画出这样的图表要容易得多：

我们将只需要以下类型的标准正交基： 22 ˆ 标准基 e1, . . . , e h 对应 Fh

ˆ 对于 T ∈ T，让 BT 表示来自 baby 程序第 3 步的 ⟨vT ⟩⊥ ⊆ Fh

的标准正交基。它有 h − 1 个向量。（这个基不是唯一确定的，它取决于 s / ∈ T 的选择。任何选择都可以。类似的备注也适用于下面定义的基。）

ˆ 对于 ( S, T ) ∈ P，让 BS,T 表示来自 baby 程序第 5 步的 ⟨vS , v T ⟩⊥ ⊆ Fh

的标准正交基。它有 h − 2 个向量。（我们继续假设 h ⩾ 8。）

ˆ 对于任意的 S, T ∈ T（不一定来自 P），我们需要一个标准正交基

⟨vS ⊗ vT ⟩⊥ ⊆ Fh

⊗ Fh

。我们将用 BS⊗T 来表示它。它可以构建如下。由 (7.3) 我们有 (⟨vS ⟩ ⊗ ⟨ vT ⟩)⊥ = ( ⟨vS ⟩⊥ ⊗ Fh

) ⊕ (⟨vS ⟩ ⊗ ⟨ vT ⟩⊥)。

第一个分量具有标准正交基 {b ⊗ ek : b ∈ BS , k ∈ [h]}。第二个分量具有标准正交基 {vS ⊗ b : b ∈ BT }。我们取 BS⊗T 为这两个基的并集。它有 h2 − 1 个向量。（检查： |BS || [h]| + |BT | = ( h − 1) h + ( h − 1) = h2 − 1。）主程序的子空间初始化如下：寄存器 xa1,a 2,a 3 从 U =

⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ 开始，所有其他寄存器从 U = 0 开始。符号 ˜ xa1,a 2,a 3 和 ˜ ya1,a 2,a 3 指的是程序开始时这些寄存器的底层值。主程序有三个“阶段”，我们现在依次描述它们。

阶段 1 — 概述

对于每一对 ( a2, a 3) ∈ T × T，我们执行 9 个步骤。前 8 个步骤基本上与 baby 程序相同，作用于数据寄存器 xT,a 2,a 3

以及 yS,a 2,a 3，其中 T, S ∈ T。因此，你可以将第 1 阶段看作是沿着第一个维度，对 |T| × | T| × | T| 立方体 x 和 y 的一维“切片”进行操作。我们为每对 ( a2, a 3) 使用一套新的暂存寄存器 (AS,T , ci, c∗)。严格来说，我们应该在暂存寄存器上添加下标 a2, a 3，但为了可读性，我们将其省略。实际上，完全照原样应用小型程序（baby program）是没有意义的，因为它针对的是 ( C2)⊗h 中的数组（其地址在 Fh

中），而这里的寄存器取值于 (C2)⊗m（其地址在 Fm

= ( Fh

)⊗3 中）。相反，我们必须修改切片调用：每当我们在某些寄存器上应用 Φ ⟨v⟩ 时（针对某些奇权重的 v ∈ Fh

），我们将其替换为 Φ ⟨v⊗va2 ⊗va3 ⟩（对于 Φ −1

也是如此）。换句话说，小型程序中的每一个子空间 U ⊆ Fh

都被替换为了 U ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ⊆ Fm

, and the latter has the same dimension as U .The replacement v 7 → v ⊗ va2 ⊗ va3 preserves all orthonormality relations, so all arguments about legality of slice call sequences still hold. (Incidentally, in the baby program, recall that we only ever used v with weight 1 or 3. Since wt( va2 ) = wt( va3 ) = 3, we see that wt( v ⊗ va2 ⊗ va3 ) = 9 wt( v). Thus the modified version only ever performs slice calls in directions v ⊗ va2 ⊗ va3 with weight 9 or 27.) Finally, in step 8 we apply some extra Φ ⟨v⟩’s to the scratch registers to bump their subspaces up from Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ to the full Fm

.23 We now briefly summarise these steps. All 9 steps are performed once for each pair ( a2, a 3). The first 8 steps are basically copied from the baby program with all spaces/vectors tensored by

va2 ⊗ va3 appropriately, so we won’t bother writing out the transform and mixup phases. The costs are literally the same as in the baby program.

Stage 1, initialisation

Here is the initial state: register current U underlying value

xT,a 2,a 3 ⟨vT ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜xT,a 2,a 3

yS,a 2,a 3 0 ˜yS,a 2,a 3

AS,T 0 ˜AS,T

ci 0 ˜ci

c∗ 0 ˜c∗

Stage 1, step 0

Cost : zero.

Final state :register current U underlying value

xT,a 2,a 3 ⟨vT ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜xT,a 2,a 3

yS,a 2,a 3 0 ˜yS,a 2,a 3 − 12

˜AS,T + 12

˜AS,T

AS,T 0 ˜AS,T

ci 0 ˜ci

c∗ 0 ˜c∗

Stage 1, step 1

Cost : zero.

Final state :register current U underlying value

xT,a 2,a 3 ⟨vT ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜xT,a 2,a 3

yS,a 2,a 3 0 ˜yS,a 2,a 3 − 12

˜AS,T + 12

˜AS,T

12 ˜c∗ − 12

˜ci

AS,T 0 ˜AS,T

ci 0 ˜ci

c∗ 0 ˜c∗

Stage 1, step 2

Cost : |P|.

Final state :24 register current U underlying value

xT,a 2,a 3 ⟨vT ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜xT,a 2,a 3

yS,a 2,a 3 0 ˜yS,a 2,a 3 − 12

T :|S∩T |=0 ˜AS,T + 12

T :|S∩T |=2 ˜AS,T

12 ˜c∗ − 12

i∈S ˜ci

AS,T ⟨vT ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜AS,T + ˜ xT,a 2,a 3

ci 0 ˜ci

c∗ 0 ˜c∗

Stage 1, step 3

Cost : |T|(h − 1) + ( h + 1) h.

Final state :register current U underlying value

xT,a 2,a 3 Fh

2 ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜xT,a 2,a 3

yS,a 2,a 3 0 ˜yS,a 2,a 3 − 12

T :|S∩T |=0 ˜AS,T + 12

T :|S∩T |=2 ˜AS,T

12 ˜c∗ − 12

i∈S ˜ci

AS,T ⟨vT ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜AS,T + ˜ xT,a 2,a 3

ci Fh

2 ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜ci + P

T :i∈T ˜xT,a 2,a 3

c∗ Fh

2 ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜c∗ + P

T ˜xT,a 2,a 3

Stage 1, step 4

Cost : ( h + 1) h.

Final state :register current U underlying value

xT,a 2,a 3 Fh

2 ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜xT,a 2,a 3

yS,a 2,a 3 0 ˜yS,a 2,a 3 + ˜ xS,a 2,a 3 − 12

T :|S∩T |=0 ( ˜AS,T + ˜ xT,a 2,a 3 )+ 12

T :|S∩T |=2 ( ˜AS,T + ˜ xT,a 2,a 3 )

AS,T ⟨vT ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜AS,T + ˜ xT,a 2,a 3

ci 0 ˜ci + P

T :i∈T ˜xT,a 2,a 3

c∗ 0 ˜c∗ + P

T ˜xT,a 2,a 3

Stage 1, step 5

Cost : |T|(h − 1) + |P|(h − 2).

Final state :25 register current U underlying value

xT,a 2,a 3 Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜xT,a 2,a 3

yS,a 2,a 3 ⟨vS ⟩⊥ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜yS,a 2,a 3 + ˜ xS,a 2,a 3

AS,T ⟨vS ⟩⊥ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜AS,T + ˜ xT,a 2,a 3

ci 0 ˜ci + P

˜xT,a 2,a 3

c∗ 0 ˜c∗ + P

˜xT,a 2,a 3

Stage 1, step 6

Cost : ( h + 1) h.

Final state :register current U underlying value

xT,a 2,a 3 Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜xT,a 2,a 3

yS,a 2,a 3 ⟨vS ⟩⊥ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜yS,a 2,a 3 + ˜ xS,a 2,a 3

AS,T ⟨vS ⟩⊥ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜AS,T + ˜ xT,a 2,a 3

ci Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜ci

c∗ Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜c∗

Stage 1, step 7

Cost : |P|.

Final state :register current U underlying value

xT,a 2,a 3 Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜xT,a 2,a 3

yS,a 2,a 3 ⟨vS ⟩⊥ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜yS,a 2,a 3 + ˜ xS,a 2,a 3

AS,T Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜AS,T

ci Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜ci

c∗ Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜c∗

Stage 1, step 8

(This step does not come from the baby program.)

Transforms : we want to move each scratch register to Fh

⊗ Fh

⊗ Fh

= Fm

, so we need to add the space Fh

⊗ (⟨va2 ⟩ ⊗ ⟨ va3 ⟩)⊥. We may use the orthonormal basis {ej ⊗ b ⊗ c : j ∈ [h], b ⊗ c ∈ Ba2⊗a3 }.This costs h(h2 − 1) slice calls per scratch register.

Mixups : none.

Cost : ( |P| + h + 1) · h(h2 − 1).

Final state :26 register current U underlying value

xT,a 2,a 3 Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜xT,a 2,a 3

yS,a 2,a 3 ⟨vS ⟩⊥ ⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ ˜yS,a 2,a 3 + ˜ xS,a 2,a 3

AS,T Fh

⊗ Fh

⊗ Fh

˜AS,T

ci Fh

⊗ Fh

⊗ Fh

˜ci

c∗ Fh

⊗ Fh

⊗ Fh

˜c∗

At this point we are done with this set of scratch registers; we put them aside and bring in a new set for the next pair ( a2, a 3) (starting again of course at U = 0 for each register).

Stage 1 — conclusion

As for the data registers, we have computed the map ( x, y ) 7 → (x, x + y) on the underlying values. The first component of the subspace for y is one dimension short of the full Fh

⊗ ⟨ va2 ⟩ ⊗ ⟨ va3 ⟩ (the current “target”), so the ˜ y part has not been fully transformed. But, as explained in the baby program, the ˜ x part has been fully transformed (i.e., up to the current target). The scratch registers were transformed completely, i.e., we have applied C⊗m to each of them. The total number of slice calls for Stage 1 is just the baby program count, plus the cost of step 8, all multiplied by the number of pairs ( a2, a 3):

|T|2 �|P|h + 2 |T|(h − 1) + 3( h2 + h) + ( |P| + h + 1) · h(h2 − 1)

= 2 |T|3(h − 1) + |T|2|P|h3 + |T|2(h2 + 2)( h2 + h).

Stage 2 — overview

The aim of this stage is to compute the function ( x, y ) 7 → (x − y, y ) on each pair of data registers. This maps the current values (˜ xa, ˜ya + ˜ xa) (see last state table) to (˜ xa − (˜ ya + ˜ xa), ˜ya + ˜ xa) = ( −˜ya, ˜ya + ˜ xa).

The strategy is essentially to run the steps of the baby program in reverse order, with each mixup operation inverted, and with the roles of x and y switched. However, we cannot run the Φ ⟨v⟩’s backwards, because we are still trying to make progress in the forward direction on the subspaces. As in the baby program, the main requirement is to ensure that the subspaces agree whenever we want to perform a linear operation on two registers. For each pair ( a1, a 3) ∈ T × T, we perform the following steps. (The modified baby program is going to act on the second coordinate.)

Stage 2, initialisation

The data registers in the following table are copied from the final state of Stage 1. For each ( a1, a 3)we use a new set of scratch registers, initialised to U = 0. 27 register current U underlying value

xa1,S,a 3 Fh

⊗ ⟨ vS ⟩ ⊗ ⟨ va3 ⟩ ˜xa1,S,a 3

ya1,T,a 3 ⟨va1 ⟩⊥ ⊗ ⟨ vT ⟩ ⊗ ⟨ va3 ⟩ ˜ya1,T,a 3 + ˜ xa1,T,a 3

AS,T 0 ˜AS,T

ci 0 ˜ci

c∗ 0 ˜c∗

Stage 2, step 0 (inverse of baby program step 7)

Transforms : we bring AS,T up to ⟨va1 ⟩⊥ ⊗ ⟨ vT ⟩ ⊗ ⟨ va3 ⟩ (to match ya1,T,a 3 ) via the orthonormal basis

{b ⊗ vT ⊗ va3 : b ∈ Ba1 }. This needs h − 1 slice calls for each ( S, T ).

Mixups : for each ( S, T ) ∈ P, we add ya1,T,a 3 to AS,T .

Cost : |P|(h − 1).

Final state :register current U underlying value

xa1,S,a 3 Fh

⊗ ⟨ vS ⟩ ⊗ ⟨ va3 ⟩ ˜xa1,S,a 3

ya1,T,a 3 ⟨va1 ⟩⊥ ⊗ ⟨ vT ⟩ ⊗ ⟨ va3 ⟩ ˜ya1,T,a 3 + ˜ xa1,T,a 3

AS,T ⟨va1 ⟩⊥ ⊗ ⟨ vT ⟩ ⊗ ⟨ va3 ⟩ ˜AS,T + ˜ ya1,T,a 3 + ˜ xa1,T,a 3

ci 0 ˜ci

c∗ 0 ˜c∗

Stage 2, step 1 (inverse of baby program step 6)

Transforms : we want to bring ya1,T,a 3 and ci, c ∗ up to ⟨va1 ⟩⊥ ⊗ Fh

⊗ ⟨ va3 ⟩.For ya1,T,a 3 we use the orthonormal basis {b ⊗ c ⊗ va3 : b ∈ Ba1 , c ∈ BT }. This costs ( h − 1) 2 slice calls for each T ∈ T.For ci, c ∗ we use the orthonormal basis {b ⊗ ej ⊗ va3 : b ∈ Ba1 , j ∈ [h]}. This costs ( h − 1) h slice calls for each ci, c ∗.

Mixups : for each T ∈ T, we add ya1,T,a 3 to every ci for which i ∈ T , and to c∗.

Cost : |T|(h − 1) 2 + ( h − 1) h(h + 1).

Final state :register current U underlying value

xa1,S,a 3 Fh

⊗ ⟨ vS ⟩ ⊗ ⟨ va3 ⟩ ˜xa1,S,a 3

ya1,T,a 3 ⟨va1 ⟩⊥ ⊗ Fh

⊗ ⟨ va3 ⟩ ˜ya1,T,a 3 + ˜ xa1,T,a 3

AS,T ⟨va1 ⟩⊥ ⊗ ⟨ vT ⟩ ⊗ ⟨ va3 ⟩ ˜AS,T + ˜ ya1,T,a 3 + ˜ xa1,T,a 3

ci ⟨va1 ⟩⊥ ⊗ Fh

⊗ ⟨ va3 ⟩ ˜ci + P

(˜ ya1,T,a 3 + ˜ xa1,T,a 3 )

c∗ ⟨va1 ⟩⊥ ⊗ Fh

⊗ ⟨ va3 ⟩ ˜c∗ + P

(˜ ya1,T,a 3 + ˜ xa1,T,a 3 )28 Stage 2, step 2 (inverse of baby program step 5)

Transforms : we want to bring both xa1,S,a 3 and AS,T up to the subspace

�⟨va1 ⟩ ⊗ ⟨ vS ⟩⊥⊥ ⊗ ⟨ va3 ⟩.

By (7.3) this is the same as

�Fh

⊗ ⟨ vS ⟩ ⊗ ⟨ va3 ⟩ ⊕ �⟨va1 ⟩⊥ ⊗ ⟨ vS ⟩⊥ ⊗ ⟨ va3 ⟩.

For xa1,S,a 3 we just need to add on the ⟨va1 ⟩⊥ ⊗ ⟨ vS ⟩⊥ ⊗ ⟨ va3 ⟩ part; we can use the orthonormal basis {b ⊗ c ⊗ va3 : b ∈ Ba1 , c ∈ BS }, which requires ( h − 1) 2 slice calls. For AS,T , we first add ⟨va1 ⟩⊥ ⊗ ⟨ vS , v T ⟩⊥ ⊗ ⟨ va3 ⟩ using the orthonormal basis {b ⊗ c ⊗ va3 : b ∈

Ba1 , c ∈ BS,T }, which gets us to ⟨va1 ⟩⊥ ⊗ ⟨ vS ⟩⊥ ⊗ ⟨ va3 ⟩. (The key fact here is that vS · vT = 0.) We then add the Fh

⊗ ⟨ vS ⟩ ⊗ ⟨ va3 ⟩ part using the orthonormal basis {ej ⊗ vS ⊗ va3 : j ∈ [h]}. The total number of slice calls is ( h − 1)( h − 2) + h = h2 − 2h + 2.

Mixups : for each ( S, T ) ∈ P, if |S ∩ T | = 0 then subtract 12 AS,T from xa1,S,a 3 , and if |S ∩ T | = 2 then add 12 AS,T to xa1,S,a 3 .

Cost : |T|(h − 1) 2 + |P|(h2 − 2h + 2).

Final state (taking the opportunity to rewrite all of the subspaces in terms of complements for the first two components): register current U underlying value

xa1,S,a 3 (⟨va1 ⟩ ⊗ ⟨ vS ⟩⊥)⊥ ⊗ ⟨ va3 ⟩ ˜xa1,S,a 3 − 12

( ˜AS,T + ˜ ya1,T,a 3 + ˜ xa1,T,a 3 )+ 12

( ˜AS,T + ˜ ya1,T,a 3 + ˜ xa1,T,a 3 )

ya1,T,a 3 (⟨va1 ⟩ ⊗ Fh

)⊥ ⊗ ⟨ va3 ⟩ ˜ya1,T,a 3 + ˜ xa1,T,a 3

AS,T (⟨va1 ⟩ ⊗ ⟨ vS ⟩⊥)⊥ ⊗ ⟨ va3 ⟩ ˜AS,T + ˜ ya1,T,a 3 + ˜ xa1,T,a 3

ci (⟨va1 ⟩ ⊗ Fh

)⊥ ⊗ ⟨ va3 ⟩ ˜ci + P

(˜ ya1,T,a 3 + ˜ xa1,T,a 3 )

c∗ (⟨va1 ⟩ ⊗ Fh

)⊥ ⊗ ⟨ va3 ⟩ ˜c∗ + P

(˜ ya1,T,a 3 + ˜ xa1,T,a 3 )

Stage 2, step 3 (inverse of baby program step 4)

Transforms : we want to bring xa1,S,a 3 and ci, c∗ up to Fh

⊗ Fh

⊗ ⟨ va3 ⟩.For xa1,S,a 3 this requires adding on ⟨va1 ⟩ ⊗ ⟨ vS ⟩⊥ ⊗ ⟨ va3 ⟩, for which we use the orthonormal basis

{va1 ⊗ b ⊗ va3 : b ∈ BS }. This requires h − 1 slice calls. For ci, c∗ this requires adding on ⟨va1 ⟩ ⊗ Fh

⊗ ⟨ va3 ⟩. We use the orthonormal basis {va1 ⊗ ej ⊗ va3 :

j ∈ [h]}. This requires h slice calls.

Mixups : for each S ∈ T we add 12 c∗ − 12

ci to xa1,S,a 3 . A similar argument to step 4 of the baby program shows that most ˜ x and ˜ y terms drop out, and the ˜ xa1,S,a 3 gets replaced by −˜ya1,S,a 3 .

Cost : |T|(h − 1) + ( h + 1) h.

Final state :29 register current U underlying value

xa1,S,a 3 Fh

⊗ Fh

⊗ ⟨ va3 ⟩ −˜ya1,S,a 3 − 12

˜AS,T + 12

˜AS,T

12 ˜c∗ − 12

˜ci

ya1,T,a 3 (⟨va1 ⟩ ⊗ Fh

)⊥ ⊗ ⟨ va3 ⟩ ˜ya1,T,a 3 + ˜ xa1,T,a 3

AS,T (⟨va1 ⟩ ⊗ ⟨ vS ⟩⊥)⊥ ⊗ ⟨ va3 ⟩ ˜AS,T + ˜ ya1,T,a 3 + ˜ xa1,T,a 3

ci Fh

⊗ Fh

⊗ ⟨ va3 ⟩ ˜ci + P

(˜ ya1,T,a 3 + ˜ xa1,T,a 3 )

c∗ Fh

⊗ Fh

⊗ ⟨ va3 ⟩ ˜c∗ + P

(˜ ya1,T,a 3 + ˜ xa1,T,a 3 )

Stage 2, step 4 (inverse of baby program step 3)

Transforms : we want to move ci, c∗ down to ( ⟨va1 ⟩ ⊗ Fh

)⊥ ⊗ ⟨ va3 ⟩, to line up with ya1,T,a 3 . This is the only backwards move in Stage 2. We need to subtract out the subspace ⟨va1 ⟩ ⊗ Fh

⊗ ⟨ va3 ⟩, so we use the orthonormal basis {va1 ⊗ ej ⊗ va3 : j ∈ [h]}. The number of slice calls is h.

Mixups : for each T ∈ T we subtract ya1,T,a 3 from every ci with i ∈ T , and also from c∗.

Cost : ( h + 1) h.

Final state :register current U underlying value

xa1,S,a 3 Fh

⊗ Fh

⊗ ⟨ va3 ⟩ −˜ya1,S,a 3 − 12

˜AS,T + 12

˜AS,T

12 ˜c∗ − 12

˜ci

ya1,T,a 3 (⟨va1 ⟩ ⊗ Fh

)⊥ ⊗ ⟨ va3 ⟩ ˜ya1,T,a 3 + ˜ xa1,T,a 3

AS,T (⟨va1 ⟩ ⊗ ⟨ vS ⟩⊥)⊥ ⊗ ⟨ va3 ⟩ ˜AS,T + ˜ ya1,T,a 3 + ˜ xa1,T,a 3

ci (⟨va1 ⟩ ⊗ Fh

)⊥ ⊗ ⟨ va3 ⟩ ˜ci

c∗ (⟨va1 ⟩ ⊗ Fh

)⊥ ⊗ ⟨ va3 ⟩ ˜c∗

Stage 2, step 5 (inverse of baby program step 2)

Transforms : we want to bring both ya1,T,a 3 and AS,T up to ( ⟨va1 ⟩ ⊗ ⟨ vT ⟩)⊥ ⊗ ⟨ va3 ⟩.For ya1,T,a 3 this requires adding on the subspace ⟨va1 ⟩ ⊗ ⟨ vT ⟩⊥ ⊗ ⟨ va3 ⟩. We use the orthonormal basis {va1 ⊗ b ⊗ va3 : b ∈ BT }. The number of slice calls is h − 1. For AS,T , first observe that by (7.3), (⟨va1 ⟩ ⊗ ⟨ vS ⟩⊥)⊥ = ( ⟨va1 ⟩ ⊗ ⟨ vS ⟩) ⊕ (⟨va1 ⟩⊥ ⊗ Fh

This implies (by vS · vT = 0 and (7.3) again) that (⟨va1 ⟩ ⊗ ⟨ vS ⟩⊥)⊥ ⊕ (⟨va1 ⟩ ⊗ ⟨ vS , v T ⟩⊥) = ( ⟨va1 ⟩ ⊗ ⟨ vT ⟩⊥) ⊕ (⟨va1 ⟩⊥ ⊗ Fh

)= ( ⟨va1 ⟩ ⊗ ⟨ vT ⟩)⊥.

Thus, to get AS,T up to ( ⟨va1 ⟩⊗⟨ vT ⟩)⊥⊗⟨ va3 ⟩, it suffices to add the subspace ⟨va1 ⟩⊗⟨ vS , v T ⟩⊥⊗⟨ va3 ⟩.We use the orthonormal basis {va1 ⊗ b ⊗ va3 : b ∈ BS,T }. The number of slice calls is h − 2.

Mixups : for each ( S, T ) ∈ P we subtract ya1,T,a 3 from AS,T .30 Cost : |T|(h − 1) + |P|(h − 2).

Final state :register current U underlying value

xa1,S,a 3 Fh

⊗ Fh

⊗ ⟨ va3 ⟩ −˜ya1,S,a 3 − 12

˜AS,T + 12

˜AS,T

12 ˜c∗ − 12

˜ci

ya1,T,a 3 (⟨va1 ⟩ ⊗ ⟨ vT ⟩)⊥ ⊗ ⟨ va3 ⟩ ˜ya1,T,a 3 + ˜ xa1,T,a 3

AS,T (⟨va1 ⟩ ⊗ ⟨ vT ⟩)⊥ ⊗ ⟨ va3 ⟩ ˜AS,T

ci (⟨va1 ⟩ ⊗ Fh

)⊥ ⊗ ⟨ va3 ⟩ ˜ci

c∗ (⟨va1 ⟩ ⊗ Fh

)⊥ ⊗ ⟨ va3 ⟩ ˜c∗

Stage 2, step 6 (inverse of baby program step 1)

Transforms : we bring ci, c ∗ back up to Fh

⊗ Fh

⊗ ⟨ va3 ⟩. As in step 4, the number of slice calls is h.

Mixups : for each S ∈ T we subtract 12 c∗ − 12

ci from xa1,S,a 3 .

Cost : ( h + 1) h.

Final state :register current U underlying value

xa1,S,a 3 Fh

⊗ Fh

⊗ ⟨ va3 ⟩ −˜ya1,S,a 3 − 12

˜AS,T + 12

˜AS,T

ya1,T,a 3 (⟨va1 ⟩ ⊗ ⟨ vT ⟩)⊥ ⊗ ⟨ va3 ⟩ ˜ya1,T,a 3 + ˜ xa1,T,a 3

AS,T (⟨va1 ⟩ ⊗ ⟨ vT ⟩)⊥ ⊗ ⟨ va3 ⟩ ˜AS,T

ci Fh

⊗ Fh

⊗ ⟨ va3 ⟩ ˜ci

c∗ Fh

⊗ Fh

⊗ ⟨ va3 ⟩ ˜c∗

Stage 2, step 7 (inverse of baby program step 0)

Transforms : we bring AS,T up to Fh

⊗ Fh

⊗ ⟨ va3 ⟩. Only one slice call is needed here, to add the subspace ⟨va1 ⟩ ⊗ ⟨ vT ⟩ ⊗ ⟨ va3 ⟩.

Mixups : for each ( S, T ) ∈ P, if |S ∩ T | = 0 then add 12 AS,T to xa1,S,a 3 , and if |S ∩ T | = 2 then subtract 12 AS,T from xa1,S,a 3 .

Cost : |P|.

Final state :register current U underlying value

xa1,S,a 3 Fh

⊗ Fh

⊗ ⟨ va3 ⟩ −˜ya1,S,a 3

ya1,T,a 3 (⟨va1 ⟩ ⊗ ⟨ vT ⟩)⊥ ⊗ ⟨ va3 ⟩ ˜ya1,T,a 3 + ˜ xa1,T,a 3

AS,T Fh

⊗ Fh

⊗ ⟨ va3 ⟩ ˜AS,T

ci Fh

⊗ Fh

⊗ ⟨ va3 ⟩ ˜ci

c∗ Fh

⊗ Fh

⊗ ⟨ va3 ⟩ ˜c∗

31 Stage 2, step 8

Transforms : as in step 8 of Stage 1, we need to finish transforming the scratch registers, to get to

⊗ Fh

⊗ Fh

. This requires adding the subspace Fh

⊗ Fh

⊗ ⟨ va3 ⟩⊥. We use the orthonormal basis

{ej ⊗ ek ⊗ b : j, k ∈ [h], b ∈ Ba3 }. This costs h2(h − 1) slice calls.

Mixups : none.

Cost : ( |P| + h + 1) h2(h − 1).

Final state :register current U underlying value

xa1,S,a 3 Fh

⊗ Fh

⊗ ⟨ va3 ⟩ −˜ya1,S,a 3

ya1,T,a 3 (⟨va1 ⟩ ⊗ ⟨ vT ⟩)⊥ ⊗ ⟨ va3 ⟩ ˜ya1,T,a 3 + ˜ xa1,T,a 3

AS,T Fh

⊗ Fh

⊗ Fh

˜AS,T

ci Fh

⊗ Fh

⊗ Fh

˜ci

c∗ Fh

⊗ Fh

⊗ Fh

˜c∗

As in stage 1, we are now done with these scratch registers, and we bring in a fresh set for the next pair ( a1, a 3).

Stage 2 — conclusion

Again, the subspace for ya1,T,a 3 is still one dimension short of the stage 2 target, which is Fh

⊗ Fh

⊗⟨va3 ⟩. So the ˜ y component of y is not quite fully transformed. But the ˜ x part is fully transformed (just as in stage 1), and the important new feature is that the ˜ y value in the x register is also fully transformed up to the current target. The total slice call count for each pair ( a1, a 3) is

|T| �(h − 1) 2 + ( h − 1) 2 + ( h − 1) + ( h − 1)

|P| �(h − 1) + ( h2 − 2h + 2) + ( h − 2) + 1 + h2(h − 1)
�(h − 1) h(h + 1) + ( h + 1) h + ( h + 1) h + ( h + 1) h + ( h + 1) h2(h − 1)

= 2 |T|(h2 − h) + |P|h3 + ( h2 + 2)( h2 + h).

Thus the total cost of Stage 2 is 2|T|3(h2 − h) + |T|2|P|h3 + |T|2(h2 + 2)( h2 + h).

The combined cost of Stage 1 and Stage 2 is 2|T|3(h2 − 1) + 2 |T|2|P|h3 + 2 |T|2(h2 + 2)( h2 + h).

Stage 3 — overview

In this stage, we want to compute the original baby program map ( x, y ) 7 → (x, y + x) again, to clear out the ˜ y part of the y registers. We are going to run the baby program in forward order, now 32 operating on the third components. The Φ ⟨v⟩’s need to be modified, but at least this time they are all going in the right direction. For each ( a1, a 2) ∈ T × T we perform the following steps. (The numbering matches that of the baby program.)

Stage 3, initialisation

The data registers in the following table are copied from the final state of Stage 2. For each ( a1, a 2)we use a new set of scratch registers, initialised to U = 0. register current U underlying value

xa1,a 2,T Fh

⊗ Fh

⊗ ⟨ vT ⟩ −˜ya1,a 2,T

ya1,a 2,S (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ ⟨ vS ⟩ ˜ya1,a 2,S + ˜ xa1,a 2,S

AS,T 0 ˜AS,T

ci 0 ˜ci

c∗ 0 ˜c∗

Stage 3, step 0

Transforms : we bring AS,T up to ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ ⟨ vS ⟩ (to match ya1,a 2,S ), using the orthonormal basis {b ⊗ c ⊗ vS : b ⊗ c ∈ Ba1⊗a2 }. The number of slice calls is h2 − 1.

Mixups : for each ( S, T ) ∈ P, if |S ∩ T | = 0 then subtract 12 AS,T from ya1,a 2,S , and if |S ∩ T | = 2 then add 12 AS,T to ya1,a 2,S .

Cost : |P|(h2 − 1).

Final state :register current U underlying value

xa1,a 2,T Fh

⊗ Fh

⊗ ⟨ vT ⟩ −˜ya1,a 2,T

ya1,a 2,S (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ ⟨ vS ⟩ ˜ya1,a 2,S + ˜ xa1,a 2,S − 12

˜AS,T

˜AS,T

AS,T (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ ⟨ vS ⟩ ˜AS,T

ci 0 ˜ci

c∗ 0 ˜c∗

Stage 3, step 1

Transforms : we want to move ya1,a 2,S and ci, c∗ up to ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

.For ya1,a 2,S this involves adding the subspace ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ ⟨ vS ⟩⊥. We use the orthonormal basis {b ⊗ c ⊗ w : b ⊗ c ∈ Ba1⊗a2 , w ∈ BS }. The number of slice calls is ( h2 − 1)( h − 1). For ci, c ∗ we have to add on all of ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

. We use the orthonormal basis {b ⊗ c ⊗ ej :

b ⊗ c ∈ Ba1⊗a2 , j ∈ [h]}. The number of slice calls is ( h2 − 1) h.

Mixups : for each S ∈ T we add 12 c∗ − 12

ci to ya1,a 2,S .33 Cost : |T|(h2 − 1)( h − 1) + ( h2 − 1) h(h + 1).

Final state :register current U underlying value

xa1,a 2,T Fh

⊗ Fh

⊗ ⟨ vT ⟩ −˜ya1,a 2,T

ya1,a 2,S (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜ya1,a 2,S + ˜ xa1,a 2,S − 12

˜AS,T

˜AS,T + 12 ˜c∗ − 12

˜ci

AS,T (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ ⟨ vS ⟩ ˜AS,T

ci (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜ci

c∗ (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜c∗

Stage 3, step 2

Transforms : we want to bring xa1,a 2,T and AS,T up to ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vT ⟩⊥)⊥.For xa1,a 2,T this requires adding the subspace ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ ⟨ vT ⟩⊥ (by (7.3)). We use the orthonormal basis {b ⊗ c ⊗ w : b ⊗ c ∈ Ba1⊗a2 , w ∈ BT }. This needs ( h2 − 1)( h − 1) slice calls. For AS,T we must first add the subspace ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ ⟨ vS ⟩⊥ to get up to ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

.We use the orthonormal basis {b ⊗ c ⊗ w : b ⊗ c ∈ Ba1⊗a2 , w ∈ BS }. This requires ( h2 − 1)( h − 1) slice calls. Then we add the one-dimensional space ⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vT ⟩, which costs only one slice call.

Mixups : for each ( S, T ) ∈ P, add xa1,a 2,T to AS,T .

Cost : |T|(h2 − 1)( h − 1) + |P|(( h2 − 1)( h − 1) + 1).

Final state :register current U underlying value

xa1,a 2,T (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vT ⟩⊥)⊥ −˜ya1,a 2,T

ya1,a 2,S (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜ya1,a 2,S + ˜ xa1,a 2,S − 12

˜AS,T

˜AS,T + 12 ˜c∗ − 12

˜ci

AS,T (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vT ⟩⊥)⊥ ˜AS,T − ˜ya1,a 2,T

ci (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜ci

c∗ (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜c∗

Stage 3, step 3

Transforms : we want to move xa1,a 2,T and ci, c ∗ up to Fh

⊗ Fh

⊗ Fh

(the fully transformed state). For xa1,a 2,T we need to add the subspace ⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vT ⟩⊥. We use the orthonormal basis

{va1 ⊗ va2 ⊗ b : b ∈ BT }, at a cost of h − 1 slice calls. For ci, c ∗ we need to add the subspace ⟨va1 ⟩⊗⟨ va2 ⟩⊗ Fh

. We use the orthonormal basis {va1 ⊗va2 ⊗ej :

j ∈ [h]}. This costs h slice calls.

Mixups : for each T ∈ T, add xa1,a 2,T to every ci for which i ∈ T , and also to c∗.34 Cost : |T|(h − 1) + ( h + 1) h.

Final state :register current U underlying value

xa1,a 2,T Fh

⊗ Fh

⊗ Fh

−˜ya1,a 2,T

ya1,a 2,S (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜ya1,a 2,S + ˜ xa1,a 2,S − 12

˜AS,T

˜AS,T + 12 ˜c∗ − 12

˜ci

AS,T (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vT ⟩⊥)⊥ ˜AS,T − ˜ya1,a 2,T

ci Fh

⊗ Fh

⊗ Fh

˜ci − P

˜ya1,a 2,T

c∗ Fh

⊗ Fh

⊗ Fh

˜c∗ − P

˜ya1,a 2,T

Stage 3, step 4

Transforms : we bring ci, c ∗ back down to ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

. This is the only backwards move in Stage 3. We use the same orthonormal basis as step 3. This costs h slice calls.

Mixups : for each S ∈ T, subtract 12 c∗ − 12

ci from ya1,a 2,S .

Cost : ( h + 1) h.

Final state :register current U underlying value

xa1,a 2,T Fh

⊗ Fh

⊗ Fh

−˜ya1,a 2,T

ya1,a 2,S (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜xa1,a 2,S − 12

( ˜AS,T − ˜ya1,a 2,T )+ 12

( ˜AS,T − ˜ya1,a 2,T )

AS,T (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vT ⟩⊥)⊥ ˜AS,T − ˜ya1,a 2,T

ci (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜ci − P

˜ya1,a 2,T

c∗ (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜c∗ − P

˜ya1,a 2,T

Stage 3, step 5

Transforms : we want to bring ya1,a 2,S and AS,T up to ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS ⟩)⊥.For ya1,a 2,S we need to add the subspace ⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS ⟩⊥. We use the orthonormal basis

{va1 ⊗ va2 ⊗ b : b ∈ BS }, at a cost of h − 1 slice calls. For AS,T we need only add the subspace ⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS , v T ⟩⊥, as (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vT ⟩⊥)⊥ = ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vT ⟩) ⊕ (( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

)together with vS · vT = 0 implies that (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vT ⟩⊥)⊥ ⊕ (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS , v T ⟩⊥)= ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS ⟩⊥) ⊕ (( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

) = ( ⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS ⟩)⊥.

Thus we may use the orthonormal basis {va1 ⊗ va2 ⊗ b : b ∈ BS,T }, at a cost of h − 2 slice calls. 35 Mixups : for each ( S, T ) ∈ P, if |S ∩ T | = 0 then add 12 AS,T to ya1,a 2,S , and if |S ∩ T | = 2 then subtract 12 AS,T from ya1,a 2,S .

Cost : |T|(h − 1) + |P|(h − 2).

Final state :register current U underlying value

xa1,a 2,T Fh

⊗ Fh

⊗ Fh

−˜ya1,a 2,T

ya1,a 2,S (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS ⟩)⊥ ˜xa1,a 2,S

AS,T (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS ⟩)⊥ ˜AS,T − ˜ya1,a 2,T

ci (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜ci − P

˜ya1,a 2,T

c∗ (⟨va1 ⟩ ⊗ ⟨ va2 ⟩)⊥ ⊗ Fh

˜c∗ − P

˜ya1,a 2,T

Stage 3, step 6

Transforms : bring ci, c ∗ up to Fh

⊗ Fh

⊗ Fh

by adding the subspace ⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ Fh

. We use the orthonormal basis {va1 ⊗ va2 ⊗ ej : j ∈ [h]}, at a cost of h slice calls.

Mixups : for each T ∈ T, subtract xa1,a 2,T from every ci for which i ∈ T , and also from c∗.

Cost : ( h + 1) h.

Final state :register current U underlying value

xa1,a 2,T Fh

⊗ Fh

⊗ Fh

−˜ya1,a 2,T

ya1,a 2,S (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS ⟩)⊥ ˜xa1,a 2,S

AS,T (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS ⟩)⊥ ˜AS,T − ˜ya1,a 2,T

ci Fh

⊗ Fh

⊗ Fh

˜ci

c∗ Fh

⊗ Fh

⊗ Fh

˜c∗

Stage 3, step 7

Transforms : bring AS,T up to Fh

⊗ Fh

⊗ Fh

by a single step in the direction va1 ⊗ va2 ⊗ vS . This costs one slice call.

Mixups : for each ( S, T ) ∈ P, subtract xa1,a 2,T from AS,T .

Cost : |P|.

Final state :register current U underlying value

xa1,a 2,T Fh

⊗ Fh

⊗ Fh

−˜ya1,a 2,T

ya1,a 2,S (⟨va1 ⟩ ⊗ ⟨ va2 ⟩ ⊗ ⟨ vS ⟩)⊥ ˜xa1,a 2,S

AS,T Fh

⊗ Fh

⊗ Fh

˜AS,T

ci Fh

⊗ Fh

⊗ Fh

˜ci

c∗ Fh

⊗ Fh

⊗ Fh

˜c∗

36 At this point the scratch registers are fully transformed, and we bring in new ones for the next pair (a1, a 2).

Stage 3 — conclusion

Let us analyse what has happened to the physical values over the course of all three stages.

All 3 |T|2(|P| + h + 1) scratch registers have been fully transformed.

The initial values ˜ ya1,a 2,a 3 , which started out in the y registers, have ended up in the x

registers, fully transformed, and with a harmless minus sign.

The initial values ˜ xa1,a 2,a 3 , which started out in the x registers, have ended up in the y

registers. They have been fully transformed, up to a rearrangement, by the same argument used in the baby case (see the section “What did the baby program achieve?”). Therefore, the net result is that every single register has been fully transformed (modulo free rearrangements and sign changes). The number of slice calls in Stage 3 for each pair ( a1, a 2) is

|T|�(h2 − 1)( h − 1) + ( h2 − 1)( h − 1) + ( h − 1) + ( h − 1)

|P|�(h2 − 1) + ( h2 − 1)( h − 1) + 1 + ( h − 2) + 1
�(h2 − 1) h(h + 1) + ( h + 1) h + ( h + 1) h + ( h + 1) h

= 2 |T|(h3 − h2) + |P|h3 + ( h2 + 2)( h2 + h).

Thus the total number of slice calls in Stage 3 over all pairs is 2|T|3(h3 − h2) + |T|2|P|h3 + |T|2(h2 + 2)( h2 + h).

Summing over all three stages, the grand total is 2|T|3(h3 − 1) + 3 |T|2|P|h3 + 3 |T|2(h2 + 2)( h2 + h).

Recalling that the number of registers is W = 2 |T|3 + 3 |T|2(|P| + h + 1), after a bit of algebra we can rewrite the grand total as

W h 3 − | T|2(2 |T| − 6h(h + 1)) .

Since |T| is cubic in h, for sufficiently large h the bracketed term is positive (according to Fable, for h ⩾ 22), and we see that the total number of slice calls is strictly less than W h 3 = W m . And this is exactly what the tensor amplification wants. Unbelievable.

8 Conclusion

As far as I can see, the gadget does what it’s supposed to do. I have worked through all the steps pretty carefully, and I think it checks out. (Where it came from, I have no idea.) I also think I believe the tensor amplification machinery. Parts I still don’t understand properly: 37 How the linear operation count and the synthetic roots of unity interact with the tensor amplification, and how to go from 2 × · · · × 2 to r × · · · × r. All of this feels like it should be okay, but I need to think about it some more to be certain.

How the rest of the 2021 algorithm behaves when d is allowed to grow at the required rate. Again this feels like it should be okay, but I haven’t checked.

The big one: data rearrangement costs in the Turing model. I haven’t even begun to look into this yet. Some final thoughts about the log n exponent. To improve it, one would need to find a more efficient gadget. I gather that this is what people (and their LLM helpers) have been doing. The impression I got from a very quick glance at their repositories is that they are trying to come up with clever optimisations of the existing construction. But one other thing that might be interesting to try (if they haven’t already done so) is to simply do some kind of (clever?) brute-force search for a very small gadget. Who knows, maybe it’s possible to write down a non-trivial gadget for I ⊗ B⊗3

acting on C4 ⊗ (C2)⊗3 or something silly like that. I mean, no-one has ever actually tried, right? Still a lot of work to do. But I need a break now.

References

[AFKL19] P. Afshani, C. B. Freksen, L. Kamma, and K. G. Larsen, Lower bounds for multiplica-tion via network coding , 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (Dagstuhl, Germany) (Christel Baier, Ioannis Chatzigian-nakis, Paola Flocchini, and Stefano Leonardi, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 132, Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2019, pp. 10:1–10:12. [Har26] D. Harvey, Faster enumeration of primes , https://arxiv.org/abs/2606.22851 , 2026. [HvdH19] D. Harvey and J. van der Hoeven, Faster polynomial multiplication over finite fields using cyclotomic coefficient rings , J. Complexity 54 (2019), 101404, 18. MR 3983215 [HvdH21] , Integer multiplication in time O(n log n), Ann. of Math. (2) 193 (2021), no. 2, 563–617. MR 4224716 [HvdH22] , Polynomial multiplication over finite fields in time O(n log n), J. ACM 69

(2022), no. 2, Art. 12, 40. MR 4433320 [HvdH25] D. Harvey and J. van der Hoeven, Integer multiplication is at least as hard as matrix transposition , https://arxiv.org/abs/2503.22848 , 2025. [LL04] Zongpeng Li and Baochun Li, Network coding in undirected networks , CISS, 2004. [TC26a] The Company, Integer multiplication below n log n, GitHub, 2026. [TC26b] , Finite tensor savings and exact Fourier circuits , GitHub, 2026. [TC26c] , An explicit power saving for the exact discrete Fourier transform , GitHub, 2026. 38