Prof. Dr. Martin Kreuzer WS 2000/2001 Fachbereich Mathematik Universität Bayreuth

Übungen zur Vorlesung

Praktische Anwendungen der Computeralgebra

Blatt 3

Abgabetermin: Mi, 20.12.2000

Aufgabe 11: Gegeben seien das vollständige Design 𝔻 = {(i, j) | i, j ∈ {−1, 0, 1}} in ℚ^{2} und die Teilmenge 𝔽 = {(0, 0), (0, −1), (1, 0), (1, 1), (−1, 1)} ⊆ 𝔻.

a) Zeigen Sie, daß die Restklassen der Terme aus O = {1, x, y, x^{2}, y^{2}} eine ℚ-Basis von ℚ[x, y]/I_{𝔽} bilden. Hinweis: Die Auswertungsmatrix von O in 𝔽 ist invertierbar.

b) Beweisen Sie, daß die Menge O nicht von der Form 𝕋^{2} \ LT_{σ}(I_{𝔽}) ist. Hinweis: Betrachten Sie das Polynom f = x^{2} + xy − x − \frac{1}{2}y^{2} − \frac{1}{2}y.

Aufgabe 12: Sei K ein Körper, sei P = K[x_{1}, …, x_{n}], und seien f_{1}, …, f_{s} ∈ P. Zeigen Sie, daß für jedes Ideal I ⊆ P gilt

I : (f_{1} ⋯ f_{s})^{∞} = (⋯ ((I : (f_{1})^{∞}) : (f_{2})^{∞}) ⋯) : (f_{s})^{∞}

Aufgabe 13: Sei K ein Körper, P = K[x_{1}, …, x_{n}], und seien f_{1}, …, f_{s}, g_{1}, …, g_{t} ∈ P. Ferner sei J ⊆ P ein Ideal, das das Polynom f_{1} ⋯ f_{s} − g_{1} ⋯ g_{t} enthalte. Beweisen Sie die Formel

J : (f_{1} ⋯ f_{s} · g_{1} ⋯ g_{t})^{∞} = J : (f_{1} ⋯ f_{s})^{∞}

Aufgabe 14: Schreiben Sie eine CoCoA-Funktion DioSysSolve(…), die als Eingabe eine Matrix A ∈ Mat_{m,n}(ℕ) und einen Vektor b ∈ ℕ^{n} erwartet. Die Funktion soll zuerst prüfen, ob das Diophantische Gleichungssystem S : A · (z_{1}, …, z_{n})^{transp.} = b lösbar ist und in diesem Fall dann eine Lösung von S berechnen.

Wenden Sie Ihre Funktion DioSysSolve(…) in folgenden Fällen an:

a) ( \begin{matrix}3 & 1 & 11 & 2 & 3 \\ 4 & 5 & 0 & 1 & 7 \\ 5 & 6 & 1 & 9 & 2 \end{matrix} ) ( z_{1} ; ⋮ ; z_{5} ) = ( \begin{matrix}20 \\ 17 \\ 23 \end{matrix} )

b) ( \begin{matrix}3 & 1 & 11 & 2 & 3 \\ 4 & 5 & 0 & 1 & 7 \\ 5 & 6 & 1 & 9 & 2 \end{matrix} ) ( z_{1} ; ⋮ ; z_{5} ) = ( \begin{matrix}20 \\ 17 \\ 21 \end{matrix} )

c) ( \begin{matrix}3 & 1 & 11 & 2 & 3 & 5 & 3 \\ 4 & 5 & 0 & 1 & 7 & 4 & 6 \\ 5 & 6 & 1 & 9 & 2 & 3 & 3 \end{matrix} ) ( z_{1} ; ⋮ ; z_{7} ) = ( \begin{matrix}31 \\ 27 \\ 38 \end{matrix} )

Aufgabe 15: In der Situation von Aufgabe 14 sei K ein Körper, sei P = K[x_{1}, …, x_{n}], sei Q = K[x_{1}, …, x_{n}, y_{1}, …, y_{m}], und sei J ⊆ Q das von {x_{1} − t_{1}, …, x_{n} − t_{n}} mit t_{i} = y_{1}^{a_{1i}} ⋯ y_{m}^{a_{mi}} erzeugte Ideal.

a) Berechnen Sie das Eliminationsideal I = J ∩ P in den folgenden Fällen mit Hilfe des eingebauten Befehls Elim(…).

1) A_{1} = ( \begin{matrix}3 & 1 & 11 & 2 & 3 & 5 & 3 & 5 \\ 4 & 5 & 0 & 1 & 7 & 4 & 6 & 2 \\ 5 & 6 & 1 & 9 & 2 & 3 & 3 & 1 \end{matrix} )

2) A_{2} = ( \begin{matrix}1 & 4 & 9 & 5 & 8 & 7 & 3 & 3 & 6 & 7 \\ 1 & 6 & 2 & 4 & 4 & 1 & 2 & 4 & 0 & 4 \\ 4 & 3 & 4 & 4 & 3 & 6 & 6 & 5 & 2 & 9 \\ 3 & 1 & 9 & 6 & 9 & 7 & 1 & 9 & 2 & 9 \\ 9 & 7 & 0 & 6 & 3 & 9 & 2 & 0 & 8 & 4 \end{matrix} )

3) A_{3} = ( \begin{matrix}4 & 3 & 3 & 3 & 2 & 2 & 2 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 2 & 1 & 1 & 0 & 0 & 0 & 3 & 2 & 2 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 2 & 1 & 0 & 0 & 1 & 0 & 2 & 1 & 0 & 3 & 2 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 2 & 0 & 0 & 1 & 0 & 1 & 2 & 0 & 1 & 2 & 3 \end{matrix}

\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 3 & 3 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 2 & 0 & 1 & 3 & 2 & 1 & 0 & 4 & 3 & 2 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 2 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 4 \end{matrix} )

b) Verwenden Sie die in CoCoA eingebaute Funktion LinKer(…) sowie die Beschreibung von I als I = I_{L} : (x_{1} ⋯ x_{n})^{∞}, um eine CoCoA-Funktion Toric(…) zu schreiben, die das Ideal I effizient berechnet. Wenden Sie Ihre Funktion in den Fällen von a) an und vergleichen Sie die Timings. Hinweis: Die Funktion LinKer(…) ist nicht deterministisch. Wenden Sie sie mindestens achtmal an, um verschiedene ℤ-Basen von L zu erzeugen.

c) Optimieren Sie ihre Funktion Toric(…), indem Sie die Resultate der Aufgaben 12 und 13 anwenden. Vergleichen Sie die Timings der neuen Funktion ToricOpt(…) wieder in den Fällen von a).