# 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 $n$ and $r$ be two coprime positive integers. If

$(X-1)^n \equiv X^n - 1 \pmod{n, X^r - 1} \,$

then either $n$ is prime or $n^2 \equiv 1 \pmod r$

## Ramifications

If Agrawal's conjecture were true, it would decrease the runtime complexity of the AKS primality test from $\tilde O((\log n)^6)$ to $\tilde O((\log n)^3)$.

## Truth or falsehood

Agrawal's conjecture has been computationally verified for $r < 100$ and $n < 10^{10}$, 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 $\tfrac{1}{n^{\varepsilon}}$ for any $\varepsilon > 0$.

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

Let $n$ and $r$ be two coprime positive integers. If

$(X-1)^n \equiv X^n - 1 \pmod{n, X^r - 1}$

and

$(X+2)^n \equiv X^n + 2 \pmod{n, X^r - 1}$

then either $n$ is prime or $n^2 \equiv 1 \pmod{r}$.

## Notes

1. ^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P". Annals of Mathematics 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229.
2. ^ Lenstra, H. W.; Pomerance, Carl. "Remarks on Agrawal’s conjecture.". American Institute of Mathematics. Retrieved 16 October 2013.
3. ^ Popovych, Roman, A note on Agrawal conjecture