Title (eng)
Counting integral points in polytopes
Parallel title (deu)
Das Zählen von Gitterpunkten in Polytopen
Author
Liselotte Tschepen
Advisor
Ilse Fischer
Assessor
Ilse Fischer
Abstract (deu)
Probleme, die sich durch das Zählen von ganzzahligen Punkten in Polytopen lösen lassen, treten in
den unterschiedlichsten mathematischen Gebieten auf. Es ist das Anliegen der vorliegenden Arbeit, einige Methoden darzustellen, mit denen diesen Abzählproblemen begegnet werden kann.
Die ersten Untersuchungen, die sich dezidiert mit dem Abzählen von ganzzahligen Punkten in Polytopen auseinandersetzen, finden sich in Arbeiten von Eug\`{e}ne Ehrhart aus den 1960er Jahren. Ehrhart betrachtete Streckungen von rationalen Polytopen um einen positiven ganzzahligen Faktor. Dabei entdeckte er, dass die Anzahl der ganzzahligen Punkte in diesen Streckungen durch ein Quasi-Polynom im Streckungsfaktor berechnet werden kann. Während wir uns im ersten Kapitel mit einer kurzen Einführung in die Polytoptheorie begnügen, die als Grundlage für die weiteren Betrachtungen dienen soll, wenden wir uns im Anschluss eingehend der Ehrhart-Theorie zu und liefern eine Darstellung ihrer wichtigsten Resultate.
Unter einem allgemeineren Blickwinkel kann man die Anzahl der ganzzahligen Punkte in Polytopen betrachten, die durch unabhängige Parallelverschiebung der Randflächen eines Polytops entstehen. Mit Hilfe der Theorie von "vector partition functions" lassen sich die Resultate der Ehrhart-Theorie für diese Polytope verallgemeinern.
Vor dem Hintergrund der Arbeit von Wolfgang Dahmen und Charles A. Micchelli \cite{DM} die im Zuge ihrer Untersuchungen von "box splines" auf "vector partition functions" gestoßen sind, führen wir im dritten Kapitel einen elementaren Beweis für eine Verallgemeinerung von Ehrharts Satz. Während der Ansatz von Dahmen und Micchelli auf den Eigenschaften von splines beruht, fußt unser Beweis auf geometrischen Betrachtungen und macht sich die Eigenschaften von Polytopen zunutze.
Mit diesen Mitteln können wir schließlich eine stärkere Version des Satzes aus \cite{DM} beweisen. Diese Variante wurde bereits von Andr\'{a}s Szenes und Mich\`{e}le Vergne in \cite{vergne} mit Hilfe von Methoden der Komplexen Analysis gezeigt.
Abstract (eng)
Problems that may be approached by counting integral points in polytopes occur in many mathematical fields. It is the objective of the present thesis to provide methods that enable us to face these problems.
The first attempts that explicitly dealt with the issue of counting integral points in polytopes were made by Eug\`{e}ne Ehrhart in the 1960s. Ehrhart concerned himself with integral dilations of rational polytopes. In doing so, he discovered that the number of integral points in these dilated polytopes may be computed by a quasi--polynomial in the dilation factor. While we content ourselves with a short introduction to the theory of polytopes in the first chapter we will subsequently engage in a more detailed study on Ehrhart Theory that will provide us with a description of its most important results.
From a more general point of view, it is convenient to examine the number of integral points in polytopes that result from independent parallel motions of the bounding hyperplanes of a given rational polytope. By means of the theory of vector partition functions, it is possible to generalize the results of Ehrhart Theory in order to apply them to this type of problem.
Based on an article of Wolfgang Dahmen and Charles A. Micchelli \cite{DM} who came across vector partition functions in the course of their investigation on box splines, we will establish a proof of a generalization of Ehrhart's Theorem in chapter three. While the approach of Dahmen and Micchelli relies on properties of splines, our proof is based on geometrical considerations and makes use of properties of polytopes.
Eventually, we may, in this wise, provide a proof of a more general version of the theorem given in \cite{DM}. This result has already been achieved by Andr\'{a}s Szenes and Mich\`{e}le Vergne
in \cite{vergne} by means of complex analysis.
Keywords (eng)
integral points in polytopesEhrhart quasi--polynomialvector partition functions
Keywords (deu)
Ganzzahlige Punkte in PolytopenEhrhart Quasi-polynomeVector Partitions Funktionen
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1261362
rdau:P60550 (deu)
9, 132 S. : graph. Darst.
Number of pages
142
Association (deu)
Title (eng)
Counting integral points in polytopes
Parallel title (deu)
Das Zählen von Gitterpunkten in Polytopen
Author
Liselotte Tschepen
Abstract (deu)
Probleme, die sich durch das Zählen von ganzzahligen Punkten in Polytopen lösen lassen, treten in
den unterschiedlichsten mathematischen Gebieten auf. Es ist das Anliegen der vorliegenden Arbeit, einige Methoden darzustellen, mit denen diesen Abzählproblemen begegnet werden kann.
Die ersten Untersuchungen, die sich dezidiert mit dem Abzählen von ganzzahligen Punkten in Polytopen auseinandersetzen, finden sich in Arbeiten von Eug\`{e}ne Ehrhart aus den 1960er Jahren. Ehrhart betrachtete Streckungen von rationalen Polytopen um einen positiven ganzzahligen Faktor. Dabei entdeckte er, dass die Anzahl der ganzzahligen Punkte in diesen Streckungen durch ein Quasi-Polynom im Streckungsfaktor berechnet werden kann. Während wir uns im ersten Kapitel mit einer kurzen Einführung in die Polytoptheorie begnügen, die als Grundlage für die weiteren Betrachtungen dienen soll, wenden wir uns im Anschluss eingehend der Ehrhart-Theorie zu und liefern eine Darstellung ihrer wichtigsten Resultate.
Unter einem allgemeineren Blickwinkel kann man die Anzahl der ganzzahligen Punkte in Polytopen betrachten, die durch unabhängige Parallelverschiebung der Randflächen eines Polytops entstehen. Mit Hilfe der Theorie von "vector partition functions" lassen sich die Resultate der Ehrhart-Theorie für diese Polytope verallgemeinern.
Vor dem Hintergrund der Arbeit von Wolfgang Dahmen und Charles A. Micchelli \cite{DM} die im Zuge ihrer Untersuchungen von "box splines" auf "vector partition functions" gestoßen sind, führen wir im dritten Kapitel einen elementaren Beweis für eine Verallgemeinerung von Ehrharts Satz. Während der Ansatz von Dahmen und Micchelli auf den Eigenschaften von splines beruht, fußt unser Beweis auf geometrischen Betrachtungen und macht sich die Eigenschaften von Polytopen zunutze.
Mit diesen Mitteln können wir schließlich eine stärkere Version des Satzes aus \cite{DM} beweisen. Diese Variante wurde bereits von Andr\'{a}s Szenes und Mich\`{e}le Vergne in \cite{vergne} mit Hilfe von Methoden der Komplexen Analysis gezeigt.
Abstract (eng)
Problems that may be approached by counting integral points in polytopes occur in many mathematical fields. It is the objective of the present thesis to provide methods that enable us to face these problems.
The first attempts that explicitly dealt with the issue of counting integral points in polytopes were made by Eug\`{e}ne Ehrhart in the 1960s. Ehrhart concerned himself with integral dilations of rational polytopes. In doing so, he discovered that the number of integral points in these dilated polytopes may be computed by a quasi--polynomial in the dilation factor. While we content ourselves with a short introduction to the theory of polytopes in the first chapter we will subsequently engage in a more detailed study on Ehrhart Theory that will provide us with a description of its most important results.
From a more general point of view, it is convenient to examine the number of integral points in polytopes that result from independent parallel motions of the bounding hyperplanes of a given rational polytope. By means of the theory of vector partition functions, it is possible to generalize the results of Ehrhart Theory in order to apply them to this type of problem.
Based on an article of Wolfgang Dahmen and Charles A. Micchelli \cite{DM} who came across vector partition functions in the course of their investigation on box splines, we will establish a proof of a generalization of Ehrhart's Theorem in chapter three. While the approach of Dahmen and Micchelli relies on properties of splines, our proof is based on geometrical considerations and makes use of properties of polytopes.
Eventually, we may, in this wise, provide a proof of a more general version of the theorem given in \cite{DM}. This result has already been achieved by Andr\'{a}s Szenes and Mich\`{e}le Vergne
in \cite{vergne} by means of complex analysis.
Keywords (eng)
integral points in polytopesEhrhart quasi--polynomialvector partition functions
Keywords (deu)
Ganzzahlige Punkte in PolytopenEhrhart Quasi-polynomeVector Partitions Funktionen
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1261363
Number of pages
142
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0