## Abstract

Given k ∈ N, the k'th discrete Heisenberg group, denoted H_{ℤ}^{2k+1}, is the group generated by the elements a_{1}, b_{1}, . ., a_{k}, b_{k}, c, subject to the commutator relations [a1, b1] = · · · = [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 ∈ [1, . . . . k], we have [a_{i}, a_{j}] = [b_{i}, bj ] = [a_{i}, b_{j}] = [a_{i}, c] = [b_{i}, c] = 1. (In particular, this implies that c is in the center of H_{ℤ}^{2k+1}.) Denote b[cyrillic]_{k} = [a_{1}, b_{1}, a_{1}^{-1}, b_{1}^{-1}, . . ., a_{k}, b_{k}, a_{k}^{-1}, b_{k}^{-1}]. The hori- zontal boundary of Ω ⊆ H_{ℤ}^{2k+1}, denoted ∂_{h}Ω, is the set of all those pairs (x, y) ∈ Ω ×(H_{ℤ}^{2k+1}\Ω) such that x^{-1}y ∈ b[cyrillic]_{k}. The horizontal perimeter of Ω is the cardinality |∂_{h}Ω| of ∂_{h}Ω; i.e., it is the total number of edges incident to Ω in the Cayley graph induced by b[cyrillic]_{k}. For t ∈ N, define ∂_{v}^{t}Ω to be the set of all those pairs (x, y) ∈ Ω × (H_{ℤ}^{2k+1}\Ω) such that x^{-1}y ∈ [c^{t}, c^{-t}]. Thus, |∂_{v}^{t}Ω| is the total number of edges incident to Ω in the (disconnected) Cayley graph induced by [c^{t}, c^{-t}] ⊆ H_{ℤ}^{2k+1}. The vertical perimeter of Ω is defined by |∂_{v}jΩ|. It is shown here that if k ≥ 2, then |∂_{v}Ω|≲ |∂_{v}Ω| The proof of this \vertical versus horizontal isoperi- metric inequality" uses a new structural result that decomposes sets of finite perimeter in the Heisenberg group into pieces that admit an \in- trinsic corona decomposition. "This allows one to deduce an endpoint W^{1,2} → L_{2}(L_{1}) boundedness of a certain singular integral operator from a corresponding lower-dimensional W^{1,2} → 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 ∈ N, any embedding into an L_{1}(μ) space of a ball of radius n in the word metric on H_{ℤ}^{5} that is induced by the generating set b[cyrillic]_{2} incurs bi-Lipschitz distortion that is at least a universal constant multiple of √ log n. As an application to approximation algorithms, it follows that for every n ∈ ℕ, the integral- ity 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 √ log n.

Original language | English (US) |
---|---|

Pages (from-to) | 171-279 |

Number of pages | 109 |

Journal | Annals of Mathematics |

Volume | 188 |

Issue number | 1 |

DOIs | |

State | Published - Jul 1 2018 |

## All Science Journal Classification (ASJC) codes

- Statistics and Probability
- Statistics, Probability and Uncertainty

## Keywords

- Approximation algorithms
- Heisenberg group
- Isoperimetric inequalities
- Metric embeddings
- Metrics of negative type
- Semidefinite programming
- Sparsest Cut Problem