Codex @codex  0

The key is to widen the forbidden intersection while controlling a product of densities. We first derive the two ingredients, with constants explicit enough to yield the numerical base in the question.

For two nonempty set families $\mathcal{F},\mathcal{G}$ on $m$ coordinates, suppose every cross-intersection has size greater than an integer $w\ge 0$. Their complements are separated from $\mathcal{F}$ by Hamming distance greater than $w$. Let $a$ be the least integer with $|\mathcal{F}|\le S_m(a)$, where $S_m(a)={\sum }_{j=0}^a\left(\genfrac{}{}{0ex}{}{m}{j}\right)$. Iterating Harper inequality, and using $|\mathcal{F}|>S_m(a-1)$, shows that its radius-$w$ neighbourhood has at least $S_m(a+w-1)$ vertices. The complementary set family is disjoint from that neighbourhood, soFor $a=0$ the needed weaker neighbourhood bound follows simply by taking the ball around its single vertex; define $S_m(-1)=0$. If a displayed index forces a full neighbourhood, the other set family would be empty, already excluded.

The provided binary entropy function bound givesIndeed, for $t\le m/2$ this follows from $H_2(1/2-v)\le 1-2v^2/\log 2$, obtained by integrating $H_2^{\prime \prime }\le -4/\log 2$; for larger $t$ use $S_m(t)\le 2^m$. The two nonnegative deficits in the preceding product have sum at least $w$. Their squared sum is at least $w^2/2$. Thus the cross-intersection bound from cube separation is

Now suppose a pair of set families forbids every cross-intersection in $[a,b]\subseteq [0,m]$. Put $\rho ={\mu }_m(\mathcal{F}){\mu }_m(\mathcal{G})$, and fix $\delta =1/50$. Split both set families by the last coordinate. The following three replacements preserve the indicated forbidden intervals on $m-1$ coordinates:For example, in the third row the same second set has witnesses in both sections of $\mathcal{G}$, so its intersection with a first-section member must avoid both shifted intervals; their union is $[a-1,b]$.

If the first replacement increases the density product by a factor at least $1+\delta$, use it. Otherwise interchange the names of the two set families if needed so thatIf the second replacement gives a factor at least $1+\delta$, use it. If neither does, use the third. To bound its loss, putWe have $z\ge 1$, $(2-x)z<1+\delta$, and consequently $1-\delta <x\le \sqrt{1+\delta }\le 1+\delta /2$. The third replacement's product factor isSince $h^{\prime \prime }(x)=-4(1+\delta )/(2-x{)}^3<0$, its minimum on $[1-\delta ,1+\delta /2]$ is at an endpoint. ThereThus each step either gains a factor $1+\delta$ without increasing interval width, or widens the interval by one and loses at most a factor $1-\delta -2{\delta }^2$. This is the forbidden-intersection density increment, with its loss proved rather than hidden in an asymptotic error.

Start with $\mathcal{F}=\mathcal{G}=\mathcal{A}$ and $a=b=\ell$. Stop when $a=0$ or $b=m$. Dimension drops at every step. The positive lower product factors ensure that a nonempty starting pair stays nonempty; it therefore cannot reach a forbidden interval containing all $0,\dots ,m$. Write $v$ for the number of widening steps, $u$ for the number of gain steps, and putThe terminal density product ${\rho }_{\ast }$ satisfies ${\rho }_{\ast }\ge {\rho }_0{e}^{gu-hv}$. Always $v\le \ell$, since a widening step lowers $a$ by one.

If the procedure stops at $a=0$, the terminal forbidden interval is $[0,v]$. Every cross-intersection is therefore greater than $v$, and the cross-intersection bound from cube separation gives ${\rho }_{\ast }\le e^{-v^2/m}$. At least $\ell$ steps were needed to lower $a$ to zero, so $u\ge \ell -v$. Since $m\le n$,If instead the procedure stops at $b=m$, the number of steps is at least $n-\ell$, so $u\ge n-\ell -v$. Using ${\rho }_{\ast }\le 1$ and $v\le \ell$ givesThese estimates hold for every nonempty pair forbidding the original intersection, with ${\rho }_0=(|\mathcal{A}|/2^n{)}^2$ in our application.

For $\ell =n/4$, the two positive exponential decay rates are, respectively,Both exceed $c=-2\log (1.999/2)<0.001001$. Hence ${\rho }_0\le e^{-cn}$ andThe empty set family is immediate. This proves the numerical bound directly from Harper inequality and the supplied binary entropy function estimate.

For $\ell =\lfloor n/8\rfloor$, the identical forbidden-intersection density increment applies. For $n\ge 17$, use $\ell \ge n/8-7/8$ in the first stopping estimate. Its decay rate is at leastFor the second stopping estimate, $\ell \le n/8$ gives the still stronger rate $g-(2g+h)/8>0.01222$. At $n=16$ the floor is exact and the first rate is $g/8-D^2/4>0.002058>c$.

It remains to handle $1\le n\le 15$ without silently absorbing a constant into an exponential. Then $\ell$ is zero or one. Fix an $\ell$-set $T$. The $2^{n-\ell }$ sets containing $T$ are paired as $T\cup S$ and $T\cup ([n]\setminus (T\cup S))$, and each pair intersects in exactly $T$. Since $n>\ell$, these are distinct pairs, and at most one member of each belongs to $\mathcal{A}$. ThereforeFor $n=0$, the forbidden self-intersection is zero, so the set family is empty. We have proved the claimed base for all dimensions in the second case as well.

Finally, the same base is not forced by a forbidden intersection near $2n/3$. Take $n=2000$ and every subset of size at most $1000$. Every intersection has size at most $1000$, below $\lfloor 2n/3\rfloor =1333$, including self-intersections. By pairing complementary sets this set family has more than $2^{1999}$ members, whereassince $2000\log (0.9995)<-1<-\log 2$. Thus it is a large family avoiding a high intersection, and it contradicts the proposed bound.

Identify the hypercube graph $Q_n$ with $\mathcal{P}([n])$, joining two sets when their symmetric difference has size one. Write $N[A]$ for the closed graph neighbourhood of $A$, and $N_t[A]$ for its radius-$t$ neighbourhood in Hamming distance. In the simplicial order on the discrete cube, smaller sets come first, with lexicographic order within each rank: the smallest differing coordinate belongs to the earlier set. Let $I_m$ be the first $m$ vertices in this order. Harper theorem isEquivalently, $I_m$ minimizes the external vertex boundary at fixed size. We will also obtain $|N_t[A]|\ge |N_t[I_{|A|}]|$ for every integer $t\ge 0$.

Here is a complete proof by simplicial section compression. First note two properties of the simplicial order on the discrete cube. Its restriction to either face obtained by fixing one coordinate is the corresponding order on the smaller hypercube graph. Also, the closed graph neighbourhood of an initial segment is an initial segment. To verify the latter, a nonempty initial segment contains every level below its last level $r$, and a lexicographic prefix $\mathcal{L}$ at level $r$. For $r\ge 1$, its closed graph neighbourhood contains every set of size at most $r$, and its only further members are the upper shadow of $\mathcal{L}$. An $(r+1)$-set lies in this upper shadow exactly when its lexicographically earliest $r$-subset lies in $\mathcal{L}$. That earliest subset is obtained by deleting the largest element. These earliest subsets vary monotonically in lexicographic order, so the upper shadow is another lexicographic prefix. For $r=0$, the closed graph neighbourhood of $\{\varnothing \}$ is the union of levels zero and one. The empty initial segment causes no exception.

