Agrawal's conjecture

Lore & Background

Agrawal's conjecture states that for coprime positive integers n and r, if (X-1)^n ≡ X^n - 1 (mod n, X^r - 1), then either n is prime or n^2 ≡ 1 (mod r). The conjecture was formulated by Manindra Agrawal in 2002. It has been computationally verified for r < 100 and n < 10^10, and for r = 5, n < 10^11.

Reader's Guide

Agrawal's conjecture is significant because its truth would reduce the runtime complexity of the AKS primality test from O~(log^6 n) to O~(log^3 n), a substantial improvement. However, a heuristic argument by Carl Pomerance and Hendrik W. Lenstra suggests there are infinitely many counterexamples, with asymptotic density greater than 1/n^ε for any ε > 0. Assuming the conjecture is false, Roman B. Popovych proposed a modified version adding a second congruence condition. The distributed computing project Primaboinca (2010–2020) tested both conjectures for n between 10^10 and 10^17 and found no counterexample, leaving the status of the original conjecture unresolved.

Did You Know?

• A heuristic by Pomerance and Lenstra suggests infinitely many counterexamples exist.
• The Primaboinca project searched n from 10^10 to 10^17 and found no counterexample.

The Statement and Its Origins

In the landscape of number theory, Agrawal's conjecture occupies a distinctive position as a proposed bridge between polynomial congruences and primality. Attributed to Manindra Agrawal in 2002, the conjecture underpins what is known as the cyclotomic AKS test. Its formal content is deceptively compact: given two coprime positive integers n and r, if the polynomial congruence (X−1)^n ≡ X^n − 1 holds modulo the pair (n, X^r − 1), then n must either be prime or satisfy the condition n² ≡ 1 (mod r). The idea traces back to a 2001 thesis by Rajat Bhattacharjee and Prashant Pandey, who first formulated the statement before it entered wider circulation under Agrawal's name. What makes the conjecture compelling is that it encodes a deep arithmetic constraint—linking a single polynomial identity to the fundamental question of whether a number is prime—while leaving a narrow exception for the case where n² reduces to 1 modulo r.

The Promise for Primality Testing

The most tantalizing consequence of Agrawal's conjecture lies in its potential to reshape computational number theory. The AKS primality test, a landmark deterministic algorithm, currently operates with a runtime complexity of Õ(log⁶ n). Should the conjecture prove true, the cyclotomic variant it enables would slash that bound dramatically to Õ(log³ n), effectively halving the exponent on the logarithmic factor. This is not a marginal improvement; in the context of algorithms whose cost scales as a power of log n, reducing the exponent from six to three represents a qualitative leap in efficiency. For cryptographic applications and large-scale number-theoretic computations where primality must be certified without probabilistic shortcuts, such a reduction could translate into orders-of-magnitude speedups for very large inputs. The conjecture thus sits at the intersection of pure algebraic number theory and practical algorithm design, offering a clean polynomial-congruence criterion that, if valid, would make deterministic primality testing significantly more accessible.

Evidence, Heuristics, and the Question of Truth

The status of Agrawal's conjecture remains unresolved, with evidence pulling in opposite directions. On the affirmative side, extensive computational verification has confirmed the statement for all r below 100 and n below 10 to the tenth power, and additionally for the specific case r = 5 with n extending to 10 to the eleventh power. These checks provide substantial empirical support. On the other hand, a heuristic argument developed by Carl Pomerance and Hendrik W. Lenstra points toward the conjecture being false, suggesting that infinitely many counterexamples exist. Their analysis indicates these counterexamples are not merely rare anomalies but possess an asymptotic density exceeding 1/n^ε for every positive ε, meaning they appear with non-negligible frequency as n grows. In response to this tension, Roman B. Popovych proposed a strengthened version of the conjecture that adds a second polynomial congruence—(X+2)^n ≡ X^n + 2 modulo (n, X^r − 1)—hoping the extra condition eliminates the suspected counterexamples while preserving the primality conclusion.

The Primaboinca Distributed Search

The quest for a definitive answer to Agrawal's conjecture has attracted the power of volunteer computing. The Primaboinca project, built on the BOINC distributed computing platform, operated from 2010 through 2020 and dedicated its resources to hunting for counterexamples to both the original Agrawal statement and Popovych's modified variant. Over its decade of operation, the project systematically searched the range from 10 to the tenth power up to 10 to the seventeenth power for values of n that might violate the conjecture. Despite this enormous computational sweep—spanning seven orders of magnitude in n—no counterexample was identified. The absence of a refutation in such a vast interval lends further credibility to the conjecture in its tested domain, yet it does not constitute a proof. The Primaboinca effort stands as a notable example of how distributed computing can push the boundaries of empirical verification in pure mathematics, extending the frontier of confirmed cases far beyond what any single institution could achieve.