Double exponential function
   HOME

TheInfoList



OR:

A double exponential function is a constant raised to the power of an
exponential function The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, a ...
. The general formula is f(x) = a^=a^ (where ''a''>1 and ''b''>1), which grows much more quickly than an exponential function. For example, if ''a'' = ''b'' = 10: *''f''(x) = 1010x *''f''(0) = 10 *''f''(1) = 1010 *''f''(2) = 10100 =
googol A googol is the large number 10100. In decimal notation, it is written as the digit 1 followed by one hundred zeroes: 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, ...
*''f''(3) = 101000 *''f''(100) = 1010100 =
googolplex A googolplex is the number 10, or equivalently, 10 or 1010,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 . Written out in ordinary decimal notation, it is 1 fol ...
.
Factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \t ...
s grow faster than exponential functions, but much more slowly than doubly exponential functions. However,
tetration In mathematics, tetration (or hyper-4) is an operation based on iterated, or repeated, exponentiation. There is no standard notation for tetration, though \uparrow \uparrow and the left-exponent ''xb'' are common. Under the definition as rep ...
and the Ackermann function grow faster. See
Big O notation Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
for a comparison of the rate of growth of various functions. The inverse of the double exponential function is the
double logarithm In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number  to the base  is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 ...
log(log(''x'')).


Doubly exponential sequences

A sequence of positive integers (or real numbers) is said to have ''doubly exponential rate of growth'' if the function giving the th term of the sequence is bounded above and below by doubly exponential functions of . Examples include * The
Fermat number In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form :F_ = 2^ + 1, where ''n'' is a non-negative integer. The first few Fermat numbers are: : 3, 5, 17, 257, 65537, 42949672 ...
s F(m) = 2^+1 * The harmonic primes: The primes ''p'', in which the sequence exceeds 0, 1, 2, 3, …The first few numbers, starting with 0, are 2, 5, 277, 5195977, ... * The
Double Mersenne number In mathematics, a double Mersenne number is a Mersenne number of the form :M_ = 2^-1 where ''p'' is prime. Examples The first four terms of the sequence of double Mersenne numbers areChris Caldwell''Mersenne Primes: History, Theorems and Li ...
s MM(p) = 2^-1 * The elements of
Sylvester's sequence In number theory, Sylvester's sequence is an integer sequence in which each term of the sequence is the product of the previous terms, plus one. The first few terms of the sequence are :2, 3, 7, 43, 1807, 3263443, 10650056950807, 11342371305542184 ...
s_n = \left\lfloor E^+\frac12 \right\rfloor where ''E'' ≈ 1.264084735305302 is Vardi's constant . * The number of ''k''-ary
Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ( ...
s: 2^ * The prime numbers 2, 11, 1361, ... a(n) = \left\lfloor A^\right\rfloor where ''A'' ≈ 1.306377883863 is
Mills' constant In number theory, Mills' constant is defined as the smallest positive real number ''A'' such that the floor function of the double exponential function : \lfloor A^ \rfloor is a prime number for all natural numbers ''n''. This constant is named ...
. Aho and Sloane observed that in several important
integer sequence In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers. An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...
s, each term is a constant plus the square of the previous term. They show that such sequences can be formed by rounding to the nearest integer the values of a doubly exponential function with middle exponent 2. Ionaşcu and Stănică describe some more general sufficient conditions for a sequence to be the floor of a doubly exponential sequence plus a constant.


Applications


Algorithmic complexity

In
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, 2-EXPTIME is the class of decision problems solvable in doubly exponential time. It is equivalent to AEXPSPACE, the set of decision problems solvable by an
alternating Turing machine In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP. ...
in exponential space, and is a superset of
EXPSPACE In computational complexity theory, is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in O(2^) space, where p(n) is a polynomial function of n. Some authors restrict p(n) to be a linear func ...
. An example of a problem in 2-EXPTIME that is not in EXPTIME is the problem of proving or disproving statements in
Presburger arithmetic Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omitti ...
. In some other problems in the design and analysis of algorithms, doubly exponential sequences are used within the design of an algorithm rather than in its analysis. An example is
Chan's algorithm In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set P of n points, in 2- or 3-dimensional space. The algorithm takes O(n \log h) time, where h is t ...
for computing
convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
s, which performs a sequence of computations using test values ''h''''i'' = 22''i'' (estimates for the eventual output size), taking time O(''n'' log ''h''''i'') for each test value in the sequence. Because of the double exponential growth of these test values, the time for each computation in the sequence grows singly exponentially as a function of ''i'', and the total time is dominated by the time for the final step of the sequence. Thus, the overall time for the algorithm is O(''n'' log ''h'') where ''h'' is the actual output size.


Number theory

Some number theoretical bounds are double exponential. Odd perfect numbers with ''n'' distinct prime factors are known to be at most 2^, a result of Nielsen (2003). The maximal volume of a
polytope In elementary geometry, a polytope is a geometric object with flat sides (''faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an -d ...
in a ''d''-dimensional
integer lattice In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid l ...
with ''k'' ≥ 1 interior lattice points is at most :k\cdot(8d)^d\cdot15^, a result of Pikhurko (2001). The
largest known prime number The largest known prime number () is , a number which has 24,862,048 digits when written in base 10. It was found via a computer volunteered by Patrick Laroche of the Great Internet Mersenne Prime Search (GIMPS) in 2018. A prime number is a posi ...
in the electronic era has grown roughly as a double exponential function of the year since
Miller A miller is a person who operates a Gristmill, mill, a machine to grind a grain (for example corn or wheat) to make flour. Mill (grinding), Milling is among the oldest of human occupations. "Miller", "Milne" and other variants are common surname ...
and
Wheeler Wheeler may refer to: Places United States * Wheeler, Alabama, an unincorporated community * Wheeler, Arkansas, an unincorporated community * Wheeler, California, an unincorporated community * Wheeler, Illinois, a village * Wheeler, Indiana, a ...
found a 79-digit prime on
EDSAC The Electronic Delay Storage Automatic Calculator (EDSAC) was an early British computer. Inspired by John von Neumann's seminal ''First Draft of a Report on the EDVAC'', the machine was constructed by Maurice Wilkes and his team at the Universi ...
1 in 1951.


Theoretical biology

In
population dynamics Population dynamics is the type of mathematics used to model and study the size and age composition of populations as dynamical systems. History Population dynamics has traditionally been the dominant branch of mathematical biology, which has ...
the growth of human population is sometimes supposed to be double exponential. Varfolomeyev and Gurevich experimentally fit : N(y)=375.6\cdot 1.00185^ \, where ''N''(''y'') is the population in millions in year ''y''.


Physics

In the
Toda oscillator In physics, the Toda oscillator is a special kind of nonlinear oscillator. It represents a chain of particles with exponential potential interaction between neighbors. These concepts are named after Morikazu Toda. The Toda oscillator is used a ...
model of
self-pulsation Self-pulsation is a transient phenomenon in continuous-wave lasers. Self-pulsation takes place at the beginning of laser action. As the pump is switched on, the gain in the active medium rises and exceeds the steady-state value. The number of p ...
, the logarithm of amplitude varies exponentially with time (for large amplitudes), thus the amplitude varies as doubly exponential function of time.. Dendritic
macromolecule A macromolecule is a very large molecule important to biophysical processes, such as a protein or nucleic acid. It is composed of thousands of covalently bonded atoms. Many macromolecules are polymers of smaller molecules called monomers. The ...
s have been observed to grow in a doubly-exponential fashion.


References

{{reflist, 2 Elementary special functions Exponentials