Sequenza di Farey

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Troleito br00tal
Messaggi: 683
Iscritto il: 16 mag 2012, 22:25

Sequenza di Farey

Messaggio da Troleito br00tal » 02 gen 2017, 13:26

Questa proprietà assurda è stata scoperta da un geologo ed è di dimostrazione del tutto olimpica.

Sia $n$ un intero positivo e sia $0=\frac{p_0}{q_0}<\frac{p_1}{q_1}<...<\frac{p_k}{q_k}=1$ la successione di tutte le frazioni ridotte ai minimi termini con denominatore $\le n$. Si dimostri che $\frac{p_{i-1}+p_{i+1}}{q_{i-1}+q_{i+1}}=\frac{p_i}{q_i}$ per ogni $0<i<k$.

Talete
Messaggi: 742
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Sequenza di Farey

Messaggio da Talete » 02 gen 2017, 17:42

Hint (no soluzione totale)
Testo nascosto:
Se sapessi che
\[\frac{p_{i+1}}{q_{i+1}}-\frac{p_i}{q_i}=\frac1{q_iq_{i+1}}\]
cosa avrei di bello?
Testo nascosto:
In tale caso potrei riscrivere
\[p_{i+1}q_i-p_iq_{i+1}=1.\]
Testo nascosto:
La tesi è equivalente a
\[p_{i-1}q_i-p_iq_{i-1}=p_{i+1}q_i-p_iq_{i+1}.\]
Testo nascosto:
Come faccio a dimostrare il "lemma"? Cosa so di
\[\frac{p_{i+1}}{q_{i+1}}-\frac{p_i}{q_i}?\]
Testo nascosto:
Di sicuro so che si scrive come
\[\frac{k}{q_iq_{i+1}}\]
per qualche $1\le k\le q_iq_{i+1}$.
Testo nascosto:
E adesso boh, non è la soluzione totale quindi non spoilero più nulla.
Piuttosto, problema bonus: trovare il valore di $k$ in funzione di $n$ (magari boh, hint: capire quante frazioni vengono "aggiunte" nel passaggio da $n$ a $n+1$).
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Linda_
Messaggi: 32
Iscritto il: 11 giu 2015, 13:09
Località: Padova, Londra

Re: Sequenza di Farey

Messaggio da Linda_ » 02 gen 2017, 18:07

Oppure si potrebbe continuare dal secondo hint di Talete per via geometrica, assegnando a $\frac{p_i}{q_i}$ il punto nel piano che ha coordinate $(q_i,p_i)$.
Poi da pc magari posto tutta la dimostrazione
"Dev'essere terribile!" "Sì, anche per me è davvero fantastico!"

Linda_
Messaggi: 32
Iscritto il: 11 giu 2015, 13:09
Località: Padova, Londra

Re: Sequenza di Farey

Messaggio da Linda_ » 02 gen 2017, 22:52

Testo nascosto:
Lemma: Presi $\frac{p_i}{q_i}$ e $\frac{p_{i+1}}{q_{i+1}}$ due elementi consecutivi nella sequenza di Farey considerata, $p_{i+1}q_i-p_iq_{i+1}=1$.
Dimostrazione
Assegniamo a $\frac{p_i}{q_i}$ il punto $A_i=(q_i,p_i)$ per ogni $i$ .Naturalmente questi punti sono tutti a 2 a 2 distinti.
Prendiamo le rette del tipo $y=\frac{p_i}{q_i}x$, cioè quelle a cui appartengono gli $A_i$ e passanti per l'origine: essendo $\frac{p_i}{q_i}<\frac{p_{i+1}}{q_{i+1}}$ per ogni $0\leq i<k$, sicuramente troveremo i punti $A_0,A_1,\ldots,A_k$ in ordine, se alla retta $y=mx$ facciamo variare $m$ imponendogli i valori da 0 a 1 (in senso antiorario li troviamo, insomma).
Ora, detta $O$ l'origine degli assi, consideriamo il triangolo $\triangle OA_iA_{i+1}$ per arrivare a dimostrare che ha area $\frac{1}{2}$.
Nei suoi lati non ci sono punti a coordinate intere:
  • - in $OA_i$ e $OA_{i+1}$ è assurdo che ci siano per come abbiamo preso $A_i$ e $A_{i+1}$ perché le rette hanno equazione $y=\frac{p_i}{q_i}x$ e $y=\frac{p_{i+1}}{q_{i+1}}x$ e i coefficienti angolari sono ridotti ai minimi termini per ipotesi;
    - nel lato $A_iA_{i+1}$ non ce ne sono perché se ce ne fosse almeno uno, allora questo avrebbe ascissa $a$ con $q_i<a<q_{i+1}$ (oppure $q_{i+1}<a<q_i$, ma non ci cambia nulla) ed ordinata $b$ e sicuramente $\frac{b}{a}$ è minore di 1 e ha $a<n$.
    Se $\gcd(a,b)=1$ allora questo punto dovrebbe identificare un elemento della successione pure lui, ma questo è assurdo perché abbiamo detto che andando da $A_i$ ad $A_{i+1}$ in senso antiorario non ci sono altri punti della successione.
    Se $\gcd(a,b)>1$ allora la frazione $\frac{b}{a}$, dopo essere stata ridotta ai minimi termini, è un elemento della successione, quindi definiamo $A_j$ il punto che lo identifica nel piano; alla luce di questo il punto di coordinate $(a,b)$ sta sulla retta $OA_j$, che a sua volta sta tra $OA_i$ e $OA_{i+1}$, assurdo per come abbiamo preso $A_i$ e $A_{i+1}$!
Inoltre all'interno del nostro triangolo non ci sono punti a coordinate intere, per lo stesso motivo esposto appena sopra.
Dunque per Pick $S_{OA_iA_{i+1}}=\frac{1}{2}$.
Consideriamo ora i vettori $\vec{v}=\vec{OA_i}$ e $\vec{w}=\vec{OA_{i+1}}$.
Si ha che $\vec{v}\times\vec{w}=p_{i+1}q_i-p_iq_{i+1}$, ed essendo il prodotto vettoriale l'area del parallelogramma che ha due lati in $\vec{v}$ e $\vec{w}$,che a sua volta è pari a $2S_{OA_iA_{i+1}}=1$, allora otteniamo che $2S_{OA_iA_{i+1}}=p_{i+1}q_i-p_iq_{i+1}$, e questo implica che $p_{i+1}q_i-p_iq_{i+1}=1$, ovvero la tesi del nostro lemma.


Ritorniamo ora al problema e consideriamo $\frac{p_{i-1}}{q_{i-1}},\frac{p_i}{q_i},\frac{p_{i+1}}{q_{i+1}}$.
Per il lemma valgono
$$p_{i+1}q_i-p_iq_{i+1}=1 \hspace{1.5cm} p_iq_{i-1}-p_{i-1}q_i=1$$
da cui $p_{i+1}q_i-p_iq_{i+1}=p_iq_{i-1}-p_{i-1}q_i$. Riscrivendo,
$$p_i(q_{i-1}+q_{i+1})=q_i(p_{i-1}+p_{i+1})$$
e dividendo entrambi i membri per $q_i(q_{i-1}+q_{i+1})$ che tanto è diverso da 0 otteniamo proprio la tesi del problema.
Edit: qualche typo
Ultima modifica di Linda_ il 03 gen 2017, 10:48, modificato 1 volta in totale.
"Dev'essere terribile!" "Sì, anche per me è davvero fantastico!"

Talete
Messaggi: 742
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

Re: Sequenza di Farey

Messaggio da Talete » 03 gen 2017, 10:40

Woo, bella la soluzione geometrica, Linda! Non ci avevo pensato ;)

Qualcuno per il problema bonus? È una scemenza dimostrarlo, una volta trovato il valore...
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

Linda_
Messaggi: 32
Iscritto il: 11 giu 2015, 13:09
Località: Padova, Londra

Re: Sequenza di Farey

Messaggio da Linda_ » 03 gen 2017, 12:59

Grazie :)

Per il bonus, $k=1+\sum_{i=2}^{n}{\phi(i)}$.
Infatti ad ogni passaggio da $n$ a $n+1$ vengono aggiunte $\phi(n+1)$ frazioni, cioè quelle con denominatore $n+1$ e numeratore minore di $n+1$ e coprimo col denominatore. Questo perché le altre con denominatore $n+1$ e numeratore non coprimo con $n+1$ appartenevano già alla successione di "ordine" minore perché se ridotte ai minimi termini hanno denominatore $<n+1$.
Poi per $n=1$ abbiamo $k=2$ perché le frazioni della successione sono $0/1$ e $1/1$, dunque le frazioni della successione fissato $n$ sono $2+\sum_{i=2}^{n}{\phi(i)}$, da cui
$$k=1+\sum_{i=2}^{n}{\phi(i)}$$

Edit: non mi ero accorta che partiva da $\frac{p_0}{q_0}$ e non da $\frac{p_1}{q_1}$, sistemato
"Dev'essere terribile!" "Sì, anche per me è davvero fantastico!"

Rispondi