Sia $\varepsilon>0$ fissato.
(a) Mostrare che esistono infiniti $n$ tali che
$$
\frac{\varphi(2^n-1)}{2^n-1}< \varepsilon.
$$
(b) Mostrare che esistono infiniti $n$ tali che
$$
\frac{\varphi(2^n-1)}{2^n-1}> 1-\varepsilon.
$$
$\varphi(2^n-1)/(2^n-1)$
$\varphi(2^n-1)/(2^n-1)$
The only goal of science is the honor of the human spirit.
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: $\varphi(2^n-1)/(2^n-1)$
Molto carino!
Ricordiamo la seguente formula:
\begin{equation}
\frac{\phi(n)}{n} = \prod_{p|n} (1-\frac{1}{p})
\end{equation}
a)
Sia $n \ge 3$ un intero positivo. Poniamo $x_n=\prod_{i=1}^n (p_i-1)$ dove $p_i$ è l'$i$-esimo primo. Notiamo che, per ogni $1 < i \le n$, $p_i$ divide $2^{x_n}-1$ per il piccolo teorema di Fermat, poiché $p_i-1$ divide $x_n$. Di conseguenza:
\begin{equation}
\frac{\phi(2^{x_n}-1)}{2^{x_n}-1} \le \prod_{i=2}^n (1-\frac{1}{p_i}) < \frac{2}{-1+\log{n}}
\end{equation}
dove la seconda disuguaglianza è un utile esercizio. Perciò, se $n>e^{1+2{\varepsilon}^{-1}}$, $\frac{\phi(2^{x_n}-1)}{2^{x_n}-1} < \varepsilon$.
b)
Vale il seguente utile fatto, dove $p$ e $q$ sono primi: se $p$ divide $2^q-1$, allora $q$ divide $p-1$. Questo implica banalmente $p>q$. In particolare, il numero di primi distinti che dividono $2^q-1$ è al più $\log_q{2^q}=q\log_q{2}$, poiché $2^q-1$ è prodotto di fattori maggiori di $q$. Perciò:
\begin{equation}
\frac{\phi(2^q-1)}{2^q-1} = \prod_{p|2^q-1}^n (1-\frac{1}{p}) \ge (1-\frac{1}{q+1})^{q\log_q{2}} = (1+\frac{1}{q})^{-q\log_q{2}} > e^{-\log_q{2}} \ge 1-\log_q{2}
\end{equation}
poiché $(1+\frac{1}{q})^{q} < e$ e $e^x \ge 1+x$. Entrambi sono lasciati come esercizi (mi dispiace lasciare tutti questi conti, ma forse è più utile se li scrive qualcuno che non abbia già visto un corso di Analisi I). Perciò, se $q>2^{\varepsilon^{-1}}$, vale $\frac{\phi(2^q-1)}{2^q-1}>1-\varepsilon$.
Ricordiamo la seguente formula:
\begin{equation}
\frac{\phi(n)}{n} = \prod_{p|n} (1-\frac{1}{p})
\end{equation}
a)
Sia $n \ge 3$ un intero positivo. Poniamo $x_n=\prod_{i=1}^n (p_i-1)$ dove $p_i$ è l'$i$-esimo primo. Notiamo che, per ogni $1 < i \le n$, $p_i$ divide $2^{x_n}-1$ per il piccolo teorema di Fermat, poiché $p_i-1$ divide $x_n$. Di conseguenza:
\begin{equation}
\frac{\phi(2^{x_n}-1)}{2^{x_n}-1} \le \prod_{i=2}^n (1-\frac{1}{p_i}) < \frac{2}{-1+\log{n}}
\end{equation}
dove la seconda disuguaglianza è un utile esercizio. Perciò, se $n>e^{1+2{\varepsilon}^{-1}}$, $\frac{\phi(2^{x_n}-1)}{2^{x_n}-1} < \varepsilon$.
b)
Vale il seguente utile fatto, dove $p$ e $q$ sono primi: se $p$ divide $2^q-1$, allora $q$ divide $p-1$. Questo implica banalmente $p>q$. In particolare, il numero di primi distinti che dividono $2^q-1$ è al più $\log_q{2^q}=q\log_q{2}$, poiché $2^q-1$ è prodotto di fattori maggiori di $q$. Perciò:
\begin{equation}
\frac{\phi(2^q-1)}{2^q-1} = \prod_{p|2^q-1}^n (1-\frac{1}{p}) \ge (1-\frac{1}{q+1})^{q\log_q{2}} = (1+\frac{1}{q})^{-q\log_q{2}} > e^{-\log_q{2}} \ge 1-\log_q{2}
\end{equation}
poiché $(1+\frac{1}{q})^{q} < e$ e $e^x \ge 1+x$. Entrambi sono lasciati come esercizi (mi dispiace lasciare tutti questi conti, ma forse è più utile se li scrive qualcuno che non abbia già visto un corso di Analisi I). Perciò, se $q>2^{\varepsilon^{-1}}$, vale $\frac{\phi(2^q-1)}{2^q-1}>1-\varepsilon$.
- Gerald Lambeau
- Messaggi: 335
- Iscritto il: 17 mag 2015, 13:32
- Località: provincia di Lucca
Re: $\varphi(2^n-1)/(2^n-1)$
Facciamo gli esercizi gentilmente lasciatici da Troleito.
Inizio da $e^x \ge x+1$. Consideriamo $e^x-x$. Voglio mostrare che $\displaystyle \lim_{x \rightarrow \pm\infty} e^x-x=+\infty$.
Se $x$ tende a meno infinito si ha $\displaystyle \lim_{x \rightarrow -\infty} e^x-x=\lim_{x \rightarrow -\infty} e^x+\lim_{x \rightarrow -\infty} -x=0+\infty=+\infty$. Per l'altro limite invece ci serviamo di un altro passaggio: $e^x \ge 2x$ per $x$ sufficientemente grande. Lo dimostreremo passando prima per l'induzione sui naturali. $e^1 \ge 2 \cdot 1$, quindi il passo base è ok. $e^{n+1}=e \cdot e^n \ge e \cdot 2 \cdot n \ge 4 \cdot n \ge 2(n+1)$ per $n\ge1$, quindi anche il passo induttivo è ok.
Ora, scelto $1<y<2$, voglio $e^{n+y}>2(n+y)$ per $n$ sufficientemente grande (si noti che così vado a dimostrarlo per $x \ge n+1$ dove $n$ è quello che vedremo, ma poco importa perché a noi la disuguaglianza ci serve per dimostrare un limite all'infinito).
$e^{n+y}=e^n \cdot e^y \ge e^y \cdot 2n$. Ora, $e^y \cdot 2n \ge 2(n+y) \Leftrightarrow e^y \ge 1+2\dfrac{y}{n}$, ma questa è sempre vera per $n \ge \dfrac{4}{e-1}$ per come è stato scelto $y$.
Bene, $e^x \ge 2x \Rightarrow e^x-x \ge x$, e siccome $\displaystyle \lim_{x \rightarrow +\infty} x=+\infty$, anche la nostra funzione si comporta così, che è quello che ci piaceva.
Che ci facciamo con tutta questa roba? Semplice, il fatto che $e^x-x$ sia continua (è differenza di funzioni continue) in $\mathbb{R}$ e che all'infinito, da entrambe le parti, diventi molto grossa (e non molto piccola, che sennò era un problema), ci permette di scegliere un intervallo sufficientemente largo, diciamo $[-10^{100}, 10^{100}]$, e direi che possiamo stare sicuri di trovare il minimo lì dentro.
Non sto a verificare tutte le ipotesi, ma direi che siamo tutti d'accordo che il minimo si trova, per Weierstrass, o sugli estremi (ma li abbiamo scelti belli larghi quindi chissene) o dove la derivata si annulla.
La derivata è $e^x-1$ che è nulla in $x=0$ e in nessun altro punto, quindi il minimo di $e^x-x$ è $e^0-0=1$, perciò $e^x \ge x+1$ e siamo tutti felici.
Adesso liquidiamo $\left(1+\dfrac{1}{q}\right)^q<e$ ponendo $q=\dfrac{1}{e^x-1}$ con $x \not=0$, che si può fare senza problemi perché $q \ge 2$. La disuguaglianza diventa $e^{\frac{x}{e^x-1}}<e \Leftrightarrow \dfrac{x}{e^x-1}<1 \Leftrightarrow x+1<e^x$ (quest'utlimo passaggio è legale perché, essendo $q$ positivo, anche $e^x-1$ deve esserlo, e dunque moltiplicare non cambia il verso della disuguaglianza) e direi che è sempre vero per quanto detto prima. L'uguale si può trovare solo nei punti di minimo di $e^x-x$, ma abbiamo visto che l'unico è $x=0$ che abbiamo escluso, quindi... Volendo si può dire che se $x$ tende a $0$, cioè se $q$ tende a infinito, quel minore diventa un uguale, ottenendo così il limite noto $\displaystyle \lim_{x \rightarrow +\infty} \left(1+\frac{1}{x}\right)^x=e$.
Scusate se sono sceso troppo nel dettaglio, ma (anche per la scuola, diciamo) voglio farle bene queste cose, quindi se c'è qualche castroneria ditemelo.
Il primo esercizio lasciato invece ancora mi sfugge, ma se qualcuno volesse un'altra strada per dimostrare che $\displaystyle \prod_{i=2}^{\infty} \left(1-\frac{1}{p_i}\right)=0$, vi suggerisco questa che ho trovato che è molto carina:.
Inizio da $e^x \ge x+1$. Consideriamo $e^x-x$. Voglio mostrare che $\displaystyle \lim_{x \rightarrow \pm\infty} e^x-x=+\infty$.
Se $x$ tende a meno infinito si ha $\displaystyle \lim_{x \rightarrow -\infty} e^x-x=\lim_{x \rightarrow -\infty} e^x+\lim_{x \rightarrow -\infty} -x=0+\infty=+\infty$. Per l'altro limite invece ci serviamo di un altro passaggio: $e^x \ge 2x$ per $x$ sufficientemente grande. Lo dimostreremo passando prima per l'induzione sui naturali. $e^1 \ge 2 \cdot 1$, quindi il passo base è ok. $e^{n+1}=e \cdot e^n \ge e \cdot 2 \cdot n \ge 4 \cdot n \ge 2(n+1)$ per $n\ge1$, quindi anche il passo induttivo è ok.
Ora, scelto $1<y<2$, voglio $e^{n+y}>2(n+y)$ per $n$ sufficientemente grande (si noti che così vado a dimostrarlo per $x \ge n+1$ dove $n$ è quello che vedremo, ma poco importa perché a noi la disuguaglianza ci serve per dimostrare un limite all'infinito).
$e^{n+y}=e^n \cdot e^y \ge e^y \cdot 2n$. Ora, $e^y \cdot 2n \ge 2(n+y) \Leftrightarrow e^y \ge 1+2\dfrac{y}{n}$, ma questa è sempre vera per $n \ge \dfrac{4}{e-1}$ per come è stato scelto $y$.
Bene, $e^x \ge 2x \Rightarrow e^x-x \ge x$, e siccome $\displaystyle \lim_{x \rightarrow +\infty} x=+\infty$, anche la nostra funzione si comporta così, che è quello che ci piaceva.
Che ci facciamo con tutta questa roba? Semplice, il fatto che $e^x-x$ sia continua (è differenza di funzioni continue) in $\mathbb{R}$ e che all'infinito, da entrambe le parti, diventi molto grossa (e non molto piccola, che sennò era un problema), ci permette di scegliere un intervallo sufficientemente largo, diciamo $[-10^{100}, 10^{100}]$, e direi che possiamo stare sicuri di trovare il minimo lì dentro.
Non sto a verificare tutte le ipotesi, ma direi che siamo tutti d'accordo che il minimo si trova, per Weierstrass, o sugli estremi (ma li abbiamo scelti belli larghi quindi chissene) o dove la derivata si annulla.
La derivata è $e^x-1$ che è nulla in $x=0$ e in nessun altro punto, quindi il minimo di $e^x-x$ è $e^0-0=1$, perciò $e^x \ge x+1$ e siamo tutti felici.
Adesso liquidiamo $\left(1+\dfrac{1}{q}\right)^q<e$ ponendo $q=\dfrac{1}{e^x-1}$ con $x \not=0$, che si può fare senza problemi perché $q \ge 2$. La disuguaglianza diventa $e^{\frac{x}{e^x-1}}<e \Leftrightarrow \dfrac{x}{e^x-1}<1 \Leftrightarrow x+1<e^x$ (quest'utlimo passaggio è legale perché, essendo $q$ positivo, anche $e^x-1$ deve esserlo, e dunque moltiplicare non cambia il verso della disuguaglianza) e direi che è sempre vero per quanto detto prima. L'uguale si può trovare solo nei punti di minimo di $e^x-x$, ma abbiamo visto che l'unico è $x=0$ che abbiamo escluso, quindi... Volendo si può dire che se $x$ tende a $0$, cioè se $q$ tende a infinito, quel minore diventa un uguale, ottenendo così il limite noto $\displaystyle \lim_{x \rightarrow +\infty} \left(1+\frac{1}{x}\right)^x=e$.
Scusate se sono sceso troppo nel dettaglio, ma (anche per la scuola, diciamo) voglio farle bene queste cose, quindi se c'è qualche castroneria ditemelo.
Il primo esercizio lasciato invece ancora mi sfugge, ma se qualcuno volesse un'altra strada per dimostrare che $\displaystyle \prod_{i=2}^{\infty} \left(1-\frac{1}{p_i}\right)=0$, vi suggerisco questa che ho trovato che è molto carina:
Testo nascosto:
"If only I could be so grossly incandescent!"
Re: $\varphi(2^n-1)/(2^n-1)$
Molto bene! Allora vi lascio anche un bonus:
(c) Mostrare che per ogni intervallo $0\le a<b\le 1$ esistono infiniti $n$ tali che
$$
\frac{\varphi(2^n-1)}{2^n-1} \in (a,b).
$$
(c) Mostrare che per ogni intervallo $0\le a<b\le 1$ esistono infiniti $n$ tali che
$$
\frac{\varphi(2^n-1)}{2^n-1} \in (a,b).
$$
The only goal of science is the honor of the human spirit.
Re: $\varphi(2^n-1)/(2^n-1)$
È un Mertens povero affatto semplice, perlomeno tecnicamente per un concorrente delle olimpiadi: la via più veloce che conosco è
Testo nascosto:
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: $\varphi(2^n-1)/(2^n-1)$
Posto la mia dimostrazione di
\begin{equation}
\prod_{i=2}^n (1-\frac{1}{p_i}) < \frac{2}{-1 + \log{n}}
\end{equation}
che tra l'altro segue la linea di dimostrazione accennata di Gerald Lambeau. Consideriamo l'inverso dell'LHS
\begin{equation}
(1-\frac{1}{2})^{-1} \prod_{i=2}^n (1-\frac{1}{p_i})^{-1} = \sum_{f(k) \le p_n} \frac{1}{k} \ge \sum_{i=1}^{p_n} \frac{1}{i} > \log{p_n} > \log{n}
\end{equation}
dove $f(m)$ è il più grande primo che divide $m$. Perciò
\begin{equation}
\prod_{i=2}^n (1-\frac{1}{p_i}) < \frac{2}{\log{n}} < \frac{2}{-1 + \log{n}}
\end{equation}
\begin{equation}
\prod_{i=2}^n (1-\frac{1}{p_i}) < \frac{2}{-1 + \log{n}}
\end{equation}
che tra l'altro segue la linea di dimostrazione accennata di Gerald Lambeau. Consideriamo l'inverso dell'LHS
\begin{equation}
(1-\frac{1}{2})^{-1} \prod_{i=2}^n (1-\frac{1}{p_i})^{-1} = \sum_{f(k) \le p_n} \frac{1}{k} \ge \sum_{i=1}^{p_n} \frac{1}{i} > \log{p_n} > \log{n}
\end{equation}
dove $f(m)$ è il più grande primo che divide $m$. Perciò
\begin{equation}
\prod_{i=2}^n (1-\frac{1}{p_i}) < \frac{2}{\log{n}} < \frac{2}{-1 + \log{n}}
\end{equation}
- Gerald Lambeau
- Messaggi: 335
- Iscritto il: 17 mag 2015, 13:32
- Località: provincia di Lucca
Re: $\varphi(2^n-1)/(2^n-1)$
Visto che è un po' difficile, c'è la soluzione su quest'articolo di Florian Luca (le domande "elementari" erano le prime due)
The only goal of science is the honor of the human spirit.