Constructive recognition of

Authors:
M. D. E. Conder, C. R. Leedham-Green and E. A. O'Brien

Journal:
Trans. Amer. Math. Soc. **358** (2006), 1203-1221

MSC (2000):
Primary 20C20; Secondary 20C40

DOI:
https://doi.org/10.1090/S0002-9947-05-03756-6

Published electronically:
May 9, 2005

MathSciNet review:
2187651

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Existing black box and other algorithms for explicitly recognising groups of Lie type over have asymptotic running times which are polynomial in , whereas the input size involves only . This has represented a serious obstruction to the efficient recognition of such groups. Recently, Brooksbank and Kantor devised new explicit recognition algorithms for classical groups; these run in time that is polynomial in the size of the input, given an oracle that recognises explicitly.

The present paper, in conjunction with an earlier paper by the first two authors, provides such an oracle. The earlier paper produced an algorithm for explicitly recognising in its natural representation in polynomial time, given a discrete logarithm oracle for . The algorithm presented here takes as input a generating set for a subgroup of that is isomorphic modulo scalars to , where is a finite field of the same characteristic as ; it returns the natural representation of modulo scalars. Since a faithful projective representation of in cross characteristic, or a faithful permutation representation of this group, is necessarily of size that is polynomial in rather than in , elementary algorithms will recognise explicitly in polynomial time in these cases. Given a discrete logarithm oracle for , our algorithm thus provides the required polynomial time oracle for recognising explicitly in the remaining case, namely for representations in the natural characteristic.

This leads to a partial solution of a question posed by Babai and Shalev: if is a matrix group in characteristic , determine in polynomial time whether or not is trivial.

**1.**László Babai, William M. Kantor, Péter P. Pálfy, and Ákos Seress,*Black-box recognition of finite simple groups of Lie type by statistics of element orders*, J. Group Theory**5**(2002), no. 4, 383–401. MR**1931364**, https://doi.org/10.1515/jgth.2002.010**2.**László Babai and Aner Shalev,*Recognizing simplicity of black-box groups and the frequency of 𝑝-singular elements in affine groups*, Groups and computation, III (Columbus, OH, 1999) Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 39–62. MR**1829470****3.**L. Babai, A. J. Goodman, W. M. Kantor, E. M. Luks, and P. P. Pálfy,*Short presentations for finite groups*, J. Algebra**194**(1997), no. 1, 79–112. MR**1461483**, https://doi.org/10.1006/jabr.1996.6980**4.**László Babai, Gene Cooperman, Larry Finkelstein, Eugene Luks, and Ákos Seress,*Fast Monte Carlo algorithms for permutation groups*, J. Comput. System Sci.**50**(1995), no. 2, 296–308. 23rd Symposium on the Theory of Computing (New Orleans, LA, 1991). MR**1330259**, https://doi.org/10.1006/jcss.1995.1024**5.**Peter A. Brooksbank,*Constructive recognition of classical groups in their natural representation*, J. Symbolic Comput.**35**(2003), no. 2, 195–239. MR**1958954**, https://doi.org/10.1016/S0747-7171(02)00132-3**6.**Peter A. Brooksbank and William M. Kantor,*On constructive recognition of a black box 𝑃𝑆𝐿(𝑑,𝑞)*, Groups and computation, III (Columbus, OH, 1999) Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 95–111. MR**1829473****7.**R. Brauer and C. Nesbitt,*On the modular characters of groups*, Ann. of Math. (2)**42**(1941), 556–590. MR**0004042**, https://doi.org/10.2307/1968918**8.**Wieb Bosma, John Cannon, and Catherine Playoust,*The Magma algebra system. I. The user language*, J. Symbolic Comput.**24**(1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR**1484478**, https://doi.org/10.1006/jsco.1996.0125**9.**Marston Conder and Charles R. Leedham-Green,*Fast recognition of classical groups over large fields*, Groups and computation, III (Columbus, OH, 1999) Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 113–121. MR**1829474****10.**F. Celler and C. R. Leedham-Green,*A constructive recognition algorithm for the special linear group*, The atlas of finite groups: ten years on (Birmingham, 1995) London Math. Soc. Lecture Note Ser., vol. 249, Cambridge Univ. Press, Cambridge, 1998, pp. 11–26. MR**1647410**, https://doi.org/10.1017/CBO9780511565830.007**11.**Frank Celler and C. R. Leedham-Green,*Calculating the order of an invertible matrix*, Groups and computation, II (New Brunswick, NJ, 1995) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, RI, 1997, pp. 55–60. MR**1444130****12.**Frank Celler, Charles R. Leedham-Green, Scott H. Murray, Alice C. Niemeyer, and E. A. O’Brien,*Generating random elements of a finite group*, Comm. Algebra**23**(1995), no. 13, 4931–4948. MR**1356111**, https://doi.org/10.1080/00927879508825509**13.**S. P. Glasby and R. B. Howlett,*Writing representations over minimal fields*, Comm. Algebra**25**(1997), no. 6, 1703–1711. MR**1446124**, https://doi.org/10.1080/00927879708825947**14.**G. H. Hardy and E. M. Wright,*An introduction to the theory of numbers*, Oxford, at the Clarendon Press, 1954. 3rd ed. MR**0067125****15.**Derek F. Holt and Sarah Rees,*Testing modules for irreducibility*, J. Austral. Math. Soc. Ser. A**57**(1994), no. 1, 1–16. MR**1279282****16.**Alexander Hulpke and Ákos Seress,*Short presentations for three-dimensional unitary groups*, J. Algebra**245**(2001), no. 2, 719–729. MR**1863898**, https://doi.org/10.1006/jabr.2001.8943**17.**Gábor Ivanyos and Klaus Lux,*Treating the exceptional cases of the MeatAxe*, Experiment. Math.**9**(2000), no. 3, 373–381. MR**1795309****18.**Vicente Landazuri and Gary M. Seitz,*On the minimal degrees of projective representations of the finite Chevalley groups*, J. Algebra**32**(1974), 418–443. MR**0360852**, https://doi.org/10.1016/0021-8693(74)90150-1**19.**Charles R. Leedham-Green,*The computational matrix group project*, Groups and computation, III (Columbus, OH, 1999) Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 229–247. MR**1829483****20.**C. R. Leedham-Green and E. A. O’Brien,*Tensor products are projective geometries*, J. Algebra**189**(1997), no. 2, 514–528. MR**1438187**, https://doi.org/10.1006/jabr.1996.6881**21.**C. R. Leedham-Green and E. A. O’Brien,*Recognising tensor products of matrix groups*, Internat. J. Algebra Comput.**7**(1997), no. 5, 541–559. MR**1470352**, https://doi.org/10.1142/S0218196797000241**22.**William M. Kantor and Ákos Seress,*Black box classical groups*, Mem. Amer. Math. Soc.**149**(2001), no. 708, viii+168. MR**1804385**, https://doi.org/10.1090/memo/0708**23.**D. S. Mitrinović, J. Sándor, and B. Crstici,*Handbook of number theory*, Mathematics and its Applications, vol. 351, Kluwer Academic Publishers Group, Dordrecht, 1996. MR**1374329****24.**J.A. Todd, ``A second note on the linear fractional group",*Proc. London Math. Soc.***11**, 1936, 103-107.**25.**Igor E. Shparlinski,*Finite fields: theory and computation*, Mathematics and its Applications, vol. 477, Kluwer Academic Publishers, Dordrecht, 1999. The meeting point of number theory, computer science, coding theory and cryptography. MR**1745660**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
20C20,
20C40

Retrieve articles in all journals with MSC (2000): 20C20, 20C40

Additional Information

**M. D. E. Conder**

Affiliation:
Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand

Email:
conder@math.auckland.ac.nz

**C. R. Leedham-Green**

Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, United Kingdom

Email:
C.R.Leedham-Green@qmul.ac.uk

**E. A. O'Brien**

Affiliation:
Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand

Email:
obrien@math.auckland.ac.nz

DOI:
https://doi.org/10.1090/S0002-9947-05-03756-6

Keywords:
Constructive recognition,
$\mathrm{PSL}(2, q)$

Received by editor(s):
January 17, 2003

Received by editor(s) in revised form:
May 4, 2004

Published electronically:
May 9, 2005

Additional Notes:
This work was supported in part by the Marsden Fund of New Zealand via grant UOA124.

Article copyright:
© Copyright 2005
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.