אי-שוויון גרותנדיק

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

הקבוע  הוא הקבוע  המינימלי שמקיים את הגדרה זו, והוא שונה עבור השדות  ו-. ערכו המדויק של  אינו ידוע עד היום. עבור המקרה הממשי, , מעריכים כי .

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

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

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

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

הערכת קבוע גרותנדיק
מאז פרסום מאמרו המקורי של גרותנדיק, מתמטיקאים שונים ניסו לפשט ולשפר את ההוכחה של אי-השוויון, וכן להשיג חסמים טובים יותר עבור קבוע גרותנדיק. להלן נקודות ציון עיקריות:
 גרותנדיק (1953): הראה . עבור המקרה המרוכב, הראה  וכן .
 לינדנשטראוס ופלצ'ינסקי (1968): הציגו את הניסוח המטריציוני של אי-השוויון ופישטו את הוכחתו של גרותנדיק למקרה הממשי, אך לא שיפרו את החסמים.
 ריץ (1974): שיפר את החסם העליון ל-.
 קריבין (1977): השיג את החסם העליון הממשי הטוב ביותר הידוע עד היום (שאינו אסימפטוטי): .
 האגרופ (1981, 1987): הרחיב את שיטת קריבין למקרה המרוכב והשיג .
 דייווי (1984): סיפק את החסמים התחתונים הטובים ביותר הידועים לזמנו:  וכן .
 בראברמן, מקריצ'ב, מקריצ'ב ונאור (2011): הראו באופן לא קונסטרוקטיבי שמתקיים , כלומר החסם של קריבין אינו הדוק. עם זאת, טרם נמצא חסם עליון קונסטרוקטיבי טוב יותר.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

עבור  כאשר , מתקיים:אם כן, מערכת ראדמאכר מהווה בסיס מתאים לשיכון שחיפשנו, וקיומה מוכיח את אי שוויון גרותנדיק! מהו הקבוע שקיבלנו? היות ש-, מההוכחה שלנו מעלה נובע (עם , , ):בעוד שידוע . למעשה, ניתן להגיע לחסם של קריבין בדרך דומה אך עם שיכון מתוחכם יותר.

יישומים
אומדן נורמת החיתוך (Cut Norm)
בהינתן מטריצה ממשית  בגודל , נורמת החיתוך שלה מוגדרת על ידי:

נורמת החיתוך קשורה לבעיית חתך מרבי (Max-Cut) בגרפים ומופיעה באלגוריתמי קירוב.
אי-שוויון גרותנדיק מספק קשר בין נורמת החיתוך,  ו-. ידוע כי:

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

שילוב אי-שוויונות אלו מראה שניתן לקרב את  באמצעות , ואת  באמצעות :

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

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

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

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

חסם צירלסון
בשנת 1935, אלברט איינשטיין, בוריס פודולסקי ונתן רוזן (EPR) פרסמו מאמר בו טענו שמכניקת הקוונטים אינה תאוריה שלמה של המציאות הפיזיקלית, ורמזו לקיומם של "משתנים חבויים" שיכולים להסביר את התוצאות הסטוכסטיות של מדידות קוונטיות באופן דטרמיניסטי (הפרדוקס של איינשטיין-פודולסקי-רוזן).
בשנת 1964, ג'ון סטיוארט בל הראה שכל תאוריית משתנים חבויים מקומית גוררת אי-שוויונות מסוימים (אי-שוויוני בל) לגבי המתאמים (קורלציות) בין מדידות הנערכות על מערכות פיזיקליות מרוחקות. מכניקת הקוונטים, לעומת זאת, חוזה הפרה של אי-שוויונות אלו.
קלאוזר, הורן, שימוני והולט (CHSH) הציעו ב-1969 גרסה של אי-שוויון בל (אי-שוויון CHSH) שניתנת לבדיקה ניסיונית. ניסויים רבים אישרו את תחזיות מכניקת הקוונטים והפרו את אי-שוויון CHSH, ובכך שללו תאוריות משתנים חבויים מקומיות.
ב-1980, בוריס צירלסון הראה שמכניקת הקוונטים עצמה מטילה חסם על מידת ההפרה האפשרית של אי-שוויון CHSH, ושקבוע גרותנדיק  קובע את ההפרה המקסימלית של אי-שוויוני בל כלליים יותר (מסוג מסוים) במכניקת הקוונטים.

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

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

לאורך השנים פותחו חסמים שונים על קבועי גרותנדיק אלו:
גבולות תחתונים עבור  (ממשי)dGrothendieck, 1953Krivine, 1979Davie, 1984.Fishburn et al., 1994.Vértesi, 2008.Briët et al., 2011.Hua et al., 2015.Diviánszky et al., 2017.Designolle et al., 2023Designolle et al., 2024 2 ≈ 1.4142131.417241.417581.43591.436651.4367041.445211.445661.48211.485795 ≈ 1.428571.460071.461121.4933961.4701771.462861.4758381.475861.4797291.48608101.49431∞ ≈ 1.570791.67696
גבולות עליונים עבור  (ממשי)dGrothendieck, 1953Rietz, 1974.Krivine, 1979Braverman et al., 2011Hirsch et al., 2016.Designolle et al., 2023 2 ≈ 1.4142131.51631.46441.45464 ≈ 1.570881.6641∞ ≈ 2.301302.261 ≈ 1.78221

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

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

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

חסם זה הוא הדוק אסימפטוטית.

לקריאה נוספת
 Joe Diestel, Jan H. Fourie, Johan Swart, The Metric Theory of Tensor Products: Grothendieck’s Résumé Revisited, American Mathematical Society, 2008
קישורים חיצוניים

 Mike Jury, Why is Grothendieck’s inequality true?, University of Florida

הערות שוליים

גרותנדיק
קטגוריה:אנליזה פונקציונלית