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 à . 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.
@article{JTNB_2013__25_1_71_0,
author = {El Otmani, Souad and Maul, Armand and Rhin, Georges and Sac-\'Ep\'ee, Jean-Marc},
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 = {http://www.numdam.org/articles/10.5802/jtnb.826/}
}
TY - JOUR AU - El Otmani, Souad AU - Maul, Armand AU - Rhin, Georges AU - Sac-Épée, Jean-Marc 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 SP - 71 EP - 78 VL - 25 IS - 1 PB - Société Arithmétique de Bordeaux UR - http://www.numdam.org/articles/10.5802/jtnb.826/ DO - 10.5802/jtnb.826 LA - en ID - JTNB_2013__25_1_71_0 ER -
%0 Journal Article %A El Otmani, Souad %A Maul, Armand %A Rhin, Georges %A Sac-Épée, Jean-Marc %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 http://www.numdam.org/articles/10.5802/jtnb.826/ %R 10.5802/jtnb.826 %G en %F JTNB_2013__25_1_71_0
El Otmani, Souad; Maul, Armand; Rhin, Georges; Sac-Épée, Jean-Marc. 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. http://www.numdam.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
[2] PARI/GP, version 2.5.0. Bordeaux, 2011, http://pari.math.u-bordeaux.fr/
[3] GNU Linear Programming Kit, version 4.35. http://www.gnu.org/software/glpk/glpk.html
[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
[6] L. Kronecker, Zwei Sätze über Gleichungen mit ganzzahligen Koefficienten. J. Reine Angew. Math. 53 (1857), 173–175. | Zbl
[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 | Zbl
[8] R. Robinson, Algebraic equations with span less than 4. Math. Comp. 18 (1964), 547–559. MR0169374 (29:6624). | MR | Zbl
[9] I. Schur, Über die Verteilung der Würzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten. Math. Z. 1 (1918), 377–402. MR1544303. | MR
[10] MPI Forum. Message Passing Interface (MPI) Forum Home Page. http://www.mpi-forum.org/ (Dec. 2009).
Cité par Sources :
