פיתרון בעית התחלקות המערבת מספרי פיבונאצ'י

מבוא

באולימפיאדת גיליס ה-48 (תחרות מתמטיקה לנוער), שהתקיימה ב-28.12.14, הופיעה השאלה הבאה:

סדרת פיבונאצ'י מוגדרת באמצעות ערכי ההתחלה F_0=0, F_1=1 ונוסחת הנסיגה F_n = F_{n-1} + F_{n-2}. יהא p מספר ראשוני אי-זוגי.
א. הוכיחו כי F_{p-1} + F_{p+1} - 1 מתחלק ב-p.
ב. הוכיחו כי לכל n חיובי שלם, F_{p^{n+1}-1}+F_{p^{n+1}+1}-(F_{p^{n}-1}+F_{p^{n}+1}) מתחלק ב-p^{n+1}.

זו הייתה השאלה השביעית והאחרונה. נוכיח אותה כאן בשני אופנים:

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

כמו כן, נציג הכללות שונות ומשונות.

פילוסופיה

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

  • סעיף א' נובע ישירות מהפעלת סעיף ב' עבור n=0, כי F_0 + F_2 = 1. לכן נוכיח פשוט את סעיף ב' לכל n שלם אי-שלילי.
  • כמו כן, אין סיבה להגביל את p להיות אי-זוגי – מבחינתנו מותר ל-p להיות שווה 2.

נסמן L_{n}=F_{n-1}+F_{n+1}. אפשר לנסח את השאלה באופן הבא:

\forall n \ge 0 : p^{n+1} | L_{p^{n+1} } - L_{p^n}

עבור כל מספר טבעי a נגדיר את הסדרה A_n = a^n. עבור סדרה זו מתקיימת טענה אנלוגית:

\forall n \ge 0 : p^{n+1} | a^{p^{n+1} } - a^{p^n}

עבור n=0 זהו המשפט הקטן של פרמה, ועבור n כללי זו מסקנה ישירה ממשפט אוילר (a^{\phi(p^{n+1})} \equiv 1 \mod {p^{n+1}} אם p \nmid a, כאשר \phi(p^{n+1}) = p^{n+1} - p^{n} היא פונקציית אוילר).
מסתבר ש-A_n, L_n חולקות תכונות קומבינטוריות ואלגבריות – נראה זאת במהלך הפוסט. הפילוסופיה של הפוסט תהיה:

פילוסופיה: כל הוכחה של הטענה \forall n\ge 0: p^{n+1} \mid a^{p^{n+1}} - a^{p^n} ניתנת להסבה להוכחה של הטענה המקבילה \forall n \ge 0 : p^{n+1} | L_{p^{n+1} } - L_{p^n}

הוכחה קומבינטורית – פיצות פיבונאצ'י

הוכחה עבור A_n = a^n

נסתכל על פיצות עם d משולשים, כאשר כל משולש יכול לקבל בדיוק אחת מבין a תוספות. כמה פיצות כאלו יש?

התשובה היא a^d = A_d, בהנחה שאנחנו חושבים על המשולשים של הפיצה כממוספרים מ-1 עד d. לדוגמא, אם d=3, אנחנו מבדילים בין הפיצה "זיתים, אננס, עגבניות" ו-"אננס, עגבניות, זיתים".

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

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

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

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

  • "בטטה, תירס, בטטה, תירס, בטטה, תירס, בטטה, תירס" בעלת מחזור 2
  • "אננס, עגבניות, זיתים" בעלת מחזור 3

ננסה לספור פיצות לא מחזוריות עם d=p^{n+1} משולשים. נספור אותן באמצעות לספור את כל הפיצות עם כזה מספר משולשים (A_{p^{n+1}}) ולחסר את כל הפיצות המחזוריות עם כזה מספר משולשים.

לפיצה עם d משולשים יכולים להיות רק מחזורים שמחלקים את d. אם המחזור הוא d בדיוק אז היא לא מחזורית, אחרת היא כן.
במקרה d=p^{n+1} קורה משהו נחמד: או שהפיצה לא מחזורית, או שהמחזור מחלק את p^n. לכן צריך לספור פיצות עם מחזור המחלק את p^n.

איך נעשה זאת? נשים לב שלכל פיצה מחזורית עם p^{n+1} משולשים אפשר להתאים פיצה עם p^n משולשים, ע"י לקחת את הפיצה שהמשולשים שלה הם ה-p^n משולשים הראשונים של הפיצה המקורית. לדוגמא, במקרה p=2,n=2 ,נתאים ל-"בטטה, תירס, בטטה, תירס, בטטה, תירס, בטטה, תירס" את "בטטה, תירס, בטטה, תירס".
התאמה זו היא חח"ע ועל (מהאבחנה הקודמת לגבי מחזורים – אתן לכם להשלים את הפרטים), ולכן כמות הפיצות המחזוריות יוצאת A_{p^n} = a^{p^n}.

קיבלנו:

כמות הפיצות הלא מחזוריות עם p^{n+1} משולשים היא A_{p^{n+1}}-A_{p^n} = a^{p^{n+1}} - a^{p^n}

טענה: כמות זו מתחלקת ב-p^{n+1}. הוכחה: כל פיצה לא מחזורית עם d משולשים אפשר לסובב ב-d דרכים ולקבל כך פיצה שונה. זה המקרה d=p^{n+1}. \blacksquare

מסקנה: המשפט הקטן של פרמה. הוכחה: נבחר n=0.

פירוש קומבינטורי של מספרי פיבונאצ'י

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

נסתכל על מחרוזות באורך n של אפסים ואחדות, כך שאסור שיהיו 2 אפסים רצופים (010 – חוקי, 001 – לא חוקי). נקרא למחרוזות כאלה "חוקיות".

טענה: יש סה"כ F_{n+2} מחרוזות חוקיות באורך n.
הוכחה: יש בדיוק שתי אפשרויות: או שמחרוזת כזו מתחילה ב-1 וממשיכה במחרוזת חוקית הקצרה בתו אחד, או שהיא מתחילה ב-01 ואז מחרוזת חוקית הקצרה בשניים. לכן מספר המחרוזות מקיים את נוסחת הנסיגה של פיבונאצ'י. תנאי ההתחלה שונים: יש 2 מחרוזות מאורך 1 (0, 1), ו-3 מאורך 2 (11, 01, 10), ולכן זו סדרת פיבונאצ'י בהזזה. \blacksquare.

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

  1. מחרוזות שמתחילות ב-1 ומסתיימות ב-1
  2. מחרוזות שמתחילות ב-0 ומסתיימות ב-0
  3. מחרוזות שמתחילות ב-0 ומסתיימות ב-1
  4. מחרוזות שמתחילות ב-1 ומסתיימות ב-0

אפשר לראות ש:

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

L_{n-1} = F_{n}+F_{n-2} סופר את המחרוזות החוקיות באורך n שמתחילות ומסתיימות באותו התו. נתנו הרגע פירוש קומבינטורי לסדרה שהופיעה בשאלה!

הערה: במקום 0 ו-1 יכולנו באותה מידה לכתוב "בצל" ו"פטריות". בסעיף הבא נעשה זאת:

פיצות פיבונאצ'י

איך זה מתקשר אלינו? אני רוצה לספור עכשיו פיצות עם n משולשים ועם 2 תוספות: בצל ופטריות. כמה כאלו יש? 2^n, נכון. אבל מה קורה אם אני מוסיף את האילוץ הבא: "אסור 2 משולשים של בצל אחד אחרי השני"?

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

נקרא לפיצות כאלה "פיצות פיבונאצ'י".

טענה: כמות הפיצות הזו היא בדיוק הסדרה L_n.
הוכחה: אפשר לחשוב על פיצה עם n משולשים בתור סדרה באורך n+1 של תוספות, כאשר התוספת ה-n+1-ית היא התוספת הראשונה.
באופן כזה אני מתרגם את הדרישה "אין בצלים עוקבים" על פיצה מעגלית באורך n לדרישה "אין בצלים עוקבים" על סדרה באורך n+1.
שימו לב שהיינו חייבים להאריך את הסדרה ב-1: אחרת, הפיצה המעגלית עם 3 משולשים "בצל, פטריות, בצל" הייתה נחשבת פיצה חוקית (כי בסדרה "בצל, פטריות, בצל" אין 2 בצלים עוקבים, למרות שפיצה היא מעגל ואחרי הבצל במשולש השלישי מגיע הבצל במשולש הראשון). חייבים לקודד אותה בתור הסדרה באורך 4 "בצל, פטריות, בצל, בצל".
על השאלה הזו (כמה סדרות עם 2 ערכים כך שערך מסוים לא מופיע פעמיים רצוף יש?) ענינו בסעיף הקודם, רק שבמקום הערכים בצל ופטריות השתמשנו ב-0 ו-1.  \blacksquare

