Предлагаю сегодня поговорить о факторизации — не самом интуитивно понятном, но очень важном инструменте "большой" математики. Эта статья не из простых, хотя ничего сложного в ней нет. Дело в том, что в ней мы рассмотрим, как математика формализует один из основных инструментов мышления — абстракцию. А абстракции могут стать чем-то внятным только после знакомства с большим числом конкретных примеров.
И вот, в качестве первого примера, мы возьмём листок бумаги и посадим на него кляксу. Пятно может быть какой угодно формы и даже состоять из нескольких частей. После того, как наше произведение будет готово, поставим перед собой следующую задачу.
Пусть мы знаем какая площадь листа оказалась запачканной. Теперь построим на этом же листке регулярную решётку, такую что её элементарная ячейка будет иметь площадь, равную площади кляксы. Можно ли, не меняя формы кляксы, найти такое расположение решётки, чтобы ни один её узел не попал внутрь запачканной области, в крайнем случае, оказался бы на границе кляксы.
Для большинства реальных клякс, имеющих вид одного пятна, утвердительный ответ на вопрос кажется вполне очевидным. Но если клякса будет состоять из множества капель, очевидность существенно пошатнётся. А на картинке ниже показана клякса для которой разместить решётку, не испачкав кляксой узлы, удалось, но с большим трудом. Стоит немного пошевелить сетку, не поворачивая её, как тот или иной узел попадёт внутрь кляксы.
Кляксы бывают разные: вытянутые, кольцеобразные, хаотично разбросанные по листку, и даже художественные. Как доказать что-то про все кляксы сразу? В таких случаях имеет смысл заняться не кляксой, а пространством, на котором она располагается. Клякс много, пространство — одно.
Чтобы бесконечное пространство стало конечным и обозримым, мы прибегнем к одному из важнейших математических приёмов, к факторизации, которое используется для того, чтобы лучше понять внутреннее устройство тех или иных математических структур и объектов.
О факторизации я уже писал в заметке про целые числа из камней и палок. Напомню, что в основе этой операции лежит некоторое отношение эквивалентности, позволяющее утверждать, что различные объекты в некотором смысле неразличимы.
Одномерная клякса
Для начала, давайте упростим задачу с кляксой до одномерного пространства, к тому же, ещё и дискретного.
Сформулируем её так: в бесконечном ряду одинаковых клеточек выберем произвольные N штук и закрасим их. Моё утверждение состоит в том, что каким бы ни было множество закрашенных клеток, всегда можно выбрать такую решётку из клеток, расположенных на одинаковом расстоянии N+1 друг от друга, что ни одно из них не совпадёт с закрашенным.
Для примера, пусть дискретная "клякса" состоит из шести клеток. Тогда можно так расположить решётку с шагом 7 так, чтобы ни один узел решётки не совпал бы с закрашенной клеткой, как это показано в первом ряду. Обратите внимание, что это положение узлов единственное, все остальные варианты не удовлетворяют условию.
Чтобы доказать, почему решётку возможно расположить нужным образом всегда, мы свернëм бесконечное пространство клеточек, сочтя эквивалентными клеточки, расстояние между которыми равно семи шагам. Соединим дугами эквивалентные клеточки и вот, что получим:
Все клеточки, соединённые дугами, попадают в некий класс, в котором все элементы эквиваленты друг другу. Обратите внимание на то, что процесс отождествления цикличен. Сдвигая дуги семь раз, мы вновь попадаем на тот же класс, с которого начали. Это наблюдение позволяет заключить, что классы эквивалентности образуют замкнутую последовательность из семи клеток, как показано на рисунке:
Колечко, которое мы получили, называется факторпространством. Оно построено по отношению эквивалентности, отождествляющему клеточки, расположенные на расстоянии семи шагов друг от друга.
Исходное большое число клеточек разместилось в семи классах, и в каждом классе оказалась седьмая часть всех клеточек.
Можно думать, об описанном нами процессе, как о вырезании из нашего пространства отрезка, длиной в семь клеточек и склеивании его концов с помощью отношения эквивалентности. Но тут важно заметить, что точки склейки как таковой нет, вернее, все эквивалентные точки склеиваются друг с другом. Полезно представлять факторизацию, не как вырезание и склеивание, а как складывание или проецирование всего бесконечного ряда клеточек на кольцеобразное факторпространство, как показано на рисунке.
Итак, процесс факторизации сливает вместе все клеточки, расположенные на расстоянии в семь клеточек друг от друга. При этом узлы решётки с шагом 7, которые мы обозначали синими кружками, тоже превращаются в одну точку в факторпространстве. Сдвигу решётки при этом соответствует сдвиг этого единственного узла по кольцу факторпространства.
Теперь становится очевидным, что если закрашенных клеток в кляксе окажется меньше количества клеток, помещающихся между узлами, то одна клетка в факторпространстве точно останется пустой. И в ней точно можно будет разместить факторизованный узел решётки. Это решение и будет соответствовать нужному расположению узлов решётки.
Если обозначить пространство клеточек, буквой K, а решётку M, то факторизацию K решёткой M, обозначают K/M. Именно таким образом строятся модулярные арифметики ℤ/mℤ из кольца целых чисел ℤ, которое факторизуется регулярной решёткой с шагом m. Я в примере с кляксой намеренно не использовал никаких чисел, чтобы показать, что это более общий метод, чем вычисления остатков в целочисленной арифметике.
В теории чисел, факторизация — это разложение на множители числа. В алгебре — это разложение на множители выражения, как, например, в этом случае:
Здесь мы увидели, что одно и то же подвыражение (x + y) повторяется с разными множителями и вынесли его за скобку, сложив множители отдельно.
Факторизуя пространство K, мы "выносим за скобки" некоторое повторяющееся подпространство K/M, в нашем случае — цепочку из семи клеточек, оставляя в качестве множителя, решётку M. Формально это записывается так: K = (K/M) × M.
Фактризовав пространство клеток, любой элемент исходного пространства можно найти, как "по адресу", указав класс внутри факторпространства и конкретный узел решëтки, с которого начинается отсчёт классов.
Привычную для нас запись чисел цифрами тоже можно рассматривать, как пример факторизации. Последовательно факторизовав кольцо целых чисел десятками, сотнями, тысячами и так далее, начиная с больших порядков, мы получаем привычную позиционную систему счисления, в которой числа записываются в виде списка цифр — координат в соответствующих решëтках порядков.
Факторизовать можно и непрерывные пространства. Например, если множество вещественных чисел ℝ факторизовать, считая эквивалентными числа, разница между которыми выражается неким фиксированным числом, то получится закольцованный отрезок, или петля. Так, например, можно построить пространство углов, или направлений, факторизовав пространство вещественных чисел отождествлением точек, отстоящих друг от друга на 2π.
Это значит, что в случае одномерной кляксы с суммарной длиной, не превышающей 𝑙, разбрызганной на непрерывной линии, мы всегда сможем разместить на этой линии решётку из точек, отстоящих друг от друга на расстоянии 𝑙 так, чтобы ни одна из этих точек не попадала на кляксу.
Правильный клей
А почему, собственно, мы решили, что факторизация удалась? Также как не все целые числа делятся друг на друга, не всегда можно факторизовать пространство. Важно, чтобы отношение эквивалентности было корректно определено, и чтобы классы эквивалентности делили пространство регулярным образом. Например, если бы решётка была нерегулярной, а представляла множество каких попало ячеек, то затея с факторизацией дискретной цепочки клеточек могла бы не удасться.
В нашей задаче кляксу предполагалось двигать. Движением называют такие преобразования пространства, которые сохраняют все расстояния между точками. Факторизацию можно считать удачной, только если отношение эквивалентности аккуратно переносит преобразование точек пространства на классы, которые являются точками факторпространства.
В нашем случае, сдвиг точки на одну клеточку вправо на исходном пространстве соответствует повороту вправо, то есть, сдвигу закольцованного факторпространства. При этом если точка из клеточки, помеченной буквой X при сдвиге попадëт в клеточку с буквой Y, то в факторпространстве весь класс X должен переместиться при таком же сдвиге в класс Y. Кроме того, в исходном пространстве семикратный сдвиг, совмещает узлы решëтки, и в факторпространстве, при семикратном повороте клетка, в которую отображается узел, совпадёт сама с собой. Так что, похоже наш клей — правильный. При другом делении ичходного пространства на части эти условия могли бы быть нарушены.
При факторизации групп, колец и других алгебраических структур, отношение эквивалентности должно очень бережно переносить свойства операций, так чтобы факторизация была гомоморфизмом. О том, что это такое, мы говорили, изучая почему можно использовать цифры для записи чисел. Это очень важное понятие в математике, и мы ещё не раз будем к нему возвращаться.
Двумерная клякса
Двумерные пространства факторизуются по такому же принципу, что и одномерные.
Отношение эквивалентности для регулярной сетки может быть таким: две точки плоскости эквивалентны, если расстояние между ними, измеряемое вдоль линий сетки равно шагу сетки. Отождествление точек в одном направлении закольцует пространство и превратит его в цилиндр. А эквивалентность в другом направлении сетки закольцует сам цилиндр и он свернётся в тор. При этом все узлы сетки превратятся в одну единственную точку на торе, а все движения сетки (сдвиги и повороты) — в перемещения этой единственной точки по компактной (то есть, замкнутой и ограниченной) тороидальной поверхности.
Я специально выделил в предыдущем абзаце, что расстояние между эквивалентными точками должно совпадать вдоль линий сетки. Подумайте, что мы получим, если пренебрежём этим уточнением и факторизуем плоскость, считая эквивалентными точки, расположенные на расстоянии r друг от друга (ответ я дам в комментарии) .
Можно сформулировать отношение эквивалентности, не используя никаких расстояний и направлений, а опираясь на понятие симметрии. Любая регулярная сетка, даже не квадратная, а прямоугольная или скошенная, обладает отчётливой симметрией: под действием целой группы сдвигов она совпадает сама с собой. Две точки пространства можно считать эквивалентными, если они совпадают при каком-то преобразовании, из группы симметрии решётки (как звёздочки на рисунке сверху). Результатом факторизации пространства по группе симметрии решётки будет область, которую в теории групп называют фундаментальным множеством. Она будет выглядеть, как элементарная ячейка сетки и, в нашем случае, обладать топологией тора.
Хорошо знакомым примером фундаментального множества может быть сектор снежинки, вырезаемой из бумаги. Группа симметрии снежинки, действуя на этот сектор, создаёт всю снежинку, тогда как складывание бумажной снежинки совмещает часть точек друг с другом, делая их неразличимыми. Складывание снежинки можно считать её факторизацией по группе симметрии правильного шестиугольника.
После такого обстоятельного введения, задача с кляксой и сеткой решается практически тривиально! Испачканную кляксой плоскость можно факторизовать сеткой, и получить тор, на который отобразится вся клякса. При этом образом всех узлов решётки будет единственная точка на этом торе. Возможно, занятые кляксой области при факторизации наложатся одна на другую, но даже если этого не произойдёт, поскольку по условию задачи, площадь кляксы равна площади ячейки сетки, на торе обязательно отыщется место для узла решётки, либо, в крайнем случае, узел попадет на край кляксы.
* * *
Сама по себе задача про кляксу не представляет большого интереса. Но мне она нравится. Она дала хороший повод поразбираться с факторизацией, работающем в алгебре, в топологии, в теории групп и теории колец и у нас в головах. В повседневности мы пострянно прибегаем к факторизации, выделяя эквивалентные элементы сложных объектов и "вынося их за скобки".
Приведу ещё один пример факторизации пространства. Мы можем описать многоквартирный дом, как произведение множества подъездов, множества этажей, множества помещений и фундаментального множества планов типовых квартир.
Дом = Типы квартир × помещения × этажи × подъезды.
Помещения: кухни, санузлы и комнаты квартир, расположенных в подъезде друг над другом, как правило, спланированы одинаково. Так что любая комната в доме может быть описана, как упорядоченный набор элементов, факторизующих дом: (помещение, тип квартиры, этаж, подъезд). При этом имеет смысл говорить об абстрактной кухне типовой квартиры, "вынеся за скобки" номера этажа и подъезда.
Более того, топология планов типовых квартир имеет некоторые необычные признаки факторизации: выход из одной квартиры одновременно является входом во все другие на всех этажах, ведь все лестничные площадки эквивалентны. Стены соседних квартир из разных планов тоже отождествляются (они помечены синими стрелками на рисунке), так что нужно иметь в виду, что громкая музыка в левой комнате трёкомнатной квартиры способна проникнуть в правую комнату двушки.
Именно умение нашего мозга факторизовать сложные множества, находя те или иные отношения эквивалентности, позволяют нам говорить об "анатомии человека", "устройстве автомобиля", "структуре администрации городского поселения", без необходимости уточнять о каких именно элементах множеств людей, автомобилей или городов идёт речь.