Transversal Difference Numbers in Finite Abelian Quotients

Technische Samenvatting: Transversale Verschilgetallen in Eindige Abelse Quotiënten

Probleemstelling
Het artikel onderzoekt het transversale verschilgetal, aangeduid als $\delta(G, H)$, voor een paar eindige abelse groepen waarbij $H \le G$. Een transversaal $T \subseteq G$ voor de quoët $G/H$ is een verzameling die precies één vertegenwoordiger bevat uit elke coset van $H$. Hoewel de grootte van $T$ vaststaat op $|G/H|$, varieert de grootte van de verschilondersteuning $D(T) = T - T = \{t_1 - t_2 : t_1, t_2 \in T\}$ afhankelijk van de specifieke inbedding van $H$ in $G$. Het centrale probleem is het bepalen van de minimale mogelijke grootte van deze ondersteuning:
$$\delta(G, H) = \min_{T} |D(T)|$$
Dit invariant is verschillend van verschil-verzamelingsproblemen (die zich richten op multipliciteit) of verschil-basisproblemen (waarbij de verzamelingsgrootte varieert). Hier staat de verzamelingsgrootte vast en is het doel de ondersteuningsgrootte te minimaliseren.

Motivatie
De primaire motivatie komt voort uit Fully Homomorphic Encryption (FHE), specif kind de "Vive Galois!"-framework van Peikert en Pepin. In deze context worden transversalen gebruikt om CRT (Chinese Restvorm) bases te indexeren voor automorfisme-expansies in cyclotomische subvelden. De verzameling van "ambient automorfisme-labels" die vereist is voor deze operaties komt overeen met de verschilondersteuning $T - T$. Het minimaliseren van $|T - T|$ vermindert het aantal verschillende automorfisme-operaties (en de daarmee gepaard gaande key-switching kosten) die nodig zijn in gepakte bootstrapping-procedures. Het artikel verduidelijkt dat $\delta(G, H)$ de theoretische ondergrens meet voor de grootte van dit label-verzameling, onafhankelijk van specifieke implementatiekosten of beveiligingsparameters.

Methodologie
De auteurs maken gebruik van instrumenten uit de additieve combinatoriek en de eindige abelse groepentheorie, specifiek:

1. Vezeldecompositie: Het decomponeren van de verschilondersteuning $D(T)$ op basis van quoët-richtingen $a \in G/H$.
2. Singleton Reductie: Het identificeren van "singleton-richtingen" (waar de verschilvezel grootte 1 heeft) en het aantonen dat deze liften naar een subgroep die disjunct is van $H$. Het quotienten door deze subgroep reduceert het probleem tot "primitieve" transversalen.
3. Kneser's Stelling: Het gebruik van de stabilizer-gebaseerde ondergrens voor somverzamelingen (en verschilverzamelingen) om schattingen voor productgroepen en ketens te verfijnen.
4. Eindige-veld Parametrisatie: Voor het specifieke geval van $G = (\mathbb{Z}/p^2\mathbb{Z})^2$ worden transversalen gemodelleerd als grafieken van functies $f: \mathbb{F}_p^2 \to \mathbb{F}_p^2$. De verschilondersteuning wordt geanalyseerd via carry-gecorrigeerde eindige-veld derivaten, wat het probleem verbindt met som-product fenomenen en beeld-expansie.
5. Probabilistische en Polynomiale Methoden: Het gebruik van random lifting-argumenten en fixed-polynomial lifting-analyse om het asymptotische gedrag voor het vierkante-vlak geval vast te stellen.

Belangrijkste Resultaten en Bijdragen

1. Algemene Ondergrens:
   Het artikel stelt een uniforme ondergrens vast:
   $$\delta(G, H) \ge 2|G/H| - m(G, H)$$
   waarbij $m(G, H)$ de maximale orde is van een subgroep van $G$ die disjunct is van $H$. Deze grens wordt afgeleid door singleton vezels te analyseren en te reduceren tot primitieve transversalen.

