A grid that packs the copies

A wave known only at its ticks explained sampling on a line. Reading a wave at evenly spaced instants folds its frequencies onto a short interval, so that a frequency and every frequency differing from it by the sampling rate give the same readings; a wave with nothing faster than half the sampling rate fits inside the fold and is determined exactly by its samples. Its last section turned to patterns of two variables — images, fields, anything that varies across a plane — and said that there the square grid is not the best grid. A pattern whose frequencies fill a disc can be sampled about 13% more cheaply on a hexagonal grid.

This essay checks that claim by exhaustion rather than taking it from a theorem. For patterns made of finitely many waves it is possible to try every lattice of sample points, in order of size, and find the smallest that determines the pattern. The search finds the hexagonal grid without being told to look for it; it finds the saving, and something more, because the reason is a question about packing discs, and in higher dimensions the packing question has answers that make the square grid look not slightly wasteful but absurd.

Copies of the frequencies, one for every lattice point #

The setting is a pattern on a square that repeats across its edges, like a tile, so that its waves have whole-number frequencies in each direction: a wave $e^{2\pi i (k_1 x + k_2 y)}$ for each frequency vector $k = (k_1, k_2)$. Where the coefficients come from found each wave’s amount by averaging the pattern against that wave over the whole square. A pattern is band-limited to a disc when every frequency it uses lies within distance $W$ of the origin. With $W = 6$ there are 113 such frequencies, the green dots of the hero figure, and the pattern is a sum of 113 waves.

Now replace the whole square by a finite set of sample points, chosen to form a lattice that repeats with the square. There is a matching lattice in the frequency plane, written $L^*$ here, consisting of the frequency vectors that look like the constant wave at every sample point. Two frequencies whose difference lies in $L^*$ then agree at every sample point, and no set of samples on that grid can tell them apart — exactly the folding of the one-dimensional essay, where $L^*$ was the multiples of the sampling rate. Each frequency has a whole lattice of impostors, shifted from it by the vectors of $L^*$, and the hero figure draws those copies of the disc round the original.

On an infinite plane, without the repetition, the frequencies would fill a continuous disc rather than a set of dots, and when the period grows without bound described how the series becomes a transform in that limit; the copies and the collisions are the same, and the tile is only what makes them countable. In one dimension the picture is the one a square wave built entirely out of round ones began with — a row of harmonics — folded back on itself at the sampling rate.

The rule follows at once. The samples determine the pattern exactly when no two of its frequencies are impostors of each other, which is to say when no copy of the disc lands on a frequency of the disc itself. When that holds, each wave’s amount is recovered by the same averaging as before, done over the samples instead of the whole square. The number of samples is the number of copies’ worth of room each copy takes up — the size of $L^*$'s basic cell — so a grid is economical exactly when its copies pack tightly without colliding.

The square grid leaves gaps #

The square grid with $m$ points along each side has copies on the square lattice of spacing $m$. The disc of radius 6 spans 13 whole numbers from $-6$ to $6$ along its axis, so a copy shifted by less than 13 would land on it: the square grid needs $m = 13$, and $13 \times 13 = 169$ samples, for a pattern of 113 waves. In the hero figure its copies sit at the corners of squares, touching along the axes and leaving large empty regions at the diagonals, where four discs leave a gap no disc can use.

That gap is the waste. A grid of samples pays for every frequency position in its basic cell, used or not, and the square grid’s cell is a square drawn round a disc. The question is whether some other lattice packs the copies more tightly, and for two dimensions the answer is the same as for coins on a table: arranged in rows offset by half a coin, each coin touching six others, they cover $\pi/\sqrt{12} \approx 90.7\%$ of the table, against $\pi/4 \approx 78.5\%$ in the square arrangement.

Searching every lattice #

Every lattice of sample points that repeats with the square corresponds to a lattice $L^*$ of whole-number frequency vectors, and every such lattice has a unique description by three whole numbers in what is called Hermite normal form: rows $(a, 0)$ and $(b, c)$ with $0 \le b < a$, and $a c$ samples. That makes an exhaustive search possible. For each number of samples $N$, starting from the number of frequencies, try every $a$ dividing $N$ and every $b$, and check whether any non-zero vector of the lattice is a difference of two frequencies in the disc. The first $N$ with a lattice that passes is the fewest samples that can determine every pattern of that band.

