MATH. SCAND. 4 (1956), 287-302 ON THE IRREDUCIBILITY OF CERTAIN TRINOMIALS ERNST S. SELMER 1. Through a study of generalized continued fractions, I have been led to certain questions concerning the irreducibility of polynomials. Let us first consider the general problem: The ordinary algorithm for a continued fraction may be described as a systematic replacement of two non-negative numbers, and a£r)tka>^T), by two other numbers, usually a^r+X) = a2 fl^W-OjW «i(r> «2(r) «»-i(/x) = -23, D(/2) = -31, which are the two smallest negative discriminants in the cubic case. n = 4: Z>(/x) = -283, D(/8) = +229. According to Delone and Faddeev [2], there exists one negative quartic discriminant with a smaller absolute value than D(f1), namely D = — 275. In the case of totally complex quartic fields, many discriminants smaller than D(f2) are known (the smallest one being D=117). However, the fields listed by Delone and Faddeev all have a quadratic subfield. Dr. H. J. Godwin has computed the small totally complex quartic fields, whether or not subfields exist. He has kindly informed me that Z>(/2) = 229 is really the least discriminant in the latter case. His results are submitted for publication to the Proc. Cambridge Phil. Soc. n = 5: D(ft) = 2869 , while /2[x) is reducible (cf. (3.1) below). The minimal discriminants of quintic fields have been calculated by Hunter [4]. In the case of 4 complex roots, the minimum is D= 1609, and there are at least 6 more fields with a smaller discriminant than D(f1). For w^6, no results on minimal discriminants are available.—I owe all references to such discriminants to Dr. J. W. S. Cassels. 3. For large n, all zeros of the polynomials (1.5) will clearly have a modulus close to 1. As we shall see later (cf. fig. 1, p. 292), a modulus = 1 can occur only for x = e±2ml3, corresponding to a rational factor xz + x + 1. It is easily seen that this is possible only for/2(x), in the case m = 2 (mod 3). The first such factorizations are given by (3.1) x5 + x+l = [x2 + x+l)(xs-x* + l) xB + x+l = (x2 + x+ l)(xe-x5 + x3-x2+ 1) . The general form of the second factor is clear. The main purpose of the present paper is to prove the following Theorem 1. The polynomials fx(x) = xn — x — l are irreducible for all n. The polynomials Math. Scand. 4. f2(x) = xn + x + l 19 290 ernst s. selmer are irreducible for k. 2 (mod 3), but have a factor x2 + x + 1 for n = 2 (mod 3). In the latter case, the second factor of f2(x) is irreducible. This result does not seem to follow from any of the existing irre-ducibility criteria. The Eisenstein-Schonemann theorem and its generalizations (cf. Ore [6]) clearly fail. However, by studying reducibility modulo a prime p, Serret [11] and Ore [6] hare shown that the polynomial xp — x + a is irreducible when p is a prime such that p -fa. This result contains as a special case the irreducibility of my polynomials fx(x) when n is a prime. However, similar methods seem to fail for composite degrees. Criteria by primality of certain values of the function are clearly insufficient in the case of arbitrary degree (but see Section 7 below). Other general criteria, which also fail in my case, are listed in the expository article by Dorwart [3], and in Part 8, problems 116-129, of Polya and Szego [10]. An important criterion, typical of one approach to the problem, is given by Perron [8]: The polynomial (with integer coefficients) xn + a^-1 + a2xn~2 + ... +an_1x + an is irreducible if W > i + K\ + l«si + • ■ • + Kl • Applied to f(x) = xn + ax ± 1, where we substitute x=l/z, this shows that f(x) is irreducible for \a\ ^ 3. When \a\=2 and/(± 1) =f= 0, we can still conclude irreducibility according to Perron. When \a\ = 2 and f(x) has a rational factor x+ 1 or a; — 1, the second factor oif{x) will be irreducible (this is not contained among Perron's statements, but follows easily from his method). To sum up, we have the following Theorem 2 (Perron). The polynomial f(x) = xn + ax±l is irreducible for |a|g3. When \a\=2, f(x) is either irreducible or has a factor x±l. In the latter case, the second factor of f(x) is irreducible. Combined with my Theorem 1, this settles the problem of irreducibility of the polynomials . r J f(x) = xn + ax± 1 for all (integer) values of a. The only criterion for irreducibility of a trinomial g(x) = xn + qxP + r, is given by Nagell [5]: g(x) is irreducible if on the irredxjcibility of certain trinomials 291 1° \q\>l + \r\*-1. 2° If h\n, h>l, then \r\ is not a hth power. In particular, we must haTe |r| > 1. Nagell remarks that his result is clearly weaker than the above criterion of Perron in the case p = n — 1. It could also be noted that Nagell's first condition coincides with Perron's criterion for p = 1 (immediately seen if a; is replaced by rjz). In this case, Nagell's second condition is consequently redundant. However, his first condition fails for my polynomials (1.5). In a series of papers from 1935 to 1937, Petterson has discussed and extended many of the general irreducibility criteria. All results are also contained in his thesis [9], where in particular (pp. 95-96) the conditions are applied to the polynomial xm+EM(x)x + a (a 4= 0) . To get the types (1.5), we must put EM{x) = a= ± 1, in which case it is easily seen that Petterson's criteria all fail. 4. To prove Theorem 1, we must study the distribution in the complex plane of the roots of the equations (4.1) xn + (x+l) = 0 . It will turn out that this distribution is very regular. Substituting in (4.1) x = re** = r (cosy+ i sirup) , and separating the real and imaginary parts, we find (4.2) rn cos rup = ±(rcos& 1 +n~1 In 2, rn 1 — n_1 lnra . For f= ±tz/2, we have r = Rn1!2> 1. The curve (4.3) cuts through the unit circle r = 1 for cos that is, the sum of the roots less the sum of their reciprocals. —Clearly, S is additive by any factorization of f(x). As a symmetric function of the roots, 8 is rational, and integer if the constant term oif(x), in normalized form, is +1. In the latter case, any factorization oif(x) must yield an integer partition of $(/(#)), since a rational factor of f(x) must then also have a constant term + 1. For both functions f±(x) and f2{x) of (1.5), we find (5.2) S(fk(x)) =1, k = 1, 2 . On the other hand, by substituting xi = reiv, xj~1 = r~ 1e-i?" in (5.1), and summing in pairs over conjugate imaginary roots, we get / 1 \ r2 -1 (5.3) 2"(*i--)= U 2-cosl (cf. fig. 1). It is not difficult to conclude from (4.4) that the negative part of the sum will always be < 1 in absolute value (but this fact is not needed for completion of the proof). Consequently, any factorization of fk(x) must yield the integer partition (5.4) 1 = 0+1 of the sum (5.2). If we leave aside for a moment the possible factor x2 + x+l of f2(x) (where r—1, S = 0), one factor of fk(x) must contain some terms of both signs in the sum (5.3). As the negative terms all have r>l, we must compensate for this by taking some roots from the interval 2tt/3<0. A partition of the type (5.4), and thereby a factorization of fk{x), consequently becomes impossible. To carry through this idea in precise mathematical terms, we substitute for cos95 in (5.3) the expression (4.3): 294 ernst s. selmer r2 — 1 r2 — 1 r2n — r2 — 1 2--cos 9? = 2---- r r 2r = i_r2 + r2»-2(r2_l) ^ 1-1 , since r2M~2 (r2 — 1) ;> r2 — 1, with equality only for r=l, that is, for a possible factor x2 + x+ 1. If we remember that the sum (5.3) is taken over conjugate imaginary roots in pairs, we get the following inequality for the sum S for any factor of fk(x): (U) s.^-JL)^^.,). The sum is now taken over all roots (real or complex) separately. On the other hand, the product of the modulus over the same roots must give unity: /Z>= 1, or #1= 1. The geometric mean of all r~2 is consequently = 1. Since this is always ^ the arithmetic mean (again with equality only for all »"=1), it follows for the sum in (5.5) that Equality can occur only for the factor x2 + x + 1. This concludes the proof of Theorem 1. 6. Whenever a new method has been developed, one tries to apply it also to cases other than those for which it was originally designed. In this instance, however, it seems that my method is "tailor-made" for the polynomials f^x) and fz(x), and for these only. After a series of attempts to generalize to other polynomials, especially of the type xn + ax + b, I feel convinced that my method will lead to no new proofs of irreducibility. (The case 6= + 1 is already covered by Theorem 2, and for \b\ > 1, all arguments are destroyed by the fact that the sum 8 may become fractional). Let us consider the polynomials xn ± x2 ± 1 . When n is even, all four combinations of signs will here lead to essentially different cases. For simplicity, we shall only deal with the combinations f(x) = xn± (x2 + l) . on the irreddcibility of certain trinomials 295 Treating these as we did with fk{x) in Section 4 above, we find Exactly as in Section 5, we find that this sum is ^ 0 for any factor of f(x), with equality only for a possible factor with all r=l. However, the corresponding sum for f(x) itself (for n>4) has the value 2, not 1. We can therefore not conclude irreducibility, only the existence of at most two irreducible factors. A similar argument, with all inequalities reversed, holds for xn ± (x2 — 1). More generally, we can show that the polynomials (6.1) F(x) = xn±xm± 1, 1 Jk, have at most m irreducible factors, in addition to a possible factor with all r=l. This result is contained as a part of Theorem 3. The following results hold for the factorization of the trinomials (6.1): 1° All possible roots with modulus 1 are roots of a rational factor, typified by xu + xd+l | xn + xm+l = (a?)ni + {a?)mi + l , if n = nxd, m = m-^d, (nlt to2) = 1, n1 + m1 = 0 (mod 3), and all those cases resulting from changing the sign of xd. 2° Apart from a possible factor of the above type, there are at most m irreducible factors, all of degree > 5 for n>1. 3° // F(x) is irreducible or has a factor x2i±xd+l and a second, irreducible factor, then F(x2) has the same property. 4° All polynomials F(x) have this property for ng20 (and hence for w^40 when n and m are both even). 7. We shall only indicate the proof of Theorem 3.—The result 1° is established by forming an expression for cosm

= 2r2 Because of 29?, it is here natural to replace the sum (5.1) by 296 ernst s. selmer may itself be reducible, cf. (11.2). Changing the sign of xd is not the same as changing the sign of x itself, if d is even. A proof of the first statement under 2° is already sketched in Section 6. The second statement may be proved as follows: Since .^(0) = +1 and F(±I)= ±1 or ± 3, we get a very limited choice of values y(0) and ip( ± 1) for a possible factor y>(x) of F(x). For each set of values, ip(x) is uniquely determined mod (xs — x). A closer examination shows that a possible quadratic factor of F(x) must have one of the forms x2±x± \ . The constant term +1 gives a factor with all r = 1. The term — 1 is impossible, since the roots then differ too much from 1 in absolute value to be roots of F(x). Similarly, the possible cubic factors of F{x) are given by x3 ± x2 ± 1 or x3 ± x ± 1 , all with one real root. The same argument shows that this root can not satisfy F(x) — 0 for n>5. An exception for n = 5 is given by (3.1). In the same way, by factorizing F(i) in the field K(i), we get a limited choice of values y(i). For each choice, %p(x) is uniquely determined mod (xi +1). Combining this with the earlier modulus (Xs — x), we get a limited (but rather large) number of alternatives mod (x5—x) for a possible factor tp(x) of F(x). Using the same principle, we find that the resulting factors of degree 4 or 5 (apart from x*±x2+ 1) can not occur for n>18, and hence not for n>7 by 4° of Theorem 3. An exception (a factor of degree 5) occurs for to = 7, m = 2, cf. 1°. The statement 3° is proved in Section 11 below. Because of this result, the cases when n and m are both even could be left out in the numerical computations. To prove the result 4°, I have mainly used a primality criterion of Polya and Szego [10, Part 8, Problem 127]: Since all the roots of the polynomials (6.1) have an absolute value <1.5 for n>2, the criterion shows that F(x) is irreducible if F(k) is a prime for an integer argument k such that \k\>l. Replacing x by 1/x, we can argue similarly with knF(l/k). More generally, the criterion can be extended to the case anF(bja), provided that all the roots of F(x) have a modulus < (\b\ — \)f\a\. As shown in Section 8 below, the criterion of Polya and Szego can be extended to cover the case \F(k)\ = t-p, where p is a prime and t is a small factor. The cases F(x2) are completely settled by the result 3°. Some information regarding Fix3) can also be obtained, cf. Section 9. on the irreducibility of certain trinomials 297 By combining these different principles, I have been able to establish the result 4° of Theorem 3. For 14\ be an upper bound for the absolute values of the roots of F{x). For a polynomial xn±xm±l (m1. Then \tp(b)\ = |a0|-|fc-«1|-|i-«a|...|A-«a| ^ -MY, which is impossible by (8.1) if (8.2) t < (\k\-M)« . This irreducibility criterion is due to Weisner [12]. However, it is useless in the most important case |/fc| = 2, and can be improved. Following the idea of Polya and Szego, we take into account the fact that 5. A factorization (8.1) consequently showed irreducibility if t < (k2 - (|&|-l)Jf2)2. This criterion proved very useful also for \k\ = 2. To indicate the strength of the condition, we may mention that the inequality is then always satisfied for t S 7 when n 9. 9. When n and m are both even, the polynomials (6.1) are of the type In this section, we will study such polynomials in general, under the assumption that fix) is irreducible, and shall establish some obvious criteria for the irreducibility of fix2). Let f(x) be of degree n, with the highest term xn. It is easily seen that the only possible factorization of fix2) must have the form (9.1) Fix) = fix2) = i-l)*gix)gi-x) , where gix) is irreducible. With g(x) — xn + a1xn-1 + azxn~2+ ... +an , we get (9.2) Fix) = fix2) = ixn + a2xn-2 + aixn~i+ ...)2- - ia1xn-1 + a3xn~3+ ...)2. Clearly fix2) is irreducible if (9.3) ( —1)™/(0) is not a perfect square . Let Jc be a rational integer. From (9.2), we see that Fik)=fik2) is a difference between two squares, which is impossible if fik2) = 2 (mod 4). For even k, this is already contained in (9.3), but we get a criterion for the irreducibility of f(x2) for odd k: fil) = 2 (mod 4) . More information can be obtained from a (purely) imaginary value of on the irreducibility of certain trinomials 299 the argument. Then F(ik) =/( — fc2) is real, and |/( — fc2)| is a sum of two squares. Consequently, f(x2) is irreducible if |/( — &2)j is exactly divisible by an odd power of a prime 4h + 3. In particular, this is the case if (9.4) l/(-&2)l = 3 (mod 4), or = 6 (mod 8) . The criteria (9.3-4) are necessary to establish Theorem 4 of Section 10 below, and thereby the result 3° of Theorem 3. We can prove similar results for a polynomial F{x) = /(*») . With the same assumptions for f(x), a possible factorization must have the form F{x) = /(x3) = g(x)G(x) = g(x)g(ex)g(o*x), q = e*™<* . In particular, /(0) must be a perfect cube (always satisfied for the polynomials (6.1)). Further,/(P) can be written as (X + Y + Z)(X+ Yq + Zq*){X+ YqI + Zq) = X3+ Y* + Z*-3XYZ , with integers X, Y and Z. This cubic form is never exactly divisible by 3, and f(xz) is consequently irreducible if /(l) or /(-l) s ±3 (mod 9). This condition was useful when examining the polynomials (6.1). 10. When f(x) is a trinomial, we can obtain additional information regarding the irreducibility of f(x2). By operating modulo 4, we can prove the following Theorem 4. Let f(x) = xn + axm + b (m < n) be an irreducible trinomial satisfying the conditions (10.1) 23-ra, 2-r b, n 4= 2m, or (10.2) a ml or 2 (mod 4), 2|6. TAe-n. /(a;2) is also irreducible. Proof. We know that f{x%) must have the form (9.2). Multiplying out, we get f{x*) = x2n + ax2m + b = x*n + A%x2n-2 + Aix*n-i + where 300 ernst s. selmer 2a2 — ax2 a22 + 2a4 — 2a1a3 2a2a4 + 2a6 — a32 — 2a1a5 a42 + 2a2a6 + 2as — 2a-xa7 — 2a3«B All coefficients aN = 0 for N>n. Let first a be ocW. If .42 = 0, both ax and a2 are even, and so also A±. Consequently Ai = a is impossible, and we must have At = 0, a4 even. If also j16 = 0, both a3 and a6 are even. We conclude similarly that A8=$=a, ^8 = 0, ag even. Continuing the argument, we see that Aik^a, and that a factorization of f{x2) is impossible if n and m have the same parity. More generally, we have clearly established the irreducibility of is irreducible. When n and m have opposite parity, the case a = +1 (mod 4) can be excluded by similar arguments. If A2 — a, both ax and a2 are odd, and so also Ai; which is impossible (always if b is even; as a consequence of n4= 2m if 6 is odd). If ,42 = .44 = 0, A6 = a, we get o„ a2 and ai even, a3 and a6 odd, which again is impossible (either n