Benutzer:SigmaB/Ehrhart-Theorie

Die Ehrhart-Theorie beschäftigt sich mit dem Abzählen von Gitterpunkten in Polytopen und deren Vielfachen. Nach einer Arbeit von Eugène Ehrhart aus dem Jahr 1962 ist die Zählfunktion für die Gitterpunkte in ganzzahligen Vielfachen eines Gitterpolytops durch ein Polynom gegeben, das Ehrhart-Polynom.

Durch das Ehrhart-Polynom entsteht ein Zusammenhang zwischen dem Volumen des Polytops und der Anzahl von Gitterpunkten und inneren Gitterpunkten des Polytops und seiner Vielfachen. Somit liefert die Ehrhart-Theorie eine Verallgemeinerung des Satzes von Pick.

Neben dem Ehrhart-Polynom wird auch die Ehrhart-Reihe als erzeugende Funktion des Ehrhart-Polynoms und das $h^{*}$-Polynom als Zählerpolynom der rationalen Funktion, welche der Ehrhart-Reihe zuordnen werden kann, untersucht.

Motivation

Für ein Polytop $P\subseteq \mathbb {R} ^{d}$ kann das Volumen ${\text{vol}}(P)$ als Grenzwert diskreter Volumnina bestimmt werden, die sich durch betrachten des Polytops im Gitter ${\frac {1}{n}}\mathbb {Z} ^{d}$ ergeben. Durch Verschiebungen der abgeschlossenen Grundmasche $\{(x_{1},\dotsc ,x_{d})\in \mathbb {R} ^{d}\mid 0\leq x_{1},\dotsc ,x_{d}\leq {\frac {1}{n}}\}$ um Gittervektoren ergibt sich nämlich eine Parketierung des $\mathbb {R} ^{d}$ durch Hyperwürfel der Kantenlänge ${\frac {1}{n}}$ und mit Hilfe der Anzahl der Gitterpunkte im Polytop kann abgezählt werden, von wie vielen dieser Hyperwürfel ein bestimmter Eckpunkt im Polytop liegt. Es gilt daher

${\text{vol}}(P)=\lim _{n\to \infty }{\frac {1}{n^{d}}}|P\cap {\frac {1}{n}}\mathbb {Z} ^{d}|=\lim _{n\to \infty }{\frac {1}{n^{d}}}|nP\cap \mathbb {Z} ^{d}|,$

wobei mit $|\cdot |$ die Anzahl der Elemente der Menge bezeichnet wurde.

Definitionen

Ist $P\subseteq \mathbb {R} ^{n}$ ein ganzzahliges Polytop der Dimension $d$, d.h. ein Polytop dessen Eckpunkte in $\mathbb {Z} ^{n}\subseteq \mathbb {R} ^{n}$ liegen und dessen affine Hülle ein $d$-dimensionaler affiner Unterraum ist, dann ist die Gitterpunktzählfunktion $L_{P}:\mathbb {Z} _{\geq 1}\to \mathbb {Z} _{\geq 0},k\mapsto |kP\cap \mathbb {Z} ^{d}|$ für die Gitterpunkte in ganzzahligen Vielfachen von $P$ durch eine Polynomfunktion vom Grad $d$ gegeben. Es gibt also ein Polynom ${\text{ehr}}_{P}\in \mathbb {Q} [t]$, sodass $L_{P}(k)={\text{ehr}}_{P}(k)$ für alle $k\in \mathbb {Z} _{\geq 1}$ gilt, und ${\text{ehr}}_{P}$ wird als Ehrhart-Polynom von $P$ bezeichnet.

Als Ehrhart-Reihe von $P$ bezeichnen wir die erzeugende Funktion des Ehrhart-Polynoms, also die formale Potenzreihe $Ehr_{P}(x)=\sum _{t=0}^{\infty }{\text{ehr}}_{P}(t)x^{t}\in \mathbb {Z} [[x]]$.

Als ganzwertiges Polynom hat das Ehrhart-Polynom ${\displaystyle }$ eine eindeutige Darstellung als ganzzahlige Linearkombination der Binomialkoeffizienten

${\binom {t+d-k}{d}}={\frac {(t+d-k)(t-d-k-1)\cdots (t-k+1)}{d!}},k=0,\dotsc ,d$

und es gibt somit ganzen Zahlen $h_{0}^{*}(P),\dotsc ,h_{d}^{*}(P)$, sodass

${\text{ehr}}_{P}(t)=\sum _{k=0}^{d}h_{k}^{*}(P){\binom {t+d-k}{d}}.$

Für $h_{P}^{*}(x):=\sum _{i=0}^{d}h_{i}^{*}(P)x^{i}$ ergibt sich

$Ehr_{P}(x)=\sum _{t=0}^{\infty }|tP\cap \mathbb {Z} ^{d}|x^{t}={\frac {h_{P}^{*}(x)}{(1-x)^{d+1}}}.$

Das Polytop $h_{P}^{*}$ wird als $h^{*}$-Polynom des ganzzahligen Polytops $P$ bezeichnet. Der Grad des $h^{*}$-Polynom wird auch als Grad von $P$ bezeichnet, wofür im Folgenden ${\text{deg}}(P)$ geschrieben wird.

Koeffizienten und Werte des Ehrhart- und des $h^{*}$-Polynoms

Das Ehrhart-Polynom ist ein ganzwertiges Polynom von Grad $d$. Damit ergibt sich für ein volldimensionales Polytop $P$ mit den Überlegungen in der Motivation das Volumen ${\text{vol}}(P)$ als Leitkoeffizient des Ehrhart-Polynoms. Ist $P$ nicht volldimensional, so erhält man als Leitkoeffizient das vom entsprechenden Untergitter induzierte Volumen.

Der auf den Leitkoeffizienten folgende Koeffizient des Ehrhart-Polynoms ergibt sich als Hälfte der Summe der Facettenvolumina, wobei diese relativ zum jeweiligen Untergitter, in welchem die Facette liegt, zu bestimmen sind.

Wegen

${\text{ehr}}_{P}(t)=\sum _{k=0}^{{\text{deg}}(P)}h_{k}^{*}(P){\binom {t+d-k}{d}}$

erhält man das Absolutglied des Ehrhart-Polynoms als ${\text{ehr}}_{P}(0)=h_{0}^{*}(P)=1$ und außerdem ${\text{ehr}}_{P}(1)=|P\cap \mathbb {Z} ^{d}|=h_{1}^{*}(P)+d+1$. Ebenso ergibt sich damit aus dem Leitkoeffizienten des Ehrhart-Polynoms das normalisierte Volumen als Wert des $h_{P}^{*}$-Polynoms in $1$, also

$h_{P}^{*}(1)=\sum _{k=0}^{{\text{deg}}(P)}h_{k}^{*})P)=d!\ {\text{vol}}(P)$.

Gilt ${\text{deg}}(P)<d$, so erhalten für das Ehrhartpolynom die Nullstellen

${\text{ehr}}_{P}(-1)=\dotsc ={\text{ehr}}_{P}(-(d-{\text{deg}}(P)))=0.$

Ehrhart-Macdonald Reziprozität

Die Ehrhart-Macdonald Reziprozität liefert eine Interpretation für die Werte des Ehrhartpolynoms für negative ganze Zahlen. Ist nämlich $P\subseteq \mathbb {R} ^{n}$ ein $d$-dimensionales ganzzahliges Polytop mit Ehrhart-Polynom ${\text{ehr}}_{P}$ und wird mit $int(\cdot )$ das Innere eines Polytops bezeichnet, so gilt für negative ganze Zahlen $-n$

${\text{ehr}}_{P}(-n)=(-1)^{d}|{\text{int}}(nP)\cap \mathbb {Z} ^{d}|.$

Die Werte für negative ganze Zahlen ergeben sich also bis auf das dimensionsabhängige Vorzeichen als Anzahl der inneren Gitterpunkte des entsprechend skalierten Polytops.

