Григорчук группа - Grigorchuk group

в математический зона теория групп, то Григорчук группа или же первая группа Григорчука это конечно порожденная группа построенный Ростислав Григорчук это предоставило первый пример конечно порожденная группа промежуточного (то есть быстрее, чем полиномиальный, но медленнее, чем экспоненциальный) рост. Группа была первоначально построена Григорчуком в статье 1980 года.^[1] а затем он доказал в статье 1984 г.^[2] что эта группа имеет промежуточный рост, что дает ответ на важную открытую проблему, поставленную Джон Милнор в 1968 году. Группа Григорчука остается ключевым объектом исследования в геометрическая теория групп, особенно при изучении так называемых групп ветвлений и групп автоматов, и имеет важные связи с теорией повторяющиеся группы монодромии.^[3]

История и значение

В рост из конечно порожденная группа измеряет асимптотику, как ${\displaystyle n\to \infty }$ размером с п-бол в Граф Кэли группы (то есть количество элементов грамм которые можно выразить словами длиной не более п в генераторной установке грамм). Изучение темпов роста конечно порожденные группы восходит к 1950-м годам и частично мотивируется понятием объемная энтропия (то есть скорость роста объема шаров) в универсальное перекрытие из компактный Риманово многообразие в дифференциальная геометрия. Очевидно, что скорость роста конечно порожденной группы не превосходит экспоненциальный и было также понятно, что конечно порожденный нильпотентные группы имеют полиномиальный рост. В 1968 г. Джон Милнор задал вопрос^[4] о существовании конечно порожденной группы промежуточный рост, то есть быстрее любой полиномиальной функции и медленнее любой экспоненциальной функции. Важным результатом по теме является Теорема Громова о группах полиномиального роста, полученный Громов в 1981 г., который показывает, что конечно порожденная группа имеет полиномиальный рост тогда и только тогда, когда эта группа имеет нильпотентный подгруппа конечных индекс. До работы Григорчука было много результатов, устанавливающих дихотомию роста (то есть, что рост всегда либо полиномиальный, либо экспоненциальный) для различных классов конечно порожденных групп, таких как линейные группы, разрешимые группы,^[5][6] и Т. Д.

Группа Григорчука грамм был построен в статье 1980 г. Ростислав Григорчук,^[1] где он доказал, что эта группа бесконечна, периодический и финитно аппроксимируемая. В последующей статье 1984 г.^[2] Григорчук доказал, что эта группа имеет промежуточный рост (этот результат был объявлен Григорчуком в 1983 году).^[7] Точнее, он доказал, что грамм имеет рост б(п) что быстрее, чем ${\displaystyle \exp({\sqrt {n}})}$ но медленнее, чем ${\displaystyle \exp(n^{s})}$ куда ${\displaystyle s=\log _{32}31\approx 0.991}$. Позднее верхняя оценка была улучшена Лоран Бартольди^[8] к

${\displaystyle s={\frac {\log 2}{\log 2-\log \eta }}\approx 0.7675,\qquad \eta ^{3}+\eta ^{2}+\eta =2.}$

Нижняя граница ${\displaystyle \exp(n^{0.504})}$ было доказано Юрий Леонов.^[9] Точная асимптотика роста грамм пока неизвестно. Предполагается, что предел

${\displaystyle \lim _{n\to \infty }\log _{n}\log b(n),}$

существует, но даже это оставалось серьезной открытой проблемой. Эту проблему решили в 2020 году Эршлер и Чжэн.^[10] Они показывают, что предел равен ${\displaystyle s}$.

Группа Григорчука также была первым примером группы, которая послушный но нет элементарный податливый, таким образом отвечая на проблему, поставленную День Махлона в 1957 г.^[11]

Изначально группа Григорчука грамм был построен как группа преобразований, сохраняющих меру Лебега на единичном интервале, но впоследствии более простые описания грамм были найдены, и теперь его обычно представляют как группу автоморфизмов бесконечного регулярного двоичный укоренившееся дерево. Изучение группы Григорчука во многом послужило основой для развития теории групп ветвей, групп автоматов и самоподобных групп в 1990–2000-е гг., И группа Григорчука остается центральным объектом этой теории. Недавно важные связи между этой теорией и сложной динамикой, в частности, понятие повторяющиеся группы монодромии, были обнаружены в работе Владимир Некрашевич.^[12] и другие.

После статьи Григорчука 1984 г. было много последующих расширений и обобщений.^{[13][14][15][16]}

