Enumerating the Subgroups of a Group, Without GAP

Vladimir Bulatov's symmetry software (symmhub / sympic) needs, for a given symmetry group, the list of its finite-index subgroups — each subgroup of index N is a way of splitting a periodic pattern into N color classes. Today that list is produced offline: a script writes the group's generators and relations into a file, the computer-algebra system GAP runs LowIndexSubgroupsFpGroup, and the output is post-processed into JSON that the web application loads.

That pipeline works, but only for groups computed in advance. A group written interactively — say an orbifold symbol typed into a browser — cannot be handled, because GAP sits on a desktop machine, not in the page:

«Моя имплементация состоит в том, что я готовлю данные для GAP … всю работу делает GAP. … Было бы замечательно, если бы это можно было бы на JavaScript иметь имплементацию.» — V. Bulatov, conversation of 5 Aug 2026 (ocean-trip transcript)

This page is that replacement: a self-contained JavaScript library (subgroups-core.js, no dependencies, runs in any browser) that takes a description of a group and enumerates its subgroups — plus the mathematical background needed to understand what, exactly, should be counted.

The question comes out of color symmetry. A perfect coloring of a periodic pattern with N colors is one where every symmetry of the uncolored pattern permutes the color classes. Choose one color; the symmetries fixing it (as a set) form a subgroup H of the full symmetry group G with index [G:H] = N, and the colors are exactly the cosets G/H. So:

Thomas W. Wieting (Reed College, 1938–2021), in The Mathematical Theory of Chromatic Plane Ornaments (1982), cataloged the color groups of all 17 wallpaper groups for every number of colors up to 60 — 8,123 color groups in total, announced at an AMS meeting in 1977. His Table 11 is preserved as OEIS A307293:

a(1)=17 is the wallpaper groups themselves; a(2)=46 the classical black-and-white groups. Wieting's totals corrected earlier tables: Jarratt & Schwarzenberger's 1980 census disagreed at indices 8, 12, 14, and the comparison exposed errors in the earlier work.

How did he compute it, on 1970s hardware? Research into the sources (see §9) identifies the method with high confidence as Marjorie Senechal's finite-index subgroup algorithm (“A simple characterization of the subgroups of space groups,” Acta Cryst. A36, 1980). Senechal states directly in her 1988 survey that Wieting used her algorithm to compute the color groups of the 17 plane groups through 60 colors. Jarratt & Schwarzenberger add that Wieting had two methods: a generators-and-relations method for N ≤ 5, and the structural method for N ≤ 60 — a foreshadowing of the two main algorithms on this page. No listing, deck, or tape of Wieting's original program is known to survive; everything here is a modern reconstruction.

The task must be stated carefully; the honest version depends on the group.

• Finite group. There is an exact, terminating answer: every subgroup can be listed. (The output can be large — that is the only obstruction.)
• Infinite group (e.g. a wallpaper group). Listing all subgroups is impossible — a free group of rank 2 already has uncountably many. The computable and useful problem is: enumerate the subgroups of index ≤ N. For wallpaper groups these are exactly the subgroups that produce colorings with at most N colors, so nothing of interest is lost.

This is precisely what GAP's LowIndexSubgroupsFpGroup does, and what Vladimir uses today with maxIndex = 24. There is no size limit on the group itself — the algorithm works from generators and relations, and wallpaper groups, although infinite, are finitely presented. For example his file groups_wp.g presents p3 (orbifold 333) as

F := FreeGroup("a","b","c","d");
return F / [ a^3, b^3, a*c, b*d, (a*d)^3 ];

(The auxiliary generators c, d are declared inverse to a, b so that subgroup generator words come out "positive" — a convention of his coloring pipeline, preserved in the presets below.)

Before any algorithm, a design choice decides how many subgroups the answer contains. Three natural equivalences give three different catalogs, all "correct":

4.1 The p3 example: why Vladimir counts more than Wieting

The wallpaper group p3 (orbifold 333) is generated by 120° rotations about the three corners of an equilateral triangle. All three rotation centers look alike: a symmetry of the group's own structure permutes them. But that permuting map is not an element of p3 — it is an outer automorphism.

«Когда я задаю, я говорю: вот один это генератор А, другой генератор В, третий генератор С — я их различаю. … У меня групп получается больше, потому что у меня эти три генератора разные, чем у него. А у него — перестановка их местами ничего не меняет. … Если я переставлю генераторы местами — паттерн поменяется.» — V. Bulatov, same conversation. He labels the three centers as distinct generators; Wieting's equivalence identifies them.

Concretely, at index 3 the group p3 has:

