¿Está la función phi de Euler acotada por debajo?

Question

Estoy trabajando en una pregunta para mi clase de teoría de números que pregunta:

Demostrar que para cada número entero $n \geq 1$ , $\phi(n) \geq \frac{\sqrt{n}}{\sqrt{2}}$ .

Sin embargo, estuve buscando en Google, y en varios sitios web he encontrado gente que explica que la función phi tiene un límite superior definido, pero no un límite inferior. ¿Estoy leyendo estos sitios incorrectamente, o me estoy perdiendo algo en el propio problema?

Answer 1

Permítanme comenzar con el límite inferior explícito en BAJO , $$ \phi(n) > \frac{n}{e^\gamma \log \log n + \frac{3}{\log \log n}} $$ para $n>2.$

y luego hacer su resultado más fácil por separado. Es un procedimiento debido a Ramanujan, en el que podemos encontrar explícitamente, para cualquier $1 > \delta > 0,$ el número entero que da el mínimo de $$ \frac{\phi(n)}{n^{1-\delta}} $$ Mi recuerdo es que los óptimos siempre se dan en los primoriales, pero tendré que comprobarlo. Ah, antes de que se me olvide, es el teorema 327 en la página 267 de Hardy y Wright que la fracción va al infinito como $n$ va al infinito, por lo que sí alcanza un mínimo.

Muy bien, comprobado, el mínimo se produce en el primorial $2 \cdot 3 \cdot 5 \cdots p,$ el producto de primos consecutivos, donde el $p$ es el mayor primo que satisface $$ p - 1 \leq p^{1 - \delta}. $$ Así, con $\delta = 1/2,$ encontramos $2 - 1 \leq \sqrt 2,$ pero $3-1 > \sqrt 3,$ por lo que el mínimo de $$ \frac{\phi(n)}{\sqrt n} $$ se produce en $n=2$ y $$ \phi(n) \geq \sqrt{ \frac{n}{ 2} }. $$

Con $\delta = \log (3/2) / \log 3 = 0.36907\ldots,$ encontramos $3 - 1 \leq 3^{1-\delta},$ por lo que el mínimo de $$ \frac{\phi(n)}{n^{0.63092975\ldots}} $$ se produce en $n=2 \cdot 3 = 6$ y $$ \frac{\phi(n)}{n^{0.63092975\ldots}} \geq \frac{2}{6^{0.63092975\ldots}} = 0.645760\ldots. $$

No es del todo óptimo, pero sí más bonito. Tome $\delta = 1/3,$ obtenemos $$ \frac{\phi(n)}{n^{2/3}} \geq \frac{2}{6^{2/3}}. $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

Ya teníamos, con $\delta = 1/2,$ $$ \phi(n) \geq \sqrt{ \frac{n}{ 2} }. $$

Con $\delta = 1/3,$ obtenemos $$ \phi(n) \geq 2 \cdot \left( \frac{n}{6} \right)^{2/3}. $$

Tome $\delta = 1/8,$ obtenemos $$ \phi(n) \geq 8 \cdot \left( \frac{n}{30} \right)^{7/8}. $$

Tome $\delta = 1/13,$ obtenemos $$ \phi(n) \geq 48 \cdot \left( \frac{n}{210} \right)^{12/13}. $$

Tome $\delta = 1/26,$ obtenemos $$ \phi(n) \geq 480 \cdot \left( \frac{n}{2310} \right)^{25/26}. $$

Tome $\delta = 1/33,$ obtenemos $$ \phi(n) \geq 5760 \cdot \left( \frac{n}{30030} \right)^{32/33}. $$

Tome $\delta = 1/47,$ obtenemos $$ \phi(n) \geq 92160 \cdot \left( \frac{n}{510510} \right)^{46/47}. $$

Este es exactamente el mismo procedimiento utilizado en los números altamente compuestos de Ramanujan y los números colosalmente abundantes de Alaoglu y Erdos, pero no estoy seguro de conocer ningún sitio que muestre cómo se obtienen los primoriales. EDIT: Pongo una prueba como respuesta separada, también doy referencia de la relación con la Hipótesis de Riemann, debida a Jean-Louis Nicolas.

