Blog d’en Cesc

Avui s’ha fallat (mai pitjor dit) per primera vegada el Premi Nacional de Còmic (estatal), equiparant els còmics, almenys en aquest aspecte, a altres arts, com ara la fotografia, la traducció o la investigació en matemàtiques. I ha estat per en Max, comiquer barceloní que ja fa anys que viu per aquí, per la seva obra d’enguany, les històries den Bardin el Surrealista i que ja va arrassar al Saló del Còmic de Barcelona d’enguany. I, tot i que aquest llibre precisament no és el que més m’agradat d’ell, estic molt content. Així demà als diaris s’en xerrarà, i per ventura alguns lectors que no compren habitualment tebeos s’en faran ganes i s’acostaran a qualque botiga especialitzada a demanar per ell. I alguns fins i tot s’hi poden enganxar!

Fa poc en Xavi demanava qui era el millor matemàtic del 2007. Tenc un candidat: n’A. Garrett Lisi. No, no n’havíeu sentit a parlar. El seu currículum és impresionant: a l’estiu surfeja a Hawaii, a l’hivern dóna classes de snowboard prop del Llac Tahoe, a Califòrnia. Feu una tesi en física teòrica fa alguns anys, però deixà el món acadèmic per un món molt més interessant, com veieu. I ara fa un parell de dies ha publicat un preprint a l’ArXiv on, emprant el que es pot considerar matemàtiques elementals, dóna una solució elegantíssima al problema de trobar la Teoria del Tot, que expliqui totes les partícules elementals, les quatre forces etc. Va, ningú no garanteix que sigui correcta, encara ha de passar la prova de predir observacions que puguin ser comprovades (ell diu que “la natura pot no estar d’acord amb la meva teoria”), però li he pegat una ullada i és molt enginyosa.

De fet, el seu treball es basa en una de les fites matemàtiques més importants d’enguany, la descripció completa de les representacions del grup de Lie E8. No és un teorema petit: 60Gb de relacions! Òbviament, no calculades a ma. Més detalls aquí.

Si us interessa l’article de Lisi, no us deixeu espantar per l’abstract, que us pot recordar lo del “Que púberes canéforas te ofrenden el acanto” den Rubén Darío. És àlgebra lineal (sobre una àlgebra, no sobre un cos, però elemental), una mica de teoria de grups i una mica de combinatòria.

Aquests dies estam discutint per aquí si proposam problemes amb premi (o per col·laborar), i en Xavi es demanava com fer-se ric donant conferències. Aquí vull posar un problema del qual poso la ma al foc que una bona solució ens faria famosos, sobretot si la solució és prou enginyosa i connectada a la vida, l’univers i tot el demés.

Es tracta d’explicar la successió 4, 8, 15, 16, 23, 42 que apareix de manera recurrent a la sèrie de tele Perdidos. Ei! sóm matemàtics, la nostra especialitat és trobar pautes i regularitats! Ara no en podrem trobar una de ben garrida aquí? La publicam en un preprint ben ampulós a l’ArXiv, i us promet que en dos dies surt als diaris. Us parla la veu de l’experiència.

Ja sé que explicar sis nombres no té cap misteri: basta donar un polinomi d’interpolació p tal que p(1)=4, p(2)=8,…, p(6)=42 i ja està. Jo deman una solució enginyosa, que enganxi (i engani) al públic i que tots els fans de Lost l’esmentin als seus webs i blocs.

Per exemple, a l’Enciclopèdia En Línia de les Successions Enteres hi he trobat aquesta solució. Sigui F(n) la successió de Flavi (partim amb la seqüència de tots els nombres naturals i llevam els parells; del resultat, llevam els nombres que ocupen les posicions múltiples de tres; dels que queden, llevam els nombres que ocupen les posicions múltiples de 4; dels que queden, llevam els nombres que ocupen posicions múltiples de 5; i així successivament: els nombres que queden al final, després de les infinites llevades de nombres, formen la successió de Flavi).
Ara, per a cada n, sigui A(n) el menor nombre tal que dues vegades el nombre de divisors de (A(n)-n)/3 és igual a F(n+1)-F(n). Resulta que, sí, ho heu endevinat, els sis primers termes d’aquesta successió A(n) són 4, 8, 15, 16, 23, 42 (i després venen 55, 200,…).

Enginyós? A mi no se m’hagués acudit mai, i això és la meva definició d’enginyós. Amb ganxo? De cap de les maneres. Li he intentat explicar a la meva dona i encara badalla.

Voleu una explicació una mica menys enginyosa però moooolt més senzilla i amb més ganxo? El ara famós polinomi de Shaw-Basho

Diguem (el polinomi aplicat a ) i, per a cada ,
(les diferències de la successió SB d’índex anterior).
Resulta que , , , , , i, oh meravella, ja és la successió constant 0!

No creieu que ho podem fer millor?

(Per cert, esper que a cap friki no se li hagi escapat que 42 és La Resposta a la Pregunta Definitiva de la Vida, l’Univers i Tot el Demés de La Guia de l’Autoestopista Galàctic.)

Hola
per emmarcar la pel·lícula Moebius que avui vespre passen en el cicle de cinema d’Art i Ciència, us deixo aquí un vincle a una traducció al castellà del conte original d’Armin J. Deutsch “A subway called Moebius”, en el qual la pel·lícula s’inspira i que pel meu gust és millor que aquella (encara que només sigui perquè el prota és algebrista, i no topòleg). Jo tenc l’original anglès, per si qualcú el vol llegir.

En una crítica d’un llibre sobre modelat matemàtic del càncer apareguda al Nature d’ahir, l’autor (Bob Weinberg, recercaire capdavanter en càncer i autor d’un llibre de text molt conegut sobre biologia del càncer) es demanava “Poden les fórmules algebraiques dir-nos més coses que el raonament (reasoning) sobre el comportament dels sistemes biològics complexos?” Em té capficat. La resposta és “No, perquè tanmateix les fórmules algebraiques no són res més que un mode de raonament, i per tant estrictament incloses dins d’aquest”? La resposta és “Sí, perquè les fórmules algebraiques centren i ajusten el raonament i permeten extreure’n les conclusions que d’altra manera podrien quedar amagades o fosques”? La resposta és “No, perquè els processos biològics són tan complexos que tanmateix no es poden capturar amb una fórmula”? La reposta és “Sí, perquè els processos biològics són tan complexos que si no s’ajuda de matemàtiques (i computació), el raonament no en pot capturar tota la complexitat” La resposta és “No, perquè els biòlges, que són els que saben de processos biològics, no entenen les fórmules algebraiques ni falta que els fa”?

Realment ben capficat, em té.

Acab de llegir que Zimbabwe devaluà la seva moneda un 1200% el passat mes de setembre (i no ho he llegit a qualsevol banda, sinó al Times online. Per ventura sigui més una notícia per al bloc den Pep Lluís, però és que justament avui estava sensible perquè ahir corregia un exercici de primer de biologia, i una vintena llarga (aproximadament una cinquena part de la clientela) m’havien posat que si una població decreix un 6% anual, en 20 anys minva un 120%.

Ah, i no cregueu que aquesta devaluació signifiqui que si abans un dòlar americà valia 250 dòlars zimbabwesos, ara quan compres un dólar americà a Zimbabwe te donen el dòlar i 2750 Z$. El que volia dir The Times (i tots els altres que donen aquesta notícia) és que el canvi Z$:US$ ha passat de 250:1 a 30000:1.

Com passa darrerament cada parell d’anys, el Nòbel d’Economia ha tornat a premiar una aplicació de les matemàtiques, en aquest cas la teoria de disseny de mecanismes, una mescla de probabiltats (com sempre), teoria de jocs (no podien faltar) i autòmats (ups, aquesta és nova). Fins i tot un dels guardonats, en Myerson, de la univ. de Chicago, és matemàtic de formació (els altres dos són economistes). Podeu trobar els detalls científics del seu treball a la nota de premsa científica lliurada pel comitè Nobel aquí.

I com passa cada cop que Nobel d’Economia i matemàtiques van plegats, em pega el corcó d’un dels meus fracassos més dolorosos. Poc després d’arribar a la UIB, devia ser el 1991, vaig participar amb un company de Barcelona en una competició que organitzava cada any la UPF sobre matemàtiques i economia. Es tractava en aquella ocasió de jugar a un cert joc de compra-venda (molt relacionat precisament amb el tema del Nobel d’enguany). Guanyava el que dissenyava l’algoritme que feia al seu propietari més ric. La cosa anava per eliminatòries, a cada ronda jugàvem tots contra tots i s’eliminaven els que guanyaven menys (o perdien més). Nosaltres hi aportàrem un algoritme bastant enginyós, amb una base matemàtica sòlida… Ens sentíem els reis del mambo. I férem el ridícul: els darrers de la primera ronda, i eliminats (gairebé amb potada al cul) a la primera.
Per cert que va guanyar un algoritme ben senzillet que emprava programació lineal i una mica de teoria de jocs.

Des de llavors el meu respecte per les aplicacions de les matemàtiques a l’economia, malgrat que per ventura el contingut matemàtic no sigui massa profund, és gairebé infinit.

Si a qualcú li interessa (per exemple, assistents que vulguin saber com hagués acabat si l’ordinador no se m’hagués rebel·lat), he penjat les transparències de la lliço inaugural d’avui a baix del tot de http://bioinfo.uib.es/~cesc/recerca/talks.html

La setmana passada vaig tornar del CMSB, un congrés de biologia
computacional de sistemes. Aquests congressos de BCS són ben curiosos, amb
gent de tot pelatge: informàtics, matemàtics, biòlegs, físics.

La BCS és l’ús de mètodes computacionals per extreure, modelar i
analitzar sistemes biològics complexos, com ara les xarxes
metabòliques (el conjunt de totes ls reaccions bioquímiques que tenen
lloc en una cèl.lula) o les xarxes tròfiques (a través de les quals
circula l’energia als ecosistemes, de presses a depredadors). Va ser
elevada als altars de l’ICM de Madrid com una de les àrees emergents d’aplicació
de les matemàtiques, i hi conviuen molts grups amb especialitats
completament diferents. Hi ha qui empra equacions diferencials
deterministes, qui empra equacions diferencials estocàstiques, qui
empra àlgebres de processos, qui empra autòmats (sistemes P, xarxes
de Petri,…) estocàstics o no, qui empra grafs senzillets. Hi ha grups
interessats en un sistema concret, hi ha grups interessats en
desenvolupar models que permetin especificar qualsevol sistema, hi ha
grups interessats en mesclar mètodes. Hi ha biòlegs que estan massa
arran de terra (literalment), matemàtics que estan massa pels núvols, informàtics
als que només els interessa el servidor web amb el programa. El
resultat és que cadascú només escolta als que xerren el seu mateix
llenguatge i tracten els mateixos problemes

Als congressos de BCS s’hi canvia el “Estudies o fas feina?” per
encetar converses per un “Tu que fas servir, models discrets o
continus?”. I si no t’agradava la resposta, és obligat un “I per
què fas servir xarxes de Petri (o π-càlcul, o EDPs estocàstiques) quan
és clar que és més adient fer servir EDPs estocàstiques (o π-càlcul, o
xarxes de Petri)?” L’altra gran pregunta era “I tu, has trobat
qualque biòleg que entengui (o li agradi) el que fas?” La vaig
sentir un parell de vegades, i la veritat és que, havent tractat amb
biòlegs aquests darrers anys, qualque moment m’imaginava els meus
estudiants davant d’una EDP estocàstica i m’esbutzava de riure.

Divergències a banda, la BCS és un lloc magnífic on aplicar les
nostres tècniques preferides a resoldre problemes molt seriosos, dels
que pot dependre trobar per exemple una cura pel càncer. El problema
serà si la solució és tan complicada que qui l’ha d’entendre s’espanta.

El nombre de Déu és el nombre mínim de moviments necessaris per
resoldre qualsevol instància del cub de Rubik, és a dir, per passar de
qualsevol configuració desordenada del cub de Rubik a la configuració
diguem-ne bàsica, on totes les cares tenen un color (per moviment
entenem un quart de volta o mitja volta d’una cara del cub). Li diuen el
nombre de Déu, perquè se suposa que Déu empraria el menor nombre
possible de moviments per resoldre el cub de Rubik.

Es coneixen configuracions que necessiten 20 moviments per resoldre-les
(és a dir, que no hi ha manera de resoldre-les amb 19 o menys), i la
conjectura és que el nombre de Déu és ‘vint-i-un parell’.

Aquest estiu, Gene Cooperman i un estudiant de doctorat, Dan Kunkle, en un treball presentat a l’ISSAC’07, han baixat la fita superior per a aquest
nombre de Déu a 26. Podeu trobar l’article original a la pàgina web que en
Kunkle ha muntat sobre el tema, i on trobareu a més un recull d’enllaços a les notícies que s’han publicat sobre aquest treball.

La demostració ha consistit essencialment a comprovar que en el graf de amb nodes totes les possibles configuració (i n’hi ha més de ) i arestes representant els moviments que passen d’una configuració a l’altre, tot node pot connectar-se a la configuració bàsica per un camí de 26 o menys arestes. Sí, és una demostració ‘amb ordinador’, tipus la teorema dels quatre colors o de la conjectura de Kepler, però com en aquests casos, no consisteix en una cerca exhaustiva de tots els camins possibles, que seria impossible atesa la magnitud de la tragèdia, sinó que la dueixen mitjançant una sèrie d’astúcies molt interessants, i molt matemàtiques: els cal primer demostrar teoremes de teoria de grups, de teoria de grafs, d’algorítmica en paral·lel, i fins i tot sobre gestió eficient de memòria. Així i tot, ha costat més de 800 hores de CPU.

Va’t aquí un problema ben curiós: trobar el nombre de Déu. Si més no, té un nom ideal per demanar subvencions.
És un problema rellevant? No ho crec, o, dit d’una altra manera més política, tant com la conjectura de Kepler.
Ara, és important aquest treball concret? Crec que sí. És clar que davallar la
fita superior del nombre de Déu és anecdòtic fins i tot per als
aficionats al cub de Rubik (de fet, encara ningú no ha trobat cap
configuració que no es pugui resoldre amb 20 moviments, prou enfora de
26). Però la gestió de grafs grans amb milions o fins i tot bilions
de nodes és un problema cada dia més rellevant: per esmentar-ne un
exemple que m’és proper (i que és el que m’ha fet llegir aquest
article, a mem si podia aprofitar qualque idea), les xarxes de
reaccions i interaccions bioquímiques que es produeixen als éssers
vius. Moltes qüestions sobre aquests grafs s’han de resoldre amb una
combinació de teoremes matemàtics (que dirigeixen, fiten fan més
eficient, … l’anàlisi del graf) i de càlculs massius
amb ordinadors el més memoriuts i potents possible.

En tot cas, per als matemàtics més purs, sempre queda el problema
bàsic: podríem trobar el nombre de Déu amb una demostració que no
involucràs càlculs massius? Qui ho sap. Però per ventura, si us voleu fer famosos, primer us convindria provar amb una demostració ‘lliure d’ordinador’ del teorema dels quatre colors.