Show simple item record

dc.contributor.authorBorovik, Alexandre
dc.contributor.authorYalçınkaya, Şükrü
dc.date.accessioned2021-03-05T17:16:52Z
dc.date.available2021-03-05T17:16:52Z
dc.identifier.citationBorovik A., Yalçınkaya Ş., "Steinberg presentations of black box classical groups in small characteristics", Diğer, ss.1-32, 2013
dc.identifier.othervv_1032021
dc.identifier.otherav_c4c50c69-5c9a-4ace-9135-6cf8a5f1a8c4
dc.identifier.urihttp://hdl.handle.net/20.500.12627/130499
dc.identifier.urihttp://arxiv.org/pdf/1302.3059.pdf
dc.description.abstractThe main component of (constructive) recognition algorithms for black box groups of Lie type in computational group theory is the construction of unipotent elements. In the existing algorithms unipotent elements are found by random search and therefore the running time of these algorithms is polynomial in the underlying field sizeqwhich makes them unfeasible for most practical applications [27]. Meanwhile, the input size of recogni- tion algorithms involves only logq. The present paper introduces a new approach to construction of unipotent elements in which the running time of the algorithm is quadratic in characteristicpof the underlying field and is polynomial in logq; for small values ofp(which make a vast and practically important class of problems), the complexity of these algorithms is polynomial in the input size.For PSL2(q),q≡1 mod 4, we present a Monte-Carlo algorithm which constructs a root subgroupU, the maximal torusTnormalizingUand a Weyl group elementwwhich conjugatesUto its opposite. Moreover, we extend this result and construct Steinberg generators for the black box untwisted classical groups defined over a field of odd sizeq=pkwhereq≡1 mod 4. Our algorithms run in time quadratic in characteristicpof the underlying field and polynomial in logqand the Lie ranknof the group.The caseq≡ −1 mod 4 requires the use of additional tools and is treated separately in our next paper [9]. Further, and much stronger results can be found in [6, 7].
dc.language.isoeng
dc.subjectMATEMATİK
dc.subjectTemel Bilimler
dc.subjectÇOK DİSİPLİNLİ BİLİMLER
dc.subjectMatematik
dc.subjectDoğa Bilimleri Genel
dc.subjectTemel Bilimler (SCI)
dc.titleSteinberg presentations of black box classical groups in small characteristics
dc.typeDiğer Yayınlar
dc.contributor.departmentThe University of Manchester , ,
dc.contributor.firstauthorID2176262


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record