# On the Degree of the GCD of Random Polynomials over a Finite Field

Authors: Kui Liu; Meijie Lu
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, we focus on the degree of the greatest common divisor (gcd) of random polynomials over Fq. Here, Fq is the finite field with q elements. Firstly, we compute the probability distribution of the degree of the gcd of random and monic polynomials with fixed degree over Fq. Then, we consider the waiting time of the sequence of the degree of gcd functions. We compute its probability distribution, expectation, and variance. Finally, by considering the degree of a certain type gcd, we investigate the probability distribution of the number of rational (i.e., in Fq) roots (counted with multiplicity) of random and monic polynomials with fixed degree over Fq.


---

## Body

## 1. Introduction

### 1.1. Background

The greatest common divisorgcd function is very basic in number theory. It has also been considered in the view of probability theory. For an integer n≥2, suppose the random variables X1,…,Xm,… are independent and uniformly distributed on 1,2,…,n. In 1880s, Cesàro [1, 2] first considered the probability distribution of the gcd of random integers and showed that(1)limn⟶∞ℙgcdX1,…,Xr=l=1ζr1lr,for r≥2 and 1≤l≤n, where ζ is the Riemann zeta function. Diaconis and Erdös [3] gave a more precise asymptotic formula for the case r=2, which is(2)ℙgcdX1,X2=l=1ζ21l2+Ologn/lnl,for 1≤l≤n as n⟶∞. One may refer to [4–7], for more related works. In 2013, Fernández and Fernández [8] considered the waiting time for the gcd sequence:(3)G1=X1,G2=gcdX1,X2,…,Gm=gcdX1,…,Xm,….LetTn be the subscript at which the sequence Gmm∈ℕ reaches the value 1 for the first time. They computed the expectation of Tn and showed that(4)limn⟶∞ETn=2+∑m=2∞1−1ζm≈2.7052.Besides random integers, it is also natural to study random polynomials. One interesting topic in this area is to understand the behavior of the number of certain type of roots of random polynomials. For example, Kac [9] considered the number of real roots of random polynomials over the real number field ℝ. One may refer to [10] for a recent progress.In this paper, we focus on the degree of thegcd of random polynomials over the finite field Fq, where q≥2 is a prime power.


### 1.2. Our Results

In the polynomial ringFqT, we use ℳ and ℳn to denote the sets of all monic polynomials and monic polynomials with degree n≥0, respectively. We also use degf to denote the degree of a polynomial f.For integersn≥1 and r≥2, we define(5)Xn,q,r≔deggcdf1,f2,…,fr,where fi, 1≤i≤r, are independent and uniformly distributed on ℳn. We derive the following probability distribution of Xn,q,r.Theorem 1.
For any integersn≥1 and r≥2, the mass function of X=Xn,q,r is(6)ℙX=l=An,q,rlqr−1l,l=0,1,…,n,where(7)An,q,rl=1−1qr−1,0≤l≤n−1,1,l=n.With the help of Theorem1, we investigate the waiting time of the sequence:(8)G1n,q=degf1,G2n,q=deggcdf1,f2,…,Gmn,q=deggcdf1,…,fm,…,where f1,f2,… are independent and uniformly distributed on ℳn, n≥1. Observe that this sequence is decreasing.For an integer0≤s<n, define the random variable Tsn,q to be the subscript at which the sequence Gmn,qm∈ℕ reaches a value not exceeding s for the first time. We compute the probability distribution of Tsn,q and then derive its expectation ETsn,q and variance VTsn,q.Theorem 2.
Suppose integern≥1; then, for integers 0≤s<n and m≥2, the mass function of Tsn,q is(9)ℙTsn,q=m=1qm−2s+11−1qs+1,and furthermore, we have(10)ETsn,q=2qs+1−1qs+1−1,andVTsn,q=qs+1qs+1−12.It is a little bit surprising that the expectation and variance ofTsn,q are independent of the degree n. Using SageMath, we verify this for s=0,1 and some n,q by doing numerical experiments with 106 times. The results are listed in Table 1 (expectation) and Table 2 (variance).Table 1
Numerical results for the expectationETsn,q.
nq,s=2,0q,s=3,0q,s=4,1q,s=5,113.0009222.500092NA.NA.23.0022602.5001152.0666502.04178332.9988542.5001662.0664242.04175842.9987712.4993462.0664662.04176752.9990412.5001602.0668952.041485⋮⋮⋮⋮⋮Theoretical3.0000002.5000002.0666662.041666Table 2
Numerical results for the varianceVTsn,q.
nq,s=2,0q,s=3,0q,s=4,1q,s=5,112.0066090.748455NA.NA.22.0131040.7485230.0712440.04349831.9922050.7474230.0706570.04334541.9889790.7472730.0708830.04340251.9975860.7496030.0715860.043045⋮⋮⋮⋮⋮Theoretical2.0000000.7500000.0711110.043402Enlightened by the proof of Theorem1, we use the degree of gcd to study the number of rational roots (counted with multiplicity) of a random polynomial f∈FqT, where f is uniformly distributed on ℳn,n≥1. Denote this number by Nn,q; then, we have the following result.Theorem 3.
For an integern≥1, the mass function of N=Nn,q is(11)ℙN=l=l+q−1q−11ql∑0≤i≤minn−l,qqi−1qi,for 0≤l≤n.The method for proving Theorem3 is also valid if we consider the number of distinct rational roots of a random polynomial f∈ℳn. This number is investigated by Leont’ev in [11], where combinational methods are used. Comparatively, our method has more flavor of number theory, and we hope it can be used for other roots’ counting problems.Notations: we useℙA to denote the probability of an event A and use EX and VX to denote the expectation and variance of a random variable X. We also use Fq to denote the finite field with q elements and use FqT to denote the polynomial ring over Fq.


## 1.1. Background

The greatest common divisorgcd function is very basic in number theory. It has also been considered in the view of probability theory. For an integer n≥2, suppose the random variables X1,…,Xm,… are independent and uniformly distributed on 1,2,…,n. In 1880s, Cesàro [1, 2] first considered the probability distribution of the gcd of random integers and showed that(1)limn⟶∞ℙgcdX1,…,Xr=l=1ζr1lr,for r≥2 and 1≤l≤n, where ζ is the Riemann zeta function. Diaconis and Erdös [3] gave a more precise asymptotic formula for the case r=2, which is(2)ℙgcdX1,X2=l=1ζ21l2+Ologn/lnl,for 1≤l≤n as n⟶∞. One may refer to [4–7], for more related works. In 2013, Fernández and Fernández [8] considered the waiting time for the gcd sequence:(3)G1=X1,G2=gcdX1,X2,…,Gm=gcdX1,…,Xm,….LetTn be the subscript at which the sequence Gmm∈ℕ reaches the value 1 for the first time. They computed the expectation of Tn and showed that(4)limn⟶∞ETn=2+∑m=2∞1−1ζm≈2.7052.Besides random integers, it is also natural to study random polynomials. One interesting topic in this area is to understand the behavior of the number of certain type of roots of random polynomials. For example, Kac [9] considered the number of real roots of random polynomials over the real number field ℝ. One may refer to [10] for a recent progress.In this paper, we focus on the degree of thegcd of random polynomials over the finite field Fq, where q≥2 is a prime power.


## 1.2. Our Results

