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

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

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

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

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

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

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

Мотивация и формулировка оператора

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

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

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

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

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

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

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

${\begin{aligned}\max &\qquad \sum _{i,j}A_{ij}\langle x^{(i)},y^{(j)}\rangle \\{\text{s.t.}}&\qquad x^{(1)},\ldots ,x^{(m)},y^{(1)},\ldots ,y^{(n)}{\text{ are unit vectors in }}(\mathbb {R} ^{d},\|\cdot \|_{2})\end{aligned}}$

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

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

$\max _{x^{(i)},y^{(i)}\in H{\text{ unit vectors}}}\sum _{i,j}A_{ij}\left\langle x^{(i)},y^{(j)}\right\rangle _{H}\leq C\|A\|_{\infty \to 1}.$

Границы констант

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

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

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

Константа Гротендика порядка d

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

Нижние границы

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

д	Гротендик, 1953 год.	Кривые, 1979 г.	Дэви, 1984 год.	Фишберн и др., 1994 г.	Вертези, 2008 г.	Бриет и др., 2011 г.	Хуа и др., 2015 г.	Дивиански и др., 2017 г.	Дизайноль и др., 2023 г.
2		${\sqrt {2}}$ ≈ 1.41421
3					1.41724		1.41758	1.4359	1.4367
4					1.44521		1.44566	1.4841
5				${\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
∞	${\frac {\pi }{2}}$ ≈ 1.57079		1.67696

Верхние границы

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

д	Гротендик, 1953 год.	Ритц, 1974 г.	Кривые, 1979 г.	Браверман и др., 2011 г.	Хирш и др., 2016 г.	Дизайноль и др., 2023 г.
2			${\sqrt {2}}$ ≈ 1.41421
3			1.5163		1.4644	1.4546
4			${\frac {\pi }{2}}$ ≈ 1.5708
8			1.6641
∞	$\operatorname {sinh} {\frac {\pi }{2}}$ ≈ 2.30130	2.261	${\frac {\pi }{2\ln(1+{\sqrt {2}})}}$ ≈ 1.78221	${\frac {\pi }{2\ln(1+{\sqrt {2}})}}-\varepsilon$

Приложения

Оценка нормы сокращения

Учитывая $m\times n$ реальная матрица $A=(a_{ij})$, отсечения норма $A$ определяется

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

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

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

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

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

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

где $C$ является абсолютной константой. Этот алгоритм аппроксимации использует полуопределенное программирование .

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

${\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}}.$

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

$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$

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

$\|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\}.$

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

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

${\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\}.$

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

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

Семереди

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

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

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

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

$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}}$

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

$\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|.$

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

$\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}.$

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

Варианты

графа

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

$\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}.$

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

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

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

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

$\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}.$

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

$\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}.$

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

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

$\log \omega \lesssim K(G)\lesssim \log \vartheta ,$

и

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

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

$\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\}.$

Параметр $\vartheta$ известна как тэта-функция Ловаса дополнения $G$.

L^p Неравенство Гротендика

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

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

$\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},$

где

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

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

См. также

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

Внешние ссылки

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