The Threshold for Subgroup Profiles to Agree is Logarithmic

by James B. Wilson

Theory of Computing, Volume 15(19), pp. 1-25, 2019

Bibliography with links to cited articles

[1]   László Babai: Graph isomorphism in quasipolynomial time [extended abstract]. In Proc. 48th STOC, pp. 684–697. ACM Press, 2016. [doi:10.1145/2897518.2897542, arXiv:1512.03547]

[2]   Reinhold Baer: Groups with abelian central quotient group. Trans. Amer. Math. Soc., 44(3):357–386, 1938. [doi:10.2307/1989886]

[3]   Donald W. Barnes and Gordon E. Wall: On normaliser preserving lattice isomorphisms between nilpotent groups. J. Austral. Math. Soc., 4(4):454–469, 1964. [doi:10.1017/S1446788700025295]

[4]   Simon R. Blackburn, Peter M. Neumann, and Geetha Venkataraman: Enumeration of finite groups. Volume 173 of Cambridge Tracts in Math. Cambridge Univ. Press, 2007. [doi:10.1017/CBO9780511542756]

[5]   Wieb Bosma, John Cannon, and Catherine Playoust: The Magma algebra system I: The user language. J. Symbolic Comput., 24(3–4):235–265, 1997. [doi:10.1006/jsco.1996.0125]

[6]   H. R. Brahana: Metabelian groups and trilinear forms. Duke Math. J., 1(2):185–197, 1935. [doi:10.1215/S0012-7094-35-00117-X]

[7]   Peter A. Brooksbank, Joshua Maglione, and James B. Wilson: A fast isomorphism test for groups whose Lie algebra has genus 2. J. Algebra, 473:545–590, 2017. [doi:10.1016/j.jalgebra.2016.12.007]

[8]   Peter A. Brooksbank and James B. Wilson: Groups acting on tensor products. J. Pure Appl. Algebra, 218(3):405–416, 2014. [doi:10.1016/j.jpaa.2013.06.011, arXiv:1210.0827]

[9]   Everett C. Dade: Answer to a question of R. Brauer. J. Algebra, 1(1):1–4, 1964. [doi:10.1016/0021-8693(64)90002-X]

[10]   Heiko Dietrich and James B. Wilson: Polynomial-time isomorphism testing of groups of most finite orders, 2018. [arXiv:1806.08872]

[11]   Heiko Dietrich and James B. Wilson: Isomorphism testing of groups of cube-free order. J. Algebra, 545:174–197, 2020. [doi:10.1016/j.jalgebra.2019.02.008, arXiv:1810.03467]

[12]   Bettina Eick, Charles R. Leedham-Green, and Eamonn A. O’Brien: Constructing automorphism groups of p-groups. Communications in Algebra, 30(5):2271–2295, 2002. [doi:10.1081/AGB-120003468]

[13]   George Glauberman and Łukasz Grabowski: Groups with identical k-profiles. Theory of Computing, 11(15):395–401, 2015. [doi:10.4086/toc.2015.v011a015]

[14]   W. Timothy Gowers: Comment on Dick Lipton’s blog entry: The Group Isomorphism Problem: A possible polymath problem? Blog entry started November 7, 2011. Comment cited: November 12, 2011.

[15]   Robert M. Guralnick: On the number of generators of a finite group. Archiv der Mathematik, 53(6):521–523, 1989. [doi:10.1007/BF01199809]

[16]   Zdeněk Hedrlín and Aleš Pultr: On full embeddings of categories of algebras. Illinois J. Math., 10(3):392–406, 1966. [doi:10.1215/ijm/1256054991]

[17]   Thomas W. Hungerford: Algebra. Springer, 1980. [doi:10.1007/978-1-4612-6101-8]

[18]   Nathan Jacobson: Lectures in Abstract Algebra II. Linear Algebra. Springer, 1953. [doi:10.1007/978-1-4684-7053-6]

[19]   Charles R. Leedham-Green and Leonard H. Soicher: Collection from the left and other strategies. J. Symb. Comput., 9(5–6):665–675, 1990. [doi:10.1016/S0747-7171(08)80081-8]

[20]   Charles R. Leedham-Green and Leonard H. Soicher: Symbolic collection using Deep Thought. LMS J. Comput. Math., 1:9–24, 1998. [doi:10.1112/S1461157000000127]

[21]   Mark L. Lewis and James B. Wilson: Isomorphism in expanding families of indistinguishable groups. Groups Complexity Cryptology, 4(1):73–110, 2012. [doi:10.1515/gcc-2012-0008, arXiv:1010.5466]

[22]   Eugene M. Luks: Computing in solvable matrix groups. In Proc. 33rd FOCS, pp. 111–120. IEEE Comp. Soc., 1992. [doi:10.1109/SFCS.1992.267813]

[23]   Gary L. Miller: Graph isomorphism, general remarks. J. Comput. System Sci., 18(2):128–142, 1979. Preliminary version in STOC’77. [doi:10.1016/0022-0000(79)90043-6]

[24]   Adriana Nenciu: Brauer t-tuples. J. Algebra, 322(2):410–428, 2009. [doi:10.1016/j.jalgebra.2009.04.019]

[25]   Derek J. S. Robinson: A Course in the Theory of Groups. Springer, 1996. [doi:10.1007/978-1-4419-8594-1]

[26]   Lajos Rónyai: Private communication, 2011.

[27]   David J. Rosenbaum: Breaking the nlog n barrier for solvable-group isomorphism. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1054–1073. ACM Press, 2013. [doi:10.1137/1.9781611973105.76, arXiv:1205.0642]

[28]   Ada Rottlaender: Nachweis der Existenz nicht-isomorpher Gruppen von gleicher Situation der Untergruppen. Mathematische Zeitschrift, 28(1):641–653, 1928. [doi:10.1007/BF01181188]

[29]   Ákos Seress: Permutation Group Algorithms. Cambridge Univ. Press, 2003. [doi:10.1017/CBO9780511546549]

[30]   Harold M. Stark: On the asymptotic density of the k-free integers. Proc. Amer. Math. Soc., 17(5):1211–1214, 1966. Available on JSTOR.

[31]   Joachim von zur Gathen and Jürgen Gerhard: Modern Computer Algebra. Cambridge Univ. Press, 1999. [doi:10.1017/CBO9781139856065]

[32]   James B. Wilson: Decomposing p-groups via Jordan algebras. J. Algebra, 322(8):2642–2679, 2009. [doi:10.1016/j.jalgebra.2009.07.029, arXiv:0711.0201]

[33]   James B. Wilson: Existence, algorithms, and asymptotics of direct product decompositions, I. Groups Complexity Cryptology, 4(1):33–72, 2012. [doi:10.1515/gcc-2012-0007]