Abstract
In this article, we will discuss algorithmic group theory from the point of view of pure mathematics. We will investigate some of the problems and show why many problems are accessible just for a few years. In algebra there are many problems, which are easy to state, sometimes even easy to prove, and where one might be surprised that there is no algorithmic solution. The two most developed areas of algebra in the sense of existence of algorithms are number theory and group theory. As the understanding of the algorithms in number theory usually needs a lot of deep theory I will restrict myself mainly to group theory. We will look at the algorithms by themselves and not which one is better to implement and similar questions. So this paper will be also interesting for all those who will probably never use a computer to solve a problem. We will see that to find algorithms for basic or more advanced questions is a deep mathematical problem, which uses many results in pure mathematics, and even more important, raises new questions in pure mathematics. So we can say that looking for algorithms is part of pure mathematics, moreover it is a highly nontrivial part.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
W. Burnside, Theory of finite groups, 2nd. edn. Cambridge 1911; Dover Publications, 1955
E. Cartan, Ouevres Completes I-1, Paris, Gauthier-Villars, 1952.
Chevalley, Sur certains groupes simple, Tohoku Math. J. 7, 1955, 14–66.
C. Chevalley, Seminaire Chevalley, Classification des Groupes de Lie Algebriques, Vol. 2, Paris 1956-58.
A. L. Chistov, D. Yu. Grigoryev, Polynomial time factoring of the multivariable polynomials over a global field, LOMI preprint E5-82, Leningrad 1982.
L. Dickson, A class of groups in an arbitrary realm connected with the configuration of the 27 lines in a cubic surface, J. Math. 33, 1901, 145–173.
M. Furst, J. Hopcroft, E. Luks, Polynomial-time algorithms for permutation groups, Proc. 21st IEEE Symposium Foundations of Computer Science, 1980, 36–41.
W. Kantor, Permutation representations of the finite classical groups of small degree or rank, J. Algebra 60, 1979, 158–168.
W. Kantor, Polynomial-time algorithms for finding elements of prime order and Sylow subgroups, J. Algorithms 6, 1985, 478–514.
W. Kantor, Sylow’s theorem in polynomial time, J. Comput. Syst. Sci. 30, 1985, 359–394.
S. Landau, Factoring polynomials over algebraic number fields, SIAM J. on 14, 1985, 184–195.
A. Lenstra, Factoring polynomials over algebraic number fields, Lecture Notes of Computer Science 162 (Proc. of EUROCAL), Springer 1983, 245–254.
A. Lenstra, H.W. Lenstra Jr., L. Lovasz, Factoring polynomials with rational coefficients, Math. Annalen 261, 1982, 515–534.
M. Liebeck, C.E. Praeger, J. Saxl, On the O’Nan-Scott theorem for finite primitive permutation groups, J. Australian Math. Soc. 44, 1988, 389–396.
E.M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. Syst. Sci. 25 (1982), 42–65.
E. Mathieu, Memoire sur le nombre de valeurs que peut acquerir une fonction quand on y permut ses variables de toutes les manieres possible, Liouville’s J. 5, 1860, 9–42.
E. Mathieu, Memoire sur l’etudes des fonctions de plusieurs quantites sur la maniere de les formes et sur les substitutions qui les laissent invariables, Liouville’s J. 6, 1861, 241–323.
E. Mathieu, Sur la fonction cinq fois transitive des 24 quantites, Liouville’s J. 18, 1873, 25–46.
J. Palfy, A polynomial bound for the orders of primitive solvable groups, J.Alg. 77 (1982), 127–137.
M. Pohst, H. Zassenhaus, Algorithmic algebraic number theory, Cambridge Univ. Press, 1989.
L. Pyber, A. Shalev, Asymptotic results for primitive permutation groups, J. Alg. 188, 1997, 103–124.
R. Ree, A family of simple groups associated with the simple Lie algebra F 4, Amer.J. Math. 83, 1961, 401–420.
R. Ree, A family of simple groups associated with the simple Lie algebra G2,Amer. J. Math. 83, 1961, 432–462.
L. Ronyai, Zero divisors in quaternion algebras, J. Algorithms 9, 1988, 494–506.
R. Steinberg, Variations on a theme of Chevalley, Pacific J. Math. 9, 1959, 875–891.
M. Suzuki, On a class of double transitive groups I,II, Ann. of Math. 75, 1962, 105–145, 79, 1964, 514–589.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg 2001
About this chapter
Cite this chapter
Stroth, G. (2001). Algorithms in Pure Mathematics. In: Alt, H. (eds) Computational Discrete Mathematics. Lecture Notes in Computer Science, vol 2122. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45506-X_11
Download citation
DOI: https://doi.org/10.1007/3-540-45506-X_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42775-9
Online ISBN: 978-3-540-45506-6
eBook Packages: Springer Book Archive