Sharper ABC-based bounds for congruent polynomials

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 radABC 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 radABC. The second improvement generalizes to m ?? 3 polynomials A1, . . . ,Am of degree at most ((3m - 5)/(3m - 7)) deg h - (6/(3m - 7)m) deg radA1 · · ·Am.