Posts Tagged ‘number theory’

Hardy and Wright, Chapters 12 and 13

June 27, 2009

Guess I kept getting distracted from posting about our meeting last week about Chapter 12. So here it is (what I remember of it – that was a long time ago), with notes from today’s meeting as well.

Honestly, we didn’t talk too much about the content of chapter 12, directly. The three of us were fairly comfortable with most of it from our algebra classes a few years ago. But Chris asked “How many of these quadratic extensions are Euclidean domains?” He had looked into this before the meeting, and found that it is an active topic of research, and that some results are known. I pointed out that we’d get to see some of them in Chapter 14.

Eric mentioned that the norm N(a+b\sqrt{m})=a^2-mb^2 could be attained in a more general fashion. Namely, these sets of “numbers” are elements of degree 2 extensions of \mathbb{Q}. That means they are a 2 dimensional vector space over \mathbb{Q}. And each element a+b\sqrt{m} acts on that vector space as a linear transformation. By writing down a matrix for that transformation and taking it’s determinant, you recover the norm. He thought these ideas had further generalizations, but I don’t remember how much he told us about.

I do remember him telling us that this result that 1-\rho is a prime (\rho being the primitive third root of unity, prime in what HW denote k(\rho)) was also somewhat generalizable. Somehow, 1-(thing) is often a prime, or so he said. I tried thinking about 1-\rho in the complex plane, but had no idea what the geometry would tell me about it being prime, or vice-versa. Eric and I talked about it and the relation to the hexagonal lattice, but didn’t get too far.

So that was what our talk inspired by Chapter 12 covered (at least, that’s what I remember of it). Today, Chris and I met and talked briefly about Chapter 13. Again, neither of us had too much to say specifically about the reading. I mentioned that I had just used the results about all the Pythagorean triples to solve a Project Euler problem.

From the chapter notes, I saw that the result about x^3+y^3+z^3=0 having no integer solutions was given as an exercise in something by Landau. I asked Chris if he knew how to phrase any of it in terms of ideals, since he’s an algebraist, but he didn’t. I also asked if some of the manipulations in 13.6, specifically the dividing by Z at some point, was inspired by some sort of projective space to affine space conversion. Dividing by capitals Zs apparently makes me think that. Chris allowed how it might be the case, and that algebraic geometry probably could come in here. But neither of us really had much specific to say.

Finally, I relayed the historical anecdote about the integers that are the sum of two cubes in two different ways. The story about Hardy visiting Ramanujan in the hospital, saying that his cab number (1729) wasn’t particularly interesting, and Ramanujan pointing out that it was the smallest integer expressible as the sum of two (positive) cubes in two distinct ways. I didn’t relay how I remembered noticing that 1729 was one of the house numbers in the movie Untraceable. I don’t know if they did that on purpose or not, but it’s there.


Hardy and Wright, Chapter 11 (part 2)

June 16, 2009

Today we finished off Chapter 11. We worked through some of the proofs, and discussing the meaning of some of theorems, and a good time was had by all.

In 11.10 it is mentioned that there are some notable constant multiples besides \sqrt{5} and 2\sqrt{2} in the bounding inequalities on approximating irrationals by rationals. However, the text doesn’t mention what they are, which I thought was unfortunate. I also wondered what sort of numbers are the troublesome examples for the constant 2\sqrt{2}. That is, the troublesome number for \sqrt{5} is the golden ratio (or anybody whose continued fraction ends in a string of 1s), so what numbers do it for 2\sqrt{2}. I think we decided that probably it was not a single number, but more like… any number whose continued fraction expansion is just lots of 1s and 2s. The more ones, the worse the number, in some sense. But as long as there are infinitely many twos, maybe you start running into, or getting close to, this 2\sqrt{2} bound.

We talked a little bit of our way through the proof that almost all numbers have arbitrarily large “quotients” (the a_n in the continued fraction). I tried to dig up some memories from my reading of Khinchin’s book about how to picture some of the intervals and things in the proof. I have this pictures in my head of rectangles over the interval [1/(n+1),1/n] of height the length of the interval (I guess that makes them squares, huh?). So the biggest rectangle is the one between 1/2 and 1, and they get smaller as you move left. Then each rectangle is split up again, this time with the rectangles getting smaller as you move to the right (within one of the first-stage rectangles). The first set of rectangles correspond, somehow, to the first term of continued fractions, and the second (smaller) rectangles correspond to the second term. Probably I should dig out that book and try to figure out what this picture actually says, but for now… that’s the picture I have in my head.

