# Agrawal's conjecture

In number theory, **Agrawal's conjecture**, due to Manindra Agrawal in 2002,^{[1]} forms the basis for the cyclotomic AKS test. Agrawal's conjecture states formally:

Let and be two coprime positive integers. If

## Ramifications

If Agrawal's conjecture were true, it would decrease the runtime complexity of the AKS primality test from to .

## Truth or falsehood

Agrawal's conjecture has been computationally verified for and ,
however a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there is an infinite number of counterexamples.^{[2]} In particular, the heuristic shows that such counterexamples have asymptotic density greater than for any .

Assuming Agrawal's conjecture is false by the above argument, a modified version (the Agrawal–Popovych conjecture^{[3]}) may still be true:

Let and be two coprime positive integers. If

and

## Notes

- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Cite web
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}