Content deleted Content added
Kneser title, year, mr, url |
No edit summary |
||
| (26 intermediate revisions by 13 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==
<math display=block> f (x) =
\begin{cases}
Line 37 ⟶ 21:
[[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,
<math> 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 , \\
Line 50 ⟶ 38:
\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.
==See also==
Line 60 ⟶ 57:
==References==
{{reflist
<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
| mr = 943525
| pages = 520–529
| 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==
| |||