Proof of the Polynomial Ham-Sandwich Theorem

Question

I'm currently reading through Simple Proofs of Classical Theorems in Discrete Geometry via the Guth–Katz Polynomial Partitioning Technique and I have what might be a very silly question, but I'm not a very experienced in reading papers by myself.

Specifically, I had problems with the proof of theorem 2.5:

The proof of the theorem is rather short and uses (some) discrete version of the Ham-Sandwich Theorem the authors bring without a proof. This is the theorem as the authors formulate it:

And this is the proof:

I have two questions about the proof (actually I bet it's just explaining the proof, sorry!)

1. Why can we assume $s=k$?
2. It is not easy for me to check that the polynomial they defined is the desired polynomial.

I understand the relationship between $z_{ij}$ and $x^iy^j$, but obviously not well enough because I can't see how the points in $\mathbb{R}^k$ being below or above that hyperplane have anything to do with whether the polynomial evaluated at a certain point is positive or negative.

Any help would be much appreciated!

Answer 1

Not sure if this question would ever help anyone, but for the sake of completeness I would post an answer because I think I might've got it now.

1. We may assume $s=k$ since if $s\leq k$ we can add some dummy sets to bisect. Generally if we were able to bisect $k$ sets we already bisected $s$ sets.
2. We note that if we sent $p$ to $\Phi (p )=p'$ and regard the $a_{ij}$ as a vector in $\mathbb{R}^k$ than we get $f(p )=a_{00} +\underline{p '}\cdot\underline{a_{ij}}$. (the for product- since by definition of $\Phi$ this corresponds to evaluate the polynomial at $p$). Since the hyperplane is the zero set of that linear equation we get that anything above it would be positive and anything below it would be negative (with respect to evaluation of the polynomial of course)