Vertical perimeter versus horizontal perimeter

Assaf Naor¹ ; Robert Young²

¹ Department of Mathematics, Princeton University, Princeton, NJ
² New York University, Courant Institute of Mathematical Sciences, New York, NY

Annals of mathematics, Tome 188 (2018) no. 1, pp. 171-279

Résumé

Given $k\in \mathbb {N}$, the $k$’th discrete Heisenberg group, denoted $ \mathbb {H}_{\scriptscriptstyle {\mathbb {Z}}}^{2k+1}$, is the group generated by the elements $a_1,b_1,\ldots ,a_k,b_k,c$, subject to the commutator relations $[a_1,b_1]=\cdots =[a_k,b_k]=c$, while all the other pairs of elements from this generating set are required to commute, i.e., for every distinct $i,j\in \{1,…,k\}$, we have $[a_i,a_j]=[b_i,b_j]=[a_i,b_j]=[a_i,c]=[b_i,c]=1$. (In particular, this implies that $c$ is in the center of $ \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{2k+1}$.) Denote $\mathfrak {S}_k=\{a_1,b_1,a_1^{-1},b_1^{-1},\ldots ,a_k,b_k,a_k^{-1},b_k^{-1}\}$. The horizontal boundary of $\Omega \subseteq \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{2k+1}$, denoted $\partial _{\mathsf {h}}\Omega $, is the set of all those pairs $(x,y)\in \Omega \times ( \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{2k+1}\smallsetminus \Omega )$ such that $x^{-1}y\in \mathfrak {S}_k$. The horizontal perimeter of $\Omega $ is the cardinality $|\partial _{\mathsf {h}}\Omega |$ of $\partial _{\mathsf {h}}\Omega $; i.e., it is the total number of edges incident to $\Omega $ in the Cayley graph induced by $\mathfrak {S}_k$. For $t\in \mathbb {N}$, define $\partial ^t_{\mathsf {v}} \Omega $ to be the set of all those pairs $(x,y)\in \Omega \times ( \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{2k+1}\smallsetminus \Omega )$ such that $x^{-1}y\in \{c^t,c^{-t}\}$. Thus, $|\partial ^t_{\mathsf {v}}\Omega |$ is the total number of edges incident to $\Omega $ in the (disconnected) Cayley graph induced by $\{c^t,c^{-t}\}\subseteq \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{2k+1}$. The vertical perimeter of $\Omega $ is defined by $|\partial _{\mathsf {v}}\Omega |= \sqrt { \sum_{t=1}^\infty |\partial ^t_{\mathsf {v}}\Omega |^2/t^2}$. It is shown here that if $k\geqslant 2$, then $|\partial _{\mathsf {v}}\Omega |\lesssim \frac {1}{k} |\partial _{\mathsf {h}}\Omega |$. The proof of this “vertical versus horizontal isoperimetric inequality” uses a new structural result that decomposes sets of finite perimeter in the Heisenberg group into pieces that admit an “intrinsic corona decomposition.” This allows one to deduce an endpoint $W^{1,1}\to L_2(L_1)$ boundedness of a certain singular integral operator from a corresponding lower-dimensional $W^{1,2}\to L_2(L_2)$ boundedness. Apart from its intrinsic geometric interest, the above (sharp) isoperimetric-type inequality has several (sharp) applications, including that for every $n\in \mathbb {N}$, any embedding into an $L_1(\mu)$ space of a ball of radius $n$ in the word metric on $ \mathbb {H}_{ \scriptscriptstyle { \mathbb {Z}}}^{5}$ that is induced by the generating set $\mathfrak {S}_2$ incurs bi-Lipschitz distortion that is at least a universal constant multiple of $\sqrt{\log n}$. As an application to approximation algorithms, it follows that for every $n\in \mathbb {N}$, the integrality gap of the Goemans–Linial semidefinite program for the Sparsest Cut Problem on inputs of size $n$ is at least a universal constant multiple of $\sqrt{\log n}$.

Détail

DOI : 10.4007/annals.2018.188.1.4