= Independent repetition of a polynomial identity test
{title2=$p_k=p_1^k\le(d/|S|)^k\quad(d<|S|)$}
Repeat the <random evaluation test for a polynomial identity> with fresh <independent random variables>, keeping the same fixed <polynomial>. Reject as soon as any <polynomial evaluation> is nonzero; accept only if all $k$ values vanish. An identity is always accepted, preserving <one-sided error>. If a nonzero <polynomial> has single-trial false acceptance <probability> $p_1$, <independence> gives $p_k=p_1^k$. The <Schwartz-Zippel lemma> bounds this by $(d/|S|)^k$ when $d<|S|$.
For $G(x)=(x-1)(x-2)$ over the <finite field> $\mathbb F_5$, two uniform <independent> choices $(a,b)$ have $25$ equally likely ordered outcomes, each with <probability> $1/25$. Both <polynomial evaluations> are zero only at $(1,1),(1,2),(2,1),(2,2)$. Hence false acceptance falls from $2/5$ in one trial to $4/25$ in two trials, and correct rejection rises from $3/5$ to $21/25$.
\Image[/polynomial-identity-independent-trials.png]
{title=Four of the twenty-five independent pairs falsely accept the nonidentity}
{description=The orange cells have both coordinates among the <polynomial roots> one and two of $G(x)=(x-1)(x-2)$ in the <finite field> $\mathbb F_5$. Every blue cell supplies at least one nonzero witness. The full grid enumerates exact outcomes under <independence> and a <uniform distribution on a finite set>; it is not a simulation.}
If the second choice reuses the first, the pair is $(a,a)$ and only five diagonal outcomes are possible. Two still falsely accept, so the error remains $2/5$. Choosing fresh <independent> points is precisely what makes the full $25$-cell grid and the product of <probabilities> valid. For a target error $0<\varepsilon<1$, this example needs
$$
k\ge\left\lceil\frac{\log(1/\varepsilon)}{\log(5/2)}\right\rceil.
$$
The <ceiling function> makes the trial count an <integer>. Four trials give $(2/5)^4=16/625>1/100$, while six give $64/15625<1/100$; five still give $32/3125>1/100$, so six is the first count below one percent. This is an exact error guarantee for each run on $G$, rather than an observed success rate.
Back to article page
