неравенство Гротендика

В математике неравенство Гротендика утверждает , что существует универсальная константа со следующим свойством. Если M _ij — матрица n  ×  n ( действительная или комплексная ) с${\displaystyle K_{G}}$

${\displaystyle {\Big |}\sum _{i,j}M_{ij}s_{i}t_{j}{\Big |}\leq 1}$

для всех (действительных или комплексных) чисел s _i , t _j с абсолютным значением не более 1, то

${\displaystyle {\Big |}\sum _{i,j}M_{ij}\langle S_{i},T_{j}\rangle {\Big |}\leq K_{G}}$

для всех векторов S _i , T _j в единичном шаре B ( H ) (действительного или комплексного) гильбертова пространства H , причем константа не зависит от n . Для фиксированного гильбертова пространства размерности d наименьшая константа, удовлетворяющая этому свойству для всех матриц n  ×  n , называется константой Гротендика и обозначается . Фактически, существует две константы Гротендика, и , в зависимости от того, работаем ли мы с действительными или комплексными числами соответственно. ^[1]${\displaystyle K_{G}}$${\displaystyle K_{G}(d)}$${\displaystyle K_{G}^{\mathbb {R} }(d)}$${\displaystyle K_{G}^{\mathbb {C} }(d)}$

Неравенство Гротендика и константы Гротендика названы в честь Александра Гротендика , который доказал существование констант в статье, опубликованной в 1953 году. ^[2]

Пусть будет матрицей. Тогда определяет линейный оператор между нормированными пространствами и для . -норма есть величина${\displaystyle A=(a_{ij})}$${\displaystyle m\times n}$${\displaystyle А}$${\displaystyle (\mathbb {R} ^{м},\|\cdot \|_{п})}$${\displaystyle (\mathbb {R} ^{n},\|\cdot \|_{q})}$${\displaystyle 1\leq p,q\leq \infty }$${\displaystyle (p\to q)}$${\displaystyle А}$

${\displaystyle \|A\|_{p\to q}=\max _{x\in \mathbb {R} ^{n}:\|x\|_{p}=1}\|Ax\|_{q}.}$

Если , то обозначим норму через .${\displaystyle p=q}$${\displaystyle \|A\|_{p}}$

Можно рассмотреть следующий вопрос: При каком значении и максимизируется ? Поскольку линейно, то достаточно рассмотреть такое, которое содержит как можно больше точек, а также такое, которое как можно больше. Сравнивая для , можно увидеть, что для всех .${\displaystyle p}$${\displaystyle д}$${\displaystyle \|A\|_{p\to q}}$${\displaystyle А}$${\displaystyle p}$${\displaystyle \{x\in \mathbb {R} ^{n}:\|x\|_{p}\leq 1\}}$${\displaystyle д}$${\displaystyle \|Ax\|_{q}}$${\displaystyle \|x\|_{p}}$${\displaystyle p=1,2,\ldots,\infty}$${\displaystyle \|A\|_{\infty \to 1}\geq \|A\|_{p\to q}}$${\displaystyle 1\leq p,q\leq \infty }$

Одним из способов вычисления является решение следующей квадратичной целочисленной программы :${\displaystyle \|A\|_{\infty \to 1}}$

${\displaystyle {\begin{align}\max &\qquad \sum _{i,j}A_{ij}x_{i}y_{j}\\{\text{st}}&\qquad (x,y)\in \{-1,1\}^{m+n}\end{align}}}$

Чтобы увидеть это, обратите внимание, что , и взятие максимума по дает . Тогда взятие максимума по дает по выпуклости и по неравенству треугольника. Эту квадратичную целочисленную программу можно ослабить до следующей полуопределенной программы :${\displaystyle \sum _{i,j}A_{ij}x_{i}y_{j}=\sum _{i}(Ay)_{i}x_{i}}$${\displaystyle x\in \{-1,1\}^{м}}$${\displaystyle \|Ау\|_{1}}$${\displaystyle y\in \{-1,1\}^{n}}$${\displaystyle \|A\|_{\infty \to 1}}$${\displaystyle \{x\in \mathbb {R} ^{m}:\|x\|_{\infty }=1\}}$

