Archive for March, 2009

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.

A Continued Fractions Lemma

March 22, 2009

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 q_k(n)=[0;1,1,\ldots,1,n], where there are k copies of 1. So, for example,

q_0(n)=[0;n]=\cfrac{1}{n}

q_1(n)=[0;1,n]=\cfrac{1}{1+\cfrac{1}{n}}

q_2(n)=[0;1,1,n]=\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{n}}}.

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 q_{k+1}(n)=\cfrac{1}{1+q_k(n)}, 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 F_{-1}=0 and F_0=1, and then the usual recurrence, F_n=F_{n-1}+F_{n-2}, for n\geq 1.

Lemma: For k\geq 2, q_k(n)=\dfrac{F_{k-1} n-F_{k-3}}{F_k n-F_{k-2}}.

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 F_{-2} and maybe even F_{-3} might let this lemma work for k=0,1, but I think that’s not the case.

Hardy and Wright, Chapter 2

March 20, 2009

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 n^2-n+41. In particular, where did it come from? The book also mentions n^2-79n+1601=(n-40)^2+(n-40)+41. 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 0\leq n\leq 79, they are only the primes generated by n^2-n+41 for 0\leq n\leq 40. 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 F_n=F_0\cdots F_{n-1}+2, it is quite easy to see that F_n divides F_{n+k}-2, which seems to me to be the heart of the proof in H&W.

While H&W give the factorization of F_5 and F_6, 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 F_n is of the form k\cdot 2^{n+1}+1. According to these pages, this result, due to Euler, was improved by Lucas who noted that in fact k will be even, so the power of 2 is really n+2. 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 F_5=2^{2^5}+1=2^{32}+1. Since a factor must be of the form k\cdot 2^6+1, you can start picking values for k to find factors. Chris brought up the idea of asking how large a k you would have to consider. We decided that since \sqrt{F_5}\approx 2^{16}, you need to consider k up to about 2^{10}. Actually, we were getting 2^9 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 641=10\cdot 2^5+1 occurs before you try too many values for k.

Chris brought up something I had thought about as well just before the meeting, concerning the relation F_n=F_0\cdots F_{n-1}+2. This looks rather like the formula p_1\cdots p_n+1 which, when p_i denotes the i-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 a_1 and an integer k, consider the sequence a_n=a_1\cdots a_{n-1}+k. Besides (a_1,k)=(3,2), are there other values for a_1,k 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 a\cdot n-1 for various a. In H&W they prove that there infinitely many primes of the form 4n-1 and 6n-1. 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 a. 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 a 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 4n+1 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 p\equiv 1\pmod 4 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 p be prime came in. Of course, I have no idea where the involution g 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

March 17, 2009

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

My goal

The red lines are supposed to indicate that the curve is 0 at \theta=\pi/4 and \theta=3\pi/4. 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 f_1(x), and it looks something like the following, with 0s at \pi/4,3\pi/4, a min corresponding to the polar point (-3,\pi/2), and a max corresponding to the polar point (2,3\pi/2):

My (Cartesian) goal

My (Cartesian) goal

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

fooplot-f2

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 x=\pi, instead of at x=\pi/2. Let’s call the resulting graph f_3(x):

fooplot-f3

Now this, to me, looks like the plot of -\sin(x), 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 -a(x)\sin(x), where my amplitude function looks like:

fooplot-aThis is just the curve a(x)=2.5+.5\sin(x), so we have a formula for f_3(x). Namely, f_3(x)=-(2.5+.5\sin(x))\sin(x). Not terribly pretty, but manageable.

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

fooplot-sxo

Thus, I’ve found f_2(x)=f_3(x+o(x)), 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 \pi/4 to obtain f_1(x)=f_2(x-\pi/4), with graph:

fooplot-wrongf1

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

Let me plot the function f_1(x), obtained so far, on a wider domain:

fooplot-wrongf1-long

Notice that this looks like a piecewise function. It begins as a sin (sinusoidal, I guess) curve (with modified amplitudes) with period \pi, 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 s(x), and it’s accompanying o(x)=s(x)-x. Notice that the formula for o(x) is not periodic. It does what I want on the interval [0,2\pi], 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 f_2(x) to f_1(x). How can I take this function that I like on [0,2\pi] and extend it periodically throughout the whole real line?

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

The following plot contains the original o(x) (in green), the saw-tooth curve m(x) (in black), and the nicely periodic offset function \tilde{o}(x)=o(m(x)) (in blue, overlapped by green o(x) in the first positive interval):

fooplot-osawper

Now let’s go back and fix up our functions. The function f_3(x) was fine, it didn’t involve o(x). The definition of f_2(x) above was f_2(x)=f_3(x+o(x)), but that uses the non-periodic offset function o(x). I’ll replace it with it’s period cousin, \tilde{o}(x)=o(m(x)), so that f_2(x)=f_3(x+\tilde{o}(x)). This has the nice periodic graph:

fooplot-actualf2

Finally, f_1(x) was just a horizontal shift of f_2(x), so f_1(x)=f_2(x-\pi/4). This graph looks much better (it’s periodic, and not 2 at x=0).

fooplot-actualf1

Not only is it correct on [0,2\pi], but when plotted as a polar curve, it gives us what we were after all along:

fooplot-f1-polar

Hurray! Now, what are the coordinates of the intersection points (besides the origin)? Does the corner at \pi/4 (coming from the corner on \tilde{o}(x)) in f_1(x) mean this function has a discontinuous derivative? How could it be patched up? Would making o(x) 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

March 16, 2009

Suppose f(x) and g(x) are functions \mathbb{R}\to \mathbb{R}, and consider the piecewise function

p(x)=\begin{cases} f(x) & x<0 \\ g(x) & x>0 \end{cases}.

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 |x| to disguise the piecewise nature of the function. This can be further obfuscated by writing it as \sqrt{x^2}, but I’ll leave it as |x|. Actually, a function I think might be more useful is |x|/x, a favorite from calculus classes. Recall that this is 1 for x positive, and -1 for x negative. Conveniently, the domains of the pieces here are exactly the domains of the pieces I want for p(x).

My first step actually makes p(x) looks worse:

p(x)=\frac{f(x)+g(x)}{2}+\begin{cases} \frac{-g(x)+f(x)}{2} & x<0 \\ \frac{g(x)-f(x)}{2} & x>0 \end{cases}

However, let me write a(x)=(f(x)+g(x))/2 and d(x)=(f(x)-g(x))/2. Then notice that the pieces in the above line are exactly d(x) or -d(x). That is,

p(x)=\begin{cases} a(x)+d(x) & x<0 \\ a(x)-d(x) & x>0 \end{cases}

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

p(x)=a(x)-\frac{|x|}{x}d(x).

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

p(x)=(f(x)+g(x)-\frac{|x|}{x}(f(x)-g(x)))/2.

With this, I could then shift things horizontally and assume that my pieces where defined on (-\infty,a) and (a,\infty), 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 f(x) and g(x) need to be defined on all of \mathbb{R}, 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?