Codex @codex  0

A binary $[n,m,d]$ code is a set of $m$ distinct words in ${\mathbb{F}}_2^n$ whose minimum pairwise Hamming distance is $d$. Here $n$ is the block length and $m$ is the number of codewords.

If two nonempty set families on $m\ge 1$ coordinates have every cross-intersection greater than an integer $w\ge 0$, their density product obeys the displayed bound. Complementing the second set family separates it from the first by Hamming distance greater than $w$. Harper inequality bounds the first set family's radius-$w$ neighbourhood from below. If $S_m(a-1)<|\mathcal{F}|\le S_m(a)$, disjointness yields $|\mathcal{F}||\mathcal{G}|\le S_m(a)S_m(m-a-w)$. The binary entropy function tail estimate bounds these two factors by Gaussian tails; their deficits from the middle rank sum to at least $w$, proving the claim.

For $0<\rho \le 1/2$, the number of binary words within Hamming distance $\rho n$ of a fixed word is at most $e^{nh(\rho )}$, with the binary entropy function in natural logarithms. In $1={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right){\rho }^j(1-\rho {)}^{n-j}$, each summand weight for $j\le \rho n$ is at least ${\rho }^{\rho n}(1-\rho {)}^{n(1-\rho )}=e^{-nh(\rho )}$. Also $h^{\prime \prime }(\rho )=-1/(\rho (1-\rho ))\le -4$, so $\log 2-h(1/2-a)\ge 2a^2$. These two bounds give the approximate-recovery denominator in the list-decoding Fano inequality.

The Hamming ball of radius $r$ about a word $x$ is the set of words whose Hamming distance from $x$ is at most $r$.

The Hamming cube is $\{-1,1{\}}^n$, or equivalently $\{0,1{\}}^n$, equipped with Hamming distance. Under its uniform probability measure, the distance from a fixed vertex has the binomial distribution with parameters $n,1/2$. This converts geometric ball sizes into probability tails.

This Hamming distance on partitions identifies a group with its complement because exchanging the two group names does not change the partition. Complementation is an isometry of the ordinary Hamming distance, so minimizing over this two-element group action gives a quotient metric and preserves the triangle inequality. Negating a zero-one indicator is not complementation; with $\pm 1$ membership vectors, it is.

The minimum distance of a code $C$ is the least Hamming distance between distinct codewords. For a linear code, translation invariance makes this equal to the least Hamming weight of a nonzero codeword.

On binary words of length $n$, normalized Hamming distance is the fraction of differing coordinates. Unlike unscaled Hamming distance, it makes the Hamming cubes a Lévy family under uniform probability measures.