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

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

Определение

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

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

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

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

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

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

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

Рост

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

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

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

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

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

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

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

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

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

Примечания

1. Kaimanovic V. A. , Vershik A. M. . (англ.) // The Annals of Probability. — 1983. — Vol. 11 , iss. 3 . — P. 457-490 . — doi : .
2. Clay M. , Margalit D. . (англ.) . — Princeton, NJ Oxford: Princeton University Press, 2017. — ISBN 9780691158662 . 9 февраля 2023 года.

Литература

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