This is the accepted version of the article: Fernández-Córdoba, Cristina; Vela, Carlos; Villanueva, Mercè. «On Z8-linear Hadamard codes : rank and classification». IEEE Transactions on Information Theory, Vol. 66, issue 2 (Feb. 2020), p. 970-982. DOI 10.1109/TIT.2019.2952599 This version is available at https://ddd.uab.cat/record/239908 under the terms of the license 1 On Z8-linear Hadamard codes: rank and classification Cristina Fernández-Córdoba, Carlos Vela and Mercè Villanueva Pn Abstract—The Z2s -additive codes are subgroups of Zn 2s , and is wtL (u) = j=1 wtL (uj ) ∈ Z2s . The Lee distance of two can be seen as a generalization of linear codes over Z2 and Z4 . vectors u, v ∈ Zn2s is dL (u, v) = wtL (v − u). The minimum A Z2s -linear Hadamard code is a binary Hadamard code which distance of a Z2s -additive code C is d(C) = min{dL (u, v) : is the Gray map image of a Z2s -additive code. It is known that either the rank or the dimension of the kernel can be used to u, v ∈ C, u 6= v}. give a complete classification for the Z4 -linear Hadamard codes. In [15], a Gray map from Z4 to Z22 is defined as φ(0) = However, when s > 2, the dimension of the kernel of Z2s - (0, 0), φ(1) = (0, 1), φ(2) = (1, 1) and φ(3) = (1, 0). There linear Hadamard codes of length 2t only provides a complete exist different generalizations of this Gray map, which go from classification for some values of t and s. In this paper, the rank s−1 Z2s to Z22 [6], [8], [9], [16]. The one given in [8] by Carlet of these codes is computed for s = 3. Moreover, it is proved that s−1 this invariant, along with the dimension of the kernel, provides is the map φ : Z2s → Z22 defined as follows: a complete classification, once t ≥ 3 is fixed. In this case, the number of nonequivalent such codes is also established. φ(u) = (us−1 , . . . , us−1 ) + (u0 , . . . , us−2 )Y, (1) Keywords Rank, Kernel, Hadamard code, Z2s -additive where u ∈ Z2s P , [u0 , u1 , . . . , us−1 ]2 is the binary expansion of code, Gray map, classification. s−1 u, that is u = i=0 2i ui (ui ∈ {0, 1}), and Y is a matrix of size (s − 1) × 2 s−1 which columns are the elements of Zs−1 2 . I. I NTRODUCTION Note that (us−1 , . . . , us−1 ) and (u0 , . . . , us−2 )Y are binary Let Z be the ring of integers modulo 2s with s ≥ 1. The 2s vectors of length 2s−1 , and that the rows of Y form a basis set of n-tuples over Z2s is denoted by Zn2s . In this paper, the of a first order Reed-Muller code after adding the all-one row. elements of Zn2s will also be called vectors over Z2s of length This generalization can be defined in terms of the elements of n. A binary code of length n is a nonempty subset of Zn2 , and a Hadamard code [16]. In this paper, we will focus on Carlet’s it is linear if it is a subspace of Zn2 . A nonempty subset of Zn2s Gray map φ, which is P a particular case of P the one presented s−1 s−1 is a Z2s -additive code if it is a subgroup of Zn2s . Note that, in [16] satisfying that i=0 λi φ(2i ) = φ( i=0 λi 2i ) (λi ∈ when s = 1, a Z2s -additive code is a binary linear code and, {0, 1}), as it was shown in [13] and will be recalled later. s−1 when s = 2, it is a quaternary linear code or a linear code Then, we define Φ : Zn2s → Zn2 2 as the component-wise over Z4 . Gray map φ. Let Sn be the symmetric group of permutations on the set Let C be a Z2s -additive code of length n. We say that its {1, . . . , n}. Two binary codes, C1 and C2 , are said to be binary image C = Φ(C) is a Z2s -linear code of length 2s−1 n. equivalent if there is a vector a ∈ Zn2 and a permutation of Since C is a subgroup of Zn2s , it is isomorphic to an abelian coordinates π ∈ Sn such that C2 = {a + π(c) : c ∈ C1 }. t structure Zt21s × Zt22s−1 × · · · × Z4s−1 × Zt2s , and we say that Two Z2s -additive codes, C1 and C2 , are said to be permutation C, or equivalently C = Φ(C), is of type (n; t1 , . . . , ts ). Note equivalent if they differ only by a permutation of coordinates, that |C| = 2st1 2(s−1)t2 · · · 2ts . Unlike linear codes over finite that is, if there is a permutation of coordinates π such that fields, linear codes over rings do not have a basis, but there C2 = {π(c) : c ∈ C1 }. exists a generator matrix for these codes. If C is a Z2s -additive The Hamming weight of a binary vector u ∈ Zn2 , denoted code of type (n; t1 , . . . , ts ), then a generator matrix of C with by wtH (u), is the number of nonzero coordinates of u. The minimum number of rows has exactly t1 + · · · + ts rows. Hamming distance of two binary vectors u, v ∈ Zn2 , denoted Two structural properties of binary codes are the rank and by dH (u, v), is the number of coordinates in which they differ. the dimension of the kernel. The rank of a binary code C Note that dH (u, v) = wtH (v − u). The minimum distance of is simply the dimension of the linear span, hCi, of C. The a binary code C is d(C) = min{dH (u, v) : u, v ∈ C, u 6= v}. kernel of a binary code C is defined as K(C) = {x ∈ Zn2 : The Lee weight of an element i ∈ Z2s is wtL (i) = min{i, 2s − x+C = C} [3]. If the all-zero vector belongs to C, then K(C) i} and the Lee weight of a vector u = (u1 , u2 , . . . , un ) ∈ Zn2s is a linear subcode of C. Note also that if C is linear, then Manuscript received Month day, year; revised Month day, year. K(C) = C = hCi. We denote the rank of a binary code C The authors are with the Department of Information and Com- as rank(C) and the dimension of the kernel as ker(C). These munications Engineering, Universitat Autònoma de Barcelona, 08193- parameters can be used to distinguish between nonequivalent Bellaterra, Spain (e-mail: cristina.fernandez@uab.cat; carlos.vela@uab.cat; merce.villanueva@uab.cat) binary codes, since equivalent ones have the same rank and This work was supported in part by the Spanish MINECO under Grants dimension of the kernel. TIN2016-77918-P (AEI/FEDER, UE) and MTM2015-69138-REDT, and by A binary code of length n, 2n codewords and minimum the Catalan AGAUR under Grant 2017SGR-00463. The material in this paper was presented in part at the 2nd IMA Conference distance n/2 is called a Hadamard code. Hadamard codes on Theoretical and Computational Discrete Mathematics [12]. can be constructed from Hadamard matrices [2], [19]. Note 2 that linear Hadamard codes are in fact first order Reed- II. R ECURSIVE C ONSTRUCTION OF Z2s -L INEAR Muller codes, or equivalently, the dual of extended Hamming H ADAMARD C ODES codes [19, Ch.13 §3]. The Z2s -additive codes that, under the The description of generator matrices having minimum Gray map Φ, give a Hadamard code are called Z2s -additive number of rows for Z4 -additive Hadamard codes, as long as Hadamard codes and the corresponding binary images are recursive constructions of these matrices, are given in [17]. In called Z2s -linear Hadamard codes. [13], [16], these results are generalized for any s > 2. In this section, we describe the recursive construction of the generator The Z4 -linear Hadamard codes of length 2t can be classified matrices of the Z2s -additive Hadamard codes, introduced in by using either the rank or the dimension of the kernel [17], [13]. [20]. Specifically, it is known that for a Z4 -linear Hadamard Let Ti = {j · 2i−1 : j ∈ {0, 1, . . . , 2s−i+1 − 1}} for all i ∈ code C of type (2t−1 ; t1 , t2 ), ker(C) = t1 + t2 + 1 if t1 > 2, {1, . . . , s}. Note that T1 = {0, . . . , 2s −1}. Let t1 , t2 ,. . . ,ts be and ker(C) = 2t1 + t2 if t1 = 1 or 2, where t2 = t + 1 − 2t1 . nonnegative integers with t1 ≥ 1. Consider the matrix At1 ,...,ts For any integer t ≥ 3 and each t1 ∈ {1, . . . , b(t+1)/2c}, there whose columns are of the form zT , z ∈ {1} × T1t1 −1 × T2t2 × is a unique (up to equivalence) Z4 -linear Hadamard code of · · · × Tsts . type (2t−1 ; t1 , t + 1 − 2t1 ), and all these codes are pairwise Example 2.1: For s = 3, for example, we have the following nonequivalent, except for t1 = 1 and t1 = 2, where the codes matrices: are equivalent to the linear Hadamard code [17]. Therefore, the     number of nonequivalent Z4 -linear Hadamard codes of length 11 1111 A1,0,1 = , A1,1,0 = , 2t is b t−1 04 0246 2 c for all t ≥ 3, and it is 1 for t = 1 and t = 2.   11111111 Linear codes over Zps , which are a generalization of Z2s - A2,0,0 = , 01234567 additive codes, were studied by Blake [4] and Shankar [21]   in 1975 and 1979, respectively. Nevertheless, the study of 1111 1111 codes over rings increased significantly after the publication A1,1,1 =  0 2 4 6 0 2 4 6  , of some good properties of linear codes over Z4 and the 0000 4444 definition of the Gray map [15]. After that, Z2s -additive codes   and their images under the Gray map are deeply studied, for 11111111 11111111 example, in [8], [14], and [22]. In [16], Krotov studied Z2s - A2,0,1 =  0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7  , linear Hadamard codes and their dual codes by using different 00000000 44444444 generalizations of the Gray map. Recently, in [1], considering A2,1,0 = Carlet’s generalization of the Gray map, two-weight Z2s -linear   codes are studied. Note that Z2s -linear Hadamard codes are 11111111 11111111 11111111 11111111 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 . in fact a particular case of these two-weight codes. 00000000 22222222 44444444 66666666 In [13], the dimension of the kernel of Z2s -linear Hadamard Let 0, 1, 2, . . . , 2s − 1 be the vectors having the elements codes is given. It is shown that the kernel do not classify 0, 1, 2, . . . , 2s − 1 from Z2s repeated in each coordinate, these codes, since there are nonequivalent codes having the respectively. The order of a vector u over Z2s , denoted by same dimension of the kernel. As a consequence, a partial ord(u), is the smallest positive integer m such that mu = 0. classification for these codes is established. In this paper, in Any matrix At1 ,...,ts can be obtained by applying the follow- order to classify the Z8 -linear Hadamard codes of length 2t , ing recursive construction. We start with A1,0,...,0 = (1). Then, for any t ≥ 3, we compute the rank of these codes. Moreover, if we have a matrix A = At1 ,...,ts , for any i ∈ {1, . . . , s}, we we prove that this invariant, along with the dimension of the may construct the matrix kernel, provides a complete classification, once we fix t ≥ 3.   Note that, unlike for s = 2, in the case s = 3, it is necessary A A ··· A Ai = . to use both invariants. 0 · 2i−1 1 · 2i−1 · · · (2s−i+1 − 1) · 2i−1 (2) 0 0 Finally, permuting the rows of Ai , we obtain a matrix At1 ,...,ts , This correspondence is organized as follows. In Section where t0j = tj for j 6= i and t0i = ti + 1. Note that any II, we describe the recursive construction of the Z2s -linear 0 0 Hadamard codes of type (n; t1 , . . . , ts ), introduced in [13]. permutation of columns of Ai gives also a matrix At1 ,...,ts . 1,0,0 In Section III, we give some known results and prove new Example 2.2: From the matrix A = (1), we obtain the ones related to the Carlet’s generalized Gray map. In Section matrix A2,0,0 ; and from A2,0,0 we can construct A2,0,1 , where IV, we compute the rank of the Z8 -linear Hadamard codes in A2,0,0 and A2,0,1 are the matrices given in Example 2.1. Note terms of the parameters t1 , t2 and t3 , by finding a set of linear that we can also generate another matrix A2,0,1 as follows: independent vectors of the span. In Section V, we show that, from A1,0,0 = (1) we obtain the matrix A1,0,1 given in for s = 3, a complete classification can be given by using Example 2.1, and from A1,0,1 we can construct the matrix both invariants: the rank and dimension of the kernel. Finally,   1111111111111111 in Section VI, we give some conclusions and further research A1 =  0 4 0 4 0 4 0 4 0 4 0 4 0 4 0 4  . on this topic. 0011223344556677 3 Then, after permuting the rows of A1 , we have the matrix [v0 , v1 , . . . , vs−1 ]2 be the binary expansions of u and v,  1111111111111111  respectively. The operation “ ” on Z2s is defined as u v = P s−1 i A2,0,1 =  0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7  , i=0 2 ui vi . Note that the binary expansion of u v is 0404040404040404 [u0 v0 , u1 v1 , . . . , us−1 vs−1 ]2 . Proposition 3.1: [22] Let u, v ∈ Z2s . Then, φ(u) + φ(v) = which is different to the matrix A2,0,1 of Example 2.1. These φ(u + v − 2(u v)). two matrices A2,0,1 generate permutation equivalent codes. Corollary 3.1: [8], [22] Let u ∈ Z2s . Then, φ(u) + Along this paper, we consider that the matrices At1 ,t2 ,...,ts φ(2s−1 ) = φ(u + 2s−1 ). are constructed recursively starting from A1,0,...,0 in the fol- Lemma 3.1: [13] Let u ∈ {2s−2 , . . . , 2s−1 − 1} ∪ {3 · lowing way. First, we add t1 − 1 rows of order 2s , up to 2 , . . . , 2s − 1} ⊂ Z2s . Then, φ(u) + φ(2s−2 ) = φ(u + s−2 obtain At1 ,0,...,0 ; then t2 rows of order 2s−1 up to generate 2s−2 + 2s−1 ). At1 ,t2 ,0,...,0 ; and so on, until we add ts rows of order 2 to Proposition 3.2: [8] Let u, v ∈ Z2s . Then, achieve At1 ,t2 ,...,ts . dH (φ(u), φ(v)) = wtH (φ(u − v)). Let Ht1 ,...,ts be the Z2s -additive code generated by the Corollary 3.2: [13] Let u, v ∈ Z2s . Then, dH (φ(u), φ(v + matrix At1 ,...,ts , where Ps t1 , . . . , ts ≥ 0 with t1 ≥ 1. Let n = 2s−1 )) + dH (φ(u), φ(v)) = 2s−1 . 2t−s+1 , where t = ( i=1 (s − i + 1) · ti )−1. It is easy to see All the remaining results, given in this section, are only that Ht1 ,...,ts is of length n and has |Ht1 ,...,ts | = 2s n = 2t+1 proved for s = 3, that is, for Z8 -linear Hadamard codes. In codewords. Note that this code is of type (n; t1 , t2 , . . . , ts ). this case, the generalized Gray map φ : Z8 → Z42 is defined Let H t1 ,...,ts = Φ(Ht1 ,...,ts ) be the corresponding Z2s -linear by code. φ(0) = (0, 0, 0, 0) φ(4) = (1, 1, 1, 1) Theorem 2.1: [16] [13] Let t1 , . . . , ts be nonnegative in- φ(1) = (0, 1, 0, 1) φ(5) = (1, 0, 1, 0) tegers with t1 ≥ 1. The Z2s -linear code H t1 ,...,ts of type φ(2) = (0, 0, 1, 1) φ(6) = (1, 1, 0, 0) (n; t1P, t2 , . . . , ts ) is a binary Hadamard code of length 2t , with φ(3) = (0, 1, 1, 0) φ(7) = (1, 0, 0, 1). s t = ( i=1 (s − i + 1) · ti ) − 1 and n = 2t−s+1 . Let G be a generator matrix of a Z2s -additive code C of Lemma 3.2: Let q be a positive integer and  [q0 , q1 , q2 , . . .]2 length n. Then, (G · · · G) is a generator matrix of the r-fold its binary expansion. Then, q−1 3 + q 0 q−1 2 + (q0 + q1 )(q − replication code of C, (C, . . . , C) = {(c, . . . , c) : c ∈ C}, of 1) + q0 (q0 + q1 ) ≡ 1 mod 2. length r · n. Proof. If q ≡ 0 mod 4, then q0 = q1 = 0 and q−1  ≡ Let Ht1 ,t2 ,t3 be a Z8 -additive Hadamard code, which is 3 1 mod 2 since (q − 2)/2, q − 1 and q − 3 are odd numbers. generated by At1 ,t2 ,t3 . Let wi be the ith row of At1 ,t2 ,t3 , if q ≡ 1 mod 4, then q0 = 1, q1 = 0 and q−1  Similarly, + 1 ≤ i ≤ t1 . If t2 = t3 = 0, we also denote wi by wit1 . Note q−1  3 +(q −1)+1 ≡ 0+0+0+1 ≡ 1 mod 2. If q ≡ 2 mod 4, that wit1 ∈ Ht1 ,0,0 is the 8t1 −` -fold replication of wi` ∈ H`,0,0 2 then q0 = 0, q1 = 1 and q−1  + (q − 1) ≡ 0 + 1 ≡ 1 mod  2. for all 1 ≤ ` ≤ t1 and i ≤ `. 3 q−1 Remark 2.1: Let Ht1 ,0,0 be a Z8 -additive Hadamard code q−1  if q ≡ 3 mod 4, then q1 = 1, q1 = 1 and 3 + Finally, of type (n; t1 , 0, 0). Let 2 ≡ 0 + 1 ≡ 1 mod 2.    Lemma 3.3: Let q be a positive integer and [q0 , q1 , q2 , . . .]2 wi1 its binary expansion. Then, W =  ...  ,   (i) q − 4≡ q0 mod 2, wiq (ii) q−42 ≡ q1 mod 2, (iii) q−32  ≡ q0 + q1 mod 2, where 2 ≤ i1 < · · · < iq ≤ t1 . By construction, we have that q−2 t1 −1 (iv) 3 ≡ q0 (q0 + q1 ) mod 2. each one of the 8q elements of Zq8 appears 8 8q = 8t1 −q−1 times as a column of W . Therefore, there exist a permutation Proof. These congruences can be proved easily consider- of coordinates ρ ∈ Sn such that ing the different values of q modulo 4, as in the proof of  w2  Lemma 3.2.  t1 ,0,0 .. Lemma 3.4: Let H be a Z8 -additive Hadamard code ρ(W ) =  .   . of type (n; t1 , 0, 0). Let E ⊆ {1, . . . , t1 }, q = |E| and wq+1 [q0 , q1 , q2 , . . .]2 the binary expansion of q. Let wi be the ith Note also that wi is the 8t1 −q−1 -fold replication of wiq+1 for row of At1 ,0,0 , i ∈ E. Then, all 2 ≤ i ≤ q + 1. X X Φ( wi ) = Φ(wi + wj + wk + wp ) i∈E i,j,k,p∈E III. P ROPERTIES OF THE G ENERALIZED G RAY M AP i 0, rd ∈ {1, 2, 3} and r1 + r2 + rd > 3 4, then we may consider that sq = sq−1 = sq−2 = sq−3 = wi . which also gives that r∗ > 0. Note that the right-hand side of the equation of the statement In order∗ to verify the statement, we consider Pq−r can be easily rewritten by replacing q by q − 4 and adding π̃8 (Φ( i=1 sid−1 )) under different cases depending on Φ(4wj ). Moreover, Pq−4by Corollary 3.1, the left-hand side of the the value of r2 ∈ {1, 2, 3}. First, consider that r2 = 1, i.e., equation is Φ( i=1 si )+Φ(4wj ). Therefore, we may assume s1 = w2 and si 6= w2 for all i ∈ {2, 3, . . . , q}. Then, by using that ri ≤ 3 for all i ∈ {1, . . . , t1 }. the same arguments as in the proof of Lemma 3.4, we have Let W be the set containing the elements of S without that the result holds. Next, consider that r2 = 2. By induction repetition. On the one hand, if w1 6∈ S, taking into account hypothesis, taking into account that (q − 2)0 ≡ q0 mod 2 and the multiplicity of each element in W and Remark 2.1, we (q − 2)1 ≡ q1 + 1 mod 2, and using again the properties of may assume that W = {w2 , . . . , wd }, where r2 ≤ · · · ≤ rd π8 and the fact that Φ ◦ π8 = π̃8 ◦ Φ, we have that and s1 = · · · = sr2 = w2 , . . . , sq−rd +1 = · · · = sq = wd . On the other hand, if w1 ∈ S, we assume that q > r1 + r2 . q−2 X Otherwise, if q = r1 + r2 , since q ≥ 6 and r1 , r2 ≤ 3, then Φ(w2d + w2d + sqi + 1 + 1) = we have to show that the statement is true for Φ(w2 + w2 + i=3 X w2 + w1 + w1 + w1 ), which can be checked easily. Since Φ(sdi + sdj + sdk + sdp )+ q > r1 + r2 , we can order all elements s1 , . . . , sq as above, 3≤i 0, we can apply the induction hypothesis to Φ(w2d + w2d + sdi + 1 + 1) = Φ(sdi )+ Q8t1 −2 −1 3≤i≤q−2 3≤i≤q−2 obtain the result. Otherwise, let π8 = i=0 (8i + 1, 8i + X X 2, 8i + 3, 8i + 4, 8i + 5, 8i + 6, 8i + 7, 8i + 8) ∈ Sn be Φ(w2d + w2d + sdi ) + Φ(sdi + 1 + 1)+ a permutation of coordinates. Note that π8 (w2 ) = w2 + 1 3≤i≤q−2 3≤i≤q−2 and π8 (wj ) = wj for all j ∈ {3, . . . , d}. Let π̃8 ∈ S4n h i (q − 4) Φ(w2d + w2d + 1 + 1) + Φ(w2d + w2d ) + Φ(1 + 1) be a permutationPr2 such P◦q−(r that Φ π8 = π̃8 ◦ Φ. Therefore, we 1 +rd ) d−1 (7) have that Φ( i=1 w2d−1 + i=r2 +1 si + (r̄ − r2 )1 + Pr2 d−1 P q−(r1 +rd ) d−1 r2 1) = Φ(π8 ( i=1 w2 + i=r2 +1 si + (r̄ − r2 )1)) = and P r2 Pq−(r1 +rd ) d−1 π̃8 (Φ( i=1 w2d−1 + i=r2 +1 si + (r̄ − r2 )1)). Note that r̄ ≥ r1 + rd ≥ rd ≥ r2 . Then, considering sd−1 X i = w1 for all Φ(w2d + w2d + sdi + sdj + 1 + 1) = i ∈ {q−(r1 +rd )+1, . . . , q−(r1 +rd )+(r̄−r2 )} 2 ≥ 1, Pifr2r̄−rd−1 3≤i 0. First, note 3≤i 0; and if r̄ = 3, k · rd = 3 mod 4 which implies that rd = 3 and r∗ > 0. On By replacing (7) and (8) into expression (6), and using items 6 (i) and (ii) of Lemma 3.3, we have that (6) is equal to wj + 1) + Φ(−2(2wi (wj + 1))) for all i, j ∈ {2, 3}, so X A1 = Φ(2w23 + w33 + 1) + Φ(w23 + 2w33 + 1)+ Φ(sdi + sdj + sdk + sdp )+ 3≤i 2, and 2t1 + t2 if t1 = 1 or 2 [20]. In this section, Pq+1 8t1 −q−2 -fold replication of y. Then, i=2 wi is the 8t1 −q−1 - we establish the rank of a Z8 -linear Hadamard code of type fold replication of (y + 0, y + 1, . . . , y + 7). The result holds (2t−2 ; t1 , t2 , t3 ), where t + 1 = 3t1 + 2t2 + t3 , in terms of the if parameters t1 , t2 and t3 by finding a set of linear independent q X vectors that generate the span of the code. µ( wi + wq+1 ) = Proposition 4.1: Let t1 , t2 , . . . , ts be nonnegative integers i=2 with t1 ≥ 1. q+1 X X Then, rank(Φ(Ht1 ,...,ts )) = ts + rank(Φ(Ht1 ,...,ts−1 ,0 )). µ(wi + wj ) + (q mod 2) µ(wi ). 2≤i 2, the dimension of the kernel is t1 + 2k − 2σt1 − t − 1 + 1, not enough to establish a complete classification of the Z2s - linear Hadamard codes of length 2t , for any t ≥ 3. In this section, we show that for s = 3, a complete classification can which is equal to be given by using both invariants: the dimension of the kernel and the rank, computed in [13] and in the previous section, t41 13 71 1 respectively. − t3 + ( + (t − k + σt1 ))t21 − rank(t1 , t, k) = 24 12 1 24 2 First, recall that the dimension of the kernel for Z8 -linear 11 3 1 Hadamard codes is given by the following result: −( + (t−k+σt1 ))t1 + ((t−k+σt1 )2 +t+k−σt1 +2). 12 2 2 Proposition 5.1: [13] Let H = Ht1 ,t2 ,t3 be a Z8 -additive Hadamard code. If Φ(H) is nonlinear, then ker(Φ(H)) = t1 + 0 0 0 t2 + t3 + σt1 , where σt1 = 1 if t1 ≥ 2 and σt1 = 2 if t1 = 1. Now, we suppose that rank(H t1 ,t2 ,t3 ) = rank(H t1 ,t2 ,t3 ) for In [13], it is also shown that, in order to obtain a com- (n; t1 , t2 , t3 ) 6= (n; t01 , t02 , t03 ) or, equivalently, rank(t1 , t, k) = plete classification of nonlinear Z2s -linear Hadamard codes of rank(t01 , t, k) for t1 6= t01 . Without loss of generality, we can length 2t , it is enough to focus on t ≥ 5, since all Z2s -linear assume that t01 < t1 . Note that if t01 = t1 , then t2 = t02 and Hadamard codes of length 2t are linear for t < 5. It is also t3 = t03 , so both codes are equal. mentioned in [13] that, at least for any 3 ≤ t ≤ 11, these codes First, we consider that 2 ≤ t01 < t1 . In this case, we have can be fully classified by using only the values of the rank (see to see that rank(t1 , t, k) − rank(t01 , t, k) 6= 0. Since t1 , t01 ≥ 2, Table I). Then, this pointed out that, maybe, it was possible σt1 = σt01 = 1 and we have that to obtain a complete classification for any t ≥ 5 by using just this invariant. However, the following example shows us that rank(t1 , t, k) − rank(t01 , t, k) = both invariants, the rank and the dimension of the kernel, are necessary in some cases. t41 13 3 71 1 11 3 − t + ( + (t − k + 1))t21 − ( + (t − k + 1))t1 + Example 5.1: Consider the Z8 -linear Hadamard codes of 24 12 1 24 2 12 2 length 217 = 131072, (t = 17), H 2,6,0 and H 4,1,4 . By t04 13 71 1 11 3 − 1 + t03 −( + (t−k+1))t02 1 +( + (t−k+1))t01 . Theorem 4.1, we have that rank(H 2,6,0 ) = rank(H 4,1,4 ) = 47. 24 12 1 24 2 12 2 12 By using the identity x2 − y 2 = (x + y)(x − y), we have that f (2, t, k) =1 − (t − k) = 0 ⇔ t − k = 1 rank(t1 , t, k) − rank(t01 , t, k) = f (3, t, k) = − 2 1 (t1 + t01 )(t21 + t02 2 0 02 1 ) − 26(t1 + t1 t1 + t1 )+ f (4, t, k) =2(t − k) − 13 = 0 ⇔ t − k = 13/2. 24 (t1 + t01 )(83 + 12(t − k)) − 58 − 36(t − k) =  1 Note that if t1 = 2, then t − k = t2 + 2 ≥ 2, so t − k 6= 1. (t1 + t01 )(t21 + t02 2 0 02 1 + 83) − 26(t1 + t1 t1 + t1 ) − 58+ 24 Therefore, for t1 ∈ {2, 3, 4}, f (t1 , t, k) 6= 0 and the result 12(t − k)(t1 + t01 − 3) , (19)  holds.  Recall that it is already known that there are b t−1 2 c which can be written as rank(t1 , t, k) − rank(t01 , t,k) = nonequivalent Z4 -linear Hadamard codes of length 2t , t ≥ 3 f (t1 , t01 ) + (t − k)g(t1 , t01 ), where f (t1 , t01 ) = 1/24 (t1 + [17]. Now, we establish how many nonequivalent Z8 -linear t01 )(t21 + t02 2 0 02 0 1 + 83) − 26(t1 + t1 t1 + t1 ) − 58 and g(t1 , t1 ) = Hadamard codes of length 2t there are, once the length 2t 0 0 1/2(t1 + t1 − 3). Note that (t − k)g(t1 , t1 ) ≥ 0 for all integer if fixed, for t ≥ 5. In [13], some upper and lower bounds pairs (t1 , t01 ) ∈ D, where D = {(t1 , t01 ) : 2 ≤ t01 < t1 }. It is are given for certain values of t. By Theorems 4.1 and 5.1, easy to see that f (t1 , t01 ) > 0 for all t01 ≥ 26, since we can 0 0 0 we know that if H t1 ,t2 ,t3 and H t1 ,t2 ,t3 are nonlinear Z8 - rewrite this expression in the following form: linear Hadamard codes of the same length with (t1 , t2 , t3 ) 6= (t01 , t02 , t03 ), then their corresponding pairs, (r, k), where r is t21 (t1 +t01 )+t02 0 0 2 0 0 1 (t1 +t1 )+83(t1 +t1 ) > 26t1 +26t1 (t1 +t1 )−58, the rank and k is the dimension of the kernel, are different. (20) Then, we have the following result: and we can observe that t21 (t1 + t01 ) > 26t21 , t02 (t 1 1 + t 0 1) ≥ Theorem 5.2: Let At,3 be the number of nonequivalent Z8 - 26t01 (t1 + t01 ) and 83(t1 + t01 ) > −58. linear Hadamard codes of length 2t . Then, for any t ≥ 5, Similarly, f (t1 , t01 ) > 0 for all t1 ≥ 26, considering the left- b(t+1)/3cj hand side of (20) as 26t1 (t1 + t01 ) + 26t02 1 − 58. Therefore, if jt + 1k X t + 1 − 3i k At,3 = + − 1. there exists a pair of integers (t1 , t01 ) such that rank(t1 , t, k) − 3 i=1 2 rank(t01 , t, k) = 0, this pair has to be in R = {(t1 , t01 ) : 2 ≤ t01 < t1 , t01 < 26, t1 < 26} ⊂ D. There are 1 + 2 + · · · + 23 = Proof. In [13, Theorem 5.3], an upper bound is given for the 276 pairs (t1 , t01 ) ∈ R, and it can be checked that any of them amount of different nonequivalent Z2s -linear Hadamard codes is a solution of the equation. for any t ≥ 3 and 2 ≤ s ≤ t − 1. In particular, when s = 3, Finally, we consider that 1 = t01 < t1 . In this case, we have we have the following bound: to prove that rank(t1 , t, k) − rank(t01 , t, k) 6= 0. Then, since At,3 ≤ t1 ≥ 2 and t01 = 1, σt1 = 1, σt01 = 2, and we obtain that |{(t1 , t2 , t3 ) ∈ N3 : t = 3t1 + 2t2 + t3 − 1, t1 ≥ 1}| − 1. rank(t1 , t, k) − rank(1, t, k) = By Theorems 4.1 and 5.1, we know that this bound is tight. t41 13 71 1 11 3 Therefore, we just have to see that − t3 + ( + (t − k + 1))t21 − ( + (t − k + 1))t1 + 24 12 1 24 2 12 2 |{(t1 , t2 , t3 ) ∈ N3 : t = 3t1 + 2t2 + t3 − 1, t1 ≥ 1}| = 1 2 1 13 71 ((t − k + 1) + t + k + 1) − + − − b(t+1)/3cj 2 24 12 24 jt + 1k X t + 1 − 3i k 1 11 3 1 + . (t − k + 2) + + (t − k + 2) − ((t − k + 2)2 + t + k). 3 i=1 2 2 12 2 2 This means that we need to compute the amount of different By simplifying, we have that solutions, (t1 , t2 , t3 ), of the equation t = 3t1 + 2t2 + t3 − 1 with t1 ≥ 1. jt + 1k rank(t1 , t, k) − rank(1, t, k) = It is easy to see that 1 ≤ t1 ≤ . Once the 3 14 value of jt1 is fixed, kwe can see that t2 is bounded by t − 26t31 + 83t21 − 58t1 + 12(t − k)(t21 − 3t1 ) .  24 1 t + 1 − 3t1 0 ≤ t2 ≤ . Note that, once t1 and t2 are fixed, 2 there is a unique value for t3 . Then, the amount of different Let f (t1 , t, k) = rank(t1 , t, k) − rank(1, t, k). We know that solutions of t = 3t1 + 2t2 + t3 − 1 with t1 ≥ 1, or equivalently t − k = 2t1 + t2 − 2 ≥ 2t1 − 2. Since 12(t − k)(t21 − 3t1 ) ≥ 0 1 4 |{(t1 , t2 , t3 ) ∈ N3 : t = 3t1 + 2t2 + t3 − 1, t1 ≥ 1}|, is for t1 ≥ 3, we have that f (t1 , t, k) ≥ g(t1 ) = [t − 26t31 + 24 1 b(t+1)/3c j 1 t + 1 − 3i k  83t21 − 58t1 + 12(2t1 − 2)(t21 − 3t1 )] = [t1 (t31 − 2t21 − 13t1 + X 24 +1 = 2 14)]. By computing the zeros of the polynomial g(t1 ) and i=1 analyzing its behavior, we have that f (t1 , t, k) ≥ g(t1 ) > 0 jt + 1k b(t+1)/3cj X t + 1 − 3i k for t1 ≥ 5. Therefore, we just need to compute f (t1 , t, k) + , 3 2 when t1 ∈ {2, 3, 4}. For these cases, we have that i=1 13 so the result holds.  codes of length 2t for a given t. It would be interesting to Example 5.2: Table I shows all possible values of (t1 , t2 , t3 ) generalize these results to any s ≥ 4, or prove that it is for which there exists a nonlinear Z8 -linear code H t1 ,t2 ,t3 of necessary to consider other invariants to classify such codes. length 2t for 5 ≤ t ≤ 11, together with the values of (r, k), Another further research on this topic would be to fix only the where r is the rank and k the dimension of the kernel. Since parameter t and find the number of nonequivalent Z2s -linear for these values of t the rank gives a complete classification, Hadamard codes having the same length 2t . In this sense, it the value of At,3 obtained from Theorem 5.2 coincides with is already proved that there are Z4 -linear codes which are the number of different (t1 , t2 , t3 ) in the second column of equivalent to a Z8 -linear Hadamard code [13]. the table, increased by one to add also the Z8 -linear code that is linear. R EFERENCES (t1 , t2 , t3 ) (r, k) At,3 [1] M. Shi, Z. Sepasdar, A. Alahmadi, P. Solé, “On two-weight Z2k -codes,” t=5 (2, 0, 0) (8,3) 2 Designs, Codes and Cryptography, 86, no. 6, pp. 1201–1209, (2018). (1, 2, 0) (8,5) [2] E. F. Assmus, J.D. Key, Designs and Their Codes, Cambridge t=6 3 University Press, Great Britain (1992). (2, 0, 1) (9,4) (1, 2, 1) (9,6) [3] H. Bauer, B. Ganter, F. Hergert, “Algebraic techniques for nonlinear t=7 (2, 0, 2) (10,5) 4 codes,” Combinatorica, 3, no. 1, pp. 21–33 (1983). (2, 1, 0) (12,4) [4] I. F. Blake, “Codes over integer residue rings,” Inform. Control, 29, pp. (1, 2, 2) (10,7) 295–300 (1975). (1, 3, 0) (12,6) [5] J. Borges, C. Fernández-Córdoba, J. Pujol, J. Rifà, M. Villanueva, t=8 (2, 0, 3) (11,6) 6 “Z2 Z4 -linear codes: generator matrices and duality,” Designs, Codes (2, 1, 1) (13,5) and Cryptography, 54, no. 2, pp. 167–179 (2010). (3, 0, 0) (17,4) [6] J. Borges, C. Fernández J. Rifà “Every Z2k -code is a binary propelinear (1, 2, 3) (11,8) code,” Electronic Notes in Discrete Mathematics, 10, pp. 100–102 (1, 3, 1) (13,7) (2001). (2, 0, 4) (12,7) [7] W. Bosma, J. J. Cannon, C. Fieker, A. Steel, Hand- t=9 7 book of Magma functions, Edition 2.22 5669 pages (2016). (2, 1, 2) (14,6) (2, 2, 0) (17,5) http://magma.maths.usyd.edu.au/magma/. (3, 0, 1) (18,5) [8] C. Carlet, “Z2k -linear codes,” IEEE Trans. Inform. Theory, 44, no. 4, (1, 2, 4) (12,9) pp. 1543–1547 (1998). (1, 3, 2) (14,8) [9] S. T. Dougherty, C. Fernández-Córdoba, “Codes over Z2k , Gray map (1, 4, 0) (17,7) and self-dual codes,” Advances in Mathematics of Communications, 5, (2, 0, 5) (13,8) no. 4, pp. 571–588 (2011). t = 10 9 [10] C. Fernández-Córdoba, C. Vela, M. Villanueva, “Construction and (2, 1, 3) (15,7) (2, 2, 1) (18,6) classification of the Z2s -linear Hadamard codes,” Electronic Notes in (3, 0, 2) (19,6) Discrete Mathematics, 54, pp. 247–252 (2016). (3, 1, 0) (24,5) [11] C. Fernández-Córdoba, C. Vela, M. Villanueva, “On the kernel of (1, 2, 5) (13,10) Z2s -linear Hadamard codes,” Coding theory and Applications, ICMCTA (1, 3, 3) (15,9) 2017. Lecture Notes in Computer Science, 10495, pp. 107–117 (2017). (1, 4, 1) (18,8) [12] C. Fernández-Córdoba, C. Vela, M. Villanueva, “On the rank of Z8 - (2, 0, 6) (14,9) linear Hadamard codes,” To appear in Electronic Notes in Discrete (2, 1, 4) (16,8) Mathematics (2018). t = 11 11 [13] C. Fernández-Córdoba, C. Vela, M. Villanueva, “On Z2s -linear (2, 2, 2) (19,7) (2, 3, 0) (23,6) Hadamard codes: kernel and partial classification,” To appear in (3, 0, 3) (20,7) Designs, Codes and Cryptography (2018). (3, 1, 1) (25,6) [14] M. K. Gupta, M. C. Bhandari, A. K. Lal, “On linear codes over Z2s ,” (4, 0, 0) (32,5) Designs, Codes and Cryptography, 36, no. 3, pp. 227–244 (2005). Table I [15] A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, P. T YPE , RANK AND DIMENSION OF THE KERNEL FOR ALL NONLINEAR Solé, “The Z4 -linearity of Kerdock, Preparata, Goethals and related Z8 - LINEAR H ADAMARD CODES OF LENGTH 2t FOR 5 ≤ t ≤ 11. codes,” IEEE Trans. Inform. Theory, 40, no. 2, pp. 301–319 (1994). [16] D. S. Krotov, “On Z2k -dual binary codes,” IEEE Trans. Inf. Theory, 53, no 4, pp. 1532–1537 (2007). [17] D. S. Krotov, “Z4 -linear Hadamard and extended perfect codes,” International Workshop on Coding and Cryptography, ser.Electron. VI. C ONCLUSIONS Notes Discrete Math. 6, pp. 107–112 (2001). [18] D. S. Krotov, M. Villanueva, M. “Classification of the Z2 Z4 -linear The Z4 -linear Hadamard codes can be classified by using Hadamard codes and their automorphism groups,” IEEE Trans. Inf. just one of the invariants, the rank or the dimension of the Theory, 61, no. 2, pp. 887–894 (2015). [19] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting kernel [17], [20]. In general, for Z2s -linear Hadamard codes Codes, Elsevier (1977). of length 2t , the kernel and its dimension were studied in [13], [20] K. T. Phelps, J. Rifà, M. Villanueva, “On the additive (Z4 -linear and where it was also proved that this invariant is not enough non-Z4 -linear) Hadamard codes: rank and kernel,” IEEE Trans. Inf. Theory, 52, no. 1, pp. 316–319 (2006). to obtain a full classification of these codes, once s and t [21] P. Shankar, “On BCH codes over arbitrary integer rings,” IEEE Trans. are fixed. In this paper, we focus on s = 3. We study the Inf. Theory, 25, no. 4, pp. 480–483 (1979). rank of the Z8 -linear Hadamard codes of length 2t , and also [22] H. Tapia-Recillas, G. Vega, “On Z2k -linear and quaternary codes,” SIAM J. Discrete Math., 17, no. 1, pp. 103–113 (2003). give an explicit construction of the linear independent vectors that generate the span. Through Example 5.1, we observe that the rank, by itself, is not enough to obtain a complete classification. However, we prove that it is really possible by Cristina Fernández-Córdoba was born in Sabadell, Catalonia (Spain) in using both of them, the rank and dimension of the kernel. We 1977. She received her Bachelor’s degree in Mathematics in 2000 from also provide the amount of nonequivalent Z8 -linear Hadamard the Universitat Autònoma de Barcelona and the Ph.D. degree in Science 14 (Computer Science Section) in 2005 from the same university. In 2000 she joined the Department of Computer Science at the Universitat Autònoma de Barcelona, and in 2005 the Department of Information and Communications Engineering at the same university. In 2008, she joined the Fundación Española para la Ciencia y la Tecnologı́a and she did a one year research stay at Auburn University under a Fulbright grant. From 2009, she is within the Department of Information and Communications Engineering at the Universitat Autònoma de Barcelona where currently is an Associate Professor. Her research interests include subjects related to combinatorics, coding theory and graph theory. Carlos Vela was born in Sevilla, Spain, in November 1992. He received the B.Sc. degree in Mathematics and the M.Sc. degree in Computer Science and AI from the Universidad de Sevilla, Spain, in 2014 and 2015, respectively, and the Ph.D. degree in Computer Science from the Universitat Autònoma de Barcelona, Spain, in 2018. He worked at the Information and Communications Engineering Department of the Universitat Autònoma de Barcelona while pursuing his Ph.D. degree. His research interests include subjects related to algebra and coding theory. Mercè Villanueva was born in Roses, Catalonia, in January 1972. She received the B.Sc. degree in Mathematics in 1994 from the Autonomous University of Barcelona, the M.Sc. degree in Computer Science in 1996, and the Ph.D. degree in Science (Computer Science Section) in 2001 from the same university. In 1994 she joined the Department of Information and Communications Engineering, at the Autonomous University of Barcelona, as an Assistant Professor, and was promoted to Associate Professor in 2002. Her research interests include subjects related to combinatorics, algebra, coding theory, and graph theory.