הסיום האלגנטי

הבנו ש-L_n סופרת פיצות עם n משולשים ו-2 תוספות: בצל ופטריות, כך שאין 2 משולשים עוקבים עם בצל. עכשיו נתעניין, כמו שהתעניינו קודם, בפיצות פיבונאצ'י שאינן מחזוריות.

טענה: L_{p^{n+1}} - L_{p^n} סופר את כמות פיצות פיבונאצ'י הלא מחזוריות עם p^{n+1} משולשים.

הוכחה: ראינו שהמחובר הראשון סופר את כמות פיצות פיבונאצ'י עם p^{n+1} משולשים.
פיצה כזו היא מחזורית אמ"מ המחזור שלה מחלק את p^{n}. לכן נותר להסביר למה הביטוי שחיסרנו, L_{p^n}, סופר פיצות פיבונאצ'י עם p^{n+1} ומחזור המחלק את p^{n}. ההסבר הוא זה:
יש התאמה חח"ע ועל בין פיצות עם מחזור המחלק את p^{n} לבין פיצות עם p^n משולשים – ההתאמה היא להצטמצם לפיצה שנוצרת מ-p^n המשולשים של הפיצה המקורית. היא חח"ע בגלל המחזור, וההעתקה היא על כי אם אני לוקח איזושהי פיצת פיבונאצ'י עם p^n משולשים ויוצר ממנה פיצה עם פי p משולשים (ע"י חזרה) – מקבלים פיצה חוקית (רק בקצוות יש סיכון לבצל שאחריו יגיע בצל, אבל זה לא יתכן כי הפיצה המקורית היא מסוג פיבונאצ'י). \blacksquare

מסקנה: L_{p^{n+1}} - L_{p^n} מתחלק ב-p^{n+1}.
הוכחה: לכל פיצת פיבונאצ'י לא מחזורית עם d משולשים יש d סיבובים שנותנים פיצת פיבונאצ'י שונה. זה המקרה d=p^{n+1}. \blacksquare

כדי להדגים, נייצג את התוספות עם 0 (בצל) ו-1 (פטריות). אם p=3,n=1, נקבל שמספר פיצות הפיבונאצ'י עם 3^{1+1}=9 משולשים הוא F_8 + F_{10} = 21+55=76.

מתוכן, פיצות פיבונאצ'י מחזוריות יש F_{2}+F_{4}=1+3=4. אלו הן הפיצות 111111111 (שמתאימה לפיצה 111 עם 3 משולשים) ו-101101101,011011011,110110110 (שמתאימות לפיצות 101,011,110 עם 3 משולשים).
ההפרש 76-4=72 מתחלק ב-3^2=9. זה קורה בגלל שלכל פיצה שספרנו יש 9 סיבובים שונים, לדוגמא:

111111110, 111111101, 111111011, 111110111, 111101111, 111011111, 110111111, 101111111, 011111111

הוכחה אלגברית – פונקציות סימטריות ופונקציות p-מכווצות

הוכחה עבור A_n = a^n

יהי p ראשוני. נסתכל על הפונקציה f(x) = x^p מהמספרים השלמים לעצמם. יש לה 2 תכונות "קסם":

  • f(x) \equiv x \mod p – שקול למשפט הקטן של פרמה
  • אם x \equiv y \mod p^k (כאשר k>0) אז f(x) \equiv f(y) \mod p^{k+1} – נובע מכך ש-f(x)-f(y) = (x-y) \cdot \frac{f(x)-f(y)}{x-y} ושהמנה שמופיע מתחלקת ב-p:

\frac{f(x)-f(y)}{x-y} = \sum_{i=0}^{p-1} x^i y^{p-1-i} \equiv \sum_{i=0}^{p-1} x^i x^{p-1-i} = x^{p-1} p = 0 \mod p

פונקציה שמקיימת 2 תנאים אלו תיקרא "p-מכווצת". הסדרה A_{p^n} מקיימת A_{p^{n+1}} = f(A_{p^n}), דבר שגורר, באינדוקציה, p^{n+1} | A_{p^{n+1}} - A_{p^n}:

  • עבור n=0 זה שקול לכך ש-f(A_1) - A_1 מתחלק ב-p – נובע מהתכונה הראשונה של פונקציה p-מכווצת.
  • אם זה נכון עבור n כלשהו, זה נכון גם ל-n+1, מהתכונה השנייה של פונקציה p-מכווצת:

A_{p^{n+2}} - A_{p^{n+1}} = f(A_{p^{n+1}}) - f(A_{p^n})

הערה: אם עובדים בנורמה ה-p-אדית (בה || x-y ||_p = p^{-v_p(x-y)}), הפונקציה הזו היא "כמעט" ליפשיצית. אפשר לנסח את התנאים עליה בתור:

  • || f(x) -x ||_p < 1
  • ||x -y||_p <1 \implies ||f(x)-f(y)||_p \le \frac{1}{p} ||x-y||_p

ניסוח מחדש של הבעיה

נחזור לבעיה שלנו.
תהי A=\left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right) =\left( \begin{array}{cc} F_2 & F_1 \\ F_1 & F_0 \end{array}\right). באינדוקציה ישירה רואים כי A^n = \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array}\right) לכל n שלם אי-שלילי. נשים לב ש-\text{tr}(A^{n})=F_{n+1}+F_{n-1}. לכן אפשר לנסח את השאלה בתור:

הראו כי \text{tr}(A^{p^{n+1}})-\text{tr}(A^{p^{n}}) מתחלק ב-p^{n+1}.

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

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

המקרה n=0

עבור n=0, מקבלים את הטענה הבאה: \text{\text{tr}}(A^{p})=\text{tr}(A)\mod p. היא מאוד מזכירה את המשפט הקטן של פרמה.

בגלל ש-\text{tr} אינווריאנטי לשינוי בסיס (כלומר, הצמדה), נרצה ללכסן את A. זה לא תמיד אפשרי, אבל מה שכן תמיד אפשרי זה שילוש – לפחות אם עובדים בהרחבה מספיק גדולה של \mathbb{F}_{p}. בבסיס זה גם A^p משולשית, והשיוויון נהיה: \sum\alpha^{p}=\sum\alpha\mod p, כאשר הסכום הוא על הע"ע של A.

למקרה הזה יש הוכחה פשוטה במיוחד. הצעד הראשון הוא \sum\alpha^{p}=(\sum\alpha)^{p}\mod p (נכונותו נובעת לדוגמא מכך שהעלאה בחזקת p היא אוטומורפיזם בכל הרחבה סופית של \mathbb{F}_{p}). הצעד השני הוא להראות ש-(\sum\alpha)^{p}\equiv\sum\alpha\mod p – שיוויון במספרים שלמים (כי \sum\alpha=\text{tr}(A)) שנובע מהמשפט הקטן של פרמה.\blacksquare
תרגיל 1: הראו את השיוויון \text{\text{tr}}(A^{p})=\text{tr}(A)\mod p עבור בסיס של המטריצות השלמות, ואז הראו שאם השיוויון עובד לשתי מטריצות הוא עובד גם לסכומן (רמז: השתמשו בכך ש-\text{tr} אינווריאנטי לסיבובים – \text{tr}(ABC) = \text{tr}(BCA)).

המקרה הכללי קשה יותר. הוא נראה כמו \sum\alpha^{p^{n+1}}=\sum\alpha^{p^{n}}\mod p^{n} – קונגרואנציה שמזכירה את משפט אוילר יותר מאת המשפט הקטן של פרמה. עבור מספרים שלמים \alpha היא אכן נובעת ממשפט אוילר, אבל בפועל אלו שלמים אלגברים וכבר אי-אפשר להוכיח את הטענה מחובר-מחובר – צריך את כל הסכום על הצמודים. טענה זו הוכחה בשנות ה-80' ויש הטוענים שאף לפני.

הוכחה קומבינטורית עם גרפים – חדשה אך שקולה

לפני שנוכיח את המקרה הכללי עם פונקציות p-מכווצות, אתן את ההוכחה הקומבינטורית שהבטחתי. הסיפור הוא כזה: אפשר לחשוב על A בתור מטריצת שכנויות של גרף מכוון (ולאו דווקא פשוט).
באופן כללי, מהגדרת כפל מטריצות, A^{n}_{i,j} סופר את כמות המסלולים באורך n מקודקוד i לקודקוד j.
העקבה של A^n סופרת מסלולים בגרף, שאורכם n, והם מתחילים ומסתיימים באותו קודקוד.
הביטוי \text{tr}(A^{p^{n+1}})-\text{tr}(A^{p^{n}}) סופר את מספר המסלולים הלא מחזוריים (כלומר, לא מורכבים מאותו מסלול שחוזר על עצמו מספר פעמים) באורך p^{n+1}. המספר הזה מתחלק ב-p^{n+1} כי לכל מסלול כזה יש p^{n+1} הזזות ציקליות שונות שגם נותנות מסלול המקיים את אותן התכונות.
ודאו שאתם מבינים את השקילות להוכחה עם הפיצות. עבור המקרה של פיבונאצ'י, יש לגרף 2 קודקודים (0 ו-1), ושלוש צלעות (לולאה מ-1 לעצמו, צלע מ-0 ל-1 וצלע בכיוון השני).

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

