Bound inferiore per la funzione enumerativa dei primi
Dimostra che
\[ \pi(x) \geq \log \log(x) \]
Se riesco a dimostrare che \( x \geq \log(x)^{\log(x)} \) sugli interi allora riesco a dimostrare il claim. Siccome poi farei così
\[ \prod_{p \leq x} p \geq x \]
Siccome se \(x \geq 2\) è pari allora abbiamo che tra \( x \) e \( x/2 \) esiste almeno un primo \(p\) inoltre \(x \geq 2\) è primo dunque
\[ \prod_{p \leq x} p \geq 2p \geq x \geq \log(x)^{\log(x)} \]
Se \( x \geq 2 \) è dispari allora abbiamo che tra \( x+1 \) e \( (x+1)/2 \) esiste almeno un primo \(x+1 > x \geq p \) inoltre \(2\) è primo e dunque
\[ \prod_{p \leq x} p \geq 2p \geq x \geq \log(x)^{\log(x)} \]
dunque applicando il logaritmo che è monotono otteniamo
\[ \sum_{p \leq x} \log p \geq \log(x) \log\left( \log(x) \right) \]
Ora siccome \(x \geq 2 \) otteniamo
\[ \frac{1}{\log(x)}\sum_{p \leq x} \log p \geq \log\left( \log(x) \right) \]
E abbiamo che
\[ \pi(x) = \frac{1}{\log(x)} \sum_{p \leq x} \log x \geq \frac{1}{\log(x)}\sum_{p \leq x} \log p \]
Ma non riesco a dimostrare che \( x \geq \left( \log x \right)^{\log x} \)
\[ \pi(x) \geq \log \log(x) \]
Se riesco a dimostrare che \( x \geq \log(x)^{\log(x)} \) sugli interi allora riesco a dimostrare il claim. Siccome poi farei così
\[ \prod_{p \leq x} p \geq x \]
Siccome se \(x \geq 2\) è pari allora abbiamo che tra \( x \) e \( x/2 \) esiste almeno un primo \(p\) inoltre \(x \geq 2\) è primo dunque
\[ \prod_{p \leq x} p \geq 2p \geq x \geq \log(x)^{\log(x)} \]
Se \( x \geq 2 \) è dispari allora abbiamo che tra \( x+1 \) e \( (x+1)/2 \) esiste almeno un primo \(x+1 > x \geq p \) inoltre \(2\) è primo e dunque
\[ \prod_{p \leq x} p \geq 2p \geq x \geq \log(x)^{\log(x)} \]
dunque applicando il logaritmo che è monotono otteniamo
\[ \sum_{p \leq x} \log p \geq \log(x) \log\left( \log(x) \right) \]
Ora siccome \(x \geq 2 \) otteniamo
\[ \frac{1}{\log(x)}\sum_{p \leq x} \log p \geq \log\left( \log(x) \right) \]
E abbiamo che
\[ \pi(x) = \frac{1}{\log(x)} \sum_{p \leq x} \log x \geq \frac{1}{\log(x)}\sum_{p \leq x} \log p \]
Ma non riesco a dimostrare che \( x \geq \left( \log x \right)^{\log x} \)
Risposte
Non riesco perché è falso... \( 16 < \log(16)^{\log(16)} \)
Abbiamo
\[ \sum_{n=1}^{x} \frac{1}{n} \leq \prod_{p \leq x} \left( 1 + \frac{1}{p} + \frac{1}{p^2} + \ldots \right) \]
\[ \leq \prod_{p \leq x} \left( \frac{1}{1- 1/p} \right) = \prod_{p \leq x} \left( \frac{p}{p-1} \right) \]
ora abbiamo che
\( \frac{p}{p-1} \leq 2 \) per ogni \( p \) primo. Abbiamo che
\[ \sum_{n=1}^{x} \frac{1}{n} \geq \int_1^x \frac{\text{d}t}{t} = \log(x) \]
Dunque
\[ \log x \leq \sum_{n=1}^{x} \frac{1}{n} \leq 2^{\pi(x)} \]
applicando il logaritmo otteniamo
\[ \log \log x \leq \pi(x) \log 2 \leq \pi(x) \]
\[ \sum_{n=1}^{x} \frac{1}{n} \leq \prod_{p \leq x} \left( 1 + \frac{1}{p} + \frac{1}{p^2} + \ldots \right) \]
\[ \leq \prod_{p \leq x} \left( \frac{1}{1- 1/p} \right) = \prod_{p \leq x} \left( \frac{p}{p-1} \right) \]
ora abbiamo che
\( \frac{p}{p-1} \leq 2 \) per ogni \( p \) primo. Abbiamo che
\[ \sum_{n=1}^{x} \frac{1}{n} \geq \int_1^x \frac{\text{d}t}{t} = \log(x) \]
Dunque
\[ \log x \leq \sum_{n=1}^{x} \frac{1}{n} \leq 2^{\pi(x)} \]
applicando il logaritmo otteniamo
\[ \log \log x \leq \pi(x) \log 2 \leq \pi(x) \]
Forse l’idea dell’esercizio e’ di usare la dimostrazione di Euclide che i primi sono
infiniti. Infatti, questa dimostrazione implica che l’enisimo primo $p_n$ e’ $\le 2^{2^{n-1}}$.
Per induzione: per $p_1=2$ e’ vero. Abbiamo che
$p_{n+1}\le 1+p_1\cdot\ldots\cdot p_n \le 1+2^1 2^2\cdots 2^{2^{n-1}}=1+2^{1+2+\ldots2^{n-1}}\le 1+2^{2^{n}-1}\le 2^{2^n}$
come richiesto. Ne segue che $\pi(2^{2^n})\ge n+1$ per ogni intero $n\ge 0$.
Per $x\ge 2$ reale abbiamo che $2^{2^n}\le x\le 2^{2^{n+1}}$ per qualche $n\ge 0$
Questo implica facilmente che $\pi(x)\ge \log\log x$ per ogni $x\ge 2$ reale.
infiniti. Infatti, questa dimostrazione implica che l’enisimo primo $p_n$ e’ $\le 2^{2^{n-1}}$.
Per induzione: per $p_1=2$ e’ vero. Abbiamo che
$p_{n+1}\le 1+p_1\cdot\ldots\cdot p_n \le 1+2^1 2^2\cdots 2^{2^{n-1}}=1+2^{1+2+\ldots2^{n-1}}\le 1+2^{2^{n}-1}\le 2^{2^n}$
come richiesto. Ne segue che $\pi(2^{2^n})\ge n+1$ per ogni intero $n\ge 0$.
Per $x\ge 2$ reale abbiamo che $2^{2^n}\le x\le 2^{2^{n+1}}$ per qualche $n\ge 0$
Questo implica facilmente che $\pi(x)\ge \log\log x$ per ogni $x\ge 2$ reale.
Si così è anche più immediato,
\( p_{n+1} \leq 1 + \prod_{j=1}^{n} p_j \) deriva dal fatto che
\[ 1 + \prod_{j=1}^{n} p_j \equiv 1 \mod p_j \]
per ogni \( 1 \leq j \leq n \) e dunque o è primo oppure è divisibile per un primo diverso da tutti i \( p_j \) con \( 1 \leq j \leq n \), vero?
\( p_{n+1} \leq 1 + \prod_{j=1}^{n} p_j \) deriva dal fatto che
\[ 1 + \prod_{j=1}^{n} p_j \equiv 1 \mod p_j \]
per ogni \( 1 \leq j \leq n \) e dunque o è primo oppure è divisibile per un primo diverso da tutti i \( p_j \) con \( 1 \leq j \leq n \), vero?
Si, si, come nella dimostrazione di Euclide
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo