הבעיה העשירית של הילברט – איך משוואת פל קשורה לכל העניין?

בואו נחזור לדבר על הבעיה העשירית של הילברט שעזבתי בשיא המתח – בדיוק לפני החלק הטכני ביותר, שנתחיל לטפל בו הפעם. תזכורת קטנה למי שאין לו כוח לקרוא את הפוסטים הקודמים: המטרה שלנו היא להוכיח שהפונקציה $latex f\left(n,k\right)=n^{k}$ – "הפונקציה האקספוננציאלית" – היא דיופנטית. כלומר, שקיימת מערכת של משוואות פולינומיות בשלמים עם המון משתנים ששלושה מהם הם $latex n,k,m$ כך שלכל הצבה של ערכים ב-$latex n,k,m$, יש פתרון למערכת המשוואות אם ורק אם $latex m=n^{k}$. אפשר, כמובן, להתחיל מלהציג את מערכת המשוואות הזו, אבל היא כוללת שתיים-עשרה משוואות ולא מעט משתנים וממבט ראשון לא יהיה ברור מה הולך שם בכלל, אז נחכה עם זה קצת בסבלנות. לפני כן נטפל בבעיה לכאורה לא קשורה, אבל כזו שתוביל אותנו כמעט ישירות אל הפונקציה האקספוננציאלית: משוואת פל.

כחלק מההכנה לפוסט הזה כתבתי פוסט על משוואת פל שאין צורך לחזור על כל מה שנאמר בו (מרטין דיוויס, במאמר על הבעיה העשירית של הילברט שאני מתבסס עליו, מוכיח מאפס את התכונות שהוא צריך באופן ישיר), אבל בואו נחזור על עיקרי הדברים הרלוונטיים. אם $latex d$ הוא מספר טבעי שאינו ריבוע, אז משוואת פל עם הפרמטר $latex d$ היא המשוואה $latex x^{2}-dy^{2}=1$ (בפוסט שלי השתמשתי ב-$latex N$ אבל עכשיו אני הולך לפי סגנון הכתיבה של דיוויס). מה שמעניין במשוואת פל הוא שלפתרונות שלה יש מבנה יפה במיוחד: קיים פתרון אחד שנקרא הפתרון היסודי ונסמן אותו בתור $latex \left(x_{1},y_{1}\right)$, כך שכל פתרון אחד מתקבל כמעין חזקה של הפתרון היסודי.

ליתר דיוק, מה שעושים הוא להסתכל על המספר האלגברי $latex x_{1}+\sqrt{d}y_{1}$ ולקחת את החזקות שלו, כלומר מגדירים $latex x_{n}+\sqrt{d}y_{n}=\left(x_{1}+\sqrt{d}y_{1}\right)^{n}$. למי שאין לו כוח להתעסק עם שורשים אפשר לעשות את זה גם באופן ישיר בצורה הבאה: אם $latex \left(x_{n},y_{n}\right)$ ו-$latex \left(x_{k},y_{k}\right)$ הם שני פתרונות של משוואת פל, אז אפשר לבנות מהם על ידי "כפל" פתרון חדש $latex \left(x_{t},y_{t}\right)$ שנראה כך:

$latex x_{t}=x_{n}x_{k}+dy_{n}y_{k}$

$latex y_{t}=x_{n}y_{k}+x_{k}y_{n}$

זוכרים משהו מזה? יפה. לא זוכרים? לא נורא, זה מה שצריך לזכור. בואו נעבור למה שדיוויס עושה. ראשית כל, למה הוא בכלל מתעניין במשוואת פל? ובכן, מצד אחד זו משוואה דיופנטית פשוטה – תנאי כמו $latex x^{2}-dy^{2}=1$ אפשר לקודד עם האמצעים שמותר לנו להשתמש בהם. מצד שני, הקטע הזה של "כל פתרון הוא חזקה של הפתרון היסודי" מתנהג כמו, ובכן, חזקה. זהו ה"גשר" שאנו זקוקים לו בין משהו דיופנטי ומשהו אקספוננציאלי. לדעתי זה די מגניב שזה נעשה באמצעות משוואת פל.

בשביל הצרכים שלו, דיוויס נזקק רק למשוואות פל מסוג מסויים: משוואות מהצורה $latex x^{2}-dy^{2}=1$ (עד כאן הכל כרגיל) כך ש-$latex d=a^{2}-1$, עבור $latex a>1$ כלשהו. כלומר, המשוואות $latex x^{2}-3y^{2}=1$, $latex x^{2}-8y^{2}=1$, $latex x^{2}-15y^{2}=1$ וכדומה (כזכור, אם $latex d$ הוא ריבוע "ממש", כלומר אם $latex d=a^{2}$, אז למשוואה אין פתרונות) למשוואות שבהן $latex d=a^{2}-1$ קל מאוד לתת פתרון: $latex x=a,y=1$ תמיד פותר את המשוואה, שהרי $latex a^{2}-\left(a^{2}-1\right)1^{2}=a^{2}-a^{2}+1=1$. האם זהו הפתרון היסודי, כלומר הפתרון שבעזרת "חזקות" שלו (ביחס לפעולת ה"כפל" שהצגתי למעלה) אפשר לקבל את כל שאר הפתרונות הלא טריוויאליים של המשוואה?

