Theme

Doing infinitely many things — page 4

Sums that never end, subdivisions that never stop, and the care required to make either of them mean something.

1 + 2 + 4 + … in two notions of size. Two sets of points against the number of terms up to 20 on an axis whose gridlines are powers of 2: the partial sums' ordinary size rising, their 2-adic distance from −1 falling.

A series that converges to minus one

1 + 2 + 4 + 8 + … runs off to infinity, and yet the formula for a geometric series says it should equal 1/(1 − 2) = −1. Measure size by how many factors of 2 a number has, instead of how large it is, and powers of 2 become small: the series converges, and to exactly −1. The same change of ruler explains why every repeating decimal is a fraction, and why repeating binary digits running off to the left are fractions too.

$The rationals and the dyadic fractions, matched 12 times without a crossing. Two number lines from 0 to 1, rationals above and dyadic fractions below, with 12 back-and-forth matchings: 1/2↔1/2, 1/3↔1/4, 2/3↔3/4, 1/4↔1/8, 3/4↔7/8, 2/5↔3/8, 1/5↔1/16, 3/5↔5/8, 4/5↔15/16, 2/7↔3/16, 1/6↔1/32, 3/8↔5/16.$ Logic

Two lists that are one order

The rationals and the fractions with a power of two below are different sets of numbers, and as orders they are exactly the same — any two countable orders that are dense and have no ends can be matched, point for point, keeping every comparison. The proof is a zigzag, and it settles every question the language of order can ask.

The first 16 vertices of Rado's graph, joined by binary digits. Adjacency table and circular drawing of the Rado graph on vertices 0 to 15, where i < j are adjacent when bit i of j is 1; 32 edges.

Logic

The graph that coin tosses always make

Take infinitely many vertices and toss a coin for every pair to decide whether they are joined. The result is random in every detail — and, with probability one, it is always the same graph. The same graph can be written down without any coins, by joining two numbers when one binary digit of the larger is a one.

$Three sizes of infinity, and the collections that have each. ℵ₀: the fractions, the algebraic numbers, every finite text, every definition of a number; 2^ℵ₀: the real numbers, the continuous functions, the open sets, the closed sets, the Borel sets; 2^(2^ℵ₀): all functions, all sets of reals, the non-Borel sets, the measurable sets.$ Logic

What counting can prove exists

There are only as many continuous functions as points of a line, only as many Borel sets, only countably many definitions — and more sets of reals than any of those. So counting proves that discontinuous functions, non-Borel sets and undefinable numbers exist without exhibiting one. It cannot prove that a set with no length exists, because the sets that have a length are exactly as numerous as all sets, and that difference turns out to be the difference between what the axioms force and what they merely allow.

A countable closed set stripped of its isolated points, 3 times. Cantor–Bendixson derivatives of the set of sums of up to 2 reciprocals: sizes 750, 40, 1, 0 in the truncation, ending empty.

Logic

Closed sets obey the continuum hypothesis

Whether some set of reals is bigger than the whole numbers and smaller than the line is a question the axioms cannot answer. For closed sets it has an answer, found in 1883: strip away the isolated points, again and again, and what is left is either nothing or a perfect set, which is as large as the line — so every closed set is countable or of the line's size. The same answer holds for Borel and analytic sets, and fails to be provable exactly one step further up.

Divergent and convergent integrands pressing towards each other. x·f(x) on a log scale for 1/x, 1/(x ln x), 1/(x ln x ln ln x) (divergent) and 1/(x (ln x)²), 1/(x ln x (ln ln x)²) (convergent), for x up to 10^300.

Analysis

No integrand sits on the border

The area under 1/x out to infinity is infinite and the area under 1/x² is finite, so it is natural to look for the dividing line. There is none. Divide any divergent integrand by its own running integral and it still diverges, more slowly; divide any convergent one by the square root of its tail and it still converges, more slowly. Paul du Bois-Reymond proved in 1873 that no single integrand can separate the two families — and the slow ones are slow beyond imagining.

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.

Computation

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.

Four stages of the four-corner Cantor dust. Four panels showing stages 1 to 4 of the four-corner Cantor set: 4, 16, 64 and 256 squares kept at the corners.

Analysis

A dust that almost every line misses

Keep the four corner squares of a square, then the four corners of each of those, and so on. What is left has a length, in the sense that measures length, and yet almost every straight line misses it entirely. Stage by stage the chance that a random line hits the dust falls — to 48% by the eighth stage — and how fast it falls to nothing is one of the few questions about a simple picture that is still open.

The Mandelbrot set counted cell by cell. A 96-cell-wide grid over the Mandelbrot set: 2034 cells certainly inside (1.3794), 290 undecided after 60 steps (0.1967).

Algebra

The area of the Mandelbrot set, from two sides

The Mandelbrot set has an area, and nobody knows it. Counting grid cells closes in on 1.5066 from both sides, but every count judges a cell by a single point, and points on the boundary never declare themselves. An exact formula exists — π times one minus a sum over the coefficients of the map onto the set's outside — and every partial sum is a guaranteed upper bound; after sixteen thousand coefficients the bound is still 1.786, and at the rate it falls it would need something like 10²⁵ more.

Analysis

The sine, rebuilt from its zeros

A polynomial is a product of factors, one for each root. Euler treated the sine the same way — one factor for each place the wave crosses the axis — and the product he wrote down is correct, though the zeros alone do not justify it. Multiplied out, it hands over the sum of the reciprocal squares, π²/6, and every even power after it.

Polynomials climbing to the square root, each above the last. The iterates of p ↦ p + (x − p²)/2 at steps 1, 2, 3, 4, 6, 9 on [0, 1] beneath the curve √x, with largest gaps 1.000, 0.500, 0.259, 0.176, 0.108, 0.068.

Analysis

Settling in order settles everywhere at once

A sequence of functions can settle at every point and never settle uniformly — the largest gap stays put while each point escapes it. Dini found the circumstances in which that cannot happen: continuous functions, a continuous limit, every member above the next, and a closed interval. Under those four conditions convergence at each point is convergence everywhere at once, and Weierstrass's iteration for the square root becomes a sequence of polynomials converging uniformly to |x|.

A diagonal walk through countably many listed sets. A grid of six rows and seven columns, each cell numbered by Cantor's diagonal order, with the path of the first twenty-one cells drawn.

Logic

The choice inside a countable union

A countable union of countable sets is countable: list each set, then walk the grid of all their members along its diagonals. The proof is two lines and every student meets it early. It also makes infinitely many arbitrary choices at once — one listing for each set — and without the axiom of choice the theorem can fail: there are consistent worlds in which the real numbers are a countable union of countable sets, and worlds in which countably many pairs of socks cannot be counted.

Records in a thousand draws, and the lengthening waits between them. A sequence of 1000 uniform draws on a logarithmic position axis, with records at positions 1, 6, 11, 27, 36, 145, 539, 927.

Probability

A wait that ends and has no average

Draw a number, then keep drawing until one beats it. Half the time the very next draw does. The wait is certain to end, it is usually short, and its average is infinite — and the chance of still waiting after n draws is exactly 1/(n + 1), whatever the numbers are drawn from, because symmetry is the only thing the calculation uses.

Probability

A share that depends on the average

What share of the whole numbers begin with the digit 1? Counted up to N, the answer swings between one ninth and five ninths for ever, and averaging the swing over N, even three times over, narrows it without removing it. Weight each number n by 1/n instead and the share settles at log₁₀ 2 — Benford's value — and so does every other sensible weighting that counts each decade alike. The primes behave the same way. Benford's law for the counting numbers is not a fact about them; it is a fact about how they are averaged.

The sum of all factorials in base 5: digits that stop changing. Partial sums of n! for N = 0 to 21, last 14 base-5 digits; the 5-adic limit ends …13010230042224.

Analysis

A sum of factorials that converges at every prime

1 + 1 + 2 + 6 + 24 + 120 + … grows faster than any geometric series and has no sum in the real numbers. Measure size by divisibility instead and the same series converges at every prime at once, to a different number each time. Whether any of those numbers ends in zero is a question Đuro Kurepa asked in 1971, and a search through every prime below 100,000 says no while a coin-toss model says it should have said yes about twice.

Number

When Euclid's number is itself prime

Multiply the primes up to p and add one. Euclid needed only that the result has a prime factor beyond p; it is itself prime for p = 2, 3, 5, 7 and 11, and then not again until 31, and then not until 379. Up to 1,100 there are nine such primes of each sign, against thirteen that a careful estimate expects. The estimate predicts infinitely many and grows by about 1.8 every time x is multiplied by e; nobody can prove there is even one more.

Number

The numbers that fool every base

561 = 3 · 11 · 17 passes Fermat's test for every base it shares no factor with, and so do 1,105, 1,729 and 102 more numbers below ten million. They were proved infinite only in 1994. Counted to 10²¹ there are about twenty million, growing like x to a power that has crept from 0.21 to 0.35 — just past the bound the proofs guarantee and nowhere near the power of one that Erdős's argument predicts.

Three countable models of one theory, different only above the constants. Models A (cₙ = n), B (cₙ = −1/(n+1), supremum 0), C (cₙ = 1, 7/5, 41/29, … rising to √2, no supremum) of the theory of a dense order with increasing constants.

Logic

Three models and never two

Take the theory of a dense order and add constants c₀ < c₁ < c₂ < … running upward for ever. The theory is complete — it decides every sentence — and yet it has exactly three countable models, told apart only by what lies above all the constants: nothing, a least point, or a gap with no least point. Vaught proved in 1961 that no complete theory has exactly two, and the proof builds this theory's third model out of its other two.

Probability

Peeking until the answer is yes

Toss a fair coin, test for bias after every toss, and stop the moment the result is significant at 5%. Within a thousand tosses nearly half of fair coins have been declared biased, and with no limit on the tosses every one of them is. Watch a Bayes factor the same way, stopping at twenty to one, and no amount of watching gets more than one fair coin in twenty past the line.

A dust plus itself is a line. C level 6: 64 intervals, length 0.0878; C+C: 1 interval(s) [0, 2].

Dynamics

Two dusts that add up to a line

The middle-thirds Cantor set has no length at all, and yet adding it to itself — every sum x + y of two of its points — fills the whole interval from 0 to 2 without a gap. The reason is a single number, the thickness, and it is exactly 1 for this set. Make the dust a little thinner and its sum with itself collapses to a dust again; make two different dusts and whether they add to a line depends on their dimensions, unless arithmetic gets in the way.

Each prime fixes the next digits of A. A = 1.306377883863080690468614492602605712916…; digits fixed by the primes from 11 to the 254-digit one: 1, 4, 11, 30, 87, 257.

Number

A constant that holds the primes

There is a number A = 1.3063778838… such that A cubed, A to the ninth, A to the twenty-seventh and every further power of three, rounded down, is prime: 2, 11, 1361, 2521008887 and on for ever. W. H. Mills proved in 1947 that such a number exists. It looks like a formula for primes and is the opposite of one. Its digits are read off the primes it produces, each prime fixes about as many digits as it has, and the whole argument stands on a theorem about gaps between primes — which is why the power is 3 and not 2.

A plane split by the order of a list. first 90 rationals; A has 4095 of 8100 pairs; 2/5 is listed at position 7.

Logic

The plane cut by a list

The continuum hypothesis looks like a statement about sizes: no infinity sits strictly between the whole numbers and the line. Wacław Sierpiński found in 1919 that it is equally a statement about the plane. It is true exactly when the plane splits into two pieces, one meeting every vertical line in only countably many points and the other meeting every horizontal line in only countably many. The split is drawn by listing the line's points in a particular order, and with the rationals in place of the reals it can be drawn exactly — a set that, counted column by column, has no area, and counted row by row, has all of it.

Analysis

No set fills half of every interval

A fat Cantor set has length one half and contains no interval, so every interval holds some of it and some of its gaps. Look closely at any one point, though, and the window around it ends up almost all set or almost all gap. Lebesgue proved in 1910 that this is forced for every set with a length: the share of a shrinking window is 0 or 1 almost everywhere. So no set can fill exactly half of every interval, however it is built.

Thirty-seven points in thirty-six boxes. n=6: pair q=8,15; difference 7: ‖q√2‖=0.100505, ‖q√3‖=0.124356.

Discrete

Two numbers approximated at once

Thirty-seven points in thirty-six boxes force a multiple of √2 and a multiple of √3 to land near whole numbers together, and the same count in more boxes makes q times the two distances less than one infinitely often. Littlewood guessed that the product can be made as small as anyone likes. Each number alone has a floor; the product finds a new record eight times below twenty million, and nobody can prove it will keep going.

All themes