For the disc of radius 6 the search stops at 124 samples, against the square grid’s 169 and the 113 frequencies that are a hard minimum, since each wave needs at least one sample to pay for it. At radius 14 the 613 frequencies need 673 samples on the best lattice and 841 on the square grid. The ratio of samples to frequencies on the best lattice settles near $1.10$, and on the square grid it falls slowly towards $1.27$.

Those limits are the packing densities turned upside down. A disc of radius $W$ has area $\pi W^2$, close to the number of frequencies in it, and its copies need a cell of area $4W^2$ in the square arrangement and $2\sqrt3\, W^2$ in the hexagonal one, since the hexagonal lattice with shortest vector $2W$ has a cell of that area. So the samples per frequency approach $4/\pi = 1.273$ and $2\sqrt3/\pi = 1.103$, and the saving approaches $1 - \sqrt3/2 = 13.4\%$. For small discs the measured saving is larger — 27% at radius 6 — because a disc of whole-number points has ragged edges, and the square grid pays for its full width along the axes while the best lattice can tuck its copies’ corners into each other’s gaps.

The winners are hexagonal #

The search returns a particular lattice for each radius, and nothing in it asked for any particular shape. The shape can be read off by reducing the lattice’s basis — repeatedly replacing the longer of two vectors by its difference from a multiple of the shorter, until neither can be shortened — which leaves the two shortest independent vectors.

For a hexagonal lattice the two shortest vectors are equal in length and meet at 60°. The winners come close at every radius and closer as the disc grows: 68.5° at radius 3, 61.6° at radius 6, and from radius 10 on between 60.6° and 61.4°, with the two vectors’ lengths within two per cent of each other. At radius 10, for instance, the best lattice is spanned by $(20, 1)$ and $(-9, -18)$, of lengths 20.02 and 20.12, meeting at 60.6°. They cannot be exactly hexagonal, because their vectors have to be whole numbers and $\sqrt3$ is not a ratio of whole numbers, but they are the best whole-number approximations to it that the disc’s edge allows.

The hero figure’s lattice, for radius 6, is spanned by $(11, 4)$ and $(9, -8)$, of lengths 11.70 and 12.04 at 61.6°. Its copies of the disc nearly touch along three directions instead of two, and that is visible in the figure as the six neighbours each copy has, where the square grid’s copies have four. The shortest vector has to be long enough that a copy shifted by it misses every frequency of the disc, which for a disc of whole-number points of radius 6 means a length of at least about 11.7 rather than the 12 a continuous disc would demand: the ragged edge lets the copies interlock slightly, and that is part of why the small-radius savings exceed the limit.

The square lattice never wins at any radius tried. Nor does any rectangular one, for a reason worth stating: the disc reaches $\pm W$ along each axis, so a lattice with an axis-parallel side must make that side at least $2W + 1$, and with both sides axis-parallel it is the square grid. The saving needs the rows of samples to be offset, and the offset is what hexagonal packing is.

One pattern, two grids #

The theory says the 124 samples determine every pattern of 113 waves. The direct test is to make one, sample it, and rebuild it.

The pattern is a random sum of the 113 waves, with amplitudes falling gently with frequency, paired so that the result is real. Sampled at the 124 points of the best lattice, each wave’s amount is recovered by averaging the samples against that wave, and the rebuilt pattern matches the original to within $3 \times 10^{-15}$ of its size — the rounding error of the arithmetic. The samples lie on offset rows, visible as slanting lines in the middle panel, and there is nothing else special about them.

An 11 × 11 grid has 121 samples, three fewer, and the same averaging gives a pattern 23% wrong in root-mean-square. Its copies are spaced 11 apart, and a disc 13 frequencies across overlaps its neighbours along both axes; the waves at the edge of the disc are confused with waves at the opposite edge, and the rebuilt pattern carries their sum in both places. To succeed the square grid needs 169 samples, 45 more than the lattice uses. Nothing about the pattern prefers hexagons; the disc does, because a disc is round and a square is not.

Three dimensions, and the bodies that pack #

The same search runs in three dimensions, where the frequencies fill a ball and a lattice in Hermite normal form has six numbers. It is much slower, and only small balls can be searched exhaustively, but the outcome is the same in kind.

