TRANSVERSAL DIFFERENCE NUMBERS IN FINITE ABELIAN QUOTIENTS
arXiv:2606.27961v1 [math.NT] 26 Jun 2026
MUGUREL BARCAU, VICENŢIU PAŞOL, AND GEORGE C. ŢURCAŞ
Abstract. Given H ≤ G finite abelian groups, a transversal T ⊆ G for G/H has fixed size |G/H|, but its ambient difference support D(T ) = T − T can vary with the embedding of H in G. We call δ(G, H) = minT |D(T )| the transversal difference number of the pair (G, H). This invariant is related to finite abelian factorisation, tiling complements, and small-sumset questions, and is motivated by recent work regarding ambient Galois labels in CRT transforms for cyclotomic-subfield homomorphic encryption. We prove various results regarding this invariant, including a general lower bound δ(G, H) ≥ 2|G/H| − m(G, H), where m(G, H) is the largest order of a subgroup of G disjoint from H. The bound is sharp for cyclic quotients, and Kneser’s theorem gives a cross-transversal estimate leading to exact product families with one nonsplit cyclic coordinate and arbitrary split factors. These results isolate the first genuinely new residual obstruction, namely the same-prime square plane G = (Z/p2 Z)2 ,
H = pG.
For odd p, this case is the technical core of the paper. Here transversals are graphs of functions F2p → F2p , and D(T ) decomposes into carry-corrected finite-field derivative images. We conjecture that δ(G, H) = (2p − 1)2 for all odd primes p, prove the unconditional lower bound 3p2 − p − 1, and give small-prime, probabilistic, and fixed-polynomial evidence for the conjecture.
1. Introduction A quotient group G/H remembers the cosets of H, but it forgets how a choice of coset representatives sits inside the ambient group. This ambient information can vary substantially from one section to another. Throughout, all groups are finite abelian and written additively. Given H ≤ G, a transversal T ⊆ G for G/H has cardinality |G/H|. However, its difference support D(T ) = T − T can varry substantially in size and a natural question is how small this set D(T ) can be. We call δ(G, H) = min |D(T )| T
the transversal difference number of the pair (G, H), where T ranges over all transversals for G/H. This invariant depends on the embedding H ≤ G, not only on the abstract quotient. For instance, δ(C2 , 0) = 2 and δ(C4 , 2C4 ) = 3, although both quotients This work was supported by the project “Group schemes, root systems, and related representations” funded by the European Union - NextGenerationEU through Romania’s National Recovery and Resilience Plan (PNRR) call no. PNRR-III-C9-2023- I8, Project CF159/31.07.2023, and coordinated by the Ministry of Research, Innovation and Digitalization (MCID) of Romania. All authors are also supported by certSign Research and Innovation. 1
2
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
are isomorphic to C2 . When trying to find δ(G, H), transversals can easily be found, but proving that their pairwise differences are as small as possible in the ambient group can be challenging. After translating T we may assume 0 ∈ T ; then T is a set-theoretic tiling complement to H, so every element of G is written uniquely as h+t with h ∈ H and t ∈ T . Thus δ(G, H) is a support minimisation problem for finite abelian factorisations G = H ⊕ T , where ⊕ denotes unique representation rather than an internal direct product. This places it near the classical theory of unique-representation factorisations and algebraic tilings [6, 11, 20, 25, 27]. The lower-bound methods are closest to small-sumset, critical-pair, and Kneser-type stabiliser arguments [8–10, 12, 13, 28]. It is not a difference-set or a relative difference-set problem, where multiplicity conditions rather than support minimisation are central [4, 19, 23], nor a differencebasis problem, where the set itself may vary in size while its differences cover the ambient group [1]. Here T has fixed size and must be a transversal; only the number of distinct ambient differences is minimised. Our motivation comes from the Galois-theoretic bookkeeping that appears in Peikert and Pepin’s Vive Galois! programme [17]. In exact fully homomorphic encryption one often wants many plaintext “slots” over a prescribed finite field or finite ring, so that one ciphertext carries a vector of plaintexts and homomorphic operations act componentwise on that vector. This is the SIMD idea of Smart and Vercauteren [24]. Cyclotomic rings provide fast arithmetic, many automorphisms, and good geometric properties, but their slot structure is arithmetically rigid: the residue degree of the chosen plaintext prime determines the slot type, and an unwanted extension degree gives fewer slots of a larger field than the application naturally wants. The point of the Peikert–Pepin construction is that cyclotomic subfields, and more generally abelian number rings, give a more flexible Galois-theoretic way to obtain the desired slot type and number of slots, while still supporting CRT bases, structured transforms, and packed bootstrapping. A finite choice of representatives enters this construction quite explicitly. In a tower of abelian extensions M/L/K, write GM/K = Gal(M/K),
GM/L = Gal(M/L).
Peikert and Pepin choose a transversal T ⊆ GM/K for the quotient GM/K /GM/L in order to index a CRT basis and the corresponding top-down sparse CRT transform [17, Def. 5.8]. Their Lemma 5.13 [17, Lemma 5.13] shows that, in the relevant automorphism expansion, a coefficient can be nonzero only for an ambient automorphism of the form τ = t′ t−1 (t, t′ ∈ T ). Thus the possible ambient automorphism labels are contained in T T −1 . In the additive notation of this paper, the same support is T −T . Consequently, the purely finite-abelian problem of minimising |T −T | over quotient transversals is exactly the problem of minimising the representative-dependent ambient label support forced by this part of the Galois/CRT bookkeeping. This is the precise sense in which a small value of δ(G, H) can be useful for the FHE framework. In Peikert–Pepin’s homomorphic CRT transforms [17, Secs. 3.2 and 4], structured linear maps are evaluated by applying automorphisms and taking linear combinations. Each distinct ambient automorphism label that is actually used is a potential automorphism operation, and in an FHE implementation such
TRANSVERSAL DIFFERENCE NUMBERS
3
an operation typically comes with key-switching data and key-switching cost. The first and third phases of packed bootstrapping are precisely CRT transforms: they move noisy decryption coefficients into the SIMD slots, allow the slotwise nonlinear decoding step, and then move the result back. Hence, for an implementation model in which each distinct ambient automorphism label carries cost, a transversal with smaller T T −1 may reduce the candidate automorphism/key-switch label set and simplify the linear part of packed bootstrapping. A word of caution about this motivation is worth mentioning. The quantity δ(G, H) measures just the size of the support of ambient automorphism labels forced by a choice of representatives, and therefore it should not be mistaken for a statement about runtime, memory, key-switching cost, parameter selection, or security. Several effects sit between this invariant and any real implementation. The label set T T −1 records which automorphisms can occur, but some of the corresponding coefficients may vanish for reasons the transversal cannot see; the cost of applying an automorphism depends on the particular FHE platform; and the Ring-LWE hardness assumptions used in this line of work are unaffected by how small |T − T | is. Once these caveats are set aside, what remains is a clean, finite, and entirely algebraic question, and that is the one we pursue: how small can the difference support of a section of a finite abelian quotient be, what is its value across broad families, and where does the naive split-or-cyclic intuition fail? Main results. The first part of the paper develops the theory in the finite abelian setting. Here the trivial lower bound δ(G, H) ≥ |G/H| is attained exactly when H has a subgroup complement. To go further, we isolate the singleton quotient directions of a transversal: their canonical lifts form a subgroup of G disjoint from H, and quotienting by it makes the transversal primitive, leaving no nonzero singleton fibres. This reduction yields the uniform lower bound δ(G, H) ≥ 2|G/H|−m(G, H), where m(G, H) is the largest order of a subgroup of G disjoint from H. For cyclic quotients the bound is sharp, and feeding Kneser’s theorem (Theorem 2.2) into a cross-transversal estimate pins down exact product families with one nonsplit cyclic coordinate and arbitrary split factors. This cyclic sharpness sits within the prime-cyclic critical-pair tradition initiated by Vosper [29], and more broadly within Kemperman’s analysis of small sumsets in abelian groups [12]. The precise statements are given in Sections 3 and 4, and there results therein should be viewed as both a general theory and as delimitation results: they identify the regimes in the ideas described above already determine the invariant. The main new difficulty begins when these mechanisms no longer control the support, namely in same-prime residual quotients with more than one nonsplit direction. Section 5 marks this transition. A residual quotient that contains a C2 × C2 plane already forces a strict gap from the trivial lower-bound. For odd primes, however, the parity argument disappears, and the first case left open by all the preceding exact results is Gp = (Z/p2 Z)2 ,
Hp = pGp .
This odd square-plane problem, treated from Section 6 onward, is the technical core of the paper. Here transversals become graphs of functions F2p → F2p , and the fibres of D(T ) turn into carry-corrected finite-field derivative images. Read in these terms, the square-plane problem sits close to finite-field sum-product [2] and image-expansion [16] questions, while the fixed-polynomial evidence gathered in
4
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
Section 7 lies nearest to value-set questions for polynomial maps [15]. We conjecture that δ(G, H) = (2p − 1)2 and prove the unconditional bound δ(G, H) ≥ 3p2 − p − 1. We also prove that random liftings meet the lower bound (2p − 1)2 with probability tending to one, and that no fixed integer-polynomial lifting can produce counterexamples once the prime is large enough. The final section gathers the primitive-quotient and square-modulus open problems that emerge along the way. 2. Preliminaries and notation Throughout the paper all groups are finite abelian and are written additively. For subsets A, B ⊆ G we write A + B = {a + b : a ∈ A, b ∈ B}, A − B = {a − b : a ∈ A, b ∈ B}, and −A = {−a : a ∈ A}. If K ≤ G is a subgroup, then A + K denotes the union of the K-cosets meeting A. Let H ≤ G. The quotient map will be denoted π = πG,H : G −→ G/H. When no confusion is possible we put Q = G/H,
q = |Q| = |G/H|.
A transversal for G/H is a subset T ⊆ G such that π|T : T → G/H is bijective. Equivalently, T contains exactly one element from each coset of H in G. For a transversal T we define its difference support D(T ) = T − T. The invariant studied in this paper is the transversal difference number of the pair (G, H): δ(G, H) = min |D(T )|, (2.1) T
where T ranges over all transversals for G/H. Translating a transversal by an element of G does not change its difference support. Hence, whenever convenient, we shall assume that T is normalized, meaning that 0 ∈ T . A normalized transversal is the same thing as a set-theoretic complement to H: every element g ∈ G has a unique expression g = h + t, with h ∈ H, and t ∈ T . This is a unique-representation factorisation of the set G; it does not mean that T is a subgroup unless this is explicitly stated. We use the terminology of set factorisations and complements in the standard sense of [27]; see also [11, 20, 25] for the classical factorisation and tiling background. It will be useful to identify a transversal with its section of the quotient map. Thus, for a normalized transversal T , we write s = sT : Q −→ G
(2.2)
for the unique section such that s(0) = 0, π ◦s = idQ , and T = s(Q). For a quotient direction a ∈ Q we define the corresponding difference fibre Da (T ) = D(T ) ∩ π −1 (a) = {s(x + a) − s(x) : x ∈ Q}.
(2.3)
The fibres Da (T ) are nonemptyFand decompose the difference support into the following disjoint union D(T ) = a∈Q Da (T ). Note that in particular D0 (T ) = {0}. We call a ∈ Q a singleton direction for T if |Da (T )| = 1. The set of singleton directions will be denoted Σ(T ) = {a ∈ Q : |Da (T )| = 1}.
(2.4)
TRANSVERSAL DIFFERENCE NUMBERS
5
If a ∈ Σ(T ), the unique element of Da (T ) will sometimes be written dT (a); equivalently, s(x + a) − s(x) = dT (a) for all x ∈ Q. Therefore, π(dT (a)) = a. We write e ) = {dT (a) : a ∈ Σ(T )} ⊆ G Σ(T for the corresponding lifted singleton set. Thus Σ(T ) is a subset of the quotient e ) is a subset of the ambient group G. G/H, while Σ(T Definition 2.1. A normalized transversal T ⊆ G for G/H is called primitive if Σ(T ) = {0}. Equivalently, no nonzero quotient direction has a singleton difference fibre. The following subgroup invariant will also appear in our work: m(G, H) = max{|K| : K ≤ G, K ∩ H = {0}}.
(2.5)
Note that 1 ≤ m(G, H) ≤ |G/H| and the case in which the pair G, H satisfies m(G, H) = 1 will be called residual. A subgroup K ≤ G is a subgroup complement to H if K ∩ H = {0} and G = H + K. In particular, H has a subgroup complement in G if and only if m(G, H) = |G/H|. For later use we recall Kneser’s theorem (see [13] or [28, Theorem 5.5]) in the finite form needed below. If A ⊆ G, its stabilizer is Stab(A) = {g ∈ G : A + g = A}. Theorem 2.2 (Kneser). Let A, B be nonempty subsets of a finite abelian group G, and write P = Stab(A + B). Then |A + B| ≥ |A + P | + |B + P | − |P |. Since A − B = A + (−B), the same estimate applies to difference sets A − B with P = Stab(A − B). The reader interested in broader background on Kneser-type inequalities, critical pairs, and small-doubling methods in abelian groups, could consult [12], [28] or [10]. 3. First bounds, singleton reduction and cyclic quotients The first estimates come from decomposing the difference support over quotient directions. We notice that singleton fibres lift to a subgroup of G disjoint from H and quotienting by this subgroup makes the transversal primitive, gives the uniform lower bound in terms of m(G, H), and leads to an exact formula for cyclic quotients. The first proposition below is the support-minimisation analogue of the basic exact-factorisation question: when does a set-theoretic complement become a subgroup complement? Classical factorisation results of Hajós [11] and Rédei [20] are related to this phenomenon. Proposition 3.1. Let H ≤ G. Then δ(G, H) = |G/H| if and only if H has a subgroup complement in G. Proof. Let q = |G/H|. For every transversal T and every fixed t0 ∈ T , the translate T − t0 has q elements and is contained in D(T ) = T − T . Hence |D(T )| ≥ q for every T , so δ(G, H) ≥ q. If K ≤ G is a subgroup complement to H, then K is a transversal for G/H and D(K) = K − K = K. Thus δ(G, H) ≤ |K| = q, and equality follows. Conversely, suppose δ(G, H) = q, and choose a transversal T with |D(T )| = q. Translating T if necessary, assume 0 ∈ T . Then T ⊆ D(T ) because t = t − 0 for
6
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
every t ∈ T . Since the two sets have the same cardinality, T = D(T ). Therefore T is closed under subtraction. As T is finite and contains 0, it is a subgroup of G. Since T is also a transversal for G/H, it is a subgroup complement to H. □ 3.1. Singleton directions and primitive quotient transversals. We use the e ) from Section 2. The next proposition explains the notation Σ(T ), dT (a), and Σ(T quotient reduction behind primitive transversals. Proposition 3.2. Let H ≤ G, and let T be a normalized transversal for G/H. Then: (1) Σ(T ) is a subgroup of G/H; (2) the map Σ(T ) −→ G, a 7−→ dT (a), e ) is a subgroup of G, is an injective group homomorphism, its image Σ(T and e ) ∩ H = {0}, e )| = |Σ(T )|; Σ(T |Σ(T (3) one has e ) = T, T + Σ(T
e ) = D(T ), D(T ) + Σ(T
e ); so D(T ) is a union of cosets modulo Σ(T (4) if e ), e ))/Σ(T e ), G = G/Σ(T H = (H + Σ(T and T denotes the image of T in G, then T is a transversal for G/H and e )| |D(T )|; |D(T )| = |Σ(T (5) the transversal T has no nonzero singleton directions. Proof. Put Q = G/H and write s = sT for the normalized section attached to T . The zero direction is singleton, since D0 (T ) = {0}. Let a, b ∈ Σ(T ). Then, for every x ∈ Q, s(x + a) − s(x) = dT (a),
s(x + b) − s(x) = dT (b).
Hence s(x + a + b) − s(x) = s(x + a + b) − s(x + a) + s(x + a) − s(x) = dT (b) + dT (a). Thus a + b is a singleton direction and dT (a + b) = dT (a) + dT (b). Since Q is finite, closure under addition and the presence of 0 imply that Σ(T ) is a subgroup. The displayed identity also shows that a 7→ dT (a) is a group homomorphism. This proves (1) and the homomorphism assertion in (2). For a ∈ Σ(T ) we have π(dT (a)) = a, because dT (a) = s(x + a) − s(x) for every x ∈ Q. Hence the homomorphism e ) is a subgroup of G with |Σ(T e )| = |Σ(T )|. a 7→ dT (a) is injective, and its image Σ(T If dT (a) ∈ H, then a = π(dT (a)) = 0, hence dT (a) = 0. Therefore e ) ∩ H = {0}. Σ(T This proves (2).
TRANSVERSAL DIFFERENCE NUMBERS
7
e ), then If σ = dT (a) ∈ Σ(T s(x + a) = s(x) + σ for every x ∈ Q. As x varies over Q, so does x + a, and therefore translation by σ permutes the elements of T . Thus e ) = T. T + Σ(T Subtracting gives e ) = D(T ), D(T ) + Σ(T e ). so D(T ) is a union of cosets modulo Σ(T Let q♮ : G → G be the quotient map. We prove (4). The image T = q♮ (T ) plainly meets every H-coset. For uniqueness, suppose that q♮ (t1 ) and q♮ (t2 ) lie in the same H-coset. Then e ). t1 − t2 ∈ H + Σ(T e ). Since T + Σ(T e ) = T , the element Write t1 − t2 = h + σ, with h ∈ H and σ ∈ Σ(T t2 + σ belongs to T . But t1 − (t2 + σ) = h ∈ H. Since T is a transversal for G/H, this forces t1 = t2 + σ, hence q♮ (t1 ) = q♮ (t2 ). Thus T is a transversal. Moreover, q♮ (D(T )) = q♮ (T − T ) = T − T = D(T ). e )-cosets, each element of D(T ) has exactly |Σ(T e )| Since D(T ) is a union of Σ(T preimages in D(T ). Hence e )| |D(T )|. |D(T )| = |Σ(T It remains to show that T is primitive. Under the natural identification e )) ≃ (G/H)/Σ(T ), G/H ≃ G/(H + Σ(T suppose that a nonzero class a has singleton fibre for T , and choose a representative a ∈ Q. Then, for some d ∈ G, e ). Da (T ) ⊆ d + Σ(T Indeed, the quotient fibre in direction a is the image of the fibres Da+k (T ), k ∈ e )-coset. For Σ(T ); if that image is a singleton, then each such fibre lies in one Σ(T every k ∈ Σ(T ), the fibre in direction a + k satisfies Da+k (T ) = {s(x + a + k) − s(x) : x ∈ Q} = {s(x + a) + dT (k) − s(x) : x ∈ Q} = Da (T ) + dT (k). e ), whose Thus the union of the fibres above a + Σ(T ) lies in the single coset d + Σ(T e )| = |Σ(T )|. The |Σ(T )| fibres in this union are nonempty and disjoint size is |Σ(T because they lie over distinct quotient directions. Hence each is a singleton. In particular a ∈ Σ(T ), so a = 0, a contradiction. Thus T has no nonzero singleton directions. □ Every transversal becomes primitive after quotienting by its lifted singleton subgroup. This is the structural reason for the lower bound below.
8
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
Proposition 3.3. For every H ≤ G one has δ(G, H) ≥ 2|G/H| − m(G, H). More precisely, for every normalized transversal T one has |D(T )| ≥ 2|G/H| − |Σ(T )|. Proof. Let T be a normalized transversal for G/H. Put Q = G/H, q = |Q|, and k = |Σ(T )|. By the fibre decomposition, X |D(T )| = |Da (T )| ≥ k + 2(q − k) = 2q − k, a∈Q
because the k singleton fibres have size 1 and all other fibres are nonempty of size at least 2. This proves the more precise bound. By Proposition 3.2, the lifted e ) is disjoint from H, so k = |Σ(T e )| ≤ m(G, H). Thus singleton subgroup Σ(T |D(T )| ≥ 2q − m(G, H). Taking the minimum over all transversals proves the proposition.
□
Remark 3.4. Looking at the proof above, if T is a normalized transversal, it is easy to see that the equality |D(T )| = 2|G/H| − m(G, H) holds if and only if |Σ(T )| = m(G, H) and every non-singleton quotient-direction fibre Da (T ) has size exactly 2. 3.2. Cyclic quotients. The bound of Proposition 3.3 is sharp for all cyclic quotients. Theorem 3.5. Let H ≤ G, and suppose that G/H is cyclic of order q. Then δ(G, H) = 2q − m(G, H). Proof. The lower bound is Proposition 3.3. We first handle the residual case m(G, H) = 1. Choose g ∈ G whose image generates G/H. If q = 1, there is nothing to prove. For q > 1, the integer q divides ord(g). The equality ord(g) = q would make ⟨g⟩ a nontrivial subgroup disjoint from H, contradicting residuality. Hence ord(g) ≥ 2q. Now observe that T = {0, g, 2g, . . . , (q − 1)g} is a transversal for G/H, and D(T ) = {kg : −(q − 1) ≤ k ≤ q − 1}. These 2q − 1 elements are distinct because any two exponents in the displayed range differ by an integer of absolute value at most 2q − 2, which is strictly smaller than ord(g). Thus δ(G, H) = 2q − 1 in the residual cyclic case. For the general case, let K ≤ G be a subgroup disjoint from H with |K| = m(G, H), and write m = |K|. Since G/H is cyclic, the image of K in G/H is the unique subgroup of order m. Hence (G/K)/((H + K)/K) ≃ G/(H + K) is cyclic of order s = q/m. The pair (G/K, (H + K)/K) is residual. Indeed, if L/K ≤ G/K were nontrivial and disjoint from (H + K)/K, then L ∩ (H + K) = K. In particular, L ∩ H = {0}, because K ∩ H = {0}. But then L would be a subgroup of G disjoint from H and strictly larger than K, contradicting the maximality of K.
TRANSVERSAL DIFFERENCE NUMBERS
9
By the residual case just proved, there is a transversal B ⊆ G/K for (G/K)/((H + K)/K) such that |B − B| = 2s − 1. Choose representatives B ⊆ G for B, and define T = B + K. Since B represents the quotient G/(H + K) and K maps isomorphically onto its image in G/H, the set T is a transversal for G/H. Moreover, D(T ) = (B − B) + K. Modulo K, this support is exactly B −B, so it is a union of 2s−1 distinct K-cosets. Therefore q |D(T )| = |K|(2s − 1) = m 2 − 1 = 2q − m. m Together with the lower bound, this proves the formula. □ For a cyclic ambient group with a prescribed subgroup, the formula becomes completely explicit. In what follows, we write Cn for the cyclic subgroup of order n, for any n ≥ 1. Corollary 3.6. Let h, q ≥ 1, let G = Chq , and let H ≤ G be the subgroup of order h. If c is the largest divisor of q that is coprime to h, then δ(G, H) = 2q − c. Proof. In a cyclic group there is a unique subgroup of each order. A subgroup of order k intersects H trivially if and only if gcd(k, h) = 1. Since such a subgroup must inject into G/H, its order must also divide q. Therefore m(G, H) is exactly the largest divisor c of q that is coprime to h. The claim follows from Theorem 3.5. □ Example 3.7 (Mixed-prime square-modulus products). Let p1 , . . . , ps be distinct Q primes, let n = i pi , and put G=
s Y i=1
Cp2i ,
H=
s Y
pi Cp2i .
i=1
Then δ(G, H) = 2n − 1. Indeed, the Chinese remainder theorem identifies (G, H) with (Cn2 , nCn2 ). Here |H| = n and |G/H| = n. In Corollary 3.6, with h = q = n, the largest divisor of q coprime to h is 1. Hence δ(G, H) = 2n − 1. Thus square-modulus products with distinct prime factors behave cyclically. The first obstruction not covered by the cyclic analysis is therefore not a product over distinct primes, but a same-prime p-primary quotient of rank at least two. This is the source of the square-plane problem studied later in the manuscript. Such CRT and product constructions are frequent in the algebraic-tiling and finite-abelian factorisation literature [6, 25, 27].
10
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
4. Chains, products, and cross-transversal estimates The aim of this section is to study the behaviour of the invariant δ with respect to subgroup chains and direct products. The technique we use for this study involves slicing a transversal over an intermediate quotient. Kneser’s theorem then upgrades the elementary nonzero-fibre count and gives exact product families with one nonsplit cyclic coordinate and arbitrary split factors. The resulting estimates are cross-transversal bounds based on Kneser’s theorem, and should be read against the structural additive theory of small sumsets in finite abelian groups [10, 12, 28]. We start with some elementary chain bounds: a multiplicative construction and two lower bounds coming from the zero and nonzero quotient fibres. Proposition 4.1. Let H ≤ K ≤ G, and write d0 = δ(K, H),
d1 = δ(G, K),
r = |K/H|,
q = |G/K|.
Then max{d0 + d1 − 1, d0 + (q − 1)r} ≤ δ(G, H) ≤ d0 d1 . Proof. Choose a transversal V ⊆ K for K/H with |D(V )| = d0 , and choose a transversal U ⊆ G for G/K with |D(U )| = d1 . Then T =U +V is a transversal for G/H. Moreover D(T ) = (U + V ) − (U + V ) ⊆ D(U ) + D(V ). Thus δ(G, H) ≤ |D(T )| ≤ |D(U )| |D(V )| = d1 d0 . For the first lower bound, let T be a transversal for G/H, and write Ty = −1 T ∩ πG,K (y) for its slice over y ∈ G/K. Choose one element of each nonempty slice; these elements form a transversal UT for G/K, so |D(UT )| ≥ d1 . Each translated slice is a transversal for K/H, so the zero G/K-fibre of D(T ) contains at least d0 elements. Since D(UT ) meets that zero fibre only in 0, |D(T )| ≥ d0 + d1 − 1. For the second lower bound, one translated slice gives at least d0 elements in the zero fibre. In every nonzero G/K-direction, the cross-difference between two corresponding slices maps onto all of K/H: the two slices each meet every H-coset inside their K-coset. Hence that fibre has at least r = |K/H| elements, and |D(T )| ≥ d0 + (q − 1)r. Taking the minimum over all T proves the proposition.
□
The proof above isolates the point where information is lost: in each nonzero G/K-direction it uses only that a cross-difference of two slices surjects onto K/H. Kneser’s theorem gives a uniform replacement for this crude fibre count. Theorem 4.2. Let H ≤ G, put q = |G/H|, and let A, B ⊆ G be transversals for G/H. Then |A − B| ≥ 2|G/H| − m(G, H).
TRANSVERSAL DIFFERENCE NUMBERS
11
Proof. Let P = Stab(A − B), and let π : G → G/H be the quotient map. Denote by s = |P ∩ H|, and by u = |π(P )|. The exact sequence 0 −→ P ∩ H −→ P −→ π(P ) −→ 0 gives |P | = su. By Kneser’s theorem, applied to A + (−B), |A − B| ≥ |A + P | + |B + P | − |P |. Since A contains one element in each H-coset, the set A + P contains, in each H-coset, at least one coset of P ∩ H. Hence |A + P | ≥ sq. The same argument gives |B + P | ≥ sq and therefore |A − B| ≥ s(2q − u). If s = 1, then P ∩ H = {0}, so P is a subgroup of G disjoint from H. Thus u = |P | ≤ m(G, H), and hence |A − B| ≥ 2q − u ≥ 2q − m(G, H). If s > 1, then u ≤ q, and so |A − B| ≥ s(2q − u) ≥ sq ≥ 2q. Since m(G, H) ≥ 1, this implies |A − B| ≥ 2q ≥ 2q − m(G, H) and the theorem follows.
□
Applying the theorem to pairs of slices in the chain H ≤ K ≤ G replaces the elementary contribution |K/H| in every nonzero G/K-fibre by 2|K/H| − m(K, H). Corollary 4.3. Let H ≤ K ≤ G, and put d0 = δ(K, H),
d1 = δ(G, K), r
= |K/H|,q
= |G/K|,m0
= m(K, H).
Then δ(G, H) ≥ max{d0 + d1 − 1, d0 + (q − 1)(2r − m0 )}. Proof. The bound d0 + d1 − 1 is Proposition 4.1. Let T be a transversal for G/H and slice it above the cosets of K. The zero G/K-fibre contains the difference set of one translated slice and contributes at least d0 elements. For a nonzero direction in G/K, the corresponding fibre contains a translated cross-difference between two slices. After translation into K, these are transversals for K/H, so Theorem 4.2 gives at least 2r − m0 elements. Summing over the q − 1 nonzero directions in G/K gives |D(T )| ≥ d0 + (q − 1)(2r − m0 ). Taking the minimum over T proves the claim.
□
Remark 4.4. Passing to quotients contained in H can only identify differences. If N ≤ H ≤ G, then δ(G/N, H/N ) ≤ δ(G, H). Indeed, the image of a transversal for G/H under the quotient map G → G/N is a transversal for (G/N )/(H/N ), and quotienting can only identify differences.
12
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
Proposition 3.2 gives a more precise form of quotienting for the particular sube ) attached to a transversal T : in that case the image transversal is group Σ(T primitive and the difference support satisfies the exact multiplicative identity e )| |D(T )|. |D(T )| = |Σ(T Applying the chain estimates to the two natural coordinate chains gives the following elementary product bounds. Let Hi ≤ Gi , put qi = |Gi /Hi |,
di = δ(Gi , Hi )
(i = 1, 2).
Then max{d1 +d2 −1, d1 +(q2 −1)q1 , d2 +(q1 −1)q2 } ≤ δ(G1 ×G2 , H1 ×H2 ) ≤ d1 d2 . (4.1) The product of optimal transversals gives the upper bound: if Ti ⊆ Gi is a transversal for Gi /Hi with |D(Ti )| = di , then T1 × T2 is a transversal for (G1 × G2 )/(H1 × H2 ), and D(T1 × T2 ) = D(T1 ) × D(T2 ). Thus the difference support has size d1 d2 . For the lower bounds, apply Proposition 4.1 to the chain H1 × H2 ≤ G1 × H2 ≤ G1 × G2 and then to the symmetric chain H1 × H2 ≤ H1 × G2 ≤ G1 × G2 . The identities δ(G1 × H2 , H1 × H2 ) = δ(G1 , H1 ),
δ(G1 × G2 , G1 × H2 ) = δ(G2 , H2 )
follow from projection and the fixed-coordinate construction. Substituting them in the two chains gives the displayed estimates. The same sharpening applies to products through the two coordinate chains. With mi = m(Gi , Hi ), Corollary 4.3 gives δ(G1 × G2 , H1 × H2 ) ≥ max{d1 + d2 − 1, d1 + (q2 − 1)(2q1 − m1 ), d2 + (q1 − 1)(2q2 − m2 )}. Remark 4.5. Since mi ≤ qi , the Kneser-sharpened product terms dominate the corresponding elementary product terms above. The improvement is strict in the term where the factor providing mi is nonsplit, meaning mi < qi , and the other quotient is nontrivial. The Cartesian-product construction need not be optimal. Example 4.6 (Products need not be multiplicative). The cyclic formula gives δ(C4 , 2C4 ) = 3,
δ(C9 , 3C9 ) = 5.
However (C4 × C9 , 2C4 × 3C9 ) ≃ (C36 , 6C36 ). By Corollary 3.6, δ(C36 , 6C36 ) = 11. Thus the optimal value for the product pair is 11, not 15.
TRANSVERSAL DIFFERENCE NUMBERS
13
The cross-transversal estimate is exact after adjoining a split factor, provided the base pair already attains the lower bound. Corollary 4.7. Let H0 ≤ G0 , let L be a finite abelian group, for which we write q0 = |G0 /H0 |, and m0 = m(G0 , H0 ). Then δ(G0 × L, H0 × {0}) ≥ |L|(2q0 − m0 ). If δ(G0 , H0 ) = 2q0 − m0 , the inequality above holds with equality. Proof. Let T be a transversal for (G0 × L)/(H0 × {0}). For each ℓ ∈ L, define Aℓ = {g ∈ G0 : (g, ℓ) ∈ T }. Because quotient cosets are indexed by (G0 /H0 ) × L, each Aℓ is a transversal for G0 /H0 . For each ℓ ∈ L, the L-coordinate ℓ fibre of D(T ) contains (Aℓ − A0 ) × {ℓ}. By Theorem 4.2, |Aℓ − A0 | ≥ 2q0 − m0 . These fibres are disjoint for different ℓ, so |D(T )| ≥ |L|(2q0 − m0 ). Taking the minimum over T proves the lower bound. For the upper bound under the displayed hypothesis, choose a transversal T0 ⊆ G0 for G0 /H0 with |D(T0 )| = 2q0 − m0 . Then T0 × L is a transversal for (G0 × L)/(H0 × {0}), and D(T0 × L) = D(T0 ) × L. Thus |D(T0 × L)| = |L| |D(T0 )| = |L|(2q0 − m0 ), which proves equality.
□
Together with the cyclic quotient formula, this gives the main exact product family of the section. Corollary 4.8. Let p be prime, let 1 ≤ b < a, and let L be a finite abelian group. Then δ(Cpa × L, pb Cpa × {0}) = |L|(2pb − 1). Proof. For the base pair G0 = Cpa ,
H0 = pb Cpa ,
the quotient has size pb . Since 1 ≤ b < a, the subgroup H0 is nonzero, and every nontrivial subgroup of the cyclic p-group Cpa meets H0 nontrivially. Therefore m(G0 , H0 ) = 1. The cyclic quotient formula, Theorem 3.5, gives δ(G0 , H0 ) = 2pb − 1 = 2|G0 /H0 | − m(G0 , H0 ). Corollary 4.7 now gives the desired equality after adjoining the split factor L.
□
14
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
Remark 4.9. Corollary 4.8 is not a product multiplicativity statement: the added factor is split, with subgroup pb Cpa × {0}. It does not cover a second nonsplit p-primary coordinate, which is why ((Z/p2 Z)2 , p(Z/p2 Z)2 ) is the first genuinely new same-prime case. 5. Noncyclic residual obstructions The cyclic quotient formula shows that the fibre lower bound is sharp for every cyclic quotient. Noncyclic residual quotients behave differently: the first obstruction is already visible in a quotient plane of order four, and it separates the cyclic theory from the higher-rank phenomena studied later. The two-torsion obstruction gives a strict improvement whenever the quotient contains a two-dimensional 2-torsion plane. Theorem 5.1. Let H ≤ G be residual, so that m(G, H) = 1. Suppose that G/H contains a subgroup isomorphic to C2 × C2 . Then every transversal T for G/H satisfies |D(T )| ≥ 2|G/H| + 1. In particular, the residual fibre lower bound 2|G/H| − 1 is not sharp for such a pair. Proof. Let Q = G/H, let q = |Q|, and normalize T , with associated section s : Q → G. Since the pair is residual, Proposition 3.2 implies that no nonzero quotient direction can be singleton. Therefore |Da (T )| ≥ 2
(a ∈ Q, a ̸= 0).
For directions of order two there is a stronger parity fact. If a ∈ Q has order two, then a = −a, hence Da (T ) = −Da (T ). No element of this fibre can be fixed by negation: if d = −d, then 2d = 0 and π(d) = a ̸= 0, so ⟨d⟩ is a nontrivial subgroup disjoint from H. Thus every ordertwo direction has an even fibre of size at least 2. Choose a subgroup P = {0, a, b, c} ≤ Q,
c = a + b,
with P ≃ C2 × C2 . We claim that the three nonzero fibres over a, b, c cannot all have size 2. Suppose, to the contrary, that they do. Put A = s(a),
B = s(b),
C = s(c).
Since each of the three fibres is stable under negation and has two elements, we have C − B = εA, C − A = ηB, B − A = θC for some signs ε, η, θ ∈ {±1}. The first two identities give B + εA = A + ηB. If ε = 1 and η = −1, this gives 2B = 0. If ε = −1 and η = 1, it gives 2A = 0. If ε = −1 and η = −1, it gives 2(A − B) = 0. Finally, if ε = η = 1, then C = A + B; using B − A = θC gives either 2A = 0 or 2B = 0. In all cases, one of A, B, or A − B has order two. Its image in Q is respectively a, b, or a + b, hence nonzero. The subgroup it generates is therefore nontrivial and disjoint from H, again contradicting residuality. Thus at least one of the three fibres over a, b, c has size at least 4.
TRANSVERSAL DIFFERENCE NUMBERS
15
Counting quotient-direction fibres now gives X |D(T )| = |Du (T )| u∈Q
≥ 1 + 2 + 2 + 4 + 2(q − 4) = 2q + 1. This proves the theorem.
□
For square-modulus 2-groups this gives an exact value in rank two. The follwing corollary is immediate. Corollary 5.2. Let r ≥ 2, let G = (Z/4Z)r ,
H = 2G.
Then δ(G, H) ≥ 2r+1 + 1. For r = 2, the equality δ(G, H) = 9 is realized by the transversal T = {0, 1}2 . The preceding obstruction is specific to quotient directions of order two. For odd primes there is no analogous negation parity argument. The same square-modulus construction is residual for every prime, and the coordinate box gives the basic upper bound. Proposition 5.3. Let p be a prime and let G = (Z/p2 Z)r ,
H = pG.
Then m(G, H) = 1. Moreover the coordinate box gives δ(G, H) ≤ (2p − 1)r . Proof. Let 0 ̸= g ∈ G. If g has order p, then g ∈ pG = H. If g has order p2 , then pg is a nonzero element of ⟨g⟩ ∩ H. Hence every nontrivial subgroup of G meets H nontrivially, and therefore m(G, H) = 1. The coordinate box Bpr = {0, 1, . . . , p − 1}r ⊆ (Z/p2 Z)r is a transversal for G/H. Its difference support is D(Bpr ) = {−(p − 1), . . . , p − 1}r , which has size (2p − 1)r . This proves the upper bound.
□
Thus, for odd p, the pair (Z/p2 Z)2 , p(Z/p2 Z)2
is the first same-prime residual case not covered by the cyclic formula, the twotorsion obstruction, or the one-nonsplit-coordinate product theorem. The rest of the paper rewrites its transversals as graphs F2p → F2p and studies the resulting carry-corrected finite-field difference images.
16
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
6. The odd square-plane problem We now specialize to the first unresolved same-prime residual case. Throughout this section p is an odd prime, Gp = (Z/p2 Z)2 ,
Hp = pGp .
By Proposition 5.3, the pair is residual and the coordinate box gives δ(Gp , Hp ) ≤ (2p − 1)2 . We rewrite its transversals in finite-field terms and prove a uniform lower bound towards the box value. The resulting corrected-derivative images are finite-field image sets; these are adjacent to the sum-product/expander literature [2, 16] and, for graph/function language to relative difference sets and planar functions works such as [19]. 6.1. Carry-corrected derivative images. We identify the quotient Gp /Hp with F2p . For x ∈ F2p , let [x] ∈ {0, 1, . . . , p − 1}2 denote the coordinatewise standard lift. Every normalized transversal for Gp /Hp has a unique form Tf = {[x] + p[f (x)] : x ∈ F2p }, where f : F2p → F2p satisfies f (0) = 0. This normalization is harmless for difference supports: translating Tf by an element of pGp subtracts a constant from f . For u, x ∈ F2p , define the carry vector cu (x) =
[x + u] − [x] − [u] ∈ F2p . p
Here the numerator is computed in Z2 using standard representatives; its coordinates are either 0 or −p, so cu (x) has coordinates 0 or −1 modulo p. We then define the carry-corrected derivative du f (x) = f (x + u) − f (x) + cu (x), and its image Au (f ) = {du f (x) : x ∈ F2p } ⊆ F2p . The finite-field parametrisation gives an exact fibre decomposition of the difference support. Lemma 6.1. For every f : F2p → F2p one has X |Tf − Tf | = |Au (f )|. u∈F2p
Moreover A0 (f ) = {0}. Proof. The difference between the representative above x+u and the representative above x is [x + u] + p[f (x + u)] − [x] − p[f (x)] = [u] + p f (x + u) − f (x) + cu (x) = [u] + p du f (x) in (Z/p2 Z)2 . In the quotient fibre u ∈ Gp /Hp ≃ F2p , the possible p-parts are exactly Au (f ). The quotient fibres are disjoint, so summing over all u gives the formula. For u = 0 one has c0 (x) = 0 and d0 f (x) = 0, hence A0 (f ) = {0}. □
TRANSVERSAL DIFFERENCE NUMBERS
17
The coordinate box corresponds to f = 0, and its support has size (2p − 1)2 . This motivates the central conjecture. Conjecture 6.2. For every odd prime p, δ (Z/p2 Z)2 , p(Z/p2 Z)2 = (2p − 1)2 . Equivalently, for every function f : F2p → F2p , X |Au (f )| ≥ (2p − 1)2 . u∈F2p
The general residual fibre lower bound gives only |Tf − Tf | ≥ 2p2 − 1. Thus the conjecture asks for an additional (2p − 1)2 − (2p2 − 1) = 2(p − 1)2 forced differences coming from the rank-two same-prime geometry. 6.2. Cycle and curl identities. The deterministic input is a pair of elementary identities using only that the corrected derivatives come from a global quotient section. Lemma 6.3. Let p be an odd prime and let f : F2p → F2p . For all u, v, x ∈ F2p one has the curl identity du f (x + v) − du f (x) = dv f (x + u) − dv f (x). Moreover, for every nonzero u ∈ F2p and every affine u-line, x + ⟨u⟩ = {x + iu : 0 ≤ i ≤ p − 1}, one has the cycle identity p−1 X
du f (x + iu) = −u.
i=0
Consequently: (1) |Au (f )| ≥ 2 for every u ̸= 0; (2) if |Au (f )| = 2, then Au (f ) is contained in an affine line parallel to ⟨u⟩. Proof. Expanding the definition of du f gives du f (x + v) − du f (x) = [f (x + u + v) − f (x + v)] − [f (x + u) − f (x)] + cu (x + v) − cu (x), and the analogous expression with u and v interchanged. The f -terms are identical. The carry terms are also identical, since cu (x + v) − cu (x) =
[x + u + v] − [x + v] − [x + u] + [x] = cv (x + u) − cv (x). p
This proves the curl identity. For the cycle identity, sum in Gp the p successive differences from the representative above x + iu to the representative above x + (i + 1)u: [u] + p du f (x + iu),
0 ≤ i ≤ p − 1.
18
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
These differences go once around the affine cycle, so their sum is zero in Gp : p−1 X
p[u] + p
du f (x + iu) = 0 (mod p2 ).
i=0
Dividing by p modulo p gives u+
p−1 X
du f (x + iu) = 0
i=0
in F2p . If Au (f ) = {a} for some u ̸= 0, then the cycle identity gives pa = 0 = −u, a contradiction. Hence |Au (f )| ≥ 2 for every nonzero u. Finally suppose Au (f ) = {a, b}. On a fixed affine u-line, let n be the number of points at which du f takes the value a. Then the other p − n points take the value b, and the cycle identity gives na + (p − n)b = n(a − b) = −u. The cases n = 0 and n = p would make the left-hand side zero, so n is nonzero modulo p. Thus a − b = −n−1 u ∈ ⟨u⟩. Therefore Au (f ) lies in an affine line parallel to ⟨u⟩. □ 6.3. A deterministic lower bound. Two independent quotient directions with minimal derivative images already force the conjectural box lower bound. Lemma 6.4. Let p be an odd prime and let f : F2p → F2p . Suppose there are two linearly independent directions u, v ∈ F2p such that |Au (f )| = |Av (f )| = 2. Then |Tf − Tf | ≥ (2p − 1)2 . Proof. By Lemma 6.3, the two images Au (f ) and Av (f ) are respectively contained in affine lines parallel to ⟨u⟩ and ⟨v⟩. Therefore du f (x + v) − du f (x) ∈ ⟨u⟩,
dv f (x + u) − dv f (x) ∈ ⟨v⟩.
By the curl identity these two quantities are equal. Since u and v are independent, ⟨u⟩ ∩ ⟨v⟩ = {0}, so both quantities vanish. Hence du f is invariant in the v-direction and dv f is invariant in the u-direction. Every nonzero w ∈ F2p can be written uniquely as w = λu + µv,
λ, µ ∈ Fp .
If exactly one of λ, µ is nonzero, then Lemma 6.3 gives |Aw (f )| ≥ 2. Assume now that λµ ̸= 0, and choose representatives λ, µ ∈ {1, . . . , p − 1}. Following first λ steps in the u-direction and then µ steps in the v-direction, define Bλ (x) =
λ−1 X i=0
du f (x + iu),
Cµ (x) =
µ−1 X
dv f (x + λu + jv).
j=0
The direct corrected derivative dw f (x) differs from Bλ (x)+Cµ (x) by a constant depending only on λ, µ, u, v and on our standard-lift carry convention, not on x. This is just the telescoping of the f -increments along the chosen path; the discrepancy
TRANSVERSAL DIFFERENCE NUMBERS
19
between the path carry and the standard carry for w is independent of the starting point. Hence Aw (f ) contains a translate of the sum of the two images of Bλ and Cµ . Since du f is invariant in the v-direction, Bλ depends only on the u-coordinate of x and its image lies in an affine line parallel to ⟨u⟩. Moreover Bλ differs from the direct derivative dλu f by a constant, so | im Bλ | = |Aλu (f )| ≥ 2. Similarly, because dv f is invariant in the u-direction, Cµ depends only on the vcoordinate, has image contained in an affine line parallel to ⟨v⟩, and | im Cµ | = |Aµv (f )| ≥ 2. As the u- and v-coordinates of x vary independently, the pair (Bλ (x), Cµ (x)) runs over im Bλ × im Cµ . Since the two image directions are parallel to the independent lines ⟨u⟩ and ⟨v⟩, addition is injective on their product. Therefore |Aw (f )| ≥ | im Bλ | | im Cµ | ≥ 4 for every mixed direction w = λu + µv with λµ ̸= 0. There are p − 1 nonzero multiples of u, p − 1 nonzero multiples of v, and (p − 1)2 mixed directions. Using Lemma 6.1, we get X |Tf − Tf | = 1 + |Aw (f )| w̸=0
≥ 1 + 2(p − 1) + 2(p − 1) + 4(p − 1)2 = (2p − 1)2 . □ This dichotomy gives an unconditional lower bound for every odd prime. Theorem 6.5. For every odd prime p, δ (Z/p2 Z)2 , p(Z/p2 Z)2 ≥ 3p2 − p − 1. Equivalently, every transversal T for Gp /Hp satisfies |D(T )| ≥ 3p2 − p − 1. Proof. Normalize the transversal and write it as T = Tf . Let S = {u ∈ F2p \ {0} : |Au (f )| = 2}. If S contains two independent directions, then Lemma 6.4 gives the stronger bound |Tf − Tf | ≥ (2p − 1)2 . Since (2p − 1)2 − (3p2 − p − 1) = (p − 1)(p − 2) ≥ 0 for p ≥ 3, the desired estimate follows in this case. It remains to consider the case where S contains no two independent directions. Then S is contained in a single one-dimensional subspace of F2p , so |S| ≤ p − 1.
20
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
By Lemma 6.3, every nonzero direction contributes at least 2, and every nonzero direction outside S contributes at least 3. Together with A0 (f ) = {0}, this gives X |Tf − Tf | = 1 + |Au (f )| u̸=0
≥ 1 + 2|S| + 3 p2 − 1 − |S|
= 3p2 − 2 − |S| ≥ 3p2 − p − 1. This proves the theorem.
□
The remaining gap to the conjectural box value is (p − 1)(p − 2); Section 7 gives asymptotic evidence for Conjecture 6.2. 6.4. Small-prime square-plane certificates. We verified the conjecture for p = 3 and p = 5 by deterministic Python computations using the graph parametrisation and fibre decomposition above. For p = 5 the search also uses the cycle and curl constraints from this section and the action of GL2 (F5 ). Since T − T is negationinvariant and 0 is the only self-inverse element in an odd-order group, |T − T | is odd. Thus it suffices to exclude the largest odd support below the box value: the computations rule out |Tf − Tf | ≤ 23 for p = 3 and |Tf − Tf | ≤ 79 for p = 5. The coordinate boxes attain 25 and 81, so δ (Z/9Z)2 , 3(Z/9Z)2 = 25, δ (Z/25Z)2 , 5(Z/25Z)2 = 81. The Python scripts used and the results could be consulted on our online companion github.com/georgeturcasubb/transversals. We could not complete a verification of the conjecture for p = 7 due to the high computational complexity. However, in these case we conducted many unsuccessful searches for transversals that could give rise to counter-examples. 7. Asymptotic evidence for the square-plane conjecture The exact values in Subsection 6.4 cover the first two odd primes. We add two asymptotic pieces of evidence: a uniformly random lifting satisfies the box lower bound with probability tending to one, and no fixed integer-polynomial rule produces counterexamples for all sufficiently large primes. 7.1. Random liftings. Call a nonzero direction u = (u1 , u2 ) ∈ F2p mixed if u1 u2 ̸= 0. For a function f : F2p → F2p , define B(f ) = {u ∈ F2p : u1 u2 ̸= 0 and |Au (f )| ≤ 3}. Thus B(f ) records mixed directions whose corrected derivative image is too small for the box contribution. Theorem 7.1. Let p be an odd prime. Choose f : F2p → F2p uniformly at random, with the values f (x) independent and uniformly distributed. Then 2 p p p 3 Pr |Tf − Tf | < (2p − 1)2 ≤ p8 . f p2p In particular, Pr |Tf − Tf | ≥ (2p − 1)2 −→ 1 f
(p → ∞).
TRANSVERSAL DIFFERENCE NUMBERS
21
The same conclusion holds for uniformly random normalized liftings f (0) = 0. Proof. Before normalization, uniform functions give the uniform model on transversals for Gp /Hp ; subtracting f (0) only translates Tf by an element of pGp . Fix f . By Lemma 6.1, X |Tf − Tf | = |Au (f )|. u∈F2p
The zero direction contributes 1, and Lemma 6.3 gives at least 2 from every nonzero direction. There are 2(p − 1) nonzero axis directions and (p − 1)2 mixed directions; the mixed directions outside B(f ) contribute at least 4, while those in B(f ) still contribute at least 2. Hence |Tf − Tf | ≥ 1 + 2 · 2(p − 1) + 2|B(f )| + 4 (p − 1)2 − |B(f )| = (2p − 1)2 − 2|B(f )|. Thus B(f ) = ∅ is sufficient for the box lower bound, and failure forces B(f ) ̸= ∅. We bound this last event. Fix a mixed direction u and a set S ⊆ F2p with |S| ≤ 3. The translation x 7→ x + u partitions F2p into p disjoint p-cycles. On one cycle, write xi = x0 + iu and yi = f (xi ). The condition du f (xi ) ∈ S is yi+1 − yi ∈ S − cu (xi ). After choosing y0 , there are at most 3 choices for each edge increment; ignoring the closing condition only overcounts. Thus one cycle has probability at most p2 3p . p2p The p cycles use disjoint values of f , hence are independent. The probability that p p2 3p this fixed S contains all values of Au (f ) is therefore at most p2p . Hence there P3 2 are at most j=0 pj ≤ p6 subsets of F2p of size at most 3. It follows that, for the fixed mixed u, 2 p p p 3 6 Pr |Au (f )| ≤ 3 ≤ p . f p2p Finally, there are (p − 1)2 < p2 mixed directions. A union bound gives 2 p p p 3 8 Pr(B(f ) ̸= ∅) ≤ p . f p2p Since failure of the box lower bound implies B(f ) ̸= ∅, this proves the estimate. Its logarithm is −2p2 log p + p2 log 3 + O(p log p), which tends to −∞. □ 7.2. Fixed-polynomial liftings. The random theorem shows that counterexamples, if they exist, are rare among all functions. We next rule out another natural source: liftings defined by one fixed polynomial rule as the prime varies. Let g = (g1 , g2 ) ∈ Z[X, Y ]2 be fixed. For a prime p, let gp : F2p → F2p be its reduction modulo p, and set Tg,p = {[z] + p[gp (z)] : z ∈ F2p } ⊆ (Z/p2 Z)2 . The word fixed is essential: for a single prime p, every function F2p → F2p has polynomial representatives of degree less than p in each variable, for instance by finite-field interpolation. The theorem excludes only one integer-polynomial rule independent of p. This fixed-polynomial setting is close to value-set questions for
22
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
polynomial maps over finite fields [15] and to finite-field polynomial/rational imageexpansion results [3]. Theorem 7.2. For every fixed g = (g1 , g2 ) ∈ Z[X, Y ]2 , there is an integer Bg such that, for every prime p > Bg , |Tg,p − Tg,p | ≥ (2p − 1)2 . The proof uses a nonzero-Jacobian image bound, large-rectangle estimates, and a degenerate-Jacobian classification. Lemma 7.3. Fix E ≥ 1. Let F = (P, Q) : A2Fp → A2Fp be a polynomial map with deg P, deg Q ≤ E and det JF ̸≡ 0. If R ⊆ F2p , then |F (R)| ≥
|R| − CE p , E2
where one may take CE = max{1, 2(E − 1)}. Proof. Let ∆ = det JF . Its zero set has at most CE p points by the elementary polynomial zero bound over finite fields. For a ∈ F2p , the fibre F −1 (a) is cut out by two plane curves of degrees at most E. Discard any common fibre components contained in {∆ = 0}; those points are already excluded below. Off the critical curve, the remaining fibre curves have no common component: otherwise their gradients would be dependent at a smooth point of that component, forcing ∆ to vanish generically there. Bezout’s theorem for plane curves [5] then bounds every noncritical fibre by E 2 geometric, hence rational, points. Thus the points of R outside {∆ = 0} map with fibres of size at most E 2 , and |F (R)| ≥
|R| − CE p . E2 □
We also use three elementary estimates on large rectangles. Let I, J ⊆ Fp be intervals of consecutive standard residues, each of size at least p/2, and put R = I × J. (1) A nonzero linear form ℓ has |ℓ(R)| ≥ p/2. This is immediate if one coefficient vanishes, and otherwise follows from Cauchy–Davenport [28]. (2) If P ∈ Fp [S] is nonconstant of degree at most d, then |P (S0 )| ≥ |S0 |/d for every S0 ⊆ Fp . (3) If Q ∈ Fp [X, Y ] is nonconstant of degree at most d, then every nonempty fibre has at most dp points by the elementary zero bound, so |Q(R)| ≥ |R|/(dp) ≥ p/(4d). The second input handles the degenerate Jacobian case, using singular subspaces of 2 × 2 matrices. Lemma 7.4. Let k be an infinite field and let L ⊆ M2 (k) be a linear subspace such that every element of L is singular. Then either all matrices in L have a common nonzero kernel vector, or all their images lie in a common line in k 2 .
TRANSVERSAL DIFFERENCE NUMBERS
23
Proof. If L = 0, both alternatives hold. Otherwise choose a nonzero rank-one 1 0 matrix in L and change source and target bases so that it is E = . For 0 0 a b B= ∈ L, the matrix E + tB is singular for every t ∈ k. Since k is infinite, c d det(E + tB) = td + t2 (ad − bc) vanishes as a polynomial in t. Hence d = 0. Since B is singular, also bc = 0. Linearity forces either b = 0 for all B ∈ L, or c = 0 for all B ∈ L; otherwise a linear combination would have both off-diagonal entries nonzero and would be nonsingular. These are exactly the common-kernel and common-image cases. □ This gives the needed classification for polynomial maps with singular Jacobian differences. Lemma 7.5. Let k be a field of characteristic zero, and let g : k 2 → k 2 be a polynomial map satisfying det(Jg(w) − Jg(z)) = 0
for all z, w ∈ k 2 .
Then there are A ∈ M2 (k) and c ∈ k 2 such that one of the following holds: g(z) = Az + G(ℓ(z)) + c for a nonzero linear form ℓ : k 2 → k and a one-variable polynomial map G : k → k 2 , or g(z) = Az + wφ(z) + c for some nonzero w ∈ k 2 and some polynomial φ ∈ k[X, Y ]. Proof. Fix z0 and let L be the linear span of {Jg(z) − Jg(z0 ) : z ∈ k 2 }. The determinant quadratic form vanishes on each generator and on each difference of two generators. Its polar form therefore vanishes on pairs of generators, so the determinant vanishes on all of L. Lemma 7.4 gives a common kernel vector or a common image line. Write Jg(z) = A + N (z) with N (z) ∈ L. If L has a common kernel vector r ̸= 0, the directional derivative of g − Az along r is zero. After a linear change of coordinates, g − Az is independent of one coordinate and has the form G(ℓ(z)) + c. If L has common image line kw, all derivatives of g − Az lie in kw. A linear form annihilating w is constant on g − Az, so g − Az − c takes values in kw and g(z) = Az + wφ(z) + c. □ Proof of Theorem 7.2. We first remove affine terms, which do not change the support size. Adding a constant translates Tg,p by an element of pGp . Adding a linear term Az applies the automorphism UA (t) = t + pAt,
t ∈ (Z/p2 Z)2 ,
where t denotes reduction modulo p; its inverse is U−A . Thus both operations preserve |Tg,p − Tg,p |, and affine-linear liftings have the coordinate-box support (2p − 1)2 . Let D = deg g. If D ≤ 1, we are done. Assume first that D ≥ 2 and ∆g (z, v) = det Jg(z + v) − Jg(z)
24
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
is not the zero polynomial over Q. Expand ∆g in the z-variables and choose a nonzero coefficient polynomial H(v). After excluding finitely many primes depending only on g, the reduction of H is nonzero; hence, for all sufficiently large p, all but Og (p) directions v ∈ F2p have H(v) ̸= 0. For these directions, the finite difference Fv (z) = gp (z + v) − gp (z) has degree at most D − 1 and nonzero Jacobian determinant. For each good v, choose a carry cell Rv : a rectangular cell of standard residue representatives on which cv (z) is constant, with both side lengths at least p/2, so |Rv | ≥ p2 /4. On Rv , the map z 7→ dv gp (z) is a constant translate of Fv (z). By Lemma 7.3, with E = D − 1, p2 /4 − CE p . E2 There are p2 − Og (p) good directions, each contributing ≫g p2 , so Lemma 6.1 gives X |Tg,p − Tg,p | = |Av (gp )| ≫g p4 . |Av (gp )| ≥
v
For all sufficiently large primes this exceeds (2p − 1)2 , proving the generic case. It remains to treat the case ∆g ≡ 0. Then det(Jg(w) − Jg(z)) = 0 for all z, w over Q, so Lemma 7.5 applies. Excluding the finitely many primes where the rational classification data have denominator problems, where the nonzero linear form or target vector vanishes after reduction, where the relevant leading forms vanish, or where the characteristic is too small for the degree bounds, we remove the affine part as above. One of two forms remains. First suppose g(z) = G(ℓ(z)), with ℓ ̸= 0. If m = deg G ≤ 1, the map is affinelinear, already handled. Otherwise, for all sufficiently large primes and every v with ℓ(v) ̸= 0, the difference G(S + ℓ(v)) − G(S) has a nonconstant coordinate of degree m − 1. On a large carry cell, the linear-form and univariate image estimates above give p |Av (gp )| ≥ . 2(m − 1) The p2 − p such directions contribute ≫g p3 , which exceeds (2p − 1)2 for all sufficiently large p. Second suppose g(z) = wφ(z), with w ̸= 0. If m = deg φ ≤ 1, the map is affinelinear, already handled. Otherwise, for all sufficiently large primes the highest homogeneous part φm remains nonconstant. The directions v for which Dv φm vanishes identically form a proper linear subspace, so all but at most p directions give a nonconstant difference φ(z + v) − φ(z) of degree at most m − 1. On a large carry cell, dv gp is a constant translate of w(φ(z + v) − φ(z)), so multiplication by w ̸= 0 preserves cardinality and the bivariate image estimate gives p . |Av (gp )| ≥ 4(m − 1) Again the total contribution is ≫g p3 , which exceeds (2p − 1)2 for all sufficiently large p. The generic and degenerate cases give an integer Bg such that the claimed inequality holds for every prime p > Bg . □
TRANSVERSAL DIFFERENCE NUMBERS
25
Remark 7.6. These results do not settle Conjecture 6.2: they exclude random counterexamples with high probability and fixed algebraic rules for large p, while the conjecture allows arbitrary p-dependent liftings. 8. Open problems and outlook The cyclic and one-nonsplit-coordinate cases are settled by the fibre lower bound, singleton reduction, and Kneser estimate. The remaining obstruction is the sameprime nonsplit rank-two case: the odd-prime box statement is still conjectural, and the fixed-prime certificates and asymptotic evidence have only the limited scope proved above. The fixed-polynomial evidence also resonates with the broader finite-field polynomial-method tradition, exemplified by Dvir’s finite-field Kakeya breakthrough [7]; however, our result is not a Kakeya theorem and uses only the polynomial image constraints developed above. 8.1. Square-plane problem. The central open P problem is Conjecture 6.2. In the notation of Lemma 6.1, it asks whether u |Au (f )| ≥ (2p − 1)2 for every f , with equality for the coordinate box. Theorem 6.5 leaves gap (p − 1)(p − 2), so any counterexample would have to realize a structured loss among low correctedderivative images. Sharper bounds for low corrected-derivative images may require incidence technology beyond the cycle-curl identities used here, such as Rudnev’s [21] point-plane incidence theorem and the Stevens–de Zeeuw point-line incidence bound over arbitrary fields [26]. Problem 8.1. Let p be odd and let f : F2p → F2p . Classify, or sharply bound, the oriented nonzero directions u for which |Au (f )| ≤ 3. In particular, decide whether any loss from these low images is necessarily compensated by larger corrected-derivative images in the remaining directions. 8.2. Higher-rank square-modulus quotients. The coordinate box suggests the following higher-rank analogue. Conjecture 8.2. For every odd prime p and every r ≥ 1, δ (Z/p2 Z)r , p(Z/p2 Z)r = (2p − 1)r . For higher-rank quotients, one natural next layer could be iterated sumsetgrowth technology in the Plünnecke–Ruzsa tradition [18,22], together with arbitraryabelian-group small-doubling structure [9]. The cases r = 1 and r = 2 are respectively the cyclic residual theorem and Conjecture 6.2. For r ≥ 3, the same graph-and-fibre identity holds, and the ranktwo argument suggests looking for a frame of low directions and product-type lower bounds for mixed directions. 8.3. Primitive quotients and residual geometries. The primitive quotient reduction separates singleton directions from the primitive quotient part, so the remaining classification can be phrased in primitive terms. Problem 8.3. Classify the pairs H ≤ G for which every primitive transversal T satisfies |D(T )| ≥ 2|G/H| − 1, and identify the primitive quotient geometries that force a strict improvement.
26
M. BARCAU, V. PAŞOL, AND G. C. ŢURCAŞ
Cyclic residual quotients attain the bound 2|G/H| − 1; residual quotients containing a C2 × C2 plane do not. The product results control one nonsplit cyclic coordinate with arbitrary split factors, leaving the next case. Qr Qr Problem 8.4. Let p be prime, G = i=1 Cpai , and H = i=1 pbi Cpai , with 1 ≤ bi < ai for at least two indices. Determine δ(G, H), or give sharp lower bounds in terms of the nonsplit p-primary coordinates. The square-plane case is the smallest instance of Problem 8.4. Resolving it would clarify the first residual nonsplit geometry left open by the transversal difference number. Code and data availability The computations mentioned in Subsection 6.4 were carried using Python and are released in the form of an online companion on GitHub at the link below https://github.com/georgeturcasubb/transversals Use of Artificial Intelligence Tools The authors used OpenAI ChatGPT Deep Research, accessed through ChatGPT to help locate and organize potentially relevant bibliographic material. The authors also used OpenAI Codex with GPT-5.5, accessed through the Codex agentic programming environment, to assist with Python experiments, realization of the GitHub repository and copy-editing of the manuscript. These tools were used as research aids, not as authors. In line with the transparency and human-responsibility principles of the Leiden Declaration on Artificial Intelligence and Mathematics [14], the human authors checked the sources, code, numerical results and take full responsibility for the results presented in the article. References [1] Taras Banakh and Volodymyr Gavrylkiv, Difference bases in finite Abelian groups, Acta Scientiarum Mathematicarum 85 (2019), no. 1–2, 119–137, available at 1704.02471. [2] Jean Bourgain, Nets H. Katz, and Terence C. Tao, A sum-product estimate in finite fields, and applications, Geometric and Functional Analysis 14 (2004), no. 1, 27–57, available at math/0301343. [3] Boris Bukh and Jacob Tsimerman, Sum-product estimates for rational functions, Proceedings of the London Mathematical Society 104 (2012), no. 1, 1–26, available at 1002.2554. [4] A. T. Butson, Relations among generalized Hadamard matrices, relative difference sets, and maximal length linear recurring sequences, Canadian Journal of Mathematics 15 (1963), 42– 48. [5] David A. Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra, 5th ed., Undergraduate Texts in Mathematics, Springer, Cham, 2025. [6] Michael Dinitz, Full rank tilings of finite Abelian groups, SIAM Journal on Discrete Mathematics 20 (2006), no. 1, 160–170. [7] Zeev Dvir, On the size of kakeya sets in finite fields, Journal of the American Mathematical Society 22 (2009), no. 4, 1093–1097, available at 0803.2336. [8] G. A. Freiman, Foundations of a structural theory of set addition, Translations of Mathematical Monographs, vol. 37, American Mathematical Society, Providence, RI, 1973. [9] Ben Green and Imre Z. Ruzsa, Freiman’s theorem in an arbitrary abelian group, Journal of the London Mathematical Society 75 (2007), no. 1, 163–175, available at math/0505198. [10] David J. Grynkiewicz, Structural additive theory, Developments in Mathematics, vol. 30, Springer, Cham, 2013.
TRANSVERSAL DIFFERENCE NUMBERS
27
[11] Georg Hajós, Über einfache und mehrfache Bedeckung des n-dimensionalen Raumes mit einem Würfelgitter, Mathematische Zeitschrift 47 (1942), 427–467. [12] J. H. B. Kemperman, On small sumsets in an abelian group, Acta Mathematica 103 (1960), 63–88. [13] Martin Kneser, Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen, Mathematische Zeitschrift 61 (1954), 429–434 (German). [14] Leiden Declaration Working Group, Leiden declaration on artificial intelligence and mathematics, 2026. https://leidendeclaration.ai/; accessed June 2026. [15] Gary L. Mullen, Daqing Wan, and Qiang Wang, Value sets of polynomial maps over finite fields, The Quarterly Journal of Mathematics 64 (2013), no. 4, 1191–1196, available at 1210. 8119. [16] Brendan Murphy and Giorgis Petridis, A second wave of expanders in finite fields, Combinatorial and additive number theory ii: Cant, new york, ny, usa, 2015 and 2016, 2017, pp. 215– 238. [17] Chris Peikert and Zachary Pepin, Vive Galois! part 1: Optimal SIMD packing and packed bootstrapping for FHE, Theory of cryptography – TCC 2025, 2026, pp. 185–219. [18] Helmut Plünnecke, Eine zahlentheoretische anwendung der graphentheorie, Journal für die reine und angewandte Mathematik 243 (1970), 171–183. [19] Alexander Pott, Kai-Uwe Schmidt, and Yue Zhou, Semifields, relative difference sets, and bent functions, Algebraic curves and finite fields: Cryptography and other applications, 2014, pp. 161–178. [20] László Rédei, Die neue theorie der endlichen abelschen gruppen und verallgemeinerung des hauptsatzes von hajós, Acta Mathematica Academiae Scientiarum Hungaricae 16 (1965), 329–373. [21] Misha Rudnev, On the number of incidences between points and planes in three dimensions, Combinatorica 38 (2018), no. 1, 219–254, available at 1407.0426. [22] Imre Z. Ruzsa, An application of graph theory to additive number theory, Scientia, Series A: Mathematical Sciences 3 (1989), 97–109. [23] James Singer, A theorem in finite projective geometry and some applications to number theory, Transactions of the American Mathematical Society 43 (1938), no. 3, 377–385. [24] Nigel P. Smart and Frederik Vercauteren, Fully homomorphic SIMD operations, Designs, Codes and Cryptography 71 (2014), no. 1, 57–81. Preliminary version in Cryptology ePrint Archive, Report 2011/133. [25] Sherman K. Stein, Algebraic tiling, The American Mathematical Monthly 81 (1974), no. 5, 445–462. [26] Sophie Stevens and Frank de Zeeuw, An improved point-line incidence bound over arbitrary fields, Bulletin of the London Mathematical Society 49 (2017), no. 5, 842–858, available at 1609.06284. [27] Sándor Szabó and Arthur D. Sands, Factoring groups into subsets, Lecture Notes in Pure and Applied Mathematics, vol. 257, Chapman & Hall/CRC, Boca Raton, FL, 2009. [28] Terence Tao and Van H. Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, 2006. [29] A. G. Vosper, The critical pairs of subsets of a group of prime order, Journal of the London Mathematical Society s1-31 (1956), no. 2, 200–205. Institute of Mathematics of the Romanian Academy and CertSIGN, Bucharest Email address: [email protected]; [email protected] Babeş-Bolyai University, Cluj-Napoca and certSIGN, Bucharest Email address: [email protected]