Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
Probably not the answer you are looking for, but for a square polynomial $gcd(f,f')$ has all roots of odd multiplicity, and if $2k_i-1$ is the multiplicity of the $x_i$th root then $\sum_i k_i=n$. The converse is also true, the condition $\sum_i k_i=n$ guarantees that $f$ doesn't have any simple roots. –  Nick S Feb 11 '11 at 20:12
    
Not directly related to your question: what did you use as a Groebner solver? Last I checked (admittedly a while ago), Mathematica or Maple were vastly outperformed by more specialized software. This might be an interesting avenue to explore, regardless of a more theoretical solution. –  Thierry Zell Feb 11 '11 at 22:54
1  
Trivial observation: You must require the field to be algebraically closed, or the polynomial to be monic or something stronger. Else, $aX^2$ will reduce the undecidable is-$a$-a-square to your is-my-polynomial-a-square. –  darij grinberg Feb 11 '11 at 23:06
    
Also, the answers require the field to have characteristic $0$. This seems to have a good reason: If the field has characteristic $2$, then you can reduce the question is-a-field-element-$a$-a-square to your is-my-polynomial-a-square (apply to the polynomial $X^2-a$). Of course, there is no polynomial equation that tells you when an element of a field of characteristic $2$ is a square. –  darij grinberg Feb 11 '11 at 23:11
    
Note on darij's remark: Let $k$ have characteristic other than $2$. Let $f$ be a polynomial in $k[x]$. Then $f$ is square in $k[x]$ if and only if $f$ is square in $k^{\mathrm{alg}}[x]$ and the leading term of $f$ is square in $k$. So the issues about algebraic closure are comparatively mild. (This is evident from looking at Greg's explicit solution.) –  David Speyer Feb 12 '11 at 17:34
show 1 more comment

4 Answers

up vote 15 down vote accepted

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.

share|improve this answer
    
Maybe I'm not understanding properly, but wouldn't the conditions I want then be that for all $k>n$, the $k$th coefficient of $sqrt(f)$'s Taylor series vanishes? Doesn't that give me infinitely many conditions (a priori) and no obvious way to know which finite set of them suffice? –  Charles Siegel Feb 11 '11 at 20:23
2  
Of course once you reach $k=n$, you can square the result and see if it works. –  Greg Kuperberg Feb 11 '11 at 20:26
    
Ok...perhaps you could be more explicit about what you're doing, because when I Taylor expand $\sqrt{f}$, I get that the degree of the coefficient of $x^i$ is $i$ in the coefficients of $f$ (well, with a $\sqrt{a_0}$ to some power in the denominator). I'm not sure what you're doing, or what the output should be, but I'm looking for a finite set of polynomials in the coefficients of $f$ whose vanishing determines that $f$ is a square. –  Charles Siegel Feb 11 '11 at 20:38
    
It's true that I misinterpreted the problem, but I think that, at the expense of a $\sqrt{a_0}$, the solution still works. The coefficients of the Taylor series of $g$ vanish for $n < k \le 2n$ if and only if $g$ is a polynomial of degree $n$. –  Greg Kuperberg Feb 11 '11 at 21:07
add comment

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?

share|improve this answer
1  
This is equivalent to the solution that I describe, except of course working from the other end. The explicit calculation is nice; it shows quite clearly that it works. –  Greg Kuperberg Feb 12 '11 at 2:33
    
@Greg: It is indeed essentially the same as what your answer says; I was interested in carrying through the solution concretely. –  ARupinski Feb 12 '11 at 3:22
    
When I said "$n=6$", I meant the case where $\deg f=12$, which makes this much, much worse for a CAS to work out. –  Charles Siegel Feb 12 '11 at 19:44
add comment

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$.

share|improve this answer
add comment

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.

share|improve this answer
1  
That would be fine for determining if a given polynomial is a square, but I'm looking for the equations that define the locus of square polynomials, and I don't see how to do that in this way. –  Charles Siegel Feb 11 '11 at 20:47
1  
@Charles: everyone who has answered the question has misread it so far, so I've taken the liberty of making the title more precise. Hope I have captured your meaning. –  Qiaochu Yuan Feb 11 '11 at 22:37
    
@Igor: This is essentially what I was doing in Macaulay2, but the elimination step was too bad by the time I got to 12th degree polynomials –  Charles Siegel Feb 12 '11 at 19:46
    
@Charles: yes, mathematica seems to choke on this as well (not surprisingly -- macaulay 2 should be more efficient). But what are you trying to do with these equations? –  Igor Rivin Feb 12 '11 at 22:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.