The spinor norm and homomorphism algorithms for classical groups

《The spinor norm and homomorphism algorithms for classical groups》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、THESPINORNORMANDHOMOMORPHISMALGORITHMSFORCLASSICALGROUPSSCOTTH.MURRAYANDCOLVAM.RONEY-DOUGALAbstract.WeinvestigatethestructureofthenormaliserNinGLd(q)oftheorthogonalgroupΩd(q),for∈{◦,+,−}.Wedevelopalgorithmstocomputethespinornorm,andhencetoconstructahomomorphismfromNwithkernelΩd(q).T

2、hesealgorithmsruninlow-degreepolynomialtime(withadiscretelogoracleinsomecases)andareimplementedinMagma.Wealsopresentsimilaralgorithmsforthenormalisersoftheotherquasisimpleclassicalgroups.1.Introduction1.1.Motivation.ThespinornormisanepimorphismfromthegeneralorthogonalgroupGO(q)dtoF+,o

3、riginallygivenbydecomposingelementsintoaproductofreflections.Thematricesof2determinantoneandspinornormzeroformtheomegagroupΩ(q).Inthispaper,weinvestigatedthestructureoftheconformalgroupCO(q),whichisthenormaliserinGL(q)ofΩ(q).Weddddevelopanalgorithmtocomputethespinornormofanelementofa

4、generalorthogonalgroup.Givenanelementgofaconformalorthogonalgroup,wesolvetwomainalgorithmictasks.Firstweefficientlycomputetheimageofgunderthenaturalquotientbytheomegagroup,asanelementofapolycyclicgroup.Secondlywefindacanonicalcosetrepresentativeofgmodulotheomegagroup.Wealsofindtheimageofgi

5、nanextensionofF×q,sincethisavoidsadiscretelogarithmcall.Wethensolveanalogousproblemsfortheotherclassicalgroups.Almostallofouralgorithmsruninanumberoffinitefieldoperationsthatislow-degreepolynomialindandlogq:theexceptionisthehomomorphismtothepolycyclicallypresentedgroup,whichmayrequireatm

6、ostonediscretelogarithmcall(ortwointheunitarycase).Wehavetwomainmotivationsforthiswork.First,thematrixgrouprecognitionproject,whichseekstoefficientlycomputecompositionseriesforfinite-dimensionalmatrixgroupsoverfinitefields[13].Thefirststageofthiscomputationistofindageometrypreservedbythegroup

7、,inthesenseofAschbacher’sTheorem[1],anduseittocomputeanormalsubgroupanditsquotient.ThesedecompositionalgorithmsterminatewhentheyreachgroupsthatliebetweenaclassicalgroupinitsnaturalrepresentationanditsnormaliserinGLd(q)(CaseC8),orarealmostsimplemoduloscalars(CaseC9).Algorithmstoconstr