Nierówność Grothendiecka

W matematyce nierówność Grothendiecka stwierdza $,$ istnieje stała uniwersalna następującej właściwości. Jeśli M _ij jest macierzą n × n ( rzeczywistą lub zespoloną ) z

{\ Displaystyle {\ duży |} \ suma _ {i, j} M_ {ij} s_ {i} t_ {j} {\ duży |} \ równoważnik 1}

więc dla wszystkich (rzeczywistych lub zespolonych) liczb _{s i t j} o _wartości bezwzględnej co najwyżej 1

{\ Displaystyle {\ duży |} \ suma _ {i, j} M_ {ij} \ langle S_ {i}, T_ {j} \ rangle {\ duży |} \ równoważnik K_ {G}}

$Hilberta$ wszystkich wektorów S _ja , T _j w kuli jednostkowej B ( H ) (rzeczywistej lub zespolonej) H , stała jest niezależna od n . Dla ustalonej przestrzeni Hilberta o wymiarze d , najmniejsza stała spełniająca tę właściwość dla wszystkich macierzy n × n nazywana jest stałą Grothendiecka i oznaczana ${\ Displaystyle K_ {G} (d)}$ . W rzeczywistości istnieją dwie stałe Grothendiecka, $\ Displaystyle K_ {G} ^ {\ mathbb {R}} (d)}$ i ${\ Displaystyle K_ {G} ^ { \mathbb {C} }(d)}$ , w zależności od tego, czy pracuje się odpowiednio z liczbami rzeczywistymi, czy zespolonymi.

Nierówność Grothendiecka i stałe Grothendiecka zostały nazwane na cześć Aleksandra Grothendiecka , który udowodnił istnienie stałych w artykule opublikowanym w 1953 roku.

Motywacja i sformułowanie operatorowe

Niech $ij}}}$ ${ \ Displaystyle A = ($ { będzie Następnie ${\ Displaystyle A}$ definiuje operator liniowy między przestrzeniami znormalizowanymi ${\ Displaystyle (\ mathbb {R} ^ {m}, \|\ cdot \|_ {p})}$ i ${\ Displaystyle (\ mathbb {R} ^ {n}, \ | \ cdot \|_ {q})}$ dla ${\ Displaystyle 1 \ równoważnik p, q \ równoważnik \ infty}$ . ${\ Displaystyle (p \ do q)}$ A $}$ ZA { \ Displaystyle jest ilość

${\ Displaystyle \| A \ | _ {p \ do q} = \ max _ {x \ w \ mathbb {R} ^ {n}: \ | x \ | _ {p} = 1} \| Ax \ | _{Q}.}$

Jeśli ${\ displaystyle p = q}$ , oznaczamy normę przez ${\ Displaystyle \|A \|_ {p}}$ .

$_$ $rozważyć$ następujące $zmaksymalizowane$ i jest _ Ponieważ $\$ liniowy, wystarczy rozważyć takie, że $displaystyle p}$ ${\ Displaystyle \ {x \ in \ mathbb {R} ^ {n}: \ | x \ | _ {p} \ równoważnik 1 \}} zawiera jak najwięcej punktów, a także takie, że q {$ \ displaystyle $}$ $to$ możliwe. Porównując ${\ Displaystyle \|x \|_ {p}}$ dla ${\ Displaystyle p = 1,2, \ ldots, \ infty}$ , widać, że ${\ Displaystyle \|A \|_ {\ infty \ do 1} \ geq \|A \|_ {p \ do q}}$ dla wszystkich ${ \ Displaystyle 1 \ równoważnik p, q \ równoważnik \ infty}$ .

$_$ obliczania rozwiązanie następującego programu

${\ Displaystyle {\ rozpocząć {wyrównane} \ max & \ qquad \ suma _ {i, j} A_ {ij} x_ {i} y_ {j} \ \{\text{st}}&\qquad (x,y)\in \{-1,1\}^{m+n}\end{wyrównane}}}$

Aby to zobaczyć, zauważ, że $x_ {i} y_ {j} =\ suma _ {i} (Ay) _ {i} x_ {i}}$ i biorąc maksimum ponad $}}$ ${\ Displaystyle x \ in \ {- 1,1 \} ^ {$ daje ${\ Displaystyle \| Tak \ | _ {1}}$ . Następnie biorąc maksimum ponad ${\ Displaystyle y \ w \ {-1,1 \} ^ {n}}$ daje ${\ Displaystyle \|A \|_ { \ infty \ do 1}}$ przez wypukłość ${\ Displaystyle \ {x \ in \ mathbb {R} ^ {m}: \ | x \ | _ {\ infty }=1\}}$ i przez nierówność trójkąta. Ten kwadratowy program liczb całkowitych można złagodzić do następującego programu półokreślonego :

${\ Displaystyle {\ rozpocząć {wyrównane} \ max & \ qquad \ suma _ {i, j} A_ {ij} \ langle x ^ {(i)}, y ^ {(j)} \ rangle \\ { \text{st}}&\qquad x^{(1)},\ldots,x^{(m)},y^{(1)},\ldots,y^{(n)}{\text{ są wektorami jednostkowymi w }}(\mathbb {R} ^{d},\|\cdot \|_{2})\end{aligned}}}$

Wiadomo, że dokładnie ‖ ZA $Displaystyle \|A \|_ {p \ do q}}$ dla ${\ Displaystyle 1 \ równoważnik q <p \ równoważnik \ infty}$ jest NP-trudne podczas gdy $NP$ - trudne dla ${\ Displaystyle p \ nie \ w \ {1,2, \ infty \}}$ .

Można zatem zadać następujące naturalne pytanie: Jak dobrze przybliżone jest optymalne rozwiązanie programu półokreślonego ‖ $\ Displaystyle \|A \|_ {\ infty \ do 1}}$ ? Nierówność Grothendiecka dostarcza odpowiedzi na $m, n \ geq$ ${\ displaystyle m \ razy n}$ istnieje stała stała $displaystyle$ , że dla dowolnego macierz i dla dowolnej przestrzeni Hilberta H. $}$ $H$

${\ Displaystyle \ max _ {x ^ {(i)}, y ^ {(i)} \ w H {\ tekst {wektory jednostkowe}}} \ suma _ {i, j} A_ {ij} \ lewo \ langle x^{(i)},y^{(j)}\right\rangle _{H}\równoważnik C\|A\|_{\infty \to 1}.}$

Granice na stałych

Sekwencje $\ Displaystyle K_ {G} ^ {\ mathbb {R}} (d)}$ i ${\ Displaystyle K_ {G} ^ {\ mathbb {C}} ( d)}$ łatwo zauważyć, że rosną, a wynik Grothendiecka stwierdza, że są one ograniczone , więc mają granice .

Grothendieck udowodnił, że ${\ Displaystyle 1,57 \ około {\ Frac {\ pi} {2}} \ równoważnik K_ {G} ^ {\ mathbb {R}} \ leq \ nazwa operatora {sinh} {\ Frac {\ pi} {2}} \ około 2,3,}$ gdzie ${\ Displaystyle K_ {G} ^ {\ mathbb {R}}}$ jest zdefiniowany jako ${\ Displaystyle \ sup _ {d} K_ {G} ^ {\ mathbb {R}} (d)}$ .

Krivine (1979) poprawił wynik, udowadniając, że ${\ Displaystyle K_ {G} ^ {\ mathbb {R}} \ równoważnik {\ Frac {\ pi}} 2\ln(1+{\sqrt {2}})}}\około 1,7822}$ , przypuszczając, że górna granica jest wąska. Jednak to przypuszczenie zostało obalone przez Bravermana i in. (2011) .

Stała rzędu Grothendiecka d

Boris Tsirelson wykazał $,$ że stałe Grothendiecka istotną w problemie : granica Tsirelsona pełnej dwudzielna nierówność Bella dla układu kwantowego o wymiarze d jest ograniczona w górę przez ${\ Displaystyle K_ {G} ^ {\ mathbb {R}} (2d ^ {2})}$ .

Dolne granice

$.$ podsumowano dotyczące najlepiej znanych

D	Grothendieck, 1953	Krzywin, 1979	Dawid, 1984	Fishburn i in., 1994	Vertesi, 2008	Briët i in., 2011	Hua i in., 2015	Diviánszky i in., 2017	Designolle i in., 2023
2		${\ Displaystyle {\ sqrt {2}}}$ ≈ 1,41421
3					1.41724		1.41758	1.4359	1.4376
4					1.44521		1.44566	1.4841
5				${\ Displaystyle {\ Frac {10} {7}}}$ ≈ 1,42857	1.46007		1.46112
6							1.47017
7						1.46286	1.47583
8						1.47586	1,47972
9						1.48608
∞	${\ Displaystyle {\ Frac {\ pi} {2}}}$ ≈ 1,57079		1,67696

Górne granice

Niektóre dane historyczne dotyczące najlepiej znanych górnych granic ${\ Displaystyle K_ {G} ^ {\ mathbb {R}} (d)$ :

D	Grothendieck, 1953	Rietz, 1974	Krzywin, 1979	Braverman i in., 2011	Hirsch i in., 2016	Designolle i in., 2023
2			${\ Displaystyle {\ sqrt {2}}}$ ≈ 1,41421
3			1,5163		1.4644	1.4546
4			${\ Displaystyle {\ Frac {\ pi} {2}}}$ ≈ 1,5708
8			1.6641
∞	${\ Displaystyle \ nazwa operatora {sinh} {\ Frac {\ pi} {2}}}$ ≈ 2,30130	2.261	${\ Displaystyle {\ Frac {\ pi} {2 \ ln (1 + {\ sqrt {2}})}}}$ ≈ 1,78221	${\ Displaystyle {\ Frac {\ pi} {2 \ ln (1 + {\ sqrt {2}})}} - \ varepsilon}$

Aplikacje

Oszacowanie normy cięcia

Za ${\ Displaystyle m \ razy n}$ macierz rzeczywista ${\ Displaystyle A = (a_ {ij})}$ , norma cięcia z jest definiowana przez ${\ Displaystyle A}$

{\ Displaystyle \|A \|_ {\ kwadrat} = \ max _ {S \ podzbiór [m], T \ podzbiór [n]} \ lewo | \ suma _ {i \ w S, j \ w T} a_ {ij}\prawo|.}

Pojęcie normy cięcia jest niezbędne przy projektowaniu wydajnych algorytmów aproksymacji gęstych grafów i macierzy. Mówiąc bardziej ogólnie, definicję normy cięcia można uogólnić dla symetrycznych mierzalnych funkcji ${\ Displaystyle W: [0,1] ^ {2} \ do \ mathbb {R}},$ tak że cięcie norma jest zdefiniowana przez W $\ displaystyle W}$

{\ Displaystyle \|W \|_ {\ kwadrat} = \ sup _ {S, T \ podzbiór [0,1]} \ lewo | \ int _ {S \ razy T} W \ prawo |.}

Ta uogólniona definicja normy cięcia jest kluczowa w badaniu przestrzeni grafonów , a te dwie definicje normy cięcia można połączyć za pomocą macierzy sąsiedztwa grafu .

Zastosowanie nierówności Grothendiecka polega na podaniu wydajnego algorytmu aproksymacji normy cięcia danej rzeczywistej macierzy ${\ displaystyle A}$ ; konkretnie, biorąc pod uwagę $rzeczywistą macierz$ , można znaleźć taką liczbę, $\ displaystyle \ alpha}$ m

${\ Displaystyle \|A \|_ {\ kwadrat} \ równoważnik \ alfa \ równoważnik C \ | A \ | _ {\ kwadrat},}$

gdzie jest $stałą$ . Ten algorytm aproksymacji wykorzystuje programowanie półokreślone .

Podajemy szkic tego algorytmu aproksymacji. Niech ${\ Displaystyle B = (b_ {ij})}$ być ${\ Displaystyle (m + 1) \ razy (n + 1)}$ zdefiniowana macierz przez

${\ Displaystyle {\ rozpocząć {pmatrix} a_ {11}& a_ {12} & \ ldots & a_ {1n} & - \ suma _ {k = 1} ^ {n} a_ {1k} \\ a_ {21} i a_ { 22}&\ldots &a_{2n}&-\sum _{k=1}^{n}a_{2k}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_ {m2}&\ldots &a_{mn}&-\suma _{k=1}^{n}a_{mk}\\-\suma _{\ell =1}^{m}a_{\ell 1} &-\sum _{\ell =1}^{m}a_{\ell 2}&\ldots &-\sum _{\ell =1}^{m}a_{\ell n}&\sum _{ k=1}^{n}\suma _{\ell =1}^{m}a_{\ell k}\end{pmacierz}}.}$

Można ${\ Displaystyle S \ w [m + 1], T \ w [n + 1]}$ $_$ obserwując tworzą maksymalizator dla normy cięcia ${\ Displaystyle B}$ , a następnie

