אלגברה מופשטת על כוס קפה/שדות

הגדרות של שדות

דוגמות לשדות

• $\mathbb{Q}$תבנית:כ (שדה המספרים הרציונליים)
• $ℝ$תבנית:כ (שדה המספרים הממשיים)
• $ℂ$תבנית:כ (שדה המספרים המרוכבים (קומפלקסיים))
• ${\mathbb{Q}}_p$תבנית:כ (מספר p-אדיתבנית:הערה).

מספר האיברים בשדה סופי

מספר האיברים בשדה מכונה גם: "סדר השדה" או "דרגת השדה", ומסומן: $ord\left(\right)$ .

מאפיין של שדה

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

אלגוריתם:

• אם מצאנו איבר חדש בשדה, השונה מכל אלו שקדמו לו בשדה - נוסיף $1$ למאפיין השדה.
• אם האיבר החדש בשדה זהה לאחד או יותר מהאיברים אשר מצאנו קודם לכן בשדה - לא נוסיף $1$, ונתקדם לאיבר הבא בשדה.

מספר האיברים השונים זה מזה בשדה- מכונה "מאפיין השדה".

מאפיין של שדה סופי

• דוגמה:

נתונה לנו קבוצה סופית כלשהי, בעלת מספר איברים $n$ , אשר מהווה שדה. שדה זה הנו סופי מפני ש $n$ סופי:

$F_n=\{0,1,\cdots (n-1)\}$ .

שני המספרים הראשונים, השייכים לשדה, יהיו: $0\in F$ ו- $1\in F$ .תבנית:ש

בהנחה ש $F$ הוא שדה סופי כלשהו, נתחיל כעת לספור את מספר האיברים בשדה, בהנחה שכולם שונים זה מזה:תבנית:ש נתחיל מהאיבר: $0\in F$, ונוסיף לו את האיבר: $1\in F$ באופן החוזר על עצמו (רפטטיבי):

• נקבל את סדרת האיברים (מספרים) הבאה:

$\underset{\text{All the elements of the string are distinct from each other}}{\underbrace{(\underset{\text{1st element}}{\underbrace{0}}\text{, }\underset{\text{2nd element}}{\underbrace{1}}\text{, }\underset{\text{3rd element}}{\underbrace{1+1}}\text{, }\underset{\text{4th element}}{\underbrace{1+1+1}}\text{ , }\underset{\text{5th element}}{\underbrace{1+1+1+1}}\text{ , }\cdots \text{,}\underset{\text{n element}}{\underbrace{n-1}})}}$

• שני האיברים הראשונים בשדה שונים זה מזה, בגלל קיום האקסיומה: $0\ne 1$ עבור שדות.
• מכיוון שהשדה הנו סופי, השדה חייב להיות גם מחזורי (רפטטיבי), עבור שדות המקיימים: $n>1$ (כלומר, החל מהשדה הזה, בעל מספר האיברים המינימלי: $\{0,1\}$), או שדה בעל מספר איברים רב יותר. על כן, כאשר נגיע לאיבר האחרון, האיבר הבא אחריו יהיה בפשטות $0\in F$ , וספירת מאפיין השדה תחזור על עצמה (מחדש).תבנית:שתבנית:ש

• דוגמה:תבנית:שתבנית:שנתבונן פעם נוספת בשדה:תבנית:שתבנית:ש$F_n=\{0,1,\cdots (n-1)\}$ .תבנית:שתבנית:ש$n$ האיברים הראשונים בשדה שונים זה מזה, אך אם נתקדם לאיבר הבא- איבר זה יהיה $0\in F$ , והוא שונה מהאיבר האחרון של הסדרה (תזכורת: כל אברי הסדרה שונים זה מזה).תבנית:שעל כן, באופן מתמטי, מאפיין השדה יהיה: $CharF=(n-1)+1=n=0$ .

• דוגמאות מעשיות:

דוגמה מספר 1:

מהו מאפיין השדה: $F_2=\{0,1\}$ ? תבנית:כ ($2$ מציין את מספר האיברים בשדה (הסופי)).

• בתחילה, מאפיין השדה, $CharF=0$ .

• נתחיל לספור:

האם $0\ne 0$ ? תבנית:כ לא. על כן, לא נוסיף $1$ למאפיין השדה, ועדיין מתקיים: $CharF=0$ .תבנית:ש נתקדם לאיבר הבא, $1$ . האם $1\ne 0$ ? כן. על כן, כעת: $CharF=1$ .תבנית:ש נתקדם לאיבר הבא, שהוא שוב $0$ (השדה רפטטיבי, חוזר על עצמו). האם $0\ne 1$ ? כן, על כן: $CharF=2$ .

השלמנו מחזור שלם של השדה, וקיבלנו שעבור האיבר הראשון בו: $0\in F$ , מאפיין השדה הנו: $CharF=2$ .תבנית:ש על כן, נכתוב: $2=0$ .

$\underset{\text{Number of distinct elements}}{\underbrace{2}}=\underset{\text{Until we get back to the first element again}}{\underbrace{0}}$

דוגמה מספר 2:

הכללה לדוגמאות 1 ו-2:

• משפטתבנית:הערה:

יהי $F$ שדה סופי. על כן, מאפיין השדה אינו אפס.

קבוצות סופיות שאינן שדות (קריטריון הכרחי (אך כנראה אינו מספיק) לכך, שקבוצה מסוימת הנה שדה)

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

$\mathbb{Z}/10\mathbb{Z}=\left\{\begin{array}{c}0\text{, }1\text{, }\cdots ,9\end{array}\right\}$

הסבר:

בצירוף הבא: $\mathbb{Z}/10\mathbb{Z}$ :

• $\mathbb{Z}$ מציין את שדה המספרים השלמים.

• $10\mathbb{Z}$ מציין את הבסיס ("מודולו") של הקבוצה אותה בחרנו.

בדוגמה זו, הבסיס הנו $10$, על כן המספרים הנמצאים בה יהיו $0-9$.

הסבר מדוע קבוצה זו אינה מהווה שדה:

בכל שדה חייב להתקיים התנאי הבא:

• $\left(1\right)$ $a\cdot b=0$ , כאשר מתנאי זה נובע, כי חייב להתקיים בהכרח: או $a=0$ , או $b=0$ .

על פי תנאי זה, אחד האיברים חייב להיות המספר $0$, על פי התנאי לעיל.

אם תנאי זה מתקיים, הרי שזהו שדה; אם לא, הרי שזהו איננו שדה.

• ממבט ראשון, ניתן לקבוע כי קבוצה זו היא אכן שדה, שהרי מתקיים:

$(9\cdot 0=0)$ , $\cdots$ , $(2\cdot 0=0)$ , $(1\cdot 0=0)$ .

אבל, יש כאן נקודה עדינה יותר:

• $\left(2\right)$ אם נמצא בקבוצה מסוימת $a\text{mod}10\ne 0$ ו- $b\text{mod}10\ne 0$, המקיימים אף הם את התנאי: $a\cdot b=0$ , הרי שהקבוצה שבחרנו איננה שדה.

• נביט בקבוצה. האם כל מספר בקבוצה, בטווח של: $1\le a\le 9$ , ($a$ מספר כלשהו בקבוצה, בין $1$ ו-$9$), ו- $b=0$ $$ [או להפך: $1\le b\le 9$ , ($b$ מספר כלשהו בקבוצה, בין $1$ ו-$9$), ו- $a=0$] $$ מקיים $a\cdot b=0$ ? התשובה היא כן.

אבל: האם אנו יכולים למצוא בקבוצה צמד מספרים, ששניהם אינם אפס, אך מכפלתם תניב מספר, שאם נחלק אותו ב- $10$, השארית תהיה שווה בכל זאת לאפס?תבנית:שהתשובה היא כן.

• למשל: $5\cdot 2=10$ , ו- $10\text{ mod }10=0$.

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

• דוגמה זו מאפשרת לבצע הכללה: אם $a\cdot b=0$ , אבל מתקיים גם: $a\text{mod}\text{ base }\ne 0$ וגם $b\text{mod}\text{ base }\ne 0$ - הרי שזהו איננו שדה.

נשאלת השאלה, מה יגרום ל: $(a\cdot b)\text{ mod }\text{base}\ne 0$ ? או, במילים אחרות, מתי $a\cdot b\ne \text{base}$ ?

• באופן כללי, עבור כל בסיס (ולמעשה עבור כל מספר), מתקיים: $\text{base}\text{ mod }\text{base}=0$ .

• ידוע כי: אם $a\text{mod}\text{ base }\ne 0$ וגם $b\text{mod}\text{ base }\ne 0$ , הרי ש: $(a\cdot b)\text{mod}\text{ base }\ne 0$ . הדבר הזה מתרחש אך ורק כאשר הבסיס הנו מספר ראשוני.

הסיבה לכך: $a$ וגם $b$ לעולם לא יתחלקו בבסיס הראשוני- ללא שארית. לכן גם: $a\cdot b$ לא יתחלק לעולם בבסיס הראשוני- ללא שארית.

מסקנה

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

גישה אינטואיטיבית, לצורך הבנת המסקנה

נסמן את הבסיס הראשוני באות $p$ , רמז למילה: "Primary".

• באופן כללי, השדה ייכתב כך: $\mathbb{Z}/p\mathbb{Z}=\left\{\begin{array}{c}0\text{, }1\text{, }\cdots ,\text{(p-1)}\end{array}\right\}$ .

• דוגמה לשדה כזה:

נבחר $p=7$, כאשר ידוע כי $7$ הנו מספר ראשוני.

השדה ייראה כך: $\mathbb{Z}/7\mathbb{Z}=\left\{\begin{array}{c}0\text{ , }1\text{ , }2\text{ , }3\text{ , }4\text{ , }5\text{ , }6\end{array}\right\}$

כעת, נבדוק שני תנאים:

• האם כל $1\le a\le 6$ , המוכפל ב- $b=0$ - תוצאתו היא $a\cdot b=0$ ? התשובה היא כן.
• האם ישנו מספר כלשהו $a$ בקבוצה, המתחלק ב- $p=base=7$ ללא שארית? התשובה היא לא.תבנית:ש

אם אף מספר אינו מקיים דרישה כזו, הרי שמכפלה של שני מספרים כלשהם בקבוצה- אף היא אינה מתחלקת ב- $p=base=7$ ללא שארית!

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

• השדה $\mathbb{Z}/p\mathbb{Z}$ מכונה: ${𝔽}_p$ .

הוכחה מתמטית פורמלית של המשפט: סדר השדה הוא מספר ראשוני (מקרה מספר 1)

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

זוהי ההוכחה, שעליי להבין ולהסביר: (כתיבה ואחר כך הבנה, בשיטת "נעשה ונשמע")

עבור כל חוג קומוטטיבי $R$ , קיים הומומורפיזם חוגי (הומומורפיזם של חוג) ייחודי: $Z\to R$ , המתואר על ידי:

