2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for going to the trouble to answer this! I may not have enough background to unpack even the basics, so please let me check my understanding. I tried unpacking the logic of the two middle sentences of the first para, and I think they are related by: P vanishes on all natural inputs $\iff$ P is the zero polynomial $\iff$ P vanishes on all integer inputs. $\endgroup$ – hyperpallium Jun 7 '18 at 3:39
  • $\begingroup$ I think the base case works by the fundamental theorem of algebra showing that there are a maximum of $n$ natural roots of an $n$-degree polynomial. Because $n$ is finite, and there are infinitely many natural numbers, the rest must be non-roots, i.e. non-zero. I was confused by "sufficiently large integers", thinking it should be sufficiently many, but realized they mean the same thing for natural numbers. $\endgroup$ – hyperpallium Jun 7 '18 at 5:09
  • $\begingroup$ Finally, I'm not sure this answers my question (the issue troubling me might be too obvious to notice!). I think I understand your answer after a few hours, but I'm not sure how it links up to my question. In my scenario, we $f-g$ to (maybe) get the zero polynomial, so there will be negative coefficients. But, subtraction of naturals is not closed. $\endgroup$ – hyperpallium Jun 7 '18 at 5:35
  • $\begingroup$ I also redrafted this question at mathematics SE, and my confusion might be clearer there If two polynomials over integers are equivalent, are the same polynomial expressions defined over positive integers also equivalent? $\endgroup$ – hyperpallium Jun 7 '18 at 5:35
  • $\begingroup$ I added an answer. I think it belabours the obvious, but is what I needee. I wonder if you could have a look please? $\endgroup$ – hyperpallium Jun 7 '18 at 7:19
1
$\begingroup$

You want to know if you can show two natural polynomials are equivalent by showing that the same polynomials are equivalent, if taken to be integer polynomials.

(This is so you can use subtraction in $P-Q=0$, to check for $P=Q$, even though $P,Q$ are natural polynomials).

Definitions By natural (or integer) polynomial, we mean the coefficients are naturals (or integers); and the inputs and outputs are naturals (or integers) - i.e, they are functions with natural (or integer) domain and range.

Steps Firstly, taking these purely as expressions (ignoring inputs and outputs), polynomials with natural coefficients are a subset of polynomials with integer coefficients (because $\Bbb N \subset \Bbb Z$). Therefore, every natural polynomial expression is also an integer polynomial expression.

Next, if we have two integer polynomial expressions which have natural coefficients (so they are also natural polynomial expressions), and they give the same integer values for all integer inputs, then they must also give the same outputs for all natural inputs (again, because $\Bbb N \subset \Bbb Z$). This covers natural inputs.

Finally, we want to show that the outputs will also be naturals. Because the coefficients and inputs are natural, and polynomials are calculated by addition and multiplication of coefficients and inputs, and addition and multiplication are closed over naturals, the output will also be natural.

Conclusion Therefore, we have shown that if two polynomials with integer coefficients, inputs and outputs are equivalent, then (assuming these particular coefficients are also natural) the same two polynomials with natural inputs and outputs are also equivalent. Thus, we can use equivalence of integer polynomials to show equivalence of natural polynomials (specifically, we can use $P-Q=0$ to check for natural polynomial equivalence, even though subtraction isn't closed over natruals).

BTW I haven't shown that two polynomials being equal for all possible inputs means they are equivalent, but I think that's the definition, isn't it? By "equivalent", I mean things like $a+ab+b=a(1+b)+b$, and whether $a+ab+b - (a(1+b)+b) = 0$ for all values of $a,b$.

PS This procedure, of checking a natural polynomials with integers, reminds me of some differential equations, with real coefficients and real solutions, but can only be solved by using complex numbers in between.

$\endgroup$
  • $\begingroup$ My answer shows that if a polynomial is not identically zero then it has a natural non-root. $\endgroup$ – Yuval Filmus Jun 7 '18 at 10:16

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.