How can we prove Schwartz Zippel PIT is applicable to natural polynomials? The naturals lack subtraction, but SZ polynomial identity testing needs subtraction... I think it's applicable, but how to prove it?

Perhaps: SZ shows natural polynomials are equal iff it shows those polynomials are equal over integers. Integer polynomials are equal iff some sequence of algebraic manipulations transforms one into the other. Since these manipulations do not involve subtraction for our case (because no negatives), if they transform integer polynomials, they will also transform two natural polynomials.

But is that a proof? Is it even the right idea?



This question is based on the answer to Is there an efficient algorithm for expression equivalence?

We have two polynomials over the natural numbers. Are they equivalent?

If we take the same polynomials over integers (or some other ring)

$$f=g \implies f-g=0$$

But the reverse is not true, because $f-g$ may have roots, i.e. be zero without $f$ and $g$ being equal. The Schwartz Zippel lemma say how likely we are to have hit a root by chance, with a ramdom guess. By making repeated guesses we can be as sure as we like that we didn't get a root every time, (And if we ever get a non-zero, we know $f\neq g$.)

I've tried to simplify the question here, to focus on just one aspect, but maybe I've got it wrong and/or omitted important details.
Suppose that $P$ is a multivariate polynomial with integer coefficients. Then $P$ vanishes on all natural inputs iff it vanishes on all integer inputs. You can prove this by showing that if $P$ is not the zero polynomial then there is a natural input on which it is non-zero. This, in turn, you can prove by induction on the number of variables.

The base case is when $P$ is a univariate polynomial. In this case it is not hard to check that $P$ is non-zero for sufficiently large integer input. Suppose next that $P$ is a $(d+1)$-variate polynomial. Choose one variable $x$ which appears in some monomial of $P$, and write $P$ as a univariate polynomial whose coefficients are $d$-variate polynomials. Suppose that the highest power of $x$ that appears in $P$ is $x^n$, and that the corresponding coefficient is the $d$-variate polynomial $Q$ in the other variables. The induction hypothesis shows that there is an input on which $Q \neq 0$. Applying the base case again, we find a non-zero input for $P$.