Hardy and Wright, Chapter 3

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 ), 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 and in a Farey sequence is . Chris and I noted that this was obvious from the lemma that . 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 in , can you find the first for which has a new successor in ? What can you say about the sequence of all such ?” The book has a lemma about how to find the next term for in . Suppose that its successor is . By other lemmas in this chapter, the next time something comes between these terms, it will be the mediant, , and this occurs in . The next time will have a new successor, it will be the mediant of with this new term, , and so will be . Continuing on, we see that has a new successor in the Farey sequences .

Next, I talked about the Stern-Brocot Tree and Minkowski’s Question Mark function, . 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’ 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 . This has something to do with defining an appropriate measure so that is the integral (of… something. 1? ?) 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 .

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 are centered at -coordinates that are neighbors of in some Farey sequence.

A Continued Fractions Lemma

I was bored, recently, in a seminar talk, and didn’t have much in front of me besides a piece of borrowed paper. I figured I’d be too distracted to do real work, so started messing around with continued fractions. They’ve always appealed to me, and I’ve only recently started playing with them. So I’ve still got lots to learn. I sat down and just started writing out the continued fraction expansion of several rational values. And I started looking for patterns. I seem to have found one. It’s not exactly brilliant, but I did it myself, so I like it.

Let , where there are copies of 1. So, for example,

I wrote down several more, but that should give you a good place to start (and recall some notation, if you haven’t seen these recently).

It’s pretty easy to tell that , which gives a handy way to prove things about these things. After writing down several terms, I started seeing Fibonacci numbers pop up, and came up with the following.

Define the Fibonacci numbers with and , and then the usual recurrence, , for .

Lemma: For , .

This is pretty easy to show by induction, so I guess I’ll leave it as an exercise for the reader (hoping I didn’t make any mistakes). I had thought maybe defining appropriate and maybe even might let this lemma work for , but I think that’s not the case.

Hardy and Wright, Chapter 2

Not too long ago I decided it would be fun to read through Hardy and Wright’s “An Introduction to the Theory of Numbers” book (I’ll just say H&W from now on, and textual references are with respect to the 6th edition). I figured other grad students in the department might like to join me, and a few did. We’re thinking about maybe reading a chapter a week or so, with no particular goals in mind besides: “learn some stuff”. I know that I will learn quite a lot reading this book. But anyway, we had our first meeting today, and I thought I’d post some of the things we talked about. We didn’t talk, in particular, about much from chapter 1, but chapter 2 had several interesting things in it. I’ll work my way backwards through chapter 2, following how our meeting went. Our setup, as a group, is just to come in with whatever questions we had from the reading, and any outside information we looked into, inspired by the reading.

The first thing we talked about was prime generating functions. In particular, Chris mentioned that he was amused by the comment in the book about how the identity function generates all the primes. I commented that I was still in the dark about the prime generating polynomial . In particular, where did it come from? The book also mentions . I had seen that polynomial before, but only in the first form. From the second form, it’s fairly easy to see that it’s just a shift of the first quadratic, and that while it generates only primes for , they are only the primes generated by for . It just hits each of those primes twice, which the book doesn’t explicitly state, but I suppose is obvious enough (especially if you read it off Mathworld, which I believe I did).

We also commented on the existence of other prime generating polynomials, following what is mentioned in the Appendix. I seem to remember reading about one such polynomial with around 26 variables ([citation needed, my apologies]). The positive outputs of these polynomials are supposed to be primes, and the negative outputs composites. The challenge, wherever I was reading this, was that it was fairly difficult to see which inputs gave positive outputs. The Mathworld article on prime generating polynomials seems a good place to start finding out more.

Another big part of what we talked about was Fermat numbers. The text proves what is called Goldbach’s theorem (any two Fermat numbers are relatively prime) on the Wikipedia page on Fermat numbers, but I think the proof on the Wikipedia page is nicer. Using the relation , it is quite easy to see that divides , which seems to me to be the heart of the proof in H&W.

While H&W give the factorization of and , little mention is made about where these factorizations come from. The Wikipedia page linked above and the Mathworld page both mention that any factor of is of the form . According to these pages, this result, due to Euler, was improved by Lucas who noted that in fact will be even, so the power of 2 is really . I asked about the proof of this (Euler’s would be fine for me) result, but none of us knew it. I suppose I should look into it some more.

