Often we come across polynomial diophantine equations of the form $y^2 = x^2 + x+ 1$ and there are two ways to disprove the existence of solutions to such equations:
1) By bounding between consecutive perfect squares.
2) By reading the equations in $\mathbb{Z}_n$ and using the quadratic reciprocity laws in $\mathbb{Z}_n$.
However these techniques fail when there are infinitely many solutions to the diophantine. For example, the diophantine $y^2 = x^4 + 6x^3 + 7x^2 – 6x + 1$ has infinitely many solutions since it is equivalent to $y^2 = (x^2+ 3x -1)^2$. Further, it looks like generating such a problem is easy, but 'identifying' the square root is hard.
So my question is:
1) Is there a way one can tell whether a polynomial is a perfect square using a simple criterion on the coefficients?
2) Is there a way one can recover the square root by a simple algorithm?
Thanks!
P.S: Note that I don't mean to say that the only way $y^2 = f(x)$ can have infinitely many solutions is when $f(x)$ is a perfect square. I know that $y^2 = 2x^2 + 1$ and $y^2 = x^3$ have infinitely many solutions as well. I am just interested in the particular case of perfect squares.
Best Answer
Let $p=p_0+p_1x+\ldots+p_{2n}x^{2n}\in\mathbb{Z}[x]$ be a polynomial of degree $2n$ and $p_0=k^2\neq 0$. Taking the square root of $p$ is a straight forward procedure, detailed below. In general this will result in a power series instead of a polynomial (of course, not all such polynomials are perfect squares).
$$\sqrt{p(x)}=\sum_{m=0}^{\infty}a_mx^m.$$
Then $p$ is a perfect square if and only if $a_m=0$ for all $n<m\leq 2n$. This follows from the recursion for the coefficients:
$$\begin{eqnarray} a_0&=&k\\ a_{n+1}&=&\frac{p_{n+1}-\sum_{m=1}^na_ma_{n+1-m}}{2k} \end{eqnarray}$$
Let's try this on one of Will's examples: $p=1-6x+7x^2+6x^3+x^4$. Starting with $a_0=1$ we find the coefficients $$1, -3, -1, 0, 0$$ at which point we can conclude that $p=(1-3x-x^2)^2$.