Theme

Doing infinitely many things — page 3

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

Closed after 3 uses of the universal. The Herbrand expansion of a first-order question at 5 stages, with the number of remaining models at each. It reaches nought after 3 instantiations.

The instance that has to be guessed

Every rule of a propositional tableau replaces a formula by shorter ones, which is why it stops. The rule for a universal claim does not replace it — it keeps it and adds an instance — and one word changing turns a decision procedure into a search that may run forever.

sin(2πkx) for k up to 10, and the largest gap between every pair. Members of the sequence sin 2πkx drawn on one pair of axes, beside a table of the largest vertical gap between every two members, none of which is less than one.

Analysis

The subsequence that has to exist

Every bounded list of numbers has a part that settles down. A bounded list of functions need not: the waves sin 2πkx never come within 1.76 of one another. One extra condition — that no member may change faster than a bound they all share — restores the guarantee, and it is the reason a differential equation with a continuous rule has a solution at all.

Partial sums of x − x²/2 + x³/3 − … on [0, 1]. Partial sums of the power series x − x²/2 + x³/3 − … drawn on the interval from 0 to 1 with the function the series sums to inside the interval, and the values at x = 1 marked.

Analysis

A sum read from inside

The series 1 − 1/2 + 1/3 − 1/4 + … adds to log 2, and the reason is not in the series. Its power series equals log(1 + x) inside the interval, and the value at the edge is read off by continuity. Abel's theorem says when that reading is honest — and the series 1 − 1 + 1 − …, which has no sum, is read the same way as a half.

Inscribed polygons in a quarter circle, and the length they climb towards. Four polygons inscribed in a quarter circle with increasing numbers of corners, each drawn over the curve, with its length beneath it — the lengths increase towards the curve's own.

Analysis

Which curves have a length at all

A length is defined as a supremum over inscribed polygons, which behaves because every refinement is longer than the last. It is also sometimes infinite — and the condition separating the two cases is a sum of absolute differences that either settles or does not.

The ball around the identity, in 3 groups. A table of the number of group elements within each distance of the identity, one row per group, with the growth type each row exhibits beside it.

Algebra

How fast the ball fills

Count the elements within r steps of doing nothing. The count grows like a polynomial in some groups and like a power of three in others, the distinction survives every change of generating set, and which polynomial degrees are possible is a theorem nobody expected.

Algebra

The edge that is as big as the ball

In a lattice the boundary of a large ball is a negligible fraction of it. In a tree it is two thirds of it at every size — and that single ratio, not the group's size, is what decides whether a set can be cut into pieces and reassembled into two copies of itself.

Runs of doubling length in 1/n^2, and the geometric series that bounds them. A bar for the total of each run of terms of 1/n to the 2, with an outlined bar above it for the bound obtained by replacing every term in the run with its largest, the bounds forming a geometric series.

Analysis

The repair at the boundary

Where the geometric yardstick says nothing, compare a series with itself at doubled spacing. That one move turns every 1/n^p back into a geometric series, reads the threshold off at p = 1, and then produces an infinite hierarchy of boundaries with no slowest divergent series anywhere in it.

Number

Why a quarter of numbers overshoot

About one number in four has proper divisors adding to more than itself. That a proportion exists at all is not automatic — there are sets defined just as simply that have no proportion — and the reason this one does is that abundance is inherited by multiples, and the numbers it is first inherited from are sparse enough to add up.

The order type of a nonstandard model of arithmetic. The ordinary numbers as a run of dots, followed by 9 galaxies — copies of the integers — at the positions of c/2 up to 2c, ordered densely like the rationals, with c² beyond. Infinitely many more galaxies lie between those drawn.

Logic

A number larger than every number

Ask for a number bigger than 0, bigger than 1, bigger than 2, and so on for ever. Every finite piece of that request is granted by an ordinary number, so compactness grants all of it at once — in a structure that satisfies every sentence true of the whole numbers and still contains something beyond all of them. Nothing in first-order logic can say 'and nothing else'.

A countable structure grown by adding witnesses. Stages of a structure built from 0 and 1 by adding sums, products, negatives and roots of quadratics: 2, 4, 12, 158 elements between −3 and 3.

Logic

A countable field that passes for the line

The real numbers are uncountable, and every first-order sentence about their addition, multiplication and order is also true of a countable field inside them — the real algebraic numbers. Löwenheim and Skolem showed this is no quirk of the reals: every theory with an infinite model has a countable one, including set theory, which then contains sets it calls uncountable.

Area out to infinity, for three powers. Left: the curves 1/√x, 1/x, 1/x² from x = 0 to 10, with the region beyond x = 1 shaded under the lowest. Right: the area from 1 to T for each, on logarithmic scales, for T up to 10^6. 1/√x keeps growing, 1/x keeps growing, 1/x² levels off at 1.

Analysis

An endless region with a finite area

A region that runs off to infinity can still have a finite area, and for the curves 1/xᵖ the exponent that makes the far end finite is exactly the one that makes the end at zero infinite. 1/x fails at both, no power succeeds at both, and a horn can hold less than π while needing infinite paint.

An additive function that is nowhere a line. A square window with 1157 points of the graph of an additive function that sends √2 to 0, scattered across the window and meeting every part of it, beside a dashed diagonal marking the straight line y = x.

Logic

A function that adds and is nowhere a line

Every continuous function with f(x + y) = f(x) + f(y) is a straight line through the origin. Drop continuity and, given the axiom of choice, there are others — functions that add perfectly and whose graphs are scattered densely over the whole plane. A finite piece of the construction can be drawn exactly; the whole of it needs a basis of the real numbers that no one can write down.

Logic

Infinitely many guessers, finitely many wrong

An infinite line of people each wears a black or white hat, sees every hat in front and none of their own, and must guess their own colour. With a finite line, each guesser is right half the time whatever they agree in advance. With an infinite line and the axiom of choice, they can agree a strategy under which all but finitely many are right — and nobody can carry it out.

$How long four orbits of the doubling map spend in each quarter. Grouped bars for four starting points of the doubling map, each group showing the fraction of time the orbit spends in each quarter of the unit interval, against a dashed line at one quarter.$ Dynamics

Almost every orbit is fair

Double a number and keep the fractional part, and do it again, and again. Where the orbit goes is written in the number's binary digits, and for almost every starting point it spends exactly a quarter of its time in each quarter of the interval. The proof is a short argument about Fourier coefficients being pushed to infinity — and it leaves room for a set of exceptions with no length at all, which includes every fraction and, for all anyone can prove, every number anyone has ever named.

$Thomae's function as a limit of tents, at n = 3 and 8. Continuous functions built from narrow triangles over the fractions, drawn at two stages, with the limit shown as a dot at height 1/q over every fraction p/q: a function continuous at the irrationals and discontinuous at the rationals.$ Analysis

A limit can jump at every fraction

A sequence of continuous functions can settle, point by point, on a function that is discontinuous at every rational number. It cannot settle on one that is discontinuous everywhere — the indicator of the rationals needs two limits in a row, and Riemann's integral cannot follow the second. The line between the two is Baire's theorem, and it measures smallness by gaps rather than by length.

xⁿ is uniform off a strip, with N = 14, 29, 59 for 3 strips. The functions x to the n on the unit interval with a band of half-width 0.05 around zero. For each of 3 strips next to 1, the member at which every later one stays in the band away from the strip.

Analysis

Uniform, except on a small set

The functions xⁿ settle on their limit at every point and never uniformly — the trouble is all in a strip next to 1. Throw the strip away and the convergence is uniform on what is left, however thin the strip. Egorov proved that this always happens on an interval, Lusin proved the matching fact about a single function, and a bump sliding off along the whole line shows why both need a set of finite length to start from.

The Cantor function has length 2. The graph of a singular or partly singular increasing function on the unit interval with an inscribed polygon, beside a table of inscribed lengths by stage and the value the derivative formula gives.

Analysis

The length the derivative never sees

The Cantor function climbs from 0 to 1 with a slope of zero almost everywhere, so the formula ∫√(1 + f′²) dx says its graph has length 1 — the length of a flat line. The inscribed polygons say 2. Mix it half and half with the diagonal and the length becomes exactly the golden ratio, while the formula still reports only the part the slope can see.

The ground a 1,500-step walk covers. A random walk on a square grid drawn as a path, with every grid square it visited shaded and its start and end marked.

Probability

The ground a walk covers

A random walk of a thousand steps visits far fewer than a thousand places: in one dimension about fifty, in the plane about four hundred, in space about six hundred and sixty. The share of steps that land on new ground is exactly the chance of never coming home — so the number that decides whether a walker returns also decides how much of the world it sees.

The Dirichlet kernel, a spike with ripples that do not die. The Dirichlet kernel for N = 4, 12 on the interval from −π to π: a central spike of height 2N + 1 and side ripples whose total area in absolute value grows with N.

Analysis

The ripples that make a series run away

Adding up the first N terms of a Fourier series is the same as averaging the function against one fixed wiggly curve. Its area is always one, but the area of its absolute value grows like the logarithm of N, without limit — and that single number is enough to force a continuous function, with no jump and no corner anywhere, whose Fourier series diverges at a point. Averaging the partial sums removes the negative ripples, and with them the whole problem.

Square roots of 2, lifted from one power of 7 to the next. A tree whose rows are the square roots of 2 modulo 7 to the powers 1 to 4, each joined to the root it reduces to; counts 2, 2, 2, 2.

Discrete

A root lifted one digit at a time

On a dial of seven, 3 × 3 is 2. On a dial of forty-nine the square root of 2 must reduce to 3, so there are only seven candidates, and exactly one of them works: 10. On a dial of 343 exactly one lift of 10 works: 108. Each step adds one digit on the left, found by solving a linear equation, and the digits go on for ever — a number …21216213 whose square is 2, in a world where closeness means divisibility by seven.

The free group on two generators with its middle removed: 4 pieces. The Cayley graph of the free group on two generators, with the elements within 0 steps of the identity greyed out and the remaining elements coloured by which connected piece they fall in.

Algebra

What is left when the middle is taken out

Cut a finite piece out of a group's picture and count the parts of what remains that run off forever. The integers leave two, the plane one, a tree more with every cut — and no group anywhere leaves exactly three, because a third end is always the first of infinitely many.

One lattice, 3 generating sets, 3 shapes of ball. Lattice points reached within a fixed number of steps in the integers squared, for one step along either axis, axis steps and one diagonal, a king's moves, each drawn inside the polygon spanned by its steps and scaled by the radius.

Algebra

The polygon a lattice becomes from far away

Walk the grid of whole-number points with a fixed set of moves and the places reachable in r moves fill a shape. With axis steps it is a diamond, add a diagonal and it is a hexagon, move like a knight and it is a ragged thing full of holes — which, seen from far enough away, is an octagon exactly. The generators decide the polygon, and the polygon decides the count.

An infinite graph that passes every finite test. Two columns of vertices continuing downward without end. The top left vertex joins every vertex on the right; each other left vertex joins only the one beside it.

Discrete

Enough partners in every finite group

Hall's theorem says a matching exists unless some group has too few partners between them. On an infinite graph that is false: one vertex that can be paired with anybody, and every other with exactly one, passes the test on every finite group and has no matching at all. The failure needs a vertex with infinitely many choices. Forbid that, and the theorem comes back, by an argument about trees rather than about matchings.

The units of a cubic field, as a lattice of logarithms. Points for 66 units of the field of a root of x³ − 3x + 1, plotted by the logarithms of two of their conjugates, lying on the lattice spanned by the logarithms of θ and θ − 1.

Algebra

Units that form a lattice

In the whole numbers only 1 and −1 have whole-number reciprocals. In the integers of a bigger field there can be infinitely many such units, and they are not scattered: take logarithms of their sizes under each way of placing the field in the real or complex numbers, and the units land exactly on a lattice. How many dimensions that lattice has is a count of those placements, and the area of its cell is a number no formula gives.

All themes