ផែនទីពណ៌ និងមូលដ្ឋានគ្រឹះ Gröbner

រូបភាពនេះជាកម្មសិទ្ធិរបស់ mathscareers.org.uk ដែលជាអ្នកអនុញ្ញាតដោយប្រើប្រាស់កនុងការងារនេះ។

អត្ថបទដកស្រង់ចេញពី Klein Project Blog

អ្នកនិពន្ធនេះបានចាប់កំណើតនៅកនុងទីក្រុង Marcelo Escudeiro Hernandes។ គាត់បានលើកដោយ “Four Colour Theorem” យើងត្រូវការផាត់ពណ៌នៅលើផែនទីដែតបួនពណ៌បុណ្ណេះ ដោយមិនដាក់ពណ៌ដូចគ្នានៅជិតគ្នានទេ។ ការប្រើសមីការពហុធានិងមូលដ្ឋាន Gröbner យើងអាចកំណត់ថាបើសិនជាមានដែតបីពណ៌នេះក៏គ្រប់គ្រាន់ដែរសម្រាប់ដាក់ពណ៌លើផែនទីមួយដែរ។

១. ផែនទីពណ៌

ទ្រឹស្តីបទពណ៌ទាំងបួនដែលល្បីៗមាននៅកនុងផែនទីទាំងមូល ទាំងនៅកនុងបង្គោលឬនៅកនុងស៊្វែរ អាចជាការដាក់ពណ៌ជាមួយនឹងពណ៌ទាំងបួនដោយមានពណ៌ដូចគ្នាមិនស្ថិតនៅតំបន់ជិតៗគ្នា។ វាជាការងាយស្រួលណាស់កនុងការបង្កើតឧទាហរណ៍នៃផែនទីដែលមិនអាចដាក់ដែតបីពណ៌ ឬក៏នែទៀតដែលអាចធ្វើបាន។ នៅពេលពិចារណាលើវិធីមួយ បើសិនជាមានដែតបីពណ៌នេះក៏គ្រប់គ្រាន់ដែរសម្រាប់ដាក់ពណ៌លើផែនទីមួយដែរ នហើយនៅក៏អាចវិភាគលើការដោះរបព័ន្ធពហុធានៅលើផែនទី។ ពណ៌នីមួយៗ ត្រូវបានតាងដោយឯកតានៃឫសរូប នហើយតំបន់នីមួយៗតាងដោយអថេរ x_i ដូចនេះអាចសន្មតថា តម្លៃមួយកនុងចំណោមតម្លៃទាំងបីក៏ដូចជា ពណ៌មួយកនុងចំណោមពណ៌ទាំងបី។ ដូចនេះយើងបានសមីការ x_i^3 - 1 = 0 សម្រាប់តំបន់នីមួយៗ។

សម្រាប់តំបន់ x_j និង x_k យើងមាន

    \[0 = x_j^3 - x_k^3 = (x_j - x_k)(x_j^2 + x_j x_k + x_k^2).\]