$m\mapsto \{\begin{array}{cc}\underset{\text{m times}}{\underbrace{1+1+\cdots +1}}& \text{if }m\ge 0\\ \\ \underset{\text{(absolute value of m) times}}{\underbrace{-(1+1+\cdots +1)}}& \text{if }m<0\end{array}$

ניישם הומומורפיזם חוגי זה למקרה: $R=F$ , כאשר $F$ הנו שדה סופי.

הגרעין תבנית:אנ של $Z\to F$ איננו אפס, מאחר ש: $Z$ הנו אינסופי, בעוד ש $F$ הנו סופי.

נכתוב את הגרעין כ: $\left(m\right)=mZ$ עבור מספר שלם $m>0$ ,

כך ש: $Z/\left(m\right)$ מהווה שיכון. שיכון זה הנו (או: המשמש כ) תת חוג של $F$ (או: מהווה שיכון לתת חוג של $F$) (באנגלית: Z/(m) embeds as a subring of F).

ידוע כי: כל תת חוג של שדה הנו שיכון (domain).

מכאן נובע, כי $m$ חייב להיות, בהכרח, מספר ראשוני.

נקרא למספר הראשוני הזה, שרירותית, בשם: $m=p$ .

מכאן נובע, כי קיים שיכון $Z/\left(p\right)\hookrightarrow F$ תבנית:אנ.

אם נסתכל על $F$ כמרחב וקטורי מעל $Z/\left(p\right)$ ,

אזי מרחב זה הנו בעל ממד סופי, מאחר ש: $F$ הנו שדה סופי.

יהי $n=di{m}_{z/\left(p\right)}\left(F\right)$ .

נבחר בסיס שרירותי: $\{e_1,\cdots ,e_n\}$ עבור השדה $F$ , מעל $Z/\left(p\right)$ ,

איברי $F$ יכולים להיכתב באופן ייחודי כ:

$c_1\cdot e_1+\cdots +c_n\cdot e_n\text{ ,}{c}_i\in Z/\left(p\right)$

לכל מקדם $C_i$ קיימות $p$ בחירות/אופציות (choices),

על כן: $\left|F\right|=p^n$ .

מ.ש.ל.

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

הוכחת המשפט, שסדר של שדה עשוי להיות חזקה של מספר ראשוני (מקרה מספר 2)

• משפטתבנית:הערה: נניח $p$ מספר ראשוני, $m$ הוא מספר שלם (טבעי?תבנית:הבהרה) חיובי, ו- $q=p^m$ . אז קיים (עד איזומורפיזם) שדה אחד בדיוק, ${𝔽}_q={𝔽}_{p^m}=GF(p^m)$, בו קיימים $p^m$ איברים.

בניית שדות סופיים

• האם סדר השדה שווה בהכרח למאפיין השדה?תבנית:הבהרה

בניית שדות סופיים באמצעות פולינומים

משפט (מקרה פרטי של המשפט בפסקה הקודמת. מקרה פרטי זה מתייחס לפולינומים, בפרט עבור פולינומים אי פריקים מתוקנים)תבנית:מקור:

• סדר של שדה סופי $F$ , הוא $p^m$ (מכיל $p^m$ איברים), כאשר $m$ היא החזקה הגבוהה ביותר בפולינום אי פריק מתוקן, אשר מהווה איבר בתוך שדה סופי זה. (ראה דוגמאות בסעיף הבא).

הוכחה:

${\displaystyle }$

פולינומים אי פריקים, פולינומים מתוקנים ופולינומים פרימיטיביים- דוגמאות לשם המחשה

• משפטתבנית:הערה:

עבור מספר ראשוני $p$, ופולינום אי פריק מתוקן $\pi \left(x\right)$, הנמצא בתוך שדה סופי (או: השייך לשדה) שנסמנו: $F_p[x]$, בעל דרגה (או סדר) $n$ - מהווה החוג: $F_p[x]/\left(\pi \left(x\right)\right)$ שדה בעל דרגה (או סדר) $p^n$ .

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

דוגמה ראשונה:

שני שדות מסדר $8$ הם:

• $\underset{\text{p=2}}{\underbrace{F_2\left[x\right]}}/\underset{\text{n=ord(polynomial)=3}}{\underbrace{(x^3+x+1)}}$ ,תבנית:שתבנית:ש
• $\underset{\text{p=2}}{\underbrace{F_2\left[x\right]}}/\underset{\text{n=ord(polynomial)=3}}{\underbrace{(x^3+x^2+1)}}$ .תבנית:שתבנית:ש
• הסיבה לכך שסדר השדות הנו $8$ היא:תבנית:ש$p=2\text{ , }n=3\Rightarrow ord\left(F\right)=p^n=2^3=8$ .

דוגמה שנייה:

שני שדות מסדר $9$ הם:

• $\underset{\text{p=3}}{\underbrace{F_3\left[x\right]}}/\underset{\text{n=ord(polynomial)=2}}{\underbrace{(x^2+1)}}$ ,תבנית:שתבנית:ש
• $\underset{\text{p=3}}{\underbrace{F_3\left[x\right]}}/\underset{\text{n=ord(polynomial)=2}}{\underbrace{(x^2+x+2)}}$ .תבנית:שתבנית:ש
• הסיבה לכך שסדר השדות הנו $9$ היא:תבנית:ש$p=3\text{ , }n=2\Rightarrow ord\left(F\right)=p^n=3^2=9$ .

דוגמה שלישית:

הפולינום: $x^3-2$ הוא אי פריק ב- $F_7\left[x\right]$ , על כן $F_7\left[x\right]/(x^3-2)$ הוא שדה בעל סדר: $7^3=343$ .

הערות:

1. מבנים אלו הם שדות, למרות שהסדר שלהם איננו ראשוני. המבנים נוצרים בדרך שונה מהדרך המקובלת, הגורסת שאם סדר של קבוצה כלשהי איננו ראשוני- זהו אינו שדה, כפי שנכתב לעיל.
2. דוגמאות אלו יכולות להוות תרגילים:
   • בשתי הדוגמאות הראשונות אנו מקבלים את סדר השדה, ואנו צריכים למצוא את הפולינומים האי פריקים המתוקנים שלהם.
   • הדוגמה השלישית הפוכה לשתי הדוגמאות הראשונות: אנו מקבלים פולינום אי פריק מתוקן, ואנו צריכים למצוא את סדר השדה.תבנית:שתבנית:ש

• כיצד נמצא פולינומים כאלו, אשר יבנו לנו את השדות הסופיים הרצויים לנו?תבנית:ש

לשם כך, עלינו להבין שלושה מושגים:תבנית:ש

• פולינומים אי פריקים.
• פולינומים מתוקנים.
• פולינומים פרימיטיביים.

פולינומים אי פריקים, פולינומים מתוקנים ופולינומים פרימיטיביים- הסברים

פולינומים מעל שדה גלואה.

פולינומים אי פריקים- הסבר

תבנית:הערה.

פולינום מוגדר כאי פריק, אם הוא לא יכול להיות מפושט לפולינומים לא טריוויאליים- מעל אותו השדה.

• דוגמה:

בשדה הפולינומים הרציונליים $\mathbb{Q}\left[x\right]$ (כלומר, פולינומים $f\left(x\right)$ , בעלי מקדמים רציונליים (בכל איבריהם? או רק חלק?תבנית:הבהרה)), נאמר שהפולינום $f\left(x\right)$ הנו אי פריק, אם לא קיימים שני פולינומים, שאינם קבועים, $g\left(x\right)$ ו- $h\left(x\right)$ ב- $x$ , שהם בעלי מקדמים רציונליים, כך שמתקיים: $f\left(x\right)=g\left(x\right)\cdot h\left(x\right)$ תבנית:הערה.

במילים פשוטות, פולינום אי פריק הנו פולינום, שלא ניתן לכתבו כמכפלה של שני פולינומים (לאו דווקא שונים, למרות שניסוח המשפט אכן מעיד, כביכול, על שני פולינומים שונים: $g\left(x\right)$ ו- $h\left(x\right)$ .תבנית:שבמילים אחרות, פולינום הנו אי פריק, אם הוא לא "מתפרק" למכפלה של שני פולינומים (זהים זה לזה או שונים זה מזה).

• דוגמה מוחשית, הכוללת את משוואת "החלום של פרשמן", המוסברת בפסקה זו:

לשדה הסופי $GF\left(2\right)$ , שייכים (בין היתר, קיימים בו פולינומים נוספים מעבר למוצג בדוגמה) הפולינומים הבאים:תבנית:שתבנית:ש

• $x^2+x+1$ : זהו פולינום אי פריק מעל שדה זה, כיוון שלא ניתן לכתבו כמכפלה של שני פולינומים. מדוע?תבנית:הבהרהתבנית:שתבנית:ש
• $x^2+1$ : זהו פולינום פריק מעל שדה זה, כיוון שמתקיימת בו משוואת "החלום של פרשמן":תבנית:שתבנית:ש$x^2+x+1\underset{\text{Freshman's Dream equation}}{\underbrace{\equiv }}{x}^2+1\left(mod\text{ 2}\right)$ .

מספר הפולינומים האי פריקים בשדה

באופן כללי, מספר הפולינומים האי פריקים, בעלי סדר $n$ (כלומר, שהחזקה הגבוהה ביותר בפולינום הנה $n$), מעל שדה $GF\left(q\right)$ , נתונה על ידי הנוסחה הבאהתבנית:הערה:

Necklace Polynomial (פולינום השרשרת?תבנית:הבהרה)

$L_q\left(n\right)=\frac{1}{n}\sum _{d|n}\mu \left(\frac{n}{d}\right)\cdot q^d$ ,

כאשר $\mu \left(n\right)$ היא פונקציית מוביוס.

מספר הפולינומים האי פריקים מסדר $n$ , מעל השדה הסופי: $GF\left(2\right)$ , שווה ל:

• מספר השרשראות תבנית:הערה הא-פריודיות המקובעות (האם זהו התרגום הנכון ל- fixed aperiodic necklaces ?תבנית:הבהרה), בעלות $n$ חרוזים (האם זהו התרגום הנכון למילה bead ?תבנית:הבהרה), בשני צבעים שונים.

• מספר מילות לינדון תבנית:אנ בינאריות, בעלות אורך $n$ .

הטבלה הבאה מציגה את הפולינומים האי פריקים ($mod\text{ 2}$) , החל מסדר $n=1$ ועד $n=5$ :תבנית:הערה.

הפולינומים האי פריקים מסדר $n$ מעל השדה הסופי: $GF\left(2\right)$ (עד סדר חמישי)

$n$	פולינומים אי פריקים	מספר הפולינומים האי פריקים עבור סדר זה
$1$	$x$תבנית:ש $1+x$	$2$
$2$	$1+x+x^2$	$1$
$3$	$1+x+x^3$תבנית:ש $1+x^2+x^3$	$2$
$4$	$1+x+x^4$תבנית:ש $1+x+x^2+x^3+x^4$תבנית:ש $1+x^3+x^4$	$3$
$5$	$1+x^2+x^5$תבנית:ש $1+x+x^2+x^3+x^5$תבנית:ש $1+x^3+x^5$תבנית:ש $1+x+x^3+x^4+x^5$תבנית:ש $1+x^2+x^3+x^4+x^5$תבנית:ש $1+x+x^2+x^4+x^5$	$6$

סדרי הפולינומים האפשריים של פולינומים אי פריקים ממעלה $n$ , מעל השדה: $GF\left(2\right)$ רשומים להלן, בסדר עולה:

וולפרם מתמטיקה ->

סדר הפולינומים- משולש להבין ולהסביר את המשולש הזהתבנית:הבהרה -> אותו הדבר, רק בטור (חד ממד ולא דו ממד).

מקור נוסף.

${\displaystyle }$

פולינומים פרימיטיביים- הסבר

פולינומים מעל שדה גלואה.

• פולינומים פרימיטיביים ושדות גלואה בעלי סדר $p^m$