3 בעיות בגיאומטריה של פולינומים

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

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

בעיה ראשונה (1894, הילברט):

בהינתן קטע I=[a,b], האם אפשר למצוא סדרת פולינומים 0\neq p_n(x) \in \mathbb{Z}[x] (פולינומים שונים מאפס עם מקדמים שלמים) כך ש-\int_{a}^{b} p_n(x)^2 \, \mathrm{d} x שואף לאפס?
כלומר, האם הביטוי \int_{a}^{b} p(x)^2 \, \mathrm{d} x יכול להיות קטן כרצוננו כאשר p פולינום עם מקדמים שלמים שאינו פולינום האפס?

(תשובה: אם אורך הקטע I קטן מ-4, אז כן.)

בעיה שנייה (Müntz 1914, Szász 1916):

ממשפט ויירשטראס, ידוע שכל פונקציה רציפה על קטע I=[a,b] אפשר לקרב ע"י פולינום באופן מוצלח כרצוננו. במפורש, עבור פונקציה רציפה f יש סדרת פולינומים p_n(x) כך ש-\max_{x\in I} |f(x) - p_n(x)| שואף לאפס (מרחק זה ידוע גם כנורמת סופרמום ומסומן \| f-p \|_{\infty}).
אבל, מה קורה אם אנחנו לא מרשים כל פולינום? נגיד, מצטמצמים למרחב שנפרש ע"י המונומים \{x^{a_1}, x^{a_2}, \cdots \} (לדוגמא: a_i יכולה להיות סדרת הראשוניים: 2, 3, 5, …). מה קורה אז? האם המשפט נשאר נכון?

(תשובה: התשובה המלאה קצת מסובכת לניסוח, בינתיים ננסח מקרה פרטי.
אם נניח לשם הפשטות ש-a=0 וש-a_i טבעיים, אז בנורמת L^2 התנאי המספיק וההכרחי הוא התנאי האלגנטי הבא: הטור \sum \frac{1}{a_i} מתבדר.
בנורמת סופרמום מקבלים את אותו התנאי חוץ מזה שבנוסף דורשים ש-a_1=0, כלומר מוסיפים בכח את הפונקציות הקבועות.
את התשובה המלאה עם פחות הנחות – בהמשך.)

בעיה שלישית (2008, שאלה מתחרות SEEMOUS):

תהי f פונקציה ממשית רציפה על קטע היחידה [0,1] המקיימת שעבור k=0,1,\cdots,n-1:

\int_{0}^{1} f(x)x^k \, \mathrm{d} x=1

מה החסם התחתון על \int_{0}^{1} f(x)^2 \, \mathrm{d}x?

(תשובה: n^2.)

נפתור אותן בסדר כרונולוגי כי זה לא "ספרות זולה" פה.

בעיה 1 – הבעיה של הילברט

1. הקדמה

הבעיה של הילברט מסקרנת. ברור שאם p(x) הוא פולינום קבוע וקטן, נגיד p(x) = 10^{-100}, אני יכול לגרום לאינטגרל של p^2 להיות קטן כרצוני.
אבל מה קורה כשאני עובד רק עם פולינומים עם מקדמים שלמים, שזו קבוצה דיסקרטית?

כמו תמיד, כדאי לנסות מקרים פרטיים. אם עובדים עם הקטע [0,1] אפשר לקחת את הסדרה p_n(x) = x^n, כי האינטגרל של הריבוע הוא \frac{1}{1+2n}, ששואף לאפס. זה עובד גם עם הקטע [-1, 1].
אם עובדים עם הזזה שלמה של הקטע, נגיד [1,3], אפשר פשוט להזיז את הפולינומים: p_n(x) = (x-2)^n.

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

2. מפולינומים לתבניות ריבועיות

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

\langle f,g\rangle = \int_{a}^{b} f(x)g(x) \, \mathrm{d}x

היא מכפלה פנימית על מרחב הפולינומים הממשיים בקטע [a,b], שמשרה את הנורמה הבאה:

\| p(x) \| = \sqrt{\langle p, p \rangle} = \sqrt{\int_{a}^{b} p(x)^2 \, \mathrm{d}x}

שבדיוק אותה אנחנו מנסים למזער. אם אני מגביל את הפולינומים שלי למעלה d, כלומר מניח שאפשר לכתוב p(x) = a_0 + a_1x + \cdots + a_d x^d, אז הביטוי \int_{a}^{b} p(x)^2 \, \mathrm{d} x הוא תבנית ריבועית ב-d+1 המשתנים a_0,a_1,\cdots, a_d:

\int_{a}^{b} p(x)^2 \, \mathrm{d}x = \langle p, p \rangle = \langle \sum_{i=0}^{d} a_i x^i, \sum_{i=0}^{d} a_i x^i \rangle = \sum_{0\le i,j \le d} a_i a_j \langle x^i, x^j \rangle

ואם נסמן ב-X את המטריצה ה-(d+1) \times (d+1) שהאיבר ה-(i,j) שלה הוא \langle x^i, x^j \rangle, אז קיבלנו ש-

\int_{a}^{b} p(x)^2 \, \mathrm{d} x = \sum_{0 \le i,j \le d} a_i a_j X_{i,j}

וזו תבנית ריבועית לכל דבר ועניין. אם נסמן ב-m_d את המינימום של התבנית מעל השלמים, כלומר:

m_d = \min_{\vec{a} \in \mathbb{Z}^{d+1} \setminus \vec{0}} \sum_{0 \le i,j \le d} a_i a_j X_{i,j}

הבעיה של הילברט שואלת מתי \lim_{d \to \infty} m_d שווה 0? (הגבול בהכרח קיים כי הסדרה מונוטונית יורדת וחיובית.)

לא לכל תבנית ריבועית יש מינימום. לדוגמא, f(a_0, a_1) = a_0^2 - a_1^2 יכולה לקבל ערך קטן כרצוננו. עם זאת, התבנית שלנו, f(a_0, \cdots, a_d) = \sum_{i,j} a_i a_j X_{i,j}, שונה. מדובר בתבנית מוגדרת חיובית – אנחנו יודעים שהיא מייצגת נורמה על מרחב הפולינומים, ולכן אי-שלילית ומתאפסת רק כשוקטור המקדמים, \vec{a}, הוא וקטור האפס.
המשמעות של זה היא שהמטריצה הסימטרית X מוגדרת חיובית, כלומר: הערכים העצמיים שלה חיוביים.
העובדה שתבנית המוגדרת חיובית מיוצגת ע"י מטריצה מוגדרת חיובית מוכחת באופן יחסית ישיר- המטריצה לכסינה מעל הממשיים כי היא סימטרית, אז נעבוד בבסיס בו היא אלכסונית, ואז מקבלים תבנית אלכסונית: f(b_0, b_1, \cdots, b_d) = \sum_{i=0}^{d} \lambda_i b_i^2, כאשר ה-\{ \lambda_i \}_{i=0}^{d} הם הערכים העצמיים, וברור שאם אחד מהם שלילי התבנית יכולה לקבל ערכים שליליים, סתירה.

3. מתבניות ריבועיות לשריגים

אנחנו הולכים להמיר את הבעיה מבעיה על תבניות ריבועיות לבעיה על שריגים. אני אתן את המוטיבציה ואז אסביר איך מממשים אותה.
מטריצות מהצורה Y^T Y (כאשר Y הפיכה מסדר n \times n) הן סימטריות (כי (Y^T Y)^T = Y^T Y^{TT} = Y^TY) ומוגדרות חיובית:

\langle \vec{a}, Y^T Y \vec{a} \rangle = \langle Y\vec{a}, Y \vec{a} \rangle = \| Y \vec{a} \|^{2} \ge 0

מהשיוויון הנ"ל רואים שבעיית המינימיזציה של התבנית הריבועית המתאימה ל-Y^T Y שקולה לבעיית מינימיזציה של אורך הוקטור Y \vec{a}. הקבוצה Y \mathbb{Z}^{n} = \text{Span}_{\mathbb{Z}} \{ Ye_0, Ye_1, \cdots, Ye_{n-1} \} היא שריג (תת-חבורה דיסקרטית של \mathbb{R}^{n}) שנפרש ע"י העמודות של Y. מסתבר שאנחנו מחפשים את הוקטור הכי קצר בשריג הזה, וזו בעייה מפורסמת שיש כלים אלגוריתמים ותאורטיים לפתור אותה – "בעיית וקטור קצר בשריג".

