Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Bounded channel-tree root-fidelity and information martingales

Open
QAlgorithms.Papers.Independent.Intakethird100.P14.channel_tree_martingales

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let WWW be a binary-input classical–quantum channel with normalized density outputs. On a probability space, let B1,B2,…B_1,B_2,\ldotsB1​,B2​,… be independent fair Bernoulli bits. Let Fn=σ(B1,…,Bn)\mathcal F_n=\sigma(B_1,\ldots,B_n)Fn​=σ(B1​,…,Bn​), with F0\mathcal F_0F0​ trivial. Starting from W0=WW_0=WW0​=W, obtain Wn+1W_{n+1}Wn+1​ from WnW_nWn​ by the bad transform when Bn+1=0B_{n+1}=0Bn+1​=0 and by the good transform when Bn+1=1B_{n+1}=1Bn+1​=1. Equivalently, the first nnn bits select the split-channel index minus one in binary. Put Fn=F(Wn)F_n=\sqrt{F(W_n)}Fn​=F(Wn​)​ and In=I(Wn)I_n=I(W_n)In​=I(Wn​), with information measured in bits. Then

(Fn,Fn)n≥0 is a bounded supermartingale,(In,Fn)n≥0 is a bounded martingale,(F_n,\mathcal F_n)_{n\ge0}\text{ is a bounded supermartingale},\qquad (I_n,\mathcal F_n)_{n\ge0}\text{ is a bounded martingale},(Fn​,Fn​)n≥0​ is a bounded supermartingale,(In​,Fn​)n≥0​ is a bounded martingale, 0≤Fn≤1,0≤In≤1pointwise for every n.0\le F_n\le1,\qquad0\le I_n\le1\quad\text{pointwise for every }n.0≤Fn​≤1,0≤In​≤1pointwise for every n.

Both processes are integrable and the extended information is finite before conversion to a real process. In Lean the IID hypothesis is expressed equivalently by measurable bits and probability 2−n2^{-n}2−n for every length-nnn prefix cylinder. This is the stochastic form of the actual channel recursion, not a statement about freely supplied bounded processes.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P14
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakethird100.P14

open Filter MeasureTheory

open scoped ENNReal NNReal ComplexOrder BigOperators

open QAlgorithms.RealRegisters (Hilbert)

open QAlgorithms.Papers.Independent.Dependency50.P33 (IsDensity)

open QAlgorithms.Papers.Independent.Dependency50.P13 (compression)

open QAlgorithms.Papers.Independent.Renew46.P44 (wordOutput)

attribute [local instance] Classical.propDecidable Classical.decEq

/-- Lemma 11, PDF p.8: actual tree processes, with the filtration generated
by exactly the first n IID fair bits. The finite-history cylinder law is
equivalent to independence and Bernoulli(1/2) marginals. Corrects the prose
B_n to B_(n+1) after time n and the displayed missing root in the F_n law.
Finiteness, pointwise [0,1] bounds and integrability are conclusions. -/
theorem channel_tree_martingales {I Omega : Type} [MeasurableSpace Omega]
    (mu : Measure Omega) [IsProbabilityMeasure mu]
    (W : Bit → OutputCoefficients I) (hW : IsBinaryCqChannel W) (B : ℕ → Omega → Bool)
    (hB : ∀ k, Measurable (B k))
    (hfair : ∀ n (h : Fin n → Bool),
      mu {w | ∀ k : Fin n, B k.val w = h k} = (1 / 2 : ℝ≥0∞) ^ n) :
    (∀ n w, symmetricInformation (splitChannel W n (branchIndex B n w)) ≠ ⊤) ∧
    (∀ n w, 0 ≤ fidelityProcess W B n w ∧ fidelityProcess W B n w ≤ 1 ∧
      0 ≤ informationProcess W B n w ∧ informationProcess W B n w ≤ 1) ∧
    (∀ n, Integrable (informationProcess W B n) mu) ∧
    Supermartingale (fidelityProcess W B) (bitFiltration B hB) mu ∧
    Martingale (informationProcess W B) (bitFiltration B hB) mu := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P14

end
Source
Polar codes for classical-quantum channels, arXiv:1109.2591v3, PDF p. 8, Lemma 11: bounded fidelity supermartingale and information martingale
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

Let III be any type, let (Ω,M,μ)(\Omega,\mathcal M,\mu)(Ω,M,μ) be any probability space, and let WbW_bWb​, b∈F2b\in\mathbb F_2b∈F2​, be density coefficient arrays: each admits Wb(i,j)=∑rur(i)vr(j)‾W_b(i,j)=\sum_r u_r(i)\overline{v_r(j)}Wb​(i,j)=∑r​ur​(i)vr​(j)​ with ur,vr∈ℓ2(I;C)u_r,v_r\in\ell^2(I;\mathbb C)ur​,vr​∈ℓ2(I;C), ∑r∥ur∥∥vr∥<∞\sum_r\|u_r\|\|v_r\|<\infty∑r​∥ur​∥∥vr​∥<∞, real nonnegative finite quadratic forms, and summable real diagonal of sum 111. Let Bk:Ω→{0,1}B_k:\Omega\to\{0,1\}Bk​:Ω→{0,1} be measurable for every k≥0k\ge0k≥0, and assume that for every n≥0n\ge0n≥0 and every h∈{0,1}nh\in\{0,1\}^nh∈{0,1}n,

μ{ω:Bk(ω)=hk for all k<n}=2−n.\mu\{\omega:B_k(\omega)=h_k\text{ for all }k<n\}=2^{-n}.μ{ω:Bk​(ω)=hk​ for all k<n}=2−n.

For an array XXX, let O(X)O(X)O(X) be a chosen bounded operator having coefficients XXX, or 000 if none exists; let R(T)R(T)R(T) be a chosen positive bounded square root, or 000 if none exists; and put tr⁡bT=∑j(Tej)j\operatorname{tr}_bT=\sum_j(Te_j)_jtrb​T=∑j​(Tej​)j​, the total infinite sum. Define F(V)=[Re⁡tr⁡bR(R(O(V0))O(V1)R(O(V0)))]2F(V)=[\operatorname{Re}\operatorname{tr}_bR(R(O(V_0))O(V_1)R(O(V_0)))]^2F(V)=[Retrb​R(R(O(V0​))O(V1​)R(O(V0​)))]2. Define D2(X∣Y)D_2(X\mid Y)D2​(X∣Y) as the supremum over all finite orthonormal families vvv, including the empty family, of +∞+\infty+∞ if ker⁡Yv⊈ker⁡Xv\ker Y_v\not\subseteq\ker X_vkerYv​⊆kerXv​, and otherwise of max⁡(0,Re⁡Tr⁡(f(Xv)−Xvlog⁡Yv−Xv+Yv)/log⁡2)\max(0,\operatorname{Re}\operatorname{Tr}(f(X_v)-X_v\log Y_v-X_v+Y_v)/\log2)max(0,ReTr(f(Xv​)−Xv​logYv​−Xv​+Yv​)/log2), where Xv=(⟨vr,O(X)vs⟩)X_v=(\langle v_r,O(X)v_s\rangle)Xv​=(⟨vr​,O(X)vs​⟩), Yv=(⟨vr,O(Y)vs⟩)Y_v=(\langle v_r,O(Y)v_s\rangle)Yv​=(⟨vr​,O(Y)vs​⟩), f(t)=tlog⁡tf(t)=t\log tf(t)=tlogt, and matrix functions use continuous functional calculus; set J(V)=12[D2(V0∣(V0+V1)/2)+D2(V1∣(V0+V1)/2)]J(V)=\tfrac12[D_2(V_0\mid(V_0+V_1)/2)+D_2(V_1\mid(V_0+V_1)/2)]J(V)=21​[D2​(V0​∣(V0​+V1​)/2)+D2​(V1​∣(V0​+V1​)/2)]. For each nnn, put N=2nN=2^nN=2n, encode u∈F2Nu\in\mathbb F_2^Nu∈F2N​ by xc=∑rurGn(r,c)x_c=\sum_r u_rG_n(r,c)xc​=∑r​ur​Gn​(r,c), where Gn(r,c)=∏k<nκ(bit⁡k(rev⁡nr),bit⁡k(c))G_n(r,c)=\prod_{k<n}\kappa(\operatorname{bit}_k(\operatorname{rev}_n r),\operatorname{bit}_k(c))Gn​(r,c)=∏k<n​κ(bitk​(revn​r),bitk​(c)), κ(a,0)=1, κ(a,1)=a\kappa(a,0)=1,\ \kappa(a,1)=aκ(a,0)=1, κ(a,1)=a, and rev⁡n\operatorname{rev}_nrevn​ reverses nnn bits. Write Vu(y,z)=∏c<NWxc(yc,zc)V_u(y,z)=\prod_{c<N}W_{x_c}(y_c,z_c)Vu​(y,z)=∏c<N​Wxc​​(yc​,zc​); let Tn,i,h,bT_{n,i,h,b}Tn,i,h,b​ be its uniform average over full NNN-bit words used to fill coordinates after a fixed prefix hhh and bit bbb at iii; and set Wn,ib((h,y),(h′,z))=1h=h′2−iTn,i,h,b(y,z)W_{n,i}^b((h,y),(h',z))=\mathbf1_{h=h'}2^{-i}T_{n,i,h,b}(y,z)Wn,ib​((h,y),(h′,z))=1h=h′​2−iTn,i,h,b​(y,z). Let

in(ω)=(∑k<nBk(ω)2n−1−k) mod 2n,Zn(ω)=F(Wn,in(ω)),Jn(ω)=J(Wn,in(ω))R,i_n(\omega)=\left(\sum_{k<n}B_k(\omega)2^{n-1-k}\right)\bmod2^n,\qquad Z_n(\omega)=\sqrt{F(W_{n,i_n(\omega)})},\qquad J_n(\omega)=J(W_{n,i_n(\omega)})_{\mathbb R},in​(ω)=(k<n∑​Bk​(ω)2n−1−k)mod2n,Zn​(ω)=F(Wn,in​(ω)​)​,Jn​(ω)=J(Wn,in​(ω)​)R​,

where the conversion to a real number sends +∞+\infty+∞ to 000. Let Fn\mathcal F_nFn​ be the sigma-algebra generated by B0,…,Bn−1B_0,\ldots,B_{n-1}B0​,…,Bn−1​, so F0\mathcal F_0F0​ is the bottom sigma-algebra. Then J(Wn,in(ω))≠+∞J(W_{n,i_n(\omega)})\ne+\inftyJ(Wn,in​(ω)​)=+∞ for every n,ωn,\omegan,ω, and 0≤Zn(ω)≤10\le Z_n(\omega)\le10≤Zn​(ω)≤1 and 0≤Jn(ω)≤10\le J_n(\omega)\le10≤Jn​(ω)≤1 for every n,ωn,\omegan,ω; every JnJ_nJn​ is integrable; ZnZ_nZn​ is a supermartingale with respect to (Fn)(\mathcal F_n)(Fn​) and μ\muμ; and JnJ_nJn​ is a martingale with respect to the same filtration and measure. Thus the processes are adapted and integrable, with E[Zm∣Fn]≤Zn\mathbb E[Z_m\mid\mathcal F_n]\le Z_nE[Zm​∣Fn​]≤Zn​ almost everywhere and E[Jm∣Fn]=Jn\mathbb E[J_m\mid\mathcal F_n]=J_nE[Jm​∣Fn​]=Jn​ almost everywhere whenever n≤mn\le mn≤m; the displayed bounds and finiteness conclusion are pointwise, including at n=0n=0n=0.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me