מנה שלמה

שלומות,

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

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

הבעיה היא כזו: בהינתן n \ge 2 מספרים a_0, a_1, \cdots, a_{n-1} שלמים, אז הביטוי  \frac{\prod_{0\le j <i \le n-1} (a_i - a_j)}{\prod_{0 \le j < i \le n-1} (i-j)} שלם, כלומר מכפלת ההפרשים \prod_{0 \le j < i \le n-1} (a_i - a_j) מתחלקת במכפלת ההפרשים \prod_{0 \le j < i \le n-1} (i-j).

אז יש לנו מכפלה עם הרבה גורמים (ספציפית, \binom{n}{2}) שמתחלקת במכפלה אחרת עם אותו מספר גורמים. לפחות כש-\forall i: a_i = i הטענה נכונה.

ננסה לפתור מקרה פרטיים, כדי לקבל מושג כלשהו לגבי הבעיה:
n = 2: הטענה היא ש-a_2 - a_1 מתחלק ב1 כאשר a_1, a_2 שלמים. הפרש של מספרים שלמים הוא שלם, וסיימנו את המקרה הזה.

n=3: הטענה היא ש-(a_3 - a_1)(a_2-a_1)(a_3 - a_2) מתחלק ב(3-2)(2-1)(3-1) = 2. זה נכון, כי לפי שובך היונים, מבין שלושת המספרים a_1,a_2,a_3 יש שניים (לפחות) בעלי אותה זוגיות ומכאן ההפרש שלהם זוגי.

n= 4: הטענה הופכת לכך ש(a_4 - a_3)(a_4 -a_2)(a_4 - a_1)(a_3 - a_2)(a_3- a_1)(a_2-a_1) מתחלק ב(4-3)(4-2)(4-1)(3-2)(3-1)(2-1) = 12. נטפל קודם בהתחלקות ב3 ולאחר מכן בהתחלקות ב4 (זה יספיק כי 12 = 3 \cdot 4, (3,4)=1). יש לנו ארבעה מספרים, ולכן משובך היונים יש 2 עם אותה שארית חלוקה ב3 ומכאן ההפרש שלהם מתחלק ב3.

לגבי החלוקה ב-4: מתוך 4 מספרים, אם יש 3 מספרים או יותר עם אותה זוגיות, אז יהיו 3 גורמים שמתחלקים ב2, כלומר המכפלה תתחלק ב8. אחרת, יש 2 זוגיים ו2 אי-זוגיים, ולכן יהיו 2 הפרשים זוגיים בדיוק, כלומר המכפלה תתחלק ב-4.

ואנחנו כבר מקבלים מושג מסויים לגבי הפיתרון. אבל האם אפשר להכליל זאת לכל n \ge 2? נסו זאת בעצמכם לפני שאתם ממשיכים.

סימונים לפוסט זה (חשוב!):

p – מספר ראשוני
p^k || n – החזקה המקסימלית של p המחלקת את n היא p^k, כלומר p^k | n אבל p^{k+1} \nmid n.

(x,y) – מחלק משותף גדול ביותר של x, y.

מעלה של פולינום במשתנה x_i – מעלת הפולינום כשמתייחסים לשאר המשתנים כקבועים.

(x)_n – המכפלה \prod_{i=0}^{n-1} (x-i)

LCM – מכפלה משותפת מינימלית של אוסף מספרים שלמים.

Vander(a_0, \cdots, a_{n-1}) – דטרמיננטה של מטריצת ונדרמונדה מהצורה a_{i,j} = a_i^j.

P_{1}=\prod_{0\le j<i\le n-1}(i-j),P_{2}=\prod_{0\le j<i\le n-1}(a_{i}-a_{j}) – סימון יחודי לבעיה

ראשוני-ראשוני

1. הפיתרון הראשון יהיה הפיתרון האינטואיטיבי: כמו שהתחלנו עם המקרים הפרטיים וניסינו להראות את התוצאה בנפרד לכל חזקת ראשוני (p^{k}||P_{1}\implies p^{k}||P_{2}), נעשה זאת גם כאן.

