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?

  • 2
    $\begingroup$ You could look at some of the work by Franco Vivaldi. I believe this is related to your question. $\endgroup$ – Anthony Quas Dec 19 '15 at 19:34
  • 3
    $\begingroup$ 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. $\endgroup$ – Joe Silverman Dec 19 '15 at 19:44
  • 1
    $\begingroup$ 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$). $\endgroup$ – Gerry Myerson Dec 19 '15 at 20:46
  • $\begingroup$ 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. $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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