חוגי פולינומים

סדרת הפוסטים שלי על אלגברה מופשטת מתקרבת לסיום החלק שעסק במבוא לחוגים ומתקרבת אל החלק שעוסק בשדות, והחוט המקשר המרכזי בין שני אלו הם חוגי פולינומים שעליהם ארצה לדבר עכשיו. פולינומים הם מאותם יצורים שצצים במתמטיקה בשלל מקומות, וגולשים גם למתמטיקה התיכונית, ואנחנו לכאורה מכירים די טוב - אבל זה לא אומר שאין הרבה מה לומר עליהם. את חלק מהדברים שאגיד עכשיו אמרתי ממש לא מזמן, אבל בכל זאת אגיד שוב, כדי לקבל פוסט שעומד בפני עצמו ככל שניתן.

מה זה בכלל פולינומים?

השאלה “מה זה בכלל פולינום” היא קצת יותר טריקית משנדמה במבט ראשון. הנה הגדרה מהשרוול: פולינום הוא ביטוי מהצורה $latex a_{n}x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$ כאשר $latex x$ מכונה משתנה ואילו $latex a_{0},a_{1},\dots,a_{n}$ נקראים מקדמים של הפולינום. האינטואיציה היא שפולינום מתאר איזה “תרגיל חשבון פוטנציאלי”: אנחנו יכולים להציב איזה שהוא ערך במקום $latex x$, ואז לחשב את החזקות של הערך הזה, לכפול אותן במקדמים, לסכום את הכל ולקבל תוצאה. בראיה האינטואיטיבית הזו הפולינום הוא בסך הכל דרך לכתוב חישוב כלשהו - לתאר פונקציה כלשהי. אבל באלגברה מודרנית זה כלל לא המצב; פולינום הוא יצור עם זכות קיום בפני עצמו, אפילו אם בכלל לא מציבים בו ערכים. ואני רוצה לתת דוגמא שתבהיר מייד את הסיטואציה.

בואו נסתכל על החוג $latex \mathbb{Z}_{3}=\left\{ 0,1,2\right\} $ שבו פעולות החיבור והכפל הן מודולו 3, ונתבונן על הפולינום הבא: $latex p\left(x\right)=x^{3}-x$. בדיקה ישירה תראה לנו שאם אנחנו מציבים בו איבר כלשהו של $latex \mathbb{Z}_{3}$ אז אנחנו מקבלים 0. כלומר, אם מסתכלים על $latex p\left(x\right)=x^{3}-x$ בתור “דרך לתאר פונקציה ותו לא” אז זו פונקציית האפס בדיוק כמו הפולינום $latex q\left(x\right)=0$. אבל שני הפולינומים הללו הם יצורים שונים - באחד מופיעים $latex x$ ו-$latex x^{3}$ ובשני לא, למשל. אם כן, גם אם פולינומים שונים מגדירים את אותה הפונקציה, אנחנו עדיין רוצים לחשוב עליהם בתור יצורים שונים.

אם אני רוצה לדבר עליהם בתור יצורים עם קיום עצמאי, עדיף לתת הגדרה קצת יותר ברורה מ”אה… זה ביטוי…”. ראשית, בואו ניקח חוג $latex R$ כלשהו שממנו יילקחו המקדמים של הפולינומים שמעניינים אותנו. עכשיו בואו “נרחיב” את החוג $latex R$ על ידי כך שנוסיף אליו אובייקט חדש שאני מסמן ב-$latex x$ ומגדיר על ה-$latex x$ הזה כללי חשבון: אם $latex a\in R$ אז $latex ax=xa$, וכמו כן חישובים שמערבים את $latex x$ מקיימים דיסטריביוטיביות. במקום לכתוב $latex x\cdot x\cdots x$ כאשר כופלים את $latex x$ בעצמו $latex n$ פעמים אני אכתוב $latex x^{n}$ ונוסיף את המוסכמה ש-$latex x^{0}=1$ (כאשר $latex 1$ הוא איבר היחידה של $latex R$). עם כל אלו, אפשר לשאול את עצמנו איך נראה איבר כללי של החוג $latex R\left[x\right]$ שמתקבל מ-$latex R$ על ידי הוספת $latex x$ פנימה ולקיחת החוג הקטן בותר שמכיל את $latex R$ ואת $latex x$ (כלומר, סגור לחיבור ולכפל). התשובה היא ש-$latex R\left[x\right]$ יהיה בדיוק אוסף האיברים מהצורה $latex a_{n}x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$, כפי שראינו קודם.

קרוב לודאי שגם זה לא מספיק לחלקכם - אתם אולי זועמים “מי $latex x$? מה $latex x$? מאיפה הוא הגיע? איך בונים אותו? מה הולך כאן?”. ובכן, למרות שזה לגמרי לגיטימי לייצר איברים חדשים יש מאין בצורה הזו (מה שחשוב הוא להגדיר את ההתנהגות שלהם ביחס לפעולות החשבון של $latex R$ ולווודא ששום דבר בהגדרות של חוג לא נשבר כשמוסיפים אותם), אם ממש מתעקשים אפשר גם להגדיר פורמלית את הפולינום $latex a_{n}x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$ בתור הסדרה $latex \left(a_{0},a_{1},\dots,a_{n}\right)$; בצורה הזו, ה-$latex x$ הוא אכן רק סימון, אבל כזה שעוזר לנו להבין איך ייראה כפל של פולינומים.

