Michel Talagrand, Premiul Abel 2024

Azi s-au decernat premiile Abel 2024. Pentru cine nu știe – în matematică este premiul cel mai apropiat (ca intenție) de premiile Nobel. Mult mai cunoscuta medalie Fields nu recompensează întreaga activitate a unui matematician, el acordându-se unor matematicieni cu vârsta de sub 40 de ani.

De ce m-am gândit să vă povestesc, pe blog, despre premiul decernat astăzi ? Poate pentru că povestea pe care doresc să v-o spun n-o veți auzi (cel puțin în limba română) de la altcineva: mă îndoiesc că sunt foarte mulți matematicieni în România care știu cu adevărat ce a realizat Michel Talagrand – incomunicabilitatea între diversele ramuri ale matematicii este destul de mare, dacă lucrezi, de exemplu, în algebră șansele să fi auzit despre noul medaliat, și să știi câte ceva despre rezultatele lui sunt destul de mici.

Vă puteți întreba – cum se face că un informatician (chiar dacă unul teoretic – subsemnatul) poate da un răspuns informat la întrebarea de mai sus ? Răspunsul e unul singur: m-am întâlnit cu rezultatele lui Talagrand acum destul de mulți ani, probabil pe la începutul anilor 2000, dacă nu chiar puțin înainte. Dețin în biblioteca personală un volum pe care l-a scris proaspătul medaliat. Prin urmare, chiar dacă n-am pretenția că știu tot ce a realizat, științific vorbind, proaspătul medaliat, mă pretind drept un interlocutor destul de informat.

Talagrand este probabilist, lucrând la intersecția cu analiza funcțională. Pe de altă parte rezultatele sale (cred) cele mai semnificative au relevanță atât pentru informatica teoretică (iată explicația pentru faptul că m-am intersectat cu articolele lui) cât și cu fizica sistemelor complexe (alt domeniu de care sunt intersat).

Inegalități izoperimetrice.

O primă clasă de contribuții ale lui Talagrand sunt legate de inegalități izoperimetrice. În cazul clasic genul acesta de rezultate are un caracter geometric – un exemplu: din toate corpurile convexe în de volum dat, corpul care are aria cea mai aria cea mai mică este (se demonstrează) sfera -dimensională. Rezultatul despre care vorbesc nu este cel de care s-a ocupat Talagrand: wikipedia atribuie acestei probleme o istorie îndelungată care începe (cu problema lui Dido) încă din antichitate.

Ca să ajung la rezultatul matematicianului francez trebuie să aduc în discuție un transfer „magic” de intuiții și rezultate, de tipul celor care se întâmplă nu atât de rar în matematică de la un domeniu (în care rezultatele inițiale codifică o intuiție destul de evidentă) la un alt domeniu (aparent deloc asemănător celui inițial). În cazul de față este vorba de la transferul unor rezultate care țin de geometrie și matematici continue către discret – grafuri și funcții booleene.

În cazul de față transferul s-a efectuat de la geometria spețiilor $\latex \mathbb{R}^n$ (spații Banach, mai general) către teoria probabilităților. Puteți citi, dacă doriți, despre inegalitatea lui Talagrand – însă pagina respectivă oferă puține intuiții și mă îndoiesc (cu excepția cazului în care lucrați în domeniu) că inegalitatea respectivă o să vă spună prea multe.

Ea este o așa-numitâ inegalitate de concentrare. Genul acesta de rezultate spune că probabilitatea ca un eveniment să devieze în mod sistematic de la comportamentul său tipic este mică. Un exemplu intuitiv de fenomen de concentrare: dacă arunc o monedă fair de 100 de ori mă aștept să obțin cap de aproximativ 50 de ori, iar probabilitatea ca să obțin cap de cel puțin 80 de ori este exponențial de mică.

Rezultatul de mai sus vorbea de concentrarea unei variabile aleatoare în jurul mediei. Rezultatele de genul acesta se aplică frecvent în combinatorică – prin inegalități de tipul inegalității Chernoff-Hoeffding. Inegalitatea lui Talagrand reprezintă o unealtă mai sofisticată, și care dă uneori rezultate în cazuri în care alte inegalități nu sunt aplicabile. Un exemplu este problema longest increasing subsequence, o problemă care se studiază în cursul de anul întâi de algoritmică, ca aplicație la programarea dinamică. Când $\latex \sigma$ reprezintă o permutare de elemente aleasă uniform la întâmplare este cunoscut faptul că

. Inegalitatea lui Talagrand ne spune cât de aproape este de . O referință încă foarte bună pentru acest tip de rezultate este cartea aceasta:

De la inegalități izoperimetrice la funcții booleene și tranziții de fază.

Inegalitățile de tip Talagrand se aplică în teoria funcțiilor booleene. Din nou, e destul de greu să ofer intuiții foarte bune, dar o să încerc.

Să considerăm o alegere în care persoane aleg una din două alternative (să zicem Biden versus Trump). Evident, putem face asta folosind votul majoritar. Dar nu e nici pe departe singura metodă – de exemplu majoritatea simplă nu este metoda folosită în sistemul din Statele Unite, care folosesc o regulă mai complicată, bazată pe electori, câștigătorul majorității într-un stat adjudecându-și de cele mai multe ori (dar nu întotdeauna !) toți electorii aceluiași stat.

Să ne punem următoarea întrebare intuitivă: fiind date două sisteme de vot diferite, care dintre metode îi dă unui alegător ales la întâmplare o influență mai mare ? Evident, pentru a răspunde la o astfel de întrebare trebuie să măsurăm cumva influența unui alegător asupra rezultatului unei alegeri. Ei, există o astfel de măsură, și ea formalizează o noțiune destul de intuitivă – influența unui alegător asupra unei alegeri este probabilitatea ca votul dat de acel alegător să fie decisiv. Domeniu care se ocupă cu așa ceva se numește analiza Fourier a funcțiilor booleene, o bună introducere – pentru matematicieni – găsindu-se în volumul de mai jos:

Nu e foarte intuitiv, dar problema de a găsi o funcție booleană al cărui „volum” (probabilitatea ca ) este constant, iar suma influențelor celor biți de input asupra funcției să fie minimă este o analogă discretă a problemei izoperimetrice de care am vorbit mai înainte – de unde faptul că inegalitatea lui Talagrand este relevantă pentru analiza funcțiilor booleene.

Și este relevantă într-un mod dramatic: prin astfel de metode se poate analiza tranziția de fază în probleme de optimizare combinatorială. De exemplu, faptul că problema satisfiabilității are o tranziție de fază (în engleză: sharp threshold) se arată cu mijloace de analiza funcțiilor booleene – arătând că problemele care nu au o astfel de tranziție de fază depind de un număr constant de biți și (pe urmă) faptul că SAT nu este o asfel de problemă.

Deloc surprinzător, de numele lui Michel Talagrand se leagă unele rezultate de început din acest domeniu.

Analiza modelelor de tip spin-glass.

Am intenționat să scriu la momentul respectiv despre premiul Nobel pentru fizică pe care l-a primit Giorgio Parisi pentru analiza modelelor de tip spin-glass (draftul articolului respectiv este încă prezent în lista de mesaje neterminate pe care le-am scris pentru acest blog). Pe scurt:

• metodele lui Parisi sunt revoluționare, ele aplicându-se și unor modele „fizice” (amestecuri de materiale magnetice cu impurități) cât și unor probleme din informatica teoretică.
• pe de altă parte matematica folosită de Parisi și alți fizicieni pentru analiza acestor modele este una complet neriguroasă – pentru matematicianul profesionist felul în care folosesc fizicienii matematica în acest domeniu având accente care pe alocuri amintesc de magie neagră și voodoo – lucruri complet neriguroase, care nu ar avea motive să meargă, și care de multe ori merg, cu rezultate (uneori) șocante.

Michel Talagrand și-a asumat ingrata sarcină de a face ordine în acest domeniu, punând matematica sistemelor de tip spin glass pe baze solide/riguroase (matematic vorbind). Mai multe din cărțile pe care le-a scris din anul 2000 încoace (inclusiv una care se află în biblioteca mea) sunt dedicate acestei probleme.

Nu pot pretinde că sunt la curent cu progresul demersului, interesele mele de cercetare s-au depărtat în ultimii 10-15 ani de acest domeniu. Probabil că, totuși, Michel Talagrand rămâne specialistul mondial numărul 1 în acest domeniu.

Aici se încheie scurta mea dizertație pe seama rezultatelor celui mai nou medaliat Abel – sper că ați aflat lucruri interesante din rândurile mele de mai sus.