TAOCP 4.6.1 Exercise 16
Let N(S_1,\ldots,S_n) = |S_1|\cdots |S_n| -
Section 4.6.1: Division of Polynomials
Exercise 16. ▶ [M22] Let $f(x_1, \ldots, x_n)$ be a multivariate polynomial that is not identically zero, and let $r(S_1, \ldots, S_n)$ be the set of roots $(x_1, \ldots, x_n)$ of $f(x_1, \ldots, x_n) = 0$ such that $x_j \in S_j$ for all $j$. If the degree of $f$ is at most $d_j \le |S_j|$ in the variable $x_j$, prove that
$$|r(S_1, \ldots, S_n)| \le |S_1| \cdot |S_2| \cdots |S_n| - (|S_1| - d_1) \cdots (|S_n| - d_n).$$
Therefore the probability of finding a root, by randomly choosing $x_j \in S_j$, approaches zero as the sets $S_j$ get bigger. [This inequality has many applications in the design of randomized algorithms, because it provides a good way to test whether a complicated sum of products of sums is identically zero without expanding out all the terms.]
Verified: yes
Solve time: 3m29s
Solution
Let
$$ N(S_1,\ldots,S_n) = |S_1|\cdots |S_n| - (|S_1|-d_1)\cdots(|S_n|-d_n). $$
We shall prove that
$$ |r(S_1,\ldots,S_n)|\le N(S_1,\ldots,S_n) $$
for every nonzero polynomial
$f(x_1,\ldots,x_n)$ whose degree in $x_j$ is at most $d_j$.
The proof is by induction on $n$.
For $n=1$, the polynomial $f(x_1)$ is a nonzero univariate polynomial of degree at most $d_1$. A nonzero polynomial of degree at most $d_1$ has at most $d_1$ roots in $S_1$. Hence
$$ |r(S_1)|\le d_1. $$
Since
$$ N(S_1) = |S_1|-(|S_1|-d_1) = d_1, $$
the result holds when $n=1$.
Assume now that the theorem holds for $n-1$ variables, and consider a nonzero polynomial
$$ f(x_1,\ldots,x_n). $$
Write it as a polynomial in $x_n$:
$$ f(x_1,\ldots,x_n) = \sum_{k=0}^{t} g_k(x_1,\ldots,x_{n-1}),x_n^k, $$
where $t\le d_n$ and $g_t\not\equiv0$.
Let
$$ T=S_1\times\cdots\times S_{n-1}. $$
For each point
$$ a=(a_1,\ldots,a_{n-1})\in T, $$
consider the univariate polynomial
$$ f_a(x_n) = f(a_1,\ldots,a_{n-1},x_n). $$
Partition $T$ into two sets:
$$ A={a\in T:g_t(a)=0}, \qquad B=T\setminus A. $$
Since $g_t$ is not identically zero and its degree in $x_j$ is at most $d_j$ for $1\le j\le n-1$, the induction hypothesis gives
$$ |A| \le |T| - \prod_{j=1}^{n-1}(|S_j|-d_j). \tag{1} $$
For each $a\in B$, the polynomial $f_a(x_n)$ is nonzero and has degree exactly $t\le d_n$. Therefore it has at most $d_n$ roots in $S_n$.
For each $a\in A$, there are at most $|S_n|$ roots in $S_n$.
Hence the total number of roots satisfies
$$ |r(S_1,\ldots,S_n)| \le |A|,|S_n| + |B|,d_n. $$
Since $|B|=|T|-|A|$,
$$ |r(S_1,\ldots,S_n)| \le |A|(|S_n|-d_n) + |T|,d_n. \tag{2} $$
Substituting the bound (1) into (2) yields
$$ \begin{aligned} |r(S_1,\ldots,S_n)| &\le \Bigl( |T| - \prod_{j=1}^{n-1}(|S_j|-d_j) \Bigr) (|S_n|-d_n) + |T|,d_n \ &= |T||S_n| - (|S_n|-d_n) \prod_{j=1}^{n-1}(|S_j|-d_j). \end{aligned} $$
Since
$$ |T|=|S_1|\cdots|S_{n-1}|, $$
we obtain
$$ |r(S_1,\ldots,S_n)| \le |S_1|\cdots|S_n| - \prod_{j=1}^{n}(|S_j|-d_j). $$
This is exactly the desired inequality.
Therefore
$$ \boxed{ |r(S_1,\ldots,S_n)| \le |S_1|\cdots|S_n| - (|S_1|-d_1)\cdots(|S_n|-d_n) }. $$
To derive the probabilistic statement, choose each $x_j$ independently and uniformly from $S_j$. The probability that the chosen point is a root is
$$ \frac{|r(S_1,\ldots,S_n)|} {|S_1|\cdots|S_n|} \le 1- \prod_{j=1}^{n} \left(1-\frac{d_j}{|S_j|}\right). $$
The degrees $d_j$ are fixed, while $|S_j|\to\infty$. Hence
$$ \frac{d_j}{|S_j|}\to0 \qquad (1\le j\le n), $$
so
$$ \prod_{j=1}^{n} \left(1-\frac{d_j}{|S_j|}\right) \to1, $$
and consequently
$$ 1- \prod_{j=1}^{n} \left(1-\frac{d_j}{|S_j|}\right) \to0. $$
Therefore the probability of finding a root by random selection approaches $0$ as the sets $S_j$ become larger.
This completes the proof.
∎