We were all a little bit slow in understanding some of the later proofs about things like the discussion in 11.11: “Further theorems concerning approximations”. But we also didn’t seem interested enough to really dive in to it.

In the section on simultaneous approximations, Eric mentioned that similar things are done in other contexts (like, perhaps, p-adics). When you have valuations, you prove a weak (single) and strong (simultaneous) theorem about approximations. While we were talking about it, I wondered if there was some analogy to the distinction between continuous (at each point in an interval) and uniformly continuous (on that interval). It seems like there maybe should be.

Finally, we spent a while digging through the proof that e is transcendental. Mostly because I was stubbornly refusing to believe I wasn’t being lied to throughout the proof. Setting h^r=r! and then “plugging h into” polynomials really made me uncomfortable. As we went, I joked about things not having any actual meaning. Eventually Chris and Eric pointed out that they do, actually, have meaning. This “plugging h in” thing is actually giving you an integer (if your polynomial has integer coefficients). That calmed me down a bit. I still feel like I don’t understand the proof at all, and certainly couldn’t explain even an outline of it. Eric said similar things, but asked if we should have expected that somehow. Eric also mentioned that these sorts of formal manipulations with things that look wrong can sometimes be ok, and that it was something related to umbral calculus. He showed us an identity (Vandermonde’s) associated with binomial coefficients that does similar sorts of symbolic trickery. Which apparently I should now go read some more about.

I had printed out a paper about the continued fraction expansion of e (which maybe was pointed out to me in this comment), which talked about Pade approximations. Some of the things looked somewhat similar to what was going on in the proof that e is transcendental (which the paper said was where they came from), but I couldn’t explain the paper well during out meeting (since I don’t understand it well enough), and we ran out of time.

Hardy and Wright, Chapter 11 (part 1)

June 6, 2009

Now that we’ve got continued fractions under our belt, from chapter 10, we can go on and start looking at “Approximation of Irrationals by Rationals”, chapter 11. One of the (many) cool things about continued fractions, is that they provide “best” rational approximations. We decided, yet again, to split the chapter into two weeks.

In our meeting today, discussing the content of 11.1-11.9, we spent most of our time trying to sort out some typos and see how a few of the inequalities came about. In particular, a typo on page 211, in the theorem that at least one in three consecutive convergents is particularly close to a starting irrational, took us quite a while to sort out.

Eric brought up a comment from the chapter notes that is quite fascinating. The first several sections talk about “the order of an approximation”. Given an irrational \xi, is there a constant K (depending on \xi) so that there are infinitely many approximations with |p/q-\xi|<K/q^n? This would be an order n approximation. In theorem 191, they show that an algebraic number of degree n (solution to polynomial of that degree) is not approximable to any order greater than n (which seems to be a slightly weaker (by 1) statement than Lioville’s Approximation Theorem). The note Eric pointed out was about Roth’s theorem which states that, in fact, no algebraic number can be approximated to order greater than 2. According to the Mathworld page, this earned Roth a Fields medal.

This reminded me about some things I had seen about the irrationality measure of a number. Roth’s theorem, reworded, says something like: every algebraic number has irrationality 1 (in which case it is rational) or 2. So if a number has irrationality measure larger than 2, you know it is transcendental. Apparently, finding the irrationality measure of a particular value is quite a trick. According to the Mathworld page, e has irrationality measure 2, so you can’t use that to decide about it being transcendental.

The whole thing is interesting, as pointed out in H&W, because you think of algebraic numbers as sort of nice (it doesn’t get much nicer than polynomials), but, in terms of rational approximations, they are the worst.

Hardy and Wright, Chapter 10

May 29, 2009

We decided to split the reading of chapter 10 into two weeks (chapter 9 here, in case you missed it). It’s a longish chapter, and I really like continued fractions (though I’m not particularly sure why, they’re just fun) and some of the other readers thought it might be worth it to spend more time reading it carefully.

