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

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

then either ${\displaystyle n}$ is prime or ${\displaystyle 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 ${\displaystyle {\tilde {O}}(\log ^{6}n)}$ to ${\displaystyle {\tilde {O}}(\log ^{3}n)}$.

## Truth or falsehood

Agrawal's conjecture has been computationally verified for ${\displaystyle r<100}$ and ${\displaystyle n<10^{10}}$; however, a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there are infinitely many counterexamples.[2] In particular, the heuristic shows that such counterexamples have asymptotic density greater than ${\displaystyle {\tfrac {1}{n^{\varepsilon }}}}$ for any ${\displaystyle \varepsilon >0}$.

Assuming Agrawal's conjecture is false by the above argument, Popovych conjectures a modified version may still be true:

Let ${\displaystyle n}$ and ${\displaystyle r}$ be two coprime positive integers. If

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

and

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

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

## Notes

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