10
$\begingroup$

I was this problem: $$\int\frac{dx}{\sqrt{x^4+2x^3+3x^2+2x+1}}$$

I solved this question because I just knew that $(1+x+x^2)^2=x^4+2x^3+3x^2+2x+1$ but this made me wonder is there is a way to know if the $n-$th root of a certain polynomial is a polynomial? Given a polynomial how to determine $n$ where the $n-th$ root of this polynomial is a polynomial and how to determine the $n-$th root of this polynomial?

There is Taylor theorem or the extended binomial theorem that can find $(P(x))^{1/n}$ but this is not what I am looking for because

  1. It only deals with two terms and the more terms that a polynomial have the more one needs to use the binomial theorem on each term which gets very ugly.
  2. It gives an infinite series which doesn't tell if each the $n-$th root is a polynomial or not
  3. Even if one can make simplifications on the infinite series to conclude it is a polynomial finding suitable $n$ would need one to check all the cases from $2-m$ where $m$ is the degree of polynomial, which is not very effective.
$\endgroup$
6
  • 1
    $\begingroup$ I would plug in some small numbers of $x$. In your example, $P(x)= x^4+2x^3+3x^2+2x+1$ we have $P(-2)= 9, P(-1)= 1, P(0)=1, P(1)=9$ so I suspect maybe it is a square of other polynomial. $\endgroup$
    – Etemon
    Commented May 25 at 7:45
  • $\begingroup$ There is a long-division-like algorithm for calcluating the square root of a number. This can be converted into an algorithm for calculating the square root of a polynomial, in a similar way that long division itself has been converted into an algorithm for polynomial division. $\endgroup$ Commented May 25 at 8:03
  • 1
    $\begingroup$ For perfect squares see How do we check if a polynomial is a perfect square? Some algorithms for perfect powers are reviewed in Giesbrecht-Roche, Detecting lacunary perfect powers and computing their roots. $\endgroup$
    – Conifold
    Commented May 25 at 8:32
  • 1
    $\begingroup$ The discriminant is zero if the polynomial has a repeated root; so if it is nonzero then the polynomial won't be a perfect power. $\endgroup$
    – Empy2
    Commented May 25 at 8:38
  • $\begingroup$ There is a multinomial theorem to address your point 1. I'm not sure it really helps, though. $\endgroup$ Commented May 25 at 8:44

3 Answers 3

23
$\begingroup$

If $f(x)$ is a power of something, then $f(x)$ and $f'(x)$ have that something as a common divisor. In your case, $$ \gcd(x^4 + 2 x^3 + 3 x^2 + 2x + 1, 4x^3+6x^2+6x+2) \\ = x^2 + x + 1 \text{.} $$

More generally, $f(x) = (p(x))^n$ implies $f'(x) = n(p(x))^{n-1}p'(x)$, so $(p(x))^{n-1}$ divides both $f$ and $f'$, therefore divides their greatest common divisor.

Note that this also applies to powers of non-polynomials. $\frac{\mathrm{d}}{\mathrm{d}x} \sin^4(x) = 4 \sin^3(x)\cos(x)$ and $\sin(x)$ divides both of these. It can be tricky to define gcds for non-polynomials. Your experience with trigonometric identities should suggest that the "immediately visible" common factors may appear, vary, and disappear as we manipulate the expressions.

If everything in sight is a polynomial, then the leading term of $f$ must be an $n^{\text{th}}$ power and so must the constant coefficient. For your example $f$, the leading term requires $n \in \{1,2,4\}$ and the constant term doesn't restrict $n$. The fact that the gcd in your example is not a cube and is not a constant tells us $n = 2$. Though the constant coefficient doesn't restrict $n$, if $f$ has a polynomial $n^{\text{th}}$ root, the constant tells us that root's constant coefficient is an $n^{\text{th}}$ root of $1$.

Let's see if we can cobble this into an algorithm. (Not optimal. Not efficient. Probably not even particularly good. But at least a procedure that works.) We will discuss starting with a polynomial having, integer ($\Bbb{Z}$), rational ($\Bbb{Q}$), real ($\Bbb{R}$) or complex ($\Bbb{C}$) coefficients and target $n^{\text{th}}$ roots from the same list. The indeterminate will be $x$ and the collections of polynomials will be denoted $\Bbb{Z}[x]$, $\Bbb{Q}[x]$, $\Bbb{R}[x]$, and $\Bbb{C}[x]$, respectively. We assume we have a polynomial $f(x)$ from one of these collections and we search for an $n \in \Bbb{Z}$ with $n \geq 1$ and a polynomial $p(x)$ from one of the collections such that $f(x) = (p(x))^n$.

For this discussion:

  • The phrase "$f(x)$ is a first power" means that $n$ can only be $1$ and $p(x)$ must be $f(x)$.
  • $A$ stands for "either $\Bbb{Z}$ and $\Bbb{Q}$", since almost always these are treated together. Similarly, $A[x]$ is used for the collection of polynomials with integer or rational coefficients. (By Gauss's lemma, these are really equivalent factorizations possibly wearing two different hats.)
  • $B[x]$ stands for "either $\Bbb{R}$ or $\Bbb{C}$" since almost always these are treated together. Similarly, $B[x]$ is used for this collection of polynomials.
  • Whenever we write a polynomial as $\text{[coefficient]}x^{\text{[power]}} + \cdots$, the elided terms have lower degree than the power shown. That is, we have written the leading term and suppressed the non-leading terms.

Let's start by maybe making $f$ a little simpler. Then continue by inspecting the leading and trailing coefficients of $f$. We finish off by applying calculus a few times.

  1. If the leading term of $f$ is negative, factor a $-1$ from $f$ and proceed below with $-f$. If we eventually find $-f = p^n$ and $n$ is odd then $f = (-p)^n$; otherwise, $f$ is a first power.

  2. Inspect the leading term. If searching for a $p(x) \in A[x]$, factor the coefficient. $n$ must be a divisor of each power of a prime and the power of $x$. If searching for $p(x) \in B[x]$, $n$ must be a divisor of the power of $x$. (The coefficient does not constrain because in $B$, everything has whatever root(s) we might desire.)

    Examples:

    • $f(x) = 32x^{10} + \cdots$: The leading term is $2^5 x^{10}$. If we want $p(x) \in A[x]$, then $n \in \{1,5\} \cap \{1,2,5,10\} = \{1,5\}$, so $f$ is a first or fifth power. If we want $p(x) \in B[x]$, then $n \in \{1,2,5,10\}$.
    • $f(x) = \frac{32}{81}x^{10} + \cdots$: The leading term is $\frac{2^5}{3^4} x^{10}$. If we want $p(x) \in A[x]$, $n \in \{1,5\} \cap \{1, 2, 4\} \cap \{1,2,5,10\} = \{1\}$, so $f$ is a first power. If we want $p(x) \in B[x]$, $n \in \{1,2,5,10\}$.
    • $f(x) = \sqrt{2} x^{11} + \cdots$: The leading coefficient is not in $A$, so $p(x) \not \in A[x]$. So we search for $p(x) \in B[x]$ and have $n \in \{1,11\}$.
  3. If we seek $p(x) \in A[x]$, then also factor the constant coefficient, with sign. For instance, if the constant coefficient is $1$, it has infinitely many factorizations: $1^k$ and $(-1)^{2k}$ for any $k \geq 0$ in $\Bbb{Z}$, leading to $n \geq 1$ in $\Bbb{Z}$. We always insert $n = 1$ by hand. Instead, if we seek $p(x) \in B[x]$, the constant coefficient does not constrain $n$; we have $n \in \Bbb{Z}$, $n \geq 1$.

    Examples, where we take $k$ to range over positive integers and we seek $p(x) \in A[x]$:

    • The constant coefficient is $4 = (-1)^{2k} 2^2$. Then $n \in \left(2\Bbb{Z} \cap \{1,2\}\right) \cup\{1\} = \{1,2\}$.
    • The constant coefficient is $-4 = (-1)^{2k+1} 2^2$. Then $n \in \left( (2\Bbb{Z} + 1) \cap \{1,2\} \right) \cup \{1\} = \{1\}$.
  4. Take the intersection of the candidate $n$s from the leading coefficient and the candidate $n$s from the constant coefficient (if the constant actually leads to a constraint). The set of surviving candidates form a lattice (of divisors of the largest candidate, ordered by "divides").

    (The candidates from step 1 form a sublattice of the division lattice of the nonnegative integers. The candidates from step 2 do also. The intersection of two such lattices is another such lattice, so the set of survivors is such a sublattice.)

    Let $N$ be the number of surviving candidates, sort the surviving candidates, and label them in increasing order $$ n_1 < n_2 < \cdots < n_{N} \text{.} $$

    Example, where $60$ is the largest candidate:

    Lattice of divisors of 60, ordered by "divides". image source

    $N = 12$ and $n_1 = 1$, $n_2 = 2$, $\dots$, $n_7 = 10$, $\dots$, $n_{N} = 60$.

  5. Suppose $f = p^n$ with $n > 1$ and degree of $p$ greater than one. Let's see what we get for the leading term when we differentiate. Let $p(x) = a x^d + \cdots$. Then \begin{align*} f(x) &= (p(x))^{n} \\ &= (a x^d + \cdots)^{n} \\ &= a^n x^{dn} + \cdots \text{ and } \\ f'(x) &= n (p(x))^{n-1} p'(x) \\ &= n (a x^d + \cdots)^{n-1} (ad x^{d-1} + \cdots) \\ &= n a^n x^{dn-1} + \cdots \text{.} \end{align*} So the leading term of $f'$ divided by the leading term of $f$ is $n/x$. If $f$ is not a power, then the leading term of $f'$ divided by the leading term of $f$ is still some constant over $x$, so again, this is a candidate $n$.

    Either this candidate is on the list from step 3 or it is not. If not, $f$ is a first power and we are done. We've narrowed the list of possible powers to one.

  6. Continuing the calculus from step 4 \begin{align*} f''(x) &= n(n-1)(p(x))^{n-2}p'(x)^2 + n (p(x))^{n-1}p''(x) \\ &= n(n-1)(ax^d + \cdots)^{n-2}(adx^{d-1}+\cdots)^2 + n(ax^d+\cdots)^{n-1}(ad(d-1)x^{d-2}+\cdots) \\ &= a^n dn(dn -1)x^{dn-2} + \cdots \end{align*} So the leading term of $f''$ divided by the leading term of $f'$ is \begin{align*} \frac{a^n dn(dn -1)x^{dn-2}}{n a^n x^{dn-1}} &= \frac{d(dn -1)}{x} \end{align*} This is, it's the degree of $p$ times one less than the degree of $f$ divided by $x$. Since we start with knowledge of the degree of $f$, we can divide the number in the numerator by one less than this degree and get $d$. Since $d$ has to be a positive integer, if the division has nonzero remainder, we discover $f$ is a first power and stop.

    We can also check that the degree of $d$ times the one surviving candidate $n$ gives the degree of $f$. (I think this second check might be redundant given the prior work, but haven't thought about it hard enough to be sure.)

  7. At this point, we have one candidate $n$ for $f = p^n$. Compute the polynomial GCD $$ p(x) = \mathrm{gcd}\left( \left( \frac{\mathrm{d}}{\mathrm{d}x}\right)^{n-1} f(x), f(x) \right) \text{.} $$ If $p$ is a constant polynomial, $f$ is a first power. Otherwise, $f = p^n$. (And remember to apply the conclusion of step 0 if you factored a $-1$ out of $f$ in that step.)

    (One might say that computing the $(n-1)^{\text{th}}$ derivative is a lot of work, but it can be done in one step if one has a table of falling factorials, since $(\mathrm{d}/\mathrm{d}x)^{n-1} ax^b = a(b)_{n-1}x^{b-(n-1)}$ if $b \geq n$ and zero otherwise.)

$\endgroup$
5
  • 10
    $\begingroup$ This will detect powers, but it's worth noting that it will also detect some non-powers, so once we find the GCD, we should investigate further to see if it actually has the right form to tell us that $f(x)$ is a perfect power. For example, if we have $f(x)=x^4+2x^3-2x-1$, then $f'(x)=4x^3+6x^2-2$, then $\gcd(f(x),f'(x)) = x^2+2x+1=(x+1)^2$, but $f(x)$ is not a power of $(x+1)^2$; rather, it is $(x+1)^3(x-1)$. $\endgroup$ Commented May 25 at 20:11
  • 1
    $\begingroup$ @MishaLavrov : I don't see that this differs from what I have written. Although maybe you point out something that wasn't sufficiently explicit? $\endgroup$ Commented May 26 at 5:10
  • $\begingroup$ Yes - everything you wrote was correct and I'm not disagreeing with it, I just think this additional detail is worth mentioning. $\endgroup$ Commented May 26 at 15:39
  • $\begingroup$ What it detects is repeated facrors of any sort. If there are nonrepeated factors or factors are repeated different numbers of times, you generally don't have a pure power. $\endgroup$ Commented May 27 at 10:42
  • $\begingroup$ @MishaLavrov : Explicitness should be markedly increased. (And I foresee new comments about polishing the described procedure.) $\endgroup$ Commented Jun 2 at 15:06
7
$\begingroup$

No there isn't a general way as far as I know. But there is one trick that I would like to tell you.


The polynomial you have $x^4+2x^3+3x^2+2x+1$
is a symmetric polynomial so there is a possibility that it can be factorised. Let's check. You can use this trick for other symmetric polynomials.

Rewrite the whole expression as $\displaystyle x^2\left(x^2+2x+3+\frac{2}{x}+\frac{1}{x^2}\right)$

Now you just have to club the appropriate terms. Rewrite this as

$\displaystyle x^2\left(\left(x+\frac{1}{x}\right)^2+2\left(x+\frac{1}{x}\right)+1\right)$

This is nothing but $\displaystyle x^2\left(x+\frac{1}{x}+1\right)^2$

which certainly equals to $$(1+x+x^2)^2$$

$\endgroup$
4
  • 1
    $\begingroup$ You seem to be implying that all symmetric polynomials are factorizable, but that's definitely not true: consider $x^2+bx+1$ for any $|b|<2$. $\endgroup$ Commented May 25 at 8:00
  • $\begingroup$ Let me change that real quick $\endgroup$
    – Zootopia
    Commented May 25 at 8:01
  • $\begingroup$ You mean, "let me change that non-real quick." $\endgroup$ Commented May 25 at 18:30
  • $\begingroup$ @PerAlexandersson It got changed, look at the edit history, now he says that "there is a possibility" $\endgroup$ Commented May 27 at 11:06
1
$\begingroup$

Suppose $x^4+2x^3+3x^2+2x+1=(ax^2+bx+c)^2$. Then expanding the right side and equating like-power terms renders

$a^2=1$

$2ab=2$

$2ac+b^2=3$

$2bc=2$

$c^2=1$

The first equation has two roots $a\in\{1,-1\}$ and wlog we may take either one. Selecting $a=1$ then leads to the second equation giving $b=1$ and the third equation giving $c=1$. If these results satisfy both remaining equations then you may render

$x^4+2x^3+3x^2+2x+1=(x^2+x+1)^2.$

A "real-life" example comes from Benjamin and Snyder's neusis construction of the regular hendecagon[1], which would be impossible with Euclidean tools plus an angle trisector alone. Their method ultimately depends on factoring a sextic polynomial

$u^6+4u^5+8u^4+12u^3+12u^2+8u+4,$

in which the degree is even, the constant term is a square and the coefficients add up to another square. To prove that this in fact is $(ax^3+bx^2+cx+d)^2$, we expand and match:

$a^2=1\implies a=1$ (wlog)

$2ab=4\implies b=2$

$2ac+b^2=8\implies c=2$

$2(ad+bc)=12\implies d=2$

$2cb+c^2=12$

$2cd=8$

$d^2=4$

where the values of $a,b,c,d$ from the first four equations have to match the last three — which actually works, and thus as the authors put it, "a miracle occurs".

Reference

  1. Benjamin, Elliot; Snyder, C. Mathematical Proceedings of the Cambridge Philosophical Society 156.3 (May 2014): 409-424.; https://dx.doi.org/10.1017/S0305004113000753
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .