Di Evelyn Lamb

Considera questa sequenza di numeri: 5, 7, 9. Riesci a individuare lo schema? Eccone un altro con lo stesso schema: 15, 19, 23. Un altro: 232, 235, 238.

“Tre cose equidistanti”, dice Raghu Meka, informatico dell’UCLA. “Questo è probabilmente lo schema più semplice che si possa immaginare”.

Eppure, per quasi un secolo, i matematici nel campo della combinatoria si sono chiesti come sapere se una lista infinita di numeri contenga una tale sequenza, chiamata progressione aritmetica. In altre parole, c’è un modo per essere matematicamente certi che un insieme contenga una sequenza di tre o più numeri equidistanti, anche se non si sa molto su come sono stati selezionati i numeri nell’insieme o quale potrebbe essere la progressione?

I progressi sulla questione sono stati lenti, persino faticosi. Ma l’anno scorso, Meka e Zander Kelley, uno studente di dottorato in informatica presso l’Università dell’Illinois Urbana-Champaign, hanno sorpreso i matematici facendo un salto esponenziale. I ricercatori sono estranei alla combinatoria, che si occupa di contare le configurazioni di numeri, punti o altri oggetti matematici. E il duo non ha deciso di affrontare il mistero delle progressioni aritmetiche.

Kelley e Meka stavano invece studiando i giochi astratti nell’informatica. La coppia cercava uno strumento matematico che potesse aiutarli a capire il modo migliore per vincere un particolare tipo di gioco più e più volte. “Sono molto interessato a una serie di tecniche che rientrano in questo ombrello chiamato struttura contro casualità”, afferma Kelley. Alcuni dei primi progressi sulle progressioni aritmetiche si basavano su tali tecniche, che è ciò che ha portato Kelley e Meka a immergersi nell’argomento.

Il mistero della comparsa delle progressioni aritmetiche è solo una delle tante questioni matematiche relative all’ordine rispetto al disordine negli insiemi di oggetti. Comprendere l’ordine – e quando e dove devono emergere i modelli – è un tema ricorrente in molte branche della matematica e dell’informatica.

Un altro esempio di ordine negli oggetti dice che ogni gruppo di sei persone deve contenere un gruppo di almeno tre conoscenti comuni (tutti e tre si conoscono) o un gruppo di almeno tre perfetti sconosciuti (nessuno ne conosce un altro). La ricerca ha dimostrato che non importa chi siano, da dove vengano o come siano stati selezionati. C’è qualcosa di potente, forse quasi inquietante, nel fatto che possiamo dire questo – e fare altre affermazioni simili sulla struttura negli insiemi – con certezza matematica.

Risolvere il mistero delle progressioni aritmetiche potrebbe aprire le porte allo studio di relazioni più complesse tra i numeri in un insieme – lacune che cambiano in modi più elaborati, per esempio. “Queste sono versioni più sofisticate degli stessi teoremi”, afferma Bryna Kra, matematica della Northwestern University di Evanston, Illinois. “In genere, una volta che si vedono le progressioni aritmetiche … si vedono altri schemi”.

Dopo aver pubblicato il loro lavoro sulle progressioni aritmetiche, Kelley e Meka, con Shachar Lovett dell’Università della California, San Diego, hanno importato le tecniche delle loro indagini sulle progressioni aritmetiche in un contesto diverso. I ricercatori hanno risolto una questione di complessità della comunicazione, un sottocampo dell’informatica teorica che si occupa di trasmettere dati in modo efficiente tra parti che hanno solo informazioni parziali.

Inoltre, sapere che determinate strutture matematiche devono apparire in determinate situazioni può essere utile nelle reti di comunicazione del mondo reale e per la compressione delle immagini.

A parte le potenziali applicazioni, i ricercatori che studiano le progressioni aritmetiche – o altri aspetti della matematica puramente teorica – sono spesso motivati più dalla pura curiosità che da qualsiasi guadagno pratico. Il fatto che le domande su questi semplici modelli e su quando appaiono rimangano in gran parte senza risposta è, per molti, una ragione sufficiente per perseguirle.

Cosa sono le progressioni aritmetiche?

