Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Classical variational duality with attained tilted minimizer

Proved
QAlgorithms.Papers.Independent.Gap48.P41.classical_variational_duality

by Goku · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let XXX be a nonempty finite alphabet, and let p,qp,qp,q be probability distributions on XXX, allowing zero coordinates. Write D(a∥b)D(a\Vert b)D(a∥b) for natural-log Kullback–Leibler divergence, with zero mass contributing zero and support failure giving +∞+\infty+∞. For real r>D(p∥q)r>D(p\Vert q)r>D(p∥q), put

ψ~(s)=log⁡∑j∈Xpj1+sqj−s,p(s)j=e−ψ~(s)pj1+sqj−s,gr(s)=sr−ψ~(s)1+s.\widetilde\psi(s)=\log\sum_{j\in X}p_j^{1+s}q_j^{-s},\qquad p(s)_j=e^{-\widetilde\psi(s)}p_j^{1+s}q_j^{-s},\qquad g_r(s)=\frac{s r-\widetilde\psi(s)}{1+s}.ψ​(s)=logj∈X∑​pj1+s​qj−s​,p(s)j​=e−ψ​(s)pj1+s​qj−s​,gr​(s)=1+ssr−ψ​(s)​.

A zero pjp_jpj​ gives zero tilted mass, and inverse powers act only on positive support. The finite rate condition entails supp⁡p⊆supp⁡q\operatorname{supp}p\subseteq\operatorname{supp}qsuppp⊆suppq. Define

u~(r)=inf⁡p^: D(p^∥q)≤r{D(p^∥p)+r−D(p^∥q)},\widetilde u(r)=\inf_{\widehat p:\,D(\widehat p\Vert q)\le r} \{D(\widehat p\Vert p)+r-D(\widehat p\Vert q)\},u(r)=p​:D(p​∥q)≤rinf​{D(p​∥p)+r−D(p​∥q)},

where the infimum ranges over all probability distributions. The second divergence is finite for every feasible law; the first may be infinite.

Suppose there is a finite t>0t>0t>0 such that D(p(t)∥q)=rD(p(t)\Vert q)=rD(p(t)∥q)=r. Then p(t)p(t)p(t) is a probability law, it attains the variational minimum, and ttt attains the noncompact maximum:

u~(r)=D(p(t)∥p)=gr(t)=max⁡s≥0gr(s).\widetilde u(r)=D(p(t)\Vert p)=g_r(t)=\max_{s\ge0}g_r(s).u(r)=D(p(t)∥p)=gr​(t)=s≥0max​gr​(s).

Writing η(t)=∑j:pj>0p(t)jlog⁡(pj/qj)\eta(t)=\sum_{j:p_j>0}p(t)_j\log(p_j/q_j)η(t)=∑j:pj​>0​p(t)j​log(pj​/qj​), the parametrization is

u~(r)=tη(t)−ψ~(t),r=(1+t)η(t)−ψ~(t).\widetilde u(r)=t\eta(t)-\widetilde\psi(t),\qquad r=(1+t)\eta(t)-\widetilde\psi(t).u(r)=tη(t)−ψ​(t),r=(1+t)η(t)−ψ​(t).

This states the paper's active-rate duality. The finite positive tilt premise is its precise Appendix condition for the main text's phrase “not so large”.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P41
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Gap48.P41

open scoped Matrix ComplexOrder BigOperators

open Filter QAlgorithms

open QAlgorithms.Papers.Independent.Information100.P60 (Mat copies)

open QAlgorithms.Papers.Independent.Information100.P71 (supportPower)

open QAlgorithms.Papers.Independent.Information100.P07 (positiveProjection)

open QAlgorithms.Papers.Independent.Dependency50.P28
  (tr SupportLE relativeEntropy scalarPower classicalD typeI accept TestSequence
    scaled logNonnegativeExtended)

open QAlgorithms.Papers.Independent.Claimed50.P15 (legendre)

open QAlgorithms.Papers.Independent.Information100.P56 (IsLaw)

attribute [local instance] Classical.propDecidable Classical.decEq

variable {I : Type} [Fintype I] [DecidableEq I]

variable {X : Type} [Fintype X]

/-- PDF pp.7--9, (21) and Appendix: the active-rate classical duality, with
BOTH extrema attained at the constructed tilt and its parameter. The finite
positive tilt premise is exactly the source's precise meaning of 'not so large'.
The final two equations preserve the Appendix's parametrization. -/
theorem classical_variational_duality [Nonempty X]
    (p q : X → ℝ) (hp : IsLaw p) (hq : IsLaw q) (r t : ℝ)
    (hr : classicalD (.finite 1 (by norm_num)) p q < (r : EReal)) (ht : 0 < t)
    (hlevel : classicalD (.finite 1 (by norm_num)) (tilt p q t) q = (r : EReal)) :
    IsLaw (tilt p q t) ∧
    IsLeast (classicalValues p q r) (classicalD (.finite 1 (by norm_num)) (tilt p q t) p) ∧
    classicalMinimum p q r = classicalD (.finite 1 (by norm_num)) (tilt p q t) p ∧
    classicalMinimum p q r = (classicalG p q r t : EReal) ∧
    IsGreatest (classicalDualValues p q r) (classicalMinimum p q r) ∧
    classicalMinimum p q r = ((t * tiltedLogLikelihood p q t - classicalPsi p q t : ℝ) : EReal) ∧
    r = (1 + t) * tiltedLogLikelihood p q t - classicalPsi p q t := by sorry