In the polynomial ringFqT, we use ℳ and ℳn to denote the sets of all monic polynomials and monic polynomials with degree n≥0, respectively. We also use degf to denote the degree of a polynomial f.For integersn≥1 and r≥2, we define(5)Xn,q,r≔deggcdf1,f2,…,fr,where fi, 1≤i≤r, are independent and uniformly distributed on ℳn. We derive the following probability distribution of Xn,q,r.Theorem 1.
For any integersn≥1 and r≥2, the mass function of X=Xn,q,r is(6)ℙX=l=An,q,rlqr−1l,l=0,1,…,n,where(7)An,q,rl=1−1qr−1,0≤l≤n−1,1,l=n.With the help of Theorem1, we investigate the waiting time of the sequence:(8)G1n,q=degf1,G2n,q=deggcdf1,f2,…,Gmn,q=deggcdf1,…,fm,…,where f1,f2,… are independent and uniformly distributed on ℳn, n≥1. Observe that this sequence is decreasing.For an integer0≤s<n, define the random variable Tsn,q to be the subscript at which the sequence Gmn,qm∈ℕ reaches a value not exceeding s for the first time. We compute the probability distribution of Tsn,q and then derive its expectation ETsn,q and variance VTsn,q.Theorem 2.
Suppose integern≥1; then, for integers 0≤s<n and m≥2, the mass function of Tsn,q is(9)ℙTsn,q=m=1qm−2s+11−1qs+1,and furthermore, we have(10)ETsn,q=2qs+1−1qs+1−1,andVTsn,q=qs+1qs+1−12.It is a little bit surprising that the expectation and variance ofTsn,q are independent of the degree n. Using SageMath, we verify this for s=0,1 and some n,q by doing numerical experiments with 106 times. The results are listed in Table 1 (expectation) and Table 2 (variance).Table 1
Numerical results for the expectationETsn,q.
nq,s=2,0q,s=3,0q,s=4,1q,s=5,113.0009222.500092NA.NA.23.0022602.5001152.0666502.04178332.9988542.5001662.0664242.04175842.9987712.4993462.0664662.04176752.9990412.5001602.0668952.041485⋮⋮⋮⋮⋮Theoretical3.0000002.5000002.0666662.041666Table 2
Numerical results for the varianceVTsn,q.
nq,s=2,0q,s=3,0q,s=4,1q,s=5,112.0066090.748455NA.NA.22.0131040.7485230.0712440.04349831.9922050.7474230.0706570.04334541.9889790.7472730.0708830.04340251.9975860.7496030.0715860.043045⋮⋮⋮⋮⋮Theoretical2.0000000.7500000.0711110.043402Enlightened by the proof of Theorem1, we use the degree of gcd to study the number of rational roots (counted with multiplicity) of a random polynomial f∈FqT, where f is uniformly distributed on ℳn,n≥1. Denote this number by Nn,q; then, we have the following result.Theorem 3.
For an integern≥1, the mass function of N=Nn,q is(11)ℙN=l=l+q−1q−11ql∑0≤i≤minn−l,qqi−1qi,for 0≤l≤n.The method for proving Theorem3 is also valid if we consider the number of distinct rational roots of a random polynomial f∈ℳn. This number is investigated by Leont’ev in [11], where combinational methods are used. Comparatively, our method has more flavor of number theory, and we hope it can be used for other roots’ counting problems.Notations: we useℙA to denote the probability of an event A and use EX and VX to denote the expectation and variance of a random variable X. We also use Fq to denote the finite field with q elements and use FqT to denote the polynomial ring over Fq.


## 2. Preliminaries

The Mo..bius function for monic polynomials is defined by μf=−1r if f is a product of r distinct monic irreducible polynomials and μf=0 if f is not square free. For any f∈ℳ, we have(12)∑d∈ℳd|fμd=1,f=1,0,otherwise.For the mean value ofμf over ℳn, it is well known that(13)∑f∈ℳnμf=1,n=0,−q,n=1,0,n≥2.For a polynomialf in FqT, we defined its norm by f:=qdegf. We derive the following two results, which are needed in proving Proposition 1.Lemma 1.
For integersr,k≥1, we have(14)∑h∈ℳ0≤degh≤ndegkhhr=∑0≤l≤nlkqr−1l,forn≥0,∑d∈ℳ0≤degd≤nμddr=1−1qr−1,forn≥1.Proof.
Note that(15)∑h∈ℳ0≤degh≤ndegkhhr=∑h∈ℳ0≤degh≤ndegkhqrdegh=∑0≤l≤nlkqrl∑h∈ℳl1.
Then, the first statement follows by noting(16)∑h∈ℳl1=ql.
For the second statement, we have(17)∑d∈ℳ0≤degd≤nμddr=∑d∈ℳ0≤degd≤nμdqrdegd=∑0≤l≤n1qrl∑d∈ℳlμd.
This together with (13) gives our desired result.The following lemma is used in the proof of Proposition2.Lemma 2.
For integern≥1, suppose Q=Qn,qT:=∏α∈FqT−αn and h∈ℳ with h|Q and 0≤degh≤n−1. Then, we have(18)∑d∈ℳ,d|Q/h0≤degd≤n−deghμdd=∑0≤i≤minn−degh,qqi−1qi.Proof.
Note that(19)∑d∈ℳ,d|Q/h0≤degd≤n−deghμdd=1+∑d∈ℳ,d|Q/h1≤degd≤n−deghμdqdegd.
Letdegd=i; then, by the definition of μd and Q, we have that d is of the form(20)d=∏j=1iT−αj,1≤i≤minn−degh,q,for some distinct αj∈Fq, 1≤j≤i. From this, we derive that(21)∑d∈ℳ,d|Q/h1≤degd≤n−deghμdqdegd=∑1≤i≤minn−degh,q−1qi∑dsatisfies20d|Q/h1.
Note thatdegh≤n−1; then, we have(22)∑dsatisfies20d|Q/h1=qi.
Then, our required result follows by combining (21) and (22) with (19).


