הבעיה העשירית של הילברט - איך מקודדים דיופנטית את כל הסדרות הסופיות?

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

עזבו אתכם לרגע משאלת הדיופנטיותת איך בכלל נראית פונקציה כזו? פשוט מאוד: זו תהיה פונקציה \( S\left(i,u\right) \) על שני משתנים שהם מספרים טבעיים חיוביים, כך שלכל סדרה סופית \( a_{1},\dots,a_{N} \) של מספרים טבעיים חיוביים, יהיה קיים \( u \) כך ש-\( S\left(i,u\right)=a_{i} \) לכל \( 1\le i\le N \). במילים אחרות, תחשבו שהתאמנו מספר טבעי לכל סדרה סופית, ואז \( S \) מקבלת הן את מספר הסדרה הזו (\( u \)) והן את האינדקס של איבר ספציפי בסדרה (\( i \)) ומחזירה אותו. מכיוון שיש רק מספר בן מניה של סדרות סופיות, ברור שקיימת פונקציה כמו \( S \); למעשה, קיימות המון פונקציות שמקיימות את התכונה של \( S \) כי יש לנו לא מעט חופש בחירה (מה יהיה המספר שמקודד כל סדרה, ומה הערכים ש-\( S\left(i,u\right) \) מחזירה כאשר \( i \) גדול מהאינדקס של האיבר האחרון בסדרה \( u \)).

האתגר שלנו, אם כן, הוא למצוא פונקציה \( S\left(i,u\right) \) שכזו שתהיה גם דיופנטית. כלומר, שיהיה פולינום במספר משתנים \( p\left(x_{1},x_{2},x_{3},y_{1},\dots,y_{k}\right) \) כך שלכל הצבה של ערכים ב-\( x_{1},x_{2},x_{3} \), המשוואה הדיופנטית המתקבלת \( p\left(a_{1},a_{2},a_{3},y_{1},\dots,y_{k}\right)=0 \) במשתנים \( y_{1},\dots,y_{k} \) היא פתירה אם ורק אם \( a_{3}=S\left(a_{1},a_{2}\right) \).

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

בואו נתחיל עם פונקציה דיופנטית תמימה למראה - הפונקציה של המספרים המשולשיים, \( T\left(n\right)=1+2+3+\dots+n=\frac{n\left(n+1\right)}{2} \). למי שתוהה איך הגעתי לנוסחה באגף ימין, זה תעלול של גאוס: אם ניקח את הסדרה \( 1,2,\dots,n \), נכתוב מתחתיה את הסדרה \( n,n-1,\dots,1 \) ונחבר כל שני איברים שנמצאים האחד מעל השני, נקבל תמיד \( n+1 \), ויש לנו בדיוק \( n \) איברים כאלו. זה מראה ש-\( T\left(n\right)+T\left(n\right)=n\left(n+1\right) \) ולכן \( T\left(n\right)=\frac{n\left(n+1\right)}{2} \). ולמה “מספרים משולשיים”? כי אם נצייר משולש שמורכב מתפוזים כך שבקודקוד העליון שלו יש תפוז אחד, בשורה שמתחתיו שני תפוזים, מתחת לכך שלושה תפוזים וכן הלאה - מספר התפוזים במשולש יהיה \( T\left(n\right) \) כאשר \( n \) הוא מספר השורות.

למה הפונקציה הזו דיופנטית? ובכן, \( p\left(x_{1},x_{2}\right)=2x_{2}-x_{1}\left(x_{1}+1\right) \) עושה את העבודה - היא מקיימת \( p\left(n,T\left(n\right)\right)=0 \) וכמו כן \( p\left(a,b\right)\ne0 \) אם \( b\ne T\left(a\right) \).

עכשיו נתחיל עם להטוטים של תורת המספרים. ראשית, שימו לב לכך ש-\( T\left(n\right) \) היא פונקציה עולה ממש, כלומר \( T\left(n\right)<T\left(n+1\right) \) תמיד, וכמו כן היא אינה חסומה (זה מובן מאליו - כל פונקציה עולה ממש של טבעיים אינה חסומה). זה אומר שלכל מספר טבעי \( z \), קיים איזה שהוא \( n\ge0 \) כך ש-\( T\left(n\right)<z\le T\left(n+1\right) \), כלומר \( z \) נופל באיזה שהוא קטע שבין \( T\left(n\right) \) ו-\( T\left(n+1\right) \) (ורק בקטע אחד כזה!). לכן אפשר לכתוב את \( z \) בצורה יחידה בתור \( z=T\left(n\right)+y \) כך ש-\( 1\le y\le n+1 \) והערכים של \( n,y \) נקבעים באופן יחיד בהינתן \( z \).

בעיה קטנה שצצה עכשיו היא ש-\( n \) יכול להיות שווה 0 אבל אנחנו מתעסקים רק במספרים שערכם לפחות 1. לכן את \( n \) נכתוב בעזרת \( y \): \( n=y+x-2 \), כאשר \( x \) הוא משתנה כלשהו שערכו נע בין 1 ובין \( n+1 \), כמו \( y \). אם כן, אפשר לכתוב:

\( z=T\left(x+y-2\right)+y \)

ושוב - \( x,y \) נקבעים ביחידותבהינתן \( z \). נגדיר כעת שלוש פונקציות:

1. \( L\left(z\right)=x \)
2. \( R\left(z\right)=y \)
3. \( P\left(x,y\right)=T\left(x+y-2\right)+y \)

בואו נבין מה הפונקציות הללו עושות. ראשית אכתוב את הזוגות \( \left(L\left(z\right),R\left(z\right)\right) \) עבור הערכים הראשונים של \( z=1,2,3,4,\dots \). עבור \( z=1 \) ברור ש-\( n=0 \) ו-\( y=1 \), ולכן \( x=1 \), כלומר הזוג הראשון הוא \( \left(1,1\right) \). עבור \( z=2 \) ברור ש-\( n=1 \) ו-\( y=1 \) ולכן \( x=2 \) ולכן הזוג השני הוא \( \left(2,1\right) \), וכן הלאה. נקבל את הסדרה:

\( \left(1,1\right),\left(2,1\right),\left(1,2\right),\left(3,1\right),\left(2,2\right),\left(1,3\right),\dots \)

העקרון די ברור: אנחנו קודם כל עוברים על כל הזוגות \( \left(x,y\right) \) שבהם \( x+y=2 \) - יש רק זוג אחד כזה - ולכן על כל הזוגות שמתאימים ל-\( n=0 \) (כזכור, \( n=x+y-2 \)). אחר כך אנחנו עוברים על כל הזוגות שמתאימים ל\( n=1 \), כלומר \( x+y=3 \), לאחר מכן על הזוגות של \( n=2 \), כלומר \( x+y=4 \), וכן הלאה. בכל הזוגות הללו אנחנו מתחילים מ-\( x \) הגדול ביותר האפשרי ובמעבר לזוג הבא מקטינים אותו ב-1 ומגדילים את \( y \) ב-1.

\( P\left(x,y\right) \) היא בבירור הפונקציה ההפוכה ל-\( L,R \), כלומר מתקיים \( P\left(L\left(z\right),R\left(z\right)\right)=z \) לכל \( z \), כמו גם \( L\left(P\left(x,y\right)\right)=x \) ו-\( R\left(P\left(x,y\right)\right)=y \). בראשית ימי הבלוג הצגתיאת הפונקציה הזו (בניסוח טיפה יותר מפורש וטיפה שונה) ואמרתי ש”רק אתמול גיליתי” את הפונקציה (מה שנכון נכון). בתגובות לפוסט העירו לי שאם מעוניינים לקודד כל זוג מספרים טבעיים באופן חח”ע ועל באמצעות מספר טבעי יחיד אפשר גם להשתמש בפונקציה \( f\left(x,y\right)=2^{x}\left(2y+1\right)-1 \) (שהולכת מהטבעיים עם 0 לטבעיים עם 0, אבל זה לא באמת משנה) שהיא קצת יותר ברורה. החסרון של הפונקציה הזו בהקשר הנוכחי היא שבגלל ה-\( 2^{x} \) שמופיע שם לא ברור איך להוכיח שהיא דיופנטית בלי עוד עבודה, וגם לא ברור איך “להפוך” אותה באמצעות פונקציות דמויות \( L,R \). במקרה שלנו, לעומת זאת, קל לראות שכל הפונקציות שהצגתי הן דיופנטיות. הבה ונעשה זאת במפורש:

1. \( x=L\left(z\right)\iff\exists y\left(2z=\left(x+y-2\right)\left(x+y-1\right)+2y\right) \)
2. \( y=R\left(z\right)\iff\exists x\left(2z=\left(x+y-2\right)\left(x+y-1\right)+2y\right) \)
3. \( z=P\left(x,y\right)\iff2z=\left(x+y-2\right)\left(x+y-1\right)+2y \)

זה משלים את החלק הראשון של הבניה שלנו: הראנו שמספור (והיפוך המספור) של זוגות של טבעיים הוא פונקציה דיופנטית. כעת - להגדרת הפונקציה \( S\left(i,u\right) \), שהיא כבר ממש בהישג ידינו!

נגדיר \( S\left(i,u\right)=L\left(u\right)\mbox{ mod }\left(1+iR\left(u\right)\right) \), וזו הפונקציה המבוקשת. רגע, מה?

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

כעת, בואו ננסה להבין איך הפונקציה “עובדת”. כל סדרה מקודדת על ידי מספר \( u \), שבעצם אנחנו חושבים עליו כאילו הוא מקודד זוג מספרים טבעיים, \( \left(a,b\right) \). עכשיו לוקחים את \( a \) ומתחילים “לגרד” ממנו את אברי הסדרה: מחלקים אותו ב-\( 1+b \), ב-\( 1+2b \), ב-\( 1+3b \) וכן הלאה… בכל פעם לוקחים את השארית ומוסיפים אותה לסדרה. מתישהו \( 1+ib \) הולך להיות גדול יותר מ-\( a \) ואז הסדרה “תתקע” על להחזיר \( a,a,a,\dots \) כל הזמן, אבל זה לא מפריע לנו - אנחנו רוצים רק לקודד סדרות סופיות ולא מעניין אותנו מה קורה עבור \( i \)-ים שגדולים מאורך הסדרה.

