Sequenze di Farey ed equazioni diofantee lineari in due indeterminate

Donato Saeli

donato.saeli@gmail.com

II PARTE

 

La prima parte di questo articolo è stata pubblicata nel numero di Ottobre 2018.

Versione in pdf di questo articolo.

2. Approssimazioni Diofantee

Il dato di fatto da cui muoviamo è che l’insieme dei numeri razionali  è denso (ovunque) sulla retta reale; cioè:
Se \( \xi \) è un numero reale, per ogni \( \varepsilon > 0, \) vi sono  (infiniti) numeri razionali
\[\dfrac{h}{k} \neq \xi \quad \text{tali  che}\quad \Big|\;\xi – \dfrac{h}{k} \, \Big| < \varepsilon. \quad  (11) \]

Tutto ciò è nella “natura” dei numeri reali, indipendentemente dalla via seguita per la loro costruzione; naturalmente sorgono diverse questioni, una fra le più importanti è la seguente:

Fissati \( \xi \) e \( \varepsilon, \) è possibile determinare le frazioni \(\dfrac{h}{k} \) con denominatore minimo che verificano le  (11)?

La risposta è affermativa, ma non del tutto semplice. Il risultato principale in questa direzione consiste nel  seguente

Teorema 4 (Dirichlet 1842)

Se \( \xi \) è un irrazionale,  \( 0 < \xi < 1 \)  e \( N \) un numero naturale, allora vi è una frazione ridotta  \(\dfrac{h}{k},\)  con \(k \leq N,\)  tale  che  \( \Big| \, \xi – \dfrac{h}{k} \, \Big| < \dfrac{1}{k(N+1)}.\)

Dimostrazione 1

Consideriamo la sequenza di Farey \( F_N, \) di ordine \( N. \)

Poichè \( 0 < \xi < 1, \) c’è in \( F_N, \) esattamente una coppia di frazioni consecutive e perciò adiacenti2 \(\dfrac{a}{b}\) e \(\dfrac{c}{d}\) per cui \(\dfrac{a}{b}<\xi<\dfrac{c}{d}\).

 

Se consideriamo la loro mediante, deve essere \(\dfrac{a}{b}<\xi<\dfrac{a+c}{b+d}\)  oppure \(\dfrac{a+c}{b+d}<\xi<\dfrac{c}{d},\) (con le disuguaglianze strette perchè \( \xi \) è irrazionale).

Abbiamo: \(b+d \geq N+1,\) perchè \(\dfrac{a+c}{b+d} \notin F_N\) dunque
\[0< \xi – \dfrac{a}{b} < \dfrac{a+c}{b+d} – \dfrac{a}{b} = \dfrac{bc-ad}{b(b+d)} = \dfrac{1}{b(b+d)} \leq \dfrac{1}{b(N+1)},\]

oppure

\[0< \dfrac{c}{d} – \xi < \dfrac{c}{d} – \dfrac{a+c}{b+d} = \dfrac{bc-ad}{d(b+d)} = \dfrac{1}{d(b+d)} \leq \dfrac{1}{d(N+1)}.\]

Infine, poichè \(\dfrac{a}{b}\) e \(\dfrac{c}{d}\) appartengono a \(F_N,\) sono ridotte e con \(b, d \leq N.\)

 

Il teorema 4 continua a valere anche nel caso in cui \( \xi \) sia razionale: \( \xi = \dfrac{\lambda}{\mu}\,, \) frazione ridotta, con \( \underline{\mu > N + 1}; \) tale condizione implica che \( \dfrac{\lambda}{\mu} \! \notin \! F_N.\)

Possiamo perciò seguire la dimostrazione precedente, tenendo conto però che può essere \( \dfrac{\lambda}{\mu} = \dfrac{a+c}{b+d}, \) ma in tal caso risulta:
\[0 < \dfrac{c}{d} – \dfrac{\lambda}{\mu} = \dfrac{c}{d} – \dfrac{a+c}{b+d} = \dfrac{1}{d(b+d)} = \dfrac{1}{d\mu} < \dfrac{1}{d(N+1)}\] ed anche
\(0 < \dfrac{\lambda}{\mu} – \dfrac{a}{b} = \dfrac{a+c}{b+d} – \dfrac{a}{b} = \dfrac{1}{b(b+d)} = \dfrac{1}{b\mu} < \dfrac{1}{b(N+1)}.\) 3

Abbiamo così dimostrato anche il seguente

Teorema 5

Siano \( \dfrac{\lambda}{\mu} \) una frazione ridotta, con \( 0 < \lambda < \mu \) e \( N \) un numero naturale.  Se \( \mu > N + 1, \) allora vi è una frazione ridotta \( \dfrac{h}{k}, \) con \( k \leq N, \)  tale che \( \Big| \, \dfrac{\lambda}{\mu} – \dfrac{h}{k} \, \Big| < \dfrac{1}{k(N+1)}\,. \)

I teoremi 4 e 5 sono di importanza fondamentale nella teoria dei numeri ed in molte applicazioni, ma suscitano anche qualche perplessità; ad esempio come si determina la coppia di frazioni consecutive in \( F_N\,, \) per cui \(\dfrac{a}{b}<\xi<\dfrac{c}{d}\) ?

 

3. L’algoritmo “di lenta migrazione

Vogliamo descrivere un algoritmo molto semplice, noto col nome di lenta migrazione, che risponde a questa domanda e permette anche di risolvere la questione sollevata all’inizio del paragrafo.

Supponiamo che \( \xi = \dfrac{\lambda}{\mu} \) sia una frazione  ridotta, con \( 0 < \lambda < \mu\,. \)

Siano \( \dfrac{A}{B}\,,  \dfrac{C}{D}  \) frazioni consecutive in \( F_n \) tali che \(\ \dfrac{A}{B} < \dfrac{\lambda}{\mu} < \dfrac{C}{D}\,, \)4 e consideriamo la loro mediante \(\ \dfrac{l}{m} = \dfrac{A + C}{B + D}\,. \)

 

Le frazioni \( \dfrac{A}{B}\,, \ \, \dfrac{l}{m} \ \, \text{e} \ \, \dfrac{C}{D} \) sono nell’ordine, consecutive in \( F_m\,, \) con \( m = b + d > n\,; \ \) e può essere \( \ \dfrac{A}{B} < \dfrac{\lambda}{\mu} < \dfrac{l}{m}\,, \ \) oppure  \( \ \dfrac{l}{m} < \dfrac{\lambda}{\mu} < \dfrac{C}{D}\,. \)

 

Se \( \ \dfrac{A}{b} < \dfrac{\lambda}{\mu} < \dfrac{l}{m}\,, \ \) poniamo \(\ \dfrac{A’}{B’} = \dfrac{A}{B} \ \) e \(\ \dfrac{C’}{D’} = \dfrac{l}{m}\,; \)

se invece \( \ \dfrac{l}{m} < \dfrac{\lambda}{\mu} < \dfrac{C}{D}\,, \ \) poniamo \(\ \dfrac{A’}{B’} = \dfrac{l}{m} \ \) e \(\ \dfrac{C’}{D’} = \dfrac{C}{D}\,. \)

In ogni caso abbiamo \( \dfrac{A’}{B’} < \dfrac{\lambda}{\mu} < \dfrac{C’}{C’}\,, \) con \( \dfrac{A’}{B’}\) e \(\dfrac{C’}{D’} \) consecutive in \( F_m\,, \)

possiamo perciò ripetere lo stesso ragionamento, considerando la loro mediante \(\ \dfrac{l’}{m’} = \dfrac{A’ + C’}{B’ + D’}\, \ \) in \( F_{m’}\) con \( m’ > m > n\,. \ \)

Posto \(\ \dfrac{A”}{B”} = \dfrac{A’}{B’} \ \) e \(\ \dfrac{C”}{D”} = \dfrac{l’}{m’}\,, \ \) se \(\ \dfrac{\lambda}{\mu} < \dfrac{l’}{m’}\,, \)

oppure \(\ \dfrac{A”}{B”} = \dfrac{l’}{m’} \ \) e \(\ \dfrac{C”}{D”} = \dfrac{C’}{D’}\,, \ \) se\(\ \dfrac{l’}{m’} < \dfrac{\lambda}{\mu}\,, \)

abbiamo \(\ \dfrac{A”}{B”} < \dfrac{\lambda}{\mu} < \dfrac{C”}{D”}\,, \ \) con \(\ \dfrac{A”}{B”} \ \ \text{e} \ \ \dfrac{C”}{D”} \ \)  consecutive in \( F_{m’}\,; \) ecc. …

.   .   .   .   .   .   .   .   .   .   .   .   .   .   .

.   .   .   .   .   .   .   .   .   .   .   .   .   .   .

.   .   .   .   .   .   .   .   .   .   .   .   .   .   .

Finchè: \(\ \dfrac{l^{(s)}}{m^{(s)}} = \dfrac{\lambda}{\mu} \,. \quad \)

Infatti la sequenza \( m\,, \, m’,\, m”,\, \dots \,, m^{(r)},\, \dots \,, \)
dei denominatori delle medianti successive è strettamente crescente;
pertanto vi è un indice \( s \) per cui \( m^{(s-1)} < \mu \leq m^{(s)}\,. \)

Perciò \( \dfrac{\lambda}{\mu} \) non è elemento di \( F_{m^{(s-1)}} \) e dunque deve essere anche \( \mu \geq m^{(s)}\,. \)5

Notiamo che se \( N < \mu \) è un numero naturale fissato, vi è un indice \( r \) tale che \( m^{(r-1)} \leq N < m^{(r)}\,. \)

Ora le frazioni \( \dfrac{A^{(r)}}{B^{(r)}} \ \, \text{e} \ \, \dfrac{C^{(r)}}{D^{(r)}} \) consecutive in \( F_{m^{(r-1)}}\,, \) rimangono tali in tutte le sequenze \( F_j\,, \) con \( m^{(r-1)} \leq j < m^{(r)}\,, \) e quindi costituiscono la coppia di frazioni consecutive in \( F_N \) fra cui si colloca \( \dfrac{\lambda}{\mu}\,. \)

Fissato infine \( \varepsilon > 0\,, \) ad ogni passo del procedimento possiamo valutare

\[\delta = \Big| \, \dfrac{\lambda}{\mu} – \dfrac{l^{(r)}}{m^{(r)}} \, \Big| \quad \] e fermarci se \( \delta < \varepsilon\,. \)

Anche per l’algoritmo di lenta migrazione abbiamo un programma in linguaggio C: falemi.c con cui abbiamo prodotto i risultati esposti negli esempi che seguono.

 

 Esempio IV (banale ma non troppo).

Se \(\ \dfrac{\lambda}{\mu} = \dfrac{77}{100}\,, \ \) abbiamo:
\[\Big(\dfrac{\lambda}{\mu} – \dfrac{A^{(r)}}{B^{(r)}}\Big) \hspace{16.5mm} \dfrac{A^{(r)}}{B^{(r)}} \hspace{25mm} \dfrac{C^{(r)}}{D^{(r)}} \hspace{17mm} \Big(\dfrac{C^{(r)}}{D^{(r)}} – \dfrac{\lambda}{\mu}\Big) \]

 

Il programma “falemi” inizia l’elaborazione con le “frazioni” \(0/1 \) e \(1/1\), ma non riporta la prima riga; così abbiamo simulato di iniziare con le frazioni \(1/2\) e \(1/1\)  aggiungendo a fine riga (0) la distanza fra  \(77/100\) e \(1/1\).

In ogni riga il programma scrive a fianco della mediante generata dalle due frazioni della riga precedente, la distanza fra questa e la \( \lambda/\mu\,. \)

Scopriamo nella riga (5) che in base al suo denominatore, la frazione \(10/13 \) è una approssimazione “ottima” di \(77/100\);6 una migliore è data solo nella riga (9) dalla frazione \(47/61\).

Se ad esempio consideriamo la sequenza \( F_{25}\,, \) le righe (6) e (7) ci dicono che le frazioni consecutive fra le quali si colloca \(77/100\) in tale sequenza, sono \(10/13\) e \(17/22\) e che in base al Teorema 5,

\[ \Big| \, \dfrac{77}{100} – \dfrac{10}{13} \, \Big| < \dfrac{1}{13 \cdot (25 + 1)} < 2,95858 \cdot 10^{-3}\,. \]

Raffigurazione delle righe (1)-(5).

Esempio V (Classico, ma più serio).

Poniamo sia \(\quad \xi = 0,14159265\dots\,, \)7osserviamo che questo è il modo più comune per indicare un numero reale; ma questa espressione ci dice solo che
\( 0,14159265 = \xi_1 = \dfrac{2831853}{20000000} \leq \xi \leq \dfrac{7.079.633}{50.000.000} = \xi_2 = 0,14159266\,, \) dove le frazioni che rappresentano \( \xi_1 \) e \( \xi_2 \) sono ridotte e \( \xi_2 – \xi_1 = 10^{-8}\,. \)

