СоХабр закрыт.

С 13.05.2019 изменения постов больше не отслеживаются, и новые посты не сохраняются.

| сохранено

H Доказательство гипотезы Коллатца в черновиках Recovery Mode

Математика
Продолжу начатую предыдущим постом тему доказательством гипотезы Коллатца.

В чём заключается эта гипотеза? Возьмём любое натуральное число $n$. Если оно чётное, то делим его на $2$, а если нечётное, то умножаем на $3$ и прибавляем $1$ (получаем $3n + 1$). Над полученным числом выполняем те же самые действия, и так далее. Гипотеза Коллатца заключается в том, что какое бы начальное число $n$ мы ни взяли, рано или поздно мы получим единицу.

Доказательство гипотезы Коллатца


Переформулируем гипотезу следующим образом: возьмём любое натуральное число $n$. Если оно чётное, то делим его на $2$ пока оно не потеряет свойство чётности, а потом переводим в систему счисления по основанию $\dfrac{1}{3}$ и прибавляем $1$ до тех пор, пока основание системы счисления не станет обратным $n$, на каждом шаге умножая $n$ на $\dfrac{p_i}{p_{i-1}}$, где $p_i$ — номер текущего шага. Гипотеза Коллатца в такой формулировке заключается в том, что какое бы начальное число $n$ мы ни взяли, рано или поздно это произойдёт, то есть в том, что уравнение

$\dfrac{1}{pn}=\dfrac{1}{3^m+m}$

где $m$ — число нечётных шагов, $p$ — общее число шагов, имеет решение при любом натуральном $n$, что очевидно так.

Доказано.

Но ничего не понятно, особенно почему я переформулировал гипотезу именно так и откуда в ней взялось число шагов. Может быть я не прав? Проверим на конкретных примерах со страницы в Википедии.

Для числа $3$ получаем

$\dfrac{1}{3p}=\dfrac{1}{3^m+m}$


решением является $m=3, p=8$, то есть число $3$ можно преобразовать в $1$ за три нечётных шага, а всего для этого потребуется $8$ шагов. Верно.
Для числа $19$ получаем

$\dfrac{1}{19p}=\dfrac{1}{3^m+m}$


решением является $m=7, p=20$, то есть число $19$ можно преобразовать в $1$ за семь нечётных шага, а всего для этого потребуется $20$ шагов. Тоже верно, но всё равно ничего не ясно. Ответ ниже.

Внимание! Слабонервным и испорченным российским математическим образованием просьба дальше не читать!

Некоторые основные понятия теории энтропии


Система — неопределимое понятие, на основании которого строятся недоказуемые определения:
Энтропия — информационная ёмкость системы.
Экстропия — величина, противоположная энтропии.
Фазовый переход — уменьшение энтропии на один порядок, происходящий при накоплении достаточного и необходимого объёма знаний.

Эволюция маленькой n


Рассмотрим на конкретном примере: возьмём из формулировки гипотезы n и превратим его в $n$. Как этого достичь? Уменьшая незнание, то есть задавая вопросы на которые возможен только однозначный ответ «да» или «нет». Поехали:
1. n — самолёт? Нет. Этот ответ уменьшил наше незнание о n на знание «n — не самолёт», но не сообщил нам ничего о свойствах n, то есть он уменьшил энтропию, но не увеличил экстропию.
2. n — математический объект? Да. Этот ответ увеличил экстропию, теперь мы знаем, что n — математический объект, следовательно обладает всеми свойствами математического объекта, в частности является переменной либо константой.
3. n — константа? Нет. Этот ответ снова снизил энтропию и произвёл фазовый переход. Количество накопленной информации «n — математический объект» и «n — не константа» перешло в её качество — вывод "$n$ — переменная" и теперь позволяет нам уменьшить энтропию данных выше определений.

Энтропия (в математике) — неотъемлемое свойство математического объекта, мера нашего незнания о нём как о системе, величина измеряемая в битах энтропии. Неформально: ответ «нет» на вопрос.

