0
$\begingroup$

Given $n$ homogeneous algebraically independent total degree $2$ polynomials with no $x_1^2,\dots,x_n^2$ variable in $\mathbb Z[x_1,\dots,x_n]$ with promise that it has non-zero integer roots with coordinates of $O(n)$ bits in magnitude we can extract at least one common integer root with elimination theory in exponential $SPACE$ and $TIME$.

Suppose we have $m\geq n$ homogeneous independent total degree $2$ polynomials with no $x_1^2,\dots,x_n^2$ variable in $\mathbb Z[x_1,\dots,x_n]$ with promise that it has non-zero integer roots with coordinates of $O(n)$ bits in magnitude and with

  1. any $n$ of them being algebraically independent

  2. only common roots of all $m$ polynomials being integer roots

then does it help improve extracting at least one integer root to subexponential $SPACE$ and $TIME$ complexity where input size is $L$ bits (measure of number of coefficients and number of bits in coefficients) at some $m=\Omega(n^{1+\epsilon})$ for a fixed $\epsilon\in(0,\infty)$ (gaussian elimination picks something integral without relevance to non-linear properties)?

$\endgroup$
  • $\begingroup$ why would one always have an integer root? excluding 0, naturally, as you work with homogeneous polynomials you always will have 0 as a common root. $\endgroup$ – Dima Pasechnik Mar 24 at 23:09
  • $\begingroup$ @DimaPasechnik Promise Problem. We assume things in input in promise problem. $\endgroup$ – VS. Mar 25 at 2:10

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.