IdealExtension
Contents
Description
Dieses Modul stellt ideelle Koerper und ideelle Koerpererweiteungen bereit.
Ein ideeller Koerper ist ein Ring, der das Koerperaxiom
fuer alle x gilt: entweder x = 0 oder x ist invertierbar
beinahe erfuellt: Fuer jedes x des ideellen Koerpers gilt entweder x = 0, oder x ist invertierbar, oder aber der ideelle Koerper muss durch einen verfeinerten ideellen Koerper ersetzt werden, in dem dann einer der beiden ersten Faelle eintritt.
Bezueglich endlich vieler Elemente verhaelt sich also ein ideeller Koerper wie ein richtiger Koerper.
Ist beispielsweise z eine algebraische Zahl und p ein normiertes Polynom, welches z als Nullstelle besitzt aber nicht notwendigerweise das Minimalpolynom von z ist, so kann man Q[X]\(p) als ideelle Koerpererweiterung von Q ansehen:
Moechte man ein Element [f] auf Invertierbarkeit testen, muss man den ggT d von f und p betrachten. Ist dieser ein konstantes Polynom, ist [f] invertierbar; ist er assoziiert zu p, so ist f also ein Vielfaches von p, womit [f] = 0 ist; und sonst hat man in d einen echten Faktor von p gefunden.
In diesem Fall muss man p durch diesen Faktor (oder seinem Komplement, falls z nicht Nullstelle von d ist) ersetzen und die Rechnung wiederholen.
Nuetzlich sind ideelle Erweiterungen in folgenden Situationen:
- Wenn (etwa in einem intuitionistischen Kontext) nicht klar ist, dass die Zahl z ein Minimalpolynom besitzt,
- wenn man das Minimalpolynom aus Effizienzgruenden nicht bestimmen moechte oder
- wenn man das Minimalpolynom nur zur Laufzeit als Wert vorliegen hat und es nicht auf Typebene holen moechte. (Ist es statisch bekannt, so sollte man besser das Modul SimpleExtension verwenden, welches richtige, nicht-ideelle Koerpererweiterungen bietet.)
(In Kommentaren notieren wir den Faktorring mit einem umgekehrten Schraegstrich, da sich der richtige Strich nicht vor Haddock verstecken laesst.)
- type Ideal k k' = ReaderT k (Either k')
- runIdeal ∷ Ideal k k' a → k → (k' → k) → a
- restart ∷ k' → Ideal k k' a
- class (Ring a, Monad (Nondet a)) ⇒ IdealField a where
- type Nondet a ∷ * -> *
- idealRecip ∷ a → Nondet a (Maybe a)
- idealEquals ∷ IdealField a ⇒ a → a → Nondet a Bool
- newtype ISE k s = S (Poly k)
- fromBase ∷ k → ISE k s
- adjointedRoot ∷ Field k ⇒ ISE k s
- canonRep ∷ Field k ⇒ ISE k s → Nondet (ISE k s) (Poly k)
- execISE ∷ Field k ⇒ Poly k → (Poly k → Bool) → (∀ s. Nondet (ISE k s) a) → a
- execISEwithAlgebraic ∷ (RingMorphism m, Field (Domain m), HasAnnihilatingPolynomials (Domain m), NormedRing (Domain m), HasMagnitudeZeroTest (Codomain m), PseudoField (Codomain m), HasDenseSubset (Codomain m), NormedRing (DenseSubset (Codomain m)), Field (DenseSubset (Codomain m))) ⇒ Alg m → (∀ s. Nondet (ISE (Domain m) s) a) → a
- demo ∷ IO ()
Monade fuer ideelle Berechnungen
type Ideal k k' = ReaderT k (Either k')
Monade fuer ideelle Berechnungen, also solche, die eine Umgebung vom Typ k benoetigen (in der Anwendung ideeller einfacher Koerpererweiterungen etwa das Moduluspolynom) und entweder ein Ergebnis produzieren oder mit einem Fehler vom Typ k' abbrechen.
Dieser sollte konstruktive Information enthalten, sodass ein Neustart der Berechnung mit einer verfeinerten Umgebung nicht an derselben Stelle abbrechen muss.
runIdeal ∷ Ideal k k' a → k → (k' → k) → a
runIdeal m x0 f laesst die Berechnung m mit der anfaenglichen Umgebung x0 laufen. Bricht diese nicht ab, wird das Ergebnis zurueckgegeben. Wenn sie andernfalls mit einer Fehlerinformation y abbricht, wird sie rekursiv mit der verfeinerten Umgebung f y neugestartet.
Um Terminierung zu gewaehrleisten, sollte f die Umgebung auch tatsaechlich derart verfeinern, dass nur endlich viele Neustarts erforderlich sind.
restart x ist eine Aktion, die zum Abbruch der Berechnung fuehrt und die
uebergebene Information x dem Aufrufer (etwa runIdeal) zur Verfuegung
stellt.
Typklasse fuer ideelle Koerper
class (Ring a, Monad (Nondet a)) ⇒ IdealField a where
Klasse fuer ideelle Koerper a. Das sind Ringe, in denen die Inversenbildung anders als in richtigen Koerpern keine pure Operation mit Rueckgabetyp Maybe a (entweder die Nullheit signalisierend oder das Inverse angebend) ist, sondern Werte in einer Monade annimmt.
Das wichtigste Beispiel ist der Datentyp ISE k s, dessen
idealRecip-Operation Werte in der Ideal-Monade annimmt und so Neustarts
der Berechnung zulaesst.
Methods
idealRecip ∷ a → Nondet a (Maybe a)
idealRecip x bestimmt, ob x entweder null (Rueckgabewert Nothing) oder invertierbar (Rueckgabewert Just y, mit y dem Inversen von x) ist. Falls dazu noetig, duerfen beliebige monadische Aktionen durchgefuehrt werden.
Instances
| Field k ⇒ IdealField (ISE k s) |
idealEquals ∷ IdealField a ⇒ a → a → Nondet a Bool
idealEquals x y bestimmt, ob x und y gleich sind.
Dazu untersuchen wir das Element x - y auf Invertierbarkeit.
Einfache endliche ideelle Koerpererweiterungen
newtype ISE k s
Datentyp fuer die Elemente einer einfachen ideellen Ringerweiterung
k[X]\(p) des Grundrings k. Das dynamische Moduluspolynom p
kann durch ask der Ideal-Monade erfragt werden.
Den Phantomtyp s verwenden wir, um unabsichtliche Vermischungen von Elementen verschiedener ideeller Erweiterungen zu verhindern.
Instances
| (Eq k, Show k, Ring k) ⇒ Show (ISE k s) | |
| HasRationalEmbedding k ⇒ HasRationalEmbedding (ISE k s) | |
| Ring k ⇒ Ring (ISE k s) | |
| Field k ⇒ IdealField (ISE k s) |
adjointedRoot ∷ Field k ⇒ ISE k s
Liefert das Element [X] der ideellen Erweiterung k[X]\(p), also die kuenstliche Nullstelle von p.
canonRep ∷ Field k ⇒ ISE k s → Nondet (ISE k s) (Poly k)
Zu jedem gegebenen Zeitpunkt ist die ideelle Koerpererweiterung ISE k s
ein Faktorring k[X]\(p) modulo eines dynamisch durch restart aenderbaren
Polynoms p.
Diese Funktion bestimmt zu einem Element des Faktorrings seinen kanonischen Repraesentanten mittels Polynomdivision durch das herausgeteilte Polynom.
Nuetzlich ist das beispielsweise dann, wenn man im Koerper Q(x) rechnen moechte, wobei x eine algebraische Zahl ist, von der man nur ein normiertes Polynom f mit f(x) = 0 (nicht aber das Minimalpolynom) kennt.
Ist dann y ein Element dieses Koerpers (dargestellt als Element von ISE k s), so bestimmt canonRep y ein Polynom g derart, dass g(x) = y.
Kanonisch ist dieses Polynom g nur in der Hinsicht, als dass es
bezueglich des aktuell bekannten Moduluspolynoms reduziert wurde. Abhaengig
von zuvor ausgefuehrten Rechnungen in der Ideal-Monade kann dieses aber
ein echter Faktor des Anfangsmodulus f sein.
Arguments
| ∷ Field k | |
| ⇒ Poly k | Startwert fuers Moduluspolynom |
| → (Poly k → Bool) | Funktionen, die zu einem gegebenen Polynom entscheidet, ob es auch als Moduluspolynom verwendet werden koennte |
| → (∀ s. Nondet (ISE k s) a) | die auszufuehrende Berechnung |
| → a | das Ergebnis der (noetigenfalls mehrfach neugestarteten) Berechnung |
Fuehrt eine Berechnung in der Ideal-Monade aus.
Bei Neustarts wird die uebergebene Funktion genutzt, um zu entscheiden, welcher von zwei gefundenen Faktoren des urspruenglichen Moduluspolynoms fuer die neu aufgewickelte Rechnung verwendet werden soll.
execISEwithAlgebraic ∷ (RingMorphism m, Field (Domain m), HasAnnihilatingPolynomials (Domain m), NormedRing (Domain m), HasMagnitudeZeroTest (Codomain m), PseudoField (Codomain m), HasDenseSubset (Codomain m), NormedRing (DenseSubset (Codomain m)), Field (DenseSubset (Codomain m))) ⇒ Alg m → (∀ s. Nondet (ISE (Domain m) s) a) → a
execISEwithAlgebraic z m fuehrt die Berechnung m im Koerper Q(z) aus. Da wir das Minimalpolynom von z nicht bestimmen wollen, realisieren wir Q(z) als ideellen Oberkoerper Q[X]\(f), wobei f das durch die Algebraizitaet von z gegebene normierte Polynom mit f(z) = 0 ist.
In Galois wird das beispielsweise benutzt, um nach Berechnung eines primitiven Elements t zu gegebenen Zahlen x und y durch eine Rechnung in Q(t) ein nichttriviales Polynom h mit h(t) = x zu finden.
Beispiele
demo ∷ IO ()