🔢 mathematics

Resolution of Erdős Problem #728: a writeup of Aristotle's Lean proof

Questo articolo presenta la prima risoluzione autonoma tramite IA del Problema di Erdős #728, utilizzando una combinazione di GPT-5.2 Pro e del sistema Aristotle per generare una prova formale in Lean che dimostra un fenomeno di gap logaritmico nella divisibilità fattoriale attraverso una nuova analisi coefficiente per coefficiente primo dei coefficienti binomiali.

Autori originali: Nat Sothanaphan

Pubblicato 2026-01-27

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Nat Sothanaphan

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

La Visione d'Insieme: Un Team di Matematici AI

Immaginate un famoso matematico in pensione, Paul Erdős, che ha passato la vita lasciando dietro di sé una gigantesca lista di "cose da fare" composta da enigmi irrisolti. Uno di questi enigmi, il #728, è rimasto intoccato per decenni.

Recentemente, un team composto da un'IA super-intelligente (GPT-5.2 Pro) e da un robot specializzato nel controllo matematico (Aristoteles) lo ha finalmente risolto. Non si sono limitati a indovinare la risposta; hanno costruito una dimostrazione rigorosa, passo dopo passo, che un computer può verificare come 100% corretta. Gli autori di questo articolo stanno semplicemente traducendo quel codice informatico in una storia che gli esseri umani possano leggere.

L'Enigma: Il Bilanciamento dei Fattoriali

Il problema pone una domanda riguardante i fattoriali (numeri come $5! = 5 \times 4 \times 3 \times 2 \times 1$ ).

Immaginate di avere una pila enorme di blocchi che rappresentano $n!$ . Volete vedere se potete costruire due torri più piccole, $a!$ e $b!$ , e una terza torre piccola $k!$ , tali che le due torri piccole si inseriscano perfettamente dentro quella grande senza che avanzino blocchi.

Matematicamente, questo significa: $a! \times b!$ divide esattamente $n! \times k!$ ?

L'enigma chiede: Quanto può essere grande il "gap" ( $k$ )?

Se $k$ è minuscolo, è facile far incastrare i blocchi.
Se $k$ è enorme, di solito è impossibile.
Il trucco è trovare una "zona Goldilocks" (una zona ideale) dove $k$ sia abbastanza grande da essere interessante, ma non così grande da far non incastrare i blocchi.

L'IA ha dimostrato che è possibile trovare infinitamente molte situazioni in cui questo gap ( $k$ ) è approssimativamente della dimensione del logaritmo del numero totale. In parole povere: se il vostro numero totale di blocchi è un milione, il gap può essere di circa 14. Se il vostro numero è un miliardo, il gap può essere di circa 20. Cresce molto lentamente, ma cresce davvero.

La Strategia: Il Gioco del "Riporto"

Per risolvere questo problema, i matematici hanno dovuto osservarlo attraverso la lente dei numeri primi (2, 3, 5, 7, ecc.). Hanno utilizzato una regola chiamata Teorema di Kummer, che è simile a un gioco di "riporto" nell'addizione.

L'Analogia: Il Secchio che Trabocca
Immaginate di sommare numeri in una lingua specifica (base $p$ ).

Quando sommate due cifre e il risultato è troppo grande per una singola posizione, "portate" l'eccedenza alla posizione successiva (il riporto).
L'Obiettivo: L'IA doveva trovare un numero ( $m$ ) che, quando raddoppiato, causasse molti riporti (come un secchio che trabocca ripetutamente).
L'Ostacolo: Allo stesso tempo, l'IA doveva assicurarsi che i numeri immediatamente successivi a $m$ (come $m+1, m+2...$ ) non avessero dei "picchi" — ovvero una divisibilità improvvisa e massiccia per un numero primo che rovinerebbe l'equilibrio.

Pensatelo come camminare su una fune tesa:

La Fune Tesa (La condizione del "Riporto"): Dovete scegliere un numero che sia "ricco di riporti". Quando lo raddoppiate, deve traboccare nei suoi secchi il più spesso possibile. Questo crea una "rete di sicurezza" di divisibilità che aiuta l'equazione a funzionare.
I Picchi (La condizione "Negativa"): Dovete evitare i numeri in cui i successivi interi sono divisibili per potenze enormi di un numero primo. Questi sono i "picchi" che vi farebbero cadere dalla fune.

Come hanno trovato la soluzione

L'IA non ha scelto un numero a caso. Ha utilizzato un argomento di conteggio (una strategia statistica):

