mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a half-exponential function is a

functional square root In mathematics, a functional square root (sometimes called a half iterate) is a square root of a function with respect to the operation of function composition. In other words, a functional square root of a function is a function satisfying ...

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 ...

. That is, a

function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...

f

such that

f

composed with itself results in an exponential function:

f\bigl(f(x)\bigr) = ab^x,

for some constants

Impossibility of a closed-form formula

If a function

f

is defined using the standard arithmetic operations, exponentials,

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 o ...

s, and

real Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...

-valued constants, then

f\bigl(f(x)\bigr)

is either subexponential or superexponential. Thus, a Hardy -function cannot be half-exponential.

Construction

Any exponential function can be written as the self-composition

f(f(x))

for infinitely many possible choices of

f

. In particular, for every

A

in the

open interval In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers satisfying is an interval which contains , , and all numbers in between. Other ...

(0,1)

and for every

continuous Continuity or continuous may refer to: Mathematics * Continuity (mathematics), the opposing concept to discreteness; common examples include ** Continuous probability distribution or random variable in probability and statistics ** Continuous ...

strictly increasing function

g

from

,A /math>

onto In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...

,1 /math>, there is an extension of this function to a continuous strictly increasing function f on the real numbers such that  The function f is the unique solution to the

functional equation In mathematics, a functional equation is, in the broadest meaning, an equation in which one or several functions appear as unknowns. So, differential equations and integral equations are functional equations. However, a more restricted meaning ...

\\ \exp g^ (x) & \mbox x \in (A,1], \\ \exp f ( \ln x) & \mbox x \in (1,\infty), \\ \ln f ( \exp x) & \mbox x \in (-\infty,0). \\ \end

A simple example, which leads to

f

having a continuous first derivative everywhere, is to take

A=\tfrac12

and

g(x)=x+\tfrac12

, giving

f (x) =
\begin
\log_e\left(e^x +\tfrac12\right) & \mbox x \le -\log_e 2, \\
e^x - \tfrac12 & \mbox  \le x \le 0, \\
x +\tfrac12 & \mbox 0 \le x \le \tfrac12, \\
e^ & \mbox \tfrac12 \le x \le 1 , \\
x \sqrt & \mbox 1 \le x \le \sqrt , \\
e^ & \mbox \sqrt \le x \le e , \\
x^ & \mbox e \le x \le e^ , \\
e^  & \mbox e^ \le x \le e^e , \ldots\\
\end

Application

Half-exponential functions are used 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 ...

for growth rates "intermediate" between polynomial and exponential. A function

f

grows at least as quickly as some half-exponential function (its composition with itself grows exponentially) if it is non-decreasing and

f^(x^C)=o(\log x)

, for

References

{{reflist, refs= {{cite journal , last1 = Crone , first1 = Lawrence J. , last2 = Neuendorffer , first2 = Arthur C. , doi = 10.1016/0022-247X(88)90080-7 , doi-access = free , issue = 2 , journal = Journal of Mathematical Analysis and Applications , mr = 943525 , pages = 520–529 , title = Functional powers near a fixed point , volume = 132 , year = 1988 {{cite conference , last1 = Miltersen , first1 = Peter Bro , last2 = Vinodchandran , first2 = N. V. , last3 = Watanabe , first3 = Osamu , editor1-last = Asano , editor1-first = Takao , editor2-last = Imai , editor2-first = Hiroshi , editor3-last = Lee , editor3-first = D. T. , editor4-last = Nakano , editor4-first = Shin-ichi , editor5-last = Tokuyama , editor5-first = Takeshi , contribution = Super-polynomial versus half-exponential circuit size in the exponential hierarchy , doi = 10.1007/3-540-48686-0_21 , mr = 1730337 , pages = 210–220 , publisher = Springer , series = Lecture Notes in Computer Science , title = Computing and Combinatorics, 5th Annual International Conference, COCOON '99, Tokyo, Japan, July 26–28, 1999, Proceedings , volume = 1627 , year = 1999 {{cite journal , last1 = Razborov , first1 = Alexander A. , author1-link = Alexander Razborov , last2 = Rudich , first2 = Steven , author2-link = Steven Rudich , doi = 10.1006/jcss.1997.1494 , doi-access = free , issue = 1 , journal =

Journal of Computer and System Sciences The ''Journal of Computer and System Sciences'' (JCSS) is a peer-reviewed scientific journal in the field of computer science. ''JCSS'' is published by Elsevier, and it was started in 1967. Many influential scientific articles have been publishe ...

, mr = 1473047 , pages = 24–35 , title = Natural proofs , volume = 55 , year = 1997 {{cite journal , last = Kneser , first = H. , author-link = Hellmuth Kneser , journal =

Journal für die reine und angewandte Mathematik ''Crelle's Journal'', or just ''Crelle'', is the common name for a mathematics journal, the ''Journal für die reine und angewandte Mathematik'' (in English: ''Journal for Pure and Applied Mathematics''). History The journal was founded by Augus ...

, mr = 0035385 , pages = 56–67 , title = Reelle analytische Lösungen der Gleichung {{math, ''φ''(''φ''(''x'') {{= ''e''^''x'' und verwandter Funktionalgleichungen , url = https://gdz.sub.uni-goettingen.de/id/PPN243919689_0187?tify%3D%7B%22pages%22%3A%5B62%5D%7D , volume = 187 , year = 1950 {{cite book , last = van der Hoeven , first = J. , doi = 10.1007/3-540-35590-1 , isbn = 978-3-540-35590-8 , mr = 2262194 , publisher = Springer-Verlag, Berlin , series = Lecture Notes in Mathematics , title = Transseries and real differential algebra , volume = 1888 , year = 2006 See exercise 4.10, p. 91, according to which every such function has a comparable growth rate to an exponential or logarithmic function iterated an integer number of times, rather than the

half-integer In mathematics, a half-integer is a number of the form :n + \tfrac, where n is an whole number. For example, :, , , 8.5 are all ''half-integers''. The name "half-integer" is perhaps misleading, as the set may be misunderstood to include numbers ...

that would be required for a half-exponential function.

External links

Does the exponential function have a (compositional) square root?

“Closed-form” functions with half-exponential growth
Analysis of algorithms Computational complexity theory

Impossibility of a closed-form formula

Construction

Application

See also

References

External links