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

אי-שוויון גרותנדיק (GT) הוא תוצאה יסודית באנליזה פונקציונלית ובתורת האופרטורים. הוא קובע כי עבור שדה $\mathbb{𝔽}\in \{\mathbb{ℝ},\mathbb{ℂ}\}$ קיים קבוע אוניברסלי $K_G^{\mathbb{𝔽}}$ (הנקרא קבוע גרותנדיק) כך שלכל מטריצה $A=(a_{ij})$ בגודל $m\times n$ מעל $\mathbb{𝔽}$, לכל מרחב הילברט $H$ מעל $\mathbb{𝔽}$ ואוסף וקטורים $u_1,\dots ,u_m\in H$ ו-$v_1,\dots ,v_n\in H$ בכדור היחידה של $H$, מתקיים:

$$|\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}⟨u_i,v_j{⟩}_H|\le K_G^{\mathbb{𝔽}}\underset{|p_i|\le 1,|q_j|\le 1}{\sup }\left|\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{p}_i{q}_j\right|$$

הקבוע $K_G^{\mathbb{𝔽}}$ הוא הקבוע $K$ המינימלי שמקיים את הגדרה זו, והוא שונה עבור השדות $\mathbb{ℝ}$ ו-$\mathbb{ℂ}$. ערכו המדויק של $K_G^{\mathbb{𝔽}}$ אינו ידוע עד היום. עבור המקרה הממשי, $K_G^{\mathbb{ℝ}}$, מעריכים כי $1.67\lesssim K_G^{\mathbb{ℝ}}\lesssim 1.78$.

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

אי השוויון זכה לניסוחים שקולים בתחומים שונים במתמטיקה. בין היתר הוצג כמשפט על צורות ביליניאריות חסומות, נורמות של מכפלות טנזוריות, אופרטורים בין מרחבי בנך, ואופרטורים בין המרחבים $L_{\mathrm{\infty }}$ ו-$L_1$. כל אחד מהנוסחים מדגיש היבט אחר של אותה תופעה מתמטית.

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

בתחום מידע קוונטי מופיע אי-השוויון במחקר אי-שוויוני בל, ובפרט בבעיית ההפרה המקסימלית האפשרית של גבולות קלאסיים (כגון חסם צירלסון). כאן $K_G^{\mathbb{𝔽}}$ משקף את גודל ההפרה האפשרית על ידי מערכות קוונטיות. אי-השוויון אף היווה השראה לפיתוח גרסאות מורחבות שלו (נקראות לעיתים "אי-שוויוני גרותנדיק מסוגים שונים"), אשר חלות על אופרטורים לא ליניאריים, מכפלות מולטילינאריות, גרפים, ועוד.

הערכת קבוע גרותנדיק

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

1. גרותנדיק (1953): הראה $\frac{\pi }{2}\le K_G^{\mathbb{ℝ}}\le \sinh (\frac{\pi }{2})\approx 2.3013$. עבור המקרה המרוכב, הראה $K_G^{\mathbb{ℂ}}\le K_G^{\mathbb{ℝ}}$ וכן $K_G^{\mathbb{ℂ}}\ge 4/\pi \approx 1.273$.
2. לינדנשטראוס ופלצ'ינסקי (1968): הציגו את הניסוח המטריציוני של אי-השוויון ופישטו את הוכחתו של גרותנדיק למקרה הממשי, אך לא שיפרו את החסמים.
3. ריץ (1974): שיפר את החסם העליון ל-$K_G^{\mathbb{ℝ}}\lesssim 2.261$.
4. קריבין (1977): השיג את החסם העליון הממשי הטוב ביותר הידוע עד היום (שאינו אסימפטוטי): $K_G^{\mathbb{ℝ}}\le \frac{\pi }{2\ln (1+\sqrt{2})}\approx 1.78221$.
5. האגרופ (1981, 1987): הרחיב את שיטת קריבין למקרה המרוכב והשיג $K_G^{\mathbb{ℂ}}\lesssim 1.40491$.
6. דייווי (1984): סיפק את החסמים התחתונים הטובים ביותר הידועים לזמנו: $K_G^{\mathbb{ℝ}}\gtrsim 1.67696$ וכן $K_G^{\mathbb{ℂ}}\gtrsim 1.33807$.
7. בראברמן, מקריצ'ב, מקריצ'ב ונאור (2011): הראו באופן לא קונסטרוקטיבי שמתקיים $K_G^{\mathbb{ℝ}}<\frac{\pi }{2\ln (1+\sqrt{2})}$, כלומר החסם של קריבין אינו הדוק. עם זאת, טרם נמצא חסם עליון קונסטרוקטיבי טוב יותר.

מוטיבציה ואינטואיציה

נניח שיש לנו מטריצה $A=(a_{ij})$ של מספרים ממשיים. אנו שואפים למקסם את הביטוי $$\sum _{i,j}{a}_{ij}{p}_i{q}_j,$$ כאשר $p_i$ ו-$q_j$ נבחרים מתוך $\{-1,1\}$. אפשר לתאר זאת כבעיה קומבינטורית שבה אנו מקצים סימנים לקשתות של גרף ממושקל במטרה להגדיל את סכום המשקולות. ערך הסופרמום של ביטוי זה הוא $\Vert A{\Vert }_{\mathrm{\infty }\to 1}$.

כעת, נרפה את ההגבלה - נאפשר ל-$u_i$ ו-$v_j$ להיות וקטורי יחידה במרחב הילברט $H$ כלשהו, ונבחן את הביטוי $$\sum _{i,j}{a}_{ij}⟨u_i,v_j{⟩}_H.$$ הערך המקסימלי של ביטוי זה על פני כל מרחבי הילברט $H$ וכל בחירות וקטורי היחידה $u_i,v_j$ יסומן $\Vert A{\Vert }_G$. אינטואיטיבית אולי נצפה שככל שמאפשרים גמישות רבה יותר (בחירת וקטורים במקום סקלרים עם ערך מוחלט 1, או סימנים בלבד), הערך המקסימלי יכול לגדול. אי-שוויון גרותנדיק קובע כי היתרון שמתקבל מהמעבר למקרה הווקטורי מוגבל על ידי קבוע אוניברסלי $K_G^{\mathbb{ℝ}}$.

פורמולציה באמצעות הנורמה של אופרטור

