# Factoring and solving trinomials

Has the problem of factoring (over the rationals) the general trinomial $ax^n+bx^k+c$ with $a,b,c\in\mathbb{Z}$, $n,k\in\mathbb{N}, n>k>1$ been solved? By solved I mean a classification theorem which will either give the factors or give a certificate that it is irreducible.

One could ask the same question, but about finding expressions for the roots of a trinomial. I am aware that long ago this problem was worked on, but I have been unable to find a modern treatment of this problem.

The question which actually motivates this one is: given a trinomial which factors, consider the number of terms in each of the factors. Further, assume that the trinomial is not cyclotomic. How many terms can the factors have? [The cyclotomic case is conjectured to be special].

[Edit: clarified that I am interested in this special case, not the general case, where the algorithms of M. van Hoeij are the current best, much superior to Cantor-Zassenhaus].

-
I am curious about the question/conjecture that you mention at the end: would you mind giving more details? –  Victor Protsak Jul 15 '10 at 18:58

One can of course apply general algorithms for irreducibility testing and factorization, so I presume you are asking if there is something more efficient or more explicit that can be said in the case of trinomials. Except for special cases I don't believe that is the case.

While it is known that every binomial in $\mathbb{Q}(x)$ must have an irreducible factor that is either binomial or trinomial, no analogous bound is known in the trinomial case. It is at least 8 terms due to the known [1] example

$$f(x)f(-x) = - x^{14} - 27180501562500 x^2 + 1244325625000000$$

for $f(x) = x^7 + 20 x^6 + 200 x^5 + 2450 x^4 + 29000 x^3 + 545000 x^2 + 8101250 x + 35275000$

1 Choudhry and A. Schinzel (1992).
On the number of terms in the irreducible factors of a polynomial over $\mathbb Q$.
Glasgow Mathematical Journal (1992), 34, 11-15.

To dig deeper I suggest starting with the work of Schinzel - who has studied these and related factorization problems intensively for almost half a century, e.g. see

MR1254093 (95d:11146) 11R09 (12E05 12E10)
Schinzel, Andrzej. On reducible trinomials.
Dissertationes Math. (Rozprawy Mat.) 329 (1993), 83 pp.

Let $K$ be a field. It is well known that a binomial $x^n+a\in K[x]$ is reducible iff it has the form $x^{pk}-b^p$ ($p$ prime) or $x^{4k}+4b^4$. In this treatise the reducibility of trinomials $x^n+ax^m+b$ $(a,b\neq 0)$ is investigated. It turns out that the situation is very complicated. A satisfactory answer is obtained if $K$ is a rational function field. For algebraic function fields in one variable and for algebraic number fields, less complete results are proved. It is assumed throughout that the characteristic of $K$ does not divide $mn(n-m)$.

It is easy to find trinomials with linear or quadratic factors. Table 1 of this paper provides additional families of reducible trinomials if $(n,m)$ belongs to a list of 12 pairs, the largest being $(15,5)$. Perhaps the simplest example is $$x^6+4(v+1)x^2-v^2=(x^3+2x^2+2x-v)(x^3-2x^2+2x+v).$$ Every reducible trinomial $f(x)=x^n+ax^m+b$ gives rise to additional examples by considering $u^nf(x^l/u)$ (with $u\in K^\times$ and $l\geq 1$) or $x^nf(1/x)/b$. Theorem 1 essentially states that every reducible trinomial arises in this manner from the examples indicated before if $K$ is a rational function field. (More precisely, it is assumed that $a^{-n}b^{n-m}$ is not a constant.) Table 2 lists $7$ families of reducible trinomials $x^n+A(v,w)x^m+B(v,w)$ with $(v,w)\in > E(K)$, where $A$, $B$ are polynomials over $\mathbb Z$ and $E$ is an elliptic curve defined by an equation $z^2=C(w)$, where $C$ is a monic polynomial over $\mathbb Z$. The polynomials $A,B$ and the corresponding factorizations of the trinomials are too complicated to be included in this review. (For the largest pair $(n,m)=(21,7)$ the corresponding $A$ fills 10 lines in the paper.) In Theorem 2 it is assumed that $K$ is a finite extension of a rational function field $F(t)$ such that $\overline FK$ has genus $g>0$ and $a^{-n}b^{n-m}\notin > \overline{F}$. If $g=1$ then there are no additional examples of reducible trinomials. If $g>1$ then essentially new examples with $n<24g$ may exist. Theorem 3 reduces the case where $K$ is a finite separable extension of $F(t)$ and $a^{-n}b^{n-m}\in\overline > F$ to studying reducibility over $K\cap\overline F$. If $K$ is an algebraic number field then for fixed $n$, $m$ a finite number of essentially new examples of reducible trinomials $x^n+ax^m+b$ may exist (Theorem 6). The author conjectures that for every $K$ there is only a finite number of these sporadic trinomials''. If the conjecture holds then there exists a constant $c(K)$ such that every trinomial over $K$ has an irreducible factor with at most $c(K)$ nonzero coefficients (Consequence 2). Table 5 contains all 52 sporadic trinomials over $\mathbb > Q$ known to the author. Their degrees lie in the range from $8$ to $52$. The rest of the paper is devoted to studying the reducibility of $ax^n+bx^m+c\in\mathbb Z[x]$. Theorem 9 (refining a result of Nagell) derives necessary conditions, which in the case $(m,n)=1$ yield an explicit bound for $b$ in terms of $a,c,m,n$. For every positive integer $d$ there exist only finitely many $n,m,b$ with $n/(m,n)>d$ and $|b|>2$ such that $x^n+bx^m\pm 1$ has a factor of degree $d$; and these can be effectively computed. Theorem 10 derives necessary conditions from the existence of a factor (of $ax^n+bx^m+c)$ of given degree $d$. These imply that there exists $n_0(d)$ such that $x^n+bx^m+1$ is irreducible if $n\geq n_0(d)$, $n\neq 2m$, $|b|>2$. By Theorem 8, for every $n$ there exist only finitely many reducible trinomials $x^n+bx^m+1$ with $n\neq 2m$.

The proof of Theorem 10 does not depend on the other results of the paper. The same applies to Theorem 9. All other theorems except for Theorem 3 are based on lower estimates for the genus of certain function fields. These estimates show that the existence of a factor of degree $k$ of $x^n+ax^m+b\in K[x]$ imposes severe restrictions on $k,m,n,a,b$ provided $K$ is a function field. The remaining cases are treated in a long series of lemmas applying to every field $K$ whose characteristic does not divide $mn(n-m)$. In several cases the proofs require extensive manipulations (with polynomials in several variables) which were performed by means of computer algebra systems. Faltings' theorem (solving Mordell's conjecture) is invoked in the proof of Theorem 6 (dealing with number fields). Theorems 7 and 8 (concerning $ax^n+bx^m+c\in\mathbb Z[x])$ are proved by using the corresponding theorems for rational function fields together with a lemma which may be viewed as a refinement of Hilbert's irreducibility theorem. The proof of this lemma is based on Siegel's theorem (on integral points of curves of positive genus) and on a result of Maillet (1919) dealing with rational functions over $\mathbb Q$ taking infinitely many integral values at rational points.

{Reviewer's remarks: In Theorem 2 the term $u^{\nu-\mu}$ in the expression for $B$ has to be replaced by $u^\nu$. The proof of Lemma 27 employs Lemma 2(c) although this lemma only applies to separable extensions. In order to prove Lemma 49 one has to know that every finite separable extension $L$ of $K(t)$ with $L\subseteq \overline > K(t)$ is contained in $K'(t)$ for some separable extension $K'$ of $K$. (One can in fact prove that $L=K'(t)$ for suitable $K'$. This need not be true for inseparable $L$.) The proof of Theorem 6 is apparently based on the incorrect assumption that a divisor $P$ of a function field $L=K(t,y)$ has degree $1$ or is ramified with respect to $K(t)$ if $t$ and $y$ are congruent to elements of $K\bmod P$.}

REVISED (1995)

Reviewed by G. Turnwald

-
Excellent. I was aware of some of Schinzel's work on this, but not those particular papers. –  Jacques Carette Jul 15 '10 at 22:18

Factor where? Over the rationals? Take a look to Berlekamp algorith. http://en.wikipedia.org/wiki/Berlekamp%27s_algorithm

The right link is http://en.wikipedia.org/wiki/Berlekamp%E2%80%93Zassenhaus_algorithm to Berlekamp–Zassenhaus algorithm.

-
Well, I meant rationals but I should maybe edit to put the right link to Wikipedia en.wikipedia.org/wiki/Berlekamp%E2%80%93Zassenhaus_algorithm Berlekamp–Zassenhaus algorithm –  ABC Jul 15 '10 at 19:00
See my edits. Computer algebra is one of my areas of expertize, so I am rather familiar with the work you mention already. So I have edited my question to make it clearer what I am looking for. –  Jacques Carette Jul 15 '10 at 22:19
No idea then. I have no areas of expertize. –  ABC Jul 16 '10 at 3:42