# Characterization and Enumeration of Good Punctured Polynomials over Finite Fields

Authors: Somphong Jitman; Aunyarut Bunyawat; Supanut Meesawat; Arithat Thanakulitthirat; Napat Thumwanit
Journal: International Journal of Mathematics and Mathematical Sciences
 (2016)

---

## Abstract

A family of good punctured polynomials is introduced. The complete characterization and enumeration of such polynomials are given over the binary fieldF2. Over a nonbinary finite field Fq, the set of good punctured polynomials of degree less than or equal to 2 are completely determined. For n≥3, constructive lower bounds of the number of good punctured polynomials of degree n over Fq are given.


---

## Body

## 1. Introduction

From the fundamental theorem of algebra, every polynomial over the rational numbersQ (or over the real numbers R) has a root in C. However, it is not guaranteed that a polynomial has a root in Q or in R. Therefore, for a given polynomial over Q (resp., R), it is of natural interest to determine whether it has a root in Q (resp., R). In general, determining whether a given polynomial has a root in a nonalgebraically closed field is an interesting problem and has been extensively studied (see, e.g., [1–4]).In this paper, we introduce punctured forms of a polynomialf(x) over a field F (see the definition below) and focus on determining whether the punctured parts of f(x) have a root in F. Due to the rich algebraic structures and various applications of polynomials over finite fields (see [5–9] and references therein), their properties such as factorization, root finding, and irreducibility have extensively been studied (see [10–13]). In this paper, we mainly focus on punctured polynomials over a finite field which is not an algebraically closed field. The readers may refer to [5] for more details on finite fields and polynomials over finite fields.Letq be a prime power and let Fq denote the finite field of q elements. Denote by Fq∗ the set of nonzero elements in Fq. Let(1)Fqx=∑i=0maixi∣ai∈Fq∀i=0,1,2,…,m,m∈N∪0be the set of all polynomials with indeterminate x over Fq. Let (2)Fqxn=fx∈Fqx∣deg⁡fx≤n,F^qxn=fx∈Fqx∣deg⁡fx=nbe the set of all polynomials of degree less than or equal to n over Fq and the set of all polynomials of degree n over Fq, respectively.Given a polynomialf(x)=∑i=0maixi∈Fq[x] of degree m, for each j∈{0,1,2,…,m}, the jthpunctured polynomial off(x) is defined to be (3)fjx=∑i=0j-1aixi+∑i=j+1maixi-1.For convenience, by abuse of notation, the degree of zero polynomial is defined to be0. Hence, we can write f(0)(x)=0 for all constant polynomials f(x)=a∈Fq.A polynomialf(x)∈Fq[x] of degree m is said to begood punctured if f(j)(x) has a root in Fq for all j∈{0,1,2,…,m}. Otherwise, f(x) is said to bebad punctured. The constant polynomials f(x)=a∈Fq are always good punctured and referred to astrivial good punctured polynomials. A good punctured polynomial is callednontrivial if it is not a trivial good punctured polynomial.Example 1.
Letf(x)=x2+2x+2 be a polynomial in F3[x]. Then f(2)(x)=2x+2, f(1)(x)=x+2, and f(0)(x)=x+2. It is not difficult to see that f(x) is good punctured.Given a positive integern and a prime power q, let T(q,n) and T^(q,n) denote the set of good punctured polynomials of degree less than or equal to n over Fq and the set of all good punctured polynomials of degree n over Fq, respectively. Precisely, (4)Tq,n=fx∈Fqxn∣fjxhas  a  root  inFq∀0≤j≤deg⁡fx,T^q,n=fx∈F^qxn∣fjxhas  a  root  inFq∀0≤j≤n.By convention, since deg⁡(0)=0, we have T(q,0)=T^(q,0)=Fq and Tq,0=T^q,0=q.Remark 2.
From the definitions ofT(q,n) and T^(q,n), we have the following facts: (1)
T^(q,n) is a subset of T(q,n).(2)
T(q,n)=T(q,n-1)∪T^(q,n) is a disjoint union for all n≥2.(3)
Tq,n=Tq,n-1+T^q,n for all n≥2.Example 3.
Over the finite fieldsF2, we have(5)T2,2=0,1,x2,x2+x,x2+x+1,T^2,2=x2,x2+x,x2+x+1.Hence, T2,2=5 and T^2,2=3, respectively.In this paper, we focus on the characterization and enumeration of the good punctured polynomials of degreen over Fq. The complete characterization and enumeration of good punctured polynomials over the binary field F2 are given in Section 2. In Section 3, good punctured polynomials of degree n over Fq, where q>2, are studied. The good punctured polynomials of degree less than or equal to 2 over fields Fq are completely determined. Lower bounds of the size of the set of good punctured polynomials of degree greater than 2 are provided as well. Conclusion and some discussions about future researches on punctured polynomials are provided in Section 4.