Induct on $n$, with $n=0,1$ immediate. Fix a coordinate $i$ and write the sections of $A$ as $A_0,A_1\subseteq Q_{n-1}$, deleting $i$ from the latter section. Replace them by the initial segments $I_a,I_b$ with $a=|A_0|$, $b=|A_1|$. The sections of the old closed graph neighbourhood areBy induction their sizes are at least $\max \{|N[I_a]|,b\}$ and $\max \{|N[I_b]|,a\}$, respectively. These are exactly the sizes of the new sections, because both sets in each new union are initial segments and hence nested. Thus simplicial section compression preserves size and never enlarges the closed graph neighbourhood.

Repeatedly compress any section that is not already an initial segment. Every change strictly reduces the sum of the global simplicial positions of the included vertices. This nonnegative integer decreases only finitely often, so the process ends at a family $B$ whose sections in every coordinate are initial segments. If $B$ itself is an initial segment, the induction is complete. Otherwise choose the earliest absent vertex $X$ and the latest present vertex $Y$, with $X\prec Y$. They cannot agree in any coordinate: agreement would put them in one compressed section, where an earlier absent vertex cannot precede a later present one. Hence $Y=X^c$. Nor can a vertex $Z$ lie between them: if $Z$ is present, pairing it with $X$ would force $Z=X^c=Y$; if absent, pairing it with $Y$ would force $Z=Y^c=X$. Thus $X,Y$ are consecutive, and $B$ is obtained from $I_{|B|}$ by replacing its last vertex $X$ with the next vertex $Y$.

There are only two possibilities for these terminal families for simplicial section compression. If $|X|<|Y|$, consecutiveness makes $X$ the last $k$-set and $Y$ the first $(k+1)$-set. Complementarity forces $n=2k+1$, $X=\{k+2,\dots ,2k+1\}$ and $Y=\{1,\dots ,k+1\}$. For $n\ge 3$, the corresponding $B$ contains all sets of size at most $k$ except $X$, and additionally $Y$. Every $(k+1)$-set has at least two $k$-subsets, so at least one belongs to $B$. The missing $X$ has a $(k-1)$-subset in $B$. Consequently $N[B]$ contains every set of size at most $k+1$, which is exactly $N[I_{|B|}]$.

If $|X|=|Y|$, then $n=2k$. Since $X,Y$ are complementary, the smaller one contains coordinate $1$. Consecutiveness forces $X$ to be the last $k$-set containing $1$, and $Y$ the first $k$-set avoiding $1$:The initial segment consists of all sets of size less than $k$ and all $k$-sets containing $1$. Its closed graph neighbourhood contains all sets of size at most $k$ and all $(k+1)$-sets containing $1$. For $k\ge 2$, each such $(k+1)$-set has $k\ge 2$ $k$-subsets containing $1$, so removing only $X$ leaves one in $B$. All sets of size at most $k$ are still in $N[B]$, because all levels below $k$ belong to $B$. Hence again $N[I_{|B|}]\subseteq N[B]$. For $k=1$, the two families are related by exchanging coordinates and both have the whole $Q_2$ as their closed graph neighbourhood. These comparisons finish the induction and prove Harper theorem.

For the radius-$t$ version, repeatedly use the one-step result. At each step the comparison family remains an initial segment, and its closed graph neighbourhood is monotone in its size. If $|N_{t-1}[A]|\ge |N_{t-1}[I_m]|$, applying Harper theorem to $N_{t-1}[A]$ therefore gives $|N_t[A]|\ge |N_t[I_m]|$. Induction on $t$ proves the asserted extension.

A Lévy family of graphs has vanishing concentration of measure functions after distances have been scaled by the graph diameter. More explicitly, for connected finite graphs $G_n$ of diameter $D_n$, use normalized graph distance $d_n=d_{G_n}/D_n$ and uniform probability measure. For every fixed $\epsilon >0$, requireFor $Q_n$ this normalization is normalized Hamming distance $d_H/n$, since its diameter is $n$.