Our first meeting covered the first few sections, which only involved basic definitions, and the theorem that every real number has an essentially unique continued fraction expansion, and the expansion is finite if and only if the number is rational. Eric stated that he was unimpressed so far, and didn’t see what I was so fascinated by. None of us seemed to have any questions about the reading, so I gave a glimpse of things to come (relation of periodic continued fractions to quadratics, and rational approximations). I also mentioned that there are some interesting tie-ins to the “modular group” (SL_2(\mathbf{Z})), Farey sequences, and Ford circles (which have come up before). Eric has been reading about hypergeometric series, and said there are some interesting formulas there related to continued fractions. He also asked if there was some relation to surreal numbers, because continued fractions approximate numbers from the left and right, alternatingly.

We picked up, the second week, in section 10.10 “A lemma”, defining an equivalence relation on reals. The relation works out to be that two numbers are equivalent if the tail of their continued fractions are the same. Chris corrected a misinterpretation Eric brought up, about canonical representatives of equivalence classes. I had wondered if the equivalence meant that, in terms of periodic continued fractions representing “quadratic” numbers, two numbers (a_1+\sqrt{b})/d_1 and (a_2+\sqrt{b})/d_2 would always be equivalent. In fact, I thought I had decided they were. But an example in the book shows that this is not the case (\sqrt{5}=[2,\dot{4}] while (\sqrt{5}+1)/2=[\dot{1}], dots representing the repeating part). Eric pointed out that two points were related if there are in the orbit of the modular group acting on \mathbb{R} as a subset of \mathbb{C}, acting as linear fractional transformations.

We spent a little while talking about periodic continued fractions, how the two directions of the proof that they are equivalent to “quadratics” go. I think the proof that any quadratic has a periodic continued fraction is fascinating. It gives no indication how long the period will be, or when it will start.

Next I mentioned that there’s a convenient algorithm for finding the continued fraction for a “quadratic surd”, and that I intend to post some python code here implementing it (and other fun functions for playing with continued fractions). While it’s essentially the normal algorithm, taking floors and then reciprocals, there’s some convenience in having quadratics around, because you can “rationalize the numerator” and sorts of things. Not mentioned in the text, but stated at both Wikipedia and Mathworld (links below), is that Lagrange showed that the continued fraction for \sqrt{D} has a period smaller than 2D, that the period begins after a single non-repeating term, and that the last term in the period is twice a_0 (the first term of the continued fraction). All of these things are true of the examples given in the text. And, while finding links… holy crap! the repeating part, besides the last numeral, is palindromic! Is there no end to the fascination!?

I’ll go ahead and just direct you to the Wikipedia page on (periodic) continued fractions, and similarly the Mathworld page (periodic) continued fractions. All (and undoubtedly many others) make for fascinating reading.

Our next main focus was on approximation by convergents. Chris pointed out how remarkable the final theorem is, that any time a fraction is sufficiently close to a number (in terms of it’s denominator), it is automatically a convergent. I mentioned one thing I read about in Rademacher’s “Higher Mathematics from an Elementary Point of View” (which I love), which was that the existence of infinitely many p/q such that |p/q-x|<\frac{1}{2q^2} (corollary of theorem 183) can be interpreted as saying that a vertical line at x passes through infinitely many Ford circles.

I then tried to explain the difference between Theorems 181 and Theorems 182, and point out that there are two reasonable definitions of “closest rational approximation”. I had read about these in Khinchin’s “Continued Fractions” (which I also love). I bumbled it a bit, but believe I was saying true things throughout. Basically, the story goes… convergents are best rational approximations in the stronger sense (thm 182), and mediants of successive convergents are best rational approximations in the weaker sense (thm 181). In fact, choose an irrational (for convenience) x, and let \square denote the operation “mediant”. For any n, define m_{n,1}=(p_n/q_n)\square (p_{n+1}/q_{n+1}), and then iteratively m_{n,k}=m_{n,k-1}\square (p_{n+1}/q_{n+1}). The last of these mediants that is on the same side of x as p_n/q_n will be p_{n+2}/q_{n+2}. Continued fractions rock.

It’s really best to think about these lemmas with an actual continued fraction example. I, personally, used 61/45=[1;2,1,4,3], and looked at the mediants m_{1,k}, between the first and second convergent.

We finished with me trying to explain something that I thought was quite surprising. Let f_k(x)=n_k(x)/k denote the closest rational to x, with denominator k (let’s not require the fraction in reduced terms). I was quite surprised, honestly (and convinced Eric he should be too), that for a chosen x, the sequence of such rationals will not be successively better approximations to x. Having had the chance to go through an example with Eric, and then a few hours to mull it over, I’ve since realized this it not particularly surprising at all. Suppose x lies in [1/4,1/3]. Half of these x will be better approximated by 1/3 than 1/4.

So, anyway, I guess that’s all I have to say about continued fractions by now. Perhaps Eric will show us sometime about fun relationships between hypergeometric series and continued fractions. If you haven’t already stopped reading this post to go find all sorts of other interesting things to read about continued fractions, either online or in Rademacher’s or Khinchin’s books, you can now.

Hardy and Wright, Chapter 9

May 14, 2009

Continuing on, we talked about “The Representation of Numbers by Decimals” this week. I thought the first few sections were fun, in the precision and care used to prove things like “Rational numbers have repeating decimals, and vice versa”.

Chris and I both, apparently, took a minute to digest the example that 29310478561 is divisible by 7, at the end of section 9.5. I feel like in my first year of undergrad I learned about this, or perhaps a similar, test for division by 7. I thought that instead of taking the sum of digits (like you would for mod 3 or mod 9), or alternating sum (for mod 11), you could take some sort of weighted sum of the digits, where the weights depended on 7^n\pmod{10} for various n. Looking around online while writing this post, it seems I was (mis-)remembering the method of Pascal, listed on this page at Mathworld. This Mathworld page mentions several other tests, which look interesting. My search turned up another as well, over at God Plays Dice.

Eric mentioned that he’s read a lot about the game of Nim (section 9.8) because Conway writes about it in On Numbers and Games, and Eric likes surreal numbers.

I like the section on “Integers with missing digits” (section 9.9), because I like to show my calculus students that the sum of the reciprocals of such numbers is a convergent series (even though, writing out the first several terms, it looks like you haven’t thrown out many terms from the harmonic series). This is known as the Kempner Series, which I first learned about in the book Gamma, by Havil.

We concluded with a little discussion on normal numbers, the last few sections of the chapter. It seems we all ran out of steam while reading this chapter, so we didn’t get through the proofs in these sections. But the ideas are interesting, and the results are fun. According to Wikipedia, there is a conjecture that all irrational algebraic numbers are normal, even though there is no known proof that any particular irrational algebraic number is normal. I remain a little confused about the definition of normal, actually. “We say that x is normal in the scale of r if all of the numbers x,rx,r^2x,\ldots are simply normal in all of the scales r,r^2,r^3,\ldots“. I think the idea with multiplying by these powers and changing the scale is that you are looking at longer and longer digit sequences, instead of just single digits (which would be simply normal). I was a little unclear about why you need to multiply x by all of those powers of r, but I guess if you don’t then you won’t ever get any digits (in the scale r^n) greater than r^{n-1}, perhaps?

Update 20090515: I completely forgot to mention another thing we talked about, and I had promised the group I’d link to. Section 9.9, on “Integers with missing digits” begins with the line “There is a familiar paradox” and a footnote that reads “Relevant in controversies about telephone directories”. I wasn’t exactly sure what this controvery was, but we decided probably it was the fact that the probability of picking a random number out of the telephone book, and having it not contain a 9 (say) is fairly small. At first, I had thought maybe the controversy the footnote was hinting at might be related to Benford’s Law, which I also remembered was just recently in the news (slashdot).

Hardy and Wright, Chapter 8 (Second Part)

May 8, 2009

Picking up where we left off last week, we finished chapter 8 today. Most of the time was spent trying to trace through the proofs of the various statements, so I won’t go into too much detail here about that. Many of the proofs had the same flavor, cleverly grouping terms in a polynomial, or setting corresponding coefficients equal in two different representations of a polynomial.

When I had first read the chapter, I didn’t pay too close attention to some of the later sections, for example the section on Leudesdorf’s Theorem (generalizing Wolstenholme’s), and the “Further consequences of Bauer’s Theorem“. However, during our meeting we worked through most of Leudesdorf’s theorem, and we were able to gain some appreciation for the various cases (specifically, why they arise).

One of the theorems in the sections we kinda glossed over was the following (Theorem 131 in the book): If p is prime, and 2v<p-3, then the numerator of S_{2v+1}=1+\frac{1}{2^{2v+1}}+\cdots+\frac{1}{(p-1)^{2v+1}} is divisible by p^2. I noted that this S_{2v+1} is a partial sum for \zeta(2v+1)=\sum_{n=1}^{\infty} n^{-(2v+1)} (Wikipedia, Mathworld). Eric wondered if perhaps they were thinking about this sum as a generalization of this \zeta function to some finite field, but the modulus of p^2 didn’t fit that entirely. Eric also reminded us that closed forms for \zeta(2v) can be found, while closed forms for \zeta(2v+1) are not known.

