# How do we check if a polynomial is a perfect square?

Often we come across polynomial diophantine equations of the form $y^2 = x^2 + x+ 1$ and there are two ways to disprove the existence of solutions to such equations:

1) By bounding between consecutive perfect squares.

2) By reading the equations in $\mathbb{Z}_n$ and using the quadratic reciprocity laws in $\mathbb{Z}_n$.

However these techniques fail when there are infinitely many solutions to the diophantine. For example, the diophantine $y^2 = x^4 + 6x^3 + 7x^2 - 6x + 1$ has infinitely many solutions since it is equivalent to $y^2 = (x^2+ 3x -1)^2$. Further, it looks like generating such a problem is easy, but 'identifying' the square root is hard.

So my question is:

1) Is there a way one can tell whether a polynomial is a perfect square using a simple criterion on the coefficients?

2) Is there a way one can recover the square root by a simple algorithm?

Thanks!

P.S: Note that I don't mean to say that the only way $y^2 = f(x)$ can have infinitely many solutions is when $f(x)$ is a perfect square. I know that $y^2 = 2x^2 + 1$ and $y^2 = x^3$ have infinitely many solutions as well. I am just interested in the particular case of perfect squares.

Let $p=p_0+p_1x+\ldots+p_{2n}x^{2n}\in\mathbb{Z}[x]$ be a polynomial of degree $2n$ and $p_0=k^2\neq 0$. Taking the square root of $p$ is a straight forward procedure, detailed below. In general this will result in a power series instead of a polynomial (of course, not all such polynomials are perfect squares).

$$\sqrt{p(x)}=\sum_{m=0}^{\infty}a_mx^m.$$

Then $p$ is a perfect square if and only if $a_m=0$ for all $n<m\leq 2n$. This follows from the recursion for the coefficients:

$$\begin{eqnarray} a_0&=&k\\ a_{n+1}&=&\frac{p_{n+1}-\sum_{m=1}^na_ma_{n+1-m}}{2k} \end{eqnarray}$$

Let's try this on one of Will's examples: $p=1-6x+7x^2+6x^3+x^4$. Starting with $a_0=1$ we find the coefficients $$1, -3, -1, 0, 0$$ at which point we can conclude that $p=(1-3x-x^2)^2$.

• Thank you, I have a hard time choosing answers now :( Sep 6, 2014 at 15:37
• @Isomorphism: Conceptually, this one is much simpler. And probably easier to program too, if that's what you want to do. Sep 6, 2014 at 16:52
• I actually wanted to solve a math problem which said find all monic polynomials with integer co-effs $f(x)$ such that $y^2 = f(x)$ has infinitely many solutions. I solved it yesterday for the case of even degree. Anyway, I will give bounty to one post and accept the other. Both are nice. Sep 6, 2014 at 17:37

I would emphasize the idea about repeated roots. A polynomial over, say, the integers, but with roots considered in $\mathbb C,$ has repeated roots under very specific conditions, and that can be used; for each real root $\alpha,$ we know that $(x-\alpha)$ divides $f(x)$ to degree at least 2, so it divides the derivative to at least degree 1. With a complex root $\beta,$ same fact for the product $(x - \beta)(x - \bar{\beta}).$ As a result, if there is a square root $s(x),$ then $$s(x) | \gcd(f(x), f'(x)).$$ The magical part is that the $\gcd$ has integer coefficients and the top degree coefficient can be forced to be 1.
I would say that this idea does not help with general factoring, but is definitive for squares: we can either say that the polynomial is not a perfect square or find the square root.

Pausing... Here, taking $f(x) = x^4 + 6 x^3 + 7 x^2 - 6 x + 1,$ with $f'(x) = 4 x^3 + 18 x^2 + 14 x,$ and $g = \gcd(f(x), f'(x)),$ we get $$g | h = (4f - x f') = 6 x^3 +14 x^2 - 18 x + 4.$$ Then $$g | (3f' - 2 h) = 26 x^2 + 76 x + -26 = 26 (x^2 + 3 x - 1).$$ And that works.

Next: higher (even) powers involved

I made up an example; I am hoping to show that one may address this question with two operations, taking formal derivative of polynomials, and taking gcd of two polynomials.

$$f = x^8 - 10 x^7 + 35 x^6 - 56 x^5 + 91 x^4 - 210 x^3 + 189 x^2 - 108 x + 324$$

$$f' = 8 x^7 - 70 x^6 + 210x^5 - 280x^4 + 364x^3 - 630x^2 + 378x - 108$$

$$g_{01} = \gcd(f,f') = x^5 - 8 x^4 + 20x^3 - 18x^2 + 27x - 54$$

how to find gcd:

====================================

$$\left( x^{8} - 10 x^{7} + 35 x^{6} - 56 x^{5} + 91 x^{4} - 210 x^{3} + 189 x^{2} - 108 x + 324 \right)$$

$$\left( 4 x^{7} - 35 x^{6} + 105 x^{5} - 140 x^{4} + 182 x^{3} - 315 x^{2} + 189 x - 54 \right)$$

$$\left( x^{8} - 10 x^{7} + 35 x^{6} - 56 x^{5} + 91 x^{4} - 210 x^{3} + 189 x^{2} - 108 x + 324 \right) = \left( 4 x^{7} - 35 x^{6} + 105 x^{5} - 140 x^{4} + 182 x^{3} - 315 x^{2} + 189 x - 54 \right) \cdot \color{magenta}{ \left( \frac{ 4 x - 5 }{ 16 } \right) } + \left( \frac{ - 35 x^{6} + 189 x^{5} + 28 x^{4} - 1190 x^{3} + 693 x^{2} - 567 x + 4914 }{ 16 } \right)$$ $$\left( 4 x^{7} - 35 x^{6} + 105 x^{5} - 140 x^{4} + 182 x^{3} - 315 x^{2} + 189 x - 54 \right) = \left( \frac{ - 35 x^{6} + 189 x^{5} + 28 x^{4} - 1190 x^{3} + 693 x^{2} - 567 x + 4914 }{ 16 } \right) \cdot \color{magenta}{ \left( \frac{ - 320 x + 1072 }{ 175 } \right) } + \left( \frac{ 896 x^{5} - 7168 x^{4} + 17920 x^{3} - 16128 x^{2} + 24192 x - 48384 }{ 25 } \right)$$ $$\left( \frac{ - 35 x^{6} + 189 x^{5} + 28 x^{4} - 1190 x^{3} + 693 x^{2} - 567 x + 4914 }{ 16 } \right) = \left( \frac{ 896 x^{5} - 7168 x^{4} + 17920 x^{3} - 16128 x^{2} + 24192 x - 48384 }{ 25 } \right) \cdot \color{magenta}{ \left( \frac{ - 125 x - 325 }{ 2048 } \right) } + \left( 0 \right)$$ $$\frac{ 0}{1}$$ $$\frac{ 1}{0}$$ $$\color{magenta}{ \left( \frac{ 4 x - 5 }{ 16 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 4 x - 5 }{ 16 } \right) }{ \left( 1 \right) }$$ $$\color{magenta}{ \left( \frac{ - 320 x + 1072 }{ 175 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ - 80 x^{2} + 368 x - 160 }{ 175 } \right) }{ \left( \frac{ - 320 x + 1072 }{ 175 } \right) }$$ $$\color{magenta}{ \left( \frac{ - 125 x - 325 }{ 2048 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 25 x^{3} - 50 x^{2} - 25 x - 150 }{ 896 } \right) }{ \left( \frac{ 100 x^{2} - 75 x + 25 }{ 896 } \right) }$$ $$\left( x^{3} - 2 x^{2} - x - 6 \right) \left( \frac{ - 20 x + 67 }{ 392 } \right) - \left( 4 x^{2} - 3 x + 1 \right) \left( \frac{ - 5 x^{2} + 23 x - 10 }{ 392 } \right) = \left( -1 \right)$$ $$\left( x^{8} - 10 x^{7} + 35 x^{6} - 56 x^{5} + 91 x^{4} - 210 x^{3} + 189 x^{2} - 108 x + 324 \right) = \left( x^{3} - 2 x^{2} - x - 6 \right) \cdot \color{magenta}{ \left( x^{5} - 8 x^{4} + 20 x^{3} - 18 x^{2} + 27 x - 54 \right) } + \left( 0 \right)$$ $$\left( 4 x^{7} - 35 x^{6} + 105 x^{5} - 140 x^{4} + 182 x^{3} - 315 x^{2} + 189 x - 54 \right) = \left( 4 x^{2} - 3 x + 1 \right) \cdot \color{magenta}{ \left( x^{5} - 8 x^{4} + 20 x^{3} - 18 x^{2} + 27 x - 54 \right) } + \left( 0 \right)$$ $$\mbox{GCD} = \color{magenta}{ \left( x^{5} - 8 x^{4} + 20 x^{3} - 18 x^{2} + 27 x - 54 \right) }$$ $$\left( x^{8} - 10 x^{7} + 35 x^{6} - 56 x^{5} + 91 x^{4} - 210 x^{3} + 189 x^{2} - 108 x + 324 \right) \left( \frac{ - 20 x + 67 }{ 392 } \right) - \left( 4 x^{7} - 35 x^{6} + 105 x^{5} - 140 x^{4} + 182 x^{3} - 315 x^{2} + 189 x - 54 \right) \left( \frac{ - 5 x^{2} + 23 x - 10 }{ 392 } \right) = \left( - x^{5} + 8 x^{4} - 20 x^{3} + 18 x^{2} - 27 x + 54 \right)$$

===============================

Now, the degree of $g_{01}$ is 5, more than half of 8, so this is encouraging but says that some exponents are over 2. So we do another two derivatives to check for exponent 4.

$$f'' = 56x^6 - 420x^5 + 1050x^4 - 1120x^3 + 1092x^2 - 1260x + 378,$$ $$f''' = 336x^5 - 2100x^4 + 4200x^3 - 3360x^2 + 2184x - 1260,$$ and $$g_{23} = \gcd(f'',f''') = 56 x - 168 = 56 (x-3).$$

This works: take $$h = f / (x-3)^4 = x^4 + 2x^3 + 5x^2 + 4x + 4,$$ $$h' = 4x^3 + 6x^2 + 10x + 4,$$ $$g_h = \gcd(h,h') = x^2 + x + 2.$$ This time, we do get half the degree, and success with $h = (x^2 + x + 2)^2.$ Therefore $$f = (x^2 + x + 2)^2 (x-3)^4$$

On purpose, I wanted to see what happens with no rational roots and no quadratic factors. Example $$f= x^{12} - 4x^{10} + 4x^9 + 6x^8 - 12x^7 + 2x^6 + 12x^5 - 11x^4 + 6x^2 - 4x + 1,$$ $$f' = 12x^{11} - 40x^9 + 36x^8 + 48x^7 - 84x^6 + 12x^5 + 60x^4 - 44x^3 + 12x - 4,$$ $$g_{01}= \gcd(f,f') = x^9 - 3x^7 + 3x^6 + 3x^5 - 6x^4 + 2x^3 + 3x^2 - 3x + 1.$$

Once again, that is more than half the degree, so we keep going.

$$f'' = 132x^{10} - 360x^8 + 288x^7 + 336x^6 - 504x^5 + 60x^4 + 240x^3 - 132x^2 + 12,$$ $$f''' = 1320x^9 - 2880x^7 + 2016x^6 + 2016x^5 - 2520x^4 + 240x^3 + 720x^2 - 264x,$$ $$g_{23}= \gcd(f'',f''') = 132x^3 - 132x + 132 = 132 ( x^3 - x + 1) .$$ This is exactly one quarter of the original degree, and indeed $$f = ( x^3 - x + 1)^4.$$

• It must have taken a lot of effort to craft such a wonderful response. It's simple and yet it never struck me. Please have this big THANK YOU. I will accept this answer after waiting for a couple of days. Thanks again. Sep 5, 2014 at 7:57
• @Will Jagy, so in the case of the quadratic polynomial $f(x)=x^2+bx+c$. If it can be written as $(x+r)^2$, what can be concluded about the integral coefficients?Do we have $b^2- 4c=0$? I recently noted a heated debate regarding this case. What is your take on that?
– user97615
Dec 8, 2015 at 17:04
• @Ramunjndscpl , the debate at that problem concerned the difference between an equation holding for all $x,$ as compared with existence of at least one $x$ for which it holds. The person asking the question did not make the question clear, and probably does not understand the distinction Dec 8, 2015 at 17:25
• I agree. That is definitely what it looked like.
– user97615
Dec 8, 2015 at 17:36

You can devise some tests fairly easily for the quartic case. Suppose you want to know if $a_4x^4+a_3x^3+a_2x^2+a_1x+a_0$ is a square.

(1) $a_4,a_0$ must both be squares. Suppose the square roots are $a,c$.

(2) We must have $a_3/a$ and $a_1/c$ equal and even. Suppose it is $2b$.

(3) $a_2$ must be $b^2\pm2ac$.

So in your example, it passes (1) $a=c=1$. So it passes (2) and $b=3$. So it passes (3) $7=3^2-2\times1\times1$.

Then the square root is $ax^2\pm bx\pm c$. You have to check to see which signs work.

But in practice I doubt if that is particularly useful, except maybe (1).

• Thanks! I did that for the quartic case. But I am interested in the more general case. Sep 4, 2014 at 10:58
• I think it will just get messier and messier as you move to higher powers. In practice, if you wanted to check whether a polynomial factorised you would just type it into Mathematica or similar and get the answer in a few seconds. I just tried typing "factor x4+6x3+7x2−6x+1" into Wolfram Alpha and got the factorisation back instantly. Sep 4, 2014 at 11:00
• Well, laws like quadratic reciprocity can tell if a number is a perfect square (modulo something, of course) by a simple criterion. I am looking for such a criterion rather than brute force computation. Sep 4, 2014 at 11:03
• IIRC two polynomials of the same degree $n$ are equal iff the agree on $n+1$ points. Sep 4, 2014 at 12:53

Generally one can quickly test if a polynomial is an $n$'th power as follows. First do some probabilistic tests via evaluations in $\,\Bbb Z\,$ and finite fields. If it passes these tests then apply Newton iteration (Newton's method) to compute any $n$'th root.

For an overview of the complexity of this and related problems see Daniel Roche's 2011 thesis Efficient Computation with Sparse and Dense Polynomials. Here is a direct link to the pertinent chapter 6: Sparse perfect powers.