A path that fills a square

In 1877 Georg Cantor wrote to Richard Dedekind that he had found a one-to-one correspondence between the points of a segment and the points of a square, and added, famously, that he saw it but did not believe it. The correspondence interleaves decimal digits, as a line with as many points as a square describes, and it is wildly discontinuous: two numbers that agree to a hundred places can be sent to points on opposite sides of the square. Dedekind’s reply put the question that mattered. Counting points could not see dimension, but perhaps continuity could. Two years later Eugen Netto proved that no correspondence between segment and square can be one-to-one and continuous in both directions.

That left a gap, and in 1890 Giuseppe Peano filled it from the side nobody expected. He gave up only one of the two demands — that the correspondence be one-to-one — and kept continuity. His curve is a continuous function from the interval $[0, 1]$ onto the whole of the unit square: a pen moving without lifting for one unit of time that passes through every point. Peano gave it as a formula in base-three digits, with no picture at all. A year later David Hilbert drew one, and the drawing is the proof.

Four squares, threaded in order #

Cut the unit square into four quarters and visit their centres in the order bottom-left, top-left, top-right, bottom-right: an upside-down U. That is stage 1. For stage 2, cut each quarter into four again and thread the sixteen small squares so that each quarter is traversed by a reduced copy of the U, turned so that it enters where the previous quarter left off and leaves next to where the next one begins. The first quarter’s copy is reflected in the diagonal, so that it starts at the bottom-left corner and ends at the top of its quarter; the middle two are upright; the last is reflected in the other diagonal. At every later stage the same rule applies inside every square: replace it by four, threaded by a turned copy of the pattern.

Stage $n$ is a polygon through the centres of $4^n$ squares of side $2^{-n}$, each joined to the next by a step of length $2^{-n}$ across a shared side. The figure shows the first three stages and the sixth, which is already a dense mesh of 4,095 steps. As shapes, the polygons do not converge to anything that looks like a curve. What converges is something else: the polygons regarded as functions.

To make them functions, give each polygon a clock. Stage $n$ starts at time 0 and finishes at time 1, and spends equal time on each of its $4^n$ squares, so it passes through the centre of square number $k$ at time $(k + \tfrac12)/4^n$ and moves at constant speed between centres. Call the resulting function $H_n$, a continuous map from $[0, 1]$ to the square. Every $H_n$ is continuous, and so a question of exactly the kind that opened the essay on limits that forget to be continuous arises: does $H_n(t)$ settle for each $t$, and if so, is the limit continuous?

A uniform limit, used to build #

The answer is in the largest distance between consecutive stages, taken over all times at once. Pass from stage $n$ to stage $n + 1$ and look at where the two polygons are at the same moment $t$. During the interval of time that stage $n$ spends in one of its squares, stage $n + 1$ spends the same interval inside the same square, wandering through its four sub-squares. So the two can never be further apart than roughly the size of a square at stage $n$ — a distance proportional to $2^{-n}$.

The computation is sharper than the estimate. Sampling every parameter at a resolution finer than either polygon’s vertices, the largest gap between stage $n$ and stage $n + 1$ is $0.2253$ for $n = 1$, $0.1127$ for $n = 2$, $0.0563$ for $n = 3$, and so on down to $0.0035$ at $n = 7$: exactly $0.4507 \times 2^{-n}$ each time, to four figures. The polygons are self-similar, so the worst moment at one stage is a scaled copy of the worst moment at the last.

That one number is the whole of the analysis. The distances halve, so for any later stages $m > n$ the triangle inequality gives

$$\sup_t |H_m(t) - H_n(t)| \le \sum_{j = n}^{m - 1} 0.4507 \times 2^{-j} < 0.9014 \times 2^{-n},$$

which tends to nothing as $n$ grows, whatever $m$ is. The sequence is uniformly Cauchy. For each $t$ the points $H_n(t)$ form a Cauchy sequence in the square and converge to some point $H(t)$, and the convergence is uniform in $t$. Then the theorem that the first essay on uniform convergence proved — a uniform limit of continuous functions is continuous — applies, and $H$ is continuous.

There is a pleasing reversal in that. The theorem was introduced as a safeguard, the condition under which limits do not misbehave, and the examples around it were all of things going wrong without it: the powers $x^n$ settling on a function with a jump, functions close in height and nowhere close in slope. Here it is used constructively, to manufacture an object whose existence most nineteenth-century mathematicians would have denied. The limit inherits continuity from the polygons and inherits nothing else they had, not their finite length and not their corners.

