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, Volume 25 (2013) no. 1, pp. 71-78.

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.

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.

Received:
Revised:
Published online:
DOI: 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/}
}
TY  - JOUR
TI  - Integer Linear Programming applied to determining monic hyperbolic irreducible polynomials with integer coefficients and span less than 4
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2013
DA  - 2013///
SP  - 71
EP  - 78
VL  - 25
IS  - 1
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.826/
UR  - https://zbmath.org/?q=an%3A1271.90053
UR  - https://www.ams.org/mathscinet-getitem?mr=3063831
UR  - https://doi.org/10.5802/jtnb.826
DO  - 10.5802/jtnb.826
LA  - en
ID  - JTNB_2013__25_1_71_0
ER  - 
%0 Journal Article
%T Integer Linear Programming applied to determining monic hyperbolic irreducible polynomials with integer coefficients and span less than 4
%J Journal de Théorie des Nombres de Bordeaux
%D 2013
%P 71-78
%V 25
%N 1
%I Société Arithmétique de Bordeaux
%U https://doi.org/10.5802/jtnb.826
%R 10.5802/jtnb.826
%G en
%F JTNB_2013__25_1_71_0
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, Volume 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).

Cited by Sources: