Content deleted Content added
Citation bot (talk | contribs) m Alter: template type. Add: title, citeseerx, isbn. Converted bare reference to cite template. | You can use this bot yourself. Report bugs here. | User-activated. |
No edit summary |
||
| (41 intermediate revisions by 18 users not shown) | |||
Line 1:
{{Short description|Functional square root of an exponential}}
In [[mathematics]], a '''half-exponential function''' is a [[functional square root]] of an [[exponential function]]. That is, a [[function (mathematics)|function]] <math>f</math> such that <math>f</math> [[function composition|composed]] with itself results in an exponential function:{{r|sqrtexp|miltersen}}
<math display=block>f\bigl(f(x)\bigr) = ab^x,</math>
for some constants {{nowrap|<math>a</math> and <math>b</math>.}}
[[Hellmuth Kneser]] first proposed a [[holomorphic function|holomorphic]] construction of the solution of <math>f\bigl(f(x)\bigr) = e^x</math> in 1950. It is closely related to the problem of extending [[tetration]] to non-integer values; the value of <math>{}^\frac{1}{2} a</math> can be understood as the value of <math>f\bigl(1)</math>, where <math>f\bigl(x)</math> satisfies <math>f\bigl(f(x)\bigr) = a^x</math>. Example values from Kneser's solution of <math>f\bigl(f(x)\bigr) = e^x</math> include <math>f\bigl(0) \approx 0.49856</math> and <math>f\bigl(1) \approx 1.64635</math>.
==Impossibility of a closed-form formula==
If a function <math>f</math> is defined using the standard arithmetic operations, exponentials, [[logarithm]]s, and [[Real number|real]]-valued constants, then <math>f\bigl(f(x)\bigr)</math> is either subexponential or superexponential.{{r|transseries}} Thus, a [[Hardy field#Examples|Hardy {{mvar|L}}-function]] cannot be half-exponential.
==Construction==
Any exponential function can be written as the self-composition <math>f(f(x))</math> for infinitely many possible choices of <math>f</math>. In particular, for every <math>A</math> in the [[open interval]] <math>(0,1)</math> and for every [[continuous function|continuous]] [[Monotonic function|strictly increasing]] function <math>g</math> from <math>[0,A]</math> [[surjective function|onto]] <math>[A,1]</math>, there is an extension of this function to a continuous strictly increasing function <math>f</math> on the real numbers such that {{nowrap|<math>f\bigl(f(x)\bigr)=\exp x</math>.{{r|croneu}}}} The function <math>f</math> is the unique solution to the [[functional equation]]
<math display=block> 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}
</math>
[[File:Half-exponential_function.png|thumb|right|300px|Example of a half-exponential function]]
A simple example, which leads to <math>f</math> having a continuous first derivative <math>f'</math> everywhere, and also causes
<math>f''\ge 0</math> everywhere (i.e. <math>f(x)</math> is concave-up,
and <math>f'(x)</math> increasing,
for all real <math>x</math>),
is to take <math>A=\tfrac12</math> and <math>g(x)=x+\tfrac12</math>, giving
<math display=block> f (x) =
\begin{cases}
\log_e\left(e^x +\tfrac12\right) & \mbox{if } x \le -\log_e 2, \\
e^x - \tfrac12 & \mbox{if } {-\log_e 2} \le x \le 0, \\
x +\tfrac12 & \mbox{if } 0 \le x \le \tfrac12, \\
e^{x-1/2} & \mbox{if } \tfrac12 \le x \le 1 , \\
x \sqrt{e} & \mbox{if } 1 \le x \le \sqrt{e} , \\
e^{x / \sqrt{e}} & \mbox{if } \sqrt{e} \le x \le e , \\
x^{\sqrt{e}} & \mbox{if } e \le x \le e^{\sqrt{e}} , \\
e^{x^{1/\sqrt{e}}} & \mbox{if } e^{\sqrt{e}} \le x \le e^e , \ldots\\
\end{cases}
</math>
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 <math>e^x</math> as a Taylor
series based at a fixpoint Q (there are an infinitude of such fixpoints,
but they all are nonreal complex,
for example <math>Q=0.3181315+1.3372357i</math>), making
Q also be a fixpoint of f, that is <math>f(Q)=e^Q=Q</math>,
then computing the [[Taylor series|Maclaurin series]] coefficients of <math>f(x-Q)</math> 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.{{r|miltersen}} A function <math>f</math> grows at least as quickly as some half-exponential function (its composition with itself grows exponentially) if it is [[Monotonic function|non-decreasing]] and <math>f^{-1}(x^C)=o(\log x)</math>, for {{nowrap|every <math>C>0</math>.{{r|razrud}}}}
==See also==
*{{annotated link|Iterated function}}
*{{annotated link|Schröder's equation}}
*{{annotated link|Abel equation}}
==References==
{{reflist|refs=
<ref name=croneu>{{cite journal
| last1 = Crone | first1 = Lawrence J.
| last2 = Neuendorffer | first2 = Arthur C.
| doi = 10.1016/0022-247X(88)90080-7 | doi-access =
| issue = 2
| journal = Journal of Mathematical Analysis and Applications
Line 26 ⟶ 69:
| title = Functional powers near a fixed point
| volume = 132
| year = 1988}}</ref>
<ref name=miltersen>{{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| isbn = 978-3-540-66200-6
}}</ref>
<ref name=razrud>{{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]]
| mr = 1473047
| pages = 24–35
| title = Natural proofs
| volume = 55
| year = 1997}}</ref>
<ref name=sqrtexp>{{cite journal
| last = Kneser | first = H. | author-link = Hellmuth Kneser
| journal = [[Crelle's Journal|Journal für die reine und angewandte Mathematik]]
| mr = 0035385
| pages = 56–67
| title = Reelle analytische Lösungen der Gleichung {{math|''φ''(''φ''(''x'') {{=}} ''e''<sup>''x''</sup>}} 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| doi = 10.1515/crll.1950.187.56 }}</ref>
<ref name=transseries>{{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]] that would be required for a half-exponential function.</ref>
}}
==External links==
[[Category:Analysis of algorithms]]
| |||