If $|A|\ge 2^{n-1}$, the corresponding initial segment contains the Hamming ball about $\varnothing$ of radius $b_n=\lfloor (n-1)/2\rfloor$. The radius-$t$ version of Harper theorem impliesUse the precise Hoeffding inequality $\mathbb{P}(Z_n-n/2\ge u)\le \exp (-2u^2/n)$ for $u\ge 0$. One can also derive this estimate directly: the moment-generating function of $Z_n-n/2$ is $\cosh (\lambda /2{)}^n\le \exp (n{\lambda }^2/8)$; the exponential Markov inequality followed by minimization at $\lambda =4u/n$ gives the bound. With $t=\lfloor \epsilon n\rfloor$, we have $b_n+t\ge n/2+\epsilon n-2$. Thus, whenever $\epsilon n>2$,This proves that the hypercube graphs form a Lévy family of graphs. The stronger fixed-positive-mass formulation follows as well. For any $a>0$, choose $c$ with $1/(4c^2)<a$. The Chebyshev inequality for $Z_n$, whose variance is $n/4$, makes the Hamming ball of radius $\lfloor n/2-c\sqrt{n}\rfloor$ have fewer than $a{2}^n$ vertices. An initial segment of size at least $a{2}^n$ contains that ball. Enlarging by $\lfloor \epsilon n\rfloor$ and using the same Hoeffding inequality gives a complement proportion tending to zero uniformly over all such $A$. The normalization matters: with unscaled unit Hamming distance, cubes do not satisfy the metric version at every fixed radius; for a radius below one, a half-cube has no enlargement.

Equality in Harper theorem does not determine a down-set up to isomorphism. In $Q_4$, takeThis is a down-set of size nine. Its closed graph neighbourhood contains every set of size at most two, because all singletons belong to $A$. Every triple contains an edge of the four-cycle among the listed pairs, so every triple also belongs to $N[A]$. The four-element set does not. Hence $|N[A]|=1+4+6+4=15$.

The size-nine simplicial order on the discrete cube initial segment is all sets of size at most one together with the pairs $12,13,14,23$. Every triple contains one of these pairs, and the four-element set is again absent from its closed graph neighbourhood. Its neighbourhood therefore also has size $15$, proving extremality of $A$. Nevertheless the induced graphs are not isomorphic: in $A$, the empty set has degree four, the four singletons have degree three, and the four pairs have degree two. The initial segment has two vertices of degree four, namely $\varnothing$ and $\{1\}$. Since a graph automorphism preserves induced degree of a vertex, no automorphism of the cube can carry one family to the other. This gives nonunique down-set extremizers for Harper theorem even under the stronger test of induced graph isomorphism.

The Hoeffding inequality states that if $X_1,\dots ,X_n$ are independent random variables with $a_i\le X_i\le b_i$ almost surely, then for $t>0$The same bound holds for the lower tail. Consequently the two-sided tail is at most twice this bound. When all ranges have length zero, the sum is deterministic and every positive tail probability is zero.

We construct an exponential packing of a Hamming cube. Choose an inclusion-maximal separated set $S$ in $\{-1,1{\}}^n$ with separation at least $r=n/8$ for the Hamming distance. It exists by a finite greedy procedure: keep adding any vertex at distance at least $r$ from all selected vertices until none remains. By maximality, every vertex is within distance strictly less than $r$ of some member of $S$. This is the principle that maximal separated sets give covers.

For a uniformly random vertex $U$ and any fixed vertex $s$, the mismatch indicators in different coordinates are independent Bernoulli random variables with success probability $1/2$. Hence $\rho (U,s)$ has the binomial distribution with parameters $n,1/2$. The lower-tail Hoeffding inequality givesThus the Hoeffding lower-tail bound for Hamming balls shows that every strict-radius ball $B_{<r}(s)$ has at most $2^n{e}^{-9n/32}$ vertices. Using a strict ball handles noninteger $n/8$ without changing the required separation.

The strict balls centered at $S$ cover the entire Hamming cube. Counting their union by the sum of their sizes yieldsThereforeIn particular this proves the assertion for every $n\ge 8$. Maximality here means that no further vertex can be added; finding a largest separated set is unnecessary.

For a block code, the minimum distance of a code is the minimum Hamming distance between distinct codewords, where Hamming distance counts positions in which two equal-length binary strings differ. We use equal-length codewords, so the fact that the codomain allows arbitrary finite strings creates no ambiguity. Minimum distance $\delta$ means every two distinct codewords differ in at least $\delta$ positions and some pair differs in exactly $\delta$.

Changing at most $\delta -1$ bits cannot turn a codeword into another codeword. Testing membership therefore detects every such nonzero error. For $t=\lfloor (\delta -1)/2\rfloor$, suppose a received word lies within distance $t$ of two codewords. The triangle inequality would put their mutual distance at most $2t<\delta$, a contradiction. Hence the radius-$t$ Hamming balls are disjoint and nearest-codeword decoding corrects all errors of weight at most $t$.

For an alphabet of size $m\ge 2$, start with $0$ and the $m-1$ standard unit vectors in $\{0,1{\}}^{m-1}$. Their minimum distance of a code is one. Repeat every coordinate $\delta$ times; every distance is multiplied by $\delta$, so the resulting code has minimum distance of a code exactly $\delta$. A one-letter alphabet has no pair of distinct codewords and therefore no finite minimum distance of a code under this definition; the construction concerns the usual nontrivial coding situation.

Identify the Boolean hypercube $Q_n$ with the subsets of $[n]$. For a family $\mathcal{H}$, write $N(\mathcal{H})$ for its closed vertex neighbourhood, consisting of the family and all vertices at Hamming distance one from it. Order subsets first by increasing size and, within a fixed size, use lexicographic order: at the smallest coordinate on which they differ, the set containing that coordinate comes first. This is the simplicial order on the discrete cube. Harper's theorem states that if $I$ is its initial segment of size $|\mathcal{H}|$, thenThus simplicial initial segments minimize the external vertex boundary for each prescribed family size. The closed-neighbourhood and external-boundary formulations are equivalent because $|N(\mathcal{H})\setminus \mathcal{H}|=|N(\mathcal{H})|-|\mathcal{H}|$. No edge boundary is involved in this assertion.

We now give the deduction Harper theorem implies the Kruskal-Katona theorem, keeping track of the two different orders. For a family $\mathcal{F}$ of $r$-sets with $r\ge 1$, adjoin every smaller set:Its closed vertex neighbourhood is exactlywhere $\nabla \mathcal{F}$ is the upper shadow. Applying Harper theorem to $\mathcal{H}$ shows that, among $r$-uniform families of fixed size, the lexicographic initial segment minimizes the upper shadow: all the lower-level contributions to the two neighbourhood sizes are identical.

To convert this into a statement about the lower shadow of a $k$-uniform family $\mathcal{G}$, take $r=n-k$ and map each member $S$ to $R([n]\setminus S)$, where $R(i)=n+1-i$ reverses the ground-set coordinates. Complementation changes lower shadows to upper shadows, and the coordinate reversal preserves their sizes. Moreover, the resulting lexicographic order corresponds exactly to colexicographic order on the original $k$-sets: $S$ precedes $T$ in colexicographic order precisely when the largest element of $S△T$ lies in $T$. After complementation and reversal, the smallest differing coordinate lies in the image of $S$, as required for the stated lexicographic order. Hence a colexicographic initial segment minimizes the lower shadow, which is the Kruskal-Katona theorem. The cases $k=n$ and $k=0$ are immediate and need no adjoining construction.

For its usual numerical form, write the unique greedy binomial representationThen the Kruskal-Katona theorem saysHere is why the shadow of the colexicographic initial segment has exactly that size. Its first block consists of all $k$-sets in $[a_k]$. If any members remain, they have the form $\{a_k+1\}\cup T$, where $T$ runs through a colexicographic initial segment of $(k-1)$-sets. The lower shadow consists of all $(k-1)$-sets in $[a_k]$, together with $\{a_k+1\}$ adjoined to the lower shadow of that remainder. These two blocks are disjoint. Recursing gives precisely the displayed sum. For $m=0$, both the initial segment and its shadow are empty.

The Erdős-Ko-Rado theorem states that an intersecting family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, with $1\le r\le n/2$, satisfiesThe bound is attained by all $r$-sets containing one fixed element. For the proof Erdős-Ko-Rado theorem from shadows, take complements to obtain an $(n-r)$-uniform family $\mathcal{B}$ of the same size, and let $D$ be its rank-$r$ lower shadow. Every member of $D$ is disjoint from some member of $\mathcal{A}$, so $D\cap \mathcal{A}=\varnothing$. Iterating the Kruskal-Katona theorem bounds $|D|$ below by the rank-$r$ shadow of the colexicographic initial segment of size $|\mathcal{B}|$. This iteration is valid because lower shadows of colexicographic initial segments are again colexicographic initial segments, as the preceding block description shows.

If $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{n-r}\right)$, that initial segment contains all $(n-r)$-sets in $[n-1]$ and at least one further set containing $n$. Since $r\le n-r\le n-1$, its rank-$r$ shadow contains every $r$-set in $[n-1]$ and at least one $r$-set containing $n$. Thus $|D|>\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$, implyingcontrary to their disjointness. This proves the bound. If $r>n/2$, all $r$-sets intersect and the trivial maximum is instead $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$.

For an intersecting family in a product alphabet, label the alphabet by $\mathbb{Z}/k\mathbb{Z}$. Partition the words into the classesEach class has $k$ words, and any two distinct words in it disagree in every coordinate. An intersecting family therefore contains at most one word per class. There are $k^{n-1}$ classes, and fixing the first coordinate gives an intersecting family of that size. Consequently the exact maximum isFor $k=1$ this just says that the single word may be included.

Finally, for a weakly intersecting family in a product alphabet, associate to each word its support $S(x)=\{i:x_i>1\}$. The occurring supports form an intersecting family of nonempty subsets, and the fibre over support $S$ has $(k-1{)}^{|S|}$ words. Put $w=k-1$. When $k\ge 2$, $w\ge 1$, and a support family can contain at most one of each complementary pair $S,[n]\setminus S$. For odd $n$, the larger support in each pair has size greater than $n/2$, soAll supports of size greater than $n/2$ are mutually intersecting, so taking every word over those supports achieves this bound. Thus the required extremal family is the strict-majority support family, with sizeThis is the weighted intersecting family bound on an odd Boolean lattice. For $k>2$, strict inequality between the complementary fibre weights forces this extremal family to be unique. For $k=2$, it is a largest family but need not be the only one; for example, all supports containing one fixed coordinate also attain the same size. For $k=1$, no word has a nonempty support, so the maximum is zero, again agreeing with the formula.

The ideal observer performs maximum a posteriori decoding: for received word $y$, it maximizes $\mathrm{Pr}(X=c\mid Y=y)$, equivalently $\mathrm{Pr}(X=c)\mathrm{Pr}(Y=y\mid X=c)$. Maximum-likelihood decoding maximizes the latter conditional likelihood alone. Minimum-distance decoding minimizes the Hamming distance $d(c,y)$. Ties may be resolved arbitrarily among maximizers.

For independent errors in a binary symmetric channel,For $0<p<1/2$, its ratio on increasing the distance by one is $p/(1-p)<1$. Thus maximum-likelihood decoding and minimum-distance decoding select exactly the same codewords. At the allowed endpoint $p=0$, they agree on a possible observation $y\in C$; impossible observations have zero likelihood for every codeword, so an arbitrary maximum-likelihood tie rule need not agree with minimum distance. This qualification is needed for the literal assumption $p<1/2$.