Экстропия (в математике) — величина, противоположная энтропии (в математике), мера нашего знания о математическом объекте как о системе, величина измеряемая в битах экстропии. Неформально: ответ «да» на вопрос.

Фазовый переход (в математике) — уменьшение энтропии (в математике) на один бит энтропии, происходящий при накоплении достаточного и необходимого объёма знаний.

Немного магии теории энтропии


Так как же всё-таки я получил свой эквивалент гипотезы Коллатца? Допустим, что изначально $n$ имело вид $8m$, то есть содержало $3$ бита экстропии: ответы «да» на вопросы «делится ли $n$ на $2,4,8$ соответственно?» и некоторое количество бит энтропии, определяемое переменной $m$. Операцией деления на $2$ мы трижды экстропию понизили, в итоге она стала равна нолю, энтропия же осталась неизменной и равной $2^p$, где $p$ — число разрядов в двоичной записи числа $q$. Переводом в систему счисления с дробным основанием мы каждый раз совершали фазовый переход (в математике), так как получали знание "$q$ делится на $3$", то есть, выражаясь понятным программистам языком, совершали битовый сдвиг влево и заменяли ноль в крайнем правом разряде на единицу. В итоге за $p$ сдвигов у нас из полностью неопределённого числа получилось числа с $p$ разрядами, все цифры в котором ноли, то есть число полностью определённое. Прибавив к нолям единицу мы и получили искомое.

P.S. Вдумчивый читатель наверняка обратил внимание на то, что важнейшим следствием из доказательства гипотезы служит тот факт, что $3^m - m$ число всегда составное при любом $m>2$. Это важнейшее открытие, ключ к экспоненциальному снижению вычислительной сложности компьютерной задачи факторизации больших чисел. Я обязательно разовью эту тему в следующем посте, который, видимо, из-за моей отрицательной кармы, увидит свет только через неделю.
–9
~1600
  Human2

комментарии (46)

+1
yarric ,  

Ничего себе! А уравнения Навье-Стокса решите?

0
Nikeware ,  

Доказательство в пару строк. Прям как с гипотезой Риманна ;-).

–1
ThisMan ,  
Вот интересно, откуда берутся такие гипотезы? Ну то есть, почему именно к нечетным нужно умножить на 3 и прибавить 1, а не два. Ведь можно таких последовательностей сколько угодно придумать и пытаться доказать. И есть какая то практическая зона применений?
0
mihaild ,  
Если прибавлять не 1, а 2, то из нечетного получается большее нечетное, и ничего интересного не выйдет.
Вообще есть обобщение: вместо разбиения на четные-нечетные, мы разбиваем на классы по модулю P, и для каждого класса делаем свое линейное преобразование (такое, чтобы результат для данного класса получился целым).
Для такого обобщения можно доказать, что по заданным параметрам и начальному числу определить, дойдет ли последовательность до 1, алгоритмически нельзя.
Соответственно, можно поменять параметры таким образом, что заведомо нельзя будет ни доказать, ни опровергнуть, что последовательность достигнет 1.

В общем случаи такие проблемы возникают примерно так: какая-то просто формулируемая задача по какой-то причине становится известной и обнаруживают, что ее просто решить не получается. Т.к. большинство просто формулируемых задач всё же решаются проще, задача от этого становится еще известнее — возникает положительная обратная связь.
+5
mihaild ,  
Могу заметить, что понятие «система счисления по основанию 1/3» не определено, а прибавление числа не зависит от системы счисления.
Кроме того, непосредственно проверяется, что 1 / (3 * 8) = 24, 1 / (3^3 + 3) = 1/30, 1/30 != 1/24. И еще 1 / (19 * 20) = 1 / 380, 1 / (3^7 + 7) = 1 / 2194, 1 / 380 != 1 / 2194. Так что наборы (n = 3, p = 8, m = 3) и (n = 19, p = 20, m = 7) не являются решениями уравнения 1/(pn) = 1 / (3^m + m).

Еще можно заметить, что в последовательностях для чисел 12 и 13 одинаковое количество умножений и делений (по 2 умножения и 7 делений), так что любая попытка выразить исходное число через количество операций каждого вида обречена на провал.
–1
Human2 ,  
Спасибо за конструктив, отредактировал. Что же касается понятия «система счисления по основанию 1/3», то оно не определено настолько же, насколько не определено понятие «система счисления по основанию 10»
0
mihaild ,  
Определено. Система счисления по основанию 10 — это отображение множества натуральных (для простоты) чисел в множество строк в алфавите {0, 1, ..., 9}.

Отредактировали замечательно — удалили единственную более-менее нормально сформулированную часть.
С «неопределяемыми понятиями» есть проблема: гипотеза Коллатца формулируется как утверждение в, например, теории множеств. Соответственно любые используемые понятия должны быть определены в той же теории.
(собственно даже в том, что у вас написано вместо определений, невооруженным взглядом видны противоречия, но копаться в этом смысла нет)
0
Sirion ,  
Это не «конструктив». Если в доказательстве находят столь зияющие дыры, это не значит, что их нужно быстренько залатать и всё будет нормально. Это значит, что проблема глубже. В самой идее доказательства. И в самом понятии, что такое доказательство, в голове доказывающего.
0
munrocket ,  
Что за система исчисления по основанию 1/3? Объясните на пальцах что вы доказываете, если вы пришли на ресурс для программистов. И чем вас традиционная система по основанию 3 не устроила, они же эквивалентны.
0
mihaild ,  
Так вы не знаете, что такое система исчисления по основанию 1/3 (я точно не знаю), или знаете, что она эквивалентна системе с основанием 3?)
0
munrocket ,   * (был изменён)
Автор не умеет излагать свои мысли просто, а делает `короткое доказательство`, поэтому под этой фразой могло быть что угодно. Очевидно число Пи в системе исчисления 1/10 будет бесконечно «большое» и записываться так ...5141.3 и в чем профит спрашивается?
+1
Welran ,  
Эмм, кому это очевидно?
–1
munrocket ,  
Все таки очевидно, что если обратить основание, то число записывается задом наперед. Если вам нет, то подумаете еще разок. Но зачем это делать кроме как для запутывания?
0
PastorGL ,  
Основанием системы счисления может быть что угодно, кроме нуля. Не обязательно целое, и даже не обязательно рациональное число, примеры см. в Википедии.
0
munrocket ,   * (был изменён)
Тогда он умышленно усложняет свое доказательство. Так как большие цифры не удобно в системе 1/3 записывать. C таким же успехом можно было выбрать основание 3.
0
qw1 ,  
Внимательно читайте свою ссылку. Там определены системы счисления с основанием > 1.
+1
staticlab ,   * (был изменён)
все цифры в котором единицы… запись которого в десятичной системе счисления 1

В любой системе счисления с натуральным основанием существует бесконечно много чисел, которые записываются исключительно цифрами 1, но только одно из них равно 1.

0
gecube ,  
В чём заключается эта гипотеза? Возьмём любое натуральное число. Если оно чётное, то делим его на, а если нечётное, то умножаем на и прибавляем (получаем ). Над полученным числом выполняем те же самые действия, и так далее. Гипотеза Коллатца заключается в том, что какое бы начальное число мы ни взяли, рано или поздно мы получим единицу.

Не понял. Зачем умножать на 3? С тем же успехом можно было взять гипотезу, что:
— берем четное число и делим его на 2;
— берем нечетное число и добавляем к нему 1;
Рано или поздно придем к 1.
0
mihaild ,  
Затем, что гипотеза Коллатца формулируется так. Можно рассмотреть и другие правила преобразования. Для некоторых из них (например, «делить четные на 2, прибавлять к нечетным 1») задача получится тривиальной. Для некоторых — заведомо неразрешимой (не получится ни доказать, ни опровергнуть, что рано или поздно придем к 1).
0
gecube ,  
Чем гипотеза Коллатца лучше любой другой подобной гипотезы, с другими значениями n? Можете в общем случае доказать для любого n, что либо существует доказательство для сходимости этого «ряда» к определенному числу, либо нет?
0
mihaild ,  
Что значит «с другими значениями n»?
Обобщение последовательности выглядит так: выбран модуль P, и дан набор правил вида «если x дает остаток i по модулю P, то заменяем x на a_i x + b_i». Начинаем с какого-то числа. Придем к 1 или нет?

