How can I write down polynomial relations that define when a polynomial is a square? It's easy to tell when a polynomial is squarefree (or not): that's just the question of the vanishing of the discriminant, which can be dealt with as the resultant of $f$ and $f'$.  However, given a polynomial of degree $2n$ $f$, when is it of the form $g^2$ for $g$ a polynomial of degree $n$?
I've been trying to work out the relations on the coefficients that will guarantee this for a specific degree ($n=6$ is my case) but whenever I take the obvious equations in the coefficients of $g$ and of $f$ and try to use Groebner bases to eliminate the coefficients of $g$, I run out of memory and my software crashes.  Is there a way to understand the locus of polynomials which are squares concretely without having to do a (seemingly unrealistically) big computation? Or perhaps a clever trick that will give these polynomial identities in a more computable way?
 A: http://en.wikipedia.org/wiki/Square-free_polynomial gives a method for finding a square-free factorization of a polynomial (over characteristic zero field), ie
$f=a_1\cdot a_2^2\cdots a_n^n$ where each $a_i$ is a square-free polynomial.  Then $f$ is a perfect square iff $a_{2i+1}=1$ for each $i$.
A: It seems to me that the OP almost contains the answer: the gcd of $f$ and $f^\prime$ (let's assume characteristic zero) contains all the irreducible factors of $f$ which appear with exponent greater than $1.$ This is surely enough to figure out if the polynomial is a square.
EDIT to answer the revised version of the question:
Write down $$\sum_{i=0}^n a_i x^i = (\sum_{j=0}^{n/2} b_j x^j)^2.$$
This gives a collection of $n+1$ quadratic equations in $3n/2 + 2$ variables. You now eliminate the $b_j$ to get the variety of perfect squares. Needless to say, this is not algorithmically very pleasant  (the degree is going to be exponential in $n$), but you can use successive resultants or Grobner bases to do it for small degrees, and you might see a pattern.
Another Edit
If you have Mathematica, you can perform the above-mentioned experiments with the program below:
genpoly[deg_, name_, var_] := Sum[name[i] var^i, {i, 0, deg}]
quadraticeq[deg_, name1_, name2_, var_]:= Eliminate[MapThread[Equal, {CoefficientList[genpoly[2deg, name1, var], var],CoefficientList[Expand[genpoly[deg, name2, var]^2], var]}], Table[name2[i], {i, 0, deg}]]
(for example, to see what the variety is describing quadratic polynomials which are squares, you do:
quadraticeq[1, a, b, x]
a and b are dummy variables, a[0], ..., a[2 deg] are the variables you care about. For quadratic polynomials you get (no surprise):
4 a[0] a[2]==a[1]^2
While for quartic polynomials you get:
a[0] a[3]^2==a[1]^2 a[4]&&-4 a[0] a[1] a[2]+8 a[0]^2 a[3]==-a[1]^3&&8 a[0] a[3] a[4]==a[1] (-a[3]^2+4 a[2] a[4])&&16 a[0] a[4]^2==-a[2] a[3]^2+4 a[2]^2 a[4]-2 a[1] a[3] a[4]&&8 a[1] a[4]^2==a[3] (-a[3]^2+4 a[2] a[4])&&a[0] (-4 a[2]^2+2 a[1] a[3])+16 a[0]^2 a[4]==-a[1]^2 a[2]&&a[0] (-4 a[2] a[3]+8 a[1] a[4])==-a[1]^2 a[3]
which is a little more painful.
A: Say, for simplicity, you are working over $\mathbb{C}$ or in characteristic zero in general.  Then you can guess one of the two values of $g(0)$ (say) and then compute the Taylor series of $\sqrt{f}$.  The approach is similar to Hensel lifting:  The equation for the first coefficient is non-linear; the equations for the others are all locally linear (so that you get explicit formulas for the coefficients of $g$ in terms of existing data).

I first misread Charles' question, but now that I have it right (I think), here is why I think that the above is still a solution.  If you read the coefficients of a polynomial of degree $n$ as projective coordinates, then over $\mathbb{C}$ the set of squares of degree $2n$ is some projective variety $S$ in $\mathbb{C}P^{2n}$.  Charles is interested in projective equations for this variety $S$.
For simplicity let's rescale the polynomial $f(x)$ so that $f(0) = 1$.  (And I guess we're working the affine chart in which $f(0) \ne 0$ before the rescaling.  It shouldn't change things much or at all.)  Then you can assume that $g = \sqrt{f}$ also satisfies $g(0) = 1$, and you can make explicit expressions for its Taylor series.  Then $g$ is a polynomial of degree $n$ if and only if its Taylor series vanishes in degree $n < k \le 2n$.  I think that this gives you the desired equations.
A: So unless I am misunderstanding the question, temporarily normalize so that the coefficient of $x^6$ in $f$ is 1. One is left with three degrees of freedom, coming from the quadradic, linear and constant terms of the degree 3 polynomial square root.
For concreteness, let $f(x) = x^6 + c_5x^5 + c_4x^4 + c_3x^3 + c_2x^2 + c_1x + c_0$
Then I work out that necessary relations on the coefficients are:
$c_2 = 2(\frac{1}{2}c_5)(\frac{1}{2}c_3-\frac{1}{4}c_4c_5+\frac{1}{16}c_5^3)+(\frac{1}{2}c_4-\frac{1}{8}c_5^2)^2$
$c_1 = 2(\frac{1}{2}c_4-\frac{1}{8}c_5^2)(\frac{1}{2}c_3 - \frac{1}{4}c_4c_5 + \frac{1}{16}c_5^3)$
$c_0 = (\frac{1}{2}c_3 - \frac{1}{4}c_4c_5 + \frac{1}{16}c_5^3)^2$
These are also sufficient since if they hold, then $f$ is the square of $x^3+(\frac{1}{2}c_5)x^2+(\frac{1}{2}c_4-\frac{1}{8}c_5^2)x + (\frac{1}{2}c_3-\frac{1}{4}c_4c_5+\frac{1}{16}c_5^3)$
Unless I did something wrong, it doesn't seem like these computations should be crashing the system. What are you using to run the Groebner calculations?
A: The solution of this problem for detecting polynomials $f$ which are squares or more generally a power $g^p$ is in my article "On Hilbert covariants" with Chipalkatti in Canadian J. Math. 66 (2014), no 1, 3--30. The idea in Greg's answer works in general and is in fact due to Hilbert. In our article we also give an alternate formula for the relevant covariant in determinantal form (eq. 12 on page 9 in the arXiv version) which may be more useful for practical computations.
