Work on a finite interval $[0,T]$ with a fixed initial point $y_0\in {\mathbb{R}}^m$. To give a clean global statement, assume $V_0,V_1,\dots ,V_d$ are bounded vector fields with bounded continuous derivatives through order three. Consider the Stratonovich integral form of the stochastic differential equationFor a control in the Cameron-Martin space of Wiener measure,let $y^h$ solve the controlled ordinary differential equationThe Stroock-Varadhan support theorem says, in the uniform metric on continuous paths,Thus a path is in the support of a measure of the diffusion precisely when it can be approximated by these deterministic controlled trajectories. There is no ellipticity assumption: the allowed controls and vector fields already encode any restrictions on reachability.

The central point of the rough-path proof is that ordinary uniform approximation of the driver does not make the solution map continuous. Small planar loops can have small amplitude but accumulated area of fixed size, and vector fields with a nonzero Lie bracket detect that area. The correct driver is enhanced Brownian motion $\mathbf{B}$, including Lévy area. Fix $2<p<3$. The universal limit theorem gives a continuous mapfrom the geometric $p$-variation rough-path space to solution paths. It agrees with the controlled ordinary differential equation when $\mathbf{X}=S_2(h)$. Adding the time coordinate, with its mixed integrals defined by integration against $dt$ and integration by parts, incorporates $V_0$ without changing the continuity argument. This is the role of the universal limit theorem: it turns a support problem for all these nonlinear diffusions into a support problem for one enhanced driving process.

For $\mathbf{X}=\mathbf{B}$, the rough differential equation is the stated Stratonovich equation. Its second-order increment includesReplacing the Stratonovich integral in the second level by its Itô integral expression contributes $\frac{1}{2}{\sum }_{i}D{V}_i{V}_{i}dt$, which is exactly the Stratonovich-to-Itô correction. Polygonal convergence from Question 3 and the universal limit theorem therefore give the Wong-Zakai approximation: the ordinary equations driven by $B^n$ converge to this Stratonovich diffusion.

It remains to establish the support of enhanced Brownian motion:One inclusion follows immediately from Question 3. Every polygonal $B^n$ belongs to $H$, and $S_2(B^n)\to \mathbf{B}$ almost surely in the rough path metric. Since $K$ is closed, $\mathbf{B}\in K$ almost surely, whence its support is contained in $K$. This alone does not prove the reverse inclusion: convergence of random approximations does not automatically give positive mass near every control.

For that inclusion, take dyadic mesh ${\delta }_n=T{2}^{-n}$ and writeOn each grid interval $R^n$ is a pinned Brownian bridge. The bridges are mutually independent and independent of the grid values defining $B^n$, by the Gaussian projection formula. Their canonical Stratonovich enhancement ${\mathbf{R}}^n$ is therefore independent of $B^n$. It is important to enhance the bridge residual itself, including its area, rather than infer area smallness from its uniform size.

The bridge enhancement tends to the zero rough path in probability. Here are the estimates behind this assertion. A bridge on an interval of length ${\delta }_n$ scales as $\sqrt{{\delta }_n}$ times a unit bridge; its full antisymmetric area has mean zero, moments of order ${\delta }_n$, and second moment of order ${\delta }_n^2$. Since its endpoint displacement is zero, at grid points the cumulative second level is just the sum of the independent bridge areas. The Doob L2 maximal inequality givesPartial intervals at the two ends contribute bridge increments and at most two local areas. Bridge scaling, Gaussian moment bounds and the corresponding iterated-integral estimates yield, uniformly in $n$ and for arbitrarily large $q$,For an interval crossing several grid cells, the full-cell second levels are independent centered areas, whose sum has moments bounded by $C_q((t-s){\delta }_n{)}^{q/2}$; the two boundary pieces and their cross product satisfy the displayed bound as well. For an interval inside one cell these are the usual scaled bridge increment and area bounds. At each fixed pair $(s,t)$ both levels converge to zero in probability: the first-level variance is $O({\delta }_n)$, and the second-level second moment is $O((t-s){\delta }_n+{\delta }_n^2)$ for sufficiently fine grids. The Kolmogorov continuity theorem gives uniformly bounded moments of a Hölder rough-path norm at any exponent $\beta <1/2$. Tightness, convergence on a dense set of pairs and interpolation to $\alpha <\beta$ now give ${\rho }_{\alpha }({\mathbf{R}}^n,e)\to 0$ in probability. Taking $1/p<\alpha <1/2$ gives $d_p({\mathbf{R}}^n,e)\to 0$ in probability.