עם זאת, לפני שאנחנו ממשיכים לדבר עליהם, נשאלת השאלה: האם בהכרח את המטריצה המוגדרת חיובית שלנו, X, אפשר לכתוב בצורה Y^T Y? התשובה היא חיובית. למעשה, אפשר לדרוש מ-Y להיות משולשית עליונה ואז מקבלים את "פירוק חולסקי" של X. לא נוכיח שתמיד אפשר למצוא פירוק כזה, אבל כן נחשב את הפירוק הזה עבור המטריצה שלנו.

נשים לך שהמטריצה X היא "מטריצת גרם". מטריצה נקראת מטריצה גרם אם יש סדרת וקטורים \{ v_i \} כך שבמקום ה-(i,j) במטריצה יש מכפלה פנימית בין שני הוקטורים v_i, v_j. במקרה שלנו, v_i = x^i.
(הערת העשרה, אפשר לדלג בקריאה ראשונה: מטריצות גרם מופיעות הרבה במתמטיקה, והדטרמיננטה שלהן מהווה אינווריאנט גיאומטרי של השריג הנפרש ע"י \{ v_i \} מעל השלמים. היא נקראת דיסקרימיננטה ונתקלים בה בין השאר בתורת המספרים האלגברית. בסיסים שונים של אותו מרחב פורשים, בהגדרה, את אותו המרחב, אבל עדיין אפשר לשאול איזה בסיסים "שמנים" יותר ע"י השוואת החבורה שהם פורשים כ-\mathbb{Z}-מודולים, כלומר ע"י השוואת הנפחים של המקבילונים היסודיים שלהם – וזו הדיסקרימיננטה.)

מטריצות גרם מוגדרות חיובית כאשר ה-\{ v_i \} בת"ל (כי הן מגיעות מנורמה, כמו שראינו – \langle \vec{a}, X\vec{a} \rangle היא הנורמה בריבוע של \sum a_i v_i). ננצל את המבנה שלהן כדי לפרק את X לצורה הדרושה.

תרגיל 1: הוכיחו את אי-שיוויון קושי-שוורץ באמצעות חישוב דטרמיננטה של מטריצת גרם מסדר 2 על 2. הוכיחו הכללות שלו באמצעות חישוב דומה למטריצות מסדר גבוה יותר.
תרגיל 2: הראו שכל מטריצה מוגדרת חיובית היא מטריצת גרם (את הכיוון השני ראינו).

אם היינו עובדים עם בסיס אורתונורמלי למרחב הפולינומים בקטע I = [a,b] (במקום עם הבסיס הסטנדרטי), התבנית הריבועית שלנו הייתה אלכסונית והיה קל יותר לבצע חישובים. מסתבר שמטריצות גרם של בסיסים שונים קשורות זו לזו ע"י פעולת "חפיפה" במטריצת המעבר:

משפט 1: יהיו \{ v_0, \cdots, v_d \}, \{ u_0, \cdots, u_d \} שני בסיסים למרחב d+1-מימדי. תהי A מטריצת המעבר בין הבסיסים, כלומר u_i = \sum_{k} a_{i,k} v_k. נסמן ב-G(w_0, \cdots, w_d) את מטריצת גרם המתאימה לסדרת וקטורים \{ w_i \}.
מתקיים:

G(u_0, \cdots, u_d) = A \cdot G(v_0, \cdots, v_d) \cdot A^T

הוכחה: יש דרכים טבעיות יותר לראות זאת, אבל אנחנו פשוט נחשב את האיבר ה-(i,j) של אגף ימין:

(A \cdot G(v_0, \cdots, v_d) \cdot A^T)_{i,j} = \sum_{k,k'} a_{i,k} \langle v_k, v_{k'} \rangle a_{j,k'} = \langle \sum_{k} a_{i,k} v_k , \sum_{k'} a_{j,k'} v_{k'} \rangle = \langle u_i, u_j \rangle

\blacksquare

זה אמנם משפט פשוט, אבל נשתמש בו בעקביות. בואו נעשה זאת עכשיו: אם נפעיל את תהליך גרם-שמידט על הוקטורים x^0, x^1, \cdots, x^d עם המכפלה הפנימית \langle f,g \rangle =\int_{a}^{b} f(x)g(x) \, \mathrm{d}x, נקבל סדרת פולינומים p_0, \cdots, p_d כך ש-G(p_0, \cdots, p_d) היא מטריצת הזהות I_{d+1}, ולפי המשפט היא מקושרת למטריצה המקורית X = G(x^0, \cdots, x^d) באופן הבא:

I_{d+1} = AXA^T \implies X = A^{-1}(A^{-1})^T

כאשר A היא מטריצת המעבר בין הבסיסים, שזה אומר ש-a_{i,j} היא המקדם של x^j ב-p_i(x). וכך, ע"י בחירת בסיס אורתונורמלי, הבענו את מטריצת גרם X בצורה Y^T Y, כאשר Y = (A^{-1})^T. השריג בו אנחנו צריכים למצוא את הוקטור הקצר ביותר הוא השריג שנפרש ע"י העמודות של Y, כלומר ע"י השורות של A^{-1}.

הערה רלוונטית: אם \{p_0, \cdots, p_d \} בסיס אורתוגונלי ל-\{ x^0, x^1, \cdots, x^d \} אבל לאו דווקא אורתונורמלי, מתקיים ש-G(p_0, \cdots, p_d) אלכסונית ולכן מקבלים את השיוויון X = (A^{-1}) D (A^{-1})^T כאשר D מטריצה אלכסונית שאלכסונה מכיל את ריבוע הנורמות של \{p_i \}.

4. משריגים לדטרמיננטות

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

לא נוכיח את המשפט הכללי של מינקובסקי, אלא את המקרה הפרטי הרלוונטי לנו. לפני שנעשה זאת, נשים לב שאנחנו מצפים שהחסם לאורך הוקטור הקצר בשריג יהיה מונוטוני עולה בדטרמיננטה, ומשיקולי יחידוֹת יהיה תלוי בדטרמיננטה בחזקת 1 חלקי המימד. המשפט מאושש זאת, אנחנו נראה איך ממנו נובע שבשריג L במרחב n-מימדי ועם נפח d(L) יש וקטור באורך קצר מ-O(\sqrt{n} d(L)^{1/n}).

משפט 2 (מקרה פרטי של משפט מינקובסקי): יהי L שריג ב-\mathbb{R}^n מנפח d(L).  אם S הוא כדור ברדיוס R סביב הראשית עם נפח גדול מ-2^n d(L), אז הוא בהכרח מכיל וקטור מהשריג L שאינו וקטור האפס.

הוכחה: הרעיון הוא שובך יונים גיאומטרי. נסמן ב-M את אחד המקבילונים היסודיים של השריג, לדוגמא M = \{ Ax | x \in [0,1)^n \}. נסמן ב-2M את המקבילון המתקבל ממתיחת כל הוקטורים ב-M פי 2 – זה המקבילון של השריג 2L.
כל וקטור במרחב אפשר להזיז בצורה יחידה ע"י וקטור מהשריג 2L כך שהוא יהיה במקבילון 2M. תהי f: S \to 2M ההעתקה (היחידה) שמעבירה וקטור בכדור לוקטור במקבילון ע"י הזזה בוקטור מ-2L . זו העתקה שמשמרת נפחים באופן מקומי (מקומית היא הזזה).
בגלל שהנפח של 2M הוא 2^n d(L), כלומר קטן מנפח הכדור S, נובע שההעתקה f אינה חח"ע. על כן f(\vec{x_0}) = f(\vec{x_1}) כאשר \vec{x_0}, \vec{x_1} נקודות שונות בכדור.
נובע שההפרש \vec{x_0} - \vec{x_1} הוא וקטור בשריג 2L, כלומר \frac{\vec{x_0} - \vec{x_1}}{2} הוא וקטור בשריג L שאינו וקטור האפס. הוא נמצא בכדור S, למשל ע"י אי-שיוויון המשולש:

\| \frac{\vec{x_0}-\vec{x_1}}{2} \| \le \frac{\| \vec{x_0} \| + \| \vec{x_1} \| }{2} \le \frac{R+R}{2} = R

סיימנו. \blacksquare

אבל איך מכאן אנחנו מסיקים על אורך הוקטור הקצר? אם יש וקטור שריג לא טריוויאלי בכדור עם רדיוס R סביב הראשית, נובע שיש וקטור בשריג באורך R \ge.
נפח של כדור עם רדיוס R במרחב n-מימדי אסימפטוטי ל-\frac{1}{\sqrt{\pi n}} (\sqrt{\frac{2\pi e}{n}} R)^n (ראו כאן). אנחנו דורשים שהנפח יהיה גדול מ-2^n d(L). אילוץ זה מראה, לאחר שלוקחים שורש n-י, שאפשר לבחור R = d(L)^{1/n} \sqrt{\frac{2n}{\pi e}} (1+o(1)).

מסקנה: בשריג L מנפח d(L) יש וקטור באורך קצר מ-O(\sqrt{n} d(L)^{1/n}).

נחזור לבעיה שלנו. לכל d יש לנו תבנית ריבועית שמיוצגת ע"י מטריצת גרם X_d, שבתורה נותנת שריג L_d (שמתקבל מגרם-שמידט על x^0, x^1, \cdots, x^d).
אנחנו מתעניינים באורך הוקטור הקצר ביותר בו (מסומן \sqrt{m_d}), ואנחנו תוהים האם \lim_{d \to \infty} m_d = 0. ע"י משפט מינקובסקי אפשר לחסום את \sqrt{m_d} מלמעלה ע"י O(\sqrt{d+1}d(L_d)^{\frac{1}{d+1}}).
ניזכר שכתבנו X=A^{-1}(A^{-1})^T, ואם לוקחים דטרמיננטה לשני הצדדים מקבלים ש-d(L_d) = \sqrt{\det X_d}, כלומר השאלה נהיית הבעיה החישובית הבאה:

\lim_{d \to \infty} \sqrt{d} \det(X_d)^{\frac{1}{2(d+1)}}

כלומר עשינו רדוקציה לחישוב הדטרמיננטה של מטריצת גרם שבמקום ה-(i,j) כתוב בה:

\langle x^i, x^j \rangle = \frac{b^{i+j+1} - a^{i+j+1}}{i+j+1}

5. פולינומי לז'נדר וחישוב הדטרמיננטה

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

יש הרבה דרכים לחשב דטרמיננטה זו, אבל נלך כמעט אחד לאחד בדרכו של הילברט.
נסמן ב-D_{a,b} את הדטרמיננטה הנ"ל (כאשר [a,b] הקטע הרלוונטי). הילברט קישר בין הדטרמיננטות השונות באמצעות טריק גאוני. בין השאר, הוא הראה שהדטרמיננטה תלויה רק בהפרש b-a.
איך רואים זאת? כרגע, כל איבר במטריצה הוא אינטגרל לפי משתנה x. אנחנו נחליט שבכל שורה יש אינטגרציה לפי משתנה אחר, כלומר, במקום ה-(i,j) כתוב \langle x_i^i, x_i^j \rangle = \int_{a}^{b} x_i^{i+j} \, \mathrm{d}x_i. כעת ניקח דטרמיננטה ונקבל אינטגרל ב-(d+1) המשתנים x_0, \cdots, x_d:

\int_{a}^{b} \cdots \int_{a}^{b} \sum_{\sigma \in S_{d+1}} \prod_{i=0}^{d} x_i^{i+\sigma(i)}(-1)^{\sigma} \, \mathrm{d}x_0 \mathrm{d}x_1 \cdots \mathrm{d}x_{d}

(לדקדקנים – ההצדקה נובעת ממשפט פוביני.) נשים לב שהאינטגרנד הוא בעצם (\prod_{i=0}^{d} x_i^{i}) ( \prod_{i=0}^{d} x_i^{\sigma(i)}(-1)^{\sigma}), כאשר הגורם השני אמור להיות מוכר לכם: זו הדטרמיננטה המפורשת של מטריצת ונדרמונטה (מטריצה שהאיבר ה-(i,j) שלה הוא x_i^j), שידועה גם בתור המכפלה \prod_{i>j} (x_i - x_j).
לכן האינטגרנד הוא:

\prod_{i=0}^{d} {x_i}^{i} \prod_{i>j} (x_i - x_j)

זה עדיין לא נוח מספיק, אז נמשיך. מה קורה כשמשנים את סדר המשתנים? האינטגרל לא אמור להשתנות, אבל האינטגרנד כן. אם x_i מוחלף ב-x_{\sigma'(i)}, אז המכפלה הראשונה נהיית \prod_{i=0}^{d} x_{\sigma'(i)}^{i}, והמכפלה השנייה נכפלת ב-(-1)^{\sigma'}.
נעשה מיצוע על פני \sigma' \in S_{d+1} ונקבל שאפשר להחליף את האינטגרנד ב:

\frac{1}{(d+1)!} (\sum_{\sigma' \in S_{d+1}} \prod_{i=0}^{d} x_{\sigma'(i)}^{i} (-1)^{\sigma'}) \prod_{i>j} (x_i - x_j)

והופ! שוב מופיעה הדטרמיננטה של מטריצת ונדרמונטדה. על כן, האינטגרל הרלוונטי הוא:

\frac{1}{(d+1)!} \int_{a}^{b} \cdots \int_{a}^{b} (\prod_{i>j} (x_i - x_j) )^2 \, \mathrm{d}x_0 \mathrm{d}x_1 \cdots \mathrm{d}x_{d}

מכאן רואים שאכן התלות היחידה היא ב-b-a. קול! ע"י שינוי משתנים לינארי רואים שלמעשה:

D_{a,b} = D_{0,1} (b-a)^{(d+1)^2}

לכן עשינו רדוקציה לחישוב \int_{[0,1]^{d+1}} (\prod_{i>j} (x_i - x_j) )^2 \, \mathrm{d}x_0 \mathrm{d}x_1 \cdots \mathrm{d}x_{d}. אינטגרל זה לא פשוט לחישוב, והדרך היחידה שאני מכיר לחשבו היא להוסיף לו פרמטרים ולקבל את מה שנקרא אינטגרל סלברג, שהוגדר, נחקר וחושב רק ב-1944 – אחרי המאמר של היבלרט (בהמשך אתן קישור להוכחה שלו).
בינתיים נסתכל על המטריצה שמתאימה לקטע [0,1], כי עכשיו התאמצנו להראות שמספיק לחקור אותה. במקום ה-(i,j) רשום בה \int_{0}^{1} x^{i+j} \, \mathrm{d}x = \frac{1}{i+j+1}. למטריצה זו קוראים "מטריצת הילברט" (משום שהופיעה לראשונה במאמר של הילברט שאנו דנים בו כרגע…) והיא מסומנת H. במקרה החמש-מימדי, לדוגמא, היא נראית כך: 3010a8e88d2fa182f42d0507d3b608b6 היא מקיימת הרבה תכונות יפות, מעבר להיותה מטריצת גרם:

  • זו "מטריצת הנקל" (Henkel) – כלומר האיבר ה-(i,j) תלוי רק בסכום i+j.
  • זו "מטריצת קושי" (Cauchy) – כלומר יש סדרות סופיות a_i, b_j כך שהאיבר ה-(i,j) הוא (a_i+b_j)^{-1}. נדבר על מטריצות כאלו בפרק הבא – מסתבר שקל לחשב להן דטרמיננטה.
  • הדטרמיננטה שלה היא אחד חלקי מספר טבעי. יתר על כן, ההופכית שלה מורכבת ממספר שלמים – נסביר זאת בהמשך.
  • משתמשים במטריצה הזו כ-"test case" כשבודקים אלגוריתמים באנליזה נומרית. זה קורה בגלל שלהופכית שלה יש ערכים שלמים גדולים, ולכן היא "לא יציבה" – אם מנסים לפתור את המערכת H \vec{x}=\vec{y}, ויש איזשהי טעות קטנה ב-\vec{y}, נסמנה \Delta, שנובעת לדוגמא ממגבלות הדיוק של המחשב, זה גורר שגיאה של H^{-1} \Delta בוקטור הפיתרון. המקדמים הגדולים של H^{-1} גורמים לשגיאה להיות לא פרופורציונית. אפשר לקרוא על כך עוד כאן.

למרות שכאמור יש נוסחה לדטרמיננטה של מטריצת קושי, הילברט סיים את ההוכחה דווקא באמצעות הכרותו עם פולינומי לז'נדר, שנחקרו רבות במאה ה-19.
פולינומי לז'נדר הם בסיס אורתוגונלי לפולינומים בקטע [-1,1] עם המכפלה הפנימית הסטנדרטית (אינטגרל של המכפלה על הקטע). "פולינומי לז'נדר המוזזים" מהווים בסיס אורתוגונלי לפולינומים בקטע [0,1] ומתקבלים מפולינומי לז'נדר המקוריים ע"י שינוי משתנים לינארי (x \mapsto 2x-1).
יתר על כן, יש להם מקדמים שלמים:

p_n(x) = (-1)^n \sum_{k=0}^{n} \binom{n}{k} \binom{n+k}{k} (-x)^k

והנורמות הן \| p_n \|^2 = \frac{1}{2n+1}. איך הגיעו לנוסחה הזו, למה הם אורתוגונלים ואיך מחשבים את הנורמה – על זאת נשיב רק בסוף הפוסט. בינתיים קחו זאת כעובדה (עד שנגיע להוכחה אתם מזומנים לבדוק את הנכונות באופן אמפירי או להעז ולהוכיח בעצמכם).

הראנו קודם שאם p_0, \cdots, p_d בסיס אורתוגונלי לפולינומים עד מעלה d בקטע [0,1], אז H=(A^{-1}) D(A^{-1})^T, כאשר A מטריצת המקדמים של \{ p_i \} ו-D אלכסונית כך ש-D_{i,i} = \langle p_i, p_i \rangle. נובע ש-H^{-1} היא A^T D^{-1} A. אם משתמשים בפולינומי לז'נדר המוזזים, נובע ש-H^{-1} מכפלה של 3 מטריצות עם מקדמים שלמים. על כן ההופכית בעלת מקדמים שלמים בעצמה, ובפרט הדטרמיננטה של H היא הופכית של מספר טבעי.
איך משתמשים בכל זה כדי לחשב את הדטרמיננטה? היא יוצאת 1 חלקי:

\det(H)^{-1} = \det(A^T) \det(D^{-1}) \det(A) = \det(A)^2 / \det(D)

המטריצה D אלכסונית ולכן הדטרמיננטה שלה היא פשוט \prod_{i=0}^{d} \frac{1}{2i+1}.
המטריצה A משולשית, והדטרמיננטה שלה היא מכפלת האלכסון, שפשוט מכיל את המקדמים המובילים של פולינומי לז'נדר המוזזים.
מהנוסחה שנתנו מקודם רואים שהמקדם המוביל של p_n הוא המקדם הבינומי \binom{2n}{n}. על כן הדטרמיננטה היא \prod_{i=0}^{d} \binom{2i}{i}.
יוצא שהדטרמיננטה של \det H היא 1 חלקי:

\prod_{i=0}^{d} \binom{2i}{i}^2(2i+1)

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

\binom{2i}{i}^2(2i+1)= (\frac{4^i}{\sqrt{\pi i}} (1+O(\frac{1}{i}))^2 (2i+1) = \frac{2}{\pi} 16^i (1+O(\frac{1}{i}))

ואם מכפילים את זה על פני i=0,1,\cdots,d מקבלים:

(\frac{2}{\pi})^{d+1} 4^{d(d+1)}(d+1)^{O(1)} = \frac{4^{(d+1)^2}}{(2\pi)^{d+1}} (d+1)^{O(1)}

הקשר D_{a,b} = D_{0,1} (b-a)^{(d+1)^2} מראה ש-

D_{a,b} = (\frac{b-a}{4})^{(d+1)^2}(2\pi)^{d+1}(d+1)^{O(1)}

ניזכר למה אנחנו בכלל מחשבים את הדטרמיננטה – אנחנו משתמשים במשפט מינקובסקי כדי לחסום את הוקטור הקצר בשריג ע"י O(\sqrt{d} D_{a,b}^{\frac{1}{2(d+1)}}). נציב את הדטרמיננטה ונקבל O(\sqrt{2\pi d (\frac{b-a}{4})^{d+1}}). הביטוי הזה שואף לאפס כאשר b-a < 4, מש"ל. \blacksquare

לקריאה נוספת:

  • אפשר לקרוא על אינטגרל סלברג וחישובו בעמודים 402-406 בספר הזה בגוגל בוקס. אל תזלזלו באינטגרל הזה- הוא פתר בעיות שהיו פתוחות 15 שנים.
  • אפשר לקרוא עוד על מטריצת הילברט ותכונותיה במאמר הזה משנת 1983.
  • יש הרצאת וידאו מעולה של דורון ציילברגר על חישוב הדטרמיננטה של מטריצת הילברט. הוא מדבר על טריק האינטגרציה שהשתמשנו בו ועל אינטגרל סלברג, ראו כאן החל מדקה 21.
  • המאמר המקורי של הילברט (זהירות – גרמנית!).

בעיה 2 – משפט Müntz-Szász

1. הקדמה

תהי \{ a_i \}_{i \ge 1} סדרה של מספרים ממשים אי-שליליים שונים.
המשפט אומר שאם עובדים בנורמת L^2, כל פונקציה רציפה בקטע [0,a] אפשר לקרב באופן קרוב כרצוננו ע"י קומבינציה לינארית של המונומים \{ x^{a_1}, x^{a_2}, \cdots \} אמ"מ הטור \sum \frac{1}{a_i} מתבדר.
אם מדובר בנורמת סופרמום לעומת זאת, לתנאי הנ"ל מתווספים התנאים a_1=0 ו-\inf a_i >0.

לדוגמא, בגלל שטור ההופכיים של הראשוניים מתבדר, אפשר לקרב כל פונקציה רציפה ב-[0,a] בעזרת המונומים \{ x^0, x^2, x^3, x^5, x^7, x^{11}, x^{13}, \cdots \}.
מנגד, בגלל שטור ההופכיים של הריבועים מתכנס (\sum_{i} \frac{1}{i^2} < \infty), נובע שלא כל פונקציה רציפה אפשר לקרב בעזרת \{ x^0, x^1, x^4, x^9, x^{16}, \cdots \}.

בתרגיל 5 נכליל את התוצאה מעט למקרה ש-a_i יהיו שליליים.

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

2. משפט הקירוב של ויירשטראס

לפני שנדבר על משפט זה בהרחבה, ניזכר במקרה פרטי שלו והוא a_i = i-1, שבעצם אומר שכל פונקציה רציפה אפשר לקרב ע"י פולינומים. משפט זה נקרא "משפט הקירוב של ויירשטראס", ויש לו הוכחה הסתברותית אלגנטית. אציג את הרעיונות המרכזיים בה ואתם תשלימו את החורים. לשם הנוחות נניח שאנחנו עובדים בקטע [0,1].

לכל x\in [0,1] ולכל n טבעי נגדיר את המשתנה המקרי הבא:

R_{x,n} = \frac{\text{Binomial}(n,x)}{n}

זה ממוצע של n ניסויי ברנולי שכל אחד מצליח בסיכוי x. התוחלת שלו היא x, וכש-n \to \infty השונות שואפת לאפס.
אם משתמשים באי-שיוויון צ'בישב, אפשר למעשה לראות ש-R_{x,n} \to x בהסתברות ובאופן אחיד ב-x, כלומר:

\forall \delta>0: \lim_{n\to \infty} \sup_{x \in [0,1]} P(|R_{x,n} - x| > \delta) = 0

שימוש ברציפות במ"ש של f בקטע הסגור [0,1] מראה שאותה טענה נכונה לגבי המשתנים f(R_{x,n}) ששואפים בהסתברות ל-f(x):

\forall \varepsilon>0: \lim_{n\to \infty} \sup_{x \in [0,1]} P(|f(R_{x,n}) - f(x)| > \varepsilon) = 0

שימוש בחסימות של f בקטע הסגור [0,1] מראה ש-

\lim_{n\to \infty} \sup_{x \in [0,1]} E|f(R_{x,n}) - f(x)| = 0

לסיום, מאי-שיוויון המשולש מקבלים שסדרת הפונקציות Ef(R_{x,n}) שואפות במ"ש ל-Ef(x) = f(x). אבל סדרה זו היא סדרת פולינומים ב-x:

Ef(R_{x,n}) = \sum_{i=0}^{n} \binom{n}{i} x^i (1-x)^{n-i} f(\frac{i}{n})

מש"ל. \blacksquare

3. הטלה על תת-מרחב והקשר למטריצות גרם

ניגש חזרה לבעיה שלנו. נעבוד, בתור התחלה, באותו מרחב שעבדנו בו בבעיה של הילברט: מרחב המכפלה הפנימית L^2([0, a]). אנחנו רוצים לדעת האם כל פונקציה רציפה f במרחב שלנו נמצאת בסגור של תת-המרחב שנפרש ע"י \{ x^{a_i} \}_{i \ge 1}, נסמנו V.
קשה לעבוד עם מרחבים אינסוף-מימדיים, אז נעבוד עם קירובים. נסמן ב-V_d את תת-המרחב \text{Span}\{ x^{a_1}, x^{a_2}, \cdots, x^{a_d} \}. תהי f פונקציה רציפה ב-[0,a]. אנחנו נחשב את ההטלה p_d(f) של f על V_d, כלומר: את הוקטור ב-V_d שהמרחק שלו מ-f מינימלי (כאשר במרחק הכוונה: נורמת ההפרש).

הרעיון הטבעי למציאת וקטור כזה הוא למזער את הפונקציה f(\lambda_1, \cdots, \lambda_d) = \| f-\sum_{i=1}^{d} \lambda_i x^{a_i} \|^2, שהיא סה"כ פונקציה ריבועית. אבל אנחנו נתחמק מכך באמצעות האבחנה הגיאומטרית הבאה:

משפט 3: יהי U מרחב מכפלה פנימית מעל הממשיים. יהי V תת-מרחב שלו ממימד סופי. יהי u \in U.
הוקטור u' \in V הוא ההטלה של u על V אמ"מ u'-u מאונך לכל איברי V, כלומר:

\forall v\in V: \langle u'-u, v \rangle = 0

הוכחה: אם \langle u' -u, v \rangle \neq 0, אני טוען שהזזה קטנה של  u' בכפולה של v תיתן וקטור קרוב יותר ל-u מאשר u'. במילים אחרות, אני טוען שיש פיתרון \lambda לאי-שיוויון הבא:

\| (u'+\lambda v)- u \| < \| u' -u\|

נעלה בריבוע ונשתמש בתכונות של מכפלה פנימית, ונקבל שזה שקול ל:

\lambda^2 \|v \|^2 + 2\lambda \langle v, u'-u\rangle < 0

אם \langle v, u'-u \rangle חיובי, ניקח \lambda שלילי וקטן. אחרת, ניקח \lambda חיובי וקטן. \blacksquare

תרגיל 3: הוכיחו את אותו המשפט למרחב מכפלה פנימית מעל המרוכבים.

מה אנחנו למדים מהמשפט? שכדי לחשב את ההטלה \vec{y} של וקטור \vec{x} על תת-מרחב \text{Span}\{v_1, \cdots, v_n \} צריך לפתור את מערכת המשוואות הבאה:

\forall 1 \le i \le n: \langle \vec{y}-\vec{x}, v_i \rangle = 0

אם נציב \vec{y} = \sum_{i=1}^{d} \lambda_i v_i זה נהייה:

\sum_{j=1}^{n} \lambda_j \langle v_i, v_j \rangle = \langle x, v_i \rangle

המטריצה שמייצגת מערכת זו היא מטריצת גרם – G(v_1, \cdots, v_n). אפשר לפתור את המערכת באלגנטיות. לדוגמא, ע"י כלל קרמר אפשר להראות שכל \lambda_j היא מנה של דטרמיננטות של מטריצות גרם.
אבל אנחנו לא באמת רוצים לפתור את המערכת – אנחנו רק רוצים את המרחק בין הוקטור המקורי להטלה שלו! אם נסמנו \text{dist}, הוא מקיים:

\text{dist}^2 = \| \vec{x} - \vec{y} \|^2 = \langle \vec{x}-\vec{y}, \vec{x} \rangle - \langle \vec{x} - \vec{y}, \vec{y} \rangle

מהמשפט שהוכחנו זה עתה, המחוסר מתאפס ונשאר רק עם המחובר. נציב \vec{y} = \sum_{i=1}^{d} \lambda_i v_i ונקבל את המשוואה הבאה:

\| \vec{x} \|^2 - \text{dist}^2 = \sum_{i=1}^{d} \lambda_i \langle v_i, \vec{x} \rangle

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

\begin{bmatrix} \langle v_1, v_1 \rangle & \cdots & \langle v_n, v_1 \rangle & \langle x, v_1 \rangle \\ \langle v_1, v_2 \rangle & \cdots & \langle v_n, v_2 \rangle & \langle x, v_2 \rangle \\ \cdots & \cdots & \cdots & \cdots \\ \langle v_1, v_n \rangle & \cdots & \langle v_n, v_n \rangle & \langle x, v_n \rangle \\ \langle v_1, x \rangle & \cdots & \langle v_n, x \rangle & \| x \|^2 -\text{dist}^2 \end{bmatrix}

בפרט הדטרמיננטה שלה היא 0. נשתמש במוליטי-לינאריות של הדטרמיננטה ונקבל את השיוויון הבא:

\det \begin{bmatrix} \langle v_1, v_1 \rangle & \cdots & \langle v_n, v_1 \rangle & \langle x, v_1 \rangle \\ \langle v_1, v_2 \rangle & \cdots & \langle v_n, v_2 \rangle & \langle x, v_2 \rangle \\ \cdots & \cdots & \cdots & \cdots \\ \langle v_1, v_n \rangle & \cdots & \langle v_n, v_n \rangle & \langle x, v_n \rangle \\ \langle v_1, x \rangle & \cdots & \langle v_n, x \rangle & \langle x, x \rangle \end{bmatrix} = \det \begin{bmatrix} \langle v_1, v_1 \rangle & \cdots & \langle v_n, v_1 \rangle & 0 \\ \langle v_1, v_2 \rangle & \cdots & \langle v_n, v_2 \rangle & 0 \\ \cdots & \cdots & \cdots & \cdots \\ \langle v_1, v_n \rangle & \cdots & \langle v_n, v_n \rangle & 0 \\ \langle v_1, x \rangle & \cdots & \langle v_n, x \rangle & \text{dist}^2 \end{bmatrix}

כלומר:

\text{dist}^2 = \frac{\det G(\vec{x}, v_1, \cdots, v_n)}{\det G(v_1, \cdots, v_n)}

איזו תוצאה אלגנטית!

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

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

\lim_{n \to \infty} \frac{\det G(f, x^{a_1}, \cdots, x^{a_n})}{\det G(x^{a_1}, \cdots, x^{a_n})}

ואנחנו רוצים שהוא יהיה שווה 0, כי אז זה אומר ש-f נמצאת בסגור של V (כי נובע ש-f היא הגבול ש ההטלות p_d(f) שנמצאות ב-V). ממשפט ויירשטראס, אנחנו יודעים שכל פונקציה רציפה אפשר לקרב ע"י פולינומים קרוב כרצוננו (בנורמת סופרמום ולכן גם בנורמת L^2). לכן, אם נראה שכל מונום f(x) = x^m נמצא בסגור של V, נסיים – זה אומר שהסגור מכיל את כל הפולינומים, ובגלל שכל פונקציה רציפה היא גבול של פולינומים, נובע שהסגור מכיל את כל הפונקציות הרציפות.

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

\forall m \in \mathbb{N}_{0}: \lim_{n \to \infty} \frac{\det G(x^m, x^{a_1}, \cdots, x^{a_n})}{\det G(x^{a_1}, \cdots, x^{a_n})} = 0

אנחנו עובדים בקטע [0,a]. ע"י שינוי משתנים x \mapsto \frac{x}{a} אפשר להניח ש-a=1. כעת המטריצות בנוסחה הנ"ל נהיות "מטריצות קושי". לשם הנוחות נסמן m = a_0.

G(x^{a_1}, \cdots, x^{a_n})_{i,j} = \langle x^{a_i}, x^{a_j} \rangle = \int_{0}^{1} x^{a_i + a_j} \, \mathrm{d}x = \frac{1}{a_i + a_j + 1}

G(x^{a_1}, \cdots, x^{a_n})_{i,j} = \langle x^{a_i}, x^{a_j} \rangle = \int_{0}^{1} x^{a_i + a_j} \, \mathrm{d}x = \frac{1}{a_i + a_j + 1}

(במטריצה הראשונה האינדקסים הם החל מ-0 ובשנייה החל מ-1.)
כזכור, מטריצת קושי היא מטריצה שאפשר לייצג את האיבר ה-(i,j) שלה ע"י \frac{1}{x_i + y_j}. במקרה שלנו, x_i = a_i, y_i = a_i+1.

4. חישוב דטרמיננטה של מטריצת קושי

משפט 4: תהי D_m דטרמיננטה של מטריצה מסדר m \times m שהאיבר ה-(i,j) שלהם הוא \frac{1}{a_i + b_j}. אזי:

D_m = \prod_{i,j=1}^{m} (a_i+b_j)^{-1} \prod_{i<j} (a_i-a_j)(b_i-b_j)

הוכחה: נחשב דטרמיננטה למטריצה לפי ההגדרה (סכום של m! מכפלות). מקבלים פונקציה רציונלית גדולה והומוגנית ממעלה -m.

המכנה שלה הוא C_m = \prod_{i,j = 1}^{m} (a_i + b_j), שזה פולינום ממעלה m^2. על כן המונה שלה ממעלה m^2-m.
אם a_i = a_{i'} אז יש 2 שורות שוות במטריצה ולכן הדטרמיננטה מתאפסת. כנ"ל אם b_j = b_{j'}. על כן המונה של הפונקציה הרציונלית מתחלק ב-

A_m \cdot B_m = \prod_{1 \le i <j \le m} (a_i- a_j) \prod_{1 \le i <j \le m} (b_i - b_j)

מכפלה זו היא ממעלה m^2-m – בדיוק מעלת המונה – ונובע ש-D_m = \frac{A_m B_m}{C_m} k_m כאשר k_m קבוע שתלוי רק ב-m.
במקרה המנוון m=1 רואים ש-k_1=1. אנחנו רוצים להראות שתמיד k_m=1.

אם נכפיל את השורה האחרונה של המטריצה ב-a_m ונשאיף את a_m לאינסוף, נקבל שהשורה האחרונה שואפת לוקטור אחדות. אם משאיפים את b_m לאינסוף (אבל יותר לאט מ-a_m) מקבלים שהעמודה האחרונה שואפת לאפסים (חוץ מהאיבר האחרון שהוא 1).
נפתח את הדטרמיננטה לפי עמודה זו ונקבל ש-a_m D_m שואף ל-D_{m-1}, כלומר \frac{a_m D_m}{D_{m-1}} \to 1 כאשר a_m, b_m \to \infty.
נציב את הנוסחה D_m = \frac{A_m B_m}{C_m} k_m, נצמצם גורמים משותפים ונקבל k_m = k_{m-1}. \blacksquare

דוגמא: אם a_i=i, b_j=j-1 מקבלים את מטריצת הילברט, והדטרמיננטה יוצאת:

\frac{\prod_{1 \le i<j\le m} (i-j)^2}{\prod_{1 \le i,j \le m} (i+j-1)}

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

נחזור למקרה שלנו. אנחנו רוצים לחשב את המנה הבאה:

\frac{\det G(x^{a_0}, x^{a_1}, \cdots, x^{a_n})}{\det G(x^{a_1}, \cdots, x^{a_n})}

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

\frac{1}{2a_0 + 1} \prod_{j=1}^{n} (\frac{a_0 - a_j}{a_0 + a_j + 1})^2

וזה הביטוי שאנחנו רוצים שישאף לאפס לכל a_0 טבעי (כולל 0). תבדקו שלא טעיתי בחישוב, עצלנים!

5. אסימפטוטיקה והוכחת המשפט עבור L^2

אנחנו רוצים שהמכפלה הנ"ל תשאף לאפס. נניח בינתיים, לשם הפשטות, ש-a_k אי-שליליים (אבל לאו דווקא שלמים). הגורם \frac{1}{2a_0 + 1} לא משפיע על התכנסות לאפס, לכן מספיק ש-

\prod_{j=1}^{n} (\frac{a_0 - a_j}{a_0 + a_j + 1})^2 = \prod_{j=1}^{n} (1 - \frac{2a_0 + 1}{a_j + a_0 + 1})^2

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

יש כלל אצבע (שגוי!) שאומר שהמכפלה \prod(1-b_i) שואפת לאפס אמ"מ הטור \sum b_i מתבדר לאינסוף. זה לא מדויק, אבל אם זה כן היה נכון היינו מסיימים את השאלה בקלות (כזכור, אנחנו צריכים להגיע לתנאי ש-\sum \frac{1}{a_i} מתבדר). נוכיח גרסה נכונה של כלל זה.

יש 2 מקרים:

א': אם ל-a_j יש גבול חלקי סופי, אז 1 - \frac{2a_0 + 1}{a_j + a_0 + 1} בעלת גבול חלקי קטן מ-1 בערך מוחלט ולכן המכפלה מתכנסת לאפס. בנוסף, הטור \sum \frac{1}{a_j} מתבדר (האיבר הכללי לא שואף לאפס) וסיימנו. זה אמנם מקרה קל אבל זה לא אומר שאינו מגניב.

ב': אם a_j שואף לאינסוף. מפתה להחליף את 1 - \frac{2a_0 + 1}{a_j + a_0 + 1} בקירוב e^{- \frac{2a_0 + 1}{a_j + a_0 + 1}} (כי e^x \sim 1+x עבור x-ים קטנים) ולכאורה לקבל את כלל האצבע. אבל זה לא ריגורוזי. איך כן עושים זאת ריגורוזית? נשים לב לשלוש עובדות:

  • החל מאיזשהו j\frac{2a_0 + 1}{a_j + a_0 + 1} \in (0,1) כי a_j שואף לאינסוף.
  • e^{-\frac{x}{1-x}} \le 1-x \le e^{-x} לכל x\in (0,1).
  • אם b_n \to 0 אז הטור \sum b_n מתכנס אמ"מ הטור \sum \frac{b_n}{1-b_n} מתכנס.

שימוש בעובדות אלו, בחוקי חזקות ובכלל הסנדוויץ' מראה שהמכפלה מתכנסת לאפס אמ"מ הטור \sum_{j} \frac{2a_0 + 1}{a_j + a_0 + 1} מתבדר, כלומר \sum_{j} \frac{1}{a_j} מתבדר. מש"ל. \blacksquare

תרגיל 5: קודם הנחנו ש-a_k סדרה אי-שלילית. אם נניח במקום את ההנחה החלשה יותר a_k > -\frac{1}{2}, הראו שהתנאי ההכרחי והמספיק נהיה: \sum_{a_k > 0} \frac{1}{a_k} מתבדר או \sum_{a_k \le 0} (a_k + \frac{1}{2}) מתבדר.

6. מנורמת L^2 לנורמת סופרמום

הראנו מה התנאי המספיק והכרחי לכך שאפשר לקרב (בנורמת L^2) כל פולינום ב-[0,a] ע"י אוסף מסוים של מונומים ולכן גם כל פונקציה רציפה (לפי משפט ויירשטראס).
נסביר איך אפשר לשנות במעט את ההוכחה כדי לקבל תנאי דומה לנורמת סופרמום, כאשר השינוי העיקרי הוא שיתווסף התנאי ש-x^0 הוא אחד המונומים.
ומדוע? נניח ש-a_i סדרה חיובית של מעריכים שלא מכילה את 0. בגלל ש-x^{a_i} מתאפס באפס נובע שכל פולינום ב-\text{Span}\{x^{a_1}, x^{a_2}, \cdots \} מתאפס באפס. גבול במידה שווה של פולינומים כאלה חייב להתאפס באפס גם (התכנסות במ"ש גוררת התכנסות נקודתית), ולכן אי-אפשר לקבל בסגור של תת-מרחב הזה את הפונקציה הקבועה והרציפה 1 (או כל פונקציה אחרת שלא מתאפסת באפס).

משפט 5: תהי \{ a_k \}_{k \ge 1} סדרת מספרים שונים כך ש-\inf_{k\ge 1} a_k > 0.
תנאי הכרחי ומספיק לכך שהסדרה \{ x^{a_k} \}_{k \ge 1} \cup \{ x^0\} תפרוש את מרחב הפונקציות הרציפות בקטע [0,a] בנורמת סופרמום הוא ש-\sum_{k \ge 1}\frac{1}{a_k} מתבדר.
הוכחה: כמו שהזכרנו מקודם, אפשר בלי הגבלת הכלליות להניח a=1.
בגלל שנורמת L^2 קטנה מנורמת סופרמום ((\int_{0}^{1} |g(x)|^2 \, \mathrm{d}x)^{1/2} \le \| g \|_{\infty}), נובע שהתנאי שמצאנו קודם, \sum_{k \ge 1}\frac{1}{a_k} מתבדר, הוא תנאי הכרחי. נראה שהתנאי הזה מספיק.

לפי משפט ויירשטראס, מספיק להראות שאפשר לקרב כל מונום x^m. בגלל שבכח הכנסנו את x^0, אפשר להניח m \ge 1.
הרעיון הוא להחליף הפרש נקודתי בין פונקציות (איתו מחשבים נורמת סופרמום) באינטגרל, ואז להשתמש באי-שיוויון קושי-שוורץ כדי להחליף את האינטגרל באינטגרל של ריבוע ולקבל נורמת L^2.
והנה הפרטים המלוכלכים: יהי \delta מספר חיובי שקטן מכל ה-a_k-ים. לכל סדרה \lambda_1, \cdots, \lambda_n, מתקיים (לכל x\in [0,1]):

\begin{aligned} |x^m - \sum_{k=1}^{n} \lambda_k x^{a_k}| & = |\int_{0}^{x} (mt^{m-1} - \sum_{k=1}^{n} a_k \lambda_{k} t^{a_k-1}) \, \mathrm{d}t \\ & \le \int_{0}^{x} t^{\delta-\frac{1}{2}} |mt^{m-\frac{1}{2}-\delta} - \sum_{k=1}^{n} a_k \lambda_k t^{a_k - \frac{1}{2} - \delta}| \, \mathrm{d} t\\ & \le (\int_{0}^{x} t^{2\delta - 1} \, \mathrm{d}t)^{1/2} (\int_{0}^{x} |mt^{m-1/2 -\delta} - \sum_{k=1}^{n} a_k \lambda_k t^{a_k-1/2-\delta}| \, \mathrm{d}t)^{1/2} \\ & \le (\frac{1}{2\delta})^{1/2} (\int_{0}^{1} |mt^{m-1/2-\delta} - \sum_{k=1}^{n} a_k \lambda_k t^{a_k-1/2 -\delta} |^2 \, \mathrm{d}t)^{1/2} \end{aligned}

שימו לב שזה חסם שלא תלוי ב-x\in [0,1].
בגלל ש-\sum \frac{1}{a_k} מתבדר אז גם \sum \frac{1}{a_k - \frac{1}{2} -\delta} מתבדר ולכן אפשר לבחור \lambda_i מתאימים כך שהאינטגרל יהיה קטן כרצוננו, ולכן \| x^m - \sum \lambda_k x^{a_k} \|_{\infty} יכול להיות קטן כרצוננו. \blacksquare

בעיה 3 – הבעיה של SEEMOUS

1. רדוקציה לאלגברה לינארית

הבעיה היא כזו: אנחנו עובדים במרחב המכפלה הפנימית L^2([0,1]), ונתונות לנו ה"זוויות" בין פונקציה רציפה f למונומים x^0, x^1, \cdots, x^{n-1}:

\forall k=0,1,\cdots, n-1: \int_{0}^{1} f(x)x^k \, \mathrm{d} x=1

אנחנו צריכים להבין כמה קטנה יכולה להיות הנורמה \int_{0}^{1} f(x)^2 \, \mathrm{d}x. קודם כל נשים לב שמדובר ב-n אילוצים, לכן אפשר למצוא פולינום p ממעלה n-1 שמקיים אותם: אם נציב p(x) = \sum_{i=0}^{n-1} a_i x^i מקבלים מערכת משוואות לינארית:

\sum_{i=0}^{n-1} a_i \langle x^i, x^k \rangle = 1

כלומר G(x^0, x^1, \cdots, x^{n-1}) \vec{a} = \vec{1}, ואם נהפוך את מטריצת גרם G(x^0, x^1, \cdots, x^{n-1}), שהיא למעשה מטריצת הילברט, נקבל את המקדמים של p.

אני טוען שמבין כל הפונקציות שמקיימות את האילוצים, ל-p יש את הנורמה הכי קטנה (ולכן צריך להסתכל רק עליה). ומדוע? אם f היא פונקציה שמקיימת את האילוצים, אז p-f מאונך ל-x^0, x^1, \cdots, x^{n-1}. נובע ש-p-f מאונך לכל פולינום ממעלה קטנה מ-n, בפרט מאונך ל-p. נובע ממשפט פיתגורס:

\langle f, f \rangle = \langle p, p \rangle + \langle f-p, f-p \rangle \ge \langle p, p \rangle

אז עשינו רדוקציה לבעיה חישובית: אנחנו צריכים להפוך את מטריצת הילברט H ולקבל את וקטור המקדמים \vec{a} = H^{-1} \vec{1}. לאחר מכן, צריך לחשב את המכפלה הפנימית \langle p, p \rangle:

\langle p, p \rangle = \sum_{i,j} a_i a_j \langle x^i, x^j \rangle = \sum a_i H_{i,j} a_j = \vec{a}^{T} H \vec{a}

נציב \vec{a} = H^{-1} \vec{1} ונקבל שהביטוי המבוקש הוא \vec{1}^{T} H^{-1} \vec{1} – ידוע גם בתור סכום האיברים במטריצה H^{-1}.

2. פירוק של מטריצת הילברט ונוסחה לפיתרון

יש נוסחה להופכית של מטריצת הילברט (ובאופן כללי להופכית של מטריצת קושי), אבל זו גישה מייגעת. אבל, אם מוצאים בסיס אורתוגונלי למרחב המכפלה הפנימית הנ"ל (כמו שעשינו בבעיה של הילברט), החיים נהיים דבש. אם p_i היא סדרה של פולינומים אורתוגונליים (כך ש-p_i ממעלה i), אז AHA^{T} = D כאשר:

  • A היא מטריצת המקדמים, כלומר בשורה ה-i יש את מקדמי p_i
  • D היא אלכסונית, במקום ה-(i,i) כתוב \langle p_i, p_i \rangle

אז:

\vec{1}^{T} H^{-1} \vec{1} = \vec{1}^{T} (A^T D^{-1} A) \vec{1} = (A\vec{1})^T (D^{-1} A\vec{1})

זה כבר ביטוי סביר: A\vec{1} זה וקטור שבמקום ה-i שלו כתוב סכום האיברים בשורה ה-i, כלומר סכום המקדמים של p_i, כלומר p_i(1), ואז הביטוי הנ"ל נהיה:

\sum_{i=0}^{n-1} \langle p_i, p_i \rangle ^{-1} p_i(1)^2

דוגמא לבסיס כזה היא "פולינומי לז'נדר המוזזים" שהוזכרו בבעיה הראשונה. הם מקיימים p_i(1)=1 ו-\langle p_i, p_i \rangle = \frac{1}{2i+1}, על כן הסכום נהיה:

\sum_{i=0}^{n-1} (2i+1) = n^2

וסיימנו. אבל לא הראנו את הדבר המרכזי: איך מגיעים לנוסחה ולתכונות של פולינומי לז'נדר?

3. פולינומי לז'נדר – תכונות והוכחות

התכונות שהזכרנו הן:

  1. p_n(x) = (-1)^n \sum_{k=0}^{n} \binom{n}{k}\binom{n+k}{k} (-x)^k. בפרט, המקדם המוביל הוא \binom{2n}{n}.
  2. \langle p_n, p_n \rangle = \frac{1}{2n+1}
  3. p_n(1) = 1
  4. הפולינומים הללו אורתוגונליים.

כל התכונות הללו הולכות לנבוע מהנוסחה האלגנטית הבאה שנקראת "נוסחת רודריגז":

p_n(x) = \frac{1}{n!} {d^n \over dx^n } \left[ (x^2 -x)^n \right]

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

אורתוגונליות: יהיו n>m. אנחנו רוצים להראות ש-\int_{0}^{1} p_n(x) p_m(x) \, \mathrm{d}x = 0.
נעשה אינטגרציה בחלקים פעם אחר פעם, באופן הבא: כזכור, יש פולינום שצריך לגזור ויש פולינום שצריך לו אינטגרציה. את התפקיד הראשון ימלא הפולינום שמגיע מ-m ואת התפקיד השני הפולינום שמגיע מ-n.
בכל אינטגרציה בחלקים נקבל שני ביטוים: איבר שמתקבל מהצבה של 1 ו-0, ואינטגרל.
לשמחתנו, האיבר הראשון תמיד יתאפס: כשגוזרים את (x^2-x)^n פחות מ-n פעמים, נשארים עם פולינום שמתחלק ב-x^2-x=x(x-1) ובפרט מתאפס ב-0,1.
לאחר שחוזרים על כך m+1 פעמים, נשארים עם אינטגרל של ביטוי שהוא למעשה 0: האינטגרנד הוא כפולה של {d^{2m+1} \over dx^{2m+1} } \left[ (x^2 -x)^m \right], וזו הנגזרת (2m+1)-ית של פולינום ממעלה 2m.

נורמה: באופן דומה, ע"י n אינטגרציות בחלקים, אפשר לחשב את הנורמה של p_n(x):

\int_{0}^{1} p_n(x)^2 \mathrm{d} x = \frac{1}{n!^2} (-1)^n \int_{0}^{1} (x^2-x)^n {d^{2n} \over dx^{2n} } \left[ (x^2 -x)^n \right] \mathrm{d} x =

הנגזרת ה-2n של פולינום מתוקן ממעלה 2n-ית היא (2n)!, ומקבלים:

=\binom{2n}{n} \int_{0}^{1} x^n(1-x)^n \mathrm{d} x

וגם את האינטגרל הזה (אינטגרל בטא, שקשור לאינטגרל סלברג) מחשבים באינטגרציה בחלקים והוא יוצא \frac{n! n!}{(2n+1)!}, כלומר סה"כ הנורמה בריבוע יוצאת \frac{1}{2n+1}, כמו שרצינו.

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

\begin{aligned} (x^2-x)^n &= x^n (x-1)^n \\ &= \sum_{k=0}^{n} x^{n+k} (-1)^{n-k} \binom{n}{k}\implies \\ \frac{1}{n!} {d^n \over dx^n} \left[ (x^2-x)^n \right] & = \sum_{k=0}^{n} \frac{(n+k)!}{n! k!} x^k (-1)^{n-k} \binom{n}{k}\\ &= (-1)^n \sum_{k=0}^{n} \binom{n}{k} \binom{n+k}{k} (-x)^k \end{aligned}

ערך ב-x=1: כעת נחשב את הערך של הפולינומים בנקודה x=1. נשים לב ש-p(x)= (x^2-x)^n סימטרי ביחס ל-x=\frac{1}{2}, כלומר p(x) = p(1-x). כשגוזרים את p, מקבלים שיוויון דומה רק עם סימן מינוס. לאחר n גזירות, הסימן הוא (-1)^n. על כן,

p_n(x) = (-1)^n p_n(1-x) \implies p_n(1) = (-1)^n p_n(0) = (-1)^n(-1)^n = 1

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

4. הכללה והוכחה אלמנטרית

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

משפט 6: תהי A_{i,j} = (a_i+b_j)^{-1} מטריצת קושי מסדר n \times n. סכום האיברים בהופכית של A, כלומר \vec{1}^TA^{-1}\vec{1}, הוא \sum (a_i + b_i).
(לדוגמא, במקרה של מטריצת הילברט, הסכום הוא \sum_{i=0}^{n-1} i + (i+1) = \sum_{i=0}^{n-1} (2i+1) = n^2.)

הוכחה: דרך שקולה להגיד "סכום האיברים ב-A^{-1}" היא "סכום האיברים בוקטור \vec{x} = A^{-1} \vec{1}". השיוויון A\vec{x} = \vec{1} גורר:

\forall t \in \{b_j \}: \sum_{i} \frac{x_i}{a_i + t} = 1

אם עושים מכנה משותף ומעבירים אגפים, מקבלים פולינום P(t) מתוקן ממעלה n ששורשיו הם \{ b_j \}, ולכן הוא שווה \prod (t-b_j), כלומר:

\prod (t-b_j) = \prod(t+a_i) - \sum_{j=1}^{n} x_j \prod_{i\neq j} (t+a_i)

נשווה את המקדם של t^{n-1} בשני האגפים ונקבל -\sum b_j = \sum a_i - \sum x_j, כלומר \sum x_j = \sum a_i + \sum b_j. \blacksquare

אנקדוטה: מסתבר ששאלה דומה, עם המטריצה a_{i,j} = \frac{1}{(2i)^2 - (2j-1)^2}, הופיעה בתחרות מתמטיקה אמריקאית לתיכונים, AIME, בשנת 1984. זה מאוד מפתיע. אם אתם סקפטים, פיתחו את הספר \text{101 Problems in Algebra} של Titu Andreescu ו-Zuming Feng. מדובר בבעיה מספר 68.

תרגיל 6: הראו שלכל n טבעי קיים פיתרון לא טריוויאלי לשיוויון הבא:

(a_0+...+a_{n-1})^2 = n^2\int_{0}^{1} (a_0+a_1 x+...+a_{n-1}x^{n-1})^2 \, \mathrm{d}x

נתראה בשמחות.

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

אודות Ofir Gorodetsky

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

תגובה אחת על 3 בעיות בגיאומטריה של פולינומים

  1. כנדרמון הגיב:

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

    להלן בעיה נוספת, שלא מדברת על גיאומטריה של פולינומים, אבל שיש בה חישוב יפה עם מטריצת ונדרמונט מפתיעה. נתבונן במעגל x^2 + y^2 = n, לו רדיוס r = sqrt(n). נתבונן בנקודות שלמות (x,y) על המעגל, ונרצה לבדוק האם יכולות להיות הרבה נקודות על קשת קצרה של המעגל. מסתבר שלא יכולות להיות אף 3 נקודות על קשת באורך קטן מ c*r^1/3! הסיבה לכך, היא שאם הן היו כל כך קרובות, אז חישוב גאומטרי יראה שהשטח של המשולש שהן מגדירות קטן מקבוע C. מצד שני, מכיוון שהן נקודות שלמות, השטח חייב להיות לפחות 1/2. לכן אם C קטן מ-1/2, מקבלים סתירה.

    כיצד ניתן להכליל את זה לקשת קצרה שמכילה m נקודות? נשים לב שהשטח שחישבנו הוא בעצם (חצי) דטרמיננטה של מטריצה, שהשורות שלה הן x_k, y_k, 1. אם נסמן את הנקודות בתור מספרים מרוכבים (שלמים גאוסיאניים) בתור ,z_k = x_k + iy_k, אז שתי העמודות הראשונות הן קומבינציות של העמודות conj(z_k), z_k. העמודה conj(z_k) היא כפולה בסקלאר של ההופכיים של z_k, ולכן עד כדי הכפלה כל שורה בחזקה של z_k, מדובר במטריצת ונדרמונט. עבור מספר אי זוגי m של נקודות, אפשר להסתכל על מטריצת ונדרמונט, לכפול את השורות כך שהחזקות תהיינה מחציתן שליליות ומחציתן חיוביות (ואחת 0), ואז את העמודות של החזקות השליליות לכפול בסקלאר כך שיהפכו לחזקות של הצמודים. אחרי התהליך תתקבל מטריצה רגולרית עם מקדמים שלמים (גאוסיאניים), ולכן לדטרמיננטה שלה יהיה ערך מוחלט לפחות 1. אם עוקבים אחרי כל הפעולות שביצענו וחוסמים את כל הגורמים בדטרמיננת הונדרמונט המקורית באמצעות הקוטר D, מקבלים ש-D קטן מ-r^(1/2 – 1/2m), עד כדי קבוע.

    משערים, אגב, שכמות הנקודות על כל קשת באורך r^(1-t) תכיל אוניפורמית לכל היותר M(t) נקודות לכל t חיובי, אבל עוד לא הצליחו לעבור את החצי.

כתיבת תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s