Rationality and computability of the covering radius for sofic shifts

1. Il Problema

Il lavoro si concentra sul raggio di copertura (covering radius) degli spazi di shift, in particolare per i shift sofic primitivi.

• Contesto: Il raggio di copertura è una quantità fondamentale nella teoria dell'informazione, specialmente per la trasmissione di dati su canali rumorosi e per la correzione degli errori in sistemi vincolati (constrained coding).
• Definizione: Per un codice $C \subseteq \{0,1\}^n$, il raggio di copertura è il minimo $R$ tale che ogni parola di lunghezza $n$ sia a distanza di Hamming al più $R$ da qualche parola in $C$. Per uno spazio di shift $X$, il raggio di copertura è definito come il limite (inferiore o superiore) della normalizzazione del raggio di copertura dei linguaggi finiti $C_n(X)$ quando $n \to \infty$.
• Domanda di ricerca: Sebbene il raggio di copertura fosse stato calcolato in casi specifici (es. shift a lunghezza di corsa limitata) e si fosse osservato che era sempre un numero razionale, non era noto se questo fosse vero in generale per tutti gli shift sofic primitivi, né se esistesse un algoritmo generale per calcolarlo.

2. Metodologia

Gli autori adottano un approccio che combina la teoria degli spazi di shift, la teoria dei giochi e l'algebra dei semianelli tropicali.

A. Formulazione come Gioco a Somma Zero

Il problema viene riformulato come un gioco a somma zero a due giocatori (Alice e Bob) con payoff medio (mean-payoff game):

• Alice sceglie un cammino (walk) $p$ di lunghezza $n$ su un grafo $H$ (che rappresenta l'alfabeto o il canale).
• Bob, conoscendo la scelta di Alice, sceglie un cammino $q$ di lunghezza $n$ su un grafo $G$ (che rappresenta lo shift sofic).
• Il payoff è la somma delle distanze di Hamming tra i label dei cammini scelti.
• Il valore del gioco $V(G, H, P)$ corrisponde al raggio di copertura dello shift.

B. Convoluzione Tropica e Funzioni Massimali

Per analizzare la struttura combinatoria del gioco, gli autori introducono un'operazione chiamata convoluzione tropicale su funzioni a valori interi definiti su coppie di vertici:
$$(f * g)(u, w) = \min_{v \in E} (f(u, v) + g(v, w))$$
Questa operazione è associativa e permette di modellare la concatenazione dei cammini nel gioco.

• Vengono definite funzioni $M(p)$ che rappresentano il payoff minimo garantito da Bob contro una scelta specifica di Alice.
• Si studiano le funzioni massimali (rispetto all'ordine parziale puntuale) tra le possibili strategie, identificando i cammini "non migliorabili" (non-improvable walks).

C. Teoria Ergodica e Spazi di Shift Ottimali

Gli autori definiscono spazi di shift $X^\dagger_H$ e $Y^\dagger_{(H,G)}$ che contengono le strategie ottimali (periodiche o quasi-periodiche) per i giocatori. Dimostrano che questi spazi sono essi stessi shift sofic, permettendo l'uso di strumenti della dinamica simbolica.

3. Risultati Chiave e Contributi

Teorema A: Razionalità

Enunciato: Il raggio di copertura di uno shift sofic primitivo è sempre un numero razionale.

• Significato: Questo risolve una congettura aperta basata su esempi precedenti, dimostrando che la complessità combinatoria degli shift sofic non genera valori irrazionali per questo parametro specifico.

Teorema B: Computabilità

Enunciato: Esiste un algoritmo che, dato un grafo etichettato primitivo $G$, calcola il raggio di copertura $R(X_G)$ in tempo finito.

• Meccanismo: L'algoritmo si basa sulla proprietà che la sequenza dei valori del gioco $V_n$ diventa eventualmente periodica (o quasi-periodica) con un periodo e un incremento costanti, permettendo di determinare il limite esatto dopo un numero finito di passi.

Teorema C: Valore del Gioco

Il risultato fondamentale che sottende A e B è che per grafi primitivi $G, H$ e una funzione di payoff $P$, il valore del gioco $V(G, H, P)$ è razionale e calcolabile.

Teorema F: Struttura degli Spazi di Strategie

Gli spazi di strategie ottimali $X^\dagger_H$ e $Y^\dagger_{(H,G)}$ sono shift sofic.

• Questo risultato è cruciale perché garantisce che le strategie ottimali possano essere descritte da grafi finiti, confermando l'esistenza di strategie periodiche che realizzano il valore del gioco (Corollario 5.4).

4. Significato e Implicazioni

1. Teoria dell'Informazione: Il lavoro fornisce una base teorica solida per la progettazione di codici correttori per sistemi vincolati. Sapere che il raggio di copertura è razionale e calcolabile permette di ottimizzare i parametri di trasmissione dati in scenari reali (es. memorizzazione magnetica o ottica).
2. Dinamica Simbolica: Il paper collega profondamente la teoria degli shift sofic con la teoria dei giochi a somma zero e la dinamica simbolica, mostrando come proprietà globali (come il raggio di copertura) possano essere dedotte da strutture locali (grafi e convoluzioni).
3. Metodologia Innovativa: L'uso della "convoluzione tropicale" e l'analisi degli spazi di strategie ottimali come shift sofic offrono nuovi strumenti per affrontare problemi di ottimizzazione in sistemi dinamici.
4. Limiti e Domande Aperte:
   • I risultati sono attualmente validi per grafi primiti. Gli autori notano che per grafi riducibili la situazione è più complessa, sebbene si sospetti che la razionalità possa essere estesa tramite decomposizione periodica.
   • Rimane aperta la questione della computabilità e della razionalità se la funzione di payoff assume valori reali (non solo interi o razionali).

In sintesi, il paper risolve definitivamente la questione della razionalità e della calcolabilità del raggio di copertura per la classe fondamentale degli shift sofic primitivi, fornendo sia una prova teorica che un metodo costruttivo per il calcolo.