Consider the effect of $f(x)=\frac12(x-x^{-1})$ on the residues mod $p$ (plus $\infty$) of a Mersenne prime $p$. You get the following tree (example $p=7$):
$$
\begin{array}{ccccccc}
4\\
&\searrow\\
&&1\\
&\nearrow&&\searrow\\
5\\
&&&&0&\rightarrow&\infty\\
2\\
&\searrow&&\nearrow\\
&&6\\
&\nearrow\\
3\\
\end{array}
$$
Proving that a binary tree always results is far beyond my abilities. I merely observed it. Can someone prove it?
Addendum: Primes of the form $k\cdot2^p-1$ or $k\cdot2^p+1$ with small $k$ seem to act quite similar tree-ish.
-
$\begingroup$ It is unclear to me what you are asking. Please formalize the statement properly. $\endgroup$– GH from MONov 28, 2015 at 21:11
-
$\begingroup$ Here's a way of formulating the question without the ascii art. Let $p=2^q-1$ be a Mersenne prime. Consider the 2-to-1 map from $(Z/pZ)^\times$ to $(Z/pZ)$ sending $x$ to $(x-1/x)/2$. Note that this map is 2-to-1 because $x$ and $-1/x$ go to the same place, and they can't be the same number because $-1$ isn't a square mod $p$ (as $p$ is 3 mod 4). The question: if you iterate this map do you always get to zero in at most $q-1$ steps? $\endgroup$– ericNov 28, 2015 at 21:13
-
$\begingroup$ @eric: Thank you. I could not decode the ascii art, although I have not tried hard either. $\endgroup$– GH from MONov 28, 2015 at 21:40
1 Answer
The critical points of $f$ are at $x=\pm i$, so we try a projective (a.k.a. fractional linear) change of variable that puts these critical points at $0$ and $\infty$, namely $x = \alpha(y)$ where $\alpha(Y) = i(Y+1) \, / \, (Y-1)$, $\alpha^{-1}(X) = (X+i) \, / \, (X-i)$, and find that $f(\alpha(y)) = \alpha(y^2)$. Therefore $-$ unusually for a degree-2 rational function $-$ the iterates of $f$ have a closed form, $$ f^{(n)}(x) = \alpha^{-1}(\alpha(x)^{2^n}). $$ Now if $p=2^l-1$ is a Mersenne prime then $i$ generates a field of $p^2$ elements, call it $F$, and $(x+i)/(x-i)$ is an element of the norm-$1$ subgroup of $F^*$, which is cyclic of order $p+1 = 2^l$. Since $y \mapsto y^2$ is the doubling map on this group, its graph has the binary-tree structure that you observed.
Likewise if $p = k 2^l - 1$ for $l \geq 2$ and $k$ odd then the graph is the union of $k$ binary trees, and if $p = k 2^l + 1$ then there are square roots of $-1$ in ${\bf Z} / p {\bf Z}$, and the graph is the union of $k$ binary trees together with two isolated points at those square roots (corresponding to $y = 0,\infty$).
-
$\begingroup$ You say "unusually". Is this the only f which has the properties needed for the proof or do we have some leeway, like A*y^2+B instead of y^2? $\endgroup$ Nov 29, 2015 at 9:39
-
$\begingroup$ Very little leeway. For quadratic polynomials, you can normalize to $y^2+c$ (e.g. from your $Ay^2+B$ scale $y$ by $a$), but if all such quadratics were easy to iterate then the Mandelbrot set would be much more boring. Aside of $c=0$, I think the only $c$ for which iteration of $y^2+c$ is elementary is $c=-2$, thanks to the identity $z^2 + z^{-2} = (z+z^{-1})^2 - 2$ (which as it happens figured in the 2014 Putnam exam, see Problem A3 <kskedlaya.org/putnam-archive/2014.pdf>). The graphs of $y^2-2 \bmod p$ are more complicated than those of $y^2$, but still tractable. $\endgroup$ Nov 29, 2015 at 20:25