В. С. Губа, “Группа Р. Томпсона $F$ и проблема аменабельности”, УМН, 77:2(464) (2022), 69–122; Russian Math. Surveys, 77:2 (2022), 251

Аннотация: В центре внимания данной работы находится группа Ричарда Томпсона $F$, открытая в 60-х годах прошлого века. Ей посвящено большое число работ. Нас интересует в первую очередь знаменитая проблема аменабельности этой группы, поставленная Россом Гейганом в 1979 г. Предпринимались многочисленные попытки решить её как в том, так и в другом направлении, но она остаётся открытой.
В данном обзоре мы излагаем наиболее важные известные свойства этой группы, касающиеся проблемы слов, представления элементов группы кусочно линейными функциями, а также диаграммами и другими геометрическими объектами. Излагаются классические результаты М. Брина и К. Сквайера, касающиеся свободных подгрупп и тождеств. Мы включили изложение более современных важных результатов, относящихся к свойствам графов Кэли (конструкция Белка–Брауна), а также теорему Бартольди о свойствах уравнений в групповых кольцах. Отдельно рассматриваются критерии (не)аменабельности групп, полезные для работы по основной проблеме. В конце мы приводим ряд своих результатов о структуре графов Кэли и новом алгоритме решения проблемы слов.
Библиография: 69 названий.

Введение

Данная работа посвящена группе Ричарда Томпсона $F$ и её основным свойствам. На эту тему имеется очень обширная литература, но мы не ставили себе целью осветить хотя бы даже на уровне упоминания все вопросы, касающиеся данной группы. Также мы не описываем здесь обобщений группы $F$. Она нас интересует прежде всего в связи с проблемой аменабельности этой группы. Данная проблема открыта на протяжении уже многих десятилетий, и предпринимались многочисленные попытки её решить как в том, так и в другом направлении.

Скажем несколько слов об истории появления этой группы. Считается, что она возникла в 60-х годах прошлого века в связи с исследованиями Ричарда Томпсона в области $\lambda$-исчисления. В своих неопубликованных заметках Томпсон установил ряд важных свойств этой группы и её обобщений. В современной литературе приняты обозначения трёх из этих групп в виде $F < T < V$. Все эти три группы являются конечно представимыми, а последние две являются простыми. Свойства группы $V$ подробно анализируются в статье Г. Хигмана [53]; см. также [56], где на основе группы $F$ были построены примеры конечно определённых групп с неразрешимой проблемой равенства слов.

Во многих источниках группа $F$ вводится на основе её представления кусочно линейными функциями. Здесь полезно отметить более ранние работы Ч. Г. Чехаты [13] и В. Длаба [19], где рассматривались бесконечно порождённые группы кусочно линейных функций в связи с проблематикой упорядоченных групп. В ходе этого появлялась группа, которая фактически является коммутантом группы $F$; она проста и бесконечно порождена.

Группа $F$ в дальнейшем не раз переоткрывалась разными авторами. См. работы [20], [21], а также [25] на тему гомотопических идемпотентов (современное обозначение $F$ укоренилось, по всей видимости, после этой работы).

Семейство групп $F_r$ ($r\geqslant 2$), где $F=F_2$, было предложено К. С. Брауном [7]. Все они оказались группами диаграмм [45] для полугрупповых копредставлений с одним соотношением $x=x^r$. Эти группы имеют во многом схожую структуру и изоморфно вкладываются друг в друга. В данной статье мы их подробно не анализируем, как и группы $T$, $V$.

Группа $F$ представляет здесь для нас интерес в первую очередь в связи с проблемой её аменабельности. Этот вопрос, открытый по сей день, был поставлен Р. Гейганом [26] в 1979 г.; см. также [27]. Разные авторы предпринимали много попыток решить проблему как в одну сторону, так и в другую. К сожалению, ни одна из них успехом не увенчалась. Отметим, что среди специалистов нет единого убеждения по поводу того, является ли группа $F$, скорее всего, аменабельной или неаменабельной. Интерес подогревается ещё и тем обстоятельством, что имеется масса различных критериев (не)аменабельности, но группа $F$ от них искусно “ускользает”. В частности, если имеется какое-то общее свойство всех аменабельных групп (например, отсутствие в них свободных неабелевых подгрупп), то, как правило, удаётся доказать, что $F$ таким свойством тоже обладает.

Одной из наиболее часто используемых ссылок на типовой набор свойств группы $F$ является статья [11]. Есть также более современные вводные статьи наподобие [10]. На русском языке такого рода обзорных статей фактически не имеется, поэтому мы поставили своей целью восполнение этого пробела. Здесь мы старались дать единое изложение основных свойств группы, а также технических средств, которые позволяют с ней работать (представление кусочно линейными функциями, двоичными деревьями и лесами, диаграммами и т. п.). Критерием отбора материала была в первую очередь связь с проблемой аменабельности. При этом в библиографию включалось не всё, что имеет отношение к теме, а лишь то, на что мы непосредственно ссылаемся. Помимо классических и более современных результатов мы включили (см. раздел 12) изложение новых конструкций, связанных с простым описанием графа Кэли группы (в виде его конечных фрагментов), а также новый алгоритм решения проблемы равенства слов.

Мы полагаем, что данная статья будет полезной для всех, кто интересуется проблемой аменабельности группы $F$, в том числе студентов и аспирантов.

1. Образующие и соотношения

В данном обзоре мы часто будем использовать понятие графа в смысле Серра. Напомним эту концепцию: всякое геометрическое ребро считается состоящим из двух взаимно обратных направленных рёбер. Оно имеет вид $\{e,e^{-1}\}$, где $e^{-1}\ne e$ и $(e^{-1})^{-1}=e$. Более подробно см. [65].

Мы также часто будем рассматривать графы Кэли групп. Если $G$ – группа с системой образующих $A$, то в качестве множества вершин рассматривается $G$. В правом графе Кэли мы с каждым элементом $g\in G$ и образующим $a\in A^{\pm1}$ связываем направленное ребро с меткой $a$, идущее из вершины $g$ в вершину $ga$. Аналогично, в левом графе Кэли мы для каждого $g\in G$ и $a\in A^{\pm1}$ проводим направленное ребро с меткой $a$ из $ag$ в $g$. Меткой пути считается произведение меток проходимых рёбер.

Перейдём к описанию нашего главного объекта рассмотрения – группы Р. Томпсона $F$. В качестве основного определения чаще всего берётся задание её элементов некоторыми кусочно линейными функциями. Мы поступим несколько иначе, предложив комбинаторное определение. Все остальные способы описания этой группы будут получены на его основе.

Рассмотрим счётное множество групповых порождающих

Группа, заданная таким копредставлением, далее будет обозначаться через $F$, а моноид, получаемый этим же способом, – через $M$. Он будет называться моноидом положительных элементов группы. Ниже будет доказано, что $F=MM^{-1}$ есть группа частных данного моноида.

Используя стандартные обозначения для сопряжённых элементов вида $a^b=b^{-1}ab$, мы можем записать соотношения из (1) в виде $x_j^{x_i}=x_{j+1}$.

Имеет смысл сразу же предъявить какие-нибудь естественные объекты, удовлетворяющие данным соотношениям. В качестве таковых рассмотрим кусочно линейные функции, отображающие множество $\mathbb R_+=[0,\infty)$ на себя. Мы будем рассматривать сохраняющие ориентацию прямой (т. е. строго возрастающие) биекции. Все они непрерывны на $\mathbb R_+$ и линейны на каждом из конечного числа промежутков, на которые разбивается положительный луч. Легко видеть, что все такие функции образуют группу относительно композиции отображений, обозначаемую далее через $\operatorname{PLF}(\mathbb R_+)$.

Для каждого целого $n\geqslant 0$ определим функцию $f_n$, которая тождественна на $[0,n]$, имеет угловой коэффициент $2$ на $[n,n+1]$, а на оставшейся части луча имеет угловой коэффициент $1$. Ввиду того, что мы будем рассматривать композицию слева направо, нам удобно рассматривать правостороннюю функциональную запись, т. е. писать $(x)f$ или $xf$ вместо $f(x)$. Таким образом,

Легко проверяется, что данные функции удовлетворяют тождественным соотношениям вида $f_jf_i=f_if_{j+1}$ при всех $j > i\geqslant 0$. Этим доказана следующая лемма.

Ниже будет показано, что данный гомоморфизм является изоморфным вложением. Также мы опишем образ группы $F$ при этом гомоморфизме.

Из леммы 1.1 можно сразу получить алгоритм решения проблемы равенства слов в группе $F$. Пусть дано групповое слово $w$ в алфавите $X$. Можно считать его циклически приведённым и непустым. Рассмотрим минимальное $i\geqslant 0$, для которого буква вида $x_i^{\pm1}$ входит в запись слова $w$. Утверждается, что если $w$ представляет единичный элемент группы $F$, то алгебраическая сумма показателей степеней при $x_i$ в слове $w$ равна нулю. Действительно, слово $w$ в представлении функциями задаёт тождественное на $[0,i]$ отображение. В правой окрестности точки $t=i$ угловые коэффициенты для функций вида $f_j$ равны $1$ при $j > i$; для $f_i$ угловой коэффициент равен $2$, а для $f_i^{-1}$ он равен $1/2$. Ввиду того, что угловые коэффициенты произведения перемножаются, мы получаем в результате число $1$, а это значит, что число вхождений $x_i$ равно числу вхождений $x_i^{-1}$. Подытожим это рассуждение в виде леммы.

Легко понять, что приведённость слова в данном случае роли не играет, так как при свободных сокращениях в группе алгебраическая сумма показателей при данной букве не меняется.

Теперь покажем, как на основе леммы 1.2 решается проблема слов в группе $F$. Рассмотрим непустое циклически приведённое слово $w$ над $X^{\pm1}$, для которого число $i\geqslant 0$ есть минимальный индекс входящих в него букв. Это слово можно записать в виде $w=u_0x_i^{k_1}u_1x_i^{k_2}u_2\ldots x_i^{k_m}u_m$, где слова $u_j$ ($0\leqslant j\leqslant m$) являются произведениями букв алфавита $X^{\pm1}$ с индексами, строго большими $i$. Можно считать, что $k_1+\cdots+k_m=0$: в противном случае мы уже знаем, что слово $w$ не равно $1$ в группе $F$. Рассмотрим числа $k_1,k_1+k_2,\dots,k_1+\cdots+k_m$ и выберем среди них максимальное. Пусть оно достигается для суммы $k_1+\cdots+k_j$. Рассмотрим циклический сдвиг слова $w$, начиная читать его после слова $u_j$. Вводя переобозначения, записываем этот сдвиг в виде $w'=x_i^{l_1}v_1x_i^{l_2}v_2\ldots x_i^{l_m}v_m$, где по построению выполняются неравенства $l_1+\cdots+l_s\leqslant 0$ для всех $1\leqslant s\leqslant m$ (последняя из сумм равна нулю).

Положим $p_s=-(l_1+\cdots+l_s)\geqslant 0$. Тогда слово $w'$ можно записать в виде $(x_i^{-p_1}v_1x_i^{p_1})(x_i^{-p_2}v_2x_i^{p_2})\ldots (x_i^{-p_m}v_mx_i^{p_m})$. Легко видеть, что в силу определяющих соотношений (1) слово вида $x_i^{-p}x_jx_i^p$ будет равно $x_{j+p}$ при $j > i$, $p\geqslant 0$. Также в $F$ будет иметь место равенство для обратных элементов, т. е. $x_i^{-p}x_j^{-1}x_i^p=x_{j+p}^{-1}$, и то же для любых произведений символов с индексами, большими $i$.

Обозначая через $[u]_p$ для любого слова $u$ над $X^{\pm1}$ слово, получаемое увеличением всех нижних индексов на величину $p\geqslant 0$, мы видим, что $w'$ равно в $F$ слову $[v_1]_{p_1}\ldots[v_m]_{p_m}$, длина которого строго уменьшилась. Далее его циклически приводим и снова находим минимальный индекс при буквах. Если для него алгебраическая сумма показателей не равна нулю, то исследуемое слово $w$ не равно $1$ в $F$. Если сумма равна нулю, то повторяем описанную выше процедуру. Длина всё время уменьшается, и мы за конечное число шагов либо получим слово с суммой показателей, отличной от нуля, либо придём к пустому слову. Последнее будет означать, что $w=1$ в $F$. Таким образом, доказана следующая лемма.

Легко понять, что сложность описанного выше алгоритма квадратично зависит от длины исследуемого слова. Ниже мы рассмотрим ещё несколько алгоритмов для этой же цели, а сейчас докажем, что группа $F$ может быть задана конечным копредставлением с двумя образующими и двумя определяющими соотношениями.

Из (1) следует, что $x_2=x_1^{x_0}$, $x_3=x_2^{x_0}$ и т. д., т. е. группа порождена элементами $x_0$, $x_1$. Это множество порождающих принято называть стандартным. Остальные буквы выражаются в виде $x_n=x_1^{x_0^{n-1}}$ при $n\geqslant 2$. Рассматривая конечное множество образующих $\{x_0,x_1\}$, принимаем данные равенства для $x_2,x_3,\ldots$ за определения.

Для доказательства заметим, что достаточно вывести все соотношения вида $x_n^{x_1}=x_{n+1}$ при $n\geqslant 2$. Из них будут следовать остальные равенства, так как соотношение $x_j^{x_i}=x_{j+1}$ получается из предыдущего для $n=j-i+1$ при помощи сопряжения элементом $x_0^{i-1}$ (здесь $i\geqslant 1$, так как случай $i=0$ представляет собой определение). Проводим индукцию по $n$, считая, что $n\geqslant 4$, так как при $n=2$ и $n=3$ соотношения даны в условии. Имеем

Определяющие соотношения из леммы 1.4 имеют длину $10$ и $14$ соответственно. Обратим внимание на другое полезное конечное копредставление группы с пятью порождающими $x_0,x_1,\dots,x_4$ и пятью определяющими соотношениями

Выше было показано, каким образом можно вывести некоторые соотношения в группе $F$ из определяющих. Для слова данной длины $n$, равного единице в $F$, всегда имеется кратчайший вывод в смысле числа применяемых при этом определяющих соотношений. На этом пути возникает понятие функции Дэна группы. Мы не будем здесь приводить серии необходимых определений. Скажем только, что для группы $F$ в серии работ [44], [36] оценка функции Дэна несколько раз улучшалась, а в [39] было окончательно доказано, что она квадратична. По смыслу это означает, что всякое слово длины $n$, равное единице в $F$, можно вывести за $O(n^2)$ шагов из определяющих соотношений конечного (ко)представления группы.

Здесь также можно упомянуть работу [8], в которой было установлено (на гомологическом языке) одно важное свойство группы $F$, которое в упрощённом пересказе состоит в том, что $F$ имеет два базисных образующих в любой размерности. Иными словами, имеется два образующих, два определяющих соотношения, два базисных сферических соотношения (т. е. соотношения между соотношениями) и т. д.

Коль скоро мы затронули вопрос о конечных (ко)представлениях группы, имеет смысл обратить внимание ещё на один полезный способ задать группу $F$. Нетрудно проверить, что правило $x_0\mapsto x_0^{-1}$, $x_1\mapsto x_1x_0^{-1}$ задаёт эндоморфизм группы $F$, так как определяющие соотношения из леммы 1.4 переходят в соотношения. Также ясно, что квадрат рассматриваемого эндоморфизма есть тождественное отображение. Поэтому мы имеем дело с (внешним) автоморфизмом группы $F$. Полагая $\overline{x}_1=x_1x_0^{-1}$, мы получаем “симметричный” для $x_1$ элемент, который вместе с ним порождает $F$, так как $x_0$ через них выражается. Приведём без доказательства вид определяющих соотношений группы в симметричном множестве порождающих $\{x_1,\overline{x}_1\}$. Введём обозначения $\alpha$ и $\beta$ для $x_1^{-1}$ и $\overline{x}_1^{\,-1}$ соответственно. Через $a\leftrightarrow b$ будем обозначать соотношение коммутативности $ab=ba$. В нашем случае для любых натуральных $m$, $n$ в группе выполняются соотношения $\alpha^{\beta^m}\leftrightarrow\beta^{\alpha^n}$. Если мы возьмём случай $m=n=1$, а также $m=1$, $n=2$, то получим задание группы $F$ в симметричном множестве образующих. Доказательство основано на применении преобразований Тице.

2. Нормальные формы

Опишем разные способы получения нормальной формы элементов группы $F$. Для начала рассмотрим положительное слово, являющееся произведением букв алфавита $X=\{x_i\mid i\geqslant 0\}$. Если слово $w$ содержит подслово вида $x_jx_i$, где $j > i$, то заменяем его на $x_ix_{j+1}$, применяя определяющее соотношение. Длина слова при этом не меняется, но слово уменьшается в лексикографическом порядке относительно $x_0 < x_1 < \cdots < x_n < \cdots$ . За конечное число шагов мы получаем нормальную форму положительного элемента, записываемую в виде $x_{i_1}\dots x_{i_m}$, где $i_1\leqslant \cdots\leqslant i_m$. Эквивалентным образом можно записать положительное слово в виде $x_{j_1}^{k_1}\dots x_{j_r}^{k_r}$, где $j_1 < \cdots < j_r$ и $k_1,\dots,k_r\geqslant 1$.

Для начала проверим, что всякий элемент группы $F$ можно представить в виде $pq^{-1}$, где $p$, $q$ – положительные слова. Это делается индукцией по длине слова над $X^{\pm1}$, представляющего данный элемент. Достаточно домножать слово вида $pq^{-1}$ на $x_i$ или $x_i^{-1}$. Второй случай очевиден, так как ведёт к слову $p(x_iq)^{-1}$.

