Dal treno per Pisa

[ma_go]

dimostrare la stima $\phi(n)>\sqrt{n}$ mi sembra un buon esercizio.

EDIT: chiaramente dimostrare $\phi(n)>n$ era un po' difficile..

[Anér]

Non sono molto d'accordo, per esempio basta sapere la formula della $ \phi $ per dimostrare le stime $ \sqrt{n} $ e $ \frac{n}{(\log_2 n)+1} $, ed è sufficiente Eulero-Fermat per la stima $ \log_2 n $ (più o meno).

[ma_go]

stai implicitamente dicendo che il problema originale del thread non è un buon esercizio?

[staffo]

Allora, io ho provato.

Voglio dimostrare che $ \phi(n)>ln(n) $ a partire da un certo $ n $.
Io la $ \phi(n) $ l'ho considerata in questa maniera (che la approssima molto per difetto): la stima di Gauss sui numeri primi approssima per difetto il numero di primi da 1 ad n, e la stima è $ \frac{n}{ln(n)} $. Ora considero il numero massimo di fattori primi in n, che è $ log_2(n) $; adesso, mettendo pure che tutti questi fattori siano primi (cosa impossibile, sarebbero tutti due ma mettiamolo pure), ci saranno comunque un numero di numeri coprimi con n che sarà $ \frac{n}{ln(n)}-log_2(n) $. Tutto ciò approssima estremamente per difetto la funzione $ \phi $, ma questo è tanto meglio per quello che devo dimostrare.

Ora devo solo dimostrare che $ \frac{n}{ln(n)}-log_2(n)>ln(n) $
Attraverso un cambio di base e un po' di passaggi arrivo a $ n > ln^{2}(n) + \frac{ln^2(n)}{ln(2)} $

Ora lavoro per induzione: verifico il passo $ n_0=100 $, che è verificata.
Ora dunque (vediamo gli strafalcioni che faccio con l'induzione):
$ n +1 > ln^{2}(n) + \frac{ln^2(n)}{ln(2)} + 1 > ln^2(n+1) + \frac {ln^2(n+1)}{ln(2)} $
e questa cosa è vera (portando a destra i logaritmi della prima si ottiene una roba del tipo $ ln^2(n+1)-ln^2(n) $ che è molto piccola per valori di n abbastanza grandi (e per bbastanza grandi intendo maggiori di 5), e così anche l'altra. Andreebbe fatte un'induzione anche su quello per verificarla rigorosamente.

quindi $ \phi $ tende ad infinito
q.e.d.

[ndp15]

Si vede che mi hanno ingannato le date presenti su wolfram dopo la stima (che poi non è neanche una stima, poichè vale sempre a parte i casi $n=2$ e $n=6$) che ho postato, dato che sono recenti credevo fossero cose che richiedessero conoscenze avanzate di TDN e analisi per essere dimostrate. Evidentemente o le date non corrispondono alla data di dimostrazione del fatto, oppure i matematici non si sono dati da fare in precedenza (va anche detto che la cosa non è improbabile, soprattutto se si conoscevano già stime migliori).

[ndp15]

ci saranno comunque un numero di numeri coprimi con n che sarà $ \frac{n}{ln(n)}-log_2(n) $.

Mi perdo qualcosa io o stai considerando che i numeri coprimi a un certo $n$ sono solo numeri primi? Comunque partire dalla stima di Gauss sui primi non mi sembra molto meglio che partire già dalle stime postate in precedenza e che portano molto prima alla soluzione

[staffo]

esatto, io sto dicendo che i numeri coprimi sono solo i primi che non contiene n; questo non è vero, è sicuramente minore della $ \phi(n) $, però se è minore e dimostro che già questo è valido, allora varrà anche per la $ \phi(n) $

EDIT: per le varie stime, va beh, lo so che non è una dimostrazione rigorosa, ma volevo provarci lo stesso

[Anér]

stai implicitamente dicendo che il problema originale del thread non è un buon esercizio?

Scusa, stavo rispondendo a ndp15 che aveva detto:

Ci sarebbe anche la più comoda (soprattutto a livello mnemonico) $ ϕ(n)>n $ (sempre modulo casi piccoli). Il problema è che ho l'idea che nessuna di
queste sia facilmente dimostrabile.

[ndp15]

stai implicitamente dicendo che il problema originale del thread non è un buon esercizio?

Scusa, stavo rispondendo a ndp15 che aveva detto:

Ci sarebbe anche la più comoda (soprattutto a livello mnemonico) $ ϕ(n)>n $ (sempre modulo casi piccoli). Il problema è che ho l'idea che nessuna di
queste sia facilmente dimostrabile.

Mi pare che l'affermazione di ma_go fosse sensata proprio riferendosi alla tua risposta a me. Siccome quella stima è facile da dimostrare, anche l'esercizio sarà semplice dato che dalla stima si deduce subito che la successione diverge.

[ma_go]

stai implicitamente dicendo che il problema originale del thread non è un buon esercizio?

Scusa, stavo rispondendo a ndp15 [...]

nessun problema, piccola incomprensione
però mi pare che nessuno abbia ancora attaccato il problema.
la soluzione di staffo è (sostanzialmente) corretta, ma prima overkilla il problema (almeno la mia stima) e poi butta via tutto il guadagno che si ha usando il cannone (che probabilmente -come dice Anér= non è assolutamente necessario).

[jordan]

la soluzione di staffo è (sostanzialmente) corretta, ma prima overkilla il problema (almeno la mia stima) e poi butta via tutto il guadagno che si ha usando il cannone (che probabilmente -come dice Anér= non è assolutamente necessario).

Dire solo "overkilla" mi sembra anche riduttivo, visto che parte dall'ipotesi $ \pi(n) \ge C\cdot \frac{n}{\ln(n)} $ con $ C=1 $ . E' vero che imponendo un opportuno $ C\in \mathbb{R}\cap (0,1) $ e dimostrando la disuaglianza in via completamente elementare, possiamo sorvolare quest'ostacolo, ma resta comunque da dimostrarlo..

...però mi pare che nessuno abbia ancora attaccato il problema.

Eh si