Функция Дена

редактировать

В математическом предмете геометрической теории групп, функция Дена, названная в честь Макс Ден, является оптимальной функцией, связанной с представлением конечной группы, которое ограничивает область отношения в этой группе (это свободно сокращенное слово в генераторах, представляющее тождественный элемент группы) с точки зрения длины этого отношения (см. стр. 79–80 в). Тип роста функции Дена - это квазиизометрический инвариант конечно определенной группы. Функция Дена конечно представленной группы также тесно связана с недетерминированной алгоритмической сложностью проблемы слов в группах. В частности, конечно представленная группа имеет разрешимую проблему слов тогда и только тогда, когда функция Дена для конечного представления этой группы рекурсивна (см. теорему 2.1 в). Идея функции Дена мотивирована изопериметрическими проблемами геометрии, такими как классическое изопериметрическое неравенство для евклидовой плоскости и, в более общем плане, понятие функции площади заполнения, которая оценивает площадь a минимальная поверхность в римановом многообразии в терминах длины граничной кривой этой поверхности.

Содержание

1 История
2 Формальное определение
- 2.1 Область отношения
- 2.2 Изопериметрическая функция
- 2.3 Функция Дена
- 2.4 Типы роста функций
3 Основные свойства
4 Примеры
5 Известные результаты
6 Обобщения
7 См. Также
8 Примечания
9 Дополнительная литература
10 Внешние ссылки

История

Идея Изопериметрическая функция для конечно представленной группы восходит к работе Макса Дена в 1910-х годах. Ден доказал, что проблема слов для стандартного представления фундаментальной группы замкнутой ориентированной поверхности рода как минимум два разрешима с помощью того, что теперь называется алгоритмом Дена. Прямым следствием этого факта является то, что для этого представления функция Дена удовлетворяет условию Dehn (n) ≤ n. Этот результат был распространен в 1960-х Мартином Гриндлингером на конечно представленные группы, удовлетворяющие условию малого сокращения C '(1/6) . Формальное понятие изопериметрической функции и функции Дена в том виде, в котором оно используется сегодня, появилось в конце 1980-х - начале 1990-х годов вместе с введением и развитием теории словесных гиперболических групп. В своей монографии 1987 г. «Гиперболические группы» Громов доказал, что конечно определенная группа словесно-гиперболическая тогда и только тогда, когда она удовлетворяет линейному изопериметрическому неравенству, то есть тогда и только тогда, когда Функция Дена этой группы эквивалентна функции f (n) = n. Доказательство Громова в значительной степени основано на аналогии с функциями заполнения площади для компактных римановых многообразий, где площадь минимальной поверхности, ограничивающей нуль-гомотопную замкнутая кривая ограничена длиной этой кривой.

Изучение изопериметрических функций и функций Дена быстро превратилось в отдельную важную тему в геометрической теории групп, тем более что типы роста этих функций являются естественными квазиизометрией инварианты конечно определенных групп. Один из основных результатов в этой области был получен Сэпиром, Бирджетом и Рипсом, которые показали, что большинство «разумных» функций временной сложности машин Тьюринга могут быть реализованы с точностью до естественной эквивалентности, как функции Дена конечно определенных групп.

Формальное определение

Пусть

G = ⟨X | R⟩ (∗) {\ Displaystyle G = \ langle X | R \ rangle \ qquad (*)}

G = \ langle X | R \ rangle \ qquad (*)

быть представлением конечной группы, где X - конечный алфавит, а R ⊆ F ( X) - конечный набор циклически редуцированных слов.

Площадь отношения

Пусть w ∈ F (X) - отношение в G, то есть свободно сокращенное слово такое, что w = 1 в G. Заметим, что это эквивалентно говоря, что w принадлежит нормальному замыканию R в F (X), то есть существует представление w как

w = u 1 r 1 u 1 - 1 ⋯ umrmum - 1 в F (X), {\ displaystyle w = u_ {1} r_ {1} u_ {1} ^ {- 1} \ cdots u_ {m} r_ {m} u_ {m} ^ {- 1} {\ text { in}} F (X),}

