Functional graphs of polynomials over finite fields

DOI10.1016/J.JCTB.2015.07.003MaRDI QIDQ895996zbMATH OpenOpenAlexFDO

Authors Bernard Mans, Luke Mathieson, Min Sha, Igor E. Shparlinski, Sergei Konyagin, Florian Luca

Publication date 11 December 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2718

zbMATH Keywords

algorithms on treescharacter sumsfinite fieldsfunctional graphspolynomial maps

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Given a function $f$ in a finite field ${mathbbF}_q$ of $q$ elements, we define the functional graph of $f$ as a directed graph on $q$ nodes labelled by the elements of ${mathbbF}_q$ where there is an edge from $u$ to $v$ if and only if $f(u)=v$. We obtain some theoretic estimates on the number of non-isomorphic graphs generated by all polynomials of a given degree. We then develop a simple and practical algorithm to test the isomorphism of quadratic polynomials that has linear memory and time complexities. Furthermore, we extend this isomorphism testing algorithm to the general case of functional graphs, and prove that, while its time complexity increases only slightly, its memory complexity remains linear. We exploit this algorithm to provide an upper bound on the number of functional graphs corresponding to polynomials of degree $d$ over ${mathbbF}_q$. Finally, we present some numerical results and compare function graphs of quadratic polynomials with those generated by random maps and pose interesting new problems.

Recommendations

• On functional graphs of quadratic polynomials
• A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields
• GRAPH COMPONENTS AND DYNAMICS OVER FINITE FIELDS
• Counting distinct functional graphs from linear finite dynamical systems
• scientific article; zbMATH DE number 4150334

Cites work

• A congruence theorem for trees
• An alternate proof of Mason's theorem
• Arithmetic properties of periodic points of quadratic maps, II
• Benedetto’s trick and existence of rational preperiodic structures for quadratic polynomials
• Chebyshev action on finite fields
• Cycle structure of power mappings in a residue class ring
• Cycles of quadratic polynomials and rational points on a genus-2 curve
• GRAPH COMPONENTS AND DYNAMICS OVER FINITE FIELDS
• Graph isomorphism, general remarks
• scientific article; zbMATH DE number 3865375 (Why is no real title available?)
• scientific article; zbMATH DE number 16479 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 749580 (Why is no real title available?)
• scientific article; zbMATH DE number 2121181 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• Monomial dynamical systems of dimension one over finite fields
• On the cycle structure of repeated exponentiation modulo a prime
• On the iteration of certain quadratic maps over GF(\(p\)).
• On the number of distinct functional graphs of affine-linear transformations over finite fields
• On the periods of the linear congruential and power generators
• Period of the power generator and small values of Carmichael's function
• Periods of rational maps modulo primes
• Phase transition of multivariate polynomial systems
• POLYNOMIAL IDENTITIES AND HAUPTMODULN
• Preperiodic points for quadratic polynomials over quadratic fields
• Random mappings with restricted preimages
• The S-unit equation over function fields
• The classification of rational preperiodic points of quadratic polynomials over \(\mathbb{Q}\): A refined conjecture
• The iterated Carmichael λ-function and the number of cycles of the power generator
• The structure of digraphs associated with the congruence x k ≡ y (mod n)
• Toward a theory of Pollard's rho method
• Wreath products and proportions of periodic points

Cited in

(24)

• On the graph of a function in many variables over a finite field
• The graph structure of Chebyshev polynomials over finite fields and applications
• On the equational graphs over finite fields
• A natural graph of finite fields distinguishing between models
• Counting distinct functional graphs from linear finite dynamical systems
• Markov chains on finite fields with deterministic jumps
• Tangent-Chebyshev maps over finite fields: new properties and functional graphs
• A limit theorem for the six-length of random functional graphs with a fixed degree sequence
• A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields
• Dynamically distinguishing polynomials
• On the graph of a function in two variables over a finite field
• On the number of distinct functional graphs of affine-linear transformations over finite fields
• On the heuristic of approximating polynomials over finite fields by random mappings
• scientific article; zbMATH DE number 4150334 (Why is no real title available?)
• Iteration entropy
• Periodic points of polynomials over finite fields
• Index divisibility in the orbit of 0 for integral polynomials
• On functional graphs of quadratic polynomials
• Current trends and open problems in arithmetic dynamics
• Functional graphs of families of quadratic polynomials
• Decomposition and factorisation of transients in functional graphs
• Dynamics of polynomial maps over finite fields
• On the deepest cycle of a random mapping
• Polynomial-delay generation of functional digraphs up to isomorphism

This page was built for publication: Functional graphs of polynomials over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q895996)