In both cases, it makes sense to express the number of steps needed to find the input as functions $t_{\textrm{CTM}}(d)$ and $t_{\textrm{PTM}}(d)$ of the distance $d$ of the reading head to the input, represented by the (unknown) number of cells between the reading head and the input when we start the CTM.

The CTM spends most of its time zig-zagging to find the input: given $d$, it needs at most $$1+2+3+ \cdots + 2d = \frac{2d(2d+1)}{2}$$ many steps. So $$t_{\textrm{CTM}}(d) \le K \cdot d^2,$$ where $K>0$ is a constant.

In contrast, because PTM involves random events, we want to find an upper bound $B(d)$ of $t_{\textrm{PTM}}(d)$ that holds *with a certain fixed probability $p_0 > 0$*, that is, such that $$t_{\textrm{PTM}}(d) \le B(d)$$ with probability $p_0$, independent of $d$. Once we have found such a probability $p_0$, it then suffices to **run $1/p_0$ many instances of PTM in parallel in order to find the input in at most $B(d)$ many steps with probability 1**. This is the most certainty we can get for a PTM!

The situation is similar for the Quantum Turing Machines (QTM) that we will define. The exercise here is to illustrate how we arrive at such a statement for our input-searching PTM. The corresponding computations for QTMs are similar but possibly more involved, and we will simply cite the corresponding statements without confirming them.

Back to our input-searching PTM: instead of zig-zagging, our PTM uses its random generator to decide whether to move left or right at each step. This makes for a simpler Turing program, and to compare its performance with that of our CTM, we need to determine $p_0$ and corresponding bound $B(d)$ as mentioned above.

To do so, denote by $p(d,n)$ the probability that our PTM finds the input in $n$ steps, assuming it was initially $d$ cells away. There are two easy cases to compute $p(d,n)$:

- if $d=0$, the reading head happens to start out on one of the cells of the input, so $p(d,n) = 1$ for all $n$;
- if $n < d$, then the input is more than $n$ cells away, so $p(d,n) = 0$.

So for our computation, we may assume that $n \ge d > 0$.

Next, we can code each possible movement outcome of our PTM after $n$ steps as as a binary number with $n$ digits, where we use the digit 1 to indicate movement by one cell *towards *the input, and the digit 0 to indicate movement by one cell *away from *the input.

With this coding, a binary $n$-digit number corresponds to a run of our PTM that detects the input, exactly if the number contains at least $d$ more 1s than 0s, which is the same as having at least $\frac{n+d}2$ many digits of 1. So to compute $p(d,n)$, we need to count the number of all binary $n$-digit numbers with at least $\frac{n+d}2$ many digits of 1, and divide that number by the number of all $n$-digit binary numbers (i.e., by $2^n$).

Now, there are exactly $\tbinom{n}{k} = \frac{n!}{k!(n-k)!}$ many binary $n$-digit numbers with exactly $k$ many digits of 1 (the same as there are $k$-element subsets of a set of $n$ elements). Therefore, $$p(d,n) = \frac1{2^n}\sum_{k \ge \frac{n+d}2} \binom{n}{k}.$$ To extract the information of $p_0$ and corresponding bound $B(d)$ is very tricky!

We need some help: We use the observation that the probabilities $p(d,n)$ correspond to so-called *cumulative probabilities* corresponding to partial areas under the curve representing the binomial distribution. This observation gives us the following fact from Probability Theory:

**Theorem** (closed formula lower bound)

If $n \ge 2d$, then $$p(d,n) \ge \frac1{15} \exp\left( -4\frac dn \right).$$

Let’s write $l(d,n)$ for the right-hand side $\frac1{15} \exp\left( -4\frac dn \right)$; this is a closed formula lower bound for $p(d,n)$. It can be much more easily manipulated: for instance, since $-4\frac dn$ is always negative, its exponential is always at most 1, so that $l(d,n) \le \frac1{15}$. On the other hand, if $d$ is fixed and $n$ goes to $\infty$, then $-4\frac dn$ approaches $0$. This means that, for any number $p_0 < \frac1{15}$, there exists some $n_0$ such that $l(d,n) > p_0$ for all $n \ge n_0$.

*Therefore, the Theorem above tells us that we can take $p_0$ to be any number less than $\frac1{15}$. * We will choose $p_0 = \frac1{30}$ to illustrate the remainder of the argument.

The other good thing about the closed form of $l(d,n)$ is that we can solve the inequality $l(d,n) \ge \frac1{30}$ for $n$: doing so yields $n \ge \frac{4d^2}{\log 2}$. Since $\log 2$ is a constant between $0$ and $1$, we can take $$n \ge 4d^2.$$ The right-hand side of this inequality can serve as our $B(d)$: if $B(d) = 4d^2$, then by the above we have $l(d,B(d)) \ge \frac1{30}$, so by the Theorem we also get $p(d,B(d)) \ge \frac1{30}$.

