OpenAIのFFTアルゴリズムはブレークスルーではなく悪質なエクスプロイトである

高速フーリエ変換 OpenAIのFFTアルゴリズムはブレークスルーではなく悪質なエクスプロイトである。 Ben Recht 2026年10月12日 皆さん、argminの読者の皆さん、こんにちは！今日の投稿は、OpenAIの数学リポジトリの一部で、高速フーリエ変換を計算すると主張しているものについて見ていきます。いつものより技術的な内容ですが、信号処理や計算複雑性理論の復習が必要な方のために、いくつかのチュートリアル資料を追加しました。 高速フーリエ変換（FFT）は、デジタル信号処理における最も重要な発明の一つであり、私のお気に入りのアルゴリズムの一つです。FFTは、信号の周波数成分を抽出するための高速な方法であり、スペクトルの異なる帯域にわたる周波数を迅速に分析、フィルタリング、操作することができます。 フーリエ変換は、単純な内積によって各周波数帯域のエネルギーを計算します。xを入力信号（長さnのサンプル配列）とし、fを周波数とします。このとき、fにおけるxの周波数成分の量は、次の式で計算できます。 デジタル信号の場合、少し数学をすれば、すべての周波数成分を理解するために、周波数2π/nの各倍数ごとに1つずつ、合計n個の内積を計算するだけでよいことがわかります。単純に考えると、これは周波数ごとにn回の乗算と加算が必要です。したがって、完全なフーリエ変換を計算するには、n^2回の算術演算が必要になるようです。 高速フーリエ変換は、1965年にJames CooleyとJohn Tukeyによって考案された巧妙な再帰的手順です。その主なアイデアは、長さnのフーリエ変換は、入力ベクトルをシャッフルし、シャッフルされた成分に対して長さn/2の2つのフーリエ変換を計算し、その後、原子算術演算を使用して出力を再結合することによって計算できるということです。シャッフルと再結合には線形数の算術演算が必要です。この手順を繰り返し、つまりlog2(n)回繰り返すことで、完全な離散フーリエ変換が計算されます。ブックキーピングを含めると、FFTは5 * n log2(n)未満の算術演算で長さnのフーリエ変換を計算します。 この加速を具体的にするために、nが1,000の場合、n^2は1,000,000であり、5 * n log nは約50,000であり、20倍の高速化になります。nが1,000,000の場合、高速化は10,000倍になります。これらの高速化は、信号処理アプリケーションの制約の中で変換が計算可能であるかどうかの違いを生む可能性があります。 FFTの発明以来、人々はさらに高速なフーリエ変換を探してきました。一つの疑問は、どれだけ速くできるかということです。FFTを計算するには、少なくともn回の操作が必要だと思われます。なぜなら、それを書き出すだけでもnステップかかるからです。FFTは、その合理的な速度限界よりも5 * log2(n)倍遅いです。そして、その5 * log2(n)という係数は大きくなる可能性があります。nが1兆の場合、それは200になります。その200という係数を減らすために、何か巧妙なことをできますか？ さて、驚くべきことに、先週OpenAIが数学界に公開した大量の論文の中に、彼らはより高速なフーリエ変換を発見したと主張しています。彼らの「main.pdf」という示唆に富む名前の論文の主な主張は次のとおりです。 私は何が起こっているのかに興味をそそられました。理論上、log(n)項は標準的なFFTよりもわずかに小さいものでした。 この論文を読みましたか？もちろん読んでいません。OpenAIの誰もこの論文を読んでいません。なぜ私が読む必要があるのでしょうか？私は世界の他のすべての数学者がAIの低級な数学に対して行うことをしました。それをスロップマシンに戻し、チャットボットインターフェースで情報検索セッションを実行して、顕著な事実を抽出しました。擬人化して言えば、ChatGPTに自分の出力についてどう思うか尋ねました。これが私たちが今数学の研究を行っている方法です。なんと素晴らしい世界でしょう。 残念ながら、私はより高速なフーリエ変換を見つけられませんでした。代わりに、形式主義が現実に乖離しすぎて、「ブレークスルー」が数学者が自然言語でゲームのルールを適切に指定できないことから生じる単なるアーティファクトになったときに、応用数学理論の中に発生する腐敗を見つけました。 まず、「ビッグオー記法」は乱用されすぎて無意味になっています。私が学部生の頃に感銘を受けた定義を復習しましょう。アルゴリズムの実行時間は、整数Nと定数Cが存在し、次のような場合にT(n) = O(F(n))となります。 つまり、アルゴリズムが実際に取るステップ数は、nが十分に大きい限り、便利な関数F(n)の定数倍によって上界されます。F(n)は通常、多項式関数や指数関数のような、馴染みがあり解釈可能なものです。この記法は、計算サイズが大きい場合にのみ関心があることを示しています。計算時間の漸近的な成長率に関心があります。すべての定数は同等です。 ビッグオー記法は、アルゴリズムの計算をショートカットするのに役立ちますが、驚くほど論理的な怠惰も許容します。実用的に高速なFFTが必要な場合、合理的なサイズのnに対して50n未満の操作を必要とするアルゴリズムを望みます。しかし、O(n)は50nを意味するわけではありません。それは1080nを意味するかもしれません。これは「線形時間」アルゴリズムと見なされます。n + 1080を必要とするアルゴリズムも、ビッグオーの領域では線形時間アルゴリズムと見なされます。nが1080より大きい場合にのみ線形時間の保証があるアルゴリズムも線形時間と見なされます。1080は、既知の宇宙の原子数にほぼ等しいです。だからこそ、Richard LiptonとKen Reganは、想像を絶するほど大きな隠れた定数を持つアルゴリズムをギャラクティックアルゴリズムと呼んでいます。 OpenAIのFFTアルゴリズムは間違いなくギャラクティックです。N=10^12のときのCの推定値は10^100でした。したがって、nが10^100であっても、古き良きCooley-Tukey-Gauss FFTの方が10^99倍高速になります。 では、この新しいFFTの結果はなぜ興味深いのでしょうか？さて、ビッグオー記法では、技術的にはCooley-Tukeyアルゴリズムよりも漸近的に高速です。 まあ、確かに。しかし、定数を考えると、アルゴリズムはnが不可能に大きい場合にのみ高速に実行されます。おおよそ、次の値が必要です。 その数字が何を意味するのかはわかりませんが。 LiptonとReganは、ギャラクティックアルゴリズムは研究を促進するため有用であると主張しています。実行時間が漸近的に可能であることが示されると、その証明された実行時間を実質的に達成するアルゴリズムを見つけることに時間を費やすことができます。おそらく、AIエージェントの群れをそれに送り込むことができます。ご自由にどうぞ。実用的なアルゴリズムが得られるかもしれませんが、そのような例は聞いたことがありません。特にここでは疑わしいです。なぜなら、OpenAIが使用する「計算」のモデルは、実際のコンピュータとは似ても似つかないからです。 「モデルは厳密な複素数演算を使用します。」これは、任意の精度の複素数を格納および乗算できることを前提としています。実際、アルゴリズムは、nとともに超多項式的に増大する大きさの複素数を乗算することを要求します。これらの数値をビットとして格納した場合、メモリ要件は実質的に入力長の指数関数になります。これは、そのような任意の大きさの複素数を単一の操作で乗算できることを前提としています。私たちはそのようなコンピュータを持っていません。したがって、main.pdfのこの定理が「真実」であるとしても（誰も知りませんし、私も気にしません）、それは私たちがより高速なFFTを探す際に設定した問題を実際に解決しているわけではありません。 FFTの理論的解析に詳しい人にとって、FFTの速度限界を破るために不条理な計算モデルが必要であることは驚くことではありません。1973年、Jacques Morgensternは、計算に使用される複素数係数の大きさが制限されている場合、0.5 * n log nより高速なフーリエ変換を得ることはできないと証明しました。それは物語の終わりであるべきでした！しかし、そうではありませんでした。人々はMorgensternの制限された係数モデルはあまりにも制限的すぎると言いました。40年後、Nir Ailonは、深刻な数値的不安定性なしにn log nより高速なFFTを計算できないことを示しました。これも一部の人々にとってはあまりにも制限的すぎたのでしょう。 したがって、この新しいOpenAIの結果は、数学的なブレークスルーというよりも、コンピュータ科学者が設計仕様を形式化するのが下手であることの奇妙な例です。「計算機」の「理論的」定義は、私たちが実際に構築するコンピュータとはかけ離れています。「より高速な」フーリエ変換は、理論が元の質問からあまりにもかけ離れてしまい、「