4
$\begingroup$

I want to check for a polynomial whether it is a perfect square.

Using the functions for polynomial factoring and decomposition, this is possible by first applying FactorList, after which you can check all these terms whether there is a polynomial that has degree equal the half of the original polynomial and divides the original polynomial twice. However, this seems like unoptimal use of Mathematica and takes time as well, as we have to iterate through a list.

Using Sqrt (a bit naive, I know) combined with PolynomialQ does not work either as Mathematica (rightly) doesn't simplify this.

Hence, my question is: is there any relatively simple (i.e. easier/less computationally heavy) method for determining whether a polynomial is a square?

Edit: three small examples:

CheckIfSquare[x^2 - 1] should give False.

CheckIfSquare[x^2 - 2x + 1] should give True as $x^2 - 2x + 1 = (x-1)^2$.

CheckIfSquare[x^3] should give False, even though x^3 is not squarefree, it is not a square itself.

|improve this question
$\endgroup$
  • 4
    $\begingroup$ FactorSquareFreeList is cheaper than full factorization. Then check that all exponents other than for the constant term are even. $\endgroup$ – Daniel Lichtblau Jan 27 '17 at 23:49
  • $\begingroup$ @DanielLichtblau: Thanks, this seems already better than my own soluton. Anythins possible without using any form of FactorList? $\endgroup$ – Stapler Jan 27 '17 at 23:54
  • 2
    $\begingroup$ You could also add fast negative criterion at the beginning by returning False if plugging in a value for x results in a non-square number. $\endgroup$ – Chip Hurst Jan 28 '17 at 0:26
  • $\begingroup$ @ChipHurst: Thanks, that makes sense. $\endgroup$ – Stapler Jan 28 '17 at 12:27
  • 1
    $\begingroup$ FSFL is really different from FL in that is is based entirely on GCD computations. No actual "factorization" is performed. $\endgroup$ – Daniel Lichtblau Jan 28 '17 at 16:49
3
$\begingroup$

This code can be streamlined, but it seems to work:

CheckIfSquare[poly_] := 
 AllTrue[Transpose[Drop[FactorList[poly], 1]][[2]], EvenQ[#]&]

Check: 

CheckIfSquare[x^2 - 1]

(* False *)

CheckIfSquare[x^2 - 2 x + 1]

(* True *)

CheckIfSquare[x^3]

(* False *)

And....

CheckIfSquare[81 - 108 x + 54 x^2 - 12 x^3 + x^4]

(* True *)

...as 81 - 108 x + 54 x^2 - 12 x^3 + x^4 = (x-3)^4

Closely related, based on Daniel Lichtblau:

AllTrue[
 Drop[FactorSquareFreeList[(x + 1)^2 (x - 9)^4], 1]
 [[All, 2]], EvenQ]
|improve this answer
$\endgroup$
  • $\begingroup$ But what about $x^3$? It will come up as not being squarefree, but it is not a perfect square. I'll add it to the question. $\endgroup$ – Stapler Jan 28 '17 at 0:03
  • $\begingroup$ Thanks for the effort, this seems to work. $\endgroup$ – Stapler Jan 28 '17 at 12:28
6
$\begingroup$

A little trick I learned long, long ago.

CheckIfSquare[p_] := Simplify[D[p, x]^2] === Simplify[4 p]

x^2-1 returns False, x^2-2 x+1 returns True, x^3 returns False

As always, using equality on the result of a chain of calculations on approximate coefficients may fail. There might be other cases I haven't thought of where this can fail, I can't think of any at the moment. But it is just so cute. And it requires no factorization at all.

EDIT: Late last night I realize that I had forgotten the details of using this and had made a mistake in this. The original purpose of this trick was to rapidly see if it was possible to find a factor of a polynomial without needing to invoke full factorization and when the power of something like MMA wasn't available. The polynomial GCD of the polynomial and it's derivative would give that. It actually fails even for some quadratics like (2 x - 7)^2 and only works correctly when the derivative of the factor equals 1 and the polynomial is quadratic. Thanks for the comments letting everyone know that I made a mistake here and FactorSquareFreeList followed by processing the degrees returned from that should be used.

|improve this answer
$\endgroup$
  • $\begingroup$ Very elegant! I like this solution, and as I am using polynomials with rational coefficients, approximations should be no problem. $\endgroup$ – Stapler Jan 28 '17 at 12:30
  • 2
    $\begingroup$ I think this is only correct when p is quadratic. With n = Exponent[p, x], the degree of D[p, x]^2 is 2n-2 and the degree of 4p is n. $\endgroup$ – Chip Hurst Jan 28 '17 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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