Tuples of polynomials over finite fields with pairwise coprimality conditions

arXiv:1706.01181v2 [math.NT] 10 Jul 2017 Tuples of polynomials over finite fields with pairwise coprimality conditions JUAN ARIAS DE REYNA Department of Mathematical Analysis, Seville University Seville, Spain [email protected] RANDELL HEYMAN School of Mathematics and Statistics, University of New South Wales Sydney, Australia [email protected] July 12, 2017 Abstract Let qbe a prime power. We estimate the number of tuples of degree bounded monic polynomials (Q1,...,Qv)∈(Fq[z])vthat satisfy given pairwise coprimality conditions. We show how this generalises from monic polynomials in finite fields to Dedekind domains with a finite norm. Keywords: relatively prime, coprime, polynomials, finite fields, Dedekind domains AMS Classification: 11C08 1 Introduction The question of calculating the number of relatively prime polynomials of fixed degree in finite fields arose in [6, Section 4.6.1, Ex.5]. Further results can be found in [4, 10, 2, 3, 5]. This naturally leads to the concept of tuples of polynomials in finite fields that exhibit pairwise coprimality conditions. This concept is also relevant to polynomial remainder codes used in, amongst other things, error correction (see [11] for an early paper). The density of pairwise coprime polynomials in tuples of finite fields can be inferred from a recent paper [8]. We improve on this result in two ways. Firstly, we contemplate generalised pairwise coprimality conditions. That is, conditions that require some, not necessarily all, of the 1 pairs of polynomials to be coprime. Secondly, we give an asymptotic counting formula rather than simply a density. Our results regarding polynomials in finite fields can be applied to the more general setting of ideals in Dedekind domains. We explain this further in Section 2. Our result is heavily based on [1]; a paper that estimates tuples of pairwise coprime integers of bounded height. We use a graph to represent the required primality conditions as follows. Let G= (V, E) be a graph with vvertices and eedges. The set of vertices, V, will be given by V={1,...,v}whilst the set of edges of G, denoted by E, is a subset of the set of pairs of elements of V. That is, E⊆ {{1,2},{1,3},...,{r, s},...,{v−1, v}}. We admit isolated vertices (that is, vertices that are not adjacent to any other vertex). An edge is always of the form {r, s}with r6=sand {r, s}={s, r}. Let X={(Q1,...,Qv)∈(Fq[z])v:Qrmonic,1≤r≤v}. For each real x > 0 and any prime power q, we define the set of all tuples that satisfy the primality conditions by YG(x) := {(Q1,...,Qv)∈X: deg Qr≤x, gcd(Qr, Qs) = 1 if {r, s} ∈ E}. We also let g(x) = |YG(x)|, and denote with dthe maximum degree of the vertices of G. All references to polynomials in Fq[z] will refer to monic polynomials. Finally, let QG(z) = 1 + B2z2+···+Bvzvbe the polynomials associated to the graph G, defined by QG(z) = X F⊂E (−1)|F|z|v(F)|, Q+ G(z) = X F⊂E z|v(F)|,(1.1) where |v(F)|is the number of non-isolated vertices of graph F. Our main result is as follows. Theorem 1.1. For a natural number n > 1, let g(n)be the cardinality of tuples of monic polynomials (Q1,...,Qv)in Fq[z]of degree deg(Qr)≤nsatisfying the coprimality conditions given by the graph Gwhose vertices have degree ≤d. Then for any 0< ε < 1 2we have g(n) = ρG,q (q−1)vqnv1 + OG,q(ndq−n) + OG,q(q−(1−ε)n).(1.2) where ρG,q =Y P∈Fq[z] Pirreducible QG(q−deg(P)).(1.3) The dependence of the constants in the Osymbols on Gand qmay be given 2 explicitly. Namely, OG,q(ndq−n) = exp(d)22e(q−1)v ρG,q O(ndq−n) and OG,q(q−(1−ε)n) = 3 ρG,q e X j=1 ρ+ G′ j,qO(q−(1−ε)n), where the constants in the new Oterms are absolute, ρ+ G,q =Y P Q+ G(q−deg(P)) (1.4) and G′ jis the graph obtained from Gby removing the edge j. We make some comments about ρG,q. Letting p(n) represent the total number of v-tuples of monic polynomials in Fq[x] of degree less than equal to n, we observe that |p(n)|=qn−1 q−1v . Thus, the density of v-tuple of polynomials in Fq[x] that are monic and have the coprimality conditions induced by graph Gis given by lim n→∞ g(n) p(n)=ρG,q. The formula for the density, ρG,q, is explicit. In [1, Section 4] we outlined the calculations for the density of 4-tuples of integers with given pairwise coprimality conditions. The calculations to obtain ρG,q in the case of polynomials in finite fields can be approached in the same way. In fact the calculations to obtain ρG,q in (1.4) are easier. We can group the polynomials by degree, since each polynomial of a given degree contributes in the identical way in the product formula for ρG,q. 1.1 Notation ⊂is used to indicate subset, including the equality case. Dis a Dedekind domain with the finite norm property. I(D) is the set of non-null ideals in D. R(D) is the the ring of ideals defined in Section 2.1. Its elements include Z, Z+and W. X,Yare sets of tuples of polynomials. |X|is the cardinality of the set X. 3 G= (V, E) is a graph with set of vertices Vand edges E. Qusually runs over non-null ideals in D. In the case D=Fq[z], the ring of polynomials with coefficients in the Galois field Fq[z], these ideals can be identified with monic polynomials. A,B,R,Sand occasionally other variables denote non-null ideals on D. Pare prime ideals in Dor monic irreducible polynomials when D=Fq[z]. ω(Q) denotes the number of distinct primes dividing the ideal Q. Or the number of distinct monic irreducible polynomials dividing the polynomial Qwhen D=FQ[z]. µ(Q) denotes 0 if the ideal Qis divisible by P2(the square of some prime ideal) or (−1)ω(Q)if Qis squarefree. In the case of monic polynomials we define µ(Q) analogously. ω(qn) denotes the number of monic polynomials of degree less than or equal to nin Fq[z], (see definition 3.3). N(Q) is the norm of the ideal Q, that is, N(Q) = |D/Q|. If D=Fq[z] then N(Q) is also equal to qdeg Q. r,sare vertices of G, so that 1 ≤r, s ≤v. {r, s}is a typical edge of the graph G. ddenotes the maximum degree of the vertices of G. edenotes the number of edges of G. 2 Problem setting The general setting of our problem refers to a Dedekind domain [9, Chap. 1]. We recall that in a Dedekind domain, D, every nonzero ideal Qhas a unique factorization of prime ideals Q=Pα1 1···Pαk k. We also require that each ideal in Dhas a finite norm. That is, N(Q) := |D/Q|<∞. These Dedekind domains with finite norm property are considered in [9, p. 11]. The norm is multiplicative N(Q1Q2) = N(Q1)N(Q2), and for any given positive real number xthe number of ideals Qwith N(Q)≤xis finite. Our main example is the ring of polynomials with coefficients in a Galois field D=Fq[z]. But there is also another important case when Dis the ring of integers of a number field. For any graph G= (V, E) we seek an estimate of the cardinality of the set GD(x) = {(Q1,...,Qv)∈I(D)v:N(Qr)≤x, gcd(Qr, Qs) = 1 if {r, s} ∈ E}. 4 2.1 The ring of ideals As a tool in our reasoning we consider formal sums of the type X Q∈I(D) n(Q) Q, where the coefficients n(Q) are real (or complex) numbers. We define two operations, sum and product, by the rules X Q∈I(D) n(Q) Q+X Q∈I(D) m(Q) Q=X Q∈I(D) n(Q) + m(Q) Q and X Q∈I(D) n(Q) Q X Q∈I(D) m(Q) Q=X Q∈I(D) 1 QX BC=Q n(B)m(C). Since there is only a finite set of pairs of ideals with BC =Qthe product is well defined. It is clear that this makes the set of these sums, R(D), a ring. A particular element of this ring is Zis given by Z=X Q 1 Q. The unique factorization of ideals in a Dedekind ring gives us Z=X Q 1 Q=Y P1 + 1 P+1 P2+···. Here Pruns through the prime ideals. To give a meaning to the infinite product we may consider simply the product topology in RI(D)of the discrete topology in R. We will write X Q∈I(D) n(Q) Q⊳X Q∈I(D) m(Q) Q(2.1) to denote that for any ideal Qwe have n(Q)≤m(Q). Observe that for any σ > 0 we obtain from (2.1) that, when the series converge, X Q∈I(D) n(Q) N(Q)σ≤X Q∈I(D) m(Q) N(Q)σ. We will use the notation NσX Q∈I(D) n(Q) Q 5 to denote X Q∈I(D) n(Q) N(Q)σ. In particular Nσ(Z) is the Dedekind zeta function in the case of a number field. Notice that Nσ(XY ) = Nσ(X)Nσ(Y) for any X,Y∈ R(D). 2.2 The particular case of polynomials in finite fields Our reasoning depends heavily on the function f(x) that counts the number of ideals of Dhaving norm ≤x. This function behaves very differently in the case of polynomials and for the integers of a number field. So that in spite of our arguments being general we consider here only the case of D=Fq[z]. Therefore for us D=Fq[z] and in this case each non-null ideal is generated by a unique monic polynomial. Therefore we speak of ideals or monic polynomials indistinctly and use the letter Qto denote them. The norm of a ideal Qdepends only on the degree of the corresponding polynomial. Specifically, N(Q) = qrif deg(Q) = r. Therefore instead of consider tuples of polynomials with N(Q)≤x we will consider tuples of polynomials of degree deg(Q)≤n. In the rest of the paper we have fixed a graph G= (V, E), a natural number nand a Dedekind ring D=Fq[z] where qis a fixed prime power. With these elements we construct a general set of tuples X=X(n) = {(Q1,...,Qv)∈Fq[z]v: deg(Qr)≤n, 1≤r≤v},(2.2) and a set of tuples satisfying the coprimality conditions Y=YG(n) = {(Q1,...,Qv)∈X: gcd(Qr, Qs) = 1 for any edge {r, s} ∈ E} (2.3) We are interested in g(n) = |YG(n)|. 3 Exact formula for the number of tuples satisfying the coprimality conditions We give here a general formula to compute g(x) in the case where D=Fq[z]. We begin with two definitions. Definition 3.1. Given the graph G= (V, E), an edge labeling is a tuple (Q1,...,Qe)of non-null ideals in D, associating an ideal Qato each edge a∈E. Analogously we consider vertex labelings. These are associations (Q1,...,Qv) of an ideal Qjfor each vertex j∈V. Frequently (see, for example, the proof of Lemma 4.3) we start with an edge labeling (N1, . . . , Ne) and associate to it a vertex labeling (M1,...,Mv) in the following way. 6 Definition 3.2. Given an edge labeling (N1,...,Ne) the associated vertex labeling (M1,...,Mv)is defined by Mr= lcm{Na:the edge a={r, s}joins the vertex rwith any other one s}, (3.1) where lcm(∅) = 1. We introduce some notation for the number of monic polynomials of degree mor less. Definition 3.3. Let w(qm) = (0m < 0, qm+1−1 q−1m≥0. Any time we use the notations Naand Mjwe assume that (M1,...,Mv) is the associated vertex labelling to the edge labeling (N1,...,Ne). The general formula for g(x) will be an application of the Principle of inclusion-exclusion. Theorem 3.4 (Principle of inclusion-exclusion).Let Xbe a finite set and let Yjbe subsets of Xfor 1≤j≤n. Then Xr n [ j=1 Yj=X J⊂{1,2,...,n} (−1)|J||YJ|, where YJ=Xfor J=∅and YJ=Tj∈JYjfor J6=∅. Lemma 3.5. Consider the graph G= (V, E)and the natural number n. Then g(n), the number of tuples of polynomials (Q1,...,Qv)of degree ≤n satisfying the coprimality conditions imposed by G, is given by the expression g(n) = X (N1,...,Ne) deg(Ne)≤n µ(N1)···µ(Ne) v Y r=1 w(qn/qdeg(Mr)).(3.2) Proof. We have a graph G= (V, E) as described in Section 2. We start with the set of all tuples of polynomials Xdefined in (2.2) We want to define subsets Yjof Xso that the difference Xr n [ j=1 Yj is the set Ydefined in (2.3), so that g(n) = |Y|. If an element (Q1,...,Qv)∈Xis not in Ythere is an edge e={r, s}in G such that gcd(Qr, Qs)6= 1. Then there is an irreducible monic polynomial P such that P|Qrand P|Qs. Obviously this polynomial Pwill be of degree less than or equal to n. 7 Therefore we define a set Y(P,e)for any irreducible polynomial Pof degree ≤nand any edge e={r, s}of Gby Y(P,e)={(Q1,...,Qv)∈X:P|Qrand P|Qs}. With these definitions it is clear that Y=Xr[ P,e Y(P,e). To apply the principle of inclusion-exclusion we consider the intersection YJ= m \ j=1 Y(Pj,ej), J ={(P1, e1),...,(Pm, em)} of a finite set of subsets Y(P,e). A tuple (Q1,...,Qv)∈Xis in the intersection YJif and only if Pj|Qrj and Pj|Qsjfor any of the edges ej={rj, sj}. For any edge elet Ne= lcm{P: (P, e)∈J}with Ne= 1 if the set {P: (P, e)∈J}is empty. In this way, given J, we have associated a monic polynomial to any edge in E. With this notation it is obvious that a tuple (Q1,...,Qv)∈Xis in the intersection YJif and only if Ne|Qrand Ne|Qsfor any edge e={r, s} ∈ E. Notice that the polynomials Neassociated in this way to a given Jare squarefree, because they are the least common multiple of a set of irreducible polynomials. We note that Jdetermines the monic squarefree polynomials N1,. . . , Ne; one for each edge in Ewhose factors are all of degree less than or equal n. Conversely, the monic squarefree polynomials N1,. . . , Ne, one for each edge in ewhose factors are all of degree less than or equal n, determines J. Looking at it in another way the polynomial Qrassociated to a given vertex rneeds to be divisible by Ne1,. . . , Neℓif ejare the edges joining the vertex rwith some other (it maybe none, ℓ= 0 when the vertex is isolated). The condition on Qris equivalent to Mr|Qr, where Mr= lcm(Ne1,...,Neℓ) (taking lcm(∅) = 1, in the case where there is no condition on Qr). Thus, associated to the given finite set Jof pairs (P, e) we have associated a tuple of polynomials (M1,...,Mv) such that YJ= m \ j=1 Y(Pj,ej)={(Q1,...,Qv)∈X:Mr|Qr,1≤r≤v}. Notice that the polynomials Mrassociated in this way to a given Jare squarefree because they are the least common multiple of a set of squarefree polynomials. The tuple of monic polynomials (Q1,...,Qv) is in YJif each component Qr satisfies two conditions. Firstly, deg(Qr)≤nfor Qrto be in X, and secondly Mr|Qrfor Qrto be in YJ. These conditions will be satisfied by any product MrAof Mrwith any monic polynomial Asuch that deg(Mr) + deg(A)≤n. Therefore if deg(Mr)> n, there is no possible Qr. When deg(Mr)≤nlet 8 m=n−deg(Mr). Then Acan be any monic polynomial of degree ≤m. The number of possible polynomials A, and therefore the number of possible Qr, are 1 + q+q2+···+qm=qm+1 −1 q−1. With these notation the cardinality of YJcan be computed as |YJ|= v Y r=1 w(qn/qdeg(Mr)), where the wfunction is as shown in Definition 3.3. We now compute |J|. This is the total number of prime factor across all the Nj. As mentioned before Nj is squarefree, so (−1)|J|= (−1)Pe j=1 ω(Nj)=µ(N1)···µ(Ne). Therefore the Principle of inclusion-exclusion yields g(n) = |Y|=X N1 ···X Ne µ(N1)···µ(Ne) v Y r=1 w(qn/qdeg(Mr)), where the summations are over all monic squarefree polynomials Njwith irreducible factors of degree ≤n. We notice that if some Njhave an irreducible factor of degree > n, then some Mrwill have a degree > n and the corresponding sum will then be zero because the factor w(qn/qdeg(Mr)) will equal zero. Also, if some Njis not squarefree the factor µ(Nj) = 0. Therefore the sum with the restricted conditions on Njwill be the same as the sum extended on all polynomials. In fact we may restrict the summation to the Njof degree ≤n, because otherwise there is a factor w(qn/qdeg(Mr)) = 0 in the corresponding term. This proves equation (3.2). 4 Main part of the asymptotic formula We now establish the asymptotic formula in the main theorem. We begin by establishing the main term and the error term of g(n). The main part of w(qm) is u(qm) := qm+1 q−1. We define the error term v(qm) as the difference, so that for any integer mwe have w(qm) = u(qm) + v(qm).(4.1) We will need the following properties of u(qm) and v(qm): Lemma 4.1. (a) For all integers m∈Zwe have |v(qm)| ≤ 1. (b) For all integers m∈Zwe have |w(qm)| ≤ u(qm). 9 Proof. In the definition of fr,s(Pm) we have to sum for each edge labeling (N1,...,Ne) of G, where Nj|Pm. Each term of the sum has a coefficient |µ(N1)···µ(Ne)|. Therefore we have only to consider the term with Nj= 1 or Nj=P. Any such labeling is determined by the set F={j: 1 ≤j≤e, Nj= P}. Therefore each non-null term corresponds to a subset F⊂E. It is clear that for this labeling the corresponding vertex labeling (M1,...,Mv) will have Mt= 1 or Mt=P. Precisely the set v(F) = ∪{t1,t2}∈F{t1, t2}coincides with the set of vertices twith Mt=P. Therefore the corresponding term is equal to 1/P|v(F)r{r,s}|. After this reasoning it is clear that we have (5.10). We will also need the following. Lemma 5.9. We have fr,s(P) = 1 + a1 P+···+av−2 Pv−2,(5.11) where the sum of all coefficients 1 + a1+···+av−2= 2e. Proof. The sum of the coefficients is the number of non-null terms in the sum (5.9). Therefore 1 + a1+···+av−2= 2e. 5.4 Formula for the coefficient of the main term We are now able to quantify the coefficient of the main term. Lemma 5.10. For any given finite graph G= (V, E), the series X (N1,...,Ne) µ(N1)···µ(Ne) qm1···qmv=Y P QG(q−deg(P)),(5.12) where the sum extends to all possible edge labelings, and mr= deg(Mr)converges absolutely. Proof. First notice that qmr=N(Mr), therefore our sum is the norm of the member of the ring of ideals Z=X (N1,...,Ne) µ(N1)···µ(Ne) M1···Mv .(5.13) Since we want to show absolute convergence we consider instead Z+=X (N1,...,Ne) |µ(N1)···µ(Ne)| M1···Mv .(5.14) In this sum when we take the norm each element is positive, therefore for the convergence we may reorder terms. We do so by joining the terms for which 16 M1···Mv=Qa given ideal. For each Qwe are associating a finite number of terms of the sum (see proof of Lemma 5.3). We obtain Z+=X Q 1 QX (N1,...,Ne) M1···Mv=Q |µ(N1)···µ(Ne)|=X Q f+ G(Q) Q. By Lemma 5.2 (Euler product) we have Z+=Y P1 + f+ G(P) P+f+ G(P2) P2+···. By Lemma 5.4 we have also f+ G(P) = 0. Taking norms we have N(Z+) = Y P1 + f+ G(P2) q2 deg(P)+f+ G(P3) q3 deg(P)+···. The number of monic irreducible polynomials of degree nis ≤qn(see Lemma 6.1). The sum of the coefficients of Q+ G(z) is a constant C=Q+ G(1). Therefore N+(Z)≤ ∞ Y n=01 + C q2nqn It is clear that this is finite because taking logarithms yields ∞ X n=0 qnlog1 + C q2n≤C ∞ X n=0 1 qn=Cq q−1<∞ By similar reasoning we obtain Z=X Q 1 QX (N1,...,Ne) M1···Mv=Q µ(N1)···µ(Ne)=X Q fG(Q) Q. By Lemma 5.2 (Euler product) we have Z=Y P1 + fG(P) P+fG(P2) P2+···. Taking norms N(Z) = X (N1,...,Ne) µ(N1)···µ(Ne) qm1···qmv=Y P QG(q−deg(P)), where the sum extends to all monic irreducible polynomials Pin Fq[z]. 17 Let ρG,q be the sum in (5.12). We have now established an interim result; expressing g(n) as a fully developed main term and a number of error terms as follows. Lemma 5.11. The number g(n), of tuples (Q1,...,Qv)with deg(Qa)≤n satisfying the conditions of coprimality given by the graph G, is g(n) = ρG,qqn q−1v−T+ v X k=1 Rk(5.15) where T=qn q−1vX (N1,...,Ne) some deg(Na)>n µ(N1)···µ(Ne) qm1···qmv,(5.16) and Rksatisfies the bound in (4.4). 6 Bound on the error terms In this Section we obtain bounds on the terms Tand Rkin (5.15) and (5.16). 6.1 Bound on Rk Let rq(n) be the number of monic irreducible polynomials in Fq[z] of degree n. It is well known that (see, for example, [7, Th. 3.25, p.84]) rq(n) = 1 nX d|n µ(n/d)qd.(6.1) We will need the following lemma. Lemma 6.1. The number rq(n)of irreducible polynomials of degree =nin Fq[z]is bounded by rq(n)≤1 nqn. Proof. By (6.1) we have to prove that Pd|nµ(n/d)qd≤qn. If n= 1 or n=p is a prime number, this is trivial. When nis composite let pbe the least prime number dividing n. The divisors of nin decreasing order are n, n/p, d3, d4,... Therefore we have X d|n µ(n/d)qd=qn−qn/p +X k≥3 µ(n/dk)qdk ≤qn−qn/p + n/p−1 X d=1 qd=qn−qn/p +qn/p −1 q−1< qn. 18 We now state and prove a bound on Rk. Lemma 6.2. Let dbe the maximum degree of a vertex in the graph G. The error terms Rkare bounded by  v X k=1 Rk≤exp(d)22evndqn q−1v−1.(6.2) Proof. The proof is similar to the proof of Lemma 5.10. We consider the element of the ring of ideals W=X (N1,...,Ne) deg(Na)≤n |µ(N1)···µ(Ne)| M1···d Mk···Mv , whose norm is equal to the sum appearing in (4.4). That is, N(W) = X (N1,...,Ne) deg(Na)≤n |µ(N1)···µ(Ne)| qm1···d qmk···qmv. The primes Pthat divide the ideals M1···d Mk···Mvappearing in the denominators of Wdivide some of the Na. Therefore deg(P)≤n. It follows that W⊳X∗ Q 1 QX M1···d Mk···Mv=Q |µ(N1)···µ(Ne)|, where the ∗in the sum indicates that we restrict the sum to monic polynomials all of whose prime factors have degree ≤n. This is not an equality because there may be some edge labelings (N1,...,Ne) that satisfy M1···d Mk···Mv=Qthat are not contained in Wbecause of the restriction on the degrees. Noticing the definition of g+ G,k(Q) we have X∗ Q 1 QX M1···d Mk···Mv=Q |µ(N1)···µ(Ne)|=X∗ Q g+ G,k(Q) Q. Reasoning as in the Euler product proof we obtain W⊳Y deg(P)≤n1 + g+ G,k(P) P+g+ G,k(P2) P2+···. By Lemma 5.5 we have g+ G,k(P) = dk, the degree of the vertex kin G. And g+ G,k(Pm) = 0 for m≥v. Let C=Q+ G,k(1) ≤2ebe the sum of g+ G,k(Pm) for 0≤m≤v. Taking norms in the above relation ⊳, yields N(W)≤ n Y m=11 + dk qm+C q2mr(m), 19 where r(m) is the number of monic irreducible polynomials of degree m. From Lemma 6.1 we have r(m)≤1 mqm, and so log N(W)≤ n X m=1 qm mlog1 + dk qm+C q2m≤ n X m=1 qm mdk qm+C q2m =dk n X m=1 1 m+ n X m=1 2e mqm≤(1 + log n)dk+ 2elog 2. Using the bound on N(W) in (4.4) yields |Rk| ≤ 22e(exp(1)n)dkqn q−1v−1. This proves our lemma. 6.2 Bound on the error term T To bound the error term Twe require the following lemma. Lemma 6.3. For any squarefree polynomial Q∈Fq[z]of degree n > 1we have ω(Q)≤4n log nlog q. (6.3) Proof. Let x=1 2 log n log q. We may assume x≥1, for otherwise ω(Q)≤n≤n x= 2 n log nlog q < 4n log nlog q. So we assume x≥1. Since Qis squarefree we have Q=Q1Q2where Q1 is the product of irreducible polynomials P|Qwith degree ≤xand Q2is the product of irreducible polynomials P|Qwith degree > x. The polynomial Q1is a divisor of R1, the product of all irreducibles of degree ≤x. That is, R1=Y k≤xY deg(P)=k P. We have ω(R1) = X k≤x rq(k) and deg(R1) = X k≤x krq(k). All irreducible factors of Q2have degree > x. Therefore xω(Q2)<deg(Q2) = n−deg(Q1). Therefore ω(Q) = ω(Q1) + ω(Q2)≤ω(R1) + n−deg(Q1) x≤n x+X k≤x rq(k), 20 where rq(n) is the number of monic irreducible polynomials in Fq[z] of degree n. By Lemma 6.1 we have rq(k)≤1 kqk, so that for x≥1 we obtain X k≤x rq(k) = X k≤x 1 kqk≤qx(1 + log x). Since x=1 2 log n log q ω(Q)≤2n log nlog q+ (1 + log x) exp1 2 log n log qlog q = 2 n log nlog q+n1 21 + log1 2 log n log q≤4n log nlog q. Note that n1 21 + log1 2 log n log q≤n1 21 + log1 2 log n log 2 , and n log nlog 2 ≤2n log nlog q. So it will suffice to show that n1 21 + log1 2 log n log 2 ≤2n log nlog 2. This is equivalent to y(1 + log y)≤2y,for y=1 2 log n log 2 ≥x≥1, which is easily shown to be true. We now prove the following bound on T. Lemma 6.4. Given any 0< ε < 1 2the term Tdefined in (5.16) is bounded by |T| ≤ 3 e X j=1 ρ+ G′ j,qqn q−1vq−(1−ε)n, n > n0,(6.4) where G′ jis the graph obtained from Gafter removing the edge ej, and n0 depends on εand the number of vertices in the graph G. Proof. By the definition (5.16) of Twe have |T| ≤ qn q−1vX (N1,...,Ne) some deg(Na)>n |µ(N1)···µ(Ne)| qm1···qmv ≤qn q−1ve X a=1 X (N1,...,Ne) deg(Na)>n |µ(N1)···µ(Ne)| qm1···qmv. 21 This is only an inequality because some edge labelings (N1,...,Ne) may have more than one Naof degree > n. We have to bound each of the esums. They are all equivalent, in fact the index of the edges is arbitrary. Therefore we only bound the one with deg(N1)> n. This simplifies our notations a little. Therefore we bound the sum S:= X (N1,...,Ne) deg(N1)>n |µ(N1)···µ(Ne)| qm1···qmv, and the corresponding element of the ring of ideals W:= X (N1,...,Ne) deg(N1)>n |µ(N1)···µ(Ne)| M1···Mv , with N(W) = S. The edge e1={r, s}plays a special role in W. We treat this edge differently from the others. Let (N1,...,Ne) be an edge labeling with deg(N1)> n and squarefree Naso that the corresponding term in Wis not null. By definition of the associated labeling (Definition 3.2), Mr= lcm(N1, Nα1,...,Nαk), Ms= lcm(N1, Nβ1,...,Nβℓ), where we may have k= 0 or ℓ= 0. For any other edge 2 ≤j≤ewe define Dj= gcd(N1, Nj) and then Nj=DjN′ j, Dj|N1.(6.5) Since we assume that Njis squarefree we have gcd(N1, N′ j) = 1. It is clear that Mr= lcm(N1, Dα1N′ α1,...,DαkN′ αk) = N1lcm(N′ α1,...,N′ αk), Ms=N1lcm(N′ β1,...,N′ βℓ). For any other vertex t6=rand t6=swe have Mt= lcm(Nt1,...,Ntm) = lcm(Dt1N′ t1,...,DtmN′ tm) = lcm(Dt1,...,Dtm) lcm(N′ t1,...,N′ tm), where mwill depend on t. It follows that the given term of Wsatisfies |µ(N1)···µ(Ne)| M1···Mv ⊳µ(N1) N2 1 |µ(N2)···µ(Ne)| lcm(N′ α1,...,N′ αk) lcm(N′ β1,...,N′ βl) ·Y 1≤t≤v t6=r, t6=s 1 lcm(Dt1,...,Dtm) lcm(N′ t1,...,N′ tm). 22 This is true even if the Njare not squarefree because in this case both members are equal to 0. We have |µ(N2)···µ(Ne)|=|µ(D2N′ 2)···µ(DeN′ e)| ≤ |µ(D2)···µ(De)| × |µ(N′ 2)···µ(N′ e)|. It follows that |µ(N1)···µ(Ne)| M1···Mv ⊳|µ(N1)| N2 1 |µ(D2)···µ(De)|Y 1≤t≤v t6=r, t6=s 1 lcm(Dt1,...,Dtm) ·|µ(N′ 2)···µ(N′ e)| lcm(N′ α1,...,N′ αk) lcm(N′ β1,...,N′ βl)Y 1≤t≤v t6=r, t6=s 1 lcm(N′ t1,...,N′ tm) Consider the graph G′= (V, E′) obtained from Gby removing the edge e1= {r, s}. Then (N′ 2,...,N′ e) is an edge labeling for G′and M′ t= lcm(N′ t1,...,N′ tm) for any vertex t /∈ {r, s}of G′, while M′ r= lcm(N′ α1,...,N′ αk) and M′ s= lcm(N′ β1,...,N′ βl). The above relation can be written as |µ(N1)···µ(Ne)| M1···Mv ⊳|µ(N1)| N2 1 |µ(D2)···µ(De)|Y 1≤t≤v t6=r, t6=s 1 lcm(Dt1,...,Dtm)· ·|µ(N′ 2)···µ(N′ e)| M′ 1···M′ v . Recall that Djare divisors of N1. The above implies that W⊳W1W2, where we define W1=X deg(N1)>n |µ(N1)| N2 1X (D2,...,De) Dj|N1 |µ(D2)···µ(De)|Y 1≤t≤v t6=r, t6=s 1 lcm(Dt1,...,Dtm), W2=X (N′ 2,...,N′ e) |µ(N′ 2)···µ(N′ e)| M′ 1···M′ v . From the data of N1, (D2,...,De) and (N′ 2,...,N′ e) we reconstruct uniquely the edge labeling (N1,...,Ne) by the equations (6.5). Lemma 5.10 applied to the graph G′gives us that N(W2) = ρ+ G′,q is a finite constant. Therefore we need to bound the norm N(W1) because W⊳W1W2implies N(W)≤ N(W1)N(W2). 23 Let G′be the graph Gwith the edge {r, s}removed. Then (D2,...,De) is a edge labeling of G′and lcm(Dt1,...,Dtm) are the polynomials of the corresponding vertex labeling. Therefore, with the notations of Definition 5.6, we have W1=X deg(N)>n |µ(N)| N2fr,s(N), where fr,s is the function associated to the graph G′and the pair of vertices, not forming an edge in G′,{r, s}. By Lemma 5.9, for each irreducible polynomial P, the norm of fr,s(P) is less than or equal 2e−1because e−1 is the number of edges of the graph G′. Hence if Nis squarefree with ω(N) irreducible factors, we have N(frs(N)) ≤2e ω(N). It follows that the norm of W1is less than or equal to N X deg(N)>n µ(N) N22e ω(N) . It will now suffice to calculate a suitable upper bound on this norm. In fact we will show the following. Lemma 6.5. Given 0< ε < 1/2and a natural number athere is an n0= n0(ε, a)such that NX deg(Q)>n |µ(Q)|2aω(Q) Q2≤3q−(1−ε)n, n ≥n0.(6.6) Proof. Joining the terms with deg(Q) = mand applying (6.3), the norm Nin (6.6) is bounded by N ≤ ∞ X m=n+1 qm1 q2mexpa(log 2)4 m log mlog q. Taking n0=n0(ε, a) we will have 4alog 2 log m< ε, for m≥n0. Therefore we have for n≥n0, N ≤ ∞ X m=n+1 1 qmqεm =1 q(1−ε)n 1 q1−ε−1. Since q≥2 and ε < 1/2, the term 1 q1−ε−1≤1 21/2−1<3 is bounded by an absolute constant. Thus, NX deg(Q)>n |µ(Q)|2aω(Q) Q2≤3q−(1−ε)n, which concludes the proof of Lemma 6.5. This concludes the proof of the upper bound on T. 24 7 Proof of the main theorem We can now prove the main theorem. Proof. In (5.15) we obtained g(n) = ρG,q (q−1)vqnv −T+ v X k=1 Rk. In (6.2) we showed that we have  v X k=1 Rk≤exp(d)22evndqn q−1v−1, where dis the maximum degree of the vertices of G. And in (6.4) we have shown that given 0 < ε < 1 2we have for n≥n0(ε, e) |T| ≤ 3 e X j=1 ρ+ G′ j,qqn q−1vq−(1−ε)n. Hence g(n) = ρG,q (q−1)vqnv1−(q−1)v qnvρG,q T+(q−1)v qnvρG,q v X k=1 Rk. Since (q−1)v qnvρG,q T≤3 ρG,q e X j=1 ρ+ G′ j,qq−(1−ε)n, n ≥n0(ε, e) and (q−1)v qnvρG,q v X k=1 Rk≤exp(d)22e(q−1)v ρG,q ndq−n, we obtain g(n) = ρG,q (q−1)vqnvL, where L= 1 + exp(d)22e(q−1)v ρG,q O(ndq−n) + 3 ρG,q e X j=1 ρ+ G′ j,qO(q−(1−ε)n), and the constants in the Osymbols are absolute in both cases. We can also write this in the simplified form g(n) = ρG,q (q−1)vqnv1 + OG,q(ndq−n) + OG,q(q−(1−ε)n). 25