This question came to me after answering this question about Diophantine sets over at MathOverflow. (It may strike the reader as frivolous, but there you go.) Prompted by this question I started wondering if there were interesting Diophantine subsets $A$ of $\mathbb{N}_{>0}$ for which one could write down relatively simple polynomials $f \in \mathbb{Z}[X]$ such that the set of positive values of $f$ equals $A$ (i.e. $f(\mathbb{Z}) \cap \mathbb{N}_{>0} = A$). It occurred to me that I should start by asking about finite Diophantine sets.
I then found that yes, it is easy to do this: for finite sets $A$ of positive integers, the following polynomial $$ f = X \left( 1 - X \cdot \prod_{a \in A} (X - a)^2 \right) $$ takes the value $x$ at $X=x$ if $x \in A$, and is negative if $x \notin A$. (Proof. If $x>0$ and we let $X=x$ in the expression for $f$, then clearly the second factor in the expression is non-positive, except if $x \in A$, when it equals unity. If $x \leq 0$ on the other hand, then it is clearly positive. Combining the conclusions from both cases, the product comes out negative or zero if $x \notin A$, and as $x$ when $x \in A$.)
So if $A$ has $n$ elements, this gives us a degree $2n+2$ polynomial $f$ such that the set of positive values of $f$ equals $A$. Since I like to be economical in the construction of my polynomials (parsimony is a virtue after all), I wonder whether this number is in fact the best we can do.
For each $n$, do we need a degree $2n+2$ polynomial in general to represent an $n$-element set $A$ of positive integers in the above manner? Put more precisely, for each $n$ does there exist an $n$-element set $A$ of positive integers such that $A$ is not the set of positive values of $f$ for any polynomial $f$ of degree $\leq 2n+1$?