Британские математики Эндрю Букер (Andrew R. Booker) и Эндрю Сазерленд (Andrew V. Sutherland) нашли новый способ разложить число 3 в сумму трех кубов целых чисел. Два тривиальных решения были известны давно: 3 = 13+13+13 = 43+43+(-5)3. Обновленный алгоритм поиска решений диофантовых уравнений позволили найти третье решение. Новый алгоритм и решения уравнения x3+y3+z3 = k для k=3, 42, 165, 579, 906 опубликованы в журнале Proceedings of the National Academy of Sciences.
Диофантовы уравнения — это полиномиальные уравнения, например, 5x+3y = 1, или x2-3y2=1, решения которых ищут среди целых чисел. Они интересны тем, что их очень просто сформулировать, но очень сложно решить. Классический пример таких уравнений — Великая теорема Ферма, xn+yn = zn для n больше двух. Чтобы доказать, что это уравнение не имеет решение в целых x, y, z потребовалось больше 350 лет.
Десятая из 23 проблем Гильберта, самых важных задач математики, сформулированных в 1900 году, звучит так: «Как за конечное число операций узнать, есть ли у диофантова уравнения решения или нет?» В 1970 году Юрий Матиясевич показал, что универсального алгоритма, который определял бы наличие решений произвольного диофантова уравнения, не существует. Тем более не существует универсального алгоритма решения диофантовых уравнений. Задача о разложении произвольных натуральных чисел в сумму кубов целых чисел — одна из тех задач, в которых неизвестно не только ее решение, но и сама возможность разложить некоторые из чисел.
Некоторые натуральные числа, например, k = 29, разложить в сумму кубов очень просто: 33+13+13 = 29. Уже для k=30 решение достигается лишь при x = 3 982 933 876 681, y = -636 600 549 515 и z = -3 977 505 554 546, а для k=31 и 32 решения и вовсе нет, как и для всех k дающих в остатке 4 или 5 при делении на 9. Это связано с тем, что кубы целых чисел могут давать в остатке при делении на 9 только 0, 1 и 8. Разложение для k=33 удалось найти Эндрю Букеру лишь в 2019 году, и оно выглядит так:
33 = 8 866 128 975 287 5283 + (−8 778 405 442 862 239)3 + (−2 736 111 468 807 040)3
В 1992 году Роджер Хит-Браун предположил, что для каждого натурального числа (кроме дающих в остатке 4 и 5 при делении на 9) есть бесконечно много разложений на кубы целых чисел. Также Хит-Браун указал на то, что эти разложения будут очень сильно отличаться по величине x, y и z. Например, две соседние тройки x,y,z для данного k могут различаться примерно в 100 миллионов раз. Интересным было найти несколько разложений на кубы для одного числа и сравнить их между собой, например, найти еще одно разложение для x3+y3+z3 = 3.
Поиск разложения k=x3+y3+z3 сводится к умному перебору x, y, z для каждого k. Математики увеличили скорость перебора возможных x, y, z немного видоизменив исходное уравнение:
(x + y)(x2 – xy + y2) = k — z3
А также воспользовавшись теорией чисел для того, чтобы сократить пространство перебираемых значений (x+y) для заданных k и z. Подробное описание алгоритма и исходный код можно найти в статье. Разбив перебор вариантов на большое количество параллельных потоков, математики смогли найти новое решение для k=3:
3 = 569 936 821 221 962 380 7203 + (−569 936 821 113 563 493 509)3 + (−472 715 493 453 327 032)3
Авторы обращают внимание на то, что тройка x, y, z несколько «перекошена» — первые два числа по модулю примерно в тысячу раз больше, чем последнее. Чтобы найти это решение, математики воспользовались вычислительной сетью Charity Engine, состоящей из полумиллиона компьютеров добровольцев. По оценкам Эндрю Букера, для того чтобы найти следующее разложение тройки в сумму трех кубов за разумное время, может потребоваться в сто миллионов раз большее количество устройств — из-за того, что тройки x, y, z встречаются так редко. «Я не знаю, найдем ли мы когда-нибудь четвертое разложение. Но я верю, что оно где-то там» — прокомментировал Сазерленд результаты исследования для MIT News. Также авторы нашли решения для k = 42, 165, 579 и 906. О результате для k=42 стало известно в сентябре 2019 года.
42 = (−80,538,738,812,075,974)3+80,435,758,145,817,5153+12,602,123,297,335,6313
165 = (−385,495,523,231,271,884)3+383,344,975,542,639,4453+98,422,560,467,622,8143
579 = 143,075,750,505,019,222,6453+(−143,070,303,858,622,169,975)3+(−6,941,531,883,806,363,291)3
906 = (−74,924,259,395,610,397)3+72,054,089,679,353,3783+35,961,979,615,356,5033
Среди натуральных чисел до 1000 остаются «непокоренными» лишь семь: 114, 390, 627, 633, 732, 921 и 975.
