Orbits in modular arithmetic - MathOverflow

Orbits in modular arithmetic

2011-03-07T22:24:55Z

Let $p$ be an odd prime number and consider the set of $p-2$ integers that is $\mathbb{Z}_p$ minus 0 and 1. Next define two bijective functions on this set \begin{align} f(x) &= 1-x \mod p \end{align} and \begin{align} g(x) &= x^{-1} \mod p \qquad \text{(the multiplicative inverse of $x$).} \end{align} One can view these two functions as group actions (generated by $f$ and $g$) on this set of integers and study the orbits. For example, if $p=7$, there are two orbits namely {2,4,6} and {3,5}.

For the general prime $p>3$, I can prove there is always an orbit consisting of $\{ 2,p-1, 2^{-1} \}$ .

Question : I'm interested to find the number of orbits as a function of $p$.

Answer by Gjergji Zaimi for Orbits in modular arithmetic

2011-03-07T23:30:16Z

You can first notice that $fgfgfg(x)=x$ and conclude that most orbits have size $6$. It is easy to show that there is one orbit of size $3$ which you found and there is an orbit of size $2$ whenever there is a solution to $$x(1-x)\equiv 1\pmod{p}$$ this happens if $\binom{-3}{p}=1$ so if $p\equiv 1\pmod{3}$. You can easily show that there can't be orbits of size $4$ or $5$. So the answer is $\frac{p+1}{6}$ if $p\equiv -1\pmod{3}$ and $\frac{p+5}{6}$ if $p\equiv 1\pmod{3}$.

Answer by kett for Orbits in modular arithmetic

2011-03-08T08:23:05Z

Thanks to Gjergji's post and subsequent comment, I was able to arrive at his answer after some effort. I post the full proof here for anyone who might find it useful.

Let $p \ge 5$ be a prime number and $f(x), g(x)$ defined above in the OP on the set of integers $S=\mathbb{Z}_p \backslash \{0,1\}$ .

Lemma 1 : $fgfgfg(x) = x$ .

Proof : \begin{align} fgfgfg(x) &= fgfg( 1 - x^{-1}) = fgfg(x^{-1}(x-1))\\ &= fg \left( 1-x(x-1)^{-1} \right) = fg \left( (x-1)(x-1)^{-1}-x(x-1)^{-1} \right) \\ &= fg \left( -(x-1)^{-1} \right) = x \end{align} One can similarly show $\;gfgfgf(x) = x$ . This proves there are no orbits with size greater than 6.

Next, consider fixed points of $f$ which amounts to solving $x \equiv 1-x$ . This gives us $x \equiv 2^{-1} \bmod p$ . Therefore, $f$ has exactly one fixed point.
The function $g$ also has only one fixed point which is $-1$ . (Recall that $1 \notin S$ ).

Lemma 2 : For all prime $p\ge 5$ , $\{2, -1, 2^{-1}\}$ is the only orbits of size 3.

Proof:
Consider the orbit that $2^{-1}$ belongs to. Clearly $g(2^{-1}) = 2$ and $f(2) = -1$ . Further applications of $f,g$ do not map outside of $\{2, -1, 2^{-1}\}$ so this set forms an orbit. Also for all $p\ge 5$ , $\{2, -1, 2^{-1}\}$ are 3 distinct elements, which means the size of this orbit is 3.

To prove there are no orbits of size 3 besides $\{2, -1, 2^{-1}\}$ , assume there is another orbit of size 3, $\{\alpha, \beta, \gamma\}$ , all distinct of course. W.l.o.g, we can assign $f(\alpha) = \beta$ and $g(\alpha) = \gamma$ . We cannot have $g(\alpha) = \beta$ as this would imply an orbit of size 2. Then $f(\beta) = ff(\alpha) = \alpha$ and $g(\gamma) = gg(\alpha) = \alpha$ . Next $f(\gamma)$ cannot be equal to $\alpha$ for it implies $f(\alpha) = \gamma$ . Nor can it be equal to $\beta$ so we arrive at $f(\gamma) = \gamma$ . But $-1$ is the only fixed point of $f$ so $\{\alpha, \beta, \gamma\}$ is exactly the orbit we already found, which is a contradiction.

Lemma 3 : There is exactly one orbit of size 2 whenever $p \equiv 1 \bmod 3$ and no orbit of size 2 if $p \equiv 2 \bmod 3$ .

We begin by assuming the existence of an orbit of size 2 with elements $\{\alpha, \beta\}$ . Then we must have $f(\alpha) = g(\alpha) = \beta$ which means $\alpha$ is the solution to $1-x = x^{-1}$ . Multiplying both sides with $4x$ and completing the squares, we end up with $(2x-1)^2 \equiv -3 \bmod p$ . The law of quadratic reciprocity tells us a solution exists iff $(2x-1)^2 \equiv p \bmod 3$ . Looking at quadratic residues modulo 3 we see it is solvable if $p \equiv 1 \bmod 3$ and not solvable if $p \equiv 2 \bmod 3$ . This proves the second statement of the Lemma.

If $p \equiv 1 \bmod 3$ , then $(2x-1)^2 \equiv -3 \bmod p$ can be solved. We shall denote the solutions as $\pm y$ , i.e. $(\pm y)^2 \equiv -3 \bmod p$ which means $\alpha = 2^{-1}(1\pm y)$ . These two distinct solutions seems to indicate there are two orbits of size 2 but this is not the case. To see this, if we let $\alpha = 2^{-1}(1 + y)$ and solve for $\beta$ , we end up with $\beta = 2^{-1}(1 - y)$ . Therefore there is only one orbit of size 2 whenever $p \equiv 1 \bmod 3$ .

Lemma 4 : There are no orbits of size 4 or 5.

To show there are no orbits of size 4, again we begin by assuming such an orbit exists with integer $\{\alpha, \beta, \gamma, \delta \}$ . Let $f(\alpha) = \beta$ and $g(\alpha) = \gamma$ .

Next, $f(\gamma)$ cannot be equal to $\alpha$ nor $\beta$ . We can also eliminate $f(\gamma) = \gamma$ as this will just give us back the orbit in Lemma 2. Therefore the only possible assignment is $f(\gamma) = \delta$ . Using a similar argument, we can argue that it must be the case that $g(\beta) = \delta$ . This means $f(\gamma) = g(\beta)$ which implies $fg(\alpha) = gf(\alpha)$ . This in turn implies $fgffg(\alpha) = fgfgf(\alpha) \Rightarrow f(\alpha) = g(\alpha)$ where we have used Lemma 1 and the fact that $ff$ and $gg$ are both identity maps. However we have already solved $f(\alpha) = g(\alpha)$ to get an orbit of size 2 so this proves there is no orbit of size 4.

The same techniques will also show there are no orbits of size 5.

Theorem 5 : The number of orbits as a function of $p$ is as claimed in posts above.

In the first case where $p \equiv 1 \bmod 3$ , there are two orbits (size 2 and 3) and all $p-7$ remaining integers belong to orbits of size 6. Therefore, the number of orbits is $(p-7)/6 + 2 = (p+5)/6$ .

If $p \equiv 2 \bmod 3$ , there is one orbit of size 3 with $p-5$ integers left over. Therefore, the number of orbits is $(p-5)/6 + 1 = (p+1)/6$ .

Answer by ACL for Orbits in modular arithmetic

2011-03-10T22:38:53Z

Your transformations act on the projective line $\mathbb Z_p \cup{\infty}$, preserving the three points $0$, $1$, $\infty$. The group they generate is isomorphic to the group $\mathfrak S_3$ of permutations on these three points.

Anyway, you can enumerate the orbit of a point $x\in\mathbb Z_p\setminus{0,1}$ and obtain [ { x, 1-x, \frac 1x, \frac1{1-x}, \frac x{x-1} , \frac{x-1}x}. ] This orbit usually has cardinality 6, unless if the stabilizer of $x$ is nontrivial. When this happens, you have $x=1-x$, or $x=1/x$, or $x=1/(1-x)$, or $x=x/(x-1)$, or $x=(x-1)/x$.

Assume now that $p>3$. (The cases $p=2$ and $3$ are trivial.)

The preceding analysis shows that there is exaclty one orbit with cardinality $3$, namely ${-1,2,1/2}$, and one orbit of cardinality $2$, ${\alpha,1-\alpha}$, where $\alpha$ is an element of $\mathbb Z_p$ satisfying $\alpha^2-\alpha+1=0$. Such an $\alpha$ exists if and only if $-3$ is a square in $\mathbb Z_p$.

Let $k$ be the number of orbits with cardinality $6$. The total number of orbits is $k+2$ if $-3$ is a square, and $k+1$ otherwise. Counting the number of elements in $\mathbb Z_p\setminus{0,1}$ gives $p-2=6k+3+2$ in the former case, and $p-2=6k+3$ in the latter, that is: $p=6k+7$, resp. $p=6k+5$.

Finally, we obtain that for $p\equiv 1\pmod 6$, $-3$ is a square modulo $p$ and there are $(p+5)/6$ orbits, while for $p\equiv -1\pmod 6$, $-3$ is not a square and there are $ (p+1)/6$ orbits.

NB. In both cases, the number of orbits is equal to $\lfloor(p+5)/6\rfloor$.