Thus we have proved the following:

**Proposition**

*With probability at least $\frac1{30}$, given an input located $d$ cells away from the reading head, our PTM will detect the input in at most $4d^2$ many steps.*

This is exactly the kind of statement we were looking for, with $p_0 = \frac1{30}$ and $B(d) = 4d^2$. This shows that our PTM is at least as efficient at finding the input as our CTM, since both need $K d^2$ many steps to do so, for some $K>0$.

Could the estimates above be improved to show that our PTM is actually more efficient than our CTM? This would require us to find a lower bound for $p(d,n)$ that grows like $d^r$ for some $r < 2$. Choosing a different number below $\frac1{15}$ for our $p_0$ will not do this, as you can verify. So we would need a better closed formula lower bound—which I have not found.

]]>**First**, let $f = (f_0, \dots, f_k) \in \U^{k+1}$ be such that $f_0 > \cdots > f_k$. We saw that if $f_0 \succ \cdots \succ f_k$, then our construction yields a qaa field $(K_f, e^x \circ \langle f \rangle, T_f)$. Is the condition $f_0 \succ \cdots \succ f_k$ really necessary?

*There exist $l \le k$ and $g_0 \succ \cdots \succ g_l$ in $\langle f \rangle$ such that, with $g = (g_0, \dots, g_l)$, we have $\langle g \rangle = \langle f \rangle$.*

In particular, the sets $e^x \circ \langle f \rangle$ and $e^x \circ \langle g \rangle$ of convergent transmonomials are the same. Moreover, our construction is independent of the particular $g$ obtained in the previous exercise:

*Let $g$ and $h$ be two tuples obtained from Exercise 1. Then $(\K_g,e^x \circ \langle g \rangle, T_g)$ and $(\K_h, e^x \circ \langle h \rangle, T_h)$ are the same.*

In view of this proposition, our construction assigns a unique qaa field $(K_f, e^x \circ \langle f \rangle, T_f)$ to every tuple $f$ in $\U$, and the direct limit of these qaa fields is again $(\K, \la, T)$.

**Second**, how do we get the Admissibility Theorem from the Continuation Theorem?

The Continuation Theorem as stated here is not actually the full statement needed in order to be able to prove it by induction on terms. What we do get from our statement is the following corollary concerning *complex valued* holomorphic continuations (where $H(a) = \{z \in \CC:\ \re(z) > a\}$):

*Let $f \in \I$ be such that $\eh(f) \le -1$. Then there exist $a \ge 0$ and a holomoprhic continuation $\f:H(a) \into \CC$ that maps every standard power domain into every standard power domain; in particular, $e^{-f}$ is bounded on every standard power domain.* $\qed$

We also obtained the following from the Uniqueness Principle:

*Let $g > f$ be simple germs in $\I$. Then $\eh(f \circ g^{-1}) \le 0$.* \qed

So to prove the Admissibility Theorem, we need to work extra in the case $\eh(f \circ g^{-1}) = 0$.

Corollary 1 fails for $f = x^2$: if $U \subseteq \CC$ is a standard power domain, then $U^2 \nsubseteq H(a)$ for every $a \in \RR$; i.e., $e^{-x^2}$ is unbounded on $U$. Indeed, Corollary 1 holds for $f = x^r$ if and only if $r \le 1$.

The full statement of the Continuation Theorem gives the following strengthening of Corollary 1:

*Let $f \in \I$ be such that $\eh(f) \le 0$. *

*There exist**$a \ge 0$ and a holomorphic continuation $\f:H(a) \into \CC$**such that $\frac1\f$ is bounded*.*$|\f(z)| \to \infty$ as $|z| \to \infty$ in $H(a)$.**Assume in addition that $f \prec x^2$. Then $\f(H(a)) \subseteq \CC \setminus (-\infty,0]$, the map $\f$ is bijolomorphic onto $\f(H(a))$, and for $z \in H(a)$ we have*$$\sign(\arg\f(z)) = \sign(\arg z) = \sign(\im z) = \sign(\im\f(z)).$$

In the Admissibility Theorem, we are dealing with germs of the form $f \circ g^{-1}$ in place of the $f$ in the CCT, where $g > f$. So we need to obtain the desired holomorphic continuation properties for $f$ as in the CCT satisfying $f < x$. To do so, we distinguish three cases:

**Case 1:**there exists $\epsilon \in (0,1)$ such that $f \prec x^\epsilon$.**Case 2:**$x^\epsilon \prec f \prec x$ for every $\epsilon \in (0,1)$.**Case 3:**$f \asymp x$.

To illustrate, let’s consider Case 1. For $\alpha \in (0,\pi/2)$ set $S(\alpha):= \{z \in \CC:\ |\arg z| < \alpha\}.$

*Assume that $f \prec x^\epsilon$ for some $\epsilon \in (0,1)$. Then there exists $a \ge 0$ such that $\f(H(a)) \subseteq S(\epsilon \frac\pi2)$.*

