Timeline for Resultants for compactly represented product form polynomials?
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 8, 2019 at 4:04 | comment | added | Turbo | Assume the system of $n$ non-homogeneous polynomial $h_1(x_1,\dots,x_n)+c_1,\dots,h_n(x_1,\dots,x_n)+c_n$ has $m$ common roots in $\mathbb Z^n$. Can we output all roots in $O(n^npoly(m))$ time? | |
| Jan 8, 2019 at 0:47 | comment | added | Turbo | If I have $n$ non-homogeneous polynomials in $f_1,\dots,f_n\in\mathbb Z[x_1,\dots,x_n]$ of form $f_i(x_1,\dots,x_n)=h_i(x_1,\dots,x_n)+c_i$ where $h_i(x_1,\dots,x_n)$ is homogeneous of degree $d$ and $c_i\in\mathbb Z$ with $gcd(f_i(x_1,\dots,x_n),f_j(x_1,\dots,x_n))=1$ at every $1\leq i<j\leq n$ and I know that they have at least one common root in $\mathbb Z^n$ is it possible to use resultants in elimination theory or Grobner basis here to find the roots? At least if I had $n+1$ such polynomials can we use elimination theory to obtain common root? | |
| Sep 24, 2018 at 14:25 | comment | added | Abdelmalek Abdesselam | A good introduction is this article by Cattani and dickenstein mate.dm.uba.ar/~alidick/papers/chapter1cd.pdf the multiplicative property I used is eq. (1.55) in that reference. | |
| Sep 24, 2018 at 14:18 | comment | added | Turbo | I do not have the background to read that book. Do you know anywhere they talk more about idenities? At least can you throw in few more identities? I want to see if there is a divide and conquer method. | |
| Sep 24, 2018 at 14:08 | comment | added | Abdelmalek Abdesselam | GKZ is this book springer.com/us/book/9780817647704 | |
| Sep 22, 2018 at 20:38 | comment | added | Turbo | May be there is a divide and conquer approach with some useful resultant identities to get to polynomial size determinant? | |
| Sep 21, 2018 at 23:23 | comment | added | Turbo | I checked Cox book not many identities there. What is gkz book? | |
| Sep 21, 2018 at 17:34 | history | edited | Abdelmalek Abdesselam | CC BY-SA 4.0 |
added 399 characters in body
|
| Sep 21, 2018 at 17:31 | comment | added | Abdelmalek Abdesselam | There is the book "Using Algebraic Geometry" by Cox, Little and O'Shea. At more advanced level there the famous GKZ book. | |
| Sep 21, 2018 at 17:29 | comment | added | Turbo | What is a good reference for identity properties of resultants like the identity you used? | |
| Sep 21, 2018 at 16:30 | history | edited | Abdelmalek Abdesselam | CC BY-SA 4.0 |
added 481 characters in body
|
| Sep 20, 2018 at 21:03 | comment | added | Turbo | It looks like $|A\times B|=\prod_{i=1}^n\prod_{j=1}^n|\mathcal T_j||\mathcal U_i|$ and so it is exponential. | |
| Sep 20, 2018 at 20:41 | comment | added | Turbo | It would nice if you could update accordingly when you have time. Please elaborate your logic to get the elimination done for your closed as well when you have time and thank you for the help. | |
| Sep 20, 2018 at 20:40 | comment | added | Abdelmalek Abdesselam | @Freeman.: I don't know. I would need to invest more time on this which is not a priority for me at the moment. | |
| Sep 20, 2018 at 20:37 | comment | added | Turbo | Not clear from your post. We see each determinant is in polynomial size (in fact linear size $2n\times2n$). Is the cardinality of $A\times B$ bounded by polynomial size as well at least for the given polynomials? | |
| Sep 20, 2018 at 20:28 | comment | added | Abdelmalek Abdesselam | @Freeman.: answer updated accordingly. | |
| Sep 20, 2018 at 20:28 | history | edited | Abdelmalek Abdesselam | CC BY-SA 4.0 |
added 1012 characters in body
|
| Sep 20, 2018 at 18:42 | comment | added | Turbo | Moreover I need to express it as determinant of polynomial size and not just compute in polynomial time. By the way it should have been $\mathbb P^{2n-1}(\mathbb C)$ since we have $2n$ variables here. I am looking at $2n$ homogeneous polynomials in $2n$ varibales. So the latter resultant in your case. | |
| Sep 20, 2018 at 18:32 | comment | added | Turbo | My goal is to find if polynomials $f_j,g_i$ have common zero in $\mathbb P^{2n}(\mathbb C)$ in polynomial time. Do you know which resultant would work here in polynomial time? | |
| Sep 20, 2018 at 14:54 | history | answered | Abdelmalek Abdesselam | CC BY-SA 4.0 |