# Remarks on Agrawal's Conjecture

These notes concern Agrawal's conjecture, the first problem in the problem session:

Conjecture. Let and be two coprime positive integers. If

then either is prime or

(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:

1. ;
2. for all ;
3. for all ; and
4. for all .
Then

and .

Remark. This result is also true for .

Proof. By assumption we get because . So and then .

We also have the following identity:

in the polynomial ring . Hence, in order to prove the identity

it suffices to prove that

The Chinese remainder theorem gives the following isomorphism:

Each ring factor is actually a field since each prime is prime to and the th cyclotomic polynomial is irreducible in so that is nothing but the splitting field of for a primitive th root of unity .

It therefore suffices to prove that each prime satisfies

in the field . We see from (ii) that

(since , we have ). Thus

Hence the order of in divides .

It remains to check the residue class of modulo ; more precisely, it suffices to show that

We can factor into pairwise coprime factors:

so it suffices to verify this modulo each factor. Since by assumption, the first follows. Assumption (iii) implies that

and so

since , and

similarly. This completes the proof.

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:

1. ;
2. is squarefree and divisible only by primes with ;
3. is squarefree and divisible only by primes with .
Both smoothness conditions (2) and (3) are rather restrictive: heuristically, the cardinality of the set is asymptotically ( )

for some positive constant that depends on the choice of . In particular, we can take a sufficiently large integer such that

which we assume from now on.

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:

for large and fixed .

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.