¿Cómo calcular el comportamiento asintótico de una función inversa?

Question

Sea $f(x) := \frac{x}{1+\log_2(x)}$ . Me gustaría calcular una expresión asintótica para su función inversa - $f^{-1}(y)$ - cuando $y$ es grande. Por ejemplo: is $f^{-1}(y)$ está en $O(y \log y)$ ? O en $O(y \log^k y)$ para algún número entero $k$ ?

Sé cómo calcular asintóticas para funciones, pero ¿cómo puedo hacer el cálculo para funciones inversas?

Answer 1

Esta función es estrictamente creciente para $x \ge 2$ y las cosas son relativamente fáciles en este caso, sólo tiene que conectar una conjetura y ver qué tan exacto es para obtener límites. Más precisamente:

Lema: Sea $f$ sea una función estrictamente creciente. Si $f(x) < y$ entonces $x < f^{-1}(y)$ y si $f(x) > y$ entonces $x > f^{-1}(y)$ .

Así, por ejemplo, calculamos que

$$f(y \log_2 y) = \frac{y \log_2 y}{1 + \log_2 (y \log_2 y)} < \frac{y \log_2 y}{\log_2 y} = y$$

de lo que se deduce que $f^{-1}(y) > y \log_2 y$ . Por otra parte

$$f(C y \log_2 y) = \frac{Cy \log_2 y}{1 + \log_2 (Cy \log_2 y)}$$

que podemos ver crecer como $Cy$ y, por tanto, para $C > 1$ será mayor que $y$ para un $y$ . Por lo tanto, para cualquier $\varepsilon > 0$ obtenemos que $f^{-1}(y) \le (1 + \varepsilon) y \log_2 y$ para un $y$ . Esto da $f^{-1}(y) = O(y \log y)$ y de hecho obtenemos $f^{-1}(y) \sim y \log_2 y$ . Se pueden dar asintóticas más precisas en términos de la Función W de Lambert .

Este ejemplo particular de inversión asintótica se da de forma natural en teoría de números, donde se utiliza para pasar de la teorema del número primo $\pi(n) \sim \frac{n}{\log n}$ a la asintótica $p_n \sim n \log n$ para la $n^{th}$ número primo.

Answer 2

Si desea la inversa de $$y= \frac{x}{1+\log_2(x)}$$ es más fácil reescribirlo como $$2y=\frac {2x}{\log_2(2x)}$$ o utilizando logaritmos naturales $$\frac 2 {\log(2)}y=\frac {2x}{\log(2x)}\implies x=-\frac{y}{\log (2)} W_{-1}\left(-\frac{\log (2)}{2 y}\right)$$ donde $W_{-1}(.)$ es la segunda rama de Función de Lambert como ya ha respondido @Qiaochu Yuan.

En el dominio real, esto implica $y \geq \frac{e\log (2)}{2}$ .

Para valores grandes de $y$ Eche un vistazo a la ampliación en la página enlazada $$W_{-1}(t)\approx L_1-L_2+\frac{L_2}{L_1}+\frac{L_2(L_2-2)}{2L_1^2}+\frac{L_2(2L_2^2-9L_2+6)}{6L_1^3}+\cdots$$ donde $L_1=\log(-t)$ y $L_2=\log(-L_1)$ .

Utilizando sólo $L_1$ entonces tienes $x \sim y \log_2(y)$ como ya ha respondido @Qiaochu Yuan.

Answer 3

Informalmente: de $$y=f(x)= \frac{x}{1+\log_2(x)} \tag 1$$

primero ves que $f(x)$ aumenta para $x>2$ por lo que le interesan ambos $x,y\to +\infty$ (en realidad, también existe otra rama, en la que $y \to \infty$ para $x \to 1/2$ pero supongo que no le interesa).

Entonces, para grandes $x$ la del denominador se vuelve despreciable y

$$ x \approx \tag 2 y \,\log_2(x)$$

Ahora, puede esperar que $(2)$ puede aplicarse recursivamente, por lo que

$$ x \approx y \log_2( y \log_2(x)) \approx y \log_2( y \log_2(y \log_2(\cdots))) \tag 3$$ o

$$ x = y (\log_2 y +O(\log_2 \log_2 y)) \tag 4$$ Se trata de una mera suposición, pero puedes hacerla rigurosa.

Por ejemplo, es fácil mostrar, conectando desde $(1)$ que

$$ \frac{x}{y \log_2 y} \to 1$$ y

$$ \frac{x}{y} - \log_2 y \approx 1 + \log_2(1+\log_2(x)) \to +\infty$$