secuencia de Farey

Al representar gráficamente los numeradores frente a los denominadores de una secuencia de Farey, se obtiene una forma como la que se muestra a la derecha, para F ₆ .

Al reflejar esta forma alrededor de los ejes diagonal y principal se genera el solsticio de Farey , que se muestra a continuación. El solsticio de Farey de orden n conecta los puntos de la cuadrícula enteros visibles desde el origen en el cuadrado de lado 2 n , centrado en el origen. Usando el teorema de Pick , el área del solsticio es 4( | F _n | − 1) , donde | F _n | es el número de fracciones en F _n .

La secuencia de Farey de orden n contiene todos los miembros de las secuencias de Farey de órdenes inferiores. En particular, F _n contiene todos los miembros de F _{n − 1} y también contiene una fracción adicional para cada número que es menor que n y coprimo con n . Así, F ₆ consta de F ₅ junto con las fracciones ⁠ 1 / 6 ⁠ y ⁠ 5 / 6 ⁠ .

El término central de una sucesión de Farey F _n es siempre 1 / 2 , para n > 1 . A partir de esto, podemos relacionar las longitudes de F _n y F _{n − 1} usando la función totiente de Euler φ ( n ) :

$${\displaystyle |F_{n}|=|F_{n-1}|+\varphi (n).}$$

Utilizando el hecho de que | F ₁ | = 2 , podemos derivar una expresión para la longitud de F _n : ^{[ 6 ]}

$${\displaystyle |F_{n}|=1+\sum _ {m=1}^{n}\varphi (m)=1+\Phi (n),}$$ donde Φ ( n ) es el totiente sumatorio .

También tenemos  : $${\displaystyle |F_{n}|={\frac {1}{2}}\left(3+\sum _{d=1}^{n}\mu (d)\left\lfloor {\tfrac {n}{d}}\right\rfloor ^{2}\right),}$$ y mediante una fórmula de inversión de Möbius  : $${\displaystyle |F_{n}|={\frac {1}{2}}(n+3)n-\sum _{d=2}^{n}|F_{\lfloor n/d\rfloor }|,}$$ donde μ ( d ) es la función de Möbius de la teoría de números , y ${\displaystyle \lfloor n/d\rfloor }$es la función de piso .

El comportamiento asintótico de | F _n | es  : $${\displaystyle |F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}.}$$

El número de fracciones de Farey con denominadores iguales a k en F _n viene dado por φ ( k ) cuando k ≤ n y cero en caso contrario. En cuanto a los numeradores, se puede definir la función${\displaystyle {\mathcal {N}}_{n}(h)}$que devuelve el número de fracciones de Farey con numeradores iguales a h en F _n . Esta función tiene algunas propiedades interesantes como ^{[ 7 ]}

${\displaystyle {\mathcal {N}}_{n}(1)=n}$,

${\displaystyle {\mathcal {N}}_{n}(p^{m})=\left\lceil (np^{m})\left(1-1/p\right)\right\rceil }$para cualquier número primo${\displaystyle p}$,

${\displaystyle {\mathcal {N}}_{n+mh}(h)={\mathcal {N}}_{n}(h)+m\varphi (h)}$ para cualquier entero m ≥ 0 ,

${\displaystyle {\mathcal {N}}_{n}(4h)={\mathcal {N}}_{n}(2h)-\varphi (2h).}$

En particular, la propiedad en la tercera línea anterior implica${\displaystyle {\mathcal {N}}_{mh}(h)=(m-1)\varphi (h)}$y, además,${\displaystyle {\mathcal {N}}_{2h}(h)=\varphi (h).}$Esto último significa que, para secuencias de Farey de orden par n , el número de fracciones con numeradores iguales a n / 2 es el mismo que el número de fracciones con denominadores iguales a n / 2 , es decir${\displaystyle {\mathcal {N}}_{n}(n/2)=\varphi (n/2)}$.

El índice${\displaystyle I_{n}(a_{k,n})=k}$de una fracción${\displaystyle a_{k,n}}$en la secuencia de Farey${\displaystyle F_{n}=\{a_{k,n}:k=0,1,\ldots ,m_{n}\}}$es simplemente la posición que${\displaystyle a_{k,n}}$ ocupa en la secuencia. Esto es de especial relevancia ya que se utiliza en una formulación alternativa de la hipótesis de Riemann , véase más adelante . A continuación se presentan varias propiedades útiles: $${\displaystyle {\begin{aligned}I_{n}(0/1)&=0,\\[6pt]I_{n}(1/n)&=1,\\[2pt]I_{n}(1/2)&={\frac {|F_{n}|-1}{2}},\\[2pt]I_{n}(1/1)&=|F_{n}|-1,\\[2pt]I_{n}(h/k)&=|F_{n}|-1-I_{n}\left({\frac {k-h}{k}}\right).\end{aligned}}}$$

El índice de ⁠ 1 / k ⁠ donde ⁠ n / i +1 ⁠ < k ≤ ⁠ n / i ⁠ y n es el mínimo común múltiplo de los primeros i números, n = mcm([2, i ]) , viene dado por: ^{[ 8 ]}$${\displaystyle I_{n}(1/k)=1+n\sum _{j=1}^{i}{\frac {\varphi (j)}{j}}-k\Phi (i).}$$

Se utilizó una expresión similar como aproximación de${\displaystyle I_{n}(x)}$para valores bajos de${\displaystyle x}$en el artículo clásico de F. Dress. ^{[ 9 ]} Una expresión general para${\displaystyle I_{n}(h/k)}$para cualquier fracción de Farey${\displaystyle h/k}$se da en. ^{[ 10 ]}

Las fracciones que son términos vecinos en cualquier secuencia de Farey se conocen como un par de Farey y tienen las siguientes propiedades.

Si a / b y c / d son vecinos en una secuencia de Farey , con a / b < c / d , entonces su diferencia c / d − a / b es igual a 1 / bd . Dado que$${\displaystyle {\frac {c}{d}}-{\frac {a}{b}}={\frac {bc-ad}{bd}},}$$

Esto equivale a decir que $${\displaystyle bc-ad=1.}$$

Así , ⁠ 1 / 3 ⁠ y ⁠ 2 / 5 ⁠ son vecinos en F ₅ , y su diferencia es ⁠ 1 / 15 ⁠ .

Lo contrario también es cierto. Si $${\displaystyle bc-ad=1}$$

para enteros positivos a , b , c , d con a < b y c < d , entonces a / b y c / d serán vecinos en la secuencia de Farey de orden max( b ,d ) .

Si ⁠ p / q ⁠ tiene vecinos ⁠ a / b ⁠ y ⁠ c / d ⁠ en alguna secuencia de Farey, con ⁠ a / b ⁠ < ⁠ p / q ⁠ < ⁠ c / d ⁠ , entonces ⁠ p / q ⁠ es la mediana de ⁠ a / b ⁠ y ⁠ c / d ⁠ – en otras palabras, $${\displaystyle {\frac {p}{q}}={\frac {a+c}{b+d}}.}$$

Esto se deduce fácilmente de la propiedad anterior, ya que si $${\displaystyle {\begin{aligned}&&bp-aq&=qc-pd=1,\\[4pt]\implies &&bp+pd&=qc+aq,\\[4pt]\implies &&p(b+d)&=q(a+c),\\\implies &&{\frac {p}{q}}&={\frac {a+c}{b+d}}.\end{aligned}}}$$

De ello se deduce que si ⁠ a / b ⁠ y ⁠ c / d ⁠ son vecinos en una secuencia de Farey, entonces el primer término que aparece entre ellos a medida que se incrementa el orden de la secuencia de Farey es $${\displaystyle {\frac {a+c}{b+d}},}$$

que aparece por primera vez en la secuencia de Farey de orden b + d .

Así, el primer término que aparece entre ⁠ 1 / 3 ⁠ y ⁠ 2 / 5 ⁠ es ⁠ 3 / 8 ⁠ , que aparece en F ₈ .

El número total de pares de vecinos de Farey en F _n es 2 | F _n | − 3 .

El árbol de Stern-Brocot es una estructura de datos que muestra cómo se construye la secuencia a partir de 0 ( = 0 / 1 ) y 1 ( = 1 / 1 ) , tomando medianas sucesivas. Sin embargo, tenga en cuenta que en el paso n de la construcción del árbol de Stern-Brocot se incluyen todas las medianas, no solo las que tienen denominador igual a n .

Las fracciones que aparecen como vecinas en una secuencia de Farey tienen expansiones de fracciones continuas estrechamente relacionadas . Cada fracción tiene dos expansiones de fracciones continuas : en una el término final es 1; en la otra el término final es mayor en 1. Si ⁠ p / q ⁠ , que aparece primero en la secuencia de Farey F _q , tiene las expansiones de fracciones continuas$${\displaystyle {\begin{aligned}&[0;\ a_{1},\ a_{2},\ \ldots ,\ a_{n-1},\ a_{n},\ 1]\\{}&[0;\ a_{1},\ a_{2},\ \ldots ,\ a_{n-1},\ a_{n}+1]\end{aligned}}}$$

Entonces , el vecino más cercano de p / q en Fq (que será su vecino con el denominador mayor) tiene una expansión en fracción _continua .$${\displaystyle [0;\ a_{1},\ a_{2},\ \ldots ,\ a_{n}]}$$

y su otro vecino tiene una expansión fraccionaria continua $${\displaystyle [0;\ a_{1},\ a_{2},\ \ldots ,\ a_{n-1}]}$$

Por ejemplo, ⁠ 3 / 8 ⁠ tiene las dos expansiones de fracciones continuas [0; 2, 1, 1, 1] y [0; 2, 1, 2] , y sus vecinos en F ₈ son ⁠ 2 / 5 ⁠ , que se puede expandir como [0; 2, 1, 1] ; y ⁠ 1 / 3 ⁠ , que se puede expandir como [0; 2, 1] .

El mcm se puede expresar como el producto de fracciones de Farey como $${\displaystyle {\text{lcm}}[1,2,...,N]=e^{\psi (N)}={\frac {1}{2}}\left(\prod _{r\in F_{N},0<r\leq 1/2}2\sin(\pi r)\right)^{2}}$$

donde ψ ( N ) es la segunda función de Chebyshev . ^{[ 12 ] [ 13 ]}

Dado que la función totiente de Euler está directamente conectada al mcd , también lo está el número de elementos en F _n , $${\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)=1+\sum \limits _{m=1}^{n}\sum \limits _{k=1}^{m}\gcd(k,m)\cos {2\pi {\frac {k}{m}}}.}$$

Para cualesquiera 3 fracciones de Farey ⁠ a / b ⁠ , ⁠ c / d ⁠ , ⁠ e / f ⁠ se cumple la siguiente identidad entre los mcd de los determinantes de matrices de 2×2 en valor absoluto : ^{[ 14 ] [ 8 ]}

$${\displaystyle \gcd \left({\begin{Vmatrix}a&c\\b&d\end{Vmatrix}},{\begin{Vmatrix}a&e\\b&f\end{Vmatrix}}\right)=\gcd \left({\begin{Vmatrix}a&c\\b&d\end{Vmatrix}},{\begin{Vmatrix}c&e\\d&f\end{Vmatrix}}\right)=\gcd \left({\begin{Vmatrix}a&e\\b&f\end{Vmatrix}},{\begin{Vmatrix}c&e\\d&f\end{Vmatrix}}\right)}$$

Las secuencias de Farey son muy útiles para encontrar aproximaciones racionales de números irracionales . ^{[ 15 ]} Por ejemplo, la construcción de Eliahou ^{[ 16 ]} de una cota inferior en la longitud de ciclos no triviales en el proceso 3 x +1 utiliza secuencias de Farey para calcular una expansión en fracción continua del número log ₂ (3) .

En sistemas físicos con fenómenos de resonancia, las secuencias de Farey proporcionan un método muy elegante y eficiente para calcular ubicaciones de resonancia en 1D ^{[ 17 ]} y 2D. ^{[ 18 ] [ 19 ]}

Las secuencias de Farey son prominentes en estudios de planificación de trayectorias de cualquier ángulo en cuadrículas de celdas cuadradas, por ejemplo, para caracterizar su complejidad computacional ^{[ 20 ]} u optimalidad. ^{[ 21 ]} La conexión puede considerarse en términos de trayectorias r -restringidas, es decir, trayectorias formadas por segmentos de línea que recorren como máximo r filas y como máximo r columnas de celdas. Sea Q el conjunto de vectores ( q , p ) tales que${\displaystyle 1\leq q\leq r}$,${\displaystyle 0\leq p\leq q}$y p , q son coprimos. Sea Q* el resultado de reflejar Q en la recta y = x . Sea${\displaystyle S=\{(\pm x,\pm y):(x,y)\in Q\cup Q*\}}$. Entonces, cualquier camino con restricción r puede describirse como una secuencia de vectores de S. Existe una biyección entre Q y la secuencia de Farey de orden r dada por ( q , p ) mapeando a${\displaystyle {\tfrac {p}{q}}}$.

Existe una conexión entre la secuencia de Farey y los círculos de Ford .

Para cada fracción ⁠ p / q ⁠ (en su mínima expresión) existe un círculo de Ford C [ p / q ] , que es el círculo con radio${\displaystyle {\tfrac {1}{2q^{2}}}}$y centro en${\displaystyle {\bigl (}{\tfrac {p}{q}},{\tfrac {1}{2q^{2}}}{\bigr )}.}$Dos círculos de Ford para fracciones diferentes son disjuntos o tangentes entre sí; dos círculos de Ford nunca se intersecan. Si 0 < p / q < 1 , entonces los círculos de Ford que son tangentes a C [ p / q ] son ​​precisamente los círculos de Ford para fracciones que son vecinas de p / q en alguna secuencia de Farey.

Por lo tanto, C [2/5] es tangente a C [1/2] , C [1/3] , C [3/7] , C [3/8] , etc.

Los círculos de Ford también aparecen en la junta apolínea (0,0,1,1) . La imagen a continuación ilustra esto junto con las líneas de resonancia de Farey. ^{[ 22 ]}

Las secuencias de Farey se utilizan en dos formulaciones equivalentes de la hipótesis de Riemann . Supongamos que los términos de F _n son${\displaystyle \{a_{k,n}:k=0,1,\ldots ,m_{n}\}.}$Definir${\displaystyle d_{k,n}=a_{k,n}-{\tfrac {k}{m_{n}}},}$en otras palabras${\displaystyle d_{k,n}}$es la diferencia entre el k -ésimo término de la n -ésima sucesión de Farey y el k -ésimo miembro de un conjunto del mismo número de puntos, distribuidos uniformemente en el intervalo unitario . En 1924, Jérôme Franel ^{[ 23 ]} demostró que la afirmación

$${\displaystyle \sum _{k=1}^{m_{n}}d_{k,n}^{2}=O(n^{r})\quad \forall r>-1}$$

es equivalente a la hipótesis de Riemann, y luego Edmund Landau ^{[ 24 ]} comentó (justo después del artículo de Franel) que la afirmación $${\displaystyle \sum _{k=1}^{m_{n}}|d_{k,n}|=O(n^{r})\quad \forall r>{\frac {1}{2}}}$$

También es equivalente a la hipótesis de Riemann.

La suma de todas las fracciones de Farey de orden n es la mitad del número de elementos: $${\displaystyle \sum _{r\in F_{n}}r={\frac {1}{2}}|F_{n}|.}$$

La suma de los denominadores en la secuencia de Farey es el doble de la suma de los numeradores y se relaciona con la función totiente de Euler:

$${\displaystyle \sum _{a/b\in F_{n}}b=2\sum _{a/b\in F_{n}}a=1+\sum _{i=1}^{n}i\varphi (i),}$$

que fue conjeturada por Harold L. Aaron en 1962 y demostrada por Jean A. Blake en 1966. ^{[ 25 ]} Una demostración en una sola línea de la conjetura de Harold L. Aaron es la siguiente. La suma de los numeradores es $${\displaystyle 1+\sum _{2\leq b\leq n}\ \sum _{(a,b)=1}a=1+\sum _{2\leq b\leq n}b{\frac {\varphi (b)}{2}}.}$$ La suma de los denominadores es $${\displaystyle 2+\sum _{2\leq b\leq n}\ \sum _{(a,b)=1}b=2+\sum _{2\leq b\leq n}b\varphi (b).}$$ El cociente de la primera suma por la segunda suma es ⁠ 1 / 2 ⁠ .

Sea b _j el denominador ordenado de F _n , entonces: ^{[ 26 ]}

$${\displaystyle \sum _{j=0}^{|F_{n}|-1}{\frac {b_{j}}{b_{j+1}}}={\frac {3|F_{n}|-4}{2}}}$$ y $${\displaystyle \sum _{j=0}^{|F_{n}|-1}{\frac {1}{b_{j+1}b_{j}}}=1.}$$

Dejar${\displaystyle {\tfrac {a_{j}}{b_{j}}}}$Sea la j -ésima fracción de Farey en F _n , entonces $${\displaystyle \sum _{j=1}^{|F_{n}|-1}(a_{j-1}b_{j+1}-a_{j+1}b_{j-1})=\sum _{j=1}^{|F_{n}|-1}{\begin{Vmatrix}a_{j-1}&a_{j+1}\\b_{j-1}&b_{j+1}\end{Vmatrix}}=3(|F_{n}|-1)-2n-1,}$$

lo cual se demuestra en ^{[ 27 ]} . Además, según esta referencia, el término dentro de la suma se puede expresar de muchas maneras diferentes: $${\displaystyle a_{j-1}b_{j+1}-a_{j+1}b_{j-1}={\frac {b_{j-1}+b_{j+1}}{b_{j}}}={\frac {a_{j-1}+a_{j+1}}{a_{j}}}=\left\lfloor {\frac {n+b_{j-1}}{b_{j}}}\right\rfloor ,}$$

obteniendo así muchas sumas diferentes sobre los elementos de Farey con el mismo resultado. Usando la simetría alrededor de 1/2 la suma anterior se puede limitar a la mitad de la secuencia como

$${\displaystyle \sum _{j=1}^{\left\lfloor {\frac {|F_{n}|}{2}}\right\rfloor }(a_{j-1}b_{j+1}-a_{j+1}b_{j-1})={\frac {3(|F_{n}|-1)}{2}}-n-\left\lceil {\frac {n}{2}}\right\rceil ,}$$

La función de Mertens se puede expresar como una suma sobre fracciones de Farey como $${\displaystyle M(n)=-1+\sum _{a\in {\mathcal {F}}_{n}}e^{2\pi ia}}$$ dónde${\displaystyle {\mathcal {F}}_{n}}$es la secuencia de Farey de orden n .

Esta fórmula se utiliza en la demostración del teorema de Franel-Landau . ^{[ 28 ]}