حلقه چندجملهای
حلقه چندجملهای (به انگلیسی: polynomial ring) یا جبر حلقهای، در ریاضیات، بخصوص در شاخه جبر، یک حلقه است (از این رو یک جبر جابجایی هم هست) که توسط مجموعهای از چندجملهایها که یک یا چند نامعین دارند (که به صورت سنتی متغیر نام دارند) تشکیل شده که ضرایبشان در حلقهٔ دیگری است که معمولاً یک میدان است.
معمولاً اصطلاح «حلقه چندجملهای» به صورت ضمنی به حالت خاصی از حلقه چندجملهای اشاره دارد که یک نامعین روی یک میدان دارد. این حلقههای چندجملهای به این علت مهم هستند که ویژگیهای مشترکی زیادی است که با حلقه اعداد صحیح دارند.
حلقه چندجملهایها در شاخههای مختلفی از ریاضیات همچون نظریه اعداد، جبر جابجایی، و هندسه جبری ظهور پیدا میکنند. در نظریه حلقهها، برای تعمیم بعضی ویژگیهای حلقههای چندجملهای، کلاسهای مختلفی از حلقهها معرفی شدهاند که شامل: حوزه تجزیه یکتا، حلقههای منظم، حلقههای گروهی، حلقههای سریهای توانی صوری، چند جملهایهای Ore و حلقههای مدرج هستند.
یک مفهوم بسیار مرتبط، حلقه توابع چندجملهای روی فضای برداری، و به صورت کلیتر حلقه توابع منظم روی واریته جبری است.
تعریف (حالت تک متغیره)
حلقه چند جملهای K[X]، با X روی یک میدان (یا به صورت کلیتر حلقه جابجایی) K را میتوان به صورت مجموعهای از عبارات، که به آن چندجملهای در X گفته میشود، به این حالت تعریف کرد (تعاریف معادل دیگری هم وجود دارد که از آنها هم استفاده معمول میشود):
که در آن p0, p1, …, pm یعنی ضرایب p عناصر K هستند و pm ≠ ۰ اگر m > 0 باشد و
دو چند جملهای زمانی با هم برابراند که ضرایب متناظر با هرکدام از Xها در هردو با هم برابر باشند.
حلقه چندجملهای K[X] را میتوان به این صورت دید، که از میدان K با اضافهکردن یک عنصر جدید X ایجاد شده که این X برای K خارجی است و با همه عناصر K شرکتپذیر بوده و خاصیت ویژه دیگری هم ندارد (از همین میتوان برای تعریفکردن حلقههای چندجملهای بهره جست).
حلقه چندجملهای در X روی K به یک جمع، یک ضرب و یک ضرب نردهای مجهز است که آن را یک جبر جابجایی میکند. این عملیات براساس قواعد معمولی برای دستکاری عبارات جبری تعریف شدهاند. بخصوص اگر:
و:
آنگاه:
و:
که در آن k = max(m, n) و l = m + n
و
در فرمولهای فوق، میتوان با افزودن «جملات ساختگی» با ضرایب صفر، چندجملهایهای p و q را توسعه داد به گونهای که pi و qiهای ظاهر شده در این عبارت تعریف شده باشند. بخصوص وقتی که m < n باشد آنگاه برای m < i ≤ n داریم pi = ۰.
ضرب اسکالر حالت خاصی از همان ضرب عمومی است که در آن p = p0 به جمله ثابت (جملهای که مستقل از X است) کاهش یافتهاست؛ یعنی:
میتوان به راحتی راستیآزمایی کرد که سه عملیات بالا در اصول موضوعه جبر جابجایی روی میدان K صدق میکنند. ازاینرو، به حلقههای چند جملهای، جبرهای چندجملهای نیز گفته میشود.
تعریف معادل دیگری که شهود کمتری دارد اما معمولاً ارجح است، چون راحتتر میشود آن را ساخت، به این صورت که چندجملهایها به صورت یک دنباله بینهایت (p0, p1, p2, …) از عناصر K تعریف شوند که این ویژگی را دارند که تنها تعداد متناهی از آنها ناصفرند، یا بهطور معادل، دنبالهای که برای آن یک m وجود دارد که برای n > m رابطه pn = ۰برقرار است. در این حالت، p0 و X را به ترتیب به عنوان نمادهای جایگزین برای دنبالههای (p0, 0, 0, …) و (0, 1, 0, 0, …) در نظر گرفتهایم. آنگاه با کمی دقت میتوان فهمید که با کمک این قواعد عملیاتی، یک عبارت به صورت زیر:
دارای یک نماد جایگزین دنبالهای به صورت زیر است:
- (p0, p1, p2, …, pm, 0, 0, …).
واژهشناسی
فرض کنید:
یک چندجمله ای ناصفر باشد که در آن
یک چندجمله ای ثابت، یا چندجمله ای صفر است، یا چندجمله ای از درجه صفر.
یک چندجمله ای صفر تکین است اگر ضریب پیشروی آن ۱ باشد.
اگر دو چندجمله ای
و بر روی یک میدان یا بهطور کلی تر یک حوزه صحیح داریم:
سریعاً نتیجه میشود که اگر
در نتیجه اگر
دو چندجمله ای با هم مرتبط (به انگلیسی: Associated) هستند اگر برای هرکدام از آنها یک عضو معکوس پذیر (به انگلیسی: Unit) وجود داشته باشد که با ضرب در آن به دیگری تبدیل شود.
هر چندجمله ای ناصفر بر روی یک میدان مرتبط با یک چندجمله ای منحصر به فرد است.
اگر دو چندجمله
یک چندجملهای تحویل ناپذیر است اگر نتوان آن را به صورت ضرب دو چندجملهای غیرثابت نوشت یا بهطور معادل، اگر مقسوم علیههای آن یا چندجملهایهای ثابت باشند یا درجه برابر با چندجملهای اصلی داشته باشند.
ارزیابی چندجملهای
فرض کنید K یک میدان باشد، یا به صورت کلیتر، یک حلقه جابجایی باشد، و R یک حلقه شامل K باشد. برای هر چندجملهای p در K[X] و هر عنصر a در R، جایگزینی X با a در p یک عنصر R را تعریف میکند، که به صورت P(a) نمایش داده میشود. این عنصر با حمل R پس از جایگزینی عملیات نشان دادهشده توسط عبارت چندجملهای به دست میآید. به این محاسبه «ارزیابی» P در a گفته میشود. برای مثال، اگر داشته باشیم
آنوقت داریم
(در مثال اول R = K و در مثال دوم R = K[X]). جایگزینی X با خودش منجر زیر میشود
که این موضوع شرح میدهد چرا دو جمله «فرض کنید P یک چندجملهای باشد» و «فرض کنید P(X) یک چندجملهای باشد» با هم معادل هستند.
تابع جندجملهای تعریف شده توسط چندجملهای P تابعی از K به K است که توسط
برای هر a در R، ارزیابی در a، که همان نگاشت
- برای هر حلقه R شامل K، و برای هر عنصر a از R، یک همریختی جبری یکتا از K[X] به R وجود دارد، که K را ثابت نگهمیدارد و X را به a نگاشت میدهد.
برای همه خاصیتهای جامع، این موضوع (به دلیل یکریختی یکتا) تعریف کننده جفت (K[X], X) است، و از این رو میتوان آن را به عنوان تعریف K[X] در نظر گرفت.
چندجملهایهای تکمتغیره روی یک میدان
اگر K یک میدان باشد، حلقه چندجملهای K[X] ویژگیهای زیادی دارد که مشابه حلقه اعداد صحیح
بیشتر ویژگیهای K[X] که در این بخش فهرست شدهاست، اگر K میدان نباشد، یا اگر چندجملهایها چندین نامعین داشته باشند، درست باقی نمیماند.
ضرب چندجمله ایهای تنک
تعریف و نمایش
در بسیاری از کاربردها پیش میآید که مجبور به نگهداری چندجملهایهایی هستیم که با این که درجهٔ بزرگی دارند ولی تعداد بسیاری از ضرایب آنها صفر میباشد. که استفاده از فرمت نگهداری فرض شده در ابتدای این نوشته برای چنین چند جملههایی بسیار ناکاراست. به چنین چندجملهایهایی، تنک میگوییم و برای اعمال روی آنها الگوریتمهای بسیاری پیشنهد شده که از ارزش بالایی هم برخوردارند. یک مثال از چنین چندجملهایهایی در زیر آمدهاست:
به همین دلیل به جای استفاده از آرایه برای نمایش این چندجملهایها از لیست پیوندی استفاده میشود. به این صورت که هر تک جمله را با یک واحد زبان برنامهنویسی که شامل درجه و ضریب آن باشد نمایش میدهیم و به آن گره میگوییم (مثلاً یک struct یا record) و این گرهها را در یک لیست پیوندی که به ترتیب درجه آنها ار کوچک به بزرگ مرتب شدهاست، نگه میداریم. برای مثال بالا، استفاده از آرایه به حدود ۱۰۱ واحد حافظه نیاز دارد در حالی با نمایش اخیر میتوان آن را با تنها ۱۶ واحد حافظه (حداکثر) نمایش داد زیرا که هر گره در لیست پیوندی اگر شامل توان و ضریب و دو اشاره جلو و عقب باشد به اندازهٔ ۴ واحد فضا مصرف میکند و با سه گره نیز چندجملهای فوق قابل نمایش است به علاوهٔ یک گره احتمالی برای سرلیست.
الگوریتمهای چندجمله ایهای تنک
در مورد این طرز نمایش چندجمله ای، نمیتوان الکوریتمهای معمول را به کار برد زیرا بسیاری از الگوریتمها فرض میکنند که دسترسی تصادفی سریع به هر یک از ضرایب دارند؛ مثلاً نمیتوان از تبدیل فوریه آن طور که اینجا مطرح شد برای ضرب چندجمله ایهای تنک استفاده کنیم.
با این حال الکوریتم استراسن که در بالا بحث شد را میتوان با تغییر جزئی برای چنین نمایشی نیز به کار برد زیرا در طی آن تنها نیاز است که با یک بار عبور از روی چندجمله ای، وسط آن را پیدا کرد و سپس آن را به دو بخش تقسیم کرد و الگوریتم را بهطور بازگشتی ادامه داد. واضح است که چنین تقسیمی به زمان اجرای الگوریتم نمیافزاید (از لحاظ تحلیل مجانبی) ولی برخی مسائل جدید در پیادهسازی را پیش میکشد مانند حالات تهی یا نصف تهی. که در بدترین حالت با افزودن تعداد ثابتی گره با ضریب صفر و اضاه کردن حالات پایه برای زمانی که چلیست پیوندی نمایش دهندهٔ چندجملهای تهی است، به راحتی میتوان این الگوریتم را روی چندجمله ایهای تنک نیز اجرا کرد.
الگوریتمهای پیشرفته تر برای ضرب چندجملههای تنک که سریع تر نیز عمل میکنند و مثلاً در برخی از آنها از داده ساختار هیپ برای نگهداری چندجمله ایها و نمایش آنها استفاده میشود، نیز وجود دارند ولی در اینجا به جزییات بیشتری از آنها نمیپردازیم.
جستارهای وابسته
- تبدیل فوریه گسسته
- الگوریتم
- چندجمله ای
- ضرب
- لیست پیوندی
منابع
- ↑ Herstein p. 153
- ↑ Herstein, Hall p. 73
- ↑ Lang p. 97
- ↑ Herstein p. 154
- ↑ Lang p.100
- ↑ Anton, Howard; Bivens, Irl C.; Davis, Stephen (2012), Calculus Single Variable, John Wiley & Sons, p. 31, ISBN 978-0-470-64770-7.
- ↑ Sendra, J. Rafael; Winkler, Franz; Pérez-Diaz, Sonia (2007), Rational Algebraic Curves: A Computer Algebra Approach, Algorithms and Computation in Mathematics, vol. 22, Springer, p. 250, ISBN 978-3-540-73724-7.
- ↑ Eves, Howard Whitley (1980), Elementary Matrix Theory, Dover, p. 183, ISBN 978-0-486-15027-7.
- ↑ Herstein p.155, 162
- ↑ Herstein p.162