Finale!

I think I’m about ready to tie together Farey sequences and the Riemann zeta function (specifically, the Riemann hypothesis). I know there were lots of gaps along the way, and lots more to explore from here, so that all gets to be the dénouement, if/when I get to it.

Yesterday we ended with the identity

Define , which you might call the cumulative Möbius function. If you are comfortable with your measure theory, you can decide that there is a measure, which I’ll denote , such that . And if you’re ok with that statement, you probably also don’t mind writing the identity for the reciprocal of zeta, above, as

If you then integrate by parts you find that

Now if (we could say something more like ) for some positive real value , then this most recent integral will converge for . Which means that would have no zeroes in the half-plane . Since there are zeroes on the critical line, where , we know that no value of less than 1/2 will work. But if you can show that for every positive , then you’ll have proven the Riemann hypothesis (and earned yourself a cool million).

Ok, so now we just have to relate the Farey sequences to this somehow.

It’s been a while, so perhaps we should recall some basics about the Farey sequences. The -th Farey sequence, denoted consists of the reduced fractions in with , ordered as usual. For today, let’s actually remove 0 from the sequences. Thinking about how many terms are in , we quickly determine that there are , where is the number of positive integers less than that are relatively prime to (with ). Let me call this sum , so that has terms.

To keep my notation under control, fix an . Then for , let be the -th term in the Farey sequence . The terms in are not equally spaced in , so let us also consider the sequence of equidistant points in . These will be the values . We’re interested in how far the Farey sequence is from this equidistant sequence, so let’s set .

If , then you can show (essentially by Möbius inversion) that

The idea is that the function that is 1 for and 0 for is also

because you can write (fairly cleverly, I feel)

By the way, I’m being a bit loose with my values of these stepwise things when they actually make their steps. Apparently the convention is to define the value at the change to be the midpoint of the values on either side. I feel like it’s a technicality I’m not hugely interested in right now.

Now we apply this identity to , obtaining

That inner sum on the right-hand side is the sum of unit vectors equally distributed around the unit circle, and so is 0 except when . So we obtain

Finally, replace with . After shuffling some symbols around, you can write

Taking absolute values on each side, using the triangle inequality, and the identity we already used about sums of equally spaced unit vectors, we can write

Using our lemma from earlier, about how to obtain the Riemann hypothesis from , we have, at last:

If is for every , then the Riemann hypothesis is true.

Hurray! The result that encouraged me to wander down this path!

So, that was fun. It turns out that both of today’s results that imply the Riemann hypothesis are actually equivalent to the Riemann hypothesis, but perhaps that’s a topic for another day…

[Update 20091203: Noticed I had some absolute value bars in the wrong places in the line before the final theorem, and corrected them (hopefully)]

?(x)

Sorry about the lack of a MaBloWriMo post yesterday. I got a little behind, left resources I wanted at the office, and did some other things.

If you remember, my original goal in this process was to relate the Farey sequences to the Riemann hypothesis. I have some vague understanding that the relationship is based on the distribution of the terms in the Farey sequence, as points in the unit interval. It’s getting on toward time to talk about the Riemann hypothesis side of this picture, so I can start relating the two. But before I do, there’s one more diversion (hopefully it isn’t too far off base) I’d like to make related to Farey sequences. I’ve still got some learning to do about it, but let’s see what I can get down today, laying some foundation for the next day or two, perhaps.

Recall that the way to construct one Farey sequence, , from the previous one, , is to throw in all of the mediants of successive terms whose denominators aren’t too big. What if we didn’t bother with that last part, and just left in all the mediants? All the numbers we’ll write down are still reduced, and we’ll obtain all of the fractions in this way, because they all show up in some Farey sequence, and we’re getting all the terms in all the Farey sequences, just sometimes a little earlier than Farey would.

Just to be clear, our first few sequences now look like this:

and so on. We see that the -th sequence in this list contains all of , as well as some other numbers with bigger denominators. A nice property of these sequences, which isn’t shared with the Farey sequences, is that every other term in the -th sequence is a new term that wasn’t in the -st sequence. So when I go to make the next sequence in this process, I’m always taking the mediant of a “new” number and an “old” number. Moreover, each “new” number will be involved in two mediants… one taken “to the left” (with the “old” number on the left, making a smaller value) and one taken “to the right”.

This language let’s me write down a binary tree (every node has two branches down) as follows: Begin with 1/2 as the root (at the top, I’m throwing out 0/1 and 1/1). This is a new fraction in the second sequence above, so to make the third sequence, I added in the “left mediant” (1/3) and “right mediant” (2/3) from 1/2. To make the sequence after that, 1/3 gives a “left mediant” (1/4) and a “right mediant” (2/5), and similarly 2/3 spawns 3/5 and 3/4. So I build up a tree that looks like this:

I’ll call this the Stern-Brocot tree, though the actual definition my be slightly different.

Another way I could build up a sequence of sequences, and generate another binary tree, is to use midpoints, instead of mediants. If my first sequence is still 0/1 and 1/1, then taking midpoints will always give me denominators that are powers of 2. My tree will now look like:

I could now line up these trees, and determine a function that takes one rational number, finds it’s position in the first tree, and spits out the value in the same position from the second tree. For example, using our pictures above, we see that this function will take 3/5 to 5/8. This function is known as Minkowski’s question mark function, , and Wikipedia has a graph, so you should click that last link. I’ve only defined it on rationals, but you wave the “continuity” wand to extend my definition to a function on .

So, to evaluate for some rational, you have to find that rational in the Stern-Brocot tree. How do you do that? You know that you don’t have to go further down in the tree than your denominator, but that’s still a lot of fractions to look at, potentially. Perhaps there’s a better way?

I guess one way is to play the over-under game. Start at 1/2. If that’s your fraction, you are done. Otherwise, if your fraction is bigger, move right, and if your fraction is smaller, move left. Repeat until you get to your fraction.

But there’s more math we can say if we think about this process slightly differently.

The point of the tree being a tree is that there is only one way to get from the root, 1/2, to any fraction. Working your way down, you make a sequence of moves, either left () or right (). So you generate some string – , for example. Of course, that notation gets out of hand quickly, so we might also use exponents to write this example as . To such a string we can associate a sequence of fractions by writing down whatever fraction we are at when we change direction. Let us write this sequence as , and call these “turning points”. I’ve used primes here, because the numbers I’m actually interested in are one before I make a turn. Let me call that sequence , calling these values parents (so has a line directly down to in the Stern-Brocot tree, connecting the two). So, for example, the sequence has turning points , , and finally and associated parents , , and .

What is the relationship among successive turning points and parents? Suppose you are at the turning point , with parent , looking to get to the next parent or turning point, and are going to do this with a sequence of moves (left or right, it doesn’t actually matter). The next parent will be the weighted mediant of the turning point with its parent . That is, , and . Similarly, the next turning point will be the weighted mediant of with . This also means that it is the weighted mediant of with .

Combining all of these relationships, messing with the algebra just slightly, you can determine that and . You may recall that these are exactly the relations between the convergents of a continued fraction (if you start putting subscripts on your , writing it as ).

So, given a continued fraction for a rational in , begin at 1/1 (which isn’t in the tree, I know) and move left times (the first move getting you to 1/2), then move right, and so on. In your final step, you only move (if you wonder about the “-1″, you might think that the -th convergent is the fraction you are after, and that is the -th parent, not the -th turning point), and you’ll arrive at . On your way, all of the fractions that you hit, one before a turning point, will be the convergents to .

That only gets us half-way into evaluating , for this rational you’ve picked. You first find its continued fraction and then, by the process above, you’ll see how to get down to from the top of your tree. That means will be the value in our second tree (taking averages, the tree with powers of two in the denominator) that follows the same path. The initial lefts, from 1/1, will get us to a value of . Then we are supposed to take rights. Taking 1 right will get us to . Another right will then be , which I’ll write . Yet another right gets us to , and so on, until . After that, we move left times. The analysis of where we end up is basically the same, you just have to remember that you are subtracting s, instead of adding them.

Putting this all together, we obtain (remembering that in the last stage we only went moves.

Just as a warning, I may be off slightly in some of my formulas. I haven’t written down anything knowing that it was false, but I’m not convinced I obtain the correct formula at the end of the day (it looks slightly different from the formula at Wikipedia, for instance). If anybody sees an error, please let me know.

That’s probably plenty for today. Up next (I think), I want to take the derivative (even though I can’t) of , because Wikipedia thinks I’ll get something related to the density of the Farey sequences.

By the way, a paper I was looking at to figure out about these things was “The Minkowski Question Mark, and the Modular Group (Expository)” by Linas Vepstas. The printed copy I have, from some time summer 2009, is incomplete, but it looks to be available online.

Ford Circles

Now that we’ve got some foundations laid for Farey sequences and rational approximations, let’s put pictures to some of those claims, via Ford circles.

For every rational , in reduced terms, draw a circle in the plane with center and radius . I’m not going to try to come up with a better picture for you than the one used on the Wikipedia page for Ford circles. (I tried embedding the picture below, but that didn’t work. So I’ll leave it to you to click the link.)

What’s so great about this construction? Well, you may recognize those radii as the error term in our discussion of rational approximations. The statement that for every irrational there are infinitely many reduced fractions such that is the same as saying that the vertical line intersects infinitely many of the Ford circles. The improved bound can also be found by (very carefully) analyzing vertical lines passing through Ford circles (more specifically, the gaps between them), but I think for now I’m going to let that statement be for now. If you want, the proof via Ford circles is in [Rademacher], and a proof via continued fractions is in [Hardy and Wright]. The result is known as Hurwitz’s theorem.

What else can be said about Ford circles? Well, yesterday I was talking about neighbors in Farey sequences. It turns out that and are neighbors in a Farey sequence if and only if the Ford circles at and at are tangent to each other.

To see why this is true, consider the circles at and , with so ). Since we know the location of their centers, we can find an expression for the distance between those centers. The two circles will intersect iff the distance between the centers is no bigger than the sum of the radii of the two circles. Re-arranging terms (and working with squares to avoid square roots), you might look at , where is the distance between the centers, and and denote the (hopefully obvious) radii. The two circles will be tangent if this is 0, and won’t intersect if the difference is positive. More care needs to be used when talking about what happens if the difference is negative, but we’ll see momentarily that this doesn’t happen, so let’s forget it. So, it turns out that is . Since all the letters there are positive integers, we see that , with equality iff . This says, based on our work yesterday, precisely that two Ford circles intersect iff the fractions they correspond to are neighbors in a Farey sequence, and when this happens, they intersect at a single point (they are tangent to eachother).

This justifies the picture from above, then. The circles never overlap, and some of them are tangent.

It might be worth it to go back and justify why any vertical line at an irrational value slices through infinitely many of the Ford circles. To that end, let be irrational. The two circles at and both have radius 1/2, and so certainly hits at least one Ford circle, kicking off an induction argument.

Suppose that hits the Ford circle . For the sake of argument, let us suppose that , so the vertical line lies to the right of the center of the circle. Not much changes if the opposite inequality is true, so let’s just stick with this one. I aim to show that hits a circle with a smaller radius, i.e. goes through a circle corresponding to a fraction with a bigger denominator than . I claim that it hits one of the circles tangent to the circle at . By the above, we know that these are the circles corresponding to neighbors of in some Farey sequence. Since I’m thinking about circles to the right of , these will be successors in the Farey sequence. Yesterday we said that all of these successors are -weighted mediants of with where is the successor of in (the first Farey sequence that shows up in).

Consider, then, the circles corresponding to the (1,1), (2,1), (3,1),… weighted mediants of with . Let me call the circles , using for the circle at . It isn’t too much work to check the necessary inequalities to show that the center of is further right than the right-most point on . I’ve already said, even if not directly, that for each , is tangent to . So, if you want, you may start at the top of , and move left along the tops of all the circles in turn, jumping from one to the next at points of tangency. How far can you go doing this? Well, if you take the limit as of the -weighted mediant of with , you get (l’Hospital!). So, the tops of the circles form an unbroken path from the top of to as close to , on the right, as we care to get. The vertical line , which passes through the right side of , must surely pass through this path, and therefore at least one of the .

That’s probably just about enough with Ford circles for now. I’m not sure what I’ll be writing about tomorrow. Hopefully something else fun. I would like to note that, as I was writing this post, I was excited to find a connection to continued fractions. I knew a connection should be there (and I’ll probably find plenty more later), and found it while asking “how can we tell which of the does pass through?”. I remembered from reading about continued fractions, , that the “convergents”, are rationals that give “best rational approximations”. Those should be the circles that passes through, or so. And so if you pass through , the next circle you should get to is . Well, it turns out, there is a nice relationship between successive convergents. Namely, and . Look at that! It’s the -weighted mediant of with ! Fantastic. Could this story get any better? I’m glad I’ve decided to find out this month.

Neighbors in Farey Sequences

I was reading about Ford circles today, and was planning on writing about them. But then I noticed that one of the things I wanted to say was based on some things I didn’t say about Farey sequences when I talked about them a few days ago. So I thought I’d go back and fill in that gap, and save Ford circles for tomorrow.

So what did I skip? Well, I mentioned that to get from one Farey sequence to the next, you throw in mediants whose denominators aren’t too big. Is there a way, given a fraction in to figure out what terms in it was the mediant of? Well, we could, of course, list the terms in , in order, and then pick the two that surround the value . I’m after another way.

Since is supposed to be reduced, and are relatively prime, and so there are integers and such that (this usually (in my mind) gets written with a “+”, not a “-”, but just change the sign of your ). Once you’ve found such a pair , all of the other pairs that satisfy the same equation are of the form , where is any integer. Among the , there is only one in the interval . Abusing notation a bit, or assuming you picked well to start, let’s call this value , and its partner . I claim that is the term directly before in .

Before talking about , I should have checked that . If this is not the case, then means , in which case we are in which is just 0/1 and 1/1. Not much interesting going on there. So let’s go ahead and assume .

Now, the linear equation gets re-written to show that (so the fractions are at least in the correct order). Messing about with inequalities some more, you can check that , and since and are relatively prime (they satisfy the linear equation), the fraction is actually in . Let be the predecessor of in (we want to show ). Since it is a neighbor, we showed last time that then . But now we’re saying that all solutions of the equation have a fixed form. That is, and for some integer . But if then is not in , and so is not in . So and , and we’re done.

Man, ok, so, after all that, we now know how to find the term before in . I’ll call it , sticking with our notation above. What about the term after ? You could play mostly the same games as above, I suppose. Or, if the successor is , then we know that and , since we made as a mediant. So and , easy enough. [Update 20091109: You have to be careful with this. The above method for finding the successor to in only works because you are in . If you look for successors in in , where , this method, using the predecessor, is wrong. For example, 1/4 is the predecessor of 1/3 in , but the fraction (1-1)/(3-4) suggested by the previous method is clearly NOT the sucessor of 1/3 in ]

So we know the neighbors of in . What is the next Farey sequence when gets a new neighbor? Let’s stick to the next time it gets a new neighbor “on the left” (less than itself). We know that when that happens, it had to be because we made the mediant with the old neighbor, our friend . So the next neighbor is , which doesn’t show up until . The newest neighbor after that will be the mediant with this new neighbor, i.e., , in . Continuing on, we see that all of the neighbors are of the form , for some positive integer . I called these -weighted mediants (of and ) yesterday.

The story goes pretty much the same on the right side. I called the neighbor on the right, in , . The next neighbors will be , , etc. These are the -weighted mediants of and .

We can put both of these into the same statement by noticing that the mediant of with is the same as the mediant of with . In other words, all of the neighbors of , in all of the Farey sequences, can be written as weighted mediants of with . They will have numerators of the form and denominators of the form . Guess what? These are exactly all of the solutions to . Go back a few paragraphs, it’s the same thing I said there.

In summary, the neighbors to , in any Farey sequence, are in one-to-one correspondence with solutions to .

If I knew what I were doing, I could probably have gotten to this statement a bit more quickly. But I don’t remember the last time I knew what I was doing, so there you have it.

Rational Approximations

Suppose is an irrational in the interval , and fix a positive integer . Let’s see what I can say about rational approximations to whose denominator is no bigger than .

First of all, lies in one of the intervals , where . Since is irrational, it won’t be an endpoint of such an interval, nor will it be the midpoint. Which is to say, it is closer to one end than the other. More explicitly, we can say that for some .

Instead of requiring the denominator of a rational approximation to actually be , what if we just ask that it be no bigger than ? Then we’re asking how well rationals in the -th Farey sequence, , approximate .

