Pour résoudre une équation, un ordinateur devine souvent, vérifie, puis devine à nouveau. Chaque tour se rapproche de la réponse. Mais de combien un tour peut-il s'en rapprocher ?
La méthode de Newton pose deux questions par tour : la valeur et la pente. Près de la réponse, le nombre de chiffres justes double alors à chaque tour.
En 1974, Kung et Traub ont conjecturé une limite de vitesse. Avec n questions par tour, l'ordre ne dépasse jamais 2 puissance n−1. Leurs propres méthodes l'atteignaient déjà. Personne ne savait prouver qu'on ne peut pas faire mieux.
Matthew Colbrook, à Cambridge, vient de le démontrer. L'astuce : des fonctions aux réponses identiques, mais au zéro caché ailleurs. Un assistant de preuve, Lean, a vérifié le résultat.
Source : Adversarial Wronskians: A proof of the Kung–Traub conjecture, https://arxiv.org/abs/2610.40660









