שדות סופיים – מי, מה, כמה ולמה

בפוסט הקודם הסברתי מהו שדה והראיתי דוגמאות לשדות סופיים פשוטים: השדות $latex \mathbb{Z}_{p}$ לכל ראשוני $latex p$ של השלמים מ-0 עד $latex p-1$ עם חיבור וכפל מודולו $latex p$ (הסברתי מדוע זה חייב להיות ראשוני). בפוסט הזה אני רוצה לשכנע אתכם בשלושה דברים, בהתבסס על כמה תוצאות במתמטיקה שאותן אציין אך לא אוכיח – ראשית, שכל שדה סופי חייב להכיל מספר איברים שהוא חזקה של ראשוני (ולכן, למשל, אין שדה סופי עם 10 איברים, כי 10 אינו חזקה של ראשוני); שנית, שלכל חזקה כזו של ראשוני קיים שדה סופי עם מספר האיברים הזה בדיוק; ושלישית, שהשדה הזו הוא יחיד, כלומר כל שני שדות סופיים עם אותו מספר איברים הם "אותו דבר", במובן זה שעל ידי שינוי הסימון של איברי השדה הראשון מקבלים בדיוק את השדה השני.

כדי להבין כמה זה מעניין כדאי לחשוב על מבנה קצת יותר פשוט משדה – חבורה. חבורה היא קבוצה שבה יש רק פעולה אחת (שנקראת לפעמים "כפל" אבל יש לה המון פרשנויות אפשריות – חיבור רגיל, כפל רגיל, הרכבה של פונקציות ועוד ועוד; הכל בהתאם להקשר) שצריכה לקיים רק אסוציאטיביות, קיום אדיש לפעולה וקיום הופכי לפעולה (אפילו קומוטטיביות לא דורשים). לכל מספר $latex n$ קיימת חבורה עם $latex n$ איברים, ולרוב המספרים קיימות המון חבורות, שנראות שונות אחת מהשניה באופן מהותי. אפילו עבור $latex n=4$ כבר יש שתי חבורות שונות (נסו למצוא אותן). כך שהמבנה הנוסף של שדה בעצם "כופה" הרבה יותר סדר על העניינים. אגב, אם אני כבר מזכיר את זה – אחת מהתוצאות הנחמדות הבסיסיות של תורת החבורות היא שעבור ראשוני $latex p$ קיימת רק חבורה יחידה עם $latex p$ איברים; הנה שוב הראשוניים נכנסים לתמונה.

אז בואו ניקח את $latex q$ להיות מספר טבעי כלשהו ונניח שיש לנו שדה סופי $latex F$ עם בדיוק $latex q$ איברים. בהכרח $latex F$ חייב להיות ממציין שונה מאפס, כי אם היה ממציין אפס הוא היה מכיל לפחות את $latex \mathbb{Q}$ שהיא קבוצה אינסופית. אז המציין שלו הוא $latex p$ עבור ראשוני כלשהי, וזה אומר שבתוך $latex F$ מתחבא לו עותק של $latex \mathbb{Z}_{p}$. במילים אחרות, $latex F$ הוא שדה סופי שמכיל את השדה $latex \mathbb{Z}_{p}$. על סיטואציה כזו אומרים ש-$latex F$ הוא שדה הרחבה של $latex \mathbb{Z}_{p}$ (אם כי בדרך כלל קצת נזהרים ואומרים דברים בסגנון "$latex F$ מכיל עותק איזומורפי של $latex \mathbb{Z}_{p}$" וכדומה – לא אכנס לדקויות הללו כאן). לרוב משתמשים בסימון $latex F/\mathbb{Z}_{p}$ כדי לומר ש-$latex F$ מרחיב את $latex \mathbb{Z}_{p}$, ובאופן כללי $latex F/E$ אומר ש-$latex F,E$ הם שדות ו-$latex E\subseteq F$.

את מה שהולך לקרות עכשיו אפשר לסכם עבור מי שבקיא במושגים המתאימים כך: קל לראות ש-$latex F$ הוא מרחב וקטורי מעל $latex \mathbb{Z}_{p}$ ממימד סופי $latex n$ ולכן יש $latex p^{n}$ צירופים לינאריים אפשריים של אברי הבסיס ולכן ב-$latex F$ בדיוק $latex p^{n}$ איברים. עכשיו אנסה להסביר מה זה אומר גם עבור מי שלא בקיא כל כך במושגים.

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

