האם נמצאה נוסחה לפתרון משוואה ממעלה חמישית?! (לא)

מבוא

לפני כמה שבועות נתקלתי בכותרת מפוצצת: “Mathematician solves algebra’s oldest problem using intriguing new number sequences”. חיפוש זריז העלה עוד כותרות מפוצצות דומות: ““The Oldest Algebra Problem Solved”: Australian Mathematician Cracks Ancient Mystery That Baffled Minds for Over 4,000 Years” וגם “200-year-old “algebra wall” shattered with a bold new approach” ואיך אפשר בלי “Researchers Solve “Impossible” Math Problem After 200 Years”. כותרות המשנה היו מפוצצות לא פחות, למשל “A mathematician has developed an algebraic solution to an equation that was long thought to be unsolvable.”.

במילים פשוטות, מאמר מתמטי (שאפשר לקרוא כאן) עם השם הנאה “A Hyper-Catalan Series Solution to Polynomial Equations, and the Geode” הצליח איכשהו להגיע לכותרות, והוא הגיע לשם על ידי רכיבה על הטענה שהוא עושה את הבלתי אפשרי: נותן נוסחה לפתרון משוואה ממעלה חמישית, דבר שהוכח כבר לפני מאתיים שנה שהוא בלתי אפשרי וגם אני כבר תיארתי אותו בבלוג. אני כבר מורגל בכותרות כאלו ולכן אחרי שהתחלתי לקרוא לא הופתעתי לגלות ש:

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

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

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

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

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

מספרי קטלן ומשוואות ממעלה שניה - מבוא

החלק הטכני של המאמר מתחיל בדוגמא שמתבססת על האופן שבו אפשר להשתמש במספרי קטלן עבור משוואות ממעלה שניה. אני אציג את זה בערך כפי שזה מוצג במאמר: הם מתחילים מלכתוב את המשוואה הריבועית בצורה הבאה: \( 1-\alpha+t\alpha^{2}=0 \). זו בוודאי לא הדרך “הסטנדרטית” שבה כותבים משוואה כזו, שהיא \( ax^{2}+bx+c=0 \), אבל אם נניח ש-\( b=-c \) (זו הנחה שבהמשך יהיה קל להיפטר ממנה), ואז נחלק את כל המשוואה ב-\( c \) (בהנחה שהוא שונה מאפס) נקבל את המשוואה \( 1-x+\frac{a}{c}x^{2}=0 \) ולכן אם נסמן \( t=\frac{a}{c} \) נקבל את הצורה שהמאמר מניח. במקרה הספציפי הזה, אפשר להשתמש בנוסחת השורשים כדי לפתור את המשוואה ולקבל \( \alpha=\frac{1}{2t}\left(1\pm\sqrt{1-4t}\right) \). עכשיו המאמר מכניס לתמונה את הבינום המוכלל של ניוטון, שתיארתי בפוסט הקודם. הרעיון בו הוא שאפשר לכתוב באופן כללי:

\( \left(1+x\right)^{r}=\sum_{n=0}^{\infty}{r \choose n}x^{n} \)

כאשר \( {r \choose n}=\frac{r\left(r-1\right)\left(r-2\right)\cdots\left(r-n+1\right)}{n!} \)

הנכונות של הבינום לא מובנת מאליה; זו טענה שמוכיחים בעזרת חשבון דיפרנציאלי ואינטגרלי, וכדי שזה יעבוד צריך להתקיים \( \left|x\right|<1 \). אחרת… ובכן, למה לא לראות בעצמנו? הנה קוד פייתון פשוט שמחשב בינום מוכלל:

def generalized_binomial(r,n):
    result = 1
    for k in range(n):
        result *= (r-k)
        result /= (k+1)
    return result

נניח שאני רוצה להשתמש בקוד הזה כדי לחשב את, נאמר, \( \sqrt{\frac{1}{4}}=\frac{1}{2} \). אז אני אציב \( x=-\frac{3}{4} \) כדי לקבל \( 1+x=\frac{1}{4} \), ו-\( r=\frac{1}{2} \), ואקבל:

N = 100
x = - 0.75
r = 0.5
val = sum(generalized_binomial(r, n) * x**n for n in range(N))
print(f"{val:.10f}")

כשאני מריץ את הקוד הזה אני מקבל \( 0.5000000000 \) - יופי של דבר! ומה אם, למשל, אני רוצה לקבל את \( \sqrt{2} \)? אני אציב \( x=1 \) ואקבל \( 1.4143562059 \) שזה לא רע בכלל אחרי בסך הכל 100 איברים שאני מחבר. ואם אני רוצה לחשב את \( \sqrt{4}=2 \)? אז אני אציב \( x=3 \) ואקבל… אה… את זה:

36897381732338865935269100862142478752415744.0000000000

אוקיי, משהו כאן בבירור הפסיק לעבוד.

ברוכים הבאים לעולם המופלא של טורי חזקות. לטור חזקות \( \sum_{n=0}^{\infty}a_{n}x^{n} \) יש תמיד רדיוס התכנסות. מספר \( R \) כך שאם \( \left|x\right|<R \) אז הטור מתכנס, ואם \( \left|x\right|>R \) אז הטור מתבדר (גדל עוד ועוד עד אינסוף). מה קורה ב-\( \left|x\right|=R \)? כאן לא מובטח כלום. זה יכול להתכנס ויכול להתבדר, אין חוקים.

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

\( \frac{1}{R}=\lim\sup_{n\to\infty}\sqrt[n]{\left|a_{n}\right|} \)

כאשר אם הגבול בצד ימין יוצא 0 אז \( R=\infty \) (הטור מתכנס לכל ערך) ואם הוא יוצא אינסוף אז \( R=0 \) (הטור לא מתכנס בכלל). ייתכן שאתם לא מכירים את \( \lim\sup_{n\to\infty} \). הצגתי את המושג בפוסט הזה, אבל הנה תזכורת זריזה:

באופן כללי, \( \lim\sup_{n\to\infty}x_{n}=\lim_{n\to\infty}\left(\sup_{m\ge n}x_{m}\right) \) כלומר - הרעיון הוא לעבור מהסדרה המקורית \( \left\{ x_{n}\right\} _{n=1}^{\infty} \)שיכולה “להשתגע” ולקפץ מעלה-ומטה ומהומות ובעיות, אל סדרה שמתנהגת יותר נחמד: \( \left\{ y_{n}\right\} _{n=1}^{\infty} \) כך ש-\( y_{n}=\sup\left\{ x_{m}\ |\ m\ge n\right\} \). כאשר \( \sup \) הוא המושג הרגיל של חסם עליון. הסיבה לשימוש ב-\( \lim\sup \) היא כדי להבטיח שהגבול תמיד יהיה קיים (למרות שהוא יכול להיות אינסוף), כך שהנוסחה “תמיד עובדת”.

לפעמים יותר קל לחשב את \( R \) באופן הבא: \( R=\lim_{n\to\infty}\left|\frac{a_{n}}{a_{n+1}}\right| \) - זו “שיטת המנה” שהזכרתי, אבל הבעיה בה היא שלא תמיד הגבול קיים. מה שמובטח הוא שאם הגבול קיים, הוא שווה לרדיוס ההתכנסות.

איך זה מתקשר לדוגמא שראינו? בדוגמא שלנו, \( a_{n}={r \choose n}=\frac{r\left(r-1\right)\left(r-2\right)\cdots\left(r-n+1\right)}{n!} \). ההגדרה הזו נראית מתאימה עבור מבחן המנה:

\( \frac{a_{n}}{a_{n+1}}=\frac{\left(n+1\right)!}{n!}\frac{r\left(r-1\right)\left(r-2\right)\cdots\left(r-n+1\right)}{r\left(r-1\right)\left(r-2\right)\cdots\left(r-n\right)}=\frac{n}{r-n}=\frac{1}{\frac{r}{n}-1} \)

החשבון הזה מניח ש-\( r \) הוא לא מספר טבעי ולכן אין סיכון שיופיע לנו 0 במונה ובמכנה (אם \( r \) הוא טבעי אז נוסחת הבינום נותנת לנו סכום סופי שמתכנס תמיד) ומכיוון ש-\( \lim_{n\to\infty}\frac{r}{n}=0 \) אנחנו מקבלים ממנו שרדיוס ההתכנסות הוא תמיד 1, מה שמתאים יפה להתנהגות שראינו, עם הדוגמה של \( \sqrt{\frac{1}{4}} \) שעבדה יפה (\( x=-\frac{3}{4} \)), הדוגמא של \( \sqrt{2} \) שעדיין עבדה למרות שהיא על רדיוס ההתכנסות (\( x=1 \)) והדוגמא של \( \sqrt{4} \) שהיא לכאורה חישוב פשוט אבל נכשלה לחלוטין כי זה כבר מעבר לרדיוס ההתכנסות (\( x=3 \)).

נחזור אל המאמר. המאמר הגיע אל הנוסחה \( \alpha=\frac{1}{2t}\left(1\pm\sqrt{1-4t}\right) \) ואז אמר שנשתמש בבינום של ניוטון על הפתרון עם סימן המינוס ונקבל

\( \alpha=\sum_{n=0}^{\infty}\frac{\left(2n\right)!}{n!\left(n+1\right)!}t^{n}=\sum_{n=0}^{\infty}C_{n}t^{n} \)

