Field

Computation — page 3

A fixed set of operations, and the exact question of what it can and cannot build.

The conic y = x² in the plane of order 7. A 7 by 7 grid of the affine plane over GF(7) with the points of the conic y = x² filled and its point at infinity marked: 8 points, no three collinear.

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.

Fair bits from a biased coin. 44 flips of a coin biased 0.7 towards 1, read in 22 pairs. Mixed pairs are kept and give their first bit; matched pairs are discarded. Over a long run the output is 50.2% ones, at 0.210 output bits per flip.

Fair bits from an unfair coin

Read a biased coin's flips in pairs, keep 01 as 0 and 10 as 1, and throw away the rest: the output is exactly fair, whatever the bias, and nobody needs to know the bias. The trick wastes most of the coin, the waste can be recycled almost up to the ceiling Shannon's entropy sets — and it fails quietly the moment the flips remember each other.

How far a filter spreads a generator's output. Bars for bit depths 1 to 8: the ceiling ⌊24/v⌋ outlined, the raw generator's count of evenly spread consecutive outputs (24, 3, 3, 3, 3, 3, 3, 3), and the tempered count (24, 12, 6, 6, 3, 3, 3, 3).

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 midpoint of AB: simplicity 11. A construction drawn step by step — the midpoint of AB, using ruler and compass — with each circle and line numbered in order and Lemoine's count of its operations beneath.

The price of a construction

Three theorems have shown that a compass alone, a straightedge with one circle, and a compass stuck at one opening all reach exactly the points a full set of instruments reaches. None of them said what the journey costs. Émile Lemoine priced every movement of the hand in 1888, and by his count a compass that collapses when lifted — Euclid's — pays twenty-one operations, by Euclid's own method, for what a compass that holds its opening does in four.

The cyclic square of order 6: no transversal, and one of 5 cells. A Latin square of order 6 with a partial transversal of 5 cells shaded — one cell in each row and column but one, each with a different symbol. No full transversal exists.

One cell short of a transversal

A transversal of a Latin square picks one cell in every row and every column with every symbol different. The cyclic squares of even order have none, and that was settled by a parity argument centuries old. Whether every square of odd order has one is a conjecture from 1967 that nobody has proved; whether every square comes within one cell of having one was settled only in 2023, and only for squares large enough.

Channel capacity 1 − H(p), and three codes at p = 0.1. The capacity of the binary symmetric channel plotted against its flip probability, with the rates of repetition, the Hamming code and no coding marked at one flip probability.

The rate a noisy channel allows

A channel that flips one bit in ten can still carry messages with as few errors as anyone likes — at up to 0.531 message bits per transmitted bit, and at no rate above that. The number is Shannon's capacity, 1 − H(p). Repetition reaches reliability only by sending nothing; a code chosen at random gets there at any rate below the limit; and the reason there is a limit at all is a count of how many flip patterns a block of noise can hold.

Decoding from 20 + m random combinations: the chance it works. Bars for the exact probability that 20 plus m random binary combinations of 20 message bits have full rank, with simulated frequencies as dots, for m from zero upwards.

Erasures a code can see

If a channel loses bits instead of flipping them, and says which ones it lost, its limit rises from 1 − H(p) to 1 − p — and reaching it needs nothing cleverer than a random matrix and the solution of simultaneous equations. A random code needs, on average, 1.607 symbols more than the message it carries, whatever the message's length, and that number is a constant Erdős proved irrational.

A line in every direction in the plane over GF(7), in 31 points. A square grid of the points of a small finite plane with the points of a Kakeya set filled, beside a list of the lines it contains, one for each direction.

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.

Latin squares of order 4, and the ones that are also Sudoku grids. Two 4×4 Latin squares with their 2×2 boxes outlined: one in which every box also holds 1 to 4, and the cyclic square, whose top-left box repeats a symbol. Of all 576 Latin squares of order 4, 288 pass the box test.

A Latin square with boxes

A finished Sudoku is a Latin square of order nine with one extra rule: each 3×3 box holds every digit once. At order four the extra rule keeps exactly half of the 576 Latin squares, the 288 survivors are two grids in disguise, and no puzzle can be pinned down by fewer than four clues. At order nine every one of those questions needed a computer, and the answers are 6.67 × 10²¹ grids, 5.47 billion essentially different ones, and seventeen clues.

3 orthogonal squares of order 4, read as a code. A table of 16 words of length 5 over 4 symbols, one per cell of 3 orthogonal Latin squares of order 4: row, column and the entry in each square. Any two words agree in at most one position.

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.

Eighty-one cards and twenty with no SET among them. A three-by-three arrangement of three-by-three grids covering the eighty-one points of four-dimensional space modulo three, with twenty cells marked that contain no three on a line.

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 bound falls exponentially behind the space. A log-scale plot against the dimension of the number of points of the space, the polynomial method's bound on a cap, and the known largest caps: the bound's line is less steep than the space's and pulls away from it.

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.

Hippias's quadratrix, traced by two uniform motions. A unit square with a quarter circle, several positions of a turning radius and a falling horizontal line, their crossings, and the curve through them ending on the base at 2/π.

A curve that divides any angle

Let a radius turn at a steady rate while a horizontal line falls at a steady rate, both finishing together, and mark where they cross. The curve they trace turns heights into angles, so dividing a height — which a ruler and compass can always do — divides the angle in the same ratio. The same curve meets its base at 2/π of the side, a length from which a square with the area of a circle follows. It reaches what no marked ruler or conic can, and the ancient objection to it is exact.

A rectangle of the parity table, nearly balanced. A 32 by 32 grid of +1 and −1 entries — the parity of the inner product of row and column — with a 15 by 14 rectangle of chosen rows and columns highlighted; its entries sum to 8.

Two weak sources make one fair bit

No fixed rule can turn every weakly random source into fair bits: for any rule, some source with almost full unpredictability makes it constant. Two independent sources are different. Multiply their bits in pairs, add, and keep the parity — and if the two together carry more unpredictability than the length of one, the result is nearly fair, whatever else the sources do. The reason is that the table of those parities is balanced on every large rectangle.

A 33 × 32 rectangle cut into 9 unequal squares. A squared rectangle of 9 squares with sides 18, 15, 14, 10, 9, 8, 7, 4, 1, each labelled with its size.

A rectangle made only of squares

A rectangle can be cut into finitely many squares — of any sizes, as many as wanted — exactly when its two sides are in whole-number proportion. Max Dehn proved it in 1903, and the proof that stuck, found by four Cambridge undergraduates in 1940, reads the squares as currents in an electrical circuit.

A triangulation of the square with 7 three-coloured triangles. A triangulation of the unit square into 34 triangles, vertices coloured by Monsky's rule, with the 7 triangles carrying all three colours shaded.

No odd number of equal triangles

A square can be cut into two triangles of equal area, or four, or any even number. It cannot be cut into three, or five, or any odd number — whatever shapes the triangles take. Paul Monsky's proof of 1970 has no geometry in its engine at all: it colours the points of the plane by how divisible their coordinates are by two.

A straightedge construction on a circle, and the same construction moved by a map that keeps the circle. Two copies of one straightedge construction on a circle — six points, five chords and their crossings — the second the image of the first under a projective map fixing the circle. Chords and crossings correspond exactly, but the centre (orange) is carried to (0.551, 0.000).

The centre a straightedge cannot find

Give a straightedge one circle and its centre, and it can do everything a compass can. Take the centre away and it cannot even find it again — because to a straightedge a circle has no centre. The maps that keep a circle and its straight lines are the motions of the hyperbolic plane, and in that plane the centre is a point like any other.

The spiral of Theodorus, √2 to √17, built from square corners and a unit length. 16 right triangles with legs √k and 1 arranged in a spiral around a common corner; their long sides have lengths √2 to √17, and together they turn through 351.2 degrees.

The lengths dividers cannot reach

A pair of dividers carries a length from one place to another and draws nothing. With a straightedge it finds midpoints, parallels and right angles, and it draws the regular 17-gon. It cannot draw a segment of length √(1 + √2) — and the reason is not on the page at all, but in the other root of the equation that number solves.

The plane of order 3 as a table, and the table times its transpose. The 13 × 13 incidence table of the projective plane of order 3 and its product with its transpose, which has 4 on the diagonal and 1 in every other cell.

The orders a plane cannot have

Every counting condition allows a projective plane of order six, and there is none. The proof that rules it out looks at one matrix identity — each point on seven lines, each two points on one — and turns it, by way of Lagrange's four squares, into the statement that six would have to be a sum of two squares. Run on the planes that do exist, the same argument hands back their orders as sums of two squares; run on six, it asks for something no arithmetic can supply.

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 spiral's tangent lays the circumference out straight. Spiral r = aθ to θ = 6.2832; tangent at P meets the perpendicular through O at T with OT = 6.28319 = OP × θ = 6.28319.

The spiral that measures its own circle

Let a ray turn steadily while a point moves steadily out along it, and the point draws Archimedes' spiral. Distance from the centre is then proportional to angle, so dividing a length divides an angle in any ratio. The spiral's second power is stranger: the tangent at the end of the first turn cuts off, on a line through the centre, a straight length exactly equal to the circumference of the circle through that end — a curved length laid out straight, and with it the circle squared. The catch is the tangent itself.

Trisecting 120° by bisection, step after step. Partial sums θ(1/4 + 1/16 + …) for θ = 120°: 30.000, 37.500, 39.375, 39.844, 39.961 degrees, approaching 40.000.

A third reached only in the limit

No compass-and-straightedge construction trisects every angle. But a quarter, plus a quarter of a quarter, plus a quarter of that, and so on, adds up to a third — and each of those pieces is two bisections away. So an angle can be trisected by bisecting forever, every stage exact and the shortfall shrinking to a quarter each time. The construction never ends, and that is precisely what Wantzel's proof forbids: a construction is a finite thing, and a third of a general angle is only reached in the limit.

The midpoint in the fewest moves: four with a ruler, six with the compass alone. Minimal constructions of the midpoint of AB: 4 moves with ruler and compass, 6 circles compass-only; 55 and 45611 configurations searched.

The fewest moves to draw it

Every construction with ruler and compass is a sequence of moves — draw this line, draw that circle — and it is natural to ask for the shortest. Nobody can answer that by cleverness alone, but a machine can answer it by trying everything: the midpoint of a segment takes four moves and no fewer, the square on it five, a third of it five. Take the ruler away and the compass pays for it: six circles for the midpoint, seven for the square.

All essays