¿Cuál es la situación actual de la conjetura de Agrawal?

Question

En su famoso artículo "Primes is in P", Agrawal, Kayal y Saxena plantearon la siguiente conjetura:

Si para los enteros coprimos $n$ y $r$ la igualdad $(X-1)^n = X^n - 1$ tiene en $\mathbb{Z}_n[X]/(X^r-1)$ entonces $n$ es primo o $n^2 = 1 \pmod{r}$ .

De ser cierto, esto daría una hermosa caracterización de los primos que podría ser fácilmente transformada en un rápido ( $O(\log^{3+\epsilon}{n})$ ) y la prueba de primalidad determinista.

Poco después de publicar 'Primes is in P', Hendrik Lenstra se dio cuenta de que la conjetura podría no ser válida para $r=5$ y $n$ de la forma muy especial (véase Nota de Lenstra y Pomerance , p.30). Se desconocía si alguno de estos $n$ existía, pero Carl Pomerance dio un argumento heurístico que convence de que debe haber infinitas $n$ que comparten estas propiedades, aparentemente raras. No conozco ninguna prueba estricta de esto.

También puede ocurrir que la conjetura en una forma modificada (si restringimos $r$ sea mayor que $\log{n}$ ) puede seguir siendo cierto.

Martin Mačaj (véase Algunas observaciones y preguntas sobre el algoritmo AKS y la conjetura relacionada ) dio otra versión de esta conjetura junto con una prueba que se basaba en otro problema no resuelto.

¿Alguien sabe si hubo algún avance en esta área en los últimos años?

Answer 1

Hice que algunos estudiantes estudiaran este problema durante una URE. Un grupo demostró que la conjetura es verdadera si $r > n/2$ No es demasiado difícil y, sin duda, se puede mejorar. Otro grupo trató de encontrar un contraejemplo utilizando el ordenador para $r=5$ , sin éxito. Estoy de acuerdo con Lenstra y Pomerance en que la conjetura debe ser falsa en general.

Enlace a la página de la URE: http://www.ma.utexas.edu/users/voloch/reu.html

Answer 2

He encontrado un documento aquí: http://eprint.iacr.org/2009/008.pdf que generaliza un resultado del trabajo de Lenstra y Pomerance.

El artículo es "A note on Agrawal conjecture" de Roman Popovych.

Este es el resumen:

Demostramos que la proposición de Lenstra que sugiere la existencia de muchos contraejemplos a la conjetura de Agrawal es cierta en un caso más general. Al mismo tiempo obtenemos una cadena estrictamente ascendente de subgrupos del grupo (Zp[X]/(Cr(X)))* y afirmamos la conjetura modificada de que el conjunto {X-1, X+2} genera un subgrupo suficientemente grande de este grupo.

Aquí está la url de un artículo de una conferencia científica de estudiantes que contiene algunos resultados numéricos:

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

Answer 3

Sobre primaboinca

PRIMABOINCA es un proyecto de investigación que utiliza ordenadores conectados a Internet para buscar un contraejemplo a algunas conjeturas. Este proyecto se ocupa de dos hipótesis de la teoría de los números. Ambas son conjeturas para la identificación de los números primos. La primera conjetura (la conjetura de Agrawal) fue la base para la formulación del primer algoritmo determinista de prueba de números primos en tiempo polinómico (algoritmo AKS). La heurística de Hendrik Lenstras y Carl Pomerances para esta conjetura sugiere que debe haber un número infinito de contraejemplos. Sin embargo, hasta ahora no se conocen contraejemplos. Esta hipótesis fue probada para n < 1010 sin haber encontrado un contraejemplo. La segunda conjetura (conjetura de Popovych) añade una condición más a la conjetura de Agrawals y, por tanto, refuerza lógicamente la conjetura. Si esta hipótesis fuera correcta, el tiempo de una prueba determinista de primos podría reducirse de O(log N)6 (la versión más eficiente actualmente del algoritmo AKS) a O(log N)3.

Puede participar descargando y ejecutando un programa gratuito en su ordenador.

http://www.primaboinca.com/