Generator

A degree-2 polynomial over GF(11), and the 7 values sent

A generator in the computation library, called 14 times across 4 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

poly-code 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

A degree-2 polynomial over GF(11), and the 7 values sent. A grid of the finite field with the polynomial's value at each point marked, and the transmitted symbols picked out.

4 symbols lost out of 7, and the message recovered

The weight of every codeword of a [6, 2] polynomial code

How many codewords lie within each radius, for a [7,3] code over 11 symbols

A received word 3 from one codeword and 3 from another

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.

the symbol lost at position 1 came back the same ×7
the number of symbols transmitted is a whole number between 3 and 12 ×4
the alphabet is a prime between 5 and 17 ×3
the number of message symbols is a whole number between 2 and 4 ×2
and inside the Johnson radius the list stays short ×1
and the count climbs steeply once the radius passes the Johnson bound ×1
and they differ in that many places ×1
and this far from the second ×1
any k of the n symbols recover the message exactly ×1
at least k symbols survive, or nothing can be recovered and the figure would be a lie ×1
at the full length every codeword is inside the ball ×1
every choice of surviving symbols was tried ×1
every lost position is one of the positions sent ×1
every non-zero remainder has a reciprocal mod a prime ×1
more symbols are sent than the message has ×1
no position is lost twice ×1
no received word has two codewords within half the minimum distance ×1
only the zero message gives the zero codeword ×1
so at least two codewords are within that radius ×1
the code has two words differing in all but one place ×1
the code is shorter than the field and longer than the message ×1
the code meets the Singleton bound exactly ×1
the field is a prime between 3 and 31 ×1
the lightest non-zero codeword weighs n − k + 1 ×1
the message is k symbols of the alphabet ×1
the number of received words examined is a whole number between 40 and 2000 ×1
the received word sits this far from the first codeword ×1
the survivors recover the message ×1
the view is one of erase, distance, list, pair ×1
there are at most as many evaluation points as field elements ×1
which is further than unique decoding reaches ×1
with one symbol too few, exactly p messages fit the survivors ×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.

Computation

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.

Computation

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

Past half the distance

A code of minimum distance five corrects two errors, and every account stops there. Two is the largest number for which the answer is unique — and a decoder that returns a short list instead of one answer reaches considerably further, which can be measured by counting the codewords in a ball.

Computation

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.

The whole library · What the figures prove