حلقه چندجمله‌ای

الگو:Sidebar with collapsible lists حلقه چندجمله‌ای الگو:به انگلیسی یا جبر حلقه‌ای، در ریاضیات، بخصوص در شاخه جبر، یک حلقه است (از این رو یک جبر جابجایی هم هست) که توسط مجموعه‌ای از چندجمله‌ای‌ها که یک یا چند نامعین دارند (که به صورت سنتی متغیر نام دارند) تشکیل شده که ضرایبشان در حلقهٔ دیگری است که معمولاً یک میدان است.

معمولاً اصطلاح «حلقه چندجمله‌ای» به صورت ضمنی به حالت خاصی از حلقه چندجمله‌ای اشاره دارد که یک نامعین روی یک میدان دارد. این حلقه‌های چندجمله‌ای به این علت مهم هستند که ویژگی‌های مشترکی زیادی است که با حلقه اعداد صحیح دارند.

حلقه چندجمله‌ای‌ها در شاخه‌های مختلفی از ریاضیات همچون نظریه اعداد، جبر جابجایی، و هندسه جبری ظهور پیدا می‌کنند. در نظریه حلقه‌ها، برای تعمیم بعضی ویژگی‌های حلقه‌های چندجمله‌ای، کلاس‌های مختلفی از حلقه‌ها معرفی شده‌اند که شامل: حوزه تجزیه یکتا، حلقه‌های منظم، حلقه‌های گروهی، حلقه‌های سری‌های توانی صوری، چند جمله‌ای‌های Ore و حلقه‌های مدرج هستند.

یک مفهوم بسیار مرتبط، حلقه توابع چندجمله‌ای روی فضای برداری، و به صورت کلی‌تر حلقه توابع منظم روی واریته جبری است.

تعریف (حالت تک متغیره)

حلقه چند جمله‌ای الگو:Math، با الگو:Math روی یک میدان (یا به صورت کلی‌تر حلقه جابجایی) الگو:Math را می‌توان به صورت مجموعه‌ای از عبارات، که به آن چندجمله‌ای در الگو:Math گفته می‌شود، به این حالت تعریف کرد (تعاریف معادل دیگری هم وجود دارد که از آن‌ها هم استفاده معمول می‌شود):^[۱]

p = p_{0} + p_{1} X + p_{2} X^{2} + \dots + p_{m - 1} X^{m - 1} + p_{m} X^{m},

که در آن الگو:Math یعنی ضرایب الگو:Math عناصر الگو:Math هستند و الگو:Math اگر الگو:Math باشد و $X, X^{2}, . . .$ نمادهایی هستند که به عنوان «توان» الگو:Math شناخته شده و از همان قواعد معمول به توان رساندن تبعیت می‌کنند، یعنی: $X^{0} = 1$ و $X^{1} = X$ و برای هر عدد صحیح نامنفی الگو:Math و الگو:Math داریم: $X^{k} X^{l} = X^{k + l}$ . نماد الگو:Math را نامعین^[۲] یا متغیر^[۳] می‌نامند (اصطلاح «متغیر» از اصطلاح‌شناسی توابع چندجمله‌ای می‌آید. با این حال، در اینجا الگو:Mvar هیچ مقداری (غیر از خودش) اختیار نمی‌کند و نمی‌تواند تغییر کند و در حلقه چندجمله‌ای ثابت است).

دو چند جمله‌ای زمانی با هم برابراند که ضرایب متناظر با هرکدام از الگو:Math‌ها در هردو با هم برابر باشند.

حلقه چندجمله‌ای الگو:Math را می‌توان به این صورت دید، که از میدان الگو:Math با اضافه‌کردن یک عنصر جدید الگو:Math ایجاد شده که این الگو:Math برای الگو:Math خارجی است و با همه عناصر الگو:Math شرکت‌پذیر بوده و خاصیت ویژه دیگری هم ندارد (از همین می‌توان برای تعریف‌کردن حلقه‌های چندجمله‌ای بهره جست).

