Generalized binary arrays from quasi-orthogonal cocycles

Generalized binary arrays from quasi-orthogonal cocycles J. A. Armario and D. L. Flannery 1Departamento de Matem´atica Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] 2School of Mathematics, Statistics and Applied Mathematics, National University of Ireland Galway, Galway H91TK33, Ireland [email protected] Abstract. Generalized perfect binary arrays (GPBAs) were used by Jedwab to construct perfect binary arrays. A non-trivial GPBA can exist only if its energy is 2or a multiple of 4. This paper introduces generalized optimal binary arrays (GOBAs) with even energy not divisible by 4, as analogs of GPBAs. We give a procedure to construct GOBAs based on a characterization of the arrays in terms of 2-cocycles. As a further application, we determine negaperiodic Golay pairs arising from generalized optimal binary sequences of small length. 1 Introduction Let φ= (φ(0), . . . , φ(n−1)) ∈ {±1}nbe a binary sequence of length n. Reading arguments modulo n, Rφ(w) := n−1 X k=0 φ(k)φ(k+w) is the periodic autocorrelation of φat shift w. The expansion of φ, denoted φ′, is the concatenation of φand −φ(in that order). A pair φ1,φ2of binary sequences, each of length 2t, such that Rφ′ 1(w) + Rφ′ 2(w) = 0 for 1≤w≤2t−1(equivalently, for 1≤ w≤4t−1and w6= 2t), is a negaperiodic Golay pair (NGP). Note that the original definition of NGP in [4] coincides with the definition above by [8, Lemma 2]. We seek good sources of NGPs. This objective is connected to several existence problems in algebraic design theory. For example, Egan showed that NGPs of length 2tare equivalent to certain relative (4t, 2,4t, 2t)-difference sets in the dicyclic group Q8tof order 8t[8, Theorem 3]. Actually, there is a relative (4t, 2,4t, 2t)-difference set in a central extension Eof Z2by a group Gof order 4t, relative to Z2, if and only if there is a Hadamard matrix of order 4twhose expanded (group-divisible) design admits a special regular action by E: a cocyclic Hadamard matrix over G[6, Theorem 2.4]. By way of [9, Theorem 3.3], Ito [13, p. 370] conjectured that Q8tcontains such relative difference sets for all t. Schmidt [16] has verified Ito’s conjecture up to t= 46. Our recent paper [3] initiated the study of quasi-orthogonal cocycles over groups Gof even order not divisible by 4, in direct analogy with cocyclic Hadamard matrices. The present paper builds on [3]. It is easy to see that max 0<w<n |Rφ(w)| ≥      0n≡0mod 4 1n≡1or 3mod 4 2n≡2mod 4. (1) The sequence φis optimal if equality holds in (1). In particular, φis perfect if Rφ(w) = 0for 0< w < n. No perfect binary sequence of length n > 4is known. Attention consequently turns to the larger class of perfect binary arrays (PBAs). Jedwab [14] introduced generalized perfect binary arrays (GPBAs) to aid in the construction of PBAs. Hughes [11] subsequently demonstrated the cocyclic nature of GPBAs. Ageneralized perfect binary sequence (GPBS) is a 1-dimensional GPBA; such φ have Rφ′(w) = 0 for all w. Each pair of GPBSs is obviously an NGP. However, a GPBS exists only if n= 2 [14, Result 4.8]. So let n > 2be even; since Rφ′(w)is divisible by 4, and not every Rφ′(w)is 0, some |Rφ′(w)|must be at least 4. Thus, we will say that φof length 2tis a generalized optimal binary sequence (GOBS) if max0<w<2t|Rφ′(w)|= 4. Equivalently, φis a GOBS if, for 0< w < 2t, |Rφ′(w)|=(0wodd 4weven when tis odd, and |Rφ′(w)|=(4wodd 0weven when tis even. We propose searching for NGPs in the set of GOBs of length 2t,todd. Just as the notion of GPBA extends that of GPBS to dimensions greater than 1, a GOBA (generalized optimal binary array) is a higher-dimensional version of a GOBS. Section 3 treats GPBAs and GOBAs from the perspective of [3]. We prove a one-to- one correspondence between GOBAs, quasi-orthogonal cocycles over abelian groups, and abelian relative quasi-difference sets. In Section 4, we outline and apply a method to find NGPs among GOBSs that correspond to quasi-orthogonal cocycles over cyclic groups. The concluding Section 5 looks at an important question for cocyclic designs prompted by the analysis in Section 4. 2 Quasi-orthogonal cocycles and related combinatorial structures Let Gand Ube finite groups, with Uabelian. A map ψ:G×G→Usuch that ψ(1,1) = 1 and ψ(g, h)ψ(gh, k) = ψ(g, hk)ψ(h, k)∀g, h, k ∈G(2) is a (normalized) cocycle over G. If φ:G→Uis any map that is normalized (i.e., φ(1) = 1) then ∂φ(g, h) = φ(g)φ(h)φ(gh)defines a cocycle ∂φ, called a coboundary. The set of all cocycles over Gforms an abelian group Z2(G, U), whose quotient by the subgroup B2(G, U)of coboundaries is the second cohomology group H2(G, U). We display ψ∈Z2(G, U)as a cocyclic matrix Mψ= [ψ(g, h)]g,h∈G. If U=Z2=h−1i and Mψis Hadamard then ψis said to be orthogonal. The row excess of a {±1}-matrix M= [mij]is RE(M) = Pi≥2Pj≥1mij. The cocycle equation (2) guarantees that ψis orthogonal if and only if RE(Mψ)is optimal, i.e., zero. For the rest of this section, |G|= 4t+ 2 >2. Proposition 1. (i) If ψ∈Z2(G, Z2)then RE(Mψ)≥4t. (ii) If ψ∈B2(G, Z2)then RE(Mψ)≥8t+ 2. Proof. See [3, Proposition 1].  In analogy with the definition of orthogonal cocycles, we say that ψis quasiorthogonal if its matrix has least possible row excess: by Proposition 1, either ψ6∈ B2(G, Z2)and RE(Mψ) = 4t, or ψ∈B2(G, Z2)and RE(Mψ) = 8t+ 2 (coboundaries were excluded from the notion of quasi-orthogonality in [3]). Lemma 1. Let Xm={g∈G|Ph∈Gψ(g, h) = m}. Then ψis quasi-orthogonal if and only if |X2∪X−2|= 4t+ 1 for ψ∈B2(G, Z2), or |X0|= 2t+ 1 and |X2∪X−2|= 2tfor ψ6∈ B2(G, Z2). Proof. See [3, Lemma 2.4].  It is not known whether quasi-orthogonal cocycles always exist. Indeed, we do not know of a group Gsuch that Z2(G, Z2)does not contain a quasi-orthogonal element (in contrast, there are several non-existence results for orthogonal cocycles, e.g., due to Ito [12]). We have found quasi-orthogonal coboundaries over many abelian G, but none over non-abelian Gsuch as dihedral groups, apart from the dihedral group of order 6. Thirdly, for all tsuch that 4t+ 1 is a sum of two squares that we tested, we always found a quasi-orthogonal cocycle ψover some group of order 4t+ 2 with |det(Mψ)| attaining the maximum 2(4t+ 1)(4t)2testablished by Ehlich-Wojtas. These existence questions all merit deeper investigation. Let Ebe a group with a normal subgroup Nof order mand index v. A relative (v, m, k, λ)-difference set in Erelative to N(the forbidden subgroup) is a k-subset R of a transversal for Nin Esuch that |R∩xR|=λ∀x∈E\N. Relative (2s, 2,2s, s)-difference sets are especially interesting. If sis even then they are equivalent to cocyclic Hadamard matrices [6, Corollary 2.5], whereas none exist if sis odd [10]. In the latter case there is a natural analog of relative difference set. Suppose that |E|= 8t+ 4 and let Z∼ =Z2be a normal (hence central) subgroup of E. A relative (4t+ 2,2,4t+ 2,2t+ 1)-quasi-difference set in Ewith forbidden subgroup Zis a transversal Rfor Zin Econtaining a subset S⊂R\ {1}of size 0or 2t+ 1 such that, for all x∈E\Z, |R∩xR|=(2t+ 1 x∈SZ 2tor 2t+ 2 otherwise. We call Rextremal if S=∅. (This modifies the original definition in [3] of relative quasi-difference set, to allow quasi-orthogonal coboundaries). The next result is mostly Proposition 4.3 in [3]. For each ψ∈Z2(G, Z2)we have a canonical central extension Eψwith element set {(±1, g)|g∈G}and multiplication defined by (u, g)(v, h) = (uvψ(g, h), gh). Proposition 2. The cocycle ψis quasi-orthogonal if and only if D={(1, g)|g∈G} is a relative (4t+2,2,4t+2,2t+1)-quasi-difference set in Eψwith forbidden subgroup h(−1,1)i, where Dis extremal for ψ∈B2(G, Z2). Remark 1. The requisite subset Sof Dcorresponds to the rows of Mψwith zero sum. 3 Generalized binary arrays with optimal autocorrelation Jedwab [14] showed that a GPBA is equivalent to an abelian relative difference set, and Hughes [11] identified its underlying orthogonal cocycle. In this section we carry over these ideas into the setting of quasi-orthogonal cocycles. We start with an adaptation of some material from [11] and [14]. The cyclic group of order mwill be written additively, i.e., as Zm={0,1, . . . , m −1}under addition modulo m. Let s= (s1, . . . , sr)be an r-tuple of positive integers greater than 1, and let G=Zs1× · · · × Zsr. A binary s-array is just a set map φ:G→ {±1}; it has energy n:= Qr i=1 si=|G|. We view a binary sequence as an s-array with r= 1. Given sand a type vector z= (z1, . . . , zr)∈ {0,1}r, let E=Z(z1+1)s1× · · · ×Z(zr+1)sr. Then H={h∈E|hi= 0 if zi= 0,and hi= 0 or siif zi= 1}, K={k∈H|khas even weight} are elementary abelian 2-subgroups of E. Note that Eis a (central) extension of Hby G. For z6=0we obtain the short exact sequence 1−→ h−1iι −→ E/K β −→ G−→ 0,(3) where ιmaps −1to the generator of H/K and β(g+K) = gmod s. This sequence determines a cocycle fz∈Z2(G, h−1i)after choice of a transversal map τ:G→ E/K. Specifically, set τ(x) = x+K; then fz(x, y) = ι−1(τ(x) + τ(y)−τ(x+y)). We can express fzas a product of cocycles on cyclic groups. Define γm∈Z2(Zm,h−1i) by γm(j, k) = (−1)⌊(j+k)/m⌋, evaluating the exponent as an ordinary integer. Proposition 3 ([11, Lemma 3.1]). (i) fz(x, y) = Qzi=1 γsi(xi, yi). (ii) fz∈B2(G, h−1i)if and only if siis odd for all isuch that zi= 1. Each cocycle ψ∈Z2(G, h−1i)has an associated short exact sequence 1−→ h−1iι′ −→ Eψ β′ −→ G−→ 0,(4) where ι′(u) = (u, 0) and β′(u, x) = x. The following is standard. Proposition 4. If ψand fzare cohomologous, say ψ=fz∂φ, then (3) and (4) are equivalent short exact sequences: the isomorphism Γdefined by (u, x)7→ ι(uφ(x)) + τ(x)makes the diagram 1−→ h−1iι′ −→ Eψ β′ −→ G−→ 0 kΓ yk 1−→ h−1iι −→ E/K β −→ G−→ 0 commute. We broaden concepts defined earlier only for sequences. The expansion of a binary s-array φwith respect to a type vector zis the map φ′on Egiven by φ′(g) = (φ(a)g∈a+K −φ(a)g /∈a+K where adenotes gmodulo s. For any array ϕ:A→ {±1}and x∈A, let Rϕ(x) = Pa∈Aϕ(a)ϕ(a+x). Lemma 2. If h∈H\Kthen φ′(h+g) = −φ′(g), and if h∈Kthen φ′(h+g) = φ′(g). Corollary 1. Rφ′(g) = |H|Px∈Tφ′(x)φ′(x+g)where Tis any transversal for H in E. Lemma 3. The isomorphism Γin Proposition 4maps {(1, x)|x∈G} ⊆ Eψonto {g+K∈E/K |φ′(g) = 1}. Proof. (Cf. [11, p. 330].) Let φ′(g) = 1 and write afor gmodulo s; then g+K= ι(φ(a)) + a+K=Γ((1, a)). Conversely, Γ((1, x)) = h+x+Kwhere h+Kis the generator of H/K if φ(x) = −1and h= 0 otherwise. By Lemma 2, φ′(h+x) = 1. The s-array φis a GPBA(s)of type zif Rφ′(g) = 0 ∀g∈E\H. When z= 0, this condition becomes (by Corollary 1) Rφ(g) = 0 ∀g∈G\ {0}. In the latter event φis a PBA; which is equivalent to ∂φ being orthogonal (we return to this case later in the section). More generally, a GPBA(s)is equivalent to a relative difference set in E/K relative to H/K, hence equivalent also to a cocyclic Hadamard matrix over G: see [11, Theorem 5.3] and [14, Theorem 3.2]. So a GPBA can exist only if its energy nis 2or a multiple of 4. Theorems 1 and 2 below are analogous results for n≡2mod 4. Assume that |G|= 4t+ 2 >2unless stated otherwise. Let s1/2, s2, . . . , srbe odd. Thus, if z1= 0 then Esplits over Hby Proposition 3, and so Rφ′is never zero by Corollary 1 and Lemma 2. Definition 1. AGOBA(s)of type zis a binary s-array φsuch that (i) Rφ′(g)∈ {0,±2|H|} ∀g∈E\H, and if z1= 1 then (ii) |{g∈E|Rφ′(g) = 0}| =|E|/2. A GOBS as defined in Section 1 is a GOBA(s)with r=z1= 1. When z=0, Definition 1 reduces to Rφ(g) = ±2∀g∈G\ {0}; we call φsatisfying this condition an optimal binary array (OBA). Lemma 4 ([14, Lemma 3.1]). For any array ϕ:A→ {±1}, Rϕ(x) = |A|+ 4(dϕ(x)− |Nϕ|) where Nϕ={a∈A|ϕ(a) = −1}and dϕ(x) = |Nϕ∩(x+Nϕ)|. Proof. Routine counting.  Theorem 1. Let φbe a binary s-array, zbe a non-zero type vector, and D={g+K∈ E/K |φ′(g) = −1}. Then φis a GOBA(s)of type zif and only if Dis a relative (4t+ 2,2,4t+ 2,2t+ 1)-quasi-difference set in E/K with forbidden subgroup H/K; furthermore, Dis extremal if z1= 0. Proof. We continue with the notation of Lemma 4. By Lemma 3, Dis a full transversal for H/K in E/K. Also, |Nφ′|=|E|/2by Lemma 2; thus |D|=|Nφ′|/|K|. For each g6∈ H, denote |D∩(g+K+D)|by dD(g+K): this is the number of x+K∈Dsuch that x−g+K∈D. Since dD(g+K) = dφ′(g)/|K|, Lemma 4 implies that Rφ′(g) = −2|H| ⇔ dD(g+K) = 2t Rφ′(g) = 0 ⇔dD(g+K) = 2t+ 1 Rφ′(g) = 2|H| ⇔ dD(g+K) = 2t+ 2. (5) Let S={g+K∈D|Rφ′(g) = 0}. According to (5), Definition 1 (i) holds if and only if dD(g+K) = (2t+ 1 g+K∈S+H/K 2tor 2t+ 2 otherwise. Lemma 2 yields |S|=|{g+K∈E/K |Rφ′(g) = 0}| 2=|R−1 φ′(0)|/2|K|. Thus |S|= 2t+ 1 for z1= 1 if and only if Definition 1 (ii) holds.  Remark 2. Theorem 1 remains valid when Dis replaced by its complement {g+K∈ E/K |φ′(g) = 1}. Theorem 2. A (normalized) binary s-array φis a GOBA(s)of type z6=0if and only if fz∂φ is quasi-orthogonal. Proof. This is a consequence of Theorem 1, Remark 2, Proposition 2, and Lemma 3.  We proceed to formulate ‘base’ cases of Theorems 1 and 2. Let ∂φ ∈B2(G, Z2). Since M∂φ is Hadamard equivalent to a group-developed matrix, and such a matrix has constant row sum, ∂φ can be orthogonal only if |G|is square. This situation has been extensively studied. Theorem 3. Let |G|= 4u2, and let Dbe a subset of Gof size 2u2−u. Define R= {(φ(g), g)|g∈G} ⊂ Z2×Gwhere φ:G→ {±1}is the characteristic function of D. Then the following are equivalent. (i) ∂φ is orthogonal. (ii) Dis a Menon-Hadamard difference set in G. (iii) Ris a relative (4u2,2,4u2,2u2)-difference set in Z2×Gwith forbidden subgroup Z2× {1G}. (iv) φis a perfect nonlinear function. If Gis abelian then (i) –(iv) are further equivalent to (v) φis a PBA. Proof. See [15, Theorem 1] for (iii) ⇔(iv). The other equivalences are given by Theorem 2.6 and Lemma 2.10 of [6].  Remark 3. In Theorem 3 and Theorem 4 below we may assume that φis normalized, by taking the complement of D(and thus also of R) if necessary. The next theorem is an analog of the previous one for |G| ≡ 2mod 4(recall that we have not found quasi-orthogonal coboundaries over non-abelian Gat orders greater than 6). Theorem 4. Let Gbe abelian of order 4t+ 2, and let Dbe a k-subset of Gwith characteristic function χ:G→GF(2). Define R={(φ(g), g)|g∈G} ⊂ Z2×G where φ(x) = (−1)χ(x). Then the following are equivalent. (i) ∂φ is quasi-orthogonal. (ii) Dis a (4t+ 2, k, k −(t+ 1),(4t+ 1)(k−t)−k(k−1))-almost difference set in G. (iii) Ris an extremal relative (4t+ 2,2,4t+ 2,2t+ 1)-quasi-difference set in Z2×G with forbidden subgroup Z2× {1G}. (iv) φis an OBA. If a difference set with parameters (n, n±√3n−2 2,n+2±2√3n−2 4)does not exist, then (i) –(iv) are further equivalent to (v) χhas optimal nonlinearity (t+ 1)/(2t+ 1). Proof. Put |G|=n. (i) ⇔(iv): Lemma 1 and the fact that φ(g)Rφ(g)is the sum of row gin M∂φ. (i) ⇔(ii): by Lemma 4, Rφ(g) = 2 or −2if and only if dφ(g) = k−t−1or k−t, respectively. Identity (19) of [5] then accounts for this part. (i) ⇔(iii): Proposition 2 together with the isomorphism E∂φ →Z2×Gdefined by (u, g)7→ (uφ(g), g); cf. Proposition 4. (ii) ⇔(v): see [5, Theorem 25].  Remark 4. The condition attached to (v) is only needed for (v) ⇒(ii). No difference sets with the stated parameters are known; see [5, Remark II, p. 224]. We end this section with a discussion of calculating GOBAs. Label the elements of Gas g1= 0, g2, . . . , g4t+2, and let δk:G→ {±1}be the characteristic function of {gk}. Up to relabeling, {∂2, . . . , ∂4t+1}is a basis of B2(G, h−1i), where ∂k:= ∂δk is an elementary coboundary. Choose z6=0. We first try to find quasi-orthogonal ψ∈Z2(G, h−1i)such that fzψ∈B2(G, h−1i). Straightforward linear algebra gives the decomposition ψ=fzQk∂ik k. Then φ=Qkδik kis a GOBA(s) of type zover G. Example 1. The maps φ1=1−1 1 1 1 1 ,φ2=1 1 −1 1 1 1 ,φ3=1 1 −1 1−1 1 on Z6=Z2×Z3are GOBA(2,3)s of type z1= (1,0),z2= (0,1),z3= (1,1), respectively. We display each quasi-orthogonal cocycle fzi∂φias a Hadamard (componentwise) product:         1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 −1−1−1 1 1 1 −1−1−1 1 1 1 −1−1−1         ◦         1 1 1 1 1 1 1 1 −1−1−1−1 1−1−1 1 1 1 1−1 1 1 −1 1 1−1 1 −1 1 1 1−1 1 1 1 −1         =         1 1 1 1 1 1 1 1 −1−1−1−1 1−1−1 1 1 1 1−1 1 −1 1 −1 1−1 1 1 −1−1 1−1 1 −1−1 1         ,         1 1 1 1 1 1 1 1 −1 1 1 −1 1−1−1 1 −1−1 1 1 1 1 1 1 1 1 −1 1 1 −1 1−1−1 1 −1−1         ◦         1 1 1 1 1 1 1−1−1 1 1 1 1−1 1 −1−1−1 1 1 −1 1 1 −1 1 1 −1 1 −1 1 1 1 −1−1 1 1         =         1 1 1 1 1 1 1−1 1 1 1 −1 1 1 −1−1 1 1 1 1 −1 1 1 −1 1 1 1 1 −1−1 1−1 1 −1−1−1         ,         1 1 1 1 1 1 1 1 −1 1 1 −1 1−1−1 1 −1−1 1 1 1 −1−1−1 1 1 −1−1−1 1 1−1−1−1 1 1         ◦         1 1 1 1 1 1 1−1−1−1−1 1 1−1 1 −1 1 1 1−1−1 1 −1−1 1−1 1 −1−1−1 1 1 1 −1−1 1         =         1 1 1 1 1 1 1−1 1 −1−1−1 1 1 −1−1−1−1 1−1−1−1 1 1 1−1−1 1 1 −1 1−1−1 1 −1 1         . Note that fz2∂φ2is a quasi-orthogonal coboundary; as are all the ∂φi. Example 2. The map   1−1 1 −1−1 1 1 1 −1 1 1 1 111111  ⊤ on Z6×Z3=Z2×Z3×Z3is a GOBA(6,3) of type z= (1,0). Its quasi-orthogonal cocycle is fz∂4∂8∂10∂13. 12. Ito, N.: On Hadamard groups. J. Algebra 168 (1994), 981–987. 13. Ito, N.: On Hadamard groups III. Kyushu J. Math. 51 (1997), 369–379. 14. Jedwab, J.: Generalized perfect arrays and Menon difference sets. Des. Codes Cryptogr. 2 (1992), 19–68. 15. Pott, A.: Nonlinear functions in abelian groups and relative difference sets. Discr. Appl. Math. 138 (2004), 177–193. 16. Schmidt, B.: Williamson matrices and a conjecture of Ito’s. Des. Codes Cryptogr. 17 (1999), 61–68.