Гипотеза Коллатца: для P = 2 и правил «четное делим на 2», «нечетное умножаем на 3 и прибавляем 1» и любого первого члена рано или поздно придем к 1.

Ничего особо фундаментального именно в этом наборе правил вроде бы нет. Просто «по историческим причинам» рассматривается именно он.

>Можете в общем случае доказать для любого n, что либо существует доказательство для сходимости этого «ряда» к определенному числу, либо нет?
Да, я могу доказать, что для любого конкретного утверждения либо существует его доказательство, либо не существует:) Вы, видимо, хотели спросить что-то другое.
0
Hardcoin ,  
Да, я могу доказать, что для любого конкретного утверждения либо существует его доказательство, либо не существует:)

Интересное утверждение. На самом деле можете? Это вообще возможно?

0
mihaild ,  
Да, элементарно.
Пусть X — наше утверждение.
Формула «А или не-А» является тавтологией исчисления высказываний.
Подставляем вместо A утверждение «X доказуемо». Получаем что "(X доказуемо) или (X недоказуемо)" является логической аксиомой исчисления предикатов.
Соответственно, последовательность
1. (X доказуемо) или (X недоказуемо)
является доказательством утверждения в исчислении предикатов.
0
Hardcoin ,  

В таком виде да. Я сначала, что вы можете доказать доказуемость/недоказуемость. А то, что верно одно из двух (но мы не знаем, какое) — это и так понятно )

0
mihaild ,  
Ну вы спрашивали
>Можете в общем случае доказать для любого n, что либо существует доказательство для сходимости этого «ряда» к определенному числу, либо нет?
Прочитать это синонимично к «по n проверить, доказуемо ли утверждение», я не могу.

Т.к. к задаче «верно ли, что для данного набора правил последовательность, начинающаяся с данного числа, придет к 1» сводится проблема останова, то понятно, что для любой (хорошей) теории есть набор правил и начальный член, такие что в этой теории нельзя ни доказать, ни опровергнуть наличие единицы в получающейся последовательности нельзя.
Для некоторых конкретных наборов правил и начальных членов можно легко.
Что получается при наборе правил из гипотезы Коллатца — не знаю, и никто не знает.
Если гипотеза Коллатца верна, то для любого конкретного n можно доказать, что начинающаяся с него последовательность придет к 1. Если неверна — может в принципе оказаться, что для какого-то n нельзя ни доказать, ни опровергнуть что начав с него придем к 1.
0
Hardcoin ,  
Прочитать это синонимично к «по n проверить, доказуемо ли утверждение», я не могу.

Это спрашивал не я, но именно так я читаю — доказать, что доказательство существует (если существует), либо не существует (если не существует). То есть определить, есть ли доказательство.

0
mihaild ,  
Это вопрос перевода с естественного языка на формальный. Формальных правил тут естественно нет, но обычно когда говорят «доказать, что ...» понимают именно доказательство одного утверждения.
+2
Refridgerator ,  
Ждём простое доказательство теоремы Ферма через магию теории энтропии.
0
staticlab ,  

В прошлой серии автор написал доказательство гипотезы Била через энтропию. Великая теорема Ферма легко доказывается при условии справедливости этой гипотезы. Доказательство приведено здесь.

0
Refridgerator ,   * (был изменён)
Да, действительно, брать надо выше — искать простое доказательство abc-гипотезы, ведь Мотидзуки с ним явно что-то намудрил.
0
Sychuan ,  
Вроде как у него уже нашли ошибку www.quantamagazine.org/titans-of-mathematics-clash-over-epic-proof-of-abc-conjecture-20180920
И судя по блогам математиков для Мотидзуки все очень плохо.
+1
Temmokan ,  
Доказательство, я так понимаю — это фраза «что очевидно».

