2
$\begingroup$

Let $n$ be a positive integer, and let $\mathbf{Z}$ act on $\mathbf{Z}_2^n$ by left shift, that is $1+(a_1,a_2,\dots,a_n)=(a_2,\dots,a_n,a_1)$. How many orbits does the action have?

First notice that $n+(a_1,a_2,\dots,a_n)=(a_1,a_2,\dots,a_n)$, so we may replace $\mathbf{Z}$ by $\mathbf{Z}_n$ without changing the orbits. Now the group is finite, so we can use Burnside's lemma. The number of orbits is $$\frac{1}{n}\sum_{g\in\mathbf{Z}_n}|X^g|,$$ where $X=\mathbf{Z}_2^n$ and $X^g$ denote the set of elements in $X$ that are fixed by $g$. I'm stuck here. How to compute $X^g$ for every $g\in\mathbf{Z}_n$?

$\endgroup$
2
$\begingroup$

Let's define $a_j$ for all integers $j$ by making the sequence $n$-periodic, that is $a_{n+j}=a_j$ for all $j$. For $g\in\Bbb Z$ fixes the sequence $(a_j)$ then this sequence is $g$-periodic as well as $n$-periodic ($a_{g+j}=a_j$). A sequence is $n$-periodic and $g$-periodic iff it is $h$-periodic for $h=\gcd(n,g)$ etc.

$\endgroup$
1
$\begingroup$

The point is that the sequences that are fixed by $d\in\mathbb{Z}$ are exactly the $d$-periodic ones, or more precise, the $\gcd(n,d)$-periodic ones. On the other hand, each $d$-periodic sequence is determined by its first $d$-digits, so there are exactly $2^d$ of such. Now the Burnside's theorem goes $$\frac{1}{n}\sum_g |X^g|=\frac{1}{n} \sum_{1\leq d\leq n} 2^{\gcd(n,d)} $$

$\endgroup$
2
  • $\begingroup$ Can we simplify the expression $\frac{1}{n}\sum_{1\leq d\leq n}2^{\gcd(n,d)}$? $\endgroup$
    – Xiang Yu
    Nov 7 '17 at 3:53
  • $\begingroup$ @XiangYu Perhaps $\frac{1}{n}\sum_{d\mid n} \varphi(n/d)2^d$ ? I'm not sure if that works for you. $\endgroup$
    – Phil. Z
    Nov 7 '17 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.