Constructor de Trenes

Una trena és una cosa que qualsevol sap fer amb els dits i que, tanmateix, amaga un dels grups més estudiats de la matemàtica moderna: infinit, no commutatiu, definit per només dues regles, i amb aplicacions que van des de la teoria de nusos fins als ordinadors quàntics. Aquí veurem d'on surten aquestes dues regles, per què decidir si dues trenes són iguals és un problema genuïnament difícil, i què està calculant de veritat el comparador de la càpsula.

1. Què és una trena, amb precisió

Imagina n fils penjant en paral·lel d'una barra horitzontal fins a una altra barra de sota. Els fils poden creuar-se entre ells pel camí, però hi ha tres regles: cap fil pot fer marxa enrere (sempre baixa), cap fil pot travessar-ne un altre, i els extrems queden fixats a les barres.

Dues trenes es consideren la mateixa si pots deformar-ne una fins a obtenir l'altra estirant i movent els fils per l'espai, sense tallar-los ni desenganxar-ne els extrems. Aquesta és la definició clau, i és intrínsecament topològica: no importa la forma exacta de les corbes, només l'entrellaçament.

Aquesta relació d'equivalència és el que fa que el tema sigui difícil. Dues trenes poden semblar completament diferents dibuixades i ser la mateixa; i dues que semblin gairebé idèntiques poden ser diferents. Cal, doncs, un mètode per decidir-ho que no depengui de mirar-se-les.

2. Els generadors: per què només fils veïns

Per convertir això en àlgebra, Emil Artin va proposar el 1925 descompondre qualsevol trena en peces mínimes. La peça mínima és un sol creuament entre dos fils veïns:

σᵢ = el fil de la posició i passa per sobre del de la posició i+1.
σᵢ⁻¹ = el mateix creuament, però per sota.

Una pregunta que sorgeix immediatament en fer servir la càpsula: per què no hi ha un generador que creui directament el fil 1 amb el 4? La resposta és a la vegada física i matemàtica. Físicament, el fil 1 no es pot teletransportar: per arribar al 4 ha de passar per damunt o per sota del 2 i del 3, i cadascun d'aquells passos és una decisió que canvia la trena. Matemàticament, si admetéssim un generador «σ₁,₄» seria ambigu: hi ha moltes maneres diferents d'arribar del fil 1 al 4, i totes donen trenes distintes.

Per això Artin es va limitar a creuaments de veïns. Qualsevol cosa més complexa s'ha de construir componen-la: per fer que el fil de la posició 1 viatgi fins a la 4 passant per sobre de tot, escrius σ₁σ₂σ₃ i obtens una diagonal neta que travessa tota la trena.

3. Les dues úniques regles

Amb els generadors i els seus inversos ja pots escriure qualsevol trena com una «paraula»: σ₁σ₂⁻¹σ₁σ₃. La pregunta és quan dues paraules diferents descriuen la mateixa trena. Sorprenentment, només calen dues regles (a més de la cancel·lació òbvia σᵢσᵢ⁻¹ = res).

Regla 1: els creuaments llunyans commuten

σᵢσⱼ = σⱼσᵢ quan |i−j| ≥ 2. La raó és evident quan la veus: si creues els fils 1 i 2, i després els fils 3 i 4, aquests dos creuaments no comparteixen cap fil. Són esdeveniments independents en zones separades de la trena, i podries fer-los simultàniament. L'ordre en què els escrius és una convenció de la notació, no un fet físic. La càpsula fa servir això: pots posar dos creuaments llunyans dins d'un mateix «instant», entre parèntesis.

Regla 2: la relació de trena (o de Yang–Baxter)

σᵢσᵢ₊₁σᵢ = σᵢ₊₁σᵢσᵢ₊₁. Aquesta és la interessant, i mereix una explicació amb noms. Anomenem A, B, C els tres fils que ocupen les posicions 1, 2, 3.

