A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields (Q2398955): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q590772 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: David B. Penman / rank | |||
Normal rank |
Revision as of 23:40, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields |
scientific article |
Statements
A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields (English)
0 references
21 August 2017
0 references
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.
0 references
arithmetic dynamics
0 references
functional graph
0 references
finite field
0 references
polynomial
0 references
rational map
0 references