Рождественские дни — время отложить привычные дела и вспомнить забавы — калейдоскопы, мозаики, снежинки… Кто нарисует самую красивую звезду?

Симметрия радует глаз. Создать красоту нам помогли математика лапласианов, язык Питон и его библиотеки — математический numpy и графический matplotlib.

Спектры невозможных решеток

КДПВ получена визуализацией значений собственных векторов некой симметричной матрицы.
В основе — спектры регулярных решеток. Мы уже рассматривали некоторые их свойства ранее. Здесь мы попытаемся формулами не злоупотреблять, а заставить их поработать на эстетику.

Итак, допустим, у нас есть некий базовый набор точек, расположенных на плоскости. Требований немного — конфигурация должна быть центрально симметричной. Например, хорошим выбором будет шестиугольная сетка:

Уже красиво, только несколько однообразно.

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

Если мы рассчитаем спектр для набора точек, расположенных на плоскости, то в спектре будет всего лишь две компоненты — одна соответствует координате x, а другая — y.

Нам же надо, чтобы спектр наших точек «зазвенел», но при этом сохранил симметрию. Добиться этого несложно. Достаточно изменить (или возмутить) функцию расстояния между точками. Например, можно положить, что расстояние между точками равно не квадрату расстояния, а его кубу, или вообще обратному расстоянию.

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

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

Допустим, что наша функция расстояния имеет следующий вид:

f(R2) = w*Rd + 1/Rd, где w = dist/n^2, Rd = R2^degree.

Здесь dist и degree — два варьируемых параметра возмущения. Тогда первые 9 вырожденных уровней для представленной выше базовой конфигурации (гексагональной решетки размера 7) при параметрах возмущения dist = -2, degree = 1 имеют вид:

В левом верхнем углу — исходная конфигурация. Значения параметров подобраны таким образом, чтобы она была почти не искаженной.

Все узоры гарантированно разные, — это следует из свойств собственных векторов (хотя иногда на глаз не отличимы). Некоторые кажутся более необычными чем другими. Вот, например, одна из причудливых конфигураций:


Можно взять в качестве исходного набора квадратную решетку. Тогда симметрия будет квадратной:


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

Добавляем цвет и размер

Выше мы рисовали просто точки (кружки). Если придать этим точкам цвет и размер, то снежинки (узоры) станут веселее и разнообразнее. Фишка в том, что цвет и размер точек мы также можем формировать на основе собственных векторов данного набора.

Алгоритм формирования цвета простой. Мы используем некую цветовую карту (из доступных наборов в matplotlib), которая преобразует значение точки в цвет, а само значение точки берем из какого-нибудь невырожденного собственного вектора. То же самое и для размера точки. Тогда можно получить примерно такое веселое кружево:


Если варьировать только цвет, то можно поиграть в детскую мозаику:

Это математика разукрасила базовую конфигурацию точек в разные цвета. А шестиугольные маркеры мы взяли из доступных в matplotlib.

Паутинки

Если близкие точки соединить линиями, то мы получим нечто вроде паутины. По научному такая операция называется триангуляцией. Достоинство пакета matplotlib в том, что там такая операция доступна «из коробки». Паутинки красивы:


Можно удалить часть треугольников на основе масок:

Мозаики

Триангуляция становится цветной, если треугольники залить разными цветами:


Выбор цветовой карты и цветового вектора сильно влияет на восприятие одной и той же конфигурации:

Использование масок обостряет контуры узоров:

Количество комбинаций и вариаций практически бесконечно. Игра узоров очень причудлива.

Контуры

Возможно, что самыми изысканными являются узоры, полученные с помощью рисования контуров на основе триангуляции. Данные узоры получаются с помощью метода tricontour() библиотеки matplotlib. Даже самые невзрачные и скучные наборы точек приобретают совершенно неожиданные вариации.

Симметрия может быть любой, например, 5-го порядка:

На наш взгляд, это магия.

Спектроскоп

Все приведенные узоры создавались с помощью программы "Spectroscope" написанной нами на Питоне. Код программы не идеален, но доступен.



С ее помощью каждый может создавать узоры, варьируя параметры через несложный интерфейс.

Вверху панели управления можно выбрать один из базовых наборов распределений точек (Base). Базовое распределение всегда имеет индекс один, если параметры возмущения равны соответственно -2 (Disturb) и 1 (Degree), поэтому на него можно всегда посмотреть.

Наиболее мощными являются базовые наборы Hex (гекс) и Square (квадрат), так как в них больше всего точек. Поэтому и разнообразных узоров они дают больше. А вот наборы x-border (границы многоугольников) и особенно Circle (окружность) наоборот — выхолощены и интересны больше для исследовательских целей.

Для базового набора можно указать его размер (Order) с помощью слайдера (ползунка). Следующее поле (Index) задает номера отображаемых спектров (уровней) из доступных для данного набора. В данной версии можно выводить 1, 4 или 9 узоров одновременно.

Важный параметр — тип узора (Plot type). Именно он задает способ (режим) отображения наших собственных векторов. Доступные мы перечислили выше (Points, Web, Mosaic, Contour).

Флажок "Titles" выводит над каждым спектром его числовые параметры, порядковый номер в общем составе уровней и значение собственного числа данного уровня. Это для тех, кому интересна не только графика.

Ниже мы видим два слайдера для параметров варьирования. При их изменении спектры оживают. Напомним, что правая кнопка мыши на слайдере — сдвигает его к текущему положению, левая — инкрементирует.

Далее следуют параметры, влияющие на вид спектров — цвет, маркеры и маска. Не во всех режимах отображения они задействованы. Маркеры, например, имеют значение только для «точечного» режима, а маски — наоборот,- для всех, кроме точечного.

Наиболее важен, пожалуй, цвет (Color). Для его задания необходимо указать цветовую карту (Map). Но играют цветом с помощью вектора (слайдер с флажком Use). Вектор цвета (и размера маркеров тоже) выбирается, как уже отмечалось, из невырожденных уровней.

В меню программы доступны стандартные функции для сохранения спектров в файлы и экспорта как изображений.

Есть много направлений, куда можно развивать спектроскоп. Помимо очевидных улучшений интерфейса, развития возможностей (анимация, например, или веб-доступ) нужно попробовать построить трехмерные узоры. Их можно не только смотреть, но и лепить ).

Математические аспекты

Во время игр со спектрами мы столкнулись с несколькими проблемными вопросами разной степени важности.

Расчет количества вырожденных спектров

Может, это и не самый важный вопрос, но возможно, самый простой. Очевидно, что доля вырожденных спектров зависит от базового распределения точек. Для основных решеток (гексагональной и квадратной) есть явные формулы.

Для гексагональной решетки количество «снежинок» Ns связано с общим количеством точек (узлов) N как:

Ns = (N-1)/3

В свою очередь количество точек квадратично зависит от размера решетки a:

N(a) = 3a(a-1) + 1. Отсюда Ns(a) = a(a-1).

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

Ns = N/4 = a^2/4

Как получать такие формулы для произвольных конфигураций — не очень понятно. Возможно, что общего алгоритма и не существует, но мы в этом не уверены.

Идентификация уровней спектра

Пожалуй, наиболее интересный вопрос. Насколько нам известно, основным способом идентификации уровней спектра является величина собственного числа. Если отсортировать данные числа в порядке возрастания, то можно каждому уровню (значению собственного числа) присвоить индекс. Данный индекс как будто бы и идентифицирует спектр.

На самом деле это не очень надежный способ. При варьировании параметров возмущения спектры оживают — узоры начинают дышать (понаблюдайте, например, как «плющит» базовое распределение при изменении параметра Disturb) и их собственные числа тоже меняются. При этом возникают ситуации, когда собственные числа разных уровней приближаются к друг другу и меняются местами в порядке сортировки. Узор (спектр), за которым мы наблюдали, может неожиданно переместиться на другое место, а его место занимает другой. При этом по характеру рисунка мы видим, где какой спектр, но программа об этом не знает. Этот «характер» и надо каким-то образом хэшировать в идентификатор.

Фазовые переходы

Явление бурного изменения узоров происходит в узкой полосе параметра возмущения. Похоже чем-то на фазовый переход. Возможно, что это известное явление. При фазовом переходе меняется как вид спектров, так и их относительное расположение. Мы специально выбрали вид возмущаемой функции таким, чтобы при изменении параметра возмущения Disturb функция меняла знак. Можно видеть, что базовое распределение при изменении параметра с минимального на максимальный переходит с первого индекса на последний. Этот переход осуществляется вроде бы перемещением базового узора по индексам от меньшего к большему. Через какое-то время мы видим измененный базовый узор на последнем индексе. Который затем эволюционирует к исходной базовой конфигурации.

Однако в больших конфигурациях, похоже, никто никуда не перемещается (ну или мы не можем отследить). Просто в определенный момент возникает зачаток новой базовой конфигурации в нужном месте (на максимальном индексе). Короче, интересно — посмотрите ).

Если бы у нас был какой-то параметр идентификации собственных уровней — мы бы более точно могли отслеживать перемещение (или смерть и рождение?) спектров. И показывать на картинке всегда заданные спектры независимо от значений их собственных чисел.

Стабилизация картинки

тоже пока нам не особо удалась. Узоры периодически вращаются вправо/влево. Непонятно, как нужно их сориентировать всегда в одном направлении.

Делители

Когда базовой конфигурацией является простая окружность (точки в вершинах правильных многоугольников), то мы сталкиваемся с феноменом делителей целых чисел. В такой конфигурации все точки равноправны. Соответственно все вырожденные уровни (а других тут и нет) также являются координатами вершин многоугольников (лежат на окружности). Но при этом спектры простых многоугольников (число вершин простое число) отличаются от составных. В спектрах простых все уровни — это тоже простые многоугольники с таким же числом вершин. А в спектрах составных уровни состоят из делителей вершин базового многоугольника.
Например, спектр 30-угольника состоит из 14 вырожденных уровней. Из них четыре 30-угольника, четыре 15-угольника, два 10-угольника, один 6-угольник, два 5-угольника и один 3-угольник. Почему именно такое распределение уровней по делителям — нам не ясно (но мы сильно и не вникали). Возможно, это уже объяснено где-то в теории групп.

На этом пока все. Удачи в творческом поиске и с Рождеством!