Fix $h\in H$. Its polygonal interpolations $h^n$ converge to $h$ in the total-variation norm: their derivatives are the cell averages of $\dot{h}$, which converge in $L^2$, hence in $L^1$. Moreover $|h^n{|}_{1\text{-var}}\le |h{|}_{1\text{-var}}$. Thus $S_2(h^n)\to S_2(h)$ in the rough path metric.

The rough path translation operation satisfiesFor a bounded variation path $b$, translation adds $b$ at level one and, at level two, the mixed termsThe second mixed term is defined by integration by parts. Their variation bounds show that translation is continuous, uniformly when $|b{|}_{1\text{-var}}$ is bounded, near the zero rough path. More explicitly the mixed second-level norms are bounded by a constant times $\Vert R{\Vert }_{p\text{-var}}|b{|}_{1\text{-var}}$; the other new second-level term is the path signature of $b$.

Given a ball of radius $\epsilon$ around $S_2(h)$, choose a sufficiently large $n$ so that $S_2(h^n)$ is close andfor the small $\eta$ supplied by translation continuity. The relevant variation bounds can be chosen uniformly in $n$, since the variations of the $h^n$ are uniformly bounded. For this fixed $n$, the event $|B^n-h^n{|}_{1\text{-var}}<\eta$ has positive probability: the finite vector of Brownian increments has an everywhere positive Gaussian density, and sufficiently small deviations of its vertices imply this variation bound. These two events are independent. On their intersection, translation continuity gives $d_p(\mathbf{B},S_2(h))<\epsilon$. Every ball around $S_2(h)$ therefore has positive probability. This proves $S_2(h)$ lies in the support, and taking closures gives $K$.

Finally, a continuous map between the separable path spaces in use satisfiesFor one direction the measure is concentrated on its support. For the other, an open neighborhood of $\Phi (x)$ pulls back to an open neighborhood of a support point $x$, which has positive measure. Using continuity of $\Phi$ and the identity $\Phi (S_2(h))=y^h$ proves the boxed Stroock-Varadhan support theorem. This separates the two ingredients: the probabilistic support calculation for Brownian motion and area, and the deterministic continuity supplied by the universal limit theorem.

If the diffusion is instead presented as an Itô integral equation with drift $b$, the controlled equation must useUsing $b$ unchanged in the controlled equation would generally give the wrong support description. The result above states explicit sufficient smoothness and nonexplosion assumptions; extensions to more general coefficients require the usual localization, not an unqualified assertion for arbitrary vector fields.

Fix $T<\infty$ and a standard $d$-dimensional Brownian motion $B$ starting at zero. Let $D_n$ be deterministic nested finite partitions of $[0,T]$ with mesh tending to zero; dyadic partitions are the basic example. Let $B^n$ be the polygonal interpolation through the partition values and put ${\mathbf{B}}^n=S_2(B^n)$. The limit is enhanced Brownian motion, with incrementsHere the integral is a Stratonovich integral. In terms of Itô integrals,Its symmetric part is $\frac{1}{2}{B}_{s,t}^{\otimes 2}$, while its antisymmetric part is Lévy area,These identities and splitting the integral at an intermediate time give the Chen identity, so $\mathbf{B}$ has values in $G^2({\mathbb{R}}^d)$.

A precise nested polygonal approximation of Brownian rough paths statement is: for every $0<\alpha <1/2$,where the rough path metric used here isIn particular, for each $2<p<3$, choosing $1/p<\alpha <1/2$ gives convergence in the inhomogeneous $p$-variation rough path metric. The limiting signed area is the Lévy area, and the limiting full second level is Stratonovich, not Itô. This distinction is necessary: a polygonal lift has the prescribed symmetric second level, whereas an Itô lift would lack half the quadratic-variation correction.

