Una cosa que me sorprende constantemente es que muchas secuencias "naturales" $f(n)$ incluso aparentemente muy complicadas, tienen tasas de crecimiento que pueden describirse mediante funciones elementales $g(n)$ (digamos, para ser precisos, funciones expresables utilizando un número acotado de operaciones aritméticas, $\exp$ y $\log$ ), en el sentido de que $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$ . Escribiré $f \sim g$ para esta relación de equivalencia. He aquí algunos ejemplos aproximadamente en orden creciente de lo sorprendente que me parece que la tasa de crecimiento sea elemental (muy subjetivo, por supuesto).
- La secuencia de Fibonacci $F_n$ satisface $F_n \sim \frac{\phi^n}{\sqrt{5}}$ .
- El factorial $n!$ satisface $n! \sim \sqrt{2\pi n} \left( \frac{n}{e} \right)^n$ .
- La función de recuento de primos $\pi(n)$ satisface $\pi(n) \sim \frac{n}{\log n}$ .
- La función de partición $p(n)$ satisface $p(n) \sim \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$ .
- Les Función de Landau $g(n)$ satisface $\log g(n) \sim \sqrt{n \log n}$ . No sé si se espera o no que $g(n) \sim \exp(\sqrt{n \log n})$ .
- Para $p$ un primo, el número $G(p^n)$ de grupos de orden $p^n$ satisface $\log_p G(p^n) \sim \frac{2}{27} n^3$ .
Conozco algunos metateoremas que garantizan una asintótica elemental para algunas clases de secuencias. El más simple implica secuencias con funciones generadoras meromórficas; esto da el ejemplo de Fibonacci anterior, así como ejemplos más complicados como el de números de Bell ordenados . Tengo la impresión de que existen teoremas análogos para las series de Dirichlet que implican teoremas tauberianos que producen el ejemplo PNT y otros ejemplos teóricos numéricos similares. Hay un metateorema que implica límites de punto de silla de montar que da el ejemplo factorial y al menos heurísticamente da el ejemplo de función de partición. Y no conozco ningún metateorema relevante para la función de Landau o $p$ -ejemplos de grupos. Así que, preguntas:
Q1: ¿Cuáles son algunas secuencias "naturales $f(n)$ que (posiblemente conjeturalmente) no tienen asintótica elemental, en el sentido de que no hay funciones elementales $g(n)$ tal que $f(n) \sim g(n)$ ?
De entrada quiero descartar dos clases de contraejemplos que no llegan a lo que me interesa: $f(n)$ puede oscilar demasiado para tener una tasa de crecimiento elemental (por ejemplo $f(n)$ podría ser el número de grupos abelianos de orden $n$ ), o puede crecer demasiado rápido para tener una tasa de crecimiento elemental (por ejemplo $f(n)$ podría ser la función del castor ocupado). Por desgracia, no estoy seguro de cómo plantear rigurosamente una condición que descarte estos y otros contraejemplos de sabor similar. Como mínimo quiero $f(n)$ sea una sucesión no acotada monotónicamente creciente de números enteros positivos, y también quiero que esté acotada desde arriba por una función elemental.
Los tipos de secuencias que me interesan como contraejemplos potenciales son secuencias como la función de Landau anterior, así como secuencias combinatorias como la función de Números de campana $B_n$ . Los propios números de Bell podrían ser un posible contraejemplo. Wikipedia da algunos límites elementales, pero expresa la tasa de crecimiento en términos del Función W de Lambert parece que la función W de Lambert tiene crecimiento elemental, pero no estoy seguro de si eso implica que $B_n$ sí lo hace.
Q2: ¿Cuáles son otros metateoremas que garantizan tasas de crecimiento elementales? ¿Existen aquí buenos principios organizativos?
Q3: ¿Cuáles son algunas secuencias "naturales" de las que se sabe que tienen tasas de crecimiento elementales, pero con argumentos específicos que no entran en los casos cubiertos por ningún metateorema?
Disculpas por las preguntas un tanto abiertas, haría una pregunta más ajustada si supiera cómo enunciarla.
Edita: Wow, aparentemente yo hice casi exactamente esta pregunta casi exactamente $10$ hace años ...e incluso di tres de los mismos ejemplos...