פורמלית, מרחב וקטורי $latex V$ מעל שדה $latex F$ נראה כמו "שדה בלי פעולת כפל" – כלומר, מוגדרת על $latex V$ פעולת חיבור בין איברים שהיא אסוציאטיבית וקומוטטיבית וקיים איבר אדיש חיבורי (שמסומן ב-$latex \overline{0}$ כי רוצים להבדיל בין האדיש החיבורי של $latex V$ לאדיש החיבורי של $latex F$) וקיים הופכי חיבורי לכל איבר, ובנוסף לכך יש גם פעולת כפל של איבר מ-$latex V$ באיבר מ-$latex F$. אברי $latex F$ מכונים "סקלרים" כדי להבדיל אותם מאברי $latex V$, ולרוב גם מסמנים אותם באות מוזרה כמו $latex \lambda$ לשם כך. הדרישה היא שהכפל הזה "יתנהג יפה", במובן זה ש-$latex \lambda_{1}\cdot\left(\lambda_{2}\cdot v\right)=\left(\lambda_{1}\times\lambda_{2}\right)\cdot v$ (שימו לב! סימנתי כאן ב-$latex \cdot$ כפל של סקלר בוקטור, וב-$latex \times$ כפל של שני סקלרים כדי שיהיה ברור למה השוויון לעיל לא מובן מאליו), וש-$latex \left(\lambda_{1}+\lambda_{2}\right)v=\lambda_{1}v+\lambda_{2}v$ וש-$latex \lambda\left(v+u\right)=\lambda v+\lambda u$.

שלוש התכונות שלעיל הן מעין תכונות של אסוציאטיביות ודיסטריביוטיביות על כפל של סקלר בוקטור. הן מבטיחות שמרחבים וקטוריים יהיו בעלי מבנה יפה ופשוט יחסית – כל כך פשוט שאפשר להבין את רוב המבנה הזה כבר במסגרת קורס הבסיס באלגברה לינארית, מה שהופך את הנושא הזה למבוא טוב (לדעתי) למתמטיקה מופשטת. חלק מהמבנה הזה בא לידי ביטוי בתוצאה הבאה: לכל מרחב וקטורי $latex V$ מעל כל שדה $latex F$ קיימת קבוצה $latex B\subseteq V$ כך שלכל $latex v\in V$ ניתן לכתוב $latex v=\sum_{i=1}^{n}\lambda_{i}b_{i}$, כאשר $latex \lambda_{i}\in F$ ו-$latex b_{i}\in B$. הקבוצה $latex B$ נקראת בסיס, סכום מהצורה $latex \sum_{i=1}^{n}\lambda_{i}b_{i}$ נקרא "צירוף לינארי של איברי $latex B$" (הוא חייב להיות סופי – אין משמעות לסכום אינסופי כאן), ואולי אתם כבר מנחשים שחסרה לי כאן עוד תכונה מהותית כי למה לא לקחת את $latex V$ להיות $latex B$ עצמה? התכונה המהותית היא שלכל $latex v\in V$, התיאור של $latex v$ כצירוף לינארי של אברי $latex B$ הוא יחיד.

בואו נבין איך זה עוזר לנו. ראשית, קל לראות שאם $latex F$ הוא שדה שמכיל את $latex \mathbb{Z}_{p}$ אז הוא אכן מרחב וקטורי מעליו, כשהפעולה של כפל בסקלר מ-$latex \mathbb{Z}_{p}$ היא פשוט פעולת הכפל הרגילה ב-$latex F$ (מכאן נובעות תכונות האסוציאטיביות והדיסטריביוטיביות מייד מכך שהן מתקיימות לכל שני איברים ב-$latex F$). לכן קיים בסיס ל-$latex F$, ומכיוון ש-$latex F$ סופי, גם הבסיס סופי – בואו נסמן את מספר האיברים שבו ב-$latex n$. כעת, כל איבר ב-$latex F$ ניתן לכתיבה בצורה יחידה כ-$latex \sum_{i=1}^{n}\lambda_{i}b_{i}$ (כאשר $latex \lambda_{i}\in\mathbb{Z}_{p}$ ו-$latex b_{i}$ איבר בסיס), וגם ברור שכל ביטוי מהצורה $latex \sum_{i=1}^{n}\lambda_{i}b_{i}$ הוא איבר חוקי ב-$latex F$ (כי $latex F$ שדה; לכפול איברים מהשדה ולחבר אותם בסופו של דבר מניב איבר בשדה). לכן מספר האיברים ב-$latex F$ הוא בדיוק כמספר הביטויים מהצורה $latex \sum_{i=1}^{n}\lambda_{i}b_{i}$. כמה כאלו יש? ובכן, כמספר הדרכים השונות שלנו לבחור את המקדמים $latex \lambda_{i}$. לכל $latex 1\le i\le n$ אנחנו יכולים לבחור כל סקלר מתוך $latex \mathbb{Z}_{p}$, וזו קבוצה בעלת $latex p$ איברים. אז יש לנו בסך הכל $latex p\cdot p\cdots p$ בחירות, כאשר הכפל הוא של $latex n$ איברים – בסך הכל $latex p^{n}$, ולכן זהו גודל השדה: $latex q=p^{n}$. את כל זה אפשר לסכם, כאמור, ב-"קל לראות ש-$latex F$ הוא מרחב וקטורי מעל $latex \mathbb{Z}_{p}$ ממימד סופי $latex n$ ולכן יש $latex p^{n}$ צירופים לינאריים אפשריים של אברי הבסיס ולכן ב-$latex F$ בדיוק $latex p^{n}$ איברים."

