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

$\endgroup$
5
  • 4
    $\begingroup$ FactorSquareFreeList is cheaper than full factorization. Then check that all exponents other than for the constant term are even. $\endgroup$ Commented Jan 27, 2017 at 23:49
  • $\begingroup$ @DanielLichtblau: Thanks, this seems already better than my own soluton. Anythins possible without using any form of FactorList? $\endgroup$
    – Stapler
    Commented Jan 27, 2017 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$
    – Greg Hurst
    Commented Jan 28, 2017 at 0:26
  • $\begingroup$ @ChipHurst: Thanks, that makes sense. $\endgroup$
    – Stapler
    Commented Jan 28, 2017 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$ Commented Jan 28, 2017 at 16:49

2 Answers 2

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]
$\endgroup$
2
  • $\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
    Commented Jan 28, 2017 at 0:03
  • $\begingroup$ Thanks for the effort, this seems to work. $\endgroup$
    – Stapler
    Commented Jan 28, 2017 at 12:28
7
$\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.

$\endgroup$
2
  • $\begingroup$ Very elegant! I like this solution, and as I am using polynomials with rational coefficients, approximations should be no problem. $\endgroup$
    – Stapler
    Commented Jan 28, 2017 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$
    – Greg Hurst
    Commented Jan 28, 2017 at 15:47

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.