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 Eugène Ehrhart (en) 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 ${\mathcal {L}}$ de l'espace euclidien $\mathbb {R} ^{n}$ et un polytope $P$ de $\mathbb {R} ^{n}$ dont tous les sommets sont des points du réseau (par exemple , on utilise fréquemment le réseau ${\mathcal {L}}=\mathbb {Z} ^{n}$ et des polytopes dont tous les sommets ont des coordonnées entières), engendrant un sous-espace affine de dimension $d$ ( $d$ est appelé la dimension de $P$ ). Pour tout entier positif $t$ , soit $tP$ le polytope obtenu par dilatation de $P$ par un facteur $t$ , c'est-à-dire le polytope obtenu en multipliant par $t$ les coordonnées de tous les sommets (exprimés dans une base du réseau, et soit $L(P,t)=\#\left(tP\cap {\mathcal {L}}\right)$ le nombre de points du réseau contenus dans le polytope $tP$ . Ehrhart (en) montra en 1962 que $L$ est un polynôme en $t$ de degré $d$ , 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}+\cdots +L_{0}(P)$ pour tout entier $t$ .

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

Exemples

Le dilaté correspondant à

t=2

d'un carré unité contient

(t+1)^{2}=9

points entiers.

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

La dilatation de $P$ par $t$ est un hypercube de côté $t$ , contenant $(t + 1) d$ points entiers, et donc le polynôme d'Ehrhart de $P$ est $L (P, t) = (t + 1) d$ ^[2]^,^[3]. On voit aussi qu'aux entiers négatifs, on a $L(P,-t)=(-1)^{d}(t-1)^{d}=(-1)^{d}L(\operatorname {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 $1 / 6 (t + 1)(t + 2)(2 t + 3)$ ^[4].

Quasi-polynômes d'Ehrhart

Soit $P$ un polytope rationnel convexe, c'est-à-dire que $P=\left\{x\in \mathbb {R} ^{d}:Ax\leq b\right\},$ avec $A\in \mathbb {Q} ^{k\times d}$ et $b\in \mathbb {Q} ^{k}$ (cela revient à dire que $P$ est l'enveloppe convexe d'un ensemble fini de points de $\mathbb {Q} ^{d}$ ). Posons $L(P,t)=\#\left(\left\{x\in \mathbb {Z} ^{n}:Ax\leq tb\right\}\right)$ , le nombre de points entiers contenus dans $tP$ . Dans ce cas, $L (P, t)$ est un quasi-polynôme (en) en $t$ , c'est-à-dire que $L(P,t)=c_{d}(t)t^{d}+c_{d-1}(t)t^{d-1}+\cdots +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(\operatorname {int} (P),t)=(-1)^{n}L(P,-t)$ .

Exemple de quasi-polynôme d'Ehrhart

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

Interprétation des coefficients

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

le coefficient dominant, $L_{d}(P)$ , est égal au volume $d$ -dimensionnel de $P$ , divisé par $v({\mathcal {L}})$ , le covolume du réseau ${\mathcal {L}}$ ;
le second coefficient, $L_{d-1}(P)$ , peut se calculer en partant des réseaux ${\mathcal {L}}_{F}$ induits par ${\mathcal {L}}$ sur les faces $F$ de $P$ : $L_{d-1}(P)$ est obtenu en divisant le (d-1)-volume de chaque face $F$ par $2v({\mathcal {L}}_{F})$ , et en faisant la somme de ces nombres pour toutes les faces de $P$ ;
le coefficient constant $a 0$ est la caractéristique d'Euler de $P$ ; 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 $P$ de dimension $d$ est $\operatorname {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 $P$ ) tels que $\operatorname {Ehr} _{P}(z)={\frac {\sum _{j=0}^{d}h_{j}^{\ast }z^{j}}{(1-z)^{d+1}}},\qquad \sum _{j=0}^{d}h_{j}^{\ast }\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 $P$ iest un polytope contenu dans $Q$ (sur le même réseau, on a $h_{j}^{*}(P)\leq h_{j}^{*}(Q)$ pour tout $j$ ^[6].

Séries d'Ehrhart pour des polytopes rationnels

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

\operatorname {Ehr} _{P}(z)=\sum _{t\geq 0}L(P,t)z^{t}={\frac {\sum _{j=0}^{D(d+1)}h_{j}^{\ast }(P)z^{j}}{\left(1-z^{D}\right)^{d+1}}},

où les $h_{j}^{*}$ sont encore des entiers naturels^[7]^,^[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{bmatrix}d\\r\end{bmatrix}}c_{d}+{\frac {(-1)^{d-r-1}}{(d-1)!}}{\begin{bmatrix}d\\r+1\end{bmatrix}}$ , où $\left[{\begin{smallmatrix}n\\k\end{smallmatrix}}\right]$ est un nombre de Stirling de première espèce ; des bornes inférieures existent également^[10]

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Ehrhart polynomial » (voir la liste des auteurs).

↑ Ian G. Macdonald, « Polynomials associated with finite cell-complexes », Journal of the London Mathematical Society, vol. 2, n^o 1,‎ 1971, p. 181–192 (DOI 10.1112/jlms/s2-4.1.181)
↑ De Loera, Rambau et Santos 2010.
↑ Mathar 2010.
↑ Beck et al. 2005.
↑ Matthias Beck et Sinai Robins, Computing the Continuous Discretely, New York, Springer, 2007, 46–47 (MR 2271992)
↑ Richard Stanley, « A monotonicity property of $h$ -vectors and $h^{*}$ -vectors », European Journal of Combinatorics, vol. 14,‎ 1993 (DOI 10.1006/eujc.1993.1028)
↑ Richard P. Stanley, « Decompositions of rational convex polytopes », Annals of Discrete Mathematics, vol. 6,‎ 1980, p. 333–342 (ISBN 9780444860484, DOI 10.1016/s0167-5060(08)70717-9)
↑ Matthias Beck et Frank Sottile, « Irrational proofs for three theorems of Stanley », European Journal of Combinatorics, vol. 28, n^o 1,‎ janvier 2007, p. 403–409 (DOI 10.1016/j.ejc.2005.06.003, arXiv math/0501359, S2CID 7801569)
↑ (en) Ulrich Betke et Peter McMullen, « Lattice points in lattice polytopes », Monatshefte für Mathematik, vol. 99, n^o 4,‎ 1^er décembre 1985, p. 253–265 (ISSN 1436-5081, DOI 10.1007/BF01312545, S2CID 119545615)
↑ Martin Henk et Makoto Tagami, « Lower bounds on the coefficients of Ehrhart polynomials », European Journal of Combinatorics, vol. 30, n^o 1,‎ 1^er janvier 2009, p. 70–83 (ISSN 0195-6698, DOI 10.1016/j.ejc.2008.02.009, arXiv 0710.2665, S2CID 3026293)

Bibliographie

Eugène Ehrhart, « Sur les polyèdres rationnels homothétiques à n dimensions », Comptes rendus de l'académie des Sciences, vol. 254,‎ 1962, p. 616–618 (MR 0130860)
(en) Ricardo Diaz et Sinai Robins, « The Ehrhart polynomial of a lattice n-simplex », Electronic Research Announcements of the American Mathematical Society, vol. 2,‎ 1996, p. 1–6 (DOI 10.1090/S1079-6762-96-00001-7, MR 1405963)
(en) Matthias Beck, Jesús A. De Loera, Mike Develin, Julian Pfeifle et Richard P. Stanley, « Integer Points in Polyhedra—Geometry, Number Theory, Algebra, Optimization », Contemporary Mathematics, Providence, RI, American Mathematical Society, vol. 374,‎ 2005, p. 15–36 (MR 2134759)
(en) Mircea Mustață, « Lecture notes on toric varieties », février 2005
(en) Matthias Beck et Sinai Robins, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, New York, Springer-Verlag, coll. « Undergraduate Texts in Mathematics », 2007 (ISBN 978-0-387-29139-0, MR 2271992)
(en) Jesús A. De Loera, Jörg Rambau et Francisco Santos, Triangulations: Structures for Algorithms and Applications, vol. 25, Springer, coll. « Algorithms and Computation in Mathematics », 2010 (ISBN 978-3-642-12970-4, lire en ligne), p. 475
(en) Richard J. Mathar, Point counts of $D_{k}$ and some $A_{k}$ and $E_{k}$ integer lattices inside hypercubes, 2010 (Bibcode 2010arXiv1002.3844M, arXiv 1002.3844)
Hélène Chakroun, « Le théorème d'Ehrhart », sur Université Grenoble-Alpes, 22 mai 2017

Portail de la géométrie

[1] Ian G. Macdonald, « Polynomials associated with finite cell-complexes », Journal of the London Mathematical Society, vol. 2, n^o 1,‎ 1971, p. 181–192 (DOI 10.1112/jlms/s2-4.1.181)

[2] De Loera, Rambau et Santos 2010.

[3] Mathar 2010.

[4] Beck et al. 2005.

[MR2271992-5] Matthias Beck et Sinai Robins, Computing the Continuous Discretely, New York, Springer, 2007, 46–47 (MR 2271992)

[6] Richard Stanley, « A monotonicity property of $h$ -vectors and $h^{*}$ -vectors », European Journal of Combinatorics, vol. 14,‎ 1993 (DOI 10.1006/eujc.1993.1028)

[7] Richard P. Stanley, « Decompositions of rational convex polytopes », Annals of Discrete Mathematics, vol. 6,‎ 1980, p. 333–342 (ISBN 9780444860484, DOI 10.1016/s0167-5060(08)70717-9)

[8] Matthias Beck et Frank Sottile, « Irrational proofs for three theorems of Stanley », European Journal of Combinatorics, vol. 28, n^o 1,‎ janvier 2007, p. 403–409 (DOI 10.1016/j.ejc.2005.06.003, arXiv math/0501359, S2CID 7801569)

[9] (en) Ulrich Betke et Peter McMullen, « Lattice points in lattice polytopes », Monatshefte für Mathematik, vol. 99, n^o 4,‎ 1^er décembre 1985, p. 253–265 (ISSN 1436-5081, DOI 10.1007/BF01312545, S2CID 119545615)

[10] Martin Henk et Makoto Tagami, « Lower bounds on the coefficients of Ehrhart polynomials », European Journal of Combinatorics, vol. 30, n^o 1,‎ 1^er janvier 2009, p. 70–83 (ISSN 0195-6698, DOI 10.1016/j.ejc.2008.02.009, arXiv 0710.2665, S2CID 3026293)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]