6
$\begingroup$

Consider paths through the lamplighter group $\mathbb{Z}_n\wr\mathbb{Z}$ with steps consisting of moving left, moving right, and toggling the lamp at the current position. How many paths of length $m$ visit an unlit lamp $k$ times, with all lamps initially off?

In other words, let $D$ be the set of "dark paths", i.e. paths where the lamp at the final position is off. This set is equinumerous with the set of paths $D'$ that leave the lamp at the origin off. A grammar for $D'$ is

$$D' = (((RM_RL+LM_LR)^* T)^n)^* (RM_RL+LM_LR)^* (\varepsilon+RM_R(RM_R)^*+LM_L(LM_L)^*)$$

where \begin{align} M_R=(T+RM_RL)^* \\ M_L=(T+LM_LR)^* \end{align}

are left- and right-leaning Motzkin paths, respectively. Thus the generating function for $D$ at $z$ is $D'$ with $L = R = T = z$:

\begin{align} D(z)=\frac{1-z(2+3z+\sqrt{1-2z-3z^2})}{(1-3z)(1-2z-4z^2)\left(1-\left(\frac{z}{z+\sqrt{1-2z-3z^2}}\right)^n\right)} \end{align}

I am interested in obtaining the generating function $f$ such that

$$[x^m y^k]f_n(x,y) = \{w \in \{L,R,T\}^m : |\text{Pref}(w) \cap D| = k\}$$

where $\text{Pref}(w)$ is the set of $|w|+1$ prefixes of $w$. For example, $$f_2(x,y) = y + x(y+2y^2) + x^2(5y^2+4y^3) + x^3(5y^2+14y^3+8y^4) + \dots$$

I can establish some lower bounds. For example, we can consider only words where the lamplighter doesn't move left (or right) after toggling a lamp, so there's only one lamp state to keep track of at a time. Is it possible to generalize this to the case where the lamplighter can encounter multiple previously-toggled lamps?

Improve this question
$\endgroup$
5
  • $\begingroup$ What "encounter an unlit lamp" means? $\endgroup$
    – Max Alekseyev
    Commented Jan 21, 2019 at 20:29
  • $\begingroup$ @MaxAlekseyev Say an element $(a,b) \in G \wr H = G^{\oplus H} \rtimes H$ is "unlit" if $a(b) = e_G$, i.e. the lamp at the current position is off (the identity element of $G$). A word $w \in (G \wr H)^*$ encounters an unlit lamp $m$ times if it has $m$ prefixes that result in an unlit element. For example, with standard generators for $\mathbb{Z}_2 \wr \mathbb{Z}$, the word $atat^{-1}$ results in the sequence (unlit, lit, unlit, lit, lit) and so encounters an unlit lamp 2 times. $\endgroup$
    – user76284
    Commented Jan 21, 2019 at 20:31
  • $\begingroup$ In your example, don't you mean the sequence is (unlit, lit, unlit, lit) -- there are 4 steps so the sequence should be 4 in length. If I understand it, labeling the two positions in $\Bbb{Z}_2$ as $0$ and $1$ you move to $1$ (unlit), toggle (now $1$ is lit), move to $0$ (unlit) and toggle (lit). But what is the meaning of your $t^{-1}$ notation; do you imply that the lamp state is also an arbitrary integer and "toggle" means one of "increase the state" or "decrease the state"? If that is the case, then the terminology "toggle" is misleading, I think. $\endgroup$
    – Mark Fischler
    Commented Feb 6, 2019 at 19:12
  • $\begingroup$ @MarkFischler A word of length $n$ has $n+1$ prefixes (including both the first and last positions). You didn't count the final position. $a,t,t^{-1}$ denote "toggle", "move right", and "move left" respectively. Not sure what to call "toggle" when a lamp has more than two states. $\endgroup$
    – user76284
    Commented Feb 6, 2019 at 19:14
  • 1
    $\begingroup$ Aha; given your example was in $\Bbb{Z}_2$ I took "a" to mean move (the direction is moot in $\Bbb{Z}_2$) and "t" to mean toggle, rather than "t" to mean translate and "a" to mean toggle. Your example path is start at 0 (unlit), toggle on (lit), move to $1$ (unlit), toggle (1 is lit), move to $0$ (lit). Of course, a generalization is that at each point in the translational $\Bbb{Z}_n$) there is a 1-d random walk, and each step in the process consists of moving to the left or right, or increasing or decreasing the position on the random walk at the current spot. $\endgroup$
    – Mark Fischler
    Commented Feb 6, 2019 at 19:23

0

Reset to default

You must log in to answer this question.