All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Does It Continue? 11 (Posted on 2019-02-10) Difficulty: 4 of 5
Before trying the problem "note your opinion as to whether the observed pattern is known to continue, known not to continue, or not known at all."

Lets factor polynomials of the form x^n-1. Starting with 1 the following list can be generated:
n=1: (x-1)
n=2: (x-1)*(x+1)
n=3: (x-1)*(x^2+x+1)
n=4: (x-1)*(x+1)*(x^2+1)
n=5: (x-1)*(x^4+x^3+x^2+x+1)
n=6: (x-1)*(x+1)*(x^2+x+1)*(x^2-x+1)

One thing to notice is that each line has exactly one polynomial factor not seen earlier in the list:
n=1: x-1
n=2: x+1
n=3: x^2+x+1
n=4: x^2+1
n=5: x^4+x^3+x^2+x+1
n=6: x^2-x+1

Does each new factorization always produce exactly one new polynomial factor?

Looking more closely you may see that all the coefficients are -1, 0, or 1. Does this continue to be the case for all factors?

No Solution Yet Submitted by Brian Smith    
Rating: 5.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Answering a different question... | Comment 1 of 3
Initial opinion: first I thought it probably true, by analogy with some Diophantine equations, but the reasoning there depends on convergents. 

So then I guessed probably unknown. 

Then I began to think about n=4; (x-1)*(x+1)*(x^2+1). (x+1)*(x^2+1) = x^3+x^2+x+1 which arguably at least in this context follows more of a 'pattern': (x+1), (x^2+x+1), (x^3+x^2+x+1) etc. 

In that case the problem answers itself: every such expression can be reduced to 2 terms, one of which is unique to that particular n. In fact, there are a number of ways to factor such expressions, e.g:

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

It's also easy to produce factorisations with larger coefficients, e.g: 

x^6-1 = (x-1)*(x+1)*(x^2+x+1)*(x^2-x+1), but also 
x^6-1 = (x-1)(x^2-x+1)(x^3+2x^2+2x+1)

What is needed is a comparing like with like method, treating all x^n-1 in the same way.

Start with the observation (x^(k*y)-1)/(x^y-1) =  sum (n=0 to k-1) x^(y*n)  [1]

This is true for all x,y,k, e.g.
(x^(2*3)-1)/(x^3-1) =  sum (n=0 to 2-1) x^(3*n)  i.e. (x^6-1)/(x^3-1) = (1+x^3)
(x^(5*5)-1)/(x^5-1) =  sum (n=0 to 5-1) x^(5*n)  i.e. (x^25-1)/(x^5-1)= (1+x^5+x^10+x^15+x^20)

Where the exponent is a prime square or power, i.e. k=y, or k=y^m  we can stop immediately, because all such representations are plainly unique.

Otherwise, {k,y} can always be selected so that GCD {k,y} = 1, when sum (n=0 to k-1) x^(y*n) is divisible by sum (n=0 to k-1) x^n  
Equivalently,  ((x-1) (x^(ky)-1))/((x^k-1) (x^y-1))   [2]

Say k=3, y=5: x^8-x^7+x^5-x^4+x^3-x+1
Say k=7, y=4: x^18-x^17+x^14-x^13+x^11-x^9+x^7-x^5+x^4-x+1

Note that if the values of k and y are swapped, the final part of the expression does not change:
x^28-1 = (x^7-1)(x^3+x^2+x+1)(x^18-x^17+x^14-x^13+x^11-x^9+x^7-x^5+x^4-x+1)
x^28-1 = (x^4-1)(x^6+x^5+x^4+x^3+x^2+x+1)(x^18-x^17+x^14-x^13+x^11-x^9+x^7-x^5+x^4-x+1)

Call [2] the invariant.

The difficulty with composite square exponents is that, e.g: ((x-1) (x^(36)-1))/((x^6-1) (x^6-1)) 
leads to the unlovely invariant:
x^25-x^24+2x^19-2x^18+3x^13-3x^12+ 4x^7-4x^6+(1-2x)/(x^2-x+1)+3/(x^2+x+1)+5x+2/(x+1) - 5
However, if the factors are rearranged, so that e.g. 36=9*4:
(x^36-1) = (x^9-1)(x^3+x^2+x+1)(x^24-x^23+x^20-x^19+x^16-x^14+x^12-x^10+x^8-x^5+x^4-x+1)
So to summarise:

x^(k*y)-1 = (x^y-1)(sum (n=0 to k-1) x^(y*n)). The first part (x^y-1) is non-unique as it must have appeared earlier in the list. If the exponent is a prime square or power, then (sum (n=0 to k-1) x^(y*n)) will be unique to that exponent and irreducible.

Otherwise, apply equation [2], giving x^(k*y)-1 = (x^y-1)(x^(k-1)+x^(k-2)...+x+1)*(invariant). The first part, (x^y-1) is non-unique as it will have appeared earlier in the list. The second part (x^(k-1)+x^(k-2)...+x+1), must have appeared whenever k has been a factor of a smaller exponent. The invariant remains the same whichever valid factor is selected to generate the factorisation. But if so, then it follows at once by the fundamental theorem of arithmetic that every invariant must be unique.

So in answer to the questions in the puzzle:

1. It is possible to factor every polynomial of form x^n-1 so that it has one and exactly one new polynomial factor, namely the invariant mentioned above. Further, every such invariant is unique.  It is true that an invariant can on occasion be further factored; for example invariant {k,y} = {3,4} = (x^2-x+1)(x^4-x^2+1). Naturally, since 12 divides 24 and 36, these are also factors of {k,y} = {3,8}, and {k,y} = {4,9}, but this does not diminish the uniqueness of the invariants themselves.

2. All such factorisations have coefficients of either -1, 0, or 1. This is inherent to the method as outlined above.

  Posted by broll on 2019-02-11 07:27:41
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information