Лампочная группа

Лампочная группа — группа, определённым образом описывающая деятельность фонарщика. Также используются названия группа мигающих лампочек и группа фонарщика (от англ. lamplighter group).

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

Определение

Лампочная группа изоморфна прямому сплетению

$\mathbb {Z} /2\mathbb {Z} \wr \mathbb {Z} =\left(\bigoplus _{-\infty }^{\infty }\mathbb {Z} /2\mathbb {Z} \right)\rtimes \mathbb {Z}$

циклической группы порядка два и бесконечной циклической группы.

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

$\dots ,l_{-2},l_{-1},l_{0},l_{1},l_{2},l_{3},\dots$,

каждый из которых может быть включён или выключен, и фонарщика, находящегося напротив одного из фонарей $l_{k}$. Так, положение фонарщика кодируется элементом $k$ группы $\mathbb {Z}$. Конфигурация фонарей же задаётся элементом бесконечной прямой суммы

$\bigoplus _{-\infty }^{\infty }\mathbb {Z} /2\mathbb {Z} ,$

копий циклической группы $\mathbb {Z} /2\mathbb {Z} =\{0,1\}$ порядка два, где элемент $0$ соответствует потушенной керосиновой лампе, а $1$ — зажжённой, причем, как подразумевает определение прямой суммы, в каждой такой конфигурации зажжено лишь конечное число ламп.

Лампочная группа имеет две образующие: $t$ и $a$. Образующая $t$ увеличивает на единицу число $k$, то есть перемещает фонарщика к следующей лампе, так что обратный элемент $t^{-1}$ уменьшает число $k$ на единицу. Образующая $a$ изменяет состояние лампы $l_{k}$ на противоположное, то есть зажигает выключенные лампы и тушит горящие. Умножение элементов группы соответствует последовательному применению данных операций.

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

Свойства

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

Копредставление

Стандартное задание лампочной группы возникает из структуры прямого cплетения:

$\langle a,t\mid a^{2}=1;\ [t^{m}at^{-m},t^{n}at^{-n}]=1$ для $m,n\in \mathbb {Z} \rangle$,

которое может быть упрощено до

$\langle a,t\mid a^{2}=1;\ (at^{n}at^{-n})^{2}=1$ для $n\in \mathbb {Z} \rangle$.

Отсутствие конечного задания

Указанное выше задание образующими и соотношениями имеет бесконечное количество соотношений. В действительности лампочная группа не является конечно представимой.

Рост

В образующих $a$ и $t$ лампочная группа имеет экспоненциальную степень роста. При замене этих образующих образующими $a$ и $at$ логарифм роста уменьшается практически в два раза.

Матричное представление

Лампочная группа изоморфна группе матриц вида

${\begin{pmatrix}x^{k}&P(x)\\0&1\end{pmatrix}},$

где $k\in \mathbb {Z}$ и $P(x)$ пробегает множество всех многочленов из $\mathbb {Z} /2\mathbb {Z} [x,x^{-1}]$. Изоморфизм имеет вид

${\begin{aligned}t&\mapsto {\begin{pmatrix}x&0\\0&1\end{pmatrix}}\\a&\mapsto {\begin{pmatrix}1&1\\0&1\end{pmatrix}}.\end{aligned}}$

Вариации и обобщения

Простейшим развитием описанного выше действия является действие групп $\mathbb {Z} /n\mathbb {Z} \wr \mathbb {Z}$ на аналогичных конфигурациях, в которых лампы могут иметь не два состояния, а $n\in \mathbb {N}$. При таком обобщении многие свойства групп поменяются незначительно.

Интерпретация, аналогичная описанной выше, может быть дана произвольным спелетениям $G\wr H$. В этом случае элементы группы $H$ могут быть мыслимы как фонари, а элементы группы $G$ — как их некоторые состояния. Выбирая образующие групп $G$ и $H$, можно считать, что фонарщик перемещается по графу Кэли группы $H$ и на каждом шаге применяет к ближайшему фонарю одну из операций, соответствующих образующим группы $G$.

Литература

• Volodymyr Nekrashevych, 2005, Self-Similar Groups, Mathematical Surveys and Monographs v. 117, American Mathematical Society, ISBN 0-8218-3831-8.