Is there always a superlinear function which "strongly dominates" a given superlinear function? Consider the class $\mathcal{F}$ of functions $f:[0, \infty) \to [0, \infty)$ with the following properties  
$(1)$ $f$ is strictly increasing with $f(0) = 0$.  
$(2)$ $f \in \omega(x)$ as $x \to \infty$. That is to say, $$\lim_{x \to \infty} \frac{f(x)}{x} = \infty$$, or $f$ is superlinear. 
The latter condition ensures that $f(x)$ is much larger than $x$ for large $x$, and hence  iteratively composing any $f \in \mathcal{F}$ with itself any number of times will produce a function which grows at least as fast as $f$ asymptotically. 
Define $$f^{[n]}(x) \stackrel{\text{def}}{=}  (\overbrace{f \circ f \circ f \cdots \circ f}^{n \ \text{times}})(x)$$
For any two $f,g \in \mathcal{F}$, we say $f$ $\textbf{strongly dominates}$ $g$ if for all $n \in \mathbb{N}$, $f \in \omega(g^{[n]}(x)) $ as $x \to \infty$. (this is "strong" domination as opposed to weak domination, which is just $f \in \omega(g)$). 
Problems:

Let $f \in \mathcal{F}$ be arbitrary. Does there exist a $g \in \mathcal{F}$ such that $g$ strongly dominates $f$? Additionally, does there exist an $h \in \mathcal{F}$ such that $f$ strongly dominates $h$? And can both $g,h$ be explicitly constructed? 

 A: My previous comment gives a “yes” answer to the first question.  This answer shows “yes” also is true for the second.  
