Agrawal's conjecture

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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]

Agrawal's conjecture has been computationally verified for and ; 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 for any .

Assuming Agrawal's conjecture is false by the above argument, a modified version (the Agrawal–Popovych conjecture[3]) may still be true:

Let and be two coprime positive integers. If

and

then either is prime or .

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. ^ 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)