Полиномдық сақиналар және олардың қасиеттері

Кіріспе

Алгебралық құрылым

Математикада, әсіресе алгебра саласында, полиномиялық сақина немесе полиномиялық алгебра – бір немесе бірнеше белгісіздерде (дәстүрлі түрде айнымалы деп те аталады) полиномиялар жиынынан, басқа сақинадағы коэффициенттермен (көбінесе өрістегі) құрылған сақина (ол сондай-ақ коммутативтік алгебра болып табылады). Көбінесе "полиномиялық сақина" термині өрістегі бір белгісіздегі полиномиялық сақинаның нақты жағдайын білдіреді. Мұндай полиномиялық сақиналардың маңыздылығы олардың бүтін сандар сақинасымен ортақ көптеген қасиеттеріне байланысты. Полиномиялық сақиналар математиканың көптеген салаларында кездеседі және олар, мысалы, сандар теориясы, коммутативтік алгебра және алгебралық геометрия сияқты салаларда маңызды рөл атқарады. Сақиналар теориясында полиномиялық сақиналардың кейбір қасиеттерін жалпылау үшін бірегей факторлау домендері, тұрақты сақиналар, топтық сақиналар, формалды қуат қатарларының сақиналары, Оре полиномдары, сыныпталған сақиналар сияқты көптеген сақиналар кластары енгізілді. Тығыз байланысты түсінік – векторлық кеңістіктегі полиномиалдық функциялар сақинасы және, жалпы алғанда, алгебралық санның тұрақты функциялар сақинасы.

Факторлау

К[X] факторлаудан басқа, барлық алдыңғы қасиеттері тиімді, себебі олардың дәлелдемелері, жоғарыда көрсетілгендей, қасиетті тексеру және бар екені айтылған көпмүшелерді есептеу алгоритмдерімен байланысты. Бұған қоса, бұл алгоритмдер тиімді, өйткені олардың есептеу күрделілігі кіріс мөлшерінің квадраттық функциясы болып табылады. Факторлау жағдайы мүлдем басқаша: бірегей факторлаудың дәлелі факторлау әдісіне ешқандай түйсік бермейді. Бүтін сандар үшін де, классикалық компьютерде оларды полиномиалдық уақытта факторлайтын белгілі алгоритм жоқ. Бұл RSA криптожүйесінің негізі, ол Интернет арқылы қауіпсіз байланыс үшін кеңінен қолданылады. K[X] жағдайында факторлар және оларды есептеу әдістері K-ға күшті түрде байланысты. Кешенді сандар бойынша бөлгішсіз факторлар (әрі факторланбайтын) барлығы бірінші дәрежелі, ал нақты сандар бойынша екінші дәрежелі бөлгішсіз көпмүшелер бар, ал рационалдық сандар бойынша кез келген дәрежедегі бөлгішсіз көпмүшелер кездеседі. Мысалы, берілген көпмүше рационалдық сандарға қатысты бөлгішсіз, ал нақты және кешенді сандарға қатысты факторланады. Факторлау алгоритмінің болуы негізгі өріске де байланысты. Нақты немесе кешенді сандар жағдайында Абель-Руффини теоремасы кейбір көпмүшелердің түбірлерін, демек, бөлгішсіз факторларды дәл есептеу мүмкін емес екенін көрсетеді. Сондықтан факторлау алгоритмі факторлардың тек жуық мәнін ғана есептей алады. Мұндай жуық мәндерді есептеу үшін әртүрлі алгоритмдер жасалған, қараңыз: Көпмүшелердің түбірін табу. K өрісінің мысалы бар, онда K арифметикалық операциялары үшін нақты алгоритмдер бар, бірақ түріндегі көпмүше бөлгішсіз бе әлде төменгі дәрежелі көпмүшелердің көбейтіндісі бе екенін анықтайтын алгоритм жоқ. Екінші жағынан, рационалдық сандар және шекті өрістерде жағдай бүтін сандарды факторлаудан жақсы, себебі полиномиалдық күрделілікке ие факторлау алгоритмдері бар. Олар көптеген жалпы мақсаттағы компьютерлік алгебра жүйелерінде жүзеге асырылған.

Except for factorization, all previous properties of K[X] are effective, since their proofs, as sketched above, are associated with algorithms for testing the property and computing the polynomials whose existence are asserted. Moreover these algorithms are efficient, as their computational complexity is a quadratic function of the input size. The situation is completely different for factorization: the proof of the unique factorization does not give any hint for a method for factorizing. Already for the integers, there is no known algorithm running on a classical computer for factorizing them in polynomial time. This is the basis of the RSA cryptosystem, widely used for secure Internet communications. In the case of K[X], the factors, and the methods for computing them, depend strongly on K. Over the complex numbers, the irreducible factors (those that cannot be factorized further) are all of degree one, while, over the real numbers, there are irreducible polynomials of degree 2, and, over the rational numbers, there are irreducible polynomials of any degree. For example, the polynomial is irreducible over the rational numbers, is factored as over the real numbers and, and as over the complex numbers. The existence of a factorization algorithm depends also on the ground field. In the case of the real or complex numbers, Abel–Ruffini theorem shows that the roots of some polynomials, and thus the irreducible factors, cannot be computed exactly. Therefore, a factorization algorithm can compute only approximations of the factors. Various algorithms have been designed for computing such approximations, see Root finding of polynomials. There is an example of a field K such that there exist exact algorithms for the arithmetic operations of K, but there cannot exist any algorithm for deciding whether a polynomial of the form is irreducible or is a product of polynomials of lower degree. On the other hand, over the rational numbers and over finite fields, the situation is better than for integer factorization, as there are factorization algorithms that have a polynomial complexity. They are implemented in most general purpose computer algebra systems.

Минималды көптік

Егер θ – ассоциативтік K алгебрасының L элементі болса, онда θ бойынша полиномды бағалау – K[X]-тен L-ге дейінгі бірегей алгебралық гомоморфизм φ болып табылады, ол X-ті θ-ға бейнелейді және K элементтеріне өзгеріс енгізбейді (K-дағы сәйкестік бейнелеуі). Ол кез келген полиномда X-ті θ-мен алмастырудан тұрады. Яғни, осы бағалау гомоморфизмінің бейнесі – θ арқылы құрылған субальгебра болып табылады, ол міндетті түрде коммутативті. Егер φ инъективті болса, θ арқылы құрылған субальгебра K[X]-ке изоморфты болады. Бұл жағдайда бұл субальгебраны көбінесе K[θ] деп белгілейді. Белгілеудің екіұштылығы, әдетте, изоморфизмнің арқасында зиянсыз. Егер бағалау гомоморфизмі инъективті болмаса, онда оның ядросы нөлден өзгеше идеал болып табылады, ол X-ті θ-мен алмастырғанда нөлге айналатын барлық полиномдардан тұрады. Бұл идеал кейбір бас коэффициенті біреу болатын полиномның барлық еселігінен тұрады, ол θ-ның минималды полиномы деп аталады. «Минималды» термині оның дәрежесі идеал элементтерінің дәрежелері арасында ең төменгісі болғандықтан туындайды. Минималды полиномдар қарастырылатын екі негізгі жағдай бар. Далалар теориясы мен сандар теориясында, егер θ, K коэффициенттері бар полиномның түбірі болса, K-нің L кеңейтілген даласының θ элементі K-ге алгебралық болып табылады. Сондықтан, L – дала болғандықтан, бұл минималды полином K бойынша міндетті түрде толық емес. Мысалы, i кешенді санының минималды полиномы (нақты сандар және рационал сандар бойынша) . Циклотомдық полиномдар – бірлік түбірлерінің минималды полиномдары. Сызықтық алгебрада K үстінен n×n шаршы матрицалар шекті өлшемді ассоциативтік K алгебрасын құрайды (векторлық кеңістік ретінде). Сондықтан бағалау гомоморфизмі инъективті бола алмайды, және әр матрицада минималды полином болады (міндетті түрде толық емес). Кейли-Гамильтон теоремасы бойынша, бағалау гомоморфизмі матрицаның сипаттамалық полиномын нөлге бейнелейді. Осыдан минималды полином сипаттамалық полиномды бөледі, демек, минималды полиномның дәрежесі ең көп дегенде n-ге тең.

If θ is an element of an associative K algebra L, the polynomial evaluation at θ is the unique algebra homomorphism φ from K[X] into L that maps X to θ and does not affect the elements of K itself (it is the identity map on K). It consists of substituting X with θ in every polynomial. That is,

The image of this evaluation homomorphism is the subalgebra generated by θ, which is necessarily commutative. If φ is injective, the subalgebra generated by θ is isomorphic to K[X]. In this case, this subalgebra is often denoted by K[θ]. The notation ambiguity is generally harmless, because of the isomorphism. If the evaluation homomorphism is not injective, this means that its kernel is a nonzero ideal, consisting of all polynomials that become zero when X is substituted with θ. This ideal consists of all multiples of some monic polynomial, that is called the minimal polynomial of θ. The term minimal is motivated by the fact that its degree is minimal among the degrees of the elements of the ideal. There are two main cases where minimal polynomials are considered. In field theory and number theory, an element θ of an extension field L of K is algebraic over K if it is a root of some polynomial with coefficients in K. The minimal polynomial over K of θ is thus the monic polynomial of minimal degree that has θ as a root. Because L is a field, this minimal polynomial is necessarily irreducible over K. For example, the minimal polynomial (over the reals as well as over the rationals) of the complex number i is The cyclotomic polynomials are the minimal polynomials of the roots of unity. In linear algebra, the n×n square matrices over K form an associative K algebra of finite dimension (as a vector space). Therefore the evaluation homomorphism cannot be injective, and every matrix has a minimal polynomial (not necessarily irreducible). By Cayley–Hamilton theorem, the evaluation homomorphism maps to zero the characteristic polynomial of a matrix. It follows that the minimal polynomial divides the characteristic polynomial, and therefore that the degree of the minimal polynomial is at most n.

