Wednesday, May 8, 2013

A cute application of Burnside's lemma

 I would like to discuss   a cute application of Burnside's lemma to a  question I learned on Mathoverflow.

First let me  present Burnside's lemma.

Burnside's lemma   Let $X$ be a finite set and $G$ a finite group acting on   $X$,
$$ G\times X\to X,\;\; (g,x)\mapsto g\cdot x. $$
Denote by $G\backslash  X$ be the space of orbits of this action. For each $g\in G$ we denote by $X^g$ the set of points in $X$ fixed by $g$
$$X^g:=\lbrace x\in X;\;\;g\cdot x=x\rbrace. $$
Then
$$ |G\backslash X|=\frac{1}{|G|} \sum_{g\in G} |X^g|,  $$
where $|A|$ denotes the cardinality of a set $A$.

Proof.   Look at the set $\newcommand{\bZ}{\mathbb{Z}}$ $\newcommand{\eF}{\mathscr{F}}$
$$ \eF = \bigl\lbrace (g,x)\in G\times X;\;\;g\cdot x= x\bigr\rbrace. $$
It defines a tautological double "fibration"
$$ G\stackrel{\ell}{\longleftarrow} \eF \stackrel{r}{\longrightarrow} X, $$
where the maps $\ell$ and $r$ are induced by  the canonical projections $G\leftarrow G\times X$ and $G\times X\to X$. We deduce

$$ \sum_{g\in G}|\ell^{-1}(g)|=|\eF|=\sum_{x\in X} |r^{-1}(x)|.  $$

Observe that the fiber $\ell^{-1}(g)$ can  be identified with the set $X^g$ so that

\begin{equation}
\sum_{g\in G}|X^g|=\sum_{x\in X} |r^{-1}(x)|. \tag{1} \label{1}
\end{equation}

For any $x\in X$ the fiber $r^{-1}(x)$ can be identified with the stabilizer $G_x$ of $x$,
$$ G_x=\bigl\lbrace g\in G;\;\; g\cdot x =x\bigr\rbrace. $$
If $x, y$ are in the same orbit of $G$ then $|G_x|=|G_y|$. Indeed, if $y=g\cdot x$ then $G_y=gG_xG^{-1}$.  

The function $x\mapsto |r^{-1}(x)|$ is  thus constant along the orbits of $G$ on $X$.   Thus the contribution of a single orbit $G\cdot x_0$ to the sum $\sum_x|r^{-1}(x)|$ is $|G_{x_0}|\cdot |G\cdot x_0|=|G|$. This  shows that

$$ \sum_{x\in X} |r^{-1}(x)|=  |G|\times \mbox{the number of orbits} =|G|\times |G\backslash X|. $$
 The desired conclusion now follows from (\ref{1}). $\Box$

I can now discuss the  problem that prompted this post. It is about certain  planar lattice walks.   The  allowable steps  of this  walk belong to the collection $\newcommand{\eS}{\mathscr{S}}$ $\newcommand{\be}{\boldsymbol{e}}$ $\newcommand{\bR}{\mathbb{R}}$ $\newcommand{\bs}{\boldsymbol{s}}$

$$\eS=\lbrace \pm\be_1,\pm\be_2\rbrace\subset \bR^2,\;\;\be_1=(1,0),\;\;\be_2=(0,1). $$

A  walk   of length $n$ is then an ordered collection of steps
$$\vec{\bs}= (\bs_1,\dotsc, \bs_n)\in\eS^n. $$

The above walk is called admissible if

$$ \bs_j+\bs_{j-1}\neq 0,\;\;\forall  j=2,\dotsc, n. \tag{2}\label{2} $$


We denote by $\newcommand{\eA}{\mathscr{A}}$ $\eA_n$ the set of admissible   walks of length $n$. Since $\bs_1$ can be chosen in four different ways, while  each of  the   following  steps   can be chosen in  three different  ways so as to preserve (\ref{2}) we deduce

$$ |\eA_n|= 4\cdot 3^{n-1}. \tag{3}\label{3} $$

There is however a  symmetry in the story, i.e., a  group acting on $\eA_n$.     $\newcommand{\eO}{\mathscr{\eO}}$  Denote  by $G_0$ the subgroup of $O(2)$ generated by the reflections  $R_0, R_1, R_2$ where

$$R_0\be_1=\be_2,\;\;R_0\be_2=\be_1, $$

$$R_1\be_1=\be_1,\;\;R_1\be_2=-\be_2, $$

$$R_2\be_1=-\be_1,\;\;R_2\be_2=-\be_2. $$

This group has order $8$ and can be identified with the Weyl group of $O(4)$.

The group $G_0$ acts on $\bR^2$ and $\eS\subset \bR^2$ is a $G_0$-invariant subset.  In particular, $G_0$ acts on the set $\eS^n$ of walks of length $n$, and $\eA_n\subset \eS^n$ is $G_0$-invariant.  Observe that if $g\in G_0$ then