Prendiamoci un momento per mettere le mani su alcuni insiemi di numeri e sulle progressioni aritmetiche che questi insiemi contengono, a partire dai numeri primi, perenni preferiti dagli appassionati di matematica. Un numero primo è un numero intero divisibile solo per se stesso e per 1; I primi 10 numeri primi sono 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. All’interno di questi numeri, possiamo trovare alcune progressioni aritmetiche. I numeri 3, 5 e 7 formano una progressione aritmetica a tre trimestri con un divario di due. Ma i numeri in una progressione non devono necessariamente seguirsi l’un l’altro all’interno dell’insieme più ampio: i numeri 5, 11, 17, 23 e 29 formano una progressione aritmetica di cinque trimestri con un divario di sei.

All’interno di un insieme finito di numeri, è semplice determinare se ci sono progressioni aritmetiche. Potrebbe essere noioso a seconda del set, ma non è misterioso. Per insiemi infiniti di numeri, però, la domanda si fa interessante.

I numeri primi vanno avanti all’infinito, e i matematici hanno posto molte domande – e risposto ad alcune – sulle progressioni aritmetiche al loro interno. C’è una progressione aritmetica più lunga possibile, un limite al numero di termini, nei numeri primi? Oppure, riesci a trovare una progressione di qualsiasi lunghezza finita se guardi abbastanza a lungo? Nel 2004, i matematici hanno dimostrato che quest’ultima ipotesi è vera. Ma le domande, tra cui quanto lontano lungo la linea dei numeri si deve guardare per trovare una progressione aritmetica con un dato numero di termini o una data dimensione del divario, rimangono aree di ricerca attive, per i numeri primi e per altri insiemi.

Una semplice progressione aritmetica

I numeri primi contengono infinite progressioni aritmetiche, ma alcuni insiemi infiniti non ne contengono nessuna. Considera le potenze di 10: 1, 10, 100, 1.000…. Gli intervalli tra i termini consecutivi aumentano rapidamente: 9, 90, 900… E nessuno di loro è uguale all’altro. Giocando un po’ con i numeri, puoi convincerti che non esistono due potenze di 10, consecutive o meno, che abbiano lo stesso divario di qualsiasi altra coppia.

Con questo contesto, affrontiamo ora una domanda al centro di questa ricerca: perché alcuni insiemi hanno progressioni aritmetiche mentre altri no? Una grande differenza tra i numeri primi e le potenze di 10 è che ci sono molti più numeri primi che potenze di 10. Più o meno. Entrambi gli insiemi sono infiniti, ma se si sceglie un numero arbitrario come limite e si guarda quanti numeri primi o potenze di 10 ci sono al di sotto di quel numero, i numeri primi vincono ogni volta. Ci sono quattro numeri primi da 1 a 10, contro solo due potenze di 10. Ci sono 25 numeri primi da 1 a 100 e solo tre potenze di 10. I numeri primi non vincono solo ogni volta, vincono di molto, e l’importo che vincono continua ad aumentare. In questo modo, i numeri primi sono più “densi” – in senso intuitivo e tecnico – rispetto alle potenze di 10.

Un insieme di numeri abbastanza scarso può avere spazi vuoti disposti in modo da evitare progressioni aritmetiche. Troppo denso, però, e il set non può evitare di avere spazi vuoti che corrispondono. Nel XX secolo, i matematici hanno stabilito un modo per misurare quella densità. Ora stanno cercando la densità al di sopra della quale devono apparire le progressioni aritmetiche.

Densità in insiemi infiniti

Lo studio delle progressioni aritmetiche in insiemi di numeri interi iniziò sul serio nel 1936, quando i matematici ungheresi Paul Erdős e Pál Turán postularono che qualsiasi insieme di numeri interi che sia abbastanza denso deve contenere progressioni aritmetiche di qualsiasi lunghezza desiderata.

Per gli insiemi finiti, è facile capire cos’è la densità. Nell’insieme dei numeri interi compresi tra 1 e 10, i numeri primi hanno una densità di 4/10, o 0,4. Ma se vogliamo capire la densità dell’intera collezione infinita di numeri primi all’interno dell’intera collezione infinita dei numeri interi, dobbiamo trovare un modo per dare un senso all’infinito diviso per l’infinito, o ∞/∞.

I matematici usano un concetto chiamato densità asintotica per litigare con la densità di un insieme infinito di numeri interi. L’idea di base è quella di scegliere un numero come punto limite, N, e vedere cosa succede all’aumentare di N. Se la densità tende verso un numero fisso, quella è la densità asintotica dell’insieme.

Torniamo alle potenze di 10, la cui densità diminuisce lungo la linea dei numeri. Man mano che ci si allontana sempre di più, la proporzione di numeri interi che sono potenze di 10 si avvicina a zero, quindi l’insieme ha una densità asintotica pari a zero. Altri insiemi hanno una densità asintotica positiva e alcuni non si stabilizzano mai in una densità asintotica.

Ciò che Erdős e Turán hanno proposto è che qualsiasi insieme di numeri con densità asintotica positiva, piuttosto che nulla, deve contenere almeno una progressione aritmetica. Per alcuni insiemi, è ovvio (i numeri pari hanno una densità asintotica di 0,5 e contengono sicuramente progressioni aritmetiche). Ma dimostrarlo per qualsiasi insieme arbitrario di numeri si è rivelata una sfida.

Fu solo nel 1953 che il matematico tedesco-britannico Klaus Roth dimostrò la congettura, aprendo la porta a una comprensione più sfumata del ruolo che la densità gioca nelle progressioni aritmetiche. Ha dimostrato che ogni insieme con densità asintotica positiva deve contenere almeno una progressione aritmetica a tre termini, o 3-AP. La sua argomentazione si basava sulla dimostrazione che gli insiemi pseudocasuali abbastanza densi – quelli che potrebbero non essere veramente scelti a caso ma hanno le proprietà generali degli insiemi casuali – devono contenere progressioni aritmetiche. Poi sviluppò un modo per ingrandire parti di insiemi non pseudocasuali e mostrare che, se l’insieme iniziale è abbastanza denso, queste aree ingrandite devono essere strutturate in modo da garantire la presenza di una progressione aritmetica.

All’inizio del 2021, Kelley e Meka stavano studiando un problema nella teoria della complessità chiamato ripetizione parallela di giochi. Non pensate al Monopoli o agli scacchi; i “giochi” a cui i ricercatori stavano pensando non faranno guadagnare soldi ad Hasbro presto. “Abbiamo la tendenza a chiamare qualsiasi cosa una partita se ha dei turni”, dice Kelley. Nei giochi tipici che Kelley e Meka stavano guardando, i giocatori hanno accesso a informazioni diverse e devono lavorare insieme per trovare una risposta a una domanda. Ma non possono comunicare durante il gioco, quindi devono decidere in anticipo una strategia. Kelley e Meka hanno cercato di determinare come massimizzare le possibilità che i giocatori vincessero molte partite di fila.

Non è proprio un salto, un salto e un salto dalla ripetizione parallela di giochi alle progressioni aritmetiche, ma Kelley e Meka ci sono arrivati abbastanza rapidamente. “Forse in un mese eravamo al problema dei 3-AP”, dice Meka. Ricerche precedenti sulla ripetizione parallela dei giochi avevano utilizzato argomenti di struttura contro casualità. Poiché il lavoro di Roth sulle progressioni aritmetiche fu il primo a utilizzare tale tecnica, Kelley e Meka erano interessati a quel lavoro nel suo habitat originale.

“Nell’informatica teorica, le persone guardano alla matematica per alcuni strumenti che potrebbero usare e, a meno che non si sia pronti a mettersi nei guai seri, di solito si vede se si possono usare gli strumenti e poi, se non si può, si passa avanti”, dice Kelley. “Non provi ad aprirli e vedere come sono”. Ma lui e Meka hanno fatto proprio questo, sapendo che avrebbero potuto finire in una profonda tana del coniglio e finire con nulla da mostrare per il loro tempo e i loro sforzi. Hanno scavato nelle argomentazioni di Roth – così come nelle ricerche più recenti sullo stesso argomento – per vedere se potevano spingere ulteriormente il lavoro. E così si sono ritrovati a fissare le progressioni aritmetiche.

Per saperne di più sull’ordine tra sei persone e sugli oggetti più in generale, dai un’occhiata a questo video di Numberphile su amici e sconosciuti.

Raggiungere nuovi limiti

Il contributo di Roth è stato più potente del semplice mostrare che qualsiasi insieme con densità asintotica positiva deve contenere un 3-AP. Dimostrò anche che alcuni insiemi con densità asintotica pari a zero, se la densità tende verso lo zero abbastanza lentamente man mano che si esce lungo la linea dei numeri, devono contenere almeno un 3-AP.

Pensa alla densità come se dovesse passare sotto una barra di limbo. Se un set diventa sparso troppo lentamente, non può arrivare sotto e deve contenere una progressione aritmetica. Ma un insieme che si avvicina a una densità di zero abbastanza rapidamente si abbassa al di sotto. Per quell’espansione, tutto va bene: potrebbe avere o meno una tale progressione.

La prova iniziale di Roth ha trovato un limite superiore a dove deve essere la barra del limbo. Ha dimostrato che qualsiasi insieme la cui densità si avvicina allo zero ad una velocità simile o più lenta dell’espressione 1/log(log(N)) deve contenere almeno una progressione aritmetica. Log significa prendere il logaritmo, e ricordare che N è il numero scelto come limite arbitrario in un insieme infinito. Stiamo valutando cosa succede all’aumentare di N.

I logaritmi crescono lentamente, più o meno come il numero di cifre di un numero. Il logaritmo di 1 è zero, di 10 è 1, di 100 è 2, di 1.000 è 3 e così via. Ma prendendo i logaritmi di quei logaritmi si ottiene una crescita molto più lenta. Per spostare log(log(N)) da zero a 1, dobbiamo spostare N da 10 a 10 miliardi. Dividendo 1 per questo doppio logaritmico, come appare nell’opera di Roth, otteniamo una densità che arrancava appena verso lo zero.

Diversi anni prima, nel 1946, il matematico Felix Behrend aveva studiato il limite inferiore della barra del limbo. Ha sviluppato una ricetta per preparare set senza 3-AP, dimostrando che qualsiasi set di questo tipo deve essere davvero estremamente scarso. Il suo limite era una densità che va a zero all’incirca alla stessa velocità di 1/e^{(log(N))^1/2}. Questa espressione potrebbe non sembrare familiare, ma c’è una funzione esponenziale nel denominatore. Il log e 1/2 potenza rallentano un po’ le cose, ma l’intera espressione va a zero molto più velocemente del doppio log che Roth ha scoperto in seguito.

Negli ultimi decenni, i ricercatori hanno cercato di colmare il divario tra le stime in stile Roth degli insiemi più sparsi che devono contenere un 3-AP e le stime in stile Behrend degli insiemi più densi che non ne contengono uno. Nel 2020, i matematici Thomas Bloom dell’Università di Oxford e Olof Sisask dell’Università di Stoccolma hanno infranto quella che era diventata nota come la barriera logaritmica per il limite superiore della barra del limbo in stile Roth, dimostrando che qualsiasi insieme con una densità che va a zero più lentamente di 1/log(N) deve contenere almeno un 3-AP. Il lavoro fu visto come una svolta nel campo, anche se il limite superiore era ancora più vicino al precedente limite superiore più noto che al limite inferiore di Behrend.

Kelley e Meka hanno abbassato drasticamente il limite superiore. Il loro risultato è stato un tasso che va a zero all’incirca allo stesso ritmo di 1/e^{(log(N))^1/11}. Questa formula sembra stranamente simile al limite inferiore di Behrend. Per la prima volta in assoluto, i limiti superiore e inferiore sono a distanza di tiro l’uno dall’altro. Colmare questo divario rivelerebbe la posizione specifica della barra del limbo e quindi darebbe una risposta chiara a quali espansioni devono contenere almeno un 3-PA.

Diretto a zero

La velocità con cui la densità di un insieme si avvicina allo zero man mano che ci si sposta lungo la linea dei numeri (riquadri) può rivelare se quell’insieme deve contenere una progressione aritmetica. Nel 2023, gli informatici Zander Kelley e Raghu Meka hanno dimostrato che se la densità si avvicina allo zero a una velocità più o meno simile o più lenta della linea nera sopra, l’insieme deve contenere una progressione. Questo limite superiore è drammaticamente inferiore alla “barriera logaritmica” (infranta nel 2020 e mostrata in rosso), ma è ancora molto lontana dal limite inferiore (identificato da Felix Behrend decenni fa).

Limiti superiore e inferiore per gli insiemi che contengono una progressione aritmetica

Qual è il prossimo passo?

