7

I usually don't like to ask questions that are too specific, but I cannot reach the exact final expression.

Lemma A function $f: \mathbb{N} \to \mathbb{C}$ verifies $$|f(n)| \leq \frac{\log{|g(n)|}+\frac{1}{2}\log{\left(\tfrac{h(n) \varepsilon}{4 |r(n)|}\right)}}{-\log{(1-h(n))}}$$ for some specific functions $g: \mathbb{N} \to \mathbb{C}$, $ h,r: \mathbb{N} \to \mathbb{R}$ and $ \varepsilon > 0$.

It is proved that

  • $g(n) = n + O(1/n)$.
  • $h(n) = 1 - \Re{( \lambda(n))}$, where $\lambda(n) = 1 - \frac{\alpha}{n^3} + O(1/n^5)$ for some positive constant $\alpha$ and a complex-valued function $\lambda$ ($\Re{(\cdot)}$ denotes de real part of a complex number).
  • $r(n) = O(1/n^2)$.

It then says that by substituting these values in the previous Lemma we obtain

$$|f(n)| \leq (1- o(1)) \frac{1}{2 \alpha} n^3 \log{(n)}.$$

(little- $o$ here) but I cannot reach this result...

What I have done: By considering the approximation $\log{(1-x)} \approx -x$ for small $x$, we have that $- \log{(1 - h(n))} = h(n)$. Thus

\begin{equation*} \begin{split} |f(n)| \leq \frac{\log{|g(n)|}+\frac{1}{2}\log{\left(\tfrac{h(n) \varepsilon}{4 |r(n)|}\right)}}{-\log{(1-h(n))}} & = \frac{\log{(n + O(1/n))}+\frac{1}{2}\log{\left(\tfrac{\left[ \frac{\alpha}{n^3}+ O(1/n^5)\right] \varepsilon}{4 O(1/n^2)}\right)}}{\frac{\alpha}{n^3}+ O(1/n^5)} \\ & = \left\{\log{(n + O(1/n))}+\frac{1}{2}\log{\left(\tfrac{[1+ O(1/n^2)] \varepsilon}{ O(n)}\right)}\right\}\frac{n^3}{\alpha} \\ & = \left\{\log{(n + O(1/n))}-\frac{1}{2}\log{\left( O(n)\right)}\right\} \frac{n^3}{\alpha} \end{split} \end{equation*}

I know that I'm close but I cannot reach the exact expression with the little-$o$ (and I don't know how they got it) so any help would be appreciated.

Macarena Perelman
  • 73

1 Answers1

1

Your steps don't seem to be precise. Remember $\frac{1}{1 + x} \geq 1 - x$ for $0 < x < 1$.

IMPORTANT: To prove the result, we need $|r(n)| = \Omega(1/n^2)$. Suppose $|r(n)| \geq \frac{\lambda_0}{n^2} $ eventually for some constant $\lambda_0$.

$$ \begin{align*} u(n) &:= \log{\left( \frac{\frac{\alpha\varepsilon}{n^3} + O(1/n^5) \varepsilon}{ 4|r(n)|}\right)} \\ &\leq \log{\left( \frac{\alpha \varepsilon}{4\lambda_0n} + O(1/n^3) \varepsilon\right)} = - \log{\left( \frac{\frac{4\lambda_0n}{\alpha \varepsilon}}{1 + O(1/n^2)} \right)} \\ &\leq -\log{\left( \frac{4\lambda_0n}{\alpha \varepsilon} (1 + O(1/n^2)) \right)} \\ 2v(n) &:= 2\log (n + O(1/n)) \\ &\leq 2\log (n \; (1 + O(1/n^2)) \;) \\ &\leq \log (n^2 \; (1 + O(1/n^2)) \;) \\ v(n) + \frac{1}{2}u(n) &= \frac{1}{2}(2v(n) + u(n)) \\ &\leq \frac{1}{2} \log \Bigg( \frac{n\alpha \varepsilon}{4\lambda_0} \big(\frac{1 + O(1/n^2)}{1 + O(1/n^2)} \big) \Bigg) \\ &\leq \frac{1}{2} \log \Bigg( \frac{n\alpha \varepsilon}{4\lambda_0} \big(1 + O(1/n^2) \big) \Bigg) \\ &\leq \frac{1}{2} \Bigg(\log n + \log\Bigg( \frac{\alpha \varepsilon}{4\lambda_0} \big(1 + O(1/n^2) \big) \Bigg) \Bigg) = \frac{1}{2}( \log n - \log K(n)) \end{align*} $$ where $K(n) = \frac{4\lambda_0}{\alpha\epsilon(1 + O(1/n^2))} > 1 \Rightarrow \log K(n) > 0$ as $\epsilon$ becomes very close to $0$. Thus

$$v(n) + \frac{1}{2}u(n) \leq \frac{\log n}{2}(1 - \frac{\log K(n)}{\log n} )$$

Now, a positive function $f(n)$ is $o(1)$ iff $\lim_{n \rightarrow \infty} f(n) = 0$. All you have to show to complete the result is that $\lim_{n \rightarrow \infty} \frac{\log K(n) }{\log n} = 0$. But this is true as this limit simplifies to $\lim_{n \rightarrow \infty} \frac{1}{n^2 \log n} = 0$.

Note: OP has already shown how to get the $\frac{n^3}{\alpha}$ factor, so I've skipped that part.

Anon
  • 2,460
  • 1
  • 15
  • 23
  • At the beginning, you mean $|r(n)| \geq \frac{\lambda_0}{n^2}$ I assume. Why do you need $\log{K(n)} > 0$? (I know that it is written minus $o(1)$, but isn't $-o(1) = o(1)$?) – Macarena Perelman Mar 31 '21 at 20:23
  • yes. 2. positive (I edited the answer, by bolding a keyword)
    • – Anon Mar 31 '21 at 20:24
  • (I'm giving you +1, just let me think a little bit more before accepting the answer) But why do I need the function to be positive? When I look at the ratio $\frac{h(n) \varepsilon}{4 |r(n)|}$, I see that it is smaller than $1$ (since the numerator is $O(1/n^3)$ and the denominator $O(1/n^2)$. Wouldn't this require $r(n) = O(1/n^2)$ instead of $r(n) = \Omega(1/n^2)$? – Macarena Perelman Mar 31 '21 at 20:29
  • That's just convention of defining $o(1)$. (Although technically you could define it for negative functions) 2. $r(n) = \Omega(\frac{1}{n^2}) \Rightarrow \frac{1}{r(n)} = O(n^2)$.
    • – Anon Mar 31 '21 at 20:34
  • Why did you remove your edit? – Macarena Perelman Mar 31 '21 at 22:06
  • It is supposed to be $\Omega$. I got confused for a while and thought it might be $O$, but that's not true. – Anon Mar 31 '21 at 22:06
  • 1
    I was getting confused as well but yes, we just have to realize that if $0 < a\leq b$ then $\log{(a)} \leq \log{(b)}$ regardless of $b$ being less or more than $1$. – Macarena Perelman Mar 31 '21 at 23:02
  • 1
    But flipping the logarithm at the beginning wouldn't allow us to write (assuming $r(n) = O(1/n^2)$)

    \begin{equation} \begin{split} \log{\left(\frac{h(n) \varepsilon}{4|r(n)|}\right)} & = - \log{\left(\frac{4|r(n)|}{h(n) \varepsilon}\right)} = -\log{\left(\frac{4|r(n)|}{\frac{\alpha \varepsilon }{n^3}( 1 + O(1/n^2))}\right)} \ & = -\log{\left(\frac{4|r(n)| n^3}{\alpha \varepsilon }( 1 + O(1/n^2))\right)} = -\log{\left(\frac{4 n O(1)}{\alpha \varepsilon }( 1 + O(1/n^2))\right)} \end{split} \end{equation}

     – Macarena Perelman Mar 31 '21 at 23:17