Jump to content

Agrawal's conjecture

From Wikipedia, the free encyclopedia

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]