Кіріспе
Топтар теориясында Тодд-Коксетер алгоритмі, 1936 жылы Дж. А. Тодд пен Х. С. М. Коксетер жасаған, косеттерді санау мәселесін шешуге арналған алгоритм болып табылады. Г тобының генераторлар мен қатынастар арқылы берілген ұсынылуы және Г тобының H кіші тобын ескере отырып, алгоритм G-дегі H-ның косеттерін анықтап, косеттер кеңістігіндегі G-нің пермутациялық бейнесін сипаттайды (сол жақтан көбейту арқылы беріледі). Егер Г тобының реті салыстырмалы түрде кіші болса және H кіші тобының күрделі еместігі белгілі болса (мысалы, циклдік топ), онда алгоритмді қолмен орындауға болады және бұл Г тобының түсінікті сипаттамасын береді. Коксетер мен Тодд өз алгоритмдерін қолданып, белгілі топтардың генераторлары арасындағы қатынастардың кейбір жүйелері толық екенін, яғни анықтамалық қатынастар жүйесін құрайтынын көрсетті. Тодд-Коксетер алгоритмі шексіз топтарға да қолданылуы мүмкін және H-ның G-дегі индексі шекті болған жағдайда, шекті қадамдар санында аяқталады. Алайда, топтық ұсынылым мен кіші топтан тұратын кез келген жұп үшін, оның жұмыс істеу уақыты кіші топтың индексінің және кіріс деректерінің мөлшерінің есептеу функциясымен шектелмейді.
Алгоритмнің сипаттамасы
Алгоритмнің бір нұсқасы келесідей орындалады. Егер , генераторлар жиыны болса және қатынастар жиыны болса , онда генераторлар жиыны мен олардың керісін білдіреміз. Анықтайық , мұнда элементтерінің сөздері болады. Қолданылатын кестелердің үш түрі бар: косет кестесі, қатынастар жиынындағы әрбір қатынас үшін қатынас кестесі, және генераторлар жиынының әрбір генераторы үшін кіші топ кестесі. Ақпарат осы кестелерге біртіндеп қосылады, және олар толтырылғаннан кейін барлық косеттер саналады және алгоритм аяқталады. Косет кестесі генератормен көбейту кезінде белгілі косеттер арасындағы қатынастарды сақтау үшін қолданылады. Онда косеттерінің қатарлары және элементтерінің әрқайсысы үшін бағана бар. Косет кестесінің i-ші қатарындағы косетті деп белгілейміз, ал j-ші бағанның генераторын деп белгілейміз. Косет кестесінің i-ші қатары мен j-ші бағанасындағы жазба (белгілі болса) k деп анықталады, мұндағы k қанағаттандырады. Қатынас кестелері біз тапқан кейбір косеттердің іс жүзінде тең екенін анықтау үшін қолданылады. қатынастар жиынындағы әрбір қатынас үшін бір қатынас кестесі сақталады. болсын, мұндағы . Қатынас кестесінде косет кестесіндегідей , косеттерінің қатарлары болады. Онда t бағанасы бар, және i-ші қатар мен j-ші бағандағы жазба (белгілі болса) k деп анықталады, мұндағы . Әсіресе, бастапқыда 'th жазба i-ге тең, себебі . Соңында, кіші топ кестелері қатынас кестелеріне ұқсас, тек олар генераторлардың қатынастарын қадағалайды. генераторлар жиынының әрбір генераторы үшін, , біз кіші топ кестесін жасаймыз. Онда тек бір қатары бар, ол өзінің косетіне сәйкес келеді. Онда t бағанасы бар, және j-ші бағандағы жазба (белгілі болса) k деп анықталады, мұндағы . Қатынас немесе кіші топ кестесінің қатары толтырылған кезде жаңа ақпарат бөлігі , табылады. Бұл шегерім деп аталады. Шегерімнен біз қатынас және кіші топ кестелерінің қосымша жазбаларын толтыра аламыз, нәтижесінде қосымша шегерімдер пайда болуы мүмкін. Біз косет кестесінің теңдеулерге сәйкес келетін жазбаларын толтыра аламыз және . Алайда, косет кестесін толтыру кезінде, бізде теңдеуге арналған жазба бар болуы мүмкін, бірақ жазбаның басқа мәні бар. Бұл жағдайда біз екі косетіміздің бір-бірімен сәйкес келетінін анықтадық, бұл кездейсоқтық деп аталады. Мысалы, болсын, мұндағы . Кестелердегі "j" санының барлық орындарын "i" санымен ауыстырамыз. Содан кейін кестедегі барлық мүмкін жазбаларды толтырамыз, бұл одан да көп шегерімдер мен кездейсоқтықтарға әкелуі мүмкін. Барлық шегерімдер мен кездейсоқтықтар ескерілгеннен кейін кестеде бос жазбалар болса, кестелерге жаңа косетті қосып, процесті қайталаймыз. Косеттерді қосу кезінде, егер Hx белгілі косет болса, онда Hxg барлық үшін белгілі бір уақытта қосылатынын қадағалаймыз (Бұл алгоритмнің аяқталуын қамтамасыз ету үшін қажет). Барлық кестелер толтырылған кезде алгоритм аяқталады. Содан кейін бізде косеттеріне әрекеті туралы барлық қажетті ақпарат болады.
The relation tables are used to detect when some of the cosets we have found are actually equivalent. One relation table for each relation in is maintained. Let be a relation in , where The relation table has rows representing the cosets of , as in the coset table. It has t columns, and the entry in the ith row and jth column is defined to be (if known) k, where In particular, the 'th entry is initially i, since
Finally, the subgroup tables are similar to the relation tables, except that they keep track of possible relations of the generators of For each generator of , with , we create a subgroup table. It has only one row, corresponding to the coset of itself. It has t columns, and the entry in the jth column is defined (if known) to be k, where
When a row of a relation or subgroup table is completed, a new piece of information , , is found. This is known as a deduction. From the deduction, we may be able to fill in additional entries of the relation and subgroup tables, resulting in possible additional deductions. We can fill in the entries of the coset table corresponding to the equations and
However, when filling in the coset table, it is possible that we may already have an entry for the equation, but the entry has a different value. In this case, we have discovered that two of our cosets are actually the same, known as a coincidence. Suppose , with We replace all instances of j in the tables with i. Then, we fill in all possible entries of the tables, possibly leading to more deductions and coincidences. If there are empty entries in the table after all deductions and coincidences have been taken care of, add a new coset to the tables and repeat the process. We make sure that when adding cosets, if Hx is a known coset, then Hxg will be added at some point for all (This is needed to guarantee that the algorithm will terminate provided is finite.) When all the tables are filled, the algorithm terminates. We then have all needed information on the action of on the cosets of .