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

then either is prime or

Ramifications

edit

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

Truth or falsehood

edit

The conjecture was formulated by Rajat Bhattacharjee and Prashant Pandey in their 2001 thesis.[2] It has been computationally verified for   and  ,[3] and for  .[4]

However, a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there are infinitely many counterexamples.[5] 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, Roman B. Popovych conjectures a modified version may still be true:

Let   and   be two coprime positive integers. If

 

and

 

then either   is prime or  .[6]

Distributed computing

edit

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  .

Notes

edit
  1. ^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229.
  2. ^ Rajat Bhattacharjee, Prashant Pandey (April 2001). "Primality Testing". Technical Report. IIT Kanpur.
  3. ^ Neeraj Kayal, Nitin Saxena (2002). "Towards a deterministic polynomial-time Primality Test". Technical Report. IIT Kanpur. CiteSeerX 10.1.1.16.9281.
  4. ^ Saxena, Nitin (Dec 2014). "Primality & Prime Number Generation" (PDF). UPMC Paris. Archived from the original (PDF) on 25 April 2018. Retrieved 24 April 2018.
  5. ^ Lenstra, H. W.; Pomerance, Carl (2003). "Remarks on Agrawal's conjecture" (PDF). American Institute of Mathematics. Retrieved 16 October 2013.
  6. ^ Popovych, Roman (30 December 2008), A note on Agrawal conjecture (PDF), retrieved 21 April 2018
edit