patternMinor
Schwartz-Zippel lemma question
Viewed 0 times
schwartzquestionzippellemma
Problem
Schwartz-Zippel lemma is as follows. Let $f(x_1,\ldots,x_n)$ be a polynomial of total degree at most $d$ over a field $\mathbb{F}$ and assume that $f$ is not identically zero. Pick uniformally at random elements $r_1,\ldots,r_n$ from the field $\mathbb{F}$ then probability that
$$f(r_1,\ldots,r_n) = 0 \le \frac{d}{|\mathbb{F}|}$$
Let us assume that $f$ is multiplinear which means each of the monomial in the polynomial $f$ is of same degree. My question is as follows. Is the following bound (given below) tight or we can come up with a better bound?
$$f(r_1,\ldots,r_n) = 0 \le \frac{d}{|\mathbb{F}|}$$
$$f(r_1,\ldots,r_n) = 0 \le \frac{d}{|\mathbb{F}|}$$
Let us assume that $f$ is multiplinear which means each of the monomial in the polynomial $f$ is of same degree. My question is as follows. Is the following bound (given below) tight or we can come up with a better bound?
$$f(r_1,\ldots,r_n) = 0 \le \frac{d}{|\mathbb{F}|}$$
Solution
If $f = \prod_{i=1}^d x_i$ is a single monomial then
$$
\Pr[f=0] = 1 - \left(1 - \frac{1}{|\mathbb{F}|}\right)^d \geq \frac{d}{|\mathbb{F}|} - \frac{d^2}{2|\mathbb{F}|^2}.
$$
(The second bound is Bonferroni's inequality.)
This shows that Schwartz–Zippel is essentially tight when $d$ is small compared to $\mathbb{F}$.
The bound $1-(1-1/|\mathbb{F}|)^d$ is tight for multilinear polynomials, see this answer on math.se.
$$
\Pr[f=0] = 1 - \left(1 - \frac{1}{|\mathbb{F}|}\right)^d \geq \frac{d}{|\mathbb{F}|} - \frac{d^2}{2|\mathbb{F}|^2}.
$$
(The second bound is Bonferroni's inequality.)
This shows that Schwartz–Zippel is essentially tight when $d$ is small compared to $\mathbb{F}$.
The bound $1-(1-1/|\mathbb{F}|)^d$ is tight for multilinear polynomials, see this answer on math.se.
Context
StackExchange Computer Science Q#130810, answer score: 3
Revisions (0)
No revisions yet.