12_salturk.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 5, No. 2, 2012, 250-259 ISSN 1307-5543 – www.ejpam.com Generalized Gaussian Numbers Related to Linear Codes over Galois Rings Esengül Saltürk∗, İrfan Şiap Department of Mathematics, Yildiz Technical University, Istanbul, Turkey Abstract. In this paper, we define a family of Generalized Gaussian Numbers that gives the number of linear codes over Galois rings directly. Also, we study some of their properties and obtain some relations between them. 2010 Mathematics Subject Classifications: 11T71, 94B05, 05A10 Key Words and Phrases: Gaussian binomial coefficients, linear codes over rings 1. Introduction Binomial coefficients and Gaussian binomial coefficients are two fundamental classes of numbers arising in enumerative combinatorics. Binomial coefficients give the number of sub- sets of a finite set. On the other hand, Gaussian binomial coefficients give the number of linear codes over finite fields of a particular dimension. Since the theory of linear codes over fields has been extended linear codes over rings recently, the problems that had found answers for field cases remain open for the ring cases. One of such problems is establishing a formula for the number of linear codes of a particular type similar to Gaussian Number formula. In this paper, the authors provide such a formula that directly gives the number of linear codes over Galois rings of a particular type. Linear codes over finite rings have been a very important field of coding theory due to Hammons et al [4]. The enumeration problems over rings are studied by many researchers. Some of them are [1, 2, 3, 5, 10, 11, 14]. The enumeration in all of these works are based on recursive formulae. In this work, we give a direct calculation of the number of linear codes over an important family of finite rings which is Galois rings. As a result of this, we define Generalized Gaussian Numbers as a further generalization of the previous works [10, 11] and give some of their properties similar to Gaussian binomial coefficients. Finally, some number sequences are also ∗Corresponding author. Email addresses: esalturk�yildiz.edu.tr (E. Saltürk), isiap�yildiz.edu.tr (̇I. Şiap) http://www.ejpam.com 250 c© 2012 EJPAM All rights reserved. E. Saltürk, İ. Şiap / Eur. J. Pure Appl. Math, 5 (2012), 250-259 251 presented. In the sequel, we present some well known concepts and results in both coding theory and algebra. Fq will denote the finite field with q elements where q is a prime power. A linear code C of length n over Fq is a subspace of Fn q . Definition 1. [8] For positive integers b 6= 1 and n, and all nonnegative integers k, the b-ary Gaussian binomial coefficients � n k � b are defined by � n 0 � b = 1, and � n k � b = (bn− 1)(bn−1 − 1) . . . (bn−k+1− 1) (bk − 1)(bk−1− 1) . . . (b− 1) , k = 1,2, . . . Theorem 1. [8] The number of distinct (although not necessarily inequivalent) [n, k]-codes over Fq is the q-ary Gaussian binomial coefficient � n k � q where q is a prime. For the proof of this theorem and some more details the reader is kindly directed to [8]. Definition 2. [13] A Galois ring is defined to be a finite ring with identity 1 such that the set of its zero divisors including 0 forms a principal ideal (p1) for some prime p where p1 = 1+ 1+ · · ·+ 1 ︸ ︷︷ ︸ p . It is well known that the characteristic a finite Galois ring is a prime power number. A finite Galois ring of characteristic pm and cardinality pmt where p is a prime number and m, t are positive integers is denoted by R = GR(pm, t). Besides some further remarks which will be given in the next section, more detailed and further information regarding Galois rings can be found in [9, 13]. Definition 3. An R submodule of Rn is called an R-linear code. Theorem 2. [6] A generator matrix of an GR(pm, t)-linear code C is equivalent to a linear code generated by       Ik1 A11 A12 · · · A1m 0 pIk2 pA22 · · · pA2m ... ... ... ... ... 0 0 · · · pm−1 Ikm−1 pm−1Amm       (1) where Ai j ’s denote matrices whose entries are from R and Ik1 , Ik2 , . . . , Ikm are identity matrices of sizes k1, k2, . . . , km respectively. A linear code C generated by a matrix (1) is called a (k1, k2, . . . , km)-type code. E. Saltürk, İ. Şiap / Eur. J. Pure Appl. Math, 5 (2012), 250-259 252 2. Codes over Galois rings A definition in a closed form for Galois rings is given in the previous section (Definition 2). Here, first we give an alternative description of a Galois ring which is constructive and it will be referred frequently. Define the following map [13] from polynomial ring Zpm[x] over Zpm to the polynomial Fp[x] over Fp: − : Zpm[x]→ Fp[x] a0+ a1 x + . . .+ an xn 7→ ā0 + ā1 x + . . .+ ān xn where x is an indeterminate over Zpm and also over Fp, āi ∈ Zp is the residue of ai ∈ Zpm and i = 0,1, . . . , n. Definition 4. [9] Let f (x) = a0 + a1 x + . . . + an xn be monic polynomial of degree d ¾ 1 in Zpm[x]. If f̄ (x) = ā0 + ā1 x + . . . + ān xn is irreducible in Fp[x], f (x) is called a monic basic irreducible polynomial in Zpm[x]. Let R = Zpm[ξ] where p is a prime and m is an integer. A Galois ring of characteristic pm and cardinality pmr is a ring isomorphic to R, where ξ is a primitive root of a basic irreducible polynomial f (x) of degree n. Obviously, R = Zpm[x]/〈 f (x)〉 and R = GR(pm, d), where 〈 f (x)〉 means the ideal gener- ated by f (x) and d is the degree of f (x). In the remaining part of the paper, R will be always referred as the ring GR(pm, d). Although R is not a vector space, we will nevertheless call its el- ements as “vectors” . The Galois ring R has elements of orders (pm)d , (pm−1)d , (pm−2)d , . . . , pd and the element zero is of order 1. Here, we give a formula for the number of distinct (not necessarily inequivalent) linear codes over R. We do the enumeration by constructing the generator matrices of those codes. Theorem 3. The number of distinct (not necessarily inequivalent) linear codes over R is NR k1,k2,...,ks (n) = � n k1, k2, . . . , ks � R = A B , (2) where A= ∏m t=1 ∏kt−1 i=0 ((p m−(t−1)) dn − (pm−1−(t−1)) dn ·d ∑t−1 j=0 k j ·pdi), and B = m∏ s=1 ks−1∏ r=0    s∏ z=1 (pm−(s−1))dkz m∏ j=s+1 (pm−( j−1))dk j −( s∏ z=1 (pm−s)dkz)(pm−(s+1))dks+1 · m∏ t=s+2 (pm−(t−1))dkt · pr ! Proof. In order to enumerate linear codes of length n and type (k1, k2, . . . , km) over R, we construct their generator matrices by choosing ordered ki R-linearly independent elements of order (pm−i+1)d , i ∈ {1,2, . . . , m} respectively. Let S = (v (pm)d 1 , v (pm)d 2 , . . . , v (pm)d k1 , v (pm−1)d 1 , . . . , v (pm−1)d k2 , . . . , v (p2)d 1 , . . . , v (p2)d km−1 , v (p)d 1 , . . . , v (p)d km ) E. Saltürk, İ. Şiap / Eur. J. Pure Appl. Math, 5 (2012), 250-259 253 be the ordered set of such elements where v ( j)d i denote the i th element of order ( j)d , p ≤ j ≤ pm, 1≤ i ≤ kw and w = 1,2, . . . , m. There are ((pm)d) n elements in Rn. In order to choose the first free vector, v (pm)d 1 , we subtract the number of elements which are not of order (pm)d from the whole group Rn. The elements of order (pm)d have at least one unit element of R in any of n components. The number of the unit elements of R is (pm)d − (pm−1)d since the number of elements which are not of order (pm)d in R is (pm−1)d . Since there are n choices for a unit in order to get an element of order (pm−1)d , we obtain the number (p(m−1)d ) n as the number of elements of Rn which are not of order (pm)d . We have ((pm)d)n− ((pm−1)d)n possibilities. For the second vector, v (pm)d 2 , we can take all vectors of order pm except the vectors which are linearly dependent with the first taken into account. Hence, we choose the second one such that 〈v(p m)d 1 , v (pm)d 2 〉 = C2 and |C2|= ((p m)d)2. The set of vectors that cannot be taken for the second vector is the following: K2 = {α1v1 (pm)d +w|w is not of order (pm)d and α1 ∈ Zp[ξ]}. Since |K2|= ((p m−1)d)npd , we have (((pm)d)n− ((pm−1)d)npd) possibilities for the second vector. Next, we choose v (pm)d 3 from Rn such that C3 = 〈C2 ∪ {v (pm)d 3 }〉 and |C3| = ((p m)d)3. While making this choice, again we exclude the set K3 = {α1v1 (pm)d +α2v2 (pm)d +w|o(w) 6= pm and α1,α2 ∈ Zp[ξ]}. Hence, we have (((pm)d)n− ((pm−1)d)np2d) ways to choose v (pm)d 3 since |K3| = ((p m−1)d)n(pd)2 possibilities. The same calculation for the remaining k1 − 3 vectors yields the following number (by considering all possibilities) (pmdn− p(m−1)dn)(pmdn− p(m−1)dnpd)(pmdn− p(m−1)dnp2d) . . . ((pm)n− (pm−1)npd(k1−1)) = k1−1∏ j=0 pmdn− p(m−1)dnpd j. Now, we choose k2 elements of order p(m−1)d and the first one is v (p(m−1)d) 1 such that Ck1+1 = 〈Ck1 ∪ {v(p (m−1)d) 1 }〉 and |Ck1+1| = (p md) k1 .(p(m−1)d) 1 . Here, we have to take into E. Saltürk, İ. Şiap / Eur. J. Pure Appl. Math, 5 (2012), 250-259 254 account the k1 elements which have been already considered of order pm that will contribute to the set of elements of order p(m−1)d . We consider the elements of the following set: Kk1+1 ={α1v1 pmd +α2v2 pmd + . . .+αk1 vk1 pmd +w|w is of order less or equal to p(m−1)d and αi ∈ Zp[ξ], i = 1,2, . . . , k1} which has elements of order less or equal to p(m−1)d . Since |Kk1+1| = (p (m−2)d)npdk1 and there are p(m−1)dn elements of order ≤ p(m−1)d in R, we have v (p(m−1)dn) 1 is (p(m−1)dn − p(m−2)dnpdk1) possibilities. The same calculation for the remaining k2 − 1 vectors yields the number {(p(m−1)d)n − (p(m−2)d )npdk1}{(p(m−1)d )n− (p(m−2)d)npdk1 pd}{(p(m−1)d )n− (p(m−2)d)npdk1 p2d} . . . {(p(m−1)d )n− (p(m−2)d)npdk1 pd(k2−1)}= k2−1∏ j=0 {(p(m−1)d) n − (p(m−2)d ) n pdk1 pd j}. Inductively, if the remaining ki, (i = 3,4, . . . , m), linearly independent vectors of orders (pm−i+1)d are chosen in a similar way, the we get A= m∏ t=1 kt−1∏ i=0 ((p(m−(t−1))d ) n − (p(m−1−(t−1))d ) n p ∑t−1 j=0 dk j pd i). possibilities. Analogously, the term B = m∏ s=1 ks−1∏ r=0    s∏ z=1 (pm−(s−1))dkz m∏ j=s+1 (pm−( j−1))dk j −( s∏ z=1 (pm−s)dkz)(pm−(s+1))dks+1 · m∏ t=s+2 (pm−(t−1))dkt .pr ! describes the number of bases determining linear codes of length n and type (k1, k2, . . . , km) over R. Here, the choices are taken from inside a linear code of length n and type (k1, k2, . . . , km). Such a code has (pmd) k1 .(p(m−1)d ) k2 . . . (p2d) km−1(p)dkm vectors. Hence the following ratio gives the result N = A B . Now we give a corollary for counting the linear codes over the first non trivial Galois ring Z4[ξ] of 16 elements. E. Saltürk, İ. Şiap / Eur. J. Pure Appl. Math, 5 (2012), 250-259 255 Corollary 1. The number of distinct linear codes of type (k1, k2) over Z4[ξ] is � n k1, k2 � Z4[ξ] = NR k1,k2 (n) = ∏k1−1 i=0 (16n− 4n+i) ∏k2−1 j=0 (4 n− 4k1+ j) ∏k1−1 t=0 (16k1.4k2 − 4k1+k2+t) ∏k2−1 l=0 (4 k1+k2 − 4k1+l) where ξ is a root of the basic irreducible polynomial 1+ x + x2 ∈ Z4[x]. Example 1. The number of distinct linear codes of length 3 and type (k1, k2) = (2,1) over Z4[ξ] is (163− 43)(163− 44)(43− 42) (1624− 424)(1624− 4242)(4241− 42) = 21. These linear codes are given by the following generator matrices:    1 0 x 0 1 x 0 0 2       1 x 0 0 2 0 0 0 1       2 0 0 0 1 0 0 0 1    where x ∈ {0,1,ξ, 1+ ξ} and ξ is a root of the polynomial 1+ x + x2. Definition 5. Let R be a Galois ring. An additive code of length n over R is subgroup of Rn. Here we emphasize that an additive code is actually a Z- submodule of Rn. On the other hand, a linear code is an R- submodule of Rn. Now we give the number of additive codes of a particular type over Galois rings. Theorem 4. The number of distinct (not necessarily inequivalent) additive codes over R is N+R k1,k2,...,ks (n) = � n k1, k2, . . . , ks �+ R = A B , (3) where A= ∏m t=1 ∏kt−1 i=0 ((p m−(t−1)) dn − (pm−1−(t−1)) dn .p ∑t−1 j=0 k j .pi), and B = m∏ s=1 ks−1∏ r=0    s∏ z=1 (pm−(s−1))kz m∏ j=s+1 (pm−( j−1))k j −( s∏ z=1 (pm−s)kz)(pm−(s+1))ks+1 · m∏ t=s+2 (pm−(t−1))kt · pr ! Proof. We prove the theorem similar to the proof of the Theorem 3. Here, we will take the additive orders of the elements of Zpm[ξ]. Corollary 2. The number of distinct additive codes of type (k1, k2) over Z4[ξ] is � n k1, k2 �+ Z4[ξ] = N+R k1,k2 (n) = ∏k1−1 i=0 (16n− 4n2i) ∏k2−1 j=0 (4 n− 2k1+ j) ∏k1−1 t=0 (4 k1 · 2k2 − 2k1+k2+t) ∏k2−1 l=0 (2 k1+k2 − 2k1+l) where ξ is a root of the polynomial 1+ x + x2. E. Saltürk, İ. Şiap / Eur. J. Pure Appl. Math, 5 (2012), 250-259 256 3. Generalized Gaussian Numbers In this section, we are interested in the properties of the numbers NR k1,k2,...,km (n). Since they resemble in some sense the Gaussian numbers we call these numbers Generalized Gaussian Numbers. Hence, we study some properties of these numbers. Some of the well known properties of the classical Gaussian binomial coefficients are as follows: Theorem 5. Assume the notations in Definition 1. Then, (i) � n k � q = � n n− k � q , (ii) � n 0 � q = � n n � q = 1, (iii) � n k � q = � n− 1 k− 1 � q + qk � n− 1 k � q , (iv) � n k � q = � n− 1 k � q + qn−k � n− 1 k− 1 � q , (v) limq→1 � n k � q = �n k � (binomial coefficient). Now we present some properties of Generalized Gaussian Numbers in the following theo- rem: Theorem 6. Let n be a positive integer, R= Zpm , (k ≤ n) and (ki ≤ n). Then, (i) If ∑m i=1 ki = n, then � n k1, k2, . . . , km � R = � n km, km−1, . . . , k1 � R , (ii) � n k1, k2, . . . , km � R = � n n− ∑m i=1 ki , km, km−1, . . . , k2 � R , (iii) � n+ 1 n− (k− 1), k, . . . , 0 � R = � n n− (k− 1), k− 1,0,0 . . . , 0 � R +pk � n n− k, k, 0,0 . . . , 0 � R , (iv) (p− 1) � n 0,0, . . . , k, 1 � R = (pn − 1) � n− 1 0,0, . . . , k, 0 � R , (v) � n n, 0,0, . . . , 0 � R = � n 0, n, 0, . . . , 0 � R = . . . = � n 0,0,0, . . . , n � R = 1. E. Saltürk, İ. Şiap / Eur. J. Pure Appl. Math, 5 (2012), 250-259 257 (vi) The followings hold: (vi).(1). � n k, 0,0, . . . , 0 � R = � n n− k, 0,0, . . . , 0 � R , (vi).(2). � n 0, k, 0, . . . , 0 � R = � n 0, n− k, 0, . . . , 0 � R , . . . . . . . . . . . . . . . . . . . . . (iv).(m). � n 0,0,0, . . . , k � R = � n 0,0,0, . . . , n− k � R . (vii) For m= 2,3, . . ., we have � n 0, k1, k2, . . . , km−1 � Zpm = � n k1, k2, . . . , km−1 � Z pm−1 . (viii) � n k, 0,0, . . . , 0 � R = (pk)n−k � n 0, k, 0, . . . , 0 � R = ((pk)n−k)2 � n 0,0, k, . . . , 0 � R = ((pk)n−k)3 � n 0,0,0, k, 0, . . . , 0 � R = · · ·= ((pk)n−k)m−1 � n 0,0,0, . . . , 0, k � R . Proof. The proof follows by applying the definitions carefully. The properties given above are generalizations of the given properties in [10]. Also very recently some similar studies are also done over different rings in [11]. In a similar approach to those works, there may be obtained some new and existing number sequences. Here we only give a few examples of number sequences. Table 1: Number of linear odes over Z4[ξ] for n= 2, n = 3 and n= 4. n (length) (k1, k2) Number n (length) (k1, k2) Number (0,1) 5 (0,1) 85 (0,2) 1 (0,2) 357 n=2 (1,0) 20 n (0,3) 85 (1,1) 5 (0,4) 31 (2,0) 1 (1,0) 5440 (0,1) 21 (1,1) 28560 (0,2) 21 n=4 (1,2) 7140 (0,3) 1 (1,3) 85 (1,0) 336 (2,0) 91392 (1,1) 420 (2,1) 85680 n=3 (1,2) 21 (2,2) 357 (2,0) 336 (3,0) 5440 (2,1) 21 (3,1) 85 (3,0) 1 (4,0) 1 REFERENCES 258 Table 1 is given as a special example of Theorem 6 for pm = 4. Here, for k1 = 0, k2 = 1, for the values of n, we obtain a sequence: 5,21,85,341,1365, . . .. This sequence exists in OEIS [12] by reference number A002450 and it is given by the formula 4n−1 3 . For k1 = 1, k2 = 0, we obtain a sequence: 20,336,5440, . . . which exists as A166984 in OEIS [12]. Moreover some new number sequences may be obtained by further examining the numbers obtained by fixing (k1, k2) and changing n. For instance, if we take k1 = 1, k2 = 1, then sequence: 5,420,28560,1855040 . . . does not exist in the literature [12]. 4. Conclusion In this paper, we have developed and proved a direct formula for the number of linear codes over the Galois Ring Zpm[ξ]. As an application of this formula, we generalize the properties given in [10] and name them Generalized Gaussian Numbers. A new number sequence is also presented. It is believed that the properties of Generalized Gaussian Numbers can be further explored. Also some more new sequences can be obtained from these numbers. ACKNOWLEDGEMENTS We would like to thank the referees for their remarks and sug- gestions. This research is supported by Yildiz Technical University Research Support Unit (2011-03-DOP01). References [1] G. Calugareanu. The total number of subgroups of a finite Abelian group. Scientiae Mathematicae Japonicae, 60:157-167, 2004. [2] S. Delsarte. Fonctions de Möbius sur les groupes abeliens finis, Annals of Math. 49:600- 609, 1948. [3] P.E. Djubjuk. On the number of subgroups of a finite abelian group, Izv. Akad. Nauk SSSR Ser. Mat., 12:351-378, 1948. [4] A.R. Hammons, P.V. Kumar, A.R. Calderbank, N.J.A. Sloane and P. Sole. The Z4-linearity of Kerdock, Preparata, Goethals and related codes. IEEE Transactions on Information Theory, 40:301-319, 1994. [5] T. Honold and I. Landjev. Linear codes over finite chain rings, The Electronic Journal of Combinatorics 7, 2000. [6] W.C. Huffman. Decompositions and extremal type II codes over Z4. IEEE Trans. Inf. Theory 44:800-809, 1998. [7] M. Ozen and I. Siap. Codes over Galois rings with respect to the Rosenbloom-Tsfasman metric. Special issue for ICMSAOŠ05 First International Conference On Modeling, Sim- ulation and Applied Optimization, The Franklin Institute Journal, 5:790-799, 2007. REFERENCES 259 [8] F.J. MacWilliams and N.J.A Sloane. The theory of error correcting codes. North-Holland Pub. Co., 1977. [9] B.R. McDonald, Finite rings with identity, Pure and Applied Mathematics. Marcel Dekker. 1974. [10] E. Saltürk and İ. Şiap. On the number of linear codes over Zpm , submitted. [11] E. Saltürk and İ. Şiap. The total number of linear codes over Fq + uFq, submitted. [12] N.J.A. Sloane. On-line encyclopedia of integer sequences. Published electronically at http://www.resear h.att. om/njas/sequen es. [13] Z.X. Wan. Quaternary codes. Series on Applied Mathematics, World Scientific Publisher Co., Singapore, 1997. [14] Y. Yeh. On prime power abelian groups. Bull. AMS, 54:323-327, 1948.