Polynôme d'Ehrhart

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 ${\displaystyle {\mathcal {L}}}$ de l'espace euclidien ${\displaystyle \mathbb {R} ^{n}}$ et un polytope P de ${\displaystyle \mathbb {R} ^{n}}$dont tous les sommets sont des points du réseau (par exemple , on utilise fréquemment le réseau ${\displaystyle {\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 ${\displaystyle 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 ${\displaystyle L_{0}(P),\dots ,L_{d}(P)}$ tels que ${\displaystyle 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 ${\displaystyle L(\operatorname {int} (P),t)=(-1)^{d}L(P,-t),}$ résultat connu sous le nom de réciprocité d'Ehrhart–Macdonald^[1].

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 ${\displaystyle 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${\displaystyle 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)(2t + 3)^[4].

Soit P un polytope rationnel convexe, c'est-à-dire que ${\displaystyle P=\left\{x\in \mathbb {R} ^{d}:Ax\leq b\right\},}$ avec ${\displaystyle A\in \mathbb {Q} ^{k\times d}}$ et ${\displaystyle b\in \mathbb {Q} ^{k}}$ (cela revient à dire que P est l'enveloppe convexe d'un ensemble fini de points de ${\displaystyle \mathbb {Q} ^{d}}$). Posons ${\displaystyle 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 ${\displaystyle L(P,t)=c_{d}(t)t^{d}+c_{d-1}(t)t^{d-1}+\cdots +c_{0}(t)}$, où les ${\displaystyle 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 ${\displaystyle L(\operatorname {int} (P),t)=(-1)^{n}L(P,-t)}$.

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 ${\displaystyle L(P,t)={\frac {7t^{2}}{4}}+{\frac {5t}{2}}+{\frac {7+(-1)^{t}}{8}}}$^[5].

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, ${\displaystyle L_{d}(P)}$, est égal au volume d-dimensionnel de P, divisé par ${\displaystyle v({\mathcal {L}})}$, le covolume du réseau ${\displaystyle {\mathcal {L}}}$ ;
• le second coefficient, ${\displaystyle L_{d-1}(P)}$, peut se calculer en partant des réseaux ${\displaystyle {\mathcal {L}}_{F}}$ induits par ${\displaystyle {\mathcal {L}}}$ sur les faces F de P : ${\displaystyle L_{d-1}(P)}$ est obtenu en divisant le (d-1)-volume de chaque face F par ${\displaystyle 2v({\mathcal {L}}_{F})}$, et en faisant la somme de ces nombres pour toutes les faces de P ;
• le coefficient constant a₀ est la caractéristique d'Euler de P ; dans le cas convexe et fermé, on a ${\displaystyle L_{0}(P)=1}$

La série génératrice des polynômes d'Ehrhart pour un polytope P de dimension d est ${\displaystyle \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 ${\displaystyle h_{j}^{*}}$ (dépendants de P) tels que ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle h_{j}^{*}(P)\leq h_{j}^{*}(Q)}$ pour tout j^[6].

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

${\displaystyle \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 ${\displaystyle h_{j}^{*}}$ sont encore des entiers naturels^[7],[8].