ON 2-SUPERIRREDUCIBLE POLYNOMIALS OVER FINITE FIELDS
J. W. BOBER, L. DU, D. FRETWELL, G. S. KOPP, AND T. D. WOOLEYA BSTRACT. We investigate k-superirreducible polynomials, by which we mean irreducible polynomials that remain irreducible under any polynomial substitution of positive degree at most k. Let F
be a finite field of characteristic p. We show that no 2-superirreducible polynomials exist in F[t] whenp = 2 and that no such polynomials of odd degree exist when p is odd. We address the remainingcase in which p is odd and the polynomials have even degree by giving an explicit formula for thenumber of monic 2-superirreducible polynomials having even degree d. This formula is analogous
to that given by Gauss for the number of monic irreducible polynomials of given degree over a finite
field. We discuss the associated asymptotic behaviour when either the degree of the polynomial or
the size of the finite field tends to infinity.

1. I NTRODUCTION
Superirreducible polynomials are polynomials that resist factorization under polynomial substitutions. Let R be a commutative domain with unity having field of fractions F , and consider apolynomial f ∈ R[t]. For each natural number k, we say that f is weakly k-superirreducible over
R if f (g(t)) is irreducible over F [t] for all polynomials g ∈ R[t] having degree k. If the polynomial
f is weakly k-superirreducible over R for 1 ≤ k ≤ K, then we say that f is K-superirreducible.
In this hierarchy, a 1-superirreducible polynomial is simply an irreducible polynomial. It transpiresthat a polynomial may be weakly k-superirreducible and yet not weakly (k − 1)-superirreducible(and consequently, not k-superirreducible). For example, one may check that x6 +x5 +x3 +x2 +1 isweakly 3-superirreducible over F2 yet not weakly 2-superirreducible. When d ≥ 2 and f ∈ R[t] has
degree d, a consideration of the polynomial f (t + f (t)) reveals that f cannot be k-superirreducible
whenever k ≥ d. The situation when 2 ≤ k < d is more subtle, however, and our focus in thispaper lies on the simplest situation here in which k = 2 and R is a finite field. Let Fq denote thefinite field of q elements, and when 1 ≤ k < d, denote by sk (q, d) the number of monic weakly
k-superirreducible polynomials lying in Fq [t] having degree d. In Proposition 3.6, we provide an
explicit formula for s2 (q, d) analogous to the formula given by Gauss for the number of monic irreducible polynomials of given degree over Fq . A consequence of this formula delivers the asymptotic
formula recorded in our first theorem.
Theorem 1.1. For q a prime power and d a positive integer, the number of 2-superirreducible
polynomials of degree d satisfies:(a) s2 (q, d) = 0 whenever either q is a power of 2 or d is odd;(b) s2 (q, d) = 0 whenever q > (d − 1)2 ;(c) when q is odd and d → ∞ through the even integers,


1 d/2
qd
.
(1.1)
s2 (q, d) = q + O qd2d1991 Mathematics Subject Classification. 11T06, 12E05, 11S05.
Key words and phrases. Irreducibility, finite fields, polynomial compositions.
1

2

BOBER, DU, FRETWELL, KOPP, AND WOOLEY

Superirreducibility has in fact been studied in the past, although not by name. Strengthening theabove pedestrian observation concerning f (t + f (t)), it follows from work of Schinzel [8, Lemma
10] that a polynomial of degree d ≥ 3 lying in Q[t] cannot be (d − 1)-superirreducible. Morerecently, Bober et al. [2] have considered superirreducibility as a potential limitation to the understanding of smooth integral values of polynomials. More precisely, these authors show in [2, Theorem 1.1] that quadratic polynomials f ∈ Q[t] admit polynomial substitutions g ∈ Q[t] of√ arbitrarily
high degree k having the property that all of the factors of f (g(t)) have degree O(k/ log log k).
Consider a positive number ε and an integer k sufficiently large in terms of ε. Then on taking m
to be an integer large enough in terms of both ε and k, it follows that with n = g(m), the polynomial value f (n) has all of its prime factors smaller than nε (see [2, Corollary 1.2]). This provides
strong information about smooth values f (n) for n ∈ Z. It is thus important to understand polynomials f (in degree higher than 2) that resist such factorizations of compositions f (g(t)), since theexistence of smooth values of such polynomials will necessarily be particularly challenging to establish. In [2, Section 6], it is shown that 2-superirreducible polynomials exist in Q[t] having degree
6. Moreover, in work contemporaneous with that reported on herein, the thesis of Du [3, Theorem
1.9.1] has exhibited some infinite families of 2-superirreducible polynomials in Q[t] of degree 4,
including the simple examples f (t) = t4 + 1 and f (t) = t4 + 2.
With a potential local-global principle in mind, it might be expected that insights into the superirreducibility of polynomials over Z and over Q might be gained by examining corresponding
superirreducibility properties over the p-adic integers Zp and p-adic numbers Qp . Such considerations lead in turn to an investigation of the superirreducibility of polynomials over finite fields. We
finish our paper by disappointing the reader in Section 4 with the news that if k ≥ 2 and p is any
prime number, then k-superirreducible polynomials exist over neither Zp nor Qp .
Other authors have considered arithmetic properties of compositions, especially compositional
iterates, of polynomials within the context of arithmetic dynamics. See the papers [6, 7] and thesurvey [1, Section 19] for a wide variety of results and questions concerning irreducibility of polynomial iterates and composites.
2. BASIC LEMMAS
In this section we prove the basic lemmas that provide the infrastructure for our subsequentdiscussions concerning superirreducibility. Recall the definition of k-superirreducibility provided
in our opening paragraph. We begin by expanding on the observation that there are no weakly
k-superirreducible polynomials of degree k or larger.
Lemma 2.1. Let R be a commutative domain with unity, and let f ∈ R[t] be a polynomial of degreed ≥ 2. Then f (t) is not weakly k-superirreducible for any k ≥ d.
Proof. For each non-negative integer r, consider the degree d + r substitution g(t) = t + tr f (t).
We havef (g(t)) = f (t + tr f (t)) ≡ f (t) ≡ 0 (mod f (t)).
Thus, we see that f (g(t)) is divisible by f (t), and it is hence reducible. It follows that f is not
weakly k-superirreducible for k ≥ d.
The next lemma is a mild generalization of [2, Proposition 3.1] to arbitrary fields. The latter
proposition is restricted to the rational field Q, and we would be remiss were we not to record that
Schinzel [9, Theorem 22] attributes this conclusion to Capelli.

ON 2-SUPERIRREDUCIBLE POLYNOMIALS OVER FINITE FIELDS

3

Lemma 2.2. Let K be a field. Suppose that f (x) ∈ K[x] is a monic irreducible polynomial, let
α be a root of f lying in a splitting field extension for f over K, and put L = K(α). Then, for
any non-constant polynomial g(t) ∈ K[t], the polynomial f (g(t)) is reducible in K[t] if and only ifg(t) − α is reducible in L[t].
Proof. We consider the K-algebra A = K[x, t]/(f (x), g(t) − x) from two perspectives. First, on
noting that f (x) is irreducible over K[x], we find that K[x]/(f (x)) ∼= K[α] = K(α) = L. Thus,on the one hand,K[x, t]/(f (x)) ∼A∼== L[t]/(g(t) − α).
(g(t) − x)
Here, of course, we view (g(t)−x) as being an ideal in K[x, t]/(f (x)). On the other hand, similarly,A∼=

K[x, t]/(g(t) − x) ∼= K[t]/(f (g(t))).
(f (x))

Thus, we obtain a K-algebra isomorphism
K[t]/(f (g(t))) ∼= L[t]/(g(t) − α).

(2.1)

