wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Take One Polynomial, Get  Integer Coefficients?
        
(Message started by: K Sengupta on Jul 24^th, 2007, 7:45am)

Title: Take One Polynomial, Get Integer Coefficients?
Post by K Sengupta on Jul 24^th, 2007, 7:45am

Consider the polynomial L(m) = m^s + 5*m^s-1 + 3, where s is a positive whole number >=2.

Analytically determine whether L(m) can be expressed as the product of two non-constant polynomials having integer coefficients.

Title: Re: Take One Polynomial, Get Integer Coeffic
Post by Eigenray on Jul 24^th, 2007, 3:24pm

The first part uses complex analysis:

[hideb]Let f(x)=x^s-1(x+5). Since |L(x)-f(x)|=3 < 4 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif |x+5| = |f(x)| for |x|=1, it follows from Rouche's theorem that L has the same number of roots inside the unit disc, counting multiplicity, that f does, namely (s-1). Since the product of the roots of L is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif3, the remaining root must be outside the unit disc.[/hideb]

(Is there an elementary proof?) Now,

[hideb]if L factors, then since the constant term 3 is prime, one factor must have a constant term of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1. But this means that there is some subset of the roots of L which multiply to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pm.gif1. Since one root has norm > 1, and the rest < 1, and the product of the norms is 3, this is impossible (unless we take the empty set, which corresponds to a trivial factorization).[/hideb]

Title: Re: Take One Polynomial, Get Integer Coefficients
Post by Barukh on Jul 25^th, 2007, 12:55am

Wow! I am sure a more elementary solution exists.

I tried to apply two knows (to me) irreducibility criteria (Eisenstein and enough-prime-numbers evaluation). Both got me to nowhere... ::)

Title: Re: Take One Polynomial, Get Integer Coefficients
Post by K Sengupta on Jul 27^th, 2007, 8:40am

I submit herewith a proposed solution to the given problem.

Still hiding it, because I am not entirely sure about the veracity of the undernoted methodology.

[hideb]Let L(m)
= (m^p + c_p-1m^p-1+.....+c₁m +/- 3) (m^q + d_q-1m^p-1+.....+d₁m +/- 1)

We will show that all c's are divisible by 3 and use that fact to establich a contradiction.

At the outset, both p and q must be >=2. If possible, let p=1. Then, it follows that +/-3 is a root. Accordingly, if s is even, we would have:

0 = 3^s(+/-3 +5) + 3 which is false since +/- 3 + 5 = 8 or -2.

Similarly, if s is odd, we would have:
0 = 3^s-1(+/-3 +5) +3, which is false since +/-3 + 5 = 8 or 2.

If q=1, then +/-1 is a root and we would reach a contradiction in a similar manner.

Hence, p<= s-2 and accordingly, the coefficients of m, m², ......., m^p are all zero.

So, we must have c₁ +/- 3d₁ = 0, and accordingly c₁ is divisible by 3.

We will prove the remaining part by way of induction.

Let us assume that c₁, ...., c_v are all divisible by 3. We consider the coefficient of m^v+1.
If q-1 > = v+1, then :
c_v+1 corresponds to a linear combination of c₁, ....., c_v-1, c_v +/- 3d_v+1

If p-1< v+1, then c_v+1 corresponds to a linear combination of some or all of c₁, c₂, ......, c_v.

In both the above cases, c_v+1 is divisible by 3.
Accordingly, considering the coefficients of m, m², ....., m^p-1, we observe that all the c's are multiples of 3.

Now, let us consider the coefficient of m^s, which is also zero. It is a sum of the terms which are multiples of 3 added to +/-1, and so, the said coefficient cannot be zero.

This leads to a contradiction.

Consequently, the factorization is not possible.[/hideb]