([*i.e.*]{} sublinear) on maximum stretch were known. For a survey on metric embeddings of finite spaces see [@Li02]. In particular, a lot of research has been done on the question of embedding into the Boolean cube. For example, see [@AB07; @HLN87] for some work on embeddings between random subsets of the Boolean cube, and [@G88] for isometric embeddings of arbitrary graphs into the Boolean cube.

Our Results
-----------

The main result of this paper is a strong *negative* answer to Problem \[prob:dict to maj\].

\[thm:main\] For all even integers $n$, there exists a bijection ${\psi}\colon {\{0,1\}^{n}}\to {\mathcal{B}_{n}}$ with $${{\sf maxStretch}}({\psi}) \le 4$$ and $${{\sf maxStretch}}({\psi}^{-1}) \le 5.$$

Theorem \[thm:main\] highlights a surprising geometric resemblance between the Boolean cube and the Hamming ball. In the language of metric geometry, Theorem \[thm:main\] says that there is a bi-Lipschitz bijection between the two spaces.

For all even integers $n$, there exists a bijection ${\psi}\colon {\{0,1\}^{n}}\to {\mathcal{B}_{n}}$, such that for every $x \neq y \in {\{0,1\}^{n}}$ it holds that $$\frac{1}{5}\leq \frac{{{\sf distance}}({\psi}(x),{\psi}(y))}{{{\sf distance}}(x,y)} \leq 4.$$

As a corollary from Theorem \[thm:main\], we obtain that the subgraph of $\{0,1\}^{n+1}$ induced by the vertices of ${\mathcal{B}_{n}}$ is *bi-Lipschitz transitive*. Informally speaking, this says that any two 