• 4 conjugacy classes of index-3 subgroups: the translation sublattice-type subgroup, plus three classes of p3-type subgroups, one pinned to each center A, B, C. This is Vladimir's count (and GAP's).
• 2 classes after merging by the outer symmetry that permutes the centers: {translation type} and {center type}. This is Wieting's count.

You can reproduce this in the lab below: preset “333 labeled: x,y,z centers (p3)”, max index 3 — the results table shows 4 conjugacy classes merging into 2.

The same coin has another face mentioned in the conversation: chirality. Some outer automorphisms are orientation-reversing — merging under them identifies a left-handed coloring with its mirror image. Whether that is "the same pattern" is, again, a modeling decision, not a theorem. Every serious catalog states its equivalence; Wieting's Table 11 uses the affine normalizer N_Aff(Γ), which is why a general low-index computation (Vladimir's, or this page's) legitimately counts more.

The second axis of design is the input representation, and each representation has a natural algorithm. The library implements all three; they validate each other.

5.1 Engine A — low-index search on coset tables (finitely presented groups; the GAP replacement)

Input: generators and relators, e.g. a b c with a^2, b^2, c^2, (ab)^2, (ca)^8, (bc)^3. An index-n subgroup H is the same thing as a transitive action of G on the n cosets G/H with a marked point — encoded by a coset table: one row per coset, one column per generator and inverse. The search:

1. Start with one coset. Find the first empty cell in the table (row-major).
2. Try every possible value: each existing coset whose matching inverse cell is free, or one new coset (if fewer than N exist). Cosets are numbered in order of first appearance, so every completed table is standardized — each literal subgroup corresponds to exactly one table, and none is produced twice.
3. After each choice, propagate deductions: trace every relator through every row; a relator path with exactly one missing edge forces that edge; a completed path that fails to close kills the branch (backtrack).
4. Every completed table with k ≤ N rows is one literal subgroup of index k: the stabilizer of coset 0. Its generators are read off by Schreier's lemma from the non-tree edges of the table.

Conjugacy classes come free: re-standardizing the same table from every base point gives the tables of all conjugates, and the lexicographically smallest is a canonical class label. The Wieting-style merge then acts on class labels by the detected symmetries of the presentation (signed generator permutations preserving the relators — for the labeled p3 presentation ⟨x,y,z | x³, y³, z³, xyz⟩ the full S₃ permuting the centers is found automatically). This is the sound, computable core of the affine-normalizer equivalence; see §8 for what it does not cover.

5.2 Engine B — closure search (finite groups, exact and total)

Input: permutation generators, e.g. (1 2 3 4), (1 3). Build the whole group and its multiplication table, then grow subgroups breadth-first: start from {1}; for each known subgroup H and one representative g per coset outside it, form ⟨H, g⟩; keep the new ones; repeat. Every subgroup arises this way (add its generators one at a time), so the enumeration is complete — this is the textbook-exact answer, feasible up to a few thousand elements. Conjugacy classes and the subgroup lattice diagram are computed directly on element sets.

5.3 Engine C — the Senechal–Wieting congruence method (crystallographic groups)

The historical algorithm, and the structural reason wallpaper groups are easy. A wallpaper group is an extension 1 → L → Γ → P → 1 of a finite point group P by the translation lattice L ≅ ℤ². Every finite-index subgroup H is assembled from three finite choices —

— where c(q,r) is the integral 2-cocycle recording glide/screw translations of the chosen section (for symmorphic groups it vanishes; for pg it is what makes a glide square to a full translation). The index factors as [Γ:H] = [P:Q]·[L:M] — the crystallographers' Hermann decomposition into a translationengleiche and a klassengleiche step. Sublattices are enumerated in Hermite normal form (σ₁(m) of them at index m), invariance is the integrality of B⁻¹qB, and the congruences are solved by propagating offsets along generators of Q. This is the method Senechal published in 1980 and Wieting ran to 60 colors; here it runs in the browser for all 17 wallpaper groups.

The suite below runs in your browser and checks the engines against independent ground truth: divisor sums for ℤ², published subgroup counts of finite groups, the research dossier's hand-checked wallpaper values, GAP's actual output for two triangle groups (computed by V. Bulatov's symmhub pipeline: *283 and the (2,3,7) Hurwitz group), and cross-agreement of engines A and C on wallpaper groups.

• Performance envelope (engine A), measured. All 17 wallpaper presentations and the triangle groups enumerate to index 24 — Vladimir's production GAP setting — in under 0.1 s in Node/Chrome; the 2-second interactive wall sits around index 50–65, and 30 s around index 70–100 depending on the group. So for the actual symmhub use case this engine already matches LowIndexSubgroupsFpGroup. The remaining headroom (GAP goes further on subgroup-rich groups) is engineering, not mathematics: the missing piece is Holt's partial-table canonicity test, which prunes conjugate branches during the search rather than after. Engine B is exact to group order ≈ 120 instantly, ≈ 240 in seconds; engine C is interactive to index ≈ 48 for every wallpaper group.
• The merge is presentation-level. Engine A merges conjugacy classes under signed generator permutations that preserve the relator multiset. This finds exactly the "relabel the centers" symmetries when the presentation exposes them (one generator per center) — use the labeled presets to see it. It is sound (only true automorphisms are used) but not complete: automorphisms that require general word substitutions, and the continuous part of the affine normalizer for the low-symmetry groups (p1, p2, pm, pg, cm), are not searched. Reproducing every number of Wieting's Table 11 therefore needs engine C plus per-group affine-normalizer data (GAP's Cryst package ships exactly that as AffineInequivalentSubgroups).
• Vladimir's 3*3 presentation is fine. His GAP file marks the p31m presentation # WRONG, but adjudicating it against an independent integer-matrix model of p31m (engine C) shows exact agreement of literal and conjugacy-class counts through index 12 — and the invariants genuinely separate p31m from p3m1 (class counts differ at indices 3, 6, 9, 12: 4/6/5/9 vs 2/5/3/7), so the match is not vacuous. The # WRONG comment appears to be stale.
• Chirality is real and detectable. For the labeled p4 presentation ⟨x,y,z | x⁴, y⁴, z², xyz⟩ the detector finds the orientation-reversing automorphism x↔y⁻¹ and merges the two 4-fold-center classes — a left-handed coloring identified with its mirror image. For the labeled p6 presentation (center orders 6, 3, 2 all distinct) it was verified independently that no chirality pairing exists among classes at low index: the merge correctly does nothing there.
• Trusting the answer. Every engine validates its own output: engine A checks that relators act trivially on every completed table; engine C re-verifies every congruence solution pairwise and re-checks the index factorization. The three-way cross-agreement in §7 is the strongest guarantee this page offers.

Primary / historical

• T. W. Wieting, The Mathematical Theory of Chromatic Plane Ornaments, Marcel Dekker, 1982. Table 11 (pp. 250–254) is the color-group census; totals preserved as OEIS A307293.
• M. Senechal, “A simple characterization of the subgroups of space groups,” Acta Crystallographica A36 (1980) 845–850 — the algorithm of §5.3. doi:10.1107/S0567739480001799
• M. Senechal, “Color groups,” Discrete Applied Mathematics 1 (1979) 51–73 — colorings ↔ coset actions. doi:10.1016/0166-218X(79)90014-3
• M. Senechal, “Color symmetry,” Computers & Mathematics with Applications 16 (1988) 545–553 — attributes the 60-color computation to Wieting using her algorithm.
• J. D. Jarratt & R. L. E. Schwarzenberger, “Coloured plane groups,” Acta Cryst. A36 (1980) — the parallel census; documents Wieting's two methods and the corrected counts.
• T. W. Wieting, “Generalized Crystals” (Reed College essay, 2010) — his own (T, Λ, γ) cocycle formulation of §5.3. reed.edu
• K.-J. Köhler, “An algorithm for finding the subgroups of n-dimensional crystallographic groups,” MATCH 10 (1981) — the independent contemporary implementation at RWTH Aachen.
• B. Grünbaum & G. C. Shephard, Tilings and Patterns, Freeman 1987, ch. 8 — the visual side of colored patterns.

Algorithms

• C. C. Sims, Computation with Finitely Presented Groups, CUP 1994 — the low-index method of §5.1.
• D. F. Holt, B. Eick, E. A. O'Brien, Handbook of Computational Group Theory, ch. 5 — coset enumeration and low-index subgroups, including the in-search canonicity pruning noted in §8.
• M. Hall Jr., “Subgroups of finite index in free groups” (1949) — the counting formula used to validate engine A on free groups.
• GAP: LowIndexSubgroupsFpGroup; the Cryst package (AffineInequivalentSubgroups, color groups); CARAT; the Bilbao Crystallographic Server.

This project

• V. Bulatov, symmhub — apps/sympic/gap/: the GAP pipeline this page replaces (orbifold presentations in groups_wp.g, driver generate_subgroups.g); JSON outputs used here as ground truth.
• Research dossier senechal_wieting_subgroup_algorithm.md and the Python reference senechal_wieting_reference.py (this folder) — the §5.3 reconstruction and its history, including the search for Wieting's original program (not found; Reed College Special Collections is the remaining lead).
• Conversation transcript, 5 Aug 2026 (V. Bulatov & G. Bulatov, ocean trip) — the requirements and the counting discussion quoted in §1 and §4.