9. Übung Elementare Algorithmen in der Algebra

Priv. Doz. Dr. G. Nebe (SS 00)

Aufgabe 33. Bestimmen Sie die Kettenbruchentwicklung von \frac{243}{89} und vergleichen Sie die Schritte mit denen im Euklidischen Algorithmus. Bestimmen Sie die Kettenbruchentwicklung von \sqrt{5}. Berechnen Sie den Wert von

2 + \frac{1|}{|1} + \frac{1|}{|2} + \frac{1|}{|1} + \frac{1|}{|1} + \frac{1|}{|4} + \frac{1|}{|1} + \frac{1|}{|1} + \frac{1|}{|6}.

Aufgabe 34. Beweisen Sie Satz 7.24 aus der Vorlesung.

Aufgabe 35. Formulieren Sie den Algorithmus CFRAC (Algorithmus 7.27). Dabei können Sie den Gauss Algorithmus zum Berechnen von Kernen von Matrizen über 𝔽_{2} benutzen. Eine MAPLE-Implementation ist nicht erforderlich.

Aufgabe 36. Sei f = 2x^{4}y^{5} + 3x^{5}y^{2} + x^{3}y^{9} ∈ ℚ[x, y]. Zeigen Sie, dass es keine Monomordnung gibt, für die lt(f) = 2x^{4}y^{5} ist.

Aufgabe 37. Ein Polynom f ∈ K[x_{1}, …, x_{n}] heißt symmetrisch, falls es invariant ist unter allen Permutationen der Variablen x_{1}, …, x_{n}. σ_{1} := x_{1} + x_{2} + … + x_{n}, σ_{2} := x_{1}x_{2} + x_{1}x_{3} + … + x_{n−1}x_{n}, …, σ_{n} := x_{1}x_{2} … x_{n} sind symmetrische Polynome und heißen die elementarsymmetrischen Polynome. Zeigen Sie: Jedes symmetrische Polynom f ∈ K[x_{1}, …, x_{n}] mit f(0, …, 0) = 0 ist ein Polynom in den σ_{1}, …, σ_{n}. Im Fall n = 2, schreiben Sie x_{1}^{4} + x_{2}^{4} als Polynom in σ_{1} = x_{1} + x_{2} und σ_{2} = x_{1}x_{2}. Hinweis: Rechnen Sie mit der lexikographischen Ordnung mit x_{1} > … > x_{n}.

(a) Ist f symmetrisch und lt(f) = cx^{α} mit α = (α_{1}, …, α_{n}), so ist α_{1} ≥ α_{2} ≥ … ≥ α_{n}.

(b) g := σ_{1}^{α_{1}−α_{2}}σ_{2}^{α_{2}−α_{3}} ⋯ σ_{n−1}^{α_{n−1}−α_{n}}σ_{n}^{α_{n}} erfüllt lt(g) = x^{α}.

(c) lm(f − cg) < lm(f), f − cg ist symmetrisch, also folgt die Behauptung mit Induktion.

Die Vorlesung von Dienstag, 4.7. wird auf Montag 3.7., 13.15-14.45 im R140 verlegt.

zusätzliche Literatur zu Gröbnerbasen: W. W. Adams, P. Loustaunau: An introduction to Gröbner bases. AMS graduate studies in math. 3 (1994)

Abgabe: Donnerstag, den 6.7.00, in der Übung 12:30 Uhr im kl. physik. Hörsaal