הבעיה העשירית של הילברט - לכל דבר טוב (חסום) יש סוף

בשעה טובה הגענו אל המכשול האחרון שעומד בינינו ובין סיום ההוכחה שהבעיה העשירית של הילברט אינה כריעה - כמת אוניברסלי חסום. אם נצליח להראות שבהינתן ביטוי דיופנטי \( P \) אפשר להוכיח שגם הביטוי \( \forall x<n\left(P\right) \) הוא דיופנטי, נסיים. כאן אמורה להיכנס לתמונה העובדה שהוכחנו (בדם יזע ודמעות) שהפונקציה האקספוננציאלית היא דיופנטית. בואו נתחיל בלראות עבור עוד פונקציות שגדלות בקצב מהיר שהן דיופנטיות.

נפתח בפונקציה שהיא אקספוננציאלית-כפולה: \( h\left(u,v,w\right)=u^{v^{w}} \). בהינתן שהפונקציה האקספוננציאלית היא דיופנטית, קל לבנות ביטוי עבור הפונקציה הזו:

\( y=u^{v^{w}}\iff\exists z\left(y=u^{z}\wedge z=v^{w}\right) \)

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

זו הייתה פונקציה קלה, בואו נדבר על משהו מסובך יותר - מקדמי הבינום, \( f\left(n,k\right)={n \choose k} \). כדי לטפל בהם, קודם כל נוכיח את הזהות \( \sum_{i=k}^{n}{n \choose i}u^{i-k}=\left[\frac{\left(u+1\right)^{n}}{u^{k}}\right] \) שמתקיימת עבור \( 0<k\le n \) ו-\( u>2^{n} \) (והוא מספר טבעי), כאשר סוגריים מרובעים מסמנים ערך שלם תחתון (המספר השלם הגדול ביותר שקטן או שווה למה שבתוך הסוגריים).

אני מניח שלפחות חלקכם משער שהדרך הנכונה להתחיל הוכחה כזו היא עם נוסחת הביטום של ניוטון, שמתארת את הסכום כש-\( k \) מתחיל מ-0: \( \sum_{i=0}^{n}{n \choose i}u^{i}=\left(u+1\right)^{n} \). כעת, נחלק את שני האגפים ב-\( u^{k} \) (מתבקש לגמרי, נכון?) ונקבל \( \sum_{i=0}^{n}{n \choose i}u^{i-k}=\frac{\left(u+1\right)^{n}}{u^{k}} \). את הסכום שבאגף שמאל אפשר לחלק לשני סכומים שונים: \( \sum_{i=0}^{k-1}{n \choose i}u^{i-k}+\sum_{i=k}^{n}{n \choose i}u^{i-k} \). מביניהם, הימני הוא הסכום שאנו רוצים לחשב, והשמאלי הוא סתם שארית מעצבנת. מה שאנחנו רוצים לומר הוא שכאשר לוקחים ערך שלם תחתון על שני הסכומים הללו, הסכום השמאלי פשוט מתפוגג לו. מכיוון שהסכום הימני הוא מספר שלם, מספיק להראות ש-\( \sum_{i=0}^{k-1}{n \choose i}u^{i-k}<1 \) כדי להוכיח שהערך השלם התחתון יעלים אותו.

כעת, \( u \) הוא מספר טבעי, כלומר \( u^{i+1-k}\le1 \) לכל \( 0\le i<k \), כלומר (נחלק ב-\( u \) את שני האגפים) לכל \( i<k \) אנו מקבלים \( u^{i-k}\le u^{-1} \). מכאן שאפשר לחסום את הסכום בצורה הבאה:

\( \sum_{i=0}^{k-1}{n \choose i}u^{i-k}\le u^{-1}\sum_{i=0}^{k-1}{n \choose i}<u^{-1}\sum_{i=0}^{n}{n \choose i}=u^{-1}2^{n}<1 \)

וכאן אנחנו משתמשים בהנחה שלנו ש-\( u>2^{n} \) (וכמובן, בכך שעל פי הבינום של ניוטון, \( \sum_{i=0}^{n}{n \choose i}=\left(1+1\right)^{n} \)).

