Half-exponential function: Difference between revisions

Revision as of 20:43, 17 May 2022

Revision as of 20:50, 17 May 2022

Line 1:

In [[mathematics]], a '''half-exponential function''' is a [[functional square root]] of an [[exponential function]], that is, a [[function (mathematics)|function]] ''&fnof;''<math>f</math> that, if [[function composition|composed]] with itself, results in an exponential function:<ref name="sqrtexp">{{cite journal

|author=Kneser, H. |authorlink=Hellmuth Kneser

|title=Reelle analytische Lösungen der Gleichung ''&phi;''(''&phi;''(''x''))&nbsp;=&nbsp;''e''^''x'' und verwandter Funktionalgleichungen

Line 8:

|pages=56&ndash;67}}

</ref><ref name="miltersen">{{cite book |author1=Peter Bro Miltersen |author2=N. V. Vinodchandran |author3=Osamu Watanabe |title=Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy |journal=Lecture Notes in Computer Science |volume=1627 |year=1999 |pages=210–220 |doi=10.1007/3-540-48686-0_21|isbn=978-3-540-66200-6 |citeseerx=10.1.1.16.2908 }}</ref>

: <math display=block>f(f(x)) = ab^x.,</math>

for some constants {{nowrap|<math>a</math> and <math>b</math>.}}

==Impossibility of a closed form formula==

: <math>f(f(x)) = ab^x.</math>

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.<ref>{{Cite web | url=https://mathoverflow.net/q/45477 | title=Fractional iteration - "Closed-form" functions with half-exponential growth}}</ref><ref>{{cite web|url=http://www.scottaaronson.com/blog/?p=263#comment-7283 |title=Shtetl-Optimized » Blog Archive » My Favorite Growth Rates |publisher=Scottaaronson.com |date=2007-08-12 |accessdate=2014-05-20}}</ref> Thus, a [[Hardy field#Examples|Hardy ''{{mvar|L''}}-function]] cannot be half-exponential.

==Construction==

If a function ''ƒ'' is defined using the standard arithmetic operations, exponentials, [[logarithm]]s, and [[Real number|real]]-valued constants, then ''ƒ''(''ƒ''(''x'')) is either subexponential or superexponential.<ref>{{Cite web | url=https://mathoverflow.net/q/45477 | title=Fractional iteration - "Closed-form" functions with half-exponential growth}}</ref><ref>{{cite web|url=http://www.scottaaronson.com/blog/?p=263#comment-7283 |title=Shtetl-Optimized » Blog Archive » My Favorite Growth Rates |publisher=Scottaaronson.com |date=2007-08-12 |accessdate=2014-05-20}}</ref> Thus, a [[Hardy field#Examples|Hardy ''L''-function]] cannot be half-exponential.

There are infinitely many functions whose self-composition is the same exponential function as each other. 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(f(x))=\exp x</math>.<ref>{{cite journal

There are infinitely many functions whose self-composition is the same exponential function as each other. 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 ''g'' 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 <math>f(f(x))=\exp x</math>.<ref>{{cite journal

| last1 = Crone | first1 = Lawrence J.

| last2 = Neuendorffer | first2 = Arthur C.

Line 24 ⟶ 26:

| volume = 132

| year = 1988| doi-access = free

}}</ref>}} The function <math>f</math> is the unique solution to the [[functional equation]]

:<math display=block> f (x) =

:<math> f (x) =

\begin{cases}

g (x) & \mbox{if } x \in [0,A], \\

Line 36 ⟶ 37:

[[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 everywhere, is to take <math>A=\tfrac12</math> and <math>g(x)=x+\tfrac12</math>, giving

:<math display=block> f (x) =

:<math> f (x) =

\begin{cases}

\log_e\left(e^x +\tfrac12\right) & \mbox{if } x \le -\log_e 2, \\

Line 51:

</math>

==Application==

Half-exponential functions are used in [[computational complexity theory]] for growth rates "intermediate" between polynomial and exponential.<ref name="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 ''ƒ''<sup>−1</supmath>f^{-1}(''x''^{''^C''})&nbsp;≤&nbsp;=o(\log&thinsp;'' x'')</math>, for {{nowrap|every&nbsp;'' <math>C''&thinsp;>&thinsp;0</math>.<ref>{{cite journal |author1=Alexander A. Razborov |author2=Steven Rudich |title=Natural Proofs |journal=Journal of Computer and System Sciences |volume=55 |issue=1 |date=August 1997 |pages=24–35 |doi=10.1006/jcss.1997.1494|doi-access=free }}</ref>}}

==See also==

*{{annotated link|Iterated function}}

*{{seeannotated alsolink|Iterated function| Schröder's equation|}}

*{{annotated link|Functional square root|Abel equation}}

*{{annotated link|Abel equation}}

{{see also|Iterated function| Schröder's equation|

Functional square root|Abel equation}}

==References==

{{reflist}}