Additive systems for $\mathbb{Z}$ are undecidable

1. Il Problema

Il lavoro si concentra sulla classificazione e sulla decidibilità dei sistemi additivi per l'insieme degli interi $\mathbb{Z}$.
Un sistema additivo per un monoide commutativo $M$ (in questo caso $\mathbb{Z}$) è una collezione di sottoinsiemi $A = \{A_0, A_1, \dots\}$ tale che ogni elemento $n \in M$ possa essere rappresentato in modo unico come somma finita $n = a_0 + a_1 + \dots + a_k$, dove $a_i \in A_i$.

Mentre la situazione per gli interi non negativi $\mathbb{N}_0$ è ben compresa grazie al Teorema di de Bruijn (che stabilisce che ogni sistema additivo per $\mathbb{N}_0$ è una contrazione di un "sistema numerico britannico"), il problema per $\mathbb{Z}$ è notoriamente difficile e non ammette una caratterizzazione completa analoga. L'obiettivo principale del paper è determinare se, data una specifica classe di collezioni per $\mathbb{Z}$, sia possibile decidere se esse costituiscono un sistema additivo completo (ovvero se la loro somma diretta copre tutto $\mathbb{Z}$).

2. Metodologia

L'autore adotta un approccio interdisciplinare che combina la combinatoria additiva con la teoria dei sistemi dinamici e la teoria della computabilità.

• Definizione di "Collezioni Canoniche": Viene introdotta una nuova famiglia di collezioni chiamate collezioni canoniche. Queste sono definite da due sequenze: una sequenza di basi $(b_i)_{i \in \mathbb{N}_0}$ (interi $>1$) e una sequenza di sistemi di residui completi $(T_i)_{i \in \mathbb{N}_0}$ modulo $b_i$, contenenti lo 0. La collezione ha la forma:
  $$\{T_0, b_0T_1, b_0b_1T_2, b_0b_1b_2T_3, \dots\}$$
  Questa definizione generalizza i sistemi numerici posizionali (come il binario o il ternario bilanciato) e i sistemi britannici a basi variabili.

• Traslazione in Sistemi Dinamici: Il cuore della metodologia consiste nel tradurre il problema della copertura di $\mathbb{Z}$ in un problema di dinamica. Per ogni numero intero $n$, l'autore definisce una mappa $f_i(n)$ che estrae il "cifra" corrispondente alla base $b_i$ e riduce il numero.
  La mappa è definita come:
  $$f_i(n) = \frac{1}{b_i}(n - t_i(n))$$
  dove $t_i(n)$ è l'unico elemento in $T_i$ congruo a $n$ modulo $b_i$.
  La rappresentazione di $n$ come somma esiste ed è unica se e solo se la traiettoria di $n$ sotto l'iterazione di queste mappe ($n, f_0(n), f_1(f_0(n)), \dots$) converge a 0 dopo un numero finito di passi.

• Riduzione a Problemi Indecidibili: L'autore costruisce collezioni canoniche specifiche in cui le mappe $f_i$ simulano il comportamento di algoritmi computazionali noti per essere indecidibili o aperti.

3. Contributi Chiave e Risultati

Il paper presenta tre risultati fondamentali (Teorema 1, Teorema 2 e Corollario 2):

A. Equivalenza con la Congettura di Collatz (Teorema 1)

L'autore dimostra l'esistenza di una collezione canonica specifica $A_C$ tale che:

$A_C$ è un sistema additivo completo per $\mathbb{Z}$ se e solo se la Congettura di Collatz è vera.

• Meccanismo: La collezione è costruita in modo che la dinamica delle mappe $f_i$ riproduca esattamente la traiettoria di Collatz ($3n+1$ se dispari, $n/2$ se pari) per gli interi positivi. La completezza del sistema richiede che ogni traiettoria raggiunga 0, il che equivale a dire che ogni numero positivo entra nel ciclo $1 \to 4 \to 2 \to 1$ (e quindi la mappa si azzera).
• Implicazione: Determinare se una specifica collezione canonica è completa è almeno tanto difficile quanto risolvere la Congettura di Collatz.

B. Indecidibilità tramite Fractran (Teorema 2 e Corollario 2)

Utilizzando il linguaggio di programmazione esoterico Fractran (introdotto da John Conway e dimostrato essere computazionalmente universale), l'autore costruisce una famiglia "ben comportata" di collezioni canoniche, chiamate collezioni di tipo Fractran.

• Risultato: Esiste una collezione canonica $A_F$ associata a un programma Fractran $F$ tale che:

  $A_F$ è completa se e solo se il programma Fractran $F$ si arresta per tutti gli input.

• Conclusione: Poiché il problema dell'arresto universale per Fractran è indecidibile (non esiste un algoritmo che possa determinare se un programma arbitrario si fermerà su tutti gli input), ne consegue che il problema di determinare se una collezione canonica (di tipo Fractran) è un sistema additivo completo è indecidibile.

4. Significato e Implicazioni

1. Complessità Intrinseca: Il lavoro dimostra che il problema della completezza dei sistemi additivi su $\mathbb{Z}$ non è solo difficile, ma possiede una complessità computazionale estrema. Non esiste un algoritmo generale per decidere se una collezione canonica copre $\mathbb{Z}$.
2. Ponte tra Discipline: Il paper stabilisce un collegamento sorprendente e diretto tra la teoria dei numeri (sistemi di numerazione e partizioni additive) e la teoria della computabilità (problemi di arresto e congetture aperte).
3. Limiti della Caratterizzazione: Mentre per $\mathbb{N}_0$ esiste un teorema di caratterizzazione completo (de Bruijn), per $\mathbb{Z}$ non esiste un analogo "semplice". Anche restringendosi a collezioni definite da dati finiti (come nel caso Fractran), la proprietà di completezza sfugge a qualsiasi procedura algoritmica.
4. Nuovi Strumenti: L'introduzione delle "collezioni canoniche" e la loro interpretazione come sistemi dinamici non autonomi offrono un nuovo framework potente per analizzare problemi di copertura e tiling su gruppi abeliani.

In sintesi, Zabolotskii dimostra che la domanda "questa collezione di insiemi genera tutti gli interi in modo unico?" è, in casi specifici costruiti ad hoc, equivalente a risolvere uno dei problemi più famosi della matematica (Collatz) o a risolvere il problema dell'arresto, rendendo la questione formalmente indecidibile.