Mapping the Hilbert curve

In 1877 the German mathematician Georg Cantor made a shocking discovery. He found that a two-dimensional surface contains no more points than a one-dimensional line.

Thus begins my latest column in American Scientist, now available in HTML or PDF. The leading actor in this story is the Hilbert curve, which illustrates Cantor’s shocking discovery by leaping out of the one-dimensional universe and filling up a two-dimensional area. David Hilbert discovered this trick in 1891, building on earlier work by Giuseppe Peano. The curve is not smooth, but it’s continuous—you can draw it without ever lifting the pencil from the paper—and when elaborated to all its infinite glory it touches every point in a square.

The first through fourth generations of the Hilbert curve

Above: The first through fourth stages in the construction of the Hilbert curve. To generate the complete space-filling curve, just keep going this way.

To supplement the new column I’ve built two interactive illustrations. The first one animates the geometric construction of the Hilbert curve, showing how four copies of the generation-n curve can be shrunken, twirled, flipped and reconnected to produce generation n+1. The second illustration is a sort of graphic calculator for exploring the mapping between one-dimensional and two-dimensional spaces. For any point t on the unit line segment [0, 1], the calculator identifies the corresponding point x, y in the unit square [0, 1]2. The inverse mapping is also implemented, although it’s not one-to-one. A point x, y in the square can correspond to multiple points t on the segment; the calculator shows only one of the possibilities.

The Hilbert-curve illustrations are posted in the Extras department here at bit-player.org. I encourage you to go play with them, but please come back and read on. I have some unsolved problems.


I built the Hilbert mapping calculator in part to satisfy my own curiosity. It’s fine to know that every point t can be matched with a point x, y, but which points go together, exactly? For example, what point in the square corresponds to the midpoint of the segment? The answer in this case is not hard to work out: The middle of the segment maps to the middle of the square: (t = 1/2) → (x = 1/2, y = 1/2). Shown below are a few more salient points, as plotted by the calculator:

mapping of n/12 onto the Hilbert curve, for n=0 through n=12

Rational points of the form t = n/12, for integer 0 ≤ n ≤ 12, are mapped into the unit square according to their positions along the Hilbert curve. For example, t = 3/12 = 1/4 is mapped to the point x = 0, y = 1/2, at the midpoint of the square’s left edge. Note that the Hilbert curve drawn in the background of the illustration is a fifth-stage approximation to the true curve, but the positions of the colored dots are calculated to much higher precision.

Looking at this tableau led me to wonder what other values of t correspond to “interesting” x, y positions. In particular, which fractions along the t segment project to points on the perimeter of the square? Which t values go to points along one of the midlines, either vertical or horizontal? To narrow these questions a little further, let’s just consider fractions whose denominator is a prime. (In all that follows I ignore fractions with denominator 1, or in other words the end points of the t segment.)

The diagram above already reveals that fractions with denominator 2 and 3 are members of the “interesting” class. The value t = 1/2 maps to the intersection of the two midlines. And t = 1/4, 1/3, 2/3 and 3/4 all generate x, y points that lie on the perimeter. Can we find interesting fractions with other prime factors in the denominator? Yes indeed! Here is the Hilbert mapping for fractions of the form n/5:

mapping of n/5 onto the Hilbert curve, for n=0 through n=5

Hilbert mapping for fifths. In the calculator you can generate this output by entering */5 into the input area labeled “t =”. It turns out that (t = 2/5) → (x = 1/3, y = 1), and (t = 3/5) → (x = 2/3, y = 1).

Note that 2/5 and 3/5 map to points on the upper boundary of the square. By a simple sequential search I soon stumbled upon two more “interesting” examples, namely n/13, and then n/17.

mapping of n/13 onto the Hilbert curve, for n=0 through n=13

Hilbert mapping for t = 0/13, 1/13, 2/13 … 13/13. The fractions t = 3/13, 4/13, 9/13 and 10/13 yield x, y coordinates on the perimeter of the square.

mapping of n/17 onto the Hilbert curve, for n=0 through n=17

Hilbert mapping for 17ths. The fractions t = 1/17, 4/17, 6/17 and 7/17 correspond to points on the perimeter, as well as the mirror images of these points when reflected through the vertical midline.

At this point I began to think that prime-denominator fractions yielding perimeter points must be lying around everywhere just waiting for me to gather them up. And I was not surprised by their seeming abundance. After all, there are infinitely many points on the perimeter of the square, and so there must be infinitely many corresponding t values—even if we confine our attention to the rational numbers.

When I continued the search, however, my luck ran out. In the “t=” box of the calculator I typed in all fractions of the form */p for primes p < 100; I found no points on the perimeter other than the ones I already knew about, namely those for p = 3, 5, 13 and 17.

So I automated the search. It turns out the next prime denominator yielding perimeter points is 257. Typing */257 into the calculator produces this garish display:

mapping of n/257 onto the Hilbert curve, for n=0 through n=257

Points of the form t = n/257. There are 32 points that lie along the perimeter of the square.

Beyond 257 comes an even longer barren stretch. Surveying all prime denominators less than 10,000 failed to reveal any more that produce Hilbert-curve perimeter points.

Why not search the other way? We can plug in x, y values on the perimeter and then use the inverse Hilbert transformation to find a corresponding t value. I tried that. It was easy to get a sequence of approximations to t but not so easy to deduce the limiting value.To summarize, if t = n/p is a fraction that maps to a point on the perimeter of the Hilbert curve, and if p is a prime less than 10,000, then p must be one of the set {3, 5, 13, 17, 257}. Let’s pluck 13 out of this group and set it aside for a moment. The remaining elements of the sequence look familiar. They are all numbers of the form \(2^{2^n} + 1\). In other words, they are Fermat numbers. In 1640 Pierre de Fermat examined the first five numbers in this sequence: 3, 5, 17, 257, 65537. He confirmed that each of them is a prime, and he conjectured that all further numbers formed on the same model would also be prime. So we come to the burning question of the moment: Does the fifth Fermat prime 65537 generate perimeter points on the Hilbert curve? It sure does: 512 of them.

The obvious next step is to look at larger Fermat numbers, but there’s a complication. Fermat’s claim that all such numbers are prime turned out to be overreaching a little bit; beyond the first five, every Fermat number checked so far has turned out to be composite. Still, we can see if they give us Hilbert perimeter points. The sixth Fermat number is 4294967297, and sure enough there are fractions with this number in the denominator that land on the perimeter of the Hilbert curve. For example, t = 4/4294967297 converges to x = 0, y = 1/32768. We can also check the factors of this number (which have been known since 17291732, when Euler identified them as 641 and 6700417). With a bit of effort I pinned down a few fractions with 6700417 in the denominator, such as 2181/6700417, that are on the perimeter.

It’s the same story with the seventh Fermat number, 18446744073709551617. Both this number and its largest prime factor, 67280421310721, yield perimeter points. I have not looked beyond the seventh F number. Would I be as reckless as Fermat if I were to conjecture that all such numbers generate Hilbert-curve perimeter points?

Thus the known prime denominators that give rise to perimeter points are the five Fermat primes, 3, 5, 17, 257 and 65537, as well as two prime factors of larger Fermat numbers, 6700417 and 67280421310721. Oh, and 13. I almost forgot 13. Who let him in?

Of course there are many (infinitely many) perimeter points whose associated t values do not have a prime denominator. If we run through all fractions whose denominator is less than 1,000 (when reduced to lowest terms), this is the set of denominators that maps to perimeter points:

{3, 4, 5, 12, 13, 16, 17, 20, 48, 51, 52, 63, 64, 65, 68, 80, 192, 204, 205, 208, 252, 255, 256, 257, 260, 272, 273, 320, 341, 768, 771, 816, 819, 820, 832}

It’s another curious bunch of numbers, with patterns that are hard to fathom. (The OEIS is no help.) I thought at first that the numbers might be composed exclusively of the primes I had identified earlier (as well as 2). This notion held together until I got to 63, which of course has a factor of 7. Then I thought a slightly weaker condition might hold: Other factors are allowed, but at least one factor must be drawn from the favored set. That lasted until I reached 341, which factors as 11 × 31. There must be some logic behind the selection of these numbers, but the rule escapes me. One more peculiarity: Every even power of 2 appears, but none of the odd powers.

Here is the analogous set of denominators for t values that project to the two midlines of the Hilbert curve:

{2, 4, 6, 10, 12, 16, 20, 26, 34, 48, 52, 64, 68, 80, 102, 126, 130, 192, 204, 208, 252, 256, 260, 272, 320, 410, 510, 514, 546, 682, 768, 816, 820, 832}

One difference jumps out immediately: All of these numbers are even. Yet the sets have more than half their elements in common. Every even member of the perimeter set is also a member of the midline set. Also note that again only even powers 2 are included (apart from 2 itself).


I doubt that any deep mathematical truth hinges on the question of which numbers correspond to perimeter points on the Hilbert curve. Nevertheless, having allowed myself to get sucked into this murky business, I would really like to come out of it with some glimmer of understanding. So far that eludes me.

I can explain part of what’s happening here by looking more closely at the mechanism of the mapping from t to x, y. The process is easiest to follow if t is expressed as a quaternary fraction (i.e., base 4). Thus we view t as a list of “quadits,” digits drawn from the set {0, 1, 2, 3}. Each stage of the mapping process takes a single quadit and uses it to choose one of four affine transformations to apply to the current x, y coordinates, from H0 to H3.

\[ \mathbf{H}_0 =
\left(
\begin{matrix}
0 & 1/2\\
1/2 & 0
\end{matrix}
\right)
\left(
\begin{matrix}
x\\
y
\end{matrix}
\right)
+
\left(
\begin{matrix}
0\\
0
\end{matrix}
\right)
\qquad
\mathbf{H}_1 =
\left(
\begin{matrix}
1/2 & 0\\
0 & 1/2
\end{matrix}
\right)
\left(
\begin{matrix}
x\\
y
\end{matrix}
\right)
+
\left(
\begin{matrix}
0\\
1/2
\end{matrix}
\right)
\]

\[ \mathbf{H}_2 =
\left(
\begin{matrix}
1/2 & 0\\
0 & 1/2
\end{matrix}
\right)
\left(
\begin{matrix}
x\\
y
\end{matrix}
\right)
+
\left(
\begin{matrix}
1/2\\[0.3em]
1/2
\end{matrix}
\right)
\qquad
\mathbf{H}_3 =
\left(
\begin{matrix}
0 & -1/2\\
-1/2 & 0
\end{matrix}
\right)
\left(
\begin{matrix}
x\\
y
\end{matrix}
\right)
+
\left(
\begin{matrix}
1\\
1/2
\end{matrix}
\right)
\]

The sequence of quadits determines a sequence of transformations, which in turn determines the mapping from t to x, y. Here is the Javascript that implements the mapping function in the online Hilbert-curve calculator:
Most of the results reported here come not from the Javascript version but from a Lisp implementation, which can take advantage of Common Lisp’s arbitrary-precision rational numbers. (Javascript has only IEEE floats.)

function hilbertMap(quadits) {
  var pt, t, x, y;
  if ( quadits.length === 0 ) {
    return new Point(1/2, 1/2);   // center of the square
  }
  else {
    t = quadits.shift();          // get first quadit
    pt = hilbertMap(quadits);     // recursive call
    x = pt.x;
    y = pt.y;
    switch(t) {
      case 0:     // southwest, with a twist
        return new Point(y * 1/2 + 0, x * 1/2 + 0);
      case 1:     // northwest
        return new Point(x * 1/2 + 0, y * 1/2 + 1/2);
      case 2:     // northeast
        return new Point(x * 1/2 + 1/2, y * 1/2 + 1/2);
      case 3:     // southeast, with twist & flip
        return new Point(y * -1/2 + 1, x * -1/2 + 1/2);
    }
  }
}

If you’re not in a mood to pick your way through either the linear algebra or the source code, I can give a rough idea of what’s going on. With each 0 quadit, the x, y point drifts toward the southwest corner of the square. A 1 quadit steers the point toward the northwest, and likewise a 2 quadit nudges the point to the northeast and a 3 quadit to the southeast. From these facts alone you can predict the outcome of simple cases. An uninterrupted string of 0 quadits has to converge on the southwest corner of the square, which is just what’s observed for t = 0. In the same way, a quadit sequence of all 1s has to end up in the northwest corner. What t value corresponds to (0.1111111…)4? This is the quaternary expansion of 1/3, which explains why we see (t = 1/3) → (x = 0, y = 1).

The quaternary expansion of 2/5 is (0.121212…)4. Let’s trace what the Javascript code above does when it is given a finite prefix of this number. In the illustration below, the prefix is just four quadits, (0.1212)4. sequence of x, y positions in mapping t = 2/5 = quaternary 0.1212 The recursive procedure effectively works back-to-front through the sequence of quadits. The x and y coordinates are given initial values of 1/2 (in the middle of the square). The first transformation is H2, which amounts to x → (y/2 + 1/2), y → (x/2 + 1/2); after this operation, the position of the x, y point is (3/4, 3/4). The next quadit is 1, and so the H1 transformation is applied to the new x, y coordinates. H1 specifies x → (x/2), y → (y/2 + 1/2); as a result, the point moves to (3/8, 7/8). Another round of H2 followed by H1 brings the position to (11/32, 31/32). Generalizing to a more precise calculation with a longer string of quadits, it’s easy to see that the nth location in this progression will have a y coordinate equal to \(\frac{2^{n}-1}{2^{n}}\); as n goes to infinity, this expression converges to 1.

Here the quaternary expansion of 2/5 is compared with the expansions of a few other fractions that correspond to y = 1 perimeter points:

t = 2/5 = (0.12121212…)4 → (x = 1/3, y = 1)

t = 6/17 = (0.11221122…)4 → (x = 1/5, y = 1)

t = 22/65 = (0.11122211…)4 → (x = 1/9, y = 1)

t = 86/257 = (0.11112222…)4 → (x = 1/17, y = 1)

Every number t whose quaternary expansion consists exclusively of 1s and 2s projects to some point along the northern boundary of the square. It would be satisfyingly tidy if we could make an analogous statement about the other three boundary edges. For example, if all 1s and 2s head north, then quadits made up of 0s and 3s ought to wind up on the southern edge. But it’s not so simple. Consider these cases:

t = 1/17 = (0.00330033…)4 → (x = 1/5, y = 0)

t = 4/17 = (0.03300330…)4 → (x = 0, y = 2/5)

t = 13/17 = (0.30033003…)4 → (x = 1, y = 2/5)

t = 16/17 = (0.33003300…)4 → (x = 4/5, y = 0)

The behavior of 1/17 and 16/17 is what you might expect: They go south. But 4/17 and 13/17 migrate not to the bottom of the square but to the two sides. If strings of 1s and 2s are so well-behaved, what’s the matter with strings of 0s and 3s? Well, the geometric transformations associated with quadrants 1 and 2 are simple scalings and translations. The matrices for quadrants 0 and 3 are more complicated: They introduce rotations and reflections. As a result it’s not so easy to predict the trajectory of an x, y point from the sequence of quadits in the t value. In any case I have not yet found a simple and obvious general rule.

The case of t = n/13 is no less perplexing:

t = 1/13 = (0.010323010323…)4 → (x = 1/3, y = 0)

t = 4/13 = (0.103230103230…)4 → (x = 0, y = 2/3)

t = 9/13 = (0.230103230103…)4 → (x = 1, y = 2/3)

t = 12/13 = (0.323010323010…)4 → (x = 2/3, y = 0)

When I trace through these transformations, as I did above for t = 2/5, I get the right answer in the end, but I haven’t a clue to the logic that drives the trajectory. I certainly can’t look at such a sequence of quadits and predict where the point will wind up.


I am left with more questions than answers. Furthermore, I don’t know whether the questions are genuinely difficult or if I am just missing something obvious. (It wouldn’t be the first time.) Anyway, here are the two big ones:

  • Can we prove that all Fermat numbers give rise to Hilbert-curve perimeter points? And, for composite Fermat numbers, will we always find that at least one of the factors shares this property?
  • Apart from the Fermat primes and factors of composite Fermat numbers, is 13 the only “sporadic” case? If so, what’s so special about 13?

I lack the mental muscle to answer these questions. Maybe someone else will make progress.


Update 2013-04-27: After publishing this story yesterday, I extended my search for “interesting” prime denominators, covering the territory between 257 and 65537. I found one new specimen: 61681. Twenty t values with this denominator yield perimeter points on the Hilbert curve. The smallest of them is t = 907/61681 → (x = 0, y = 101/1025). The repeating unit of the quaternary expansion of this fraction is (0.00033003223330033011)4.


Update 2013-04-29: Please see the comments! Several readers have provided illuminating insights, including a finite-state machine by ShreevatsaR that recognizes the class of quaternary-digit sequences that map to the perimeter of the square. And, as a further result of ShreevatsaR’s analysis, we have yet another “interesting” prime denominator: 15790321.

This entry was posted in computing, mathematics.

