Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Bayesian Shannon-code evidence rate

Open
QAlgorithms.Papers.Independent.Intakethird100.P80.compression_limit85

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

prove2quantum

Fix the quantum experiment, setting law, iid trials, and continuous uniformly positive normalized local-theory prior of the Bayesian limit. Let mnm_nmn​ be the actual Bayesian marginal likelihood. On its positive-probability support, use the Shannon binary code obtained by sorting words by decreasing mnm_nmn​ probability, breaking ties by a fixed finite enumeration, and taking the first ⌈−log⁡2mn(zn)⌉\lceil-\log_2m_n(z^n)\rceil⌈−log2​mn​(zn)⌉ binary digits of the cumulative probability. The resulting words form a prefix code and have lengths LnL_nLn​ satisfying

−log⁡2mn(zn)≤Ln(zn)<−log⁡2mn(zn)+1.-\log_2m_n(z^n)\le L_n(z^n)<-\log_2m_n(z^n)+1.−log2​mn​(zn)≤Ln​(zn)<−log2​mn​(zn)+1.

The iid law is a probability measure, the prior is integrable, and u(σ)=inf⁡πD2(Qσ∥Pσ;π)u(\sigma)=\inf_\pi D_2(Q_\sigma\|P_{\sigma;\pi})u(σ)=infπ​D2​(Qσ​∥Pσ;π​) is finite. Almost surely every observed word has positive quantum and Bayesian likelihood, and

Ln(Zn)−[−log⁡2Qσ(Zn)]n⟶u(σ).\frac{L_n(Z^n)-[-\log_2 Q_\sigma(Z^n)]}{n}\longrightarrow u(\sigma).nLn​(Zn)−[−log2​Qσ​(Zn)]​⟶u(σ).

This gives the information-theoretic evidence rate (53), (85) for an actual support-restricted code; impossible words are excluded from its coding alphabet.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P80
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakethird100.P80

open scoped BigOperators ENNReal Topology Classical

open MeasureTheory Filter

section ProbabilityCoding

/-- PDF pp.27,29,31, (53),(85): the explicit support-restricted Bayesian/Shannon code.
Its words have the source's ceiling lengths, and its excess over ideal Q length has the KL rate.
This is normalized convergence, not the invalid pathwise O(log n) claim in (46). -/
theorem compression_limit85 {S : BellExperiment} (Q : Table S) (hQ : NonlocalityProof Q)
    (s : Sigma S) (w : (Potential S → ℝ) → ℝ) (hw : AdmissiblePrior w) :
    Integrable w (simplexVolume S) ∧ iidLaw Q s.1 Set.univ = 1 ∧ lowerValue Q s.1 < ⊤ ∧
    (∀ n, IsPrefixCode (fun z : {z : Fin n → BellTrial S // 0 < bayesMarginal s.1 w z} =>
      shannonWord (fun t : Fin n → BellTrial S => bayesMarginal s.1 w t) z.1)) ∧
    (∀ n (z : Fin n → BellTrial S), 0 < bayesMarginal s.1 w z →
      let L := ((shannonWord (fun t : Fin n → BellTrial S => bayesMarginal s.1 w t) z).length : ℝ);
      -Real.logb 2 (bayesMarginal s.1 w z) ≤ L ∧ L < -Real.logb 2 (bayesMarginal s.1 w z) + 1) ∧
    ∀ᵐ z ∂iidLaw Q s.1,
      (∀ n, 0 < sampleLikelihood (trialJointLaw Q s.1) (initialTrials z n) ∧
        0 < bayesMarginal s.1 w (initialTrials z n)) ∧
      Tendsto (fun n : ℕ =>
        (((shannonWord (fun t : Fin n → BellTrial S => bayesMarginal s.1 w t)
          (initialTrials z n)).length : ℝ) + Real.logb 2 (sampleLikelihood (trialJointLaw Q s.1) (initialTrials z n))) / n)
        atTop (𝓝 (lowerValue Q s.1).toReal) := by sorry

end ProbabilityCoding

end QAlgorithms.Papers.Independent.Intakethird100.P80

end
Source
The statistical strength of nonlocality proofs, arXiv:quant-ph/0307125v2, PDF p. 27, Appendix IV-F: Bayesian/Shannon code evidence rate
Read-back

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

Let SSS consist of a positive finite number of parties, positive finite numbers of settings for each party, and positive finite numbers of outcomes at each party and setting. Write AAA for its joint settings, XaX_aXa​ for its joint outcomes at setting aaa, VVV for the finite set of assignments prescribing an outcome at every setting of every party, and v∣av|_av∣a​ for the prescribed joint outcome at aaa. Let Q(a,x)Q(a,x)Q(a,x) be a real table such that each Q(a,⋅)Q(a,\cdot)Q(a,⋅) is nonnegative and sums to 111; for every subset JJJ of parties, settings a,ba,ba,b agreeing on JJJ, and v∈Vv\in Vv∈V, the sum of Q(a,x)Q(a,x)Q(a,x) over xi=vi(ai)x_i=v_i(a_i)xi​=vi​(ai​) for all i∈Ji\in Ji∈J equals the corresponding sum of Q(b,x)Q(b,x)Q(b,x) over xi=vi(bi)x_i=v_i(b_i)xi​=vi​(bi​); and there exist positive local dimensions did_idi​, a positive semidefinite joint matrix ρ\rhoρ of trace 111, and positive semidefinite local matrices Mi,ai,xiM_{i,a_i,x_i}Mi,ai​,xi​​, summing to the identity over xix_ixi​, such that Q(a,x)=Re⁡tr⁡(Ea,xρ)Q(a,x)=\operatorname{Re}\operatorname{tr}(E_{a,x}\rho)Q(a,x)=Retr(Ea,x​ρ), with Ea,x(u,v)=∏iMi,ai,xi(ui,vi)E_{a,x}(u,v)=\prod_iM_{i,a_i,x_i}(u_i,v_i)Ea,x​(u,v)=∏i​Mi,ai​,xi​​(ui​,vi​). Let sss be any nonnegative distribution of total mass 111 on AAA, including distributions with zero coordinates. For a distribution p∈P(V)p\in\mathcal P(V)p∈P(V), define Pp(a,x)=∑v: v∣a=xp(v)P_p(a,x)=\sum_{v:\,v|_a=x}p(v)Pp​(a,x)=∑v:v∣a​=x​p(v), and define trial laws on B={(a,x):a∈A, x∈Xa}B=\{(a,x):a\in A,\ x\in X_a\}B={(a,x):a∈A, x∈Xa​} by q(a,x)=s(a)Q(a,x)q(a,x)=s(a)Q(a,x)q(a,x)=s(a)Q(a,x) and rp(a,x)=s(a)Pp(a,x)r_p(a,x)=s(a)P_p(a,x)rp​(a,x)=s(a)Pp​(a,x). Define D(q∥r)=+∞D(q\|r)=+\inftyD(q∥r)=+∞ if some trial has q>0q>0q>0 and r=0r=0r=0, and otherwise define it as the extended nonnegative real corresponding to max⁡{0,∑b:q(b)≠0q(b)log⁡2(q(b)/r(b))}\max\{0,\sum_{b:q(b)\ne0}q(b)\log_2(q(b)/r(b))\}max{0,∑b:q(b)=0​q(b)log2​(q(b)/r(b))}; put Δ=inf⁡p∈P(V)D(q∥rp)\Delta=\inf_{p\in\mathcal P(V)}D(q\|r_p)Δ=infp∈P(V)​D(q∥rp​). Let ν\nuν be Hausdorff measure of dimension ∣V∣−1|V|-1∣V∣−1, restricted to P(V)\mathcal P(V)P(V), and let w:RV→Rw:\mathbb R^V\to\mathbb Rw:RV→R be continuous on that simplex, satisfy c<w(p)c<w(p)c<w(p) throughout it for some real c>0c>0c>0, and have ∫w dν=1\int w\,d\nu=1∫wdν=1. For each length-nnn trial sample ttt, put Lq(t)=∏iq(ti)L_q(t)=\prod_iq(t_i)Lq​(t)=∏i​q(ti​) and mn(t)=∫w(p)∏irp(ti) dν(p)m_n(t)=\int w(p)\prod_i r_p(t_i)\,d\nu(p)mn​(t)=∫w(p)∏i​rp​(ti​)dν(p). Using the finite enumeration ene_nen​ supplied on the length-nnn sample space, define

cn(t)=∑umn(t)<mn(u) or (mn(u)=mn(t) and en(u)<en(t))mn(u),ℓn(t)=⌈−log⁡2mn(t)⌉+,c_n(t)= \sum_{\substack{u\\ m_n(t)<m_n(u)\ \text{or}\ (m_n(u)=m_n(t)\ \text{and}\ e_n(u)<e_n(t))}} m_n(u),\qquad \ell_n(t)=\left\lceil-\log_2m_n(t)\right\rceil_+,cn​(t)=umn​(t)<mn​(u) or (mn​(u)=mn​(t) and en​(u)<en​(t))​∑​mn​(u),ℓn​(t)=⌈−log2​mn​(t)⌉+​,

and let Wn(t)W_n(t)Wn​(t) be the Boolean word of length ℓn(t)\ell_n(t)ℓn​(t) whose entry at index jjj is true exactly when ⌊2j+1cn(t)⌋+ mod 2=1\lfloor2^{j+1}c_n(t)\rfloor_+\bmod2=1⌊2j+1cn​(t)⌋+​mod2=1; natural-number floor and ceiling are truncated at zero, and the total logarithm has log⁡20=0\log_2 0=0log2​0=0. Let Pq\mathbb P_qPq​ be the infinite product of the trial measure ∑b∈Bmax⁡{q(b),0}δb\sum_{b\in B}\max\{q(b),0\}\delta_b∑b∈B​max{q(b),0}δb​. The conclusion is that www is integrable with respect to ν\nuν, Pq\mathbb P_qPq​ has total mass 111, Δ<+∞\Delta<+\inftyΔ<+∞, and, for every nnn, WnW_nWn​ restricted to samples with mn(t)>0m_n(t)>0mn​(t)>0 is prefix-free, meaning that a prefix relation between two such words implies equality of their samples. Moreover, for every nnn and every sample ttt with mn(t)>0m_n(t)>0mn​(t)>0,

−log⁡2mn(t)≤∣Wn(t)∣<−log⁡2mn(t)+1.-\log_2m_n(t)\le |W_n(t)|<-\log_2m_n(t)+1.−log2​mn​(t)≤∣Wn​(t)∣<−log2​mn​(t)+1.

Finally, for Pq\mathbb P_qPq​-almost every infinite sequence zzz,

(∀n∈N, Lq(z<n)>0 and mn(z<n)>0)andlim⁡n→∞∣Wn(z<n)∣+log⁡2Lq(z<n)n=ΔR,\bigl(\forall n\in\mathbb N,\ L_q(z_{<n})>0\ \text{and}\ m_n(z_{<n})>0\bigr) \quad\text{and}\quad \lim_{n\to\infty} \frac{|W_n(z_{<n})|+\log_2L_q(z_{<n})}{n} =\Delta_{\mathbb R},(∀n∈N, Lq​(z<n​)>0 and mn​(z<n​)>0)andn→∞lim​n∣Wn​(z<n​)∣+log2​Lq​(z<n​)​=ΔR​,

where z<n=(z0,…,zn−1)z_{<n}=(z_0,\ldots,z_{n-1})z<n​=(z0​,…,zn−1​) and ΔR\Delta_{\mathbb R}ΔR​ is the real value of the finite number Δ\DeltaΔ. All universal claims about nnn include n=0n=0n=0: its likelihood and marginal are 111, its word is empty, and the quotient's term at n=0n=0n=0 is 000 under total real division.

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