# Analogue of the Schwartz–Zippel lemma for subspaces

Let $f : \mathbb{R}^n \to \mathbb{R}$ be a nonzero multivariate polynomial of total degree $d$ over the reals, and $S \subset \mathbb{R}$ be finite. Pick a positive integer $k$, choose $y_1, \ldots, y_k$ randomly and uniformly from $S^n$, and consider the $k$-variable polynomial

$$g(t_1, \ldots, t_k) = f(t_1 y_1 + \cdots + t_k y_k)$$

Question: Is there a nice upper bound on the probability that $g(t)$ is the zero polynomial?

This is similar to the Schwartz-Zippel lemma, but instead of picking a single point we pick a random linear subspace. Indeed, if $k = 1$, $f$ is homogeneous, and $0 \notin S$, it is exactly the Schwartz-Zippel lemma, and we have

$$Pr(g=0) \le \frac{d}{|S|}$$

For general $k$, allowing only one $t_i$ to be nonzero at a time gives

$$Pr(g=0) \le \frac{d^k}{|S|^k}$$

However, this bound seems very weak, since it ignores all the cross terms in $g$, so hopefully a much stronger bound exists.

• Interestingly, the Schwartz-Zippel derived bound is tight for linear $f$ ($d = 1$), so any stronger bound for higher degree would need to use the fact that higher terms exist. – Geoffrey Irving May 4 '13 at 0:45

$$f(x_1, \ldots, x_n) = (x_1 - s)^d$$
for $s \in S$, then
$$Pr(g = 0) \ge \frac{1}{|S|^k}$$
so Schwartz-Zippel is tight up to the relatively small factor $d^k$. In general, higher degree terms do not always help since they can be powers of a linear term.