${\ Displaystyle S ^ {*} = {\ rozpocząć {przypadki} S, & {\ tekst {jeśli}} m + 1 \ nie \ w S, \\ {[m]} \ setminus S, & {\ tekst { inaczej}},\end{przypadków}}\qquad T^{*}={\begin{przypadków}T,&{\text{if }}n+1\not \in T,\\{[n]} \setminus S,&{\text{inaczej}},\end{przypadki}}\qquad }$

tworzą maksymalizator dla normy cięcia ${\ displaystyle A}$ . Następnie można sprawdzić, że ${\ Displaystyle \|B \|_ {\ kwadrat} = \| B \|_ {\ infty \ do 1}/4$ } Gdzie

${\ Displaystyle \|B \|_ {\ infty \ do 1} = \ max \ lewo \ {\ suma _ {i = 1} ^ {m + 1} \ suma _ {j = 1} ^ {n + 1 }b_{ij}\varepsilon _{i}\delta _{j}:\varepsilon _{1},\ldots,\varepsilon _{m+1}\in \{-1,1\},\delta _ {1},\ldots ,\delta _{n+1}\in \{-1,1\}\right\}.}$

Chociaż nie jest to ważne w tym dowodzie, można interpretować jako normę $1}}$ $Displaystyle \|$ do od ${\ Displaystyle \ ell _ {\ infty} ^ {m}}$ do ${\ Displaystyle \ ell _ {1} ^ {m}}$ .

Teraz wystarczy zaprojektować wydajny algorytm aproksymacji ${\ Displaystyle \|A \|_ {\ infty \ do 1}$ } Rozważamy następujący program półokreślony :

${\ Displaystyle {\ tekst {SDP}} (A) = \ max \ lewo \ {\ suma _ {i = 1} ^ {m} \ suma _ {j = 1} ^ {n} a_ {ij} \ lewo \langle x_{i},y_{j}\right\rangle :x_{1},\ldots,x_{m},y_{1},\ldots,y_{n}\in S^{n+m- 1}\prawo\}.}$

Następnie ${\ Displaystyle {\ tekst {SDP}} (A) \ geq \|A \|_ {\ infty \ do 1}}$ . Nierówność Grothediecka oznacza, że $\ Displaystyle {\ tekst {SDP}} (A) \ równoważnik K_ {G} ^ {\ mathbb {R}} \ | A \ |_{\infty \do 1}}$ . Wiele algorytmów (takich jak metody punktów wewnętrznych , metody pierwszego rzędu, metoda wiązek, metoda rozszerzona metoda Lagrange'a ) są znane z wyprowadzania wartości półokreślonego programu aż do błędu addytywnego $czasie,$ który jest wielomianem w opisie programu rozmiar i ${\ Displaystyle \ log ( 1/\varepsilon )}$ . Dlatego można wyprowadzić, co spełnia ${\ Displaystyle \ alpha = {\ tekst {SDP}} (B)}$

${\ Displaystyle \|A \|_ {\ kwadrat} \ równoważnik \ alfa \ równoważnik C \|A \|_ {\ kwadrat} \ qquad {\ tekst {z}} \ qquad C = K_ {G} ^ {\ matematykabb {R} }.}$

Lemat Szemerédiego o regularności

Lemat Szemerédiego o regularności jest użytecznym narzędziem w teorii grafów, stwierdzając (nieformalnie), że dowolny wykres można podzielić na kontrolowaną liczbę elementów, które oddziałują na siebie w pseudolosowy sposób . Innym zastosowaniem nierówności Grothendiecka jest utworzenie podziału zbioru wierzchołków, który spełnia wniosek lematu Szemerédiego o regularności , za pomocą algorytmu estymacji normy cięcia, w czasie, który jest wielomianem w górnej granicy regularnego rozmiaru podziału Szemerédiego, ale niezależny od liczby wierzchołków w grafie.

$} \ displaystyle \ varepsilon }$ -regularny wąskim gardłem” konstruowania regularnego podziału Szemerediego w czasie wielomianowym jest określenie w czasie wielomianowym, czy dana para jest bliska bycia ${\ Displaystyle (X, Y)$ , co oznacza, że dla wszystkich ${\ Displaystyle S \ podzbiór X, T \ podzbiór Y}$ z ${\ Displaystyle | S | \ geq \ varepsilon | X |, | T | \ geq \ varepsilon | Y |}$ mamy

${\ Displaystyle \ lewo | {\ Frac {e (S, T)}} {| S || T |}} - {\ Frac {e (X, Y)} {| X|| Y|}} \right|\leq \varepsilon ,}$

gdzie ${\ Displaystyle e (X', Y') = |\ {(u, v) \ w X'\ razy Y': uv \ w E \} |} dla wszystkich X ′$ , $X ',Y'\podzbiór V}$ i ${\ Displaystyle V, E}$ to odpowiednio zestawy wierzchołków i krawędzi wykresu. W tym celu konstruujemy $macierz$ $(x ,y)\in X\times Y}}$ { , gdzie ${\ displaystyle n = | V|}$ , zdefiniowany przez

${\ Displaystyle a_ {xy} = {\ rozpocząć {przypadki} 1 - {\ Frac {e (X, Y)}} {| X | | Y|}}, & {\ tekst {jeśli}} xy \ w E, \\-{\frac {e(X,Y)}{|X||Y|}},&{\text{inaczej}}.\end{przypadki}}}$

Następnie dla wszystkich ${\ Displaystyle S \ podzbiór X, T \ podzbiór Y}$ ,

${\ Displaystyle \ lewo | \ suma _ {x \ w S, y \ w T} a_ {xy} \ prawo | = | S | | T | \ lewo | {\ Frac {e (S, T)}} {| S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\prawo|.}$

Stąd, jeśli nie jest $kwadrat }\geq \varepsilon ^{3}n^{2}}$ , to $≥$ $Displaystyle \$ $A$ . Wynika z tego, że stosując algorytm aproksymacji normy cięcia wraz z techniką zaokrąglania, można znaleźć w czasie wielomianowym ${\ Displaystyle S \ podzbiór X, T \ podzbiór Y}$ takie że

${\ Displaystyle \ min \ lewo \ {n | S |, n | T |, n ^ {2} \ lewo | {\ Frac {e (S, T)}} {| S|| T|}} - {\ frac {e(X,Y)}{|X||Y|}}\right|\right\}\geq \left|\sum _{x\in S,y\in T}a_{xy}\right |\geq {\frac {1}{K_{G}^{\mathbb {R}}}}\varepsilon ^{3}n^{2}\geq {\frac {1}{2}}\varepsilon ^ {3}n^{2}.}$

Następnie algorytm tworzenia regularnego podziału Szemerédiego wynika z konstruktywnego argumentu Alona i in.

Warianty nierówności Grothendiecka

Nierówność Grothendiecka wykresu

Grothendiecka na wykresie stwierdza, że dla każdego $sol$ dla każdego wykresu $1, \ ldots, n \}, E)}$ $Displaystyle G = (\$ $n \ razy n}$ pętli własnych, istnieje uniwersalna stała $displaystyle$ , że każda macierz ${\ Displaystyle A = (a_ {ij})}$ spełnia to

${\ Displaystyle \ max _ {x_ {1}, \ ldots, x_ {n} \ w S ^ {n-1}} \ suma _ {ij \ w E} a_ {ij} \ lewo \ langle x_ {i} ,x_{j}\right\rangle \leq K\max _{\varepsilon _{1},\ldots,\varepsilon _{n}\in \{-1,1\}}\sum _{ij\in E}a_{ij}\varepsilon_{1}\varepsilon_{n}.}$

Stała $na$ wykresie , oznaczona $, jest$ najmniejsza stała $,$ spełnia powyższą

Nierówność Grothendiecka wykresu jest rozszerzeniem nierówności Grothendiecka, ponieważ pierwsza nierówność jest szczególnym przypadkiem drugiej nierówności, gdy jest $displaystyle G} \{1,\ldots ,n\}}$ kopiami { \ $}$ jako klasy podziału na partycje. Zatem,

${\ Displaystyle K_ {G} = \ sup _ {n \ w \ mathbb {N}} \ {K (G): G {\ tekst {jest }} n {\ tekst {- wierzchołkowy wykres dwudzielny}} \} .}$

Dla $wierzchołków, nierówność Grothendiecka staje się sol = K$ n { \ $Displaystyle$ $K_ {$

${\ Displaystyle \ max _ {x_ {1}, \ ldots, x_ {n} \ w S ^ {n-1}} \ suma _ {i, j \ w \ {1, \ ldots, n \}, ja \neq j}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq K(K_{n})\max _{\varepsilon _{1},\ldots ,\varepsilon _{n}\in \{-1,1\}}\sum _{i,j\in \{1,\ldots,n\},i\neq j}a_{ij}\varepsilon _{i} \varepsilon _{j}.}$

Okazuje się, że ${\ Displaystyle K (K_ {n}) \ asymp \ log n}$ . Z jednej strony mamy ${\ Displaystyle K (K_ {n}) \ lesssim \ log n}$ . Rzeczywiście, następująca nierówność jest prawdziwa dla dowolnej $Displaystyle A = (a_ {ij}$ ${$ ) , co oznacza, że ${\ Displaystyle K (K_ {n}) \ lesssim \ log n}$ przez nierówność Cauchy'ego-Schwarza :

${\ Displaystyle \ max _ {x_ {1}, \ ldots, x_ {n} \ w S ^ {n-1}} \ suma _ {i, j \ w \ {1, \ ldots, n \}, ja \neq j}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq \log \left({\frac {\sum _{i\in \{1,\ldots , n\}}\sum _{j\in \{1,\ldots ,n\}\setminus \{i\}}|a_{ij}|}{\sqrt {\suma _{i\in \{1 ,\ldots ,n\}}\sum _{j\in \{1,\ldots ,n\}\setminus \{i\}}a_{ij}^{2}}}}\right)\max _ {\varepsilon _{1},\ldots,\varepsilon _{n}\in \{-1,1\}}\sum _{i,j\in \{1,\ldots,n\},i\ neq j}a_{ij}\varepsilon _{1}\varepsilon _{n}.}$

Z drugiej strony pasująca $Makarychev$ granica wynika Alon , .

Nierówność $wykresu$ $.$ _ _ $_$ _ Wiadomo, że

${\ Displaystyle \ log \ omega \ lesssim K (G) \ lesssim \ log \ vartheta,}$

I

${\ Displaystyle K (G) \ równoważnik {\ Frac {\ pi} {2 \ log \ lewo ({\ frac {1+{\sqrt {(\vartheta -1)^{2}+1}}}{\vartheta -1}}\right)}},}$

gdzie ${\ Displaystyle \ omega}$ jest liczbą kliki sol ${\ Displaystyle G}$ tj. największą ${\ Displaystyle k \ in \ {2, \ ldots, n \}}$ takie, że istnieje ${\ Displaystyle S \ podzbiór \ {1 \ ldots, n \}}$ z ${\ displaystyle | S | = k}$ tak, że ${\ Displaystyle ij \ w E}$ wszystkich odrębnych ${\ Displaystyle i, j \ in S}$ i

${\ Displaystyle \ vartheta = \ min \ lewo \ {\ max _ {i \ w \ {1, \ ldots, n \}} {\ Frac {1} {\ langle x_ {i}, y \ rangle}}: x_{1},\ldots,x_{n},y\in S^{n},\left\langle x_{i},x_{j}\right\rangle =0\;\dla wszystkich ij\in E\ Prawidłowy\}.}$

Parametr jest znany jako funkcja theta Lovásza dopełnienia . $displaystyle \$ $vartheta }$ \

Nierówność L^p Grothendiecka

Stosując nierówność Grothendiecka do przybliżenia normy cięcia, widzieliśmy, że nierówność Grothendiecka odpowiada na następujące pytanie: Jak dobrze optymalne rozwiązanie półokreślonego programu SDP ( ZA ) {\ Displaystyle {\ tekst $( A)}$ przybliżony ${\ Displaystyle \|A \|_ {\ infty \ do 1}}$ , co można postrzegać jako problem optymalizacji na sześcianie jednostkowym? Mówiąc bardziej ogólnie, możemy zadać podobne pytania dotyczące ciał wypukłych innych niż sześcian jednostkowy.

Na przykład następująca nierówność wynika z Naora i Schechtmana oraz niezależnie od Guruswamiego i in.: Dla każdej $})}$ ${$ = $Displaystyle A = (a_$ i każdy ${\ Displaystyle p \ geq 2}$ ,

${\ Displaystyle \ max _ {x_ {1}, \ ldots, x_ {n} \ w \ mathbb {R} ^ {n}, \ suma _ {k = 1} ^ {n} \| x_ {k} \ |_{2}^{p}\równik 1}\suma _{i=1}^{n}\suma _{j=1}^{n}a_{ij}\lewo\langle x_{i}, x_{j}\right\rangle \leq \gamma _{p}^{2}\max _{t_{1},\ldots ,t_{n}\in \mathbb {R} ,\suma _{k= 1}^{n}|t_{k}|^{p}\równoważnik 1}\suma _{i=1}^{n}\suma _{j=1}^{n}a_{ij}t_{ i}t_{j},}$