Orbits in modular arithmetic - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T11:52:04Z http://mathoverflow.net/feeds/question/57739 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57739/orbits-in-modular-arithmetic Orbits in modular arithmetic kett 2011-03-07T22:24:55Z 2011-03-11T06:51:16Z <p>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) &amp;= 1-x \mod p \end{align} and \begin{align} g(x) &amp;= 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}.</p> <p>For the general prime $p>3$, I can prove there is always an orbit consisting of <code>$\{ 2,p-1, 2^{-1} \}$</code>.</p> <p>Question : I'm interested to find the number of orbits as a function of $p$.</p> http://mathoverflow.net/questions/57739/orbits-in-modular-arithmetic/57746#57746 Answer by Gjergji Zaimi for Orbits in modular arithmetic Gjergji Zaimi 2011-03-07T23:30:16Z 2011-03-07T23:38:30Z <p>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}$.</p> http://mathoverflow.net/questions/57739/orbits-in-modular-arithmetic/57790#57790 Answer by kett for Orbits in modular arithmetic kett 2011-03-08T08:23:05Z 2011-03-11T06:51:16Z <p>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.</p> <p>Let <code>$p \ge 5$</code> be a prime number and <code>$f(x), g(x)$</code> defined above in the OP on the set of integers <code>$S=\mathbb{Z}_p \backslash \{0,1\}$</code>.</p> <p><br/></p> <h2>Lemma 1 : <code>$fgfgfg(x) = x$</code>.</h2> <p>Proof : <code>\begin{align} fgfgfg(x) &amp;= fgfg( 1 - x^{-1}) = fgfg(x^{-1}(x-1))\\<br> &amp;= fg \left( 1-x(x-1)^{-1} \right) = fg \left( (x-1)(x-1)^{-1}-x(x-1)^{-1} \right) \\<br> &amp;= fg \left( -(x-1)^{-1} \right) = x \end{align}</code> One can similarly show <code>$\;gfgfgf(x) = x$</code>. This proves there are no orbits with size greater than 6. </p> <p>Next, consider fixed points of <code>$f$</code> which amounts to solving <code>$x \equiv 1-x$</code>. This gives us <code>$x \equiv 2^{-1} \bmod p$</code>. Therefore, <code>$f$</code> has exactly one fixed point.<br> The function <code>$g$</code> also has only one fixed point which is <code>$-1$</code>. (Recall that <code>$1 \notin S$</code>).</p> <p><br/> </p> <h2>Lemma 2 : For all prime <code>$p\ge 5$</code>, <code>$\{2, -1, 2^{-1}\}$</code> is the only orbits of size 3.</h2> <p>Proof:<br> Consider the orbit that <code>$2^{-1}$</code> belongs to. Clearly <code>$g(2^{-1}) = 2$</code> and <code>$f(2) = -1$</code>. Further applications of <code>$f,g$</code> do not map outside of <code>$\{2, -1, 2^{-1}\}$</code> so this set forms an orbit. Also for all <code>$p\ge 5$</code>, <code>$\{2, -1, 2^{-1}\}$</code> are 3 distinct elements, which means the size of this orbit is 3.</p> <p>To prove there are no orbits of size 3 besides <code>$\{2, -1, 2^{-1}\}$</code>, assume there is another orbit of size 3, <code>$\{\alpha, \beta, \gamma\}$</code>, all distinct of course. W.l.o.g, we can assign <code>$f(\alpha) = \beta$</code> and <code>$g(\alpha) = \gamma$</code>. We cannot have <code>$g(\alpha) = \beta$</code> as this would imply an orbit of size 2. Then <code>$f(\beta) = ff(\alpha) = \alpha$</code> and <code>$g(\gamma) = gg(\alpha) = \alpha$</code>. Next <code>$f(\gamma)$</code> cannot be equal to <code>$\alpha$</code> for it implies <code>$f(\alpha) = \gamma$</code>. Nor can it be equal to <code>$\beta$</code> so we arrive at <code>$f(\gamma) = \gamma$</code>. But <code>$-1$</code> is the only fixed point of <code>$f$</code> so <code>$\{\alpha, \beta, \gamma\}$</code> is exactly the orbit we already found, which is a contradiction.</p> <p><br/></p> <h2>Lemma 3 : There is exactly one orbit of size 2 whenever <code>$p \equiv 1 \bmod 3$</code> and no orbit of size 2 if <code>$p \equiv 2 \bmod 3$</code>.</h2> <p>We begin by assuming the existence of an orbit of size 2 with elements <code>$\{\alpha, \beta\}$</code>. Then we must have <code>$f(\alpha) = g(\alpha) = \beta$</code> which means <code>$\alpha$</code> is the solution to <code>$1-x = x^{-1}$</code>. Multiplying both sides with <code>$4x$</code> and completing the squares, we end up with <code>$(2x-1)^2 \equiv -3 \bmod p$</code>. The law of quadratic reciprocity tells us a solution exists iff <code>$(2x-1)^2 \equiv p \bmod 3$</code>. Looking at quadratic residues modulo 3 we see it is solvable if <code>$p \equiv 1 \bmod 3$</code> and not solvable if <code>$p \equiv 2 \bmod 3$</code>. This proves the second statement of the Lemma.</p> <p>If <code>$p \equiv 1 \bmod 3$</code>, then <code>$(2x-1)^2 \equiv -3 \bmod p$</code> can be solved. We shall denote the solutions as <code>$\pm y$</code>, i.e. <code>$(\pm y)^2 \equiv -3 \bmod p$</code> which means <code>$\alpha = 2^{-1}(1\pm y)$</code>. 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 <code>$\alpha = 2^{-1}(1 + y)$</code> and solve for <code>$\beta$</code>, we end up with <code>$\beta = 2^{-1}(1 - y)$</code>. Therefore there is only one orbit of size 2 whenever <code>$p \equiv 1 \bmod 3$</code>.</p> <p><br/></p> <h2>Lemma 4 : There are no orbits of size 4 or 5.</h2> <p>To show there are no orbits of size 4, again we begin by assuming such an orbit exists with integer <code>$\{\alpha, \beta, \gamma, \delta \}$</code>. Let <code>$f(\alpha) = \beta$</code> and <code>$g(\alpha) = \gamma$</code>. </p> <p>Next, <code>$f(\gamma)$</code> cannot be equal to <code>$\alpha$</code> nor <code>$\beta$</code>. We can also eliminate <code>$f(\gamma) = \gamma$</code> as this will just give us back the orbit in Lemma 2. Therefore the only possible assignment is <code>$f(\gamma) = \delta$</code>. Using a similar argument, we can argue that it must be the case that <code>$g(\beta) = \delta$</code>. This means <code>$f(\gamma) = g(\beta)$</code> which implies <code>$fg(\alpha) = gf(\alpha)$</code>. This in turn implies <code>$fgffg(\alpha) = fgfgf(\alpha) \Rightarrow f(\alpha) = g(\alpha)$</code> where we have used Lemma 1 and the fact that <code>$ff$</code> and <code>$gg$</code> are both identity maps. However we have already solved <code>$f(\alpha) = g(\alpha)$</code> to get an orbit of size 2 so this proves there is no orbit of size 4.</p> <p>The same techniques will also show there are no orbits of size 5.</p> <p><br/></p> <h2>Theorem 5 : The number of orbits as a function of <code>$p$</code> is as claimed in posts above.</h2> <p>In the first case where <code>$p \equiv 1 \bmod 3$</code>, there are two orbits (size 2 and 3) and all <code>$p-7$</code> remaining integers belong to orbits of size 6. Therefore, the number of orbits is <code>$(p-7)/6 + 2 = (p+5)/6$</code>.</p> <p>If <code>$p \equiv 2 \bmod 3$</code>, there is one orbit of size 3 with <code>$p-5$</code> integers left over. Therefore, the number of orbits is <code>$(p-5)/6 + 1 = (p+1)/6$</code>.</p> http://mathoverflow.net/questions/57739/orbits-in-modular-arithmetic/58112#58112 Answer by ACL for Orbits in modular arithmetic ACL 2011-03-10T22:38:53Z 2011-03-10T22:38:53Z <p>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.</p> <p>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$.</p> <p>Assume now that $p>3$. (The cases $p=2$ and $3$ are trivial.)</p> <p>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$.</p> <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$.</p> <p>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.</p> <p>NB. In both cases, the number of orbits is equal to $\lfloor(p+5)/6\rfloor$.</p>