## 2. Good Punctured Polynomials over the Binary Field

In this section, we focus on good punctured polynomials over the finite fieldF2. The characterization and enumeration of such polynomials are completely determined.First, we determine the setT(2,n) of good punctured polynomials of degree less than or equal to n over the binary field F2. It is not difficult to see that T(2,1)=F2. For n≥2, the set T(2,n) is given as follows.Theorem 4.
Letn≥2 be a positive integer. Then (6)T2,n=A∪B∪C,where A=∑i=02kxi∣0≤k≤n/2, B=xf(x)∣f(x)∈F2[x]n-1andf(1)=0, and C=x2f(x)∣f(x)∈F2[x]n-2.Proof.
First, we prove thatA∪B∪C⊆T(2,n). Let g(x)∈A∪B∪C. We distinguish the proof into three cases.
Case 1 (g(x)∈A). Then g(x)=∑i=02kxi for some 0≤k≤n/2. It follows that 1 is a root of g(j)(x)=∑i=02k-1xi for all 0≤j≤2k. Hence, g(x)∈T(2,n).
Case 2 (g(x)∈B). Then g(x)=xf(x) for some f(x)∈F2[x]n-1. We have g(0)(1)=f(1)=0 and g(i)(0)=g(0)=0 for all 0<i≤deg(g(x)). Hence, g(i)(x) has a root in F2 for all 0≤i≤deg(g(x)). Therefore, g(x)∈T(2,n).
Case 3 (g(x)∈C). Then g(x)=x2h(x) for some h(x)∈F2[x]n-2. It follows that 0 is a root of g(0)(x)=g(1)(x)=xh(x) and g(i)(x)=x2h(i-2)(x) for all 2≤i≤deg(g(x)). Therefore, f(i)(x) has a root in F2 for all 0≤i≤deg(g(x)). As desired, g(x)∈T(2,n).
On the other hand, letg(x)∈T(2,n). Write g(x)=∑i=0deg(g(x))gixi and consider the following two cases.
Case 1 (g0=0)
Case 1.1 (g1=0). Then g(x)∈C.
Case 1.2 (g1=1). Then deg(g(x))≥1. Since g(0)(x)=∑i=0deg(g(x))-1gi+1xi, we have g(0)(0)=g1=1. It follows that 0=g(0)(1)=∑i=0deg(g(x))-1gi+1=g(1). Hence, g(x)∈B.
Case 2 (g0=1). Since g(0)(0)=g0=1, we have 0=g(0)(1)=∑i=1deg(g(x))gi. Suppose that there exists 1≤j<deg(g(x)) such that gj=0. Since g(j)(0)=g0=1 and g(deg(g(x)))(0)=g0=1, we have(7)0=gj1=∑i=0j-1gi+∑i=j+1deg⁡gxgi,0=gdeg⁡gx1=∑i=0deg⁡gx-1gi.It follows that 0=gj=gdeg(g(x))=1, a contradiction. Hence, gi=1 for all 0≤i≤deg(g(x)). Since 0=g(0)(1)=∑i=1deg(g(x))gi, the degree of g(x) must be even. We conclude that g(x)∈A.
From the two cases, we haveg(x)∈A∪B∪C, and, hence, T(2,n)⊆A∪B∪C.
Therefore,T(2,n)=A∪B∪C as desired.Corollary 5.
Ifn is a positive integer, then (8)T2,n=2ifn=1,3·2n-2+n2+1ifn≥2.Proof.
By direct calculation, we haveT(2,1)={0,1} and T2,1=2.
Next, assume thatn≥2. By Theorem 4, we have(9)T2,n=A∪B∪C,where A=∑i=02kxi∣0≤k≤n/2, B=xf(x)∣f(x)∈F2xn-1andf(1)=0, and C=x2f(x)∣f(x)∈F2xn-2.
SinceA and B∪C are disjoint, by the inclusion-exclusion principle, we have (10)T2,n=A∪B∪C=A+B+C-B∩C.Clearly, A=n/2+1 and C=2n-1. Observe that xf(x)=x∑i=0n-1fixi∈B if and only if 0≤i≤n-1∣fi=1 is even. Hence, (11)B=2n-1.It is not difficult to see that (12)B∩C=x2fx∣fx∈F2xn-2,f1=0,and, hence,(13)B∩C=2n-2.Therefore, (14)T2,n=n2+1+2n-1+2n-1-2n-2=3·2n-2+n2+1as desired.Next, we determine the setT^(2,n) of good punctured polynomials of degree n over the binary field F2. Since T(2,1)=F2, we have T^(2,1)=∅. For n≥2, the set T^(2,n) can be determined as follows.Theorem 6.
Ifn≥2 is a positive integer, then (15)T^2,n=A^∪B^∪C^ifniseven,B^∪C^ifnisodd,where A^=∑i=0nxi, B^=xfx+xn-1∣f(x)∈F2xn-2andf(1)=1, and C^=x2fx+xn-2∣f(x)∈F2xn-3.Proof.
We prove the statement by determining the elements inT(2,n) of degree n. Let A=∑i=02kxi∣0≤k≤n/2, B=xf(x)∣f(x)∈F2xn-1andf(1)=0, and C=x2f(x)∣f(x)∈F2xn-2 be defined as in Theorem 4.
It is not difficult to see that the set of elements inB (resp., C) of degree n is B^ (resp., C^).
Ifn is even, then the set of elements in A of degree n is A^. In the case where n is odd, the set of elements in A of degree n is empty.
By Theorem4, the result, therefore, follows.Corollary 7.
Ifn is a positive integer, then (16)T^2,n=0ifn=1,3ifn=2,3·2n-3ifn≥3isodd,3·2n-3+1ifn≥4iseven.Proof.
By direct calculation, we haveT^(2,1)=∅ and(17)T^2,2=x2,x2+x,x2+x+1.Hence, we have T^2,1=0 and T^(2,2)=3.
Next, assume thatn≥3. By Theorem 6, we have(18)T^2,n=A^∪B^∪C^ifnis  even,B^∪C^ifnis  odd,where A^, B^, and C^ are defined as in Theorem 6. Since A^ and B^∪C^ are disjoint, by the inclusion-exclusion principle, we have (19)T^2,n=A^∪B^∪C^=A^+B^+C^-B^∩C^.We note that A^=1 and C^=2n-2.
Sincex(f(x)+xn-1)=x∑i=0n-2fixi+xn-1∈B^ if and only if(20)i∣0≤i≤n-2,fi=1is odd, we have (21)B^=2n-2.It is not difficult to see that (22)B^∩C^=x2fx+xn-2∣fx∈F2xn-3,f1=1,and, hence,(23)B^∩C^=2n-3.Therefore, by (18), we have (24)T^2,n=1+2n-2+2n-2-2n-3ifnis  even,2n-2+2n-2-2n-3ifnis  odd=3·2n-3+1ifnis  even,3·2n-3ifnis  oddas desired.Table1 presents the numbers T2,n and T^2,n for n=1,2,…,13. The relation T2,n=T2,n-1+T^2,n in Remark 2 can be easily seen.Table 1
Punctured polynomials overF2.
n
1
2
3
4
5
6
7
8
9
10
11
12
13
T
(
2
,
n
)
2
5
8
15
27
52
100
197
389
774
1542
3079
6151
T
^
(
2
,
n
)
0
3
3
7
12
25
48
97
192
385
768
1537
3072


## 3. Punctured Polynomials over Nonbinary Finite Fields

In this section, we focus on punctured polynomials over nonbinary finite fields. Given a prime powerq>2, the characterization and enumeration of good punctured polynomials of degree less than or equal to 2 over Fq are completely determined. For n≥3, we construct subsets of T(q,n) and T^(q,n) which lead to lower bounds of the cardinalities of T(q,n) and T^(q,n), respectively.Theorem 8.
Ifq>2 is a prime power, then T(q,1)=Fq.Proof.
By the definition,Fq⊆T(q,1). Let f(x)=ax+b∈T(q,1). Since f(0)(x)=a has a root in Fq, we have a=0. Hence, f(x)=b∈Fq as desired.The next corollary follows immediately from Theorem8.Corollary 9.
Ifq>2 is a prime power, then the following statements hold:(i)
Tq,1=q.(ii)
T^(q,1)=∅.(iii)
T^q,1=0.Theorem 10.
Letq>2 be a prime power. Then(25)Tq,2=a2x2+a1x+a0∣a2,a1,a0∈Fq∗×Fq∗×Fq∪a2x2∣a2∈Fq∗∪Fq.Proof.
LetA=a2x2+a1x+a0∣a2,a1,a0∈Fq∗×Fq∗×Fq and B=a2x2∣a2∈Fq∗.
Letf(x)∈A∪B∪Fq. We write f(x)=a2x2+a1x+a0 and consider the proof as two cases.
Case 1 (f(x)∈A). We have f(0)(x)=a2x+a1, f(1)(x)=a2x+a0, and f(2)(x)=a1x+a0. Since a2 and a1 are nonzero, it follows that -a1a2-1, -a0a2-1, and -a0a1-1 are roots of f(0)(x), f(1)(x), and f(2)(x), respectively. Hence, f(x)∈T(q,2).
Case 2 (f(x)∈B). Then f(x)=a2x2 for some a2∈Fq∗. It follows that 0 is a root of f(0)(x)=a2x, f(1)(x)=a2x, and f(2)(x)=0. Therefore, f(x)∈T(q,2).
Case 3 (f(x)∈Fq). Then, by the definition, f(x)∈T(q,2).
On the other hand, letf(x)=a2x2+a1x+a0∈T(q,2). If a2=0, then f(x)=a1x+a0∈T(q,1), and, hence, f(x)=a0∈Fq by Theorem 8. Assume that a2≠0. Then f(0)(x)=a2x+a1, f(1)(x)=a2x+a0, and f(2)(x)=a1x+a0 have a root in Fq.
Case 1 (a1=0). We have that f(2)(x)=a0 has a root in Fq which implies that a0=0. Therefore, f(x)=a2x2∈B.
Case 2 (a1≠0). Since f(0)(x)=a2x+a1 has a root in Fq, we have a2≠0. Hence, f(x)∈A.
From the two cases, it can be concluded thatf(x)∈A∪B∪Fq.
As desired, we haveT(q,2)=A∪B∪Fq.Corollary 11.
Ifq>2 is a prime power, then(26)Tq,2=qq2-2q+3-1.Proof.
LetA=a2x2+a1x+a0∣a2,a1,a0∈Fq∗×Fq∗×Fq and B=a2x2∣a2∈Fq∗ be defined as in the proof of Theorem 10. It is not difficult to see that A, B, and Fq are disjoint. By Theorem 10, we have (27)Tq,2=A∪B∪Fq=A+B+Fq=q-1q-1q+q-1+q=qq2-2q+3-1as desired.Corollary 12.
Ifq is a prime power, then(28)T^q,2=a2x2+a1x+a0∣a2,a1,a0∈Fq∗×Fq∗×Fq∪a2x2∣a2∈Fq∗.Proof.
From Theorem10, it is not difficult to see that the polynomials of degree less than 2 in T(q,2) are f(x)=a∈Fq. Hence, the result follows.Corollary 13.
Ifq is a prime power, then(29)T^q,2=q-1q2-q+1.Proof.
From Corollaries11 and 12, it follows that(30)T^q,2=Tq,2-q=qq2-2q+3-1-q=q-1q2-q+1.In the case wheren≥3, determining the sets T(q,n) and T^(q,n) is more tedious and complicated. For these cases, we give constructive lower bounds of Tq,n and T^q,n.The following results are important tools in constructing lower bounds ofTq,n and T^q,n.Theorem 14 (see [14, Page 588]).
Letn be a positive integer and let q be a prime power. Then the number of monic irreducible polynomials of degree n in Fq[x] is(31)Ln,q=1n∑d∣nμdqn/d,where(32)μn=1ifn=1,0ifncontainsarepeatedprimefactor,-1rifnisaproductofrdistinctprimesis the Möbius function.Theorem 15 (see [3, Section 4.2, Theorem 1]).
Letf(x) be a polynomial of degree 2 or 3 in Fq[x]. Then f(x) is reducible if and only if f(x) has a root in Fq[x].Theorem 16.
Ifq>2 is a prime power, then(33)T^q,3≥12q-1qq+1.Proof.
LetS≔{xf(x)∣f(x)∈F^qx2andf(x)hasarootinFq}.
First, we show thatS⊆T^(q,3). Let g(x)=x(a2x2+a1x+a0)∈S, where a2∈Fq∗ and a1,a0∈Fq. Then g(0)(x)=a2x2+a1x+a0 has a root in Fq and 0 is a root of (34)g1x=a2x2+a1x,g2x=a2x2+a0x,g3x=a1x2+a0x.Hence, g(x)∈T^(q,3) is good punctured.
By Theorem14, the number of monic irreducible polynomials of degree 2 over Fq is (35)Lq,2=12∑d∣2μdq2/d=12μ1q2+μ2q1=12q2-q.Hence, the number of irreducible polynomials of degree 2 over Fq is(36)12q-1q2-q.By Theorem 15, the number of polynomials of degree 2 over Fq having a root in Fq is(37)S=q-1q2-12q-1q2-q=12q-1qq+1.Since S⊆T^(q,3), we have(38)T^q,3≥S=12q-1qq+1as desired.Corollary 17.
Ifq>2 is a prime power, then(39)Tq,3≥3q3-4q2+5q-22.Proof.
By Corollary11 and Theorem 16, we have(40)Tq,2=qq2-2q+3-1,T^q,3≥12q-1qq+1.Hence, by Remark 2, we have the relation (41)Tq,3=Tq,2+T^q,3≥qq2-2q+3-1+12q-1qq+1=3q3-4q2+5q-22.Theorem 18.
Ifq>2 is a prime power, then(42)T^q,4≥12q-1qq2+1.Proof.
LetS≔xfx∣fx∈F^qx3andfxhasarootinFq.
First, we show thatS⊆T^(q,4). Let g(x)=x(a3x3+a2x2+a1x+a0)∈S, where a3∈Fq∗ and a2,a1,a0∈Fq. Then g(0)(x)=a3x3+a2x2+a1x+a0 has a root in Fq and 0 is a root of (43)g1x=a3x3+a2x2+a1x,g2x=a3x3+a2x2+a0x,g3x=a3x3+a1x2+a0x,g4x=a2x3+a1x2+a0x.Therefore, g(x)∈T^(q,4) is good punctured as desired.
By Theorem14, the number of monic irreducible polynomials of degree 3 over Fq is (44)Lq,3=13∑d∣3μdq3/d=12μ1q3+μ3q1=12q3-q.Hence, the number of irreducible polynomials of degree 3 over Fq is(45)12q-1q3-q.By Theorem 15, the number of polynomials of degree 3 over Fq having a root in Fq is(46)S=q-1q3-12q-1q3-q=12q-1qq2+1.Since S⊆T^(q,4), we have (47)T^q,4≥S=12q-1qq2+1as desired.Corollary 19.
Ifq>2 is a prime power, then(48)Tq,4≥q4+2q3-3q2+4q-22.Proof.
By Corollary17, we have(49)Tq,3≥3q3-4q2+5q-22.From Theorem 18, we have(50)T^q,4≥12q-1qq2+1.Hence, by Remark 2, we have the relation (51)Tq,4=Tq,3+T^q,4≥3q3-4q2+5q-22+12q-1qq2+1=q4+2q3-3q2+4q-22.Theorem 20.
Letq>2 be a prime power and let n≥5 be an integer. Then(52)Tq,n≥qn-1+q3-2q2+2q.Proof.
LetA={x2f(x)∣f(x)∈Fqxn-2}.
First, we show thatA∪T(q,2)⊆T(q,n). Clearly, T(q,2)⊆T(q,n). Let g(x)∈A. Then 0 is a root of g(i)(x) for all i=0,1,…,deg(g(x)), and, hence, g(x)∈T(q,n). Note that A∩Tq,2=ax2∣a∈Fq∗. By Corollary 11, we have(53)Tq,2=qq2-2q+2.Therefore, consider(54)Tq,n≥A+Tq,2-A∩Tq,2=qn-1+qq2-2q+3-1-q-1=qn-1+q3-2q2+2q.Corollary 21.
Letq>2 be a prime power and let n≥5 be an integer. Then T^q,n≥(q-1)qn-2.Proof.
The set of elements inA of degree n in the proof of Theorem 20 is A^={x2f(x)∣f(x)∈F^qxn-2}. By Theorem 20, we have(55)T^q,n≥A^≥q-1qn-2.


## 4. Conclusion and Open Problems

The concepts of punctured polynomials and good punctured polynomials are introduced. Over the finite fieldF2, the complete characterization and enumeration of such polynomials are given. Over nonbinary finite fields, the good punctured polynomials of degree less than or equal to 2 are completely determined. For n≥3, constructive lower bounds of the number of good punctured polynomials of degree n are given.In general, the following related problems are also interesting:(1)
Determine the setsT^(q,n) and T^(q,n), where q>2 is a prime power and n≥3 is an integer.(2)
Determine the exact values ofT^q,n and T^q,n, where q>2 is a prime power and n≥3 is an integer.(3)
Improve lower bounds ofT^q,n and T^q,n, where q>2 is a prime power and n≥3 is an integer.(4)
Characterize and enumerate the good punctured polynomials of degreen over the real numbers R or over the rational numbers Q.



---

*Source: 6093219-2016-03-21.xml*