How do we check if a polynomial is a perfect square? 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.
 A: You can devise some tests fairly easily for the quartic case. Suppose you want to know if $a_4x^4+a_3x^3+a_2x^2+a_1x+a_0$ is a square.
(1) $a_4,a_0$ must both be squares. Suppose the square roots are $a,c$.
(2) We must have $a_3/a$ and $a_1/c$ equal and even. Suppose it is $2b$.
(3) $a_2$ must be $b^2\pm2ac$.
So in your example, it passes (1) $a=c=1$. So it passes (2) and $b=3$. So it passes (3) $7=3^2-2\times1\times1$.
Then the square root is $ax^2\pm bx\pm c$. You have to check to see which signs work.
But in practice I doubt if that is particularly useful, except maybe (1).
A: Generally one can quickly test if a polynomial is an $n$'th power as follows. First do some probabilistic tests via evaluations in $\,\Bbb Z\,$ and finite fields. If it passes these tests then apply Newton iteration (Newton's method) to compute any $n$'th root.
For an overview of the complexity of this and related problems see Daniel Roche's 2011 thesis Efficient Computation with Sparse and Dense Polynomials. Here is a direct link to the pertinent chapter 6: Sparse perfect powers.
A: 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$.
