Hardy and Wright, Chapter 2

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.