Lattice
Named by 43 essays across 11 fields — each of them below, with the objects they name alongside it.
The shape of a number's divisors
Lay a number's divisors out as a lattice with one axis per prime, and two of the most useful facts in arithmetic stop being formulas and become the width and the corner of a rectangle.
Two squares, and a lattice
Whether a prime is the sum of two squares is decided entirely by its remainder on division by four. A fact about circles is settled by a fact about remainders, and neither statement contains any hint of the other.
Two dials at once
Watch one number on two clocks with different faces. If the faces share no factor, every pair of readings occurs exactly once — so two remainders name a number, and a hard calculation can be split into two easy ones.
Counting one rectangle, twice
Whether seven is a square modulo eleven, and whether eleven is a square modulo seven, are two unrelated-looking questions. Their answers are linked, and the link is a rectangle of dots counted along its rows and then along its columns.
Area by counting dots
Draw a polygon with every corner on a grid of dots. Count the dots strictly inside, add half the dots on the edge, subtract one — and the answer is the area, exactly, with no measuring anywhere.
The lattice that runs the other way
The symmetries of a polynomial's roots form a group, and the fields between the bottom and the top form a lattice. The two are the same picture, one of them turned over — a bigger group of symmetries fixes less, so it names a smaller field.
The planes a recurrence cannot leave
One multiplication and one addition, taken modulo a fixed number, produce a sequence that passes for random one value at a time. Taken two or three at a time it does not, and the reason is a whole-number relation that pins every point onto one of a small family of parallel lines.
One point in every big enough shape
A determinant measures a lattice, not the basis that happened to describe it — and that measurement is an exchange rate. Any symmetric convex region with more than four times that area has to swallow a lattice point.
The integers among the quaternions
The obvious integer quaternions are the ones with whole coordinates, and they are the wrong ones. Sixteen more, with every coordinate a half, have to be let in — and with them comes a division algorithm, twenty-four units instead of eight, and a regular solid that exists only in four dimensions.
The theorem that has no version in space
A lattice polygon's area is decided completely by two counts of dots. The obvious guess is that a lattice solid's volume is decided by the same two counts in three dimensions, and there is a family of tetrahedra with identical counts and every volume that says otherwise.
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.
Two hundred and forty directions
The quaternions have twenty-four units and they are the vertices of the most symmetric object in four dimensions. Eight dimensions has two hundred and forty of them, and the quaternions turn out to be how they are built — twice over, with a hundred and ninety-two left to explain.
Sixteen polygons with one dot inside
Fix one of Pick's two counts at one and ask what is left. The answer is a finite list, the list has exactly sixteen entries, each one is its own kind of object with a dual that is another entry, and the whole classification is a search a page can carry out.
The dots a circle catches
Pick's theorem gives a lattice polygon's area exactly, with no error term anywhere. Ask a circle the same question and the exactness is gone: the count is the area plus something, the something has been measured for two centuries, and nobody knows how big it is.
Not one step but a continuum
Classical logic is the constructive system plus one axiom, which makes it sound as though there are two logics and one gap. There are uncountably many logics in that gap, each one a class of algebras, and the smallest separations between them fit in five elements.
The two squares actually produced
Three proofs say a prime one more than a multiple of four is a sum of two squares, and not one of them hands over the squares. Running the Euclidean algorithm half-way does — and where to stop is the whole of the correctness argument.
![The integers of ℚ(√5), with ℤ[√5] inside them. Points a + bφ plotted against their conjugates for small whole a and b, with the index-two sublattice ℤ[√5] filled and the basic cells of both lattices shaded, of areas √5 and 2√5.](/f/the-integers-of-q-5-with-z-5-inside-them-a4f067e7.svg)
The integers a field contains
Inside the field of numbers a + b√5, the obvious integers are those with whole a and b. They are not all of them: the golden ratio has a one-half in it and satisfies x² = x + 1, a monic equation with whole coefficients, exactly as an integer should. The right integers form a lattice twice as dense as the obvious one — and a whole-number matrix proves they are closed under addition.
Factoring uniquely with no way to divide
Unique factorisation is proved by dividing with a small remainder, and in the Gaussian integers that works because discs of radius one cover the plane. In the integers of ℚ(√−19) the discs leave holes, no division algorithm of any kind can be made to work — and factorisation is unique anyway. The same field is why n² + n + 41 is prime forty times running.
A walk that may not step where it has been
Forbid a walk on the square grid from ever revisiting a site and the number of possible n-step walks grows like 2.638ⁿ instead of 4ⁿ — a number nobody can write down exactly. On the honeycomb it is exactly √(2 + √2), proved in 2010. And the walks spread out like n to the three-quarters, faster than any ordinary walk, which physicists have used since 1949 and mathematicians still cannot prove.
The loops on a torus that never cross themselves
Every loop on a torus is classified by two whole numbers: how often it goes round one way and how often the other. Some classes can be drawn without the loop ever crossing itself and some cannot, and the rule is the oldest in arithmetic — the two numbers must have no common factor. The same two numbers say how often any two loops must meet.
The ball that stays outside the table
Turn billiards inside out. A point outside a convex table looks at the corner on its right, jumps straight through it, and lands as far beyond as it started before. Round a square every orbit closes; round a circle every orbit keeps to its own circle; round a regular pentagon the orbits form islands with a fractal between them. Whether some table lets a point wander off to infinity was Moser's question, and the answer — yes, for a kite — took until 2007.
The diagonal no unit measures
Draw the five diagonals of a regular pentagon and they make a star with a smaller pentagon at its centre. Subtract the side from the diagonal and what is left is the smaller pentagon's diagonal; subtract that from the side and what is left is its side. The pentagon has handed back a smaller copy of itself, and it will do so for ever — which means no unit, however small, measures both the side and the diagonal an exact whole number of times.
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.
One extra person on one side
In a random market of a thousand a side, whoever proposes gets about their seventh choice and whoever receives gets about their hundred-and-fortieth. Add one person to one side and the advantage of proposing all but disappears: the shorter side does well and the longer side badly, whichever side proposes, and most people are left with exactly one stable partner.
The matching in the middle
List every stable matching of a market, give each member their stable partners sorted from best to worst, and hand each the one in the middle. Nothing says the result should even be a matching — two people might pick the same partner — and yet it always is one, it is always stable, and the other side gets its median partners too.
The wait for the next sum of two squares
Sums of two squares thin out to a share of nought, and yet the gaps between them stay short. Take the largest square below any number; what is left over is small, and a small number is always close to a square. Two squarings in a row say the next sum of two squares is never more than about 2√2 times the fourth root of n away — a bound proved in 1947 that nobody has improved, sitting far above every gap anyone has found.
A fraction on the circle forces a whole point
If a number is a sum of two squares of fractions, it is a sum of two squares of whole numbers. Draw the circle, mark the rational point, join it to the nearest lattice point and follow the line to where it meets the circle again: the new point is rational too, with a smaller denominator. Repeat, and the denominators fall until they reach one. The argument needs no primes at all — only the fact that every point of the plane is within distance one of the lattice.
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.
The prices nobody can break away from
When houses are sold to buyers who value them differently, there is a whole range of prices at which nobody wants to walk away, and it has a remarkable shape — one corner best for every buyer at once, one best for every seller at once, and the buyers' corner pays each buyer exactly what the market would lose without them.
Points on a lattice that see almost nothing
Average a function over the points of a carefully tilted lattice and the error can fall like one over the square of the number of points — far faster than random sampling, and faster than the most evenly spread sequences. The reason is that a lattice rule is blind to only a thin set of frequencies, its dual lattice, and a smooth periodic function has almost nothing there.
How many pairs can be one apart
Place n points in the plane and count the pairs exactly one unit apart. A square grid with its spacing as the unit gives two pairs per point; the same grid with the unit chosen as a length it realises in many directions — the square root of 5, of 25, of 65, of 325 — gives three, five, eight. Counting points on circles caps the total at a constant times n to the four-thirds. Between that cap and the grids the truth has not moved since 1984, and at every size anyone can draw, the two look alike.
Which way a prime's two squares point
A prime one more than a multiple of four is a sum of two squares in exactly one way, and the two squares make a point on a circle. Draw that point for every such prime and ask which way it faces. It faces every way equally — the angles spread evenly over the sector, which Hecke proved by giving each angle a remainder and copying Dirichlet. Measured over seventy-four thousand primes, they are even more evenly spread than random angles would be.
![Primes in five thousand thin sectors. 581517 primes in (2e7, 4e7] in 4967 sectors; mean 117.08, variance ratio 0.874, 2 empty.](/f/primes-in-five-thousand-thin-sectors-90657fc7.svg)
Sectors that shrink with the primes
Hecke proved that the angles of the primes a² + b² are evenly spread, so every fixed sector eventually gets its share. Let the sector shrink as the primes grow, to width X^(−α), and the question is open beyond small α. Measured on the 581,517 such primes between twenty and forty million, wide shrinking sectors fluctuate far less than chance and thin ones as much as chance — and the thin sectors that go empty are not scattered: they gather beside the directions of small rational slope, most of all slopes like 1/3 and 1/1 whose two terms are both odd.
Three coordinates and a fourth power
The Heisenberg group is made of triples of whole numbers, and two moves generate all of it. Count the triples within r moves of the start and the count grows like r⁴, not r³: at forty-four moves there are 1,600,703 of them, against 117,569 for the cubic lattice. The fourth power comes from one coordinate that the moves reach by enclosing area, so that height costs only the square root of itself — and seen from far away, the ball of reachable triples is a curved solid with a dimple at each pole.
No way to hand out true and false
Birkhoff and von Neumann read the propositions of quantum mechanics as subspaces, with "and" the intersection and "or" the span. Three lines in a plane already break the distributive law. Kochen and Specker proved something stronger: the propositions cannot be called true and false at all, if every complete measurement is to have exactly one true outcome. Cabello's eighteen directions in four dimensions show why in one line of arithmetic — nine bases, each direction in two of them, and nine is odd — and a search of all 262,144 assignments confirms it.
A wave known only at its ticks
Read a sine wave nine cycles a second at ten instants a second and the readings describe a wave of one cycle a second instead. Read a wave with nothing faster than 3.7 cycles a second at more than 7.4 instants a second and the readings determine it exactly. Both facts are the same fold of the frequency axis, and it is why wagon wheels turn backwards on film.
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.
A grid that packs the copies
Sampling a pattern on a grid makes copies of its frequencies, one for every point of a lattice, and the pattern can be read back from the samples only if the copies do not collide. For a pattern whose frequencies fill a disc the square grid wastes room between its copies. Searching every lattice of samples for the fewest that work finds a nearly hexagonal one every time — 124 samples where the square grid needs 169 — and the saving is the hexagonal packing's over the square, 13.4% in the limit. In three dimensions it is 29%, and in twenty-four the cubic grid needs 16,777,216 times as many samples as the best.
The second letter breaks the pattern
In one letter the constructive logic has infinitely many formulas, but they climb in a column two wide, four new ones for every step a state of knowledge can take. Add a second letter and the pattern is gone: sixteen formulas at the last step, 265,454 one step back, and more than two to the power 265,428 one step further. Every one of those is a genuine formula, and the reason the two-letter lattice has never been drawn is that each layer of the model is about as large as the number of formulas the layer above can tell apart.
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.
How many stable matchings a market has
A market with random preferences on both sides has not one stable matching but many — a few at ten a side, a few dozen at a hundred, about a thousand at a thousand — and all of them are reached from the proposers' best by a chain of rotations. Boris Pittel proved that the average grows like n ln n / e. The averages measured here sit at a third of that at every size a computer can reach.
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 market with the most stable matchings
Random preferences give a sixteen-a-side market about five stable matchings. Nesting a two-a-side market inside itself gives the same size 195,472, every one of them listed. That construction is forty years old and nothing has beaten it, while the ceiling above it has fallen from 2¹⁷ⁿ to 3.55ⁿ. The truth lies somewhere between 2.28ⁿ and that.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchModular arithmeticNormSums of two squaresCounting two waysGaussian integersGolden ratioGrowth rateInvariantPrimesStable matchingUnique factorisation