המקרה הכללי עם פולינומים סימטרים

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

  • למטריצות A, A^p אותו פולינום אופייני מודולו p
  • אם ל-A,B אותו פולינום אופייני מודולו p^k, אז יש ל-A^p,B^p אותו פולינום אופייני מודולו p^{k+1}.

ומתוכן מקבלים באינדוקציה ישירה:

A^{p^{k+1}}, A^{p^{k}} בעלי פולינומים אופייניים שמסכימים מודולו p^{k+1}, לכל k \ge 0.

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

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

אינטרפרטציה להוכחה

באינטרפרטציה הזו, למען הנוחות, נתמקד בטענה שהזכרנו (הנובעת מהמאמר): A^{p^{k+1}}, A^{p^{k}} בעלי פולינומים אופייניים שמסכימים מודולו p^{k+1}, לכל k \ge 0.

במקום לדבר על פולינומים אופייניים, נחזור לדבר על השורשים שלהם (קרי, הערכים העצמיים של המטריצה. מתוכם אפשר לשחזר את הפולינום). נסמן את השורשים של הפולינום של A ב-a_1, \cdots, a_n. נשים לב שכשמעלים מטריצה בחזקה, הערכים העצמיים שלה עולים באותה חזקה.
בגלל שהמטריצות שלנו שלמות, הפולינומים האופייניים הם מתוקנים ועם מקדמים שלמים. בפרט, אפשר לחשוב על השורשים \{ a_j \} כעל שורשים של פולינום מתוקן עם מקדמים שלמים. המקרה שלנו מתייחס ספציפית לפולינום x^2-x-1, עם השורשים a_1,a_2 = \frac{1 \pm \sqrt{5}}{2}.
מנוסחאות ויאטה, אנחנו יודעים שהפולינומים הסימטרים האלמנטרים בשורשים אלו הם מספרים שלמים (במקרה שלנו, a_1+a_2 = 1, a_1 a_2 = -1).
אנחנו רוצים לחקור את העקבה של A^{p^k}, שהיא \sum_{i=1}^{n} a_i^{p^k}.
נסמן ב-e_1(x_1,\cdots, x_n), \cdots, e_n(x_1, \cdots, x_n) את הפולינומים הסימטרים האלמנטרים ב-n משתנים (לדוגמא: e_1(x_1,x_2) = x_1+x_2, e_2(x_1,x_2)=x_1 x_2). אותנו מעניין הפולינום הראשון, e_1, כשמציבים בו את השורשים המדוברים בחזקת חזקות ראשוניים. הדרך להבין את ההצבה הזו היא להבין את כל הפולינומים הסימטרים בו"ז כשמציבים בהם את החזקות הנ"ל, כלומר גם את e_2, \cdots, e_n כשמציבים בהם את החזקות. לכן נסמן:

\vec{v}_{i} = (e_1(a_1^{p^i}, \cdots, a_n^{p^i}), \cdots, e_n(a_1^{p^i}, \cdots, a_n^{p^i}))

(כאמור, אותנו מעניינת רק הקואורדינטה הראשונה, אבל נבין אותה אם נבין את השאר.)
נסמן ב-T_i(x_1,\cdots, x_n) את הפונקציה המקיימת:

T_i(e_1(x_1,\cdots,x_n),\cdots, e_n(x_1,\cdots, x_n)) =e_i(x_1^p,\cdots, x_n^p)

(לדוגמא: T_1(x_1+x_2, x_1 x_2) = x_1^p + x_2^p.) מהמשפט היסודי של הפולינומים הסימטריים, זה פולינום, ולמעשה עם מקדמים שלמים (בפרט, נובע ש-v_i וקטור שלם).
אפשר להגיד משהו חזק יותר – בגלל ש-\frac{T_i(e_1,\cdots,e_n) - e_i^p}{p} עם מקדמים שלמים (מהמשפט הקטן של פרמה), נובע שוב מהמשפט היסודי שזה פולינום עם מקדמים שלמים בפולינומים הסימטרים ובפרט נכון להגיד ש:

T_i(x_1, \cdots, x_n) \equiv x_i^p \mod p

אם נסמן ב-\vec{T} את הפונקציה הוקטורית שמורכבת מכל הפולינומים הללו, \vec{T} = (T_1, \cdots, T_n), נקבל ש:

\vec{v}_{i+1} = \vec{T}(\vec{v}_{i} )

זה שיוויון פנטסטי, שמציג את הסדרה המעניינת אותנו כסדרת רקורסיה מעומק 1. איך נראית הפונקציה \vec{T}?

  • עבור מטריצות 1 על 1, T(x) = x^p
  • עבור מטריצות 2 על 2, T(x+y, xy) = (x^p+y^p, x^py^p). לדוגמא, עבור p=2 נקבל T(a,b) = (a^2-2b, b^2).
    עבור מטריצות 3 על 3, T(x+y+z, xy+yz+zx,xyz) = (x^p+y^p+z^p, x^py^p+y^pz^p+z^px^p, x^p y^p z^p))

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

פונקציה \vec{F}: \mathbb{Z}^d \to \mathbb{Z}^d תיקרא "p-מכווצת" אם מתקיימות 2 התכונות הבאות:

  • \vec{F}(\vec{x}) \equiv \vec{x} \mod p – כלומר, כל קואורדינטה של הפרש הוקטורים מתאפסת מודולו p
  • \vec{x} \equiv \vec{y} \mod p^k (כאשר k>0) גורר \vec{F}(\vec{x}) \equiv \vec{F}(\vec{y}) \mod p^{k+1}

אם נראה ש-\vec{T} היא p-מכווצת, אז התכונות שלה יגררו באינדוקציה ישירה ש-\vec{v}_{i+1} \equiv \vec{v}_{i} \mod p^{i+1}, וזה בדיוק מה שרצינו להוכיח.

תרגיל חשוב: הראו ש-\vec{T} שלנו היא p-מכווצת מתוך כך שהיא פונקציה פולינומיאלית המקיימת T_i(x_1, \cdots, x_n) \equiv x_i^p \mod p.
(רמז: התנאי הראשון נובע ישירות מהמשפט הקטן של פרמה. התנאי השני סגור לחיבור, לכן מספיק להוכיח זאת עבור הפונקציה F_1(x_1, \cdots, x_n) = (x_1^p, \cdots, x_n^p) ועבור פונקציה פולינומיאלית שכל מקדמיה מתחלקים ב-p.)

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

\text{tr}(A^{p^{k+1}}) \equiv \text{tr}(A^{p^k}) \mod p^{k+1}
\det(A^{p^{k+1}}) \equiv \det(A^{p^k}) \mod p^{k+1}

מגניב.

הערה: כדאי לחשוב על \vec{T} כעל העלאה בחזקת p (קואורדינטה-קואורדינטה), עד כדי "שגיאה" שהיא פולינום כפול p. זה מבטיח התכנסות p-אדית של הסדרה \vec{v}_{i+1} = \vec{T}(\vec{v}_i) – אנחנו מתכנסים לנקודת שבת לא טריוויאלית של \vec{T} ב-p-אדים. כלומר, ב-p-אדים, הפונקציה \vec{T} מקיימת בדיוק את התנאים (הכמו-ליפשיציים) כדי שהאיטרציות \vec{v}_{i+1} = \vec{T}(\vec{v}_{i} ) יתכנסו לנקודת שבת, מה שמזכיר מאוד את הבנייה של קרקטר Teichmüller.

שלבי ההוכחה המקורית

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

1. יהי f\in\mathbb{Z}[x_{1},\cdots,x_{n}] פולינום סימטרי ו-p מספר ראשוני. הראו שקיים פולינום סימטרי h\in\mathbb{Z}[x_{1},\cdots,x_{n}] כך ש-

f(x_{1}^{p},\cdots,x_{n}^{p})=f(x_{1},\cdots,x_{n})^{p}+ph(x_{1},\cdots,x_{n})

