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

Группа Григорчука — первый пример конечнопорождённой группы промежуточного роста (то есть её рост быстрее полиномиального, но медленнее экспоненциального).

Пример построен Ростиславом Ивановичем Григорчуком, промежуточный рост доказан им в работе 1984 года. Тем самым был дан ответ на вопрос Милнора, заданный в 1968 году.

Построение

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

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

Бесконечное полное двоичное дерево

Рассмотрим бесконечное полное двоичное корневое дерево Т₂ и его автоморфизмы. Это дерево изоморфно любому своему поддереву, поэтому любой его автоморфизм может быть применён и к любому поддереву.

Каждая вершина дерева Т₂ может быть помечена элементом множества Σ^* всех конечных строк в алфавите Σ = {0,1}, включая пустую строку Ø. Пустая строка Ø соответствует корневой вершине Т₂. Метка левого потомка каждого узла получается добавлением 0, правого — 1.

Любой автоморфизм дерева T₂ сохраняет путь от корневого узла до любого другого и не перемещает ни один узел с одного уровня на другой. Выполнение этих свойств достаточно, чтобы перестановка множества вершин дерева была автоморфизмом дерева. Поэтому группа всех автоморфизмов Aut(Т₂) соответствует группе всех таких перестановок σ множества строк Σ^*, которые сохраняют длину строки (то есть длина x должна равняться длине σ(х)) и сохраняют отношение «начальный сегмент строки» (то есть если строка х является начальным сегментом строки y, то σ(х) является начальным сегментом σ(y)).

Образующие

Группа Григорчука G определяется как подгруппа группы Aut(Т₂), порождённая определёнными четырьмя элементами а, b, с, d, то есть $G=\langle a,b,c,d\rangle <\mathrm {Aut} (T_{2})$.

С точки зрения преобразования строк, состоящих из 0 и 1, автоморфизмы а, b, с, d определяются рекурсивно следующим образом:

• a(0x) = 1x, a(1x) = 0x;
• b(0x) = 0a(x), b(1x) = 1c(x);
• c(0x) = 0a(x), c(1x) = 1d(x);
• d(0x) = 0x, d(1x) = 1b(x)

для каждого x в Σ*. Например:

• a(11101) = 01101
• b(11101) = 1c(1101) = 11d(101) = 111b(01) = 1110a(1) = 11100
• c(11101) = 1d(1101) = 11b(101) = 111c(01) = 1110a(1) = 11100
• d(11101) = 1b(1101) = 11c(101) = 111d(01) = 11101

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

С точки зрения преобразования двоичного дерева элемент a меняет местами левое и правое поддеревья того дерева, на которое он действует. Остальные элементы действуют отдельно на каждое из этих двух поддеревьев, эти элементы могут быть рекурсивно представлены парами (два элемента пары соответствуют действию на левое и правое поддеревья):

• b = (a,c),
• c = (a,d),
• d = (1,b).

Здесь b = (a, c) означает, что b не меняет корень Т₂, действует на левое поддерево как a, а на правое — как c. Здесь 1 обозначает тождественное отображение.

В не рекурсивном представлении действие элементов b, c, d выглядит так: начиная от корня, продвигаемся вниз, выбирая на каждом шаге правого потомка; при этом всякий раз к левому поддереву применяется операция a (меняющая местами два его поддерева), кроме каждого третьего шага, начиная с третьего, второго и первого шага для b, c и d, соответственно.

Свойства образующих

Ниже приведены основные следствия из этого построения.

• Каждый из элементов a, b, c, d имеет порядок 2 в G.
• Элементы b, c, d попарно коммутируют, и bc = cb = d, bd = db = c, dc = dc = b.
  • В частности, $\langle b,c,d\rangle$ — абелева группа порядка 4; она изоморфна прямому произведению двух циклических групп порядка 2.