Instead of thinking about , let’s multiply everything by , and so look at (we’ll divide by that again soon enough). So now we’re not asking about rational approximations, as such, but asking about pairs of integers, and with , so that is “pretty close” to the integer .

Let’s re-phrase once more. Consider all of the multiples of . All of these are irrationals, but could now be bigger than 1 (our original was less than 1). I don’t want to think about things bigger than 1, so let me trim all of these multiples down to just the “fractional part”. Which is to say, I’ll now think about all of the values (the “floor” notation picks out the “greatest integer less than”), which are all irrationals in the interval . Now for each I have an integer , and let me denote this integer by . You might note that is always less than .

So now I am thinking about the irrational values in the interval . I’ll think about them in comparison to the rational points , like I did before. Following Rademacher (as most of my content has been and will be), we distinguish two cases.

1. Suppose some falls in the interval . Then , and so (since ).
2. If is free of our points, then by the pidgeon-hole principle, some interval contains two values, say and (arrange notation so that , forcing also ). Then , which we re-arrange to say that . Letting and , we have , which we again re-write, as in case (1), to say that .

We have, therefore, improved the “order” of our approximation. To begin with, we said that rational approximations could be found with . I think of this as a “order 1″ approximation, since the denominator of the error is a linear function of the denominator of the rational approximation. We have now improved this so that , which I would therefore call an “order 2″ approximation. If you are a little more careful with your inequalities, you can improve the bound to (an error that I think I’ll probably end up mentioning again tomorrow), basically for the same reason there is a coefficient of 2 in the order 1 approximation, I guess.

I should probably be a little (a lot) more careful in what I am saying with the above. I chose an irrational and an integer , and said that an “order 2″ rational approximation could be found. The stronger claim is that, in fact, infinitely many order 2 rational approximations can be found, if you let increase. Suppose your first order 2 approximation gives you , when you have bounded the denominator by . Find a new so that . Then go through the process above, using as the new bound on the denominator. When you find with that process, then you’ve found a new rational approximation (since it is closer to then was) that is still order 2 (since that’s what the process does for you).

So, can order 2 be improved on? Can you find order 3, or higher? It turns out, “no”, in general (and the golden ratio is an example). You can improve the coefficient of 2 in the order 2 approximation to , but that’s apparently the best you can do, in general. There’s more than can be said along these lines. The Roth-Liouville irrationality measure might be fun to talk about (it earned Roth a Fields medal, so it must be ok), as would continued fractions. I’m not sure how much these are related to my stated goal of understanding the link between Farey sequences and the Riemann hypothesis, so for now, perhaps I’ll leave them alone.

For some reason, I thought it might be fun to make a visualization about rational approximations using . Here is a picture of the rationals in , as a subset of :

Here’s a graph of the function taking to “the rational in closest to “:

Farey Sequences

Ok, so if I’m going to talk about Farey sequences and the Riemann hypothesis for MaBloWriMo, then Farey sequences are probably a good place to start.

Let us say that the -th Farey sequence is the sequence of fractions where and and are relatively prime (so that is in “lowest terms”). Let’s denote this sequence by . The first few are:

.

There’s sort of a nice way to get from one Farey sequence to the next: add fractions incorrectly.

The mediant of the fractions and is defined to be the fraction . It turns out that the mediant of two fractions always lies between them, which you can check by taking differences and noticing they have the correct sign. Now, to make the sequence , knowing the sequence , you simply include all the existing terms, and any mediants of successive terms that have a denominator no bigger than . So, for example, consider above. We consider the fractions obtained by adding to this sequence the mediants:

and then we throw out any fraction whose denominator is bigger than 5, giving us

.

There’s a little something to worry about in this process. Well, probably a few little somethings. The one I’ve got in mind is: are the mediants always reduced? However, you might also ask: are we sure we get all of the fractions this way?

To begin to answer these, let me change the subject. Look at any of the Farey sequences listed above, and pick any two successive terms in that sequence. Call them and , and let’s say that we’ve picked out indices so that . Now compute . Done? You got , didn’t you? This happens no matter what Farey sequence you are in, and no matter which successive terms you take. You always find that, with the notation above, . This is fairly interesting.

We already knew that, for example, and were relatively prime. And for a pair of relatively prime integers, there always exist integers such that . Conversely, if you can find such a pair of integers, then and are relatively prime. What’s perhaps a little surprising is that, in this case, the and happen to show up in the next term of the Farey sequence: and .