I though I had remembered that this result made it very easy to find the factors of . Since a factor must be of the form , you can start picking values for to find factors. Chris brought up the idea of asking how large a you would have to consider. We decided that since , you need to consider up to about . Actually, we were getting during our meeting, but I think we were off by one due to an error by me. I guess it’s nice, then, that the factor occurs before you try too many values for .

Chris brought up something I had thought about as well just before the meeting, concerning the relation . This looks rather like the formula which, when denotes the -th prime, is frequently used to show there are infinitely many primes. The thought I had was something like the following. Given a starting value and an integer , consider the sequence . Besides , are there other values for that give known, interesting, sequences? I may practice my python this weekend and generate the starts of some sequences for small values, and see if anything noteworthy pops up.

Next we talked about primes of the form for various . In H&W they prove that there infinitely many primes of the form and . The proofs they give rely on the fact that, mod 4 or mod 6, the only way to get a product equal to -1 is to use a -1 somewhere. I had wondered (rather naively, apparently) if this same proof extended to other values of . However, mod 5 you can get -1 with two 2s (as Andy pointed out), and mod 7 you can get -1 with 2 and 3. My next (again, naive) thought was maybe for even it worked, but mod 8 you can get -1 as 3 and 5. So, no luck there. What’s the general proof then? This is a case of Dirichlet’s theorem, which the book mentions (and they point out that the proof is too hard to include in this book). According to the book this is an easy case. Something more for me to look into I guess.

Finally, I brought up this wonderful proof that every prime of the form is the sum of two primes. Mostly I brought it up because I hadn’t been able to follow the whole thing. What’s funny about that is the original paper it was published in is titled “A One-Sentence Proof That Every Prime Is a Sum of Two Squares.” So I couldn’t even make my way through a one-sentence proof . Of course, those are generally the most dense. But with a little talking things out, Chris and I got things sorted. And I finally saw where the assumption that be prime came in. Of course, I have no idea where the involution in that paper (or blog post) come from, but I printed out Heath-Brown’s paper “Fermat’s Two Squares Theorem” paper, found from this Wikipedia page, so perhaps I’ll gain some understanding from that. After figuring out this proof, Chris presented the proof given in an Algebra course he took a few years ago, using Gaussian integers.

All in all, a pretty good first (non-organizational) meeting.

A Polar Curve

So I suppose, if I’m being honest, my post from earlier today about piecewise functions wasn’t entirely self-motivated. In all honestly, I sat down and was inspired to find a formula for a new polar curve. I’ve done similar things before. Today’s goal was to find a formula for a polar curve like the following:

My goal

The red lines are supposed to indicate that the curve is 0 at and . My goal in drawing this curve was to find something that looked like a limacon, but had self-intersections away from the origin. It’s a happy coincidence (in my mind, anyway) that the result, when crossings are properly applied, is a trefoil knot.

So, anyway, how to find a formula for my function? The first step, for me, is to unroll it back to a Cartesian form. I’ll call it , and it looks something like the following, with 0s at , a min corresponding to the polar point , and a max corresponding to the polar point :

My (Cartesian) goal

Next, I know that shifting functions horizontally isn’t too hard, so let me shift left by , obtaining a graph like the one above, except passing through the origin. Let’s call this :

As a third change, though one that’s trickier to sort out algebraically (I’ll do it below), I’ll make the graph more symmetric by assuming the second 0 occurs at , instead of at . Let’s call the resulting graph :

Now this, to me, looks like the plot of , except for the fact that the amplitude is 3 on the first half, and only 2 on the second half. So let’s call it , where my amplitude function looks like:

This is just the curve , so we have a formula for . Namely, . Not terribly pretty, but manageable.

Now, how do I do that change that took me from to ? Since the graph of is obtained from the graph of by some sort of horizontal manipulations, I know for some function . What does look like? Well, it sends 0 to 0, and to , and also sends to . That gives me three points, , , and on the graph of , and I’ll define to be the piecewise linear function connecting them. Because I think maybe it’ll be handy, let me set . From my work on piecewise curves in my earlier post (and a handful of algebra and horizontal translations), I know I can write . The following graph shows (in black), (in red), and (blue):

Thus, I’ve found , something I can write out fully if I want (it’s getting to be a pretty long formula). Finally, I shift this graph over to the right by to obtain , with graph:

Oh no! That’s not the graph I was expecting at the beginning. My Cartesian goal didn’t hit 2 at . What happened?

Let me plot the function , obtained so far, on a wider domain:

Notice that this looks like a piecewise function. It begins as a sin (sinusoidal, I guess) curve (with modified amplitudes) with period , and then shifts to one with a larger period. I would have probably hoped that the curve I was going for was just going to be periodic itself, so that if I extended the domain in the polar curve, I’d just end up tracing out the trefoil again.

The problem stems from my linear shift function , and it’s accompanying . Notice that the formula for is not periodic. It does what I want on the interval , but outside of that, it’s negative. That’s not what I wanted, and it matters because I shift some of these negative bits into the picture with my final shift from to . How can I take this function that I like on and extend it periodically throughout the whole real line?

Let me define another function, , which computes ““. Usually, I expect the modulus of a number to be taken with respect to an integer, not . All the same, we can make it work. The function can be written as (here is the “floor” function, returning the greatest integer less than ). The graph of this function is a saw-tooth curve. Of course, I don’t want ““, but ““. I just modify with some factors of , obtaining .

The following plot contains the original (in green), the saw-tooth curve (in black), and the nicely periodic offset function (in blue, overlapped by green in the first positive interval):

Now let’s go back and fix up our functions. The function was fine, it didn’t involve . The definition of above was , but that uses the non-periodic offset function . I’ll replace it with it’s period cousin, , so that . This has the nice periodic graph:

Finally, was just a horizontal shift of , so . This graph looks much better (it’s periodic, and not 2 at ).

Not only is it correct on , but when plotted as a polar curve, it gives us what we were after all along:

Hurray! Now, what are the coordinates of the intersection points (besides the origin)? Does the corner at (coming from the corner on ) in mean this function has a discontinuous derivative? How could it be patched up? Would making as a quadratic function (I’ve got 3 non-colinear points, which determine a quadratic) work well? Can the symmetry be improved? Perhaps by picking other angles where the curve is 0, or different amplitudes for the inner and outer loop (2 and 3, respectively, in the example above)?

I don’t know the answers to any of those questions. Some I have worked a little on (the last one, since I could do lots of nice plots if I set things up in enough generality in Maple), others, though interesting (points of intersection), I have not.

By the way, I made all of my graphs at fooplot.com (which I’ve used lots, it’s nice).

Piecewise Functions

Suppose and are functions , and consider the piecewise function

For no particularly good reason, today I went in search of another way to write this expression. I wasn’t sure exactly what sort of expression I was shooting for, but I hoped I’d know it when I saw it.

I’m want to try to avoid explicitly writing a piecewise function, and somehow use to disguise the piecewise nature of the function. This can be further obfuscated by writing it as , but I’ll leave it as . Actually, a function I think might be more useful is , a favorite from calculus classes. Recall that this is 1 for positive, and -1 for negative. Conveniently, the domains of the pieces here are exactly the domains of the pieces I want for .

My first step actually makes looks worse:

However, let me write and . Then notice that the pieces in the above line are exactly or . That is,

I can wrap this up using my from above to get that sign distinction, arriving at

That’s a reasonable answer I suppose. I’ve written my piecewise function all on one line, I guess, as

With this, I could then shift things horizontally and assume that my pieces where defined on and , instead of just splitting at 0. I could also, sort of inductively, get a piecewise function with more than 2 pieces. To do this, just split it into a leftmost non-piecewise function, and then a right-hand piecewise function, and use the ideas above.

I don’t think that this is the answer that makes me the happiest though. But it’s the only idea I’ve got currently. The reason I don’t like this is that and need to be defined on all of , even though in the original piecewise function they need only be defined on half the line. Also, I’m not sure I’m a huge fan of the handling of more than 2 pieces with the above method.

So, what suggestions have you got for improvement?