Un modello OpenAI smentisce una congettura centrale della geometria discreta

Per quasi 80 anni, i matematici hanno studiato una questione apparentemente semplice: se si colocano n punti nel piano, quante coppie di punti possono essere esattamente a distanza 1 l'uno dall'altro?

Questo è il problema delle distanze unitarie piane, proposto da Paul Erdős nel 1946. È uno dei problemi più noti della geometria combinatoria, facile da enunciare e notevolmente difficile da risolvere. Il libro del 2005 "Research Problems in Discrete Geometry", di Brass, Moser e Pach, lo chiama "probabilmente il problema più noto (e più semplice da spiegare) della geometria combinatoria". Noga Alon, un noto combinatorialista di Princeton, lo descrive come "uno dei problemi preferiti di Erdős". Erdős stesso offrì un premio in denaro per risolvere questo problema.

Oggi, condividiamo una svolta nella questione delle distanze unitarie. Dal lavoro originale di Erdős, si credeva che le costruzioni "griglia quadrata" mostrate più avanti fossero essenzialmente ottimali per massimizzare il numero di coppie a distanza unitaria. Un modello interno a OpenAI ha smentito questa congettura duratura, fornendo una famiglia infinita di esempi che danno miglioramenti polinomiali. La prova è stata verificata da un gruppo di matematici esterni. Questi hanno anche scritto un articolo affianco che spiega l'argomento e fornisce ulteriore contesto per l'importanza del risultato.

Il risultato è notevole anche per il modo in cui è stato ottenuto. La prova è venuta da un nuovo modello generico di ragionamento, invece che da uno specifico addestramento su matematica o strumenti scaffoldati per cercare strategie di dimostrazione. Nell’ambito di uno sforzo più ampio per testare se i modelli avanzati possano contribuire alla ricerca di frontiera, li abbiamo valutati su una collezione di problemi di Erdős. In questo caso, è emersa una prova che ha risolto il problema aperto.

Questa dimostrazione è un importante traguardo per le comunità matematica e AI. Segna la prima volta che un problema aperto prominente, centrale in un sottocampo della matematica, è stato risolto autonomamente dall'IA. Inoltre, dimostra la profondità di ragionamento che questi sistemi riescono a supportare. La matematica fornisce un testo particolarmente chiaro per il ragionamento: i problemi sono precisi, potenziali prove possono essere verificate, e un lungo argomento funziona solo se il ragionamento si mantiene coerente dall'inizio alla fine. Il metodo con cui è stato risolto il problema è anch’esso notevole. La prova introduce idee inaspettate ma sofisticate della teoria algebrica dei numeri rilevanti per una domanda geometrica elementare.

Lo studioso premiato con la Fields Medal Tim Gowers, nel commento al paper affianco, chiamò il risultato "un traguardo per la matematica guidata dall'IA". Secondo il noto teorico dei numeri Arul Shankar, "Penso che questo lavoro dimostri che i modelli AI correnti vadano al di là degli ausiliari per i matematici umani – sono in grado di avere idee originali ed ingegnose, e poi portarle a buon fine".

i matematici si commentano il risultato

1 di 4

Costruzione precedente conosciuta di molte distanze unitarie da una griglia quadrata ridimensionata.

Il problema delle distanze unitarie

Sia $u \left(\right. n \left.\right)$ il numero massimo di coppie a distanza unitaria tra $n$ punti nel piano. Esempi che raggiungono una crescita lineare sono facili da costruire: posizionando $n$ punti in una linea si ottengono $n - 1$ coppie, mentre una griglia quadrata fornisce circa $2n$ coppie. La costruzione precedentemente meglio conosciuta, derivata da una griglia quadrata ridimensionata, dà persino di più: $n^{1 + C / \log \log (n)}$ per una costante $C$. Poiché $\log \log(n)$ tende all’infinito con $n$, il termine aggiuntivo nell'esponente tende a $0$, il che significa che queste costruzioni ottengano una crescita solo leggermente superiore a quella lineare. Per decenni, si credeva che questa velocità fosse essenzialmente la migliore possibile, e nessuna costruzione fosse in grado di migliorare significativamente su quella della griglia quadrata. In termini tecnici, Erdős congetturò un limite superiore di $n^{1 + o \left(\right.1\left.\right)}$ in cui il termine $o \left(\right.1\left.\right)$ tende a $0$ quando $n$ aumenta.

Il nostro nuovo risultato smentisce questa congettura. Più precisamente, per infiniti valori di $n$, la prova costruisce configurazioni di $n$ punti che forniscono almeno $n^{1 + \delta}$ coppie a distanza unitaria, per un fissato esponente $\delta > 0$. (La prova originale dell’AI non fornisce un $\delta$ esplicito, ma un'affinamento imminente del professore di matematica di Princeton Will Sawin mostra che si può assumere $\delta = 0.014$.)

La storia del problema aiuta a capire perché il risultato è sorprendente. Il miglior limite inferiore noto era sostanzialmente invariato da costruzione originale del 1946 di Erdős. Il miglior vincolo superiore, $O(n^{4 / 3})$, risale al lavoro di Spencer, Szemerédi e Trotter del 1984. Nonostante ulteriori raffinamenti e lavori strutturali successivi da parte di Székely, Katz e Silider, Pach, Raz, Solymosi e di altri, il limite superiore è rimasto essenzialmente invariato. Come ulteriore supporto alla congettura, Matoušek e Alon-Bucić-Sauermann hanno studiato il problema con distanze non-euclidee nel piano e hanno provato che “la maggior parte” di queste distanze non-euclidee rispettano la congettura in qualche modo.

Nuove tecniche dalla teoria algebrica dei numeri

Alla base, la prova parte con un’idea geometrica familiare e la spinge in una direzione inaspettata.

La dimostrazione originale del limite inferiore di Erdős può essere compresa attraverso i numeri di Gauss: numeri della forma $a + b i$, dove $a$ e $b$ sono interi e $i$ è la radice quadrata di $-1$. I numeri di Gauss estendono gli interi comuni e, come questi, godono di proprietà come la fattorizzazione unica in primi. Tali estensioni degli interi o razionali sono note come campi algebrici dei numeri. Nuovo argomento sostituisce i numeri di Gauss con generalizzazioni più complicate dalla teoria algebrica numera, con simmetrie più ricche che possono creare molte più differenze a lunghezza unitaria.

L'argomento preciso utilizza strument