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.

I have doubts about the proof of the Ham-Sandwich theorem descibed on planetmath (http://planetmath.org/proofofhamsandwichtheorem) and wikipedia (http://en.wikipedia.org/wiki/Ham_sandwich_theorem): There you fix one of the $n$ sets in $\mathbb R^n$ to be bisected and for each "direction" $p\in S^{n-1}$ and $t\in\mathbb R$ you consider all hyperplanes with normal vector $p$ containing $tp$. By the mean value theorem and the continuity properties of the Lebesgue measure you get $t\in \mathbb R$ such that the corresponding hyperplane cuts the set in two parts of equal mass. However, there might be a whole interval of such $t$ and both references cited above claim that you get a continuous function $t(p)$ if you choose the midpoint of that interval. (The $n-1$-dimensional Borsuk-Ulam theorem then finishes the proof.)

This is the point I do not see. The proof on planetmath strongly suggests that this "midpoint-continuity" holds for each continuous function $f: S^{n-1} \times \mathbb R \to \mathbb R$ which is increasing in the second variable and such that the level sets $\lbrace t\in \mathbb R: f(p,t)=0 \rbrace$ are not empty and compact intervals.

A counterexample to this claim is $f(p,t)= \|p-e\| t + \varphi(t)$ where $e$ is any fixed element of $S^{n-1}$ and $\varphi(t)$ is an increasing function whose $0$-set is $[0,1]$ (this is to make the level sets compact). The level sets are then singletons $\lbrace 0\rbrace$ for $p\neq e$ and $[0,1]$ for $p=e$.

I believe that something similar to this may really happen in the Ham-Sandwich situation.


I know that there are other proofs using the $n$-dimensional Borsuk-Ulam theorem. But the one discussed here has the advantage that you get the Pancake theorem from the $1$-dimensional Borsuk-Ulam which is so much simpler than the higher dimensional cases.

Do I misunderstand something?

share|improve this question
    
Maybe, we have a bit more here as $f(p,t)=-f(-p,-t)$. –  Hagen von Eitzen May 4 '13 at 12:35
    
This is true. But I do not see how this could help since continuity is a local property and $-p$ is very far from $p$. –  Jochen May 4 '13 at 12:48
    
I think the boundedness of the sets in the Ham sandwich theorem is vital somehow. At least, for unbounded sets, I can easily come up with an example where $t(p)$ becomes discontinuous. –  Harald Hanche-Olsen May 4 '13 at 13:57
    
I have no idea how boundedness could help. On the wikipedia page the theorem is stated for sets of finite measure which seems to be the natural assumption. Perhaps, several people have doubts: In the litreature you find often additional assumptions (compact or open sets, I think I have even seen a book assuming connectedness). –  Jochen May 4 '13 at 14:46
add comment

2 Answers

up vote 1 down vote accepted

Let $A$ be the set to be bisected, and let $H(p,t)=\{x\colon x\cdot p=t\|p^2\|\}$. Further, let $K$ be the essential support of $A$, i.e., $x\in K$ if every neighbourhood of $x$ meets $A$ in a set of positive measure. Note that $K$ is compact.

Further, for each $p\in S^{n-1}$ let $t_+(p)$ and $t_-(p)$ be the largest and smallest values of $t$ so that $H(p,t)$ bisects $A$ into pieces of equal measure.

Claim: $t_\pm(p)$ are continuous functions of $p$.

At a point $p$ for which $t_-(p)<t_+(p)$, it should be clear that $H(p,t)$ (with $t_-<t<t_+$) divides $K$ into disjoint compact sets $K_\pm$ (this is where boundedness comes in). Further, $t_\pm(p)$ is characterized by $H(p,t)$ just touching either of these sets. The continuity of $t_\pm$ is then easily established.

At a point $p$ where $t_-(p)=t_+(p)$, there are thin slices of $A$ to either side of $H(p,t)$ of positive measure. If you perturb $p$ a little, a small change in $t$ is sufficient to include the entire slice to one or the other side of $H(p,t)$. This will establish the continuity of $t_\pm$ at such a point.

share|improve this answer
    
I do not believe that $t_\pm$ are continous. If $A$ has a symmetry axis I think it can easily happen that there is only a single $p$ with $t_+(p) \neq t_-(p)$. Thus continuity of both functions is impossible (there should be a reason for taking the midpoint). –  Jochen May 4 '13 at 14:55
    
Well, I am quite confident that my proof is correct, at least as far as this particular point goes. If you can come up with a set $A$ with the property you mention, I shall be most impressed. (I admit I could have written up much more detail, but I don't have the time for it.) One detail: It is important for the argument of the penultimate paragraph that the sets $K_\pm$ don't change under small perturbations in $p$. –  Harald Hanche-Olsen May 4 '13 at 15:05
    
Okay, I start to believe that compactness might help (what I had in mind was most prbably wrong -- although I would have liked to impress you). As you mentioned in a previous comment, the claimed continuity seems to wrong in the unbounded case. –  Jochen May 4 '13 at 18:31
    
Indeed. So congratulations are in order for finding a gap in the proof at planetmath. The gap can be filled however, but writing it out in full detail may be a bit much, at least for wikipedia. On planetmath, I don't know. But I have the impression that they want their proofs to be complete. –  Harald Hanche-Olsen May 4 '13 at 19:15
    
Thanks a lot. I see the things much clearer, now. I have made a short comment on planetmath about the proof. We will see what happens. –  Jochen May 4 '13 at 20:11
add comment

If one simply wishes to prove the ham sandwich theorem (for bounded sets) I think one can avoid this discussion by a limiting argument. Superpose on $A$ a thin gas of uniform density $\rho$ filling a ball of radius (say) twice the diameter of $A$. Now the corresponding function $H(p,t)$ is continuous in $t$ with a positive derivative bounded away from zero, and it easily follows that $t(p)$ is unique and depends continuously on $p$.

Use this and the standard Borsuk-Ulam argument to solve the HST for the modified $A$ and the original $B$ and $C$. Now let the density $\rho$ of the gas go to zero. The set of potential solution planes is compact (a ball times a sphere) so we can extract a convergent subsequence of these planes as $\rho\to 0$. A limit of this subsequence will solve the original problem.

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.