Определение

Бесконечное двоичное дерево Т₂. Его узлы помечены строками из нулей и единиц.

Хотя изначально группа Григорчука определялась как группа Мера Лебега -сохраняющие преобразования единичного интервала, в настоящее время эта группа обычно задается своей реализацией как группа автоморфизмов бесконечного регулярного двоичный укоренившееся дерево Т₂. Дерево Т₂ реализуется как набор ${\displaystyle \Sigma ^{*}}$ всех конечных строк в алфавите ${\displaystyle \Sigma =\{0,1\}}$ плюс пустая строка ${\displaystyle \varnothing }$ которая является корневой вершиной Т₂. Для вершины Икс из Т₂ Струна Икс0 - это левый ребенок из Икс и строка Икс1 - это правильный ребенок из Икс в Т₂. Группа всех автоморфизмов Aut (Т₂), таким образом, можно рассматривать как группу всех сохраняющих длину перестановки σ из ${\displaystyle \Sigma ^{*}}$ которые также уважают начальный сегмент отношение, то есть такое, что всякий раз, когда строка Икс это начальный сегмент строки у тогда σ(Икс) - начальный отрезок σ(у).

В Григорчук группа грамм тогда определяется как подгруппа Aut (Т₂) генерируется четырьмя специфическими элементами Aut (Т₂):

${\displaystyle G=\langle a,b,c,d\rangle \leqslant {\text{Aut}}(T_{2}),}$

где автоморфизмы а, б, c, d определяются следующим образом (заметим, что ${\displaystyle \varnothing }$ фиксируется все автоморфизмы дерева):

${\displaystyle {\begin{aligned}a(0)=1,\qquad a(1)=0,\qquad \forall x\in \Sigma ^{*}\quad &{\begin{cases}a(0x)=1x\\a(1x)=0x\end{cases}}\\[6pt]{\begin{aligned}&b(0)=c(0)=d(0)=0\\&b(1)=c(1)=d(1)=1\end{aligned}}\qquad \forall x\in \Sigma ^{*}\quad &{\begin{aligned}&{\begin{cases}b(0x)=0a(x)\\b(1x)=1c(x)\end{cases}}\\&{\begin{cases}c(0x)=0a(x)\\c(1x)=1d(x)\end{cases}}\\&{\begin{cases}d(0x)=0x\\d(1x)=1b(x)\end{cases}}\end{aligned}}\end{aligned}}}$

Действие стандартной образующей группы Григорчука на дереве Т₂. Треугольники обозначают бесконечные поддеревья, которые остаются неизменными.

Мы видим, что только элемент а определен явно, а элементы б, c, d определены рекурсивно. Чтобы получить более полное представление об этом действии, отметим, что ${\displaystyle T_{2}}$ имеет естественную градацию в уровни определяется длиной строк:

${\displaystyle {\begin{aligned}&\ell =0\qquad \varnothing \\&\ell =1\qquad 0,1\\&\ell =2\qquad 00,01,10,11\\&\qquad \cdots \end{aligned}}}$

Теперь позвольте ${\displaystyle T[n]}$ обозначим объединение всех вершин с уровнем ${\displaystyle \leqslant n.}$ Это означает:

${\displaystyle {\begin{aligned}T[0]&=\{\varnothing \}\\T[1]&=\{\varnothing ,0,1\}\\T[2]&=\{\varnothing ,0,1,00,01,10,11\}\\&\quad \cdots \end{aligned}}}$

Поскольку автоморфизмы дерева сохраняют длину, ${\displaystyle T[n]}$ как набор фиксируется ${\displaystyle {\text{Aut}}(T_{2})}$ для всех ${\displaystyle n\geqslant 0.}$ Имея это в виду, мы пишем:

${\displaystyle T_{2}=0\Sigma ^{*}\sqcup T[1]\sqcup 1\Sigma ^{*}.}$

Мы называем ${\displaystyle 0\Sigma ^{*}}$ (соотв. ${\displaystyle 1\Sigma ^{*}}$) левую (соответственно правую) ветвь и обозначим ее ${\displaystyle T_{L}}$ (соотв. ${\displaystyle T_{R}}$). Используя эти обозначения, мы видим, что:

${\displaystyle a(T_{L})\subseteq T_{R},\quad a(T_{R})\subseteq T_{L}.}$

Теперь мы также можем записать действие элементов б, c и d в терминах несвязного объединения следующим образом:

${\displaystyle {\begin{aligned}b:=(a,c)\quad &\Longleftrightarrow \quad b(x)={\begin{cases}a(x)&x\in T_{L}\\c(x)&x\in T_{R}\end{cases}}\\c:=(a,d)\quad &\Longleftrightarrow \quad c(x)={\begin{cases}a(x)&x\in T_{L}\\d(x)&x\in T_{R}\end{cases}}\\d:=({\text{id}},b)\quad &\Longleftrightarrow \quad d(x)={\begin{cases}x&x\in T_{L}\\b(x)&x\in T_{R}\end{cases}}\end{aligned}}}$

Аналогично у нас есть:

${\displaystyle aba=(c,a),\quad aca=(d,a),\quad ada=(b,{\text{id}}).}$

Характеристики

Ниже приведены основные алгебраические свойства группы Григорчука (см.^[17] для доказательств):

• Группа грамм бесконечно.^[2]
• Группа грамм является финитно аппроксимируемая.^[2] Позволять ${\displaystyle \rho _{n}:G\to {\text{Aut}}(T[n])}$ - гомоморфизм ограничения, переводящий каждый элемент грамм к его ограничению на конечное дерево Т[п]. Группы Aut (Т[п]) конечны и для любого нетривиального грамм в грамм Существует п такой, что ${\displaystyle \rho _{n}(g)\neq 1.}$
• Группа грамм генерируется а и любые два из трех элементов б, в, г. Например, мы можем написать ${\displaystyle G=\langle a,b,c\rangle .}$
• Элементы а, б, c, d находятся инволюции.
• Элементы б, c, d попарно коммутируют и до н.э = cb = d, bd = db = c, Округ Колумбия = CD = б, так что ${\displaystyle \langle b,c,d\rangle \leqslant G}$ является абелева группа порядка 4 изоморфный к прямой продукт из двух циклические группы порядка 2.
• Комбинируя два предыдущих свойства, мы видим, что каждый элемент грамм можно записать как (положительное) слово в а, б, c, d такое, что это слово не содержит подслов вида аа, bb, cc, дд, CD, Округ Колумбия, до н.э, cb, bd, db. Такие слова называются уменьшенный.
• Группа грамм это 2-группа, то есть каждый элемент в грамм имеет конечный порядок это степень двойки.^[1]
• Группа грамм имеет промежуточный рост.^[2]
• Группа грамм является послушный но нет элементарный поддающийся.^[2]
• Группа грамм является просто бесконечно, то есть грамм бесконечно, но каждый правильный факторгруппа из грамм конечно.
• Группа грамм имеет свойство подгруппы конгруэнции: подгруппа ЧАС имеет конечный индекс в грамм тогда и только тогда, когда есть положительное целое число п такой, что ${\displaystyle \ker(\rho _{n})\leqslant H.}$
• Группа грамм имеет решаемый проблема членства в подгруппе, то есть существует алгоритм, который по произвольным словам ш, ты₁, ..., ты_п решает, стоит ли ш представляет собой элемент подгруппы, порожденной ты₁, ..., ты_п.^[18]
• Группа грамм является подгруппа отделимая, т.е. каждая конечно порожденная подгруппа замкнута в проконечная топология на грамм.^[18]
• Каждый максимальная подгруппа из грамм имеет конечный индекс в грамм.^[19]
• Группа грамм конечно порожден, но не конечно презентабельный.^[2][20]
• В стабилизатор вершин первого уровня в ${\displaystyle T_{2}}$ в грамм (подгруппа элементов, которые действуют как тождества для строк 0 и 1), генерируется следующими элементами:

${\displaystyle G_{\{0,1\}}=\langle b,c,d,aba,aca,ada\rangle .}$

${\displaystyle G_{\{0,1\}}}$ это нормальная подгруппа из индекс 2 в грамм и

${\displaystyle G=G_{\{0,1\}}\sqcup aG_{\{0,1\}}.}$

• Сокращенное слово представляет собой элемент ${\displaystyle G_{\{0,1\}}}$тогда и только тогда, когда это слово включает четное число вхождений а.
• Если ш сокращенное слово в грамм с положительным четным числом вхождений ато есть слова ты, v (не обязательно уменьшенное), такое, что:

${\displaystyle w=(u,v)\quad {\text{and}}\quad {\begin{cases}|u|,|v|\leqslant {\tfrac {1}{2}}|w|&|w|{\text{ odd}}\\|u|,|v|\leqslant {\tfrac {1}{2}}(|w|+1)&|w|{\text{ even}}\end{cases}}}$

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

• Группа грамм имеет решаемый проблема со словом и решаемый проблема сопряженности (следствие свойства сжатия).

Смотрите также

• Геометрическая теория групп
• Рост конечно порожденных групп
• Аменабильные группы
• Итерированная группа монодромии
• Некоммутативная криптография

Рекомендации

1. Р. И. Григорчук. К проблеме Бернсайда о периодических группах. Функциональный анализ и его приложения, т. 14 (1980), нет. 1. С. 53–54.
2. Григорчук Р.И., Степени роста конечно порожденных групп и теория инвариантных средних. Известия Академии Наук СССР. Серия Математическая. т. 48 (1984), нет. 5. С. 939–985.
3. Владимир Некрашевич. Самоподобные группы. Математические обзоры и монографии, 117. Американское математическое общество, Провиденс, Род-Айленд, 2005. ISBN  0-8218-3831-8.
4. Джон Милнор, проблема № 5603, Американский математический ежемесячный журнал, т. 75 (1968), стр. 685–686.
5. Джон Милнор. Рост конечно порожденных разрешимых групп. В архиве 2011-05-23 на Wayback Machine Журнал дифференциальной геометрии. т. 2 (1968), стр. 447–449.
6. Джозеф Розенблатт. Инвариантные меры и условия роста, Труды Американского математического общества, т. 193 (1974), стр. 33–53.
7. Григорчук, Р. И. (1983). К проблеме Милнора о групповом росте [О проблеме Милнора роста группы]. Доклады Академии Наук СССР (на русском). 271 (1): 30–33.
8. Лоран Бартольди. Нижние оценки роста группы, действующей на двоичное корневое дерево. Международный журнал алгебры и вычислений, вып. 11 (2001), нет. 1. С. 73–88.
9. Ю. Г. Леонов, О нижней оценке роста 3-образующей 2-группы. Математический сборник, т. 192 (2001), нет. 11. С. 77–92; перевод в: Сборник математики. т. 192 (2001), нет. 11–12. С. 1661–1676.
10. Анна Эршлер, Тяньи Чжэн. «Рост периодических групп Григорчука». Inventiones Mathematicae, т. 219 (2020), № 3, стр. 1069–1155.
11. Махлон М. Дэй. Аменабельные полугруппы. Иллинойсский журнал математики, вып. 1 (1957), стр. 509–544.
12. Владимир Некрашевич, Самоподобные группы. Математические обзоры и монографии, 117. Американское математическое общество, Провиденс, Род-Айленд, 2005. ISBN  0-8218-3831-8.
13. Роман Мучник и Игорь Пак. О росте групп Григорчука. Международный журнал алгебры и вычислений, вып. 11 (2001), нет. 1. С. 1–17.
14. Лоран Бартольди. Рост торсионной группы Григорчука. Уведомления о международных математических исследованиях, 1998 г., № 20. С. 1049–1054.
15. Анна Эршлер. Критические константы повторяемости случайных блужданий по G-пространствам. В архиве 2011-07-25 на Wayback Machine Université de Grenoble. Annales de l'Institut Fourier, vol. 55 (2005), нет. 2. С. 493–509.
16. Джереми Бриессель, Рост определенных групп В архиве 2011-10-02 на Wayback Machine, Докторская диссертация, Парижский университет, 2008.
17. Пьер де ла Харп. Разделы геометрической теории групп. Чикагские лекции по математике. Издательство Чикагского университета, Чикаго. ISBN  0-226-31719-6; Гл. VIII, Первая группа Григорчука, с. 211–264.
18. Р. И. Григорчук, Дж. С. Уилсон. Структурное свойство абстрактной соизмеримости подгрупп. Журнал Лондонского математического общества (2), т. 68 (2003), нет. 3. С. 671–682.
19. Е. Л. Первова, Везде плотные подгруппы группы автоморфизмов деревьев. (на русском). Труды Математического института имени В. А. Стеклова. т. 231 (2000), Дин. Сист., Автомат. я Бескон. Gruppy, стр. 356–367; перевод в: Труды Математического института им. В. А. Стеклова, т. 231 (2000), вып. 4. С. 339–350.
20. И. Г. Лысенок, Набор определяющих соотношений для группы Григорчука. Математические заметки, т. 38 (1985), нет. 4. С. 503–516.

внешняя ссылка

• Ростислав Григорчук и Игорь Пак, Группы среднего роста: введение для начинающих, препринт, 2006, arXiv