Answer 2

Encontrará una prueba completa del resultado en el apéndice de este documento . Aquí tienes una pista para empezar a hacerlo tú mismo.

Primero demuestre que si $n$ es impar o un múltiplo de $4$ entonces $\varphi(n)\ge\sqrt n$ para ello se utilizará la factorización primaria de $n$ y la multiplicidad de $\varphi$ . Entonces maneja el caso $n=2m$ avec $m$ impar utilizando la multiplicidad de $\varphi$ para escribir $\varphi(n)=\varphi(2)\varphi(m)$ .

Answer 3

EEDDIITT: esto da una prueba de mi afirmación principal en mi primera respuesta, que una determinada función toma su valor mínimo en un determinado primor. De hecho, puse esa información, con algunos ejemplos, en el artículo de la wikipedia, pero fue editado en un minuto por considerarlo irrelevante. Sobre gustos no hay nada escrito.

ORIGINAL: Tomamos como dado el Teorema 327 en la página 267 de Hardy y Wright, que para alguna fija $0 < \delta < 1,$ la función $$ g(n) = \frac{\phi(n)}{n^{1-\delta}} $$ va al infinito como $n$ va al infinito.

Tenga en cuenta que $g(1) = 1$ pero $g(2) < 1.$ Para algunos $N_\delta,$ siempre que $ n > N_\delta$ obtenemos $g(n) > 1.$ De ello se desprende que, comprobando todos los $1 \leq n \leq N_\delta,$ la cantidad $g(n)$ asume un mínimo que es menor que 1. Quizás asume este mínimo en más de un punto. Si es así, tomamos el mayor valor de $n.$

Aquí vamos a demostrar que el valor de $n$ en el que se produce el mínimo es el primorial creado al tomar el producto de todos los primos $p$ que satisfagan $$ p^{1-\delta} \geq p-1. $$ Como ya he mencionado, en el caso dos el mínimo se produce en dos $n,$ esto da el mayor de los dos.

Por lo tanto, la mayor tarea de la existencia la hacen Hardy y Wright. Tenemos el mínimo de $g$ en algunos $$ n = p_1^{a_1} p_2^{a_2} p_3^{a_3} \cdots p_r^{a_r}, $$ con $$ p_1 < p_2 < \cdots < p_r. $$

En primer lugar, suponga que uno o más de los $a_i > 1.$ Ahora, $$ \frac{ g(p_i)}{g(p_i^{a_i})} = p^{\delta - a_i \delta} = p^{\delta (1 - a_i)} < 1. $$ Como resultado, si disminuimos ese exponente a uno, el valor de $g$ se reduce, contradiciendo la minimalidad. Así que todos los exponentes son realmente 1.

En segundo lugar, suponer que hay algún hueco, algún primo $q < p_r $ tal que $q \neq p_j$ para todos $j,$ es decir $q$ no divide $n.$ Bueno, para la variable real $x > 0,$ la función $$ \frac{x-1}{x^{1-\delta}} $$ es siempre creciente, ya que la primera derivada es $$ x^{\delta - 2} (\delta x +(1-\delta)). $$ Se deduce que, en la factorización de $n,$ si sustituimos $p_r$ por $q,$ el valor de $g$ se reduce, contradiciendo la minimalidad. Así que los factores primos de $n$ son consecutivos, empezando por el 2, y $n$ se denomina primorosa.

Por último, ¿cuál es el mayor factor primo de $n?$ A partir de 2, multiplicando por cualquier primo $p$ con $$ \frac{p-1}{p^{1-\delta}} \leq 1 $$ reduce el valor de $g$ o lo mantiene igual, por lo que al exigir el mayor $n$ en caso de que haya dos que alcancen el mínimo de $g,$ tomamos $n$ para ser el producto de todos los primos $p$ satisfaciendo $$ p - 1 \leq p^{1-\delta}, $$ o $$ p^{1-\delta} \geq p-1 $$ como lo escribí por primera vez.