כדי להוכיח את זה מספיק להוכיח שאם $latex \left(x,y\right)$ הוא פתרון כלשהו של המשוואה, אז לא ייתכן שמתקיים $latex 1<x+y\sqrt{d}<a+\sqrt{d}$, כלמר אין פתרון למשוואה "בין" שני הפתרונות הבסיסיים $latex \left(1,0\right)$ ו-$latex \left(a,1\right)$. זה מספיק כי אם $latex a+\sqrt{d}<x+y\sqrt{d}$, אז בוודאי שגם $latex a+\sqrt{d}<\left(x^{2}+dy^{2}\right)+\left(xy+yx\right)$, כלומר החזקה השניה של הפתרון $latex \left(x,y\right)$ לא יכולה לתת את $latex \left(a,1\right)$, וגם החזקה השלישית וכן הלאה, מה שמאלץ את $latex \left(a,1\right)$ להיות הפתרון היסודי.

אם כן, בואו נניח בכשלילה ש-$latex \left(x,y\right)$ הוא פתרון של המשוואה שגם מקיים $latex 1<x+y\sqrt{d}<a+\sqrt{d}$. כעת, מכיוון שמתקיים $latex x^{2}-dy^{2}=1$ הרי שאפשר לפרק את הביטוי הזה ולקבל

$latex \left(x-y\sqrt{d}\right)\left(x+y\sqrt{d}\right)=x^{2}-dy^{2}=1=a^{2}-d=\left(a-\sqrt{d}\right)\left(a+\sqrt{d}\right)$

בואו נחלק את שני האגפים ב-$latex x+y\sqrt{d}$. נקבל:

$latex x-y\sqrt{d}=a-\sqrt{d}\cdot\frac{a+\sqrt{d}}{x+y\sqrt{d}}>a-\sqrt{d}$

כי הרי הביטוי $latex \frac{a+\sqrt{d}}{x+y\sqrt{d}}$ הוא גדול מ-1 אם מניחים ש-$latex x+y\sqrt{d}<a+\sqrt{d}$. עכשיו, נכפול את שני האגפים במינוס 1, הסימן של אי השוויון יתהפך ולבסוף נקבל:

$latex -x+y\sqrt{d}<-a+\sqrt{d}$

אם נחבר את זה לאי השוויון $latex x+y\sqrt{d}<a+\sqrt{d}$ נקבל בסופו של דבר ש-$latex 2y\sqrt{d}<2\sqrt{d}$, כלומר $latex y<1$. זה לכשעצמו עדיין לגיטימי – אולי $latex y$ שלילי, או אפס? לכן אנו נזקקים לעוד תעלול. נשים לב לכך שעל פי הנחתנו, $latex x+y\sqrt{d}>1$ ולכן $latex \left(x-y\sqrt{d}\right)=\frac{1}{x+y\sqrt{d}}<1$, ולכן $latex -x+y\sqrt{d}>-1$, ואם נחבר את זה ל-$latex 1<x+y\sqrt{d}$ נקבל ש-$latex 0<y$, כלומר $latex 0<y<1$, כלומר $latex y$ בכלל לא מספר שלם, אבל רק מספרים שלמים הם פתרונות חוקיים של משוואת פל. זה מסיים את הסיפור. אני מודה, ההוכחה הזו היא לא הדבר הכי יפה בעולם.

עכשיו, משאנחנו יודעים מהו הפתרון היסודי, אפשר לתת סימון כללי לשאר הפתרונות החיוביים. מכיוון שהמשוואה שלנו תלויה גם ב-$latex d$, אבל את $latex d$ כתבנו בתור $latex a^{2}-1$, אנחנו משתמשים ב-$latex x_{n}\left(a\right)$ ו-$latex y_{n}\left(a\right)$ כדי לתאר את הפתרונות. פורמלית הסדרות הללו מוגדרות כך: $latex x_{0}\left(a\right)=1,y_{0}\left(a\right)=0$, ובאופן אינדוקטיבי:

$latex x_{n+1}\left(a\right)=ax_{n}\left(a\right)+dy_{n}\left(a\right)$

