# Does there exist a polynomial $P(x,y)$ which detects all non-squares?

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.

• A possibly helpful note: This can be done with two very similar polynomials $P_1(x,y)=(x+y-1)^2+y$ and $P_2(x,y)=(x+y-1)^2+(x+y-1)+y$. These two polynomials have disjoint images, with $\operatorname{Im}(P_1)\cup \operatorname{Im}(P_2)$ representing all non-squares: the image of $P_1$ is the union of the intervals $[n^2+1,n^2+n]$ for each $n\geq 1$, while the image of $P_2$ is the union of the intervals $[n^2+n+1,n^2+2n]$ for each $n\geq 1$. (This can be used to construct a $3$-variable polynomial $$P(x,y,z)=\big(1-(z-1)(z-2)\big)\big((x+y-1)^2+(z-1)(x+y-1)+y\big)$$ with the desired property. May 6 at 6:12