Integer Linear Programming applied to determining monic hyperbolic irreducible polynomials with integer coefficients and span less than 4
Journal de Théorie des Nombres de Bordeaux, Tome 25 (2013) no. 1, pp. 71-78.

Dans ce travail, nous proposons une nouvelle méthode destinée à trouver des polynômes unitaires irréductibles à racines réelles, à coefficients entiers, et dont le diamètre soit inférieur à 4. L’idée principale est de ramener la recherche de tels polynômes à la résolution d’un problème d’optimisation en entiers. Dans ce cadre, les coefficients des polynômes que nous cherchons sont les inconnues entières du problème. Nous donnons des contraintes sur les coefficients induites par les propriétés que l’on s’attend à trouver pour de tels polynômes, notamment une répartition particulière de leurs racines. Ces propriétés s’inspirent de celles des polynômes déjà connus dans la littérature relative à ce domaine.

In this work, 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.

Reçu le :
Révisé le :
Publié le :
DOI : https://doi.org/10.5802/jtnb.826
@article{JTNB_2013__25_1_71_0,
     author = {Souad El Otmani and Armand Maul and Georges Rhin and Jean-Marc Sac-\'Ep\'ee},
     title = {Integer {Linear} {Programming} applied to determining monic hyperbolic irreducible polynomials with integer coefficients and span less than 4},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {71--78},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {25},
     number = {1},
     year = {2013},
     doi = {10.5802/jtnb.826},
     zbl = {1271.90053},
     mrnumber = {3063831},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.826/}
}
Souad El Otmani; Armand Maul; Georges Rhin; Jean-Marc Sac-Épée. Integer Linear Programming applied to determining monic hyperbolic irreducible polynomials with integer coefficients and span less than 4. Journal de Théorie des Nombres de Bordeaux, Tome 25 (2013) no. 1, pp. 71-78. doi : 10.5802/jtnb.826. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.826/

[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. | MR 2948323 | Zbl pre06077904

[6] L. Kronecker, Zwei Sätze über Gleichungen mit ganzzahligen Koefficienten. J. Reine Angew. Math. 53 (1857), 173–175. | Zbl 053.1389cj

[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). | MR 144892 | Zbl 0116.25402

[8] R. Robinson, Algebraic equations with span less than 4. Math. Comp. 18 (1964), 547–559. MR0169374 (29:6624). | MR 169374 | 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. | MR 1544303

[10] MPI Forum. Message Passing Interface (MPI) Forum Home Page. (Dec. 2009).