Gröbner bases and cocyclic Hadamard matrices

Gröbner bases and cocyclic Hadamard matrices Víctor Álvarez, José Andrés Armario, Raúl M. Falcón, María Dolores Frau, Félix Gudiel Dpto. Matemática Aplicada I, Univ. Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain a b s t r a c t Keywords: Hadamard matrix Basis of cocycles Polynomial ring Ideal Hadamard ideals were introduced in 2006 as a set of nonlinear polynomial equations whose zeros are uniquely related to Hadamard matrices with one or two circulant cores of a given order. Based on this idea, the cocyclic Hadamard test enables us to describe a polynomial ideal that characterizes the set of cocyclic Hadamard matrices over a fixed finite group Gof order 4t. Nevertheless, the complexity of the computation of the reduced Gröbner basis of this ideal is 2O(t2), which is excessive even for very small orders. In order to improve the efficiency of this polynomial method, we take advantage of some recent results on the inner structure of a cocyclic matrix to describe an alternative polynomial ideal that also characterizes the aforementioned set of cocyclic Hadamard matrices over G. The complexity of the computation decreases in this way to 2O(t). Particularly, we design two specific procedures for looking for Zt×Z2 2-cocyclic Hadamard matrices and D4t-cocyclic Hadamard matrices, so that larger cocyclic Hadamard matrices (up to t≤39) are explicitly obtained. 1. Introduction A binary Hadamard matrix H of order nis an n ×nmatrix with every entry either 1or −1, which satisfies HHT=nI, where Iis the identity matrix of order n. Although it is well-known that nhas to be necessarily 1, 2or a multiple of 4(as soon as three or more rows have to be simultaneously orthogonal), there is no certainty whether such a Hadamard matrix exists at every possible order. Currently, the smallest order for which no Hadamard matrix is known is 668, and there are only 12 such orders below 2000 (Ðokovic et al. (2014)). The Hadamard conjecture asserts that there exists a Hadamard matrix of order 4tfor every natural number t. There exist many different constructions for Hadamard matrices: Sylvester, Paley, Williamson, Ito, Goethals–Seidel, one and two circulant cores or cocyclic matrices, amongst others (see Horadam (2007)). Nevertheless, most of them fail to yield Hadamard matrices for every order which is a multiple of 4 and therefore are not suitable candidates for a proof of the Hadamard conjecture. Among all these constructions, it seems that the most promising are the two circulant cores matrices (Fletcher et al. (2001); Kotsireas et al. (2006b)), the Goethals–Seidel arrays (Goethals and Seidel (1967); Seberry and Yamada (1992)) and the cocyclic constructions (Horadam (2007)). Actually, the one and two circulant cores constructions have recently been described to be somehow cocyclic-based (the cores themselves are cocyclic over Z4t−1and D4t−2, respectively, see Álvarez et al. (2017) for details). A stronger version of the Hadamard conjecture, posed by Horadam and de Launey (1995) is the cocyclic Hadamard conjecture: this states that there exists a cocyclic Hadamard matrix at every possible order. Currently the smallest order for which no cocyclic Hadamard matrix is known is 188 (Horadam (2007)). Kotsireas et al. (2006a) introduced the concept of Hadamard ideal as a set of nonlinear polynomial equations whose zeros determine the set of Hadamard matrices with one circulant core. Shortly after, Kotsireas et al. (2006b) used the same ideal together with a series of new polynomials in order to determine the set of Hadamard matrices with two circulant cores, by means of which they computed the Hadamard matrices with two circulant cores up to order 52. In this paper, we define several cocyclic Hadamard ideals, whose zeros determine the set of cocyclic Hadamard matrices over a finite group Gof order 4t. Based on the cocyclic test of Horadam and de Launey (1995), our first approach (Theorem 2) gives rise to a procedure CocGM(t, G, opt)which works just for very small t, actually t≤3. In order to improve the efficiency of this polynomial method and provided a basis of G-cocycles is known (which is always the case, see Flannery and O’Brien (2000); Flannery and Egan (2015)), we define in Theorem 5 an alternative ideal based upon the system of equations described by Álvarez et al. (2008), which also characterizes the set of G-cocyclic Hadamard matrices. This gives a procedure CocCB(t, G, opt)suitable for larger values of t. Furthermore, from the knowledge of the properties of cocyclic matrices over Zt×Z2 2and D4tdescribed by Álvarez et al. (2015, 2016), improved versions of this procedure (CocAH(t, col, dist, H)and CocDH(t, dist, opt, H), based on Theorems 7 and 9, respectively) are used to perform local searches for Zt×Z2 2-cocyclic Hadamard matrices and D4t-cocyclic Hadamard matrices. All the procedures have been implemented as a library hadamard.lib in the open computer algebra system for polynomial computations Singular, developed by Decker et al. (2016). Examples illustrating the use of this library and thelibrary itself are available onlineat http://personales.us.es/ raufalgan/LS/hadamard.lib. Further, all the computations that are exposed throughout the paper are implemented in a system with an AMD Opteron 6348, with a 2.8 GHz processor (48 cores), 256 GB RAM and 3 TB Hard Drive. Running the procedures on this system, cocyclic Hadamard matrices have been found up to order 4t≤156. The remainder of the paper is organized as follows. The first part of Section 2is devoted to describing some preliminary concepts and results on Hadamard matrices and Algebraic Geometry, that are used in the rest of the paper. Later, we define a zero-dimensional ideal that determines the set of cocyclic Hadamard matrices over a given group Gof order 4t, which comes from a straightforward translation of the cocyclic Hadamard test of Horadam and de Launey (1995). In Section 3, we propose an alternative to the previous construction by defining a new zero-dimensional ideal, based on the results of Álvarez et al. (2008). Actually, we specialize this procedure for Zt×Z2 2-cocyclic Hadamard matrices and D4t-cocyclic Hadamard matrices, attending to the properties described by Álvarez et al. (2015, 2016). The last section is devoted to conclusions and outlines for further work. 2. Preliminaries We describe in this section some basic concepts and results on Hadamard matrices and Algebraic Geometry that are used throughout the paper. We refer to the monographs of Mac Lane (1995), Horadam (2007), De Launey and Flannery (2011) and Cox et al. (1998, 2007) for more details about these topics. 2.1. Hadamard matrices Assume throughout that G ={g1=1, ..., g4t}is a multiplicative finite group of 4telements, not necessarily abelian. A function ψ:G ×G →−1 ∼ =Z2is said to be a (binary) cocycle over G, or simply G-cocycle for short, if it satisfies that ψ(gi,gj)ψ(gigj,gk)=ψ(gj,gk)ψ(gi,gjgk), for all gi,gj,gk∈G.(1) The cocycle ψis naturally displayed as a cocyclic matrix Mψof order 4t×4t, whose (i, j)th entry is ψ(gi, gj)for all gi, gj∈G. Since it must be ψ(1, gj) =ψ(gi, 1)for all gi, gj∈G, the first row and column of Mψare all either 1 or −1. In the first case, the cocycle ψand its cocyclic matrix Mψare said to be normalized. There is a one to one correspondence between normalized and non normalized cocycles. Without loss of generality, we will assume that all cocycles considered hereafter are normalized, and will be termed simply cocycles for short. Let gd∈G. The elementary coboundary ∂dis the cocycle over Gdefined as ∂d(i,j):= δgd(gi)δgd(gj)δgd(gigj), where δgd:G →−1is the characteristic set map such that δgd(gi) =−1if gi=gdand 1, otherwise. The generalized coboundary matrix M∂dconsists of negating the dth-row of the matrix M∂d. Note that negating a row or a column of a matrix does not change its Hadamard character. This is just a particular case of a more general set: there is an equivalence relation (termed Hadamard equivalence) on Hadamard matrices, so that two matrices are Hadamard equivalent whenever they differ in a series of row and/or column negations and/or permutations. These Hadamard equivalence classes may be grouped by means of a broader notion of equivalence relation which incorporates some different orthogonality preserving moves, termed switching operations. The interested reader is referred to Orrick (2008) and the references therein for details. The following technical result summarizes some properties which are satisfied by generalized coboundary matrices, as described in Álvarez et al. (2008), and will be of interest for later use. Lemma 1 (Álvarez et al. (2008)). The next results hold. a) M∂dcontains exactly two negative entries in each row s = 1, which are located at positions (s, d)and (s, e), for ge=g−1 sgd. b) Given gs= 1and gcin G, there are exactly two generalized coboundary matrices (M∂cand M∂d), with a negative entry in the position (s, c), where gd=gsgc. c) Two generalized coboundary matrices share their two negative entries at the sthrow if and only if g2 s=1. A basis B ={ψ1, ..., ψk}of cocycles over Gconsists of some elementary coboundaries ∂iand some representative cocycles. Since the elementary coboundary ∂1related to the identity element 1 ∈Gis not normalized, we may assume that ∂1/∈B. A basis for coboundaries consists of 4t−r−1 elements, for rbeing the rank of the Sylow 2-subgroup of G/[G, G], and may be calculated straightforwardly (see Horadam and de Launey (1995); Flannery and Egan (2015)). A basis for representative cocycles consists of rcocycles coming from Ext(G/[G, G], Z2)and k −4t+1 cocycles (one for each 2-power component of H2(G)) coming from Hom(H2(G), Z2), and may be calculated by means of aMagma (Bosma et al. (1997)) procedure as described in Flannery (1996); Flannery and O’Brien (2000). Every cocycle over Gadmits a unique representation as a product of the generators in B, ψ=ψx1 1···ψxk k, xi∈{0, 1}. The tuple (x1, ..., xk)Bdefines the coordinates of ψwith regards to B. Accordingly, every cocyclic matrix Mψ=(ψ(i, j)), for ψ=(x1, ..., xk)B, admits a unique decomposition Mψ=Mx1 ψ1···Mxk ψkas the Hadamard pointwise product of those matrices Mψicorresponding to entries xi=1. In what follows, we use generalized coboundary matrices instead of classical coboundary matrices. Let us point out that any matrix obtained as the Hadamard product of generalized coboundary matrices and representative cocycles is Hadamard equivalent to a cocyclic matrix by means of negations of certain rows. A cocycle ψ(over G) is said to be orthogonal if its cocyclic matrix Mψis Hadamard. In such a case, Mψis said to be a cocyclic Hadamard matrix over Gor a G-cocyclic Hadamard matrix. The set of cocyclic Hadamard matrices over Gis denoted by HG. The cocyclic Hadamard test of Horadam and de Launey (1995) asserts that a cocyclic matrix Mψis Hadamard if and only if  j∈G ψ(i,j)=0,for all i∈G\{1}.(2) A row of Mψis termed Hadamard row precisely when its summation is zero. Therefore, Mψis Hadamard if and only if every row (but the first) is a Hadamard row. 2.2. Algebraic geometry Let {X}and K[X]be, respectively, the set of mvariables {x1, ..., xm}and the associated multivariate polynomial ring over a field K. The affine variety V (I)of an ideal I⊆K[X]is the set of points in Kmthat are zeros of all the polynomials of I. The ideal Iis said to be zero-dimensional if V(I) is finite. It is said to be radical if every polynomial p ∈K[X]belongs to Iwhenever there exists a natural number nsuch that pn∈I. A term order <on the set of monomials of K[X]is a multiplicative well-ordering that has the constant monomial 1as its smallest element. The largest monomial of a polynomial pof Iwith respect to the term order <is its leading monomial. The ideal generated by the leading monomials of all the non-zero elements of Iis its initial ideal I<. Those monomials of polynomials of Ithat are not leading monomials of any polynomial of Iare called standard monomials. If the ideal Iis zero-dimensional, then the number of standard monomials of Icoincides with the dimension of K[X]/Iover K, which is greater than or equal to the number of points of V(I). The equality holds when Iis radical. This dimension can be obtained by computing the Hilbert function HFK[X]/I, which maps each non-negative integer donto dimK(K[X]d/Id), where K[X]ddenotes the set of homogeneous polynomials in K[X]of degree dand Id=K[X]d∩I. In particular, dimK(K[X]/I) =0≤dHFK[X]/I(d). If the ideal Iis zero-dimensional, then the number HFK[X]/I(d) coincides with the set of standard monomials of degree d, regardless of the term order. As a consequence, the Hilbert function of K[X]/Icoincides with that of K[X]/I<, for any term order <, which can be obtained by using for instance the algorithm of Mora and Möller (1983). Previously, it was required to determine the initial ideal I<. In any case, Bayer and Stillman (1992) already proved that the problem of computing Hilbert functions is NP-complete. A Gröbner basis (Buchberger (2006)) of the ideal Iis any subset GB of polynomials of Iwhose leading monomials with respect to a given term order generate the initial ideal I<. It is reduced if all its polynomials are monic and no monomial of a polynomial in GB is generated by the leading monomials of the rest of polynomials in the basis. There exists a unique reduced Gröbner basis of the ideal I. This basis generates the initial ideal I<and can be used, therefore, to determine the cardinality of its affine variety V(I). Further, the points of this variety can be enumerated once the reduced Gröbner basis is decomposed into finitely many disjoint subsets, each of them being formed by the polynomials of a triangular system of polynomial equations, whose factorization and subsequent resolution are easier than the system related to the generators of the original ideal I. See in this regard the articles of Hillebrand (1999), Lazard (1992) and Möller (1993). Gröbner bases can, therefore, be used to determine both the cardinality and the elements of the set HGof cocyclic Hadamard matrices over a multiplicative finite group Gof 4telements. To this end, let Q[XG]be the polynomial ring over the field Qof rational numbers, with set of 16t2variables {XG} ={xi,j:gi, gj∈G}and let us define the polynomial pi,j,k(X):= xi,jxij,k−xj,kxi,jk,for all gi,gj,gk∈G, where the products ij and jk are induced by the group law in G. The next result shows how the set HGof cocyclic Hadamard matrices over Gcan be identified with the affine variety defined by a zero-dimensional radical ideal of nonlinear polynomials in Q[XG]. Theorem 2. The set HGcan be identified with the set of zeros of the zero-dimensional ideal IG=I1 G+I2 G+ I3 G+I4 G⊂Q[XG]consisting in the summation of the following four subideals: ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ I1 G=x2 i,j−1:i,j∈G, I2 G=pi,j,k(X):i,j,k∈G, I3 G=x1,i−1,xi,1−1:i∈G, I4 G=j∈Gxi,j:i∈G\{1}. Besides, |HG| =dimQ(Q[XG]/IG). Proof. Let P=(p1,1, ..., p4t,4t)be a point of the affine variety V(IG). Attending to I1 G, every component pi,jof Pis either 1or −1, for all i, j ∈G. Let ψ:G ×G →{±1}be defined such that ψ(i, j) =pi,j, for all gi, gj∈G. Since I2 Gimplies by construction that ψsatisfies identity (1) for all gi, gj, gk∈G, the point Pcan be identified with the cocyclic matrix Mψrelated to ψ(which is, in addition, normalized, because of the definition of the subideal I3 G). Finally, I4 Gimplies that Mψsatisfies identity (2) and hence, Mψis Hadamard. The affine variety V(IG)coincides, therefore, with the set HG, whose finiteness involves the ideal IGto be zero-dimensional. Besides, since IG∩Q[xi,j] = x2 i,j−1  ⊆IGfor all i, j ∈Gand all these polynomials are square-free, Proposition 2.7 of Cox et al. (1998) implies that IG=IG+ i,j IG∩Q[xi,j]=IG, so IGis therefore radical. And hence, |HG| =|V(IG)| =dimQ(Q[XG]/IG).2 Notice that, as defined, each of the subideals I1 G, I2 G, I3 Gand I4 Gare generated by 16t2, 64t3, 8t−1 and 4t−1 polynomials over the set of 16t2variables XG. Nevertheless, some of these polynomials are redundant and may straightforwardly be removed from a system of generators for IG. Namely, it is easy to check that I3 G⊂x1,1−1 +I2 G, as the result of a standard proof on the fact that any cocycle is either normalized or unnormalized (see Lemma 1.3 of Horadam and de Launey (1995) for details). Furthermore, the 8t−1 polynomials {x2 1,i−1, x2 i,1−1 :i ∈G}in I1 Gmay be removed as well, since they are also in I3 G. Anyway, the set of polynomials generating IGwhich we have just described consists of O(t3)polynomials of degree up to 2over O(t2)variables. It is a remarkable fact that the computation of the reduced Gröbner basis of a zero-dimensional ideal is extremely sensitive to the number of variables. See in this regard the articles of Hashemi (2009), Hashemi and Lazard (2011), Lakshman (1991) and Lakshman and Lazard (1991). In the last reference, the authors proved that the complexity of our computation is dO(n), where dis the maximal degree of the generators of ideal and nis the number of variables. In the case of Theorem 2, this complexity is 2O(t2), which renders the computation only possible for very low values of t. The procedure CocGM(t, G, opt)(included in the library hadamard.lib which is available online for free at the personal web page of one of the authors, as noticed before) provides an implementation of the method that runs on Singular (Decker et al. (2016)). It is specifically designed for the group Zt×Z2 2(taking G =1as input) and the dihedral group D4t(taking G =2as input), though it might be straightforwardly modified to fix for any other group G. It would suffice to include the polynomials generating the subideal I2 G, attending to the particular group law of G. Depending on whether the parameter opt is equal to 1 or 2, the procedure calculates either just the number of cocyclic Hadamard matrices over Gor the explicit full set of these matrices. Notice that it makes use of the Singular procedures elimlinearpart and tolessvars which speed up and simplify the calculations, reducing the number of variables and polynomials in turn. Example 3. As an illustration of the method, consider the group G =Z2 2. The ideal IG, as described in Theorem 2, is defined over the set of 16 variables {XG} ={xi,j:gi, gj∈G}and initially consists of 90 generating polynomials, although we already pointed out before that some of these polynomials are redundant and may be removed straightforwardly from the very beginning. Assuming x1,i=xi,1=1 for 1 ≤i ≤4, we reduce to 9 variables, namely xi,j, for 2 ≤i, j ≤4. A reduced Gröbner basis for IGwith respect to the degree reverse lexicographical order consists of the following 14 polynomials: p1=x4,2+x4,3+x4,4+1, p2=x3,2+x3,3+x3,4+1, p3=x2,4+x3,4+ x4,4+1, p4=x2,3+x3,3+x4,3+1, p5=x2,2+x2,3+x2,4+1, p6=x2 4,4−1, p7=x4,3x4,4+x4,3+x4,4+1, p8=x3,4x4,4+x3,4+x4,4+1, p9=x2 4,3−1, p10 =x3,4x4,3+x3,3x4,4−x3,3−x3,4−x4,3−x4,4−2, p11 =x3,3x4,3−x3,3−x4,3−1, p12 =x2 3,4−1, p13 =x3,3x3,4−x3,3−x3,4−1, p14 =x2 3,3−1. These polynomials consist of monomials which may be organized into two subsets, leader monomials LM ={x2,2, x2,3, x2,4, x3,2, x4,2, x2 3,3, x3,3x3,4, x3,3x4,3, x2 3,4, x3,4x4,3, x3,4x4,4, x2 4,3, x4,3x4,4, x2 4,4} and standard monomials SM ={1, x3,3, x3,4, x4,3, x4,4, x3,3x4,4}. Since |SM| =6, the affine variety V(IG)consists of 6 points Pk=(x(k) 2,2, x(k) 2,3, x(k) 2,4, x(k) 3,2, x(k) 3,3, x(k) 3,4, x(k) 4,2, x(k) 4,3, x(k) 4,4), 1 ≤k ≤6, as well. These points ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ P1=(−1,−1,1,−1,1,−1,1,−1,−1), P2=(−1,1,−1,−1,−1,1,1,−1,−1), P3=(−1,−1,1,1,−1,−1,−1,1,−1), P4=(1,−1,−1,−1,−1,1,−1,1,−1), P5=(−1,1,−1,1,−1,−1,−1,−1,1), P6=(1,−1,−1,−1,1,−1,−1,−1,1), provide the 6 normalized cocyclic Hadamard matrices over Z2 2, consisting of 3 ×3 cores with exactly one positive entry at each row iand at each column j, 2 ≤i, j ≤4.  As a matter of fact, running the procedure CocGM(t, G, opt)in our computer system, the computation of the reduced Gröbner bases of the ideals related to the group Zt×Z2 2and the dihedral group D4tare only feasible for t≤3(see Table 1). Unfortunately, for higher orders, the system runs out of memory, and some new insight is needed to improve the method. In Section 3we define another ideal JGfor computing HGin a more subtle way, based on the previous work of Álvarez et al. (2008). Unfortunately, it will still be extremely hard to compute HGfor large |G|. Nevertheless, taking advantage of the properties of cocyclic matrices over D4tand Zt×Z2 2 described by Álvarez et al. (2015, 2016), this ideal JGmay be specifically simplified for computing HD4tand HZt×Z2 2in a better way. 3. Ideals built from a basis for G-cocycles In order to reduce the complexity of the computation of the reduced Gröbner basis that has been described in the previous section, we consider a new zero-dimensional radical ideal JGrelated to the set HG, where we diminish the number of variables and the maximal degree of the polynomials. For this purpose, what is needed is just knowing an explicit basis for cocycles over G, which the methods of Horadam and de Launey (1995); Flannery (1996); Flannery and O’Brien (2000); Flannery and Egan (2015); Álvarez et al. (2009) provide. Let Gbe a multiplicative finite group of order 4t, B ={ψ1, ..., ψk}be a basis for normalized cocycles over Gand ψbe a normalized cocycle over Gof coordinates (x1, ..., xk)Bwith regards to B, so that ψ=ψx1 1···ψxk k, for some xi∈{0, 1}, 1 ≤i ≤k. Let md i,jdenote the (i, j)th entry of Mψd, so that the (i, j)th entry of Mψis (m1 i,j)x1···(mk i,j)xk. Recall that cocyclic Hadamard matrices are precisely those matrices that are built up from Hadamard rows (excepting the first row, consisting all of 1s). In these circumstances, the ith-row of the previous matrix Mψis Hadamard if and only if 4t  j=1 (m1 i,j)x1···(mk i,j)xk=0. The next result holds. Theorem 4 (Álvarez et al. (2008)). The matrix Mψis Hadamard if and only if the vector of coordinates (x1, ..., xk)Bof ψwith regards to Bsatisfies the following system of 4t−1equations and k unknowns ⎧ ⎪ ⎨ ⎪ ⎩ (m1 2,1)x1...(mk 2,1)xk+...+(m1 2,4t)x1...(mk 2,4t)xk=0 . . . (m1 4t,1)x1...(mk 4t,1)xk+...+(m1 4t,4t)x1···(mk 4t,4t)xk=0 (3) The solutions of the system (3) constitute precisely the whole set of normalized cocyclic Hadamard matrices over G. Trying to solve this system may be as complicated as performing an exhaustive search for cocyclic Hadamard matrices over G. Instead, we intend to translate the system (3) in terms of a set of nonlinear Q[X]-polynomial equations over the set of variables {X} ={x1, ..., xk}(whose 0, 1values are related to the coordinates of G-cocycles with regards to B), and to study the structure of the associated ideal. A succinct algebraic description of the quadratic constraints {X} ⊂{0, 1}kis provided by the following set of kalgebraic equations: xi(xi−1)=0,for all i∈{1,...,k}.(4) In order to define the rest of polynomial equations that arise from the system (3), we use the next two main ideas for simplifications: •From a practical point of view, we may assume we work with a fixed representative cocycle ρ among all of the possible choices of representative cocycles. In fact, empirically, in the groups most intensively studied, there always exists a choice ρof representative cocycle that tends to be the most successful for providing Hadamard matrices. See in this regard the works of Álvarez et al. (2008, 2015, 2016), Baliga and Horadam (1995), Flannery (1997) and Horadam (2007). We will denote by Mρ=(ri,j)the matrix related to this representative cocycle ρ. Obviously, this pruning in the searching space leads to the circumstance that some G-cocyclic Hadamard matrices are lost (namely, if they do exist, those lying on a cocyclic equivalence class different to that of ρ). For instance, this is the case of the 1400 cocyclic Hadamard matrices over D4·5, listed in Table 1, where 800 matrices Mψare missing from the total amount of 2200 D4·5-cocyclic Hadamard matrices. If we want to find the whole set of cocyclic Hadamard matrices, we have to perform an analogous search for the other possible choices of Mρ. In what follows we assume that ψ1, ..., ψk−m∈Bare G-coboundaries, ψk−m+1, ..., ψk∈Bare representative G-cocycles and ρ= k  i=k−m+1 ψxi iis a fixed linear combination of these representative cocycles. •The second property of Lemma 1 implies that the hth summand of the lth equation in (3) reduces to be rl+1,h(mi l+1,h)xi(mj l+1,h)xj, for iand jdefining the (unique) two generalized coboundaries M∂iand M∂jsharing a negative entry in the position (l +1, h). Namely, {i, j} ={h, (l +1)h}. Notice that, eventually, one or even both of these coboundaries ∂h, ∂(l+1)hmight not be in B. Actually, the monomial sl,h(X)related to the aforementioned hth summand of the lth equation in (3) depends on whether the two, just one or none of the coboundaries ∂h, ∂(l+1)h(precisely those whose related generalized coboundary matrices contribute a negative entry at position (l +1, h)) are in B. More concretely, •If both ∂h, ∂(l+1)h, ∈B, then sl,h(X):= rl+1,h(1−2xh)(1−2x(l+1)h). •If just one of them is in B, say {i} ={h, (l +1)h} ∩B, then sl,h(X):= rl+1,h(1−2xi). •If both ∂h, ∂(l+1)h/∈B, then sl,h(X):= rl+1,h. Let Sl(X) := 4t  j=1 sl,j(X)and let Hρ Gbe the set of solutions of (3) of the form ψ=ρ k−m  i=1 ψxi i. The set Hρ Gcoincides with the set of solutions of the system of polynomial equations xi(xi−1)=0,if 1 ≤i≤k−m, Sl(X)=0,if 1 ≤l≤4t−1. Similarly to Theorem 2, the next result holds. Theorem 5. The set Hρ Gcan be identified with the set of zeros of the zero-dimensional ideal JG=J1 G+J2 G⊂ Q[X]consisting in the summation of the following two subideals: J1 G=x2 i−xi:i∈{1,...,k−m}, J2 G=Sl(X):l∈{1,...4t−1}. Moreover, |Hρ G| =dimQ(Q[X]/JG). Proof. Similarly to Theorem 2, let P=(p1, ..., pk−m)be a point of the affine variety V(JG). Attending to J1 G, every component piof Pis either 1or 0, for all 1 ≤i ≤k −m. Let ψ:G ×G →{±1}be defined such that ψ=ρ k−m  i=1 ψxi i. Since J2 Gimplies by construction that Mψsatisfies (4), the point Pcan be identified with the cocyclic Hadamard matrix Mψrelated to ψ. The affine variety V(JG)coincides, therefore, with the set HG, whose finiteness involves the ideal JGto be zero-dimensional. Besides, since JG∩Q[xi] = x2 i−xi ⊆JGfor all 1 ≤i ≤k −mand all these polynomials are square-free, Proposition 2.7 of Cox et al. (1998) implies that JG=JG+ i JG∩Q[xi]= JG, so JGis therefore radical. And hence, |Hρ G| =|V(JG)| =dimQ(Q[X]/JG).2 Notice that, as defined, the ideal JGis generated by O(t)polynomials of degree up to 2over the set of O(t)variables {x1, ..., xk−m}. Observe in particular that, according to Lakshman and Lazard, the Table 1 Running times related to CocGM and CocCB. t|Hρ Zt×Z2 2 |Running time in seconds |Hρ D4t|Running time in seconds CocGM CocCB CocGM CocCB 16 0(0)0(0)60(0)0(0) 324 102(4255)0(0)72 −0(0) 5 120 −7(93)1400 −11 (5826) 7−−−7488 −52282 (−) complexity of the computation of the reduced Gröbner decreases from 2O(t2)in Theorem 2 to 2O(t) in Theorem 5. The procedure CocCB(t, G, opt)(included in the library hadamard.lib as well) provides an implementation of this method. It is specifically designed for the group Zt×Z2 2(taking G =1as input and using (5) as the representative cocycle ρ) and the dihedral group D4t(taking G =2as input and using (6) as the representative cocycle ρ), though it might be straightforwardly modified to fix for any other group G. It would suffice to actualize the polynomials Sl(X), attending to the particular group law of Gand the corresponding representative cocycle ρ. Once again, depending on whether the parameter opt is equal to 1 or 2, the procedure calculates either just the number of cocyclic Hadamard matrices over Gor the explicit full set of these matrices. In order to check the efficiency of this alternative, the procedure has been tested in the computation of the number of cocyclic Hadamard matrices developed over the group Zt×Z2 2and the dihedral group D4tof order 4t. Running times to compute this number on our computer system are exposed in Table 1, where we also indicate in parentheses the running time that is required to determine the explicit full set of matrices. Notice that although there are actually 2200 cocyclic Hadamard matrices over D4·5, just 1400 of them lies on the cocyclic equivalence class [ρ]of ρas defined in (6) (see Álvarez et al. (2008) for details). This explains the output of the procedure, which limits to compute those cocyclic Hadamard matrices lying on the cocyclic equivalence class of [ρ]. Anyway, this is not a source of problems as we commented before, since this case seems to provide most of the D4t-cocyclic Hadamard matrices known so far (see Flannery (1997); Álvarez et al. (2008, 2016)). Actually, this procedure CocCB(t, G, opt)might be improved if a deeper knowledge about the inner structure of cocyclic matrices over Gis known. In particular, building on the works of Álvarez et al. (2015, 2016), we have been able to design two specific procedures for looking for Zt×Z2 2-cocyclic Hadamard matrices and D4t-cocyclic Hadamard matrices, so that larger cocyclic Hadamard matrices (up to t≤39) are obtained. The details are described in the next two subsections. 3.1. The group Zt×Z2 2 Let Gbe the abelian group Zt×Z2 2=a, b, c:at=b2=c2=1, t>1 odd, with ordering {1,c,b,bc,a,ac,ab,abc,...,at−1,at−1c,at−1b,at−1bc}, indexed as {1, ..., 4t}. A basis B ={∂2, ..., ∂4t−2, β1, β2, β3}for cocycles over Gis described by Álvarez et al. (2008, 2009), and consists of 4t−3 coboundaries and three representative cocycles. As usual, ∂i refers to the coboundary associated to the ith-element in G. An explicit description of these cocycles may be found in Álvarez et al. (2008). Notice that all cocyclic Hadamard matrices over Zt×Z2 2known so far use all the three representative cocycles β1, β2and β3simultaneously (see the paper of Baliga and Horadam (1995) for details). Thus, we assume Mρ=1t⊗⎛ ⎜ ⎜ ⎝ 1111 1−11−1 1−1−11 11 −1−1 ⎞ ⎟ ⎟ ⎠ (5)