Sia $k$ un intero positivo fissato. Dimostrare che esiste un intero positivo $n$ tale che tutte le seguenti equazioni non hanno alcuna soluzione negli interi:
$$\varphi(m)=n+i, \text{per ogni }i=1,2,\ldots,k$$
La funzione di Eulero ha parecchi buchi
La funzione di Eulero ha parecchi buchi
The only goal of science is the honor of the human spirit.
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: La funzione di Eulero ha parecchi buchi
Visto che nessuno posta, intanto scrivo io una soluzione puzzona e un po' barona.
Scelto \(r\) tale che \(2^{r+1} > k\), imponiamo che \( n \not \equiv -1, -2, \ldots, -k \pmod{2^{r+1} } \ \ (*) \).
In questo modo, visto che \( \omega(m)=s \ \ \Rightarrow \ \ 2^s \mid \varphi(m) \), sicuramente la soluzione \(m\) a
\[ \varphi(m) = n+i, \ \ i=1, \ldots, k\]
avrà al più \(r\) fattori primi. Richiamiamo il fatto che la densità asintotica dei numeri \(m\) con \(\omega(m) \le r\), fissato \(r\), è nulla (qui o qui) .
D'altronde, i numeri della forma \(\varphi(m)\) con \(\omega(m) \le r\) potrebbero essere anche meno: infatti può capitare che \(\varphi(a) = \varphi(b)\) con \(a,b\) distinti, ma non può capitare \(a=b\) con \(\varphi(a), \varphi(b)\) distinti. Dunque, anche l'insieme \(S_r = \{ \varphi(m): \omega(m) \le r\}\) ha densità asintotica nulla.
Questo fatto si riscrive come
\[ \lim_{n \to \infty } \frac{ S_r \cap [1,n] }{n} = 0\]
Dunque esiste un \(t_k\) tale che, per ogni \(t \ge t_k\) vale
\[\frac{ S_r \cap [1,t] }{t} < \frac{1}{3k} \]
Per comodità, prendiamo un \(\mathcal{l} \ge t_k\) divisibile per \(3k\). Dividiamo l'intervallo \([1, \mathcal{l} ]\) in intervalli lunghi \(3k\): ce n'è almeno uno, diciamo \(I\), in cui non compaiono elementi di \(S_r\), altrimenti la densità di \(S_r\) sarebbe maggiore di \( 1/3k\). La condizione \((*)\) ci "vieta" al massimo \(k\) numeri consecutivi di \(I\); anche se essi fossero al centro, comunque ci sarebbe un intervallo \([a, a+k-1] \subset I\) in cui non compaiono elementi di \(S_r\). Prendendo \(n=a\), otteniamo la tesi.
In realtà, notiamo che questo ci assicura l'esistenza di infiniti \(n\) siffatti. Detto \(n_k\) il numero trovato con questa costruzione, sicuramente \(n_{t_k} > t_k > n_k \) e \(n_{t_k}\) è soluzione anche per il caso \(k\). Iterando questo procedimento, possiamo trovarne infiniti.
Ribadisco, la soluzione è un po' rozza e un po' barona, e con un po' di impegno si può trovare, secondo me, anche una soluzione solo elementare.
Scelto \(r\) tale che \(2^{r+1} > k\), imponiamo che \( n \not \equiv -1, -2, \ldots, -k \pmod{2^{r+1} } \ \ (*) \).
In questo modo, visto che \( \omega(m)=s \ \ \Rightarrow \ \ 2^s \mid \varphi(m) \), sicuramente la soluzione \(m\) a
\[ \varphi(m) = n+i, \ \ i=1, \ldots, k\]
avrà al più \(r\) fattori primi. Richiamiamo il fatto che la densità asintotica dei numeri \(m\) con \(\omega(m) \le r\), fissato \(r\), è nulla (qui o qui) .
D'altronde, i numeri della forma \(\varphi(m)\) con \(\omega(m) \le r\) potrebbero essere anche meno: infatti può capitare che \(\varphi(a) = \varphi(b)\) con \(a,b\) distinti, ma non può capitare \(a=b\) con \(\varphi(a), \varphi(b)\) distinti. Dunque, anche l'insieme \(S_r = \{ \varphi(m): \omega(m) \le r\}\) ha densità asintotica nulla.
Questo fatto si riscrive come
\[ \lim_{n \to \infty } \frac{ S_r \cap [1,n] }{n} = 0\]
Dunque esiste un \(t_k\) tale che, per ogni \(t \ge t_k\) vale
\[\frac{ S_r \cap [1,t] }{t} < \frac{1}{3k} \]
Per comodità, prendiamo un \(\mathcal{l} \ge t_k\) divisibile per \(3k\). Dividiamo l'intervallo \([1, \mathcal{l} ]\) in intervalli lunghi \(3k\): ce n'è almeno uno, diciamo \(I\), in cui non compaiono elementi di \(S_r\), altrimenti la densità di \(S_r\) sarebbe maggiore di \( 1/3k\). La condizione \((*)\) ci "vieta" al massimo \(k\) numeri consecutivi di \(I\); anche se essi fossero al centro, comunque ci sarebbe un intervallo \([a, a+k-1] \subset I\) in cui non compaiono elementi di \(S_r\). Prendendo \(n=a\), otteniamo la tesi.
In realtà, notiamo che questo ci assicura l'esistenza di infiniti \(n\) siffatti. Detto \(n_k\) il numero trovato con questa costruzione, sicuramente \(n_{t_k} > t_k > n_k \) e \(n_{t_k}\) è soluzione anche per il caso \(k\). Iterando questo procedimento, possiamo trovarne infiniti.
Ribadisco, la soluzione è un po' rozza e un po' barona, e con un po' di impegno si può trovare, secondo me, anche una soluzione solo elementare.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: La funzione di Eulero ha parecchi buchi
Hai un po' barato usando quel risultato 
Del resto, non conosco una dimostrazione che sia sostanzialmente diversa: una stima quantitativa qui, come sopra l'idea è, in breve, che se fissiamo $k$ allora l'insieme degli interi con al massimo $k$ fattori primi ha densità asintotica nulla (meh, questo non è vero per altri tipi di "densità"
)
Del resto, non conosco una dimostrazione che sia sostanzialmente diversa: una stima quantitativa qui, come sopra l'idea è, in breve, che se fissiamo $k$ allora l'insieme degli interi con al massimo $k$ fattori primi ha densità asintotica nulla (meh, questo non è vero per altri tipi di "densità"
)The only goal of science is the honor of the human spirit.