## 3. Proof of Theorem1

We first compute thekth power moments of X=Xn,q,r.Proposition 1.
For any integersn,k≥1 and r≥2, we have(23)EXkn,q,r=∑0≤l≤nAn,q,rllkqr−1l,where An,q,rl is given by (7).Proof.
By the definition of thekth moment, we have(24)EXk=1qrn∑fi∈ℳn,1≤i≤rdegkgcdf1,…,fr.
It follows that(25)EXk=1qrn∑h∈ℳ0≤degh≤ndegkh∑fi∈ℳn,1≤i≤rgcdf1,…,fr=h1.
Then, for the inner sum on the right-hand side of (25), we can write(26)∑fi∈ℳn,1≤i≤rgcdf1,…,fr=h1=∑fi∈ℳn,h|fi1≤i≤r∑d∈ℳd|gcdf1/h,…,fr/hμd,where we have used (12). Changing the order of the summations, we obtain(27)∑fi∈ℳn,1≤i≤rgcdf1,…,fr=h1=∑d∈ℳ0≤degd≤n−deghμd∑f∈ℳndh|f1r=∑d∈ℳ0≤degd≤n−deghμdqrn−degdh.
It follows that(28)∑fi∈ℳn,1≤i≤rgcdf1,…,fr=h1=qrnhr∑d∈ℳ0≤degd≤n−deghμddr.
Inserting (28) to (25) gives(29)EXk=∑h∈ℳ0≤degh≤ndegkhhr∑d∈ℳ0≤degd≤n−deghμddr.
The contribution of thoseh with degh=n is equal to(30)∑h∈ℳndegkhhr=nkqrn∑h∈ℳn1=nkqr−1n.
By Lemma1, the contribution of those h with 0≤degh≤n−1 is equal to(31)1−1qr−1∑0≤l≤n−1lkqr−1l.
Hence, we have(32)EXk=nkqr−1n+1−1qr−1∑0≤l≤n−1lkqr−1l,which is our desired result.Now, we are ready to prove Theorem1. Suppose MXt:=EetX is the moment generating function of X; then, we have(33)MXt=∑k=0∞tkk!EXk.It follows from Proposition1 that(34)MXt=∑k=0∞tkk!∑0≤l≤nAn,q,rllkqr−1l=∑0≤l≤nAn,q,rlqr−1lelt.Then, our desired result follows from the relationship between the moment generating function and the generating function ofX.


## 4. Proof of Theorem2

For an integer0≤s<n, note that the event Gmn,q≤s=Xn,q,m≤s coincides with the event Tsn,q≤m for each m≥2. Hence, by Theorem 1, we have(35)ℙTsn,q≤m=∑0≤l≤sℙXn,q,m=l=1−1qm−1s+1.This gives the mass function in Theorem2.By the definition of the expectation ofTsn,q, we have(36)ETsn,q=∑m=2∞mℙTsn,q=m=2ℙTsn,q>1+∑m=2∞ℙTsn,q>m.It follows from (35) that(37)ETsn,q=2+∑m=2∞1qm−1s+1=2qs+1−1qs+1−1.To deal withVTsn,q, we write(38)VTsn,q=ETsn,q2−ETsn,q2.ForETsn,q2, we have(39)ETsn,q2=∑m=2∞m2ℙTsn,q=m=4ℙTsn,q>1+∑m=2∞2m+1ℙTsn,q>m.It follows from (35) again that(40)ETsn,q2=4+2∑m=2∞mqm−1s+1+∑m=2∞1qm−1s+1=4q2s+1−3qs+1+1qs+1−12,where we have used(41)∑m=2∞mqm−1s+1=2qs+1−1qs+1−12.Inserting (37) and (40) into (38) yields our desired result.


## 5. Proof of Theorem3

We first compute thekth power moments of N=Nn,q.Proposition 2.
For any integersn,k≥1, we have(42)ENkn,q=∑0≤l≤nl+q−1q−1lkql∑0≤i≤minn−l,qqi−1qi.Proof.
Proof. LetQ=Qn,qT:=∏α∈FqT−αn. Notice that(43)Nn,q=deggcdf,Q,where f is random and uniformly distributed on ℳn. Then, by the definition of the kth moment, we have(44)ENk=1qn∑f∈ℳndegkgcdf,Q.
It follows that(45)ENk=1qn∑h∈ℳ,h|Q0≤degh≤ndegkh∑f∈ℳngcdf,Q=h1.
For the inner sum on the right-hand side of (45), we have(46)∑f∈ℳngcdf,Q=h1=∑f∈ℳnh|f∑d∈ℳd∣gcdf/h,Q/hμd,where we have used (12). Changing the order of the summations, we derive(47)∑f∈ℳngcdf,Q=h1=∑d∈ℳ,d|Q/h0≤degd≤n−deghμd∑f∈ℳndh|f1=∑d∈ℳ,d|Q/h0≤degd≤n−deghμdqn−degdh.
By (45) and (47), we obtain(48)ENk=∑h∈ℳ,h|Q0≤degh≤ndegkhh∑d∈ℳ,d|Q/h0≤degd≤n−deghμdd.
Breaking the above sum into two sums according todegh=n or not, we have(49)ENk=∑1+∑2,where(50)∑1=nkqn∑h∈ℳnh|Q1,∑2=∑h∈ℳ,h|Q0≤degh≤n−1degkhh∑d∈ℳ,d|Q/h0≤degd≤n−deghμdd.
To deal with∑1, note that h|Q and degh=n; then, h is of the form(51)h=∏j=1qT−αjrj,for distinct αj∈Fq, 1≤j≤q, where 0≤rj≤n and r1+⋯+rq=n. Thus, we have(52)∑1=nkqn∑0≤rj≤n,1≤j≤qr1+⋯+rq=n1=n+q−1q−1nkqn.
For∑2, using Lemma 2, we derive(53)∑2=∑h∈ℳ,h|Q0≤degh≤n−1degkhh∑0≤i≤minn−degh,qqi−1qi.
Letdegh=l; then, we have(54)∑2=∑0≤l≤n−1lkql∑0≤i≤minn−l,qqi−1qi∑h∈ℳlh|Q1=∑0≤l≤n−1l+q−1q−1lkql∑0≤i≤minn−l,qqi−1qi.
Plugging (52) and (54) into (49) yields our required result.Now, we are ready to prove Theorem3. Suppose MNt:=EetN is the moment generating function of N; then, we have(55)MNt=∑k=0∞tkk!ENk.By Proposition2, we derive(56)MNt=∑k=0∞tkk!∑0≤l≤nl+q−1q−1lkql∑0≤i≤minn−l,qqi−1qi,which gives(57)MNt=∑0≤l≤nl+q−1q−11ql∑0≤i≤minn−l,qqi−1qietl.Then, our desired result follows from the relationship between the moment generating function and the generating function ofN.



---

*Source: 3619347-2021-09-09.xml*