Skip to main content
Post Undeleted by user124864
Post Deleted by user124864
added 246 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

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 in $\infty$ norm. and I only seek a slightly cleverer algorithm to trivial one. It also does not seem amenable to simple reduction from factoring such as $x_1x_2-Nx_0^2=0$ as it does not look like amenable to producing two additional homogeneous equations so that $x_0=1$ and product of coordinates of roots $\neq0$ holds.

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 in $\infty$ norm. I only seek a slightly cleverer algorithm to trivial one.

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 in $\infty$ norm and I only seek a slightly cleverer algorithm to trivial one. It also does not seem amenable to simple reduction from factoring such as $x_1x_2-Nx_0^2=0$ as it does not look like amenable to producing two additional homogeneous equations so that $x_0=1$ and product of coordinates of roots $\neq0$ holds.

added 28 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

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 in $\infty$ norm. I only seek a slightly cleverer algorithm to trivial one.

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.

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 in $\infty$ norm. I only seek a slightly cleverer algorithm to trivial one.

added 28 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

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.

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

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.

added 118 characters in body; edited title
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
deleted 19 characters in body; edited title
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
deleted 19 characters in body; edited title
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
deleted 19 characters in body; edited title
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
added 139 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
added 190 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
added 50 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
Rollback to Revision 2
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
added 11 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
Post Undeleted by user124864
Post Deleted by user124864
deleted 8 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading