A Mixed Heuristic for Generating Cocyclic Hadamard Matrices

A Mixed Heuristic for Generating Cocyclic Hadamard Matrices V. Alvarez · J. A. Armario · R. M. Falcón · M. D. Frau · F. Gudiel · M. B. Güemes · A. Osuna Abstract A way of generating cocyclic Hadamard matrices is described, which combines a new heuristic, coming from a novel notion of fitness, and a peculiar local search, defined as a constraint satisfaction problem. Calculations support the idea that finding a cocyclic Hadamard matrix of order 4 · 47 might be within reach, for the first time, progressing further upon the ideas explained in this work. Keywords Hadamard matrices · Cocyclic matrices · Heuristic · Constraint satisfaction problem This work was completed with the supports of FQM-016 from Junta de Andalucía and Departamento de Matemática Aplicada I de la Universidad de Sevilla. The authors want to express their gratitude to the anonymous referees for their pertinent comments and suggestions, which have permitted to improve the readability and understandability of the paper. V. Alvarez (B)·J. A. Armario ·M. D. Frau ·F. Gudiel ·A. Osuna Dpto. Matemática Aplicada I, ETSI Informatica, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain e-mail: valv[email protected] J. A. Armario e-mail: [email protected] M. D. Frau e-mail: [email protected] F. Gudiel e-mail: [email protected] A. Osuna e-mail: [email protected] R. M. Falcón Dpto. Matemática Aplicada I, ETSA, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain e-mail: [email protected] M. B. Güemes Dpto. Álgebra, Fac. Matemáticas, Universidad de Sevilla, c./ Tarfia s/n, 41012 Sevilla, Spain e-mail: [email protected] 1 Introduction Square matrices with entries in {1,−1}whose rows are pairwise orthogonal are termed binary Hadamard matrices, and were introduced in the nineteenth century, related to the maximum determinant problem. They are conjectured to exist for every order 1, 2 or multiple of 4, but nowadays the problem of their existence remains still open. Many constructions of Hadamard matrices are known. Among them, we are particularly interested in cocyclic Hadamard matrices, those Hadamard matrices Hadamard equivalent (by means of row/columns permutations/negations) to matrices Mψ=(ψ(i,j)) related to some 2-cocycle ψ∈Z2(G;ZZ2),ψ:G×G→{±1}, i.e. satisfying that ψ(i,j)ψ(ij,k)ψ(i,jk)ψ(j,k)=1,i,j,k∈G, for Ga finite group with given order {1,...,4t}, 1 being the identity element. Precisely, these relations yield a fast cocyclic Hadamard test, consisting in checking whether the summation of each row of Mψ(but the first) is zero,  j∈G ψ(i,j)=0,i∈G\{1},(1.1) in which case ψis said to be orthogonal. Unfortunately, it is far from clear whether it is easier to construct cocyclic Hadamard matrices better than usual binary Hadamard matrices. Some light on this purpose was thrown in [5], where cocyclic Hadamard equivalence classes were identified up to order 40. The interested reader is referred to [6,10–12] for further explanations on (cocyclic) Hadamard matrices and related structures. The set of cocycles forms an abelian group Z2(G,ZZ2)under pointwise multiplication. The simplest cocycles are the coboundaries ∂f, defined for any function f:G→{±1}by ∂f(g,h)=f(g)−1f(h)−1f(gh). The subgroup of coboundaries, B2(G,ZZ2), is naturally generated by the set of elementary coboundaries ∂i:= ∂δi, where δiis the Kronecker delta function of the ith-element in Gin the given ordering. Cocycles may be grouped into cohomological classes, to form H2(G;ZZ2)=Z2(G,ZZ2)/B2(G,ZZ2), so that [ψ]=[ψ]∈H2(G,ZZ2)⇔ψ=ψ|G| i=1∂ri i, for ri∈{0,1}. This way, fixed a representative cocycle [ρ]∈H2(G;ZZ2), in order to look for cocyclic Hadamard matrices Mψover G,for[ψ]=[ρ]∈H2(G;ZZ2), it suffices to look for a subset of elementary coboundaries ∂ij such that ψ=ρk j=1∂ijis orthogonal. From (1.1), a cocyclic matrix Mψover Gis Hadamard if and only if the summation of each row 2 ≤i≤|G| is zero. This fact leads straightforwardly to a naive fitness function f1:Z2(G;ZZ2)→Z+, which measures the amount of rows of Mψwhich fail to sum up zero. Searching for a global minimum for f1would end providing a cocyclic Hadamard matrix Mψover G, if one exists, as soon as f1(ψ) =0. Several years ago, some of the authors developed some heuristic procedures searching for cocyclic Hadamard matrices (see [3] and the references therein for details). Most of them used the notion of fitness defined above and seemed to work fine. However, although the procedures converged to a truly cocyclic Hadamard matrix, as desired, unexpectedly we have realized that there is not any apparent correlation between a matrix Mψbeing close to be Hadamard (say, differing just in one coboundary from being a cocyclic Hadamard matrix), and the fitness value f1(ψ) as it is actually defined (i.e. the number of its rows which fail to sum up zero), which by no means has necessarily to be close to zero as well. Table 1(distributed in several pages due to size limitations) shows some examples of cocyclic Hadamard matrices Mψover D4t, for odd values of 3 ≤t≤17, so that modified by the action of just one coboundary ∂i(as indicated in eachcase),giverisetococyclicmatricesattainingfitness f1(ψ∂i)whichalmostfulfilltheprospectiverange[1,t−1]. Here we assume D4t=a,b:a2t=b2=1,ab =ba−1and the ordering {1,a,...,a2t−1,b,ab,...,a2t−1b} in D4t. The representative cocycle ρis fixed to be Mρ=BN2tBN2t BNs 2t−BNs 2t Table 1 f1does not depend on the Hamming distance from a full Hadamard matrix! ti j:ψ=ρk j=1∂ijis orthogonal i:ψ=ψ·∂if1(ψ∂i) 35,10 2 1 82 5 7, 8, 12, 16, 18 8 1 22 33 14 4 7 2, 6, 7, 17, 19, 22, 23, 25 5 1 42 23 74 12 5 7 6, 9, 17, 19, 21, 24, 25 19 6 9 2, 7, 8, 12, 21, 23, 25, 28, 29, 31, 32 32 1 21 2 33 24 75 10 6 23 7 11 2, 3, 6, 8, 9, 10, 11, 12, 13, 15, 18, 19, 21, 22, 25 2 24, 26, 30, 35, 36, 37, 42 13 3 44 35 15 6 27 36 8 11 2, 7, 9, 11, 15, 20, 22 1 23, 24, 25, 29, 30, 31, 34, 35, 37, 38, 40, 41 11 9 11 3, 5, 7, 10, 11, 13, 14, 15, 16, 20, 5 10 23, 24, 26, 29, 30, 31, 35, 36,38 13 3, 4, 6, 8, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 24, 26, 4 2 28, 31,32, 35, 39, 40, 42, 43, 44, 45, 50 7 3 24 55 12 6 67 15 8 20 9 17 10 13 2, 5, 6, 7, 9, 10, 11, 16, 17, 19, 21, 22, 23, 25, 26, 28 1 27, 29, 32, 33, 34, 35, 36, 38, 39, 41, 43, 44, 46, 47, 48, 49, 50 41 11 13 3, 5, 7, 8, 9, 11, 12, 15, 19, 22, 24, 25, 29 12 27, 29, 31, 32, 33, 34, 35, 36, 40, 41, 42, 45, 46, 47 Table 1 continued ti j:ψ=ρk j=1∂ijis orthogonal i:ψ=ψ·∂if1(ψ∂i) 15 4, 6, 7, 8, 9, 12, 13, 15, 16, 19, 21, 23, 24, 25, 26, 28, 29, 30, 13 2 34, 36, 40, 41, 44, 49, 50, 52, 54, 55 50 3 12 4 45 36 27 10 8 89 27 10 35 11 28 12 15 2, 4, 5, 7, 8, 10, 11, 17, 18, 19, 20, 21, 22, 24, 26, 27, 28, 32 1 33, 36, 37, 38, 40, 41, 42, 43, 44, 46, 48, 50, 51, 52, 53, 56, 57, 58 47 13 17 6, 7, 9, 11, 12, 13, 15, 19, 24, 29, 7 2 38, 39, 40, 41, 43, 47, 50, 51,54, 55, 57, 59, 60, 62, 65 24 14 17 2, 6, 8, 9, 13, 16, 20, 22, 23, 24, 27, 29, 32,33, 39, 42, 45, 46,47, 50, 51, 52, 60, 62 44 3 17 4 43 5 25 6 37 28 49 810 51 11 34 12 61 13 for BN2tbeing the back negacyclic matrix of order 2t, and BNs 2tbeing the matrix obtained from BN2tby displaying its rows from bottom to top. Notice that the only cases which are missed in these tables are fitness 8 for t=9, fitness 14 for t=15 and fitness 1, 15 and 16 for t=17. Anyway, we do not know whether some of them could actually exist, since we have not performed any exhaustive search, that is out of interest for our purposes. What is worth stressing is that, attending to the notion of fitness defined so far, cocyclic matrices Mψwhich fail to be Hadamard in just one coboudary might have any possible value of fitness f1(ψ), whereas it would have been desirable that they had fitness close to zero. Actually, this fact has motivated that we look for another way to define a new fitness function f2, which faithfully reflects how close is a matrix Mψto be Hadamard, in terms of a lower bound on the number of coboundaries which have to be modified in the expression defining ψso that a cocyclic Hadamard matrix might be obtained. This is the main concern of the paper. 2 A New Fitness Function As introduced in (1.1), we already know that a cocyclic matrix Mψover Gis Hadamard if and only if the summation of each row 2 ≤i≤|G|is zero. In [2] a way to check these conditions was described, in terms of paths and intersections of coboundaries, which we reproduce now. Every 2-cocycle over Gmay be described as a pointwise product ψ=ρk j=1∂ijof a representative (non trivial) cocycle ρ∈H2(G;Z2)and a subset of elementary coboundaries ∂ij,for∂ij(h,k)=δ(ij,h)δ(ij,k)δ(ij,hk), where δis the Kronecker delta function. Notice that such a subset {∂ij}is not unique, in general, until a basis for coboundaries is fixed. There is empirical evidence (at least, for the groups more intensively studied, see [2,4,8,10] for instance), that there always exists a choice ρof representative cocycle that tends to be the most successful for providing Hadamard matrices. For this reason, in the remainder of the paper, we will consider that such a ρis fixed, and hence the only variables to consider are the set of 4telementary coboundaries arising from G. Therefore, when convenient throughout the paper, any cocycle ψ=ρk j=1∂ij(or indistinctly the cocyclic matrix Mψbeneath, as well) may be naturally displayed as binary tuples vψof length 4t,theith entry being 1 if and only if i∈{i1,...,ik}, and 0 otherwise. Since negating a row of any coboundary matrix M∂hhas no effect in the validity of the cocyclic Hadamard test (1.1)forψ, in what follows we consider generalized coboundary matrices instead, obtained from the former by just negating the hth row. Nevertheless, for simplicity and convenience of the reader, we will preserve the same notation for both structures. At any row 2 ≤r≤4t, every generalized coboundary matrix M∂hhas exactly two negative entries, located at positions (r,h)and (r,r−1h),termedhead and tail, respectively. When the tail of a coboundary is the head of another coboundary at a row r, these coboundaries are said to form a r-path. Analogously, when a coboundary share a negative entry (no matter it is a head or a tail) at a row rwith the cocycle ρthen they form a r-intersection. Consequently, the cocyclic Hadamard test (1.1) may be reformulated in terms of paths and intersections, so that cr−Ir=t−ρr 2,2≤r≤4t,(2.1) where crdenotes the number of maximal r-paths in which the subset of coboundaries defining ψsplits into, Ir denotes the number of r-intersections that they give rise to, and ρrdenotes the amount of negative entries of Mρat row r. Notice that the right-hand sides of the Eq. (2.1) are constant, and do not depend on the subset of coboundaries defining ψ. However, the change of just one coboundary in the expression defining ψ, no matter either eliminated or introduced, reflects in the left-hand sides of Eq. (2.1) as changes of at most 1 unit (either increasing or decreasing) with respect to their former values, as we prove now. Proposition 2.1 Given any coboundary ∂h, the left-hand sides of Eq. (2.1)corresponding to the cocycles ψand ψ·∂hdiffer at most in 1, in absolute value. Proof Consider a cocycle ψ=ρk j=1∂ijand a coboundary ∂h.Fixedarowr,2≤r≤4t, Table 2shows the range in which the number crof r-paths and Irof r-intersections vary from ψto ψ∂hdepending on whether none, one or even both between the head and the tail of ∂hare (×) or not (◦) ends of a maximal path in ψas well. It is worth noting that the states of such head and tail necessarily change from ψto ψ∂h, as a straightforward consequence that these are precisely the 2 negative entries that ∂hcontributes with. Therefore, the left-hand sides of Eq. (2.1) corresponding to ψand ψ·∂hcan never differ more than 1, in absolute value, as claimed.  Table 2 Analyzing how (cr−Ir)varies from ψto ψ∂h ψ→ψ∂hcrIr(cr−Ir) {◦,◦} → {×,×} + 10,+1,+2−1,0,+1 {◦,×} → {×,◦} 0−1,0,+1−1,0,+1 {×,×} → {◦,◦} − 1−2,−1,0−1,0,+1 The following result, which is a straightforward consequence of Proposition 2.1, includes a natural formulation for a fitness function f2meeting the conditions we are expecting for. Corollary 2.2 A lower bound on the number of coboundaries needed to transform ψ=ρk j=1∂ijinto an orthogonal cocycle is f2(ψ) =max 2≤r≤4t(cr−Ir)−t−ρr 2.(2.2) Actually, as commented before, the space of 24tcocyclic matrices Mψmay be naturally displayed in terms of the vectors vψof their coordinates with regards to the set of elementary coboundaries {∂1,...,∂ 4t}. Attending to Corollary 2.2, vectors at Hamming distance 1 should have comparable fitness, as desired. Even more, it is worth stressing that f2helps to prune the search space in an impressive way, since it precisely gives a lower bound on the number of coboundaries to modify in the expression defining ψso that it can be moved to a cocyclic Hadamard matrix. This way, given ψ, we know that no cocyclic Hadamard matrix exists in a Hamming ratio of f2(ψ) −1fromψ. Conversely, a further application of this fact is to decide good zones for performing some local searches. We are now in conditions to design a new heuristic looking for cocyclic Hadamard matrices. 3 The Heuristic By construction, a cocyclic Hadamard matrix over Gcorresponds to a global minimum for f2. This section is devoted to design a heuristic trying to locate such a global minimum. As usual, the main problem to tackle is dealing with local minima. You can imagine the space of 24tcocyclic matrices Mψorganized by their fitness f2(ψ) as the surface of the sea. No matter the sea is in calm, the number of valleys and hills that the waves originate on its surface tends to be extremely huge. In these circumstances, it is quite easy to locate some local minima, but nevertheless it is extremely difficult to locate points corresponding to minimum height. This is the image we can think of in our minds for the search we are dealing with. Furthermore, the proportion of cocyclic Hadamard matrices with regards to the total space of cocyclic matrices seems to be negligible, as calculations in [2,4,8,10] suggest. A simple idea would be to perform a step by step search, moving from a given cocycle vψto some of its 4t neighbors vψat Hamming distance 1, so that f2(ψ)< f2(ψ). Unfortunately, it occurs surprisingly often that such a cocycle ψdoes not exist. In fact, from (2.2), a trivial upper bound for f2is 2t+max(0,ρr 2−t)24t, the latter being the total amount of cocyclic matrices. Consequently, there are many different cocyclic matrices meeting each of the possible values in the image of f2. And it is quite easy that, for any cocyclic matrix Mψrandomly chosen, none of its neighbors ψimproves the value f2(ψ) (in which case, ψis actually a local minimum for f2). For instance, taking ρand the dihedral group D4tas explained above, Table 3shows the number #iof local minima attaining fitness f2=i. A second approach would require to relax the condition considered so far for moving from one vertex to another, in such a way that f2(ψ)=f2(ψ) might suffice to move from ψto ψ. The question now is determining some subsidiary criteria to break the tie when no neighbor ψexists satisfying f2(ψ)< f2(ψ), but some do exist such Table 3 Number of local minima t\i0123 372 66 5 1400 9240 6416 1600 Table 4 D4t-cocyclic Hadamard matrices tIter Time (s) ij:ψ=ρk j=1∂ijis orthogonal 5 1 0.03 1, 3, 5, 8, 11, 18, 19 7 2 0.17 2, 4, 7, 10, 11, 12, 13, 14, 16, 17, 18, 20, 21, 22, 26, 27 9 4 0.65 2, 3, 4, 7, 9, 11, 12, 13, 14, 15, 16, 17, 20, 24, 25, 30, 31, 33, 36 11 116 31 4, 6, 8, 9, 12, 16, 18, 19, 21, 22, 23, 27, 32, 34, 35, 41, 42, 43 13 242 61 1, 9, 12, 13, 14, 16, 19, 20, 22, 23, 24, 25, 26, 29, 30, 33, 35, 40, 41, 42, 44 15 1374 852 3, 5, 7, 8, 9, 11, 13, 14, 17, 21, 22, 29, 31, 32, 34, 35, 37, 41, 42, 43, 44, 46, 47, 48, 50, 51, 57, 58 that equality holds. This would permit to avoid staying around a local minimum, and to facilitate moving to explore some other promising zones of the search space. As introduced in (2.2), f2(Mψ)gives the maximum from the differences (cr−Ir)−(t−ρr 2)along the 4t−1 rows in the range 2 ≤r≤4t. A way to fine tuning the search in order to break ties may be reached by associating to every cocycle ψa vector dψof length 1 +f2(Mψ)which counts the number of times that every integer instance in the range [0,f2(Mψ)]appears along these 4t−1 differences. In these circumstances, given two cocycles sharing the same fitness f2(Mψ)=f2(Mψ), one may assume that ψis better than ψif dψis lesser than dψin colexicographical order. That is dψ=(a1,...as)<(b1,...bt)=dψif and only if s<tor s=tand ai<bi for the last iwhere aiand bido differ. When a stationary point (i.e. a local minimum) is reached, in the sense that no neighbor exists at Hamming distance 1 which improves its fitness, then a random move is performed, to reach a new base point at certain prefixed Hamming distance s. This distance sshould simultaneously take us close enough to this “potentially” good zone around this local minimum, but at the same time far enough so that we seldom could reach the same stationary point more than once. Empirical results suggest that s=6 seems to meet these requirements. This value have been used in the calculations included in Table 4, which improve the results obtained by those heuristics [1,3]usingthe older and naive fitness notion, f1, looking for cocyclic Hadamard matrices over D4t. Notice that D4tseems to be the most prolific group for providing cocyclic matrices, see [10] and the references therein. However, the heuristic fails to give Hadamard matrices for t≥17 in reasonable time. Actually, the calculations we attempted for t=17 were aborted after 70.000 iterations and about 18 hours of computation each. Nevertheless, our determination held on. We turned to think for a local search which helped to improve the heuristic, so that larger matrices might be found. Undoubtedly, acocyclicHadamardmatrixismorelikelytobefoundaround multiple instancesofcoyclicmatrices Mψsatisfying f2(Mψ)=1. As a matter of fact, notice that the 4tneighbors ψof a cocycle ψdefining a cocyclic Hadamard matrix Mψsatisfy f2(ψ)≤1. Experimental results show that, as tincreases, it is not as hard as one could expect to find a cocycle ψsatisfying f2(ψ) =1. Actually, after 10 runs in each case, Table 5shows the average fitness fit of the randomly generated initial cocycle, the average number of iterations Iter as well as the average computing time Time required for reaching a cocycle ψover D4tsatisfying f2(ψ) =1, for odd values of t≤47. For this reason, every time that a cocycle ψmeeting f2(ψ)=1 is found, it makes sense to perform a local search, looking exhaustively for cocyclic matrices of fitness at most 1, in the ball B(ψ,s)determined by some fixed Hamming distance sfrom ψ. Hopefully, this process might lead to a path of sufficiently close cocycles ψ all of which meet fitness 1, until a cocyclic Hadamard matrix is finally found. Nevertheless, the number of matrices in such a ball B(ψ,s)grows exponentially on s,ass w=04t w. Depending on t, the computation capabilities which are available naturally limit the largest parameter sone might consider. Table 5 Analyzing the convergence to fitness 1 t15 17 19 21 23 25 27 29 31 Fit 4.2 4.3 4.4 5.2 5.5 5.4 6.6 5.7 6.9 Iter 1.2 1.4 1.3 2 2.1 3.8 6.1 4.8 9.5 Time (s) 0.46 0.75 0.96 1.98 2.59 7.35 14.78 14.07 33.79 t33 35 37 39 41 43 45 47 Fit 6.9 7.7 7.2 6.5 8.5 8 8.4 8.4 Iter 19.4 20.1 66 245 243.5 650.1 2072 3013.8 Time (s) 82 101 393 2094 2936 3905 20,703 34,621 Table 6 The size of B(ψ, s),for1≤s≤5 s12 3 4 5 |B(ψ, s)|189 17,767 1,107,603 51,512,518 1,906,413,390 For instance, for t=47, which is actually the first occurrence for which no cocyclic Hadamard matrix is known yet, the sizes of these balls grows as 25s+10, as Table 6shows. So that it could hardly be supported to perform a search for s≥5. Even the case s=4, which requires managing up to 5 ·107instances, might be unacceptable for practical purposes. That was the case, until unexpectedly the translation of the problem in terms of a Constraint Satisfaction Problem [7] (CSP in brief, hereafter), made it possible. Roughly speaking, the idea beyond the constraint satisfaction paradigm is characterizing a problem as a set of constraints to be simultaneously satisfied, and then find the set of solutions by means of a constraint solver. No matter the same solver is used, a given problem might possibly admit many different formulations as a CSP, each of them requiring possibly different amount of resources (not only variables and/or constraints, but also CPU memory) and consequently different running computation times in turn. An explicit formulation of a CSP looking for all cocycles ψ∈B(ψ, 4)such that f2(ψ)≤1 may be described as follows. We look for binary vectors vψ=(x0,...,x4t−1), which satisfy the conditions:  (t−j)−1 2 4t−1  i=0 σixi−x2ti 2t+(i+jmod 2t) ≤1,(3.1) for σi=1if0≤i≤2t−jor 2t≤i≤4t−jand −1 elsewhere, and 1 ≤j≤t−1. Once the model is fixed, the following step consists in carrying it into a solver. We have used Minion [9], one of the fastest and most scalable constraint solvers using the “model and run” methodology. It is a black box from the user point of view, deliberately providing few options, but guaranteeing raw speed in return. The vector vψ=(x0,...,x4t−1)is naturally codified as a boolean vector ingred of 4tunknowns. The t−1 relations (3.1) may be translated by means of a boolean matrix camenosin of size (t−1)×4t, such that camenosin[j−1,i]=|xi−x2ti 2t+(i+jmod 2t)|for 1 ≤j≤t−1. In these circumstances, it suffices to impose the constraints weightedsumleq([ 2t−(j−1)   1,...,1, j−1   −1,...,−1, 2t−(j−1)   1,...,1, j−1   −1,...,−1],camenosin[j,_],2(t−j)) weightedsumleq([ 2t−(j−1)   1,...,1, j−1   −1,...,−1, 2t−(j−1)   1,...,1, j−1   −1,...,−1],camenosin[j,_],2(t−2−j)) for 0 ≤j≤t−2. Table 7 Calculations for 19 ≤t≤23 tψ0kψkMinion (s) 17 e1c966 f450819e555 1, 12, 48, 68 61c966 f4500616550 32 41, 46, 47, 49 12, 53, 66 19 114bd7765e598c2e7c8 16, 31, 34, 68 114ad77c0edb8e8e648 67 29, 47, 55, 57 36, 41, 59, 69 21 1627dc8eadec977dc78d8 29, 35, 47, 71 54a79d960 f eed77c458d8 122 2, 7, 8, 18 8, 25, 28, 33 25, 39, 50, 64 9, 24, 65 23 95ee3e2bbb65ef2df84cfeb 19, 25, 28, 81 57e60ebbed643d2dfa667a8 219 2, 12, 13, 48 12, 17, 79, 92 17, 39,55, 75 7, 43, 49, 77 36, 40, 43, 83 7, 34, 52, 71 31, 38, 40, 83 7, 20, 86, 91 1, 31, 50 From these data a Minion file .min modeling our CSP may be then straightforwardly generated. Running over dihedral groups D4t,fort=47, the procedure takes barely 5 hours of computing time, on a standard Intel(R) Core(TM) i7-5500U CPU, 2.40 GHz, 8 GB RAM. In order to locate a cocyclic Hadamard matrix, both the heuristic and the local search just described may be combined as follows. Firstly, the heuristic is used until a cocycle ψ0is located such that f2(ψ0)=1. Starting from ψ0, a sequence of different cocycles {ψk}is constructed, such that ψk+1∈B(ψk,4)and f2(ψk+1)≤1. The process is repeated until either a no valid successor cocycle exists, or hopefully a truly orthogonal cocycle is found. As an illustration of how the method performs, we now include in Table 7some calculations which ultimately succeed locating a cocyclic Hadamard matrix over D4t,forsomet. We indicate the initial cocycle ψ0provided by the heuristic, the chain of subsets of (at most) 4 coboundaries which are changed to move from ψito ψi+1,the orthogonal cocycle ψkobtained as the tail of the chain, as well as the computational time required in every isolated call to Minion. Due to space restrictions, the 4t-binary tuples representing cocycles have been translated to their equivalent hexadecimal forms, in such a way that every possible nibble (group of 4 bits) from 0000 to 1111 is encoded as its corresponding hexadecimal digit from 0 to f, as usual. Further examples require an important amount of computational work and time, which is out of the scope of the paper. This effort should be straightforward directed to the case t=47. Notice that there is not any specific criteria to choose a particular cocycle ψi+1∈B(ψi,4)among those meeting fitness f2(ψ)=1. Nevertheless, there is not any guarantee that the process will end providing an orthogonal cocycle, either. Even more, there is not any certainty about the finiteness of such a sequence {ψi}. These questions should require further investigation.