Что-то мировое математическое сообщество ни единым словом не выразило ликования по поводу решения гипотезы.
+1
Sirion ,  
Зато на хабре уже 9 плюсов. Мне было бы очень интересно пообщаться с их авторами.
0
staticlab ,  

Если точнее, к этой статье было 13 плюсов, а к предыдущей 18.

0
Sirion ,  
Мне интересно, эти люди вообще читали текст, или плюсанули не глядя, потому что «огого математика хабр торт!1»
0
mihaild ,  
Приходите в дискуссионный раздел dxdy или на вихру (если еще не), там таких много.
0
Sirion ,  
Ну, я думал, тамошние обитатели там и живут, не выбираясь массово на другие ресурсы.
–1
Refridgerator ,   * (был изменён)
Зато на хабре уже 9 плюсов. Мне было бы очень интересно пообщаться с их авторами.
Ну, я поставил прошлой статье плюс. Объясню, почему:

1) мне самому недавно наставили минусов, хотелось реабилитироваться и поддержать плюсом другого несчастного;
2) тема интересная, и к оформлению статьи нет претензий;
3) даже если автор ошибается — все иногда ошибаются, это как минимум даёт повод для дискуссий;
4) жанр «математическая фантастика» тоже имеет право на существование.
+1
mihaild ,  
Это не ошибка, это not even wrong. И даже если человек по какой-то причине никогда не слышал про то, что используемые понятия нужно определять — в комментариях ему про это сказали, но улучшений не произошло.
0
Sirion ,  
Я не вижу у вас недавней заминусованной статьи. В черновиках?
0
Refridgerator ,  
Нет, просто первой реакцией на последнюю статью были не первые комментарии, а минусы в карму)
0
Refridgerator ,   * (был изменён)
Опять же, истинность математических выкладок никак не зависит от того, как много людей посчитают эти выкладки истинными. Да и автор слегка слукавил — исходя из заголовка кажется, что он этот миллион уже получил.
0
Sirion ,  
Вообще-то именно от этого она и зависит. Математическое доказательство — это текст, с помощью которого один математик убеждает других математиков в своей правоте. Доказательство, которое никого не способно убедить, ничтожно независимо от своих внутренних качеств.
0
Refridgerator ,   * (был изменён)
В одной из книг автор-математик сказал примерно следующее: «Математики не пишут доказательства. Математики плетут узоры». Находят связи между различными элементами и понятиями, которые помогают находить более короткие пути для решения задач. Ну или просто бродить по дебрям математических абстракций без риска заблудиться) А доказательства помогают убедиться, что эти связи — реальны.

И автор обсуждаемых статей пытается убедить нас, что есть особенная связь между основанием 1/3 и гипотезой Коллатца. И есть связь между признаками делимости чисел с окончаниями 1, 3, 7, 9 и гипотезой Била. И есть связь между термодинамикой и теорией чисел. И возможно даже, что кого-то убедил. Но это ничего не меняет, ни для кого.
0
Sirion ,  
Это называется, прошу прощения, «влияние мочи на солнечные лучи».

Математика — это когда видишь связи, которые есть. Когда видишь связи, которых нет — это апофения.
0
mihaild ,  
Это уже вопрос личного восприятия, скорее.
Истинность математических выкладок, безусловно, не зависит от людей. Но т.к. у нас нет прямого доступа к безошибочному оракулу истинности — то приходится использовать экспертные оценки в качестве прокси.
В математике (а также в науке) любой желающий, теоретически, может сам стать экспертом, способным проверять чужие работы.

Вопрос о том, что из формализма и интуиции является «сутью» математики, а что — только общением математиков — однозначного ответа не имеет, и разные очень сильные математики отвечают на него по-разному. Впрочем, математикой к счастью можно заниматься и не отвечая на него.