7
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ You could look at some of the work by Franco Vivaldi. I believe this is related to your question. $\endgroup$
    – Anthony Quas
    Commented Dec 19, 2015 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
    Commented Dec 19, 2015 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
    Commented Dec 19, 2015 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
    Commented Dec 20, 2015 at 6:47

1 Answer 1

Reset to default
14
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .