Polynôme d'Ehrhart

En mathématiques, on associe à un polytope entier (c'est-à-dire à un polytope convexe dont les coordonnées des sommets sont entières) son polynôme d'Ehrhart (étudié par Modèle:Lien vers 1960), lequel décrit une relation entre le volume du polytope et le nombre des points à coordonnées entières qu'il contient. La théorie de ces polynômes peut être vue comme une généralisation du théorème de Pick en dimensions supérieures.

Définition

L'idée de la construction de Ehrhart est de considérer comme fonction de t le nombre de points entiers intérieurs à un polytope obtenu par homothétie par un facteur t du polytope étudié.

Plus précisément, soit un réseau $ℒ$ de l'espace euclidien $ℝ^{n}$ et un polytope Modèle:Math de $ℝ^{n}$ dont tous les sommets sont des points du réseau (par exemple , on utilise fréquemment le réseau $ℒ = ℤ^{n}$ et des polytopes dont tous les sommets ont des coordonnées entières), engendrant un sous-espace affine de dimension Modèle:Math (Modèle:Math est appelé la dimension de Modèle:Math). Pour tout entier positif Modèle:Math, soit Modèle:Math le polytope obtenu par dilatation de Modèle:Math par un facteur Modèle:Math, c'est-à-dire le polytope obtenu en multipliant par Modèle:Math les coordonnées de tous les sommets (exprimés dans une base du réseau, et soit $L (P, t) = # (t P \cap ℒ)$ le nombre de points du réseau contenus dans le polytope Modèle:Math. Modèle:Lien montra en 1962 que Modèle:Math est un polynôme en Modèle:Math de degré Modèle:Math, c'est-à-dire qu'il existe des nombres rationnels $L_{0} (P), \dots, L_{d} (P)$ tels que $L (P, t) = L_{d} (P) t^{d} + L_{d - 1} (P) t^{d - 1} + \dots + L_{0} (P)$ pour tout entier Modèle:Math.

Le polynôme d'Ehrhart de l'intérieur d'un polytope convexe Modèle:Math de dimension Modèle:Math vérifie $L (int (P), t) = (- 1)^{d} L (P, - t),$ résultat connu sous le nom de réciprocité d'Ehrhart–Macdonald^[1].

Exemples

Soit Modèle:Math un hypercube unité de dimension Modèle:Math, dont les sommets sont les points dont toutes les coordonnées valent 0 ou 1, autrement dit $P = {x \in ℝ^{d} : 0 \leq x_{i} \leq 1; 1 \leq i \leq d} .$

La dilatation de Modèle:Math par Modèle:Math est un hypercube de côté Modèle:Math, contenant Modèle:Math points entiers, et donc le polynôme d'Ehrhart de Modèle:Math est Modèle:Math^[2]Modèle:,^[3]. On voit aussi qu'aux entiers négatifs, on a $L (P, - t) = (- 1)^{d} (t - 1)^{d} = (- 1)^{d} L (int (P), t),$ comme le prédit la réciprocité d'Ehrhart–Macdonald.

Bien d'autres nombres figurés peuvent s'exprimer à l'aide de polynômes d'Ehrhart. Par exemple, les nombres pyramidaux carrés sont donnés par le polynôme d'Ehrhart d'une pyramide à base carrée de côtés et de hauteur 1 ; le polynôme d'Ehrhart est dans ce cas Modèle:Math^[4].

Quasi-polynômes d'Ehrhart

Soit Modèle:Math un polytope rationnel convexe, c'est-à-dire que $P = {x \in ℝ^{d} : A x \leq b},$ avec $A \in ℚ^{k \times d}$ et $b \in ℚ^{k}$ (cela revient à dire que Modèle:Math est l'enveloppe convexe d'un ensemble fini de points de $ℚ^{d}$ ). Posons $L (P, t) = # ({x \in ℤ^{n} : A x \leq t b})$ , le nombre de points entiers contenus dans Modèle:Math. Dans ce cas, Modèle:Math est un Modèle:Lien en Modèle:Math, c'est-à-dire que $L (P, t) = c_{d} (t) t^{d} + c_{d - 1} (t) t^{d - 1} + \dots + c_{0} (t)$ , où les $c_{i} (t)$ sont des fonctions périodiques de période entière. La loi de réciprocité d'Ehrhart–Macdonald est encore valable : on a $L (int (P), t) = (- 1)^{n} L (P, - t)$ .

Exemple de quasi-polynôme d'Ehrhart

Soit Modèle:Math un quadrilatère de sommets (0,0), (0,2), (1,1) et (Modèle:Sfrac, 0). Le nombre de points entiers dans Modèle:Math est donné par le quasi-polynôme $L (P, t) = \frac{7 t^{2}}{4} + \frac{5 t}{2} + \frac{7 + (- 1)^{t}}{8}$ ^[5].

Interprétation des coefficients

Si Modèle:Math est fermé (c'est-à-dire que les faces de la frontière appartiennent à Modèle:Math), certains coefficients de Modèle:Math ont une interprétation simple :

le coefficient dominant, $L_{d} (P)$ , est égal au volume Modèle:Math-dimensionnel de Modèle:Math, divisé par $v (ℒ)$ , le covolume du réseau $ℒ$ ;
le second coefficient, $L_{d - 1} (P)$ , peut se calculer en partant des réseaux $ℒ_{F}$ induits par $ℒ$ sur les faces Modèle:Math de Modèle:Math : $L_{d - 1} (P)$ est obtenu en divisant le (d-1)-volume de chaque face Modèle:Math par $2 v (ℒ_{F})$ , et en faisant la somme de ces nombres pour toutes les faces de Modèle:Math ;
le coefficient constant Modèle:Math est la caractéristique d'Euler de Modèle:Math ; dans le cas convexe et fermé, on a $L_{0} (P) = 1$

Séries d'Ehrhart

La série génératrice des polynômes d'Ehrhart pour un polytope Modèle:Math de dimension Modèle:Math est ${Ehr}_{P} (z) = \sum_{t \geq 0} L (P, t) z^{t}$ .

Cette série est une fraction rationnelle ; plus précisément, Ehrhart a démontré qu'il existe des nombres complexes $h_{j}^{*}$ (dépendants de Modèle:Math) tels que ${Ehr}_{P} (z) = \frac{\sum_{j = 0}^{d} h_{j}^{*} z^{j}}{(1 - z)^{d + 1}}, \sum_{j = 0}^{d} h_{j}^{*} \neq 0 .$

De plus, le théorème de non-négativité de Richard Stanley affirme que sous ces hypothèses, les $h_{j}^{*}$ sont des entiers naturels.

Un autre résultat de Stanley montre que si Modèle:Math iest un polytope contenu dans Modèle:Math (sur le même réseau, on a $h_{j}^{*} (P) \leq h_{j}^{*} (Q)$ pour tout Modèle:Math^[6].

Séries d'Ehrhart pour des polytopes rationnels

On peut également définir des séries analogues pour un polytope rationnel Modèle:Math de dimension Modèle:Math. Appelant Modèle:Math ile plus petit entier tel que Modèle:Math soit un polytope entier (Modèle:Math est appelé le dénominateur de Modèle:Math), on a la formule

{Ehr}_{P} (z) = \sum_{t \geq 0} L (P, t) z^{t} = \frac{\sum_{j = 0}^{D (d + 1)} h_{j}^{*} (P) z^{j}}{{(1 - z^{D})}^{d + 1}},

où les $h_{j}^{*}$ sont encore des entiers naturels^[7]Modèle:,^[8].

Bornes pour les coefficients

On peut déterminer des bornes pour les coefficients non dominants $c_{0}, \dots, c_{d - 1}$ de la représentation $L (P, t) = \sum_{r = 0}^{d} c_{r} t^{r}$ : on a par exemple^[9] $c_{r} \leq (- 1)^{d - r} [\begin{matrix} d \\ r \end{matrix}] c_{d} + \frac{(- 1)^{d - r - 1}}{(d - 1)!} [\begin{matrix} d \\ r + 1 \end{matrix}]$ , où $[\begin{matrix} n \\ k \end{matrix}]$ est un nombre de Stirling de première espèce ; des bornes inférieures existent également^[10]

Notes et références

Modèle:Traduction/Référence Modèle:Références

Bibliographie

Modèle:Portail

[1] Modèle:Article

[2] Modèle:Harvsp.

[3] Modèle:Harvsp.

[4] Modèle:Harvsp.

[MR2271992-5] Modèle:Ouvrage

[6] Modèle:Article

[7] Modèle:Article

[8] Modèle:Article

[9] Modèle:Article

[10] Modèle:Article

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Polynôme d'Ehrhart

Sommaire

Définition

Exemples

Quasi-polynômes d'Ehrhart

Exemple de quasi-polynôme d'Ehrhart

Interprétation des coefficients

Séries d'Ehrhart

Séries d'Ehrhart pour des polytopes rationnels

Bornes pour les coefficients

Notes et références

Bibliographie

Menu de navigation

Polynôme d'Ehrhart

Définition

Exemples

Quasi-polynômes d'Ehrhart

Exemple de quasi-polynôme d'Ehrhart

Interprétation des coefficients

Séries d'Ehrhart

Séries d'Ehrhart pour des polytopes rationnels

Bornes pour les coefficients

Notes et références

Bibliographie

Menu de navigation

Rechercher