Here is a proof sketch emphasizing the nested martingale structure. SetA Brownian bridge between two prescribed endpoints has the affine interpolation as conditional mean. ConsequentlyFor $i\ne j$ the coordinate processes remain independent when their respective partition values are conditioned on. Approximating the Itô integral by its left sums, conditioning each product, and then taking its $L^2$ limit givesIndeed each conditioned factor is its polygonal interpolation, and their sums converge to the ordinary integral of those piecewise linear functions. For a fixed pair $s,t$, the right side is therefore a martingale in the refinement index $n$. It is not being asserted to be a martingale in physical time; polygonal interpolation uses the right endpoint of its current cell.

The union of the partitions is dense. Continuity of $B$ implies that ${\mathcal{G}}_{\infty }=\sigma ({\bigcup }_n{\mathcal{G}}_n)$ contains the full Brownian path and its stochastic integrals, up to completion. The martingale convergence theorem for conditional expectations therefore yields convergence of $B_t^n$ and all off-diagonal ${\mathbb{B}}_{s,t}^{n,ij}$ at every fixed pair, almost surely and in $L^q$ for finite $q$. Simultaneously it holds for a countable dense collection of pairs. The diagonal terms must be handled separately:They are not conditional expectations of the diagonal Brownian second level: the latter would also contain a conditional variance.

Pointwise convergence alone is insufficient for the rough path metric. The Burkholder-Davis-Gundy inequalities, Brownian scaling and Gaussian increment moments give, for arbitrarily large $q$,Equivalently, using the homogeneous norm on $G^2$, the $q$-th moment of the Carnot-Carathéodory distance of an increment is bounded by $C_q|t-s{|}^{q/2}$. The metric form of the Kolmogorov continuity theorem, with $q$ chosen large, gives for every $\beta <1/2$ a random $K_{\beta }$ having all finite moments such thatConditioning these bounds givesThe diagonal bounds follow by squaring the first bound. The two conditional-expectation processes are nonnegative martingales; the Doob Lp maximal inequality makes their suprema over $n$ finite almost surely, with all needed moments. Thus all the polygonal lifts have a common random bound at exponent $\beta$.

These bounds and the Chen identity give joint equicontinuity of the increments as functions of $(s,t)$. Convergence on the dense collection of pairs consequently gives uniform convergence of both levels on the time triangle. Take $\alpha <\beta <1/2$. For either level $k=1,2$, with $M$ a common bound and ${\epsilon }_n$ its uniform difference, interpolation givesThis proves the stated Hölder rough path metric convergence. Finally, for a partition $D$, the $k$-th level difference satisfiesbecause $\alpha p>1$. Taking the appropriate powers and suprema proves $p$-variation convergence too. Nesting is what permits the conditional-expectation martingale proof; without nesting one instead needs direct approximation estimates.

For a Lipschitz continuous path $x:[0,T]\to V$, define its signature of a bounded variation path in the truncated tensor algebra byThe Riemann-Stieltjes integrals exist since $x$ has bounded variation. Equivalently, since $x$ is absolutely continuous, the integrand is $x^{\prime }(u_1)\otimes \cdots \otimes x^{\prime }(u_k)$ with Lebesgue integration on the ordered simplex. The degree-zero component is $1$, andThe lift solves $dS=S\otimes dx$, starting at the identity. Since its velocities belong to the first layer, its endpoint lies in the free step-N nilpotent Lie group.

For $s\le t\le u$, partition the degree-$k$ integration simplex according to how many integration variables lie before $t$. If exactly $j$ do, the integral factors as the first $j$-fold integral on $[s,t]$ tensor the last $(k-j)$-fold integral on $[t,u]$. The boundaries with a time equal to $t$ have zero measure. Thuswhich is precisely the Chen identity:This proves the identity at every level, including $k=0$, rather than just checking the first two levels.

For a strictly increasing continuously differentiable map $\psi :[a,b]\to [0,T]$, the actual change of variables formula isTo prove it, substitute $u_j=\psi (v_j)$ in each ordered integral. Strict increase preserves the order, and the almost-everywhere chain rule gives $d(x\circ \psi )(v)=x^{\prime }(\psi (v)){\psi }^{\prime }(v)dv$. The resulting integral is over $\psi (a)<u_1<\cdots <u_k<\psi (b)$. A vanishing derivative at some points causes no difficulty: monotone continuously differentiable substitution still applies, and the zero derivative contributes no variation.

Therefore orientation-preserving reparametrisation of the whole segment preserves its path signature. On $[0,1]$ the printed equality needs $\psi (0)=0$ and $\psi (1)=1$, equivalently that $\psi$ be onto. These endpoints are not forced by the stated assumptions. For example $x(t)=t{e}_1$ and $\psi (t)=t/2$ satisfy those assumptions, butwhich already differ at level one for every $N\ge 1$. The endpoint-preserving interpretation proves the intended invariance, while the general formula states exactly what remains true without it.

Put $V={\mathbb{R}}^d$ and write $a^{(k)}$ for the degree-$k$ component of a tensor. We use the truncated tensor algebraHere $V^{\otimes 0}=\mathbb{R}$, and products of degree above $N$ are discarded. The answers to the three printed parts follow with these conventions; the middle part is missing from the converted TeX.

Use binary codes, so the polynomial modulus is $f(X)=X^N+1=X^N-1$ in ${\mathbb{F}}_2[X]$. A cyclic code $C$ is a linear subspace of ${\mathbb{F}}_2^N$ invariant under the cyclic shift $(a_0,\dots ,a_{N-1})\mapsto (a_{N-1},a_0,\dots ,a_{N-2})$. Identify a word with $a(X)={\sum }_{i=0}^{N-1}{a}_i{X}^i$. Addition is coefficientwise, and multiplication is polynomial multiplication reduced modulo $f$. In the quotient ringmultiplication by $X$ is exactly that cyclic shift. Closure under this map and linear combinations gives closure under multiplication by every polynomial, so a cyclic code is an ideal of $R$. Conversely, an ideal is a linear subspace closed under multiplication by $X$, proving the correspondence.

Take the inverse image of $C$ in ${\mathbb{F}}_2[X]$. This is an ideal containing $(f)$. The polynomial division algorithm shows directly that it has a unique monic generator $g$: choose a nonzero polynomial of least polynomial degree and divide any other member by it; the remainder is in the ideal and has smaller polynomial degree, so must vanish. If two monic generators existed, mutual divisibility would make them equal. Because $f$ belongs to the ideal, $g\mid f$. Conversely every monic divisor of $f$ defines an ideal of $R$. Thus the generator polynomial of a cyclic code satisfiesFor a nonzero code, $g$ is its nonzero polynomial representative of least polynomial degree. For the zero code, use $g=f$, whose residue in $R$ is zero; this standard convention covers that endpoint despite its having no nonzero codeword.

Let $r=\mathrm{deg}g$ and $k=N-r$, and put $h=f/g$. Every codeword has a unique representation $bg$ with $\mathrm{deg}b<k$: dividing an arbitrary multiplier by $h$ does not change its product with $g$ modulo $f$. The words $g,Xg,\dots ,X^{k-1}g$ have distinct leading degrees below $N$ and are independent. ConsequentlyThe statement remains valid for the zero code, with an empty basis, and the full code, with $g=1$.

For length 16, characteristic two gives $X^{16}+1=(X+1{)}^{16}$. Its only monic divisors are $(X+1{)}^j$ for $0\le j\le 16$. Hence all binary cyclic codes of length a power of two in this case areThere are exactly 17 codes, forming the chain $C_{16}\subset C_{15}\subset \cdots \subset C_0$. This is a repeated-root cyclic code situation, so it would be incorrect to count just square-free factors. Their canonical check polynomials of a cyclic code are $(X+1{)}^{16-j}$. An explicit expansion of each generator is ${\prod }_{b:\text{bit }b\text{ of }j\text{ is }1}(1+X^{2^b})$.

The canonical check polynomial of a cyclic code isIndeed $ah\equiv 0(\mathrm{mod}f)$ means $f\mid ah$. Since $f=gh$, cancellation in the polynomial ring gives $g\mid a$, exactly code membership. No coprimality of $g$ and $h$ is needed, including for length 16.

There is a normalization qualification in the printed definition. The kernel condition alone does not force the supplied polynomial $\tilde{h}$ to equal this canonical $h$. If $d=\gcd (f,\tilde{h})$, write $f=d{f}_1$ and $\tilde{h}=d{h}_1$ with $\gcd (f_1,h_1)=1$. Then $f\mid a\tilde{h}$ holds exactly when $f_1\mid a$, so its kernel is the ideal generated by $f/d$. ThereforeEquivalently $\tilde{h}=hu$ with $\gcd (u,g)=1$. Requiring the monic divisor of $f$ selects the canonical check polynomial of a cyclic code. For example $Xh$ gives the same kernel as $h$, since $X$ is a unit modulo $f$, but is generally a different polynomial. Given any permitted $\tilde{h}$, taking $\gcd (f,\tilde{h})$ recovers the canonical $h$.

To construct a parity-check matrix, write the canonical $h={\sum }_{l=0}^k{h}_l{X}^l$ and its reciprocal polynomial $h^{\ast }(X)=X^{k}h(X^{-1})$. Take coefficient vectors, padded to length $N$, ofas the $r$ rows of $H$. Here $h_0=1$ because $h\mid f$, so these rows have successive leading degrees $k,k+1,\dots ,N-1$ and are independent. For a word $a$, row $j$ has dot product ${\sum }_{l=0}^k{h}_{k-l}{a}_{j+l}$, the coefficient of $X^{k+j}$ in the ordinary product $ah$. If $a\in C$, then $ah=bf$ with $\mathrm{deg}b<k$. This product has no terms in degrees $k,\dots ,N-1$, so $H{a}^T=0$. The kernel of $H$ has dimension $N-r=k$, the same as $C$, proving $\ker H=C$. This proves the reciprocal-polynomial parity-check matrix construction and identifies its rows as a basis for the dual of a cyclic code.

Alternatively, a supplied check polynomial of a cyclic code reduced modulo $f$, $\tilde{h}={\sum }_{l=0}^{N-1}{\tilde{h}}_l{X}^l$, gives the polynomial multiplication parity-check matrixThis circulant matrix represents multiplication by $\tilde{h}$ modulo $f$, so its kernel is $C$ and its matrix rank is $r$. Selecting independent rows yields a rank-$r$ parity-check matrix even without initially normalizing the supplied polynomial.

The syndrome $s(y)=H{y}^T$ labels the coset $C+y$. Indeed $s(y)=s(z)$ if and only if $H(y-z{)}^T=0$, equivalently $y-z\in C$. There are $2^r$ cosets, each with $2^k$ words, and the syndrome classification of code cosets gives a bijection between them and ${\mathbb{F}}_2^r$. If $y=c+e$ is a transmitted codeword plus an error, then $s(y)=s(e)$: the syndrome determines the error coset. Choosing a minimum-weight coset leader and subtracting it performs minimum-distance decoding. The error itself need not be uniquely identified, but it is unique when its weight is at most $\lfloor (d-1)/2\rfloor$, since the corresponding error-correction balls are disjoint.

For the repetition code, the nonzero codeword is the all-ones word, soTheir product is $X^N+1$, and the generator polynomial degree $N-1$ gives dimension one. For the single parity-check code, membership is $a(1)=0$, equivalent to divisibility by $X+1$. ThusIts dimension is $N-1$; it is the even-weight code.

Finally, factor the binary length-seven modulus:A standard cyclic realization of the Hamming code of length seven usesIts dimension is four. The reciprocal-check construction givesIts columns are exactly the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$, so no word of weight one or two is in its kernel. The generator itself has weight three, so the minimum Hamming distance is exactly three; this is the $[7,4,3]$ Hamming code. Reversing the cyclic coordinate order gives the equally valid reciprocal choiceThe polynomial answer therefore depends on the cyclic coordinate convention, while the resulting codes are equivalent.

We give the bounds for an alphabet of size $q\ge 2$, including the binary case $q=2$. Let $C$ be a length-$n$ code with $M$ codewords and minimum Hamming distance at least $d$, where $1\le d\le n$. Write $A_q(n,d)$ for the maximum code size at a given distance andfor the number of words in a Hamming ball of radius $t$. The $j$th term chooses the changed coordinates and the $q-1$ alternative symbols in each.

For the Hamming bound, put $t=\lfloor (d-1)/2\rfloor$. Balls of radius $t$ around distinct codewords are disjoint: a common point would, by the triangle inequality, make their distance at most $2t<d$. Counting those balls inside the $q^n$ ambient words provesNo linearity is needed. For a linear code of dimension $k$ over ${\mathbb{F}}_q$, replace $M$ by $q^k$.

