"Distribuzione" dei primi

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Rispondi
Avatar utente
mates
Messaggi: 65
Iscritto il: 01 gen 1970, 01:00

"Distribuzione" dei primi

Messaggio da mates » 05 ott 2005, 14:15

Spostato in MNE. Lo preciso di nuovo, nelle quattro categorie di "problem solving olimpico" ci vanno solo problemi "di tipo olimpiadi", tutto il resto è MNE

Sia $ n $ un intero positivo e sia $ p $ un numero primo tale che $ n < p \leq 2n $. Sia $ \alpha := |\{p \mbox{ è primo e } n < p \leq 2n \} | $.
(a) Dimostrare che $ n^{\alpha} \leq (2n)!/(n!)^2 $ (Facile)
(b) Dimostrare che $ (2n)!/(n!)^2 \leq 4^n $
(c) Trovare due costanti $ a, b $ tali che $ \alpha \leq an/ \log_b n $
(d) Dedurre che esiste una costante $ c $ tale che $ \pi(n) \leq cn / \ln n $ dove $ \pi(n) $ rappresenta il numero di primi minori o uguali ad $ n $ (questo è più difficile degli altri...)

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 07 ott 2005, 08:09

Per ogni $ n\in\mathbb{N}_0 $, siano $ \mathcal{P}_n = \{p \in \mathfrak{P}: n < p \leq 2n\} $ ed $ \alpha = |\mathcal{P}_n| $.

i) Se $ p\in\mathcal{P}_n $, allora $ \gcd(n!, p) = 1 $, e dunque $ \displaystyle p \,\| \binom{2n}{n} $. Pertanto $ \displaystyle n^\alpha < \prod_{p \in \mathcal{P}_n} p \leq \binom{2n}{n} $, q.e.d.

ii) In base al teorema del binomiale: $ \displaystyle 4^n = 2^{2n} = \sum_{k=0}^{2n} \binom{2n}{k} \geq \binom{2n}{n} $, q.e.d.

iii) Da i) e ii) seguita $ n^\alpha < 2^{2n} $, e quindi $ \displaystyle\alpha < \frac{2n}{\log_2 n} $, purché sia $ n > 1 $. Pertanto può porsi $ a = b = 2 $.

iv) Per caso c'è da usare la lambda maior di Von Mangoldt? 8)

Avatar utente
mates
Messaggi: 65
Iscritto il: 01 gen 1970, 01:00

Messaggio da mates » 08 ott 2005, 22:35

Beh, non necessariamente. E' fattibile con metodi assolutamente elementari che non richiedono conoscenze strane.. :lol: :lol:

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 08 ott 2005, 23:43

iv) Uh... Dalla ii) $ \ln((2n)!) - 2\ln(n!) \leq 2n\ln 2 $. Senonché, comunque scelto $ m\in\mathbb{N} $: $ \displaystyle\log(m!) = \sum_{p \leq m} \left(\log p \cdot \sum_{t=1}^{\infty} \left\lfloor\frac{m}{p^t}\right\rfloor\right) $, d'accordo con la tanto decantata identità di Legendre-De Polignac.

Perciò $ 2n \ln 2 \displaystyle\geq \sum_{p \leq 2n} \left(\log p \cdot \sum_{t=1}^{+\infty} \left(\left\lfloor\frac{2n}{p^t}\right\rfloor - \left\lfloor\frac{n}{p^t}\right\rfloor\right) \right) $ $ \geq \displaystyle\sum_{n < p \leq 2n} \log p $, siccome $ 0 \leq \lfloor 2x \rfloor - 2\lfloor x \rfloor \leq 1 $, per ogni $ x\in\mathbb{R} $; e in particolare $ \displaystyle\left\lfloor \frac{2n}{p} \right\rfloor - 2\left\lfloor\frac{n}{p}\right\rfloor = 1 $, se $ n < p \leq 2n $. In altri termini $ 2n \ln 2 \geq \theta(2n) - \theta(n) $, per ogni $ n\in\mathbb{N}_0 $, ove $ \theta(\cdot) $ è la funzione omonima di Chebyshev (la cui definizione coinvolge appunto la lambda maior di Mangoldt).

Da qui, ponendo $ k = \lfloor \log_2 n\rfloor $, si trova $ \theta(n) \leq \theta(2^{k+1}) = \displaystyle\sum_{i=0}^k (\theta(2^{i+1}) - \theta(2^i)) \leq $ $ \displaystyle\sum_{i=0}^k 2^{i+1} \ln 2 = 2^{k+2} \ln 2 \leq 4n \ln 2 $.

Se adesso $ 0 < \alpha < 1 $, risulta $ (\pi(n) - \pi(n^\alpha)) \log n^\alpha \leq \displaystyle\sum_{n^\alpha < p \leq n} \log p \leq \theta(n) \leq 4n\ln 2 $, e dunque $ \pi(n) \leq \displaystyle\frac{4n \ln 2}{\alpha \ln n} + \pi(n^\alpha) \leq \frac{4n \ln 2}{\alpha \ln n} + n^\alpha $. A questo punto ci vengono in soccorso Jack e le sue derivate, per concludere finalmente che $ \pi(n) \leq \displaystyle\frac{6 n}{\ln n} $. Davvero divertente...
Ultima modifica di HiTLeuLeR il 09 ott 2005, 17:57, modificato 1 volta in totale.

Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo » 09 ott 2005, 14:36

Credo sia un errore di battiura, almeno spero sia così, dacchè non ho voglia di leggere il resto del messaggio. Comunque questa conclusione lascia... come dire... un po' perplessi, e forse Jack si dissocierebbe da questa asserzione:
HiTLeuLeR ha scritto:A questo punto ci vengono in soccorso Jack e le sue derivate, per concludere finalmente che $ \pi(n) \leq \displaystyle\frac{6\ln n}{n} $. Davvero divertente...

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 09 ott 2005, 17:56

Ovviamente è un orrore di battitura... :wink: Correggo subito! :mrgreen:

Avatar utente
mates
Messaggi: 65
Iscritto il: 01 gen 1970, 01:00

Messaggio da mates » 21 ott 2005, 17:53

Ok HiTLeuLeR, bella soluzione :D . Comunque si può anche fare in modo molto più elementare e senza derivate e funzioni di Chebyshev.....
Un po' di inuzione è più che sufficiente :!: :!:

Qualcuno si cimenta ??

Altrimenti posto la mia sol. :lol: :D

Rispondi