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...)
"Distribuzione" dei primi
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?
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?
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...
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.
-
psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
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...
Correggo subito! 
. Comunque si può anche fare in modo molto più elementare e senza derivate e funzioni di Chebyshev.....