- Gil Cohen
- Igor Shinkar
bibliography:
- 'bibliography.bib'
title: |
    Bi-Lipschitz Bijection between the Boolean Cube\
    and the Hamming Ball
---

Introduction {#sec:intro}
============

The Boolean cube ${\{0,1\}^{n}}$ and the Hamming ball ${\mathcal{B}_{n}}= \{x \in {\{0,1\}^{n+1}} \colon |x|>n/2\}$, equipped with the Hamming distance, are two fundamental combinatorial structures that exhibit, in some aspects, different geometric properties. As a simple illustrative example, for an even integer $n \in {{\mathbb N}}$, consider the vertex and edge boundaries[^2] of ${\{0,1\}^{n}}$ and ${\mathcal{B}_{n}}$, when viewed as subsets of ${\{0,1\}^{n+1}}$ of equal density $1/2$. The Boolean cube is easily seen to maximize vertex boundary among all subsets of equal density (since all its vertices lie on the boundary), whereas Harper’s vertex-isoperimetric inequality [@Harper66] implies that the Hamming ball is in fact the unique minimizer. The same phenomena occurs for edge boundary, though interestingly, the roles are reversed: among all monotone sets[^3] of density $1/2$, the Poincaré inequality implies that the Boolean cube is the unique minimizer of edge boundary, whereas a classical result of Hart shows that the Hamming ball is the unique maximizer [@Hart76]. From the Boolean functions perspective, the indicator of ${\{0,1\}^{n}}$ embedded in ${\{0,1\}^{n+1}}$ is commonly referred to as the *dictator* 