A Near-Optimal Polynomial Distance Lemma over Boolean Slices

The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that n-variate non-zero polynomial functions of degree d over a field F, are non-zero over any “grid” (points of the form Sⁿ for finite subset S ⊆ F) with probability at least max{|S|⁻d/(|S|−¹⁾, 1 − d/|S|} over the choice of random point from the grid. In particular, over the Boolean cube (S = {0, 1} ⊆ F), the lemma asserts non-zero polynomials are non-zero with probability at least 2^−d. In this work we extend the ODLSZ lemma optimally (up to lower-order terms) to “Boolean slices” i.e., points of Hamming weight exactly k. We show that non-zero polynomials on the slice are non-zero with probability (t/n)^d(1 − on(1)) where t = min{k, n − k} for every d ≤ k ≤ (n − d). As with the ODLSZ lemma, our results extend to polynomials over Abelian groups. This bound is tight upto the error term as evidenced by multilinear monomials of degree d, and it is also the case that some corrective term is necessary. A particularly interesting case is the “balanced slice” (k = n/2) where our lemma asserts that non-zero polynomials are non-zero with roughly the same probability on the slice as on the whole cube. The behaviour of low-degree polynomials over Boolean slices has received much attention in recent years. However, the problem of proving a tight version of the ODLSZ lemma does not seem to have been considered before, except for a recent work of Amireddy, Behera, Paraashar, Srinivasan and Sudan (SODA 2025), who established a sub-optimal bound of approximately ((k/n) · (1 − (k/n)))^d using a proof similar to that of the standard ODLSZ lemma. While the statement of our result mimics that of the ODLSZ lemma, our proof is significantly more intricate and involves spectral reasoning which is employed to show that a natural way of embedding a copy of the Boolean cube inside a balanced Boolean slice is a good sampler.