4

Let $n>1$ be an integer. An old result of Selmer, See Theorem 1, page 289 in

http://www.mscand.dk/article.php?id=1472,

(If the link does not work try googling: selmer trinomials)

says that

$$ S(n) = x^n-x-1 $$ is irreducible over the the field $k= \mathbb{Q}$ of rational numbers.

Question : What is known about the possible irreducibility (or not) of the sligthly more general trinomial

$$ T(n,m) = x^n - x^m -1 $$

(with $0 < m < n$)

over the prime field

$$ k =GF(p) $$

such that (say)

(a) $p>2,$

(since seems there are many known results for binary polynomials)

and

(b) $n$ goes to infinity when $p$ goes to infinity.

EDIT: Observe that something can be said about the parity of the number of irreducible factors: Use Stickelberger's parity theorem.

Ricardo Andrade
  • 6,139
Luis H Gallardo
  • 1,601
  • A previous answer about some (reducible) trinomial multiples of $x^2-x+1$ was deleted, taking some of my comments with it. I note that adding appropriate multiples of $x^3+1$ to $x^2-x+1$, and then dividing by $(+-1)x^k$ as desired, generates a two parameter family of trinomials (with an exponent in each residue class mod 3) whose signs depend on the added multiples, and are all multiples of $x^2-x+1$. Related to this is http://mathoverflow.net/questions/56579/ (thanks to Mark Sapir and Gerry Myerson). Gerhard "Where Do Deleted Comments Go?" Paseman, 2011.02.24 – Gerhard Paseman Feb 25 '11 at 07:22
  • Consider the $(2k+1)^n$ monic degree $n$ polynomials with all coefficients no larger in absolute value than $k$. One can see why "most" would be irreducible in $\mathbb{Z}[x]$ whereas many fewer would be irreducible in $\mathbb{Z}_p[x]$. Still, that seems like a pretty weak explanation of the fact that $x^n-x-1$ is always irreducible in $\mathbb{Z}[x]$ but appears to rarely be irreducible in $\mathbb{Z}_p[x]$. – Aaron Meyerowitz Mar 03 '11 at 22:07
  • Something is known (See Theorem 3.86, page 131 of Lidl and Niederreiter's book Finite Fields, vol 20 of Encyclopedia of Mathematics and its Applications, reprinted 1987) about the number $N(q,n)$ of $a \in GF(q)$ that make the trinomial $$ S_n(x) =x^n+x+a $$ irreducible over $GF(q)$: $$ \vert N(q,n)- \frac{q}{n} \vert \leq B_n q^{1/2} $$ for some constant $B_n$ depending only on $n.$ – Luis H Gallardo Mar 08 '11 at 23:46
  • Above: $n \geq 2$ and $p$ does NOT divide $2n(n-1).$ – Luis H Gallardo Mar 08 '11 at 23:51

1 Answers1

4

Based on a small number of small cases I suspect that the majority of those do factor.

Let $r$ be a primitive root $\mod p$ then there is an $n$ such that $r^n=r+1 \mod p$. Then $x-r$ is a factor of $x^n-x-1$ in $\mathbb{Z}_p$. On average $n$ should be about $p/2$. Of course one can use $x^{n+p-1}-x-1$ but that seems like cheating. That is just cases with a linear factor.

For $p=19, $ $x^k-x-1$ factors for $2 \le k \le 18$ except for $k=4$ and $k=15$.

SashaKolpakov
  • 1,236
Aaron Meyerowitz
  • 30,015
  • @Aaron: Interesting idea. Can we say something when (say) $n \equiv 1 \pmod{p(p-1)}$ ? – Luis H Gallardo Feb 25 '11 at 19:56
  • Most of the time they factor but not always.... – Aaron Meyerowitz Feb 26 '11 at 00:53
  • For all prime numbers less than $103$ (not tried more since this begin to take some time in maple) the only irreducible polynomial $$ x^{p(p-1)+1}-x-1 $$ in $GF(p)[x]$ occurs when $p=5.$ – Luis H Gallardo Mar 02 '11 at 23:00
  • My comment was that $x^{jp(p-1)+1}-x-1 $ factors "most of the time but not always" $\mod p$. That is just based on small $p$ and $j$, but it does seem pretty dramatic.Up to $j=29$, $x^{20j+1}-x-1$ factors $\mod 5$ except for $j=1,17$ and $x^{6j+1}-x-1$ factors $\mod 3$ except for $j=2,12,20.$ – Aaron Meyerowitz Mar 03 '11 at 22:20
  • It appears that for prime $p=4k-1$ one has that $x^2+x+2k$ is a factor of $x^{p^2-p+1}-x-1$. I have no proof though. – Aaron Meyerowitz Mar 04 '11 at 02:38
  • @Aaron: I think I have a proof. I will be emailing you soon. – Luis H Gallardo Mar 05 '11 at 23:43