La probabilità della coprimalità
Problem. Choose two natural numbers $x,y \in {1,2, ..., n}$ randomly (with uniform probability) and independently. Let $P_{n}$ be the probability that $x$ and $y$ are coprime. Prove that $\lim_{n \to +\infty} P_{n} = 6/pi^2$.
Non ho la soluzione. Ci sto pensando. Qualunque suggerimento e/o aiuto è ben accetto.
Risposte
"Paolo90":
Non ho la soluzione. Ci sto pensando. Qualunque suggerimento e/o aiuto è ben accetto.
Qui trovi tutto
Più semplice e più immediato, Tom M. Apostol, Introduction to Analytic Number Theory, pagina 62 (sezione 3.8, distribuzione dei punti a coordinate intere visibili dall'origine).
Se non hai modo di accedervi, dimmelo che la prossima volta che ci vediamo ti porto tutto!
Comunque, l'idea è questa:
Definizione. Due punti a coordinate intere si dicono visibili a vicenda se il segmento che li congiunge non contiene altri punti a coordinate intere.
Lemma. Due punti a coordinate intere [tex](a,b)[/tex] e [tex](c,d)[/tex] sono visibili a vicenda se e solo se [tex]\text{gcd}(c - a,d-b) = 1[/tex].
A questo punto:
Teorema. L'insieme dei punti a coordinate intere visibili dall'origine ha densità [tex]\frac{6}{\pi^2}[/tex].
La dimostrazione è auto-contenuta e si basa su quest'altro teorema:
Teorema. Per [tex]x > 1[/tex] vale la relazione asintotica [tex]\displaystyle \sum_{n \le x} \varphi(n) = \frac{3}{\pi^2} x^2 + O(x \log x)[/tex].
La dimostrazione di questo fatto è davvero elementare e basta smanettare un po' con la formula di inversione di Moebius e qualche altra identità tra funzioni aritmetiche. Secondo me, puoi anche provare a farlo per esercizio!
Se non hai modo di accedervi, dimmelo che la prossima volta che ci vediamo ti porto tutto!
Comunque, l'idea è questa:
Definizione. Due punti a coordinate intere si dicono visibili a vicenda se il segmento che li congiunge non contiene altri punti a coordinate intere.
Lemma. Due punti a coordinate intere [tex](a,b)[/tex] e [tex](c,d)[/tex] sono visibili a vicenda se e solo se [tex]\text{gcd}(c - a,d-b) = 1[/tex].
A questo punto:
Teorema. L'insieme dei punti a coordinate intere visibili dall'origine ha densità [tex]\frac{6}{\pi^2}[/tex].
La dimostrazione è auto-contenuta e si basa su quest'altro teorema:
Teorema. Per [tex]x > 1[/tex] vale la relazione asintotica [tex]\displaystyle \sum_{n \le x} \varphi(n) = \frac{3}{\pi^2} x^2 + O(x \log x)[/tex].
La dimostrazione di questo fatto è davvero elementare e basta smanettare un po' con la formula di inversione di Moebius e qualche altra identità tra funzioni aritmetiche. Secondo me, puoi anche provare a farlo per esercizio!
Io ricordo l'approccio intuitivo (non formale): la probabilita' che un numero sia divisibile per un primo [tex]p[/tex] e' [tex]1/p[/tex], quindi la probabilita' che due numeri distinti non siano divisibili entrambi per [tex]p[/tex] e' [tex]1-1/p^2[/tex]. Ne segue che la probabilita' che siano coprimi e' la produttoria [tex]\prod_p (1-1/p^2) = \prod_p (1-p^{-2}) = 1/\zeta(2) = 6/\pi^2[/tex].
"Martino":
Io ricordo l'approccio intuitivo (non formale): la probabilita' che un numero sia divisibile per un primo [tex]p[/tex] e' [tex]1/p[/tex], quindi la probabilita' che due numeri distinti non siano divisibili entrambi per [tex]p[/tex] e' [tex]1-1/p^2[/tex]. Ne segue che la probabilita' che siano coprimi e' la produttoria [tex]\prod_p (1-1/p^2) = \prod_p (1-p^{-2}) = 1/\zeta(2) = 6/\pi^2[/tex].
Infatti questo e' esattamente l'argomento che viene usato nel paragrafo di wikipedia sulla funzione [tex]\zeta[/tex] che avevo postato io.
C'e' da dire che c'e' sermpre quella clausola minatoria "intuitivo, non formale", per cui magari c'e' qualche dettaglio in cui si annida piu' di un diavolo...
"yoshiharu":Infatti questo e' esattamente l'argomento che viene usato nel paragrafo di wikipedia sulla funzione [tex]\zeta[/tex] che avevo postato io.
[quote="Martino"]Io ricordo l'approccio intuitivo (non formale): la probabilità che un numero sia divisibile per un primo [tex]p[/tex] e' [tex]1/p[/tex], quindi la probabilita' che due numeri distinti non siano divisibili entrambi per [tex]p[/tex] e' [tex]1-1/p^2[/tex]. Ne segue che la probabilita' che siano coprimi e' la produttoria [tex]\prod_p (1-1/p^2) = \prod_p (1-p^{-2}) = 1/\zeta(2) = 6/\pi^2[/tex].
C'e' da dire che c'e' sermpre quella clausola minatoria "intuitivo, non formale", per cui magari c'e' qualche dettaglio in cui si annida piu' di un diavolo...[/quote]Beh, è chiaro che quella non è una dimostrazione, manca qualsiasi tipo di giustificazione formale delle asserzioni, nella fattispecie non si è chiarito com'è definita la probabilitè né se e come sia compatibile con le produttore infinite.
Come dice Martino, giustamente, le probabilità andrebbero formalizzate e contestualizzate. Per farsi un'idea si potrebbe pensare di calcolare la probabilità che scelto un numero naturale in $\{1,...,n\}$ (uniformemente a caso) questo sia coprimo con $n$. Ora la funzione di Eulero $\phi(n)$ (http://en.wikipedia.org/wiki/Euler%27s_totient_function) restituisce il "numero" di interi coprimi con $n$. Qunidi la probabilità cercata sarebbe $\frac{\phi(n)}{n}$. Ora applicando il teorema fondamentale dell'aritmetica a $n$ si perviene alla segeuente $\frac{\phi(n)}{n}=\prod_{p|n}(1-\frac{1}{p})$ (vedere link).
Dato che la funzione di Eulero è moltiplicativa sui numeri coprimi si dovrebbe pervenire alla soluzione del problema iniziale come corollario (cioè la probabilità di coprimalità scelti due numeri a caso).
Se proprio volete cimentarvi sul tema allora potete provare a dare un'occhiata ulteriore: http://ir.library.osaka-u.ac.jp/metadb/ ... 582ojm.pdf
P.S. Se siete dei probabilisti magari date un'occhiata agli altri post che ho lasciato in questa sezione, così mi fate felice, perché gli analisti ci snobbano!
Dato che la funzione di Eulero è moltiplicativa sui numeri coprimi si dovrebbe pervenire alla soluzione del problema iniziale come corollario (cioè la probabilità di coprimalità scelti due numeri a caso).
Se proprio volete cimentarvi sul tema allora potete provare a dare un'occhiata ulteriore: http://ir.library.osaka-u.ac.jp/metadb/ ... 582ojm.pdf
P.S. Se siete dei probabilisti magari date un'occhiata agli altri post che ho lasciato in questa sezione, così mi fate felice, perché gli analisti ci snobbano
!
Ho letto e riletto il testo dell'esercizio e credo che siamo andati un po' oltre a quanto richiesto da quest'ultimo. Insomma alla fine chiede il limite di una successione e non fa riferimento alla probabilità che due numeri siano coprimi. Mi sbaglio? Se non dovessi sbagliarmi, la risoluzione non pretende argomentazioni complicatissime.
Ovviamente la probabilità in questo caso è solo un espediente, tuttavia ci si può approcciare potendo definire il problema, in ambito probabilistico, in uno spazio finito e poi procedendo al limite.
La complicazione deriva dal fatto che su un insieme discreto e infinito non è definita la probabilità uniforme, quindi il testo si dell'esercizio porta a fraintendimenti.
Infine l'esercizio cita "Choose two natural numbers randomly (with uniform probability)".
La complicazione deriva dal fatto che su un insieme discreto e infinito non è definita la probabilità uniforme, quindi il testo si dell'esercizio porta a fraintendimenti.
Infine l'esercizio cita "Choose two natural numbers randomly (with uniform probability)".
Mi sono espresso male, come al solito 
. Cerco di essere più chiaro, per come interpreto io, l'esercizio richiede di determinare, fissato \(n\in\mathbb{N}_{>0}\), una forma chiusa di \(P_n\), al variare di \(n\), dopodiché calcolare il \(\displaystyle \lim_{n\to\infty} P_n\).
Dire che però tale limite coincide con la probabilità che due numeri scelti a caso in \(\mathbb{N}_{>0}\) siano coprimi è tutto un altro paio di maniche.
[Edit importante]: Non mi sono messo a fare i conti, quindi è possibile che non sia così banale determinare una forma chiusa di \(P_n\).
. Cerco di essere più chiaro, per come interpreto io, l'esercizio richiede di determinare, fissato \(n\in\mathbb{N}_{>0}\), una forma chiusa di \(P_n\), al variare di \(n\), dopodiché calcolare il \(\displaystyle \lim_{n\to\infty} P_n\). Dire che però tale limite coincide con la probabilità che due numeri scelti a caso in \(\mathbb{N}_{>0}\) siano coprimi è tutto un altro paio di maniche.
[Edit importante]: Non mi sono messo a fare i conti, quindi è possibile che non sia così banale determinare una forma chiusa di \(P_n\).
"Andrea2976":
P.S. Se siete dei probabilisti magari date un'occhiata agli altri post che ho lasciato in questa sezione, così mi fate felice, perché gli analisti ci snobbano
Mi duole ammettere che hai ragione, caro Andrea. Personalmente mi rendo conto di sapere ben poco di probabilità, purtroppo, anche perché nei corsi universitari da me seguiti ce n'era pochina. Solo questo è il motivo per cui difficilmente riesco ad intervenire nelle discussioni a tema, e non lo snobbare la tua disciplina che, al contrario, apprezzo moltissimo.
Dato che questa problema ha suscitato un po' più di interesse, si può vedere il libro, di Achim Klenke, Probability Theory: A Comprehensive Course.
Guardare "Example 2.6".
P.S. Non so se sia possibile fare l' "upload" di sole due pagine del libro citato senza avere problemi di copyright.
Casomai fosse possibile come posso fare tale upload?
Guardare "Example 2.6".
P.S. Non so se sia possibile fare l' "upload" di sole due pagine del libro citato senza avere problemi di copyright.
Casomai fosse possibile come posso fare tale upload?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo