¿Por qué la curva de Hilbert llena todo el cuadrado?

Question

Nunca he visto una definición formal de la curva de Hilbert, mucho menos un análisis cuidadoso de por qué llena todo el cuadrado. Los artículos de Wikipedia y Mathworld suelen ser bastante vagos.

Supongo que la idea es algo así: se define una secuencia de funciones $f_i(t) : [0,1]\to {\Bbb R}^2$, y luego se considera el límite puntual $f(t) = \lim_{i\to\infty} f_i(t)$.

Pero al ver el diagrama, no está claro que la secuencia converja. Puedo imaginar que podríamos pensar en seguir un único punto en el rango de $f_i$ a medida que $i$ aumenta, y ese punto podría moverse, pero solo en $2^{-i}$ en cada etapa, a medida que pasamos de $f_i$ a $f_{i+1}$, y así eventualmente se acerca a una posición límite. Pero no sé cómo podríamos llegar desde allí a mostrar que $f_i(t)$ converge para un valor particular del argumento, especialmente para un argumento que no sea racional diádico.

Y aunque converja, cada punto en el rango de cada $f_i$ tiene al menos una coordenada racional, por lo que no está en absoluto claro por qué un punto como $({1\over\sqrt2}, {1\over\sqrt2})$ debería estar en el rango de $f$.

Si hay una explicación fácil, me alegraría escucharla, pero también me gustaría tener una referencia en inglés.

Answer 1

Observando las imágenes, las curvas parciales se obtienen uniendo los centros de los cuadrados más pequeños dentro del cuadrado. En el primer paso se divide el cuadrado unitario en 4 cuadrados de lado $1/2$. Luego, cada uno de estos cuadrados se divide nuevamente en $4$ cuadrados, y así sucesivamente. Así que todo se reduce a enumerar las subdivisiones sucesivas del cuadrado: $f_n$ será la curva obtenida uniendo los centros de los $4^n$ cuadrados de lado $2^{-n}$ de acuerdo con el esquema de numeración adecuado.

Se puede convenir que $f_n:[0,1]\to[0,1]^2$, y representamos la parte de la línea correspondiente al $k^{\rm th}$ cuadrado usando el intervalo $[(k-1)4^{-n},k\,4^{-n})$.

La numeración para los primeros $4$ cuadrados (con lados $1/2$) es $1,2,3,4$ donde $1$ es el inferior izquierdo y luego procedemos en sentido horario.

Dado entonces el orden $n^{\rm th}$, obtenemos el orden $(n+1)^{\rm th}$ de la siguiente manera: los $4^{n+1}$ cuadrados se agrupan en cuatro grupos principales de $4^{n}$ cuadrados correspondientes a los cuatro "cuadrantes" del cuadrado unitario ("primer" cuadrante es inferior izquierdo, "segundo" cuadrante es superior izquierdo, "tercer" cuadrante es superior derecho, "cuarto" cuadrante es inferior derecho). En cada cuadrante utilizaremos la numeración del orden $n^{\rm th}$, de la siguiente manera:

Primer cuadrante: tomamos la numeración $n^{\rm th}$, la rotamos $90$ grados en sentido horario y usamos el orden inverso.

Segundo cuadrante: tomamos la numeración $n^{\rm th}$ en su orden original (por supuesto, reemplazando $1$ con $4^n+1$, $2$ con $4^n+2$, etc.

Tercer cuadrante: tomamos la numeración $n^{\rm th}$ en su orden original (por supuesto, reemplazando $1$ con $2\times4^n+1$, $2$ con $2\times4^n+2$, etc.

Cuarto cuadrante: tomamos la numeración $n^{\rm th}$, la rotamos $90$ grados en sentido antihorario y usamos el orden inverso, comenzando con $3\times4^n+1$.

(esto no es tan fácil de escribir o leer, pero es muy fácil de verificar si dibujas los cuadrados)

Las dos afirmaciones que deben ser demostradas son:

1) la secuencia $\{f_n\}$ converge uniformemente;

2) la función límite toca cada punto en el cuadrado.

Para demostrar 1), notamos que en el intervalo $[k4^{-n},(k+1)4^{-n})$, tanto $f_n$ como $f_{n+1}$ toman valores en el mismo cuadrado de lado $2^{-n}$. Esto muestra que $$ |f_{n+1}-f_n|\leq2^{-n}\ \ \ \text{uniformemente.} $$

