1
$\begingroup$

Given $n$ polynomials $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$ where each of $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$ is homogeneous of degree $d$ and $r_1,\dots,r_{2n}\in\mathbb Z$ what is the complexity of finding common roots over $\mathbb Z$ for the polynomial system $$h_{2n}(x_1,\dots,x_{2n})=0,\dots,h_{2n}(x_1,\dots,x_{2n})=0?$$

Is the time and space complexity $f(B^d)d^{O(n)}$ at some polynomial $f$ if the roots are bound in $B$ and we have the condition $x_ix_{n+j}=x_jx_{n+i}$ at every $i,j\in\{1,\dots,n\}$?

I am unable to find a polynomial system which needs $d^{O(n)}$ choices with $x_ix_{n+j}=x_jx_{n+i}$ true. Is there such a polynomial system?

I think the complexity might be more like $f(B^dnd)$. Is it possible to prove this?

Improve this question
$\endgroup$
2
  • $\begingroup$ Probably uncomputable. I don't know for sure, but I doubt the homogeneous version of Hilbert's tenth problem has a different answer than the inhomogeneous one. $\endgroup$
    – Joshua Grochow
    Commented Jan 20, 2019 at 0:25
  • $\begingroup$ @JoshuaGrochow Please look modifications made. $\endgroup$
    – Turbo
    Commented Jan 22, 2019 at 5:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.