🔢 mathematics

Transversal Difference Numbers in Finite Abelian Quotients

This paper introduces and investigates the transversal difference number $\delta(G,H)$ , a new invariant measuring the minimal size of the difference set of a transversal in finite abelian quotients, by establishing general lower bounds, characterizing specific product families, and providing strong evidence for a conjectured exact value in the technically core case of same-prime square planes.

Original authors: Mugurel Barcau, Vicenţiu Paşol, George C. Ţurcaş

Published 2026-06-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mugurel Barcau, Vicenţiu Paşol, George C. Ţurcaş

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Picking Representatives for a Group

Imagine you have a massive, organized warehouse (the group G) filled with thousands of identical-looking boxes. Inside this warehouse, there are smaller, specific rooms (the subgroup H).

When you want to do a quick inventory, you don't need to count every single box in every room. Instead, you just need to pick one representative box from each room to stand in for that whole room. This collection of one box per room is called a transversal.

The paper asks a very specific question: How "spread out" are these representative boxes?

If you take any two representative boxes and measure the "distance" (or difference) between them, you get a list of all possible distances. The authors want to find a way to pick your representatives so that this list of distances is as short and compact as possible. They call this compactness the "Transversal Difference Number."

The Analogy: The "Labeling" Problem

Why does this matter? The paper mentions a real-world application in Homomorphic Encryption (a type of super-secure computing).

Think of the warehouse as a secure vault where you are processing data. To do math on the data without opening the vault, you use a special "translation key" (a Galois label).

If you pick your representatives poorly, your translation keys might be scattered all over the map. You'd have to carry a huge, heavy bag of keys to do your work.
If you pick them wisely, all your keys cluster together in a small, neat pile. You only need a tiny bag.

The paper is trying to figure out: What is the smallest possible bag size we can achieve for any given warehouse layout?

The Rules of the Game

The authors discovered that the answer depends entirely on the shape of the warehouse and how the rooms are arranged.

1. The Easy Cases (Cyclic Quotients)
Sometimes, the rooms are arranged in a simple circle or a straight line. In these cases, the authors found a perfect formula. It's like arranging books on a single shelf; you can always find a way to pick representatives so the "distance list" is exactly as small as mathematically possible.

The Result: If the layout is simple (cyclic), we know the exact answer.

2. The "Split" vs. "Nonsplit" Twist
The paper distinguishes between two types of warehouse layouts:

Split: The rooms are arranged so cleanly that you can pick representatives that form a perfect, independent group of their own. Here, the "distance list" is tiny.
Nonsplit: The rooms are tangled. You can't pick representatives that form a clean group; they are forced to overlap in messy ways. This is where the math gets hard.

3. The "Square Plane" Mystery (The Core Discovery)
The most interesting part of the paper is about a specific, tricky layout: a square grid made of prime-numbered blocks (specifically, a $p \times p$ grid where $p$ is an odd number like 3, 5, or 7).

The Intuition: If you try to pick representatives on this grid, you might think you can just pick a simple square block (like a $3 \times 3$ square). This gives a certain "distance list" size.
The Conjecture: The authors conjecture (strongly believe) that you cannot do better than this simple square block. No matter how cleverly you twist and turn your selection of representatives, you can't shrink the "distance list" any further.
The Evidence:
- They proved that for small grids (like $3 \times 3$ and $5 \times 5$ ), the simple square is indeed the best you can do.
- They proved that if you pick representatives randomly, you will almost certainly get a "distance list" that is just as big as the simple square (or bigger).
- They proved that if you use a fixed mathematical rule (like a specific polynomial formula) to pick your representatives, you will also fail to beat the simple square for large grids.

The "Carry" and "Derivative" Metaphor

To prove their points about the square grids, the authors had to invent a new way of looking at the problem. They treated the representatives like a graph of a function (a line drawn on a graph).

They realized that the "distance" between representatives is like measuring the slope of that line. However, because the warehouse is a grid with a "wrap-around" effect (like a video game screen where going off the right edge puts you on the left), there are "carries" (like when you add 9 + 1 and get 10, carrying the 1).

The authors showed that the "distance list" is essentially a collection of corrected slopes. They proved that even if you try to make the slopes very uniform, the "wrap-around" carries force the list of distances to stay large.

Summary of Findings

General Rule: There is a universal lower limit to how small the "distance list" can be. It depends on the size of the warehouse and the largest "independent" group you can find inside it.
Simple Shapes: If the warehouse is a simple circle or line, we know the exact minimum size.
The Square Grid Mystery: For a square grid of prime size, the authors strongly suspect the minimum size is exactly what you get from picking a simple square block.
- They have a proof that the list cannot be smaller than a certain number (a lower bound).
- They have computer checks for small grids confirming the simple square is best.
- They have probability proofs showing that random attempts won't work.
- They have algebraic proofs showing that fixed formulas won't work.

What They Didn't Do

The paper does not claim to have solved the problem for every possible grid size yet. The "Square Plane" case for large prime numbers is still a conjecture. They have strong evidence it's true, but a final, rigorous mathematical proof for all odd primes is the next step they are calling for.

They also explicitly state that while this helps understand the "cost" of encryption keys, they are not solving the encryption problem itself, nor are they making claims about how fast a computer will run. They are purely solving a puzzle about how to arrange numbers in a group to minimize the variety of differences between them.

Technical Summary: Transversal Difference Numbers in Finite Abelian Quotients

Problem Statement
The paper investigates the transversal difference number, denoted $\delta(G, H)$ , for a pair of finite abelian groups where $H \le G$ . A transversal $T \subseteq G$ for the quotient $G/H$ is a set containing exactly one representative from each coset of $H$ . While the size of $T$ is fixed at $|G/H|$ , the size of its difference support $D(T) = T - T = \{t_1 - t_2 : t_1, t_2 \in T\}$ varies depending on the specific embedding of $H$ in $G$ . The central problem is to determine the minimum possible size of this support:
$\delta(G, H) = \min_{T} |D(T)|$
This invariant is distinct from difference-set problems (which focus on multiplicity) or difference-basis problems (where the set size varies). Here, the set size is fixed, and the goal is support minimization.

Motivation
The primary motivation stems from Fully Homomorphic Encryption (FHE), specifically the "Vive Galois!" framework by Peikert and Pepin. In this context, transversals are used to index CRT (Chinese Remainder Theorem) bases for automorphism expansions in cyclotomic subfields. The set of "ambient automorphism labels" required for these operations corresponds to the difference support $T - T$ . Minimizing $|T - T|$ reduces the number of distinct automorphism operations (and associated key-switching costs) needed in packed bootstrapping procedures. The paper clarifies that $\delta(G, H)$ measures the theoretical lower bound on this label set size, independent of specific implementation costs or security parameters.

Methodology
The authors employ tools from additive combinatorics and finite abelian group theory, specifically:

Fiber Decomposition: Decomposing the difference support $D(T)$ based on quotient directions $a \in G/H$ .
Singleton Reduction: Identifying "singleton directions" (where the difference fiber has size 1) and showing they lift to a subgroup disjoint from $H$ . Quotienting by this subgroup reduces the problem to "primitive" transversals.
Kneser's Theorem: Utilizing the stabilizer-based lower bound for sumsets (and difference sets) to refine estimates for product groups and chains.
Finite-Field Parametrization: For the specific case of $G = (\mathbb{Z}/p^2\mathbb{Z})^2$ , transversals are modeled as graphs of functions $f: \mathbb{F}_p^2 \to \mathbb{F}_p^2$ . The difference support is analyzed via carry-corrected finite-field derivatives, linking the problem to sum-product phenomena and image expansion.
Probabilistic and Polynomial Methods: Using random lifting arguments and fixed-polynomial lifting analysis to establish asymptotic behavior for the square-plane case.

Key Results and Contributions

General Lower Bound:
The paper establishes a uniform lower bound:
$\delta(G, H) \ge 2|G/H| - m(G, H)$
where $m(G, H)$ is the maximum order of a subgroup of $G$ disjoint from $H$ . This bound is derived by analyzing singleton fibers and reducing to primitive transversals.
Cyclic Quotients:
The bound is proven sharp for all cyclic quotients. If $G/H$ is cyclic of order $q$ , then $\delta(G, H) = 2q - m(G, H)$ . This result generalizes known cases and provides exact formulas for cyclic ambient groups.
Product Families and Cross-Transversal Estimates:
Using Kneser's theorem, the authors derive exact formulas for product groups where one coordinate is a "nonsplit" cyclic $p$ -group and the other is arbitrary. Specifically, for $G = C_{p^a} \times L$ and $H = p^b C_{p^a} \times \{0\}$ (with $1 \le b < a$ ), the value is $\delta(G, H) = |L|(2p^b - 1)$ . This demonstrates that product structures often behave multiplicatively unless "same-prime" nonsplit coordinates are involved.
The Square-Plane Obstruction (Odd Primes):
The paper identifies the pair $G_p = (\mathbb{Z}/p^2\mathbb{Z})^2$ and $H_p = pG_p$ (for odd primes $p$ ) as the first genuinely new obstruction where the cyclic and product theories fail.
- Conjecture: $\delta(G_p, H_p) = (2p - 1)^2$ . This value corresponds to the "coordinate box" transversal (the standard lift).
- Unconditional Lower Bound: The authors prove $\delta(G_p, H_p) \ge 3p^2 - p - 1$ .
- Evidence:
  - Small Primes: Deterministic verification confirms the conjecture for $p=3$ and $p=5$ .
  - Random Liftings: It is shown that a uniformly random transversal satisfies the conjectured bound with probability approaching 1 as $p \to \infty$ .
  - Fixed Polynomials: It is proven that no fixed integer-polynomial lifting rule can produce a counterexample for sufficiently large primes.
Two-Torsion Obstruction:
For the case $p=2$ , the paper proves that if $G/H$ contains a $C_2 \times C_2$ subgroup, the lower bound is strictly improved to $2|G/H| + 1$ , separating the 2-torsion case from the odd-prime theory.

Significance and Claims
The paper claims to isolate the first genuinely new residual obstruction in the study of transversal difference numbers: the same-prime square plane $(\mathbb{Z}/p^2\mathbb{Z})^2$ . While the cyclic and mixed-prime cases are fully resolved, the odd-prime square-plane case remains a conjecture.

The authors position their work as a rigorous algebraic investigation into the "residual" geometry of finite abelian quotients. They explicitly state that their results do not claim to solve the FHE implementation problem directly (as runtime and security depend on factors beyond $|T-T|$ ) but rather provide the precise algebraic lower bound for the label set size in the Galois/CRT bookkeeping of such systems. The technical core of the paper lies in the translation of the group-theoretic problem into finite-field derivative images and the subsequent application of incidence and polynomial methods to bound these images.

Open Problems
The paper concludes by framing the square-plane conjecture as the central open problem. It also poses questions regarding higher-rank square-modulus quotients $(\mathbb{Z}/p^2\mathbb{Z})^r$ and the classification of primitive quotient geometries that force strict improvements over the general lower bound.