שימו לב למסקנה הפשוטה מהזהות \( \sum_{i=k}^{n}{n \choose i}u^{i-k}=\left[\frac{\left(u+1\right)^{n}}{u^{k}}\right] \) - אם ניקח את המשוואה הזו ונתבונן עליה מודולו \( u \), נקבל \( {n \choose k}\equiv_{u}\left[\frac{\left(u+1\right)^{n}}{u^{k}}\right] \), כי כל שאר המחוברים מתאפסים כשמסתכלים על המשוואה מודולו \( u \). זה התעלול שיאפשר לנו להגדיר את \( {n \choose k} \) דיופנטית. מה שמעניין במשוואה הזו היא שאגף שמאל לא כולל את \( u \). מה שראינו הוא שלכל \( u>2^{n} \) מתקיים ש-\( \left[\frac{\left(u+1\right)^{n}}{u^{k}}\right] \) שקול מודולו \( u \) ל-\( {n \choose k} \). כעת, \( {n \choose k}<2^{n}<u \) ולכן זו יותר מסתם שקילות - זה מה שמתקבל כשלוקחים את \( \left[\frac{\left(u+1\right)^{n}}{u^{k}}\right] \), מחלקים ב-\( u \) ובודקים מה השארית (נסו לחשב בעצמכם - במחשב - כמה מקרים אם אינכם מאמינים). זה מאפשר לנו להגדיר את \( {n \choose k} \) באמצעות הביטוי הדיופנטי הבא:

\( z={n \choose k}\iff\exists u,v,w\left(v=2^{n}\wedge u>v\wedge w=\left[\frac{\left(u+1\right)^{n}}{u^{k}}\right]\wedge z\equiv_{u}w\wedge z<u\right) \)

יש כאן כמה וכמה רכיבים בתוך הסוגריים שצריך להשתכנע שכל אחד מהם לכשעצמו הוא דיופנטי. אז ראשית, \( v=2^{n} \) הוא דיופנטי כי הפונקציה האקספוננציאלית היא דיופנטית (לכן נזקקנו לה). הביטוי \( u>v \) הוא בבירור דיופנטי (ראינו את זה בעבר - נסו לשחזר מהראש). כנ”ל \( z<u \). הביטוי \( z\equiv_{u}w \) אולי נראה טיפה יותר טריקי, אבל הוא שקול ל-\( \exists a\left(z=ua+w\right) \) הדיופנטי. מי נשאר? רק \( w=\left[\frac{\left(u+1\right)^{n}}{u^{k}}\right] \) המפחיד. האתגר הוא בעצם להראות ש-\( w=\left[\frac{x}{y}\right] \) הוא דיופנטי, כי \( \left(u+1\right)^{n} \) ו-\( u^{k} \) הן פונקציות אקספוננציאליות ולכן דיופנטיות. למרבה המזל, מכיוון שאי-שוויונים הם דיופנטיים, קל לתאר גם את \( w=\left[\frac{x}{y}\right] \): הרי אם \( w=\left[\frac{x}{y}\right] \) זה אומר ש-\( w\le\frac{x}{y}\le w+1 \) ולכן \( yw\le x\wedge x\le y\left(w+1\right) \), ושתי המשוואות הללו מספיקות. מסקנה סופית: \( {n \choose k} \) היא דיופנטית (בזכות העובדה שהפונקציה האקספוננציאלית היא דיופנטית).

בואו נעבור עכשיו לתקוף פונקציה מפורסמת אחרת שגדלה מהר: \( f\left(n\right)=n! \). גם כאן כדי לתקוף אותה אנחנו צריכים משוואה אלגברית נחמדה כלשהי שהיא מקיימת; במקרה שלנו, אם \( u>\left(2n\right)^{n+1} \) אז \( n!=\left[u^{n}/{u \choose n}\right] \) היא המשוואה המדוברת. שימו לב שזה משהו בסגנון דומה להוכחה הקודמת; גם פה אנחנו משתמשים בכך שאם אנחנו לוקחים שתי פונקציות שגדלות מהר עם בסיס כלשהו שמסומן ב-\( u \) שהוא גדול דיו, אז מקבלים קירוב רציונלי די טוב לפונקציה שאנחנו רוצים לתקוף. כמו קודם, בואו ננסה להבין מהו \( u^{n}/{u \choose n} \) עבור \( u \) גדול שכזה:

\( u^{n}/{u \choose n}=u^{n}\cdot\frac{n!\left(u-n\right)!}{u!}=\frac{u^{n}n!}{u\left(u-1\right)\left(u-2\right)\cdots\left(u-n+1\right)}=n!\left(\frac{1}{1\left(1-\frac{1}{u}\right)\cdots\left(1-\frac{n-1}{u}\right)}\right) \)

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

\( n!\left(\frac{1}{1\left(1-\frac{1}{u}\right)\cdots\left(1-\frac{n-1}{u}\right)}\right)<n!\frac{1}{\left(1-\frac{n}{u}\right)^{n}} \)

זאת כי ככל שמגדילים את הערך של \( x \) בביטוי \( \left(1-\frac{x}{u}\right) \) כך מקטינים את הביטוי, ולכן מגדילים את אחד חלקי הביטוי.

