Para todos $n$ existe $x$ tal que $\varphi(x)<\varphi(x+1)<\ldots<\varphi(x+n)$

Question

Sea $\varphi$ sea la función de Euler, es decir $\varphi(n)$ representa el número de números enteros $m \in \{1,\ldots,n\}$ tal que $\text{gcd}(m,n)=1$ .

Sea $n\ge 2$ sea un número entero positivo. Demostrar que existen infinitas $x$ para lo cual
$$ \varphi(x)<\varphi(x+1)<\ldots<\varphi(x+n). $$

[Es una generalización de un concurso de matemáticas en el que se hace la misma pregunta para $n=2$ conozco la respuesta, y es positiva].

Answer 1

En la siguiente $p$ siempre denotará un número primo. $p_k$ será el $k$ -primo. Es evidente que basta con demostrar que, dado $0\le x_i<y_i\le\alpha$ ( $i=0,\dots,n$ ), siempre podemos encontrar $x$ s.t. $\phi(x+i)\in(x_i,y_i)$ para cualquier $i$ . Aquí $\alpha:=\prod_{p\le n+1}\frac{p-1}{p}$ .

Primero demostramos este lema crucial, que en particular da la tesis para $n=0$ :

Lema. Dado $0\le x<y\le 1$ y cualquier $z\in\mathbb{N}$ existe un conjunto $A$ de primos $>z$ s.t. $m:=\prod_{p\in A}p$ satisface $x<\frac{\phi(m)}{m}<y$ .
Recordamos que $\frac{\phi(m)}{m}=\prod_{p\in A}\frac{p-1}{p}$ .
Prueba. Elige cualquier primo $p_k>z$ s.t. $\frac{p_k-1}{p_k}>x$ . Desde $\prod_p\frac{p-1}{p}=0$ (lo que se deduce de la conocida divergencia de $\sum_p\frac{1}{p}$ ) existe un máximo $\ell\ge k$ s.t. $\prod_{j=k}^\ell\frac{p_j-1}{p_j}>x$ . Pon todos los primos $p_k,\dots,p_\ell$ en el conjunto $A$ y buscar otro $k'>\ell$ s.t. $\left(\prod_{j=k}^\ell\frac{p_j-1}{p_j}\right)\frac{p_{k'}-1}{p_{k'}}>x$ y otra vez existe un máximo $\ell'\ge k'$ para lo cual $$\left(\prod_{j=k}^\ell\frac{p_j-1}{p_j}\right)\left(\prod_{j=k'}^{\ell'}\frac{p_j-1}{p_j}\right)>x$$ retenciones. Añada $p_{k'},\dots,p_{\ell'}$ a $A$ e iterar este procedimiento. Tras un número finito de pasos obtendremos el $A$ desde $\frac{p-1}{p}\to 1$ como $p\to\infty$ (por lo que si un número real positivo $t$ es tal que $t>x$ y $t\frac{p-1}{p}\le x$ para algunos grandes $p$ , tendremos $t<y$ ). $\blacksquare$

Establecer $q:=\prod_{p\le n+1}q$ . Aplicando el lema $n+1$ veces, encontramos conjuntos disjuntos $A_0,\dots,A_n$ de primos $>n+1$ tal que, llamando a $s_i:=\prod_{p\in A_i}p$ , tenemos $x_i\frac{(q,i)}{\phi((q,i))}<\frac{\phi(s_i)}{s_i}<y_i\frac{(q,i)}{\phi((q,i))}$ . Aquí $(q,i)=\text{gcd}(q,i)$ . Esto puede hacerse ya que $\frac{(q,i)}{\phi((q,i))}\le\frac{1}{\alpha}$ mientras que $x_i,y_i\le \alpha$ . La razón de esta elección de los intervalos se verá enseguida.

Ahora dejemos que $M$ ser muy grande y llamar $B$ el conjunto de los primos $p_j>n+1$ con $j\le M$ que no pertenecen a ningún $A_i$ es decir $$B:=\{p_j\mid j\le M\}\setminus\left(\{1,\dots,n+1\}\cup\bigcup_{i=0}^n A_i\right),$$ y establece $b:=\prod_{p\in B}p$ . El Teorema Chino del Resto nos permite resolver este sistema de congruencias: $$\begin{cases}x\equiv 0\pmod{qs_0} \\ x+i\equiv 0\pmod{s_i}\ \forall i=1,\dots,n \\ x-1\equiv 0\pmod{b}\end{cases}$$ Afirmamos que, para $M$ suficientemente grande, la solución positiva más pequeña $x$ de este sistema es el que estamos buscando. De hecho, si $p\mid x+i$ (para cualquier $i=0,\dots,n$ ), entonces hay tres casos:

• $p\le n+1$
• $p\in A_i$
• $p=p_j$ para algunos $j>M$ .

No hay otras posibilidades (de lo contrario $p\in A_{i'}$ para algunos $i'\neq i$ o $p\in B$ así que $p\mid x+i'$ o $p\mid x-1$ pero ninguna de ellas es posible, como $p$ dividiría entonces un número $\le n+1$ ). Obsérvese que para los dos primeros casos se cumple la inversa adecuada, es decir, cada primo en $A_i$ divide $x+i$ mientras que cada primo $p\le n+1$ divide $x+i$ si $p\mid i$ gracias a que $p\mid q\mid x$ .

Así $$\frac{\phi(x+i)}{x+i}=\prod_{p\mid (q,i)}\frac{p-1}{p}\prod_{p\in A_i}\frac{p-1}{p}\prod_{p_j\mid x+i,\ j>M}\frac{p_j-1}{p_j}$$ y $\prod_{p\mid (q,i)}\frac{p-1}{p}=\frac{\phi((q,i))}{(q,i)}$ por lo que por las estimaciones satisfechas por $s_i$ obtenemos $$\prod_{p\mid (q,i)}\frac{p-1}{p}\prod_{p\in A_i}\frac{p-1}{p}=\frac{\phi((q,i))}{(q,i)}s_i\in(x_i,y_i).$$ Para concluir sólo tenemos que demostrar que el último producto tiende a $1$ como $M\to \infty$ . Pero por minimalidad $x<\prod_{j=1}^M p_j$ por lo que (para $M$ grande) $x+i<\prod_{j=1}^{M+1} p_j$ Así pues $x+i$ tiene como máximo $M$ factores primos distintos. Así que $$1\ge \prod_{p_j\mid x+i,\ j>M}\frac{p_j-1}{p_j}=\prod_{p_j\mid x+i,\ j>M}\left(1-\frac{1}{p_j}\right)\ge\left(1-\frac{1}{p_M}\right)^M$$ y por lo tanto $$\liminf_{M\to\infty}\left(1-\frac{1}{p_M}\right)^M\ge\liminf_{M\to\infty}\left(1-\frac{1}{aM}\right)^M=e^{-\frac{1}{a}}$$ para cualquier $a>0$ donde utilizamos una estimación muy laxa $p_M\ge aM$ (para $M$ suficientemente grande en función de $a$ ). Envío de $a\to\infty$ obtenemos $\liminf_{M\to\infty}\left(1-\frac{1}{p_M}\right)^M\ge 1$ lo que da $\lim_{M\to\infty}\prod_{p_j\mid x+i,\ j>M}\frac{p_j-1}{p_j}=1$ (tenga en cuenta que $x$ depende de $M$ !).

Esto también muestra el resultado mencionado por Erick Wong en los comentarios.

Answer 2

Respuesta parcial: Imponemos las condiciones de divisibilidad adecuadas mediante el siguiente algoritmo:

1. Asignar $a_k\leftarrow\frac{\phi(k)}{k}$ para $1\le k\le n+1$ . Sea $N\leftarrow n+1$ . Sea $S\leftarrow(n+1)\mathbb N$
2. Si $a_1<a_2<\ldots <a_n$ termina.
3. Sea $i$ sea maximal con $a_i\ge a_{i+1}$ .
4. Sea $p$ sea el primo más pequeño $>N$ .
5. Sea $a_i\leftarrow a_i\cdot\left(1-\frac1p\right)$ , $S\leftarrow S\cap\left(p\mathbb Z-i\right)$ , $N\leftarrow p$ y vuelve al paso 2.

Se garantiza que el algoritmo termina porque $\prod\left(1-\frac1p\right)$ diverge hacia $0$ . Una vez que termina, tenemos la siguiente situación: Para $1\le i\le n$ y $p$ prime $\le N$ o bien $p\mid s+i$ para todos $s\in S$ o $p\nmid s+i$ para todos $s\in S$ . De hecho obtenemos $$ \frac{\phi(s+i)}{s+i}=a_i\prod_{p|s+i\atop p>N}\left(1-\frac1p\right)$$ para todos $s\in S$ (esta condición se cumple siempre que entramos en el paso 2). Esto nos permite concluir $\phi(s+1)<\phi(s+2)<\ldots<\phi(s+n+1)$ siempre que $\prod_{p|s+i\atop p>N}\left(1-\frac1p\right)$ está siempre suficientemente cerca de $1$ . La pregunta es: ¿podemos conseguirlo?