Integer linear programming applied to determining monic hyperbolic irreducible polynomials with integer coefficients and span less than 4. (English. French summary) Zbl 1271.90053

Summary: We propose a new method to find monic irreducible polynomials with integer coefficients, only real roots, and span less than 4. The main idea is to reduce the search of such polynomials to the solution of integer linear programming problems. In this frame, the coefficients of the polynomials we are looking for are the integer unknowns. We give inequality constraints specified by the properties that the polynomials should have, such as the typical distribution of their roots. These properties can be inferred from those of polynomials already treated in the literature on this topic.


90C10 Integer programming
90C05 Linear programming
13F20 Polynomial rings and ideals; rings of integer-valued polynomials
13P05 Polynomials, factorization in commutative rings


Full Text: DOI Link Link


[1] S. Capparelli, A. Del Fra, C. Sciò, On the span of polynomials with integer coefficients. Mathematics of Computation, S 0025-5718(09)02292-3. · Zbl 1216.12001
[2] PARI/GP, version 2.5.0. Bordeaux, 2011,
[3] GNU Linear Programming Kit, version 4.35.
[4] M. Galassi et al, GNU Scientific Library Reference Manual (2nd Ed.). ISBN 0954161734.
[5] V. Flammang, G. Rhin, Q. Wu, The Totally Real Algebraic Integers with Diameter less than 4. Moscow Journal of Combinatorics and Number Theory Vol. 1 (2011), Iss. 1, 21-32. · Zbl 1261.11028
[6] L. Kronecker, Zwei Sätze über Gleichungen mit ganzzahligen Koefficienten. J. Reine Angew. Math. 53 (1857), 173-175.
[7] R. Robinson, Intervals containing infinitely many sets of conjugate algebraic integers. Studies in Mathematical Analysis and Related Topics: Essays in honor of George Pólya, Stanford Univ. Press, 1962, 305-315. MR0144892 (26:2433). · Zbl 0116.25402
[8] R. Robinson, Algebraic equations with span less than 4. Math. Comp. 18 (1964), 547-559. MR0169374 (29:6624). · Zbl 0147.12905
[9] I. Schur, Über die Verteilung der Würzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten. Math. Z. 1 (1918), 377-402. MR1544303. · JFM 46.0128.03
[10] MPI Forum. Message Passing Interface (MPI) Forum Home Page. (Dec. 2009).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.