В первом случае достаточно научиться представлять элемент $q^{-1}x_i$ в виде произведения положительного и отрицательного слова. Проводим индукцию по длине слова $q$. Если оно пустое, то всё очевидно. В противном случае полагаем $q=x_kr$, где $x_k$ – первая буква. При $k=i$ происходит сокращение и мы имеем слово $r^{-1}$. Пусть $k < i$. Тогда, в силу определяющих соотношений, $q^{-1}x_i=r^{-1}x_k^{-1}x_i=r^{-1}x_{i+1}\cdot x_k^{-1}$, и слово $r^{-1}x_{i+1}$ преобразуется к нужному виду по предположению индукции. Получается произведение положительного и отрицательного слова. Пусть теперь $k > i$. Здесь $q^{-1}x_i=r^{-1}x_k^{-1}x_i=r^{-1}x_i\cdot x_{k+1}^{-1}$, что также позволяет сослаться на предположение индукции.

Итак, мы можем любой элемент представить в виде $pq^{-1}$ или, более подробно, как

Данное ограничение как раз и означает невозможность применения того вида сопряжения, о котором шла речь выше. Частным случаем данного условия является то, что $i_s\ne j_t$, т. е. форма (2) приведена. Существование представления мы доказали выше; осталось проверить единственность.

Рассуждая от противного, предположим, что один и тот же элемент группы представим в виде нормальной формы из условия леммы двумя различными способами: $p_1q_1^{-1}=p_2q_2^{-1}$, где слова $p_1$, $p_2$, $q_1$, $q_2$ положительны. Равенство имеет место в группе $F$, но слова в левой и правой части отличаются. Выберем минимальный контрпример в смысле суммы длин слов в той и другой части.

Обозначим через $i$ минимальный индекс, который встречается в записи слов. Ясно, что с буквы $x_i$ не могут начинаться сразу оба слова $p_1$, $q_1$: в противном случае на неё можно сократить. По этой же причине $q_1^{-1}$, $q_2^{-1}$ не могут одновременно оканчиваться буквой $x_i^{-1}$.

Согласно лемме 1.2 алгебраические суммы показателей степеней при $x_i$ для обеих частей должны быть одинаковы. Если они принимают положительное значение, то $x_i$ входит в запись той и другой части, что невозможно. Аналогично для отрицательных значений. Поэтому суммы показателей степеней там и там равны нулю. Отсюда следует, что мы имеем равенство вида $x_i^kp_3q_3^{-1}x_i^{-k}=p_2q_2^{-1}$, где $k\geqslant 1$, и в запись слов $p_2$, $q_2$, $p_3$, $q_3$ буквы $x_i^{\pm1}$ уже не входят. Из ограничения в формулировке леммы следует, что $x_{i+1}$ входит в запись хотя бы одного из слов $p_3$, $q_3$.

Сопрягая степенью элемента $x_i$, мы приходим в группе $F$ к равенству $p_3q_3^{-1}=[p_2]_k[q_2]_k^{-1}$, где сумма длин слов левой и правой части уменьшилась на $2k$, а все индексы букв в правой части увеличились на $k$. Для слов $p_2$, $q_2$ они уже были не меньше $i+1$, а теперь стали не меньше $i+2$. В левой же части, как мы видели, присутствует индекс $i+1$, что даёт различные слова в нормальной форме и тем самым противоречит минимальности контрпримера. Лемма доказана.

Теперь всё готово для доказательства инъективности гомоморфизма представления элементов $F$ кусочно линейными функциями.

Для доказательства от противного рассмотрим неединичный элемент $g\in F$, переходящий в тождественную функцию. По лемме 2.1 этот элемент $g$ записывается нормальной формой вида $pq^{-1}$, где хотя бы одно из слов $p$, $q$ непусто. Как и выше, выбираем контрпример минимальной длины, обозначая через $i$ наименьший из индексов, встречающийся в записи слов. Ясно, что буквы $x_i$ и $x_i^{-1}$ одновременно входить в запись не могут, так как при сопряжении получится более короткий нетривиальный элемент ядра. Переходя при необходимости к обратному элементу, можно считать, что $x_i$ входит в запись $p$. Тогда функция $f$, в которую переходит $g$, тождественна на отрезке $[0,i]$, а в правой окрестности точки $i$ угловой коэффициент больше единицы (он равен $2^k$, если $x_i$ входит в $p$ в степени $k\geqslant 1$). Пришли к противоречию.

В самом деле, если функция $f\in\operatorname{PLF}(\mathbb R_+)$ не тождественна, то существует наибольшее $a\geqslant 0$ такое, что $f$ тождественна на $[0,a]$. В правой окрестности точки $a$ функция имеет вид $f(x)=k(x-a)+a$, где $k\ne 1$. Тогда для любого натурального $n$ в достаточно малой правой окрестности той же точки имеет место тождество $f^n(x)=k^n(x-a)+a$, причём $k\ne 1$. Следовательно, $n$-я степень $f$ (относительно композиции) не является тождественной, т. е. $\operatorname{PLF}(\mathbb R_+)$ не имеет кручения. Значит, $F$ также не имеет кручения.

Нормальные формы элементов из леммы 2.1 весьма удобны для вычислений в группе, однако они не обладают свойством “локальности”. Для проверки того, что слово представляет собой нормальную форму, следует проверять подслова вида $x_i\ldots x_i^{-1}$, следя за тем, чтобы между этими буквами встречалась буква вида $x_{i+1}^{\pm1}$. В работе [44] построены примеры нормальных форм элементов группы $F$ как для бесконечного множества образующих, так и для конечного. Первые из них обладают свойством локальности в том смысле, что если все подслова длины $2$ являются нормальными формами, то это же верно для самих слов. Приведём без доказательства формулировки обеих теорем.

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

Из этой конструкции получается нормальная форма второго вида, над алфавитом $\{x_0,x_1\}$, обладающая свойством регулярности в смысле теории формальных языков. Хотя слова этого языка не обладают свойством геодезичности (т. е. не дают слова минимально возможной длины), данная нормальная форма позволяет оценивать функцию роста группы $F$ в стандартном множестве образующих. Заметим, что рост группы экспоненциален, что является следствием наличия свободной подполугруппы, порождённой элементами $x_0$, $x_1$. Из свойств нормальной формы для положительных элементов легко выводится, что все положительные слова от этих образующих дают попарно различные элементы.

Более сильный результат о функции роста получен в работе автора [38]. А именно, показатель роста группы в стандартных образующих не меньше $(3+\sqrt5\,)/2$. Есть не доказанная на данный момент гипотеза (см. [22]), что это значение является точным.

Что касается второй нормальной формы из [44], то приведём её описание в кратком виде.

В качестве следствия утверждения о нормальных формах приведём ещё один простой, но важный результат. Легко видеть, что правило $x_i\mapsto x_{i+1}$ ($i\geqslant 0$) задаёт эндоморфизм группы $F$, так как соотношения переходят в соотношения.

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

Из сказанного следует, что группа $F$ изоморфно отображается при $\psi$ на подгруппу $H$, порождённую элементами вида $x_i$ при $i\geqslant 1$. Это позволяет применить конструкцию $\operatorname{HNN}$-расширения при помощи проходной буквы $t$, полагая $t^{-1}x_it=\psi(x_i)=x_{i+1}$ для всех $i\geqslant 0$. Получаемые соотношения с точностью до переобозначения задают группу $F$, так как $t$ играет роль $x_0$, и букве $x_i$ в новом (ко)представлении соответствует $x_{i+1}$ в старом. Такое свойство делает группу $F$ в некотором роде “уникальной”, поскольку она может быть описана в терминах гомотопических идемпотентов. В таком качестве она была переоткрыта в работах Е. Дыдака, П. Фрейда и А. Хеллера в конце 1970-х годов. См. по этому поводу статью [7], где среди прочего показано, что $F$ является в некотором смысле “универсальной” группой относительно свойства наличия эндоморфизма $\psi$, сопряжённого своему квадрату.

Заканчивая данный раздел, приведём важный результат о гомоморфных образах группы $F$. Она в этом смысле близка по своим свойствам к простым группам. А именно, всякая неединичная нормальная подгруппа группы $F$ содержит её коммутант.

Этот факт играет полезную роль в нахождении различных изоморфных представлений группы $F$ и в доказательстве мономорфности тех или иных отображений. А именно, если имеется гомоморфизм из $F$ в какую-то группу, то достаточно проверить, что образ неабелев. Тогда он изоморфен самой группе $F$. Этим способом можно строить многочисленные копии группы $F$ внутри самой себя.

Отметим здесь попутно, что вопрос о том, какие подгруппы $F$ содержат копию всей группы $F$, представляет самостоятельный интерес. В этом смысле, полезное достаточное условие имеется в работе [5], а в [47] предложен соответствующий критерий в терминах групп диаграмм.

Для доказательства достаточно взять любой неединичный элемент группы, представленный нормальной формой $pq^{-1}$, и доказать, что его нормальное замыкание содержит элемент $x_1x_2^{-1}$. Последнее равносильно соотношению коммутативности образующих $x_0$ и $x_1$ в факторгруппе.

Удобно рассуждать на языке соотношений, добавляя к списку новое соотношение $p=q$ и выводя из него как следствие то, что $x_1=x_2$. Если слова начинаются одной и той же буквой, то на неё можно сократить, получая более короткое соотношение. Пусть $x_i$ – буква с наименьшим индексом, которая встречается в записи слов. Тогда можно считать, что $p$ имеет вид $x_i^kr$, где $k\geqslant 1$, и слова $r$, $q$ не содержат букв с индексами $\leqslant i$. Значит, мы имеем соотношение вида $x_i^k=v(x_{i+1},x_{i+2},\dots)$ для некоторого группового слова. Сопрягая элементом $x_i$, мы выводим отсюда соотношение $x_i^k=v(x_{i+2},x_{i+3},\dots)$. Слово в правой части при сопряжении как элементом $x_i$, так и элементом $x_{i+1}$ увеличивает все индексы на единицу. Поэтому оно коммутирует с $x_ix_{i+1}^{-1}$. Следовательно, $x_i^k$ коммутирует с этим же элементом, а потому и с $x_{i+1}$. Тогда $x_{i+1}=x_{i+1}^{x_i^k}=x_{i+k+1}$. Сопрягая $x_0^{-i}$, приходим к равенству $x_1=x_{k+1}$. Сопрягая далее несколько раз элементом $x_1^{-1}$, получаем $x_1=x_2$, что и требовалось.

3. Деревья и леса

В этом и следующем разделах мы рассмотрим форму представления элементов группы $F$ при помощи геометрических объектов – таких как корневые двоичные деревья (а также леса) и полугрупповые диаграммы. Начнём с серии определений.

Корневые двоичные деревья (к.д.д.) можно определить как формально, так и геометрически. Формальные выражения определяем индуктивно:

(b) если $T_1$ и $T_2$ – корневые двоичные деревья, то выражение $(T_1 \widehat{\ }\,T_2)$ также является к.д.д.;

С геометрической точки зрения мы имеем следующее. Дерево из пункта (a) изображается в виде точки; она считается корнем данного дерева. Для дерева из пункта (b) сначала изображаем объединение двух отрезков $AB$ и $AC$, идущих из вершины $A$, считающейся корнем данного дерева, влево вниз и вправо вниз соответственно. Такую фигуру мы называем кареткой. Далее к вершинам $B$ и $C$ присоединяем изображения деревьев $T_1$ и $T_2$ соответственно, располагая в них корни этих деревьев, чтобы при этом присоединяемые деревья не пересекались.

Каждое к.д.д. обладает листьями, т. е. вершинами, расположенными снизу. Для дерева из пункта (a), называемого далее пустым или тривиальным, единственный лист совпадает с корнем. Для к.д.д. из пункта (b) множество листьев есть объединение множеств листьев для $T_1$ и $T_2$.

Легко видеть (по индукции), что дерево с $n\geqslant 0$ каретками имеет $n+1$ лист. Из курса перечислительной комбинаторики известно, что количество таких деревьев есть $n$-е число Каталана

Корневой двоичный лес определяется как конечная последовательность корневых двоичных деревьев: $T_1,\dots,T_m$, где $m\geqslant 1$. Листьями этого леса считаются листья входящих в него деревьев, и они нумеруются натуральными числами слева направо. Из стандартной комбинаторики известно, что количество корневых лесов с общим количеством листьев, равным $n$, также равно $n$-му числу Каталана. Напомним, как осуществляется биекция между лесами и деревьями. Рисуем справа дополнительную вершину (новый лист) и последовательно добавляем каретки, навешивая их на два крайних справа дерева. Это приводит к дереву с $n+1$ листом, т. е. $n$ каретками. Понятно, как можно от дерева перейти обратно к изначальному лесу: нужно удалить те каретки, которые имеют ребро на правой линии дерева, после чего стереть образовавшуюся справа вершину.

Наряду с описанными выше корневыми двоичными лесами полезно рассматривать бесконечные последовательности корневых двоичных деревьев $T_1, T_2,\dots, T_m,\dots$, где все деревья, начиная с некоторого номера, тривиальны. Такие объекты будем называть финитными лесами. Листья этих лесов нумеруем слева направо натуральными числами. На множестве финитных лесов естественным образом задаётся бинарная операция $\circ$, называемая конкатенацией или произведением (в последнем случае знак $\circ$ будем опускать). Устроена она следующим образом. Пусть финитный лес $T$ обозначен, как выше, а финитный лес $S$ задан последовательностью деревьев $S_1,S_2,\dots,S_m,\dots$ . Тогда $T\circ S$ строится следующим образом: для каждого $i\geqslant 1$ к $i$-му листу $T$ присоединяем $i$-е дерево леса $S$. При этом снова получается финитный лес. Легко понять, что операция $\circ$ ассоциативна.

Роль этой конструкции объясняется следующим соображением. Рассмотрим финитный лес $X_i$ для каждого $i\geqslant 0$. Он состоит из одной каретки и тривиальных деревьев, причём каретка расположена так, что перед ней имеется ровно $i$ тривиальных деревьев. Непосредственно проверяется, что для любых $j > i\geqslant 0$ выполнено равенство $X_jX_i=X_iX_{j+1}$, откуда прямо следует, что финитные леса с операцией произведения образуют моноид, изоморфный моноиду $M$ положительных элементов группы $F$.

Единичный элемент задаётся последовательностью тривиальных лесов, для остальных элементов нормальная форма строится по индукции. Берём первое слева нетривиальное дерево, и пусть оно расположено в позиции $i\geqslant 0$, т. е. имеет номер $i+1$, и перед ним имеется ровно $i$ тривиальных деревьев. Тогда первая буква нормальной формы данного леса есть $x_i$, после чего убираем верхнюю каретку с первого слева дерева, получая лес с меньшим числом кареток. Для него по индукции уже известна нормальная форма, и остаётся $x_i$ домножить на неё слева, получая нормальную форму данного леса.

Скажем, если взять лес на рис. 2 и превратить его в финитный, добавляя бесконечное число тривиальных деревьев справа, то получится нормальная форма $x_0^2x_4^2x_6$. Зная нормальную форму, мы можем по описанному принципу нарисовать для неё финитный лес.

Таким образом, финитные леса хорошо описывают положительные элементы группы $F$. Этого достаточно для изучения конечных подграфов графа Кэли всей группы в силу следующих стандартных фактов.

Рассмотрим два финитных леса и “наложим” их деревья друг на друга. Ясно, что, делая это с двумя корневыми двоичными деревьями, мы в качестве “объединения” получаем снова корневое двоичное дерево. То же справедливо и для финитных лесов. Тогда для двух лесов $T$ и $S$ мы имеем равенство вида $T\circ U=S\circ V$, где получаемый новый лес естественно назвать наименьшим общим кратным для $T$ и $S$. Легко проверить, что та же конструкция осуществима для любого конечного набора финитных лесов. Отсюда вытекает следующая лемма.

Действительно, представляя элементы набора нормальными формами вида $g_i=p_iq_i^{-1}$, где $p_i$, $q_i$ – положительные слова ($1\leqslant i\leqslant k$), мы рассматриваем наименьшее общее кратное $q$ для элементов $q_1,\dots,q_k$. Положим $q=q_iu_i$ для некоторых положительных элементов $u_i$ при всех $i$. Тогда $g_i=p_iu_iq^{-1}$ и в качестве $g$ берём элемент $q\in F$.

Понятно, что в левом графе Кэли группы можно осуществить правый сдвиг (домножение справа) на произвольный элемент, и мы получим изоморфный граф. Для правого графа Кэли, что более стандартно для рассмотрения, мы путём левого сдвига помещаем любой конечный подграф в моноид отрицательных элементов $M^{-1}$.

4. Диаграммы

Данный раздел посвящён описанию представления элементов группы $F$ полугрупповыми диаграммами. Более детальная информация на эту тему может быть найдена в [45]. Но здесь мы хотим дать несколько модифицированную версию, основанную на идее представления элементов $F$ при помощи несферических диаграмм. См. на эту тему также [38].

Прежде всего напомним понятие полугрупповой диаграммы и введём ряд обозначений. Для этого рассмотрим следующий пример. Пусть

Это диаграмма $\Delta$ над полугрупповым (ко)представлением ${\mathcal P}$. В данном случае мы имеем плоский размеченный граф с $10$ вершинами, $15$ (геометрическими) рёбрами и $6$ клетками. Каждая клетка соответствует некоторому элементарному преобразованию слова, т. е. переходу вида $p\cdot u\cdot q\to p\cdot v\cdot q$, где $p$, $q$ – слова (возможно, пустые), а $u=v$ или $v=u$ принадлежит списку определяющих соотношений. Диаграмма $\Delta$ имеет крайнюю слева вершину, обозначаемую $\iota(\Delta)$, и крайнюю справа вершину, обозначаемую $\tau(\Delta)$. Она также обладает верхним путём $\mathbf{top}(\Delta)$ и нижним путём $\mathbf{bot}(\Delta)$ из $\iota(\Delta)$ в $\tau(\Delta)$. Каждая клетка $\pi$ диаграммы может быть рассмотрена как отдельная диаграмма. Определённые выше функции $\iota$, $\tau$, $\mathbf{top}$, $\mathbf{bot}$ могут быть также применены к $\pi$. Изотопные диаграммы мы не различаем.

Говорят, что $\Delta$ есть $(w_1,w_2)$-диаграмма, если метка её верхнего пути равна $w_1$ и метка нижнего пути равна $w_2$. В нашем примере мы имеем дело с $(a^5,a)$-диаграммой. Если даны две диаграммы, нижний путь первой из которых имеет ту же метку, что верхний путь второй, то мы можем естественным образом определить конкатенацию этих диаграмм, отождествляя нижний путь первой диаграммы с верхним путём второй. Результатом конкатенации $(w_1,w_2)$-диаграммы и $(w_2,w_3)$-диаграммы, очевидно, будет $(w_1,w_3)$-диаграмма. Мы используем символ $\circ$ для операции конкатенации.

Для любой диаграммы $\Delta$ над ${\mathcal P}$ мы можем рассмотреть её зеркальный образ $\Delta^{-1}$. Диаграмма может содержать так называемые диполи, т. е. поддиаграммы вида $\pi\circ\pi^{-1}$, где $\pi$ – клетка. Под сокращением диполя мы понимаем удаление общей границы $\pi$ и $\pi^{-1}$ с последующей склейкой путей $\mathbf{top}(\pi)$ и $\mathbf{bot}(\pi^{-1})$. В любой диаграмме мы можем последовательно сократить все диполи. Несложно доказывается, что результат не зависит от порядка применения этих операций. Диаграмма называется приведённой, если она не имеет диполей.

Операция сокращения диполей имеет обратную, называемую вставкой диполя. Эти операции индуцируют отношение эквивалентности на множестве диаграмм: две диаграммы называются эквивалентными, если от одной из них можно перейти к другой посредством конечного числа вставок/удалений диполей (в любом количестве и в обе стороны). Каждый класс эквивалентности содержит в точности одну приведённую диаграмму.

Для любого непустого слова $w$ множество всех $(w,w)$-диаграмм образует моноид с нейтральным элементом $\varepsilon(w)$ (диаграммой без клеток). Операция $\circ$ естественным образом индуцирует бинарную операцию на множестве классов эквивалентности диаграмм. Она называется произведением, а эквивалентные диаграммы мы далее именуем равными. Таким образом, классы эквивалентности $(w,w)$-диаграмм образуют группу, которая называется группой диаграмм над полугрупповым (ко)представлением ${\mathcal P}$ с базой $w$. Мы обозначаем её через ${\mathcal D}({\mathcal P},w)$. Её можно представлять себе как группу на множестве всех приведённых $(w,w)$-диаграмм. Групповой операцией является конкатенация с последующим сокращением всех диполей. Обратным элементом диаграммы служит её зеркальный образ.

Под суммой двух диаграмм мы подразумеваем диаграмму, получаемую отождествлением крайней правой вершины первой из диаграмм с крайней левой вершиной второй из них. Эта операция также ассоциативна, хотя не коммутативна. Сумму двух диаграмм $\Delta_1$, $\Delta_2$ обозначаем в виде $\Delta_1+\Delta_2$.

Известно, что группа $F$ является группой диаграмм для простейшего полугруппового (ко)предствления ${\mathcal P}=\langle x\mid x^2=x\rangle$ с базой $x$ (заметим, что для любой другой базы вида $x^k$, где $k\geqslant 1$, получается та же самая группа). Можно сравнить это представление с другими известными способами. Например, в [11] и многих других статьях элементы $F$ задаются в виде упорядоченных пар корневых двоичных деревьев. Если элемент $g\in F$ представлен в виде приведённой $(x,x)$-диаграммы $\Delta$, то соответствующая пара деревьев может быть восстановлена следующим образом. Рассмотрим двойственный граф $\Gamma$ для графа $\Delta$. Вершинами $\Gamma$ служат середины всех рёбер из $\Delta$. Для каждой $(x,x^2)$-клетки в $\Delta$ мы соединяем середину верхнего ребра с серединами рёбер $e'$, $e''$, где $e'e''$ есть нижний путь клетки. При этом возникает каретка. Все такие каретки образуют корневое двоичное дерево. Далее то же самое делаем для всех $(x^2,x)$-клеток из $\Delta$. Это даёт второе корневое двоичное дерево, корень которого расположен внизу. При этом $i$-й лист верхнего дерева совпадает с $i$-м листом нижнего.

На рис. 4 изображена $(x,x)$-диаграмма из 8 клеток, в которую вписана пара корневых двоичных деревьев, каждое из которых имеет по 4 каретки.

5. Переходные отображения

Вернёмся к вопросу о представлении элементов группы $F$ кусочно линейными функциями. Обсудим здесь представление $F$ как группы диаграмм и задание её элементов в виде кусочно линейных отображений отрезка $[0,1]$ на себя. Пусть $\Delta$ есть $(x^p,x^q)$-диаграмма над ${\mathcal P}$. Свяжем с ней кусочно линейную функцию, отображающую $[0,p]$ на $[0,q]$. Всякое ребро диаграммы $\Delta$ гомеоморфно единичному отрезку $[0,1]$. Поэтому можно ввести на нём координаты так, что левый конец имеет координату $0$, а правый – координату $1$. Пусть $\pi$ есть $(x,x^2)$-клетка из $\Delta$. Отобразим $\mathbf{top}(\pi)$ на $\mathbf{bot}(\pi)$ линейно, т. е. точка на ребре $\mathbf{top}(\pi)$ с координатой $t\in[0,1]$ будет переходить в точку на $\mathbf{bot}(\pi)$ с координатой $2t$ (нижний путь $\pi$ имеет длину $2$, т. е. он естественным образом гомеоморфен отрезку $[0,2]$). То же самое сделаем для любой $(x^2,x)$-клетки из $\Delta$. Таким образом, для любой клетки $\pi$ из $\Delta$ мы имеем отображение $T_\pi$ из $\mathbf{top}(\pi)$ на $\mathbf{bot}(\pi)$. Мы называем его переходным отображением. Эта конструкция для произвольных групп диаграмм рассматривалась в [49].

Пусть теперь $t$ – произвольное число из отрезка $[0,p]$. Рассмотрим точку $o$ на пути $\mathbf{top}(\Delta)$ с координатой $t$. Если $o$ не является точкой пути $\mathbf{bot}(\Delta)$, то она будет внутренней точкой верхнего пути некоторой клетки. Мы можем применить к $o$ переходное отображение для этой клетки. Повторяем эту операцию до тех пор, пока не получим точку $o'$ на пути $\mathbf{bot}(\Delta)$. Координата этой точки принадлежит отрезку $[0,q]$. Следовательно, мы имеем функцию $f_\Delta\colon[0,p]\to[0,q]$, построенную по диаграмме $\Delta$. Легко видеть, что эта функция будет кусочно линейной. Когда мы берём конкатенацию диаграмм, это соответствует композиции кусочно линейных функций. Для группы $F$ как группы диаграмм ${\mathcal D}({\mathcal P},x)$ мы получим гомоморфизм в группу $\operatorname{PLF}[0,1]$. Он будет мономорфизмом ввиду теоремы 2.7. То, что образы $x_0$ и $x_1$ не перестановочны, легко проверяется, так как образы элементов $x_1$ и $x_2$ различны по построению.

Сферические $(x,x)$-диаграммы, соответствующие стандартным образующим $x_0$, $x_1$ группы $F$, изображены на рис. 5.

То же самое относится к случаю представления $F$ кусочно линейными отображениями положительного луча на себя, что мы обсуждали выше.

Заметим, что в определении групп диаграмм у нас фигурировали диаграммы сферические, т. е. $(w,w)$-диаграммы для некоторого слова $w$. Другое представление $F$, уже с помощью несферических диаграмм, описываемое ниже, будет соответствовать случаю кусочно линейных преобразований положительного луча.

Пусть $\Delta$ – произвольная диаграмма над ${\mathcal P}=\langle x\mid x^2=x\rangle$, не обязательно сферическая. Добавим к ней бесконечную последовательность рёбер справа от $\Delta$, давая каждому из них метку $x$. Такой объект мы назовём финитной диаграммой над ${\mathcal P}$. Она имеет конечное число клеток. Финитная диаграмма, построенная по $\Delta$, будет обозначаться через $\widehat\Delta$. Она обладает крайней левой вершиной $\iota(\widehat\Delta)$ и двумя выделенными бесконечными путями, начинающимися в вершине $\iota(\widehat\Delta)$. Оба они помечены бесконечной степенью буквы $x$. Эти пути можно обозначить $\mathbf{top}(\widehat\Delta)$ и $\mathbf{bot}(\widehat\Delta)$ соответственно.

Понятие диполя для финитной диаграммы такое же, как для обычной. То же касается операций вставки/удаления диполей, отношения эквивалентности и т. д. Любые две финитные диаграммы могут быть подвергнуты конкатенации (нижний путь первой склеиваем с верхним путём второй). Для этой операции используем тот же символ $\circ$. Эта операция превращает множество всех финитных диаграмм в моноид. Нейтральным элементом служит диаграмма без клеток, обозначаемая $\varepsilon$. Как и в случае сферических диаграмм, конкатенация индуцирует групповую структуру на множестве классов эквивалентности финитных диаграмм. Эту группу обозначим через $\widehat{\mathcal D}({\mathcal P},x)$. (Заметим, что для полугруппового копредставления произвольного вида эта конструкция не осуществима, но она всегда возможна, если алфавит меток состоит из одного символа.)

Легко проверяется, что построенная выше группа финитных диаграмм изоморфна $F$. В самом деле, пусть $X_i$ есть финитная диаграмма, состоящая из одной $(x,x^2)$-клетки, пути конечной длины с меткой $x^i$ слева от неё и пути с меткой $x^{\infty}$ справа (см. рис. 6). Через $X_i^{-1}$, как обычно, обозначаем зеркальный образ $X_i$ относительно горизонтальной оси симметрии. Финитные диаграммы вида $X_i^{\pm1}$ ($i\geqslant 0$) будут называться атомарными. Для любых целых $j > i\geqslant 0$ диаграмма, изображенная на рис. 7, равна как $X_j\circ X_i$, так и $X_i\circ X_{j+1}$. Это означает, что получается гомоморфизм из $F$ в группу финитных диаграмм. Он сюръективен, так как всякая финитная диаграмма может быть разложена в произведение атомарных. Инъективность гомоморфизма, как обычно, выводится из теоремы 2.7. Ясно, что образ здесь неабелев, поскольку $X_1X_0=X_0X_2\ne X_0X_1$.

Совпадение обозначений со случаем финитных лесов здесь не случайно, так как одно получается из другого переходом к двойственному графу. Мы будем использовать оба представления, считая их по сути одинаковыми. Иногда бывает удобно использовать одну модель, иногда – другую. Например, переходные отображения лучше описываются в терминах диаграмм, а не лесов. В ряде ситуаций может быть и наоборот.

Заметим, что диаграммам $X_i$ соответствуют в качестве переходных отображений в точности функции вида $f_i$ из раздела 1. Работая с финитными диаграммами, часто бывает удобно удалять бесконечный “хвост” справа от основной части диаграммы, так как он не несёт никакой информации. Иными словами, мы можем рассматривать обычные диаграммы над ${\mathcal P}$, не являющиеся суммой диаграммы и ребра справа. Исключением является диаграмма из одного ребра, которое мы предпочитаем не удалять, чтобы не получился вырожденный случай диаграммы без рёбер. Назовём такие диаграммы без диполей каноническими. Любой элемент из $F$ однозначно задаётся такой диаграммой.

Групповая структура здесь выглядит так: если даны канонические $(x^p,x^q)$-диаграмма $\Delta_1$ и $(x^s,x^t)$-диаграмма $\Delta_2$, мы перемножаем их следующим образом. Если $q=s$, осуществляем обычную конкатенацию. Если $q < s$, то берём конкатенацию $\Delta_1+\varepsilon(x^{s-q})$ и $\Delta_2$. (Напомним, что для непустого слова $w$ мы понимаем под $\varepsilon(w)$ диаграмму без клеток, представляющую собой простой путь с меткой $w$.) Если $q > s$, то берём конкатенацию $\Delta_1$ и $\Delta_2+\varepsilon(x^{q-s})$. После осуществления конкатенации мы сокращаем все диполи и превращаем диаграмму в каноническую, удаляя общий конец верхнего и нижнего пути. Как уже говорилось, единственным исключением служит диаграмма $\varepsilon(x)$ – единица данной группы. Она уже считается канонической, и мы её оставляем как есть.

Зная нормальную форму, легко нарисовать по ней каноническую диаграмму, и обратно. Число клеток в диаграмме равно длине нормальной формы. Это делает канонические диаграммы более удобными по сравнению со сферическими, где клеток будет больше за счёт придания сферического “обрамления”.

Пример на рис. 8 иллюстрирует диаграмму, соответствующую элементу $g=x_0^2x_1x_6x_3^{-1}x_0^{-2}$, представленному нормальной формой.

Опишем способ превращения канонической диаграммы в сферическую. Он аналогичен способу превращения леса в дерево, который мы рассматривали в разделе 3. Итак, к канонической диаграмме $\Delta$ добавляем ребро справа, беря $\Delta+\varepsilon(x)$. Пусть $v$ – крайняя правая вершина этой диаграммы. Мы соединяем $v$ дугами со всеми вершинами пути $\mathbf{top}(\Delta)$ сверху и со всеми вершинами пути $\mathbf{bot}(\Delta)$ снизу. Добавляемые рёбра снабжаем меткой $x$. В результате получается $(x,x)$-диаграмма, которая представляет тот же элемент $g$ в группе диаграмм ${\mathcal D}({\mathcal P},x)$. Добавленные клетки играют вспомогательную роль и не соответствуют никаким из образующих в записи элемента $g$.

Обратим внимание на важное обстоятельство: диаграмма на рис. 8 изображена так, что все её $(x,x^2)$-клетки расположены выше прямой линии, а все $(x^2,x)$-клетки расположены ниже. Это следствие того, что нормальная форма элементов из $F$ есть произведение вида $pq^{-1}$, где $p$, $q$ – положительные слова. Справедливо более общее утверждение, использовавшееся не раз во многих работах, в частности в [46] и [37]. Хотя этот факт и элементарен, он является важным техническим средством для работы с диаграммами.

Заметим, что условиям леммы удовлетворяет как $\langle x\mid x=x^2\rangle$, так и $\langle a,b\mid a=bab, b=aba\rangle$ из начала предыдущего раздела. Такие полугрупповые (ко)представления встречаются довольно часто, особенно при исследовании подгрупп группы $F$. Следуя уже использовавшейся терминологии, будем называть их древоподобными (tree-like). (Термин связан с тем, что букву $a$ из левой части соотношения можно “разветвить” на слово $A$ из правой части и его буквы “ветвить” далее, что приводит к появлению корневого дерева.)

Кратко напомним идею доказательства леммы. Пусть $p$ – самый длинный положительный путь в $\Delta$ из $\iota(\Delta)$ в $\tau(\Delta)$. Он разрезает $\Delta$ на две части. Достаточно доказать, что все клетки “верхней” части (выше пути $p$) соответствуют соотношениям вида $a=A$, где $a$ – буква, и ни одна из них не соответствует $A=a$. Предполагая противное, допустим, что имеется клетка $\pi$ в верхней части $\Delta$ с верхней меткой $A$ и нижней меткой $a$. Нижний путь клетки $\pi$ не может быть подпутём $p$, так как $p$ выбран путём наибольшей длины. Поэтому нижнее ребро клетки $\pi$ принадлежит верхнему пути некоторой другой клетки $\pi'$. Ввиду того, что $\Delta$ не имеет диполей, а все буквы в левых частях соотношений разные, оказывается, что верхний путь клетки $\pi'$ не может иметь длину $1$. Это означает, что мы можем указать новую клетку в $\Delta$, которая опять соответствует соотношению вида $A=a$. Применяя то же соображение к $\pi'$, мы получаем процесс, который никогда не завершается. Это невозможно, так как клетки в ходе процесса не повторяются.

6. Группы кусочно линейных функций

Выше мы показали, что элементы $F$ представляются кусочно линейными функциями, но не описали, как выглядит образ соответствующего гомоморфизма. Для начала отметим необходимые условия для функций из леммы 1.1 быть в образе гомоморфизма в группу $\operatorname{PLF}(\mathbb R_+)$. Все функции вида $f_n$ кусочно линейны и имеют конечное число “изломов” (точек, где не существует производная). Все угловые коэффициенты равны целочисленным степеням двойки. Далее, двоично-рациональные точки переходят в двоично-рациональные, и только они могут быть точками излома. Помимо всего прочего, на бесконечности все функции имеют вид сдвига на целое число.

Всё сказанное верно для функций вида $f_n$ и им обратных. Указанные свойства сохраняются при композиции и взятии обратного. Следовательно, функции с перечисленным набором условий образуют некоторую подгруппу $H$ в группе $\operatorname{PLF}(\mathbb R_+)$. Наша цель – доказать, что гомоморфизм $F$ в $H$ сюръективен.

Рассмотрим график какой-либо функции из $H$. Увеличим масштаб по каждой оси в $2^n$ раз, где $n$ – достаточно большое число. Оно подбирается так, чтобы после умножения на $2^n$ все двоично-рациональные точки излома графика стали целыми. Изменению масштаба здесь соответствует сопряжение. Введём обозначение для диаграмм, для которых функция перехода линейно отображает единичный отрезок на отрезок от нуля до $2^m$. Такую диаграмму $\Psi_m$ определим индуктивно. Пусть $\pi$ – клетка вида $x=x^2$. Тогда $\Psi_1=\pi$ и $\Psi_{m+1}=\pi\circ(\Psi_m+\Psi_m)$ при $m\geqslant 1$. После увеличения масштаба график функции состоит из отрезков, соединяющих точки с целочисленными координатами. Угловые коэффициенты имеют вид $2^k$, где $k$ целое. Каждый отдельный отрезок графика отображает некоторый отрезок длиной $s$ на отрезок длиной $2^ks$. Если $k > 0$, то такому отрезку будет соответствовать сумма $s$ экземпляров $\Psi_k$. Если $k < 0$, то аналогично берём $s$ экземпляров $\Psi_k^{-1}$. При $k=0$ берём диаграмму $\varepsilon(x^s)$ без клеток. Так поступаем для каждого отрезка, а потом всё полученное складываем. Это даст диаграмму $\Delta$, для которой функция перехода представляет собой нашу функцию в увеличенном масштабе.

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

Описанная диаграмма даёт конструктивный способ восстановления элемента из $F$ по заданной кусочно линейной функции из $H$. Таким образом, получается, что группа $F$ изоморфна группе кусочно линейных функций со следующими свойствами:

Если за основу взять сферические $(x,x)$-диаграммы и применить к ним переходные отображения, то получится группа кусочно линейных отображений отрезка $[0,1]$ на себя с теми же свойствами кроме последнего. Часто именно это определение группы $F$ берут за основу.

Наконец, можно заметить следующее. Если рассматривать функции из $\mathbb R$ на себя, то элементы $x_1,x_2,\ldots$ группы $F$ можно перевести в $f_0,f_1,\ldots$ соответственно (расширяя их до тождественных на отрицательном луче). Элемент $x_0$ переведём в функцию $t\mapsto t+1$. При этом снова все определяющие соотношения группы $F$ будут выполняться, и мы получим изоморфное представление функциями из $\mathbb R$ на себя с теми же свойствами, добавляя ещё одно условие, что на минус бесконечности также имеет место сдвиг на целочисленную константу (возможно, другую). В разных ситуациях бывает удобно использовать одно из перечисленных представлений функциями. Все группы здесь изоморфны $F$ и при этом вложены друг в друга.

Отметим, что группа $F$ линейно упорядочиваема. Под этим понимается существование линейного порядка на группе, устойчивого относительно умножения как слева, так и справа. Этим же свойством обладает вся группа $\operatorname{PLF}(\mathbb R_+)$. Положительные элементы определяются так: смотрим на график функции и находим первую точку отклонения графика от тождественной функции. Если угловой коэффициент в правой окрестности этой точки больше $1$, то объявляем функцию положительной. Множество положительных функций замкнуто относительно произведения и сопряжения. Отсюда следует существование инвариантного с двух сторон порядка: $f\succ g$ тогда и только тогда, когда функция $fg^{-1}$ положительна.

Закончим данный раздел известной технической леммой о транзитивности действия группы на последовательностях двоично-рациональных точек. Сделаем это для функций на полупрямой. Выше мы использовали временное обозначение $H$ для группы функций с условиями (a)–(d). Сейчас мы знаем, что она изоморфна $F$, поэтому будем так её и обозначать, не рискуя получить конфликт обозначений.

Как и выше, можно увеличить масштаб по обеим осям в $2^n$ раз, переводя все точки в целочисленные. Сопряжение функцией вида $t\mapsto t/2^n$ не меняет свойства угловых коэффициентов быть целочисленными степенями двойки. Теперь достаточно построить функцию для каждого отдельного отрезка. Задача состоит в том, чтобы перевести отрезок $[0,u]$ в $[0,v]$ для любых целых положительных $u$, $v$ при помощи кусочно линейной функции с допустимыми угловыми коэффициентами.

Если не стремиться получить при этом как можно меньше звеньев ломаной, то годится следующее рассуждение. Достаточно уметь осуществлять сдвиг на вектор, когда одна из компонент равна 1, так как $(u,v)=(u-1,1)+(1,v-1)$ для случая $u,v > 1$. Поэтому решаем задачу для случая $u=1$, $v > 1$. Заметим, что она равносильна построению функции для векторов $(2,2v)$, $(4,4v)$ и т. д.

Запишем число $v$ в двоичной системе как сумму $r$ различных степеней двойки. Будем считать, что $2^{s-1} < r\leqslant 2^s$. Легко видеть, что $v$ будет при этом представимо и в виде $2^s$ степеней двойки (уже не обязательно различных). Это следует из того, что все слагаемые (кроме, возможно, одного) можно представить в виде суммы двух равных, и тогда их общее количество можно довести до нужной величины.

Для примера: если $v=7=1+2+4$, то $r=3$, $s=2$. Тогда полагаем $7=1+2+2+2$, где слагаемых получается $4$. В общем случае мы домножаем всё на $2^s$, и число степеней двойки остаётся прежним. В итоге получается вектор $(2^s,2^sv)$, который представляем в виде суммы $2^s$ векторов с первой единичной координатой и второй координатой, равной степени двойки. В нашем примере это даёт $(4,28)=(1,4)+(1,8)+(1,8)+(1,8)$, что решает задачу.

7. Свободные подгруппы и тождества

Лемму о транзитивности из предыдущего раздела мы применим для получения важного результата о том, что группа $F$ не удовлетворяет никакому нетривиальному тождеству. Это было установлено М. Брином и К. Сквайером в работе [6]. Там же был получен другой принципиальный результат об отсутствии в $F$ неабелевых свободных подгрупп, который мы изложим чуть ниже.

Рассмотрим произвольное отличное от единичного приведённое групповое слово $v(\xi_1,\dots,\xi_m)$ от некоторого числа переменных. Требуется указать такие элементы $g_1,\dots,g_m\in F$, для которых $v(g_1,\dots,g_m)\ne1$. Мы сделаем это для представления $F$ функциями из $\operatorname{PLF}(\mathbb R_+)$. Прежде всего, запишем слово $v$ как произведение букв $\eta_1\ldots\eta_n$, где каждое $\eta_j$ равно какому-то $\xi_i^{\pm1}$, причём соседние буквы не являются взаимно обратными.

Функции будем подбирать так, чтобы при действии каждой очередной буквой происходили переходы $1\to\dfrac{1}{2}\to\dfrac{1}{4}\to\cdots\to\dfrac{1}{2^n}$ . Это накладывает требование на функции $g_1,\dots,g_m$. А именно, если $\xi_i$ встретилось в качестве $j$-й буквы слова $v$, т. е. $\eta_j$, то функция $g_i$ должна переводить число $2^{-(j-1)}$ в $2^{-j}$. Заметим, что та же самая буква $\xi_i$ может входить в запись слова многократно, что накладывает несколько условий для разных значений $j$. Также если в качестве $\eta_j$ встретилась буква $\xi_i^{-1}$, то от функции $g_i$ требуется, чтобы число $2^{-j}$ под действием этой функции переходило в $2^{-(j-1)}$. Заметим, что противоречий при этом не возникает, так как никакое число под действием одной и той же функции не может иметь двух разных образов. Последнее вытекает из факта приведённости слова $v$ в свободной группе.

Осталось проверить, что все эти условия совместимы. Ввиду того, что все рассматриваемые значения функций здесь двоично-рациональны, для применения леммы 6.1 нужно проверить лишь условие монотонности, т. е. тот факт, что в списке требований на функции вида $g_i$ меньшие числа переходят в меньшие. В данном случае это очевидно, так как каждое число переходит либо в удвоенное, либо в два раза меньшее. Тогда если $2^{-r}$ перешло в $2^{-(r+1)}$, то число $2^{-(r+1)}$ уже не может перейти в большее число под действием той же функции, а именно в $2^{-r}$ (других вариантов нет). Это следует из того, что одна и та же буква не может иметь сразу и положительную, и отрицательную степень, а переходы осуществляются здесь только в одном направлении (для положительных букв – слева направо, для отрицательных – наоборот).

Для ясности рассмотрим простой пример слова $v=\xi_1^2\xi_2^{-1}\xi_1^{-2}\xi_2$. Здесь получается, что

Результат об отсутствии свободных неабелевых подгрупп в группе $F$ мы изложим в несколько более сильной форме, следуя [46]. Как мы уже знаем, $F$ изоморфно вкладывается в группу $\operatorname{PLF}(I)$ кусочно линейных функций с конечным числом изломов на единичном интервале $I=[0,1]$. Теперь всё будет следовать из такого результата.

Для $f\in\operatorname{PLF}(I)$ через $\operatorname{supp} f$ обозначим множество всех $t\in I$, для которых $tf\ne t$. Пусть $G$ – неабелева подгруппа в $\operatorname{PLF}(I)$. Рассмотрим функции $f,g\in G$ такие, что $fg\ne gf$. Пусть $J=\operatorname{supp}f\cup\operatorname{supp}g$. Очевидно, что $J$ есть объединение конечного числа непересекающихся интервалов $J_k=(a_k,b_k)$, $1\leqslant k\leqslant m$. По условию, $[f,g]\ne1$ в группе $\operatorname{PLF}(I)$. Поэтому среди $J_1,\dots,J_m$ имеются интервалы, на которых функция $[f,g]$ не тождественна. Обозначим число таких интервалов через $\nu(f,g)$. Без ограничения общности будем далее считать, что некоммутирующие элементы $f,g\in G$ выбраны так, что число $\nu(f,g)$ является минимальным. Через $H$ обозначим подгруппу в $\operatorname{PLF}(I)$, порожденную $f$ и $g$. По условию концы интервалов $J_1,\dots,J_m$ неподвижны как относительно $f$, так и относительно $g$ и каждый из этих интервалов инвариантен относительно действия элементов подгруппы $H$.

Покажем, что для любых $x,y\in J_k$ ($1\leqslant k\leqslant m$), где $x < y$, существует функция $w\in H$ такая, что $xw>y$. Возьмем точную верхнюю грань $z$ множества точек $\{xh\mid h\in H\}$. Ясно, что $a_k<z\leqslant b_k$. Если $z\ne b_k$, то либо $zf\ne z$, либо $zg\ne z$ по определению множества $J$. Без ограничения общности пусть $zf\ne z$. Это неравенство выполняется также в некоторой малой окрестности точки $z$. Следовательно, либо $zf$, либо $zf^{-1}$ больше, чем $z$, – противоречие. Поэтому $z=b_k$, откуда следует, что под действием некоторого элемента из $H$ образ точки $x$ можно сделать сколь угодно близким к $b_k$. Фактически это и требовалось доказать.

Выберем интервал $(a_i,b_i)$ ($1\leqslant i\leqslant m$), на котором $[f,g]$ не тождественна. Легко видеть, что функция $[f,g]$ тождественна в некоторой окрестности каждой из точек $a_i$, $b_i$. Поэтому $\operatorname{supp}[f,g]$ непуст и содержится в $[c_0,d_0]$, где $a_i<c_0<d_0<b_i$. Согласно сказанному выше существует функция $w\in H$ такая, что $d_0<c_0w<b_i$. Обозначим $[f,g]$ через $h_0$. Для любого $n\geqslant 1$ положим $c_n=c_0w^n$, $d_n=d_0w^n$, $h_n=h_0^{w^n}$. Очевидно, что $c_0<d_0<c_1<d_1<\cdots$, причем $\operatorname{supp} h_n\cap J_i\subseteq[c_n,d_n]$. Отсюда следует, что при любых $i,j\geqslant 0$ коммутатор $[h_i,h_j]$ тождествен на $J_i$. Предположим, что $[h_i,h_j]\ne1$ для некоторых $i$, $j$. Поскольку все интервалы $J_1,\dots,J_m$ являются $H$-инвариантными, ясно, что на любом из интервалов $J_k$ ($1\leqslant k\leqslant m$), на котором $h_0$ была тождественна, все функции $h_1,h_2,\ldots$ также будут тождественны. Следовательно, мы можем заменить $f$, $g$ на $h_i$, $h_j$, имея при этом $\nu(h_i,h_j)<\nu(f,g)$, что противоречит выбору $f$, $g$. Это противоречие доказывает, что $[h_i,h_j]=1$ для любых $i,j\geqslant 0$.

В доказательствах, данных в [6], [11], отсюда делался вывод, что элементы $h_0,h_1,h_2,\ldots$ образуют базис свободной абелевой группы. С учётом следствия 2.3 об отсутствии кручения в группе $F$ нам остаётся лишь добавить, что $h_n^w=h_{n+1}$ при всех $n\geqslant 0$, поэтому элементы $h_0$, $w$ порождают прямое сплетение ${\mathbb Z}\wr{\mathbb Z}\leqslant G$. Теорема доказана.

Помимо отмеченных выше работ, в которых так или иначе затрагиваются свойства подгрупп группы $F$, отметим также статью [48], а ряд новых результатов о подгруппах группы Томпсона получен в недавних работах Г. Голан и М. Сапира [28]–[30].

8. Критерии аменабельности групп

Прежде чем начать обсуждение основной для данного обзора проблемы (не)аменабельности группы $F$, напомним основные определения.

Пусть $G$ – группа. Рассмотрим линейное пространство ${\mathfrak B}(G)$ ограниченных функций на группе $G$ со значениями в $\mathbb R$. Линейный функционал $\mu$ на ${\mathfrak B}(G)$ называется (лево)инвариантным средним, если он удовлетворяет следующим условиям:

(i) для любой функции $f\in{\mathfrak B}(G)$ такой, что $f(x)\geqslant 0$ при всех $x\in G$, выполнено условие $\mu(f)\geqslant 0$;

(ii) для любого $a\in G$ выполнено условие $\mu(f_a)=\mu(f)$, где $f_a(x)=f(ax)$ при всех $x\in G$.

Заметим, что вместо условия (i) часто приводят равносильное, требуя, чтобы были выполнены неравенства $\inf_{x\in G}f(x)\leqslant \mu(f)\leqslant \sup_{x\in G}f(x)$ для всех функций из ${\mathfrak B}(G)$.

Аналогичным образом даётся определение (право)инвариантного среднего на группе. Такое различие полезно делать в случае полугрупп, для которых между одним и другим имеется разница. Но нас здесь будут интересовать группы, для которых оба условия равносильны за счёт возможности перехода к обратному элементу. Более того, для групп можно требовать двусторонней инвариантности, т. е. $\mu(f)=\mu(f_a)=\mu(_af)$, где $_af(x)=f(xa)$ для всех $x\in G$.

Рассмотрим произвольное подмножество $A\subseteq G$. Если (лево)инвариантное среднее на группе $G$ существует, то можно рассмотреть значение функционала на характеристической функции этого множества, т. е. $\mu(\chi_A)$, где $\chi_A(x)=1$ при $x\in A$ и $\chi_A(x)=0$ при $x\notin A$. Такое правило задаёт конечно-аддитивную вероятностную меру на множестве всех подмножеств $A$. Удобно упростить обозначения и писать $\mu(A)$ вместо $\mu(\chi_A)$, что не ведёт к коллизиям.

Получается отображение $\mu\colon\mathcal{P}(G)\to[0,1]$ со следующими свойствами:

(ii) $\mu(A\cup B)=\mu(A)+\mu(B)$ для всех $A,B\subseteq G$ с условием $A\cap B=\varnothing$;

Если такое отображение для группы существует, т. е. имеется конечно-аддитивная вероятностная мера, то для любой ограниченной функции на группе можно рассмотреть её интеграл Лебега по этой мере. Легко проверить, что он будет обладать всеми свойствами инвариантного среднего.

Таким образом, оба условия оказываются эквивалентными. Более того, с их помощью можно добиться двусторонней инвариантности. Покажем кратко, как это можно сделать для меры. Для каждого $A\subseteq G$ и $x\in G$ можно рассмотреть меру $\mu(Ax)$, которая зависит от $x$. Это ограниченная функция от $x$, и её можно усреднить по группе. Получится новая мера $\nu$, которая дополнительно будет обладать свойством двусторонней инвариантности: $\nu(gA)=\nu(A)=\nu(Ag)$ для всех $A\subseteq G$, $g\in G$.

В технические подробности мы здесь вдаваться не будем, отсылая читателя к литературе. См., например, [31], [18], [64].

Уже говорилось, что везде можно требовать односторонней или двусторонней инвариантности.

Понятие аменабельной группы восходит к работе Дж. фон Неймана [59]. Приведённые определения являются стандартными, и с их помощью легко доказывать разного рода общие свойства аменабельных групп. Например, как доказать, что подгруппа $H$ аменабельной группы $G$ аменабельна? Можно рассмотреть смежные классы $G$ по $H$ – например, левые. Всякое подмножество $B\subseteq H$ можно распространить на всю группу $G$, беря объединение $A=\bigcup\limits_g gH$ по системе представителей смежных классов. Число $\nu(B)$ полагаем равным $\mu(A)$. Нетрудно проверить, что этим будет задана мера $\nu$ на $H$ со всеми требуемыми свойствами.

Похожими средствами доказывается, что факторгруппа аменабельной группы аменабельна. Там достаточно взять полный прообраз подмножества при естественном гомоморфизме и рассмотреть его меру в качестве меры этого подмножества в факторгруппе.

Рассмотрим ещё случай группового расширения. Пусть $N$ нормальна в $G$, и пусть группы $N$ и $G/N$ аменабельны. Какую меру следует поставить в соответствие подмножеству $A\subseteq G$? Надо рассмотреть $G$ как объединение смежных классов по $N$, индексированных элементами факторгруппы. Для каждого элемента факторгруппы надо рассмотреть меру пересечения $A$ с соответствующим смежным классом. Последний находится во взаимно однозначном соответствии с $N$, и пересечение переносим туда посредством биекции, беря его меру в $N$. Получается ограниченная функция на факторгруппе, которую по ней и усредняем.

Из достаточно общих соображений доказывается замкнутость класса аменабельных групп относительно возрастающих направленных объединений. Отсюда можно вывести, что свойство аменабельности локально: если все конечно порождённые подгруппы в $G$ аменабельны, то и сама группа $G$ аменабельна. Нас далее будет интересовать именно конечно порождённый случай.

Отметим также, что конечные группы аменабельны, что вполне очевидно (достаточно взять все элементы равновероятными). Если группа абелева, то она также аменабельна, что доказывается сравнительно просто. Можно считать её конечно порождённой, тогда она будет гомоморфным образом прямой степени $\mathbb Z$ и достаточно обосновать аменабельность $\mathbb Z$. Объясним, как это делается, так как при этом используется одна важная идея.