יש נקודה עדינה אחת בהגדרה הזו שחשוב להתייחס אליה: אם אני כותב יצור כמו $latex p\left(x\right)=0\cdot x^{2}+x+1$ אני לא רוצה לחשוב עליו בתור אובייקט שונה מאשר $latex x+1$. לכן, למרות שלפעמים משתלם לי מאוד לכתוב פולינום שהחזקות הגבוהות שלו מוכפלות ב-0 (עוד רגע נראה דוגמא לכך, בהגדרת חיבור וכפל פולינומים) אני רוצה לומר שזה עדיין אותו פולינום כמו זה שיתקבל על ידי כך שפשוט לא נכתוב את החזקות הגבוהות הללו. לכן לכל פולינום אנחנו בוחרים ייצוג קנוני $latex a_{n}x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$ שבו $latex a_{n}\ne0$, למעט במקרה שבו הפולינום הוא פולינום האפס $latex p\left(x\right)=0$. אם אתם רוצים פורמליזם, אז אני מגדיר פולינום בתור סדרה אינסופית $latex \left(a_{0},a_{1},\dots\right)$ עם הדרישה הנוספת שהחל ממקום מסויים כל אברי הסדרה שווים 0.

ל-$latex a_{n}$ בייצוג הקנוני של הפולינום קוראים המקדם המוביל של הפולינום, ואם $latex a_{n}=1$ אומרים שהפולינום מתוקן. על הדרך אעיר ש-$latex a_{0}$ נקרא המקדם החופשי של הפולינום. המעלה (או כמו שאני לפעמים כותב בלי לשים לב, הדרגה) של הפולינום $latex a_{n}x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$, כאשר $latex a_{n}\ne0$, היא $latex n$; מסמנים זאת $latex \deg\left(p\right)=n$. עבור פולינום האפס בדרך כלל לא מגדירים בכלל את המעלה.

חיבור וכפל של פולינומים מתבצעים בצורה שמשמרת את חוקי החשבון הרגילים של $latex R$, אבל בואו נכתוב את זה באופן כללי:

  • חיבור: $latex \sum_{i=0}^{n}a_{i}x^{i}+\sum_{i=0}^{n}b_{i}x^{i}=\sum_{i=0}^{n}\left(a_{i}+b_{i}\right)x^{i}$
  • כפל: $latex \left(\sum_{i=0}^{n}a_{i}x^{i}\right)\cdot\left(\sum_{i=0}^{m}b_{i}x^{i}\right)=\sum_{k=0}^{n+m}\left(\sum_{i=0}^{k}a_{i}b_{k-i}\right)x^{k}$

שימו לב שבחיבור השתמשתי ב-$latex n$ כדי לסמן את המקדם הגדול ביותר שאני כותב בכל אחד מהפולינומים; זה לא מגביל את הכלליות של ההגדרה כי בהינתן שני פולינומים ממעלה שונה, אני יכול לכתוב איברים נוספים עם מקדם 0 (למשל, במקום לכתוב $latex \left(x^{2}+3\right)+\left(2x\right)$ אפשר לכתוב $latex \left(x^{2}+0\cdot x+3\right)+\left(0\cdot x^{2}+2x+0\right)$).

פעולת החיבור היא קצת “משעממת”; אם היינו מתארים פולינומים בתור סדרות אז חיבור היה בסך הכל ביצוע חיבור “איבר-איבר” בשתי הסדרות, כלומר

$latex \left(a_{1},\dots,a_{n}\right)+\left(b_{1},\dots,b_{n}\right)=\left(a_{1}+b_{1},\dots,a_{n}+b_{n}\right)$

אבל הכפל הוא כבר סיפור שונה לגמרי. הכפל מתאים לפעולה המתמטית שנקראת קונבולוציה, וזו פעולה מעניינת ושימושית מאוד. קונבולוציה של שתי סדרות מתבצעת כך: ראשית הופכים את הסדר של אחת מהסדרות, ואז כותבים את הסדרה האחת מעל השניה, כופלים את האיברים שנמצאים האחד מעל השני, ומחברים את כל המכפלות שמתקבלות בצורה הזו. תיארתי את זה בעבר בבלוג, והנה זה שוב. ראשית נכתוב את הסדרות כך:

$latex \begin{array}{ccccccc} \cdots & b_{2} & b_{1} & b_{0}\\ & & & a_{0} & a_{1} & a_{2} & \cdots \end{array}$

חשבו על מקומות ריקים בתור 0, ולכן איברים שמתחת או מעל להם יש מקום ריק לא יתרמו לסכום; הסכום שנקבל למעלה הוא פשוט $latex a_{0}b_{0}$, וזה גם המקדם של $latex x^{0}$ במכפלה של שני הפולינומים.

כעת נזיז את הסדרה העליונה מקום אחד ימינה ונקבל

$latex \begin{array}{ccccccc} \cdots & b_{3} & b_{2} & b_{1} & b_{0}\\ & & & a_{0} & a_{1} & a_{2} & \cdots \end{array}$

זה נותן לנו את הסכום $latex a_{0}b_{1}+a_{1}b_{0}$ שמתאים למקדם של $latex x^{1}$, וכן הלאה. בסופו של דבר, מכיוון ששתי הסדרות סופיות, השלב האחרון יהיה

$latex \begin{array}{ccccccc} & & & b_{m} & b_{m-1} & \cdots\\ & \cdots & a_{n-1} & a_{n} \end{array}$

שייתן לנו את המקדם $latex a_{n}b_{m}$ של $latex x^{n+m}$. במילים אחרות, מכפלת שני הפולינומים $latex \sum_{i=0}^{n}a_{i}x^{i}$ ו-$latex \sum_{i=0}^{m}b_{i}x^{i}$ מייצרת לנו פולינום חדש, שמקדמיו הם כל הקונבולוציות האפשריות של הסדרות $latex \left(a_{0},\dots,a_{n}\right)$ ו-$latex \left(b_{0},\dots,b_{m}\right)$.

