Булева проблема пифагоровых троек

Булева проблема пифагоровых троек — одна из задач теорииРамсея.

Формулировка


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

Замечание


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

История


 В 2015 году Джошуа Купер и Ральф Оверстрит раскрасили двумя цветами 7664натуральных чисел так, что все пифагоровы тройки были разноцветными.
 Марин Гейле, Оливер Кульман и Виктор Марек в мае 2016 года решилизадачу. Они доказали, что множество натуральных чисел \{1,\ldots,7824\} можно поделить так, чтобы каждая часть не имела ни однойпифагоровой тройки, но это невозможно для \{1,\ldots, 7825\}.
 Теорема была доказана путём перебора всех вариантов с использованием 800ядер суперкомпьютера Stampede в в течение двух дней. Размер файла сдоказательством в формате DRAT достиг 200 терабайт. Из него былизготовлен и помещён в архив сертификат размером 68 гигабайт. Для 7824натуральных чисел существует несколько решений проблемы, но для 7825решений не найдено.
 Статья Марин Гейле, Оливера Кульмана и Виктора Марека была выбрана длядоклада на конференции SAT 2016, которая состоялась в Бордо (Франция) виюле 2016 года, и была признана лучшей работой.