Ricordando vecchi bound su \pi(n)
Ricordando vecchi bound su \pi(n)
Spulciando qualche esercizio Hailiano di non molto tempo fa, si riesce ad affermare:
"Utilizzando risultati completamente elementari (e non sottointendendo alcun fatto noto), mostrare che, comunque venga scelto $ (x,y) \in \mathbb{R}^2 $ tale che $ x>0 $, esiste un intero positivo $ h(x,y) $ tale che $ nx+y>\pi(n) $ per ogni intero $ n > h(x,y) $."
Come solito, qui $ \pi(n) $ sta a indicare il numero di primi minori o uguali a n.
"Utilizzando risultati completamente elementari (e non sottointendendo alcun fatto noto), mostrare che, comunque venga scelto $ (x,y) \in \mathbb{R}^2 $ tale che $ x>0 $, esiste un intero positivo $ h(x,y) $ tale che $ nx+y>\pi(n) $ per ogni intero $ n > h(x,y) $."
Come solito, qui $ \pi(n) $ sta a indicare il numero di primi minori o uguali a n.
The only goal of science is the honor of the human spirit.
Piuttosto che lasciar morire questo topic comincio i miei deliri, che giusto per piacere a jordan non sono nè una dimostrazione nè tantomeno una dimostrazione elementare.
Provo con una variante più semplice ponendo y=0 (ovviamente con x>=1 il problema è banale anche con la y).
Il problema proposto si trasforma quindi nel provare la:
affermazione1: per ogni x in R esiste h tale che se $ n\ge h $ allora $ \pi(n)<nx $. Poichè per $ x\ge 1 $ il problema è banale (ossia si risolve semplicemente osservando che $ \pi(n)<n $) restringo x in (0,1). pongo $ x:=\frac{1}{d} $ (se x è irrazionale o della forma m/n con (m,n)=1 e m diverso da 1 lo faccio per difetto e questo non dovrebbe cambiare le cose) e trasformo la tesi in questa:
affermazione2: per ogni d in N esiste h t.c. se $ n\ge h $ allora $ d\pi(n)<n $. Allora deve valere quest'altra tesi: per ogni d in N esiste h t.c. se $ n\ge h $ allora $ 1/d>\pi(n)/n $. Ricorda molto la definizione di limite di una successione allora dico che l'affermazione 1 è provata sse è provata la
affermazione3: la successione $ s_n:=\pi(n)/n $ converge al limite 0. E il problema è proprio dimostrare questo in maniera elementare.
Assumiamo come verità di fede che $ \varphi(n)>\pi(n) $ per ogni n (o che quantomeno esiste una sottosuccessione infinita di N per cui vale la disuguaglianza), allora dividendo entrambi i membri per n ottengo
$ \prod (1-1/p_i)>s_n $ e azzardo un passaggio ai limiti
$ \lim \inf \prod (1-1/p_i)>\lim \sup s_n $
ma $ \lim \inf \prod (1-1/p_i)=\lim \inf \frac{1}{\prod \frac{1}{p_i-1} \prod p_i}=\lim \inf \frac{1}{\prod {p_i}}\frac{1}{\zeta(-1)}=0 $ (per la formula prodotto di Eulero).
da cui $ \lim \sup s_n=0 $.
Più avanti provo a postare qualcosa per rendere credibile la disuguaglianza tra phi e pi (e per rendere credibili i limiti dopo). Sono grati commenti, anche pessimi
Provo con una variante più semplice ponendo y=0 (ovviamente con x>=1 il problema è banale anche con la y).
Il problema proposto si trasforma quindi nel provare la:
affermazione1: per ogni x in R esiste h tale che se $ n\ge h $ allora $ \pi(n)<nx $. Poichè per $ x\ge 1 $ il problema è banale (ossia si risolve semplicemente osservando che $ \pi(n)<n $) restringo x in (0,1). pongo $ x:=\frac{1}{d} $ (se x è irrazionale o della forma m/n con (m,n)=1 e m diverso da 1 lo faccio per difetto e questo non dovrebbe cambiare le cose) e trasformo la tesi in questa:
affermazione2: per ogni d in N esiste h t.c. se $ n\ge h $ allora $ d\pi(n)<n $. Allora deve valere quest'altra tesi: per ogni d in N esiste h t.c. se $ n\ge h $ allora $ 1/d>\pi(n)/n $. Ricorda molto la definizione di limite di una successione allora dico che l'affermazione 1 è provata sse è provata la
affermazione3: la successione $ s_n:=\pi(n)/n $ converge al limite 0. E il problema è proprio dimostrare questo in maniera elementare.
Assumiamo come verità di fede che $ \varphi(n)>\pi(n) $ per ogni n (o che quantomeno esiste una sottosuccessione infinita di N per cui vale la disuguaglianza), allora dividendo entrambi i membri per n ottengo
$ \prod (1-1/p_i)>s_n $ e azzardo un passaggio ai limiti
$ \lim \inf \prod (1-1/p_i)>\lim \sup s_n $
ma $ \lim \inf \prod (1-1/p_i)=\lim \inf \frac{1}{\prod \frac{1}{p_i-1} \prod p_i}=\lim \inf \frac{1}{\prod {p_i}}\frac{1}{\zeta(-1)}=0 $ (per la formula prodotto di Eulero).
da cui $ \lim \sup s_n=0 $.
Più avanti provo a postare qualcosa per rendere credibile la disuguaglianza tra phi e pi (e per rendere credibili i limiti dopo). Sono grati commenti, anche pessimi
Aboliamo il latino nei licei scientifici!
- federiko97
- Messaggi: 44
- Iscritto il: 03 nov 2008, 20:36
- Località: Roma
Allora, alcune cose che mi va di dire al mondo:
1) jordan si diverte a complicare gli enunciati, ma l'aggiunta di quel +y è del tutto irrilevante. In realtà "per ogni reale positivo x si ha che, per n sufficientemente grande, $ nx>\pi(x)" $è una formulazione equivalente.
2) Giulius: ho l'impressione che tu abbia dato per scontato l'esistenza di dei limiti che potrebbero non esistere e in effetti temo non esistano ($ \frac{\phi(n)}{n} $ oscilla tra 0 e 1 ma non converge, quindi temo che il passaggio con lim inf e lim sup non sia vero)
3) Una dimostrazione sborona che sfrutta un fatto olimpicamente noto: pongo $ \displaystyle f(n) =\prod_{p\le n} p $ (dove la produttoria è calcolata sui primi, in sostanza è il prodotto dei numeri primi da 1 a n) e ora si ha $ f(n)<4^n $.
Si dimostra per induzione: in 1 quella cosa significa $ 1< 4 $ (la produttoria sull'insieme vuoto fa 1). Per passare da n a n+1 (con n dispari) è facile, perché a destra moltiplico per 4, a sinistra non moltiplico nulla perché se n è pari non è primo (tranne n=2 che è comunque minore di 4). Per dimostrare che la tesi è vera per 2n+1, supponendo che sia vera per valori più piccoli faccio così: $ f(2n+1)\le f(n+1){2n+1\choose n} $ (i primi maggiori di n+1 dividono il binomiale) ma $ f(n)<4^n $ per ipotesi e $ {2n+1\choose n}\le 2^{2n} $ per ovvi motivi, quindi abbiamo concluso.
Ora poniamo $ \theta(n)=\log(f(n)) $. E' chiaro che, per ogni x reale positivo fissato, si ha, per n sufficientemente grande $ \displaystyle\frac{\theta(n)}{\pi(n)}>\frac{\log(4)}{x} $ (a sinistra ho la media aritmetica dei logaritmi dei primi tra 1 e n: visto che i logaritmi di tali primi tendono a infinito, così fa anche la media). Unendo questo a $ \theta(n)<n\log(4) $ abbiamo la tesi.
1) jordan si diverte a complicare gli enunciati, ma l'aggiunta di quel +y è del tutto irrilevante. In realtà "per ogni reale positivo x si ha che, per n sufficientemente grande, $ nx>\pi(x)" $è una formulazione equivalente.
2) Giulius: ho l'impressione che tu abbia dato per scontato l'esistenza di dei limiti che potrebbero non esistere e in effetti temo non esistano ($ \frac{\phi(n)}{n} $ oscilla tra 0 e 1 ma non converge, quindi temo che il passaggio con lim inf e lim sup non sia vero)
3) Una dimostrazione sborona che sfrutta un fatto olimpicamente noto: pongo $ \displaystyle f(n) =\prod_{p\le n} p $ (dove la produttoria è calcolata sui primi, in sostanza è il prodotto dei numeri primi da 1 a n) e ora si ha $ f(n)<4^n $.
Si dimostra per induzione: in 1 quella cosa significa $ 1< 4 $ (la produttoria sull'insieme vuoto fa 1). Per passare da n a n+1 (con n dispari) è facile, perché a destra moltiplico per 4, a sinistra non moltiplico nulla perché se n è pari non è primo (tranne n=2 che è comunque minore di 4). Per dimostrare che la tesi è vera per 2n+1, supponendo che sia vera per valori più piccoli faccio così: $ f(2n+1)\le f(n+1){2n+1\choose n} $ (i primi maggiori di n+1 dividono il binomiale) ma $ f(n)<4^n $ per ipotesi e $ {2n+1\choose n}\le 2^{2n} $ per ovvi motivi, quindi abbiamo concluso.
Ora poniamo $ \theta(n)=\log(f(n)) $. E' chiaro che, per ogni x reale positivo fissato, si ha, per n sufficientemente grande $ \displaystyle\frac{\theta(n)}{\pi(n)}>\frac{\log(4)}{x} $ (a sinistra ho la media aritmetica dei logaritmi dei primi tra 1 e n: visto che i logaritmi di tali primi tendono a infinito, così fa anche la media). Unendo questo a $ \theta(n)<n\log(4) $ abbiamo la tesi.
Io credo che alcune entità superiori, pur non avendo odore, possano esistere. Esse influenzano le nostre vite in maniera che nessuno scienziato può comprendere.
Complimenti bella soluzione, in effetti non ci avevo pensato =S.
Sulla questione dei limiti hai ragione ne ero ben conscio anche se cmq i limiti esistono, poichè esiste la sottosuccessione di N che prende tutti i primi che è la sottosuccessione che converge al limite maggiore di pi(n)/n (che è 0 come hai anche mostrato e quindi pari per forza al lim inf e quindi detto semplicemente lim) e per quanto riguarda phi(n)/n ha sia lim sup che è raggiunto dalla sottosuccessione che prende i primi (infatti phi (p)/p tende a 1 per p che tende a infinito) sia lim inf che è raggiunto per esempio dai numeri altamente composti e che è 0. A questo punto credo che il problema stia nel fatto che non posso prendere i limiti poichè lim inf da una parte e limite sup dall'altra non sono realizzati dalla stessa sottosuccessione. Almeno credo sia questo il problema perchè non è che mi intenda molto di analisi percui se qualcuno può darmi delucidazioni lo ringrazio in anticipo.
Sulla questione dei limiti hai ragione ne ero ben conscio anche se cmq i limiti esistono, poichè esiste la sottosuccessione di N che prende tutti i primi che è la sottosuccessione che converge al limite maggiore di pi(n)/n (che è 0 come hai anche mostrato e quindi pari per forza al lim inf e quindi detto semplicemente lim) e per quanto riguarda phi(n)/n ha sia lim sup che è raggiunto dalla sottosuccessione che prende i primi (infatti phi (p)/p tende a 1 per p che tende a infinito) sia lim inf che è raggiunto per esempio dai numeri altamente composti e che è 0. A questo punto credo che il problema stia nel fatto che non posso prendere i limiti poichè lim inf da una parte e limite sup dall'altra non sono realizzati dalla stessa sottosuccessione. Almeno credo sia questo il problema perchè non è che mi intenda molto di analisi percui se qualcuno può darmi delucidazioni lo ringrazio in anticipo.
Aboliamo il latino nei licei scientifici!
federiko97 ha scritto: in effetti temo non esistano ($ \frac{\phi(n)}{n} $ oscilla tra 0 e 1 ma non converge, quindi temo che il passaggio con lim inf e lim sup non sia vero)
e scritto nella sezione riguardante la funzione totiente.wikipedia ha scritto:Quindi il suo inverso è 0, e la successione
$ \[ \frac{\phi(n)}{n} \[ $
diventa arbitrariamente vicina a 0.
MIND TORNA CON NOI
nu, phi(n)/n non converge ha ragione federiko, perchè per esempio per un primo p grandissimo phi(p)/p è vicinissimo a 1. Se però studi separatamente i primi e i numeri altamente composti ottieni due sottosuccessioni convergenti a 1 o a 0, che sono quindi limite sup e limite inf. inquesto senso wikipedia probabilmente sbaglia perchè lascia intuire che lim phi(n)/n = 0 mentre non è così.
Aboliamo il latino nei licei scientifici!
- federiko97
- Messaggi: 44
- Iscritto il: 03 nov 2008, 20:36
- Località: Roma
"Diventa arbitrariamente vicina" e "tende a" sono concetti distinti, nonostante la mia prof di matematica li interscambi piuttosto spesso...Giulius ha scritto:nu, phi(n)/n non converge ha ragione federiko, perchè per esempio per un primo p grandissimo phi(p)/p è vicinissimo a 1. Se però studi separatamente i primi e i numeri altamente composti ottieni due sottosuccessioni convergenti a 1 o a 0, che sono quindi limite sup e limite inf. inquesto senso wikipedia probabilmente sbaglia perchè lascia intuire che lim phi(n)/n = 0 mentre non è così.
Comunque sì, quello che volevo dire è che tu puoi prendere una sottosuccessione di naturali per cui il limite di phi(n)/n fa 0, ma a quel punto tu dimostri che esiste una sottosuccessione di naturali tale che lì pi(n)/n va a 0. Quindi in sostanza hai dimostrato che se pi(n)/n ha un limite per n che tende a infinito, allora quel limite è zero. Purtroppo però non escludi, ad esempio, che pi(p)/p con p primo molto grande, non sia sempre maggiore di 1/2, ad esempio. Comunque, per una soluzione meno calata dall'alto della mia, potresti trovare un altro modo (un po' meno contorto di quello che proponevi ) per usare il fatto che il prodotto di (1-1/p) va a 0...
Buona fortuna..
Io credo che alcune entità superiori, pur non avendo odore, possano esistere. Esse influenzano le nostre vite in maniera che nessuno scienziato può comprendere.
Mmm la dimostrazione di Giulius doveva in teoria essere nata da una discussione mia e sua su msn, ma io avevo capito che si postava una cosa un po' diversa...
Allora, sia $ $P_a $ il prodotto dei primi $ $a $ primi. Sia $ $c_a(n) $ la funzione che conta i coprimi con $ $P_a $ da 1 ad n. Per n abbastanza grande, abbiamo ovviamente che $ $c_a(n)>\pi(n) $, in quanto $ $c_a $ prende tutti i primi tranne quelli che dividono $ $P_a $, più molti altri numeri. Quindi, sempre per n abbastanza grande, $ $\frac{c_a(n)}{n}>\frac{\pi(n)}{n} $. Ora il LHS per n che tende a infinito tende ovviamente a $ $\frac{\phi(P_a)}{P_a} $, che, detto $ $p_i $ l'i-esimo primo, è uguale a $ $\prod_{i=1}^{a}\frac{p_i-1}{p_i} $, che come ha dimostrato Giulius, per a tendente a infinito, tende a 0. Questo vuol dire che per tutti gli n maggiori di un valore sufficientemente grande $ $\frac{\pi(n)}{n} $ è più piccolo di un valore arbitrariamente piccolo ($ $\prod_{i=1}^{a}\frac{p_i-1}{p_i} $), il che è (circa) la definizione di limite.
Allora, sia $ $P_a $ il prodotto dei primi $ $a $ primi. Sia $ $c_a(n) $ la funzione che conta i coprimi con $ $P_a $ da 1 ad n. Per n abbastanza grande, abbiamo ovviamente che $ $c_a(n)>\pi(n) $, in quanto $ $c_a $ prende tutti i primi tranne quelli che dividono $ $P_a $, più molti altri numeri. Quindi, sempre per n abbastanza grande, $ $\frac{c_a(n)}{n}>\frac{\pi(n)}{n} $. Ora il LHS per n che tende a infinito tende ovviamente a $ $\frac{\phi(P_a)}{P_a} $, che, detto $ $p_i $ l'i-esimo primo, è uguale a $ $\prod_{i=1}^{a}\frac{p_i-1}{p_i} $, che come ha dimostrato Giulius, per a tendente a infinito, tende a 0. Questo vuol dire che per tutti gli n maggiori di un valore sufficientemente grande $ $\frac{\pi(n)}{n} $ è più piccolo di un valore arbitrariamente piccolo ($ $\prod_{i=1}^{a}\frac{p_i-1}{p_i} $), il che è (circa) la definizione di limite.
Mi scuso per non aver risposto prima..
Giulius ha scritto:Piuttosto che lasciar morire questo topic comincio i miei deliri, che giusto per piacere a jordan non sono nè una dimostrazione nè tantomeno una dimostrazione elementare.
Esatto.Giulius ha scritto:[...] allora dico che l'affermazione 1 è provata sse è provata la
affermazione3: la successione $ s_n:=\pi(n)/n $ converge al limite 0.E il problema è proprio dimostrare questo in maniera elementare.
In realtà questa disuguaglianza vale definitivamente, ma è molto più difficile di quello che vogliamo dimostrare (chi vuole provarci qui?)Giulius ha scritto:Assumiamo come verità di fede che $ \varphi(n)>\pi(n) $ per ogni n (o che quantomeno esiste una sottosuccessione infinita di N per cui vale la disuguaglianza)
Non sono io l'esperto che può assicurarti che i passaggi fatti siano leciti, è comunque da dire che devi prima mostrare che tale limite esiste.Giulius ha scritto:...allora dividendo entrambi i membri per n ottengo
$ \prod (1-1/p_i)>s_n $ e azzardo un passaggio ai limiti
$ \lim \inf \prod (1-1/p_i)>\lim \sup s_n $
ma $ \lim \inf \prod (1-1/p_i)=\lim \inf \frac{1}{\prod \frac{1}{p_i-1} \prod p_i}=\lim \inf \frac{1}{\prod {p_i}}\frac{1}{\zeta(-1)}=0 $ (per la formula prodotto di Eulero).
da cui $ \lim \sup s_n=0 $.
Che carofederiko97 ha scritto:Allora, alcune cose che mi va di dire al mondo:1) jordan si diverte a complicare gli enunciati, ma l'aggiunta di quel +y è del tutto irrilevante. In realtà "per ogni reale positivo x si ha che, per n sufficientemente grande, $ nx>\pi(x)" $è una formulazione equivalente.
Bellissimo, complimenti!federiko97 ha scritto: 3) Una dimostrazione sborona:[...]Per dimostrare che la tesi è vera per 2n+1, supponendo che sia vera per valori più piccoli faccio così: $ f(2n+1)\le f(n+1){2n+1\choose n} $ (i primi maggiori di n+1 dividono il binomiale) ma $ f(n)<4^n $ per ipotesi e $ {2n+1\choose n}\le 2^{2n} $ per ovvi motivi, quindi abbiamo concluso.
Ma così non valejulio14 ha scritto:... è uguale a $ $\prod_{i=1}^{a}\frac{p_i-1}{p_i} $, che come ha dimostrato Giulius, per a tendente a infinito, tende a 0...
The only goal of science is the honor of the human spirit.
L'upper bound del primoriale un passo cruciale anche nel dimostrare il postulato di Bertrand. clikfederiko97 ha scritto:3) Una dimostrazione sborona che sfrutta un fatto olimpicamente noto: pongo $ \displaystyle f(n) =\prod_{p\le n} p $ (dove la produttoria è calcolata sui primi, in sostanza è il prodotto dei numeri primi da 1 a n) e ora si ha $ f(n)<4^n $.
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]