Finding number of cycles in permutation corresponding to translation in a group [University Olympiad]

Question

here is a question from our university olympiad practice manual which is intended to help us prepare for upcoming inter-university math Olympiad.

I think I can see, solution would be similar to Proof of Fermat Little Theorem using Burnside Lemma, with substitution $k = 1$, $n = a$, but I am not sure how to write it formally to score full points?

General tips to write formal olympiad solutions would also be appreciated! (I got less than half points in correct solutions I wrote last year :/ )

Thanks in advanced! :)

Answer 1

1. $\mathbb{Z}_p^k$ acts on $F$ by $a \cdot f$ = $f(x + a).$ This satisfies $(a + b) \cdot f(x) = a \cdot (b \cdot f(x))$ as $f(x + a + b) = b \cdot f(x + a).$ Furthermore, $0 \cdot f(x) = f(x).$ Hence, $\mathbb{Z}_p^k$ has a well defined group action on $F.$

2. Fix $a \in \mathbb{Z}_p^k \setminus \{0\}.$ Note that there is a well defined group action for any group on itself - now consider the group action of $\mathbb{Z}_p^k$ on itself. Because $a \neq 0$ the number of orbits for the subgroup $\langle a \rangle$ in $\mathbb{Z}_p^k$ we have is $p^{k - 1}.$ To see this, we can use Burnsides Lemma which tells us the number of orbits is $\frac{1}{|\langle a \rangle|} \sum_{f \in F} |Stab_{\langle a \rangle} (f)| = \frac{1}{p} p^k = p^{k - 1},$ as the order of $a$ is $p$ in $\mathbb{Z}_p^k$ and for each $f, Stab(f) = \{0\}$. Now if all the elements in any given orbit of $\langle a \rangle \cdot \mathbb{Z}_p^k$ map to the same element for a given function $f$ then the orbit $\langle a \rangle \cdot f = \{f\}.$ This is clear as the effect of $a \cdot f = f(x + a)$ simply changes the image of $x$ to the image of another member of its orbit. Now, if this is not the case and for a given $f$ we have two elements of a given orbit of $\langle a \rangle$ map to different elements, then we would have the orbit of $f$ be of size $p.$ Hence, it remains to calculate the number of functions that send every element of any given orbit $\langle a \rangle \cdot \mathbb{Z}_p^k$ to the same element and the ones that do not. Since there are $p^{k - 1}$ orbits, we can see that the number of distinct possible choices for the former case is $n^{p^{k - 1}}$ and the latter case has $n^{p^k} - n^{p^{k - 1}}$ choices as we have $n^{p^k}$ number of functions in $F.$ Hence, by our reasoning, we can see that the number of cycles, i.e. the number of distinct orbits of $\langle a \rangle$ acting on $F$ is $n^{p^{k - 1}} + (n^{p^k} - n^{p^{k - 1}})/p$.

3. You can use the fact that $p \mid n^{p^k} - n^{p^{k - 1}}$ and use induction. Maybe there is a cleaner and more direct argument, but I don't know it...

The main thing in formality for proof writing is making sure nothing is hidden and you have clear logical steps. I edited my answer to show you how I would write the proof. I'm by no means an expert at writing proofs but this is the main idea behind proof writing and it should be the same for olympiads.