Fonction exponentielle double - Double exponential function

Une fonction exponentielle double (courbe rouge) par rapport à une fonction exponentielle simple (courbe bleue).

Une fonction exponentielle double est une constante élevée à la puissance d'une fonction exponentielle . La formule générale est (où a >1 et b >1), qui croît beaucoup plus rapidement qu'une fonction exponentielle. Par exemple, si a = b = 10 : ${\displaystyle f(x)=a^{b^{x}}=a^{(b^{x})}}$

• f (0) = 10
• f (1) = 10 ¹⁰
• f (2) = 10 ¹⁰⁰ = gogol
• f (3) = 10 ¹⁰⁰⁰
• f (100) = 10 ^{10 100} = googolplex .

Les factorielles croissent plus vite que les fonctions exponentielles, mais beaucoup plus lentement que les fonctions doublement exponentielles. Cependant, la tétration et la fonction d'Ackermann croissent plus rapidement. Voir la notation Big O pour une comparaison du taux de croissance de diverses fonctions.

L'inverse de la fonction exponentielle double est le double logarithme ln(ln( x )).

Séquences doublement exponentielles

Une séquence d'entiers positifs (ou de nombres réels) est dite avoir un taux de croissance doublement exponentiel si la fonction donnant le n ième terme de la séquence est bornée en haut et en bas par des fonctions doublement exponentielles de n . Les exemples comprennent

• Les nombres de Fermat
  $${\style d'affichage F(m)=2^{2^{m}}+1}$$

  
• Les nombres premiers harmoniques : Les nombres premiers p , dans lesquels la suite 1/2 + 1/3 + 1/5 + 1/7 + + 1/ p dépasse 0, 1, 2, 3, …
  Les premiers nombres, commençant par 0, sont 2, 5, 277, 5195977, ... (séquence A016088 dans l' OEIS )
• Les nombres Double Mersenne
  $${\displaystyle MM(p)=2^{2^{p}-1}-1}$$

  
• Les éléments de la séquence de Sylvestre (séquence A000058 dans l' OEIS )
  $${\displaystyle s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor }$$

  
  où E 1,264084735305302 est la constante de Vardi (séquence A076393 dans l' OEIS ).
• Le nombre de fonctions booléennes k -aires :
  $${\displaystyle 2^{2^{k}}}$$

  
• Les nombres premiers 2, 11, 1361, ... (séquence A051254 dans l' OEIS )
  $${\displaystyle a(n)=\left\lfloor A^{3^{n}}\right\rfloor }$$

  
  où A 1,306377883863 est la constante de Mills .

Aho et Sloane ont observé que dans plusieurs séquences entières importantes , chaque terme est une constante plus le carré du terme précédent. Ils montrent que de telles séquences peuvent être formées en arrondissant à l'entier le plus proche les valeurs d'une fonction doublement exponentielle avec l'exposant médian 2. Ionaşcu et Stănică décrivent des conditions suffisantes plus générales pour qu'une séquence soit le plancher d'une séquence doublement exponentielle plus une constante .

Applications

Complexité algorithmique

Dans la théorie de la complexité computationnelle , certains algorithmes prennent un temps doublement exponentiel :

• Il est prouvé que chaque procédure de décision pour l'arithmétique de Presburger nécessite au moins un temps exponentiel double
• Calculer une base de Gröbner sur un champ. Dans le pire des cas, une base de Gröbner peut avoir un nombre d'éléments doublement exponentiel en nombre de variables. D'autre part, la complexité dans le pire des cas des algorithmes de base de Gröbner est doublement exponentielle en nombre de variables ainsi qu'en taille d'entrée.
• Trouver un ensemble complet d'unificateurs associatifs-commutatifs
• CTL ⁺ satisfaisant (qui est, en fait, 2-EXPTIME -complet)
• L'élimination des quantificateurs sur des corps fermés réels prend un temps doublement exponentiel (voir Décomposition algébrique cylindrique ).
• Calculer le complément d'une expression régulière

Dans certains autres problèmes de conception et d'analyse d'algorithmes, des séquences doublement exponentielles sont utilisées dans la conception d'un algorithme plutôt que dans son analyse. Un exemple est l'algorithme de Chan pour le calcul des enveloppes convexes , qui effectue une séquence de calculs en utilisant les valeurs de test h _i  = 2 ^{2 i} (estimations de la taille de sortie finale), en prenant le temps O( n  log  h _i ) pour chaque valeur de test dans la séquence . En raison de la double croissance exponentielle de ces valeurs de test, le temps pour chaque calcul dans la séquence croît de manière exponentielle en fonction de i , et le temps total est dominé par le temps pour l'étape finale de la séquence. Ainsi, le temps global pour l'algorithme est O( n  log  h ) où h est la taille de sortie réelle.

La théorie du nombre

Certaines bornes théoriques des nombres sont doublement exponentielles. Les nombres parfaits impairs avec n facteurs premiers distincts sont connus pour être au plus

${\displaystyle 2^{4^{n}}}$

un résultat de Nielsen (2003). Le volume maximal d'un polytope du réseau d avec k ≥ 1 points de réseau intérieurs est au plus

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

un résultat de Pikhurko.

Le plus grand nombre premier connu de l'ère électronique a augmenté à peu près comme une double fonction exponentielle de l'année depuis que Miller et Wheeler ont trouvé un nombre premier à 79 chiffres sur EDSAC 1 en 1951.

Biologie théorique

Dans la dynamique des populations, la croissance de la population humaine est parfois supposée être doublement exponentielle. Varfolomeyev et Gurevich s'adaptent expérimentalement

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

où N ( y ) est la population en millions de l' année y .

La physique

Dans le modèle d' auto-pulsation de l' oscillateur Toda , le logarithme de l'amplitude varie de façon exponentielle avec le temps (pour les grandes amplitudes), donc l'amplitude varie comme une fonction doublement exponentielle du temps.

Il a été observé que les macromolécules dendritiques croissent de façon doublement exponentielle.

Les références