Κανονική αλυσίδα

Στα μαθηματικά, και πιο συγκεκριμένα στην υπολογιστική άλγεβρα και στη θεωρία απαλοιφής, μια κανονική αλυσίδα είναι ένα ιδιαίτερο είδος τριγωνικού συνόλου πολυμεταβλητών πολυωνύμων πάνω σε ένα πεδίο, όπου τριγωνικό σύνολο είναι μια πεπερασμένη ακολουθία πολυωνύμων τέτοια ώστε κάθε ένα από αυτά να περιέχει τουλάχιστον ένα πιο απροσδιόριστο από το προηγούμενο. Η συνθήκη που πρέπει να ικανοποιεί ένα τριγωνικό σύνολο για να είναι κανονική αλυσίδα είναι ότι, για κάθε , κάθε κοινό μηδέν (σε ένα αλγεβρικά κλειστό πεδίο) των  πρώτων πολυωνύμων μπορεί να παραταθεί σε ένα κοινό μηδέν του th πολυωνύμου. Με άλλα λόγια, οι κανονικές αλυσίδες επιτρέπουν την επίλυση συστημάτων πολυωνυμικών εξισώσεων με την επίλυση διαδοχικών μονομεταβλητών εξισώσεων χωρίς να εξετάζονται διαφορετικές περιπτώσεις.

Οι κανονικές αλυσίδες βελτιώνουν την έννοια των χαρακτηριστικών συνόλων του Γου με την έννοια ότι παρέχουν ένα καλύτερο αποτέλεσμα με παρόμοια μέθοδο υπολογισμού.

Εισαγωγή

Δεδομένου ενός γραμμικού συστήματος, μπορεί κανείς να το μετατρέψει σε τριγωνικό σύστημα μέσω της απαλοιφής Γκάους. Για τη μη γραμμική περίπτωση, δεδομένου ενός πολυωνυμικού συστήματος F πάνω σε ένα πεδίο, μπορεί κανείς να το μετατρέψει (να το αποσυνθέσει ή να το τριγωνοποιήσει) σε ένα πεπερασμένο σύνολο τριγωνικών συνόλων, με την έννοια ότι η αλγεβρική ποικιλία V(F) περιγράφεται από αυτά τα τριγωνικά σύνολα.

Ένα τριγωνικό σύνολο μπορεί απλώς να περιγράφει το κενό σύνολο. Για να διορθωθεί αυτή η εκφυλισμένη περίπτωση, εισήχθη η έννοια της κανονικής αλυσίδας, ανεξάρτητα από τους Καλκμπρένερ (1993), Yάνγκ και Ζανγκ (1994). Οι κανονικές αλυσίδες εμφανίζονται επίσης στους Τσου και Γκάο (1992). Οι κανονικές αλυσίδες είναι ειδικά τριγωνικά σύνολα τα οποία χρησιμοποιούνται σε διάφορους αλγορίθμους για τον υπολογισμό μη-αναμεμειγμένων διαστάσεων αποσυνθέσεων αλγεβρικών ποικιλιών. Χωρίς τη χρήση παραγοντοποίησης, αυτές οι αποσυνθέσεις έχουν καλύτερες ιδιότητες από αυτές που παράγει ο αλγόριθμος του Γου. Ο αρχικός ορισμός του Καλκμπρένερ βασίστηκε στην ακόλουθη παρατήρηση: κάθε μη αναγώγιμη ποικιλία καθορίζεται μοναδικά από ένα από τα γενικά σημεία της και οι ποικιλίες μπορούν να αναπαρασταθούν περιγράφοντας τα γενικά σημεία των μη αναγώγιμων συνιστωσών τους. Αυτά τα γενικά σημεία προκύπτουν από κανονικές αλυσίδες.

 Παραδείγματα
Συμβολίζουμε Q το πεδίο ρητών αριθμών. Στο Q[x1, x2, x3] με διάταξη μεταβλητών ,


