Densidad de números que tienen grandes divisores primos (formalización del argumento heurístico de probabilidad)

Question

Quiero demostrar que el conjunto de los números naturales n que tenga un divisor primo mayor que $\sqrt{n}$ es positivo.

Tengo un argumento heurístico que esta densidad debe ser $\log 2$ que es aproximadamente 0,7, pero no estoy seguro de cómo se podría convertir esto en un argumento formal.

Para cualquier x la probabilidad de que x es primo es aproximadamente $1/ \log x$ (Por el teorema de los números primos). Además, la probabilidad de que n es múltiplo de x es aproximadamente $1/x$ . Son "independientes", por lo que la probabilidad de que n es múltiplo de x y x es primo es aproximadamente $1/x\log x$ .

Sabemos que n puede tener como máximo un divisor primo mayor que $\sqrt{n}$ por lo que la probabilidad de que n tiene un divisor primo mayor que $\sqrt{n}$ puede aproximarse mediante la integral:

$$\int_{\sqrt{n}}^n \frac{dx}{x \log x} = [\log (\log x)]_{\sqrt{n}}^n = \log 2$$

¿Puede precisarse en términos de densidades? ¿Cómo se tratarían los términos de error? ¿Se ha demostrado ya este resultado u otro similar?

AÑADIDO MÁS TARDE: Las pruebas que siguen resuelven esta cuestión, y también parecen demostrar que la densidad de números n con un divisor primo mayor que $n^\alpha$ es $-\log \alpha$ para $1 > \alpha \ge 1/2$ . Mi pregunta: ¿el resultado también es válido para $0 < \alpha < 1/2$ ? Para tales $\alpha$ Podríamos tener más de un divisor primo, por lo que el simple recuento anterior no funciona; necesitamos utilizar un tamiz que reste las contribuciones múltiples que se producen a partir de números que tienen más de un divisor primo de este tipo. Supongo que, asintóticamente, esto no importaría, pero no estoy seguro de cómo demostrarlo formalmente.

Answer 1

En realidad, esto es bastante sencillo, y se reduce a que

$ \sum_{p \text{prime}} \frac 1p = \log \log x + C + o(1)$

para alguna constante $C$ . Para ver cómo aplicar esto al problema original, dejemos que $p$ denota el mayor divisor primo de $n$ y escribe $n = pz$ . Entonces $p \ge \sqrt{n}$ sólo si $z \le p$ . Por lo tanto, el número de tales $n \le x$ es

$\sum_{p \le x} \sum_{z \le \min(p,x/p)} 1$ que se divide en un término principal

$\sum_{p \ge \sqrt{x}} \lfloor \frac xp \rfloor$ más un plazo menor $\sum_{p \le \sqrt{x}} p \le \sqrt{x} \pi(\sqrt x) = o(x)$ que, por tanto, es despreciable en comparación con el primer término. Del término principal se encarga la ecuación que he citado al principio, utilizando el hecho de que $\pi(n) = o(n)$ y finalmente que

$\log \log x - \log \log \sqrt x = \log 2$ .

Answer 2

Si recuerdo correctamente, este fue un ejercicio de Matemáticas para el Análisis de Algoritmos. No tengo acceso a una biblioteca ahora mismo, así que no puedo comprobar eso.

En cualquier caso, aquí es una prueba. Fijar un entero positivo $N$. Vamos a contar el número de $n$ $\{ 1,2, \ldots, N \}$ tales que el mayor divisor primo de $n$$\leq \sqrt{n}$.

Podemos romper este recuento en dos partes: (1) Los $n$ que son divisibles por $p$ donde $p \leq \sqrt{N}$ $n \leq p^2$ y (2) Los $n$ que son divisibles por $p > \sqrt{n}$.

Caso (1) es más fácil. Estamos buscando a $\sum_{p \leq \sqrt{N}} p = \int_{t=0}^{\sqrt{N}} t d \pi(t)$. (Esta es una de Riemann-Stieltjes integral.) La integración por partes, esto es $\int_{0}^{\sqrt{N}} \pi(u) du + O( \sqrt{N} \ \pi(\sqrt{N}))$. Desde $\pi(u) = O(u / \log u)$$u \to \infty$, esta integral es $O \left( \int^{\sqrt{N}} \pi(u) du \right) = O\left(\sqrt{N} \frac{\sqrt{N}}{\log N} \right) = O(N/\log N)$, y el segundo término también es $O(N/\log N)$. Para el caso 1 contribuye densidad cero.

Caso (2) es la misma idea de integrar por partes y utilizar el teorema de los números primos—, pero los detalles son messier porque necesitamos una mejor obligado.

Estamos tratando de calcular $$\sum_{\sqrt{N} \leq p \leq N} \lfloor \frac{N}{p} \rfloor = \int_{\sqrt{N}}^N \lfloor \frac{N}{t} \rfloor d\pi(t) = \int_{\sqrt{N}}^N \left( \frac{N}{t} + O(1) \right) d\pi(t).$$

El término de error es:$O(\pi(N)) = N/\log N$, por lo que, de nuevo, no efecto de la densidad. Integrar el término principal por partes, tenemos $$\int_{\sqrt{N}}^N \left( \frac{\partial}{\partial t} \ \frac{N}{t} \right) \pi(t) dt +O(N/\log N).$$ Donde el término de error es:$\left( N/t \pi(t) \right)|^N_{\sqrt{N}}$.

Ahora, $\pi(t) = Li(t) + O(t/(\log t)^K)$ cualquier $K$, por el teorema de los números primos, donde $Li(t) = \int^t du/\log u$. Por tanto, el primer término es $$\int_{\sqrt{N}}^N \left( \frac{\partial}{\partial t} \ \frac{N}{t} \right) Li(t) dt + O\left( \int^N \frac{N}{t^2} \frac{t}{(\log t)^K} dt \right).$$ El término de error es:$O \left( N/(\log N)^{K-1} \right)$.

En el término principal, integrar por partes, "invertir" nuestro anterior integración por partes. Tenemos $$\int_{\sqrt{N}}^N \frac{N}{t} \frac{dt}{\log t} + O(N/\log N).$$

Centrándose en el término principal, una vez más, hemos $$N \int_{\sqrt{N}}^N \frac{dt}{t \log t} = N \log 2.$$

Poner todos nuestros términos de error juntos, el número de enteros con grandes factores primos es $$N \log 2 + O(N/\log N).$$

---

En resumen, integración por partes, el Primer Número Teorema, agresivo y la poda de los términos de error.

Como recuerdo, el ejercicio de seguimiento de las Matemáticas en el Análisis de Algoritmos es la obtención de una fórmula de la forma $$N \log 2 + c N/\log N + O(N/(\log N)^2).$$ Eso es un duro ejercicio! Si quieres aprender mucho acerca de la forma asintótica de la técnica, se los recomiendo.

Answer 3

Como sospechabas, cuando el mayor factor primo de $n$ es menor que $\sqrt{n}$ entonces las cosas se complican. Sin embargo, se han hecho muchas cosas al respecto. Uno de los más interesantes está en http://www.google.com/url?sa=t&source=web&ct=res&cd=2&ved=0CA0QFjAB&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.108.7037%26rep%3Drep1%26type%3Dpdf&ei=HW1wS5qVKoze8Qbis7H8BQ&usg=AFQjCNGtuzzG1YhO-6m_ySNG3iw1RX-0ig&sig2=OftdPThF1PkbArX_-1cDRw

por Donnelly y Grimmet.

Esto también conduce al estudio de los números "suaves": un número entero es y-suave, si todos sus factores primos son $\le y$ . Un buen estudio al respecto se encuentra en http://www.dms.umontreal.ca/~andrew/PDF/msrire.pdf

Answer 4

El número esperado de divisores primos mayores que $n^{\alpha}$ es, de hecho, $-\log \alpha$ . Para $\alpha \ge 1/2$ esto se reduce a la probabilidad de tener un divisor grande, ya que $n$ no puede tener dos divisores mayores que $n^{1/2}$ . Para $1/3 < \alpha < 1/2$ la situación es más complicada, ya que hay que considerar la probabilidad de que haya dos "grandes" (mayores que $n^\alpha$ ) divisores; para $1/4 < \alpha < 1/3$ incluso podría haber tres divisores grandes, etc.

Existe una analogía entre la estructura cíclica de las permutaciones y las factorizaciones primos de los números enteros; en particular, tu afirmación de que el número esperado de divisores primos de $n$ superior a $n^{\alpha}$ es $-\log \alpha$ es equivalente a la afirmación de que el número esperado de ciclos de una permutación sobre $n$ elementos más largos que $\alpha n$ es $-\log \alpha$ . Véase el preprint de Andrew Granville La anatomía de los números enteros y las permutaciones .

Teniendo esto en cuenta, he escrito una parte del argumento de tamizado análogo para permutaciones en un preprint, Número de ciclos de longitud normalizada especificada en permutaciones (arXiv:0909.2909). No estoy seguro de si se ha escrito para factorizaciones primos -- la literatura es un poco borrosa en mi mente -- pero hay una buena probabilidad de que haya sido.

Answer 5

Su pregunta "añadido más tarde" puede responderse leyendo estos dos Artículos de Wikipedia. Los números enteros que te interesan se llaman comúnmente "números lisos". En realidad estás contando los enteros no lisos, pero eso es un cambio trivial.