[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

1492.0. "Factors of X^n - 1" by CIVAGE::LYNN (Lynn Yarbrough @WNP DTN 427-5663) Thu Sep 12 1991 14:07

Here's an interesting problem, culled from a recent Mathematica text I was 
browsing through:

We note that
x^2 - 1 = (x - 1) (x + 1)
X^3 - 1 = (x - 1) (x^2 + x + 1)
...
x^12 - 1 = 
                          2            2                2    4    2
        (x - 1) (x + 1) (x  + x + 1) (x  - x + 1) (1 + x ) (x  - x  + 1)

etc.

In each of the above examples, all of the polynomial coefficients of each 
factor are either +1, -1, or 0. Is this generally true of the factors of 
X^n - 1 for integer n>0?  You are invited to offer either a proof or a
counterexample.

T.R	Title	User	Personal Name	Date	Lines
1492.1		ALLVAX::JROTH	I know he moves along the piers	`Fri Sep 13 1991 08:09`	7
	The first counterexample is (x^105-1), because the 105'th cyclotomic polynomial is the first one that doesn't have all coefficients of -1,0,+1... (Stan's masters thesis was on cyclotomic polynomials...) - Jim
1492.2	what type of poly is cyclotomic ?	STAR::ABBASI		`Fri Sep 13 1991 10:54`	1
	what is , please, is cyclotomic polynomials ?
1492.3		ALLVAX::JROTH	I know he moves along the piers	`Fri Sep 13 1991 16:38`	6
	Cyclotomy has to do with subdivision of the circle. Cyclotomic polynomials are the products of the primitive n'th roots of unity. - Jim
1492.4		HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Wed Sep 25 1991 16:00`	1
	Don't leave us hanging ! Please factor x^105 - 1. Thanks.
1492.5	MAPLE factors x^105-1	CIVAGE::LYNN	Lynn Yarbrough @WNP DTN 427-5663	`Wed Sep 25 1991 16:48`	23
	> factor(x^105-1); 6 5 4 3 2 4 3 2 5 (x - 1) (x + x + x + x + x + x + 1) (x + x + x + x + 1) (1 - x + x 6 7 8 10 11 12 13 14 16 17 18 19 23 - x + x - x + x - x + x - x + x - x + x - x + x - x 24 2 3 4 6 8 9 11 12 + x ) (x + x + 1) (1 - x + x - x + x - x + x - x + x ) 3 4 5 7 8 6 5 2 7 24 12 (1 - x + x - x + x - x + x ) (1 + x - x - x + x - 2 x - x + x 8 13 14 16 17 9 15 48 20 22 26 28 - x + x + x + x + x - x + x + x - x - x - x - x 31 32 33 34 35 36 39 40 41 42 43 46 + x + x + x + x + x + x - x - x - 2 x - x - x + x 47 + x )
1492.6	Remember SNL's "Great mysteries of the Universe"?	VMSDEV::HALLYB	Fish have no concept of fire	`Wed Sep 25 1991 19:42`	13
	Thanks, MAPLE & Lynn. What a shame, a couple of 2s spoil a lonnnng series of 0s and 1s. Which gives rise to the following sorts of questions: Given k>0, what is the smallest N(k) such that k appears as a coefficient in the factorization in X^N - 1? Does N(k) exist for all k? Does the value of k/N(k) converge as k --> oo ? To what? In case anyone is looking for a research project... John
1492.7	They're rare	CIVAGE::LYNN	Lynn Yarbrough @WNP DTN 427-5663	`Thu Sep 26 1991 15:38`	5
	I know that "large" (abs value > 1) coefficients are quite rare. N=935 is the smallest that I know of that has a k=3. I think N has to have at least 3 distinct prime factors to produce a large one, and even that is not enough. x^(5711*13)-1 has some 4's and 5's. Fascinating but time-consuming hobby...