On Extremal Self-Dual Ternary Codes of Length 48

(1)

International Journal of Combinatorics Volume 2012, Article ID 154281,9pages doi:10.1155/2012/154281

Research Article

On Extremal Self-Dual Ternary Codes of Length 48

Gabriele Nebe

Lehrstuhl D f ¨ur Mathematik, RWTH Aachen University, 52056 Aachen, Germany

Correspondence should be addressed to Gabriele Nebe,[email protected] Received 6 September 2011; Accepted 7 January 2012

Academic Editor: Ch´ınh T. Hoang

Copyrightq2012 Gabriele Nebe. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

All extremal ternary self-dual codes of length 48 that have some automorphism of prime order p ≥ 5 are equivalent to one of the two known codes, the Pless code or the extended quadratic residue code.

1. Introduction.

The notion of an extremal self-dual code has been introduced in1. As Gleason2remarks one may use invariance properties of the weight enumerator of a self-dual code to deduce upper bounds on the minimum distance. Extremal codes are self-dual codes that achieve these bounds. The most wanted extremal code is a binary self-dual doubly even code of length 72 and minimum distance 16. One frequently used strategy is to classify extremal codes with a given automorphism, see3,4for the first papers on this subject.

Ternary codes with a given automorphism have been studied in5. The minimum dis- tancedC :min{wtc |0/c∈ C}of a self-dual ternary codeC C^⊥ ≤ Fⁿ₃ of lengthnis bounded by

dC≤3n 12

3. 1.1

Codes achieving equality are called extremal. Of particular interest are extremal ternary codes of length a multiple of 12. There exists a unique extremal code of length 12the extended ternary Golay code, two extremal codes of length 24the extended quadratic residue code Q₂₄ : QR23, 3and the Pless codeP₂₄. For length 36, the Pless code yields one example of an extremal code. Reference5shows that this is the only code with an automorphism of prime orderp ≥5; a complete classification is yet unknown. The present paper investigates the extremal codes of length 48. There are two such codes known, the extended quadratic

(2)

residue codeQ48 and the Pless codeP48. The computer calculations described in this paper show that these two codes are the only extremal ternary codesCof length 48 for which the order of the automorphism group is divisible by some primep≥5. Theoretical arguments exclude all types of automorphisms that do not occur for the two known examples.

Any extremal ternary self-dual code of length 48 defines an extremal even unimodular lattice of dimension 486. A long-term project to find or even classify such lattices was my main motivation for this paper.

2. Automorphisms of Codes

LetFbe some finite field,F^∗its multiplicative group. For any monomial transformationσ ∈ Mon_nF : F^∗S_n, the imageπσ ∈ S_n is called the permutational part ofσ. Thenσhas a unique expression as

σdiagα1, . . . , α_nπσ mσπσ, 2.1

andmσis called the monomial part ofσ. For a codeC≤Fⁿwe let

MonC:{σ∈Mon_nF|σC C} 2.2

be the full monomial automorphism group ofC.

We call a code C ≤ Fⁿ an orthogonal direct sum, if there are codes Ci ≤ Fⁿⁱ 1≤i≤s >1of lengthnisuch that

C∼⊥^s

i1Ci

c₁¹, . . . , c¹_n₁, . . . , c^s₁ , . . . , c^s_n_s

|cⁱ∈Ci1≤i≤s

. 2.3

Lemma 2.1. LetC ≤Fⁿ not be an orthogonal direct sum. Then the kernel of the restriction ofπ to MonCis isomorphic toF^∗.

Proof. ClearlyF^∗CCsinceCis anF-subspace. Assume thatσ:diagα1, . . . , αn∈MonC withαi∈F^∗, not all equal. Let{α1, . . . , αn}{β1, . . . , βs}with pairwise distinctβi. Then

C⊥^s

i1ker σ−βiid

2.4 is the direct sum of eigenspaces ofσ. Moreover the standard basis is a basis of eigenvectors ofσso this is an orthogonal direct sum.

In the investigation of possible automorphisms of codes, the following strategy has proved to be very fruitful4,7.

Definition 2.2. Letσ∈MonCbe an automorphism ofC. Thenπσ∈S_nis a direct product of disjoint cycles of lengths dividing the order ofσ. In particular if the order ofσ is some primep, then we say thatσhas cycle typet, f, ifπσhastcycles of lengthpandf fixed pointssoptf n.

(3)

Lemma 2.3. Letσ∈MonChave prime orderp.

aIfpdoes not divide|F^∗|then there is some elementτ ∈Mon_nFsuch thatmτστ⁻¹ id.

ReplacingCbyτCone hence may assume thatmσ 1.

bAssume thatpdoes not divide charF,mσ 1, andπσ 1, . . . , p· · ·t−1p 1, . . . , tptp1· · ·n. ThenCCσ⊕E, where

Cσ

c∈C|c1· · ·cp, c_p1· · ·c2p, . . . , c_t−1p1· · ·ctp

2.5

is the fixed code ofσand

E

⎧⎨

⎩c∈C| p

i1

c_i 2p ip1

c_i· · · tp it−1p1

c_ic_tp1· · ·c_n 0

⎫⎬

⎭ 2.6

is the uniqueσ-invariant complement ofCσinC.

cDefine two projections

π_t:Cσ−→F^t, π_tc: c_p, c_2p, . . . , c_tp , πf :Cσ−→F^f, πfc: c_tp1, c_tp2, . . . , c_tpf

. 2.7

SoCσ∼ π_tCσ, πfCσ :Cσ^∗. IfCC^⊥is self-dual with respect tox, y: _n

i1xiyi, thenCσ^∗ ≤F^tf is a self-dual code with respect to the inner productx, y: _t

i1pxiyitf jt1xjyj.

dIn particular dimCσ tf/2 and dimE tp−1/2.

Proof. afollows from the Schur-Zassenhaus theorem in finite group theory. For the ternary case, see5, Lemma 1.

bandcare similar to4, Lemma 2.

In the following we will keep the notation of the previous lemma and regard the fixed codeCσ.

Remark 2.4. Iff≤dCthent≥f.

Proof. Otherwise the kernel K : kerπt {0, . . . ,0, c1, . . . , cf ∈ Cσ} is a nontrivial subcode of minimum distance≤f < dC.

The way to analyse the codeEfromLemma 2.3is based on the following remark.

Remark 2.5. Letp /charFbe some prime andσ∈MonnFan element of orderp. Let X^p−1 X−1g1· · ·g_m∈FX 2.8

(4)

be the factorization ofX^p−1 into irreducible polynomials. Then all factorsgihave the same degreed||F|pZ|, the order of|F|modp. There are polynomialsa_i ∈FX 0 ≤i≤m such that

1a₀g₁· · ·g_m X−1^m

i1

a_i

j /i

g_j. 2.9

Then the primitive idempotents inFX/X^p−1are given by the classes of

e0a0g1· · ·gm, eiai

j /i

gjX−1, 1≤i≤m. 2.10

LetLbe the extension field ofFwithL:F d. Then the group ring FX

X^p−1 Fσ ∼F⊕L ⊕ · · · ⊕L

m

2.11

is a commutative semisimpleF-algebra. Any codeC≤Fⁿwith an automorphismσ∈MonC is a module for this algebra. Putei : eiσ ∈ Fσ. ThenC Ce0⊕Ce1⊕ · · · ⊕Cem with Ce₀ Cσ,ECe₁⊕ · · · ⊕Ce_m. Omitting the coordinates ofEthat correspond to the fixed points ofσ, the codesCe_iareL-linear codes of lengtht. Clearly dim_FE d_m

i1dim_LCei. IfCis self-dual then dimE tp−1/2.

3. Extremal Ternary Codes of Length 48

LetCC^⊥≤F⁴⁸₃ be an extremal self-dual ternary code of length 48, sodC 15.

3.1. Large Primes

In this section we prove the main result of this paper.

Theorem 3.1. LetCC^⊥ ≤F⁴⁸₃ be an extremal self-dual code with an automorphism of prime order p≥5. ThenCis one of the two known codes. So eitherCQ48is the extended quadratic residue code of length 48 with automorphism group

MonQ48 C₂×P SL₂47of order 2⁵·3·23·47 3.1

orCP48is the Pless code with automorphism group

MonP48 C₂×SL₂23·2 of order 2⁶·3·11·23. 3.2 Lemma 3.2. Letσ ∈ MonCbe an automorphism of prime orderp ≥ 5. Then eitherp 47 and t, f 1,1orp23 andt, f 2,2orp11 andt, f 4,4.

(5)

Proof. For the proof we use the notation ofLemma 2.3. In particular we letK : kerπt

{0, . . . ,0, c₁, . . . , c_f∈Cσ}and putK^∗:{c1, . . . , c_f|0, . . . ,0, c₁, . . . , c_f∈Cσ}. Then

K^∗≤F^f₃, dK^∗≥15, dimK^∗≥ f−t

2 . 3.3

Moreovertpf48.

1Ift 1, thenp 47. Ifp 47, thent f 1. So assume thatp < 47 andt 1.

Then the codeEhas lengthpand dimensionp−1/2, thereforep≥dC 15. Sop≥17 and f≤48−1731.

ThenK^∗ ≤F^f₃ has dimensionf−1/2 and minimum distancedK^∗≥15. From the bounds given in8there is no such possibility forf≤31.

2Ift2, thenp23. Assume thatt2. Since 2·p≤48 we getp≤23, and ifp23, thent, f 2,2.

So assume that p < 23. The code E is a nonzero code of length 2p and minimum distance≥15, so 2p≥15 andpis one of 11, 13, 17, 19, andf 26, 22, 14, 10. The codeK^∗≤F^f₃ has dimension≥f/2−1 and minimum distance≥15. Again by8there is no such code.

3 p /13. For p 13 one now only has the possibilityt 3 and f 9. The same argument as above constructs a code K^∗ ≤ F⁹₃ of dimension at least f t/2−t 3 of minimum distance≥15> f which is absurd.

4Ifp11, thentf 4. Otherwiset3 andf 15 and the codeK^∗as above has length 15, dimension≥6, and minimum distance≥15 which is impossible.

5Ifp7, thentf 6. Otherwiset3, 4, 5 andf 27, 20, 13 and the codeK^∗as above has dimension≥ft/2−t12,8,4, lengthf, and minimum distance≥15 which is impossible by8.

6p /7. Assume thatp7, thentf 6 and the kernelKof the projection ofCσ onto the first 42 components is trivial. So the image of the projection isF⁶₃⊗ 1,1,1,1,1,1,1;

in particular it contains the vector 1⁷,0³⁵ of weight 7. So Cσ contains some word 1⁷,0³⁵, a1, . . . , a6of weight≤13 which is a contradiction.

7 If p 5, then t f 8 or t 9 andf 3. Otherwise t 3, 4, 5, 6, 7 and f 33, 28, 23, 18, 13 and the codeK^∗ ≤F^f₃ has dimension≥ ft/2−t 15,12,9,6,3 and minimum distance≥15 which is impossible by8.

8p /5. Assume thatp 5. Then one possibility is thatt 8 and the projection of Cσonto the first 8·5 coordinates isF⁸₃⊗ 1,1,1,1,1and contains a word of weight 5. But thenCσhas a word of weightwwith 5< w≤5813 a contradiction.

The other possibility ist 9. Then the codeE E^⊥is a Hermitian self-dual code of length 9 over the field with 3⁴ 81 elements, which is impossible, since the length of such a code is 2 times the dimension and hence even.

Lemma 3.3. Ifp11, thenC∼P₄₈.

Proof. Letσ ∈ MonCbe of order 11. Sincex¹¹ −1 x−1gh ∈ F3xfor irreducible polynomialsg, hof degree 5,

F3σ ∼F3⊕F3⁵⊕F3⁵. 3.4

(6)

Lete1, e2, e3 ∈ F3σdenote the primitive idempotents. Then C Ce1 ⊕Ce2⊕Ce3 with Cσ Ce₁Ce^⊥₁ of dimension 4 andCe₂Ce^⊥₃ ≤F3⁵⊕F3⁵⁴. Clearly the projection ofCσ onto the first 44 coordinates is injective. Since all weights ofCare multiples of 3 and≥15, this leaves just one possibility forCσ:

G0 L0|R0:

⎛

⎜⎜

⎝

1¹¹ 0¹¹ 0¹¹ 0¹¹ 1 1 1 1 0¹¹ 1¹¹ 0¹¹ 0¹¹ 1 1 −1 −1 0¹¹ 0¹¹ 1¹¹ 0¹¹ 1 −1 1 −1 0¹¹ 0¹¹ 0¹¹ 1¹¹ 1 −1 −1 1

⎞

⎟⎟

⎠. 3.5

The cyclic codeZof length 11 with generator polynomialx−1gand similarly the one with generator polynomialx−1hhas weight enumerator

x¹¹132x⁵y⁶110x²y⁹. 3.6

In particular it contains more words of weight 6 than of weight 9. This shows that the dimension ofCe_ioverF3⁵is 2 for bothi2,3, since otherwise one of them has dimension≥3 and therefore contains all words0,0, c, αcfor allc ∈Zand someα∈F3⁵. Not all of them can have weight≥ 15. Similarly one sees that the codesCei ≤F⁴₃5 have minimum distance 3 fori2,3. So we may choose generator matrices

G1 :

!1 0 a b 0 1 c d

"

, G2 :

!1 0 a b 0 1 c d

"

3.7

with ^{a b}_{c d}

∈ GL₂F3⁵ and ^a_c^bd

− ^{a b}_{c d}_−tr

. To obtain F3-generator matrices for the corresponding codesCe2andCe3 of length 48, we choose a generator matrixg1 ∈F⁵₃^×¹¹ of the cyclic codeZof length 11 with generator polynomialx−1gand the corresponding dual basisg₂∈F⁵₃^×¹¹of the cyclic code with generator polynomialx−1h. We compute the action ofσthe multiplication withxand represent this as left multiplication withz₁₁ ∈F⁵₃^×⁵ on the basis g1. Ifa ₄

i0aizⁱ₁₁ ∈ F3⁵ with ai ∈ F3, then the entry ain G1 is replaced by ₄

i0a_izⁱ₁₁g₁ ∈F⁵₃^×¹¹and analogously forG2, where we use of course the matrixg₂instead of g₁. Replacing the code by an equivalent one we may choosea,b,cas orbit representatives of the action of−z11onF^∗₃5.

A generator matrix ofCis then given by

⎛

⎝L0 R0 G1 0 G2 0

⎞

⎠. 3.8

All codes obtained this way are equivalent to the Pless codeP₄₈.

(7)

Lemma 3.4. Ifp23, thenC∼P48orC∼Q48.

Proof. Letσ ∈ MonCbe of order 23. Sincex²³ −1 x−1gh ∈ F3xfor irreducible polynomialsg, hof degree 11,

F3σ ∼F3⊕F3¹¹⊕F3¹¹. 3.9 Lete1, e2, e3 ∈ F3σdenote the primitive idempotents. Then C Ce1 ⊕Ce2⊕Ce3 with Cσ Ce₁ Ce^⊥₁ of dimension 2 andCe₂ Ce^⊥₃ ≤F3¹¹ ⊕F3¹¹². Since all weights ofCare multiples of 3, this leaves just one possibility forCσ up to equivalence:

Cσ #

1²³,0²³,1,0 ,

0²³,1²³,0,1$

. 3.10

The codesCe2 andCe3are codes of length 2 over F3¹¹ such that dimCe2 dimCe3 2.

Note that the alphabet F₃¹¹ is identified with the cyclic code of length 23 with generator polynomial x− 1g resp., x −1h. These codes have minimum distance 9 < 15, so dimCe2 dimCe3 1 and both codes have a generator matrix of the form1, t resp., 1,−t⁻¹fort∈F^∗₃11. Going through all possibilities fortup to the action of the subgroup of F^∗₃11 of order 23the only codesCfor whichCσ⊕Ce₂⊕Ce₃ have minimum distance≥ 15 are the two known extremal codesP₄₈andQ₄₈.

Lemma 3.5. Ifp47, thenC∼Q48.

Proof. The subcodeC₀ :{c∈F⁴⁷₃ |c,0∈C}is a cyclic code of length 47, dimension 23, and minimum distance≥15. Sincex⁴⁷−1 x−1gh∈F3xfor irreducible polynomialsg, hof degree 23,C0is the cyclic code with generator polynomialx−1gor equivalentlyx−1h andCC0,0,1 ≤F⁴⁸₃ is the extended quadratic residue code.

3.2. Automorphisms of Order 2

As above letC C^⊥ ≤F⁴⁸₃ be an extremal self-dual ternary code. Assume thatσ ∈MonC such that the permutational partπσhas order 2. Then σ² ±1 because ofLemma 2.1. If σ²−1, thenσis conjugate to a block diagonal matrix with all blocks _{−1 0}^{0 1}

:JandCis a Hermitian self-dual code of length 24 overF9. Such automorphismsσwithσ²−1 occur for both known extremal codes.

Ifσ²1, thenσis conjugate to a block diagonal matrix

σ∼diag

%!0 1 1 0

"t

,1^f,−1^a

&

3.11

fort, a, f∈N0, 2taf48.

Proposition 3.6. Assume thatσ ∈MonC,σ² 1 andπσ/1. Then eithert, a, f 24,0,0 ort, a, f 22,2,2. Automorphisms of both kinds are contained in AutP48.

(8)

Proof. 1 Wlogf ≤ a: Replacing σ by−σ we may assume without loss of generality that f≤a.

2f−t∈4Z: ByLemma 2.3the codeCσ^∗ ≤F^tf₃ is a self-dual code with respect to the inner productx, y −_t

i1x_iy_if

j1x_jy_j. This space only contains a self-dual code if f−tis a multiple of 4.

3 tf ∈ {22,24}: The code Cσ^∗ ≤ F^tf₃ has dimensiontf/2 and minimum distance≥ 15/2 and hence minimum distance≥ 8. By8this implies thattf ≥ 22. Since ta≥tfandta tf 48 this only leaves these two possibilities.

4tf /22: We first treat the casef≤14. ThenK^∗∼kerπtis a code of lengthf ≤14 and minimum distance≥15 and hence trivial. Soπ_tis injective and

Cσ∼D:πtCσ≤F^t₃, dimD 11, dD≥'15−f 2

(

. 3.12

Using 8 and the fact that f − t is a multiple of 4, this only leaves the cases t, f ∈ {19,3,21,1}. To rule out these two cases we use the fact thatD is the dual of the self- orthogonal ternary codeD^⊥ π_tkerπf. The bounds in9givedD≤5<15−3/2 for t19 anddD≤6<15−1/2 fort21.

Iff ≥15, thent≤7 andK^∗ ∼kerπthas dimensionf−t >0 and minimum distance

≥15. This is easily ruled out by the known boundssee8.

5Iftf 24 then eithert, f 24,0ort, f 22,2. Again the casef > tis easily ruled out using dimension and minimum distance ofK^∗as before.

So assume thatf≤t, and letDπ_tCσas before. Then dimD 12 and using8 one gets that

t, f

∈ {24,0,22,2,20,4}. 3.13

Assume thatt20. Then there is some self-dual codeΛ Λ^⊥≤F²⁰₃ such that D^⊥π_t ker π_f

≤Λ Λ^⊥≤D. 3.14

Clearly alsodΛ≥dD≥6, soΛis an extremal ternary code of length 20. There are 6 such codes, and none of them has a proper overcode with minimum distance 6.

Remark 3.7. Ifσ ∈ MonCis some automorphism of order 4, thenσ² −1 orσ² has type 24,0,0in the notation ofProposition 3.6.

Proof. Assume that σ ∈ MonC has order 4 but σ²/ − 1. Then τ σ² is one of the automorphisms fromProposition 3.6and soσis conjugate to some block diagonal matrix

σ∼diag

⎛

⎜⎜

⎜⎝

⎛

⎜⎜

⎝

0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0

⎞

⎟⎟

⎠

t/2

,

!0 1 1 0

"f/2

,

!0 −1 1 0

"a/2

⎞

⎟⎟

⎟⎠. 3.15

(9)

Ift22 andf 2 then the fixed code ofσis a self-dual code in1,1,1,1^t/2⊥ 1,1^f/2and Cσ^∗ ≤F^t/2f/2₃ is a self-dual code with respect to the formx, y:_t/2

i1xiyi−t/2f/2 it/21 xiyi

which implies thatt/2−f/2 is a multiple of 4, a contradiction.

For the two known extremal codes all automorphismsσof order 4 satisfyσ² −1. It would be nice to have some argument to exclude the other possibility.

References

1 C. L. Mallows and N. J. A. Sloane, “An upper bound for self-dual codes,” Information and Computation, vol. 22, pp. 188–200, 1973.

2 A. M. Gleason, “Weight polynomials of self-dual codes and the MacWilliams identities,” in Actes du Congr`es International des Math´ematiciens (Nice, 1970), vol. 3, pp. 211–215, Gauthier-Villars, Paris, France, 1971.

3 J. H. Conway and V. Pless, “On primes dividing the group order of a doubly-even72; 36; 16code and the group order of a quaternary24; 12; 10code,” Discrete Mathematics, vol. 38, no. 2-3, pp. 143–156, 1982.

4 W. C. Huﬀman, “Automorphisms of codes with applications to extremal doubly even codes of length 48,” Institute of Electrical and Electronics Engineers. Transactions on Information Theory, vol. 28, no. 3, pp.

511–521, 1982.

5 W. C. Huﬀman, “On extremal self-dual ternary codes of lengths 48 to 40,” Institute of Electrical and Electronics Engineers. Transactions on Information Theory, vol. 38, no. 4, pp. 1395–1400, 1992.

6 H. Koch, “The 48-dimensional analogues of the Leech lattice,” Rossi˘ıskaya Akademiya Nauk. Trudy Mate- maticheskogo Instituta Imeni V. A. Steklova, vol. 208, pp. 193–201, 1995.

7 S. Bouyuklieva, “On the automorphism group of a doubly-even72; 36; 16code,” Institute of Electrical and Electronics Engineers. Transactions on Information Theory, vol. 50, no. 3, pp. 544–547, 2004.

8 M. Grassl, Code Tables: bounds on the parameters of various types of codes,http://www.codetables .de/.

9 A. Meyer, “On dual extremal maximal self-orthogonal codes of type I-IV,” Advances in Mathematics of Communications, vol. 4, no. 4, pp. 579–596, 2010.

(10)

Submit your manuscripts at http://www.hindawi.com

Hindawi Publishing Corporation

http://www.hindawi.com Volume 2014

Mathematics

^{Journal of}

Hindawi Publishing Corporation http://www.hindawi.com

Differential Equations

International Journal of

Volume 2014

Applied Mathematics^{Journal of}

Mathematical PhysicsAdvances in

Complex Analysis

^{Journal of}

Optimization

^{Journal of}

Combinatorics

Journal of

Function Spaces

Abstract and Applied Analysis

International Journal of Mathematics and Mathematical Sciences

The Scientific World Journal

Discrete Dynamics in Nature and Society

Discrete Mathematics

^{Journal of}

On Extremal Self-Dual Ternary Codes of Length 48

Research Article