# Worst case polynomial in elimination theory under rank conditions?

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?

• 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. – Joshua Grochow Jan 20 '19 at 0:25
• @JoshuaGrochow Please look modifications made. – T.... Jan 22 '19 at 5:05