21
$\begingroup$

In discussion about the question Is there a way to represent the interior of a circle with a curve?, it was mentioned that such a curve cannot be one-to-one (because $[0,1]$ is not homeomorphic to $[0,1]^2$). I'm curious about in what way the Peano curve is not one-to-one.

The construction of the Peano curve is a recursive refinement of a particular path that discretely looks one-to-one, in that it touches every coordinate point at a given scale in a bijection. In the limit there's no bijection, but at every step there is a bijection between the curve so far and the coordinates of points within $[0,1]^2$ truncated to so many binary digits.

In a surjection that is not an injection, there must be some overlap (some $x,y$ where $x\neq y$ but $f(x)=f(y)$. What I'm getting at is...where is the overlap? I'm guessing it's not just at one point - is it at all points? how much overlap? What is the nature of the overlap (for a given point on $[0,1]^2$, which points in $[0,1]$ map to it?

(for discussion's sake, use the definition of the Hilbert-Peano curve)

Edit: A small bit of clarification: given a point $(j,k)$, is their overlap, and if so, how much (what is the cardinality of the inverse image at that point)? How about just for a particular point like $(1/2, 1/2)$?

  • 2
    The self-similarity of the curve at least shows that the noninjective points are dense (either in the interval or the square.)2011-03-29

3 Answers 3

16

The points of overlap are precisely those where one at least one coordinate is a dyadic rational $n/2^N$ for some integers $n,N$, except some points on the boundary of the square $[0,1]^2$. If you focus on the middle point $(1/2,1/2)$ of the square in the animation on the Wikipedia page, you can observe that it is approached from three different directions. (Actually, $H(1/6)=H(1/2)=H(5/6)=(1/2,1/2)$, where $H:[0,1]\to[0,1]^2$ is the Hilbert curve.) The same goes for the points $(1/4,1/4), (3/4,1/4), (3/4,1/4), (3/4, 3/4),$ and so on.

It's not self-intersecting in all points: the point $(0,0)$ for example is only hit once.

Added after comments: Here's how to see exactly which points are the points of self-intersection.

Subdivide $[0,1]^2$ into a grid of $2^n\times2^n$ squares. The $n$th iteration of the discrete Hilbert curve passes through each of these squares once. Number the squares from $1$ to $(2^n)^2$ in the order we pass through them, and let $H_n(k/(2^n)^2)$ be the center of the $k$th square, and extend $H_n$ to the whole interval $[0,1]$ by making it piecewise linear between the points $k/(2^n)^2$. The Hilbert curve $H:[0,1]\to[0,1]^2$ is defined by $H(x)=\lim_{n\to\infty}H_n(x)$.

Now suppose that $H(x)=H(y)$ where $x\neq y$, so that the point $H(x)\in[0,1]^2$ is a point where the curve self-intersects. Subdivide $[0,1]^2$ into a grid of $2^n\times 2^n$ squares, where $n$ is large enough so that the interval $(x-\epsilon,x+\epsilon)$ maps into one square, while $(y-\epsilon,y+\epsilon)$ maps into another square, for some small $\epsilon>0$. (This should always be possible by the construction of the Hilbert curve.) Since $H(x)$ and $H(y)$ belong to different squares, but they are equal, they must meet along the border of the squares, and this can only happen if one coordinate is a dyadic rational.

In the other direction, fix any point $(x,y)$ where one coordinate is a dyadic rational. This is a point on the border between two different squares in some $2^n\times 2^n$-subdivision of $[0,1]^2$. By the construction of the Hilbert curve, there exist a closed interval whose image is the first square, and another closed interval whose image is the second square. If $(x,y)$ is an interior point, by the way the Hilbert curve snakes around, we can always make sure those two intervals are disjoint. Since both intervals map surjectively onto the border between our two squares, there exists a point $x$ in the first interval and a point $y$ in the other interval such that $H(x)=H(y)$.

  • 0
    @Mitch: (cont.) You can calculate $H(1/6)=H(1/2)=H(5/6)=(1/2,1/2)$ by counting how many squares the $n$th discrete Hilbert curve $H_n$ passes through until it reaches one of the four squares touching $(1/2,1/2)$. If $H(x)=(1/2,1/2)$ where $0\leq x\leq 1/4$, then $H_n(x)$ is in the lower left square touching $(1/2,1/2)$, so we must have $x\in[1/6-1/2^{2n},1/6]$ (I'll leave how to calculate that as an exercise).2011-04-05
4

You can see some specific places where the curve is not 1-1 as follows. The various stages of the construction are controlled by a grid, and as the curve gets filled in, it approaches the edges (and corners) of the grid from each side. So in the limit, points in the square which lie on the edge of the grid at some stage of the construction will be in the image of at least two points of the peano arc. The interior corners will lie in at least 4 points. So this at least shows it is not 1-1.

1

This is actually elaborated in the wiki article on Space-filling curves.

The short of it is that the Peano curve is continuous, $[0,1]$ is compact and $[0, 1]^2$ is Hausdorff, so if it were injective it would be a homeomorphism (we already know its surjective).

The missing bit is that it is everywhere self-intersecting but I feel this may be shown through arbitrarily restricting the domain - it is continuous, after all, so there is hope.

  • 1
    It seems counterintuitive, yes; but there is a "qualitative" heuristc remark which can highlight this fact. In fact, as you can see from the pictures, if one sets *$\delta_n :=$ minimum distance separating each couple of blocks the curve is made of at the $n$th step*, then $\delta_n=2^{-n}$; therefore in the limit (i.e. when the iteration gets closer and closer to *Peano's curve*) $\delta_n\to 0$, i.e. the blocks become closer. Of course, this is a purely heuristic argument, but I think it can help visualizing how things go.2011-03-29