Concept

Necklace

An arrangement of coloured beads in a ring, counted as one object when arrangements that differ only by a rotation are the same. Counting necklaces is the standard application of Burnside's lemma, and the count of prime length gives a proof of Fermat's little theorem.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

6 necklaces, concatenated into a de Bruijn sequence. The Lyndon words of length dividing 4 over 2 letters, listed in lexicographic order and written end to end; the result is the lexicographically least de Bruijn sequence of order 4.

Every necklace, in order

The graph construction needs the whole graph in memory and finds one sequence among hundreds of millions. Listing the necklaces in alphabetical order and writing them end to end needs no graph at all, and produces the smallest of them.

computation · De bruijn

36 3-tuples with product e, and the 3 that no turn moves. Every ordered choice of 3 elements of the 6 symmetries of a 3-gon whose product is the identity, in cards grouped by cyclic turning. 3 cards hold a single tuple repeating one element; the other 11 hold 3 each.

Necklaces made of symmetries

Lagrange's theorem says a subgroup's size divides the group's, and the converse is false. One piece of the converse is true: every prime that divides the size is the order of some element. The proof threads the group's own elements onto a necklace whose product is nothing, turns it, and counts — the argument that proved Fermat's little theorem with beads, with the beads replaced by motions.

algebra · Symmetry groups

Named alongside it

The objects these essays reach for when they reach for this one.

Counting argument Alternating group Cyclic group De bruijn sequence Dihedral group Equivalence class Eulerian path Greedy algorithm Group action Lagrange theorem Lexicographic order Lyndon word

All concepts