Fonction exponentielle double
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Double_Exponential_Function.svg/320px-Double_Exponential_Function.svg.png)
Une fonction exponentielle double est une fonction exponentielle dont l’exposant est lui-même une fonction exponentielle.
La forme générale est :
Cette fonction croît plus vite qu’une exponentielle simple. Par exemple, pour a = b = 10 :
- f(−1) ≈ 1,25892541 ;
- f(0) = 10 ;
- f(1) = 1010 ;
- f(2) = 10100 = googol ;
- f(3) = 101000 ;
- f(100) = 1010100 = googolplex.
Les factorielles croissent plus vite que les exponentielles, mais beaucoup plus lentement que les exponentielles doubles. La fonction hyper-exponentielle et la fonction d'Ackermann croissent encore plus vite[1].
L’inverse d’une fonction exponentielle double est un logarithme double.
Suites à croissance exponentielle double
[modifier | modifier le code]Aho et Sloane remarquèrent que, pour certaines suites entières importantes, chaque terme successif est égal au carré du terme précédent plus une constante. Ils montrèrent que de telles suites peuvent être calculées en arrondissant à l’entier le plus proche les valeurs d’une exponentielle double de la forme : [2].
Les suites d'entiers qui suivent ce schéma sont, en particulier :
- Les nombres de Fermat :
- Les termes successifs de la série de Sylvester (suite A000058 de l'OEIS) :
- L’arité des opérateurs logiques :
Plus généralement, si la nième valeur d'une suite d’entiers est proportionnelle à une fonction exponentielle double de n, Ionescu et Stanica qualifient la série de « presque exponentielle double » et indiquent les conditions selon lesquelles elle peut être calculée comme l’arrondi inférieur (arrondi par troncation) d’une série exponentielle double, plus, éventuellement, un coefficient constant[3].
D’autres suites de ce type sont :
- où A ≈ 1,306377883863 est la constante de Mills.
Applications
[modifier | modifier le code]Complexité algorithmique
[modifier | modifier le code]Dans la théorie de la complexité algorithmique, certains algorithmes sont de complexité exponentielle double :
- Procédures de décision dans l’arithmétique de Presburger ;
- Calcul d'une base de Gröbner (dans le cas le plus défavorable) ;
- Trouver en théorie de la décision un ensemble complet unifié d’opérateurs associatifs-commutatifs[4]
- Résolution des problèmes en CTL* (qui sont, en fait en 2-EXP-complets)[5] ;
- L’élimination des quantificateurs sur un corps réel clos nécessite un temps croissant au moins selon une exponentielle double (mais on ne sait même pas si elle est calculable en un temps de classe ELEMENTARY).
Théorie des nombres
[modifier | modifier le code]Certaines limites de la théorie des nombres sont en exponentielle double. Un nombre parfait impair avec n facteur premiers différents, dont on ne sait même pas s’il existe, vaut au plus 24n (Nielsen 2003[6]).
Le nombre de chiffres du plus grand nombre premier connu a évolué selon une exponentielle double en fonction du nombre d’années depuis que l'on dispose d'ordinateurs pour le calculer[réf. souhaitée] (c'est-à-dire depuis que Miller et Wheeler déterminèrent un nombre premier de 79 chiffres sur la machine EDSAC1 in 1951[7]).
Biologie théorique
[modifier | modifier le code]En dynamique des populations, on a émis l’hypothèse que la croissance de la population humaine pouvait être approchée par une fonction exponentielle double. Gurevich and Varfolomeyev [8] ajustèrent expérimentalement la fonction
où N(y) est la population humaine de l’année y en millions.
Physique
[modifier | modifier le code]Dans le modèle d’oscilateur TODA de l'auto-pulsation, le logarithme de l’amplitude (pour les grandes amplitudes) croît exponentiellement avec le temps ; ainsi l’amplitude croît-elle selon une double exponentielle du temps [9].
Références
[modifier | modifier le code]- Sur la comparaison de la croissance des fonctions, voir Comparaison asymptotique.
- (en) A. V. Aho et N. J. A. Sloane, « Some doubly exponential sequences », Fibonacci Quarterly, vol. 11, , p. 429-437.
- (en) E. Ionascu et P. Stanica, « Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences », Acta Mathematica Universitatis Comenianae, vol. LXXIII, no 1, , p. 78-87.
- (en) Deepak Kapur et Paliath Narendran, « Double-exponential complexity of computing a complete set of AC-unifiers », Proc. 7th IEEE Symp. Logic in Computer Science (LICS 1992), , p. 11-21 (lire en ligne) ;
- (en) Jan Johannse et Martin Lange, « CTL+ is complete for double exponential time », Proc. 30th Int. Colloq. Automata, Languages, and Programming (ICALP 2003), Springer-Verlag, vol. 2719, , p. 767–775 (DOI 10.1007/3-540-45061-0_60, lire en ligne)
- (en) Pace P. Nielsen, « An upper bound for odd perfect numbers », The Electronic Journal of Combinatorial Number Theory, vol. 3, , A14 (lire en ligne)
- (en) J. C. P. Miller et D. J. Wheeler, « Large prime numbers », Nature, vol. 168, , p. 838 (DOI 10.1038/168838b0)
- (en) S. D. Varfolomeyev et K. G. Gurevich, « The hyperexponential growth of the human population on a macrohistorical scale », Journal of Theoretical Biology, vol. 212, no 3, , p. 367–372 (DOI 10.1006/jtbi.2001.2384).
- D. Kouznetsov, J.-F. Bisson, J. Li et K. Ueda, « Self-pulsing laser as oscillator Toda: Approximation through elementary functions », Journal of Physics A : Mathematical and Theorical, vol. 40, , p. 1–18 (DOI 10.1088/1751-8113/40/9/016, lire en ligne)