Zwykły łańcuch

W algebrze komputerowej regularny łańcuch jest szczególnym rodzajem trójkątnego zestawu w wielowymiarowym wielomianowym pierścieniu nad polem. Wzmacnia pojęcie zbioru charakterystycznego .

Wstęp

Biorąc pod uwagę system liniowy , można go przekształcić w system trójkątny poprzez eliminację Gaussa . W przypadku nieliniowym, biorąc pod uwagę system wielomianowy F na polu, można go przekształcić (rozłożyć lub triangularyzować) na skończony zbiór zbiorów trójkątnych w tym sensie, że rozmaitość algebraiczna V ( F ) jest opisana przez te zbiory trójkątne .

Zbiór trójkątny może jedynie opisywać zbiór pusty. Aby naprawić ten zdegenerowany przypadek, pojęcie regularnego łańcucha zostało wprowadzone niezależnie przez Kalkbrener (1993), Yang i Zhang (1994). Regularne łańcuchy pojawiają się również w Chou i Gao (1992). Łańcuchy regularne to specjalne zbiory trójkątne, które są używane w różnych algorytmach do obliczania niezmieszanych wymiarów rozkładów rozmaitości algebraicznych. Bez stosowania rozkładu na czynniki, te dekompozycje mają lepsze właściwości niż te, które są generowane przez algorytm Wu . Oryginalna definicja Kalkbrenera opierała się na następującej obserwacji: każda nieredukowalna odmiana jest jednoznacznie określona przez jedną z jej punkty rodzajowe i odmiany można przedstawić, opisując punkty rodzajowe ich nieredukowalnych składników. Te ogólne punkty są podawane przez regularne łańcuchy.

Przykłady

Oznaczmy Q polem liczb wymiernych. W Q [ x ₁ , x ₂ , x ₃ ] ze zmienną kolejnością x ₁ < x ₂ < x ₃ ,

${\ Displaystyle T = \ {x_ {2} ^ {2} -x_ {1} ^ {2}, x_ {2} (x_{3}-x_{1})\}}$

jest zbiorem trójkątnym, a także regularnym łańcuchem. Dwa ogólne punkty podane przez T to ( a , a , a ) i ( a , − a , a ), gdzie a jest transcendentalne względem Q . Istnieją więc dwa nieredukowalne składniki, dane przez { x ₂ − x ₁ , x ₃ − x ₁ } i { x ₂ + x ₁ , x ₃ − x ₁ } , odpowiednio. Należy zauważyć, że: (1) zawartość drugiego wielomianu wynosi x ₂ , co nie ma udziału w reprezentowanych ogólnych punktach, a zatem można je usunąć; (2) wymiar każdego składnika wynosi 1, liczba wolnych zmiennych w regularnym łańcuchu.

Definicje formalne

Zmienne w pierścieniu wielomianowym

${\ Displaystyle R = k [x_ {1}, \ ldots, x_ {n}]}$

są zawsze sortowane jako x ₁ < ⋯ < x _n . Niestały wielomian f w można postrzegać jako wielomian jednowymiarowy w swojej największej $.$ Największa zmienna w f nazywana jest jej zmienną główną, oznaczoną przez mvar ( f ). Niech u będzie główną zmienną f i zapisz ją jako

$\ Displaystyle f = a_ {e} u ^ {e} + \ cdots + a_ {0},$

gdzie e jest stopniem f w odniesieniu do u i jest wiodącym współczynnikiem $.$ odniesieniu do u $Wtedy$ inicjał f to to jego główny stopień .

• Zestaw trójkątny

Niepusty podzbiór T z $są$ jest zbiorem trójkątnym, jeśli wielomiany w T niestałe i mają różne zmienne główne. Zatem zbiór trójkątny jest skończony i ma co najwyżej liczność n .

• Zwykły łańcuch

Niech T = { t ₁ , ..., t _s } będzie trójkątnym zbiorem takim, że mvar ( t ₁ ) < ⋯ < mvar ( t _s ) , ${\ displaystyle h_ {i}}$ będzie początkiem t _ja i h będzie iloczynem h _i 's. Wtedy T jest regularnym łańcuchem if

${\ Displaystyle \ operatorname {wynikowy} (h, T) = \ operatorname {wynikowy} (\ cdots (\ operatorname {wynikowy} (h, t_ {s}), \ ldots, t_ {i}) \ cdots) \ neq 0,}$

gdzie każda wypadkowa jest obliczana odpowiednio w odniesieniu do zmiennej głównej t _i . Ta definicja pochodzi od Yang i Zhang, która ma dużo algorytmicznego smaku.

• Quasi-składowy i nasycony ideał regularnego łańcucha

Quasi -składowa W ( T ) opisana regularnym łańcuchem T jest

${\ Displaystyle W (T) = V (T) \ setminus V (h)}$ , czyli

