SFU Discrete Math Seminar: Daniel Panario

  • Date: 04/14/2023
  • Time: 11:30
Daniel Panario, Carleton University

Simon Fraser University


The Dynamics of Iterating Functions over Finite Fields


When we iterate functions over finite structures, there is an underlying natural functional graph. For a function $f$ over a finite field $\mathbb{F}_q$, this graph has $q$ nodes and a directed edge from vertex $a$ to vertex $b$ if and only if $f(a)=b$. It is well known, combinatorially, that functional graphs are sets of connected components, components are directed cycles of nodes, and each of these nodes is the root of a directed tree. The study of iterations of functions over a finite field and their corresponding functional graphs is a growing area ofresearch, in part due to their applications in cryptography and integer factorization methods like Pollard rho algorithm. Some functions over finite fields when iterated present strong symmetry properties. These symmetries allow mathematical proofs of some dynamical properties such as period and preperiod of a generic element, (average) ``rho length'' (number of iterations until a cycle is formed), number of connected components, cycle lengths, and permutational properties (including the cycle decomposition). We survey the main problems addressed in this area so far. We briefly comment on ongoing research about the functional graph of generalized cyclotomic mappings of finite fields. We study periodic points, cycle structure, and rooted trees attached to periodic points. We briefly comment on some open problems. Based on joint works with Alexander Bors (Carleton, Canada), Rodrigo Martins (UTFPR, Brazil), Claudio Qureshi (UdelaR, Uruguay), Lucas Reis (UFMG, Brazil) and Qiang (Steven) Wang (Carleton, Canada).

Other Information: 

Wednesday at 11:30am in Room K9509