Testing isomorphism of graded algebras

Brooksbank, Peter; O’Brien, E.; Wilson, James

doi:10.1090/tran/7884

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.