הנפה של ארטוסטנס-לז’נדר

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

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

א.      נסתכל על כל המספרים מ- 1-100 בטבלה

 10

 9

 8

 7

 6

 5

 4

 3

 2

 1

 20

 19

 18

17

 16

 15

 14

 13

 12

 11

 30

 29

 28

 27

 26

 25

 24

 23

 22

 21

 40

 39

 38

 37

 36

 35

 34

 33

 32

 31

 50

 49

 48

 47

 46

 45

 44

 43

 42

 41

 60

 59

 58

 57

 56

 55

 54

 53

 52

 51

 70

 69

 68

 67

 66

 65

 64

 63

 62

 61

 80

 79

 78

 77

 76

 75

 74

 73

 72

 71

 90

 89

 88

 87

 86

 85

 84

 83

 82

 81

 100

 99

 98

 97

 96

 95

 94

 93

 92

 91

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

 

 9

 

 7

 

 5

 

 3

 2

 1

 

 19

 

 17

 

 15

 

 13

 

 11

 

 29

 

 27

 

 25

 

 23

 

 21

 

 39

 

 37

 

 35

 

 33

 

 31

 

 49

 

 47

 

 45

 

 43

 

 41

 

 59

 

 57

 

 55

 

 53

 

 51

 

 69

 

 67

 

 65

 

 63

 

 61

 

 79

 

 77

 

 75

 

 73

 

 71

 

 89

 

 87

 

 85

 

 83

 

 81

 

 99

 

 97

 

 95

 

 93

 

 91

 אם נמחק כעת באופן דומה את כל הכפולות של 3 חוץ מ-3, את של 5 חוץ מ-5 ואת של 7  חוץ מ-7 נקבל

     

  7

 

  5

 

  3

  2

  1

 

 19

 

 17

     

 13

 

 11

 

 29

         

 23

   
     

 37

         

 31

     

 47

     

 43

 

 41

 

 59

         

 53

   
     

 67

         

 61

 

 79

         

 73

 

 71

 

 89

         

 83

   
     

 97

           

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

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

   

13

 

 11

                   

   31

 

  29

         

23

     

19

 

17

   47

     

   43

 

  41

     

37

       
   

  61

 

   59

         

53

       

   79

         

  73

 

71

     

67

   
           

  89

         

83

   
   

 109

 

107

     

103

 

101

     

97

 127

         

 121

 

 

         

113

 143

     

  139

 

 137

       

131

   
 

 157

     

 

     

149

   
   

 173

     

 169

 

167

     

163

 

 191

     

  187

     

 

 

181

 

 

   
       

 

     

199

 

197

     

193

 223

 

 221

       

 

     

211

 

209

 239

         

 233

     

229

 

227

   
   

 253

 

  251

     

247

         

241

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

פונקציית מביוס

כלי שמשמש לעשות זאת נקרא “פונקציית מביוס”. הפונקציה הזאת מסומנת באות היוונית \({ \mu }\)   (“מו”, שהיא ה”מם” היוונית, האות הראשונה בשמו של מביוס , 1790 – 1868, מתמטיקאי ואסטרונום גרמני, תלמידו של גאוס. על שמו גם נקראת “טבעת מביוס”)

לשם כך, נצטרך לעשות הכרה עם פונקציה אריתמטית (=פונקציה שמקבלת ערכים טבעיים בלבד) הידועה בשם פונקציית מביוס – \({ \mu }\). לצורך זה נגדיר מספר טבעי חסר-ריבועים כמספר שכל המחלקים הראשוניים שלו שונים. למשל המספר \({ 3\cdot2=6 }\) הוא חסר ריבועים בעוד ש- \({ 3\cdot2\cdot2=12 }\) לא.  עבור מספר טבעי \({n = p_1 \dotsm p_r }\) חסר ריבועים פונקציית מביוס \({ \mu(n) }\)  מוגדרת כ- \({ (-1)^r }\) בעוד שעבור מספר שאיננו חסר-ריבועים הפונקציה מוגדרת כאפס. מתברר שלפונקציה זו יש תכונה מאוד חשובה לשיטות נפה.

משפט.

\[ \sum_{d|n} \mu(d) = \left\{ \begin{array}{l l} 1 & \quad n=1\\ 0 & \quad n\not=1 \end{array} \right.\]

שימו לב כי ברישום זה \({  \sum_{d|n} \mu(d) }\) פירושו סכום הערכים \({   \mu(d) }\) כאשר \({ d }\) “רץ” על כל המחלקים של \({ n }\).

דוגמא. \({  \sum_{d|6} \mu(d) = \mu(1) + \mu(2) + \mu(3) + \mu(6) = 1 + (-1) + (-1) + 1 = 0 }\) 

נסמן: \({ f(n) = \sum_{d|n} \mu(d) }\) אזי על פי המשפט נקבל כי \[ f(n) = \left\{ \begin{array}{l l} 1 & \quad n=1\\ 0 & \quad n\not=1 \end{array} \right.\]

מדוע זה חשוב? משום  שאנו יכולים להחליף את \({ n }\) בסכום הזה במחלק המשותף המקסימלי של \({ n }\)  ו-\({ m }\) , מספר שאנו מסמנים אותו ב-\({ (m,n) }\)  . כשעושים זאת מקבלים \[ f((m,n)) = \left\{ \begin{array}{l l} 1 & \quad (m,n)=1\\ 0 & \quad (m,n)\not=1 \end{array} \right.\]

כלומר הפונקציה תיתן 1 כל אימת ש-\({ (m,n)=1 }\)  (שפירושו ש -\({ n }\)  ו-\({ m }\)  זרים) ואפס אחרת. אם כעת נסמן \({n =2\cdot3 \dotsm p_r }\) אזי \({ f((m,2\cdot3 \dotsm p_r))}\)  יתן 1 כל אימת ש-\({ (m,2\cdot3 \dotsm p_r)=1}\)  כלומר כאשר כל המחלקים הראשוניים של \({ m } \) גדולים מ-\({ p_r} \). כלומר הסכום \({ \sum_{m \leq x}f((m,2\cdot3 \dotsm p_r))}\) סופר את הטבעיים עד \({ x} \) שכל המחלקים הראשוניים שלהם גדולים מ-\({ p_r} \). הנקודה המעניינת היא שגם קל יחסית להעריך את הסכום האחרון. לכך לא ניכנס כאן. מכאן אפשר ללמוד כל מיני שיטות להערכת הסכום האחרון. אחת מהן היא השיטה של חתן פרס פילדס ופרס וולף הנורבגי אטלה סלברג, מגדולי המתמטיקאים של המאה ועשרים (1917-2007). את השיטה הקרויה על שמו, נפת סלברג, גילה סלברג עוד בשנות החמישים של המאה ה-20. כזכור השערת התאומים הראשוניים גורסת כי יש אינסוף זוגות של ראשוניים שהמרחק ביניהם הוא 2.

ב-1985 הוכיחו גולדסטון, יילדרים ופינץ באמצעות נפת סלברג כי קיימים אינסוף זוגות של ראשוניים \({ p_n} \) ו-\({ p_{n+1}} \) כך שהמרחק ביניהם קטן מ- \({ \log p_n} \). באביב שעבר הצליח ז’אנג, מתמטיקאי סיני עלום שם, לשפר את תוצאה זו לכדי 70,000,000!  בסוף שנה שעברה, מיינהארד, פוסטדוקטורנט בריטי, הצליח בטכניקה שונה מזו של ז’אנג להקטין את המספר ל-600. כיום, עובדת קבוצה של מתמטיקאים בניסיון להקטין מספר זה דרך כל מיני שיפורים בחישובים. בדרך זו הצליחו לשפר את התוצאה ל-246!

4 תגובות על הנפה של ארטוסטנס-לז’נדר

  • מאת אורח‏:

    למי שמתעניין: אותה קבוצת מתמטיקאים ששיפרה את התוצאה ל-246 הוכיחה גם שבהינתן הכללה של השערה מסוימת בשם השערת Elliott–Halberstam, ניתן לשפר את התוצאה ל-6!
    בויקי של הפרויקט לשיפור התוצאה (http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes) ניתן לראות את החסמים שהקבוצה מצאה גם לערכים שונים מ-2 (כלומר במקום לדבר על זוגות ראשוניים שההפרש ביניהם הוא 2 (קרי, ראשוניים תאומים), מדברים על זוגות ראשוניים שההפרש ביניהם הוא m.)

  • מאת יוסי‏:

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

  • מאת לא רלוונטי‏:

    הפסקה האחרונה מופיעה פעמיים (עם שינוי קטן),
    והתכוונת במשפט הראשון שלה p_(n+1) zz ולא p_n+1.

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

  • מאת admin‏:

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