1
$\begingroup$
  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')?

$\endgroup$

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.