$$\eS^g= \begin{cases} \eS, & g=1\\
\{\pm \be_1\} & g=R_1,\\
\{\pm \be_2\}, & g=R_2\\
\emptyset,  & g\neq 1,R_1,R_2.
\end{cases} \tag{4} \label{4} $$

There exists another involution $R_3$ that acts on $\eS^n$. More precisely

$$R_3(\bs_1,\dotsc,\bs_n)=(\bs_n,\dotsc,\bs_1). $$

 Clearly $R_3\eA_n\subset\eA_n$.  We denote by $G$ the  subgroup  of the group of permutations of $\eA_n$ generated by $G_0$ and $R_3$. Since obviously  $R_3$ commutes with all of the reflections $R_0,R_1, R_2$ we deduce that  $G\cong G_0\times (\bZ/2). $

 

We would like to compute the number of orbits  of the action of $G$ on  $\eA_n$.     We denote by $p_n$ this number.    The final answer is contained in the equalities (\ref{odd}) and (\ref{even}) below which show different behaviors depending on whether $n$ is odd or even.   Here are   the details.

For any $\gamma\in G$ we  denote by $\eA_n(\gamma)$ the set of admissible paths of length $n$ fixed by $\gamma$ and we set  $p_n(\gamma):=|\eA_n(\gamma)|$.  From Burnside's lemma we  deduce

$$ p_n=\frac{1}{16} \sum_{\gamma\in G} p_n(\gamma).\tag{5}\label{5} $$

We need to compute the numbers $p_n(g)$.  We distinguish two cases.

A.  $\gamma\in G_0$.   If  $\gamma=1$, then

$$p_n(1)= |\eA_n|. $$

Suppose that  $\gamma\neq 1$. Then $\vec{\bs}\in\eA_n(\gamma)\subset \eS^n$ iff

$$ \gamma\bs_j=\bs_j,\;\;\forall j=1,\dotsc, n. $$

According to  (\ref{4}) the only   nontrivial   elements of $G_0$ that have fixed points when acting on $\eS$ are   $R_1$, $R_2$.  The only admissible paths  of  length $1$ that are $R_j$-invariant, $j=1,2$ are

$$(\be_j,\dotsc,\be_j),\;\;(-\be_j,\dotsc,-\be_j). $$  Hence, if $\gamma\in G_0$, then

$$ p_n(\gamma)=\begin{cases}
|\eA_n|, & \gamma=1\\
2, & \gamma=R_1,R_2,\\
0, & \mbox{otherwise}.
\end{cases} \tag{6}\label{6} $$

B.  $\gamma=(g,R_3)$, $g\in G_0$.

Hence $\newcommand{\Llra}{\Longleftrightarrow}$

$$ \vec{\bs}\in \eA_n(g, R_3)\Llra  R_3\vec{\bs}=g\vec{\bs}. $$

If $h\in G_0$,  $\vec{\bs}\in\eA_n(g,R_3)$ and $\newcommand{\si}{\boldsymbol{\sigma}}$ we set $\vec{\si} = h\vec{\bs}$, then

$$  R_3\vec{\si}= R_3 h \vec{\bs}= h R_3 \vec{\bs}= hg \vec{\bs}= hgh^{-1} \vec{\si}. $$

This shows that

$$|\eA_n(g,R_3)|=|\eA_n(hgh^{-1}, R_3)|,\;\;\forall g,h\in G_0.\tag{7}\label{7} $$

This shows that the  map $G_0\ni g\mapsto |\eA_n(g, R_3)|$ is constant on the conjugacy classes  of $G_0$.  Let us describe these conjugacy classes. It helps to observe that the morphism $\det :O(2)\to\{\pm 1\}$  induces a morphism

$$ \det :G_0\to\{\pm 1\} $$

and this morphism is constant on the conjugacy classes.       There exist two  conjugacy classes of determinant $-1$

$$ C(R_1)=\{ R_1, R_2=-R_1\},\;\; C(R_0)=\{R_0, -R_0\}.$$


The other conjugacy classes  are

$$ C_1=\{1\},\;\; C_{-1}= \{-1\}, \;\; C=\{ J, -J\}, $$

where $J= RR_1$ is the counterclockwise rotation by  $\pi/2$.   Thus  we need to compute the five numbers

$$p_n(\pm 1,R_3), \; p_n(R_1,R_3), \; p_n(R_0,\;  R_3), \; p_n(J, R_3). $$


We discuss them separately. Set $m:=\lfloor (n+1)/2\rfloor$

$\eA_n(1,R_3).$    A walk  $\vec{\bs}\in \eA_n(1,R_3)$ is determined by the initial segment  of length $m$ which could be an arbitrary  walk in $\eA_m$.

For $n$ even, $n=2m$,   a walk $\vec{\bs}\in \eA_n(1,R_3)$ if and only if it has the form

$$\vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,\bs_{m},\bs_{m-1},\dotsc, \bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$

For $n$ odd, $n=2m-1$,  a walk $\vec{\bs}\in \eA_n(1,R_3)$ if and only if it has the form

$$  \vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,\bs_{m-1},\dotsc, \bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$.

Hence

$$ p_n(1, R_3)=  |\eA_m|= 4\cdot 3^{\lfloor(n+1)/2\rfloor -1}. \tag{8}\label{8} $$


$\eA_n(-1,R_3).$        Such a path is again determined by the  initial segment  of length $m$.

For $n$ even, $n=2m$,   if  $\vec{\bs}\in \eA_n(-1,R_3)$, then

$$\vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,-\bs_{m},-\bs_{m-1},\dotsc, -\bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$

Clearly such a path is not admissible. Hence $\eA_m(-1, R_3)=\emptyset$ if $n$ is even.

If $n$ is odd,  $n=2m-1$, and $\vec{\bs}\in\eA_n(-1,R_3)$, then $\bs_m=-\bs_m$.  Not possible!.

 Hence

$$ p_n(-1,R_3)=0,\;\;\forall n. \tag{9}\label{9} $$


$\eA_n(R_1,R_3). $   A path $\vec{\bs}=(\bs_1,\dotsc,\bs_n)\in\eA_n(R_1, R_3)$    is  determined by  initial segment  of length $m$.

For $n$ even, $n=2m$,   if  $\vec{\bs}\in \eA_n(-1,R_3)$, then

$$ \vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,R_1\bs_{m},R_1\bs_{m-1},\dotsc, R_1\bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$

Such a path is admissible if and only if $\bs_m+R_1\bs_m\neq 0$, i.e., $\bs_m=\pm\be_1$.  The number of admissible paths  $(\bs_1,\dotsc,\bs_m)$ which end with $\bs_m=\pm\be_1$  is $2\cdot 3^{m-1}$.


For $n$ odd, $n=2m-1$,   if  $\vec{\bs}\in \eA_n(-1,R_3)$, then

$$\vec{\bs}=(\bs_1,\dotsc,\bs_{m-1}\,\bs_m, R_1\bs_{m-1},\dotsc, R_1\bs_1),\;\;\bs_m=R_1\bs_m.$$

 We deduce

$$ p_n(R_1,R_3) =2\cdot 3^{m-1},\;\;m=\lfloor(n+1)/2\rfloor.  \tag{10}\label{10} $$

$\eA_n(R_0,R_3). $   Arguing as above  we deduce that if $(\bs_1,\dotsc,\bs_n)\in\eA(R_0,R_3)$     and  $n$ is odd, then $R_0\bs_m=\bs_m$ which is impossible because $R_0$ does not have fixed points on $\eS$.

For $n$ even, $n=2m$, $\vec{\bs}=(\bs_1,\dotsc,\bs_n)\in \eA_n(R_0,R_3)$ if and only if

$$\vec{\bs}=(\bs_1,\dotsc,\bs_{m-1}\bs_m,R_0\bs_m, R_0\bs_{m-1},\dotsc, R_0\bs_1),\;\; (\bs_1,\dotsc,\bs_m,R_0\bs_m)\in \eA_m. $$

Whatever $\bs_m\in\eS$, we have $\bs_m+R_0\bs_m\neq 0$. We deduce

$$ p_n(R_0, R_3)=\begin{cases}
0, & n=2m-1\\
4\cdot 3^{m-1}, & n=2m.
\end{cases} \tag{11}\label{11} $$


$\eA_n(J,R_3). $  We observe that

$$(\bs_1,\dotsc,\bs_n)\in\eA_n(J, R_3)\Llra (J\bs_n,\dotsc, J\bs_1)=(\bs_1,\dotsc,\bs_n). $$


This implies  $J^2\bs_n=\bs_n$ which is obviously impossible.  Hence

$$ p_n(J, R_3) =0,\;\;\forall n. \tag{12}\label{12} $$

Using (\ref{5})  and (\ref{6}) we deduce

$$ p_n=\frac{1}{16}\Bigl( 4\cdot 3^{n-1}+4 +p_n(1,R_3)+ p_n(-1,R_3)+ 2p_n(R_1,R_3) +2p_n(R_0,R_3) +2p_n(J)\Bigr) $$

$$= \frac{1}{16}\Bigl( 4\cdot 3^{n-1}+4 +p_n(1,R_3)+ 2p_n(R_1,R_3) +2p_n(R_0,R_3) \Bigr). $$

Using  (\ref{8}), (\ref{9}), (\ref{10}), (\ref{11}), (\ref{12})  in the  above  equality we  deduce  the following.

If $n=2m-1$, then



$$ p_n= \frac{1}{16}\Bigl( 4\cdot 3^{n-1} + 4 + 8\cdot 3^{m-1}\Bigr) = \frac{1}{4}\bigl(\,3^{n-1}+2\cdot 3^{m-1}+1\bigr).\tag{$\ast$}\label{odd}$$


If $n=2m$, then

$$ p_n=   \frac{1}{16}\Bigl( 4\cdot 3^{n-1} + 4 + 16\cdot 3^{m-1}\Bigr) =  \frac{1}{4}\bigl(\,3^{n-1}+4\cdot 3^{m-1}+1\bigr). \tag{$\ast\ast$}\label{even}$$

No comments: