Hilbert curve, understanding the original article

Question

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)

Answer 1

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.

Answer 2

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.

Answer 3

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.