יפה, אז ראינו שכל שדה סופי חייב להיות בעל $latex p^{n}$ איברים עבור $latex p$ ראשוני ו-$latex n$ טבעי כלשהם. כעת נותר להראות כי לכל ראשוני ולכל טבעי אכן קיים שדה שמכיל את המספר הזה של איברים, ושהוא יחיד. הרעיון הוא להתחיל מ-$latex \mathbb{Z}_{p}$ ולהרחיב אותו באופן כזה שיתקבל שדה בן $latex p^{n}$ איברים. כאן אנו נזקקים למושג מרכזי בתורת השדות – שדה פיצול של פולינום.

נניח ש-$latex F$ הוא שדה כלשהו (אפילו לא בהכרח סופי), אז פולינום מעליו הוא ביטוי מהצורה $latex a_{k}x^{k}+a_{k-1}x^{k-1}+\dots+a_{1}x+a_{0}$, כאשר $latex a_{0},\dots,a_{k}$ הם כולם איברים של $latex F$ ומכונים מקדמי הפולינום, ואילו $latex x$ הוא סתם סימון. אפשר להציב בפולינום ערכים – להחליף את $latex x$ ביצורים שבאמת אפשר לכפול במקדמים ולחבר ולראות מה מקבלים. אם מקבלים 0, אז הערך נקרא שורש של הפולינום (אין קשר אמיתי ל-$latex \sqrt{}$, אם כי שורש של הפולינום $latex x^{2}-a$ הוא אכן $latex \sqrt{a}$). אם יש לנו פולינום שמקדמיו לקוחים מתוך $latex F$, זה לחלוטין לא מבטיח שיהיו לו שורשים ב-$latex F$, אבל ייתכן שיהיו לו שורשים בשדה שמכיל את $latex F$. למשל, לפולינום $latex x^{2}-2$, שמקדמיו לקוחים מתוך $latex \mathbb{Q}$, אין שורשים רציונליים כי $latex \sqrt{2}$ איננו רציונלי וכך גם $latex -\sqrt{2}$.

שורש כזה מצוי, למשל, ב-$latex \mathbb{R}$, והרי $latex \mathbb{R}/\mathbb{Q}$ היא הרחבת שדות לגיטימית על פי ההגדרה שנתתי למעלה. אלא שזו הרחבה "חזקה מדי" במובן מסויים – יש ב-$latex \mathbb{R}$ גם המון איברים שלא קשורים בכלל לפולינום $latex x^{2}-2$ וגם כאלו שלא מאפסים אף פולינום במקדמים רציונליים, למשל $latex \pi$. אם מסתכלים על $latex \mathbb{R}$ כמרחב וקטורי מעל $latex \mathbb{Q}$ מקבלים מרחב אינסוף-ממדי. בקיצור, נראה שאולי כדאי לדבר כאן על רזולוציות קטנות יותר.

כאן נכנס לתמונה השדה $latex \mathbb{Q}\left(\sqrt{2}\right)$ שהזכרתי בפוסט הקודם – השדה שאיבריו הם כל המספרים הממשיים מהצורה $latex a+b\sqrt{2}$ כאשר $latex a,b$ רציונליים. בשדה הזו נמצאים כל השורשים של הפולינום $latex x^{2}-2$, ולא קשה במיוחד לראות שהוא "אופטימלי" במובן זה שכל שדה הרחבה של $latex \mathbb{Q}$ שמכיל את שני השורשים הללו, מכיל גם את $latex \mathbb{Q}\left(\sqrt{2}\right)$ (אם שדה מכיל גם את הרציונליים וגם את $latex \sqrt{2}$ אז בוודאי שאפשר לכפול את $latex \sqrt{2}$ ברציונלי $latex b$ כלשהו ולקבל ש-$latex b\sqrt{2}$ גם הוא איבר בשדה; ולזה אפשר לחבר $latex a$ רציונלי כלשהו ולקבל שוב איבר בשדה; ולכן $latex a+b\sqrt{2}$ בהכרח בשדה). שדה הרחבה כזה מכונה שדה הפיצול של הפולינום. בניסוח פורמלי: בהינתן פולינום $latex p\left(x\right)$ שמקדמיו לקוחים משדה $latex F$, שדה הפיצול שלו הוא שדה הרחבה של $latex F$ שבו נמצאים כל שורשי $latex p\left(x\right)$ והוא מינימלי ביחס להכלה.

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

כדי לבנות את ההרחבה הזו משתמשים בכלים סטנדרטיים מתורת החוגים דווקא – מסתכלים על חוג הפולינומים מעל $latex F$ ובונים חוג מנה כלשהו של חוג הפולינומים הזה ומהר מאוד מתברר שהוא שדה, ושדה שבו ל-$latex p\left(x\right)$ יש שורש. זו בניה נפלאה ואני לא הולך להגיד עליה עוד שום דבר. על ההוכחה ששדה הפיצול הוא יחיד, שהיא לב העניין פה, אני הולך להגיד עוד פחות. השימוש שלי בכל הסיפור הזה צפוי: לכל $latex n$ טבעי, אני הולך להציג פולינום מעל $latex \mathbb{Z}_{p}$ כך ששדה הפיצול שלו הוא בדיוק הרחבה מדרגה $latex n$ (כלומר, אם חושבים עליה כמרחב וקטורי מעל $latex \mathbb{Z}_{p}$, המימד שלה יהיה $latex n$). זה יראה לי קיום, ועם עוד טיפונת מאמץ גם יראה יחידות.

אז בואו ניקח $latex q=p^{n}$ כלשהו וננסה לבנות שדה סופי עם $latex q$ איברים, בתור שדה פיצול של פולינום מסויים מעל $latex \mathbb{Z}_{p}$. כדי להבין איזה פולינום כדאי לקחת בשביל שדה הפיצול, צריך להראות עוד טריק שמגיע הפעם הישר מתורת החבורות. שדה הוא גם חבורה ביחס לכפל, בתנאי שמעיפים ממנו את 0 שאין לו הופכי כפלי. כלומר, משדה עם $latex q$ איברים אפשר לקבל חבורה כפלית עם $latex q-1$ איברים (לרוב מסמנים אותה ב-$latex F^{*}$, אבל נעזוב את זה). כאן אני שולף מהשרוול משפט בסיסי בתורת החבורות – אם יש לנו חבורה עם $latex m$ איברים ו-$latex a$ הוא איבר בחבורה, אז $latex a^{m}=1$ ($latex a$ בחזקת $latex m$ הוא מה שמתקבל כשכופלים את $latex a$ בעצמו $latex m$ פעמים). מקרה פרטי מפורסם של המשפט הזה נקרא "המשפט הקטן של פרמה" (לא המשפט האחרון של פרמה!) ואולי שמעתם עליו. מכל מקום, במקרה שלנו המסקנה היא ש-$latex a^{q-1}=1$ לכל $latex a\in F$ שאיננו אפס; ולכן $latex a^{q}=a$ לכל $latex a\in F$, כולל אפס (עבור אפס מוודאים את המשוואה ישירות…). מכאן ש-$latex a^{q}-a=0$, והנה גילינו פולינום שמאפס את כל איברי $latex F$: $latex p\left(x\right)=x^{q}-x$. זה יהיה הפולינום שאת שדה הפיצול שלו ניקח, ונקבל ששדה הפיצול כולל בדיוק את כל השורשים שלו, ושום דבר פרט להם.

אם כן, הבה נסמן ב-$latex E$ את שדה הפיצול של $latex x^{q}-x$ מעל $latex \mathbb{Z}_{p}$. "שדה פיצול" הוא מונח טיפה אבסטרקטי ולא ברור לנו איך $latex E$ נראה כרגע, אז בואו נגדיר קבוצה $latex K$ של כל איברי $latex E$ שהם שורשים של $latex x^{q}-x$, כלומר $latex K=\left\{ a\in E|a^{q}-a=0\right\} $. הפאנץ' הוא שגם קבוצת השורשים הזו היא עצמה שדה; ומכיוון ששדה הפיצול של פולינום הוא השדה המינימלי ביחס להכלה שמכיל את כל השורשים שלו, נקבל ש-$latex E=K$. אבל איך משתכנעים ש-$latex K$ הוא שדה? אין מה לעשות, צריך לבדוק את כל התכונות של שדה. למרבה המזל, תכונות כמו קומוטטיביות, אסוציאטיביות ודיסטריביוטיות "נורשות" מהשדה הגדול ביותר (קחו $latex a,b\in K$, אז בפרט $latex a,b\in E$ ולכן $latex a+b=b+a$ כי $latex E$ שדה; אז המשוואה הזו מתקיימת באותה מידה גם ב-$latex K$). נשאר לבדוק שכפל וחיבור של איברים ב-$latex K$ עדיין משאירים אותנו ב-$latex K$; ש-0,1 שניהם ב-$latex K$; ושאם $latex a\in K$ כך גם ההופכיים החיבורי והכפלי שלו.