Insbesondere folgt für den Leitkoeffizienten des $h^{*}$-Polynoms

$h_{{\text{deg}}(P)}^{*}=|{\text{int}}((d+1-{\text{deg}}(P))P)\cap \mathbb {Z} ^{d}|$

und $d+1-{\text{deg}}(P)$ ist die kleinste ganze Zahl, sodass $kP$ einen inneren Gitterpunkt hat.

Abschätzungen für Koeffizienten

Die Koeffizienten des $h^{*}$-Polynoms sind nicht-negative ganze Zahlen. Diese Abschätzung von Stanley ergibt sich auch als Spezialfall einer ebenfalls von Stanley bewiesenen Monotonieaussage für das $h^{*}$-Polynom zweier unterschiedlicher Polytope. Es gilt nämlich für Gitterpolytope $Q\subseteq P$ stets koeffizientenweise

$h_{Q}^{*}\leq h_{P}^{*}.$

Aus der Beschreibung der Koeffizienten folgt außerdem allgemein die Abschätzung

$h_{d}^{*}(P)=|{\text{int}}(P)\cap \mathbb {Z} ^{n}|\leq |P\cap \mathbb {Z} ^{n}|-(d+1)=h_{1}^{*}(P).$

Daneben sind weitere Abschätzungen bekannt.

Die Koeffizienten des Ehrhart-Polynoms können hingegen rational und auch negativ sein, aus der Ganzheit der Koeffizienten des $h^{*}$-Polynoms folgt aber zumindest, dass die Nenner der Koeffizienten des Ehrhart-Polynoms $d!$ teilen.

Abschätzungen https://arxiv.org/pdf/math/0402148.pdf https://arxiv.org/abs/0710.2665 https://arxiv.org/pdf/0904.3035.pdf

Spezielle Familien von Polytopen

Ehrhart positivity and unimodularity ?

https://arxiv.org/pdf/1804.08258.pdf https://arxiv.org/pdf/1505.07377.pdf https://arxiv.org/pdf/1711.09962.pdf