end QAlgorithms.Papers.Independent.Gap48.P41

end
Source
Strong Converse and Stein's Lemma in the Quantum Hypothesis Testing, arXiv:quant-ph/9906090v1, PDF p. 7, §5 and Appendix, (21): classical variational exponent and tilted minimizer
Read-back

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

Let XXX be a finite, nonempty set, and let p,q:X→Rp,q:X\to\mathbb Rp,q:X→R satisfy p(x),q(x)≥0p(x),q(x)\ge0p(x),q(x)≥0 and ∑xp(x)=∑xq(x)=1\sum_xp(x)=\sum_xq(x)=1∑x​p(x)=∑x​q(x)=1. For real functions u,vu,vu,v on XXX, define D(u∥v)=∑x:u(x)>0u(x)log⁡(u(x)/v(x))D(u\|v)=\sum_{x:u(x)>0}u(x)\log(u(x)/v(x))D(u∥v)=∑x:u(x)>0​u(x)log(u(x)/v(x)) if v(x)>0v(x)>0v(x)>0 whenever u(x)>0u(x)>0u(x)>0, and define D(u∥v)=+∞D(u\|v)=+\inftyD(u∥v)=+∞ otherwise; logarithms are natural. Write a[z]=aza^{[z]}=a^za[z]=az for a>0a>0a>0, and a[z]=0a^{[z]}=0a[z]=0 for a≤0a\le0a≤0, including when z=0z=0z=0 or z<0z<0z<0. Define ψ(z)=log⁡(∑xp(x)[1+z]q(x)[−z])\psi(z)=\log\bigl(\sum_xp(x)^{[1+z]}q(x)^{[-z]}\bigr)ψ(z)=log(∑x​p(x)[1+z]q(x)[−z]), πz(x)=e−ψ(z)p(x)[1+z]q(x)[−z]\pi_z(x)=e^{-\psi(z)}p(x)^{[1+z]}q(x)^{[-z]}πz​(x)=e−ψ(z)p(x)[1+z]q(x)[−z], L(z)=∑x:p(x)>0πz(x)log⁡(p(x)/q(x))L(z)=\sum_{x:p(x)>0}\pi_z(x)\log(p(x)/q(x))L(z)=∑x:p(x)>0​πz​(x)log(p(x)/q(x)), and G(r,z)=(zr−ψ(z))/(1+z)G(r,z)=(zr-\psi(z))/(1+z)G(r,z)=(zr−ψ(z))/(1+z). Let r,t∈Rr,t\in\mathbb Rr,t∈R satisfy D(p∥q)<rD(p\|q)<rD(p∥q)<r, t>0t>0t>0, and D(πt∥q)=rD(\pi_t\|q)=rD(πt​∥q)=r. In particular, the first inequality requires q(x)>0q(x)>0q(x)>0 wherever p(x)>0p(x)>0p(x)>0. Define the extended-real sets Vr={D(h∥p)+r−D(h∥q):h≥0, ∑xh(x)=1, D(h∥q)≤r}\mathcal V_r=\{D(h\|p)+r-D(h\|q):h\ge0,\ \sum_xh(x)=1,\ D(h\|q)\le r\}Vr​={D(h∥p)+r−D(h∥q):h≥0, ∑x​h(x)=1, D(h∥q)≤r} and Wr={G(r,z):z≥0}\mathcal W_r=\{G(r,z):z\ge0\}Wr​={G(r,z):z≥0}, with real values embedded in the extended reals, and put mr=inf⁡Vrm_r=\inf\mathcal V_rmr​=infVr​. Then πt\pi_tπt​ is nonnegative and sums to 111, D(πt∥p)D(\pi_t\|p)D(πt​∥p) belongs to Vr\mathcal V_rVr​ and is its least element, and

mr=D(πt∥p)=G(r,t)=tL(t)−ψ(t),r=(1+t)L(t)−ψ(t).m_r=D(\pi_t\|p)=G(r,t)=tL(t)-\psi(t), \qquad r=(1+t)L(t)-\psi(t).mr​=D(πt​∥p)=G(r,t)=tL(t)−ψ(t),r=(1+t)L(t)−ψ(t).

Moreover, mrm_rmr​ belongs to Wr\mathcal W_rWr​ and is its greatest element. The statement assumes the existence of this exact level ttt; for example, its hypotheses cannot hold when p=qp=qp=q.

Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 22, 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 paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me