These notes concern Agrawal's conjecture, the first problem in the problem session:
Conjecture. Let and be two coprime positive integers. If
(If Agrawal's conjecture were true, this would improve the polynomial time complexity of the AKS primality testing algorithm from to .)
The contents are due to Lenstra and Pomerance and suggest strongly that this conjecture is false.
Proposition. [Lenstra] Let be pairwise distinct prime integers, and let . Suppose that:
Remark. This result is also true for .
We also have the following identity:
It therefore suffices to prove that each prime satisfies
It remains to check the residue class of modulo ; more precisely, it suffices to show that
By this proposition, we have a heuristic which suggests the existence of many counterexamples to the Agrawal conjecture. This argument taken from analytic number theory is very similar to the one already used by Pomerance to find counterexamples to the Baillie-PSW primality testing algorithm which can be found at http://www.pseudoprime.com/dopo.pdf.
Fix some arbitrarily large integer and let be very large. Let denote the set of primes in the interval such that:
Also choose an odd integer such that . We consider the squarefree numbers that run over products of distinct primes of the set . Obviously such an integer satisfies . The number of choices for is exactly given by the binomial coefficient , and we get the lower bound:
Let denote the product of primes with , and let denote the product of primes with . Then and are coprime and asymptotically the product equals as , so that for some large . Thus, the number of choices for the numbers that satisfy in addition and should be asymptotically
But any such is a counterexample to Agrawal's conjecture by Lenstra's proposition. We see therefore that for fixed and for all large , there should be at least counterexamples to Agrawal's conjecture below . That is, if we let , this argument implies that the number of counterexamples is expected to be for any .
Back to the main index for Future directions in algorithmic number theory.