Probability, Sheet 3, Problem 5

I’m sorry I’ve been falling behind on my blogging. I’ll try to catch up gradually. Here is a discussion of the problem, as I mentioned during the tutorial.

A vector space of uncountable dimension

Let V=\{ f: {\bf N}\rightarrow R\} be the real vector space of all functions from the natural numbers to the reals. Then V has uncountable dimension. To see this, for each a>0, let f_a be the function such that f_a(n)=a^n.

Claim: The f_a are linearly independent.

Proof: It suffices to show that any finite collection \{f_{a_i}\}_{i=1}^n with a strictly increasing sequence of a_i are linearly independent.

We prove this by induction on n, the fact being clear for n=1. Suppose \sum_{i=1}^nc_if_{a_i}=0 with n>1. The equation means


for all m. Thus, \sum_{i=1}^{n-1}c_i(a_i/a_n)^m+c_n=0 for all m. Now let m\rightarrow \infty. This shows that c_n=0. Thus, by induction, all c_i=0.

We have displayed an uncountable linearly independent collection of functions in V. Now, let \{b_i\}_{i\in I} be a basis for V. Each f_a can be written as a linear combination of \{b_i\}_{i\in I(a)} for some finite set I(a) of indices, where we choose the set I(a) to be minimal with this property. Since the linear span of any finite set of the b_i is finite-dimensional, for any finite subset S\subset I, there are at most finitely many a such that I(a)=S. That is, the map a\mapsto I(a) is a finite-to-one map from the positive reals R_{>0} to the finite subsets of I. Hence, the set of finite subsets of I must be uncountable. But then I itself must be uncountable. (I leave it as an exercise to show that the set of finite subsets of a countable set is itself countable. You should really write out the proof if you’ve never done it before.)

I might point out that before the tutorials, I was a bit confused myself. That is, the first bit about the f_a‘s being an uncountable linearly independent set is rather easy. However, I started hesitating: Still, why can’t there be a countable set of elements in terms of which we can express all of them? After all, the set of coefficients we can use for the expressions is uncountable… So think through again clearly: how is this resolved above?

As a final remark, note that this proves that V is not isomorphic to R[x]. This is perhaps the first example you’ve seen where you can prove that two vector spaces of *infinite* dimensions are not isomorphic by simply counting the dimensions and comparing them.

Linear independence of polynomials

One of the exercises this week asked for a proof of linear independence for the set

\{x^i\}_{i\in {\bf N}}

inside the polynomials R[x] with real coefficients. However, note that the polynomials here are regarded as *functions* from R to R. Thus, it amounts to showing that if

c_0+c_1x+\cdots c_nx^n=0

as a function, then all c_i have to be zero. This does require proof. One quick way to do this is to note that all polynomial functions are differentiable. And if

f(x)=c_0+c_1x+\cdots c_nx^n

is the zero function, then so are all its derivatives. In particular,


for all i. But f^{(i)}(0)=i!c_i. Thus, c_i=0 for all i.

One possible reason for confusion is that there is another ‘formal’ definition of R[x] by simply identifying a polynomial with its sequence of coefficients. That is, you can think of an element of R[x] as a function f:N \rightarrow R that has *finite support* in that f(i)=0 for all but finitely many i. With this definition, the polynomial x^i becomes identified with the function e_i that sends i to 1 and everything else to zero. If you take this approach, the linear independence also becomes formal. But in this problem, you are defining R[x] as a function in its variable. This of course is the natural definition you’ve been familiar with at least since secondary school.

Here are two questions:

1. If you think of two polynomials f and g as functions from N to R with finite support, what is a nice way to write the product fg?

2. What is the advantage of this formal definition?

Mathematics in Society

After several conversations recently about the social status of mathematics, I thought I’d put here links to two short essays I wrote on this.

1. An exchange on Mathoverflow

2. Mathematical Vistas

Mathematical problems

This week, I was given a very short deadline to write one of those introductory blurbs to the Korean edition of Ian Stewart’s book, ‘The Great Mathematical Problems.’ I could only skim through it, but I managed to get enough of a sense to write something. Here it is, in case some students find it interesting.

SNU Topology of number fields, week of 15 July

I was looking over the notes and saw a few items omitted by Milne.

First, in the proof of Hilbert’s theorem 90, there is no proof of the linear independence of distinct characters on a group. You can try to figure it out yourself (quite easy) or look at the notes with that title Keith Conrad’s webpage. (For some strange reason, I can’t create a direct link to the paper.)

Secondly, Milne has a cryptic remark without definition or proof about a ‘Verlagerung’ (transfer map) in Proposition 3.2. This is reference to the fact that the restriction map for Tate cohomology in degree minus 2 corresponds to a classical formula for a map between abelianizations. This proof is not so straightforward, and can be found in Prop.11.12 of these nice notes by Holden Lee. It seems they’re from a reading course he took with Professor Shin Sug Woo.

If some of you would like to read a more leisurely exposition of group cohomology, I found online these notes by Kenneth Brown.

Finally, this old paper of Oort contains a discussion of extensions and cup products.

SNU Topology of Number Fields

Here are some documents to help you with the course.

1. General Motivation:

Lecture at the Cambridge workshop on non-abelian fundamental groups in arithmetic geometry (2009)

Lecture at Bordeaux conference in honor of Martin Taylor’s 60th birthday (2012)

Lecture at British Mathematical Colloquium (2011)

Lecture at AMC, Busan (2013)

2. James Milne’s lecture notes:

Class Field Theory

Algebraic Number Theory

Arithmetic Duality Theorems

3. Langlands programme:

Langlands’s lecture at Helsinki ICM

Report on work of Bao Chau Ngo (with Sugwoo Shin)

4. Topology of number fields:

Mazur’s paper on etale cohomology of number fields

Morishita’s paper on knots and primes

Furusho’s paper on Galois action on knots

Is air blue?

This blog is now mostly about my teaching at Merton and Oxford. However, I thought I would occasionally insert a post about my learning as well. For the most part, this means learning from my colleagues, whom I tend to pester endlessly over meals with silly and nerdy questions. One such appears in the title of this post; the victims were Alan Barr and Alex Schekochihin.

The answer of ‘yes’ can be justified as follows:

When we speak of the color of an object, it is the visual sensation* correponding to the mixture of frequencies in the light it scatters. This color is not constant, but there is a dominant one determined by an interpolation of usual experience.

From this point of view, it seems sensible to say that air in small quantities is transparent, but in large quantities**, it is blue.

So when a young child asks,

‘Why is the sky blue?,’

a reasonable response is

‘Because air is blue.’

It’s not that the usual answer in terms of Rayleigh scattering is wrong. But this is going into the deeper explanation of why air is blue. On the other hand, the shallower response above corresponds to something like:

Q: Why are leaves green?

A: Because they contain a lot of chlorophyll, which is green.

The Rayleigh scattering and so forth would then be analogous to an explanation of why chlorophyll is green. (I don’t know. Of course there must be a chemical explanation of sorts, but I seem to recall that there is also an interesting evolutionary explanation.) You can go into this later when the child is older.

By the way, ‘air’ here refers to the substance making up the Earth’s atmosphere. Atmospheric colours seen from other bodies in the solar system seem to be quite diverse.

Invoking the classification of different interactions, one might argue that there is a distinction between a process that involves a good deal of absorption-emission (which is the case for most solid objects we see) and one that only has elastic scattering. However, Alan and Alex assure me that these are really no different from a physicist’s view: It’s all scattering.

At the end of the Warden and Tutor’s meeting today, Simon Hooker contributed the interesting remark that liquid oxygen is a very pretty blue, although that is likely to be a different phenomenon from Rayleigh scattering.

Apparently, Philip Larkin was aware of this question and answer:

High Windows (1967)

When I see a couple of kids
And guess he’s fucking her and she’s
Taking pills or wearing a diaphragm,
I know this is paradise

Everyone old has dreamed of all their lives—
Bonds and gestures pushed to one side
Like an outdated combine harvester,
And everyone young going down the long slide

To happiness, endlessly. I wonder if
Anyone looked at me, forty years back,
And thought, That’ll be the life;
No God any more, or sweating in the dark

About hell and that, or having to hide
What you think of the priest. He
And his lot will all go down the long slide
Like free bloody birds. And immediately

Rather than words comes the thought of high windows:
The sun-comprehending glass,
And beyond it, the deep blue air, that shows
Nothing, and is nowhere, and is endless.

As you know, a poet chooses his words pretty carefully, especially in a short poem. So Larkin must have meant something nontrivial writing the last stanza: ‘blue sky’ would have been the phrase coming more readily to mind.

I think Alan summarized his annoyance quite succinctly:

‘They fuck you up, these mathematicians.’

Well, we don’t mean to…


* ‘Visual sensation’ here is referring to the fact that color seen by the eye is an equivalence class of light. You may know that the space of colours is three-dimensional, a mere projection of the space of physical light, which is infinite-dimensional. For an intriguing overview of this topic, I recommend the article ‘Geometry in Color Perception’ by A. Ashtekar, A. Corichi and M. Pierri, in: Black Holes, Gravitational Radiation and the University, (Kluwer Dodrecht, 1999), p. 535-549, CGPG pre-print 97/12-7.

** By the way, the fact that colour is an aggregate effect applies to usual objects as well. Gold is rather yellow, but I doubt it would be if we broke it down into molecules. Obviously, how much stuff needs to be present for us to start experiencing colour will depend on the substance.

Probability, sheet 4, number 8

I didn’t have time to fully discuss number 8 of sheet 4 . But Matej Balog has kindly agreed to let me post his solution on the blog.

Probability sheet 4, number 9

I would like to highly recommend working out number 9 on probability sheet 4, simply because it’s so amusing.

It reads like this:

Passengers arrive at a bus stop at rate 1 per minute. Find the distribution of the number
of passengers boarding a typical bus in two cases: (a) buses arrive regularly every 10
minutes; (b) buses arrive as a Poisson process with rate 1 per 10 minutes. Which one has
higher variance?

I arrive at the bus stop at 2pm. Find the distribution of the number of other passengers
boarding the same bus as me in the two cases above.

Most of the problem is straightforward, and I won’t go over it here. For example, the mean number of passengers boarding will be 10 in either case, but, naturally, the variance will be higher in case (b). But what’s amusing is the second part, where we assume you arrive at the bus at some given time, and calculate the mean number of *other* passengers boarding with you. For case (a), you find 10 as before, but for case (b), the mean turns out to be 20!

This situation is sometimes referred to as the ‘inspector’s paradox’. That is, if you’re an inspector trying to check up on the mean number of passengers boarding at a given stop by arriving at 2 PM for a number of days to take the bus, you will tend to find a larger mean than the true mean for the average bus, at least in the model (b). You should ask yourself why this happens.


Get every new post delivered to your Inbox.