Armed with the observation that the difference between successive terms has a 1 in the numerator, in even just the first Farey sequence, , we can proceed by induction on to show that if are successive terms in then: (1) , and also (2) the mediant of these fractions is reduced. Therefore, if the mediant has a denominator no bigger than , it will get included in .

Does this process of expanding one Farey sequence to the next by throwing in mediants actually give us all of the terms of the next Farey sequence? That is, if is a fraction in reduced form, is it the mediant of two successive fractions from ?

Let me answer that by considering what I’ll call weighted mediants (a name I just made up, it may or may not show up in your favorite reference). Let me say that the -weighted mediant of fractions is the fraction . I’ll assume . So, for example, the normal mediant, defined above, is just the -weighted mediant. I claim that: (1) every weighted mediant lies between the two original fractions, (2) every fraction between two successive terms in a Farey sequence can be obtained as a weighted mediant.

Claim (1) is easy, just take appropriate differences and note that they have the appropriate sign, as before. For claim (2), suppose , where are successive terms in a Farey sequence, so that . Our goal is to find so that and . The assumption means that we can, indeed, find integers satisfying this condition, namely: and .

So, back to the question about obtaining every fraction in by taking mediants from . We need to show that if and is relatively prime to , then is the mediant of two successive fractions in . Well, certainly lies between two of them, say and in keeping with our notation, and we have just shown that it may therefore be obtained as some weighted mediant (we want it to be the -weighted mediant). Since the denominator of the -weighted mediant is , the smallest denominator is obtained only with the -weighted (i.e., normal) mediant. This denominator must be at least , because otherwise the fraction would show up in some Farey sequence before . As is obtainable as a weighted mediant, it must be the -weighted mediant, which is what we wanted to show. Let’s call it a day.

MaBloWriMo

I’m at least a day behind, but I’m thinking I might try this “Math Blog Writing Month” suggested by Charles Siegel over at Rigorous Trivialities.

A few months ago I was reading Hardy and Wright’s “An Introduction to the Theory of Numbers” with some friends. While that reading seems to have ended (we made it further than originally expected, to be honest), there was a topic I read about that I decided I wanted to learn more about. When H&W covered Farey sequences, I checked out the Wikipedia page and was fairly delighted to find that there is a statement about Farey sequences that is equivalent to the Riemann hypothesis (RH).

I know nearly nothing about the RH. You take a function defined by an infinite series, extend to the complex plane, notice that the zeroes have to lie in a particular region, and then the claim is that you can narrow down that region even more. Great. Why do I care about the zeroes of this function? Oh, right, because they are related to the distribution of the primes. And how is that again? I have no idea. Probably I should be embarrassed about this, being a math graduate student and not knowing the math behind the most famous open problem.

Well, now seems like as good a time as any to learn more. Farey sequences look fun, and close to some pretty pictures (Ford circles and the ? function). And so my plan is to learn enough about all of that, and the RH, to see if I can understand the relationship between the two. Not so that I can try to prove RH, mind you (I seriously have no delusions about this). It just seems like a fun thing to learn about. Plus maybe it’ll give me an excuse to give a talk in my department’s “graduate seminar”, which I always think is a fun thing to do.

I’ve got a few sources that I plan on looking at (and, indeed, have already been looking at). I found Rademacher’s “Higher Mathematics from an Elementary Point of View” to be quite delightful, and it contains information about the Farey and Ford part of the story. Of course, H&W might also help out here. I’ve got some papers tucked away somewhere I may dig up as well, and when I do, I’ll mention them. And, on the Riemann side of the story, I think I’ll look at Edwards’ “Riemann’s Zeta Function”, which has a section on the connection with Farey sequences.

I figure I’ll try to read at least a little bit every day, and share what I come across here. Perhaps in a month I’ll have some vague understanding (goal: less vague than it is now) about what’s going with the topic. Or perhaps I’ll crap out after a week (or less). But for now, let’s say I’m trying. Starting off a day late (and with an essentially non-mathematical post) means I probably should try to find a day or two and write more than one post. We’ll see. Also, I don’t expect I’ll get close to the 1000 word mark very often. We’ll see.