Cfrgtkky

Upon writing this post, I had the following natural conjecture:
$
defnn{mathbb{N}}
defrr{mathbb{R}}
$

Take any family ${ C_r : rinrr }$ of functions from $nn$ to $rr$ where $0 < C_s(n) ll C_t(n)$ as $n to infty$ for every $s,t in rr$ such that $s < t$. Then for every $r in rr$ there is some function $D_r$ from $nn$ to $rr$ such that for every $ε in rr^+$ we have $C_r(n) ll D_r(n) ll C_{r+ε}(n)$ as $n to infty$. (By considering the reciprocal family this immediately implies the other side as well.)

Intuitively, I claim that there will always be some asymptotic class that falls between the cracks of any linearly-ordered real-parametrized family of asymptotic classes. I think that this is equivalent to the stronger claim of nowhere-denseness, but I am not sure.

For example:

• If $C_r(n) = n^r$ for every $r in rr$ and $r in nn$, then $D_r$ where $D_r(n) = n^r·ln(n)$ for every $n in nn$ provides a suitable witness, since $n^0 ll ln(n) ll n^ε$ as $n to infty$ for every $ε in rr^+$.




• If $C_r(n) = r^n$ for every $r in rr$ and $r in nn$, then $D_r$ where $D_r(n) = n^r·n$ for every $n in nn$ provides a suitable witness, since $r^0 ll n ll (1+frac{ε}{r})^n$ as $n to infty$ for every $ε in rr^+$.

It is easy to show that $C$ has strict upper and lower bounds since $C_{-n}(n) ll C_r(n) ll C_n(n)$ as $n to infty$ for every $r in rr$. But I cannot find a general way to construct 'in-between' functions. I know that $C_{r+frac1n}(n) ll C_{r+ε}(n)$ as $n to infty$ for every $r in rr$ and $ε in rr^+$, but it is possible that $C_{r+frac1n}(n) sim C_r(n)$, as is indeed the case in both the above examples.

Is my conjecture true? If so, it suffices to prove that $C_0(n) ll D_0(n) ll C_ε(n)$ as $n to infty$ for some function $D_0$ from $nn$ to $rr$, since the general claim follows by translation. If not, it suffices to prove that for some family $C$ there is no such $D_0$, again due to translation.

You can diagonalize to find a sequence asymptotically bigger than $C_{r}$ but asymptotically smaller than $C_{r+epsilon}$ for any $epsilon>0$.

Fix $r$. Define $d_r(n)$ to be the greatest positive integer such that $C_{r+1/j}(n')/C_r(n')ge d_r(n)$ for all positive integer $j le d_r(n)$ and $n'ge n$, or $d_r(n)=1$ if none exists. Take $D_r(n)=C_r(n)d_r(n)$.

For any positive integer $j$, either $j le d_r(n)$ or $d_r(n) le j$, so by construction $D_r(n) le C_{r+1/j}(n)$ or $D_r(n) le j·C_r(n)$ as $n to infty$. Therefore $D_rll C_{r+epsilon}$ for any $epsilon>0.$

I claim that $d_r(n)toinfty$ as $ntoinfty$.
For any fixed positive integer $Delta$, from the conjunction of $C_rll C_{r+1/j}$ for positive integer $j le Delta$, there is a large enough $n$ such that for all $jleDelta$ and $n'ge n$ we have $C_{r+1/j}(n')/C_r(n')geDelta$. For this $n$ we have $d_r(n) ge Delta$. And $d_r$ is clearly non-decreasing. So $d_r$ tends to $infty$. Therefore $C_rll D_r$.