= Hamming cube as an L1 and L2 metric
{c}
{title2=$H_n=\{0,1\}^n$}
Use the $\{0,1\}^n$ convention for the <Hamming cube> $H_n$. Its elements are length-$n$ <binary strings>, and their <Hamming distance> counts the differing coordinates:
$$
k=d_H(x,y)=\sum_{j=1}^n|x_j-y_j|.
$$
Send each <binary string> to the <vector> with the same coordinates, by $\iota_n:H_n\to\mathbb R^n$. Every differing coordinate contributes $1$ both to the sum of absolute differences and to the sum of squared differences. Therefore the <L1 norm> and <L2 norm> give, respectively,
$$
d_1(\iota_nx,\iota_ny)=k,\qquad
d_2(\iota_nx,\iota_ny)=\sqrt{k}.
$$
This short coordinate calculation proves that the <L1 norm> gives an <isometric embedding>, while <Euclidean distance> grows like the <square root> of the number of changed <binary digits>. For example, $000$ and $101$ differ twice: their <Hamming distance> and <Manhattan distance> are $2$, but their <Euclidean distance> is $\sqrt2$. Comparing <binary strings> in these two geometric representations answers different questions even though the points have the same coordinates.
For distinct pairs $k$ ranges over every integer from $1$ to $n$. The <metric embedding> into the <L2 norm> thus has sharp ratios
$$
\frac{d_2(\iota_nx,\iota_ny)}{d_H(x,y)}=\frac1{\sqrt{k}},\qquad
a=\frac1{\sqrt n},\quad b=1,\quad
\operatorname{dist}(\iota_n)=\sqrt n.
$$
Neighbors attain $b$ and opposite corners attain $a$. This computes the <bi-Lipschitz distortion> of this coordinate map; it does not prove that every <metric embedding> into an <L2 space> has at least this <bi-Lipschitz distortion>. Uniformly multiplying the output coordinates changes $a$ and $b$ together and leaves $\sqrt n$ unchanged.
\Image[/hamming-cube-distance-scaling.png]
{title=Hamming distances become k in L1 and square root of k in L2, with controls independent of dimension}
The important family distinction is that these coordinate maps have no dimension-independent bound on their <bi-Lipschitz distortion> into the <L2 norm>, yet they do give a <uniform coarse embedding of a family of metric spaces>. Pad each output <vector> with zero coordinates to view all maps in the single <l2 sequence space>, an <L2 space> for <counting measure>. Then the same functions
$$
\rho_-(t)=\rho_+(t)=\sqrt t\qquad(t\geq0)
$$
work for every $n$, and $\rho_-(t)\to\infty$. Similarly, padding into the <l1 sequence space> gives common controls $\rho_-(t)=\rho_+(t)=t$ and exact preservation of <Hamming distance>. These claims use unnormalized <Hamming distance>; replacing it by <normalized Hamming distance> changes the family of source <metrics>.
The geometry has a practical origin: Hamming's 1950 paper uses the number of differing positions between <binary strings> to study <error-correcting codes>. Changing one <binary digit> moves to a neighboring corner, so a question about corrupted messages becomes a question about separation in the <Hamming cube>. https://ineffectivetheory.com/edu/papers/hamming-codes-1950.pdf[R. W. Hamming, Error Detecting and Error Correcting Codes, 1950, Section 5]{ref}
Back to article page
