Proving Properties of $φ$-Representations with the Walnut Theorem-Prover

Il paper rivede un classico teorema sulle rappresentazioni $\phi$-basate utilizzando il dimostratore Walnut per ottenere una prova computazionale diretta, permettendo di derivare in modo uniforme e automatico sia risultati noti che nuovi, senza ricorrere all'induzione.

L'essenziale

Ecco una spiegazione del lavoro di Jeffrey Shallit, "Proving Properties of φ-Representations with the Walnut Theorem-Prover", tradotta in un linguaggio semplice e quotidiano, con l'aiuto di alcune metafore creative.

Il Grande Mistero dei Numeri d'Oro

Immagina di avere un numero magico, chiamato $\phi$ (phi), che è la famosa "Sezione Aurea" ($\approx 1,618$). Di solito, scriviamo i numeri usando la base 10 (con le cifre da 0 a 9) o la base 2 (solo 0 e 1, come nei computer). Ma cosa succederebbe se provassimo a scrivere i numeri usando solo la Sezione Aurea come base?

È come se avessimo un nuovo alfabeto matematico. In questo sistema, ogni numero può essere scritto come una somma di potenze di $\phi$. Ad esempio, il numero 2 non è scritto come "10" (in binario) o "2" (in decimale), ma come una stringa di 0 e 1 che sembra un codice segreto: 10.01 o 1.11.

Il problema è che ci sono molti modi diversi per scrivere lo stesso numero in questo sistema. È come se potessi dire "ciao" in italiano, "ciao" in francese, o "hello" in inglese. Ma per la matematica, serve un modo "ufficiale" e unico, chiamato rappresentazione canonica.

Il Problema: Trovare la Regola del Gioco

Per decenni, i matematici hanno cercato di capire le regole per trasformare un numero intero (come 43) nella sua forma "ufficiale" in base $\phi$. Nel 2005, due ricercatori, Frougny e Sakarovitch, hanno scoperto che esiste una macchina automatica (un automa) che può fare questo lavoro: prende un numero, lo guarda e decide se la scrittura è corretta o no.

Tuttavia, la loro macchina era descritta in modo così complicato e astratto che era quasi impossibile da vedere o da usare. Era come se avessero detto: "C'è un robot che risolve il problema", ma senza dare il manuale di istruzioni o mostrare il robot.

La Soluzione: Walnut, il "Detective Matematico"

Jeffrey Shallit, l'autore di questo articolo, ha usato uno strumento software gratuito chiamato Walnut.
Immagina Walnut non come un semplice calcolatore, ma come un investigatore super-intelligente o un traduttore universale.

Ecco come funziona la sua magia:

1. La Domanda: Shallit scrive una domanda in un linguaggio logico semplice (quasi come una frase in inglese) che descrive le regole della rappresentazione in base $\phi$.
2. L'Investigazione: Walnut analizza la domanda. Invece di fare calcoli a mano (che sarebbero infiniti), Walnut costruisce automaticamente la "macchina" (l'automa) che risolve il problema.
3. La Risposta: Walnut non solo costruisce la macchina, ma la usa per verificare se certe affermazioni sono vere o false, e persino per scoprire nuove regole che nessuno aveva mai notato prima.

Cosa ha Scoperto Shallit?

Usando questo "detective", Shallit ha fatto tre cose principali:

1. Ha ricostruito la macchina perduta: Ha preso le idee confuse di Frougny e Sakarovitch e le ha trasformate in un diagramma chiaro e visibile. Ora possiamo vedere esattamente come la macchina "pensa" e decide se un numero è scritto correttamente.
2. Ha risolto vecchi enigmi senza fatica: Molti matematici avevano passato anni a scrivere lunghe dimostrazioni (basate su "induzioni", che sono come scale infinite da salire passo dopo passo) per provare certe proprietà. Shallit ha usato Walnut per dire: "Ehi, la macchina lo fa da sola!" e ha ottenuto le stesse prove in pochi secondi, senza bisogno di scalare la scala.
3. Ha trovato nuovi tesori: Mentre Walnut lavorava, ha scoperto cose nuove. Per esempio:
   • Ha capito esattamente quali numeri hanno rappresentazioni che sono palindromi (che si leggono allo stesso modo da sinistra a destra e viceversa, come "101").
   • Ha scoperto quante volte appare il numero "1" in queste rappresentazioni.
   • Ha analizzato i "blocchi" di 1 consecutivi (come "111") e ha scoperto che seguono schemi sorprendenti legati ai numeri di Fibonacci (quella sequenza 1, 1, 2, 3, 5, 8... che trovi nelle conchiglie e nei girasoli).

