Example data table
| Example | Generators | Relators | Subgroup | Expected index | Notes |
|---|---|---|---|---|---|
| S₃ as a presentation | a, b | a^2; b^3; (a b)^2 | b | 2 | Index of ⟨b⟩ in the group is two. |
Formula used
This tool implements a Todd–Coxeter style coset enumeration process. It builds a coset table for a finitely presented group < X | R > relative to a subgroup H given by words in X.
- Coset action: each table entry represents c · x for a coset c and generator x.
- Relator constraint: for every relator word r, enforce c · r = c.
- Subgroup constraint: for each subgroup word h, enforce 1 · h = 1.
- Coincidences: when constraints imply two cosets are equal, they are merged.
- Index estimate: the number of live cosets after merges is the current index estimate.
How to use this calculator
- Enter generator names, then list relators as words that evaluate to the identity.
- Enter subgroup generator words (optional). Leaving it blank means the trivial subgroup.
- Start with moderate limits, then increase max cosets or passes if needed.
- Use conservative mode to avoid expanding, or aggressive mode to finish finite cases.
- After a run, review the index estimate and the coset table entries.
- Export results to CSV, or download a PDF report for notes.
Input choices and expected table growth
Coset enumeration starts with the subgroup coset 1 and grows a table by applying every generator and inverse. If you enter 2 generators, the table has 4 columns (a, a^-1, b, b^-1). With 40 live cosets, that is 160 potential transitions to define. Presentations with 3 generators already create 6 columns, so the same 40 cosets imply 240 slots, which makes limits meaningful.
Pass limits, definitions, and coincidences
A “definition” occurs when an undefined entry forces creation of a new coset to satisfy a scan. A “coincidence” occurs when scans imply two cosets must be the same, so they are merged using union‑find. In many finite examples, coincidences surge late: a run may define 120 cosets, then collapse to 24 live cosets after merges. Tracking both counts helps diagnose whether growth is real or temporary.
Index estimate as a measurable outcome
The index estimate is the number of live cosets after merges. When the table becomes complete (every live coset has every column filled), this value equals the subgroup index [G:H]. When the run is partial, treat it as a provisional lower bound that can increase. A stable index across multiple passes, with few new definitions, is a practical sign you are close to completion. For classroom checks, compare the completed table against known group order, or rerun with higher limits to confirm the same index repeats reliably again.
Relators, subgroup words, and simplification
Each relator r enforces c·r=c for every coset c, while each subgroup word h enforces 1·h=1. Words are scanned symbol by symbol, so shorter scans are faster and less error‑prone. Optional simplification cancels adjacent inverses, reducing length; for instance a b b^-1 a^-1 simplifies to the empty word. Rewriting relators into balanced lengths can also reduce branching.
Operational limits and exportable evidence
Max cosets caps memory growth, max passes controls repeated scanning, and the time limit prevents long stalls. Conservative mode reduces branching, while aggressive mode pushes completion in finite cases at the cost of more temporary definitions. Export CSV to audit specific rows, then use the PDF report as a reproducible record of inputs, limits, and the resulting table.
FAQs
1) What does a complete table mean?
A table is complete when every live coset has a defined transition for every generator and inverse. In that case, the live coset count equals the subgroup index and the remaining blanks should be zero.
2) Why did the run stop early?
Stopping usually means you hit the max cosets, the time limit, or the max passes. Increase one limit at a time and rerun, or switch modes to change how aggressively new definitions are introduced.
3) What is a coincidence in the output?
A coincidence is a forced equality between two cosets discovered during a relator or subgroup scan. The tool merges them and rewrites references, which can sharply reduce the live coset count and change the table structure.
4) How should I choose max cosets and passes?
Start with a max cosets value slightly above your expected index times a safety factor, such as 5× to 10×. If definitions keep rising, raise cosets; if definitions are stable but completion lags, raise passes.
5) Can this prove a group is infinite?
No. Failure to complete only shows the chosen strategy and limits did not finish. Some infinite groups still produce partial tables, and some difficult finite presentations need different relators or higher limits.
6) How do I interpret zeros or missing entries?
Zeros indicate an undefined transition at the time the snapshot was taken. In partial runs, undefined entries are expected. In complete runs, zeros should not appear for live cosets; rerun with higher limits if they do.
Notes and limitations
Coset enumeration can be computationally demanding. Some presentations may not complete within the chosen limits, may grow past the max cosets, or may stop at the time limit. For best results, keep examples small and well-conditioned.