The arithmetic of GF(4)
finite-field is one function. Everything below came out of it during this
build, at parameters taken from the essays rather than invented for this page — so a figure
here is the same figure a reader meets in an essay, and if the generator changes, this page
changes with it.
With nothing chosen
The non-zero elements of GF(16) as the powers of one of them
A Kloosterman sum, drawn one term at a time
No Kloosterman sum crosses 2√p
Every Kloosterman sum at one prime, on a semicircle
The moments of Kloosterman sums are Catalan numbers
What it checks while it draws
Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.
- y² = x³ + 0x + 1 over GF(43) has a count inside p + 1 ± 2√p ×1806
- a curve over GF(101) has exactly 82 points ×41
- the 1 × 1 kernel has the dimension of gcd(p(x), p(x + 1)) ×40
- in GF(7) the sum of the 0th powers is 0 ×33
- every count the bound allows over GF(5) occurs ×16
- every cubic over GF(5) is inside the bound ×16
- the 9 zeros of a sum of 3 squares over GF(3) are divisible by p to at least the promised power ×12
- over GF(7) no cubic misses p by more than 2√p ×11
- there is a field with 4 elements only if 4 is a prime power ×7
- in GF(7) the sum of the 6th powers is −1 ×5
- A is a set of residues modulo 13 ×3
- B is a set of residues modulo 13 ×3
- the largest cap in dimension 1 ×3
- the monomial count at n = 4 ×3
- the prime is between 7 and 61 ×3
- the size of the field is a whole number between 2 and 9 ×3
- 2 zeros and 2 ones contain no 3 with a sum divisible by 3 ×2
- boards up to between 10 and 60 on a side ×2
- every 5 residues mod 3 contain 3 with a sum divisible by 3 ×2
- primes to 500 or 1,000 ×2
- the largest prime is a whole number between 13 and 97 ×2
- 1 − f² is 1 at a zero of f and 0 elsewhere ×1
- A and B are read only by the sumset and cdgrid views ×1
- a board is solvable exactly when every quiet pattern covers an even number of its lights ×1
- a conic y² = x² + b misses p by exactly one ×1
- a cycle can be lit exactly when its length is a multiple of four ×1
- a graph on 21 vertices is never invertible ×1
- a path can be lit unless its length leaves remainder 1 on division by 4 ×1
- a prime from 101 to 20,011 ×1
- a progression's own operation gives exactly 2k − 1 ×1
- a quiet pattern changes nothing ×1
- a ring of composite size has a pair of non-zero elements multiplying to zero ×1
- adding a vertex changes the dimension of the kernel by exactly one, up or down ×1
- addition and multiplication are commutative ×1
- an irreducible polynomial of the right degree was found ×1
- an m × n board and an n × m board have the same kernel ×1
- and every one of them can be lit ×1
- and it is exactly the composite ones that leave an element without a reciprocal ×1
- and no curve y² = x⁵ + ax + b by more than 4√p ×1
- and so is the mean fourth power, an eighth ×1
- and stays below the limit ×1
- and that variable's power sums to 0 over GF(3) ×1
- and the fewest is the smallest ×1
- and the parabola construction is the smallest there is ×1
- between 3 and 8 variables ×1
- chasing leaves only the bottom row lit ×1
- chasing the lights agrees with full elimination ×1
- dim is read only by the dvir view and the cap views that take a dimension ×1
- each quiet pattern of presses changes nothing ×1
- each walk ends within 2√p of zero ×1
- every constructed array appears in the search ×1
- every constructed array is a Costas array ×1
- every graph has an even number of odd-degree vertices ×1
- every group without the false share still finds the secret ×1
- every K(a, 1; p) is within 2√p ×1
- every light sees an even number of the witness set ×1
- every monomial has a variable whose power is not a positive multiple of p − 1 ×1
- every non-zero element has a reciprocal ×1
- every other point is the third point of some pair of the cap ×1
- every point of every chosen line is in the set ×1
- every quiet pattern presses an even number of lights ×1
- every random graph has an all-on press pattern ×1
- every solution turns the board off ×1
- every window of ten columns of the strip is a Costas array ×1
- failures are exactly the boards with equal powers ×1
- for every graph to seven vertices the kernel's law is exactly the chain's ×1
- for sampled graphs the kernel's law matches the chain's within sampling error ×1
- for the exact sizes the gap to the prediction shrinks with every vertex ×1
- from order nine the search grows by a factor between four and five and a half per order ×1
- from order seven on, the constructions account for under one array in twenty ×1
- given a kernel of dimension k, about one graph in 2ᵏ can be lit ×1
- Golomb's arrays from the field of thirteen are Costas arrays ×1
- graphs on two vertices that can be lit ×1
- K(1, 1; p) is within 2√p ×1
- mod is read only by the cdmin view ×1
- modulo a composite number the bound fails somewhere ×1
- modulo a prime the smallest sumset is exactly min(p, a + b − 1) ×1
- multiplication distributes over addition ×1
- multiplication is associative ×1
- no Kakeya set beats the counting bound ×1
- no Kloosterman sum for any prime up to the bound exceeds 2√p ×1
- no line holds three points of the cap ×1
- no random cap beats the largest possible ×1
- no row of the difference triangle repeats a value ×1
- no set is small under both ×1
- no two non-zero elements multiply to zero ×1
- no two points of the cap have their third point in it ×1
- odd primes up to 11 ×1
- on six vertices 2^10 = 1,024 labelled graphs have every degree odd ×1
- on six vertices every graph with all degrees odd is litable ×1
- one to three prime-power fields from 3 to 16 ×1
- over a cap, x + y + z = 0 only on the diagonal ×1
- over a set with a line, it happens off the diagonal too ×1
- q is an odd prime from 3 to 13 ×1
- q is read only by the tables, the log view and the kakeya view ×1
- random graphs on an even number of vertices can be lit more often than on an odd number ×1
- so the number of zeros is 0 mod 3 ×1
- so, since (0, 0, 0) is one, there is another ×1
- some one-way network cannot be turned all on ×1
- some part of every split is at most two thirds ×1
- some row is divisible by exactly the higher power Ax and Katz promise, and no more ×1
- the 3 × 3 press matrix is invertible over F₂ ×1
- the 5 × 5 board's press matrix has a kernel of dimension two ×1
- the adjacency matrix of a graph has even rank over the two-element field ×1
- the board is solvable exactly when the two-power rule says ×1
- the board passes every parity check before it is solved ×1
- the cap drawn is a largest one ×1
- the cap has twenty points ×1
- the cap's share of the space falls with every dimension ×1
- the constant is 2.7551 ×1
- the dimension is 2, 3 or 4 ×1
- the drawn points and the count agree ×1
- the drawn presses turn every light on ×1
- the expansion is drawn over GF(3), where it fits on a page ×1
- the exponent of a product is the sum of the exponents ×1
- the field is closed ×1
- the four-by-four board can be lit and the five-by-five cannot ×1
- the full sum is real and within 2√p ×1
- the largest cap blocks every point outside it ×1
- the largest cap in the plane of nine points has four ×1
- the largest cap in the space of twenty-seven points has nine ×1
- the largest power summed is a whole number between 8 and 20 ×1
- the lower bound never exceeds what a construction achieves ×1
- the m × n kernel has the dimension of gcd(pₘ(x), pₙ(x + 1)) ×1
- the mean square of the normalised error is the semicircle's, a quarter ×1
- the modulus is 5, 7, 8, 9, 11 or 12 ×1
- the modulus is 7, 11 or 13 ×1
- the modulus is 7, 11, 12, 13 or 17 ×1
- the monomials at or below two thirds of the top degree are a minority ×1
- the monomials of every degree number 3ⁿ ×1
- the most points any curve has is the largest whole number the bound allows ×1
- the number being factorised is a whole number between 1 and 1000000 ×1
- the number of primitive elements is φ(q−1) ×1
- the number of random caps is a whole number between 200 and 5000 ×1
- the option is one this view reads ×1
- the plane of nine points has twelve lines ×1
- the possible secrets all share a parity ×1
- the powers of a primitive element close back onto one ×1
- the press pattern lights every light ×1
- the prime is 1,009, 4,001 or 10,007 ×1
- the prime is 101 or 1009 ×1
- the rate climbs with n ×1
- the sampled shares agree with Σ P(k)/2ᵏ ×1
- the search finds the published count of Costas arrays ×1
- the set has q(q + 1)/2 + (q − 1)/2 points ×1
- the set holds a line in each of the q + 1 directions ×1
- the size of the ring drawn beside it is a whole number between 0 and 12 ×1
- the sum of K(a, 1; p)² over a is exactly p² − p − 1 ×1
- the sum of K(a, 1; p)⁴ over a is exactly 2p³ − 3p² − 3p − 1 ×1
- the sumset is at least as large as Cauchy and Davenport promise ×1
- the theorem is checked for n = 3 and n = 5 ×1
- the three-variable form is drawn over GF(3), GF(5) or GF(7) ×1
- the tuples are all counted ×1
- the two limiting shares add up to one ×1
- the two-variable form is drawn over a prime from 3 to 11 ×1
- the view is one the family draws ×1
- the walk ends at the count less p + 1 ×1
- the zeros of x² + y² + z² over GF(5) number a multiple of 5 ×1
- Welch's array from the prime 11 and the primitive root 2 is a Costas array ×1
- with self-toggling every board can be lit (Sutner) ×1
- with α = β the array is symmetric about its diagonal — Lempel's case ×1
- x² + y² over GF(7) has only the zero at the origin, since −1 is not a square ×1
Where it is called
Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.
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.
ComputationA 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.
ComputationA 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.
ComputationA 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.
ComputationDots 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.
ComputationEvery 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.
ComputationEvery 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.
ComputationGive 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.
ComputationHalf 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.
ComputationNo 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.
ComputationSeven 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.
ComputationSolutions 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.
ComputationThe 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.
ComputationThe 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.
ComputationThe 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.
ComputationTwenty 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.
ComputationA 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.
ComputationTwo 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.
ComputationWhen 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.