Skip to main content
show how to get lots of different z coordinates
Source Link
Sean Eberhard
  • 9.7k
  • 30
  • 57

In fact $\omega_{G/Z}(SZ/Z) = \omega_G(S)$, despite the plausible-sounding examples in the comments. The argument is actually embarassingly simple. Let $S_1$ be a lift of $SZ/Z$ to $G$, so that $|S_1| = |SZ/Z|$ and $S \subset S_1 Z_1$ for some $Z_1 \subset Z$. Then $S^n = S_1^n Z_1^n$, and $Z_1^n$ grows polynomially, so $\omega_G(S) \leq |S_1| = |SZ/Z|$. Thus also $\omega_G(S^n) \leq |S^nZ/Z|$, but $\omega_G(S^n) = \omega_G(S)^n$ and $|S^nZ/Z|^{1/n} \to \omega_{G/Z}(SZ/Z)$.

The examples in the comments do however have the property that $|S^n \cap Z|$ grows exponentially, but this is not obvious. Let $G$ be Hall's group (as suggested by YCor) of matrices of the form $$\left( \begin{array}{ccc} 1 & x & z \\ 0 & t^k & y \\ 0 & 0 & 1 \end{array} \right),$$ where $k \in \mathbf{Z}$ and $x,y,z\in A = \mathbf{F}_p[t^{\pm 1}]$. Let $H$ be the subgroup defined by $k=0$ and $x,y,z\in\mathbf{F}_p$, let $\varphi$ be the diagonal matrix $(1, t, 1)$. Let $S$ be the symmetric generating set $H \varphi^{\pm1} H$. Modulo $Z$, this group is just the lamplighter group $\mathbf{Z}^2 \wr \mathbf{Z}$, and the generating set $S$ represents "change a lamp, take a step, change a lamp". The $(x, y)$ coordinates therefore record the lamp configuration at the end of the walk, and the $z$ coodinate records second-order information. To be precise, we have $$S^n = \bigcup H^{\varphi^{i_0}} H^{\varphi^{i_1}} \cdots H^{\varphi^{i_n}} \varphi^{-i_n},$$ where the union is over all $n$-step walks $i_0, \dots, i_n$ in $\mathbf{Z}$, by which I mean $i_0=0$ and $|i_t - i_{t-1}| = 1$ for each $t > 0$. We have $$H^{\varphi^{i_0}} H^{\varphi^{i_1}} \cdots H^{\varphi^{i_n}} = \left\{\left( \begin{array}{ccc} 1 & x_0 t^{i_0} + \cdots + x_n t^{i_n} & \sum_{s < t} x_s y_t t^{i_s - i_t} + z_0 + \cdots + z_n \\ 0 & 1 & y_0 t^{-i_0} + \cdots + y_n t^{-i_n} \\ 0 & 0 & 1 \end{array} \right) \colon x_i, y_j, z_k \in \mathbf{F}_p \right\}.$$ Thus the $z$ coordinate counts differences $i_s - i_t$ between lamp positions where the first lamp was lit before the second lamp. Now consider a walk of length $4n$ consisting of $n$ steps right, $n$ steps left,the following form: first light an $n$ steps right$x$ lamp, then walk around lighting $n$ steps left$y$ lamps however you like, wherethen return to the finalorigin and extinguish the $n$ steps left$x$ lamp, then go extinguish all the $y$ lamps, and finally return to the origin. TheIf you do this then your final $x$ and $y$ coordinates are zero by design, andsince they just record the final lamp configuration, but your $z$ coordinate is $$\sum_d t^d \sum_{\substack{s < t \\ i_s - i_t = d}} x_s y_t.$$ I now need to check that this quadratic form is sufficiently nondegenerate that one gets lotsrecords the configuration of different $z$ coordinates$y$ lamps between the two $x$ lightings. I admit I haven't quite doneThis argument proves that, but it seems reasonable $|S^n \cap Z|$ grows at least as fast as $p^{n/4}$.

So, Q1: no. Q3: no. Q2: still mysterious.

In fact $\omega_{G/Z}(SZ/Z) = \omega_G(S)$, despite the plausible-sounding examples in the comments. The argument is actually embarassingly simple. Let $S_1$ be a lift of $SZ/Z$ to $G$, so that $|S_1| = |SZ/Z|$ and $S \subset S_1 Z_1$ for some $Z_1 \subset Z$. Then $S^n = S_1^n Z_1^n$, and $Z_1^n$ grows polynomially, so $\omega_G(S) \leq |S_1| = |SZ/Z|$. Thus also $\omega_G(S^n) \leq |S^nZ/Z|$, but $\omega_G(S^n) = \omega_G(S)^n$ and $|S^nZ/Z|^{1/n} \to \omega_{G/Z}(SZ/Z)$.

The examples in the comments do however have the property that $|S^n \cap Z|$ grows exponentially, but this is not obvious. Let $G$ be Hall's group (as suggested by YCor) of matrices of the form $$\left( \begin{array}{ccc} 1 & x & z \\ 0 & t^k & y \\ 0 & 0 & 1 \end{array} \right),$$ where $k \in \mathbf{Z}$ and $x,y,z\in A = \mathbf{F}_p[t^{\pm 1}]$. Let $H$ be the subgroup defined by $k=0$ and $x,y,z\in\mathbf{F}_p$, let $\varphi$ be the diagonal matrix $(1, t, 1)$. Let $S$ be the symmetric generating set $H \varphi^{\pm1} H$. Modulo $Z$, this group is just the lamplighter group $\mathbf{Z}^2 \wr \mathbf{Z}$, and the generating set $S$ represents "change a lamp, take a step, change a lamp". The $(x, y)$ coordinates therefore record the lamp configuration at the end of the walk, and the $z$ coodinate records second-order information. To be precise, we have $$S^n = \bigcup H^{\varphi^{i_0}} H^{\varphi^{i_1}} \cdots H^{\varphi^{i_n}} \varphi^{-i_n},$$ where the union is over all $n$-step walks $i_0, \dots, i_n$ in $\mathbf{Z}$, by which I mean $i_0=0$ and $|i_t - i_{t-1}| = 1$ for each $t > 0$. We have $$H^{\varphi^{i_0}} H^{\varphi^{i_1}} \cdots H^{\varphi^{i_n}} = \left\{\left( \begin{array}{ccc} 1 & x_0 t^{i_0} + \cdots + x_n t^{i_n} & \sum_{s < t} x_s y_t t^{i_s - i_t} + z_0 + \cdots + z_n \\ 0 & 1 & y_0 t^{-i_0} + \cdots + y_n t^{-i_n} \\ 0 & 0 & 1 \end{array} \right) \colon x_i, y_j, z_k \in \mathbf{F}_p \right\}.$$ Thus the $z$ coordinate counts differences $i_s - i_t$ between lamp positions where the first lamp was lit before the second lamp. Now consider a walk of length $4n$ consisting of $n$ steps right, $n$ steps left, $n$ steps right, $n$ steps left, where the final $n$ steps left extinguish all the lamps. The $x$ and $y$ coordinates are zero by design, and the $z$ coordinate is $$\sum_d t^d \sum_{\substack{s < t \\ i_s - i_t = d}} x_s y_t.$$ I now need to check that this quadratic form is sufficiently nondegenerate that one gets lots of different $z$ coordinates. I admit I haven't quite done that, but it seems reasonable.

So, Q1: no. Q3: no. Q2: still mysterious.

In fact $\omega_{G/Z}(SZ/Z) = \omega_G(S)$, despite the plausible-sounding examples in the comments. The argument is actually embarassingly simple. Let $S_1$ be a lift of $SZ/Z$ to $G$, so that $|S_1| = |SZ/Z|$ and $S \subset S_1 Z_1$ for some $Z_1 \subset Z$. Then $S^n = S_1^n Z_1^n$, and $Z_1^n$ grows polynomially, so $\omega_G(S) \leq |S_1| = |SZ/Z|$. Thus also $\omega_G(S^n) \leq |S^nZ/Z|$, but $\omega_G(S^n) = \omega_G(S)^n$ and $|S^nZ/Z|^{1/n} \to \omega_{G/Z}(SZ/Z)$.

The examples in the comments do however have the property that $|S^n \cap Z|$ grows exponentially, but this is not obvious. Let $G$ be Hall's group (as suggested by YCor) of matrices of the form $$\left( \begin{array}{ccc} 1 & x & z \\ 0 & t^k & y \\ 0 & 0 & 1 \end{array} \right),$$ where $k \in \mathbf{Z}$ and $x,y,z\in A = \mathbf{F}_p[t^{\pm 1}]$. Let $H$ be the subgroup defined by $k=0$ and $x,y,z\in\mathbf{F}_p$, let $\varphi$ be the diagonal matrix $(1, t, 1)$. Let $S$ be the symmetric generating set $H \varphi^{\pm1} H$. Modulo $Z$, this group is just the lamplighter group $\mathbf{Z}^2 \wr \mathbf{Z}$, and the generating set $S$ represents "change a lamp, take a step, change a lamp". The $(x, y)$ coordinates therefore record the lamp configuration at the end of the walk, and the $z$ coodinate records second-order information. To be precise, we have $$S^n = \bigcup H^{\varphi^{i_0}} H^{\varphi^{i_1}} \cdots H^{\varphi^{i_n}} \varphi^{-i_n},$$ where the union is over all $n$-step walks $i_0, \dots, i_n$ in $\mathbf{Z}$, by which I mean $i_0=0$ and $|i_t - i_{t-1}| = 1$ for each $t > 0$. We have $$H^{\varphi^{i_0}} H^{\varphi^{i_1}} \cdots H^{\varphi^{i_n}} = \left\{\left( \begin{array}{ccc} 1 & x_0 t^{i_0} + \cdots + x_n t^{i_n} & \sum_{s < t} x_s y_t t^{i_s - i_t} + z_0 + \cdots + z_n \\ 0 & 1 & y_0 t^{-i_0} + \cdots + y_n t^{-i_n} \\ 0 & 0 & 1 \end{array} \right) \colon x_i, y_j, z_k \in \mathbf{F}_p \right\}.$$ Thus the $z$ coordinate counts differences $i_s - i_t$ between lamp positions where the first lamp was lit before the second lamp. Now consider a walk of the following form: first light an $x$ lamp, then walk around lighting $y$ lamps however you like, then return to the origin and extinguish the $x$ lamp, then go extinguish all the $y$ lamps, and finally return to the origin. If you do this then your final $x$ and $y$ coordinates are zero, since they just record the final lamp configuration, but your $z$ coordinate records the configuration of $y$ lamps between the two $x$ lightings. This argument proves that $|S^n \cap Z|$ grows at least as fast as $p^{n/4}$.

So, Q1: no. Q3: no. Q2: still mysterious.

Source Link
Sean Eberhard
  • 9.7k
  • 30
  • 57

In fact $\omega_{G/Z}(SZ/Z) = \omega_G(S)$, despite the plausible-sounding examples in the comments. The argument is actually embarassingly simple. Let $S_1$ be a lift of $SZ/Z$ to $G$, so that $|S_1| = |SZ/Z|$ and $S \subset S_1 Z_1$ for some $Z_1 \subset Z$. Then $S^n = S_1^n Z_1^n$, and $Z_1^n$ grows polynomially, so $\omega_G(S) \leq |S_1| = |SZ/Z|$. Thus also $\omega_G(S^n) \leq |S^nZ/Z|$, but $\omega_G(S^n) = \omega_G(S)^n$ and $|S^nZ/Z|^{1/n} \to \omega_{G/Z}(SZ/Z)$.

The examples in the comments do however have the property that $|S^n \cap Z|$ grows exponentially, but this is not obvious. Let $G$ be Hall's group (as suggested by YCor) of matrices of the form $$\left( \begin{array}{ccc} 1 & x & z \\ 0 & t^k & y \\ 0 & 0 & 1 \end{array} \right),$$ where $k \in \mathbf{Z}$ and $x,y,z\in A = \mathbf{F}_p[t^{\pm 1}]$. Let $H$ be the subgroup defined by $k=0$ and $x,y,z\in\mathbf{F}_p$, let $\varphi$ be the diagonal matrix $(1, t, 1)$. Let $S$ be the symmetric generating set $H \varphi^{\pm1} H$. Modulo $Z$, this group is just the lamplighter group $\mathbf{Z}^2 \wr \mathbf{Z}$, and the generating set $S$ represents "change a lamp, take a step, change a lamp". The $(x, y)$ coordinates therefore record the lamp configuration at the end of the walk, and the $z$ coodinate records second-order information. To be precise, we have $$S^n = \bigcup H^{\varphi^{i_0}} H^{\varphi^{i_1}} \cdots H^{\varphi^{i_n}} \varphi^{-i_n},$$ where the union is over all $n$-step walks $i_0, \dots, i_n$ in $\mathbf{Z}$, by which I mean $i_0=0$ and $|i_t - i_{t-1}| = 1$ for each $t > 0$. We have $$H^{\varphi^{i_0}} H^{\varphi^{i_1}} \cdots H^{\varphi^{i_n}} = \left\{\left( \begin{array}{ccc} 1 & x_0 t^{i_0} + \cdots + x_n t^{i_n} & \sum_{s < t} x_s y_t t^{i_s - i_t} + z_0 + \cdots + z_n \\ 0 & 1 & y_0 t^{-i_0} + \cdots + y_n t^{-i_n} \\ 0 & 0 & 1 \end{array} \right) \colon x_i, y_j, z_k \in \mathbf{F}_p \right\}.$$ Thus the $z$ coordinate counts differences $i_s - i_t$ between lamp positions where the first lamp was lit before the second lamp. Now consider a walk of length $4n$ consisting of $n$ steps right, $n$ steps left, $n$ steps right, $n$ steps left, where the final $n$ steps left extinguish all the lamps. The $x$ and $y$ coordinates are zero by design, and the $z$ coordinate is $$\sum_d t^d \sum_{\substack{s < t \\ i_s - i_t = d}} x_s y_t.$$ I now need to check that this quadratic form is sufficiently nondegenerate that one gets lots of different $z$ coordinates. I admit I haven't quite done that, but it seems reasonable.

So, Q1: no. Q3: no. Q2: still mysterious.