OliForum Matematico

Dimostrare che, scelti $n$ interi a caso nell'insieme $\{1,2,\ldots,2n\}$, uno di essi dovrà essere libero da quadrati.

Premessa: $\displaystyle \sum\limits_{p \text{ primo}} \frac{1}{p^2}< \frac{1}{2}$
Dimostrazione (bruttina): Definisco una funzione $Q: \mathbb{N}^* \to \mathbb{N}$ nel seguente modo: per ogni $n$ intero positivo,
$Q(n)$ è il numero elementi di $\{1,\ldots, n\}$ che sono liberi da quadrati.

Ad esempio $Q(9)=6$ perchè nell'insieme $\{1,2,3,4,5,6,7,8,9\}$
ci sono sei elementi liberi da quadrati (e cioè $1,2,3,5,6,7$)

Devo dimostrare che per ogni $n$ intero positivo si ha $Q(2n)>n$.
Fisso $n$. Consideriamo tutti e soli i primi minori di $\sqrt{2n}$:
$p_1<p_2 < \ldots< p_h <\sqrt{2n}$, per un $h$ opportuno.

Per ogni $i=1,\ldots,h$ sia $A_i:= \biggl\{p_i^2, 2 p_i^2, 3 p_i^2, \ldots, \left\lfloor \frac{2n}{p_i^2} \right\rfloor p_i^2 \biggr\}$
Ovviamente la cardinalità di $A_i$ è $\left\lfloor \frac{2n}{p_i^2} \right\rfloor$
Ora, l'unione di tutti gli $A_i$ è l'insieme di tutti e soli gli interi positivi minori o uguali ad $2n$ che non sono liberi da quadrati.
Si ha \[ |\bigcup_{i=1}^{h} A_i| \leq \sum_{i=1}^h |A_i|= \sum_{i=1}^h \left\lfloor \frac{2n}{p_i^2} \right\rfloor < \sum_{i=1}^h \frac{2n}{p_i^2}= 2n \cdot \sum_{i=1}^h \frac{1}{p_i^2} < 2n \sum_{i=1}^{+\infty} \frac{1}{p_i^2}< 2n \cdot \frac{1}{2}=n\]
Dunque $\displaystyle Q(2n)= 2n- |\bigcup_{i=1 }^{h} A_i|>2n-n=n$, come volevasi.

@ Gi8 Forse mi sbaglierò ma a me sembra corretto.
La mia soluzione (forse) era questa:
consideriamo i numeri che NON sono squarefree. Allora sono della forma ${{p}^{2}}Q$ con p primo e Q naturale.
Se ${{p}^{2}}Q\le 2n$ allora deve essere $Q\le \frac{2n}{{{p}^{2}}}$, ossia, $\sum\limits_{p<2n}{\frac{2n}{{{p}^{2}}}}<2n\sum\limits_{k=2}^{+\infty }{\frac{1}{{{2}^{k}}}}=2n\frac{1}{2}=n$.
Quindi, per Pp.cassetti o Pigeonhole, presi n numeri almeno uno è squarefree.

@gpzes: Perchè vale questo? \[\sum_p \frac{1}{p^2} < \sum_{k=2}^{+\infty} \frac{1}{2^k}\]

Gi8

Gi8 ha scritto:@gpzes: Perchè vale questo? \[\sum_p \frac{1}{p^2} < \sum_{k=2}^{+\infty} \frac{1}{2^k}\]

Perchè i $p<2n$ sono finiti.
Non sto considerando una sommatoria infinita sui $p$: posso minorare i primi con potenze di due.

Ho capito che la sommatoria sui primi è finita, ma non riesco a trovare una giustificazione per quella disuguaglianza.
Perchè puoi minorare i primi con potenze di due?
(probabilmente è una stupidata, ma non ci arrivo)

Dato un primo qualsiasi esistono naturali tale che ${{2}^{\alpha }}<p<{{2}^{\beta}}$ .
Se elevo al quadrato e passo ai reciproci ottengo $\sum\limits_{p}{\frac{1}{{{p}^{2}}}}\le\frac{1}{2}$.

gpzes ha scritto:Dato un primo qualsiasi esistono naturali tale che ${{2}^{\alpha }}<p<{{2}^{\beta}}$ .
Se elevo al quadrato e passo ai reciproci ottengo $\sum\limits_{p}{\frac{1}{{{p}^{2}}}}\le\frac{1}{2}$.

What? :/

Il claim (come mostrato sopra manualmente) è giusto, difatti $$\sum_{p \in \mathbb{P}}{1\over p^2}=\sum_{k\ge 1}{\mu(k)\over k}\log(\zeta(2k))=0.4522474200\dots,$$
ma la dimostrazione mi pare ha qualche problema..

Scusatemi per tali grossolanità

$\sum\limits_{p}{\frac{1}{{{p}^{2}}}}=L<\frac{1}{2}$

è tutta da dimostrare!!

Un'altra soluzione allo stesso modo un po' manuale..

• $ \displaystyle \sum_{i=1}^{\pi(n)}{\left\lfloor \frac{n}{p_i^2} \right\rfloor} \le n\sum_{i=1}^{\pi(n)}{\frac{1}{p_i^{2}}} $ $ \displaystyle \le n \left(\frac{1}{2^{2}}+\frac{1}{3^{2}}+\frac{1}{5^{2}}+\frac{1}{7^{2}}+\frac{1}{11^{2}}+\frac{1}{13^{2}}+\sum_{i=17}^{n}{1/i^{2}}\right) $

• • $ \displaystyle \le n\left[\frac{1}{2^{2}}+\frac{1}{3^{2}}+\frac{1}{5^{2}}+\frac{1}{7^{2}}+\frac{1}{11^{2}}+\frac{1}{13^{2}}+\sum_{i=17}^n\left(\frac{1}{i-1}-\frac{1}{i}\right)\right] $

A questo punto la somma è minore di
$$\displaystyle n\left(\frac{1}{2^{2}}+\frac{1}{3^{2}}+\frac{1}{5^{2}}+\frac{1}{7^{2}}+\frac{1}{11^{2}}+\frac{1}{13^{2}}+\frac{1}{16}\right) < \frac{n}{2}$$

Siano:
1. \(A_n = \{1,\ldots,n\}\);
2. \(R_n= \{ a \in A_n : \ \ \forall p \in \mathbb{P} \ \ p^2 \nmid n\} = \{\mbox{squarefree } \le n \} \);
3. \(L_p= \{ a \le n \ : \ \ \exists p\in \mathbb{P} \ \ p^2 \mid a\}\);
4. \(\displaystyle P_n = \prod_{ p \le n} p\).
La tesi è che \(|R_n| > \frac{n}{2}\). Abbiamo:
\[ R_n = A_n \setminus \bigcup_{p \le n} L_p\]
perchè se un numero non appartiene a nessun \(L_p\) allora è squarefree. Visto che
\[ |L_{p_1} \cap \ldots L_{p_k} | = \frac{n}{(p_1\cdot \ldots \cdot \ldots p_k)^2 } \]
Abbiamo, per inclusione-esclusione con il metodo \(\mu(n)\) (che se volete spiego per chi non lo conosce, è in tutto e per tutto inclusione-esclusione ma con una notazione comoda):
\[ |R_n| = \sum_{d \mid P(n) } \frac{\mu(d) n}{d^2} = n \sum_{p \le n } \left (1-\frac{1}{p^2} \right ) \ge n \left ( \sum_{p \in \mathbb{P} } \frac{1}{1-p^{-2} } \right )^{-1} = \frac{6}{\pi^2} n > \frac{n}{2} \]

EDIT: che scemo, ho dimenticato la parte intera :/

Altra dimostrazione di $\displaystyle \sum_{p \text{ primo} } \frac{1}{p^2} < \frac{1}{2}$

$\displaystyle \sum_p \frac{1}{p^2} = \frac{1}{2^2}+ \frac{1}{3^2}+ \frac{1}{5^2}+ \sum_{ p\geq 7 } \frac{1}{p^2}< \frac{1}{2^2}+ \frac{1}{3^2}+ \frac{1}{5^2}+ \sum_{n=3}^{+\infty} \frac{1}{(2n)^2}=$
$\displaystyle = \left[ \frac{1}{3^2}+ \frac{1}{5^2}- \frac{1}{4^2}\right]+ \left[ \frac{1}{2^2}+ \frac{1}{4^2} +\sum_{n=3}^{+\infty} \frac{1}{(2n)^2}\right]= \frac{1}{3^2}+ \frac{1}{5^2}- \frac{1}{4^2} +\frac{1}{4}\sum_{n=1}^{+\infty}\frac{1}{n^2}= $
$\displaystyle = \frac{1}{3^2}+ \frac{1}{5^2}- \frac{1}{4^2}+\frac{1}{4}\cdot \frac{\pi^2}{6}= 0.49984462<0.5 $

Spiegheresti questo metodo di inclusione-esclusione?

Sii! Volentieri
Una funzione strana: \(\mu(n)\)
Sia \(n=p_1^{\alpha_1} \cdot \ldots \cdot p_k ^{\alpha_k}\) (*). Se c'è un \(\alpha_i \ge 2\), allora \(\mu(n)=0\); altrimenti \(\mu(n) = (-1)^{k}\). Inoltre \(\mu(1) = 1\).
E' facile vedere che \(\mu(n)\) è moltiplicativa, ossia se \(a,b\) sono coprimi allora \(\mu(a) \cdot \mu(b) = \mu(ab)\).
Vediamo un lemma per entrare in atmosfera \(\mu\). Dimostriamo che, per \(n>1\), vale (sempre usando la notazione (*) ) :
\[ \sum_{d \mid n} \mu(d) = 0\]
I divisori di \(n\) sono di tre tipi:
1. Quelli non squarefree, che non contribuiscono alla somma;
2. Quelli squarefree con un numero dispari di primi: sono \( \displaystyle S_{-} = \sum_{2m+1 \le k} \binom{k}{2m+1} \) (che sarebbe: fisso un numero dispari \(2m+1\) che rappresenta il numero di primi del divisore, e il binomiale sono i modi di scegliere \(2m+1\) primi tra i \(k\) che dividono \(n\) ). Contribuiscono con \(-S_{-}\) (\(\mu\) vale -1\).
3. Quelli squarefree con un numero pari di primi: sono \(\displaystyle S_{+} = \sum_{2m \le k} \binom{k}{2m}\) e contribuiscono con \(S_{+}\).
Nel complesso la somma è
\[ S_{+}-S_{-} = \sum_{2m \le k} \binom{k}{2m} - \sum_{2m+1 \le k} \binom{k}{2m+1} = \sum_{m \le k} (-1)^{m} \binom{k}{m} = (1-1)^k = 0\]
Wow!
Che c'entra con inclusione esclusione.
E' la prima volta che mi capita di formalizzare questa cosa in generale, perciò boh, vediamo che viene, e se non sono chiaro dimmi pure In ogni caso la parte generale si spiega meglio guardando l'esempio dopo!
Siano:
1. \(N\) il nostro insieme principale (che di solito è \(\{1, \ldots, n\}\) );
2. \(n=|N|\);
3. \(m\) un intero, e \(k\) il numero di primi che lo dividono;
4. Per ogni primo \(p\) tale che \(p \mid m\), degli insiemi (quasi) a caso \(A_p \subseteq N\);
5. Una funzione \(f:\mathbb{N}^{2} \rightarrow \mathbb{N} \) tale che:
a) \(n=f(1,n)\)
b) \(|A_p| = f(p,n)\)
c) \( |A_{p_1} \cap \ldots \cap A_{p_s} | = f(p_1 \cdot \ldots \cdot p_s ,n)\)
dove \(p_1, \ldots, p_s\) dividono \(m\). In pratica possiamo scrivere tutti i termini che compaiono in un inclusione-esclusione su \(\bigcup_{p \mid m} A_p\) in termini di \(f\) (vero?).
Siamo interessati, non si sa perchè, a calcolare la cardinalità di
\[ S = N \setminus \bigcup_{p \mid m} A_p \]
Intanto abbiamo, visto che \(A_p \subseteq N\) per ogni \(p\):
\[ |S| = n- | \bigcup_{p \mid m} A_p | \]
Per il principio di inclusione esclusione abbiamo, usando la definizione di \(f\):
\[ |S| = n- \sum_{p \mid m} f(p,n) + \sum_{p_1 \neq p_2 \mid m} f(p_1p_2, n) + \ldots +(-1)^k f(p_1 \cdot \ldots \cdot p_k, n)\]
Ma, ehi! Guardiamolo bene. Ogni termine è della forma \(f(d,n)\), dove \(d\) è un divisore di \(m\), e ha davanti:
1. Un \(-1\) se \(\mu(d)=-1\);
2. Un \(+1\) se \(\mu(d) = +1\);
3. Uno \(0\) se \(\mu(d)=0\) (perchè effettivamente compaiono solo squarefree);
Perciò possiamo riscriverla come
\[ |S| = \sum_{d \mid n} \mu(d) f(d, n) \]
che è decisamente più comodo della versione iniziale
Un esempio pratico.
Sia \(S\) l'insieme dei coprimi con un certo \(m\) nell'insieme \(N= \{1,\ldots,n\}\). Vogliamo calcolare |S|, e lo vogliamo calcolare come \(| N \setminus H|\), dove \(H\) è invece l'insieme dei non coprimi con \(m\). Per riprendere la notazione di sopra, definiamo, per ogni \(p \mid m\):
\[A_p = \{a \in N: \ \ \ p \mid a\} \]
Visto che se un numero non è coprimo con \(m\) ha almeno un primo in comune con \(m\), vale
\[ H = \bigcup_{ p \mid m} A_p\]
perciò (assomiglia a quello di sopra?):
\[ |S| = | N \setminus \bigcup_{p \mid m} A_p |\]
Visto che (i requisiti della \(f\) sopra con \(f(a,b) = \left \lfloor \frac{b}{a} \right \rfloor\) ):
1. \(\displaystyle |A_p| = \left \lfloor \frac{n}{p} \right \rfloor \);
2. \(\displaystyle |A_{p_1} \cap \ldots \cap A_{p_s} | = \left \lfloor \frac{n}{p_1 \cdot \ldots \cdot p_s} \right \rfloor\);
3. \( \displaystyle |N| = \left \lfloor \frac{n}{1} \right \rfloor\)
Abbiamo:
\[ |S| = \sum_{d \mid m} \mu(d) \left \lfloor \frac{n}{d} \right \rfloor \]
che con un po' di conti, cosa che adesso non ci importa di fare, si può più o meno stimare (sbarazzandosi delle parte intere).
Spero di essere stato chiaro! Per inciso, nel problema la cosa è uguale ma con
\(\displaystyle m= \prod_{p \le n} p\)
\(\displaystyle A_p = \{ a \in N: \ \ p^2 \mid a \mbox{ per qualche } p\}\)
\(\displaystyle f(p,n) = \left \lfloor \frac{n}{p^2} \right \rfloor\).

