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.

  • $\begingroup$ 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. $\endgroup$ – Geoffrey Irving May 4 '13 at 0:45

Unfortunately, the Schwartz-Zippel lemma is close to tight regardless of the degree with no extra assumptions on the polynomial. For example, if

$$ 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.

It's possible that an irreducibility assumption would help, though.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.