Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I have no idea what the answer is, but here's one thing you might try; calculate the number of orbits for the first few primes, then look up the resulting sequence in the Online Encyclopedia of Integer Sequences. –  Gerry Myerson Mar 7 '11 at 22:34
    
OK let's see. Let $N(p)$ be the number of orbits. Then $N(5) = 1, N(7) = 2, N(11) = 2, N(13) = 3$. It seems I need more data points to narrow things down. –  kett Mar 7 '11 at 23:03
    
These maps show up, if I recall it correctly, in several publications on "exceptional units" (Martinet, Leutbecher, Niklasch). –  Franz Lemmermeyer Mar 8 '11 at 12:18

3 Answers 3

up vote 15 down vote accepted

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

share|improve this answer
    
If you have time, would you mind expanding a little bit more on your proof as I haven't been able to reproduce your answer. For example, I don't know how to show $fgfgfg(x)=x$. I can see why one would only need to consider composed functions that alternate between $f$ and $g$ because their squares are just the identity map. –  kett Mar 7 '11 at 23:53
    
Also I can see how the orbit of size 2 can be obtained by solving $f(x) \equiv g(x)$ which leads to your equation $x(1-x) \equiv 1 \bmod p$ but I don't understand how your condition impies there is a solution. It seems like I need to solve the quadratic equation $x^2 - x + 1 \equiv 0 \bmod p$. –  kett Mar 7 '11 at 23:54
    
@kett, at this point you should be able to work out the details yourself. The values under the f,g maps are the same as the ones of the cross-ratio under the $S_4$ action. en.wikipedia.org/wiki/Cross-ratio#Action_of_symmetric_group Also notice that you can rewrite the second equation as $(2x-1)^2\equiv -3\pmod{p}$ –  Gjergji Zaimi Mar 8 '11 at 0:03
    
Your second comment is quite useful, to solve it using quadratic reciprocity. en.wikipedia.org/wiki/Quadratic_reciprocity –  kett Mar 8 '11 at 1:16
    
Much better than my suggestion of calculating examples and looking it up in the OEIS. –  Gerry Myerson Mar 8 '11 at 3:07

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

share|improve this answer

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

share|improve this answer
2  
@kett: There appear to be two essentially complete answers to this question already, so there is no need to bump it so many times (5 times in the past 2 days). If you feel the need for such an extremely detailed write-up, it may be worthwhile writing it on your own (in a text or LaTeX editor) and then, if you'd like to put it here, to copy and paste it upon completion. –  Daniel Litt Mar 11 '11 at 5:03
    
I'm sorry, I wasn't aware this post gets bumped every time I edit my answer -- that wasn't my intention. Is there a way to turn this feature off? –  kett Mar 11 '11 at 6:55
    
No alas, except to write up your answer externally and paste it in when you're done, as I suggested. –  Daniel Litt Mar 14 '11 at 1:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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