Quasi-orthogonal cocycles, optimal sequences and a conjecture of Littlewood

Quasi-orthogonal cocycles, optimal sequences and a conjecture of Littlewood J. A. Armario1 D. L. Flannery2 Abstract A quasi-orthogonal cocycle, defined over a group of order congruent to 2 modulo 4, is naturally analogous to an orthogonal cocycle (i.e., one defined over a group of order divisible by 4, and whose display matrix is Hadamard). Here we extend the theory of quasi-orthogonal cocycles in new directions, using equivalences with various optimal binary and quaternary sequences. Keywords Cocycle · Quasi-orthogonal · Sequence · Array · Autocorrelation · Merit factor · Golay pairs · Butson Hadamard matrix · EW matrix Mathematics Subject Classification 05B10 · 05B20 · 94A55 1 Introduction The theory of quasi-orthogonal cocycles and associated combinatorial objects has been explored in recent papers [4–6]. The current paper makes further progress in understanding the significance of these cocycles. Dedicated to Professor K. T. Arasu on the occasion of his 65th birthday. BJ. A. Armario [email protected] D. L. Flannery [email protected] 1Departamento de Matemática Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Seville, Spain 2School of Mathematics, Statistics and Applied Mathematics, National University of Ireland Galway, Galway H91TK33, Ireland Specifically, we examine optimal binary and quaternary sequences for periodic, negaperiodic, and aperiodic autocorrelation, from the cocyclic point of view. We thereby obtain a sufficient condition (in terms of quasi-orthogonal cocycles over Z2m, modd) for a conjecture of Littlewood about the asymptotic behavior of the merit factor of binary sequences. It is known that this problem is related to the L4-norm of complex-valued polynomials with ±1 coefficients on the unit circle. In addition, we establish: a characterization of binary periodic optimal sequences of length 2mvia binary sequences of length m; a method for constructing an EW matrix (a kind of D- optimal matrix) from optimal quaternary sequences; a bijection between negaperiodic Golay pairs of binary sequences of length 2mand periodic Golay pairs of quaternary sequences of length m. Applying the latter bijection, we discover a new quaternary complex Hadamard matrix of order 70. 2 Cocycles This section reviews some elementary 2-cohomology and other basic results. For groups Gand U, where Uis finite abelian, a map ψ:G×G→Usuch that ψ(g,h)ψ(gh,k)=ψ(g,hk)ψ(h,k)∀g,h,k∈G is a cocycle. The group of these cocycles is denoted Z2(G,U). Given a map φ:G→ U,thecoboundary ∂φ ∈Z2(G,U)is defined by ∂φ(g,h)=φ(g)−1φ(h)−1φ(gh). Thecoboundariesformasubgroup B2(G,U)of Z2(G,U).Forconvenience,ourcocycles are normalized, i.e., ψ(1,1)=1. Each cocyclic matrix Mψ=[ψ(g,h)]g,h∈G over Gusually has first row and column indexed by 1G. Lemma 1 [11, Lemma 6.6] MψM ψhas (i,j)th entry ψ(gig−1 j,gj)g∈Gψ(gig−1 j,g). Let U=−1∼ =Z2. In this case, if Mψis a Hadamard matrix (so that |G|=2or |G|≡0 mod 4), then ψis said to be orthogonal. The row excess RE(M)of a cocyclic {± 1}-matrix Mindexed by Gis the sum of the absolute values of all row sums, apart from the row indexed by 1G. By Lemma 1, ψis orthogonal precisely when RE(Mψ)=0. Henceforth we are interested mainly in cocycles over Gof just even order, i.e., |G|=4t+2>2. Proposition 1 [4, Proposition 1] Let ψ∈Z2(G,Z2). (i) RE(Mψ)≥4t, and RE(Mψ)≥8t+2if ψ∈B2(G,Z2). (ii) RE(Mψ)=4t if and only if n/2rows of Mψeach sum to 0and the remaining non-initial rows each have sum ±2. (iii) Let ψ∈B2(G,Z2). Then RE(Mψ)=8t+2if and only if every non-initial row sum of Mψis ±2. By analogy with the definition of orthogonal cocycles, we call ψquasi-orthogonal if RE(Mψ)is minimal: RE(Mψ)=4tfor ψ/∈B2(G,Z2), and RE(Mψ)=8t+2 for ψ∈B2(G,Z2). The analogy between orthogonal and quasi-orthogonal cocycles was noticed originally in connection with the maximal determinant problem for square binary matrices (to be discussed below). 3 Optimal sequences, arrays, and matrices Let s=(s1,...,sr)where si>1, and let Gbe the abelian group Zs1×···×Zsr. An s-array is just a map φ:G→Cwhere C={±1}or {± 1,±i}.Ofcourse,a sequence is an s-array with r=1. Let wbe a non-negative integer. The periodic autocorrelation at shift wof an array φ:G→Cis Rφ(w) = g∈G φ(g)φ(g+w), reading arguments modulo n; the overline denotes complex conjugate. A sequence φof length nsuch that Rφ(w) =0for0<w<nis perfect.No perfect binary (resp., quaternary) sequences of length n>4 (resp., n>16) are known; see [2,16]. Consequently, we search for sequences with next best possible periodic autocorrelation (according to [3, p. 2940] and [15]). A binary sequence φof length n≡2mod4isanOBS(optimal binary sequence)if|Rφ(w)|=2 for all w, 0<w<n. A quaternary sequence φof odd length nis an OQS (optimal quaternary sequence)ifRφ(w) ∈{±1}for all w,0<w<n(Rφ(w) is real by [6, Corollary 2]). Let |G|≡2 mod 4. A binary array φon Gis an OBA (optimal binary array)if |Rφ(w)|=2 for all nonzero w∈G. When G=Z2×Zm, this definition coincides with the definition of OBS. The following two facts from [5,6] relate (normalized) optimal arrays and sequences to quasi-orthogonal cocycles (we remark that Result 1 is Proposition 1(iii) combined with the identity Rφ(w) =φ(w)g∈G∂φ(w,g)). Result 1 Let |G|=2m,modd. A binary s-array φon Gis an OBA if and only if ∂φ is quasi-orthogonal. Result 2 There exists an OQS of odd length mif and only if there exists a quasiorthogonal cocycle over Z2×Zmthat is not a coboundary. Result 1 leads to a new characterization of optimal binary sequences, which we give next. Result 2 will be applied to construction of EW matrices. Theorem 1 Let m be odd. A binary sequence φ=(φ(0),...,φ(2m−1)) is an OBS if and only if there exist binary sequences a, b each of length m such that |Ra(w) +Rb(w)|= 2,1≤w≤m−1, |Ra,b(0)|= 1, |Ra,b(w) +Ra,b(m−w)|= 2,1≤w≤(m−1)/2, where Ra,b(w) =2m−1 k=0a(k)b(k+w) is the periodic cross-correlation function. Proof Define a(j)=φ(j)jeven φ(m+j)jodd,b(j)=φ(m+j)jeven φ(j)jodd, and ϕ=a(0)··· a(m−1) b(0)··· b(m−1). We calculate that Rφ(w) =Rϕ(w mod 2,wmod m). Hence, φis optimal if and only if the (2,m)-array ϕis an OBA; which, by Result 1, is equivalent to ∂ϕ ∈B2(Z2×Zm,−1)being quasi-orthogonal. Let M=AB BA  where A,Bare the m×mback-circulant {± 1}-matrices with first rows (a(0),..., a(m−1)) and (b(0),...,b(m−1)), respectively. The normalization of Mis M∂ϕ = DMD for a diagonal matrix D. Thus, by Lemma 1, the entries of MMare row sums of M∂ϕ up to sign. Proposition 1then implies that ∂ϕ is quasi-orthogonal if and only if abs(MM)=2mI +2(J−I)(1) where Jis the all 1s matrix, and abs(X)is obtained from Xby taking the absolute value of each entry. Since Aand Bare back-circulant, they are symmetric, so from (1) we get abs(A2+B2)=2mI +2(J−I)(2) abs(AB +BA)=2J.(3) By inspection, (2) is equivalent to |Ra(w) + Rb(w)|=2for1 ≤ w ≤ m − 1, and (3) is equivalent to the remaining conditions in the statement of the theorem.  Example 1 If φ=(1,−1,1,−1,1,1,−1,−1,1,1,1,1,1,1)then Rφ=(14,2, 2,2,2,2,2,−2,2,2,2,2,2,2).Alsoa=(1,1,1,1,1,1,−1),b=(−1,−1, 1,−1,1,1,1),Ra=(7,3,3,3,3,3,3),Rb=(7,−1,−1,−1,−1,−1,−1), and Ra,b=(−1,3,3,−1,3,−1,−1). For the rest of this section, ‘determinant’ of a matrix means the absolute value of its determinant. Let Mbe a D-optimal design of order n:ann×n{± 1}-matrix with largest possible determinant at the given order. Hadamard famously proved that det M≤nn/2.For orders n≡ 0 mod 4, more stringent bounds have been established. Let n≡2mod4; Ehlich [9] and independently Wojtas [17] proved that det M≤(2n−2)(n−2)1 2n−1. This bound can be attained only if n−1 is the sum of two squares. A D-optimal design that attains the Ehlich–Wojtas bound is called an EW matrix. If a cocyclic matrix Mψ is EW, then ψis quasi-orthogonal [1]. Below, we go in the other direction, providing a construction of EW matrices from a type of OQS. Theorem 2 Suppose that there exists a quaternary sequence f of odd length m such that R f(w) =1for all w,0<w<m. Let C be the circulant matrix with first row [f(0), f(1),..., f(m−1)], and write C =1−i 2(A+iB)where A, B are {± 1}- matrices of order m. Further, let M=AB −BA . Then MM=L0 0L(4) where L =2(m−1)Im+2Jm,A=Re(C)−Im(C), and B =Re(C)+Im(C). Hence M is an EW matrix and 2m−1must be the sum of two squares. Proof By the definitions, MM=AA+BB−AB+BA  −BA +ABAA+BB and CC∗=1 2(AA+BB−iAB+iBA ), where ∗denotes complex conjugate transpose. Also, CC∗=(m−1)I+Jbecause Rf(w) =1for1≤w≤m−1. The result is now clear.  Example 2 Let f1=(1,i,1)and f2=(1,−1,1,1,1). Then Rf1=(3,1,1), Rf2=(5,1,1,1,1),A1=⎡ ⎣ 1−11 11−1 −111 ⎤ ⎦,B1=J3, and A2=B2= ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1−1111 11−111 111−11 1111−1 −11111 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ . At first glance, Theorem 2does not extend to OQS fsuch that Rf(w) takes on values −1. But a Hadamard equivalent of the matrix Min that situation could satisfy (4). Note that, conversely, an EW matrix Mcertainly satisfies (4) up to equivalence. 4 Negaperiodic optimal sequences Let φ=(φ(0),...,φ(n−1)) be a binary sequence, and denote the concatenation φ|−φby φ. Then NR φ(w) := n−1  k=0 φ(k)φ(k+w) is the negaperiodic autocorrelation of φat shift w. It is well known that max 0<w<n|NR φ(w)|≥0neven 1nodd. Sequences φ such that NRφ(w) = 0for1 ≤ w ≤ n − 1 do not exist at lengths n > 2[13, Result 4.8]. Hence, if n is even, then |NRφ(w)|≥ 2forsomew. A binary sequence φ of length 2m such that NRφ(w) ∈{0, ± 2} for all w,0 <w <2m, has optimal negaperiodic autocorrelation.In[6], we showed that there exists a binary sequence of length 2m ≡ 2 mod 4 with optimal negaperiodic autocorrelation if and only if there exists a quasi-orthogonal cocycle over Z2 × Zm that is not a coboundary. A pair φ1, φ2 of binary (resp., quaternary) sequences, each of length n, such that NRφ1 (w) + NRφ2 (w) = 0(resp., Rφ1 (w) + Rφ2 (w) = 0) for 1 ≤ w ≤ n − 1isa negaperiodic Golay pair (NGP) (resp., quaternary periodic Golay pair). An n × n matrix H with entries in {± 1, ± i} is a quaternary complex Hadamard matrix or Butson Hadamard matrix (denoted BH(n, 4))if HH∗ = nI . We discuss how to construct BH(n, 4) from negaperiodic Golay pairs. In particular, we construct a BH(70, 4) that seems to be new. Previously there were two known inequivalent BH(70, 4), one due to Djokovic [7] and the other due to Egan [8]. Lemma 2 Let m be odd. There is a bijection between the set of negaperiodic Golay pairs of length 2m (denoted PUGP(2m,2,1)in [8]) and the set of periodic Golay pairs of quaternary sequences of length m (PUGP(m,4,0)in [8]). Proof Let ϕbe a binary sequence of length 2m, and (per [6, Lemma 1]) let φbe the (2,m)-array associated to ϕ, defined as follows. For m≡1mod4: φ(a,k)=⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ ϕ(k+am)k≡0mod4 (−1)1−aϕ(k+(1−a)m)k≡1mod4 −ϕ(k+am)k≡2mod4 (−1)aϕ(k+(1−a)m)k≡3mod4 and for m≡3mod4: φ(a,k)=⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ (−1)aϕ(k+am)k≡0mod4 ϕ(k+(1−a)m)k≡1mod4 (−1)1−aϕ(k+am)k≡2mod4 −ϕ(k+(1−a)m)k≡3mod4. Furthermore (per [6, Remark 1]), let fbe the associated quaternary sequence of length mdefined by f(k)=1−i 2(φ(0,k)+iφ(1,k)), φ(a,k)=Re(f(k)) −Im(f(k)) if a=0 Re(f(k)) +Im(f(k)) if a=1. By routine computation, (ϕ1,ϕ 2)is an NGP(2m) if and only if (f1,f2)is a periodic Golay pair of quaternary sequences of length m. Example 3 f1=(1,i,i,−i,1,1,−i,1,−1,−1,−i,−i,−1,−i,−i,i,i,1, −i,−i,−i,i,−i,1,−1,1,1,1,−i,−1,−1,1,1,i,1) and f2=(1,i,−1,−i,−i,1,i,−1,i,1,−i,i,−i,1,−i,−i,1,−i,i,1,i, −i,i,−1,i,−i,−1,−i,−i,−1,−i,i,−i,−1,i) is the quaternary periodic Golay pair as in Lemma 2associated to the NGP of length 70 in [12, p. 662]. The following is a special case of [8, Theorem 3.2]. Theorem 3 Let (f1,f2)be a quaternary periodic Golay pair of odd length m. Then H=AB −B∗A∗ is a BH(2m,4), where A and B are circulant matrices with first rows [f1(0),..., f1(m−1)]and [f2(0),..., f2(m−1)], respectively. Corollary 1 Theorem 3and Example 3furnish a new B H(70,4). Our method of constructing BH(70,4)is similar to the one in [8]; Egan uses a bijection between PUGP(m,4,1)and PUGP(2m,2,1). We point out that PUGP(2m,2,0)= PUGP(2m,2,1) and GP(2m)=PUGP(2m,2,0)∩PUGP(2m,2,1), where GP(2m)denotes thesetof binary(aperiodic) Golaypairsoflength2m.Egan[8, Theorem 2.2] proved that GP(m,4)=∩ 3 k=0PUGP(m,4,k) where GP(m,4)denotes the set of quaternary (aperiodic) Golay pairs. Thus, GP(m,4)=∩ 3 k=1PUGP(m,4,k). 5 Aperiodic optimal sequences The aperiodic autocorrelation at shift wof a binary sequence φof length nis Cφ(w) = 0≤k<n−w φ(k)φ(k+w). We observe that Rφ(w) =Cφ(w) +Cφ(n−w), NR φ(w) =Cφ(w) −Cφ(n−w). (5) Typically, sequences with good aperiodic autocorrelation are identified among sequences with good periodic autocorrelation. By (5), it might be advisable to search also among the sequences with good negaperiodic autocorrelation as a first step. We show how this task reduces yet again to the existence problem for quasi-orthogonal cocycles. Lemma 3 Let φbe a binary sequence of length 2m. Define μ∈Z2(Z2m,−1)\ B2(Z2m,−1)by μ( j,k)=(−1)(j+k)/2m, and put ψ=μ∂φ. Then NR φ(w) =φ(0)φ(w)ψ(n−w, w) 2m−1  j=0 ψ(n−w, j)∀w, 0<w<2m. Proof If Ais the 2m×2mnega-back-circulant {± 1}-matrix with first row [φ(0),..., φ(2m−1)], then [AA]1,j=NR φ(j−1). We normalize B=A◦Mμto obtain the coboundary matrix M∂φ, i.e., M∂φ =DBD where Dis the diagonal matrix with [D]j,j=φ(j−1)and ◦denotes Hadamard (componentwise) product. Since Mψ=M∂φ ◦Mμ=D(B◦Mμ)D=DAD,wehaveAA=DMψM ψD,so NR φ(j−1)=φ(0)φ( j−1)[MψM ψ]1,j. By Lemma 1, we are done.  Corollary 2 Let m be odd. Then φ=(φ(0), . . . , φ(2m−1)) ∈{±1}2mis optimal negaperiodic if and only if the cocycle μ∂φ is quasi-orthogonal. Proof This follows from Proposition 1and Lemma 3. The final topic that we consider concerns the merit factor of a binary sequence φ of length n: F(φ) =n2 20<w<n|Cφ(w)|2. The growth rate of the optimal merit factor, as sequence length increases, is related to a classical conjecture of Littlewood [14] about the asymptotic behavior of norms of polynomials on the unit circle. We bound F(φ) relying on the existence of quasiorthogonal coboundaries and non-coboundary cocycles over Z2m,modd. Proposition 2 Suppose that φis an OBS of length n ≡2mod 4, and let μbe as in Lemma 3.Ifμ∂φ is quasi-orthogonal, then Cφ(w) ∈{0,±1,±2}, with |Cφ(w)|=1 for n/2different values w. Hence n2 5n−8≤F(φ) ≤n.(6) Proof Each non-initial row sum of M∂φ is ±2 by Result 1. On the other hand, if ψ=μ∂φ is quasi-orthogonal, then Mψhas n 2rows summing to zero, and n−2 2rows summing to ±2 (Proposition 1). Therefore, (5) and Lemma 3yield that Cφ(w) +Cφ(n−w) =±2 Cφ(w) −Cφ(n−w) =0