¿Hay una prueba de complejidad de Kolmogorov del teorema del número primo?

Question

Lance Fortnow utiliza la complejidad de Kolmorogov para probar un Teorema de Números Casi Primarios ( https://lance.fortnow.com/papers/files/kaikoura.pdf después del teorema $2.1$ ): el $i$ El primo es a lo sumo $i( \log i)^2$ . Esto difiere del límite del Teorema de los Números Primarios sólo por un factor de $ \log i$ .

1. ¿Hay alguna manera de afilar esta prueba a un límite de $O(i \log i)$ haciendo un buen uso de la teoría de la complejidad (Matt. El comentario F da un pequeño $O(( \log\log i)^2)$ factor)?

añadió : Si 1. no es posible, ¿qué información adicional necesitamos para llegar al Teorema de los Números Primarios?

La única limitación parece ser la creatividad necesaria en los códigos libres de prefijos. Tal vez haya una codificación asintóticamente eficiente o algún otro razonamiento que se necesite.

2. ¿Hay una conexión entre los códigos sin prefijos y la teoría de los números multiplicativos? Ambos tratan de caracterizar la representación única de alguna manera.

Answer 1

En primer lugar, la prueba dada allí no muestra realmente que $p_n = O(n( \log n)^2)$ (al menos no sin más esfuerzo). En cambio, lo que muestra es que hay $n$ para el cual $p_n = O(n( \log n)^2)$ y con un pequeño esfuerzo que esto supone para los arbitrariamente grandes $n$ . Como se ha señalado en los comentarios, el argumento también da que hay $n$ con $p_n = O(n ( \log n) ( \log \log n)^2)$ etc.

De hecho, todo lo que sucede en esta prueba es que la suma de los recíprocos de los primos divergen, lo que también da inmediatamente que debe haber grandes $n$ con $p_n \le n ( \log n)^2$ etc. (si no, la suma de los recíprocos convergería). Así que permítanme reformular esta ``nueva prueba'' en un lenguaje más usual: la prueba es bonita, pero no hay realmente ninguna idea nueva aquí, sólo un lenguaje menos familiar (que es interesante y sugerente).

Considere los números enteros $n$ debajo de $x$ (que es grande), y clasificarlos de acuerdo a su mayor factor principal $p=P(n)$ . Si $z$ es cualquier número fijo, entonces hay como mucho $( \log x)^z$ los números de abajo $x$ todos cuyos factores principales son menores que $z$ . Por lo tanto $$ x \le ( \log x)^z + \sum_ { \substack { n \le x \\ P(n) >z}} 1 \le ( \log x)^z + \sum_ {p>z } \frac {x}{p}, $$ ya que hay a lo sumo $x/p$ números enteros abajo $x$ cuyo mayor factor principal es $p$ . Esto demuestra que para cualquier $z$ $$ \sum_ {p> z} \frac 1p >1, $$ que equivale a la divergencia de la suma de los recíprocos de los primos. Este es el contenido de la prueba en las notas vinculadas.

Hay un hecho que encuentro intrigante. El argumento de la complejidad de cómo concatenar ``programas'' dado allí parece encajar exactamente con cómo una secuencia debe crecer para tener una suma divergente (que $1/n( \log n)^2$ converge, $1/(n( \log n)( \log \log n)^2)$ converge, etc ¡Curioso!

Answer 2

Creo que no es raro que los argumentos de la teoría elemental de números sean "filosóficamente" teóricos de la información. Pero no se trata de un hecho muy profundo: al fin y al cabo, todo se reduce al conocido principio heurístico de que los sucesos de que un "entero aleatorio" sea divisible por diferentes primos son sucesos aproximadamente independientes. Precisar esa noción heurística es lo que siempre requiere argumentos mucho más sutiles que implican análisis complejos, etc., en los que el pensamiento teórico de la información no desempeña ningún papel aparente. Así que estoy razonablemente seguro de que la respuesta a la pregunta del título sobre el teorema de los números primos es "no".

No obstante, se pueden hacer cosas muy bonitas con esta idea. He aquí un ejemplo que descubrí hace muchos años, relacionado con la estimación estándar $$ \textrm{(*)} \qquad \sum_{p \le n} \frac{\log p}{p} = \log(n) + O(1) \qquad (n\to \infty) $$ (suma sobre primos) - una serie que está muy relacionada con la suma de los recíprocos de los primos y con las estimaciones de $p_n$ que usted y otros discutían aquí. Voy a dar (*) la siguiente interpretación teórica de la información (que dará una prueba rigurosa de un límite en una dirección):

Tomemos una variable aleatoria $X$ que se elige uniformemente al azar entre los números $1,\ldots,n$ . Para cada primo $p\le n$ , dejemos que $V_p$ sea el $p$ -valoración de X (el exponente de $p$ dividiendo $X$ ). Una observación clave es que conocer todos los $V_p$ se puede recuperar $X$ . Esto significa que existe una desigualdad de entropías de Shannon: $$ \log_2(n) = H(X) \le H(\{V_p, p\le n\}) \le \sum_{p\le n} H(V_p), $$ por propiedades bien conocidas de la función entropía $H(\cdot)$ (subaditividad y monotonicidad con respecto a la $\sigma$ -precisamente análogas a las propiedades de la complejidad de Kolmogorov que Fortnow utiliza en sus notas).

Ahora, ¿cuál es la entropía $H(V_p)$ de la variable aleatoria $V_p$ ? Es la expresión $$ - \sum_{k\ge 0} \operatorname{Pr}(V_p=k) \log \operatorname{Pr}(V_p=k), $$ que puede limitarse desde arriba por la $k=1$ plazo $$ -\operatorname{Pr}(V_p=1) \log \operatorname{Pr}(V_p=1) = -\left( \frac{1}{n} \lfloor n/p \rfloor \right) \log \left( \frac{1}{n} \lfloor n/p \rfloor \right), $$ más todas las demás partes (que dejaré como ejercicio para mostrar es $O(1)$ ). Y esta última cantidad es aproximadamente igual a $\frac{\log p}{p}$ mientras $p$ es menor en orden de magnitud que $n$ . Así, tras algunas estimaciones más sencillas, se obtiene esencialmente el " $\ge$ "de (*), junto con la idea añadida de que el término de error en aproximaciones como (*) dice algo sobre hasta qué punto las propiedades de divisibilidad de un número típico por diferentes primos están correlacionadas entre sí.

Como decía al principio, esto es interesante a nivel filosófico, pero no sé si alguien ha encontrado la manera de hacer que este tipo de argumentos sean lo suficientemente precisos como para demostrar algo tan sólido como el teorema de los números primos, o incluso algo más sólido que las estimaciones más elementales que ya tienen pruebas muy cortas y directas.