Journal de Théorie des Nombres de Bordeaux, to appear.

SHARPER ABC-BASED BOUNDS FOR CONGRUENT POLYNOMIALS

DANIEL J. BERNSTEIN

Abstract. Agrawal, Kayal, and Saxena recently introduced a new method of proving that an integer is prime. The speed of the Agrawal-Kayal-Saxena method depends on proven lower bounds for the size of the multiplicative semigroup generated by several polynomials modulo another polynomial h. Voloch pointed out an application of the Stothers-Mason ABC theorem in this context: under mild assumptions, distinct polynomials A, B, C of degree at most 1.2 deg h−0.2 deg rad ABC cannot all be congruent modulo h. This paper presents two improvements in the combinatorial part of Voloch’s argument. The first improvement moves the degree bound up to 2 deg h − deg rad ABC. The second improvement generalizes to m ≥ 3 polynomials A_{1}, …, A_{m} of degree at most ((3m − 5)/(3m − 7)) deg h − (6/(3m − 7)m) deg rad A_{1} ⋯ A_{m}.

1. Introduction

Fix a nonconstant univariate polynomial h over a field k. Assume that the characteristic of k is at least 3 deg h − 1. The main theorem of this paper, Theorem 2.3, states that if m ≥ 3 distinct polynomials A_{1}, …, A_{m} are all congruent modulo h and coprime to h then

max\{deg A_{1}, …, deg A_{m}\} > \frac{3m − 5}{3m − 7} deg h − \frac{6}{(3m − 7)m} deg rad A_{1} ⋯ A_{m}.

As usual, rad X means the largest monic squarefree divisor of X, i.e., the product of the monic irreducibles dividing X. If deg rad A_{1} ⋯ A_{m} < (m/3) deg h then this bound is better than the obvious bound max{deg A_{1}, …, deg A_{m}} > deg h − 1.

For example, if distinct polynomials A, B, C are congruent modulo h and coprime to h then max{deg A, deg B, deg C} > 2 deg h − deg rad ABC. No better bound is possible in this level of generality: if h = x^{10} − 1, A = x^{20}, B = x^{10}, and C = 1 then rad ABC = rad x^{30} = x so 2 deg h − deg rad ABC = 19.

The proof relies on the Stothers-Mason ABC theorem. Analogous bounds in the number-field case follow from the ABC conjecture.

Previous work. Voloch in [3] proved that max{deg A, deg B, deg C} > 1.2 deg h− 0.2 deg rad ABC. This paper improves Voloch’s result in two ways: first, it is quantitatively stronger, in the interesting case that deg rad ABC < deg h; second, it applies to larger values of m.

Date: 2003.10.01. Permanent ID of this document: 1d9e079cee20138de8e119a99044baa3.

2000 Mathematics Subject Classification. Primary 11C08.

The author was supported by the National Science Foundation under grant DMS–0140542, and by the Alfred P. Sloan Foundation. He used the libraries at the Mathematical Sciences Research Institute and the University of California at Berkeley.

Application. Consider the subgroup G of (k[x]/h)^{∗} generated by {x − s : s ∈ S}, where S ⊆ k and 0 ∉ h(S). The Agrawal-Kayal-Saxena primality-proving method requires a lower bound on #G for groups G of this type, typically with #S = deg h. The primality-proving method becomes faster as the lower bound on #G increases, as discussed in [1, Section 7].

This paper shows that #G ≥ \frac{1}{m−1} \binom{⌊((3m−5)/(3m−7)) deg h−(6/(3m−7)m)#S⌋+#S}{#S} for any m ≥ 3. Indeed, the binomial coefficient is the number of products of powers of {x − s} in k[x] of degree at most ⌊((3m − 5)/(3m − 7)) deg h − (6/(3m − 7)m)#S⌋; m distinct such products cannot all have the same image modulo h.

In particular, if #S = deg h, then #G ≥ \frac{1}{3} \binom{⌊2.1 deg h⌋}{deg h} ≈ 4.27689^{deg h}. Compare this to the bound #G ≥ \binom{2 deg h−1}{deg h} ≈ 4^{deg h} obtained from a degree bound of deg h − 1. Note that the improvement requires m > 3.

Different methods from [3] produce a lower bound around 5.828^{deg h}, so the ABCbased techniques in [3] and in this paper have not yet had an impact on the speed of primality proving. However, I suspect that these techniques have not yet reached their limits.