• Группа G порождается a и любыми двумя из трёх элементов b, c, d (например, $G=\langle a,b,c\rangle$).
• В приведённых выше рекурсивных обозначениях $aba=(c,a),\ aca=(d,a),\ ada=(b,1)$.
• Стабилизатор St_G[1] в G — это подгруппа, порождённая b, c, d, aba, aca, ada. Подгруппа St_G[1] является нормальной подгруппой индекса 2 в G, и

  G = St_G[1] $\sqcup$ a St_G[1].

• Каждый элемент G может быть записан как (положительное) слово из букв a, b, c, d без подслов формы aa, bb, cc, dd, cd, dc, bc, cb, bd, db.
  • Такие слова называются сокращёнными.
  • «Положительное слово» здесь означает, что в соответствующей записи отсутствуют элементы a⁻¹, b⁻¹ и т. д. Поскольку у всех этих образующих порядок равен 2, т. е. они сами себе обратны, то это необременительное условие.
• Сокращённое слово представляет собой элемент из стабилизатора St_G[1] тогда и только тогда, когда это слово включает в себя чётное число вхождений a.
• Если w — сокращённое слово чётной длины с положительным чётным числом появлений a, то есть некоторые слова u, v, записанные через a, b, c, d (не обязательно сокращённые), такие, что в G есть w = (u, v) и |u| ≤ |w|/2, |v| ≤ |w|/2.
  • Если w — сокращённое слово нечётной длины с положительным чётным числом вхождений a, то подобное утверждение тоже верно, но неравенства принимают вид: |u| ≤ (|w| + 1)/2, |v| ≤ (|w| + 1)/2.

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

Свойства

• Группа $G$ бесконечна.
• Группа $G$ является остаточно конечной.
• Группа $G$ является $2$-группой, то есть каждый элемент в $G$ имеет конечный порядок, который равен степени $2$.
• Группа $G$ имеет промежуточный рост.
  • В частности, группа $G$ аменабельна.
  • Григорчук доказал, что рост группы $G$, $\gamma (n)$, заключён между $\exp n^{\alpha }$ и $\exp n^{\beta },\ \alpha =1/2,\ \beta =\log _{32}31\approx 0{,}991$.
  • В 1998 году Бартольди снизил показатель $\beta$ верхней границы с $\log _{32}31$ до

  $\beta ={\frac {\log 2}{\log 2/{\eta }}}\approx 0{,}7674$,

  где $\eta$ — действительный корень многочлена $P=x^{3}+x^{2}+x-2$.

  • В 2011 году Бартольди и Эршлер определяют многочлен $Q=-x^{3}P(2/x)/2$, $Q=x^{3}-x^{2}-2x-4$, единственным вещественным корнем которого является $2/\eta$.
  • В 2018 году Эршлер и Жэнь нашли точное предельное значение показателя степени $n$ в показателе экспоненты в $\gamma (n)$

  $\lim _{n\to \infty }{\frac {\log \log \gamma (n)}{\log n}}=\alpha _{0}={\frac {\log 2}{\log {\lambda }}}\approx 0.7674$,

  где $\lambda$ — действительный корень многочлена $Q=x^{3}-x^{2}-2x-4$; то есть предельная нижняя граница $\alpha _{0}$ совпадает с верхней границей $\beta$.

• Каждая факторгруппа $G$ по нетривиальной нормальной группе конечна.
• Каждая конечно порождённая подгруппа замкнута в про-конечной топологии на $G$.
• Каждая максимальная подгруппа в $G$ имеет конечный индекс.
• Группа $G$ конечно порождённая, но не конечно заданная.
• Централизатор элемента конечно порожден тогда и только тогда, когда элемент сопряжен с порождающим элементом $a$.
• Индексы членов нижнего центрального ряда ограничены сверху числом 4.
• Найдены примеры максимальных локально конечных подгрупп, они оказались бесконечными.

См. также

• АТ-группа
• Аменабельная группа
• Геометрическая теория групп
• Степень роста группы