Procediamo applicando l’algoritmo di lenta migrazione su \( \xi_1 = \dfrac{2831853}{20000000}\,. \)
\[ \Big(\dfrac{\lambda}{\mu} – \dfrac{A^{(r)}}{B^{(r)}}\Big) \hspace{16.5mm} \dfrac{A^{(r)}}{B^{(r)}} \hspace{25mm} \dfrac{C^{(r)}}{D^{(r)}} \hspace{17mm} \Big(\dfrac{C^{(r)}}{D^{(r)}} – \dfrac{\lambda}{\mu}\Big) \]

Anche in questo caso troviamo una riga “speciale”, la (21), vi compaiono le due frazioni \(15/106\) e \(16/113\) consecutive in \( F_{113}\,; \) mediante la riga successiva ed il Teorema 5 abbiamo:
\[ \Big| \, \xi_1 – \dfrac{16}{113} \, \Big| < \dfrac{1}{113 \cdot (113 + 1)} < 7,7627698 \cdot 10^{-5}\,. \]

Di nuovo la stima stabilita in base al Teorema 5 risulta modesta in confronto al valore effettivo della distanza \( \dfrac{16}{113} – \xi_1 < 2,70354 \cdot 10^{-7}\,; \) per ottenere una distanza minore occorre raggiungere la riga (165) con la frazione \(2319/16.378\,.\)

Notiamo anche come dalla riga (22) alla (309) le medianti successive si spostino, “migrando lentamente”, verso le frazioni \( \xi_1 \) e \(16/113\,.\)

Osserviamo infine che è anche \( \dfrac{16}{113} – \xi_2 < 2,60354 \cdot 10^{-7}\,; \)
pertanto \( \dfrac{16}{113} – \xi < 2,70354 \cdot 10^{-7}\,; \) per ogni numero \(\ \xi\,, \) \(\ \xi_1 < \xi < \xi_2\,. \)

In particolare  \(\ \xi_1 < \pi – 3 < \xi_2 \ \) ed abbiamo:
\[\Big| \, \pi – 3 – \dfrac{16}{113} \, \Big| = \Big| \, \pi – \dfrac{355}{113} \, \Big| < 2,70354 \cdot 10^{-7}\,. \]

 

4. L’algoritmo “ideale”

Tornando alla questione posta a fine § 2, ovviamente una soluzione alternativa sarebbe scorrere nell’ordine le frazioni della sequenza \( F_n \) fino a trovare la prima che supera \( \lambda / \mu\,; \) vale a dire, fissato \( n\,, \) potere consultare la tavola contenente nell’ordine, gli elementi di \( F_n\,. \)

Come disporre in tempo reale di una tavola con nell’ordine, gli elementi di \( F_n\,, \) per ogni \( n \) non eccessivamente grande, ci viene indicato dalla seguente

Proposizione 6

Se \( \dfrac{a}{b} < \dfrac{c}{d} < 1\,, \) sono frazioni consecutive in \( F_n\,, \) allora la frazione che segue \( \dfrac{c}{d} \) nella stessa sequenza è \( \dfrac{sc-a}{sd-b}\,, \) dove \( s = \Big\lfloor \dfrac{b+n}{d}\Big\rfloor\,. \)8

Conviene anteporre alla dimostrazione due lemmi.

Lemma 7

Se \( bc – ad = 1 \) e \( s > r > \dfrac{b}{d}\,, \) allora \( \dfrac{sc-a}{sd-b} < \dfrac{rc-a}{rd-b}\,. \)

Dimostrazione

Da \( bc – ad = 1\, \)  e  \(s > r\) segue \( rbc – rad < sbc – sad\, \) ed anche \(scrd + ab – rad -sbc < scrd + ab – sad -rbc\,, \) ossia \( (sc-a)(rd-b) < (sd-b)(rc-a)\,. \)

Poichè \( s > \dfrac{b}{d} \, \)  e  \( r > \dfrac{b}{d} \) implicano \( (rd-b)(sd-b) > 0\,, \) otteniamo l’asserto.

Lemma 8

Se \( \dfrac{a}{b}\,, \ \dfrac{c}{d}\,, \ \dfrac{e}{f} \) sono consecutive in \( F_n\,, \) allora \( \dfrac{c}{d} = \dfrac{a+e}{b+f}\,. \)

Dimostrazione

Abbiamo \( bc – ad = 1 \, \)  e  \( de – cf = 1\,; \)  sottraendo queste membro a membro otteniamo \( bc – ad – de + cf = 0\,, \) da cui \( c(b+f) = d(a+e)\,. \)

Notiamo che la frazione \( \dfrac{a+e}{b+f} \) può  non essere ridotta, perchè le frazioni
\(\dfrac{a}{b}\, \)  e  \( \dfrac{e}{f} \) possono non essere adiacenti.

Ad esempio le frazioni \( \dfrac{3}{5}\,, \ \dfrac{2}{3}\,, \ \dfrac{5}{7}\, \) sono consecutive in \( F_7 \, \)  e  \( \dfrac{3+5}{5+7} = \dfrac{8}{12} = \dfrac{2}{3}\,; \) infatti le frazioni \( \dfrac{3}{5} \, \)  e  \(\dfrac{5}{7} \) non sono adiacenti \( (1 \neq 5 \times 5 – 7 \times 3 = 4)\,. \)

 

Dimostrazione della Proposizione 6

Indichiamo con \( \dfrac{x}{y} \) la frazione successiva alle due frazioni \( \dfrac{a}{b}\, \) e \( \dfrac{c}{d} \) in \( F_n\,. \) Così  \( \dfrac{c}{d} \, \) deve essere la mediante fra \( \dfrac{a}{b}\)  e \(\dfrac{x}{y} \) cioè \( \dfrac{c}{d}= \dfrac{a+x}{b+y} \) (Lemma 8).

Poichè \( \dfrac{a+x}{b+y} \) può non essere ridotta, abbiamo \( a + x = k \cdot c \) e \( b + y = k \cdot d\,, \) ossia \( x = k \cdot c -a \) e \( y = k \cdot d – b\,; \) ma \( \dfrac{x}{y} \) è un elemento di \( F_n \) e perciò \( 1 \leq y = k \cdot d – b \leq n \) da cui \( \dfrac{b+1}{d} \leq k \leq \dfrac{b+n}{d}\,. \)

Consideriamo ora la “funzione” \( g(t) = \dfrac{ct-a}{dt-b}\,, \quad t \in \mathbb{R} \smallsetminus \{b/d\}\,, \) decrescente, per \( t > \dfrac{b}{d} \) (Lemma 7).

Abbiamo: \(g\Big(\dfrac{b+1}{d}\Big) = \dfrac{c}{d} + \dfrac{1}{d} \leq 1\) e \(g\Big(\dfrac{b+n}{d}\Big) = \dfrac{c}{d} + \dfrac{1}{dn}\,; \)
cosicchè le frazioni \( g(r) = \dfrac{rc-a}{rd-b},\) per \(r = \Big\lceil\dfrac{b+1}{d}\Big\rceil, \dots , \Big\lfloor \dfrac{b+n}{d}\Big\rfloor\) appartengono tutte a \( F_n \) e \( \dfrac{x}{y} \) ne è la più piccola, cioè \(\dfrac{x}{y} = \dfrac{sc-a}{sd-b},\) dove \(s = \Big\lfloor \dfrac{b+n}{d}\Big\rfloor.\)

In particolare, per \(\dfrac{0}{1}\) e \(\dfrac{1}{n}\) si ha \(s = \Big\lfloor \dfrac{b+n}{d}\Big\rfloor = \Big\lfloor \dfrac{1+n}{n}\Big\rfloor = 1,\) se \(n \geq 2\)  e la frazione successiva è \(\dfrac{1}{n-1}.\)

 

Esempio VI

Determinare, nell’ordine, le frazioni della sequenza   \(F_7\,. \)

Le prime tre sono \(\dfrac{0}{1}\,, \ \ \dfrac{1}{7}\) e \(\dfrac{1}{6}\,;\)

alla coppia \(\dfrac{1}{7}\,, \ \ \dfrac{1}{6}\) corrisponde \(s= \Big\lfloor \dfrac{7+7}{6} \Big\rfloor =2\) e \(\dfrac{x}{y}= \dfrac{2 \cdot 1-1}{2 \cdot 6-7}= \dfrac{1}{5}\)

alla coppia \(\dfrac{1}{6}\,, \ \ \dfrac{1}{5}\) corrisponde \(s= \Big\lfloor \dfrac{6+7}{5} \Big\rfloor =2\) e \(\dfrac{x}{y}= \dfrac{2 \cdot 1-1}{2 \cdot 5-6}= \dfrac{1}{4}\)

”                ” \(\dfrac{1}{5}\,, \ \ \dfrac{1}{4}\)           ”           \(s= \Big\lfloor \dfrac{5+7}{4} \Big\rfloor =3\) ”  \(\dfrac{x}{y}= \dfrac{3 \cdot 1-1}{3 \cdot 4-5}= \dfrac{2}{7}\)

”                ” \(\dfrac{1}{4}\,, \ \ \dfrac{2}{7}\)           ”           \(s= \Big\lfloor \dfrac{4+7}{7} \Big\rfloor =1\) ”  \(\dfrac{x}{y}= \dfrac{1 \cdot 2-1}{1 \cdot 7-4}= \dfrac{1}{3}\)

”                ” \(\dfrac{2}{7}\,, \ \ \dfrac{1}{3}\)           ”           \(s= \Big\lfloor \dfrac{7+7}{3} \Big\rfloor =4\) ”  \(\dfrac{x}{y}= \dfrac{4 \cdot 1-2}{4 \cdot 3-7}= \dfrac{2}{5}\)

”                ” \(\dfrac{1}{3}\,, \ \ \dfrac{2}{5}\)           ”           \(s= \Big\lfloor \dfrac{3+7}{5} \Big\rfloor =2\) ”  \(\dfrac{x}{y}= \dfrac{2 \cdot 2-1}{2 \cdot 5-3}= \dfrac{3}{7}\)

”                ” \(\dfrac{2}{5}\,, \ \ \dfrac{3}{7}\)           ”           \(s= \Big\lfloor \dfrac{5+7}{7} \Big\rfloor =1\) ”  \(\dfrac{x}{y}= \dfrac{1 \cdot 3-2}{1 \cdot 7-5}= \dfrac{1}{2}.\)

Ora va da sè che le frazioni successive sono nell’ordine:
\(\dfrac{4}{7}\,, \ \ \dfrac{3}{5}\,, \ \ \dfrac{2}{3}\,, \ \ \dfrac{5}{7}\,, \ \ \dfrac{3}{4}\,, \ \ \dfrac{4}{5}\,, \ \ \dfrac{5}{6}\,, \ \ \dfrac{6}{7}\)  e \(\dfrac{1}{1}\) 9
è bene comunque notare che alla coppia \(\dfrac{5}{6}\,, \ \ \dfrac{6}{7}\) corrisponde \(s= \Big\lfloor \dfrac{6+7}{7} \Big\rfloor =1\) e \(\dfrac{x}{y}= \dfrac{1 \cdot 6-5}{1 \cdot 7-6}= \dfrac{1}{1}\,.\)

Rimane evidente che dalla Proposizione 6 possiamo ricavare un algoritmo sufficientemente veloce, con modesto impiego di memoria, in grado di sviluppare tavole complete per sequenze di Farey di ordine relativamente grande.

Il programma   fsq.c è in grado generare in pochi secondi un file testo contenente la sequenza \( F_{4100} \)  (131 MegaByte, 5.110.923 frazioni), ancora facilmente consultabile (sull’elaboratore), nonostante l’imponente dimensione.

L’immagine che segue ne riproduce un frammento con un “elemento famoso”

L’impresa di Neville, evidentemente all’oscuro della Prop. 6, con solo carta, matita e metodi suoi originali, certo più complicati e faticosi, è stata veramente eroica.

Possiamo infine determinare, nell’ordine, le frazioni di una sequenza di Farey \( F_n, \) successive ad una sola frazione fissata.

Se \( \dfrac{l}{m} \in F_n, \ \; 0 < l < m\,, \) consideriamo l’equazione diofantea
\[ mx – ly = 1;\quad\quad (12) \]
sappiamo che la \( (12) \) ammette una soluzione particolare \(\ \ (x_0,y_0),\) con \( 1 \leq x_0 \leq l, \quad\) e la soluzione generale \(\ \ (x_0 + sl,y_0 + sm), \quad \forall s \in \mathbb{Z} \) (cfr. Parte I, pp. 4-5).

Ne segue \(\ \ m – 1 \leq mx_0 – 1 \leq ml – 1\) e \(\ \ \dfrac{m}{l} – \dfrac{1}{l} \leq y_0 \leq m – \dfrac{1}{l}, \ \ \) vale a dire \(\ \ 1 \leq y_0 \leq m – 1;\) così \(\ \ (x_0,y_0) \ \ \) è la soluzione della \( (12) \) con componenti positive minime.

Poichè \(\ \ 0 < l < m \ \ \) implica \(\ \ 0 < lx_0 < mx_0 = ly_0 + 1 \ \ \) ed anche \(\ \ x_0 \leq y_0, \ \ \) possiamo concludere che le frazioni \(\ \ \dfrac{l}{m} \ \) e \(\ \dfrac{x_0}{y_0} \ \ \) sono consecutive in \( F_m, \) potrebbero però non esserlo in \( F_n\,; \ \ \) se questo è il caso, osserviamo che le frazioni \(\ \ \dfrac{l}{m} \ \) e \(\ \dfrac{rl + x_0}{rm + y_0} \ \ \) sono adiacenti, \(\ \forall r \in \mathbb{N}.\)10

Se scegliamo allora \(\ \bar{r} = \Big\lfloor \dfrac{n – y_0}{m} \Big\rfloor, \ \) otteniamo la frazione \(\ \dfrac{\bar{r}l + x_0}{\bar{r}m + y_0} \ \) consecutiva a \(\ \dfrac{l}{m} \ \) in \(\ F_n\,.\)

 

Esempio VII

Determinare le prime tre frazioni successive alla frazione \(\dfrac{65}{263}\) nella sequenza \(F_{521}.\)

Consideriamo l’equazione diofantea \(263x-65y=1,\) si vede facilmente che\((22,89)\) ne è la soluzione con i termini positivi minimi; ne segue che le frazioni \(\dfrac{65}{263}\) e \(\dfrac{22}{89}\) sono consecutive in \(F_{263}\) e così le frazioni \(\dfrac{65}{263}\) e \(\dfrac{65+22}{263+89}=\dfrac{87}{352}\) sono consecutive in\(F_{521}.\)

Procedendo ora come nell’Esempio VI, alla coppia \(\dfrac{65}{263} \ \ \dfrac{87}{352}\) corrisponde

\(s= \Big\lfloor \dfrac{263+521}{352} \Big\rfloor =2\) e la frazione \(\dfrac{x}{y}= \dfrac{2 \cdot 87-65}{2 \cdot 352-263}= \dfrac{109}{441}\) e quindi alla coppia

\(\dfrac{87}{352} \ \ \dfrac{109}{441}\) corrisponde \(s= \Big\lfloor \dfrac{352+521}{441} \Big\rfloor =1\)

e la frazione \(\dfrac{x}{y}= \dfrac{1 \cdot 109-87}{1 \cdot 441-352}= \dfrac{22}{89}\) per l’appunto.

 

Appendice

Sequenze di Farey: Breve elenco di definizioni e proprietà.

i)  Se \( \dfrac{a}{b} \ \text{e} \ \dfrac{c}{d} \) sono frazioni tali che \( \dfrac{a}{b} < \dfrac{c}{d}, \) allora \( \dfrac{a}{b} < \dfrac{a+c}{b+d} < \dfrac{c}{d}\,; \)

la frazione \( \dfrac{a+c}{b+d} \) si dice mediante di \( \dfrac{a}{b} \ \text{e} \ \dfrac{c}{d}\,. \)

ii)  Se \( \dfrac{a}{b} \ \text{e} \ \dfrac{c}{d} \) sono frazioni tali che \( bc – ad = 1, \) allora devono essere necessariamente ridotte;

due frazioni \( \dfrac{a}{b} \) e  \(\dfrac{c}{d} \) che sodddisfano la condizione \( bc – ad = 1, \) si dicono  adiacenti.

iii) Se le frazioni \( \dfrac{a}{b}\) e \(\text{e} \ \dfrac{c}{d} \) sono adiacenti, allora anche le frazioni \( \dfrac{a}{b} \) e  \( \dfrac{a+c}{b+d} \) e le frazioni \( \dfrac{a+c}{b+d} \)  e \( \dfrac{c}{d} \) lo sono.

iv) Se \( \dfrac{a}{b} \) e \( \dfrac{c}{d} \) sono adiacenti e \( \dfrac{h}{k} \) è una frazione ridotta tale che \( \dfrac{a}{b} < \dfrac{h}{k} < \dfrac{c}{d}, \) allora è \( k \geq b+d; \) e se \( k = b+d, \) allora \( \dfrac{h}{k} = \dfrac{a+c}{b+d}. \)

