Fraccions contínues

Construïm la idea des de zero: d'on surt la notació, per què el rectangle és exactament el mateix que l'algorisme, per què els convergents són òptims, i com tot això acaba resolent una equació que va tenir Europa encallada un segle.

1. Com s'escriu un número?

Estem tan acostumats a la notació decimal que oblidem que és una tria arbitrària. Escriure π = 3,14159… vol dir «3 unitats, 1 desena, 4 centèsimes…»: tot depèn de què hàgim decidit que és una desena, i això depèn de tenir deu dits. En base 2, els mateixos números tenen dígits completament diferents. La notació decimal, doncs, no ens diu res sobre el número; ens diu com es comporta el número respecte d'una base que hem escollit nosaltres.

I això té conseqüències incòmodes. En decimal, 1/3 = 0,333… és infinit i periòdic, mentre que 1/2 = 0,5 s'acaba de seguida. Però 1/3 i 1/2 són, aritmèticament, exactament la mateixa mena d'objecte: dues fraccions senzilles. La diferència entre elles no és matemàtica, és un accident de la base 10. Pitjor encara: mirant els decimals de 0,333… i els de 0,101001000100001… (que és irracional) no hi ha manera òbvia de distingir qui és racional i qui no.

Les fraccions contínues arreglen exactament això. No depenen de cap base. S'obtenen només amb dues operacions —agafar la part entera i fer la inversa— i el resultat és una espècie de «carnet d'identitat aritmètic» del número: la seva forma et diu immediatament si és racional, si és una arrel quadrada, o si és cap de les dues coses.

2. Construcció

El procediment és una recepta de dues instruccions que es repeteixen. Partim d'un número x:

(a) Agafa la part entera: a₀ = ⌊x⌋. El que sobra, x − a₀, és un número entre 0 i 1. (b) Si el que sobra és 0, has acabat. Si no, fes-ne la inversa —com que era menor que 1, la inversa és més gran que 1— i torna al pas (a) amb aquest número nou.

Cada volta produeix un enter aₙ. La llista d'aquests enters, escrita [a₀; a₁, a₂, …], és la fracció contínua de x. Vegem-ho amb un número concret.

Fixa't en els números que han anat apareixent com a residus: 93, 43, 7, 1. Si has vist mai l'algorisme d'Euclides per calcular el màxim comú divisor de 415 i 93, són exactament els mateixos. No s'hi assemblen: són el mateix càlcul. La fracció contínua d'un racional p/q no és res més que l'algorisme d'Euclides aplicat a p i q, apuntant els quocients en lloc de només el residu final. D'aquí surt un fet immediat i important: com que l'algorisme d'Euclides sempre acaba quan els números són enters, la fracció contínua d'un racional sempre és finita. I a l'inrevés: si s'acaba, el número era racional.

3. Exemple amb un rectangle

Ara ve la part que l'element interactiu d'aquesta càpsula fa visible. Agafa un rectangle de costats x i 1 (el llarg i el curt). Pregunta: quants quadrats de costat 1 hi caben, de manera sencera, dins d'aquest rectangle? La resposta és ⌊x⌋, que és exactament a₀. Retalla'ls. El que queda és un rectangle més petit, de costats 1 i x − a₀.

Aquest rectangle nou té el costat curt on abans hi havia el llarg. Si el gires perquè torni a estar «de cara», les seves proporcions són 1 : (x−a₀), o sigui, la proporció d'abans invertida. I què fa el pas (b) de la recepta? Exactament això: invertir. Per tant, retallar quadrats i girar el que queda és la versió geomètrica d'agafar la part entera i invertir. Cada terme de la fracció contínua és, literalment, «quants quadrats hi cabien en aquest pas».

4. Els convergents

Si tallem la torre de fraccions en un pis qualsevol, obtenim un número racional. Aquests talls es diuen convergents i s'escriuen pₙ/qₙ. No cal recalcular-los des de zero cada vegada: hi ha una recurrència que els genera un darrere l'altre.

$p_n=a_n{p}_{n-1}+p_{n-2}$   i   $q_n=a_n{q}_{n-1}+q_{n-2}$

Hi ha una identitat que surt d'aquesta recurrència i que ho explica gairebé tot: pₙqₙ₋₁ − pₙ₋₁qₙ = (−1)ⁿ⁻¹. Té dues lectures. La primera: com que el resultat és ±1, qualsevol divisor comú de pₙ i qₙ hauria de dividir 1, o sigui que els convergents ja surten sempre simplificats, sense haver de fer res. La segona és més potent: dividint-ho tot per qₙqₙ₋₁ s'obté que la distància entre dos convergents consecutius és exactament 1/(qₙqₙ₋₁). Com que els convergents van saltant alternativament per sota i per damunt del valor real, aquesta distància acota l'error: |x − pₙ/qₙ| < 1/(qₙqₙ₊₁).

