Agrawal's conjecture

In number theory, Agrawal's conjecture, due to Manindra Agrawal in 2002,{{cite journal |first=Manindra |last=Agrawal |first2=Neeraj |last2=Kayal |first3=Nitin |last3=Saxena |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |title=PRIMES is in P |journal=Annals of Mathematics |volume=160 |year=2004 |issue=2 |pages=781–793 |doi=10.4007/annals.2004.160.781 |jstor=3597229 |doi-access=free }} 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\mathord\left(\log^{6} n\right)$ to $\tilde O\mathord\left(\log^3 n\right)$ .

Truth or falsehood

The conjecture was formulated by Rajat Bhattacharjee and Prashant Pandey in their 2001 thesis.{{cite journal|author=Rajat Bhattacharjee, Prashant Pandey|date=April 2001|url=https://cs.stanford.edu/people/rajatb/primality.ps.gz |title=Primality Testing|journal=Technical Report|publisher=IIT Kanpur}} It has been computationally verified for $r < 100$ and $n < 10^{10}$ ,{{cite journal|author=Neeraj Kayal, Nitin Saxena|year=2002|title=Towards a deterministic polynomial-time Primality Test|journal=Technical Report|publisher=IIT Kanpur|citeseerx=10.1.1.16.9281}} and for $r = 5, n < 10^{11}$ .{{cite web|url=https://www.cse.iitk.ac.in/users/nitin/talks/Dec2014-3Paris.pdf|title=Primality & Prime Number Generation|last=Saxena|first=Nitin|date=Dec 2014|publisher=UPMC Paris|accessdate=24 April 2018|archive-url=https://web.archive.org/web/20180425032115/https://www.cse.iitk.ac.in/users/nitin/talks/Dec2014-3Paris.pdf|archive-date=25 April 2018|url-status=dead}}

However, a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there are infinitely many counterexamples.{{cite web|last=Lenstra|first=H. W.|first2=Carl|last2=Pomerance|date=2003|title=Remarks on Agrawal's conjecture.|url=http://www.aimath.org/WWN/primesinp/primesinp.pdf|publisher=American Institute of Mathematics|accessdate=16 October 2013}} 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, Roman B. Popovych conjectures a modified version 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}$ .

{{citation|url=https://eprint.iacr.org/2009/008.pdf |title=A note on Agrawal conjecture |first=Roman |last=Popovych|date=30 December 2008|accessdate=21 April 2018}}

Distributed computing

Both Agrawal's conjecture and Popovych's conjecture were tested by distributed computing project Primaboinca which ran from 2010 to 2020, based on BOINC. The project found no counterexample, searching in $10^{10} < n < 10^{17}$ .

Notes

External links

[http://www.primaboinca.com/ Primaboinca project]

Category:Conjectures about prime numbers