Math Is Fun Forum

beni

Guest

polynomial

How to break up the polynomial
x^10+x^5+1
Over the rational numbers

ZHero

Real Member

Registered: 2008-06-08

Posts: 1,889

Re: polynomial

it factorizes to
(x^2+x+1) (x^8-x^7+x^5-x^4+x^3-x+1)

I don't know what it means to break it over the rationals.

---

If two or more thoughts intersect, there has to be a point!

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Hi beni;

If I understand you you want an irreducible factorization over Q. If you you can factor it over Q you can factor it over Z.

A graph of the function shows no real roots so I believe the factorization is done in the form

1) quadratic times 8 th order poly
2) 4 th order times by a 6th order

Mathematica gives:

Pari, Sage, Maxima, Mupad, Maple, Derive, will all do it for you, or you can take it to wolfram alpha, use the command.

Factor[x^10+x^5+1] this will factor over the integers.

To do it by hand is nearly impossible unless there is some specific trick. The Berlekamp-Zassenhaus algorithm is used but it is strictly for computers. The only clear non computer method I know requires the solution of an 8x8 non linear simultaneous set of equations. But solving this by hand is not possible either.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

soroban

Member

Registered: 2007-03-09

Posts: 452

Re: polynomial

. .

. .

.[1]

Then [1] becomes:

. .

. .

. . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

. .

.

beni

Guest

Re: polynomial

How do I prove that you can not solve the polynomial
x^8-x^7+x^5-x^4+x^3 -x+1

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Hi beni;

I think you are getting into Abstract Algebra. There is a theorem by Eisenstein that covers irreducibility over Q. Incidentally as I have stated there is a theorem that when a polynomial is reducible over Q it is also reducible over Z for the same degree.

Look here:

http://www.math.niu.edu/~beachy/aaol/po … .html#real

Then here to see what you are up against.

http://en.wikipedia.org/wiki/Factorizat … olynomials

Kroneckers method is used to prove a large poly like yours is irreducible in Z.Mostly they again use computer methods like LLL ( lattice reduction ) and Berlenkamp. This implies that the problem might be solved using a PSLQ.

I must be missing something but I can find nothing easier than Kroneckers method , half way down the page.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

beni

Guest

Re: polynomial

Can I prove it without  "Eisenstein"?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Hi beni;

If Eisensteins method applied here I would gladly use it. But I don't know how to apply it to your problem. Did you check the second page. Kronecker has a method that should work.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

BENI

Guest

Re: polynomial

Sorry but I want to understand:
I can factor     x^10+x^5+1   over Z
but I can't factor it Q  ??

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Hi;

If you can factor it over Q you can factor it over Z and vice versa. Provided we are dealing with a monic poly with integer coefficients. May hold for more but this is what we are discussing.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Hi;

Can I prove it without  "Eisenstein"?

This is a method that I found and like!

Just using those 9 numbers and getting 8 primes and a unit in column 2 is proof that f(x) is irreducible over Z and therefore irreducible over Q.

Although there are tricks that strengthen Eisensteins criterion, this method is stronger and much easier for computation.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

jk22

Member

Registered: 2010-06-14

Posts: 33

Re: polynomial

Hi, nice to meet you.

I looked at the Kronecker's method, but don't understand how it goes

for example : f(x)=x^8-x^7+x^5-x^4+x^3-x+1

I have f(0)=1, f(2)=151, f(-2)=331

if I look for a polynomial g(x)=ax^2+bx+c, fitted with the values above, got :
g(0)=1=>c=1
and a=60, b=-45.

and the following of it would be : if the coefficient are integer, and the discriminant <0 it should be dividable ?? (which here is not the case, since delta>0)

Last edited by jk22 (2010-07-25 23:47:57)

yehoram

Member

Registered: 2010-06-24

Posts: 8

Re: polynomial

Hi guys !

From Israel - Jerusalem !

How about this :

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Hi yehoram;

Welcome to the forum!

A polynomial needs to have non negative integer or whole number exponents.

Is not a polynomial. When you are factoring a polynomial you are trying to have polynomial factors.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

yehoram

Member

Registered: 2010-06-24

Posts: 8

Re: polynomial

Hi yehoram;

Welcome to the forum!

A polynomial needs to have non negative integer or whole number exponents.

Is not a polynomial. When you are factoring a polynomial you are trying to have polynomial factors.

This 

is

also negative ?????

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Hi yehoram;

I am not following you, that is a factorization of x^10 + x^5 + 1. What do you require?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Just using those 9 numbers and getting 8 primes and a unit in column 2 is proof that f(x) is irreducible over Z and therefore irreducible over Q.

The above quote for post # 11 is a little misleading. For the method in post 11 to work all the time at least in theory, requires that a certain unproved assertion by Bouniakowsky in 1857 is true. Practically it also suffers from degenerate cases such as ( x^12 + 488669 ) which does not produce a prime until,

And then the next prime:

And then the next prime:

So there are only 3 for x that are <= 1 000 000.

Since each of these primes is over 70 digits and I need 10 more we can see that this method is no longer practical for this problem.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

jk22

Member

Registered: 2010-06-14

Posts: 33

Re: polynomial

I have a similar problem but over real numbers : P(x) = 2x^4 + x^3 - x^2 - x

i can get x(2x^3 + x^2 - x - 1), but then i cannot find the next real root with 3rd degree formulas

and cannot find another method. thanks.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Hi jk22;

There is an exact solution for the general cubic.
It is very tedious. Usually you use numerical methods to get the next real root.

The problem of getting the roots of an equation of anything other than a quadratic or linear equation is difficult. You need a good understanding of the theory of equations and Numerical analysis.
A computer is mandatory.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

mrtumtum

Member

Registered: 2010-12-30

Posts: 5

Re: polynomial

factor 483016364881
483016364881: 181 22111 120691

7790284054561
7790284054561: 31 22381 11228251

23304888110401
23304888110401: 50551 461017351

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Hi mrtumtum;

Welcome to the forum.

Those factorizations are all correct. But why are you doing them?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

mrtumtum

Member

Registered: 2010-12-30

Posts: 5

Re: polynomial

\left(
\begin{array}{cc}
f(-1) & 1 \\
f(2) & 151 \\
f(5)& 315121 \\
f(11) & 195019441 \\
f(17) & 6566760001 \\
f(23) & 74912328481 \\
f(29) & 483016364881 \\
f(41) & 7790284054561 \\
f(47) & 23304888110401
\end{array}
\right)

Go Back

This is a method that I found and like!

Just using those 9 numbers and getting 8 primes and a unit in column 2 is proof that f(x) is irreducible over Z and therefore irreducible over Q.

Although there are tricks that strengthen Eisensteins criterion, this method is stronger and much easier for computation.

mrtumtum

Member

Registered: 2010-12-30

Posts: 5

Re: polynomial

I was intrigued by your answer and wanted to check the answer
thansk
mrtumtum

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: polynomial

Hi mrtumtum;

That is very good for spotting that! Thanks for alerting me to the error. I am repairing it, thanks again!

Post #11 should look like this.

The fact that all the arguments of f differ by more than 2 and the second column contains 8 primes and a unit establishes the irreducibility of that polynomial.

For this method to always work, Bouniakowsky's 1857 conjecture which has no known counterexamples would have to be true. The conjecture states that every irreducible polynomial generates an infinite number of primes.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.