$\varphi(2^n-1)/(2^n-1)$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3972
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

$\varphi(2^n-1)/(2^n-1)$

Messaggio da jordan » 18 ott 2017, 17:29

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.
$$
The only goal of science is the honor of the human spirit.

Avatar utente
Troleito br00tal
Messaggi: 679
Iscritto il: 16 mag 2012, 22:25

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da Troleito br00tal » 31 ott 2017, 20:31

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$.

Gerald Lambeau
Messaggi: 290
Iscritto il: 17 mag 2015, 13:32

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da Gerald Lambeau » 05 nov 2017, 19:02

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:
Testo nascosto:
sfruttare una certa connessione tra l'inverso di quel prodotto e la seria armonica
.
"Non ho rispetto per i miei superiori, figurati se ho rispetto per i miei pari: il rispetto di un uomo lo merita solo chi è a lui inferiore."
Cit. Marco (mio vero nome)

The Game.

Ci sono cose che non si possono confutare; per tutto il resto, c'è la fisica.

Avatar utente
jordan
Messaggi: 3972
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da jordan » 06 nov 2017, 12:33

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).
$$
The only goal of science is the honor of the human spirit.

Avatar utente
<enigma>
Messaggi: 873
Iscritto il: 24 set 2009, 16:44

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da <enigma> » 08 nov 2017, 11:31

Gerald Lambeau ha scritto:
05 nov 2017, 19:02
Il primo esercizio lasciato invece ancora mi sfugge
È un Mertens povero affatto semplice, perlomeno tecnicamente per un concorrente delle olimpiadi: la via più veloce che conosco è
Testo nascosto:
dimostrare l'identità $\sum_{n \leq x} \log n=\sum_{n \leq x}\Lambda(n) \left \lfloor x/n \right \rfloor$; sommare per parti $\sum_{n \leq x }\Lambda(n)/n$ e dedurne stime su $\sum _{p \leq x}1/p$; esponenziare e concludere
"Quello lì pubblica come un riccio!" (G.)
"Questo puoi mostrarlo o assumendo abc o assumendo GRH+BSD, vedi tu cos'è meno peggio..." (cit.)

Avatar utente
Troleito br00tal
Messaggi: 679
Iscritto il: 16 mag 2012, 22:25

Re: $\varphi(2^n-1)/(2^n-1)$

Messaggio da Troleito br00tal » 19 nov 2017, 23:08

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}

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 4 ospiti