Discrete Polynomial Ham-Sandwich Theorem: Consider an algebraic hypersurface of degree $k$ in $\Bbb R^n$; let $Q$ be a polynomial of degree $k$ in $n$ variables. Define $m := \binom {n + k} {n}$ - 1. Let $A_1, \ldots, A_m$ be disjoint finite sets in $\Bbb R^n$. Then there exists $Q$ s.t. $$ \forall i \in [m], \quad \left| A_i \cap \{ Q<0 \} \right|, \left| A_i \cap \{ Q > 0 \} \right| \le \frac {\left| A_i \right|} 2 $$
Proof: I read a proof sketch for the Discrete Ham-Sandwich Theorem (see at the bottom) in which the "cutting"/bisecting surface is (degenerate to) only being a hyperplane (rather than an algebraic hypersurface). In this proof I got familiar with the "trick of balls with volume" (do you have a better name for that?). My question is why not using the same "trick of balls with volume" to reduce the discrete case into the continuous case (in which $A_1, \ldots, A_m \subset \Bbb R^n$ are disjoint bounded open sets), to which I already have a proof sketch (see below)?
Thank you.
Proof sketch for Continuous Polynomial Ham-Sandwich Theorem: Let $Q$ be a polynomial of degree $k$ in $n$ variables. We want to show that $\exists Q$ s.t. $$ \forall i \in [m], \quad vol \left( A_i \cap \{ Q<0 \}\right) = vol \left( A_i \cap \{ Q > 0 \}\right) = \frac {vol(A_i)} 2 $$ Note that $m$ is the number of non-constant monomials in $n$ variables of degree $\le k$. Thus we can make polynomials of degree $≤ k$ from points of the $m$-sphere $\Bbb{S^m}$ by identifying the vector $b = (b_0 , \ldots , b_m) ∈ \Bbb S^m$ with the polynomial $Q_b$ whose coefficients are precisely the values $b_0 , \ldots , b_m$. Define $f : \Bbb S^m \rightarrow \Bbb R^m$ as follows
$$ f_i (b_0 , \ldots , b_m) = vol \left( A_i \cap \{ Q_b<0 \}\right) - vol \left( A_i \cap \{ Q_b > 0 \}\right) $$ In other words, the $i$-th coordinate of $f$ measures how good the hyperplane $\{Q_b = 0\}$ is at bisecting the set $A_i$; In particular, this hyperplane bisects $A_i$ if and only if $f_i(b_0 , \ldots, b_m ) = 0$. $f$ can be shown to be continuous using the dominated convergence theorem. Intuitively, if we vary $b_0 , \ldots , b_m$ by just a little bit, then the polynomial $Q_b$ will only change a little bit, which means that the location of its zero-set $\{Q_b = 0\}$ will only change a little bit, so the value of each $f_i$ will only change a little bit; then since every $f_i$ is continuous, we get that $f$ is continuous. Also, $f$ is odd since every coordinate satisfy $$ \begin{split} f_i(-b_0 , \ldots, -b_m ) &= vol \left( A_i \cap \{ Q_{-b}<0 \}\right) - vol \left( A_i \cap \{ Q_{-b} > 0 \}\right) \\ &= vol \left( A_i \cap \{ Q_{b} > 0 \}\right) - vol \left( A_i \cap \{ Q_{b} < 0 \}\right) \\ &= -f_i(b_0 , \ldots, b_m ) \end{split} $$ By the Borsuk–Ulam theorem, $\exists (a_0 , \ldots , a_m) ∈ \Bbb S^m$ s.t. $f (a_0 , \ldots , a_m) = 0$. This implies that the hypersurface $\{Q_a = 0\}$ bisects each $A_i$.
Proof sketch for Discrete Ham-Sandwich Theorem: For each $i \in [m]$ we define $A_i'$ to be the set of balls of radius $\epsilon$, centered around every point in $A_i$, namely $A_i' := \bigcup_{x \in A_i} B(x, \epsilon)$. We choose $\epsilon$ s.t. the hyperplane intersects in total at most $n$ balls. Therefore whenever $n$ is odd, we know that on one hand the hyperplane must intersect at least one ball for each $A_i'$, but on the other hand it can't intersect more than $n$ balls; concluding that the hyperplane intersect exactly one ball for each $A_i'$, and by symmetry the hyperplane must pass through the ball's center in order to bisect its volume. It means that the hyperplane bisects the original $A_i$ as required. Otherwise (i.e $n$ is even), it's possible to remove any point, do what we did for odd $n$, then return the point, since we are guaranteed that on each side of the hyperplane there won't be more than half of the points (after adding back the removed point).
