Benutzer:SigmaB/Ehrhart-Theorie

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen


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[1] 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 -Polynom als Zählerpolynom der rationalen Funktion, welche der Ehrhart-Reihe zuordnen werden kann, untersucht.

Für ein Polytop kann das Volumen als Grenzwert diskreter Volumnina bestimmt werden, die sich durch betrachten des Polytops im Gitter ergeben. Durch Verschiebungen der abgeschlossenen Grundmasche um Gittervektoren ergibt sich nämlich eine Parketierung des durch Hyperwürfel der Kantenlänge 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

wobei mit die Anzahl der Elemente der Menge bezeichnet wurde.

Ist ein ganzzahliges Polytop der Dimension , d.h. ein Polytop dessen Eckpunkte in liegen und dessen affine Hülle ein -dimensionaler affiner Unterraum ist, dann ist die Gitterpunktzählfunktion für die Gitterpunkte in ganzzahligen Vielfachen von durch eine Polynomfunktion vom Grad gegeben.[2][3] Es gibt also ein Polynom , sodass für alle gilt, und wird als Ehrhart-Polynom von bezeichnet.

Als Ehrhart-Reihe von bezeichnen wir die erzeugende Funktion des Ehrhart-Polynoms, also die formale Potenzreihe .

Als ganzwertiges Polynom hat das Ehrhart-Polynom eine eindeutige Darstellung als ganzzahlige Linearkombination der Binomialkoeffizienten

und es gibt somit ganzen Zahlen , sodass

Für ergibt sich

Das Polytop wird als -Polynom des ganzzahligen Polytops bezeichnet.[4] Der Grad des -Polynom wird auch als Grad von bezeichnet, wofür im Folgenden geschrieben wird.[5]

Koeffizienten und Werte des Ehrhart- und des -Polynoms

[Bearbeiten | Quelltext bearbeiten]

Das Ehrhart-Polynom ist ein ganzwertiges Polynom von Grad . Damit ergibt sich für ein volldimensionales Polytop mit den Überlegungen in der Motivation das Volumen als Leitkoeffizient des Ehrhart-Polynoms. Ist nicht volldimensional, so erhält man als Leitkoeffizient das vom entsprechenden Untergitter induzierte Volumen.[6]

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.[7]

Wegen

erhält man das Absolutglied des Ehrhart-Polynoms als und außerdem .[8] Ebenso ergibt sich damit aus dem Leitkoeffizienten des Ehrhart-Polynoms das normalisierte Volumen als Wert des -Polynoms in , also

.[9]

Gilt , so erhalten für das Ehrhartpolynom die Nullstellen

[10]

Ehrhart-Macdonald Reziprozität

[Bearbeiten | Quelltext bearbeiten]

Die Ehrhart-Macdonald Reziprozität liefert eine Interpretation für die Werte des Ehrhartpolynoms für negative ganze Zahlen. Ist nämlich ein -dimensionales ganzzahliges Polytop mit Ehrhart-Polynom und wird mit das Innere eines Polytops bezeichnet, so gilt für negative ganze Zahlen

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.[11][12]

Insbesondere folgt für den Leitkoeffizienten des -Polynoms

und ist die kleinste ganze Zahl, sodass einen inneren Gitterpunkt hat.

Abschätzungen für Koeffizienten

[Bearbeiten | Quelltext bearbeiten]

Die Koeffizienten des -Polynoms sind nicht-negative ganze Zahlen.[13][14] Diese Abschätzung von Stanley ergibt sich auch als Spezialfall einer ebenfalls von Stanley bewiesenen Monotonieaussage[15] für das -Polynom zweier unterschiedlicher Polytope. Es gilt nämlich für Gitterpolytope stets koeffizientenweise

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

Daneben sind weitere Abschätzungen bekannt.[16]

Die Koeffizienten des Ehrhart-Polynoms können hingegen rational und auch negativ sein, aus der Ganzheit der Koeffizienten des -Polynoms folgt aber zumindest, dass die Nenner der Koeffizienten des Ehrhart-Polynoms 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

[Bearbeiten | Quelltext bearbeiten]

Ehrhart positivity and unimodularity ?

[Bearbeiten | Quelltext bearbeiten]

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)

Figurierte Zahlen

[Bearbeiten | Quelltext bearbeiten]

Standardgittersimplex

[Bearbeiten | Quelltext bearbeiten]

Für den -dimensionalen Standardsimplex ergibt sich die Anzahl der Gitterpunkte in als Summe der ersten natürlichen Zahlen, also als die Dreieckszahl .

Für den -dimensionalen Standardsimplex bestimmt man die Anzahl der Gitterpunkte in als Summe der Dreieckszahlen und erhält damit die Tetraederzahl .

Allgemein ergeben sich also rekursiv die -dimensionalen Simplexzahlen und somit für den -dimensionalen Standardsimplex

Da die Standardsimplizes stehts als normiertes Volumen haben, gilt

und damit wegen der Nicht-Negativität der und bereits

Insbesondere gilt also und ist das kleiste ganzzahlige Vielfache von , das einen inneren Gitterpunkt enthält.

Einheitswürfel

[Bearbeiten | Quelltext bearbeiten]

Für den -dimensionalen Einheitswürfel erhalten wir für die Anzahl der Gitterpunkte in die Quadratzahlen und entsprechend für den -dimensionalen Einheitswürfel in die Kubikzahlen als Anzahl der Gitterpunkte.

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

Es gilt und als Koeffizienten des -Polynoms ergeben sich die Eulerschen Zahlen.[17]

Für ein zweidimensionales ganzzahliges Polytop können sowohl das Ehrhart- als auch das -Polynom aufgrund der allgemeinen Charakterisierungen der Koeffizienten explizit angegeben werden. Bezeichnet den Rand von , so gilt

und

Insbesondere ergibt sich

was gerade die Aussage des Satzes von Pick ist.

Dass die Anzahl der inneren Punkte und der Randpunkte für nicht mehr ausreicht um das Volumen zu bestimmen und sich somit der Satz von Pick nur in Dimension gilt, zeigt sich anschaulich an den sogenannten Reeve Tetraedern , die für eine positive ganze Zahl als konvexen Hülle von gegeben sind. Es gilt nämlich und , während das Volumen 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.

Da das Ehrhartpolynom ein Polynom von Grad ist, kann es als Interpolationspolynom bestimmt werden, sobald 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.[18][19] In spezialisierten Computeralgebrasystemen wie etwa polymake sind die entsprechenden Algorithmen verfügbar.[20]

Verallgemeinerungen

[Bearbeiten | Quelltext bearbeiten]

Ehrhart-Theorie für rationale Polytope

[Bearbeiten | Quelltext bearbeiten]

Kommutative Algebra

[Bearbeiten | Quelltext bearbeiten]

Mehrdimensional ?

[Bearbeiten | Quelltext bearbeiten]

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

Zusammenhänge mit anderen Gebieten

[Bearbeiten | Quelltext bearbeiten]

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

In Lehrbüchern zu allgemeineren Themen

[Bearbeiten | Quelltext bearbeiten]

Vorlesungsskripte

[Bearbeiten | Quelltext bearbeiten]


Originalpublikationen

[Bearbeiten | Quelltext bearbeiten]
  • 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 -vectors and -vectors. Europ. J. Combinatorics, 1993, 14, S. 251-258, online

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Ehrhart: Sur les polyèdres rationnels homothétiques à n dimensions. 1962, Théorème 1
  2. Ehrhart: Sur les polyèdres rationnels homothétiques à n dimensions. 1962, Théorème 1
  3. Beck, Robins: Computing the Continous Discretly. 2009, Theorem 3.8 (Ehrhart's theorem).
  4. Auch die Bezeichnungen als -Polynom oder -Polynom treten auf.
  5. Beck, Robins: Computing the Continous Discretly. 2009, Theorem 4.5
  6. Beck, Robins: Computing the Continous Discretly. 2009, Corollary 3.20.
  7. Beck, Robins: Computing the Continous Discretly. 2009, Theorem 5.6.
  8. Beck, Robins: Computing the Continous Discretly. 2009, Lemma 3.13. ff.
  9. Beck, Robins: Computing the Continous Discretly. 2009, Lemma 3.21.
  10. Beck, Robins: Computing the Continous Discretly. 2009, Theorem 3.19.
  11. MacDonald: Polynomials Associated with Finite Cell-Complexes. 1971, Theorem 4.6
  12. Beck, Robins: Computing the Continous Discretly. 2009, Theorem 4.1 (Ehrhart-Macdonald reciprocity)
  13. Stanley: Decompositions of rational convex polytopes. 1980, Theorem 2.1.
  14. Beck, Robins: Computing the Continous Discretly. 2009, Theorem 3.12.
  15. Stanley: A Monotonicity Property of -vectors and -vectors. 1993, Theorem 3.3.
  16. Alan Stapledon: Inequalities and Ehrhart -Vectors. Trans. Amer. Math. Soc. 361, 2009, S. 5615-5626.
  17. Beck, Robins: Computing the Continous Discretly. 2009, Theorem 2.1.
  18. Alexander I. Barvinok: A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension Is Fixed. Mathematics of Operations Research, Vol. 19, No. 4 (Nov., 1994), S. 769-779
  19. Alexander I. Barvinok: Computing the Ehrhart Polynomial of a Convex Lattice Polytope. Discrete Comput Geom 12:35,48, 1994, online
  20. Tutorial for Lattice Polytopes. polymake wiki, abgerufen am 14. August 2021.