Чтобы решить уравнение, компьютер часто делает догадку, проверяет её, а затем снова угадывает. Каждый раунд приближает к ответу. Но насколько ближе может подвести один раунд?
Метод Ньютона задаёт за раунд два вопроса: значение функции и её наклон. Вблизи ответа число верных цифр при этом удваивается с каждым раундом.
В 1974 году Кунг и Трауб предположили, что существует предел скорости. При n вопросах за раунд порядок никогда не может превысить 2 в степени n−1. Они построили методы, достигающие этого предела. Никто не мог доказать, что его нельзя превзойти.
Теперь доказательство получено: его автор — Мэтью Колбрук (Matthew Colbrook) из Кембриджа. Хитрость: строить функции, которые дают те же ответы, но прячут свой ноль в другом месте. Результат проверила система автоматической проверки доказательств Lean.
Источник: Adversarial Wronskians: A proof of the Kung–Traub conjecture, https://arxiv.org/abs/2610.40660