حلقه چندجمله‌ای در الگو:Math روی الگو:Math به یک جمع، یک ضرب و یک ضرب نرده‌ای مجهز است که آن را یک جبر جابجایی می‌کند. این عملیات براساس قواعد معمولی برای دستکاری عبارات جبری تعریف شده‌اند. بخصوص اگر:

p = p_{0} + p_{1} X + p_{2} X^{2} + \dots + p_{m} X^{m},

و:

q = q_{0} + q_{1} X + q_{2} X^{2} + \dots + q_{n} X^{n},

آنگاه:

p + q = r_{0} + r_{1} X + r_{2} X^{2} + \dots + r_{k} X^{k},

و:

p q = s_{0} + s_{1} X + s_{2} X^{2} + \dots + s_{l} X^{l},

که در آن الگو:Math و الگو:Math

r_{i} = p_{i} + q_{i}

و

s_{i} = p_{0} q_{i} + p_{1} q_{i - 1} + \dots + p_{i} q_{0} .

در فرمول‌های فوق، می‌توان با افزودن «جملات ساختگی» با ضرایب صفر، چندجمله‌ای‌های الگو:Math و الگو:Math را توسعه داد به گونه‌ای که الگو:Math و الگو:Math‌های ظاهر شده در این عبارت تعریف شده باشند. بخصوص وقتی که الگو:Math باشد آنگاه برای الگو:Math داریم الگو:Math.

ضرب اسکالر حالت خاصی از همان ضرب عمومی است که در آن الگو:Math به جمله ثابت (جمله‌ای که مستقل از الگو:Math است) کاهش یافته‌است؛ یعنی:

p_{0} (q_{0} + q_{1} X + \dots + q_{n} X^{n}) = p_{0} q_{0} + (p_{0} q_{1}) X + \dots + (p_{0} q_{n}) X^{n}

می‌توان به راحتی راستی‌آزمایی کرد که سه عملیات بالا در اصول موضوعه جبر جابجایی روی میدان الگو:Mvar صدق می‌کنند. ازاین‌رو، به حلقه‌های چند جمله‌ای، جبرهای چندجمله‌ای نیز گفته می‌شود.

تعریف معادل دیگری که شهود کمتری دارد اما معمولاً ارجح است، چون راحت‌تر می‌شود آن را ساخت، به این صورت که چندجمله‌ای‌ها به صورت یک دنباله بی‌نهایت الگو:Math از عناصر الگو:Math تعریف شوند که این ویژگی را دارند که تنها تعداد متناهی از آن‌ها ناصفرند، یا به‌طور معادل، دنباله‌ای که برای آن یک الگو:Math وجود دارد که برای الگو:Math رابطه الگو:Nowrapبرقرار است. در این حالت، الگو:Math و الگو:Mvar را به ترتیب به عنوان نمادهای جایگزین برای دنباله‌های الگو:Math و الگو:Math در نظر گرفته‌ایم. آنگاه با کمی دقت می‌توان فهمید که با کمک این قواعد عملیاتی، یک عبارت به صورت زیر:

p_{0} + p_{1} X + p_{2} X^{2} + \dots + p_{m} X^{m}

دارای یک نماد جایگزین دنباله‌ای به صورت زیر است:

الگو:Math.

واژه‌شناسی

فرض کنید:

a_{0} + a_{1} X + a_{2} X^{2} + \dots + a_{m} X^{m}

یک چندجمله ای ناصفر باشد که در آن $(a_{0}, a_{1}, a_{2}, \dots, p_{m}, 0, 0, \dots)$ $p = p_{0} + p_{1} X + p_{2} X^{2} + \dots + p_{m - 1} X^{m - 1} + p_{m} X^{m},$ جمله ثابت چندجمله ای $r_{i} = p_{i} + q_{i}$ است. در چند جمله ای‌های صفر این ثابت صفر است (البته ممکن است در حالت‌های دیگر هم صفر باشد). درجه ی $r_{i} = p_{i} + q_{i}$ که به صورت $k$ نوشته می‌شود $k$ است. این مقدار برابر بزرگترین $\deg (p)$ یی است که ضریب $m$ صفر نباشد.^[۴] ضریب پیشرو ی $r_{i} = p_{i} + q_{i}$ ، برابر $X^{k}$ است.^[۵] در حالت خاص چندجمله ای‌های صفر که تمام ضرایب آن صفر است، چندجمله ای پیشرو تعریف نشده و درجه را اغلب تعریف نشده،^[۶] برابر -1^[۷] یا برابر $p_{m}$ ^[۸] تعریف می‌کنند.

