# Do many homogeneous polynomials help in faster integer root extraction?

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)?

• 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. – Dima Pasechnik Mar 24 at 23:09
• @DimaPasechnik Promise Problem. We assume things in input in promise problem. – VS. Mar 25 at 2:10