הכפל המעניין הזה מזכיר קצת את מה שקורה עם מטריצות; גם מטריצות נראות במבט ראשון כמו דרך לא כל כך מעניינת לתאר סדרות (במקרה הזה, סדרות דו-ממדיות) והחיבור שלהן הוא איבר-איבר, אבל הכפל שלהן הוא מאוד מוזר ממבט ראשון, ומאוד מעניין ממבט שני בגלל היכולת שלו לתאר דברים שונים ומשונים.

תכונות בסיסיות של חוגי פולינומים

אפשר לבדוק ולראות במפורש שההגדרות של חיבור וכפל פולינומים הופכות את $latex R\left[x\right]$ לחוג, לכל $latex R$. איך החוג הזה יתנהג בדיוק, זה כבר תלוי בשאלה מהו $latex R$. כש-$latex R$ הוא חוג כללי קשה להגיד יותר מדי דברים ברורים על מה יקרה לפולינומים מעליו. למשל, תכונה שאנחנו מכירים מהיומיום של פולינומים היא ש-$latex \deg\left(pq\right)=\deg\left(p\right)+\deg\left(q\right)$ - כשכופלים פולינומים מקבלים פולינום מדרגה שהיא סכום הדרגות שלהם. זה לא עובד לחוג פולינומים מעל $latex R$ כללי; למשל, ניקח $latex R=\mathbb{Z}_{4}$, אז $latex \left(2x+1\right)\cdot\left(2x+1\right)=4x^{2}+4x+1=1$, כשהשוויון הוא בחוג $latex \mathbb{Z}_{4}$. קיבלנו אם כן פולינום ממעלה 0 על ידי כפל שני פולינומים ממעלה 1. ה”בעיה” הייתה שהמקדמים המובילים של הפולינומים שכפלנו היו מחלקי אפס; אם הם לא כאלו, או ש-$latex R$ הוא תחום שלמות, אז $latex \deg\left(pq\right)=\deg\left(p\right)+\deg\left(q\right)$ אכן מתקיים. עד שלומדים על חוגים ושדות ההקשר שבו רואים פולינומים הוא בדרך כלל כזה שבו $latex R$ הוא שדה, למשל המספרים הממשיים, ולכן התכונה הזו נראית לנו (אולי) מובנת מאליה.

שימו לב למשהו נוסף שראינו בדוגמא שלי: $latex 2x+1$ היה ההופכי של עצמו. אם $latex R$ הוא תחום שלמות זה לא יכול לקרות: התכונה על סכום המעלות מבטיחה שההפיכים היחידים ב-$latex R\left[x\right]$ יהיו “פולינומים” ממעלה 0, ופולינומים כאלו הם פשוט איברים של $latex R$, כך שההפיכים ב-$latex R\left[x\right]$ הם בדיוק ההפיכים של $latex R$. במילים אחרות, אפשר לשכוח מכך ש-$latex R\left[x\right]$ יהיה שדה; אבל אם $latex R$ הוא תחום שלמות אז $latex R\left[x\right]$ הוא תחום שלמות ואז אפשר לדבר על שדה השברים של $latex R\left[x\right]$. השדה הזה, שהאיברים שלו הם כל היצורים מהצורה $latex \frac{p\left(x\right)}{q\left(x\right)}$ כאשר $latex q\left(x\right)$ איננו פולינום האפס, נקרא שדה הפונקציות הרציונליות מעל $latex R$. לא נדבר עליו יותר כאן, אבל כדאי לדעת שדבר כזה קיים.

הסיטואציה המעניינת ביותר מבחינתנו היא זו שבה החוג שמעליו אנחנו עובדים הוא שדה; בדרך כלל מסמנים אותו ב-$latex F$ במקרה הזה ולא ב-$latex R$ כדי שיהיה ברור שאנחנו בסיטואציה הזו. החשיבות של המקרה הזה היא בכך שבו אפשר להגדיר חלוקה עם שארית על הפולינומים. כלומר, אם $latex a\left(x\right),b\left(x\right)\in F\left[x\right]$ הם פולינומים כך ש-$latex b\left(x\right)\ne0$ אז קיימים $latex q\left(x\right),r\left(x\right)\in F\left[x\right]$ כך ש-

$latex a\left(x\right)=b\left(x\right)q\left(x\right)+r\left(x\right)$

עם התכונה הנוספת לפיה $latex \deg\left(r\right)<\deg b$ או ש-$latex r=0$. שימו לב שזה חייב להיות מעל שדה: למשל, ב-$latex \mathbb{Z}\left[x\right]$ הפולינום $latex x$ פשוט לא מתחלק עם שארית על ידי $latex 2$. זה טיפה שובר אינטואיציה כי הרי אנחנו רגילים לחשוב על “חלוקה עם שארית” בדיוק בהקשר של $latex \mathbb{Z}$.

בואו נוכיח את הטענה על החלוקה עם שארית פורמלית, באינדוקציה על המעלה של $latex a\left(x\right)$. אם לחדד - אנחנו קובעים מראש פולינום $latex b\left(x\right)$ כלשהו ומוכיחים שלכל $latex a\left(x\right)$ ניתן לחלק עם שארית את $latex a\left(x\right)$ ב-$latex b\left(x\right)$.

בסיס האינדוקציה הוא כל המקרים שבהם $latex \deg\left(a\right)<\deg\left(b\right)$. במקרים הללו אפשר פשוט “לרמות” ולהגדיר $latex q\left(x\right)=0$ ו-$latex r\left(x\right)=a\left(x\right)$ ומקבלים $latex a\left(x\right)=b\left(x\right)q\left(x\right)+r\left(x\right)$ תוך עמידה בקריטריון $latex \deg\left(r\right)<\deg\left(b\right)$ (זה כמו האופן שבו מחלקים את 6 ב-17 עם שארית - המנה היא 0 והשארית היא 6).

כעת נעבור לצעד האינדוקציה: נניח ש-$latex \deg\left(a\right)=n\ge\deg\left(b\right)$ ושהוכחנו כבר את הטענה לכל מעלה קטנה מ-$latex n$. הרעיון הוא להעלים את המקדם המוביל של $latex a\left(x\right)$ כדי לקבל פולינום ממעלה נמוכה יותר שאנחנו כבר יודעים איך לחלק - זה למעשה גם הרעיון מאחורי השיטות הפרקטיות שבהן אנחנו מבצעים חילוק ארוך (של שלמים/פולינומים) ביד.

אם כן, נסמן $latex a\left(x\right)=a_{n}x^{n}+\dots+a_{1}x+a_{0}$, כאשר $latex a_{n}\ne0$. באופן דומה נסמן $latex b\left(x\right)=b_{m}x^{m}+\dots+b_{1}x+b_{0}$ עם $latex b_{m}\ne0$. ההנחה שלנו היא ש-$latex n\ge m$ אחרת היינו מטפלים במקרה הזה כחלק מהבסיס. נגדיר כעת פולינום חדש באופן הבא:

$latex a^{\prime}\left(x\right)=a\left(x\right)-\frac{a_{n}}{b_{m}}x^{n-m}b\left(x\right)$

הפולינום הזה יהיה לכל היותר ממעלה $latex n-1$ ולכן אפשר להשתמש עליו בהנחת האינדוקציה ולקבל:

$latex a^{\prime}\left(x\right)=q^{\prime}\left(x\right)b\left(x\right)+r\left(x\right)$ כך ש-$latex \deg\left(r^{\prime}\right)<\deg\left(b\right)$ או $latex r=0$ (שימו לב - לא שמתי תג על $latex b$ מכיוון שאנחנו מוכיחים את המשפט עבור כל ה-$latex a\left(x\right)$-ים האפשריים ועם $latex b\left(x\right)$ קבוע עבור כולם; ועל $latex r$ לא שמתי תג כי הוא יהיה גם השארית הסופית שארצה לקבל).

יש לנו עכשיו שתי משוואות שמערבות את $latex a^{\prime}\left(x\right)$. נשווה את שתיהן ונקבל:

$latex a\left(x\right)=\frac{a_{n}}{b_{m}}x^{n-m}b\left(x\right)+q^{\prime}\left(x\right)b\left(x\right)+r\left(x\right)=\left(\frac{a_{n}}{b_{m}}x^{n-m}+q^{\prime}\left(x\right)\right)+r\left(x\right)$

כלומר, קיבלנו את המבוקש, עם $latex q\left(x\right)=\frac{a_{n}}{b_{m}}x^{n-m}+q^{\prime}\left(x\right)$.

החילוק-עם-שארית הזה הוא עסק רציני מאוד - זה הופך את $latex F\left[x\right]$ לתחום אוקלידי לכל שדה $latex F$ אפשרי. בפרט זה אומר ש-$latex F\left[x\right]$ הוא תחום פריקות יחידה (כלומר, כל פולינום מתפרק באופן יחיד לגורמים אי-פריקים) ותחום ראשי (כלומר, כל אידאל נוצר בידי פולינום יחיד). שני אלו יהיו מאוד חשובים בהמשך, כשנדבר על תורת השדות.

שורשים של פולינומים

קודם עשיתי מהומה גדולה סביב זה שפולינום הוא יותר מאשר סתם פונקציה ושאפשר להתעסק עם פולינומים גם בלי להציב בהם דברים בכלל, אבל זה לא אומר שזה לא מעניין להציב בהם דברים. אחד מהדברים החשובים ביותר שאפשר לעשות עם פולינום הוא להציב בו דברים, כמו שאחד מהדברים החשובים ביותר שאפשר לעשות עם מטריצה הוא לכפול אותה בוקטורים.

אם $latex p\left(x\right)\in R\left[x\right]$ כך ש-$latex p\left(x\right)=a_{n}x^{n}+\dots+a_{1}x+a_{0}$ ו-$latex r\in R$ אז הצבה של $latex r$ ב-$latex p\left(x\right)$ מניבה לנו איבר ב-$latex R$ שמחושב באופן הבא:

$latex p\left(r\right)=a_{n}r^{n}+\dots+a_{1}r+a_{0}$

אין כאן שום דבר מפתיע או חדש, כמובן. יש רק נקודה קטנה שאני רוצה להתייחס אליה במפורש: אפשר להציב בפולינום גם ערכים שנלקחים מתוך קבוצה שלא בהכרח שווה לחוג $latex R$ שממנו נלקחו מקדמי הפולינום; כל מה שנדרש הוא שהמקדמים ידעו “לשחק יפה” עם $latex r$, כלומר שתהיה משמעות לכפל שלהם. זו הסיבה שבגללה אפשר להציב, למשל, מטריצות בתוך פולינומים; יש לנו מושג של כפל מטריצה בסקלר שהוא האופן שבו המטריצה משחקת יפה עם המקדמים של הפולינום. עם זאת, ההקשר שמעניין אותי בתורת השדות הוא כמעט תמיד זה שבו מציבים בתוך פולינום מ-$latex R\left[x\right]$ ערך מחוג שמרחיב את $latex R$ - כלומר, כולל את $latex R$ בתור תת-חוג. במקרה הזה, ה”משחק יפה” הוא פשוט פעולת הכפל הרגילה בחוג ההרחבה הזה. למשל, בפולינום $latex p\left(x\right)=3x^{2}+1\in\mathbb{Q}\left[x\right]$ אין שום בעיה להציב את $latex \pi$ ולקבל $latex p\left(\pi\right)=3\pi^{2}+1$ וזאת למרות ש-$latex \pi\notin\mathbb{Q}$.

בואו נדבר עכשיו על המקרה שבו $latex F$ שדה, $latex p\left(x\right)\in F\left[x\right]$ ו-$latex a\in F$. אנחנו אומרים ש-$latex a$ הוא שורש של $latex p\left(x\right)$ אם $latex p\left(a\right)=0$. שורשים של פולינומים מעניינים אותנו במיוחד כי הם במובן מסויים אבני הבניין של הפולינום: אם $latex p\left(a\right)=0$ ואנחנו מעל שדה, אז אני טוען שהפולינום $latex \left(x-a\right)$ מחלק את $latex p\left(x\right)$. ההוכחה פשוטה: אנחנו מעל שדה אז אפשר לחלק עם שארית ולקבל

$latex p\left(x\right)=q\left(x\right)\left(x-a\right)+r\left(x\right)$

עכשיו, $latex \deg\left(r\right)<\deg\left(x-a\right)=1$ ולכן בהכרח $latex \deg\left(r\right)=0$ כך ש-$latex r$ הוא קבוע. אם נציב $latex a$ בשני אגפי המשוואה, נקבל

$latex p\left(a\right)=0=q\left(a\right)\cdot0+r=r$

כלומר, נקבל שהשארית היא בהכרח 0, ומכאן ש-$latex x-a$ מחלק את $latex p\left(x\right)$ בלי שארית.

עכשיו, שימו לב מה קרה כאן. ראינו ש-$latex p\left(x\right)=q\left(x\right)\left(x-a\right)$, אז $latex \deg\left(p\right)=\deg\left(q\right)+1$, כלומר הצגנו את $latex p\left(x\right)$ בתור מכפלה של שני פולינומים ממעלה נמוכה יותר. נניח שגם ל-$latex q\left(x\right)$ יש שורש, אז גם אותו אפשר לפרק ככה, ואם לכל הפולינומים שנגיע אליהם בצורה הזו יש שורש, בסוף נקבל את השוויון

$latex p\left(x\right)=a\left(x-a_{1}\right)\left(x-a_{2}\right)\dots\left(x-a_{n}\right)$

כאשר $latex a_{1},\dots,a_{n}$ הם השורשים (לאו דווקא שונים זה מזה) של $latex p\left(x\right)$ ו-$latex a\in F$ הוא המקדם המוביל של $latex p\left(x\right)$. במילים אחרות - אם כל השורשים של $latex p\left(x\right)$ שייכים לשדה $latex F$, אז הפירוק לגורמים אי פריקים של $latex p\left(x\right)$ הוא בדיוק המכפלה הנ”ל. למשל, הפולינום $latex x^{2}-1$ מתפרק מעל $latex \mathbb{R}$ ל-$latex \left(x-1\right)\left(x+1\right)$ והשורשים שלו הם 1 ו-$latex -1$; הפולינום $latex x^{2}+x-6$ מתפרק ל-$latex \left(x-2\right)\left(x+3\right)$ והשורשים שלו הם 2 ו-$latex -3$; ואילו $latex x^{2}+1$ לא מתפרק כלל מעל $latex \mathbb{R}$ אבל מעל $latex \mathbb{C}$ הוא יתפרק ל-$latex \left(x+i\right)\left(x-i\right)$.

הפירוק הזה גם מלמד אותנו בדיוק איך בנויים המקדמים של $latex p\left(x\right)$; הם כולם מורכבים מסכומים של מכפלות של שורשים של $latex p\left(x\right)$. בואו נראה דוגמא עבור פולינום ממעלה שלישית עם שורשים $latex a,b,c$: הפירוק שלו הוא $latex \left(x-a\right)\left(x-b\right)\left(x-c\right)$. לפתוח את הסוגריים באופן מפורש זו עבודה טכנית, אבל היא תשתלם לנו, כי אחרי שנעשה אותה נראה (ונרגיש) שהפולינום הוא מהצורה

$latex x^{3}-\left(a+b+c\right)x^{2}+\left(ab+ac+bc\right)x-abc$

שימו לב לסימטריה שיש בכל המקדמים - במקדם של $latex x^{2}$ משתתפים כל הסכומים האפשריים של מכפלה של שורש בודד; במקדם של $latex x$ כל הסכומים של מכפלה של שני שורשים, ובמקדם של $latex x^{0}$ כל הסכומים של מכפלה של שלושה. על כך אומרים לפעמים שהמקדמים של הפולינום הם פונקציות סימטריות בשורשים שלו. העובדה שהפולינום נבנה כולו מתוך השורשים (עד כדי כפל של כל הפולינום באיבר כלשהו של $latex F$) מצביעה יפה על החשיבות הרבה שלהם.

אבל מה קורה אם אותו שורש מופיע יותר מפעם אחת? נסתכל למשל על $latex x^{3}-9x+27x-27$. קל לראות שהפירוק של הפולינום הזה לגורמים הוא $latex \left(x-3\right)\left(x-3\right)\left(x-3\right)$, כלומר יש לו שורש בודד שהוא 3 שמופיע שלוש פעמים. אין עם זה בעיה; הנוסחה מלמעלה עובדת גם כאשר $latex a=b=c=3$ (בדקו!). במקרה הזה אומרים על 3 שהוא שורש מריבוי שלוש, ובאופן כללי מספר הפעמים ששורש כלשהו מופיע בפירוק הוא הריבוי שלו. הנה דרך אחרת להגדיר ריבוי של שורש: $latex a$ הוא שורש מריבוי $latex k$ של $latex p\left(x\right)$ אם $latex p\left(x\right)=\left(x-a\right)^{k}q\left(x\right)$ כך ש-$latex a$ אינו שורש של $latex q\left(x\right)$.

