Problem. Does there exist a two-variable polynomial $P(x, y)$ with integer coefficients such that a positive integer $n$ is not a perfect square if and only if there is a pair $(x, y)$ of positive integers such that $P(x, y)=n$?
Context. The answer is positive for polynomials in 3 variables! This appeared as a problem in USA Team Selection Test in 2013. It turns out that the polynomial $P(x, y, z)=z^2\cdot (x^2-zy^2-1)^2+z$ enjoys the following property: a positive integer $n$ is a not a perfect square if and only if $P(x, y, z)=n$ has a solution in positive integers $(x, y, z)\in \mathbb{N}^{3}$. This construction works nicely due to Pell's equation. If $n$ is not a perfect square, then Pell's equation $x^2-ny^2=1$ has a solution in positive integers $(x_0, y_0)$, and so we get $P(x_0, y_0, n) = n$. Conversely, if $P(x, y, z)=n$, then one can show that $n$ cannot be a perfect square because $n=z^2(x^2-zy^2-1)^2+z$ can be squeezed between two consecutive perfect squares: $$ (z(x^2-zy^2-1))^2 < n < (z(|x^2-zy^2-1|+1)^2 $$
Remark. It is clear that there is no single-variable polynomial $P(x)$ which could achieve the desired property. Indeed, there are arbitrary number of consecutive non-squares, and a polynomial $P(x)$ of degree $n>1$ cannot output a consecutive list of $n+1$ numbers. This last claim itself is a nice problem; for a solution, see Example 2.24 in page 11 of Number Theory: Concepts and Problems by Andreescu, Dospinescu and Mushkarov.
