Given homogeneous degree $2$ randomly chosen polynomials $f_1,\dots,f_{m}$ in $\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$ each with only monomials $x_iy_j$ with condition that the system $f_1=\dots=f_{m}=0$ has an unique common root in $\mathbb Z^{2n}\backslash\{{(0,\dots,0)}\}$ upto sign and exchange of $x$ and $y$ variables we can extract the root with elimination theory in $2^{O(n)}poly(\max\log\|f_i\|_\infty)$ time if $m=2n$ holds. Assume we have $m=poly(n)$ random equations (note only any $2n$ of them can be algebrically independent and they will be so with high propbaility).

  1. Is there an approach that can give $O(poly(n)poly(\max\log\|f_i\|_\infty))$ time?

  2. What conditions are on the polynomials are needed to extract the unique root in $O(poly(n))poly(\max\log\|f_i\|_\infty)$ time in case roots 1. does not have a general algorithm?

Is this approachable using Sum-of-squares? Note $f_i^2$ are all non-negative and have same integer roots.

  • $\begingroup$ Interesting question. I'm curious as to the motivation? $\endgroup$ Mar 18 '19 at 21:43
  • $\begingroup$ @JoshuaGrochow The motivation is circuitous and I can communicate privately if interested. $\endgroup$
    – Mr.
    Mar 18 '19 at 22:02
  • $\begingroup$ Sure, I'd be curious to hear. $\endgroup$ Mar 18 '19 at 22:51
  • $\begingroup$ @JoshuaGrochow Ok I will send you email. However do you think this can be solved? $\endgroup$
    – Mr.
    Mar 18 '19 at 23:26
  • $\begingroup$ @JoshuaGrochow I have completed documentation of this. May I send information on this approach? $\endgroup$
    – Mr.
    Jun 5 '19 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.