Factoring a hard polynomial

I was thinking along the same lines as TZakrevskiy but with a slight twist. Once you've become convinced that $P(n)=n^4+6n^3+11n^2+6n+1$ is the square of a quadratic (because its values for small $n$ are all squares), try computing

$$P(10)=10000+6000+1100+60+1=17161$$

and then take its square root:

$$\sqrt{17161}=131=1\cdot10^2+3\cdot10+1$$

which suggests the (correct) factorization

$$P(n)=(n^2+3n+1)^2$$

If you want to be extra sure, look at

$$\sqrt{100^4+6\cdot100^3+11\cdot100^2+6\cdot100+1}=10301$$


In general there's no easy way. But there are a lot of tricks you can use, and sometimes they work.

For this problem, the rational root theorem tells us that if there is a rational root, it must be $\pm 1$. Evidently it isn't either of these, so there are no rational roots, and therefore no factors of the form $n-q$.

So we are looking for two second-degree factors: $$n^4+6n^3+11n^2+6n+1 = (an^2+bn+c)(pn^2+qn+r)$$

But we can see from the coefficient of 1 on the $n^4$ term that $a=p=1$. From the constant term of 1 we have either $c=r=1$ or $c=r=-1$, so it's really

$$n^4+6n^3+11n^2+6n+1 = (n^2+bn\pm1)(n^2+qn\pm1).$$

Equating the coefficients of the $n^3$ terms on each side, we see that $b+q=6$.

Equating the coefficients of the $n^2$ terms on each side, we see that either $bq+2=11$ (if we take the $\pm$ signs to be $+$) or that $bq-2 = 11$ (if the $\pm$ signs are $-$).

The equations $b+q=6$ and $bq-2 = 11$ certainly have no solution in integers, since one of $b$ or $q$ must be 13. So we try the other pair of equations, $b+q=6$ and $bq+2 = 11$. Here the solution $b=q=3$ is obvious, and we are done, except to check the answer. We must do this, because we have completely ignored the coefficient of the $n$ term.


Exploit the symmetry of the palindromic polynomial to factorise as follows,

$$\begin{align*} n^4 + 6n^3 + 11n^2 + 6n + 1 &= n^2\left( n^2 + \frac{1}{n^2} + 6n + \frac{6}{n} + 11 \right)\\ &= n^2\left( (n + 1/n)^2 + 6(n + 1/n) + 9 \vphantom{\frac{1}{n^2}} \right)\\ &= n^2\left( n + 1/n + 3 \right)^2\\ &= \left( n^2 + 3n + 1 \right)^2,\\ \end{align*}$$

having essentially substituted $k = n + \frac{1}{n}$ and used $k^2 - 2 = n^2 + \frac{1}{n^2}$.