Matpic
mathematics, in pictures
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 5 essays across 5 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 Every residue joined to 2 times itself, on a dial of 199. A circle with 199 equally spaced points and a chord from each point k to the point 2k mod 199, with the 1-cusped curve the chords envelope drawn dashed.

Multiplying every number on the dial at once

Join every residue on a dial to twice itself and the chords draw a heart-shaped curve with one cusp; join each to three times itself and the curve has two. The picture is the whole multiplication map at once, and it holds three facts: the map splits the dial into cycles whose lengths are orders, those cycles on a dial of 2ⁿ − 1 are the binary necklaces of length n, and the curve is the caustic light draws inside a cup.

discrete · Modular arithmetic How many windows of each period, on two maps and as a count of necklaces. period 1: 1 (logistic), 1 (sine), 1 (necklaces), 1 (polynomials); period 2: 1 (logistic), 1 (sine), 1 (necklaces), 1 (polynomials); period 3: 1 (logistic), 1 (sine), 1 (necklaces), 1 (polynomials); period 4: 2 (logistic), 2 (sine), 2 (necklaces), 2 (polynomials); period 5: 3 (logistic), 3 (sine), 3 (necklaces), 3 (polynomials); period 6: 5 (logistic), 5 (sine), 5 (necklaces), 5 (polynomials); period 7: 9 (logistic), 9 (sine), 9 (necklaces), 9 (polynomials); period 8: 16 (logistic), 16 (sine), 16 (necklaces), 16 (polynomials); period 9: 28 (logistic), 28 (sine), 28 (necklaces), 28 (polynomials); period 10: — (logistic), — (sine), 51 (necklaces), 51 (polynomials); period 11: — (logistic), — (sine), 93 (necklaces), 93 (polynomials); period 12: — (logistic), — (sine), 170 (necklaces), 170 (polynomials); period 13: — (logistic), — (sine), 315 (necklaces), — (polynomials); period 14: — (logistic), — (sine), 585 (necklaces), — (polynomials).

Windows counted like necklaces

The logistic map has one window of period three, two of period four, three of period five, five of period six, nine of period seven — and the sine map, which shares no algebra with it, has exactly the same numbers, in exactly the same order along the parameter. The counts are 1, 1, 1, 2, 3, 5, 9, 16, 28, 51, and they are the number of ways to thread a necklace of beads in two colours.

dynamics · Period-doubling The necklaces of 7 beads with 3 black. C(7, 3) = 35 arrangements in 5 rotation classes of sizes 7, 7, 7, 7, 7.

The row that proves a prime

Fermat's little theorem can be fooled: 561 passes it for every base and is not prime. Thread necklaces with a fixed number of black beads instead of any colours at all, and the count becomes a statement about a whole row of Pascal's triangle — every middle entry of row n is a multiple of n exactly when n is prime — which no composite can fake. Written as polynomials it is (x + a)ⁿ = xⁿ + a, and cut down to size it is the first proof that primes can be recognised in polynomial time.

number · Fermats little theorem

Named alongside it

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

Counting argumentModular arithmeticOrbitAlternating groupBifurcationBinomial coefficientCausticComplexityCyclic groupDe bruijn sequenceDihedral groupDoubling map

All concepts