די בבירור 0,1 מאפסים את הפולינום $latex x^{q}-x$, כך שזו לא בעיה.

בואו נעבור לטפל בתכונות הסגירות: אנחנו רוצים להראות שאם לוקחים שורשים כלשהם של $latex x^{q}-x$ אז גם ההופכיים החיבורי והכפלי שלהם, וסכומם, ומכפלתם – כולם גם הם שורשים של $latex x^{q}-x$.

בנוגע לקיום הופכי חיבורי: אם $latex q$ אי זוגי אז

$latex \left(-a\right)^{q}-\left(-a\right)=\left(-1\right)^{q}a^{q}+a=-a^{q}+a=-\left(a^{q}-a\right)=0$

ואם $latex q$ זוגי אז בהכרח $latex q=2^{n}$ ואז השדה שבנינו הוא מעל $latex \mathbb{Z}_{2}$, שהוא ממציין 2; ובמציין 2, $latex 1=-1$ ולכן $latex -a=a\in K$.

בנוגע לקיום הופכי כפלי,

$latex \left(a^{-1}\right)^{q}-a^{-1}=\left(a^{q}\right)^{-1}-a^{-1}=a^{-1}-a^{-1}=0$

כאן הסתמכתי על זה ש-$latex a^{q}=a$ שהרי $latex a$ הוא שורש של $latex x^{q}-x$.

נותר רק להראות שכפל של שורשים הוא שורש, ושסכום של שורשים הוא שורש. כפל גם הוא קל:

$latex \left(ab\right)^{q}-\left(ab\right)=a^{q}b^{q}-ab=ab-ab=0$

שוב, הסתמכתי על כך ש-$latex a^{q}=a$ וכו'.

עבור חיבור היינו רוצים לעשות את אותו הדבר:

$latex \left(a+b\right)^{q}-\left(a+b\right)=\left(a^{q}+b^{q}\right)-\left(a+b\right)=\left(a+b\right)-\left(a+b\right)=0$

אבל כאן אנחנו בבעיה – השוויון $latex \left(a+b\right)^{q}=a^{q}+b^{q}$ נראה אמנם מפתה, אבל כולם יודעים שהוא אינו נכון. הוא עד כדי כך מפתה עד שהוא זכה לשם Freshman's dream , אבל כבר בחזקת 2 אנחנו יודעים שזה לא עובד: $latex \left(a+b\right)^{2}=a^{2}+2ab+b^{2}$ וזה כמובן שונה מ-$latex a^{2}+b^{2}$. רק מה, אמרתי לכם שבשדות סופיים העולם מתנהג שונה ממה שאנחנו רגילים; ולמעשה, אפילו לא צריך שדות סופיים אלא שדות ממציין שונה מאפס. הנה לכם טענה נחמדה: בשדה ממציין $latex p$, השוויון $latex \left(a+b\right)^{q}=a^{q}+b^{q}$ הוא נכון לחלוטין אם $latex p$ מחלק את $latex q$.

למה? ובכן, בשדה ממציין $latex p$, כל איבר שמחברים לעצמו מספר פעמים שהוא כפולה של $latex p$ הוא אפס. כעת, את $latex \left(a+b\right)^{q}$ אפשר לפתוח בעזרת הבינום של ניוטון ולקבל $latex \left(a+b\right)^{q}=\sum_{i=0}^{q}{q \choose i}a^{q-i}b^{i}$. האיבר הראשון פה הוא $latex a^{q}$ והאחרון הוא $latex b^{q}$, ומה באמצע? האיבר השני הוא $latex qa^{q-1}b$, כלומר $latex a^{q-1}b$ מחובר לעצמו $latex q$ פעמים, וזו כפולה של $latex p$ אז האיבר הזה מתאפס. ובאופן כללי?

באופן כללי קל להתחיל מהמקרה שבו $latex q=p$, כלומר החזקה עצמה היא הראשוני $latex p$. במקרה כזה $latex {p \choose i}=\frac{p!}{i!\left(p-i\right)!}$ בבירור חייב להתחלק ב-$latex p$, כי $latex p$ מחלק את המונה (הוא חלק מהמכפלה $latex p!$) אבל אינו מחלק את המכנה, כי המכנה הוא כולו מכפלה של מספרים שקטנים יותר מ-$latex p$, ו-$latex p$ ראשוני. מכאן נובע חיש קל ש-$latex \left(a+b\right)^{p}=a^{p}+b^{p}$, ומכאן פשוט להמשיך הלאה באינדוקציה: אם כבר ראינו ש-$latex \left(a+b\right)^{p^{n-1}}=a^{p^{n-1}}+b^{p^{n-1}}$, אז

