Open Collections

Periods of iterations of mappings over finite fields with restricted preimage sizes

Banff International Research Station for Mathematical Innovation and Discovery

Let $[n] = \{1, \dots, n\}$ and let $\Omega_n$ be the set of all mappings from $[n]$ to itself. Let $f$ be a random uniform element of $\Omega_n$ and let $\mathbf{T}(f)$ and $\mathbf{B}(f)$ denote, respectively, the least common multiple and the product of the length of the cycles of $f$. Harris proved in 1973 that $\log \mathbf{T}$ converges in distribution to a standard normal distribution and, in 2011, E. Schmutz obtained an asymptotic estimate on the logarithm of the expectation of $\mathbf{T}$ and $\mathbf{B}$ over all mappings on $n$ nodes. We obtain analogous results for random uniform mappings on $n = kr$ nodes with preimage sizes restricted to a set of the form $\{0,k\}$, where $k = k(r) \geq 2$. This is motivated by the use of these classes of mappings as heuristic models for the statistics of polynomials of the form $x^k + a$ over the integers modulo $p$, with $ p \equiv 1 \pmod k$. We also exhibit and discuss our numerical results on this heuristic. Joint work with R. Martins, C. Qureshi and E. Schmutz.

Mathematics; Combinatorics; Probability theory and stochastic processes; Control/optimization/operation research

video/mp4

Author affiliation: Carleton University

2017-04-28

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/61401

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/