For the ball of radius 4, with 257 frequencies, the best lattice needs 333 samples and the cubic grid 729. For such small balls the counts are dominated by their edges, as in two dimensions, and the saving is larger than its limit. For large balls the limit is again a packing density. The densest packing of balls in space is the arrangement of oranges on a market stall, the face-centred cubic packing, filling $\pi/\sqrt{18} \approx 74\%$ of space against the cubic arrangement’s $\pi/6 \approx 52\%$, and Kepler’s guess that nothing does better was proved by Thomas Hales in 1998. When the copies of the ball are packed that way, the samples themselves sit on the dual lattice, the body-centred cubic lattice — a cube with an extra point at its centre — and that grid needs $1/\sqrt2$ of the cubic grid’s samples, a saving of 29.3%. Daniel Petersen and David Middleton set out this correspondence for every dimension in 1962, and it is why body-centred grids are used in volume rendering and in some three-dimensional imaging.

What the cube wastes in higher dimensions #

The correspondence holds in any number of dimensions: the best grid for a signal of $d$ variables band-limited to a ball is the dual of the densest lattice packing of balls in $d$ dimensions, and the cubic grid’s excess is the ratio of that packing’s density to the cubic packing’s.

The densest lattice packings are known in dimensions one to eight and in twenty-four, and each has a name. In four it is the lattice $D_4$, the points with whole coordinates and an even sum, which is the lattice of the integers among the quaternions up to scale; there the cubic grid needs exactly twice the samples. In eight it is $E_8$, the lattice of two hundred and forty directions, and the cubic grid needs sixteen times as many. In twenty-four it is the Leech lattice, and the ratio is exactly $2^{24}$: a cubic grid for a band-limited signal of twenty-four variables uses 16,777,216 samples for every one that a Leech-lattice grid needs.

The reason the waste grows so fast is the geometry of balls in many dimensions. A ball fills less and less of the cube round it — in twenty-four dimensions about one part in nine billion — and a cubic grid pays for the whole cube. Good lattices fit their balls into the corners of each other’s cubes, and in high dimension the corners are nearly everything. The same arithmetic is behind error-correcting codes, where sixteen spheres that fill a cube found a packing of binary words that wastes nothing at all.

What the search assumes #

The search is exhaustive only within its setting. The patterns repeat across the square, so the frequencies are whole-number vectors and the sample lattices must repeat with the square too; an infinite plane allows any lattice at all, including the exactly hexagonal one the searches here can only approximate. The band is a disc of whole-number points, not a continuous disc, so small radii have ragged edges and the measured savings run above the limit. And the comparison is between lattices: sample sets that are not lattices, and reconstructions that are not the plain averaging used here, are outside it. Some non-lattice sample sets do better than any lattice for particular bands, and their theory — Landau’s density bounds — shows that the number of frequencies is a floor no scheme can beat, a floor the best lattice comes within 10% of.

Still open: the best grid in other dimensions #

In every dimension other than one to eight and twenty-four, the densest lattice packing of balls is unknown, and so is the best grid for sampling a signal band-limited to a ball. The problem is not academic. Medical scanners sample in three dimensions and time, and the four-dimensional answer, $D_4$, halves the samples of the cubic grid; signals of more variables appear in physics simulations and in machine learning, and in dimensions 9 to 23 the best known lattices are good guesses without proofs. The searches above are the problem’s smallest cases, solved by trying everything; in dimension ten, the number of lattices in Hermite normal form grows like the ninth power of their size, and a search large enough to show the limit is far beyond reach.

There is a second question that the whole-number setting raises. The winners approach the hexagonal shape with a pattern of near misses — 60.6° at radius 10 and 61.4° at radius 12 — that depends on how well $\sqrt3$ can be approximated by fractions with small denominators, the subject of three gaps and no more and its relatives. A precise statement of how close the best whole-number lattice comes to hexagonal at each radius, and of how much extra it costs, would join sampling to the theory of rational approximation; the measurements here suggest it but do not prove it.

Packing the copies is sampling the pattern #

A grid of samples makes copies of a pattern’s frequencies on a lattice, and the grid works exactly when the copies do not collide. For a pattern whose frequencies fill a disc, the square grid’s copies leave gaps at their diagonals; searching every lattice, size by size, finds a nearly hexagonal one every time, with 124 samples where the square grid needs 169 for a pattern of 113 waves, and a pattern rebuilt exactly from those 124 samples is rebuilt 23% wrong from 121 on a square. In the limit the saving is the hexagonal packing’s advantage over the square, 13.4%; in three dimensions the body-centred grid saves 29%, and in twenty-four, where the copies can sit on the Leech lattice, the cubic grid needs $2^{24}$ times as many samples. In most dimensions the best grid is not known, because the densest packing of balls is not.