Speaker: Daniel Panario (Carleton University)

Title: Periods of Iterations of Mappings over Finite Fields

with Indegrees Restricted to {0, k}

Date: Friday, December 2, 2016

Time: 11:30 a.m.

Room: HP 4351 (Macphail Room), Carleton University

ABSTRACT: Let [n]= {1,…,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

T(f) and 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 T converges in distribution to a standard normal distribution and, in 2011, Schmutz obtained an asymptotic estimate on the logarithm of the expectation of T and 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) is at least 2.

This work is motivated by the use of these classes of mappings, by Pollard (1975) and Brent and Pollard (1981), as heuristic models for the statistics of polynomials of the form x^k+a over the integers modulo p, with p congruent to 1 modulo k. If time permits, we exhibit and discuss our numerical results on this heuristic. We will provide, at the beginning of the talk, an introduction to dynamical systems over finite fields and their applications, specially in cryptography.

Joint work with Rodrigo Martins, Claudio Qureshi and Eric Schmutz.