یک چندجمله ای ثابت، یا چندجمله ای صفر است، یا چندجمله ای از درجه صفر.

یک چندجمله ای صفر تکین است اگر ضریب پیشروی آن ۱ باشد.

اگر دو چندجمله ای $r_{i} = p_{i} + q_{i}$ و $s_{i} = p_{0} q_{i} + p_{1} q_{i - 1} + \dots + p_{i} q_{0} .$ داده شده باشند خواهیم داشت:

$K$

و بر روی یک میدان یا به‌طور کلی تر یک حوزه صحیح داریم:^[۹]

$K$

سریعاً نتیجه می‌شود که اگر $\deg (p + q) \leq m a x (\deg (p), \deg (q)),$ یک حوزه صحیح باشد آنگاه $\deg (p q) = \deg (p) + \deg (q) .$ نیز حوزه صحیح است.^[۱۰]

در نتیجه اگر $\deg (p + q) \leq m a x (\deg (p), \deg (q)),$ یک حوزه صحیح باشد، یک چندجمله ای دارای معکوس ضربی است اگر و تنها اگر ثابت باشند، و آن ثابت در $\deg (p + q) \leq m a x (\deg (p), \deg (q)),$ معکوس ضربی داشته باشد.

دو چندجمله ای با هم مرتبط الگو:به انگلیسی هستند اگر برای هرکدام از آن‌ها یک عضو معکوس پذیر الگو:به انگلیسی وجود داشته باشد که با ضرب در آن به دیگری تبدیل شود.

هر چندجمله ای ناصفر بر روی یک میدان مرتبط با یک چندجمله ای منحصر به فرد است.

اگر دو چندجمله $r_{i} = p_{i} + q_{i}$ و $s_{i} = p_{0} q_{i} + p_{1} q_{i - 1} + \dots + p_{i} q_{0} .$ داده شده باشد، می‌گویند $r_{i} = p_{i} + q_{i}$ مقسوم علیه $s_{i} = p_{0} q_{i} + p_{1} q_{i - 1} + \dots + p_{i} q_{0} .$ است، یا $r_{i} = p_{i} + q_{i}$ چندجمله ای $s_{i} = p_{0} q_{i} + p_{1} q_{i - 1} + \dots + p_{i} q_{0} .$ را تقسیم می‌کند یا $s_{i} = p_{0} q_{i} + p_{1} q_{i - 1} + \dots + p_{i} q_{0} .$ ضریبی از $r_{i} = p_{i} + q_{i}$ است اگر چندجمله ای $q$ وجود داشته باشد به گونه ای که $p$ .

یک چندجمله‌ای تحویل ناپذیر است اگر نتوان آن را به صورت ضرب دو چندجمله‌ای غیرثابت نوشت یا به‌طور معادل، اگر مقسوم علیه‌های آن یا چندجمله‌ای‌های ثابت باشند یا درجه برابر با چندجمله‌ای اصلی داشته باشند.

ارزیابی چندجمله‌ای

فرض کنید الگو:Mvar یک میدان باشد، یا به صورت کلی‌تر، یک حلقه جابجایی باشد، و الگو:Mvar یک حلقه شامل الگو:Mvar باشد. برای هر چندجمله‌ای الگو:Mvar در الگو:Math و هر عنصر الگو:Mvar در الگو:Mvar، جایگزینی الگو:Mvar با الگو:Mvar در الگو:Mvar یک عنصر الگو:Math را تعریف می‌کند، که به صورت الگو:Math نمایش داده می‌شود. این عنصر با حمل الگو:Mvar پس از جایگزینی عملیات نشان داده‌شده توسط عبارت چندجمله‌ای به دست می‌آید. به این محاسبه «ارزیابی» الگو:Math در الگو:Math گفته می‌شود. برای مثال، اگر داشته باشیم

P = X^{2} - 1,

آنوقت داریم

\begin{matrix} P (3) & = 3^{2} - 1 = 8, \\ P (X^{2} + 1) & = {(X^{2} + 1)}^{2} - 1 = X^{4} + 2 X^{2} \end{matrix}

(در مثال اول الگو:Math و در مثال دوم الگو:Math). جایگزینی الگو:Math با خودش منجر زیر می‌شود

P = P (X),

که این موضوع شرح می‌دهد چرا دو جمله «فرض کنید الگو:Mvar یک چندجمله‌ای باشد» و «فرض کنید الگو:Math یک چندجمله‌ای باشد» با هم معادل هستند.

تابع جندجمله‌ای تعریف شده توسط چندجمله‌ای الگو:Mvar تابعی از الگو:Mvar به الگو:Mvar است که توسط $x \mapsto P (x)$ تعریف می‌شود. اگر الگو:Mvar یک میدان نامتناهی باشد، دو چندجمله‌ای متفاوت، توابع چندجمله‌ای متفاوتی را تعریف می‌کنند، اما این خاصیت برای میدان‌های متناهی نادرست است. برای مثال، اگر الگو:Mvar میدانی با الگو:Mvar عنصر باشد، آنوقت چندجمله‌ای‌های الگو:Math و الگو:Math هر دو تعریف کننده تابع صفر هستند.

برای هر الگو:Math در الگو:Math، ارزیابی در الگو:Mvar، که همان نگاشت $P \mapsto P (a)$ است، یک همریختی جبری از الگو:Math به الگو:Math را تعریف می‌کند، که یک همریختی یکتا از الگو:Math به الگو:Math است، که الگو:Mvar را ثابت نگه‌می‌دارد و الگو:Mvar را به الگو:Mvar نگاشت می‌دهد. به زبان دیگر، الگو:Math این خاصیت جامع را دارد:

برای هر حلقه الگو:Mvar شامل الگو:Mvar، و برای هر عنصر الگو:Mvar از الگو:Mvar، یک همریختی جبری یکتا از الگو:Math به الگو:Mvar وجود دارد، که الگو:Mvar را ثابت نگه‌می‌دارد و الگو:Mvar را به الگو:Mvar نگاشت می‌دهد.

برای همه خاصیت‌های جامع، این موضوع (به دلیل یکریختی یکتا) تعریف کننده جفت الگو:Math است، و از این رو می‌توان آن را به عنوان تعریف الگو:Math در نظر گرفت.

چندجمله‌ای‌های تک‌متغیره روی یک میدان

اگر الگو:Mvar یک میدان باشد، حلقه چندجمله‌ای الگو:Math ویژگی‌های زیادی دارد که مشابه حلقه اعداد صحیح $ℤ$ است. بیشتر این شباهت‌ها از شباهت بین تقسیم طولانی اعداد صحیح و تقسیم طولانی چندجمله‌ای‌ها نشات می‌گیرند.

بیشتر ویژگی‌های الگو:Math که در این بخش فهرست شده‌است، اگر الگو:Mvar میدان نباشد، یا اگر چندجمله‌ای‌ها چندین نامعین داشته باشند، درست باقی نمی‌ماند.

ضرب چندجمله ای‌های تنک

تعریف و نمایش

