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/