2. Cyclische Quotiënten:
   De grens wordt bewezen scherp voor alle cyclische quotiënten. Als $G/H$ cyclisch is van orde $q$, dan is $\delta(G, H) = 2q - m(G, H)$. Dit resultaat generaliseert bekende gevallen en levert exacte formules voor cyclische ambient groepen.

3. Productfamilies en Cross-Transversal Schattingen:
   Met behulp van Kneser's stelling leiden de auteurs exacte formules af voor productgroepen waarbij één coördinaat een "niet-gesplitste" cyclische $p$-groep is en de andere willekeurig is. Specifiek, voor $G = C_{p^a} \times L$ en $H = p^b C_{p^a} \times \{0\}$ (met $1 \le b < a$), is de waarde $\delta(G, H) = |L|(2p^b - 1)$. Dit toont aan dat productstructuren vaak multiplicatief gedrag vertonen, tenzij "dezelfde-prijs" niet-gesplitste coördinaten betrokken zijn.

4. De Vierkante-Vlak Obstruction (Oneven Priemen):
   Het artikel identificeert het paar $G_p = (\mathbb{Z}/p^2\mathbb{Z})^2$ en $H_p = pG_p$ (voor oneven priemgetallen) als de eerste werkelijk nieuwe obstructie waar de cyclische en producttheorieën falen.

   • Conjectuur: $\delta(G_p, H_p) = (2p - 1)^2$. Deze waarde komt overeen met de "coördinaat-box" transversaal (de standaard lift).
   • Onvoorwaardelijke Ondergrens: De auteurs bewijzen $\delta(G_p, H_p) \ge 3p^2 - p - 1$.
   • Bewijs:
     • Kleine Priemen: Deterministische verificatie bevestigt de conjectuur voor $p=3$ en $p=5$.
     • Random Liftings: Er wordt aangetoond dat een uniform willekeurige transversaal de geconjectureerde grens voldoet met een waarschijnlijkheid die naar 1 convergeert als $p \to \infty$.
     • Fixed Polynomials: Er wordt bewezen dat geen enkele vaste geheelgetal-polynomiale lifting-regel een tegenvoorbeeld kan produceren voor voldoende grote priemgetallen.

5. Twee-Torsie Obstruction:
   Voor het geval $p=2$ bewijst het artikel dat als $G/H$ een $C_2 \times C_2$ subgroep bevat, de ondergrens strikt wordt verbeterd naar $2|G/H| + 1$, waarmee het 2-torsie geval wordt gescheiden van de oneven priem theorie.

Betekenis en Claims
Het artikel claimt de eerste werkelijk nieuwe residuele obstructie te hebben geïsoleerd in de studie van transversale verschilgetallen: het zelfde-prijs vierkante vlak $(\mathbb{Z}/p^2\mathbb{Z})^2$. Terwijl de cyclische en gemengde-prijs gevallen volledig zijn opgelost, blijft de oneven-priem vierkante-vlak casus een conjectuur.

De auteurs positioneren hun werk als een rigoureuze algebraïsche investigatie naar de "residuele" geometrie van eindige abelse quotiënten. Ze verklaren expliciet dat hun resultaten niet direct het FHE-implementatieprobleem oplossen (aangezien runtime en beveiliging afhangen van factoren buiten $|T-T|$), maar dat ze de precieze algebraïsche ondergrens bieden voor de grootte van de label-verzameling in de Galois/CRT boekhouding van dergelijke systemen. De technische kern van het artikel ligt in de vertaling van het groepentheoretische probleem naar eindige-veld derivaten-beelden en de daaropvolgende toepassing van incidentie en polynomiale methoden om deze beelden te begrenzen.

Openstaande Problemen
Het artikel concludeert door de vierkante-vlak conjectuur als het centrale openstaande probleem te kaderen. Het stelt ook vragen over hogere-rang vierkante-modulus quotiënten $(\mathbb{Z}/p^2\mathbb{Z})^r$ en de classificatie van primitieve quotient-geometrieën die strikte verbeteringen boven de algemene ondergrens afdwingen.