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

រូបភាពនេះជាកម្មសិទ្ធិរបស់ mathscareers.org.uk ដែលជាអ្នកអនុញ្ញាតអោយប្រើប្រាស់ក្នុងការងារនេះ។ អ្នកនិពន្ធនេះបានចាប់កំណើតនៅក្នុងទីក្រុង Marcelo Escuderio Hermandes។ គាត់បានល្បីដោយ “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_jx_k+x_k^2)$ ។ បើសិន $x_j$ និង $x_k$ នៅតំបន់ជិតគ្នាតែបើតំបន់ជិតគ្នាមិនអាចមានពណ៌ដូចគ្នានោះ នាំអោយ $x_j\neq x_k$ ដូចនេះ នាំអោយ $x_j^2+x_jx_k+x_k^2=0$ ។ ក្នុងវិធីនេះ ផែនទីដែលមាន $n$ តំបន់អាចមាន តែបីពណ៌ប៉ុណ្ណោះ នោះយើងមានប្រព័ន្ធសមីការពហុធា៖

$\begin{cases}x_i^3-1=0\\x_j^2+x_jx_k+x_k^2=0\end{cases}$

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

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

តើវាអាចមានតែបីពណ៌រឺ? ដើម្បីឆ្លើយនឹងសំនួរ យើងត្រូវតែផ្ទៀងផ្ទាត់លើប្រព័ន្ធពហុធា (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_1f_1+\cdots+h_rf_r\mid h_1,\ldots,h_r\in P(n)\}$

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

ប្រព័ន្ធសមីការទាំងពីរវាពិតជាងាយស្រួលក្នុងការផ្ទៀងផ្ទាត់ $f_1=\cdots=f_r=0$ និង $g_1=\cdots=g_s=0$ ដែល $f_i,g_j\in P(n)$ បំពេញលក្ខខណ្ឌ (2) $\langle f_1,\ldots,f_r\rangle=\langle g_1,\ldots,g_s\rangle$ ដែលមានដំណោះស្រាយដូចគ្នា។

ហេតុដូច្នេះយុទ្ធសាស្ត្រក្នុងការដោះស្រាយប្រព័ន្ធសមីការដែល $f_1=\cdots=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 Bucherger បានបង្កើត ទ្រឹស្ដីបទអាល់ការីតមួយដើម្បីគណនាវា ។ ការបង្កើតទាំងនេះ ត្រូវបានគេហៅថា មូលដ្ឋានគ្រឹះ Gröbner និងទ្រឹស្ដីបទអាល់ការីតរបស់ Buchberger ដើម្បីគណនា វាជាទ្រឹស្ដីបទមួយដ៏សំខាន់ក្នុងការគណនាពិជគណិត។

បើសិនជាឧទាហរណ៍មានទម្រង់ $I=\langle f_1\rangle$ យើងមាន $f\in I$ លុះត្រាតែ $f=h_1f_1$ ដែល $f$ ចែកដាច់ដោយ $f_1$ ។ ប្រៀបធៀប បើ $f\in\langle f_1,\ldots,f_r\rangle$ លុះត្រាតែ $f=h_1f_1+\cdots+h_rf_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\preceq m$ និង $m_1.m\preceq m_2.m$ កាលណា $m_1\preceq m_2$ នោះគេអាចយកវាទៅអនុវត្តក្នុងការចែកអាល់ការីត ។

ក្នុងឧទាហរណ៍ ជាការរៀបតាមលំដាប់សទ្ទានុក្រម $\preceq_{Lex}$ ដែល $x_1^{a_1}\ldots x_n^{a_n}\preceq_{Lex}x_1^{b_1}\ldots x_n^{b_n}$ បើសិនជាមាន $1\leqslant i\leqslant n$ ដូចនេះ $a_i< b_i$ និង $a_j=b_j$ ដែល $j< i$ បើសិនជាលំដាប់នៃឯកធាមិនប្រែប្រួល នោះឯកធាធំបំផុតនៃពហុធា $f$ វាត្រូវបានគេហៅថាកន្សោមគោលនៃ $f$ ហើយកំណត់សរសេរដោយ $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\preceq 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$ ជាមួយនឹងលំដាប់សទ្ទានុក្រម ពីព្រោះ $lt(x+y+z-6-(x-y+1))=lt(2y+z-7)=2y$ គឺចែកមិនដាច់នឹង $x=lt(x+y+z-6)=lt(x-y+1)=lt(x+y-z)$ ។

ដើម្បីទទួលយកគំនិតមូលដ្ឋាន Gröbner ជាមួយនឹងការជ្រើសរើសលំដាប់ឯកធា អ្នកអាចអនុវត្តតាមអាល់ការីតរបស់ Buchberger (3) ។ យើងអាចរកអាល់ហ្គោរីតក្នុងការគណនាមូលដ្ឋាន 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\}$ ។

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

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

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

$G=\{x_1^3-1;\ x_2^2+x_2x_1+x_1^2;\ x_3^2+x_3x_2-x_2x_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\}$

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

$\begin{cases}x_1^3-1=0\\x_2^2+x_2x_1+x_1^2=0\\x_5-x_2=0\\x_7-x_2=0\\x_9-x_3=0\end{cases}$

តាមការបកស្រាយខាងលើ យើងអាចប្រើគ្រប់ពណ៌សម្រាប់ $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_3x_2-x_2x_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$ ។ ដូច្នេះយើងរកដោយចំលាស់ពណ៌នោះរាល់ដំណោះស្រាយអាចធ្វើបានៈ

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

ឯកសារយោង

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

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

(3) http://www.rise.jku.at/buchberg/papers/1970-00-00-Aenglsih.pdf

(4) Adams, W. and Loustaunau, P., An Introduction to Grobner Basis AMS, Providence Rl (1994).

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

(6) Hermandes, H, E., Um Primeiro Contato com Bases de Grobner, 28⁰. Coloqui Brasileiro de Matematica, IMPA, Rio de Janeiro, (2011).

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

Related

Leave a ReplyCancel Reply

Share this:

Related

Leave a ReplyCancel Reply