On the Classification of All Self-Dual Additive Co

arXiv:math/0504522v4[math.CO]17Feb2006OntheClassificationofAllSelf-DualAdditiveCodesoverGF(4)ofLengthupto12LarsEirikDanielsen∗MatthewG.Parker∗February17,2006AbstractWeconsideradditivecodesoverGF(4)thatareself-dualwithrespecttotheHermitiantraceinnerproduct.Suchcodeshaveawell-knowninterpretationasquantumcodesandcorrespondtoisotropicsystems.Ithasalsobeenshownthatthesecodescanberepresentedasgraphs,andthattwocodesareequivalentifandonlyifthecorrespondinggraphsareequivalentwithrespecttolocalcomplementationandgraphisomorphism.Weusethesefactstoclassifyallcodesoflengthupto12,wherepreviouslyonlyallcodesoflengthupto9wereknown.WealsoclassifyallextremalTypeIIcodesoflength14.Finally,wefindthatthesmallestTypeIandTypeIIcodeswithtrivialautomorphismgrouphavelength9and12,respectively.Keywords:Self-dualcodes;Graphs;Localcomplementation1IntroductionAnadditivecode,C,overGF(4)oflengthnisanadditivesubgroupofGF(4)n.Ccontains2kcodewordsforsome0≤k≤2n,andcanbedefinedbyak×ngeneratormatrix,withentriesfromGF(4),whoserowsspanCadditively.Ciscalledan(n,2k)code.WedenoteGF(4)={0,1,ω,ω2},whereω2=ω+1.Conjugationofx∈GF(4)isdefinedbyx=x2.Thetracemap,Tr:GF(4)→GF(2),isdefinedbyTr(x)=x+x.TheHermitiantraceinnerproductoftwovectorsoverGF(4)oflengthn,u=(u1,u2,...,un)andv=(v1,v2,...,vn),isgivenbyu∗v=Tr(u·v)=nXi=1Tr(uivi)=nXi=1(uiv2i+u2ivi)(mod2).(1)Notethatu∗visalsothenumber(modulo2)ofplaceswhereuandvhavedifferentnon-zerovalues.WedefinethedualofthecodeCwithrespecttotheHermitiantraceinnerproduct,C⊥={u∈GF(4)n|u∗c=0forallc∈C}.Cisself-orthogonalifC⊆C⊥.Ithasbeenshownthatself-orthogonaladditivecodesoverGF(4)canbeusedtorepresentquantumerror-correcting∗TheSelmerCenter,DepartmentofInformatics,UniversityofBergen,PB7800,N-5020Bergen,Norway.{larsed,matthew}@ii.uib.no~{larsed,matthew}1codes[4].IfC=C⊥,thenCisself-dualandmustbean(n,2n)code.Self-dualadditivecodesoverGF(4)correspondtozero-dimensionalquantumcodes,whichrepresentsinglequantumstates.Ifthecodehashighminimumdistance,thecorrespondingquantumstateishighlyentangled.TheHammingweightofu,denotedwt(u),isthenumberofnonzerocom-ponentsofu.TheHammingdistancebetweenuandviswt(u−v).TheminimumdistanceofthecodeCistheminimalHammingdistancebetweenanytwodistinctcodewordsofC.SinceCisanadditivecode,theminimumdistanceisalsogivenbythesmallestnonzeroweightofanycodewordinC.Acodewithminimumdistancediscalledan(n,2k,d)code.TheweightdistributionofthecodeCisthesequence(A0,A1,...,An),whereAiisthenumberofcodewordsofweighti.TheweightenumeratorofCisthepolynomialW(x,y)=nXi=0Aixn−iyi(2)Wedistinguishbetweentwotypesofself-dualadditivecodesoverGF(4).AcodeisofTypeIIifallcodewordshaveevenweight,otherwiseitisofTypeI.ItcanbeshownthataTypeIIcodemusthaveevenlength.Boundsontheminimumdistanceofself-dualcodesweregivenbyRainsandSloane[19,The-orem33].LetdIbetheminimumdistanceofaTypeIcodeoflengthn.ThendIisupper-boundedbydI≤2n6+1,ifn≡0(mod6)2n6+3,ifn≡5(mod6)2n6+2,otherwise.(3)ThereisasimilarboundondII,theminimumdistanceofaTypeIIcodeoflengthn,dII≤2jn6k+2.(4)Acodethatmeetstheappropriateboundiscalledextremal.ItcanbeshownthatextremalTypeIIcodesmusthaveauniqueweightenumerator.RainsandSloane[19]alsousedalinearprogrammingbound,andshowedthatextremalcodesdonotexistforalllengths.Forinstance,thereisnoself-dual(13,213,6)code.Ifacodehashighestpossibleminimumdistance,butisnotextremal,itiscalledoptimal.AninterestingopenproblemiswhetherthereexistsaTypeII(24,224,10)code.Alinearcode,C,overGF(4)whichisself-dualwithrespecttotheHermitianinnerproduct,i.e.,u·v=0forallu,v∈C,isalsoaself-dualadditivecodewithrespecttotheHermitiantraceinnerproduct.However,mostoftheself-dualadditivecodesarenotlinear.OnlyTypeIIcodescanbelinear,sinceself-duallinearcodesoverGF(4)mustcontaincodewordsofevenweightonly.ItfollowsthatthesetofHermitianself-duallinearcodesoverGF(4)isasubsetofthesetofTypeIIself-dualadditivecodesoverGF(4).Example1.Theuniqueextremal(6,26,4)code,alsoknownastheHexacode,2hasageneratormatrix1001ωωω00ωω2ω2010ω1ω0ω0ω2ωω2001ωω100ωω2ω2ω.ThiscodehasweightenumeratorW(x,y)=x6+45x2y4+18y6.ItisthereforeofTypeII,anditcanbeverifiedthatitisalsoalinearcode.Twoself-dualadditivecodesoverGF(4),CandC′,areequivalentifandonlyifthecodewordsofCcanbemappedontothecodewordsofC′byamapthatpreservesself-duality.Suchamapmustconsistofapermutationofcoordinates(columnsofthegeneratormatrix),followedbymultiplicationofcoordinatesbynonzeroelementsfromGF(4),followedbypossibleconjugationofcoordinates.Foracodeoflengthn,thereisatotalof6nn!suchmaps.The6possibletransformationsgivenbyscalingandconjugationofacoordinateareequivalenttothe6permutationsoftheelements{1,ω,ω2}inthecoordinate.AmapthatmapsCtoCiscalledanautomorphismofC.AllautomorphismsofCmakeupanautomorphismgroup,denotedAut(C).ThenumberofdistinctcodesequivalenttoCisthengivenby6nn!|Aut(C)|.Bysummingthesizesofallequivalenceclasses,wefindthetotalnumberofdistinctcodesoflengthn,denotedTn.ItwasshownbyH¨ohn[16]thatTnisalsogivenbythemassformula,Tn=nYi=1(2i+1)=tnXj=16nn!|Aut(Cj)|,(5)wherethesumisoverallequivalenceclasses.Similarly,thetotalnumberofd