WikiSort.ru - Не сортированное

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

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

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

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

Образующие

Группа Григорчука G определяется как подгруппа группы Aut(Т₂), порождённая определёнными четырьмя элементами а, b, с, d, то есть ${\displaystyle 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

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

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

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

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

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

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

• Каждый из элементов a, b, c, d имеет порядок 2 в G.
• Элементы b, c, d попарно коммутируют, и bc = cb = d, bd = db = c, dc = dc = b.
  • В частности, ${\displaystyle \langle b,c,d\rangle }$ — абелева группа порядка 4; она изоморфна прямому произведению двух циклических групп порядка 2.
• Группа G порождается a и любыми двумя из трёх элементов b, c, d (например, ${\displaystyle G=\langle a,b,c\rangle }$ ).
• В приведённых выше рекурсивных обозначениях ${\displaystyle 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] ${\displaystyle \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.

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