Post on 14-Aug-2020
transcript
Gitterpunkte in konvexen MengenInstitut für Algebra und GeometrieProf. Dr. Martin Henk
Dipl.-Math. Carsten Thiel
Übung 8WS 2011/2012
Aufgabe 8.1 Sei P ⊂ Rn ein Polytop mit P ∩ Zn = vert(P ).Zeigen Sie, dass |vert(P )| ≤ 2n.
Aufgabe 8.2 Sei P ⊂ V ein rationales Polyeder. Zeigen Sie, dass P ∗ eben-falls ein rationales Polyeder ist.
Aufgabe 8.3 Sei u1, . . . , un reduzierte Basis von Λ. Beweisen Sie, dass
�u1� ≤ 2n−1
2 minu∈Λ\{ 0 }
�u� .
Aufgabe 8.4 Seien u1, . . . , un ∈ Zn linear unabhängige Vektoren. Weiterseien K = cone(u1, . . . , un) und
P =�
n�
i=1αiui
����� 0 < αi ≤ 1 für i = 1, . . . , n
�
.
Zeigen Sie, dass
�
w∈int(K)∩Zn
xw =� �
u∈P ∩Zn
xu� n�
i=1
11 − xui
und �
w∈int(K)∩Zn
x−w = (−1)n�
w∈K∩Zn
xw .
Besprechung: 08.12.2011 S. 1/1
Gitterpunkte in konvexen MengenInstitut für Algebra und Geometrie
Prof. Dr. Martin Henk
Dipl.-Math. Carsten Thiel
Übung 7WS 2011/2012
Aufgabe 7.1 Eine Menge S ⊂ V heißt Halbgruppe, falls für alle x, y ∈ Sauch x + y ∈ S gilt. Eine Teilmenge X ⊂ S heißt Erzeugendensystem von S,
falls es zu jedem s ∈ S Elemente x1, . . . , xk ∈ X und Zahlen λ1, . . . , λk ∈ Z≥0gibt, mit
s = λ1x1 + . . . + λkxk .
Beweisen Sie, dass jede Halbgruppe S ⊂ Z ein endliches Erzeugendensystem
hat und finden Sie eine Halbgruppe T ⊂ Z2, die kein endliches Erzeugen-
densystem hat.
Aufgabe 7.2 Sei Λ ⊂ R2ein Gitter. Beweisen Sie, dass es eine Basis u1, u2
von Λ gibt, für die der Winkel zwischen u1 und u2 zwischen 60◦
und 90◦
liegt.
Aufgabe 7.3 Sei Λ ⊂ V ein Gitter. Eine Menge von Vektoren u1, . . . , uk
heißt primitiv, falls sie eine Basis des Gitters
Λ ∩ lin { u1, . . . , uk }
bilden. Beweisen Sie, dass das für Λ = Zngenau dann der Fall ist, wenn
der größte gemeinsame Teiler aller Determinanten von (k × k)-Minoren der
Matrix U = (u1, . . . , uk) genau 1 ist.
Aufgabe 7.4 Seien �1, . . . , �n homogene lineare Formen, gegeben durch
�i(x) = ai1x1 + . . . + ainxn , mit aij ∈ R für 1 ≤ i, j ≤ n .
Sei A = (aij)ij die Matrix dieses Systems und sei det A �= 0. Weiter seien
τi ∈ R>0 für 1 ≤ i ≤ n mit τ1 · τ2 · · · τn ≥ |det A|.Zeigen Sie, dass es ein z ∈ Zn \ { 0 } gibt, mit
|�i(z)| ≤ τi , für 1 ≤ i ≤ n .
Besprechung: 01.12.2011 S. 1/1
Gitterpunkte in konvexen MengenInstitut für Algebra und Geometrie
Prof. Dr. Martin Henk
Dipl.-Math. Carsten Thiel
Übung 6WS 2011/2012
Aufgabe 6.1 Seien P1 und P2 Polyeder in V . Zeigen Sie:
P1 und P2 sind genau dann stark kombinatorisch isomorph, wenn es eine
Bijektion α : vert(P1) → vert(P2) gibt mit fcone(P1, v) = fcone(P2, α(v))
für jede Ecke v ∈ vert(P1).
Aufgabe 6.2 Sei P ⊂ V ein Polytop. Beweisen Sie
�
v∈vert(P )Φ
�[fcone(P, v)]
�= 0 .
Aufgabe 6.3 Drücken Sie das Volumen des Einheitswürfels C = [0, 1]n
in
Rndurch die Formel aus Korollar 8.2 ii) aus.
Aufgabe 6.4 Sei a = (α1, . . . , αn) ∈ Rnein Vektor mit paarweise verschie-
denen Koordinaten und sei P die konvexe Hülle der n! Punkte, die aus adurch Permutationen der Koordinaten hervorgehen.
Beweisen Sie, dass P ein einfaches Polytop der Dimension n − 1 ist, dass in
der affinen Hyperebene
A = { (x1, . . . , xn) ∈ Rn | x1 + . . . + xn = α1 + . . . + αn }
liegt.
Drücken Sie außerdem das Volumen von P als Polytop im (n − 1)-dimensi-
onalen Raum A mit Hilfe der Formel aus Korollar 8.2 ii) aus.
Besprechung: Mittwoch, 23.11.2011 S. 1/1
Gitterpunkte in konvexen MengenInstitut für Algebra und GeometrieProf. Dr. Martin Henk
Dipl.-Math. Carsten Thiel
Übung 5WS 2011/2012
Aufgabe 5.1 Beweisen Sie Satz 6.4.Hinweis: Kombinieren Sie die Beweise von Satz 5.4 und Satz 6.3. BeweisenSie die Aussage zunächst für das Simplex und wenden Sie schließlich einegeeignete Projektion an.
Aufgabe 5.2 Sei P ⊂ V ein unbeschränktes Polyeder der Dimension n, daskeine Gerade enthält. Sei f0
i (P ) die Anzahl der beschränkten i-dimensionalenSeiten von P , sei f∞
i (P ) die Anzahl der unbeschränkten i-dimensionalen Sei-ten von P und sei fi(P ) = f0
i (P )+f∞i (P ) die Gesamtzahl der i-Seiten. (Wir
betrachten P als n-Seite von sich selbst.) Beweisen Sie
n−1�
i=0(−1)if0
i (P ) = 1 ,n�
i=1(−1)i+1f∞
i (P ) = 1 undn�
i=0(−1)ifi(P ) = 0 .
Aufgabe 5.3 Sei P ⊂ V ein Polytop der Dimension n. Beweisen Sie
(−1)n[int P ] =�
F ⊆PSeite
(−1)dim F [F ] .
(Wir betrachten P als Seite von sich selbst.)
Aufgabe 5.4 Sei P ⊂ V ein unbeschränktes Polyeder, das keine Geradeenthält. Beweisen Sie χ([int P ]) = 0.
Besprechung: 17.11.2011 S. 1/1
Gitterpunkte in konvexen MengenInstitut für Algebra und Geometrie
Prof. Dr. Martin Henk
Dipl.-Math. Carsten Thiel
Übung 4WS 2011/2012
Aufgabe 4.1 Wir ersetzen die Funktion Gε aus dem Beweis von Satz 4.3
durch
�G(x, y) =
�1 falls �x, y� ≤ 1,
0 sonst.
Sei �D diejenige Abbildung, die durch
�D(f) = h für h(y) = χ�
�G(x, y)f(x)
�
definiert wird. Beweisen Sie, dass �D : C(V ) → Bild( �D) eine lineare Abbil-
dung ist und berechnen Sie �D([B]), wobei B ⊂ V eine Kugel vom Radius 1
um den Nullpunkt ist.
Aufgabe 4.2 Seien f und g Linearkombinationen von Indikatorfunktionen
polyedrischer Kegel in V . Sei D die Abbildung aus Satz 4.3 iii). Zeigen Sie,
dass D(f · g) = D(f) ∗ D(g).
Aufgabe 4.3 Sei P = { x ∈ V | �i(x) ≤ αi , i ∈ I } und für v ∈ P sei wie
gehabt Iv = { i ∈ I | �i(v) = αi }. Beweisen Sie
tcone(P, v) = { x ∈ V | �i(x) ≤ αi , i ∈ Iv }und
fcone(P, v) = { x ∈ V | �i(x) ≤ 0 , i ∈ Iv } .
Aufgabe 4.4 Sei P ⊂ V , P �= ∅, ein Polyeder, das keine Gerade enthält
und seien Q die konvexe Hülle der Ecken und CP der Rezessionskegel von
P . Beweisen Sie, dass für jede Ecke v von P gilt
tcone(P, v) = tcone(Q, v) + CP .
Aufgabe 4.5 Sei P ⊂ V , P �= ∅, ein Polyeder, das keine Gerade enthält
und sei CP der Rezessionskegel von P . Beweisen Sie, dass�
v∈vert(P )[fcone(P, v)] ≡ [CP ] modulo Polyeder mit Geraden.
Aufgabe 4.6 Sei P ⊆ V ein Polyeder, F ⊆ P eine Seite von P und sei
v ∈ rel int(F ). Beweisen Sie, dass tcone(P, v) und fcone(P, v) nicht von der
Wahl von v abhängen.
Man kann also von Tangentenkegel tcone(P, F ) und Kegel der zulässigenRichtungen fcone(P, F ) einer Seite F von P sprechen.
Besprechung: Dienstag, 08.11.2011 S. 1/1
Gitterpunkte in konvexen MengenInstitut für Algebra und GeometrieProf. Dr. Martin Henk
Dipl.-Math. Carsten Thiel
Übung 3WS 2011/2012
Aufgabe 3.1 Seien P1, P2 ⊆ V nicht-leere Polyeder und sei Q = P1 + P2ihre Minkowski-Summe. Beweisen Sie, dass jede Seite F von Q in der FormF = G + H geschrieben werden kann, wobei G Seite von P1 und H Seitevon P2 ist.
Aufgabe 3.2 Seien P1, P2 ⊆ V nicht-leere Polyeder und sei Q = P1 ∩ P2.Beweisen Sie, dass jede Ecke v von Q in der Form v = F1 ∩ F2, geschriebenwerden kann, wobei Fi Seite von Pi ist und dim F1 + dim F2 ≤ dim V .
Aufgabe 3.3 (Satz von Birkhoff–von Neumann) Im Raum der n × n Ma-trizen X = (xij) sei P die Menge derjenigen Matrizen, die die Gleichungen
n�
j=1xij = 1 für i = 1, . . . , n und
n�
i=1xij = 1 für j = 1, . . . , n
sowie die Ungleichungen
xij ≥ 0 für alle i, j
erfüllen. Beweisen Sie, dass P ein Polytop der Dimension (n − 1)2 ist unddass dessen Ecken genau die Permutationsmatrizen X sind, die genau einenEintrag „1“ und n − 1 Einträge „0“ in jeder Zeile und jeder Spalte haben.Hinweis: Beweisen Sie, dass unter den Einträgen jeder Ecke von P mindes-tens (n − 1)2 Nullen auftreten.
Aufgabe 3.4 Seien r1, . . . , rm und c1, . . . , cn positive ganze Zahlen mitm�
i=1ri =
n�
j=1cj .
Im Raum der m × n Matrizen X = (xij) betrachten wir das Transportati-
onspolytop P , bestehend aus denjenigen Matrizen, die die Gleichungenn�
j=1xij = ri für i = 1, . . . , m und
m�
i=1xij = cj für j = 1, . . . , n
sowie die Ungleichungen
xij ≥ 0 für alle i, j
erfüllen. Beweisen Sie, dass eine Ecke X von P nur ganze Einträge hat.
Besprechung: 03.11.2011 S. 1/1
Gitterpunkte in konvexen MengenInstitut für Algebra und GeometrieProf. Dr. Martin Henk
Dipl.-Math. Carsten Thiel
Übung 2WS 2011/2012
Aufgabe 2.1 Finden Sie Beispiele für abgeschlossene konvexe MengenA, B, C ⊆ V und eine lineare Transformation T : V → W , sodass
T (A) und B + C
nicht abgeschlossen sind.
Aufgabe 2.2 Seien V und W Vektorräume und T : V → W eine lineareAbildung und sei �T : P(V ) → P(W ) wie in Satz 2.2.Zeigen Sie, dass �T (f ∗ g) = �T (f) ∗ �T (g).
Aufgabe 2.3 Sei I := { (ξ1, ξ2) | 0 ≤ ξ1, ξ2 ≤ 1 } das Quadrat in der Ebene.Zeigen Sie, dass
[I] ∗ [− int I] = [0]gilt, wobei − int I = { (ξ1, ξ2) | −1 < ξ1, ξ2 < 0 }.
Aufgabe 2.4 Zeigen Sie, dass die Indikatorfunktion [P ] eines unbeschränk-ten Polyeders P ⊆ V ein Nullteiler ist, d. h. finden Sie ein f ∈ P(V ) mitf ∗ [P ] = 0.
Aufgabe 2.5 Wie viele Seiten hat der d-dimensionale Würfel
C = { (ξ1, . . . , ξd) | 0 ≤ ξi ≤ 1 für i = 1, . . . , d } ?
Besprechung: 27.10.2011 S. 1/1
Gitterpunkte in konvexen MengenInstitut für Algebra und GeometrieProf. Dr. Martin Henk
Dipl.-Math. Carsten Thiel
Übung 1WS 2011/2012
Aufgabe 1.1 Seien a und b teilerfremde positive Zahlen und sei
S := { m1a + m2b | m1, m2 ∈ Z+ }
die Menge der Linearkombinationen von a und b mit nicht-negativen Koef-fizienten. Zeigen Sie, dass
�
m∈S
xm = 1 − xab
(1 − xa)(1 − xb) für |x| < 1 .
Geben Sie eine Interpretation der Formel
11 − x
− 1 − xab
(1 − xa)(1 − xb)und vereinfachen Sie diese für a = 3 und b = 7.
Aufgabe 1.2 Sei P ⊂ R2 ein allgemeines Gitterpolygon, also die Vereini-gung von endlichen vielen einfachen Gitterpolygonen die selbst Gitterpoly-gon ist. Beweisen Sie zunächst die kombinatorische Eulercharakteristik
χ(P ) = F − E + V ,
dabei F die Zahl der Flächen, E die der Kanten und V die der Ecken.Beweisen Sie dann den Satz von Pick
vol(P ) = G(int P ) + 12 G(bd P ) − χ(P ) .
Aufgabe 1.3 Beweisen Sie die Inklusions-Exklusions-Formel�
n�
i=1Xi
�
=�
I⊂{ 1,...,n }I �=∅
(−1)|I|−1�
�
i∈I
Xi
�
für Mengen Xi ⊂ V , i = 1, . . . , n.
Aufgabe 1.4 Sei
C := { (ξ1, . . . , ξd) | 0 < ξi < 1 für i = 1, . . . , d }
der offene d-dimensionale Würfel im Rd.Zeigen Sie [C] ∈ P(Rd) und χ([C]) = (−1)d.
Besprechung: 20.10.2011 S. 1/1