$latex y_{n+1}\left(a\right)=ay_{n}\left(a\right)+x_{n}\left(a\right)$

או בצורה טיפה יותר אלגנטית אבל לא מפורשת, $latex x_{n}\left(a\right)+y_{n}\left(a\right)\sqrt{d}=\left(a+\sqrt{d}\right)^{n}$. אבחנה חביבה של דיוויס בנקודה הזו היא שהנוסחה הזו דומה באופיה לנוסחת אוילר, $latex \cos\theta+i\sin\theta=e^{i\theta}$. כאן $latex \cos$ מיוצג על ידי $latex x_{n}\left(a\right)$, $latex \sin$ מיוצג על ידי $latex y_{n}\left(a\right)$, במקום $latex i$ יש לנו את $latex \sqrt{d}$ ובמקום $latex e^{i}$ יש לנו את $latex a+\sqrt{d}$. דיוויס מצביע על כך שניתן להשתמש בייצוג המעריכי הזה כדי לקבל בקלות נוסחאות לחיבור וחיסור (למעשה, כבר יש לנו את הנוסחה לחיבור…) שמזכירות את הנוסחאות המקבילות מטריגו – ושוב, לא במקרה! הדרך הכי טובה לפתח את הנוסחאות מטריגו היא לעבור דרך נוסחת אוילר שפשוט נותנת לנו אותן במתנה. אני מציע לכם לשחק קצת עם המשוואות ולהוכיח את הנוסחאות הללו לעצמכם בדרך הזו:

$latex x_{m\pm n}=x_{m}x_{n}\pm dy_{m}y_{n}$

$latex y_{m\pm n}=x_{n}y_{m}\pm x_{m}y_{n}$

שימו לב שכבר התעצלתי מלכתוב את ה-$latex \left(a\right)$ אחרי ה-$latex x_{n},y_{n}$ וכך גם אמשיך לעשות בהמשך אם זהותו המדויקת של ה-$latex a$ לא רלוונטית באותו רגע או ברורה מההקשר.

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

בתור התחלה, $latex x_{n},y_{n}$ הם זרים – אין להם מחלק משותף חיובי גדול מ-1. זה מסומן בתור $latex \left(x_{n},y_{n}\right)=1$. למה? פשוט: אם $latex d$ חיובי מחלק את $latex x_{n}$ ואת $latex y_{n}$ אז הוא בוודאי מחלק גם את $latex x_{n}^{2}$ ואת $latex dy_{n}^{2}$ ולכן גם מחלק את ההפרש ביניהם, שהוא 1. אם $latex d$הוא חיובי ומחלק את 1, הוא בהכרח 1 בעצמו.

קצת יותר מעניינת הטענה ש-$latex y_{n}$ מחלק את $latex y_{nk}$. זה מן הסתם נכון עבור $latex k=1$ אבל לערכים גדולים יותר יש צורך להוכיח זאת באינדוקציה, בעזרת נוסחת החיבור שלנו:

$latex y_{n\left(k+1\right)}=y_{nk+n}=x_{n}y_{nk}+x_{nk}y_{n}$

מהנחת האינדוקציה עולה ש-$latex y_{n}$ מחלק את $latex y_{nk}$ ולכן את $latex x_{n}y_{nk}$, וברור שהוא מחלק את $latex x_{nk}y_{n}$, ולכן קיבלנו ש-$latex y_{n}$ מחלק את $latex y_{n\left(k+1\right)}$. האם יש עוד איברים בסדרת ה-$latex y$-ים אותם $latex y_{n}$ יכול לחלק? מסתבר שלא. נניח ש-$latex y_{n}$ מחלק את $latex y_{t}$ אבל $latex n$ לא מחלק את $latex t$. אז אפשר לחלק אותם עם שארית, כלומר לכתוב $latex t=qn+r$ כאשר $latex 0<r<n$ היא השארית. נקבל: $latex y_{t}=x_{r}y_{nq}+x_{nq}y_{r}$. אם $latex y_{n}$ מחלק את הביטוי הזה, אז מכיוון שאנו יודעים שהוא מחלק את $latex y_{nq}$ נקבל שהוא חייב לחלק את $latex x_{nq}y_{r}$. כעת, $latex \left(y_{nq},x_{nq}\right)=1$ ולכן לא ייתכן ש-$latex y_{n}$ יחלק את $latex x_{nq}$, אחרת הוא היה גורם משותף שלו ושל $latex y_{nq}$. לכן בהכרח $latex y_{n}$ מחלק את $latex y_{r}$, אבל זה בלתי אפשרי כי $latex y_{n}>y_{r}$! סוף הסיפור.

