Todd–Coxeter algorithm
In group theory, the Todd–Coxeter algorithm, created by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group G by generators and relations and a subgroup H of G, the algorithm enumerates the cosets of H on G and describes the permutation representation of G on the space of the cosets (given by the left multiplication action). If the order of a group G is relatively small and the subgroup H is known to be uncomplicated (for example, a cyclic group), then the algorithm can be carried out by hand and gives a reasonable description of the group G. Using their algorithm, Coxeter and Todd showed that certain systems of relations between generators of known groups are complete, i.e. constitute systems of defining relat
- Comment
- enIn group theory, the Todd–Coxeter algorithm, created by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group G by generators and relations and a subgroup H of G, the algorithm enumerates the cosets of H on G and describes the permutation representation of G on the space of the cosets (given by the left multiplication action). If the order of a group G is relatively small and the subgroup H is known to be uncomplicated (for example, a cyclic group), then the algorithm can be carried out by hand and gives a reasonable description of the group G. Using their algorithm, Coxeter and Todd showed that certain systems of relations between generators of known groups are complete, i.e. constitute systems of defining relat
- Has abstract
- enIn group theory, the Todd–Coxeter algorithm, created by J. A. Todd and H. S. M. Coxeter in 1936, is an algorithm for solving the coset enumeration problem. Given a presentation of a group G by generators and relations and a subgroup H of G, the algorithm enumerates the cosets of H on G and describes the permutation representation of G on the space of the cosets (given by the left multiplication action). If the order of a group G is relatively small and the subgroup H is known to be uncomplicated (for example, a cyclic group), then the algorithm can be carried out by hand and gives a reasonable description of the group G. Using their algorithm, Coxeter and Todd showed that certain systems of relations between generators of known groups are complete, i.e. constitute systems of defining relations. The Todd–Coxeter algorithm can be applied to infinite groups and is known to terminate in a finite number of steps, provided that the index of H in G is finite. On the other hand, for a general pair consisting of a group presentation and a subgroup, its running time is not bounded by any computable function of the index of the subgroup and the size of the input data.
- Hypernym
- Algorithm
- Is primary topic of
- Todd–Coxeter algorithm
- Label
- enTodd–Coxeter algorithm
- Link from a Wikipage to an external page
- www.ams.org/notices/199706/seress.pdf
- Link from a Wikipage to another Wikipage
- Algorithm
- Category:Computational group theory
- Computable function
- Coset
- Coset enumeration
- Coxeter group
- Cyclic group
- Ergebnisse der Mathematik und ihrer Grenzgebiete
- Generating set of a group
- Group action (mathematics)
- Group theory
- H. S. M. Coxeter
- Index (group theory)
- J. A. Todd
- Notices of the American Mathematical Society
- Order of a group
- Presentation of a group
- Proceedings of the Edinburgh Mathematical Society
- Relation (mathematics)
- Springer-Verlag
- Subgroup
- SameAs
- 4rjgS
- Algorithme de Todd-Coxeter
- m.03mm44
- Q690505
- Todd-Coxeter-Algorithmus
- Todd-Coxeter-algoritme
- Алгоритм Тодда — Коксетера
- الگوریتم تاد–کاکسیتر
- Subject
- Category:Computational group theory
- WasDerivedFrom
- Todd–Coxeter algorithm?oldid=951498203&ns=0
- WikiPageLength
- 6653
- Wikipage page ID
- 894779
- Wikipage revision ID
- 951498203
- WikiPageUsesTemplate
- Template:Cite book
- Template:Cite journal