Hence K[t]/(f (g(t))) is a field if and only if L[t]/(g(t)−α) is a field, and thus f (g(t)) is irreducible
in K[t] if and only if g(t) − α is irreducible in L[t]. The desired conclusion follows.

We take the opportunity to record a further consequence of the relation (2.1), since it may be ofuse in future investigations concerning superirreducibility.
Lemma 2.3. Let K be a field. Suppose that f (x) ∈ K[x] is a monic irreducible polynomial, andlet g(t) ∈ K[t] be any non-constant polynomial. Then, for any polynomial divisor h(t) of f (g(t)),
we have deg(f )| deg(h).
Proof. The relation (2.1) shows that K[t]/(f (g(t)) has the structure of an L-algebra. Any ring
quotient of an L-algebra is still an L-algebra. Thus, we see that K[t]/(h(t)) is an L-algebra, and inparticular a vector space over L. Consequently, one hasdeg(h) = dimK K[t]/(h(t)) = [L : K] (dimL K[t]/(h(t))) = deg(f ) (dimL K[t]/(h(t))) ,and thus deg(f )| deg(h).

We also provide a trivial lemma explaining the relationship between our definitions of superirreducibility and weak superirreducibility for different values of k.
Lemma 2.4. Let R be a commutative domain with unity, and let f (x) ∈ R[x] and k ∈ N. The
polynomial f (x) is k-superirreducible if and only if it is weakly `-superirreducible for all natural
numbers ` ≤ k. The polynomial f (x) is weakly k-superirredcubible if and only if it is weakly`-superirreducible for all natural numbers ` dividing k.
Proof. All of the implications follow formally from the definitions except for the statement that,
if f (x) is weakly k-superirreducible and `|k, then f (x) is weakly `-superirreducible. To provethis, write k = `m and consider a polynomial g(t) of degree `. The substitution f (g(tm )) is thus
irreducible, and hence so is f (g(t)).
It follows that “2-superirreducible” and “weakly 2-superirreducible” are synonyms.

4

BOBER, DU, FRETWELL, KOPP, AND WOOLEY

3. C OUNTING 2- SUPERIRREDUCIBLE POLYNOMIALS OVER FINITE FIELDS
Recall that when 1 ≤ k < d, we write sk (q, d) for the number of monic weakly k-superirreducible
polynomials lying in Fq [t] having degree d. In particular, the concluding remark of the previous
section shows that s2 (q, d) is the number of monic 2-superirreducible polynomials in Fq [t] having
degree d. Our goal in this section is to establish formulae for s2 (q, d) that deliver the conclusions
recorded in Theorem 1.1.
3.1. Elementary cases. We begin by confirming that when q is a power of 2, and also when d is
odd, one has s2 (q, d) = 0. In fact, rather more is true, as we now demonstrate.
Proposition 3.1. Let p be a prime. Then for all natural numbers ` and d, one has sp (p` , d) = 0.
P
Proof. Consider a polynomial f ∈ Fp` [t] having degree d. Write f (x) = dj=0 aj xj , and note that`aj = apj for each index j. Thus, we havedX`pf (t ) =apj tpj =
j=0

d
X
`−1
ajp tj!p,

j=0

and it follows that f (x) is not weakly p-superirreducible. Consequently, one has sp (p` , d) = 0.



The special case p = 2 of Proposition 3.1 shows that s2 (q, d) = 0 when q is a power of 2. Next,
we turn to polynomials of odd degree over Fq .
Proposition 3.2. When d is an odd natural number, one has s2 (q, d) = 0.
Proof. In view of the case p = 2 of Proposition 3.1, there is no loss of generality in assuming thatq is odd. Let f (x) ∈ Fq [x] be a monic irreducible polynomial of degree d. The polynomial f has
a root α lying in Fqd , and Fqd = Fq (α). By virtue of Lemma 2.2, if we are able to find a quadratic
polynomial g(t) ∈ Fq [t] having the property that g(t) − α has a root in Fqd , then we may infer thatf (g(t)) is reducible. This will confirm that f (x) is not 2-superirreducible, delivering the desiredconclusion.
We may divide into two cases:(a) Suppose first that α = β 2 for some β ∈ Fqd . Then we put g(t) = t2 and observe that thepolynomial g(t) − α has the root β ∈ Fqd .
(b) In the remaining cases, we may suppose that α is not the square of any element of Fqd .
Since q 6= 2, there exists an element b ∈ Fq which is not the square of any element of Fq .
On recalling our assumption that d is odd, we find that b is not the square of any elementin Fqd . Thus, we may infer that b−1 α = β 2 for some β ∈ Fqd . We now put g(t) = bt2 andobserve that the polynomial g(t) − α has the root β ∈ Fqd .
In either case, our previous discussion shows that f (x) is not 2-superirreducible, and this implies
the desired conclusion.
The conclusion of Proposition 3.2 combines with that of Proposition 3.1 to confirm the first assertion of Theorem 1.1. These cases of Theorem 1.1 help to explain the example noted in the
introduction demonstrating that weak (k − 1)-superirreducibility is not necessarily inherited fromthe corresponding property of weak k-superirreducibility. Expanding a little on that example, we
observe that by making use of commonly available computer algebra packages, one finds the following examples of polynomials weakly 3-superirreducible over F2 [x] yet not 2-superirreducible

ON 2-SUPERIRREDUCIBLE POLYNOMIALS OVER FINITE FIELDS

5

over F2 [x]:x6 + x5 + x3 + x2 + 1,
x8 + x6 + x5 + x3 + 1,
x10 + x9 + x7 + x2 + 1,
x10 + x9 + x8 + x4 + x3 + x2 + 1,
x10 + x9 + x7 + x6 + x5 + x4 + x3 + x2 + 1.
In each of these examples of a polynomial f ∈ F2 [x], the failure of 2-superirreducibility follows
from Proposition 3.1. Meanwhile, a direct computation confirms that the polynomial f (g(t)) is
irreducible over F2 [t] for each of the 8 possible monic cubic polynomials g(t) lying in F2 [t]. No
analogous odd degree examples are available, of course, by virtue of Proposition 3.2, though examples of larger even degrees are not too difficult to identify.
3.2. Heuristics. We next address the problem of determining a formula for the number sk (q, d) ofmonic weakly k-superirreducible polynomials of degree d over Fq . The simplest situation here withk = 1 is completely resolved by celebrated work of Gauss, since 1-superirreducibility is equivalent
to irreducibility. Thus, as is well-known, it follows from Gauss [4, p. 602] that
 
1X
d e
s1 (q, d) =
µ
q ,
d
e
e|d

whence, as d → ∞, one has the asymptotic formula


qd
1 d/2
s1 (q, d) =
+O q
.
d
d
The corresponding situation with k ≥ 2 is more subtle. We now motivate our proof of an asymptotic
formula for s2 (q, d) with a heuristic argument that addresses the cases remaining to be considered,namely those where d is even and q is odd. The heuristic argument is based on the following lemma,
which will also be used in the proof.
Lemma 3.3. Let q be an odd prime power, and let f (x) ∈ Fq [x] be a monic irreducible polynomialof even degree d. Let α ∈ Fqd be a root of f (x). The polynomial f (x) is 2-superirreducible if andonly if α + c is not a square in Fqd for all c ∈ Fq .
Proof. As a consequence of Lemma 2.2, the polynomial f (x) is 2-superirreducible in Fq [x] if andonly if g(t) − α is irreducible in Fqd [t] for all quadratic polynomials g ∈ Fq [t]. Since this condition
is invariant under all additive shifts mapping t to t + v, for v ∈ Fq , it suffices to consider only
the quadratic polynomials of the shape g(t) = at2 − b, with a, b ∈ Fq . Moreover, the assumptionthat d is even ensures that a is a square in Fqd , and hence we may restrict our attention further topolynomials of the shape g(t) = t2 − c with c ∈ Fq . So f (x) is 2-superirreducible if and only if theequation t2 − c = α has no solution in Fqd for any c ∈ Fq .
For heuristic purposes, we now model the behaviour of these elements α + c as if they are
randomly distributed throughout Fqd . Since roughly half the elements of Fqd are squares, one should
expect that the condition that α + c is not a square is satisfied for a fixed choice of c with probability
close to 12 . Treating the conditions for varying c ∈ Fq as independent events, we therefore expectthat f (x) is 2-superirreducible with probability close to 1/2q . Multiplying this probability by the

6

BOBER, DU, FRETWELL, KOPP, AND WOOLEY

number of choices for monic irreducible polynomials f (x) of degree d, our heuristic predicts thatwhen d is even and q is odd, one should haveqd.
d2q
We shall see in the next subsection that this heuristic accurately predicts the asymptotic behaviourof s2 (q, d) as d → ∞ through even integers d.
s2 (q, d) ≈3.3. The large d limit. The asymptotic formula predicted by the heuristic described in the previous subsection will follow in the large d limit from Weil’s resolution of the Riemann hypothesis forcurves over finite fields. We make use, specifically, of the Weil bound for certain higher autocorrelations of the quadratic character generalizing Jacobi sums. Our goal in this subsection is the proofof the estimate for s2 (q, d) supplied by the following theorem, an immediate consequence of whichis the asymptotic formula (1.1) supplied by Theorem 1.1.
Theorem 3.4. When q is odd and d is even, one has
qqd< q d/2 .
qd2
2dThe proof of this estimate is based on a more rigorous version of the heuristic argument given in
Section 3.2, and it employs character sums that we now define.
s2 (q, d) −Definition 3.5. Let q be an odd prime power, and write χq for the nontrivial quadratic characterχq : F×q → {1, −1}, extended to Fq by setting χq (0) = 0. We define the order n autocorrelation ofχq with offsets u1 , . . . , un ∈ Fq to be the sumXaq (u1 , . . . , un ) =χq (β + u1 ) · · · χq (β + un ).
β∈FqNoting that this definition is independent of the ordering of the arguments, when U = {u1 , . . . , un }is a subset of Fq , we adopt the convention of writing aq (U ) for aq (u1 , . . . , un ).
Note that aq (U ) ∈ Z for all subsets U of Fq . When |U | = 1 it is apparent that aq (U ) = 0.
Meanwhile, in circumstances where |U | = 2, so that U = {u1 , u2 } for some elements u1 , u2 ∈ Fq
with u1 6= u2 , the autocorrelation aq (U ) = aq (u1 , u2 ) is a quadratic Jacobi sum. Thus, in thissituation, we have aq (u1 , u2 ) = ±1; see [5, Chapter 8]. The higher-order correlations become more
complicated, but we will see that they can easily be bounded. First, we relate the autocorrelationsof χq to the number s2 (q, d) of monic 2-superirreducible polynomials of degree d in Fq [x].
Proposition 3.6. Let q be an odd prime power and d be even. ThenX
1 X d e|U |s2 (q, d) = qµ
q +(−1) aqe (U ) .
d2ee|dd/e odd∅6=U ⊆Fq

Proof. Consider a monic irreducible polynomial f (x) ∈ Fq [x] of degree d, and let α be a root off (x) in Fqd . It follows from Lemma 3.3 that f (x) is 2-superirreducible if and only if α + c is nota square in Fqd for each c ∈ Fq . Since the latter condition is equivalent to the requirement that
χqd (α + c) = −1 for all c ∈ Fq , we see that(Y11, if f is 2-superirreducible,
1 − χqd (α + c) =20, otherwise.
c∈FqON 2-SUPERIRREDUCIBLE POLYNOMIALS OVER FINITE FIELDS

7This relation provides an algebraic formulation of the indicator function for 2-superirreducibility.
Instead of summing this quantity over monic irreducible polynomials, we can instead sum overelements α ∈ Fqd not lying in any proper subfield, dividing by d to account for overcounting. Thus,
we find that
Y1X1s2 (q, d) =1 − χqd (α + c) .
d
2
c∈F
α∈F
q

qd

α∈
/ Fqe (e < d and e|d)

The condition on α in the first summation of this relation may be encoded using the Möbius function. Thus, we obtain
1 X d X Y
1 − χqd (α + c) .
s2 (q, d) = qµd2e α∈F e c∈F
e|d

q

q

When d/e is even, the quadratic character χqd on Fqd restricts to the trivial character on Fqe , andwhen d/e is odd, it instead restricts to χqe . We therefore deduce that
1 X d X Y
s2 (q, d) = qµ(1 − χqe (α + c)) ,d2e α∈F e c∈F
e|dd/e odd

and on observing thatX Y

q

(1 − χqe (α + c)) = q e +α∈Fqe c∈FqqX(−1)|U | aqe (U ),∅6=U ⊆Fq

the desired formula for s2 (q, d) follows.



We next establish a bound on the autocorrelations aqe (U ).
Lemma 3.7. Let q be an odd prime power. Suppose that U is a non-empty subset of Fq with |U | = n.
Then for each positive integer e, one has |aqe (U )| ≤ (n − 1)q e/2 .
Proof. Observe thataqe (U ) =Xχqe (h(β)),β∈Fqewhere h(t) = (t + u1 ) · · · (t + un ) is a polynomial in Fq [t] having roots −u1 , . . . , −un . Since
u1 , . . . , un are distinct and χqe is a multiplicative character of order 2, it follows from a versionof Weil’s bound established by Schmidt that |aqe (U )| ≤ (n − 1)q e/2 ; see [10, Chapter 2, p. 43,
Theorem 2C’].

Now we complete the proof of Theorem 3.4. In this proof, we expend a little extra effort toachieve a more attractive conclusion.
Proof of Theorem 3.4. We begin by observing that, in view of Lemma 3.7, one has
q  
X
X
q
|U |
(−1) aqe (U ) ≤(n − 1)q e/2nn=1∅6=U ⊆Fq
 X
 X
q 
q  
q−1
q
e/2
q
−
=q
n−1
n
n=2
n=2

= q e/2 q(2q−1 − 1) − (2q − q − 1) .

(3.1)

8

BOBER, DU, FRETWELL, KOPP, AND WOOLEY

We note next that since d is assumed to be even, then whenever e is a divisor of d with d/e odd, it
follows that e is even. Moreover, if it is the case that e < d, then e ≤ d/3. The first constraint on e
here conveys us from (3.1) to the upper bound
d/2

X

X

|U |

q−1

(−1) aqe (U ) ≤ 2

X mq(q − 2) + 1
m=0e|d∅6=U ⊆Fqd/e oddq2q−1 (q − 2) + 1 q d/2 .
q−1
Meanwhile, making use also of the second constraint on e, we obtain the bound
X
X
q d/2
qe ≤
q .
qm <
q−1
<

e|d
e < d and d/e odd

0≤m≤d/3

By applying these bounds in combination with Proposition 3.6, we deduce that q d/2
1qqd
q ≤ q d/2 .
s2 (q, d) − q < q (q − 1)2q−1 − 2q−1 + 2
d2
d2
q−1
2d
This completes the proof of Theorem 3.4.



3.4. Vanishing in the large q limit. We turn our attention next to the behaviour of s2 (q, d) whend is fixed and q is large. It transpires that s2 (q, d) = 0 for large enough prime powers q. Thisconclusion follows from Lemma 3.3 once we confirm that for every primitive element α ∈ Fqd ,there exists an element c ∈ Fq for which χqd (α + c) = 1.
Lemma 3.8. Suppose that q is an odd prime power and α ∈ Fqd is a primitive element. Then,
whenever q > (d − 1)2 , one hasXχqd (α + c) < q.
c∈Fq

Proof. Consider the d-dimensional commutative Fq -algebra Fqd = Fq [α]. Observe that the character χqd is not trivial on Fq [α] = Fqd . It follows from Wan [11, Corollary 2.2], taking β = −α in thenotation of that paper, thatX
χqd (c + α) ≤ (d − 1)q 1/2 .
c∈Fq
2Provided that q > (d − 1) , one has (d − 1)q 1/2 < q, and thus the desired conclusion follows.



We are now equipped to establish the final conclusion of Theorem 1.1.
Theorem 3.9. Let d be an even integer, and suppose that q is an odd prime power with q > (d−1)2 .
Then s2 (q, d) = 0.
Proof. Suppose that f (x) ∈ Fq [x] is a 2-superirreducible polynomial of degree d over Fq , andconsider a root α ∈ Fqd of f . By Lemma 3.3, we must have χqd (α + c) = −1 for every c ∈ Fq , andhenceXχqd (α + c) = −q.
c∈FqThis contradicts the estimate supplied by Lemma 3.8, since we have assumed that q > (d − 1)2 .
Consequently, there can be no 2-superirreducible polynomials of degree d over Fq .
ON 2-SUPERIRREDUCIBLE POLYNOMIALS OVER FINITE FIELDS

9

4. R ELATIONSHIP TO RATIONAL AND p- ADIC SUPERIRREDUCIBILITY
Fix a rational prime number p. Then, any monic polynomial f ∈ Z[x] that is irreducible modulo p
is also irreducible over Q[x]. One might guess that this familiar property extends from irreducibility
to superirreducibility. Thus, if the monic polynomial f (x) reduces to a weakly k-superirreducible
polynomial modulo p, one might expect that f (x) is itself weakly k-superirreducible over Z, andperhaps also over Q. We find that such an expectation is in fact excessively optimistic. Indeed,
there are 2-superirreducible polynomials over F3 with integral lifts that are not 2-superirreducible
over Z.
Example 4.1. Consider the polynomial f (x) ∈ Z[x] given by
f (x) = x4 − 12x3 + 2x2 − 39x + 71.
Then, we have f (x) ≡ x4 −x2 −1 (mod 3), and it is verified by an exhaustive check that x4 −x2 −1
is 2-superirreducible in F3 [x]. However, one has
f (3t2 + t) = (t4 + 3t3 + 2t2 − 1)(81t4 − 135t3 − 27t2 + 39t − 71),
so that f (x) is not 2-superirreducible over Z.
Despite examples like the one above, one may still hope that the assumption of additional congruential properties involving higher powers of p might suffice to exclude such problematic examples,
thereby providing a means to lift superirreducible polynomials over Zp to superirreducible polynomials over Z. The following proposition reveals a major obstruction to any such lifting process,since it shows that for each natural number k ≥ 2, there are no p-adic weakly k-superirreducible
polynomials.
Proposition 4.2. Let p be a prime number. When k ≥ 2, there are no weakly k-superirreducible
polynomials over Zp or over Qp .
Proof. Suppose, if possible, that f ∈ Qp [x] is a weakly k-superirreducible polynomial. There is
no loss of generality in assuming that f is an irreducible polynomial lying in Zp [x]. Let α be aroot of f lying in a splitting field extension for f over Qp , and let e = 1 + |vp (α)|, where vp (α)
is defined in such a manner that |α|p = p−vp (α) . Let h ∈ Zp [t] be any polynomial of degreek, put g(t) = pe h(t) + t, and consider the equation g(β) = α. Since |g(α) − α|p < 1 and|g 0 (α)|p = |1 + pe h0 (α)|p = 1, an application of Hensel’s lemma demonstrates that the equationg(β) = α has a solution β ∈ Qp (α). Thus, the equation α = pe h(β) + β has a solution β ∈ Qp (α),
and by appealing to Lemma 2.2, we conclude that the polynomial f (pe h(t) + t) is reducible overQp [t]. Since pe h(t) + t ∈ Zp [t], we see that f is neither weakly k-superirreducible over Zp nor overQp , and we arrive at a contradiction. The desired conclusion follows.

The discussion of this section appears to show, therefore, that superirreducibility over Fp , andindeed superirreducibility over Zp and Qp , is not closely connected to corresponding superirreducibility over Z and Q.
5. ACKNOWLEDGEMENTS
We thank an anonymous referee for providing helpful comments on improving the clarity of thepaper as well as for bringing to our attention the references [1,6,7]. We are grateful to the developersof Magma, Mathematica, and SageMath for writing software that we used to search for numericalexamples and perform plausibility checks on asymptotics proved in this paper.

10

BOBER, DU, FRETWELL, KOPP, AND WOOLEY

The fourth author is supported by NSF grant DMS-2302514. The fifth author is supported by NSF
grants DMS-1854398 and DMS-2001549. The first, third, and fourth authors are also supported by
the Heilbronn Institute for Mathematical Research.
R EFERENCES[1] R. Benedetto, P. Ingram, R. Jones, M. Manes, J. H. Silverman, and T. J. Tucker, Current trends and open problems
in arithmetic dynamics, Bull. Amer. Math. Soc. 56 (2019), no. 4, 611–685.
[2] J. W. Bober, D. Fretwell, G. Martin and T. D. Wooley, Smooth values of polynomials, J. Austral. Math. Soc. 108(2020), no. 2, 245–261.
[3] L. Du, Superirreducibility of polynomials, binomial coefficient asymptotics and stories from my classroom, Ph.D.
Thesis, University of Michigan, 2020.
[4] C. F. Gauss, Untersuchungen über höhere Arithmetik, Chelsea, New York, 1965.
[5] K. Ireland and M. Rosen, A classical introduction to modern number theory, Springer, New York, 1982.
[6] R. Jones and A. Levy, Eventually stable rational functions, Int. J. Number Theory 13 (2017), no. 9, 2299–2318.
[7] R. W. K. Odoni, The Galois theory of iterates and composites of polynomials, Proc. Lond. Math. Soc. (3) 51(1985), no. 3, 385–414.
[8] A. Schinzel, On two theorems of Gelfond and some of their applications, Acta Arith. 13 (1967), no. 2, 177–236.
[9] A. Schinzel, Polynomials with special regard to reducibility, Encyclopedia of Mathematics and its Applications,vol. 77, Cambridge University Press, Cambridge, 2000.
[10] W. M. Schmidt, Equations over finite fields. An elementary approach, Lecture Notes in Math., vol. 536, Springer,
New York, 1976.
[11] D. Wan, Generators and irreducible polynomials over finite fields, Math. Comp. 66 (1997), no. 219, 1195–1212.
S CHOOL OF M ATHEMATICS , U NIVERSITY OF B RISTOL , F RY B UILDING , W OODLAND ROAD , B RISTOL BS8
1UG, UK AND THE H EILBRONN I NSTITUTE FOR M ATHEMATICAL R ESEARCH , B RISTOL , UK
Email address: j.bober@bristol.ac.uk
D EPARTMENT OF M ATHEMATICS , D RAPER B UILDING , B EREA C OLLEGE , 101 C HESTNUT S T., B EREA , KY
40404, USA
Email address: dul@berea.edu
D EPARTMENT OF M ATHEMATICS AND S TATISTICS , F YLDE C OLLEGE , L ANCASTER U NIVERSITY, L ANCASTER
LA1 4YF, UK
Email address: d.fretwell@lancaster.ac.uk
D EPARTMENT OF M ATHEMATICS , L OUISIANA S TATE U NIVERSITY, L OCKETT H ALL , BATON ROUGE , LA
70803, USA
Email address: kopp@math.lsu.edu
D EPARTMENT OF M ATHEMATICS , P URDUE U NIVERSITY, 150 N. U NIVERSITY S TREET, W EST L AFAYETTE , IN
47907-2067, USA
Email address: twooley@purdue.edu