方程式を解く速さの限界、1974年の予想がついに証明された

関数fがゼロを横切る場所を見つけるため、コンピューターはしばしば反復法（iteration）を実行する。推測値xから始め、関数にいくつか問いかけ、よりよい推測値を計算し、それを繰り返す。問いかけとは評価（evaluation）のことだ。ある点でのfの値、あるいはその傾き（導関数）や、さらに高階の導関数の値である。

2倍になる桁

こうした方法の速さは、その次数（order）で測られる。現在の誤差をεとすると、次数pの反復法では、誤差はおおよそεのp乗になる。次数2は、答えの近くでは正しい桁の数が1ステップごとに2倍になることを意味し、次数4は4倍になることを意味する。

ニュートン法は1ステップに2回の評価、f(x)とその傾きf′(x)を使い、x − f(x)/f′(x)へ移る。その次数は2だ。1ステップあたりの問いを増やせば、より速くなりうる。問題は、どれだけ速くなるかだ。

1974年の予想

1974年、H. T. KungとJ. F. Traubは、Journal of the ACMに載った論文の「予想8.1」として、1つの答えを提案した。1ステップあたりn回の評価を使う記憶をもたない反復法の次数は、最大でも2ⁿ⁻¹である。「記憶をもたない」とは、その方法が現在の推測値以外、前のステップから何も保持しないことを意味する。

この上限をこれより下げることはできなかった。KungとTraub自身が、n ≥ 2のすべてのnについて2ⁿ⁻¹に達する「多点」法をつくっていたからだ。3回の評価で次数4、4回で8、5回で16である。欠けていたのはもう半分、つまりどんな方法もそれ以上にはなれないという証明だった。部分的な結果は、予想と同時に、そしてそのあとにも得られた。この上限は、補間にもとづく方法、2回の評価を使う有理的な方法、そしてさまざまな追加条件のもとで証明された。関数の値だけを使う方法については、より弱い上限2ⁿが確立された。一般の場合は未解決のままだった。

アルゴリズムをだます

ケンブリッジ大学応用数学・理論物理学科のMatthew Colbrookが、いまこれを完全に証明した。そのモデルは、アルゴリズムに意図的に寛大だ。アルゴリズムは、どこで評価するか、どの導関数をとるかを、進みながら選んでよい。答えをどんな決定論的なやり方で処理してもよく、その規則になめらかさは求められない。

証明は、アルゴリズム自身の決定論性を逆手にとる。すべての問いにまったく同じ答えを返すが、零点が異なる2つの関数をつくるのだ。アルゴリズムはどちらに対しても同じ推測値を返さなければならないので、そのどちらか一方では、2つの零点の距離の少なくとも半分だけ外れる。

そうしたペアを見つけるため、Colbrookは基準となる関数を、n次以下の小さな多項式で少しずらす。この多項式には調整できる係数がn + 1個ある。1回の評価で固定されるのは、それらの組み合わせのうち多くても1つなので、n回問いかけたあとでも、アルゴリズムには見えないずらし方が残る。それを数えるだけでは十分ではない。見えないずらしが、零点をほとんど動かさないかもしれないからだ。

鍵となる道具はロンスキアン（Wronskian）だ。多項式の族とその導関数からつくられる行列式である。新しい補題によれば、族に属する多項式が小さな円板の中に多くの零点を詰め込んでいるなら、その族のロンスキアンはその近くでゼロにならなければならない。零点がこれらの少数の点から離れたままになる関数で、つねにアルゴリズムに答えることで、証明は零点を自由に動ける状態に保つ。

帳簿をつけていくと、指数が現れる。零点から距離εのところで始めると、零点の候補は、少なくとも定数とεのべき乗の積に相当する範囲に広がったままになる。著者の言葉では、「指数は最初の観測のあとでは1のままで、そのあと2倍になっていき、n回の観測のあとで2ⁿ⁻¹になる」。

あらゆるスケールに対する1つの関数

難題が1つ残っていた。次数の定義では、前にかかる定数が関数に依存してよいので、スケールごとに別のまずい関数を用意しても何も証明できない。そこでColbrookは、補正を1つずつ加えていくことで、ただ1つの関数をつくる。それぞれの補正は、アルゴリズムがすでに問いかけたすべての点でゼロになるので、過去の答えはすべてまったく同じままだ。

その極限は整関数（entire function）だ。複素数の範囲でさえ、いたるところでなめらかな関数で、実数直線上での傾きは3/4から5/4のあいだにとどまる。行儀のよい零点を1つだけもつ、着実に上昇する曲線である。2ⁿ⁻¹を超えるどんなpについても、この関数の上では、方法は次数pに達しない。したがって、n ≥ 2について、記憶をもたない場合の最適な次数はちょうど2ⁿ⁻¹となる。論文は、評価が複素数である場合にも同じ上限を証明している。

一度に全部問いかけることの代償

より精密な主張は、評価をグループで行う場合を扱う。グループ内のすべての問いは、その答えがどれか1つでも届く前に選ばれる。並列的な方法の状況だ。グループの大きさがℓ₁, …, ℓₖのとき、次数は最大でもℓ₁ × (ℓ₂ + 1) × … × (ℓₖ + 1)である。n個の問いを一度に全部発すると、次数の上限はnになる。1つずつ発すれば、2ⁿ⁻¹が可能になる。評価が5回なら、5対16だ。

機械による検証

これらの結果は、すべての論理的なステップをチェックする証明支援系Leanで形式的に検証されている。コードは公開されており、Palomarレジストリに登録されている。著者は、Leanによる形式化はChatGPT 6の助けを借りて行われ、その後Lean 4 Comparatorを使って論文の定理と照合されたこと、そしてすべての議論を著者自身が見直し、内容について全責任を負うことを明記している。

この限界が関係するのは、忘れてしまう方法だ。以前のステップを再利用できる方法は別の上限に従い、この論文はそれを扱っていない。