Irreducible polynomials over finite fields produced by composition of quadratics

Abstract

For a set $S$ of quadratic polynomials over a finite field, let $C$ be the (infinite) set of arbitrary compositions of elements in $S$. In this paper we show that there are examples with arbitrarily large $S$ such that every polynomial in $C$ is irreducible. As a second result, when $\#S>1$, we give an algorithm to determine whether all the elements in $C$ are irreducible, using only $O(\#S(\log q{)}^3{q}^{1/2})$ operations.