Quando Kelley e Meka hanno iniziato a lavorare sul problema dei 3 AP, pensavano che probabilmente avrebbero semplicemente curiosato in giro per identificare le barriere per spostare il limite superiore verso il basso. Un anno dopo, i due stavano scrivendo un articolo sulla loro scoperta. “Penso che una cosa che ci ha fatto andare avanti è stata che non ci siamo mai sentiti come se stessimo sbattendo completamente contro un muro”, dice Meka. “Sembrava sempre che stessimo imparando qualcosa di utile o che stessimo effettivamente facendo progressi”.

Meka descrive il loro approccio generale, basato sulle prime tecniche di Roth, come lo sfruttamento di una “dicotomia illusoria” tra casualità e struttura. Hanno sviluppato una definizione di pseudocasualità per il loro lavoro e hanno dimostrato che per questa definizione, qualsiasi insieme pseudocasuale abbastanza denso deve contenere almeno una progressione aritmetica.

Dopo aver gestito il caso pseudocasuale, il team ha considerato insiemi di numeri più strutturati e ha dimostrato che anche questi insiemi dovevano esibire i modelli desiderati. Infine, Kelley e Meka ampliarono da questi tipi di insiemi a tutti gli insiemi di numeri abbastanza grandi, dimostrando che quegli insiemi devono avere le proprietà degli insiemi pseudocasuali o strutturati.

“Mi sembrava del tutto intrattabile portare avanti quelle tecniche”, dice Siask, “fino a quando questo articolo di Kelley e Meka non è arrivato nella mia casella di posta”. Lui e Bloom, che in precedenza aveva infranto la barriera logaritmica, “hanno passato un po’ di tempo a digerire l’articolo e a parlarne fino a quando non lo abbiamo capito nella nostra lingua”, dice.

I matematici e gli informatici tendono a usare alcune notazioni e terminologie diverse, ma Sisask, Bloom e altri esperti del settore hanno rapidamente riconosciuto il lavoro come solido. Dopo aver digerito gli argomenti, Sisask e Bloom scrissero una spiegazione del lavoro, con alcuni sottili miglioramenti tecnici, orientata verso altri ricercatori in combinatoria. Diversi mesi dopo, il team ha abbassato un po’ di più il limite superiore, ottenendo un nuovo limite di 1/e^{(log(N))^1/9}. 

I ricercatori di combinatoria stanno ancora cercando di capire fino a che punto possono andare. Saranno in grado di spingere il limite superiore fino al limite inferiore più conosciuto, o ci sarà sempre un piccolo divario in cui la nostra conoscenza è incompleta? Kelley e Meka stanno utilizzando gli strumenti che hanno affinato sulle progressioni aritmetiche per continuare a lavorare su problemi nella teoria della complessità e in altre aree dell’informatica teorica.

Quando ho chiesto a Meka come mai due informatici abbiano fatto un così grande passo avanti su un problema matematico che aveva sconcertato gli esperti di combinatoria per anni, ha detto che non ne era sicuro. Pensa che forse il loro vantaggio è venuto dall’essere freschi alla sfida.

“Il problema esiste da molto tempo e i progressi sembravano piuttosto bloccati”, afferma. Infatti, dopo che lui e Kelley erano sulla buona strada per la pubblicazione, Kelley dice di essersi imbattuto in un post sul blog del 2011 che delineava esattamente il motivo per cui i matematici erano pessimisti riguardo all’approccio che i due avevano eventualmente usato.

“La gente pensava che queste tecniche non potessero superare le barriere esistenti”, dice Meka, “ma forse non sapevamo che esistessero le barriere”.

Domande o commenti su questo articolo? Inviaci un’e-mail all’indirizzo feedback@sciencenews.org | Domande frequenti sulle ristampe

Una versione di questo articolo è apparsa nel numero del 24 febbraio 2024 di Science News.

Citazioni

Z. Kelley e R. Meka. Limiti forti per 3 progressioni. arxiv: 2302.05537. Presentato il 10 febbraio 2023.

K.F. Roth. Su determinati insiemi di numeri interi. Giornale della Società Matematica di Londra. Gennaio 1953. DOI: 10.1112/jlms/s1-28.1.104.

T.F. Bloom e O. Sisask. Rompere la barriera logaritmica nel teorema di Roth sulle progressioni aritmetiche. arxiv:2007.03528. Inviato il 7 luglio 2020.

T.F. Bloom e O. Sisask. Il Kelley-Meka salta per serie prive di progressioni aritmetiche a tre trimestri. arxiv.org/abs/2302.07211. Presentato il 14 febbraio 2023.