Paul Erdős, una vita attraversando i problemi

Perché è importante

Paul Erdős ha fatto della domanda matematica un punto d’incontro. Un problema sui numeri primi poteva condurlo alla combinatoria; una domanda sui grafi diventava un’occasione per usare la probabilità. Il filo conduttore era cercare un ragionamento capace di spiegare un fenomeno, oltre a stabilire che fosse vero.

Una delle sue eredità più feconde è il metodo probabilistico: scegliere idealmente un oggetto a caso e dimostrare che ha una probabilità positiva di possedere la proprietà desiderata. Se la probabilità è positiva, almeno un oggetto con quella proprietà deve esistere. Il caso diventa così uno strumento per raggiungere una conclusione certa.

La motivazione del Premio Wolf riconosce insieme l’ampiezza dei suoi contributi e la capacità di stimolare matematici in tutto il mondo. È un buon ritratto della sua influenza: risultati, metodi e nuove domande da condividere.

La vita

Erdős nasce a Budapest nel 1913, in una famiglia ebraica. Entrambi i genitori insegnano matematica. Nel 1934 consegue il dottorato e si trasferisce a Manchester con una borsa di ricerca, mentre le restrizioni antiebraiche rendono sempre più difficile il futuro in Ungheria.

Nel 1938 raggiunge gli Stati Uniti. La guerra separa la sua vita scientifica dalla famiglia rimasta in Europa. Negli anni successivi prende forma il suo modo di lavorare itinerante: visite a università e colleghi, discussioni, articoli scritti insieme, nuovi problemi da portare alla tappa successiva.

Non si lega stabilmente a una sola sede accademica. La rete delle persone con cui lavora diventa anche la geografia della sua ricerca. Muore a Varsavia il 20 settembre 1996. La biografia di MacTutor ricostruisce questo percorso, intrecciando vicende personali e lavoro matematico.

Le idee che hanno cambiato la matematica

1. I numeri primi e le dimostrazioni elementari

Da giovane Erdős trova una dimostrazione elementare del postulato di Bertrand: per ogni intero n maggiore di 1 esiste un primo p strettamente compreso fra n e 2n. Il risultato era già noto; la novità stava nella dimostrazione. “Elementare” indica qui gli strumenti utilizzati, non una garanzia di facilità.

Per n = 10, per esempio, possiamo scegliere 11, 13, 17 o 19. Ma controllare alcuni intervalli non risolve il problema: la dimostrazione deve funzionare per ogni n. Questo passaggio dagli esempi alla necessità è il cuore della teoria dei numeri.

2. Dimostrare l’esistenza attraverso il caso

Supponiamo di voler costruire una rete con caratteristiche molto particolari. Cercarla provando una configurazione dopo l’altra può essere difficile. Il metodo probabilistico cambia prospettiva: considera tutte le configurazioni attraverso un esperimento casuale e stima quante possano fallire.

Se la probabilità del fallimento è minore di 1, il successo è possibile. La dimostrazione può essere rigorosa senza consegnare immediatamente un esempio concreto. Come spiega Noga Alon nel suo saggio sul ragionamento probabilistico di Erdős, questo approccio ha avuto applicazioni profonde in combinatoria, grafi e teoria additiva dei numeri.

3. L’ordine inevitabile nei grafi

Un grafo rappresenta oggetti come punti e relazioni come collegamenti. Possiamo allora domandarci quali configurazioni diventino inevitabili quando aumentano i punti, oppure quanti collegamenti si possano inserire evitando una certa figura.

Nella teoria di Ramsey si cerca una regolarità che sopravvive a qualunque assegnazione di colori. Il problema delle sei persone a una festa ne offre un primo assaggio. Erdős contribuì a trasformare queste domande in un vasto territorio di ricerca, nel quale dimostrare che un oggetto esiste può essere molto più semplice che costruirlo esplicitamente.

La formula o il teorema simbolo

Un piccolo esempio mostra il metodo al lavoro. Consideriamo un grafo finito, senza cappi, con m collegamenti. Possiamo dividere i suoi punti in due gruppi in modo che almeno metà dei collegamenti passi da un gruppo all’altro:

esiste una divisione con almeno m/2 collegamenti fra i due gruppi

Mettiamo ogni punto in uno dei due gruppi lanciando una moneta equa, indipendentemente dagli altri punti. Per ogni collegamento ci sono quattro assegnazioni equiprobabili dei suoi estremi: due lo fanno attraversare da un gruppo all’altro. La probabilità è quindi 1/2.

E[X] = m · 1/2 = m/2

X conta i collegamenti fra gruppi diversi. Per linearità del valore atteso, la sua media è m/2: non serve che i singoli collegamenti siano indipendenti. Almeno una divisione raggiunge o supera la media, altrimenti anche la media sarebbe più piccola. È un esempio standard del metodo, illustrato anche nelle note di James Aspnes a Yale, non un risultato da attribuire esclusivamente a Erdős.

Un problema raccontato

Cinque laboratori devono essere distribuiti in due gruppi di lavoro. Ognuno collabora con tutti gli altri: i rapporti sono dieci. Vogliamo lasciare il maggior numero possibile di collaborazioni fra gruppi diversi, per favorire lo scambio.

Il ragionamento probabilistico garantisce subito almeno cinque rapporti fra i gruppi. In questo esempio possiamo fare meglio: con due laboratori da una parte e tre dall’altra, ogni laboratorio del primo gruppo mantiene tre rapporti esterni. Il totale è 2 × 3 = 6.

È anche il massimo. Se il primo gruppo contiene k laboratori, l’altro ne contiene 5 − k e i rapporti esterni sono k(5 − k): per k da 0 a 5 i valori sono 0, 4, 6, 6, 4, 0.

L’esempio distingue una garanzia generale dal risultato ottimo in un caso concreto. La dimostrazione probabilistica ci dà una soglia valida per qualunque rete; conoscere meglio la rete può consentire di superarla. Inoltre una singola estrazione casuale non è obbligata a raggiungere la soglia: la certezza riguarda l’esistenza di una buona divisione.

Curiosità

• Il numero di Erdős vale 0 per lui, 1 per un suo coautore, 2 per chi ha collaborato con un suo coautore senza aver scritto con lui: si sceglie sempre la catena più corta.
• Questo numero misura una distanza nella rete delle pubblicazioni condivise, non la qualità di un matematico né la difficoltà dei suoi risultati.
• La metafora di The Book immagina una raccolta delle dimostrazioni perfette. Aigner e Ziegler iniziarono a lavorare con Erdős al loro libro nel 1995.
• Il suo cognome contiene una ő, la o ungherese con doppio accento acuto, diversa dalla ö con dieresi.

Cosa leggere

Per conoscere la sua vita

Paul Hoffman, L’uomo che amava solo i numeri. Una biografia narrativa per incontrare la persona, il lavoro itinerante e il mondo dei suoi interlocutori.

Per entrare nelle dimostrazioni

Martin Aigner e Günter M. Ziegler, Proofs from THE BOOK. Una raccolta di ragionamenti eleganti, fra numeri, geometria e combinatoria. Il capitolo sul postulato di Bertrand permette di proseguire uno dei temi di questo articolo.

Fonti e approfondimenti

Oltre alle fonti collegate nel testo, l’Erdős Number Project, curato da Jerry Grossman, documenta le collaborazioni e spiega come si costruisce il relativo grafo. Le sue regole di definizione chiariscono quali pubblicazioni vengono conteggiate.

L’eredità

Erdős ha contribuito a rendere naturale una forma di ricerca che attraversa i confini fra discipline: formulare una domanda precisa, cercare un esempio, capire che cosa lo impedisce e chiedere aiuto a un metodo proveniente da un altro campo.

Il metodo probabilistico resta una lezione particolarmente fertile. Per dimostrare un fatto deterministico possiamo introdurre temporaneamente il caso. Alla fine la probabilità scompare dalla conclusione: rimane un oggetto che deve esistere, e spesso un nuovo problema, quello di trovarlo.

In una frase

Paul Erdős ha mostrato quanta matematica possa nascere da una buona domanda condivisa con la persona giusta.

DALLA MIA BIBLIOTECA

• Paul Hoffman — L’uomo che amava solo i numeri. La biografia per accompagnare il percorso umano.
• Martin Aigner e Günter M. Ziegler — Proofs from the Book. Il volume per passare dal racconto alle dimostrazioni.

Scopri gli altri articoli della serie “Grandi matematici”