Пусть $A\subseteq\mathbb Z$. Рассмотрим пересечение $A$ с отрезком $[-n,n]$ для каждого натурального $n$. Обозначим его через $A_n$. Рассмотрим долю элементов подмножества в отрезке, т. е. $|A_n|/(2n+1)$. Это ограниченная последовательность. Берём её предел по фиксированному неглавному ультрафильтру в $\mathbb N$. Значение этого предела считаем мерой множества. Проверки здесь почти все очевидны, и обсудить имеет смысл только инвариантность. Ясно, что мера инвариантна относительно всех сдвигов тогда и только тогда, когда она инвариантна относительно сдвига на единицу. Но в нашем случае сдвиг на единицу меняет мощность пересечения с отрезком максимум на 2 и после деления на $2n+1$ в пределе получается нуль.

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

Таким образом, мы располагаем пока таким запасом аменабельных групп: берутся все конечные и все абелевы, и далее рассматривается замыкание этого класса относительно (i) взятия подгрупп, (ii) взятия факторгрупп, (iii) операций группового расширения, (iv) объединения возрастающего направленного семейства групп. Такие группы ввёл М. Дей в [17], он назвал их элементарно аменабельными (EA). Он же поставил проблему о том, совпадает ли этот класс групп с классом всех аменабельных.

Отрицательный ответ был дан Р. И. Григорчуком [33], построившим знаменитые группы промежуточного роста. В дальнейшем были построены и другие примеры, часть которых мы упомянем ниже. Пока отметим, что группа Томпсона $F$, аменабельность которой является открытой проблемой и главным объектом нашего рассмотрения, не является элементарно аменабельной [14]. Примеры конечно представленных групп, которые аменабельны, но не принадлежат классу EA, также были впервые построены Григорчуком [34], [35].

Обратимся теперь к случаю конечно порождённых групп. Пусть группа $G$ задана $m$-элементным множеством порождающих $a_1,\dots,a_m$. Тогда с ней можно связать функцию роста и функцию двойственного роста (cogrowth). Делается это так. Рассматриваем все групповые слова длины не более $n$ в алфавите образующих и смотрим, какое количество элементов группы при этом получается. Это число представляет собой объём шара радиуса $n$ в графе Кэли группы $G$ с данной системой образующих. Этим задаётся функция роста группы, которая зависит от системы образующих $A$ и может быть обозначена $\gamma_A(n)$. При замене системы образующих на другую конечную систему эта функция меняется не сильно. Точное описание эквивалентности функций мы не приводим, замечая лишь то, что бывают группы с функцией степенного роста, а также экспоненциального роста, причём эти свойства от выбора системы образующих не зависят. Долгое время оставалась открытой проблема Милнора о существовании групп промежуточного роста, которая в уже упоминавшейся работе [33] и была положительно решена. Здесь важно отметить тот факт, что любая группа субэкспоненциального роста автоматически оказывается аменабельной – почему это так, будет объяснено ниже. Группа $F$ обладает свободной полугруппой с образующими $x_0$, $x_1$, что может быть легко доказано на языке диаграмм. Это следует из того факта, что делимость положительного элемента справа на $x_0$ исключает его делимость справа на $x_1$. Поэтому рост группы экспоненциален. См. также [11; следствие 4.7].

Для фиксированной системы образующих можно рассмотреть последовательность $\sqrt[n]{\gamma_A(n)}$ . Несложным упражнением является доказательство того, что она имеет предел. Это является следствием легко доказываемого субмультипликативного свойства: $\gamma_A(m+n)\leqslant \gamma_A(m)\gamma_A(n)$. Более подробно см. [63; гл. 1, § 2]. Данный предел называется показателем роста группы относительно фиксированной системы образующих. Для показателя роста группы Томпсона относительно стандартной системы порождающих $x_0$, $x_1$ в [38] была получена нижняя оценка $(3+\sqrt5\,)/2$. Есть основания полагать, что она является точной [22].

Хотя функции роста и важны, но свойство аменабельности группы они до конца не “улавливают”. А вот в некотором роде двойственная конструкция даёт один из критериев. Пусть $G$ снова порождена $m$ элементами, тогда она изоморфна факторгруппе свободной группы по некоторой её нормальной подгруппе: $\mathbb F_m/N$. Будем рассматривать групповые слова длины $n$ над алфавитом $\{a_1,\dots,a_m\}$ свободных порождающих, которые задают элемент нормальной подгруппы $N$. Это в точности слова данной длины, равные единице в группе $G$. Обозначим их количество через $P_n$ и извлечём корень $n$-й степени. Полученная величина $\sqrt[n]{P_n}$ уже не всегда имеет предел (например, все соотношения в группе могут иметь чётную длину – как для случая группы $F$ в стандартной системе образующих), но она всегда имеет верхний предел $\limsup_{n\to\infty}\sqrt[n]{P_n}$ (известно также, что он совпадает с обычным, если брать только чётные $n$). Будем называть это число двойственным показателем роста (cogrowth rate) для данной системы образующих. Понятно, что $P_n\leqslant (2m)^n$, откуда $\sqrt[n]{P_n}\leqslant 2m$. Ясно, что верхний предел не превосходит $2m$. Оказывается, что равенство имеет место в точности для аменабельных групп, и это свойство не зависит от выбора конечной системы порождающих. В этом состоит знаменитый критерий Кестена [54], [55].

Заметим, что чаще всего этот критерий формулируют в терминах вероятности, и рассматривают число

Иногда бывает удобно рассматривать не все групповые слова от образующих, а только приведённые в свободной группе. Введём обозначение $\overline{P}_n$ для числа приведённых групповых слов длины $n$, представляющих единичный элемент группы $G$. Понятно, что $\overline{P}_n\leqslant 2m(2m-1)^{n-1}$, поэтому верхний предел не больше $2m-1$. Назовём число $\limsup_{n\to\infty}\sqrt[n]{\overline{P}_n}$ приведённым показателем двойственного роста. Во многих работах с успехом использовался следующий критерий из [32].

Оба критерия говорят о том, что группа аменабельна тогда и только тогда, когда слов от образующих, равных единице, имеется очень много. Из критерия Григорчука непосредственно следует, что свободная группа ранга $m > 1$ неаменабельна, хотя этот факт может быть установлен и проще. Поскольку аменабельность распространяется на подгруппы, получаем, что если в группе есть свободная неабелева подгруппа, то отсюда сразу следует неаменабельность самой группы. Интерес к проблеме аменабельности группы $F$ был во многом вызван отсутствием в ней свободных неабелевых подгрупп, что мы доказывали в разделе 7.

Долгое время оставалась открытой проблема: существуют ли неаменабельные группы, не имеющие свободных подгрупп ранга $>1$? Эта проблема неявно фигурировала в работе фон Неймана [59], а в явной форме была сформулирована М. Деем [17]. Решена она была впервые в работе А. Ю. Ольшанского [60]. Через некоторое время С. И. Адян [1] доказал неаменабельность свободных бернсайдовых групп достаточно большого нечётного показателя (такие группы периодичны, и свободных подгрупп в них нет). В обеих работах применялся критерий Григорчука. Однако все эти примеры относились к числу групп, не задаваемых конечным числом соотношений. Группа Томпсона $F$ не раз рассматривалась в качестве кандидата на роль конечно определённой группы, не являющейся аменабельной и не обладающей свободными неабелевыми подгруппами. Однако является ли $F$ таковой, мы не знаем по сей день, а соответствующий пример (весьма сложный технически) был построен в совместной работе Ольшанского и Сапира [61].

О возможности применения критериев Кестена и Григорчука к проблеме аменабельности $F$ мы поговорим позже в разделе 12.

Обратимся к одному из наиболее популярных и часто используемых критериев аменабельности – критерию Фёлнера [23]. Разные авторы формулируют его совершенно по-разному, хотя суть везде одна и та же. Критерий этот необычайно общий, и его имеет смысл сформулировать для любых групп, а не только для конечно порождённых. Остановимся на такой формулировке.

Сразу же очевидно, что подгруппа $H$, порождённая множеством $A$, сама должна быть аменабельной, если условие критерия Фёлнера выполняется. Поэтому множество $Y$ должно существовать уже в пределах подгруппы $H$. Для конечно порождённого случая можно добавить к $A$ все образующие в конечном количестве. Например, можно расширить $A$ до системы порождающих группы или добавить к $A$ единичный элемент. Если мы посмотрим на ситуацию с такой точки зрения, то увидим конечное множество $Y$, которое “почти инвариантно” относительно действия образующими. Поместив $Y$ в левый граф Кэли группы с данным множеством образующих (в этом случае образующие действуют умножениями слева), мы получим конечный подграф, в котором “почти все” вершины являются внутренними точками $Y$, т. е. имеют максимально возможную степень.

В связи с этим удобно рассмотреть понятие плотности графа Кэли, которое было введено в работе [38]; см. также [2]. Пусть дан конечный граф $\Gamma$. Назовём его плотностью среднюю степень его вершин. Пусть теперь дан граф Кэли (правый или левый) некоторой $m$-порождённой группы. Его плотностью назовём точную верхнюю грань плотностей всех его конечных (непустых) подграфов. Получается удобная переформулировка предыдущего критерия для конечно порождённого случая.

Такой подход позволяет в некотором смысле “измерять”, в какой степени мы близки к доказательству аменабельности той или иной группы. Допустим, она имеет $m$ порождающих. Какого максимального значения плотности мы умеем достигать для её подграфов? При этом подразумевается, что группа может и не быть аменабельной – плотности мы вправе оценивать и для такого случая.

Оказывается, что для группы Томпсона $F$ в стандартной системе групповых порождающих $\{x_0,x_1\}$ наилучшей на данный момент является оценка плотности, стремящаяся к $3.5$. От значения $4$ это достаточно далеко. Лучшая из имеющихся на данный момент конструкций будет рассмотрена в разделе 9. Сейчас же можно коротко отметить её основные особенности.

Существует семейство конечных подграфов, для которых выполняются следующие свойства. Если $Y$ – конечный подграф, то для каждого образующего $a$ или ему обратного можно говорить о вероятности того, что из случайно взятой вершины исходит ребро с меткой $a$ в пределах подграфа $Y$. Удобно говорить на таком языке, что $Y$ – это автомат (размеченный) и его вершина принимает ребро с меткой $a$. В конструкции Белка и Брауна из [4] построено семейство конечных подграфов $Y$ в графе Кэли для стандартной системы порождающих, где образующий $x_0^{\pm1}$ принимается с вероятностью, близкой к 1, и $x_1^{\pm1}$ не принимается с вероятностью, чуть превышающей $1/4$. Тот факт, что данная конструкция более чем за 15 лет никем принципиально не была улучшена, является одним из доводов в пользу того, что $F$, скорее всего, неаменабельна.

Здесь можно ещё упомянуть работу [40], в которой на основе предыдущей конструкции сделано следующее. Берётся симметричное множество из двух образующих $\{x_1,\overline{x}_1\}$, описанное в разделе 1; см. лемму 1.4. Для такого порождающего множества конструкция Белка–Брауна давала оценку плотности, равную $3$. Имелась гипотеза, что оценка плотности $3.5$ для графа Кэли в системе $\{x_0,x_1\}$ оптимальна. Она не доказана и не опровергнута до сих пор. Этой гипотезе естественно соответствовало предположение, что для симметричного множества образующих оптимальной оценкой плотности будет число $3$. Однако это оказалось не так: в цитируемой работе были построены примеры конечных подграфов в графе Кэли с симметричным множеством образующих, плотность которых строго больше значения $3$. Данный результат был далее усилен в работе [42].

Из всего этого можно заключить, что доказать аменабельность $F$ через критерий Фёлнера, построив в явном виде так называемые фёлнеровские множества, либо очень трудно, либо вовсе невозможно. Для формулировки следующего важного результата следует дать чуть более формальное определение системы фёлнеровских множеств. Пусть $G$ – аменабельная группа, порождённая множеством $A$. Для любого натурального $n$ существует конечное множество $Y_n$ со свойством $|AY_n| < (1+1/n)|Y_n|$. В этом случае мы говорим, что $Y_n$ ($n\in\mathbb N$) есть фёлнеровская система подмножеств аменабельной группы.

После этого определения уместно пояснить, почему из существования фёлнеровской системы вытекает аменабельность группы, т. е. возможность задать на ней инвариантную конечно-аддитивную меру. Вспомним, как выше это делалось для случая группы $\mathbb Z$. Заметим, что множества $Y_n$ отнюдь не должны быть как-то вложены друг в друга.

Если $X\subseteq G$ – произвольное подмножество, то мы рассматриваем долю этого подмножества в пределах $Y_n$, т. е. величину $x_n=|X\cap Y_n|/|Y_n|$. Это ограниченная числовая последовательность, у которой мы берём предел по фиксированному неглавному ультрафильтру на $\mathbb N$. Меру подмножества $X$ полагаем равной значению этого предела. Все нужные свойства легко проверяются, и инвариантность следует из того, что если вместо $X$ взять его сдвиг $aX$ для какого-то образующего $a$, то величина $x_n$ изменится на бесконечно малую за счёт того, что множества $aY_n$ и $Y_n$ почти совпадают. Поэтому предел будет тем же, и свойство $\mu(X)=\mu(aX)$ будет выполнено для любого образующего, а значит, и для любого элемента группы. Последняя в итоге оказывается аменабельной. Это было обоснование критерия Фёлнера в одну из сторон. Ниже будет рассмотрено доказательство в другую сторону.

Здесь же отметим, что если группа имеет субэкспонециальный рост (полиномиальный или промежуточный), то в качестве системы фёлнеровских множеств можно взять обычные шары возрастающих радиусов в графе Кэли. Для случая групп экспоненциального роста, в частности для $F$, такая конструкция уже не проходит. Она не годится даже для метабелевой группы $\mathbb Z\wr\mathbb Z$ – прямого сплетения бесконечной циклической группы с собой. Эта группа содержится в $F$, и фёлнеровская система подмножеств для прямого сплетения легко строится в явной форме, но уже не в виде шаров.

Сформулируем теперь важный результат Дж. Т. Мура из [58]. Суть теоремы в том, что если $F$ аменабельна, то фёлнеровские множества имеют очень быстрый рост.

Данный результат можно при желании трактовать как в пользу аменабельности группы $F$, так и в пользу её неаменабельности. Первая трактовка: группа аменабельна, но фёлнеровские множества очень сложно устроены, поэтому их не удаётся обнаружить. Вторая трактовка основана на соображениях построения потоков на графах, о чём речь будет идти ниже. В этом смысле теорему Мура можно истолковать как ослабленный вариант доказательства неаменабельности (причём самый лучший из имеющихся на данный момент), для которого нужно искать усиление.

Перейдём к исследованию случая, когда условие из критерия Фёлнера для группы $G$ не выполнено. Её саму будем считать конечно порождённой. На этом пути мы получим ещё несколько полезных и интересных критериев (не)аменабельности.

Беря отрицание условия, имеем следующее: существуют конечное подмножество $A$ и положительное $\varepsilon_0$ такие, что $|AY|\geqslant(1+\varepsilon_0)|Y|$ для любого конечного подмножества $Y$. Рассмотрим натуральное $k$, для которого $(1+\varepsilon_0)^k\geqslant 2$. Тогда, очевидно, $|BY|\geqslant 2|Y|$ для любого конечного подмножества $Y$, где $B=A^k$ (степень $A$ как множества элементов).

Множество $B$, для которого выполнено предыдущее условие, мы называем удваивающим. Если группа неаменабельна, то условие критерия Фёлнера нарушается, поэтому удваивающее множество образующих всегда существует. Для случая группы Томпсона $F$ было достаточно давно известно, что множество $\{x_0^{\pm1},x_1^{\pm1}\}$ удваивающим не является. Это было отмечено в добавлении к статье [38], и вскоре после этого Дж. М. Белк и К. С. Браун значительно усилили эту оценку. Если к множеству добавить симметричные образующие, то исходя из поверхностных оценок мощностей можно было надеяться на получение множества с удваивающим свойством. Однако в [40] было установлено, что множество из шести образующих $\{x_0^{\pm1},x_1^{\pm1},\overline{x}_1^{\pm1}\}$ не обладает таким свойством, даже если туда включить единицу. Открытым остаётся вопрос о том, будет ли удваивающим множество $\{x_0^{\pm1},x_1^{\pm1},x_2^{\pm1}\}$. Конечно, можно добавлять образующие $x_3^{\pm1}$ и т. д., пытаясь добиться эффекта удвоения, однако с большими множествами порождающих становится труднее работать.

Продолжим анализ общей ситуации. Пусть в группе $G$ найдено удваивающее множество $B$. Можно построить двудольный граф, каждая из долей которого есть копия группы $G$, и от элемента $g$ первой доли проводится ребро к элементу $bg$ второй доли для каждого $b\in B$. Возникает ситуация задачи о паросочетаниях для бесконечных множеств. См. [51] по поводу классического варианта этой задачи, а также [50], [52] по поводу её обобщений. Пусть элементы первой доли – это “юноши”, а элементы второй доли – “девушки”. Рёбра показывают отношение знакомства. Граф знакомств считается локально конечным. Условие $|BY|\geqslant 2|Y|$ говорит о том, что для любых $s$ юношей найдётся не менее $2s$ девушек, каждая из которых знакома хотя бы с одним из $s$ юношей. Теорема Холла для бесконечных множеств позволяет заключить, что каждому юноше можно поставить в соответствие двух знакомых с ним девушек таким образом, чтобы никакая девушка не ставилась в соответствие разным юношам. Более подробно о связи между теоремами из этой области см. раздел H книги [12]. Отметим также, что название “теорема Холла–Радо”, приводимое в [57] и упоминаемое в ряде других источников, не вполне корректно.

