Factoring x^4 + x^2 + 1
AJ Davidson
+ 1 into (x^2 + x + 1)(x^2 - x + 1). I fed the express into Mathematica and
it was about to factorize it. I deduced that if the mathematics package is
able to factorize, there must be a certain algorithm or laws to it.
Is there any way to factorize x^4 + x^2 + 1 by applying rules?
Thanks in advance!
A.J.
Jon Haugsand
I don't know about mathematica, but why not solve the quadric in
"ordinary" fashion ending with (x-a)(x-b)(x-c)(x-d) and then try each
factor against each other until you find a pair that eliminates the
imaginary parts?
--
Jon Haugsand
Dept. of Informatics, Univ. of Oslo, Norway, mailto:jon...@ifi.uio.no
http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 95 21 52
Victor Khomenko
Rule 1: try Mathematica or Maple.
Rule 2: if you for some reason don't access to Mathematica, Maple, or other
similar system, compute all the roots of the polynomial (in your case it is
easy to do by making a substitution y=x^2 and solving the equation y^2+y+1,
and then x^2=y1, x^2=y2, where y1 and y2 are the roots of y^2+y+1). Note
that the roots are complex numbers in this case, denote them x1,x2,x3,x4.
Then x^4+x^2+1=(x-x1)(x-x2)(x-x3)(x-x4). The problem with this factorisation
is that it's over complex numbers. To make a factorisation over reals, find
complementary roots (e.g. if x1=a+b*i and x2=a-b*i then they are
complementary). There should be two pairs of complementary roots, say x1 and
x2, and x2 and x3. Partially open the parentheses as follows
((x-x1)(x-x2))*((x-x3)(x-x4)), which gives you (x^2 + x + 1)(x^2 - x + 1).
All the best,
Victor.
Ignacio Larrosa Cañestro
news:10448717...@drone5.qsi.net.nz...
x^4 + x^2 + 1 = (x^2 + ax + b)(x^2 + cx + d)
= x^4 + (a + c)x^3 + (b + d + ac)x^2 + (a + c)x + bd
===>
a + c = 0 ===> c = -a
b + d + ac = 1 ===> b + d - a^2 = 1
ad + bc = 0 ===> a(d - b) = 0 ==> a = c = 0 OR b = d
bd = 1 ===> d = 1/b
Then
a = c = 0 ==>
b + 1/b = 1 ===> b^2 - b + 1 = 0 ==>
b = (1 +/- sqrt(1 - 4))/2 = 1/2 +/- i*sqrt(3)/2
d = 1 - b = 1/2 -/+ i*sqrt(3)/2
It isn't that we was looking for ..
Then, a =/= 0 ===> c = -a, b = d = +/- 1
a^2 = b + d - 1 = 1 or - 3
Let b = d = 1 to avoid newly complex values,
a = +/-1 ==> c -/+ 1
and
x^4 + x^2 + 1 = (x^2 + x + 1)(x^2 - x + 1)
--
Best regards from a 'PPrestigeada' Galicia, and
NO BLOOD FOR OIL!
Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosaQUIT...@mundo-r.com
Count Dracula
> Is there any way to factorize x^4 + x^2 + 1 by applying rules?
Yes, there is. Let y = x^2 and consider
x^4 + x^2 + 1 = y^2 + y + 1 = y^2 + 2 y + 1 - y
= (y + 1)^2 - y
This step used the rule 'completing the square'.
Now we have a 'difference of two squares', so
(x^2 + 1)^2 - x^2 = (x^2 + 1 + x)(x^2 + 1 - x)
= (x^2 + x + 1)(x^2 - x + 1)
--
_________________________________________________________________________
Levent Kitis lk3no...@esinet.net
_________________________________________________________________________
Helmut Richter
> Is there any way to factorize x^4 + x^2 + 1 by applying rules?
This depends a lot on what you accept as a "rule".
Every polynomial with integer coefficients can be factored into
irreducible factors by an algorithm, that is, a finite set of
instructions to follow, which terminate after finitely many steps.
So it is not astonishing that computer algebra programs can do this
task.
General algoritms for this purpose are, however, quite complex, both
regarding their description and actually performing them. Therefore
one might not be inclined to call them either "rule" or "formula".
This specific polynomial can more easily be factored by hand, as
multiple other contributors have shown.
Helmut Richter
Jon Haugsand
> Every polynomial with integer coefficients can be factored into
> irreducible factors by an algorithm, that is, a finite set of
> instructions to follow, which terminate after finitely many steps.
Really? This must be the long sought after reason why Niels Henrik
Abel never got any acknowledge in his lifetime.
William Elliot
Er yes, but who'd expect the rule is complete the square?
x^4 + x^2 + 1 = x^4 + 2x^2 + 1 - x^2 = (x^2+1)^2 - x^2
= (x^2 - x + 1)(x^2 + x + 1)
by difference of squares rule.
Helmut Richter
> * Helmut Richter
>> Every polynomial with integer coefficients can be factored into
>> irreducible factors by an algorithm, that is, a finite set of
>> instructions to follow, which terminate after finitely many steps.
>
> Really? This must be the long sought after reason why Niels Henrik
> Abel never got any acknowledge in his lifetime.
With "factored into irreducible factors" I meant factors that are
irreducible integer polynomials, which is sufficient for the OP's
question.
I am not aware that Abel was working on *this* problem. As far as I
know, he started where the algorithm I was alluding to ends: with an
irreducible polynomial.
The algorithm can, for instance, be found in Cohen's book.
Helmut Richter
diego
> I fed the express into Mathematica and
> it was about to factorize it. I deduced that if the mathematics package is
> able to factorize, there must be a certain algorithm or laws to it.
Can you try for me factorize with mathematica the polynom :
x^7+x^5+x^4+10
Leonard Blackburn
= x^4 + 2x^2 + 1 - x^2
= (x^2 + 1)^2 - x^2
= (x^2 + 1 - x)(x^2 + 1 + x).
Maybe this isn't what you're looking for, but these steps taken
could be part of an algorithm. You could check whether a given
polynomial is of a certain type where adding and subtracting a
square would be useful. Then, you could apply a difference-of-
squares formula. This is most likely not how Mathematica would
do it. But humans are smarter than Mathematica, and can sometimes
come up with a creative solution.
Phil Carmody
Aurefeullian factorisation.
Phil
The Last Danish Pastry
news:pan.2003.02.10....@yahoo.co.uk...
"Aurifeuillian", after Léon François Antoine Aurifeuille.
Ronald Bruck
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <b2bhsj$1ar3sc$1...@ID-11651.news.dfncis.de>, The Last Danish
Pastry <TheLastDa...@yahoo.com> wrote:
> Léon François Antoine Aurifeuille
Interesting. I Googled this term, and found only one hit, whose home
page is
<http://home.att.net/~numericana/>
(for the full name; there are lots of hits for the last name only).
Browsing through some of the arcana at this site, I found a thorough
discussion of how many cm are in an inch (2.54, of course) and whether
this is exact--I happened to know that it IS exact, since 1959, by
definition, but the site has much more detail than that.
Worthwhile. Apparently it's based on a forthcoming book by the author.
--Ron Bruck
Robert Israel
>Can you try for me factorize with mathematica the polynom :
>x^7+x^5+x^4+10
This is irreducible over the rationals. Moreover, it has Galois group
S_7, and any factorization must involve coefficients that can't be
expressed using radicals. (I used Maple, not Mathematica)
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
Peter L. Montgomery
After you understand what is happening here, try to factor
x^4 + 4 and x^6 + 27. Note, by the way, that
these (and x^4 + x^2 + 1) are always positive for real x,
so they have no real roots, and all factors must have even degree.
--
The YY/MM/DD date was 03/02/01.
As the countdown ended, zero astronauts survived.
Peter-Lawren...@cwi.nl Home: San Rafael, California
Microsoft Research and CWI
Zubin Chandran
If you do not know the theory of cyclotomic polynomials etc, a general
method to work on problems like this is using complex numbers, which
would be covered in an introductory complex analysis course.
We know that x^4 + x^2 + 1 = 0 has four roots, and using basic methods
we can find the roots and factorize as:
x + 1/2 + i Sqrt(3) / 2
x + 1/2 - i Sqrt(3) / 2
x - 1/2 + i Sqrt(3) / 2
x - 1/2 - i Sqrt(3) / 2
At which point you multiply the pairs to get the answer,
(x + 1/2 + i Sqrt(3) / 2)(x + 1/2 - i Sqrt(3) / 2) = x^2 + x + 1
(x - 1/2 + i Sqrt(3) / 2)(x - 1/2 - i Sqrt(3) / 2) = x^2 - x + 1
When I took undergrad complex analysis, I thought it was the coolest
thing since sliced bread when we factored x^4 + 1 this way..
Zubin Chandran
Phil Carmody
> "Phil Carmody" <thefatphi...@yahoo.co.uk> wrote in message
>> > Is there any way to factorize x^4 + x^2 + 1 by applying rules?
>>
>> Aurefeullian factorisation.
>
> "Aurifeuillian", after Léon François Antoine Aurifeuille.
My dear fellow, there are in fact only so many vowels the hand can
type in the course of an evening.
I think I'm right in saying that, aren't I, Court Composer?
Funnily enough, it's not even Aurefeuillian, it's a standard Cyclotomic
factorisation Phi_odd(n^even).
How more wrong could I have been? Perhaps I should have posted my
previous response to soc.culture.indian or something like that to
complete my error!
Basically (like Aurefeuillian factorisations), it's a case of completing
the square. However, with Aurefeuille, you have to borrow a square root in
order to get the thing to work.
Phil
Bill Dubuque
>
> x^4 + x^2 + 1 = (x^2 + x + 1) (x^2 - x + 1), why?
It's the special case n = 3 of general cyclotomic factorizations [1],[2]:
(x^2)^n - 1 = (x^n)^2 - 1, now factor, and divide by x^2-1
x^2n - 1 x^n - 1 x^n + 1
-------- = ------- -------
x^2 - 1 x - 1 x + 1
i.e. p(x^2) = p(x) p(-x) if n is odd.
More exotic cyclotomic factorizations also arise via difference of squares
due to Aurifeuille, Gauss, Le Lasseur, Lucas; e.g. below, and [3],[4],[5]
x^4 + 4 = (x^4 + 4x^2 + 4) - (2x)^2 = (x^2 + 2x + 2) (x^2 - 2x + 2)
x^6 + 27
-------- = (x^2 + 3x + 3) (x^2 - 3x + 3)
x^2 + 3
x^10 - 5^5
---------- = (x^4 + 5x^3 + 15x^2 + 25x + 25)(x^4 - 5x^3 + 15x^2 - 25x + 25)
x^2 - 5
x^12 + 6^6
---------- = (x^4 + 6x^3 + 18x^2 + 36x + 36)(x^4 - 6x^3 + 18x^2 - 36x + 36)
x^4 + 36
x^14 + 7^7
---------- = (x^6 + 7x^5 + 21x^4 + 49x^3 + 147x^2 + 343x + 343) *
x^2 + 7 (x^6 - 7x^5 + 21x^4 - 49x^3 + 147x^2 - 343x + 343)
Keep in mind that any product may be expressed as a difference of squares
a b = ((a + b)/2)^2 - ((a - b)/2)^2
-Bill Dubuque
[1] http://mathworld.wolfram.com/CyclotomicPolynomial.html
[2] http://groups.google.com/groups?selm=y8zy986pvlh.fsf%40nestle.ai.mit.edu
[3] http://mathworld.wolfram.com/AurifeuilleanFactorization.html
[4] R. P. Brent, Computing Aurifeuillian factors
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub127.html
[5] R. P. Brent, On computing factors of cyclotomic polynomials
http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pub/pub135.html
Oscar Lanzi III
parentheses are perfect squares.
Compare this with the factorization of x^4 + 4 into (x^2 - 2x + 2)(x^2 +
2x + 2), where again there is a "hidden" difference of squares because
you have a quartic expression rather than a quadratic one.
--OL
Earle Jones
"AJ Davidson" <ajdav...@subdimension.com> wrote:
*
Let a = x^2
You new polynomial is
a^2 + a + 1
Using whatever quadratic "rule" you like, factor this.
then subtitute the x^2 back into the expressions for a.
earle
*
The Last Danish Pastry
news:earle.jones-17B5...@netnews.attbi.com...
And does this give the factorisation mentioned by the original poster?
--
Clive Tooth
http://www.clivetooth.dk