Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a problem we've been considering in our undergraduate math club, and I thought it would be nice to get further thoughts on the subject.

I will start with a two dimensional case and then extend the problem to 3 dimensions (which is the one we have been considering).

2 Dimensions
We want the minimum number of colors that can color the edge of a circle such that, when any two radii are drawn at a right angle to each other, they touch different colors on the edge of the circle.

One color obviously doesn't satisfy the condition, and we can see that two colors is a lower bound for this problem and four colors is trivially an upper bound. The solution is fairly trivial as well; the circle can be colored with two colors as shown below:

enter image description here

Note that the color at a boundary must be selected to meet the constraint, which isn't really shown in the picture.

3 Dimensions
Now consider the 3 dimensional case. We want the same constraint to hold, but now instead of there being just two points that touch right angled radii, we have an infinite number of points along a great circle.

The lower and upper bounds are not quite as obvious but are not much of a stretch.

  • Lower Bound:
    Pick a color for a single point on the sphere, and consider points on the great circle indicated by our constraint. Every point on the great circle must be different from the selected point, and we've already shown that a circle can be covered by two colors. Therefore the sphere requires at least 3 colors to cover it.
  • Upper Bound:
    Divide the sphere into two hemispheres, with the upper hemisphere taking the boundary (so that the lower hemisphere is "open"). Being careful with the boundaries, you can color each quadrant of the hemisphere with just four colors, but it requires that the point in the center of each hemisphere be a fifth color.
    A flattened illustration:
    enter image description here

(Each color can only take one of the boundaries, but I didn't show that in the illustration)

We now know that the sphere can be colored with 3-5 colors, but we want the minimum, and have yet to show that 3 and 4 colors are not possible. We discussed the "inversion of a sphere" problem and considered that there might be some "tricky" coloring that could be done with just three or four colors. (Fully aware that the problems are not analagous).

share|improve this question
    
To be perfectly clear, the constraint is still that any two points on the sphere which subtend a right angle at the center must be in different colours? –  Rahul Sep 24 '11 at 23:29
    
Maybe try to show the area of a region with the constraint that no two points in it are at right angles to each other must be less than $\pi$ (which is one-fourth the surface area)? –  anon Sep 24 '11 at 23:50
    
@anon: That would have to be $\le\pi$. –  Brian M. Scott Sep 25 '11 at 1:00
    
@Brian: In light of the fact that four colors can be used, the idea would then be to try proving the area must be strictly less than $4\pi/3$. Of course $\le\pi$ would be a strengthening of it but I can't see that it's a priori true. But I see now this line of thinking really doesn't establish anything because it doesn't account for the re-use of colors. –  anon Sep 25 '11 at 1:46
    
@anon: The fact that the rational points on the sphere can be coloured with $3$ colours but you need $4$ for the real points seems to indicate that arguments using only area won't completely determine the solution. –  joriki Sep 25 '11 at 4:06
show 2 more comments

2 Answers

up vote 6 down vote accepted

This problem is solved here, with a minimum of four colours. See also here. (Christian Blatter is mentioned as having posed this problem; he's quite active on this site.) Note that there's also an interesting connection to the Kochen–Specker theorem.

share|improve this answer
add comment

The fact that four colours are needed is due to Gleason. Suppose you have a non-negative function $f$ defined on the sphere that sums to one on the vectors in any orthonormal basis. He proved (in the course of proving what is now called "Gleason's theorem") that $f$ is continuous. How do we use this?

If we have a 3-colouring of the sphere, choose a colour class $C$. Define $f$ to be the characteristic function of this set---so $f(x)=1$ if $x\in C$ and $f(x)=0$ otherwise. Then $f$ is a non-negative function that sums to 1 on each orthonormal basis, but is certainly not continuous.

The Kochen-Specker theorem follows from Gleason's theorem by a compactness argument.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.