*Proof.* Set $h:= \frac{x^\epsilon}f$. Then $h \in \I$, and since $f < x$, we also have $h \prec x^2$. Since $\eh(f) \le 0$ and $\eh(x^\epsilon) \le 0$, we also have $\eh(h) \le 0$. So by the CCT, there exist $a>0$ and a biholomorphic continuation $\h:H(a) \into \h(H(a))$ such that, for $z \in H(a)$, we have $\sign(\arg\h(z)) = \sign(\arg z)$.

After increasing $a$ if necessary, we have $\h = \frac{z^\epsilon}\f$, where $z^\epsilon$ denotes the principle branch of this power function. So if $\arg(z)>0$, we get from the above that $$0 < \arg \frac{z^\epsilon}{\f(z)} = \epsilon\arg(z) – \arg(\f(z)).$$ The case $\arg(z) < 0$ is handled similarly, which proves the lemma. $\qed$

The other two cases are a bit more elaborate, but they are still handled using similar reductions to statement 3 of the CCT.

]]>I describe here the generalization of this construction to arbitrary convergent transmonomials, based on the Continuation Theorem.

A germ $f \in \I$ is **simple** if $\level(f) = \eh(f)$.

For example, every convergent transmonomial is simple, as is every purely infinite germ.

Recall that $$\la := \bigcup_{n \in \NN} \M \circ \log_n$$ is the set of all convergent transmonomials, while $$\U:= \log \circ \la$$ is the set of all purely infinite convergent transseries. We call a germ $f \in \H$ a convergent transmonomial (resp., purely infinite) if its image $T(f)$ is.

The following upper bound is crucial for generalizing our construction:

*Let $f,g \in \I$ be simple. Then* $$\level(f)-\level(g) \le \eh(f \circ g^{-1}) \le \max\{0, \level(f)-\level(g)\}.$$ *in particular, if $\level(f) \le \level(g)$, then $\level(f \circ g^{-1}) \le 0$.*

*Let $\S_0$ be the set of all simple germs in $\I$ of level $0$. Then $\S_0$ is a group under composition.* $\qed$

To generalize our construction, recall its schematic:

$$ \begin{matrix} \RR & \xrightarrow{\text{(UP)}} & \begin{bmatrix} \F_0 \\ e^{-x} \circ (x) \end{bmatrix} \\ & \swarrow \circ\log \swarrow & \\ \begin{bmatrix} \F_1′ \\ e^{-x} \circ (\log) \end{bmatrix} & \xrightarrow{\text{(UP)}} & \begin{bmatrix} \F_1 \\ e^{-x} \circ (x,\log) \end{bmatrix} \\ & \swarrow \circ\log \swarrow & \\ & \vdots & \\ & \xrightarrow{\text{(UP)}} & \begin{bmatrix} \F_{k-1} \\ e^{-x} \circ (x,\log, \dots, \log_{k-1}) \end{bmatrix} \\ & \swarrow \circ\log \swarrow & \\ \begin{bmatrix} \F_k’ \\ e^{-x} \circ (\log, \dots, \log_{k}) \end{bmatrix} & \xrightarrow{\text{(UP)}} & \begin{bmatrix} \F_k \\ e^{-x} \circ (x,\log, \dots, \log_{k}) \end{bmatrix} \\ \end{matrix} $$

In this schematic, each bracket $\begin{bmatrix} \F_i \\ e^{-x} \circ (x,\log, \dots, \log_{i}) \end{bmatrix}$ indicates the field $\F_i$ constructed at stage $i$ whose asymptotic expansions have support generated by the germs $e^{-x} \circ (x,\log, \dots, \log_{i})$. The $\swarrow \circ\log \swarrow$ line indicates shifting this field by composing on the right by $\log$, to obtain the field $\begin{bmatrix} \F_{i+1}’ \\ e^{-x} \circ (\log, \dots, \log_{i+1}) \end{bmatrix}$ on the left of the next lower row. Finally, the $\xrightarrow{\text{(UP)}}$ arrow indicates constructing the next field with asymptotic expansions in the monomials generated by $e^{-x}$ with coefficients in $\F_{i+1}’$, using the Uniqueness Principle, and then replacing each of the coefficients in $\F_{i+1}’$ by their previously constructed asymptotic expansions.

To adapt this schematic to a general tuple $f = (f_0, \dots, f_k) \in \I^{k+1}$ with $f_0 > \cdots > f_k$, it would have to look like this:

$$ \begin{matrix} \RR & \xrightarrow{\text{(UP)}} & \begin{bmatrix} \F_0 \\ e^{-x} \circ (x) \end{bmatrix} \\ & \swarrow \circ \left(f_k \circ f_{k-1}^{-1}\right) \swarrow & \\ \begin{bmatrix} \K_1′ \\ e^{-x} \circ \left(f_k \circ f_{k-1}^{-1}\right) \end{bmatrix} & \xrightarrow{\text{(UP)}} & \begin{bmatrix} \K_1 \\ e^{-x} \circ \left(x,f_k \circ f_{k-1}^{-1}\right) \end{bmatrix} \\ & \swarrow \circ\left(f_{k-1} \circ f_{k-2}^{-1}\right) \swarrow & \\ & \vdots & \\ & \xrightarrow{\text{(UP)}} & \begin{bmatrix} \K_{k-1} \\ e^{-x} \circ \left(x,f_2 \circ f_{1}^{-1}, \dots, f_k \circ f_{1}^{-1}\right) \end{bmatrix} \\ & \swarrow \circ \left(f_1 \circ f_{0}^{-1} \right) \swarrow & \\ \begin{bmatrix} \K_k’ \\ e^{-x} \circ \left(f_1 \circ f_{0}^{-1}, \dots, f_k \circ f_{0}^{-1}\right) \end{bmatrix} & \xrightarrow{\text{(UP)}} & \begin{bmatrix} \K_k \\ e^{-x} \circ \left(x,f_1 \circ f_{0}^{-1}, \dots, f_k \circ f_{0}^{-1}\right) \end{bmatrix} \\ & \swarrow \circ f_0 \swarrow & \\ \begin{bmatrix} \K_{k+1}’ \\ e^{-x} \circ \left(f_0, \dots, f_k\right) \end{bmatrix} &\end{matrix} $$

Provided the construction can be carried out like this for $f$, we then set $\K_f:= \K_{k+1}’$.

To carry out the construction for $f$, it has to satisfy the following two conditions:

- for $1 \le i < j \le k$ and every standard power domain $V$, there exist a standard power domain $U$ and a holomorphic continuation $\f_{ij}$ of $f_j \circ f_i^{-1}$ on $U$ such that $\f_{ij}(U) \subseteq V$;
- for $0 \le i \le k$, the set of transmonomials generated by $e^{-x} \circ \left(f_i \circ f_{i}^{-1}, \dots, f_k \circ f_{i}^{-1}\right)$ is a scale on standard quadratic domains.

The tuple $f$ is called **admissible** if the above two conditions hold.

By Corollary 1 and the Continuation Theorem, the tuple $f$ is admissible whenever each $f_i$ is simple and $\level(f_0) > \cdots > \level(f_k)$ (as is the case for $f_i = \log_i$, for instance). Therefore, we are at least able to extend our construction to the case where each $f_i$ is purely infinite (so that each $e^x \circ f_i$ is a convergent transmonomial) and $\level(f_0) > \cdots > \level(f_k)$.

Our statement of the Continuation Theorem does not appear to allow generalizing the construction to the cases where some of the $f_i$ have the same level. However, our statement is not actually the full statement that can be proved by induction on terms. If one works with the full statement instead, one can prove the

*If each $f_i$ is simple and $f_0 \succ \cdots \succ f_k$, then $f$ is admissible. In particular, if each $f_i \in \U$ and $f_0 \succ \cdots \succ f_k$, then $f$ is admissible.*

We denote by $\langle f \rangle$ the additive real vector space generated by $\{f_0, \dots, f_k\}$. Note that the set of monomials generated by $e^x \circ f$ is then $e^x \circ \langle f \rangle$.

*For each $f \in \U^{k+1}$ such that $f_0 \succ \cdots \succ f_k$, we obtain a qaa field $(\K_f,e^x \circ \langle f \rangle, T_f)$. Moreover, if $g = (g_0, \dots, g_l) \in \U^{k+1}$ is such that $g_0 \succ \cdots \succ g_l$ and $\{f_0, \dots, f_k\} \subseteq \{g_0, \dots, g_l\}$, then the qaa field $(\K_g, e^x \circ \langle g \rangle, T_g)$ extends $(\K_f,e^x \circ \langle f \rangle, T_f)$*.

This means that the system of all qaa fields $(\K_f,e^x \circ \langle f \rangle, T_f)$, with *$f \in \U^{k+1}$ such that $f_0 \succ \cdots \succ f_k,$ *is a directed system. Note that the corresponding direct limit of all monomial space $e^x \circ \langle f \rangle$ is $\la$.

We let $(\K,\la,T)$ be the direct limit of this system of qaa fields.

This last qaa field has the following additional properties:

*The field $\K$ is a Hardy field and $T$ preserves differentiation.**$(\K,\la,T)$ extends both $(\F,L,T)$ and $(\H,\la,T)$.*

The Hardy field $\K$ is not closed under exponentiation. To see this, consider a germ $f \in \K$ with *divergent* Dulac series $T(f) = \sum a_\alpha e^{-\alpha x}$. (There are such almost regular germs, and all almost regular germs are contained in $\K$.) Then $f \cdot \exp_2 \in \K$ as well, and the transseries $T(f \cdot \exp_2) = T(f) \cdot \exp_2$ is divergent and purely infinite. So $\exp \circ T(f \cdot \exp_2)$ is a transmonomial that is *not convergent*, hence is not in the image $T(\K)$. It follows that $\exp \circ (f \cdot \exp_2) \notin \K$.

- Is the Liouville closure of $\K$ also a qaa field? One possible way to answer this may be by giving a positive answer to the next question.
- Is the image $T(\K)$ a transserial Hardy field in the sense of Van der Hoeven?

I introduce real domains in $\LL$ and angular level, and I use these notions to describe holomorphic continuations on $\LL$ of one-variable functions definable in $\Ranexp$.

In this post “definable” means “definable in $\Ranexp$”.

**Definition**

A set $U \subseteq \LL$ is a **real domain** if there exist $a \gt 0$ and a continuous function $f = f_{U}:(a,+\infty) \into (0,+\infty)$ such that $$U = \set{z \in H_\LL(a):\ \left|\arg z\right| \lt f\left(|z|\right)}.$$ In this situation, we also write $U = U_f$.

**Remarks**

- The real domain $U_f$ is definable if and only if $f$ is definable.
- Every real domain is simply connected.

**Examples**

- For $a\gt 0$, the sector $S_\LL(a)$ is a definable real domain, while the half-plane $H_\LL(a)$ is not a real domain (but is definable).
- Of special interest to us are the
**standard power domains**$U^\epsilon_C = (\pi_0)^{-1}\left(\Omega^\epsilon_C\right)$, where $$\Omega^\epsilon_C := \set{z + C (1+z)^\epsilon:\ \re z \gt 0}$$ for some $C \gt 0$ and $\epsilon \in (0,1)$.

Indeed, these standard power domains are examples of the following type of real domains:

**Definition**

A set $U \subseteq \LL$ is a **strictly real domain** if there exists a continuous function $f:(a,+\infty) \into (0,+\infty)$ such that $U = (\pi_0)^{-1}(\Omega)$ with $$\Omega = \set{z \in \CC:\ |\im z| \lt f(\re z)}.$$

Below, recall that $\H$ denotes the Hardy field of $\Ranexp$. Similarly to working with germs at $+\infty$ of definable functions, we work with germs at $\infty$ of domains in $\LL$.

**Definition**

Two sets $X,Y \subseteq \LL$ are called **equivalent at $\infty$** if there exists $R>0$ such that $X \cap H_\LL(R) = Y \cap H_\LL(R)$. The corresponding equivalence classes are called the **germs at $\infty$** of subsets of $\LL$.

Thus, for $h \in \H_{\gt 0}:= \set{h \in \H:\ h\gt 0}$, we denote by $U_h$ the germ at $\infty$ of any real domain $U_g$ such that $g$ is a representative of $f$.

**Remark**

If $f,g \in \H_{\gt 0}$ are such that $f \lt g$ and $U_g$ is strictly real, then $U_f$ is strictly real. So we set $$\Hsr := \set{h \in \H_{\gt 0}:\ U_h \text{ is strictly real}},$$ a downward closed subset of $\H_{\gt 0}$.

We are not only interested in the holomorphic continuations of definable functions per se, but also in the image of (definable) real domains under these continuations.

**Lemma 1***By direct calculation, we obtain:*

*For $r\gt 0$ and a definable real domain $U$, the images $\p_r(U)$ and $\m_r(U)$ are definable real domains.**For a definable real domain $U$, the image $\llog(U)$ is a definable strictly real domain.**For a definable strictly real domain $U$, the image $\eexp(U)$ is a definable real domain.*

The lemma implies that there are functions $$\nu_{p_r}, \nu_{m_r}:\H_{\gt 0} \into \H_{\gt 0},$$ for $r\gt 0$, and $$\nu_{\log}:\H_{\gt 0} \into \Hsr$$ and $$\nu_{\exp}:\Hsr \into \H_{\gt 0}$$ such that, for $f \in \E$ where $$\E:= \{\log,\exp\} \cup \{p_r:\ r \gt 0\} \cup \{m_r:\ r \gt 0\},$$ and for all appropriate $h \in \H_{\gt 0}$, we have $$\f\left(U_h\right) = U_{\nu_{f}(h)}.$$

However, while $\nu_{p_r}$ and $\nu_{m_r}$ are easy to compute (exercise!), the function $\nu_{\log}$ is a bit harder to figure out (see below). Still, some basic tame calculus observations show the following:

**Lemma 2***The maps $\nu_{f}$ are order-preserving bijections and, for $f,g \in \E$ and appropriate $h \in \H_{\gt 0}$, we have* $$(\f \circ \g)(U_h) = U_{\nu_{f}(\nu_{g}(h))}.$$

Iterating this observation, we let $\E^\circ$ be the set of all finite words $f_1 \circ \cdots \circ f_n$ with each $f_i \in \E$, and we obtain the following:

**Corollary***For each $f \in \E^\circ$, there exist downward closed subsets $\H_1(f), \H_2(f) \subseteq \H_{\gt 0}$ and an order-preserving bijection $\nu_{f}:\H_1(f) \into \H_2(f)$ such that $$\f(U_h) = U_{\nu_{f}(h)}$$ for $h \in \H_1(f)$. Moreover, for $f,g \in \E^\circ$, we have (as germs at $0^+$) $$\nu_{f \circ g} = \nu_{f} \circ \nu_{g}.$$*

**Remark**

A similar statement, with the set $$\I := \set{f:\ \lim_{t \to +\infty} f(t) = +\infty}$$ of all **infinitely increasing** germs in $\H$ in place of $\E^\circ$, is false. Indeed, the continuation $\t_a$ of the translation $t_a$ maps certain definable real domains to domains that are neither real nor definable.

Next, I introduce a rough measure of size for a real domain $U_f$, based on the level of its boundary function $f$.

Let $\I$ be the set of all infinitely increasing $\,f \in \H$ and set $\bo:= \H_{\gt 0} \setminus \I$.

By a theorem of Marker and Miller, every $f \in \I$ has **level**, that is, there exist $k,l \in \ZZ$ such that $$\log_l \circ f \sim \log_{l-k},$$ where $h_1 \sim h_2$ if and only if $h_1(t)/h_2(t) \to 1$ as $t \to +\infty$. In this situation, $k$ is unique and called the **level** of $\,f$, and $\log_s \circ f \sim \log_{s-k}$ for $s \ge l$.

We extend the level to all of $\H_{>0}$ as follows: we set $$\D := \set{1/f:\ f \in \I},$$ and for $f \in \D$, we set the $$\level(f):= \level(1/f).$$ Furthermore, for $\,f \in \H_{\gt 0} \setminus \{\I \cup \D\}$, we set $\level(f):= -\infty$.

**Fact** (Marker and Miller)*Let $\,f,g \in \H_{\gt 0}$.*

*If $\,f,g \in \I$ and $f \le g$, then $\level(f) \le \level(g)$.**If $\,f,g \in \bo$ and $f \le g$, then $\level(f) \ge \level(g)$.**If $\,g \in \I$, then $\level(f \circ g) = \level(f) + \level(g)$.**$\level(fg) \le \max\{\level(f),\level(g)\}$; equality holds whenever $\level(f) \ne \level(g)$.*

For $f \in \I$, show that $\level(f) = \eh(\lm(f)) \le \eh(f)$, where $\lm(f)$ denotes the leading monomial of the transseries $T(f)$.

Given $\,f \in \H_{\gt 0}$ and a word $w \in \E^\circ$, how do the levels of $f$ and of $\nu_w(f)$ compare?

**Example**

If $w = p_r$ or $w = m_r$, for $r>0$, then $\level(f) = \level(\nu_w(f))$.

Things get a little more interesting for $w = \log$:

*Let $f \in \D \cdot \log$. Then there exists $u \in \H_{>0}$ such that $u \sim 1$ and* $$\nu_{\log}(f) \sim \frac{f}{\log} \circ e^{xu}.$$

*Proof.* Since $\frac f\log \in \D$ and $\arctan(x) -= x+o(x)$ as $x \to 0$, we get $$\theta:= \theta(f) \sim \frac f\log \quad\text{and}\quad \rho:= \rho(f) \sim \log.$$ So there exists $v \in \H_{>0}$ such that $v \sim 1$ and $\rho = \log \cdot v$. Composing oin the right with $\rho^{-1}$ (the compositional inverse of $\rho$) gives $$x = \left(\log \circ \rho^{-1}\right) \cdot \frac1u,$$ where $u \in \H_{>0}$ is such that $u \sim 1$. So $\rho^{-1} = e^{xu}$; it follows from the exercise that $$\nu_{\log}(f) = \theta \circ \rho^{-1} \sim \frac f\log \circ \rho^{-1} = \frac f\log \circ e^{xu},$$ as claimed. $\qed$

**Corollary***For $\,f \in \H_{\gt 0}$, we have* $$\level(\nu_{\log}(f)) \begin{cases} = \level(f/\log)+ 1 &\text{if } f \in \D\cdot \log, \\ -\infty &\text{otherwise.} \end{cases}$$

*Proof.* If $f > \D\cdot\log$, then $\arctan(f/\log) \in \H_{>0}\setminus\D$, so $\nu_{\log}(f) \in \bo\setminus\D$ by the exercise. $\qed$

In view of this corollary, we make the following

**Definition**

For $k \in \ZZ$, set $$\D_k:= \set{f \in \D:\ \level(f) = k}$$ and $$\D_{\ge k}:= \set{f \in \D:\ \level(f) \ge k}.$$ We also set $$\J:= \H_{>0} \setminus (\D_{\ge 1}\cdot \log).$$

