Ricordando vecchi bound su \pi(n)

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

Ricordando vecchi bound su \pi(n)

Messaggio da jordan » 01 lug 2009, 21:08

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

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 05 lug 2009, 23:01

uppino! sembra così caruccio...
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Giulius
Messaggi: 58
Iscritto il: 02 apr 2009, 21:49
Località: Milano

Messaggio da Giulius » 06 lug 2009, 11:41

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 :D
Aboliamo il latino nei licei scientifici!

Avatar utente
federiko97
Messaggi: 44
Iscritto il: 03 nov 2008, 20:36
Località: Roma

Messaggio da federiko97 » 06 lug 2009, 13:59

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.
Io credo che alcune entità superiori, pur non avendo odore, possano esistere. Esse influenzano le nostre vite in maniera che nessuno scienziato può comprendere.

Giulius
Messaggi: 58
Iscritto il: 02 apr 2009, 21:49
Località: Milano

Messaggio da Giulius » 06 lug 2009, 14:12

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.
Aboliamo il latino nei licei scientifici!

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 06 lug 2009, 14:14

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)
wikipedia ha scritto:Quindi il suo inverso è 0, e la successione
$ \[ \frac{\phi(n)}{n} \[ $
diventa arbitrariamente vicina a 0.
e scritto nella sezione riguardante la funzione totiente.
MIND TORNA CON NOI

Giulius
Messaggi: 58
Iscritto il: 02 apr 2009, 21:49
Località: Milano

Messaggio da Giulius » 06 lug 2009, 14:18

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!

Avatar utente
federiko97
Messaggi: 44
Iscritto il: 03 nov 2008, 20:36
Località: Roma

Messaggio da federiko97 » 06 lug 2009, 16:55

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ì.
"Diventa arbitrariamente vicina" e "tende a" sono concetti distinti, nonostante la mia prof di matematica li interscambi piuttosto spesso...

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 :P ) 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.

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 06 lug 2009, 18:54

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.
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

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

Messaggio da jordan » 12 lug 2009, 11:49

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.
:lol:
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.
Esatto.
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)
In realtà questa disuguaglianza vale definitivamente, ma è molto più difficile di quello che vogliamo dimostrare (chi vuole provarci qui?)
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 $.
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.
federiko97 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.
Che caro :lol:
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.
Bellissimo, complimenti!
julio14 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...
Ma così non vale :lol:
The only goal of science is the honor of the human spirit.

Avatar utente
FeddyStra
Messaggi: 403
Iscritto il: 19 set 2006, 15:34
Località: 45° 7' 19.2'' N 7° 23' 20.1'' E

Messaggio da FeddyStra » 12 lug 2009, 18:35

federiko97 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 $.
L'upper bound del primoriale un passo cruciale anche nel dimostrare il postulato di Bertrand. clik
[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]

Rispondi