Cuestión filosófica relacionada con Los mayores primos conocidos

Question

El otro día, hablando de matemáticas y, en concreto, de números primos, me vino a la cabeza la siguiente pregunta y se me ocurrió plantearla aquí para ver qué opinaba la gente al respecto.

Pregunta principal: Supongamos que mañana alguien demuestra que alguna función siempre genera primos (concretos) para cualquier entrada. ¿Cómo afectaría esto a listas como la Primas más grandes conocidas ?

Permítanme dar un poco más de detalle para demostrar por qué creo que esta cuestión no es del todo trivial o fantasiosa.

En primer lugar, el requisito de que la función sea capaz de generar primos concretos pretende evitar ejemplos "estúpidos" como Nextprime(n) que, dado un "mayor primo conocido" P, da como resultado un primo mayor Nextprime(P). Nótese, sin embargo, que la definición de Nextprime no indica explícitamente cuál es este primo, cualquier implementación de la misma (en Maple o Mathematica, por ejemplo) simplemente realiza un bucle a través de los enteros mayores que la entrada, comprobando la primalidad de cada uno de ellos de alguna manera.

Por otra parte, un candidato para tal función podría ser la secuencia catalana definida por:

$C(0) = 2$ , $C(n+1) = 2^{C(n)}-1$

Aunque $C(5) = 2^{170141183460469231731687303715884105727}-1$ es demasiado grande para probarla con los métodos actuales (con unos $10^{30}$ veces más dígitos que el mayor primo conocido actualmente), y aunque el consenso actual es que $C(5)$ es probablemente compuesto, no parece totalmente fuera del ámbito de la posibilidad de que alguien podría encontrar alguna manera muy inteligente de mostrar $C(5)$ es primo, o incluso que $C(n)$ es siempre primo, o quizás alguna otra secuencia definida concretamente.

La cuestión es la siguiente: una vez que se sabe que cada elemento de una secuencia es primo, ¿se niegan por completo cosas como la lista de los mayores primos conocidos? ¿O el hecho de que $C(n)$ para $n\geq 5$ ¿Tiene demasiados dígitos como para poder calcularlos todos (en lugar de eso, sólo se pueden calcular los primeros o los últimos dígitos), lo que significa que, aunque se demostrara de algún modo que son primos, técnicamente no serían "conocidos"?

Obsérvese también que en el ámbito de los grupos simples finitos la cuestión análoga ya es difícil de decidir, puesto que se conocen infinitas familias de tales grupos, pero las descripciones concretas (como generadores y relaciones o tablas de caracteres) no siempre están disponibles o ni siquiera son computables dentro de límites de tiempo razonables. Del mismo modo, se podrían plantear cuestiones análogas en otras ramas (variedades de mayor volumen con ciertas restricciones, etc.).

En cualquier caso, parece una pregunta razonable para que la consideren matemáticos serios, así que sólo quiero saber qué opinan los demás sobre el tema (y si a alguien se le ocurre un título mejor, que no dude en sugerirlo).

Answer 1

En primer lugar, no creo que la idea de que "conocer un primo requiere conocer su expansión decimal" concuerde bien con la práctica matemática. Si no me equivoco, los mayores primos conocidos son todos primos de Mersenne, y (¡por una buena razón!) casi siempre se escriben de la forma p=2 k -1, no por sus expansiones decimales. Por supuesto, los Mersennes conocidos actualmente son lo suficientemente pequeños como para que uno podría calcular sus expansiones decimales en Maple o Mathematica, si por alguna razón uno quisiera hacerlo. Pero incluso si ese no fuera el caso (digamos, si k tuviera 10.000 dígitos), seguiría siendo perfectamente feliz describiendo p=2 k -1 como "primo conocido", siempre que alguien conociera tanto k como una prueba de que p era primo.

Por otra parte, de forma similar a lo que sugirió con su función "NextPrime", ¿qué le parece

p := los 10 10^10000 ¿el número primo?

Ciertamente, p existe, e incluso se puede escribir un programa para obtenerlo. Pero, ¿es p "conocido"? Afirmarlo parece estirar el significado de la palabra "conocido" hasta hacerlo irreconocible.

Intentando llegar a algún criterio de principio que separe los dos ejemplos anteriores, esto es lo mejor que se me ha ocurrido:

Un número primo p de n dígitos es "conocido" si existe un algoritmo conocido para obtener los dígitos de p que se ejecuta en tiempo poli(n) (junto con una prueba de que el algoritmo obtiene efectivamente un número primo y se detiene en pasos poli(n)).

(En sentido estricto, la definición anterior abarca la "conoscibilidad" de familias infinitas de números primos, y no de números primos individuales, ya que una vez fijado p, siempre se puede obtener en tiempo O(1). Pero se trata de una advertencia estándar).