Perché è Importante?

Pensa a questo lavoro come alla costruzione di un ponte.
Prima, per attraversare il fiume della matematica complessa (le rappresentazioni in base $\phi$), dovevi nuotare a fatica o costruire ponti di legno instabili (le lunghe dimostrazioni manuali).
Ora, grazie a Walnut, abbiamo un ponte d'acciaio solido e automatico.

Questo significa che:

• Possiamo verificare teoremi in modo automatico e infallibile.
• Possiamo scoprire nuove proprietà dei numeri che prima erano nascoste nella nebbia.
• Possiamo applicare queste tecniche non solo alla Sezione Aurea, ma a molti altri sistemi numerici esotici.

In Sintesi

Jeffrey Shallit ha preso un mistero matematico vecchio di vent'anni, ha usato un software intelligente (Walnut) come un "super-assistente" per costruire una mappa chiara del territorio, e ha dimostrato che molte delle regole complesse possono essere scoperte e provate in modo semplice e diretto, come se fossero un gioco di logica piuttosto che un'ardua battaglia matematica.

È come se avesse dato a tutti noi gli occhiali da mago per vedere la bellezza nascosta dietro i numeri d'oro.

Sommario tecnico

Ecco un riassunto tecnico dettagliato del paper "Proving Properties of φ-Rappresentazioni con il Theorem-Prover Walnut" di Jeffrey Shallit, redatto in italiano.

1. Introduzione e Problema

Il paper si concentra sulle rappresentazioni in base $\phi$ (dove $\phi = (1+\sqrt{5})/2$ è il numero aureo), un'estensione del sistema di numerazione di Zeckendorf ai numeri reali non negativi. Una rappresentazione canonica di un numero $z$ in base $\phi$ è una stringa di cifre binarie $a_i \in \{0, 1\}$ tale che $z = \sum a_i \phi^i$, con il vincolo di non avere due "1" consecutivi (nessun blocco "11").

Il problema centrale affrontato è la verifica e la generalizzazione di teoremi riguardanti queste rappresentazioni, in particolare quelli legati all'automatismo computazionale. Un risultato fondamentale precedente, dovuto a Frougny e Sakarovitch (2009), afferma che l'insieme delle rappresentazioni canoniche degli interi non negativi in base $\phi$ è riconoscibile da un automata finito. Tuttavia, la costruzione originale di tale automa era complessa, non esplicitamente presentata nel dettaglio e difficile da utilizzare per derivare nuove proprietà in modo sistematico.

L'obiettivo del paper è fornire una costruzione esplicita e computazionale di questo automa e utilizzarlo per:

1. Riprovare in modo semplice e uniforme risultati esistenti nella letteratura (in particolare lavori recenti di Dekking e Van Loon).
2. Derivare nuovi teoremi e sequenze numeriche relative alle rappresentazioni in base $\phi$.

2. Metodologia: L'Approccio Computazionale con Walnut

La metodologia principale del paper si basa sull'uso di Walnut, un software open-source sviluppato da Hamoon Mousavi e Shallit, che funge da "theorem-prover" per sequenze automatiche.

• Logica del Primo Ordine: L'autore esprime le proprietà delle rappresentazioni $\phi$ come formule nella logica del primo ordine.
• Decision Procedure: Walnut utilizza una procedura decisionale per un'estensione dell'aritmetica di Presburger, specifica per le sequenze automatiche (in questo caso, sequenze legate ai numeri di Fibonacci).
• Costruzione di Automi: Se una formula contiene variabili libere, Walnut calcola automaticamente un automa finito che accetta esattamente i valori di quelle variabili per cui la formula è vera.
• Rappresentazioni Multiple: Il paper utilizza due sistemi di numerazione per gli interi:
  • Sistema di Zeckendorf: Per gli interi non negativi ($n = \sum a_i F_i$).
  • Sistema NegaFibonacci: Per gli interi (positivi, negativi o zero) ($n = \sum a_i F_{-i}$).
• Composizione di Automi: L'automa principale di Frougny-Sakarovitch viene costruito componendo automi più piccoli e semplici (normalizzatori, shifters, estrattori di bit) definiti tramite espressioni regolari e logica.

3. Costruzione dell'Automa di Frougny-Sakarovitch

Il cuore del lavoro è la costruzione esplicita dell'automa che verifica se $n = [x.y]_\phi$.

