1
$\begingroup$

My understanding (which may be at fault for my confusion)

I am currently self studying Bruijn's book "Asymptotic Methods in Analysis". In chapter 1.4: enter image description here

What I understand from this is

$$\lim_{x \to \infty}{\frac{f(x)}{g(x)}} = 1 \iff f \sim g \iff f = g \cdot (1+o(1))$$

The issue

I had no issues with this conclusion until I reached chapter 2.8, exercise 1. I found an answer in this site about this exercise: Asymptotic behavior of the solutions to $\sin x = (\log x)^{-1}$. I had no problem following this answer until the very end. My question is NOT about said exercise. Therefore I will spare you the details, only focusing on the problematic statement which I use as an example to showcase my issue with the topic I am discussing here.

Suppose $z$ is a function of $n$ such that $$z = o(1), \quad (n \to \infty)$$

Then, what is claimed is that $$z + O(z^3) = \frac{1}{\log{n}} + o\Big(\frac{1}{n(\log{n})^2}\Big)$$

implies $$z \sim \frac{1}{\log{n}}$$

To more efficiently discuss my problem with this, let $L_n = (\log{n})^{-1}$. By my understanding, this should mean that $$z = L_n(1+o(1))$$

but $$\frac{z}{L_n} = \frac{L_n+o(L_n^3/n)+O(z^3)}{L_n} = 1 + o(L_n^2/n) + O(z^3/L_n) = 1 + o(1)+ O(z^3/L_n)$$

So, how do we know that $O(z^3/L_n) = o(1)$ ? I have written two different approaches for answering this question, but I am uncertain about both.

First approach to answering why $O(z^3/L_n) = o(1)$

This approach is based on the assumption that we can write $$o(z) = z\cdot o(1)$$ The reason that I am uncertain about it, is that it sidesteps the statement $O(z^3/L_n) = o(1)$, by first showing that $z = L_n(1+o(1))$. So, we can write $$z+O(z^3) = L_n + o(L_n^2/n) \Rightarrow z + o(z) = L_n + o(L_n)$$ $$\Rightarrow z = L_n\Big(\frac{1+o(1)}{1+o(1)}\Big)$$ Then, by the expansion of $(1+x)^{-1}$ about $x=0$, $$z = L_n(1+o(1))(1+o(1)) = L_n(1+o(1))$$ which means, $$O(z^3/L_n) = O(\frac{L_n^3 + o(L_n^3)}{L_n}) = O(L_n^2) = o(1)$$

Second approach to answering why $O(z^3/L_n) = o(1)$

I find this approach more interesting, as it uses the recursive nature of $$z = L_n + o(L_n^2/n)+O(z^3)$$

Assume $O(z^3/L_n) \ne o(1)$. Then $z^3/L_n \notin o(1)$ and therefore $$1 = O(z^3/L_n)$$

We can then write $$O(z^3/L_n) = O(z^2 \cdot z/L_n) = O(z^2 (1 + o(L_n/n) + O(z^3/L_n))) = O(z^5/L_n)$$

We can continue this to conclude that for every integer $N \ge 1$, $$O(z^3/L_n) = O(z^{2N+1}/L_n)$$

and therefore by our assumption, $$z^{2N+1}/L_n \notin o(1), \quad \forall N$$

By itself this last statement probably is not a contradiction. But perhaps it holds true if $z$ is in some specific function space ?(ie in the "elementary" functions)

Then one could attempt to show that z is a member of said function space based on the details of the original question which I omitted

Many thanks!

$\endgroup$
1
  • $\begingroup$ Harmless misprint before your "first approach": it should be $ \frac{z}{L_n} = \frac{L_n+o(L_n^2/n)+O(z^3)}{L_n} = 1 + o(L_n/n) + O(z^3/L_n)$ instead of $ \frac{z}{L_n} = \frac{L_n+o(L_n^3/n)+O(z^3)}{L_n} = 1 + o(L_n^2/n) + O(z^3/L_n).$ $\endgroup$ Sep 13, 2022 at 13:54

1 Answer 1

0
$\begingroup$

Your first approach is correct (except it would be cleaner to write $z_n$ everywhere instead of $z$). The second one has a flaw at "and therefore $1 = O(z^3/L_n)$".

$$a_n\ne o(b_n)\quad\not\Rightarrow\quad b_n=O(a_n).$$

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. If $z^3/L_n\notin o(1)$ then is it not true that asymptotically $z^3/L_n$ will approach a non-zero number $c$ (or $\infty$)? Therefore can we not say that $1 < k \cdot |z^3/L_n|$ with $ k = 2 |c^{-1}| $ for large enough $n$? However in general I do not disagree with your statement $\endgroup$
    – Stamatis
    Sep 14, 2022 at 9:11

You must log in to answer this question.

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