עכשיו, \( \frac{1}{\left(1-\frac{n}{u}\right)^{n}}=\left(\frac{1}{1-\frac{n}{u}}\right)^{n} \) ולכן כדאי לנו למצוא חסם כלשהו על מה שבפנים, \( \frac{1}{1-\frac{n}{u}} \). לצורך כך כדאי להיזכר שהדבר הזה נראה כמו סכום של טור גיאומטרי. באופן כללי, אם \( \left|q\right|<1 \), אז מתקיים

\( \sum_{k=0}^{\infty}q^{k}=\frac{1}{1-q} \)

ובמקרה שלנו \( u>2n \) (ממש ממש גדול יותר, אם תציצו שניה במה שדרשנו עליו) כך ש-\( \frac{n}{u}<\frac{1}{2} \), ולכן:

\( \frac{1}{1-\frac{n}{u}}=\sum_{k=0}^{\infty}\left(\frac{n}{u}\right)^{k}=1+\left(\frac{n}{u}\right)\sum_{k=0}^{\infty}\left(\frac{n}{u}\right)^{k}<1+\frac{n}{u}\sum_{k=0}^{\infty}\left(\frac{1}{2}\right)^{k}=1+\frac{2n}{u} \)

כל המעברים כאן הם חשבון פשוט, אבל את השני ביצעתי קצת בזריזות: פשוט הוצאתי מהסכום את האיבר הראשון שלו (1) ואז הוצאתי החוצה גורם משותף לשאר האיברים (\( \frac{n}{u} \)).

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

\( \left(1+\frac{2n}{u}\right)^{n}=\sum_{k=0}^{n}{n \choose k}\left(\frac{2n}{u}\right)^{k}<1+\frac{2n}{u}\sum_{k=1}^{n}{n \choose k}<1+\frac{2n}{u}2^{n} \)

גם פה רוב המעברים הם פשוטים - הראשון הוא הבינום, השני הוא פשוט פירוק לאיבר ראשון בסכום וכל היתר והוצאת גורם משותף והתעלמות מהיתר, בהתבסס על כך ש-\( \frac{2n}{u}<1 \), והמעבר השלישי הוא פשוט הנוסחה \( \sum_{k=0}^{n}{n \choose k}=2^{n} \) בפעולה.

בואו נזכר ממה התחלנו: \( u^{n}/{u \choose n} \). הגענו לכך שהוא קטן מ-\( n!\frac{1}{\left(1-\frac{n}{u}\right)^{n}} \), ולכן:

\( u^{n}/{u \choose n}<n!+\frac{2n}{u}2^{n}n!<n!+\frac{2^{n+1}n^{n+1}}{u}<n!+1 \)

המעבר הלפני אחרון נובע מכך ש-\( n!<n^{n} \) (כמובן - בשני המקרים מכפילים \( n \) איברים אבל ב-\( n! \) רובם קטנים יותר מ-\( n \)) המעבר האחרון נובע מההנחה שלנו על \( u \): \( u>\left(2n\right)^{n+1} \). זה מסיים את ההוכחה כי זה מראה ש-\( n!\le u^{n}/{u \choose n}<n!+1 \) ולכן לקיחת ערך שלם תמיד תחזיר לנו \( n! \). אם עוד לא ברור למה הביטוי הזה הוא לפחות \( n! \), זכרו ש-\( u^{n}/{u \choose n}=\frac{u^{n}}{u\left(u-1\right)\left(u-2\right)\cdots\left(u-n+1\right)}n! \) - במונה ובמכנה יש \( n \) מוכפלים, אבל במונה כולם \( u \) ובמכנה רובם קטנים מ-\( u \).

עכשיו אפשר להוכיח ש-\( n! \) דיופנטית בהתבסס על כך ש-\( {n \choose k} \) דיופנטית. הביטוי הדיופנטי הוא פשוט למדי:

\( m=n!\iff\exists u\left[{u \choose n}m\le u^{n}\wedge u^{n}\le{u \choose n}\left(m+1\right)\wedge u>\left(2n\right)^{n+1}\right] \)

יפה. הראינו כבר על שלוש פונקציות שגדלות “מהר” שהן דיופנטיות - \( n^{k},{n \choose k},n! \). עכשיו אפשר לעבור לפונקציה שהיא היעד הסופי שלנו, ובהשוואה לשלוש הפונקציות הטבעיות הללו אולי תהיה טיפה מאכזבת: \( h\left(a,b,y\right)=\prod_{k=1}^{y}\left(a+bk\right) \). מילולית, הפונקציה כופלת את \( y \) האיברים הראשונים בסדרה חשבונית שהאיבר הראשון שלה הוא \( a+b \) וההפרש בין שני איברים סמוכים הוא \( b \). למה הפונקציה הזו דווקא כל כך יעילה? ובכן… אה… זה טכני, חכו ותראו. לא תהיה תובנה מדהימה בסוף.

כדי להראות שהפונקציה הזו דיופנטית נשתמש בתעלול שאיכשהו יערבב את כל שלוש הפונקציות שראינו עד כה. ראשית, נניח שיש לנו \( q,M \) שעבורם מתקיימת המשוואה \( bq\equiv_{M}a \). אז נרצה להראות שהקסם הבא מתקיים:

\( \prod_{k=1}^{y}\left(a+bk\right)\equiv_{M}b^{y}y!{q+y \choose y} \)

ההוכחה דווקא פשוטה למדי הפעם. פשוט נפתח את הביטוי:

\( b^{y}y!{q+y \choose y}=b^{y}y!\frac{\left(q+y\right)!}{y!q!}=b^{y}\left(q+y\right)\left(q+y-1\right)\cdots\left(q+1\right) \)

\( =\left(bq+by\right)\left(bq+b\left(y-1\right)\right)\cdots\left(bq+b\right)\equiv_{M}\prod_{k=1}^{y}\left(a+bk\right) \)

מה שנותר לעשות הוא להבטיח שאכן קיימים \( M,q \) שמקיימים את המשוואה \( bq\equiv_{M}a \). בגלל האותיות העסק יכול להיראות מבלבל, אז בואו נשכח לרגע מהכל ונעבור לדון במשהו כללי - המשוואה הלינארית \( ax\equiv_{n}b \) כאשר \( a,b,n \) נתונים ואילו \( x \) הוא המשתנה. הטענה היא שלמשוואה הזו קיים פתרון אם \( \left(a,n\right)=1 \), כלומר \( a \) זר ל-\( n \). הסיבה לכך היא שבמקרה הזה, קיים ל-\( a \) הופכי כפלי מודולו \( n \) ולכן \( x\equiv_{n}a^{-1}b \). במקרה שלנו ה”משתנה” הוא בכלל \( q \) ומה שאנחנו צריכים כדי שהמשוואה תהיה פתירה הוא שיתקיים \( \left(b,M\right)=1 \); למזלנו, אנחנו יכולים לבחור את \( M \) כדי להבטיח שזה יקרה: נבחר \( M=b\left(a+by\right)^{y}+1 \), אז אגף ימין בודאות לא מתחלק על ידי אף ראשוני שמחלק את \( b \) (כי כפלנו את \( b \) במשהו והוספנו 1) ולכן \( \left(M,b\right) \) זרים ומובטח לנו שקיים \( q \) כלשהו (לא יודע מי) כך ש-\( bq\equiv_{M}a \). את כל זה אפשר לכתוב בתור ביטוי דיופנטי:

\( z=\prod_{k=1}^{y}\left(a+bk\right)\iff\exists M,q,t,p \)

\( M=b\left(a+by\right)^{y}+1\wedge bq=a+Mt \)

\( \wedge z<M\wedge z+Mp=b^{y}y!{q+y \choose y} \)

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

בואו נעבור על מה שאנחנו רוצים לעשות. ביטוי דיופנטי מתורגם בסופו של דבר לפולינום \( P \) ולמשוואה

\( \exists y_{1},\dots,y_{m}\left[P\left(x_{1},\dots,x_{n},y_{1},\dots,y_{m}\right)=0\right] \)

שמגדירה קבוצה - בדיוק את קבוצת ה-\( x \)-ים שכשמציבים אותם מקבלים משוואה פתירה.

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

\( \forall z\le y\exists y_{1},\dots,y_{m}\left[P\left(x_{1},\dots,x_{n},z,y,y_{1},\dots,y_{m}\right)=0\right] \)

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

\( \exists u\forall_{\le y}z\exists_{\le u}y_{1},\dots,y_{m}\left[P\left(x_{1},\dots,x_{n},z,y,y_{1},\dots,y_{m}\right)=0\right] \)

שבו אני מגביל את \( z \) להיות קטן או שווה ל-\( y \) כלשהו ומגביל את כל ה-\( y_{i} \)-ים להיות קטנים מ-\( u \) כלשהו שכמובן קיים בהנחה שקיימים \( y_{i} \)-ים שפותרים את המשוואה (פשוט קחו את המקסימום מביניהם).

עכשיו לאקשן. אני טוען שבהינתן פולינום \( Q \) מתאים, הביטוי הבא:

\( \forall_{\le y}z\exists_{\le u}y_{1},\dots,y_{m}\left[P\left(x_{1},\dots,x_{n},z,y,y_{1},\dots,y_{m}\right)=0\right] \)

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

