3
$\begingroup$

Upon writing this post, I had the following natural conjecture: $ \def\nn{\mathbb{N}} \def\rr{\mathbb{R}} $

Take any family $\{ C_r : r\in\rr \}$ 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.

$\endgroup$
4
  • $\begingroup$ You'll want to look at Gordon Fisher's 1981 paper The infinite and infinitesimal quantities of du Bois-Reymond and their reception and Hausdorff gaps (see this survey). $\endgroup$ Jan 16, 2018 at 17:56
  • $\begingroup$ @DaveL.Renfro: If you have an answer to my question, could you kindly post an answer that doesn't rely on links or articles hidden behind a great paywall? Thank you! $\endgroup$
    – user21820
    Jan 17, 2018 at 2:02
  • $\begingroup$ I've been too busy at work lately (non-academic) to spend time trying to dig into this topic, but maybe the following will help. First, even if you can't visit a library to access the Gordon Fisher paper (my copy is a photocopy I made back in the late 1980s; I don't have online access either), the title of the paper itself provides words and phrases you can use in searches for relevant work and for books/papers that cite Fisher's paper. Second, Math Origins: Orders of Growth at the MAA website should be useful. $\endgroup$ Jan 23, 2018 at 11:11
  • $\begingroup$ @DaveL.Renfro: Thanks for that! I'm too busy these few weeks to have time for mathematical research, but I'll try to get to them eventually. I took a look at the last link you provided, and I already know everything on that page, I think. $\endgroup$
    – user21820
    Jan 23, 2018 at 14:32

1 Answer 1

2
+50
$\begingroup$

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_r\ll C_{r+\epsilon}$ for any $\epsilon>0.$

I claim that $d_r(n)\to\infty$ as $n\to\infty$. For any fixed positive integer $\Delta$, from the conjunction of $C_r\ll C_{r+1/j}$ for positive integer $j \le \Delta$, there is a large enough $n$ such that for all $j\le\Delta$ and $n'\ge n$ we have $C_{r+1/j}(n')/C_r(n')\ge\Delta$. 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_r\ll D_r$.

$\endgroup$
1
  • $\begingroup$ Thanks! I edited to add a bit of missing detail. =) $\endgroup$
    – user21820
    Dec 29, 2018 at 17:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .