Finite field
Named by 39 essays across 5 fields — each of them below, with the objects they name alongside it.
A polynomial through the gaps
Write the message as the coefficients of a polynomial and send its values instead. Any k of them determine the polynomial, so it does not matter which ones are lost — and it does not matter how many, as long as k survive.
The field with four elements
The integers modulo four are not a field: two times two is zero and two has no reciprocal. There is nevertheless a field with four elements, and building it means giving up on counting as the way to make arithmetic finite.
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.
Seven points, seven lines
A geometry with seven points, in which every two points lie on exactly one line and every two lines meet in exactly one point. There are no parallels, the whole thing is built out of the two-element field, and one of its lines has to be drawn as a circle.
The thirty-six officers
Six regiments send six officers each, one of every rank. Arrange all thirty-six in a square so that each row and each column holds every rank once and every regiment once. Euler could not, guessed why, and was wrong about the reason.
A field's worth of squares
Two orthogonal squares of order five are easy to stumble on. Four of them, every pair orthogonal, is not a stumble — it is one line of arithmetic over a field, and the field supplies as many as the order allows.
The plane hiding in the squares
A complete family of orthogonal squares is not a collection of squares that happen to agree nowhere. It is a geometry — a plane with n² points in which every two points lie on exactly one line — and reading it that way is how the impossible orders were found.
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.
Nineteen thousand bits of state
The generator most simulations actually use is not clever. It is a linear recurrence over the two-element field with an enormous state, and its virtues are a proved period, a proved equidistribution and speed — none of which is unpredictability, which it does not have and does not claim.
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.
Give or take twice the square root
A cubic curve over the integers mod 43 should have about 44 points — one for each value of x, on average, and one at infinity. No curve misses by more than 13, the largest whole number below 2√43, and every count from 31 to 57 belongs to some curve. The first fact is Hasse's theorem, the second Deuring's, and the way the counts spread between the limits is a semicircle.
A plane in a list of numbers
A projective plane of order three has thirteen points and thirteen lines and fifty-two incidences. All of it is in the four numbers 0, 1, 3, 9 — because their pairwise differences hit every non-zero residue modulo thirteen exactly once, and the plane is that list's thirteen shifts.
A plane no field built
Every finite field builds a projective plane, and for a long time every known plane was built that way. The plane over Dickson's nearfield of order nine has ninety-one points, ninety-one lines and every incidence right — and Desargues' theorem fails in it on most configurations tried, except for one line, from which it never fails at all.
The curve that no three points in line define
In a finite plane, take as many points as possible with no three on a line. In odd order the largest such sets have one more point than the order — and every one of them, searched exhaustively in the small planes and proved by Segre for all odd orders, is a conic. In even order every tangent meets at one point, which can be added, and the curves stop being forced.
A filter that changes only the spread
The generator most simulations use passes every output through a last scrambling step before anyone sees it. The step is reversible, it changes nothing about the period, and it cannot make the generator any less predictable. What it changes is which patterns of consecutive outputs can occur at all — on a small twisted generator, from half of them to every one.
The densest graph without a square
Forbid four points joined in a cycle and a graph can keep only about ½n^(3/2) of its edges — far fewer than the quarter of all pairs a triangle-free graph keeps. Counting pairs of neighbours proves the ceiling in two lines. What reaches it is not a random graph but a finite geometry: the points of a projective plane, joined when they are orthogonal.
No set with a line in every direction is small
In the plane over the integers modulo 7 there are 49 points and lines in 8 directions. A set holding a whole line in every direction needs 31 of the points — more than half — and in any dimension such a set fills a fixed share of the space. In the real plane the same sets can have area zero. Over a finite field one polynomial of low degree shows they cannot be small.
A sum of two sets modulo a prime cannot be small
Add every element of one set of residues to every element of another. Over the whole numbers the sums always number at least |A| + |B| − 1. Modulo a prime the sums can wrap round and collide, and still they never number fewer — the theorem Cauchy proved in 1813 and Davenport again in 1935. Modulo 12 they can. A polynomial of low degree explains the difference in a paragraph.
Orthogonal squares are a code
Write down each cell of a set of orthogonal Latin squares as a word — its row, its column, and its entry in each square — and no two words agree in more than one place. That is not a pleasant accident of the squares. It is exactly what being Latin and being orthogonal say, it makes the list an error-correcting code as good as any code of its size can be, and the squares a field builds turn out to be a Reed–Solomon code, the one on every compact disc.
Twenty cards with no set among them
The card game SET is a four-dimensional space over the integers mod 3, and a set is a line in it. Twenty cards can avoid every line and twenty-one cannot — a fact that took a proof in 1970 — while laying cards down at random and stopping when nothing more fits reaches twenty about once in two thousand tries.
The polynomial that bounds the caps
For forty years the best bound on a set of SET cards with no set among them shrank only like one over the dimension. In 2016 a two-page argument made it shrink exponentially, and the whole proof is a count of monomials: a table that is diagonal on a cap, one polynomial that describes it, and the fact that three parts of a degree cannot all be large.
How a polynomial breaks modulo the primes
Reduce x³ − 2 modulo a prime and it factors: into three linear pieces for some primes, one linear and one quadratic for others, not at all for the rest. Over the primes up to twenty thousand those three patterns occur a sixth, a half and a third of the time — exactly the shares of the identity, the flips and the rotations in the symmetry group of a triangle, the group that permutes the three cube roots of 2. A polynomial's factorisations modulo primes are a census of its Galois group.
Every power of x that draws a hyperoval
In a plane of order 2^h, the graph of x^k plus two points at infinity is sometimes a hyperoval — as many points as a plane allows with no three in line. Searching every exponent in every plane from order 4 to 4096 finds hundreds that work, and once six symmetries of the problem are applied they fall into exactly the families already known: the conic, the translation curves, Segre's x⁶ and Glynn's two. Whether that list is complete in every order is open.
The longest code that survives every erasure
A Reed–Solomon code of k symbols can lose any n − k of its n and still be read. Over an alphabet of q symbols it can be at most q + 1 long — and it is conjectured that no code with the same perfect tolerance can ever be longer, apart from one family of exceptions in even characteristic. A search through every possible code for small alphabets confirms it cell by cell, a proof exists when q is prime, and for every other q the question is open.
The boards on which every light goes out
In Lights Out, pressing a light toggles it and its neighbours, and the goal is to turn every light off. Over the field with two elements the puzzle is a system of linear equations, and whether every pattern can be cleared depends only on whether one matrix is invertible. On a 3 × 3 board it is; on 5 × 5 a quarter of patterns can be cleared; on 39 × 39 one in four billion. Which sizes fail is decided by a common factor of two polynomials.
Four lists find a collision sooner
Two lists of random 24-bit strings need about four thousand entries each before some string appears in both — the birthday bound. Ask instead for one string from each of four lists whose exclusive-or is zero, and lists of a few hundred suffice, because merging the lists in pairs manufactures the near-misses a direct search would have to find by luck. David Wagner's algorithm turns the square root into a cube root, and more lists into smaller roots.
Every light on, from every light off
In Lights Out, pressing a light toggles it and its neighbours. On a five-by-five board only one pattern in four can be reached from all off — and yet all on is always one of them. The same is true on every board and on every network of lights whatever, provided the influence runs both ways. The proof is a single observation about symmetric matrices over a field with two elements, and it fails, as a three-arrow example shows, the moment influence runs one way.
A grid of bits whose rank stops at the state
Fill a square grid with a generator's output bits and compute its rank over the field of two elements. Random bits give full rank or one short, in fixed proportions. A generator built from shifts and exclusive-ors gives full rank up to its number of state bits and then never one more — 32 for a 32-bit xorshift, 128 for the lowest bit of xorshift128+ — however large the grid. The test that catches it is decided by a line of linear algebra.
When a press skips its own light
In Lights Out every board can be turned from all off to all on, because each press toggles its own light. Change the rule so a press toggles only the neighbours and the guarantee is gone: 310 of the 3,600 boards up to sixty by sixty cannot be lit. A single comparison of powers of two predicts every one of them, and on general graphs the answer depends on whether the number of vertices is odd or even, for a reason that is one line of algebra.
Half the chance for every silent set
In the lights game where a press toggles only the neighbours, a random network can be lit about 56 times in a hundred when it has an even number of vertices and 44 when odd. The numbers are 0.560562 and 0.439438, they add to one, and they come from a chain: each new vertex raises or lowers the dimension of the silent sets by one, and each dimension halves the chance.
Three hundred thousand outputs of nearly nothing
Start the Mersenne twister from a state with a single 1 among its 19,937 bits and it puts out zeros, then sparse ones, and only after about 340,000 outputs anything that looks random. Every linear generator has such a zeroland around the all-zero state; xorshift128 crosses it in 37 outputs, WELL512 in 44, and the twister's three-word twist makes it the slowest of all by four orders of magnitude.
Dots that never repeat a step
Place n dots on an n-by-n grid, one in each row and column, so that no two pairs of dots are joined by the same step. These Costas arrays were invented for sonar, and finite fields build them: a primitive root modulo a prime gives one family, a pair of primitive elements in any finite field another. Yet the constructions account for almost none of the arrays that exist — 92 of the 2,160 of order ten — and for orders 32 and 33 nobody has found a single one.
The fewest points that meet every line
In a finite plane any line meets every other line, so a single line is a set of points that every line passes through. Ask for such a set that contains no whole line and the answer is surprisingly expensive: in the plane of order 7, which has 57 points, it takes 12, and an exhaustive search over seventy-one million branches shows that 11 will not do. Two theorems predict the number — a square-root bound met by a copy of a smaller plane, and a bound of three halves for prime orders met by three half-lines.
Two fields that every prime confuses
Reduce x⁸ − 3 and x⁸ − 48 modulo any prime other than 2 and 3 and factor them: the two lists of factor degrees are the same, at all 9,590 such primes below 100,000. The fields the two equations define are still different. The reason is a pair of ways for one group to permute eight roots, with the same cycle lengths element by element and different fixed points — the same coincidence, in degree seven, as the points and lines of the Fano plane.
A sum that never leaves its circle
Add up e^(2πi(x + x̄)/p) over the nonzero x modulo a prime, where x̄ is the inverse of x. A thousand unit steps could go a thousand units; Kloosterman's sum never goes beyond 2√p, and at a fixed prime its values over every choice of coefficient fall on a semicircle whose moments are the Catalan numbers. Follow one sum through the primes instead and the same semicircle appears — and nobody can prove it.
Differences round a ring
Write four numbers at the corners of a square and put on each side the difference of its two corners. Repeat with the new square. Whatever the four whole numbers are, the process reaches nought within a few steps. Write five numbers and it almost never does. Rings whose size is a power of two always finish, and every other ring settles into a cycle whose length depends on how a polynomial factors over two elements: 7 at seven, 341 at eleven, 31 at thirty-one.
Two shares know nothing
Hide a number as the constant term of a quadratic modulo a prime and give eight people one value each. Any three can recover it. Any two know exactly nothing: of the 2,197 quadratics modulo 13, those matching two shares split into exactly one for each possible secret. Over the whole numbers the same two shares already give away the secret's parity.
Parallel planes take a vote
Draw a four-dimensional space with two values to a coordinate as a 4 × 4 grid, and mark its hyperplanes: thirty-two patterns any two of which differ on eight of sixteen squares. A polynomial's top coefficient can be read off any plane, and parallel planes do not overlap, so an error spoils only one vote. One of them flew to Mars, and in 2016 it turned out to reach Shannon's limit.
The period the golden ratio sets
The Fibonacci numbers, taken modulo any whole number, eventually repeat — the last digits every sixty terms. At a prime the period is not arbitrary: it divides p − 1 when the prime ends in 1 or 9, and 2(p + 1) when it ends in 3 or 7. The reason is where the golden ratio lives. Modulo the first kind of prime it is an ordinary remainder; modulo the second it has to be adjoined, as √5 is adjoined to the rationals, and in that larger field the p-th power swaps φ with its conjugate.
Named alongside it
The objects these essays reach for when they reach for this one.
Counting argumentExhaustive searchProjective planeModular arithmeticPolynomialIncidencePseudorandomnessRankError-correcting codeParityIrreducible polynomialKernel