Vertical perimeter versus horizontal perimeter

Abstract

The discrete Heisenberg group ${\mathbb{H}}_{\mathbb{Z}}^{2k+1}$ is the group generated by $a_1,b_1,\dots ,a_k,b_k,c$, subject to the relations $[a_1,b_1]=\dots =[a_k,b_k]=c$ and $[a_i,a_j]=[b_i,b_j]=[a_i,b_j]=[a_i,c]=[b_i,c]=1$ for every distinct $i,j\in \{1,\dots ,k\}$. Denote $S=\{a_1^{\pm 1},b_1^{\pm 1},\dots ,a_k^{\pm 1},b_k^{\pm 1}\}$. The horizontal boundary of $\Omega \subset {\mathbb{H}}_{\mathbb{Z}}^{2k+1}$, denoted ${\partial }_h\Omega$, is the set of all $(x,y)\in \Omega \times ({\mathbb{H}}_{\mathbb{Z}}^{2k+1}\setminus \Omega )$ such that $x^{-1}y\in S$. The horizontal perimeter of $\Omega$ is $|{\partial }_h\Omega |$. For $t\in \mathbb{N}$, define ${\partial }_v^t\Omega$ to be the set of all $(x,y)\in \Omega \times ({\mathbb{H}}_{\mathsf{Z}}^{2k+1}\setminus \Omega )$ such that $x^{-1}y\in \{c^t,c^{-t}\}$. The vertical perimeter of $\Omega$ is defined by $|{\partial }_v\Omega |=\sqrt{{\sum }_{t=1}^{\infty }|{\partial }_v^t\Omega {|}^2/t^2}$. It is shown here that if $k\ge 2$, then $|{\partial }_v\Omega |\lesssim \frac{1}{k}|{\partial }_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. The above inequality has several applications, including that any embedding into $L_1$ of a ball of radius $n$ in the word metric on ${\mathbb{H}}_{\mathbb{Z}}^5$ incurs bi-Lipschitz distortion that is at least a constant multiple of $\sqrt{\log n}$. It follows that the integrality gap of the Goemans--Linial semidefinite program for the Sparsest Cut Problem on inputs of size $n$ is at least a constant multiple of $\sqrt{\log n}$.

suggestions of referees addressed