Hace $\log_{2}(n)=\Omega(\sqrt{n})$ implica $n^2 = \Omega(2^n)$ ?

Question

Estoy teniendo algunos problemas tratando de probar $\log_{2}(n) \neq \Omega(\sqrt{n})$ . Estoy tratando de hacer esto sin usar límites.

Soy capaz de demostrar $n^2 \neq \Omega(2^n)$ Así que si $\log_{2}(n)=\Omega(\sqrt{n}) \Rightarrow n^2 = \Omega(2^n)$ entonces creo que puedo usar el contrapositivo para refutar $\log_{2}(n) = \Omega(\sqrt{n})$ .

La razón por la que creo $\log_{2}(n)=\Omega(\sqrt{n}) $ implica $ n^2 = \Omega(2^n)$ es porque $\log_{2}{n}$ tiene una solución entera $k$ en cada $n=2^k$ mientras que $\sqrt{n}$ tiene una solución entera $k$ en cada $n=k^2$ . Así que para $\log_{2}{n}$ para estar en $\Omega(\sqrt{n})$ la distancia entre las soluciones enteras para $\sqrt{n}$ tendría que crecer más rápidamente que la distancia entre soluciones enteras para $\log_{2}{n}$ .

¿Es válido mi razonamiento?

Editar:

Para demostrar que $n^2 \neq \Omega(2^n)$ Primero asumo que es verdad. Así que asumo que lo siguiente es cierto:

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

Luego muevo un poco las piezas de la desigualdad,

$$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}}$$

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

Dejo que $a = \max(2^{6-\log{c}}, c, n_0) + 7$ y $b=(a+3)^2$ . Por lo tanto, $b > a > n_0$ Por lo tanto, lo siguiente debería ser cierto:

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

Para demostrar que no es cierto, hago lo siguiente:

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

Para $c \geq 1$ :

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

Por lo tanto, para $c > 0$ :

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

Lo que significa que:

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

Por lo tanto, lo siguiente debería ser cierto:

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

Así que muevo un poco las piezas de la desigualdad:

$$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$$

y recuerda que por la definición que di para $a$ ,

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

Por lo tanto, conduce a una contradicción, ya que es imposible que

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

que sea cierto.

Por lo tanto, $n^2 \neq \Omega(2^n)$ .

Editar 2: Utilicé la desigualdad que Gary proporcionó para demostrar que $\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}$$

Por lo tanto, esto lleva a una contradicción por lo que $\log{n} \neq \Omega(\sqrt{n})$ .

Answer 1

Tomar la negación en $O,\Omega, \Theta$ Las notaciones asintóticas necesitan una buena comprensión cuando buscamos valores y cuando tenemos variables arbitrarias. Palabras como "rápido" o "lento" deben tener una comprensión matemática exacta.

Por ejemplo, comparemos $n \in O(2^n)$ a $n \notin \Omega(2^n)$ .

Para empezar tenemos $$\exists C>0,\exists N\in\mathbb{N}, \forall n > N, n \leqslant C \cdot 2^n\quad\quad(1)$$ Para el segundo $$\forall C>0,\forall N\in\mathbb{N}, \exists n > N, n < C \cdot 2^n\quad\quad(2)$$

Vemos, que mientras en primera $(1)$ somos buscando en para $C$ , luego en el segundo $(2)$ $C$ es arbitrario variable.

Para $(1)$ es suficiente para conocer la desigualdad $$n < 2^n, n\in \mathbb{N}\quad\quad(3)$$ En base a ello podemos utilizar el par $C=1,N=1$ .

Pero muy diferente es la situación en $(2)$ . Aquí $(3)$ desigualdades de tipo no es suficiente. Reescribiendo $(2)$ como $\frac{n}{2^n}<C$ donde el planteamiento del problema está en encontrar $n$ para cualquier $C>0$ llegamos a una tarea similar a la del límite. Cuando decidimos demostrar $(2)$ Entonces, por lo general, estamos utilizando formas que, de facto, dan límite.

Por lo tanto, lo más fácil es utilizar la declaración $\frac{n}{2^n}\to 0, n\to\infty$ que, por supuesto, es más fuerte, entonces $(2)$ . Para discutir conmigo, será bastante adecuado si alguien puede traer una prueba, que da exactamente $(2)$ pero no es equivalente al límite.

Y, al final, sobre tu prueba por contradicción en el comentario. ¿Entiendo correctamente, que usted quiere decir $c, n_0$ ¿arbitrario? Si es así, entonces se llega a la situación misma con $(2)$ .

Respuesta a Editar : Gracias por la explicación detallada. Por lo que veo está bien. Permítanme decir, que usted comienza con la asunción de la declaración como mi $(1)$ pero para encontrar una contradicción en ella se llega a la afirmación con el tipo $(2)$ : Has creado una prueba en la que $c$ es arbitrario no negativo y encontrar $b$ (es decir $a,n$ ) para ello. Y una última nota sobre esta prueba: La terminas con la imposibilidad de $6\log{(a+3)} > (a+3)^2$ pero, ¿cómo demuestras esto último? Usted vendrá a los mismos esfuerzos, como es necesario demostrar por los límites, que escribí en el final de mi respuesta. Lo siento, por repetir una vez más - obviamente es posible no utilizar la palabra "límite", pero esencialmente estamos haciendo lo mismo.

Y ahora sobre su objetivo de conseguir $\log_{2}(n)=\Omega(\sqrt{n}) \Rightarrow n^2 = \Omega(2^n)$ . Me doy cuenta de que esta implicación es cierta sólo porque la primera afirmación es falsa y la respuesta al título es sí. Entonces, ¿por qué lo necesitamos?

Pasemos al objetivo principal $\log_{2}(n) \neq \Omega(\sqrt{n})$ . Formalmente, de la misma manera con $(2)$ Esto es $$\forall c>0,\forall N\in\mathbb{N}, \exists n > N, \log_{2}(n) < c \cdot\sqrt{n}$$ Por lo tanto, venimos a la tarea de arbitrario $c$ buscar, encontrar , apropiado $n$ . Puedo, si lo desea, traer pruebas para $\frac{ \log_{2}(n)}{\sqrt{n}}< c$ "sin límite", es decir, no mencionaré esta palabra, por pasos de desigualdades, pero esencialmente será lo mismo.

Para Edición2 :

Me queda la impresión de que es un poco más complejo de lo que se podría haber evitado. Cuando en condiciones $\exists c \exists n_0 \forall n > n_0 $ usted viene a $\frac{4}{\ln{2} \cdot n^{1/4}} \geq c$ es decir $n \leqslant \left(\frac{4}{\ln{2} \cdot c}\right)^4$ entonces esto ya es una contradicción con Propiedad arquimediana de números reales. También, permítanme notar, que la desigualdad de Gary da directamente el límite. Para cualquier $0<\alpha<1$ podemos utilizar la desigualdad $$ \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}$$ lado derecho se comporta como una subsecuencia de $\dfrac{1}{\alpha} \cdot \dfrac{log _{2}n }{n} + \dfrac{1}{\alpha} \cdot \dfrac{1}{n}$