Hardy and Wright, Chapter 8 (First Part)

May 1, 2009

This week we met a day early, owing to some scheduling conflicts. If you missed last week’s notes on chapter 7, they’re here. This week we spent an hour talking about things in chapter 8, but did not finish, so we’ll return to the last few sections next week. Chapter 8 is on “Congruences to composite moduli,” and is a bit dense, for us anyway.

Chris continues to claim the book is imprecise, while Eric and I are of the mind that it is simply written in an older style, and could be more verbose. Chris is an algebraist, and Eric and I are topologists, which may have something to do with our discrepancy. Chris’ objection this week concerned statements in the text at the end of section 8.4. In this and the previous section, the congruences under consideration are f(x)\equiv 0\pmod{p^a} for some a>1, and polynomial f. The idea is that you can get at solutions by considering the equivalence mod p^{a-1}. Then depending on the function, and what roots you find mod p^{a-1}, you can say things about roots mod p^a. There is a condition on the derivative of f that I thought was maybe related to field extensions (I vaguely remember things like this coming up in Algebra courses years ago), but we decided this was not the case.

Anyway, Chris was asking about the claim that x^2-c\equiv 0\pmod{2^a} has either 2 roots or 0 when a=2, and 4 or 0 when a>2 (c odd). He had asked me about this earlier in the week, and I have written out the squares mod 4,8,16, and 32, and verified the statement there. Chris was concerned about the relation to the statement of Theorem 123. Looking at that theorem, each root of x^2-c\equiv 0\pmod{2^{a-1}} should either give 2 or 0 roots, mod 2^a, and so it seemed like there should be more and more roots for higher powers. We tried to sort this out for a while, and worked through the proof of Theorem 123 as we went, and eventually decided maybe it was ok. Then, while writing this up I realized probably we hadn’t actually decided how the argument went for these cases. Perhaps I’ll have more for you next week.

Part of the proof of theorem 123 was to re-write f(\xi+sp^{a-1}) as f(\xi)+sp^{a-1}f'(\xi)+\frac{1}{2}s^2p^{2a-2}f''(\xi)+\cdots, a technique that was used a few times in this chapter. When I was reading this I decided it looked like this was a Taylor series, and during our meeting we agreed that this was the case. We also talked about the statement that \frac{f^{(k)}(x)}{k!} is always an integer (it helps that f is polynomial). There’s no way I would have thought to use Taylor series, if I had been trying to prove these statements on my own (which I would be, I suppose, if I were more serious).

I then asked if people had worked through the example at the end of section 8.1, about professors’ lecturing schedule. I could follow the equivalences, but I was a little confused about how the word problem was converted to the equivalences. I can see that starting on Monday, and lecturing every 2 days corresponds to the days 1+2k_1 (if we let Monday be the first day), and similarly for the other lecturing schedules. But then I didn’t understand the condition x=7k_7 corresponding to no lectures on Sunday. Chris suggested that maybe the interpretation of the problem was that instructors would have “lectures” that spanned a few days (like the first professor above, starting on Monday, would have “2-day-lectures”). I think we have since sorted out that this is not correct. The instructor will lecture every n-th day (like n=2 in the example line above), and not lecture any of the other days. The setup of the problem is asking “what is the first Sunday that each lecturer would be lecturing?” Thus, we need equivalences x=a+n_ak_a corresponding to the a-th lecturer lecturing every n_a days (and beginning, conveniently, on the a-th day) to pick out days when everybody would be lecturing, and the equivalence x=7k_7 to pick out Sundays.

Eric asked if the solutions to x^{p-1}-1\equiv 0\pmod{p^a} could be easily determined from the roots of x^{p-1}-1\equiv 0\pmod{p^{a-1}}. Of course, the point of these few sections was that they are roots \xi of the second equation, with some multiple of p^{a-1} added on. So the roots of the first equation have the form \xi+sp^{a-1} for 0\leq \xi<p^{a-1},0\leq s<p. Eric’s question is if those values of s are easy to find. We got a little help from python, working out the case p=5,a=2, but burned out before getting to the next prime. Perhaps we’ll come back to it next week.

Finally, Chris asked about any relation between the polynomials f_m(x) of section 8.5 and cyclotomic polynomials. I only vaguely remember what those are, but he reminded us that the n-th cyclotomic polynomial was one whose roots were exactly the n-th roots of unity. Interpreting this in the finite ring setting (that we are in), he seems to be correct when m is a prime. However, we’re not sure that carries over when m is not prime (which is, perhaps, part of the point of this section). In a related question, he asked what one could say about x^5-1\equiv 0\pmod{6}.

We didn’t come up with too much useful during out meeting, but Eric and I played around with some numbers afterwards. The results of the first few sections of chapter 8 indicate that you should be able to obtain solutions to x^5-1\equiv 0\pmod{6} by considering the equivalence mod 2, and mod 3, and combining the results. Doing so, we note that x^5\equiv x\pmod{2} and also mod 3, so the only roots are x=1\pmod{2} and x=1\pmod{3}. This should give the single root x=1\pmod{6}. We asked python (well, sage, technically, via Eric’s setup), and found the interesting result that x^5\equiv x\pmod 6, which we were both surprised by. We played around with a few other moduli, and continued to be intrigued by what we found. Perhaps we’ll have more to say next week, when we continue our discussion of chapter 8. For now, all we can say is that we’re not too good at thinking in modular arithmetic.

Hardy and Wright, Chapter 7

April 25, 2009

Another week, another chapter (last week’s chapter). This week was “General Properties of Congruences”, a reasonably fun chapter. On a side note, I’d like to say how pleased I am that our little group is still going. And note that having a scheduled blog post every week has been a fun habit. It also makes the tags for these post dominate my tag-cloud. I guess that means I should try to spend more time writing about other things as well.

Chris mentioned, before our meeting, how he thought some of the statements were imprecise. I disagreed, but we both thought that some of the wording could be improved. I think that’s to be expected from a book first written 70 years ago. Perhaps I should try to dig up some specific examples.

Chris and Eric and I all agreed that the beginning of the chapter, the first few sections on results about polynomials mod p, brought us back to our first year, graduate-level algebra class.

We discussed how the numbers A_l, defined to be “the sum of the products of l different members of the set 1,2,\ldots,p-1” was just the coefficient of x^l in the polynomial (x-1)(x-2)\cdots (x-(p-1)). Chris pointed out that really it was the absolute value of that coefficient. If I remember correctly, this was some of the wording Chris was unhappy with.

Most of the rest of our time was spend tracing through the discussion in the text from sections 7.7 and 7.8 on “The residue of \{\frac{1}{2}(p-1)\}!” and “A theorem of Wolstenholme”. We all seemed to think that these were fun sections.

As none of the three of us spend much time actually working with integers, we had a bit to discuss with the “associate” of a number mod p, or mod p^2. We all realized that the associate was just the multiplicative inverse, but had to stop for a second to think about the difference between the inverse mod p and mod p^2. We realized, before too long, that if the inverse of i, mod p, is n, then the inverse of i, mod p^2, has the form n+p\cdot k.

We thought about the relationship between integers mod p and mod p^2. Thinking mod p^2, we write down a p by p array, the first row being 0,1,2,\ldots,p-1, the next row being p,p+1,\ldots,2p-1, and on until the final row, p(p-1),\ldots p^2-1. Thinking about multiplicative inverses again, if the inverse of i is n mod p (as in the previous paragraph), then the inverse of i mod p^2 appears in the same column as n in this array we have constructed. We were trying to interpret Wolstenholme’s theorem (the sum 1+\frac{1}{2}+\cdots+\frac{1}{p-1} is equivalent to 0 mod p^2, where 1/i is the multiplicative inverse of i mod p^2) as summing across rows in this array. That’s not quite right, because the inverses don’t all lie in a row, they are scattered around. If I’m thinking about things correctly, though, these inverses, 1,\frac{1}{2},\ldots,\frac{1}{p-1} (mod p^2) should occur one in each column of the array we have made (I guess, besides the first column, which is the column of multiplies of p).

We didn’t make it to the theorem of von Staudt, concerning Bernoulli numbers taken mod 1. Perhaps we’ll return to it sometime later.

Hardy and Wright, Chapter 6

April 20, 2009

Last week’s exploration into “Congruences and Residues” primed us (no pun intended) for Chapter 6 of Hardy and Wright, “Fermat’s Theorem and its Consequences”. This was, for me, the most challenging chapter so far. Luckily, we had our largest attendance to date (four) to get through it.

Chris started out by telling us that he thinks about as many of these mod-p congruence results as possible as results about the cyclic group of units in the integers mod p. He’s an algebraist, so it’s reasonable.

Eric told us about a relation between some of these mod-p results concerning binomial coefficients and topology. He mentioned something about the sphere spectrum, it’s localization at p, and the Eilenberg-Maclane spectrum H\mathbb{Z}. Perhaps he’d help us out by providing those remarks in the comments, as I’m not particularly familiar with them.

I asked if anybody knew if there was some way I was allowed to think about a^{\frac{1}{2}(p-1)} (whose equivalence class mod p was a hot topic in this chapter) as (\sqrt{a})^{p-1}. When a is a quadratic residue, this just about makes sense (of course, it would have two roots, but both, when raised to the p-1 power, give 1 as a result). Alternatively, when a is not a quadratic residue, a^{\frac{1}{2}(p-1)}\equiv -1\pmod{p}. So when a is not a quadratic residue, I’m still tempted to think of \sqrt{a} in some relation to the imaginary number i. None of us in the meeting seemed to know if there was some reasonable connection here, so perhaps a reader can fill us in?

While I’m talking about quadratic residues, I should point out that the Mathworld page on quadratic residues has some fun pictures.

I then mentioned that I had found the Shanks-Tonelli algorithm for finding the “square root” of a quadratic residue (that is, given a quadratic residue a, find an x so that x^2\equiv a\pmod{p}). While I’m dropping names, I also noted that the result that the Fermat number F_k is prime iff F_k|(3^{\frac{1}{2}(F_k-1)}+1), at the end of section 6.14, sometimes goes by the name of Pepin’s Test.

Next, I mentioned that I had spent some time thinking about Theorems 86 and 87 for composite moduli. The question is: For which n is there an 0<m<n and 0<x,0\leq y so that 1+x^2+y^2=mn? It’s easy to show that this is never satisfied if n is 4, or a multiple thereof. Eric noted that this was easy to see by thinking about the squares mod 4 (only 0 and 1 are squares mod 4). I found this to be a fun little problem to use as inspiration for learning a little more python, and generated a big table of how to write multiples of n as one more than a square, or a sum of squares, for varying n. Turns out, there are many ways, in general, of doing so.

I asked if anybody had any ideas what it was about 1093 that made it one of the two known primes so that 2^{p-1}-1\equiv 0\pmod{p^2}, in relation to Theorem 91. That is, was there something I should have gleaned from the proof? Nobody was particularly sure, but Eric thought maybe there was some relation to regular primes (or irregular). This is a topic that’ll apparently come up later in the book, but Eric told us that it was related to some statements about Dedekind domains and the class group. When we looked up the regular and irregular primes on the Online Encyclopedia of Integer Sequences, though, Eric guessed that maybe it was something else, as there are quite a few of both type. For your convenience, the regular primes are sequence A007703, and the irregulars are A000928.

I guess this last question of mine wasn’t particularly bright. If more were known about why 1093 worked, I feel like either people would have found more, or there would be proofs that there weren’t others. Perhaps I could look into it some more. Either way, it was only the beginning of my poor questions. I also asked why it was we were studying quadratic residues, instead of, say, triadic (?) or higher. My guess, which Eric seconded, was that it was simply the next easiest thing to consider after linear residues, which are somewhat straightfoward. We both guess that things are harder to say about higher powers. I suddenly wonder about higher powers of 2 though… quartic, octic… I’m just making up words.

My remaining not particularly bright question was why there was a whole section about the “quadratic character of 2.” Why 2, in particular? We decided that it was just because it was next after 1, and the answer was relatively easy to obtain. Andy pointed out that, since the quadratic character of -3 was done in the book, as was -1, the quadratic character of 3 was known, using the result about products of quadratic residues and non-residues.

In the 6th edition of the book (the one I’m using, to which all references refer) there is a typo in theorem 97, which we verified because Andy has an older version of the text, without the typo (so… they re-typed the text? I almost think that’s a job I could handle happily. I’ve done it before [pdf]). In the theorem, they make a claim about when 7 is a quadratic residue, and then return to prove the theorem after Gauss’ law of reciprocity. However, when they return, they actually prove a theorem about 5, not 7. I tried my hand at 7, but it seemed hard to say anything about it (at least, consider primes of various classes mod 10).

