Me preguntaba cómo mostrar que $\tau(n)/\phi(n)\to 0$ , ya que $n\to \infty$ . Aquí $\tau(n)$ denota el número de divisores positivos de n, y $\phi(n)$ es la función phi de Euler.
Respuestas
¿Demasiados anuncios?
ND Geek
Puntos
880
Una pista: deje que $Q(n)$ denota la mayor potencia prima que divide a $n$ . Entonces demuestre:
- $\displaystyle \frac{\tau(n)}{\phi(n)} \le 2 \frac{\tau(Q(n))}{\phi(Q(n))} \le \frac4{\log2} \frac{\log Q(n)}{Q(n)}$ ;
- $Q(n) \to \infty$ como $n\to \infty$ . Para el número 1, querrá utilizar el hecho de que $\tau(n)/\phi(n)$ es multiplicativa, así como las evaluaciones explícitas de las mismas sobre potencias primarias.
Obsérvese que para un entero impar $n>1$ tenemos $\tau(n)/\varphi(n)<1$ (primero se observa para una potencia primaria impar, luego por multiplicatividad a todas las impar $n$ ).
Para cada $\epsilon>0$ , considere el conjunto $S_\epsilon$ de esos impar $n$ 's con $\tau(n)/\varphi(n)>\epsilon$ . Escriba $n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$ , donde $p_1, \dots, p_k$ son impar. Entonces
$$\frac{\alpha_1+1}{p_1^{\alpha_1}} \dots \frac{\alpha_1+1}{p_1^{\alpha_1}}>\epsilon$$
y como cada término del producto es $<1$ cada término debe ser a su vez $>\epsilon$ . Por lo tanto, para cada $i$ ,
$$\frac{1+\alpha_i}{p_i^{\alpha_i}}>\epsilon.$$
Es evidente que existen combinaciones finitas de $p$ y $\alpha$ que satisfacen esto. Por lo tanto, $S_\epsilon$ es finito. Ahora, para un número entero general $n=2^mn'$ donde $n'$ es impar y con $\tau(n)/\varphi(n)> \epsilon$ , tenga en cuenta que $\tau(n)/\varphi(n)<2\tau(n')/\varphi(n')$ por lo que hay un número finito de opciones para $n'$ y $\tau(n)/\varphi(n)<\frac{m+1}{2^m}$ por lo que hay un número finito de opciones para $m$ .
Por lo tanto, para cada $\epsilon>0$ hay un número finito de enteros $n$ con $\tau(n)/\varphi(n)>\epsilon$ .
Aquí hay un gráfico de $\tau(n)/\varphi(n)$ para $n<10^5$ :
Y también, aquí es una foto de un bebé oso
Stephan Aßmus
Puntos
16
Existe una metodología para tratar por separado el numerador y el denominador, iniciada por Ramanujan. La construcción de números "altamente compuestos" superiores da:
$$ \tau(n) \; \leq \; \; 24 \; \; \left( \frac{n}{315} \right)^{(1/3)} $$
El argumento relacionado, con un cierto tipo de óptimos en los primoriales, da
$$ \phi(n) \geq \frac{2 n^{2/3}}{6^{2/3}},$$
y juntos conseguimos
$$ \frac{\tau(n)}{\phi(n)} \leq \frac{12 \; \cdot \; 4^{1/3}}{ 35^{1/3} \; \; n^{1/3}} \; = \; \frac{5.823426...}{n^{1/3}} $$
EDIT, martes, 20 de diciembre: se necesita muy poca maquinaria para describir cómo obtener valores muy pequeños de $\phi(n)$ en relación con el tamaño de $n,$ y luego derivar desigualdades útiles a partir de esa información. Dada una $1 \geq \delta > 0,$ queremos encontrar el número $N_\delta$ que da la El más pequeño valor de $$ f(n) = \frac{\phi(n)}{n^{1-\delta}}.$$ Vemos que $f(1) = 1.$ Además, si tenemos algún $n$ que no es divisible por un primo $p,$ entonces $f(np) = f(n) f(p),$ y reducimos el resultado si multiplicamos por $p$ cuando $f(p) < 1.$ Al mismo tiempo, si $n$ ya es divisible por $p,$ multiplicando por $p$ siempre aumenta $f,$ así que $N_\delta$ será libre de cuadrados en cualquier caso. Así que esa es la receta, $N_\delta$ es el producto (finito) de los primos $p$ para lo cual $$ p^{1-\delta} \geq p-1.$$ La derivada de $x^{1-\delta} - x + 1$ es $(1-\delta) x^{-\delta} -1,$ y esto es negativo para $x \geq 1,$ mientras que la segunda derivada $-\delta (1-\delta) x^{-1-\delta}$ también es negativo allí, por lo que en algún momento $x^{1-\delta} - x + 1$ se convierte en $0$ y a partir de ahí negativo. Como resultado, $N_\delta$ es el producto de los primos consecutivos hasta algún punto. Estos se llaman primoriales.
Mientras tanto, el primer (mayor) $\delta$ que incluye un primo $p$ es $$ \delta_p = \frac{\log \left( 1 + \frac{1}{p-1} \right)}{\log p} $$
Tomando $\delta = 1/3,$ obtenemos $N_{1/3}=6$ y $1 -\delta = 2/3,$ para que siempre tengamos $$ \frac{\phi(n)}{n^{2/3}} \geq \frac{\phi(6)}{6^{2/3}} = \frac{2}{6^{2/3}} $$
