Computation — page 4

The longest code that survives every erasure

A Reed–Solomon code of k symbols can lose any n − k of its n and still be read. Over an alphabet of q symbols it can be at most q + 1 long — and it is conjectured that no code with the same perfect tolerance can ever be longer, apart from one family of exceptions in even characteristic. A search through every possible code for small alphabets confirms it cell by cell, a proof exists when q is prime, and for every other q the question is open.

Every ordering once, around a cycle

No cycle can show every ordering of three symbols as a window of three: a window holding each symbol once forces the next symbol to repeat the one just dropped, so the sequence has period three and shows three orderings of six. Two repairs work. Write each ordering by its first two entries and the transitions form a balanced graph, so Euler's theorem hands over the cycle at once. Or add a fourth symbol and ask only that each window keep a different relative order — which works too, but no graph explains why.

How nearly equal an odd number of triangles can be

A square cannot be cut into an odd number of triangles of equal area. It can be cut into five triangles whose areas differ by about two hundredths, seven that differ by three thousandths, nine by a ten-thousandth and a half — the spread falling by a factor of seven or more with every two triangles added, closing on equality and never reaching it. A search for the closest finds that the best five it can make have the golden ratio in their areas.

A mate is rare until order ten

Euler asked whether a Latin square can have an orthogonal mate, and for every order but two and six the answer is yes for some square. For a square chosen at random the answer is different. Exactly 6 of the 56 reduced squares of order five have a mate and none of order six does; of squares drawn at random, about one in a hundred of order seven has one, one in three hundred of order eight, one in seventy of order nine — and three in five of order ten.

A rotation that hides the lattice

A congruential generator modulo a power of two has a lowest bit that alternates and pairs of outputs that lie on a few lines. Keep the generator exactly as it is, and show only eight bits of each state, rotated by an amount the state's own top bits choose: every output bit now runs the full cycle, the pairs fill the square as a random sequence would, and triples pass a test the state's own bits fail by a factor of six. Nothing about the state has changed, and four outputs still give it away.

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

Ten digits need a symmetry that does not commute

A check digit should catch one wrong digit and two neighbours swapped. Over eleven symbols a weighted sum does both; over the ten decimal digits no weighted sum can, no scheme of any shape built on adding modulo ten can, and the reason is the same as the reason Euler's thirty-six officers cannot be paraded. What works is the ten symmetries of a pentagon, which do not commute.

Square it and keep the middle

John von Neumann's first generator of random numbers squared a number and kept its middle digits. Followed from every four-digit seed, it never lasts more than 111 steps before a value repeats — a third of what the birthday problem allows a truly random rule — and one seed in five ends at zero for ever. A counter added before each squaring cures the collapse.

The centre a compass finds in six circles

A circle is drawn and its centre was never marked. A straightedge alone can never find it again. A compass alone can, from two points on the circle, in six circles — and a search through every construction of five circles or fewer shows that six is the least. The reason six works is an inversion that turns the circle into a straight line; the price of discarding the straightedge is exactly one move.

The arcs that make the centre cheap

Finding a circle's centre with the compass alone, from two points on it, costs six circles when the points are placed with no special relation — and as few as two when the arc between them is 60°. Searching every arc in steps of five degrees maps the price exactly, and it is not a smooth function of the arc: it is a list of coincidences, each one a small number of compass steps that happens to land on a chord equal to the radius.

The best of thirty-four thousand scramblings

Verhoeff's check digit multiplies digits in the symmetry group of a pentagon after scrambling each one a different number of times, and 34,040 scramblings make it catch every swap of neighbours. Graded on the rarer errors, none of them catches everything, the best catch 86 of 90 doubled-digit slips and 848 of 900 swaps across a digit — and the scrambling Verhoeff published in 1969 is one of the forty that are best at both.

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

A grid of bits whose rank stops at the state

Fill a square grid with a generator's output bits and compute its rank over the field of two elements. Random bits give full rank or one short, in fixed proportions. A generator built from shifts and exclusive-ors gives full rank up to its number of state bits and then never one more — 32 for a 32-bit xorshift, 128 for the lowest bit of xorshift128+ — however large the grid. The test that catches it is decided by a line of linear algebra.

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

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

Three hundred thousand outputs of nearly nothing

Start the Mersenne twister from a state with a single 1 among its 19,937 bits and it puts out zeros, then sparse ones, and only after about 340,000 outputs anything that looks random. Every linear generator has such a zeroland around the all-zero state; xorshift128 crosses it in 37 outputs, WELL512 in 44, and the twister's three-word twist makes it the slowest of all by four orders of magnitude.

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

A perfect coin and a biased shuffle

Give a program a perfect source of random numbers and ask it to shuffle a deck by swapping each card with a card chosen from anywhere in the deck. The result is biased, provably and for every deck of three or more cards: there are nⁿ equally likely runs and n! orders, and the first number is never a multiple of the second. In a deck of 52 some card-and-place pairs come up a third more often than they should. Swapping only with cards not yet placed fixes it; swapping only with later cards makes nothing but single cycles.

The shortest string holding every ordering

Thirty-three symbols hold all twenty-four orderings of 1, 2, 3, 4 as blocks of four in a row, and no shorter string does. The formula 1! + 2! + … + n! gives the shortest length for up to five symbols and was believed for all of them — until a string of 872 for six beat its 873, and a lower bound posted anonymously on a forum left everything between 867 and 872 open.

What two points build in two rounds

Start with two points and draw every line and circle they allow; mark every crossing; do it again. The first round gives six points, the second gives 203, and the third gives over 1.7 billion. Computed exactly, the 203 points show the tower of square roots growing in real time — eleven rational points, seventy-six that need √3, and the rest needing one of six new square roots.

A seed is a deck

A shuffle that is perfectly correct, driven by a generator that passes every statistical test, can still deal almost none of the possible decks. A shuffle program is a function from the generator's starting state to an ordering of the cards, so it can never produce more orderings than the generator has states: a 32-bit seed reaches one deck in about 10⁵⁸. On nine cards and a 16-bit generator every case can be checked — 62,616 of the 362,880 orders are ever dealt — and on a full deck, six cards on the table are enough to name the seed and every card still to come.

Birthdays spaced too evenly

Scatter n birthdays through a year of k days, sort them, and count how many of the gaps between neighbours repeat an earlier gap. For random birthdays the count is close to a Poisson variable with mean n³/4k. A linear congruential generator with m states, read in pairs, matches that law until the grid has as many cells as the generator has states, and then leaves it at once: at sixteen times as many cells, every run of the spacings count rejects it. The sample that catches it is about five times the cube root of the period — 8,192 outputs for a 32-bit generator, thirteen million for a 64-bit one — and the same states, scrambled before they are read, pass.