אנדרה סמרדי: בכל כאוס יש סדר
שישה חודשים לאחר שהחל את לימודי הרפואה, החליט אנדרה סמרדי (Endre Szemerédi) שהוא אינו סומך על עצמו עם אזמל מנתחים — הוא הטיל ספק ביכולתו, כפי שאמר מאוחר יותר, "לבצע עבודה הנושאת באחריות כזו" — ועזב את הלימודים. הוא חיפש את דרכו לזמן מה, אז נרשם ללימודי מתמטיקה, ושובץ בטעות מנהלית למנחה דוקטורט שמעולם לא ביקש. הטעות בניירת הציבה אותו במוסקבה תחת הדרכתו של ישראל גלפנד (Israel Gelfand), אחד המתמטיקאים הדגולים של המאה העשרים, במקום תחת אלכסנדר גלפונד (Alexander Gelfond), אותו סמרדי ביקש מלכתחילה. זוהי אחת התאונות המוצלחות בתחום.
מבודפשט למוסקבה בטעות
סמרדי נולד ב-21 באוגוסט 1940 בבודפשט. לאחר ניסיונו הקצר והזנוח ברפואה, הוא השלים את התואר הראשון באוניברסיטת אטווש לוראנד (Eötvös Loránd University) בבודפשט לפני שעבר לאוניברסיטת מוסקבה לצורך לימודי התואר השני והדוקטורט. שם, תחת גלפנד — אותה טעות מנהלית ששלחה אותו למנחה הלא נכון — הוא החל את הקריירה במתמטיקה בדידה, שלימים תעניק לו הכרה שוות ערך למדליית פילדס שניתנת לעיתים רחוקות עבור קומבינטוריקה: פרס אבל.
המשפט הנושא את שמו
הישגו המגדיר של סמרדי, שפורסם ב-1975, פתר השערה שפול ארדש (Paul Erdős) ופאל טוראן (Pál Turán) הציגו עשורים קודם לכן ושעמדה בפני כל ניסיון הוכחה מאז: שכל קבוצה של מספרים טבעיים בעלת צפיפות עליונה חיובית — בקירוב, כל קבוצה שאינה מתדלדלת לאפס ביחס לציר המספרים כולו — חייבת להכיל סדרות חשבוניות מכל אורך, לא משנה כמה ארוכות. זוהי הצהרה על סדר חבוי: לא משנה כמה לא סדירה או דלילה נראית קבוצה משמעותית מספיק של מספרים שלמים, סדרות בעלות תבנית חבויות בתוכה באופן בלתי נמנע. ועדת פרס אבל סיכמה מאוחר יותר את רוח עבודתו במשפט אחד: "בכל כאוס יש סדר".
למת הרגולריות
ההוכחה של אותו משפט הניבה משהו בעל השלכות רבות אף יותר מהמשפט עצמו. לאורך הדרך, הציג סמרדי את מה שנקרא כיום למת הרגולריות של סמרדי, תוצאה מבנית המראה שכל גרף גדול מספיק ניתן לחלוקה למספר חסום של חלקים המתנהגים, במובן סטטיסטי מדויק, כמעט באקראיות זה כלפי זה. זה נשמע כמו למת טכנית; היא הפכה לאחד הכלים המרכזיים של הקומבינטוריקה המודרנית, והיא מהווה בסיס לבדיקת תכונות, תורת גבולות של גרפים, וחלק ניכר מתורת הגרפים הקיצונית שפותחה בעשורים שחלפו מאז. זוכי מדליית פילדס, בהם טימותי גוורס (Timothy Gowers) ולאסלו לובאס (László Lovász), הקדישו הרצאות שלמות למעקב אחר השלכותיה — מקרה נדיר שבו תוצר הלוואי של הוכחה עולה בהשפעתו על המשפט המקורי.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →גוף של תוצאות על שמו
הקריירה של סמרדי הניבה צבר גדול באופן יוצא דופן של תוצאות שנושאות כיום את שמו לצד שמות שותפיו למחקר: משפט סמרדי-טרוטר (Szemerédi–Trotter) בגיאומטריה של התנגשויות, התוחם כמה פעמים נקודות וקווים במישור יכולים להיפגש; משפט היינאל-סמרדי (Hajnal–Szemerédi) בצביעת גרפים; משפט ארדש-סמרדי (Erdős–Szemerédi) על סכומים ומכפלות בקבוצות סופיות, תוצאה יסודית במה שהפך לתחום הקומבינטוריקה החיבורית; וביחד עם מיקלוש אייטאי (Miklós Ajtai), את משפט הפינות. עם אייטאי ויאנוש קומלוש (János Komlósh) הוא קבע חסמים משפיעים על מספרי רמזי ובנה רשתות מיון בעלות עומק אופטימלי — גיחה נדירה ממתמטיקה טהורה למדעי המחשב התיאורטיים שעזרה להצדיק את מקום עבודתו האקדמי בסופו של דבר במחלקה למדעי המחשב. עם אייטאי, ואצלב חבטאל (Václav Chvátal) ומונרו ניובורן (Monroe Newborn) הוא גם הוכיח את אי-שוויון מספר החצייה, חסם יסודי בציור גרפים. ביותר ממאתיים מאמרים שפורסמו, הקו המנחה עקבי: מציאת מבנה נוקשה ובלתי נמנע בתוך אובייקטים — קבוצות של מספרים שלמים, גרפים, תצורות נקודות — שנראים חסרי סדר על פני השטח שלהם.
קריירה אמריקאית הבנויה על יסודות הונגריים
סמרדי הצטרף לאוניברסיטת ראטגרס (Rutgers University) ב-1986 כפרופסור למדעי המחשב של מדינת ניו ג'רזי, תפקיד בו הוא עדיין מחזיק כפרופסור אמריטוס, בעודו נשאר קשור באופן קבוע למכון אלפרד רניי (Alfréd Rényi Institute of Mathematics) למתמטיקה בבודפשט, הבית המוסדי של המתמטיקה ההונגרית מאז אמצע המאה העשרים. בינתיים הוא החזיק במשרות אורח בסטנפורד, מקגיל, אוניברסיטת קרוליינה הדרומית ואוניברסיטת שיקגו, וכן בחברות במכון למחקר מתקדם בפרינסטון — קריירה המשתרעת על פני ההגירה המתמטית של המלחמה הקרה מהונגריה והגוש הסובייטי לאוניברסיטאות מחקר אמריקאיות.
הכרה
הכיבודים נערמו לאורך חמישה עשורים: פרס אלפרד רניי ב-1973 ופרס ג'ורג' פויה (George Pólya) ב-1975, בשנים שלאחר הופעת המשפט שלו; פרס לירוי פ. סטיל (Leroy P. Steele) ופרס רולף שוק (Rolf Schock) במתמטיקה, שניהם ב-2008; בחירה לאקדמיה הלאומית למדעים של ארצות הברית ב-2010; וב-2012, פרס אבל בעצמו, שהוענק "על תרומותיו היסודיות למתמטיקה בדידה ולמדעי המחשב התיאורטיים, והוקרה על ההשפעה העמוקה והמתמשכת של תרומות אלו על תורת המספרים החיבורית ותורת הארגודית" — ציטוט שמייחס במפורש לעבודתו את עיצובם מחדש של תחומים הרבה מעבר לקומבינטוריקה בהגדרתה הצרה. הונגריה הפכה אותו לזוכה מסדר אישטוון הקדוש בשנת 2020.
מדוע אנדרה נקרא גאון
המקרה בעד גאונותו של סמרדי הוא ברור ככל שהמתמטיקה יכולה להציע: הוכחה אחת, של השערה אחת ארוכת ימים, יצרה כלי — למת הרגולריות — שהשפעתו במורד הזרם על תחום שלם עולה ללא ספק על זו של המשפט שלשמו היא נבנתה. סוג כזה של השפעה מסדר שני, שבו השיטה מאריכה ימים ועולה על מטרתה המקורית, הוא אחד הסימנים הברורים ביותר בשדה של מוח הפועל ברמה המבנית העמוקה ביותר במקום רק לפתור את הבעיה שלפניו. שפתה של ועדת פרס אבל עצמה — איתור סדר בתוך כאוס — אינה הגזמה; זהו ניסוח מחדש הוגן של מה שלמת הרגולריות עושה בפועל, והעובדה שגוורס ולובאס, בעצמם מהדמויות המעוטרות ביותר בתחום, בנו הרצאות מרכזיות סביב הסבר השלכותיה למתמטיקאים אחרים היא סוג של הערכת עמיתים שקשה לייצר או לנפח.
אם יש סייג, הוא נוגע לצמצום ולא להגזמה: תהילתו של סמרדי נשענת ברובה המכריע על תוצאות במתמטיקה בדידה וקומבינטוריקה, תחומים שחלק ניכר מהמאה העשרים נתפסו על ידי חלקים מהממסד המתמטי כפחות יוקרתיים מאנליזה, גיאומטריה או תורת המספרים בצורתם הקלאסית — פרס אבל לקומבינטוריקאי נתפס בעצמו באותה עת כטיעון מרומז שהתחום ראוי להכרה לה הוא חיכה זמן רב. זה לא מפחית מהעבודה; זה אומר שהתווית "גאון" כאן עוקבת אחר צורה טכנית ספציפית של תובנה מבנית ולא אחר סוג של תהילה אוניברסלית המיוחסת לפיזיקאים או מתמטיקאים שתוצאותיהם מפורסמות גם מחוץ לתחומם.
מורשת
למת הרגולריות נלמדת כעת כחומר סטנדרטי בקורסי קומבינטוריקה לתארים מתקדמים ברחבי העולם ונשארת מנוע פעיל למחקר חדש, כולל בתחומים — מדעי המחשב התיאורטיים, קומבינטוריקה חיבורית, תורת גבולות של גרפים — שכמעט ולא היו קיימים כשסמרדי כתב אותה לראשונה ב-1975. הוא עדיין פעיל כחוקר אמריטוס בשנות השמונים לחייו, ונשאר אחד המקרים הברורים ביותר במתמטיקה המודרנית של שיטת הוכחה אחת שהופכת למשמעותית יותר מהמשפט שהיא נועדה לבסס.