16 Responses to Mapping the Hilbert curve

  1. Scott Farrar says:

    Very interesting!

    I decided to take a look at 13ths. You forgot that 1/13 and 12/13 lie on the perimeter, I believe.

    The special thing about 1, 3, 4, 9, 10, 12 (all /13) is their repeating decimal patterns form a cycle that is separate from the cycle formed by 2, 5, 6, 7, 8, 11 (all /13)

    0.076923
    0.230769
    0.307692
    0.692307
    0.769230
    0.923076

    You can see two cycles here: http://scottfarrar.com/blah/13ths.PNG

    • Brian Hayes says:

      Yes, the cyclic structure is also apparent in the quaternary expansions.

       1/13 --> 0.010323
       4/13 --> 0.103230
       3/13 --> 0.032301
      10/13 --> 0.323010
       9/13 --> 0.230103
      12/13 --> 0.301032
      
  2. Scott Farrar says:

    Also I started playing with divisions of the top “segment”. I’m not sure if I’m getting ahead of myself because my precision may not be sufficient.

    But consider these t values:
    4/12
    5/12, 7/12
    8/12

    Then these:
    2/5
    3/5

    Then these:
    16/48
    17/48, 19/48
    20/48, 28/48
    29/48, 31/48
    32/48

    Then these:
    6/17
    7/17
    10/17
    11/17

    Then these:
    20/60
    21/60
    24/60
    25/60, 35/60
    36/60
    39/60
    40/60

    Then these:
    21/63
    22/63
    25/63
    26/63
    37/63
    38/63
    41/63
    42/63

    Each successive set seems to divide the top “segment” into halves, thirds, quarters, fifths, sixths, sevenths, etc. But again, I’m not sure about the precision. Something to explore, perhaps.

    • Brian Hayes says:

      Your results are exact in the limit of an infinitely elaborated Hilbert curve. Fractions of the form \(n / 4^{k} \times 3\) produce a gridlike display, with regular divisions both vertically and horizontally. Try entering t = */12 or */48 or */192 or */768 into the online calculator.

  3. Stuart Price says:

    Those fractions with denominator 63 that Scott lists all pair up as external rays to the Mandelbrot set. Eg 21/63 and 42/63 land at the root point of the period 2 component, then 22 and 25 land together at the period 6 bifurcation from that component. 38 and 41 pinch off the conjugate component, and finally 26 and 37 pair up from either side of the real axis to land at the first primitive period 6 component. Perhaps there’s more to explore here, but I can’t crunch the bigger numbers in my head!

  4. Stuart Price says:

    I fired up the laptop to explore a little more. 6/17 = 90/255 lands at the root of a period 8 component, and it’s parameter ray partner is 101/255. This is also a t-value mapping to the square’s perimeter. 7 and 10/17 (=105, 150/255) land together on a primitive period 8 component on the real axis. What’s interesting to me is that there no nested components coming up for any given period.

    Moreover, where 4095 is the denominator for period 12 rays, all the “interesting” (ie perimeter) ones are actually just period 2, 4 and 6 rays that have already been counted. One of the most infamous components of the Mandelbrot set, the period 3 real axis component (3/7, 4/7), does not correspond to perimeter points of the Hilbert curve. Perhaps there is a connection with Brian’s observations about only even powers of 2 appearing in his lists.

    If I didn’t have to go to work this week, I’d be exploring this 24/7!

  5. ShreevatsaR says:

    This may be stating the obvious (or restating the problem), but it’s an exercise I found interesting.

    Let’s consider the quaternary digits as a string of characters. So for instance, 2/5 = 0.12121212… corresponds to the (infinite) string “12121212…”.

    We want to find all strings that lie on some (west/north/east/south) boundary. For strings of length 1, the strings that lie on the west boundary are 0 and 1, the strings that lie on the north boundary are 1 and 2, etc. For strings of length 3, the strings that lie on the west boundary (the leftmost column of the 8×8 grid) are 000, 001, 032, 033, 100, 103, 110 and 111.

    Let W be the set of all (infinite) strings that form the west boundary, similarly N, E, and S. My main observation, which is actually an easy exercise to prove (basically falls out of the definition of the curve), is that:

    W = 1W + 0S
    N = 1N + 2N
    E = 2E + 3S
    S = 0W + 3E
    (where as usual 1W etc. denotes concatentation, and + denotes “OR” or union.)

    Here N is the only “independent” one: we immediately see that N = (1+2)N which gives N = (1+2)* where * is the Kleene star (as in regexps).

    The others depend on each other in not very nice ways. We can “eliminate” one of them—S seems a good choice—and write the rest as:
    W = 1W + 0S = 1W + 0(0W + 3E) = 1W + 00W + 03E = (1+00)W + 03E and
    E = 2E + 3S = 2E + 3(0W + 3E) = 2E + 30W + 33E = 30W + (2+33)E.

    We want to find W + N + E + S. Of these, N is simply (1+2)* and can be treated separately. We can add the rest to get
    W + E + S = (1 + 0 + 00 + 30)W + (03 + 2 + 33 + 3)E, which simplifies a little to
    = (1 + 0 + 30)W + (2 + 3 + 03)E as 00W is subsumed by 0W and 33E by 3E.

    So in other words: the set of all quaternary digit sequences that lie on the boundary are those that either:
    * contain only 1s and 2s, or
    * start with 1 or 0 or 30 followed by something that lies on the west boundary, or
    * start with 2 or 3 or 03 followed by something that lies on the east boundary.

    Haven’t yet thought about how to go from here to the denominators of the actual fractions. :-) But at least it’s now a statement just about the form of the digits of the numbers… or is this really progress? Maybe not.

  6. ShreevatsaR says:

    Just a pedantic note about my previous comment above, for what it’s worth: it’s not correct to say N = (1+2)* (though N = (1+2)N is correct), since we’re considering only infinite strings. When I wrote that notation I was still in the process of generalizing from the finite string case, where I was considering a finite string e.g. 111 to lie on the perimeter (at the top-left corner of the depth-3 not-yet-Hilbert curve, rather than the final curve).

  7. ShreevatsaR says:

    Figured out a visual way of expressing the above equations

    N = 1N + 2N

    W = 1W + 0S

    E = 2E + 3S

    S = 0W + 3E

    Consider this image: http://imgur.com/IvCQdcc [also shown below -- BH] as a state-transition diagram.* Then strings on the perimeter of the Hilbert curve are those that are not rejected by it. In other words, if you can start in one of the boxes (W / N / E / S) and follow the infinite string without ever encountering any trouble (which means a character for which there is no outgoing edge from the current box), then that string lies on the perimeter.

    For instance, the string corresponding to 1/13 is (010323) repeating, which fits: you can start in the “S” box, and follow the string… after every 6 characters (every 3 actually in this instance) you return to the S box. You never have to leave the boxes and “die”, so it’s on the perimeter. Similarly, 907/61681 corresponds to the string (00033003223330033011) repeated, which can be done by starting in the W box.

    We can make up any arbitrary such path that stays in the boxes, and, if it’s a repeating string (which includes ending with all 0s), it will correspond to a rational number that is on the perimeter of the Hilbert curve. Even if it’s not repeating, it will be some irrational number that is on the perimeter.

    As for other “sporadic” primes: my guess is that 13 and 61681 are not the only ones. Note that if the string corresponding to a fraction has something like “13″ or “20″ anywhere in it, that string is immediately disqualified… Fermat primes seem to be good at avoiding these patterns. BTW, you only need to try primes that are factors of (4^k – 1) for some k, as any fraction with a length-k repeating part can be written as a fraction with (4^k – 1) as denominator. Considering powers of 4 up to 32 and prime factors greater than 65537, this means just the primes 87211, 131071, 174763, 178481, 262657, 524287, 2796203, 3033169, 6700417, 15790321, 715827883, 2147483647… perhaps your program might find another sporadic prime among these, if we’re lucky?

    • Brian Hayes says:

      Considering powers of 4 up to 32 and prime factors greater than 65537, this means just the primes 87211, 131071, 174763, 178481, 262657, 524287, 2796203, 3033169, 6700417, 15790321, 715827883, 2147483647…

      One of those numbers is already on our list: 6700417 is a factor of the sixth Fermat number (the one that Euler showed to be composite); and, as noted above, 6700417 is a perimeter denominator. Among the other numbers you suggest, there’s one more hit: 15790321. Among fractions with this denominator that map to the perimeter, the smallest is t=907/15790321. I have not finished checking 2147483647 (and indeed it may be beyond my capacity) but all the other candidates fail.

      Number-theory question: Are there primes other than 2 that are known not to be factors of (4^k – 1) for some k?

      • ShreevatsaR says:

        No actually, there is no such prime. We can in fact prove that every odd number p is a factor of (4^k – 1) for some k, using the pigeonhole principle: consider the numbers 4^k for k from 1 to p+1. They can’t be all distinct, as there are only p possible values modulo p, and therefore two of them, say 4^m and 4^n (assume m < n), leave the same reamainder mod p.
        Then p divides \( 4^n – 4^m = (4^m) (4^{n-m} – 1) \) and as it has no factor in common with 4^m, it divides 4^(n-m) – 1.

        So actually my reason for making the list of primes above wasn't very sound, but somehow it has given a hit. :-)

        Meanwhile, we can say something about the Fermat numbers, in a slightly more general form: For each k ≥ 1, the fraction \( \frac{1}{4^{2k} + 1} \) is mapped to the south boundary.
        Proof:
        \[ \frac{1}{4^{2k} + 1} = \frac{4^{2k} - 1}{4^{4k} - 1} \] whose representation in base 4 has a repeating part consisting of 2k 0s followed by 2k 3s. If we start in the "S" state and follow this string, we're back to S after the 4k-long repeating part, so the string goes to the southern perimeter.

        Of the Fermat numbers, this handles cases k ≥ 2 (we have 2^2^k + 1 = 4^2^(k-1) +1) and leaves out 3 and 5, which must be dealt with separately. Indeed, 1/5 = 3/15 = (03)repeating is not on the boundary at all (we instead have 2/5 = 6/15 which in base 4 is (12) repeating, so it's on the N boundary), and 1/3 which is (1) repeating is on the W/N boundary.

  8. ShreevatsaR says:

    The image http://imgur.com/IvCQdcc also immediately shows why odd powers of 2 don’t appear as denominators of perimeter fractions, and even powers do: a fraction p/q, where q is an odd power of 2, correspond to a string ending in …20000…, and there is no way to follow “20″ along the states. On the other hand, if q is an even powers of 2, then there are many ways to get fractions p/q that correspond to such strings; one such fraction is to take p=q/4, which comes from the string 1111..(the right number of 1s)..110000…., which you can follow by starting in the box W. There are many other such strings of course, and the number of strings can even be calculated exactly.

  9. Carl W says:

    Every rational can be written in the form \(n/4^i + r/(4^k – 1)\), with \(i \geq 0\), \(k \geq 1\), and \(0 \leq r < 4^k-1\). (Proof sketch: consider the quaternary expansion of the rational. Then \(r\) is the digit sequence of the repeating part, \(k\) is the length of the repeating part, and \(i\) is the number of digits before it starts repeating. Note that \(n\) is not required to be positive.)

    For a given \(i\) and \(k\), there are approximately \(4^{i+k}\) rationals of this form between 0 and 1. Of these, looking at the transition diagram, we can deduce that the number that map to the perimeter of the square is \(\leq 4 \cdot 2^{i+k}\). The "4" comes from the 4 possible initial states in the transition diagram. At each step in the transition diagram, there are 2 possible digits that remain in the diagram (and 2 that don't); we've got \(i+k\) digits under consideration, so that's the source of the \(2^{i+k}\). (Note that even if the digits of \(r\) stay in the diagram, it's possible that the digits of \(r\) repeated twice do not.)

    So in looking for rational numbers that map to the perimeter of the square, it seems that there are two fruitful places to look. Either look at numbers whose quaternary expansion has some special pattern, or look at numbers whose repeating part (when written in quaternary) is unusually short. (That's essentially what ShreevatsaR did by looking at primes that were factors of \(4^k-1\) for relatively small \(k\).) Or, of course, it's possible to enumerate all rationals that map to the perimeter by starting with the \(n/4^i + r/(4^k-1)\) form.

    So far, people have been talking about rationals that map to the perimeter. Are there any interesting irrationals that map to the perimeter? Probably not. Since there are digit sequences which are forbidden in the quaternary expansion of a number that maps to the perimeter, any number which is normal in base 4 cannot map to the perimeter. And if we believe the various conjectures about most "interesting" irrationals (that are not constructed by special reference to their digit sequence) being absolutely normal, they cannot map to the perimeter.

  10. Juan Antonio Martinez says:

    Did you try with prime Fibonaci numbers? Some of them seem to be on your “list”…

    • Brian Hayes says:

      I’ve checked all primes up to 65537; in that range the only Fibonacci primes that project to the perimeter are the smallest ones, 3, 5 and 13. I’ve just looked at the first Fibonacci prime larger than 65537, which is 514229. Nope.

  11. You might be interested in some modern random Peano-like curves. See the middle of the page http://mypage.iu.edu/~rdlyons/rw/rw.html .