Computation — page 2

6 necklaces, concatenated into a de Bruijn sequence. The Lyndon words of length dividing 4 over 2 letters, listed in lexicographic order and written end to end; the result is the lexicographically least de Bruijn sequence of order 4.

Every necklace, in order

The graph construction needs the whole graph in memory and finds one sequence among hundreds of millions. Listing the necklaces in alphabetical order and writing them end to end needs no graph at all, and produces the smallest of them.

A 4-bit register that visits all 15 nonzero states. The first 15 states of a 4-bit linear feedback shift register with taps at 4 and 1, with the bit that leaves the register at each step; the output shows every nonzero window of 4 bits exactly once.

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.

A four-by-four array holding every two-by-two block. A binary array, cyclic in both directions, drawn with its wrapped row and column, in which each of the sixteen two-by-two blocks appears exactly once.

A page that knows where it is

A four-by-four array of bits, cyclic in both directions, in which every two-by-two block appears exactly once. Print it repeatedly across a sheet and any four marks on that sheet are an address.

A cycle showing every pair from 5 things exactly once. The complete graph on 5 points with an Eulerian circuit drawn, and the cyclic sequence of symbols it spells; every window of two consecutive symbols is a different pair.

A cycle for every pair

A cyclic sequence in which every window of two consecutive symbols is a different pair of things. For five things it exists and for four it does not, and in both cases there are exactly as many pairs as there are places to put them.

The same modulus, four multipliers, four qualities. 4 linear generators at modulus 1021, drawn as scatters of consecutive pairs and ranked by the spacing of the lines their points fall on. The spacings differ by more than a factor of two.

The test that ranks the generators

Every linear generator's output lies on a family of parallel planes. Which generator is better is decided by how far apart those planes are, and that distance is the length of the shortest whole-number vector the modulus annihilates — a quantity that can be computed exactly rather than estimated by testing.

Four outputs are enough to find the rule. A row of 12 outputs of a linear generator, with the first 4 marked as given and the rest as predicted. The multiplier and increment recovered from the given ones reproduce every later output exactly.

Four numbers and the rule is yours

A linear generator can be solved. Given a few of its outputs, the multiplier and the increment fall out of two congruences, and every future output is then known exactly — which is a failure of a completely different kind from the lattice defect, and is not detected by any test of how evenly the points are spread.

Randomness that has to be earned

A generator that resists prediction cannot be built out of a rule anybody can fit. It has to be built out of a computation believed hard to undo, and the belief is the load-bearing part — which makes cryptographic randomness a conditional statement rather than a construction.

Every pattern, exactly as often. A table over 4 window lengths of a shift register's output stream: how many bit patterns are possible, how many actually occur, and the difference between the most and least frequent, which is one in every row.

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.

The circle is used once, and its centre is the point. A circle with its centre and one diameter, a point above it, and the straightedge-only construction of the parallel to that diameter through the point.

One circle, and a straightedge

A straightedge alone cannot bisect a segment, so it cannot draw a parallel, so it can construct almost nothing. Draw one circle anywhere and mark its centre and everything a compass could ever have done becomes available — the circle is never needed again.

A compass that will not change its opening. A segment longer than twice the compass's fixed opening, with the opening stepped along it 2 times and the remaining piece bisected by two arcs of that same opening.

The compass that will not open

Fix the compass at one opening and never change it. That looks like a serious loss — a circle of a given radius through a given point is the compass's whole job — and it turns out to cost nothing at all, for reasons that are arithmetic rather than geometric.

The largest code at each length, distance 3, against four bounds. A table with one row per word length, giving the exact size of the largest code of that length at the stated minimum distance and the values of the Singleton, Hamming, Plotkin and Gilbert-Varshamov bounds.

The best a code can be

A code is a set of words chosen far apart, and every construction answers "here is one" rather than "here is the best". The best can be computed at small lengths, and putting four classical bounds beside the exact answer shows which of them is doing the work and where none of them is.

How many codewords lie within each radius, for a [7,3] code over 11 symbols. A bar for each decoding radius, its height the largest number of codewords found inside a ball of that radius around a randomly drawn received word, with the unique-decoding radius and the Johnson radius marked.

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.

A dissection that never comes apart

The plane theorem lets the pieces be picked up and put down anywhere. Require instead that they stay joined at their corners and swing, and the theorem survives — which was open for a century and is a much stronger statement about the same cuts.

The quantity a cut cannot change and a turn can. 4 polygons, each with the spikes of its translation invariant drawn round a dial: the length of the edges facing each direction, less the length of those facing the opposite way. It vanishes everywhere for 3 of them.

Slid, but never turned

The classical dissections all turn their pieces. Forbid the turn — allow the pieces to be slid and nothing else — and equal area stops being enough, for a reason that is a single number attached to each direction and that a cut cannot change.

What the chain costs on a 6-gon: 39 pieces. A regular 6-gon fanned into 4 triangles, each with the three cuts that turn it into a rectangle, beside the running count of the pieces the whole chain produces — 39 of them.

Finitely many, and nobody says how many

The theorem promises a dissection exists and the proof produces one. Running the proof on a hexagon produces thirty-nine pieces, ingenuity produces five, and there is no method for proving that five cannot be four.

Volume and one more number decide what a solid can be cut into. A table of a cube, a prism, a sixth of a cube, a regular tetrahedron, a regular octahedron and a collection of two tetrahedra with one octahedron, giving each one's volume, its Dehn invariant computed from its measured dihedral angles, and whether it can be cut into a box of equal volume.

The obstruction that was the only one

Dehn showed in 1901 that a cube cannot be cut into a regular tetrahedron of the same volume, because a number built from edges and angles disagrees. For sixty-four years nobody knew whether that number was the whole story. Sydler proved in 1965 that it is: volume and Dehn's number together decide every case.

A spherical triangle becomes a quadrilateral with two right angles. A triangle on a sphere with the arc through the midpoints of two of its sides, the perpendiculars dropped from its three corners, and the quadrilateral with right angles at its base that the same area makes when the two corner pieces are moved.

Equal area on a sphere, without a rectangle

On a sphere, two polygons of the same area can still be cut into each other, exactly as in the plane. Almost nothing in the plane proof survives the move: a sphere has no rectangles, no parallel strips and no similar triangles of different sizes. What carries the theorem instead is a quadrilateral with two right angles, built from a triangle's midline.

The zeros of x² + y² + z² over GF(5), and of x² + y² over GF(7). Grids of every point over a small prime field with the solutions of a quadratic equation filled in: the three-variable equation drawn as one slice per value of z, beside a two-variable equation with far fewer solutions.

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.

The cubic curves over GF(43) with the most and the fewest points. The solutions of two equations y squared equals x cubed plus ax plus b over the field with 43 elements, drawn as dots on a square grid: the curve with the most points and the curve with the fewest.

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.

Which polygons two instrument sets reach, up to 24. A strip of the polygons from 3 to 24 sides, each marked according to whether compass and straightedge reach it and whether a conic or a trisector does, with the degree of its cosine beneath.

Two instruments with one reach

Allow every conic to be drawn at will, or allow an angle to be cut in three. The two permissions look nothing alike and reach exactly the same numbers — because what an operation buys is a degree, and both of these buy three.

The polynomial the 11-sided polygon needs. The minimal polynomial of twice the cosine of the central angle of an 11-sided polygon, with its degree, the rational root test applied to it, and whether that degree is reachable by cubic steps.

A quintic a sliding mark reaches

The eleven-sided polygon needs a number of degree five, and five is not a product of twos and threes — so no conic and no angle trisector reaches it. A ruler with two scratches does, which places the marked ruler strictly above the conics and leaves its exact reach unknown.

A design on 7 points cannot have fewer than 7 blocks. The incidence matrix of a design on 7 points and 7 blocks beside the product of it with its own transpose, which has a constant off the diagonal and a determinant computed exactly.

More blocks than points

A schedule in which every pair meets once cannot use fewer groups than it has people. Nothing about the counting conditions says so, and the proof is not combinatorial at all — it is a determinant, computed over a field the schedules have nothing to do with.

A plane of 13 points from a list of 4 numbers. A ring of 13 points with one block of 4 of them drawn as a closed path, beside the table of the 13 blocks its shifts produce.

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.

The one line from which the nearfield plane looks Desarguesian. A grid of the 91 lines of the nearfield plane of order nine shaded by how many of 40 Desargues configurations with that line as axis failed; only the line at infinity has none, and every other line at least 20.

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.