В данном случае можно зафиксировать элемент $b\in B$ и любому подмножеству $Z$ вершин второй доли поставить в соответствие множество $b^{-1}Z$ вершин первой доли. Из этого будет следовать, что любые $t$ девушек знакомы в совокупности с не менее чем $t$ юношами. Из этого с помощью рассуждений в духе теоремы Кантора–Бернштейна выводится существование совершенного паросочетания, при котором каждой девушке сопоставляется ровно один знакомый юноша, а каждый юноша при этом сопоставлен ровно двум девушкам.

На языке группы и её подмножеств это означает следующее. Если для группы $G$ нарушается условие Фёлнера, то существует отображение $f\colon G\to G$ такое, что каждый элемент из $G$ имеет ровно два прообраза, и при этом группа представляется в виде дизъюнктного объединения $G=G_1\sqcup G_2\sqcup\cdots\sqcup G_q$ таким образом, что $f(g)=b_ig$ для любого $g\in G_i$ ($1\leqslant i\leqslant q$), где $b_1,\dots,b_q$ – фиксированный конечный набор элементов группы. Вводя для каждого $g$ нумерацию двух его прообразов, мы получаем отображения $h_1$ и $h_2$ из $G$ в $G$, которые позволяют определить биекцию $G$ на $G'\sqcup G''$, где $G'$ и $G''$ – дизъюнктные копии группы $G$. При этом $G$ можно представить в виде дизъюнктного объединения конечного числа частей

Из существования парадоксального разбиения группы мгновенно следует, что инвариантной меры на группе не существует, так как в противном случае из свойств этой меры следовало бы противоречие в виде $\mu(G)=2\mu(G)$. Отметим, что это элегантное доказательство, основанное на теореме Холла для бесконечных множеств, было изложено в [18].

Отсюда сразу следует, что если условие критерия Фёлнера нарушается, то группа неаменабельна. С учётом импликации в другую сторону, о которой уже говорилось, имеем следующий

Для некоторых групп, которые устроены достаточно просто (например, для свободных неабелевых групп), парадоксальные разбиения легко строятся в явном виде. Примеры можно найти в [18], [64]. Также можно заметить, что если группа обладает свободной неабелевой подгруппой, то она разбивается на смежные классы, каждый из которых устроен как подгруппа, и парадоксальное разбиение на каждой из копий позволяет получить парадоксальное разбиение всей группы.

Попутно можно отметить ещё один критерий. Выше мы говорили об удваивающем отображении $f\colon G\to G$, наличие которого свидетельствует о неаменабельности группы. Обратно, если $G$ неаменабельна, то нарушается условие критерия Фёлнера, в результате чего можно построить удваивающее отображение. Оно обладает тем свойством, что каждый элемент имеет ровно два прообраза, и при этом элемент $g$ и его образ $f(g)=bg$, где $b$ принадлежит конечному множеству, находятся на ограниченном расстоянии в (левом) графе Кэли. Для правого графа Кэли всё аналогично. Ясно, что если все “сдвиги” происходят на ограниченное расстояние, то в качестве $B$ можно взять конечную совокупность элементов ограниченной длины.

От специфики системы порождающих здесь может зависеть только значение константы. Образно можно представить себе эту ситуацию так. В каждой вершине графа Кэли живёт “блоха”, которая умеет прыгать в пределах ограниченного расстояния. Тогда в случае неаменабельности группы все блохи могут одновременно совершить прыжки так, что в каждой вершине окажется ровно две блохи.

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

Пусть дан граф $\Gamma$, рассматриваемый в смысле Серра (все рёбра считаются направленными, и у каждого ребра $e$ имеется формальное обратное $e^{-1}\ne e$). Потоком на графе $\Gamma$ называется отображение $\nu$ из $E$ в $\mathbb R$, где $E=E(\Gamma)$ есть множество ориентированных (направленных) рёбер. При этом должно выполняться равенство $\nu(e^{-1})=-\nu(e)$ для всех $e\in E$. Это очень простое и наглядное понятие, которое легко изображается на рисунке в виде стрелочек на рёбрах с числовыми метками на них. Графы при этом рассматриваем локально конечные. Величину $\nu(e)$ называем величиной потока (или просто потоком) через ребро $e$. Сумму $\displaystyle\sum_i\nu(e_i)$ по всем ориентированным рёбрам $e_i$, оканчивающимся в вершине $v$, назовём притоком в вершину $v$.

Ясно, что здесь можно ввести нормировку, полагая без ограничения общности, например, $\varepsilon_0=1$. Замена образующих влияет в данном случае только на значения констант. Поскольку нам не известны источники, в которых критерий излагался бы в этом виде (хотя по сути это относится к области известного), скажем несколько слов о доказательстве.

Пусть группа порождена множеством $A$, где $|A|=m$, и на левом графе Кэли мы построили соответствующий поток. Рассмотрим произвольное конечное множество вершин $Y$. Оно определяет некоторый подграф – не обязательно связный. Рассмотрим множество $AY\setminus Y$. Достаточно доказать неравенство $|AY\setminus Y| > \varepsilon|Y|$ для некоторого положительного $\varepsilon$. Отсюда будет следовать, что $|AY|\geqslant (1+\varepsilon)|Y|$ для всех конечных подмножеств $G$, и тогда группа неаменабельна по критерию Фёлнера.

Иными словами, надо убедиться в том, что в $AY\setminus Y$ достаточно много элементов. Для каждого $g$ из этого множества имеется ребро $e$ с меткой из $A$, конец которого принадлежит $Y$. Назовём такие рёбра внешними для $Y$. Для каждой вершины из $AY\setminus Y$ имеется не более $m$ исходящих из неё внешних рёбер. Поэтому достаточно получить оценку снизу для числа внешних рёбер.

Суммарный приток в вершины из $Y$ по условию составляет не меньше $\varepsilon_0|Y|$. Поскольку потоки по рёбрам между вершинами из $Y$ вносят нулевой вклад в суммарный приток, учитывать следует только внешние рёбра. Приток по каждому из них не больше $C$, и после умножения на число внешних рёбер должно получиться не меньше $\varepsilon_0|Y|$. Значит, внешних рёбер не меньше $C^{-1}\varepsilon_0|Y|$, и тогда в $AY\setminus Y$ не меньше $\varepsilon|Y|$ элементов, где $\varepsilon=m^{-1}C^{-1}\varepsilon_0$.

В обратную сторону: пусть имеется неаменабельная группа $G$ с конечным множеством порождающих $A$. Мы знаем, что для неё существует удваивающее множество порождающих $B$, для которого имеется удваивающая функция $f\colon G\to G$. Для графа Кэли группы $G$ относительно множества порождающих $B$ поток строится по очень простому принципу: из каждой вершины $g$ в вершину $f(g)$, которая является соседней в графе, запускаем поток интенсивности $1$ по ребру, идущему из $g$ в $f(g)$. При этом в каждую вершину придут два ребра, а выйдет из неё одно, поэтому приток в каждую вершину будет равен $\varepsilon_0=1$. Константа $C$ при этом также будет равна единице.

Теперь превратим этот поток в другой, уже для графа Кэли с множеством порождающих $A$. Каждый элемент из $B$ выразим каким-нибудь способом в виде группового слова $w$ от образующих из $A$. Поток по ребру, метка которого была равна $b$, перенаправим по пути с меткой $w$. Ясно, что в итоге приток в любую вершину останется равным $\varepsilon_0=1$. Через любое заданное ребро может пройти лишь ограниченное константой число путей с меткой вида $w$ ввиду того, что все эти длины ограничены в совокупности. Оценку сверху числа таких путей и надо принять за $C$; явный её вид совершенно не важен. Это даёт требуемый поток на графе Кэли группы $G$ с заданным множеством порождающих. Критерий в терминах потоков доказан.

Предлагаемый критерий является потенциально полезным средством для установления неаменабельности группы. Работать при этом можно с любым множеством порождающих, не обязательно удваивающим. Заметим также, что нет необходимости строить такие потоки сразу на всём бесконечном графе Кэли. Достаточно брать конечные фрагменты графа, которые в объединении его исчерпывают. Это могут быть шары возрастающих радиусов или другие конечные множества, принадлежность которым усматривается по простому признаку – скажем, числу клеток в диаграмме, или числу кареток в дереве или лесе. О таких конструкциях для группы $F$ мы поговорим в разделе 12.

9. Конструкция Белка–Брауна

Введём понятие высоты корневого двоичного дерева. У тривиального дерева (из одной вершины) высота равна $0$. Для дерева $T=(T_1\widehat{\ }\,T_2)$, в котором поддеревья $T_1$ и $T_2$ соединены кареткой, высота по определению равна $\operatorname{hgt}T=\max(\operatorname{hgt}T_1,\operatorname{hgt} T_2)+1$.

Помеченным (корневым двоичным) лесом назовём такой корневой двоичный лес, в котором одно из составляющих его деревьев выделено (помечено маркером).

Пусть $n\geqslant 1$, $k\geqslant 0$ – фиксированные параметры. Через $\operatorname{BB}(n,k)$ обозначим множество всех помеченных лесов, которые имеют $n$ листьев и для которых высота каждого из входящих в такой лес деревьев не превосходит $k$. Группа $F$ обладает левым частичным действием на этом множестве. А именно, $x_0$ действует сдвигом маркера на единицу влево, если такое действие возможно. Аналогично устроено действие образующим $x_0^{-1}$, когда маркер смещается на единицу вправо.

Действие элементом $x_1$ таково: если помеченное дерево тривиально, то оно не определено. Если помеченное дерево имеет вид $T=(T_1 \widehat{\ }\, T_2)$, то мы удаляем его верхнюю каретку, увеличивая число деревьев на единицу, и помечаем дерево $T_1$. Легко заметить, что применение симметричного образующего $\overline{x}_1=x_1x_0^{-1}$ означает то же самое с заменой $T_1$ на $T_2$ в качестве выделенного дерева (здесь сначала действует $x_1$, а потом $x_0^{-1}$).

Отсюда видно, что действия элементами $x_1$ и $\overline{x}_1$ симметричны друг другу. Они порождают $F$, т. е. их можно рассматривать как естественное множество порождающих группы, наряду со стандартным множеством образующих.

Действия образующими $x_1^{-1}$ и $\overline{x}_1^{\,-1}$ устроены аналогично. А именно, если выделенное дерево является крайним справа, то $x_1^{-1}$ не применимо. В противном случае, если выделенное дерево $T$ имеет дерево $T''$ правее него, то мы добавляем каретку для этих деревьев и дерево $(T\widehat{\ }\, T'')$ объявляем отмеченным в результате. Заметим, что если мы находимся внутри множества $\operatorname{BB}(n,k)$, то оба дерева $T$, $T''$ должны иметь высоту $<k$: в противном случае $x_1^{-1}$ применить нельзя. Действие элементом $\overline{x}_1^{\,-1}$ неприменимо, если выделенное дерево $T$ является крайним слева. В противном случае слева от $T$ имеется дерево $T'$ и мы соединяем эти деревья кареткой. Полученное при этом дерево $(T'\widehat{\ }\, T)$ будет объявлено выделенным. Как и выше, оба дерева $T'$, $T$ должны иметь высоту $<k$, чтобы мы оставались внутри множества $\operatorname{BB}(n,k)$.

Сформулированные правила будут важны для дальнейшего; читателю рекомендуется их запомнить.

Можно непосредственно проверить, что применение определяющих соотношений группы $F$ приводит к тождественному результату (при условии, что действие на каждом шаге определено). Детали можно найти в [4]. Таким образом, можно рассматривать $\operatorname{BB}(n,k)$ как множество вершин графа Кэли группы $F$. Это можно сделать для любого из трёх множеств групповых порождающих: $\{x_0,x_1\}$, $\{x_1,\overline{x}_1\}$ и $\{x_1,\overline{x}_1,x_0\}$.

Для любого фиксированного $k$ пусть $n\gg k$. Поскольку любое дерево высоты $k$ имеет не более $2^k$ листьев, любой лес из $\operatorname{BB}(n,k)$ содержит не менее $n/2^k$ деревьев. Следовательно, если мы случайно выберем размеченный лес, вероятность того, что соответствующая вершина графа принимает оба образующих $x_0$, $x_0^{-1}$, стремится к $1$. Оценим вероятность принять образующий $x_1$. Обратное имеет место тогда и только тогда, когда помеченное дерево тривиально. Будем считать, что это дерево не является крайним справа. Тогда можно удалить это тривиальное дерево, перемещая маркер на одну позицию вправо. В результате мы получим элемент множества $\operatorname{BB}(n-1,k)$. Обратная операция всегда возможна. Тем самым, интересующая нас вероятность равна $|\operatorname{BB}(n-1,k)|/|\operatorname{BB}(n,k)|$. Она стремится к некоторому числу $\xi_k$ при $n\to\infty$. Если $k$ достаточно велико, то $\xi_k$ близко к $1/4$. Действительно, для больших $k$ число элементов множества $\operatorname{BB}(n,k)$ растёт почти как $4^n$, подобно числам Каталана. Более детальное объяснение см. далее.

Для случая обратного символа $x_1^{-1}$ прямая оценка вероятности его не принимать является достаточно трудоемкой. Однако она совпадает с оценкой для $x_1$ ввиду следующего несложного утверждения.

Напомним, что для данного конечного подграфа $Y$ графа Кэли $\mathcal{C}$ его границей Чигера $\partial_{\ast}Y$ называется множество всех его внешних рёбер, т. е. множество направленных рёбер, начало которых принадлежит $Y$, а конец не принадлежит.

Пусть $e$ – ребро с меткой $a$ из $\partial_{\ast}Y$. Его начальная вершина $v$ принадлежит $Y$. Положим $v_0=v$, и для любого $n\geqslant 0$ пусть $v_{n+1}$ есть начальная вершина ребра из $\mathcal{C}$ с меткой $a$, у которого конечная вершина есть $v_n$. Если элемент $a$ имеет бесконечный порядок в $G$, то все вершины вида $v_n$ ($n\geqslant 0$) попарно различны. В этом случае, поскольку $Y$ конечно, существует наименьшее $n > 0$ такое, что $v_n$ не принадлежит $Y$. Тогда $v_{n-1}$ принадлежит $Y$ и автомат не принимает ребро из $v_{n-1}$ в $v_n$ с меткой $a^{-1}$. Это ребро $f$ поставим в соответствие ребру $e$.

Предположим, что $a$ имеет конечный порядок в $G$. Тогда имеется замкнутый путь в $\mathcal C$ с началом $v$, метка которого равна степени $a$. У этого пути есть вершины вне $Y$. Поэтому, как и в предыдущем абзаце, мы можем найти наименьшее $n$ с тем же свойством. В этом случае мы также полагаем $e\mapsto f$.

Ясно, что этим задаётся биекция между рёбрами из $\partial_{\ast}Y$ с метками $a$ и $a^{-1}$. Обратное отображение $f\mapsto e$ устроено точно так же с заменой образующего $a\in A^{\pm1}$ на его обратный $a^{-1}$.

Итак, в силу только что доказанной леммы мы видим, что число внешних рёбер подграфа (т. е. рёбер границы Чигера для $\operatorname{BB}(n,k)$) стремится к половине мощности этого множества. Это значит, что плотность $\operatorname{BB}(n,k)$ стремится к $3.5$.

Чтобы быть более точными, добавим некоторые вычисления. Прежде всего, пусть $\Phi_k(z)$ есть производящая функция множества корневых двоичных деревьев высоты $\leqslant k$ с $n$ листьями. Ясно, что $\Phi_0(z)=z$. Для $k > 0$ мы имеем либо тривиальное дерево, соответствующее слагаемому $z$, либо оно имеет верхнюю каретку. Удаляя её, мы получаем упорядоченную пару корневых двоичных деревьев высоты $\leqslant k-1$. Тем самым, $\Phi_k(z)=z+\Phi_{k-1}(z)^2$.

Итак, мы имеем последовательность многочленов с целыми положительными коэффициентами. Все они задают возрастающие функции при $z\geqslant 0$ и стремятся к бесконечности при $z\to\infty$. Поэтому существует и единственно решение уравнения $\Phi_k(z)=1$. Обозначим его через $\xi_k$. Это даёт убывающую последовательность. Покажем, что $\xi_k\to 1/4$ при $k\to\infty$.

Прежде всего, индукцией по $k$ можно легко проверить, что $\Phi_k(1/4)<1/2$ для всех $k\geqslant 0$. Таким образом, $1/4 < \xi_k$. С другой стороны, всякое дерево с $n\leqslant k$ каретками (а потому с $n+1$ листьями) имеет высоту $\leqslant k$. По этой причине первые коэффициенты $\Phi_k(z)$ совпадают с числами Каталана: коэффициент при $z^{n+1}$ равен $c_n$ для $n\leqslant k$.

10. Условие Оре

Пусть дано ассоциативное кольцо $R$ с единицей. (Правым) условием Оре для такого кольца называется следующее: для любых $a,b\in R$ существуют $u,v\in R$, не равные одновременно нулю, для которых $au=bv$. (Иными словами, главные правые идеалы $aR$ и $bR$ имеют ненулевое пересечение.) В дальнейшем мы будем рассматривать это определение, говоря просто об условии Оре.

Согласно классической теореме Оре [62] если $R$ не имеет делителей нуля и удовлетворяет условию Оре, то оно вложимо в тело, называемое телом частных кольца $R$.

Пусть $G$ – конечно порождённая группа и $K$ – некоторое поле. Известно, что если $G$ аменабельна, то групповое кольцо $K[G]$ удовлетворяет условию Оре. Это доказано в [68], причём доказательство достаточно простое.

Можно обобщить это утверждение. Пусть вместо одного линейного уравнения $au=bv$ с коэффициентами из $R$ рассматривается система, в которой число неизвестных превышает число уравнений:

Утверждается, что для аменабельной группы $G$ такая система всегда имеет ненулевое решение.