${\displaystyle {\begin{aligned}\max &\qquad \sum _{i,j}A_{ij}\langle x^{(i)},y^{(j)}\rangle \\{\text{st}}&\qquad x^{(1)},\ldots ,x^{(m)},y^{(1)},\ldots ,y^{(n)}{\text{ являются единичными векторами в }}(\mathbb {R} ^{d},\|\cdot \|_{2})\end{aligned}}}$

Известно, что точное вычисление для является NP-трудным , в то время как точное вычисление является NP-трудным для .${\displaystyle \|A\|_{p\to q}}$${\displaystyle 1\leq q<p\leq \infty }$${\displaystyle \|A\|_{p}}$${\displaystyle p\not \in \{1,2,\infty \}}$

Тогда можно задать следующий естественный вопрос: Насколько хорошо оптимальное решение полуопределенной программы приближается к ? Неравенство Гротендика дает ответ на этот вопрос: существует фиксированная константа такая, что для любого , для любой матрицы и для любого гильбертова пространства ,${\displaystyle \|A\|_{\infty \to 1}}$${\displaystyle С>0}$${\displaystyle m,n\geq 1}$${\displaystyle m\times n}$${\displaystyle А}$${\displaystyle H}$

${\displaystyle \max _{x^{(i)},y^{(i)}\in H{\text{ единичные векторы}}}\sum _{i,j}A_{ij}\left\langle x^{(i)},y^{(j)}\right\rangle _{H}\leq C\|A\|_{\infty \to 1}.}$

Легко видеть, что последовательности и возрастают, а результат Гротендика утверждает, что они ограничены ^[2] [ ^3], поэтому они имеют пределы .${\displaystyle K_{G}^{\mathbb {R} }(d)}$${\displaystyle K_{G}^{\mathbb {C} }(d)}$

Гротендик доказал, что где определено как . ^[4]${\displaystyle 1.57\approx {\frac {\pi }{2}}\leq K_{G}^{\mathbb {R} }\leq \operatorname {sinh} {\frac {\pi }{2}}\approx 2.3,}$${\displaystyle K_{G}^{\mathbb {R} }}$${\displaystyle \sup _{d}K_{G}^{\mathbb {R} }(d)}$

Кривин (1979) ^[5] улучшил результат, доказав, что , предположив, что верхняя граница узкая. Однако эта гипотеза была опровергнута Браверманом и др. (2011). ^[6]${\displaystyle K_{G}^{\mathbb {R} }\leq {\frac {\pi }{2\ln(1+{\sqrt {2}})}}\approx 1.7822}$

Борис Цирельсон показал, что константы Гротендика играют существенную роль в проблеме квантовой нелокальности : граница Цирельсона любого полного корреляционного двудольного неравенства Белла для квантовой системы размерности d ограничена сверху величиной . ^{[7] [8]}${\displaystyle K_{G}^{\mathbb {R} }(d)}$${\displaystyle K_{G}^{\mathbb {R} }(2d^{2})}$

Некоторые исторические данные о наиболее известных нижних границах приведены в следующей таблице.${\displaystyle K_{G}^{\mathbb {R} }(d)}$

г	Гротендик, 1953 [2]	Кривин, 1979 [5]	Дэви, 1984 [9]	Фишберн и др., 1994 [10]	Вертези, 2008 [11]	Бриет и др., 2011 [12]	Хуа и др., 2015 [13]	Дивиански и др., 2017 [14]	Дизайнолл и др., 2023 [15]
2		${\displaystyle {\sqrt {2}}}$≈ 1,41421
3					1.41724		1.41758	1.4359	1.43665
4					1.44521		1.44566	1.4821
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
10						1.49431
∞	${\displaystyle {\frac {\pi }{2}}}$≈ 1,57079		1.67696

Некоторые исторические данные о наиболее известных верхних границах :${\displaystyle K_{G}^{\mathbb {R} }(d)}$

