5
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It is unclear to me what you are asking. Please formalize the statement properly. $\endgroup$
    – GH from MO
    Nov 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$
    – eric
    Nov 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 MO
    Nov 28, 2015 at 21:40

1 Answer 1

10
$\begingroup$

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

$\endgroup$
2
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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