\( \exists c,t,a_{1},\dots,a_{m} \)

\( 1+ct=\prod_{k=1}^{y}1+kt \)

\( \wedge t=Q\left(y,u,x_{1},\dots,x_{n}\right)!\wedge1+ct|\prod_{j=1}^{u}\left(a_{1}-j\right) \)

\( \wedge\dots\wedge1+ct|\prod_{j=1}^{u}\left(a_{m}-j\right) \)

\( \wedge P\left(x_{1},\dots,x_{n},c,y,a_{1},\dots,a_{m}\right)\equiv_{1+ct}0 \)

כדי שזה יעבוד, \( Q\left(y,u,x_{1},\dots,x_{n}\right) \) צריך לקיים את שלוש התכונות הבאות:

\( Q\left(y,u,x_{1},\dots,x_{n}\right)>u \)

\( Q\left(y,u,x_{1},\dots,x_{n}\right)>y \)

אם \( z\le y \) וגם \( y_{1},\dots,y_{m}\le u \) אז

\( \left|P\left(x_{1},\dots,x_{n},z,y,y_{1},\dots,y_{m}\right)\right|\le Q\left(y,u,x_{1},\dots,x_{n}\right) \)

זהו. אם נצליח לעשות את זה, גמרנו, שכן בבירור הביטוי המפלצתי שכתבתי הוא דיופנטי - הוא כולל רק את \( \prod\left(a+bk\right) \) שכבר ראינו שהיא דיופנטית, ואת היחס \( a|b \) (“\( a \) מחלק את \( b \)”) שכבר ראינו שהוא דיופנטי, ואת היחס \( \equiv \) שכבר ראינו שהוא דיופנטי, ואת הפונקציה \( n! \) שכבר ראינו שהיא דיופנטית.

עכשיו מכיוון שזו הוכחת שקילות, צריך להוכיח שני כיוונים. בואו נניח קודם כל שיש לנו \( x_{1},\dots,x_{n},y,u \) שעבורם הביטוי הדיופנטי המפלצתי הוא נכון (כלומר, יש פתרון למשוואות שלו) ונראה שקיים ערך של \( z \) שחסום על ידי \( y \) כך שעבורו קיימים ערכים של \( y_{i} \)-ים שחסומים על ידי \( u \) כך ש-\( P\left(x_{1},\dots,x_{n},z,y,y_{1},\dots,y_{m}\right)=0 \).

בואו נניח ש-\( z=k \), כאשר \( 1\le k\le y \). אנחנו רוצים למצוא \( y_{1}^{\left(k\right)},\dots,y_{m}^{\left(k\right)} \) כך ש-\( P\left(x_{1},\dots,x_{n},y,k,y_{1}^{\left(k\right)},\dots,y_{m}^{\left(k\right)}\right)=0 \). אנחנו יודעים שהביטוי הדיופנטי המפלצתי פתיר. אז בואו ניקח את הצבת הערכים לתוכו ונשתמש בה. בפרט, הצבת הערכים הזו נותנת לנו \( a_{1},\dots,a_{m} \) ו-\( t \). בואו נסמן ב-\( p_{k} \) גורם ראשוני כלשהו של \( 1+kt \), וכעת נגדיר:

\( y_{i}^{\left(k\right)}=a_{i}\mbox{ mod }p_{k} \)

דהיינו, \( y_{i}^{\left(k\right)} \) מתקבל מחלוקת \( a_{i} \) ב-\( p_{k} \) ולקיחת השארית. אני טוען שהערכים הללו אכן מספקים את \( P \), ושהם לא גדולים מ-\( u \), כלומר \( 1\le y_{i}^{\left(k\right)}\le u \). מדוע?

ובכן, ראשית נטפל בעניין הגודל. שימו לב לכך ש-\( p_{k}|1+kt \) (כי בחרנו את \( p_{k} \) להיות גורם של הביטוי הימני), וש-\( 1+kt|1+ct \) (זה נובע מייד מהמשוואה הראשונה בביטוי המפלצתי) וש-\( 1+ct|\prod_{j=1}^{u}\left(a_{i}-j\right) \) (זו אחת מהמשוואות בביטוי המפלצתי). מסקנה: \( p_{k}|\prod_{j=1}^{u}\left(a_{i}-j\right) \), אבל מכיוון שלקחנו את \( p_{k} \) להיות ראשוני, אם הוא מחלק מכפלה הוא מחלק אחד מאיבריה, כלומר יש \( j \) ספציפי כלשהו כך ש-\( p_{k}|a_{i}-j \). מסקנה: \( a_{i}\equiv_{p_{k}}j\equiv_{p_{k}}y_{i}^{\left(k\right)} \).

