ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.284931 J. Algebra Comb. Discrete Appl. 4(2) • 181–188 Received: 15 June 2015 Accepted: 22 February 2016 Journal of Algebra Combinatorics Discrete Structures and Applications Essential idempotents and simplex codes∗ Research Article Gladys Chalom, Raul A. Ferraz, C. Polcino Milies Abstract: We define essential idempotents in group algebras and use them to prove that every mininmal abelian non-cyclic code is a repetition code. Also we use them to prove that every minimal abelian code is equivalent to a minimal cyclic code of the same length. Finally, we show that a binary cyclic code is simplex if and only if is of length of the form n = 2k − 1 and is generated by an essential idempotent. 2010 MSC: 16S34, 20C05, 94B15 Keywords: Group code, Essential idempotent, Simplex code 1. Introduction Let Fq be a finite field with q elements and m a positive integer. We recall that a linear code of length n over Fq is any proper subspace C of Fnq . Given a vector v = (a0,a1, . . . ,an−2,an−1) ∈C, its shift is the vector v1 = (an−1,a0,a1, . . . ,an−2). A linear code C is cyclic if, for every vector v ∈ C, its shift also belongs to C. Notice that the definition implies that if a vector v1 = (a0,a1, . . . ,an−2,an−1) is in C, then every vector obtained as a circular permutation of v is also in C. The map ψ : Fnq → Fq[X]/〈Xn−1〉 given by ψ(a0,a1, . . . ,am−2,am−1) = a0+a1X+· · · ,am−2Xm−2+ am−1X m−1 is an isomorphism of linear spaces and it is easy to see that a code C of length n over Fq is cyclic if and only its image ψ(C) is an ideal of the ring Fq[X]/〈Xn − 1〉. Since this ring is isomorphic to the group algebra of a cyclic group C, of order n, over Fq, we can think of cyclic codes as ideals in the group algebra FqC. More generally, an abelian code over Fq is any ideal in the group algebra FqA of a finite abelian group A. These codes were introduced independently by S.D. Berman [1] and MacWilliams [8]. ∗ This work was supported by FAPESP proc. 2009/52665-0 and CNPq 300243/79-0. Gladys Chalom, Raul A. Ferraz; Universidade de Sao Paulo, Brazil (email: agchalom@ime.usp.br, raul@ime.usp.br). C. Polcino Milies (Corresponding Author); Universidade de Sao Paulo and Univeersidade Federal do ABC, Brazil (email: polcino@ime.usp.br). 181 G. Chalom et al. / J. Algebra Comb. Discrete Appl. 4(2) (2017) 181–188 Since in the case when char(F) |6 |A| the group algebra FA is semisimple and all ideals are direct sums of the minimal ones, it is only natural to study minimal abelian code - or - equivalently, primitive idempotents - and these has been done by several authors (see, for example [6], [5], [4] [9] [12] [14]). Also, Sabin and Lomonaco [15] have shown that central codes in metacyclic group algebras are equivalent to abelian codes. In what follows, we shall show that these are not better than minimal cyclic codes. First, we prove in Corollary 2.5 that every minimal abelian non-cyclic code is a repetition code. Then, we show, in Theorem 3.3, that every minimal abelian code is equivalent to a minimal cyclic code of the same length. Finally, in section § 4, we show that essential idempotents can be used to characterize simplex codes. 2. Basic facts Throughout this paper all groups will be finite, and we shall always assume that the fields F consid- ered are such that char(F) |6 |G|. For an element α in the group algebra FG, the Hamming weight of α is the number of elements in its support; i.e., if α = ∑ g∈G αgg, then ω(α) = |{g ∈ G | αg 6= 0}|. Given an ideal I ⊂ FG the weight distribution of I is the map which assigns, to each possible weight t, the number of elements of I having weight t. Let H 6= {1} be a normal subgroup of a group G. Then Ĥ = 1 |H| ∑ h∈H h. is a central idempotent of FG and FG = FG · Ĥ ⊕FG · (1 − Ĥ). Remark 2.1. As shown in [11, Proposition 3.6.7] we have that FG · (1 − Ĥ) = ∆(G,H), the kernel of the natural projection π : FG → F[G/H] and it is easy to see that FG · Ĥ ∼= F[G/H] via the map ψ : FG · Ĥ → F[G/H] defined by g · Ĥ 7→ gH ∈ G/H. Also, if α ∈ FA · Ĥ, taking a transversal T of H in A we can rewrite α as α = ∑ t∈T ∑ h∈H αthth. As α ∈ FA · Ĥ, we have that α = αĤ = ∑ t∈T ∑ h∈H αththĤ = ∑ t∈T ∑ h∈H αthtĤ. So αth = αth′ for every h,h′ ∈ H and, setting αt = αth,∀h ∈ H we can write α = |H| ∑ t∈T αttĤ. (1) Since Ĥ is central, it is a sum of primitive central idempotents called its constituents. Given a primitive idempotent e we have that either eĤ = e or eĤ = 0, depending on wheather e is, or is not, a constituent of H. 182 G. Chalom et al. / J. Algebra Comb. Discrete Appl. 4(2) (2017) 181–188 In the first case, e is an element in the ideal FGĤ, and thus an element α in FGe is also in FGĤ. So, it can be written as in eqution 1. Writing T = {t1, t2, . . . , td} and H = {h1,h2, . . . ,hm}, the explicit expression of α is α = α1t1h1 + α1t1h2 + · · · + α1t1hm + · · · + αdtdh1 + αdtdh2 + · · · + αdtdhm. In terms of coding theory, this means that the code given by the minimal ideal FGe is a repetition code. We shall be interested in idempotents that are not of this type. Definition 2.2. A primitive idempotent e in the group algebra FG, is an essential idempotent if e · Ĥ = 0, for every subgroup H 6= (1) in G. A minimal ideal of FG is called an essential ideal if it is generated by an essential idempotent and non essential otherwise. Notice that, if e is a central idempotent, then the map π : G → Ge, given by π(g) = g ·e is a group epimorphism. We can use this map to characterize essential idempotents. Proposition 2.3. Let e ∈ FG be a primitive central idempotent. Then e is essential if and only if the map π : G → Ge, is a group isomorphism. Proof. Let e be essential and assume, by way of contradiction, that π is not a monomorphism. Then, there exists 1 6= g ∈ G such that π(g) = ge = e, hence also gie = e for every positive integer i. Thus 〈̂g〉 ·e = e, a contradiction. Conversely, assume that e is not essential. Then, there exists H 6= (1) such that eĤ = e. For every h ∈ H, we have that h · e = h · eĤ = Ĥ · e = e. Hence H ⊂ Ker(π) and thus π is not injective. Consequently, if π is an isomorphism, e is essential. Corollary 2.4. If G is abelian and FG contains an essential idempotent, then G is cyclic. Proof. If e ∈ FG is essential, then G ∼= Ge ⊂ FGe. As G is abelian, a simple component FGe of FG is a field and Ge, being a finite subgroup contained in it, is cyclic. In terms of coding theory, the result above gives the following. Corollary 2.5. Let A be an abelian non-cyclic group. Then, for any finite field Fq, all the minimal codes of FqA are repetition codes. We wish to show, on the other hand, that if G is a cyclic group, then FG always contains an essential idempotent. To do so, assume that G is cyclic of order n = pn11 · · ·p nt t . Then, G can be written as a direct product G = C1 ×···×Ct, where Ci is cyclic, of order pnii , 1 ≤ i ≤ t. Let Ki be the minimal subgroup of Ci; i.e. the unique subgroup of order pi in Ci and denote by ai a generator of this subgroup, 1 ≤ i ≤ t. Set e0 = (1 − K̂1) · · ·(1 − K̂t) =  1 − (1 + a1 + · · · + apn1−111 ) p1   · · ·  1 − (1 + at + · · · + apnt−1tt ) pt   . Then e0 is a central idempotent and we claim that it is non zero. In fact, it is easy to see that the coefficient of a1 · · ·at in this expression is (−1)t(1/p1) · · ·(1/pt) so, e0 6= 0. Theorem 2.6. Let G be a cyclic group. Then, a primitive idempotent e ∈ FG is essential if and only if e ·e0 = e. 183 G. Chalom et al. / J. Algebra Comb. Discrete Appl. 4(2) (2017) 181–188 Proof. Let e ∈ FG be essential. Then, in particular, eK̂i = 0, so e(1 − K̂i) = e, 1 ≤ i ≤ t. Hence e ·e0 = e(1 − K̂1)(1 − K̂2) · · ·(1 − K̂t) = e · (1 − K̂2) · · ·(1 − K̂t) = · · · = e. Conversely, if e is not essential then there exists a subgroup H of G such that e · Ĥ = e. There exists a minimal subgroup Ki ⊂ H, and for this subgroup we have that Ĥ(1 − K̂i) = Ĥ − ĤK̂i = 0. Consequently Ĥ ·e0 = 0. Hence: e ·e0 = (e · Ĥ) ·e0 = e · (Ĥ ·e0) = 0. Remark 2.7. Notice that the previous theorem actually shows that e0 is the sum of all the essential idempotents of FG and, consequently, the simple components of the ideal FGe0 are precisely the essential ideals. Since e0 is non zero, we have the following. Corollary 2.8. Let G be a cyclic group and F a field such that char(F) |6 |G|. Then, FG always contains an essencial idempotent. 3. The equivalence Let F be a field, A be a finite abelian group such that char(F) |6 |A| and e 6= Â an idempotent in FA. Set He = {g ∈ G | ge = e}. (2) Clearly, He is the unique maximal subgroup of G is such that Hee = e and it can be shown easily that He = G if and only if e = Ĝ, the principal idempotent of FG. Actually, He is the kernel of the irreducible representation associated to the simple component FG ·e. Theorem 3.1. Let e 6= Â be a primitive idempotent of FA and ψ the natural projection defined in Remark 2.1. Then, the element ψ(e) is an essential idempotent of F[A/He]. Proof. Let K 6= 1 be a non-trivial subgroup of A/He. Then, it is of the form K = K/He where K 6= He is a subgroup of A containing He. Let T be a transversal of He in K. Then K̂ = 1 |K| ∑ k∈K k = |He| |K| ∑ t∈T tĤe = 1 |K| ∑ t∈T tĤe. As ψ(Ĥe)=1, we have ψ(K̂) = 1 |K| ∑ t∈T ψ(t) = 1 |K| ∑ t∈T tHe = K̂. Then ψ(e) ·K = ψ(e) ·ψ(K̂) = ψ(e · K̂) = 0, as K 6⊂ He. Corollary 3.2. Let e 6= Â be a primitive idempotent of FA. Then, the factor group A/He is cyclic. 184 G. Chalom et al. / J. Algebra Comb. Discrete Appl. 4(2) (2017) 181–188 Proof. This fact follows immediately from Proposition 3.1 above and Corollary 2.4. Let G1 and G2 denote two finite groups of the same order, F a field, and let γ : G1 → G2 be a biijection. Denote by γ : FG1 → FG2 its linear extension to the corresponding group algebras. Clearly, γ is a Hamming isometry; i.e., elements corresponding under this map have the same Ham- ming weight. Ideals I1 ⊂ FG1 and I2 ⊂ FG2 such that γ(I1) = I2 are thus equivalent, in the sense that they have the same dimension and the same weight distribution. In this case, the codes I1 and I2 are said to be permutation equivalent and were called combinatorially equivalent in [15]. In what follows, we will show that every minimal ideal of an abelian group algebra FA is permutation equivalent to a minimal ideal of the group algebra of a cyclic group of the same length. Let A be an abelian group of order n, F a field, I a minimal ideal of FA and e be the primitive idempotent generating I. Let He be the subgroup defined in (2) and let C be a cyclic group of the same order n. If He = A then e = Â and any bijection σ : A → C is such that I = FAe = Fe is mapped to FCĈ, so I is equivalent to FCĈ. So, assume that He 6= A. Since the order d of the factor group A/He is a divisor of n, there exists a unique subgroup K of C such that |A/He| = |C/K| = d and, as they are both cyclic groups, we have that A/He ∼= C/K. (3) So, also F[A/He] ∼= F[C/K] and FA · Ĥe ∼= F[A/He] ∼= F[C/K] ∼= FC · K̂. Denote by µ : F[A/He] → F[C/K] and θ : FA · Ĥe → FC · K̂ realizing these isomorphisms. Let a ∈ A be an element such that a = aHe is a generator of A/He. Then {1,a,a2, . . . ,ad−1} is a transversal of He in A and we can write A = {aih | 0 ≤ i ≤ d− 1, h ∈ He}. Similarly, if t ∈ C is such that t = tK = µ(aHe), it is a generator of C/K and we can write C = {tik | 0 ≤ i ≤ d− 1, k ∈ K}. As He and K have the same order, we can choose a bijection f : He → K and define a map η : A → C by η(aih) = tif(h), for all aih ∈ A. Given an element α ∈ FA · Ĥe, using formula (1) we can write it in the form α = |He| d−1∑ i=0 αia i · Ĥe, and, taking into account that |He| = |K|, we compute θ(α) = µ ( |He| d−1∑ i=0 αiā i ) = |K| d−1∑ i=0 αit iK̂ = d−1∑ i=0 αit i ( ∑ h∈He f(h) ) . Comparing the expressions of α and θ(α) it is clear that the linear extension of η : A → C to FA coincides with θ on FA · Ĥe, and it is such that θ(FA · Ĥe) = FC · K̂. Notice that FA · e ⊂ FA · Ĥe and thus e is primitive also in FA · Ĥe, so e′ = θ(e) is primitive in FC · K̂. 185 G. Chalom et al. / J. Algebra Comb. Discrete Appl. 4(2) (2017) 181–188 We claim that e′ is also primitive in FC. In fact, assume that e′ = f1 + f2, with f1,f2 orthogonal idempotents in FC. Then e′ ·K̂ = f1K̂ + f2K̂ is a decomposition of e′ in FC ·K̂. Hence, either f1K̂ = 0 and f2K̂ = e′ or vice-versa. So either f1 = f1e′ = f1e′K̂ = 0 or, in a similar way, f2 = 0. Hence, we have shown the following. Theorem 3.3. Every minimal ideal in the semisimple group algebra FA of a finite abelian group A is permutation equivalent to a minimal ideal in the group algebra FC of a cyclic group C of the same order. It should be noted that non minimal abelian codes can actually be more convenient than the cyclic ones (see, for example, [7], [10] and [13]). 4. Binary simplex codes Set r = dimFqC and let B = {v1,v2, . . . ,vr} be a basis of C over Fq. We shall denote by GB the generating matrix of C; i.e. the matrix whose rows are the componentes of the vectors of B, when written in the basis B of FqC. We start with a very simple remark. Lemma 4.1. The matrix GB contains no zero columns. Proof. In fact, assume that the jth column of the given matrix is zero. Then, the jth component of every vector in C is equal to 0. Take any non-zero vector v ∈C. So it has at least one component which is equal to 1. Since every shift of v is in C, there exists a vector in C whose jth component is equal to 1, a contradiction. Notice also that, if a matrix GB has two columns, in positions i and j, say, that are equal to one another, then the ith component of every vector in C is equal to its jth component. Hence, we have shown the following. Lemma 4.2. The columns of a matrix GB are pairwise different for a given basis B of C, if and only if the columns of generating matrices are pairwise different, for every basis of C. Set F = Fq · e. Then F is an isomorphic copy of Fq contained in FqC · e. Notice that, since g is a generator of C, we have that F[ge] = FqC ·e. Then, the evaluation mapping ϕ : F[X] → FqC ·e given by ϕ(f) = f(ge), for all f ∈ F[X], is an epimorphism and we have that FqC ·e ∼= F[X] Ker(ϕ) . Notice that Ker(ϕ) = 〈h〉, for some h ∈ F[X], which is a polinomial of minimal degree having ge as a root. Since dimFFqC ·e = dimFq FqC ·e = r we have that the degree of h is precisely r and there exist coeficients b0, . . . ,br−1 in F such that gre = br−1g r−1e + · · · + b0. This clearly implies that B0 = {e,ge, . . . ,gr−1e} is a basis of FqC ·e over F and also over Fq. Moreover, we have the following. Theorem 4.3. For every basis B of C the generating matrix GB has pairwise different columns if and only if the mapping ψ : C → C ·e is an isomorphism. 186 G. Chalom et al. / J. Algebra Comb. Discrete Appl. 4(2) (2017) 181–188 Proof. Notice that FqC ·e is of dimension r over Fq, it contains qr elements. Suppose, by way of contradiction, the ψ is not injective. Then, there exists an index j, 0 < j < n, such that e = gje. Write e = a0 + a1g + · · · + an−1gn−1. Then gje = a0gj + a1gj+1 + · · · + an−1gj+n−1. Since e = gje, we have that ai = ai+j, 0 ≤ i ≤ n − 1, where the subindexes are taken modulo n. This shows that if G denotes the generating matrix with respect to the basis B then, the first column of G is equal to its jth column. Conversely, assume that ψ is an isomorphism and, by way of contradiction, that there exists a basis whose corresponding generating matrix has two equal columns, in positions i and j, say. In view of Lemma 4.2 we can assume, without loss of generality, that this basis is precisely the basis B0. This means that ai+t = aj+t or, equivalently, that at = at+j−i, for all t, where indexes are taken, again, modulo n. This readily implies that e = gj−ie. Recall that a binary linear code of dimension k and length n is called simplex if a generating matrix for the code contains all possible non zero columns of length k. Since these are 2k − 1 in number, this matrix must be of size k × (2k − 1) so, we must have n = 2k − 1. Theorem 4.4. Let C be a binary linear code of dimension k and length n = 2k −1. Then C is a simplex code if and only if it is essential. Proof. Assume that C is simplex. Since all its columns are different, it follows from Theorem 4.3 that the mapping ψ : C → C · e is an isomorphism. To prove thar e is an essential idempotent we are only left to prove that it is primitive. Notice that C ·e ⊂ F2C ·e\{0}. Since F2C ·e = C is of dimension k over F2, it contains 2k elements. Hence |F2C ·e\{0}| = n = |C|, showing that actually C ·e = F2C ·e\{0}. This means that every non zero element in FC ·e is invertible and thus, it is a field. Consequently, e is primitive. As a consequence, and taking the results in [3] into account, we can state the following. Corollary 4.5. Every binary linear code of constant weight is a repetition of a code generated by an essential idempotent. References [1] S. D. Berman, Semisimple cyclic and abelian codes. II, Kibernetika 3(3) (1967) 21–30. [2] S. D. Berman, On the theory of group codes, Kibernetika 3(1) (1967) 31–39. [3] A. Bonisoli, Every equidistant linear code is a sequence of dual Hamming codes, Ars Combin. 18 (1984) 181–186. [4] R. A. Ferraz, M. Guerreiro, C. P. Milies, G−equivalence in group algebras and minimal abelian codes, IEEE Trans. Inform. Theory 60(1) (2014) 252–260. [5] R. A. Ferraz, C. P. Milies, Idempotents in group algebras and minimal abelian codes, Finite Fields Appl. 13(2) (2007) 382–393. [6] P. Grover, A. K. Bhandari, Explicit determination of certain minimal abelian codes and their mini- mum distance, Asian–European J. Math. 5(1) (2012) 1–24. [7] J. Jensen, The concatenated structure of cyclic and abelian codes, IEEE Trans. Inform. Theory 31(6) (1985) 788–793. [8] F. J. Mac Williams, Binary codes which are ideals in the group algebra of an abelian group, Bell System Tech. J. 49(6) (1970) 987–1011. 187 http://dx.doi.org/10.1007/BF01119999 http://dx.doi.org/10.1007/BF01072842 http://www.ams.org/mathscinet-getitem?mr=823843 http://www.ams.org/mathscinet-getitem?mr=823843 http://dx.doi.org/10.1109/TIT.2013.2284211 http://dx.doi.org/10.1109/TIT.2013.2284211 http://dx.doi.org/10.1016/j.ffa.2005.09.007 http://dx.doi.org/10.1016/j.ffa.2005.09.007 http://dx.doi.org/10.1142/S1793557112500027 http://dx.doi.org/10.1142/S1793557112500027 http://dx.doi.org/10.1109/TIT.1985.1057109 http://dx.doi.org/10.1109/TIT.1985.1057109 http://dx.doi.org/10.1002/j.1538-7305.1970.tb01812.x http://dx.doi.org/10.1002/j.1538-7305.1970.tb01812.x G. Chalom et al. / J. Algebra Comb. Discrete Appl. 4(2) (2017) 181–188 [9] R. L. Miller, Minimal codes in abelian group algebras, J. Combinatorial Theory Ser A 26(2) (1979) 166–178. [10] C. P. Milies, F. D. de Melo, On cyclic and abelian codes, IEEE Trans. Information Theory 59(11) (2013) 7314–7319. [11] C. Polcino Milies, S. K. Sehgal, An Introduction to Group Rings, Algebras and Applications, Kluwer Academic Publishers, Dortrecht, 2002. [12] A. Poli, Construction of primitive idempotents for a variable codes, Applied Algebra, Algorithmics and Error–Correcting Codes: 2nd International Conference, AAECC–2 Toulouse, France, October 1–5, 1984 Proceedings (1986) 25–35. [13] R. E. Sabin, On minimum distance bounds for abelian codes, Appl. Algebra Engrg. Comm. Comput. 3(3) (1992) 183–197. [14] R. E. Sabin, On determining all codes in semi–simple group rings, Applied Algebra, Algebraic Algo- rithms and Error–Correcting Codes: 10th International Symposium,AAECC-10 San Juan de Puerto Rico, Puerto Rico, May 10–14, 1993 Proceedings (1993) 279–290. [15] R. E. Sabin, S. J. Lomonaco, Metacyclic error–correcting codes, Appl. Algebra Engrg. Comm. Com- put. 6(3) (1995) 191–210. 188 http://dx.doi.org/10.1016/0097-3165(79)90066-9 http://dx.doi.org/10.1016/0097-3165(79)90066-9 http://dx.doi.org/10.1109/TIT.2013.2275111 http://dx.doi.org/10.1109/TIT.2013.2275111 http://dx.doi.org/10.1007/3-540-16767-6_48 http://dx.doi.org/10.1007/3-540-16767-6_48 http://dx.doi.org/10.1007/3-540-16767-6_48 http://dx.doi.org/10.1007/BF01268659 http://dx.doi.org/10.1007/BF01268659 http://dx.doi.org/10.1007/3-540-56686-4_50 http://dx.doi.org/10.1007/3-540-56686-4_50 http://dx.doi.org/10.1007/3-540-56686-4_50 http://dx.doi.org/10.1007/BF01195337 http://dx.doi.org/10.1007/BF01195337 Introduction Basic facts The equivalence Binary simplex codes References