បើសិន x_j និង x_k នៅតំបន់ជិតគ្នាដែតបើតំបន់ជិតគ្នាមិនអាចមានពណ៌ដូចគ្នានេះ នាំដោយ x_j \neq x_k ដូចនេះ នាំដោយ x_j^2 + x_j x_k + x_k^2 = 0។ កនុងវិធីនេះ ផែនទីដែលមាន n តំបន់អាចមានដែតបីពណ៌បុណ្ណេះ នេះយើងមានប្រព័ន្ធសមីការពហុធា៖

    \[\left\{ \begin{array}{l} x_i^3 - 1 = 0, \\ x_j^2 + x_j x_k + x_k^2 = 0 \end{array}\right. \quad (1)\]

ដែល i = 1, \ldots, n ហើយ x_j និង x_k តាងដោយតំបន់ដែលជាបន្ទាប់គ្នា រៀងគ្នា ហើយមានដំណោះស្រាយយ៉ាងហោចណាស់មួយ។

យើងពិចារណាលើផែនទី:

រូបភាព 1
រូបភាព 1

តើវាអាចមានដែតបីពណ៌រឺ? ដើម្បីឆ្លើយនឹងសំណួរ យើងត្រូវដែតផ្ទៀងផ្ទាត់លើប្រព័ន្ធពហុធា (1) ដោយ i = 1, \ldots, 9 ហើយយើងអាចដោះស្រាយបាន

    \[(j,k) \in \{(1,2); (2,3); (2,6); (2,9); (3,4); (3,5); (3,6); (4,5); (5,6); (6,7); (6,9); (7,8); (7,9); (8,9)\}.\]

២. ប្រព័ន្ធសមីការពហុធា

ចម្លើយនៃបញ្ហាជាច្រើននៅកនុងគណិតវិទ្យារឺជាដំណោះស្រាយនៃប្រព័ន្ធសមីការពហុធា ហើយវាមិនមែនជាការងាយស្រួលនទេ។ បើសិនជាប្រព័ន្ធដែលគេឲ្យជាសមីការលីនែអ៊រ យើងអាចដោះស្រាយតាមវិធី Gaussian ឬជំនួសដោយសមីការណាដែលសមមូលនឹងវា ហើយយើងអាចងាយស្រួលកនុងការដោះស្រាយ។ កនុងករណីដែលប្រព័ន្ធពហុធានេះវាមានវិធីសាស្រ្តដោះស្រាយដូចដែលយើងបានពណ៌នាខាងលើ។

យើងកំណត់សំណុំនៃពហុធាដោយ P(n) ដែលដាក់វាជាកត្តារួមជាមួយអញ្ញាត x_1, \ldots, x_n។ នៅឲ្យ f_1, \ldots, f_r ជាសំណុំពហុធាកនុងសំណុំ P(n)។ នេះយើងកំណត់ដោយៈ

    \[I = \langle f_1, \ldots, f_r \rangle = \{ h_1 f_1 + \ldots + h_r f_r \mid h_1, \ldots, h_r \in P(n) \}.\]

ដោយមានទ្រឹស្តីបទមួយរបស់អ្នកគណិតវិទ្យា David Hilbert (2) ដែលនៅថាទ្រឹស្តីបទ Hilbert’s Nullstellensatz និយាយថា ប្រព័ន្ធពហុធានៃ f_1 = \ldots = f_r = 0 អាចមានដំណោះស្រាយ លុះត្រាដែត 1 \notin \langle f_1, \ldots, f_r \rangle ប៉ុន្តែតើយើងអាចត្រូតពិនិត្យលក្ខណ៉យ៉ាងដូចម្ដេច?

ប្រព័ន្ធសមីការទាំងពីរវាពិតជាងាយស្រួលកនុងការផ្ទៀងផ្ទាត់ f_1 = \ldots = f_r = 0 និង g_1 = \ldots = g_s = 0 ដែល f_i, g_j \in P(n) បំពេញលក្ខណ៉

    \[\langle f_1, \ldots, f_r \rangle = \langle g_1, \ldots, g_s \rangle \quad (2)\]

ដែលមានដំណោះស្រាយដូចគ្នា។

ហេតុដូចនេះយុទ្ធសាស្រ្តកនុងការដោះស្រាយប្រព័ន្ធសមីការដែល f_1 = \ldots = f_r = 0 នេះក៏អាចរកពហុធា g_1, \ldots, g_s បានដែរ ដែលបានបំពេញលក្ខណ៉ (2) ហើយវាពិតជាអាចសាកល្បងបានបើសិនជាគេដោយ f \in P(n) ប៉ុន្តែ \langle f_1, \ldots, f_r \rangle មិនមែនសុទ្ធតែជារបស់ P(n) នេះទេ និងដំណោះស្រាយរួម រឺជាការងាយស្រួលណាស់កនុងការរកជាងប្រព័ន្ធសមីការដើម។

ដូចគ្នាដែរ ដែល G = \{g_1, \ldots, g_s\} ត្រូវបានគេរកតាមរយៈទ្រឹស្តីបទមួយកនុងកំឡុងពេលចុងពាក់កណ្ដាលសតវត្សទី១ ដោយអ្នកគណិតវិទ្យា Wolfgang Gröbner រយៈពេលបន្តិចឆ្នាំក្រោយមក សិស្សរបស់គាត់ Bruno Buchberger បានបង្កើតទ្រឹស្តីបទដាល់ការីតីមួយដើម្បីរកវា។ ការបង្កើតទាំងនេះ ត្រូវបានគេនៅថាមូលដ្ឋានគ្រឹះ Gröbner និងទ្រឹស្តីបទដាល់ការីតីរបស់ Buchberger ដើម្បីរកវាជាទ org ្រឹស្តីបទមួយដែសំខាន់កនុងការរកពិជគណិត។

បើសិនជាឧទាហរណ៍មានទម្រង់ I = \langle f_1 \rangle យើងមាន f \in I លុះត្រាដែត f = h_1 f_1 ដែល f ចែកអាច់ដោយ f_1។ ប្រៀបធៀប បើ f \in \langle f_1, \ldots, f_r \rangle លុះត្រាដែត f = h_1 f_1 + \ldots + h_r f_r តាមលក្ខណៈខាងលើ មានភាពស្រដៀងសម្រាប់ការចែក f ដោយ f_1, \ldots, f_r។ ការពិតយើងអាចចែកពហុធាជាមួយអថេរមួយចំនួនដោយសំណុំកំណត់នៃពហុធាទាំងមូល បន្ទាប់មកឯកធាត្រូវបានគេរៀបតាមលំដាប់។

៣. មូលដ្ឋានគ្រឹះ Gröbner

ឯកធា m មួយនៃ P(n) មានធាតុជាទម្រង់ x_1^{a_1} \ldots x_n^{a_n} ដែល a_1, \ldots, a_n ជាចំនួនគត់។ ឯកធា x_1^0 \ldots x_n^0 បានកំណត់ដោយ 1។ កនុងចំណោមឯកធានៃសំណុំ P(n) ត្រូវបានគេរៀបតាមលំដាប់តូចជាងឬស្មើ ដែលមានមួយបំពេញលក្ខណ៉ 1 \leq m និង m_1.m \leq m_2.m កាលណា m_1 \leq m_2 នេះគេអាចយកវានៅអនុវត្តកនុងការចែកដាល់ការីត។

កនុងឧទាហរណ៍ ជាការរៀបតាមលំដាប់សទ្ទុក្រម Lex ដែល x_1^{a_1} \ldots x_n^{a_n} \leq_{Lex} x_1^{b_1} \ldots x_n^{b_n} បើសិនជាមាន 1 \leq i \leq n ដូចនេះ a_i < b_i និង a_j = b_j ដែល j < i។

បើសិនជាលំដាប់នៃឯកធាមិនប្រែប្រួល នេះឯកធាធំបំផុតនៃពហុធា f វាត្រូវបានគេនៅថាកន្ទោមគោលនៃ f ហើយកំណត់សរសេរដោយ \mathrm{lt}(f)។

មូលដ្ឋានគ្រឹះ Gröbner បានឱ្យថា I = \langle f_1, \ldots, f_r \rangle ជាមួយនឹងការឲ្យលំដាប់ឯកធាតាមនិយមន័យ គ្រប់សំណុំ G = \{g_1, \ldots, g_s\} ជាធាតុរបស់ I ដែលកន្ទោមគោលគ្រប់ធាតុនៃសំណុំ I ចែកអាច់និងកន្ទោមគោលនៃធាតុមួយចំនួនរបស់សំណុំ G។ យើងអាចបង្ហាញថាគ្រប់មូលដ្ឋាន Gröbner G នៃ I ជាសំណុំដែលបំពេញលក្ខណ៉ 2។

ដូចនេះ 1 \in I លុះត្រាដែតមានមូលដ្ឋាន Gröbner នៃសំណុំ I មានធាតុមិនសូន្យ នេះ 1 \leq m សម្រាប់គ្រប់ឯកធា m នៃ P(n)។

ឧទាហរណ៍ G = \{f_1\} ជាមូលដ្ឋាន Gröbner នៃ \langle f_1 \rangle ជាមួយនឹងគ្រប់លំដាប់ឯកធាទាំងអស់ ចំណែកឯ G = \{x+y+z-6, x-y+1, x+y-z\} រឺមិនមែនជាមូលដ្ឋាន Gröbner នៃ I = \langle x+y+z-6, x-y+1, x+y-z \rangle ជាមួយនឹងលំដាប់សទ្ទុក្រម ពីព្រោះ

    \[\mathrm{lt}(x+y+z-6-(x-y+1)) = \mathrm{lt}(2y+z-7) = 2y\]

រឺចែកមិនអាច់នឹង

    \[x = \mathrm{lt}(x+y+z-6) = \mathrm{lt}(x-y+1) = \mathrm{lt}(x+y-z).\]

ដើម្បីទទួលយកគំនិតមូលដ្ឋាន Gröbner ជាមួយនឹងការជ្រើសរើសលំដាប់ឯកធា អ្នកអាចអនុវត្តតាមដាល់ការីតីរបស់ Buchberger3។ យើងអាចរកដាល់គោរីតីកនុងការរកមូលដ្ឋាន Gröbner ភាគច្រើនការរកតាមប្រព័ន្ធពិជគណិត។

ជំនួសឲ្យគំនិតរបស់ Gröbner I = \langle x+y+z-6, x-y+1, x+y-z \rangle ជាមួយនឹងលំដាប់សទ្ទុក្រម នេះរឺ G = \{x+y+z-6, 2y+z-7, 2z-6\}។

៤. ដំណោះស្រាយបញ្ហា និង ការអនុវត្តផ្សេងៗ

ប្រព័ន្ធសមីការដែលបានឲ្យកនុងឧទាហរណ៍មានចំនួនកំណត់ជាច្រើននៃដំណោះស្រាយ (មាន ៩ អញ្ញាត ហើយអញ្ញាតនីមួយៗអាចយកតម្លៃមួយ កនុងចំណោមតម្លៃទាំងបី)។ បញ្ហាកំណត់ប្រសិនជាប្រព័ន្ធអាចដោះស្រាយគ្រប់សមីការ កនុងករណីនេះ អាចកំណត់វាបាន។

ការអនុវត្តរបស់ដាល់ការីត Buchberger កនុងប្រព័ន្ធសមីការនៃឧទាហរណ៍ទី១ យើងទទួលបានដូច Gröbner G ដែរ ជាមួយនឹងលំដាប់សទ្ទុក្រមៈ

    \[G = \left\{ \begin{array}{l} x_1^3 - 1;\; x_2^2 + x_2 x_1 + x_1^2;\; x_3^2 + x_3 x_2 - x_2 x_1 - x_1^2; \\ x_4 + x_3 + x_2;\; x_5 - x_2;\; x_6 + x_3 + x_2;\; x_7 - x_2;\; x_8 + x_3 + x_2;\; x_9 - x_3 \end{array} \right\}.\]

ដូចនេះ 1 \notin I ត្រូវនៅនឹងប្រព័ន្ធចម្លើយដែលទទួលបាន។ សមីការរឺៈ

    \[\left\{ \begin{array}{l} x_1^3 - 1 = 0, \\ x_2^2 + x_2 x_1 + x_1^2 = 0, \\ x_5 - x_2 = 0, \\ x_7 - x_2 = 0, \\ x_9 - x_3 = 0 \end{array}\right.\]

តាមការបកស្រាយខាងលើ យើងអាចប្រើប្រាស់ពណ៌សម្រាប់ x_1, x_2 \neq x_1, x_2 = x_5 = x_7 និង x_3 = x_9។

ពណ៌ត្រូវបានតាងដោយឫសទី៣នៃឯកតា ហើយរាល់ការដោះស្រាយ x_4 + x_3 + x_2 = 0, x_6 + x_3 + x_2 = 0 និង x_8 + x_3 + x_2 = 0 រឺជាតម្លៃសល្នតម្នែងពី x_2, x_3 និង x_4 ហើយដូចនេះ x_4 = x_6 = x_8។

ជាចុងក្រោយ 0 = x_3^2 + x_3 x_2 - x_2 x_1 - x_1^2 = (x_3 + x_2 + x_1)(x_3 - x_1) ឲ្យយើងនូវលទ្ធផលពីររឺ x_3 + x_2 + x_1 = 0 ឬ x_3 - x_1 = 0 នេះ x_1, x_2 និង x_3 យកពណ៌ផ្សេងគ្នា ឬ x_1 = x_3។ ដូចនេះយើងរកដោយចំលាស់ពណ៌នេះរាល់ដំណោះស្រាយអាចធ្វើបាន៖

រូបភាព 2
រូបភាព 2

មូលដ្ឋាន Gröbner ក៏អាចប្រើដើម្បីធ្វើប្រមាណវិធីដោយសុក្រិត្យ បម្លែងសមីការប៉ារ៉ាម៉ែត នៅជាសមីការមិនប៉ារ៉ាម៉ែត ដើម្បីរកពហុធាតូចបំផុតនៃចំនួនពិជគណិត ទ្រឹស្តីបទផ្សេងៗនៃធរណីមាត្រអឺក្លីត ការសាងសង់សំណង់និងការដោះរូបនៃល្បែង Sudoku ៕

ឯកសារយោង

(1) http://www.ipv.pt/millenium/Millenium24/12.pdf

(2) http://www.mat.uniroma1.it/people/manetti/dispense/nullstellen.pdf

(3) https://www.risc.jku.at/people/buchberg/papers/1970-00-00-A.english.pdf

(4) Adams, W. and Loustaunau, P., An Introduction to Gröbner Basis, AMS, Providence RI (1994).

(5) Cox, D; Little, J. and O’Shea, D., Ideals, Varieties and Algorithms, 2nd edition, Springer-Verlag, New York, (1996).

(6) Hernandes, M. E., Um Primeiro Contato com Bases de Gröbner, 28°. Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro, (2011).

Leave a Reply

អាសយដ្ឋាន​អ៊ីមែល​របស់​អ្នក​នឹង​មិន​ត្រូវ​ផ្សាយ​ទេ។ វាល​ដែល​ត្រូវ​ការ​ត្រូវ​បាន​គូស *