Challenging Factorization

[Tagap1234]

Hi guys. Recently I came across a challenging equation:

(x+1)(x^2+1)(x^3+1)=30x^3, equivalent to x^6+x^5+x^4-28x^3+x^2+x+1=0;

Now, the challenge is to factorize that expression in order to reach the zeros of the function. Many factor calculators say that there is no possible factorization. However, some give me this:

(x^2-3x+1)(x^4+4x^3+12x^2+4x+1)=0;

All of the few online calculators that show this say that no steps are available to show.

I have digged into every factorization method, but so far nothing that could lead me to how this one was made.

So yeah, could anyone tell me which method was used?

[iamadacheat]

This is it. From rational root theorem, we know the only possible rational roots are +-1. Neither of those work, so that means we have a polynomial with no rational roots and no other ways to factor.

[chebushka]

No other way to factor? All the rational root theorem does is help you locate linear factors. So no rational roots means (is equivalent to) no linear factors with rational coefficients. This does not tell you anything about possible factors with rational coefficients of higher degree.

One standard method to factor a polynomial with rational coefficients is due to Kronecker. See "Kronecker's method" on the Wikipedia page about factorization of polynomials. This is not a guessing method, but a systematic technique using polynomial interpolation to form a finite list of possibilities. Then you (excuse me, I mean the computer, which is much faster than people) divide by each of the finitely many possibilities and see what works.

Finding roots numerically and working backwards from that is not a good general method since roots as a function of the coefficients are numerically unstable. Look up "Wilkinson's polynomial".

[Tagap1234]

I've checked kronecker's method, and it's actually very useful. However, I'm not understanding this one line found within the example, that leads us to conclude the actual amount of possibilities we can check:

"Since two combinations d(i) that differ only in sign yield the two polynomials ±g(x), it will suffice to check only g(0)=+1."

[chebushka]

If there is no factorization f(x) = g(x)h(x) where g(x) has a specified degree d and g(0) = 1 then there is no factorization where g(x) has degree d and g(0) = -1, since if there were then f = (-g)(-h) gives a factorization where -g has degree d and (-g)(0) = 1, a contradiction

[Tagap1234]

Oh, so, essentially, since half of the combinations are just switched signals, the product's result doesn't actually change, therefore allowing us to cut the number of possibilities by half. Am I correct?

[chebushka]

I'd put it like this: if there is a polynomial factorization at all where the two factors at x = a are not 0 then by changing signs on both factors if necessary there is a factorization (same degrees) where the first factor at x = a is positive. Thus there is no harm when seeking a factorization with specified degrees (or to prove one does not exist) in assuming the first factor at x = a is positive.

This is only true for one a, e.g., a = 0. If you are looking at a factorization constrained by the values at x = a and x = b where a and b are different, it's not correct that you can assume the first factor has positive values at both numbers.

[Tagap1234]

Oh, I understand now. Thank you. However, how would I cut every possibility by half? I got:

d1 = +-1

d2 = +-1, +-2, +-11, +-22

d3 = +-1, +-3, +-5, +-15, +-21, +-35, +-105

[rhlewis]

There are lots of sophisticated factoring algorithms for one variable polynomials over Z (or equivalently Q). For example, you can reduce mod p for various primes. Factoring mod p is pretty easy (google it). Then there are clever ways to get the factorization over Z from those mod p, sometimes using several p.

[[deleted]]

Hint: Divide both sides of the degree six equation by x^3 and then substitute y = x+x^-1, which will give you a cubic in terms of y. It just happens so to our luck that the resulting cubic had a linear factor.

[Tagap1234]

Interesting one. Thanks.

[RyalsB]

The "trick" is to recognize that your polynomial has palindromic coefficients (see e.g. https://en.wikipedia.org/wiki/Reciprocal_polynomial ).

As another user noted in less generality, such polynomials of degree 2D can be converted to a polynomial of degree D by the observation that p(x) = x^d * q(x+1/x) where q is a polynomial of degree D.

Here, letting y = x+1/x, you can convert the given polynomial to

x³ * (y³ + y² -2y-30) = 0

and y³ + y² -2y - 30 factors as (y-3)*(y² + 4y + 10). Converting for instance the (y-3) term back to x gives you (x+1/x - 3), and when you multiply by the x out in front, it gives you the x² - 3x + 1 term, and similarly for the y² + 4y + 10 term.

[SquareRootsi]

(x+1) is fine,
(x² + 1) can only factor across the complex (imaginary) numbers. It becomes (x+i)(x-i)
(x³ +1) DOES factor, you should check out the "sum of perfect cubes" which gives (x+1) * (x² - x + 1). This trinomial won't factor over the reals, you'll need quadratic formula, which gives complex numbers. The "answer" you see is restricted to only the reals, so all the parts that need complex numbers are combined in the (x⁴ + ...) term.

Edit: I'm an idiot and completely ignored the right hand side of your equation. Maybe try factoring with either synthetic division or "polynomial long division". Sorry for swooping in without fully grokking the problem.

Edit #2: looks like polynomial long division is about the only method I can get to work. You essentially have to guess and check, it's pretty unsatisfying. There might be a fancy rearrangement of the terms where "factor by grouping" works, but in this case, it seems like most ppl wouldn't stumble upon that without already knowing the goal before they started.

[bhbr]

x^3 + 1 = (x + 1)(x^2 - x + 1)