г	Гротендик, 1953 [2]	Риц, 1974 [16]	Кривин, 1979 [5]	Браверман и др., 2011 [6]	Хирш и др., 2016 [17]	Дизайнолл и др., 2023 [15]
2			${\displaystyle {\sqrt {2}}}$≈ 1,41421
3			1.5163		1.4644	1.4546
4			${\displaystyle {\frac {\pi }{2}}}$≈ 1,5708
8			1.6641
∞	${\displaystyle \operatorname {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 }$

Для вещественной матрицы норма разреза определяется как${\displaystyle m\times n}$${\displaystyle A=(a_{ij})}$${\displaystyle A}$

${\displaystyle \|A\|_{\square }=\max _{S\subset [m],T\subset [n]}\left|\sum _{i\in S,j\in T}a_{ij}\right|.}$

Понятие нормы разреза имеет важное значение при разработке эффективных алгоритмов аппроксимации для плотных графов и матриц. В более общем смысле определение нормы разреза может быть обобщено для симметричных измеримых функций, так что норма разреза определяется как${\displaystyle W:[0,1]^{2}\to \mathbb {R} }$${\displaystyle W}$

${\displaystyle \|W\|_{\square }=\sup _{S,T\subset [0,1]}\left|\int _{S\times T}W\right|.}$

Это обобщенное определение нормы разреза имеет решающее значение при изучении пространства графонов , и два определения нормы разреза могут быть связаны через матрицу смежности графа .

Применение неравенства Гротендика заключается в том, чтобы дать эффективный алгоритм для аппроксимации нормы разреза заданной действительной матрицы ; в частности, если задана действительная матрица, можно найти число такое, что${\displaystyle A}$${\displaystyle m\times n}$${\displaystyle \alpha }$

${\displaystyle \|A\|_{\square }\leq \alpha \leq C\|A\|_{\square },}$

где — абсолютная константа. ^[18] Этот алгоритм приближения использует полуопределенное программирование .${\displaystyle C}$

Приведем набросок этого аппроксимационного алгоритма. Пусть матрица определяется как${\displaystyle B=(b_{ij})}$${\displaystyle (m+1)\times (n+1)}$

${\displaystyle {\begin{pmatrix}a_{11}&a_{12}&\ldots &a_{1n}&-\sum _{k=1}^{n}a_{1k}\\a_{21}&a_{22}&\ldots &a_{2n}&-\sum _{k=1}^{n}a_{2k}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\ldots &a_{mn}&-\sum _{k=1}^{n}a_{mk}\\-\sum _{\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}\sum _{\ell =1}^{m}a_{\ell k}\end{pmatrix}}.}$

Можно проверить это , наблюдая, если сформировать максимизатор для нормы разреза , то${\displaystyle \|A\|_{\square }=\|B\|_{\square }}$${\displaystyle S\in [m+1],T\in [n+1]}$${\displaystyle B}$

${\displaystyle S^{*}={\begin{cases}S,&{\text{if }}m+1\not \in S,\\{[m]}\setminus S,&{\text{otherwise}},\end{cases}}\qquad T^{*}={\begin{cases}T,&{\text{if }}n+1\not \in T,\\{[n]}\setminus S,&{\text{otherwise}},\end{cases}}\qquad }$

образуют максимизатор для нормы разреза . Далее можно проверить, что , где${\displaystyle A}$${\displaystyle \|B\|_{\square }=\|B\|_{\infty \to 1}/4}$

${\displaystyle \|B\|_{\infty \to 1}=\max \left\{\sum _{i=1}^{m+1}\sum _{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\}.}$^[19]

Хотя это и не важно в этом доказательстве, его можно интерпретировать как норму, если рассматривать его как линейный оператор от до .${\displaystyle \|B\|_{\infty \to 1}}$${\displaystyle B}$${\displaystyle \ell _{\infty }^{m}}$${\displaystyle \ell _{1}^{m}}$

Теперь достаточно разработать эффективный алгоритм для аппроксимации . Рассмотрим следующую полуопределенную программу :${\displaystyle \|A\|_{\infty \to 1}}$

${\displaystyle {\text{SDP}}(A)=\max \left\{\sum _{i=1}^{m}\sum _{j=1}^{n}a_{ij}\left\langle x_{i},y_{j}\right\rangle :x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}\in S^{n+m-1}\right\}.}$

Тогда . Неравенство Гротедика подразумевает, что . Известно, что многие алгоритмы (такие как методы внутренней точки , методы первого порядка, метод пучка, расширенный метод Лагранжа ) выводят значение полуопределенной программы с точностью до аддитивной ошибки  во времени, которая является полиномиальной по размеру описания программы и . ^[20] Следовательно, можно вывести , который удовлетворяет${\displaystyle {\text{SDP}}(A)\geq \|A\|_{\infty \to 1}}$${\displaystyle {\text{SDP}}(A)\leq K_{G}^{\mathbb {R} }\|A\|_{\infty \to 1}}$${\displaystyle \varepsilon }$${\displaystyle \log(1/\varepsilon )}$${\displaystyle \alpha ={\text{SDP}}(B)}$

${\displaystyle \|A\|_{\square }\leq \alpha \leq C\|A\|_{\square }\qquad {\text{with}}\qquad C=K_{G}^{\mathbb {R} }.}$

Лемма регулярности Семереди является полезным инструментом в теории графов, утверждая (неформально), что любой граф можно разбить на контролируемое число частей, которые взаимодействуют друг с другом псевдослучайным образом . Другое применение неравенства Гротендика заключается в создании разбиения множества вершин, которое удовлетворяет заключению леммы регулярности Семереди , с помощью алгоритма оценки нормы разреза, за время, которое является полиномиальным относительно верхней границы размера регулярного разбиения Семереди, но не зависит от числа вершин в графе. ^[19]

Оказывается, что основным «узким местом» построения регулярного разбиения Семереди за полиномиальное время является определение за полиномиальное время того, близка ли заданная пара к -регулярности , то есть для всех с , мы имеем${\displaystyle (X,Y)}$${\displaystyle \varepsilon }$${\displaystyle S\subset X,T\subset Y}$${\displaystyle |S|\geq \varepsilon |X|,|T|\geq \varepsilon |Y|}$

${\displaystyle \left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|\leq \varepsilon ,}$

где для всех и — вершины и ребра графа соответственно. Для этого мы строим матрицу , где , определяемую как${\displaystyle e(X',Y')=|\{(u,v)\in X'\times Y':uv\in E\}|}$${\displaystyle X',Y'\subset V}$${\displaystyle V,E}$${\displaystyle n\times n}$${\displaystyle A=(a_{xy})_{(x,y)\in X\times Y}}$${\displaystyle n=|V|}$

${\displaystyle a_{xy}={\begin{cases}1-{\frac {e(X,Y)}{|X||Y|}},&{\text{if }}xy\in E,\\-{\frac {e(X,Y)}{|X||Y|}},&{\text{otherwise}}.\end{cases}}}$

Тогда для всех ,${\displaystyle S\subset X,T\subset Y}$

${\displaystyle \left|\sum _{x\in S,y\in T}a_{xy}\right|=|S||T|\left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|.}$

Следовательно, если не является -регулярным, то . Отсюда следует, что, используя алгоритм аппроксимации нормы разреза вместе с техникой округления, можно найти за полиномиальное время такое, что${\displaystyle (X,Y)}$${\displaystyle \varepsilon }$${\displaystyle \|A\|_{\square }\geq \varepsilon ^{3}n^{2}}$${\displaystyle S\subset X,T\subset Y}$

${\displaystyle \min \left\{n|S|,n|T|,n^{2}\left|{\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}.}$

Тогда алгоритм создания регулярного разбиения Семереди следует из конструктивного аргумента Алона и др. ^[21]

Неравенство Гротендика для графа утверждает, что для каждого и для каждого графа без петель существует универсальная константа, такая что каждая матрица удовлетворяет условию${\displaystyle n\in \mathbb {N} }$${\displaystyle G=(\{1,\ldots ,n\},E)}$${\displaystyle K>0}$${\displaystyle n\times n}$${\displaystyle A=(a_{ij})}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{ij\in E}a_{ij}\left\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}.}$^[22]

Константа Гротендика графа , обозначаемая , определяется как наименьшая константа , удовлетворяющая указанному выше свойству.${\displaystyle G}$${\displaystyle K(G)}$${\displaystyle K}$

Неравенство Гротендика графа является расширением неравенства Гротендика, поскольку первое неравенство является частным случаем последнего неравенства, когда — двудольный граф с двумя копиями в качестве его двудольных классов. Таким образом,${\displaystyle G}$${\displaystyle \{1,\ldots ,n\}}$

${\displaystyle K_{G}=\sup _{n\in \mathbb {N} }\{K(G):G{\text{ is an }}n{\text{-vertex bipartite graph}}\}.}$

Для , полного графа с -вершинами, неравенство Гротендика принимает вид${\displaystyle G=K_{n}}$${\displaystyle n}$${\displaystyle G}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{i,j\in \{1,\ldots ,n\},i\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}.}$

Оказывается, что . С одной стороны, имеем . ^{[23] [24] [25]} Действительно, для любой матрицы справедливо следующее неравенство , из которого следует, что по неравенству Коши-Шварца : ^[22]${\displaystyle K(K_{n})\asymp \log n}$${\displaystyle K(K_{n})\lesssim \log n}$${\displaystyle n\times n}$${\displaystyle A=(a_{ij})}$${\displaystyle K(K_{n})\lesssim \log n}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{i,j\in \{1,\ldots ,n\},i\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 {\sum _{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}.}$

С другой стороны, соответствующая нижняя граница была получена Алоном , Макарычевым, Макарычевым и Наором в 2006 году. ^[22]${\displaystyle K(K_{n})\gtrsim \log n}$

Неравенство Гротендика графа зависит от структуры . Известно, что${\displaystyle K(G)}$${\displaystyle G}$${\displaystyle G}$

${\displaystyle \log \omega \lesssim K(G)\lesssim \log \vartheta ,}$^[22]

и

${\displaystyle K(G)\leq {\frac {\pi }{2\log \left({\frac {1+{\sqrt {(\vartheta -1)^{2}+1}}}{\vartheta -1}}\right)}},}$^[26]

где - число клики , т.е. наибольшее такое, что существует с таким, что для всех различных , и${\displaystyle \omega }$${\displaystyle G}$${\displaystyle k\in \{2,\ldots ,n\}}$${\displaystyle S\subset \{1,\ldots ,n\}}$${\displaystyle |S|=k}$${\displaystyle ij\in E}$${\displaystyle i,j\in S}$

${\displaystyle \vartheta =\min \left\{\max _{i\in \{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\;\forall ij\in E\right\}.}$

Параметр известен как тета-функция Ловаса дополнения . ^{[27] [28] [22]}${\displaystyle \vartheta }$${\displaystyle G}$

При применении неравенства Гротендика для аппроксимации нормы разреза мы увидели, что неравенство Гротендика отвечает на следующий вопрос: насколько хорошо оптимальное решение полуопределенной программы аппроксимирует , которую можно рассматривать как задачу оптимизации над единичным кубом? В более общем смысле, мы можем задавать аналогичные вопросы над выпуклыми телами, отличными от единичного куба.${\displaystyle {\text{SDP}}(A)}$${\displaystyle \|A\|_{\infty \to 1}}$

Например, следующее неравенство получено Наором и Шехтманом ^[29] и независимо Гурусвами и др.: ^[30] Для каждой матрицы и каждого ,${\displaystyle n\times n}$${\displaystyle A=(a_{ij})}$${\displaystyle p\geq 2}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in \mathbb {R} ^{n},\sum _{k=1}^{n}\|x_{k}\|_{2}^{p}\leq 1}\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq \gamma _{p}^{2}\max _{t_{1},\ldots ,t_{n}\in \mathbb {R} ,\sum _{k=1}^{n}|t_{k}|^{p}\leq 1}\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}t_{i}t_{j},}$

где

${\displaystyle \gamma _{p}={\sqrt {2}}\left({\frac {\Gamma ((p+1)/2)}{\sqrt {\pi }}}\right)^{1/p}.}$

Константа точна в неравенстве. Формула Стерлинга подразумевает, что при .${\displaystyle \gamma _{p}^{2}}$${\displaystyle \gamma _{p}^{2}=p/e+O(1)}$${\displaystyle p\to \infty }$

• Неравенство Пизье–Рингроуза

• Вайсштейн, Эрик В. «Константа Гротендика». MathWorld .(Примечание: историческая часть здесь не точна.)