Eric asked about the efficiency of the primality tests that occupy the second to last section of this chapter (Theorems 101 and 102). None of us seemed to know anything, but my guess was that finding the element h, that seems to help out both of these tests, was not easy. But I really have no idea.

Finally, we concluded with my account of Carmichael’s paper “Fermat Numbers” in the American Mathematical Monthly, V. 26 No. 4 from 1919, pp 137-146 (available (in a sense) at JSTOR here). At least, my account of the part about Euler/Lucas’ result on divisors of Fermat numbers, which I mentioned in our discussion of chapter 2. For completeness or so, allow me to present the proof here.

Theorem: If the prime p divides the Fermat number F_n=2^{2^n}+1, then there is a k so that p=k2^{n+2}+1.

Proof: Since 2^{2^n}\equiv -1\pmod{p} by assumption, we see easily that (2^{2^n})^2=2^{2^{n+1}}\equiv 1\pmod{p}, and so by Fermat’s theorem, 2^{n+1}|p-1, which is to say p=k'\cdot 2^{n+1}+1 (this is Euler’s result). It remains to be seen that k' is even. If n\geq 2 then p=k'\cdot 2^{n+1}+1\equiv 1\pmod{8}, meaning p is of the form 8t+1. Since we studied the quadratic character of 2, we know that 2 is a quadratic residue of a prime of this form, and so 2^{\frac{1}{2}(p-1)}\equiv 1\pmod{p}. Thus, \frac{1}{2}(p-1) is divisible by 2^{n+1}, and so p-1 is divisible by 2^{n+2}, which was our goal. Of course, one should check the claim for the numbers F_0 and F_1.

Since the product of two numbers of the form k2^{n+2}+1 has the same form, the theorem can actually be stated about any divisor of Fermat numbers, not just prime divisors.

Hardy and Wright, Chapter 5

April 11, 2009

As per schedule, we talked about chapter 5 from Hardy and Wright’s Number Theory book this week (chapter 4 last week). “We” was the smallest it’s been, and so “talked about” was the most brief of our talks to date (besides, perhaps, the organizational meeting).

Chapter 5, “Congruences and Residues”, was, in my mind, a somewhat odd chapter. The first handful of definitions and results, about congruence mod m, I feel like I’ve (mostly) seen several times, so I take it as pretty basic (which isn’t necessarily to say easy to read). I also like thinking about greatest common divisors, which were introduced in this chapter, in the context of category theory, but still am not sure where to go with it. I had hoped, fleetingly, that some lemma in this section might be stated in terms of some lemma about limits or so, but didn’t notice one. Anyway, after this introduction, some crazy sums are mentioned (Gauss’, Ramanujan’s, and Kloosterman’s), but I don’t see the motivation, and they aren’t used. Looking at the index, it looks like only Ramanujan’s will show up later in the text. After this section on sums, the chapter ends with a proof that the 17-gon is constructable. All in all, it seems like a hodge-podge chapter, both in topic and difficulty.

Chris and I agree that using \equiv for “is congruent to” and “is logically equivalent to” is pretty obnoxious. Especially when used all in the same line. For example:

t+ym'\equiv t+zm'\pmod{p}\equiv m|m'(y-z)\equiv d|(y-z)

Chris brought up the result that the congruence kx\equiv l\pmod{m} is soluble iff d=(k,m) divides l, in which case there are d solutions (this is Theorem 57 in the book). He brought it up because he wasn’t entirely aware of the generalization past d=1. I’m not sure I was either, but it is reasonable.

We did agree that using the notation \overline{x} for the solution x' to the equation xx'\equiv 1\pmod{m} (when it exists) was a nice choice of notation. Embedding the integers mod m in the unit circle in the complex plane via k\mapsto e^{2\pi ik/m}, the multiplicative inverse of x is the complex conjugate, so the notation lines up.

We finished by talking a little bit about geometric constructions. I liked the long argument about the 17-gon being constructable, by showing that the cosine of an interior angle was constructable, by showing that it was a solution to a system of quadratics (or so). At the beginning of this process, 3 is chosen as a primitive root of 17, and used to define a permutation of \{0,\ldots,15\} by m\mapsto 3^m\pmod{17}. I’m not exactly sure why this was done, or why 3 in particular, but it’s fun to trace through the argument from then on. Chris liked the geometric construction, and is tempted to try actually performing it. We reminded ourselves how to bisect angles and draw perpendiculars with straight-edge and compass.