Skip to main content
12 of 14
added 28 characters in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Solving solutions to systems of polynomial equations over $\mathbb Z$

Macaulay Resultants help identify common root in $\mathbb P^{n-1}(\mathbb K)$ of $n$ homogeneous polynomials in $n$ variables when $\mathbb K$ is algebraically closed. Is it possible that some type of multivariate resultants give all solutions $(x_0,x_1,\dots,x_{n-1},x_n)\not=(0,0,\dots,0,0)$ with $x_0=1$ and $\prod_{i=0}^nx_i\neq0$ of $r\geq n+1$ degree $d$ homogeneous polynomials in polynomial ring $\mathbb Z[x_0,x_1,\dots,x_{n-1},x_n]$ $$f_1(x_0,x_1,\dots,x_n)=0$$ $$f_2(x_0,x_1,\dots,x_n)=0$$ $$\vdots$$ $$f_r(x_0,x_1,\dots,x_n)=0$$ or is there different technique that applies (we assume coefficient matrix is rank $r$)?

The method could be exponential in $n,d$ (note Macaulay Resultants are exponential in $n,d$ and I only seek a method that is compatible in complexity with algebraically closed case). It only needs to depend polylogarithmically in $q=\binom{n+d}d\max_j\|f_j\|_\infty$ (it is trivial to find a method with $O(\ell^{nd})$ complexity where $\ell=\|(x_0,x_1,\dots,x_n)\|_\infty$ is infinity norm of solutions sought and it is assumed $\ell<q$ holds but I seek something $O((\log q)^{nd})$ which is a much relaxed framework). If convenient we may think of working in $\mathbb Z_m[x_0,x_1,\dots,x_{n-1},x_n]$ with $m\gg\binom{n+d}d\max_j\|f_j\|_\infty$ a prime.

Undecidability is not an issue since roots are bounded.

Turbo
  • 13.9k
  • 1
  • 27
  • 76