Why every point is reached #

Continuity was the hard half for Netto’s theorem; for Hilbert’s curve the surprising half is that the limit is onto. The reason is built into the clock. Stage $n$ spends the time interval $[k/4^n, (k + 1)/4^n]$ inside square number $k$, and so does every later stage, since each later stage subdivides the same interval among the same square’s pieces. The limit therefore sends that whole time interval into the closed square number $k$.

Now take any point $p$ of the unit square. It lies in some square of the first stage, in some square of the second stage inside that, and so on: a nested sequence of closed squares shrinking to $p$, and a matching nested sequence of closed time intervals. Nested closed intervals of lengths $4^{-n}$ shrink to a single time $t$. For each $n$ the point $H(t)$ lies in the stage-$n$ square containing $p$, because $t$ lies in that square’s interval, and those squares shrink to $p$. So $H(t) = p$. Every point is reached.

The figure shows the first two levels of that bookkeeping. The parameter is cut into sixteen equal intervals and the square into sixteen equal squares, and the stage-5 polygon’s vertices from the $k$-th interval all land in the $k$-th square — 64 vertices in each, every one checked. The shading matches, and it matches at every finer level in the same way.

The same bookkeeping proves something stronger. A union of time intervals of total length $L$ is sent onto a union of squares of total area $L$, at every level of subdivision, so the curve preserves measure: the set of times at which $H$ is in a region has length equal to the region’s area. A pen running at Hilbert’s schedule spends a quarter of its time in each quarter of the square, a sixteenth in each sixteenth, and in the limit it spends exactly as long in any region as that region’s area. The curve is not merely onto. It covers the square evenly, in the sense that a measure can detect.

Two coordinates, each a monster #

Write the curve as two ordinary functions, $H(t) = (x(t), y(t))$. Each is a continuous real function on $[0, 1]$, and the figure shows both. They are the kind of graph Weierstrass’s corner-everywhere function introduced: rough at every scale, each made of four smaller copies of itself, reflected and rescaled.

Neither has a derivative at any point. The reason is a size argument. In a time interval of length $h$ the curve covers a region of area $h$, so it must move a distance of order $\sqrt h$ — which, for small $h$, is enormously more than $h$. A function whose increments over intervals of length $h$ are of size $\sqrt h$ cannot have a finite slope: the difference quotient grows like $1/\sqrt h$. To turn that into a proof at every single point one uses self-similarity to show that, at every point and every scale, some nearby time sends the curve a distance of order $\sqrt h$ away in at least one coordinate. The details are fiddly; the area argument is the reason.

The two graphs also show the large-scale structure. During the first quarter of the time, both coordinates stay at or below one half: the curve is in the bottom-left quarter. At $t = \tfrac14$ the curve is at the middle of the left side, $(0, \tfrac12)$, which the figure’s construction checks. At $t = \tfrac12$ it is at the centre of the square, and at the end it arrives at the bottom-right corner. In between, each coordinate takes every value between 0 and 1 many times over, in the way a function filling a square must.

This explains, too, why no smooth curve can fill anything. A differentiable path has a bounded slope over any closed interval on which its derivative is continuous, so in time $h$ it moves a distance of order $h$, and its image can be covered by about $1/h$ discs of radius $h$, of total area of order $h$. As $h$ shrinks that area vanishes: smooth curves have area zero. Filling a square forces exactly the roughness the coordinates display.

Exactly half an exponent #

The area argument says how close two times can be and still send the curve far apart. Put it as a ratio. If the curve moves a distance $d$ in a time $h$, then

$$\frac{|H(s) - H(t)|^2}{|s - t|}$$

compares squared distance with elapsed time, and the area argument says this ratio can be large but not unboundedly so. That is the content of the statement that $H$ is Hölder continuous with exponent one half: there is a constant $C$ with $|H(s) - H(t)| \le \sqrt{C |s - t|}$ for every pair of times.

The figure measures $C$. Take every multiple of $1/3072$ as a time — 3,073 of them, so about 4.7 million pairs — and compute the ratio for every pair. Grouped by the size of the gap, the largest ratios run between about 3 and 6 for every gap from the smallest up to a quarter of the interval, with no trend with scale, which is what self-similarity predicts; only gaps comparable to the whole interval give smaller ratios, down to about 1.3 for the very largest — and to exactly 1 for the two ends, which are one unit apart and one unit of time apart. The largest of all is $5.998$, at $s = 1472/3072 = 23/48$ and $t = 1600/3072 = 25/48$.

