half-exponential function

If a function $f$ is defined using the standard arithmetic operations, exponentials, logarithms, and real-valued constants, then $f\backslash bigl(f(x)\backslash bigr)$ is either subexponential or superexponential.{{r|transseries}} Thus, a Hardy field#Examples cannot be half-exponential.

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 $(0,1)$ and for every continuous strictly increasing function $g$ from $[0,A]$ onto $[A,1]$, there is an extension of this function to a continuous strictly increasing function $f$ on the real numbers such that {{nowrap|$f\backslash bigl(f(x)\backslash bigr)=\backslash exp\; x$.{{r|croneu}}}} The function $f$ is the unique solution to the functional equation

$$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}

File:Half-exponential_function.png

A simple example, which leads to $f$ having a continuous first derivative $f\text{'}$ everywhere, and also causes

$f\text{'}\text{'}\backslash ge\; 0$ everywhere (i.e. $f(x)$ is concave-up,

and $f\text{'}(x)$ increasing,

for all real $x$),

is to take $A=\backslash tfrac12$ and $g(x)=x+\backslash tfrac12$, giving

$$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}

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$ 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.3372357i$), making

Q also be a fixpoint of f, that is $f(Q)=e^Q=Q$,

then computing the Maclaurin series coefficients of $f(x-Q)$ one by one. This results in Kneser's construction mentioned above.

Half-exponential functions are used in computational complexity theory for growth rates "intermediate" between polynomial and exponential.{{r|miltersen}} 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^\{-1\}(x^C)=o(\backslash log\; x)$, for {{nowrap|every $C>0$.{{r|razrud}}}}

• {{annotated link|Iterated function}}
• {{annotated link|Schröder's equation}}
• {{annotated link|Abel equation}}

{{reflist|refs=

{{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}}

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

}}

{{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}}

{{cite journal

| last = Kneser | first = H. | author-link = Hellmuth Kneser

| journal = Journal für die reine und angewandte Mathematik

| 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| doi = 10.1515/crll.1950.187.56 }}

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

}}

• [https://mathoverflow.net/q/12081 Does the exponential function have a (compositional) square root?]
• [https://mathoverflow.net/q/45477 “Closed-form” functions with half-exponential growth]

Category:Analysis of algorithms

Category:Computational complexity theory