Positive Lower Density for Hofstadter's $ab-1$ Problem

Il Gioco Infinito della Costruzione di Numeri

Immaginate un vasto, infinito parco giochi dove i numeri sono i giocattoli. Nel mondo della matematica, nello specifico in un ramo chiamato teoria dei numeri, i ricercatori amano giocare a giochi con regole che generano nuovi numeri partendo da quelli vecchi. Uno dei tipi di giochi più famosi coinvolge la "ricorrenza" o il "rinnovamento". Pensatelo come a un gioco di sedie musicali, ma invece delle persone ci sono i numeri, e invece di una sedia c'è un posto specifico su una linea numerica. La grande domanda che i matematici si pongono da decenni è: se continuate a giocare a questo gioco per sempre, i numeri che create si disperderanno uniformemente in tutto il parco giochi, o si raggrupperanno in un angolo, lasciando enormi spazi vuoti?

Questo specifico articolo affronta un enigma che è nato da una regola semplice: parti dai numeri 2 e 3. Poi, prendi due numeri qualsiasi che hai già e che siano diversi tra loro, moltiplicali e sottrai 1. Se il risultato è un numero intero, aggiungilo alla tua collezione. Ripeti all'infinito. La domanda, posta dal leggendario matematico Paul Erdős (che l'aveva sentita dall'autore delle famose sequenze "Hofstadter's Figure-Figure"), è se questa collezione di numeri sia abbastanza "spessa". Ha una "densità inferiore positiva"? In parole povere, l'insieme di numeri che generate occupa alla fine una percentuale significativa e non nulla della linea numerica, non importa quanto lontano si vada? Per molto tempo, nessuno sapeva se la risposta fosse sì o no.

La Soluzione: Un Sistema di Traffico per i Numeri

In questo articolo, Samuel Korsky dimostra che la risposta è sì. L'insieme di numeri generati da questa regola ha effettivamente una densità inferiore positiva. Ciò significa che mentre si osservano intervalli di numeri sempre più grandi, si troverà sempre una parte garantita e non nulla di essi appartenente a questo insieme speciale. Non sono solo pochi numeri sparsi; sono abbondanti.

Per capire come l'autore abbia risolto questo problema, immaginate l'insieme dei numeri come una città, e la regola "moltiplica e sottrai 1" come un insieme di strade a senso unico. L'obiettivo dell'autore era dimostrare che ci sono così tanti modi diversi di guidare attraverso questa città che non si può evitare di colpire molte destinazioni. Tuttavia, c'è un intoppo: la regola dice che puoi moltiplicare solo numeri distinti. Se provi a moltiplicare un numero per se stesso, la regola si rompe. Questo è come una legge del traffico che dice che non puoi guidare su una strada se sei già stato su quel preciso segmento stradale durante lo stesso viaggio.

La strategia dell'autore è costruire un "sistema di controllo del traffico" utilizzando una mappa divisa in 20 zone specifiche (intervalli). Egli assegna diversi "moltiplicatori" (come 2, 3, 5, 9, 14) a queste zone. Quando un numero finisce in una zona, il sistema indica quale moltiplicatore usare successivamente. Il genio della dimostrazione risiede nel modo in cui questi moltiplicatori sono scelti. L'autore predispone quattro diversi "modelli di traffico" (assegnazioni). Alternando questi modelli in base allo stato attuale del sistema, egli assicura che i numeri non rimangano bloccati o non violino la regola della "distintività".

Pensateci come a un gioco di "Segui il Capo" dove il capo cerca di mantenere un equilibrio perfetto. L'autore tiene traccia degli "ingredienti" dei numeri (specificamente le potenze dei numeri primi 2, 3, 5 e 7). Vuole che la ricetta rimanga bilanciata in modo che i numeri crescano in un modo molto specifico e prevedibile. Utilizza un ciclo di feedback: se la ricetta diventa troppo pesante sul numero 2, il sistema passa a un modello che aggiunge più 3 o 5 per bilanciare il tutto. Questo mantiene la "pendenza" della crescita (quanto velocemente i numeri diventano grandi) bloccata su un obiettivo specifico.

L'articolo mostra che, gestendo attentamente questi passaggi, il sistema crea un numero enorme di percorsi unici che portano tutti alla stessa "pendenza". Poiché i percorsi sono unici e il sistema è progettato per tornare al suo punto di partenza ripetutamente (un concetto chiamato "ricorrenza positiva"), la matematica dimostra che esistono infiniti numeri distinti generati.

Fondamentalmente, l'autore dimostra che questi percorsi sono distinti anche se la matematica sottostante permette alcune sovrapposizioni (il sistema non è "libero" nel senso matematico stretto). Lo dimostra mostrando che, se si tracciano i percorsi a ritroso sulla sua mappa a 20 zone, essi non si incrociano mai fino a raggiungere la fine. Ciò garantisce che ogni percorso produca un numero finale unico.

Il colpo di scena finale è un argomento di conteggio. L'autore calcola che per ogni "passaggio" in questo processo, il numero di percorsi validi cresce a un ritmo che corrisponde alla crescita dei numeri stessi. Dimostra che per un numero $x$ specifico, la quantità del suo insieme speciale trovata tra $1$e$x$ è almeno $c \times x$, dove $c$ è una costante maggiore di zero. In altre parole, non importa quanto si conti, si troverà sempre un flusso costante di questi numeri.

L'articolo non si limita a suggerire che ciò sia probabile; fornisce una dimostrazione matematica rigorosa e passo dopo passo. Utilizza una combinazione di probabilità (per dimostrare che il sistema ritorna sempre al suo inizio), geometria (per mappare gli intervalli) e teoria dei numeri (per contare i fattori primi). Il risultato è una risposta definitiva a una domanda vecchia di decenni: l'insieme non è rado; è denso, riempiendo la linea numerica con una presenza costante e positiva.