Algebraic dynamics in finite fields

What is known about combinatorial structure of the rational maps of degree 2 over finite fields? From some general reasons I think it was studied. For being more specific, consider the field $\mathbb{F}_{2^n}$ and the map $x\rightarrow f(x)=x+1/x$. We may consider such a map as oriented graph with outdegrees 1 (except outdegree 0 for $x=0$) and indegrees usually 0 or 2 (except again $x=0$ with indegree 0). Each weak connected component contains exactly 1 cycle (except connected component of 0, which is a tree.) What is known about number of cycles of different lengths? About trees growing from these cycles?

• You could look at some of the work by Franco Vivaldi. I believe this is related to your question. – Anthony Quas Dec 19 '15 at 19:34
• Rather than treating 0 specially, you should treat $f(x)$ as a map on $\mathbb P^1(\mathbb F_{2^n})$. Then every point has one outgoing arrow, and points have either 0 or 2 incoming arrows provided you count them with multiplicity. – Joe Silverman Dec 19 '15 at 19:44
• These come up in the Pollard rho method of integer factorization (although the emphasis is on the fields of $p$ elements, for large prime $p$). – Gerry Myerson Dec 19 '15 at 20:46
• I think it is natural to count degrees in such a way that some of indegrees equals sum of ourdegrees. If we do so, outdegree of 1 should be equal to indegree of 0. – Fedor Petrov Dec 20 '15 at 6:47

There is a growing body of literature on dynamics of rational maps over finite fields. The following paper would seem to be relevant.

• Ugolini, S., Graphs associated with the map $x\mapsto x+x^{-1}$ in finite fields of characteristic two, Theory and applications of finite fields, Contemp. Math. 579, 197-204, Amer. Math. Soc., 2012.

Here are a few more to get you started.

• Alberto de Faria, Joao and Hutz, Benjamin, Combinatorics of cycle lengths on Wehler K3 Surfaces over finite fields, New Zealand J. Math. 45 (2015), 19-31.
• Alden Gassert, T., Chebyshev action on finite fields, Discrete Math. 315 (2014), 83–94.
• Bach, Eric and Bridy, Andrew, On the number of distinct functional graphs of affine-linear transformations over finite fields, Linear Algebra Appl. 439 (2013), 1312-1320.
• Burnette, Charles and Schmutz, Eric, Periods of Iterated Rational Functions over a Finite Field, 2015, arXiv:1508.04193.
• Flynn, Ryan and Garton, Derek, Graph components and dynamics over finite fields, Int. J. Number Theory 10 (2014), 779-792.
• Roberts, John A. G. and Vivaldi, Franco, Signature of time-reversal symmetry in polynomial automorphisms over finite fields, Nonlinearity 18 (2005), 2171-2192.
• Roberts, John A. G. and Vivaldi, Franco, A combinatorial model for reversible rational maps over finite fields, Nonlinearity 22 (2009), 1965--1982.

And you can try searching for the phrase "finite field" in the arithmetic dynamics bibliography that I've compiled at http://www.math.brown.edu/~jhs/ArithDyn.bib