אתם בוודאי תוהים לאן אני חותר עם כל התכונות הללו. המטרה היא למצוא משהו שאפשר לקודד דיופנטית איכשהו ויאפשר לנו לאפיין את הסדרות $latex x_{n},y_{n}$ במדויק. הכיוון המבטיח ביותר הוא תכונות של הסדרות הללו מודולו משהו. כזכור, $latex a\equiv_{n}b$ פירושו ש-$latex n$ מחלק את $latex a-b$ (ובמילים אחרות, שהשארית של חלוקת $latex a$ ו-$latex b$ ב-$latex n$ היא זהה). הנה דוגמה ראשונה לתכונת מודולו:

$latex y_{nk}\equiv_{y_{n}^{3}}kx_{n}^{k-1}y_{n}$

טוב, במבט ראשון המשוואה הזו נראית מונפצת לגמרי. איך בכלל הגיעו אליה? התשובה היא שמישהו כנראה ניסה, על מנת להבין את הסדרות $latex x_{n},y_{n}$, לשחק איתן כמה שיותר. הוא כנראה הסתכל על האיבר $latex x_{nk}+y_{nk}\sqrt{d}=\left(x_{n}+y_{n}\sqrt{d}\right)^{k}$ ושאל את עצמו – הממ, מה יקרה אם פשוט נפתח את הסוגריים באמצעות הבינום של ניוטון (הדרך ה"רגילה" לפתוח סוגריים שכאלה)? התשובה היא שנקבל:

$latex \left(x_{n}+y_{n}\sqrt{d}\right)^{k}=\sum_{i=0}^{k}{k \choose i}x_{n}^{k-i}\left(y_{n}\sqrt{d}\right)^{i}=\sum_{i=0}^{k}{k \choose i}x_{n}^{k-i}y_{n}^{i}d^{\frac{i}{2}}$

שימו לב ל-$latex d^{\frac{i}{2}}$. עבור הערכים הזוגיים של $latex i$ זהו מספר טבעי, ולכן כל הגורם $latex {k \choose i}x_{n}^{k-i}y_{n}^{i}d^{\frac{i}{2}}$ יתרום ל-$latex x_{nk}$ במקרה הזה. עבור $latex i$ אי זוגי נקבל $latex \sqrt{d}$ בחזקת משהו אי זוגי, ולכן כל הגורם יתרום ל-$latex y_{nk}\sqrt{d}$. אם נחלק ב-$latex \sqrt{d}$ את שני האגפים נקבל שהגורם הזה תורם $latex {k \choose i}x_{n}^{k-i}y_{n}^{i}d^{\frac{i-1}{2}}$ ל-$latex y_{nk}$. לכן קיבלנו:

$latex y_{nk}=\sum_{\begin{array}{c}i=1\\i\mbox{ odd}\end{array}}^{k}{k \choose i}x_{n}^{k-i}y_{n}^{i}d^{\frac{i-1}{2}}$

