First of all, let me define $Dioph(M)$, where $M$ is a set of numbers: $$Dioph({M})=\{p \mid \text{ $p$ is a polynomial with integer coefficients and the zeros of $p$ are in ${M}$}\}.$$

Let $p \in Dioph({Z})$ and $q\in Dioph({N})$.

I am trying to find a (computable) reduction $f$ from $Dioph(Z)$ to $Dioph(N)$.

My idea for the reduction is as follows. Let $p$ be a polynomial with $k$ variables. There must be a $k$-tuple $(a_1,\dots,a_k)$ so that $p(a_1,\dots,a_k)=0$. I define $$f(p(x_1,\dots,x_n)) =(x-|a_1|)(x-|a_2|)\dots(x-|a_k|).$$

When I try to prove that $p \in Dioph(Z)$ iff $f(p) \in Dioph(N)$, I have trouble reconstructing $p$ from $f(p)$. I would appreciate any hints.

  • $\begingroup$ Your reduction doesn't work, for several reasons. First, $p$ might not have any roots. Second, it's not clear how you would find $a_1,\ldots,a_k$. Third, $p$ could have other roots besides $(a_1,\ldots,a_k)$. $\endgroup$ – Yuval Filmus Nov 28 '17 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.