数の格子のかけ算に新記録

二つの行列(数を並べた格子)をかけ合わせることは、計算において最も基本的な演算の一つだ。教科書どおりのやり方では、n行n列の格子どうしのかけ算のコストはn³のように増える。フォルカー・シュトラッセン(Volker Strassen)の1969年のアルゴリズムが、初めてそれより速く計算した。論文の言葉でいえば「劣立方」(subcubic)だ。以来、数学者たちは一つの数で進歩を測ってきた。指数ω(オメガ)、つまり格子が大きくなるときに十分なnの最小のべきである。

シュトラッセンはそれを2.81未満にした。論文に一覧が載っている数十年にわたる研究によって、刻み幅をどんどん小さくしながら、約2.37まで下がってきた。2026年には、エミリアン・デュポン(Emilien Dupont)らが2.371177に到達した。そして今回、Matroid, Inc.社のレザ・ザデー(Reza Zadeh)がω < 2.37115924を証明した。

1969年のシュトラッセンから本論文までの、ωの上界の主な改善。— 表1、Zadeh (2026), arXiv:2610.10593, CC BY 4.0.

21万2820個の設定をもつレシピ

こうした記録は、小さな格子のためのより巧妙な技から生まれるわけではない。生まれるもとは、コッパースミス=ウィノグラード・テンソルと呼ばれる代数的な対象だ。これは切り分けて組み合わせ直すことを再帰的に繰り返すことで、多数の独立した行列の積に変えられる。どう切り分けるかは、膨大な選択の集合で決まる。確率分布、エントロピーのペナルティ、そして階層ごとに定められる行列のサイズなどだ。有効な選択の組はどれも有効な上界を与える。腕の見せどころは、よい組を見つけることにある。

ジョシュ・アルマン(Josh Alman)らの枠組みと、デュポンらの定式化を土台に、ザデーは21万2820個の数を同時に調整した。そこには三つの改良がある。

• 重要度に応じた尺度の変更。 構成の一部の要素はまれにしか現れないため、結果への影響はごくわずかで、最適化手法はそれらをほとんど動かさない。そこで各数を、その要素が担う重みに応じて尺度変更した。
• ボトルネックのための6つのダイヤル。 最終的な指数は、三つの段階で競合する三つの量のうち最も弱いものによって決まる。別個の補正で、わずか6つの調整つまみを使ってそれらの釣り合いを保った。
• 厳密な書き出し。 最終的なレシピは、分母が2⁹⁶の厳密な分数に変換された。

検証による証明

この上界は、コンピューター支援による証明だ。Pythonの標準ライブラリだけを使う短いプログラムが(ネットワークも、モデルも、追加パッケージも使わない)、厳密な分数からすべての分布を再構築し、丸め誤差を保証した計算で結果を評価する。プログラムは、鍵となる量が約85億分の1だけ正であることを確かめ、これが上界を証明する。著者は、これがカバーしない範囲も強調している。このプログラムは監査可能なコードであって、証明支援系で理論全体を形式化したものではない。また探索は局所的なもので、このレシピが可能な限り最良だとは主張していない。

著者はまた、名前を挙げていない生成AIツールが数値的な探索、ソフトウェア、原稿の作成を支援したこと、そして初期のコードがエリック・ナスルンド(Eric Naslund)が公開で共有していた計算メモをもとにしたことも記している。2026年10月5日に公開された別のコンピューター証明書は2.371169353に到達していたが、新しい値はそれよりさらに低い。

理論の上では、より速く

デュポンらの結果に対する改善は、指数で0.00001776だ。この方法で得られる上界はどれもそうだが、保証は漸近的なものである。指数だけでは、新しいアルゴリズムがどの行列サイズから実際に既存の手法に勝つのかはわからない。変わるのは、1969年から続く問いに対する最良の既知の答えだ。数の格子は、原理的にどれだけ速くかけ合わせられるのか。