טריקים מתמטיים לאילוף המרחק הבינוני | מגזין קוונטה

עד כה השנה, Quanta תיארה שלוש התקדמות מרכזיות בתיאוריית רמזי, המחקר כיצד להימנע מיצירת דפוסים מתמטיים. ה תוצאה ראשונה שים מכסה חדשה לגודל קבוצת מספרים שלמים מבלי להכיל שלושה מספרים ברווח שווה, כמו {2, 4, 6} או {21, 31, 41}. ה שני ו שְׁלִישִׁי באופן דומה לשים גבולות חדשים לגודל של רשתות ללא אשכולות של נקודות שכולן מחוברות או כולן מבודדות זו מזו.

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

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

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

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

למרות שהתוצאה של קלי ומקה חלה גם אם N הוא קטן יחסית, זה לא נותן גבול שימושי במיוחד במקרה כזה. עבור ערכים קטנים מאוד של N, עדיף לך לדבוק בשיטות פשוטות מאוד. אם N הוא, נניח, 5, פשוט תסתכל על כל קבוצות המספרים האפשריות בין 1 ל N, ובחר את הגדול ביותר ללא התקדמות: {1, 2, 4, 5}.

אבל מספר התשובות האפשריות השונות גדל מהר מאוד ומקשה מדי על שימוש באסטרטגיה פשוטה כל כך. יש יותר ממיליון סטים המורכבים ממספרים בין 1 ל-1. יש יותר מ-20⁶⁰ שימוש במספרים בין 1 ל-200. מציאת הסט ללא התקדמות הטוב ביותר עבור מקרים אלה דורשת מנה כבדה של כוח מחשוב, אפילו עם אסטרטגיות לשיפור היעילות. "אתה צריך להיות מסוגל לסחוט הרבה ביצועים מהדברים", אמר ג'יימס גלן, מדען מחשבים באוניברסיטת ייל. בשנת 2008, Gasarch, Glenn and קלייד קרוסקל של אוניברסיטת מרילנד כתב תוכנית כדי למצוא את ההגדרות הגדולות ביותר ללא התקדמות עד an N של 187. (עבודה קודמת קיבלה את התשובות עד 150, כמו גם עבור 157.) למרות רשימת הטריקים, התוכנית שלהם לקחה חודשים לסיום, אמר גלן.

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

גאסארך, גלן וקרוסקל ניסו גם כמה אסטרטגיות אחרות. רעיון אחד מבטיח נשען על אקראיות. דרך פשוטה להמציא סט ללא התקדמות היא לשים 1 בסט שלך, ואז תמיד להוסיף את המספר הבא שלא יוצר התקדמות אריתמטית. בצע את ההליך הזה עד שתלחץ על המספר 10, ותקבל את הסט {1, 2, 4, 5, 10}. אבל מסתבר שזו לא האסטרטגיה הטובה ביותר באופן כללי. "מה אם לא נתחיל ב-1?" אמר גאסארך. "אם אתה מתחיל ממקום אקראי, אתה באמת מצליח יותר." לחוקרים אין מושג מדוע אקראיות כל כך שימושית, הוא הוסיף.

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

ב1981, ברנדן מקיי, כיום מדען מחשבים באוניברסיטה הלאומית של אוסטרליה, כתב תוכנה בשם nauty, שנועדה להפוך את חישוב מספרי רמזי לפשוט יותר. Nauty מבטיחה שהחוקרים לא יבזבזו זמן בבדיקת שני גרפים שהם רק גרסאות מתהפכות או מסובבות אחד של השני. "אם מישהו נמצא באזור ולא משתמש בנאוטי, המשחק נגמר. אתה חייב להשתמש בו," אמר סטניסלב רדזישובסקי, מתמטיקאי במכון הטכנולוגי של רוצ'סטר. ובכל זאת, כמות החישוב הכרוכה כמעט בלתי מובנת. בשנת 2013, Radziszowski and יאן גודגבור הוכיח את זה r(3, 10) הוא לכל היותר 42. "זה לקח, אני חושב, כמעט 50 שנות מעבד", אמר Goedgebeur, מדען מחשבים באוניברסיטת KU Leuven בבלגיה.

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

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

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

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