2. יהיו e_{1},\cdots,e_{n}\in\mathbb{Z}[x_{1},\cdots,x_{n}] הפולינומים הסימטרים האלמנטרים ב-x_{1},\cdots,x_{n}. מהמשפט היסודי של הפולינומים הסימטרים, לכל 1 \le i \le n קיים פולינום יחיד T_{p,i}\in\mathbb{Z}[x_{1},\cdots,x_{n}] כך ש-

e_{i}(x_{1}^{p},\cdots,x_{n}^{p})=T_{p,i}(e_{1}(x_{1},\cdots,x_{n}),\cdots,e_{n}(x_{1},\cdots,x_{n}))

השתמשו בסעיף הקודם כדי להראות ש-T_{p,i}(x_{1},\cdots,x_{n})\equiv x_{i}^{p}\mod p.

3. נעבוד ב-\mathbb{Z}[x_{1},\cdots,x_{n},y_{1},\cdots,y_{n}] ונגדיר את האידאל I=(y_{1},\cdots,y_{n}). השתמשו בפיתוח טיילור ובסעיף הקודם כדי להראות ש-

T_{p,i}(x_{1}+y_{1},\cdots,x_{n}+y_{n})\equiv T_{p,i}(x_{1},\cdots,x_{n})\mod(pI+I^{2})

4. עבור פולינום מתוקן f(x)=x^{n}+\sum_{i=1}^{n}(-1)^{i}a_{i}x^{n-i}=\prod_{i=1}^{n}(x-u_{i}) (מעל חוג חילופי כללי) נתאים את הפולינום המתוקן, מאותה מעלה, T_{p}(f)=x^{n}+\sum_{i=1}^{n}(-1)^{i}T_{p,i}(a_{1},\cdots,a_{n})x^{n-i}.
הראו ש-T_{p}(f)=\prod_{i=1}^{n}(x-u_{i}^{p}) והסיקו שאם f הפולינום האופייני של מטריצה A אז T_p(f) הפולינום האופייני של A^p.

5. מסקנה משני הסעיפים האחרונים: אם R חוג חילופי, ו-I אידאל בו, אז f\equiv g\mod I גורר T_{p}(f)\equiv T_{p}(g)\mod(pI+I^{2}).
עבור R=\mathbb{Z},I=(p^{k}) נקבל: f\equiv g\mod p^{k} גורר T_{p}(f)\equiv T_{p}(g)\mod p^{k+1}.

6. הראו, בעזרת סעיף 4, כי עבור f\in\mathbb{Z}[x] מתוקן, מתקיים T_{p}(f)\equiv f\mod p. כלומר, ל-A ול-A^p אותו פולינום אופייני מודולו p.

7. כעת אפשר להראות, באינדוקציה על k, של-A^{p^{k}},A^{p^{k+1}} אותו פולינום אופייני מודולו p^{k+1}: מקרה הבסיס הוא הסעיף הקודם, וצעד האינדוקציה מהסעיף הקודם-קודם.
בפרט, יש להם אותה עקבה מודולו p^{k+1}\blacksquare

הכללות

הכללה של ההוכחה הראשונה

נכליל את ההוכחה הראשונה באמצעות פונקציית מביוס:

\sum_{d|n}\mu(\frac{n}{d})L_{d} מתחלק ב-n לכל n טבעי.

עבור n שהוא חזקת ראשוני, מקבלים את הבעיה המקורית. ההוכחה היא כמו ההוכחה הקומבינטורית, רק עם הכלה-הדחה יותר עדינה: אנחנו סופרים פיצות פיבונאצ'י לא מחזוריות מאורך n. דוגמא: pq|L_{pq}-L_{p}-L_{q}+L_{1} לכל זוג ראשוניים שונים p,q. אתן לכם להשלים את הפרטים.

הכללה של ההוכחה השנייה

נכליל את ההוכחה השנייה באמצעות חקר מטריצות.

ההוכחה השנייה ממשיכה לעבוד כאשר מחליפים את L_n בכל סדרה שמופיעה כעקבה של חזקות מטריצה שלמה. אילו סדרות אפשר לקבל כך? נשים לב שאם A מטריצה ריבועית שלמה אז \text{tr}(A^{n}) מקיימת נוסחה נסיגה לינארית (שנגזרת ישירות מהפולינום האופייני של A). לכן מדובר בהכרח בסדרות שהן סדרות נסיגה עם מקדמים שלמים.

מסתבר שלכל נוסחת נסיגה a_{n}=\sum_{i=1}^{d}\lambda_{i}a_{n-i} עם מקדמים שלמים, יש תנאי התחלה יחידים כך שהיא תתקבל בתור \text{tr}(A^{n}). הפולינום האופייני של A כזו חייב להיות הפולינום האופייני של הנוסחה: x^{n}-\sum_{i=1}^{d}\lambda_{i}x^{n-i} (ואפשר לבנות כזו מטריצה לדוגמא בעזרת מטריצה נלוות). לאחר שילוש, אנחנו מגלים ש-\text{tr}(A^{n})=\sum\alpha^{n} כאשר הסכום הוא על שורשי הפולינום.
נובע שתנאי ההתחלה הם: a_{i}=\sum\alpha^{i} עבור 0\le i\le d-1.
הערה: אפשר לכתוב את \sum\alpha^{i} כפולינומים במקדמים \lambda_{i} – ראו זהויות ניוטון.

דוגמא: אם d=1 אז a_0 = 1 והסדרה נהיית a_{n}=\lambda_{1}^{n}.
אם d=2, אז a_{0}=2,a_{1}=\lambda_{1} ו-a_n = \lambda_1 a_{n-1} + \lambda_2 a_{n-2}. בפרט, אם רוצים את נוסחת הנסיגה של פיבונאצ'י, נקבל את תנאי ההתחלה a_0=2, a_1=1.

נשים לב ש-L_n היא גם סדרה כזו – אם נשתמש בנוסחת המפורשת F_{n}=\frac{\phi^{n}-\overline{\phi}^{n}}{\phi-\overline{\phi}}, נקבל:

L_{n}=\frac{\phi^{n}\phi^{-1}-\overline{\phi}^{n}\overline{\phi}^{-1}}{\phi-\overline{\phi}}+\frac{\phi^{n}\phi-\overline{\phi}^{n}\overline{\phi}}{\phi-\overline{\phi}}=\frac{\phi^{n}(\phi^{-1}+\phi)-\overline{\phi}^{n}(\overline{\phi}^{-1}+\overline{\phi})}{\phi-\overline{\phi}}=\phi^{n}+\overline{\phi}^{n}

כאשר השיוויון האחרון נבע מכך ש-\phi\cdot\overline{\phi}=-1.

L_n מוכרת בתור "סדרת לוקאס" ומקיימת בין השאר L_{n}=\frac{F_{2n}}{F_{n}}.

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

אדואר לוקאס (1842-1891), מתמטיקאי צרפתי. חקר את מספרי פיבונאצ'י ואת מספרי לוקאס. מי שהמציא את החידה הידועה בתור "מגדלי האנוי".

שילוב שתי ההכללות

אם נשלב את 2 ההכללות, נקבל שאם a_n היא סדרת נסיגה מעומק d המקיימת a_{i}=\sum\alpha^{i} (סכום על d שורשי הפולינום האופייני של הסדרה) עבור 0\le i\le d-1, אז \sum_{m|n}\mu(\frac{n}{m})a_{m} מתחלק ב-n לכל n טבעי.

תרגיל 2: הראו שהביטוי \sum_{d|n} \phi(\frac{n}{d}) L_d מתחלק ב-n, לכל n טבעי. (רמז: נגדיר שפיצות הן שקולות אם אחת מתקבלת מהשנייה ע"י סיבוב. סיפרו את מספר מחלקות השקילות של פיצות חוקיות באורך n בעזרת משפט המנייה של פוליה.)
תרגיל 3: הראו שלא מקבלים אינפורמציה אריתמטית חדשה על הסדרה L_n מתוך התרגיל הקודם, ושלמעשה גם התכונה \forall n \in \mathbb{N}: n | \sum_{d|n} \mu(\frac{n}{d}) L_d וגם התכונה \forall n \in \mathbb{N}: n | \sum_{d|n} \phi(\frac{n}{d}) L_d שקולות לתכונה: p^{k} | L_{p^{k}n}-L_{n} לכל ראשוני p ו-n,k טבעיים.
(תרגילים נוספים בניחוח זה תוכלו למצוא באוסף התרגילים על פונקציות אריתמטיות כאן – הסתכלו לדוגמא על שאלה 8.)

מודעות פרסומת

אודות Ofir Gorodetsky

Graduate student at TAU. Can be contacted at bambaman1 at gmail dot com.
פוסט זה פורסם בקטגוריה המשפט הקטן של פרמה, פולינומים, קומבינטוריקה, תורת המספרים. אפשר להגיע ישירות לפוסט זה עם קישור ישיר.

להשאיר תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s