עכשיו אפשר לדבר על קשר ברור שיש בין המעלה של פולינום ובין מספר השורשים שלו - מספר השורשים לא יכול להיות גדול מהמעלה שלו, פשוט כי ראינו שלכל שורש $latex a$ אפשר להקטין את המעלה של הפולינום ב-1 על ידי חלוקה ב-$latex x-a$. זה נכון רק מעל שדה; למשל, מעל החוג $latex \mathbb{Z}_{8}$ שאיננו שדה, קל לראות של-$latex x^{2}-1$ יש ארבעה שורשים: $latex 1,3,5,7$. זהירות לא לבלבל את התוצאה הזו, שלפולינום ממעלה $latex n$ מעל שדה יש לכל היותר $latex n$ שורשים, עם מה שנקרא המשפט היסודי של האלגברה שאומר משהו שונה לגמרי; הוא אומר שאם $latex p\left(x\right)\in\mathbb{C}\left[x\right]$ ו-$latex p\left(x\right)$ הוא ממעלה $latex n$, אז ל-$latex p\left(x\right)$ יש בדיוק $latex n$ שורשים ב-$latex \mathbb{C}$ (כולל ריבוי, כלומר שורש יכול להיספר יותר מפעם אחת, על פי מספר הפעמים שהוא מופיע בפירוק). בניסוח שקול: לכל פולינום ממעלה לפחות 1 מעל המרוכבים יש שורש מרוכב (ואז אפשר לחלק ב-$latex x-a$ ולהמשיך באינדוקציה). המשפט הזה מדבר ספציפית על $latex \mathbb{C}$, וכשנדבר על תורת השדות נראה שיש שם כללי יותר לתופעה שהוא מתאר: הוא בעצם אומר “שדה המרוכבים סגור אלגברית” אבל על זה נדבר בהמשך.

פולינומים פריקים ואי פריקים

מה שראינו קודם הוא שאם לפולינום ממעלה לפחות 2 $latex p\left(x\right)\in F\left[x\right]$ יש שורש $latex a\in F$, אז הוא פריק מעל $latex F$: ניתן לכתוב אותו בתור $latex p\left(x\right)=\left(x-a\right)q\left(x\right)$ כאשר אף אחד משני המוכפלים אינו הפיך (כלומר, אינו פולינום ממעלה 0). זה קריטריון מספיק לכך שפולינום יהיה פריק, אבל הוא לא הכרחי: מעל $latex \mathbb{R}$ אין לפולינום $latex x^{4}+2x^{2}+1$ שורשים, אבל הוא מתפרק ל-$latex \left(x^{2}+1\right)\left(x^{2}+1\right)$. מכיוון שבהמשך הפריקות/אי הפריקות של פולינומים תשחק תפקיד חשוב, מעניין לדעת מה השיטות הבסיסיות שאיתן בודקים דברים כאלו. יש כמה כללי אצבע סטנדרטיים שאתאר את כולם פה, אבל הם בוודאי לא מהווים תיאור ממצה של כל מה שאפשר לעשות.

ראשית, שימו לב שהדוגמא שלי לפולינום פריק שאין לו שורש הייתה ממעלה 4. זה לא מקרי; פולינום ממעלה 2 או 3 הוא פריק אם ורק אם יש לו שורש, פשוט כי אחד מהגורמים בפירוק חייב להיות מדרגה 1 (כלומר, להיות מהצורה $latex ax+b=a\left(x-\left(-\frac{b}{a}\right)\right)$ שמתאימה לשורש $latex -\frac{b}{a}$).

שנית, הנה תעלול נחמד, שנוגע ברעיון עמוק יותר שבא לידי ביטוי בחלק של תורת השדות שנקרא תורת גלואה: אם $latex p\left(x\right)\in\mathbb{R}\left[x\right]$ הוא פולינום עם מקדמים ממשיים ו-$latex z=a+bi$ הוא שורש מרוכב של הפולינום, אז גם הצמוד שלו $latex \overline{z}=a-bi$ הוא שורש של הפולינום. כדי לראות את זה, בואו נכתוב לרגע את הפולינום במפורש: $latex p\left(x\right)=a_{n}x^{n}+\dots+a_{1}x+a_{0}$. אם נציב את $latex z$ נקבל

$latex p\left(z\right)=a_{n}z^{n}+\dots+a_{1}z+a_{0}=0$

עכשיו אפשר לקחת את הצמוד של שני האגפים, ולהשתמש בתכונות הסטנדרטיות של הצמוד שהן $latex \overline{z_{1}+z_{2}}=\overline{z_{1}}+\overline{z_{2}}$ ו-$latex \overline{z_{1}\cdot z_{2}}=\overline{z_{1}}\cdot\overline{z_{2}}$. נקבל:

$latex \overline{p\left(z\right)}=\overline{a_{n}z^{n}+\dots+a_{1}z+a_{0}}=\overline{a_{n}}\cdot\overline{z}^{n}+\dots+\overline{a_{1}}\cdot\overline{z}+\overline{a_{0}}$

אבל המקדמים של הפולינום הם ממשיים, כלומר שווים לצמוד של עצמם, כך שנקבל

$latex \overline{a_{n}}\cdot\overline{z}^{n}+\dots+\overline{a_{1}}\cdot\overline{z}+\overline{a_{0}}=a_{n}\cdot\overline{z}^{n}+\dots+a_{1}\cdot\overline{z}+a_{0}=p\left(\overline{z}\right)$

קיבלנו ש-$latex p\left(\overline{z}\right)=\overline{p\left(z\right)}=\overline{0}=0$. התעלול הזה, כאמור, ניתן להכללה מרחיקת לכת, אבל בינתיים נבין איך הוא עוזר לנו פה.

