¿Cuál es el límite inferior más sencillo de las funciones de recuento de primos?

Question

Estoy tratando de entender cómo puede existir un límite inferior en la función de recuento de primos, y para comenzar este proceso de educación estoy tratando de encontrar una prueba completa simple, que no dependa de otra teoría más compleja?

Answer 1

En realidad, no entiendo en absoluto por qué el límite clásico de Chebyshev se considera tan difícil. La prueba consta de cuatro pasos elementales:

1) $A_n={2n \choose n}=\frac{(2n)!}{n!^2}$ es un número entero cuya factorización incluye sólo primos $p\le 2n$ . Además, este número es bastante grande: ya que $\frac{n+k}{k}\ge 2$ para todos $1\le k\le n$ tenemos $A_n\ge 2^n$ .

2) La potencia de un primo $p$ en $m!$ es igual a $\left[\frac mp\right]+\left[\frac m{p^2}\right]+\dots+\left[\frac m{p^k}\right]$ donde $p^k\le m< p^{k+1}$ .

3) Por lo tanto, la potencia de cualquier primo $p$ en $A_n$ es igual a $\sum_{j=1}^{k_p}\left(\left[\frac {2n}{p^j}\right]-2\left[\frac n{p^j}\right]\right)\le k_p$ , donde $p^{k_p}\le 2n< p^{k_p+1}$ (utilizamos aquí la observación trivial de que $[2x]-2[x]\le 1$ para todos $x$ ).

4) Así pues, $2^n\le A_n\le \prod_{p\le 2n}p^{k_p}\le (2n)^{\pi(2n)}$ de donde $$ \pi(2n)\ge \frac{n\log 2}{\log(2n)} $$ dándole el orden de magnitud correcto a costa de, como mucho, media hora de estudios.

Answer 2

He aquí un límite inferior muy fácil de demostrar:

Consideremos el producto de todos los primos menores que $n$ Llámalo $P_n$ . Sea el mayor primo menor que $n$ sea $q_n$ . Debe haber un primo en $[q_n+1, P_n+1]$ (esto se debe a que $P_n+1$ debe ser a su vez primo o divisible por algún otro primo, pero no es divisible por ningún primo menor o igual que $q_n$ ). Claramente, $P_n+1\leq n!$ para $n>2,n\in\mathbb{N}$

Dado que $\pi(3)=2$ vemos que $\pi(3!)=\pi(6)\geq2+1=3$ entonces $\pi(6!)\geq4$

En general $\pi(3\underbrace{!!...!!}_{n})\geq n+1$

La interpolación es fácil, dejemos que $\pi(n)=\pi(k)$ para $k=\sup\{3\underbrace{!!...!!}_{m}|3\underbrace{!!...!!}_{m}\leq n\}$

Answer 3

Hay un simple límite inferior debido a Erdős que he detallado en otra respuesta. La integridad, la voy a volver a publicar el argumento como una respuesta aquí.

Deje $n\in\mathbb{N}=\{1,2,3,\ldots\}.$ Considerar el conjunto $$S(n) = \{(k,l)\in\mathbb{N}^{2}:l\text{ is square-free and }k^{2}l\leq n\}.$$ It is a standard fact that every natural number has a unique representation in the form $k^{2}l,$ where $k$ and $l$ are natural numbers and $l$ is square-free. This gives $\lvert S(n)\rvert = n.$

Ahora si tenemos un par de $(k,l)$$k^{2}l\leq n,$, entonces debemos tener $k^{2}\leq n$$l\leq n$, ya que el $k$ $l$ son positivos. Tenga en cuenta que esto da $k\leq\sqrt{n}.$ Desde $l$ es cuadrado-libre, $l$ se puede expresar como un producto de distintos números primos, cada uno de los cuales debe ser no mayor que $n$ desde $l\leq n$. Es decir, $l$ se puede expresar como un producto de los números primos $p_{1},p_{2},\ldots,p_{\pi(n)}.$ Hay $2^{\pi(n)}$ dichos productos.

Por lo tanto, si conocemos $(k,l)\in S(n)$, a continuación, existen en la mayoría de las $\sqrt{n}$ posibilidades de lo $k$ podría ser y en la mayoría de las $2^{\pi(n)}$ posibilidades de lo $l$ podría ser (independiente de $k$, por supuesto). De ello se desprende que $\lvert S(n)\rvert \leq 2^{\pi(n)}\sqrt{n},$ $n\leq2^{\pi(n)}\sqrt{n}.$

Tomando $\log$s y reorganizar nos da el siguiente resultado: $$\pi(n)\geq\frac{\log{n}}{2\log{2}}\quad\text{for }n=1,2,\ldots.$$

Answer 4

Según el postulado de Bertrand (pruebas de que se puede encontrar aquí), si $n\geq 2$, entonces no es una de las principales entre el $n$ $2n$ (no incluidas $n$). Por lo tanto, en general, $\pi(2x) \geq \pi(x)+1$. Desde $\pi(2)=1$,$\pi(4)\geq 1+1=2, \pi(8)\geq 2+1=3$, y, en general, $\pi(2^n)\geq n \implies \pi(x) \geq \log_2(x)$ (desde $\pi$ es creciente). Este límite inferior es de ninguna manera óptima, pero es sencillo y admite un relativamente simple prueba.

Answer 5

Dado $k$ primos $p_1,\ldots,p_k$, nos vamos a calcular el número de productos de estos números primos por debajo de un cierto umbral de $2^n$. Es decir, pregunte cuántas decisiones de los exponentes $a_i\in \mathbb N$ satisfacer: $$p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}\leq 2^n.$$ Ya que cada prime es, al menos,$2$, obtenemos que esta declaración implica $$2^{a_1+a_2+\ldots+a_k}\leq 2^n$$ $$a_1+a_2+\ldots+a_k\leq n.$$ Una de las estrellas y las barras de argumento establece que el número de tuplas $(a_1,\ldots,a_k)$ satisfacer este es ${n+k\choose n}$. Hay $2^n$ enteros en el intervalo de $[1,2^n]$, y cada uno puede escribir como un producto de números primos menos de $2^n$. Por lo tanto, debemos tener, establecimiento $k=\pi(2^n)$: $${n+\pi(2^n)\choose n}\geq 2^n.$$ Eso es bastante sencilla prueba.

---

Bueno, vamos a hacer la dolorosa bits de mostrar que este es un logarítmica obligado. Esto es, lamentablemente, el uso de más difícil herramientas que se requieren para obtener el obligado en primer lugar. Básicamente se reduce a averiguar que hay algunos $\alpha$ de manera tal que el mínimo de $\pi(2^n)\geq \alpha n$ de las grandes suficientemente $n$. Para ello, tenga en cuenta el valor $${(\alpha+1)n \choose n}=\frac{((\alpha+1)n)!}{n!(\alpha n)!}$$ where we slightly abuse notation in assuming the relevant terms are integers. Since we're going to use an asymptotic approximation, this does not really matter. Using Stirling's approximation that $n!\sim \sqrt{2\pi n}(n/e)^n$ en cada factorial da $${(\alpha+1)n \choose n}\sim \frac{1}{\sqrt{2\pi n}}\cdot \frac{\sqrt{\alpha+1}}{\sqrt{\alpha}}\cdot \frac{((\alpha+1)n/e)^{(\alpha+1)n}}{(n/e)^n(\alpha n/e)^{\alpha n}}=\frac{1}{\sqrt{2\pi n}}\cdot \frac{\sqrt{\alpha+1}}{\sqrt{\alpha}}\cdot \left(\frac{(\alpha+1)^{\alpha+1}}{\alpha^{\alpha}}\right)^n$$ Lo que debe quedar claro es que esta función es, finalmente, delimitada por $\frac{(\alpha+1)^{\alpha+1}}{\alpha^{\alpha}}$, lo que significa que la expresión debe ser al menos dos. Numéricamente, esto da $\alpha\geq .2938\ldots$. Por la mínima posible $\alpha$ dado por esta desigualdad, obtendríamos $$\pi(2^n)\geq \alpha n$$ por lo suficientemente grande como $n$. Esto es suficiente para establecer un logarítmica límite inferior en el primer función de conteo.