Matpic
mathematics, in pictures
Concept

Primitive element

A member of a group whose powers run through the whole group, or of a field extension that generates all of it. Its existence turns a structure into a list of powers, so that multiplication becomes addition of exponents.

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

The non-zero elements of GF(16) as the powers of one of them. A ring of the field's non-zero elements in the order the powers of a primitive element produce them, beside a table of exponents.

Every element is a power of one of them

Pick the right element of a finite field and its powers run through every other non-zero element exactly once before returning to one. Multiplication becomes addition of exponents, and a table of q − 1 entries replaces the whole multiplication table.

computation · Finite fields The 7 7th roots of unity. 7 points spaced evenly around the unit circle, at the vertices of a regular 7-sided polygon.

The polygon an equation forces

The n solutions of z to the n equals one are the corners of a regular polygon, and nearly everything about them — that they form a group, that they sum to zero, that the equation factors into pieces with whole-number coefficients — is that picture read carefully.

algebra · Roots of unity A 4-bit register that visits all 15 nonzero states. The first 15 states of a 4-bit linear feedback shift register with taps at 4 and 1, with the bit that leaves the register at each step; the output shows every nonzero window of 4 bits exactly once.

A memory of four bits

A register holding four bits, shifting them along and adding two of them back, runs through all fifteen nonzero states before it repeats. Which two are added back is a question about a polynomial, and getting it wrong costs fourteen of the fifteen.

computation · De bruijn Multiplication by 3 modulo 11, and the sign of the shuffle. Residues in two rows joined by strings showing where multiplication sends each one, with a strip beneath comparing the sign of the shuffle to the Legendre symbol for every multiplier.

The symbol is the sign of a shuffle

Multiplying every residue modulo p by a fixed number rearranges them. That rearrangement is a permutation, permutations have a sign, and the sign is exactly the Legendre symbol — so a question about squares becomes a question about crossings.

number · Quadratic reciprocity The Gauss sum for 13, added one root at a time. Partial sums of the p-th roots of unity signed by the Legendre symbol, drawn as a walk closing on a point at distance root p from the origin.

One sum, squared two ways

Add the p-th roots of unity, each taken with a plus or a minus according to whether its index is a square. The walk that results closes on a point at distance √p from the origin — and squaring that one number, evaluated two different ways, is the reciprocity law.

number · Quadratic reciprocity The zeros of x² + y² + z² over GF(5), and of x² + y² over GF(7). Grids of every point over a small prime field with the solutions of a quadratic equation filled in: the three-variable equation drawn as one slice per value of z, beside a two-variable equation with far fewer solutions.

Solutions that come in multiples of p

Count the solutions of x² + y² + z² = 0 in the field with five elements and there are 25; with seven, there are 49. Whenever a system of equations has more unknowns than its total degree, its number of solutions is a multiple of the characteristic — which forces a solution besides zero, and the reason is a sum over the field that vanishes because its non-zero elements form one cycle.

computation · Finite fields

Named alongside it

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

Cyclic groupFinite fieldModular arithmeticComplex numbersCounting argumentCyclotomic polynomialDiscrete logarithmFermats little theoremLegendre symbolPolynomialQuadratic reciprocityQuadratic residue

All concepts