Max Home IndustryЧто вы делаете после решения ответа на вопрос о жизни, вселенной и всем остальном? Если вы математики Дрю Сазерленд и Энди Букер, вы решите более сложную задачу.
В 2019 году Букер из Бристольского университета и Сазерленд, главный научный сотрудник Массачусетского технологического института, первыми нашли ответ на 42. Это число имеет значение для поп-культуры как вымышленный ответ на «главный вопрос жизни — вселенную. и все такое », как классно написал Дуглас Адамс в своем романе« Автостопом по Галактике ». Вопрос, который порождает 42, по крайней мере, в романе, удручающе, до смешного неизвестен.
В математике, совершенно случайно, существует полиномиальное уравнение, ответ для которого, 42, точно так же ускользнул от математиков на протяжении десятилетий. Уравнение x 3 + y 3 + z 3 = k известно как задача суммы кубов. Несмотря на кажущуюся простоту, уравнение становится экспоненциально сложным для решения, если его оформить как «диофантово уравнение» — проблема, которая требует, чтобы для любого значения k значения x, y и z каждое должны быть целыми числами.
Когда уравнение суммы кубов оформлено таким образом, для определенных значений k целочисленные решения для x, y и z могут вырасти до огромных чисел. Числовое пространство, в котором математики должны искать эти числа, еще больше, что требует сложных и массивных вычислений.
На протяжении многих лет математикам приходилось решать уравнение различными способами, либо находя решение, либо определяя, что решение не должно существовать для каждого значения k от 1 до 100, за исключением 42.
В сентябре 2019 года Букер и Сазерленд, используя совокупную мощность полумиллиона домашних компьютеров по всему миру, впервые нашли решение для 42. Широко известный прорыв побудил команду к решению еще более сложной, а в некоторой степени и более сложной задачи. универсальная проблема: найти следующее решение для 3.
Букер и Сазерленд опубликовали решения для 42 и 3, а также несколько других чисел, превышающих 100, на этой неделе в Proceedings of the National Academy of Sciences .
Поднимая перчатку
Первые два решения уравнения x 3 + y 3 + z 3 = 3 могут быть очевидны для любого школьника, изучающего алгебру, где x, y и z могут быть либо 1, 1 и 1, либо 4, 4 и -5. Однако поиск третьего решения на протяжении десятилетий ставил в тупик опытных теоретиков чисел, и в 1953 году эта загадка побудила математика-новатора Луиса Морделла задать вопрос: возможно ли вообще узнать, существуют ли другие решения для 3?
«Это было похоже на то, как Морделл бросил вызов», — говорит Сазерленд. «Интерес к решению этого вопроса не столько для конкретного решения, сколько для лучшего понимания того, насколько сложно решить эти уравнения. Это эталон, по которому мы можем измерить себя».
Шли десятилетия, а для 3 новых решений не было, и многие начали верить, что их не найти. Но вскоре после того, как был найден ответ на 42, метод Букера и Сазерленда за удивительно короткое время нашел следующее решение для 3:
569936821221962380720 3 + (-569936821113563493509) 3 + (-472715493453327032) 3 = 3
Это открытие явилось прямым ответом на вопрос Морделла: да, можно найти следующее решение для 3, и, более того, вот это решение. И, возможно, более универсально, решение, включающее гигантские 21-значные числа, которые до сих пор было невозможно отсеять, предполагает, что существует больше решений для 3 и других значений k.
«В математическом и вычислительном сообществах возникли серьезные сомнения, потому что [вопрос Морделла] очень трудно проверить», — говорит Сазерленд. «Цифры так быстро становятся такими большими. Вы никогда не найдете больше, чем несколько первых решений. Но что я могу сказать, так это то, что, найдя это единственное решение, я убежден, что их бесконечно много».
Изюминка решения
Чтобы найти решения для 42 и 3, команда начала с существующего алгоритма или преобразования уравнения суммы кубов в форму, которую, по их мнению, было бы легче решить:
k — z 3 = x 3 + y 3 = ( x + y ) ( x 2 — xy + y 2 )
Этот подход был впервые предложен математиком Роджером Хит-Брауном, который предположил, что для каждого подходящего k должно быть бесконечно много решений. Команда дополнительно изменила алгоритм, представив x + y как единственный параметр d. Затем они сократили уравнение, разделив обе части на d и сохранив только остаток — математическая операция, называемая «по модулю d», — оставив упрощенное представление проблемы.
«Теперь вы можете думать о k как о кубическом корне из z по модулю d», — объясняет Сазерленд. «Итак, представьте себе работу в системе арифметики, в которой вас интересует только остаток по модулю d, а мы пытаемся вычислить кубический корень из k».
С этой более изящной версией уравнения исследователям нужно было бы только искать значения d и z, которые гарантировали бы нахождение окончательных решений для x, y и z при k = 3. Но все же пространство чисел, которое им пришлось бы перебирать, было бы бесконечно большим.
Итак, исследователи оптимизировали алгоритм, используя математические методы «просеивания», чтобы резко сократить пространство возможных решений для d.
«Это включает в себя довольно продвинутую теорию чисел, использующую структуру того, что мы знаем о числовых полях, чтобы не заглядывать туда, куда нам не нужно смотреть», — говорит Сазерленд.
Глобальная задача
Команда также разработала способы эффективного разделения поиска алгоритма на сотни тысяч потоков параллельной обработки. Если бы алгоритм запускался только на одном компьютере, на поиск решения k = 3 потребовались бы сотни лет. Разделив задание на миллионы более мелких задач, каждая из которых независимо запускается на отдельном компьютере, команда может еще больше ускорить поиск.
В сентябре 2019 года исследователи воплотили свой план в жизнь с помощью Charity Engine — проекта, который можно загрузить как бесплатное приложение на любой персональный компьютер и который предназначен для использования любых свободных домашних вычислительных мощностей для коллективного решения сложных математических задач. В то время сеть Charity Engine включала более 400 000 компьютеров по всему миру, и Букер и Сазерленд смогли запустить свой алгоритм в сети в качестве теста новой программной платформы Charity Engine.
«Им говорят, что для каждого компьютера в сети ваша задача — искать d, простой фактор которых попадает в этот диапазон, при некоторых других условиях», — говорит Сазерленд. «И нам нужно было выяснить, как разделить задание примерно на 4 миллиона задач, на выполнение каждой из которых у компьютера уйдет около трех часов».
Очень быстро глобальная сетка вернула самое первое решение для k = 42, и всего через две недели исследователи подтвердили, что нашли третье решение для k = 3 — веху, которую они отметили, частично, распечатав уравнение на футболках.
Тот факт, что существует третье решение для k = 3, предполагает, что исходная гипотеза Хита-Брауна была верной и что существует бесконечно больше решений, помимо этого новейшего. Хит-Браун также предсказывает, что расстояние между решениями будет экспоненциально расти вместе с их поисками. Например, вместо 21-значных значений третьего решения четвертое решение для x, y и z, скорее всего, будет включать числа с ошеломляющими 28 цифрами.
«Объем работы, которую вы должны выполнить для каждого нового решения, увеличивается более чем в 10 миллионов раз, поэтому для следующего решения для 3 потребуется 10 миллионов раз 400 000 компьютеров, и нет никакой гарантии, что этого достаточно», — говорит Сазерленд. . «Я не знаю, узнаем ли мы когда-нибудь четвертое решение. Но я верю, что оно существует».
Это исследование было частично поддержано Фондом Саймонса.