Vol. 11, No. 1, 2018

Download this article
Download this article For screen
For printing
Recent Issues

Volume 11, 1 issue

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields

Elisa Bellah, Derek Garton, Erin Tannenbaum and Noah Walton

Vol. 11 (2018), No. 1, 169–179
DOI: 10.2140/involve.2018.11.169
Abstract

Flynn and Garton (2014) bounded the average number of components of the functional graphs of polynomials of fixed degree over a finite field. When the fixed degree was large (relative to the size of the finite field), their lower bound matched Kruskal’s asymptotic for random functional graphs. However, when the fixed degree was small, they were unable to match Kruskal’s bound, since they could not (Lagrange) interpolate cycles in functional graphs of length greater than the fixed degree. In our work, we introduce a heuristic for approximating the average number of such cycles of any length. This heuristic is, roughly, that for sets of edges in a functional graph, the quality of being a cycle and the quality of being interpolable are “uncorrelated enough”. We prove that this heuristic implies that the average number of components of the functional graphs of polynomials of fixed degree over a finite field is within a bounded constant of Kruskal’s bound. We also analyze some numerical data comparing implications of this heuristic to some component counts of functional graphs of polynomials over finite fields.

Keywords
arithmetic dynamics, functional graphs, finite fields, polynomials, rational maps
Mathematical Subject Classification 2010
Primary: 37P05
Secondary: 05C80, 37P25
Milestones
Received: 17 October 2016
Accepted: 5 December 2016
Published: 17 July 2017

Communicated by Michael E. Zieve
Authors
Elisa Bellah
Department of Mathematics
University of Oregon
Eugene, OR 97403
United States
Derek Garton
Fariborz Maseeh Department of Mathematics and Statistics
Portland State University
PO Box 751
Portland, OR 97207
United States
Erin Tannenbaum
Fariborz Maseeh Department of Mathematics and Statistics
Portland State University
PO Box 751
Portland, OR 97207
United States
Noah Walton
Fariborz Maseeh Department of Mathematics and Statistics
Portland State University
PO Box 751
Portland, OR 97207
United States