ustalona różnica odmian V ( T ) i V ( h ). Dołączony obiekt algebraiczny regularnego łańcucha jest jego nasyconym ideałem

${\ Displaystyle \ operatorname {s.} (T) = (T): h ^ {\ infty}.}$

Klasycznym wynikiem jest to, że zamknięcie Zariskiego W ( T ) jest równe rozmaitości zdefiniowanej przez sat ( T ), to znaczy

${\ Displaystyle {\ overline {W (T)}} = V (\ operatorname {sat} (T)}}$

a jego wymiar to n - | T |, różnica liczby zmiennych i liczby wielomianów w T .

• Rozkłady trójkątne

Ogólnie rzecz biorąc, istnieją dwa sposoby dekompozycji systemu wielomianowego F . Pierwszym z nich jest leniwy rozkład, czyli jedynie reprezentacja jego punktów generycznych w sensie (Kalkbrenera),

${\ Displaystyle {\ sqrt {(F)}} = \ bigcap _ {i = 1} ^ {e} {\ sqrt {\ operatorname {s} (T_ {i})}}.}$

Drugi to opisanie wszystkich zer w sensie Lazarda ,

${\ Displaystyle V (F) = \ bigcup _ {i = 1} ^ {e} W (T_ {i}).}$

Istnieją różne algorytmy dostępne dla dekompozycji trójkątnych w każdym sensie.

Nieruchomości

Niech T będzie regularnym łańcuchem w wielomianowym pierścieniu R .

• Nasycony ideał sat( T ) jest ideałem niezmieszanym o wymiarze n − | T |.
• Zwykły łańcuch ma silną właściwość eliminacji w tym sensie, że:

${\ Displaystyle \ operatorname {sat} (T \ czapka k [x_ {1}, \ ldots, x_ {i}]) = \ operatorname {sat} (T) \ czapka k [x_ {1}, \ ldots, x_ {i}].}$

• Wielomian p jest w sat( T ) wtedy i tylko wtedy, gdy p jest pseudo-zredukowane do zera przez T , to znaczy

${\ Displaystyle p \ w \ operatorname {sat} (T)\iff \mathrm {prem} (p,T)=0.}$

Zatem test przynależności dla sat( T ) jest algorytmiczny.

• Wielomian p jest dzielnikiem zera modulo sat( T ) wtedy i tylko wtedy, gdy ${\ Displaystyle \ operatorname {prem} (p, T) \ neq 0}$ i ${\ Displaystyle \ operatorname {wypadkowy} ( p,T)=0}$ .

Stąd test regularności dla sat( T ) jest algorytmiczny.

• Mając ideał pierwszy P , istnieje regularny łańcuch C taki, że P = sat( C ).
• Jeśli pierwszy element regularnego łańcucha C jest nierozkładalnym wielomianem, a pozostałe są liniowe w swojej zmiennej głównej, to sat( C ) jest ideałem pierwszym.
• I odwrotnie, jeśli P jest ideałem pierwszym, to po prawie wszystkich liniowych zmianach zmiennych istnieje regularny łańcuch C o poprzednim kształcie, taki że P = sat( C ).
• Zbiór trójkątny jest regularnym łańcuchem wtedy i tylko wtedy, gdy jest charakterystycznym zbiorem Ritta jego nasyconego ideału.

Zobacz też

• Metoda zbioru charakterystycznego Wu
• podstawa Gröbnera
• Regularny system półalgebraiczny
• Dekompozycja trójkątna

Dalsze referencje

• P. Aubry, D. Lazard, M. Moreno Maza. O teoriach zbiorów trójkątnych . Journal of Symbolic Computation, 28 (1–2): 105–124, 1999.
• F. Boulier i F. Lemaire oraz M. Moreno Maza. Dobrze znane twierdzenia o układach trójkątnych i zasada D5 . Transgressive Computing 2006, Granada, Hiszpania.
• E. Huberta. Uwagi o zbiorach trójkątnych i algorytmach triangulacyjno-rozkładowych I: Układy wielomianowe . LNCS, tom 2630, Springer-Verlag Heidelberg.
• F. Lemaire i M. Moreno Maza i Y. Xie. Biblioteka RegularChains. Klon Konferencja 2005.
• M. Kalkbrener: Algorytmiczne właściwości pierścieni wielomianowych . J. Symb. Oblicz. 26(5): 525-581 (1998).
• M. Kalkbrener: uogólniony algorytm euklidesowy do obliczania trójkątnych reprezentacji rozmaitości algebraicznych . J. Symb. Oblicz. 15(2): 143-167 (1993).
• D. Wanga. Obliczanie systemów trójkątnych i systemów regularnych . Journal of Symbolic Computation 30 (2) (2000) 221–236.
• Yang, L., Zhang, J. (1994). Wyszukiwanie zależności między równaniami algebraicznymi: algorytm zastosowany do automatycznego wnioskowania . Sztuczna inteligencja w matematyce, s. 14715, Oxford University Press.