2019 Dec 6, Andrew Bridy, Yale University, Structure and randomness in functional graphs of polynomials over finite fields

Maseeh Mathematics + Statistics Colloquium

Andrew Bridy, Yale University
Structure and randomness in functional graphs of polynomials over finite fields

Let f be a polynomial with integer coefficients. For a finite field Fp, we form a (directed) graph that describes the action of f on Fp by drawing a vertex for each element of Fp and drawing a (directed) edge between the vertices x and y if f(x)=y. For certain special polynomials like f(x)=xn, the graphs are very structured and easy to describe. For most polynomials, various aspects of their functional graphs resemble the graphs of functions chosen at random. We investigate this relationship and prove that, for some families of polynomials, the number of cycles of any length behaves in a way that is as "random" as possible. This is joint work with Derek Garton.