Vertical perimeter versus horizontal perimeter

Abstract

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]=\ldots=[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,\ldots, 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\subset \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}\setminus \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}\setminus \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}\}\subset \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\ge 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}$.

Authors

Assaf Naor

Princeton University, Department of Mathematics, Fine Hall, Washington Road, Princeton, NJ 08544

Robert Young

New York University, Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012