二重指数関数

二重指数関数（にじゅうしすうかんすう、英: double exponential function）とは、指数関数の肩に指数関数を持つ関数である。一般形は $f(x)=a^{b^{x}}=a^{(b^{x})}$ 。指数関数と同様に、二重指数関数型積分公式など、応用上はネイピア数を底に取ったものがよく使われる。

指数の底が $a > 1, b > 1$ を満たすなら、二重指数関数は通常の指数関数よりも速く大きくなる。また二重指数関数は階乗より急速に増大する。階乗は通常の（一重の）指数関数よりも速く増大するため、充分大きい $x$ について以下の関係が成り立つ（ $e$ はネイピア数）：

$e^{x}<x!<e^{e^{x}}$

二重指数関数に比べて速く増大する関数として、例えばテトレーションとアッカーマン関数がよく知られている（その他さまざまな関数の増加率については例えばランダウの記号を参照のこと）。

二重指数関数 $a^{b^{x}}$ の逆関数は、二重対数 $\log _{b}(\log _{a}x)$ である。

二重指数列

正の整数（または実数）の数列で、数列のn番目の項を与える関数がnの二重指数関数で上下を押さえられるものを、二重指数関数的に成長する数列という。

フェルマー数

F(m)=2^{2^{m}}+1

調和素数：1/2 + 1/3 + 1/5 + 1/7 + ... + 1 / pが0、1、2、3、..を超える素数p 0で始まる最初のいくつかの番号は、2、5、277、5195977、...（A016088）である。
二重メルセンヌ数

MM(p)=2^{2^{p-1}}-1

シルベスター数列の要素（A000058）

s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor

なお、E ≈ 1.264084735305302 はヴァルディの定数（A076393）である

k-aryブール関数:

2^{2^{k}}

素数 2, 11, 1361, ... (A051254)

a(n)=\left\lfloor A^{3^{n}}\right\rfloor

なお、A ≈ 1.306377883863はミルズの定数である。

アルフレッド・エイホとニール・スローンは、いくつかの重要な整数列で、各項が定数に前の項の2乗を加えたものであることを観察した。それらは、そのような数列が、中間の指数2を持つ二重指数関数の値を最も近い整数に丸めることによって形成できることを示している^[1] IonaşcuとStănicăは、数列が二重指数列と定数のフロアになるためのより一般的な十分条件について説明している^[2]。

微分・積分

自然二重指数関数

微分

${d \over dx}e^{e^{x}}=e^{x+e^{x}}$

積分

積分定数は省略する。

$\int e^{e^{x}}dx=\operatorname {Ei} (e^{x})$

ただし、ここで $\operatorname {Ei} (x)$ は指数積分である。

テイラー展開

自然二重指数関数 $e^{e^{x}}$ は、ベル数 $B_{n}$ の指数型母関数

$\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}=e^{e^{x}-1}$

により

$e^{e^{x}}=e\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}$

とマクローリン展開される。

応用

計算機科学

計算複雑性理論では、以下に示すようなアルゴリズムにおいて二重指数関数時間を要する。

プレスバーガー算術の決定問題の計算複雑性は二重指数関数時間に漸近される。
体上のグレブナー基底の計算。多項式の最大次数を $d$ 、変数の数を $n$ とすると、グレブナー基底の計算複雑性は最悪 $d 2 n +o(n)$ となることがある。
ACユニファーの完全系の発見^[3]
CTL⁺の満足^[4]。これは実際には2-EXPTIME（英語版）完全である。ただし、2-EXPTIMEとは $p (n)$ を $n$ の多項式として $O(2 2 p (n))$ の時間で解ける決定問題の集合である。
実閉体上での量化子除去（英語版）（円筒代数分解（英語版）を参照）.
正規表現の補数の計算^[5]

アルゴリズムの設計と解析における他の問題では、二重指数数列は解析ではなくアルゴリズム設計の中で使用される。例えば、凸包を計算するチャンのアルゴリズム（英語版）では、テスト値 $h i =2 2 i$ （最終的な出力サイズの推定値）を用いて一連の計算を行い、一連の各テスト値に対して $O (n log h i)$ の時間を要する。これらのテスト値は二重指数関数的に成長するため、数列の各計算の時間は $i$ の関数として指数関数的に成長し、総時間は数列の最終ステップの時間が支配的となる。したがって、このアルゴリズムの全体的な時間は $O (n log h)$ となり、 $h$ は実際の出力サイズとなる^[6]。

数論

数論的な上限は二重指数関数的になるものもある。たとえば、 $n$ 個の異なる素因数を持つ奇数完全数は最大で $2 4 n$ となる（ヤコブ・ニールセン（数学者）（英語版）,2003）^[7]。また、 $k \geq1$ の格子点を内部に持つ $d -$ 次元超多面体の体積は最大で $(8 d) d ･15 d ･2 2 d +1$ になる（Pikhurko）^[8]。

情報化時代に知られている最大の素数の桁数は、1951年にMillerとWheelerがEDSAC1で79桁の素数を発見して以来、年に対する二重指数関数として近似的に成長している^[9]。

理論生物学

人口統計学では、人口増加は二重指数関数的であるとされることがある。VarfolomeyevとGurevichが実験的に検証したところ^[10]、 $N (y)$ を一年あたりの100万人の人口増加として

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

であった。

物理学

戸田発振器（英語版）の自己振動モデルでは、振幅が大きい場合に振幅の対数が時間に対して指数関数的に変化するため、振幅は時間の二重指数関数として変化する^[11]。

また、樹状高分子は二重指数関数的に成長することが観察されている^[12]。

参考文献

[脚注の使い方]

^ Aho, A. V.; Sloane, N. J. A. (1973), “Some doubly exponential sequences”, Fibonacci Quarterly 11: 429–437, http://neilsloane.com/doc/doubly.html .
^ 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 .
^ Kapur, Deepak; Narendran, Paliath (1992), “Double-exponential complexity of computing a complete set of AC-unifiers”, Proc. 7th IEEE Symp. Logic in Computer Science (LICS 1992), pp. 11–21, doi:10.1109/LICS.1992.185515, ISBN 0-8186-2735-2 .
^ Johannsen, Jan; Lange, Martin (2003), “CTL⁺ is complete for double exponential time”, in Baeten, Jos C. M.; Lenstra, Jan Karel; Parrow, Joachim et al., Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), Lecture Notes in Computer Science, 2719, Springer-Verlag, pp. 767–775, doi:10.1007/3-540-45061-0_60, ISBN 978-3-540-40493-4, オリジナルの2007-09-30時点におけるアーカイブ。 2006年12月22日閲覧。 .
^ Gruber, Hermann; Holzer, Markus (2008). "Finite Automata, Digraph Connectivity, and Regular Expression Size" (PDF). Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008). the 35th International Colloquium on Automata, Languages and Programming. Vol. 5126. pp. 39–50. doi:10.1007/978-3-540-70583-3_4。
^ Chan, T. M. (1996), “Optimal output-sensitive convex hull algorithms in two and three dimensions”, Discrete and Computational Geometry 16 (4): 361–368, doi:10.1007/BF02712873, MR1414961
^ Nielsen, Pace P. (2003), “An upper bound for odd perfect numbers”, INTEGERS: The Electronic Journal of Combinatorial Number Theory 3: A14 .
^ Pikhurko, Oleg (2001), “Lattice points in lattice polytopes”, Mathematika 48: 15–24, arXiv:math/0008028, Bibcode: 2000math......8028P, doi:10.1112/s0025579300014339
^ Miller, J. C. P.; Wheeler, D. J. (1951), “Large prime numbers”, Nature 168 (4280): 838, Bibcode: 1951Natur.168..838M, doi:10.1038/168838b0 .
^ 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, doi:10.1006/jtbi.2001.2384, PMID 11829357 .
^ 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 .
^ 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.