Προβολή πηγαίου κώδικα για τη σελίδα Κανονική αλυσίδα

Στα [[μαθηματικά]], και πιο συγκεκριμένα στην [[υπολογιστική άλγεβρα]] και στη θεωρία απαλοιφής, μια '''κανονική αλυσίδα''' είναι ένα ιδιαίτερο είδος τριγωνικού συνόλου πολυμεταβλητών [[Πολυώνυμο|πολυωνύμων]]<ref>{{Cite web|url=https://doc.sagemath.org/html/en/reference/polynomial_rings/polynomial_rings_multivar.html|title=Multivariate Polynomials and Polynomial Rings - Polynomials|website=doc.sagemath.org|accessdate=2024-05-31}}</ref> πάνω σε ένα πεδίο, όπου τριγωνικό σύνολο είναι μια πεπερασμένη ακολουθία πολυωνύμων τέτοια ώστε κάθε ένα από αυτά να περιέχει τουλάχιστον ένα πιο απροσδιόριστο από το προηγούμενο. Η συνθήκη που πρέπει να ικανοποιεί ένα τριγωνικό σύνολο για να είναι κανονική αλυσίδα είναι ότι, για κάθε {{mvar|k}}, κάθε κοινό μηδέν (σε ένα αλγεβρικά κλειστό πεδίο) των {{mvar|k}} πρώτων πολυωνύμων μπορεί να παραταθεί σε ένα κοινό μηδέν του {{math|(''k'' + 1)}}th πολυωνύμου. Με άλλα λόγια, οι κανονικές αλυσίδες επιτρέπουν την επίλυση συστημάτων πολυωνυμικών εξισώσεων με την επίλυση διαδοχικών μονομεταβλητών εξισώσεων χωρίς να εξετάζονται διαφορετικές περιπτώσεις.

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

==Εισαγωγή==

Δεδομένου ενός [[Σύστημα γραμμικών εξισώσεων|γραμμικού συστήματος]], μπορεί κανείς να το μετατρέψει σε [[Τριγωνικός πίνακας|τριγωνικό σύστημα]] μέσω της [[Γκαουσιανή απαλοιφή|απαλοιφής Γκάους]]<ref>{{Cite journal|title=On the worst-case complexity of integer Gaussian elimination|url=https://scholar.archive.org/work/2htta67odrfilhxegzjqfratyy|journal=Proceedings of the 1997 international symposium on Symbolic and algebraic computation - ISSAC '97|date=1997|doi=10.1145/258726.258740|language=el|first=Xin Gui|last=Fang|first2=George|last2=Havas}}</ref>. Για τη μη γραμμική περίπτωση, δεδομένου ενός πολυωνυμικού συστήματος F πάνω σε ένα πεδίο, μπορεί κανείς να το μετατρέψει (να το αποσυνθέσει ή να το τριγωνοποιήσει) σε ένα [[πεπερασμένο σύνολο]] τριγωνικών συνόλων, με την έννοια ότι η [[αλγεβρική ποικιλία]] V(F) περιγράφεται από αυτά τα τριγωνικά σύνολα.

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

== Παραδείγματα==
Συμβολίζουμε '''Q''' το πεδίο ρητών αριθμών. Στο '''Q'''[''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>] με διάταξη μεταβλητών {{nowrap|''x''<sub>1</sub> < ''x''<sub>2</sub> < ''x''<sub>3</sub>}},
: <math>T = \{ x_2^2-x_1^2, x_2(x_3-x_1)\}</math>

είναι ένα τριγωνικό σύνολο και επίσης μια κανονική αλυσίδα. Δύο γενικά σημεία που δίνονται από το ''T'' είναι τα (''a'', ''a'', ''a'') και (''a'', −''a'', ''a'') όπου το a είναι υπερβατικό πάνω από το '''Q'''.
Έτσι υπάρχουν δύο μη αναγώγιμες συνιστώσες, που δίνονται από τα {{nowrap|{ ''x''<sub>2</sub> − ''x''<sub>1</sub>, ''x''<sub>3</sub> − ''x''<sub>1</sub> }<nowiki/>}} και {{nowrap|{ ''x''<sub>2</sub> + ''x''<sub>1</sub>, ''x''<sub>3</sub> − ''x''<sub>1</sub> }<nowiki/>}}, αντίστοιχα. Ας σημειωθεί ότι: (1) το περιεχόμενο του δεύτερου πολυωνύμου είναι το ''x''<sub>2</sub>, το οποίο δεν συνεισφέρει στα γενικά σημεία που αναπαρίστανται και συνεπώς μπορεί να αφαιρεθεί- (2) η διάσταση κάθε συνιστώσας είναι 1, ο αριθμός των ελεύθερων μεταβλητών στην κανονική αλυσίδα.

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

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

:<math>R = k[x_1, \ldots, x_n]</math> 

είναι πάντα ταξινομημένοι ως{{nowrap|''x''<sub>1</sub> < ⋯ < ''x''<sub>''n''</sub>}}. Ένα μη σταθερό [[πολυώνυμο]] ''f'' στο <math>R</math> μπορεί να θεωρηθεί ως ένα μονοσήμαντο πολυώνυμο στη μεγαλύτερη μεταβλητή του. Η μεγαλύτερη μεταβλητή της f ονομάζεται κύρια μεταβλητή της, η οποία συμβολίζεται με ''mvar''(''f''). Έστω ''u'' η κύρια μεταβλητή της ''f'' και γράψτε την ως 
:<math>f = a_eu^e + \cdots + a_0,</math>

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

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

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

Έστω ''T'' = {''t''<sub>1</sub>, ..., ''t''<sub>''s''</sub>} ένα τριγωνικό σύνολο τέτοιο ώστε {{nowrap|''mvar''(''t''<sub>1</sub>) < ⋯ < ''mvar''(''t''<sub>''s''</sub>)}}, 
<math>h_i</math> το αρχικό του ''t''<sub>''i''</sub> και ''h'' το γινόμενο των ''h''<sub>''i''</sub>'s. 

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

: <math>\mathrm{resultant}(h, T) = \mathrm{resultant}(\cdots(\mathrm{resultant}(h, t_s),\ldots, t_i)\cdots) \neq 0 ,</math>

όπου κάθε προκύπτουσα υπολογίζεται ως προς την κύρια μεταβλητή ''t''<sub>''i''</sub>, αντίστοιχα.  
Αυτός ο ορισμός προέρχεται από τους Γιανγκ και Ζανγκ<ref name=":0">{{Cite web|url=https://inis.iaea.org/collection/NCLCollectionStore/_Public/22/086/22086436.pdf|title=Yang, L., Zhang, J. (1994). Searching dependency between algebraic equations: an algorithm applied to automated reasoning.}}</ref>, ο οποίος έχει πολύ αλγοριθμική χροιά.

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

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

:{{nowrap|<math>W(T) = V(T)\setminus V(h)</math>,}} δηλαδή,
η διαφορά συνόλου των ποικιλιών ''V''(''T'') και ''V''(''h''). 
Το συνημμένο αλγεβρικό αντικείμενο μιας κανονικής αλυσίδας είναι το ''κορεσμένο ιδεώδες'' της. 

:<math>\mathrm{sat}(T) = (T):h^\infty .</math>

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

:<math>\overline{W(T)} = V(\mathrm{sat}(T)) ,</math>
και η διάστασή του είναι ''n'' - |''T''|, η διαφορά του αριθμού των μεταβλητών και του αριθμού των πολυωνύμων στο ''T''.

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

Γενικά, υπάρχουν δύο τρόποι για να αναλυθεί ένα πολυωνυμικό σύστημα ''F''. Ο πρώτος είναι η χαλαρή αποσύνθεση, δηλαδή η αναπαράσταση μόνο των γενικών σημείων του με την έννοια του (Καλκμπρένερ),
: <math>\sqrt{(F)} = \bigcap_{i=1}^e \sqrt{\mathrm{sat}(T_i)} .</math>

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

: <math>V(F) = \bigcup_{i=1}^e W(T_i) .</math>

Υπάρχουν διαθέσιμοι διάφοροι αλγόριθμοι για τριγωνικές αποσυνθέσεις<ref>{{Cite web|url=https://pdf.sciencedirectassets.com/272313/1-s2.0-S0747717112X00129/1-s2.0-S0747717111002070/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjELv%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJHMEUCIGH5WcqPrRiDk2ea9BdI91N6Ue3tjoRLR3C%2BEeNATlf9AiEArUFOfQyBXYNXQFcEim3DyNVCk6LOICWe8KmGO7d%2BE%2FIqsgUIQxAFGgwwNTkwMDM1NDY4NjUiDHro5P51bRp0kA9pryqPBbvPHp33LdecbJWUWcpn6222uSXvhoov36UzuvXFJjmEEPb7UmjaaupKhOTHefUHSzmPbDRYV%2FCXQtJ24U4XmBUKv97jRLMCDX%2FXuc7zH98WabSaMdl7FSM69Uqd5c18dEhxhp5EEbgyGCrC9kAvvjUJ7Xb5ATfoAvKmG27QrUDPDSRrAVNA9ezeEcpJS8k2BzfUPPL%2BPNSHMtMqNKqB7WznKEmxn%2BhVPG8TEt1tgpiTj4KmhPfh4hbwiZ8Bongk1zgWJEvNVM8DJyPJBj8HCyWmjgG66pEJPa7BiF1T1OSs%2FxL39bOdzdjRjEz7iO%2FAVOsOLRWNcAdQjBBZlYlZm%2FJ%2BOD5%2F%2FT03zTWi0fT4HFEDDD8b5zLmN4G0hahuqQxDcMjV71FiJeBL8CpfMgAuQieoJrTN%2BxiJ63vPcWvsH7DESf4Xhf5DYBfJojBN%2BNJMqyK%2B9DDo6AYUSGFgD5%2BboQ6rEA7LYtiQcjiy3f6nJCr8V1muOeVZvIrIvHM4rlABGKOAtVKSwKyTgN%2FJeWdYxNzTvtNi2YNvTJVA58w3ZbGs13M4M4QWSqUbZNvA7ThMPEyu4w46PZ0fuPlol9YdUNSO9xurwb0b9iDJXrmJ65s0AHIx48sGt2gwsgpHzoDLJlXInQZvztDKZxyg9BpCWP6sisgeGKb2KIm8RfQb0bsM%2FulV1qeAaeCzdJzC9VY05wPqGg9wyrGL5CVSxvzl0RcNrcr8R5HX6T%2FLyqFJDemzBIj5el0nKmv72QMBqYOR%2Fy%2FsC1QRGcY6tbAxUc%2Faxu9rwevm%2BS6HavZsgVeTkTDkshAOa6gAL2%2BpV9ZtsMXtomZhUIG1TqDsiIQGvCVxuSgf%2FIABJfMeGmd8qdgzOLww4MTmsgY6sQHeL5Q%2FdzPAy9Ol%2BCEmA0LeSAMWrx4CEqiOrKHsQcyC2rtsoUsqVrVKnUVtdUmp1%2FmyvhLY4Z%2FTRUkuRZgUqJMtRW3FSHWh%2FvfG6Om4ALlvaSiUk3wMV1kMe%2F%2FlAvfkO0nZQrO5lN80f6gdDZMEMnr%2FAbOMLyyUk2lnInctRmyzJMj2qNwu0fjr8mvY8FbH1jmnCV7O5RkhzC6uZpCJmpga0lhOn60wFiVZFPFmas3y8%2BA%3D&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Date=20240531T120641Z&X-Amz-SignedHeaders=host&X-Amz-Expires=300&X-Amz-Credential=ASIAQ3PHCVTYYHN2HTNT%2F20240531%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Signature=e0dd341797189f74d8a005c599780413f5930a668bbf9cab23f7e1c3761ea9ad&hash=befbd4f839c738753c270aa252e2f224efafa9aebfcb8c7d506c0478313cc8f8&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=S0747717111002070&tid=spdf-37a14565-7d88-4e32-9d0a-7ee6bece9871&sid=ecfba4037dd7e44e017b09c10cd8031805d3gxrqb&type=client&tsoh=d3d3LnNjaWVuY2VkaXJlY3QuY29t&ua=1d115d5802530a560501&rr=88c6d6df2f94ee7b&cc=gr&kca=eyJrZXkiOiJNSzBBamlUTytQWm85R2FjK0xDSXVpcWNhRGhvV25SeXo5Q1dBdlcvV3BrT1NYS1pTVnZ6NkJFcEVTUlNJNFR6VnlWWDZzdFltQmNISzFtY2VDK0RLUWd3dmdGYXF0OUxGN3BQTHZ4TkhNRWplY3RNeHNsS3JzR1VHZnZ6TjMvZEU2Z0hVd1NvRlZSd3dnUVJEV1ZsWW5GaGJXUmJDcE5xL1ozU1RPMEdwb1FlTzhvTyIsIml2IjoiZWEwYzczYzU3MTgwMmM3NjdhNjY1NWI2NTFiZjYwM2IifQ==_1717157213759|title=Triangular decomposition of semi-algebraic systems}}</ref> με οποιαδήποτε έννοια.

== Ιδιότητες ==

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

* Το κορεσμένο [[Ιδεώδες (μαθηματικά)|ιδεώδες]] sat(''T'') είναι ένα ''αμιγές ιδεώδες'' με διάσταση ''n'' - |''T''|.
* Μια κανονική αλυσίδα κατέχει μια ισχυρή ιδιότητα απαλοιφής με την έννοια ότι:
: <math> \mathrm{sat}(T \cap k[x_1, \ldots , x_i]) = \mathrm{sat}(T) \cap k[x_1,\ldots , x_i] .</math>

* Ένα πολυώνυμο ''p'' είναι στο sat(''T'') [[αν και μόνο αν]] το p είναι ψευδο-αναγωγικό στο μηδέν από το ''T'', δηλαδή,
: <math>p\in\mathrm{sat}(T)\iff \mathrm{prem}(p, T) = 0 .</math>
:Ως εκ τούτου, ο έλεγχος συμμετοχής για το sat(''T'') είναι αλγοριθμικός.

* Ένα πολυώνυμο ''p'' είναι ''μηδενικός διαιρέτης''<ref>{{Cite web|url=https://encyclopediaofmath.org/index.php?title=Zero_divisor|title=Zero divisor - Encyclopedia of Mathematics|website=encyclopediaofmath.org|accessdate=2024-05-31}}</ref> modulo sat(''T'') αν και μόνο αν <math>\mathrm{prem}(p, T)\neq0</math> και {{nowrap|<math>\mathrm{resultant}(p, T)=0</math>.}}
:Ως εκ τούτου, ο έλεγχος κανονικότητας για το sat(''T'') είναι αλγοριθμικός.

* Δεδομένου ενός πρώτου ιδεώδους ''P'', υπάρχει μια κανονική αλυσίδα ''C'' τέτοια ώστε ''P'' = sat(''C''). 
* Αν το πρώτο στοιχείο μιας κανονικής αλυσίδας ''C'' είναι ένα μη αναγώγιμο πολυώνυμο και τα υπόλοιπα είναι γραμμικά στην κύρια μεταβλητή τους, τότε το sat(''C'') είναι ένα πρώτο [[Ιδεώδες (μαθηματικά)|ιδεώδες]].
* Αντίστροφα, αν ''P'' είναι ένα πρώτο ιδεώδες, τότε, μετά από σχεδόν όλες τις γραμμικές αλλαγές των μεταβλητών, υπάρχει μια κανονική αλυσίδα ''C'' του προηγούμενου σχήματος τέτοια ώστε ''P'' = sat(''C'').
* Ένα τριγωνικό σύνολο είναι μια κανονική αλυσίδα αν και μόνο αν είναι ένα χαρακτηριστικό σύνολο Ριτ<ref>{{Cite web|url=https://library.wolfram.com/infocenter/MathSource/5716/|title=WuRittSolva: Implementation of Wu-Ritt Characteristic Set Method -- from Wolfram Library Archive|website=library.wolfram.com|accessdate=2024-05-31}}</ref> του κορεσμένου ιδεώδους του.

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

* P. Aubry, D. Lazard, M. Moreno Maza. [http://www.sciencedirect.com/science/article/pii/S0747717199902699 On the theories of triangular sets]. Journal of Symbolic Computation, 28(1&ndash;2):105&ndash;124, 1999.
* F. Boulier and F. Lemaire and M. Moreno Maza. [https://hal.archives-ouvertes.fr/docs/00/13/71/58/PDF/blm06.pdf Well known theorems on triangular systems and the D5 principle]. Transgressive Computing 2006, Granada, Spain.
* E. Hubert. [ftp://nozdr.ru/biblio/kolxo3/Cs/CsCa/Winkler%20F.,%20Langer%20U.%20(eds.)%20Symbolic%20and%20Numerical%20Scientific%20Computation%20(Proc.%20SNSC%202001,%20Hagenberg)(LNCS2630,%20Springer,%202003)(ISBN%203540405542)(398s)_CsCa_.pdf#page=51 Notes on triangular sets and triangulation-decomposition algorithms I: Polynomial systems]{{Dead link|date=Αυγούστου 2024 }}.  LNCS, volume 2630, Springer-Verlag Heidelberg.
* F. Lemaire and M. Moreno Maza and Y. Xie. The RegularChains library. Maple Conference 2005. 
* M. Kalkbrener: [https://core.ac.uk/download/pdf/82131108.pdf Algorithmic Properties of Polynomial Rings]. J. Symb. Comput. 26(5): 525&ndash;581 (1998).
* M. Kalkbrener: [http://www.sciencedirect.com/science/article/pii/S0747717183710114/pdf?md5=43680d0255596096147a53ce3b42a16a&pid=1-s2.0-S0747717183710114-main.pdf&_valck=1 A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties]. J. Symb. Comput. 15(2): 143&ndash;167 (1993).
* D. Wang. [https://www.sciencedirect.com/science/article/pii/S0747717199903553/pdf?md5=835a5b4348eaffe59316f0af18d1394d&pid=1-s2.0-S0747717199903553-main.pdf Computing Triangular Systems and Regular Systems]. Journal of Symbolic Computation 30(2) (2000) 221&ndash;236.
* Yang, L., Zhang, J. (1994). [http://www.iaea.org/inis/collection/NCLCollectionStore/_Public/22/086/22086436.pdf Searching dependency between algebraic equations: an algorithm applied to automated reasoning]. Artificial Intelligence in Mathematics, pp.&nbsp;14715,  [[Oxford University Press]].

==Δείτε επίσης==

* [https://books.google.gr/books?id=3rtX9t-nnvwC&pg=PA195&dq=Noetherian+scheme&hl=el&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwi_4vS_65yGAxVDBdsEHT_9AA0Q6AF6BAgFEAI#v=onepage&q=Noetherian%20scheme&f=false Algebraic Geometry]
* [[Αλγεβρική ποικιλία]]
*[[Τοπολογία]]

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

*[https://www.itia.ntua.gr/en/docinfo/1318/ English - Greek Dictionary of Pure and Applied Mathematics] Εθνικό Μετσόβιο Πολυτεχνείο
*[https://www.mas.ucy.ac.cy/georgios/bookfiles/dict1.pdf Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου]
* [https://staff.fnwi.uva.nl/z.mao/animated_ideals_PD_crys.arxiv.pdf Revisiting derived crystalline cohomology]
* [http://math.ucdavis.edu/~mluu/cohomology-2017.pdf Crystalline Cohomology of Superschemes]
*Onishchik, A.L. (2001) [1994], "[https://encyclopediaofmath.org/index.php?title=Analytic%20space&oldid=45182 Analytic space]", [[Εγκυκλοπαίδεια των Μαθηματικών|Encyclopedia of Mathematics]], EMS Press
*[http://www.jmilne.org/math/Books/adt.html ''Arithmetic Duality Theorems'' (PDF)], online book by James Milne, explains at the level of flat cohomology duality theorems originating in the [[:en:Tate–Poitou duality|Tate–Poitou duality]] of [[:en:Galois cohomology|Galois cohomology]]
*[https://pbelmans.ncag.info/blog/2013/12/31/the-fppf-topology-is-generated-by-zariski-coverings-and-surjective-finite-locally-free-morphisms/ The fppf topology is generated by Zariski coverings and surjective finite locally free morphisms]

==Παραπομπές==
{{reflist}}

{{Authority control}} 
{{Portal bar|Μαθηματικά}}

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