Why does the Hilbert curve fill the whole square?

Solution 1:

Looking at the pictures, the partial curves are obtained by joining the centres of smaller squares within the square. In the first step one divides the unit square into 4 squares of side $1/2$. Then each of these squares is divided again into $4$ squares, and so on. So the whole thing is reduced to the numbering of the successive subdivisions of the square: $f_n$ will be the curve obtained by joining the centres of the $4^n$ squares of side $2^{-n}$ according to the proper numbering scheme.

One can make the convention that $f_n:[0,1]\to[0,1]^2$, and we represent the part of the line corresponding to the $k^{\rm th}$ square using the interval $[(k-1)4^{-n},k\,4^{-n})$.

The numbering for the first $4$ squares (with sides $1/2$) is $1,2,3,4$ where $1$ is the lower left and then we proceed clockwise.

Given then $n^{\rm th}$ ordering, we obtain the $(n+1)^{\rm th}$ ordering in the following way: the $4^{n+1}$ squares are grouped in four main groups of $4^{n}$ squares corresponding to the four "quadrants" of the unit square ("first" quadrant is lower left, "second" quadrant is upper left, "third" quadrant is upper right, "fourth" quadrant is lower right). In each quadrant we will use the numbering from the $n^{\rm th}$ numbering, in the following way:

First quadrant: we take the $n^{\rm th}$ numbering, rotate it $90$ degrees clockwise and use reverse order.

Second quadrant: we take the $n^{\rm th}$ numbering in its original order (of course, replacing $1$ with $4^n+1$, $2$ with $4^n+2$, etc.

Third quadrant: we take the $n^{\rm th}$ numbering in its original order (of course, replacing $1$ with $2\times4^n+1$, $2$ with $2\times4^n+2$, etc.

Fourth quadrant: we take the $n^{\rm th}$ numbering, rotate it $90$ degrees counter-clockwise and use reverse order, starting with $3\times4^n+1$.

(this is not that easy to write or read, but it is very easy to check if you draw the squares)

The two claims to be proven are:

1) the sequence $\{f_n\}$ converges uniformly;

2) the limit function touches every point in the square.

To prove 1), we note that in the interval $[k4^{-n},(k+1)4^{-n})$, both $f_n$ and $f_{n+1}$ take values in the same square of side $2^{-n}$. This shows that $$ |f_{n+1}-f_n|\leq2^{-n}\ \ \ \text{ uniformly.} $$

Regarding 2), if we write $f=\lim f_n$, then $f$ is continuous, and so the image of the compact interval $[0,1]$ is compact, so in particular it is closed. Fix any point $(x,y)\in[0,1]^2$. Fix $n$; then there exists a square from our grid, of side $2^{-n}$ that contains $(x,y)$; say it's the $k^{\rm th}$ one. Then $$ \|f_n(k/4^n)-(x,y)\|\leq 2^{-n}. $$ Since $f=f_n+\sum_{m=n}^\infty (f_{m+1}-f_m)$, $$ \|f(k/4^n)-(x,y)\|\leq\|f_n(k/4^n)-(x,y)\|+\sum_{m=n}^\infty\|f_{m+1}-f_m\|\\ \leq2^{-n}+\sum_{m=n}^\infty2^{-m}=2^{-n}+2^{-n+1}=\frac3{2^{n}}. $$ This shows that $(x,y)$ is in the closure of the graph of $f$, but we already know that the graph of $f$ is closed, and so the image of $f$ is $[0,1]^2$.

Solution 2:

Since no one has yet given you any references in English, below are a couple of books that are fairly complete for what you want.

Each book is pitched at the U.S. advanced undergraduate level. Sagan's book is very detailed with historical issues for these curves and it is also quite readable. The book by Darst seems decent also (it has much less on history), but I haven't looked at it much yet (despite having gotten a copy about two years ago; I've had Sagan's book since around 1995).

Curious Curves by Darst/Palagallo/Price (2009)

http://www.amazon.com/dp/9814291285

Space-Filling Curves by Sagan (1994)

http://www.amazon.com/dp/0387942653

Solution 3:

I really like the answer of Martin Argerami. The only point that worried me was

(this is not that easy to write or read, but it is very easy to check if you draw the squares)

To circumvent this problem, one can use the following argument that is based on Banach's fixed point theorem (note that the geometric idea is still the same as for the construction of the Hilbert curve and/or in the post of Martin Argerami). Also compare the following to the post of john mangual.

We define mappings

$$ \begin{eqnarray*} A_{1}: & \left[0,1\right]^{2}\rightarrow\left[0,\frac{1}{2}\right]^{2}\subset\left[0,1\right]^{2}, & x\mapsto\frac{1}{2}\left[\left(\begin{array}{cc} 0 & 1\\ -1 & 0 \end{array}\right)\left(x-\left(\begin{matrix}1/2\\ 1/2 \end{matrix}\right)\right)+\left(\begin{matrix}1/2\\ 1/2 \end{matrix}\right)\right]\\ & & \phantom{x}=\frac{1}{2}\left(\begin{array}{cc} 0 & 1\\ -1 & 0 \end{array}\right)\,x+\left(\begin{matrix}0\\ 1 \end{matrix}\right),\\ A_{2}: & \left[0,1\right]^{2}\rightarrow\left[0,\frac{1}{2}\right]\times\left[\frac{1}{2},1\right]\subset\left[0,1\right]^{2}, & x\mapsto\frac{1}{2}x+\left(\begin{matrix}0\\ 1/2 \end{matrix}\right),\\ A_{3}: & \left[0,1\right]^{2}\rightarrow\left[\frac{1}{2},1\right]^{2}\subset\left[0,1\right]^{2}, & x\mapsto\frac{1}{2}x+\left(\begin{matrix}1/2\\ 1/2 \end{matrix}\right),\\ A_{4}: & \left[0,1\right]^{2}\rightarrow\left[\frac{1}{2},1\right]\times\left[0,\frac{1}{2}\right]\subset\left[0,1\right]^{2}, & x\mapsto\frac{1}{2}\left[\left(\begin{array}{cc} 0 & -1\\ 1 & 0 \end{array}\right)\left(x-\left(\begin{matrix}1/2\\ 1/2 \end{matrix}\right)\right)+\left(\begin{matrix}1/2\\ 1/2 \end{matrix}\right)\right]+\left(\begin{matrix}1/2\\ 0 \end{matrix}\right)\\ & & \phantom{x}=\frac{1}{2}\left(\begin{array}{cc} 0 & -1\\ 1 & 0 \end{array}\right)x+\left(\begin{matrix}1\\ 0 \end{matrix}\right). \end{eqnarray*} $$

