Ejemplos de secuencias cuya asíntota no puede describirse mediante funciones elementales

Question

Para mí es un poco milagroso que incluso secuencias muy complicadas $a_n$ que surgen en diversas áreas de las matemáticas tienen la propiedad de que existe una función elemental $f(n)$ tal que $a_n = \Theta(f(n))$ o, incluso mejor, $a_n \sim f(n)$ . Por ejemplo

• Aproximación de Stirling $n! \sim \sqrt{2\pi n} \left( \frac{n}{e} \right)^n$ (y sus diversas implicaciones),
• La asintótica de la función de partición $p_n \sim \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$ ,
• Teorema de los números primos $\pi(n) \sim \frac{n}{\log n}$ ,
• La asintótica de los números de Ramsey no diagonales $R(3, n) = \Theta \left( \frac{n^2}{\log n} \right)$ .

Ejemplos de secuencias $a_n$ que se dan "en la naturaleza" y que es demostrable que no tienen esta propiedad (ya sea en su versión débil o fuerte)? Preferiblemente ejemplos más sencillos.

(Supongo que debería mencionar que no me interesan las secuencias que no tienen esta propiedad por razones de computabilidad, por ejemplo, la función del castor ocupado. Me interesan más, por ejemplo, ejemplos naturales de secuencias con crecimiento asintótico "semiexponencial").

Answer 1

Algunos algoritmos tienen un tiempo de ejecución que implica $\log^* n$ el número de iteraciones de $\log$ antes de que el resultado sea como máximo $1$ . Se trata esencialmente de la inversa de la base de tetración $e$ . Por ejemplo, el algoritmo Fredman-Tarjan para encontrar un árbol de expansión de peso mínimo tiene un tiempo de ejecución $E ~\log^* V$ y el algoritmo aleatorio de Clarkson et al. para triangular un polígono simple con $n$ vértices tiene un tiempo de ejecución previsto $n ~\log^* n$ . (En ambos casos, existen algoritmos asintóticamente más rápidos de Bernard Chazelle).

Answer 2

Supongamos que F es un campo de característica finita y que u,v,w están en A=F[x,y]. Sea a_n la dimensión del espacio vectorial A/(u^n,v^n,w^n). Supongamos que a_1 es >0 y finito. Entonces, a medida que n crece (a_n)/(n^2), aunque acotado por encima y acotado lejos de 0 generalmente tiene un comportamiento oscilante "tipo fractal".

Answer 3

Exponenciales iterados $\exp^{[n]}(x)$ crecen más rápido que cualquier función elemental. Es posible construir muchas funciones que crecen aún más rápido.