ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.505364 J. Algebra Comb. Discrete Appl. 6(1) • 1–11 Received: 21 August 2017 Accepted: 2 December 2018 Journal of Algebra Combinatorics Discrete Structures and Applications Weight distribution of a class of cyclic codes of length 2n Research Article Manjit Singh, Sudhir Batra Abstract: Let Fq be a finite field with q elements and n be a positive integer. In this paper, we determine the weight distribution of a class cyclic codes of length 2n over Fq whose parity check polynomials are either binomials or trinomials with 2l zeros over Fq, where integer l ≥ 1. In addition, constant weight and two-weight linear codes are constructed when q ≡ 3 (mod 4). 2010 MSC: 12E05, 12E20, 94B05, 11T71 Keywords: Linear codes, Reversible codes, Weight distributions, Constant weight codes 1. Introduction A linear [m,k]q code C over Fq is a k-dimensional subspace of Fmq . Let λ be a nonzero element in Fq. A linear code C of length m over Fq is called a λ-constacyclic code if (c1,c2, . . . ,cm−1,c0λ) ∈ C, ∀ (c0,c1,c2, . . . ,cm−1) ∈ C. A λ-constacyclic code of length m over Fq is called a simple-root code if gcd(m,q) = 1; otherwise it is called repeated-root code. If we identify a vector (a0,a1, . . . ,am−1) ∈ Fmq with a polynomial a0xm−1 + a1x m−2 +· · ·+am−1 modulo (xm−λ) in Fq[x], then a simple-root λ-constacyclic code C can be interpreted as an ideal of the quotient ring R = Fq[x]/〈xm −λ〉. It is well known that each ideal in R is of the form 〈g(x)〉, where g(x) is a monic divisor of xm −λ in Fq[x]. The polynomial g(x) is known as the generator polynomial of the code C and the corresponding factor h(x) = (xm −λ)/g(x) of xm −λ is referred to as the parity check polynomial of the code C. If h(x) is a product of t monic irreducible factors over Fq, then we say C with t zeros over Fq. A constacyclic code is called an irreducible code over Fq if t = 1, Manjit Singh (Corresponding Author), Sudhir Batra; Department of Mathematics, Deenbandhu Chhotu Ram University of Science and Technology, Murthal-131039, Sonepat, India (email: manjitsingh.math@gmail.com, batrasudhir@rediffmail.com). 1 https://orcid.org/0000-0003-3351-7287 https://orcid.org/0000-0003-4139-0589 M. Singh, S. Batra / J. Algebra Comb. Discrete Appl. 6(1) (2019) 1–11 and a reducible code over Fq if t ≥ 2. A λ−constacyclic code C is called cyclic if λ = 1 and negacyclic if λ = −1. Let Ai be the number of codewords of a linear code C of length m over Fq with Hamming weight i, where 0 ≤ i ≤ m. Note that A0 = 1 and Ai = 0 for all 1 ≤ i < d, where d is the minimum Hamming distance of the code. The sequence (1,A1,A2, . . . ,Am) is called the weight distribution of the code C. Cyclic codes are the most important class of linear codes for a wide variety of applications. In the last few decades, the weight distribution of irreducible cyclic codes have been studied extensively (see [3, 9, 12]). However, not much is known about the weight distribution of reducible codes except in very specific cases. Vega [11] presented a new family of two-weight reducible cyclic codes that can be constructed as the direct sum of two one-weight irreducible codes. For any q = pm, where p is an odd prime, m ≥ 3, k ≥ 1 and gcd(k,m) = 1, Feng and Luo [4] obtained weight distribution of cyclic codes C1 of dimension 2m and C2 of dimension 3m over Fp of length n = q − 1 with parity-check polynomial h2(x)h3(x) and h(x) = h1(x)h2(x)h3(x) respectively, where h1(x), h2(x) and h3(x) are the minimal polynomials of π−1, π−2 and π−(p k+1) over Fp, respectively, for a primitive element π of Fq with deghi(x) = m for i = 1, 2, 3. For doing this, they computed the value distribution of multi-sets of exponential sums using quadratic form over Fp. Yang, Xiong, Ding and Luo [14] proposed a class of cyclic codes C of length n over Fq with parity- check polynomial h(x) = ha1 (x)ha2 (x) · · ·hat (x), where hai (x) is the minimal polynomial of γ−ai over Fq, deghai (x) = m, r = q m, γ is a generator of F∗r and n = (r−1)/δ, δ = gcd(r−1,a1,a2, . . . ,at) and integer e ≥ t ≥ 2 with e|(q − 1). They remarked that it may be very difficult to find the weight distribution of this class of codes if the integers ai are not chosen in the right way or the Gaussian periods have many different values. The values of the Gaussian periods are in general very hard to determine. Hence they obtained the weight distribution of this class of codes when t = e and the Gaussian periods of order N are known, including the cases that N = 1, 2, 3, semi-primitive case and a special index 2 case. Recently, assuming `v||(q − 1), where ` is a prime and v is an integer, and q ≡ 1 (mod 4) if ` = 2, Zhu, Yue and Hu [15] have applied a combinatorial method to obtain not only the weight distribution of all cyclic codes of length `m with two zeros over Fq, but also the weight distribution of a special cyclic code of length `m with three zeros over Fq. In this paper, we present a class of cyclic codes of length 2n with 2l zeros over Fq, where q is an odd prime power and n > l ≥ 1. Further, using the explicit forms of codewords, the weight distribution of these codes is determined explicitly. We make use of Diophantine equation and its solutions to obtain the explicit form of weights of codewords and the number of codewords of the given weight of these cyclic codes. It is observed that, when q ≡ 3 (mod 4), the problem of finding the weight distribution is transferred into a problem of determining the weight distribution of a two-weight negacyclic code, which turns out to be associated with counting the number of constant weight linear codes. These codes are known for applicability of various association schemes and traceability schemes, which justify their practical applications in engineering perspective (see [1, 2, 5–7]). In particular, these codes are of special interest in authentication codes [2] and traceability schemes [6]. The paper is organized as follows: The necessary notations and some auxiliary results are provided in Section 2. In Section 3, we describe a class of negacyclic and hence cyclic codes of length 2n with 2l zeros over Fq. It is observed that these reducible codes are reversible when q ≡ 3 (mod 4). In Section 4, constant weight linear codes and two-weight negacyclic codes are constructed and the weight distribution of cyclic codes of length 2n with 2l zeros over Fq are determined. In the end of this section, we give an example illustrating the results. In Section 5, we conclude the paper. 2. Preliminaries The paper follows the standard notation of finite fields. The multiplicative group of Fq is denoted by F∗q. It is well known that F ∗ q is a cyclic group of order q− 1. For any integer m ≥ 2, let ν2(m) denote 2 M. Singh, S. Batra / J. Algebra Comb. Discrete Appl. 6(1) (2019) 1–11 the highest power of 2 dividing m. Let q be an odd prime power, s = ν2(q−1) and u = ν2(q2 −1). Then u−s = ν2(q + 1) ≥ 1. Readily note that (i) u−s = 1 if and only if q ≡ 1 (mod 4), and (ii) s = 1 if and only if q ≡ 3 (mod 4). Let αk be a primitive 2kth root of unity in F∗q. Also, let βk be a primitive 2 kth root of unity in F∗ q2 when s + 1 ≤ k ≤ u. Notice that β2s+1 = αs. Since βk ∈ Fq2 \ Fq, the minimal polynomial of βk over Fq is x2 − (βk + β q k)x + β q+1 k . If f(x) is an irreducible polynomial over Fq and f(0) 6= 0, then, for any integer k ≥ 2, the following result is useful to check the irreducibility of the polynomial of the type of f(xk) over Fq. Lemma 2.1. [13, Theorem 10.15] Let f(x) be any irreducible polynomial over Fq of degree l ≥ 1. Suppose that f(0) 6= 0 and f(x) is of order e which is equal to the order of any root of f(x). Let k be a positive integer, then the polynomial f(xk) is irreducible over Fq of order ke if and only if the following three conditions are satisfied: (i) Every prime divisor of k divides e; (ii) gcd(k, q l−1 e ) = 1; (iii) If 4|k, then 4|(ql − 1). We end this section with the following lemma. Lemma 2.2. Let q be an odd prime power and r ≥ 1 be an integer. Then (i) For any 2 ≤ k ≤ s, x2 r − αk is a product of 2l monic irreducible binomial factors of degree 2r−l over Fq, where l = min{r,s−k}. (ii) For any s + 2 ≤ k ≤ u, x2 r+1 − (βk + β q k)x 2r + β q+1 k is a product of 2 l monic irreducible trinomial factors of degree 2r−l over Fq, where l = min{r,u−k}. Proof. (i) For any fixed 2 ≤ k ≤ s, let l = min{r,s − k}. Then 2k+l|(q − 1), αk+l ∈ F∗q such that αk = α 2l k+l. The set Sk = {α 2ki+1 k+l : 1 ≤ i ≤ 2 l} contains 2l distinct elements of order 2k+l in F∗q. For any α ∈ Sk, x2 r−l −α is a factor of x2 r −αk. Since gcd(2r−l, q−12k+l ) = 1, by Lemma 2.1, x 2r−l −α is irreducible over Fq for every α ∈ Sk. (ii) For any fixed s + 2 ≤ k ≤ u, let l = min{r,u − k}. Then 2k+l|(q2 − 1), βk+l ∈ F∗q2 such that βk = β 2l k+l. The set Tk = {β 2ki+1 k+l : 1 ≤ i ≤ 2 l} contains 2l distinct elements of order 2k+l in F∗ q2 . In view of the part (i), x2 r−l − η is an irreducible factor of x2 r − βk over Fq2 for every η ∈ Tk. For any η ∈ Tk, we notice that βk = η2 l and βqk = (η q)2 l . Further, x2 r−l − η is a factor of x2 r − βk over Fq2 if and only if x2 r−l −ηq is a factor of x2 r −βqk over Fq2. This bijection of factors of x 2r −βk and x2 r −βqk over Fq2 generates a unique factor (x2 r−l − η)(x2 r−l − ηq) = x2 r−l+1 − (η + ηq)x2 r−l + ηq+1 ∈ Fq[x] of (x2 r −βk)(x2 r −βqk) = x 2r+1 − (βk + β q k)x 2r + β q+1 k ∈ Fq[x] for every η ∈ Tk. Since gcd(2 r−l, q 2−1 2k+l ) = 1, hence by Lemma 2.1, x2 r−l+1 − (η + ηq)x2 r−l + ηq+1 is irreducible over Fq for every η ∈ Tk. 3. Negacyclic and cyclic codes For any 1 ≤ k ≤ s and integer r ≥ 0, we define a negacyclic [2k+r−1, 2r]q code and a cyclic [2k+r, 2r]q code over Fq by N (k) r = 〈N (k) r (x)〉 and C (k) r = 〈C (k) r (x)〉, respectively, with the generator polynomials N(k)r (x) = x2 r+k−1 + 1 x2 r −αk and C(k)r (x) = x2 r+k − 1 x2 r −αk . 3 M. Singh, S. Batra / J. Algebra Comb. Discrete Appl. 6(1) (2019) 1–11 Note that N(1)r is the whole space F2 r q . By Lemma 2.2, for each 2 ≤ k ≤ s, N (k) r and C (k) r are the codes with 2l zeros over Fq, where l = min{r,s−k}. Lemma 3.1. For any 1 ≤ k ≤ s and integer r ≥ 0, N(k)r = {(b,bαk, . . . ,bα 2k−1−1 k ) : b ∈ F 2r q } and C(k)r = {(b,bαk, . . . ,bα 2k−1−1 k ,−b,−bαk, . . . ,−bα 2k−1−1 k ) : b ∈ F 2r q }. Proof. For 1 ≤ k ≤ s, observe that α2 k−1 k = −1. It follows that x2 k−1 + 1 = (x−αk) 2k−1−1∑ i=0 αikx 2k−1−i−1 and for any r ≥ 0, x2 r+k−1 + 1 = (x2 r −αk) 2k−1−1∑ i=0 αikx 2r(2k−1−i−1) = (x2 r −αk)N(k)r (x). Therefore the generator polynomial of N(k)r is N(k)r (x) = 2k−1−1∑ i=0 αikx 2r(2k−1−i−1). Let b = (b0,b1, . . . ,b2r−1) ∈ F2 r q be a message word and the corresponding message polynomial be b(x) = ∑2r−1 j=0 bjx 2r−j−1 ∈ Fq[x]. Then the code polynomial of N (k) r is given by: b(x) ( x2 r+k−1 + 1 x2 r −αk ) = 2k−1−1∑ i=0 2r−1∑ j=0 bjα i kx 2r+k−1−2ri−j−1. The polynomial on the right hand side can be expressed as a vector of the form (b,bαk, . . . ,bα 2k−1−1 k ) by substituting i = 0, 1, . . . , 2k−1 − 1. Hence, we have N(k)r = {(b,bαk, . . . ,bα 2k−1−1 k )}. Since the generator polynomial of C(k)r is C(k)r (x) = N (k) r (x) ( x2 r+k−1 − 1 ) , so we obtain C(k)r = {(c,−c) : c = (b,bαk, . . . ,bα 2k−1−1 k ) ∈ N (k) r }. Lemma 3.1 is valid for every odd q. Consider the case q ≡ 3 (mod 4), i.e., s = 1, then we obtain the following trivial codes: N (1) r = F2 r q and C (1) r = {(c,−c) : c ∈ F2 r q }. 4 M. Singh, S. Batra / J. Algebra Comb. Discrete Appl. 6(1) (2019) 1–11 In the rest of this section, we assume q ≡ 3 (mod 4). In order to define a class of cyclic codes with parity check polynomial of the type x2 r+1 − (βk + β q k)x 2r + β q+1 k with 2 l zeros, where l = min{r,u−k}, we need a bit more notations of [10]. For any x ∈ Fq2 \ Fq, let T(x) = x + xq and N(x) = xq+1. It follows that the minimal polynomial of β2 over Fq is x2 + 1, and the minimal polynomial of βk over Fq is x2 − T(βk)x + N(βk) for every 3 ≤ k ≤ u. For every 1 ≤ i ≤ 2k−2 and 3 ≤ k ≤ u, there are exactly 2k−2 elements of the form T(β2i−1k ) and N(β2i−1k ) = β q+1 k = ±1. In order to avoid cumbersome notations, for a fixed k, we denote ξ = T(βk), � = β q+1 k . Note that ξ = 0 if k = 2; � = 1 for 2 ≤ k ≤ u − 1 and � = −1 for k = u. Further, for any integer i ≥ 0 and 3 ≤ k ≤ u, we define the followings: (i) δi = βik −β qi k βk −β q k with δ0 = 0, δ1 = 1 and δ2k−1−i = �iδi for every 0 ≤ i ≤ 2k−1 − 1. In view of [10, Lemma 3.1], δi = ξδi−1 − �δi−2 for 2 ≤ i ≤ 2k−1 − 1, with δ0 = 0 and δ1 = 1. (ii) γi(a,b) = δi+1a + δib, where a,b ∈ Fq. Lemma 3.2. Let 3 ≤ k ≤ u be a fixed integer and a,b ∈ Fq. Then, the sequence (γi(a,b))i≥0 satisfies the recursive relation γi(a,b) = ξγi−1(a,b) − �γi−2(a,b), for i ≥ 2 with γ0(a,b) = a, γ1(a,b) = ξa + �b. For any given (a,b) ∈ Fq × Fq, the sequence γi = γi(a,b) contains 2k terms satisfying γ2k−1+i = −γi for every 0 ≤ i ≤ 2k−1 − 1. Proof. By our definition γi(a,b) = δi+1a+δib, where 0 ≤ i ≤ 2k−1−1 and a,b ∈ Fq, it is immediate. For any fixed 3 ≤ k ≤ u, observe that x2 − ξx + � is a divisor of x2 k−1 + 1, but not a divisor of x2 k−1 − 1. Let Nk(x) = x2 k−1 + 1 x2 − ξx + � . (If k = 2, then ξ = 0, � = 1 and hence Nk(x) = 1.) Further, for any integer r ≥ 0, x2 r+1 − ξx2 r + � is a divisor of x2 r+k−1 + 1. Let Nr,k(x) = x2 r+k−1 + 1 x2 r+1 − ξx2r + � and Cr,k(x) = Nr,k(x)(x 2r+k−1 − 1). Then Nr,k(x) = Nk(x2 r ). For any integer r ≥ 0, we define a negacyclic [2r+k−1, 2r+1]q code and a cyclic [2r+k, 2r+1]q code over Fq by Nr,k = 〈Nr,k(x)〉, Cr,k = 〈Cr,k(x)〉 with Nk = N0,k, a 2-dimensional negacyclic code of length 2k−1 over Fq. For 3 ≤ k ≤ u, by Lemma 2.2, Nr,k and Cr,k are the codes with 2l zeros over Fq. Remark 3.3. Let f(x) = a0xm + a1xm−1 + · · ·+ am ∈ Fq[x] be a polynomial of degree m. The reciprocal polynomial of f(x) is the polynomial f∗(x) = xmf(x−1) = amxm + am−1xm−1 + · · · + a0. Further, f(x) is said to be reversible provided f∗(x) = f(x). A reversible code is a code such that reversing the order of the components of a codeword gives always a codeword. Massey [8] showed that reversible cyclic codes are those which have self-reciprocal generator polynomials. For any integer r ≥ 0, the polynomial x2 r+1 − ξx2 r + 1 is reversible. By Lemma 2.2, x2 r+1 − ξx2 r + 1 is reducible over Fq and hence Cr,k is a reducible and reversible cyclic code. Cyclic codes can be decoded by sequential circuits, and hence the invariance of these codes under the reversing transformation is of special interest [8]. Theorem 3.4. For any fixed k in 3 ≤ k ≤ u, the negacyclic [2k−1, 2]q-code is given by Nk = {(γ0(a,b),γ1(a,b), . . . ,γ2k−1−1(a,b) : a,b ∈ Fq}. Further, for any integer r ≥ 0, the negacyclic [2r+k−1, 2r+1]q code Nr,k is Nr,k = Nk ×Nk ×···×Nk︸ ︷︷ ︸ 2rcopies . 5 M. Singh, S. Batra / J. Algebra Comb. Discrete Appl. 6(1) (2019) 1–11 Proof. For any fixed 3 ≤ k ≤ u, observe that Nk(x) = x2 k−1 + 1 (x−βk)(x−β q k) = 2k−1−1∑ i=1 ( βik −β iq k βk −β q k ) x2 k−1−i−1 = 2k−1−1∑ i=1 δix 2k−1−i−1. The code polynomial of Nk is (ax + b)Nk(x) = 2k−1−1∑ i=1 δi(ax + b)x 2k−1−i−1 = 2k−1−1∑ i=0 (aδi+1 + bδi) x 2k−1−i−1. In view of Lemma 3.2, we obtain the desired form of Nk. Now, for any integer r ≥ 0, we have Nr,k(x) = Nk(x 2r ) = 2k−1−1∑ i=1 δix 2r(2k−1−i−1). Let a(x) = ∑2r+1−1 j=0 ajx 2r+1−j−1 be the polynomial representation of the vector a = (a0,a1, . . . ,a2r+1−1) ∈ F2 r+1 q . If we denote bj = aj+2r for 0 ≤ j ≤ 2r − 1, then a = (a0,a1, . . . ,a2r−1,b0,b1, . . . ,b2r−1) and a(x) = 2r−1∑ j=0 (ajx 2r + bj)x 2r−j−1. The code polynomial of Nr,k is a(x)Nr,k(x) = 2r−1∑ j=0 2k−1−1∑ i=1 δi(ajx 2r + bj)x 2r(2k−1−i)−j−1 = 2r−1∑ j=0  2k−1−2∑ i=0 ajδi+1x 2r(2k−1−i)−j−1 + 2k−1−1∑ i=1 bjδix 2r(2k−1−i)−j−1   = 2r−1∑ j=0 2k−1−1∑ i=0 (ajδi+1 + bjδi) x 2r+k−1−2ri−j−1. Let γi,j = γi(aj,bj) = ajδi+1 + bjδi, where 0 ≤ i ≤ 2k−1 − 1 and 0 ≤ j ≤ 2r − 1. Note that any codeword in Nk is of the form (c0,c1, . . . ,c2k−1−1) with ci = γi(a,b) for 0 ≤ i ≤ 2k−1 − 1. Similarly, let us denote c2k−1j+i = γi,j = γi(aj,bj) for 0 ≤ j ≤ 2r − 1. Then any codeword of Nr,k can be expressed as (c0,c1, . . . ,c2r+k−1−1) in which for every 0 ≤ i ≤ 2k−1 − 1, there exists 0 ≤ l ≤ 2k−1 − 1 such that c2k−1j+i = cl. Let Ej = {(c2k−1j+0,c2k−1j+1, . . . ,c2k−1j+2k−1−1)}. Then Ej is a block subcode of Nr,k such that Ej = Nk. Since Nr,k = {(c̄0, c̄1, . . . , c̄2r−1) : c̄j ∈Ej}, we have Nr,k = {(c̄0, c̄1, . . . , c̄2r−1) : c̄j ∈ Nk for 0 ≤ j ≤ 2r − 1}. This completes the proof. 6 M. Singh, S. Batra / J. Algebra Comb. Discrete Appl. 6(1) (2019) 1–11 4. Weight distributions In this section, we determine the weight distribution of codes defined in the last section. The following theorem gives the weight distribution of C(k)r for 2 ≤ k ≤ s. Theorem 4.1. Let q ≡ 1 (mod 4) and 2 ≤ k ≤ s. Then, for any integer r ≥ 0, the weight distribution of C(k)r is given by: A2kj = ( 2r j ) (q − 1)j ; where 0 ≤ j ≤ 2r. Proof. Let b = (b0,b1, . . . ,b2r−1) be a message word. Further, let j denote the number of nonzero symbols in b. Since each nonzero symbol has q − 1 choices and there are exactly ( 2r j ) message word with j nonzero symbols, the number of message word having j nonzero symbols is ( 2r j ) (q−1)j, where 0 ≤ j ≤ 2r. By Lemma 3.1, any codeword of C(k)r is of the type (c,−c), where c ∈ N (k) r such that c = (b,bαk, . . . ,bα 2k−1−1 k ) with b = (b0,b1, . . . ,b2r−1). Using the form of codeword c, the weight of c is 2k−1j and the number of codewords of weight 2k−1j are also ( 2r j ) (q−1)j. It follows that, the weight of any codeword of C(k)r is 2kj and the number of codewords of weight 2kj is same as the number of codewords of weight 2k−1j. Therefore A2kj = ( 2r j ) (q−1)j. Remark 4.2. For any integer r ≥ 0, C(1)r = {(c,−c) : c = (b0,b1, . . . ,b2r−1)}, the weight distribution of C (1) 1 is A2j = ( 2r j ) (q − 1)j. In rest of the section, we determine the weight distribution of cyclic codes Cr,k for 3 ≤ k ≤ u and integer r ≥ 0. At first, we determine the weight distribution of Nr,k. In view of Theorem 3.4, the weight distribution of Nr,k can be derived from the weight distribution of Nk. Fundamentally, we need to compute the weight distribution of Nk. In this connection, some additional conventions are explained here. Let Θ : F2q → Nk be a mapping, defined as Θ((a,b)) = (c0,c1, . . . ,c2k−1−1), where ci = γi(a,b) for any a,b ∈ Fq. Then Θ is an Fq-isomorphism. Further, for any fixed 0 ≤ i ≤ 2k−1 − 1, let Ki = {(a,b) ∈ F2q : ci = 0}. Observe that Ki is an 1-dimensional subspace of F2q with K0 = {(0,b) : b ∈ Fq} = Fq and K2k−1−1 = {(a, 0) : a ∈ Fq} = Fq. Denote Ni = Θ(Ki), a copy of Ki in Nk. Obviously, Ni is also an 1-dimensional subspace of Nk. A code C with the same Hamming distance between every pair of its codewords is called an equidis- tant code. If all the codewords of a code C carry the same weight, then C is called constant weight code. A code C with both of these properties is known as equidistant constant weight code. A linear constant weight code is always an equidistant code. The following result presents a class of constant weight codes, which are applied in many areas [2, 5, 6]. Lemma 4.3. For each 0 ≤ i ≤ 2k−1 − 1 and 3 ≤ k ≤ u, Ni is a constant weight linear code such that N0 = {(0,δ1a,δ2a,. . . ,δ2k−1−1a) : a ∈ Fq}, N2k−1−1 = {(δ1a,δ2a,. . . ,δ2k−1−1a, 0) : a ∈ Fq} and for any 1 ≤ i ≤ 2k−1 − 2, 7 M. Singh, S. Batra / J. Algebra Comb. Discrete Appl. 6(1) (2019) 1–11 Ni = {(a,δ1(λ1 −λi)a,. . . ,δj(λj −λi)a,. . . ,−�λia) : a ∈ Fq} with Ni ∩Nj = {(0, 0, . . . , 0)} for 1 ≤ i 6= j ≤ 2k−1 − 1, where λi = δi+1/δi for 1 ≤ i ≤ 2k−1 − 2. Proof. For any (a,b) ∈ Ki, there exists a unique (c0,c1, . . . ,c2k−1−1) ∈ Ni such that ci = γi(a,b) = δi+1a + δib = 0. If c0 = 0, then a = 0 and cj = δjb for 1 ≤ j ≤ 2k−1 − 1. It follows that N0 = {(0,δ1b, . . . ,δ2k−1−1b) : b ∈ Fq}. Also if c2k−1−1 = 0, then b = 0 and cj = δj+1a for 0 ≤ j ≤ 2k−1 − 2 and hence N2k−1−1 = {(δ1a,δ2a,. . . ,δ2k−1−1a, 0) : a ∈ Fq}. Further, let 1 ≤ i ≤ 2k−1 − 2 and (a,b) ∈ Ki i.e., ci = γi(a,b) = 0. Then b = −λia, where λi = δi+1/δi for 1 ≤ i ≤ 2k−1 − 2. It follows that Ni = {(a,δ1(λ1 −λi)a,. . . ,δj(λj −λi)a,. . . ,−�λia) : a ∈ Fq}. Next we shall show that Ni is constant weight code. This assertion obviously holds for i = 0 and i = 2k−1 − 1. Further, let 1 ≤ i ≤ 2k−1 − 2. For this, we must show that ci is the only zero in (c0,c1, . . . ,c2k−1−1). Assume ci = cj = 0 for j 6= i. Then λi = λj for i 6= j. This implies βk ∈ Fq for 3 ≤ k ≤ u, which is a contradiction as 2k - (q − 1) for k ≥ 2 when q ≡ 3 (mod 4). So cj 6= 0 for any j 6= i. Therefore the weight of any nonzero codeword of Ni is 2k−1 − 1 for every 0 ≤ i ≤ 2k−1 − 1 and Ni ∩Nj = {(0, 0, . . . , 0)} for every 1 ≤ i 6= j ≤ 2k−1 − 1. This proves the result. We now move to determine the weight distribution of Nk for 3 ≤ k ≤ u. Theorem 4.4. The negacyclic code Nk is a two-weight code for 3 ≤ k ≤ u. Further, if ` (k) 0 and ` (k) 1 are non-zero weights of Nk and if A (0) ` (k) i is the number of words of weight `(k)i in Nk, then ` (k) 0 = 2 k−1, `(k)1 = ` (k) 0 − 1, A (0) ` (k) 0 = (q − 2k−1 + 1)(q − 1) and A(0) ` (k) 1 = 2k−1(q − 1). Proof. Let c = (c0,c1, . . . ,c2k−1−1) ∈ Nk be a codeword with ci = γi(a,b), where a,b ∈ Fq. For a moment, if ci = 0 and cj = 0 for some i 6= j, then a = b = 0. In this case c becomes a zero codeword. Thus no two symbols of a nonzero codeword c can be simultaneously zero. Therefore the possible weight of nonzero c is `(k)i = 2 k−1 − i for i = 0, 1. For any fixed 0 ≤ i ≤ 2k−1 − 1, by Lemma 4.3, Ni has q − 1 nonzero codewords of weight 2k−1 − 1 and one codeword of weight zero. Let N = ⋃2k−1−1 i=0 Ni and M = {c ∈ Nk : c /∈ N}. Then Nk = M∪N and M∩N = ∅. Observe that N has (q − 1)2k−1 codewords of weight 2k−1 − 1. Therefore, M has (q2 − 1) − (q − 1)2k−1 = (q − 1)(q − 2k−1 + 1) nonzero codewords of weight 2k−1. Remark 4.5. Take q + 1 = 2k−1 for some 3 ≤ k ≤ u, then by Lemma 4.3, M = ∅ and N = Nk. Equivalently, Nk is a linear constant weight code with constant weight 2k−1 − 1. For example, N6 is a constant weight code of length 32 with the constant weight 31 over F31. Further, if q + 1 6= 2k−1, but q + 1 = 2k for some 2 ≤ k ≤ u− 1, then Nk is a linear 2-weight code of the same frequency 2k−1(q − 1), i.e., A(0) ` (k) i = 2k−1(q − 1) for i = 0, 1 (see Example 4.8). The following result determines the weight distribution of Nr,k recursively using the weight distribu- tion of Nk. Theorem 4.6. For any r ≥ 0 and 3 ≤ k ≤ u, the weight distribution of negacyclic codes Nr,k over Fq is A`(k) = ∑ (x,y) ( 2r x )( 2r −x y )( (q − 2k−1 + 1)(q − 1) )x( 2k−1(q − 1) )y , where (x,y) varies over all possible solutions of the Diophantine equation 2k−1x+ (2k−1−1)y = `(k) such that 0 ≤ x ≤ 2r, 0 ≤ y ≤ 2r −x. 8 M. Singh, S. Batra / J. Algebra Comb. Discrete Appl. 6(1) (2019) 1–11 Proof. In view of Theorem 3.4, Nr,k = Nk ×Nk ×···×Nk︸ ︷︷ ︸ 2r copies . If c ∈ Nr,k is any codeword, then there are 2r vectors c̄1, c̄2, . . . , c̄2r (not necessarily distinct) in Nk such that c = (c̄1, c̄2, . . . , c̄2r ). By Theorem 4.4, the possible weights of codewords c̄j ∈ Nk, where 1 ≤ j ≤ 2r, are `(k)i = 2 k−1 − i for i = 0, 1, 2k−1. Let xi, for i = 0, 1, 2k−1, be the number of c̄j’s in a codeword c of weight `(k)i . Clearly x1 + x2 + x2k−1 = 2 r. Further, if `(k) denotes the weight of c, then `(k) = ` (k) 0 x0 + ` (k) 1 x1. For the given 2r copies of Nk, we first can choose the x0 copies of weight 2k−1 in ( 2r x0 ) ways. From 2r − x0 copies of Nk, we can select the x1 copies of them, having weight 2k−1 − 1, in ( 2r −x0 x1 ) ways. Now we can select the x2k−1 copies from the remaining 2r −x0 −x1 copies, having weight zero, in( 2r −x0 −x1 x2k−1 ) ways. This can be done in only one way because 2r −x0 −x1 = x2k−1. By Theorem 4.4, A2k−1 = (q − 1)(q − 2 k−1 + 1) and A2k−1−1 = (q − 1)2 k−1. Therefore A2k−1x0 = ( 2r x0 )( (q − 2k−1 + 1)(q − 1) )x0 and A(2k−1−1)x1 = ( 2r −x0 x1 )( 2k−1(q − 1) )x1. Since the Diophantine equation `(k) = `(k)0 x + ` (k) 1 y admits finite solutions and (x,y) varies over the set of all possible solutions, the number of codewords of weight `(k) = 2k−1x + (2k−1 − 1)y is given by A`(k) = ∑ (x,y) 0≤x≤2r 0≤y≤2r−x A2k−1xA(2k−1−1)y. This completes the proof. Theorem 4.7. Let q ≡ 3 (mod 4) and 3 ≤ k ≤ u. Then, the weight distribution of cyclic code Cr,k is given by A` = ∑ (x,y) `=2kx+(2k−2)y 0≤x≤2r,0≤y≤2r−x ( 2r x )( 2r −x y )( 2k−1(q − 1) )x+y(q − 2k−1 + 1 2k−1 )x . Proof. If c is any codeword of Cr,k, there exists a codeword c0 ∈ Nr,k such that c = (c0,−c0). Observe that, for any 3 ≤ k ≤ u and q ≡ 3 (mod 4), 2k+1|(q + 1). Now applying Theorem 4.6, we obtain the weight distribution of cyclic code Cr,k in the desired form. Note that the main result in [9] is a special case of Theorem 4.1 and Theorem 4.7. Example 4.8. Let q = 7 and k = 3. By Theorem 4.4, the weight distribution of a negacyclic [4, 2, 3]7 code N3 is A0 = 1, A3 = A4 = 24. Further, by Theorem 4.7, the weight distribution of a reducible cyclic [16, 4, 6]7 code is given by A` = ∑ (x,y) 0≤x≤2,0≤y≤2−x ( 2 x )( 2 −x y ) 24x+y with 8x + 6y = `. 9 M. Singh, S. Batra / J. Algebra Comb. Discrete Appl. 6(1) (2019) 1–11 Table 4.8 characterizes the type of possible weights ` = 8x + 6y of a reducible cyclic [16, 4, 6]7 code with the number of codewords A` of a given weight `. Table 4.8 ` | 0 6 8 12 14 16 (x,y) | (0, 0) (0, 1) (1, 0) (0, 2) (1, 1) (2, 0) A` | 1 48 48 576 1152 576 5. Concluding remarks The main contributions of this paper are the followings: • The construction of a class of linear codes of length 2n with 2l zeros over Fq and their weight distribution. These codes are reversible when l ≥ 1 and q ≡ 3 (mod 4). • The explicit form of the weight distribution in which the weights of codewords and the number of codewords of a given weight of these codes can be computed easily using a linear Diophantine equation and its solutions (see Example 4.8). • The construction of constant weight linear codes and two-weight negacyclic codes of length 2n, where 2n divides q + 1 and integer n ≥ 2. A class of linear codes with few weights are of special interest in authentication codes [2] and traceability schemes [6]. Many authors have worked on the problem of determining the weight distribution of reducible cyclic codes using mathematical tools, such as Gaussian periods and exponential sums. The values of the Gaussian periods, exponential sums are in general very hard to compute. It would be interesting to use the combinatorics approach of this paper for obtaining the weight distribution of cyclic codes of length m over Fq whose parity check polynomials are binomials or trinomials over Fq for the case m ∈{2nd,dn} for some odd integer d such that d|(q − 1) or d|(q + 1). Acknowledgment: The authors wish to thank the anonymous referees for their valuable comments that really helped us to improve the quality of this paper. References [1] E. R. Berlekamp, Algebraic Coding Theory, Revised Edition, World Scientific Publishing Co. Pte. Ltd., 2015. [2] C. Ding, D. R. Kohel, S. Ling, Secret–sharing with a class of ternary codes, Theor. Comput. Sci. 246(1–2) (2000) 285–298. [3] H. Q. Dinh, C. Li, Q. Yue, Recent progress on weight distributions of cyclic codes over finite fields, J. Algebra Comb. Discrete Struct. Appl. 2(1) (2015) 39–63. [4] K. Feng, J. Luo, Weight distribution of some reducible cyclic codes, Finite Fields Appl. 14(2) (2008) 390–409. [5] W. C. Huffman, V. Pless, Fundamentals of Error–Correcting Codes, Cambridge University Press, Cambridge, 2003. [6] A. Kathuria, S. K. Arora, S. Batra, On traceability property of equidistant codes, Discrete Math. 340(4) (2017) 713–721. [7] R. Lidl, H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge University Press, Cambridge, 1986. 10 https://mathscinet.ams.org/mathscinet-getitem?mr=3380755 https://mathscinet.ams.org/mathscinet-getitem?mr=3380755 https://doi.org/10.1016/S0304-3975(00)00207-3 https://doi.org/10.1016/S0304-3975(00)00207-3 http://dx.doi.org/10.13069/jacodesmath.36866 http://dx.doi.org/10.13069/jacodesmath.36866 https://doi.org/10.1016/j.ffa.2007.03.003 https://doi.org/10.1016/j.ffa.2007.03.003 https://mathscinet.ams.org/mathscinet-getitem?mr=1996953 https://mathscinet.ams.org/mathscinet-getitem?mr=1996953 https://doi.org/10.1016/j.disc.2016.12.009 https://doi.org/10.1016/j.disc.2016.12.009 https://mathscinet.ams.org/mathscinet-getitem?mr=860948 https://mathscinet.ams.org/mathscinet-getitem?mr=860948 M. Singh, S. Batra / J. Algebra Comb. Discrete Appl. 6(1) (2019) 1–11 [8] J. L. Massey, Reversible codes, Inform. Control 7(3) (1964) 369–380. [9] A. Sharma, G. K. Bakshi, M. Raka, The weight distributions of irreducible cyclic codes of length 2m, Finite Fields Appl. 13(4) (2007) 1086–1095. [10] M. Singh, S. Batra, Some special cyclic codes of length 2n, J. Algebra Appl. 16(1) (2017) 17 pages. [11] G. Vega, The weight distribution of an extended class of reducible cyclic codes, IEEE Trans. Inform. Theory, 58(7) (2012) 4862–4869. [12] M. Van Der Vlugt, Hasse–Davenport curves, Gauss sums and weight distributions of irreducible cyclic codes, J. Number Theory 55(2) (1995) 145–159. [13] Z. Wan, Lectures on Finite Fields and Galois Rings, World Scientific Publishing, Singapore, 2003. [14] J. Yang, M. Xiong, C. Ding, J. Luo, Weight distribution of a class of cyclic codes with arbitrary number of zeros, IEEE Trans. Inform. Theory 59(9) (2013) 5985–5993. [15] X. Zhu, Q. Yue, L. Hu, Weight distributions of cyclic codes of length lm, Finite Fields Appl. 31 (2015) 241–257. 11 https://doi.org/10.1016/S0019-9958(64)90438-3 https://doi.org/10.1016/j.ffa.2007.07.004 https://doi.org/10.1016/j.ffa.2007.07.004 https://doi.org/10.1142/S0219498817500025 https://doi.org/10.1109/TIT.2012.2193376 https://doi.org/10.1109/TIT.2012.2193376 https://doi.org/10.1006/jnth.1995.1133 https://doi.org/10.1006/jnth.1995.1133 https://doi.org/10.1142/5350 https://doi.org/10.1109/TIT.2013.2266731 https://doi.org/10.1109/TIT.2013.2266731 https://doi.org/10.1016/j.ffa.2014.07.005 https://doi.org/10.1016/j.ffa.2014.07.005 Introduction Preliminaries Negacyclic and cyclic codes Weight distributions Concluding remarks References