4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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 mathoverflow.net/questions/56579 (thanks to Mark Sapir and Gerry Myerson). Gerhard "Where Do Deleted Comments Go?" Paseman, 2011.02.24 $\endgroup$ Feb 25, 2011 at 7:22
  • $\begingroup$ 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]$. $\endgroup$ Mar 3, 2011 at 22:07
  • $\begingroup$ 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.$ $\endgroup$ Mar 8, 2011 at 23:46
  • $\begingroup$ Above: $n \geq 2$ and $p$ does NOT divide $2n(n-1).$ $\endgroup$ Mar 8, 2011 at 23:51

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ @Aaron: Interesting idea. Can we say something when (say) $n \equiv 1 \pmod{p(p-1)}$ ? $\endgroup$ Feb 25, 2011 at 19:56
  • $\begingroup$ Most of the time they factor but not always.... $\endgroup$ Feb 26, 2011 at 0:53
  • $\begingroup$ 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.$ $\endgroup$ Mar 2, 2011 at 23:00
  • $\begingroup$ 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.$ $\endgroup$ Mar 3, 2011 at 22:20
  • $\begingroup$ 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. $\endgroup$ Mar 4, 2011 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.