On functional graphs of quadratic polynomials

DOI10.1080/10586458.2017.1391725zbMATH Open1417.05088arXiv1706.04734OpenAlexW2964224850MaRDI QIDQ5228846FDOQ5228846

Authors: Bernard Mans, Min Sha, Daniel Sutantyo, Igor E. Shparlinski 

Publication date: 13 August 2019

Published in: Experimental Mathematics (Search for Journal in Brave)

Abstract: We study functional graphs generated by quadratic polynomials over prime fields. We introduce efficient algorithms for methodical computations and provide the values of various direct and cumulative statistical parameters of interest. These include: the number of connected functional graphs, the number of graphs having a maximal cycle, the number of cycles of fixed size, the number of components of fixed size, as well as the shape of trees extracted from functional graphs. We particularly focus on connected functional graphs, that is, the graphs which contain only one component (and thus only one cycle). Based on the results of our computations, we formulate several conjectures highlighting the similarities and differences between these functional graphs and random mappings.

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

Recommendations

• Functional graphs of polynomials over finite fields
• A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields
• GRAPH COMPONENTS AND DYNAMICS OVER FINITE FIELDS
• Grasping the connectivity of random functional graphs
• The graph structure of Chebyshev polynomials over finite fields and applications

zbMATH Keywords

algorithmsfinite fieldspolynomial mapsrandom mapsfunctional graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph polynomials (05C31) Other character sums and Gauss sums (11T24)

Cites Work

• The arithmetic of dynamical systems
• The average height of binary trees and other simple trees
• On the reduction modulo \(p\) of an absolutely irreducible polynomial \(f(x,y)\)
• Irreducibility of polynomials modulo \(p\) via Newton polytopes.
• Reduzibilität ebener Kurven.
• Title not available (Why is that?)
• Corrigendum: ``On certain algebraic curves related to polynomial maps
• On the iteration of certain quadratic maps over GF(\(p\)).
• Bifurcations and discriminants for polynomial maps
• Title not available (Why is that?)
• Periods of rational maps modulo primes
• Dynamically distinguishing polynomials
• The Galois Theory of Periodic Points of Polynomial Maps
• GRAPH COMPONENTS AND DYNAMICS OVER FINITE FIELDS
• Functional graphs of polynomials over finite fields
• Function digraphs of quadratic maps modulo \(p\)
• Title not available (Why is that?)
• Counting dynamical systems over finite fields
• Periods of iterated rational functions
• On the heuristic of approximating polynomials over finite fields by random mappings
• A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields

Cited In (12)

• Connected components of the graph generated by power maps in prime finite fields
• Iteration entropy
• Functional graphs of families of quadratic polynomials
• On the equational graphs over finite fields
• Title not available (Why is that?)
• Functional graphs of polynomials over finite fields
• A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields
• Pluripolarity of graphs of quasianalytic functions of several variables in the sense of Gonchar
• Dynamics of polynomial maps over finite fields
• Preperiodic points for quadratic polynomials over cyclotomic quadratic fields
• Grasping the connectivity of random functional graphs
• Title not available (Why is that?)

Uses Software

• NTL
• PARI/GP

This page was built for publication: On functional graphs of quadratic polynomials

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