В самом деле, пусть $A\subseteq G$ – объединение носителей всех коэффициентов вида $a_{ij}$. По критерию Фёлнера (см. раздел 8) для любого $\varepsilon > 0$ существует конечное множество $X$ такое, что $|AX|<(1+\varepsilon)|X|$. Пусть $u_j$ ($1\leqslant j\leqslant n$) будут линейными комбинациями элементов из $X$ с неопределёнными коэффициентами из поля. Это даёт $n|X|$ неизвестных, принимающих значения в $K$. Для любого из $m$ уравнений системы мы собираем вместе все коэффициенты при данном элементе из $AX$ и налагаем условие, что их сумма равна нулю. Это приводит к обычной системе из $m|AX|$ линейных уравнений. Такая система имеет ненулевое решение в поле, если число неизвестных превышает число уравнений. Это имеет место при $m(1+\varepsilon) < n$, т. е. достаточно положить $\varepsilon < (n-m)/m$.

В недавней работе [3] Л. Бартольди показал, что обратное утверждение также верно. Это даёт новый критерий аменабельности группы. Хотя теорема 1.1 в [3] касается так называемых свойств GOE и MEP для автоматов (Gardens of Eden и Mutually Erasable Patterns; подробнее об этих свойствах см. [12]), её доказательство позволяет извлечь следующее утверждение.

В добавлении к работе [3] Д. Килак показывает, что если групповое кольцо $K[G]$ не имеет делителей нуля, то оба свойства из теоремы эквивалентны условию Оре. В частности, это имеет место для группы Томпсона $F$. Она является упорядоченной, поэтому в групповом кольце над полем нет делителей нуля. (Отметим попутно, что для группы $F$ упорядочение строится на основе представления её элементов кусочно линейными функциями, а в [49] доказан намного более общий факт об упорядочиваемости всех групп диаграмм.)

Данная теорема позволяет изучать проблему аменабельности $F$ на языке уравнений в групповых кольцах. Отметим работу [41], в которой проблема сведена к случаю однородных уравнений в моноидном кольце $K[M]$ и исследован случай, когда коэффициенты являются многочленами первой степени. Для этого случая доказано существование ненулевых решений. Для случая, когда коэффициенты имеют степень 2 и являются линейными комбинациями пяти одночленов из множества $\{x_0^2,x_0x_1,x_0x_2,x_1^2,x_1x_2\}$, также дан положительный ответ. При увеличении степеней многочленов или количества образующих, от которых они зависят, ответ на данный момент не известен.

Ввиду важности данного результата изложим здесь подробное доказательство теоремы Бартольди. Во всех ключевых моментах мы следуем идеям исходной работы [3].

В одну из сторон всё следует из результата Д. Тамари. Далее считаем, что группа $G$ неаменабельна. Без ограничения общности можно считать её конечно порождённой.

Согласно критерию Фёлнера существуют $\varepsilon > 0$ и конечное множество $A$, которое можно расширить до некоторого множества образующих $S_0$ так, что для любого непустого конечного подмножества $D\subset G$ выполнено неравенство $|S_0D| > (1+\varepsilon)|D|$. Ввиду того, что экспонента растёт быстрее линейной функции, найдётся натуральное $k$, для которого $|S_0^kD| > (1+\varepsilon)^k|D| > (k\ln|S_0|+1)|D|$. Положим $S=S_0^k$ и $n=|S|$. Обозначения $S$ и $n$ будут важны до конца доказательства. Ясно, что $n=|S_0^k|\leqslant |S_0|^k$, откуда следует, что $\ln n\leqslant k\ln|S_0|$, поэтому для любого конечного непустого $D\subset G$ выполняется неравенство

Рассмотрим группу подстановок $\operatorname{Sym}(S)$ на множестве $S$. Каждую подстановку разложим в произведение независимых циклов, учитывая циклы единичной длины. Построим систему уравнений над групповым кольцом группы $G$. Каждая подстановка $\sigma\in\operatorname{Sym}(S)$ даст нам столько уравнений системы, сколько в ней имеется циклов. Используя тот факт, что всякий цикл длиной $d$ может быть записан $d$ различными способами, легко видеть, что подстановок с выделенным циклом длиной $d$ будет в точности $n!/d$. Поэтому общее число уравнений нашей системы составит $N=n!\,\biggl(1+\dfrac{1}{2}+\cdots+\dfrac{1}{n}\biggr)$.

Количество неизвестных нашей системы мы положим равным $N+1$, а в качестве поля коэффициентов выберем поле $K=\mathbb Q(Z)$ рациональных функций с достаточно большим количеством переменных. Заметим, что сам доказываемый факт можно несколько усилить: он будет верен для любого бесконечного поля, а также для подходящего конечного расширения любого конечного поля, но в столь сильной форме нам это далее не потребуется.

Пусть $\sigma\in\operatorname{Sym}(S)$ – подстановка, в которой выделен цикл $(s_1\ldots s_d)$. Свяжем с ним уравнение над $K[G]$ вида $a_1y_1+\cdots+a_{N+1}y_{N+1}=0$, где все $a_i$ ($1\leqslant i\leqslant N+1$) суть линейные комбинации элементов $s_1,\dots,s_d\in G$ с коэффициентами из $Z$, где каждая свободная переменная из множества $Z$ может быть использована в системе уравнений только один раз. Как уже говорилось, число уравнений в такой системе будет равно $N$, т. е. число неизвестных на единицу больше числа уравнений. Далее будем доказывать, что решение $(y_1,\dots,y_{N+1})\in K[G]^{N+1}$ может быть только нулевым.

Рассуждая от противного, предположим, что имеется ненулевое решение. Каждая координата решения есть линейная комбинация конечного числа элементов из $G$ (возможно, нулевая). Ввиду того, что вектор решения ненулевой, объединение носителей $D=\bigcup\limits_{i=1}^{N+1}\operatorname{supp}(y_i)$ есть непустое конечное множество. Тогда к нему можно применить неравенства, верные для любого такого множества. В частности, мы знаем, что

Построим двудольный граф $\Gamma$, у которого одной долей является множество $D$, а второй – множество $SD$. Для каждой вершины из $D$ рассмотрим $n$ исходящих из неё рёбер с метками $s\in S$, соединяющих каждое $g\in D$ с $sg\in SD$. Для любой вершины второй доли рассмотрим все входящие в неё рёбра графа. Их может быть от $1$ до $n$. Если в такую вершину входят $d$ рёбер, то каждому из них мы придаём вес, равный $1/d$. В частности, сумма весов рёбер, входящих в данную вершину из $SD$, равна единице, а суммарный вес всех рёбер графа $\Gamma$ будет равен $|SD|$. Ввиду того, что первая доля графа содержит $|D|$ вершин, найдётся вершина $g\in D$ такая, что сумма весов всех $n$ выходящих из неё рёбер не меньше $|SD|/|D|$.

Выбранный элемент $g$ будет играть ключевую роль в оставшейся части доказательства. Сразу же отметим, что целью является доказательство того, что все коэффициенты при $g$ для компонент решения $(y_1,\dots,y_{N+1})$ окажутся нулевыми, что будет означать установление противоречия.

Введём важное для дальнейшего техническое понятие. Символ $s\in S$ будем называть полезным для подстановки $\sigma\in\operatorname{Sym}(S)$, если в вершину $sg$ графа $\Gamma$ входит ровно одно ребро с меткой из того же самого цикла, в запись которого входит $s$. Отметим следующее вспомогательное комбинаторное утверждение.

Доказательство. Поскольку рассматриваемая вероятность не зависит от обозначений, мы можем без ограничения общности считать, что речь идёт о символах от $1$ до $m$. Рассмотрим одну из возможных биекций между множествами всех перестановок и подстановок на $n$ символах. В каждой из подстановок запишем все её циклы так, чтобы наименьший элемент цикла следовал в самом конце. При этом последние элементы циклов должны образовывать возрастающую последовательность. Ясно, что такой способ записи однозначен, и ему соответствует некоторая перестановка. Биективность вытекает из существования обратного отображения, т. е. по каждой перестановке мы однозначно можем восстановить подстановку. А именно, первый из циклов будет оканчиваться символом $1$, в результате чего он однозначно определяется. Если при этом какие-то символы остались, то второй цикл окончится наименьшим из них, и то же самое для всех остальных циклов.

Например, по перестановке $418923657$ мы однозначно восстанавливаем подстановку $(41)(892)(3)(65)(7)$.

Случайно взятая подстановка (перестановка) задаёт порядок на множестве символов, и при этом порядки следования элементов любого его подмножества оказываются равновероятными. Поэтому среди символов от $1$ до $m$ каждый символ с равной вероятностью следует самым первым. Для того чтобы цикл, содержащий $1$, не содержал символов от $2$ до $m$, необходимо и достаточно, чтобы символ $1$ в перестановке предшествовал символам от $2$ до $m$, вероятность чего равна $1/m$. Лемма доказана.

Рассмотрим теперь произвольный символ $s\in S$ и найдём вероятность того, что в случайно взятой подстановке $\sigma\in\operatorname{Sym}(S)$ этот символ окажется полезным. Пусть в вершину $sg$ графа $\Gamma$ входят $m$ рёбер с метками $s=s_1,\dots,s_m$. Заметим, что вес каждого из этих рёбер в точности равен $1/m$. С другой стороны, это есть вероятность того, что в цикле подстановки $\sigma$, содержащем $s$, нет ни одного из символов $s_2,\dots,s_m$, а это и означает, что $s$ будет полезным для $\sigma$.

Таким образом, общее число подстановок, для которых $s$ окажется полезным, равно произведению $n!$ на вес ребра с меткой $s$, выходящего из $g$. Суммируя по всем символам, мы получаем, что общее число пар вида $(\sigma,s)$, где $s$ полезен для $\sigma$, равно произведению $n!$ на сумму весов исходящих из вершины $g$ рёбер. Тем самым, данное число пар больше, чем $n!\biggl(1+\dfrac{1}{2}+\cdots+\dfrac{1}{n}+\dfrac{1}{n!}\biggr)=N+1$.

Рассмотрим теперь уравнение системы, построенное на основе подстановки $\sigma$ и выделенного в ней цикла $(s_1\ldots s_d)$, где $s=s_1$ – полезный для данной подстановки символ. По определению ни один из элементов вида $s_ih$, где $2\leqslant i\leqslant d$, $h\in D$, не равен $sg$. Наше уравнение имеет вид $a_1y_1+\cdots+a_{N+1}y_{N+1}=0$, где элементы вида $a_i$ суть линейные комбинации $s_1,\dots,s_d$ с коэффициентами из $Z$, а элементы вида $y_i$ суть линейные комбинации элементов из $D$ с какими-то коэффициентами из $K$. Обозначим через $t_i$ коэффициент при $g$ в выражении $y_i$ ($1\leqslant i\leqslant N+1$). Если мы далее подставим вместо $a_i$ линейные комбинации элементов цикла (все они – с разными $Z$-коэффициентами), а вместо $y_i$ напишем линейные комбинации элементов из $D$, раскрывая скобки и приводя подобные члены, то окажется, что коэффициент при $sg$ получается только за счёт умножения $s=s_1$ на $g\in D$ и никак иначе: именно в этом суть свойства полезности символа $s$ в подстановке. Тогда этот коэффициент равен нулю и возникает обыкновенное линейное уравнение, левая часть которого есть линейная комбинация переменных $t_1,\dots,t_{N+1}$ с попарно различными $Z$-коэффициентами.

Выписывая такое линейное уравнение для всех пар вида $(\sigma,s)$, где $s$ является полезным для $\sigma$, мы получаем, согласно сказанному выше, более $N+1$ линейных уравнений (достаточно было бы ровно $N+1$) от переменных $t_1,\dots,t_{N+1}$. Коэффициенты, принадлежащие $Z$, при этом нигде не повторяются, и такая однородная система имеет только нулевое решение. Последнее означает, что все коэффициенты при $g$ в разложении каждого $y_i$ равны нулю, т. е. $g$ не принадлежит объединению носителей.

Полученное противоречие завершает доказательство теоремы Бартольди. Для ясности отметим, что один и тот же цикл может содержать, вообще говоря, много полезных элементов, за счёт чего и достигается нужный эффект.

Скажем несколько слов о том, как отсюда следует теорема Килака. Ограничимся случаем группы $F$, хотя утверждение является чуть более общим. Уже говорилось о том, что для любого поля $K$ групповое кольцо $R=K[F]$ группы Томпсона не имеет делителей нуля. Тогда если это кольцо удовлетворяет условию Оре, то $R$ вложимо в тело частных $RR^{-1}$. Над телом любая линейная система, в которой уравнений меньше, чем неизвестных, имеет ненулевое решение. Пусть оно имеет вид $(r_1s_1^{-1},\dots,r_ns_n^{-1})$, где $r_i,s_i\in R$ ($1\leqslant i\leqslant n$). Индукцией по числу элементов из условия Оре выводится, что всякое конечное подмножество ненулевых элементов в $R$ имеет общее левое кратное, т. е. существует $s\in R$, делящийся слева на все $s_1,\dots,s_n$ одновременно. Домножая решение $(r_1s_1^{-1},\dots,r_ns_n^{-1})$ справа на $s$, получаем ненулевое решение системы в самом групповом кольце $K[F]$. Тогда $F$ удовлетворяет условию (ii) из теоремы Бартольди, а потому удовлетворяет и условию (i), т. е. является аменабельной.

11. Формула длины

Во многих исследованиях свойств группы $F$ возникает проблема нахождения длины элемента группы в данной системе образующих (т. е. длины кратчайшего группового слова от образующих, представляющего данный элемент). По этой причине мы решили осветить вопрос о нахождении длин элементов группы в данном разделе.

Алгоритм нахождения длины элемента группы $F$ в системе групповых образующих $x_0$, $x_1$ был получен Б. Фордхэмом в его диссертации [24]. Он был основан на представлении элементов $F$ парами корневых двоичных деревьев. Каждая каретка дерева принадлежала одному из семи классов, определяемых в этой работе (только шесть из них оказывались существенными). Все каретки деревьев были перенумерованы. Для каждого номера имеется $36$ случаев для пары, образованной $i$-ми каретками деревьев по принципу принадлежности этих кареток одному из классов. Каждому классу приписывался вес. Сумма весов и задавала при этом норму (словарную длину) элемента. При помощи этого алгоритма норма вычислялась за полиномиальное время, хотя алгоритм сам по себе оказывался сложным. Тем не менее он служил полезным средством для решения ряда задач, относящихся к $F$, и с успехом применялся в ряде работ – таких как [9], [15].

В работе [38] мы предложили намного более простой алгоритм вычисления длины элемента группы $F$, основанный на его представлении несферическими (каноническими) диаграммами из раздела 5. Мы анализируем вершины диаграммы, разделяя их всего на два типа. Чтобы найти норму (словарную длину), достаточно сложить число клеток с удвоенным числом так называемых специальных вершин. Этот алгоритм очень ясно устроен и прост в использовании.

Отметим, что в работе [4] также имеется алгоритм вычисления длины элементов $F$, основанный на представлении парами корневых помеченных лесов. Он проще алгоритма Фордхэма, но всё же сложнее предлагаемого нами.

Итак, пусть $\Delta$ – каноническая диаграмма, задающая элемент из $F$ (это понятие было введено в разделе 5). Согласно лемме 5.1 мы знаем, что все вершины в $\Delta$ принадлежат самому длинному пути $p$ из $\iota(\Delta)$ в $\tau(\Delta)$. Непустой путь $q$ в $\Delta$ с положительной меткой $q$ (в частности, отдельное ребро) называется мостом, если $q$ служит общим подпутём в $\mathbf{top}(\Delta)$ и $\mathbf{bot}(\Delta)$. Если $q$ – мост в $\Delta$, то диаграмма допускает разложение вида $\Delta'+q+\Delta''$, где $\Delta$, $\Delta''$ – некоторые диаграммы ($\Delta''$ может оказаться пустой) и $q$ обозначает поддиаграмму в $\Delta$, состоящую из моста $q$. Мы называем мост $q$ нетривиальным, если $\Delta''$ имеет клетки. Заметим, что всякий мост, являясь путём, имеет начальную точку $\iota(q)$.

Поскольку $\Delta$ можно рассматривать как конечный связный граф, имеется естественная функция расстояния на множестве его вершин. Как обычно, расстоянием между двумя вершинами связного графа называется длина кратчайшего пути, их соединяющего.

На рис. 9 мы нумеруем все вершины диаграммы $\Delta$, идя вдоль пути $p$ от начальной вершины, имеющей номер $0$. Ясно, что в данном примере вершины $0$, $1$, $3$, $5$, $6$ активны. Вершины $5$, $6$ из этого списка, и только они, являются специальными вершинами диаграммы $\Delta$.

Следующий результат был получен в [38]. Приведём его формулировку без доказательства.

Можно проверить, что элемент $g$ группы $F$, представленный диаграммой на рис. 9, имеет длину $11$. Он обладает следующим интересным свойством: при умножении справа на любой из групповых порождающих $x_0^{\pm1}$, $x_1^{\pm1}$ длина элемента уменьшается на единицу (такие вершины графа Кэли называют тупиковыми). Проверка легко осуществляется при помощи формулы из теоремы 11.2. Более подробно о тупиковых элементах в графе Кэли группы $F$ см. [15].

12. Разное

В данном разделе мы представим ряд новых результатов о группе $F$. Они касаются простого описания исчерпывающих конечных фрагментов графов Кэли, а также нового алгоритма решения проблемы слов в этой группе.

Уже говорилось о том, что, в контексте проблемы аменабельности, вместо описания бесконечного графа Кэли достаточно описания конечных подграфов, которые содержат шары сколь угодно большого радиуса. В силу леммы 3.1 достаточно рассматривать такие конечные фрагменты в пределах моноида $M$ положительных элементов.

Одно из индуктивных описаний конечных фрагментов графа Кэли было дано в [38] в связи с предъявлением семейства подграфов, плотность которых стремится к трём. Достаточно стандартным средством для работы с группой является также представление её элементов в виде помеченных корневых двоичных лесов, что было нами задействовано в разделе 9 в ходе описания конструкции Белка–Брауна. С этого описания мы сейчас и будем стартовать. Прежде всего покажем, как каждому помеченному корневому двоичному лесу поставить в соответствие упорядоченную тройку деревьев, что делается достаточно естественным образом.

