Kenneth Deeley

Posted on Wednesday, 15 October, 2003 - 09:19 pm:

(1) Let {E1, E2, E3,.........} be a sequence of events. Find an expression for the event that infinitely many of the Ei's occur.

(2) Suppose that 10% of the surface of a sphere is coloured blue and the rest coloured red. Prove that it is possible to inscribe a cube in the sphere with all of its vertices red irrespective of the distribution of the colours.

Thanks for any help.

Tristan Marshall

Posted on Thursday, 16 October, 2003 - 07:17 pm:

For 1 the expression is:

LaTeX Image

To see this, observe that any point not in infinitely many of the LaTeX Image

is not in the intersection of the unions.

I'll just sketch a solution for 2:

Suppose we've defined the set of points where the sphere's surface is blue. Now imagine inscribing a cube in such a way that one of its vertices is in this set (there could be more than one, but this doesn't matter), and colouring its seven other vertices blue. Now repeat this for every point in the original 'blue' set.

Formally, what we have done is form a larger set, which I'll call 'pseudo-blue', by rotating the 'blue' set through pi/2 four times and projecting through the centre of the sphere. We can immediately say two things about this 'pseudo-blue' set:

a) A cube has a blue vertex if and only if all of its vertices are 'pseudo-blue'

b) The 'size' ('measure' to be more formal) of 'pseudo-blue' is at most eight times the size (measure) of 'blue'

Since the 'blue' set covers 10% of the surface, 'pseudo-blue' covers at most 80% of the surface. Hence we can pick a point on the sphere that is not 'pseudo-blue' and inscribe a cube with a vertex at that point - this cube will have all its vertices red.

I've omitted some (a lot) of details, but I think this should give you the gist of things.

David Loeffler

Posted on Thursday, 16 October, 2003 - 11:11 pm:

Tristan, this doesn't quite work. The problem is that you have to ensure that the maps from the first vertex of the sphere to the other seven are sufficiently nice that they preserve measure, which I claim isn't immediately obvious.

(I consulted a measure theorist on this one and he assured me that the right way to do it is with Haar measure on SO(3). I'll post the details when he gives them to me.)

David

Tristan Marshall

Posted on Friday, 17 October, 2003 - 11:09 am:

Hmm, yes, you have a point. I did say I'd omitted some details!

David Loeffler

Posted on Friday, 17 October, 2003 - 01:11 pm:

I have a nasty suspicion that it's not actually possible to make all the maps measure-preserving.

David

Tristan Marshall

Posted on Friday, 17 October, 2003 - 01:41 pm:

Perhaps, but I can't think of an obvious counterexample (mind you, I'm more a probabilist than a measure theorist). The maps from one vertex to the other seven are all rotations of the sphere or projections through the centre, and so aren't particularly pathological.

We also need to assume that the set of coloured points is measurable, or we fail before we even start.

Kenneth Deeley

Posted on Friday, 17 October, 2003 - 02:35 pm:

Sorry, can you explain these terms:
'measure theory'
'pathological'
'measurable'

I had no idea that this question involved so much.

Cheers,
Ken

David Loeffler

Posted on Friday, 17 October, 2003 - 03:24 pm:

Tristan, the set of rotations and projections you gave won't in general generate a cube, if you keep the axis fixed; and if you vary the axes from point to point, of course you lose the niceness of the map.

If the set of coloured points isn't measurable the question doesn't make any sense anyway!

---

Kenneth, this is a genuinely hard question. It's sort of morally obvious that it must work for any set of size less than 1/8, because of Tristan's 'pseudo-blue' argument, but the problem is what we mean by that statement. We are dealing with infinite sets, and it is quite hard to get a handle on the notion of the 'area' or 'size' of a set. What is the area of the set of points on the sphere with rational coordinates, for example? Or of a fractal set?

Measure theory is a way of assigning a 'size' to certain sets. Formally a 'measure' is a function from some set of 'nice' subsets of some set W to [0, infinity], with the property that if two sets (or more generally a countable family of sets) are disjoint, then the measure of their union is the sum of their measures, and that the empty set has measure zero. The set of subsets we define the measure on is important: if sets are too nasty, then it becomes impossible to define measures on them.

In the example above, we are working with a certain obvious measure on the unit sphere derived from the Lebesgue measure on

³ . The sets for which a Lebesgue measure is defined are known as the Lebesgue-measurable sets (or sometimes just measurable , when the Lebesgue measure is understood). The Lebesgue measure of a cuboid is exactly what one would expect it to be: its volume, the product of its edge lengths. Lebesgue measure is in a certain sense the ultimate generalisation of this - there is no measure defined on a wider class of sets than Lebesgue measure which still gives cubiods the measure you expect them to have.

Here's an example of the sort of paradox you can get in to if you try to work with non-measurable sets. You can take a sphere of radius 1, decompose it into something like seven pieces, move them around a bit in

³ and put them together in a different order, and you have two spheres of radius 1! This is very strange and weird. The problem is that the seven pieces themselves aren't measurable, so you can't say "this can't work as the total volume of the pieces won't add up".

This is just a brief outline of why one has to tread extremely carefully when talking about the sizes of sets. I myself don't know a great deal about measure theory (it's one of my lecture courses this term, actually) so there is a distinct possibility that some of the above may be false or misleading.

David

Kenneth Deeley

Posted on Friday, 17 October, 2003 - 05:59 pm:

Thanks David and Tristan.
For (2) I have used an argument which relies on one of the Boolean inequalities. I would appreciate it if you could give your opinions on this.

a) Let V be the event that a randomly chosen point is coloured blue, and let this be a vertex.
Hence, since 10% of the sphere is blue, the probability of V is:

P(V)= 10/100 = 0.1

(b) A cube has 8 vertices, so the probability that at least one vertex is blue is:

P( union from r=1 to r=8 of Vr )

Kenneth Deeley

Posted on Friday, 17 October, 2003 - 06:02 pm:

(c) The Boolean inequality says that the probability of the union is less than or equal to the sum of the individual probabilities.

Hence
P(union from r=1 to r=8 of Vr) < = P(v1) +...+P(v8)

Hence
P(union from r=1 to r=8 of Vr) < = 8/10 [since each of the Vi's has prob=1/10.]

Kenneth Deeley

Posted on Friday, 17 October, 2003 - 06:02 pm:

(d) Since P([all vertices red]union[at least one vertex blue])=P(the sample space),

P(all vertices red) = 1-P(at least one vertex blue)

Hence P(all vertices red) > = 1-(8/10) =0.2

The conclusion is that at least 20% of all possible cubes have all their vertices red.

Sorry about the awkward notation. How valid [if at all] is this argument?

Ken

David Loeffler

Posted on Friday, 17 October, 2003 - 07:46 pm:

You're doing more or less what my measure-theorist friend was suggesting. What you are saying is: take a cube uniformly at random among the cubes inscribed in the sphere. Then we would hope that the distribution of each of its vertices over the sphere is uniform. Intuitively it can't possibly be anything else, but can we make sense of the notion of 'picking a random cube'?

If this works, then P(at least one vertex blue) $< \sum_{i = 1}^{8} P (v_{i}$ blue $)$ where $v_{i}$ is the $i^{th}$ vertex. The assumption that $v_{i}$ ranges uniformly over the sphere gives $P (v_{i}$ blue $) = μ ($ blue $) < 0.1$ , so the probability of an all-red cube is at least 0.2 and in particular a red cube exists. (Here $μ$ is the natural measure on the sphere, which you can extract from Lebesgue measure on $R^{3}$ .)

The set of all possible positions of the cube is the same as the set of all possible rotations of three- dimensional space. This has a group structure (obviously), which is the special orthogonal group $S O_{3} (R)$ (the group of real orthogonal 3x3 matrices with determinant +1).

Now, this has a very pleasant well-behaved measure on it called Haar measure. (In fact anything that has both a group structure and a reasonably nice topology has a Haar measure.) This allows us to make sense of the notion of a uniformly distributed variable in $S O_{3}$ , and everything does work out neatly.

(As you have probably worked out, probability and measure are very closely connected concepts: probability is just a measure such that $μ (Ω) = 1$ .)

David

Kenneth Deeley

Posted on Friday, 17 October, 2003 - 08:05 pm:

Thank you David for your replies [they have given me a much greater understanding now of this problem]. Good luck with your measure theory course.

Thanks
Ken