Математические трюки для укрощения средней дистанции | Журнал Кванта

В этом году, Quanta зафиксировал три основных достижения в теории Рамсея, изучение того, как избежать создания математических моделей. первый результат установите новый предел того, насколько большим может быть набор целых чисел, не содержащий трех чисел, расположенных через равные промежутки, например {2, 4, 6} или {21, 31, 41}. второй и в третьих аналогичным образом установите новые ограничения на размер сетей без кластеров точек, которые либо все связаны, либо все изолированы друг от друга.

Доказательства касаются того, что происходит, когда задействованные числа становятся бесконечно большими. Как это ни парадоксально, иногда это может быть проще, чем иметь дело с надоедливыми реальными величинами.

Например, рассмотрим два вопроса о дроби с действительно большим знаменателем. Вы можете спросить, каково десятичное расширение, скажем, 1/42503312127361. Или вы можете спросить, будет ли это число приближаться к нулю по мере роста знаменателя. Первый вопрос — это конкретный вопрос о реальной величине, и его труднее рассчитать, чем второй, который спрашивает, как величина 1/n будет «асимптотически» изменяться как n растет. (Все ближе и ближе к 0.)

«Эта проблема преследует всю теорию Рэмси, — сказал Уильям Газарк, ученый-компьютерщик из Мэрилендского университета. «Теория Рамси известна тем, что дает асимптотически очень хорошие результаты». Но анализ чисел, меньших бесконечности, требует совершенно другого математического инструментария.

Гасарч изучал вопросы теории Рамсея, связанные с конечными числами, которые слишком велики для решения задачи методом грубой силы. В одном проекте он использовал конечную версию первого прорыва этого года — февральскую статью Зандер Келли, аспирант Иллинойского университета в Урбане-Шампейне и Рагху Мека из Калифорнийского университета в Лос-Анджелесе. Келли и Мека нашли новую верхнюю границу количества целых чисел от 1 до N вы можете поместить в набор, избегая при этом трехчленных последовательностей или шаблонов из равномерно расположенных чисел.

Хотя результат Келли и Меки применим, даже если N относительно невелика, в этом случае она не дает особенно полезной оценки. Для очень малых значений N, вам лучше придерживаться очень простых методов. Если N равно, скажем, 5, просто посмотрите на все возможные наборы чисел от 1 до N, и выберите самый большой вариант без прогрессии: {1, 2, 4, 5}.

Но количество различных возможных ответов растет очень быстро и делает применение такой простой стратегии слишком сложным. Существует более 1 миллиона наборов, состоящих из чисел от 1 до 20. Более 10⁶⁰ с использованием чисел от 1 до 200. Поиск наилучшего набора без прогрессии для этих случаев требует огромной вычислительной мощности, даже при использовании стратегий повышения эффективности. «Вы должны быть в состоянии выжать из вещей много производительности», — сказал Джеймс Гленн, ученый-компьютерщик из Йельского университета. В 2008 году Гасарх, Гленн и Клайд Краскал Университета Мэриленда написал программу чтобы найти самые большие наборы без прогрессии до N из 187. (В предыдущей работе были ответы до 150, а также до 157.) Несмотря на список трюков, их программа заняла месяцы, сказал Гленн.

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

Гасарч, Гленн и Крускал также попробовали несколько других стратегий. Одна многообещающая идея опиралась на случайность. Простой способ получить набор без прогрессии — это поставить 1 в свой набор, а затем всегда добавлять следующее число, которое не создает арифметическую прогрессию. Следуйте этой процедуре, пока не нажмете число 10, и вы получите набор {1, 2, 4, 5, 10}. Но оказывается, это не лучшая стратегия в целом. «Что, если мы не начнем с 1?» — сказал Газарх. «Если вы начнете в случайном месте, вы на самом деле добьетесь большего успеха». Он добавил, что исследователи понятия не имеют, почему случайность так полезна.

Вычисление конечных версий двух других результатов новой теории Рамсея еще более досадно, чем определение размера множеств без прогрессии. Эти результаты касаются математических сетей (называемых графами), состоящих из узлов, соединенных линиями, называемыми ребрами. Число Рэмси r(s, t) — наименьшее количество узлов, которое должен иметь граф, прежде чем станет невозможным избежать включения группы s соединенные узлы или t отключенные. Вычисление числа Рамсея представляет собой такую ​​головную боль, что даже r(5, 5) неизвестно — это где-то между 43 и 48.

В 1981 Брендан Маккей, ныне работающий информатиком в Австралийском национальном университете, написал программу под названием nauty, предназначенную для упрощения вычисления чисел Рамсея. Nauty гарантирует, что исследователи не будут тратить время на проверку двух графиков, которые являются просто перевернутыми или повернутыми версиями друг друга. «Если кто-то находится поблизости и не использует nauty, игра окончена. Вы должны использовать его, — сказал Станислав Радзишовский, математик из Рочестерского технологического института. Тем не менее, количество необходимых вычислений почти непостижимо. В 2013 году Радзишовский и Ян Геджебер доказали, что r(3, 10) не больше 42. «На это ушло, по-моему, почти 50 лет процессорного времени», — сказал Геджебер, ученый-компьютерщик из KU Leuven University в Бельгии.

Если вы не можете вычислить точное число Рамсея, попробуйте сузить его значение с помощью примеров. Если бы вы нашли граф с 45 узлами без пяти связанных узлов и без пяти узлов, которые все были разъединены, это доказывало бы, что r(5, 5) больше 45. Математики, изучающие числа Рамсея, раньше думали, что найти эти примеры, называемые графами Рамсея, будет просто, сказал Радзишовский. Но это было не так. «Было ожидание, что красивые, крутые математические построения дадут наилучшие возможные построения, и нам просто нужно больше людей, чтобы над этим работать», — сказал он. «Мне все больше и больше кажется, что это хаотично».

Случайность является одновременно и препятствием для понимания, и полезным инструментом. Джеффри Эксу, ученый-компьютерщик из Университета штата Индиана, потратил годы на усовершенствование случайных методов для создания графов Рэмси. В бумага 2015 анонсировав десятки новых рекордных графов Рэмси, Exoo и Милош Татаревич генерировали случайные графы, а затем постепенно корректировали их, удаляя или добавляя ребра, что уменьшало количество нежелательных кластеров, пока они не нашли граф Рэмси. Тем не менее, методы Exoo — это искусство, как и все остальное, — сказал Радзишовски. Иногда они требуют, чтобы он комбинировал несколько методов или использовал суждение о том, с какого типа графиков начать. «Многие люди пытаются это сделать, но не могут», — сказал Радзишовский.

Методы, разработанные для построения графов Рамсея, когда-нибудь могут найти более широкое применение, сказал Геджебер, который работал над создание других видов графиков, таких как графики, представляющие химические соединения. «Вполне вероятно, что эти методы также могут быть перенесены и скорректированы, чтобы помочь более эффективно генерировать другие классы графиков (и наоборот)», — написал он в электронном письме.

Однако для Радзишовского причина изучения малых чисел Рамсея гораздо проще. «Потому что он открыт, потому что никто не знает ответа», — сказал он. «Тривиальные дела мы делаем вручную; чуть больше, нужен компьютер, а чуть больше, даже компьютер не годится. Так и возникает вызов».