נשים לב ש-

P_{1}=\prod_{i=1}^{n-1}\prod_{j=0}^{i-1}(i-j)=\prod_{i=1}^{n-1} i!=1!2!\cdots(n-1)!

נרצה להבין את הפירוק לגורמים של P_1. בשביל זה נוסיף סימון חדש: v_p(n) = k אמ"מ p^k || n. הפונקציה v_p נקראת 'הערכה p-אדית' והיא מודדת כמה n מתחלק בp. נשתמש בתכונה השימושית שלה, שהיא הופכת כפל לחיבור: v_p(xy) = v_p(x) + v_p(y).

איך מחשבים, עבור מספרים שלמים שונים מאפס x_1, \cdots ,x_m את v_p(x_1 \cdot x_2 \cdot \cdots \cdot x_m)? מסמנים בt_1 כמה x_i-ים מתחלק בp. אח"כ מסמנים בt_2 כמה x_i-ים מתחלקים בp^2, וכן הלאה.

סה"כ, v_{p}(x_{1}\cdots x_{m})=\sum_{i \ge 1} t_{i}. (הסכום מוגדר היטב כי החל מנקודה מסויימת הt_i-ים מתאפסים.) מה הסיבה? אם נסתכל על הפירוק של x_1 x_2 \cdots x_m לראשוניים, אז בדיוק t_k - t_{k-1} x_i-ים מקיימים v_p(x_i) = k, ולכן v_{p}(x_{1}\cdots x_{m})=\sum_{k \ge 1} k(t_{k}-t_{k-1})=\sum_{i \ge 1} t_{i} (t_0 = 0). לחילופין, אפשר להגיד שכל התחלקות בp^k מוסיפה אחד לv_{p}(x_{1}\cdots x_{m}).

עכשיו אפשר לחשב את v_p(m!): כמה מספרים מתוך \{ 1,2,\cdots ,m\} מתחלקים בp^k? בדיוק \lfloor\frac{m}{p^{k}}\rfloor (בדקו!). לכן:

v_{p}(m!)=\sum_{k\ge1}\lfloor\frac{m}{p^{k}}\rfloor

ומכאן,

v_{p}(P_{1})=\sum_{m=1}^{n-1}v_{p}(m!)=\sum_{m=1}^{n-1}\sum_{k\ge1}\lfloor\frac{m}{p^{k}}\rfloor

(הערה: הטור הפנימי הוא טור סופי בעצם, כי אם k > \log_p n אז \lfloor\frac{m}{p^{k}}\rfloor=0.)

איך נוכיח את ההתחלקות? נרצה להראות שכמות הזוגות a_i - a_j, i>j המתחלקים בp^k היא לפחות \sum_{m=1}^{n-1}\lfloor\frac{m}{p^{k}}\rfloor. כשנסכום על k, תנבע התוצאה: v_p(P_2) \ge v_p(P_1).

למה: אם מחלקים את a בb עם שארית ומקבלים a = bq +r, 0 \le r < q, אז \sum_{m=1}^{a}\lfloor\frac{m}{b}\rfloor=b\binom{q}{2}+q(r+1). הוכחה: תרגילון.

כמעט סיימנו. נניח שמתוך קבוצת ה\{ a_j \}_{j=1}^{n}-ים, יש בדיוק x_i ששווים i \text{mod} p^k. אז כל 0 \le m < p^k תורם \binom{x_m}{2} זוגות a_i - a_j שההפרש ביניהם מתחלק בp^m. לכן מספר הזוגות a_i - a_j המתחלקים בp^k שווה ממש ל\sum_{i=0}^{p^{k}-1}\binom{x_{i}}{2}. אם נכתוב n-1=qp^{k}+r, צ"ל:

(*) \sum_{i=0}^{p^{k}-1}\binom{x_{i}}{2}\ge p^{k}\binom{q}{2}+q(r+1)

