Математики предсказали, что если они наложат достаточно ограничений на то, как форма может распределять пространство, они смогут заставить возникать периодический паттерн. Но они были неправы.
Одна из старейших и простейших задач в геометрии застала математиков врасплох — и не в первый раз.
С древности художники и геометры задавались вопросом, как формы могут покрывать всю плоскость плиткой без зазоров или перекрытий. И все же “до недавнего времени было известно не так уж много”, — сказал Алекс Иосевич, математик из Университета Рочестера.
Наиболее очевидные варианты укладки повторяются: пол легко покрыть копиями квадратов, треугольников или шестиугольников. В 1960-х годах математики обнаружили странные наборы плиток, которые могут полностью покрывать плоскость, но только такими способами, которые никогда не повторяются.
“Вы хотите понять структуру таких плиток”, — сказала Рэйчел Гринфельд, математик из Института перспективных исследований в Принстоне, штат Нью-Джерси. “Насколько сумасшедшими они могут стать?”
Оказывается, это довольно безумно.
Первый такой неповторяющийся, или апериодический, узор основывался на наборе из 20 426 различных плиток. Математики хотели знать, смогут ли они уменьшить это число. К середине 1970-х годов Роджер Пенроуз (который впоследствии получит Нобелевскую премию по физике 2020 года за работу над черными дырами) доказал, что достаточно простого набора всего из двух плиток, получивших название “воздушные змеи” и “дротики”.
Нетрудно придумать шаблоны, которые не повторяются. Многие повторяющиеся или периодические укладки можно настроить так, чтобы они не повторялись. Рассмотрим, скажем, бесконечную сетку квадратов, выровненных наподобие шахматной доски. Если вы сдвинете каждую строку так, чтобы она была смещена на величину, отличную от той, что находится над ней, вы никогда не сможете найти область, которую можно вырезать и вставить как штамп, чтобы воссоздать полную плитку.
Настоящая хитрость заключается в том, чтобы найти наборы плиток — как у Пенроуза, — которые могут покрывать всю плоскость, но только таким образом, чтобы они не повторялись.
Две плитки Пенроуза подняли вопрос: может ли существовать одна плитка искусной формы, которая соответствует всем требованиям?
Удивительно, но ответ оказывается утвердительным — если вам разрешено сдвигать, поворачивать и отражать плитку, и если плитка отсоединена, что означает, что в ней есть пробелы. Эти промежутки заполняются другими соответствующим образом повернутыми, соответствующим образом отраженными копиями плитки, в конечном счете покрывающими всю двумерную плоскость. Но если вам не разрешено поворачивать эту фигуру, невозможно выложить плоскость плиткой, не оставляя зазоров.
Действительно, несколько лет назад математик Сиддхартха Бхаттачарья доказал, что — независимо от того, насколько сложный или утонченный дизайн плитки вы придумали — если вы можете использовать только сдвиги или переводы одной плитки, то невозможно создать плитку, которая может покрывать всю плоскость апериодически, но не периодически.
Математики предположили, что двумерный результат Бхаттачарьи будет справедлив и в пространствах более высокой размерности. Точно так же, как не существует апериодической двумерной плитки, они предположили, что не существует подходящего трехмерного блока (или более сложной плитки), и так далее в сколь угодно большом количестве измерений.
Эта гипотеза была названа гипотезой периодического разбиения на плитки.
В препринте, опубликованном в прошлом месяце, Гринфельд вместе с Теренсом Тао из Калифорнийского университета в Лос—Анджелесе, наконец, разрешили гипотезу — но не так, как ожидали математики. Они сконструировали плитку, которая может апериодически заполнять пространство высокой размерности, но не может делать это периодически, тем самым опровергая гипотезу.
Две плитки Пенроуза подняли вопрос: может ли существовать одна плитка искусной формы, которая соответствует всем требованиям?
Удивительно, но ответ оказывается утвердительным — если вам разрешено сдвигать, поворачивать и отражать плитку, и если плитка отсоединена, что означает, что в ней есть пробелы. Эти промежутки заполняются другими соответствующим образом повернутыми, соответствующим образом отраженными копиями плитки, в конечном счете покрывающими всю двумерную плоскость. Но если вам не разрешено поворачивать эту фигуру, невозможно выложить плоскость плиткой, не оставляя зазоров.
Действительно, несколько лет назад математик Сиддхартха Бхаттачарья доказал, что — независимо от того, насколько сложный или утонченный дизайн плитки вы придумали — если вы можете использовать только сдвиги или переводы одной плитки, то невозможно создать плитку, которая может покрывать всю плоскость апериодически, но не периодически.
Математики предположили, что двумерный результат Бхаттачарьи будет справедлив и в пространствах более высокой размерности. Точно так же, как не существует апериодической двумерной плитки, они предположили, что не существует подходящего трехмерного блока (или более сложной плитки), и так далее в сколь угодно большом количестве измерений.
Эта гипотеза была названа гипотезой периодического разбиения на плитки.
В препринте, опубликованном в прошлом месяце, Гринфельд вместе с Теренсом Тао из Калифорнийского университета в Лос—Анджелесе, наконец, разрешили гипотезу — но не так, как ожидали математики. Они сконструировали плитку, которая может апериодически заполнять пространство высокой размерности, но не может делать это периодически, тем самым опровергая гипотезу.
Dan Komoda/Insitute for Advanced Study
“Это было неожиданностью. Я ожидал, что гипотеза окажется верной во всех измерениях”, — сказал Михалис Колунцакис, математик из Критского университета. “Но я думаю, что в достаточно высоких измерениях интуиция не заходит очень далеко”.
Странная плитка примечательна не только тем, что раздвигает границы того, что геометрически возможно, а что нет. Это также тесно связано с вопросами, выходящими за рамки геометрии, в том числе с вопросами о пределах самой логики.
Стержень
В 2019 году Гринфельд поступила в Калифорнийский университет в Лос—Анджелесе в качестве постдокторского исследователя, и она и Тао — оба независимо работали над другой проблемой, связанной с трансляционными разбиениями, — нацелились на доказательство гипотезы периодического разбиения на плитки.
Поскольку уже было известно, что гипотеза верна в одном и двух измерениях, они попытались доказать ее в трех: показать, что если вы можете перемещать копии одной фигуры, чтобы разбить на плитки все трехмерное пространство, то должен быть способ периодически разбивать пространство на плитки.
Они добились некоторого прогресса, повторно доказав гипотезу в двух измерениях, используя различные методы — те, которые, как они надеялись, будут применимы к трехмерному случаю. Но потом они наткнулись на стену. “В какой-то момент мы расстроились и сказали: «Хорошо, возможно, есть причина, по которой мы не можем доказать эту гипотезу в более высоких измерениях. Мы должны начать искать контрпримеры”, — сказал Тао.
Они прочесали литературу в поисках других апериодических конструкций, начиная с первой: набора из более чем 20 000 плиток, опубликованного в 1964 году, который мог охватывать плоскость с помощью переводов, но только апериодически. Затем они приступили к разработке новых методов построения одной апериодической плитки.
Они начали со смены обстановки. Допустим, вы хотите разбить на плитки двумерное пространство. Вместо того чтобы пытаться разбить непрерывную плоскость на плитки, рассмотрим двумерную решетку, бесконечный массив точек, расположенных в сетке. Теперь вы можете определить плитку как конечный набор точек на этой сетке; если у вас есть правильная плитка, то вы можете покрыть каждую точку решетки ровно один раз, сделав копии этого конечного набора точек и сдвинув их по кругу.
Доказательство гипотезы о “дискретном” периодическом разбиении на плитки для многомерных решеток — это несколько иная проблема, чем доказательство непрерывной версии гипотезы, поскольку существуют разбиения, которые возможны в решетках, но не в непрерывном пространстве. Но они связаны. Гринфельд и Тао планировали предложить дискретный контрпример к гипотезе, который затем они могли бы модифицировать, чтобы он работал и в непрерывном случае.
Летом 2021 года они подошли вплотную, обнаружив две плитки в очень многомерном пространстве. Плитки могут заполнять пространство, в котором они обитают, но только апериодически. “Этого недостаточно”, — сказал Гринфельд. “Два — это очень близко, но укладка двумя плитками гораздо менее жесткая, чем укладка одной плиткой”. Им потребовалось бы еще полтора года, чтобы собрать истинный контрпример к гипотезе периодического разбиения на плитки.
Сэндвич с плиткой
Они начали с создания нового языка, переписав свою задачу как особый вид уравнения. Неизвестная “переменная” в этом уравнении — то, что им нужно было решить, — представляла все возможные способы разметки пространства высокой размерности. “Но трудно описать вещи только одним уравнением”, — сказал Тао. “Иногда вам нужно несколько уравнений, чтобы описать действительно сложный набор в пространстве”.
Итак, Гринфельд и Тао переосмыслили вопрос, который они пытались решить. Они поняли, что вместо этого они могли бы разработать систему уравнений, где каждое уравнение кодировало бы различные ограничения на их решение. Это позволило им разбить свою проблему на вопрос о множестве различных плиток — в данном случае, плиток, которые покрывают заданное пространство, используя один и тот же набор переводов.
Например, в двух измерениях вы можете покрыть плоскость квадратом, перемещая его вверх, вниз, влево или вправо, по одной единице за раз. Но другие фигуры также могут укладывать плоскость плиткой, используя точно такой же набор сдвигов: например, квадрат с выступом, добавленным к правому краю и удаленным с левого края, как кусочек головоломки.
Если вы возьмете квадрат, кусочек головоломки и другие плитки, которые используют один и тот же набор перемещений, а затем сложите их вместе, как мясные нарезки в сэндвиче, вы можете создать одну плитку, которая использует один набор перемещений для покрытия трехмерного пространства. Гринфельду и Тао нужно было бы сделать это во многих других измерениях.
“Поскольку мы все равно работали в больших измерениях, добавление еще одного измерения на самом деле нам не повредило”, — сказал Тао. Скорее, это дало им дополнительную гибкость, необходимую для того, чтобы получить в свои руки хорошее решение.
Математики попытались обратить вспять эту процедуру построения сэндвича, переписав свою задачу с одним уравнением, состоящую из многомерных плиток, как серию плиточных уравнений в меньших измерениях. Эти уравнения позже будут определять, как будет выглядеть конструкция плитки более высокого размера.
Гринфельд и Тао рассматривали свою систему уравнений в виде плиток как компьютерную программу: каждая строка кода или уравнение — это команда, и в сочетании команды могут генерировать программу, которая достигает определенной цели. “Логические схемы состоят из очень простых объектов, таких как элементы ”И», «ИЛИ» и так далее, каждый из которых не очень интересен», — сказал Тао. “Но вы можете сложить их вместе, и вы можете создать схему, которая будет рисовать синусоидальную волну или общаться через Интернет”.
“Итак, мы начали рассматривать нашу проблему как своего рода проблему программирования”, — продолжил он. Каждая из их команд была бы другим свойством, которому должна была удовлетворять их окончательная укладка, так что программа в целом гарантировала бы, что любые укладки, соответствующие всем критериям, должны быть апериодическими.
Тогда вопрос заключался в том, какие свойства им нужно было закодировать во всех этих уравнениях разбиения на плитки, чтобы это произошло. Например, плитка в одном слое сэндвича может иметь такую форму, которая допускала бы только определенные виды движений. Математики должны были бы тщательно составить свой список ограничений — так, чтобы он не был настолько ограничительным, чтобы исключить какие-либо решения вообще, но был бы достаточно ограничительным, чтобы исключить все периодические решения.
“Игра здесь заключается в том, чтобы создать правильный уровень ограничений, — сказал Гринфельд, “ чтобы закодировать правильную головоломку”.
Бесконечное судоку
Головоломка, которую Гринфельд и Тао надеялись запрограммировать с помощью своих плиточных уравнений, представляла собой сетку с бесконечным числом строк и большим, но конечным числом столбцов. Математики стремились заполнить каждую строку и диагональ определенными последовательностями цифр, которые соответствовали бы видам ограничений, которые они могли бы описать с помощью плиточных уравнений: что-то, что они сравнивали с гигантской головоломкой судоку. Затем пара нашла последовательности, которые были апериодическими — это означает, что решение соответствующей системы уравнений с разбиением на плитки также было апериодическим. “В принципе, есть только одно решение этой головоломки, и это забавная вещь, которая почти, но не совсем периодична”, — сказал Тао. “Это заняло много времени, чтобы найти”.
“Такого рода вещи, когда вы изучаете функции, которые являются почти периодическими, но не совсем, — это то, что было в математике”, — сказала Изабелла Лаба, математик из Университета Британской Колумбии. “Но это совсем другой способ использования такого типа структуры”.
Как выразился Иосевич, Гринфельд и Тао “создали совершенно элементарный объект и подняли его до ситуации, когда все выглядит более сложным”.
При этом они построили апериодическую плитку высокой размерности — сначала в дискретной настройке, затем в непрерывной. Их плитка настолько сложна, так полна изгибов и отверстий, что на ней едва хватает места. “Это отвратительная плитка”, — сказал Тао. “Мы не предпринимали никаких попыток сделать эту плитку красивой”. Он и Гринфельд не вычисляли размерность пространства, в котором он живет; они просто знают, что он массивный, возможно, такой же большой, как [Ошибка математической обработки]. (Если бы вы попытались записать это число на страницах всех книг в мире, у вас бы закончилась бумага.) “Наше доказательство конструктивно, поэтому все является явным и вычислимым”, — сказал Гринфельд. “Но поскольку это очень, очень далеко от оптимального, мы просто не проверяли это”.
Действительно, математики думают, что они могут найти апериодические плитки в гораздо меньших измерениях. Это потому, что некоторые из более технических частей их конструкции включали работу в специальных пространствах, которые концептуально “очень близки к двумерным”, сказал Гринфельд. Она не думает, что они найдут трехмерную плитку, но она говорит, что возможно существование 4D-плитки.
И поэтому, по словам Иосевича, они не просто опровергли гипотезу о периодической укладке плитки: “Они сделали это самым унизительным из возможных способов”.
Набег на Незавершенность
Эта работа знаменует собой новый способ построения апериодических плиток — тот, который, по мнению Гринфельда и Тао, теперь может быть применен для опровержения других гипотез, связанных с плиточным покрытием. Это, в свою очередь, вероятно, позволит математикам еще больше расширить границы того, где может возникнуть сложность. “Похоже, действительно появляется такой принцип, что многомерная геометрия просто отвратительна”, — сказал Тао. “Что патологии могут проявляться, и что интуиция, которую мы получаем из двух и трех измерений, может вводить в заблуждение”.
Работа также затрагивает вопросы не только о границах человеческой интуиции, но и о границах математического мышления. В 1930-х годах математик Курт Гедель показал, что любая логическая система, достаточная для развития базовой арифметики, является неполной: существуют утверждения, которые не могут быть ни доказаны, ни опровергнуты в рамках этой системы. Оказывается, математика полна “неразрешимых” утверждений.
Аналогичным образом, он также полон вычислительно неразрешимых проблем — проблем, которые не могут быть решены ни одним алгоритмом за конечный промежуток времени. Математики обнаружили в 1960-х годах, что проблемы, связанные с разбиением на части, также могут быть неразрешимыми. То есть для некоторых наборов фигур вы можете доказать, что за конечное время невозможно определить, занимают ли они данное пространство или нет. (В принципе, единственным способом сделать это было бы рассмотреть все возможные способы укладки плиток рядом друг с другом до скончания времен.)
“Это очень простая в постановке задача, но, тем не менее, она выходит за рамки математики”, — сказал Ричард Кеньон, математик из Йельского университета. “Это не первый пример подобной ситуации, когда определенная математическая теория неразрешима или неполна, но это действительно самый приземленный пример”.
В прошлом году Гринфельд и Тао обнаружили, что общее утверждение о парах плиток высокой размерности неразрешимо: они доказали, что никто никогда не сможет выяснить, можно ли сделать так, чтобы определенные пары плиток полностью покрывали пространство, в котором они обитают (будь то периодически или апериодически).
Может ли утверждение об одной плитке также быть неразрешимым? С 1960-х годов было известно, что если бы гипотеза о периодической укладке плитки была верна, то всегда можно было бы определить, может ли любая данная плитка покрывать плоскость.
Но обратное не обязательно верно. Просто потому, что существует апериодическая плитка, это не означает, что существует неразрешимая плитка.
Это то, что Гринфельд и Тао хотят выяснить дальше, используя некоторые методы, которые они разработали для своего недавнего результата. “Мы считаем вполне правдоподобным, что созданный нами язык должен быть способен создать неразрешимую головоломку”, — сказал Тао. “Таким образом, может быть какая-то плитка, для которой мы никогда не сможем доказать, что она занимает место или не занимает его”.
Чтобы доказать, что утверждение неразрешимо, математики обычно показывают, что оно эквивалентно другому вопросу, который, как уже известно, неразрешим. В результате, если эта проблема разбиения на плитки также окажется неразрешимой, она может послужить еще одним инструментом для демонстрации неразрешимости в других контекстах — контекстах, выходящих далеко за рамки вопросов о том, как разбивать пространства на плитки.
В то же время, однако, результат Гринфельда и Тао служит своего рода предупреждением. “Математики любят красивые, чистые утверждения”, — сказал Иосевич. “Но не верьте всему, что вы слышите. … К сожалению, не факт, что все интересные утверждения в математике должны быть красивыми и что они должны работать так, как мы этого хотим”.