עכשיו משתמשים בתעלול שמשתמשים בו כל הזמן בתורת המספרים (תצטרכו להאמין לי). שמים לב לכך שפרט לאיבר הראשון בסכום, זה שמתקבל עבור $latex i=1$, עבור כל שאר האיברים מתקיים $latex i\ge3$ ולכן $latex y_{n}^{3}$ מחלק את כולם, ולכן מודולו $latex y_{n}^{3}$ הם נעלמים (זו הסיבה שבגללה בוחרים $latex y_{n}^{3}$ דווקא – כדי שהמודולוס יהיה גדול יחסית ועדיין יישאר לנו ביטוי פשוט יחסית. לכן נישאר רק עם האיבר הראשון:

$latex y_{nk}\equiv_{y_{n}^{3}}{k \choose 1}x_{n}^{k-1}y_{n}=kx_{n}^{k-1}y_{n}$

פתאום הביטוי הזה כבר לא נראה מפחיד כל כך. לפחות לא בשבילי. כמובן, עדיין לא ברור בשביל מה הוא טוב. אז הנה המסקנה המיידית שלו: מה קורה אם במשוואה שקיבלנו נציב $latex k=y_{n}$? נקבל מייד

$latex y_{ny_{n}}\equiv_{y_{n}^{3}}y_{n}x_{n}^{y_{n}-1}y_{n}=y_{n}^{2}x_{n}^{y_{n}-1}$

שזה אומר, בצורה הכי מפורשת שרק אפשר, ש-$latex y_{ny_{n}}-y_{n}^{2}x_{n}^{y_{n}-1}=\alpha\cdot y_{n}^{3}$, כאשר $latex \alpha$ הוא מספר שלם לא מעניין כלשהו. נעביר אגפים, נוציא גורם משותף, ונקבל:

$latex y_{ny_{n}}=y_{n}^{2}\left(x_{n}^{y_{n}-1}+\alpha y_{n}\right)$

כלומר, המסקנה שלנו היא ש-$latex y_{n}^{2}$ מחלק את $latex y_{ny_{n}}$. עוד תכונת התחלקות של הסדרה $latex y_{n}$! כמו בתכונת ההתחלקות הקודמת, אנחנו גם רוצים להבין מה קורה בכיוון ההפוך. כלומר, אם $latex y_{n}^{2}$ מחלק $latex y_{t}$ כלשהו, אז מה אפשר לדעת על $latex t$? במקרה שלנו אפשר להוכיח שבהכרח $latex y_{n}$ מחלק את $latex t$. למה? טוב, ראשית, אם $latex y_{n}^{2}$ מחלק את $latex y_{t}$ אז בוודאי שגם $latex y_{n}$ מחלק אותו, וכבר ראינו שזה גורר ש-$latex n$ מחלק את $latex t$, כלומר אפשר לכתוב $latex t=nk$. עכשיו, $latex y_{t}=y_{nk}\equiv_{y_{n}^{3}}kx_{n}^{k-1}y_{n}$, ולכן בגלל ש-$latex y_{n}^{2}$ מחלק את $latex y_{t}$ נקבל שהוא מחלק גם את $latex kx_{n}^{k-1}y_{n}$, כלומר $latex y_{n}$ מחלק את $latex kx_{n}^{k-1}$. כמו כן, $latex \left(y_{n},x_{n}\right)=1$ ולכן $latex y_{n}$ מחלק את $latex k$, אבל $latex t=nk$ ולכן $latex y_{n}$ מחלק את $latex t$ – סיימנו.

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

בואו נעבור לדבר עכשיו על משהו קצת שונה שקשור לסדרות $latex x_{n},y_{n}$ – אפשר להציג אותן גם באמצעות נוסחת נסיגה. בפרט:

$latex x_{n+1}=2ax_{n}-x_{n-1}$

$latex y_{n+1}=2ay_{n}-y_{n-1}$

ההוכחה כמעט מיידית באמצעות הנוסחאות שלנו ל-$latex x_{n\pm m}$ ו-$latex y_{n\pm m}$ ואתם מוזמנים לנסות ולמצוא אותה בעצמכם.

מה שנחמד בנוסחאות הנסיגה הללו הוא שהן מאפשרות להוכיח טענות על הסדרות $latex x_{n},y_{n}$ אינדוקטיבית. למשל, בואו נוכיח ש-$latex y_{n}\equiv_{a-1}n$: ראשית כל בודקים ישירות שזה מתקיים עבור $latex n=0,1$, ושנית:

$latex y_{n+1}=2ay_{n}-y_{n-1}\equiv_{a-1}2n-\left(n-1\right)=n+1$ (השתמשתי כאן בכך ש-$latex a\equiv_{a-1}1$)

כמו כן, וזה כבר מעניין למדי, אם $latex a\equiv_{c}b$ אז לכל $latex n$ מתקיים ש-$latex x_{n}\left(a\right)\equiv_{c}x_{n}\left(b\right)$ ו-$latex y_{n}\left(a\right)\equiv_{c}y_{n}\left(b\right)$. גם ההוכחה פה היא מיידית מתוך נוסחת הנסיגה, כאשר המקרים $latex n=0,1$טריוויאליים (מבחן – היכן אנו משתמשים שם בכך ש-$latex a\equiv_{c}b$?). בכל הנוגע לצעד:

$latex y_{n+1}\left(a\right)=2ay_{n}\left(a\right)-y_{n-1}\left(a\right)\equiv_{c}2by_{n}\left(b\right)-y_{n-1}\left(b\right)=y_{n+1}\left(b\right)$

ואותו דבר בדיוק עבור $latex x_{n}$.

עוד שעשוע הוא להיווכח בכך ש-$latex y_{n}$ הוא זוגי עבור $latex n$ זוגי, ואי זוגי עבור $latex n$ אי זוגי. את זה אפשר להסיק מהסתכלות על נוסחת הנסיגה מודולו 2:

$latex y_{n+1}=2ay_{n}-y_{n-1}\equiv_{2}y_{n-1}$

ובגלל ש-$latex y_{0}$ זוגי ו-$latex y_{1}$ אי זוגי התוצאה נובעת.

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

$latex x_{n}\left(a\right)-y_{n}\left(a\right)\left(a-y\right)\equiv_{2ay-y^{2}-1}y^{n}$

מי זה $latex y$? מספר כלשהו. אז למה דווקא לסמן אותו ב-$latex y$? כדי לדבוק בסימונים של דיוויס.

ההוכחה, כרגיל, דורשת קודם כל לבדוק את המקרה של $latex n=0,1$. בואו נעשה את זה במפורש הפעם:

$latex x_{0}\left(a\right)-y_{0}\left(a\right)\left(a-y\right)=1-0\left(a-y\right)=1\equiv_{2ay-y^{2}-1}y^{0}$

$latex x_{1}\left(a\right)-y_{1}\left(a\right)\left(a-y\right)=a-1\left(a-y\right)=y\equiv_{2ay-y^{2}-1}y^{1}$

ועכשיו נמשיך אינדוקטיבית:

$latex x_{n+1}\left(a\right)-y_{n+1}\left(a\right)\left(a-y\right)=2a\left[x_{n}\left(a\right)-y_{n}\left(a-y\right)\right]-\left[x_{n-1}\left(a\right)-y_{n-1}\left(a-y\right)\right]\equiv_{2ay-y^{2}-1}2ay^{n}-y^{n-1}$

עוד לא סיימנו:

$latex 2ay^{n}-y^{n-1}=y^{n-1}\left(2ay-1\right)\equiv_{2ay-y^{2}-1}y^{n-1}y^{2}=y^{n+1}$

לב העניין כאן הוא המעבר $latex \left(2ay-1\right)\equiv_{2ay-y^{2}-1}y^{2}$ – ודאו שאתם מבינים למה הוא נכון.

עכשיו בואו נבין משהו על קצב הגידול של $latex x_{n},y_{n}$. נתחיל מ-$latex y_{n}$. כזכור, $latex y_{n+1}=y_{n}x_{1}+y_{1}x_{n}=ay_{n}+x_{n}$, ולכן $latex y_{n+1}>ay_{n}$ – בפרט אפשר להסיק ש-$latex y_{n}$ חיובי לכל $latex n$ (לא נצטרך יותר מזה).

בכל הנוגע ל-$latex x_{n}$, יש לנו את הנוסחה $latex x_{n+1}=x_{n}x_{1}+dy_{n}y_{1}=ax_{n}+dy_{n}$. אז $latex x_{n+1}>ax_{n}$ לכל $latex n$, ולכן אפשר להראות באינדוקציה ש-$latex x_{n}\ge a^{n}$, כלומר הסדרה גדלה בקצב שהוא לפחות אקספוננציאלי. זה חסם מלמטה, אבל האם אפשר לחסום גם מלמעלה? ובכן, בקלות, עם נוסחת הנסיגה של $latex x_{n}$: $latex x_{n+1}=2ax_{n}-x_{n-1}\le2ax_{n}$ ולכן $latex x_{n}\le\left(2a\right)^{n}$.

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

$latex x_{2n\pm i}\equiv_{x_{n}}-x_{i}$

אין כאן יותר מאשר שימוש בהגדרה:

$latex x_{2n\pm i}=x_{n}x_{n\pm i}+dy_{n}y_{n\pm i}\equiv_{x_{n}}dy_{n}\left(y_{n}x_{i}\pm x_{n}y_{i}\right)\equiv_{x_{n}}dy_{n}^{2}x_{i}=\left(x_{n}^{2}-1\right)x_{i}\equiv_{x_{n}}-1$

כאן השתמשנו בכך ש-$latex x_{n}^{2}-dy_{n}^{2}=1$, ולכן $latex dy_{n}^{2}=x_{n}^{2}-1$.

מסקנה מיידית היא ש-$latex x_{4n\pm i}\equiv_{x_{n}}x_{i}$, כי $latex x_{4n\pm i}=x_{2n+\left(2n\pm i\right)}\equiv_{x_{n}}-x_{2n\pm i}\equiv_{x_{n}}x_{i}$.

עכשיו לתוצאה שההוכחה שלה תהיה טיפה יותר ארוכה, אבל כבר נראית די מעניינת: אם $latex x_{i}\equiv_{x_{n}}x_{j}$ כך ש-$latex i\le j\le2n$ ו-$latex n>0$ אז $latex i=j$ למעט המקרה $latex a=2,n=1,i=0,j=2$. זה מעניין כי זה מראה שאפשר לזהות בצורה ייחודית, בערך, איברים ב-$latex x_{n}\left(a\right)$ על פי תכונות התחלקות שלהם, וזה משהו שאפשר לקודד דיופנטית, בערך.

בדרך כלל כשמדברים על חישובים מודולו $latex n$ (ל-$latex n$ כלשהו) אנו מסתכלים על הקבוצה $latex \left\{ 0,1,2,\dots,n-1\right\} $ ועושים בה את החשבון. אבל בתיאוריה יכלנו לעבוד גם עם הקבוצה $latex \left\{ -1,0,\dots,n-2\right\} $ או עם הרבה קבוצות אחרות – העיקר הוא רק למצוא קבוצה שבה אין שני מספרים ששקולים מודולו $latex n$, ויש נציג לכל מחלקת שקילות מודולו $latex n$ (בניסוח פשוט, לכל מספר בין $latex 0$ ל-$latex n-1$ יש בקבוצה איבר ששקול לו מודולו $latex n$). בתורת המספרים לעתים מאוד נוח לעבוד עם קבוצת נציגים שאיננה $latex \left\{ 0,1,\dots,n-1\right\} $ אלא כוללת בחציה מספרים שליליים, כאילו הזזנו את הקבוצה $latex \left\{ 0,1,\dots,n-1\right\} $ מרחק של חצי $latex n$ בערך. כאשר $latex n$ אי זוגי אין כזה דבר, "חצי $latex n$", אבל אפשר לדבר על המספר $latex q=\frac{n-1}{2}$ שהוא מספר שלם, ואז להתבונן על קבוצת הנציגים $latex \left\{ -q,-q+1,\dots,-1,0,1,\dots,q\right\} $ שכוללת בדיוק $latex q$ מספרים חיוביים, $latex q$ מספרים שליליים ואת $latex 0$, כלומר $latex 2q+1=n$ מספרים, ומכיוון שהם כולם ברצף ההפרש בין אף זוג שלהם לא יכול להתחלק ב-$latex n$ (ההפרש המקסימלי הוא $latex q-\left(-q\right)=2q=n-1$). כלומר, זו אכן קבוצת נציגים לגיטימית. כפי שאמרתי, לעתים נוח יותר לעבוד עם הקבוצה הזו וכך גם נעשה עכשיו.

אז בואו נניח ש-$latex x_{n}$ הוא אי זוגי וניקח את אוסף השאריות מ-$latex -q$ עד $latex q$ כאשר $latex q=\frac{x_{n}-1}{2}$. עכשיו, בואו נסתכל לרגע במספרים $latex x_{0},x_{1},x_{2},\dots,x_{n-1}$. ראשית, יש בדיוק $latex n$ כאלו. שנית, זו סדרה עולה: $latex 1=x_{0}<x_{1}<x_{2}<\dots<x_{n-1}<x_{n}$ וזאת בגלל נוסחת הנסיגה שמגדירה את ה-$latex x_{n}$-ים. זה בפרט אומר שכל ה-$latex x_{i}$-ים הללו שונים זה מזה מודולו $latex x_{n}$ (למה?). כעת, אפשר לחסום את הגודל של האיבר המקסימלי בסדרה: אנחנו יודעים ש-$latex x_{n}=ax_{n-1}+dy_{n-1}\ge ax_{n-1}$ ולכן $latex x_{n-1}\le\frac{x_{n}}{a}\le\frac{x_{n}}{2}$. נובע מזה ש-$latex x_{n-1}\le q$ (כי $latex x_{n-1}$ הוא שלם ואילו $latex q$ הוא הערך השלם התחתון של $latex \frac{x_{n}}{2}$). במילים אחרות, ה-$latex x_{i}$-ים מתאימים לשאריות חיוביות בתוך הקבוצה $latex \left\{ -q,-q+1,\dots,-1,0,1,\dots,q\right\} $.

בואו נסתכל עכשיו על המספרים שמעבר ל-$latex x_{n}$: $latex x_{n+1},x_{n+2},\dots,x_{2n}$. לפני רגע ראינו את התכונה $latex x_{2n\pm i}\equiv_{x_{n}}-x_{i}$ ועכשיו היא תועיל לנו: היא אומרת שהסדרה $latex x_{n+1},x_{n+2},\dots,x_{2n}$ שקולה מודולו $latex x_{n}$ לסדרה $latex -x_{n-1},-x_{n-2},\dots,-x_{0}$. מכיוון שה-$latex x_{i}$-ים התאימו לשאריות חיוביות, זה אומר שה-$latex x_{n+i}$-ים מתאימים לשאריות שליליות בתוך הקבוצה $latex \left\{ -q,-q+1,\dots,-1,0,1,\dots,q\right\} $. השאריות החיוביות והשליליות בקבוצה לא שקולות זו לזו, ולכן קיבלנו שכל ה-$latex x_{i}$-ים עד $latex i\le2n$ לא שקולים האחד לשני (אם אתם עדיין לא משוכנעים נסו להשלים את ההוכחה).

זה טיפל רק במקרה שבו $latex x_{n}$ אי זוגי. אם הוא זוגי אז נסמן $latex q=\frac{x_{n}}{2}$ ואוסף השאריות יהיה הפעם $latex \left\{ -q+1,-q+1,\dots,-1,0,1,\dots,q\right\} $, כלומר הקצה השמאלי הוא לא $latex -q$ אלא מספר שגדול ממנו ב-1. מתי זה יכול להפריע להוכחה שלעיל? רק אם איכשהו הסדרה $latex x_{i}$ מגיעה אל $latex q$, והיא יכולה להגיע רק באיבר האחרון שלה, כלומר $latex x_{n-1}=q=\frac{x_{n}}{2}$. זה מקרה קצה, אבל זה עשוי להתרחש. אם זה התרחש, בואו נראה מה נוסחת הנסיגה של $latex x_{n}$ אומרת לנו:

$latex x_{n}=ax_{n-1}+dy_{n-1}=a\frac{x_{n}}{2}+dy_{n-1}$

מתי זה יכול לקרות? מכיוון ש-$latex a\ge2$, הדרך היחידה שבה נוכל לקבל שוויון היא אם $latex a=2$ (אחרת $latex a\frac{x_{n}}{2}+dy_{n-1}>x_{n}$), ובמקרה זה בהכרח $latex y_{n-1}=0$, אבל זה קורה רק עבור $latex n=1$. הנה הוכחנו שאנחנו במקרה הפרטי היחיד שסייגנו החוצה מראש בניסוח המשפט.

יפה, הוכחנו את המשפט, בואו נרחיב אותו טיפה ונראה שאם $latex x_{i}\equiv_{x_{n}}x_{j}$ תוך שאנו מאלצים את $latex i$ להיות קטן יותר – $latex 0<i\le n$ אבל מרשים ל-$latex j$ להיות גדול יותר – $latex 0\le j<4n$, אז או ש-$latex j=i$ כמקודם או ש-$latex j=4n-i$. ההוכחה פשוטה: אם $latex j\le2n$ פשוט נשתמש במשפט שזה עתה הוכחנו. יש את ה"סכנה" שאנחנו במקרה היוצא מן הכלל, אבל אז $latex j=0$ (כי אסרנו על $latex i$ להיות 0) וזה מוביל לסתירה כי אז $latex i=2>1=n$. בקיצור, החריג ההוא לא ממש רלוונטי במקרה הזה.

במקרה השני $latex j>2n$. נסמן $latex t=4n-j$, אז $latex 0<t<2n$. כעת, זוכרים שהוכחנו מתישהו ש-$latex x_{4n\pm j}\equiv_{x_{n}}x_{j}$? זה נותן לנו עכשיו ש-$latex x_{t}\equiv_{x_{n}}x_{j}\equiv x_{i}$ ולכן שוב, מהמשפט שזה עתה הוכחנו, $latex t=i$ (ולמה החריג למשפט לא יכול להתקיים כעת?)

רק עוד דבר אחד וסיימנו: נניח ש-$latex 0<i\le n$ ומתקיים $latex x_{i}\equiv_{x_{n}}x_{j}$, בלי שום הנחות על $latex j$. מה נוכל לומר עליו? ובכן, בואו ננסה לחלק אותו ב-$latex 4n$, כלומר נרשום אותו בצורה $latex j=4nt+r$ כאשר $latex 0\le r<4n$. עכשיו, זכרו שוב ש-$latex x_{4n\pm k}\equiv_{x_{n}}x_{k}$ ושאפשר לכתוב $latex 4nt+r=4n+\left(4n\left(t-1\right)+r\right)$, ולכן $latex x_{j}=x_{4nt+r}\equiv_{x_{n}}x_{4n\left(t-1\right)+r}$. אפשר להמשיך עם זה ולקבל בסופו של דבר $latex x_{j}\equiv_{x_{n}}x_{r}$, ולכן $latex x_{r}\equiv_{x_{n}}x_{i}$. עכשיו $latex 0\le r<4n$ ולכן אפשר להשתמש במשפט הקודם עליו ולקבל $latex i=r$ או $latex i=4n-r$. משני המקרים הללו נקבל ש-$latex j\equiv_{4n}r\equiv_{4n}\pm i$ (אחד משניהם, לא שניהם גם יחד!).

זהו. זה היה מייגע ביותר, אבל עכשיו קיבלנו די והותר כלי נשק להתמודדות עם שאלת הדיופנטיות של $latex \left(x_{n},y_{n}\right)$ בפרט, ושל הפונקציה האקספוננציאלית בכלל. בפוסט הבא זה גם יקרה בפועל.

תגובה אחת בנושא “הבעיה העשירית של הילברט – איך משוואת פל קשורה לכל העניין?”

  1. אולי פספסתי משהו אבל לא אמורים להיות סוגרים מסביב ל-(a-sqrt(d)) אחרי החלוקה ב-(x+y*sqrt(d)?

    חוץ מזה, פוסט די נחמד למי שאוהב חשבון מודולרי.

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *