Группа Григорчука

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

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

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

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

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

Нижняя граница $\exp(n^{0.504})$ was proved by Yurii Leonov . Точная асимптотика роста G пока неизвестна. Предполагается, что предел

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

существует, но даже это остается серьезной открытой проблемой. Эту проблему решили в 2020 году Эршлер и Чжэн. Они показывают, что предел равен $s$.

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

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

После статьи Григорчука 1984 года было много последующих расширений и обобщений.

Определение

Бесконечное двоичное дерево T ₂ . Его узлы помечены строками из 0 и 1.

Хотя первоначально группа Григорчука определялась как группа сохраняющих меру преобразований единичного интервала Лебега , в настоящее время эту группу обычно задают ее реализацией как группы автоморфизмов бесконечного регулярного бинарного корневого дерева   T ₂ . Дерево T ₂ — это множество Σ ^* всех конечных строк в алфавите Σ = {0,1} , включая пустую строку   ∅ , которая является корнем T ₂ . Для вершины x из T ₂ строка x 0 является левым дочерним элементом x , а строка x 1 является правым дочерним элементом x в T ₂ . Таким образом, группу всех автоморфизмов Aut( T ₂ ) можно рассматривать как группу всех сохраняющих длину перестановок   σ группы Σ ^* которые также соблюдают отношение начального сегмента : всякий раз, когда строка x является начальным сегментом строки y , тогда σ( x ) является начальным сегментом σ( y ) .

Группа Григорчука   G — это подгруппа Aut ( T ₂ ), четырьмя конкретными элементами Aut( T ₂ ) определяемыми следующим образом (заметим, что ∅ фиксируется порожденная любым , древесным автоморфизмом): $$G=\langle a,b,c,d\rangle \leq {\text{Aut}}(T_{2}){\text{,}}$$ где $$a(0)=1{\text{,}}\qquad a(1)=0{\text{,}}\qquad \forall x\in \Sigma ^{*}\quad {\begin{cases}a(0x)=1x\\a(1x)=0x\end{cases}}$$ и $${\begin{aligned}&b(0)=c(0)=d(0)=0\\&b(1)=c(1)=d(1)=1{\text{,}}\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){\text{.}}\end{cases}}\end{aligned}}$$

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

Только элемент a определен явно; он меняет местами дочерние деревья ∅ . Элементы b , c и d определяются посредством взаимной рекурсии .

Чтобы понять эффект последних операций, рассмотрим самую правую ветвь B T } ₂ , которая начинается с {∅, 1, 11, 111, ... . ветвь B порядково изоморфна Как $\mathbb {N} .$ Исходное дерево T ₂ можно получить, укоренив дерево, изоморфное T _2, в каждом элементе B ; и наоборот, можно разложить T ₂ на изоморфные поддеревья, индексированные элементами $B\cong \mathbb {N}$.

Все операции b , c и d учитывают это разложение: они фиксируют каждый элемент B и действуют как автоморфизмы на каждом индексированном поддереве. Когда действует b , он фиксирует каждое поддерево с индексом ≡ 2 (mod 3) , но действует как a на остальных. Аналогично, когда действует c , он фиксирует только поддеревья индекса ≡ 1 (mod 3) ; и d фиксирует индекс ≡ 0 (mod 3) .

Компактное обозначение этих операций следующее: пусть левая (соответственно правая) ветвь T ₂ равна T _L = 0Σ. ^* (соответственно T _R = 1Σ ^* ), так что $$a(T_{L})\subseteq T_{R},\quad a(T_{R})\subseteq T_{L}{\text{.}}$$ Мы пишем f = ( g , h ), чтобы обозначить, что f действует как g на T _L и как h на T _R . Таким образом $${\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}{\text{.}}\end{cases}}\end{aligned}}$$ Сходным образом $$aba=(c,a),\quad aca=(d,a),\quad ada=(b,{\text{id}}){\text{,}}$$ где id — тождественная функция .

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

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

• Группа G бесконечна.
• Группа G аппроксимируемо конечна . Позволять $\rho _{n}:G\to {\text{Aut}}(T[n])$ — гомоморфизм ограничения, который переводит каждый элемент G в ограничение на первые n уровней T ₂ . Группы Aut( T [ n ]) конечны и для любого нетривиального g из G существует n такое, что $\rho _{n}(g)\neq 1.$
• Группа G порождается a и любыми двумя из трех элементов b,c,d . Например, мы можем написать $G=\langle a,b,c\rangle .$
• Элементы a , b , c , d являются инволюциями .
• Элементы b , c , d попарно коммутируют и bc = cb = d , bd = db = c , dc = cd = b , так что $\langle b,c,d\rangle \leqslant G$ — абелева группа порядка 4, изоморфная прямому произведению двух циклических групп порядка 2.
• Объединив два предыдущих свойства, мы видим, что каждый элемент G можно записать как (положительное) слово в a , b , c , d такое, что это слово не содержит подслов вида aa , bb , cc , dd , cd. , dc , bc , cb , bd , db . Такие слова называются редуцированными .
• Группа G является 2-группой , то есть каждый элемент в G имеет конечный порядок , равный степени 2.
• Группа G периодична (как 2-группа) и не локально конечна (поскольку она конечно порождена). По существу, это контрпример к проблеме Бернсайда .
• Группа G имеет промежуточный рост.
• Группа G аменабельна , но не элементарно аменабельна .
• Группа G , просто бесконечна то есть G бесконечна, но каждая собственная G конечна факторгруппа .
• Группа G обладает свойством конгруэнтной подгруппы : подгруппа H имеет конечный индекс в G тогда и только тогда, когда существует целое положительное число n такое, что $\ker(\rho _{n})\leqslant H.$
• Группа G имеет разрешимую проблему членства в подгруппе , то есть существует алгоритм, который по произвольным словам w , u ₁ , ..., un _решает , представляет ли w элемент подгруппы, порожденной u ₁ , .. ., ты _н .
• Группа G подгруппово отделима т. е. каждая конечно порожденная подгруппа замкнута в проконечной топологии на G. ,
• Каждая максимальная подгруппа группы G имеет конечный индекс в G .
• Группа G конечно порождена, но не конечно представима .
• Стабилизатор в вершин первого уровня $T_{2}$ в G (подгруппа элементов, которые действуют как тождества в строках 0 и 1), генерируется следующими элементами:

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

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

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

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

$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}}$

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

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

См. также

• Геометрическая теория групп
• Рост конечно порожденных групп
• Поддающиеся группы
• Итерированная группа монодромии
• Некоммутативная криптография

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

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