Number of orbits of a group action

Question

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$?

Answer 1

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.

Answer 2

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)} $$