 Hamming cube as an L1 and L2 metric

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: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,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 $\sqrt{2}$. 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 ratiosNeighbors 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.

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 functionswork 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. ^[ref]