L'Accademia norvegese di Scienze e Lettere ha deciso di assegnare il Abel Prize per il 2012 a Endre Szemeredi, dell'Istituto di Matematica Alfred Renyi dell'Università di Budapest e del Dipartimento di Informatica della Rutgers University (New Jersey, USA). Un premio di un milione di dollari, e più che meritato, come recita la motivazione, "per i suoi contributi fondamentali alla matematica discreta e alla informatica teorica, nonché per l'impatto profondo e duraturo di questi contributi sulla teoria additiva dei numeri e della teoria ergodica".
La matematica discreta è una disciplina che studia strutture come i grafi, le sequenze, le permutazioni e le configurazioni geometriche. La matematica di queste strutture costituisce la base dell’informatica teorica e della teoria dell’informazione. Le reti di comunicazione come Internet possono ad esempio essere descritte e analizzate utilizzando strumenti della teoria dei grafi, mentre le intuizioni della matematica discreta hanno importanza decisiva nello sviluppo di algoritmi computazionali efficienti. I problemi di natura combinatoria delle strutture discrete si ritrovano anche in molte aree della matematica pura, tra cui la teoria dei numeri, la teoria della probabilità, l’algebra, la geometria e l’analisi.
Endre Szemerédi ha rivoluzionato la matematica discreta introducendo tecniche ingegnose e innovative e risolvendo molti problemi fondamentali. Grazie alla sua opera la matematica combinatoria ha assunto un ruolo di primo piano, rivelando i suoi stretti legami con la teoria addittiva dei numeri, la teoria ergodica, l’informatica teorica e la geometria d’incidenza.
Nel 1975, Endre Szemerédi suscitò per la prima volta l’attenzione della comunità matematica risolvendo la famosa congettura di Erdős–Turán, in cui dimostrò che ogni insieme di numeri naturali con densità superiore positiva contiene progressioni aritmetiche arbitrariamente lunghe. Tale evento costituì una vera e propria sorpresa, perché la sola dimostrazione dell’esistenza di progressioni aritmetiche di lunghezza 3 e 4 aveva richiesto grandi sforzi a Klaus Roth e allo stesso Szemerédi.
Tuttavia, il futuro riservava una sorpresa ancora maggiore. La dimostrazione di Szemerédi fu un capolavoro di ragionamento combinatorio di cui si colse immediatamente l’eccezionale profondità e importanza. Un passaggio cruciale della dimostrazione, ora nota come il Lemma di regolarità di Szemerédi, sta nella classificazione strutturale dei grafi di grandi dimensioni. Nel corso del tempo, questo lemma è diventato un caposaldo della teoria dei grafi e dell’informatica teorica, portando alla risoluzione di importanti problemi di property-testing e dando origine alla teoria dei limiti dei grafi.
Le sorprese, comunque, non erano finite. Oltre all’impatto sulla matematica discreta e sulla teoria additiva dei numeri, il teorema di Szemerédi spinse Hillel Furstenberg a esplorare nuove direzioni della teoria ergodica. Egli diede una nuova dimostrazione del teorema di Szemerédi con il Teorema della ricorrenza multipla nella teoria ergodica, stabilendo inaspettatamente un nesso tra problemi di matematica discreta e la teoria dei sistemi dinamici. Questo rapporto fondamentale fu foriero di molti altri sviluppi, come ad esempio il teorema di Green-Tao, in cui si afferma che la sequenza di numeri primi contiene progressioni aritmetiche arbitrariamente lunghe.
Szemerédi ha dato molti altri importanti contributi che hanno influenzato profondamente sia la matematica discreta, sia l’informatica teorica. Nell’ambito della matematica discreta possiamo citare il teorema di Szemerédi–Trotter, il metodo semi-aleatorio di Ajtai–Komlós–Szemerédi, il teorema del prodotto della somma di Erdős–Szemerédi e il lemma di Balog–Szemerédi–Gowers. Nell’ambito dell’informatica teorica citiamo invece la rete di ordinamento di Ajtai-Komlos- Szemerédi, lo schema di hashing di Fredman–Komlós–Szemerédi, e il teorema di Paul–Pippenger– Szemerédi–Trotter in base al quale il tempo lineare deterministico è distinto da quello non deterministisco.
L’approccio di Szemerédi alla matematica s’inscrive nella lunga tradizione ungherese della risoluzione dei problemi, tuttavia l’impatto teorico del suo lavoro è stato rivoluzionario.
Per approfondimenti: http://www.abelprize.no/