Reflexive Polytop (Hibi), Zonotope, Birkhoff-Polytop (https://arxiv.org/abs/math/0202267)

Beispiele

Figurierte Zahlen

Standardgittersimplex

Für den $2$-dimensionalen Standardsimplex $\Delta _{2}=conv((0,0),(1,0)(0,1))$ ergibt sich die Anzahl der Gitterpunkte in $t\cdot \Delta _{2}$ als Summe der ersten $t+1$ natürlichen Zahlen, also als die Dreieckszahl ${\frac {(t+1)(t+2)}{2}}={\binom {t+2}{2}}$.

Für den $3$-dimensionalen Standardsimplex $\Delta _{3}=conv((0,0,0),(1,0,0)(0,1,0),(0,0,1)$ bestimmt man die Anzahl der Gitterpunkte in $t\cdot \Delta _{3}$ als Summe der Dreieckszahlen ${\binom {2+2}{2}},\dotsc ,{\binom {t+2}{2}}$ und erhält damit die Tetraederzahl ${\binom {t+3}{3}}$.

Allgemein ergeben sich also rekursiv die $d+1$-dimensionalen Simplexzahlen und somit für den $d+1$-dimensionalen Standardsimplex $\Delta _{d}=conv(0,e_{1},\dotsc ,e_{d+1})$

${\text{ehr}}_{\Delta _{d+1}}(t)=\sum _{n=0}^{t}{\text{ehr}}_{\Delta _{d}}(n)=\sum _{n=0}^{t}{\binom {d+n}{d}}={\binom {(d+1)+t}{d+1}}.$

Da die Standardsimplizes stehts als normiertes Volumen $1$ haben, gilt

$1=d!vol(\Delta _{d})=\sum _{i=0}^{d}h_{i}^{*}(\Delta _{d})$

und damit wegen der Nicht-Negativität der $h_{i}^{*}$ und $h_{0}^{*}=1$ bereits

$h_{\Delta _{d}}^{*}=1.$

Insbesondere gilt also ${\text{deg}}(\Delta _{d})=0$ und $(d+1)\Delta _{d}$ ist das kleiste ganzzahlige Vielfache von $\Delta _{d}$, das einen inneren Gitterpunkt enthält.

Einheitswürfel

Für den $2$-dimensionalen Einheitswürfel $[0,1]^{2}$ erhalten wir für die Anzahl der Gitterpunkte in $t\cdot [0,1]^{2}$ die Quadratzahlen $(t+1)^{2}$ und entsprechend für den $3$-dimensionalen Einheitswürfel $[0,1]^{3}$ in $t\cdot [0,1]^{2}$ die Kubikzahlen $(t+1)^{3}$ als Anzahl der Gitterpunkte.

Allgemein erhalten wir also für den $d$-dimensionalen Einheitswürfel

${\text{ehr}}_{[0,1]^{d}}(t)=(t+1)^{d}.$

Es gilt ${\text{deg}}([0,1]^{d})=d-1$ und als Koeffizienten des $h^{*}$-Polynoms ergeben sich die Eulerschen Zahlen.

Satz von Pick

Für ein zweidimensionales ganzzahliges Polytop $P$ können sowohl das Ehrhart- als auch das $h^{*}$-Polynom aufgrund der allgemeinen Charakterisierungen der Koeffizienten explizit angegeben werden. Bezeichnet $\partial P$ den Rand von $P$, so gilt

${\text{ehr}}_{P}(t)={\text{vol}}(P)t^{2}+{\frac {1}{2}}|\partial P\cap \mathbb {Z} ^{2}|t+1$

und

$h_{P}^{*}(t)=|{\text{int}}(P)\cap \mathbb {Z} ^{2}|t^{2}+(|P\cap \mathbb {Z} ^{2}|-3)t+1.$

Insbesondere ergibt sich

${\text{vol}}(P)={\frac {1}{2!}}\cdot h_{P}^{*}(1)={\frac {1}{2}}|{\text{int}}(P)\cap \mathbb {Z} ^{2}|+{\frac {1}{2}}|P\cap \mathbb {Z} ^{2}|-1=|{\text{int}}(P)\cap \mathbb {Z} ^{2}|+{\frac {1}{2}}|\partial P\cap \mathbb {Z} ^{2}|-1,$

was gerade die Aussage des Satzes von Pick ist.

Dass die Anzahl der inneren Punkte und der Randpunkte für $\dim P>2$ nicht mehr ausreicht um das Volumen zu bestimmen und sich somit der Satz von Pick nur in Dimension $2$ gilt, zeigt sich anschaulich an den sogenannten Reeve Tetraedern $\tau _{r}$, die für eine positive ganze Zahl $r$ als konvexen Hülle von $(0,0,0),(1,0,0),(0,1,0),(1,1,r)$ gegeben sind. Es gilt nämlich $|{\text{int}}(\tau _{r})\cap \mathbb {Z} ^{3}|=0$ und $|\partial \tau _{r}\cap \mathbb {Z} ^{3}|=4$, während das Volumen ${\text{vol}}(\tau _{r}(n))={\frac {n}{6}}$ beliebig große Werte annehmen kann.

Mit Hilfe des Leitkoeffizienten des Ehrhart-Polynoms erhält man aber als Verallgemeinerung des Satzes von Pick weiterhin die Möglichkeit das Volumen zu bestimmen, wenn die Anzahl der Gitterpunkte, inneren Gitterpunkte oder der Randpunkte in ausreichend vielen ganzzahligen Vielfachen des Polytops bekannt sind.

Berechnung

Da das Ehrhartpolynom ein Polynom von Grad $d$ ist, kann es als Interpolationspolynom bestimmt werden, sobald $d+1$ Werte bekannt sind. Da die ganzzahligen Werte aber als Anzahl der Gitterpunkte bzw. inneren Gitterpunkte in entsprechenden ganzzahligen Vielfachen des Polytops bestimmt werden können, ist die effiziente Berechnung des Ehrhartpolynoms möglich, wenn effizient Gitterpunkte gezählt werden können. Dies ist aber durch Algorithmen von Alexander Barvinok in jeder Dimension in polynomialer Laufzeit möglich. In spezialisierten Computeralgebrasystemen wie etwa polymake sind die entsprechenden Algorithmen verfügbar.

Verallgemeinerungen

Mehrdimensional ?

https://arxiv.org/abs/math/0111331 https://www.math.uni-frankfurt.de/~theobald/publications/mixedehrhart3.pdf

Zusammenhänge mit anderen Gebieten

torische Geometrie voting theory https://link.springer.com/content/pdf/10.1007/s00355-007-0236-1.pdf

Literatur

Monographien

• Matthias Beck, Sinai Robins: Computing the Continuous Discretely. Integer-Point Enumeration in Polyhedra (= Undergraduate Texts in Mathematics). 2. Auflage. Springer, New York 2015, ISBN 978-1-4939-2968-9, doi:10.1007/978-1-4939-2969-6.  (PDF Version 2009 auf math.sfsu.edu/beck)
• Matthias Beck, Sinai Robins: Das Kontinuum diskret berechnen. Springer, Berlin/Heidelberg 2008, ISBN 978-3-540-79595-7, doi:10.1007/978-3-540-79596-4 (Originaltitel: Computing the Continuous Discretely. Übersetzt von Kord Eickmeyer). 
• Eugène Ehrhart: Polynômes arithmétiques et méthode des polyèdres en combinatoire (= International Series of Numerical Mathematics. Band 35). Birkhäuser Verlag, Basel 1977, ISBN 978-3-7643-0872-8. 

In Lehrbüchern zu allgemeineren Themen

• Alexander Barvinok: Lattice points and lattice polytopes. In: Jacob E. Goodman, Joseph O'Rourke, Csaba D. Tóth (Hrsg.): Handbook of Discrete and Computational Geometry. 3. Auflage. CNC Press, Boca Raton 2017, ISBN 978-1-4987-1139-5, S. 185–210.  (Preliminary PDF Version auf csun.edu/~ctoth) Kapitel 7.4
• Richard P. Stanley: Enumerative Combinatorics. Volume I. 2. Auflage. ‎ Cambridge University Press, New York 2012, ISBN 978-1-107-60262-5.  (PDF Version 2011 auf math.mit.edu/~rstan) Kapitel 4.6
• Ezra Miller, Bernd Sturmfels: Combinatorial Commutative Algebra (= Graduate Studies in Mathematics. Band 227). Springer, New York 2005, ISBN 978-0-387-22356-8, doi:10.1007/b138602.  Kapitel 12
• Alexander Barvinok: A Course in Convexity (= Graduate Studies in Mathematics. Band 54). AMS, Providence, Rhode Island 2002, ISBN 978-0-8218-2968-4.  Kapitel 8
• Günter Ewald: Combinatorial Convexity and Algebraic Geometry (= Graduate Texts in Mathematics. Band 168). Springer, New York 1996, ISBN 978-0-387-94755-6, doi:10.1007/978-1-4612-4044-0.  Kapitel IV.6

Vorlesungsskripte

• Christian Haase, Benjamin Nill, Andreas Paffenholz: Lecture Notes on Lattice Polytopes. 2020, mathematik.tu-darmstadt.de/~paffenholz

Originalpublikationen

• Eugène Ehrhart: Sur les polyèdres rationnels homothétiques à n dimensions. C. R. Acad. Sci. Paris 254, 1962, S. 616–618, bnf online.
• Ian G. MacDonald: Polynomials Associated with Finite Cell-Complexes. Journal of the London Mathematical Society, Volume s2-4, Issue 1, Juli 1971, S. 181–192,online
• Richard P. Stanley: Decompositions of rational convex polytopes. Annals of Discrete Mathematics 6, 1980, S. 333-343, online
• Richard P. Stanley: A Monotonicity Property of $h$-vectors and $h^{*}$-vectors. Europ. J. Combinatorics, 1993, 14, S. 251-258, online