$latex \left(a+b\right)^{p^{n}}=\left(\left(a+b\right)^{p^{n-1}}\right)^{p}=\left(a^{p^{n-1}}+b^{p^{n-1}}\right)^{p}=\left(a^{p^{n-1}}\right)^{p}+\left(b^{p^{n-1}}\right)^{p}=a^{p^{n}}+b^{p^{n}}$

ובכך הוכחנו ש-$latex \left(a+b\right)^{q}=a^{q}+b^{q}$ לכל $latex q=p^{n}$, כשאנו עובדים בשדה ממציין $latex p$.

נסכם – ראינו שאותו $latex K$, אוסף השורשים של $latex x^{q}-x$ בשדה הפיצול של הפולינום הזה מעל $latex \mathbb{Z}_{p}$, הוא בעצמו שדה. ולכן זהו שדה הפיצול המדובר. לפולינום $latex x^{q}-x$ יש בדיוק $latex q$ שורשים כי ידוע שלפולינום ממעלה $latex n$ יש $latex n$ שורשים, ולכן…

הופ! שוב נפלנו למלכודת. אמנם, אפשר להוכיח שלפולינום ממעלה $latex n$ יש בשדה הפיצול שלו $latex n$ שורשים – עושים זאת באינדוקציה תוך אבחנה שאם $latex a$ שורש של $latex p\left(x\right)$ אז $latex p\left(x\right)=\left(x-a\right)q\left(x\right)$ כאשר $latex q\left(x\right)$ פולינום שדרגתו קטנה ב-1 מדרגת $latex p\left(x\right)$ וכל שורש שלו הוא גם שורש של $latex q\left(x\right)$ – אבל זה לא מבטיח שאותם שורשים הם שונים. למשל, לפולינום $latex x^{2}-2x+1$ יש רק שורש יחיד: 1. זה שורש "מריבוי 2" כי אם כותבים את הפולינום כמכפלה של איקס-פחות-שורש, אז הגורם שמתאים ל-1 מופיע בחזקת 2: $latex x^{2}-2x+1=\left(x-1\right)^{2}$. באופן דומה לפולינום $latex \left(x-3\right)^{4}\left(x-5\right)$ יש שני שורשים: 5, שהוא שורש מריבוי 1, ו-3, שהוא שורש מריבוי 4. כשנפתח את הסוגריים נקבל פולינום ממעלה חמישית.

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

הנגזרת של הפולינום $latex a_{k}x^{k}+a_{k-1}x^{k-1}+\dots+a_{1}x+a_{0}$ היא הפולינום $latex a_{k}kx^{k-1}+a_{k-1}\left(k-1\right)x^{k-2}+\dots+a_{1}$. במילים אחרות, כופלים את המקדם של $latex x^{k}$ ב-$latex k$ ומקטינים את החזקה ב-1. בדרך כלל אם $latex p\left(x\right)$ הוא פולינום, הנגזרת הפורמלית שלו מסומנת ב-$latex p^{\prime}\left(x\right)$.

זו הגדרה "פורמלית", במובן זה שהיא לא מתבססת על גבולות, כמו ההגדרה הרגילה של נגזרת. הסיבה לכך היא שנגזרת היא מושג שבא לטפל במחלקה רחבה בהרבה של פונקציות, אבל במחיר של הנחות מסויימות של מבנה טופולוגי על השדה שמעליו עובדים (למשל, מעל $latex \mathbb{R}$ הנגזרת מתבססת על כך שיש מושג של מרחק שמוגדר באמצעות ערך מוחלט). אנחנו לא רוצים להיכנס לזה ואין לנו בהכרח דרך טובה להגדיר נגזרת מעל שדות כלליים, ומצד שני מושג הנגזרת ספציפית עבור פולינומים הוא עדיין יעיל למדי, ולכן אנחנו מגדירים אותו באופן ישיר שכזה. מההגדרה הזו קל להוכיח את כללי הנגזרת הרגילים – למשל, ש-$latex \left(p\left(x\right)\cdot q\left(x\right)\right)^{\prime}=p^{\prime}\left(x\right)q\left(x\right)+p\left(x\right)q^{\prime}\left(x\right)$, ותוצאה נחמדה אחת שנעזרת בנגזרת של פולינומים היא זו: לפולינום $latex p\left(x\right)$ יש שורש מריבוי גדול מ-1 אם ורק אם יש ל-$latex p\left(x\right)$ ול-$latex p^{\prime}\left(x\right)$ שורש משותף (ומן הסתם, כל שורש משותף כזה יהיה דוגמה לשורש מריבוי גדול מ-1).

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

כאשר גוזרים את $latex x^{q}-x$ מקבלים $latex qx^{q-1}-1$, אבל מכיוון ש-$latex p$ מחלק את $latex q$, אז הנגזרת היא $latex -1$, שהוא פולינום ממעלה אפס ובפרט אין לו שורשים, ולכן לא יכול להיות לו שורש משותף עם $latex x^{q}-x$ ולכן אין לפולינום הזה שורש מרובה וכל שורשיו שונים, כפי שרצינו. כאן זה יישום פשוט למדי של התעלול עם הנגזרת, אבל זה תעלול מועיל באופן כללי.

אם כן, לסיכום – הראנו ששדה הפיצול של $latex x^{q}-x$ מעל $latex \mathbb{Z}_{p}$ הוא בעל בדיוק $latex q$ איברים, מה שהוכיח את קיומו של שדה עם $latex q$ איברים. היחידות נובעת מכך ששדה פיצול הוא יחיד: נניח שיש לנו עוד שדה עם $latex q=p^{n}$ איברים. הוא חייב להיות ממציין $latex p$ (כי אם היה ממציין אחר, מספר האיברים שבו היה חייב להיות חזקה של המציין האחר הזה) ולכן מכיל בתוכו את $latex \mathbb{Z}_{p}$. בנוסף, מכיוון שהוא בעל $latex q$ איברים אז כפי שכבר ראינו כל איבר בו מקיים $latex a^{q}-a=0$, ולכן הוא מכיל את כל שורשי $latex x^{q}-x$ ורק אותם – לכן הוא שדה פיצול של $latex x^{q}-x$, וכפי שאמרנו שדה פיצול הוא יחיד. זה מסיים את ההוכחה.

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