Aquí hi ha la clau de tot. Aquesta cota depèn de qₙ₊₁, que és aproximadament aₙ₊₁·qₙ. Per tant: com més gran sigui el terme següent de la fracció contínua, millor és l'aproximació que acabes d'obtenir. Un terme gros vol dir que el residu que quedava era minúscul, i per tant que ja eres molt a prop. Això no és una observació estètica: és un criteri que es pot llegir directament de la llista de termes.

Amb un denominador de només tres xifres, 355/113 clava π fins a la sisena decimal. No és sort ni casualitat: és perquè al lloc número quatre de la fracció contínua de π hi ha un 292, un terme excepcionalment gran. Els matemàtics xinesos ja coneixien aquesta fracció al segle V (Zu Chongzhi), mil anys abans que existís la teoria que explica per què funciona tan bé.

5. Quan el procés no s'acaba

Ja hem vist que racional ⟺ finita. Què passa amb els irracionals? El cas més net és el nombre auri φ = (1+√5)/2, que compleix φ = 1 + 1/φ. Substituint aquesta igualtat dins d'ella mateixa una i altra vegada s'obté φ = [1; 1, 1, 1, 1, …], tot uns per sempre.

Segons el que hem dit al punt 4, tots els termes iguals a 1 —el valor més petit possible— vol dir que cap convergent és mai especialment bo. Per això φ es coneix com «el número més irracional que hi ha»: és el que pitjor s'aproxima per fraccions. I això té una conseqüència física real, no només aritmètica: les llavors de gira-sol i les fulles de moltes plantes se separen amb un angle relacionat amb φ precisament perquè és l'angle que mai es repeteix de manera aproximada, i això les fa empaquetar-se sense deixar forats.

El cas de les arrels quadrades és diferent i encara més notable. Per a qualsevol N que no sigui un quadrat perfecte, la fracció contínua de √N sempre acaba sent periòdica: un bloc de termes que es repeteix indefinidament (teorema de Lagrange, 1770). √2 = [1; 2, 2, 2, …], √3 = [1; 1, 2, 1, 2, …], √7 = [2; 1, 1, 1, 4, …]. La forma d'aquesta periodicitat és el que fa possible tot el que ve ara.

6. L'equació de Pell

L'equació x² − N y² = 1 sembla inofensiva. Si acceptem solucions reals qualssevol, n'hi ha infinites i no diuen res: formen una hipèrbola. El problema de veritat és exigir que x i y siguin nombres enters. Aquesta restricció ho canvia tot: de sobte hem de trobar punts de coordenades enteres sobre una corba, i no hi ha cap fórmula que els doni.

La connexió amb les fraccions contínues surt de reescriure l'equació. Si x² − Ny² = 1, dividint per y² tenim (x/y)² − N = 1/y², és a dir, (x/y)² és gairebé exactament N. Dit d'una altra manera: x/y ha de ser una aproximació racional excel·lent de √N. I pel teorema del punt 4, les aproximacions excel·lents no poden ser altra cosa que convergents. Per això la recepta funciona: es calculen els convergents de √N, un darrere l'altre, i es prova cadascun contra l'equació fins que un hi encaixa. La periodicitat garanteix que passarà.

7. Què fem a l'element interactiu

La càpsula té dues vistes que fan coses complementàries.

La vista «Retalla el rectangle» et fa executar l'algorisme a mà. Cada arrossegada és un pas: decideixes quants quadrats hi caben, ho confirmes, i el rectangle es transforma en el següent. Aquí no hi ha res calculat per tu excepte la comprovació: si dius que hi caben menys quadrats dels que hi caben de veritat, t'avisa. El requadre de sota et diu per què el rectangle nou té les mides que té, i a dalt es va escrivint la notació [a₀; a₁, …] i el convergent actual comparat amb el valor real, perquè vegis l'error encongir-se.

La vista «L'equació de Pell» fa el camí complet automàticament per a un N que triïs, i —això és el important— t'ensenya la feina, no només el resultat. La taula del final llista tots els convergents que s'han hagut de provar, amb el valor de x² − Ny² per a cadascun, i marca en verd el primer que dona 1. Així es veu que trobar la solució no és aplicar una fórmula, sinó una cerca ordenada que la teoria garanteix que acabarà.

8. Aparicions fora de les matemàtiques

Calendaris. L'any solar dura 365,2422 dies. Quants dies de traspàs cal afegir, i cada quant? És exactament la pregunta «quina és la millor aproximació racional de 0,2422?». La fracció contínua és [0; 4, 7, 1, 3, …] i els seus convergents són 1/4, 7/29, 8/33, 31/128. El primer, 1/4, és el calendari julià: un any de traspàs cada quatre. El tercer, 8/33, dona un error de només 0,0002 dies per any —millor que el nostre calendari gregorià, que fa servir 97/400 i s'equivoca en 0,0003. El calendari persa, dissenyat per Omar Khayyam al segle XI, usa precisament un cicle de 33 anys.

