Integer Linear Programming applied to determining monic hyperbolic irreducible polynomials with integer coefficients and span less than 4

Souad El Otmani[1]; Armand Maul[2]; Georges Rhin[2]; Jean-Marc Sac-Épée[2]

  • [1] Université de Lorraine, site de Metz Ile du Saulcy 57045 Metz Cedex
  • [2] Université de Lorraine, site de Metz Ile du Saulcy 57050 Metz Cedex

Journal de Théorie des Nombres de Bordeaux (2013)

  • Volume: 25, Issue: 1, page 71-78
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

El Otmani, Souad, et al. "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 25.1 (2013): 71-78. <http://eudml.org/doc/275691>.

@article{ElOtmani2013,
abstract = {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.},
affiliation = {Université de Lorraine, site de Metz Ile du Saulcy 57045 Metz Cedex; Université de Lorraine, site de Metz Ile du Saulcy 57050 Metz Cedex; Université de Lorraine, site de Metz Ile du Saulcy 57050 Metz Cedex; Université de Lorraine, site de Metz Ile du Saulcy 57050 Metz Cedex},
author = {El Otmani, Souad, Maul, Armand, Rhin, Georges, Sac-Épée, Jean-Marc},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {inequality constraints; roots},
language = {eng},
month = {4},
number = {1},
pages = {71-78},
publisher = {Société Arithmétique de Bordeaux},
title = {Integer Linear Programming applied to determining monic hyperbolic irreducible polynomials with integer coefficients and span less than 4},
url = {http://eudml.org/doc/275691},
volume = {25},
year = {2013},
}

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
DA - 2013/4//
PB - Société Arithmétique de Bordeaux
VL - 25
IS - 1
SP - 71
EP - 78
AB - 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.
LA - eng
KW - inequality constraints; roots
UR - http://eudml.org/doc/275691
ER -

References

top
  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. Zbl1216.12001
  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. Zbl1261.11028MR2948323
  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). Zbl0116.25402MR144892
  8. R. Robinson, Algebraic equations with span less than 4. Math. Comp. 18 (1964), 547–559. MR0169374 (29:6624). Zbl0147.12905MR169374
  9. I. Schur, Über die Verteilung der Würzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten. Math. Z. 1 (1918), 377–402. MR1544303. Zbl46.0128.03MR1544303
  10. MPI Forum. Message Passing Interface (MPI) Forum Home Page.http://www.mpi-forum.org/ (Dec. 2009). 

NotesEmbed ?

top

You must be logged in to post comments.