JACODESMATH / ISSN 2148-838X J. Algebra Comb. Discrete Appl. 1(1) • 1-12 Received: 21 April 2014; Accepted: 26 August 2014 DOI 10.13069/jacodesmath.31486 Journal of Algebra Combinatorics Discrete Structures and Applications Cyclic and constacyclic codes over a non-chain ring Research Article Aysegul Bayram1∗, Irfan Siap1∗∗ 1. Yildiz Technical University, Faculty of Arts and Science, Department of Mathematics, Istanbul, Turkey Abstract: In this study, we consider linear and especially cyclic codes over the non-chain ring Zp[v]/〈vp − v〉 where p is a prime. This is a generalization of the case p = 3. Further, in this work the structure of constacyclic codes are studied as well. This study takes advantage mainly from a Gray map which preserves the distance between codes over this ring and p-ary codes and moreover this map enlightens the structure of these codes. Furthermore, a MacWilliams type identity is presented together with some illustrative examples. 2010 MSC: 94B05, 94B15, 11T71 Keywords: Non-chain rings, Linear codes, Cyclic codes, Constacycllic codes, MacWilliams type identity 1. Introduction Recently, codes over some special finite rings especially chain rings have been studied. More recently, codes over finite non-chain rings have been also considered. However, the study on non-chain rings has proved to be challenging due to the algebraic structure of these rings which does not allow to give a nice and compact presentation of linear codes over these rings. Study on codes over such rings or rings in general is motivated by the existence of some special maps called Gray maps whose images give codes over fields. The existence of such maps is not guaranteed in general. First substantial paper which relates codes over the quaternary ring Z4 to binary codes is studied initially in [9] where a Gray map is presented. Some important results of this study are the generation of some optimal non-binary codes such as Kerdock, Preparata codes via a Gray map. This particular work motivated the researchers and since then codes over rings have been of great importance to the study. We can list some related studies on this subject that study codes over chain rings such as the ring of four elements F2 + uF2, the ring of 8 elements F2 + uF2 + u2F2, and a more general chain ring F2[u]/〈us〉 are presented in [2–4, 6, 11, 13]. Some Euclidean and Hermitian self-dual codes over the ring F2[v]/〈v2 −v〉 are related to binary self-dual and formally self-dual codes and optimal self-dual binary codes obtained in [5] which inspired the original work of the authors [4]. Gao studied a new generalization of [4] over Fp under the restriction v3 −v in ∗ E-mail: abayram@yildiz.edu.tr, aaysegulbayram@gmail.com ∗∗ E-mail: isiap@yildiz.edu.tr 1 Cyclic and constacyclic codes over a non-chain ring [8]. Here, the authors mainly further generalize the results in [4] to codes over the ring Zp[v]/〈vp − v〉 and study algebraic structure, that is, its ideals, units, etc. Furthermore, the authors also determine the algebraic structure of linear, cyclic and constacyclic codes over this generalized ring by means of a Gray map. In this work, we consider codes over the non-chain ring Zp[v]/〈vp − v〉 = {a0 + a1v + ... + ap−1v p−1|a0,a1, ...,ap−1 ∈ Zp and vp = v}. In the first section we analyze the structure of the ring and investigate its algebraic properties. Furthermore, linear codes over Zp[v]/〈vp − v〉 are taken into account and the generator matrices of their Gray images are examined. Then, the dual of a linear code is defined by defining an inner product and relation between linear code and further its dual is presented. The relation between cyclic codes and their duals over Zp[v]/〈vp −v〉 are also studied. Finally, a class of constacyclic codes have been introduced and dual codes of them are studied. 2. Preliminaries The ring Rp = Zp[v]/〈vp − v〉 has pp elements where p is a prime number. In order to study the structure of this ring, we introduce a linear map φ which we refer as a Gray map in the following way: φ :Rp = Zp[v]/〈vp −v〉→ Zpp α = a0 + a1v + ... + ap−1v p−1 → φ(α) = φ(a0 + a1v + ... + ap−1vp−1) = (α(0),α(1), ...,α(p−1)) (1) where α(i) = a0 + a1i + ... + ap−1ip−1 (mod p) for all i ∈ {0,1, ...,p− 1}.. Indeed, this map is basically the natural one that gives the Chinese Remainder Theorem and hence this map relates the rings Rp and Zpp. Due to the fact that the map φ is a ring isomorphism, we have Rp ∼= Zp[v]/〈v〉⊕Zp[v]/〈v −1〉⊕ ·· ·⊕Zp[v]/〈v − (p−1)〉∼= Zpp. It is not easy to find the structure of lattices of ideals of non-chain rings in general. Here by using the Gray map introduced above, we are able to give the structure of ideals of Rp and further count the number of ideals as follows: Lemma 2.1. Rp has exactly 2p ideals. Proof. Since Zp is a field then its ideals are exactly the zero ideal and Zp itself, then the number of ideals of Zpp is the product of the number of the trivial ideals. Therefore the number of ideals of Rp is 2p. Example 2.2. Consider the ring R5. Prior to listing the ideals of R5 we introduce a short notation such as 11010 which means that the ideal in Z55 which is composed by the zero ideals in its third and fifth coordinates and the all ring in the rest. Also, we note that a1a20a40 where ai 6= 0 for i ∈ {1,2,4} gives the same ideals since the nonzero elements in the field generate the all field. Therefore, the ideals that generate the all ring have 55 = 3125 elements and naturally the elements that generate these ideals are units of R5: • 11111 → 〈1〉 = 〈2〉 = 〈3〉 = 〈4〉 = 〈2 + v2〉 = ... = 〈1 + v + 2v2〉. The maximal ideals with 625 elements: • 11110 → 〈1 +v〉 = 〈2 + 2v〉 = 〈3 + 3v〉 = 〈4 + 4v〉 = 〈1 + 2v +v2〉 = ... = 〈4 + 3v + 4v2 + 4v3 + 4v4〉. • 11101 → 〈2 +v〉 = 〈4 + 2v〉 = 〈1 + 3v〉 = 〈3 + 4v〉 = 〈4 + 4v +v2〉 = ... = 〈3 + 3v + 4v2 + 4v3 + 4v4〉. • 11011 → 〈3 + v〉 = 〈1 + 2v〉 = 〈4 + 3v〉 = 〈2 + 4v〉 = 〈4 + v + v2〉 = ... = 〈2 + 3v + 4v2 + 4v3 + 4v4〉. • 10111 → 〈4 +v〉 = 〈3 + 2v〉 = 〈2 + 3v〉 = 〈1 + 4v〉 = 〈1 + 3v +v2〉 = ... = 〈4 + 4v + 4v2 + 4v3 + 4v4〉. • ... 2 A. Bayram, I. Siap • 11100→〈2+3v+v2〉 = 〈4+v+2v2〉 = 〈1+4v+3v2〉 = 〈3+2v+4v2〉 = ... = 〈1+3v+2v2+4v3+4v4〉. The ideals with 25 elements: • 00011 → 〈2v + 2v2 + (v3)〉 = 〈4v + 4v2 + 2v3〉 = 〈v + v2 + 3v3〉 = ... = 〈1 + 3v + 2v2 + 4v3 + 4v4〉. • 00101 →〈3v+v2+v3〉 = 〈v+2v2+2v3〉 = 〈4v+3v2+3v3〉 = 〈2v+4v2+4v3〉 = ... = 〈2v2+4v3+4v4〉. • ... • 11000 →〈1+v+v2+v3〉 = 〈1+2v+2v2+2v3〉 = 〈3+3v+3v2+3v3〉 = ... = 〈4+3v+3v2+3v3+4v4〉. The ideals with 5 elements: • 10000 → 〈4 + v4〉 = 〈3 + 2v4〉 = 〈2 + 3v4〉 = 〈1 + 4v4〉. • 01000 → 〈v+v2 +v3 +v4〉 = 〈2v+2v2 +2v3 +2v4〉 = 〈3v+3v2 +3v3 +3v4〉 = 〈4v+4v2 +4v3 +4v4〉. • 00100 → 〈3v+4v2 +2v3 +v4〉 = 〈v+3v2 +4v3 +2v4〉 = 〈4v+2v2 +v3 +3v4〉 = 〈2v+v2 +3v3 +4v4〉. • 00010 → 〈2v+4v2 +3v3 +v4〉 = 〈4v+3v2 +v3 +2v4〉 = 〈v+2v2 +4v3 +3v4〉 = 〈3v+v2 +2v3 +4v4〉. • 00001 → 〈4v+v2 +4v3 +v4〉 = 〈3v+2v2 +3v3 +2v4〉 = 〈2v+3v2 +2v3 +3v4〉 = 〈v+4v2 +v3 +4v4〉. and the zero ideal: • 00000 → 〈0〉. Let R be a ring and a ∈ R. If a is nonzero then its Hamming weight denoted by w(a) equals to 1 otherwise it is equal to 0. This is generalized to an n-tuple such that if a = (a1,a2, . . . ,an) ∈ Rn, then the Hamming weight of a is defined by w(a) = ∑n i=1 w(ai). The Hamming distance between two n-tuples is d(x,y) = w(x−y) where x,y ∈ Rn. It is well known that the Hamming distance is a metric on Rn. It is possible to characterize the unit elements of Rp and further give the number of elements in an ideal by considering the definition of φ together with its properties. Lemma 2.3. Suppose that I = 〈α〉 where α = a0 + a1v + . . . + ap−1vp−1 ∈ Rp. |I| = p ∑p−1 i=0 w(α(i)). Especially, if α(i) 6= 0 for all i, Then α is a unit in Rp and vice versa. Since the map φ is a ring isomorphism, the inverse map of φ denoted by φ−1 : Zpp → Rp exists. In the following example we present the inverse map explicitly: Example 2.4. The inverse map is defined by φ−1 : Z55 → R5 (k,l,m,n,t) → k+(4l+2m+3n+t)v+(4l+m+n+4t)v2 +(4l+3m+2n+t)v3 +4(k+l+m+n+t)v4. Definition 2.5. (Gray weight) Let α = a0 + a1v + ... + ap−1vp−1 ∈ Rp. Then wG(α) = w(φ(α)) (2) is called the Gray weight of α. The Gray distance between two elements α and β of Rp is described by dG(α,β) = w(φ(α)−φ(β)) which also happens to be a linear distance preserving map from (Rnp ,dG) to (Z pn p ,d). Example 2.6. Let p = 7. If α = 1 + v + 5v2 + 5v3 and β = 6v + 4v2 + 5v3, then wG(α) = w(φ(1 + v + 5v2 + 5v3)) = w(1,5,0,2,6,0,0) = 4 and wG(β) = w(φ(6v + 4v2 + 5v3)) = w(0,1,5,0,2,6,0) = 4 hence dG(α,β) = w(φ(α) − φ(β)) = w((1,5,0,2,6,0,0) − (0,1,5,0,2,6,0)) = w((1,4,2,2,4,1,0)) = w(1 + 2v + v2) = 6. Definition 2.7. Let a = (a1,a2, ..,ap) ∈ Zpp. Then, supp(a) = {i|ai 6= 0}⊆{1,2, ...,p}. 3 Cyclic and constacyclic codes over a non-chain ring We can easily check that: • If supp(φ(α)) = supp(φ(β)) then wG(α) = wG(β) where α,β ∈ Rp. • Assume that 〈α〉 and 〈β〉 are two ideals in Rp. Then, supp(φ(α)) = supp(φ(β)) if and only if 〈α〉 = 〈β〉. Therefore, Rp is a principal ideal ring, that is, all ideals in Rp are generated by a single element of Rp similar to the special case p = 3 [4] . Theorem 2.8. If I = 〈α1,α2, . . . ,αs〉 is a finitely generated ideal of Rp, then I = 〈β〉 for some β ∈ Rp where supp(φ(β)) = ⋃s i=1 supp(φ(αi)). Example 2.9. Let I = 〈α1,α2〉 where α1 = 3v + v2 + v3 and α2 = 1 + 3v + 3v2 + 3v3 + 2v4 ∈ R5. Since supp(φ(α1)) = supp(φ(3v + v 2 + v3)) = supp((0,0,3,0,2)) = {3,5} and supp(φ(α2)) = supp(φ(1 + 3v + 3v 2 + 3v3 + 2v4)) = supp((1,2,0,0,0)) = {1,2} supp(φ(β)) = 2⋃ i=1 supp(φ(αi)) = {1,2,3,5}, then β can be selected as 4 + 2v + 3v2 + 3v3 + 2v4 which generates a maximal ideal in R5. The units and the elements which generate the maximal ideals in Rp can be classified by means of their Gray images: Lemma 2.10. Let α ∈ Rp. The follows hold: i) supp(φ(α)) = {1, ...,p} if and only if α is a unit. Hence, Rp has exactly (p−1)p units . ii) Suppose I = 〈α〉. Then, | supp(φ(α))| = p−1, if and only if I is maximal. 3. Linear Codes over Rp A minimal generating set is comprised for all linear codes by a set of linearly independent and spanning vectors called basis for codes over fields. However, in the case for codes over rings, this is a challenging problem and in most cases impossible since we do not have basis in general for modules. In [2] and in [3], authors gave a basis or a minimal spanning set for the codes of even length over Z2 + uZ2 and Z2 + uZ2 + u2Z2 + · · ·+ uk−1Z2, respectively. These are all chain rings, that is, the set of all ideals is a chain under set-theoretic inclusion. Since Rp is not a chain ring, we can not get a generating matrix, easily. To overcome this problem in linear code case some special definitions (modular dependence) and cases of codes over rings are presented in [12] and in [15]. Here, based on the Gray image of the code, the generator matrix of the image code is presented and some results are obtained: Theorem 3.1. Assume that the set {g1,g2, . . . ,gk}⊂ Rnp is a generating set of a linear code C over Rp of length n where gi = (gi1,gi2, . . . ,gin). Then, the matrix 4 A. Bayram, I. Siap φ(G) =   φ(g11) φ(g12) · · · φ(g1n) φ(vg11) φ(vg12) · · · φ(vg1n) φ(v2g11) φ(v 2g12) · · · φ(v2g1n) ... ... ... φ(vp−1g11) φ(v p−1g12) · · · φ(vp−1g1n) ... ... ... φ(gk1) φ(gk2) · · · φ(gkn) φ(vgk1) φ(vgk2) · · · φ(vgkn) φ(v2gk1) φ(v 2gk2) · · · φ(v2gkn) ... ... ... φ(vp−1gk1) φ(v p−1gk2) · · · φ(vp−1gkn   generates φ(C). Example 3.2. Let p = 5 and suppose that G = [ 2v + 4v2 + 3v3 + v4 0 0 4v + v2 + 4v3 + v4 ] is a generator matrix of C of length 2 over R5 = Z5[v]/〈v5 −v〉. Then φ(G) =   00000 00000 00000 00000 00000 00000 00000 00000 00000 00004 00000 00000 00000 00000 00000 00000 00040 00000 00000 00000   . Hence φ(G) is a generator matrix of φ(C), with length 10, dimension 2 and size 52 = 25. Another simple and compact way to represent the structure of a generator matrix of φ(G) is given below. Let α = g0 + g1v + ... + gp−1vp−1 ∈ Rp and α(i) = g0 + g1i + ... + gp−1ip−1 (mod p). φ(α) = φ(g0 + g1v + ... + gp−1v p−1) = (α(0),α(1), ...,α(p−1)). Alternatively, after some row operations the generator matrix is then equivalent to a block matrix with blocks (Gij)p×p = diag(αij(0),αij(1), . . . ,αij(p−1)). As mentioned above, we again emphasize that it is a difficult problem to determine the minimal independent sets that generate a linear code over Rp in general due to the fact that Rp is not a chain ring. However, one can adopt a similar approach as presented in both [12] and [15] to capture the size of linear codes over R for some special cases. Definition 3.3. A set {g1,g2, . . . ,gk} ⊂ Rnp is called a minimal independent generating set for a code C, if {φ(g1),φ(vg1), . . . ,φ(vp−1g1),φ(g2),φ(vg2), . . . ,φ(vp−1g2), . . . ,φ(gk),φ(vgk), . . . ,φ(vp−1gk)}⊂ Zpnp is a Zp-linearly independent set. 5 Cyclic and constacyclic codes over a non-chain ring Now, having this definition at hand one can determine the size of a code with a generating set which is Zp-linearly independent: Lemma 3.4. If C = 〈{g1,g2, . . . ,gk}〉 where the set {g1,g2, . . . ,gk} ⊂ Rnp is a minimal independent generating set, then |C| = ppk. 3.1. The Dual Code In this subsection, an inner product which is introduced as below helps us to construct the dual code of a linear code where the inner product is obtained with the Gray image. We also show the proof of a lemma which relates dual of the code and its Gray image: Let g = [g1,g2, . . . ,gn],h = [h1,h2, . . . ,hn] ∈ Rnp , gi = gi1 + gi2v + . . . + gipvp−1,hi = hi1 + hi2v + . . .+hipv p−1 , gi(j) = gi1 +gi2j + . . .+gipjp−1 (mod p) and hi(j) = hi1 +hi2j + . . .+hipjp−1 (mod p). 〈g, h〉φ = n∑ i=1 p−1∑ j=1 (gi(j)hi(j)) . If C is a linear code of length n over the ring Rp, then the dual code is defined by C⊥ = {h ∈ Rnp |〈g,h〉φ = 0 for all g ∈ C}. (3) Lemma 3.5. φ(C)⊥ = φ(C⊥). Proof. The proof follows from the definitions: If h ∈ C⊥, then, 〈g,h〉φ = 0 for all g ∈ C. This implies that 〈φ(g),φ(h)〉 = 0 for all φ(g). Hence, φ(h) ∈ (φ(C))⊥ . Thus, φ(C⊥) ⊂ φ(C)⊥. The reverse follows directly by reversing the steps. Example 3.6. Let G = [ 2 + 4v4 3 + 3v + v2 + 2v3 + 3v4 2v3 + 2v4 3 + 4v + 3v4 ] be a generator matrix of a linear code C over R5 = Z5[v]/〈v5−v〉, Then the image of this code is generated by φ(G) =   φ(2 + 4v4) φ(3 + 3v + v2 + 2v3 + 3v4) φ(v(2 + 4v4)) φ(v(3 + 3v + v2 + 2v3 + 3v4)) φ(v2(2 + 4v4)) φ(v2(3 + 3v + v2 + 2v3 + 3v4)) φ(v3(2 + 4v4)) φ(v3(3 + 3v + v2 + 2v3 + 3v4)) φ(v4(2 + 4v4)) φ(v4(3 + 3v + v2 + 2v3 + 3v4)) φ(2v3 + 2v4) φ(3 + 4v + 3v4) φ(v(2v3 + 2v4)) φ(v(3 + 4v + 3v4)) φ(v2(2v3 + 2v4)) φ(v2(3 + 4v + 3v4)) φ(v3(2v3 + 2v4)) φ(v3(3 + 4v + 3v4)) φ(v4(2v3 + 2v4)) φ(v4(3 + 4v + 3v4))   =   2 0 0 0 0 3 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 4 0 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 2   6 A. Bayram, I. Siap ∼   1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1   over Z5, then |C| = 59. Let H = [ 0 0 0 1 0 0 0 0 3 0 ] . is a parity check matrix of φ(C). Hence ∣∣φ(C)⊥∣∣ = 5. Conversely, for all h = [h] ∈ C⊥ such that h = [ h1 + h2v + h3v 2 + h4v 3 + h5v 4 h ′ 1 + h ′ 2v + h ′ 3v 2 + h ′ 4v 3 + h ′ 5v 4 ] then C⊥ = { h = [ (2v + 4v2 + 3v3 + v4)h5 (v + 2v 2 + 4v3 + 3v4)h5 ] ,h5 ∈ Z5} Hence,∣∣∣C⊥∣∣∣ = 5. Therefore, φ(C⊥) = φ(C)⊥. 3.2. MacWilliams Identity for Codes over Rp The MacWilliams identity is one of the prominent results in coding theory, which supplies the relationship between the weight enumerator of a linear code and that of its dual code [10]. The distribution of weights for a linear code is crucial to its performance analysis such as, linear programming bound, error correcting capabilities, the extremal weight enumerators related to the dual codes, etc. In this section, we state several lemmas and the main theorem. We also illustrate the theorem with a moderate example. In this work, we assume that the character χ is described by χ(a) = ξa(0)+a(1)+a(2)+...+a(p−1) where ξ = e2πi/p. The Gray weight enumerator of a linear code C over Rp is defined by W (x,y) = ∑ c∈C xpn−wG(c)ywG(c). This section is a generalization of Section 3.2 in [4], so we will not give all proofs in detail here. Therefore we present the statement of lemmas and the main theorem and state an example to show the result. Lemma 3.7. 1. Assume that I 6= {0} be an ideal of the ring Rp. Then,∑ a∈I χ(a) = 0. 2. For a ∈ Rp, we have ∑ r∈Rp χ(ar) = { pp, a = 0 0, a 6= 0. 7 Cyclic and constacyclic codes over a non-chain ring 3. If β ∈ Rp, then ∑ α∈Rp χ(〈β,α〉)xp−wG(α)ywG(α) = (x + (p−1)y)p−wG(β) (x−y)wG(β) . The following well known result plays an important role in finalizing the proof of the main theorem: Lemma 3.8. [10] If C and its dual C⊥ are linear codes over the ring Rp with f̂ (u) = ∑ v∈Rnp χ(〈u,v〉)f (v) , then ∑ v∈C⊥ f (v) = 1 |C| ∑ u∈C f̂ (u). By combining the lemmas above we get the main theorem that relates the Gray weight enumerators of the code and its dual: Theorem 3.9. Suppose that C is a linear code over Rp, then WC⊥ (x,y) = 1 |C| WC (x + (p−1)y,x−y) . Example 3.10. Assume that G = [ 2 + 3v4 0 0 3v + 3v2 + 3v3 + 3v4 ] generates a linear code C over R5. Then, its Gray weight enumerator is WC(x,y) = x 10 + 8x9y + 16x8y2. Therefore, by applying the necessary change of variables in the main theorem, we obtain WC⊥(x,y) = x 10 + 32x9y + 448x8y2 + 3584x7y3 + 17920x6y4 + 57344x5y5 + 114688x4y6 + 131072x3y7 +65536x2y8. 4. Cyclic Codes over Rp A very significant and well know class of linear codes is the class of cyclic codes which plays a crucial role in coding theory due to their easy implementation. Since cyclic codes can be described as ideals in some polynomial rings, they have considerable inherent algebraic structure. In this part we consider the algebraic structure of cyclic codes over the ring Rp. We also study the structure of their duals. Definition 4.1. Let σ be a cyclic right shift on the entries of an n-tuple in Rn such that σ(c0,c1, . . . , cn−1) = (cn−1,c0, . . . ,cn−2). For a linear code C, if σ(C) = C, then C is called a cyclic code of length n. 8 A. Bayram, I. Siap After associating a polynomial c(x) = c0 + c1x + · · ·+ cn−1xn−1 to a codeword c = (c0,c1, . . . ,cn−1) ∈ C, if C is a cyclic code then, C becomes an ideal of the quotient ring R[x]/〈xn −1〉. Let R(n,p) = Rp[x]/〈xn −1〉. Since Rp ∼= Zpp, then Rp[x]/〈xn −1〉∼= Zp[x]/〈xn −1〉×Zp[x]/〈xn −1〉× . . .×Zp[x]/〈xn −1〉. Let L(n,p) = Zp[x]/〈xn −1〉×Zp[x]/〈xn −1〉× . . .×Zp[x]/〈xn −1〉. Now as a natural extension of φ ,we can get an isomorphism between the rings R(n,p) and L(n,p). We define a projection map πi : Z p p → Zp, such that πi((a1,a2, . . . ap)) = ai for 1 ≤ i ≤ p. Then, we identify φ :R(n,p) → L(n,p) φ( n∑ i=0 aix i) = ( n∑ i=0 π1(φ(ai))x i, n∑ i=0 π2(φ(ai))x i, . . . , n∑ i=0 πp(φ(ai))x i). Example 4.2. Let f(x) = (1 + v2)x3 + (1 + 3v + v3)x2 + (3v2 + v4)x + 1 in R(4,5). Then, φ(f(x)) = (x3 + x2 + 1,2x3 + 4x + 2,3x + 1,2x2 + 3x + 1,2x3 + 2x2 + 4x + 1). It is easy to get the structure of R[x]/〈xn −1〉 since this map is an isomorphism. R(n,p) is a principal ideal ring. We can determine the generator of ideals as follows: Suppose that I = 〈f1(x),f2(x), . . . ,fs(x)〉 is a finitely generated ideal of R(n,p) where fi(x) = ∑n j=0 fijx j. Then, for i = 1,2, . . . , p let gi = gcd1≤j≤s(πi(φ(fj))),xn −1). Hence, I = 〈g(x)〉 where g(x) = φ−1((g1(x),g2(x), . . . ,gp(x))). Example 4.3. Let I = 〈f1(x) = (1+v+2v2+x+(1+2v+v2)x2,f2(x) = 2+2v2+(1+v+v2)x+(v+2v2)x2〉 be an ideal of R(4,3). Then, φ(f1(x)) = ((2+x)2,(2+x)2,2+x) and φ(f2(x)) = (2+x,1,(2+x)2). Next, g1 = gcd((2+x) 2,2+x,x3−1) = 2+x, g2 = gcd((2+x)2,1,x3−1) = 1, g3 = gcd(2+x,(2+x)2,x3−1) = 2 + x. So we have φ(I) = 〈(2 + x,1,2 + x)〉. Therefore, I = φ−1(φ(I)) = 〈φ−1(2 + x,1,2 + x)〉 = 〈2 + v + v2 + (1 + v + v2)x〉. The following lemma can be observed as a straightforward result of the above statements and the example: Lemma 4.4. If C = 〈g(x)〉 is a cyclic code of length n over Rp and φ(g(x)) = (g1,g2, . . . , gp) with deg(gcd(gi,x n −1)) = n−ki for 1 ≤ i ≤ p, then |C| = p ∑p i=1 ki. 4.1. The Dual of Cyclic Codes In this subsection, we study the algebraic structure of the dual of a cyclic code over Rp. Let C = 〈g(x)〉 be a cyclic code of length n over Rp. Assume that, φ(C) = J = 〈(g1(x),g2(x), . . . gp(x))〉 where gi = πi(φ(g(x))). The dual of J is the cyclic code J⊥ = 〈(h1R(x),h2R(x), . . . , hpR (x))〉, where hi(x) = (xn − 1)/(gcd(xn − 1,gi) and hi R (x) is the reciprocal polynomial of hi(x). Hence, C⊥ = 〈φ−1(h1 R (x),h2 R (x), . . . , hp R (x))〉. 9 Cyclic and constacyclic codes over a non-chain ring Example 4.5. Let I = 〈f(x) = (3v4+3v3+4v)x3+(4v4+4v3+2v2+1)x2+(2v4+4v2+3)x+(v3+4v+2) > be an ideal of R(5,4). Then, φ(f(x)) = (x2+3x+2,x2+4x+2,x+3,x3+x2+x+1,x3+3x2+4x+2). Next, g1 = gcd(x 2+3x+2,x4−1) = x2+3x+2, g2 = gcd(x2+4x+2,x4−1) = x2+4x+2, g3 = gcd(x+3,x4−1) = x+3, g4 = gcd(x3+x2+x+1,x4−1) = x3+x2+x+1, g5 = gcd(x3+3x2+4x+2,x4−1) = x3+3x2+4x+2. Thus, |〈I〉| = 59. C⊥ = 〈φ−1(h1R(x),h2R(x),h3R(x),h4R(x),h5R(x))〉 = 〈φ−1((2x2 + 2x + 1,3x2 + 4x + 1,x3+x2+x+1,4x+1,2x+1))〉 = 〈(4v4+3v3+v2+2v)x3+(4v4+3v2+4v+2)x2+(4v3+4v2+2v+2)x+1〉. Therefore, ∣∣〈C⊥〉∣∣ = 511. 5. Constacyclic Codes over Rp In this section, we study constacyclic codes over Rp. Definition 5.1. Let α = a0 +a1v+...+ap−1vp−1 be a unit element of Rp and C be a linear code of length n over Rp. If for all c = (c0,c1, . . . ,cn−1) ∈ C and a unit in Rp we have (αcn−1,c0,c1, . . . ,cn−2) ∈ C, then C is called an α-constacyclic code or shortly constacyclic code. Similar to the cyclic codes case if we associate each codeword c = (c0,c1, . . . ,cn−1) ∈ C with a polynomial c = c0 + c1x + · · · + cn−1xn−1 ∈ R[x], then C can be viewed as an ideal in S(n,p) = Rp[x]/〈xn −α〉. By applying the Chinese Remainder Theorem, we have the following result: Let S(n,p) = Rp[x]/〈xn −α〉. Since Rp ∼= Zpp, Then S ∼= Zp[x]/〈xn −α(0)〉×Zp[x]/〈xn −α(1)〉× . . .×Zp[x]/〈xn −α(p−1)〉. For example, let I = 〈f(x) = (4+3v+v3 +v4 +(1+3v+v2 +4v3 +4v4)x+(3v+4v2 +2v3 +2v4)x2 +(2v+ v2+3v3+4v4)x3)〉, be an ideal of R(4,5) then φ(f(x)) = (4+x,4+3x+x2,4+2x+x3,1+x+x2,1+4x+x2). Since α is a unit element of Rp, then α(i) 6= 0 for all 0 ≤ i ≤ p−1, the number of constacyclic codes over Rp can be obtain as follows: Theorem 5.2. The number of α-constacyclic codes of length n is equal to ∏p−1 i=0 δ(i) where δ(i) = { σn, i = 1, η(n,i), i = 2, ...,(p−1). σn and η(n,i) are equal to the number of cyclic and α(i)−constacyclic codes of length n over Zp, respec- tively. Proof. Since α is a unit element of Rp, the Gray image consists of non zero elements of Zp. If the Gray image contains 1 as a component then the projection code corresponding to that particular component is cyclic which has a generator polynomial as a divisor of xn − 1 over Zp. In addition, if Gray image contains non zero elements different from 1, call it α(i), then the projection is a α(i)−constacyclic code of length n over Zp. Therefore, if σn and η(n,i) are equal to the number of cyclic and α(i)−constacyclic codes of length n over Zp, respectively, then the number of α-constacyclic codes of length n is equal to∏p−1 i=0 δ(i). Example 5.3. Let φ(4 + v + 2v3) = (4,2,2,1,1) ∈ Z5. Since the number of 2−constacyclic , negacyclic and cyclic codes over Z5 are δ(2) = η(4,2) = 2, δ(4) = η(4,4) = 22 and δ(1) = σ4 = 8, respectively then the number of all (4 +v + 2v3)−constacyclic code length 4 over R5 is equal to 4.2.2.8.8 = 22+1+1+3+3 = 210. The algebraic structure of a dual constacyclic code can be obtained as follows: Suppose C = 〈g(x)〉 is an α-constacyclic code of length n over Rp. Let gi = πi(φ(g(x))), then φ(C) = 〈(g1(x),g2(x), . . . gp(x))〉. The dual of C is an α-constacyclic code which is equal to 〈φ−1(h1(x),h2(x), . . . hp(x))〉, where hi(x) = (xn −α(i))/(gi(x)). 10 A. Bayram, I. Siap Example 5.4. Let C be a (1+v+4v2 +3v3)−constacyclic code over R7 generated by f(x) = (4v6 +4v5 + 6v3 +v)x3 +(5v6 +v5 +6v4 +v3 +6v2 +v+1)x+(v6 +5v5 +4v3 +v2 +5v+3) which is an ideal of R(3,7). Since φ(1 + v + 4v2 + 3v3) = (1,2,1,2,2,5,1) and φ(f(x)) = (x + 3,x3 + 5,0,0,x3 + 5,x3 + 2,x + 5) then g1 = x + 3 and h1(x) = (x3 −1)/(x + 3) = (x2 + 4x + 2), g2 = x3 + 5 and h2(x) = (x3 −2)/(x3 + 5) = 1, g3 = 0 and h3(x) = 0, g4 = 0 and h4(x) = 0, g5 = x3 + 5 and h5(x) = (x3 −2)/(x3 + 5) = 1, g6 = x3 + 5 and h6(x) = (x3 − 5)/(x3 + 2) = 1, g7 = x + 5 and h7(x) = (x3 − 1)/(x + 5) = x2 + 2x + 4. So, φ−1(h1(x),h2(x),h3(x),h4(x),h5(x),h6(x),h7(x)) = φ −1(x2 + 4x + 2,1,0,0,1,1,x2 + 2x + 4) = (5v6 + v5 +6v4 +v3 +6v2 +v+1)x2 +(v6 +2v5 +5v4 +2v3 +5v2 +2v+4)x+(5v6 +v5 +3v4 +3v3 +3v2 +5v+2) Therefore, C⊥ = 〈(5v6 + v5 + 6v4 + v3 + 6v2 + v + 1)x2 + (v6 + 2v5 + 5v4 + 2v3 + 5v2 + 2v + 4)x + (5v6 + v5 + 3v4 + 3v3 + 3v2 + 5v + 2)〉. 6. Conclusions We have explored further a new family of codes over a special non-chain ring by generalizing some results in [4]. In general, non-chain rings are very complicated to be studied. Here, by introducing a Gray map the problem has been resolved. Linear, cyclic and constacyclic codes have been introduced. A MacWilliams Type Identity is also proven. This results can be easily generalized to codes over the ring Fq[v]/〈vq −v〉 where Fq is a field with q elements. Acknowledgment: The preliminary results of this paper are presented in Proceedings of the 2013 International Conference on Computational and Mathematical Methods in Science and Engineering- CMMSE 2013, June 24-27 2013, Almeria, Spain. References [1] T. Abualrub, I. Siap, On the Construction of Cyclic Codes over the Ring Z2 + uZ2, WSEAS Trans. on Math., 5(6), 750-756, 2006. [2] T. Abulraub, I. Siap, Cyclic Codes over the Rings Z2 + uZ2 and Z2 + uZ2 + u2Z2, Designs, Codes and Cryptography, 3(42), 273-287, 2007. [3] M. Al-Ashker, M. Hamoudeh, Cyclic codes over Z2 + uZ2 + u2Z2 + · · ·+ uk−1Z2, Turkish J. Math., 35(4), 737-749, 2011. [4] A. Bayram, I. Siap, Structure of Codes over the Ring Z3[v]/〈v3 − v〉, Applicable Algebra in Engi- neering, Communication and Computing, 24(5), 369-386, 2013. [5] K. Betsumiya, M. Harada, Optimal self-dual codes over F2×F2, with respect to the Hamming weight, IEEE Transactions on Information Theory, 50(2), 356-358, 2004. [6] A. Bonnecaze and P. Udaya, Cyclic codes and self-dual codes over F2 +uF2, IEEE Trans. Inf. Theory, 45(4), 1250-1255, 1999. [7] S.T. Dougherty, B. Yildiz and S. Karadeniz, Codes over R, Gray Maps and their Binary Images, Finite Fields and Their Applications, 17(3), 205-219, 2011. [8] J. Gao, Y. Wang, Some results on linear codes over Fp+vFp+v3Fp, Journal of Applied Mathematics and Computing, May 2014. [9] A.R. Hammons, Jr., P.V. Kumar, A.R. Calderbank, N.J.A. Sloane, and P. Sole, The Z4-linearity of Kerdock, Preparata, Goethals, and related codes, IEEE Trans. Inf. Theory, 40(2), 301-319, 1994. [10] F.J. MacWilliams and N.J.A. Sloane, The Theory of Error Correcting Codes, North-Holland, Ams- terdam, The Netherlands, 1977. [11] M. Ozen and I. Siap, Linear Codes Over Fq[u]/(us) with Respect to the Rosenbloom-Tsfasman Metric, Designs, Codes and Cryptography, 38(1), 17-29, 2006. [12] Y. H. Park, Modular independence and generator matrices for codes over Zm, Des. Codes Crypt., 50(2), 147-162, 2009. 11 Cyclic and constacyclic codes over a non-chain ring [13] J.-F. Qian, L.-N. Zhang, and S.-X. Zhu, Constacyclic and Cyclic Codes over F2 +uF2 +u2F2, IEICE Trans. Fundamentals, 89(6), 1863-1865, 2006. [14] B. Yildiz, S. Karadeniz, Linear Codes over F2 + uF2 + vF2 + uvF2, Des. Codes Crypt., 54(1), 61-81, 2010. [15] B. Yildiz, S. Karadeniz, Cyclic Codes over F2 +uF2 +vF2 +uvF2, Des. Codes Crypt., 58(3), 221-234, 2011. [16] S.-X. Zhu, Y. Wang, M.-J. Shi, Cyclic codes over F2 + vF2, ISIT’09 Proceedings of the 2009 IEEE international conference on Symposium on Information Theory, 3, 1719-1722, 2009. 12 Introduction Preliminaries Linear Codes over Rp Cyclic Codes over Rp Constacyclic Codes over Rp Conclusions References