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.

  • 4
    $\begingroup$ 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. $\endgroup$ May 6 at 6:12


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.