Stime deboli sulla pi(n)

[Stoppa2006]

Sia $ \pi (n) $ la funzine enumeratrice dei primi, che associa ad $ n $ il numero di primi minori o uguali ad $ n $. Dimostrare queste due stime (molto molto larghe...) per ogni $ n\ge 2 $:

1) $ \pi (n)\ge \log\log n $

2) $ \pi (n)\ge \displaystyle\frac{\log n}{\log 4} $

Chiaramente non vale usare nessun teorema di teoria analitica dei numeri, nè nessuna stima nota sulla pi... perchè usare i cannoni quando ci si può sporcare le mani La seconda non è troppo facile...

[Stoppa2006]

Per il primo usare la dimostrazione di Euclide (o quella con i numeri di Fermat) sull'infinità dei primi.

[afullo]

1) Partiamo dai primi 2 e 3. Sia una successione tale che (scusate ma non so utilizzare il LaTeX):

a_0 = 2
a_1 = 3
a_n = a_0 * a_1 * ... * a_(n-1) + 1

Otteniamo la successione:

2, 3, 7, 43, ...

In questo modo ogni a_n non è divisibile per nessuno dei precedenti termini e quindi, ogni volta che aggiungiamo un nuovo termine alla successione, possiamo affermare che esiste almeno un altro numero primo compreso tra 2 e a_n che non sia compreso tra i termini precedenti.

Pertanto:

pi(2) >= 1
pi(3) >= 2
pi(7) >= 3
pi(43) >= 4
...
pi(a_n) >= n+1

Si può inoltre notare che (volendo lo si prova per induzione):

a_n = a_(n-1)*(a_(n-1)-1)+1 < (a_(n-1))^2

Se log(log(x)) = y, allora log(log(x^2))=log(2*log(x))= log 2 + log(log(x)) = log 2 + y < 1 + y (poichè log 2 < 1).
La funzione log(log(x)) e la funzione pi(x) sono crescenti (la prima in senso stretto, la seconda in senso lato), ed inoltre log(log(2))<0, dunque:

log(log(2)) < 0 < 1 <= pi(2)
log(log(3)) < log(log(4)) < 1 < 2 <= pi(3) <= pi(4)
log(log(5)) < log(log(6)) < ... < log(log(16)) < 2 <= 2 <= pi(5) <= pi(6) <= ... <= pi(16)
log(log(17)) < ... < log(log(256)) < 3 <= 3 <= pi(7) <= pi(17) <= ... <= pi(256)
log(log(257) < ... < log(log(65536) < 4 <= 4 <= pi(43) <= pi(257) <= ... <= pi(65536)
e così via. In generale:

log(log(2^(2^(n-1))+1)) < ... < log(log(2^(2^n)) < n <= n <= pi(a_(n-1)) <= pi(2^(2^(n-1))+1) <= ... <= pi(2^(2^n))

In grassetto ho evidenziato dove utilizzo le disuguaglianze ricavate prima su pi(x) o su log(log(x)) considerando il fatto che elevando al quadrato l'argomento il risultato cresce di log 2, quindi meno di 1; in rosso scuro la disuguaglianza che stabilisce la relazione tra i log(log(x)) e i pi(x).
Il fatto che l'argomento del log (in blu) ogni volta venga elevato al quadrato mentre quello di pi (in rosso) aumenti ma diventi meno del quadrato (vedi disuguaglianza in verde) ci garantisce che quello del log, andando avanti, rimanga sempre maggiore anche di quello di pi della riga successiva, da cui quello che ci interessa sapere per rendere sempre valida la disuguaglianza col simbolo riportato in indaco, ovvero che l'argomento del log aumentato di 1 sia maggiore di quello di pi della riga successiva, o analogamente che l'argomento del log della riga precedente aumentato di 1 sia maggiore di quello di pi (cioè a_(n-1) < 2^(2^(n-1))+1), per cui la disuguaglianza è valida per ogni n, da cui la tesi.

[Stoppa2006]

Non riesco davvero a capire la tua dimostrazione

[afullo]

Non riesco davvero a capire la tua dimostrazione

Cosa non hai capito?