17
$\begingroup$

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:

  1. $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$.
  2. 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.
$\endgroup$
  • 1
    $\begingroup$ For a commutative ring, "subring of a direct product of fields" is equivalent to being reduced (no nonzero nilpotent elements). In a noetherian commutative ring it's also equivalent to "subring of a finite direct product of fields". $\endgroup$ – YCor Nov 3 '14 at 13:08
  • 1
    $\begingroup$ I now see the next problem: $q\prod_{i=0}^{p-1}(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 Emil Jeřábek's nice version of the lemma/conjecture can't be used directly to probabilistically check $(1+x^n)=1+x^n(\operatorname{mod}n)$, which was one of the motivations for this question in the first place. One can try to go to some extension ring to fix this, but the hoped for/suggested simplicity is lost nevertheless. $\endgroup$ – Thomas Klimpel Nov 4 '14 at 23:02
9
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ Maybe I should also stress that the conditions on $S$ are necessary even in the simplest possible case: if $ua=ub$ for distinct $a,b\in S$ and $u\ne0$, the degree $1$ univariate polynomial $u(x-a)$ has at least two zeros in $S$. $\endgroup$ – Emil Jeřábek Nov 3 '14 at 19:21
4
$\begingroup$

See Section 4 in "On Zeros of a Polynomial in a Finite Grid" to see how Schwartz-Zippel lemma and many similar results on zeros of polynomials work for arbitrary commutative rings as long as the "grid" $S_1 \times S_2 \times \dots \times S_n \subseteq R^n$ satisfies a certain Condition (D) which is the same as the condition given in your conjecture applied to each $S_i$.

$\endgroup$

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.