Fix $f \in \mathcal{F}$.  We want to construct $h \in \mathcal{F}$ such that $f$ strongly 
dominates $h$.  We construct $h$ piecewise linear over a sequence of switching times
$\{S_k\}_{k=0}^{\infty}$ that satisfy 
$$ 0 < S_0 < S_1 < S_2 < S_3 < … $$
and $\lim_{k\rightarrow \infty} S_k = \infty$.  For a given sequence $\{S_k\}_{k=0}^{\infty}$ (to be precisely defined later), define $h:[0,\infty)\rightarrow\mathbb{R}$ by: 
$$ h(x) = \left\{ \begin{array}{ll}
x &\mbox{ if $x \in [0, S_0)$} \\
kx & \mbox{ if $x \in [S_{k-1}, S_k)$, $k \in \{1, 2, 3, ...\}$} 
\end{array}
\right.$$
Claim 1:
For any such sequence $\{S_k\}_{k=0}^{\infty}$, the $h$ function defined above satisfies $h \in \mathcal{F}$. 
Proof:  By construction, $h(0)=0$ and $h$ is increasing. For $x \geq S_0$ we can write
$h(x) = k_x x $, where $k_x$ is defined as the index $k \in \{1, 2, 3, \ldots\}$ such that 
$x \in [S_{k-1},S_k)$. Then
$$\frac{h(x)}{x} = \frac{k_x x}{x} = k_x \rightarrow \infty$$
$\Box$
Claim 2:
If $f \in \mathcal{F}$, then $\sqrt{x f} \in \mathcal{F}$ and 
$$ \lim_{x\rightarrow\infty} \frac{\sqrt{xf(x)}}{f(x)} = 0$$ 
Proof: The function $\sqrt{xf(x)}$ is increasing, sends $0\rightarrow 0$, and
\begin{align}
\frac{\sqrt{xf(x)}}{x} &= \sqrt{f(x)/x} \rightarrow \infty\\
\frac{\sqrt{xf(x)}}{f(x)} &= \sqrt{x/f(x)}\rightarrow 0
\end{align}
where the limits hold because $f(x)/x\rightarrow \infty$.
 $\Box$
Now define $\phi:[0,\infty) \rightarrow\mathbb{R}$ by: 
$$ \phi(x) = \left\{ \begin{array}{ll}
0 &\mbox{ if $x=0$} \\
\inf_{y \in [x, \infty)} \frac{\sqrt{y f(y)}}{y}   & \mbox{ if $x>0$} 
\end{array}
\right.$$
Claim 3:
The function $\phi$ is nondecreasing and satisfies
$$ \lim_{x\rightarrow\infty} \phi(x) = \infty$$
Proof: We have
$$ \lim_{x\rightarrow\infty} \phi(x) = \lim\inf_{x\rightarrow\infty} \frac{\sqrt{xf(x)}}{x}=\infty   $$ 
where the limit holds because $\sqrt{xf(x)}\in \mathcal{F}$ so $\frac{\sqrt{xf(x)}}{x}\rightarrow\infty$.
$\Box$
It remains to choose the sequence $\{S_k\}_{k=0}^{\infty}$ such that the resulting $h$ function is strongly dominated by $f$.  Formally define $S_{-1}=0$. 
For $k \in \{0, 1, 2, …\}$ and with knowledge of $S_{k-1}$, choose $S_k$ as any real 
number that satisfies: 


*

*Property 1: $S_{k-1} < S_k$.

*Property 2: $(k+2)^{k+1} \leq \phi(S_k)$

*Property 3: $S_{k-1}k^{k-1} < S_k$ (only required if $k\geq 2$). 
It is always possible to choose such a sequence $\{S_k\}_{k=0}^{\infty}$. In particular, the condition of the second bullet can be satisfied because $\phi(x)$ is nondecreasing and $\lim_{x\rightarrow\infty} \phi(x) =\infty$ (so we can always choose $S_k$ larger than the thresholds required in Properties 1 and 3 and sufficiently large to satisfy Property 2).   
Claim 4:
Fix $k$ as a positive integer.  If $x \in [S_{k-1}, S_k)$ then 
$$ x(k+1)^k \leq \sqrt{x f(x)}  $$ 
Proof: We have 
\begin{align}
x(k+1)^k &\overset{(a)}{\leq} x\phi(S_{k-1}) \\
&\overset{(b)}{=} x \inf_{y \in[S_{k-1}, \infty)} \frac{\sqrt{y f(y)}}{y}\\
&\overset{(c)}{\leq} x \frac{\sqrt{xf(x)}}{x} \\
&= \sqrt{x f(x)} 
\end{align}
where (a) holds by Property 2 (applied to $k-1 \in \{0, 1, 2, …\}$);
(b)  holds by definition of $\phi$; (c) holds because $x \in [S_{k-1}, \infty)$.
 $\Box$
Claim 5:
Fix $n$ as a positive integer. Fix $x \geq S_{n-1}$.  Let $k$ be the index such 
that $x \in [S_{k-1}, S_k)$ (note that $k\geq n$).  Then 
$$ h^{[n]}(x) \leq x(k+1)^k $$
Proof: Postponed until later (see details below). $\Box$
Claim 6:
The function $f$ strongly dominates $h$.
Proof:  Fix $n$ as a positive integer. Consider any $x \geq S_{n-1}$.  Let $k\geq n$ be the index such that $x \in [S_{k-1}, S_k)$. We have: 
\begin{align}
\frac{h^{[n]}(x)}{f(x)} &\overset{(a)}{\leq} \frac{x(k+1)^k}{f(x)} \\
&\overset{(b)}{\leq}  \frac{\sqrt{x f(x)}}{f(x)} \rightarrow 0
\end{align}
where (a) holds by Claim 5; (b) holds by Claim 4; and the limit holds by Claim 2. $\Box$

Proof of Claim 5: Fix $n$ as a positive integer and fix $x \geq S_{n-1}$.  Let $k \geq n$ be the index such that $x \in [S_{k-1}, S_k)$. Then
$$ (k+1)^k x \leq (k+1)^kS_k < S_{k+1} $$
where the final inequality holds by Property 3 (applied to $k+1 \geq 2$). Thus


*

*$h(x) = kx \leq (k+1)x < S_{k+1}$.  So $h(x) \in [S_{k-1}, S_{k+1})$. 

*$h(h(x)) \leq (k+1)h(x) \leq (k+1)^2x < S_{k+1}$.  So $h(h(x)) \in [S_{k-1}, S_{k+1})$. 

*... and so on... 

*$\underbrace{(h \circ \ldots  \circ h)}_{\mbox{k times}}(x) \leq (k+1)^kx < S_{k+1}$.
$\Box$
