Archive for June, 2009

Extrema at the Integers

June 27, 2009

For a little while now I’ve been wanting to sit down and come up with a formula for a continuous function that has its local extrema at the integers. I forget why I wanted this.

As stated, this is an easy problem. The function \cos(\pi x) has extrema at all the integers, and only the integers. For whatever reason, I want the function I’m after to be sort of like a wavy line (like y=x, but wavy, with extrema). The function x+\cos(\pi x) almost fits the bill. It has the right basic shape (a wavy line with extrema), but the extrema don’t hit exactly at the integers.

Let’s try to be a little more specific in our goal still. Suppose I have two lines, y_0=m_0x+b_0 and y_1=m_1x+b_1, and that for x\geq 0 the line y_0 is lower than the line y_1. In particular, this means b_0\leq b_1 and m_0\leq m_1 (and I’m assuming 0< m_0). Now, I want the maximum values to lie on the line y_1, minimum values on y_0. Let’s shoot for getting the minimums to occur at even integers, and the maximums to occur at odd integers.

My first thought at this point was to make an sort of “mixing function” h(x) and combine the two lines with the mixing function to make

f(x)=h(x)y_1+(1-h(x))y_0.

If my h(x) is bounded by 0 and 1, then when it is 0, f(x) will be y_0, and when h(x)=1, we’ll have f(x)=y_1. So how does my mixing function look? Well, I want y_0 (so h=0) at the even integers, and y_1 (so h=1) at the odds, so it looks like a reasonable first guess for h(x) is

h(x)=\frac{1}{2}(1-\cos(\pi x)).

Now, when I mix my two lines using this function, and the rule above for f(x), I don’t get what I want. Sad. After a while, I realized why I didn’t get what I wanted. Since my h(x) is always between 0 and 1, the f(x) is always between the two lines, y_0 and y_1. But if f(x) has a minimum on y_0 at some point x=a, then f'(a)=0, so in some interval to the right of a, we’ll have f(x)\leq y_0 (since y_0'>0).

To patch this up, I decided to modify my lines. I’ll make each of my lines a little wavy, so that at the integers they’ll have derivative 0 (but go through the same point). But I don’t want any extrema, so I’ll keep the derivative positive. So I’ll replace y_0 with a function whose derivative is \frac{a}{2}(1-\cos(2\pi x)), for some value a. Of course, we can find a, because we know the values at all of the integers. Integrating and such, we set up

y_0=m_0(x-\frac{1}{2\pi}\sin(2\pi x))+b_0.

and similarly

y_1=m_1(x-\frac{1}{2\pi}\sin(2\pi x))+b_1.

Now, finally, when we mix these two functions with our mixing function h(x) above, to make the function f(x), we finally get what I set out for (as long as the values m_0,b_0,m_1,b_1 are reasonable).

The whole formula is something I could write down here, but it doesn’t seem to simplify much. I’ll do a specific case though. If my lines are x-1 and x+1, then my function is

f(x)=\frac{1}{2}(2x-\frac{1}{\pi}\sin(2\pi x)-2\cos(\pi x)),

which you can investigate at (among other place) WolframAlpha. With a double angle identity, you can pretty quickly see the derivative is 0 just at the integers (and at all of them). If you’re into it, you can also see the points of inflection are always halfway between integers.

So, anyway. Anybody have a better way to do this? Or some idea why you might look for such a function?

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.