EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 10, No. 5, 2017, 1112-1123 ISSN 1307-5543 – www.ejpam.com Published by New York Business Global Optimal Divisible Binary Codes from Gray-Homogeneous Images of Codes over Rk,m Bahattin Yildiz1,∗, Nesibe Tufekci 1 Department of Mathematics & Statistics, Northern Arizona University, Flagstaff, AZ 86001, USA Abstract. In this work, we find a form for the homogeneous weight over the ring Rk,m, using the related theoretical results from the literature. We then use the first order Reed-Muller codes to find a distance-preserving map that takes codes over Rk,m to binary codes. By considering cyclic, constacyclic and quasicyclic codes over Rk,m of different lengths for different values of k and m, we construct a considerable number of optimal binary codes that are divisible with high levels of divisibility. The codes we have obtained are also quasicyclic with high indices and they are all self-orthogonal when km ≥ 4. The results, which have been obtained by computer search are tabulated. 2010 Mathematics Subject Classifications: 94B05, 94B99 Key Words and Phrases: Homogeneous weight, Frobenius rings, divisible codes, self-orthogonal quasicyclic codes, optimal codes 1. Introduction The homogeneous weight was introduced for codes over rings as an alternative to the Hamming weight. The theoretical work on the homogeneous weight and its form for Frobenius rings can be found in such works as [4], [6] and [8]. Different characterizations for the homogeneous weight on Frobenius rings were given in these works. The Mobius function or the generating character of the ring seem to be the prevalent tools used in these constructions. In most works related to the homogeneous weight, the average weight γ is unassigned. In a number of recent works involving different alphabets, γ was given a fixed value and then a distance-preserving isometry was defined using different methods and tools. We will call such an isometry a Gray-homogeneous map here. In [17] and [16] an algebraic and a combinatorial construction was given respectively, for the Gray-homogeneous map on Galois rings. In [11], combinatorial constructions using projective geometries were given for the Gray-homogeneous maps on finite chain rings and some other families of rings. In ∗Corresponding author. Email addresses: bahattin.yildiz@nau.edu (B. Yildiz), nesibe tufekci@hotmail.com (N. Tufekci) http://www.ejpam.com 1112 c© 2017 EJPAM All rights reserved. B. Yildiz, N. Tufekci / Eur. J. Pure Appl. Math, 10 (5) (2017), 1112-1123 1113 [15], a construction for the Gray-homogeneous map using Reed-Muller codes was given for codes over the ring family of Rk, and many new quasicyclic codes were obtained as images. In this work, we consider the homogeneous weight on the ring family Rk,m, a char- acteristic 2 family of Frobenius rings, intrduced in [13]. Using the generating character characterization of the homogeneous weight we find a form for the homogeneous weight on Rk,m. We assign a value to the average weight γ, giving algebraic and combinatorial justifications. We then construct the Gray-homogeneous map using Reed-Muller codes. Using the images of cyclic, constacyclic and quasicyclic codes overRk,m of different lengths with suitable k,m we are able to construct many optimal binary codes that are divisible with high levels of divisibility. The codes we have obtained are also quasicyclic with high indices and they are all self-orthogonal when km ≥ 4. Thus we obtain many optimal, self-orthogonal quasicyclic binary codes, which have been shown to be of importance in [12], for their connection to difference sets and their near-BCH performance. The rest of the work is organized as follows. In section 2, we give some preliminaries on the ring family Rk,m, mainly citing from [13]. In section 3, we recall the defini- tions of the homogeneous weight from the relevant literature and applying the definitions to Rk,m, we find the homogeneous weight for codes over Rk,m. We also construct the Gray-homogeneous map. Section 4 contains the computational results obtained using a computer search, with the help of Magma, [2]. We then finish with concluding remarks in section 5. 2. Preliminaries The ring denoted by Rk,m is a characteristic 2 ring of size 2km, that was introduced in [13], and is defined as follows for k ≥ m ≥ 1: Rk,m = F2[u, v]/ 〈 uk, vm, uv − vu 〉 . Note that when k = 2,m = 1 the ring is F2 + uF2, when k = m = 2 the ring is F2 + uF2 + vF2 + uvF2, both quite commonly-used in the recent literature of Coding Theory. Any element of Rk,m can be represented as∑ 0≤i≤k−1 0≤j≤m−1 ciju ivj , cij ∈ F2. (1) The following lemmas from [13] describes the algebraic structure of these rings. Lemma 1. An element in Rk,m of the form given in (1) is a unit if and only if c00 is 1. Lemma 2. The ring Rk,m is a local ring with a unique maximal ideal Iu,v = 〈u, v〉. This ideal consists of all non-units and satisfies |Iu,v| = |Rk,m| 2 . B. Yildiz, N. Tufekci / Eur. J. Pure Appl. Math, 10 (5) (2017), 1112-1123 1114 By U(Rk,m), denote the units of Rk,m and by D(Rk,m), the set of non-units in Rk,m. It is easy to see that |U(Rk,m)| = |D(Rk,m)| = |Rk,m| 2 and that U(Rk,m) = 1 +D(Rk,m). We easily observe that when m > 1, Rk,m is not a chain ring. However, as was also pointed out in [13], since Rk,m/Rad(Rk,m) ' Soc(Rk,m) the ring Rk,m is a Frobenius ring. As a Frobenius ring, Rk,m has a generating character. It was shown in [13] that the generating character of Rk,m is given by χ : (Rk,m,+) → ({−1, 1} , .)∑ 0≤i≤k−1 0≤j≤m−1 ciju ivj 7→ (−1)wH(c) , (2) where c = (cij) is the binary vector consisting of all the coefficients cij ’s of a typical element in Rk,m, and wH(c) denotes the Hamming weight of c. For example, in the case when k = 2,m = 1, i.e., when the ring is F2 + uF2, the generating character takes on the values: χ(0) = 1, χ(1) = χ(u) = −1 and χ(1 + u) = 1. A linear code C of length n over Rk,m is an Rk,m-submodule of Rnk,m. Special types of codes such as cyclic and quasicyclic codes are also defined over Rk,m in the natural way they are defined over rings. For more details on the structural properties of the rings as well as a Lee weight and related Gray maps we refer to [13]. 3. The Homogeneous Weight and the Corresponding Gray Map on Rk,m Homogeneous weights were first introduced in 1997 by Heise and Constantinescu in [4]. They have been studied especially within the context of Frobenius rings. [8] and [6] can be cited for this purpose. The homogeneous weight is defined with two conditions for arbitrary finite rings as follows in [6]: Definition 1. A real valued function ω on the finite ring R is called a (left) homogeneous weight if ω(0) = 0 and the following is true: (H1) For all x, y ∈ R,Rx = Ry implies ω(x) = ω(y) holds. (H2) There exists a real number γ such that∑ y∈Rx ω(y) = γ |Rx| for all x ∈ R\{0} It has been shown that all Frobenius rings are equipped with a homogeneous weight. Different characterizations of the homogeneous weight for Frobenus rings have been given. Some of these use the Mobius function, and some use the generating character of Frobenius rings. In our work we will use the following proposition from [8], which describes the homogeneous weight in terms of the generating character of the ring: B. Yildiz, N. Tufekci / Eur. J. Pure Appl. Math, 10 (5) (2017), 1112-1123 1115 Proposition 1. ([8]) The homogeneous weight function for a finite ring R with generating character χ is of the form ω : R → R x 7→ γ [ 1− 1 |R×| ∑ ρ∈R× χ(xρ) ] , (3) where R×, represents the group of units of R. The γ that appears in the weight function is also called the average weight and further satisfies the following property: Proposition 2. ([8]) Let I be either a left or a right ideal of a finite Frobenius ring R, and let y ∈ R. Then ∑ r∈I+y ω(r) = γ |I|. Applying Proposition 1 to the ring Rk,m, we can obtain a form for the homogeneous weight for codes over the ring Rk,m: Theorem 1. The homogeneous weight for the ring Rk,m is of the form ωhom(x)  0 x = 0, 2γ, x = uk−1vm−1, γ, otherwise. Proof. We first note that uk−1vm−1ρ = uk−1vm−1 for all ρ ∈ U(Rk,m) and so we have χ(uk−1vm−1ρ) = (−1) for all ρ ∈ U(Rk,m). Putting uk−1vm−1 into Equation 3 we see that we have ωhom(uk−1vm−1) = γ [ 1− 1 2km−1 ∑ ρ∈U(Rk,m) (−1) ] = 2γ. On the other hand, following the same arguments as were used in [15] we can prove that, for any element x in Rk,m such that x 6= 0, uk−1vm−1, we have∑ α∈U(Rk,m) χ(αx) = 0. Thus we obtain ωhom(x) = γ [ 1− 1 2km−1 0 ] = γ for all x 6= 0, uk−1vm−1. Having settled the form of the homogeneous weight, we now want to choose a specific value for γ so that we can find a distance preserving isometry from Rk,m to Fs2 for a suitable s. We will call this map the Gray-homogeneous map. We recall some of the work done in this direction. An inductive algebraic construction of a distance preserving Gray map was given by Yildiz from Galois rings with the homogeneous distance to the field of prime size with the Hamming distance in [17] as well as a combinatorial construction B. Yildiz, N. Tufekci / Eur. J. Pure Appl. Math, 10 (5) (2017), 1112-1123 1116 of the Gray map for Galois rings by using Affine geometries in [16]. Later, projective geometries PGn(q) were used to construct the Gray map for linear codes over a family of Frobenius rings in [11]. Considering the hyperplanes and projective spaces, the work in [11] suggests the use of the projective geometry PGkm−1(F2). This requires the s to be 2km−1. However, as was later done in [15], the first order Reed-Muller codes seem to give us a more constructive method of finding this map. We recall that the first order Reed-Muller codes RM(1,m) are a family of binary linear codes of parameters [2m,m + 1, 2m−1], for each positive integer m. The important property of the first order Reed-Muller codes is that there is one codeword with weight 2m and all the other non-zero codewords have weight 2m−1. Because of the structure of the homogeneous weight, it is clear that first order Reed-Muller codes can be used to construct the Gray map. Since |Rk,m| = 2km, we clearly need RM(1, s) where s + 1 = km. Thus, to define a distance preserving Gray map for the homogeneous weight on Rk,m we use the first order Reed-Muller codes RM(1, km−1), of length 2km−1. This coincides with length of the image suggested in [11], which adds an added motivation for the choice of γ for us. Thus we choose γ = 2km−2. This means that for us, the homogeneous weight will have the following form: ωhom(x)  0 if x = 0, 2km−1 if x = uk−1vm−1, 2km−2 otherwise. Now, in order to define the Gray-homogeneous map on Rk,m, we first note that Rk,m can be viewed as an F2-vector space with a basis β = {1, u, . . . , uk−1, v, . . . , vm−1, uv, . . . , uk−1vm−1}. RM(1, 2km− 1) has exactly km basis elements, which are binary vectors of length 2km−1, including (1, 1, . . . , 1). So, we first let φhom map elements of the minimal ideal Iuk−1vm−1 to the two elements of RM(1, km − 1), given by (0 . . . 0) and (1 . . . 1), respectively. The remaining elements of the basis are mapped to basic generators of RM(1, km− 1) except (1 . . . 1). Taking all the possible linear combinations, we extend the map φhom to Rk,m. The map is then extended in the natural way Rnk,m: φhom : (Rk,m)n → F(2km−1)n 2 (c1, c2, . . . , cn) 7→ (φhom(c1), φhom(c2), . . . , φhom(cn)) . (4) The properties of the Reed-Muller codes then result in the following: Theorem 2. φhom is a distance preserving isometry from (Rnk,m, homogeneous distance) to (F2km−1n 2 , hamming distance). Thus if C is a linear code over Rk,m of length n and minimum homogeneous weight d, then φhom(C) is a binary linear code of length 2km−1n, and minimum hamming weight d. Moreover, the Homogeneous weight distribution of C is the same as the hamming weight distribution of φhom(C). B. Yildiz, N. Tufekci / Eur. J. Pure Appl. Math, 10 (5) (2017), 1112-1123 1117 We finish this section with a few examples: The homogeneous weight forR2,1 = F+uF2 coincides with the Lee weight defined on F2 + uF2 and the Gray-homogeneous map also coincides with the usual Gray map for F2 + uF2, that is well-known in the literature. Let us consider R3,1 = F2 + uF2 + u2F2. The homogeneous weight then is found to be ωhom(x)  0 if x = 0, 4 if x = u2, 2 otherwise. The Gray-homogeneous map will then be given by φhom(u2) = (1, 1, 1, 1), φhom(u) = (1, 1, 0, 0), φhom(1) = (1, 0, 1, 0). The map is then extended to R3,1 by taking the F2-linear combinations. Consequently we have φhom(a+ bu+ cu2) = (a+ b+ c, b+ c, a+ c, c), a, b, c ∈ F2. 4. Divisible codes over Rk,m Divisible codes were first introduced by Ward in 1981 in [14]. A code is divisible if the weights of all the codewords have a common divisor ∆ > 1. The replicated code, constructed by repeating each coordinate of a selected code a certain number of times is the simplest divisible code. Moreover, Ward proved that a divisible code is equivalent to a ∆-fold replicated code if the divisor ∆ of the code is relatively prime to the field characteristic in [14]. A divisible code is said to be of “level e”, if the greatest common divisor of weights of codewords in C equals pe for some integer e ≥ 1. Reed-Muller codes are an example of divisible codes, by the following theorem in [10]: Theorem 3. The weight of every codeword in RM(r,m) is divisible by 2[(m−1)/r]. Because of the homogeneous weight on Rk,m we can easily observe the following: Theorem 4. Any linear code C over Rk,m is divisible with ∆ ≥ γ. In particular with our choice of γ, we see that if C is a linear code over Rk,m of length n, then φhom(C) is a divisible binary code of length 2km−1n with ∆ ≥ 2km−2. Thus any such code is of level e ≥ km− 2. It is well known that binary linear divisible codes with ∆ = 2k, k ≥ 2 are also self- orthogonal. Thus we have the following corollary: Corollary 1. Let C be any linear code over Rk,m. Then φhom(C) is a binary self- orthogonal linear code if km ≥ 4. In what follows, we will search for binary divisible codes with various divisors from the Gray-homogeneous images of cyclic, constacyclic and quasicyclic codes over Rk,m of some lengths. Because of the increased size of the rings, we will mostly consider the rings R3,1 , R4,1 and R5,1. The examples that we give are mainly optimal. B. Yildiz, N. Tufekci / Eur. J. Pure Appl. Math, 10 (5) (2017), 1112-1123 1118 4.1. Divisible Cyclic Codes Over Rk,m Recall that a linear code C of length n overRk,m is a cyclic code if τ(c̄) = (cn−1, c0, . . . , cn−2) ∈ C for all c̄ = (c0, c1 . . . , cn−1) ∈ C, where τ is the cyclic shift. Considering the polynomial correspondence π : (Rk,m)n → Rk,m[x] c̄ = (c0, c1 . . . , cn−1) 7→ c0 + c1x+ . . .+ cn−1x n−1 we know that a code C of length n over Rk,m is cyclic if and only if π(C) is an ideal in the ring Rk,m[x]/(xn−1). There are a lot of results concerning the structural properties of cyclic codes over rings, in particular over finite chain rings. The rings that we consider for the purposes in this section, R3,1, R4,1 being finite chain, we are not going to go into the theoretical aspects of cyclic codes. Instead we will demonstrate how some one- generator cyclic codes over these rings lead to optimal divisible binary linear codes under the Gray-homogeneous map. Since the Gray-homogeneous image of a cyclic code over Rk,m is a 2km−1-quasicyclic binary code, the binary codes that we have constructed have the additional property that they are 4-quasicyclic or 8-quasicyclic according as we are on the ring R3,1 or R4,1. Table 1: Divisible cyclic codes over R3,1 of length n and the binary images n g(x) φhom(〈g(x)〉) ∆ level 3 u2x+ u2x2 [12, 2, 8] 8 3 3 1 + x2 [12, 3, 6] 6 1 4 ux+ u2x2 + ux3 [16, 4, 8] 8 3 4 1 + x+ x2 + (1 + u2)x3 [16, 5, 8] 8 3 4 x+ ux2 + (u+ 1)x3 [16, 6, 6] 2 1 4 x2 + x3 [16, 9, 4] 2 1 4 x3 [16, 12, 2] 2 1 5 x3 + x4 [20, 12, 4] 2 1 5 x3 + (1 + u2)x4 [20, 13, 4] 2 1 6 ux+ ux2 + u2x3 + ux4 + (u+ u2)x5 [24, 4, 12] 4 2 6 x4 + x5 [24, 15, 4] 2 1 6 x4 + (1 + u)x5 [24, 16, 4] 2 1 7 u2x2 + u2x4 + u2x5 + u2x6 [28, 3, 16] 16 4 7 1 + x+ x2 + (1 + u2)x3 + x4 + (1 + u2)x5 + (1 + u2)x6 [28, 6, 12] 2 1 7 x2 + x4 + (1 + u2)x5 + (1 + u2)x6 [28, 12, 8] 4 2 7 x5 + (1 + u2)x6 [28, 19, 4] 2 1 8 x3 + ux5 + ux6 + x7 [32, 14, 8] 2 1 8 x4 + x5 + (1 + u)x6 + (1 + u+ u2)x7 [32, 15, 8] 2 1 B. Yildiz, N. Tufekci / Eur. J. Pure Appl. Math, 10 (5) (2017), 1112-1123 1119 Table 2: Divisible cyclic codes over R4,1 of length n and the binary images n g(x) φhom(〈g(x)〉) ∆ level 2 u+ ux [16, 3, 8] 8 3 3 u3x+ u3x2 [24, 2, 16] 16 4 3 x+ x2 [24, 8, 8] 4 2 3 x+ (1 + u3)x2 [24, 9, 8] 4 2 4 u2x+ u3x2 + u2x3 [32, 4, 16] 16 4 4 1 + x+ (1 + u3)x2 + (1 + u3)x3 [32, 5, 16] 16 4 4 1 + x+ x2 + (1 + u3)x3 [32, 6, 16] 16 4 6 u3x+ u3x2 + u3x4 + u3x5 [48, 2, 32] 32 5 6 u2x+ u2x2 + u3x3 + u2x4 + (u2 + u3)x5 [48, 4, 24] 8 3 Remark 1. All the binary codes given in the above tables are optimal or best known codes, meaning that they either attain upper bounds or have the best known minimum distance according to [5]. The codes given in Table 2 have the additional property that they are all self-orthogonal quasicyclic codes of the best possible parameters. 4.2. Divisible constacyclic codes over Rk,m Constacyclic codes are a natural generalization of cyclic codes. For a unit α ∈ R, a constacyclic shift on Rn is given by τα(c0, c1, . . . , cn−1) = (αcn−1, c0, c1, . . . , cn−2). A code C over R is said to be α-constacyclic if it is invariant under the α-constacyclic shift, i.e., τα(C) = C. In exactly the same way as the cyclic codes, constacylic codes are also endowed with an algebraic structure. More precisely, constacyclic codes over R are in one-to-one correspondence with ideals in the quoient ring R[x]/(xn − α). Structural properties of constacyclic codes over different alphabets have been studied quite extensively in the literature. In [9], Karadeniz and Yildiz studied (1 + v)-constacyclic codes over R2,2 = F2 + uF2 + vF2 + uvF2. It is well known that if R is a ring of characteristic 2, and α ∈ R satisfies α2 = 1, then α-constacyclic codes over R are also cyclic. In R2,2 as well as in the latter generalizations Rk, [15], every unit satisfies this property. So, constacyclic codes over these rings of odd lengths are just cyclic. However, the cases that we look at, namely in R3,1, R4,1 and R5,1 this is not true. If we take α = 1 + u, then (1 + u)2 6= 1 in the rings mentioned above. In what follows, we have listed some examples of one-generator (1 + u)-constacyclic codes over Rk,m and their homogeneous gray images, which turn out to be divisible, optimal and in some cases self-orthogonal: B. Yildiz, N. Tufekci / Eur. J. Pure Appl. Math, 10 (5) (2017), 1112-1123 1120 Table 3: Divisible (1 + u)-constacyclic codes over Rk,1 of length n and the binary images Rk,1 n generator of the code φhom(〈g(x)〉) ∆ level R3,1 6 (0, u2, u2, 0, u2, u2) [24, 2, 16] 16 4 R3,1 6 (0, 0, 0, 1, u, 1) [24, 15, 4] 2 1 R3,1 7 (0, 0, u2, 0, u2, u2, u2) [28, 3, 16] 16 4 R3,1 7 (1, u+ 1, 1, u+ 1, 1, u2 + u+ 1, u2 + 1) [28, 6, 12] 2 1 R3,1 7 (0, 0, 1, 0, 1, u+ 1, 1) [28, 12, 8] 4 2 R3,1 7 (0, 0, 0, 0, 0, 1, u2 + u+ 1) [28, 19, 4] 2 1 R3,1 9 (0, u2, u2, 0, u2, u2, 0, u2, u2) [36, 2, 24] 24 R4,1 2 (u2, u2) [16, 3, 8] 8 3 R4,1 3 (0, 1, u+ 1) [24, 8, 8] 4 2 R4,1 3 (0, 1, u3 + u+ 1) [24, 9, 8] 4 2 R4,1 5 (1, u3 + u2 + u+ 1, u2 + 1, u+ 1, 1) [40, 4, 20] 20 R4,1 7 (0, 0, u3, 0, u3, u3, u3) [56, 3, 32] 32 5 R5,1 3 (0, u4, u4) [48, 2, 32] 32 5 R5,1 3 (u, u2 + u, u3 + u) [48, 4, 24] 24 R5,1 3 (1, 1 + u+ u4, 1 + u2) [48, 5, 24] 24 R5,1 5 (1, u3 + u2 + u+ 1, u4 + u2 + 1, u+ 1, u4 + 1) [80, 5, 40] 40 Remark 2. If C is an α-constacyclic code over Rk,m, then φhom(C) might not be a 2km−1- quasicyclic binary code, however it can easily be shown that φhom(C) is equivalent to a 2km−1-quasicyclic binary code. Thus all the codes given in the above table are equivalent to binary quasicyclic codes and they are also self-orthogonal when ∆ ≥ 4. 4.3. Some results on divisible quasicyclic codes over Rk,m Quasicyclic codes are another generalization of cyclic codes and have generated a lot of interest. They have algebraic structure and they also satisfy a modified version of the Gilbert-Varshamov bound. Many optimal good binary codes are quasicyclic. A lot of good codes have been constructed using quasicyclic codes over different alphabets, such as [1] and [3]. A definition can be given from [10]: Definition 2. A code C of length n is called `−quasicyclic if `|n and τ `(C) = C. Note that when ` = 1, 1-quasicyclic codes are just cyclic codes. Structurally, the generator matrix of a t generator `−quasicyclic code can be shown to be of the following form:  C00 C01 . . . C0,`−1 C10 C11 . . . C1,`−1 ... ... ... ... Ct,0 Ct,1 . . . Ct,`−1  where Cij are m×m circulant matrices. In such a case, the length n of the `−quasicyclic code C is m× `. We refer to [12, 3] for more information on quasicyclic codes. B. Yildiz, N. Tufekci / Eur. J. Pure Appl. Math, 10 (5) (2017), 1112-1123 1121 We have searched through one generator `-quasicyclic codes over Rk,m to get divisible codes of various lengths. We have listed in the following table, divisible, optimal binary codes obtained as the φhom-images of quasi cyclic codes over Rk,m: Table 4: Divisible `-quasicyclic codes over Rk,1 and the binary images Rk,1 ` generator of the code φhom(〈g(x)〉) ∆ level R3,1 3 (0, 1, 1, 0, 1, 1 + u2, u, u, u2) [36, 2, 24] 24 3 (0, u, u, 0, u, u2 + u, u, u, u2) [36, 5, 16] 4 2 3 (0, 1, 1, 0, u, u, 1, u2, u2 + 1) [36, 6, 16] 4 2 3 (0, 1, 1, 0, 1, u2 + 1, u, u, u2) [36, 7, 16] 4 2 3 (1, 1, u2 + 1, u2 + 1, 1, 1, u2 + 1, u2 + 1, 1, 1, u2 + 1, u2 + 1) [48, 4, 24] 24 3 (0, u, u2, u2 + u, 1, 1, u2 + 1, u2 + 1, 1, u+ 1, 1, u+ 1) [48, 5, 24] 8 3 2 (0, 1, 1, u2, 1, u2 + 1, u2 + u, 1, u2 + u+ 1, u, 1, u+ 1) [48, 6, 24] 8 3 2 (0, 0, 0, u, u, 0, u2, u, u, u2) [40, 8, 16] 8 3 3 (1, 1, 1, 1, u2 + 1, 1, 1, 1, u2 + 1, u2 + 1, 1, 1, u2 + 1, 1, u2 + 1) [60, 7, 28] 2 1 3 (0, 0, 0, 1, 1, 0, u, 1, u, 1, 1, u+ 1, u2, 1, u2 + u+ 1) [60, 12, 24] 4 2 R4,1 2 (1, 1, u3 + 1, u3 + 1, 1, 1, u3 + 1, u3 + 1) [64, 5, 32] 32 5 2 (1, 1, 1, u3 + 1, 1, 1, 1, u3 + 1) [64, 6, 32] 32 5 2 (1, 1, u2 + 1, u3 + u2 + 1, 1, 1, u3 + u2 + 1, u2 + 1) [64, 7, 32] 32 5 3 (1, 1, u3 + 1, 1, 1, u3 + 1, 1, 1, u3 + 1) [72, 5, 36] 12 3 (1, 1, 1, u3 + 1, 1, 1, 1, u3 + 1, 1, 1, 1, u3 + 1) [96, 6, 48] 48 Remark 3. It can easily be shown that the Gray-homogeneous image of an `-quasicyclic code is a (2km−1`)-quasicyclic binary code. So, the binary codes constructed above are all (2km−1`)-quasicyclic for the appropriate values of `, k,m. In all but one of the cases they are self-orthogonal as well. Thus almost all the codes given in the above table are optimal self-orthogonal quasicyclic codes. 4.4. Griesmer Code The Griesmer bound, introduced in [7] is one of the many bounds that exist for codes, and can be stated as follows: For a linear [n, k, d]-code over Fq, we have n ≥ k−1∑ i=0 d d qi e, (5) where dxe denotes the smallest integer greater than or equal to x. Linear codes meeting this bound are called Griesmer Codes. Let us consider a one generator cyclic code Ckm of length n over Rk,m with the generator vector (11 . . . 1). This is actually the repetition code. It is clear to see that the Gray-homogeneous image of this code is a binary linear code of the parameters [2km−1n, km, 2km−2n]. Thus, the images of this code are binary divisible codes with divi- sor at least 2km−2. We may construct many optimal linear codes, which otherwise may REFERENCES 1122 have complicated constructions, in a relatively easier way from Ckm. As an illustration of this idea, consider, the Gray-homogeneous images of C51 and C32 of length n. These will be binary codes of parameters [16n, 5, 8n] and [32n, 6, 16n], respectively. According to [5], these codes are all optimal when 1 ≤ n ≤ 8. We finish this section by noticing that φhom(Ckm)s are Griesmer codes, when n = 1, for all k and m. Theorem 5. The binary linear code φhom(Ckm) is a Griesmer code for n = 1, and for all k,m. Proof. When n = 1, φhom(Ckm) is a km-dimensional linear code with minimum dis- tance 2km−2. Calculating the Griesmer lower bound according to 5, we see that the lower bound must be km−1∑ i=0 d d 2i e = d2 km−2 20 e+ d2 km−2 21 e+ · · ·+ d2 km−2 2km−2 e+ d2 km−2 2km−1 e = 2km−2 + 2km−3 + · · ·+ 1 + 1 = (2km−1 − 1) + 1 = 2km−1, which is precisely the length of φhom(Ckm), when n = 1. 5. conclusion Finding optimal binary codes is a relevant question in coding theory. The database given in [5] is a dynamic source of such codes together with different suggested construc- tions. In our work, we were able to reconstruct many of the optimal codes by using different constructions over the rings Rk,m. The codes that are obtained, are not only all optimal, but they possess some further properties such as being divisible with high levels of divisi- bility, and in many cases self-orthogonal. They are also quasicyclic with high indices. This means that the binary codes that we have obtained from the Gray-homogeneous images of codes over Rk,m are rather special examples of codes that appear in [5]. Considering that many of the codes we have obtained fall into the class of self-orthogonal quasicyclic codes, they are of interest within the context of [12] as well. The relative ease with which we obtained the codes and usually simple constructions suggest that, the idea of using Rk,m and the Gray-homogeneous map is worth pursuing in many other contexts as well. References [1] N Aydin, S Karadeniz and B Yildiz. Some new binary quasi-cyclic codes from codes over the ring F2+uF2+vF2+uvF2, Applicable Algebra in Engineering, Communication and Computing, 24:355-367, 2013. REFERENCES 1123 [2] W Bosma, J Cannon and C Playoust. The Magma algebra system I. The user lan- guage, Journal of Symbolic Computation, 24:235–265, 1997. [3] Z Chen. Six new binary quasi-cyclic codes, IEEE Transactions on Information The- ory, 40(5):1666–1667, 1994. [4] I Constantinescu and W Heise. A metric for codes over residue class rings of integers, Problemy Peredachi Informatsii, 33(3):22–28, 1997. [5] M Grassl. Bound on the minimum distance of linear codes and quantum codes, Online available at: www.codetables.de(Accessed on 2015/12/01). [6] M Greferath and M E OSullivan. On bounds for codes over Frobenius rings under homogeneous weights, Discrete Mathematics, 289:11-24, 2004. [7] J H Griesmer. A bound for error correcting codes, IBM Journal of Research and Development, 4:532–542, 1960. [8] T Honold. A Characterization of finite Frobenius rings, Archiv der Mathematik, 76:406-415, 2001. [9] S Karadeniz and B Yildiz. (1 + v)-constacylic codes over F2 + uF2 + vF2 + uvF2, Journal of the Franklin Institute, 348:2625–2632, 2011. [10] F J MacWilliams and N J A Sloane. The Theory of Error-Correcting Codes, North- Holland Publishing Company, 1977. [11] A Pasa and B Yildiz. Constructing Gray maps from combinatorial geometries, Com- munications de la Facult des Sciences de l’Universit d’Ankara Serie A1, 63:147–161, 2014. [12] R L Townsend and E Weldon. Self-orthogonal quasi-cyclic codes, IEEE Transactions on Information Theory, 13(2):183–195, 1967. [13] N Tufekci and B Yildiz. On codes overRk,m and constructions for new binary self-dual codes, Mathematica Slovaca, 66(6):1511–1526, 2016. [14] H N Ward. Divisible codes, Archive der Mathematik, 36:485-499, 1981. [15] B Yildiz and I G Kelebek. The homogeneous weight for Rk, related Gray map and new binary quasicyclic codes, ArXiv: 1504.04111, 2014. [16] B Yildiz. A Combinatorial construction of the Gray map over Galois rings, Discrete Mathematics, 309:3408–3412, 2009. [17] B Yildiz. Weight enumerators and Gray maps of linear codes over rings, Ph.D. Thesis: California Institute of Technology, 2006.