In mathematics, the lamplighter group L of group theory is the restricted wreath product
The name of the group comes from viewing the group as acting on a doubly infinite sequence of street lamps
each of which may be on or off, and a lamplighter standing at some lamp
An equivalent description for this, called the base group
is an infinite direct sum of copies of the cyclic group
corresponds to a light that is on, and the direct sum is used to ensure that only finitely many lights are on at once.
to encode which bulbs are illuminated.
There are two generators for the group: the generator t increments k, so that the lamplighter moves to the next lamp (t -1 decrements k), while the generator a means that the state of lamp lk is changed (from off to on or from on to off).
Group multiplication is done by "following" these operations.
We may assume that only finitely many lamps are lit at any time, since the action of any element of L changes at most finitely many lamps.
The number of lamps lit is, however, unbounded.
The Turing machine has unbounded memory, but has only used a finite amount of memory at any given time.
Moreover, the Turing machine's head is analogous to the lamplighter.
The standard presentation for the lamplighter group arises from the wreath product structure The growth rate of the group, the function describing the number of group elements that can be formed as a product of
, is generally defined with respect to these two generators
This is exponential, with the golden ratio as its base, the same rate as the growth of the Fibonacci numbers.
[1] In some cases the growth rate is studied with respect to two different generators
, changing the logarithm of the growth rate by at most a factor of 2.
It has infinitely many relations, as specified by the indices
In fact there is no finite presentation for the lamplighter group, that is, it is not finitely presented.
to be a formal variable, the lamplighter group
is isomorphic to the group of matrices where
[2] Using the presentations above, the isomorphism is given by One can also define lamplighter groups
The classical lamplighter group is recovered when
Higher dimensional versions of these groups of the form