Что это за зверь? Гипотеза Била — предложенное в 1993 году математиком-любителем Эндрю Билом (Andrew Beal) утверждение со следующей формулировкой: если , где — натуральные числа и , то имеют общий простой делитель. Казалось бы всё просто, но это только на первый взгляд. Эта задача сложна настолько, что за её доказательство (или опровержение) Бил учредил премию в один миллион долларов. Звучит заманчиво? Очень. На этом вступление будем считать законченным и перейдём непосредственно к доказательству.
К энтропии
Что есть энтропия? Не пугайтесь, этот вопрос в рамках данной статьи мы рассматривать не будем. Рассмотрим числа как на две независимые системы с энтропией соответственно. Можем ли мы сделать это? Конечно. По теореме сложения энтропии при объединении независимых систем их энтропии складываются. Следовательно, энтропия сложной системы равна нолю, так как
при имеет только тривиальное решение. А значит у системы возможно только одно состояние. Или, говоря простым языком, представимо в виде суммы единственным образом с точностью до перестановки слагаемых. Запомним этот факт, мы вернёмся к нему позже.
D значит Dелимость
Введём понятие коэффициента делимости . Пусть — каноническое разложение числа на множители, — число десятков числа , записанного в системе счисления по основанию , тогда является решением системы
Лемма 1: существует для любых чисел, взаимно простых с основанием системы счисления в которой это число записано. Доказательство леммы 1 следует из того факта, что уравнение вида имеет множество решений.
Теорема 1 (теорема Громовой): число делится на , если число без последних цифр плюс последних цифр, умноженных на , делится на .
Данная теорема была впервые сформулирована российским математиком Людмилой Фёдоровной Громовой не позднее 2009 года и я познакомился с ним в этой работе. Доказательство теоремы 1 несложно, но весьма громоздко, поэтому здесь приведено не будет, интересующимся математикой читателям предлагаю доказать её самостоятельно, остальным — прослушать аудио версию доказательства за авторством Александра Александровича Дегтяря.
Per aspera ad astra
Докажем гипотезу Била от противного. Допустим, что числа попарно взаимно просты. Не теряя общности, можем считать Тогда, перейдя в систему счисления по основанию , гипотеза принимает вид . По лемме вычислим для .
Запишем числа в виде , где — первые цифр, считая справа, — остальные цифры. Нетрудно увидеть, что , т.е. вся разница между заключается в том, что в одном разряде у них стоят отличающиеся на единицу цифры. Следовательно, , т.е. коэффициенты делимости тоже отличаются на .
Делится ли на соответственно? Глупый вопрос, конечно же делится. Следовательно, по теореме Громовой,
Преобразуем и вычтем второе уравнение из первого:
Нетрудно увидеть, что при уравнение имеет множество решений. Но по определению может быть равен нолю только для , значит . Следовательно, по теореме Михалеску , но по определению . Противоречие.
А теперь внимание! Фокус! Следите за руками!!!
Ловкость рук, никакого мошенства и немного магии энтропии
Так как энтропия сложной системы , то для числа , а значит и определены однозначно. Следовательно, уравнение не имеет переменных и является не уравнением, а равенством, и может иметь лишь единственное решение, которое вводит нас в противоречие с условием гипотезы Била. Следовательно, наше допущение ложно и имеют общий простой делитель.
Доказано.
Литература: Л.Ф. Громова, Признаки делимости чисел с окончаниями 1, 3, 7, 9
P.S. Используя удивительные свойства энтропии вычислительную сложность задачи факторизации можно снизить с до . Я нашёл этому поистине чудесное доказательство, которое, однако, выходит далеко за рамки этого поста. Мы поговорим об этом в другой раз.
Комментарии (101)
CheY
03.10.2018 18:01+2Самое главное-то не написали. Миллион получили?
Human2 Автор
03.10.2018 18:15Нет. По условиям премии миллион мне дадут только через два года.
aamonster
03.10.2018 18:19Не дадут. Сразу видны слабые места в доказательстве — как минимум, почему вы считаете, что сложение двух чисел эквивалентно объединению соответствующих систем? Да и «законность» представления этих чисел в качестве независимых систем нужно доказать (разобрать все свойства систем, для которых считается энтропия, и проверить, что они выполняются).
Human2 Автор
03.10.2018 18:27Ещё какие-то слабые места видите?
aamonster
03.10.2018 18:41Дальше особо не смотрел (вникать — требует усилий и времени), всё равно без преодоления этих мест не привязать энтропию к доказательству — а значит, и дальнейшая часть теряет смысл (разве что так, чтобы быть в курсе об упомянутых вами теоремах)
Human2 Автор
03.10.2018 19:17Объясню на простом и понятном примере.
Допустим, Петя и Маша подкидывают монетки, каждый свою. Выпасть может орёл или решка (аналогично числа А^x и B^y могут быть любыми, к примеру, 2^3 и 3^2), но если у них выпадают два орла одновременно, то дети кушают по яблоку (аналогично A^x + B^y = C^z, числа 2^3 и 3^2 эквивалентны тому, что одновременно выпали орёл и решка). Можем ли мы определённо сказать сколько дети скушали яблок? Можем, столько же, сколько раз им выпали два орла. То есть энтропия (неопределённость) в данном случае отсутствует (равна нолю).
Так понятнее?
staticlab
03.10.2018 19:36Слабым местом также видится применение теоремы Громовой. В оригинальной статье говорится, что дальнейшие выкладки не распространяются для чисел, делящихся на 2 и 5.
Human2 Автор
03.10.2018 20:14Верно, не распространяются на делители основания системы. В предположении о взаимной простоте A,B,C теорема Громовой будет работать.
staticlab
03.10.2018 19:11+5Как минимум через два года после публикации работы в реферируемом издании. То есть отсчёт ещё не начался.
rafuck
03.10.2018 18:28Поясните, пожалуйста, как получилась первая система? Я взял, к примеру, A = B = C = 2, x = y = 3, z = 4. И получил 2^4 = 2^3 + 2^3, но я не получил 2^4=2^3*2^3
UPD. Вопрос снят. Но рассуждение, которое привело к данной системе, для меня не очевидно.Human2 Автор
03.10.2018 18:33Первая система получилась из теоремы о сложении энтропии. Почитать об этой теореме можно тут.
rafuck
04.10.2018 00:15Фраза про то, что C^z = A^x+B^y представима единственным образом, видимо, не верна, или озвучена недостаточно строго. Поскольку если, например, C^z = A^x+B^y и y = gk, то C^z = A^x+D^k, где D = B^g. Или я не понимаю, что значит выражение «единственным образом» в этом контексте.
Human2 Автор
04.10.2018 00:43Согласен, поработаю над формулировкой. Суть в том, что В^y это не два числа, это единая система.
rafuck
04.10.2018 00:37И еще один вопрос, наверное. Вы предлагаете рассматривать выражения A^x и B^y как некие случайные процессы. Но их энтропия, очевидно, совпадает, поскольку сами эти выражения совпадают с точностью до обозначений, разве нет? (если нет, поясните, почему). Если же да, то из вывода «энтропия C^z равна нулю» следует вывод: энтропия A^x равна нулю.
Human2 Автор
04.10.2018 00:44Не совсем так. Из вывода «энтропия C^z равна нулю» следует вывод: условная энтропия A^x относительно C^z равна нулю.
rafuck
04.10.2018 00:47Так энтропии A^x и B^y совпадают или нет?
Human2 Автор
04.10.2018 05:26С того момента, как мы определили одного из чисел A^x, B^y, C^z энтропии двух других стали равны нолю. Стало быть да, совпадают.
Human2 Автор
04.10.2018 06:04Выражусь точнее: условная энтропия A^x относительно B^y равна 1, то есть A^x не определён настолько же, насколько не определён B^y
rafuck
04.10.2018 11:00Позволю себе спросить еще раз. Вы рассматриваете A^x и B^y как две независимые случайные величины. Можно ли их энтропии сразу же обозначить одной и той же буковкой, например, E?
mihaild
03.10.2018 18:49+2Первая ошибка в третьем предложении третьего абзаца: понятие «взгляд на числа как на две независимые системы с энтропией» не определено.
Hardcoin
03.10.2018 19:44Я верно понимаю, что доказательство ни одним независимым профессиональным математиком пока не проверено?
mihaild
03.10.2018 19:59+1Тут не нужно быть профессиональным математиком, любой хороший студент математической специальности скажет, что это не доказательство.
Human2 Автор
03.10.2018 20:12Верно. Для того и выложил его на Хабр.
mihaild
03.10.2018 20:49Тогда перепишите его с явным выписыванием модулей, где они встречаются, заменой 10 на основание системы исчисления, использующейся в данный момент и т.д. — станет сильно проще читать.
Hilbert
04.10.2018 16:11А статьи на хабре рецензируются математиками? :) Логичнее было направить статью в рецензируемое математическое издание, получили бы отзывы реальных математиков (стиль, конечно, пришлось бы подправить, но пользы куда больше).
Sirion
03.10.2018 20:26+7Тэкс-тэкс-тэкс, что тут у нас? Очередное решение знаменитой математической проблемы с элементарной формулировкой. На Хабре. Ахаха, нунаканецта!
Sirion
03.10.2018 20:56Вообще, мне дико, что кто-то поставил плюсы к столь очевидному бреду. «Формулу сложения энтропии» неплохо было бы проверить для начала на числах 1, 1 и 2.
Human2 Автор
03.10.2018 21:00Проверьте, кто мешает? 1*1=1, 1+1=2, 2 неравно 1. Противоречие.
mihaild
03.10.2018 21:12Вообще т.к. собственно степени и сложение в рассуждении про энтропию не использовались, оно без изменений должно переноситься на любое уравнение вида x = f(y, z). Т.е. у вас получается, что для любой функции f уравнение f(y, z) = x имеет единственное решение относительно y, z.
Human2 Автор
03.10.2018 21:31Нет, не получается.
Рассмотрим два уравнения x + y = 10 и q + p = 20, где x,y,q,p натуральные числа. В первом x,y имеют энтропию 1 децит, во втором q,p 2 децита. В вашем же примере энтропия сложной системы не ограничена (например константами или, как в гипотезе Била, сложением), а следовательно бесконечна.mihaild
03.10.2018 21:47Нет, получается. По крайней мере пока вы не ввели формально все определения.
Human2 Автор
03.10.2018 21:59Определение чего нужно? Слова децит? Это как бит (2 состояния) и байт (8 состояний) только с 10 состояниями.
mihaild
03.10.2018 22:03Всего фреймворка, включающего понятия энтропия, применительно к уравнениям и/или их решениям.
(пока что непонятно ни про энтропию чего вы говорите, ни тем более что такое энтропия этого чего-то)Human2 Автор
03.10.2018 22:06Чуть подождите, сейчас пишу пост с доказательством гипотезы Коллатца, там и введу все определения.
Sirion
03.10.2018 23:06+1По-вашему сумма «энтропий» (логарифмов) чисел должна равняться «энтропии» (логарифму) их суммы. Это очевидная неправда.
Human2 Автор
03.10.2018 23:08-1Хотите опровергнуть давно и не мной доказанную теорему о сложении энтропии? Дерзайте.
daiver19
03.10.2018 23:22+1Теорема сложения энтропий в представленной вами форме исходит из теоремы умножения вероятностей случайных, независимых величин. В условии нет ни слова о таких величинах.
Human2 Автор
03.10.2018 23:32-1А разве A^X и B^y не произвольные (случайные) и независимые друг от друга числа?
staticlab
03.10.2018 23:36+2Это не вероятности.
Human2 Автор
04.10.2018 00:12А что есть вероятность? Вероятность – это одновременно и возможность события, и мера этой возможности.
mihaild
04.10.2018 00:21+1Вероятность — это счетно-аддитивная функция из сигма-алгебры событий в отрезок [0; 1]. Подробнее см. www.machinelearning.ru/wiki/index.php?title=%D0%92%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%BE
Sirion
04.10.2018 01:07Зачем пугаете человека стращными словами? Сказали бы просто, что вероятность — это нормированная мера.
daiver19
03.10.2018 23:37Конечно нет. Это конкретные числа, а не случайные переменные. Вам надо доказать теорему для всех натуральных чисел, а не для двух случайных переменных. Это вообще различные сущности.
Более того, даже если мы представим задачу в терминах теории вероятности в духе «A, B и С — это случайные переменные, такие что A^x + B^y = C^z», то очевидно, что они не независимы между собой (по сути, у вас есть множество из кортежей по 6 переменных из которых вы берете один случайным образом). Не знаю, правда, как это поможет решению.Human2 Автор
04.10.2018 00:16Объясню на простом и понятном примере, который уже приводил выше.
Допустим, Петя и Маша больше не подкидывают монетки, теперь они пишут случайные числа A^x и B^y. Написать они могут любое число (числа А^x и B^y могут быть любыми, к примеру, 2^3 и 3^2), но если так совпало, что A^x + B^y = C^z то дети кушают по яблоку (числа 2^3 и 3^2 эквивалентны тому, что дети яблок не кушают). Можем ли мы определённо сказать сколько дети скушали яблок? Можем, столько же, сколько раз сумма двух случайных переменных оказалась равна C^z. То есть энтропия (неопределённость) в данном случае отсутствует (равна нолю).
Так понятнее?daiver19
04.10.2018 00:41Это эквивалентно тому, что я описал выше — вы выбираете из один из множества валидных кортежей из шести переменных. При чем тут энтропия равная нулю и как из этого следует теорема сложения энтропий мне неясно.
Sirion
04.10.2018 00:24Вы утверждаете, что сумма энтропий равна энтропии суммы. Давайте проверим это на примере. log 1 + log 1 = log (1 + 1). Получилась лажа. Как так вышло?
daiver19
03.10.2018 22:47+1Вы вообще понимаете, что ваша система уравнений неверна чисто с математической точки зрения? Т.е. из A + B = C не следует, что log A + log B = log C (источник: алгебра, 10й класс школы). Вы это хоть энтропией назовите, хоть магическим эфиром, но от этого ничего не изменится.
Или, говоря простым языком, представимо в виде суммы единственным образом с точностью до перестановки слагаемых.
Это неверно, т.к. любое c^z представимо виде бесконечного количества пар a^x + b^y если a и b действительные ну или комплексные. Что-то я не заметил, где вы используете факт того, что числа натуральные.
В общем, это даже на софизм не тянет.Human2 Автор
03.10.2018 23:10Вы, видимо, совсем не понимаете. В системе «log A^x + log B^y = log C^z» то, что A^x + B^y = C^z является аксиомой.
staticlab
04.10.2018 01:50Учитывая, что по вашим выкладкам получается
H(C^z) = 0,
а
H(x) = log x,
то
log C^z = 0.
Следовательно
C^z = 1.
Отсюда при условии что C и z — натуральные числа, следует, что C = z = 1.
rafuck
04.10.2018 03:00ну, да, с этой стороны тоже можно. Пусть ответит вот на этот вопрос:
habr.com/post/425239/#comment_19189453
Deosis
04.10.2018 09:15Что противоречит исходным данным. Дальше доказательство можно не рассматривать.
Sdima1357
04.10.2018 01:06Автору.
Смело берите ссуду под этот миллион. Хватит и на платное обучение и на квартиру рядом с универом.
Редактору.
Когда уже перестанут принимать на Хабре домашние доказательства теоремы Ферма, опровергателей Эйнштейна и разработки вечных двигателей, раздражает…Sirion
04.10.2018 01:08+1У меня есть подозрение, что такие вещи принимаются специально на потеху публике. Если это не так, это стоило бы сделать так.
rafuck
04.10.2018 01:08+2Зря вы так. Хорошая статья. Я узнал про забавную теорему из теории чисел.
staticlab
04.10.2018 12:34+1Кстати из этой гипотезы прямо следует Великая теорема Ферма. Простое доказательство есть в Википедии. То есть можно считать, что автор предлагает нам своё доказательство ВТФ, при этом во много раз более простое, чем доказательство Уайлса, несмотря на то, что считается, что доказательство ВТФ в принципе нельзя сделать существенно проще, чем оно есть сейчас.
rafuck
04.10.2018 13:07+1Тут вот какое дело. На мой взгляд, ошибка в рассуждениях видна сразу. Но. Если автор — молодой человек, то такие исследования должны только поощряться, как мне кажется.
staticlab
04.10.2018 13:16+1Поощрять попытки молодого математика доказать сложнейшие математически проблемы инструментами школьной математики? Есть риск вырастить ферматиста, вам не кажется?
rafuck
04.10.2018 13:35Да, но вместе с тем, есть риск получить образованного человека.
Sirion
04.10.2018 13:44Риск минимален, подход «не буду учить этот ваш матан, лучше попробую школьными методами, авось повезёт» надёжно от такого защищает.
rafuck
04.10.2018 13:56Ну, озвученный вами образ мышления, — это лишь домыслы, не так ли?
Sirion
04.10.2018 13:59+1Математика — прекрасная и очень красивая наука с множеством областей, теорий и ответвлений. Однако есть в ней особая, «чистая» область, этакая математика в квадрате, под названием высшая арифметика. А уже там прячется основа основ всей математики, её священный Грааль — элементарная теория чисел, изучающая без использования методов других разделов математики такие вопросы как делимость целых чисел, проблема факторизации, диофантовы уравнения и многое другое.
Перевод на русский: я не хочу знать методы современной теории чисел, я хочу решать открытые проблемы, как олимпиадные задачки для девятого класса.mihaild
04.10.2018 14:21Ой, я это пропустил. Почему мне раньше про это не сказали, и на экзамене по ТЧ заставляли про какие-то вычеты говорить?(
Sirion
04.10.2018 16:16Вычеты… Я не так давно на барахолке видел книжку «Аналитическая теория чисел». Я заглянул в неё и у меня встали дыбом волосы, в том числе и на голове. А ведь эта книжка старше меня. Как выглядит действительно современная ТЧ, я даже представить боюсь. Но она однозначно очень далека от милых детских игр с
пиписькойвычетами.mihaild
04.10.2018 16:27Скорее всего там много чего страшного. Но вот глянул на предмет обозначений несколько случайных из последних статей по ТЧ с архива — обычные интегралы по контуру, преобразование Фурье, дифф. формы, группы Галуа — ничего сверх-ужасного. Т.е. и относительно простыми методами всё еще что-то делают.
rafuck
04.10.2018 14:27Однако оказывается, что теория чисел и, например, топология каким-то образом связаны. То есть священный Грааль, кажется, все же может использовать дугие разделы математики.
mihaild
04.10.2018 14:26+1Тут не «ошибка в рассуждениях» — ошибки бывают даже у очень серьезных математиков. У того же Уайлса, например:)
Тут ошибка в том, что за доказательство выдается текст, не похожий на доказательство чисто синтаксически. Довольно распространенная проблема — попытка переноса каких-то свойств одной категории на другую, без описания, как это делается (и как правило с требованиями, с которыми это сделать вообще невозможно). Можно научить так не делать, но для этого нужно, чтобы автор был готов слушать.rafuck
04.10.2018 14:30А почему мы все думаем, что автор не готов слушать?
mihaild
04.10.2018 14:35Потому что на просьбу дать определения он говорит «подождите», и продолжает рассуждать о неопределенных понятиях.
Ну и вообще случаи, когда людям, пытающимся на пальцах с использованием мутной терминологии решить сложные проблемы, в итоге удавалось объяснить, что так делать не надо, конечно известны, но крайне редки.
Refridgerator
04.10.2018 05:55Автору не хватило терпения. Нужно было сначала получить миллион, а потом уже говорить «доказано». Неужели история с доказательством теоремы Ферма Эндрю Уальсом ничему не научила?
спойлерВ первой версии доказательства, которое Уальс торжественно представил публике, оказался недочёт, который удалось устранить только через некоторое время при помощи ещё одного математика.Refridgerator
04.10.2018 10:01В тегах фигурирует «теорема Нечаева», но в статье нет ни ссылки, ни формулировки её в явном виде. В чём она заключается?
staticlab
04.10.2018 11:14+1Автор, считая, что доказал гипотезу Била, решил назвать её своим именем. То есть не теорема Била, а теорема Нечаева.
Вероятно, после того, как он "докажет" гипотезу Коллатца, у нас будут Первая и Вторая теоремы Нечаева.
rafuck
04.10.2018 13:10Если быть до конца буквоедом, то гипотеза и теорема — существенно разные вещи. И БТФ должна была называться Большой Гипотезой Ферма, а вот ее доказательство — это уже теорема.
staticlab
04.10.2018 13:20Само собой. Теоремой её называли исторически, полагая, что Ферма всё-таки доказал её.
Касательно "теоремы Нечаева", кажется, есть аналогия с историей гипотезы Каталана, на которую также ссылается автор: "В 2002 году математик румынского происхождения Преда Михалеску… доказал эту гипотезу. С тех пор доказанную гипотезу Каталана стали также называть Теорема Михалеску."
usrsse2
Формулы не отображаются
aamonster
Вы часом не с мобильного браузера смотрите? На них в принципе не показывает формулы на хабре, надо переключиться в показ десктопного сайта.
usrsse2
Нет, десктопный Safari 12.
aamonster
Проверил, у меня тоже воспроизводится (в хроме нормально). Надо будет посмотреть, куда репортить баги по движку хабра.
UPD: зарепортил в «обратную связь» на сайте.
JC_IIB
Safari Version 11
Формул нет.