Respecto a 2), si escribimos $f=\lim f_n$, entonces $f$ es continua, y por lo tanto la imagen del intervalo compacto $[0,1]$ es compacta, por lo que en particular es cerrada. Fijemos un punto $(x,y)\in[0,1]^2$. Fijemos $n$; entonces existe un cuadrado de nuestra cuadrícula, de lado $2^{-n}$ que contiene $(x,y)$; digamos que es el $k^{\rm th}$. Entonces $$ \|f_n(k/4^n)-(x,y)\|\leq 2^{-n}. $$ Como $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}}. $$ Esto muestra que $(x,y)$ está en la clausura del gráfico de $f$, pero ya sabemos que el gráfico de $f$ es cerrado, y por lo tanto la imagen de $f$ es $[0,1]^2.

Answer 2

Dado que todavía nadie te ha dado referencias en inglés, a continuación hay un par de libros que son bastante completos para lo que buscas.

Cada libro está dirigido al nivel universitario avanzado en los Estados Unidos. El libro de Sagan es muy detallado con temas históricos sobre estas curvas y también es bastante legible. El libro de Darst parece ser decente también (tiene mucho menos historia), pero no lo he revisado mucho aún (a pesar de haberlo conseguido hace unos dos años; tengo el libro de Sagan desde alrededor de 1995).

Curious Curves de Darst/Palagallo/Price (2009)

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

Space-Filling Curves de Sagan (1994)

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

Answer 3

Realmente me gusta la respuesta de Martín Argerami. El único punto que me preocupaba era

(esto no es tan fácil de escribir o leer, pero es muy fácil de verificar si dibujas los cuadrados)

Para evitar este problema, se puede utilizar el siguiente argumento que se basa en el teorema del punto fijo de Banach (note que la idea geométrica sigue siendo la misma que para la construcción de la curva de Hilbert y/o en la publicación de Martín Argerami). Compare también lo siguiente con la publicación de John Mangual.

Definimos los mapeos

$$ \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*} $$

Estas son solo las rotaciones (+escalamiento y desplazamiento) que se utilizan en la numeración como en la publicación de Martín Argerami.

Es fácil verificar que estos son mapas bien definidos y sobreyectivos (incluso biyectivos) que satisfacen

$$\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} $$

para todo $j=1,\dots,4$ y $x,y \in [0,1]^2$.

Para $j=1,\dots,4$ también definimos $I_{j}:=\left[\frac{j-1}{4},\frac{j}{4}\right]\subset\left[0,1\right]^{2}$ y $$ \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*} $$

Es nuevamente un ejercicio fácil demostrar que estos son mapas bien definidos y sobreyectivos (incluso biyectivos).

Ahora, sea $$ 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\} . $$

Es fácil ver que este es un subconjunto cerrado y no vacío de $C([0,1]; \Bbb{R}^2)$, cuando este espacio está equipado con la norma $\sup$ (usemos $|\cdot| = \Vert \cdot \Vert_2$ en $\Bbb{R}^2$).

Ahora definimos un operador $T : M \rightarrow M$ por

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

Se puede verificar que $Tf$ es una función bien definida y continua para $f \in M$ e incluso $Tf \in M$ para $f \in M$, de modo que $T$ está bien definido.

Usando la estimación $(\ast)$ anterior, se obtiene fácilmente

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

para todo $f,g \in M$. Por lo tanto, por el teorema del punto fijo de Banach, existe un punto fijo (único) $f_0 \in M$ de $T$, que es así un mapeo continuo $f_0 : [0,1] \rightarrow [0,1]^2$. Queda por demostrar que $f_0$ es sobreyectivo. Como la imagen $f_0 ([0,1])$ es compacta, basta con demostrar que es densa en $[0,1]^2$.

Usando inducción en $j \in \Bbb{N}_0$, demostraremos que para cada $y \in [0,1]^2$, existe algún $x \in [0,1]$ que satisface

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

Esto es claro para $j=0$, ya que el diámetro de $[0,1]^2$ es precisamente $\sqrt{2}$.

Para el paso inductivo, observe que hay algún $j \in \{1, \dots, 4\}$ tal que $y \in A_j ([0,1]^2)$, es decir, $y = A_j y'$ para algún $y' \in [0,1]^2$. Por inducción, existe algún $x' \in [0,1]$ tal que $(\ast \ast)$ se satisface para $x'$ e $y'$ en lugar de $x,y$.

Además (porque $\varphi_j$ es sobreyectiva), existe $x \in I_j$ con $x' = \varphi_j (x)$.

Ahora, la propiedad del punto fijo $f_0 =Tf_0$ implica

$$ 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), $$

Usando la estimación $(\ast)$, llegamos a

\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} lo cual completa la demostración.

Answer 4

Escribí un programa para abordar esta pregunta: explorando la curva de llenado de espacio de Hilbert

Aquí está la imagen del intervalo $[\frac{1}{18}, \frac{1}{\sqrt{2}}]$ de la curva de llenado de espacio de Hilbert. .
Observa que es la unión de una cantidad infinita de cuadrados diádicos.

---

La imagen de la curva de Hilbert es invariante bajo el mapa 4 a 1 $T:[0,1]^2 \to [0,1]^2$ definido por:

• en $[0, \frac{1}{2}]^2$ gira $90^\circ$ en sentido contrario a las manecillas del reloj alrededor de $(\frac{1}{4}, \frac{1}{4})$ y duplica ambas coordenadas
• en $[0, \frac{1}{2}] \times [\frac{1}{2}, 1]$ duplica ambas coordenadas y traslada al cuadrado unitario
• en $[\frac{1}{2}, 1]^2$ duplica ambas coordenadas y traslada al cuadrado unitario
• en $[\frac{1}{2}, 1] \times [0, \frac{1}{2}]$ gira $90^\circ$ en el sentido de las manecillas del reloj alrededor de $(\frac{3}{4}, \frac{1}{4})$ y duplica ambas coordenadas

El mapa correspondiente en la preimagen $[0,1] = [0, \frac{1}{4}] \cup [ \frac{1}{4}, \frac{1}{2}] \cup [ \frac{1}{2}, \frac{3}{4}] \cup [ \frac{3}{4}, 1] $ es multiplicar por $4$ y trasladar de regreso a $[0,1]$.

Esto es equivalente a decir que la curva de Hilbert es un sistema de Lindemayer.

---

Examinemos las iteraciones de la curva de Hilbert en base 4:

1 2
0 3

y

11 12|21 22
10 13|20 23
-----------
03 02|31 30
00 01|32 33

y

111 112 121 122|211 212 221 222
110 113 120 123|210 213 220 223
103 102 131 130|203 202 231 230
100 101 132 133|200 201 232 233
--------------- ---------------
033 030 023 022|311 310 303 300
032 031 020 021|312 313 302 301
001 002 013 012|321 320 331 332
000 003 010 011|322 323 330 333

La preimagen de un cuadrado diádico de tamaño $\frac{1}{2^k} \times \frac{1}{2^k}$ es el subconjunto de $[0,1]$ con los primeros $k$ dígitos especificados en la expansión en base 4.

De esta manera podemos establecer la existencia de una curva límite y una convergencia uniforme.

Podemos tomar un punto como $(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$ expandirlo en base 4 y obtener una preimagen bien definida. Por lo tanto, es espacio-llenante.

Answer 5

También tuve dudas similares cuando aprendí por primera vez sobre la curva de Hilbert. La forma en que lo veo, de forma informal:

Supongamos que $x$ es un punto dentro del cuadrado con coordenadas irracionales. ¿La curva límite realmente incluye ese punto? Sí. ¿Significa esto que debe haber alguna curva $f_n$ (para algún $n$ "lo suficientemente grande") que lo toque? No, por supuesto que no.

Tienes la intuición correcta, en que tenemos una sucesión de transformaciones $f_i(t):[0,1] \to \mathbb{R}^2$ y estamos interesados en su límite. Podemos pensar en el parámetro como un "tiempo", y en cada iteración incrementamos la "velocidad" para seguir toda la curva en el mismo tiempo.

Lo que queremos ver es que de hecho podemos encontrar un $t_x \in [0,1]$ tal que $f(t_x)=x$, es decir, que se puede encontrar un instante de tiempo, para que en el límite la curva pase sobre nuestro punto $x$ en ese momento.

Ahora, para cada iteración $k$, dividimos el cuadrado en $2^k \times 2^k$ cuadrados. La curva visita el centro de estos cuadrados en instantes de tiempo $i/4^k$ ($i=1.. 4^k$) (efecto de borde no importante: supongamos que comenzamos en el primer punto en el tiempo $1/4^k$ en lugar de en el tiempo $0$). Entonces, por ejemplo, en la primera iteración, en el tiempo t=1/4 estamos en el cuadrado inferior izquierdo. Lo importante es que las subdivisiones iterativas de la curva (que tal vez parecen un poco... discontinuas) son continuas, en el sentido de que siempre (es decir, para otras iteraciones) será cierto que alrededor del tiempo $t=1/4$ estaremos dentro del cuadrado inferior izquierdo, y lo mismo se aplica a los cuadrados más pequeños: los refinamientos sucesivos nunca me sacan del cuadrado anterior para el mismo tiempo. Debería quedar claro entonces que cada cuadrado se puede poner en correspondencia con un intervalo en el parámetro $(t_a,t_b) \in [0,1]$, y que los cuadrados anidados sucesivos corresponden a intervalos anidados en el parámetro $t.

Volviendo a nuestro punto $x$, este se puede expresar de manera única como una secuencia de cuadrados contenidos (mismo razonamiento que el "principio de intervalos anidados" para los números reales), que corresponderán a una secuencia de intervalos contenidos en el parámetro, y por lo tanto definirán un número real único.