Пусть дан помеченный корневой двоичный лес, деревья которого мы обозначим в виде $T_{-k},\dots,T_{-1},T_0,T_1,\dots,T_m$, где $k,m\geqslant 0$, и помеченным является дерево $T_0$. Добавим слева и справа к этому лесу одноточечные деревья, обозначая их через $T_{-(k+1)}$ и $T_{m+1}$ соответственно. Далее будем добавлять каретки, навешивая их последовательно на два крайних справа дерева, не затрагивая при этом дерево $T_0$ и делая это до тех пор, пока правее $T_0$ не останется ровно одно дерево. При этом добавить придётся $m$ кареток. В точности ту же самую процедуру проведём слева, добавляя $k$ кареток. А именно, будем последовательно навешивать новую каретку на два крайних слева дерева, пока левее $T_0$ не окажется ровно одно дерево. Итогом этого процесса станет тройка корневых двоичных деревьев. То дерево, которое изначально было помеченным, останется посередине в неизменном виде.

Обозначим через $n$ общее число листьев в тройке деревьев. Ясно, что $n\geqslant 3$, и из элементарных комбинаторных соображений легко понять, что количество троек деревьев для данного $n$ будет выражаться через числа Каталана как

Домножению элемента группы слева на $x_0$ соответствует такая операция: крайнюю слева каретку снимаем, получается четвёрка деревьев, каретку устанавливаем на два крайних справа дерева. Такая операция применима, если первое из деревьев тройки нетривиально. Аналогично определяется домножение слева на $x_0^{-1}$.

Домножению элемента группы слева на $x_1$ соответствует такая операция: среднюю каретку снимаем, получается четвёрка деревьев, каретку устанавливаем на два крайних справа дерева. Такая операция применима, если второе из деревьев тройки нетривиально. Аналогично определяется домножение слева на $x_1^{-1}$.

Здесь можно заметить, что операция домножения слева на симметричный образующий $\overline{x}_1=x_1x_0^{-1}$ соответствует снятию средней каретки с последующим её перемещением влево, а не вправо. На этом примере хорошо заметен данный вид симметрии. Он соответствует (внешнему) автоморфизму группы $F$, заданному правилами $x_0\mapsto x_0^{-1}$, $x_1\mapsto\overline{x}_1$.

Таким образом, $\Gamma_n$ становится подграфом (левого) графа Кэли группы $F$. Сама по себе процедура перемещения кареток (применения образующих из множества $\{x_0^{\pm1},x_1^{\pm1},\overline{x}_1^{\pm1}\}$) чем-то напоминает известные “ханойские башни”.

Структура этих графов достаточно удобна для работы с группой, в частности для построения потоков на графах Кэли. Как мы уже знаем из раздела 8, достаточно это делать на расширяющихся конечных фрагментах. Проверка того, что графы вида $\Gamma_n$ содержат шары сколь угодно больших радиусов, достаточно проста. Для каждого $m\geqslant 1$ рассмотрим тройку одинаковых корневых двоичных деревьев, которые на любом из $m$ уровней имеют ветвление. Иными словами, любой путь от корня до листа имеет длину $m$. Дерево с таким свойством единственно, оно имеет $2^m$ листов. Тогда при $n=3\cdot2^m$ мы получим в графе $\Gamma_n$ вершину, для которой применимо действие любыми образующими не менее $m$ раз. Это значит, что шар радиуса $m$ с центром в данной вершине целиком лежит в $\Gamma_n$.

Вершины графа $\Gamma_n$ подразделяем на внутренние и граничные. К первой категории относятся те, для которых любое из деревьев тройки нетривиально, а ко второй – все остальные. (Нетрудно проверить, что внутренних вершин в пределе будет $1/4$ от общего их числа.) Для каждой внутренней вершины можно вместо тройки деревьев рассмотреть $(x^3,x^n)$-диаграмму. У этой диаграммы можно рассмотреть множество клеток, нижняя часть которых является подпутём нижнего пути диаграммы. Будем говорить, что эти клетки образуют подошву диаграммы. Если мы её удалим, то получим какую-то $(x^3,x^s)$-диаграмму при некотором $s < n$, которая является вершиной графа $\Gamma_{s}$.

Предположим, что какое-то ребро графа $\Gamma_n$ соединяет две его внутренние вершины. Утверждается, что они имеют одинаковые “подошвы”. Это легко усматривается геометрически. В самом деле, пусть мы подняли какую-то каретку, чему соответствует удаление верхнего пути одной из клеток. Если при этом была затронута “подошва”, то образуются два ребра нижнего пути этой клетки (две отдельные вершины, являющиеся листьями, если говорить на языке деревьев), и при перемещении в другое место каретки одна из этих вершин остаётся нетронутой. А это значит, что мы перешли к граничной, а не внутренней вершине.

Из сказанного следует, что все внутренние вершины разбиваются в дизъюнктное объединение классов эквивалентности: в один класс попадают диаграммы с одной и той же “подошвой”. Получается, что без границы (множества граничных вершин) и инцидентных ей рёбер всё остальное распадается на не связанные между собой графы, каждый из которых является подграфом некоторого $\Gamma_{s}$ при $s < n$. Эти соображения могут быть использованы для построения потоков на графах по индукции. Основная трудность здесь состоит в том, что если граничная вершина соединена с несколькими внутренними, то мы не знаем правила, по которому следует распределять интенсивность потока. Сама задача состоит в том, чтобы обеспечить такой поток с границы, для которого приток в каждую внутреннюю вершину будет равен единице, а поток через каждое ребро не превосходит некоторой константы.

Заметим, что в этих терминах можно трактовать результат Мура из [58], где, при переводе рассуждений на другой язык, строятся потоки на графе и для данного $n$ потоки через ребро ограничены очень медленно растущей функцией – обратной $n$-кратной “башне” из экспонент. По этой причине мы предполагаем, что развитие идей статьи [58] могло бы помочь в доказательстве неаменабельности группы.

Перейдём теперь к описанию более простой модели для фрагментов графа Кэли. В графе $\Gamma_n$ вершинами являются достаточно сложные геометрические объекты – тройки деревьев. Мы сейчас добьёмся того, чтобы вершинами графа стали обычные геометрические точки. Столь же просто будут выглядеть и рёбра.

Рассмотрим дизъюнктное объединение всех корневых двоичных деревьев с заданным числом кареток, равным $n$. Тогда мы имеем $c_n$ таких деревьев. Рассмотрим произвольную вершину $v$ одного из деревьев. Если она не является самой верхней, то она входит в состав ровно одной каретки, расположенной над этой вершиной. Раскрасим такую каретку в красный цвет. Если её верхняя точка не является корнем дерева, то снова рассмотрим каретку, расположенную над этой вершиной, и также раскрасим её в красный цвет. Процесс будем продолжать до тех пор, пока не дойдём до корня дерева. Раскрашенное множество кареток начнём удалять сверху вниз, пока не дойдем до $v$. У нас получится корневой двоичный лес, который сделаем помеченным, выделяя дерево с корнем $v$. Такая процедура может быть проведена с любой вершиной любого из деревьев.

Назовём две вершины эквивалентными, если описанная процедура приводит к одинаковой картине, т. е. к одинаковым помеченным корневым двоичным лесам. Очевидно, что такое отношение $\sim$ на множестве вершин всех рассматриваемых деревьев в самом деле является эквивалентностью (нетрудно заметить, что общее число вершин в нашем дизъюнктном объединении равно $(2n+1)c_n$). Берём все имеющиеся вершины, эквивалентные отождествляем, получая вершины нового графа. Рёбра же будут устроены так: для каждой из кареток, состоящей из левого и правого отрезков, поставим на этих отрезках стрелки сверху вниз и пометим буквой $x_1$ левый отрезок, а буквой $\overline{x}_1$ правый отрезок. Подразумевается, что рёбра, соединяющие пары соответственно эквивалентных вершин, также будут отождествляться. То, что мы построили, является подграфом (левого) графа Кэли группы $F$ в симметричной системе групповых образующих $\{x_1,\overline{x}_1\}$ как бы в “рассыпанном” виде. Одна и та же вершина графа может присутствовать во многих экземплярах, и то же для рёбер.

Можно проследить, сколько раз одна и та же вершина $v$ появится в рассматриваемых деревьях. Если после удаления верхних кареток получился лес, для которого левее $v$ расположено $s$ деревьев, а правее неё имеется $t$ деревьев, то вершина $v$ будет присутствовать в количестве $\dfrac{(s+t)!}{s!\,t!}$ копий. Этот факт легко доказывается индукцией по $s+t$ при помощи свойств биномиальных коэффициентов.

Подытожим сказанное в виде отдельного утверждения.

Отметим, что рёбра с меткой $x_0$ фактически никуда не исчезают: их можно добавить, если с каждой кареткой связать треугольник, и тогда ребро, помеченное $x_0$, будет идти справа налево.

Подчеркнём также, что пути в графе Кэли можно теперь изображать на самих деревьях, и при этом можно “прыгать” от любой вершины к эквивалентной, продолжая путь. Раньше для изображения пути в графе $\Gamma_n$ надо было бы рисовать все встречающиеся в нём вершины в виде сложных картинок, а в новой модели такой необходимости уже нет.

Теперь перейдём к изложению нового алгоритма, решающего проблему равенства слов в группе $F$, без выхода за пределы группового алфавита $\{x_0,x_1\}$ и без изменения длины исследуемого слова. Сформулируем всё в виде отдельного утверждения, а потом его докажем. Напомним, что если слово равно 1 в группе $F$, то оно принадлежит коммутанту свободной группы (сумма показателей как по $x_0$, так и по $x_1$ равна нулю). Это следует из того, что определяющие соотношения обладают этим свойством. Поэтому только такие слова и рассматриваем.

Теорема 12.2. Пусть $w$ – групповое слово над алфавитом $\{x_0,x_1\}$ с нулевой суммой показателей при каждом из образующих. Опишем преобразование $\mathcal{T}$ слова $w$ на каждом шаге.

Запишем слово по окружности, представляя его в виде размеченного циклического графа. Будем обходить этот граф в одном из направлений, начиная с произвольной вершины, которой придаём вес 0. Каждая следующая вершина имеет тот же вес, что и предыдущая, если мы прошли по ребру с меткой $x_1^{\pm1}$. При прохождении по ребру с меткой $x_0$ вес следующей вершины увеличивается на 1. При прохождении по ребру с меткой $x_0^{-1}$ вес следующей вершины уменьшается на 1.

Если слово не содержит букв $x_1^{\pm1}$, то оно равно 1 в свободной группе, и потому равно 1 в $F$. В противном случае рассмотрим рёбра с меткой $x_1^{\pm1}$. Их концы имеют одинаковый вес. Выделим те рёбра с меткой $x_1^{\pm1}$, для которых этот вес максимален. Заменим их метки по правилу $x_1\mapsto x_0$, $x_1^{-1}\mapsto x_0^{-1}$. Получится слово той же длины, которое обозначим $\mathcal{T}(w)$.

Если в новом слове суммы показателей при $x_0$ и $x_1$ нулевые, то итерируем процесс, снова применяя преобразование $\mathcal{T}$. Если нет, то $w$ не равно 1 в $F$. Процесс оканчивается за конечное число шагов. Для равного 1 в группе $F$ слова мы должны в конце получить слово только от $x_0^{\pm1}$.

Доказательство. Заметим, что мы можем как проводить свободные сокращения в получающихся словах, так и не проводить. Можно взять за основу ту версию, когда сокращений мы не производим, работая со словом постоянной длины. Легко понять, что она чётна.

Обосновать достаточно то, что $w=1$ в $F$ тогда и только тогда, когда $\mathcal{T}(w)=1$ в $F$. Пусть мы выделили те вхождения $x_1^{\pm1}$, концы которых имеют максимальный вес. Припишем это значение веса самому ребру с меткой $x_1^{\pm1}$. Тогда слово $w$ с точностью до циклического сдвига и равенства в свободной группе имеет такой вид (мы выделяем все вхождения $x_1^{\pm1}$ максимального веса, не собирая их в степени): $x_1^{\pm1}u_1x_1^{\pm1}u_2\ldots x_1^{\pm1}u_k$.

Начнём с лёгкого случая, когда все слова $u_i$ ($1\leqslant i\leqslant k$) состоят только из букв $x_0^{\pm1}$. Тогда все они имеют нулевую сумму показателей в силу определения веса, т. е. равны 1 в свободной группе. В этом случае $w$ равно в свободной группе степени $x_1$, т. е. сумма показателей при $x_1$ должна быть нулевой. Тогда после замены букв $x_1$ на буквы $x_0$, согласно процедуре, получится свободно равное 1 слово. Если же сумма показателей при $x_1$ не равна нулю, то процесс оборвётся и $w$ здесь не равно 1 в $F$.

Теперь предположим, что в словах вида $u_i$ имеются вхождения букв $x_1^{\pm1}$. Выделим их, записывая

$$ \begin{equation*} u_i=x_0^{d_{i0}}x_1^{\pm1}x_0^{d_{i1}}\ldots x_1^{\pm1}x_0^{d_{i,m_i}} \end{equation*} \notag $$

с точностью до приведения в свободной группе.

Заметим, что любое слово вида $x_1^{\pm1}x_0^{-s_1}x_1^{\pm1}x_0^{-s_2}\ldots x_1^{\pm1}x_0^{-s_q}$ можно переписать как $x_1^{\pm1}(x_0^{-s_1}x_1^{\pm1}x_0^{s_1}) (x_0^{-(s_1+s_2)}x_1^{\pm1}x_0^{s_1+s_2})\ldots$ по тому же принципу (равенство в свободной группе). При этом если у нас получился “слог” вида $x_0^{-s}x_1^{\pm1}x_0^{s}$, то соответствующее ребро с меткой $x_1^{\pm1}$ имеет вес в точности $-s$. Ввиду этого, веса всех таких рёбер, для вхождений $x_1^{\pm1}$ в слова вида $u_i$, отрицательны, и после применения соотношений в группе $F$ эти “слоги” становятся равными $x_{s+1}^{\pm1}$, где $s > 0$.

Таким образом, после переписывания слова с точностью до равенства в $F$ все вхождения $x_0^{\pm1}$ исчезают и $w$ оказывается равным слову вида $x_1^{\pm1}v_1\ldots x_1^{\pm1}v_k$, где выделенные вхождения максимального веса остаются на своих местах, в то время как слова $u_i$ заменяются на групповые слова $v_i$ от образующих $x_2,x_3,\dots$ . (Заметим, что всё это мы делаем только в ходе обоснования алгоритма, а в ходе его работы нам расширять алфавит не приходится.)

Теперь сошлёмся на элементарную лемму 1.2, согласно которой если $w$ было равно 1 в $F$, то сумма показателей при выделенных вхождениях $x_1^{\pm1}$ равна нулю. Если она не равна нулю, то алгоритм на этом оканчивается с отрицательным ответом.

Осталось понять, что при условии равенства нулю суммы показателей в слове $x_1^{\delta_1}v_1\ldots x_1^{\delta_k}v_k$ можно сделать замены по принципу $x_1^{\pm1}\mapsto x_0^{\pm1}$ и от этого свойство слова быть равным 1 в $F$ не изменится. Это, по сути дела, следует из того, что $x_n^{x_0}=x_n^{x_1}$ при $n\geqslant 2$, но мы дадим чуть более подробное обоснование.

Проще всего у слова $x_1^{\delta_1}v_1\ldots x_1^{\delta_k}v_k$ рассмотреть подходящий циклический сдвиг, который обладает тем свойством, что $\delta_1+\cdots+\delta_j\leqslant 0$ для всех $j$ от $1$ до $k$. Это, по сути, тот же приём, что и выше, основанный на рассмотрении рёбер максимального веса. Здесь надо взять частичные суммы показателей и найти место, где они принимают максимальное значение. С этого места и начинаем читать циклический сдвиг, оставляя исходные обозначения. После применения соотношений в группе $F$ мы получим слово вида $v_1^{x_1^{r_1}}v_2^{x_1^{r_2}}\ldots v_k^{x_1^{r_k}}$, где все $r_1,r_2,\dots,r_k$ неотрицательны. Осталось заметить, что в этом случае замена $x_1$ на $x_0$ не меняет значения слова в $F$, так как слова $v_i$ являются произведениями букв $x_n^{\pm1}$ при $n\geqslant 2$ и $x_n^{x_1^r}=x_{n+r}=x_n^{x_0^r}$ при $r\geqslant 0$. Теорема доказана.

Можно привести простейшую иллюстрацию работы алгоритма из теоремы 12.2. Рассмотрим слово $w=x_0^{-2}x_1x_0^2x_1^{-1}x_0^{-1}x_1^{-1}x_0x_1$ (одно из определяющих соотношений). Легко проверить, что максимальный вес здесь будут иметь второе и четвёртое вхождения $x_1^{\pm1}$. После их переименования в $x_0^{\pm1}$ сохраняется баланс показателей. Слово $\mathcal{T}(w)$ приобретает вид $x_0^{-2}x_1x_0^2x_0^{-1}x_0^{-1}x_1^{-1}x_0x_0$ (сокращать в свободной группе можно, но не обязательно), и два оставшихся вхождения $x_1^{\pm1}$ приобретут одинаковый (а потому максимальный) вес. На следующем шаге они будут переименованы в $x_0^{\pm1}$.

Есть надежда, что данный алгоритм поможет как-то оценить количество слов данной длины, равных 1 в $F$. В частности, можно оценивать число слов, требующих заданного количества шагов работы алгоритма. Использование критерия Кестена–Григорчука, в случае получения успешной оценки, решило бы проблему аменабельности в ту или другую сторону.

Автор выражает благодарность В. Л. Попову за содействие при подготовке статьи к печати, а также анонимному рецензенту, высказавшему большое количество ценных замечаний.