A look at a few Tripos questions II

This is the second in a series of posts that started here. In the first post I explained what I’m up to. Now let me just continue with some more questions. I’m now on to the harder Section II questions. Here’s the first one I want to look at. Even though it makes the posts shortish, I think I’m going to stick to one long question per post.

9F. Prove the Axiom of Archimedes.

Let $x$ be a real number in $[0,1]$ and let $m,n$ be positive integers. Show that the limit

$\displaystyle \lim_{m\to\infty}[\lim_{n\to\infty} \cos^{2n}(m!\pi x)]$

exists, and that its value depends on whether $x$ is rational or irrational.

[You may assume standard properties of the cosine function provided they are clearly stated.]

In an exam you have a choice of questions, so with a question like this I’d recommend beginning by spending a minute or two trying to guess whether you’ll be able to do it (and do it reasonably quickly). The first part is bookwork (the Cambridge term for reproducing things that are in your notes), so either you know it or you don’t. What’s less obvious is how you’re going to get on with the second part.

It’s fairly clear, however, that a good way to proceed is to understand the inner limit first and only then worry about what happens with the outer limit. So what can we say about $\lim_{n\to\infty} \cos^{2n}(m!\pi x)$ ? Well, the sequence consists of bigger and bigger powers of some number — the number $\cos^{2}(m!\pi x)$ , to be precise. That number lies between 0 and 1, so its successive powers will tend to 0 unless it is 1. How can it be 1? Only if $m!\pi x$ is a multiple of $2\pi$ , which means that $m!x$ must be a multiple of 2.

Aha, now we see where rationality and irrationality come in: if $x$ is irrational, then $m!x$ can’t be a multiple of 2, so the limit is 0. OK, we’re almost certainly going to be able to finish this off, so let’s get started.

Prove the Axiom of Archimedes.

There are various versions of this — I’m not sure which was given in the course. However, from the thoughts we’ve just had it seems very likely that the intended version is the one that says that $1/n\to 0$ as $n\to\infty$ .

A general point here is that there is almost always a connection between the early theoretical part of a question like this and the more specific what-happens-in-this-example part. So if you can’t relate the axiom of Archimedes to the double limit, you should be worried. In general, this convention of Tripos questions is your friend — it’s another thing that makes it easier to look for what the examiner wants you to do.

The thing to remember about the statement that $1/n\to 0$ is that it is not trivial. It is trivial if you think of the reals as infinite decimals, but to prove that every real number has a decimal expansion you need … the axiom of Archimedes. We’re thinking of real numbers as elements of complete ordered fields, so we want to prove that $1/n\to 0$ using the axioms for a complete ordered field.

The obvious axiom to use here is the monotone sequences axiom, since we have a monotone sequence to look at. So here goes.

Since $1/n$ is decreasing and bounded below, it converges to a limit. Since all the terms of the sequence are positive, the limit cannot be negative. Suppose it is a positive number $c$ . Then we can find $n$ such that $1/n < 2c$ (by the definition of convergence). But then $1/m\leq 1/2n < c$ for every $m\geq 2n$ , which contradicts the fact that $c$ is the limit of the sequence. Therefore, $1/n\to 0$ .

Rest of question.

We’ve done in our heads part of the rest of the question, so let’s write that down.

If $x$ is irrational, then for every $m$ the number $\cos^2(m!\pi x)$ is positive and less than 1.

Now there’s a slight dilemma. It feels obvious that the powers of this number tend to 0, but are we allowed to assume that? Ordinarily I would say yes, but since the first part of the question asks us to prove the axiom of Archimedes and the rest of the question is (it turns out) very easy, it is almost certainly the examiner’s intention that we include a proof, using the axiom of Archimedes, that $t^n\to 0$ whenever $0\leq t<1$ .

Here’s how I’d prove that. I find it more convenient to prove the equivalent result that $s^n\to\infty$ whenever $s>1$ . And here’s what I write for that.

Let $s=1+r$ . By the binomial theorem, $s^n\geq 1+nr$ . But $1+nr\to\infty$ by the Archimedean axiom (unfortunately, it seems that I made the wrong guess about which version to use — it would have been more convenient to prove that $n\to\infty$ ), so $s^n\to\infty$ as required.

How do we prove that $1+nr\to\infty$ ? By saying that $1+nr\geq C$ whenever $n\geq (C-1)/r$ and appealing to the axiom of Archimedes for the statement that there actually exists an integer that is at least $(C-1)/r$ .

While we’re at it, let me remind you how that version of the Archimedean axiom is proved. The statement to be proved is that for every real number $x$ there is an integer $n$ that is greater than $x$ .

We start with the “let” trick: that is, we write, “Let $x$ be a real number.”

We’ve got nothing to go on, so in an effort to generate some information, we assume that the result is false. So we write, “Let $T$ be a real number and suppose that $n\leq T$ for every integer $n$ .”

This can be rephrased as “ $T$ is an upper bound for the set of all integers.” OK, the integers are a non-empty set and they are bounded above. What does that trigger in our minds? If we’re reasonably up on the course, it should trigger the least upper bound axiom. So we add, “Therefore, there must be a least upper bound $S$ for the set of all integers.”

It’s obvious that such a bound can’t exist: you just pick an integer close to it (which you must be able to do or it wouldn’t be the least upper bound) and add 1. Here’s what I’d write. “Since $S$ is the least upper bound, there must be an integer $n$ such that $n > S-1$ . But then $n+1 > S$ , which is a contradiction.”

OK, we’ve dealt pretty comprehensively with the case where $x$ is irrational. What about when $x$ is rational? A quick look to see what happens, and we see that what we care about is whether $m!x$ is a multiple of 2. To make things easier to think about, let’s write $x$ as $p/q$ . Then when $m\geq q$ we find that $m!p/q$ is an integer.

What’s the neatest way of getting it to be an even integer? Actually, I see that I don’t need this after all: I was being slightly stupid, since for $\cos^2(m!\pi x)$ to equal 1, all I need is for $m!x$ to be an integer (by the deep result that $(-1)^2=1$ ). So here’s what I’d write.

If $x$ is rational, then it is equal to $p/q$ for some integers $p$ and $q$ , with $q\ne 0$ . If $m\geq q$ , then $m!x$ is an integer, so $\cos^{2n}(m!\pi x)=1$ for every $n$ . Therefore,

$\displaystyle \lim_{m\to\infty}[\lim_{n\to\infty} \cos^{2n}(m!\pi x)]=1$

whenever $x$ is rational.

Even with all the complications I tried to shoehorn in, I’d say that was a pretty easy question. But you have to be a bit careful with easy questions: they make the examiners fussier about your answers. In particular, if you’re in doubt about whether you’re allowed to assume something (a good example in this case being the fact that $t^n\to 0$ when $0\leq t< 1$ ) you should be a little more careful.

Let me list the general principles we’ve had so far for making this judgment. They are not infallible, but they are a good guide.

1. You can assume something as long as it belongs to an earlier part of the course. (Example: it’s OK to assume general facts about limits when proving something about differentiability.)

2. If the question is about one thing, then it’s OK to use knowledge about other topics when analysing a concrete example. (Example: if the question is about differentiability in general and then asks you about an example that involves trigonometric functions, then it’s OK to assume facts like that the derivative of $\sin$ is $\cos$ . On the other hand, if the question is about formally deriving the properties of trigonometric functions, then it is definitely not OK to assume those facts.)

3. If the question starts with a bit of theory and then asks you to look at a concrete example, then you should not assume facts that can be proved with the help of the theory: the examiner is asking you to relate the theory to the example, and you must demonstrate that you see the connection. (Example: if you’ve been asked to prove the axiom of Archimedes and then find yourself needing the fact that $t^n\to 0$ when $0\leq t< 1$ , then you are almost certainly expected to give a proof, since the proof uses the axiom of Archimedes.)

This entry was posted on April 28, 2012 at 11:11 am and is filed under Cambridge teaching, IA Analysis. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

10 Responses to “A look at a few Tripos questions II”

Nyaya Says:
April 28, 2012 at 4:43 pm | Reply
For the sake of completeness, shouldn’t one also mention the case when $x$ is rational and $m<q$?

On a different note, I envy your students for having such a great teacher.
- gowers Says:
  April 28, 2012 at 5:05 pm
  I was being a bit brief there (as is appropriate if you’re in the middle of an exam). But the point is that we need to show that if $m$ is sufficiently large then the function is close to its limit. So if we prove that it actually equals the limit whenever $m\geq q$ then we’re done.
- gowers Says:
  April 28, 2012 at 5:07 pm
  The emphasis on “equals” there is slightly misleading: the really important thing is that all that matters is that the closeness happens when $m$ is sufficiently large — the fact that we get equality is a little bonus that we could in theory have done without.
pierre Says:
April 28, 2012 at 8:18 pm | Reply
It seems like things would be easier for everyone if the questions were written in a way that made clearer what could be assumed. For example, this question might be rewritten as:

1. Prove the Axiom of Archimedes.

2. Prove that t^n -> 0 whenever 0<=t<1 using the Axiom of Archimedes.

3. Using your result in 2, prove the following: let x be a real number in and let m,n …

It seems like a significant portion of this blogpost is dedicated to divining the mind of the examiners about allowed assumptions. Perhaps if the questions were written in a way that makes this clear everyone (that is, both you and the students) could spend more time focusing on mathematics.
- Sean Says:
  April 28, 2012 at 11:43 pm
  A large part of solving an unseen question (and doing mathematics in general) is figuring out what method to use or what lemmata to prove without being told these in advance, and without necessarily having confirmation at every step of the way that one is on the right track.
  
  I’m guessing the examiners want to test this skill, though it’s hard to do this if the questions are too prescriptive. Even a statement saying which assumptions are allowed would probably be interpreted as a significant hint that the student should make use of those assumptions.
David Says:
April 28, 2012 at 10:23 pm | Reply
I think there’s a slight error in your characterisation of when cos^2(m!*pi*x) is 1: m!*pi*x could also be an odd multiple of pi.
- David Says:
  April 28, 2012 at 10:25 pm
  This is what you get for not reading the whole post before commenting…
Ether Says:
April 30, 2012 at 12:17 pm | Reply
I remember doing this question (as a practice) and wondering ‘What happens if you swap the limits around’.

As in, you let m tend to infinity and then n tend to infinity. I think that for a irrational number it can fail to have a limit. Is that correct?
- gowers Says:
  April 30, 2012 at 3:04 pm
  Yes it is correct. If you want a simple proof, just let $\epsilon_1,\epsilon_2,\dots$ be an arbitrary sequence of 0s and 1s and take the number $\alpha=\sum_n \epsilon_n/n!$ . If you multiply that by $m!$ and take the integer part, you’ll get something close to $\epsilon_m$ . Therefore, it’s easy to make sure that $\cos(2\pi m!\alpha)$ doesn’t tend to a limit. If you want $\cos^{2n}(\pi m!\alpha)$ not to tend to a limit, just take the previous $\alpha$ and divide it by 2.
Greg Marks Says:
April 30, 2012 at 10:03 pm | Reply
Although the statement “its value depends on whether $x$ is rational or irrational” is not quite the same as saying “its value depends only on whether $x$ is rational or irrational,” it is close enough that students might consider the possibility that plugging in the simplest rational $x$ they can think of reveals what they’re supposed to prove. (This sort of ploy was also helpful, for example, on Problem A2 of the 2011 Putnam Competition.)