What is the current status of Agrawal's conjecture?

Question

In their famous 'Primes is in P' paper Agrawal, Kayal and Saxena stated the following conjecture:

If for coprime integers $n$ and $r$ the equality $(X-1)^n = X^n - 1$ holds in $\mathbb{Z}_n[X]/(X^r-1)$ then either $n$ is prime or $n^2 = 1 \pmod{r}$.

If true this would give a beautiful characterization of primes that could be easily transformed into a fast ($O(\log^{3+\epsilon}{n})$) and deterministic primality test.

Shortly after publishing 'Primes is in P' Hendrik Lenstra noticed that the conjecture may not be valid for $r=5$ and $n$ of the very special form (see Lenstra's and Pomerance's note, p.30). It was unknown whether any such $n$ existed but Carl Pomerance gave a heuristic argument convincing that there should be infinitely many $n$'s sharing these, apparently rare, properties. I'm not aware of any strict proof for this.

It may also happen that the conjecture in a modified form (if we restrict $r$ to be greater than $\log{n}$) can be still true.

Martin Mačaj (see Some remarks and questions about the AKS algorithm and related conjecture) gave another version of this conjecture together with a proof that relied on yet another unsolved problem.

Does anyone know if there were any advances in this area in the recent years?

Answer 1

I had some students look at this problem during an REU. A group proved that the conjecture is true if $r > n/2$, that's not too hard and can certainly be improved. Another group tried to find a counterexample using the computer for $r=5$, without success. I agree with Lenstra and Pomerance that the conjecture should be false in general.

Link to REU page: http://www.ma.utexas.edu/users/voloch/reu.html

Answer 2

I found a paper here: http://eprint.iacr.org/2009/008.pdf which generalizes a result from Lenstra's and Pomerance's paper.

The paper is "A note on Agrawal conjecture" by Roman Popovych.

Here is the abstract:

We prove that Lenstra proposition suggesting existence of many counterexamples to Agrawal conjecture is true in a more general case. At the same time we obtain a strictly ascending chain of subgroups of the group (Zp[X]/(Cr(X)))* and state the modified conjecture that the set {X-1, X+2} generate big enough subgroup of this group.

Here is the url for a paper from a student scientific conference containing some numerical results:

http://www.fmph.uniba.sk/fileadmin/user_upload/editors/studium/svk/2009/INF/vana.pdf.

Answer 3

About primaboinca

PRIMABOINCA is a research project that uses Internet-connected computers to search for a counterexample to some conjectures. This project concerns itself with two hypotheses in number theory. Both are conjectures for the identification of prime numbers. The first conjecture (Agrawal’s Conjecture) was the basis for the formulation of the first deterministic prime test algorithm in polynomial time (AKS algorithm). Hendrik Lenstras and Carl Pomerances heuristic for this conjecture suggests that there must be an infinite number of counterexamples. So far, however, no counterexamples are known. This hypothesis was tested for n < 1010 without having found a counterexample. The second conjecture (Popovych’s conjecture) adds a further condition to Agrawals conjecture and therefore logically strengthens the conjecture. If this hypothesis would be correct, the time of a deterministic prime test could be reduced from O(log N)6 (currently most efficient version of the AKS algorithm) to O(log N)3.

You can participate by downloading and running a free program on your computer.

http://www.primaboinca.com/