Date: Mon, 20 Mar 95 16:23:44 CST From: rusin (Dave Rusin) To: eppstein@wormwood.ics.uci.edu Subject: Re: x^k - x^(k-1) - 1 irreducible? Status: RO In article <3ki9bh$osj@wormwood.ics.uci.edu> you write: >While working on something else, I began playing with polynomials >of the form x^k - x^(k-1) - 1. After factoring the first 100 of these >over Q in Mathematica, an interesting pattern emerged: >except for the factor x^2 - x + 1 which exists whenever k = -1 mod 6, >these polynomials seem to be irreducible. > >Is this true for larger k? Easy? Known? The only general technique I >know for proving irreducibility is Eisenstein's criterion, which doesn't >work here even after a linear change of variable. I don't know either, but it's a good problem. Could you send me a copy of any answers you get? Possible hints: (1) Replace x by 1/x to get f(x) = x^k + x - 1, a little simpler. (2) One other general technique for proving irreducibility: If f is irreducible mod p for some p, then it's irreducible (Irreducibility mod p is not too hard to check: you need x^(p^k)=x mod p with k minimal such. Use the base-2 expansion of factors of k to evaluate x^(p^k) easily.) (3) A method for factoring: If f(x) = g(x) h(x), then for each integer n we have f(n)=g(n)h(n). With a given f, we then have only a finite number of possibilities for g(1), g(2), g(3), etc. Then g can be found by Lagrange interplation. In this case, for example, the _only_ quadratic factors possible are +-1, +-(x^2-x-1), +-(x^2+x-1), and +-(2x^2-1). dave ============================================================================== To: rusin@math.niu.edu Subject: x^k - x^(k-1) - 1 irreducible? Date: Mon, 20 Mar 1995 14:33:46 -0800 From: David Eppstein Here is another answer I received. I think the paper he refers to is the following one (taken from the INSPEC database): H. Osada. The Galois groups of the polynomials X^n + a X^l + b. Journal of Number Theory, Feb. 1987, vol.25, (no.2):230-8. Abstract: Conditions under which the Galois group of the polynomial X^n + a X^l + b over the rational number field Q is isomorphic to the symmetric group S_n of degree n are given. Using the result, the author proves the Williams-Uchiyama conjecture (see K.S. Williams, Canad. Math. Bull., vol.12, p.545-65, 1969 and S. Uchiyama, Proc. Japan Acad., vol.46, p.755-7, 1970) concerning the irreducibility of the polynomial X^n + X + a modulo p. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/ ============================================================================== To: [Anonymous], rusin@math.niu.edu, A.H.Rodgers@dcs.qmw.ac.uk Subject: x^k - x^(k-1) - 1 irreducible? Date: Tue, 28 Mar 1995 14:15:38 -0800 From: David Eppstein The question I originally asked was, if we define p_k(x) = x^k - x^(k-1) - 1, then is it true that p_k(x) is irreducible over Q if k neq 5 (mod 6) and has only the factor x^2 - x + 1 if k = 5 (mod 6). Through various sources it now seems that this is true and pretty much already known. - Dave Rusin pointed out the transformation x -> 1/x which simplifies the polynomial a little to x^k + x - 1. - Keith Conrad gave me a pointer to the paper "The Galois groups of the polynomials X^n + a X^l + b", by H. Osada [J. Num. Th. 25 (1987) 230-238] which turns out only to be about proving that if p_k (or some other trinomials) is in fact irreducible, then the Galois group is S_k (with some side conditions on the coefficients that turn out to be always true for p_k). However, it gave me a pointer to Selmer. - Ernst Selmer ["On the irreducibility of certain trinomials", Math. Scand. 4 (1956) 287-302] considers exactly the polynomials x^k +- x +- 1. He notes that by changing signs, you can make the +-'s match each other. He shows (by considering the distribution of roots in the complex plane) that x^k-x-1 is always irreducible, and that x^k+x+1 has the factor x^2+x+1 if k is 2 (mod 3) and is otherwise irreducible. For (Rusin's version of) p_k, the sign change gives us x^k - x - 1 if k is even, and x^k + x + 1 if k is odd. Therefore Selmer's results answer the question I asked. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/