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

Edit : La primera versión de esta respuesta proponía un criterio basado en la complejidad de Kolmogorov, pero como Scott Aaronson comentó, esto no es muy restrictivo ya que todos los primos tienen una complejidad bastante baja: la primalidad no es muy difícil de diseñar una prueba ineficiente para, el n'º primo $p_n$ tiene una complejidad máxima de $\log n \approx \log\log p_n$ . Parece que lo que yo tenía en mente era más o menos lo que él escribió en su respuesta.

Sin embargo, me parece que la cuestión de la complejidad es parte de lo que hace que la pregunta sea interesante: debería esperarse que los números extremadamente grandes tuvieran una complejidad extremadamente grande, y es la disparidad entre la baja complejidad de alguna descripción corta como C(5) y la alta complejidad de la propia cadena de dígitos de C(5) lo que hace que la descripción parezca no ser concreta. En términos más generales, se puede dudar de la conocibilidad de los números extremadamente grandes basándose en que no se pueden escribir explícitamente, como se indica en la pregunta.

Así que, contrariamente a la afirmación de que C(5) no es una descripción concreta de un número, creo que debido a su baja complejidad es mucho más concreto de lo que su tamaño podría sugerir, y sus dígitos de base 2 se enumeran fácilmente; la mayoría de los números de su magnitud son totalmente abstractos y sus dígitos en cualquier base nunca se conocerán. De hecho, no estoy del todo seguro de que un algoritmo de enumeración de primos que calcule C(5) en tiempo polinómico en C(4) (su número de dígitos binarios), como sugiere Scott, sea en realidad especialmente concreto, a menos que tome una entrada significativamente menor que C(5) (nótese que C(5) es aproximadamente el primo C(5)'th).

Es decir, un cálculo puede ser eficiente sin ser hormigón . En el espíritu de la respuesta de Alastair Litterick, me gustaría sugerir que

Un algoritmo para enumerar (alguna familia infinita de) primos que sea eficiente en el sentido de la respuesta de Scott también es "concreto" si la longitud de su salida es superpolinómica en la longitud de su entrada.

En términos más generales, supongo que tendría sentido cuantificar cuánto mayor es la salida, a efectos de sondear primos muy distantes.

---

Puesto que la pregunta se declara filosófica, yo también tengo algunas ideas filosóficas sobre su significado. Estas no abordan la cuestión de la misma manera que las anteriores.

Creo que la palabra "conocido" debe tomarse con un grano de sal incluso en el caso del actual récord del primo más grande, aunque estuviera expresado en dígitos de base-10. Buscar primos de tamaño récord es una actividad ajena a las matemáticas, igual que la búsqueda de planetas extrasolares por parte de los astrónomos es ajena a la geología, aunque si alguna vez fuéramos a uno, podríamos estudiarlo geológicamente. Con una prueba en la mano de que hay infinitos primos, encontrar uno en particular sólo es útil si necesitamos números específicos para alguna tarea, como la criptografía, cuya ejecución ni siquiera es una cuestión de informática una vez implementada. Esto no quiere decir que la construcción de una búsqueda de primos no sea una cuestión tanto de matemáticas como de informática: por ejemplo, probar los primos de Mersenne es una estrategia extraída de las matemáticas, ya que es pas se sabe que hay infinitas, y hacer las pruebas de forma eficiente es informática. Sin embargo, ejecutar la búsqueda con éxito no es ni lo uno ni lo otro.

En cambio, para conocer un primo, o cualquier cosa, es necesario poder responder a preguntas sobre él; mejor aún, las preguntas no deben tener respuestas generales conocidas. Por ejemplo, "¿el último dígito es 3?" es una buena pregunta, pero sólo pregunta por el residuo módulo 10, y el teorema de Dirichlet ya describe estadísticamente la respuesta a esa pregunta. Se podría tener curiosidad por el sesgo de Chebyshev (qué clase de residuo tiene más números primos hasta un cierto tamaño), pero eso no se puede resolver de una manera u otra mirando ejemplos individuales. Por otra parte, ni siquiera 2 se entiende del todo como un primo, ya que no podemos decir en qué módulo de primos es una raíz primitiva (implícitamente, por ejemplo, "los que son 5 mod 7"). Ésta, al igual que los primos de Mersenne, es otra lista que no se sabe si es infinita.

Aparte de las conjeturas sobre números primos individuales que pueden comprobarse en números concretos, existen conjeturas estadísticas, similares en su naturaleza al teorema de Dirichlet, que no están resueltas y que tampoco pueden resolverse mediante una búsqueda de números primos dispersos. Por ejemplo, uno podría querer saber si un primo concreto $p_n$ comienza un hueco primo máximo (mayor que cualquier hueco anterior), para el que el único cómputo posible es de un exhaustivo lista de primos hasta $p_{n + 1}$ .

Supongamos, sin embargo, que tuviéramos un algoritmo para generar una lista de todos primos, en orden, dando todos los primos de n dígitos en tiempo polinómico demostrable. Seguimos sin poder verificar la hipótesis de Riemann en la forma que $$\lvert \pi(x) - \operatorname{Li}(x) \rvert = O(x^{1/2} \log x)$$ a menos que tuviéramos una comprensión mucho más profunda de la comportamiento de ese algoritmo. Sin saber esto, no sería razonable decir que los números primos son "conocidos" como conjunto. Y no creo que sea un listón demasiado alto decir que si todos los números primos son "conocidos", entonces los números primos son conocidos como conjunto.

En resumen, no creo que una mera lista de primos, finita o infinita, pueda constituir un conocimiento de sus elementos.