حلقه چندجمله‌ای
حلقه چندجمله‌ای یا جبر حلقه‌ای، در ریاضیات، بخصوص در شاخه جبر، یک حلقه است (از این رو یک جبر جابجایی هم هست) که توسط مجموعه‌ای از چندجمله‌ای‌ها که یک یا چند نامعین دارند (که به صورت سنتی متغیر نام دارند) تشکیل شده که ضرایبشان در حلقهٔ دیگری است که معمولاً یک میدان است.
معمولاً اصطلاح «حلقه چندجمله‌ای» به صورت ضمنی به حالت خاصی از حلقه چندجمله‌ای اشاره دارد که یک نامعین روی یک میدان دارد. این حلقه‌های چندجمله‌ای به این علت مهم هستند که ویژگی‌های مشترکی زیادی است که با حلقه اعداد صحیح دارند.
حلقه چندجمله‌ای‌ها در شاخه‌های مختلفی از ریاضیات همچون نظریه اعداد، جبر جابجایی، و هندسه جبری ظهور پیدا می‌کنند. در نظریه حلقه‌ها، برای تعمیم بعضی ویژگی‌های حلقه‌های چندجمله‌ای، کلاس‌های مختلفی از حلقه‌ها معرفی شده‌اند که شامل: حوزه تجزیه یکتا، حلقه‌های منظم، ، حلقه‌های سری‌های توانی صوری، و هستند.
یک مفهوم بسیار مرتبط، روی فضای برداری، و به صورت کلی‌تر روی واریته جبری است.
حلقه چند جمله‌ای ، با روی یک میدان (یا به صورت کلی‌تر حلقه جابجایی) را می‌توان به صورت مجموعه‌ای از عبارات، که به آن چندجمله‌ای در گفته می‌شود، به این حالت تعریف کرد (تعاریف معادل دیگری هم وجود دارد که از آن‌ها هم استفاده معمول می‌شود):
که در آن یعنی ضرایب عناصر هستند و اگر باشد و formula_2 نمادهایی هستند که به عنوان «توان» شناخته شده و از همان قواعد معمول به توان رساندن تبعیت می‌کنند، یعنی: formula_3 و formula_4 و برای هر عدد صحیح نامنفی و داریم: formula_5. نماد را نامعین یا متغیر می‌نامند (اصطلاح «"متغیر»" از اصطلاح‌شناسی توابع چندجمله‌ای می‌آید. با این حال، در اینجا هیچ مقداری (غیر از خودش) اختیار نمی‌کند و نمی‌تواند تغییر کند و در حلقه چندجمله‌ای "ثابت" است).
دو چند جمله‌ای زمانی با هم برابراند که ضرایب متناظر با هرکدام از ‌ها در هردو با هم برابر باشند.
حلقه چندجمله‌ای را می‌توان به این صورت دید، که از میدان با اضافه‌کردن یک عنصر جدید ایجاد شده که این برای خارجی است و با همه عناصر شرکت‌پذیر بوده و خاصیت ویژه دیگری هم ندارد (از همین می‌توان برای تعریف‌کردن حلقه‌های چندجمله‌ای بهره جست).
حلقه چندجمله‌ای در روی به یک جمع، یک ضرب و یک مجهز است که آن را یک جبر جابجایی می‌کند. این عملیات براساس قواعد معمولی برای دستکاری عبارات جبری تعریف شده‌اند. بخصوص اگر:
و:
آنگاه:
و:
که در آن و
و
در فرمول‌های فوق، می‌توان با افزودن «جملات ساختگی» با ضرایب صفر، چندجمله‌ای‌های و را توسعه داد به گونه‌ای که و ‌های ظاهر شده در این عبارت تعریف شده باشند. بخصوص وقتی که باشد آنگاه برای داریم .
ضرب اسکالر حالت خاصی از همان ضرب عمومی است که در آن به "جمله ثابت" (جمله‌ای که مستقل از است) کاهش یافته‌است؛ یعنی:
می‌توان به راحتی راستی‌آزمایی کرد که سه عملیات بالا در اصول موضوعه جبر جابجایی روی میدان صدق می‌کنند. ازاین‌رو، به حلقه‌های چند جمله‌ای، "جبرهای چندجمله‌ای" نیز گفته می‌شود.
تعریف معادل دیگری که شهود کمتری دارد اما معمولاً ارجح است، چون راحت‌تر می‌شود آن را ساخت، به این صورت که چندجمله‌ای‌ها به صورت یک دنباله بی‌نهایت از عناصر تعریف شوند که این ویژگی را دارند که تنها تعداد متناهی از آن‌ها ناصفرند، یا به‌طور معادل، دنباله‌ای که برای آن یک وجود دارد که برای رابطه برقرار است. در این حالت، و را به ترتیب به عنوان نمادهای جایگزین برای دنباله‌های و در نظر گرفته‌ایم. آنگاه با کمی دقت می‌توان فهمید که با کمک این قواعد عملیاتی، یک عبارت به صورت زیر: دارای یک نماد جایگزین دنباله‌ای به صورت زیر است:
فرض کنید:
یک چندجمله ای ناصفر باشد که در آن formula_15 formula_1 "جمله ثابت" چندجمله ای formula_10 است. در چند جمله ای‌های صفر این ثابت صفر است (البته ممکن است در حالت‌های دیگر هم صفر باشد). "درجه" ی formula_10 که به صورت formula_19 نوشته می‌شود formula_19 است. این مقدار برابر بزرگترین formula_21 یی است که ضریب formula_22 صفر نباشد. "ضریب پیشرو" ی formula_10، برابر formula_24 است. در حالت خاص چندجمله ای‌های صفر که تمام ضرایب آن صفر است، چندجمله ای پیشرو تعریف نشده و درجه را اغلب تعریف نشده، برابر -1 یا برابر formula_25 تعریف می‌کنند.
یک "چندجمله ای ثابت"، یا چندجمله ای صفر است، یا چندجمله ای از درجه صفر.
یک چندجمله ای صفر تکین است اگر ضریب پیشروی آن ۱ باشد.
اگر دو چندجمله ای formula_10 و formula_11 داده شده باشند خواهیم داشت:
formula_28
و بر روی یک میدان یا به‌طور کلی تر یک حوزه صحیح داریم:
formula_28
سریعاً نتیجه می‌شود که اگر formula_30 یک حوزه صحیح باشد آنگاه formula_31 نیز حوزه صحیح است.
در نتیجه اگر formula_30 یک حوزه صحیح باشد، یک چندجمله ای دارای معکوس ضربی است اگر و تنها اگر ثابت باشند، و آن ثابت در formula_30 معکوس ضربی داشته باشد.
دو چندجمله ای با هم مرتبط هستند اگر برای هرکدام از آن‌ها یک عضو معکوس پذیر وجود داشته باشد که با ضرب در آن به دیگری تبدیل شود.
هر چندجمله ای ناصفر بر روی یک میدان مرتبط با یک چندجمله ای منحصر به فرد است.
اگر دو چندجمله formula_10 و formula_11 داده شده باشد، می‌گویند formula_10 مقسوم علیه formula_11 است، یا formula_10 چندجمله ای formula_11 را تقسیم می‌کند یا formula_11 ضریبی از formula_10 است اگر چندجمله ای formula_42 وجود داشته باشد به گونه ای که formula_43.
یک چندجمله‌ای تحویل ناپذیر است اگر نتوان آن را به صورت ضرب دو چندجمله‌ای غیرثابت نوشت یا به‌طور معادل، اگر مقسوم علیه‌های آن یا چندجمله‌ای‌های ثابت باشند یا درجه برابر با چندجمله‌ای اصلی داشته باشند.
فرض کنید یک میدان باشد، یا به صورت کلی‌تر، یک حلقه جابجایی باشد، و یک حلقه شامل باشد. برای هر چندجمله‌ای در و هر عنصر در ، جایگزینی با در یک عنصر را تعریف می‌کند، که به صورت نمایش داده می‌شود. این عنصر با حمل پس از جایگزینی عملیات نشان داده‌شده توسط عبارت چندجمله‌ای به دست می‌آید. به این محاسبه «ارزیابی» در گفته می‌شود. برای مثال، اگر داشته باشیم آنوقت داریم (در مثال اول و در مثال دوم ). جایگزینی با خودش منجر زیر می‌شود
که این موضوع شرح می‌دهد چرا دو جمله «فرض کنید یک چندجمله‌ای باشد» و «فرض کنید یک چندجمله‌ای باشد» با هم معادل هستند.
"تابع جندجمله‌ای" تعریف شده توسط چندجمله‌ای تابعی از به است که توسط formula_47 تعریف می‌شود. اگر یک میدان نامتناهی باشد، دو چندجمله‌ای متفاوت، توابع چندجمله‌ای متفاوتی را تعریف می‌کنند، اما این خاصیت برای میدان‌های متناهی نادرست است. برای مثال، اگر میدانی با عنصر باشد، آنوقت چندجمله‌ای‌های و هر دو تعریف کننده تابع صفر هستند.
برای هر در ، ارزیابی در ، که همان نگاشت formula_48 است، یک از به را تعریف می‌کند، که یک همریختی یکتا از به است، که را ثابت نگه‌می‌دارد و را به نگاشت می‌دهد. به زبان دیگر، این را دارد: برای همه خاصیت‌های جامع، این موضوع (به دلیل یکریختی یکتا) تعریف کننده جفت است، و از این رو می‌توان آن را به عنوان تعریف در نظر گرفت.
اگر یک میدان باشد، حلقه چندجمله‌ای ویژگی‌های زیادی دارد که مشابه حلقه اعداد صحیح formula_49 است. بیشتر این شباهت‌ها از شباهت بین تقسیم طولانی اعداد صحیح و نشات می‌گیرند.
بیشتر ویژگی‌های که در این بخش فهرست شده‌است، اگر میدان نباشد، یا اگر چندجمله‌ای‌ها چندین نامعین داشته باشند، درست باقی نمی‌ماند.
در بسیاری از کاربردها پیش می‌آید که مجبور به نگهداری چندجمله‌ای‌هایی هستیم که با این که درجهٔ بزرگی دارند ولی تعداد بسیاری از ضرایب آن‌ها صفر می‌باشد. که استفاده از فرمت نگهداری فرض شده در ابتدای این نوشته برای چنین چند جمله‌هایی بسیار ناکاراست. به چنین چندجمله‌ای‌هایی، تنک می‌گوییم و برای اعمال روی آن‌ها الگوریتم‌های بسیاری پیشنهد شده که از ارزش بالایی هم برخوردارند. یک مثال از چنین چندجمله‌ای‌هایی در زیر آمده‌است:
formula_50
به همین دلیل به جای استفاده از آرایه برای نمایش این چندجمله‌ای‌ها از لیست پیوندی استفاده می‌شود. به این صورت که هر تک جمله را با یک واحد زبان برنامه‌نویسی که شامل درجه و ضریب آن باشد نمایش می‌دهیم و به آن گره می‌گوییم (مثلاً یک struct یا record) و این گره‌ها را در یک لیست پیوندی که به ترتیب درجه آن‌ها ار کوچک به بزرگ مرتب شده‌است، نگه می‌داریم. برای مثال بالا، استفاده از آرایه به حدود ۱۰۱ واحد حافظه نیاز دارد در حالی با نمایش اخیر می‌توان آن را با تنها ۱۶ واحد حافظه (حداکثر) نمایش داد زیرا که هر گره در لیست پیوندی اگر شامل توان و ضریب و دو اشاره جلو و عقب باشد به اندازهٔ ۴ واحد فضا مصرف می‌کند و با سه گره نیز چندجمله‌ای فوق قابل نمایش است به علاوهٔ یک گره احتمالی برای سرلیست.
در مورد این طرز نمایش چندجمله ای، نمی‌توان الکوریتم‌های معمول را به کار برد زیرا بسیاری از الگوریتم‌ها فرض می‌کنند که دسترسی تصادفی سریع به هر یک از ضرایب دارند؛ مثلاً نمی‌توان از تبدیل فوریه آن طور که اینجا مطرح شد برای ضرب چندجمله ای‌های تنک استفاده کنیم. با این حال الکوریتم استراسن که در بالا بحث شد را می‌توان با تغییر جزئی برای چنین نمایشی نیز به کار برد زیرا در طی آن تنها نیاز است که با یک بار عبور از روی چندجمله ای، وسط آن را پیدا کرد و سپس آن را به دو بخش تقسیم کرد و الگوریتم را به‌طور بازگشتی ادامه داد. واضح است که چنین تقسیمی به زمان اجرای الگوریتم نمی‌افزاید (از لحاظ تحلیل مجانبی) ولی برخی مسائل جدید در پیاده‌سازی را پیش می‌کشد مانند حالات تهی یا نصف تهی. که در بدترین حالت با افزودن تعداد ثابتی گره با ضریب صفر و اضاه کردن حالات پایه برای زمانی که چلیست پیوندی نمایش دهندهٔ چندجمله‌ای تهی است، به راحتی می‌توان این الگوریتم را روی چندجمله ای‌های تنک نیز اجرا کرد. الگوریتم‌های پیشرفته تر برای ضرب چندجمله‌های تنک که سریع تر نیز عمل می‌کنند و مثلاً در برخی از آن‌ها از داده ساختار هیپ برای نگهداری چندجمله ای‌ها و نمایش آن‌ها استفاده می‌شود، نیز وجود دارند ولی در این‌جا به جزییات بیشتری از آن‌ها نمی‌پردازیم.