כאשר \( C_{n} \) הם מספרי קטלן.

יש כאן, כמובן, דילוג על כמה שלבים של חישוב, אבל למרבה המזל כבר עשיתי את הכל בפירוט בפוסט הקודם שלי, על הפונקציה היוצרת של מספרי קטלן: ראינו שם שהיא \( C\left(x\right)=\frac{1-\sqrt{1-4x}}{2x} \), כאשר \( C\left(x\right)=\sum_{n=0}^{\infty}C_{n}x^{n} \). ה-\( \frac{\left(2n\right)!}{n!\left(n+1\right)!} \) שמופיע במאמר זו פשוט דרך מפורשת לכתוב את מספרי קטלן, \( C_{n}=\frac{\left(2n\right)!}{n!\left(n+1\right)!}=\frac{1}{n+1}{2n \choose n} \). המאמר משתמש ב-\( t \) בתור המשתנה של הסכימה ולא ב-\( x \), אבל זה כל ההבדל.

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

Applying Newton’s binomial expansion to the minus sign solution reveals the generating series of the Catalan numbers as the formal power series solution:

מילות המפתח כאן הן “Formal power series solution”. מה זה טור חזקות פורמלי - הקדשתי את כל הפוסט הקודם כדי להסביר, ואני לא אחזור על הפרטים הטכניים כאן אבל הרעיון המרכזי הוא זה: השוויון \( \frac{1-\sqrt{1-4x}}{2x}=\sum_{n=0}^{\infty}C_{n}x^{n} \) הוא נכון בלי להציב ערכים ב-\( x \). השוויון הזה לא אומר “לכל ערך שנציב ב-\( x \), אגף שמאל יהיה שווה לאגף ימין”. זו לא משוואה במובן הזה. השוויון אומר “האובייקט המתמטי שמופיע בצד שמאל הוא בדיוק אותו אובייקט כמו זה שמופיע באגף ימין”, כש”האובייקט” הוא מה שנקרא טור חזקות פורמלי. בטור שכזה האיקסים הם לא משהו שמציבים בו ערכים אלא משהו ש”מחזיק” את המקדמים. נשמע מוזר? כן, לכן הפוסט הקודם שלי מדבר על זה. ברצינות, אם זה מפריע לכם, קראו את הפוסט הקודם.

אבל אם מבינים את \( \frac{1-\sqrt{1-4x}}{2x} \) בתור ביטוי פורמלי נטו, משהו שלא אמורים להציב בו דברים, מה המשמעות של לכתוב \( \alpha=\frac{1-\sqrt{1-4t}}{2t} \), כמו שהמאמר עושה? המאמר מתחיל עם המשוואה \( 1-\alpha+t\alpha^{2}=0 \). מה זו המשוואה הזו? גם זה ביטוי פורמלי או שהרעיון פה הוא שמציבים ערך בפרמטר \( t \) ואז מקבלים משוואה שבאמת אפשר לפתור? כלומר, האם \( \alpha \) כאן מייצג מספר שמאופיין על ידי כך שהוא פותר משוואה פולינומית ואנחנו מחפשים דרך טובה לייצר את המספר הזה, או ש-\( \alpha \) מייצג כאן מלכתחילה טור חזקות פורמלי ולכן ה”פתרון” של המשוואה \( 1-\alpha+t\alpha^{2}=0 \) הוא נוסחה מפורשת לסדרת המקדמים של הטור הזה?

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

השאלה המעניינת שעולה כרגע היא - אוקיי, אנחנו מקבלים את זה שהראינו את השוויון הפורמלי \( \alpha=\frac{1-\sqrt{1-4t}}{2t}=\sum_{n=0}^{\infty}C_{n}t^{n} \). האם אפשר להשתמש בזה כדי לחשב פתרונות של המשוואה הריבועית \( 1-\alpha+t\alpha^{2}=0 \) עבור ערכים קונקרטיים של \( t \)? כלומר, להציב ערך מספרי ב-\( t \) ואז לחשב את \( \sum_{n=0}^{\infty}C_{n}t^{n} \) ולקבל את הערך? התשובה היא שבהחלט אפשר! אבל… בכפוף לקטע הזה של “רדיוס התכנסות”, מה שאומר שעבור רוב ערכי \( t \) זה לא יעבוד.

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

\( \frac{C_{n}}{C_{n+1}}=\frac{\left(2n\right)!}{n!\left(n+1\right)!}\frac{\left(n+1\right)!\left(n+2\right)!}{\left(2n+2\right)!}=\frac{\left(n+1\right)\left(n+2\right)}{\left(2n+1\right)\left(2n+2\right)}=\frac{n^{2}+2n+2}{4n^{2}+6n+2}\to\frac{1}{4} \)

כלומר, הרדיוס הוא \( R=\frac{1}{4} \).

רציתי לבחור \( t \) קטן מהרדיוס שעדיין נותן עבור \( \alpha \) ערך “נחמד” שאפשר לחשב ידנית, אז הינדסתי את \( t=\frac{2}{9} \). הערך הזה נותן לנו את המשוואה הריבועית \( 2\alpha^{2}-9\alpha+9=0 \) שהפתרונות שלה הם

\( \alpha_{1,2}=\frac{9\pm\sqrt{81-72}}{4}=\frac{9\pm\sqrt{9}}{4}=\frac{9\pm3}{4}=3,1.5 \)

כאשר \( 1.5 \) הוא הפתרון שמתקבל מהמינוס. עכשיו, הנה קוד שיאפשר לנו לחשב מה קורה:

def C(n):   
    result = 1
    for k in range(2, n+1):
        result *= (n+k)
        result /= k
    return result

N = 100
t = 2/9
val = sum(C(n)* t**n for n in range(N))
print(f"{val:.10f}")

כשאני מריץ אותו אני מקבל \( 1.4999999653 \) שזה יפה מאוד, ואם אני מעלה את \( N \) אל \( 200 \) אני מקבל כבר \( 1.5 \) (זה עדיין לא בדיוק \( 1.5 \) אלא רק במסגרת 10 ספרות הדיוק שאני מציג). כלומר זה עובד, ועובד יפה! כל עוד \( t<\frac{1}{4} \).

מה קורה אם \( t=\frac{1}{4} \)? כאן אז אנחנו מקבלים את המשוואה \( \alpha^{2}-4t+4=0 \) שנפתרת על ידי \( \alpha=2 \). אם נחשב את הטור \( \sum_{n=0}^{\infty}\frac{C_{n}}{4^{n}} \) עם הקוד שלי נקבל עבור \( N=100 \) את התוצאה \( 1.8873030420 \) שזה… אה… די קרוב ל-2! בטח אם אני אחבר יותר איברים, כלומר אגדיל את \( N \), אני אתקרב עוד יותר ל-2. אם אני מציב \( N=500 \) אני מקבל \( 1.9495499636 \), שזה טוב! זה הולך ומתקרב אל 2! אבל אז…! כשאני מציב \( N=600 \)! אני פתאום מקבל “nan”. מה זה אומר בכלל? זה אומר שתש כוחו של פייתון. היכולת שלו לעשות חישובים עם המספרים הרלוונטיים נגמרה. במקרה הנוכחי, מה שגומר אותו זה ה-\( \frac{1}{4^{n}} \) שהופך להיות כל כך קטן ששיטת הייצוג הסטנדרטית של נקודה צפה (דיברתי על זה קצת כאן) כבר לא מסוגלת לייצג אותו. זה נשמע כמובן טיפה הזוי - אם זה מספר כל כך קטן למה שהוא בכלל עוד ישפיע על הסכום? כלומר, למה אפילו ב-\( N=500 \) עדיין לא קיבלנו את התוצאה 2 ברמת דיוק של 10 ספרות? ובכן, כי כמה ש-\( \frac{1}{4^{n}} \) הוא קטן מתקזז עם כמה ש-\( C_{n} \) הוא גדול. במילים אחרות, ייצוג כזה באמצעות טור הוא לא ייצוג יעיל, כי הטור מורכב משני גורמים אקספוננציאליים שרבים זה עם זה ומקזזים זה את זה. זה בעצם מה שמבחני המנה והשורש מראים לנו - מה קצב הגידול של המקדמים שהחזקה נאלצת להתמודד איתם. כל עוד החזקה גדולה יותר מקצב הגידול הזה, הטור יתכנס מהר יחסית; אבל כשהם שווים זה יכול להיות עניין כואב ביותר ושום דבר לא מובטח, ואם הם גדולים יותר…

אם אני מציב למשל \( t=-2 \) אני מקבל את המשוואה \( 2\alpha^{2}+\alpha-1=0 \) עם הפתרונות \( \alpha_{1,2}=\frac{-1\pm\sqrt{1+8}}{4}=\frac{-1\pm3}{4}=-1,0.5 \) אבל אם אציב את זה בקוד שלי, אפילו עבור \( N=10 \), אני אקבל בערך \( -2170881 \) ומשם זה רק נהיה יותר ויותר גרוע. הטור לא עובד במקרים כאלו, תשכחו מזה.

יש לכאורה עוד בעיה פה - הטור נותן לי רק פתרון אחד, מה עם השני? זה פחות מפריע לי כי תמיד אפשר לפתור משוואות בצורה הבאה: אם \( p\left(x\right) \) הוא הפולינום שמקודד את המשוואה, מוצאים שורש אחד ספציפי \( p\left(\alpha\right)=0 \) ואז מחלקים ומקבלים \( q\left(x\right)=\frac{p\left(x\right)}{x-\alpha} \). זה עובד, ושורש של \( q\left(x\right) \) יהיה גם שורש של \( p\left(x\right) \) ובצורה הזו אפשר למצוא את כל השורשים… אם כי אני בעצם מניח כאן במובלע שאם את \( p\left(x\right) \) הייתי מסוגל לפתור עם הטור הזה אני אוכל לפתור גם את \( q\left(x\right) \) באותה צורה, וראינו כבר שזה לא בהכרח נכון - זה מאוד תלוי במקדמים.

האם זה אומר שיש משוואות שהשיטה פשוט לא מסוגלת לפתור? לא! בהמשך המאמר יש התייחסות לזה. אז בואו נראה את השלב שבו הוא מתחיל לפרמל דברים.

מספרי קטלן ומשוואות ממעלה שניה - הגישה הפורמלית של המאמר

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

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

כשמתעסקים בשילושים של מצולעים, צריך איכשהו להבדיל בין שני שילושים שנראים “אותו דבר עד כדי סיבוב”. בפוסט שלי הדרך להשיג את זה הייתה למספר את הקודקודים של המצולע; המאמר משיג את האפקט הזה על ידי סימון אחת הצלעות של המצולע בתור “גג” וכשמציירים את המצולע, היא מצויירת למעלה - זה היה התפקיד של הצלע 1-2 אצלי. לפוליגון עם צלע שהיא גג שכבר עבר חלוקה למשולשים המאמר קורא Triagon ומשתמש בסימון \( | \) (קו אנכי) כדי לתאר את המקרה המנוון של “מצולע” בן שתי צלעות - משהו שראינו בפוסט שלי שמשתלם לספור. המאמר מסמן ב-\( \mathcal{T}_{n} \) את אוסף הטריגונים עם \( n \) פאות; כלומר, מספר המשולשים שיש בתוך הטריגון. זו דרך חכמה לעקוף את ניג’וס ה-\( n+2 \) שמתלווה לפוליגונים הללו כשסופרים את הקודקודים. עם הסימון הזה, \( \left|\mathcal{T}_{n}\right|=C_{n} \). כמובן, זה מניח שאנחנו מזהים טריגונים שהם “אותו הדבר” אפילו אם הצורה שלהם קצת שונה - אני מניח שאנחנו בסדר עם זה.

עכשיו המאמר מסביר בצורה מפורטת איך אפשר לבנות טריגון חדש משניים קיימים. בגדול, זה ההיפוך של התהליך שתיארתי בפוסט שלי - שם הסרנו את הצלע 1-2 וקיבלנו שני טריגונים, כך שמספר הפאות הכולל שלהם הוא כמספר הפאות בטריגון שהתחלנו ממנו, פחות 1. כשמסמנים את הפונקציה היוצרת של הטריגונים על ידי \( T\left[t\right] \) כפי שהמאמר עושה, זה מוביל למשוואה

\( T=1+tT^{2} \)

בניות כאלו מוסברות בצורה יותר מקיפה בספר הנהדר Analytic Combinatorics של Flajolet ו-Sedgewick שכרגע זמין במלואו באופן חופשי כאן. הבניה עבור קטלן מוסברת בעמוד 35-36; בגדול, אפשר לחשוב על כל טריגון בתור אחד משני דברים: או הטריגון המנוון \( | \) וכזה יש בדיוק 1, מגודל 0, ולכן התרומה שלו ל-\( T\left[t\right] \) היא \( 1\cdot t^{0} \); או טריגון שאפשר לתאר בתור משהו שבנוי משלושה טריגונים: שניים מגודל כלשהו ואחד מגודל 1 (המשולש שמסירים כשמוחקים את הצלע 1-2). מכיוון שמכפלה של פונקציות יוצרות מתאימה בדיוק לסיטואציה של בניה של אובייקט קומבינטורי מהאובייקטים שמתוארים על ידי הפונקציות שמכפילים, כך שהגודל של האובייקט הקומבינטורי הזה הוא סכום הגדלים של המוכפלים, מקבלים עבור המקרה הזה את \( T\cdot t\cdot T=tT^{2} \). דרך ההתבוננות הזו היא ממש מועילה ולמי שזה מעניין אותה אני ממליץ לקרוא את הספר (רק את החלק הראשון שלו! היתר זה נושאים, אה, שונים) והתייחסתי לזה קצת יותר בפוסטים שכתבתי בשעתו.

בקיצור, קיבלנו את הנוסחה \( T=1+tT^{2} \) שבפוסט הקודם שלי ראינו כבר שהיא הנוסחה שמקיימים מספרי קטלן ומכאן המאמר מרשה לעצמו לכתוב \( T=\sum_{n=0}^{\infty}C_{n}t^{n} \).

עכשיו, אם נעביר את \( T \) אגף נקבל את המשוואה \( 1-T+tT^{2}=0 \), כלומר \( T \) מקיים משוואה ריבועית מצורה ספציפית: המקדם החופשי הוא 1 והמקדם של החזקה הבאה הוא \( -1 \). המאמר אומר שפולינום שמקיים את שתי הדרישות הללו הוא בצורה גאומטרית ושהמשוואה הריבועית \( 1-\alpha+t\alpha^{2} \) היא המשוואה הריבועית הגאומטרית הכללית. בהתבסס על התוצאה הקומבינטורית שהוא הראה (שהיא, כאמור, סטנדרטית) הוא מסיק את מה שהוא מכנה משפט 1: שלמשוואה \( 1-\alpha+t\alpha^{2} \) יש “formal power series solution” שהוא

\( \alpha=T\left[t\right]=\sum_{n=0}^{\infty}C_{n}t^{n} \)

אני חייב להודות שאני לא בטוח מה התוכן של המשפט הזה מעבר ל”הפונקציה היוצרת של מספרי קטלן מקיימת את המשוואה הריבועית \( 1-\alpha+t\alpha^{2} \)” - וזו כאמור טענה סטנדרטית עוד מימי אוילר. המאמר קורא לזה הנוסחה הגאומטרית הריבועית הרכה שזה שם מפוצץ לדבר קיים, אבל מייד אחר כך מגיע תוכן קצת יותר מעניין - הסבר איך אפשר לעבור מהמקרה הזה לפתרון של משוואה ריבועית כללית, לא כזו שהיא בצורה גאומטרית. לזה הוא קורא משפט 2 ונותן לו את השם הטיפה פחות מפוצץ הנוסחה הריבועית הרכה. זה הולך ככה: נסמן משוואה ריבועית כללית בתור \( c_{0}-c_{1}x+c_{2}x^{2}=0 \). עכשיו נבצע החלפת משתנים: נסמן, \( x=\frac{c_{0}}{c_{1}}\alpha \) נציב במשוואה ונקבל

\( c_{0}\left(1-\alpha+\frac{c_{0}c_{2}}{c_{1}^{2}}\alpha^{2}\right)=0 \)

עכשיו נשתמש במשפט הקודם עם \( t=\frac{c_{0}c_{2}}{c_{1}^{2}} \) ונקבל את הפתרון הבא:

\( \alpha=\sum_{n=0}^{\infty}C_{n}\frac{c_{0}^{n}c_{2}^{n}}{c_{1}^{2n}} \)

אלא שאנחנו רוצים את \( x \), לא את \( \alpha \), אז נכפול הכל ב-\( c_{0} \) ונחלק ב-\( c_{1} \) ונקבל

\( x=\sum_{n=0}^{\infty}C_{n}\frac{c_{0}^{1+n}c_{2}^{n}}{c_{1}^{1+2n}} \)

וזו כבר נוסחה קונקרטית ומעניינת! רק מה, היא… לא לגמרי עובדת. ראשית, יש לנו חלוקה ב-\( c_{1} \), זה אומר שאם \( c_{1}=0 \) (כמו למשל במשוואה \( x^{2}=2 \)) השיטה נכשלת. המאמר מתייחס לזה:

It’s curious that the equation with the easiest solution in radicals is the least accessible with this method. A simple change of variables lets us skirt around the problem.

אם \( c_{0}=0 \) אז המשוואה שלנו היא מהצורה \( c_{2}x^{2}=c_{1}x \) ולכן יש לה את הפתרון הטריוויאלי \( x=0 \); זה מה שהנוסחה משיגה במקרה הזה; בשביל להשיג את הפתרון השני צריך להשתמש בטריק החלוקה שתיארתי קודם. האם זה אומר שהנוסחה שהם מצאו היא “לא כללית”? אני לא חושב שזה כזה בעייתי. אם תסתכלו בפוסט שלי על פתרון משוואה ממעלה שלישית, גם שם משתמשים בטריקים של החלפת משתנים, למשל. כדי להרגיש שיש בעיה עם מקרי הקיצון הללו צריך להיות ממש טהרנים לגבי מה זה אומר שיש “פתרון כללי” למשוואה.

אבל הבעיה האמיתית, שכבר ראינו קודם, היא שהטור הזה פשוט לא מתכנס עבור חלק מהמספרים. המאמר לא מתייחס לזה שם, ואני מניח שזה בצדק מבחינתו כי לומר “formal power series solution” זה לכאורה לצאת ידי חובה. בהמשך, כאמור, תהיה התייחסות יותר רצינית לזה אז נעזוב את זה לבינתיים.

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

מספרי היפר-קטלן ומשוואות ממעלה כלשהי

לפני שנראה מה המאמר עושה, בואו נחשוב שניה מה היינו רוצים שיקרה. עבור משוואה ממעלה שניה, מספרי קטלן נתנו לנו את הנוסחה \( T=1+tT^{2} \). עבור משוואה ממעלה שלישית, אולי אפשר למצוא בעיה מקבילה עם משוואה מהצורה \( T=1+tT^{2}+tT^{3} \)? זה לא כזה קשה - רק צריך למצוא אובייקט שנספר על ידי \( T \), יש 1 ממנו שהוא מגודל 0, ואפשר לבנות אותו מחיבור של שניים או שלושה אובייקטים, ואז הגודל שלו הוא סכום הגדלים שלהם ועוד 1. להמציא כזה אובייקט זה כנראה לא כל כך קשה (אם תפתחו ב-Analytic Combinatorics את החלק של Context-free specifications and languages תראו דרך כללית לעשות דברים כאלו) אבל יש כאן שתי בעיות. ראשית, לא ברור אם נוכל למצוא נוסחה מפורשת לכמות האיברים שמתאימים לאובייקט, כמו זו שהייתה לנו עבור קטלן; ושנית, המשוואה שלנו יוצאת מאוד מוגבלת - המקדם של \( T^{2} \) זהה למקדם של \( T^{3} \), וללהטוטים שעשינו קודם יש גבול, הם לא יצליחו לטפל גם בזה.

אז כאן המאמר עושה משהו יפה: במקום לעבוד עם פונקציה יוצרת במשתנה בודד, הוא עובר לעבוד עם פונקציה יוצרת במספר משתנים. בואו נבין איך זה ייראה עבור משוואה ממעלה שלישית, ואז נוכל להגיע כבר למשוואה כללית. עבור מעלה שלישית, המטרה היא למצוא פונקציה יוצרת \( S\left[t_{2},t_{3}\right] \) כך ש-\( S=1+t_{2}S^{2}+t_{3}S^{3} \).

מה \( S \) הולכת לספור? ובכן, קודם היה לנו את \( T=\sum_{n=0}^{\infty}\left|\mathcal{T}_{n}\right|t^{n} \), כך ש-\( \mathcal{T}_{n} \) הייתה קבוצה של טריגונים, כלומר פוליגונים עם צלע מובחנת ספציפית שמחולקים למשולשים, וספציפית ב-\( \mathcal{T}_{n} \) היו הטריגונים שמחולקים ל-\( n \) משולשים. אבל מה אם נרשה חלוקה גם למשולשים וגם למרובעים? אפשר לסמן ב- \( \mathcal{S}_{\left[m_{2},m_{3}\right]} \) את מספר הפוליגונים עם צלע מובחנת שמחולקים ל-\( m_{2} \) משולשים ו-\( m_{3} \) מרובעים, ו-\( \left[m_{2},m_{3}\right] \) ייקרא הטיפוס של ה… אה… לא נקרא לזה טריגון (כי tri זה שלוש, ועברנו לדבר על חלוקה פנימית לדברים עם יותר משלוש צלעות) - במאמר קוראים לזה סבדיגון (subdigon). עכשיו נגדיר את מספר ההיפר-קטלן \( C_{\left[m_{2},m_{3}\right]} \) בתור מספר הסבדיגונים מטיפוס \( \left[m_{2},m_{3}\right] \) ונגדיר פונקציה יוצרת עם שני משתנים,

\( S=S\left[t_{2},t_{3}\right]=\sum_{m_{2},m_{3}\ge0}C_{\left[m_{2},m_{3}\right]}t_{2}^{m_{2}}t_{3}^{m_{3}} \)

כאן הרעיון הוא שהחזקה של \( t_{2} \) סופרת כמה משולשים יש בסבדיגון שלנו, והחזקה של \( t_{3} \) סופרת כמה מרובעים.

הכתיב הזה טיפה מסורבל, וגם לא לגמרי ברור על מה משתנה הסכימה רץ, אז המאמר מפשט את זה ומסמן \( \mathbf{m}=\left[m_{2},m_{3}\right] \) וכותב \( \mathbf{m}\ge0 \) כדי לסמן את זה ש-\( \mathbf{m} \) רץ על כל הזוגות \( \left[m_{2},m_{3}\right] \) שבהם \( m_{2}\ge0 \) וגם \( m_{3}\ge0 \). אפשר להשתמש גם בסימון \( \mathbf{t}^{\mathbf{m}}=t_{2}^{m_{2}}t_{3}^{m_{3}} \) ולקבל מעין “שחזור” של הנוסחה הקודמת:

\( S=\sum_{\mathbf{m}\ge0}C_{\mathbf{m}}\mathbf{t}^{\mathbf{m}} \)

עכשיו יש שתי שאלות:

  • איזו נוסחה פולינומית מקיימת \( S \) הזו? אנחנו רוצים הכללה של \( T=1+tT^{2} \).
  • איך מחשבים מספרית את \( C_{\mathbf{m}} \)? אנחנו רוצים חישוב נוח כמו של \( C_{n} \).

למרבה השמחה, בשני המקרים יש לזה תשובה טובה. ראשית, הנוסחה הפולינומית ש-\( S \) מקיימת. קודם, במקרה של \( T \), קיבלנו את \( T=1+tT^{2} \) באופן הבא: ה-1 היה הטריגון היחיד עם 0 משולשים, שסומן \( | \), ואילו \( tT^{2} \) תיאר בניה של טריגון מתוך שני טריגונים קיימים (זה \( T \) כפול \( T \)) ועוד משולש אחד שדוחפים ביניהם (זה \( t \)). הרעיון הוא שבמשולש שדוחפים ביניהם אחת מהצלעות תהיה הצלע המובחנת של הטריגון שבונים, ואל שתי הצלעות האחרות “מדביקים” את שני הטריגונים שבחרנו. כשאנחנו עובדים עם סבדיגונים את פעולת הבניה הזו אפשר לעשות גם עם מרובע, כלומר לקחת מרובע, לסמן את אחת הצלעות שלו בתור הצלע המובחנת, ולהדביק לו שלושה סבדיגונים. התוצאה של זה תהיה \( t_{3}S^{3} \): החזקה השלישית של \( S \) היא כי אנחנו מדביקים שלושה סבדיגונים; המכפלה ב-\( t_{3} \) היא כי הוספנו לסבדיגון שאנחנו בונים מרובע שאליו כולם נדבקים, ו-\( t_{3} \) סופר כמה מרובעים יש.

הבניה הקודמת, שבה לוקחים משולש ומדביקים לו שני סבדיגונים, עדיין אפשרית גם כן, ונספרת על ידי \( t_{2}S^{2} \). ובגלל שאלו שתי בניות שונות שמניבות אובייקטים שונים, סופרים אותן בנפרד (“עקרון החיבור”) ויחד עם מקרה הבסיס, נקבל את הנוסחה

\( S=1+t_{2}S^{2}+t_{3}S^{3} \)

ועכשיו אפשר כמו קודם להסתכל על המשוואה

\( 0=1-\alpha+t_{2}\alpha^{2}+t_{3}\alpha^{3} \)

ולהגיד שיש לה formal power series solution שהוא

\( \alpha=S=S\left[t_{2},t_{3}\right]=\sum_{m_{2},m_{3}\ge0}C_{\left[m_{2},m_{3}\right]}t_{2}^{m_{2}}t_{3}^{m_{3}}=\sum_{\mathbf{m}\ge0}C_{\mathbf{m}}\mathbf{t}^{\mathbf{m}} \)

כדי להשלים את התמונה, מסתכלים על משוואה פולינומית כללית ממעלה 3:

\( 0=c_{0}-c_{1}x+c_{2}x^{2}+c_{3}x^{3} \)

ומשתמשים באותה החלפה, \( \alpha=\frac{c_{0}}{c_{1}}x \) והצבות \( t_{k}=\frac{c_{0}^{k-1}c_{k}}{c_{1}^{k}} \) עבור \( k=2,3 \) כדי לקבל

\( x=\sum_{m_{2},m_{3}\ge0}C_{\left[m_{2},m_{3}\right]}\frac{c_{0}^{1+m_{2}+2m_{3}}}{c_{1}^{1+2m_{2}+3m_{3}}}c_{2}^{m_{2}}c_{3}^{m_{3}} \)

ושוב - המאמר מתעלם באלגנטיות כאן מהשאלה האם בכלל הטור מתכנס עבור כזו הצבה של ערכים ב-\( t \)-ים.

זהו, זה כל הרעיון - וזו הדרך שבה המאמר מוכיח את התוצאה המרכזית שלו. אלא שהוא לא עושה את זה רק עבור משוואות ממעלה שלישית; הוא עושה את זה לכל מעלה, כי הההכללה של מה שראינו היא פשוטה מאוד: אמרנו שסבדיגון יכול להיות מטיפוס \( \left[m_{2},m_{3}\right] \)? אנחנו מרשים לו להיות מטיפוס יותר כללי, \( \mathbf{m}=\left[m_{2},m_{3},m_{4},\ldots\right] \) כאשר המגבלה היחידה היא שכל ה-\( m \)-ים הם 0 החל ממקום מסוים. \( \mathcal{S}_{\left[m_{2},m_{3},m_{4},\ldots\right]} \) סופרת את הפוליגונים עם צלע מובחנת שמחולקים ל-\( m_{2} \) משולשים, \( m_{3} \) מרובעים, \( m_{4} \) מחומשים וכן הלאה - באופן כללי, \( m_{k} \) מצולעים עם \( k+1 \) צלעות והמספר מסומן ב-\( C_{\left[m_{2},m_{3},\ldots\right]} \) (ומכיוון שאנחנו סופרים רק צורות סופיות, ברור שלא ייתכן ש-\( \left[m_{2},m_{3},m_{4},\ldots\right] \) יהיה אינסופי “באמת” אלא חייב להיות 0 החל ממקום מסוים). עכשיו כותבים

\( S=S\left[t_{2},t_{3}\right]=\sum_{m_{2},m_{3},\ldots\ge0}C_{\left[m_{2},m_{3},\ldots\right]}t_{2}^{m_{2}}t_{3}^{m_{3}}\ldots \)

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

\( \alpha=S=S\left[t_{2},t_{3},\ldots\right]=\sum_{m_{2},m_{3},\ldots\ge0}C_{\left[m_{2},m_{3},\ldots\right]}t_{2}^{m_{2}}t_{3}^{m_{3}}\ldots=\sum_{\mathbf{m}\ge0}C_{\mathbf{m}}\mathbf{t}^{\mathbf{m}} \)

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

\( x=\sum_{m_{2},m_{3},\ldots\ge0}C_{\left[m_{2},m_{3},\ldots\right]}\frac{c_{0}^{1+m_{2}+2m_{3}+\ldots}}{c_{1}^{1+2m_{2}+3m_{3}+\ldots}}c_{2}^{m_{2}}c_{3}^{m_{3}}\ldots \)

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

בואו ניקח רגע להעריך את זה לפני שנתקדם.

אוקיי, אז קיבלנו נוסחה, אבל בנוסחה הזו מופיעים המספרים \( C_{\left[m_{2},m_{3},\ldots\right]} \), ואם אין לנו דרך נוחה לחשב אותם, אז מה עשינו בזה? למרבה השמחה, יש נוסחה פשוטה עבורם, כמו שיש עבור מספרי קטלן. המאמר לא מוכיח את זה אלא מצטט תוצאה מוכרת אם \( \mathbf{m}=\left[m_{2},m_{3},m_{4},\ldots\right] \) אז

\( C_{\mathbf{m}}=\frac{\left(2m_{2}+3m_{3}+4m_{4}+\ldots\right)!}{\left(1+m_{2}+2m_{3}+3m_{4}+\ldots\right)!m_{2}!m_{3}!m_{4}!\cdots} \)

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

בואו נלכלך ידיים וננסה להבין - האם זה יעיל?

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

ראשית, נניח שיש לנו משוואה ריבועית, \( ax^{2}+bx+c=0 \). נוסחת השורשים נותנת לנו את הפתרון \( x_{1,2}=\frac{-b\pm\sqrt{b^{2}-4ac}}{2a} \). מה יש לנו כאן? כדי לחשב את הנוסחה צריך

  • להעלות את \( b \) בריבוע (פעולת כפל)
  • לחשב את \( 4ac \) (שתי פעולות כפל)
  • לחשב את \( b^{2}-4ac \) (פעולת חיסור)
  • לחשב את \( \sqrt{b^{2}-4ac} \) (פעולת הוצאת שורש)
  • לחשב את \( \pm\sqrt{b^{2}-4ac}-b \) (פעולת חיסור)
  • לחשב את \( 2a \) (פעולת כפל)
  • לחשב את \( \frac{-b\pm\sqrt{b^{2}-4ac}}{2a} \) (פעולת חילוק)

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

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

Our modern quadratic formula involves a square root operation, which even in ancient times was known to generally not terminate, yielding only approximate solutions

שנית, כל הקטע הזה של נוסחה שיש בה פעולות מקוננות (פעולות שמבוצעות זו בתוך זו; למשל, במשוואה ממעלה שלישית בהחלט יש הוצאת שורש בתוך הוצאת שורש שלישי - אנחנו מקבלים משהו שנראה כמו \( \sqrt[3]{-\frac{27}{2}q+\frac{3}{2}\sqrt{-3D}} \)) מפריע להם, לעומת סכום “פשוט יותר”:

After all, if we’re permitted nested unending nth root calculations, why not a simpler ongoing sum that actually solves polynomials beyond degree four

אני אישית חושב שהוצאת שורש היא דבר די פשוט. ראשית, מבחינה קונספטואלית: עם איבר כמו \( \sqrt{a} \) אני יכול לעבוד בקלות, אלגברית: למשל, אני יודע ש-\( \left(3+\sqrt{a}\right)^{2}=9+6\sqrt{a}+a=\left(9+a\right)+6\sqrt{a} \). כלומר, אני יודע לבצע אלגברה עם ביטויים שמכילים שורשים ולקבל בחזרה ביטוי שהוא באותה רמת סיבוך - עדיין יש לו רק שורשים מאותה רמה. עם פתרון שנתון בנוסחת ההיפר-קטלן אני לא יודע אם אני יכול לעשות את זה באותה קלות - אבל זה דיון רחב מאוד שאני לא הולך להיכנס אליו וממילא לא תהיה בו הכרעה ברורה ולא צריכה להיות בו הכרעה ברורה כי חלק ממה שנחמד במתמטיקה הוא שיש שלל ייצוגים שונים לאותו דבר, וכל ייצוג מביא איתו נקודת מבט שונה שיכולה להיות שימושית לפעמים.

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

השימושיות של ניוטון-רפסון חורגת מאשר “סתם” מציאת שורשים לפולינומים, ובהקשר של שורשים לפולינומים יש שיטות לשפר את היעילות שלה, אבל זה מצדיק פוסט בפני עצמו (שאין לי). כאן אני אסתפק בלהציג את השיטה בצורה הפשוטה ביותר שלה ונראה אם זה יספיק. הרעיון המרכזי בניוטון-רפסון הוא זה: אם נתונה לנו פונקציה \( f\left(x\right) \) ואנחנו רוצים למצוא \( a \) כך ש-\( f\left(a\right)=0 \), בואו נגדיר סדרה של קירובים ל-\( a \) הזו, שהולכת ומשתפרת. נתחיל עם קירוב כלשהו, \( a_{0} \), ואז נגדיר סדרה \( a_{n} \) על ידי הכלל

\( a_{n+1}=a_{n}-\frac{f\left(a_{n}\right)}{f^{\prime}\left(a_{n}\right)} \)

למה? מאיפה זה מגיע? בפוסט הזה שלי אני מנסה (בפרק השלישי) לתת לזה אינטואיציה - לא אכנס לזה עכשיו שוב (אבל בהחלט צריך פוסט ייעודי על הנושא הזה!). במקום זה, בואו נראה איך זה עובד עבור הבעיה הפשוטה של חישוב שורש. במקרה הזה, נניח שאני רוצה לחשב את השורש \( \sqrt{D} \) עבור מספר ממשי \( D \) כלשהו. אני אגדיר פונקציה \( f\left(x\right)=x^{2}-D \), אז בבירור \( f\left(\sqrt{D}\right)=0 \) ולכן זו הפונקציה שאני רוצה להשתמש בה. חישוב הנגזרת של פונקציה כזו הוא טריוויאלי: \( f^{\prime}\left(x\right)=2x \), ולכן נקבל את הסדרה

\( a_{n+1}=a_{n}-\frac{a_{n}^{2}-D}{2a_{n}}=\frac{2a_{n}^{2}-a_{n}^{2}+D}{2a_{n}}=\frac{a_{n}^{2}+D}{2a_{n}}=\frac{1}{2}\left(a_{n}+\frac{D}{a_{n}}\right) \)

אני מאוד אוהב את התוצאה הזו, כי הנוסחה \( a_{n+1}=\frac{1}{2}\left(a_{n}+\frac{D}{a_{n}}\right) \) הייתה למעשה קיימת הרבה לפני ניוטון - זו שיטה שתוארה על ידי הרון מאלכסנדריה לפני 2,000 שנים בערך, ויש לה אינטואיציה גאומטרית יפהפיה: אם נסתכל על ריבוע ששטחו \( D \), אז אורך צלעו יהיה \( \sqrt{D} \). מה שהרון מציע הוא להתחיל עם מלבן שאורך אחת מצלעותיו הוא \( a_{0} \) ושטחו \( D \), ואז אורך צלעו השניה תהיה \( \frac{D}{a_{n}} \). אנחנו רוצים שאורכי הצלעות ישתוו, אז אנחנו מחליפים את \( a_{n} \) בממוצע בין \( a_{n} \) והצלע השניה, ומקבלים סדרה שהולכת ומשתפרת של מלבנים שהופכים לקרובים יותר ויותר לריבוע.

כל איטרציה כוללת פעולת חילוק “קשה” אחת: החילוק \( \frac{D}{a_{n}} \). בנוסף יש פעולת חיבור ופעולת חילוק “קלה יותר”, חילוק ב-2. זה לא כל כך הרבה!

הנה קוד שמריץ את זה ומקבל תוצאה שהיא מדויקת בכל ספרות הדיוק שהוא מציג:

D = 137
N = 10
a = D
for n in range(N):
    a = (a + D/a) / 2
print(f"Newton's method: sqrt({D}) = {a:.10f}")

הקוד מבצע בסך הכל 10 איטרציות. לא רע! אבל האם אפשר להסתפק בפחות? אם תנסו להריץ, תראו שגם עבור \( N=8 \) מקבלים את אותה התוצאה, אבל לפני כן לא. אבל… האם באמת היינו צריכים להתחיל מ-\( D \)? האם אין דרך טובה יותר לנחש ערך התחלתי? ובכן, יש שלל דרכים, הנה אחת פשוטה: נסתכל כמה ביטים נדרשים כדי לייצג את \( D \) בזיכרון, ניקח רק חצי מהן ואז ניקח מספר שמיוצג על ידי כמות הביטים הזו - הוא יהיה בערך מסדר גודל כמו השורש של \( D \). הנה דרך פשוטה לעשות את זה בפייתון:

a = 2 ** (D.bit_length() // 2)

אם נשתמש בדרך הזו, מספר האיטרציות שצריך בשביל רמת הדיוק שלנו יקטן ל-\( N=4 \). לא רע בכלל!

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

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

\( 1-\alpha+t_{2}\alpha^{2}+t_{3}\alpha^{3} \)

ומציג במפורש את הפתרון הכללי שהוא מצא עבורה:

\( \alpha=\sum_{m_{2}\ge0}\sum_{m_{3}\ge0}\frac{\left(2m_{2}+3m_{3}\right)!}{\left(1+m_{2}+2m_{3}\right)!m_{2}!m_{3}!}t_{2}^{m_{2}}t_{3}^{m_{3}} \)

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

\( f\left(x\right)=x^{3}-2x-5=0 \)

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

\( Q\left(t_{2},t_{3}\right)=1+\left(t_{2}+t_{3}\right)+\left(2t_{2}^{2}+5t_{2}t_{3}+3t_{3}^{2}\right)+\left(5t_{2}^{3}+21t_{2}^{2}t_{3}+28t_{2}t_{3}^{2}+12t_{3}^{3}\right) \)

ועכשיו, כדי לפתור משוואה כללית \( c_{0}-c_{1}x+c_{2}x^{2}+c_{3}x^{3}=0 \), הנוסחה שהמאמר מצא אומרת לנו לחשב את הביטוי שהם מסמנים ב-\( K\left(c_{0},c_{1},c_{2},c_{3}\right) \) ומוגדר כך:

\( K\left(c_{0},c_{1},c_{2},c_{3}\right)=\frac{c_{0}}{c_{1}}Q\left(\frac{c_{0}c_{2}}{c_{1}^{2}},\frac{c_{0}^{2}c_{3}}{c_{1}^{3}}\right) \)

והם מציבים בו את המקדמים של \( f\left(x\right)=x^{3}-2x-5 \), כלומר מחשבים את \( K\left(-5,2,0,1\right) \) ומקבלים… משהו שהוא בערך \( -999.082031 \), מה שהם מכנים ``clearly a fail’’. זו ההתייחסות הכי ישירה שראיתי במאמר לכך שבכלל רדיוס ההתכנסות (שבבירור לא מתקיים כאן) הוא רלוונטי.

אבל הכישלון הזה נותן להם את ההזדמנות להראות איך מתגברים על זה. הם אומרים ש-\( x=2 \) הוא קירוב ראשון סביר (לא אתווכח עם זה) אז במקום לפתור את הבעיה “איזה ערך צריך להציב ב-\( f \) כדי לקבל 0” הם מנסים לפתור את הבעיה “כמה צריך לזוז מהערך \( x=2 \) כדי ש-\( f \) יקבל 0” ואת זה עושים פורמלית על ידי הגדרת \( g\left(x\right)=f\left(2+x\right)=x^{3}+6x^{2}+10x-1 \) ואז חישוב של \( K\left(-1,-10,6,1\right)=0.0945345708\ldots \) וזה יוצא קירוב נכון ב-4 הספרות הראשונות (הערך האמיתי הוא בערך \( 2.0945514815423\ldots \)).

אוקיי, מעניין. מה יש לניוטון-רפסון לומר בעניין הזה? הנוסחה של ניוטון-רפסון שמופעלת על \( f\left(x\right)=x^{3}-2x-5 \) נותנת את הסדרה

\( a_{n+1}=a_{n}-\frac{f\left(a_{n}\right)}{f^{\prime}\left(a_{n}\right)}=a_{n}-\frac{a_{n}^{3}-2a_{n}-5}{3a_{n}^{2}-2}=\frac{2a_{n}^{3}+5}{3a_{n}^{2}-2} \)

בואו נרוץ על זה ישירות, החל מהקירוב \( a_{0}=2 \) שהם הציעו:

N = 4
a = 2
for n in range(N):
    a = (2*a**3+5) / (3*a**2-2)
print(f"Newton's method: {a:.10f}")

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

עדיין, מאוד מעניין להשוות בין שני הדברים שקיבלנו פה. בניוטון-רפסון קיבלנו את הביטוי \( a_{n+1}=\frac{2a_{n}^{3}+5}{3a_{n}^{2}-2} \), שהוא איטרציה של פונקציה רציונלית. פונקציה רציונלית, נזכיר, היא פונקציה שהיא מנה של שני פולינומים, משהו מהצורה \( \frac{p\left(x\right)}{q\left(x\right)} \). לעומת זאת, ה-\( Q\left(t_{2},t_{3}\right) \) שהמאמר השתמש בו הוא פולינום (בשני משתנים). אבל קצת קשה להשוות את שתי הסיטואציות, כי אחרי שמציבים ערכים מספריים ב-\( Q \) הסיפור נגמר - מקבלים את הקירוב שרצינו - בעוד שב-\( a_{n+1}=\frac{2a_{n}^{3}+5}{3a_{n}^{2}-2} \) חלק מהחישוב כבר בוצע בזה שהגעתי בכלל לפונקציה רציונלית יפה; מה שנשאר הוא החישובים של האיטרציה, שזה משהו שבכלל לא קיים בשיטה הקודמת. מצד שני, ראינו שהשיטה הקודמת נכשלת ודרשה בעצמה ביצוע של סוג של איטרציה - החלפה של \( x \) ב-\( x+2 \), מה שדורש חישוב משל עצמו. במילים אחרות - השוואה בין השיטות היא עסק רציני יותר ממה שהמאמר באמת מנסה להיכנס אליו, ואני מנחש בזהירות שאם היה לו שיפור משמעותי להציג ביחס לניוטון-רפסון הוא היה מרחיב על העניין הזה, כי זו באמת הייתה תוצאה מהממת.

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

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

\( f\left(x\right)=c_{n}x^{n}+c_{n-1}x^{n-1}+\ldots+c_{0} \)

הנגזרת של זה קלה מאוד לחישוב:

\( f^{\prime}\left(x\right)=nc_{n}x^{n-1}+\left(n-1\right)c_{n-1}x^{n-2}+\ldots+c_{1} \)

עכשיו, \( x-\frac{f\left(x\right)}{f^{\prime}\left(x\right)} \) דורש לכפול את \( x \) במכנה ולחסר מזה את המונה. גם את זה קל לעשות ידנית, כי

\( xf^{\prime}\left(x\right)=nc_{n}x^{n}+\left(n-1\right)c_{n-1}x^{n-1}+\ldots+c_{1}x \)

ולכן נקבל

\( x-\frac{f\left(x\right)}{f^{\prime}\left(x\right)}=\frac{\left(n-1\right)c_{n}x^{n}+\left(n-2\right)c_{n-1}x^{n-1}+\ldots+c_{2}x^{2}-c_{0}}{nc_{n}x^{n-1}+\left(n-1\right)c_{n-1}x^{n-2}+\ldots+c_{1}} \)

הנה קוד שעושה את זה:

def newton(coeffs, x0, N):
    numerator = [(n-1) * c for n, c in enumerate(coeffs)]
    denominator = [n * c for n, c in enumerate(coeffs[1:], start=1)]
    x = x0
    for _ in range(N):
        f_x = sum(c * x**n for n, c in enumerate(numerator))
        f_prime_x = sum(c * x**n for n, c in enumerate(denominator))
        if f_prime_x == 0:
            raise ValueError("Derivative is zero")
        x = f_x / f_prime_x
    return x

אל מול הקוד הזה אני רוצה להעמיד קוד שמדמה את מה שהמאמר עושה עם מספרי היפר-קטלן: בהינתן פולינום \( f\left(x\right) \) ממעלה \( k \) שמנסים למצוא לו שורש, מייצרים את הפולינום מרובה המשתנים \( Q\left(t_{2},t_{3},\ldots,t_{k}\right) \). בהינתן קירוב התחלתי \( x_{0} \) לשורש שאנחנו מנסים למצוא, מחשבים את \( g\left(x\right)=f\left(x+x_{0}\right)=c_{0}-c_{1}x+c_{2}x^{2}+\ldots+c_{k}x^{k} \) ואז מחשבים את \( \frac{c_{0}}{c_{1}}Q\left(\frac{c_{0}c_{2}}{c_{1}^{2}},\frac{c_{0}^{2}c_{3}}{c_{1}^{3}},\ldots,\frac{c_{0}^{k-1}c_{k}}{c_{1}^{k}}\right) \).

בשביל לחשב את \( Q \) צריך לדעת לחשב את מספרי היפר-קטלן, \( C_{\mathbf{m}}=\frac{\left(2m_{2}+3m_{3}+4m_{4}+\ldots\right)!}{\left(1+m_{2}+2m_{3}+3m_{4}+\ldots\right)!m_{2}!m_{3}!m_{4}!\cdots} \). חישוב של זה הוא קצת כאב ראש בצורה ישירה כי יש לנו המון מספרים עם עצרת, אז נקבל מנה של שני מספרי ענק וזה ייצא לא מדויק. למרבה השמחה, אפשר לרתום לוגריתמים לעזרתנו. כפי שהסברתי בפוסט שלי על לוגריתמים, הם הומצאו כדי לעזור לנו לחשב מכפלות ומנות של מספרים גדולים, והם עדיין משמשים טוב לזה. אם אני אפעיל \( \ln \) על שני האגפים, אני אקבל

\( \ln C_{\mathbf{m}}=\ln\left(\left(2m_{2}+3m_{3}+4m_{4}+\ldots\right)!\right)-\ln\left(\left(1+m_{2}+2m_{3}+3m_{4}+\ldots\right)!\right)-\sum_{k=2}\ln\left(m_{k}!\right) \)

לוגריתם של עצרת הוא כלי כל כך שימושי בחישובים, שספריות מתמטיות סטנדרטיות לרוב מציעות אותו כפונקציה בסיסית. ליתר דיוק, לוגריתם של מה שנקרא פונקציית גמא, \( \Gamma \), שהיא פונקציה שמקיימת \( \Gamma\left(n+1\right)=n! \), ובנוסף לכך יש לה שלל תכונות נחמדות שלא ניכנס אליהן כאן. השורה התחתונה היא שהקוד הזה מחשב את \( C_{\mathbf{m}} \) בצורה מדויקת ויעילה, תוך התבססות על כך שהוא צריך לצאת מספר טבעי ולכן אפשר להסתמך על חישוב שהוא טיפה לא מדויק ואז לעגל:

def hyperC(m):
    A = sum((i + 2) * m_i for i, m_i in enumerate(m))
    B = sum((i + 1) * m_i for i, m_i in enumerate(m))
    
    log_numerator = math.lgamma(A + 1)
    log_denominator = math.lgamma(B + 2) + sum(math.lgamma(m_i + 1) for m_i in m)

    return round(math.exp(log_numerator - log_denominator))

עם הקוד הזה וספריית האלגברה הסימבולית sympy אפשר לייצר את \( Q \). הפרמטרים שלנו הם \( N \) שהוא הסכום המקסימלי של אברי \( \mathbf{m} \) (בדוגמה שלהם, \( N=3 \)) ו-\( k \) שהוא המימד של \( \mathbf{m} \), כלומר כמה משתנים יש שם. ראשית אני מגדיר פונקציה רקורסיבית, partitions, שעוברת על כל הדרכים לחלק את המספר \( N \) לסכום של \( k \) מספרים טבעיים:

def partitions(N, k):
    if k == 1:
        return [[N]]
    result = []
    for n in range(N+1):
        for p in partitions(N-n, k-1):
            result.append([n] + p)
    return result

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

from sympy import symbols, Add
def generate_polynomial(N, k, t=None):
    if t is None:
        t = symbols(f't2:{k+2}')
    monomials = []
    for n in range(N+1):
        for m in partitions(n, k):
            coeff = hyperC(m)
            term = coeff
            for i, m_i in enumerate(m):
                if m_i != 0:
                    term *= t[i]**m_i
            monomials.append(term)
    F = Add(*monomials)
    return F

כל החישובים הללו “לא נחשבים” מבחינתי כשבאים למצוא פתרון למשוואה ספציפית, כי אפשר לעשות אותם באופן חד פעמי מראש - הרי \( Q \) לא תלוי במשוואה ספציפית, רק במספר המשתנים ובשאלה כמה \( N \) שלנו יהיה גדול (ככל ש-\( N \) גדול יותר הקירוב יהיה טוב יותר אבל נצטרך לסכום \( \Theta\left(N^{k}\right) \) איברים).

לסיום, אני צריך דרך כלשהי לבצע את שינוי המקדמים \( g\left(x\right)=f\left(x+a\right) \). כאן אני יכול להשתמש בבינום של ניוטון, באופן הבא: אם \( f\left(x\right)=\sum_{k=0}^{n}a_{k}x^{k} \) אז

\( f\left(x+a\right)=\sum_{k=0}^{n}a_{k}\left(x+a\right)^{k}=\sum_{k=0}^{n}a_{k}\sum_{i=0}^{k}{k \choose i}x^{i}a^{k-i} \)

אפשר לשנות את סדר הסכימה כדי לאגד לכל \( x^{i} \) את כל המקדמים שלו:

\( =\sum_{i=0}^{n}\left(\sum_{k=i}^{n}a_{k}{k \choose i}a^{k-i}\right)x^{i} \)

כלומר, נגדיר

\( b_{i}=\sum_{k=i}^{n}a_{k}{k \choose i}a^{k-i} \)

ונקבל ש-\( g\left(x\right)=f\left(x+a\right)=\sum_{i=0}^{n}b_{i}x^{i} \)

הנה קוד שעושה את החישוב הזה:

def shift_polynomial(coeffs, a):
    n = len(coeffs)
    shifted = [0] * n
    for i in range(n):
        shifted[i] = sum(
            coeffs[k] * math.comb(k, i) * a**(k-i)
            for k in range(i, n)
        )
    return shifted

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

def catalan(coeffs, x0, N):
    coeffs = shift_polynomial(coeffs, x0)
    c0 = coeffs[0]
    c1 = -coeffs[1]
    k = len(coeffs) - 2
    t = symbols(f't2:{k+2}')
    Q = generate_polynomial(N, k, t)
    subs_dict = {t[i-2]: coeffs[i]*c0**(i-1)/c1**i for i in range(2,len(coeffs))}
    return x0 + (c0/c1) * Q.subs(subs_dict)

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

ועכשיו, אפשר לעשות בדיקה חפיפניקית כדי לראות מי מצליח יותר - ניוטון או קטלן?

הנה קוד לדוגמא שעושה בדיקה כזו:

coeffs = [-5, -2, 0, 1]
x0 = 2
N = 5
result = catalan(coeffs, x0, N)
print(f"Catalan method result: {result:.10f}")
result = newton(coeffs, x0, N)
print(f"Newton method result: {result:.10f}")

יש כאן בבירור השוואה בין תפוזים ותפוחים - אני משתמש באותו \( N \) בתור “פרמטר הקירוב” גם עבור ניוטון וגם עבור קטלן, אבל בשיטת ניוטון \( N \) הוא בסך הכל מספר האיטרציות שמבצעים, ובשיטה של המאמר \( N \) הוא חסם על גודל סכום האיברים ב-\( \mathbf{m} \). כלומר, בעוד שהגדלת \( N \) ב-1 אצל ניוטון פשוט מוסיפה עוד איטרציה אחת, שרמת הסיבוכיות שלה דומה לקודמותיה, בשיטת קטלן ההגדלה הזו מוסיפה \( \Theta\left(N^{k-1}\right) \) איברים לסכום. במילים אחרות, השימוש ב-\( N \) בצורה כזו עוזר לקטלן כי הוא מאפשר לו להגדיל את מספר הצעדים שהוא מבצע הרבה יותר מאשר ניוטון.

זה לא מפריע לי.

כשמריצים את הקוד למעלה, עם הפרמטרים \( x_{0}=2 \) ו-\( N=5 \), מקבלים עבור ניוטון את התוצאה \( 2.0945514815 \) (שהיא מדויקת בכל הספרות) ועבור קטלן את \( 2.0945508795 \) (שהיא עדיין די מדויקת אבל רק עד ה-55). לרמת הדיוק של ניוטון קטלן הגיע ב-\( N=13 \); בשלב הזה ניוטון כבר מקבל \( 2.0945514815423269539 \) (המאמר נוקב ב-\( 2.0945514815423265915 \) בתור הקירוב של 19 הספרות הראשונות). בקיצור, על הדוגמא שלהם קטלן לא באמת נותן תחרות לניוטון.

אם אני מתחיל מקירוב יותר נאיבי, \( x_{0}=0 \), אז ניוטון צריך שאבקש \( N=19 \) כדי לקבל את הקירוב של 10 הספרות שראינו קודם (כמובן, בעולם האמיתי לא צריך להגיד לניוטון כמה איטרציות לעשות; מבקשים ממנו לעצור אחרי שהוא רואה שהפעלת איטרציה קיבעה את 10 הספרות הראשונות) אבל קטלן, כמו שהבטיחו במאמר, נכשל לגמרי ונותן \( -108653171492152000000000 \). אם תשאלו אותי, זה יתרון גדול של ניוטון; אפילו אם אגדיר \( x_{0}=-1000000000000 \), עבור \( N=100 \) אקבל את אותו קירוב לפתרון. כשהפונקציה שמנסים לטפל בה היא נחמדה (ופולינום היא פונקציה נחמדה), ניוטון זה כמו מגנט שנדבק בכוח אל הפתרון די מהר. השיטה של המאמר פשוט לא יודעת לעשות את זה - היא תלויה הרבה יותר בכך שנמצא לה קירוב ראשוני מתאים.

אז הרושם הראשוני שהשיטה במאמר לא יודעת לטפל ב”כל” משוואה אלא רק במשוואות שהפרמטרים שלהן נופלות תחת רדיוס ההתכנסות של הטור הרלוונטי - הרושם הזה שגוי, בהחלט אפשר ליצור אלגוריתם טוב שמטפל בכל משוואה (כמעט… לא התייחסתי למקרה של \( c_{1}=0 \)) אבל האלגוריתם הזה יהיה רגיש לתנאי ההתחלה, הרבה יותר מאשר ניוטון רגיש. וזה קצת נשמע מוזר כי אם רק מסתכלים על הכותרת של המאמר לא ברור בכלל שיש צורך שיהיו “תנאי התחלה” שכאלו.

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

import random
def random_coefficients(degree, lower_bound=-10, upper_bound=10):
    return [random.randint(lower_bound, upper_bound) for _ in range(degree + 1)]
random.seed(42)
coeffs = random_coefficients(10, -10, 10)
print(coeffs)
x0 = 1.4
N = 5
result = catalan(coeffs, x0, N)
print(f"Catalan method result: {result:.10f}")
result = newton(coeffs, x0, N)
print(f"Newton's method result: {result:.10f}")

במקרה הנוכחי בחרתי פולינום ממעלה 10 וקיבלתי את המקדמים \( [10,-7,-10,-2,-3,-3,-6,-7,7,-8,8] \). אחר כך הרצתי ניוטון בצד עם המון איטרציות כדי לדעת מה הערך ה”נכון” שאנחנו מחפשים, וראיתי שהוא קרוב ל-\( 1.4 \) והזנתי את זה לקטלן. למה \( N=5 \) ולא משהו גדול יותר? כי בשלב הזה, מכיוון שהפולינום הוא ממעלה גבוהה אז ה-\( k \) שבחזקה שלו מעלים את \( N \) הוא די גבוה, ולכן זמן הריצה כבר מורגש - לקוד הזה לקחו יותר מ-15 שניות לרוץ, למרות שניוטון מסיים מייד. אחרי הריצה הזו ניוטון השיג \( 1.4042602427 \) (זו התוצאה הנכונה, במסגרת ספרות הדיוק) וקטלן השיג \( 1.4042602426 \), שזה… יפה מאוד! כמעט אותו דבר! אבל כמובן, זה בזכות קירוב התחלתי טוב; אם אני מתחיל מ-\( x_{0}=2 \) קטלן טיפה פחות מצליח, ומקבל \( 1.6666226398 \) לעומת ה-\( 1.4187182359 \) של ניוטון. עבור ערכים גדולים יותר של \( x_{0} \) קטלן מחזיר תוצאות פחות מדויקות אבל לא מתחרבש לגמרי אפילו עבור \( x_{0}=100 \). זה לא כל כך מפתיע; כשמבצעים את ההזזה \( g\left(x\right)=f\left(x+a\right) \) זה מנפח מאוד את המקדמים הקטנים ופחות את הגדולים. ואז מציבים ערך מהצורה \( \frac{c_{0}^{i-1}c_{i}}{c_{1}^{i}} \) בפולינום. מה שקורה הוא ש-\( c_{0}^{i-1} \)מבטל “בערך” את ה-\( c_{1}^{i-1} \) שבמכנה ומשאיר \( \frac{c_{i}}{c_{1}} \), ואם \( c_{1} \) גדול מאוד ביחס ל-\( c_{i} \) נקבל מספר קטן - כלומר, המספרים שנציב יהיו בסיכוי טוב בתוך רדיוס ההתכנסות. לכן דווקא הניחוש ההתחלתי \( x_{0}=0 \), למרות שהוא קרוב הרבה יותר לתוצאה האמיתית מאשר \( x_{0}=100 \), הולך להוביל לקטסטרופה. העניין הוא שעבור \( x_{0}=100 \) אמנם לא נקבל קטסטרופה אלא תוצאה שהיא הגיונית, אבל היא לא קירוב טוב במיוחד (מקבלים \( 80.6474783702 \) עבור \( N=5 \)).

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

בואו נתלונן על הצגה לא נאמנה של המתמטיקה בתקשורת, כי זה כבר מזמן לא קרה

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

נתחיל מהכותרת הראשונה שבה נתקלתי: Mathematician solves algebra’s oldest problem using intriguing new number sequences. היא מגיעה מהפרסום כאן, שהוא לא כתבה עיתונאית אלא פרסום של האוניברסיטה עצמה. ככזה, הוא יחסית מדויק. עדיין, יש דבר או שניים שמרגיזים אותי.

למשל, הם כותבים שם ש-

A general method for solving ‘higher order’ polynomial equations, where x is raised to the power of five or higher, has historically proven elusive.
Now, UNSW Honorary Professor Norman Wildberger has revealed a new approach using novel number sequences, outlined in a recent publication with computer scientist Dr. Dean Rubine.

מה שמקפיץ אותי הוא ה-novel number sequences - הרי מספרי ההיפר-קטלן הם לא חדשים; המאמר מצטט ספרות יפה שעוסקת בהם עוד מהמאה ה-19. החידוש במאמר הוא להסתכל על הפונקציה היוצרת שלהם ולהגיד - היי, תראו, זה סוג של נותן פתרון של משוואה.

הדבר שיותר מרגיז אותי מגיע אחרי התיאור של גלואה וההוכחה לאי הפתירות על ידי רדיקלים של משוואות ממעלה חמישית ומעלה:

Approximate solutions for higher-degree polynomials have since been developed and are widely used in applications but, Prof. Wildberger says, these don’t belong to pure algebra.

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

שנית, מה בכלל המשמעות של “pure algebra” כאן? בסופו של דבר, הדרך לקבל פתרון קונקרטי למשוואה בשיטה של המאמר היא להציב מספרים בתור טור אינסופי ולקוות שיתכנס. זה לגמרי פתרון אנליטי. לכן אני משער שב”אלגברה טהורה” הכוונה למה שראינו בפוסט הקודם - לכך שכדי להגדיר שוויון ברמת הפונקציות היוצרות לא צריך בכלל חשבון דיפרנציאלי ואינטגרלי. זו הנקודה שהמאמר אכן מקפיד עליה - לומר שהפתרון הוא “כטור חזקות פורמלי” אבל כבר אמרתי שאני לא מבין איך זה בעצם פתרון - כי בטור חזקות פורמלי מה שמעניין אותנו הוא לקודד את המקדמים של הטור, ואילו כאן הטור לכאורה מקודד מספר שמתקבל על ידי הצבה.

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

הלאה, בואו נעבור למאמר עם הכותרת “The Oldest Algebra Problem Solved”: Australian Mathematician Cracks Ancient Mystery That Baffled Minds for Over 4,000 Years” שאפשר לראות כאן. המאמר נפתח בסתם בלבול תמים שגורם לו לחשוב שנוסחת השורשים (הנוסחה לפתרון משוואה ממעלה שניה) היא מה שנותן לנו את הפתרון למשוואות ממעלה שלישית ורביעית (הו לא, כל כך לא). מה שבאמת מרגיז אותי פה הוא שהמאמר כותב ש”בדיקות על משוואה מפורסמת ממעלה שלישית בה השתמש וואליס במאה ה-17 הדגימו את יעילות השיטה” - אבל הם לא אומרים איך וואליס השתמש במשוואה הזו; כזכור, הוא השתמש בה כדי להדגים את שיטת ניוטון - השיטה שמניבה למשוואה הזו פתרונות טובים יותר. יותר מזה, המאמר עובר להתלונן על כך שעד כה היו רק פתרונות מקורבים שלא שייכים לאלגברה “טהורה” אבל השיטה החדשה היא “יותר מדויקת”.

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

מה עם “200-year-old “algebra wall” shattered with a bold new approach” שנמצא כאן? יש בו פסקה מעצבנת במיוחד:

Mathematician Norman Wildberger, an Honorary Professor at Australia's University of New South Wales, and computer scientist Dean Rubine have thrown out the rulebook and presented a new way to solve polynomial equations that go beyond x to the power of four -- something that has only been resolved with "approximate solutions." While this won't mean a whole lot to school students in math class, accuracy in answering higher-order polynomial problems could have huge implications in the fields of science and technology.

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

וזה נמשך:

“One of the equations we tested was a famous cubic equation used by Wallis in the 17th century to demonstrate Newton's method," Wildberger explained. "Our solution worked beautifully."

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

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

If you're still with me, this new method solves for equations that can't generally be resolved using traditional methods, like using root-taking approaches. In this sense, it breaks through a centuries-old mathematical wall. The novel approach removes the limitations presented by the kind of simple finite formula we were taught at school.

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

ומה עם “Researchers Solve “Impossible” Math Problem After 200 Years”? טוב, זה כמעט מועתק מילה במילה מהקומוניקט של האוניברסיטה, אז אין טעם להתעסק גם בו - אבל זה ממחיש את העניין. כל המאמרים הללו נכתבו על ידי אנשים שדי בבירור לא מבינים את הנושא ופשוט מתבססים על מה שהאוניברסיטה סיפרה להם, והאוניברסיטה סיפרה להם את האמת… אבל לא את כל האמת. זה הטריק הכי ישן בספר, כמובן.

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

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

נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com