ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.645018 J. Algebra Comb. Discrete Appl. 7(1) • 21–33 Received: 30 June 2019 Accepted: 12 October 2019 Journal of Algebra Combinatorics Discrete Structures and Applications A class of constacyclic codes containing formally self-dual and isodual codes Research Article Manjit Singh Abstract: In this paper, we investigate a class of constacyclic codes which contains isodual codes and formally self-dual codes. Further, we introduce a recursive approach to obtain the explicit factorization of x2 m`n −µk ∈ Fq[x], where n,m are positive integers and µk is an element of order `k in Fq. Moreover, we give many examples of interesting isodual and formally self-dual constacyclic codes. 2010 MSC: 12E05, 94B05, 11T71 Keywords: Constacyclic codes, Weight distributions, Isodual codes, Formally self-dual codes 1. Introduction Let Fq be a finite field with q elements and n be a positive integer. An [n,k]q-linear code C is a k-dimensional subspace of Fnq . Usually, elements of C are referred to as codewords. The Hamming weight of a vector c ∈ Fnq , denoted by wt(c), is the number of nonzero coordinate entries in c. The Hamming distance between two vectors c and c′ in Fnq is defined as d(c,c ′) = wt(c− c′). The minimum distance dH(C) of a code C is the smallest distance between distinct codewords of the code C, i.e. dH(C) = min{d(c,c′) : c,c′ ∈ C}. For a linear code C, the minimum distance d = dH(C) is the same as the minimum weight of nonzero codewords of C. Let Ai denote the number of codewords with Hamming weight i in C, where 0 ≤ i ≤ n. The sequence (A0,A1, . . . ,An) is called the weight distribution of the code C. A linear code possessing minimum weight d has no nonzero codeword of weight less than d except zero codeword, that is, Ai = 0 for all 1 ≤ i ≤ d−1 and A0 = 1. The weight distribution is an important research object in coding theory. However, the problem of determining the weight distribution of linear codes is, in general, notoriously difficult. There are extremely few linear codes for which the weight distribution is known (see for example [7], [11], [17], [18] and the references therein). Manjit Singh; Department of Mathematics, Deenbandhu Chhotu Ram University of Science and Technology, Murthal-131039, Sonepat, India (email: manjitsingh.math@gmail.com). 21 http://orcid.org/0000-0003-3351-7287 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 For an [n,k]q-linear code C, the dual code C⊥ is also a linear code of length n and dimension n−k over Fq. The code C is self-orthogonal if C ⊆ C⊥ and self-dual if C = C⊥. The length n of a self-dual code is even and dimension is n/2. Further, if q is odd, then there is no self-dual cyclic code of length 2n over Fq and, if q is even, then there is a unique self-dual cyclic code of dimension 2n−1 of length 2n (see [16, Section 5]). Blackford [4] obtained the necessary and sufficient conditions for the existence of simple-root self-dual negacyclic codes. Bakshi and Raka [3] obtained all the self-dual negacyclic codes of length 2n over Fpm, where p is an odd prime and integer m ≥ 1. Dinh [8, Corollary 3.3] characterized all repeated-root self-dual negacyclic codes of length 2ps over Fpm. Remarkably note that constacyclic codes, except negacyclic codes or binary cyclic codes, do not include an important class of codes, that is, self-dual codes, however these codes contain formally self-dual and isodual codes. A linear code C is called isodual if C is equivalent to its dual code C⊥. A code C is called formally self-dual (f.s.d.) code if C and C⊥ have the same weight distribution. Automatically, self-dual codes are isodual codes and isodual codes are formally self-dual codes. Huffman and Pless [9] studied formally self-dual binary codes, however little work is known about formally self-dual codes over non-binary fields. These codes are important due to their applications in lattices [2], designs [10], code based cryptography, particularly in determining a minimal access set [14] and coding theory [5]. In this paper, motivated by the numerous practical applications of isodual codes and formally self- dual codes, we investigate a class of isodual and formally self-dual constacyclic codes which are permu- tation and monomially equivalent to each other. Further, we study the form of codewords, generator polynomials and the weight distribution of a class of µk- irreducible constacyclic codes of length 2`n over Fq, where ` is odd prime such that `k|(q−1) and µk is an element of order `k in F∗q \{1,−1}. This paper also presents a recursive factorization of x2 m`n −µk ∈ Fq[x], where integer m ≥ 1. The structure of the paper is as follows: Some background of constacyclic codes, the necessary notation and some known results are to be used presented in Section 2. In Section 3, the explicit factorization of x2` n −µk over Fq is obtained. Further, we introduce a recursive factorization of x2 m`n−µk. The form of codewords of all irreducible µk-constacyclic codes of length `n and 2`n are also obtained. Moreover, the weight distributions of these codes are determined by simply observing the weight of each message word. In Section 4, we construct a family of isodual and hence formally self-dual codes of length 2`n over Fq in a very special case. In the end of this section, we illustrate a class of isodual codes and formally self-dual codes by means of some examples. 2. Preliminaries Throughout this paper Fq denotes a finite field with q elements, where q is a power of a prime. For a fixed µ ∈ F∗q, where F∗q = Fq \{0}, a linear code C of length n over Fq is called a µ-constacyclic code if (c1,c2, . . . ,cn−1,µc0) ∈ C for each (c0,c1,c2, . . . ,cn−1) ∈ C. The code C is called cyclic if µ = 1 and negacyclic if µ = −1. If gcd(n,q) = 1, a µ-constacyclic code of length n is called simple-root code; otherwise it is called repeated-root code. Identifying the vector (a0,a1, . . . ,an−1) ∈ Fnq with the polynomial a0xn−1 + a1xn−2 + · · · + an−1 ∈ Fq[x], a simple-root µ- constacyclic code C can be represented as an ideal of the quotient ring Fq[x]/〈xn − µ〉. Each ideal in Fq[x]/〈xn −µ〉 is of the form 〈g(x)〉, where g(x) is a monic divisor of xn −µ in Fq[x]. The polynomial g(x) is known as the generator polynomial of the code C. A µ-constacyclic code C is called irreducible or minimal over Fq if h(x) = (xn −µ)/g(x) is an irreducible polynomial over Fq, where the polynomial h(x) is known as the parity check polynomial of the code C. The structure of constacyclic codes have been extensively studied and can be found in [1, 3, 5–8, 11]. For any two vectors a = (a1,a2, . . . ,an) and b = (b1,b2, . . . ,bn) in Fnq , the (Euclidean) inner product or dot product of a and b is defined as follows: 22 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 a ·b = n∑ i=1 aibi ∈ Fq, where ai,bi ∈ Fq for each i = 1,2, . . . ,n. The two vectors a and b are said to be orthogonal if a · b = 0. The dual code of C, denoted by C⊥, is defined as C⊥ = {b ∈ Fnq : a ·b = 0 for all a ∈ C}. For any polynomial f(x) = r∑ i=0 aix r−i, where a0 6= 0, over Fq, the reciprocal polynomial of f(x), denoted by f∗(x), is given by: f∗(x) = xrf(x−1) = r∑ i=0 aix i. For a µ-constacyclic [n,k]q-code C with parity check polynomial h(x) of degree k over Fq, the generator polynomial of C⊥ is given by h∗(x) over Fq. Note that h∗(x) divides xn −µ−1 over Fq if and only if h(x) divides xn −µ over Fq. Lemma 2.1. [8, Proposition 2.2] The dual of µ-constacyclic code is a µ−1-constacyclic code. Remark 2.2. The dual code C⊥ of a cyclic (negacyclic) code C is a cyclic (negacyclic) code, however, from Lemma 2.1, we notice that the dual code of µ-constacyclic code is not a µ-constacyclic code for every µ ∈ F∗q \{1,−1}. Definition 2.3 (see [13]). Two (n,M)-codes, where M is the size of the code, over Fq are equivalent if one can be obtained from the other by a combination of operations of the following type: (i) permutation of the n digits of the codewords; (ii) multiplication of the symbols appearing in a fixed position by a nonzero scalar. Lemma 2.4. [13, p.72] Equivalent linear codes have the same length, dimension and distance. The following result contains a criterion on irreducible non-linear binomials over Fq, which was given by Serret in 1866. Lemma 2.5. [12, Theorem 3.75] Let t ≥ 2 be an integer and a ∈ F∗q. Then the binomial xt − a is irreducible in Fq[x] if and only if the following two conditions are satisfied: (i) each prime factor of t divides the order e of a in F∗q, but does not divide (q −1)/e; (ii) q ≡ 1 (mod 4) if t ≡ 0 (mod 4). For this section and the rest of this work, we set the following notation: Let ` be a prime such that gcd(`,q) = 1 and v = max{k : `k|(q−1)}. Obviously, v = 0 if and only if ` - (q−1). Let µk be a primitive `kth root of unity in F∗q with µ0 = 1. For a fixed k, where 1 ≤ k ≤ v, we rephrase the factorization of x` n − µk over Fq in the following form: Lemma 2.6. [6, Theorem 4.1(ii)] Let n be a positive integer, gcd(q,`) = 1, r = min{n,v−k}, 1 ≤ k ≤ v, and v ≥ 2 if ` = 2. Then the irreducible factorization of x` n −µk is given by x` n −µk = `r∏ i=1 (x` n−r −µ` ki+1 k+r ), where µk+r is an element of order `k+r in F∗q. 23 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 In particular, by taking ` = 2 in Lemma 2.6, a factorization of x2 n −µk into the product of 2r factors is given as follows: Lemma 2.7. Let n be a positive integer, q be odd prime power, r = min{n,v−k} and 1 ≤ k ≤ v. Then a factorization of x2 n −µk over Fq is given by: x2 n −µk = 2r∏ i=1 (x2 n−r −µ2 ki+1 k+r ), where µk+r is an element of order 2k+r in F∗q. Further, if v ≥ 2, the factorization is irreducible over Fq, and if v = 1, the irreducible factorization of x2 n −µv is given in Lemma [16, Lemma 2.6]. In order to give a detailed explanation of our examples, we consider the following notions and results given in [15]. Let Sq = {a2 : a ∈ F∗q} and Oq = {a ∈ F∗q : |a| is odd}, where |a| denotes the order of a ∈ F∗q. Readily note that Oq and Sq are subgroups of the multiplicative group F∗q of the nonzero elements of Fq satisfying Oq ⊆Sq. Remarkably note that q ≡ 3 (mod 4) if and only if Oq = Sq. Lemma 2.8. [15, Theorem 4.2] Let q and t be odd primes such that q = 2t + 1. Then Sq is generated by 4. Lemma 2.9. [15, Theorem 4.4] Let q and t be odd primes such that q = 4t+1. Then the following holds: (i) Oq = 〈t〉 = {ti : 0 ≤ i ≤ t−1}. (ii) Sq = 〈4〉 and Oq = 〈16〉 for q > 13. 3. A class of irreducible constacyclic codes This section studies a class of µk- irreducible constacyclic code over Fq. The weight distribution of this class of codes is followed by the form of codewords without putting much effort. First of all, by using the same notation introduced in Lemma 2.6, let Ck,i denote a µk-constacyclic [`n,`n−r]q code with the parity check polynomial hk,i(x) = x` n−r −µ` ki+1 k+r . Then the generator polynomial gk,i(x) of Ck,i is given by: gk,i(x) = x` n −µk x` n−r −µ` ki+1 k+r . Theorem 3.1. Let n be a positive integer, ` be a prime such that gcd(`,q) = 1, `k|(q−1) for 1 ≤ k ≤ v and r = min{n,v −k}. Then the generator polynomial of Ck,i is given by: gk,i(x) = `r−1∑ u=0 µ (`ki+1)u k+r x `n−r(`r−u−1). Further, if a = (a0,a1, . . . ,a`n−r−1) ∈ F` n−r q be any message word, then Ck,i = {(a,aµ` ki+1 k+r , · · · ,aµ (`ki+1)(`r−1) k+r )}. Proof. Let r = min{n,v −k} and 1 ≤ k ≤ v. Since µk = µ (`ki+1)`r k+r for 1 ≤ i ≤ ` r, so x` n −µk = (x` n−r )` r −µ(` ki+1)`r k+r = (x `n−r −µ` ki+1 k+r ) (`r−1∑ u=0 µ (`ki+1)u k+r x `n−r(`r−u−1)). 24 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 Therefore, the generator polynomial gk,i(x) of a µk-constacyclic [`n,`n−r]q code Ck,i is given by: gk,i(x) = x` n −µk x` n−r −µ` ki+1 k+r = `r−1∑ u=0 µ (`ki+1)u k+r x `n−r(`r−u−1). Let a = (a0,a1, · · · ,a`n−r−1) ∈ F` n−r q be any message word. Then the corresponding message polynomial can be expressed as a(x) = `n−r−1∑ j=0 ajx `n−r−j−1. Therefore, the code polynomial of Ck,i is given as follows: a(x)gk,i(x) =  `n−r−1∑ j=0 ajx `n−r−j−1  (`r−1∑ u=0 µ (`ki+1)u k+r x `n−r(`r−u−1) ) = `r−1∑ u=0 µ (`ki+1)u k+r  `n−r−1∑ j=0 ajx `n−r−j−1  x`n−r(`r−u−1) = `r−1∑ u=0 `n−r−1∑ j=0 ajµ (`ki+1)u k+r x `n−r(`r−u)−j−1. Further, the uth component of codeword (c∗0,c ∗ 1, · · · ,c∗`r−1) is c∗u = (a0µ (`ki+1)u k+r ,a1µ (`ki+1)u k+r , · · · ,a`n−r−1µ (`ki+1)u k+r ). By using notation aθ for the vector (a0θ,a1θ, · · · ,a`n−r−1θ), where θ ∈ F∗q, the code Ck,i is given by: Ck,i = {(a,aµ` ki+1 k+r , · · · ,aµ (`ki+1)(`r−1) k+r ) : a ∈ F `n−r q }. This completes the proof. Remark 3.2. By Lemma 2.5, x` n−r − µ` ki+1 k+r is an irreducible factor of x `n − µk over Fq for every 1 ≤ i ≤ `r provided that v ≥ 2 if ` = 2. Let us consider the exceptional case v = 1 if ` = 2. Then k = 1, i = 1 and hence gk,i = 1. Thus, the code Ck,i becomes the whole space F2 n q , a trivial negacyclic code. For any n ≥ 2, x2 n + 1 is reducible over Fq, where q ≡ 3 (mod 4). Therefore, there are non-trivial negacyclic equivalent codes of length 2n. These negacyclic codes of length 2n over Fq and their weight distribution have been studied in [17, Theorem 4.6]. Lemma 3.3. For any 1 ≤ i,j ≤ `r, Ck,i is equivalent to Ck,j. Proof. There are `r irreducible codes Ck,i for 1 ≤ i ≤ `r for each fixed k, where 1 ≤ k ≤ v and r = min{n,v −k}. For every pair (i,j), where 1 ≤ i ≤ j ≤ `r, there exists a unique l = j − i (mod `r) such that µ` kj+1 k+r = µ l rµ `ki+1 k+r . Using the form of codewords of Ck,i and Ck,j given in Theorem 3.1, it follows that Ck,j = µj−ir Ck,i. Thus, the code Ck,j can be obtained form the code Ck,i by multiplying µj−ir and hence they are equivalent. By Lemma 3.3, in particular, the code Ck,i is equivalent to Ck,`r . For convenience point of view, we denote Ck,`r by Ck. 25 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 Theorem 3.4. By using the assumptions of Theorem 3.1, the weight distribution of µk-constacyclic [`n,`n−r]q code Ck is A`rj = ( `n−r j ) (q −1)j for 0 ≤ j ≤ `n−r. Proof. Direct from Theorem 3.1. Keeping in mind the previous notation, we now present the following result, which will be important in order to study of isodual and formally self-dual constacyclic codes that we are interested in. Theorem 3.5. Let q, `, r and k be as before, and additionally, let ` be odd. Then x2` n −µk = `r∏ i=1 (x` n−r ±θ` ki+1 k+r ), where θk+r is an element of order `k+rand θ2k = µk. Proof. For each 1 ≤ k ≤ v, the order of µk is `k. Clearly `k is odd and µ` k+1 k = µk. Let θk = µ (`k+1)/2 k for 1 ≤ k ≤ v. Then the order of θk is `k and θ2k = µk. It follows that x 2`n − µk = x2` k − θ2k = (x` k −θk)(x` k + θk). By Lemma 2.6, the factorization of x` n −θk over Fq is given by: x` n −θk = `r∏ i=1 (x` n−r −θ` ki+1 k+r ). By changing x to −x in the above factorization of x` n −θk, we obtain the factorization of x` n + θk over Fq as follows: x` n + θk = `r∏ i=1 (x` n−r + θ` ki+1 k+r ). This completes the proof. Theorem 3.6. Let q, `, r, k ` be as in Theorem 3.5, and additionally, let m be a positive integer. Then a recursive factorization of x2 m`n −µk over Fq is given by x2 m`n −µk = `r∏ i=1 (x2 m−1`n−r ±θ` ki+1 k+r ), where θk+r is an element of order `k+rand θ2k = µk. Proof. The required form of factorization follows directly by using the substitution x to x2 m−1 in Theorem 3.5. By Lemma 2.5, binomials x2 m−1`n ±θ` ki+1 k+r is reducible over Fq if and only if ∓θ `ki+1 k+r ∈Sq, where Sq is the set of all square elements in F∗q. For each 1 ≤ k ≤ v, in view of Theorem 3.5, there are 2`r distinct irreducible factors of x2` n −µk over Fq. Let C′k,i and C ′′ k,i be µk-constacyclic [2` n,`n−r]q codes such that C′k,i = 〈g ′ k,i(x)〉 and C ′′ k,i = 〈g ′′ k,i(x)〉, where 1 ≤ i ≤ `r, 1 ≤ k ≤ v and g′k,i(x) = x2` n −µk x` n−r −θ` ki+1 k+r = ( x` n −θk x` n−r −θ` ki+1 k+r ) (x` n + θk) and g′′k,i(x) = x2` n −µk x` n−r + θ` ki+1 k+r = ( x` n + θk x` n−r + θ` ki+1 k+r ) (x` n −θk). 26 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 Theorem 3.7. Let ` be a prime. 1 ≤ i ≤ `r and 1 ≤ k ≤ v. Then the generator polynomial g′k,i(x) of C′k,i is given by g′k,i(x) = `r−1∑ u=0 θ (`ki+1)u k+r x `n−r(`r−u−1)(x` n + θk). Further, if a ∈ F` n−r q is any message word, then C′k,i = {(a,aθ `ki+1 k+r , · · · ,aθ (`ki+1)(2`r−1) k+r )}. Proof. Using the argument of Theorem 3.1, we obtain x` n −θk = (x` n−r −θ` ki+1 k+r ) (`r−1∑ u=0 θ (`ki+1)u k+r x `n−r(`r−u−1)). It follows that x2` n −µk = (x` n −θk)(x` n + θk) = (x` n−r −θ` ki+1 k+r ) (`r−1∑ u=0 θ (`ki+1)u k+r x `n−r(`r−u−1))(x`n + θk) = (x` n−r −θ` ki+1 k+r ) (2`r−1∑ u=0 θ (`ki+1)u k+r x `n−r(2`r−u−1)). Thus the generator polynomial g′k,i(x) of a µk-constacyclic [2` n,`n−r]q code C′k,i is g′k,i(x) = x2` n −µk x` n−r −θ` ki+1 k+r = 2`r−1∑ u=0 θ (`ki+1)u k+r x `n−r(2`r−u−1). Let a = (a0,a1, · · · ,a`n−r−1) ∈ F` n−r q be any message word. Then the corresponding message polynomial can be expressed as a(x) = `n−r−1∑ j=0 ajx `n−r−j−1. It follows that the code polynomial of C′k,i is a(x)g′k,i(x) =  `n−r−1∑ j=0 ajx `n−r−j−1  (2`r−1∑ u=0 θ (`ki+1)u k+r x `n−r(2`r−u−1) ) = `r−1∑ u=0 θ (`ki+1)u k+r  `n−r−1∑ j=0 ajx `n−r−j−1  x`n−r(2`r−u−1) = 2`r−1∑ u=0 `n−r−1∑ j=0 ajθ (`ki+1)u k+r x `n−r(2`r−u)−j−1. Further, the uth component of codeword (c∗∗0 ,c ∗∗ 1 , · · · ,c∗∗`r−1) is c∗∗u = (a0θ (`ki+1)u k+r ,a1θ (`ki+1)u k+r , · · · ,a`n−r−1θ (`ki+1)u k+r ). If we denote aθ = (a0θ,a1θ, · · · ,a`n−r−1θ) for some θ ∈ F∗q, then c∗∗u = aθ (`ki+1)u k+r for each 0 ≤ u ≤ 2` r−1. Therefore 27 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 C′k,i = {(a,aθ `ki+1 k+r , · · · ,aθ (`ki+1)(2`r−1) k+r ) : a ∈ F `n−r q }. This completes the proof. Using the argument discussed in Lemma 3.3, observe that codes C′k,i and C ′′ k,i are equivalent to codes C′k,`r and C ′′ k,`r respectively. Denote C ′ k,`r by C ′ k, and C ′′ k,`r by C ′′ k . Theorem 3.8. With our notation and assumption, C′k is equivalent to C ′′ k . Proof. Let g′k(x) and g ′′ k(x) be generator polynomials of C ′ k and C ′′ k respectively. Now the equivalence of these codes is asserted by the following identity: g′′k(−x) = x2` n −µk −x`n−r + θk+r = − ( x2` n −µk x` n−r −θk+r ) = −g′k(x). Remark 3.9. For each fixed 1 ≤ k ≤ v and r = min{n,v −k}, there are 2`r irreducible codes C′k,i and C′′k,i for 1 ≤ i ≤ ` r. By Theorem 3.8, these codes are equivalent to C′k. By Lemma 2.4, since equivalent linear codes share the same weight distributions, so it is sufficient to determine the weight distribution of C′k, a µk-constacyclic code of length 2` n with the parity check polynomial x` n−r −θk+r. Theorem 3.10. Let ` be a prime, r = min{n,v − k} and 1 ≤ k ≤ v. Then the weight distribution of µk-constacyclic [2`n,`n−r]q code C′k is A2`rj = ( `n−r j ) (q −1)j for 0 ≤ j ≤ `n−r. Proof. From Theorem 3.7, the explicit form of codewords of C′k is given by: C′k = {(a,aθk+r, · · · ,aθ 2`r−1 k+r ) : a ∈ F `n−r q }. Now, the weight distribution of C′k follows directly by using the above form of the code. In end of this section, we present two examples as follows. Example 3.11. With our notation, let q = 163, ` = 3. Then v = 4, 1 ≤ k ≤ 3 and r = min{n,4−k}≥ 1. Since Sq(= Oq), a subgroup of order 81, has φ(3i) = 3i−1·2 elements of order 3i for 1 ≤ i ≤ 4, and 4 ∈Sq, so its order is either 9, 27 or 81. Using simple modular arithmetic, we obtain the order of 4 is 81. Thus one of the value of µ4 is 4. Take µ4 = −18 = 461, µ3 = 36 = 421, µ2 = 38 = 463, µ1 = 104 = 427. It is important to note that the choice of µ4 determines µi uniquely as follows µ4−i = µ3 i 4 for 0 ≤ i ≤ 3, however if we choose µ1 first, then µ2 has more than one choices, for example if µ1 = 104, then µ2 ∈ {40,38}. By Lemma 2.6, the factorization of x3 n −µk is given by: x3 n −µk = 3r∏ i=1 (x3 n−r −µ3 ki+1 k+r ). In view of Table 1, the explicit factorization of x81 −38 over F163 is given by: x81 −38 = (x9 + 32)(x9 + 75)(x9 + 79)(x9 + 68)(x9 −24) (x9 + 66)(x9 + 63)(x9 −51)(x9 + 18). Further, by Theorem 3.4, the weight distribution of 38-constacyclic [81,9,9]163 code C is A9j = ( 9 j ) (162)j for 0 ≤ j ≤ 9. 28 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 Table 1. Parameters of the factorization x3 n −µk; 1 ≤ k ≤ 3 n k r = min{n,4−k} µk degree coefficients in F∗163 3n−r {(−18)3 ki+1 : 1 ≤ i ≤ 3r} 5 1 3 104 9 {(36)i(−18) : 1 ≤ i ≤ 27} 5 2 2 38 27 {(38)i(−18) : 1 ≤ i ≤ 9} 5 3 1 36 81 {(104)i(−18) : 1 ≤ i ≤ 3} 4 1 3 104 3 {(36)i(−18) : 1 ≤ i ≤ 27} 4 2 2 38 9 {(38)i(−18) : 1 ≤ i ≤ 9} 4 3 1 36 27 {(104)i(−18) : 1 ≤ i ≤ 3} 3 1 3 104 1 {(36)i(−18) : 1 ≤ i ≤ 27} 3 2 2 38 3 {(38)i(−18) : 1 ≤ i ≤ 9} 3 3 1 36 9 {(104)i(−18) : 1 ≤ i ≤ 3} 2 1 2 104 3 {(36)i(−18) : 1 ≤ i ≤ 9} 2 2 2 38 1 {(38)i(−18) : 1 ≤ i ≤ 9} 2 3 1 36 3 {(104)i(−18) : 1 ≤ i ≤ 3} 1 1 1 104 1 {(36)i(−18) : 1 ≤ i ≤ 3} 1 2 1 38 1 {(38)i(−18) : 1 ≤ i ≤ 3} 1 3 1 36 1 {(104)i(−18) : 1 ≤ i ≤ 3} The weight distribution of Ck, where A3 n−r j = ( 3n−r j ) (162)j for 0 ≤ j ≤ 3n−r n k r = 4−k µk Weight No. of codewords of weight i i = 3rj Ai = A 3n−r j 5 1 3 104 27j A9j 5 2 2 38 9j A27j 5 3 1 36 3j A81j 4 1 3 104 27j A3j 4 2 2 38 9j A9j 4 3 1 36 3j A27j 3 1 3 104 27j A1j 3 2 2 38 9j A3j 3 3 1 36 3j A9j Table 1 provides the weight distributions of all irreducible µk-constacyclic codes of length 3n for n = 3,4,5 and 1 ≤ k ≤ 3 over F163. Example 3.12. With our notation, let q = 251, ` = 5. Then v = 3 and r = min{n,3 −k}. The set of all square elements Sq contains 125 elements as follows: φ(125) = 100 elements of order 125, φ(25) = 20 elements of order 25, 4 elements of order 5 and one element of order 1. Since 4,9 ∈ Sq are of order 25 and 125 respectively. Take µ3 = 9, thereby µ2 = µ53 = 64 and µ 5 2 = µ1 = −32 = 219. Now, µ2 = 64, µ3 = 9, θ2 = 6413 = −8 and θ3 = 913 = 88. By Theorem 3.5, the factorization of x2·5 n −µk for n ≥ 1 is given by: x2·5 n −µk = 5r∏ i=1 (x5 n−r ±θ5 ki+1 k+r ). Now for n = 2, k = 2, r = 1, µ2 = 64, θ3 = 88, the explicit factorization of x50 − 64 over F251 is given 29 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 by: x50 −64 = 5∏ i=1 (x5 ±8825i+1) = (x5 + 96)(x5 + 55)(x5 −60)(x5 −3)(x5 −88) (x5 −96)(x5 −55)(x5 + 60)(x5 + 3)(x5 + 88). Also by Theorem 3.10, the weight distribution of 64-constacyclic [50,5,10]251 code is A10j = ( 5 j ) (250)j for 0 ≤ j ≤ 5. Further, by Theorem 3.6, a reducible factorization of x100 −64 is given by: x100 −64 = 5∏ i=1 (x10 ±8825i+1) = (x10 + 96)(x10 + 55)(x10 −60)(x10 −3)(x10 −88) (x10 −96)(x10 −55)(x10 + 60)(x10 + 3)(x10 + 88). Since −1 /∈Sq and 88 ∈Sq, so there are 5 reducible binomials, for example x10−88 = (x5−313)(x5+313) = (x5 + 29)(x5 − 29), and the remaining 5 are irreducible over Fq. Moreover all binomials x10 − 8825i+1 for 1 ≤ i ≤ 5 are reducible over Fq such as x10 − 8825i+1 = (x5 − 313(25i+1))(x5 + 313(25i+1)) = (x5 + 2925i+1)(x5 −2925i+1) for 1 ≤ i ≤ 5. This process can be carried forward for a reducible factorization of x200 −64 from the explicit factorization of x100 −64 with 15 irreducible factors over Fq. 4. Formally self-dual and isodual codes A code is formally self-dual (f.s.d.) if the code and its dual have the same weight distribution. A code is isodual if it is equivalent to its dual. Since two equivalent codes have the same weight distribution, so the class of formally self-dual codes automatically contains the class of isodual codes, however, a formally self-dual code need not be isodual (see [9, p. 378]). In this section, we construct isodual and formally self-dual linear codes. Theorem 4.1. Let ` be an odd prime such that `|(q−1), but `2 - (q−1) and n be a positive integer. Let η be a primitive `th root of unity in F∗q. Then there exists an element θ = η (`+1)/2 ∈ F∗q of the order ` such that x2` n −η = (x` n −θ)(x` n + θ). If C1 = 〈x` n + θ)〉 and C2 = 〈x` n −θ)〉. Then C1 = {(a,θa)} , C⊥1 = {(θa,−a)}, C2 = {(a,−θa) and C⊥2 = {(θa,a) where a = (a0,a1, . . . ,a`n−1) ∈ F` n q . Further, C1 and C2 are isodual codes, and Ci, C⊥i for i = 1,2 are formally self-dual codes. Proof. On substituting v = 1, r = 0, k = 1, η = µk+r = µ1 in Theorem 3.5, the factorization of x2` n −µk reduces in the following form: x2` n −η = x2` n −η`+1 = (x` n −θ)(x` n + θ), where θ = η(`+1)/2. Clearly the order of θ ∈ F∗q is `. Further, by Theorem 3.7, we find the desired form of C1 and C2. Furthermore, C⊥1 is a η −1-constacyclic code. Since x2` n −η−1 = 1 η (θx` n − 1)(θx` n + 1) and C1 is generated by x` n + θ, so C⊥1 = 〈θx` n −1〉 = 〈x` n −θ−1〉. Similarly C⊥2 = 〈θx` n + 1〉 = 〈x` n + θ−1〉. Obviously, C1, C2, C⊥1 and C ⊥ 2 are all equivalent via a permutation of coordinates and multiplying certain coordinates by constants. Since the relation of equivalence of codes is an equivalence relation, so C1 is equivalent to C⊥1 and C2 is equivalent to C ⊥ 2 . This proves that C1 and C2 are isodual codes. Further, by Theorem 3.10, the weight distribution of Ci and its dual C⊥i is A2j = ( ` j ) (q − 1)j, where 0 ≤ j ≤ ` for i = 1,2. Therefore C1 and C2 are formally self-dual codes. 30 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 Remark 4.2. In view of Theorem 3.5, θk ∈ F∗q presents one of the solution of the equation x2 = µk. Obviously, −θk is another solution of this equation. Since the order of θk is `k, then θk is a square element in F∗q. Note that −1 is a square in Fq if and only if 4|(q − 1). In fact, the order of −θk is 2`k when q ≡ 3 (mod 4) and, `k when q ≡ 1 (mod 4). From Theorem 3.6, a reducible factorization of x4` n −µk over Fq is given recursively as follows: x4` n −µk = `r∏ i=1 (x2` n−r ±θ` ki+1 k+r ). (i) If q ≡ 1 (mod 4), for each i, since ±θ` ki+1 k+r is a square element of order ` k+r, where r and k are as usual, and hence by applying Theorem 3.5, one has the explicit factorization of x2` n−r ± θ` ki+1 k+r into the product of 2`r1 + 2`r1 irreducible factors over Fq, where r1 = min{n − r,v − k}. In this case when q ≡ 1 (mod 8), this process of factorization allows us to select the generator polynomials of isodual and formally self-dual codes of length 8`n and dimension 4`n over a finite field from the given factorization of x8` n −µk ∈ Fq[x] (see Example 4.6). (ii) If q ≡ 3 (mod 4), then −1 /∈ Sq, and one of the element ±θ` ki+1 k+r is a square element and hence either of the binomial x2` n−r ±θ` ki+1 k+r can be expressed as a product of 2` r1 irreducible factors over Fq, where r1 = min{n − r,v − k}. In this case, the generator polynomials of isodual codes and formally self-dual codes are given by Theorem 4.1. 4.1. Worked examples The following are examples of isodual codes and formally self-dual codes by means of Theorem 4.1 and Theorem 3.6. Example 4.3. For q = 13, we have ` = 3, v = 1, r = 0. By Lemma 2.9, the order of 3 is 3 modulo 13, it follows that µ1 = 3 θ1 = 9. By Lemma 2.5, x3 − 3 is an irreducible over F13. By Theorem 3.5, x6 −3 = (x3 −9)(x3 + 9). Let C1 = 〈x3 −9〉 = {(a0,a1,a2,4a0,4a1,4a2) : a0,a1,a2 ∈ F13}. Then C⊥1 is 9-constacyclic code and is given by: C⊥1 = 〈x3 + 3〉 = {(a0,a1,a2,3a0,3a1,3a2) : a0,a1,a2 ∈ F13}. The weight distribution of C1 and C⊥1 is A2j = ( 3 j ) (12)j for 0 ≤ j ≤ 3. Thus the weight distribution of this code is same as the weight of the code C1. Denote by C2 = 〈x3 +9〉, C3 = 〈x3−3〉 and C4 = 〈x3 +3〉. Then these codes are formally self-dual codes, while pairs (C1,C4) and (C2,C3) are of isodual codes. Moreover, using Theorem 3.6, we obtain x12 −3 = (x3 −3)(x3 + 3)(x3 −2)(x3 + 2). Now, let C = 〈(x3 + 10)(x3 + 11)〉, then C⊥ = 〈(x3 + 4)(x3 + 6)〉. Here C and C⊥ are respectively, a 3-constacyclic [12,6,3]13-code and a 9-constacyclic [12,6,3]13-code. It is quite easy to see that these codes are equivalent and hence C is isodual. Example 4.4. For q = 11, we obtain ` = 5, v = 1, r = 0. By Lemma 2.8, µ1 ∈ 〈4〉 is an element of order 5. All φ(5) = 4 elements of order 5 are given in {3,4,5,9}. Consider µ1 = 3. By Lemma 2.5, x5−3 is irreducible and x10−3 is reducible over F11. Note that x10−3 = x10−36 = (x5−33)(x5 +33) = (x5 − 5)(x5 + 5). By Theorem 3.6, x20 − 3 = (x10 − 5)(x10 + 5). Since 42 = 5, so θ1 = 4, x10 − 5 = (x5 − 4)(x5 + 4) and hence x20 − 3 = (x5 − 4)(x5 + 4)(x10 − 6). Let C = 〈x5 + 5〉 = {(a,5a) : a ∈ F511}. 31 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 Then C is a 3-constacyclic code of length 10 over F11 with the parity check polynomial x5 − 5. Then C⊥ = 〈5x5 −1〉 = 〈x5 + 2〉 = {(a,2a) : a ∈ F511} is a 4-constacyclic code of length 10 over F11. Since C⊥ is equivalent to C, so C is isodual and hence formally self-dual codes. Example 4.5. For q = 29, we obtain ` = 7, v = 1, r = 0. By Lemma 2.9, 7 is an element of order 7 modulo 29. Take µ1 = 7. By Lemma 2.5, x7 − 7 is irreducible and x14 − 7 is reducible over F29. Note that x14 −7 = x14 −78 = (x7 −74)(x7 + 74) = (x7 + 6)(x7 −6). Let C = 〈x7 −6〉 = {(a,−6a) : a ∈ F729}. Then C is a 7-constacyclic code of length 14 over F29 with the parity check polynomial x7 + 6. Then C⊥ = 〈6x7 + 1〉 = 〈x7 + 5〉 = {(a,5a) : a ∈ F729} is a 4-constacyclic code of length 14 over F29. Since C⊥ = 4C and hence C is isodual and hence formally self-dual codes. By Theorem 3.6, x28 − 7 = (x14 − 6)(x14 − 23) = (x7 ± 8)(x7 ± 9) and x28 − 25 = (x14 − 5)(x14 + 5) = (x7 ± 11)(x7 ± 13). Now let C1 = 〈(x7 − 8)(x7 + 9)〉,C⊥1 = 〈(x7 − 11)(x7 + 13)〉,C2 = 〈(x7 − 8)(x7 − 9)〉,C⊥2 = 〈(x7 − 11)(x7 − 13)〉, C3 = 〈(x7 +8)(x7−9)〉, C⊥3 = 〈(x7 +11)(x7−13)〉 and C4 = 〈(x7 +8)(x7 +9)〉, C⊥4 = 〈(x7 +11)(x7 +13)〉 can be used for describing equivalent isodual and formally self-dual 23-constacyclic codes. Example 4.6. For q = 41, we obtain ` = 5, v = 1, r = 0. Note that 16 is an element of order 5 modulo 41. Take µ1 = 16, we have µ −1 1 = 18. By Lemma 2.5, x 5 − 16 is irreducible and x40 − 16 is reducible over F41. The factorization of x40 −16 over F41 is given by x40 −16 = (x5 ±17)(x5 ±11)(x5 ±10)(x5 ±8). Also x40 −18 = (x5 ±12)(x5 ±15)(x5 ±4)(x5 ±5). Let C = 〈f1(x)f2(x)g1(x)g2(x)〉, where fi(x) = x5 −ηi and gi(x) = x5 +ηi, where ηi ∈{8,10,11,17} and 1 ≤ i ≤ 2. Then C is a 16-constacyclic code of length 40 over F41 and Then C⊥ = 〈 x40 −18 f∗1 (x)f ∗ 2 (x)g ∗ 1(x)g ∗ 2(x) 〉 is an 18-constacyclic code of length 40 over F41. This represents a class of isodual codes. Acknowledgment: The author would like to sincerely thank the anonymous referees who gave many helpful comments and suggestions to create an improved version. References [1] N. Aydin, I. Siap, D. K. Ray–Chaudhuri, The structure of 1–generator quasi–twisted codes and new linear codes, Des. Codes Cryptogr. 24(3) (2001) 313–326. [2] C. Bachoc, T. A. Gulliver, M. Harada, Isodual codes over Z2k and isodual lattices, J. Algebra Combin. 12(3) (2000) 223–240. [3] G. K. Bakshi, M. Raka, A class of constacyclic codes over a finite field, Finite Field Appl. 18(2) (2012) 362–377. [4] T. Blackford, Negacyclic duadic codes, Finite Fields Appl. 14(4) (2008) 930–943. [5] T. Blackford, Isodual constacyclic codes, Finite Fields Appl. 24 (2013) 29–44. [6] B. Chen, Y. Fan, L. Lin, H. Liu, Constacyclic codes over finite fields, Finite Fields Appl. 18(6) (2012) 1217–1231. [7] 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. [8] H. Q. Dinh, Repeated–root constacyclic codes of length 2ps, Finite Fields Appl. 18(1) (2012) 133–143. [9] W. C. Huffman, V. Pless, Fundamentals of Error–Correcting Codes, Cambridge University Press, 2003. 32 https://doi.org/10.1023/A:1011283523000 https://doi.org/10.1023/A:1011283523000 https://doi.org/10.1023/A:1011259823212 https://doi.org/10.1023/A:1011259823212 https://doi.org/10.1016/j.ffa.2011.09.005 https://doi.org/10.1016/j.ffa.2011.09.005 https://doi.org/10.1016/j.ffa.2008.05.004 https://doi.org/10.1016/j.ffa.2013.05.005 https://doi.org/10.1016/j.ffa.2012.10.001 https://doi.org/10.1016/j.ffa.2012.10.001 https://doi.org/10.13069/jacodesmath.36866 https://doi.org/10.13069/jacodesmath.36866 https://doi.org/10.1016/j.ffa.2011.07.003 M. Singh / J. Algebra Comb. Discrete Appl. 7(1) (2020) 21–33 [10] G. T. Kennedy, V. Pless, On designs and formally self–dual codes, Des. Codes Cryptogr. 4(1) (1994) 43–55. [11] F. Li, Q. Yue, The primitive idempotents and weight distributions of irreducible constacyclic codes, Des. Codes Cryptogr. 86(4) (2018) 771–784. [12] R. Lidl, H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge University Press, 1986. [13] S. Ling, C. Xing, Coding Theory: A First Course, Cambridge University Press, 2004. [14] J. L. Massey, Minimal codewords and secret sharing, Proc. 6th Joint Swedish–Russian Workshop on Information Theory, Mölle, Sweden, (1993) 276–279. [15] M. Singh, Some subgroups of F∗q and explicit factors of x 2nd −1 ∈ Fq[x], Transactions on Combina- torics (2019) doi: 10.22108/TOC.2019.114742.1612. [16] M. Singh, S. Batra, Some special cyclic codes of length 2n, J. Algebra Appl. 16(1) (2017) 17 pages. [17] M. Singh, S. Batra, Weight distribution of a class of cyclic codes of length 2n, J. Algebra Comb. Discrete Appl. 6(1) (2018) 1–11. [18] X. Zhu, Q. Yue, L. Hu, Weight distributions of cyclic codes of length lm, Finite Fields Appl. 31 (2015) 241–257. 33 https://doi.org/10.1007/BF01388559 https://doi.org/10.1007/BF01388559 https://doi.org/10.1007/s10623-017-0356-2 https://doi.org/10.1007/s10623-017-0356-2 http://dx.doi.org/10.22108/TOC.2019.114742.1612 http://dx.doi.org/10.22108/TOC.2019.114742.1612 https://doi.org/10.1142/S0219498817500025 http://dx.doi.org/10.13069/jacodesmath.505364 http://dx.doi.org/10.13069/jacodesmath.505364 https://doi.org/10.1016/j.ffa.2014.07.005 https://doi.org/10.1016/j.ffa.2014.07.005 Introduction Preliminaries A class of irreducible constacyclic codes Formally self-dual and isodual codes References