23 תגובות בנושא “שדות סופיים – מי, מה, כמה ולמה”

  1. למעשה, התכוונתי לומר שיש אפילו שתי חבורות אבליות מאותו סדר לפחות, ואז כל מה שהיית צריך לעשות הוא להביא לי את 6. אני לא ממש מבין מה עבר לי בראש…

  2. ובכן, לא. למשל, הסגור האלגברי של הרציונליים הוא עדיין בן מניה, ואין תיאור יפה לכל תת השדות שלו…

  3. ניטפוק קל:

    1) נניח ש-a הוא שורש של pleft(xright), אז אפשר לכתוב pleft(xright)=left(x-aright)qleft(xright) כך ש-a אינו שורש של pleft(xright).
    משהו לא בסדר במשפט (החלק "ש-a אינו שורש של pleft(xright " מיותר)

    2) "שעבור ראשוני p קיימת רק חבורה יחידה עם $latex p$ איברים; הנה שוב הראשוניים נכנסים לתמונה."
    משהו עם ה-latex p לא מסתדר (אולי זה רק אצלי בדפדפן?).

    3) כשהרחבת את Q כדי להראות שדה בו יש שורש לפולינום x^2-2, השתמשת ב-R, ואז אמרת שהוא "גדול מידי". אבל במובן מסוים, R הוא לא גדול מספיק – עבור הפולינום x^2+1 כבר לא יהיו בו שורשים מתאימים לפולינום.

  4. 1) כן, הוא שריד לניסוח שונה של הפסקה הזו. אתקן.
    2) לא, זה שריד לתיקון בעקבות ההערה של אלון.
    3) זה נכון אבל לא רלוונטי. הנקודה הייתה שלא צריך את *כל* R בשביל ההרחבה שאנחנו רוצים לבצע (בפרט, לא צריך להוסיף איברים טרנסנדנטיים, לעבור לשדה שאינו בן מניה, וכו').

  5. אין לי ספק שקיים שדה יחיד בן 8 איברים: הרי הוכחת את זה כאן בפוסט. ובכל זאת, אני מסתכל על 2 שדות שנראים לי שונים. כנראה שאו שאחד מהם לא שדה, או שהם איזומורפיים, ואני לא רואה את זה.
    אם נסמן את האיברים ב-0 עד 7, בשני השדות פעולת החיבור היא BITWISE XOR (כלומר למשל 3+5=6), אבל יש שני "לוחות כפל" ששניהם מתאימים עבור 2-7 (כפל ב-1 וב-0 די מובן מאליו).
    הלוח הראשון הוא:

    4 6 3 1 7 5
    6 5 7 4 1 2
    3 7 6 2 5 1
    1 4 2 7 3 6
    7 1 5 3 2 4
    5 2 1 6 4 3

    והשני

    4 6 5 7 1 3
    6 5 1 2 7 4
    5 1 7 3 2 6
    7 2 3 6 4 1
    1 7 2 4 3 5
    3 4 6 1 5 2

    (בשתי הטבלאות הטור הימני ביותר הוא הכפולות של 2, והשמאלי ביותר הכפולות של 7, והשורה העליונה היא הכפולות של 2, והתחתונה – הכפולות של 7).

    אני תוהה איך זה יכול להיות.

  6. זה רק אני, או שלוחות הכפל שלך לא סימטריים, ולכן הכפל לא קומוטטיבי?

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

  7. לוחות הכפל דווקא סימטריים, הם פשוט רשומים מימין לשמאל במקום משמאל לימין.
    2*2=4, 2*3=3*2=6, 3*3=5, וכן הלאה.
    כל האיברים (חוץ מ-1 ו-0) הם איברים פרימיטיביים, בשני השדות.

  8. אדרבא, אם כולם יוצרים אז מציאת איזומורפיזם היא עוד יותר קלה.

    בוא ניקח את 2 בתור יוצר לשדה הראשון. אז החזקות שלו לפי הסדר הן:

    2,4,3,6,7,5,1

    בוא ניקח את 2 שוב בתור יוצר לשדה השני. אז החזקות שלו לפי הסדר הן:
    2,4,5,7,3,6,1

    אז בוא נגדיר את האיזומורפיזם הבא:
    0 < --> 0
    1 < --> 1
    2 < --> 2
    3 < --> 5
    4 < --> 4
    5 < --> 6
    6 < --> 7
    7 < --> 3

    צד ימין הוא השדה הראשון, צד שמאל הוא השדה השני.

    עובד?

  9. לא עובד. האיזומורפיזם הזה שומר על הכפל, אבל לא שומר על החיבור, כי בשני השדות 2+4=6, אבל 2 ו-4 עוברים לעצמם, ו-6 עובר ל-7.

  10. מצאתי את האיזומורפיזם הנכון: 23, 45, והיתר עוברים לעצמם. תודה על העזרה.
    (הטריק שלך עובד אם בוחרים את 6 או 7 בתור יוצר, אבל לא עובד עם יוצרים אחרים).

  11. יש, השאלה אם הוא עובד גם במקרים אחרים.
    הבעיה עם השיטה שלך היא שהיא מתייחסת רק לכפל. אם נסתכל על הפעולה של "חיבור עם ההופכי הכפלי" (שנותנת עבור כל איבר את הסכום שלו ושל ההופכי הכפלי שלו) נקבל, עבור החבורה הראשונה:
    2 — > 7, 3 — > 5, 4 — > 3, 5 — > 7, 6 — > 5, 7 — > 3.
    ועבור החבורה השניה:
    2 — > 4, 3 — > 7, 4 — > 7, 5 — > 2, 6 — > 4, 7 — > 2.
    כלומר, בחבורה הראשונה רק 3,5,7 יכולים להתקבל, ובשניה רק 2,4,7. לכן המספרים האלה חייבים לעבור אלה לאלה, ולפי הסדר הזה. זה נותן לנו 3 אפשרויות לאיזומורפיזם, וכל 3 האפשרויות עובדות.
    אחת מהן היא האיזומורפיזם שמצאתי, אבל יש 2 נוספים שבהם אף איבר לא עובר לעצמו.

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

  13. כתוב: "אז המציין שלו הוא p עבור ראשוני כלשהי"
    צ"ל: "אז המציין שלו הוא p עבור ראשוני כלשהו"

  14. כתוב: בשדה הזו נמצאים כל השורשים של הפולינום
    צ"ל: בשדה הזה נמצאים כל השורשים של הפולינום

  15. בתשובה לשאלת האלגוריתם למציאת איזומורפיזם:
    אם יש לך דרך למצוא פולינום אי-פריק מדרגה k, אפשר למצוא איזומורפיזם ב-zzz O(k*p^k) zzz. משתמשים במשפט שאומר שאם a,b שורשים של אותו פולינום אי-פריק, אז יש איזומורפיזם בין zzz F(a), F(b) zzz שמקשר בין a ו-b.

    אז ברגע שאיכשהו יש לנו פולינום כזה:
    1) רצים על כל האיברים של כל שדה, ומחפשים בכל אחד מהם איבר שמאפס את הפולינום (בהכרח קיים – ולמעשה קיימים k שורשים, אז אם סדר האיברים היה אקראי הסיבוכיות הממוצעת קצת יותר טובה).
    2) החזקות הקטנות מ-k של השורשים שמצאנו הם בסיס לשדה כמרחב וקטורי מעל Fp. פשוט רצים לקסיקוגרפית על הצירופים הלינאריים שלהם, ומתאימים כל צירוף לינארי של החזקות של השורש שמצאנו בשדה הראשון לצירוף הלינארי עם אותם מקדמים של השורש שמצאנו בשדה השני.

    עם שיפוצים של הרעיון הזה אפשר גם למצוא יוצר לחבורת האוטומורפיזמים של שדה

    שיהיה לי בהצלחה במבחן

  16. תיקון: אם אני לא טועה, ברגע שיש לך את השורשים האלה הם גם יוצרים כפלים – אז אפשר גם להתאים לפי סדר החזקות עד חזקת p^k

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *