Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Todd–Coxeter algorithm
open-in-new
<p>In <a href="/facts/Group_theory/NfowcI5H">group theory</a>, the Todd–Coxeter algorithm, created by <a href="/facts/J._A._Todd/9qhLwNgb">J. A. Todd</a> and <a href="/facts/H._S._M._Coxeter/D2l5jWGG">H. S. M. Coxeter</a> in 1936, is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for solving the <a href="/facts/Coset_enumeration/RagjtDcH">coset enumeration</a> problem. Given a <a href="/facts/Presentation_of_a_group/f9emPUoI">presentation of a group</a> <i>G</i> by generators and relations and a <a href="/facts/Subgroup/r91mBgpa">subgroup</a> <i>H</i> of <i>G</i>, the algorithm enumerates the <a href="/facts/Coset/zFgQUTLY">cosets</a> of <i>H</i> on <i>G</i> and describes the <a href="/facts/Group_action_(mathematics)/Vh9VtUUw">permutation representation</a> of <i>G</i> on the space of the cosets (given by the left multiplication action). If the <a href="/facts/Order_of_a_group/Cl3tKGFg">order of a group</a> <i>G</i> is relatively small and the subgroup <i>H</i> is known to be uncomplicated (for example, a <a href="/facts/Cyclic_group/JL5zfFuL">cyclic group</a>), then the algorithm can be carried out by hand and gives a reasonable description of the group <i>G</i>. 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. </p><p>The Todd–Coxeter algorithm can be applied to infinite groups and is known to terminate in a finite number of steps, provided that the <a href="/facts/Index_(group_theory)/ewY2A71Y">index</a> of <i>H</i> in <i>G</i> 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 <a href="/facts/Computable_function/dzwBlLGn">computable function</a> of the index of the subgroup and the size of the input data. </p>