Common divisors of an-1 and bn-1 over function fields

Joseph H. Silverman

Mathematics Department, Box 1917
Brown University
Providence, RI 02912 USA


Ailon and Rudnick have shown that if a,bCT are multiplicatively independent polynomials, then deggcdan1,bn1 is bounded for all n1. We show that if instead a,bFT for a finite field F of characteristic p, then deggcdan1,bn1 is larger than Cn for a constant C=Ca,b>0 and for infinitely many n, even if n is restricted in various reasonable ways (e.g., pn).

Table of Contents

  Introduction... *
1  A preliminary example... *
2  Basic results on rational function fields over finite fields... *
3  The main theorem... *
References  ... *


Let a and b be positive integers that are multiplicatively independent in Q* and let ε>0. Bugeaud, Corvaja, and Zannier [2] recently showed that there is an n0=n0a,b,ε so that (1)gcdan1,bn12εnfor allnn0. In other words, an1 and bn1 cannot share a common factor of significant size. Although elementary to state, the proof requires deep tools from Diophantine analysis, specifically Schmidt's subspace theorem [4].

Ailon and Rudnick [1] consider the analogous problem in which a and b are taken to be polynomials in CT. They prove the stronger result (2)deggcdan1,bn1Ca,bfor alln1. It is natural to consider the situation when a and b are polynomials in FqT, where Fq is a finite field of characteristic p. In this case, some restriction on n is certainly needed, since trivially gcdampk1,bmpk1=gcdam1,bm1pk. In this paper we will show that for a,bFqT, even much stronger restrictions on the allowable values of n do not allow one to prove an estimate analogous to (1), much less one as strong as (2).

Acknowledgements. The author would like to thank Gary Walsh for rekindling his interest in arithmetic properties of divisibility sequences and for drawing his attention to the papers [1] and [2], Felipe Voloch for a helpful discussion of Diophantine approximation in characteristic p, and Andrew Granville and the referee for several suggestions that greatly improved this article.

1.  A preliminary example

As noted in the introduction, Ailon and Rudnick [1] prove that if aT,bTCT are nonconstant polynomials that are multiplicatively independent in CT, then deggcdaTn1,bTn1Ca,bfor alln1. Suppose instead that aT,bTFqT, where Fq is a finite field of characteristic p. It is natural to ask if the Ailon-Rudnick estimate holds, at least if we require that pn. As the following example shows, the answer is no.

Example 1.   Let aT=T and bT=T+1, let Q=pk be some power of p, and take n=Q1. Then  bTn1=T+1Q11=T+1QT+1T+1=TQ+1T+1T+1 =TQTT+1=TTn1T+1=TaTn1T+1. Hence  gcdaTn1,bTn1=gcdT+1aTn1,T+1bTn1T+1 =gcdT+1aTn1,TaTn1T+1 =aTn1T+1. Therefore deggcdaTn1,bTn1=n1.

2.  Basic results on rational function fields over finite fields

Before stating and proving a generalization of the example described in Section 1, we briefly recall some basic arithmetic facts about the rational function field FqT. We start with some notation:

 Sq={πFqT:πis monic and irreducible}. Sq,N={πSq:degπ=N}. Sq,Nα,μ={πSq,N:παmodμ}. ΦqμThe function field analog of Euler's  function ([3], Chapter 1) Φqμ=#FqTμFqT*=qdegμπ|μπSq11qdegπ.

We are now ready to state three important theorems in the arithmetic theory of (rational) function fields.

Theorem 1.   #Sq,N=qNN+OqN2N.

Proof. See [3, Theorem 2.2] for a proof. To see why this is the analogue of the classical prime number theorem, notice that there are qN monic polynomials of degree N in FqT, so the fact that #Sq,N is asymptotic to qNlogqqN is analogous to the fact that πX is asymptotic to XlogX.

Theorem 2.   Let α,μFqT be polynomials with gcdα,μ=1. Then (3)#Sq,Nα,μ=1Φqμ·qNN+OqN2N,

Proof. See [3, Theorem 4.8] for a proof. Of course, Theorem 1 is the special case of Theorem 2 with α=0 and μ=1.

Finally, we will need the following special case of the general r-power reciprocity law in FqT.

Theorem 3.   Let πSq, let μFqT, and let r be an odd integer dividing q1. Then (4)π1modμ(i.e.,πSq1,μ)μis anrthpower moduloπ.

Proof. Let αμrFq* denote the rth power residue symbol ([3, Chapter 3]), and let {α1,α2,,αt} be coset representatives for the elements αFqTμFqT with the property that αμr=1. Then one version [3, Proposition 3.6] of the r-power reciprocity law in FqT says that for any monic irreducible polynomial πFqT, παimodμfor some1itμis anrthpower moduloπ. (Note that our assumption that r is odd ensures that either q1r is even or else Fq has characteristic 2.) In particular, the implication (4) is an immediate consequence of the fact that 1μr=1 for every modulus μ.

3.  The main theorem

Example 1 shows that for particular polynomials aT and bT, the polynomial gcdaTn1,bTn1 can be large when n1modq. We first generalize this example to arbitrary polynomials aT and bT. We then consider more general exponent values and show that it is unlikely that there is any infinite “natural” set of exponents E with the property that nE:deggcdaTn1,bTn1εn is finite for every ε>0.

Theorem 4.   Let Fq be a finite field and let aT,bTFqT be nonconstant monic polynomials. Fix any power qk of q and any congruence class n0ZqkZ. Then there is a positive constant c=ca,b,qk>0 such that deggcdaTn1,bTn1cnfor infinitely manynn0modqk.

Proof. To illustrate the main ideas, we start with the special case k=1 and n0=1, so as in Example 1, we look at exponents n satisfying n1modq. More precisely, we will take n=qN1forN=1,2,3,. For all πSq,N, the group FqTπ*FqN* has order n, so as long as πab, it follows that anbn1modπ. Hence for all sufficiently large N, e.g., Ndegab, we have gcdan1,bn1is divisible byπSq,Nπ, and hence deggcdaTn1,bTn1πSq,Ndegπ=#Sq,N·N. The “Prime Number Theorem for Polynomials” (Theorem 1) says that #Sq,N=qNN+OqN2N, so we find that deggcdaTn1,bTn1qN+OqN2=n+On. This completes the proof of the theorem for n1modq.

In order to obtain more general exponents, we take n to have the form qN1r for a suitable choice of N and r. Then gcdan1,bn1 is divisible by primes π for which both a and b are rth powers modulo π. In order to exploit this weaker condition, we will use the function field versions of the power reciprocity law and Dirichlet's theorem on primes in arithmetic progression.

For now, we assume that gcdq,n0=1, since this is the most interesting case. At the end of the proof we briefly indicate what to do if n0 is divisible by the characteristic. Let r1 be the smallest odd integer satisfying r·n01modqk, and let Q=qkϕr, where ϕ· is the usual Euler phi function. We note that Q1modr. (If we were aiming for better constants, we could take Q to be any power qm with mk and qm1modr.)

For each power QN of Q, we let n=nQN=QN1r, and we observe that since qk|Q, we have r·n1modqk,and hencenn0modqk. It remains to show that deggcdaTn1,bTn1cn for all n=nQN.

Let T=LCMaT,bTFqT be the (monic) least common multiple of aT and bT. We want to use Theorem 3 to find primes for which aT and bT are rth powers, but in order to apply Theorem 3, we need to work with a sufficiently large base field. More precisely, we work in FQT, since our choice of Q ensures that the condition r|Q1 in Theorem 3 is satisfied.

We consider polynomials πSQ,N1,, i.e., monic irreducible polynomials of degree N in FQT satisfying π1mod. Then  πSQ,N1,π1modaandπ1modb aArmodπandbBrmodπ for someA,BFQT,from Theorem 3, anArQN1r=AQN11modπsincedegπ=N, and similarlybn1modπ. This proves that gcdaTn1,bTn1 is divisible by every polynomial in SQ,N1,, so we obtain the lower bound  deggcdaTn1,bTn1πSQ,N1,degπ =#SQ,N1,·N =QNΦQ+OQN2from Theorem 2, where recall that ΦQ=#FQTFQT*=Qdegπ|πSQ11Qdegπ. Finally, using the definition n=QN1r, we see that  deggcdaTn1,bTn1rΦQ·n+On for alln=QN1r, where the big-O constant is independent of N. This gives the desired result, with an explicit value for c.

We are left to deal with the case that n0 is divisible by the characteristic p of Fq. Write n0=pi·n1 with pn1. From the result proven above, we know that (5)deggcdaTn1,bTn1cnfor infinitely manynn1modqk. For these values of n, it follows  deggcdaTpin1,bTpin1=deggcdaTn1pi,bTn1pi =pideggcdaTn1,bTn1 cpin and that pinpin1=n0modqk. Thus the values pin with n satisfying (5) show that Theorem 4 is true when p|n0.

Remark 1.   The proof of Theorem 4 shows that it is true for any c<1ΦQLCMaT,bT, where Q is a certain explicit, but potentially quite large, power of q. More precisely, we can take Q=qm for some m<2kqk, but this huge number is undoubtedly far from optimal.

Remark 2.   We conclude this note by again displaying the striking “trichotomy” in the values of gcdan1,bn1:  Z:loggcdan1,bn1εn. FqT:deggcdan1,bn1cn. CT:deggcdan1,bn1c. For FqT and CT, these estimates are best possible, aside from the delicate question of the value of the constants. However, the situation for Z is less clear. Bugeaud, Corvaja, and Zannier [2, Remark 2 after Theorem 1] note that there is an absolute constant c=ca,b>0 so that loggcdan1,bn1cnloglogn holds for infinitely many n. It is reasonable to guess that this lower bound is also an upper bound, with an appropriate larger choice of c. However, it appears to be an extremely difficult problem to prove any upper bound of the form loggcdan1,bn1fn with fn satisfying fnn0.


[1]   N. Ailon, Z. Rudnick, Torsion points on curves and common divisors of ak1 and bk1, to appear in Acta Arithmetica, arXiv math.NT/0202102.
[2]   Y. Bugeaud, P. Corvaja, U. Zannier, An upper bound for the G.C.D. of an1 and bn1, Math. Zeit. 243 (2003), no. 1, 79–84, MR 1953049, Zbl 1021.11001.
[3]   M. Rosen, Number theory in function fields, GTM 210, Springer-Verlag, New York, 2002, MR 1876657.
[4]   W. Schmidt, Diophantine approximation, Lecture Notes in Mathematics 785, Springer-Verlag, Berlin, 1980, MR 0568710, Zbl 0421.10019.