ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.369864 J. Algebra Comb. Discrete Appl. 5(1) • 45–49 Received: 11 February 2017 Accepted: 1 September 2017 Journal of Algebra Combinatorics Discrete Structures and Applications No MacWilliams duality for codes over nonabelian groups Research Article M. Ryan Julian Jr. Abstract: Dougherty, Kim, and Solé [3] have asked whether there is a duality theory and a MacWilliams formula for codes over nonabelian groups, or more generally, whether there is any subclass of nonabelian groups which have such a duality theory. We answer this in the negative by showing that there does not exist a nonabelian group G with a duality theory on the subgroups of Gn for all n. 2010 MSC: 94B60, 20E15 Keywords: Dual code, Subgroup lattice, MacWilliams identity, Iwasawa group 1. Introduction For codes over finite fields, C ⊂ Fnq , the usual inner product for vectors over Fnq produces a well established duality theory between C and C⊥ = {x ∈ Fnq |〈x,c〉 = 0 ∀c ∈ C}. Furthermore, the weight enumerator polynomials for a pair of dual codes are related by the famous MacWilliams identity, which for codes over F2 takes the form W(C⊥; x,y) = 1|C|W(C; y−x,y +x). There are a number of generalizations of this result that cover different types of weight enumerators as well as codes over different algebraic objects, including abelian groups. Dougherty, Kim, and Solé [3] asked whether it is possible to extend these results to nonabelian groups. In particular, they asked “Is there a subclass of nonabelian groups for which a duality and a MacWilliams formula exist?” We will answer this question under the assumption that a code over a group G is defined to be a subgroup of Gn, in analogy to the usual definition of codes over abelian groups. Our approach will refrain from choosing a particular definition of a dual code, and instead we will determine whether any suitable choice exists that can provide a duality satisfying our Definition 2.1. It remains open whether there is some other definition of a code over a group G that might better generalize the existing theory of codes over abelian groups, allowing duality to rely on something other than just the subgroup structure. When they posed the question, Dougherty, Kim, and Solé [3] had already identified one particular difficulty in finding a duality theory for nonabelian groups. They observed that the subgroups of the M. Ryan Julian Jr.; University of Wisconsin - Madison, United States (email: mrjulian@math.wisc.edu). 45 http://orcid.org/0000-0002-6117-1415 M. R. Julian / J. Algebra Comb. Discrete Appl. 5(1) (2018) 45–49 quaternion group {±1,±i,±j,±k} do not form a self-dual subgroup lattice. This group has three sub- groups of order 4, namely {±1,±i}, {±1,±j}, and {±1,±k}, but only one subgroup of order 2, {±1}. So if we expect codes over G and their duals to be subgroups of Gn with the property that |C||C⊥| = |G|n, then we would need to restrict our attention to some subclass of nonabelian groups that does not include the quaternions. Pursuing this line of thought, instead of looking for an inner product that might produce a duality theory, as is done for finite fields and abelian groups, we focus on the structures of subgroup lattices. If a nonabelian group G is to have a duality theory for the subgroups of Gn, it would be necessary for the subgroup lattice of Gn to be self-dual. Fortunately, subgroup lattices with duals have already been classified. In the 1950’s, Suzuki determined which finite solvable groups have duals [6], and Zacher was able to prove ten years later that all finite groups with duals are solvable [7]. We will apply this classification to show that if G is a finite nonabelian group with a self-dual subgroup lattice, then G×G will not have a self-dual subgroup lattice. As a corollary, there cannot exist any nonabelian finite group G with the property that Gn has a self-dual subgroup lattice for all n. While we can define a code over a nonabelian group G to be a subgroup of Gn, there is no subclass of nonabelian groups that will support a duality theory with this definition. 2. Self-dual subgroup lattices Since our approach to this problem takes us into the theory of subgroup lattices, we will need to begin with a quick tour through the relevant terminology. Definition 2.1. Let L(G) denote the subgroup lattice of a group G. We say G has a dual group Ḡ if there exists a bijective map δ : L(G) → L(Ḡ) such that for all H,K ∈ L(G), H ≤ K if and only if δ(K) ≤ δ(H). We are interested in groups that are self-dual, i.e. groups G with a dual Ḡ ∼= G. Observe that if Gn was self-dual, then by defining a code over G to be a subgroup of Gn, the duality map for Gn would take a code C to a dual code C⊥. This is the same arrangement that works to produce dual codes over finite fields and abelian groups, but in those cases the duality map can be produced by appealing to an inner product. Without an inner product structure to fall back on for nonabelian groups, we instead depend on studying the subgroup lattices. We will make use of the classification of finite groups with duals given in Chapter 8 of Schmidt’s book on subgroup lattices [5], but the classification requires a bit of specialized terminology. Definition 2.2. A finite group G is called a P-group if it is: 1. an elementary abelian group of prime power order, or 2. a group which can be decomposed as G = SpSq, where Sp is a p-Sylow subgroup which is an abelian P-group, Sq is a cyclic q-Sylow subgroup of order q, Sq =< B >, and for any element A of Sp we have BAB−1 = Ar, r 6≡ 1, rq ≡ 1 (mod p). Definition 2.3. A modular lattice is a lattice that satisfies the condition x ≤ b implies x ∨ (a ∧ b) = (x ∨ a) ∧ b for any lattice element a, where ∨ and ∧ are the join and meet operations on the lattice. Groups with modular subgroup lattices are called Iwasawa groups. Since p-groups with modular subgroup lattices have already been classified by Iwasawa [4], we will not actually need to work much with this definition, but we include it for completeness. Definition 2.4. A Hamiltonian group is a nonabelian group G such that every subgroup of G is normal. 46 http://orcid.org/0000-0002-6117-1415 M. R. Julian / J. Algebra Comb. Discrete Appl. 5(1) (2018) 45–49 The smallest example of a Hamiltonian group is the quaternion group of order 8 that we met earlier, and, in fact, Dedekind showed that every Hamiltonian group is the direct product of the quaternion group with some other abelian group [2]. We have already seen that the subgroup lattice of the quaternions is not self-dual. So it is perhaps unsurprising that in our attempts to understand self-dual subgroup lattices we will be applying a theorem [5] that instructs us to focus our attention on non-Hamiltonian groups. Theorem 2.5. A finite group G has a dual if and only if G is a direct product of finite coprime groups Gλ such that each Gλ is a P-group or a non-Hamiltonian p-group with a modular subgroup lattice. In particular, if G is self-dual, it must satisfy this condition. To use this classification to understand codes over G (e.g. subgroups of Gn), we must understand the direct products of P-groups and of non- Hamiltonian p-groups with modular subgroup lattices with themselves. We will examine these first before tackling the main theorem. 3. Direct products Lemma 3.1. If G is a nonabelian P-group, then G×G is not a P-group. Proof. From the definition above, a nonabelian P-group must be the semidirect product of an elemen- tary abelian group of order pk and a cyclic group of prime order q (along with some additional structure). In particular, |G| = pkq, so |G × G| = p2kq2. Then G × G cannot be a P-group, since the order of nonabelian P-groups must be of the form p`q for primes p and q. To handle the case where G is a non-Hamiltonian p-group with a modular subgroup lattice, we will apply a theorem of Iwasawa [4]. Theorem 3.2. If G is a non-Hamiltonian nonabelian p-group with a modular subgroup lattice, then G contains an abelian normal subgroup N such that G/N =< q > is cyclic and for all n ∈ N, q−1nq = n1+p s , where s ≥ 1 (s ≥ 2 if p = 2). In fact, to show that this property cannot hold for both G and G × G, we actually only need an abelian normal subgroup with a cyclic quotient. The further structure described in Iwasawa’s theorem is unnecessary for the following lemma. Lemma 3.3. If G is a nonabelian group, then G and G×G cannot both be non-Hamiltonian p-groups with modular subgroup lattices. Proof. Suppose that both G and G×G are non-Hamiltonian p-groups with modular subgroup lattices. Let N be an abelian normal subgroup of G×G such that (G×G)/N is cyclic, and let p1 and p2 be the standard projections G×G → G. Observe that if p1(N) 6= G and p2(N) 6= G, then (G×G)/N cannot be cyclic, since (G × G)/N would have a non-cyclic quotient. In particular, since N ⊆ p1(N) × p2(N) and p1(N) and p2(N) are normal in G, we have ((G×G)/N) / ((p1(N) ×p2(N))/N) ∼= (G×G)/(p1(N) ×p2(N)) ∼= (G/p1(N)) × (G/p2(N)), and since p1(N) 6= G and p2(N) 6= G, we claim that (G/p1(N)) × (G/p2(N)) is not cyclic. To confirm this claim, we first observe that G/p1(N) and G/p2(N) are p-groups of orders pa and pb, respectively for some integers a and b. Since p1(N) 6= G and p2(N) 6= G, we know that a,b > 0. Then (G/p1(N))×(G/p2(N)) is a group of order papb = pa+b. Suppose that g1 ∈ G/p1(N) and g2 ∈ G/p2(N) with |g1| = pc and |g2| = pd. Then (g1,g2) ∈ (G/p1(N)) × (G/p2(N)) and |(g1,g2)| = lcm(|g1|, |g2|) = lcm(pc,pd) = pmax(c,d). Since c ≤ a, d ≤ b, and a,b > 0, we have that pmax(c,d) < pa+b, so (g1,g2) cannot 47 http://orcid.org/0000-0002-6117-1415 M. R. Julian / J. Algebra Comb. Discrete Appl. 5(1) (2018) 45–49 generate (G/p1(N)) × (G/p2(N)). Since no element of (G/p1(N)) × (G/p2(N)) can generate the entire group, (G/p1(N)) × (G/p2(N)) cannot be cyclic. So, for some i ∈ {1, 2}, pi(N) = G. But this contradicts the existence of such an abelian normal subgroup N, since N was chosen to be abelian while G is nonabelian and abelian groups cannot project onto nonabelian groups. There is already a result in the literature [1] that states the following: a nonabelian non-Hamiltonian p-group P = P1 ×P2 is an Iwasawa group if and only if P1 and P2 are Iwasawa and, for i = 1 or i = 2, Pi is abelian such that Exp(Pi) ≤ ps and s is the integer that comes from the nonabelian factor Pj for j 6= i. Our second lemma would be a direct corollary of this result. Unfortunately, the published proof is incorrect, since after establishing elements of P such that xk1a ` 1a ` 2 = x1a 1+ps1 1 a2, the author claims without any further justification that this implies that either ` = 1 or ` = 1 + ps1. Without this step, there remains a gap in the published proof, so our proof above can be considered a partial correction of that result. 4. The main theorem With these lemmas in hand, we are now ready to prove the main theorem. Theorem 4.1. If G is a finite nonabelian group with a self-dual subgroup lattice, then G×G does not have a self-dual subgroup lattice. Proof. First, if G is a finite nonabelian group with a self-dual subgroup lattice, then by theorem (2.5) G can be expressed as G = ⊕ Gλ, where the Gλ are coprime and each Gλ is either a P-group or a non-Hamiltonian p-group with a modular subgroup lattice. Then G×G = ⊕ (Gλ ×Gλ), and since the Gλ×Gλ are still coprime, it suffices to check whether it is possible for each Gλ×Gλ to still be a P-group or a non-Hamiltonian p-group with a modular subgroup lattice. By theorem (3.1), we know that this will not work if Gλ is a P-group, and by theorem (3.3), we know that this will also not work if Gλ is a non-Hamiltonian p-group with a modular subgroup lattice. Thus we can conclude that if G is a finite nonabelian group with a self-dual subgroup lattice, then G × G cannot also have a self-dual subgroup lattice. 5. Conclusion This result shows that there does not exist any finite nonabelian group G so that Gn has a duality theory for all n. So if we define a code over a nonabelian group G to be a subgroup of Gn, then our coding theory over nonabelian groups cannot have a MacWilliams-type duality theory, and there is no subclass of nonabelian groups where a duality theory could be recovered. Some variations of Dougherty, Kim, and Solé’s question remain open. For example, one could change our definition so that codes over G are not restricted to be subgroups of Gn, and ask whether some other collection of codes could produce meaningful self-dual lattices. Another possibility would be to relax our demands for the duality map. Although our work goes a long way towards describing the boundary between classes of codes with and without duality, the most general form of Dougherty, Kim, and Solé’s question, “Find the largest class of algebraic structures A for which a duality and MacWilliams relations hold” remains a target for future research. 48 http://orcid.org/0000-0002-6117-1415 M. R. Julian / J. Algebra Comb. Discrete Appl. 5(1) (2018) 45–49 References [1] J. Chifman, Note on direct products of certain classes of finite groups, Commun. Algebra 37(5) (2009) 1831–1842. [2] R. Dedekind, Ueber Gruppen, deren sämmtliche Theiler Normaltheiler sind, Math. Ann. 48(4) (1897) 548–561. [3] S. Dougherty, J.-L. Kim, P. Solé, Open problems in coding theory, Contemp. Math. 634 (2015) 79–99. [4] K. Iwasawa, Über die endlichen Gruppen und die Verbände ihrer Untergruppen, J. Fac. Sci. Imp. Univ. Tokyo. Sect. I. 4 (1941) 171–199. [5] R. Schmidt, Subgroup Lattices of Groups, Walter de Gruyter, Berlin, 1994. [6] M. Suzuki, On the lattice of subgroups of finite groups, Trans. Amer. Math. Soc. 70(2) (1951) 345–371. [7] G. Zacher, Caratterizzazione dei gruppi immagini omomorfe duali di un gruppo finito, Rend. Sem. Mat. Univ. Padova 31 (1961) 412–422. 49 http://orcid.org/0000-0002-6117-1415 http://dx.doi.org/10.1080/00927870802070322 http://dx.doi.org/10.1080/00927870802070322 http://doi.org/10.1007/BF01447922 http://doi.org/10.1007/BF01447922 http://www.ams.org/mathscinet-getitem?mr=3307391 http://www.ams.org/mathscinet-getitem?mr=5721 http://www.ams.org/mathscinet-getitem?mr=5721 http://www.ams.org/mathscinet-getitem?mr=1292462 http://dx.doi.org/10.2307/1990375 http://www.ams.org/mathscinet-getitem?mr=140566 http://www.ams.org/mathscinet-getitem?mr=140566 Introduction Self-dual subgroup lattices Direct products The main theorem Conclusion References