Transversal Difference Numbers in Finite Abelian Quotients

Sintesi Tecnica: Numeri di Differenza Trasversale in Quozienti Abeliani Finiti

Enunciato del Problema
Il documento investiga il numero di differenza trasversale, denotato con $\delta(G, H)$, per una coppia di gruppi abeliani finiti dove $H \le G$. Una trasversale $T \subseteq G$ per il quoziente $G/H$ è un insieme contenente esattamente un rappresentante per ogni classe laterale di $H$. Sebbene la dimensione di $T$ sia fissata a $|G/H|$, la dimensione del suo supporto di differenza $D(T) = T - T = \{t_1 - t_2 : t_1, t_2 \in T\}$ varia a seconda della specifica immersione di $H$ in $G$. Il problema centrale è determinare la dimensione minima possibile di questo supporto:
$$\delta(G, H) = \min_{T} |D(T)|$$
Questo invariante è distinto dai problemi dei distinti (che si concentrano sulla molteplicità) o dai problemi della base di differenza (dove la dimensione dell'insieme varia). Qui, la dimensione dell'insieme è fissata e l'obiettivo è la minimizzazione del supporto.

Motivazione
La motivazione primaria deriva dalla Crittografia Completamente Omomorfica (FHE), specificamente dal framework "Vive Galois!" di Peikert e Pepin. In questo contesto, le trasversali vengono utilizzate per indicizzare le basi CRT (Chinese Remainder Theorem) per le espansioni di automorfismo in sottocampi ciclotomici. L'insieme di "etichette di automorfismo ambiente" richiesto per queste operazioni corrisponde al supporto di differenza $T - T$. Minimizzare $|T - T|$ riduce il numero di operazioni di automorfismo distinte (e i relativi costi di key-switching) necessari nelle procedure di bootstrapping impacchettato. Il documento chiarisce che $\delta(G, H)$ misura il limite inferiore teorico sulla dimensione di questo insieme di etichette, indipendentemente da specifici costi di implementazione o parametri di sicurezza.

Metodologia
Gli autori utilizzano strumenti della combinatoria additiva e della teoria dei gruppi abeliani finiti, nello specifico:

1. Decomposizione a Fibre: Decomposizione del supporto di differenza $D(T)$ basata sulle direzioni del quoziente $a \in G/H$.
2. Riduzione a Singoletto: Identificazione delle "direzioni a singoletto" (dove la fibra di differenza ha dimensione 1) e dimostrazione che esse si elevano a un sottogruppo disgiunto da $H$. Il quotientamento per questo sottogruppo riduce il problema a trasversali "primitive".
3. Teorema di Kneser: Utilizzo del limite inferiore basato sul stabilizzatore per insiemi di somma (e insiemi di differenza) per raffinare le stime per gruppi prodotto e catene.
4. Parametrizzazione su Campi Finiti: Per il caso specifico $G = (\mathbb{Z}/p^2\mathbb{Z})^2$, le trasversali sono modellate come grafici di funzioni $f: \mathbb{F}_p^2 \to \mathbb{F}_p^2$. Il supporto di differenza viene analizzato tramite derivate su campi finiti corrette per il riporto, collegando il problema ai fenomeni di somma-prodotto e all'espansione dell'immagine.
5. Metodi Probabilistici e Polinomiali: Utilizzo di argomenti di lifting casuale e analisi di lifting con polinomi fissi per stabilire il comportamento asintotico per il caso del piano quadrato.

Risultati Chiave e Contributi

1. Limite Inferiore Generale:
   Il documento stabilisce un limite inferiore uniforme:
   $$\delta(G, H) \ge 2|G/H| - m(G, H)$$
   dove $m(G, H)$ è l'ordine massimo di un sottogruppo di $G$ disgiunto da $H$. Questo limite è derivato dall'analisi delle fibre a singoletto e dalla riduzione a trasversali primitive.

2. Quozienti Ciclici:
   Il limite è dimostrato essere stretto per tutti i quozienti ciclici. Se $G/H$ è ciclico di ordine $q$, allora $\delta(G, H) = 2q - m(G, H)$. Questo risultato generalizza casi noti e fornisce formule esatte per gruppi ambiente ciclici.

3. Famiglie di Prodotti ed Estimazioni Cross-Trasversali:
   Utilizzando il teorema di Kneser, gli autori derivano formule esatte per i gruppi prodotto in cui una coordinata è un gruppo $p$-ico non-split e l'altra è arbitraria. Nello specifico, per $G = C_{p^a} \times L$ e $H = p^b C_{p^a} \times \{0\}$ (con $1 \le b < a$), il valore è $\delta(G, H) = |L|(2p^b - 1)$. Ciò dimostra che le strutture di prodotto si comportano spesso in modo moltiplicativo, a meno che non siano coinvolte coordinate non-split dello stesso primo.

4. L'Ostruzione del Piano Quadrato (Primi Dispari):
   Il documento identifica la coppia $G_p = (\mathbb{Z}/p^2\mathbb{Z})^2$ e $H_p = pG_p$ (per primi dispari) come la prima vera nuova ostruzione in cui la teoria ciclica e quella dei prodotti falliscono.

   • Congettura: $\delta(G_p, H_p) = (2p - 1)^2$. Questo valore corrisponde alla trasversale "a scatola di coordinate" (il lift standard).
   • Limite Inferiore Incondizionato: Gli autori dimostrano che $\delta(G_p, H_p) \ge 3p^2 - p - 1$.
   • Evidenze:
     • Primi Piccoli: La verifica deterministica conferma la congettura per $p=3$ e $p=5$.
     • Lifting Casuali: È dimostrato che una trasversale uniformemente casuale soddisfa il valore congetturato con probabilità che tende a 1 quando $p \to \infty$.
     • Polinomi Fissi: È dimostrato che nessun rule di lifting basato su polinomi interi fissi può produrre un controesempio per primi sufficientemente grandi.

5. Ostruzione della 2-Torsione:
   Per il caso $p=2$, il documento dimostra che se $G/H$ contiene un sottogruppo $C_2 \times C_2$, il limite inferiore è strettamente migliorato a $2|G/H| + 1$, separando il caso della 2-torsione dalla teoria dei primi dispari.

Significatività e Rivendicazioni
Il documento rivendica di isolare la prima vera nuova ostruzione residua nello studio dei numeri di differenza trasversale: il piano quadrato a stesso primo $(\mathbb{Z}/p^2\mathbb{Z})^2$. Mentre i casi ciclici e di primi misti sono completamente risolti, il caso del piano quadrato per primi dispari rimane una congettura.

Gli autori pongono il loro lavoro come un'indagine algebrica rigorosa sulla geometria "residua" dei quozienti abeliani finiti. Essi dichiarano esplicitamente che i loro risultati non pretendono di risolvere direttamente il problema dell'implementazione FHE (poiché runtime e sicurezza dipendono da fattori oltre $|T-T|$), ma forniscono il preciso limite algebrico inferiore per la dimensione dell'insieme di etichette nel bookkeeping Galois/CRT di tali sistemi. Il nucleo tecnico del documento risiede nella traduzione del problema di teoria dei gruppi nelle immagini delle derivate su campi finiti e nel successivo applicare metodi di incidenza e polinomiali per limitare tali immagini.

Problemi Aperti
Il documento si conclude inquadrando la congettura del piano quadrato come il problema aperto centrale. Pone inoltre domande riguardanti i quozienti di rango superiore con modulo quadrato $(\mathbb{Z}/p^2\mathbb{Z})^r$ e la classificazione delle geometrie di quoziente primitive che forzano miglioramenti stretti rispetto al limite inferiore generale.