These are just the rotations (+scaling and shifting) that are used in the numbering as in the post of Martin Argerami.

It is easy to check that these are well-defined and surjective maps (even bijective) that satisfy

$$\tag {*} \begin{equation} \left\Vert A_{j}x-A_{j}y\right\Vert _{2}=\frac{1}{2}\cdot\left\Vert x-y\right\Vert _{2} \end{equation} $$

for all $j=1,\dots,4$ and $x,y \in [0,1]^2$.

For $j=1,\dots,4$ we also set $I_{j}:=\left[\frac{j-1}{4},\frac{j}{4}\right]\subset\left[0,1\right]^{2}$ and $$ \begin{eqnarray*} \varphi_{1}: & I_{1}\rightarrow\left[0,1\right], & x\mapsto1-4x,\\ \varphi_{2}: & I_{2}\rightarrow\left[0,1\right], & x\mapsto4\cdot\left(x-\frac{1}{4}\right),\\ \varphi_{3}: & I_{3}\rightarrow\left[0,1\right], & x\mapsto4\cdot\left(x-\frac{1}{2}\right),\\ \varphi_{4}: & I_{4}\rightarrow\left[0,1\right], & x\mapsto1-4\cdot\left(x-\frac{3}{4}\right). \end{eqnarray*} $$

It is again an easy exercise to show that these are well-defined and surjective (even bijective).

Now, let $$ M:=\left\{ f\in C\left(\left[0,1\right];\mathbb{R}^{2}\right) \,\middle|\,f\left(0\right)=\left(\begin{matrix}0\\ 0 \end{matrix}\right),\; f\left(1\right)=\left(\begin{matrix}1\\ 0 \end{matrix}\right)\;,f\left(\left[0,1\right]\right)\subset\left[0,1\right]^{2}\right\} . $$

It is easy to see that this is a closed, nonempty subset of $C([0,1]; \Bbb{R}^2)$, when this space is equipped with the $\sup$-norm (let us use $|\cdot| = \Vert \cdot \Vert_2$ on $\Bbb{R}^2$).

We now define an operator $T : M \rightarrow M$ by

$$ \left(Tf\right)\left(x\right):=A_{j}\left(f\left(\varphi_{j}\left(x\right)\right)\right)\text{ for }x\in I_{j}\text{ and }j\in\{1,2,3,4\} $$

One can check that $Tf$ is a well-defined, continuous function for $f \in M$ and even $Tf \in M$ for $f \in M$, so that $T$ is well-defined.

Using the estimate $(\ast)$ above, one easily gets

$$ \left\Vert Tf-Tg\right\Vert _{\sup}\leq\frac{1}{2}\cdot\left\Vert f-g\right\Vert _{\sup} $$

for all $f,g \in M$. Thus, by Banach's fixed point theorem, there is a (unique) fixed point $f_0 \in M$ of $T$, which is thus a continuous map $f_0 : [0,1] \rightarrow [0,1]^2$. It remains to show that $f_0$ is surjective. As the image $f_0 ([0,1])$ is compact, it suffices to show that it is dense in $[0,1]^2$.

Using induction on $j \in \Bbb{N}_0$, we will show that for each $y \in [0,1]^2$, there is some $x \in [0,1]$ satisfying

$$\tag {**} \left\Vert f_{0}\left(x\right)-y\right\Vert _{2}\leq\sqrt{2}\cdot2^{-j}. $$

This is clear for $j=0$, as the diameter of $[0,1]^2$ is just $\sqrt{2}$.

For the induction step, note that there is some $j \in \{1, \dots, 4\}$ such that $y \in A_j ([0,1]^2)$, i.e. $y = A_j y'$ for some $y' \in [0,1]^2$. By induction, there is some $x' \in [0,1]$ such that $(\ast \ast)$ is satisfied for $x'$ and $y'$ instead of $x,y$.

Furthermore (because $\varphi_j$ is surjective), there is $x \in I_j$ with $x' = \varphi_j (x)$.

Now, the fixed point property $f_0 =Tf_0$ implies

$$ f_{0}\left(x\right)=\left(Tf_{0}\right)\left(x\right)=A_{j}\left(f_{0}\left(\varphi_{j}\left(x\right)\right)\right)=A_{j}\left(f_{0}\left(x'\right)\right), $$

Using the estimate $(\ast)$, we arrive at

\begin{align} \left\Vert f_{0}\left(x\right)-y\right\Vert _{2}&=\left\Vert A_{j}\left(f_{0}\left(x'\right)\right)-A_{j}y'\right\Vert _{2}=\frac{1}{2}\cdot\left\Vert f_{0}\left(x'\right)-y'\right\Vert _{2}\\ &\leq\frac{1}{2}\cdot\sqrt{2}\cdot2^{-j}=\sqrt{2}\cdot2^{-\left(j+1\right)}, \end{align} which completes the proof.