Posts Tagged ‘sequence’

Hardy and Wright, Chapter 3

March 28, 2009

Well, somewhat surprisingly, my little reading group hasn’t yet disbanded entirely. Last week we had a great discussion about chapter 2 of H&W, which put us in chapter 3 for this week.

Chris commented that one of the more interesting things, for him, in this chapter was that people would actually be interested in proving things about sequences of reduced fractions with bounded denominator (the Farey sequences that start the chapter). I rather enjoyed playing with them and reading about them. My understanding is that they are useful for starting to get bounds on approximating irrationals by rationals, a topic which I’m fairly certain we will return to. I also was glad to see a proof of Minkowski’s theorem about symmetric regions with large area containing lattice points. I think I’d heard the result before, but it’s always nice to see (and be able to follow!) a proof.

I was a little confused about when a mediant is reduced. I thought that the mediant of reduced fractions was reduced. For any three consecutive terms of a Farey sequence, the middle is the mediant of the other two. There is a footnote stating that the middle term might be the reduced form of the mediant. Why would you need this footnote, if mediants are already reduced? Chris pointed out that in the Farey sequence with denominator no larger than 3 (denote if F_3), 1/3, 1/2, 2/3 are consecutive terms, but the middle is the reduced mediant of the outer terms. All the text claims is that the first time a term shows up, it is the reduced mediant of its neighbors. Clearly mediants of reduced fractions aren’t, necessarily, reduced. Eric and I were frequently embarrased by things we thought were true during this meeting, and I pointed out that this was exactly why I wanted to read about these things: I don’t work with integers too much 🙂

Eric wondered about the fact that the distance between two consecutive terms h/k and h'/k' in a Farey sequence is 1/(kk'). Chris and I noted that this was obvious from the lemma that kh'-hk'=1. Eric was wondering, though, if one could determine it without that lemma somehow. We didn’t come up with much.

I presented the answer I had found to the question I had asked myself: “For h/n in F_n, can you find the first n'>n for which h/n has a new successor in F_{n'}? What can you say about the sequence of all such n'?” The book has a lemma about how to find the next term for h/n in F_n. Suppose that its successor is h'/k'. By other lemmas in this chapter, the next time something comes between these terms, it will be the mediant, \frac{h+h'}{n+k'}, and this occurs in F_{n+k'}. The next time h/n will have a new successor, it will be the mediant of h/n with this new term, \frac{h+h'}{n+k'}, and so will be \frac{2h+h'}{2n+k'}. Continuing on, we see that h/n has a new successor in the Farey sequences F_{m\cdot n+k'}.

Next, I talked about the Stern-Brocot Tree and Minkowski’s Question Mark function, ?(x). We had mentioned in our meeting that the terms of the Farey sequence are not equally distributed, and I pointed out that there was some relation between that and how ‘wobbly’ ?(x)-x is. Notice that the Farey sequences are least dense around 1/2, and most dense around 0 and 1, which relates well to the wobbliness of the graph of ?(x)-x. This has something to do with defining an appropriate measure so that ?(x) is the integral (of… something. 1? x?) with respect to this measure. At least, that’s what I gathered from Wikipedia. I’d like to read more about this.

Also, Eric and I had both noticed the comment on the Wikipedia page that there is a relation between Farey sequences and the Riemann hypothesis, which we found pretty intriguing. Of course, neither of us knew much about it. Perhaps a topic for another day. It seems to be related to the density, or perhaps distribution is more accurate, of the terms of Farey sequences in the interval [0,1].

I completely forgot to bring up Ford circles. If you put circles of appropriate sizes above the points in a Farey sequence, you get lots of nice tangent circles, with fun properties. Perhaps the property most relevant to this section is that any circles tangent to the circle above p/q are centered at x-coordinates that are neighbors of p/q in some Farey sequence.

Counting Cards

January 3, 2009

Over the past few days my roommate and I have been working on a business card Menger sponge origami project. This was most recently inspired by Thomas Hull‘s fun book ‘Project Origami‘, but it’s quite possible I’d heard of the project before I found the book. I know that in Hull’s book he finds formulas for the number of cards it takes to make various iterations of the sponge, but I wanted to try to come up with them again on my own, and thought I’d share my process.

Let F_n be the number of cards showing on each face of a level n sponge (recalling that level 0 is just an ordinary cube). The exterior faces of the Menger sponge are Sierpinski carpets, and it’s pretty easy to determine that F_0=1 and F_n=8\cdot F_{n-1}. This means F_n=8^n.

Next, let U_n be the number of cards needed to make a completely unpanelled level n sponge. So U_0=6, and to make a level n sponge requires 20 level n-1 sponges, so U_n=20\cdot U_{n-1}. This makes U_n=20^n\cdot 6.

Now I’d like to determine the number of cards needed for what I’ll call ‘interior panelled’ sponges. Let I_n denote the number of cards for such a level n sponge. A level n sponge consists of lots of little cubes, some of the faces of which are showing (not stuck against faces of other little cubes). Some of the showing faces occur on the very exterior of the sponge (on the faces of the encompassing cube, if you want). So ‘interior panelled’ would be all of the faces except these very exterior ones. There’s no such thing as an interior panelled level 0 sponge, so we start at level 1, counting I_1 as follows: Begin with an unpanelled level 1 sponge (U_1=20\cdot 6 cards), and panel the two interior faces of each of the 12 ‘edge’ level 0 cubes. So I_1=U_1+2\cdot 12=20\cdot 6 +2\cdot 12=144.

What about the next iteration for I_n? Well, there are 20 ‘interior panelled’ n-1 sponges, and you need to panel 2 of the exterior faces of each of the 12 ‘edge’ cubes. The exterior faces, recall, require F_{n-1} cards to panel. So I_n=20\cdot I_{n-1}+2\cdot 12\cdot F_{n-1}. Since we know F_{n-1}=8^{n-1}, we can clean this formula up a little: I_n=20\cdot I_{n-1}+24\cdot 8^{n-1}.

Now we’re almost done. The overall goal is to have a fully panelled level n sponge. Let P_n denote the number of cards required. Since a fully panelled level n cube is an interior panelled level n cube, along with exterior panelling, it’s easy to count. There are 6 exterior faces, each requiring F_n=8^n cards to panel, so P_n=I_n+6\cdot 8^n.

So we’re down to two formulas:

\begin{array}{rcl}I_n &=& 20\cdot I_{n-1}+24\cdot 8^{n-1} \\ P_n &=& I_n+6\cdot 8^n\end{array}

At this point, I checked Hull’s book, and noticed he had only one formula – one for P_n. So how do we get rid of I_n?

Solve the second equation for I_n, obtaining I_n=P_n-6\cdot 8^n (and so also I_{n-1}=P_{n-1}-6\cdot 8^{n-1}). Now substitute these two formulas in their appropriate places in the formula above for I_n. This gives

P_n-6\cdot 8^n=20(P_{n-1}-6\cdot 8^{n-1})+24\cdot 8^{n-1}

which we simplify to

P_n=20\cdot P_{n-1}-6\cdot 8^n,

obtaining the formula that Hull’s book has (hurray!).

Perhaps there’s something more than can be done to understand this formula though (and Hull does have remarks like this as well). I’d really like my recurrence formula for P_n to have (n-1)s showing up, instead of that n in the power for 8. So write P_n=20\cdot P_{n-1}-6\cdot 8\cdot 8^{n-1}. How can we interpret this formula geometrically, in terms of the sponge? Well, we see that to make a panelled level n sponge, we make 20 level n-1 sponges, and then remove some bits. In particular, we remove the panelling on faces of cubes that come together – that’s where the 8^{n-1} comes from, it is, after all F_{n-1}, the number of panels on a face of an n-1 sponge. How many faces come together? Well, each of the 8 corner cubes (that lonely 8 in 6\cdot 8\cdot 8^{n-1}) is 3-valent, meaning there are three ‘edges’ hitting that cube. At each of these 3 edges, we have two (3\cdot 2=6, in 6\cdot 8\cdot 8^{n-1}) panelled faces coming together, and we must remove all of that panelling.

So there you have it – a formula for the number of cards to build a level n Menger sponge. If you’re interested in building one, start gathering up cards. While the level 0 sponge (a cube) requires only 12 cards, a level 1 sponge already requires 192 cards. The level 2 sponge, that my roommate and I built, took 3456 cards, and the next level would require a staggering 66,048 cards. I’m in no hurry to start making one of those.