# Hilbert curve, understanding the original article

I'm trying to read and understand the article in which Hilbert gave an illustration of a space filling curve, namely "Ueber die stetige Abbildung einer Linie auf ein Flächenstück". It's only a short 2 page paper, but me being not the best mathematician, I'm not able to fill in the gaps left in the explanation.

This is the three figures available in the paper, below, I give my translation of the relevant piece of text.

"We take a line segment of length 1 and divide it up into 4 pieces of equal length. We then take a unit square and divide it by means of two perpendicular lines into 4 equal quadrants marked 1,2,3,4 (Fig 1). Next, we divide each piece on the line segment into four equal pieces, yeilding 16 pieces; at the same time, we also divide each of the quadrants into equal quadrants, and write the number $1, 2, 3,\ldots, 16$ in the 16 resulting quadrants, where the ordering of the quadrants is to be chosen so that each quadrant shares a side with it's predecessor (Fig 2). If we take this process further - Fig. 3 illustrates the next step - it can easily be seen that to each point on the line, we can assign a singular point in a quadrant. All we need to do is to mark the piece of the segment that contains the point. The quadrants with the same numbers lie necessarily within each other and enclose in the limit (or "on its border", orig. "in der Grenze") a point of the unit square."

Now, I have several issues with this, namely:

• I do not understand how the first bold part gives an unambigous definition of the curve. Even if I follow the transitions between quadrants from fig 1 and fig 2, I can still come up with a different ordering (curve) for fig 3 (assuming the recursive nature of the definition), see the red line on the picture below. Notice that it's not even symmetrical (although it could be if I ordered the bottom right (last four) quadrants differently). Where did I go wrong here? (I understand there are other ways to define the curve, such as L-Systems, I'm just curious about this specific definition)

• The second thing I do not understand is the second bold part. I can se how he maps intervals on the segment to quadrants, and that in the limit, the quadrants become points, as do intervals on the line. Intuitively, this is clear. However, what I do not understand is the part about quadrants with the same numbers being contained within each other; I'm, however, not all that sure about my translation being correct here.

Any other explanations welcome! I do have a little math background, but I am not a mathematician. I'd just like to convince myself about the correctness of the definition; pardon the inevitable lack of rigor.

thank you!

PS: the original paper, in German, can be found online here (pages 2-3) or at pages 94-95 of Chaos and Fractals: New Frontier of Science by Peitgen, Jürgens, and Saupe.

PPS: Here's the Springer link to Hilbert's paper (may be behind a pay wall)

• I included the images for you and added a link to the original paper. You should now be able to post the link you had in mind. (you can also add the links as a comment)
– t.b.
Jul 22 '11 at 13:47
• @Theo Buehler Thanks! Can't save an edit with the images; The original article can be found on pages 2-3 of this PDF Jul 22 '11 at 13:55
• Okay, I included that information as well and some further links. I assume that you'll get a second upvote for this question soon and then you'll be able to edit your post again.
– t.b.
Jul 22 '11 at 13:59
• I admit that I don't understand how Hilbert defines the curve recursively. I can see that at each given step of the construction, the curve may intersect each square in at most $10$ different ways (horizontal or vertical 'full cuts', left, right, up or down 'half cuts', and four kinds of 'corner cuts') and that you only need to specify how to modify each of these cases as you move to the next step of the construction, but he seems to take another approach. Jul 23 '11 at 1:09
• But even this is not true, as when passing from $4$ to $16$ squares, there are two vertical 'half cuts' that transform differently... Jul 23 '11 at 1:11

I am not sure about the first part, maybe there's some implicit assumptions used (maybe that the line segment must start from the bottom left corner and end at the bottom right corner or something like that).

For your second question, though, the idea is this: consider the set of all points that are not of the form $\frac{n}{4^k}$ for positive integers $n,k$ with $n < 4^k$, call it $G$.

Fix one such point $x$. Then at any step of the division of the unit interval (0,1) into sub-quadrants, such $x$ will lie in the interior of one of the quadrants (since the end points are of the form $n/4^k)$. So we can construct a nested sequence of intervals for each $x\in G$, by defining $I(k;x) = [(n-1)/4^k, n/4^k]$ where $n$ is chosen such that $x\in I(k;x)$.

And let $N(k;x)$ be the positive integer $n$ chosen in the definition of $I(k;x)$. Observe that by construction, $4N(k-1;x)-4 < N(k;x) \leq 4N(k-1;x)$.

Observe that by this construction, $I(k+1;x) \subset I(k;x)$.

Now, let $Q(n,k)$ be the $n$th quadrant of the square exhibited in the $k$'th step of the construction. Using the recursive nature of the construction, you have that $Q(n,k) \subset Q(m,k-1)$ iff $4(m-1) < n \leq 4m$.

Hence we have that for any fixed $x$, the sequence $N(k;x)$ gives rise to a sequence of squares $Q_k(x) := Q(N(k;x),k)$ with the property that $Q_k(x) \subset Q_{k-1}(x)$.

So the "same number" is the number $x$. The statement that the "Quadrants of the same number contains each other" is the above paragraph, where for each $x\in G$ you obtain a decreasing sequence of squares.

Observe also that if you take $H$ to be the subset of the unit square such that neither of the two coordinates are of the form $n/ 2^k$, for each $y\in H$ you can analogously define a decreasing sequence of squares $Q(k;y)$ and their associated numbers $M(k;y)$. This sequence allows you to map to each $y\in H$ a decreasing (nested) sequence of intervals which you can use to determine the corresponding point in the unit interval.

• thanks, if $x$ is what is meant by "same number", then that makes sense; as for the part under the horizontal rule, by "decreasing sequence of squares"? (I assume you mean nested squares $Q(k;y)$ and a not necessarily decreasing sequence of their numbers $M(k;y)$) Jul 23 '11 at 13:33
• Ah yes, sorry about the jargon. In analysis when we say a decreasing and increasing sequence of sets, we mean decreasing and increasing with regards to the inclusion operator. So a decreasing sequence of sets is $\Omega_1 \supsetneq \Omega_2 \supsetneq \Omega_3\cdots$ Jul 23 '11 at 14:12

I think the following method yields correct results. Suppose your curve constructed at the $n$-th generation ($n$ starts at $n=1$), that is, you have already constructed a curve for when the square has been subdivided into $4^n$ squares. The curve defines a linear order on the set of those $4^n$ squares by saying that the first square is the one in the bottom left corner and, starting there, following the curve along its path. This is the ordering Hilbert considers.

Take any square from your collection of $4^n$ squares, say it's square number $k\in\lbrace 1,\dots,4^n,\rbrace$, cut it into $4$ equal squares, and draw the square that connects the centers of these smaller squares. This square we can call the "$k$-th central square" (of generation $n$). This gives you $4^n$ central squares.

Here's how you're going to modify the curve to get to the $(n+1)$-th generation. We're going to draw what it does one (generation $n$) square at a time (so there'll be $4^n$ steps).

• $k=1$ : your new curve starts on the bottom left vertex of the $1$-th central square, must travel along the $1$-th central square, visit all $4$ vertices of the $1$-th central square (but only $3$ of it's edges), and end at one of the two vertices of the $1$-th central square that's closest to the $2$-th square (I'm deliberately not saying 'first square' or 'second square'). Now you draw the line connecting this last vertex to the directly opposite vertex in the $2$-th central square.

A drawing or intuition should convince you there is exactly one such path. This way you've constructed a curve that visited all $4$ vertices of the $1$-th central square and "connected" the $1$-th square to the $2$-th square, and ended on a vertex of the $2$-th central square.

• If $2\leq k\leq 4^{n}-1$ : Suppose you've already constructed a curve that connects the $1$-th square to the $k$-th square, and ended on a vertex of the $k$-th central square. The generation $n$ curve connects square $k$ to square $k+1$. The generation $(n+1)$ curve will also connect square $k$ to square $k+1$. Just ask that it travel along the $k$-th central square, visit all $4$ vertices of that central square (but only $3$ of its eges), and end at one of the $2$ vertices of the $k$-th central square that are closest to the $(k+1)$-th square. You then connect this final vertex to the directly opposite vertex in the $(k+1)$-th central square.

Again, there is only one such path. This curve "connects" the $1$-th square to the $(k+1)$-th square, and ends on a vertex of the $(k+1)$-th central square

• When $k=4^n$, you still need to draw a couple of lines. You've got a curve that connects the $1$-th square to the $4^n$-th square, and ends on a vertex of the $4^n$-th central square. You simly demand that it travel along the $4^n$-th central square, visit all its vertices and eends at the bottom right vertex.

The only thing that remains to be checked is that this final path indeed exists, that is, that you're not entering the $4^n$-th central square at its top left vertex, but this should follow from the (intuitively evident) fact that the construction above yields a path that is symetric with respect to the central vertical axis.

• again, thanks; your are right that if the endpoints are fixed at the corners like you said and (not sure if that is obvious from your description) the connection rule works recursively (if we make sure that for two quadrants $Q_i,Q_j$ ordered after each other ($|i-j|=1$) at level $n$, there is going to be (exactly) one connection between their $4 + 4 = 8$ child quadrants at level $n+1$), we should indeed get a unambigously defined curve. Jul 23 '11 at 13:41

As an illustration of the reasoning in the answer by Willie Wong, take the point $p = 1/3\in [0, 1]$.

Since $1/4 < 1/3 < 2/4$, in the first step of the construction, $p$ is inside the piece $2$ of the interval so it is mapped to the quadrant numbered $2$.

Since $5/16 < 1/3 < 6/16$, in the second step, $p$ is inside the piece $6$ of the interval so it is mapped to the quadrant numbered $6$.
Note that the quadrant $6$ of the second step is inside the quadrant $2$ of the first step.

Since $21/64 < 1/3 < 22/64$, in the third step $p$ is mapped to the quadrant numbered $22$.
Note that the quadrant $22$ of the third step is inside the quadrant $6$ of the second step.