How does the cycle structure of an invertible linear map over $\Bbb Z/n\Bbb Z$ compare to its affine translations?

Question

The general question I am interested is roughly what is in the title; more concretely:

Fix a positive integer $n$, and $m\in(\Bbb Z/n\Bbb Z)^\times$. For each $b\in\Bbb Z/n\Bbb Z$, define the invertible map $f_b:\Bbb Z/n\Bbb Z \to \Bbb Z/n\Bbb Z$ by $f(x)=mx+b$. What is the cycle structure of $f_b$ as $b$ varies?

For instance, if $n$ is prime, then every $f_b$ has a unique fixed point, $b$, and every other element fits into a cycle whose length is the multiplicative order of $m$ in $(\Bbb Z/n\Bbb Z)^\times$. In particular, every $f_b$ has the same cycle structure.

My particular interest is in a more difficult example, where there is some variability, but computer search seems to suggest much less than I expected. Let $n$ be even and $m$ be a number such that the cycle structure of $f_0$ is $[k,k,k,\dots, k,1,1]$ for some $k$ [or, equivalently, for $k=\text{ord}_{(\Bbb Z/n\Bbb Z)^\times}(m)$]. I claim the following:

Claim: Given the previous setup, the cycle structure of $f_b$ is one of the following:

• $[k,k,k,\dots, k,1,1]$
• $[k,k,k,\dots, k, 2]$
• $[2k,\dots, 2k, 2]$
• $[4,4,\dots, 4]$
• $[2,2,2,2,\dots, 2,2]$

(For what it's worth, I have some guesses as to when these occur. For instance, it seems that you get all 4s precisely when $8|n$ and $m=n/2-1$. The second case happens seems to happen only when $k$ is even, $n/2$ is odd, and every prime factor of $n$ is equivalent to $1$ mod $k$.)

I suspect that proving this claim would be quite tedious, so I am not seeking a proof of it per se (although I certainly would welcome one). Rather, I am looking for techniques with which to solve problems that are similar, in the sense that they require understanding cycle structures of affine functions.

(In case it sparks a memory: The group of affine transformations over $\Bbb Z/n\Bbb Z$ is isomorphic to the normalizer $N_{S_n}(C_n)$, where $C_n$ is the cyclic subgroup generated by the long cycle $c=(1\,2\cdots n)$. Varying $b$ is equivalent to considering right-translations of a given element by powers of $c$.)

Answer 1

Since it seems that this will remain Unanswered otherwise, I am posting this as a answer. I'm not sure this will interest anyone else, but perhaps my blogger's instincts are kicking in from a few years back.

For what it's worth, I ended up resolving the claim in my question statement (in the context that I asked it) as Lemma 4.5 in this preprint. To my past self, I would say that the solution to that particular problem was mostly "Shut up and calculate!" However, perhaps some small lessons:

• The prime $2$ caused a great deal of annoyance in the proof; the reason why it was $2$ as opposed to any other was because $\gcd(m,n-1)=2$. This was really the key insight; I recognized very early that $\gcd(m, n-1)$ was important, but I thought I didn't have any control on it. In fact, this number is precisely the number of fixpoints (1-cycles) of $f$; see Proposition 4.3(c).
• I first obtained a solution using Sun Tzu's theorem and then tried very hard to remove it. I failed to do so, because I found no way of handing the headaches that $2$ was giving me except by appealing to it directly. (I tried so hard to remove it because I do not think that such a proof is as insightful as it should be, perhaps because it lacks the actual solutions to the equivalence.)

I do like joriki's idea; now that I am not so focused on overcoming this particular hurdle, perhaps I should turn some attention to it...