נשים לב ש-f(x) = \binom{x}{2} פונקציה קמורה. מכאן, המינימום של הסכום (תחת האילוץ שסכום הx_i הוא n) אינטואיטיבית מתקבל כשהx_i קרובים או אפילו שווים (ראו אי-שיוויון ינסן). אפשר להוכיח זאת בנקל – אם x_i \ge x_j + 2 אז \binom{x_{i}}{2}+\binom{x_{j}}{2}>\binom{x_{i}-1}{2}+\binom{x_{j}+1}{2} (בידקו! רמז – \binom{n+1}{2}-\binom{n}{2}=\binom{n}{1}), כלומר במצב שבו מתקבל המינימום, הx_i המינימלי שווה או קטן ב1 מהx_i המקסימלי. נניח x_1 = \cdots = x_{r'+1} = x+1, x_{r'+2} = \cdots = x_n = x, r' \ge 0. x חייב לקיים \frac{n}{p^k} - 1 \le x < \frac{n}{p^k}, מה שמאלץ x = q וr'=r, ואז המינימום הוא:

(r'+1)\binom{x+1}{2}+(p^{k}-r'-1)\binom{x}{2}=p^{k}\binom{x}{2}+x(r'+1)= p^{k}\binom{q}{2}+q(r+1)

וקיבלנו שמתקיים (*), כלומר מספר האיברים המתחלקים בp^k במונה גדול/שווה מאלו במכנה, לכל p ראשוני וk טבעי.

משימה: קראו את המאמר Unrigorously Jensen, המכיל עוד בעיות קומבינטוריות הנפתרות באמצעות קמירות f(x) = \binom{x}{2}.

תרגיל 1: הוכיחו ש\prod_{0 \le i < j \le n-1} (a_j^2 - a_i^2) מתחלק ב\frac{2!4!\cdots (2n-2)!}{2^n}.

——

אלגברה ליניארית ומטריצת ונדרמונדה

נציג משפחה חדשה של פתרונות. לפני כן, יש להיזכר בקונספט של מטריצת ונדרמונדה: מטריצת ונדרמונדה היא מטריצה מהצורה a_{i,j} = x_{i} ^{j} עבור  0\le i,j \le k-1 (או הטרנספוז שלה). הדטרמיננטה שלה היא \prod_{0 \le j < i \le k-1} (x_{i}-x_{j}) – כמו בביטוי בשאלה. ולמה זו הדטרמיננטה? כי כש-x_i = x_j אז הדטרמיננטה מתאפסת (2 שורות שוות), לכן מכפלת הגורמים הלינאריים הזרים הללו מחלקת את הדטרמיננטה, שהיא פולינום בx_i (בדקו! רמז: פריקות יחידה של פולינומים). מצד שני, משיקולי מעלות, בגלל ש\deg\det A \le\binom{n}{2}=\deg\prod(x_{i}-x_{j}), אז בהכרח הדטרמיננטה היא C\prod(x_{i}-x_{j}) עבור קבוע רציונלי C. כדי להראות שC=1 אפשר להשתמש באינדוקציה או לבחור מונום ספציפי במכפלה הזו ולבדוק מה המקדם שלו בדטרמיננטה ובמכפלה.

אנחנו מכירים את המטריצה הזו כבר: אם יש לנו פולינום P ממעלה k-1 \ge, המקבל בנקודה x_i את הערך v_i (0 \le i \le k-1), ווקטור המקדמים שלו הוא \vec{p}^{T} = (p_0,p_1,\cdots,p_{k-1}) אז A \vec{p} = \vec{v}. לכן, להפוך את A שקול ללמצוא את מקדמי הפולינום העובר דרך הנקודות הללו. לכן בעצם אינטרפולציית לגראנז' היא נוסחה לA^{-1}. אפשר להפוך מטריצת בעזרת כלל קרמר, כלומר: מטריצת ונדרמונדה + כלל קרמר = אינטרפולציית לגראנז'.

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

נסתכל על הדטרמיננטה של המטריצה B המוגדרת ע"י b_{i,j} = \binom{a_i}{j}, עם 0\le i,j \le n-1. מצד אחד, איברי המטריצה שלמים לכן הדטרמיננטה היא מספר שלם. מצד שני, אחרי שמוציאים מעמודה j את j!^{-1}, מקבלים ש-

\det B = \prod_{i=1}^{n-1} i!^{-1} \det (a_{i})_{j} = P_1^{-1} \det (a_{i})_{j}

(תזכורת: הסימון (x)_n משמעו המכפלה \prod_{i=0}^{n-1} (x-i))

אבל בעצם \det (a_{i})_{j} = P_2, כי (a_{i})_{j} פולינום מתוקן בa_i ממעלה j, ולכן אפשר להחסיר מעמודה j קומבינציה של עמודות קודמות (j'<j) כך שבעמודה j יהיה ממש a_{i}^{j}, כך לכל j מהקטן לגדול, וקיבלנו דטרמיננטה של מטריצת ונדרמונדה השווה לP_2. לכן \frac{P_2}{P_1} = \det B \in \mathbb{Z}.

תרגיל 2: הוכח כי \prod_{0 \le j < i \le n-1} (a_{i}-a_{j}) \frac{LCM(a_{i})}{\prod a_{i}} מתחלק ב-\prod_{0 \le j < i \le n-2} (i-j). (רמז: החליפו את העמודה האחרונה של B בעמודה אחרת.) מצאו דוגמה בה יש שיוויון. מצאו דוגמה בה המשפטים נותנים אותה תוצאה.

3. הפיתרון הבא גם משתמש במטריצת ונדרמונדה, אבל הוא יותר טבעי. נגדיר 2 מטריצות A,B:

a_{i,j} = j^i, b_{i,j} = a_{j}^{i}, 0\le i,j \le n-1

אז אנחנו צריכים להוכיח ש\det A^{-1}B שלם. זה ינבע אם נראה שA^{-1}B מטריצה עם ערכים שלמים, וזה אכן המצב. נסמן בC את המכפלה הזו, ובC^{(i)} את העמודה הi שלה. מקבלים, עבור 0\le i \le n-1:

B^{(i)}=AC^{(i)}

ובעזרת כלל קרמר אפשר לחלץ את C^{(i)}. תזכורת על כלל קרמר: אם A הפיכה, פיתרון של A\vec{x} = \vec{b} ניתן מפורשות ע"י x_{i}=\frac{\det A_{i,\vec{b}}}{\det A}, כאשר A_{i,\vec{b}} היא A שבה החליפו את העמודה הi ב\vec{b}. הוכחה: המשוואה שקולה ל\sum x_{i}A^{(i)}=b. הסכום הזה הוא העמודה הi של A_{i,\vec{b}}, וכדי לחשב את הדטרמיננטה שלה נחסר מהעמודה הזו כפולות מתאימות של העמודות האחרות, ובסוף נשאר עם עמודה ששווה לx_i A^{(i)}. הקבוע x_i יוצא החוצה:

\det A_{i,\vec{b}}=\det(A^{(0)},\cdots,A^{(i-1)},x_{i}A^{(i)},A^{(i+1)},\cdots,A^{(n-1)})=x_{i}\det A \implies x_{i} = \frac{ \det A_{i,\vec{b}} }{\det A}

נפעיל את הכלל:

C_{j}^{(i)}=\frac{\det A_{j,B^{(i)}}}{\det A}=\frac{Vander(0,1,\cdots,j-1,a_{i},j+1,\cdots,n-1)}{Vander(0,1,\cdots,n-1)}=\frac{\prod_{i>k,i,k\neq j}(i-k)}{\prod_{i>k,i,k\neq j}(i-k)}\frac{\prod_{k<j}(a_{i}-k)\prod_{k>j}(k-a_{i})}{\prod_{k<j}(j-k)\prod_{k>j}(k-j)}=\frac{\prod_{k<j}(a_{i}-k)\prod_{k>j}(k-a_{i})}{\prod_{k<j}(j-k)\prod_{k>j}(k-j)}=\binom{a_{i}}{j}\binom{n-1-a_{i}}{n-j-1}

כלומר קיבלנו שהמטריצה C ניתנת ע"י C_{i,j}=\binom{a_{j}}{i}\binom{n-1-a_{j}}{n-i-1}, ומכך שמקדמים בינומיים הם שלמים נובע ש\frac{P_2}{P_1} = \det C\in\mathbb{Z}.

————

תכונות של פולינומים

הפתרונות הבאים יהיו בניחוח פולינומים ויתחברו לפוסט הקודם.

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

נסמן בL_j(x) את הפולינום ממעלה n-1 המקיים L_{j} (a_{i}) = 0 עבור i \neq j וL_{j}(a_{j}) = 1 (אנחנו מניחים שהa_i שונים, אחרת הטענה טריוויאלית). קל לראות ש\{ L_i \}_{i=0}^{n-1} בת"ל (אם יש צירוף שהוא אפס, אז בפרט הוא מתאפס על a_i ולכן L_i נלקח עם מקדם 0). לכן את הפולינום x^i אפשר לכתוב בתור \sum_{j=0}^{n-1} a_{j}^{i}L_{j}(X), עבור 0 \le i \le n-1: 2 האגפים ממעלה n-1 \ge ומזדהים על \{a_{i}\}_{i=0}^{n-1}, ולכן הם אותו פולינום. כלומר המטריצה B שכניסותיה a_j^i מעבירה מהבסיס \{x^i \}_{i=0}^{n-1} לבסיס \{L_i(x)\}_{i=0}^{n-1}, והדטרמיננטה שלה היא P_2.

כעת נעשה אותו תהליך עם a_i =i (נסמן את הפולינומים בM_i), ונקבל מטריצה A עם כניסות j^i שמעבירה מבסיס \{ x^i \}_{i=0}^{n-1} לבסיס \{ M_i(x) \}_{i=0}^{n-1}, עם דטרמיננטה P_1. המטריצה A^{-1} B מעבירה בין הבסיס \{ L_i \} ל\{M_i \}.

למה כניסותיה שלמות? כי זה שקול לכך שM_i = \sum_{j} m_{i,j} L_{j} גורר שm_{i,j} מספרים שלמים. נציב x=a_j ונקבל m_{i,j} = M_{i}(a_{j}). מכך שM_i מקבל ערך שלם על 0,1,\cdots ,n-1 והוא ממעלה n-1 \ge, הוא מקבל ערך שלם על כל מספר שלם (ראו פוסט קודם), בפרט על a_j, ומכאן m_{i,j} שלמים

5. אינדוקציה! אבל על מה? על M=\max\{a_{i}\}_{i=0}^{n-1}. קודם נבחין במשהו בסיסי: אפשר להניח (וכך נעשה) בה"כ שa_i חיוביים, ע"י הוספת מספר טבעי מספיק גדול לכולם (בגלל שרק ההפרשים חשובים לנו, זה לא משפיע). נשים לב שבאינדוקציה לא נקבע את ערך n.

אם M = 1, הביטוי מתאפס ובפרט שלם כי כל הa_i שווים ל1.

כעת נניח שהוכחנו עבור כל M \le k, ונרצה להוכיח עבור M = k+1. נפצל לשלושה מקרים:

א': אם k+1 < n, אז משובך היונים יש שני a_i שווים, ולכן הביטוי מתאפס ובפרט שלם.

ב': אם k+1 = n, המספרים a_i הם פרמוטציה של \{ 0, 1, \cdots, n-1 \}, ולכן הביטוי שווה 1 (עד כדי סימן ששווה לסימן הפרמוטציה), פשוט כי במונה ובמכנה יש אותם איברים עד כדי סימן.

ג': אם k+1 > n, אז אם יש לנו שני a_i שווים, סיימנו. אחרת, נניח בה"כ כי a_{n-1} = M וששאר a_i קטנים מM (שינוי סדר יכול לשנות רק את סימן הביטוי). נגדיר פולינום בn משתנים: h(x_0,\cdots,x_{n-1}) = \frac{\prod_{0 \le j < i \le n-1} (x_i-x_j)}{\prod_{0 \le j < i \le n-1} (i-j)} להיות הביטוי בשאלה, שהוא למעשה פולינום. נגדיר פולינום במשתנה אחד: g(t)=h(a_{0},\cdots,a_{n-2},t). נשים לב שאם 1\le t \le M-1 אז מהנחת האינדוקציה g(t) \in \mathbb{Z}. מעלת g היא n-1, שקטנה מk = M-1. לפי הפוסט הקודם, אם פולינום ממעלה קטנה מn מקבל ערך שלם על n ערכים שלמים עוקבים, הוא תמיד מקבל ערכים שלמים על נקודות שלמות. מכאן g(a_{n-1}) = g(M) גם כן שלם, מש"ל.

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

נשים לב שh מקבל ערכים שלמים על \{ 0,1, \cdots, n-1\}^{n}: אם x_i = x_j עבור i \neq j, אז הפולינום מתאפס. אחרת, הx_i-ים הם פרמוטציה של \{0, 1, \cdots, n-1 \}, ואז ערך הפולינום שווה בדיוק לסימן של הפרמוטציה (\pm 1), כלומר מקבל ערך שלם.

עכשיו הראו, בגזירה דיסקרטית, שאם פולינום ממעלה d_i בx_i (0 \le i \le n-1) מקבל ערכים שלמים על \prod_{i=0}^{n-1} \{0, 1, \cdots, d_i \} אז הוא מקבל ערכים שלמים על \mathbb{Z}^{n}.

תרגיל 3: הוכיחו את הטענה האחרונה. האם אפשר לחזק אותה?

———

אנלוגיות-q

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

לפני כן, נדבר על אנלוגיות-q. בפתרונות הקודמים נתקלנו רבות במקדמים בינומיים. בואו ננסה להוכיח את השלמות שלהם בלי להשתמש באינטרפרטציה הקומבינטורית הסטנדרטית. \binom{n+m}{n} שלם אמ"מ מכפלת n המספרים העוקבים m+1,m+2,\cdots,m+n מתחלקת בn!. נוכיח משהו חזק יותר: הפונקציה הרציונלית

f(q)=\frac{\prod_{i=m+1}^{m+n}\frac{q^{i}-1}{q-1}}{\prod_{i=1}^{n}\frac{q^{i}-1}{q-1}}

היא בעצם פולינום שמקבל ערכים שלמים לכל q שלם.

קודם כל, למה זה אכן גורר את הטענה? כי f(1) שווה ל\binom{n+m}{m} (רמז: \frac{q^{i}-1}{q-1}=1+q+\cdots+q^{i-1}).

ואיך מוכיחים את הטענה? גישה אחת היא אלגברית לגמרי: נשים לב ש-f(q)=\frac{\prod_{i=m+1}^{m+n}(q^{i}-1)}{\prod_{i=1}^{n}(q^{i}-1)} הוא מנה של 2 פולינומים מתוקנים עם מקדמים שלמים. אם נראה שהמכנה מחלק את המונה, אז הלמה של גאוס גוררת שf גם הוא פולינום מתוקן עם מקדמים שלמים. ואיך מוכיחים את ההתחלקות? נראה ששורש של המכנה הוא שורש של המונה עם לפחות אותו ריבוי. ניקח שורש יחידה מסדר 1 \le r \le n. המכנה מתאפס בו (מריבוי אחד) לכל i שמתחלק בr (בגלל הביטוי q^i -1), סה"כ: ריבוי \lfloor\frac{n}{r}\rfloor. המונה מתאפס בו לכל m+1 \le i \le m+n שמתחלק בr, סה"כ: ריבוי \lfloor\frac{m+n}{r}\rfloor-\lfloor\frac{m}{r}\rfloor. כעת נותר להראות ש\lfloor x+y \rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor לכל x,y ממשיים. מכיוון ש\lfloor x+1\rfloor=1+\lfloor x\rfloor, אפשר להניח בה"כ שx,y\in[0,1), ואז הטענה שקולה ל-\lfloor x+y \rfloor \ge 0 עבור x,y \ge 0, וזה נכון.

הוכחה אחרת מסתמכת על הפירוש הקומבינטורי של המקדמים הבינומיים, אבל באופן מוכלל: נניח ויש לנו שדה סופי \mathbb{F}_{q}, ואנחנו רוצים לספור שרשראות מקסימליות מעל המרחב הוקטורי \mathbb{F}_{q}^{n}, כלומר סדרה עולה ממש של תתי-מרחבים וקטורים מאורך מקסימלי. איך בונים שרשרת? מתחילים במרחב ה-0, V_0 = \{ \vec 0 \}, וכל פעם בוחרים וקטור שלא נמצא בתת-המרחב, ומסתכלים על תת-המרחב שמתקבל כשמוסיפים אותו. השרשרת המתקבלת תהיה באורך n. ע"י בנייה הדרגתית של השרשרת, מקבלים שמספר השרשראות הוא:

\prod_{i=0}^{n-1} \frac{q^n - q^i}{q^{i}(q-1)} = \prod_{i=0}^{n-1} \frac{q^{n-i} - 1}{q-1}

(ודאו זאת!)

ביטוי זה מסומן n!_q (עצרת q-ית). כאשר q=1 אנחנו מקבלים n!_1 = n!  – שזה במובן מסויים מספר השרשראות העולות מאורך n מעל היצור הפיקטיבי "שדה מגודל 1": n! סופר את מספר השרשראות המקסימליות של תתי-קבוצות של \{1,2,\cdots,n\}. את f אפשר לפרש כעת בתור \frac{(n+m)!_q}{n!_q m!_q} = \binom{n+m}{m}_q ("מקדם q-נומי"). מה המשמעות הקומבינטורית? כמה תתי-מרחבים ממימד n יש במרחב ממימד n+m מעל השדה \mathbb{F}_{q}. (הראו זאת!) התשובה לשאלה זו היא מספר שלם, וסיימנו.

תרגיל 4: קראו על הלמה של גאוס והוכיחו אותה. הסיקו ממנה שאם P,Q \in \mathbb{Z}[x] פולינומים מתוקנים ו-\frac{P}{Q} \in \mathbb{Q}[x] אז \frac{P}{Q} \in \mathbb{Z}[x].

תרגיל 5: הוכיחו אנלוגיות-q של משפטים על מקדמים בינומים (באופן אלגברי וקומבינטורי):

\binom{n+m}{k}_{q}=\sum_{i+j=k}\binom{n}{i}_{q}\binom{m}{j}_{q}q^{j(m-i)}

\prod_{k=0}^{n-1}(1+q^{k}t)=\sum_{k=0}^{n}q^{\binom{k}{2}}\binom{n}{k}_{q}t^{k}

\binom{m}{r}_{q}=q^{r}\binom{m-1}{r}_{q}+\binom{m-1}{r-1}_{q}

7. איך כל זה מתקשר אלינו? נניח בה"כ שa_i חיוביים ועולים (זה משנה רק את הסימן של הביטוי). נגדיר f(q)=\frac{\prod_{i >j} q^{a_{i}}-q^{a_{j}}}{\prod_{i > j} q^{i}-q^{j}}. אם נראה שf פולינום עם מקדמים שלמים, אז בפרט

f(1) = \frac{\prod_{i>j} a_i - a_j}{\prod_{i>j} i-j}

יהיה שלם.

אז למה f פולינום? נכתוב f(q)=q^{\sum a_{j}-j}\prod\frac{q^{a_{i}-a_{j}}-1}{q^{i-j}-1}. שורשי f הם 0 ושורשי יחידה. מה הריבוי של 0? במונה הוא \sum a_j ובמכנה \sum j, ומכיוון שa_{j}\ge j+1, הריבוי במונה גובר על המכנה. כעת ניקח שורש יחידה מסדר r. הוא מופיע במכנה בריבוי 1 לכל i>j כך שi \equiv j \mod r. הוא מופיע במונה בריבוי 1 לכל i>j כך ש-a_i \equiv a_j \mod r. זה כבר מזכיר את הפיתרון הראשון! למעשה, יש לנו כאן את אותו החישוב. אם נסמן בx_i את כמות האיברים השווים לi \text{ mod } r, אז אנחנו רוצים למצוא את המינימום של \sum \binom{x_i}{2}, שמתקבל כאשר הx_i שווים או בהפרש 1, ובסוף לקבל שהמינימום מתקבל כאשר a_i = i.

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

למה הפולינום f בעל מקדמים שלמים? שוב הלמה של גאוס – בתור פולינום שהוא מנה של 2 פולינומים מתוקנים עם מקדמים שלמים, הוא חייב להיות גם כזה.

תרגיל 6: מצאו עוד q-אנלוגיות מגניבות בסגנון הזה.

תרגיל 7: הראו שאם a_i \text{mod} k מתפלג כמו i \text{mod} k, אז \prod_{i>j} \frac{\prod_{a_{i} \equiv a_{j} (k) }(a_{i}-a_{j}) } {\prod_{i \equiv j (k)} (i-j)} שלם. (רמז: הציבו שורש יחידה בf.)

תרגיל 8: הראו שהפולינומים הציקלוטומים לא מיוחדים, כלומר עבור סדרת פולינומים עם מקדמים שלמים \{T_n \}_{n\ge 1} מתקיים \frac{\prod_{d|a_{i}-a_{j}}T_{d}}{\prod_{d|i-j}T_{d}}\in\mathbb{Z}[x]. מה מקבלים כאשר T_n שווה לקבוע? מצאו עוד מקרים מעניינים.

—-

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

ביבליוגרפיה:

1. 3 דיונים מ-mathlinks: דיון א', ב', ג'

2. דיון מ-mathoverflow

3. An Integral Polynomial \ B. Sury

4. דיונים עם חברים

———

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

שבוע טוב!

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

אודות Ofir Gorodetsky

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

3 תגובות על מנה שלמה

  1. תום קלוורי הגיב:

    ממש מגניב!
    אהבתי מאוד את 5, 6, 7.
    6 נראה *ממש* כמו משפט האפסים הקומבינטורי, אבל לא הצלחתי להראות הוכחה מיידית ממנו. יש משהו בסגנון?

    • gorofir הגיב:

      6 מזכיר את משפט האפסים כי יש פולינום שמתאפס "מודולו 1" על תיבה, ולכן הוא זהותית 0 "מודולו 1". אני לא בטוח אבל שזה ניתן להכללה באותו אופן שאפשר להכליל את משפט האפסים מתיבה יפה (של מספרים עוקבים) לתיבה כללית. בפרט, אפשר לבנות פולינום ממעלה n שמקבל ערכים שלמים בn+1 נק' אבל הוא לא שלם בכל הנקודות. וגם אם יש איזושהי הכללה, אני לא בטוח שהיא אלגנטית. [לדוגמא, אפשר להסיק שהמקדמים של הפולינום רציונליים!]. עוד לא בדקתי את הנושא לעומק, אבל אפשר לנסות לבדוק בספר הבא:
      http://books.google.co.il/books?id=AlAluH5is6AC&printsec=frontcover&hl=iw&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false
      אגב, המשפט הזה הוא של אוסטרובסקי.

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

      נחמד לראות אותך כאן!

  2. פינגבאק: אי-שיוויון הממוצעים | One and One

להשאיר תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s