Por lo que veo, la definición anterior capta correctamente la intuición de que un primo p es "conocido" si conocemos una fórmula de forma cerrada para p (que puede evaluarse en tiempo polinómico), pero pas si nos limitamos a conocer una definición no constructiva de p (para la que se necesita un tiempo exponencial para determinar de qué p estamos hablando).

Un caso de prueba muy interesante para mi definición es

p := el primer primo mayor que 10 10^10000 .

Según mi definición, el primo anterior es actualmente "desconocido", pero se convertirá en "conocido" si alguien demuestra la conjetura de que el espacio entre dos primos consecutivos de n dígitos nunca supera q(n) para algún polinomio q fijo.

Si aceptas mi definición, entonces una "función que siempre genera primos" casi con toda seguridad sería trivializar los concursos de números primos más grandes, ya que presumiblemente daría una forma determinista de generar números primos de n dígitos en n O(1) tiempo, para n tan grande como se quiera (que no es algo que tengamos actualmente).

Ahora bien, puede que haya casos en los que mi definición no coincida con la "conocibilidad intuitiva"; si es así, ¡espero ver contraejemplos!

Answer 2

Creo que está malinterpretando el propósito de la lista de "mayores primos". Hay áreas de las matemáticas en las que realmente no sabemos cómo generar o catalogar los objetos de determinados tipos. Los números primos no entran en esta categoría.

Más bien, estas listas existen básicamente como punto de referencia para los algoritmos informáticos de teoría numérica. Por ejemplo, si se desarrolla un nuevo superordenador, se puede probar su destreza comprobando la primalidad de algunos números más grandes que no están en la lista.

Answer 3

No creo que en principio pueda trazarse una línea divisoria entre primos "conocidos" como $2^{43112609}-1$ (el récord actual), y por otro "desconocidos" pero bien definidos, como el primer primo mayor que un número dado.

Como ya se ha señalado, el primo récord actual sigue siendo lo bastante pequeño como para contarlo como conocido según la ingenua idea de que conocemos su representación decimal. Tiene unos pocos millones de dígitos, y encontrarlos requiere poco tiempo informático adicional en comparación con probar la primalidad en primer lugar.

Si esta situación cambia debido a nuevos métodos para comprobar la primalidad de números enormes (digamos, cuyos dígitos ni siquiera pueden almacenarse en toda la memoria informática del mundo), supongo que volveremos a recurrir a una noción intuitiva de cuándo un número es conocido.

Será difícil llegar a una definición clara de lo conocido en términos de complejidad computacional, ya que se puede encontrar una $n$ en tiempo polinómico (aunque no de forma determinista demostrable) y, naturalmente, los primos récord estarán en el rango en el que el grado (o incluso la constante) del polinomio es crucial.

Especulando sobre el futuro desarrollo de la teoría de números y las pruebas de primalidad, creo que el consenso es que si $C(5)$ se demuestra primo mañana, pasará a encabezar la lista, mientras que si alguien establece que $C(n)$ es primo para cada $n$ la conclusión será que se conocen explícitamente infinitos primos.

Otra posibilidad es mejorar la prueba de primalidad de los números generales. Si se pudiera comprobar la primalidad de números arbitrarios con la misma eficacia que la de los números de Mersenne, es posible que los nuevos récords mundiales de primos consistieran en extravagantes patrones de dígitos, aderezados con codificaciones secretas de humor friki.

En principio, la situación es diferente en el caso de los primos gemelos récord. El récord actual es $65516468355\cdot 2^{333333}\pm 1$ y, por lo que tengo entendido, no se sabe rigurosamente si existen primos gemelos más grandes. Si alguien demostrara con algún tipo de criba que un intervalo de números mayores debe contener un par de primos gemelos, entonces supongo que la lista de primos gemelos récord se dividiría en pares conocidos "explícitamente" y "teóricamente".

Answer 4

Creo que el descubrimiento de un algoritmo generador de primos simplemente dividiría el estudio en una "lista de los mayores primos conocidos no generados por el algoritmo X" y "primos generados por el algoritmo X", de forma muy parecida a la clasificación de los grupos simples finitos.

Siguiendo esto hasta su conclusión lógica, incluso si supiéramos de forma demostrable cada algoritmo generador $n$ -en poly( $n$ )-tiempo, aún nos quedaría la pregunta de qué primos no eran generados por una de estas funciones, lo que da lugar a un concepto de primo "esporádico", y serían éstos los que interesarían.

Answer 5

Siempre he entendido que "los mayores primos conocidos" se refiere coloquialmente a los primos que (i) tienen expansiones decimales que se pueden escribir en poco tiempo y (ii) tienen pruebas de primalidad que han sido doble/triplemente comprobadas.

Imagino que si se demostrara que la secuencia que sugieres es siempre primo, la gente dejaría de hablar de los mayores primos conocidos. Seguirían buscando formas de encontrar muchos números primos del mismo tamaño y de mejorar el límite de ese tamaño.