Se \( n \) è un intero positivo, si dice sequenza di Farey di ordine  \( n \) e si indica con \( F_n \, , \) la totalità delle frazioni ridotte \( h/k \) tali che: \( 1 \leq k \leq n \) e\(\; 0/1 \leq h/k \leq 1/1 \, ; \) disposte in ordine crescente.

v) In ogni sequenza di Farey due frazioni consecutive sono adiacenti (Teorema di Farey-Cauchy).

vi) Se è \(n>1\), allora due frazioni consecutive in \(F_n\) non possono avere lo stesso denominatore.

L’ultimo asserto è conseguenza immediata del Teorema di Farey-Cauchy:
Se \(\dfrac{h}{k}\) e \(\dfrac{h+l}{k}\) sono consecutive in \(F_n\), deve essere \(k(h+l)-hk=kl=1\), da cui \(k=l=1\), così \(h=0\) e \(n=1\); cioè la sequenza è necessariamente la \(F_1\) e le due frazioni \(\dfrac{0}{1}\) e \(\dfrac{1}{1}\,.\)

 

Bibliografia

[8] Beiler, A. H., Recreations in the Theory of Numbers Dover, New York, 1964.
[9] Hardy G. H., Wright E. M., An introduction to the theory of numbers, Clarendon Press, Oxford, 1979.
[10] Neville E. H., The structure of Farey series, Proc. London Maths. Soc., (Ser. 2) 51 (1949), 132-144.
[11] Neville E. H., The Farey series of order 1025, Cambridge University Press, 1950.
[12] Richards Ian, Continued Fractions Without Tears, Mathematics Magazine, 54-4 (1981) 163-171.
[13] Routledge Norman, Computing Farey Series, The Mathematical Gazette, 92-(523), 55–62.

Note

  1. La dimostrazione che esporremo segue una linea diversa dall’originale, poichè poggia su alcune proprietà delle sequenze di Farey; il lettore può trovare le definizioni e le proposizioni necessarie nell’Appendice I, o in [4], oppure anche in [9].
  2. Due frazioni \( \dfrac{a}{b} \ \text{e} \ \dfrac{c}{d} \) si dicono adiacenti  se \( bc – ad = 1\)
  3. Notiamo che se \( \mu=N+1, \)  da \( \dfrac{a}{b} < \dfrac{\lambda}{\mu} < \dfrac{c}{d} \)  in \( F_N \) segue \(\dfrac{\lambda}{\mu} = \dfrac{a+c}{b+d};\) pertanto  \( \dfrac{c}{d} – \dfrac{\lambda}{\mu} = \dfrac{1}{d(N+1)} \)  e \( \dfrac{\lambda}{\mu} – \dfrac{a}{b} = \dfrac{1}{b(N+1)}.\)
  4. \( \dfrac{0}{1} \) e \( \dfrac{1}{1} \) sono consecutive in \( F_1 \)  e da \( 0 < \lambda < \mu \) segue \( 0 < \dfrac{\lambda}{\mu} < 1\,; \ \)
    così  per iniziare possiamo sempre scegliere questa coppia di frazioni.
  5. Cfr. i punti iv) e v) dell’Appendice.
  6. L’aggettivo “ottimo” è appropriato e non casuale; ma questa è un’altra storia (frazioni  continue cfr [12]).
  7. I puntini rappresentano una successione (infinita) di cifre omesse.
  8. Non è chiara l’origine di questo enunciato. Con precisione, neanche l’anno in cui viene reso noto (intorno al 1957 ?); la prima citazione che abbiamo, sotto forma di regola, è in [8].
  9. Impieghiamo la trasformazione dell’intervallo \( [0,1] \) che manda \( x \) in \( 1 – x\,. \)
  10. La frazione \( \dfrac{rl + x_0}{rm + y_0} \) si dice migrante da \( \dfrac{x_0}{y_0} \) verso \(\dfrac{l}{m} \) di ordine \( r \ (\forall r \in \mathbb{N}_0); \) rimane evidente che vi è una biiezione fra la totalità di queste frazioni e l’insieme delle soluzioni della \( (12) \) a componenti positive.

Autore dell'articolo: Donato Saeli

Lascia un commento