Небольшой рассказ о грубой геометрии
Моя статья для газеты Троицкий вариант. Для тех, у кого трудности с VPN привожу cокращенный текст статьи — полный текст доступен на сайте газеты. А для тех, кто посчитает нужным — газету можно поддержать рублём.
Место действия — метрические пространства
Перед тем, как перейти к главному герою — грубым отображениям, сначала нужно определиться с тем, где же будут разворачиваться дальнейшие события. Нудно говоря, метрическое пространство это такая пара (M, ρ) из множества M и функции ρ: M × M → ℝ, называемой метрикой (иначе — расстоянием), что выполнены следующие свойства:
- ρ(a; b) ≥ 0, ρ(a; b) = 0 ↔ a = b — расстояние неотрицательно и между не совпадающими точками отлично от нуля;
- ρ(a; b) = ρ(b; a) — расстояние симметрично;
- ρ(a; b) + ρ(b; c) ≥ ρ(a; c) — неравенство треугольника.
Сразу скажем, что привычная нам евклидова метрика и другие ее близкие родственники уже соответствуют нашему определению. То же касается и расстояния в графе — минимальной длины пути, соединяющего вершины. Еще одним очень важным примером метрического пространства является геометрия Лобачевского, например ее модель в верхней полуплоскости.
Итак, оформим наши примеры в более научных терминах. Мы дальше будем много говорить о разных метриках на плоскости ℝ^2 и всегда будем подразумевать, что там заданы декартовы координаты, т. е. у каждой точки есть координаты (x, y). И, скажем, верхняя полуплоскость состоит из точек вида (x, y), где y > 0.
Итак, следующие пары задают структуру метрического пространства:
1. Плоскость ℝ^2 и функция ρ_p для p ≥ 1
2. Верхняя полуплоскость и (страшноватая, но как есть) функция ρ заданной формулой
3. Ненаправленный граф γ и функция ρ(a, b) = длина минимального пути из a в b.
Обратим внимание на первый пример. Если p = 2, то мы получаем обычную евклидову метрику. А если p = 1, то так называемую манхеттенскую, или городскую, как иногда говорят. А вот метрика ρ задает геометрию Лобачевского (это когда через данную точку можно провести бесконечно много прямых, параллельных данной). Больше о геометрии Лобачевского можно прочитать в [1].
Грубость — это, &*△#$, в каком смысле?
Начнем с того, что между двумя метрическими пространствами может найтись взаимно однозначное отображение f : (M_1, ρ^1) → (M_2, ρ^2), сохраняющее расстояния ρ_1 (f(x_1),f(x_2)) = ρ^2 (x_1, x_2). Тогда такие метрические пространства называют изометричными. К примеру, если вы возьмете и «cомнете» плоскость, сохранив расстояние, т. е. считая расстояние между точками на мятой плоскости как расстояние между точками на обычной, то такое отображение будет изометрией. Но понятно, что изометричность — очень сильное условие. К примеру, для разных p введенные нами выше пространства (ℝ^2, ρ_p) изометрическими не будут, хотя с точки зрения внутреннего устройства они друг на друга достаточно похожи. А вот на геометрию Лобачевского, к примеру, они совсем не похожи. Точно так же понятно, что прямую ℝ уместно сравнивать с целыми числами ℤ, а плоскость — с целочисленной решеткой ℤ × ℤ.
Возникает естественное желание найти какое-нибудь условие «равенства», более слабое, чем изометричность, но все-таки имеющее понятный геометрический смысл. При этом хотелось бы, чтобы похожие метрические пространства были «равными», а непохожие — не были. В таком случае мы сможем искать разные инварианты, которые позволят нам отличать похожее от непохожего. Такое условие называется квазиизометричностью.
Итак, назовем отображение F : (M_1, ρ^1) → (M_2, ρ^2) квазиизометрией (или грубой изометрией), если:
1. Найдутся константы A, B такие, что
2. Найдется константа C такая, что
Попробуем перевести эти формулы на человеческий язык. Первое условие значит, что расстояние между точками f(x) и f(y) хоть и меняется, но контролируемо: точки не могут ни слишком далеко разбежаться, ни слипнуться. Если мы возьмем A = 1; B = 0, то получим изометричность. А при иных A, B получаем степень искажения относительно обычно изометрии. Второе же условие аналогично взаимной однозначности: оно дает нам, что у каждой точки z в образе (куда бъем) есть если не настоящий прообраз f–1(z), то во всяком случае такая точка x, что ее образ попадает «недалеко» от z.
Несложно убедиться (проще, чем в «Ландафшице»), что все метрические пространства (ℝ2, ρp) квазиизометричны относительно тождественного отображения id: x ⟼ x. Куда сложнее проверить (но все-таки можно), что они не квазиизометричны геометрии Лобачевского.
Так же заметим, что прямая R (с обычной метрикой) квазиизометрична целым числам ℤ так же, как плоскость (с метриками ρp) всегда грубо изометрична целочисленной решетке. Но ни в коем случае не грубо эквивалентна прямой, что тоже можно проверить непосредственно, но ниже мы предложим способ сделать это «автоматически».
Еще можно установить, что разные графы Кэли для одной группы (о которых я рассказывал в [2]) обязательно будут квазиизометричными, хоть и не будут изометричными.
Конец близок?
Чем отличается прямая от плоскости? Или они обе от пучка лучей, исходящих из одной точки «по всем румбам»? Крупномасштабно, т. е. если посмотреть издалека («вооруженным взглядом»), становится понятно, что разница — в торчащих в разные стороны бесконечных «хвостах», по каждому из которых можно уйти на бесконечность. Строго выражаясь, речь идет о занятном грубом инварианте — числе концов. Дадим сначала определение для графов.
Определение. Будем называть числом концов данного графа γ максимально число бесконечных (!) компонент связности в графах вида γ \ Q, где Q — всевозможные конечные подграфы.
Легко проверить, что число концов (конечное или бесконечное) у разных грубо изометричных пространств обязано совпадать.
Понятно, что у целочисленной решетки на плоскости конец один (как ни вырезай конечную дырку, бесконечный остаток графа будет связен), у прямой — концов два (после вырезания конечной дырки останется два бесконечных луча), а у связки лучей концов столько, сколько лучей. Так что все эти графы не будут грубо эквивалентными, потому что у них число концов разное.
Есть и более занятный пример. Например, у дерева (граф без циклов), в котором есть бесконечно много вершин со степенью три (т. е. вершин, из которых выходит три ребра), концов будет бесконечно много, потому как, вырезая всё больший и больший кусок, мы можем получить сколь угодно много бесконечных компонент связности.
Понятие конца можно обобщить и на случай произвольных метрических пространств.
Определение. Будем называть числом концов данного метрическое пространства (M, ρ) максимальное число бесконечных (!) компонент связности в метрических пространствах вида (M, ρ) \ Q, где Q — всевозможные конечные метрические подпространства.
Как и для графов, легко проверить следующее утверждение. Если два метрических пространства грубо изометричны, то у них число концов одинаково. Обратное, конечно, не верно. Сложный, но важный пример: геометрия Лобачевского имеет один конец, но не грубо изометрична обычной плоскости (у которой снова один конец). Простой (но тоже важный, конечно) пример: целочисленная решетка в трехмерном пространстве и целочисленная решетка на плоскости. Например, ниже нам пригодится гексагональная решетка на плоскости
Дадим и ученое определение для графов (на метрические пространства оно легко обобщается).
Во-первых, лучом в графе будем называть упорядоченную последовательность соседних вершин. Во-вторых, назовем два луча эквивалентными, если есть третий луч, у которого бесконечно много пересечений с обоими лучами.
В-третьих, концом мы назовем классы эквивалентных концов. Таким образом, конец — это не какой-то отдельный подграф, а некая система внутри графа. Хотя геометрически можно говорить, что на прямой, скажем, есть два конца — «левый» и «правый».
Еще один смешно звучащий термин — это «толстый конец» (иначе, простите, жирный конец — fat end, см. [3], это не я придумал). Собственно говоря, конец называется толстым, если в него входит бесконечно много непересекающихся лучей. Ну и несложно видеть, что, к примеру, на плоскости конец один, но толстый. А в луче конец тоже один, но не толстый (иначе говоря — тонкий).
Оказывается, что верно и обратное. Сформулируем теорему Рудольфа Халина (см. оригинальную работу [4], а излагаем мы по [3]).
Теорема. Если в графе есть толстый конец, то в нем есть подграф, изоморфный подразделению гексагональной решетки.
Иными словами, если есть толстый конец, то в некотором подграфе, лежащем в толстом конце, есть структура гексагональной сетки. Доступное доказательство этой теоремы можно прочитать в [3].
Собственно, теорема Халина позволяет в сложно (и, вообще говоря, непонятно как) устроенном толстом конце найти хорошую внутреннюю структуру.
Добавлю еще, что идея, как по множеству концов понять, каким образом можно достигать бесконечности, крайне продуктивна и позволяет строить «грубые» компактификации метрического пространства. Про три разных варианта таких конструкций можно почитать в препринте исследовательницы Элизы Хартман [5].
Скорости роста
Мы уже говорили, что геометрия Лобачевского не будет грубо изометричной евклидовой. Доказывать это в лоб непросто, и нам потребуется еще один сюжет из грубой геометрии — понятие скорости роста метрического пространства. Кстати, любители теории алгоритмов сейчас увидят много знакомых терминов (и неспроста).
Пусть мы имеем решетку в нашем пространстве M. Зафиксируем какую-нибудь точку O и посмотрим на количество точек решетки на расстоянии не более, чем N от O. Получится некоторая функция fM, O(N). Оказывается, любые две функции роста f, g (при фиксированной метрике и разных точках — началах координат) эквивалентны в следующем смысле
для всех достаточно больших n и некоторых положительных констант a, b, c, d. Короче говоря, функция роста может меняться, но если для одной точки она линейна (квадратична, экспоненциальна, etc), то будет линейной (квадратичной, экспоненциалной, etc) и для любой другой точки. Более того, можно показать, что у двух грубо изометричных пространств функции роста также будут эквивалентны.
Например, для ℤ функция роста линейна, для ℤ × ℤ — квадратична, а для дерева, у которого все вершины имеют степень три, — экспоненциальна.
Если внимательно посчитать (ну или обратиться к соответствующей литературе, например [6]), то окажется, что у пространства с геометрией Лобачевского скорость роста экспоненциальная. А значит, геометрия Лобачевского не может быть грубо изометричной евклидовой.
Кстати, отметим, что вопреки ожиданиям людей, знакомых с проблемой P = N P (подробнее см., например [7]), функции роста даже «интересных» метрических пространств бывают не только полиномиальными и экспоненциальными. Оказывается, бывают регулярно устроенные пространства промежуточного роста (граф Кэли некоторой группы) — соответствующий пример построил в 1983 году Ростислав Григорчук. Подробнее об этом результате и вообще о функциях роста см. в [8].
Вернемся к геометрии Лобачевского и заодно разберемся, почему ее называют гиперболической геометрией. Для этого нам потребуется понятие кривизны.
Строгое определение кривизны требует определенных знаний, которых мы от уважаемого читателя совсем не требуем, поэтому попробуем дать понятие кривизны пространства неформально. Сразу скажу, что в журнале «Квант» есть две замечательные статьи про кривизну, на которые можно обратить внимание [10, 11] для лучшего понимания.
Неформально понятие кривизны на поверхности можно воспринимать следующим образом. Возьмем треугольник, у которого стороны — геодезические. И нарисуем треугольник с такими же сторонами на обычной евклидовой плоскости. Если углы треугольника на плоскости меньше исходного — значит, кривизна отрицательна, если больше — положительна. К примеру, сфера — поверхность положительной кривизны. Там бывают треугольники, у которых все углы прямые (и вообще сумма углов всегда больше 180°). А вот на гиперболоиде (на котором реализуется геометрия Лобачевского, откуда и название) кривизна отрицательна, и углы у гиперболического треугольника всегда меньше углов его плоского аналога.
Как при грубых изометриях устроена кривизна, в своем время исследовал Михаил Громов в [9]. Одним из результатов была «кошачья» классификация пространств CAT(k) по параметру k, отвечающему кривизне. CAT в данном случае — акроним фамилий Эли Жозефа Картана, Александра Даниловича Александрова и Виктора Андреевича Топоногова, чьи работы в свое время и легли в основу этой теории.
Полный текст (без ограничения на 16000 символов) — см. здесь.
Литература по теме:
1. Прасолов В. Геометрия Лобачевского // МЦНМО, 2004. mccme.ru/prasolov/
2. Арутюнов А. Как правильно гулять по графам Кэли // ТрВ-Наука № 353 от 17 мая 2022 года. trv-science.ru/2022/05/kak-pravilno-gulyat-po-grapham-cayley/
3. Dlestel R. A short proof of Halin’s grid theorem // Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg. Vol. 74. P. 237–242 (2004).
4. Halin R. Uber die Maximalzahl fremder unendlicher Wege in Graphen // Math. Nachr. 30 (1965). P. 63–85.
5. Hartmanm E. Coarse compactifications of proper metric spaces // arxiv:2009.08147, 2020 arxiv.org/abs/2009.08147
6. Roe J. Lectures on coarse geometry // Pennsylvania State University, University Park, PA, 2003.
7. Шень А. Проблема перебора // Postnauka, 04.03.2015 postnauka.ru/faq/43795
8. Grigorchuk R., Pak I. Groups of Intermediate Growth, an Introduction // L’Enseignement Mathematique. 2008. Vol. 54. P. 251–272. math.tamu.edu/~grigorch/publications/grigorchuk_pak_intermediate_growth.pdf
9. Gromov M. Hyperbolic groups // Essays in group theory. Math. Sci. Res. Inst. Publ. 8. New York: Springer, 1987. P. 75–263.
10. Виленкин Н. О кривизне // Квант. 1992. № 4. С. 2–9, 15. kvant.mccme.ru/1992/04/o_krivizne.htm
11. Табачников С. Л. О кривизне // Квант. 1989. № 6. С. 15–21 kvant.mccme.ru/1989/05/o_krivizne.htm
Простите, я пока не врубаюсь, Вы рассматриваете метрические пространства (скорее, особняком в единственном, а не... Читать дальше
@Леонид Коганов, речь идёт о том, что традиционно рассматривают понятие изометрии. Выражаясь нестрого: два метрических пространства одинаковы, если они изометричны. Я предлагаю (вслед за … ) рассматривать квазиизометричность. В тексте есть две идеи:
- Какие пространства "квазиизометрия" различает, а какие нет. Вот с точки зрения l_p метрик — не различает. А вот например по скорости роста, или по числу концов — различает. Здесь же рядом и идея об инвариантах при квазиизометриях. Простейший — число концов, посложнее — скорость роста. Но есть и другие, конечно.
- Сюжет про теорему Халина имеет целью подвести читателя к мысли о том, что сохраняется при грубых отображениях. Грубое — это когда неравенство на метрики образов есть, а условия "грубой обратимости" — нет. Это сюжет о построении категории метрических пространств, где в качестве морфизмов берутся грубые отображения (ну как в категории векторных пространств берутся линейные операторы).
Ну и кроме того, я пытался дать базовое понятие о том, какие математические задачи можно такими "грубыми методами" решать. Хоть тут есть, конечно, трудности: результатов по приложению грубой геометрии пока не так много, раздел уж больно новый.
"Страшноватая" формула из второго пункта первого раздела "Место действия…" есть, как я пока прикидочно полагаю, формула элементарной аналитической евклидовой декартовой геометрии. Пусть мы имеем две точки А и В верхней полуплоскости, не лежащие на одной прямой (общий случай, сингулярный достигается соответствующим предельным переходом - Л.К.). Геодезическая в модели Пуанкаре есть дуга окружности, соединяющая А с В, причём центр находится на оси абсцисс. Делим отрезок АВ (хорду искомой дуги) пополам и через полученную середину восставляем перпендикуляр. Ищем пересечение с осью абсцисс восставленного перпендикуляра. Получаем длину радиуса и заодно арксинус как значение половинного (к длине геодезической дуги) угла, измеряеого в радианной мере. Полагаю, что переход к записи выше должен даваться стандартно знаменитой формулой (Коутса или Котеса, он был шотландец) - Эйлера (который осмыслил и "продвинул").
Таков пока не реализованный план. Если кто опередит - в обиде не буду (меньше работы! - Л.К.)
Л.К.
Тут у меня враньё в логике, как я сейчас полагаю, и смешение двух метрик: "лобачевское" расстояние должно неограниченно расти при приближении одного из концов геодезической к абсолюту "лобачевской" гиперболическрй плоскости. Виноват и буду "исправляться" постепенно.
К.
Автор удалил комментарий
@Майк Горькинкоф, даже, если Вы - нейросеть, то читайте внимательно начальный курс анализа и не беспокойте людей, реально занятых реальным трудом. Ладно?
Л.К.