# 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}}\,}$

## Ramifications

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

## 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 is an infinite number of counterexamples.[2] In particular, the heuristic shows that such counterexamples have asymptotic density greater than ${\displaystyle {\tfrac {1}{n^{\epsilon }}}}$ for any ${\displaystyle \epsilon >0}$.

Assuming Agrawal's conjecture is false by the above argument, a modified version (the Agrawal–Popovych conjecture[3]) 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}}}$

## Notes

1. {{#invoke:Citation/CS1|citation |CitationClass=journal }}
2. Template:Cite web
3. {{#invoke:citation/CS1|citation |CitationClass=citation }}