Disuguaglianze sul prodotto dei numeri primi

[amatrix92]

Senza cannoneggiare, si mostri che

$ \displaystyle n \leq \prod_{p \leq n} p \leq 4^n $


A questo punto, sempre senza cannoneggiare e senza linkare teoremi assurdi, si trovino, scrivendo correttaemente la dimostrazione, bound migliori dipendenti da n. Divertitevi

[kalu]

Non mi viene nessuna buona idea per la disuguaglianza a destra, ma visto che nessuno risponde inizio con solo quella a sinistra..

$ 1+\displaystyle \prod_{p \leq n} p $ ha almeno un fattore primo $ q $ diverso da tutti quelli in produttoria (e quindi maggiore di $ n $), per il quale possiamo quindi scrivere $ \displaystyle q \leq 1+ \prod_{p \leq n} p $.
Supponiamo che esista un $ n $ tale che $ \displaystyle n > \prod_{p \leq n} p $. Allora avremmo che $ \displaystyle n \geq 1+ \prod_{p \leq n} p \geq q \rightarrow n \geq q $. Assurdo.

[amatrix92]

Bene kalu .

Giacchè mi piace vedere da dimostrare la doppia disugualianza e nessuno rilancia, rilancio subito io:

$ \displaystyle n^2 \leq \prod_{p\leq n} p \leq 4^n $ con la disuguaglianza di sinistra valida per $ n \geq 7 $.


Ritengo che quella di sinistra rimanga ancora un po' più facile di quella di destra. Tra qualche giorno o su richiesta metterò un (piccolo) hint sulla seconda.

[Ido Bovski]

La disuguaglianza di destra è davvero figa.

Lemma non troppo antip-adico. $\displaystyle \nu_p \left[ {2m+1 \choose m} \right]=1$ per ogni $m+1<p<2m+1$.
La dimostrazione è immediata.

Lemma del binomiale. $\displaystyle {2m+1 \choose m}<4^m$.
Dimostrazione:
$\displaystyle 2\cdot 4^m=(1+1)^{2m+1}=1+{2m+1 \choose 1}+...+{2m+1 \choose m}+{2m+1 \choose m+1}+...+1>{2m+1 \choose m}+{2m+1 \choose m+1}=2{2m+1 \choose m}$.

Ora dimostriamo per induzione su $n$ che $\displaystyle \prod_{p \le n}p<4^n$.
Consideriamo distintamente due casi: $n=2k$ e $n=2k+1$.
Passo base. Banalmente verificato.
Passo induttivo. Supponiamo che la tesi sia vera per gli interi $<n$.

• Se $n=2k$, allora
  $$\displaystyle \prod_{p \le 2k}p=\prod_{p \le 2k-1}p<4^{2k-1}<4^{2k}.$$
• Se $n=2k+1$, per "lemma non troppo anti-padico" e "lemma del binomiale", abbiamo che
  $$\displaystyle \prod_{p \le 2k+1}p=\left( \prod_{p \le k+1}p \right) \left( \prod_{k+1<p<2k+1}p \right)<4^{k+1}{2k+1 \choose k}<4^{k+1}\cdot 4^k=4^{2k+1}.$$

Rilancio: $\displaystyle \prod_{p \le n}p<(2.83)^n$.

[amatrix92]

Complimenti, non era facile! E la tua soluzione, benchè sostanzialmente uguale alla mia è molto più elegante (Del tipo non avevo usato valutazioni p-adiche ma considerazioni " a voce" e il lemma del binomiale l'avevo mostrato per induzione... )!
La mia intenzione era di passare da $ 4^n $ a $ 3^n $ ma noto con immenso piacere che ti sei già spinto oltre .

Per far sì che questo post non risulti inutile lascio un piccolo hint per la prima disuguaglianza:

Testo nascosto:

Nel Crivello di Eratostene non si controllano tutti i primi fino ad n ...