είναι ένα τριγωνικό σύνολο και επίσης μια κανονική αλυσίδα. Δύο γενικά σημεία που δίνονται από το T είναι τα (a, a, a) και (a, −a, a) όπου το a είναι υπερβατικό πάνω από το Q.
Έτσι υπάρχουν δύο μη αναγώγιμες συνιστώσες, που δίνονται από τα  και , αντίστοιχα. Ας σημειωθεί ότι: (1) το περιεχόμενο του δεύτερου πολυωνύμου είναι το x2, το οποίο δεν συνεισφέρει στα γενικά σημεία που αναπαρίστανται και συνεπώς μπορεί να αφαιρεθεί- (2) η διάσταση κάθε συνιστώσας είναι 1, ο αριθμός των ελεύθερων μεταβλητών στην κανονική αλυσίδα.

Τυπικοί ορισμοί

Οι μεταβλητές στον πολυωνυμικό δακτύλιο



είναι πάντα ταξινομημένοι ως. Ένα μη σταθερό πολυώνυμο f στο  μπορεί να θεωρηθεί ως ένα μονοσήμαντο πολυώνυμο στη μεγαλύτερη μεταβλητή του. Η μεγαλύτερη μεταβλητή της f ονομάζεται κύρια μεταβλητή της, η οποία συμβολίζεται με mvar(f). Έστω u η κύρια μεταβλητή της f και γράψτε την ως 

όπου e είναι ο βαθμός του f σε σχέση με το u και  είναι ο κύριος συντελεστής του f σε σχέση με το u.  Τότε ο αρχικός βαθμός της f είναι  και e είναι ο κύριος βαθμός της.

Ένα μη κενό υποσύνολο T του  είναι τριγωνικό σύνολο, αν τα πολυώνυμα στο T είναι μη σταθερά και έχουν διακριτές κύριες μεταβλητές. Επομένως, ένα τριγωνικό σύνολο είναι πεπερασμένο και έχει πληθικότητα το πολύ n.

Κανονική αλυσίδα

Έστω T = {t1, ..., ts} ένα τριγωνικό σύνολο τέτοιο ώστε , 
 το αρχικό του ti και h το γινόμενο των hi's. 

Τότε η Τ είναι κανονική αλυσίδα αν 



όπου κάθε προκύπτουσα υπολογίζεται ως προς την κύρια μεταβλητή ti, αντίστοιχα.  
Αυτός ο ορισμός προέρχεται από τους Γιανγκ και Ζανγκ, ο οποίος έχει πολύ αλγοριθμική χροιά.

Οιονεί συστατικό και κορεσμένο ιδεώδες μιας κανονικής αλυσίδας

Η οιονεί συνιστώσα W(T) που περιγράφεται από την κανονική αλυσίδα T είναι 

 δηλαδή,
η διαφορά συνόλου των ποικιλιών V(T) και V(h). 
Το συνημμένο αλγεβρικό αντικείμενο μιας κανονικής αλυσίδας είναι το κορεσμένο ιδεώδες της. 

Ένα κλασικό αποτέλεσμα είναι ότι το κλείσιμο Ζαρίσκι του W'''(T) ισούται με την ποικιλία που ορίζεται από το sat(T), δηλαδή,

και η διάστασή του είναι n - |T|, η διαφορά του αριθμού των μεταβλητών και του αριθμού των πολυωνύμων στο T.

Τριγωνικές αποσυνθέσεις

Γενικά, υπάρχουν δύο τρόποι για να αναλυθεί ένα πολυωνυμικό σύστημα F. Ο πρώτος είναι η χαλαρή αποσύνθεση, δηλαδή η αναπαράσταση μόνο των γενικών σημείων του με την έννοια του (Καλκμπρένερ),


Η δεύτερη αφορά την περιγραφή όλων των μηδενικών με την έννοια του Ντανιέλ Λαζάρντ,



Υπάρχουν διαθέσιμοι διάφοροι αλγόριθμοι για τριγωνικές αποσυνθέσεις με οποιαδήποτε έννοια.

 Ιδιότητες 

Έστω T μια κανονική αλυσίδα στον πολυωνυμικό δακτύλιο R.

 Το κορεσμένο ιδεώδες sat(T) είναι ένα αμιγές ιδεώδες με διάσταση n - |T|.
 Μια κανονική αλυσίδα κατέχει μια ισχυρή ιδιότητα απαλοιφής με την έννοια ότι:


 Ένα πολυώνυμο p είναι στο sat(T) αν και μόνο αν το p είναι ψευδο-αναγωγικό στο μηδέν από το T, δηλαδή,

Ως εκ τούτου, ο έλεγχος συμμετοχής για το sat(T) είναι αλγοριθμικός.

 Ένα πολυώνυμο p είναι μηδενικός διαιρέτης modulo sat(T) αν και μόνο αν  και 
Ως εκ τούτου, ο έλεγχος κανονικότητας για το sat(T) είναι αλγοριθμικός.

 Δεδομένου ενός πρώτου ιδεώδους P, υπάρχει μια κανονική αλυσίδα C τέτοια ώστε P = sat(C). 
 Αν το πρώτο στοιχείο μιας κανονικής αλυσίδας C είναι ένα μη αναγώγιμο πολυώνυμο και τα υπόλοιπα είναι γραμμικά στην κύρια μεταβλητή τους, τότε το sat(C) είναι ένα πρώτο ιδεώδες.
 Αντίστροφα, αν P είναι ένα πρώτο ιδεώδες, τότε, μετά από σχεδόν όλες τις γραμμικές αλλαγές των μεταβλητών, υπάρχει μια κανονική αλυσίδα C του προηγούμενου σχήματος τέτοια ώστε P = sat(C'').
 Ένα τριγωνικό σύνολο είναι μια κανονική αλυσίδα αν και μόνο αν είναι ένα χαρακτηριστικό σύνολο Ριτ του κορεσμένου ιδεώδους του.

Δημοσιεύσεις 

 P. Aubry, D. Lazard, M. Moreno Maza. On the theories of triangular sets. Journal of Symbolic Computation, 28(1–2):105–124, 1999.
 F. Boulier and F. Lemaire and M. Moreno Maza. Well known theorems on triangular systems and the D5 principle. Transgressive Computing 2006, Granada, Spain.
 E. Hubert. Notes on triangular sets and triangulation-decomposition algorithms I: Polynomial systems.  LNCS, volume 2630, Springer-Verlag Heidelberg.
 F. Lemaire and M. Moreno Maza and Y. Xie. The RegularChains library. Maple Conference 2005. 
 M. Kalkbrener: Algorithmic Properties of Polynomial Rings. J. Symb. Comput. 26(5): 525–581 (1998).
 M. Kalkbrener: A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties. J. Symb. Comput. 15(2): 143–167 (1993).
 D. Wang. Computing Triangular Systems and Regular Systems. Journal of Symbolic Computation 30(2) (2000) 221–236.
 Yang, L., Zhang, J. (1994). Searching dependency between algebraic equations: an algorithm applied to automated reasoning. Artificial Intelligence in Mathematics, pp. 14715,  Oxford University Press.

Δείτε επίσης

 Algebraic Geometry
 Αλγεβρική ποικιλία
Τοπολογία

Εξωτερικοί σύνδεσμοι  

English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
 Revisiting derived crystalline cohomology 
 Crystalline Cohomology of Superschemes
Onishchik, A.L. (2001) [1994], "Analytic space", Encyclopedia of Mathematics, EMS Press
Arithmetic Duality Theorems (PDF), online book by James Milne, explains at the level of flat cohomology duality theorems originating in the Tate–Poitou duality of Galois cohomology
The fppf topology is generated by Zariski coverings and surjective finite locally free morphisms

Παραπομπές



Κατηγορία:Αλγεβρική γεωμετρία
Κατηγορία:Άλγεβρα
Κατηγορία:Εξισώσεις
Κατηγορία:Περιοχές των μαθηματικών
Κατηγορία:Πολυώνυμα
Κατηγορία:Επιστήμη υπολογιστών