La conclusió física és la clau: en tots dos casos hi ha un fil (l'A) que passa per damunt dels altres dos com un pont, sense enganxar-s'hi. I a sota seu, els fils B i C es creuen una vegada. L'única diferència entre les dues expressions és a quina alçada passa aquest creuament de sota: abans o després que el pont hi passi per damunt. Com que el pont no toca res, pots fer lliscar aquell creuament amunt i avall lliurement sense que cap fil travessi cap altre. Per això són la mateixa trena.

4. Per què això és un grup, i quin

El conjunt de totes les trenes de n fils, amb l'operació «enganxa'n una sota l'altra», compleix les quatre condicions de la càpsula de Taules de Cayley: hi ha element neutre (els fils rectes), tot element té invers (fes la trena del revés, canviant sobre per sota), l'operació és associativa i és tancada. És el grup de trenes Bₙ.

Té dues propietats que el fan especialment interessant. Primera: és infinit (pots enrotllar dos fils tantes vegades com vulguis, i cada nombre de voltes dona una trena diferent). Segona: és no abelià per a n ≥ 3 — σ₁σ₂ ≠ σ₂σ₁, com pots comprovar amb el comparador de la càpsula. Un grup infinit i no abelià, definit per només dues relacions, és un objecte molt ric però molt difícil de manipular.

5. El problema de la paraula

La pregunta central de la càpsula —«són aquestes dues seqüències la mateixa trena?»— té un nom en àlgebra: el problema de la paraula. I no és una pregunta menor.

Per a grups en general, aquest problema és indecidible: Piotr Novikov (1955) i William Boone (1958) van demostrar, independentment, que existeixen grups amb una presentació finita per als quals no pot existir cap algorisme que decideixi si dues paraules són iguals. No és que no l'hàgim trobat: és que està demostrat que no n'hi ha cap.

El grup de trenes, en canvi, sí que té solució. Artin ja en va donar una el 1925, i Frank Garside en va desenvolupar una de molt més eficient el 1969. Que Bₙ estigui al costat bo de la frontera és part del motiu pel qual és tan estudiat: és prou complicat per ser interessant i prou dòcil per poder-hi calcular.

6. Els invariants ràpids, i on fallen

La càpsula calcula dos números que serveixen per descartar de pressa:

L'exponent net. Compta +1 per cada σᵢ i −1 per cada σᵢ⁻¹. Com que les dues relacions d'Artin conserven aquest recompte (a la regla 1 no es canvia res, i a la regla 2 hi ha tres generadors positius a cada costat), dues trenes iguals han de tenir el mateix exponent. Si difereixen, ja s'ha acabat.

La permutació. Oblida qui passa per sobre i qui per sota, i mira només on acaba cada fil. Això dona una permutació dels n fils, i defineix un homomorfisme de Bₙ cap al grup simètric Sₙ. També es conserva, i també serveix per descartar.

Però cap dels dos, ni els dos junts, no basten. I aquí hi ha un exemple que ho ensenya de manera contundent, i que pots reproduir tu mateix al comparador:

Compara-la amb la trena buida al comparador i veuràs que l'aplicació respon «no es pot determinar» en lloc d'afirmar que són iguals. Això no és un defecte de l'eina: és honestedat. Els invariants ràpids no han pogut descartar-ho, i la cerca acotada no ha trobat cap seqüència de relacions que les connecti —perquè no existeix. Un programa mal fet diria «iguals»; aquest diu el que sap i el que no.

7. Què fem a l'element interactiu

Mode Explora. Cada botó «Fils i–i+1» és, literalment, un generador: el primer clic el posa a σᵢ (sobre), el segon a σᵢ⁻¹ (sota), el tercer el torna a recte. Els parells veïns es desactiven sols quan compartirien un fil, perquè un instant simultani només té sentit amb creuaments independents. «Afegeix aquest instant» l'incorpora al dibuix, que creix cap avall; «Simplifica» cancel·la les parelles σᵢσᵢ⁻¹ adjacents; el comparador respon la pregunta d'igualtat raonant en veu alta —primer l'exponent, després la permutació, i només si totes dues coincideixen intenta reduir les paraules.

Mode Repte. Té quatre tipus de pregunta que cobreixen les operacions bàsiques del grup: Simplifica (troba una forma més curta de la mateixa trena), Troba l'invers (construeix w⁻¹, que és invertir l'ordre i canviar tots els signes), Veritat o fals (dues paraules donades són la mateixa trena?) i Troba la permutació (on acaba cada fil).

Fixa't que el pas 1 és imprescindible i no és obvi: sense aplicar la relació de trena, les cancel·lacions no apareixen. Aquesta és exactament la dificultat del problema de la paraula — a vegades cal allargar o reorganitzar una expressió abans de poder-la escurçar.

8. Aparicions fora de les matemàtiques

Teoria de nusos. Si uneixes cada extrem inferior amb el seu propi extrem superior, la trena es tanca i esdevé un nus o enllaç. El teorema d'Alexander (1923) diu que tot nus s'obté així. I el teorema de Markov diu exactament quan dues trenes donen el mateix nus. Junts converteixen la classificació de nusos en un problema sobre grups de trenes — i d'aquí en va sortir, el 1984, el polinomi de Jones, que li va valer a Vaughan Jones la medalla Fields.

Ordinadors quàntics topològics. És potser l'aplicació més espectacular. Certes quasipartícules en dues dimensions, els anyons, tenen la propietat que intercanviar-ne dues no torna l'estat a l'original: el transforma segons una representació del grup de trenes. La proposta de Microsoft i altres és fer servir això per computar: el programa és una trena, i les portes lògiques són creuaments. L'avantatge és que el resultat depèn només de la topologia de la trena, no de la trajectòria exacta, i per tant és intrínsecament resistent al soroll.

Física estadística. L'equació de Yang–Baxter —que és la nostra regla 2 en una altra forma— és la condició central dels models integrables de mecànica estadística. Va aparèixer independentment en aquell context abans que ningú notés que era la relació d'Artin.

Robòtica i planificació de moviments. Coordinar diversos robots que es mouen en un pla sense xocar és, formalment, construir una trena en l'espai-temps: cada robot és un fil i el temps és la direcció vertical. Els algorismes de planificació treballen amb aquest espai de configuracions.

Criptografia. Als anys 2000 es van proposar sistemes de clau pública basats en la dificultat del problema de conjugació al grup de trenes. La majoria han estat trencats, però la línia continua sent activa dins la «criptografia no commutativa».

9. Curiositats

B₂ és, senzillament, els nombres enters. Amb només dos fils no hi ha veïns llunyans ni relació de trena: l'únic que pots fer és enrotllar-los. Una trena queda determinada pel nombre de voltes, amb signe. Per tant B₂ ≅ ℤ. Tota la complexitat apareix de cop en passar a tres fils.

Cap trena té ordre finit. El grup de trenes és lliure de torsió: si repeteixes una trena no trivial les vegades que vulguis, mai no obtindràs els fils rectes. És molt diferent dels grups finits de la càpsula de Cayley, on tot element repetit prou vegades torna a la identitat.

Es va trigar 75 anys a saber si es podien escriure com a matrius. La pregunta de si Bₙ és «lineal» (representable fidelment per matrius) va estar oberta des d'Artin fins al 2001, quan Stephen Bigelow i Daan Krammer la van respondre afirmativament, de manera independent i gairebé simultània.

El mig gir fonamental. La trena Δ = σ₁σ₂σ₁ de tres fils fa exactament mitja volta a tot el feix, i inverteix l'ordre dels fils. El seu quadrat, Δ², és una volta sencera i té una propietat notable: commuta amb absolutament tot. És l'únic tipus d'element que ho fa, i genera el «centre» del grup. Aquesta és la peça sobre la qual Garside va construir el seu algorisme.

La trencadissa de trenar cabell. Una trena de tres flocs de les de tota la vida és, en notació d'Artin, la repetició de (σ₁σ₂⁻¹) — creuar alternadament per sobre i per sota. Que quedi «plana» i no s'enrotlli sobre si mateixa és perquè els exponents s'alternen i l'exponent net creix molt a poc a poc.

10. Connexió amb altres àrees

Cap a l'àlgebra, aquesta càpsula és la continuació natural de Taules de Cayley: allà els grups són finits i caben en una taula; aquí n'hi ha un d'infinit que no cap en cap taula i que només es pot descriure per generadors i relacions. És el salt de «llistar els elements» a «descriure les regles», que és com es treballa amb els grups de veritat.

Cap a la topologia, connecta directament amb Nusos i tricolorabilitat: pel teorema d'Alexander, tot nus és el tancament d'una trena, i el trèvol que allà acoloreixes és exactament el tancament de σ₁³. Els moviments de Reidemeister d'aquella càpsula són els parents geomètrics de les relacions d'Artin d'aquesta.

I hi ha un pont amb el Trencaclosques del 15 que val la pena notar: la projecció Bₙ → Sₙ que oblida sobre/sota és el mateix tipus d'homomorfisme que allà assigna un signe a cada permutació. En tots dos casos, oblidar informació de manera controlada produeix un invariant útil.