Those two times can be followed exactly. They straddle the halfway point, one twenty-fourth apart. At $t = \tfrac12$ the curve is at the centre; just before, it is finishing the second quarter, and just after, starting the third. In base four, $23/48 = 0.1322\ldots$ with the 2 repeating, and following the digits through the construction puts the curve at $(\tfrac14, \tfrac12)$; by symmetry $25/48$ goes to $(\tfrac34, \tfrac12)$. The two points are half a unit apart, so the squared distance is $\tfrac14$, and dividing by the gap of $\tfrac1{24}$ gives exactly 6. The computed $5.998$ differs only because the limit is approximated by a polygon of $4^{14}$ squares.

Tim Bauman proved in 2006 that 6 is the largest value the ratio takes for Hilbert’s curve anywhere, so the constant is exact. The exponent one half cannot be improved for any curve that preserves area: an interval of length $h$ fills a region of area $h$, and a region of area $h$ has diameter at least $2\sqrt{h/\pi}$ by the isodiametric inequality, so some pair of times $h$ apart lands at least that far apart. Every measure-preserving square-filling curve therefore has a ratio of at least $4/\pi \approx 1.27$, and Hilbert’s sits at 6.

The points it has to pass more than once #

Netto’s theorem forbids a continuous map from the interval onto the square that is one-to-one, and it is short enough to give whole. If such a map existed, it would be a continuous bijection from a closed interval, which is compact, onto the square, and such a map is automatically a homeomorphism: its inverse is continuous too. Remove any interior time $t$. The interval falls into two pieces. The square with the single point $H(t)$ removed is still in one piece. A homeomorphism cannot turn one piece into two, so the map was not one-to-one after all. Some points must be reached more than once.

The counting can be done exactly for points on a grid. A point lies in one, two or four closed squares of a given stage, depending on whether it is inside a square, on a side or at a corner. Each such square is the image of one time interval, so the point is reached once in each interval — but two consecutive intervals share an endpoint, and if the curve passes from one square to the next through the point itself, the two visits are the same. So the number of times the point is reached is the number of separate runs of consecutive intervals among the squares that contain it, counted at a fine enough level that the runs stop changing. For the 289 points whose coordinates are multiples of $\tfrac1{16}$, the counts are the same at stage 10 as at stage 12, and they are striking: 34 points reached once, 71 twice, 143 three times and 41 four times.

No point is reached five times, and none can be, since no point lies in more than four closed squares of one size. All 34 points reached only once lie on the edge of the big square, where there is less room to come back; every one of the 225 grid points inside it is reached at least twice, because each lies on a line between squares that the curve visits at widely separated times. The centre itself, where the curve passes at $t = \tfrac12$, is reached three times. That the multiple points are so common on the grid is an artefact of choosing grid points; a point chosen at random is reached exactly once with probability one, since the multiple points lie on the countably many grid lines and form a set of area zero. The square is filled almost injectively, and the failures sit exactly where Netto’s theorem says they must.

Length, dimension and what continuity cannot carry #

Each stage of Hilbert’s polygon has $4^n - 1$ steps of length $2^{-n}$, so its length is $2^n - 2^{-n}$, doubling every stage. The limit has no finite length at all, and in the sense the essay on which curves have a length made precise, it is not rectifiable on any interval of time however short. That was inevitable: a curve of finite length can be covered by small discs of total area as small as one likes, which is the smooth-curve argument above with the derivative removed.

The deeper lesson is about dimension. Cantor’s correspondence showed that counting points cannot distinguish a segment from a square; Hilbert’s curve shows that continuous maps cannot either, if they are only required to go one way. A continuous image of a one-dimensional object can be two-dimensional. What does preserve dimension is a continuous map with a continuous inverse, which is why the theorem that a closed curve cuts the plane in two and nothing smaller cuts space needs homeomorphisms and not mere continuous maps. Dimension became a topological invariant only once mathematicians stopped asking it of the wrong class of maps — the outcome of exactly the dispute that Cantor’s letter and Peano’s curve started.

The limit is also a meeting point of two kinds of fractal dimension. The image is the full square, of dimension 2. The graph of each coordinate is a fractal curve in the plane, and the box-counting dimension of such a graph, for a Hölder function of exponent one half that is as rough as it can be, is $2 - \tfrac12 = 1.5$ — the same calculation that gives a dimension that is not a whole number to the coastlines and snowflakes. The rough graph and the full square are two views of the same half-exponent.

Other ways to fill a square #

