方程式を解くとき、コンピューターはしばしば推測し、確かめ、また推測する。1回まわるごとに答えに近づく。では、1回でどこまで近づけるのだろうか。
ニュートン法は1回につき2つの問いを発する。関数の値とその傾きだ。答えの近くでは、正しい桁の数が1回ごとに2倍になる。
1974年、KungとTraubは速さの限界を予想した。1回につきn個の問いでは、次数は2のn−1乗を決して超えられない。2人はその限界に達する方法をつくっていた。だが、それが破られないことは誰も証明できなかった。
ケンブリッジ大学のMatthew Colbrookが、いまそれを証明した。秘訣は、同じ答えを返しながら、零点を別の場所に隠す関数をつくることだ。証明支援系Leanが、その結果を検証した。
出典:Adversarial Wronskians: A proof of the Kung–Traub conjecture, https://arxiv.org/abs/2610.40660









