The polynomials which occur in the Schwartz-Zippel lemma could be defined for any commutative ring, yet the lemma is restricted to fields. This makes it inapplicable for $(1+x^n)=1+x^n(\operatorname{mod}n)$ and similar identities, and feels a bit "unnatural" to me. Why can't
Lemma (Schwartz, Zippel).
Let
$P\in F[x_1,x_2,\ldots,x_n]$
be a non-zero polynomial of total degree $d \geq 0$ over a field, $F$. Let $S$ be a finite subset of $F$ and let $r_1, r_2, \dots, r_n$ be selected at random independently and uniformly from $S$.
Then
$\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}.$
be generalized to
Conjecture.
Let
$P\in R[x_1,x_2,\ldots,x_n]$
be a non-zero polynomial of total degree $d \geq 0$ over a "nice" commutative ring, $R$. Let $S$ be a finite subset of $R$ with "$\forall s, t\in S:((\exists u\in R:(u\neq 0\land su=tu))\Rightarrow s=t)$" and let $r_1, r_2, \dots, r_n$ be selected at random independently and uniformly from $S$.
Then
$\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}.$
Here "nice" would be some property that is satisfied for common rings like $\mathbb Z$ or $\mathbb Z/n\mathbb Z$. For example being a subring of the direct product of a family of fields might work for square-free $n$. (So "nice" commutative ring might be replaced by subring of a commutative (von Neumann) regular ring.) The condition "$\forall s, t\in S:(\dots)$" tries to ensure that one can apply the normal Schwartz-Zippel lemma independently to each field from the underlying family of fields. This condition is automatically satisfied for a subring of a field (like $\mathbb Z$), and can be checked easily by verifying $\operatorname{gcd}(s-t,n)=1$ for $\mathbb Z/n\mathbb Z$, hence it is no real limitation.
Question 1 Does this work, or am I overlooking something? (This question also refers to the implicit assumption that the reformulation is more useful than the original lemma, because it doesn't exclude "common rings like $\mathbb Z$ or $\mathbb Z/n\mathbb Z$". It applies to $(1+x^n)=1+x^n(\operatorname{mod}n)$, because "This condition … can be checked easily by verifying $\operatorname{gcd}(s-t,n)=1$ for $\mathbb Z/n\mathbb Z$, hence it is no real limitation.")
Question 2 Is it also possible to completely omit any "niceness" requirements for the ring, maybe by modifying the condition "$\forall s, t\in S:(\dots)$" slightly?
Edit Note that Question 1 has been answered in the comments, i.e. I am indeed overlooking something. The reformulation is true for arbitrary commutative rings, as shown by Emil Jeřábek's nice proof. However, it is not at all clear whether it is really more useful than the original lemma:
- $q\prod^{p−1}_{i=0}(x−i)$ in $\mathbb Z/pq \mathbb Z$ is a non-zero polynomial of total degree $p$, but it evaluates to $0$ for any $x\in\mathbb Z/pq \mathbb Z$. So even the reformulation can't be used directly to probabilistically check $(1+x^n)=1+x^n(\operatorname{mod}n)$. What I overlooked here is that the ability to check whether $s-t$ is a zero-divisor for the individual witnesses from $S$ used to evaluate $P$ is not enough to ensure $|S|>d$ with sufficiently high probability to efficiently test the identity $P=0$.
- The reformulation also can't be used directly for identity testing over $\mathbb Z$. The problem here is that the intermediate results during evaluation of $P$ can become too big for efficient computation. The original lemma can be applied to this problem by first randomly drawing a sufficiently big prime number $p$, and then doing the computation in the field $\mathbb Z/p \mathbb Z$. The probability to draw a divisor of $P$ is quite small, if $p$ was drawn from a sufficiently big collection. One could hope now that the reformulation would allow to randomly draw a sufficiently big $p^\alpha$ instead, and then do the computation in the ring $\mathbb Z/p^\alpha \mathbb Z$. But the fact that $|S|\leq p$ makes this inapplicable for $d>=p$. What one can do is apply the original lemma in $\mathbb Q$ (or the reformulation in $\mathbb Z$), and then draw sufficiently big random numbers $n_i$ for each individual evaluation of $P$. This seems to require more random bits, and doesn't need the reformulation either.
Best Answer
Your conjecture holds for arbitrary commutative rings.
First, your condition implies that a nonzero degree $d$ univariate polynomial $f\in R[x]$ can only have $d$ roots in $S$. One can show this e.g. by induction on $d$: the case $d=0$ is trivial, and if $f(x)$ of degree $d+1$ has distinct roots $a_1,\dots,a_{d+2}\in S$, we can write $f(x)=(x-a_{d+2})g(x)$ for some degree $d$ polynomial $g$. Since $a_i-a_{d+2}$ is cancellative for $i=1,\dots,d+1$, this means $g$ has $d+1$ roots $a_1,\dots,a_{d+1}$, contradicting the induction hypothesis.
Then we can prove the conjecture using the standard proof of the Schwarz–Zippel lemma, by induction on $n$.
The case $n=1$ is the property above. Assuming the statement holds for $n$, an $(n+1)$-variate nonzero polynomial can be written as $$f(x_1,\dots,x_{n+1})=\sum_{i\le d'}x_{n+1}^if_i(x_1,\dots,x_n),$$ where $f_{d'}$ is nonzero. We have $$\Pr(f_{d'}(x_1,\dots,x_n)=0)\le\frac{\deg(f_{d'})}{|S|}$$ by the induction hypothesis, and if $f_{d'}(a_1,\dots,a_n)\ne 0$, then $$\Pr(f(a_1,\dots,a_n,x_{n+1})=0)\le\frac{d'}{|S|}$$ by the univariate case, hence $$\Pr(f(x_1,\dots,x_{n+1})=0)\le\frac{d'+\deg(f_{d'})}{|S|}\le\frac d{|S|}.$$