Irreducible compositions of degree two polynomials over finite fields have regular structure

Abstract

Let $q$ be an odd prime power and $D$ be the set of monic irreducible polynomials in ${\mathbb{F}}_q[x]$ which can be written as a composition of monic degree two polynomials. In this paper we prove that $D$ has a natural regular structure by showing that there exists a finite automaton having $D$ as accepted language. Our method is constructive.

To appear in The Quarterly Journal of Mathematics

References in corpus (3)

• On sets of irreducible polynomials closed by composition
• A Note on Stable Quadratic Polynomials over Fields of Characteristic Two
• On the existence of infinite, non-trivial $F$-sets

Cited by in corpus (3)

• Dynamical height growth: left, right, and total orbits
• Full Orbit Sequences in Affine Spaces via Fractional Jumps and Pseudorandom Number Generation
• The inverse problem for arboreal Galois representations of index two