Көптамалық өрнегі

Полиномиялық өрнек – скалярлармен (K элементтері), белгісіздермен және қосу, көбейту және нөлге тең немесе одан жоғары бүтін дәрежеге көтеру операторлары арқылы құрастырылған өрнек. Бұл операциялардың бәрі полиномиялық өрнекте анықталғандықтан, ол полиномияны білдіреді, яғни K жиынының елементі. Полиномияны мономиалдардың сызықтық комбинациясы ретінде беру – бұл полиномиялық өрнектің ерекше жағдайы, ол көбінесе канондық форма, нормалды форма немесе полиномияның ашық түрі деп аталады. Берілген полиномиялық өрнек үшін, оның құрауыштарының арасындағы қосындыларды көбейту арқылы тарату заңымен кеңейту арқылы ұсынылған полиномияның ашық түрін есептеуге болады, содан кейін коммутативтілік қасиетін (екі скалярдың көбейтіндісінен басқа) және нәтижедегі қосындының мүшелерін скаляр мен мономиалдың көбейтіндісіне түрлендіру үшін ассоциативтілік қасиетін қолдануға болады; содан кейін ұқсас мүшелерді топтастыру арқылы канондық формаға жетуге болады. Полиномиялық өрнек пен оның ұсынуы мүмкін полиномия арасындағы айырмашылық салыстырмалы түрде жақында пайда болды және негізінен компьютерлік алгебраның дамуымен байланысты, мысалы, екі полиномиялық өрнек бірдей полиномияны білдіретінін тексеру күрделі есептеу болуы мүмкін.

Категориялық сипаттама

Егер K коммутативті сақина болса, K[X1, …, Xn] полиномиялық сақинасы мынадай әмбебап қасиетке ие: әрбір коммутативті K алгебрасы A үшін және A элементтерінің әрбір n-тік (x1, …, xn) үшін K[X1, …, Xn] -ден A-ға дейін бірегей алгебралық гомоморфизм бар, ол әр Xᵢ-ді тиісті xᵢ-ге бейнелейді. Бұл гомоморфизм – әр полиномиалда Xᵢ орнына xᵢ-ді қоюдан тұратын бағалау гомоморфизмі. Бұл, әр әмбебап қасиет сияқты, осы жұпты бірегей изоморфизмге дейін сипаттайды. Бұл қосымша функторлар тұрғысынан да түсіндірілуі мүмкін. Нақтырақ айтқанда, SET және ALG жиындар мен коммутативті K алгебраларының санаттары болсын (мұнда және келесіде морфизмдер тривиальды түрде анықталады). Алгебраларды олардың негізгі жиындарына бейнелейтін ұмытылмас функтор бар. Екінші жағынан, K[X] бейнелеуі функторды кері бағытта анықтайды. (Егер X шексіз болса, K[X] – X элементтерінің шекті санындағы барлық полиномиалдардың жиыны.) Полиномиялық сақинаның әмбебап қасиеті F және POL – қосымша функторлар екенін білдіреді. Яғни, биекция бар. Бұл полиномиялық сақиналар еркін коммутативтік алгебралар деп айту арқылы да білдірілуі мүмкін, өйткені олар коммутативтік алгебралар санатындағы еркін объектілер. Сол сияқты, бүтін сан коэффициенттері бар полиномиялық сақина – оның айнымалылар жиынындағы еркін коммутативтік сақина, өйткені коммутативтік сақиналар мен коммутативтік алгебралар бүтін сандар бойынша бірдей.

Бірнеше белгісіздер өрісте

Көп айнымалылы полиномдық сақиналар өрісте инвариантты теория және алгебралық геометрияда негізгі рөл атқарады. Олардың кейбір қасиеттерін, мысалы жоғарыда сипатталғандарын, бір ғана белгісізке келтіруге болады, бірақ бұл әрқашан мүмкін болмайды. Атап айтқанда, геометриялық қолданыстарға байланысты, көптеген қызықты қасиеттер белгісіздердің аффиндік немесе проективтік түрлендірулеріне қатысты өзгермейтін болуы керек. Бұл көбінесе белгісіздердің біреуін белгісіздер бойынша рекурсия үшін таңдау мүмкін еместігін білдіреді. Безоу теоремасы, Гильберттің Нөлдік теоремасы және Якобтың болжамы – өрістегі көп айнымалы полиномдарға тән ең белгілі қасиеттердің қатарында.