A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields (Q2398955): Difference between revisions

Given a polynomial \(f\) over a finite field \(\mathbb{F}_{q}\) of order \(q\), we can form a directed graph \(\Gamma_{f}\) on the vertex set \(\mathbb{F}_{q}\) with a directed edge from \(s\) to \(t\) if \(f(s)=t\). Then we can consider the number of components of this directed graph. In particular, we can ask how that number of components varies as the polynomial does, or for a random choice of the polynomial. Let \(X_{q,k}\) be the indicator variable of whether a component is a \(k\)-cycle, and \(Y_{q,d,k}\) be the number of polynomials of degree \(d\) which give a particular component with \(k\) vertices. One cannot unconditionally say that \(X_{q,k}\) and \(Y_{q,d,k}\) are uncorrelated, but the paper under review proposes a certain heuristic of approximate uncorrelatedness -- this is Hypothesis 3.1 -- and shows that this hypothesis implies a good estimate for the average number of components in \(\Gamma_{f}\) for polynomials of degree \(d\) over \(\mathbb{F}_{q}\). The paper ends with some numerical evidence for the conjecture and some remarks about the situation when rational functions replace polynomials.