This is the submitted version of the article: Fernández-Córdoba, Cristina; Vela, Carlos; Villanueva, Mercè. «Equivalences among Z2s -linear Hadamard codes». Discrete Mathematics, Vol. 343, issue 3 (March 2020), art. 111721. DOI 10.1016/j.disc.2019.111721 This version is available at https://ddd.uab.cat/record/239897 under the terms of the license Equivalences among Z2s -linear Hadamard codes Cristina Fernández-Córdoba, Carlos Vela, Mercè Villanueva Department of Information and Communications Engineering, Universitat Autònoma de Barcelona, 08193 Cerdanyola del Vallès, Spain. Abstract The Z2s -additive codes are subgroups of Zn2s , and can be seen as a gener- alization of linear codes over Z2 and Z4 . A Z2s -linear Hadamard code is a binary Hadamard code which is the Gray map image of a Z2s -additive code. A partial classification of these codes by using the dimension of the kernel is known. In this paper, we establish that some Z2s -linear Hadamard codes of length 2t are equivalent, once t is fixed. This allows us to improve the known upper bounds for the number of such nonequivalent codes. Moreover, up to t = 11, this new upper bound coincides with a known lower bound (based on the rank and dimension of the kernel). Finally, when we focus on s ∈ {2, 3}, the full classification of the Z2s -linear Hadamard codes of length 2t is established by giving the exact number of such codes. Keywords: Rank, Kernel, Hadamard code, Z2s -additive code, Gray map, classification 2000 MSC: 94B25, 94B60 1. Introduction 1 Let Z2s be the ring of integers modulo 2s with s ≥ 1. The set of n-tuples 2 over Z2s is denoted by Zn2s . A binary code of length n is a nonempty subset 3 of Zn2 , and it is linear if it is a subspace of Zn2 . A nonempty subset of Zn2s 4 is a Z2s -additive code if it is a subgroup of Zn2s . Note that, when s = 1, a 5 Z2s -additive code is a binary linear code and, when s = 2, it is a quaternary 6 linear code or a linear code over Z4 . 7 The Hamming weight of a binary vector u ∈ Zn2 , denoted by wtH (u), is 8 the number of nonzero coordinates of u. The Hamming distance of two binary 9 vectors u, v ∈ Zn2 , denoted by dH (u, v), is the number of coordinates in which 10 they differ. Note that dH (u, v) = wtH (v − u). The minimum distance of a Preprint submitted to Discrete Mathematics October 31, 2019 11 binary code C is d(C) = min{dH (u, v) : u, v ∈ C, u 6= v}. The Lee weight 12 of an element i ∈ Z2s is wtL (i) = min{i, 2s − Pi} and the Lee weight of a 13 vector u = (u1 , u2 , . . . , un ) ∈ Zn2s is wtL (u) = nj=1 wtL (uj ) ∈ Z2s . The Lee 14 distance of two vectors u, v ∈ Zn2s is dL (u, v) = wtL (v − u). The minimum 15 distance of a Z2s -additive code C is d(C) = min{dL (u, v) : u, v ∈ C, u 6= v}. In [12], a Gray map from Z4 to Z22 is defined as φ(0) = (0, 0), φ(1) = (0, 1), φ(2) = (1, 1) and φ(3) = (1, 0). There exist different generalizations of this s−1 Gray map, which go from Z2s to Z22 [5, 6, 13]. The one given in [5], by 2s−1 Carlet, is the map φs : Z2s → Z2 defined as follows: φs (u) = (us−1 , . . . , us−1 ) + (u0 , . . . , us−2 )Ys−1 , (1) 16 Ps−1 ui ∈ Z2s , [u0 , u1 , . . . , us−1 ]2 is the binary expansion of u, that where s−1 is u = 17 i=0 2 ui (ui ∈ {0, 1}), and Ys−1 is a matrix of size (s − 1) × 2 which 18 columns are the elements of Zs−1 2 . Note that the rows of Y s−1 form a basis of 19 a first order Reed-Muller code after adding the all-one row. The generalized s−1 20 Gray map from Z2s to Z22 given in [13], by Krotov, is defined in a more 21 general way in terms of the codewords of a Hadamard code. In this paper, we 22 will focus on Carlet’sPGray map φs , which P is a particular case of the Krotov’s 23 one satisfying that λi φs (2i ) = φs ( λi 2i ). Then, we define Φs : Zn2s → s−1 24 Zn2 2 as the component-wise Gray map φs . 25 Let C be a Z2s -additive code of length n. We say that its binary image 26 C = Φs (C) is a Z2s -linear code of length 2s−1 n. Since C is a subgroup of Zn2s , t 27 it is isomorphic to an abelian structure Zt21s × Zt22s−1 × · · · × Z4s−1 × Zt2s , and 28 we say that C, or equivalently C = Φs (C), is of type (n; t1 , . . . , ts ). Note that 29 |C| = 2st1 2(s−1)t2 · · · 2ts . If C is a Z2s -additive code of type (n; t1 , . . . , ts ), then 30 a generator matrix of C with minimum number of rows has exactly t1 +· · ·+ts n 31 Pr A 2-linear combination of the elements of B = {b1 , . . . , br } ⊆ Z2s is rows. 32 i=1 λi bi , for λi ∈ Z2 . We say that B is a 2-basis of C if the elements in 33 B are 2-linearly independent and any c ∈ C is a 2-linear combination of the 34 elements of B. 35 Let Sn be the symmetric group of permutations on the set {1, . . . , n}. Two 36 binary codes, C1 and C2 , are said to be equivalent if there is a vector a ∈ Zn2 37 and a permutation of coordinates π ∈ Sn such that C2 = {a + π(c) : c ∈ C1 }. 38 Two Z2s -additive codes, C1 and C2 , are said to be permutation equivalent 39 if they differ only by a permutation of coordinates, that is, if there is a 40 permutation of coordinates π ∈ Sn such that C2 = {π(c) : c ∈ C1 }. A binary 41 code C is transitive if for each x ∈ C there exists a permutation πx ∈ Sn 2 42 such that x + πx (C) = C. A binary code C is propelinear if it is transitive 43 and it satisfies that if x + πx (y) = z, then πz = πx πy . In [19], it is shown 44 that Z4 -linear codes are in fact propelinear codes. 45 Two structural properties of binary codes are the rank and the dimension 46 of the kernel. The rank of a binary code C is simply the dimension of 47 the linear span, hCi, of C. The kernel of a binary code C is defined as 48 K(C) = {x ∈ Zn2 : x + C = C} [2]. If the all-zero vector belongs to C, 49 then K(C) is a linear subcode of C. Note also that if C is linear, then 50 K(C) = C = hCi. We denote the rank of a binary code C as rank(C) 51 and the dimension of the kernel as ker(C). These invariants can be used to 52 distinguish between nonequivalent binary codes, since equivalent ones have 53 the same rank and dimension of the kernel. 54 A binary code of length n, 2n codewords and minimum distance n/2 is 55 called a Hadamard code. Hadamard codes can be constructed from Hadamard 56 matrices [1, 16]. Note that linear Hadamard codes are in fact first order 57 Reed-Muller codes, or equivalently, the dual of extended Hamming codes 58 [16, Ch.13 §3]. The Z2s -additive codes that, under the Gray map Φs , give 59 a Hadamard code are called Z2s -additive Hadamard codes and the corre- 60 sponding binary images are called Z2s -linear Hadamard codes. Note that 61 Z2s -additive Hadamard codes are the only regular proper Z2s -additive two- 62 weight homogeneous codes with dual Krotov distance at least 4 [21]. The 63 homogeneous weight of an element i ∈ Z2s , denoted by wt(i), is such that 64 wt(0) = 0, wt(2s−1 ) = 2s−1 and wt(i) = 2s−1 for all i ∈ Z2s \{0, 2s−1 }. 65 The Z4 -linear Hadamard codes of length 2t can be classified by using ei- 66 ther the rank or the dimension of the kernel [14, 18]. For s > 2, the dimension 67 of the kernel for Z2s -linear Hadamard codes of length 2t is established in [7], 68 and it is proved that this invariant only provides a complete classification for 69 certain values of t and s. Lower and upper bounds are also established for 70 the number of nonequivalent Z2s -linear Hadamard codes of length 2t , when 71 both t and s are fixed, and when just t is fixed; denoted by At,s and At , 72 respectively. The rank of these codes is computed in [8] only for s = 3, and 73 it is proved that in this case the rank is not enough to obtain a complete 74 classification. However, it is also shown that, for s = 3, by using both in- 75 variants, the rank and dimension of the kernel, it is possible to provide a full 76 classification for any t ≥ 3. Moreover, the exact value of At,3 is given. From 77 [7] and [8], we can check that there are nonlinear codes having the same rank 78 and dimension of the kernel for different values of s, once the length 2t is 79 fixed, for all 5 ≤ t ≤ 11. 3 80 In this paper, we show that there are Hadamard codes that can be seen 81 as Z2s -linear codes for different values of s, up to permutations. Moreover, 82 for t ≤ 11, we see that the codes that are permutation equivalent are, in 83 fact, those having the same pair of invariants, rank and dimension of the 84 kernel. These equivalence results allow us to obtain a more accurate clas- 85 sification of the Z2s -linear Hadamard codes, than the one given in [7]. The 86 paper is organised as follows. In Section 2, we recall the recursive con- 87 struction of the Z2s -linear Hadamard codes, the known partial classification, 88 and some bounds on the number of nonequivalent such codes, presented in 89 [7]. In Section 3, we prove some equivalence relations among the Z2s -linear 90 Hadamard codes of the same length 2t . Moreover, we prove that some Z2s - 91 linear Hadamard codes with s > 2 are also propelinear. Later, in Section 92 4, we improve the classification given in [7] by refining the known bounds. 93 Then, in Section 5, we show that the rank, together with the dimension of 94 the kernel, provide a full classification for the Z2s -linear Hadamard codes 95 of length 2t with s ∈ {2, 3}. In addition, in this case, we obtain the exact 96 number of nonequivalent such codes. Finally, in Section 6, we give some 97 conclusions and further research on this topic. 98 2. Partial classification 99 The description of a generator matrix having minimum number of rows 100 for a Z4 -additive Hadamard code, as long as a recursive construction of these 101 matrices, are given in [14]. In [13], the Z2s -additive Hadamard codes with 102 s > 2 are introduced and generator matrices with minimum number of rows 103 are given for these codes. In this section, we provide some results presented 104 in [7] and related to their recursive construction, partial classification and 105 bounds on the number of nonequivalent Z2s -linear Hadamard codes of length 106 2t . 107 Let Ti = {j · 2i−1 : j ∈ {0, 1, . . . , 2s−i+1 − 1}} for all i ∈ {1, . . . , s}. 108 Note that T1 = {0, . . . , 2s − 1}. Let t1 , t2 ,. . . ,ts be nonnegative integers 109 with t1 ≥ 1. Consider the matrix At1 ,...,ts whose columns are of the form 110 zT , z ∈ {1} × T1t1 −1 × T2t2 × · · · × Tsts . Let 0, 1, 2, . . . , 2s − 1 be the vectors 111 having the same element 0, 1, 2, . . . , 2s − 1 from Z2s in all its coordinates, 112 respectively. The order of a vector u over Z2s , denoted by ord(u), is the 113 smallest positive integer m such that mu = 0. Any matrix At1 ,...,ts can be obtained by applying the following recursive construction. We start with A1,0,...,0 = (1). Then, if we have a matrix 4 A = At1 ,...,ts , for any i ∈ {1, . . . , s}, we may construct the matrix   A A ··· A Ai = . (2) 0 · 2i−1 1 · 2i−1 · · · (2s−i+1 − 1) · 2i−1 0 0 114 Finally, permuting the rows of Ai , we obtain a matrix At1 ,...,ts , where t0j = tj 115 for j 6= i and t0i = ti + 1. Note that any permutation of columns of Ai gives 0 0 116 also a matrix At1 ,...,ts . Along this paper, we consider that the matrices At1 ,...,ts 117 are constructed recursively starting from A1,0,...,0 in the following way. First, 118 we add t1 − 1 rows of order 2s , up to obtain At1 ,0,...,0 ; then t2 rows of order 119 2s−1 up to generate At1 ,0,...,0 ; and so on, until we add ts rows of order 2 to 120 achieve At1 ,...,ts . See [7] for examples. 121 Let Ht1 ,...,ts be the Z2s -additive code generated by the matrix At1 ,...,ts , 122 wherePt1 , . . . , ts are nonnegative integers with t1 ≥ 1. Let n = 2t−s+1 , where 123 t = ( si=1 (s − i + 1) · ti ) − 1. The code Ht1 ,...,ts has length n, and the cor- 124 responding Z2s -linear code H t1 ,...,ts = Φ(Ht1 ,...,ts ) is a binary Hadamard code 125 of length 2t [7, 13]. In [7], it is shown that, in order to classify the Z2s -linear 126 Hadamard codes of length 2t , we can focus on t ≥ 5 and 2 ≤ s ≤ t − 2, since 127 in the rest of the cases there is exactly one code, which is linear. Moreover, 128 for any t ≥ 5 and 2 ≤ s ≤ t − 2, there are exactly two Z2s -linear Hadamard 129 codes of length 2t , H 1,0,...,0,t+1−s and H 1,0,...,0,1,t−1−s , which are linear. 130 Tables 1 and 3, for 5 ≤ t ≤ 11 and 2 ≤ s ≤ t − 2, show all possible 131 values (t1 , . . . , ts ) for which there exists a nonlinear Z2s -linear Hadamard 132 code H t1 ,...,ts of length 2t . For each one of them, the values (r, k) are shown, 133 where r is the rank (computed by using the computer algebra system Magma 134 [4, 20]) and k is the dimension of the kernel ([7, 14]). The rank for s = 2 135 and s = 3 can also be computed by using the results given in [18] and [8], 136 respectively. Note that if two codes have different values (r, k), then they 137 are not equivalent. Therefore, from the values of the dimension of the kernel 138 given in these tables, it is easy to see that this invariant does not classify. 139 From [8], we have that, considering only the rank, it is not possible to fully 140 classify these codes either. s 141 Let Xt,s be the number Ps of nonnegative integer solutions (t1 , . . . , ts ) ∈ N 142 of the equation t = ( i=1 (s − i + 1) · ti ) − 1 with t1 ≥ 1. Let At,s be the 143 number of nonequivalent Z2s -linear Hadamard codes of length 2t and a fixed 144 s ≥ 2. Then, for any t ≥ 5 and 2 ≤ s ≤ t − 2, we have that At,s ≤ Xt,s − 1, 145 since there are exactly two codes which are linear. Moreover, when t ≤ 11, 146 this bound is tight. It is still an open problem to know whether this bound 147 is tight for t ≥ 12. 5 t=5 t=6 t=7 t=8 (t1 , . . . , ts ) (r, k) (t1 , . . . , ts ) (r, k) (t1 , . . . , ts ) (r, k) (t1 , . . . , ts ) (r, k) (3, 0) (7,4) (3, 1) (8,5) (3, 2) (9,6) (3, 3) (10,7) Z4 (4, 0) (11,5) (4, 1) (12,6) (2, 0, 0) (8,3) (1, 2, 0) (8,5) (1, 2, 1) (9,6) (1, 2, 2) (10,7) (2, 0, 1) (9,4) (2, 0, 2) (10,5) (1, 3, 0) (12,6) Z8 (2, 1, 0) (12,4) (2, 0, 3) (11,6) (2, 1, 1) (13,5) (3, 0, 0) (17,4) (1, 1, 0, 0) (9,4) (1, 0, 2, 0) (9,6) (1, 0, 2, 1) (10,7) (1, 1, 0, 1) (10,5) (1, 1, 0, 2) (11,6) Z16 (2, 0, 0, 0) (14,3) (1, 1, 1, 0) (13,5) (2, 0, 0, 1) (15,4) (1, 0, 1, 0, 0) (10,5) (1, 0, 0, 2, 0) (10,7) Z32 (1, 0, 1, 0, 1) (11,6) (1, 1, 0, 0, 0) (15,4) Z64 (1, 0, 0, 1, 0, 0) (11,6) Table 1: Type, rank and dimension of the kernel for all nonlinear Z2s -linear Hadamard codes of length 2t for 5 ≤ t ≤ 8. 148 In [7], a partial classification for the Z2s -linear Hadamard codes of length t 149 2 is given. Specifically, lower and upper bounds on the number of nonequiv- 150 alent such codes, once only t is fixed, are established. The exact number of 151 nonequivalent codes of length 2t , for 3 ≤ t ≤ 7, which coincides with the 152 lower bound, is also established in [7]. These values are highlighted in bold 153 type in Table 2. Theorem 2.1. [7] Let At be the number of nonequivalent Z2s -linear Hadamard codes of length 2t with t ≥ 3. Then, t−2 X At ≤ 1 + (Xt,s − 2) (3) s=2 and t−2 X At ≤ 1 + (At,s − 1). (4) s=2 6 t 3 4 5 6 7 8 9 10 11 lower bound (r, k) 1 1 3 3 6 7 11 13 20 upper bound (3) and (4) 1 1 3 5 10 16 26 38 57 Table 2: Bounds for the number At of nonequivalent Z2s -linear Hadamard codes of length 2t for 3 ≤ t ≤ 11. 154 In this paper, in order to improve this partial classification, we analyse the 155 equivalence relations among the Z2s -linear Hadamard codes with the same 156 length 2t and different values of s. We prove that some of them are indeed 157 permutation equivalent. For 5 ≤ t ≤ 11, the ones that are permutation 158 equivalent coincide with the ones that have the same invariants, rank and 159 dimension of the kernel, that is, the same pair (r, k) in Tables 1 and 3. 160 Finally, by using this equivalence relations, we improve the upper bounds 161 on the number At of nonequivalent Z2s -linear Hadamard codes of length 2t 162 given by Theorem 2.1. This allow us to determine the exact value of At for 163 8 ≤ t ≤ 11, since one of the new upper bounds coincides with the lower 164 bound (r, k) for these cases. 7 t=9 t = 10 t = 11 (t1 , . . . , ts ) (r, k) (t1 , . . . , ts ) (r, k) (t1 , . . . , ts ) (r, k) (3, 4) (11,8) (3, 5) (12,9) (3, 6) (13,10) (4, 2) (13,7) (4, 3) (14,8) (4, 4) (15,9) Z4 (5, 0) (16,6) (5, 1) (17,7) (5, 2) (18,8) (6, 0) (22,7) (1, 2, 3) (11,8) (1, 2, 4) (12,9) (1, 2, 5) (13,10) (1, 3, 1) (13,7) (1, 3, 2) (14,8) (1, 3, 3) (15,9) (2, 0, 4) (12,7) (1, 4, 0) (17,7) (1, 4, 1) (18,8) (2, 1, 2) (14,6) (2, 0, 5) (13,8) (2, 0, 6) (14,9) (2, 2, 0) (17,5) (2, 1, 3) (15,7) (2, 1, 4) (16,8) Z8 (3, 0, 1) (18,5) (2, 2, 1) (18,6) (2, 2, 2) (19,7) (3, 0, 2) (19,6) (2, 3, 0) (23,6) (3, 1, 0) (24,5) (3, 0, 3) (20,7) (3, 1, 1) (25,6) (4, 0, 0) (32,5) (1, 0, 2, 2) (11,8) (1, 0, 2, 3) (12,9) (1, 0, 2, 4) (13,10) (1, 0, 3, 0) (13,7) (1, 0, 3, 1) (14,8) (1, 0, 3, 2) (15,9) (1, 2, 0, 0) (18,5) (1, 1, 0, 4) (13,8) (1, 0, 4, 0) (18,8) (1, 1, 0, 3) (12,7) (1, 1, 1, 2) (15,7) (1, 1, 0, 5) (14,9) (1, 1, 1, 1) (14,6) (1, 1, 2, 0) (18,6) (1, 1, 1, 3) (16,8) (2, 0, 0, 2) (16,5) (1, 2, 0, 1) (19,6) (1, 1, 2, 1) (19,7) Z16 (2, 0, 1, 0) (20,4) (2, 0, 0, 3) (17,6) (1, 2, 0, 2) (20,7) (2, 0, 1, 1) (21,5) (1, 2, 1, 0) (25,6) (2, 1, 0, 0) (28,4) (2, 0, 0, 4) (18,7) (2, 0, 1, 2) (22,6) (2, 0, 2, 0) (27,5) (2, 1, 0, 1) (29,5) (3, 0, 0, 0) (44,4) (1, 0, 0, 2, 1) (11,8) (1, 0, 0, 2, 2) (12,9) (1, 0, 0, 2, 3) (13,10) (1, 0, 1, 0, 2) (12,7) (1, 0, 0, 3, 0) (14,8) (1, 0, 0, 3, 1) (15,9) (1, 0, 1, 1, 0) (14,6) (1, 0, 1, 0, 3) (13,8) (1, 0, 1, 0, 4) (14,9) (1, 1, 0, 0, 1) (16,5) (1, 0, 1, 1, 1) (15,7) (1, 0, 1, 1, 2) (16,8) (2, 0, 0, 0, 0) (26,3) (1, 0, 2, 0, 0) (19,6) (1, 0, 1, 2, 0) (19,7) Z32 (1, 1, 0, 0, 2) (17,6) (1, 0, 2, 0, 1) (20,7) (1, 1, 0, 1, 0) (21,5) (1, 1, 0, 0, 3) (18,7) (2, 0, 0, 0, 1) (27,4) (1, 1, 0, 1, 1) (22,6) (1, 1, 1, 0, 0) (29,5) (2, 0, 0, 0, 2) (28,5) (2, 0, 0, 1, 0) (36,4) (1, 0, 0, 0, 2, 0) (11,8) (1, 0, 0, 0, 2, 1) (12,9) (1, 0, 0, 0, 2, 2) (13,10) (1, 0, 0, 1, 0, 1) (12,7) (1, 0, 0, 1, 0, 2) (13,8) (1, 0, 0, 0, 3, 0) (15,9) (1, 0, 1, 0, 0, 0) (16,5) (1, 0, 0, 1, 1, 0) (15,7) (1, 0, 0, 1, 0, 3) (14,9) (1, 0, 1, 0, 0, 1) (17,6) (1, 0, 0, 1, 1, 1) (16,8) Z64 (1, 1, 0, 0, 0, 0) (27,4) (1, 0, 0, 2, 0, 0) (20,7) (1, 0, 1, 0, 0, 2) (18,7) (1, 0, 1, 0, 1, 0) (22,6) (1, 1, 0, 0, 0, 1) (28,5) (2, 0, 0, 0, 0, 0) (48,3) (1, 0, 0, 0, 1, 0, 0) (12,7) (1, 0, 0, 0, 0, 2, 0) (12,9) (1, 0, 0, 0, 0, 2, 1) (13,10) (1, 0, 0, 0, 1, 0, 1) (13,8) (1, 0, 0, 0, 1, 0, 2) (14,9) Z128 (1, 0, 0, 1, 0, 0, 0) (17,6) (1, 0, 0, 0, 1, 1, 0) (16,8) (1, 0, 0, 1, 0, 0, 1) (18,7) (1, 0, 1, 0, 0, 0, 0) (28,5) (1, 0, 0, 0, 0, 1, 0, 0) (13,8) (1, 0, 0, 0, 0, 0, 2, 0) (13,10) Z256 (1, 0, 0, 0, 0, 1, 0, 1) (14,9) (1, 0, 0, 0, 1, 0, 0, 0) (18,7) Z512 (1, 0, 0, 0, 0, 0, 1, 0, 0) (14,9) Table 3: Type, rank and dimension of the kernel for all nonlinear Z2s -linear Hadamard codes of length 2t for 9 ≤ t ≤ 11. 8 165 3. Equivalent Z2s -linear Hadamard codes 166 In this section, we give some properties of the generalized Gray map Φs . 167 We also prove that some of the Z2s -linear Hadamard codes of the same length 168 2t , having different values of s are permutation equivalent. Moreover, we see 169 that they coincide with the ones having the same rank and dimension of the 170 kernel for 5 ≤ t ≤ 11. Lemma 3.1. [7] Let λi ∈ {0, 1}, i ∈ {0, . . . , s − 2}. Then, s−2 X s−2 X λi φs (2i ) = φs ( λi 2i ). i=0 i=0 Let γs ∈ S2s−1 be the permutation defined as   1 2 ... 2s−2 2s−2 + 1 2s−2 + 2 . . . 2s−1 . 1 3 . . . 2s−1 − 1 2 4 . . . 2s−1 For example, we have that γ3 = (2, 3) ∈ S4 and γ4 = (2, 3, 5)(4, 7, 6) ∈ S8 . Then, we can define the map τs : Z2s → Z22s−1 as τs (u) = Φ−1 −1 s−1 (γs (φs (u))), (5) 171 where u ∈ Z2s . Example 3.1. For s = 3, we have Φ3 (0) = (0, 0, 0, 0) = γ3 (0, 0, 0, 0) = γ3 (Φ2 (0, 0)) Φ3 (1) = (0, 1, 0, 1) = γ3 (0, 0, 1, 1) = γ3 (Φ2 (0, 2)) Φ3 (2) = (0, 0, 1, 1) = γ3 (0, 1, 0, 1) = γ3 (Φ2 (1, 1)) Φ3 (3) = (0, 1, 1, 0) = γ3 (0, 1, 1, 0) = γ3 (Φ2 (1, 3)) (6) Φ3 (4) = (1, 1, 1, 1) = γ3 (1, 1, 1, 1) = γ3 (Φ2 (2, 2)) Φ3 (5) = (1, 0, 1, 0) = γ3 (1, 1, 0, 0) = γ3 (Φ2 (2, 0)) Φ3 (6) = (1, 1, 0, 0) = γ3 (1, 0, 1, 0) = γ3 (Φ2 (3, 3)) Φ3 (7) = (1, 0, 0, 1) = γ3 (1, 0, 0, 1) = γ3 (Φ2 (3, 1)). 172 These equalities define the map τ3 : Z8 → Z24 as τ3 (0) = (0, 0), τ3 (1) = (0, 2), 173 τ3 (2) = (1, 1), τ3 (3) = (1, 3), τ3 (4) = (2, 2), τ3 (5) = (2, 0), τ3 (6) = (3, 3) and 174 τ3 (7) = (3, 1). 9 175 Lemma 3.2. Let s ≥ 2. Then, 176 (i) τs (1) = (0, 2s−2 ), 177 (ii) τs (2i u) = 2i−1 (u, u) for all i ∈ {1, . . . , s−1} and u ∈ {0, 1, . . . , 2s−1 −1}. 178 Proof. First, τs (1) = Φ−1 −1 −1 −1 s−1 (γs (φs (1))) = Φs−1 (γs (0, 1, 0, 1, . . . , 0, 1)) = 179 Φ−1 s−1 (0, 1) = (0, 2 s−2 ), and (i) holds. In order to prove (ii), let u ∈ Z2s and [u0 , . . . , us−1 ]2 be its binary expan- sion. The binary expansion of 2i u is [0, . . . , 0, u0 , . . . , us−i−1 ]2 and we have that φs (2i u) = (us−i−1 , . . . , us−i−1 ) + (0, . . . , 0, u0 , . . . , us−i−2 )Ys−1 . Recall that the matrix Ys−1 given in (1), related to the definition of φs , is a matrix of size (s − 1) × 2s−1 which columns are the elements of Zs−1 2 . Without loss of generality, we consider that Ys is the matrix obtained recursively from Y1 = (0 1) and   Ys−1 Ys−1 Ys = . (7) 0 1 It is easy to see that   0 1 γs−1 (Ys−1 ) = . (8) Ys−2 Ys−2 Then, we have that γs−1 (φs (2i u)) =   (2s−1 ) 0 1 = (us−i−1 , . . . , us−i−1 ) + (0, .(i) . ., 0, u0 , . . . , us−i−2 ) = Ys−2 Ys−2 s−1  = (us−i−1 , (2. . . ), us−i−1 ) + (0, (i−1) . . . , 0, u0 , . . . , us−i−2 ) Ys−2 Ys−2 = i−1 i−1 i−1 = (φs−1 (2 u), φs−1 (2 u)) = Φs−1 (2 (u, u)). 180 Therefore, τs (2i u) = Φ−1 −1 i s−1 (γs (φs (2 u))) = 2 i−1 (u, u), and (ii) holds.  Proposition 3.1. Let s ≥ 2 and λi ∈ {0, 1}, i ∈ {0, . . . , s − 1}. Then, Xs−1 Xs−1 φs ( λi 2i ) = γs (Φs−1 ( τs (λi 2i ))). (9) i=0 i=0 10 Proof. By Lemma 3.2, we know that for all i ∈ {1, . . . , s − 1}, τs (2i ) = (2 , 2i−1 ) and τs (1) = (0, 2s−2 ). Then, by Lemma 3.1, we have that i−1 s−1 X Xs−1 γs (Φs−1 ( τs (λi 2i ))) = γs ( Φs−1 (τs (λi 2i ))). i=0 i=0 Moreover, γs commutes with the addition. Therefore, by applying the defi- nition of the map τs given in (5), we obtain that s−1 X s−1 X s−1 X i i γs (Φs−1 ( τs (λi 2 ))) = γs (Φs−1 (τs (λi 2 ))) = φs (λi 2i ), i=0 i=0 i=0 Ps−1 181 which is equal to φs ( i=0 λi 2i ) by Lemma 3.1.  Corollary 3.1. Let s ≥ 2 and λi ∈ {0, 1}, i ∈ {0, . . . , s − 1}. Then, s−1 X s−1 X τs ( λi 2i ) = τs (λi 2i ). (10) i=0 i=0 Proof. By Proposition 3.1, we have that s−1 X Xs−1 φs ( λi 2i ) = γs (Φs−1 ( τs (λi 2i ))), i=0 i=0 and, therefore, s−1 X s−1 X Φ−1 −1 s−1 (γs (φs ( i λi 2 ))) = τs (λi 2i ), i=0 i=0 that is, τs ( s−1 P i Ps−1 i 182 i=0 λi 2 ) = i=0 τs (λi 2 ).  Now, we extend the permutation γs ∈ S2s−1 to a permutation γs ∈ S2s−1 n such that restricted to each set of 2s−1 coordinates {2s−1 i + 1, 2s−1 i + 2, . . . , 2s−1 (i + 1)}, i ∈ {0, . . . , n − 1}, acts as γs ∈ S2s−1 . Then, we component-wise −1 extend function τs defined in (5) to τs : Zn2s → Z2n 2s−1 and define τ̃s = ρ ◦ τs , where ρ ∈ S2n is defined as   1 2 ... i ... n n + 1 . . . n + i . . . 2n . 1 3 . . . 2i − 1 . . . 2n − 1 2 . . . 2i . . . 2n 11 If u = (u1 , u2 , . . . , un ) ∈ Zn2s and τs (ui ) = (u1i , u2i ) for all i ∈ {1, . . . , n}, then τs (u) = (u11 , u21 , u12 , u22 , . . . , u1n , u2n ) and τ̃s (u) = (u11 , . . . , u1n , u21 , . . . , u2n ). Note also that Φs (u) = γs (Φs−1 (ρ(τ̃s (u)))) 183 for all u ∈ Zn2s , since τ̃s (u) = ρ−1 (τs (u)) = ρ−1 (Φ−1 −1 s−1 (γs (Φs (u)))). (s) 184 Let wi be the ith row of At1 ,...,ts , 1 ≤ i ≤ t1 + · · · + ts . By construction, (s) (s) (s) 185 w1 = 1 and ord(wi ) ≤ ord(wj ) if i > j. Let σi be the integer such that (s) (s) 186 ord(wi ) = 2σi . Then, B t1 ,...,ts = {2pi wi : 1 ≤ i ≤ t1 + · · · + ts , 0 ≤ pi ≤ 187 σi − 1} is a 2-basis of Ht1 ,...,ts . Example 3.2. Let H2,1 and H1,1,0 be the Z4 -additive and Z8 -additive Hadamard codes, which are generated by   1 1 1 1 1 1 1 1   2,1 1,1,0 1 1 1 1 A =  0 1 2 3 0 1 2 3  , and A = , 0246 0 0 0 0 2 2 2 2 respectively. The corresponding 2-bases are (2) (2) (2) (2) (2) B 2,1 = {w1 , 2w1 , w2 , 2w2 , w3 } = {(1, 1, 1, 1, 1, 1, 1, 1), (2, 2, 2, 2, 2, 2, 2, 2), (0, 1, 2, 3, 0, 1, 2, 3), (0, 2, 0, 2, 0, 2, 0, 2), (0, 0, 0, 0, 2, 2, 2, 2)}, and (3) (3) (3) (3) (3) B 1,1,0 = {w1 , 2w1 , 4w1 , w2 , 2w2 } = {(1, 1, 1, 1), (2, 2, 2, 2), (4, 4, 4, 4), (0, 2, 4, 6), (0, 4, 0, 4)}. 188 Proposition 3.2. Let ts ≥ 1, and Ht1 ,...,ts and H1,t1 −1,t2 ,...,ts−1 ,ts −1 be the Z2s - 189 additive and Z2s+1 -additive Hadamard codes with generator matrices At1 ,...,ts (s) (s+1) 190 and A1,t1 −1,t2 ,...,ts−1 ,ts −1 , respectively. Let wi and wi be the ith row of 191 At1 ,...,ts and A1,t1 −1,t2 ,...,ts−1 ,ts −1 , respectively. Then, we have that (s+1) (s) 192 (i) τ̃s+1 (2pi wi ) = 2pi wi , for all i ∈ {2, . . . , t1 + · · · + ts − 1} and (s) 193 pi ∈ {0, . . . , σi − 1}, where ord(wi ) = 2σi ; (s+1) (s) 194 (ii) τ̃s+1 (2j+1 w1 ) = 2j w1 , for all j ∈ {0, . . . , s − 1}; (s+1) (s) 195 (iii) τ̃s+1 (w1 ) = wt1 +···+ts . 12 (s) Proof. Consider At1 ,...,ts with ts ≥ 1, and wi its ith row for i ∈ {1, . . . , t1 + · · · + ts }. Then, the matrix over Z2s+1  (s)  w1  2w(s)   2   . .   .  (s) 2wt1 +···+ts is, by definition, A1,t1 −1,t2 ,...,ts−1 ,ts . Moreover, by construction we have that  1,t −1,t ,...,t ,t −1 A1,t1 −1,t2 ,...,ts−1 ,ts −1  1,t1 −1,t2 ,...,ts−1 ,ts A 1 2 s−1 s A = . 0 2s (s+1) Therefore, if wi is the ith row of A1,t1 −1,t2 ,...,ts−1 ,ts −1 for i ∈ {2, . . . , t1 + (s+1) (s+1) (s) (s) t2 + · · · + ts − 1}, we have that (wi , wi ) = 2wi and ord(wi ) = (s+1) (s+1) (s+1) ord(wi ) = σi . Let vi be the vector over Z2s+1 such that wi = (s+1) (s) (s+1) (s+1) (s+1) 2vi and wi = (vi , vi ). Let (vi )j be the jth coordinate of (s+1) vi . By the definition of τ̃s+1 and Lemma 3.2, for pi ∈ {0, . . . , σi − 1}, we have that (s+1) (s+1) (s+1) τ̃s+1 (2pi wi ) = ρ−1 (τs+1 (2pi wi )) = ρ−1 (τs+1 (2pi +1 vi )) = (s+1) (s+1) (s+1) (s+1) = ρ−1 (2pi ((vi )1 , (vi )1 , . . . , (vi )n , (vi )n )) = (s+1) (s+1) (s) = 2pi (vi , vi ) = 2 p i wi , 196 and (i) holds. (s) (s+1) (s+1) (s) 197 Since w1 = (w1 , w1 ) = 1 and wt1 +···+ts = (0, 2s−1 ), then the 198 equalities in items (ii) and (iii) hold by the definition of τ̃s+1 and Lemma 199 3.2.  200 Note that, from the previous proposition, we have that τ̃s is a bijection 201 between the 2-bases, B t1 ,...,ts and B 1,t1 −1,...,ts−1 ,ts −1 . Example 3.3. Let H2,1 and H1,1,0 be the same codes considered in Example 3.2. The length of H1,1,0 is n = 4. Then, the extension of γ3 = (2, 3) ∈ S4 is γ3 = (2, 3)(6, 7)(10, 11)(14, 15) ∈ S16 , and   1 2 3 4 5 6 7 8 ρ= ∈ S8 . (11) 1 3 5 7 2 4 6 8 13 In this case, we have that Φ3 (1, 1, 1, 1) = γ3 (Φ2 (0, 2, 0, 2, 0, 2, 0, 2)) = γ3 (Φ2 (ρ(0, 0, 0, 0, 2, 2, 2, 2))) Φ3 (2, 2, 2, 2) = γ3 (Φ2 (1, 1, 1, 1, 1, 1, 1, 1)) = γ3 (Φ2 (ρ(1, 1, 1, 1, 1, 1, 1, 1))) Φ3 (4, 4, 4, 4) = γ3 (Φ2 (2, 2, 2, 2, 2, 2, 2, 2)) = γ3 (Φ2 (ρ(2, 2, 2, 2, 2, 2, 2, 2))) Φ3 (0, 2, 4, 6) = γ3 (Φ2 (0, 0, 1, 1, 2, 2, 3, 3)) = γ3 (Φ2 (ρ(0, 1, 2, 3, 0, 1, 2, 3))) Φ3 (0, 4, 0, 4) = γ3 (Φ2 (0, 0, 2, 2, 0, 0, 2, 2)) = γ3 (Φ2 (ρ(0, 2, 0, 2, 0, 2, 0, 2))). Since Φ3 (u) = γ3 (Φ2 (ρ(τ̃3 (u)))) for all u ∈ Z48 , the map τ̃3 sends the elements of the 2-basis B 1,1,0 into the elements of the 2-basis B 2,1 . That is, as it is shown in Proposition 3.2, (3) (2) τ̃3 (w1 ) = τ̃3 (1, 1, 1, 1) = (0, 0, 0, 0, 2, 2, 2, 2) = w3 (3) (2) τ̃3 (2w1 ) = τ̃3 (2, 2, 2, 2) = (1, 1, 1, 1, 1, 1, 1, 1) = w1 (3) (2) τ̃3 (4w1 ) = τ̃3 (4, 4, 4, 4) = (2, 2, 2, 2, 2, 2, 2, 2) = 2w1 (12) (3) (2) τ̃3 (w2 ) = τ̃3 (0, 2, 4, 6) = (0, 1, 2, 3, 0, 1, 2, 3) = w2 (3) (2) τ̃3 (2w2 ) = τ̃3 (0, 4, 0, 4) = (0, 2, 0, 2, 0, 2, 0, 2) = 2w2 , 202 so τ̃3 is a bijection between both 2-bases. 203 Lemma 3.3. Let Hs = Ht1 ,...,ts be a Z2s -additive code with ts ≥ 1, and 204 Hs+1 = H1,t1 −1,t2 ,...,ts−1 ,ts −1 be a Z2s+1 -additive Hadamard code. Then, Hs = 205 Φs (Hs ) is permutation equivalent to Hs+1 = Φs+1 (Hs+1 ). 206 Proof. Let t be the integer such that Hs and Hs+1 are of length 2t . Let (s) (s) (s+1) (s+1) 207 Bs = {v1 , . . . , vt+1 } and Bs+1 = {v1 , . . . , vt+1 } be the 2-basis of Hs 208 and Hs+1 , respectively. By Proposition 3.2, τ̃s+1 is a bijection between Bs 209 and Bs+1 . By the definition of τ̃s+1 and Corollary 3.1, we have that τ̃s+1 210 commutes with the addition, so τ̃s+1 (Hs+1 ) = Hs . 211 Let ρ∗ ∈ S2t be a permutation such that Φs (ρ(u)) = ρ∗ (Φs (u)) for all −1 212 u ∈ Hs . Since Hs = τ̃s+1 (Hs+1 ) = ρ−1 (Φ−1 s (γs+1 (Φs+1 (Hs+1 )))), we have −1 −1 213 that Φs (Hs ) = ρ∗ (γs+1 (Φs+1 (Hs+1 ))). Therefore, we obtain Hs = (γs+1 ◦ 214 ρ∗ )−1 (Hs+1 ), where γs+1 ◦ ρ∗ ∈ S2t .  215 The following theorem determines which Z2s0 -linear Hadamard codes are 216 equivalent to a given Z2s -linear Hadamard code H t1 ,...,ts . We denote by 0j the (s) 217 all-zero vector of length j. Let σ be the integer such that ord(w2 ) = 2s+1−σ . 218 Note that σ = 1 if and only if t1 ≥ 2. Moreover, since σ2 is the integer such (s) 219 that ord(w2 ) = 2σ2 , we have that σ = s + 1 − σ2 . 14 220 Theorem 3.1. Let H t1 ,...,ts be a Z2s -linear Hadamard code with ts ≥ 1. `−1 221 Then, H t1 ,...,ts is equivalent to the Z2s+` -linear Hadamard code H 1,0 ,t1 −1,t2 ,...,ts−1 ,ts −` , 222 for all ` ∈ {1, . . . , ts }. `−1 223 Proof. Consider H0 = Ht1 ,...,ts and H` = H1,0 ,t1 −1,t2 ,...,ts−1 ,ts −` for 224 ` ∈ {1, . . . , ts }. By Lemma 3.3, we have that Hi = Φ(Hi ) is permutation 225 equivalent to Hi+1 = Φ(Hi+1 ) for all i ∈ {0, . . . , ` − 1} and ` ∈ {1, . . . , ts }. 226 Therefore, we have that H0 and H` are permutation equivalent for all ` ∈ 227 {1, . . . , ts }.  Let t1 , t2 , . . . , ts be nonnegative integers with t1 ≥ 2. Let CH (t1 , . . . , ts ) = [H1 = H t1 ,...,ts , H2 , . . . , Hts +1] be the sequence of all Z2s0 -linear Hadamard Ps0 0 codes of length 2t , where t = i=1 (s − i + 1) · ti −1, that are permutation equivalent to H t1 ,...,ts by Theorem 3.1. We denote by CH (t1 , . . . , ts )[i] the ith code Hi in the sequence, for 1 ≤ i ≤ ts + 1. We consider that the order of the codes in CH (t1 , . . . , ts ) is the following: ( H t1 ,...,ts , if i = 1, CH (t1 , . . . , ts )[i] = 1,0i−2 ,t1 −1,t2 ,...,ts−1 ,ts −i+1 (13) H , otherwise. 228 We refer to CH (t1 , . . . , ts ) as the chain of equivalences of H t1 ,...,ts . Note that 229 if ts = 0, then CH (t1 , . . . , ts ) = [H t1 ,...,ts ]. Corollary 3.2. Let t1 , t2 , . . . , ts be nonnegative integers with t1 ≥ 2. Then, |CH (t1 , . . . , ts )| = ts + 1. 230 Example 3.4. The chain of equivalences of H 3,3 is the sequence CH (3, 3) = 231 [H 3,3 , H 1,2,2 , H 1,0,2,1 , H 1,0,0,2,0 ] and contains exactly t2 +1 = 4 codes. Note that 232 this sequence contains all the codes of length 28 having the pair (r, k) = (10, 7) 233 in Table 1. In the same table, we can see that there is only one code of length 234 27 having the pair (r, k) = (12, 4), named H 2,1,0 . The chain of equivalences 235 of this code is CH (2, 1, 0) = [H 2,1,0 ], which contains just this code, since 236 t3 + 1 = 1. 237 Proposition 3.3. Let t1 , t2 , . . . , ts be nonnegative integers with t1 ≥ 2. Then, 0 0 238 the Z2s0 -linear Hadamard code H t1 ,...,ts0 = CH (t1 , . . . , ts )[i], 1 ≤ i ≤ ts + 1, 239 satisfies 15 240 (i) s0 = s + i − 1, 241 (ii) σ 0 = i, 242 (iii) t0s0 = ts − i + 1, ( (t1 , . . . , ts ), if i = 1, 243 (iv) (t01 , . . . , t0s0 ) = i−2 (1, 0 , t1 − 1, t2 , . . . , ts−1 , ts − i + 1), otherwise. 244 Proof. Straightforward from Theorem 3.1 and the definition of the chain 245 of equivalences CH (t1 , . . . , ts ).  0 0 246 Note that the value of s0 is different for every code H t1 ,...,ts0 belonging to 247 the same chain of equivalences CH (t1 , . . . , ts ). 248 Corollary 3.3. Let t1 , t2 , . . . , ts be nonnegative integers with t1 ≥ 2. 0 0 249 (i) The Z2s0 -linear Hadamard code H t1 ,...,ts0 = CH (t1 , . . . , ts )[1] is the only 250 one in CH (t1 , . . . , ts ) with σ 0 = 1, that is, the only one with t01 ≥ 2. 0 0 251 (ii) The Z2s0 -linear Hadamard code H t1 ,...,ts0 = CH (t1 , . . . , ts )[ts + 1] is the 252 only one in CH (t1 , . . . , ts ) with t0s0 = 0. 253 Now, given any Z2s -linear Hadamard code H t1 ,...,ts , we determine the 254 chain of equivalences containing this code, as well as its position in the se- 255 quence. Therefore, note that indeed we prove that any code H t1 ,...,ts (with 256 t1 ≥ 1) belongs to an unique chain of equivalences CH (t01 , . . . , t0s0 ) with t01 ≥ 2. 257 Proposition 3.4. Let t1 , t2 , . . . , ts be nonnegative integers with t1 ≥ 1. The 258 Z2s -linear Hadamard code H t1 ,...,ts belongs to an unique chain of equivalences. 259 If t1 ≥ 2, then σ = 1 and H t1 ,...,ts = CH (t1 , . . . , ts )[1]. Otherwise, if t1 = 1, 260 then σ > 1 and H t1 ,...,ts = CH (t01 , . . . , t0s0 )[σ], where (t01 , . . . , t0s0 ) = (tσ + 261 1, tσ+1 , . . . , ts−1 , ts + σ − 1) and s0 = s − σ + 1. 262 Proof. If t1 ≥ 2, it is clear by the definition of chain of equivalences and 263 Corollary 3.3. If t1 = 1, then σ > 1. By Proposition 3.3, since H t1 ,...,ts = 264 CH (t01 , . . . , t0s0 )[σ], we have that (t1 , . . . , ts ) = (1, 0σ−2 , t01 − 1, t02 , . . . , t0s0 −1 , t0s0 − 265 σ + 1). Therefore, tσ = t01 − 1, tσ+1 = t02 , . . ., ts−1 = t0s0 −1 , ts = t0s0 − σ + 1, 266 and the result follows.  16 Corollary 3.4. Let H t1 ,...,ts be a Z2s -linear Hadamard code and CH (t01 , . . . , t0s0 ) the chain of equivalences such that H t1 ,...,ts = CH (t01 , . . . , t0s0 )[σ]. Then, |CH (t01 , . . . , t0s0 )| = ts + σ. 267 Proof. If t1 ≥ 2, then H t1 ,...,ts = CH (t1 , . . . , ts )[1] by Proposition 3.4. By 268 Corollary 3.2, |CH (t1 , . . . , ts )| = ts + 1 = ts + σ. Otherwise, if t1 = 1, then 269 H t1 ,...,ts = CH (tσ + 1, tσ+1 , . . . , ts−1 , ts + σ − 1)[σ] by Proposition 3.4. Finally, 270 |CH (tσ + 1, tσ+1 , . . . , ts−1 , ts + σ − 1)| = ts + σ − 1 + 1 = ts + σ by Corollary 271 3.2.  272 Example 3.5. The Z24 -linear Hadamard code H 1,0,2,1 has t1 = 1, σ = 3 273 and s = 4. By Proposition 3.4, since σ = 3 and s0 = s − σ + 1 = 2, this 274 code is placed in the third position of the chain of equivalences CH (t01 , t02 ), 275 where t01 = t3 + 1 = 2 + 1 = 3 and t02 = t4 + σ − 1 = 1 + 3 − 1 = 3. 276 Therefore, H 1,0,2,1 = CH (3, 3)[3]. By Corollary 3.4, CH (3, 3) contains exactly 277 t4 + σ = 1 + 3 = 4 codes, which are the ones described in Example 3.4. 278 If H t1 ,...,ts is a Z2s -linear Hadamard code of length 2t with t1 ≥ 2 and 279 ts = 0, then |CH (t1 , . . . , ts )| = 1 by Corollary 3.4. In this case, from Tables 1 0 0 280 and 3, we can see that H t1 ,...,ts is not equivalent to any other code H t1 ,...,ts0 of 281 the same length 2t , for t ≤ 11. We conjecture that this is true for any t ≥ 12. 282 The values of (t1 , . . . , ts ) for which the codes H t1 ,...,ts are not equivalent to 283 any other such code of the same length 2t , for t ≤ 11, can be found in Table 284 4. t=5 (3,0), (2,0,0) t=7 (4,0), (2,1,0), (2,0,0,0) t=8 (3,0,0) t=9 (5,0), (2,2,0), (2,0,1,0), (2,0,0,0,0) t = 10 (3,1,0), (2,1,0,0) t = 11 (6,0), (2,3,0), (4,0,0), (2,0,2,0), (3,0,0,0), (2,0,0,1,0), (2,0,0,0,0,0) Table 4: Type of all Z2s -linear Hadamard codes of length 2t with σ = 1 and ts = 0 for t ≤ 11. 285 From Tables 1 and 3, we can also see that the Z2s -linear Hadamard codes 286 of length 2t with t ≤ 11 having the same values (r, k) are the ones which are 287 equivalent by Theorem 3.1. We conjecture that this is true for any t ≥ 12. 17 288 Recall that all Z4 -linear codes are propelinear, so also transitive [19]. 289 Now, as a corollary of Proposition 3.4, we show under which conditions a Z2s - 290 linear Hadamard code with s > 2 is propelinear because it is permutation 291 equivalent to a Z4 -linear code. First, we give the following lemma that is 292 easily proven. 293 Lemma 3.4. Let C1 and C2 be permutation equivalent binary codes. If C1 294 is propelinear, then so it is C2 . 295 Corollary 3.5. Let t1 , t2 , . . . , ts be nonnegative integers with t1 ≥ 1 and 296 s ≥ 2. Then, H t1 ,...,ts is propelinear if either s = 2 or s > 2, t1 = 1 and 297 σ = s − 1. 298 Proof. By [19], we have that all Z4 -linear codes are propelinear. There- 299 fore, H t1 ,...,ts is propelinear if s = 2. 300 Assume s > 2, σ = s − 1 and t1 = 1. By Proposition 3.4, the code t1 ,...,ts 301 H = H 1,0,...,0,ts−1 ,ts is permutation equivalent to H ts−1 +1,ts +s−2 , which is 302 Z4 -linear and so propelinear. Then the statement follows by Lemma 3.4.  303 4. Improvement of the partial classification 304 In this section, we improve some results given in [7], on the classification 305 of the Z2s -linear Hadamard codes of length 2t , once t is fixed. More precisely, 306 we improve the upper bounds of At given by Theorem 2.1 and determine the 307 exact value of At for t ≤ 11 by using the equivalence results established in 308 Section 3. 309 Next, we prove two corollaries of Theorem 3.1, which allow us to improve 310 the known upper bounds for At . 311 Corollary 4.1. Let H t1 ,...,ts be a Z2s -linear Hadamard code. Then, H t1 ,...,ts is 312 equivalent to ts +σ Z2s0 -linear Hadamard codes for s0 ∈ {s+1−σ, . . . , s+ts }. 0 0 313 Among them, there is exactly one H t1 ,...,ts0 with t01 ≥ 2, and there is exactly 0 0 314 one H t1 ,...,ts0 with t0s0 = 0. 315 Proof. The code H t1 ,...,ts belongs to a chain of equivalences C, which can 316 be determined by Proposition 3.4. We have that H t1 ,...,ts is equivalent to any 317 code in C by Theorem 3.1, and the number of codes in C is ts +σ by Corollary 18 318 3.4. By Proposition 3.4, the first code in C has s0 = s−σ +1. By Proposition 0 0 319 3.3, the ith code H t1 ,...,ts0 = C[i] has s0 = s − σ + i for i ∈ {1, . . . , ts + σ}. 320 Therefore, s0 ∈ {s − σ + 1, . . . , s + ts }. Finally, by Corollary 3.3, C[1] is the 321 only code in C with t01 ≥ 2 and C[ts + σ] is the only code in C with t0s0 = 0. 322  323 From Corollary 4.1, in order to determine the number of nonequivalent 324 Z2s -linear Hadamard codes of length 2t , At , we just have to consider one code 325 out of the ts + σ codes that are equivalent. For example, we can consider the 326 one with t1 ≥ 2. 327 Corollary 4.2. Let H be a nonlinear Z2s -linear Hadamard code of length 328 2t . If s ∈ {b(t + 1)/2c + 1, . . . , t + 1}, then there is an equivalent Z2s0 -linear 329 Hadamard code of length 2t with s0 ∈ {2, . . . , b(t + 1)/2c}. 330 Proof. Let H t1 ,...,ts bePa Z2s -linear Hadamard code with s ∈ {b(t + 331 1)/2c + 1, . . . , t + 1}. Since si=1 (s + 1 − i)ti = t + 1, then t1 = 1 and we have 332 that σ > 1. Therefore, by Proposition 3.4, H t1 ,...,ts is permutation equivalent 333 to the Z2s−σ+1 -linear Hadamard code H = H tσ +1,tσ+1 ,...,ts−1 ,ts +σ−1 . 334 Now, we just need to see that s−σ+1 < P b(t+1)/2c. Since the length of H 335 is 2 , we have that t+1 = (s−σ+1)(tσ +1)+ s−σ+1 t i=2 (s−σ+2−i)tσ−1+i +σ−1. 336 Therefore, (s − σ + 1)(tσ + 1) ≤ t + 1 and s − σ + 1 ≤ (t + 1)/(tσ + 1). By 337 the definition of tσ , we know that tσ ≥ 1, so s − σ + 1 ≤ b(t + 1)/2c.  338 Note that we can focus on the Z2s -linear Hadamard codes of length 2t 339 with s ∈ {2, . . . , b(t + 1)/2c} by Corollary 4.2, and we can restrict ourselves 340 to the codes having t1 ≥ 2 by Corollary 4.1. With this on mind, in order 341 to classify all P such codes for a given t ≥ 3, we define X̃t,s = |{(t1 , . . . , ts ) ∈ 342 N : t + 1 = si=1 (s − i + 1)ti , t1 ≥ 2}| for s ∈ {3, . . . , b(t + 1)/2c} and s 343 X̃t,2 = |{(t1 , t2 ) ∈ N2 : t + 1 = 2t1 + t2 , t1 ≥ 3}|. Note that, in the definition 344 of X̃t,2 , we consider t1 ≥ 3 because the code is linear if t1 = 2 [14]. Theorem 4.1. Let At be the number of nonequivalent Z2s -linear Hadamard codes of length 2t with t ≥ 3. Then, b t+1 2 c X At ≤ 1 + X̃t,s (14) s=2 19 and b t+1 2 c X At ≤ 1 + (At,s − 1). (15) s=2 345 Moreover, for 3 ≤ t ≤ 11, the upper bound (14) is tight. 346 Proof. In [7], it is proven that the codes H 1,0,...,0,ts and H 1,0,...,0,1,ts , 347 with s > 2 and ts ≥ 0, are the only Z2s -linear Hadamard codes which 348 are linear. Note that they are not included in the definition of X̃t,s for 349 s ∈ {3, . . . , b(t + 1)/2c}. When s = 2, recall that the codes with t1 = 1 and 350 t1 = 2 are the ones which are linear [14]. Note that they are not included 351 in the definition of X̃t,2 either. Therefore, the new upper bounds (14) and 352 (15) follow by Corollaries 4.1 and 4.2, after adding 1 to take into account the 353 linear code. 354 In Table 5, for 3 ≤ t ≤ 11, these new upper bounds together with previous 355 bounds are shown. Note that the lower bound (r, k) coincides with the upper 356 bound (14) for t ≤ 11, so this upper bound is tight for t ≤ 11.  t 3 4 5 6 7 8 9 10 11 lower bound (r, k) 1 1 3 3 6 7 11 13 20 upper bound (14) 1 1 3 3 6 7 11 13 20 upper bound (15) 1 1 3 4 9 12 22 28 47 upper bound (3) and (4) 1 1 3 5 10 16 26 38 57 Table 5: Bounds for the number At of nonequivalent Z2s -linear Hadamard codes of length 2t for 3 ≤ t ≤ 11. 357 This last result improves the partial classification given in [7]. Actually, 358 by definition, we have that X̃t,s ≤ Xt,s − 2, so the upper bound (14) is clearly 359 better than (3). It is also clear that the upper bound (15) is better than (4) 360 since there are fewer addends. Therefore, both new upper bounds improve 361 the previous known upper bounds obtained in [7]. Recall that At,s = Xt,s − 1 362 for any 3 ≤ t ≤ 11 and 2 ≤ s ≤ t − 2. If this equation is also true for any 363 t ≥ 12, then upper bounds (3) and (4) coincide. Moreover, upper bound (14) 364 would always be better than (15) since X̃t,s ≤ Xt,s − 2 = At,s − 1. 365 5. Full classification of Z4 -linear and Z8 -linear Hadamard codes 366 A complete classification of Z4 -linear and Z8 -linear Hadamard codes is 367 given in [14] and [8], respectively. By the results in Section 3, we know that 20 368 there are nonlinear Hadamard codes which are equivalent to both, a Z4 -linear 369 and a Z8 -linear code. In this section, we establish the complete classification 370 for the Z2s -linear Hadamard codes of length 2t with s ∈ {2, 3}. We also 371 determine the number of nonequivalent such codes. 372 Theorem 5.1. Every Z4 -linear Hadamard code of length 2t is equivalent to 373 a Z8 -linear Hadamard code, except for the Z4 -linear Hadamard code H (t+1)/2,0 374 with t ≥ 5 odd. 375 Proof. First of all, for t ≤ 4, we know that all Z2s -linear Hadamard codes 376 are linear, so they are permutation equivalent to the binary linear Hadamard 377 code of length 2t . Recall that, for s = 2, we have that t = 2t1 + t2 − 1. 378 Then, if t is even, all the solutions for t = 2t1 + t2 − 1 satisfy that t2 ≥ 1. 379 Then, by using Theorem 3.1, we have that every Z4 -linear Hadamard code 380 H t1 ,t2 of length 2t is permutation equivalent to the Z8 -linear Hadamard code 381 H 1,t1 −1,t2 −1 . 382 If t is odd, then there exists one solution for t = 2t1 + t2 − 1 with t2 = 383 0, that is, when t1 = (t + 1)/2. For the rest of solutions with t2 ≥ 1, 384 again by using Theorem 3.1, we know that each Z4 -linear Hadamard code 385 is permutation equivalent to a Z8 -linear Hadamard code. Finally, we have 386 to show that the code H (t+1)/2,0 is not permutation equivalent to a Z8 -linear 387 Hadamard code. Suppose that there exists a Z8 -linear Hadamard code H t1 ,t2 ,t3 that is permutation equivalent to H (t+1)/2,0 . We know that both codes should have the same length and dimension of the kernel. Recall that ker(H (t+1)/2,0 ) = (t+1)/2+1 since t ≥ 5 [14]. We also have that ker(H t1 ,t2 ,t3 ) = t1 +t2 +t3 +σt1 , where σt1 = 1 if t1 ≥ 2 and σt1 = 2 if t1 = 1 [7]. On the one hand, if t1 = 1, then σt1 = 2 and, from the equations t + 1 = 3 + 2t2 + t3 and (t+1)/2+1 = 1+t2 +t3 +2, we obtain that t3 = −1 which is not possible. On the other hand, if t1 ≥ 2, then σt1 = 1 and we have the following equations: ) ( t+1 = 3t1 + 2t2 + t3 t3 = t1 t+1 ⇒ t + 1 − 4t1 . + 1 = t1 + t2 + t3 + 1 t2 = 2 2 These two codes should also have the same rank, so rank(H t1 ,(t+1−4t1 )/2,t1 ) = rank(H (t+1)/2,0 ). As proven in [18], we have that if t1 ≥ 1 and t2 ≥ 0, then   t1 ,t2 t1 − 1 rank(Φ(H )) = 2t1 + t2 + . 2 21 From [8], we also have that t41 t3 35t21 7t1 t2 2 rank(Φ(Ht1 ,t2 ,t3 )) = − 1 + + + (t1 + t1 + t2 + 1) + t3 + 1. 24 12 24 12 2 Then, after simplifying, we obtain that t31 − 26t21 + (6t + 65)t1 − 18t − 4 = 0. (16) 388 Note that the left-hand side of equation (16) is strictly positive for t1 ≥ 389 26, since we can rewrite it as t31 + (6t + 65)t1 > 26t21 + 18t + 4. For t1 ∈ 390 {3, 6, 8, 9, 10, 12, . . . , 25}, equation (16) has no integer solution for t. For 391 t1 = 1, it has solution t = 3, but recall that t ≥ 4. For t1 = 4, it has 392 solution t = 16, but in this case t2 = 1/2 6∈ Z. Finally, for t1 ∈ {2, 5, 7, 11}, 393 it has solutions t = 5, 17, 20, 23, respectively, but in all these cases, t2 < 0. 394 Therefore, the result holds.  395 We have shown that the classification of the Z2s -linear Hadamard codes 396 with s ∈ {2, 3} is complete. Specifically, there exists only one binary nonlin- 397 ear Hadamard code of length 2t that is Z4 -linear, but not Z8 -linear, when t 398 odd. When t is even, all the Z4 -linear Hadamard codes of length 2t are also 399 Z8 -linear. This means that to generate all the Z2s -linear Hadamard codes 400 with s ∈ {2, 3} of a fixed length 2t , it is enough to generate all the Z8 -linear 401 Hadamard codes, and add the code H (t+1)/2,0 if t is odd. Finally, in Theorem 402 5.2, we establish the number of nonequivalent Z2s -linear Hadamard codes 403 with s ∈ {2, 3}, once the length 2t if fixed. Theorem 5.2. Let At,{2,3} be the number of nonequivalent Z2s -linear Hadamard codes of length 2t with s ∈ {2, 3}. Then, ( 1 if t < 5 At,{2,3} = At,3 + (t mod 2) if t ≥ 5, where the number of nonequivalent Z8 -linear Hadamard codes of length 2t is b(t+1)/3cj jt + 1k X t + 1 − 3i k At,3 = + − 1. 3 i=1 2 404 Proof. The explicit expression for At,3 is proven in [8]. Then, the ex- 405 pression for At,{2,3} follows from Theorem 5.1  22 406 In Table 6, we can see the complete classification of the Z2s -linear Hadamard 407 codes with s ∈ {2, 3} for 7 ≤ t ≤ 9. In the second row, there are the codes 408 that are both Z4 -linear and Z8 -linear together with its pair (r, k). In the 409 first and third rows, there are the codes that are just Z4 -linear or Z8 -linear, 410 respectively. t=7 t=8 t=9 type (r, k) type (r, k) type (r, k) Z4 (4, 0) (11,5) (5, 0) (16,6) (3, 3) o (3, 4) o Z4 (10,7) (11,8) (3, 2) o (1, 2, 2) (1, 2, 3) (9,6) (1, 2, 1) (4, 1) o (4, 2) o Z8 (12,6) (13,7) (1, 3, 0) (1, 3, 1) (2, 0, 2) (10,5) (2, 0, 3) (11,6) (2, 0, 4) (12,7) (2, 1, 0) (12,4) (2, 1, 1) (13,5) (2, 1, 2) (14,6) Z8 (3, 0, 0) (17,4) (2, 2, 0) (17,5) (3, 0, 1) (18,5) Table 6: Type, rank and dimension of the kernel for all nonlinear Z4 -linear and Z8 -linear Hadamard codes of length 2t for 7 ≤ t ≤ 9. 411 6. Conclusions 412 The results presented in this paper allow us to improve the partial classifi- 413 cation on the number At of nonequivalent Z2s -linear Hadamard codes having 414 the same length 2t , given in [7]. Specifically, we establish that there are some 415 families of such codes which are equivalent. This result allows us to give new 416 upper bounds on At . Moreover, we show that one of them, (14), is tight for 417 any 3 ≤ t ≤ 11. Actually, for these cases, we notice that the full classification 418 is also given by considering the pairs of invariants, rank and dimension of 419 the kernel. A future research would be to establish whether this is also true 420 in general, that is for any t ≥ 12. 421 Recall that At,s is the number of nonequivalent Z2s -linear Hadamard 422 codes having the same value of s and the same length 2t . In general, by 423 definition, we have that At,s ≤ Xt,s − 1. From Tables 1 and 3, for 5 ≤ t ≤ 11 424 and 2 ≤ s ≤ t − 2, we know that At,s = Xt,s − 1, that is, the classification of 23 425 these codesPis given by the number of solutions (t1 , . . . , ts ) ∈ Ns of the equa- s 426 tion t = ( i=1 (s − i + 1) · ti ) − 1 with t1 ≥ 1. Moreover, At,s also coincides 427 with the exact number of different pairs of invariants, rank and dimension of 428 the kernel. It is an open problem to determine whether At,s = Xt,s − 1 for all 429 t ≥ 12. Note that when this equation holds, the upper bound (14) is better 430 than (15). 431 As we can see in Table 4, there are some Z2s -linear Hadamard codes of 432 length 2t which are not equivalent to any other such code with the same 433 length. For example, the codes H 4,0 , H 2,1,0 , and H 2,0,0,0 of length 27 are 434 just Z4 -linear, Z8 -linear, and Z16 -linear codes, respectively. In general, we 435 conjecture that the Z2s -linear Hadamard codes H t1 ,...,ts with t1 ≥ 2 (i.e. 436 σ = 1) and ts = 0 are not equivalent to any other Z2s0 -linear Hadamard code 437 of the same length. 438 When we focus on the Z2s -linear Hadamard codes of length 2t with s ∈ 439 {2, 3}, we are able to give a complete classification for any t ≥ 3, by using 440 the equivalence results given in Section 3 and the explicit formula for the 441 rank of the Z4 -linear and Z8 -linear Hadamard codes, computed in [14] and 442 [8], respectively. 443 There are Hadamard codes, called Z2 Z4 -linear Hadamard codes, which 444 came from the image of a generalized Gray map of subgroups of Zα2 × Zβ4 . 445 If α = 0, they correspond to Z4 -linear Hadamard codes. In [18], the classi- 446 fication of all Z2 Z4 -linear Hadamard codes of length 2t with α 6= 0 is given. 447 Moreover, in [15], it is proven that each one of these codes is equivalent to 448 a Z4 -linear Hadamard code, except for one, namely H̄t , when t is even. It 449 is known that H̄t has rank r = 1 + t + t/2 2 and dimension of the kernel 450 k = 1 + t/2 [18]. From this result and Tables 1 and 3, it is easy to check that 451 H̄t is not equivalent to any Z2s -linear Hadamard code of the same length 2t 452 for 4 ≤ t ≤ 11 even. Another further research could be to show that this is 453 also true for any t ≥ 12 even. 454 In [22], a more general family of Hadamard codes, constructed from the 455 image of the generalized Gray map of subgroups of Zαp 1 × Zαp22 × · · · × Zαpss 456 with p prime, are described. The techniques developed in [7, 8, 9] and in this 457 paper could also be applied to these codes in order to classify them. In [10], 458 the results on the kernel and its dimension of Z2s -linear Hadamard codes 459 given in [7] have been used to establish equivalent results for the family of 460 Z2s -linear simplex and MacDonald codes defined in [11]. 461 Finally, it is also worth to mention that we have found that some Z2s - 462 linear Hadamard codes with s > 2 are propelinear (so also transitive). It is 24 463 an open problem to determine whether there are other Z2s -linear Hadamard 464 codes that are propelinear (or transitive) and not equivalent to a Z4 -linear 465 Hadamard code. 466 7. Acknowledgements 467 The authors would like to thank the anonymous referees for their com- 468 ments, which enabled them to improve the paper. 469 This work has been partially supported by the Spanish MINECO under 470 Grant TIN2016-77918-P (AEI/FEDER, UE), and by the Catalan AGAUR 471 under Grant 2017SGR-00463. The material in this paper was presented in 472 part at the 16th International Workshop on Algebraic and Combinatorial 473 Coding Theory in Svetlogorsk (Kaliningrad region), Russia, 2018 [9]. 474 References 475 [1] Assmus, E. F., Key, J. D.: Designs and Their Codes. Cambridge Uni- 476 versity Press, Great Britain (1992). 477 [2] Bauer, H., Ganter, B., Hergert, F.: Algebraic techniques for nonlinear 478 codes. Combinatorica, 3, no. 1, pp. 21–33 (1983). 479 [3] Borges, J., Fernández-Córdoba, C., Pujol, J., Rifà, J., Villanueva, M.: 480 Z2 Z4 -linear codes: generator matrices and duality. Designs, Codes and 481 Cryptography, 54, no. 2, pp. 167–179 (2010). 482 [4] Bosma, W., Cannon, J. J., Fieker, C., Steel, A.: Hand- 483 book of Magma functions, Edition 2.22, 5669 pages (2016). 484 http://magma.maths.usyd.edu.au/magma/. 485 [5] Carlet, C.: Z2k -linear codes. IEEE Trans. Inf. Theory, 44, no. 4, pp. 486 1543–1547 (1998). 487 [6] Dougherty, S. T., Fernández-Córdoba, C.: Codes over Z2k , Gray map 488 and self-dual codes. Advances in Mathematics of Communications, 5, 489 no. 4, pp. 571–588 (2011). 490 [7] C. Fernández-Córdoba, C. Vela, and M. Villanueva, On Z2s -linear 491 Hadamard codes: kernel and partial classification. Designs, Codes and 492 Cryptography, 87, no. 2-3, pp. 417–435 (2019). 25 493 [8] C. Fernández-Córdoba, C. Vela, and M. Villanueva, “On Z8 -linear 494 Hadamard codes: rank and classification,” submitted to IEEE Trans. 495 Inf. Theory, (2018). 496 [9] Fernández-Córdoba, C., Vela, C., Villanueva, M.: On some equivalent 497 Z2s -linear Hadamard codes. Proc. of 16th International Workshop on 498 Algebraic and Combinatorial Coding Theory, Svetlogorsk (Kaliningrad 499 region), Russia, pp. 80–84 (2018). 500 [10] Fernández-Córdoba, C., Vela, C., Villanueva, M.: On the kernel of Z2s - 501 linear simplex and MacDonald codes, arXiv:1910.07911, (2019). 502 [11] Gupta, M. K., On some linear codes over Z2s . PhD. Thesis (1998). 503 [12] Hammons, A. R., Kumar, P. V., Calderbank, A. R., Sloane, N. J. A., 504 Solé, P.: The Z4 -linearity of Kerdock, Preparata, Goethals and related 505 codes. IEEE Trans. Inf. Theory, 40, no. 2, pp. 301–319 (1994). 506 [13] Krotov, D. S.: On Z2k -dual binary codes. IEEE Trans. Inf. Theory, 53, 507 no. 4, pp. 1532–1537 (2007). 508 [14] Krotov, D. S.: Z4 -linear Hadamard and extended perfect codes. Proc. 509 of International Workshop on Coding and Cryptography, ser. Electron. 510 Notes Discrete Math. 6, pp. 107–112 (2001). 511 [15] Krotov, D. S., Villanueva, M.: Classification of the Z2 Z4 -linear 512 Hadamard codes and their automorphism groups. IEEE Trans. Inf. The- 513 ory, 61, no. 2, pp. 887–894 (2015). 514 [16] MacWilliams, F. J., Sloane, N. J. A.: The Theory of Error-Correcting 515 Codes. Elsevier, Amsterdam (1977). 516 [17] Shi, M., Sepasdar, Z., Alahmadi, A., Solé, P.: On two-weight Z2k -codes. 517 Designs, Codes and Cryptography, 86, no. 6, pp. 1201–1209 (2018). 518 [18] Phelps, K. T., Rifà, J., Villanueva, M.: On the additive (Z4 -linear and 519 non-Z4 -linear) Hadamard codes: rank and kernel. IEEE Trans. Inf. The- 520 ory, 52, no. 1, pp. 316–319 (2006). 521 [19] Pujol, J., Rifà, J.: Translation invariant propelinear codes. IEEE Trans. 522 Inf. Theory, 43, pp. 590–598 (1997). 26 523 [20] Pujol, J., Villanueva, M.: Q-ary codes. A Magma package, ver- 524 sion 1.0. Universitat Autònoma de Barcelona, Barcelona (2017). 525 http://ccsg/uab.cat. 526 [21] Shi, M., Sepasdar, Z., Alahmadi, A., Solé, P.: On two-weight Z2k -codes. 527 Designs, Codes and Cryptography, 86, no. 6, pp. 1201–1209 (2018). 528 [22] Shi, M., Wu, R., Krotov, D. S.: On Zp Zpk -additive codes and their 529 duality. IEEE Trans. Inf. Theory, 65, no. 6, pp. 3841–3847 (2019). 27