For the Gilbert–Varshamov bound, construct a code greedily, adding any word at distance at least $d$ from all previously selected words, until none remains. The process terminates because the space is finite. Its maximality implies that the radius-$(d-1)$ balls around its codewords cover the whole space: an uncovered word could have been added. These balls may overlap, but the size of their union is at most the sum of their sizes. Hence the constructed code has $M{V}_q(n,d-1)\ge q^n$, proving the existence boundOne may take the ceiling on the right because code size is integral.

For completeness, the sharper linear version is the Varshamov bound for linear codes. When $q$ is a prime power and $d\ge 2$, an $[n,k,\ge d]$ linear code exists providedSet $r=n-k$ and choose $n$ columns of an $r\times n$ parity-check matrix in order. When choosing column $l$, exclude all combinations of at most $d-2$ earlier columns, including the zero combination. There are at most ${\sum }_{j=0}^{d-2}\left(\genfrac{}{}{0ex}{}{l-1}{j}\right)(q-1{)}^j$ forbidden vectors, smaller than $q^r$ by the assumed inequality. A column can therefore be chosen. Inductively every set of at most $d-1$ chosen columns is independent: a relation involving the newest one would express it as a combination of at most $d-2$ earlier columns. The kernel has dimension at least $n-r=k$ and minimum Hamming distance at least $d$, since a low-weight kernel vector would be such a column relation. If its dimension is larger than $k$, take a $k$-dimensional subspace. This proves the stated linear existence claim; it does not assume the greedy nonlinear code was linear.

To derive the asymptotic bounds, define the q-ary entropywith the continuous endpoint conventions. Its derivative is ${\log }_q((q-1)(1-x)/x)$, so it is increasing on $[0,1-1/q]$ and has maximum one at $1-1/q$. Stirling's formula gives, uniformly for integer $0\le j\le n$,The sum defining $V_q$ is between its largest summand and $(n+1)$ times that summand. For radius fractions tending to $\rho \le 1-1/q$, monotonicity of $H_q$ makes the largest exponent tend to $H_q(\rho )$. Consequently the Hamming ball volume exponent isFor $\rho >1-1/q$, the exponent is one: use a radius fraction just below $1-1/q$ for a lower bound and $V_q\le q^n$ for an upper bound.

Set $d_n=\max \{1,\lceil \delta n\rceil \}$ and define the asymptotic rate-distance function byThe code rate is $n^{-1}{\log }_{q}M$ and the relative minimum distance is $d/n$. A limsup suffices; no unproved existence of a limit for optimal code sizes is required. The packing radii have fraction tending to $\delta /2$, so the finite Hamming bound and the volume exponent give the asymptotic Hamming boundThe covering radii have fraction tending to $\delta$, giving the asymptotic Gilbert–Varshamov boundFor larger $\delta$, this covering argument gives only the trivial lower bound zero, not the expression obtained by extending the decreasing information entropy function beyond its maximum.

The asymptotic lower bound is also achievable by linear codes over a finite field. For $\delta >0$ and sufficiently large $n$, take redundancy $r_n=\lfloor {\log }_q{V}_q(n-1,d_n-2)\rfloor +1$, so $q^{r_n}>V_q(n-1,d_n-2)$. The linear existence condition produces dimension at least $n-r_n$; its rate has liminf at least $1-H_q(\delta )$. At $\delta =0$, use the whole space, of rate one. In particular, for binary codes the bounds reduce towhere $h_2$ is the binary entropy function.

Use base-two logarithms and put $H=H(U_1)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Zero-probability letters can be omitted. The random variables $I_j=-{\log }_2{p}_{U_j}$ are self-information values, are IID, and have finite mean $H$ because the alphabet is finite. Independence givesFor an arbitrary $\delta >0$, define the typical setThe weak law of large numbers implies $P(T_{n,\delta })\to 1$. Every string in this set satisfiesThis is the asymptotic equipartition property for the given finite IID source, here obtained directly from the weak law of large numbers.

For the upper bound, summing the lower bound on typical-string probabilities yields $|T_{n,\delta }|\le 2^{n(H+\delta )}$. For sufficiently large $n$, its probability is at least $1-\epsilon$, so it is an admissible set in the definition of $M(n,\epsilon )$. HenceFor the lower bound, let $A$ be any admissible set and write ${\eta }_n=P(T_{n,\delta }^c)\to 0$. ThenEach member of this intersection has probability at most $2^{-n(H-\delta )}$. Therefore, for all sufficiently large $n$,This applies in particular to a minimum-size admissible set, giving a liminf at least $H-\delta$. Letting $\delta \downarrow 0$ proves both existence and the value of the minimal high-probability source-set exponent:For a deterministic source, $H=0$ and $M(n,\epsilon )=1$, consistent with the formula.

For coding, label the strings in an admissible set with distinct binary indices of length $\lceil {\log }_{2}M(n,\epsilon )\rceil$. A decoder reconstructs those strings exactly and may fail outside the set. Thus asymptotically $H$ bits per source symbol describe any fixed fraction $1-\epsilon$ of the probability mass. More strongly, every rate $R>H$ permits block codes with error tending to zero: choose $\delta <R-H$, encode the typical strings individually and reserve one index for all other strings. The required number of indices is at most $2^{n(H+\delta )}+1\le 2^{nR}$ for large $n$.

Conversely, a block encoder with at most $2^{nR}$ outputs can reconstruct at most that many distinct input strings correctly. If $R<H$, choose $0<\delta <H-R$. Its success probability is at mostThis gives the strong converse for fixed-rate source coding. It is the operational significance of the information entropy limit for reliable source encoding at a rate. The allowance of a small reconstruction error matters: a fixed-length code that must encode every possible string without error generally needs the larger rate ${\log }_2|\{i:p_i>0\}|$.

Extend $f$ by zero outside $[1,N]\cap \mathbb{Z}$. Here is a dyadic endpoint convention for small Type I and Type II sums. Write $D_M=[M,2M)\cap \mathbb{Z}$, with $M$ a power of two. Type I sums are $\delta$-small if, for every $M\le N^{1/100}$, dyadic $K$ with $MK\le N$, and arbitrary integer intervals $I_m\subset D_K$,Type II sums are $\delta$-small if, for all dyadic $M,K\in [N^{1/100},N^{99/100}]$ and sequences $|a_m|,|b_n|\le 1$,Zero extension handles boxes crossing the endpoint $mn=N$. Fixed choices of open or closed dyadic endpoints do not matter, but interval uniformity and uniformity in both bounded coefficient sequences do matter. These are the estimates used in the Vinogradov Type I–II method.

An interesting technical step is Fourier separation of interval cutoffs. For an integer interval $I_m$, let $\widehat{1_{I_m}}(\theta )={\sum }_{r\in I_m}e(-r\theta )$. Discrete Fourier inversion givesThe exponential geometric sum bound gives a common envelope $H_N(\theta )\ll \min (N,\Vert \theta {\Vert }^{-1})$, with ${\int }_0^1{H}_N\ll \log (2N)$. Divide the interval transform by this envelope: at each frequency it is a bounded coefficient depending on $m$, and $e(n\theta )$ is a bounded coefficient depending on $n$. The Type II sum assumption therefore bounds the interval-cutoff sum by $O(\delta N\log N)$. Choosing the outer unit phases to turn each inner sum into its modulus extends the Type I sum bound to boxes where both variables are in the Type II range.

Take $U=V=\lfloor N^{1/3}\rfloor$. With subscripts denoting truncation of arithmetic functions, the Vaughan identity iswhere $\ast$ now means Dirichlet convolution. For completeness it follows from $\mu \ast 1=ϵ$ and $\Lambda \ast 1=\log$: expand ${\mu }_{>U}\ast {\Lambda }_{>V}\ast 1$, cancel the short terms, and retain $\Lambda$. The short first term contributes $O(N^{1/3}\log N)$ to the sum against $f$.

The next two terms give Type I sums. The logarithmic term has outer coefficient $\mu (m)$, $m\le U$, and inner factor $\log n$, removed by partial summation at a cost $O(\log N)$. In the other term the outer variable is $m=cd\le UV$ with coefficientThis logarithmic coefficient bound in Vaughan identity avoids a loss from a divisor weight. On boxes with short outer variable use the hypothesis directly; on boxes where both variables are at least $N^{1/100}$ use the extended bound proved above. Boxes with inner variable less than $N^{1/100}$ contain at most $O(N^{2/3+1/100})$ pairs in total and are treated trivially. All remaining inner scales are at most $N^{99/100}$ whenever the outer scale exceeds $N^{1/100}$.