מה שאני צריך לשכנע אתכם בו הוא כפול: ראשית, שהפונקציה הזו דיופנטית; את זה אעשה אחר כך. שנית, שאכן אפשר לקבל כל סדרה סופית בעזרת השיטה הזו של לקחת \( a \) מסויים ולהתחיל “לקלף” אותו עם \( 1+ib \).

כאן נכנס משפט השאריות הסיני לתמונה. נניח שאנחנו רוצים לקודד את הסדרה \( a_{1},\dots,a_{N} \). בואו נניח גם שאנחנו מכירים \( b \) כלשהו כך ש-\( 1+b,1+2b,\dots,1+Nb \) כולם זרים זה לזה. במקרה הזה, ניצחנו, כי נסתכל על מערכת המשוואות:

\( x\equiv_{1+b}a_{1} \)

\( \vdots \)

\( x\equiv_{1+Nb}a_{N} \)

משפט השאריות הסיני מבטיח שקיים למערכת הזו פתרון. ניקח את הפתרון הזה להיות \( a \), וסיימנו. השאלה, אם כן, היא רק האם לכל \( N \) טבעי קיים \( b \) טבעי כך ש-\( 1+b,1+2b,\dots,1+Nb \) כולם זרים זה לזה. בואו נשאל את עצמנו מה יגרום לכך שעבור \( N \) מסויים \( b \) ספציפי לא יעבוד, כלומר יהיו \( i,j \) כך ש-\( 1+ib,1+jb \) לא יהיו זרים, כלומר יהיה איזה שהוא מספר \( d \) שמחלק את שניהם.

אם \( d \) מחלק את שניהם, הוא מחלק גם כל צירוף לינארי שלהם, כלומר סכום שלהם כשהם מוכפלים במספר שלם כלשהו, כלומר \( d \) בפרט מחלק גם את \( j\left(1+ib\right)-i\left(1+jb\right)=j-i \). עכשיו, מכיוון ש-\( 1\le i,j\le N \) הרי שבהכרח גם \( 1\le d\le N \); לכן כדי שנקבל מספרים זרים די לנו להבטיח שאף אחד מהם לא יוכל להתחלק על ידי מספר שבין 1 ל-\( N \). התעלול פשוט: נבחר את \( b \) להיות מספר שמתחלק ב-\( N! \), ובנוסף לכך הוא גם גדול מכל האיברים \( a_{1},\dots,a_{N} \) של סדרה (כדי להבטיח ש-\( a \) מודולו \( 1+ib \) אכן יחזיר את \( a_{i} \) ולא רק מספר ששקול לו). כעת, אם \( b \) מתחלק ב-\( N! \) אז בפרט כל \( 1\le d\le N \) מחלק את \( b \), ולכן מחלק את \( ib \), ולכן לא מחלק את \( 1+ib \); זו הסיבה לבחירה ה”מוזרה” שלנו בסדרת המודולוסים.

התעלול המקסים הזה קודם לעיסוק בפונקציות דיופנטיות; הוא מופיע כבר במאמר המפורסם של קורט גדל שבו הוא הוכיח את משפט אי השלמות שלו (כזכור, זה גם המאמר שבו הופיעו הפונקציות הרקורסיביות לראשונה). עם זאת, אנחנו הולכים צעד אחד מעבר לגדל בכך שאנחנו מוכיחים גם ש-\( S\left(i,u\right) \) היא דיופנטית.

הנה מערכת משוואות דיופנטיות שמראה ש-\( S\left(i,u\right) \) דיופנטית:

\( S\left(i,u\right)=w \)

\( \iff \)

\( x=L\left(u\right)\wedge y=R\left(u\right) \)

\( \wedge\exists z\left(x=w+z\left(1+iy\right)\right) \)

\( \wedge\exists v\left(1+iy=w+v-1\right) \)

שתי המשוואות הראשונות נתונות בצורה לא מפורשת על ידי \( x=L\left(u\right)\wedge y=R\left(u\right) \) שכבר ראינו. זו בעצם דרך “לפרק” את\( u \) לתוך המשתנים \( x,y \) של המשוואה הדיופנטית. השורה הבאה אומרת לנו ש-\( w \) התקבל מ-\( x \) על ידי חלוקה ב-\( \left(1+iy\right) \) ולקיחת שארית (\( z \) הוא המנה של החלוקה). השורה האחרונה אומרת לנו במפורש ש-\( w\le1+iy \) (העדפתי לכתוב זאת במפורש מאשר לכתוב את הנוסחה עם סימן האי-שוויון, כי מי זוכר כבר איך הראינו שהיחס הזה דיופנטי). בקיצור, ההוכחה היא פשוטה למדי, בהינתן מה שכבר למדנו על פונקציות דיופנטיות!

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