• L'automa prende in input tre stringhe in parallelo: $w$ (rappresentazione di Zeckendorf di $n$), $x$ (parte intera della rappresentazione $\phi$) e $y^R$ (parte frazionaria invertita).
• Sfruttando l'identità $\phi^k = F_k \phi + F_{k-1}$, l'automa scompone la somma in una parte lineare in $\phi$ e una parte costante.
• Le condizioni di validità ($c' = -c$ e $n = d + d'$) vengono verificate tramite automi intermedi.
• Il risultato è un automa di 116 stati (riducibile a 39 stati se si impone la canonicità, ovvero l'assenza di "11").

4. Risultati Chiave e Contributi

Utilizzando questo automa, Shallit ottiene una serie di risultati, molti dei quali sono dimostrati in modo "automatico" senza induzioni manuali complesse.

A. Riprova di Risultati Esistenti

• Rappresentazioni di Fibonacci e Lucas: Viene fornita una prova automatica delle forme canoniche delle rappresentazioni $\phi$ dei numeri di Fibonacci ($F_n$) e di Lucas ($L_n$), confermando risultati di Frougny-Sakarovitch e Dekking-Van Loon.
• Espansioni di Knott: Vengono enumerate le "espansioni di Knott" (rappresentazioni che non terminano in 011). L'autore recupera i risultati complessi di Dekking e Van Loon sul numero di tali espansioni ($Tot_\kappa(n)$) e fornisce una rappresentazione lineare che permette un calcolo efficiente $O(\log n)$.
• Espansioni "Naturali" e DVL: Vengono analizzate le espansioni "naturali" (dove la lunghezza della parte frazionaria è uguale a quella della parte intera) e le "DVL-expansions" (una variante canonica definita da Dekking e Van Loon), ottenendo risultati su di esse in modo sistematico.

B. Nuovi Risultati e Teoremi

• Congettura di Gerdemann (2012): Viene dimostrata la congettura secondo cui la somma delle cifre nella rappresentazione di Zeckendorf di $n$ è sempre minore o uguale alla somma delle cifre nella sua rappresentazione canonica in base $\phi$. La prova utilizza un algoritmo di cammino minimo (Bellman-Ford) su un grafo derivato dall'automa.
• Lunghezza delle Rappresentazioni: Viene studiata la lunghezza della parte intera $\ell(n)$, dimostrando che la differenza $\ell(n) - \ell(n-1)$ è una sequenza automatica di Fibonacci e caratterizzando esattamente quando tale differenza è 1.
• Bit Individuali: Vengono caratterizzati i singoli bit delle rappresentazioni $\phi$ (es. $d_0(n)$, $d_1(n)$, $d_{-1}(n)$). In particolare, viene mostrato che $d_{-1}(n) = 1$ se e solo se $n$ ammette esattamente due distinte rappresentazioni come somma di numeri di Lucas.
• Sequenze Palindromiche e Anti-palindromiche: Vengono costruiti automi per identificare i numeri $n$ le cui rappresentazioni $\phi$ sono palindromiche o anti-palindromiche, generando nuove sequenze numeriche (es. A362780, A362781).
• Rappresentazioni per Interi Algebrici: Il metodo viene esteso per gestire numeri della forma $m\phi + n$ (interi algebrici in $\mathbb{Z}[\phi]$), permettendo di verificare proprietà come l'uguaglianza delle lunghezze delle parti intera e frazionaria.

5. Significato e Impatto

Il lavoro di Shallit ha un significato profondo per la teoria dei numeri computazionale e la teoria degli automi:

1. Democratizzazione della Complessità: Trasforma problemi matematici complessi e "difficili da leggere" (come la costruzione originale di Frougny-Sakarovitch) in procedure algoritmiche standardizzabili.
2. Unificazione: Offre un quadro unificato per trattare diverse varianti di rappresentazioni in base $\phi$ (Zeckendorf, NegaFibonacci, Knott, DVL, ecc.) utilizzando lo stesso strumento logico.
3. Scoperta Automatica: Dimostra che è possibile "scoprire" nuovi teoremi e sequenze (come quelle relative alle somme di cifre o alle lunghezze) semplicemente cambiando i vincoli logici forniti a Walnut, senza bisogno di nuove intuizioni matematiche profonde manuali.
4. Riproducibilità: Fornisce il codice Walnut esatto per ogni risultato, rendendo le dimostrazioni verificabili e riproducibili da altri ricercatori.

In sintesi, il paper non solo risolve problemi aperti, ma stabilisce un nuovo paradigma metodologico: l'uso di theorem-prover basati su automi per esplorare e provare proprietà di sistemi di numerazione non standard, trasformando la ricerca di pattern in un processo computazionale diretto.