{\ displaystyle w = u_ {1} r_ {1} u_ {1} ^ { -1} \ cdots u_ {m} r_ {m} u_ {m} ^ {- 1} {\ text {in}} F (X),}

(♠)

где m ≥ 0 и где r i ∈ R для i = 1,..., m.

Для w ∈ F (X), удовлетворяющего w = 1 в G, площадь w относительно (∗), обозначенная Area (w), является наименьшей m ≥ 0 такой, что существует представление ( ♠) для w как произведение в F (X) m сопряженных элементов из R.

Свободно редуцированное слово w ∈ F (X) удовлетворяет w = 1 в G тогда и только тогда, когда петля, помеченная w в комплексе представлений для G, соответствующем (∗), является гомотопным нуль. Этот факт можно использовать, чтобы показать, что Area (w) - это наименьшее количество 2-ячеек в диаграмме Ван Кампена над (∗) с граничным циклом, помеченным w.

Изопериметрическая функция

Изопериметрическая функция для конечного представления (∗) - это монотонная неубывающая функция

f: N → [0, ∞) {\ displaystyle f: \ mathbb {N} \ to [0, \ infty)}

{\ displaystyle f: \ mathbb {N} \ to [0, \ infty)}

такое, что всякий раз, когда w ∈ F (X) является свободно сокращенным словом, удовлетворяющим w = 1 в G, то

Area (w) ≤ f (| w |),

где | w | - длина слова w.

Функция Дена

Тогда функция Дена конечного представления (∗) определяется как

D ehn (n) = max {A rea (w): w = 1 в G, | w | ≤ n, w свободно сводится. } {\ displaystyle {\ rm {Dehn}} (n) = \ max \ {{\ rm {Area}} (w): w = 1 {\ text {in}} G, | w | \ leq n, w {\ text {свободно сокращенный}}. \}}

{\ displaystyle {\ rm {Dehn}} (n) = \ max \ {{\ rm {Area}} (w): w = 1 {\ text { in}} G, | w | \ leq n, w {\ text {свободно уменьшено}}. \}}

Эквивалентно, Dehn (n) является наименьшей изопериметрической функцией для (∗), то есть Dehn (n) является изопериметрической функцией для (∗) и для любого другого изопериметрической функции f (n) мы имеем

Dehn (n) ≤ f (n)

для каждого n ≥ 0.

Типы роста функций

Поскольку функции Дена обычно трудно вычислить точно, обычно изучаются их типы асимптотического роста, когда n стремится к бесконечности.

Для двух монотонно-неубывающих функций

f, g: N → [0, ∞) {\ displaystyle f, g: \ mathbb {N} \ to [0, \ infty)}

{\ displaystyle е, g: \ mathbb {N} \ к [0, \ infty)}

говорят, что в f преобладает g, если существует C ≥1 такое, что

f (n) ≤ C g (C n + C) + C n + C {\ displaystyle f (n) \ leq Cg (Cn + C) + Cn + C}

{\ displaystyle f (n) \ leq Cg (Cn + C) + Cn + C}

для любого целого n ≥ 0. Скажем, что f ≈ g, если f доминирует над g, а g доминирует над f. Тогда ≈ является отношением эквивалентности, и функции Дена и изопериметрические функции обычно изучаются с точностью до этого отношения эквивалентности. Таким образом, для любых a, b>1 имеем a ≈ b. Аналогично, если f (n) - многочлен степени d (где d ≥ 1 - действительное число) с неотрицательными коэффициентами, то f (n) ≈ n. Кроме того, 1 ≈ n.

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

Основные свойства

Если G и H являются квазиизометрическими конечно определенными группами и некоторое конечное представление G имеет изопериметрическую функцию f (n), то для любое конечное представление H существует изопериметрическая функция, эквивалентная f (n). В частности, этот факт верен для G = H, где одна и та же группа задается двумя разными конечными представлениями.
Следовательно, для конечно определенной группы тип роста ее функции Дена, в смысле приведенного выше определения не зависит от выбора конечного представления для этой группы. В более общем смысле, если две конечно определенные группы квазиизометричны, то их функции Дена эквивалентны.
Для конечно определенной группы G, заданной конечным представлением (∗), следующие условия эквивалентны :
- G имеет рекурсивную функцию Дена относительно (∗).
- Существует рекурсивная изопериметрическая функция f (n) для (∗).
- Группа G имеет разрешимую проблему слов.

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

