On-line catalogue and orders (secure paiement, VISA or MASTERCARD only)

Journals available by subscription

Annales scientifiques de l'ENS

Astérisque

Bulletin de la SMF

Mémoires de la SMF

Revue d'Histoire des Mathématiques

Gazette des Mathématiciens

Books

Astérisque

Cours Spécialisés

Documents Mathématiques

Mémoires de la SMF

Panoramas et Synthèses

Séminaires et Congrès

Jean Morlet Chair Series

SMF/AMS Texts and Monographs

La Série T

Volumes "Journée Annuelle"

Other Books

Donald E. Knuth - French translations

Nicolas Bourbaki's seminar new edition

Jean Leray's scientific works new edition

Revue de l'Institut Elie Cartan

Electronic Editions

Annales scientifiques de l'ENS

Bulletin de la SMF

Revue d'Histoire des Mathématiques

Séminaires et Congrès

More information / Subscription

Publications for a general public

L'explosion des mathématiques (smf.emath.fr)

Mathématiques L'explosion continue (smf.emath.fr)

Zoom sur les métiers des maths (smf.emath.fr)

Zoom sur les métiers des mathématiques et de l'informatique (smf.emath.fr)

Où en sont les mathématiques ?

La Série T

For the authors

Submission of manuscripts

Formats and documentation

More info

Electronic distribution list (smf.emath.fr)

Information for bookselers and subscription agencies (smf.emath.fr)

Publications de la SMF
fr en
Your IP number: 54.227.6.156
Access to elec. publ.: SémCong

Bulletin de la SMF

Presentation of the publication

Titles

Last Titles

Editorial staff committee / Secretary

Number:

Search


Catalogue & orders

Bulletin de la SMF - Titles - 121 - pages 299-314

Titles121

Une borne optimale pour la programmation entière quasi-convexe
Bernd Bank - Joos Heintz - Teresa Krick - Reinhard Mandel - Pablo Solernó
Bulletin de la Société mathématique de France 121, number 2 (1993), 299-314
Download this article : PS file / PDF file

Résumé :
Soient $F_1,\ldots ,F_s\in 
\mathbb {Z}
[X_1,\ldots ,X_N]$ des polynômes quasiconvexes de degré majoré par $d\geq 2$, et $\ell $ une borne pour la longueur binaire de leurs coefficients. On montre que si le système $F_1\leq 0,\ldots ,F_s\leq 0$ admet une solution entière, alors il existe une telle solution à longueur binaire majorée par $(sd)^{cn} \ell $ (où c est une constante, indépendante de s,d,n et $\ell $). Le caractère simplement exponentiel de cette borne est intrinsèque au problème. On obtient aussi une borne similaire pour le problème de minimisation correspondant.

Abstract:
Let $F_1,\ldots , F_s\in 
\mathbb {Z}
[X_1,\ldots ,X_n]$ be quasiconvex polynomials of degrees bounded by $d\geq 2$ and assume that the maximum binary length of the coefficients of these polynomials doesn't exceed a given natural number $\ell $. We show that the system of polynomial inequalities $F_1\leq 0,\ldots ,F_s\leq 0$ admits an integer solution if and only if such a solution with binary length bounded by $(sd)^{cn} \ell $ exists. (Here c is a constant, independent on s,d,n and $\ell $). The simply exponential nature of this bound is intrinsical to this problem. We obtain a similar geometrical bound for the corresponding minimisation problem.

Class. math. : 90 C 10, 65 K 05


ISSN : 0037-9484
Publié avec le concours de : Centre National de la Recherche Scientifique