1
$\begingroup$

The following question was asked at https://mathoverflow.net/questions/360053/asymptotic-growth-bound-on-a-sequence-equivalent-to-an-asymptotic-growth-bound-o, but then deleted by the user:

I posted the following question on [Math Stack Exchange][1] on April 2, where it's been unanswered for over a month. I hope the good denizens of Overflow will allow me to migrate it here in hope of an answer or some advice on where to look further.

Question:

Let $(a_n)$ and $(b_n)$ be sequences of positive real numbers. Denote by $o$ the "little-oh" Landau symbol. Is it possible, in general, to find a third sequence $(c_n)$ such that $\sum_{k=0}^n a_k = o(b_n)$ if and only if $a_n = o(c_n)$? Is there a formula for such a $(c_n)$ in terms of $(a_n)$ and $(b_n)$?

It's also possible that some generalization of classical asymptotic analysis can be used to obtain a result in the same spirit, and I'm interested in hearing if this is so.

[1]: https://math.stackexchange.com/questions/3606416/asymptotic-growth-bound-on-a-sequence-equivalent-to-an-asymptotic-growth-bound-o

I think this question may make sense. Below is the answer to it.

$\endgroup$

1 Answer 1

1
$\begingroup$

The answer is yes or no, depending on how the quantifiers are placed.

If the question is this: Is it true that

$\forall (a_n)\ \forall (b_n)\ \exists (c_n)\ \ \big[\sum_{k=0}^n a_k=o(b_n)\iff a_n = o(c_n)\big]$?

then the answer is yes. Everywhere here, $(a_n),(b_n),(c_n)$ are sequences of positive real numbers.

Indeed, for any such $(a_n)$ and $(b_n)$, for all $n$ just let $c_n:=na_n$ if $\sum_{k=0}^n a_k=o(b_n)$ and $c_n:=a_n$ otherwise.


More interesting is this question: Is it true that

$\forall (b_n)\ \exists (c_n)\ \forall (a_n)\ \ \big[\sum_{k=0}^n a_k=o(b_n)\iff a_n=o(c_n)\big]$?

Here the answer is no. Indeed, suppose that, to the contrary, the latter highlighted statement holds. For all natural $n$ let $$b_n:=n\ln n.$$

Then I claim that for any $(c_n)$ such that \begin{equation*} \forall (a_n)\ \ \big[\sum_{k=0}^n a_k=o(b_n)\iff a_n=o(c_n)\big] \tag{0} \end{equation*} we have \begin{equation*} c_n>\sqrt n \end{equation*} eventually, that is, for all large enough $n$. Indeed, suppose otherwise: that for some natural $n_1<n_2<\cdots$ and all natural $j$ \begin{equation*} c_{n_j}\le\sqrt{n_j}. \tag{1} \end{equation*} For all natural $k$, let now \begin{equation*} a_k:=\sum_{i=1}^\infty\sqrt{n_{i^2}}\,I\{k=n_{i^2}\}, \end{equation*} where $I\{\cdot\}$ denotes the indicator. That is, $a_k=\sqrt{n_{i^2}}$ if $k=n_{i^2}$ for some natural $i$, and $a_k=0$ otherwise. Then \begin{equation*} \sum_{k=0}^n a_k =\sum_{i=1}^\infty\sqrt{n_{i^2}}\,I\{n_{i^2}\le n\} \le\sum_{i=1}^\infty\sqrt n\,I\{i^2\le n\}\le n=o(b_n). \end{equation*} So, by (0), $a_n=o(c_n)$, whence \begin{equation*} \sqrt{n_{i^2}}=a_{n_{i^2}}=o(c_{n_{i^2}})=o(\sqrt{n_{i^2}}), \end{equation*} by (1). This contradiction proves that indeed $c_n>\sqrt n$ eventually.

So, letting now $a_n:=\sqrt n/\ln(n+1)$, we have the condition $a_n=o(c_n)$ satisfied. However, here \begin{equation*} \sum_{k=0}^n a_k\sim\tfrac23\, n^{3/2}/\ln(n+1), \end{equation*} which is not $o(b_n)$. Thus, the second highlighted statement is false.

$\endgroup$
4
  • $\begingroup$ For the yes version above, it looks like cn is defined to give the complementary result. Gerhard "Would Like Some Further Explanation" Paseman, 2020.05.11. $\endgroup$ Commented May 11, 2020 at 20:20
  • $\begingroup$ @GerhardPaseman : It seems to me everything is correct there. E.g., if $a_k\equiv1$ and $b_n\equiv n^2$, then we take $c_n:=na_n=n$, and the equivalence $\iff$ holds. If $a_k\equiv1$ and $b_n\equiv n$, then we take $c_n:=a_n=1$, and the equivalence $\iff$ again holds. How do you get a complementary result? $\endgroup$ Commented May 11, 2020 at 21:36
  • $\begingroup$ It looks like I was thinking upper bounds, not asymptotics. You are right about the definition of cn. I am wondering though if you need a quantification over all n in your statement. Gerhard "Thanks For Your Checking In". Paseman, 2020.05.11. $\endgroup$ Commented May 11, 2020 at 21:41
  • $\begingroup$ Instead of the plain quantification over all $n$, the original question had $o(\cdot)$ asymptotics, which of course involves a $\forall\exists\forall$-type quantification. $\endgroup$ Commented May 11, 2020 at 21:56

You must log in to answer this question.

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