Engranatges. Christiaan Huygens va construir el 1680 un planetari mecànic i necessitava rodes dentades amb una proporció igual a la dels períodes orbitals dels planetes. No pots fer una roda amb 2,718 dents: has de trobar una fracció amb numerador i denominador enters, prou petits per cabre a la màquina i prou exactes perquè el planetari no es desviï. Huygens va fer servir fraccions contínues, i és un dels primers usos documentats de la tècnica per a un problema d'enginyeria.

Música. Per què l'octava es divideix en 12 semitons i no en 11 o 13? Una quinta justa és una proporció de freqüències de 3/2. Si volem que un cert nombre de semitons iguals doni una quinta, necessitem aproximar log₂(3/2) = 0,58496… per una fracció. La seva fracció contínua dona els convergents 1/2, 3/5, 7/12, 24/41, 31/53. El 7/12 diu: «7 semitons de 12 fan una quinta» —que és exactament el sistema temperat occidental. I el 31/53 explica per què alguns teòrics han proposat escales de 53 notes: és el següent salt de qualitat.

Criptografia. L'atac de Wiener (1990) contra RSA es basa en fraccions contínues: si la clau privada és massa petita en comparació amb el mòdul, apareix com un dels convergents d'una fracció construïda amb la clau pública, i es recupera en mil·lisegons. És la raó per la qual les implementacions serioses d'RSA imposen una mida mínima a la clau privada.

9. Curiositats

El número e té un patró perfecte; π no en té cap. La fracció contínua de e és [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, …]: després del 2 inicial, els termes van «1, 2k, 1» amb k creixent, per sempre. Euler ho va descobrir el 1737 i li va servir per demostrar que e és irracional (una fracció contínua infinita no pot ser racional). La de π, en canvi, comença [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, …] i ningú n'ha trobat mai cap patró. Que un dels dos números més famosos de la matemàtica tingui una estructura cristal·lina i l'altre sembli soroll continua sent un dels contrastos més desconcertants del tema.

Gairebé tots els números comparteixen una mateixa mitjana secreta. Agafa un número real a l'atzar, calcula'n la fracció contínua i fes la mitjana geomètrica dels seus termes. Aleksandr Khinchin va demostrar el 1935 que, per a gairebé tots els números reals, aquesta mitjana tendeix sempre al mateix valor: la constant de Khinchin, ≈ 2,6854520. No importa quin número hagis triat. El més divertit és que no se sap si constants tan corrents com π, e o √2 compleixen aquesta propietat que compleix «gairebé tothom»: numèricament sembla que sí, però no hi ha cap demostració.

Un de cada dos termes és un 1 (gairebé). Els termes d'una fracció contínua no surten a l'atzar uniforme: segueixen la distribució de Gauss–Kuzmin, segons la qual la probabilitat que un terme valgui k és log₂(1 + 1/(k²+2k)). Per a k = 1 això dona 41,5%. Gairebé la meitat dels termes de qualsevol número «típic» són uns.

La proporció d'argent. Si φ = [1;1,1,1,…] és la d'or, √2 − 1 = [0; 2, 2, 2, …] es coneix com la proporció d'argent, i governa el format de paper DIN A4: en tallar un A4 per la meitat en surt un A5 amb exactament les mateixes proporcions, cosa que només pot passar amb la proporció 1:√2.

Mil anys d'avantatge. El matemàtic i astrònom xinès Zu Chongzhi ja usava 355/113 per a π al segle V, i el seu valor va ser la millor aproximació coneguda al món durant prop de nou-cents anys. La teoria que explica per què aquesta fracció concreta és tan extraordinàriament bona no va arribar fins al segle XVIII, amb Euler i Lagrange.

10. Connexió amb altres àrees

Cap avall, cap a l'aritmètica elemental: ja hem vist que això és l'algorisme d'Euclides, el mateix que es fa servir per calcular màxims comuns divisors a l'escola. La fracció contínua només consisteix a apuntar la informació que l'algorisme d'Euclides llença.

Cap amunt, cap a l'àlgebra: el teorema de Lagrange que hem citat al punt 5 té un recíproc, degut a Euler, i junts diuen que una fracció contínua és periòdica exactament quan el número és una arrel d'una equació de segon grau amb coeficients enters (un «irracional quadràtic»). Això vol dir que la forma de la fracció contínua detecta el grau algebraic del número. La pregunta natural següent —hi ha un patró equivalent per a arrels cúbiques?— continua oberta avui; ningú sap si la fracció contínua de ∛2 té termes acotats o no.

I cap a un lloc inesperat, els sistemes dinàmics: el pas «agafa la part fraccionària i inverteix-la» és una funció, l'anomenada aplicació de Gauss, i estudiar les fraccions contínues equival a estudiar què fa aquesta funció quan s'itera. Des d'aquest punt de vista, els termes aₙ són una mena de trajectòria caòtica, i es pot demostrar (Khinchin) que per a gairebé tots els números reals la mitjana geomètrica dels termes tendeix a una constant universal, ≈ 2,685, independent del número que hagis triat. La mateixa lògica de «itera una regla simple i mira l'estructura que apareix» és la que trobaràs a les càpsules del Joc del caos i del Mètode de Newton.