Theme

Decided by exhaustion — page 13

Questions with finitely many cases, settled by going through all of them — and what changes when a claim about every argument becomes a count.
Ten points, thirteen halving lines. points 0.253,1.518 0.242,0.216 0.717,0.119 -0.427,0.222 0.554,0.409 0.299,0.346 0.806,0.006 -1.101,0.118 1.209,-0.414 0.445,0.714; halving pairs 0-9 1-2 1-3 1-5 2-4 2-6 3-5 3-7 4-5 4-9 5-6 5-9 6-8; degrees 1,3,3,3,3,5,3,1,1,3. Topology

Lines that leave half on each side

Scatter ten points on a page and draw every line through two of them that leaves four on each side. There are at least five such halving lines and at most thirteen, and every point lies on an odd number of them. Both facts come from turning a line through half a revolution, the argument that halves two shapes with one cut. How many halving lines n points can have is the k-set problem, and its answer lies somewhere between a little more than n and n to the four-thirds.

How often a table of random signs is singular. n=2: 0.5000 (parallel 0.500); n=3: 0.6250 (parallel 0.625); n=4: 0.6602 (parallel 0.660); n=5: 0.6558 (parallel 0.628); n=6: 0.6270 (parallel 0.547); n=7: 0.5810 (parallel 0.442); n=8: 0.5216 (parallel 0.329); n=9: 0.4515 (parallel 0.234); n=10: 0.3757 (parallel 0.154); n=11: 0.2963 (parallel 0.0978); n=12: 0.2274 (parallel 0.0619); n=13: 0.1639 (parallel 0.0361); n=14: 0.1136 (parallel 0.0217); n=15: 0.07550 (parallel 0.0127); n=16: 0.04668 (parallel 0.00683); n=18: 0.01639 (parallel 0.00229); n=20: 0.004725 (parallel 0.000683) Algebra

How often a table of random signs is flat

Fill a square table with random plus and minus signs and ask whether its determinant is nought. For four rows the answer is yes two times in three. The chance then falls, and since 2020 it has been known to fall at exactly the rate of the dullest accident, two rows or columns equal or opposite. The conjecture is that this accident is, in the end, the whole story. Every size a computer can reach says otherwise, and the theory says the computer has not gone far enough.

How often a game picked at random has a core. n=3: 0.20:1.000 0.24:1.000 0.28:1.000 0.32:1.000 0.36:1.000 0.40:1.000 0.44:1.000 0.48:1.000 0.52:1.000 0.56:1.000 0.60:1.000 0.64:1.000 0.68:1.000 0.72:0.997 0.76:0.993 0.80:0.980 0.84:0.958 0.88:0.933 0.92:0.899 0.96:0.872 1.00:0.833; n=4: 0.20:1.000 0.24:1.000 0.28:1.000 0.32:1.000 0.36:1.000 0.40:1.000 0.44:1.000 0.48:1.000 0.52:0.991 0.56:0.937 0.60:0.843 0.64:0.737 0.68:0.634 0.72:0.517 0.76:0.424 0.80:0.323 0.84:0.258 0.88:0.182 0.92:0.134 0.96:0.091 1.00:0.066; n=5: 0.20:1.000 0.24:1.000 0.28:1.000 0.32:1.000 0.36:1.000 0.40:1.000 0.44:0.994 0.48:0.904 0.52:0.725 0.56:0.438 0.60:0.245 0.64:0.116 0.68:0.059 0.72:0.022 0.76:0.009 0.80:0.002 0.84:0.002 0.88:0.001 0.92:0.001 0.96:0.000 1.00:0.000 Applied

A core is a rare thing to find at random

A game has a core when the whole can be shared so that no group would do better on its own, and Bondareva and Shapley turned that into a finite list of checks. For three players there are five checks; for four, forty-one; for five, 1,291. Draw the coalitions' values at random and the list wins: a third of three-player games fail, nineteen four-player games in twenty, and not one five-player game in two thousand passes. The cores that theorems promise come from structure, and structure is exactly what a random game lacks.

