🔢 mathematics

Superlinear complexity of the $(3/2)^n$ steering word

Questo articolo dimostra che la complessità dei sottoparole della parola di guida generata dalla mappa $(3/2)^n$ è superlineare, un risultato stabilito utilizzando il Teorema dello Spazio Sottostante e completamente formalizzato in Lean-4.

Autori originali: Ralf Stephan

Pubblicato 2026-07-14

📖 5 min di lettura🧠 Approfondimento

CC0 1.0

Autori originali: Ralf Stephan

Articolo originale dedicato al pubblico dominio sotto CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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

Immagina una macchina magica che prende un numero, lo moltiplica per 1,5 e poi lo arrotonda al numero intero più vicino. Ora, immagina di far passare questa macchina ripetutamente, partendo dal numero 1.

1 diventa 1,5, che arrotonda a 2.
2 diventa 3, che resta 3.
3 diventa 4,5, che arrotonda a 5.
5 diventa 7,5, che arrotonda a 8.

Questo crea una sequenza di numeri interi: 1, 2, 2, 3, 5, 8, e così via. Ma il saggio non è interessato solo ai numeri in sé; è interessato al "volante" che dice alla macchina come arrivarci. Ad ogni singolo passaggio, la macchina ha dovuto scegliere se arrotondare per eccesso o per difetto per colpire l'intero più vicino. Quando metti insieme tutte queste decisioni, ottieni una lunga, infinita "parola di guida".

La grande domanda che il saggio pone è: quanto è complesso questo codice?

Nel mondo dei pattern, alcuni codici sono noiosamente semplici. Pensa a una canzone che ripete semplicemente "la-la-la" per sempre. Questo è un pattern semplice. Altri codici sono caotici e disordinati, come l'interferenza di una radio. I matematici misurano questa "disordinezza" contando quanti pezzi unici e brevi (o "sotto-parole") esistono in un codice di una certa lunghezza. Se un codice è semplice, il numero di pezzi unici cresce lentamente (come una linea retta). Se è complesso, il numero di pezzi unici esplode.

La Scoperta Principale
Il saggio dimostra che questa specifica parola di guida è estremamente complessa. Non cresce semplicemente in linea retta; cresce in modo "superlineare". Ciò significa che man mano che si osservano pezzi sempre più lunghi del codice, il numero di pattern unici che si trovano aumenta sempre più velocemente, schizzando verso l'infinito.

Per dirla in modo giocoso: se provassi a prevedere la mossa successiva in questa sequenza guardando il passato, finiresti per sbattere contro un muro. Non importa quanto lungo sia il pattern che trovi, la sequenza prima o poi farà qualcosa di completamente nuovo che non hai mai visto prima. Si rifiuta di stabilizzarsi in un ciclo.

Ciò che il Saggio Esclude
Il saggio esclude esplicitamente l'idea che questa sequenza sia "eventualmente periodica". In parole povere, questo significa che la sequenza non tornerà mai in un ciclo ripetitivo come un disco rotto. Non inizierà mai a dire "1, 2, 3, 1, 2, 3" per sempre. Gli autori dimostrano che, per quanto avanti si vada nella sequenza, non si troverà mai un punto in cui essa ripete lo stesso pattern ripetutamente.

Quanto sono sicuri?
Gli autori non stanno solo tirando a indovinare o simulando su un computer. Essi hanno dimostrato il fatto.

Hanno costruito una fortezza di logica usando due strumenti matematici pesanti (i teoremi di Corvaja–Zannier e Nair–Kumar–Rout) che agiscono come serrature indistruttibili. Hanno anche fatto una cosa molto speciale: hanno tradotto l'intera dimostrazione in un linguaggio informatico chiamato Lean-4. Questo computer ha controllato ogni singolo passaggio della loro logica per assicurarsi che non ci fossero errori umani. Il computer ha detto: "Sì, questa dimostrazione è valida".

Il Viaggio della Dimostrazione
La dimostrazione avviene in tre fasi, come scalare una montagna:

Fase 0 (Le Fondamenta): Hanno prima dimostrato che se la sequenza avesse ripetuto un pattern lungo, violerebbe le leggi della matematica (nello specifico, creerebbe un'impossibilità matematica riguardante il modo in cui i numeri si dividono). Questo ha dimostrato che la sequenza non è un semplice ciclo e ha già mostrato che era più complessa del pattern più semplice non ciclico.
Fase 1 (La Riduzione): Si sono resi conto che, per dimostrare che la sequenza è estremamente complessa, dovevano solo dimostrare una cosa specifica: che i numeri nella sequenza non si avvicinano "troppo" tra loro troppo spesso. Se rimanessero lontani, il codice sarebbe stato costretto a essere disordinato e complesso.
Fase 2 (La Cima): Hanno usato quegli strumenti matematici pesanti per dimostrare che i numeri rimangono effettivamente lontani. Hanno diviso il problema in tre zone:
- La Zona dei Piccoli Gap: Quando i numeri sono vicini tra loro nella sequenza.
- La Zona dei Grandi Gap: Quando i numeri sono molto lontani tra loro nella sequenza.
- La Zona Intermedia: L'area complicata nel mezzo.

Per le prime due zone, hanno usato un teorema potente. Per la zona intermedia, hanno usato un trucco intelligente (una "dicotomia") che mostrava come, se il pattern avesse cercato di essere semplice, ciò avrebbe portato a una contraddizione (come dimostrare che una frazione è in realtà un numero intero, il che è impossibile).

In Sintesi
La parola di guida per la sequenza (3/2) è un capolavoro caotico e non ripetitivo. È così complessa che il numero di pattern unici che contiene cresce più velocemente di qualsiasi linea retta. Questa non è una suggestione o una simulazione; è un fatto matematicamente dimostrato, ricontrollato da un computer, che mostra come una regola apparentemente semplice generi una danza di numeri infinitamente intricata.

Sintesi Tecnica: Complessità Superlineare della Parola di Guida $(3/2)^n$

Enunciato del Problema
Il saggio investiga la dinamica simbolica generata dall'orbita del numero 1 sotto la mappa $x \mapsto \frac{3}{2}x$ , concentrandosi specificamente sulla sequenza degli errori di arrotondamento al numero intero più vicino. Mentre la distribuzione della sequenza $\|(\frac{3}{2})^n\|$ (distanza dall'intero più vicino) è un problema aperto di lunga data nella teoria dei numeri, questo lavoro sposta l'attenzione sulla "parola di guida" (steering word) $T = (t_n)_{n \geq 0}$ . Questa parola registra le traslazioni intere selezionate ad ogni passo della dinamica autonoma, definita come $t_n = 2m_{n+1} - 3m_n$ , dove $m_n = \text{round}((\frac{3}{2})^n)$ . La questione centrale affrontata è la complessità dei sottoparole $p_T(k)$ , che conta il numero di fattori distinti di lunghezza $k$ in $T$ . Il saggio mira a dimostrare che tale complessità è superlineare, ovvero $\lim_{k \to \infty} p_T(k)/k = \infty$ .

Metodologia
La strategia di dimostrazione è strutturata in tre fasi distinte, trasferendo i metodi dallo studio della complessità dei numeri algebrici (specificamente il metodo Adamczewski–Bugeaud) a questo contesto dinamico. L'argomento si basa pesantemente sul Teorema dello Spazio Sottile (Subspace Theorem) ed è indicato come pienamente formalizzato in Lean-4.

Fase 0: Identità Esatte e Limiti Incondizionati (Sezioni 2)
L'autore deriva un'identità di ripetizione esatta. Se un fattore di lunghezza $k$ si ripete nelle posizioni $a$ e $c$ ( $a < c$ ), ciò impone la relazione $3^k(\varepsilon_c - \varepsilon_a) = 2^k(\varepsilon_{c+k} - \varepsilon_{a+k})$ , dove $\varepsilon_n$ è l'errore di arrotondamento.
- Questa identità produce una condizione di divisibilità: $2^k \mid (m_c - m_a)$ .
- Combinata con le proprietà di crescita dell'orbita, ciò stabilisce che le lunghe ripetizioni non possono verificarsi arbitrariamente tardi nella parola.
- Risultato Incondizionato: Il saggio dimostra che $T$ non è eventualmente periodica e stabilisce un limite inferiore lineare $p_T(k) \geq \frac{41}{24}k - 3$ , che è strettamente superiore al limite di Morse–Hedlund ( $k+1$ ) per parole aperiodiche.
Fase 1: Riduzione a un Nucleo Diofantico (Sezione 3)
Il problema di dimostrare la complessità superlineare viene ridotto a una singola affermazione diofantica, definita come il Nucleo (K).
- Affermazione (K): Per ogni razionale $\theta \in (0, 1)$ , l'insieme delle coppie $(a, c)$ con $2 \leq a < c$ che soddisfano $\|(\frac{3}{2})^c - (\frac{3}{2})^a\| \leq \theta^c$ è finito.
- Questo rappresenta una proprietà di "repulsione esponenziale delle coppie", migliorando il limite inferiore banale della distanza tra i punti dell'orbita dalla base $2^{-1}$ a un'arbitraria base $\theta < 1$ .
- La riduzione mostra che se (K) è verificata, allora $p_T(k)/k \to \infty$ .
Fase 2: Stabilire il Nucleo (Sezioni 4 e 5)
La dimostrazione di (K) viene ottenuta partizionando l'insieme delle potenziali soluzioni in tre "fette" (slices) e applicando risultati profondi dell'approssimazione diofantica:
- Fetta a Gap Limitato (Bounded Gap Slice): Per gap fissi $c-a$ , la finitezza è dimostrata utilizzando il Teorema Principale di Corvaja–Zannier (una conseguenza del Teorema dello Spazio Sottile di Schmidt).
- Fetta a Gap Enorme (Huge-Gap Slice): Per la regione in cui $a \leq \epsilon' c$ , la finitezza è stabilita anch'essa tramite il teorema di Corvaja–Zannier, trattando il problema come un caso specifico di esclusione pseudo-Pisot.
- Fascia Centrale (Middle Band): Per la regione rimanente dove i gap crescono ma $a$ non è trascurabile rispetto a $c$ , l'autore impiega una dicotomia di gap. Se l'insieme delle soluzioni fosse infinito, si potrebbe estrarre una sottofamiglia con gap distinti. Ciò conduce a una contraddizione tramite il teorema S-unit tuple di Nair–Kumar–Rout, che implicherebbe che $(\frac{3}{2})^c$ sia un intero per qualche $c$ , un'impossibilità.

Contributi Chiave e Risultati

Teorema Principale (Teorema 1.1): La complessità delle sottoparole della parola di guida $T$ è superlineare ( $p_T(k)/k \to \infty$ ).
Limite Inferiore Incondizionato: Il saggio fornisce un limite inferiore lineare esplicito e incondizionato $p_T(k) \geq \frac{41}{24}k - 3$ , derivato senza fare affidamento su congetture non provate.
Formalizzazione: L'intero argomento è formalizzato in Lean-4. La formalizzazione dipende solo dal Teorema dello Spazio Sottile di Evertse–Schlickewei in 3 variabili, confermando così la correttezza delle dipendenze dai risultati di Corvaja–Zannier e Nair–Kumar–Rout.
Aperiodicità: Una prova rigorosa che la parola di guida non è eventualmente periodica.

Significato e Rivendicazioni
Il saggio sostiene di risolvere la questione della complessità per questo specifico sistema dinamico autonomo collegando la dinamica simbolica all'approssimazione diofantica.

Trasferimento Metodologico: Esso adatta con successo il metodo Adamczewski–Bugeaud, tipicamente usato per i numeri algebrici, a una parola dinamica. L'autore nota che la natura autonoma della dinamica $(3/2)$ semplifica la gestione contabile, permettendo ai fattori ripetuti di comprimersi in pulite disuguaglianze diofantiche senza necessità di ancoraggio al prefisso.
Dipendenza da Teoremi Profondi: La dimostrazione della superlinearità è condizionata al teorema di Corvaja–Zannier (revisionato tra pari) e al teorema di Nair–Kumar–Rout (un preprint al momento della stesura). Tuttavia, la formalizzazione in Lean-4 funge da verifica che queste dipendenze sono conseguenze logicamente solide del Teorema dello Spazio Sottile.
Limitazioni: I risultati riguardanti la crescita superlineare sono inefficaci; il Teorema dello Spazio Sottile non fornisce limiti espliciti sulla dimensione degli insiemi eccettuionali (il numero di soluzioni alle disuguaglianze diofantiche). Il saggio non pretende di risolvere il problema aperto più ampio riguardante la densità di $\|(\frac{3}{2})^n\| \to 0$ , bensì caratterizza la complessità combinatoria della sequenza di arrotondamento.

Articoli simili