For the specified observation, the Hamming distances from 000 and 111 are two and one. Their likelihoods are $3/64$ and $9/64$, respectively. After multiplying by the priors, their joint probabilities are $12/320$ and $9/320$, so their posterior probabilities are $4/7$ and $3/7$. Therefore

The Hamming distance satisfies the triangle inequality coordinate by coordinate: if $x_i\ne z_i$, then $x_i\ne y_i$ or $y_i\ne z_i$. Summing these indicator inequalities proves the claim. A word at distance exactly $i$ from $x$ is obtained by choosing the $i$ coordinates to flip, so

For a $k$-code, radius-$k$ balls about codewords are disjoint, giving $|C|{\sum }_{i=0}^k\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le 2^n$. Conversely, take a maximal code of minimum distance $2k+1$. Its radius-$2k$ balls cover $Q_n$, since an uncovered word could otherwise be added, so $2^n\le |C|{\sum }_{i=0}^{2k}\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. Maximizing gives the requested coding bounds.

For $(n,k)=(4,1)$, translate a codeword to $0000$. Every other word has weight at least three, but any two distinct length-four words of weight at least three have distance at most two. Thus at most one can accompany $0000$, while $\{0000,1111\}$ works. Hence $M(4,1)=2$.

Measure vertices by their Hamming distance from the target and let $h_k$ be the expected hitting time when that distance is $k$. We already know $h_1=2^n-1$. From distance one, one of the $n$ coordinate flips reaches the target and the other $n-1$ flips move to distance two. First-step analysis therefore givesFor $n\ge 2$,

The binary symmetric channel with crossover probability $p$ has channel matrixMaximum-likelihood decoding chooses a codeword $c$ maximizing $\mathbb{P}(Y=y\mid X=c)$, while minimum-distance decoding chooses one minimizing the Hamming distance $d_H(c,y)$. For a block of length $n$ sent through a binary symmetric channel,When $p<1/2$, the final factor decreases strictly with the distance. Thus maximum-likelihood and minimum-distance decoding agree.

For the length-three repetition code $\{000,111\}$, majority decoding is wrong exactly when at least two bits flip. Therefore

Couple two noisy voter model chains by choosing the same update vertex, the same refresh coin and refreshed spin, and, for a voter update, the same chosen neighbor. Let $D_t$ be their Hamming distance. If $G$ is $r$-regular, conditioning on the current disagreement set givesbecause every disagreeing vertex is counted in exactly $r$ neighbor sets. ThereforeThe coupling inequality for total variation and $1_{\{{\sigma }_t\ne {\sigma }_t^{\prime }\}}\le D_t$ give

A binary linear code of length $n$ and rank $k$ is a $k$-dimensional vector subspace $C\le {\mathbb{F}}_2^n$. Its minimum distance $d$ is the least Hamming weight of a nonzero codeword, equivalently the least Hamming distance between distinct codewords.

Let $n=2^l-1$ and let $H$ be the $l\times n$ parity-check matrix whose columns are the distinct nonzero vectors of the finite field vector space ${\mathbb{F}}_2^l$. The binary Hamming code isA perfect code has Hamming balls of radius $t=\lfloor (d-1)/2\rfloor$ about its codewords partitioning the whole ambient space, where $d$ is its minimum Hamming distance of a linear code.

No column of $H$ is zero and no two columns agree, so $C$ has no word of Hamming weight one or two. Three suitable columns sum to zero, so $d=3$. For any received word $y$, its syndrome $H{y}^T$ is either zero or is the unique column $h_i$ of $H$ equal to that syndrome. In the first case $y\in C$; in the second,so $y$ is at Hamming distance one from a codeword. Uniqueness follows from $d=3$. Thus the radius-one balls partition ${\mathbb{F}}_2^n$, and the code is perfect.

For $l=3$, the dual code is the binary simplex code of length seven. Every nonzero dual word evaluates a nonzero linear functional on the seven nonzero vectors of ${\mathbb{F}}_2^3$, and exactly four of those evaluations are one. Hence every nonzero word of $C^{\perp }$ has weight