Приветствую Вас, уважаемые Читатели! 3 мая 2016 года, в Arxiv.org было представлено самое большое математическое «доказательство» (или, точнее, проверка), занимающее 200 терабайт.
Математики из Университета Техаса в Остине с помощью компьютерных методов решили задачу о булевых пифагоровых тройках. На решение задачи ушло два дня непрерывной работы 800-процессорного суперкомпьютера. Размер предыдущего рекордного доказательства был «всего» в 14 гигабайт.
Формулировка задачи
Существуют тройки натуральных чисел, называемые пифагоровыми, они устроены так, что сумма квадратов двух из них в точности равна квадрату третьего. Можно ли поделить все натуральные числа на две группы таким образом, чтобы ни в одной из них по отдельности не нашлось ни одной пифагоровой тройки?
Эта задача - классическая проблема теории Рамсея - раздела комбинаторики, изучающего условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. Задачи в теории Рамсея обычно звучат в форме вопроса «сколько элементов должно быть в некотором объекте, чтобы гарантированно выполнялось заданное условие или существовала заданная структура». Простейший пример: доказать, что в любой группе из 6 человек найдутся либо 3 человека, знакомые друг с другом, либо 3 человека, попарно незнакомые друг с другом.
Иными словами, задача предлагает разделить все числа на «красные» и «синие» таким образом, чтобы ни одна из троек не оказалась одноцветной. К примеру, для классической тройки 3^2+4^2=5^2, если 3 и 4, к примеру, «синие», то 5 точно должна быть «красной». Одна из сложностей состоит в том, что количество пифагоровых троек бесконечно велико, причем одно и то же число может входить в разные тройки.
В случае, если это невозможно, математикам необходимо предоставить контрпример — набор натуральных чисел от 1 до N, который так гарантированно нельзя раскрасить.
За решение этой задачи Рональд Грэм, математик из Университета Калифорнии, в шутку пообещал вручить приз в 100 долларов.
Фактическое утверждение доказанной теоремы:
Множество {1, . . . , 7824} может быть разделено на две части таким образом, чтобы ни одна часть не содержала тройки Пифагора, в то время как это невозможно для {1, . . . , 7825}.
Для того, чтобы доказать этот факт, в простейшем случае потребовалось бы перебрать огромное число вариантов — 2^7825. Это число по меньшей мере с 2350 нулями. По сути "методом грубой силы" нужно предъявить все возможные разбиения множества чисел от 1 до N на две части и попытаться раскрасить их в два цвета.
Воспользовавшись некоторыми наблюдениями, симметриями и приемами теории чисел, авторам удалось сократить перебор до триллиона вариантов.
В кратце о доказательстве: каждое разбиение пифагоровых троек исследователи сводили к некоторой булевой формуле (использовали конъюктивную нормальную форму):
Затем распараллеливали задачу, разбивали её на составные части и находили истинность этих формул. Истина означала возможность раскраски множества в два цвета, как это требовалось в задаче. Для одной из формул в наборе {1...7825} это сделать не получилось.
Несмотря на то, что ответ на задачу найден, компьютерное решение не отвечает на вопрос «почему». В препринте, описывающем доказательство, авторы замечают, что 7825 — «гипотенуза» сразу в двух тройках. При попытках раскрасить натуральные числа от 1 до 7824, числа 5865 и 5180, входящие в одну тройку, оказывались другого цвета, чем числа 625 и 7800, входящие в другую.
В аннотации к своей публикации авторы в шутку упоминают о гонораре, предложенном Рональдом Грэмом несколько десятков лет назад!
Куллманн указывает, что их доказательство — которое не является доказательством в классическом смысле этого термина в математике — не объясняет, что происходит, начиная с 7825, и не может сказать нам, имеет ли это конкретное число какое-либо особое значение. Таким образом, призовые деньги (как написано в статье) не могут быть востребованы!
Так что не исключено, что в ближайшее время появится чисто математическое доказательство, решающее задачу, и приз в 100 долларов будет выплачен.
- Спасибо за внимание!
