Archive for May, 2009

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).

A Sibling!

May 13, 2009

Ok, ok, so this isn’t a math post. But my parent has formed a new kid, tasked with learning Python/Sage. I’m a big brother now!

I’m in the Carnival!

May 8, 2009

My post on a Riemann sum made the 52nd Carnival of Mathematics!

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, 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. 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 sagenb.org 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.