Matpic
mathematics, in pictures
Field

Computation — page 2

A fixed set of operations, and the exact question of what it can and cannot build.
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.

 A scatter with no lines in it. 900 consecutive pairs from a generator that squares modulo a product of two primes. The points show no family of parallel lines, and an exhaustive search for a short relation between consecutive outputs finds none.

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 three pieces of the triangle-to-rectangle dissection drawn at 4 moments of the swing. Each top piece turns about a pin at the end of the slice it stands on, and the pieces stay joined throughout.

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

Every construction on this ladder turns its 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.

All essays