3 votos

Asintótica de la función divisora

Intento entender el post de Tao del 23 de septiembre de 2008 dado aquí sobre el límite del divisor.

Mis problemas son cuando utiliza la notación big-O para demostrar lo que enumera como límite (4) $$ d(n) \leq \exp(O(\frac{\log n}{\log\log n})). $$

En primer lugar, tras demostrar que $$ d(n) \leq O(\frac{1}{\epsilon})^{\exp (1/\epsilon)} $$ declara que $$ O(\frac{1}{\epsilon})^{\exp(1/\epsilon)}=\exp(\exp(O(1/\epsilon))). $$ No sé cómo ver esto. Un poco más tarde utiliza lo anterior para escribir $$ d(n)\leq\exp(\exp(O(1/\epsilon)))n^\epsilon. $$ Conectamos $C/\log\log n$ y declara que el segundo término del lado derecho domina, lo que puede verse tomando logaritmos. Yo tampoco lo veo. Cualquier idea sería muy apreciada. Gracias.

2voto

Gudmundur Orn Puntos 853

Veámoslos uno por uno.

  1. Queremos demostrar que $$ O\left(\frac{1}{\epsilon}\right)^{\exp(1/\epsilon)}=\exp(\exp(O(1/\epsilon))). $$

    Para facilitar la notación, dejo de lado la mayoría de los $O(\cdot)$ constantes. A continuación, observe que $$ \left( \frac{1}{e} \right) ^{ \exp(1/\epsilon) } = e^{\log(1/\epsilon)\cdot \exp(1/\epsilon)}$$

    y en general, $\log x \cdot e^x = O(e^{x +\delta})$ para cualquier $\delta > 0$ . Así, $$ \left( \frac{1}{e} \right) ^{ \exp(1/\epsilon) } = e^{\log(1/\epsilon)\cdot \exp(1/\epsilon)} = \exp (\, \exp ( \, O (1/\epsilon )\, )\, )$$

  2. Sigamos su sugerencia. Así pues, establezcamos $\epsilon = C/\log\log n$ para algunos grandes $C$ . Entonces queremos comparar el crecimiento de $\exp ( \exp ( O(1/\epsilon)))$ y $n^\epsilon$ . Vuelvo a dejar caer la mayoría $O(\cdot)$ constantes para facilitar. La primera:

    $$ \exp( \exp ( 1/\epsilon)) = \exp ( \exp ( \log \log n / C) ) = \exp \exp (\log (\log n)^{1/C} ) = \exp ( (\log n)^{1/C}).$$

    El segundo se queda:

    $$ n^{C/\log \log n}$$

    Ahora toma los registros. Luego comparamos

    $$ (\log n)^{1/C} \quad \text{and} \quad \frac{C}{\log \log n} \log n$$

    Similar al hecho anterior, $\frac{x}{\log x} > x^{1 - \delta}$ para cualquier $\delta > 0$ . Por lo tanto, para los grandes $C$ La parte izquierda es como una pequeña potencia (mucho menos que $1$ , digamos) de $\log n$ y el lado derecho es como una potencia mayor (bastante cerca de $1$ ) de $\log n$ .

Así que esa es una forma de obtener sus dos resultados. $\diamondsuit$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X