La conjetura de Agrawal

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

Sean y dos números enteros positivos coprimos . Si ${\displaystyle n}$ ${\displaystyle r}$

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

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

Ramificaciones

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

Verdad o falsedad

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

Sin embargo, un argumento heurístico de Carl Pomerance y Hendrik W. Lenstra sugiere que hay infinitos contraejemplos. ^[5] En particular, la heurística muestra que tales contraejemplos tienen una densidad asintótica mayor que cualquier otro . ${\displaystyle {\tfrac {1}{n^{\varepsilon }}}}$ ${\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 puede ser cierta:

Sean y dos números enteros coprimos positivos. Si ${\displaystyle n}$ ${\displaystyle r}$

${\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 cualquiera es primo o . ^[6] ${\displaystyle n}$ ${\displaystyle n^{2}\equiv 1{\pmod {r}}}$

Computación distribuída

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

Notas

1. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES está en P" (PDF) . Anales de Matemáticas . 160 (2): 781–793. doi : 10.4007/anales.2004.160.781 . JSTOR  3597229.
2. Rajat Bhattacharjee, Prashant Pandey (abril de 2001). "Prueba de primalidad". Reporte técnico . IIT Kanpur .
3. Neeraj Kayal, Nitin Saxena (2002). "Hacia una prueba de primalidad determinista en tiempo polinómico". Reporte técnico . IIT Kanpur. CiteSeerX 10.1.1.16.9281 . 
4. Saxena, Nitin (diciembre de 2014). "Primalidad y generación de números primos" (PDF) . UPMC París. Archivado desde el original (PDF) el 25 de abril de 2018 . Consultado el 24 de abril de 2018 .
5. Lenstra, HW; Pomerancia, Carl (2003). "Observaciones sobre la conjetura de Agrawal" (PDF) . Instituto Americano de Matemáticas . Consultado el 16 de octubre de 2013 .
6. Popovych, Roman (30 de diciembre de 2008), Una nota sobre la conjetura de Agrawal (PDF) , consultado el 21 de abril de 2018

enlaces externos

• proyecto primaboinca