Знание площади Площадь (w) отношения w позволяет ограничить в терминах | w | не только количество конъюгатов определяющих отношений в (♠), но также и длины сопрягающих элементов u i. Как следствие, известно, что если конечно представленная группа G, заданная конечным представлением (∗), имеет вычислимую функцию Дена Dehn (n), то проблема слов для G разрешима с недетерминированной временной сложностью Dehn (n) и детерминированная временная сложность Exp (Dehn (n)). Однако в целом не существует разумной границы для функции Дена конечно представленной группы с точки зрения детерминированной временной сложности проблемы слов, и разрыв между двумя функциями может быть довольно большим.

Примеры

Для любого конечной группе G имеем Dehn (n) ≈ n.
Для замкнутой ориентированной поверхности рода 2 стандартное представление ее фундаментальной группы

G = ⟨a 1, a 2, b 1, млрд | [a 1, b 1] [a 2, b 2] = 1⟩ {\ displaystyle G = \ langle a_ {1}, a_ {2}, b_ {1}, b_ {n} | [a_ {1}, b_ {1}] [a_ {2}, b_ {2}] = 1 \ rangle}

{\ displaystyle G = \ langle a_ { 1}, a_ {2}, b_ {1}, b_ {n} | [a_ {1}, b_ {1}] [a_ {2}, b_ {2}] = 1 \ rangle}

удовлетворяет Dehn (n) ≤ n и Dehn (n) ≈ n.

Для любого целого числа k ≥ 2 свободная абелева группа $Z k {\ displaystyle \ mathbb {Z} ^ {k}}$ ${\ displaystyle \ mathbb {Z} ^ {k}}$ имеет Dehn (n) ≈ n.
Группа Баумслага-Солитара

B (1, 2) = ⟨a, b | b - 1 ab = a 2⟩ {\ displaystyle B (1,2) = \ langle a, b | b ^ {- 1} ab = a ^ {2} \ rangle}

{\ displaystyle B (1,2) = \ langle a, b | b ^ {- 1} ab = a ^ {2} \ rangle}

имеет Dehn (n) ≈ 2 (см.).

Трехмерная дискретная группа Гейзенберга

H 3 = ⟨a, b, t | [a, t] = [b, t] = 1, [a, b] = t 2⟩ {\ displaystyle H_ {3} = \ langle a, b, t | [a, t] = [b, t] = 1, [a, b] = t ^ {2} \ rangle}

{\ displaystyle H_ {3} = \ langle a, b, t | [a, t] = [b, t] = 1, [a, b] = t ^ {2} \ rangle}

удовлетворяет кубическому, но не квадратичному изопериметрическому неравенству.

многомерные группы Гейзенберга

H 2 k + 1 = ⟨a 1, b 1,…, ak, bk, t | [ai, bi] = t, [ai, t] = [bi, t] = 1, i = 1,…, k, [ai, bj] = 1, i ≠ j⟩ {\ displaystyle H_ {2k + 1 } = \ langle a_ {1}, b_ {1}, \ dots, a_ {k}, b_ {k}, t | [a_ {i}, b_ {i}] = t, [a_ {i}, t ] = [b_ {i}, t] = 1, i = 1, \ dots, k, [a_ {i}, b_ {j}] = 1, i \ neq j \ rangle}

{\ displaystyle H_ {2k + 1} = \ langle a_ {1}, b_ { 1}, \ dots, a_ {k}, b_ {k}, t | [a_ {i}, b_ {i}] = t, [a_ {i}, t] = [b_ {i}, t] = 1, я знак равно 1, \ точки, к, [a_ {i}, b_ {j}] = 1, я \ neq j \ rangle}

где k ≥ 2, удовлетворяют квадратичным изопериметрическим неравенствам.

Если G является «группой Новикова-Буна», то есть конечно определенной группой с неразрешимой проблемой слов, то функция Дена группы G растет быстрее, чем любая рекурсивная функция.
Для группы Томпсона F функция Дена является квадратичной, то есть эквивалентной n (см.).
Так называемая группа Баумслага-Герстена

G = ⟨a, t | (T - 1 a - 1 t) a (t - 1 at) = a 2⟩ {\ displaystyle G = \ langle a, t | (t ^ {- 1} a ^ {- 1} t) a (t ^ {-1} at) = a ^ {2} \ rangle}

{\ displaystyle G = \ langle a, t | ( t ^ {- 1} a ^ {- 1} t) a (t ^ {- 1} at) = a ^ {2} \ rangle}

имеет функцию Дена, растущую быстрее, чем любая фиксированная итерационная башня экспонент. В частности, для этой группы

Dehn (n) ≈ exp (exp (exp (... (exp (1))...)))

где количество экспонент равно интегралу часть журнала 2 (n) (см.).

Известные результаты

Конечно представленная группа является гиперболической группой тогда и только тогда, когда ее функция Дена эквивалентна n, то есть тогда и только тогда, когда каждое конечное представление этой группы удовлетворяет линейному изопериметрическому неравенству.
Изопериметрический разрыв : Если конечно представленная группа удовлетворяет субквадратичному изопериметрическому неравенству, то она является гиперболической по словам. Таким образом, не существует конечно определенных групп с функциями Дена, эквивалентными n при d ∈ (1,2).
Автоматические группы и, в более общем смысле, удовлетворяют квадратичным изопериметрическим неравенствам.
Конечно порожденные нильпотентная группа имеет функцию Дена, эквивалентную n, где d ≥ 1, и все положительные целые числа d реализуются таким образом. Более того, любая конечно порожденная нильпотентная группа G допускает полиномиальное изопериметрическое неравенство степени c + 1, где c - класс нильпотентности группы G.
Множество действительных чисел d ≥ 1, такое, что существует конечно представимое группа с функцией Дена, эквивалентной n, плотна в интервале $[2, ∞) {\ displaystyle [2, \ infty)}$ ${\ display стиль [2, \ infty)}$ .
Если все асимптотические конусы конечно определенной группы являются односвязная, то группа удовлетворяет полиномиальному изопериметрическому неравенству.
Если конечно определенная группа удовлетворяет квадратичному изопериметрическому неравенству, то все асимптотические конусы этой группы односвязны.
Если (M, g) - замкнутое риманово многообразие и G = π 1 (M), то функция Дена группы G эквивалентна функции площади заполнения многообразия.
Если G - группа, действующая должным образом разрывно и кокомпактно изометриями на пространстве CAT (0), то G удовлетворяет квадратичному изопериметрическому неравенству. В частности, это относится к случаю, когда G является фундаментальной группой замкнутого риманова многообразия неположительной секционной кривизны (не обязательно постоянной).
Функция Дена для SL (m, Z ) не более чем экспоненциальна для любого m ≥ 3. Для SL (3, Z ) эта граница точна и в этом случае известно, что функция Дена не допускает субэкспоненциальной верхней границы. Функции Дена для SL (m, Z ), где m>4 квадратичны. Функция Дена для SL (4, Z ) была предположена Тёрстоном как квадратичная.
Группы классов отображения поверхностей конечного типа автоматические и удовлетворяют квадратичным изопериметрическим неравенствам.
Функции Дена для групп Aut (F k) и Out (F k) являются экспоненциальными для любого k ≥ 3. Экспоненциальные изопериметрические неравенства для Aut (F k) и Out (F k) при k ≥ 3 были найдены Хэтчером и Фогтманном. Эти границы точны, а группы Aut (F k) и Out (F k) не удовлетворяют субэкспоненциальным изопериметрическим неравенствам, как показано для k = 3 Бридсоном и Фогтманном, и для k ≥ 4 по Генделю и Мошеру.
Для каждого автоморфизма φ конечно порожденной свободной группы Fkгруппа торов отображения $F k ⋊ ϕ Z {\ displaystyle F_ {k} \ rtimes _ {\ phi} \ mathbb {Z}}$ ${\ displaystyle F_ {k} \ rtimes _ { \ phi} \ mathbb {Z}}$ функции φ удовлетворяет квадратичному изопериметрическому неравенству.
Большинство «разумных» вычислимых функций, которые ≥n, могут быть реализованы с точностью до эквивалентности следующим образом: Функции Дена конечно определенных групп. В частности, если f (n) ≥ n - супераддитивная функция, двоичное представление которой вычислимо во времени $O (f (n) 4) {\ displaystyle O \ left ({\ sqrt [{4}] {f ( n)}} \ right)}$ ${\ displaystyle O \ left ({\ sqrt [{4}] {f (n)}} \ справа)}$ с помощью машины Тьюринга, тогда f (n) эквивалентно функции Дена конечно определенной группы.
Хотя нельзя разумно ограничили функцию Дена группы с точки зрения сложности ее словесной проблемы, Биргет, Ольшанский, Рипс и Сепир получили следующий результат, дающий далеко идущее обобщение теоремы вложения Хигмана : Проблема слов конечно порожденной группы разрешима за недетерминированное полиномиальное время тогда и только тогда, когда эта группа может быть вложена в конечно определенную группу с полиномиальной изопериметрической функцией. Более того, каждую группу с проблемой слов, решаемой за время T (n), можно вложить в группу с изопериметрической функцией, эквивалентной nT (n).

Обобщения

Есть несколько сопутствующих понятий, тесно связанных с понятием изопериметрическая функция. Таким образом, an ограничивает наименьший диаметр (относительно симплициальной метрики, где каждое ребро имеет длину один) диаграммы Ван Кампена для определенного отношения w через длину w. Наименьшая длина заполнения диаграммы Ван Кампена для конкретного отношения w в терминах длины w. Здесь длина заполнения диаграммы - это минимум по всем комбинаторным нуль-гомотопиям диаграммы максимальной длины промежуточных петель, ограничивающих промежуточные диаграммы вдоль таких нуль-гомотопий. Функция длины заполнения тесно связана с недетерминированной пространственной сложностью проблемы слов для конечно представленных групп. Существует несколько общих неравенств, связывающих функцию Дена, оптимальную изодиаметрическую функцию и функцию оптимальной длины заполнения, но точная связь между ними еще не выяснена.
Существуют также многомерные обобщения изопериметрической функции и функции Дена.. При k ≥ 1 k-мерная изопериметрическая функция группы ограничивает минимальный комбинаторный объем (k + 1) -мерных заполнений шарами k-сфер, отображаемых в k-связное пространство, на котором группа действует правильно и кокомпактно; оценка дана как функция комбинаторного объема k-сферы. Стандартное понятие изопериметрической функции соответствует случаю k = 1. В отличие от случая стандартных функций Дена, мало что известно о возможных типах роста k-мерных изопериметрических функций конечно представленных групп при k ≥ 2.
В своей монографии «Асимптотические инварианты бесконечных групп» Громов предложил вероятностную или усредненную версию функции Дена и предположил, что для многих групп усредненные функции Дена должны иметь строго более медленную асимптотику, чем стандартные функции Дена. Более точные трактовки понятия усредненной функции Дена или средней функции Дена были даны позже другими исследователями, которые также доказали, что действительно усредненные функции Дена субасимптотичны стандартным функциям Дена в ряде случаев (таких как нильпотентные и абелевы группы). 199>Относительная версия понятия изопериметрической функции играет центральную роль в подходе Осина к относительно гиперболическим группам.
Григорчук и Иванов исследовали несколько естественных обобщений функции Дена для представления групп на конечном числе образующих. но с бесконечным множеством определяющих отношений.

См. также

Примечания

Дополнительная литература

Ноэль Брэди, Тим Райли и Хэмиш Шорт. Геометрия задачи о словах для конечно порожденных групп. Дополнительные курсы по математике CRM Barcelona, Birkhäuser, Basel, 2007. ISBN 3-7643-7949-9.
Мартин Р. Бридсон. Геометрия проблемы слова. Приглашения к геометрии и топологии, стр. 29–91, Oxford Graduate Texts in Mathematics, 7, Oxford University Press, Oxford, 2002. ISBN 0-19-850772-0.

Внешние ссылки

Изопериметрическое неравенство для SL (n, Z). Семинар в сентябре 2008 г. в Американском институте of Mathematics.
PDF статьи Бридсона Геометрия словесной задачи.