- $\D_{-1} \subseteq \D_{-1} \cdot \log$ and $\D_0 \cap \D_{-1}\cdot\log = \emptyset$; in particular, the sets $\J$, $\D_{-1}\cdot\log$ and $\D_{\ge 0}$ form a partition of $\H_{>0}$.
- $\nu_{\log}(\J) \subseteq \D_{-1}\cdot\log$.
- $\nu_{\log}(\D_{-1}\cdot\log) = \D_0$.
- $\nu_{\log}(\D_k) = \D_{k+1}$ for $k \in \NN$.

Based on this exercise, the **angular level** $\alevel:\H_{\gt 0} \into \{-1, 0, \dots \}$ is defined as $$\alevel(f):= \max\{-1,\level(\nu_{\log}(f)\}.$$

Combining the Fact and the Lemma, we obtain:

**Proposition***The angular level is decreasing and, for $\,f \in \H_{\gt 0}$, we have*

*$\alevel(\nu_{p_r}(f)) = \alevel(\nu_{m_r}(f)) = \alevel(f)$, for $r>0$;**$\alevel(\nu_{\log}(f)) = \alevel(f) + 1$;**if $\,f \in \Hsr$, then $\alevel(\nu_{\exp}(f)) = \alevel(f)\ – 1$.*$\qed$

**Corollary***Let $\,w \in \E^\circ$, and let $f$ be in the domain of $\nu_w$. Then $$\alevel(\nu_w(f)) = \alevel(f)\ – \level(w). \qed$$*

In order to describe the continuation properties of general $f \in \H$, we need to relax the notion of (definable) real domain, while keeping in mind the scale provided by the angular level.

**Definition**

Let $\lambda \in \ZZ$, $U,V \subseteq \LL$ be domains and $\phi:U \into V$.

- $U$ is a
**$k$-domain**if there exist $\,f,g \in \H_{>0}$ of angular level $k$ such that $U_f \subseteq U \subseteq U_g$. - $\phi$ has
**angular level $\lambda$**if $U$ is an $l$-domain for some $l \ge -1$ and, for $k \ge \max\{\lambda -1,l\}$ and every $k$-domain $U’ \subseteq U$, the image $\phi(U’)$ is a $(k-\lambda)$-domain.

- $\m_r$ and $\p_r$ hacve angular level 0, $\eexp$ has angular level $-1$ and $\llog$ has angular level $1$.
- $\t_a$ has angular level $0$.
- Let $w \in \E^\circ$ of level $\lambda = \eh(w)$, and set $\eta:= \max\{\lambda,0\}$. Then, by the earlier observations, it follows that there exists an $(\eta-1)$-domain $U \subseteq \LL$ and an injective holomorphic continuation $\w:U \into \LL$ such that $\w$ has angular level $\lambda$.

It is this way of describing the extension properties of words in $\E^\circ$ that works for general definable $f$:

**Continuation Theorem***Let $\,f \in \I$ and set $\eta:=\max\{\eh(f),0\}$ and $\lambda:= \level(f) \le \eta$. Then there exist an $(\eta-1)$-domain $U$, and $(\eta-\lambda-1)$-domain $V$ and a biholomorphic continuation $\f: U \into V$ of $\,f$ of angular level $\lambda$.*

How optimal are these holomorphic extensions? Using the Uniqueness Principle and the Continuation Theorem, we obtain a converse of the latter:

**Proposition***Let $\,f \in I$ and $\,\eta \in \NN$, and assume that $\,f$ has a holomorphic continuation $\,\f:U \into H_{\LL}(a)$, where $U \subseteq \LL$ is an $(\eta-1)$-domain and $a > 0$. Then $\eh(f) \le \eta$.*

*Let $f \in \I$ and set $\eta:= \max\{\eh(f),0\}$ and $\lambda:= \level(f)$. Then* $$-\lambda \le \eh(f^{-1}) \le \eta-\lambda.$$

*Proof.* Let $\f:U \into V$ be a biholomorphic continuation of $f$ of angular level $\lambda$ obtained from the Continuation Theorem. Then $\f^{-1}$ is a continuation of $f^{-1}$, and since $U \subseteq H_{\LL}(a)$ for some $a>0$ and $U$ is an $(\eta-\lambda-1)$-domain, the corollary follows from the proposition. $\qed$

We are interested in holomorphic continuations of one-variable functions definable in $\Ranexp$. Since $\exp$ and $\log$ are two crucial functions definable in $\Ranexp$, the natural domain on which to consider holomorphic continuations of all definable functions is the Riemann surface of the logarithm $$\LL:= (0,\infty) \times \RR$$ with its usual covering map $$\pi:\LL \into \CC \setminus {0}$$ defined by $\pi(r,\theta) = re^{i\theta}$. We let $$\left|(r,\theta)\right|:= r$$ be the **modulus** and $$\arg(r,\theta):= \theta$$ be the **argument** of $(r,\theta) \in \LL$. We also denote by $\Log:\LL \into \CC$ the biholomorphic map $$\Log x:= \log|x| + i \arg x,$$ and by $\Exp:\CC \into \LL$ its inverse.

Finally, we set $$d(x,y):= \max{||x|-|y||, |\arg x -\arg y|}$$ and $$B(x,s):= \set{y \in \LL:\ d(x,y) \lt s}.$$

**Remarks**

- One drawback of $\LL$ is that addition does not extend globally on $\LL$. However, the map $\Log$ gives $\LL$ the structure of a holomorphic manifold, thereby giving meaning to the term “holomorphic function” on $\LL$.
- Since $\pi = \exp \circ \Log$, one might simply work in the “logarithmic chart” on $\CC$ instead of in $\LL$. However, describing the continuation properties of functions in the logarithmic chart really means describing the continuation properties of their compositions with $\log$, which is not what we want in the end. On the other hand, we do need to work in the logarithmic chart of $\CC$ whenever we have to compute with derivatives of functions on $\LL$.
- While $\LL$ and $\Log$ are clearly definable, the projection $\pi$ is not; indeed, any restriction of $\pi$ to a domain in $\LL$ on which $\arg x$ is unbounded is not definable.

**Example:** Holomorphic continuation on $\LL$ of power functions.

For real $r\gt 0$, we define the **power function** $\p_r:\LL \into \LL$ by $$\p_r(s,\theta):= (s^r,r\theta)$$ and the **scalar multiplication** $\m_r:\LL \into \LL$ by $$\m_r(s,\theta):= (rs,\theta).$$ Note that these continuations are definable and injective, hence biholomorphic.

**Definition**

For $a\gt 0$ we define the **half-plane** $$H_\LL(a):= \set{x \in \LL:\ |x| \gt a}$$ and the **sector** $$S_\LL(a):= \set{x \in \LL:\ |\arg x| \lt a}.$$ Note that the restriction $$\pi_0:= \pi\rest{S_\LL(\pi)}:S_\LL(\pi) \into \CC \setminus (-\infty,0]$$ is biholomorphic and definable.

**Example:** Holomorphic continuations on $\LL$ of $\log$ and $\exp$.

If $\log$ also denotes the standard branch of the logarithm on $\CC \setminus (-\infty,0]$, then we have $$\Log(x) = \log(\pi(x)), \quad\text{for } x \in S_\LL(\pi).$$ So we define $\llog:\LL \setminus (0,1) \into S_\LL(\pi)$ by $$\llog(x) := (\pi_0)^{-1}(\Log(x)),$$ and we define $\eexp: S_\LL(\pi) \into \LL \setminus (0,1)$ by $\eexp := \llog^{-1}$. Note in particular that $$\llog\left(H_\LL(1)\right) = S_\LL(\pi/2).$$ Note again that these continuations are biholomorphic and definable.

A general observation about holomorphic continuations on $\LL$ arises out of the existence of branches of $\log$ (see e.g. Theorem 13.11 in Rudin’s book):

**Lemma***Let $U \subseteq \CC \setminus {0}$ be a domain and $f:U \into \CC \setminus{0}$ be holomorphic, and assume that $\pi^{-1}(U)$ is simply connected. Then $f$ lifts to a unique holomorphic $\f:\pi^{-1}(U) \into \LL$ such that $f \circ \pi = \pi \circ \f$.*

**Examples** arising from the lemma:

- $f \in \CC[X,1/X]$ and $U= D(a)$, where $a\gt 0$ is such that $Z(f):= \set{z \in \CC:\ f(z) = 0} \subseteq B_a(0)$ and $$D(a):= \set{z \in \CC:\ |z|\gt a}.$$
- For $a \in \RR$, the injective map $t_a: D(|a|) \into \CC \setminus \{0\}$ defined by $t_a(z):= z+a$. Note that, in this case, the corresponding lifting even extends to a biholomorphic map $$\t_a:\LL \setminus \pi^{-1}(-a) \into \LL \setminus \pi^{-1}(a)$$ with compositional inverse $\t_{-a}$.
- $f \in \Pc{R}{X}$ is nonzero, and $a>0$ is sufficiently small such that $F(z) \ne 0$ for $z \in U:= B_a(0) \setminus \{0\}$. In this situation, if $f(0) = 0$, then $$\left|\f(x)\right| \to 0 \text{ as } |x| \to 0;$$ while if $f(0) = a \ne 0$, then $$d\left(\f(x),a\right) \to 0 \text{ as } |x| \to 0.$$

**Final remark**

The holomorphic continuations discussed here are not always definable. For instance, the translation $\t_a$ in Example 2 above is not definable because, for instance, it maps the line ${\arg x = 2a}$ to an infinitely oscillating curve.