Hadamard 2-Designs from Frobenius Groups Z_v : Z_k

Hadamard 2-Designs from Frobenius Groups Zv:Zk R. Radohery Georges Abstract We present a construction of Hadamard 2-designs using affine Frobenius groups of the form Zv:Zk. By applying the Key-Moori method to these groups under specific arithmetical conditions—namely, when v= 4λ+ 3 and k= 2λ+ 1 are both prime—we prove that the resulting symmetric 1-designs are actually Hadamard 2-designs with parameters 2 − (4λ+ 3,2λ+ 1, λ). This construction provides an explicit, group-theoretic approach to generating an infinite family of Hadamard designs, demonstrating the continued utility of algebraic methods in combinatorial design theory. We discuss computational aspects of the construction and provide examples for small parameter values. 1 Introduction The interaction between finite groups, block designs and linear codes has been a central theme in algebraic combinatorics for several decades (see, for example, [3,1,16,24]). Classical work of Bose established that many families of block designs can be constructed and analysed using tools from finite field theory, finite geometry and combinatorics [3]. On the coding theory side, the incidence matrices of such designs often yield linear codes with large automorphism groups, and this can be exploited in encoding and decoding algorithms [1]. Among symmetric 2-designs, those with Hadamard parameters occupy a particularly important position because of their close connection with Hadamard matrices and extremal binary codes. Recall that the existence of a Hadamard matrix of order 4uis equivalent to the existence of a symmetric 2 −(4u−1,2u−1, u −1) design, usually called a Hadamard design [16,21,18,26]. Such designs provide highly regular incidence structures and give rise to classical families of error-correcting codes [1]. 1.1 Motivation and Parameter Selection The parameter forms v= 4λ+ 3 and k= 2λ+ 1 are of particular interest in Hadamard design theory [2,4]. These parameters correspond to cases where classical construction methods often encounter significant difficulties [4,27]. When both vand kare prime, additional algebraic structure becomes available through group-theoretic methods, making these cases amenable to our construction approach. Our work addresses a gap in the systematic construction of Hadamard 2-designs for this infinite family of parameters. The primality conditions ensure that the Frobenius group Zv:Zkhas the rigid structure necessary for the Key-Moori construction to produce designs with the required 2-homogeneity property. Moreover, the arithmetical relationship k= (v−1)/2 guarantees that the multiplicative group F× vcan be decomposed in a way that yields transitivity on 2-subsets, which is essential for obtaining Hadamard parameters. 1.2 Applications and Broader Context Beyond their intrinsic combinatorial interest, Hadamard 2-designs have important applications across multiple domains: 1  Coding Theory: Through their incidence matrices, Hadamard designs give rise to extremal binary codes meeting the Grey-Rankin bound—codes that achieve the maximum possible minimum distance for their length and dimension [1].  Statistical Design: These designs appear as orthogonal arrays in experimental design, providing optimal arrangements for testing multiple factors simultaneously [19,12].  Quantum Information: Hadamard designs are used in constructions of mutually unbiased bases, which are fundamental objects in quantum state tomography and quantum cryptography [9].  Cryptography: The designs provide authentication codes with strong security properties against impersonation and substitution attacks [8,10,23].  Signal Processing: The underlying Hadamard matrices are central to Hadamard transforms, widely used in data compression and error correction. Thus, systematic construction methods for new families of Hadamard designs have both theoretical and practical significance. 1.3 Group-Theoretic Constructions Group-theoretic constructions of Hadamard designs typically proceed by exploiting highly transitive actions or special orbit structures of finite groups. Notable examples include constructions from Sylvester-type Hadamard matrices via 2-groups [25,21], and constructions from symplectic groups acting on appropriate coset or subspace geometries [15]. Key and Moori developed two general methods for constructing symmetric 1-designs from primitive group actions and from maximal subgroups together with suitable conjugacy classes [13,14,17]. These methods have been successfully applied to many families of finite simple groups, including projective special linear groups, classical groups, and sporadic simple groups (see, for example, [15,17]). 1.4 Our Contribution In this paper we apply the first method of Key and Moori to certain Frobenius groups. Let v and kbe prime numbers and consider the Frobenius group G∼ =Zv:Zk of order vk acting on the vright cosets of a Frobenius complement of order k. From the orbit structure of the point stabiliser in this primitive action, Key-Moori Method 1 yields a symmetric 1-design with parameters 1−(v, k, k). When vand ksatisfy the arithmetical conditions v= 4λ+ 3, k = 2λ+ 1 for some integer λ≥1, we show that this design is in fact a Hadamard 2-design with parameters 2−(v, k, λ). Equivalently, for each such pair of primes (v, k) we obtain a symmetric 2 −(4λ+ 3,2λ+ 1, λ) design whose automorphism group contains the Frobenius group Zv:Zk. Our approach is purely group-theoretic and uses only the basic structure theory of Frobenius groups together with Key-Moori Method 1. The proof technique—counting incidences between blocks and pairs—is both elementary and elegant, relying on basic properties of group actions rather than deep structural theorems. 2 1.5 Organization In Section 2we recall the necessary notions from design theory and group actions, and we record the version of Key-Moori Method 1 that will be used. We also collect the standard facts about Frobenius groups needed to describe the relevant primitive action of Zv:Zk. In Section 3we describe the affine action of Zv:Zkand the resulting symmetric 1-designs. In Section 4we prove that, under the above arithmetical conditions on vand k, these designs are Hadamard 2-designs. Section 5discusses computational aspects and provides explicit examples. We conclude in Section 6with remarks on future directions. 2 Preliminaries 2.1 Designs and Hadamard Designs An incidence structure is a triple I= (P,B, I), where Pis a finite set of points,Bis a finite set of blocks, and I⊆ P × B is an incidence relation. For a block B∈ B we write p∈Bif (p, B)∈I. We say that Bhas size kif it is incident with exactly kpoints. Definition 2.1. Let t, v, k, λ be positive integers with t≤k≤v. A t-(v, k, λ)design is an incidence structure D= (P,B, I) such that  |P| =v;  every block B∈ B is incident with exactly kpoints; and  every t-subset of Pis contained in exactly λblocks. We call Dat-design. This is standard terminology; see, for example, [1,16,6,24]. If Dis a t-(v, k, λ) design with b=|B| blocks, then Dis said to be symmetric if v=b, that is, if the number of points equals the number of blocks. The following class of symmetric 2-designs will be central in what follows. Definition 2.2. Let ube a positive integer. A Hadamard design is a symmetric 2 −(4u− 1,2u−1, u −1) design. It is well known that Hadamard designs are equivalent to Hadamard matrices: the existence of a Hadamard matrix of order 4uis equivalent to the existence of a Hadamard 2−(4u−1,2u− 1, u−1) design [16,21,18,26]. In particular, if Dis a 2−(4u−1,2u−1, u−1) design, then the incidence matrix of Dcan be extended by one row and one column to a {±1}-matrix of order 4uwith mutually orthogonal rows. 2.2 Group Actions and the Key-Moori Method Throughout, Gdenotes a finite group. If Gacts on a finite set Ω, we view Ω as a right G-set and write αgfor the image of α∈Ω under g∈G. For α∈Ω the stabiliser of αin Gis Gα={g∈G|αg=α}, and for a subset ∆ ⊆Ω the setwise stabiliser of ∆ in Gis G∆={g∈G|∆g= ∆}. The action is called transitive if Ghas a single orbit on Ω, and primitive if it is transitive and preserves no non-trivial partition of Ω. Standard background on permutation groups can be found, for example, in [7,5]. We will use the following construction of symmetric 1-designs from primitive group actions, due to Key and Moori; see [13,14,17,15]. 3 Method 2.3 (Key-Moori Method 1).Let Gbe a finite primitive permutation group acting on a set Ω of size n. Fix α∈Ω and let ∆ = {α, β, . . .}be an orbit of the stabiliser Gαon Ω with |∆|>1. Set B={∆g|g∈G}. Then D= (Ω,B) is a symmetric 1 −(n, |∆|,|∆|) design, and Gacts as an automorphism group of D, primitively on points and on blocks. There is also a version of this method allowing ∆ to be a union of orbits of Gα, including the orbit {α}, which still yields a symmetric 1-design with the same automorphism group; see, for example, [15,17]. We will only need the basic form stated above. Intuition Behind the Key-Moori Construction The Key-Moori method exploits the symmetry inherent in transitive group actions. By taking the orbit of a subset ∆ (containing α) under the full group G, we ensure that every block has the same “local structure.” Specifically, if ∆ is an orbit of Gαand B= ∆gis any block, then the stabiliser of any point in Bacts on Bin a manner conjugate to how Gαacts on ∆. This uniformity, combined with the transitivity (or primitivity) of Gon Ω, guarantees the regularity properties required for a t-design. In essence, the method transforms group-theoretic symmetry into combinatorial regularity: the orbit structure under point stabilisers determines the block structure, and the global transitivity of Gensures that all points (and all blocks) are treated uniformly. Example 2.4 (The Fano Plane).Consider the simplest case of our construction where λ= 1, giving v= 7 and k= 3. The group Z7:Z3acts transitively on 7 points. Let Ω = F7= {0,1,2,3,4,5,6}under addition modulo 7, and let H={1,2,4}be the unique subgroup of order 3 in F× 7. The stabiliser of point 0 is G0=H, which acts on Ω \ {0}with two orbits: ∆1={1,2,4},∆2={3,5,6}. Choosing ∆ = ∆1, the base block is {0,1,2,4}(if we include the fixed point) or simply the orbit {1,2,4}on the non-zero elements. Applying translations by all elements of F7generates the 7 blocks of the design. The resulting structure is the Fano plane, the unique 2 −(7,3,1) design—a fundamental object in combinatorics and the smallest projective plane. This example illustrates how the Key-Moori method, applied to a small Frobenius group, produces a well-known and highly symmetric design. 2.3 Frobenius Groups We now recall the standard definition and structural properties of Frobenius groups needed later; see, for example, [11,20]. Definition 2.5. A finite permutation group Gacting transitively on a finite set Xis called a Frobenius group if the identity is the only element of Gthat fixes more than one point of X. Equivalently, for any non-identity element g∈G, either ghas no fixed points, or it fixes exactly one point of X. Let Gbe a Frobenius group acting on X. The set N={e}∪{g∈G|ghas no fixed point on X} is called the Frobenius kernel of G. It is a normal subgroup of G, and Gis a semidirect product G∼ =N:Gxfor any point stabiliser Gx. The following facts about the orbit structure of Frobenius groups are standard (see, for instance, [11,20]). 4 Theorem 2.6. Let Gbe a Frobenius group acting transitively on a finite set X, and let x∈X. Then: (i) The stabiliser Gxhas a unique orbit of length 1, namely {x}. (ii) On X\ {x}the group Gxacts semiregularly; in particular, every orbit of Gxon X\ {x} has size |Gx|. (iii) The Frobenius kernel Nis a normal subgroup of Gand G∼ =N:Gx. In the special case of groups of order pq with pand qprime, we will use the following well-known structure theorem (see, for example, [20,11]). Theorem 2.7. Let Gbe a non-abelian group of order pq, where p<qare primes and p|(q−1). Then: (i) Gis isomorphic to the semidirect product Zq:Zp. (ii) Gadmits a faithful transitive action of degree qin which the point stabiliser is a subgroup of order p. (iii) In this action, Gis a primitive Frobenius group of degree q. In what follows we will write G=Zv:Zkfor such a Frobenius group with vand kprime, and we consider its natural primitive action of degree von the right cosets of the subgroup of order k. Combining Theorem 2.6 with Method 2.3 applied to this action will yield a family of symmetric 1-designs with parameters 1 −(v, k, k). Under the additional arithmetic condition v= 4λ+ 3 and k= 2λ+ 1, these designs will be seen to be Hadamard 2-designs. 3 The Affine Frobenius Group Zv:Zk Let vand kbe primes with k|(v−1). Write Fvfor the field with velements, identified with its additive group. Let Hbe the unique subgroup of F× vof order k. We consider the subgroup Gof the affine group AGL(1, v) consisting of maps x7→ ax +b(a∈H, b ∈Fv). Then Gis a Frobenius group with kernel the translation subgroup N∼ =Zvand complement H∼ =Zk. The action on X=Fvis transitive, and the stabiliser of 0 is precisely G0=H. Lemma 3.1. In the above setting, the action of Gon Xis a primitive Frobenius action, and for each x∈Xthe stabiliser Gxhas the following orbit structure: X={x}˙ ∪∆1˙ ∪ · · · ˙ ∪∆m, where each ∆iis an orbit of size k. In particular, if v−1=2k, then m= 2 and X={x}˙ ∪∆1˙ ∪∆2 with |∆1|=|∆2|=k. Proof. The translation subgroup Nacts regularly on X, so Gis transitive. The stabiliser of 0 is G0=H, a subgroup of index vin G. Because vis prime, G0is maximal and the action is primitive. Since nontrivial elements of Nhave no fixed points and nontrivial elements of Hfix exactly one point, Gis a Frobenius group with kernel Nand complement H. By Theorem 2.6, for each x∈Xthe stabiliser Gxhas a single orbit {x}of size 1, and all other orbits on X\ {x}have size |Gx|=k. Thus Xdecomposes as claimed, with |X\ {x}| =v−1 = mk and therefore m= (v−1)/k. If v−1 = 2k, then m= 2 and the final statement follows. 5 We next recall the suborbit design construction in this setting. Lemma 3.2 (Suborbit Design).Let Gact primitively on a set Xof size vand let x∈X. Let ∆⊆Xbe an orbit of Gxwith 1<|∆|< v. Set B={∆g|g∈G} and define D= (X, B)with incidence given by inclusion. Then Dis a symmetric 1−(v, k, k) design, where k=|∆|. Proof. By transitivity, |X|= [G:Gx] = v. Because ∆ is an orbit of Gx, we have Gx⊆G∆. Hence the orbit-stabiliser theorem gives |B| = [G:G∆] = [G:Gx] = v, so Dis symmetric with vpoints and vblocks. Each block has size k=|∆|by construction. To see that each point lies in the same number of blocks, let x, y ∈X. Because the action is primitive, it is transitive, so there exists g∈G with xg=y. Conjugation by ginduces a bijection between the blocks containing xand the blocks containing y. Hence the number of blocks through a point is constant on X, and Dis a 1-design. Finally, the symmetric condition v=|B| and the identity vr =bk imply that the replication number requals k. Thus Dis a symmetric 1 −(v, k, k) design. Combining Lemma 3.1 with Lemma 3.2 gives the following immediate consequence for the groups G=Zv:Zk. Corollary 3.3. Suppose vand kare primes with k|(v−1). Let G≤AGL(1, v)be as above, acting on X=Fv. Fix x∈Xand let ∆be a non-trivial orbit of Gxon X. Then the incidence structure D= (X, B), with B={∆g|g∈G}, is a symmetric 1−(v, k, k)design. If moreover v−1 = 2k, then for each xthere are exactly two choices for ∆, both of size k. Remark 3.4 (Significance of Primality Conditions).The primality conditions on vand kare not merely technical requirements but play a fundamental role in our construction. When vis prime, Zvhas no non-trivial proper subgroups, ensuring that the Frobenius group structure is as “rigid” as possible. When kis also prime, the complement Zkacts on Zvin a particularly wellbehaved manner, with orbit structures that are completely determined by the multiplicative order of a generator of Hmodulo v. These conditions together guarantee that when k= (v−1)/2, the subgroup Hof F× vhas index exactly 2, which is precisely what we need in Lemma 3.5 below to obtain 2-homogeneity of the affine action of Gon X. This 2-homogeneity is the key property that elevates our symmetric 1-designs to Hadamard 2-designs. 3.1 Two-Homogeneity of the Affine Action We now specialise to the case v= 4λ+3 and show that the affine action of Gis 2-homogeneous. Lemma 3.5 (Two-Homogeneity).Suppose vis a prime with v= 4λ+3 for some integer λ≥1, and set k= 2λ+ 1 = (v−1)/2, which is also prime. Let G≤AGL(1, v)be as above. Then G acts transitively on the set of 2-subsets of X=Fv. 6 Proof. The additive group of Xis Fv, and the multiplicative group F× vhas order v−1 = 2k. The subgroup Hhas order kand therefore index 2 in F× v. Because −1 has order 2 and kis odd, we have −1/∈H, so F× vdecomposes as a disjoint union F× v=H˙ ∪(−H), where −H={−h:h∈H}. Consider two unordered pairs of distinct points {x1, x2}and {y1, y2}in X. Using translations (elements of N) we may assume {x1, x2}={0, d1},{y1, y2}={0, d2}, with d1, d2∈F× v. The ratio d2d−1 1lies in F× v, so either d2d−1 1∈Hor d2d−1 1∈ −H. Case 1: d2d−1 1∈H. Then there exists a∈Hsuch that d2=ad1. The affine map x7→ ax lies in Gand sends {0, d1}to {0, d2}. Case 2: d2d−1 1∈ −H. Then d2d−1 1=−afor some a∈H, so −d2=ad1. The map x7→ ax sends {0, d1}to {0,−d2}, which is the same unordered pair as {0, d2}. In either case there exists g∈Gwith {x1, x2}g={y1, y2}. Thus Gis transitive on the set of 2-subsets of X, as required. 4 The Main Theorem We now combine the suborbit design construction with the two-homogeneity of Gto show that the symmetric 1-designs from Corollary 3.3 are in fact 2-designs with Hadamard parameters. Lemma 4.1. Let D= (X, B)be a symmetric 1−(v, k, k)design, and let G≤Aut(D)act transitively on the set of 2-subsets of X. Then Dis a 2−(v, k, λ)design for some λ≥1. Proof. For distinct points x, y ∈X, let λ(x, y) = |{B∈ B :{x, y} ⊆ B}| be the number of blocks containing both xand y. Because Gacts as a group of automorphisms of Dand is transitive on 2-subsets, the value of λ(x, y) is constant on the orbit of {x, y}and hence independent of the particular pair. Thus there exists an integer λ≥0 such that λ(x, y) = λfor all distinct x, y ∈X. It remains to see that λ > 0. Since each block contains k≥2 points, there exists at least one pair of distinct points lying in a block; for that pair we have λ(x, y)≥1, and therefore λ≥1 for all pairs. Hence Dis a 2 −(v, k, λ) design. We can now state and prove the main result. Theorem 4.2. Let λ≥1be an integer and suppose vand kare primes with v= 4λ+ 3, k = 2λ+ 1. Let G≤AGL(1, v)be the Frobenius group G={x7→ ax +b|a∈H, b ∈Fv}, where His the unique subgroup of F× vof order k. Fix x∈X=Fvand let ∆be one of the two orbits of Gxof size kon X\ {x}. Let B={∆g|g∈G}, D = (X, B). Then Dis a Hadamard design with parameters 2−(v, k, λ) = 2 −(4λ+ 3,2λ+ 1, λ). 7 Proof. By Corollary 3.3,Dis a symmetric 1 −(v, k, k) design. By Lemma 3.5 the group Gacts transitively on the 2-subsets of X, and by construction G≤Aut(D). Hence Lemma 4.1 applies, and Dis a 2 −(v, k, λ′) design for some λ′≥1. To determine λ′, we count incidences of blocks and pairs in two ways. Let bbe the number of blocks. Since Dis symmetric, b=v. Each block contains k 2pairs of distinct points, so the total number of (block, pair) incidences is vk 2. On the other hand, there are v 2unordered pairs of distinct points, and each lies in exactly λ′ blocks, so the same total is equal to λ′v 2. Thus λ′v 2=vk 2 and therefore λ′=vk 2 v 2=v·k(k−1)/2 v(v−1)/2=k(k−1) v−1. Now substitute v= 4λ+ 3 and k= 2λ+ 1: λ′=(2λ+ 1)(2λ) 4λ+ 2 =2λ(2λ+ 1) 2(2λ+ 1) =λ. Thus the parameter computed from the design identity agrees with the given λ, and the parameters of Dare indeed 2−(v, k, λ)=2−(4λ+ 3,2λ+ 1, λ). By Definition 2.2,Dis a Hadamard design. Remark 4.3 (Interpretation of the Main Theorem).Theorem 4.2 establishes that whenever we can find primes of the form v= 4λ+ 3 and k= 2λ+ 1, the Key-Moori construction applied to the Frobenius group Zv:Zkautomatically produces a Hadamard 2-design. The arithmetical relationship between v,k, and λis precisely what is needed to ensure λ(v−1) = k(k−1), the defining equation for Hadamard 2-designs with these parameters. This elegant connection between number-theoretic conditions (primality and arithmetic progressions) and combinatorial properties (2-homogeneity and Hadamard parameters) exemplifies the power of algebraic methods in design theory. The construction is both explicit and systematic: given suitable primes, the design is determined by the group structure and can be computed directly. Remark 4.4 (Uniqueness).For small parameter sets, certain Hadamard 2-designs are known to be unique up to isomorphism. For instance, the 2 −(7,3,1) design (Fano plane) is unique, as is the 2 −(11,5,2) biplane. However, for larger parameters, multiple non-isomorphic designs typically exist. Our construction produces a specific representative distinguished by having a large automorphism group of order at least vk. Determining the full automorphism group and investigating uniqueness for larger parameter sets remains an interesting open problem. It would be particularly valuable to characterise which of our designs are uniquely determined by their parameters and which admit non-isomorphic variants. 8 5 Computational Aspects and Examples A pair of primes (v, k) arises from some λif and only if v= 4λ+ 3, k = 2λ+ 1 are both prime. For such a pair, Theorem 4.2 yields a Hadamard design 2−(v, k, λ) = 2 −(4λ+ 3,2λ+ 1, λ) admitting G=Zv:Zkas a group of automorphisms. 5.1 Finding Suitable Parameters The construction method presented in this paper requires finding primes of the form v= 4λ+3 and k= 2λ+ 1. We discuss several practical considerations for implementing this construction. Density of suitable primes: By Dirichlet’s theorem on primes in arithmetic progressions, there are infinitely many primes of each required form [22]. However, finding pairs (v, k) satisfying both conditions simultaneously for a given λrequires that both 4λ+ 3 and 2λ+ 1 be prime, which becomes increasingly rare for large λ. This is reminiscent of the twin prime problem, though the arithmetic progressions involved are different. The density of such λis not known precisely, but numerical evidence suggests that suitable values occur regularly enough for practical construction of moderately sized designs. 5.2 Computational Complexity Given suitable primes vand k, the construction of the design involves several computational steps: 1. Group structure computation: Determining the action of Zkon Zvrequires computing powers modulo v, which can be done in O(klog v) time using fast exponentiation. 2. Orbit determination: Finding the orbits of the point stabiliser on pairs requires O(k·v) operations in the worst case. 3. Block generation: Once a base block is determined, generating all vblocks by group action requires O(v·k) operations. Overall, the construction has time complexity O(v2k) = O(λ3) in terms of the design parameter λ. For small to moderate values of λ(say λ≤100), this is entirely feasible on modern computers. 5.3 Small Examples The following table lists small values of λfor which both v= 4λ+ 3 and k= 2λ+ 1 are prime: For λ= 1, our construction yields the Fano plane, which is known to be the unique 2−(7,3,1) design. For larger parameters, multiple non-isomorphic designs may exist, and our construction produces a specific representative with a large automorphism group (of order vk). In each case the incidence matrix of the design can be converted, via the standard construction, into a Hadamard matrix of order 4(λ+ 1). 9