Transversal Difference Numbers in Finite Abelian Quotients

Resumen Técnico: Números de Diferencia Transversal en Cocientes Abelianos Finitos

Planteamiento del Problema
El artículo investiga el número de diferencia transversal, denotado como $\delta(G, H)$, para un par de grupos abelianos finitos donde $H \le G$. Un transversal $T \subseteq G$ para el cociente $G/H$ es un conjunto que contiene exactamente un representante de cada coset de $H$. Si bien el tamaño de $T$ es fijo en $|G/H|$, el tamaño de su soporte de diferencias $D(T) = T - T = \{t_1 - t_2 : t_1, t_2 \in T\}$ varía dependiendo de la incrustación específica de $H$ en $G$. El problema central es determinar el tamaño mínimo posible de este soporte:
$$\delta(G, H) = \min_{T} |D(T)|$$
Este invariante es distinto de los problemas de conjuntos de diferencias (que se centran en la multiplicidad) o de los problemas de bases de diferencia (donde el tamaño del conjunto varía). Aquí, el tamaño del conjunto es fijo y el objetivo es la minimización del soporte.

Motivación
La motivación principal surge de la Criptografía Totalmente Homomórfica (FHE), específicamente del marco "Vive Galois!" de Peikert y Pepin. En este contexto, los transversales se utilizan para indexar las bases CRT (Teorema del Resto Chino) para las expansiones de automorfismos en subcampos cíclotómicos. El conjunto de "etiquetas de automorfismo ambiental" requeridas para estas operaciones corresponde al soporte de diferencia $T - T$. Minimizar $|T - T|$ reduce el número de operaciones de automorfismo distintas (y los costos asociados de cambio de clave) necesarios en los procedimientos de bootstrapping empaquetado. El artículo aclara que $\delta(G, H)$ mide el límite inferior teórico del tamaño de este conjunto de etiquetas, independientemente de los costos de implementación específicos o los parámetros de seguridad.

Metodología
Los autores emplean herramientas de la combinatoria aditiva y la teoría de grupos abelianos finitos, específicamente:

1. Descomposición de Fibra: Descomposición del soporte de diferencia $D(T)$ basado en direcciones de cociente $a \in G/H$.
2. Reducción a Singleton: Identificación de "direcciones singleton" (donde la fibra de la diferencia tiene tamaño 1) y demostración de que estas se elevan a un subgrupo disjunto de $H$. El cociente por este subgrupo reduce el problema a transversales "primitivos".
3. Teorema de Kneser: Utilización de la cota inferior basada en el estabilizador para sumas (y diferencias) de conjuntos para refinar las estimaciones para grupos producto y cadenas.
4. Parametrización de Campos Finitos: Para el caso específico de $G = (\mathbb{Z}/p^2\mathbb{Z})^2$, los transversales se modelan como gráficas de funciones $f: \mathbb{F}_p^2 \to \mathbb{F}_p^2$. El soporte de la diferencia se analiza mediante derivadas de campos finitos con corrección de acarreo, vinculando el problema con los fenómenos de suma-producto y la expansión de la imagen.
5. Métodos Probabilísticos y Polinomiales: Uso de argumentos de elevación aleatoria y análisis de elevación por polinomios fijos para establecer el comportamiento asintótico para el caso del plano cuadrado.

Resultos Clave y Contribuciones

1. Cota Inferior General:
   El artículo establece una cota inferior uniforme:
   $$\delta(G, H) \ge 2|G/H| - m(G, H)$$
   donde $m(G, H)$ es el orden máximo de un subgrupo de $G$ disjunto de $H$. Esta cota se deriva analizando fibras singleton y reduciendo a transversales primitivos.

2. Cocientes Cíclicos:
   Se demuestra que la cota es ajustada (sharp) para todos los cocientes cíclicos. Si $G/H$ es cíclico de orden $q$, entonces $\delta(G, H) = 2q - m(G, H)$. Este resultado generaliza casos conocidos y proporciona fórmulas exactas para grupos ambientales cíclicos.

3. Familias de Productos y Estimaciones de Transversales Cruzados:
   Utilizando el teorema de Kneser, los autores derivan fórmulas exactas para grupos producto donde una coordenada es un grupo $p$-cíclico "no dividido" (nonsplit) y la otra es arbitraria. Específicamente, para $G = C_{p^a} \times L$ y $H = p^b C_{p^a} \times \{0\}$ (con $1 \le b < a$), el valor es $\delta(G, H) = |L|(2p^b - 1)$. Esto demuestra que las estructuras de producto suelen comportarse de manera multiplicativa a menos que intervengan coordenadas no divididas del mismo primo.

4. La Obstrucción del Plano Cuadrado (Primos Impares):
   El artículo identifica el par $G_p = (\mathbb{Z}/p^2\mathbb{Z})^2$ y $H_p = pG_p$ (para primos impares) como la primera obstrucción genuinamente nueva donde las teorías cíclica y de producto fallan.

   • Conjetura: $\delta(G_p, H_p) = (2p - 1)^2$. Este valor corresponde al transversal de la "caja de coordenadas" (la elevación estándar).
   • Cota Inferior Incondicional: Los autores demuestran que $\delta(G_p, H_p) \ge 3p^2 - p - 1$.
   • Evidencia:
     • Primos Pequeños: La verificación determinista confirma la conjetura para $p=3$ y $p=5$.
     • Elevaciones Aleatorias: Se muestra que un transversal uniformemente aleatorio satisface la cota conjeturada con una probabilidad que tiende a 1 cuando $p \to \infty$.
     • Polinomios Fijos: Se demuestra que ninguna regla de elevación por polinomio entero fijo puede producir un contraejemplo para primos suficientemente grandes.

5. Obstrucción de Dos Torsión:
   Para el caso $p=2$, el artículo demuestra que si $G/H$ contiene un subgrupo $C_2 \times C_2$, la cota inferior mejora estrictamente a $2|G/H| + 1$, separando el caso de 2-torsión de la teoría de primos impares.

Significado y Reivindicaciones
El artículo afirma aislar la primera obstrucción residual genuinamente nueva en el estudio de los números de diferencia de transversales: el plano cuadrado de mismo primo $(\mathbb{Z}/p^2\mathbb{Z})^2$. Mientras que los casos cíclicos y de primos mixtos están totalmente resueltos, el caso del plano cuadrado para primos impares sigue siendo una conjetura.

Los autores posicionan su trabajo como una investigación algebraica rigurosa de la geometría "residual" de los cocientes abelianos finitos. Declaran explícitamente que sus resultados no pretenden resolver directamente el problema de implementación de FHE (ya que el tiempo de ejecución y la seguridad dependen de factores más allá de $|T-T|$), sino que proporcionan la cota inferior algebraica precisa para el tamaño del conjunto de etiquetas en la contabilidad de Galois/CRT de tales sistemas. El núcleo técnico del artículo reside en la traducción del problema de teoría de grupos a imágenes de derivadas de campos finitos y la subsiguiente aplicación de métodos de incidencia y polinomiales para acotar dichas imágenes.

Problemas Abiertos
El artículo concluye enmarcando la conjetura del plano cuadrado como el problema abierto central. También plantea preguntas sobre cocientes de módulo cuadrado de mayor rango $(\mathbb{Z}/p^2\mathbb{Z})^r$ y la clasificación de geometrías de cocientes primitivos que fuerzan mejoras estrictas sobre la cota inferior general.