ניתן לחשוב על אי-שוויון גרותנדיק גם מהפרספקטיבה של אופרטורים ליניאריים חסומים. המטריצה $A$ מייצגת אופרטור ליניארי $A:{\mathbb{𝔽}}^n\to {\mathbb{𝔽}}^m$. אם נגדיר נורמות $\Vert \cdot {\Vert }_{\alpha },\Vert \cdot {\Vert }_{\beta }$ בהתאמה לכל אחד מהמרחבים הווקטוריים האלו, ניתן לשאול - עד כמה עשוי האופרטור $A$ להגדיל את הנורמה של וקטור שהוא פועל עליו? הנורמה האופרטורית המושרית עונה על שאלה זו: $$\Vert A{\Vert }_{\alpha \to \beta }:=\underset{\Vert u{\Vert }_{\alpha }=1}{\sup }\Vert A(u){\Vert }_{\beta }$$באופן שקול ניתן להגדיר:$$\Vert A{\Vert }_{\alpha \to \beta }=\underset{\Vert u{\Vert }_{\alpha }=1,\Vert v^{*}{\Vert }_{{\beta }^{*}}=1}{\sup }|v^{*}(A(u))|$$כאשר $v^{*}$ מתייחס למרחב הדואלי. בחירה נפוצה של נורמה למרחב ${\mathbb{𝔽}}^n$ היא נורמת ${\ell }_n^{\alpha }$. אם באותו האופן נבחר למרחב ${\mathbb{𝔽}}^m$ את הנורמה ${\ell }_m^{\beta }$, אז הנורמה האופרטורית המתקבלת עבור $A$ היא:$$\Vert A{\Vert }_{\alpha \to \beta }=\underset{\Vert u{\Vert }_{\alpha }=1,\Vert v^{*}{\Vert }_{{\beta }^{*}}=1}{\sup }\left|\sum _{ij}{a}_{ij}{v}_i^{*}{u}_j\right|$$נורמה זו מקסימלית כאשר נבחר $\alpha =\mathrm{\infty },\beta =1$:$$\underset{\alpha ,\beta }{\sup }\Vert A{\Vert }_{\alpha \to \beta }=\Vert A{\Vert }_{\mathrm{\infty }\to 1}:=\underset{u_i,v_j\in \mathbb{𝔽},|u_i|=1,|v_j|=1}{\sup }\left|\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{u}_i^{*}{v}_j\right|$$אי שוויון גרותנדיק מכליל את הביטוי הזה. אכן, $u_i^{*}{v}_j=⟨u_i,v_j{⟩}_{{\mathbb{𝔽}}^1}$ ולכן נוכל להרחיב את ההגדרה למרחב הילברט כללי $H$:$$\Vert A{\Vert }_H:=\underset{u_i,v_j\in H,\Vert u_i{\Vert }_H=1,\Vert v_j{\Vert }_H=1}{\sup }|\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}⟨u_i,v_j{⟩}_H|$$נגדיר את "נורמת" גרותנדיק של המטריצה $A$, כסופרימום של הביטוי הזה על כל מרחבי הילברט מעל $\mathbb{𝔽}$: $$\Vert A{\Vert }_G:=\underset{H}{\sup }\Vert A{\Vert }_H$$אז, אי שוויון גרותנדיק גורס כי קיים קבוע אוניברסלי $K_G^{\mathbb{𝔽}}$ עבורו לכל מטריצה סופית $A$ מעל השדה $\mathbb{𝔽}$: $$\Vert A{\Vert }_G\le K_G^{\mathbb{𝔽}}\cdot \Vert A{\Vert }_{\mathrm{\infty }\to 1}$$במילים, הנורמה האופרטורית המקסימלית שמושרית מהמרחבים הנורמיים ${\ell }^p$, לא יכולה לסטות יותר מדי מהנורמה האופרטורית המקסימלית שמושרית ממרחבי הילברט.

סקיצת הוכחה עבור המקרה הממשי

הקדמה

אלמנט מפתיע באי-שוויון גרותנדיק הוא קיומו של קבוע אוניברסלי עבור כל מרחבי הילברט מעל השדה $\mathbb{𝔽}$. אפשרות אחרת להסתכל על כך היא באמצעות הפורמולציה באמצעות הנורמה של אופרטור. מהפרספקטיבה הזו, אי-השוויון מציג קשר בין קבוצת המרחבים הנורמיים ${\ell }^p$ לבין קבוצת כל מרחבי הילברט מעל $\mathbb{𝔽}$.

דרך אחת להבחין מדוע קבוע כזה קיים, היא לשים לב שניתן לשכן וקטורים ממרחבי הילברט שונים כמשתנים מקריים במרחב הילברט $L^2(\mu )$ עבור מרחב הסתברות $(\mathrm{\Omega },{ℰ},\mu )$. כלומר, אם השיכון של $u,v$ הוא $U,V$ בהתאמה, נדרש $⟨u,v{⟩}_H=\mathbb{𝔼}[UV]=⟨U,V{⟩}_{L^2(\mu )}$.

מציאת שיכון שכזה היא טריוויאלית. על ידי בחירת בסיסים אורתונורמליים $\{e_n\}$ למרחב $H$ ו-$\{{\psi }_n\}$ למרחב $L^2(\mu )$ (לשם הנוחות נניח שהמרחבים $H,L^2(\mu )$ ספרביליים וגם שהמרחב $L^2(\mu )$ מממד אינסופי), נוכל לבחור שיכון: $$x\mapsto X:=\sum _n⟨x_i,e_n{⟩}_H\cdot {\psi }_n$$כך, מתקיים: $$\mathbb{𝔼}[U_i{V}_j]=\sum _n⟨u_i,e_n{⟩}_H\cdot ⟨v_j,e_n{⟩}_H=⟨u_i,v_j{⟩}_H$$בפרט,$\mathbb{𝔼}[|U_i{|}^2]=\Vert u_i\underset{H}{\overset{2}{\Vert }}$. כפי שנראה, אי-שוויון גרותנדיק נובע מקיומו של שיכון בעל תכונה נוספת - שהמשתנים המקריים ${\psi }_n$ שייכים גם ל-$L^p(\mu )$ עבור $p>2$ כלשהו, והנורמות שלהם ב-$L^p(\mu )$ חסומות באופן אחיד. בחירות שונות של שיכונים כאלו יובילו לקבועי גרותנדיק שונים (שאינם בהכרח הדוקים).

