Hostname: page-component-5cf477f64f-rdph2 Total loading time: 0 Render date: 2025-03-31T05:34:47.686Z Has data issue: false hasContentIssue false

Iterating additive polynomials over finite fields

Published online by Cambridge University Press:  25 March 2025

Lucas Reis*
Affiliation:
Departamento de Matemática, Universidade Federal de Minas Gerais, Belo Horizonte, MG, Brazil

Abstract

Let q be a power of a prime p, let $\mathbb F_q$ be the finite field with q elements and, for each nonconstant polynomial $F\in \mathbb F_{q}[X]$ and each integer $n\ge 1$, let $s_F(n)$ be the degree of the splitting field (over $\mathbb F_q$) of the iterated polynomial $F^{(n)}(X)$. In 1999, Odoni proved that $s_A(n)$ grows linearly with respect to n if $A\in \mathbb F_q[X]$ is an additive polynomial not of the form $aX^{p^h}$; moreover, if q = p and $B(X)=X^p-X$, he obtained the formula $s_{B}(n)=p^{\lceil \log_p n\rceil}$. In this paper we note that $s_F(n)$ grows at least linearly unless $F\in \mathbb F_q[X]$ has an exceptional form and we obtain a stronger form of Odoni’s result, extending it to affine polynomials. In particular, we prove that if A is additive, then $s_A(n)$ resembles the step function $p^{\lceil \log_p n\rceil}$ and we indeed have the identity $s_A(n)=\alpha p^{\lceil \log_p \beta n\rceil}$ for some $\alpha, \beta\in \mathbb Q$, unless A presents a special irregularity of dynamical flavour. As applications of our main result, we obtain statistics for periodic points of linear maps over $\mathbb F_{q^i}$ as $i\to +\infty$ and for the factorization of iterates of affine polynomials over finite fields.

Type
Research Article
Copyright
© The Author(s), 2025. Published by Cambridge University Press on Behalf of The Edinburgh Mathematical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ahmadi, O., Luca, F., Ostafe, A. and Shparlisnki, I., On stable quadratic polynomials, Glasgow Math. J. 54(2) (2012), 359369.CrossRefGoogle Scholar
Ali, N., Stabilité des polynômes, Acta Arith. 119(1) (2005), 5363.CrossRefGoogle Scholar
Ayad, M. and McQuillan, D. L., Irreducibility of the iterates of a quadratic polynomial over a field., Acta Arith. 93(1) (2000), 8797. Corrigendum: Acta Arith 99 (2001), 1, 97.CrossRefGoogle Scholar
Bach, E. and Bridy, A., On the number of distinct functional graphs of affine-linear transformations over finite fields, Linear Algebra Appl. 439(5) (2013), 13121320.CrossRefGoogle Scholar
Benedetto, R., Ingram, P., Jones, R., Manes, M., Silverman, J. H. and Tucker, T., Current trends and open problems in arithmetic dynamics, Bull. Am. Math. Soc. 56(4) (2019), 611685.Google Scholar
Bridy, A., Jones, R., Kelsey, G. and Lodge, R., Iterated monodromy groups of rational functions and periodic points over finite fields, Math. Ann. 390 (2023), 439475.Google Scholar
Danielson, L. and Fein, B., On the irreducibility of the iterates of $x^n-b$, Proc. Am. Math. Soc. 130(6) (2001), 15891596.CrossRefGoogle Scholar
Elspas, B., The theory of autonomous linear sequential networks, IRE Trans. Circ. Theory CT 6(1) (1959), 4560.CrossRefGoogle Scholar
Gómez-Pérez, D., Ostafe, A. and Shparlinski, I., On irreducible divisors of iterated polynomials, Rev. Mat. Iberoam. 30(4) (2014), 11231134.CrossRefGoogle Scholar
Garton, D., Periodic points of polynomials over finite fields, Trans. Am. Math. Soc. 375(7) (2022), 48494871.CrossRefGoogle Scholar
Hernandez-Toledo, R. A., Linear finite dynamical systems, Commun. Algebra 33(9) (2005), 29772989.CrossRefGoogle Scholar
, J. Juul, The Image size of iterated rational maps over finite fields, Int. Math. Res. Not. 5 (2021), 33623388.Google Scholar
Jones, R. and Boston, N., Settled polynomials over finite fields, Proc. Am. Math. Soc. 140(6) (2012), 18491863.CrossRefGoogle Scholar
Li, H. -C., Periodic points of a linear transformation, Linear Algebra Appl. 437(10) (2012), 24892497.CrossRefGoogle Scholar
Lidl, R. and Niederreiter, H., Introduction to Finite Fields and Their applications (Cambridge University Press, New York, NY, USA, 1986).Google Scholar
Manes, M. and Thompson, B., Periodic points in towers of finite fields for polynomials associated to algebraic groups, Rocky Mountain J. Math. 49(1) (2019), 171197.Google Scholar
Mullen, G. L. and Panario, D., Handbook of Finite Fields, (Taylor and Francis, Boca Raton, 2013).CrossRefGoogle Scholar
Odoni, R. W. K., The Galois theory of iterates and composites of polynomials, Proc. London Math. Soc. 51(3) (1985), 385414.CrossRefGoogle Scholar
Odoni, R. W. K., On the Galois groups of iterated generic additive polynomials, Math. Proc. Camb. Phil. Soc. 121(1) (1997), 16.CrossRefGoogle Scholar
Odoni, R. W. K., On additive polynomials over finite fields, Proc. Edinb. Math. Soc. 42(1) (1999), 116.Google Scholar
Qureshi, C. and Reis, L., Dynamics of the a-map over residually finite Dedekind domains, J. Num. Theory 204 (2019), 134154.CrossRefGoogle Scholar
Reis, L., Nilpotent linearized polynomials over finite fields and applications, Finite Fields Appl. 50 (2018), 279292.CrossRefGoogle Scholar
Reis, L., Factorization of a class of composed polynomials, Des. Codes Cryptogr. 87(7) (2018), 16571671.CrossRefGoogle Scholar
Reis, L., On the factorization of iterated polynomials, Rev. Mat. Iberoam. 36(7) (2020), 19571978.Google Scholar
Reis, L., Counting distinct functional graphs from linear finite dynamical systems, Linear Algebra Appl. 656 (2023), 409420.CrossRefGoogle Scholar