La conjetura de Agrawal

En teoría de números , la conjetura de Agrawal , debida a Manindra Agrawal en 2002, ^{[ 1 ]} constituye la base de la prueba AKS ciclotómica . La conjetura de Agrawal establece formalmente:

Dejar${\displaystyle n}$y${\displaystyle r}$sean dos enteros positivos coprimos . Si

${\displaystyle (X-1)^{n}\equiv X^{n}-1{\pmod {n,\,X^{r}-1}}\,}$

entonces o${\displaystyle n}$es primo o${\displaystyle n^{2}\equiv 1{\pmod {r}}}$

Si la conjetura de Agrawal fuera cierta, disminuiría la complejidad temporal de la prueba de primalidad AKS de${\displaystyle {\tilde {O}}{\mathord {\left(\log ^{6}n\right)}}}$a${\displaystyle {\tilde {O}}{\mathord {\left(\log ^{3}n\right)}}}$.

La conjetura fue formulada por Rajat Bhattacharjee y Prashant Pandey en su tesis de 2001. ^{[ 2 ]} Ha sido verificada computacionalmente para${\displaystyle r<100}$y${\displaystyle n<10^{10}}$, ^{[ 3 ]} y para${\displaystyle r=5,n<10^{11}}$. ^{[ 4 ]}

Sin embargo, un argumento heurístico de Carl Pomerance y Hendrik W. Lenstra sugiere que existen infinitos contraejemplos. ^{[ 5 ]} En particular, la heurística muestra que tales contraejemplos tienen una densidad asintótica mayor que${\displaystyle {\tfrac {1}{n^{\varepsilon }}}}$para cualquier${\displaystyle \varepsilon >0}$.

Suponiendo que la conjetura de Agrawal sea falsa según el argumento anterior, Roman B. Popovych conjetura que una versión modificada aún podría ser cierta:

Dejar${\displaystyle n}$y${\displaystyle r}$sean dos enteros positivos coprimos. Si

${\displaystyle (X-1)^{n}\equiv X^{n}-1{\pmod {n,\,X^{r}-1}}}$

y

${\displaystyle (X+2)^{n}\equiv X^{n}+2{\pmod {n,\,X^{r}-1}}}$

entonces o${\displaystyle n}$es primo o${\displaystyle n^{2}\equiv 1{\pmod {r}}}$. ^{[ 6 ]}

Tanto la conjetura de Agrawal como la de Popovych fueron probadas por el proyecto de computación distribuida Primaboinca, que se desarrolló entre 2010 y 2020, basado en BOINC . El proyecto no encontró ningún contraejemplo, buscando en${\displaystyle 10^{10}<n<10^{17}}$.

• Proyecto Primaboinca