13

5

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?

flag
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 2011 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 2011 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 2011 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 2011 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 2011 at 17:34
show 1 more comment

4 Answers

15

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.

link|flag
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 2011 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 2011 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 2011 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 2011 at 21:07
11

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?

link|flag
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 2011 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 2011 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 2011 at 19:44
4

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

link|flag
4

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.

link|flag
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 2011 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 2011 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 2011 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 2011 at 22:33

Your Answer

Get an OpenID
or

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