Función doble exponencial

Una función exponencial doble (curva roja) en comparación con una función exponencial simple (curva azul)

Una función doble exponencial (o exponencial doble) es una constante elevada a la potencia de una función exponencial. La fórmula general es ${\displaystyle f(x)=a^{b^{x}}=a^{(b^{x})}}$ (donde a>1 y b>1), y su crecimiento es mucho más rápido que el de una función exponencial. Por ejemplo, si a = b = 10:

• f(0) = 10
• f(1) = 10^10
• f(2) = 10^100 = gúgol
• f(3) = 10^1000
• f(100) = 10^10100 = gúgolplex.

Los factoriales crecen más rápido que las funciones exponenciales, pero mucho más lentamente que las funciones doblemente exponenciales. Sin embargo, la tetración y la función de Ackermann crecen más rápido todavía. Véase cota superior asintótica para una comparación de la tasa de crecimiento de distintas funciones.

El inverso de la función doble exponencial es el doble logaritmo log(log(x)).

Sucesiones doblemente exponenciales

Se dice que una secuencia de enteros positivos (o números reales) tiene una tasa de crecimiento doblemente exponencial si la función que da el término n de la secuencia está limitada por arriba y por abajo por funciones doblemente exponenciales de n. Entre los ejemplos se incluyen:

• Los números de Fermat $${\displaystyle F(m)=2^{2^{m}}+1}$$
• Los primos armónicos, es decir, los primos p en los que la sucesión 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/p supera a 0, 1, 2, 3, … Los primeros números, a partir del 0, son 2, 5, 277, 5195977, ... (sucesión A016088 en OEIS)
• Los números dobles de Mersenne $${\displaystyle MM(p)=2^{2^{p}-1}-1}$$
• Los elementos de la sucesión de Sylvester (sucesión A000058 en OEIS) $${\displaystyle s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor }$$ donde E ≈ 1.264084735305302 es la constante de Vardi (sucesión A076393 en OEIS).
• Las funciones booleanas k-arias: $${\displaystyle 2^{2^{k}}}$$
• Los números primos 2, 11, 1361, ... (sucesión A051254 en OEIS) $${\displaystyle a(n)=\left\lfloor A^{3^{n}}\right\rfloor }$$ donde A ≈ 1.306377883863 es la constante de Mills.

Alfred Aho y Neil Sloane observaron que en varios sucesiones enteras importantes, cada término es una constante más el cuadrado del término anterior. Muestran que tales secuencias pueden formarse redondeando al entero más cercano a los valores de una función doblemente exponencial con exponente medio 2.[1]​ Ionaşcu y Stănică describen algunas condiciones suficientes más generales para que una secuencia sea el suelo de una secuencia doblemente exponencial más una constante.[2]​

Aplicaciones

Complejidad algorítmica

En teoría de la complejidad computacional, 2-EXPTIME es la clase de problemas de decisión que se pueden resolver en un tiempo doblemente exponencial. Es equivalente a AEXPSPACE, el conjunto de problemas de decisión que se pueden resolver con una máquina de Turing alternante en el espacio exponencial, y es un superconjunto de EXPSPACE.[3]​ Un ejemplo de un problema en 2-EXPTIME que no está en EXPTIME es el problema de probar o refutar declaraciones en la aritmética de Presburger.[4]​

En algunos otros problemas en el diseño y análisis de algoritmos, las secuencias doblemente exponenciales se usan dentro del diseño de un algoritmo en lugar de en su análisis. Un ejemplo es el algoritmo de Chan para calcular una envolvente convexa, que realiza una secuencia de cálculos usando valores de prueba h_i = 2^2i (estimaciones para el tamaño de salida final), tomando el tiempo O(n log  h_i) para cada valor de prueba en la secuencia. Debido al doble crecimiento exponencial de estos valores de prueba, el tiempo para cada cálculo en la secuencia crece exponencialmente en función de i, y el tiempo total está dominado por el tiempo del paso final de la secuencia. Por lo tanto, el tiempo total para el algoritmo es O(n log h) donde h es el tamaño de salida real.[5]​

Teoría de números

Algunos límites de la teoría de números son exponenciales dobles. Se sabe que los números perfectos con n factores primos distintos son como máximo ${\displaystyle 2^{4^{n}}}$, resultado demostrado por Nielsen (2003).[6]​

El volumen máximo de un politopo en una retícula entera de dimensión d con k ≥ 1 puntos reticulares interiores es como máximo de

${\displaystyle k\cdot (8d)^{d}\cdot 15^{d\cdot 2^{2d+1}},}$

resultado de Pikhurko (2001).[7]​

El mayor número primo conocido en la era electrónica ha crecido aproximadamente como una función exponencial doble desde el año en el que Miller y Wheeler encontraron un número primo de 79 dígitos en el ordenador EDSAC1 en 1951.[8]​

Biología teórica

En dinámica de poblaciones, a veces se supone que el crecimiento de la población humana es doblemente exponencial. Varfolomeyev y Gurevich propusieron[9]​ con valores experimentalmente ajustados que

${\displaystyle N(y)=375.6\cdot 1.00185^{1.00737^{y-1000}}\,}$

donde N(y) es la población en millones en el año y.

Aplicaciones en física

En el modelo del oscilador de Toda de autopulsación, el logaritmo de la amplitud varía exponencialmente con el tiempo (para amplitudes grandes), por lo que la amplitud varía como una función del tiempo doblemente exponencial.[10]​

Se ha observado que las macromoléculas dendríticas crecen de forma doblemente exponencial.[11]​

Referencias

1. Aho, A. V.; Sloane, N. J. A. (1973), «Some doubly exponential sequences», Fibonacci Quarterly 11: 429-437 ..
2. Ionaşcu, Eugen-Julien; Stănică, Pantelimon (2004), «Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences», Acta Mathematica Universitatis Comenianae LXXIII (1): 75-87 ..
3. Christos Papadimitriou, Computational Complexity (1994), ISBN 978-0-201-53082-7. Section 20.1, corollary 3, page 495.
4. Fischer, M. J., and Michael Oser Rabin, 1974, ""Super-Exponential Complexity of Presburger Arithmetic. Archivado el 15 de septiembre de 2006 en Wayback Machine." Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7: 27–41
5. Chan, T. M. (1996), «Optimal output-sensitive convex hull algorithms in two and three dimensions», Discrete and Computational Geometry 16 (4): 361-368, MR 1414961, doi:10.1007/BF02712873 .
6. Nielsen, Pace P. (2003), «An upper bound for odd perfect numbers», INTEGERS: The Electronic Journal of Combinatorial Number Theory 3: A14 ..
7. Pikhurko, Oleg (2001), «Lattice points in lattice polytopes», Mathematika 48 (1–2): 15-24, Bibcode:2000math......8028P, arXiv:math/0008028, doi:10.1112/s0025579300014339 .
8. Miller, J. C. P.; Wheeler, D. J. (1951), «Large prime numbers», Nature 168 (4280): 838, Bibcode:1951Natur.168..838M, doi:10.1038/168838b0 ..
9. Varfolomeyev, S. D.; Gurevich, K. G. (2001), «The hyperexponential growth of the human population on a macrohistorical scale», Journal of Theoretical Biology 212 (3): 367-372, PMID 11829357, doi:10.1006/jtbi.2001.2384 ..
10. Kouznetsov, D.; Bisson, J.-F.; Li, J.; Ueda, K. (2007), «Self-pulsing laser as oscillator Toda: Approximation through elementary functions», Journal of Physics A 40 (9): 1-18, Bibcode:2007JPhA...40.2107K, doi:10.1088/1751-8113/40/9/016 ..
11. Kawaguchi, Tohru; Walker, Kathleen L.; Wilkins, Charles L.; Moore, Jeffrey S. (1995). «Double Exponential Dendrimer Growth». Journal of the American Chemical Society 117 (8): 2159-2165. doi:10.1021/ja00113a005. 

• Datos: Q3075235