14
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nick S
    Feb 11, 2011 at 20:12
  • $\begingroup$ 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. $\endgroup$ Feb 11, 2011 at 22:54
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 11, 2011 at 23:06
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 11, 2011 at 23:11
  • $\begingroup$ 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.) $\endgroup$ Feb 12, 2011 at 17:34

5 Answers 5

14
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Feb 11, 2011 at 20:23
  • 2
    $\begingroup$ Of course once you reach $k=n$, you can square the result and see if it works. $\endgroup$ Feb 11, 2011 at 20:26
  • $\begingroup$ 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. $\endgroup$ Feb 11, 2011 at 20:38
  • $\begingroup$ 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$. $\endgroup$ Feb 11, 2011 at 21:07
10
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 12, 2011 at 2:33
  • $\begingroup$ @Greg: It is indeed essentially the same as what your answer says; I was interested in carrying through the solution concretely. $\endgroup$
    – ARupinski
    Feb 12, 2011 at 3:22
  • $\begingroup$ 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. $\endgroup$ Feb 12, 2011 at 19:44
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 11, 2011 at 20:47
  • 1
    $\begingroup$ @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. $\endgroup$ Feb 11, 2011 at 22:37
  • $\begingroup$ @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 $\endgroup$ Feb 12, 2011 at 19:46
  • $\begingroup$ @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? $\endgroup$
    – Igor Rivin
    Feb 12, 2011 at 22:33
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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