L'Area di Ricerca: Hanno esaminato un intervallo enorme di numeri (da $M$ a $2M$ ).
Il Filtro: Hanno calcolato quanti numeri in questo intervallo fossero "negativi" (ovvero non avevano abbastanza riporti, o presentavano un picco).
Il Risultato: Hanno dimostrato che il numero di candidati "negativi" è in realtà più piccolo del numero totale di candidati nell'intervallo.
La Conclusione: Poiché ci sono più numeri che numeri "negativi", deve esserci per forza almeno un numero "positivo" rimasto nel mucchio.

È come dire: "Se avete un barattolo di 1.000 biglie e solo 900 di esse sono rosse (negative), deve esserci almeno un centinaio di biglie blu (positive) rimaste". L'IA ha dimostrato che per ogni barattolo sufficientemente grande, una biglia "positiva" esiste sempre.

Perché questo è importante (secondo l'articolo)

Prima dimostrazione solo-AI: Questa è la prima volta che un sistema di IA ha risolto autonomamente uno dei famosi problemi di Erdős e ha prodotto una dimostrazione formale che gli esseri umani possono verificare.
Il "Gap Logaritmico": Hanno confermato che il gap tra i numeri può essere logaritmico. Sebbene l'articolo noti che il gap potrebbe potenzialmente essere leggermente più grande (come suggerito dal matematico Terence Tao), questa dimostrazione stabilisce una base solida e garantita.
Metodologia: Il metodo utilizzato (contare i riporti ed evitare i picchi) è simile alle tecniche che lo stesso Erdős utilizzava in passato, ma applicato qui a un bersaglio più complesso e mobile.

Riassunto

L'articolo è un rapporto su come un team di IA abbia risolto un enigma matematico di 40 anni fa. Hanno dimostrato che è sempre possibile trovare un insieme specifico di numeri in cui un'equazione fattoriale complessa si bilancia perfettamente. Ci sono riusciti trattando i numeri come secchi che traboccano (riporti) e dimostrando che si può sempre trovare un secchio che trabocchi quanto basta per essere utile, senza versare troppo nei posti sbagliati.

Sintesi Tecnica: Risoluzione del Problema di Erdős #728

Enunciato del Problema
Il documento affronta il Problema di Erdős #728, che investiga la dimensione massima possibile del gap $k := a + b - n$ sotto il vincolo di divisibilità fattoriale:
$a! b! \mid n! (a + b - n)!$
Senza ulteriori vincoli, esistono soluzioni banali dove $k$ può essere arbitrariamente grande (ad esempio, prendendo $a$ e $b$ molto grandi). Per rendere il problema non banale, gli autori impongono la condizione che $a$ e $b$ siano distanti dagli estremi, specificamente $\varepsilon n \le a, b \le (1-\varepsilon)n$ per un certo $0 < \varepsilon < 1/2$ . L'obiettivo è determinare quanto possa essere grande $k$ rispetto a $n$ sotto tali vincoli.

Metodologia e Strategia di Dimostrazione
La dimostrazione procede trasformando la condizione di divisibilità fattoriale in un problema riguardante i coefficienti binomiali e le valutazioni $p$ -adiche.

Riduzione alla Divisibilità Binomiale:
Impostando $n = 2m$ , $b = m$ e $a = m + k$ , la condizione originale è equivalente a:
$\binom{m+k}{k} \mid \binom{2m}{m}$
Ciò richiede di dimostrare che per ogni numero primo $p$ , la valutazione $p$ -adica del lato sinistro è minore o uguale a quella del lato destro:
$\nu_p\left(\binom{m+k}{k}\right) \le \nu_p\left(\binom{2m}{m}\right)$
Analisi della Valutazione tramite il Teorema di Kummer:
Utilizzando il teorema di Kummer, $\nu_p\left(\binom{2m}{m}\right)$ viene identificata con il numero di riporti che si verificano durante l'addizione di $m + m$ in base $p$ . Il termine $\nu_p\left(\binom{m+k}{k}\right)$ è limitato dal valore massimo della valutazione di qualsiasi termine nel blocco consecutivo $m+1, \dots, m+k$ , indicato con $V_p(m, k)$ .
La disuguaglianza fondamentale da soddisfare è:
$V_p(m, k) \le \kappa_p(m)$
dove $\kappa_p(m)$ è il conteggio dei riporti per $m+m$ in base $p$ .
Analisi Primo per Primo:
Gli autori dividono l'analisi in due regimi basati sulla dimensione del numero primo $p$ rispetto a $k$ :
- Primi Grandi ( $p > 2k$ ): In questo intervallo, la disuguaglianza è soddisfatta automaticamente. Poiché la lunghezza dell'intervallo $k$ è minore di $p/2$ , al massimo un numero nel blocco $m+1, \dots, m+k$ può essere divisibile per $p$ . Se una potenza elevata $p^J$ divide un termine, le cifre in base $p$ di $m$ forzano almeno $J$ riporti quando raddoppiate, soddisfacendo la condizione.
- Primi Piccoli ( $p \le 2k$ ): Questa è la difficoltà principale. Gli autori impiegano un argomento di conteggio probabilistico per trovare un intero $m$ $m$ in un grande intervallo $[M, 2M]$ $[M, 2 M]$ che soddisfi simultaneamente due condizioni per tutti i $p \le 2k$ $p \leq 2 k$ :
  - Ricco di Riporto (Carry-Rich): L'espansione in base $p$ di $m$ possiede molte cifre $\ge \lceil p/2 \rceil$ nelle prime $L_p$ posizioni. Ciò forza un alto numero di riporti ( $\kappa_p(m)$ ) quando $m$ viene raddoppiato.
  - Privo di Picchi (Spike-Free): Nessun intero nel blocco $m+1, \dots, m+k$ è divisibile per una potenza di $p$ insolitamente alta (specificamente, $V_p(m, k)$ è mantenuto al di sotto di una soglia $J_p + t(M)$ ).
Esistenza tramite il Legge della Disgiunzione (Union Bound):
Gli autori definiscono gli insiemi "cattivi" di interi $m$ che falliscono o la condizione di riporto o la condizione di picco. Utilizzando i limiti di Chernoff per la distribuzione delle cifre grandi e il semplice conteggio per la condizione di picco, dimostrano che la misura totale degli insiemi cattivi è strettamente inferiore alla dimensione dell'intervallo $[M, 2M]$ . Di conseguenza, esiste un $m$ "buono" che soddisfa la condizione di divisibilità per tutti i numeri primi rilevanti simultaneamente.

Risultati Chiave
Il documento stabilisce il Teorema 1 (Finestra del gap logaritmico):
Per ogni costante $0 < C_1 < C_2$ e $0 < \varepsilon < 1/2$ , esistono infiniti triple $(a, b, n) \in \mathbb{N}^3$ tali che:

$\varepsilon n \le a, b \le (1-\varepsilon)n$
$a! b! \mid n! (a + b - n)!$
$C_1 \log n < a + b - n < C_2 \log n$

La costruzione produce un gap $k$ che cresce logaritmicamente con $n$ . Gli autori osservano che l'attuale dimostrazione produce un $k \asymp \log n$ , ma il metodo potrebbe potenzialmente essere esteso a $k = \exp(c\sqrt{\log n})$ con ulteriori raffinamenti, sebbene l'attuale esposizione si concentri sul regime logaritmico.

Significato e Rivendicazioni

Primo Problema di Erdős risolto dall'IA: Gli autori affermano che questo è il primo problema di Erdős ad essere stato "completamente risolto autonomamente da un sistema di IA". Il sistema utilizzato è stato una combinazione di GPT-5.2 Pro e il dimostratore di teoremi "Aristotle" di Harmonic.
Verifica Formale: La dimostrazione è stata generata come una prova formale nel dimostratore di teoremi Lean e successivamente tradotta nella matematica informale presentata in questo documento.
Contributo Metodologico: Il lavoro estende le tecniche precedenti di Erdős e Pomerance riguardanti i divisori dei coefficienti binomiali centrali. A differenza dei lavori precedenti che si concentravano su interi "poveri di riporti" (pochi riporti) o dimensioni di gap fisse, questa dimostrazione costruisce interi "ricchi di riporti" per gestire una finestra crescente di dimensione $k \asymp \log n$ .
Indipendenza: Gli autori notano che, dopo il loro lavoro iniziale, Carl Pomerance ha derivato indipendentemente risultati simili, e modifiche di questo argomento sono state utilizzate per risolvere i Problemi di Erdős #729 e #401.

Il documento non pretende di risolvere il problema nella sua forma assolutamente più forte (notando il potenziale per gap più grandi), ma afferma la risoluzione riuscita della specifica questione del gap logaritmico posta da Erdős.