🔢 mathematics

Sharper upper bounds for $q$ -ary $B_2$ codes from Toeplitz SDPs

Questo lavoro migliora i limiti superiori sulla capacità dei codici $q$ -ari $B_2$ sfruttando la struttura analitica di Fourier della distribuzione di differenza tra variabili casuali per formulare un problema di ottimizzazione convessa risolta tramite SDP Toeplitz troncati.

Autori originali: Stefano Della Fiore

Pubblicato 2026-03-31

📖 4 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Stefano Della Fiore

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.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

Il Problema: Costruire una "Cassaforte" Perfetta

Immagina di dover creare un sistema di codici segreti (come delle chiavi di una cassaforte) per un mondo dove le chiavi sono fatte di numeri da 0 a $q-1$ .
L'obiettivo è creare quante più chiavi possibili (massimizzare il numero di codici) mantenendo una regola d'oro: nessuna somma di due chiavi deve mai coincidere con la somma di altre due chiavi diverse.

Se due coppie di chiavi diverse producono la stessa somma, il sistema si rompe perché non puoi più distinguere chi ha aperto cosa. Questi codici speciali si chiamano codici B2.

Il problema per i matematici è: "Quante chiavi possiamo creare al massimo prima di rompere la regola?" La risposta è espressa come un "tasso" (una percentuale di efficienza). Più alto è il tasso, più efficiente è il codice.

La Vecchia Strategia: Guardare solo il "Scontro"

In un lavoro precedente, gli autori avevano cercato di trovare il limite massimo di queste chiavi usando un approccio un po' "grezzo".
Immagina di avere due persone che scelgono casualmente una chiave.
La vecchia strategia si chiedeva: "Qual è la probabilità che queste due persone scelgano esattamente la stessa chiave?"
Sapevano che questa probabilità doveva essere almeno $1/q$ (come dire: se ci sono 10 colori, c'è almeno il 10% di possibilità che due persone scelgano lo stesso colore).
Basandosi solo su questo "scontro" (collisione), hanno calcolato un limite teorico. Era un buon limite, ma un po' approssimativo, come misurare la distanza tra due città guardando solo la linea retta su una mappa, senza considerare le curve della strada.

La Nuova Strategia: La "Musica" delle Differenze

In questo nuovo articolo, l'autore, Stefano Della Fiore, dice: "Aspetta, stiamo guardando solo un pezzo del puzzle. Dobbiamo ascoltare l'intera musica!"

Ecco l'analogia:
Immagina che ogni differenza tra due chiavi (il numero che ottieni sottraendo una chiave dall'altra) sia una nota musicale.
La vecchia strategia guardava solo quanto spesso la nota era "silenzio" (quando le due chiavi erano uguali).
La nuova strategia osserva l'intera melodia.

La Melodia (Analisi di Fourier): Quando sottrai due chiavi, la distribuzione delle differenze non è casuale. Ha una struttura matematica precisa, come un'onda sonora. Questa onda deve essere sempre "positiva" (non può avere valori negativi che non hanno senso fisico).
Il Filtro Magico (Matrici di Toeplitz): Per assicurarsi che questa melodia sia reale e possibile, gli autori usano un filtro matematico molto potente chiamato Matrici di Toeplitz. È come un setaccio che controlla se la melodia è coerente in ogni suo punto, non solo nel silenzio iniziale.

Il Risultato: Un Limite Più Stretto

Usando questa "musica" completa e il filtro magico, gli autori riescono a dimostrare che la "confusione" (l'entropia) tra le chiavi è meno di quanto pensassero prima.

Prima: Pensavamo che il codice potesse essere un po' più grande (il limite era più alto).
Ora: Dimostriamo che il codice deve essere un po' più piccolo di quanto speravamo (il limite è più basso e preciso).

È come se prima avessimo detto: "In questa stanza possono stare al massimo 100 persone".
Ora, analizzando meglio l'architettura della stanza (le pareti, le porte, la struttura), diciamo: "In realtà, per sicurezza, possono stare al massimo 95 persone". Il nuovo limite è più sicuro e più preciso.

Perché è importante?

L'articolo mostra che per certi numeri (da 9 a 13), questo nuovo metodo batte tutti i record precedenti.
In pratica, hanno trovato un modo più intelligente per "contare" le possibilità, sfruttando la bellezza della matematica (le onde e le frequenze) invece di usare solo la statistica di base.

In sintesi:
Hanno preso un problema di crittografia, hanno smesso di guardare solo l'urto tra due oggetti e hanno iniziato ad ascoltare la "canzone" che questi oggetti creano quando si muovono. Questo ha permesso loro di scrivere una regola più precisa su quanto possono essere grandi i nostri codici segreti.

1. Il Problema

Il lavoro si concentra sulla determinazione di limiti superiori asintotici per il tasso (rate) dei codici B2 q-ari.

Definizione di Codice B2: Un codice $C_n \subset \{0, \dots, q-1\}^n$ è definito come codice B2 se tutte le somme (sui reali) di coppie di codeword $c_i + c_j$ (con $1 \le i \le j \le M$ ) sono distinte. Per $q=2$ , questa definizione equivale a quella dei codici 2-separabili.
Obiettivo: Trovare il limite superiore del tasso asintotico $R = \limsup_{n \to \infty} \frac{1}{n} \log_q |C_n|$ .
Contesto: I limiti esistenti in letteratura (es. Lindström, Wang, e lavori precedenti dello stesso autore) sono stati derivati utilizzando metodi di teoria dell'informazione basati su entropia, ma spesso si basano su rilassamenti "grossolani" delle distribuzioni di probabilità coinvolte.

2. Metodologia

L'autore raffina il passaggio chiave nella derivazione dei limiti di tasso, che consiste nel controllare l'entropia della differenza $D = X - Y$ di due variabili aleatorie q-arie indipendenti e identicamente distribuite (i.i.d.) $X$ e $Y$ .

Approccio Tradizionale vs. Nuovo Approccio

Approccio Precedente [5]: Si massimizzava l'entropia $H(X-Y)$ sotto il vincolo unico che la probabilità di collisione fosse $P(X=Y) \ge 1/q$ . Questo portava a un limite superiore chiuso ma non ottimale.
Nuovo Approccio (Fourier-Analitico): Il paper sfrutta la struttura completa della distribuzione di differenza.
1. Rappresentazione di Fourier: La funzione caratteristica della differenza è $\psi_{X-Y}(\theta) = |\phi(\theta)|^2$ , dove $\phi$ è la funzione caratteristica di $X$ . Di conseguenza, la funzione di massa di probabilità (pmf) della differenza $r_k = P(X-Y=k)$ è l'autocorrelazione di una pmf.
2. Polinomio Trigonométrico: La serie di Fourier associata alla distribuzione di differenza, $R(\theta) = \sum r_k e^{ik\theta}$ , deve essere un polinomio trigonometrico non negativo di grado al più $q-1$ .
3. Ottimizzazione Convessa: Invece di considerare solo il vincolo $r_0 \ge 1/q$ , il problema viene formulato come un problema di massimizzazione dell'entropia soggetto alla condizione che il polinomio $R(\theta)$ sia non negativo per ogni $\theta \in [0, 2\pi]$ .

Formulazione SDP (Semidefinite Programming)

Il vincolo di non negatività di un polinomio trigonometrico è equivalente all'esistenza di una famiglia infinita di vincoli di matrici di Toeplitz semidefinite positive (PSD).

Si definisce una matrice di Toeplitz $T^{(N)}(r)$ basata sui coefficienti $r_k$ .
Il problema di ottimizzazione viene risolto numericamente tramite SDP troncati (imponendo $T^{(N)}(r) \succeq 0$ per $N$ fino a un massimo $N_{max}$ ).
Questo approccio fornisce un rilassamento convesso più stretto rispetto ai metodi precedenti, poiché esclude distribuzioni ad alta entropia che soddisfano $r_0 \ge 1/q$ ma non possono essere autocorrelazioni di una distribuzione di probabilità valida.

3. Contributi Chiave

Rilassamento Fourier-Analitico: Introduzione di un nuovo rilassamento per la distribuzione di differenza i.i.d. che sfrutta il fatto che la sua funzione caratteristica è un polinomio trigonometrico non negativo.
Equivalenza SDP: Dimostrazione esplicita che questo rilassamento è caratterizzato equivalentemente da vincoli di matrici di Toeplitz PSD, collegando il problema ai classici risultati di positività definita per i coefficienti di Fourier.
Miglioramento del Limite di Entropia: Derivazione di un limite superiore stretto per l'entropia $H(X-Y)$ (denotato $h^F_q$ ) che è rigorosamente inferiore al limite precedente $\bar{h}_q$ .
Nuovi Limiti di Tasso: Integrazione del nuovo limite di entropia nel metodo "prefix-suffix" per ottenere limiti asintotici superiori più stretti per i codici B2 q-ari.
Valutazione Numerica: Calcolo dei nuovi limiti per $q \in \{9, 10, 11, 12, 13\}$ utilizzando SDP troncati, ottenendo i migliori limiti noti in letteratura per questi valori.

4. Risultati

Il paper presenta una tabella comparativa (Tabella I) che mostra i nuovi limiti di tasso ( $R^{new}_q$ ) confrontati con i migliori limiti esistenti (Lindström, Della Fiore-Dalai, Wang).

Per $q=9$ , il nuovo limite è 0.55792 (migliore del 0.56149 precedente).
Per $q=10$ , il nuovo limite è 0.55611 (migliore del 0.55966 precedente).
Per $q=11, 12, 13$ , si osservano miglioramenti costanti e significativi rispetto a tutti i lavori citati.
Il limite asintotico finale è dato da:
$R_b \le \frac{h^F_q}{\log q + h^F_q}$
dove $h^F_q$ è il valore ottimo del programma convesso Fourier-analitico.

5. Significato e Implicazioni

Rottura del "Gap" di Rilassamento: Il lavoro dimostra che ignorare la struttura di autocorrelazione (limitandosi al vincolo di collisione) porta a limiti di tasso non ottimali. Sfruttare la struttura di Fourier/Toeplitz permette di "tagliare" regioni dello spazio delle distribuzioni che non sono fisicamente realizzabili come differenze di variabili i.i.d.
Metodologia Generale: L'approccio combina teoria dell'informazione, analisi armonica e ottimizzazione convessa (SDP) in modo efficace. Questo metodo è potenzialmente estendibile ad altre famiglie di codici dove l'argomento prefix-suffix riduce il problema al controllo di entropie di differenze discrete strutturate.
Futuro: L'autore suggerisce che il "gap" tra il rilassamento (non negatività di $R(\theta)$ ) e la realtà (esistenza di un fattore spettrale con coefficienti non negativi) potrebbe essere ulteriormente ridotto aggiungendo vincoli di momento o estendendo il metodo a somme di ordine superiore (condizioni tipo $B_h$ ).

In sintesi, questo paper rappresenta un avanzamento significativo nella teoria dei codici combinatori, fornendo limiti di capacità più precisi per i codici B2 attraverso l'uso sofisticato di strumenti di ottimizzazione semidefinita basati sulla struttura di Fourier delle distribuzioni di probabilità.