Hilbert’s is not the only construction, and comparing it with the others shows which of its properties are forced and which are choices. Peano’s original curve divides the square into nine sub-squares rather than four and threads them in a zigzag, base three in place of base two; it too is a uniform limit of polygons, it too preserves area, and it too is Hölder of exponent one half, with a different constant. Any construction that assigns each piece of the parameter to a piece of the square of the same measure, at every scale, and keeps consecutive pieces adjacent, gives a continuous, area-preserving, nowhere-differentiable filling curve by exactly the argument above. What varies between them is the constant and the pattern of points visited more than once.

There are other curves with the same property. Henri Lebesgue’s of 1904 is defined on the Cantor set, by reading alternate binary digits as two coordinates, and filled in by straight segments across the gaps. It is continuous and onto, like Hilbert’s, but it is differentiable almost everywhere — the straight pieces carry all of the length of the interval, and the filling happens on a set of length zero. Smoothness almost everywhere and filling a square are compatible; what they are not compatible with is smoothness everywhere, or measure preservation, which Lebesgue’s curve gives up.

Polygons standing in for the limit #

None of the figures shows the limit. Every drawing is a polygon at some finite stage, and the limit curve, which passes through every point of the square, would look like a solid grey square — that is, like nothing at all. The proof that it fills the square is the nested-squares argument, not any picture; the pictures show only that each stage stays close to the last, that time intervals map into their squares, and that the ratio of squared distance to elapsed time is bounded on a finite grid of times.

The counts of points reached once, twice, three and four times are for one grid of 289 points and rest on runs that stopped changing between two levels of refinement. That stability is evidence for the counts, and the upper bound of four is a proof, but the census says nothing about how often points off the grid are reached. Likewise the ratio $5.998$ is a maximum over 4.7 million pairs, not a supremum: the exact value 6 comes from following the two parameters through the construction and from Bauman’s theorem, not from the scatter.

Computed in squares, quoted from Bauman #

Computed here: the polygons up to stage 6 as drawn, with each square visited once and every step a shared side; the largest gap between stages 1 and 8, equal to $0.4507 \times 2^{-n}$ in each case; the containment of the stage-5 vertices in their squares; the coordinate functions from a polygon of $4^{14}$ squares; the ratio over every pair of 3,073 times, peaking at the pair $23/48$ and $25/48$; and the preimage counts on the sixteenths grid at stages 10 and 12. The identification of the peak points as $(\tfrac14, \tfrac12)$ and $(\tfrac34, \tfrac12)$ agrees with the computed images to within $5 \times 10^{-5}$.

Quoted: the histories of Cantor, Dedekind, Netto, Peano and Hilbert; Bauman’s theorem that 6 is the exact supremum; and Lebesgue’s curve and its differentiability almost everywhere. The nowhere-differentiability of the coordinates is sketched here and not proved in full.

Still open: the least ratio a filling curve can have #

Hilbert’s ratio of 6 is exact, and the lower bound of $4/\pi$ for any measure-preserving square-filling curve follows from the area argument above. Between them is a gap. Better lower bounds are known than the simple one here, and curves with ratios below Hilbert’s have been designed, but the least value the ratio can take for a continuous measure-preserving map of the interval onto the square is not known. The answer depends on which distance is used, and the question has been studied separately for the Euclidean distance, the largest coordinate difference, and the sum of the differences.

The three-dimensional version is more open still. A cube can be filled by curves built the same way, eight sub-cubes at a time, and there are a very large number of essentially different ways to thread eight cubes and turn the copies. Which of them keeps neighbours closest, in the sense of the ratio $|H(s) - H(t)|^3 / |s - t|$, has been explored by search rather than settled by proof.

Filling by halving #

Hilbert’s curve exists because consecutive polygons never differ by more than $0.4507 \times 2^{-n}$, so their limit is uniform, so it is continuous; it fills the square because every interval of time is assigned its own square at every scale. The same assignment makes it preserve area, makes it Hölder of exponent one half with constant exactly 6, and forbids it from being one-to-one, so that grid points are reached up to four times.

The construction answers Dedekind’s question in the way he did not expect. Continuity alone does not protect dimension; a one-dimensional parameter can paint a two-dimensional region, provided it moves fast enough — distance $\sqrt h$ in time $h$ — and gives up both smoothness and injectivity to do so. What protects dimension is continuity in both directions, and the theorem of uniform convergence, introduced to keep limits well behaved, is exactly the tool that builds the counterexample showing why both directions are needed.