ENTRADAS

11 ago 2017

LA SUCESIÓN DE FAREY

John Farey y su ingeniosa construcción.

¿Cuántas fracciones (no negativas) diferentes existen de forma que el denominador sea menor que 100 y el numerador menor o igual que el denominador? Así, de esta guisa, apareció este problema en una publicación anual en Londom From en 1747.

Diagrama del término noveno de la sucesión de Farey. Wikipedia

Diagrama del término noveno de la sucesión de Farey. Wikipedia

Charles Haros en 1812 fue el primer matemático en formular la sucesión que se puede construir con las condiciones del problema anterior. Esta sucesión se denomina sucesión de Farey en honor al geólogo y escritor inglés John Farey (1766-1826)  quien fue el primero en publicarlo en la revista “Bulletin de la Societe Philomatique” en 1816. Esta revista fue leída por el matemático Agustin Louis Cauchy (1789-1857) quien tras leerla atribuyó su descubrimiento a Farey.

Ni John Farey ni Cauchy quisieron en ningún momento privar de la fama a Haros pues no consta que conocieran su trabajo previo.

Para que nos hagamos una idea de la sucesión de Farey vamos a construir algunos términos de la misma.

Denotamos por F_n al n-ésimo término de la sucesión. Vamos a explicar las reglas de formación, y para que quede más claro, vamos a ir construyento F_5.

1.- Se construyen todas las posibles fracciones en las que numerador y denominador sean números entre 1 y n. En nuestro ejemplo F_5 consideraremos los números de 1 a 5. (Se incluye también el 0 en la secuencia).

Fracciones con numerador 0 (como son todas iguales sólo consideramos la primera) \frac{0}{1}

Fracciones con numerador 1:  \frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{4}, \frac{1}{5} .

Fracciones con numerador 2:  \frac{2}{1},\frac{2}{2},\frac{2}{3},\frac{2}{4}, \frac{2}{5} .

Fracciones con numerador 3:  \frac{3}{1},\frac{3}{2},\frac{3}{3},\frac{3}{4}, \frac{3}{5} .

Fracciones con numerador 4:  \frac{4}{1},\frac{4}{2},\frac{4}{3},\frac{4}{4}, \frac{4}{5} .

Fracciones con numerador 5:  \frac{5}{1},\frac{5}{2},\frac{5}{3},\frac{5}{4}, \frac{5}{5} .

2.- Se eliminan las fracciones impropias, es decir, aquellas cuyo numerador sea mayor que su denominador.

3.- Se simplifican todas las fracciones, y se eliminan las repeticiones.

En nuestro caso nos quedarían:

0,1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\frac{2}{3},\frac{2}{5},\frac{3}{4},\frac{3}{5},\frac{4}{5}

4.- Se ordena el resultado de menor a mayor.

En nuestro caso:

F_5=\{0,\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},1\}

Esta sucesión da respuesta al problema que planteamos inicialmente. Concretamente se trataría de ver cuantos términos tiene el término F_{99}  de la sucesión.

Si calculamos F_6 tenemos:

F_6=\{0,\frac{1}{6},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{5}{6},1 \}

Observemos que por la forma de construir la sucesión, se cumple que cada término contiene todos los elementos del término anterior. Es decir el término F_n  contiene todos los elementos del término F_{n-1}.

Ahora que ya conocemos la regla de formación de la sucesión, observemos ahora dos términos consecutivos (vecinos) de la sucesión de Farey del término F_5

F_5=\{0,\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},1\}

Por ejemplo fijémonos en los términos \frac{1}{4} y \frac{1}{3}. Si restamos ambos miembros se tiene:

\frac{1}{3}-\frac{1}{4}=\frac{1}{12}=\frac{1}{3\cdot 4}

Esto no es un hecho aislado, sino que si consideramos dos términos vecinos cualesquiera, \frac{a}{b} y \frac{c}{d} (\frac{a}{b}<\frac{c}{d}) de la sucesión de Farey, se tiene que:

\frac{c}{d}-\frac{a}{b}=\frac{1}{bd}

Por tanto si queremos dar respuesta al problema planteado inicialmente, sólo tenemos que calcular el término 99 de la sucesión de Farey. Pero para llegar a él primero tenemos que estudiar más a fondo esta curiosa sucesión.

Para ello vamos a definir la función \varphi de Euler:

\varphi (n)=Card\{k\in \mathbb{N}; k\leq n, MCD(k,n)=1\}

Es decir, para cada número natural n, se tiene que \varphi (n) es la cantidad de números primos relativos con n (tienen máximo común divisor con n la unidad) y menores o iguales que n.

Se puede observar que:

\varphi (1)=1  Ya que el único número menor o igual que 1 primo relativo con él es el propio 1.

\varphi (2)=1

\varphi (3)=2. Ya que 1 y 2 son números naturales primos relativos o coprimos con 3.

En general se puede observar que si p es un número primo, entonces \varphi (p)=p-1. Nuestro objetivo es deducir una fórmula para el cálculo de F_n. Para ello recordemos que F_n contiene los términos de F_{n-1}, por lo tanto:

F_n=F_{n-1}+l_n

Donde:

l_n estará formado por todas las fracciones con denominador n y numerador primo relativo con n. Dicho de otra forma, el cardinal de l_n será Card(l_n)=\varphi (n).

Por lo tanto se deduce que:

Card(F_n)=Card(F_{n-1})+\varphi (n)

Ahora si tenemos una relación directa entre la sucesión de Farey y la función \varphi de Euler.

Vamos a estudiar un poco más a fondo la función fi de Euler para poder calcular F_{99} que es nuestro objetivo.

Nóptese que si n=p^k con p número primo y k número natural, entonces:

\varphi (p^k)=(p-1)p^{k-1}

Vamos a probar esta igualdad utilizando el método de inducción sobre el número natural k.

Sea p un número primo fijo pero arbitrario, entonces:

1.- Etapa base: k=1

En este caso tenemos que probar que \varphi (p^1)=(p-1)p^{1-1}

Pero esto es obvio porque \varphi (p^1)=\varphi (p)=p-1=(p-1)p^0=(p-1)p^{1-1}

2.- Etapa de inducción. Supongamos cierta la igualdad para un determinado número natural k, y la probaremos para k+1.

Supongamos por tanto que se cumple \varphi (p^k)=(p-1)p^{k-1}

Y probaremos que \varphi (p^{k+1})=(p-1)p^{k}.

Observemos que:

(p-1)p^k=((p-1)p^{k-1})p=\varphi (p^k)p

Por otro lado \varphi (p^k) es la cantidad de números primos relativos con p^k por lo que al multiplicarla por p, obtenemos la cantidad de números primos relativos con p^{k+1}, es decir:

\varphi (p^{k})p=\varphi (p^{k+1})

De donde deducimos que:

\varphi (p^{k+1})=(p-1)p^k

Y por lo tanto queda demostrada la igualdad por el método de inducción.

La función \varphi de Euler cumple también la propiedad siguiente: Si m, n son números naturales primos relativos entre sí, entonces \varphi (mn)=\varphi (m)\varphi (n). Esta propiedad no será demostrada por no hacer más farragosa y extensa esta lectura pero puede consultarse en bibliografía.

Esta propiedad anterior, nos da pie a calcular la función \varphi de Euler de cualquier número entero, puesto que si n es un número entero cualquiera, entonces, puede descomponerse como producto de potencias de números primos de la forma:

n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}

Donde p_1,p_2,\cdot, p_r son números primos distintos y k_1,k_2,\cdots k_r son números naturales mayores o iguales que 1.

Entonces:

\varphi (n)=\varphi (p_1^{k_1}(p_2^{k_2})\cdots p_r^{k_r})=

=\varphi(p_1^{k_1})\varphi (p_2^{k_2})\cdots \varphi (p_r^{k_r})=

=(p_1-1)p_1^{k_1-1}(p_2-1)p_2^{k_2-1}\cdots (p_r-1)p_r^{k_r-1}=

=(1-\frac{1}{p_1})p_1^{k_1}(1-\frac{1}{p_2})p_2^{k_2}\cdots (1-\frac{1}{p_r})p_r^{k_r}=n\cdots \prod_{p|n}(1-\frac{1}{p})

Donde en la última igualdad hemos usado que n=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}.

Veamos un ejemplo sencillo de cálculo práctico:

\varphi (12)=\varphi (2^2\cdot 3)=12(1-\frac{1}{2})(1-\frac{1}{3})=12\cdot \frac{1}{2}\cdot \frac{2}{3}=4

Observamos, por lo tanto, que hay 4 primos relativos con 12 menores que él. Como 12 es un número relativamente bajo podemos calcular los primos relativos con 12 menores que él, éstos son: 1, 5, 7 y 11.

Con esta propiedad podemos abordar nuestro problema inicial, recordemos que queríamos calcular F_{99} , y para ello podemos hacer uso de:

Card(F_n)=Card(F_{n-1})+\varphi (n)

Tenemos que:

Card(F_n)=Card(F_{n-1})+\varphi(n)=Card(F_{n-1})+Card(F_{n-2})+\varphi (n-1)=

=\cdots Card(F_1)+\varphi (2)+\varphi (3)+\cdots +\varphi (n)

Como además se tiene que Card(F_1)=\varphi (1)=1, entonces sustituyendo en la expresión anterior llegamos a que:

Card(F_n)=\varphi (1)+\varphi (2)+\cdots +\varphi (n)=\sum_{k=1}^n \varphi (k)

Por lo tanto tenemos que la solución a nuestro problema será:

\varphi (99)=\sum_{k=1}^{99}\varphi (k)=1+1+2+2+4+2+\cdots +42+60=3004

Con esto podemos concluir que existen 3004 fracciones (no negativas) diferentes de forma que el denominador sea menor que 100 y el numerador menor o igual que el denominador.

AUTOR: FRANCISCO MORANTE QUIRANTES @fdetsocial

Más entradas del autor para FdeT

Si quieres participar en el blog como colaborador en alguna de las secciones, envíanos un mail a info@fdet.es 

Grupo FdeT

Compartir:
Facebooktwittergoogle_pluslinkedin

Leave a Reply

A %d blogueros les gusta esto: