01.10.2015 | Наука

Австралиец поборол компьютер в решении проблемы несоответствия Эрдёша

В 1930-х годах венгерский математик Пал Эрдёш (Pál Erdős) интересовался свойствами бесконечной последовательности из чисел -1 и 1.

Фото John D., Catherine T. MacArthur Foundation/Wikimedia Commons

Его исследования были призваны выяснить, будет ли такая последовательность всегда содержать шаблоны и некую структуру внутри случайности.

Одним из способов измерения стало вычисление величины, известной как несоответствие или расхождение (сумма конечного числа элементов). Она подразумевает суммирование всех -1 и 1 в каждой из возможных подпоследовательностей. Казалось бы, при суммировании (пусть и почти бесконечном) 1 и -1 должны давать нуль. Но Эрдёш утверждал, что по мере того, как исследуемая подпоследовательность будет становиться длиннее, сумма или несоответствие будет расти, выдавая тем самым неоспоримую структуру подпоследовательности чисел. Однако учёный так и не доказал свою точку зрения, умерев в 1996 году. Но математики долгое время пытались найти этому доказательство.

В 2014 году учёные российского происхождения Алексей Лисица и Борис Конев, сотрудники Ливерпульского университета в Великобритании, использовали компьютер, чтобы доказать, что расхождение всегда будет больше 2. Компьютер "трудился" над задачей шесть часов, и в результате выдал гигантский файл доказательства (выводы приведены в препринте статьи на сайте arXiv.org). Он получился огромным: объём файла составил 13 гигабайт, что больше, чем весь текстовый архив сайта "Википедия". Математики предположили, что ни один человек в мире не сможет его перепроверить.

Математик Теренс Тао (Terence Tao), австралиец, работающий в Калифорнийском университете в Лос-Анджелесе, пошёл более стандартным путём и попытался доказать, что Эрдёш был прав, считая, что расхождение является бесконечным вне зависимости от выбранной последовательности. Он сделал это путём соединения недавних результатов в теории чисел с данными, полученными в проекте Polymath5.

Группа математиков, включавшая Тао, начала работать над проектом в 2010 году. Проект Polymath5 должен был объединить профессионалов и любителей, желающих привнести новые идеи в решение сложных математических задач. В результате такого сотрудничества был создан своего рода математический супермозг. Однако в итоге проект был закрыт, несмотря на определённый прогресс учёных.

"Мы свели задачу о несоответствии Эрдёша к, казалось бы, более простой задаче со специального типа последовательностью под названием полностью мультипликативная функция", – рассказывает Тао.

В январе 2015 года комментарий в его блоге заставил учёного задуматься о том, чтобы использовать данные проекта Polymath для решения проблемы.

"Сначала я думал, что сходство было лишь поверхностным, — признаётся Тао. – Но, обдумав идею тщательнее и пересмотрев некоторые предыдущие предварительные результаты Polymath5, я понял: если можно было полностью доказать гипотезу Эллиотта- Халберстама, то почему бы не попробовать таким же образом решить проблему несоответствия Эрдёша".

Работа Теренса была опубликована на сайте препринтов arxiv.org. Сейчас его решение изучают коллеги, если оно будет признано верным, то статья Тао появится в открытом доступе в журнале Discrete Analysis.

Вряд ли у нынешнего достижения будет практическое применение, однако результат подчёркивает различия между двумя современными подходами к математике: краудсорсингу и компьютерным алгоритмам. В данном случае математик и окружавшие его люди смогли справиться с задачей лучше куда более производительных машин.

По публикациям UkrNet