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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.