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

Dado que se trata de una wiki comunitaria, no me sentiré tan mal por no ofrecer respuestas concretas, sino más bien un punto de vista abstracto que podría sugerir otra vía de búsqueda.

Para mí, el tema básico se conoce con el nombre de "campos de Hardy": campos de gérmenes de funciones de valor real en el infinito. Uno de los ejemplos básicos es el campo de gérmenes de todas las funciones que se pueden construir a partir de polinomios, exponenciales y logaritmos, y que se cierran con las cuatro operaciones aritméticas y la composición.

Un hecho maravilloso es la ley de la tricotomía: que tales "funciones log-exp" son o bien eventualmente positivas, o bien eventualmente cero, o bien eventualmente negativas. Tal vez esto se parezca a los supuestos de monotonicidad que Qiaochu mencionó antes. Garantiza que los gérmenes en el infinito de tales funciones forman efectivamente un campo $K$ . Dentro del campo hay un anillo de valoración formado por gérmenes de funciones acotadas, $O$ . Existe una valoración correspondiente en $K$ cuyo grupo de valores es $K^\ast/O^\ast$ .

Los elementos de $K^\ast/O^\ast$ pueden denominarse "tasas de crecimiento". En efecto, dos gérmenes de funciones $[f]$ , $[g]$ son equivalentes mod $O^\ast$ si ambos $f/g$ y $g/f$ son acotadas, es decir, son asintóticas (hasta una constante) -- recuérdese que por tricotomía, estas funciones acotadas no oscilan sino que tienden a un límite definido.

Desde este punto de vista, nos interesan los campos Hardy que surgen de forma natural cuyos grupos de valores contienen estrictamente al grupo de valores de la clase log-exp mencionada anteriormente (de modo que obtenemos "tasas intermedias de crecimiento").

La razón por la que menciono todo esto es que creo que existe una literatura bastante amplia sobre construcciones de campos de Hardy (con la que, por desgracia, no estoy muy familiarizado). Un área de investigación es la teoría de modelos y, en particular, las estructuras o-minimales, donde la o-minimalidad garantiza la ley de la tricotomía antes mencionada. Hay expertos por ahí (por ejemplo, David Marker, si está escuchando) que podrían darnos ejemplos "naturales" de estructuras o-minimales con tales tasas intermedias de crecimiento en el infinito. A mí también me interesaría.

Edita: Y ahora que he escrito esto, ¡recuerdo que hay teoremas en la teoría de la estructura o-minimal que tienden a descartar tales tasas intermedias de crecimiento! Eso en sí mismo sería interesante, y de todos modos quizá alguien como David Marker conozca algunos ejemplos interesantes, de la teoría de la estructura o-minimal o no.

Answer 2

Varias funciones aritméticas no tienen un equivalente en términos de función elemental, sino que sólo tienen un equivalente "en la media". Por ejemplo $d(n)$ el número de divisores de $n$ es bastante irregular, pero satisface $$\frac1n(d(1)+\cdots+d(n))\sim\log n.$$ Asimismo, la suma $\sigma(n)$ de divisores de $n$ es irregular (aunque un poco menos que $d(n)$ ) pero satisface $$\frac1n(\sigma(1)+\cdots+\sigma(n))\sim\frac{\pi^2n}{12}.$$ Por último, el orden medio del indicador de Euler $\phi(n)$ es $\frac{3n}{\pi^2}$ .

Answer 3

Secuencias Davenport-Schinzel están relacionados con la complejidad de las disposiciones de diversas formas geométricas (por ejemplo, envolventes de segmentos de línea). Su asintótica se describe en términos de la función inversa de Ackermann.

Answer 4

En Números de campana tienen asintótica relacionada con la función W de Lambert.

EDIT: Hoy he estado curioseando en mathworld, y he encontrado que el Puntos Gram también tienen asintótica relacionada con la función W.

Answer 5

Consideremos la función escalera de Cantor $f:\ [0,1]\rightarrow [0,1]$ y la función de momento $F(x):=\int_0^1 (f(t))^x dt$ . En $x$ tiende a $+\infty$ se comporta como $x^{-\sigma}$ , $\sigma:=\ln 3/\ln 2$ . Pero el límite $F(x)\cdot x^{\sigma}$ no existe: este valor oscila muy lentamente en torno a una constante $1.9967\dots$

Más información en ruso aquí: http://www.math.spbu.ru/analysis/f-doska/lap_can.pdf