Block Tensor Rank of Sum-Rank Metric Codes

Resumen Técnico: Rango de Tensor de Bloque de Códigos de Métrica Suma-Rango

Planteamiento del Problema
Los códigos de métrica suma-rango generalizan tanto a los códigos de métrica Hamming como a los de métrica de rango, representando las palabras de código como tuplas de matrices particionadas en bloques fijos, con un peso definido como la suma de los rangos de dichos bloques. Si bien el invariante de rango tensorial para los códigos de métrica de rango (el número mínimo de matrices de rango uno que generan un código) ha sido ampliamente estudiado, no se ha desarrollado sistemáticamente un invariante correspondiente adaptado a la estructura de bloques de los códigos de suma-rango. El artículo aborda el desafío de definir y calcular un "rango de tensor de bloque" para los códigos de suma-rango que respete la descomposición de bloques, distinguiéndolo de los invariantes teóricos de soporte y de los enfoques existentes de prueba de equivalencia de tensores.

Metodología y Definiciones
Los autores introducen el concepto de tensores simples de bloque, definidos como matrices de rango uno soportadas enteramente dentro de un único bloque de la tupla de suma-rango. El rango de tensor de bloque de un código de suma-rango $C$, denotado como $btrk(C)$, se define como el menor número de tensores simples de bloque cuyo espacio lineal contiene a $C$.

El enfoque metodológico central consiste en:

1. Tuplas Generadoras: Asociar cada código con una tupla de 3-tensores (uno por bloque) que generan el código mediante aplicaciones lineales.
2. Descomposición por Bloques: Demostrar que el rango de tensor de bloque de todo el código es la suma de los rangos tensoriales de sus proyecciones de bloque individuales. Esto reduce el problema global a problemas estándar de rango de tensores sobre códigos de métrica de rango.
3. Argumento del Código de Coordenadas: Construir un código lineal de bloque sobre el campo base $\mathbb{F}_q$ (el "código de coordenadas") mediante el mapeo de las palabras de código a sus coeficientes relativos a una base de tensores simples de bloque. Esto permite la transferencia de los límites clásicos de la métrica Hamming al entorno del rango de tensor de bloque.

Contribuciones Clave y Resultados

• Teorema de Descomposición Estructural: El artículo establece que $btrk(C) = \sum_{i=1}^t trk(\pi_i(C))$, donde $\pi_i(C)$ es la proyección del código sobre el $i$-ésimo bloque y $trk$ denota el rango tensorial estándar. Esta identidad implica que el cálculo del rango de tensor de bloque se separa en computaciones independientes de rango de tensor para cada bloque.
• Límites Inferiores: Se derivan dos límites inferiores complementarios:
  • Límite por Proyección: Derivado directamente del teorema de descomposición, establece que $btrk(C) \ge \sum N_q(k_i, d_i)$, donde $k_i$ y $d_i$ son la dimensión y la distancia de rango mínima de la $i$-ésima proyección.
  • Límite del Código de Coordenadas: Derivado de los parámetros globales $(k, d)$ del código, establece que $btrk(C) \ge N_q(k, d)$, donde $N_q(k, d)$ es la longitud mínima de un código lineal con dimensión $k$ y distancia Hamming mínima $d$.
  • Refinamientos de Singleton y Griesmer: Al aplicar los límites clásicos de Singleton y Griesmer a $N_q(k, d)$, los autores derivan el límite de coordenada de Singleton ($btrk(C) \ge k + d - 1$) y el límite de coordenada de Griesmer ($btrk(C) \ge G_q(k, d)$).
• Nociones Extremales:
  • Códigos BTR: Códigos que alcanzan el límite de coordenada de Singleton ($btrk(C) = k + d - 1$).
  • Códigos Extremales de Rango de Tensor de Bloque: Códigos que alcanzan el límite más ajustado $btrk(C) = N_q(k, d)$.
• Construcciones:
  • Levantamiento Diagonal de Bloques: Se introduce un método general para construir códigos de suma-rango mediante el levantamiento de códigos lineales de bloque clásicos (el "backbone" o estructura base) a través de mapas diagonales.
  • Familias BTR: Se proporcionan construcciones explícitas de códigos BTR utilizando backbones MDS (por ejemplo, códigos Reed–Solomon) bajo regímenes específicos (regímenes de bloque grueso, MDS-backbone uniforme y de agrupación/pooling).
  • Familias Óptimas de Griesmer: Utilizando backbones óptimos de Griesmer (por ejemplo, códigos Simplex y MacDonald), los autores construyen códigos que alcanzan el límite de coordenada de Griesmer, los cuales son extremales pero no necesariamente BTR cuando $G_q(k, d) > k + d - 1$.
• Comparación con Códigos MSRD: El artículo demuestra que la optimalidad BTR y la optimalidad de Distancia de Suma-Rango Máxima (MSRD) son distintas. Específicamente, en el régimen de levantamiento de backbone MDS uniforme, los códigos no pueden alcanzar simultáneamente el umbral BTR y la dimensión MSRD uniforme. Además, los autores aplican su criterio de brecha de proyección a las construcciones existentes (Chen [19] y Lao et al. [20]), mostrando que mientras algunas están cerca del umbral BTR, otras (como ciertos códigos MSRD) exhiben grandes brechas debido a altos rangos tensoriales en sus proyecciones de bloque.

Significancia y Reivindicaciones
El artículo afirma proporcionar el primer marco sistemático para analizar códigos de suma-rango a través de la lente del rango de tensor adaptado a bloques. Su significancia radica en:

1. Unificación: Conectar la teoría de codificación de suma-rango con la teoría de descomposición de tensores y los límites clásicos de la métrica Hamming.
2. Reducción Computacional: El teorema de descomposición por bloques simplifica el cálculo del rango de tensor de bloque a problemas conocidos de rango de tensor de métrica de rango.
3. Nuevos Criterios de Optimalidad: Introducir los códigos BTR y los códigos extremos de rango de tensor de bloque como nuevas clases de códigos óptimos, distintos de los códigos MSRD.
4. Perspectiva Estructural: Los autores sugieren que el rango de tensor de bloque sirve como una medida de la "economía algebraica" de un código. Postulan que este invariante podría ser relevante para distinguir familias de códigos estructurados de las aleatorias en la criptografía post-cuántica, aunque no proponen esquemas o ataques criptográficos específicos.

El trabajo concluye identificando problemas abiertos, incluyendo la clasificación de regímenes de parámetros para la existencia de BTR más allá de las construcciones de levantamiento y el uso potencial del rango de tensor de bloque como un distinguidor estructural en la criptografía basada en códigos.