Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Probabilistic and Asymptotic Aspects of Finite Simple Groups Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

2. Estimation Problems and Randomised Group Algorithms

verfasst von : Alice C. Niemeyer, Cheryl E. Praeger, Ákos Seress

Erschienen in: Probabilistic Group Theory, Combinatorics, and Computing

Verlag: Springer London

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This chapter discusses the role of estimation in the design and analysis of randomised algorithms for computing with finite groups.An exposition is given of a variety of different approaches to estimating proportions of important element classes, including geometric methods, and the use of generating functions and the theory of Lie type groups.Numerous results concerning estimation in permutation groups and finite classical groups are surveyed.An application is given to the construction of involution centralisers, a crucial component in the constructive recognition of finite simple groups.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Probabilistic and Asymptotic Aspects of Finite Simple Groups
Nächstes Kapitel Designs, Groups and Computing
Fußnoten
1
Translation by Peter M. Neumann, The Queen’s College, University of Oxford.
 
Literatur
1.
C. Altseimer, A.V. Borovik, Probabilistic Recognition of Orthogonal and Symplectic Groups, in Groups and Computation, III, vol. 8, Columbus, OH, 1999 (Ohio State University Mathematical Research Institute Publications/de Gruyter, Berlin, 2001), pp. 1–20
2.
3.
L. Babai, Local Expansion of Vertex-Transitive Graphs and Random Generation in Finite Groups, in 23rd ACM Symposium on Theory of Computing (ACM, New York, 1991), pp. 164–174
4.
L. Babai, R. Beals, A Polynomial-Time Theory of Black Box Groups. I, in Groups St. Andrews 1997 in Bath, I. London Mathematical Society Lecture Note Series, vol. 260 (Cambridge University Press, Cambridge, 1999), pp. 30–64
5.
L. Babai, E. Szemerédi, On the Complexity of Matrix Group Problems I, in 25th Annual Symposium on Foundations of Computer Science (IEEE Computer Society Press, Los Alamitos, 1984), pp. 229–240
6.
L. Babai, W.M. Kantor, P.P. Pálfy, Á. Seress, Black-box recognition of finite simple groups of Lie type by statistics of element orders. J. Group Theor. 5(4), 383–401 (2002)MATH
7.
L. Babai, R. Beals, Á. Seress, Polynomial-Time Theory of Matrix Groups, in 41st ACM Symposium on Theory of Computing, Bethesda, MD, 2009 (ACM, New York, 2009), pp. 55–64CrossRef
8.
R. Beals, C.R. Leedham-Green, A.C. Niemeyer, C.E. Praeger, Á. Seress, Permutations with restricted cycle structure and an algorithmic application. Combin. Probab. Comput. 11(5), 447–464 (2002)MathSciNetMATH
9.
R. Beals, C.R. Leedham-Green, A.C. Niemeyer, C.E. Praeger, Á. Seress, A black-box group algorithm for recognizing finite symmetric and alternating groups. I. Trans. Am. Math. Soc. 355(5), 2097–2113 (2003)MathSciNetMATHCrossRef
10.
11.
12.
E.A. Bertram, B. Gordon, Counting special permutations. Eur. J. Comb. 10(3), 221–226 (1989)MathSciNetMATH
13.
14.
M. Bóna, A. McLennan, D. White, Permutations with roots. Random Struct. Algorithm 17(2), 157–167 (2000)MATHCrossRef
15.
W. Bosma, J. Cannon, C. Playoust, The Magma algebra system. I. The user language. J. Symbolic Comput. 24, 235–265 (1997)MathSciNetMATHCrossRef
16.
J.N. Bray, An improved method for generating the centralizer of an involution. Arch. Math. (Basel) 74(4), 241–245 (2000)
17.
R.W. Carter, Finite Groups of Lie Type (Wiley Classics Library, Wiley, Chichester, 1993), Conjugacy classes and complex characters, Reprint of the 1985 original, A Wiley-Interscience Publication
18.
F. Celler, C.R. Leedham-Green, S.H. Murray, A.C. Niemeyer, E.A. O’Brien, Generating random elements of a finite group. Comm. Algebra 23(13), 4931–4948 (1995)MathSciNetMATHCrossRef
19.
W.W. Chernoff, Solutions to x r  = α in the alternating group. Ars Combin. 29(C), 226–227 (1990) (Twelfth British Combinatorial Conference, Norwich, 1989)
20.
S. Chowla, I.N. Herstein, W.K. Moore, On recursions connected with symmetric groups. I. Can. J. Math. 3, 328–334 (1951)MathSciNetMATHCrossRef
21.
S. Chowla, I.N. Herstein, W.R. Scott, The solutions of x d  = 1 in symmetric groups. Norske Vid. Selsk. Forh. Trondheim 25, 29–31 (1952/1953)
22.
23.
A. de Moivre, The Doctrine of Chances: Or, A Method of Calculating the Probability of Events in Play, 2nd edn. (H. Woodfall, London, 1738)
24.
J.D. Dixon, Generating random elements in finite groups. Electron. J. Comb. 15(1), Research Paper 94 (2008)
25.
P. Dusart, The kth prime is greater than \(k(\ln k +\ln \ln k - 1)\) for k ≥ 2. Math. Comp. 68(225), 411–415 (2009)MathSciNetCrossRef
26.
P. Erdős, M. Szalay, On Some Problems of the Statistical Theory of Partitions, in Number Theory, vol. I, Budapest, 1987. Colloq. Math. Soc. János Bolyai, vol. 51 (North-Holland, Amsterdam, 1990), pp. 93–110
27.
P. Erdős, P. Turán, On some problems of a statistical group-theory. I. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 4, 175–186 (1965)CrossRef
28.
P. Erdős, P. Turán, On some problems of a statistical group-theory. II. Acta Math. Acad. Sci. Hung. 18, 151–163 (1967)CrossRef
29.
P. Erdős, P. Turán, On some problems of a statistical group-theory. III. Acta Math. Acad. Sci. Hung. 18, 309–320 (1967)CrossRef
30.
P. Erdős, P. Turán, On some problems of a statistical group-theory. IV. Acta Math. Acad. Sci. Hung. 19, 413–435 (1968)CrossRef
31.
P. Erdős, P. Turán, On some problems of a statistical group theory. VI. J. Indian Math. Soc. 34(3–4), 175–192 (1970/1971)
32.
P. Erdős, P. Turán, On some problems of a statistical group theory. V. Period. Math. Hung. 1(1), 5–13 (1971)CrossRef
33.
L. Euler, Calcul de la probabilité dans le jeu de rencontre. Mémoires de l’Academie des Sciences de Berlin, 7 (1751) 1753, pp. 255–270. Reprinted in Opera Omnia: Series 1, vol. 7, pp. 11–25. Available through The Euler Archive at www.​EulerArchive.​org.
34.
L. Euler, Solutio Quaestionis curiosae ex doctrina combinationum. Mémoires de l’Académie des Sciences de St.-Petersbourg, 3:57–64, 1811. Reprinted in Opera Omnia: Series 1, vol. 7, pp. 435–440. Available through The Euler Archive at www.​EulerArchive.​org.
35.
P. Flajolet, R. Sedgewick, Analytic Combinatorics (Cambridge University Press, Cambridge, 2009)MATHCrossRef
36.
J. Fulman, P.M. Neumann, C.E. Praeger, A generating function approach to the enumeration of matrices in classical groups over finite fields. Mem. Am. Math. Soc. 176(830), vi+90 (2005)
37.
38.
S.P. Glasby, Using recurrence relations to count certain elements in symmetric groups. Eur. J. Comb. 22(4), 497–501 (2001)MathSciNetMATHCrossRef
39.
40.
V. Gončarov, On the field of combinatory analysis. Am. Math. Soc. Transl. 19(2), 1–46 (1962)
41.
D. Gorenstein, R. Lyons, R. Solomon, The Classification of the Finite Simple Groups. Mathematical Surveys and Monographs, vol. 40 (American Mathematical Society, Providence, 1994)
42.
43.
W.K. Hayman, A generalisation of Stirling’s formula. J. Reine Angew. Math. 196, 67–95 (1956)MathSciNetMATH
44.
45.
P.E. Holmes, S.A. Linton, E.A. O’Brien, A.J.E. Ryba, R.A. Wilson, Constructive membership in black-box groups. J. Group Theor. 11(6), 747–763 (2008)MathSciNetMATH
46.
I.M. Isaacs, W.M. Kantor, N. Spaltenstein, On the probability that a group element is p-singular. J. Algebra 176(1), 139–181 (1995)MathSciNetMATHCrossRef
47.
E. Jacobsthal, Sur le nombre d’éléments du groupe symétrique S n dont l’ordre est un nombre premier. Norske Vid. Selsk. Forh. Trondheim 21(12), 49–51 (1949)MathSciNetMATH
48.
W.M. Kantor, Á. Seress, Black box classical groups. Mem. Am. Math. Soc. 149(708), viii+168 (2001)
49.
A.V. Kolchin, Equations that contain an unknown permutation. Diskret. Mat. 6(1), 100–115 (1994)MathSciNet
50.
V.F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications, vol. 53 (Cambridge University Press, Cambridge, 1999)
51.
E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen. 2 Bände, 2nd edn. (Chelsea Publishing Co., New York, 1953), With an appendix by Paul T. Bateman
52.
C.R. Leedham-Green, The Computational Matrix Group Project, in Groups and Computation, III, vol. 8, Columbus, OH, 1999 (Ohio State University Mathematical Research Institute Publications/de Gruyter, Berlin, 2001), pp. 229–247
53.
C.R. Leedham-Green, E.A. O’Brien, Constructive recognition of classical groups in odd characteristic. J. Algebra 322(3), 833–881 (2009)MathSciNetMATHCrossRef
54.
G.I. Lehrer, Rational tori, semisimple orbits and the topology of hyperplane complements. Comment. Math. Helv. 67(2), 226–251 (1992)MathSciNetMATHCrossRef
55.
56.
M.W. Liebeck, E.A. O’Brien, Finding the characteristic of a group of Lie type. J. Lond. Math. Soc. (2) 75(3), 741–754 (2007)
57.
58.
F. Lübeck, A.C. Niemeyer, C.E. Praeger, Finding involutions in finite Lie type groups of odd characteristic. J. Algebra 321(11), 3397–3417 (2009)MathSciNetMATHCrossRef
59.
E.M. Luks, Permutation Groups and Polynomial-Time Computation, in Groups and computation, New Brunswick, NJ, 1991. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 11 (American Mathematical Society, Providence, 1993), pp. 139–175
60.
61.
A. Maróti, Symmetric functions, generalized blocks, and permutations with restricted cycle structure. Eur. J. Comb. 28(3), 942–963 (2007)MATHCrossRef
62.
N. Metropolis, The beginnings of the Monte Carlo method. Los Alamos Sci. 15 (Special Issue), 125–130 (1987)
63.
M.P. Mineev, A.I. Pavlov, The number of permutations of a special form. Mat. Sb. (N.S.) 99(141)(3), 468–476, 480 (1976)
64.
P.R. de Monmort, Essay d’analyse sur les jeux de hazard (J. Quillau, Paris, 1708)
65.
P.R. de Monmort, Essay d’analyse sur les jeux de hazard, 2nd edn. (J. Quillau, Paris, 1713)
66.
67.
68.
69.
P.M. Neumann, C.E. Praeger, A recognition algorithm for special linear groups. Proc. Lond. Math. Soc. (3) 65 (3), 555–603 (1992)
70.
P.M. Neumann, C.E. Praeger, Cyclic matrices over finite fields. J. Lond. Math. Soc. (2) 52, 263–284 (1995)
71.
72.
A.C. Niemeyer, C.E. Praeger, A recognition algorithm for classical groups over finite fields. Proc. Lond. Math. Soc. (3) 77 (1), 117–169 (1998)
73.
A.C. Niemeyer, C.E. Praeger, On the frequency of permutations containing a long cycle. J. Algebra 300(1), 289–304 (2006)MathSciNetMATHCrossRef
74.
75.
A.C. Niemeyer, C.E. Praeger, On the proportion of permutations of order a multiple of the degree. J. Lond. Math. Soc. (2) 76(3), 622–632 (2007)
76.
A.C. Niemeyer, C.E. Praeger, Estimating proportions of elements in finite groups of Lie type. J. Algebra 324(1), 122–145 (2010)MathSciNetMATHCrossRef
77.
E.A. O’Brien, Algorithms for Matrix Groups, in Groups St. Andrews 2009 in Bath, vol. 2. London Mathematical Society Lecture Note Series, vol. 388 (Cambridge University Press, Cambridge, 2011), pp. 297–323
78.
C.W. Parker, R.A. Wilson, Recognising simplicity of black-box groups by constructing involutions and their centralisers. J. Algebra 324(5), 885–915 (2010)MathSciNetMATHCrossRef
79.
E.T. Parker, P.J. Nikolai, A search for analogues of the Mathieu groups. Math. Tables Aids Comput. 12, 38–43 (1958)MathSciNetCrossRef
80.
A.I. Pavlov, An equation in a symmetric semigroup. Trudy Mat. Inst. Steklov. 177, 114–121, 208 (1986); Proc. Steklov Inst. Math. 1988(4), 121–129, Probabilistic problems of discrete mathematics
81.
A.I. Pavlov, On permutations with cycle lengths from a fixed set. Theor. Probab. Appl. 31, 618–619 (1986)
82.
W. Plesken, D. Robertz, The average number of cycles. Arch. Math. (Basel) 93(5), 445–449 (2009)
83.
84.
C.E. Praeger, Á. Seress, Probabilistic generation of finite classical groups in odd characteristic by involutions. J. Group Theor. 14(4), 521–545 (2011)MathSciNetMATH
85.
C.E. Praeger, Á. Seress, Balanced involutions in the centralisers of involutions in finite general linear groups of odd characteristic (in preparation)
86.
C.E. Praeger, Á. Seress, Regular semisimple elements and involutions in finite general linear groups of odd characteristic. Proc. Am. Math. Soc. 140, 3003–3015 (2012)MathSciNetCrossRef
87.
Á. Seress, Permutation Group Algorithms. Cambridge Tracts in Mathematics, vol. 152 (Cambridge University Press, Cambridge, 2003)
88.
C.C. Sims, Computational Methods in the Study of Permutation Groups, in Computational Problems in Abstract Algebra, Proceedings of the Conference, Oxford, 1967 (Pergamon, Oxford, 1970), pp. 169–183
89.
C.C. Sims, The Existence and Uniqueness of Lyons’ Group, in Finite groups ’72, Proceedings of the Gainesville Conference, University of Florida, Gainesville, FL, 1972. North–Holland Mathematical Studies, vol. 7 (North-Holland, Amsterdam, 1973), pp. 138–141
90.
A.N. Timashev, Random permutations with cycle lengths in a given finite set. Diskret. Mat. 20(1), 25–37 (2008)MathSciNet
91.
92.
L.M. Volynets, The number of solutions of the equation x s  = e in a symmetric group. Mat. Zametki 40(2), 155–160, 286 (1986)
93.
R. Warlimont, Über die Anzahl der Lösungen von x n  = 1 in der symmetrischen Gruppe S n . Arch. Math. (Basel) 30 (6), 591–594 (1978)
94.
H. Wielandt, Finite Permutation Groups, Translated from the German by R. Bercov (Academic, New York, 1964)MATH
95.
H.S. Wilf, The asymptotics of e P(z) and the number of elements of each order in S n . Bull. Am. Math. Soc. (N.S.) 15 (2), 228–232 (1986)
96.
H.S. Wilf, Generatingfunctionology, 2nd edn. (Academic, Boston, 1994)MATH
97.
Metadaten
Titel
Estimation Problems and Randomised Group Algorithms
verfasst von
Alice C. Niemeyer
Cheryl E. Praeger
Ákos Seress
Copyright-Jahr
2013
Verlag
Springer London
Buch
Probabilistic Group Theory, Combinatorics, and Computing

Print ISBN: 978-1-4471-4813-5

Electronic ISBN: 978-1-4471-4814-2

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4471-4814-2_2