Computation — page 1

Two points, and everything one round of compass and straightedge adds. Two starting points with the line and circles they permit, and the four points where those objects cross.

What two points can build

A compass and a straightedge are not a craft. They are two operations on a set of points, applied over and over, and writing them that way turns "can this be drawn?" into a question with an answer.

The tower ℚ ⊂ ℚ(√2) ⊂ ℚ(√2, √3). A tower of field extensions with the degree of each step, beside the multiplication table of the basis.

A line meets a line by solving a linear equation and a circle by solving a quadratic one. There is no third case, so the numbers a construction reaches can only ever double in complexity — and a doubling is a thing that can be counted.

Every rational number that could be a root of x³ − 2. A table of the candidate rational roots allowed by the rational root theorem, with the polynomial's exact value at each.

The cube that will not double

Doubling a cube needs an edge in the ratio of the cube root of two. That number satisfies an equation of degree three, three does not divide any power of two, and the oldest open problem in geometry closes in a line.

Which angles with a rational cosine can be cut in three. A dial of angles marked trisectable or not, beside the cubic whose rational roots decided each one.

The angle that will not divide by three

Halving an angle costs one circle. Cutting it in three means solving a cubic, and for sixty degrees that cubic has no rational root — but plenty of angles do trisect, and which ones is a question with a countable answer.

Which regular polygons a compass and straightedge can draw, up to 100. A grid of the integers with the constructible ones filled in, each verdict computed two independent ways.

Which polygons can be drawn

Three sides yes, seven no, seventeen yes. The list of constructible regular polygons is neither everything nor almost nothing, and the pattern in it is a fact about which numbers are one less than a power of two.

The circle that will not square

The other three impossibilities are a number having the wrong degree. This one is a number having no degree at all — and that is a claim no finite search can establish, which makes it the one place in this field where the picture has to admit what it is not doing.

A code on the 3-cube, and the balls around its words. The corners of a hypercube with the chosen codewords marked and the words within one error of each shaded.

Distance is a picture

A message is a corner of a cube and an error is a step along an edge. Everything a code can do is decided by how far apart the corners it uses are — and that is a fact about a drawing.

The sixteen words of the [7,4] Hamming code. A table of sixteen seven-bit codewords with their data bits, parity bits and weights.

Sixteen spheres that fill a cube

A hundred and twenty-eight seven-bit words, sixteen of them chosen, and a ball of eight around each. Sixteen times eight is a hundred and twenty-eight exactly — so the balls tile the space with nothing left over, and the code wastes nothing at all.

The syndrome of 1011010, and the bit it names. A parity-check matrix over a received word, with the resulting syndrome matched against the table of single-error syndromes.

Finding the error without reading the message

Three parity checks on a seven-bit word produce three bits. If they are all zero nothing is wrong; otherwise they are the number of the position that broke. The message is never consulted, because the answer does not depend on it.

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.

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 arithmetic of GF(4), and of the integers mod 4. Addition and multiplication tables of a finite field, optionally beside the table of a ring of the same kind of size.

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 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.

The Fano plane, and the incidence table behind it. Seven points joined by six straight lines and one circle, beside the seven-by-seven table of which point lies on which line.

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.

A schedule on 9 points where every pair meets exactly once. Points around a circle with the triples of a Steiner system drawn between them, beside the list of triples.

A schedule where every pair meets once

Sort n people into groups of three so that every two of them share a group exactly once. Two divisions have to come out whole, that rules out most sizes — and at every size the divisions permit, a schedule exists.

Transversals of the cyclic square of order 6. A cyclic Latin square with a transversal marked if it has one, beside a count of transversals at neighbouring orders.

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.

Every word once, around a cycle

A cyclic string of eight bits holds all eight three-bit words, each exactly once — and the reason such a thing exists is that the constraint linking overlapping windows is itself the construction.

A triangle cut into three pieces that make a rectangle. A triangle sliced at half its height and again down the altitude of the small triangle, beside the rectangle the same three pieces make when each top piece is turned a half turn.

Equal area is enough, and equal volume is not

Any two polygons of the same area can be cut into each other with finitely many straight cuts. The same sentence with area replaced by volume and polygon by polyhedron is false, and what blocks it is an angle.

The midpoint of a segment, drawn with a compass and no straightedge. A segment with the arcs that step its length three times round one end to reach the point twice as far away, and the further arcs that send that point back to the midpoint, every one of them a circle.

The straightedge buys nothing

Every point a compass and a straightedge can construct together can be constructed by the compass alone. The straightedge draws lines nobody needs; the compass does the work, and the proof that it does is an inversion performed with arcs.

256 consecutive pairs from xₙ₊₁ = 137xₙ + 187 mod 256. Consecutive outputs of a linear congruential generator plotted as points of a square, falling on a small family of evenly spaced parallel lines.

The planes a recurrence cannot leave

One multiplication and one addition, taken modulo a fixed number, produce a sequence that passes for random one value at a time. Taken two or three at a time it does not, and the reason is a whole-number relation that pins every point onto one of a small family of parallel lines.

An angle of 60° cut in three with one mark. A circle with a marked point on it, a straightedge laid through that point so the segment between the extended diameter and the circle equals the radius, and the third-angle it makes.

The mark that changes what is reachable

Two thousand years of failure to trisect an angle with compass and straightedge was failure at a stated set of operations. Scratch two marks on the straightedge and Archimedes trisects any angle in four steps — because the new operation solves a cubic, and the old ones could only ever solve quadratics.

The 3 mutually orthogonal squares of order 4. Every Latin square built from the field of order 4 as a·i + j, one for each non-zero multiplier, with every pair checked orthogonal.

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 affine plane of order 3, one parallel class at a time. The n² cells of a complete set of orthogonal Latin squares of order 3, with the rows, the columns and each square's symbol classes drawn as lines of a plane.

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.

Nine thousand four hundred and eight

There are four Latin squares of order four once the first row and column are fixed, fifty-six of order five, and nine thousand four hundred and eight of order six. The exact answer is known for eleven orders and for no more — and yet a half-finished square can always be finished.

The 576 squares of order 4, sorted by whether they associate. Every Latin square of order 4, counted by whether it associates and by which group it is when it does.

Sixteen of five hundred and seventy-six

A Latin square is a multiplication table in which every equation has exactly one solution. Ask it to be associative as well and almost every square drops out — sixteen of the five hundred and seventy-six of order four survive, and they are the two groups.