Supongamos que tenemos un número $x$ y queremos saber de qué número $t$ es su logaritmo [natural], $x=\ln(t)$ : sería tan fácil como hallar $t=e^x$ . Sin embargo, supongamos que tenemos una calculadora muy básica que solo suma, resta, divide y multiplica; no tiene necesariamente potencias y el número $e$ ni está, la típica calculadora en cotabilidad. ¿Cómo hallaríamos la solución? La solución viene dado por una serie de polinomios logarítmicos (donde podemos obtener el grado de aproximación que queramos con una suma parcial):
$$\sum_{n=0}^\infty \frac{1}{n!}\ln^n(x) = x \qquad \sum_{n=0}^\infty \frac{(-1)^n}{n!}\ln^n(x) = \frac{1}{x}$$ Es más, siguiendo este resultado, uno puede ver cómo expresar cualquier polinomio “clásico” de grado $N$ , $P_N(x)$ , con coeficientes $\big(a_k\big)_{k=0}^N$ , como un polinomio logarítmico_$$P_N(x) = \sum_{k=0}^N a_k x^k = \sum_{k=0}^N a_k \sum_{n=0}^\infty \frac{k^n}{n!}\ln^n(x) = \sum_{n=0}^\infty \frac{\ln^n(x)}{n!}\sum_{k=0}^N a_k k^n$$
¿Cómo se obtienen estas relaciones? Muchas se sacan usando series de Taylor y sustituyendo $x\mapsto\ln(t)$ . Por ejemplo si tomamos la del coseno y seno hiperbólicos:
$$\sum_{n=0}^\infty \frac{1}{(2n)!}\ln^{2n}(x) = \frac{x^2+1}{2x} \qquad \sum_{n=0}^\infty \frac{1}{(2n+1)!}\ln^{2n+1}(x) = \frac{x^2-1}{2x}$$Es más, siquiendo este razonamiento uno puede hallar una expresión cerrada en términos únicamente de logaritmos del logaritmo integral: $\displaystyle \operatorname{li} \overset{\text{def}}{=}―\hspace{-11.5pt}\int_0^x \frac{1}{\ln t} \;\text{d}t$ a través de la expresión $\operatorname{li}(x)\triangleq\operatorname{Ei}\big(\ln(x)\big)$ , de una función íntimamente relacionada, la exponencial integral $\displaystyle \operatorname{Ei}(x) \overset{\text{def}}{=}―\hspace{-11.5pt}\int_{-\infty}^x\frac{e^t}{t}\;\text{d}t$ : $$\operatorname{li}(x) = \gamma+\ln\!\big|\!\ln(x)\big| + \sum_{n=1}^\infty \frac{1}{n \, n!}\ln^n(x)$$ Uno puede ver fácilmente que lo que hemos estado haciendo hasta hora es buscar expresiones “bomitas” que tengan alguna exponencial de por medio, y haciendo un cambio de variable tontorrón obtenemos expresiones en términos que nos interesan, es decir, pasamos de series polinómicas en $ \mathbb{R}[x]$ tras un cambio de variable a series polinómicas logarítmicamente en $ \mathbb{R}\big[\ln(t)\big] \cong \mathbb{R}[x]/(t-e^x) \cong \mathbb{R}[x]/\big(\ln(t)-x\big) $ . Es más, $\big\{ \ln^k(t) \big\}_{k=0}^N$ conforman una base de $\mathbb{C}_N\big[\ln(t)\big]$ para cualquier $N$ .
Además esto es tan importante que en notación asitótica si uno pone una virgulilla, $ \widetilde{\mathcal{O}} , \widetilde{ {\scriptstyle \mathcal{O}} }, \widetilde{\Omega},\cdots$ , significa que no está acotado por dicha función como tal sino como dicha función por la $\alpha$-ésima potencia del logaritmo de dicha función para algún $\alpha$ , es decir: $$g(x) \in \widetilde{\mathcal{O}}\Big(f(x)\Big) \!\overset{\;\Delta}{\iff} g(x) \in \mathcal{O}\Big(f(x)\,\ln^\alpha\!\!\big(f(x)\big)\Big) \\ g(x) \in \widetilde{{\scriptstyle \mathcal{O}}}\Big(f(x)\Big) \!\overset{\;\Delta}{\iff} g(x) \in {\scriptstyle \mathcal{O}}\Big(f(x)\,\ln^\alpha\!\!\big(f(x)\big)\Big) \\ g(x) \in \widetilde{\Omega}\Big(f(x)\Big) \!\overset{\;\Delta}{\iff} g(x) \in \Omega\Big(f(x)\,\ln^\alpha\!\!\big(f(x)\big)\Big)$$ Veamos dos ejemplos
Autor: Đɑvɪẟ Ƒernández-De la Cruʒ.
$$\sum_{n=0}^\infty \frac{1}{(2n)!}\ln^{2n}(x) = \frac{x^2+1}{2x} \qquad \sum_{n=0}^\infty \frac{1}{(2n+1)!}\ln^{2n+1}(x) = \frac{x^2-1}{2x}$$Es más, siquiendo este razonamiento uno puede hallar una expresión cerrada en términos únicamente de logaritmos del logaritmo integral: $\displaystyle \operatorname{li} \overset{\text{def}}{=}―\hspace{-11.5pt}\int_0^x \frac{1}{\ln t} \;\text{d}t$ a través de la expresión $\operatorname{li}(x)\triangleq\operatorname{Ei}\big(\ln(x)\big)$ , de una función íntimamente relacionada, la exponencial integral $\displaystyle \operatorname{Ei}(x) \overset{\text{def}}{=}―\hspace{-11.5pt}\int_{-\infty}^x\frac{e^t}{t}\;\text{d}t$ : $$\operatorname{li}(x) = \gamma+\ln\!\big|\!\ln(x)\big| + \sum_{n=1}^\infty \frac{1}{n \, n!}\ln^n(x)$$ Uno puede ver fácilmente que lo que hemos estado haciendo hasta hora es buscar expresiones “bomitas” que tengan alguna exponencial de por medio, y haciendo un cambio de variable tontorrón obtenemos expresiones en términos que nos interesan, es decir, pasamos de series polinómicas en $ \mathbb{R}[x]$ tras un cambio de variable a series polinómicas logarítmicamente en $ \mathbb{R}\big[\ln(t)\big] \cong \mathbb{R}[x]/(t-e^x) \cong \mathbb{R}[x]/\big(\ln(t)-x\big) $ . Es más, $\big\{ \ln^k(t) \big\}_{k=0}^N$ conforman una base de $\mathbb{C}_N\big[\ln(t)\big]$ para cualquier $N$ .
Además esto es tan importante que en notación asitótica si uno pone una virgulilla, $ \widetilde{\mathcal{O}} , \widetilde{ {\scriptstyle \mathcal{O}} }, \widetilde{\Omega},\cdots$ , significa que no está acotado por dicha función como tal sino como dicha función por la $\alpha$-ésima potencia del logaritmo de dicha función para algún $\alpha$ , es decir: $$g(x) \in \widetilde{\mathcal{O}}\Big(f(x)\Big) \!\overset{\;\Delta}{\iff} g(x) \in \mathcal{O}\Big(f(x)\,\ln^\alpha\!\!\big(f(x)\big)\Big) \\ g(x) \in \widetilde{{\scriptstyle \mathcal{O}}}\Big(f(x)\Big) \!\overset{\;\Delta}{\iff} g(x) \in {\scriptstyle \mathcal{O}}\Big(f(x)\,\ln^\alpha\!\!\big(f(x)\big)\Big) \\ g(x) \in \widetilde{\Omega}\Big(f(x)\Big) \!\overset{\;\Delta}{\iff} g(x) \in \Omega\Big(f(x)\,\ln^\alpha\!\!\big(f(x)\big)\Big)$$ Veamos dos ejemplos
- El algoritmo bitonic sort tiene un coste operacional de $\widetilde{\mathcal{O}}(n)$ , en particular, de $\mathcal{O}\Big(n\ln^2(n)\Big)$ .
- El estimador de medianas repetidas (Spiegel): por fuerza bruta tiene un coste operativo de $\mathcal{O}(n^2) \subsetneq \widetilde{\mathcal{O}}(n^2)$ ; usando téctinas sofisticadas, $\mathcal{O}\big(n \ln^2(n)\big) \subsetneq \widetilde{\mathcal{O}}(n)$ ; en tiempo esperado randomizado, $\mathcal{O}\big(n \ln(n)\big) \subsetneq \widetilde{\mathcal{O}}(n)$ ; pero en un algoritmo on-line con un tiempo de actualización $\mathcal{O}\big(n\big) \subsetneq \widetilde{\mathcal{O}}(n)$ .
Autor: Đɑvɪẟ Ƒernández-De la Cruʒ.
