Слишком хорошо, чтобы пропустить: Терри Тао почти доказывает гипотезу Коллатца

Некоторые новости прошлого года заслуживают второго шанса. Здесь у нас есть одна такая – хотя и не так хорошо известная, как давняя гипотеза P = NP, Коллатц очаровывала людей в течение последних восьми десятилетий и представила почти столько же ошибочных доказательств. Теперь математик Теренс Тао, кажется, близок к доказательству.

(2019-09-13)

Если вы не знаете, что такое гипотеза Коллатца, значит, вы не пропустили ничего действительно важного – за возможным исключением прекрасного мультфильма xkcd, воспроизведенного ниже:

Рисунок точен, но давайте проясним гипотезу, выдвинутую в 1937 году немецким математиком Лотаром Коллатцем:

Выберите число, положительное целое число

Если даже разделить на 2

Если нечетное умножьте на 3 и прибавьте единицу

Повторите два вышеуказанных шага с новым значением

Если вы попробуете, то обнаружите, что в конечном итоге получите результат 1. Например, 10, 5,16, 8, 4, 2, 1. Сначала вы думаете, что это случайность, и поэтому пытаетесь выполнить еще несколько тестов. . Затем вы становитесь одержимыми и пишете программу – и всегда получаете 1.

Пока что это было проверено для значений до 5,76×10 ^ 18.

Гипотеза Коллатца состоит в том, что это действительно всегда верно, но можете ли вы это доказать?

Если вы думаете, что это должно быть легко, то стоит знать, что Пол Эрдеш провозгласил:

«Математика может быть не готова к таким задачам»

Теренс Тао из Университета Калифорнии ближе к доказательству, чем когда-либо. Почему это не доказательство? Потому что это вероятностный аргумент:

Почти все орбиты отображения Коллатца достигают почти ограниченных значений.

Почему это важно? Причина в том, что если вы можете показать, что минимум последовательности Коллатца для N всегда меньше N для всех N> 1, то вы доказали гипотезу Коллатца. Причина проста. Если вы получите значение m, меньшее, чем N, тогда остальная часть последовательности для N будет такой же, как если бы вы начали с m, и теперь у нас есть, что минимум для последовательности меньше m. Вы можете повторить это и вернуться, чтобы доказать, что минимум должен быть равен 1.

Дао не совсем доказал это, но он доказал (переписанный, чтобы быть ближе к английскому):

Теорема 2 Пусть f – любая функция, определенная на целых числах, исключая ноль, и f (N) стремится к бесконечности с N, тогда минимум последовательности Коллатца для N меньше f (N) почти для всех N.

Если взять f за тождество, то минимальное значение Коллатца для N меньше N.

Итак, проблема решена?

Не совсем. В теореме есть ласковое слово «почти для всех». Это сигнал того, что теорема вероятностная. Это означает, что множество N, для которого это верно, плотно (в смысле логарифмической плотности). В нетехническом смысле это означает, что мы доказали, что теорема верна для всех, кроме незначительного числа случаев.

Незначительное число случаев также включает в себя отсутствие случаев вообще, поэтому теорема может применяться ко всем N или может быть несколько примеров, когда она не применяется, а гипотеза Коллатца в конце концов неверна.

Так что это?

Как пишет Тао в ответе на комментарий к своему сообщению в блоге:

«… но это одна из тех ситуаций, когда кажется, что существует огромный разрыв между« почти всеми »и« всеми »результатами».

Похоже, что гипотеза Коллатца продержится еще некоторое время. Вооружившись этим вероятностным аргументом, можно будет увидеть новые причины его истинности.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *