Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Half-exponential function
Function that results in an exponential function when composed

In mathematics, a half-exponential function is a functional square root of an exponential function. That is, a function f {\displaystyle f} such that f {\displaystyle f} composed with itself results in an exponential function: f ( f ( x ) ) = a b x , {\displaystyle f{\bigl (}f(x){\bigr )}=ab^{x},} for some constants a {\displaystyle a} and b {\displaystyle b} .

Hellmuth Kneser first proposed a holomorphic construction of the solution of f ( f ( x ) ) = e x {\displaystyle f{\bigl (}f(x){\bigr )}=e^{x}} in 1950. It is closely related to the problem of extending tetration to non-integer values; the value of 1 2 a {\displaystyle {}^{\frac {1}{2}}a} can be understood as the value of f ( 1 ) {\displaystyle f{\bigl (}1)} , where f ( x ) {\displaystyle f{\bigl (}x)} satisfies f ( f ( x ) ) = a x {\displaystyle f{\bigl (}f(x){\bigr )}=a^{x}} . Example values from Kneser's solution of f ( f ( x ) ) = e x {\displaystyle f{\bigl (}f(x){\bigr )}=e^{x}} include f ( 0 ) ≈ 0.49856 {\displaystyle f{\bigl (}0)\approx 0.49856} and f ( 1 ) ≈ 1.64635 {\displaystyle f{\bigl (}1)\approx 1.64635} .

Related Image Collections Add Image
Profiles
1 Image
We don't have any YouTube videos related to Half-exponential function yet.
We don't have any PDF documents related to Half-exponential function yet.
We don't have any Books related to Half-exponential function yet.
We don't have any archived web articles related to Half-exponential function yet.

Impossibility of a closed-form formula

If a function f {\displaystyle f} is defined using the standard arithmetic operations, exponentials, logarithms, and real-valued constants, then f ( f ( x ) ) {\displaystyle f{\bigl (}f(x){\bigr )}} is either subexponential or superexponential.3 Thus, a Hardy L-function cannot be half-exponential.

Construction

Any exponential function can be written as the self-composition f ( f ( x ) ) {\displaystyle f(f(x))} for infinitely many possible choices of f {\displaystyle f} . In particular, for every A {\displaystyle A} in the open interval ( 0 , 1 ) {\displaystyle (0,1)} and for every continuous strictly increasing function g {\displaystyle g} from [ 0 , A ] {\displaystyle [0,A]} onto [ A , 1 ] {\displaystyle [A,1]} , there is an extension of this function to a continuous strictly increasing function f {\displaystyle f} on the real numbers such that f ( f ( x ) ) = exp ⁡ x {\displaystyle f{\bigl (}f(x){\bigr )}=\exp x} .4 The function f {\displaystyle f} is the unique solution to the functional equation f ( x ) = { g ( x ) if  x ∈ [ 0 , A ] , exp ⁡ g − 1 ( x ) if  x ∈ ( A , 1 ] , exp ⁡ f ( ln ⁡ x ) if  x ∈ ( 1 , ∞ ) , ln ⁡ f ( exp ⁡ x ) if  x ∈ ( − ∞ , 0 ) . {\displaystyle f(x)={\begin{cases}g(x)&{\mbox{if }}x\in [0,A],\\\exp g^{-1}(x)&{\mbox{if }}x\in (A,1],\\\exp f(\ln x)&{\mbox{if }}x\in (1,\infty ),\\\ln f(\exp x)&{\mbox{if }}x\in (-\infty ,0).\\\end{cases}}}

A simple example, which leads to f {\displaystyle f} having a continuous first derivative f ′ {\displaystyle f'} everywhere, and also causes f ″ ≥ 0 {\displaystyle f''\geq 0} everywhere (i.e. f ( x ) {\displaystyle f(x)} is concave-up, and f ′ ( x ) {\displaystyle f'(x)} increasing, for all real x {\displaystyle x} ), is to take A = 1 2 {\displaystyle A={\tfrac {1}{2}}} and g ( x ) = x + 1 2 {\displaystyle g(x)=x+{\tfrac {1}{2}}} , giving f ( x ) = { log e ⁡ ( e x + 1 2 ) if  x ≤ − log e ⁡ 2 , e x − 1 2 if  − log e ⁡ 2 ≤ x ≤ 0 , x + 1 2 if  0 ≤ x ≤ 1 2 , e x − 1 / 2 if  1 2 ≤ x ≤ 1 , x e if  1 ≤ x ≤ e , e x / e if  e ≤ x ≤ e , x e if  e ≤ x ≤ e e , e x 1 / e if  e e ≤ x ≤ e e , … {\displaystyle f(x)={\begin{cases}\log _{e}\left(e^{x}+{\tfrac {1}{2}}\right)&{\mbox{if }}x\leq -\log _{e}2,\\e^{x}-{\tfrac {1}{2}}&{\mbox{if }}{-\log _{e}2}\leq x\leq 0,\\x+{\tfrac {1}{2}}&{\mbox{if }}0\leq x\leq {\tfrac {1}{2}},\\e^{x-1/2}&{\mbox{if }}{\tfrac {1}{2}}\leq x\leq 1,\\x{\sqrt {e}}&{\mbox{if }}1\leq x\leq {\sqrt {e}},\\e^{x/{\sqrt {e}}}&{\mbox{if }}{\sqrt {e}}\leq x\leq e,\\x^{\sqrt {e}}&{\mbox{if }}e\leq x\leq e^{\sqrt {e}},\\e^{x^{1/{\sqrt {e}}}}&{\mbox{if }}e^{\sqrt {e}}\leq x\leq e^{e},\ldots \\\end{cases}}} Crone and Neuendorffer claim that there is no semi-exponential function f(x) that is both (a) analytic and (b) always maps reals to reals. The piecewise solution above achieves goal (b) but not (a). Achieving goal (a) is possible by writing e x {\displaystyle e^{x}} as a Taylor series based at a fixpoint Q (there are an infinitude of such fixpoints, but they all are nonreal complex, for example Q = 0.3181315 + 1.3372357 i {\displaystyle Q=0.3181315+1.3372357i} ), making Q also be a fixpoint of f, that is f ( Q ) = e Q = Q {\displaystyle f(Q)=e^{Q}=Q} , then computing the Maclaurin series coefficients of f ( x − Q ) {\displaystyle f(x-Q)} one by one. This results in Kneser's construction mentioned above.

Application

Half-exponential functions are used in computational complexity theory for growth rates "intermediate" between polynomial and exponential.5 A function f {\displaystyle f} grows at least as quickly as some half-exponential function (its composition with itself grows exponentially) if it is non-decreasing and f − 1 ( x C ) = o ( log ⁡ x ) {\displaystyle f^{-1}(x^{C})=o(\log x)} , for every C > 0 {\displaystyle C>0} .6

See also

References

  1. Kneser, H. (1950). "Reelle analytische Lösungen der Gleichung φ(φ(x) = ex und verwandter Funktionalgleichungen". Journal für die reine und angewandte Mathematik. 187: 56–67. doi:10.1515/crll.1950.187.56. MR 0035385. /wiki/Hellmuth_Kneser ↩

  2. Miltersen, Peter Bro; Vinodchandran, N. V.; Watanabe, Osamu (1999). "Super-polynomial versus half-exponential circuit size in the exponential hierarchy". In Asano, Takao; Imai, Hiroshi; Lee, D. T.; Nakano, Shin-ichi; Tokuyama, Takeshi (eds.). Computing and Combinatorics, 5th Annual International Conference, COCOON '99, Tokyo, Japan, July 26–28, 1999, Proceedings. Lecture Notes in Computer Science. Vol. 1627. Springer. pp. 210–220. doi:10.1007/3-540-48686-0_21. ISBN 978-3-540-66200-6. MR 1730337. 978-3-540-66200-6 ↩

  3. van der Hoeven, J. (2006). Transseries and Real Differential Algebra. Lecture Notes in Mathematics. Vol. 1888. Springer-Verlag, Berlin. doi:10.1007/3-540-35590-1. ISBN 978-3-540-35590-8. MR 2262194. 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 that would be required for a half-exponential function. 978-3-540-35590-8 ↩

  4. Crone, Lawrence J.; Neuendorffer, Arthur C. (1988). "Functional powers near a fixed point". Journal of Mathematical Analysis and Applications. 132 (2): 520–529. doi:10.1016/0022-247X(88)90080-7. MR 0943525. /wiki/Doi_(identifier) ↩

  5. Miltersen, Peter Bro; Vinodchandran, N. V.; Watanabe, Osamu (1999). "Super-polynomial versus half-exponential circuit size in the exponential hierarchy". In Asano, Takao; Imai, Hiroshi; Lee, D. T.; Nakano, Shin-ichi; Tokuyama, Takeshi (eds.). Computing and Combinatorics, 5th Annual International Conference, COCOON '99, Tokyo, Japan, July 26–28, 1999, Proceedings. Lecture Notes in Computer Science. Vol. 1627. Springer. pp. 210–220. doi:10.1007/3-540-48686-0_21. ISBN 978-3-540-66200-6. MR 1730337. 978-3-540-66200-6 ↩

  6. Razborov, Alexander A.; Rudich, Steven (1997). "Natural proofs". Journal of Computer and System Sciences. 55 (1): 24–35. doi:10.1006/jcss.1997.1494. MR 1473047. /wiki/Alexander_Razborov ↩