1. Pick a set of primitive (gcd of coordinates is $1$) integer points $\mathcal T$ in $\mathbb Z^n$.

  2. Denote the set of $n$ many algebraically independent homogeneous system of polynomials (thus zero-dimensional system) in $\mathbb Z[x_1,\dots,x_n]$ with degree $2$ with absolute value of coefficients bound by $2^{n^c}$ size at a fixed $c\geq1$ with all the points in $\mathcal T$ being their primitive integer roots to be $\mathcal P$.

Note that for a system of polynomials $H\in\mathcal P$ we may have additional real roots in $\mathbb R^n$. However integer roots come from every point in $\mathcal T$ and are the only integer roots in $H$.

Note that for system of polynomials $H_1,H_2\in\mathcal P$ we have all the integer roots agreeing. However real roots may not agree and in fact may have no real roots in common.

Consider the problem 'Given $H_1$ and $H_2$ from $\mathcal P$ does the intersection of roots equal $\mathcal T$?'.

I would also think with probability $1$ we have answer is 'yes'.

  1. What is the probability that the answer is 'yes'?

  2. Is this in $NP$ (note it is not clear it is in $coNP$ either as we might need infinite precision real roots to certify 'no')?


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.