נשים לב שמבין כל מרחבי $L^p$, המרחב $L^2$ הוא מרחב הילברט היחיד. מונוטוניות הנורמות על מרחבי $L^p$ משחקת תפקיד מפתח בפיתוח הקשר בין הנורמות $\Vert \cdot {\Vert }_{p\to q},\Vert \cdot {\Vert }_H$ שמופיעות באי-השוויון.

ניסוח תנאי מספק לקיום אי-שוויון גרותנדיק

ראשית, ניווכח שקיומו של שיכון מתאים גורר את אי שוויון גרותנדיק:

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

יהי $2<p<\mathrm{\infty }$, ונניח כי קיים קבוע $C>0$ כך שלכל מרחב הילברט $H$, ולכל בחירת וקטורים $u_1,\dots u_m,v_1,\dots v_n$ בכדור היחידה של $H$, קיים מרחב הסתברות $(\mathrm{\Omega },{ℰ},\mu )$ ושיכון כמשתנים מקריים $U_1,\dots U_m,V_1,\dots ,V_n$, עבורם: $$⟨u_i,v_j{⟩}_H=\mathbb{𝔼}[U_i{V}_j],\mathbb{𝔼}[{\left|U_i\right|}^p]\le C,\mathbb{𝔼}[{\left|V_j\right|}^p]\le C$$

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

$p$

וב-

$C$

.

הערה: למעשה, התנאי הנוסף על השיכון שלנו הוא קיומו של קבוע

$2<p<\mathrm{\infty }$

כך שהמומנט ה-

$p$

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

הוכחה

יהיו מטריצה ממשית $m\times n$, $A=(a_{ij})$, מרחב הילברט $H$ ווקטורים $u_1,\dots ,u_m,v_1,\dots ,v_n$ בכדור היחידה של $H$. כדי לנצל את ההנחה בנוגע למומנט החסום, נרצה לחלק את השיכונים שלנו ל"גבעות" ול"זנבות". נגדיר עבור $F\in L^p(\mu )$ (כאשר $F$ מייצג $U_i$ או $V_j$): $$F^M(\omega ):=\{\begin{array}{ll}F(\omega )& |F(\omega )|>M\\ 0& |F(\omega )|\le M\end{array},F_M(\omega ):=\{\begin{array}{ll}0& |F(\omega )|>M\\ F(\omega )& |F(\omega )|\le M\end{array},$$ מההנחה בנוגע למומנט, נצפה שהגבעות יהפכו זניחות כשנגדיל את $M$. אכן: $$\Vert F^M\underset{L^2(\mu )}{\overset{2}{\Vert }}\le \underset{|F|>M}{\int }|F{|}^p{M}^{2-p}d\mu \le M^{2-p}\int |F{|}^{p}d\mu =M^{2-p}\cdot C$$כמו כן ממונוטוניות נורמות $L^p$, גם המומנט השני חסום, ובפרט נורמת ה"זנבות" חסומה. כלומר, קיים קבוע $C^{\prime }$ עבורו: $$\Vert F_M{\Vert }_{L^2(\mu )},\Vert F{\Vert }_{L^2(\mu )}\le C^{\prime }$$בפרט נוכל לבחור $C^{\prime }=C^{1/p}$. בעזרת החסמים המתוארים, נפעל לחסום את הביטוי בצידו השמאלי של א"ש גרותנדיק: $$|\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}⟨u_i,v_j{⟩}_H|=\left|\mathbb{𝔼}\left[\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{U}_i{V}_j\right]\right|.$$ לשם כך נפצל את המכפלה $U_i{V}_j$ לשלושה חלקים:$$U_i{V}_j=(U_i{)}_M(V_j{)}_M+(U_i{)}^M(V_j{)}_M+(U_i)(V_j{)}^M,$$ונחסום כל חלק בנפרד. ראשית:$$\left|\mathbb{𝔼}[\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}(U_i{)}_M(V_j{)}_M]\right|\le M^2\cdot \Vert A{\Vert }_{\mathrm{\infty }\to 1}$$בנוסף לפי הגדרת $\Vert A{\Vert }_G$ (ראה פורמולציה באמצעות הנורמה של אופרטור), לאור ההבחנה ש-$L^2(\mu )$ הוא מרחב הילברט:$$\begin{array}{rl}\left|\mathbb{𝔼}[\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}(U_i{)}^M(V_j{)}_M]\right|& \le \underset{i}{\max }\Vert (U_i{)}^M{\Vert }_{L^2(\mu )}\cdot \underset{j}{\max }\Vert (V_j{)}_M{\Vert }_{L^2(\mu )}\cdot \Vert A{\Vert }_G\\ & \le M^{1-p/2}\cdot C^{1/2}\cdot C^{\prime }\cdot \Vert A{\Vert }_G\end{array}$$באופן דומה, $$\left|\mathbb{𝔼}[\sum _{i,j}{a}_{ij}(U_i)(V_j{)}^M]\right|\le M^{1-p/2}\cdot C^{1/2}\cdot C^{\prime }\cdot \Vert A{\Vert }_G$$ביחד: $$|\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}⟨u_i,v_j{⟩}_H|\le M^2\Vert A{\Vert }_{\mathrm{\infty }\to 1}+2M^{1-p/2}\cdot C^{1/2}\cdot C^{\prime }\cdot \Vert A{\Vert }_G$$. נשים לב כי צד ימין אינו תלוי בבחירת המרחב $H$ ולכן על ידי לקיחת סופרימום על פני כל מרחבי הילברט (כמתואר בהגדרה של $\Vert A{\Vert }_G$):$$\Vert A{\Vert }_G\le M^2\Vert A{\Vert }_{\mathrm{\infty }\to 1}+\frac{2C^{1/2}\cdot C^{\prime }}{M^{p/2-1}}\cdot \Vert A{\Vert }_G$$ מאחר ש-$p>2$, ניתן לבחור $M>(2C^{1/2}\cdot C^{\prime }{)}^{\frac{2}{p-2}}$, להעביר אגפים ולקבל חסם עליון: $$\Vert A{\Vert }_G\le \underset{K_M(p,C,C^{\prime })}{\underbrace{\frac{M^2}{1-2C^{1/2}\cdot C^{\prime }\cdot M^{1-p/2}}}}\Vert A{\Vert }_{\mathrm{\infty }\to 1}$$מינימזציה של ביטוי זה ב-$M$ (בטווח המותר) מובילה לקבוע: $$K(p,C,C^{\prime }):=\underset{M}{\min }{K}_M(p,C,C^{\prime })=\frac{2\cdot {[C^{1/2}\cdot C\cdot {(1+\frac{p}{2})}^{\frac{p+2}{4}}]}^{\frac{4}{p-2}}}{p-2}$$∎

הוכחת קיום התנאי המספק

איך ניתן למצוא שיכון שכזה? דוגמה אחת לבסיס מתאים היא מערכת ראדמאכר - סדרה $r_n(\omega )$ של משתנים מקריים בלתי תלויים שלוקחים את הערכים $\pm 1$ בהסתברות $\frac{1}{2}$ כל אחד: $$r_n(\omega ):=\text{sgn}(\sin (2^n\pi \omega )),n=1,2,\dots ,\omega \in [0,1]$$

מערכת זו אורתונורמלית ב-

$L^2([0,1])$

. בהתאם לכך נבנה את השיכון:

$$u_i=\sum _n⟨u_i,e_n{⟩}_H\cdot e_n⟼U_i=\sum _n⟨u_i,e_n{⟩}_H\cdot r_n$$

ובאותו האופן עבור

$v_j\mapsto V_j$

. נותר להוכיח את החסם על המומנט ה-

$p$

, כאשר נזכור

$\sum _n{|⟨u_{i,}{e}_n⟩|}^2=\Vert u_i{\Vert }_H\le 1$

:

טענה: חסם אחיד על המומנט הרביעי של מערכת ראדמאכר: עבור

$X(\omega )=\sum _n{a}_n{r}_n(\omega )$

כאשר

$\sum _n{a}_n^2\le 1$

, מתקיים:

$$\mathbb{𝔼}\left[{\left|X\right|}^4\right]\le 3$$

הוכחה

מליניאריות התוחלת:$$\mathbb{𝔼}\left[{\left|X\right|}^4\right]=\mathbb{𝔼}\left[{\left(\sum _n{a}_n{r}_n\right)}^4\right]=\sum _{k,l,s,t}{a}_k{a}_l{a}_s{a}_t\mathbb{𝔼}[r_k{r}_l{r}_s{r}_t]$$ היות שאיברי מערכת ראדמאכר בלתי-תלויים, התוחלת $\mathbb{𝔼}[r_k{r}_l{r}_s{r}_t]$ אינה אפס רק אם כל אינדקס מופיע מספר זוגי של פעמים. לכן:$$\begin{array}{rl}{\Vert \sum a_n{r}_n\Vert }_{L^4([0,1])}^4& =\sum _i[a_i^2(\sum _k{a}_k^2+\sum _l{a}_l^2+\sum _j{a}_j^2)-2a_i^4]\le 3\cdot {\left(\sum _n{\left|a_n\right|}^2\right)}^2\le 3\end{array}$$∎

אם כן, מערכת ראדמאכר מהווה בסיס מתאים לשיכון שחיפשנו, וקיומה מוכיח את אי שוויון גרותנדיק! מהו הקבוע שקיבלנו? היות ש-$\Vert r_n{\Vert }_{L^2([0,1])}=1$, מההוכחה שלנו מעלה נובע (עם $p=4$, $C=3$, $C^{\prime }=1$):$$K_G^{\mathbb{ℝ}}\le 81,$$בעוד שידוע $1.67696\lesssim K_G^{\mathbb{ℝ}}\lesssim 1.78221$. למעשה, ניתן להגיע לחסם של קריבין בדרך דומה אך עם שיכון מתוחכם יותר.

יישומים

אומדן נורמת החיתוך (Cut Norm)

בהינתן מטריצה ממשית $A=(a_{ij})$ בגודל $m\times n$, נורמת החיתוך שלה מוגדרת על ידי: $$\Vert A{\Vert }_{◻}:=\underset{S\subseteq \{1,\dots ,m\},T\subseteq \{1,\dots ,n\}}{\max }\left|\sum _{i\in S,j\in T}{a}_{ij}\right|.$$ נורמת החיתוך קשורה לבעיית חתך מרבי (Max-Cut) בגרפים ומופיעה באלגוריתמי קירוב. אי-שוויון גרותנדיק מספק קשר בין נורמת החיתוך, $\Vert A{\Vert }_{\mathrm{\infty }\to 1}$ ו-$\Vert A{\Vert }_G$. ידוע כי: $$\Vert A{\Vert }_{◻}\le \Vert A{\Vert }_{\mathrm{\infty }\to 1}\le C_0\cdot \Vert A{\Vert }_{◻}$$ עבור קבוע אוניברסלי $C_0$ (למשל, $C_0=4$ עבור מטריצות כלליות). מאי-שוויון גרותנדיק אנו יודעים (ראה פורמולציה באמצעות הנורמה של אופרטור): $$\Vert A{\Vert }_{\mathrm{\infty }\to 1}\le \Vert A{\Vert }_G\le K_G^{\mathbb{ℝ}}\cdot \Vert A{\Vert }_{\mathrm{\infty }\to 1}$$ שילוב אי-שוויונות אלו מראה שניתן לקרב את $\Vert A{\Vert }_G$ באמצעות $\Vert A{\Vert }_{\mathrm{\infty }\to 1}$, ואת $\Vert A{\Vert }_{\mathrm{\infty }\to 1}$ באמצעות $\Vert A{\Vert }_{◻}$: $$\frac{1}{C_0\cdot K_G^{\mathbb{ℝ}}}\Vert A{\Vert }_G\le \Vert A{\Vert }_{◻}\le \Vert A{\Vert }_G$$ בעוד שחישוב מדויק של $\Vert A{\Vert }_{◻}$ (או $\Vert A{\Vert }_{\mathrm{\infty }\to 1}$) הוא בעיה NP-קשה, ניתן לחשב את $\Vert A{\Vert }_G$ (או לקרב אותו) ביעילות עד לכל דיוק $\epsilon >0$ באמצעות תכנות SDP בזמן פולינומי בגודל המטריצה וב-$1/\epsilon$. לכן, אי-שוויון גרותנדיק מאפשר לקרב את נורמת החיתוך עד כדי פקטור $K_G^{\mathbb{ℝ}}$ (או $C_0\cdot K_G^{\mathbb{ℝ}}$).

למת הרגולריות של סמרדי

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

מתברר כי “צוואר-הבקבוק” העיקרי בבניית חלוקה רגולרית של סמרדי בזמן פולינומי הוא לקבוע, גם כן בזמן פולינומי, האם זוג נתון $(X,Y)$ של קבוצות קודקודים זרות קרוב להיות $\epsilon$-רגולרי. כלומר, שלכל $S\subset X,T\subset Y$ המקיימות $|S|\ge \epsilon |X|,|T|\ge \epsilon |Y|$ מתקיים:

$$|\frac{e(S,T)}{|S||T|}-\frac{e(X,Y)}{|X||Y|}|\le \epsilon ,$$

כאשר $e(S,T)$ הוא מספר הקשתות בין הקבוצות $S,T$ ובאותו האופן עבור $X,Y$. ניתן להראות שעבור מטריצה $A{\text{'}}_{XY}$ מתאימה, אם $\Vert A{\text{'}}_{XY}{\Vert }_{◻}<{\epsilon }^3|X||Y|$, הזוג $(X,Y)$ הוא $\epsilon$-רגולרי. כאמור, ניתן לקרב את נורמת החיתוך באמצעות $\Vert A{\text{'}}_{XY}{\Vert }_G$ ואי-שוויון גרותנדיק.

חסם צירלסון

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

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

קבוע גרותנדיק מסדר d

קבוע גרותנדיק מסדר $d$ (עבור מרחבי הילברט ממשיים), המסומן $K_G(d)$, הוא הקבוע $K$ המינימלי כך שלכל מטריצה ממשית $A=(a_{ij})$ בגודל $m\times n$, ולכל שני סטים של וקטורים $u_1,\dots ,u_m\in {\mathbb{ℝ}}^d$ ו-$v_1,\dots ,v_n\in {\mathbb{ℝ}}^d$ המקיימים $\Vert u_i{\Vert }_2\le 1$ ו-$\Vert v_j{\Vert }_2\le 1$, מתקיים: $$|\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}⟨u_i,v_j⟩|\le K\cdot \underset{|p_i|\le 1,|q_j|\le 1}{\sup }\left|\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{p}_i{q}_j\right|$$ במילים אחרות, $K_G(d)$ הוא קבוע גרותנדיק כאשר מרחב הילברט $H$ מוגבל להיות ${\mathbb{ℝ}}^d$ (או כל מרחב הילברט ממשי מממד $d$ לכל היותר). הסדרה $(K_G(d){)}_{d=1}^{\mathrm{\infty }}$ היא סדרה לא יורדת של קבועים. הקבוע $K_G^{\mathbb{ℝ}}$ שהוגדר קודם הוא למעשה:$$\underset{d\ge 1}{\sup }{K}_G(d)=\underset{d\to \mathrm{\infty }}{\lim }{K}_G(d)$$באופן אינטואיטיבי, $K_G(d)$ מודד עד כמה ניתן "להפר" את הגרסה הסקלרית של הביטוי כאשר הווקטורים $u_i,v_j$ חיים במרחב מממד $d$. לקבועים אלה יש יישומים חשובים, למשל בפיזיקה קוונטית בהקשרים של אי-שוויוני בל וחסם צירלסון (על שם המתמטיקאי בוריס צירלסון), ובאופטימיזציה.

לאורך השנים פותחו חסמים שונים על קבועי גרותנדיק אלו:

גבולות תחתונים עבור $K_G(d)$ (ממשי)
d	Grothendieck, 1953	Krivine, 1979	Davie, 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., 2023	Designolle et al., 2024
2		$\sqrt{2}$ ≈ 1.41421
3					1.41724		1.41758	1.4359	1.43665	1.43670
4					1.44521		1.44566	1.4821		1.48579
5				$\frac{10}{7}$ ≈ 1.42857	1.46007		1.46112			1.49339
6							1.47017
7						1.46286	1.47583
8						1.47586	1.47972
9						1.48608
10						1.49431
∞	$\frac{\pi }{2}$ ≈ 1.57079		1.67696

גבולות עליונים עבור $K_G(d)$ (ממשי)
d	Grothendieck, 1953	Rietz, 1974	Krivine, 1979	Braverman et al., 2011	Hirsch et al., 2016	Designolle et al., 2023
2			$\sqrt{2}$ ≈ 1.41421
3			1.5163		1.4644	1.4546
4			$\frac{\pi }{2}$ ≈ 1.5708
8			1.6641
∞	$\sinh \frac{\pi }{2}$ ≈ 2.30130	2.261	$\frac{\pi }{2\ln (1+\sqrt{2})}$ ≈ 1.78221	$\frac{\pi }{2\ln (1+\sqrt{2})}-\epsilon$

קבוע גרותנדיק של גרף

בהשראת אי-שוויון גרותנדיק, הוגדר קבוע גרותנדיק של גרף סופי $G=(V,E)$ כקבוע $K(G)$ המינימלי כך שלכל פונקציית משקולות על הקשתות $a:E\to \mathbb{ℝ}$ מתקיים: $$\underset{f:V\to S({\ell }_2)}{\sup }\sum _{\{u,v\}\in E}a(u,v)⟨f(u),f(v){⟩}_{{\ell }_2}\le K(G)\cdot \underset{f:V\to \{-1,1\}}{\sup }\sum _{\{u,v\}\in E}a(u,v)f(u)f(v),$$ כאשר $S({\ell }_2)$ היא ספירת היחידה של ${\ell }_2$. נסמן ב-$K(G)$ את הקבוע המינימלי הזה. נבחן, למשל, את הגרף דו-צדדי המלא $K_{n,n}$. במקרה זה מתקבל: $$K(K_{n,n})=K_G^{\mathbb{ℝ}}(n),\underset{n\ge 1}{\sup }K(K_{n,n})=K_G^{\mathbb{ℝ}}.$$ אם $G^{\prime }=(V^{\prime },E^{\prime })$ הוא תת-גרף מושרה של $G$, אזי $K(G^{\prime })\le K(G)$. לכן, לכל גרף דו-צדדי $G$ מתקיים $K(G)\le K_G^{\mathbb{ℝ}}$. ואולם, עבור גרפים כלליים הקבוע אינו נשאר חסום. למעשה, ידוע כי קיים קבוע מוחלט $C>0$ כך שלכל גרף $G=(V,E)$ (ללא לולאות עצמיות) מתקיים: $$K(G)\le C\cdot \log (|V|+1),$$ חסם זה הוא הדוק אסימפטוטית.

לקריאה נוספת

• Joe Diestel, Jan H. Fourie, Johan Swart, The Metric Theory of Tensor Products: Grothendieck’s Résumé Revisited, American Mathematical Society, 2008

קישורים חיצוניים

• אי-שוויון גרותנדיק, באתר MathWorld (באנגלית)

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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