Block Tensor Rank of Sum-Rank Metric Codes

Sintesi Tecnica: Rango del Tensore a Blocchi dei Codici con Metrica Somma-Rango

Enunciato del Problema
I codici con metrica somma-rango generalizzano sia i codici con metrica di Hamming che quelli con metrica di rango, rappresentando i codici come tuple di matrici partizionate in blocchi fissi, con un peso definito come la somma dei ranghi di tali blocchi. Sebbene l'invariante del rango tensoriale per i codici con metrica di rango (il numero minimo di matrici di rango uno che generano un codice) sia ben studiata, un corrispondente invariante adattato alla struttura a blocchi dei codici somma-rango non è stato sistematicamente sviluppato. Il documento affronta la sfida di definire e calcolare un "rango del tensore a blocchi" per i codici somma-rango che rispetti la decomposizione a blocchi, distinguendolo dagli invarianti basati sul supporto e dagli esistenti approcci tensoriali per il test di equivalenza.

Metodologia e Definizioni
Gli autori introducono il concetto di tensori semplici a blocchi, definiti come matrici di rango uno il cui supporto è interamente contenuto in un singolo blocco della tupla somma-rango. Il rango del tensore a blocchi di un codice somma-rango $C$, indicato con $btrk(C)$, è definito come il numero minimo di tensori semplici a blocchi il cui spazio lineare contiene $C$.

L'approccio metodologico centrale consiste nel:

1. Tuple Generatrici: Associare a ciascun codice una tupla di 3-tensori (uno per ogni blocco) che generano il codice tramite mappe lineari.
2. Decomposizione a Blocchi: Dimostrare che il rango del tensore a blocchi dell'intero codice è la somma dei ranghi tensoriali delle sue singole proiezioni a blocchi. Ciò riduce il problema globale ai problemi standard di rango tensoriale sui codici con metrica di rango.
3. Argomento del Codice di Coordinate: Costruire un codice lineare a blocchi sul campo base $\mathbb{F}_q$ (il "codice di coordinate") mappando i codici nei loro coefficienti rispetto a una base semplice a blocchi. Ciò consente il trasferimento dei classici limiti della metrica di Hamming al contesto del rango del tensore a blocchi.

Contributi Chiave e Risultati

• Teorema di Decomposizione Strutturale: Il documento stabilisce che $btrk(C) = \sum_{i=1}^t trk(\pi_i(C))$, dove $\pi_i(C)$ è la proiezione del codice sul $i$-esimo blocco e $trk$ indica il rango tensoriale standard. Questa identità implica che il calcolo del rango del tensore a blocchi si separa in calcoli indipendenti del rango tensoriale per ogni blocco.
• Limiti Inferiori: Vengono derivati due limiti inferiori complementari:
  • Limite di Proiezione per Blocco: Derivato direttamente dal teorema di decomposizione, afferma che $btrk(C) \ge \sum N_q(k_i, d_i)$, dove $k_i$ e $d_i$ sono la dimensione e la distanza di rango minima della $i$-esima proiezione.
  • Limite del Codice di Coordinate: Derivato dai parametri globali $(k, d)$ del codice, afferma che $btrk(C) \ge N_q(k, d)$, dove $N_q(k, d)$ è la lunghezza minima di un codice lineare con dimensione $k$ e distanza di Hamming minima $d$.
  • Raffinatezze di Singleton e Griesmer: Applicando i classici limiti di Singleton e Griesmer a $N_q(k, d)$, gli autori derivano il limite di coordinata di Singleton ($btrk(C) \ge k + d - 1$) e il limite di coordinata di Griesmer ($btrk(C) \ge G_q(k, d)$).
• Nozioni di Estremalità:
  • Codici BTR: Codici che raggiungono il limite di coordinata di Singleton ($btrk(C) = k + d - 1$).
  • Codici Estremi per il Rango del Tensore a Blocchi: Codici che raggiungono il limite più stretto $btrk(C) = N_q(k, d)$.
• Costruzioni:
  • Sollevamento Diagonale a Blocchi: Viene introdotto un metodo generale per costruire codici somma-rango sollevando i classici codici lineari a blocchi (l'"ossatura" o backbone) in blocchi matriciali tramite mappe diagonali.
  • Famiglie BTR: Vengono fornite costruzioni esplicite di codici BTR utilizzando ossature MDS (ad esempio, codici di Reed–Solomon) sotto specifici regimi di parametri (regimi Fat-block, Uniform MDS-backbone e Pooling).
  • Famiglie Ottimali per Griesmer: Utilizzando ossature ottimali per Griesmer (ad esempio, codici Simplex e MacDonald), gli autori costruiscono codici che raggiungono il limite di coordinata di Griesmer, i quali sono estremi ma non necessariamente BTR quando $G_q(k, d) > k + d - 1$.
• Confronto con i Codici MSRD: Il documento dimostra che l'ottimalità BTR e l'ottimalità MSRD (Massima Distanza Somma-Rango) sono concetti distinti. Nello specifico, nel regime di sollevamento con ossatura MDS uniforme, i codici non possono raggiungere simultaneamente la soglia BTR e la dimensione MSRD uniforme. Inoltre, gli autori applicano il loro criterio di gap di proiezione alle costruzioni esistenti (Chen [19] e Lao et al. [20]), mostrando che mentre alcune sono vicine alla soglia BTR, altre (come certi codici MSRD) presentano ampi gap dovuti agli alti ranghi tensoriali nelle loro proiezioni a blocchi.

Significato e Rivendicazioni
Il documento sostiene di fornire il primo quadro sistematico per l'analisi dei codici somma-rango attraverso la lente del rango tensoriale adattato ai blocchi. La sua importanza risiede nella:

1. Unificazione: Collegare la teoria dei codici somma-rango con la teoria della decomposizione tensoriale e i classici limiti della metrica di Hamming.
2. Riduzione Computazionale: Il teorema di decomposizione a blocchi semplifica il calcolo del rango del tensore a blocchi in problemi noti di rango tensoriale con metrica di rango.
3. Nuovi Criteri di Ottimalità: Introduzione dei codici BTR e dei codici estremi per il rango del tensore a blocchi come nuove classi di codici ottimali, distinti dai codici MSRD.
4. Approfondimento Strutturale: Gli autori suggeriscono che il rango del tensore a blocchi funga da misura dell' "economia algebrica" di un codice. Essi postulano che questo invariante potrebbe essere rilevante per distinguere famiglie di codici strutturati da quelle casuali nella crittografia post-quantistica, sebbene non propongano schemi o attacchi crittografici specifici.

Il lavoro si conclude identificando problemi aperti, tra cui la classificazione dei regimi di parametri per l'esistenza di BTR oltre le costruzioni di sollevamento e il potenziale uso del rango del tensore a blocchi come discriminatore strutturale nella crittografia basata su codici.