ראשית, אם $latex z$ הוא מספר מרוכב כלשהו, אז $latex z\cdot\overline{z}$ ו-$latex z+\overline{z}$ הם ממשיים (פשוט בדקו זאת!). לכן, אם $latex z$ הוא שורש של $latex p\left(x\right)$ והוא שונה מהצמוד שלו (כלומר, אינו ממשי) אז גם $latex \left(x-z\right)$ וגם $latex \left(x-\overline{z}\right)$ הם גורמים של $latex p\left(x\right)$ כשמפרקים אותו לגורמים מעל $latex \mathbb{C}$; ומכפלת שני הגורמים הללו היא $latex x^{2}-\left(z+\overline{z}\right)x+z\cdot\overline{z}$, שהוא פולינום עם מקדמים ממשיים. קיבלנו שיש ל-$latex p\left(x\right)$ גורם ממעלה 2 על כל שורש מרוכב שאינו ממשי של $latex p\left(x\right)$; ובנוסף לכך על כל שורש ממשי של $latex p\left(x\right)$ נקבל גורם ממעלה 1. המסקנה היא שכל פולינום מעל $latex \mathbb{R}$ מתפרק למכפלה של גורמים שהם לכל היותר ממעלה 2. שימו לב שהשתמשנו כאן כמעט במובלע במשפט היסודי של האלגברה, כשהנחנו שכל השורשים של $latex p\left(x\right)$ הם או ממשיים או מרוכבים שאינם ממשיים.

והנה תעלול למציאת שורשים שעובד רק ברציונליים ואוהבים לקרוא לו “משפט הניחוש האינטליגנטי” כי הוא נותן לנו רשימה בתקווה מצומצמת של מועמדים להיות השורשים הרציונליים של פולינום שהמקדמים שלו הם שלמים: נניח ש-$latex p\left(x\right)=a_{n}x^{n}+\dots+a_{1}x+a_{0}$ הוא פולינום שכל מקדמיו ב-$latex \mathbb{Z}$; אז אם $latex \frac{r}{s}$ הוא שורש שלו שמוצג בצורה מצומצמת, כלומר ל-$latex r,s$ אין גורם משותף, אז בהכרח $latex r|a_{0}$ ו-$latex s|a_{n}$ ($latex r$ מחלק את המקדם החופשי ו-$latex s$ מחלק את המקדם המוביל). כמקרה פרטי מקבלים שאם $latex p\left(x\right)$ הוא פולינום מתוקן, אז השורשים הרציונליים שלו הם בהכרח שלמים ומחלקים את המקדם החופשי.

אין בהוכחה משהו מתוחכם. פשוט מציבים $latex x=\frac{r}{s}$, מכפילים ב-$latex s^{n}$ כדי לנטרל את השבר, ומקבלים את התוצאה

$latex a_{n}r^{n}+a_{n-1}r^{n-1}s+\dots+a_{1}rs^{n-1}+a_{0}s^{n}=0$

עכשיו, אפשר להעביר את הגורם הראשון אגף ומקבלים

$latex -a_{n}r^{n}=s\left(a_{n-1}r^{n-1}+\dots+a_{0}s^{n-1}\right)$

כלומר, $latex s$ מחלק את אגף ימין, ולכן את אגף שמאל, אבל באגף שמאל הוא לא מחלק את $latex r^{n}$ (אחרת $latex \frac{r}{s}$ לא היה שבר מצומצם) ולכן הוא בהכרח מחלק את $latex a_{n}$; באופן דומה, אפשר להעביר את הגורם האחרון אגף, לקבל $latex -a_{0}s^{n}=r\left(a_{n}r^{n-1}+\dots+a_{1}s^{n-1}\right)$ ומכך ינבע ש-$latex r$ מחלק את $latex a_{0}$. זו הוכחה טכנית אבל אני אוהב אותה כי כשזוכרים את הרעיון שלה קל להיזכר במשפט מהראש - למה מחלקים דווקא את המקדם המוביל והמקדם החופשי ולמה המכנה מחלק את המקדם המוביל והמונה את החופשי.

כלל האצבע האחרון שאני רוצה להראות הוא טכניקה שמאפשרת להוכיח שפולינום הוא אי-פריק (משהו שעד עכשיו לא הראיתי). היא לא יעילה תמיד, אבל כשהיא כן היא מאוד פשוטה לבדיקה - ועוד יתרון הוא שקל יחסית לבנות פולינום אי פריק על סמך מה שהיא מציעה. השיטה הזו נקראת קריטריון אייזנשטיין. נתחיל מלהציג מקרה פרטי שלה: ניקח פולינום מתוקן עם מקדמים שלמים $latex a\left(x\right)=x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$. כעת, נניח ש-$latex p$ הוא מספר ראשוני שמחלק את כל המקדמים של הפולינום למעט את זה של $latex x^{n}$, ובנוסף לכך ש-$latex p^{2}$ אינו מחלק את $latex a_{0}$ - אז הפולינום אי פריק מעל $latex \mathbb{Q}$. למשל, $latex x^{3}+2x+6$ הוא אי פריק בגלל $latex p=2$ (הייתם יכולים לראות זאת גם בעזרת הטכניקות הקודמות; השורשים האפשריים היחידים של הפולינום הזה מעל הרציונליים הם 1,2,3,6 והשלילות שלהם, ובדיקה ישירה מראה שאף אחד מהם אינו שורש, ואם פולינום ממעלה שלישית הוא פריק בהכרח יש לו שורש).

