The minimal growth rate of the countable family of sequences

Question

Let us consider a countable set of sequences of positive numbers $\{(x_n^{(1)}),(x_n^{(2)}),\dots\}$ for which we have

• $(\forall k\in\mathbb{N}) \ \lim_n x_n^{(k)} = +\infty$, and
• $(\forall k\in\mathbb{N}) \ \lim_n\frac{x_n^{(k+1)}}{x_n^{(k)}}=0$ (the growth rate of the sequences is in the descending order).

My question is the existence of a minimal element, i.e. is there a sequence of positive numbers $(y_n)$ such that $\lim_n y_n=+\infty$ and for every $k\in\mathbb{N}$ we have $\lim_n\frac{y_n}{x_n^{(k)}}=0$?

Of course, any bounded sequence satisfies the second condition, but that is not satisfactory to me.

An example of the above situation where the existence of $(y_n)$ is obvious is $x_n^{(k)}=n^{\frac{1}{k}}$, where we can take $y_n=\ln n$.

Answer 1

Joel's answer gives the history of the result, and Fan Zheng's comment gives a one-word proof, "diagonalization", but it might be worthwhile to make the argument more explicit. The strategy for defining the sequence $(y_n)$ is to make it a sequence of integers that is monotone non-decreasing but grows very slowly. That is, $y_n$ will be 1 for $1\leq n<j_1$, and then it will be 2 for $j_1\leq n<j_2$, then 3 for $j_2\leq n<j_3$, and so forth. The intervals of constancy, $[j_i,j_{i+1})$, will be chosen to be quite long, so that the sequence $(y_n)$ increases very slowly, but notice that this sequence will tend to infinity. What remains is to make sure that $y_n$ is o$(x^{(k)}_n)$ for every $k$, and that will be achieved by choosing the $j$'s large enough. Specifically, $j_m$, the place where the $(y_n)$ sequence jumps from $m$ to $m+1$, should be chosen to be a number $j$ so large that, for all $k\leq m$ and all $n\geq j$, $x^{(k)}_n>(m+1)^2$. Of course, such a $j$ exists because each of the $x^{(k)}$ sequences tends to infinity. (The square of $(m+1)$ here could be replaced with any other exponent $>1$, or indeed with anything that ensures that the value of $x^{(k)}_n$ is way bigger than the new value $m+1$ in the $y$-sequence.) What this choice of the $j_m$'s achieves is that, for any fixed $k$, you'll have $y_n$ way smaller than $x^{(k)}_n$ once $n$ is past $j_k$. Therefore, $y_n$ is o$(x^{(k)}_n)$, as required.

Answer 2

The answer is yes, and this question is strongly related to the topic of Hausdorff gaps.

You have specified a sequence of functions $x^{(k)}$ that is decreasing modulo finite with respect to the coordinate-wise order on $\mathbb{R}^\omega/\text{Fin}$. We write $f<^*g$ to mean that $f(n)<g(n)$ for all but finitely many $n$. For each $k$, you have $x^{(k+1)}_n< x^{(k)}_n$ for all but finitely many $n$, and so $x^{(k+1)}<^*x^{(k)}$. Furthermore, if we let $z^{(k)}_n=k$ for all $n$ and $k$, we have what is called an $(\omega,\omega)$-(pre)gap, because for any $k$ we have $$z^{(k)}_n<z^{(k+1)}_n<\cdots<x^{(k+1)}_n<x^{(k)}_n$$ for all sufficiently large $n$. So we have an increasing sequence below converging upward to the gap and decreasing sequence above converging downward to the gap (using the order on functions modulo finite).

Hausdorff proved that in this situation, there is a function $n\mapsto y_n$ that fills the gap (and you can find explicit constructions of the gap-filling functions; Andreas provides one). (There are continuum many such functions, and no single optimal one.) So we have for each $k$ that $k<y_n<x^{(k+1)}_n$ for all but finitely many $n$. And this ensures your desired hypotheses.