Does $\log_{2}(n)=\Omega(\sqrt{n})$ imply $n^2 = \Omega(2^n)$?

Question

I'm having some trouble trying to prove $\log_{2}(n) \neq \Omega(\sqrt{n})$. I'm trying to do this without using limits.

I am able to prove $n^2 \neq \Omega(2^n)$, so if $\log_{2}(n)=\Omega(\sqrt{n}) \Rightarrow n^2 = \Omega(2^n)$ then I think I can use the contrapositive to disprove $\log_{2}(n) = \Omega(\sqrt{n})$.

The reason I think $\log_{2}(n)=\Omega(\sqrt{n}) $ implies $ n^2 = \Omega(2^n)$ is because $\log_{2}{n}$ has an integer solution $k$ at every $n=2^k$ while $\sqrt{n}$ has an integer solution $k$ at every $n=k^2$. So for $\log_{2}{n}$ to be in $\Omega(\sqrt{n})$, the distance between integer solutions for $\sqrt{n}$ would have to grow more quickly than the distance between integer solutions for $\log_{2}{n}$.

Is my reasoning valid?

Edit:

To prove that $n^2 \neq \Omega(2^n)$, I first assume it is true. So I assume the following is true:

$$\exists c \exists n_0 \forall n(n > n_0 \to n^2 \geq c \cdot 2^n)$$

Then I move the pieces of the inequality around a bit,

$$n^2 \geq c \cdot 2^n \Rightarrow 2\log{n} \geq \log{c} + n \Rightarrow 2 \geq \frac{\log{c}}{\log{n}} + \frac{n}{\log{n}}$$

So $(n > n_0) \to (2 \geq \frac{\log{c}}{\log{n}} + \frac{n}{\log{n}})$

I let $a = \max(2^{6-\log{c}}, c, n_0) + 7$, and $b=(a+3)^2$. Therefore, $b > a > n_0$, so the following should be true:

$$2 \geq \frac{\log{c}}{\log{b}} + \frac{b}{\log{b}}$$

To show that it is not true, I do the following:

For $0 < c < 1$: $$(\log{c} < 0) \land (\log{b} > 0) \land (|\log{b}| > |\log{c}|) \to -1 < \frac{\log{c}}{\log{b}} < 0$$

For $c \geq 1$:

$$(b > c) \to (\log{b} > \log{c}) \to 0 \leq \frac{\log{c}}{\log{b}} < 1$$

Therefore, for $c > 0$:

$$-1 < \frac{\log{c}}{\log{b}} < 1$$

Which means that:

$$-1 + \frac{b}{\log{b}} < \frac{\log{c}}{\log{b}} + \frac{b}{\log{b}} < 1 + \frac{b}{\log{b}}$$

Therefore, the following should be true:

$$2 \geq \frac{\log{c}}{\log{b}} + \frac{b}{\log{b}} > -1 + \frac{b}{\log{b}}$$

So I move the pieces of the inequality around a bit:

$$2 > -1 + \frac{b}{\log{b}} \Rightarrow 3 > \frac{b}{\log{b}} \Rightarrow 3 > \frac{(a+3)^2}{2\log{(a+3)}} \Rightarrow 6\log{(a+3)} > (a+3)^2$$

and remember that by the definition I gave for $a$,

$$(a+3 > 6) \land (a+3 > \log{a+3} > 1)$$

So it leads to a contradiction, as it is impossible for

$$6\log{(a+3)} > (a+3)^2$$

to be true.

Therefore, $n^2 \neq \Omega(2^n)$.

Edit 2: I used the inequality that Gary provided to prove that $\log{n} \neq \Omega(\sqrt{n})$:

$$\log{n} = \Omega(\sqrt{n}) \to \exists c \exists n_0 \forall n (n > n_0 \to \log{n} \geq c \cdot \sqrt{n})$$

$$\log{n} \geq c \cdot \sqrt{n} \Rightarrow \frac{\log{n}}{n^{1/2}} \geq c$$

$$\frac{\log{n}}{n^{1/2}} \leq \frac{4}{\ln{2} \cdot n^{1/4}} \textrm{, so}$$

$$ \frac{4}{\ln{2} \cdot n^{1/4}} \geq c \Rightarrow 4 \geq c \cdot \ln{2} \cdot n^{1/4} \textrm{ should be true.}$$

$$(\frac{1}{2} < \ln{2}) \to (c \cdot \frac{1}{2} \cdot n^{1/4} < c \cdot \ln2 \cdot n^{1/4})$$

$$4 \geq \frac{1}{2} \cdot c \cdot n^{1/4} \Rightarrow 8 \geq c \cdot n^{1/4}$$

$$\textrm{Let } a = \max\left(\left(\frac{8}{c^{-1}}\right)^4 + 1, c, n_0\right)+8^4$$

$$a > n_0 \textrm{, so } 8 \geq c \cdot a^{1/4} \textrm{ should be true but} $$

$$(0 < c < 1) \to (c \cdot \frac{8}{c^{-1}} = 8 \land a^{1/4} > \frac{8}{c^-1}) \to (c \cdot a^{1/4} > 8)$$

$$(c \geq 1) \to (a > 8^4) \to (c \cdot a ^{1/4} > 8)$$

$$\textrm{So } 8 \geq c \cdot a^{1/4} \textrm{ cannot be true}$$

Therefore, this leads to a contradiction so $\log{n} \neq \Omega(\sqrt{n})$.

Answer 1

Taking negation in $O,\Omega, \Theta$ asymptotic notations needs good understanding when we are searching for values and when we have arbitrary variables. Such words as "quick" or "slow" should have exact mathematical understanding.

For example, let's compare $n \in O(2^n)$ to $n \notin \Omega(2^n)$.

For first we have $$\exists C>0,\exists N\in\mathbb{N}, \forall n > N, n \leqslant C \cdot 2^n\quad\quad(1)$$ For second $$\forall C>0,\forall N\in\mathbb{N}, \exists n > N, n < C \cdot 2^n\quad\quad(2)$$

We see, that while in first $(1)$ we are searching for $C$, then in second $(2)$ $C$ is arbitrary variable.

For $(1)$ is enough to know inequality $$n < 2^n, n\in \mathbb{N}\quad\quad(3)$$ Based on it we can use pair $C=1,N=1$.

But quite different is situation in $(2)$. Here $(3)$ type inequalities is not enough. Rewriting $(2)$ as $\frac{n}{2^n}<C$ where the statement of the problem is in finding $n$ for any $C>0$, we arrive at task similar to limit. When we decide to prove $(2)$, then usually we are using ways which, de facto, gives limit.

So, most easy is to use statement $\frac{n}{2^n}\to 0, n\to\infty$, which, of course, is more strong, then $(2)$. To argue with me, it will be quite suitable if someone can bring proof, which gives exactly $(2)$, but is not equivalent to limit.

And, at end, about your proof by contradiction in comment. Do I correctly understand, that you mean $c, n_0$ arbitrary? If yes, then you come to situation same with $(2)$.

Answer to Edit: Thanks for detail explanation. As far as I see it's ok. Let me say, that You start with assuming statement like my $(1)$, but to find contradiction in it you come to statement with type $(2)$: You created proof where $c$ is arbitrary non-negative and find $b$ (i.e. $a,n$) for it. And last note about this proof: You finish it with impossibility of $6\log{(a+3)} > (a+3)^2$, but how are you proving this last one? You will come to same efforts, as is needing to prove by limits, which I wrote in end of my answer. Sorry, for repeating one more time - obviously is possible not to use the word "limit", but essentially we are doing same.

And now about your aim to get $\log_{2}(n)=\Omega(\sqrt{n}) \Rightarrow n^2 = \Omega(2^n)$. I notice, that this implication is true only because first statement is false and answer to title is yes. So why we need it?

Let's come to main aim $\log_{2}(n) \neq \Omega(\sqrt{n})$. Formally, in same way with $(2)$, this is $$\forall c>0,\forall N\in\mathbb{N}, \exists n > N, \log_{2}(n) < c \cdot\sqrt{n}$$ So, we come to task for arbitrary $c$ search,find, appropriate $n$. I can, if you would like it, bring proof for $\frac{ \log_{2}(n)}{\sqrt{n}}< c$ "without limit" i.e. I'll not mention this word, by steps of inequalities, but essentially it will be same.

For Edit2:

I am left with the impression of a little more complexity than could have been avoided. When in conditions $\exists c \exists n_0 \forall n > n_0 $ you come to $\frac{4}{\ln{2} \cdot n^{1/4}} \geq c$ i.e. $n \leqslant \left(\frac{4}{\ln{2} \cdot c}\right)^4$, then this is already contradiction with Archimedean property of real numbers. Also, let me note, that Gary's inequality directly gives limit. For any $0<\alpha<1$ we can use inequality $$ \dfrac{log _{2}n}{n^{\alpha}} = \dfrac{1}{\alpha} \cdot \dfrac{log _{2}n^{\alpha}}{n^{\alpha}} \leqslant \dfrac{1}{\alpha} \cdot \dfrac{log _{2}(\lfloor n^{\alpha} \rfloor + 1)}{\lfloor n^{\alpha} \rfloor} = \dfrac{1}{\alpha} \cdot \dfrac{log _{2}\lfloor n^{\alpha} \rfloor }{\lfloor n^{\alpha} \rfloor} + \dfrac{1}{\alpha} \cdot \dfrac{1}{\lfloor n^{\alpha} \rfloor}$$ right side behaves as subsequence of $\dfrac{1}{\alpha} \cdot \dfrac{log _{2}n }{n} + \dfrac{1}{\alpha} \cdot \dfrac{1}{n}$