En mi primera respuesta a esta misma pregunta se dan ejemplos.

EEDDIITTTT: Jean-Louis Nicolas demostró, en 1983, que la Hipótesis de Riemann es verdadera si y sólo si, para todos los primoriales $P,$ $$ \frac{e^\gamma \phi(P) \log \log P}{P} < 1. $$ Muy bien, la referencia exacta es: Valores pequeños de la función de Euler. Journal of Number Theory, volumen 17 (1983), número 3, páginas 375-388.

Por otro lado, si RH es falsa, la desigualdad es verdadera para infinitos primoriales y falsa para infinitos. Así que, de cualquier manera, es verdadera para infinitos primoriales (una vez más, estos son $P = 2 \cdot 3 \cdot 5 \cdots p$ el producto de los primos consecutivos que empiezan por 2).

Por la razón que sea, el criterio de Guy Robin que fue alumno de Nicolás, llegó a ser más conocido.

Answer 4

En primer lugar: la función $\phi(n)$ no tiene el límite inferior en forma de una línea recta con una pendiente positiva.
Esto se deduce de la fórmula $$\dfrac{\phi(n)}n = \prod\limits_{p\,|\, n}\dfrac{p-1}p,$$ fórmula, que ilustra el no incremento de $\dfrac{\phi(n)}n$ .

El análisis de la fórmula lleva a las siguientes conclusiones para : $$\dfrac{\phi(np^k)}{np^k} = \begin{cases}\dfrac{\phi(n)}{n},\text{ if }p\,|\,n\\\dfrac{\phi(n)}{n}\dfrac{p-1}p,\text{ if }p\!\not|\:n\end{cases}$$ Estas conclusiones pueden ilustrarse con una mesa sencilla :

Por lo tanto, no es difícil demostrar que $$\dfrac{\phi(n)}n \geq H(n),$$ donde $H(n)$ es una función escalonada $$H(n) = \begin{cases} \dfrac12,\text{ if } n \in [2,6)\\ \dfrac13,\text{ if } n \in [6,30)\\ \dots\\ r_k,\text{ if } n \in [p_k\#, p_{k+1}\#)\\ \dots, \end{cases}$$
$\qquad p_k\# = \prod\limits_{i=1}^{k}p_i$ es primitivo , $$\left\{p_k\#\right\}=\{2,6,30,210,2310,30030,510510,96996900,223092870,6469693230,\dots\}$$ $$r_k = \dfrac1{p_k\#}\prod\limits_{i=1}^{k}(p_i-1),\dots, \quad \{r_k\}=\left\{\dfrac12,\dfrac13,\dfrac4{15},\dfrac8{35},\dfrac{16}{77},\dfrac{192}{1001},\dfrac{3072}{17017},\dfrac{55396}{323323},\dfrac{110592}{676039},\dfrac{442368}{2800733},\dots\right\}$$ $$\{p_i\}=\{2,3,5,\dots\}.$$ Esta función es susceptible de varias aproximaciones.

Como $p_i\geq i,$ entonces para no aumentar la consecuencia $R_k$ es una relación válida $$r_k = \prod\limits_{i=1}^k\left(1-\dfrac1{p_i}\right)\geq \prod\limits_{i=1}^k\left(1-\dfrac1{i+1}\right) = \dfrac1{k+1}.$$ Por otro lado, no es difícil demostrar que $$p_k\#\geq k(k+1).$$ Así que para $(k-1)k < n \leq k(k+1):$ $$\sqrt{n}>k-1,$$ $$\dfrac{\phi(n)}n \geq\dfrac1{k(k+1)}\phi\left(k(k+1)\right) \geq \dfrac {\phi(p_k\#)}{p_k\#}=r_k \geq \dfrac1{k+1} > \dfrac1{\sqrt n +2}.$$ $$\boxed{\phi(n) \geq \dfrac n{\sqrt n+2}},$$