Testing isomorphism of graded algebras
HTML articles powered by AMS MathViewer
- by Peter A. Brooksbank, E. A. O’Brien and James B. Wilson PDF
- Trans. Amer. Math. Soc. 372 (2019), 8067-8090 Request permission
Abstract:
We present a new algorithm to decide isomorphism between finite graded algebras. For a broad class of nilpotent Lie algebras, we demonstrate that it runs in time polynomial in the order of the input algebras. We introduce heuristics that often dramatically improve the performance of the algorithm and report on an implementation in Magma.References
- Anders Björner, Subspace arrangements, First European Congress of Mathematics, Vol. I (Paris, 1992) Progr. Math., vol. 119, Birkhäuser, Basel, 1994, pp. 321–370. MR 1341828
- Simon R. Blackburn, Peter M. Neumann, and Geetha Venkataraman, Enumeration of finite groups, Cambridge Tracts in Mathematics, vol. 173, Cambridge University Press, Cambridge, 2007. MR 2382539, DOI 10.1017/CBO9780511542756
- 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, DOI 10.1006/jsco.1996.0125
- Peter A. Brooksbank and Eugene M. Luks, Testing isomorphism of modules, J. Algebra 320 (2008), no. 11, 4020–4029. MR 2464805, DOI 10.1016/j.jalgebra.2008.07.014
- Peter A. Brooksbank, Joshua Maglione, and James B. Wilson, A fast isomorphism test for groups whose Lie algebra has genus 2, J. Algebra 473 (2017), 545–590. MR 3591162, DOI 10.1016/j.jalgebra.2016.12.007
- Peter A. Brooksbank and E. A. O’Brien, Constructing the group preserving a system of forms, Internat. J. Algebra Comput. 18 (2008), no. 2, 227–241. MR 2403820, DOI 10.1142/S021819670800441X
- Peter A. Brooksbank and James B. Wilson, Groups acting on tensor products, J. Pure Appl. Algebra 218 (2014), no. 3, 405–416. MR 3124207, DOI 10.1016/j.jpaa.2013.06.011
- Peter A. Brooksbank and James B. Wilson, Computing isometry groups of Hermitian maps, Trans. Amer. Math. Soc. 364 (2012), no. 4, 1975–1996. MR 2869196, DOI 10.1090/S0002-9947-2011-05388-2
- David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587–592. MR 606517, DOI 10.1090/S0025-5718-1981-0606517-5
- Jean Dieudonné, Sur la réduction canonique des couples de matrices, Bull. Soc. Math. France 74 (1946), 130–146 (French). MR 22826, DOI 10.24033/bsmf.1380
- Bettina Eick, Computing the automorphism group of a solvable Lie algebra, Linear Algebra Appl. 382 (2004), 195–209. MR 2050106, DOI 10.1016/j.laa.2003.12.009
- Bettina Eick, Computing automorphism groups and testing isomorphisms for modular group algebras, J. Algebra 320 (2008), no. 11, 3895–3910. MR 2464798, DOI 10.1016/j.jalgebra.2008.05.002
- Bettina Eick, C. R. Leedham-Green, and E. A. O’Brien, Constructing automorphism groups of $p$-groups, Comm. Algebra 30 (2002), no. 5, 2271–2295. MR 1904637, DOI 10.1081/AGB-120003468
- Gábor Ivanyos and Youming Qiao, Algorithms based on $*$-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing, SIAM J. Comput. 48 (2019), no. 3, 926–963. MR 3945816, DOI 10.1137/18M1165682
- Brendan D. McKay, Practical graph isomorphism, Congr. Numer. 30 (1981), 45–87. MR 635936
- Joshua Maglione, Efficient characteristic refinements for finite groups. part 2, J. Symbolic Comput. 80 (2017), no. part 2, 511–520. MR 3574524, DOI 10.1016/j.jsc.2016.07.007
- Rudolf Scharlau, Paare alternierender Formen, Math. Z. 147 (1976), no. 1, 13–19. MR 419484, DOI 10.1007/BF01214270
- Libero Verardi, Semi-extraspecial groups of exponent $p$, Ann. Mat. Pura Appl. (4) 148 (1987), 131–171 (Italian, with English summary). MR 932762, DOI 10.1007/BF01774287
- A. L. Vishnevetskiĭ, A system of invariants of certain groups of class $2$ with commutator subgroup of rank two, Ukrain. Mat. Zh. 37 (1985), no. 3, 294–300, 403 (Russian). MR 795568
- James B. Wilson, Finding central decompositions of $p$-groups, J. Group Theory 12 (2009), no. 6, 813–830. MR 2582050, DOI 10.1515/JGT.2009.015
- James B. Wilson, Optimal algorithms of Gram-Schmidt type, Linear Algebra Appl. 438 (2013), no. 12, 4573–4583. MR 3039211, DOI 10.1016/j.laa.2013.02.026
- James B. Wilson, Division, adjoints, and dualities of bilinear maps, Comm. Algebra 41 (2013), no. 11, 3989–4008. MR 3169502, DOI 10.1080/00927872.2012.660668
- James B. Wilson, On automorphisms of groups, rings, and algebras, Comm. Algebra 45 (2017), no. 4, 1452–1478. MR 3576669, DOI 10.1080/00927872.2016.1175617
- Peter A. Brooksbank, Joshua Maglione, E. A. O’Brien, and James B. Wilson, TheTensor.Space: Software for multilinear algebra and isomorphism tests, https://github.com/thetensor-space, 2019.
Additional Information
- Peter A. Brooksbank
- Affiliation: Department of Mathematics, Bucknell University, Lewisburg, Pennsylvania 17837
- MR Author ID: 321878
- E. A. O’Brien
- Affiliation: Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand
- MR Author ID: 251889
- James B. Wilson
- Affiliation: Department of Mathematics, Colorado State University, Fort Collins, Colorado 80523
- MR Author ID: 881789
- Received by editor(s): July 24, 2017
- Received by editor(s) in revised form: March 6, 2019
- Published electronically: August 1, 2019
- Additional Notes: This work was supported in part by the Marsden Fund of New Zealand via grant UOA 1626, by NSF grants DMS-1620454 and DMS-1620362, and by the Simons Foundation $\#$281435.
- © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 372 (2019), 8067-8090
- MSC (2010): Primary 17-08, 15A69, 68Q25; Secondary 20D15, 17B70
- DOI: https://doi.org/10.1090/tran/7884
- MathSciNet review: 4029690