در بسیاری از کاربردها پیش می‌آید که مجبور به نگهداری چندجمله‌ای‌هایی هستیم که با این که درجهٔ بزرگی دارند ولی تعداد بسیاری از ضرایب آن‌ها صفر می‌باشد. که استفاده از فرمت نگهداری فرض شده در ابتدای این نوشته برای چنین چند جمله‌هایی بسیار ناکاراست. به چنین چندجمله‌ای‌هایی، تنک می‌گوییم و برای اعمال روی آن‌ها الگوریتم‌های بسیاری پیشنهد شده که از ارزش بالایی هم برخوردارند. یک مثال از چنین چندجمله‌ای‌هایی در زیر آمده‌است:الگو:سخ الگو:وسط‌چین $x^{100} - x^{2} + 1$ الگو:پایان الگو:سخ به همین دلیل به جای استفاده از آرایه برای نمایش این چندجمله‌ای‌ها از لیست پیوندی استفاده می‌شود. به این صورت که هر تک جمله را با یک واحد زبان برنامه‌نویسی که شامل درجه و ضریب آن باشد نمایش می‌دهیم و به آن گره می‌گوییم (مثلاً یک struct یا record) و این گره‌ها را در یک لیست پیوندی که به ترتیب درجه آن‌ها ار کوچک به بزرگ مرتب شده‌است، نگه می‌داریم. برای مثال بالا، استفاده از آرایه به حدود ۱۰۱ واحد حافظه نیاز دارد در حالی با نمایش اخیر می‌توان آن را با تنها ۱۶ واحد حافظه (حداکثر) نمایش داد زیرا که هر گره در لیست پیوندی اگر شامل توان و ضریب و دو اشاره جلو و عقب باشد به اندازهٔ ۴ واحد فضا مصرف می‌کند و با سه گره نیز چندجمله‌ای فوق قابل نمایش است به علاوهٔ یک گره احتمالی برای سرلیست.

الگوریتم‌های چندجمله ای‌های تنک

در مورد این طرز نمایش چندجمله ای، نمی‌توان الکوریتم‌های معمول را به کار برد زیرا بسیاری از الگوریتم‌ها فرض می‌کنند که دسترسی تصادفی سریع به هر یک از ضرایب دارند؛ مثلاً نمی‌توان از تبدیل فوریه آن طور که اینجا مطرح شد برای ضرب چندجمله ای‌های تنک استفاده کنیم.الگو:سخ با این حال الکوریتم استراسن که در بالا بحث شد را می‌توان با تغییر جزئی برای چنین نمایشی نیز به کار برد زیرا در طی آن تنها نیاز است که با یک بار عبور از روی چندجمله ای، وسط آن را پیدا کرد و سپس آن را به دو بخش تقسیم کرد و الگوریتم را به‌طور بازگشتی ادامه داد. واضح است که چنین تقسیمی به زمان اجرای الگوریتم نمی‌افزاید (از لحاظ تحلیل مجانبی) ولی برخی مسائل جدید در پیاده‌سازی را پیش می‌کشد مانند حالات تهی یا نصف تهی. که در بدترین حالت با افزودن تعداد ثابتی گره با ضریب صفر و اضاه کردن حالات پایه برای زمانی که چلیست پیوندی نمایش دهندهٔ چندجمله‌ای تهی است، به راحتی می‌توان این الگوریتم را روی چندجمله ای‌های تنک نیز اجرا کرد.الگو:سخ الگوریتم‌های پیشرفته تر برای ضرب چندجمله‌های تنک که سریع تر نیز عمل می‌کنند و مثلاً در برخی از آن‌ها از داده ساختار هیپ برای نگهداری چندجمله ای‌ها و نمایش آن‌ها استفاده می‌شود، نیز وجود دارند ولی در این‌جا به جزییات بیشتری از آن‌ها نمی‌پردازیم.

جستارهای وابسته

منابع

الگو:پانویس

کتابشناسی

الگو:چپ‌چین

الگو:پایان چپ‌چین الگو:جبر

↑ Herstein p. 153
↑ Herstein, Hall p. 73
↑ Lang p. 97
↑ Herstein p. 154
↑ Lang p.100
↑ الگو:Citation.
↑ الگو:Citation.
↑ الگو:Citation.
↑ Herstein p.155, 162
↑ Herstein p.162

[1] Herstein p. 153

[2] Herstein, Hall p. 73

[3] Lang p. 97

[4] Herstein p. 154

[5] Lang p.100

[6] الگو:Citation.

[7] الگو:Citation.

[8] الگو:Citation.

[9] Herstein p.155, 162

[10] Herstein p.162

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]