איך מוכיחים את הקריטריון? אין סיבה לא להוכיח אותו בצורה כללית יותר, עבור תחום שלמות כלשהו. יהא $latex R$ תחום שלמות ו-$latex a\left(x\right)=x^{n}+a_{n-1}x^{n-1}+\dots+a_{1}x+a_{0}$ פולינום מתוקן ב-$latex R\left[x\right]$. אם קיים אידאל ראשוני $latex P$ כך ש-$latex a_{0},a_{1},\dots,a_{n-1}\in P$ אבל $latex a_{0}\notin P^{2}$ אז $latex p\left(x\right)$ אי-פריק מעל $latex R$.

אולי כדאי להזכיר מהו $latex P^{2}$. מכפלה של אידאלים באופן כללי היא אוסף הסכומים הסופיים של מכפלות של אברי האידאלים. כלומר, במקרה שלנו $latex P^{2}=\left\{ \sum ab\ |\ a\in P,b\in P\right\} $.

בואו נראה כעת איך מוכיחים את הקריטריון. נניח בשלילה ש-$latex a\left(x\right)=b\left(x\right)c\left(x\right)$ עבור פולינומים ממעלה לפחות 1 $latex b\left(x\right),c\left(x\right)$ מעל $latex R$. עכשיו בואו נעבור לדבר על החוג $latex R/P$. החוג הזה הוא תחום שלמות כי $latex P$ הוא אידאל ראשוני, ואפשר לדבר על פולינומים מעל החוג הזה. בפרט, אפשר לדבר על $latex a\left(x\right),b\left(x\right),c\left(x\right)$ מעליו; אנחנו פשוט מחליפים כל מקדם של הפולינומים הללו בתמונה שלו בחוג המנה $latex R/P$. למשל, אני מסמן

$latex \overline{a\left(x\right)}=x^{n}+\left(a_{n-1}+P\right)x^{n-1}+\dots+\left(a_{1}+P\right)x+\left(a_{0}+P\right)$

עכשיו, אם $latex a_{i}\in P$ אז $latex a_{i}+P=P$; אתם צריכים לחשוב על $latex P$ בתור “סקלר האפס” בחוג המנה $latex R/P$, כך ש-$latex \overline{a\left(x\right)}$ הוא בעצם פולינום פשוט במיוחד: $latex \overline{a\left(x\right)}=x^{n}+P$. כדי לפשט לי את הסימונים אני אפסיק לכתוב $latex +P$ ולשים גג מעל פולינומים; פשוט נבין שפעולות החשבון שאנחנו מבצעים הן מעכשיו בחוג $latex R/P$.

אם כן, בחוג $latex R/P$ יש לנו את הסיטואציה הבאה: שני פולינומים ממעלה 1 לפחות $latex b\left(x\right),c\left(x\right)$ כך ש-$latex b\left(x\right)c\left(x\right)=x^{n}$. אכתוב אותם במפורש:

$latex b\left(x\right)=b_{m}x^{m}+\dots+b_{1}x+b_{0}$

$latex c\left(x\right)=c_{k}x^{k}+\dots+c_{1}x+c_{0}$

כאשר $latex m,k<n$ ו-$latex m+k=n$. מכך ש-$latex b\left(x\right)c\left(x\right)=x^{n}$ אני מקבל $latex n+1$ משוואות שמתארות את הקונבולוציה של המקדמים של $latex b\left(x\right),c\left(x\right)$:

$latex b_{0}c_{0}=0$

$latex b_{0}c_{1}+b_{1}c_{0}=0$

$latex \vdots$

$latex b_{m-1}c_{k}+b_{m}c_{k-1}=0$

$latex b_{m}c_{k}=1$

בואו נתחיל מהמשוואה הראשונה, $latex b_{0}c_{0}=0$. אנחנו בתחום שלמות $latex R/P$ ולכן או $latex b_{0}$ או $latex c_{0}$ הם 0; נניח בלי הגבלת הכלליות ש-$latex b_{0}=0$. עכשיו נכנס לפעולה הנתון לפיו $latex a_{0}\notin P^{2}$; אם ב-$latex R/P$ היה מתקיים ש-$latex b_{0}=c_{0}=0$ זה היה אומר שבחוג $latex R$ מתקיים $latex b_{0}\in P$ וגם $latex c_{0}\in P$ ולכן $latex a_{0}=b_{0}c_{0}\in P^{2}$. זה בלתי אפשרי, ולכן בחוג $latex R/P$ מתקיים $latex c_{0}\ne0$. אני טוען שאי השוויון הקטן הזה יגרום לתגובת שרשרת בקרב כל משוואות הקונבולוציה שלעיל שתכריח את כל המקדמים של $latex b\left(x\right)$ להיות אפס, עד אשר נקבל סתירה במשוואה האחרונה, $latex b_{m}c_{k}=1$.

ראינו כבר ש-$latex b_{0}=0$. זה הופך את המשוואה השניה ל-$latex b_{1}c_{0}=0$, ומכיוון ש-$latex c_{0}\ne0$ אז $latex b_{1}=0$. עכשיו המשוואה השלישית, שלא כתבתי, תהפוך ל-$latex b_{2}c_{0}=0$, וכן הלאה וכן הלאה. מתישהו נגיע אל $latex b_{m}c_{0}=0$ (במשוואה של המקדם $latex x^{m}$, שהוא $latex \sum_{i=0}^{m}b_{i}c_{m-i}=0$ כי $latex m<n$) ונסיק ש-$latex b_{m}=0$; אבל עכשיו המשוואה $latex b_{m}c_{k}=1$ לא יכולה להתקיים, והגענו לסתירה עם ההנחה ש-$latex a\left(x\right)$ היה פריק.

זה מסיים את ההוכחה של קריטריון אייזנשטיין וגם את הפוסט; כמובן שזה לא סוף הסיפור של הפולינומים אלא בקושי ההתחלה.


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com