אם אצליח לשכנע אתכם ש-\( y_{i}^{\left(k\right)}=j \) זה יראה ש-\( y_{i}^{\left(k\right)} \) קטן מספיק, כי \( 1\le j\le u \). כעת, \( y_{i}^{\left(k\right)} \) התקבל מחלוקה של משהו ב-\( p_{k} \) ולקיחת השארית, כלומר הוא אוטומטית קטן מ-\( p_{k} \). אם נוכיח ש-\( j<p_{k} \) זה יסיים את העניין כי שני מספרים ששקולים מודולו \( p_{k} \) ושניהם קטנים מ-\( p_{k} \) חייבים להיות שווים. כדי להראות ש-\( j<p_{k} \) מספיק להראות ש-\( u<p_{k} \). כעת נכניס את \( Q \) לתמונה: כזכור, \( Q\left(y,u,x_{1},\dots,x_{n}\right)>u \), ולכן די לנו להראות ש-\( p_{k}>Q\left(y,u,x_{1},\dots,x_{n}\right) \). איך נעשה את זה? ובכן, בואו נסתכל על הביטוי המפלצתי ונראה איך \( Q \) בא לידי ביטוי בו.

יש רק משוואה אחת שמערבת את \( Q \): \( t=Q\left(y,u,x_{1},\dots,x_{n}\right)! \). מילולית זה אומר ש-\( t \) הוא מכפלת כל המספרים הטבעיים עד וכולל \( Q\left(y,u,x_{1},\dots,x_{n}\right) \). כעת, אם מישהו מחלק את \( 1+kt \) אז הוא לא מחלק את \( t \), ולכן הוא לא יכול להיות אף אחד מהמספרים הטבעיים עד וכולל \( Q\left(y,u,x_{1},\dots,x_{n}\right) \). מסקנה: \( p_{k}>Q\left(y,u,x_{1},\dots,x_{n}\right)! \), וזה מה שרצינו.

הראינו אם כן שה-\( y_{i}^{\left(k\right)} \)-ים הם בסדר הגודל הנכון, אבל למה הם פותרים את \( P \)?

ובכן, מכיוון ש-\( p_{k} \) מחלק את \( 1+kt \) וגם את \( 1+ct \) הרי שקיבלנו:

\( 1+ct\equiv_{p_{k}}0 \)

\( 1+kt\equiv_{p_{k}}0 \)

נכפול את המשוואה הראשונה ב-\( k \), את השניה ב-\( c \), ונקבל:

\( k+kct\equiv_{p_{k}}0 \)

\( c+kct\equiv_{p_{k}}0 \)

נשווה את שתיהן ונקבל ש-\( k\equiv_{p_{k}}c \). כמו כן, אנחנו זוכרים שעל פי הגדרתם, \( y_{i}^{\left(k\right)}\equiv_{p_{k}}a_{i} \). המסקנה:

\( P\left(x_{1},\dots,x_{n},k,y,y_{1}^{\left(k\right)},\dots,y_{m}^{\left(k\right)}\right)\equiv_{p_{k}}P\left(x_{1},\dots,x_{n},c,y,a_{1},\dots,a_{m}\right)\equiv_{p_{k}}0 \)

(המעבר השני נובע מכך ש-\( P\equiv_{1+ct}0 \) ו-\( p_{k} \) מחלק את \( 1+ct \)).

עכשיו, השוויון שלעיל לא אומר ש-\( P\left(x_{1},\dots,x_{n},k,y,y_{1}^{\left(k\right)},\dots,y_{m}^{\left(k\right)}\right)=0 \), רק שקול לאפס מודולו \( p_{k} \). כדי להראות שוויון לאפס צריך להראות שהביטוי הזה גם קטן מ-\( p_{k} \). אבל זה שוב נובע מ-\( Q \), הפעם מהתכונה השלישית שלו:

\( \left|P\left(x_{1},\dots,x_{n},k,y,y_{1}^{\left(k\right)},\dots,y_{m}^{\left(k\right)}\right)\right|\le Q\left(y,u,x_{1},\dots,x_{n}\right)<p_{k} \)

וסיימנו את כיוון הגרירה הראשון, לפיו אם \( x_{1},\dots,x_{n} \) פותרים את הביטוי המפלצתי הם פותרים את \( P \) ה”רגיל”.

נותר הכיוון השני. נניח שעבור \( x_{1},\dots,x_{n},y \), לכל \( 1\le k\le y \) יש \( y_{1}^{\left(k\right)},\dots,y_{m}^{\left(k\right)} \) כך ש-

\( P\left(x_{1},\dots,x_{n},k,y,y_{1}^{\left(k\right)},\dots,y_{m}^{\left(k\right)}\right)=0 \).

אנחנו רוצים עכשיו להוכיח קיום של \( t,c,a_{1},\dots,a_{m} \) שפותרים את מערכת המשוואות המפלצתית.

נסמן בתור \( u \) מספר שגדול מכל ה-\( y_{i}^{\left(k\right)} \)-ים הללו. כעת, נגדיר \( t=Q\left(y,u,x_{1},\dots,x_{n}\right)! \). נותר לנו להגדיר את \( c \) ואת ה-\( a_{i} \)-ים.

כעת, \( 1+kt\equiv_{t}1 \) ולכן \( \prod_{k=1}^{y}\left(1+kt\right)\equiv_{t}1 \). המשמעות הישירה של השקילות הזו היא שקיים \( c \) כך ש-\( \prod_{k=1}^{y}\left(1+kt\right)=1+ct \), כך שמצאנו את ה-\( c \) שלנו והוא מקיים את המשוואה הראשונה בביטוי המפלצתי. נשאר רק לבחור את ה-\( a_{i} \)-ים כך שיקיימו את המשוואות \( 1+ct|\prod_{j=1}^{u}\left(a_{i}-j\right) \), וכך שיתקיים \( P\left(x_{1},\dots,x_{n},c,y,a_{1},\dots,a_{m}\right)\equiv_{1+ct}0 \). זה השלב שידרוש תחכום ושימוש במשפט השאריות הסיני.

מה שאני רוצה לעשות הוא להגדיר את \( a_{i} \) להיות הפתרון למערכת המשוואות \( a_{i}\equiv_{1+kt}y_{i}^{\left(k\right)} \), \( 1\le k\le y \) (זה לא כל כך מפתיע מבחינה רעיונית - אם אתם עוד מצליחים לעקוב אחרי מה שקורה בהוכחה ברמת התמונה הגדולה - אני בקושי מצליח - אפשר לראות שה-\( a_{i} \)-ים הללו אמורים לקודד בתוכם איכשהו את הפתרונות ל-\( P \) עבור כל בחירה של \( k \) בתחום המתאים). כדי להראות שקיים פתרון למערכת הזו צריך להוכיח שכל המודולוסים זרים, כלומר ש-\( \left(1+kt,1+lt\right)=1 \) עבור \( 1\le l<k\le y \). נניח בשלילה שיש איזה ראשוני \( p \) שמחלק את שניהם, אז הוא מחלק גם את ההפרש שלהם, כלומר \( p|t\left(k-l\right) \). שימו לב ש-\( p \) לא יכול לחלק את \( t \), אחרת הוא לא היה מחלק את \( 1+kt \), ולכן בהכרח \( p|k-l \). בפרט זה אומר ש-\( p<y \). כעת, תעלול! הגדרנו \( t=Q\left(y,u,x_{1},\dots,x_{n}\right)! \), והרי \( Q\left(y,u,x_{1},\dots,x_{n}\right)>y \), ולכן כל מספר עד \( y \) נכלל במכפלה שמרכיבה את \( t \), ולכן \( p \) חייב לחלק את \( t \) וזו סתירה. מסקנה: \( \left(1+kt,1+lt\right)=1 \) ואפשר להשתמש במשפט השאריות הסיני כפי שרצינו כדי למצוא את ה-\( a_{i} \)-ים.

למה זה עזר לנו? ובכן, שימו לב כי לכל \( k \) אנחנו מקבלים:

\( P\left(x_{1},\dots,x_{n},c,y,a_{1},\dots,a_{m}\right)\equiv_{1+kt}P\left(x_{1},\dots,x_{n},k,y,y_{1}^{\left(k\right)},\dots,y_{m}^{\left(k\right)}\right)=0 \)

כלומר, לכל \( 1\le k\le y \) קיבלנו ש-\( 1+kt \) מחלק את \( P\left(x_{1},\dots,x_{n},c,y,a_{1},\dots,a_{m}\right) \). מכיוון שכל ה-\( 1+kt \)-ים זרים זה לזה, אפשר להשתמש במשפט נוסף: אם שני מספרים זרים זה לזה מחלקים את אותו מספר, גם המכפלה שלהם מחלקת אותו. בסימנים: אם \( a|c \) וגם \( b|c \) וגם \( \left(a,b\right)=1 \) אז \( ab|c \).

המסקנה שלנו היא ש-\( 1+ct=\prod_{k=1}^{y}1+kt \) מחלק את \( P\left(x_{1},\dots,x_{n},c,y,a_{1},\dots,a_{m}\right) \), וזו בדיוק המשוואה האחרונה בביטוי המפלצתי. כמעט סיימנו. נשאר רק להראות שמתקיים \( 1+ct|\prod_{j=1}^{u}\left(a_{i}-j\right) \) לכל \( a_{i} \). לשם כך מספיק, כפי שראינו, להראות שלכל \( a_{i} \) ולכל \( k \) מתקיים \( 1+kt|\prod_{j=1}^{u}\left(a_{i}-j\right) \). כדי לחלק מכפלה מספיק לחלק איבר אחד שלה, כלומר מספיק לנו להראות שלכל \( a_{i} \) ולכל \( k \) קיים \( j \) כך ש-\( 1+kt|a_{i}-j \), אבל זה קל: מכיוון שהגדרנו את \( a_{i} \) להיות איבר שמקיים \( a_{i}\equiv_{1+kt}y_{i}^{\left(k\right)} \) זה אומר ש-\( 1+kt \) מחלק את \( a_{i}-y_{i}^{\left(k\right)} \) ולכן \( y_{i}^{\left(k\right)} \) הוא ה-\( j \) שלנו; רק צריך לשים לב לכך ש-\( 1\le y_{i}^{\left(k\right)}\le u \) ולכן הוא בתחום המתאים (הנה לנו הסיבה שבגללה היה חשוב להגביל את הערכים של ה-\( y_{i} \)-ים).

סיימנו!

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

הבניה של \( Q \) אינה מורכבת, אבל כיף זה לא הולך להיות. בואו פשוט נראה אותה. ראשית כל, בואו נציג את \( P \) בתור סכום של מונומים, כלומר נכתוב

\( P\left(x_{1},\dots,x_{n},k,y,y_{1},\dots,y_{m}\right)=\sum_{r=1}^{N}t_{r} \)

כך שכל מונום הוא בעל המראה המזעזע הבא:

\( t_{r}=cx_{1}^{q_{1}}\cdots x_{n}^{q_{n}}k^{a}y^{b}y_{1}^{s_{1}}\cdots y_{m}^{s_{m}} \)

בואו נגדיר מונום חדש, \( u_{r} \), על בסיס \( t_{r} \):

\( u_{r}=\left|c\right|y^{a+b}x_{1}^{q_{1}}\cdots x_{n}^{q_{n}}u^{s_{1}+\dots s_{m}} \)

ועכשיו נגדיר את \( Q \):

\( Q\left(y,u,x_{1},\dots,x_{n}\right)=u+y+\sum_{r=1}^{N}u_{r} \)

בבירור מתקיים \( Q\left(y,u,x_{1},\dots,x_{n}\right)>u \) וגם \( Q\left(y,u,x_{1},\dots,x_{n}\right)>y \) רק מעצם הבניה (זכרו שכל הערכים שאפשר להציב בפולינום הם חיוביים). צריך רק להסביר למה מתקיים

\( \left|P\left(x_{1},\dots,x_{n},k,y,y_{1},\dots,y_{m}\right)\right|\le Q\left(y,u,x_{1},\dots,x_{n}\right) \)

וזאת, כזכור, בתנאי ש-\( k\le y \) וגם \( y_{1},\dots,y_{m}\le u \).

אז למה זה נכון? ובכן, עם אי-שוויון המשולש נקבל:

\( \left|P\left(x_{1},\dots,x_{n},k,y,y_{1},\dots,y_{m}\right)\right|\le\sum_{r=1}^{N}\left|t_{r}\right| \)

לכן מספיק להשוות מונום-מונום ולהראות ש-\( \left|t_{r}\right|\le u_{r} \).

את \( t_{r} \) אפשר להפריד לשלושה חלקים. הראשון הוא \( \left|c\right|x_{1}^{q_{1}}\cdots x_{n}^{q_{n}} \) שקיים כמו שהוא גם ב-\( u_{r} \); השני הוא \( k^{a}y^{b} \) שמכוסה על ידי \( y^{a+b} \) של \( u_{r} \) בתנאי ש-\( k\le y \); והשלישי הוא \( y_{1}^{s_{1}}\cdots y_{m}^{s_{m}} \) שמכוסה על ידי \( u^{s_{1}+\dots s_{m}} \) בתנאי ש-\( y_{i}\le u \). זה מסיים את הבניה של \( Q \), ולכן מסיים את ההוכחה של הטענה לפיה אפשר לבנות ביטויים דיופנטיים עם הכמת האוניברסלי החסום, ולכן מסיים את ההוכחה שהבעיה העשירית של הילברט לא כריעה!

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


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

Buy Me a Coffee at ko-fi.com