The Golay code drawn from an icosahedron. generator rows f19001 e72002 eac004 47d008 8bb010 33e020 bca040 7d4080 de1100 2e7200 58f400 957800; weight distribution 0:1 8:759 12:2576 16:759 24:1. Computation

A code built from an icosahedron

Write down which corners of an icosahedron are not joined by an edge, put the table beside a diagonal of ones, and add the twelve rows together in every combination. The 4,096 strings of 24 bits that come out differ from each other in at least eight places, occur in only five weights, and — with one bit deleted — fill the space of 23-bit strings so exactly that every one of the 8,388,608 lies within three flips of exactly one of them. This is the Golay code, which carried Voyager's pictures home, and its words of weight eight cover every five of the twenty-four positions exactly once.

The point on the most connecting lines. two lines 7+7: degrees 8,8,8,8,8,8,8,8,8,8,8,8,8,8; grid 5x5: max 15. Geometry

The busiest point in a set

Scatter points in the plane, not all on one line, and draw every line through two of them. Some point lies on many of those lines — but how many must? Gabriel Dirac guessed half: in any such set, some point is on about half of the lines it could be on. Split the points evenly between two lines and no point does better than half plus one, so the guess cannot be raised. Proving it is another matter. Seventy years on, the best theorem says a third.

Two majorities of one class must overlap. regions (outside, S, M, SM, P, SP, MP, SMP): 3,2,0,4,2,0,4,2. Logic

Syllogisms that say most

The syllogism knew four words — all, no, some, some not — and two thousand years of logic decided which of its 256 forms were valid. Add 'most', a word everyone uses in arguments, and the 256 become 864. A diagram with marks for 'empty' and 'occupied' can no longer decide them, because 'most' compares sizes; but writing the number of things in each region turns every form into a linear programme, and the programme decides all of them at once. Thirty-one are valid, including one Augustus De Morgan found in 1847: if most M are S and most M are P, then some S are P. And 'most' cannot be passed along a chain: ninety-nine per cent of S can be M, ninety-nine per cent of M can be P, and no S be P at all.

Every denominator has a fraction with small quotients. 2:1340 3:1624 4:32 5:3; need 5: 6,54,150 Number

A small quotient for every denominator

Pick a denominator, any whole number. Among the fractions with that denominator, is there always one whose continued fraction has no large entries — whose path down the Stern–Brocot tree never turns the same way more than five times running? Stanisław Zaremba guessed so in 1972, for a reason to do with sampling a square evenly. Every denominator up to a hundred thousand obeys, with only 6, 54 and 150 needing a five. The guess is proved for almost every denominator and not for all, and the reason it ought to be true is a dimension: the reals whose quotients stay at most five fill a set of dimension 0.837, enough to give each denominator thousands of good fractions on average, and the open question is whether averages are kept everywhere.

Two polynomials that factor alike at every prime. 5:8 7:2+2+2+2 11:1+1+2+2+2 13:1+1+1+1+2+2 17:8 19:4+4 23:1+1+2+2+2 29:8 31:2+2+2+2 37:4+4 41:8 43:4+4 47:1+1+2+2+2 53:8 59:1+1+2+2+2 61:4+4 67:4+4 71:1+1+2+2+2 73:4+4 79:2+2+2+2 83:1+1+2+2+2 89:8 97:4+4 101:8 103:2+2+2+2 107:1+1+2+2+2 109:1+1+1+1+2+2 113:8 127:2+2+2+2 131:1+1+2+2+2 137:8 139:4+4 149:8 151:2+2+2+2 157:4+4 163:4+4 167:1+1+2+2+2 173:8 179:1+1+2+2+2 181:1+1+1+1+2+2 191:1+1+2+2+2 193:2+2+2+2 197:8 199:2+2+2+2 211:4+4 223:2+2+2+2 Algebra

Two fields that every prime confuses

Reduce x⁸ − 3 and x⁸ − 48 modulo any prime other than 2 and 3 and factor them: the two lists of factor degrees are the same, at all 9,590 such primes below 100,000. The fields the two equations define are still different. The reason is a pair of ways for one group to permute eight roots, with the same cycle lengths element by element and different fixed points — the same coincidence, in degree seven, as the points and lines of the Fano plane.

How often each rule finds the Condorcet winner. n=3: 0.8824/0.9412/0.9559/0.6471; n=5: 0.8259/0.9751/0.9378/0.6866; n=7: 0.8281/0.9578/0.9278/0.6833; n=11: 0.8054/0.9656/0.9179/0.7079; n=21: 0.7941/0.9619/0.9097/0.7205; n=51: 0.7804/0.9624/0.9046/0.7339; limit 0.7572±0.0009/0.9629±0.0004/0.9011±0.0006/0.7563±0.0009; P(CW) limit 0.9116. Applied

How often the rules find the majority favourite

When one candidate beats every rival head to head, a voting rule ought to elect it. Plurality does about three times in four when every ranking is equally likely, the runoff between the top two 96 times in a hundred, Borda's count 90. Every profile of up to 51 voters is counted exactly, the limit is sampled, and adding candidates pulls plurality down below one half.

A word that survives losing any one of its bits. codeword 100110010110, a=0 mod 13; deletions at 1..12 all decoded. Computation

A code that survives a lost bit

A flipped bit leaves the word the right length and wrong in one place; a lost bit leaves it one short, with no sign of where the gap was. Keep only the words whose 1s sit at positions adding up to a multiple of n + 1, and any single lost bit can be put back. The price is about log₂(n + 1) bits, the same as the Hamming code pays for a flip.

A bracket that shrinks by the golden ratio. 2: [0.00000, 1.00000]; 3: [0.00000, 0.61803]; 4: [0.23607, 0.61803]; 5: [0.23607, 0.47214]; 6: [0.32624, 0.47214]; 7: [0.32624, 0.41641]; 8: [0.36068, 0.41641]; 9: [0.36068, 0.39512]; peak 0.374750. Geometry

The search that reuses a point

To find the peak of a function that rises and then falls, evaluate it at two points and throw away the part beyond the lower one. Place the points so that the survivor can be used again, and there is exactly one way to do it: at the golden ratio. Each new evaluation then shrinks the bracket to 0.618 of its width, and with a fixed number of evaluations nothing does better than Fibonacci's numbers.

The bases that still pass for 561. n=561: coprime 320, Fermat liars 320, strong liars 10 (Monier 10). Number

A quarter of the bases at most

Carmichael numbers pass Fermat's test for every base they share no factor with, so Fermat's test can be fooled for ever. Watch the squarings on the way to aⁿ⁻¹ instead, and a prime allows only one pattern; 561 lets just 10 of its 320 bases through, and Monier and Rabin proved that no odd composite but 9 lets through more than a quarter. Four fixed bases prove every number below 3.2 billion prime or not.

A curve that crosses a line twelve times. n=6: upper 9,8,7,6,5,4,3,2,1,0,11,10; lower 3,2,1,0,7,6,5,4,11,10,9,8; meanders 1828 of 17424. Topology

Curves that cross a line and close

Draw a closed curve that crosses a straight line 2n times and never crosses itself. Above the line it is a set of nested arches, below it another, and every such curve is a pair of the Catalan number's arch systems that happen to close into one loop. There are 1, 2, 8, 42, 262, 1,828 of them, and every count computed so far grows by a factor creeping towards 12.26 — a number nobody can prove, with an exponent conjectured from the physics of random surfaces.

A decisive set halved for ever. voter 37: residues 1, 1, 5, 5, 5, 37; …111: residues 1, 3, 7, 15, 31, 63. Logic

An electorate too large for a dictator

Arrow proved that a voting rule with his four properties must have a dictator, and his proof uses the finiteness of the electorate exactly once. With infinitely many voters the dictator can vanish: the sets of voters who get their way form an ultrafilter, and every free ultrafilter is a rule with all four properties and nobody in charge. The catch is that no such rule can be written down. Its existence is a fragment of the axiom of choice.

One quantifier blind to two others. The prefix ∀x∃y∀u∃v drawn in a line, where v depends on x, y and u, and in branching form, where y depends only on x and v only on u; six points paired off by a fixed-point-free involution and five points, where no such pairing exists. Logic

Four quantifiers, one of them blind

In 'for every x there is a y, and for every u there is a v', the last choice may depend on everything before it. Leon Henkin asked in 1961 what happens if v may depend on u alone. Using nothing but the equals sign, four such quantifiers then say that a set has an even number of points, or that it is infinite — things no ordinary sentence can say — and the game behind the sentence can end with neither player able to win.

The far end of a sliding tray falls as holes are added. Exhaustive search of the 2×3, 2×4 and 3×3 sliding trays with one to all-but-one holes. Far ends for the 3×3 tray: 31, 24, 21, 17, 13, 10, 7, 4; averages 21.97, 16.04, 12.70, 9.99, 7.88, 5.92, 3.75, 2.00. Algebra

A second empty square

With one empty square a sliding tray can reach exactly half its arrangements, and the half it misses is guarded by a sign. Leave a second square empty and the guard disappears — every arrangement is reachable, two tiles can be exchanged in four moves, and the far end of the three-by-three tray comes in from thirty-one moves to twenty-four. Searching every tray with every number of holes shows what each extra square of room is worth.

How many words can survive two lost bits. Two-deletion-correcting code sizes by length: n=4: optimum 2, greedy 2, Helberg 2; n=5: optimum 2, greedy 2, Helberg 2; n=6: optimum 4, greedy 4, Helberg 3; n=7: optimum 5, greedy 5, Helberg 4; n=8: optimum 7, greedy 6, Helberg 5; n=9: optimum 11, greedy 9, Helberg 6; n=10: optimum -, greedy 13, Helberg 8; n=11: optimum -, greedy 20, Helberg 9; n=12: optimum -, greedy 29, Helberg 11; n=13: optimum -, greedy 46, Helberg 15. Computation

Two lost bits

One congruence repairs any single lost bit, and the set of words it defines is believed to be the best possible. Two lost bits defeat it. An exhaustive search finds the largest codes that survive two — 2, 2, 4, 5, 7 and 11 words for lengths 4 to 9 — and Helberg's congruence, with weights that grow like Fibonacci numbers, gives a code that provably works at every length but spends a fixed share of every bit on protection. The best codes need only about four times the logarithm of the length.

Three arrows in and three out: counting on prisms of the cubic grid. Entropy per point of Eulerian orientations on cubic prisms: 2x2: 2.79369, 2x3: 2.68151, 3x3: 2.58713; small tori 2 × 2 × 2 3.14618, 2 × 2 × 3 2.95513, 2 × 3 × 3 2.81100, 3 × 3 × 3 2.69925; Pauling 2.5. Discrete

Three arrows in and three out

Put an arrow on every edge of the cubic grid so that every point has three arrows in and three out. On the square grid the same question — two in, two out — has an exact answer, found by Elliott Lieb in 1967: about 1.5396 arrangements per point. On the cubic grid nobody knows the answer. Pauling's guess of 2.5 is a proven lower bound, and exact counts on prisms of the grid come down towards it from above — 2.794, 2.682, 2.587 as the cross-section widens — without reaching it.

How wide the narrowest refutation must be. Minimal resolution refutation widths by saturation: parity on a cycle of six: 2 (widest clause 2, 6 letters, 12 clauses); parity on K₄: 4 (widest clause 3, 6 letters, 16 clauses); parity on the prism: 4 (widest clause 3, 9 letters, 24 clauses); parity on K₃,₃: 5 (widest clause 3, 9 letters, 24 clauses); three pigeons, two holes: 2 (widest clause 2, 6 letters, 9 clauses); four pigeons, three holes: 3 (widest clause 3, 12 letters, 22 clauses). Logic

The narrowest refutation

A resolution refutation can be long, and it can be wide — use clauses with many letters. Width turns out to be the easier of the two to compute exactly: derive everything that can be derived without ever writing a clause longer than w, and see whether a contradiction appears. Doing that for small formulas shows the parity formulas of graphs needing wider clauses than they contain, by more on graphs that are harder to cut in half, and the pigeonhole formulas needing no extra width at all — although every refutation of them is exponentially long. Width is not the whole price.

What each connective of two letters can express on its own. Three-letter fragment sizes of the clones generated by single binary connectives: false 4, nor 256, not x but y 38, not x 6, x but not y 38, not y 6, xor 8, nand 256, and 7, iff 8, y 3, if x then y 38, x 3, if y then x 38, or 7, true 4. Logic

What an incomplete set of connectives can say

Nand alone can express every truth function, and Post's five properties say exactly which sets of connectives can. That answers the question at the top. Below it lies a whole landscape: and alone expresses 7 of the 256 functions of three letters, xor 8, implication 38, and the sixty-four sets that can be drawn from and, or, not, xor and the two constants fall into just 22 different classes of expressible functions. The classes fit together into Emil Post's lattice of 1941 — countably infinite, completely described, and on three letters small enough to draw.

The unitary divisors of every number, and the four that sum to exactly twice. sigma*(n)/n for n up to 100000; equal to 2 at 6, 60, 90, 87360; maximum 3.2224 at 30030. Search to 10000000 finds 6, 60, 90, 87360. Number

Divisors that take a prime whole

Six is perfect because its proper divisors 1, 2 and 3 add up to 6. Keep only the divisors that take each prime of a number completely or not at all — for 60, that is 1, 3, 4, 5, 12, 15 and 20 — and ask for the same coincidence. Below ten million it happens four times: 6, 60, 90 and 87,360. The fifth has twenty-four digits. And unlike ordinary perfect numbers, where nobody knows whether an odd one exists, here a two-line argument rules every odd number out.

How many fourth powers every number needs. Fewest fourth powers summing to n, n <= 10000000: 19 needed by 79, 159, 239, 319, 399, 479, 559; 18 by 24 numbers (last 1248); 17 by 65 (last 13792). Number

Nineteen fourth powers, and then sixteen

Edward Waring claimed in 1770 that every number is a sum of at most nineteen fourth powers. It is true, and it is needed: 79 takes nineteen, because its remainder on division by sixteen forces fifteen ones. But only seven numbers need nineteen, the last of them 559; the last to need eighteen is 1,248, and the last to need seventeen is 13,792. Counting every number to ten million shows the stragglers thinning out and the one obstruction that never goes away — the remainder modulo sixteen, which makes 31, 496, 7,936 and every 31·16ᵐ need sixteen for ever.

The 7 × 7 Fourier matrix as arrows. Entries of the order 7 discrete Fourier matrix as unit arrows, with the minor on rows 1,3,4 and columns 0,2,5 highlighted; its determinant has modulus 2.645751. Algebra

A prime leaves no room for a comb

Take the table of powers of a root of unity, pick any rows and any equal number of columns, and take the determinant. At order 12 about one such determinant in six is exactly nought. At order 11, among 184,756 of them, none is, and in 1926 Chebotarev proved that none ever is at a prime. It means a signal on p places and its transform together occupy at least p + 1, while a comb on twelve places and its transform take 4 and 3.

Three distances fix a word of three bits. The cube of three-bit words with landmarks 000, 001, 010; each word labelled by its Hamming distances to them; all eight lists differ. Computation

How few distances fix a word

An unknown word of a thousand bits can be read one bit at a time with a thousand questions. Ask instead for its distance from a chosen word, and each answer is worth about half of log₂ n bits, so roughly two hundred distances fix it. A balance reading many coins at once is the same question. So is Mastermind, in which Knuth's rule finds any of the 1,296 codes in at most five guesses and a mean of 4.476, and no first guess is best on both counts.

All themes