4
$\begingroup$

Let $k \in \mathbb{N}$. Given an algorithm $\mathcal{A}$ which takes as argument a polynomial $P \in \mathbb{Z}[x_1,\dots,x_k]$ and either returns true or false, we say that $\mathcal{A}$ works for $P$ if either the equation $P(x_1,\dots,x_k) = 0$ has integer solutions and $\mathcal{A}$ returns true or the equation has no integer solutions and $\mathcal{A}$ returns false. Otherwise we say that $\mathcal{A}$ fails for $P$.

Further, given such algorithm $\mathcal{A}$ and $k, d, C \in \mathbb{N}$, let $f_{\mathcal{A}}(k,d,C)$ denote the number of polynomials $P \in \mathbb{Z}[x_1,\dots,x_k]$ of total degree at most $d$ and coefficients with absolute value bounded above by $C$ for which $\mathcal{A}$ fails.

Question: What is the best known asymptotic lower bound for $f_{\mathcal{A}}(k,d,C)$?

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't know what kind of answer you're expecting. I expect the algorithm that always returns false will do pretty well; maybe it's not even possible to do better than this asymptotically. $\endgroup$
    – Qiaochu Yuan
    Commented Oct 20, 2014 at 16:55
  • 1
    $\begingroup$ The algorithm that always returns false should be pretty good when $d>k$. Slightly better in this range would be to perform a search for solutions up to some power of $C$. For $d \le k$ it's probably better to check local solvability. In that range one expects many equations to have solutions so the always false algorithm won't be so good. I don't know how to get a lower bound that works for all algorithms, i.e., estimate the density of undecidable equations. $\endgroup$
    – Felipe Voloch
    Commented Oct 20, 2014 at 17:43

0

Reset to default

You must log in to answer this question.