Game: Group and Multi-Dimensional Chessboard

155 Views Asked by At

Let $G$ be a group and $S\subseteq G$. Consider a $d$-dimensional chessboard of size $n_1\times n_2\times \ldots \times n_d$, where $n_1,n_2,\ldots,n_d\in\mathbb{N}$. Each unit hypercube of the chessboard contains an element of $G$, which is called the label of the hypercube. A move consists of three parts:

(1) selecting an element $s\in S$,

(2) choosing a unit hypercube of the chessboard, say with index $\left(i_1,i_2,\ldots,i_d\right)$, and

(3) multiplying $s$ on the left to the label of every unit hypercube with index $\left(j_1,j_2,\ldots,j_d\right)$ such that $j_\mu\geq i_\mu$ for all $\mu=1,2,\ldots,d$.

The task is to make a finite sequence of moves from an arbitrary initial configuration to a situation in which every label is the identity $1_G$ of the group $G$. Here are the questions.

(a) If $S=G$, then justify that it is always possible to complete the task in $N:=n_1n_2\cdots n_d$ moves.

(b) Assume Part (a). Determine whether or not $N$ is the smallest integer $\nu$ such that, from every initial configuration, it is guaranteed that there exists a sequence of at most $\nu$ moves to complete the required task.

(c) If $S$ generates $G$ as a monoid (namely, for every $g\in G$, there exist $s_1,s_2,\ldots,s_l\in S$ with $l\in\mathbb{N}\cup\{0\}$ such that $g=s_1s_2\cdots s_l$), and there exists a natural number $\ell$ such that every element of $G$ is a product of at most $\ell$ (not necessarily distinct) elements of $S$, then verify that it is always possible to complete the task in $\ell n_1n_2\cdots n_d$ moves.

(d) Assume Part (c). Suppose that $\lambda$ is the smallest possible of such integers $\ell$. Is it true that there is an initial configuration that requires at least $\lambda n_1n_2\cdots n_d$ moves to complete the task?

(e) Suppose that $S$ generates $G$ as a monoid, but the length of an element of $G$ with respect to $S$ can be arbitrary large. (The length of $g\in G$ with respect to $S$ is the smallest integer $l\geq 0$ such that there exist $s_1,s_2,\ldots,s_l\in S$ for which $g=s_1s_2\cdots s_l$.) Prove that it is still possible to complete the task from any initial configuration in finitely many moves.

(f) Assume Part (e). For a given $k\in\mathbb{N}$, does there exist an initial configuration that requires at least $k$ moves to complete the task?

(g) Show that the required task is always possible if and only if $S$ generates $G$ as a monoid.

Here, $1_G$ is considered to be the product of $0$ element of $S$. The answers to Parts (b) and (d) are unknown, but for abelian groups $G$, the answers are both affirmative. This problem is inspired by $n\times n$ chessboard game with coins (in which $d=2$, $n_1=n_2=n$, $G=\left\langle s\,|\,s^2=1_G\right\rangle$, and $S=\{s\}$). There, I also posted a sketch of a proof for the case where $G=\left\langle s\,|\,s^t=1_G\right\rangle$ for a fixed $t\in\mathbb{N}$ and $S=\{s\}$.

2

There are 2 best solutions below

0
On

This is not an answer, just a group-theoretic reformulation of the question. I'm posting here because I don't want to overload the question with too much text.

If $S$ generates $G$ as a monoid, then let $\lambda_G(S)$ denote the maximum length of elements of $G$ with respect to $S$ (where we set $\lambda_G(S):=\infty$ if there are no longest elements of $G$ with respect to $S$). Denote by $[n]$ the set $\{1,2,\ldots,n\}$ for each $n\in\mathbb{N}$. For $i_1\in\left[n_1\right]$, $i_2\in\left[n_2\right]$, $\ldots$, $i_d\in\left[n_d\right]$, and $g\in G$, define $T_{i_1,i_2,\ldots,i_d}(g)$ to be the element $\left(t_{j_1,j_2,\ldots,j_d}\right)_{j_1\in\left[n_1\right],j_2\in\left[n_2\right],\ldots,j_d\in\left[n_d\right]}$ of $\mathcal{G}:=G^{n_1\times n_2\times\ldots n_d}$ such that $t_{j_1,j_2,\ldots,j_d}=g^{-1}$ if $j_\mu\geq i_\mu$ for all $\mu=1,2,\ldots,d$, whereas $t_{j_1,j_2,\ldots,j_d}=1_G$ otherwise. Write $\tau(S)$ for $$\left\{T_{i_1,i_2,\ldots,i_d}(s)\,|\,s\in S\text{ and }i_\mu\in\left[n_\mu\right]\text{ for all }\mu=1,2,\ldots,d\right\}\,.$$

(a) Justify that $\tau(G)$ generates $\mathcal{G}$ as a monoid and $\lambda_\mathcal{G}\big(\tau(G)\big)\leq n_1n_2\cdots n_d$.

(b) Determine whether $\lambda_\mathcal{G}\big(\tau(G)\big)=n_1n_2\cdots n_d$.

(c) If $S$ generates $G$ as a monoid and $\lambda_G(S)<\infty$, verify that $\tau(S)$ generates $\mathcal{G}$ as a monoid and $\lambda_\mathcal{G}\big(\tau(S)\big)\leq \lambda_G(S)\,n_1n_2\cdots n_d$.

(d) Is it true that $\lambda_\mathcal{G}\big(\tau(S)\big)= \lambda_G(S)\,n_1n_2\cdots n_d$, provided that $S$ generates $G$ as a monoid and $\lambda_G(S)<\infty$?

(e) Prove in general that, if $S$ generates $G$ as a monoid, then $\tau(S)$ generates $\mathcal{G}$ as a monoid.

(f) Does it hold that $\lambda_\mathcal{G}\big(\tau(S)\big)=\infty$, given that $S$ generates $G$ as a monoid and $\lambda_G(S)=\infty$?

(g) Show that $\tau(S)$ generates $\mathcal{G}$ as a monoid if and only if $S$ generates $G$ as a monoid.


The answers to Parts (b) and (d) may be "no" (but I believe that the answer to (b) is "yes"). I now believe that (d) is false for most pairs $(G,S)$. A probable counterexample is $d=1$, $n_1=2$, $G=\big\langle a,b\,|\,a^2=1_G,\,b^3=1_G,\text{ and }ba=ab^2\big\rangle$ (i.e., the dihedral group of order $6$), and $S=\left\{a,b\right\}$. I think that $\lambda_\mathcal{G}\big(\tau(S)\big)=4<6=\lambda_G(S)\,n_1$, but I am not certain whether I have made any errors.

If the answer to (d) is indeed negative, it may make sense to ask the following question: asymptotically, how bad does $\lambda_{\mathcal{G}}\big(\tau(S)\big)$ deviates from $\lambda_G(S)$? That is, it may be of interest to compute $$\underline{\lambda}^d_G(S):=\liminf_{\prod\limits_{\mu=1}^d\,n_\mu\,\to\,\infty}\,\frac{\lambda_{\mathcal{G}}\big(\tau(S)\big)}{\prod\limits_{\mu=1}^d\,n_\mu}\text{ and }\overline{\lambda}^d_G(S):=\limsup_{\prod\limits_{\mu=1}^d\,n_\mu\,\to\,\infty}\,\frac{\lambda_{\mathcal{G}}\big(\tau(S)\big)}{\prod\limits_{\mu=1}^d\,n_\mu}\,,$$ or even $\underline{\Lambda}_G(S):=\lim\limits_{d\to\infty}\,\underline{\lambda}^d_G(S)$ and $\overline{\Lambda}_G(S):=\lim\limits_{d\to\infty}\,\overline{\lambda}^d_G(S)$.


Generalization: Each unit hypercube $\left(i_1,i_2,\ldots,i_d\right)\in\left[n_1\right]\times \left[n_2\right]\times\ldots\left[n_d\right]$ is associated to a left $G$-set $M_{i_1,i_2,\ldots,i_d}$ and a label of this hypercube is an element of $M_{i_1,i_2,\ldots,i_d}$. A move is defined as before. Fix $m_{i_1,i_2,\ldots,i_d}\in M_{i_1,i_2,\ldots,i_d}$ for all $i_\mu\in\left[n_\mu\right]$, $\mu=1,2,\ldots,d$. The task is to make a finite sequence of moves from an arbitrary initial configuration to a situation where the label of the unit hypercube $\left(i_1,i_2,\ldots,i_d\right)$ is $m_{i_1,i_2,\ldots,i_d}$ for every indices $\left(i_1,i_2,\ldots,i_d\right)\in\left[n_1\right]\times \left[n_2\right]\times\ldots\left[n_d\right]$. Then, this task is always possible if and only if

(i) $G$ acts transitively on every $M_{i_1,i_2,\ldots,i_d}$, and

(ii) the image of $S$ under the canonical projection $G\,\to \, G/K_{i_1,i_2,\ldots,i_d}$, where $K_{i_1,i_2,\ldots,i_d}$ is the kernel of the $G$-action on $M_{i_1,i_2,\ldots,i_d}$, generates $G/K_{i_1,i_2,\ldots,i_d}$ as a monoid for every $\left(i_1,i_2,\ldots,i_d\right)$ in $\left[n_1\right]\times \left[n_2\right]\times\ldots\left[n_d\right]$.

You can similarly ask questions (a), (b), (c), (d), (e), and (f), but I shall leave them to you.

1
On

(a) We can enumerate the unit hypercubes in such a way (namely in lexic order) that every earlier hypercube is not modified by moves referring to later ones. This allows modifying the hypercubes one by one and once and for all, each in a single move.

(b) This may depend on $G$, but for $G=\Bbb Z$ it is easy to come up with an initial configuration that does require so many moves. Just let the values grow "fast enough"

(c) Any solution to (a) can be rewritten by replacing elements of $G$ by up to $\ell$ elements of $S$.

(d) Not in general. It may happen that only few elements of $G$ do require $\ell$ factors.

(e) We still can replace a finite solution from (a) with a finite solution for the problem at hand

(f) Yes. Already to neutralize the lowest corner, we may need a complicated group element

(g) If $S$ does not generate $G$ as a monoid, then it may not even possible to turn the lowest corner into $1_G$