Forse nuova soluzione???

Dato il naturale $N$ (il$2n$del problema) si ha che $N$= n° SquareFree + n° NonSquareFree , abbreviato SF e NSF.

Claim: Ogni naturale $m>1$ è prodotto di un SF e un Quadrato Perfetto. (esercizio)

Cerchiamo di studiare, allora, i naturali $m>1$ esprimibili come $m={{M}^{2}}Q\le N$, dove Q è un SF.
L’idea è cercare delle limitazioni sui Q, che soddisfino la disuguaglianza, per poter avere informazioni sulle combinazioni di primi minori di N che possono essere usate; in sintesi, per cercare di contare i SF.

Iniziamo col vedere quanti possono essere i naturali i cui quadrati sono minori di N.
Vediamo per quali $\alpha $vale la disuguaglianza ${{\left( N-\alpha \right)}^{2}}\le N$. Dopo alcuni conti, si otterrebbe che, poiché $\alpha $ deve essere minore o al massimo N-1 , che \[N-\left[ \sqrt{N} \right]\le \alpha \le N-1\].
Allora il massimo valore di Q per cui $Q\le \frac{N}{{{M}^{2}}}$, si otterrebbe per il minimo assunto da $\alpha $; ossia, si avrebbe $Q\le \frac{N}{{{\left( N-\left( N-\left[ \sqrt{N} \right] \right) \right)}^{2}}}=\frac{N}{{{\left( \left[ \sqrt{N} \right] \right)}^{2}}}<1$. ( I casi N = 1,2,3,4 sono abbastanza agevoli.)

Ciò vuol dire che NSF= numero di Quadrati Perfetti minori o uguali a N!!!

Quindi, $N$= n° SquareFree + n° Quadrati Perfetti.
Ma i quadrati perfetti minori o uguali a N , li abbiamo calcolati prima.
Escludendo il numero 1, che è SF, otteniamo che SF = \[N-\left( N-1-\left( N-\left[ \sqrt{N} \right] \right)+1-1 \right)=N+1-\left[ \sqrt{N} \right]\].

Osservando che \[\sqrt{N}\le \frac{N+1}{2}\] e utilizzando sempre proprietà della parte intera di un numero, otteniamo che
\[N+1-\left[ \sqrt{N} \right]\ge N+1-\frac{N+1}{2}=\frac{N+1}{2}\ge \left[ \frac{N}{2} \right]+\frac{1}{2}>\left[ \frac{N}{2} \right]\]!!! Tesi del problema.

Spero di non avere fatto castronerie più del solito