2. Proofs

Theorem 2.1. Let k be a field. Let h be a positive-degree element of the polynomial ring k[x]. Assume that 1, 2, 3, …, 3 deg h − 2 are invertible in k. Let A, B, C be distinct nonzero elements of k[x]. If gcd{A, B, C} = 1 and A ≡ B ≡ C (mod h) then max{deg A, deg B, deg C} > 2 deg h − deg rad ABC.

Proof. Assume without loss of generality that deg A = max{deg A, deg B, deg C}. The nonzero polynomial A−B is a multiple of h, so deg A ≥ deg(A−B) ≥ deg h > 0; thus deg rad ABC > 0.

If deg A ≥ 2 deg h then deg A > 2 deg h − deg rad ABC; done.

Define U = (B−C)/h, V = (C−A)/h, and W = (A−B)/h. Then U ≠ 0; V ≠ 0; W ≠ 0; U, V, W each have degree at most deg A − deg h; and UA + V B + W C = 0. Define D = gcd{UA, V B, W C}.

If deg D = deg UA then UA divides V B, W C; so A divides V W A, V W B, V W C; so A divides gcd{V W A, V W B, V W C} = V W; but V W ≠ 0, so deg A ≤ deg V W ≤ 2(deg A − deg h); so deg A ≥ 2 deg h; done.

Assume from now on that deg D < deg UA and that deg A ≤ 2 deg h − 1. Then deg(UA/D) is between 1 and 2 deg A−deg h ≤ 3 deg h−2; so the derivative of UA/D is nonzero. Also UA/D+V B/D+W C/D = 0, and gcd{UA/D, V B/D, W C/D} = 1. By Theorem 3.1 below, deg(UA/D) < deg rad((UA/D)(V B/D)(W C/D)).

The proof follows Voloch up to this point. Voloch next observes that D divides gcd{UV W A, UV W B, UV W C} = UV W gcd{A, B, C} = UV W. I claim that more is true: D rad((UA/D)(V B/D)(W C/D)) divides UV W rad ABC.

(In other words: If d = min{u + a, v + b, w + c} and min{a, b, c} = 0 then d + [u + v + w + a + b + c > 3d] ≤ u + v + w + [a + b + c > 0]. Proof: Without loss of generality assume a = 0. Then d ≤ u ≤ u + v + w. If d < u + v + w then d + [⋯] ≤ d + 1 ≤ u + v + w ≤ u + v + w + [⋯] as claimed. If a + b + c > 0 then d+[⋯] ≤ u+v+w+1 = u+v+w+[⋯] as claimed. Otherwise u+v+w+a+b+c = d ≤ 3d so d + [u + v + w + a + b + c > 3d] = d ≤ u + v + w ≤ u + v + w + [⋯] as claimed.)

Thus deg UA < deg(D rad((UA/D)(V B/D)(W C/D))) ≤ deg(UV W rad ABC). Hence deg A < deg(V W rad ABC) ≤ 2(deg A − deg h) + deg rad ABC; i.e., deg A > 2 deg h − deg rad ABC as claimed. □

Theorem 2.2. Let k be a field. Let h be a positive-degree element of the polynomial ring k[x]. Assume that 1, 2, 3, …, 3 deg h − 2 are invertible in k. Let A, B, C be distinct nonzero elements of k[x]. If gcd{A, B, C} is coprime to h and A ≡ B ≡ C (mod h) then

max{deg A, deg B, deg C}

> 2 deg h − deg rad A − deg rad B − deg rad C

+ deg rad gcd{A, B} + deg rad gcd{A, C} + deg rad gcd{B, C}.

Proof. Write G = gcd{A, B, C}. Then G is coprime to h, so A/G ≡ B/G ≡ C/G (mod h). By Theorem 2.1,

max\{deg \frac{A}{G}, deg \frac{B}{G} , deg \frac{C}{G}\} > 2 deg h − deg rad \frac{ABC}{GGG} ≥ 2 deg h − deg rad ABC,

so max{deg A, deg B, deg C} ≥ 2 deg h + deg G − deg rad ABC. But deg G ≥ deg rad G = deg rad ABC −deg rad A−deg rad B −deg rad C +deg rad gcd{A, B}+ deg rad gcd{A, C} + deg rad gcd{B, C} by inclusion-exclusion. □

Theorem 2.3. Let k be a field. Let h be a positive-degree element of the polynomial ring k[x]. Assume that 1, 2, 3, …, 3 deg h − 2 are invertible in k. Let S be a finite subset of k[x] − {0}, with #S ≥ 3. If each element of S is coprime to h, and all the elements of S are congruent modulo h, then

max\{deg A : A ∈ S\} > \frac{3#S − 5}{3#S − 7} deg h − \frac{6}{(3#S − 7)#S} deg rad ∏_{A∈S} A.

For example, max{deg A : A ∈ S} > 1.4 deg h − 0.3 deg rad ∏_{A∈S} A if #S = 4, and max{deg A : A ∈ S} > 1.25 deg h − 0.15 deg rad ∏_{A∈S} A if #S = 5.

Proof. Define d = max{deg A : A ∈ S} and e = deg rad ∏_{A∈S} A. By Theorem 2.2,

d > 2 deg h − deg rad A − deg rad B − deg rad C
+ deg rad gcd{A, B} + deg rad gcd{A, C} + deg rad gcd{B, C}

for any distinct A, B, C ∈ S. Average this inequality over all choices of A, B, C to see that d > 2 deg h − 3 avg_{A} deg rad A + 3 avg_{A≠B} deg rad gcd{A, B}. On the other hand, e ≥ #S avg_{A} deg rad A − \binom{#S}{2} avg_{A≠B} deg rad gcd\{A, B\} by inclusionexclusion, so

d + \frac{3}{#S} e > 2 deg h − \frac{3#S − 9}{2} avg_{A≠B} deg rad gcd\{A, B\}.

Note that 3#S − 9 ≥ 0 since #S ≥ 3.

One can bound each term deg rad gcd{A, B} by the simple observation that A/gcd{A, B} and B/gcd{A, B} are distinct congruent polynomials of degree at most d − deg gcd{A, B}; thus d − deg gcd{A, B} ≥ deg h, so deg rad gcd{A, B} ≤ d − deg h. Hence

d + \frac{3}{#S} e > 2 deg h − \frac{3#S − 9}{2}(d − deg h);

i.e., d > ((3#S − 5)/(3#S − 7)) deg h − (6/(3#S − 7)#S)e. □

3. Appendix: the ABC theorem

Theorem 3.1 is a typical statement of the Stothers-Mason ABC theorem, included in this paper for completeness. The proof given here is due to Noah Snyder; see [2].

Theorem 3.1. Let k be a field. Let A, B, C be nonzero elements of the polynomial ring k[x] with A + B + C = 0 and gcd{A, B, C} = 1. If deg A ≥ deg rad ABC then A′ = 0.

In fact, A′ = B′ = C′ = 0. As usual, X′ means the derivative of X; the relevance of derivatives is that X/rad X divides X′.

Proof. Note that gcd{A, B} = gcd{A, B, −(A + B)} = gcd{A, B, C} = 1. By the same argument, gcd{A, C} = 1 and gcd{B, C} = 1.

C/rad C divides both C and C′, so it divides C′B − CB′. Similarly, B/rad B divides C′B −CB′. Furthermore, C′ = −(A′ +B′), so C′B −CB′ = −(A′ +B′)B + (A + B)B′ = AB′ − A′B; thus A/rad A divides C′B − CB′.

The ratios A/rad A, B/rad B, C/rad C are pairwise coprime, so their product ABC/rad ABC divides C′B − CB′. But by hypothesis deg(ABC/rad ABC) = deg ABC − deg rad ABC ≥ deg BC > deg(C′B − CB′); so C′B − CB′ = 0; so AB′ − A′B = 0; so A divides A′B; but A and B are coprime, so A divides A′; but deg A > deg A′, so A′ = 0. □

References

[1] Daniel J. Bernstein, Proving primality in essentially quartic random time. Available from

    http://cr.yp.to/papers.html.

[2] Noah Snyder, An alternate proof of Mason’s theorem, Elemente der Mathematik 55 (2000), 93–94. ISSN 0013–6018. MR 2001g:11033. Available from http://www.springerlink.

    com/openurl.asp?genre=article&issn=0013-6018&volume=55&issue=3&spage=93.

[3] José Felipe Voloch, On some subgroups of the multiplicative group of finite rings. Available

    from http://www.ma.utexas.edu/users/voloch/preprint.html.

Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, IL 60607–7045

E-mail address: djb@cr.yp.to