Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in

Get started

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

Functional Analysis

232 missions · 139 completed

Missions

Open93Completed139All232
🏆Completed
AnalysisMathematical Physics·Captain: mikedeng1

Mathematical Methods in Quantum Mechanics X: The Uncertainty Principle and the Harmonic OscillatorTextbook

Motivation

The quantum harmonic oscillator is the Schrödinger operator of a particle in a quadratic potential. It describes small vibrations around an equilibrium, the modes of the electromagnetic field, and phonons in a crystal. It is also one of the very few Schrödinger operators whose spectrum and eigenfunctions are known in closed form. The eigenvalues are equally spaced, and the eigenfunctions are Hermite functions. Its algebraic treatment by creation and annihilation operators goes back to Dirac (The Principles of Quantum Mechanics, 1930). That treatment became the template for second quantization and Fock space.

The same chapter of G. Teschl's Mathematical Methods in Quantum Mechanics (AMS Graduate Studies in Mathematics 99, 2009, Chapter 8, AMS page) contains two further results that use commutation relations. The first is the Heisenberg uncertainty principle (Heisenberg 1927; the general form for two observables is due to Robertson, Phys. Rev. 34 (1929)). The second is an abstract statement that A∗AA^*AA∗A and AA∗AA^*AA∗ have the same spectrum away from 000. Physicists call this supersymmetric quantum mechanics, and Teschl uses it later for the hydrogen atom. This mission follows Teschl's Sections 8.1–8.4.

Setting

Let H\mathfrak HH be a complex Hilbert space. A linear operator AAA is a linear map defined on a subspace D(A)⊆H\mathfrak D(A) \subseteq \mathfrak HD(A)⊆H, its domain. AAA is symmetric if D(A)\mathfrak D(A)D(A) is dense and ⟨φ,Aψ⟩=⟨Aφ,ψ⟩\langle \varphi, A\psi\rangle = \langle A\varphi, \psi\rangle⟨φ,Aψ⟩=⟨Aφ,ψ⟩ for all φ,ψ∈D(A)\varphi, \psi \in \mathfrak D(A)φ,ψ∈D(A). For a closed operator AAA and z∈Cz \in \mathbb Cz∈C, the resolvent RA(z)=(A−z)−1R_A(z) = (A - z)^{-1}RA​(z)=(A−z)−1 exists when A−zA - zA−z maps D(A)\mathfrak D(A)D(A) bijectively onto H\mathfrak HH with a bounded inverse. The resolvent set ρ(A)\rho(A)ρ(A) is the set of such zzz, and the spectrum is σ(A)=C∖ρ(A)\sigma(A) = \mathbb C \setminus \rho(A)σ(A)=C∖ρ(A). An operator is essentially self-adjoint on its domain if its closure A‾\overline AA is self-adjoint.

For ψ∈D(A)\psi \in \mathfrak D(A)ψ∈D(A) with ∥ψ∥=1\|\psi\| = 1∥ψ∥=1 (a state), the expectation is Eψ(A)=⟨ψ,Aψ⟩\mathbb E_\psi(A) = \langle\psi, A\psi\rangleEψ​(A)=⟨ψ,Aψ⟩ and the mean-square deviation is Δψ(A)=∥(A−Eψ(A))ψ∥\Delta_\psi(A) = \|(A - \mathbb E_\psi(A))\psi\|Δψ​(A)=∥(A−Eψ​(A))ψ∥. The commutator is [A,B]ψ=ABψ−BAψ[A,B]\psi = AB\psi - BA\psi[A,B]ψ=ABψ−BAψ for ψ∈D(AB)∩D(BA)\psi \in \mathfrak D(AB) \cap \mathfrak D(BA)ψ∈D(AB)∩D(BA), where D(AB)={ψ∈D(B)∣Bψ∈D(A)}\mathfrak D(AB) = \{\psi \in \mathfrak D(B) \mid B\psi \in \mathfrak D(A)\}D(AB)={ψ∈D(B)∣Bψ∈D(A)}.

Fix a frequency ω>0\omega > 0ω>0. On R3\mathbb R^3R3 with Lebesgue measure, let

Dω=span⁡{xαe−ω∣x∣2/2∣α∈N03}⊆L2(R3),\mathfrak D_\omega = \operatorname{span}\{x^\alpha e^{-\omega|x|^2/2} \mid \alpha \in \mathbb N_0^3\} \subseteq L^2(\mathbb R^3),Dω​=span{xαe−ω∣x∣2/2∣α∈N03​}⊆L2(R3),

where xα=x1α1x2α2x3α3x^\alpha = x_1^{\alpha_1}x_2^{\alpha_2}x_3^{\alpha_3}xα=x1α1​​x2α2​​x3α3​​ and ∣x∣|x|∣x∣ is the Euclidean norm. With Δ=∑j∂2/∂xj2\Delta = \sum_j \partial^2/\partial x_j^2Δ=∑j​∂2/∂xj2​ and Teschl's units (ℏ=1\hbar = 1ℏ=1, mass 1/21/21/2, so the free Hamiltonian is H0=−ΔH_0 = -\DeltaH0​=−Δ), the harmonic oscillator is the operator

H=H0+ω2x2,(Hf)(x)=−Δf(x)+ω2∣x∣2f(x),D(H)=Dω.H = H_0 + \omega^2 x^2, \qquad (Hf)(x) = -\Delta f(x) + \omega^2|x|^2 f(x), \qquad \mathfrak D(H) = \mathfrak D_\omega.H=H0​+ω2x2,(Hf)(x)=−Δf(x)+ω2∣x∣2f(x),D(H)=Dω​.

In one dimension the ladder operators on span⁡{xke−ωx2/2}\operatorname{span}\{x^k e^{-\omega x^2/2}\}span{xke−ωx2/2} are

A±=12(ω x∓1ωddx).A_\pm = \frac{1}{\sqrt2}\Big(\sqrt\omega\,x \mp \frac{1}{\sqrt\omega}\frac{d}{dx}\Big).A±​=2​1​(ω​x∓ω​1​dxd​).

The Hermite polynomials are Hn(x)=(−1)nex2dndxne−x2H_n(x) = (-1)^n e^{x^2}\frac{d^n}{dx^n}e^{-x^2}Hn​(x)=(−1)nex2dxndn​e−x2. The Hermite functions are

ψn(x)=12nn!(ωπ)1/4Hn(ω x) e−ωx2/2,\psi_n(x) = \frac{1}{\sqrt{2^n n!}}\Big(\frac\omega\pi\Big)^{1/4} H_n(\sqrt\omega\,x)\,e^{-\omega x^2/2},ψn​(x)=2nn!​1​(πω​)1/4Hn​(ω​x)e−ωx2/2,

and on R3\mathbb R^3R3, ψn1,n2,n3(x)=ψn1(x1)ψn2(x2)ψn3(x3)\psi_{n_1,n_2,n_3}(x) = \psi_{n_1}(x_1)\psi_{n_2}(x_2)\psi_{n_3}(x_3)ψn1​,n2​,n3​​(x)=ψn1​​(x1​)ψn2​​(x2​)ψn3​​(x3​).

Formalization targets

Goal: the harmonic oscillator (Theorem 8.5)

For every ω>0\omega > 0ω>0 the operator HHH above exists. It is essentially self-adjoint on Dω\mathfrak D_\omegaDω​, the functions ψn1,n2,n3\psi_{n_1,n_2,n_3}ψn1​,n2​,n3​​, (n1,n2,n3)∈N03(n_1,n_2,n_3) \in \mathbb N_0^3(n1​,n2​,n3​)∈N03​, form an orthonormal basis of L2(R3)L^2(\mathbb R^3)L2(R3) consisting of eigenvectors of HHH, and

σ(H‾)={(2n+3)ω∣n∈N0}.\sigma(\overline H) = \{(2n + 3)\omega \mid n \in \mathbb N_0\}.σ(H)={(2n+3)ω∣n∈N0​}.

Milestones

  • Density (Lemma 8.3). span⁡{xαe−∣x∣2/2∣α∈N0n}\operatorname{span}\{x^\alpha e^{-|x|^2/2} \mid \alpha \in \mathbb N_0^n\}span{xαe−∣x∣2/2∣α∈N0n​} is dense in L2(Rn)L^2(\mathbb R^n)L2(Rn) for every nnn.
  • Canonical commutation relation (Eq. (8.36)). [A−,A+]=1[A_-, A_+] = 1[A−​,A+​]=1 on span⁡{xke−ωx2/2}\operatorname{span}\{x^k e^{-\omega x^2/2}\}span{xke−ωx2/2}.
  • Factorization (Eq. (8.37)). On the same space, −d2dx2+ω2x2=ω(2N+1)-\frac{d^2}{dx^2} + \omega^2x^2 = \omega(2N + 1)−dx2d2​+ω2x2=ω(2N+1) with N=A+A−N = A_+A_-N=A+​A−​, and the space is invariant under A±A_\pmA±​.
  • Hermite functions (Eqs. (8.40)–(8.42)). ψn=A+nψ0/n!\psi_n = A_+^n\psi_0/\sqrt{n!}ψn​=A+n​ψ0​/n!​ with ψ0(x)=(ω/π)1/4e−ωx2/2\psi_0(x) = (\omega/\pi)^{1/4}e^{-\omega x^2/2}ψ0​(x)=(ω/π)1/4e−ωx2/2. Each ψn\psi_nψn​ is a normalized eigenfunction of NNN for the eigenvalue nnn, and span⁡{ψn}=span⁡{xke−ωx2/2}\operatorname{span}\{\psi_n\} = \operatorname{span}\{x^k e^{-\omega x^2/2}\}span{ψn​}=span{xke−ωx2/2}.
  • Heisenberg uncertainty principle (Theorem 8.2). For symmetric AAA, BBB and a state ψ∈D(AB)∩D(BA)\psi \in \mathfrak D(AB) \cap \mathfrak D(BA)ψ∈D(AB)∩D(BA),
Δψ(A) Δψ(B)≥12 ∣Eψ([A,B])∣,\Delta_\psi(A)\,\Delta_\psi(B) \ge \tfrac12\,|\mathbb E_\psi([A,B])|,Δψ​(A)Δψ​(B)≥21​∣Eψ​([A,B])∣,

with equality if (B−Eψ(B))ψ=iλ(A−Eψ(A))ψ(B - \mathbb E_\psi(B))\psi = i\lambda(A - \mathbb E_\psi(A))\psi(B−Eψ​(B))ψ=iλ(A−Eψ​(A))ψ for a real λ≠0\lambda \ne 0λ=0, or if ψ\psiψ is an eigenvector of AAA or BBB.

  • Abstract commutation (Theorem 8.6). For AAA closed and densely defined, A∗A∣Ker⁡(A)⊥A^*A|_{\operatorname{Ker}(A)^\perp}A∗A∣Ker(A)⊥​ and AA∗∣Ker⁡(A∗)⊥AA^*|_{\operatorname{Ker}(A^*)^\perp}AA∗∣Ker(A∗)⊥​ are unitarily equivalent. AAA maps eigenvectors of A∗AA^*AA∗A (eigenvalue EEE) to eigenvectors of AA∗AA^*AA∗ with ∥Aψ0∥=E ∥ψ0∥\|A\psi_0\| = \sqrt E\,\|\psi_0\|∥Aψ0​∥=E​∥ψ0​∥. For z≠0z \ne 0z=0,
RAA∗(z)⊇1z(ARA∗A(z)A∗−1),RA∗A(z)⊇1z(A∗RAA∗(z)A−1).R_{AA^*}(z) \supseteq \tfrac1z\big(A R_{A^*A}(z) A^* - 1\big), \qquad R_{A^*A}(z) \supseteq \tfrac1z\big(A^* R_{AA^*}(z) A - 1\big).RAA∗​(z)⊇z1​(ARA∗A​(z)A∗−1),RA∗A​(z)⊇z1​(A∗RAA∗​(z)A−1).

The last two milestones do not enter the goal. They are the chapter's other two theorems and use the same operator-theoretic layer.

Significance

Theorem 8.5 is the rigorous form of the most used exactly solvable model of quantum mechanics. Once it is available, the Hermite functions become an orthonormal basis of L2(R3)L^2(\mathbb R^3)L2(R3) that diagonalizes a concrete differential operator. That basis underlies Mehler's formula and the Fourier transform's action Fψn=(−i)nψn\mathcal F\psi_n = (-i)^n\psi_nFψn​=(−i)nψn​ (Eq. (8.46)). Perturbation arguments around the oscillator also start from it, and so does the construction of Fock space. The uncertainty principle is the basic quantitative constraint on simultaneous measurement. Theorem 8.6 gives an eigenvalue transfer mechanism that Teschl reuses to compute the hydrogen spectrum (Section 10.4).

Formally, the mission asks for a machine-checked proof about an unbounded differential operator on L2(R3)L^2(\mathbb R^3)L2(R3), stated on a concrete core. Mathlib has unbounded operators (LinearPMap, closure, adjoint), LpL^pLp spaces, Gaussian integrals and the probabilists' Hermite polynomials. It has no statement identifying the spectrum of a concrete Schrödinger operator. These results are proved in every textbook, but none of them has been formalized in this form.

Difficulty

The algebra of Eqs. (8.36)–(8.41) is a finite computation with polynomials times a Gaussian. The work in the goal is analytic. Essential self-adjointness is a statement about the closure of an operator on a non-closed domain. Symmetry of HHH together with a family of eigenvectors in Dω\mathfrak D_\omegaDω​ does not give it by definition, and the relevant criterion for unbounded operators is not in Mathlib. Completeness of the eigenfunctions in L2(R3)L^2(\mathbb R^3)L2(R3) is a density statement about a concrete function space (Lemma 8.3), and it has to be transferred from one dimension to three. The spectrum is asked for the closure H‾\overline HH, not for HHH on Dω\mathfrak D_\omegaDω​: the eigenvalues (2n+3)ω(2n+3)\omega(2n+3)ω are easy to exhibit, but showing that no other point of C\mathbb CC lies in σ(H‾)\sigma(\overline H)σ(H) requires control of (H‾−z)−1(\overline H - z)^{-1}(H−z)−1 on all of L2L^2L2. Finally, the Rodrigues formula (8.42) and the ladder construction (8.40) define the same functions only after an identity for all derivatives of e−x2e^{-x^2}e−x2.

Formalization scope

H\mathfrak HH is a complex inner product space with CompleteSpace; separability is not assumed, and no statement needs it. Operators are Mathlib LinearPMaps H →ₗ.[ℂ] H. A∗A^*A∗ is LinearPMap.adjoint, and every statement using it assumes a dense domain. Self-adjointness is Mathlib's IsSelfAdjoint, and essential self-adjointness is IsSelfAdjoint H.closure. ρ\rhoρ and σ\sigmaσ are defined in the mission for LinearPMaps (bounded two-sided inverse of A−zA - zA−z); Mathlib's Banach-algebra spectrum is not used. L2(Rn)L^2(\mathbb R^n)L2(Rn) is Lp ℂ 2 volume on EuclideanSpace ℝ (Fin n). The Laplacian is the sum of second Fréchet derivatives along the unit vectors. Hermite polynomials are defined by the Rodrigues formula, not as Mathlib's probabilists' Polynomial.hermite. No projection-valued measure, functional calculus or Fourier transform is taken as data.

The oscillator is not defined as a construction. IsHarmonicOscillator ω H states that D(H)=Dω\mathfrak D(H) = \mathfrak D_\omegaD(H)=Dω​ and that HHH acts on a representative fff as −Δf+ω2∣x∣2f-\Delta f + \omega^2|x|^2 f−Δf+ω2∣x∣2f. This determines HHH uniquely, and the goal also asserts that such an HHH exists. Trivializing formalization ruled out: defining HHH as the diagonal operator ∑n(2∣n∣+3)ω⟨ψn,⋅⟩ψn\sum_n (2|n| + 3)\omega\langle\psi_n,\cdot\rangle\psi_n∑n​(2∣n∣+3)ω⟨ψn​,⋅⟩ψn​ would make the spectrum immediate. Here HHH is the differential operator on Dω\mathfrak D_\omegaDω​, and its eigenvalues must be derived.

Two choices differ from the printed text. First, Teschl's (8.34) writes the domain with e−x2/2e^{-x^2/2}e−x2/2, but his (8.39)–(8.41) and the conclusion span⁡{ψn}=D\operatorname{span}\{\psi_n\} = \mathfrak Dspan{ψn​}=D use e−ωx2/2e^{-\omega x^2/2}e−ωx2/2. The mission uses Dω\mathfrak D_\omegaDω​, which equals (8.34) for ω=1\omega = 1ω=1. Lemma 8.3 is stated for (8.20)'s D\mathfrak DD itself. Second, Theorem 8.6 prints "H1ψ1=ψ1H_1\psi_1 = \psi_1H1​ψ1​=ψ1​", and the mission states the intended H1ψ1=Eψ1H_1\psi_1 = E\psi_1H1​ψ1​=Eψ1​. The uncertainty principle adds ∥ψ∥=1\|\psi\| = 1∥ψ∥=1 explicitly; the book assumes it through its definition of a state.

Reusable pieces are the product of LinearPMaps, spectrum and resolvent for unbounded operators, the Gauss–polynomial core and its density, and the Hermite-function API. Contributions of general lemmas are welcome, for example "an operator with an orthonormal eigenbasis in its domain is essentially self-adjoint" and the spectrum of such an operator.

Selected references

  • G. Teschl, Mathematical Methods in Quantum Mechanics, With Applications to Schrödinger Operators, Graduate Studies in Mathematics 99, AMS, 2009. bookstore.ams.org/gsm-99
  • H. P. Robertson, "The Uncertainty Principle", Physical Review 34 (1929), 163–164. doi:10.1103/PhysRev.34.163
  • W. Heisenberg, "Über den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik", Zeitschrift für Physik 43 (1927), 172–198. doi:10.1007/BF01397280
15 thms3 active usersReviewed
AnalysisMathematical Physics·Captain: mikedeng1

Mathematical Methods in Quantum Mechanics VIII: Relatively Compact Perturbations and Weyl's TheoremTextbook

Motivation

In quantum mechanics the spectrum of a Hamiltonian splits into two parts that behave very differently under perturbation. Isolated eigenvalues of finite multiplicity (bound states) move, split or disappear when the operator is changed even slightly; the rest of the spectrum, which carries scattering states and accumulation points of eigenvalues, is far more rigid. Weyl's theorem makes this rigidity precise: if two self-adjoint operators have resolvents that differ by a compact operator, their essential spectra coincide. It is the standard first step in locating the spectrum of a Schrödinger operator −Δ+V-\Delta + V−Δ+V: one shows that VVV is a relatively compact perturbation of −Δ-\Delta−Δ, concludes σess(−Δ+V)=σess(−Δ)=[0,∞)\sigma_{ess}(-\Delta + V) = \sigma_{ess}(-\Delta) = [0,\infty)σess​(−Δ+V)=σess​(−Δ)=[0,∞), and is left with the discrete eigenvalues below zero.

The result goes back to H. Weyl's 1909 work on compact perturbations of bounded self-adjoint operators; the resolvent formulation for unbounded operators is the one used in modern texts such as Reed–Simon (Vol. IV, Sec. XIII.4) and Teschl's Mathematical Methods in Quantum Mechanics (AMS GSM 99, 2009), Section 6.4, which this mission follows.

Setting

Let H\mathfrak HH be a complex Hilbert space and AAA a linear operator with domain D(A)⊆H\mathfrak D(A) \subseteq \mathfrak HD(A)⊆H. For z∈Cz \in \mathbb Cz∈C, the resolvent RA(z)=(A−z)−1R_A(z) = (A - z)^{-1}RA​(z)=(A−z)−1 exists when A−zA - zA−z maps D(A)\mathfrak D(A)D(A) bijectively onto H\mathfrak HH with a bounded inverse. The resolvent set ρ(A)\rho(A)ρ(A) is the set of such zzz, and the spectrum is σ(A)=C∖ρ(A)\sigma(A) = \mathbb C \setminus \rho(A)σ(A)=C∖ρ(A).

The discrete spectrum σd(A)\sigma_d(A)σd​(A) is the set of eigenvalues zzz of AAA that are isolated points of σ(A)\sigma(A)σ(A) and whose eigenspace Ker⁡(A−z)\operatorname{Ker}(A - z)Ker(A−z) is finite dimensional. The essential spectrum is σess(A)=σ(A)∖σd(A)\sigma_{ess}(A) = \sigma(A) \setminus \sigma_d(A)σess​(A)=σ(A)∖σd​(A).

A sequence ψn∈D(A)\psi_n \in \mathfrak D(A)ψn​∈D(A) with ∥ψn∥=1\|\psi_n\| = 1∥ψn​∥=1, ⟨φ,ψn⟩→0\langle \varphi, \psi_n \rangle \to 0⟨φ,ψn​⟩→0 for every φ\varphiφ (weak convergence to zero) and ∥(A−z)ψn∥→0\|(A - z)\psi_n\| \to 0∥(A−z)ψn​∥→0 is a singular Weyl sequence for AAA at zzz.

An operator is compact if it maps bounded sets to relatively compact sets; C(H)\mathfrak C(\mathfrak H)C(H) denotes the compact operators. An operator KKK is relatively compact with respect to AAA if D(A)⊆D(K)\mathfrak D(A) \subseteq \mathfrak D(K)D(A)⊆D(K) and KRA(z)∈C(H)K R_A(z) \in \mathfrak C(\mathfrak H)KRA​(z)∈C(H) for one z∈ρ(A)z \in \rho(A)z∈ρ(A). BBB is AAA bounded if D(A)⊆D(B)\mathfrak D(A) \subseteq \mathfrak D(B)D(A)⊆D(B) and ∥Bψ∥≤a∥Aψ∥+b∥ψ∥\|B\psi\| \le a\|A\psi\| + b\|\psi\|∥Bψ∥≤a∥Aψ∥+b∥ψ∥ on D(A)\mathfrak D(A)D(A); the infimum of admissible aaa is the AAA-bound. A symmetric operator AAA has defect indices d±(A)=dim⁡Ran⁡(A±i)⊥d_\pm(A) = \dim \operatorname{Ran}(A \pm i)^\perpd±​(A)=dimRan(A±i)⊥.

Formalization targets

Goal: Weyl's theorem (Theorem 6.19)

For self-adjoint AAA and BBB,

∃ z∈ρ(A)∩ρ(B): RA(z)−RB(z)∈C(H)⟹σess(A)=σess(B).\exists\, z \in \rho(A) \cap \rho(B):\ R_A(z) - R_B(z) \in \mathfrak C(\mathfrak H) \quad\Longrightarrow\quad \sigma_{ess}(A) = \sigma_{ess}(B).∃z∈ρ(A)∩ρ(B): RA​(z)−RB​(z)∈C(H)⟹σess​(A)=σess​(B).

Milestones

  • Weyl criterion (Lemma 6.17). For self-adjoint AAA: z∈σess(A)z \in \sigma_{ess}(A)z∈σess​(A) if and only if a singular Weyl sequence at zzz exists; if so, it can be chosen orthonormal.
  • Compact perturbations (Lemma 6.18). For self-adjoint AAA and compact self-adjoint KKK, σess(A+K)=σess(A)\sigma_{ess}(A + K) = \sigma_{ess}(A)σess​(A+K)=σess​(A), and
σess(A)=⋂K∈C(H), K∗=Kσ(A+K).\sigma_{ess}(A) = \bigcap_{K \in \mathfrak C(\mathfrak H),\, K^* = K} \sigma(A + K).σess​(A)=K∈C(H),K∗=K⋂​σ(A+K).
  • Independence of zzz (Lemma 6.21, first part). If RA(z)−RB(z)R_A(z) - R_B(z)RA​(z)−RB​(z) is compact for one z∈ρ(A)∩ρ(B)z \in \rho(A) \cap \rho(B)z∈ρ(A)∩ρ(B), it is compact for all such zzz.
  • Self-adjoint extensions (Theorem 6.20). If AAA is symmetric with d+(A)=d−(A)<∞d_+(A) = d_-(A) < \inftyd+​(A)=d−​(A)<∞, all self-adjoint extensions of AAA have the same essential spectrum.
  • Relative compactness is infinitesimal (Lemma 6.22). For self-adjoint AAA, a relatively compact KKK has AAA-bound 000.
  • Stability of relative compactness (Lemma 6.23). If AAA is self-adjoint, BBB symmetric with AAA-bound less than one, and KKK relatively compact with respect to AAA, then KKK is relatively compact with respect to A+BA + BA+B.

Significance

The result. Weyl's theorem reduces the determination of the essential spectrum of a perturbed operator to that of a simpler reference operator. Combined with Lemma 6.22 and the Kato–Rellich theorem, it yields σess(A+K)=σess(A)\sigma_{ess}(A + K) = \sigma_{ess}(A)σess​(A+K)=σess​(A) for every relatively compact symmetric KKK; Lemma 6.23 extends this to perturbations of the form B+KB + KB+K. These are the inputs to the HVZ theorem for NNN-body systems, to the spectral analysis of one-particle Schrödinger operators with decaying potentials, and, via Theorem 6.20, to the observation that boundary conditions at a limit-circle endpoint do not affect the essential spectrum of a Sturm–Liouville operator. The Weyl criterion is independently useful: it is how points are shown to lie in σess\sigma_{ess}σess​ in concrete examples.

Formalizing it. The results are classical and proved in every text on the subject. None of them is formalized: Mathlib has compact operators and the adjoint of a densely defined LinearPMap, but no resolvent set or spectrum for unbounded operators, no discrete or essential spectrum and no relative compactness. This mission asks for formal proofs of Teschl's statements and, with them, a reusable layer of definitions (resolvent of a LinearPMap, σd\sigma_dσd​, σess\sigma_{ess}σess​, singular Weyl sequences, relative compactness) on which later chapters (free Schrödinger operator, HVZ theorem) can build.

Difficulty

The obvious route to all of these statements goes through the spectral theorem: Teschl's proof of the Weyl criterion uses spectral projections PA((λ−ε,λ+ε))P_A((\lambda - \varepsilon, \lambda + \varepsilon))PA​((λ−ε,λ+ε)) and spectral measures μψn\mu_{\psi_n}μψn​​, and his characterization (6.27)–(6.28) of σess\sigma_{ess}σess​ by ranks of spectral projections presupposes the functional calculus. Mathlib has no spectral theorem for unbounded self-adjoint operators, so this route requires either building it or finding arguments that avoid it. The definition of σess\sigma_{ess}σess​ used here is deliberately the PVM-free one of p. 145, which makes the statements expressible now but moves the difficulty into the proofs: showing that a point of σ(A)∖σd(A)\sigma(A) \setminus \sigma_d(A)σ(A)∖σd​(A) carries a singular Weyl sequence requires controlling approximate eigenvectors near a non-isolated spectral point or an eigenvalue of infinite multiplicity without projections.

A second difficulty is domain bookkeeping. A+KA + KA+K, A+BA + BA+B, KRA(z)K R_A(z)KRA​(z) and RA+B(z)R_{A+B}(z)RA+B​(z) all involve unbounded operators with different domains, and identities such as the second resolvent formula KRA+B(z)=KRA(z)(I−BRA+B(z))K R_{A+B}(z) = K R_A(z)(\mathbb I - B R_{A+B}(z))KRA+B​(z)=KRA​(z)(I−BRA+B​(z)) must be established on the correct domains. Theorem 6.20 requires relating the resolvents of two self-adjoint extensions through the finite-dimensional defect spaces.

Formalization scope

The Hilbert space is {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℂ H] [CompleteSpace H]; separability is not assumed, since no statement of the section needs it. Unbounded operators are Mathlib LinearPMaps H →ₗ.[ℂ] H, self-adjointness is Mathlib's IsSelfAdjoint (which implies a dense domain), and symmetric operators are densely defined by definition, as in the book. The resolvent is the bounded two-sided inverse of A−zA - zA−z of p. 73 (IsResolventAt), and ρ(A)\rho(A)ρ(A), σ(A)\sigma(A)σ(A) are defined from it; Mathlib's Banach-algebra spectrum is not used. "For one z∈ρ(A)∩ρ(B)z \in \rho(A) \cap \rho(B)z∈ρ(A)∩ρ(B)" is an existential over zzz and the two resolvents. Compactness is Mathlib's IsCompactOperator, which on a Hilbert space agrees with the book's norm closure of finite rank operators. A+KA + KA+K for bounded KKK is K +ᵥ A (domain D(A)\mathfrak D(A)D(A)); A+BA + BA+B for unbounded BBB is the LinearPMap sum with domain D(A)∩D(B)\mathfrak D(A) \cap \mathfrak D(B)D(A)∩D(B). The AAA-bound is valued in [0,∞][0,\infty][0,∞] and is ∞\infty∞ for an operator that is not AAA bounded. The defect indices are "equal and finite" when both defect spaces are finite dimensional with equal finrank.

No projection-valued measure or functional calculus is taken as data, and none is needed: every statement is phrased without f(A)f(A)f(A). For this reason the second half of Lemma 6.21, f(A)−f(B)∈C(H)f(A) - f(B) \in \mathfrak C(\mathfrak H)f(A)−f(B)∈C(H) for f∈C∞(R)f \in C_\infty(\mathbb R)f∈C∞​(R), and the form-compactness results Lemma 6.26 and Corollary 6.27 of Section 6.5 are not part of the mission.

A trivializing formalization is ruled out: the discrete spectrum requires all three of "eigenvalue", "isolated in σ(A)\sigma(A)σ(A)" and "finite-dimensional eigenspace", so σess\sigma_{ess}σess​ is neither empty nor all of σ(A)\sigma(A)σ(A) by definition, and the resolvent hypothesis of Weyl's theorem is an existential over genuine resolvents, never a junk value outside ρ(A)\rho(A)ρ(A).

A complete development needs the resolvent identities for LinearPMaps, the relation between self-adjointness and real spectrum, weak convergence of bounded sequences, and the fact that compact operators map weakly null sequences to norm-null ones. The definitions of resolvent, σess\sigma_{ess}σess​, relative compactness and AAA-bound are shared with other chapters of this series and are intended for reuse. Contributions of general lemmas on LinearPMap resolvents are welcome.

Selected references

  • G. Teschl, Mathematical Methods in Quantum Mechanics, With Applications to Schrödinger Operators, Graduate Studies in Mathematics 99, AMS, 2009, Section 6.4. https://doi.org/10.1090/gsm/099
  • H. Weyl, Über beschränkte quadratische Formen, deren Differenz vollstetig ist, Rendiconti del Circolo Matematico di Palermo 27 (1909), 373–392. https://doi.org/10.1007/BF03019655
  • M. Reed and B. Simon, Methods of Modern Mathematical Physics IV: Analysis of Operators, Academic Press, 1978, Section XIII.4.
  • T. Kato, Perturbation Theory for Linear Operators, 2nd ed., Springer, 1980, Section IV.5. https://doi.org/10.1007/978-3-642-66282-9
14 thms3 active usersReviewed
🏆Completed
AnalysisPartial Differential Equations·Captain: mikedeng1

Notes on Partial Differential Equations X: Galerkin Existence of Weak Solutions of Parabolic PDEsTextbook

Motivation

Linear second-order parabolic equations such as ut+Lu=fu_t + Lu = fut​+Lu=f model diffusion with advection, growth or decay, and external sources. The heat equation is the prototype. For coefficients that are only bounded and measurable, classical solutions need not exist, and the natural well-posedness theory is the L2L^2L2 energy theory of weak solutions. In that theory the solution is a curve t↦u(t)t \mapsto u(t)t↦u(t) in a Sobolev space, and the equation holds in the dual space. This framework, developed by J.-L. Lions and others in the 1950s–60s (Lions–Magenes 1972), underlies the numerical analysis of parabolic problems through finite elements and spectral Galerkin methods. It also underlies the existence theory for nonlinear evolution equations such as the Navier–Stokes equations (Temam 1977).

This mission formalizes Chapter 6 of J. K. Hunter's Notes on Partial Differential Equations (UC Davis, revised 6/18/2014): the existence, uniqueness and energy estimate for weak solutions of the parabolic initial–boundary value problem, proved by the Galerkin method. It also formalizes the vector-valued calculus on Hilbert triples that the proof rests on, and the Ehrling and Aubin–Lions compactness results of §6.6.

Setting

Let Ω⊂Rn\Omega \subset \mathbb{R}^nΩ⊂Rn be a bounded open set and T>0T > 0T>0. H01(Ω)H^1_0(\Omega)H01​(Ω) is the closure of Cc∞(Ω)C_c^\infty(\Omega)Cc∞​(Ω) in the norm ∥u∥H012=∫Ω(u2+∣Du∣2) dx\|u\|_{H^1_0}^2 = \int_\Omega (u^2 + |Du|^2)\,dx∥u∥H01​2​=∫Ω​(u2+∣Du∣2)dx. H−1(Ω)H^{-1}(\Omega)H−1(Ω) is its dual, with pairing ⟨f,v⟩\langle f, v\rangle⟨f,v⟩. Every u∈L2(Ω)u \in L^2(\Omega)u∈L2(Ω) acts on H01(Ω)H^1_0(\Omega)H01​(Ω) by v↦∫Ωuv dxv \mapsto \int_\Omega uv\,dxv↦∫Ω​uvdx.

The operator is Lu=−∑i,j∂i(aij∂ju)+∑jbj∂ju+cuLu = -\sum_{i,j}\partial_i(a^{ij}\partial_j u) + \sum_j b^j\partial_j u + cuLu=−∑i,j​∂i​(aij∂j​u)+∑j​bj∂j​u+cu. Its coefficients satisfy Assumption 6.1: aij,bj,c∈L∞(Ω×(0,T))a^{ij}, b^j, c \in L^\infty(\Omega\times(0,T))aij,bj,c∈L∞(Ω×(0,T)), aij=ajia^{ij} = a^{ji}aij=aji, and uniform ellipticity ∑aijξiξj≥θ∣ξ∣2\sum a^{ij}\xi_i\xi_j \ge \theta|\xi|^2∑aijξi​ξj​≥θ∣ξ∣2 for some θ>0\theta > 0θ>0. The associated form is

a(u,v;t)=∑i,j∫Ωaij∂iu ∂jv dx+∑j∫Ωbj∂ju v dx+∫Ωc uv dx.a(u, v; t) = \sum_{i,j}\int_\Omega a^{ij}\partial_i u\,\partial_j v\,dx + \sum_j\int_\Omega b^j\partial_j u\,v\,dx + \int_\Omega c\,uv\,dx.a(u,v;t)=i,j∑​∫Ω​aij∂i​u∂j​vdx+j∑​∫Ω​bj∂j​uvdx+∫Ω​cuvdx.

A function u:[0,T]→H01(Ω)u : [0,T] \to H^1_0(\Omega)u:[0,T]→H01​(Ω) has weak time derivative ut=wu_t = wut​=w if ∫0Tϕ′(t)u(t) dt=−∫0Tϕ(t)w(t) dt\int_0^T \phi'(t)u(t)\,dt = -\int_0^T\phi(t)w(t)\,dt∫0T​ϕ′(t)u(t)dt=−∫0T​ϕ(t)w(t)dt for all ϕ∈Cc∞(0,T)\phi \in C_c^\infty(0,T)ϕ∈Cc∞​(0,T), with Bochner integrals in H−1(Ω)H^{-1}(\Omega)H−1(Ω). Given f∈L2(0,T;H−1(Ω))f \in L^2(0,T;H^{-1}(\Omega))f∈L2(0,T;H−1(Ω)) and g∈L2(Ω)g \in L^2(\Omega)g∈L2(Ω), uuu is a weak solution of

ut+Lu=f in Ω×(0,T),u=0 on ∂Ω,u(0)=gu_t + Lu = f \ \text{in } \Omega\times(0,T), \qquad u = 0 \ \text{on } \partial\Omega, \qquad u(0) = gut​+Lu=f in Ω×(0,T),u=0 on ∂Ω,u(0)=g

when three conditions hold. First, u∈L2(0,T;H01)u \in L^2(0,T;H^1_0)u∈L2(0,T;H01​) and ut∈L2(0,T;H−1)u_t \in L^2(0,T;H^{-1})ut​∈L2(0,T;H−1). Second, ⟨ut(t),v⟩+a(u(t),v;t)=⟨f(t),v⟩\langle u_t(t), v\rangle + a(u(t), v; t) = \langle f(t), v\rangle⟨ut​(t),v⟩+a(u(t),v;t)=⟨f(t),v⟩ for every v∈H01(Ω)v \in H^1_0(\Omega)v∈H01​(Ω) and a.e. ttt. Third, u(0)=gu(0) = gu(0)=g, where the value at 000 is that of the continuous representative in C([0,T];L2(Ω))C([0,T];L^2(\Omega))C([0,T];L2(Ω)).

The Galerkin approximations use an L2L^2L2-orthonormal basis {wk}\{w_k\}{wk​} of Dirichlet eigenfunctions and the spaces EN=⟨w1,…,wN⟩E_N = \langle w_1, \dots, w_N\rangleEN​=⟨w1​,…,wN​⟩. The approximation uN:[0,T]→ENu_N : [0,T] \to E_NuN​:[0,T]→EN​ solves the projected equation (uNt,v)L2+a(uN,v;t)=⟨f,v⟩(u_{Nt}, v)_{L^2} + a(u_N, v; t) = \langle f, v\rangle(uNt​,v)L2​+a(uN​,v;t)=⟨f,v⟩ for v∈ENv \in E_Nv∈EN​, with uN(0)=PNgu_N(0) = P_N guN​(0)=PN​g.

A Hilbert triple V↪H↪V′\mathcal{V} \hookrightarrow \mathcal{H} \hookrightarrow \mathcal{V}'V↪H↪V′ consists of two separable Hilbert spaces V\mathcal{V}V, H\mathcal{H}H and the dual V′\mathcal{V}'V′, with dense continuous injective embeddings and ⟨f,v⟩=(f,v)H\langle f, v\rangle = (f, v)_{\mathcal{H}}⟨f,v⟩=(f,v)H​ for f∈Hf \in \mathcal{H}f∈H. The model is H01↪L2↪H−1H^1_0 \hookrightarrow L^2 \hookrightarrow H^{-1}H01​↪L2↪H−1.

Formalization targets

Goal: Theorem 6.3

For every f∈L2(0,T;H−1(Ω))f \in L^2(0,T;H^{-1}(\Omega))f∈L2(0,T;H−1(Ω)) and g∈L2(Ω)g \in L^2(\Omega)g∈L2(Ω) there is a unique weak solution u∈C([0,T];L2)∩L2(0,T;H01)u \in C([0,T];L^2) \cap L^2(0,T;H^1_0)u∈C([0,T];L2)∩L2(0,T;H01​) with ut∈L2(0,T;H−1)u_t \in L^2(0,T;H^{-1})ut​∈L2(0,T;H−1). There is also a constant C=C(Ω,T,L)C = C(\Omega, T, L)C=C(Ω,T,L) such that

∥u∥L∞(0,T;L2)+∥u∥L2(0,T;H01)+∥ut∥L2(0,T;H−1)≤C(∥f∥L2(0,T;H−1)+∥g∥L2).\|u\|_{L^\infty(0,T;L^2)} + \|u\|_{L^2(0,T;H^1_0)} + \|u_t\|_{L^2(0,T;H^{-1})} \le C\big(\|f\|_{L^2(0,T;H^{-1})} + \|g\|_{L^2}\big).∥u∥L∞(0,T;L2)​+∥u∥L2(0,T;H01​)​+∥ut​∥L2(0,T;H−1)​≤C(∥f∥L2(0,T;H−1)​+∥g∥L2​).

Milestones

  • Theorem 6.41. If u∈L2(0,T;V)u \in L^2(0,T;\mathcal{V})u∈L2(0,T;V) and ut∈L2(0,T;V′)u_t \in L^2(0,T;\mathcal{V}')ut​∈L2(0,T;V′), then u∈C([0,T];H)u \in C([0,T];\mathcal{H})u∈C([0,T];H). Moreover ddt(u,v)H=⟨ut,v⟩\frac{d}{dt}(u,v)_{\mathcal{H}} = \langle u_t, v\rangledtd​(u,v)H​=⟨ut​,v⟩, ddt∥u∥H2=2⟨ut,u⟩\frac{d}{dt}\|u\|^2_{\mathcal{H}} = 2\langle u_t, u\rangledtd​∥u∥H2​=2⟨ut​,u⟩, and ∥u∥L∞(H)≤C(∥u∥L2(V)+∥ut∥L2(V′))\|u\|_{L^\infty(\mathcal{H})} \le C(\|u\|_{L^2(\mathcal{V})} + \|u_t\|_{L^2(\mathcal{V}')})∥u∥L∞(H)​≤C(∥u∥L2(V)​+∥ut​∥L2(V′)​).
  • Theorem 6.42. ∫0T⟨ut,v⟩ dt=(u(T),v(T))H−(u(0),v(0))H−∫0T⟨u,vt⟩ dt\int_0^T\langle u_t, v\rangle\,dt = (u(T),v(T))_{\mathcal{H}} - (u(0),v(0))_{\mathcal{H}} - \int_0^T\langle u, v_t\rangle\,dt∫0T​⟨ut​,v⟩dt=(u(T),v(T))H​−(u(0),v(0))H​−∫0T​⟨u,vt​⟩dt.
  • Proposition 6.5. Each Galerkin problem has a unique solution uNu_NuN​.
  • Proposition 6.6. The energy estimate above holds for uNu_NuN​ with CCC independent of NNN.
  • Proposition 6.7. A subsequence of uNu_NuN​ converges weakly to a weak solution satisfying the estimate.
  • Lemma 6.10 (Ehrling) and Theorem 6.9 (Aubin–Lions). These are further results of the chapter, stated for Banach spaces X↪Y↪ZX \hookrightarrow Y \hookrightarrow ZX↪Y↪Z with XXX compactly embedded in YYY.

Significance

Theorem 6.3 is the basic well-posedness theorem for linear parabolic equations with rough coefficients. It gives existence and uniqueness, and continuous dependence on the data through the linear estimate. The same argument gives the Galerkin convergence that justifies spectral and finite-element semi-discretizations. The Hilbert-triple calculus of Theorems 6.41–6.42 is the standard setting for linear and nonlinear evolution equations. The Aubin–Lions lemma is the compactness tool for nonlinear problems, such as the semilinear heat equation of §6.6 and the Navier–Stokes equations of §6.7.

All of these results are classical and proved in the notes, except that Theorem 6.41's proof leans on vector-valued mollification. As far as a search of the platform shows, none of them is formalized there. Mathlib has the Bochner integral, LpL^pLp spaces of Banach-valued functions and Gronwall's inequality. It does not have weak derivatives of vector-valued functions, Hilbert triples, or evolution-equation existence theorems. The work here is therefore to formalize known proofs, and in doing so to build reusable infrastructure for time-dependent PDEs.

Difficulty

The main obstacle is that the natural objects are equivalence classes of vector-valued functions, not functions. The initial condition u(0)=gu(0) = gu(0)=g is meaningless for an element of L2(0,T;H01)L^2(0,T;H^1_0)L2(0,T;H01​) until Theorem 6.41 provides a continuous representative. Its proof needs extension across the endpoints and mollification of V\mathcal{V}V-valued functions. Passing to the limit in the Galerkin scheme needs weak compactness in L2(0,T;H01)L^2(0,T;H^1_0)L2(0,T;H01​) and L2(0,T;H−1)L^2(0,T;H^{-1})L2(0,T;H−1), identified with a dual Bochner space. Proposition 6.5 is a linear ODE system whose coefficients are only L∞L^\inftyL∞ in time, so the Picard–Lindelöf theorem for continuous right-hand sides does not apply directly. The H−1H^{-1}H−1 bound on uNtu_{Nt}uNt​ needs the projection PNP_NPN​ to be bounded on H01H^1_0H01​ as well as on L2L^2L2, which is why the basis is taken to be eigenfunctions. Uniqueness needs the energy identity (6.46) and a Gronwall argument in weak form.

Formalization scope

  • Rn\mathbb{R}^nRn is EuclideanSpace ℝ (Fin n), with 0-based coordinates. H10 n Ω is the closure of the jets (ϕ,∇ϕ)(\phi, \nabla\phi)(ϕ,∇ϕ), ϕ∈Cc∞(Ω)\phi \in C_c^\infty(\Omega)ϕ∈Cc∞​(Ω), in L2(Ω;R×Rn)L^2(\Omega;\mathbb{R}\times\mathbb{R}^n)L2(Ω;R×Rn), so its norm is the full H1H^1H1 norm. Hm1 n Ω is StrongDual ℝ (H10 n Ω). l2Embed is the embedding H01↪L2↪H−1H^1_0 \hookrightarrow L^2 \hookrightarrow H^{-1}H01​↪L2↪H−1.
  • Lp(0,T;X)L^p(0,T;X)Lp(0,T;X) is MemLp for Lebesgue measure on (0,T)(0,T)(0,T), and norms are eLpNorm with values in [0,∞][0,\infty][0,∞]. Constants are finite nonnegative reals. Every constant is quantified before the data it must not depend on: before fff, ggg in Theorem 6.3, and before the basis, fff, ggg, NNN in Propositions 6.6–6.7.
  • The weak time derivative is (6.14) in its standard form ∫ϕ′u=−∫ϕw\int\phi' u = -\int\phi w∫ϕ′u=−∫ϕw. The page prints ϕ\phiϕ and ϕ′\phi'ϕ′ interchanged, which is a typo.
  • Weak solutions take g∈L2(Ω)g \in L^2(\Omega)g∈L2(Ω) as in Assumption 6.1(3). The printed Theorem 6.3 says g∈H01(Ω)g \in H^1_0(\Omega)g∈H01​(Ω), a special case. u(0)=gu(0) = gu(0)=g is read through a continuous representative u~∈C([0,T];L2)\tilde u \in C([0,T];L^2)u~∈C([0,T];L2), and uniqueness means equality for a.e. ttt.
  • Coefficient conditions and ellipticity hold almost everywhere on Ω×(0,T)\Omega\times(0,T)Ω×(0,T). The Galerkin basis is a hypothesis: an orthonormal basis of L2(Ω)L^2(\Omega)L2(Ω) of weak Dirichlet eigenfunctions.
  • Proposition 6.7 states weak convergence of uNku_{N_k}uNk​​ in L2(0,T;H01)L^2(0,T;H^1_0)L2(0,T;H01​) and of uNktu_{N_k t}uNk​t​ in L2(0,T;H−1)L^2(0,T;H^{-1})L2(0,T;H−1), in the explicit integral form of p. 186. This is at least as strong as the printed claim.
  • Hilbert triples are structures with two continuous injective dense-range embeddings, separability, and the compatibility identity. Reflexivity in Theorem 6.9 is surjectivity of the canonical map into the bidual.
  • Ruling out trivializations. Every Bochner integral in a definition has an integrable integrand under the stated L2L^2L2 hypotheses, so no weak-derivative or weak-solution condition holds through the integral's junk value 000. The initial condition is imposed on a continuous representative, so it is not vacuous on a null set.
  • Reusable infrastructure welcome: vector-valued mollification and extension, the Hilbert-triple calculus, and dual identification of L2(0,T;X)′L^2(0,T;X)'L2(0,T;X)′.

Selected references

  • J. K. Hunter, Notes on Partial Differential Equations, UC Davis lecture notes, revised 6/18/2014, Chapter 6. https://www.math.ucdavis.edu/~hunter/pdes/pde_notes.pdf
  • L. C. Evans, Partial Differential Equations, 2nd ed., Graduate Studies in Mathematics 19, AMS, 2010, §7.1. https://doi.org/10.1090/gsm/019
  • J.-L. Lions and E. Magenes, Non-Homogeneous Boundary Value Problems and Applications I, Springer, 1972. https://doi.org/10.1007/978-3-642-65161-8
  • R. Temam, Navier–Stokes Equations: Theory and Numerical Analysis, North-Holland, 1977; AMS Chelsea reprint 2001. https://doi.org/10.1090/chel/343
  • J. Simon, Compact sets in the space Lp(0,T;B)L^p(0,T;B)Lp(0,T;B), Ann. Mat. Pura Appl. 146 (1987), 65–96. https://doi.org/10.1007/BF01762360
17 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

On the Maximal Monotonicity of Subdifferential Mappings II: Subdifferentials Are Exactly the Maximal Cyclically Monotone Operators, Unique up to an Additive ConstantResearch Paper

Motivation

A differentiable convex function on Rn\mathbb{R}^nRn is determined, up to an additive constant, by its gradient, and a vector field is a gradient of a convex function exactly when it satisfies a monotonicity condition along closed cycles. Convex analysis and optimization need the same statement for nonsmooth and extended-valued functions on infinite-dimensional spaces: the subdifferential replaces the gradient, and the question becomes which multivalued maps from a Banach space to its dual arise as subdifferentials, and how much of the function they determine. The answer underlies the treatment of optimality conditions, variational inequalities and evolution equations governed by subdifferentials, where one works with the operator ∂f\partial f∂f and needs to recover fff from it.

Timeline.

  • 1966: R. T. Rockafellar, Characterization of the subdifferentials of convex functions, Pacific J. Math. 17 (DOI 10.2140/pjm.1966.17.497), studied cyclically monotone operators and stated the characterization of subdifferentials as the maximal cyclically monotone operators (its Theorem 3), together with the maximal monotonicity of subdifferentials (its Theorem 4).
  • 1969: H. Brézis pointed out a gap in the 1966 proofs of maximality and uniqueness: a family of dual vectors xε∗x_\varepsilon^*xε∗​ used in the argument might increase unboundedly in norm as ε→0\varepsilon \to 0ε→0.
  • 1970: Rockafellar, On the maximal monotonicity of subdifferential mappings, Pacific J. Math. 33 (DOI 10.2140/pjm.1970.33.209), repaired the argument for arbitrary real Banach spaces, proving Theorem A (maximal monotonicity of ∂f\partial f∂f) and Theorem B (the characterization treated here).

Setting

Let EEE be a real Banach space with dual E∗E^*E∗, and write ⟨x,x∗⟩\langle x, x^* \rangle⟨x,x∗⟩ for the value of x∗∈E∗x^* \in E^*x∗∈E∗ at x∈Ex \in Ex∈E. A proper convex function on EEE is a function f:E→(−∞,+∞]f : E \to (-\infty, +\infty]f:E→(−∞,+∞], not identically +∞+\infty+∞, with f((1−λ)x+λy)≤(1−λ)f(x)+λf(y)f((1-\lambda)x + \lambda y) \le (1-\lambda)f(x) + \lambda f(y)f((1−λ)x+λy)≤(1−λ)f(x)+λf(y) for all x,y∈Ex, y \in Ex,y∈E and 0<λ<10 < \lambda < 10<λ<1. It is lower semicontinuous (lsc) in the norm topology. Its subdifferential is the multivalued map

∂f(x)={ x∗∈E∗∣f(y)≥f(x)+⟨y−x,x∗⟩  ∀y∈E }.\partial f(x) = \{\, x^* \in E^* \mid f(y) \ge f(x) + \langle y - x, x^* \rangle \ \ \forall y \in E \,\}.∂f(x)={x∗∈E∗∣f(y)≥f(x)+⟨y−x,x∗⟩  ∀y∈E}.

A multivalued map T:E→E∗T : E \to E^*T:E→E∗ is a cyclically monotone operator if

⟨x0−x1,x0∗⟩+⋯+⟨xn−1−xn,xn−1∗⟩+⟨xn−x0,xn∗⟩≥0whenever xi∗∈T(xi), i=0,…,n,\langle x_0 - x_1, x_0^* \rangle + \cdots + \langle x_{n-1} - x_n, x_{n-1}^* \rangle + \langle x_n - x_0, x_n^* \rangle \ge 0 \qquad\text{whenever } x_i^* \in T(x_i),\ i = 0, \dots, n,⟨x0​−x1​,x0∗​⟩+⋯+⟨xn−1​−xn​,xn−1∗​⟩+⟨xn​−x0​,xn∗​⟩≥0whenever xi∗​∈T(xi​), i=0,…,n,

and maximal cyclically monotone if, in addition, its graph {(x,x∗)∣x∗∈T(x)}\{(x, x^*) \mid x^* \in T(x)\}{(x,x∗)∣x∗∈T(x)} is not properly contained in the graph of any other cyclically monotone operator. The conjugate of fff is f∗(x∗)=sup⁡x∈E(⟨x,x∗⟩−f(x))f^*(x^*) = \sup_{x \in E} (\langle x, x^* \rangle - f(x))f∗(x∗)=supx∈E​(⟨x,x∗⟩−f(x)) on E∗E^*E∗, and j(x)=12∥x∥2j(x) = \tfrac12\|x\|^2j(x)=21​∥x∥2. In the Lean development these are ProperConvex, subdiff, IsCyclicallyMonotone, IsMaximalCyclicallyMonotone, conj and halfSqNorm, in the namespace RockafellarMaxMono.Cyclic.

Formalization targets

Goal: Theorem B (p. 210)

For every multivalued map T:E→E∗T : E \to E^*T:E→E∗ on a real Banach space EEE,

(∃f lsc proper convex with T=∂f)  ⟺  T is maximal cyclically monotone,\bigl(\exists f \text{ lsc proper convex with } T = \partial f\bigr) \iff T \text{ is maximal cyclically monotone},(∃f lsc proper convex with T=∂f)⟺T is maximal cyclically monotone,

and if fff and ggg are lsc proper convex with ∂f=T=∂g\partial f = T = \partial g∂f=T=∂g, then g=f+cg = f + cg=f+c for a real constant ccc. Both halves are one statement.

Milestones, in attack order

  1. (3.7) For a finite continuous convex function fff on a real Banach space, ∂f(x)\partial f(x)∂f(x) is nonempty and weak* compact and f′(x;u)=max⁡{⟨u,x∗⟩∣x∗∈∂f(x)}f'(x;u) = \max\{\langle u, x^* \rangle \mid x^* \in \partial f(x)\}f′(x;u)=max{⟨u,x∗⟩∣x∗∈∂f(x)}.
  2. Finite continuous case (pp. 214–215). For finite continuous convex f,gf, gf,g on a real Banach space, ∂g(x)⊃∂f(x)\partial g(x) \supset \partial f(x)∂g(x)⊃∂f(x) for all xxx implies g=f+constg = f + \mathrm{const}g=f+const.
  3. (3.1) ∂(f+j)(x)=∂f(x)+∂j(x)\partial(f + j)(x) = \partial f(x) + \partial j(x)∂(f+j)(x)=∂f(x)+∂j(x) for lsc proper convex fff.
  4. Proposition 1 x∗∗∈∂f∗(x∗)x^{**} \in \partial f^*(x^*)x∗∗∈∂f∗(x∗) if and only if x∗∗x^{**}x∗∗ is a weak** limit of a bounded net xix_ixi​ with xi∗∈∂f(xi)x_i^* \in \partial f(x_i)xi∗​∈∂f(xi​), xi∗→x∗x_i^* \to x^*xi∗​→x∗ in norm.
  5. (p. 213) (f+j)∗(f + j)^*(f+j)∗ is finite and continuous on E∗E^*E∗.
  6. (p. 211) f∗∗f^{**}f∗∗ restricted to EEE is fff.
  7. (3.6) For lsc proper convex f,gf, gf,g: ∂g(x)⊃∂f(x)\partial g(x) \supset \partial f(x)∂g(x)⊃∂f(x) for all xxx implies g=f+constg = f + \mathrm{const}g=f+const.

Significance

The result. Theorem B gives an intrinsic description of subdifferential maps: an operator is the subdifferential of a closed proper convex function if and only if it satisfies the cycle inequality and cannot be enlarged without violating it. The uniqueness clause says that a closed convex function is recovered from its subdifferential up to a constant, the nonsmooth counterpart of recovering a function from its gradient. Milestone 7 is stronger than uniqueness: a one-sided inclusion ∂f⊆∂g\partial f \subseteq \partial g∂f⊆∂g already forces g=f+cg = f + cg=f+c, and this is what gives maximality.

Formalizing it. The theorem is proved in the paper, and nothing of it is formalized on the platform. Mathlib has convex functions, continuous duals, biduals and weak-* topologies, but not extended-valued subdifferentials on Banach spaces, conjugate duality in the nonreflexive setting, or monotone operator theory. This mission produces formal statements of the paper's steps, the standard max formula for directional derivatives on a Banach space, and the Fenchel conjugate facts the argument uses, each as a separate target.

Difficulty

In a reflexive space the argument is short, because ∂f∗\partial f^*∂f∗ is the inverse of ∂f\partial f∂f. In a nonreflexive space it is not: ∂f∗\partial f^*∂f∗ maps E∗E^*E∗ into E∗∗E^{**}E∗∗, and points of E∗∗∖EE^{**} \setminus EE∗∗∖E appear. The naive route, transferring the inclusion ∂f⊆∂g\partial f \subseteq \partial g∂f⊆∂g to the conjugates by inverting the maps, breaks down there, and the 1966 argument failed at a related step, where the dual vectors in an approximation could be unbounded. Relating ∂f∗\partial f^*∂f∗ to ∂f\partial f∂f without reflexivity is where the difficulty sits; the boundedness of the approximating nets in Proposition 1 is essential and cannot be dropped. The finite continuous case and the max formula (3.7) are needed on an arbitrary Banach space, including the dual E∗E^*E∗, not only on EEE.

Formalization scope

EEE is a real Banach space (NormedAddCommGroup, NormedSpace ℝ, CompleteSpace); E∗E^*E∗ is StrongDual ℝ E with the operator norm, E∗∗E^{**}E∗∗ is StrongDual ℝ (StrongDual ℝ E), and E↪E∗∗E \hookrightarrow E^{**}E↪E∗∗ is NormedSpace.inclusionInDoubleDual. No reflexivity, inner product or finite dimension is assumed. Explicit readings:

  • Values in (−∞,+∞](-\infty, +\infty](−∞,+∞] are EReal with the requirement f(x)≠−∞f(x) \ne -\inftyf(x)=−∞; convexity is the paper's inequality for 0<λ<10 < \lambda < 10<λ<1 in EReal arithmetic. Lower semicontinuity is in the norm topology.
  • A multivalued map is E → Set (StrongDual ℝ E); T=∂fT = \partial fT=∂f means T(x)=∂f(x)T(x) = \partial f(x)T(x)=∂f(x) for every xxx.
  • The cycle inequality quantifies over all n∈Nn \in \mathbb{N}n∈N and points indexed by Fin (n + 1) with wrap-around addition, so the last term is ⟨xn−x0,xn∗⟩\langle x_n - x_0, x_n^* \rangle⟨xn​−x0​,xn∗​⟩. Maximality is graph inclusion among cyclically monotone operators, not among monotone operators.
  • The uniqueness constant is a real number, never ±∞\pm\infty±∞.
  • "⊃\supset⊃" in (3.6) is non-strict inclusion, and the hypothesis is one-sided.
  • A net is a nonempty directed partially ordered index type with convergence along atTop; weak** convergence is pointwise convergence on E∗E^*E∗; "bounded" is a uniform norm bound.
  • "Finite and continuous" for (f+j)∗(f+j)^*(f+j)∗ means equal everywhere to a continuous real-valued function. The max in (3.7) is IsGreatest, so it is attained; the directional derivative is the limit along λ→0+\lambda \to 0^+λ→0+.
  • The print's "∂(f+j)=∂f(x)+∂j(x)\partial(f + j) = \partial f(x) + \partial j(x)∂(f+j)=∂f(x)+∂j(x)" in (3.1) is read as ∂(f+j)(x)\partial(f+j)(x)∂(f+j)(x).

A formalization that drops lower semicontinuity, allows an extended-real constant, or replaces "maximal cyclically monotone" by "maximal monotone" states a different, and in the first two cases false or trivial, theorem; the statements here keep all three.

The proof reduces Theorem B to milestone 7 through Theorem 1 of Rockafellar (1966) and its Corollary 2, which are not stated in this paper and are not milestones; formal statements of them are welcome as supporting theorems. Contributions of reusable infrastructure are welcome: extended-valued subdifferentials and conjugates on normed spaces, the Fenchel–Moreau identity on EEE, the sum rule with a continuous function, and the max formula for directional derivatives.

Selected references

  • R. T. Rockafellar, On the maximal monotonicity of subdifferential mappings, Pacific J. Math. 33 (1970), 209–216. https://doi.org/10.2140/pjm.1970.33.209
  • R. T. Rockafellar, Characterization of the subdifferentials of convex functions, Pacific J. Math. 17 (1966), 497–510. https://doi.org/10.2140/pjm.1966.17.497
  • G. J. Minty, On the monotonicity of the gradient of a convex function, Pacific J. Math. 14 (1964), 243–247. https://doi.org/10.2140/pjm.1964.14.243
  • J.-J. Moreau, Fonctionnelles convexes, mimeographed lecture notes, Collège de France, 1967.
  • R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970. https://doi.org/10.1515/9781400873173
13 thms3 active usersReviewed
🏆Completed
AnalysisPartial Differential Equations·Captain: mikedeng1

Notes on Partial Differential Equations VIII: Strongly Continuous Semigroups and the Lumer–Phillips TheoremTextbook

Motivation

Many linear partial differential equations of evolution type — the heat equation, the Schrödinger equation, linear wave and Klein–Gordon equations, linearized reaction–diffusion and Kuramoto–Sivashinsky equations — can be written as an ordinary differential equation

ut=Au,u(0)=f,u_t = Au, \qquad u(0) = f,ut​=Au,u(0)=f,

in a Banach space XXX of functions, where AAA is a spatial differential operator. When AAA is bounded, the solution is the operator exponential etAfe^{tA}fetAf. Differential operators are unbounded, however, and then the solution operators f↦u(t)f \mapsto u(t)f↦u(t) are only continuous in time in the strong sense and may exist only forward in time. Semigroup theory makes this picture rigorous: it characterizes exactly which operators AAA generate a well-posed evolution, and it is the standard route from energy estimates to existence and uniqueness for linear and semilinear evolution equations (Duhamel's formula, §5.4.5 of the notes, used for the semilinear heat equation in §5.5).

This mission formalizes §5.4 of J. K. Hunter's Notes on Partial Differential Equations (UC Davis, revised 6/18/2014): uniformly continuous groups, strongly continuous semigroups and their generators, the Hille–Yosida theorem, the Lumer–Phillips theorem and Stone's theorem.

Timeline. The generation theorem for contraction semigroups is due independently to E. Hille (1948) and K. Yosida (1948); the general version with constants MMM, aaa to Feller, Miyadera and Phillips (1952–53). G. Lumer and R. S. Phillips (1961) recast the contraction case in terms of dissipative operators. Stone's theorem on one-parameter unitary groups dates from 1930–32. Standard modern accounts are Pazy (1983) and Engel–Nagel (2000).

Setting

Let XXX be a Banach space over K=R\mathbb{K} = \mathbb{R}K=R or C\mathbb{C}C, and L(X)\mathcal{L}(X)L(X) the Banach space of bounded linear operators on XXX with the operator norm.

A uniformly continuous group is a family {T(t):t∈R}⊂L(X)\{T(t) : t \in \mathbb{R}\} \subset \mathcal{L}(X){T(t):t∈R}⊂L(X) with T(0)=IT(0) = IT(0)=I, T(s)T(t)=T(s+t)T(s)T(t) = T(s+t)T(s)T(t)=T(s+t), and T(h)→IT(h) \to IT(h)→I in operator norm as h→0h \to 0h→0. A strongly continuous (C₀) semigroup is a family {T(t):t≥0}⊂L(X)\{T(t) : t \ge 0\} \subset \mathcal{L}(X){T(t):t≥0}⊂L(X) with T(0)=IT(0) = IT(0)=I, T(s)T(t)=T(s+t)T(s)T(t) = T(s+t)T(s)T(t)=T(s+t) for s,t≥0s, t \ge 0s,t≥0, and T(h)f→fT(h)f \to fT(h)f→f as h→0+h \to 0^+h→0+ for every f∈Xf \in Xf∈X; it is a contraction semigroup if ∥T(t)∥≤1\|T(t)\| \le 1∥T(t)∥≤1 for all t≥0t \ge 0t≥0. A C₀ group has the same properties for all s,t∈Rs, t \in \mathbb{R}s,t∈R; on a complex Hilbert space it is unitary if every T(t)T(t)T(t) is unitary.

An operator A:D(A)⊂X→XA : \mathcal{D}(A) \subset X \to XA:D(A)⊂X→X is a linear map defined on a subspace D(A)\mathcal{D}(A)D(A). The generator of a C₀ semigroup is the operator AAA whose domain is the set of fff for which

Af=lim⁡h→0+T(h)f−fhAf = \lim_{h \to 0^+} \frac{T(h)f - f}{h}Af=h→0+lim​hT(h)f−f​

exists in norm, with AfAfAf this limit. AAA is closed if its graph {(f,Af):f∈D(A)}\{(f, Af) : f \in \mathcal{D}(A)\}{(f,Af):f∈D(A)} is closed in X×XX \times XX×X, and densely defined if D(A)\mathcal{D}(A)D(A) is dense. A scalar λ\lambdaλ is in the resolvent set of AAA if λI−A:D(A)→X\lambda I - A : \mathcal{D}(A) \to XλI−A:D(A)→X is a bijection, and then R(λ,A)=(λI−A)−1R(\lambda, A) = (\lambda I - A)^{-1}R(λ,A)=(λI−A)−1 is the resolvent. AAA is dissipative if λ∥f∥≤∥(λI−A)f∥\lambda\|f\| \le \|(\lambda I - A)f\|λ∥f∥≤∥(λI−A)f∥ for all real λ>0\lambda > 0λ>0 and f∈D(A)f \in \mathcal{D}(A)f∈D(A), and m-dissipative if in addition λI−A\lambda I - AλI−A is onto XXX for some λ>0\lambda > 0λ>0. On a complex Hilbert space H\mathcal{H}H, AAA is self-adjoint if D(A)\mathcal{D}(A)D(A) is dense, D(A)=D(A∗)\mathcal{D}(A) = \mathcal{D}(A^*)D(A)=D(A∗), and (x,Ay)=(Ax,y)(x, Ay) = (Ax, y)(x,Ay)=(Ax,y) for x,y∈D(A)x, y \in \mathcal{D}(A)x,y∈D(A).

Formalization targets

Goal: the Lumer–Phillips theorem (Theorem 5.38)

For an operator A:D(A)⊂X→XA : \mathcal{D}(A) \subset X \to XA:D(A)⊂X→X,

A generates a C₀ contraction semigroup on X  ⟺  A is closed, densely defined and m-dissipative.A \text{ generates a C₀ contraction semigroup on } X \iff A \text{ is closed, densely defined and m-dissipative.}A generates a C₀ contraction semigroup on X⟺A is closed, densely defined and m-dissipative.

Milestones

  1. Theorem 5.24. A uniformly continuous group is smooth in operator norm, A=T′(0)∈L(X)A = T'(0) \in \mathcal{L}(X)A=T′(0)∈L(X) exists, and T(t)=etAT(t) = e^{tA}T(t)=etA for all t∈Rt \in \mathbb{R}t∈R.
  2. Theorem 5.32. The generator of a C₀ semigroup is closed and densely defined.
  3. Theorem 5.35 (Hille–Yosida). AAA generates a C₀ semigroup if and only if, for some M≥1M \ge 1M≥1 and a∈Ra \in \mathbb{R}a∈R, AAA is closed and densely defined, (a,∞)(a, \infty)(a,∞) lies in the resolvent set, and
∥R(λ,A)n∥≤M(λ−a)n(λ>a, n∈N);\|R(\lambda, A)^n\| \le \frac{M}{(\lambda - a)^n} \qquad (\lambda > a,\ n \in \mathbb{N});∥R(λ,A)n∥≤(λ−a)nM​(λ>a, n∈N);

in that case ∥T(t)∥≤Meat\|T(t)\| \le M e^{at}∥T(t)∥≤Meat for t≥0t \ge 0t≥0. 4. Corollary 5.36. The contraction case: M=1M = 1M=1, a=0a = 0a=0, with ∥R(λ,A)∥≤1/λ\|R(\lambda, A)\| \le 1/\lambda∥R(λ,A)∥≤1/λ. 5. Theorem 5.42 (Stone). On a complex Hilbert space, iAiAiA generates a C₀ unitary group if and only if AAA is self-adjoint.

Significance

The result itself. The Lumer–Phillips theorem is the working form of generation theory for PDEs: to show that ut=Auu_t = Auut​=Au is well posed with ∥u(t)∥≤∥u(0)∥\|u(t)\| \le \|u(0)\|∥u(t)∥≤∥u(0)∥, it suffices to prove an energy inequality (dissipativity) and to solve a single resolvent equation λf−Af=g\lambda f - Af = gλf−Af=g. The notes apply it to the Laplacian on H2(Rn)⊂L2(Rn)H^2(\mathbb{R}^n) \subset L^2(\mathbb{R}^n)H2(Rn)⊂L2(Rn) and, after a shift, to the linearized Kuramoto–Sivashinsky operator; later chapters use the resulting semigroups in Duhamel's formula to construct solutions of semilinear heat and Schrödinger equations. Hille–Yosida gives the general growth bound ∥T(t)∥≤Meat\|T(t)\| \le Me^{at}∥T(t)∥≤Meat, and Stone's theorem identifies unitary quantum dynamics with self-adjoint Hamiltonians.

Formalizing it. All results are classical and proved in the literature; the notes themselves state 5.32, 5.35, 5.36, 5.38 and 5.42 without proof, referring to standard texts. Mathlib currently has the operator exponential on Banach algebras, partially defined linear maps (LinearPMap) with closedness, closures and adjoints, but no theory of C₀ semigroups or their generators. A complete development would give Lean a reusable generation theory for unbounded operators, on which parabolic and dispersive PDE existence results can rest.

Difficulty

The central obstacle is the passage from resolvent information to a semigroup. Formally T(t)=etAT(t) = e^{tA}T(t)=etA, but for unbounded AAA the exponential series is meaningless, and the necessity directions require showing that the resolvent is a Laplace transform of the semigroup, which needs integration of strongly (not norm) continuous operator-valued functions. The sufficiency directions must construct a semigroup from AAA by an approximation of the unbounded generator and a limit that converges only strongly, and then identify the generator of the limit with AAA — including its domain, which is where most careless arguments fail. In the Lumer–Phillips theorem, surjectivity of λI−A\lambda I - AλI−A is assumed for a single λ>0\lambda > 0λ>0 and must be propagated to every λ>0\lambda > 0λ>0. In Stone's theorem both directions need domain arguments for unbounded operators on Hilbert space; symmetry of AAA alone is not enough.

Formalization scope

  • Scalars: a field 𝕜 with [RCLike 𝕜] (ℝ or ℂ), and X a Banach space over it ([NormedAddCommGroup X] [NormedSpace 𝕜 X] [CompleteSpace X]). Stone's theorem is over ℂ on an InnerProductSpace ℂ H with [CompleteSpace H]. Theorem 5.24 additionally equips X with a compatible real structure ([NormedSpace ℝ X] [IsScalarTower ℝ 𝕜 X]) so that t↦T(t)t \mapsto T(t)t↦T(t) can be differentiated; etAe^{tA}etA is Mathlib's NormedSpace.exp, and C∞C^\inftyC∞ is ContDiff ℝ ∞.
  • Operators A:D(A)⊂X→XA : \mathcal{D}(A) \subset X \to XA:D(A)⊂X→X are X →ₗ.[𝕜] X (LinearPMap); closedness is LinearPMap.IsClosed (closed graph).
  • Semigroups are functions T : ℝ → X →L[𝕜] X; for semigroups only the values at t≥0t \ge 0t≥0 enter. Composition is multiplication in X →L[𝕜] X.
  • The generator relation IsGenerator T A states, for all f,gf, gf,g: the right difference quotient h−1(T(h)f−f)h^{-1}(T(h)f - f)h−1(T(h)f−f) tends to ggg as h→0+h \to 0^+h→0+ if and only if f∈D(A)f \in \mathcal{D}(A)f∈D(A) and Af=gAf = gAf=g. So "AAA generates a semigroup" means that AAA equals the generator including its domain; a formalization in which AAA merely agrees with the limit on some subspace, or in which the generator is a restriction, would make the theorems different (and false) statements, and is ruled out.
  • Resolvent norm bounds ∥R(λ,A)n∥≤c\|R(\lambda, A)^n\| \le c∥R(λ,A)n∥≤c are stated pointwise, ∥R(λ,A)ng∥≤c∥g∥\|R(\lambda,A)^n g\| \le c\|g\|∥R(λ,A)ng∥≤c∥g∥ for all ggg, which is equivalent. In (5.24) n=0n = 0n=0 is included, which adds nothing because M≥1M \ge 1M≥1. The "in that case" clause of Theorem 5.35 is a second conjunct: for every semigroup generated by AAA and every M,aM, aM,a satisfying the three conditions, ∥T(t)∥≤Meat\|T(t)\| \le Me^{at}∥T(t)∥≤Meat.
  • Closedness and density, which the notes build into the definitions of the resolvent set and of dissipativity, are stated explicitly wherever they are used (they appear as condition (1) in every theorem).
  • The generator of a C₀ group (Stone) is the generator of its forward part, as in Definition 5.30; the operator iAiAiA is Complex.I • A, with the same domain as AAA. Self-adjointness is Definition 5.41 as printed, not Mathlib's IsSelfAdjoint for LinearPMap, although the two agree.
  • Useful infrastructure, reusable beyond this mission: Riemann/Bochner integration of strongly continuous operator families, the Laplace-transform representation of the resolvent, Yosida approximations, and dissipativity–resolvent equivalences. Contributions of any of these as separate lemmas are welcome.

Selected references

  • J. K. Hunter, Notes on Partial Differential Equations, UC Davis lecture notes, revised 6/18/2014, §5.4. https://www.math.ucdavis.edu/~hunter/pdes/pde_notes.pdf
  • A. Pazy, Semigroups of Linear Operators and Applications to Partial Differential Equations, Springer, 1983. https://doi.org/10.1007/978-1-4612-5561-1
  • K.-J. Engel and R. Nagel, One-Parameter Semigroups for Linear Evolution Equations, Springer GTM 194, 2000. https://doi.org/10.1007/b97696
  • G. Lumer and R. S. Phillips, Dissipative operators in a Banach space, Pacific J. Math. 11 (1961), 679–698. https://doi.org/10.2140/pjm.1961.11.679
  • M. H. Stone, On one-parameter unitary groups in Hilbert space, Ann. of Math. 33 (1932), 643–648. https://doi.org/10.2307/1968538
  • K. Yosida, On the differentiability and the representation of one-parameter semigroup of linear operators, J. Math. Soc. Japan 1 (1948), 15–21. https://doi.org/10.2969/jmsj/00110015
9 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

On the Maximal Monotonicity of Subdifferential Mappings I: The Subdifferential of a Lower Semicontinuous Proper Convex Function on a Banach Space Is Maximal MonotoneResearch Paper

Motivation

Monotone operators from a Banach space EEE to its dual E∗E^*E∗ are the abstract framework for nonlinear equations, variational inequalities and evolution equations, and for the convergence theory of proximal-point and splitting algorithms in infinite dimensions. Within that framework, the class that behaves well — for surjectivity results, for resolvents, for sums — is the class of maximal monotone operators. The most important source of such operators is convex analysis: the subdifferential of a convex function. Whether every subdifferential of a closed proper convex function is maximal monotone, in an arbitrary Banach space, is therefore a basic question for convex optimization in function spaces.

Timeline:

  • 1964. G. J. Minty proves maximality of the subdifferential for convex functions that are finite and continuous everywhere (Minty, Pacific J. Math. 14 (1964)).
  • 1965. A. Brøndsted and R. T. Rockafellar show that subgradients exist on a dense set and approximate ε-subgradients (Brøndsted–Rockafellar, Proc. AMS 16 (1965)). J.-J. Moreau develops proximal maps and conjugate duality for convex functions in Hilbert space (Moreau, Bull. SMF 93 (1965)); his later lecture notes Fonctionnelles convexes (Collège de France, 1967) are the paper's reference for conjugates in locally convex spaces.
  • 1966. R. T. Rockafellar announces the general Banach-space result, for every lower semicontinuous proper convex function (Rockafellar, Pacific J. Math. 17 (1966)). H. Brézis later points out a gap in that proof: a subgradient chosen in the argument may grow without bound.
  • 1970. Rockafellar gives a complete proof by a different route, valid in nonreflexive spaces, in the paper formalized here (Rockafellar, Pacific J. Math. 33 (1970)).

Setting

Let EEE be a real Banach space with dual E∗E^*E∗ and bidual E∗∗E^{**}E∗∗, and write ⟨x,x∗⟩=x∗(x)\langle x, x^*\rangle = x^*(x)⟨x,x∗⟩=x∗(x). EEE sits in E∗∗E^{**}E∗∗ through the canonical embedding.

A proper convex function on EEE is a function f:E→(−∞,+∞]f : E \to (-\infty, +\infty]f:E→(−∞,+∞], not identically +∞+\infty+∞, such that f((1−λ)x+λy)≤(1−λ)f(x)+λf(y)f((1-\lambda)x + \lambda y) \le (1-\lambda) f(x) + \lambda f(y)f((1−λ)x+λy)≤(1−λ)f(x)+λf(y) for all x,y∈Ex, y \in Ex,y∈E and 0<λ<10 < \lambda < 10<λ<1. It is lower semicontinuous for the norm topology.

The subdifferential of fff is the multivalued map ∂f:E→E∗\partial f : E \to E^*∂f:E→E∗,

∂f(x)={ x∗∈E∗∣f(y)≥f(x)+⟨y−x,x∗⟩  ∀y∈E }.\partial f(x) = \{\, x^* \in E^* \mid f(y) \ge f(x) + \langle y - x, x^* \rangle \ \ \forall y \in E \,\}.∂f(x)={x∗∈E∗∣f(y)≥f(x)+⟨y−x,x∗⟩  ∀y∈E}.

A multivalued map T:E→E∗T : E \to E^*T:E→E∗ is monotone if ⟨x0−x1,x0∗−x1∗⟩≥0\langle x_0 - x_1, x_0^* - x_1^* \rangle \ge 0⟨x0​−x1​,x0∗​−x1∗​⟩≥0 whenever x0∗∈T(x0)x_0^* \in T(x_0)x0∗​∈T(x0​) and x1∗∈T(x1)x_1^* \in T(x_1)x1∗​∈T(x1​). It is maximal monotone if, in addition, its graph {(x,x∗)∣x∗∈T(x)}\{(x, x^*) \mid x^* \in T(x)\}{(x,x∗)∣x∗∈T(x)} is not properly contained in the graph of any other monotone map T′:E→E∗T' : E \to E^*T′:E→E∗.

The conjugate of fff is f∗(x∗)=sup⁡x∈E{⟨x,x∗⟩−f(x)}f^*(x^*) = \sup_{x \in E} \{\langle x, x^*\rangle - f(x)\}f∗(x∗)=supx∈E​{⟨x,x∗⟩−f(x)}, a function on E∗E^*E∗; its subdifferential ∂f∗\partial f^*∂f∗ maps E∗E^*E∗ into E∗∗E^{**}E∗∗. Finally j(x)=12∥x∥2j(x) = \tfrac12 \|x\|^2j(x)=21​∥x∥2.

In Lean these are ProperConvex f, subdiff f, IsMonotoneOp T, IsMaximalMonotone T, conj f and halfSqNorm, all stated over an arbitrary real normed space V so that they apply equally to EEE and to E∗E^*E∗.

Formalization targets

Goal: Theorem A (p. 210)

f lower semicontinuous proper convex on E⟹∂f:E→E∗ is maximal monotone.f \text{ lower semicontinuous proper convex on } E \quad\Longrightarrow\quad \partial f : E \to E^* \text{ is maximal monotone.}f lower semicontinuous proper convex on E⟹∂f:E→E∗ is maximal monotone.

No reflexivity, inner product or finite dimension is assumed.

Milestones, in attack order

  1. (2.2) Fenchel–Young: f(x)+f∗(x∗)≥⟨x,x∗⟩f(x) + f^*(x^*) \ge \langle x, x^* \ranglef(x)+f∗(x∗)≥⟨x,x∗⟩, with equality iff x∗∈∂f(x)x^* \in \partial f(x)x∗∈∂f(x).
  2. §2, p. 210. f∗f^*f∗ is a weak* lower semicontinuous (hence strongly lower semicontinuous) proper convex function on E∗E^*E∗.
  3. §2, p. 211. The restriction of f∗∗f^{**}f∗∗ to EEE is fff.
  4. Proposition 1. x∗∗∈∂f∗(x∗)x^{**} \in \partial f^*(x^*)x∗∗∈∂f∗(x∗) iff there are a net xi∗→x∗x_i^* \to x^*xi∗​→x∗ in norm and a bounded net xi→x∗∗x_i \to x^{**}xi​→x∗∗ weak**, on one directed index set, with xi∗∈∂f(xi)x_i^* \in \partial f(x_i)xi∗​∈∂f(xi​).
  5. (3.1) ∂(f+j)(x)=∂f(x)+∂j(x)\partial(f + j)(x) = \partial f(x) + \partial j(x)∂(f+j)(x)=∂f(x)+∂j(x) for all x∈Ex \in Ex∈E.
  6. §3, p. 213. (f+j)∗(f + j)^*(f+j)∗ is finite and continuous throughout E∗E^*E∗.
  7. §3, p. 213 (Minty). On any real Banach space, a convex function that is finite and continuous everywhere has a maximal monotone subdifferential.

Significance

Theorem A places every closed proper convex function in the maximal monotone class, in every real Banach space. Downstream, it is what allows convex minimization problems to be treated by the general theory: surjectivity of ∂f+λJ\partial f + \lambda J∂f+λJ (with JJJ the duality map) in reflexive spaces, existence for evolution equations governed by subdifferentials, the definition of resolvents and proximal maps, and the convergence of proximal-point and splitting methods for convex problems. Proposition 1 is of independent interest: in a nonreflexive space ∂f∗\partial f^*∂f∗ is not the inverse of ∂f\partial f∂f, but it is still completely determined by ∂f\partial f∂f through bounded weak** nets.

The theorem is classical and fully proved in the literature. What this mission adds is a machine-checked proof of the nonreflexive Banach-space statement, together with the infrastructure it needs: extended-real-valued proper convex functions, the subdifferential and the conjugate on a normed space and its dual, monotone and maximal monotone operators, and the Fenchel–Moreau identity f∗∗∣E=ff^{**}|_E = ff∗∗∣E​=f. None of these exists in Mathlib at the pinned revision, and Mathlib contains no statement of Theorem A, in Hilbert or in Banach spaces.

Difficulty

Monotonicity of ∂f\partial f∂f follows in two lines from the definition; the whole difficulty is maximality. In a Hilbert space the standard argument solves x+∂f(x)∋yx + \partial f(x) \ni yx+∂f(x)∋y by minimizing f+12∥⋅−y∥2f + \tfrac12\|\cdot - y\|^2f+21​∥⋅−y∥2 and uses the identification of EEE with E∗E^*E∗; in a general Banach space there is no such identification, and minimizers need not exist without reflexivity. The 1966 argument tried to approximate subgradients of fff at nearby points, and it failed because those subgradients could become unbounded as the approximation was refined. Any argument that passes through the dual meets a second obstacle: ∂f∗\partial f^*∂f∗ takes values in the bidual E∗∗E^{**}E∗∗, which is strictly larger than EEE when EEE is not reflexive, so ∂f∗\partial f^*∂f∗ is not the inverse of ∂f\partial f∂f. Relating the two is the content of Proposition 1, and its necessity half requires approximation results well beyond the definitions.

Formalization scope

Lean representation and committed conventions:

  • EEE is a real Banach space: NormedAddCommGroup E, NormedSpace ℝ E, CompleteSpace E. E∗E^*E∗ is StrongDual ℝ E with the operator norm; the pairing ⟨x,x∗⟩\langle x, x^*\rangle⟨x,x∗⟩ is x' x; E∗∗E^{**}E∗∗ is StrongDual ℝ (StrongDual ℝ E) and E↪E∗∗E \hookrightarrow E^{**}E↪E∗∗ is NormedSpace.inclusionInDoubleDual ℝ E.
  • The value set (−∞,+∞](-\infty,+\infty](−∞,+∞] is EReal with the clause "never ⊥\bot⊥". Properness also requires some value ≠⊤\ne \top=⊤. Convexity is the paper's inequality for 0<λ<10 < \lambda < 10<λ<1, computed in EReal.
  • Multivalued maps are V → Set (StrongDual ℝ V). Maximality is graph inclusion, quantified over every monotone T', not only over subdifferentials.
  • The conjugate is an EReal supremum over all of VVV; the biconjugate is conj (conj f) on the bidual.
  • (2.2) is stated as ⟨x,x∗⟩≤f(x)+f∗(x∗)\langle x, x^*\rangle \le f(x) + f^*(x^*)⟨x,x∗⟩≤f(x)+f∗(x∗) with the equality case, avoiding EReal subtraction.
  • Weak* lower semicontinuity of f∗f^*f∗ is lower semicontinuity on WeakDual ℝ E.
  • In Proposition 1 a net is a map from a nonempty, directed, partially ordered index type (in the universe of EEE), with convergence along atTop. Weak** convergence is pointwise convergence on E∗E^*E∗ of the canonical images, which is convergence in the weak topology induced on E∗∗E^{**}E∗∗ by E∗E^*E∗. Boundedness is a uniform norm bound.
  • (3.1) reads the printed ∂(f+j)\partial(f+j)∂(f+j) as ∂(f+j)(x)\partial(f+j)(x)∂(f+j)(x); the right side is the pointwise (Minkowski) set sum.
  • "Finite and continuous" for (f+j)∗(f+j)^*(f+j)∗ is the existence of a continuous real-valued hhh on E∗E^*E∗ equal to it everywhere.
  • Minty's case is stated for an arbitrary real Banach space VVV, because the proof applies it on E∗E^*E∗.

A trivializing formalization is ruled out: properness excludes f≡+∞f \equiv +\inftyf≡+∞ (whose empty subdifferential is monotone but not maximal) and −∞-\infty−∞ values, maximality ranges over all monotone operators, and the index set in Proposition 1 is nonempty and directed so that no convergence statement holds vacuously.

Infrastructure needed and reusable beyond this mission: extended-real convex analysis on normed spaces (conjugates, the Fenchel–Moreau theorem via Hahn–Banach separation, lower semicontinuity in the weak and weak* topologies), subdifferential calculus for a sum with a continuous function, nets and weak** approximation in the bidual (Goldstine-type arguments), and the Brøndsted–Rockafellar approximation of ε-subgradients. Contributions are welcome at every milestone; the definitions layer and milestones 1–3 are the natural starting points.

Selected references

  • R. T. Rockafellar, On the maximal monotonicity of subdifferential mappings, Pacific Journal of Mathematics 33 (1970), 209–216. https://doi.org/10.2140/pjm.1970.33.209
  • R. T. Rockafellar, Characterization of the subdifferentials of convex functions, Pacific Journal of Mathematics 17 (1966), 497–510. https://doi.org/10.2140/pjm.1966.17.497
  • G. J. Minty, On the monotonicity of the gradient of a convex function, Pacific Journal of Mathematics 14 (1964), 243–247. https://doi.org/10.2140/pjm.1964.14.243
  • J.-J. Moreau, Proximité et dualité dans un espace hilbertien, Bulletin de la Société Mathématique de France 93 (1965), 273–299. https://doi.org/10.24033/bsmf.1625
  • A. Brøndsted and R. T. Rockafellar, On the subdifferentiability of convex functions, Proceedings of the American Mathematical Society 16 (1965), 605–611. https://doi.org/10.1090/S0002-9939-1965-0178103-8
13 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization: The IFB Iterates Minimize the Objective and Converge Weakly to a MinimizerResearch Paper

Motivation

Many problems in signal processing, statistics and operations research ask to minimize a sum Θ=Φ+Ψ\Theta = \Phi + \PsiΘ=Φ+Ψ of a nonsmooth convex term Φ\PhiΦ (a constraint indicator, an ℓ1\ell^1ℓ1 penalty) and a smooth term Ψ\PsiΨ. The standard method is the forward-backward (proximal-gradient) algorithm: an explicit gradient step on Ψ\PsiΨ followed by a proximal step on Φ\PhiΦ. Its classical convergence theory requires Ψ\PsiΨ to be convex and the step size to stay below 2/LΨ2/L_\Psi2/LΨ​, where LΨL_\PsiLΨ​ is the Lipschitz constant of ∇Ψ\nabla\Psi∇Ψ.

Attouch, Peypouquet and Redont (authors' manuscript of SIAM J. Optim. 24 (2014)) derive an inertial forward-backward algorithm (IFB) as a time discretization of a second-order dissipative dynamical system with Hessian-driven damping. The added inertial terms cost essentially nothing to compute, yet they allow step sizes beyond 2/LΨ2/L_\Psi2/LΨ​ and a smooth part Ψ\PsiΨ that is not convex, provided the sum Θ\ThetaΘ is.

Timeline of the relevant results:

  • Heavy-ball-with-friction methods, the inertial discretizations of u¨+αu˙+∇Φ(u)=0\ddot u + \alpha\dot u + \nabla\Phi(u) = 0u¨+αu˙+∇Φ(u)=0, were introduced by Polyak (1964) and developed by Alvarez and Attouch (2001) for proximal schemes.
  • Hessian-driven damping for one potential: Alvarez, Attouch, Bolte and Redont (2002); for a nonsmooth potential plus a smooth one, the continuous dynamics underlying (IFB): Attouch, Maingé and Redont (2012).
  • The discrete algorithm (IFB) and its weak convergence in Hilbert spaces: Attouch, Peypouquet and Redont (2014), the paper of this mission.

Setting

Let HHH be a real Hilbert space with inner product ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle⟨⋅,⋅⟩. Let Φ:H→R∪{+∞}\Phi : H \to \mathbb R\cup\{+\infty\}Φ:H→R∪{+∞} and Ψ:H→R\Psi : H \to \mathbb RΨ:H→R, and write Θ=Φ+Ψ\Theta = \Phi + \PsiΘ=Φ+Ψ and S=Argmin⁡Θ\mathcal S = \operatorname{Argmin}\ThetaS=ArgminΘ. A vector ggg is a subgradient of Φ\PhiΦ at uuu, written g∈∂Φ(u)g \in \partial\Phi(u)g∈∂Φ(u), if Φ(u)<+∞\Phi(u) < +\inftyΦ(u)<+∞ and Φ(u)+⟨g,v−u⟩≤Φ(v)\Phi(u) + \langle g, v - u\rangle \le \Phi(v)Φ(u)+⟨g,v−u⟩≤Φ(v) for all vvv.

Hypothesis H fixes positive constants LΨL_\PsiLΨ​, aaa, bbb and a step size λ\lambdaλ with:

  • HΦH_\PhiHΦ​: Φ\PhiΦ is proper, lower semicontinuous and convex;
  • HΨH_\PsiHΨ​: Ψ\PsiΨ is differentiable and ∇Ψ\nabla\Psi∇Ψ is LΨL_\PsiLΨ​-Lipschitz;
  • HλH_\lambdaHλ​: 0<λ<Λ=min⁡{1/a, 2(a+b)/(bLΨ)}0 < \lambda < \Lambda = \min\{1/a,\ 2(a+b)/(bL_\Psi)\}0<λ<Λ=min{1/a, 2(a+b)/(bLΨ​)};
  • HΘH_\ThetaHΘ​: Θ\ThetaΘ is convex and bounded from below.

Algorithm (IFB). From any (u0,y0)∈H×H(u_0, y_0) \in H \times H(u0​,y0​)∈H×H, compute for k≥0k \ge 0k≥0

0∈uk+1−ukλ+∂Φ(uk+1)+auk−byk,0=yk+1−ykλ+∇Ψ(uk+1)−auk+1+byk+1.0 \in \frac{u_{k+1}-u_k}{\lambda} + \partial\Phi(u_{k+1}) + a u_k - b y_k, \qquad 0 = \frac{y_{k+1}-y_k}{\lambda} + \nabla\Psi(u_{k+1}) - a u_{k+1} + b y_{k+1}.0∈λuk+1​−uk​​+∂Φ(uk+1​)+auk​−byk​,0=λyk+1​−yk​​+∇Ψ(uk+1​)−auk+1​+byk+1​.

A sequence uku_kuk​ converges weakly to ppp, written uk⇀pu_k \rightharpoonup puk​⇀p, if ⟨uk,v⟩→⟨p,v⟩\langle u_k, v\rangle \to \langle p, v\rangle⟨uk​,v⟩→⟨p,v⟩ for every v∈Hv \in Hv∈H. The analysis uses the velocity ξk=uk−uk−1\xi_k = u_k - u_{k-1}ξk​=uk​−uk−1​, the energy Ek=Θ(uk)+γ∥ξk∥2E_k = \Theta(u_k) + \gamma\|\xi_k\|^2Ek​=Θ(uk​)+γ∥ξk​∥2 with γ=(1−aλ)/(2bλ2)\gamma = (1-a\lambda)/(2b\lambda^2)γ=(1−aλ)/(2bλ2), and two auxiliary real sequences Gk(q)G_k(q)Gk​(q) and Fk(q)F_k(q)Fk​(q), defined from uuu, yyy and a reference point qqq by (17) and (18) of the paper.

Formalization targets

Goal: Theorem 1

Under Hypothesis H, for every sequence generated by (IFB),

lim⁡k→∞Θ(uk)=inf⁡Θ;\lim_{k\to\infty}\Theta(u_k) = \inf\Theta;k→∞lim​Θ(uk​)=infΘ;

if S≠∅\mathcal S \ne \emptysetS=∅ and one of (i) S\mathcal SS is a singleton, (ii) Φ\PhiΦ is differentiable with weak-to-weak sequentially continuous gradient, (iii) ∇Ψ\nabla\Psi∇Ψ is weak-to-weak sequentially continuous, (iv) Ψ\PsiΨ is convex, holds, then

uk⇀pfor some p∈S;u_k \rightharpoonup p \quad\text{for some } p \in \mathcal S;uk​⇀pfor some p∈S;

and if S=∅\mathcal S = \emptysetS=∅, then ∥uk∥→+∞\|u_k\| \to +\infty∥uk​∥→+∞.

Milestones

In the order of the paper's argument: Proposition 2 (energy decrease, ∑∥ξk∥2<∞\sum\|\xi_k\|^2 < \infty∑∥ξk​∥2<∞); Proposition 3 (the identity and inequality (19) for Fk(q)F_k(q)Fk​(q)); Proposition 4 (Gk(q)G_k(q)Gk​(q) is bounded above for q∈dom⁡Φq\in\operatorname{dom}\Phiq∈domΦ); the lower bound (28) on Fk(q)F_k(q)Fk​(q); Lemma 5 (a real-sequence lemma); Proposition 6 (Θ(uk)→inf⁡Θ\Theta(u_k)\to\inf\ThetaΘ(uk​)→infΘ, weak cluster points lie in S\mathcal SS); Lemma 7 (a boundedness lemma); Proposition 8 (boundedness of (uk)(u_k)(uk​) and convergence of Fk(q)F_k(q)Fk​(q) when S≠∅\mathcal S \ne\emptysetS=∅).

Significance

The result gives convergence of a forward-backward type method under a step-size bound Λ\LambdaΛ that can be made arbitrarily large by choosing aaa small, and for a smooth term Ψ\PsiΨ that need not be convex. The special case Φ=δC\Phi = \delta_CΦ=δC​ (indicator of a closed convex set) yields an inertial gradient-projection method, and the paper applies the theorem to feasibility problems, the CQ algorithm, Pareto fronts and ℓ1\ell^1ℓ1 signal recovery.

The theorem is proved in the paper; to our knowledge it is not formalized anywhere. A complete formalization would provide a machine-checked Liapunov analysis of an inertial proximal method in an infinite-dimensional Hilbert space, including the passage from a minimizing sequence to weak convergence. The milestones Proposition 2, 3 and 8 are energy estimates that also underlie other inertial and proximal schemes.

Difficulty

The energy EkE_kEk​ controls the values Θ(uk)\Theta(u_k)Θ(uk​) and the velocities ξk\xi_kξk​, but not the iterates themselves. The first idea, proving that ∥uk−q∥\|u_k - q\|∥uk​−q∥ is nonincreasing for every q∈Sq \in \mathcal Sq∈S (Fejér monotonicity, the standard route for the classical forward-backward method), does not come out of the energy estimates for (IFB): the inertial variable yky_kyk​ couples consecutive steps, and the distance to a minimizer is not a Liapunov function. The paper's replacement, the sequence Fk(q)F_k(q)Fk​(q), carries the auxiliary sum Gk(q)G_k(q)Gk​(q), whose upper bound already requires the full Hypothesis H. Because HHH is infinite-dimensional, bounded sequences have only weakly convergent subsequences, so the minimizing property has to pass through weak lower semicontinuity of Θ\ThetaΘ, and the final step, uniqueness of the weak cluster point, needs a separate argument in each of the cases (i)–(iv) together with Opial's lemma, which is not in Mathlib.

Formalization scope

  • HHH is a general real Hilbert space (InnerProductSpace ℝ H with CompleteSpace H); nothing is specialized to finite dimension.
  • Φ\PhiΦ and Θ\ThetaΘ take values in EReal. Properness excludes −∞-\infty−∞. Convexity of an extended-valued function is convexity of its epigraph in H×RH\times\mathbb RH×R, because Mathlib's ConvexOn needs a scalar action that EReal lacks. The subgradient predicate requires Φ(u)<+∞\Phi(u) < +\inftyΦ(u)<+∞, so ∂Φ(u)=∅\partial\Phi(u) = \emptyset∂Φ(u)=∅ off dom⁡Φ\operatorname{dom}\PhidomΦ.
  • (IFB) is encoded as the subgradient inclusion, not through the proximity operator. Weak convergence is convergence of all inner products ⟨uk,v⟩\langle u_k, v\rangle⟨uk​,v⟩; weak cluster points are weak limits along strictly increasing subsequences.
  • LΨ>0L_\Psi > 0LΨ​>0 is assumed (harmless: a Lipschitz gradient is Lipschitz with every larger constant). The step size λ\lambdaλ is written lam.
  • ξk\xi_kξk​, zkz_kzk​, EkE_kEk​, GkG_kGk​, FkF_kFk​ are defined on all natural indices, and each statement quantifies k≥1k \ge 1k≥1 (or k≥2k \ge 2k≥2 for GkG_kGk​) as the paper does. Energies and values are never truncated to real numbers, so no statement becomes true through the convention EReal.toReal ⊤ = 0.
  • Deviation from the printed text: Proposition 4 is printed under HΦH_\PhiHΦ​ and HΨH_\PsiHΨ​ only, but its proof invokes Proposition 2, which needs all of Hypothesis H, and the printed statement is false for step sizes above Λ\LambdaΛ (e.g. H=RH=\mathbb RH=R, Φ=x2/2\Phi = x^2/2Φ=x2/2, Ψ=3x2/2\Psi = 3x^2/2Ψ=3x2/2, a=2a=2a=2, b=0.02b=0.02b=0.02, λ=10\lambda = 10λ=10). The milestone is stated under the full Hypothesis H.
  • A formalization in which ∂Φ(u)\partial\Phi(u)∂Φ(u) is nonempty at points of infinite value, in which the energy is converted to a real number, or in which Hypothesis H cannot be satisfied, would make these statements trivial or vacuous, and is ruled out by the definitions above.

A complete development needs Opial's lemma, weak sequential compactness of bounded sets in Hilbert space, weak lower semicontinuity of lower semicontinuous convex functions, the descent lemma for functions with Lipschitz gradient, and monotonicity of the subdifferential. These are reusable well beyond this mission; contributions of any of them, and of the milestones in any order, are welcome.

Selected references

  • H. Attouch, J. Peypouquet, P. Redont, A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization, SIAM J. Optim. 24(1), 2014 (statements cited from the authors' manuscript of Aug 2013). https://doi.org/10.1137/130910294
  • H. Attouch, P.-E. Maingé, P. Redont, A second-order differential system with Hessian-driven damping; application to non-elastic shock laws, Differential Equations and Applications 4(1), 2012. https://doi.org/10.7153/dea-04-02
  • F. Alvarez, H. Attouch, An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Analysis 9, 2001. https://doi.org/10.1023/A:1011253113155
  • F. Alvarez, H. Attouch, J. Bolte, P. Redont, A second-order gradient-like dissipative dynamical system with Hessian-driven damping, J. Math. Pures Appl. 81(8), 2002. https://doi.org/10.1016/S0021-7824(01)01253-3
  • B. T. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math. Phys. 4(5), 1964. https://doi.org/10.1016/0041-5553(64)90137-5
  • Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc. 73, 1967. https://doi.org/10.1090/S0002-9904-1967-11761-0
12 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

A Three-Operator Splitting Scheme and its Optimization Applications 3: Accelerated Convergence under Strong MonotonicityResearch Paper

Motivation

Many problems in convex optimization, variational inequalities and signal processing reduce to finding a zero of a sum of three monotone operators, one of which is single-valued and smooth. Davis and Yin (Set-Valued Var. Anal. 25, 2017) introduced a splitting scheme that evaluates each of the three operators separately: the two set-valued ones through their resolvents, the single-valued one through a forward step. With a fixed stepsize, their Algorithm 1 converges weakly but can be slow: the paper's Section 3.4 constructs examples where the squared distance of the iterates to the solution decays no faster than (k+1)−(1+ϵ)(k+1)^{-(1+\epsilon)}(k+1)−(1+ϵ) for every ϵ>0\epsilon > 0ϵ>0.

When one of the operators is strongly monotone (for example the subdifferential of a strongly convex function), first-order splitting methods can be accelerated by letting the stepsize shrink like 1/k1/k1/k; the paper relates its stepsizes to those of Chambolle and Pock's accelerated primal–dual method (J. Math. Imaging Vis. 40, 2011, Algorithm 2) and of Boţ, Csetnek, Heinrich and Hendrich (Math. Program. 150, 2015, Algorithm 5). Section 3.3 of Davis–Yin carries this device over to three-operator splitting and obtains an O(1/(k+1)2)O(1/(k+1)^2)O(1/(k+1)2) rate for the squared distance. This mission formalizes that result.

Setting

Let HHH be a real Hilbert space. A set-valued operator A:H→2HA : H \to 2^HA:H→2H is monotone if ⟨x−y,u−v⟩≥0\langle x - y, u - v\rangle \ge 0⟨x−y,u−v⟩≥0 for all u∈Axu \in Axu∈Ax, v∈Ayv \in Ayv∈Ay, and maximal monotone if its graph is not properly contained in the graph of another monotone operator. It is μ\muμ-strongly monotone if ⟨x−y,u−v⟩≥μ∥x−y∥2\langle x - y, u - v\rangle \ge \mu\|x-y\|^2⟨x−y,u−v⟩≥μ∥x−y∥2 for all such pairs. A single-valued C:H→HC : H \to HC:H→H is β\betaβ-cocoercive if β∥Cx−Cy∥2≤⟨Cx−Cy,x−y⟩\beta\|Cx - Cy\|^2 \le \langle Cx - Cy, x - y\rangleβ∥Cx−Cy∥2≤⟨Cx−Cy,x−y⟩, and LCL_CLC​-Lipschitz if ∥Cx−Cy∥≤LC∥x−y∥\|Cx - Cy\| \le L_C\|x - y\|∥Cx−Cy∥≤LC​∥x−y∥.

The problem is to find x∗∈zer⁡(A+B+C)x^* \in \operatorname{zer}(A + B + C)x∗∈zer(A+B+C), that is, 0∈Ax∗+Bx∗+Cx∗0 \in Ax^* + Bx^* + Cx^*0∈Ax∗+Bx∗+Cx∗, where AAA, BBB are maximal monotone and CCC is monotone and single-valued. For γ>0\gamma > 0γ>0 the resolvent JγA=(I+γA)−1J_{\gamma A} = (I + \gamma A)^{-1}JγA​=(I+γA)−1 is the map with x∈JγAx+γA(JγAx)x \in J_{\gamma A}x + \gamma A(J_{\gamma A}x)x∈JγA​x+γA(JγA​x).

Algorithm 3 fixes stepsizes (γk)k≥0⊆(0,∞)(\gamma_k)_{k\ge 0} \subseteq (0,\infty)(γk​)k≥0​⊆(0,∞) and an initial point xA0∈Hx_A^0 \in HxA0​∈H, sets xB0=Jγ0B(xA0)x_B^0 = J_{\gamma_0 B}(x_A^0)xB0​=Jγ0​B​(xA0​), uB0=γ0−1(xA0−xB0)u_B^0 = \gamma_0^{-1}(x_A^0 - x_B^0)uB0​=γ0−1​(xA0​−xB0​), and iterates for k≥0k \ge 0k≥0

xBk+1=JγkB(xAk+γkuBk),uBk+1=1γk(xAk+γkuBk−xBk+1),xAk+1=Jγk+1A(xBk+1−γk+1uBk+1−γk+1CxBk+1).x_B^{k+1} = J_{\gamma_k B}(x_A^k + \gamma_k u_B^k),\quad u_B^{k+1} = \tfrac{1}{\gamma_k}(x_A^k + \gamma_k u_B^k - x_B^{k+1}),\quad x_A^{k+1} = J_{\gamma_{k+1}A}(x_B^{k+1} - \gamma_{k+1}u_B^{k+1} - \gamma_{k+1}Cx_B^{k+1}).xBk+1​=Jγk​B​(xAk​+γk​uBk​),uBk+1​=γk​1​(xAk​+γk​uBk​−xBk+1​),xAk+1​=Jγk+1​A​(xBk+1​−γk+1​uBk+1​−γk+1​CxBk+1​).

The stepsize changes in the middle of an iteration. Two stepsize rules are considered, each defined recursively from γ0\gamma_0γ0​:

(3.6)γk+1=−2γk2μCη+(2γk2μCη)2+4(1+2γkμB)γk22(1+2γkμB),(3.7)γk+1=γk1+2γk(μB−γkLC2/2).\text{(3.6)}\quad \gamma_{k+1} = \frac{-2\gamma_k^2\mu_C\eta + \sqrt{(2\gamma_k^2\mu_C\eta)^2 + 4(1+2\gamma_k\mu_B)\gamma_k^2}}{2(1+2\gamma_k\mu_B)}, \qquad \text{(3.7)}\quad \gamma_{k+1} = \frac{\gamma_k}{\sqrt{1 + 2\gamma_k(\mu_B - \gamma_kL_C^2/2)}}.(3.6)γk+1​=2(1+2γk​μB​)−2γk2​μC​η+(2γk2​μC​η)2+4(1+2γk​μB​)γk2​​​,(3.7)γk+1​=1+2γk​(μB​−γk​LC2​/2)​γk​​.

Formalization targets

Goal: Theorem 3.3, both parts

Let BBB be μB\mu_BμB​-strongly monotone with μB≥0\mu_B \ge 0μB​≥0.

  1. If CCC is β\betaβ-cocoercive and μC\mu_CμC​-strongly monotone (μC>0\mu_C > 0μC​>0), η∈(0,1)\eta \in (0,1)η∈(0,1), γ0∈(0,2β(1−η))\gamma_0 \in (0, 2\beta(1-\eta))γ0​∈(0,2β(1−η)) and the stepsizes follow (3.6), then for every x∗∈zer⁡(A+B+C)x^* \in \operatorname{zer}(A+B+C)x∗∈zer(A+B+C)
∃K ∀k≥0:∥xBk−x∗∥2≤K(k+1)2.\exists K\ \forall k \ge 0:\quad \|x_B^k - x^*\|^2 \le \frac{K}{(k+1)^2}.∃K ∀k≥0:∥xBk​−x∗∥2≤(k+1)2K​.
  1. If CCC is LCL_CLC​-Lipschitz, μB>0\mu_B > 0μB​>0, γ0∈(0,2μB/LC2)\gamma_0 \in (0, 2\mu_B/L_C^2)γ0​∈(0,2μB​/LC2​) and the stepsizes follow (3.7), the same conclusion holds.

The goal asserts the shape of the rate only; the constant KKK is not fixed.

Milestones

  • Proposition 3.1, Parts 1 and 2: the one-step inequalities (3.9) and (3.10) for Algorithm 3 with arbitrary admissible stepsizes.
  • Stepsize facts from the proof of Theorem 3.3: the identities that make (3.9) and (3.10) telescope, the monotonicity of the stepsizes (3.6), and the limits (k+1)γk→1/(μCη+μB)(k+1)\gamma_k \to 1/(\mu_C\eta + \mu_B)(k+1)γk​→1/(μC​η+μB​) for (3.6) and (k+1)γk→1/μB(k+1)\gamma_k \to 1/\mu_B(k+1)γk​→1/μB​ for (3.7).

Significance

The theorem shows that strong monotonicity of BBB or CCC can be converted into a quadratically decaying distance bound without knowledge of the solution, with stepsizes that are computable from the strong monotonicity and cocoercivity (or Lipschitz) constants alone. Since the rate is established for xBkx_B^kxBk​, it applies directly to splitting schemes for strongly convex composite problems min⁡f+g+h\min f + g + hminf+g+h with hhh smooth, where xBkx_B^kxBk​ is the proximal point of ggg.

The result is proved in the paper; no machine-checked version is known. The formalization adds a precise statement of the admissible parameter ranges, a check of the index conventions of a scheme whose stepsize changes mid-iteration, and a correction of the one-step inequalities at the first iteration (see Formalization scope). The stepsize limits are statements about explicit real recursions and are of independent use for other accelerated schemes.

Difficulty

The one-step inequalities (3.9) and (3.10) are long but elementary chains of inner-product identities and Young's inequality; the work lies in bookkeeping two stepsizes per iteration. The rate itself does not follow from the one-step inequality alone: telescoping gives a bound of the form ∥xBk−x∗∥2≲γk2\|x_B^{k}-x^*\|^2 \lesssim \gamma_k^2∥xBk​−x∗∥2≲γk2​, and one must then show γk\gamma_kγk​ decays exactly like 1/k1/k1/k. The rules (3.6) and (3.7) are nonlinear recursions without closed form, so their asymptotics require a Stolz–Cesàro type argument, which is not available in Mathlib under that name. Choosing a stepsize sequence of the form c/kc/kc/k instead is a different algorithm and not covered by the theorem.

Formalization scope

  • HHH is an arbitrary real Hilbert space (InnerProductSpace ℝ H, CompleteSpace H), not a Euclidean space.
  • Resolvents are not constructed. They are families JA JB : ℝ → H → H required to satisfy the resolvent inclusion γ−1(x−J(γ)x)∈A(J(γ)x)\gamma^{-1}(x - J(\gamma)x) \in A(J(\gamma)x)γ−1(x−J(γ)x)∈A(J(γ)x) for every γ>0\gamma > 0γ>0; for maximal monotone operators such maps exist and are unique, so nothing is lost.
  • Algorithm 3 is a single recursive definition of the triple (xAk,xBk,uBk)(x_A^k, x_B^k, u_B^k)(xAk​,xBk​,uBk​) from xA0x_A^0xA0​, the stepsizes, the resolvent families and CCC; the paper's loop index k=1,2,…k = 1, 2, \dotsk=1,2,… matches recursion (3.8) shifted by one.
  • The stepsize rules (3.6) and (3.7) are recursive real sequences, used verbatim; each theorem assumes the paper's parameter ranges.
  • O(1/(k+1)2)O(1/(k+1)^2)O(1/(k+1)2) is rendered as ∃K ∀k, ∥xBk−x∗∥2≤K/(k+1)2\exists K\,\forall k,\ \|x_B^k - x^*\|^2 \le K/(k+1)^2∃K∀k, ∥xBk​−x∗∥2≤K/(k+1)2, with KKK chosen after all data (initial point, operators, constants, γ0\gamma_0γ0​, x∗x^*x∗) and before kkk. No explicit constant is stated.
  • Strong monotonicity of CCC means μC>0\mu_C > 0μC​>0; only μB=0\mu_B = 0μB​=0 is allowed, as on the page. With μB=μC=0\mu_B = \mu_C = 0μB​=μC​=0 rule (3.6) keeps γk\gamma_kγk​ constant and the rate fails, so a formalization allowing μC=0\mu_C = 0μC​=0 would be false. In Part 2, LC>0L_C > 0LC​>0 is assumed so that the stepsize interval is meaningful, and CCC is assumed monotone, as in problem (1.1) and as used in the paper's proof of (3.10).
  • The paper states (3.9) and (3.10) for all k≥0k \ge 0k≥0; at k=0k = 0k=0 the initial point xA0x_A^0xA0​ is not a resolvent output, and both inequalities fail in general. The milestones state them for k≥1k \ge 1k≥1. Theorem 3.3 is unaffected, since finitely many initial terms do not change an O(⋅)O(\cdot)O(⋅) bound.
  • The display γk2−γk+12=γkγk+1(2γkμB+2γk+1μCη)\gamma_k^2 - \gamma_{k+1}^2 = \gamma_k\gamma_{k+1}(2\gamma_k\mu_B + 2\gamma_{k+1}\mu_C\eta)γk2​−γk+12​=γk​γk+1​(2γk​μB​+2γk+1​μC​η) on p. 845 has γk\gamma_kγk​ and γk+1\gamma_{k+1}γk+1​ swapped inside the bracket; the milestone states the corrected identity γkγk+1(2γk+1μB+2γkμCη)\gamma_k\gamma_{k+1}(2\gamma_{k+1}\mu_B + 2\gamma_k\mu_C\eta)γk​γk+1​(2γk+1​μB​+2γk​μC​η).
  • A trivializing formalization, such as one in which the resolvent hypothesis is unsatisfiable, the stepsize interval is empty, or the rate constant may depend on kkk, is ruled out: the hypotheses are met by A=0A = 0A=0, B=μBIB = \mu_B IB=μB​I (with resolvents JγA=IJ_{\gamma A} = IJγA​=I, JγB=(1+γμB)−1IJ_{\gamma B} = (1+\gamma\mu_B)^{-1}IJγB​=(1+γμB​)−1I) and C=cIC = cIC=cI with c>0c > 0c>0, and KKK is quantified before kkk.

Contributions are welcome at every level: proofs of the real-sequence milestones (a general Stolz–Cesàro lemma would be reusable well beyond this mission), of the two one-step inequalities, and of the telescoping argument that assembles the goal.

Selected references

  • D. Davis and W. Yin, A Three-Operator Splitting Scheme and its Optimization Applications, Set-Valued and Variational Analysis 25 (2017), 829–858. https://doi.org/10.1007/s11228-017-0421-z (preprint: https://arxiv.org/abs/1504.01032)
  • R. I. Boţ, E. R. Csetnek, A. Heinrich and C. Hendrich, On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems, Mathematical Programming 150 (2015), 251–279. https://doi.org/10.1007/s10107-014-0766-0
  • A. Chambolle and T. Pock, A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging, Journal of Mathematical Imaging and Vision 40 (2011), 120–145. https://doi.org/10.1007/s10851-010-0251-1
  • H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., Springer, 2017. https://doi.org/10.1007/978-3-319-48311-5
11 thms3 active usersReviewed
OptimizationTheoretical Computer Science·Captain: Lucas

The Grothendieck Constant: New Upper and Lower BoundsOpen Problem

Motivation

Given a real matrix A=(aij)∈Rm×nA=(a_{ij})\in\mathbb R^{m\times n}A=(aij​)∈Rm×n, consider maximizing the bilinear form ∑i,jaijxiyj\sum_{i,j}a_{ij}x_iy_j∑i,j​aij​xi​yj​ over sign vectors x∈{±1}mx\in\{\pm1\}^mx∈{±1}m, y∈{±1}ny\in\{\pm1\}^ny∈{±1}n. This discrete optimum, written OPT(A)\mathrm{OPT}(A)OPT(A), is closely tied to the cut norm of a matrix and is NP-hard to compute. Relaxing each sign to a unit vector and each product to an inner product gives the semidefinite value SDP(A)\mathrm{SDP}(A)SDP(A), computable in polynomial time. Grothendieck's inequality (Grothendieck, 1953) states that the relaxation overshoots by at most a universal factor: there is a finite KKK, independent of AAA, of m,nm,nm,n, and of the dimension of the vectors, with SDP(A)≤K⋅OPT(A)\mathrm{SDP}(A)\le K\cdot\mathrm{OPT}(A)SDP(A)≤K⋅OPT(A) for every AAA. The Grothendieck constant KGK_GKG​ is the least such KKK — equivalently, the worst-case integrality gap of the canonical semidefinite relaxation of this bilinear problem.

The constant is not a curiosity of one optimization problem. It originated in functional analysis, where it is central to the geometry of Banach spaces and to harmonic analysis; it governs the approximation ratio available for cut norms; and, in quantum information, it measures the maximal advantage of quantum over classical correlations in Bell-type experiments. Its exact value has been open since 1953.

A timeline of the bounds:

  • 1953, Grothendieck. Existence of a finite KKK, together with the lower bound KG≥π/2=1.5707…K_G\ge\pi/2=1.5707\ldotsKG​≥π/2=1.5707…
  • 1977, Krivine. KG≤π/(2log⁡(1+2))=1.7822…K_G\le\pi/\bigl(2\log(1+\sqrt2)\bigr)=1.7822\ldotsKG​≤π/(2log(1+2​))=1.7822…, obtained by analyzing hyperplane rounding, and conjectured to be optimal.
  • 1984/1991, Davie and Reeds (independently). KG≥1.6769…K_G\ge1.6769\ldotsKG​≥1.6769…, from an explicit high-dimensional Gaussian hard instance.
  • 2011, Braverman–Makarychev–Makarychev–Naor. Krivine's conjecture is false: KG<π/(2log⁡(1+2))K_G<\pi/(2\log(1+\sqrt2))KG​<π/(2log(1+2​)) strictly, with no quantitative gap.
  • 2014, Naor–Regev. Mixtures of Krivine schemes are asymptotically optimal: rounding schemes of this one family approach the true value of KGK_GKG​.
  • 2026, Heilman; Jones–Malavolta. The first improvements on Davie–Reeds, by 10−2610^{-26}10−26 and 10−1210^{-12}10−12 respectively; and the first explicit numerical improvements on Krivine's bound, of order 10−510^{-5}10−5 (Heilman; Li–Saha–Xue et al.).
  • 2026, Saha–Li–Xue–Chaudhuri–Klivans–Kothari–Meka. The bounds this mission targets:
6π11 ≤ KG ≤ π2log⁡(1+2)−3.47×10−4,\frac{6\pi}{11}\ \le\ K_G\ \le\ \frac{\pi}{2\log(1+\sqrt2)}-3.47\times10^{-4},116π​ ≤ KG​ ≤ 2log(1+2​)π​−3.47×10−4,

i.e. 1.7135…≤KG≤1.7818…1.7135\ldots\le K_G\le1.7818\ldots1.7135…≤KG​≤1.7818…, which fixes the tenths digit of KGK_GKG​ at 777.

Setting

Fix m,n∈Nm,n\in\mathbb Nm,n∈N and A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n.

OPT(A):=max⁡x∈{±1}m,  y∈{±1}n∑i,jaijxiyj,SDP(A):=sup⁡d∈N sup⁡ui,vj∈Sd−1∑i,jaij⟨ui,vj⟩.\mathrm{OPT}(A):=\max_{x\in\{\pm1\}^m,\;y\in\{\pm1\}^n}\sum_{i,j}a_{ij}x_iy_j,\qquad \mathrm{SDP}(A):=\sup_{d\in\mathbb N}\ \sup_{u_i,v_j\in S^{d-1}}\sum_{i,j}a_{ij}\langle u_i,v_j\rangle .OPT(A):=x∈{±1}m,y∈{±1}nmax​i,j∑​aij​xi​yj​,SDP(A):=d∈Nsup​ ui​,vj​∈Sd−1sup​i,j∑​aij​⟨ui​,vj​⟩.

Here u1,…,umu_1,\dots,u_mu1​,…,um​ and v1,…,vnv_1,\dots,v_nv1​,…,vn​ are unit vectors of a common but arbitrary finite dimension ddd. Since a sign is a unit vector in dimension one, OPT(A)≤SDP(A)\mathrm{OPT}(A)\le\mathrm{SDP}(A)OPT(A)≤SDP(A). Call KKK a Grothendieck bound if SDP(A)≤K⋅OPT(A)\mathrm{SDP}(A)\le K\cdot\mathrm{OPT}(A)SDP(A)≤K⋅OPT(A) for every mmm, nnn and AAA, and set KG:=inf⁡{K:K is a Grothendieck bound}K_G:=\inf\{K: K\text{ is a Grothendieck bound}\}KG​:=inf{K:K is a Grothendieck bound}.

Upper bounds on KGK_GKG​ come from rounding algorithms. A Krivine scheme of dimension kkk is a pair of partitions of Rk\mathbb R^kRk into a +1+1+1 region and a −1-1−1 region, encoded by measurable odd functions f,g:Rk→{±1}f,g:\mathbb R^k\to\{\pm1\}f,g:Rk→{±1}: the algorithm maps each SDP vector to a Gaussian point in Rk\mathbb R^kRk, correlated according to the inner products, and reads off the label of the region the point lands in. Taking f=g=sgn⁡(z1)f=g=\operatorname{sgn}(z_1)f=g=sgn(z1​) recovers random hyperplane rounding. The quality of a scheme is carried by its normalized correlation function

H(t):=π2 E[f(X)g(Y)],H(t):=\frac{\pi}{2}\,\mathbb E\bigl[f(X)g(Y)\bigr],H(t):=2π​E[f(X)g(Y)],

where X,YX,YX,Y are standard Gaussian vectors in Rk\mathbb R^kRk with E[XiYi]=t\mathbb E[X_iY_i]=tE[Xi​Yi​]=t for every coordinate iii. For the half-space partition H(t)=arcsin⁡tH(t)=\arcsin tH(t)=arcsint, whose analysis gives Krivine's bound. Writing the odd expansion H(t)=b1t+b3t3+⋯H(t)=b_1t+b_3t^3+\cdotsH(t)=b1​t+b3​t3+⋯, the hyperplane scheme sits at (b1,b3)=(1,16)(b_1,b_3)=(1,\tfrac16)(b1​,b3​)=(1,61​).

Formalization targets

Goal

6π11 ≤ KG ≤ π2log⁡(1+2)−3.47×10−4\frac{6\pi}{11}\ \le\ K_G\ \le\ \frac{\pi}{2\log(1+\sqrt2)}-3.47\times10^{-4}116π​ ≤ KG​ ≤ 2log(1+2​)π​−3.47×10−4

This is the two-sided bound the source paper states as the outcome of its Theorems 2.1 and 2.2. It is the weakest statement that carries both of the paper's contributions at once; each side is also a milestone in its own right, so partial progress is recorded even if only one direction closes.

Milestones

The milestone list runs from the classical background to the two new bounds: OPT≤SDP\mathrm{OPT}\le\mathrm{SDP}OPT≤SDP; the existence of a finite Grothendieck bound; KG≥π/2K_G\ge\pi/2KG​≥π/2; Krivine's KG≤π/(2log⁡(1+2))K_G\le\pi/(2\log(1+\sqrt2))KG​≤π/(2log(1+2​)); the affine coefficient constraint b3≥2b1−116b_3\ge2b_1-\tfrac{11}{6}b3​≥2b1​−611​ valid for every Krivine scheme (Theorem 2.2, equation (1)); the transfer of a member of the affine family into a lower bound on KGK_GKG​ (Appendix A); the lower bound KG≥6π/11K_G\ge6\pi/11KG​≥6π/11 (Theorem 2.2); and the cubic–quintic upper bound (Theorem 2.1).

Significance

The two target bounds narrow an interval that had been essentially static for four decades: before 2026 the state of the art was 1.6769…≤KG≤1.7822…1.6769\ldots\le K_G\le1.7822\ldots1.6769…≤KG​≤1.7822…, wide enough that the tenths digit was unknown. The lower bound is also methodologically new. Every previous lower bound was obtained by exhibiting a hard instance; this one instead proves a ceiling on the performance of every rounding scheme in the Krivine family and converts that ceiling, through the Naor–Regev optimality theorem, into a bound on the constant. The affine constraint b3≥2b1−116b_3\ge2b_1-\tfrac{11}{6}b3​≥2b1​−611​ is the transportable core of that argument: being affine in the coefficients, it survives mixing schemes and passing to limits, which is exactly what the reduction to KGK_GKG​ requires.

On the formalization side, nothing here is machine-checked today. The upper bound (Theorem 2.1) is certified by interval arithmetic in the companion paper, and the lower bound's central one-dimensional inequality likewise rests on a computer-assisted certificate; reproducing either inside Lean means building a rigorous numeric layer on top of the analytic argument. Ahead of that, the mission needs a formal definition of KGK_GKG​ itself and of the Krivine-scheme apparatus, neither of which exists in Mathlib — these are reusable well beyond this mission, since Grothendieck's inequality feeds cut-norm approximation and Bell-inequality bounds. Contributions of intermediate lemmas about OPT\mathrm{OPT}OPT, SDP\mathrm{SDP}SDP, Gaussian correlation identities, and Hermite expansions are welcome even when the headline bounds stay open.

Difficulty

The obvious route to a lower bound is to write down a matrix and compute. That route is what Davie and Reeds exhausted; improving it has produced gains of order 10−1210^{-12}10−12 at best, because the hard instances are high-dimensional Gaussian objects whose OPT\mathrm{OPT}OPT is itself hard to bound tightly. The route taken here avoids instances entirely, and its difficulty lies elsewhere: a constraint on a single scheme is worthless unless it survives averaging over schemes and passing to limits of schemes of growing dimension, since only then does the Naor–Regev optimality theorem convert it into a statement about KGK_GKG​. Constraints that are nonlinear in the scheme do not survive that passage, which is why the target inequality is affine in (b1,b3)(b_1,b_3)(b1​,b3​). For the upper bound, the difficulty is that the improvement is genuinely asymptotic: it comes from a limit of schemes of growing dimension rather than any fixed low-dimensional partition, and the final margin of 3.47×10−43.47\times10^{-4}3.47×10−4 is certified numerically rather than in closed form.

Formalization scope

OPT(A)\mathrm{OPT}(A)OPT(A) and SDP(A)\mathrm{SDP}(A)SDP(A) are defined as suprema of explicitly described sets of reals, over matrices indexed by Fin m and Fin n with real entries; the sign vectors are real-valued functions constrained to take the values 111 and −1-1−1, and the relaxation quantifies over unit vectors of EuclideanSpace ℝ (Fin d) for an existentially quantified ddd, so no dimension bound is built in. The empty-index cases m=0m=0m=0 or n=0n=0n=0 are included and give value 000 on both sides. KGK_GKG​ is the infimum of the set of Grothendieck bounds; that set is nonempty precisely by Grothendieck's inequality, which is itself a milestone, and it is bounded below, so the infimum is not a junk value.

A Krivine scheme is a structure carrying two measurable ±1\pm1±1-valued functions on Fin k → ℝ, each odd almost everywhere. Almost-everywhere oddness is forced: no ±1\pm1±1-valued function satisfies f(−0)=−f(0)f(-0)=-f(0)f(−0)=−f(0) at the origin, so a pointwise requirement would make the structure empty and every statement about schemes vacuous. With the null-set relaxation the half-space partition is a scheme in every dimension k≥1k\ge1k≥1, and the definition file constructs it, pinning down non-vacuity; dimension k=0k=0k=0 admits no scheme. The correlation function is the explicit double Gaussian integral against the correlated-pair density, scaled by π/2\pi/2π/2, and the coefficients b1,b3b_1,b_3b1​,b3​ are read off as H′(0)H'(0)H′(0) and H′′′(0)/6H'''(0)/6H′′′(0)/6 — where HHH fails to be three times differentiable at 000 these are the ambient junk value 000, which a solver should keep in mind when reading the coefficient milestones.

No trivializing reading is available for the goal: it pins KGK_GKG​ between two explicit numerical constants, so it can be satisfied neither vacuously nor by a degenerate convention. Solvers should be aware that the source paper states its two theorems in abridged form and refers to its companion paper for the full proofs, and that the further bounds reported there — the stronger lower rungs 27π/4927\pi/4927π/49 and 51π/9251\pi/9251π/92, and the upper values 1.7818018410331.7818018410331.781801841033 and 1.78133198106256391.78133198106256391.7813319810625639 — are explicitly described as system-tested but not author-verified; they are deliberately outside this mission's milestone list.

Selected references

  • A. Grothendieck, Résumé de la théorie métrique des produits tensoriels topologiques, Bol. Soc. Mat. São Paulo 8 (1953), 1–79.
  • J.-L. Krivine, Sur la constante de Grothendieck, C. R. Acad. Sci. Paris (1977).
  • M. Braverman, K. Makarychev, Y. Makarychev, A. Naor, The Grothendieck constant is strictly smaller than Krivine's bound, FOCS 2011, 453–462. https://doi.org/10.1109/FOCS.2011.77
  • A. Naor, O. Regev, Krivine schemes are optimal, Proc. Amer. Math. Soc. 142 (2014), 4315–4320. https://doi.org/10.1090/S0002-9939-2014-12145-3
  • N. Alon, A. Naor, Approximating the cut-norm via Grothendieck's inequality, SIAM J. Comput. 35 (2006), 787–803. https://doi.org/10.1137/S0097539704441629
  • A. Li, R. Saha, A. Xue, S. Chaudhuri, A. Klivans, P. K. Kothari, R. Meka, Long-Horizon AI Research for Grothendieck Constant: A Case Study in Human–AI Mathematical Collaboration, arXiv:2608.11195v3, 2026. https://arxiv.org/abs/2608.11195
  • R. Saha, A. Li, A. Xue, S. Chaudhuri, A. Klivans, P. K. Kothari, R. Meka, New upper and lower bounds for the Grothendieck constant, 2026 (companion paper containing the full proofs).
12 thms3 active usersReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

High-Dimensional Statistics XI: The Moore-Aronszajn TheoremTextbook

Motivation

Many statistical problems — nonparametric regression, density estimation, dimension reduction, testing — are naturally posed as optimization over a space of functions rather than a finite-dimensional parameter vector. Hilbert spaces provide the right generality: they carry an inner product and a norm, so notions of projection, orthogonality and least-squares fitting all make sense, exactly as in ordinary Euclidean space, even though the "vectors" are now functions. Reproducing kernel Hilbert spaces (RKHSs) are the particular class of function-valued Hilbert spaces that make this program computationally tractable: they are generated by a single bivariate kernel function, and every RKHS computation reduces to evaluating that kernel, never to manipulating an infinite-dimensional object directly (the "kernel trick"). Wainwright's High-Dimensional Statistics (2019), Chapter 12, develops the foundational correspondence between kernels and Hilbert spaces that makes this possible, and this mission formalizes its two central theorems.

Setting

A Hilbert space is a complete inner product space (Definitions 12.1–12.2); this mission uses Mathlib's own NormedAddCommGroup/InnerProductSpace ℝ/CompleteSpace typeclasses for this notion throughout. A linear functional L:H→RL:H\to\mathbb RL:H→R is bounded if ∣L(f)∣≤M∥f∥H|L(f)|\le M\|f\|_H∣L(f)∣≤M∥f∥H​ for some M<∞M<\inftyM<∞ and all f∈Hf\in Hf∈H; the Riesz representation theorem (Theorem 12.5) says every such functional is L(f)=⟨f,g⟩HL(f)=\langle f,g\rangle_HL(f)=⟨f,g⟩H​ for a unique g∈Hg\in Hg∈H.

A bivariate function K:X×X→RK:X\times X\to\mathbb RK:X×X→R is a positive semidefinite (PSD) kernel (Definition 12.6) if it is symmetric and every finite Gram matrix (K(xi,xj))i,j=1n(K(x_i,x_j))_{i,j=1}^n(K(xi​,xj​))i,j=1n​ is positive semidefinite — the natural generalization of a PSD matrix to a (possibly infinite) index set XXX, with no topological structure on XXX required. A reproducing kernel Hilbert space (RKHS) for a kernel KKK is a Hilbert space HHH of functions on XXX such that, for every x∈Xx\in Xx∈X, the function K(⋅,x)K(\cdot,x)K(⋅,x) belongs to HHH and

⟨f,K(⋅,x)⟩H=f(x)for all f∈H(12.3)\langle f, K(\cdot,x)\rangle_H = f(x) \qquad \text{for all } f\in H \tag{12.3}⟨f,K(⋅,x)⟩H​=f(x)for all f∈H(12.3)

— the reproducing property. Equivalently (Definition 12.12), HHH is an RKHS exactly when every evaluation functional f↦f(x)f\mapsto f(x)f↦f(x) is bounded on HHH.

Formalization targets

Goal (Theorem 12.11, the Moore-Aronszajn theorem)

Given any PSD kernel function KKK on any set XXX, there is a Hilbert space HHH (embedded into functions on XXX) in which KKK satisfies the reproducing property (12.3) — and this Hilbert space is unique: any two Hilbert spaces with this property for the same KKK are linearly isometric via an isometry intertwining their embeddings into functions on XXX.

Milestones

  • Theorem 12.5 (Riesz representation). Every bounded linear functional on a Hilbert space HHH has a unique representer g∈Hg\in Hg∈H: L(f)=⟨f,g⟩HL(f)=\langle f,g\rangle_HL(f)=⟨f,g⟩H​ for all fff. Used inside the proof of Theorem 12.13 to produce the representer RxR_xRx​ of each evaluation functional.
  • Theorem 12.13 (the converse correspondence). Given any Hilbert space HHH of functions on XXX in which every evaluation functional is bounded, there is a unique PSD kernel KKK satisfying the reproducing property for HHH — completing the Moore-Aronszajn equivalence between PSD kernels and Hilbert spaces with bounded evaluation functionals.
  • Theorem 12.20 (Mercer's theorem). Under compactness of XXX, continuity of KKK, and the Hilbert-Schmidt condition ∫X×XK2 dP dP<∞\int_{X\times X}K^2\,dP\,dP<\infty∫X×X​K2dPdP<∞, the integral operator TK(f)(x)=∫XK(x,z)f(z) dP(z)T_K(f)(x)=\int_XK(x,z)f(z)\,dP(z)TK​(f)(x)=∫X​K(x,z)f(z)dP(z) has an orthonormal eigenbasis (φj)(\varphi_j)(φj​) of L2(X;P)L^2(X;P)L2(X;P) with non-negative eigenvalues (μj)(\mu_j)(μj​), and K(x,z)=∑jμjφj(x)φj(z)K(x,z)=\sum_j\mu_j\varphi_j(x)\varphi_j(z)K(x,z)=∑j​μj​φj​(x)φj​(z), with the series converging absolutely and uniformly.

Significance

Theorem 12.11 is the theorem that makes the entire RKHS apparatus well-posed: every time a statistician writes down a kernel — linear, polynomial, Gaussian — Theorem 12.11 guarantees that a canonical Hilbert space of functions exists in which that kernel reproduces, so that optimizing over "the RKHS associated with KKK" is a well-defined problem, not merely a suggestive shorthand. Theorem 12.13's converse shows the correspondence is exact — the class of kernel-generated Hilbert spaces is exactly the class of function spaces with bounded evaluation, the class relevant to any statistical application that samples a function at finitely many points. Together, these two results are the foundation the book's own later chapters build directly on: Chapter 13's nonparametric least-squares oracle inequality, and Chapter 14's kernel density estimation, both work by optimizing over an RKHS and are only well-posed because of this correspondence. Mercer's theorem, in turn, is what connects the RKHS viewpoint back to the earlier feature-map viewpoint of Chapter 12.2.2 (Eq. 12.2): the eigenfunctions (μjφj)j(\sqrt{\mu_j}\varphi_j)_j(μj​​φj​)j​ give an explicit feature map into ℓ2(N)\ell^2(\mathbb N)ℓ2(N) realizing KKK, and its expansion is what later underlies the book's discussion of kernel PCA and of RKHS balls as ellipsoids in ℓ2(N)\ell^2(\mathbb N)ℓ2(N)-coordinates.

Difficulty

The formalization difficulty is concentrated in getting the type of the existence-and- uniqueness claim right, not in any single hypothesis. A Hilbert space is not naturally a subtype of a fixed ambient space in Lean, so "the Hilbert space HHH" of Theorem 12.11 is formalized as an abstract type together with its own NormedAddCommGroup/InnerProductSpace ℝ/CompleteSpace instances, connected to "a space of functions on XXX" via an injective linear embedding into X→RX\to\mathbb RX→R — and uniqueness must then be stated as an isometric equivalence between any two witnessing Hilbert spaces that respects this embedding, the faithful rendering of the book's own proof, which literally shows two candidate Hilbert spaces are equal as sets of functions. A second subtlety is keeping Theorem 12.11's hypotheses (a bare PSD kernel, no topology on XXX) cleanly separated from Mercer's theorem's additional compactness, continuity and measure-theoretic apparatus — the two theorems are frequently conflated informally, but the book is explicit that Theorem 12.11 needs none of Mercer's structure.

Formalization scope

XXX is an unconstrained Type* for Theorem 12.5, 12.11 and 12.13 — no topology, matching the book's own generality. Mercer's theorem (Theorem 12.20) additionally requires [MetricSpace X] [CompactSpace X] [MeasurableSpace X] [BorelSpace X] and a finite measure P, matching its own compactness/continuity/measure-theoretic hypotheses exactly, never applied outside that scope. The integral operator TKT_KTK​ of Eq. (12.11a) is presented as an abstract linear map on Lp ℝ 2 P tied to the defining integral formula via an explicit hypothesis, rather than constructed as a def, since constructing it as a genuine well-defined operator (needing integrability and a.e.-measurability arguments) is proof content, not definitional content, and this mission's definitions file is sorry-free by convention. Mercer's orthonormal-basis index type is existentially quantified over a countable ι (∃ (ι : Type) (_ : Countable ι), ...) rather than fixed to ℕ, since L²(X;P) can be finite-dimensional for finite X (Example 12.18/12.21), where no infinite orthonormal basis exists; the uniform-convergence conjunct is correspondingly quantified over every bijection e : ℕ ≃ ι (vacuous when ι is finite, a genuine order-independent claim when ι is countably infinite). A trivializing formalization of this chapter would state only existence in Theorem 12.11 and drop uniqueness (explicitly warned against by this chapter's own brief), or state Mercer's convergence merely pointwise or in L2L^2L2 rather than absolutely and uniformly; this mission avoids both. Out of scope: the constructive proof detail of Theorem 12.11 (the explicit span-and-complete construction is proof content, not part of the statement), the chapter's worked kernel examples (linear, polynomial, Gaussian kernels, Examples 12.7–12.9), and the further consequences of Mercer's theorem (Corollary 12.26 on RKHS-ball ellipsoids, the feature-map connection of Eq. 12.14) — all natural follow-on work for a future mission on kernel-based nonparametric regression (Chapter 13, mission 13-nonparametric-ls), which restates whatever RKHS objects it needs locally rather than importing this mission's draft, per this book's series-wide convention.

Selected references

  • Wainwright, M. J. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019. Chapter 12. DOI: 10.1017/9781108627771.
  • Aronszajn, N. "Theory of reproducing kernels." Transactions of the American Mathematical Society, 68(3), 1950, 337–404.
  • Mercer, J. "Functions of positive and negative type, and their connection with the theory of integral equations." Philosophical Transactions of the Royal Society A, 209, 1909, 415–446.
6 thms3 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Support Vector Machines IV: The Representer Theorem for Empirical SVM SolutionsTextbook

Motivation

Support vector machines (SVMs) are trained by solving a regularized empirical risk minimization problem over a reproducing kernel Hilbert space (RKHS) — a space that is typically infinite-dimensional. On its face, this looks computationally hopeless: how can a computer search an infinite-dimensional space for a minimizer? The representer theorem is the result that makes SVM training tractable at all: it shows that no matter how large the RKHS is, the minimizer of the SVM objective for a sample of size nnn always lies in the nnn-dimensional subspace spanned by the kernel evaluated at the nnn sample points. This turns an infinite- dimensional optimization problem into a finite-dimensional one before a single line of an optimization algorithm is written, and it is the reason every practical SVM solver (from the original sequential minimal optimization algorithm onward) searches only over nnn coefficients rather than over an abstract function space.

The theorem in this mission — Theorem 5.5 of Steinwart and Christmann, Support Vector Machines (Springer, 2008) — is stated for general convex losses and general kernels, subsuming the classification-SVM and regression-SVM special cases that appear throughout the machine learning literature. Its lineage traces to Kimeldorf and Wahba's 1971 representer theorem for spline-smoothing problems; the book's own version (attributed to a 1971 result, generalized here to arbitrary convex losses and RKHSs) is the general form used throughout the rest of the book.

Setting

Fix a nonempty set XXX (the input space) and a loss function L:X×R×R→[0,∞)L : X \times \mathbb R \times \mathbb R \to [0,\infty)L:X×R×R→[0,∞): a measurable map where L(x,y,t)L(x,y,t)L(x,y,t) is the cost of predicting label yyy by value ttt when the input is xxx. LLL is convex if L(x,y,⋅)L(x,y,\cdot)L(x,y,⋅) is convex for every fixed x,yx,yx,y.

A reproducing kernel Hilbert space (RKHS) over XXX is a real Hilbert space HHH of real-valued functions on XXX that carries a kernel k:X×X→Rk : X \times X \to \mathbb Rk:X×X→R with two properties: k(⋅,x)∈Hk(\cdot,x) \in Hk(⋅,x)∈H for every x∈Xx \in Xx∈X, and the reproducing property f(x)=⟨f,k(⋅,x)⟩Hf(x) = \langle f, k(\cdot,x)\rangle_Hf(x)=⟨f,k(⋅,x)⟩H​ holds for every f∈Hf \in Hf∈H and x∈Xx \in Xx∈X. Intuitively, kkk lets you evaluate any f∈Hf \in Hf∈H at a point xxx by taking an inner product with the fixed function k(⋅,x)k(\cdot,x)k(⋅,x) — this is what makes HHH a space of genuine, pointwise-evaluable functions rather than an abstract Hilbert space.

Given a finite sample D:=((x1,y1),…,(xn,yn))∈(X×R)nD := ((x_1,y_1),\dots,(x_n,y_n)) \in (X \times \mathbb R)^nD:=((x1​,y1​),…,(xn​,yn​))∈(X×R)n, the empirical LLL-risk of f:X→Rf : X \to \mathbb Rf:X→R is RL,D(f):=1n∑i=1nL(xi,yi,f(xi))R_{L,D}(f) := \tfrac1n\sum_{i=1}^n L(x_i,y_i,f(x_i))RL,D​(f):=n1​∑i=1n​L(xi​,yi​,f(xi​)). For a regularization parameter λ>0\lambda > 0λ>0, the SVM training problem asks for a minimizer of the regularized empirical risk

f↦λ∥f∥H2+RL,D(f)f \mapsto \lambda\|f\|_H^2 + R_{L,D}(f)f↦λ∥f∥H2​+RL,D​(f)

over all of HHH. A minimizer of this objective is called an empirical SVM solution fD,λf_{D,\lambda}fD,λ​.

Formalization targets

Goal — Theorem 5.5 (Representer theorem)

∃! fD,λ∈H:λ∥fD,λ∥H2+RL,D(fD,λ)=min⁡f∈H(λ∥f∥H2+RL,D(f)),fD,λ(x)=∑i=1nαi k(x,xi)   for some α1,…,αn∈R.\exists! \, f_{D,\lambda} \in H : \quad \lambda\|f_{D,\lambda}\|_H^2 + R_{L,D}(f_{D,\lambda}) = \min_{f \in H} \Bigl(\lambda\|f\|_H^2 + R_{L,D}(f)\Bigr), \qquad f_{D,\lambda}(x) = \sum_{i=1}^n \alpha_i\, k(x,x_i) \; \text{ for some } \alpha_1,\dots,\alpha_n \in \mathbb R.∃!fD,λ​∈H:λ∥fD,λ​∥H2​+RL,D​(fD,λ​)=f∈Hmin​(λ∥f∥H2​+RL,D​(f)),fD,λ​(x)=i=1∑n​αi​k(x,xi​) for some α1​,…,αn​∈R.

The theorem asserts both halves at once: the regularized empirical risk has a unique minimizer over the (possibly infinite-dimensional) HHH, and that unique minimizer is representable as a finite linear combination of the kernel functions at the sample points. Neither the coefficients αi\alpha_iαi​ nor the finite-dimensional subspace they live in are fixed in advance by the statement; only their existence is asserted, so a stronger claim (e.g. uniqueness or an explicit formula for the αi\alpha_iαi​) would be a different, harder theorem not proved here.

Supporting milestones (the general, population-level analogue)

The book develops the representer theorem's existence-and-uniqueness clause by first proving it for the corresponding population problem — minimizing f↦λ∥f∥H2+RL,P(f)f \mapsto \lambda\|f\|_H^2 + R_{L,P}(f)f↦λ∥f∥H2​+RL,P​(f) over a distribution PPP rather than a finite sample — and then adapting the same two arguments to the empirical case:

  • Lemma 5.1 (uniqueness): for a convex loss and an RKHS HHH with RL,P(f)<∞R_{L,P}(f) < \inftyRL,P​(f)<∞ for some f∈Hf \in Hf∈H, the regularized population risk has at most one minimizer over HHH, for every λ>0\lambda > 0λ>0.
  • Theorem 5.2 (existence): for a convex, PPP-integrable Nemitski loss and the RKHS of a bounded kernel, the regularized population risk has at least one minimizer, for every λ>0\lambda > 0λ>0.
  • Theorem 5.6 (non-triviality): under the same hypotheses as Theorem 5.2, if HHH can beat the risk of the zero function (inf⁡f∈HRL,P(f)<RL,P(0)\inf_{f \in H} R_{L,P}(f) < R_{L,P}(0)inff∈H​RL,P​(f)<RL,P​(0)), then every minimizer is nonzero, for every λ>0\lambda > 0λ>0.

Significance

The representer theorem is the single fact that turns kernel-based learning from a theoretical curiosity into a practical algorithm family: every popular SVM solver (SMO, coordinate descent, interior-point methods for the dual) is, at bottom, a method for finding the nnn coefficients α1,…,αn\alpha_1,\dots,\alpha_nα1​,…,αn​ the theorem guarantees exist, not for searching HHH directly. The representation also underlies the "kernel trick": since the objective and the solution both depend on HHH only through inner products ⟨k(⋅,xi),k(⋅,xj)⟩H=k(xi,xj)\langle k(\cdot,x_i), k(\cdot,x_j)\rangle_H = k(x_i,x_j)⟨k(⋅,xi​),k(⋅,xj​)⟩H​=k(xi​,xj​), an SVM can be trained and evaluated without ever computing with elements of HHH explicitly, using only the n×nn \times nn×n Gram matrix of kernel values.

Formalizing this theorem means formalizing the existence-and-uniqueness argument (Lemma 5.1's strict-convexity computation for the midpoint of two hypothetical minimizers, together with the weak-compactness argument used for existence) and the orthogonal-projection argument for the representation clause (projecting any candidate minimizer onto the finite-dimensional span of the kernel functions at the sample points strictly improves — or leaves unchanged — both the norm term and the risk term, so an optimal solution can always be chosen inside that span). No part of this argument has a machine-checked Lean proof in Mathlib or elsewhere at the time of writing; only the underlying general-purpose tools (Hilbert-space projections, convexity of norms) are already in Mathlib.

Difficulty

The natural first idea for the representation clause is to try to exhibit the coefficients αi\alpha_iαi​ directly, e.g. by writing down the dual optimization problem and reading off its KKT multipliers. This is exactly backwards: the book's proof (and any faithful one) derives the representation before knowing anything about a dual problem, purely from the orthogonal decomposition H=H∣X′⊕H∣X′⊥H = H|_{X'} \oplus H|_{X'}^\perpH=H∣X′​⊕H∣X′⊥​ of HHH into the span H∣X′H|_{X'}H∣X′​ of the sample's kernel functions and its orthogonal complement. The key insight — one that a solver who reaches for duality first will miss — is that projecting any f∈Hf \in Hf∈H onto H∣X′H|_{X'}H∣X′​ leaves the empirical risk exactly unchanged (since RL,DR_{L,D}RL,D​ only sees fff's values at the sample points, and the reproducing property shows those values are unaffected by throwing away the H∣X′⊥H|_{X'}^\perpH∣X′⊥​ component) while weakly decreasing the norm term, so the infimum over all of HHH is already attained inside the finite-dimensional H∣X′H|_{X'}H∣X′​.

For the existence-and-uniqueness clause, the difficulty is genuinely functional-analytic rather than algorithmic: existence needs a compactness argument in a space with no compact balls (Theorem 5.2 gets around this via lower semicontinuity and boundedness of the sublevel set, not via any finite-dimensional trick), and uniqueness needs the parallelogram-law strict convexity of the Hilbert norm, not merely convexity of the loss.

Formalization scope

HHH is represented as an arbitrary real Hilbert space together with an injective linear evaluation map into X→RX \to \mathbb RX→R (so that HHH is genuinely realized as a space of functions, not an abstract Hilbert space with no relation to XXX), and a kernel kkk satisfying the reproducing property with respect to that evaluation map (IsRKHSOfKernel). This is an equivalent, operative rendering of "HHH is the RKHS of the kernel kkk" (Definition 4.18 together with Lemma 4.19 of the book), chosen because it is exactly the form the chapter's own proofs use; it is restated inside this chunk's own InfiniteSample sub-namespace rather than imported from the Kernels chapter's mission, since drafts in this series cannot import one another.

The population risk RL,PR_{L,P}RL,P​ is formalized as a lower Lebesgue integral into [0,∞][0,\infty][0,∞] (ENNReal), which is always well-defined for a nonnegative integrand with no integrability hypothesis — matching the book's own remark that "the integral always exists, although it is not necessarily finite." The empirical risk RL,DR_{L,D}RL,D​, by contrast, is a manifestly finite average over the nnn sample points and is formalized as an ordinary real number. The sample size nnn is required positive (n≥1n \ge 1n≥1), matching the book's implicit convention that the empirical measure Dˉ:=1n∑iδ(xi,yi)\bar D := \tfrac1n\sum_i \delta_{(x_i,y_i)}Dˉ:=n1​∑i​δ(xi​,yi​)​ presupposes a nonempty sample.

A trivializing formalization of the representer theorem would state only the representation clause fD,λ(x)=∑iαik(x,xi)f_{D,\lambda}(x) = \sum_i \alpha_i k(x,x_i)fD,λ​(x)=∑i​αi​k(x,xi​) while assuming the existence of "the" solution fD,λf_{D,\lambda}fD,λ​ as a hypothesis; this begs the question, since the book's own proof establishes existence and uniqueness as part of the theorem, not as a standing assumption. This mission's goal keeps both clauses bundled into one ∃! statement for exactly this reason.

The infrastructure needed — a general convex loss, a Nemitski-loss integrability condition, and the RKHS/reproducing-kernel bundle — is restated locally here and is reusable, with the same caveat about not being importable across this series' independently drafted chapters, by any later mission (e.g. this book's own Chapters 6, 8 and 9) that needs the same objects. Contributed proofs are welcome for either the existence/uniqueness argument (Lemma 5.1/Theorem 5.2's techniques) or the orthogonal-projection representation argument; the two are largely independent and could be solved separately.

Selected references

  • I. Steinwart and A. Christmann, Support Vector Machines, Springer Series in Information Science and Statistics, Springer, 2008. https://doi.org/10.1007/978-0-387-77242-4
  • G. Kimeldorf and G. Wahba, "Some results on Tchebycheffian spline functions," Journal of Mathematical Analysis and Applications, 33(1):82–95, 1971. https://doi.org/10.1016/0022-247X(71)90184-3
  • B. Schölkopf, R. Herbrich, and A. J. Smola, "A generalized representer theorem," in Computational Learning Theory (COLT 2001), Lecture Notes in Computer Science, vol. 2111, Springer, 2001, pp. 416–426. https://doi.org/10.1007/3-540-44581-1_27
11 thms3 active usersReviewed
🏆Completed
Mathematical Physics·Captain: Lucas

Lectures on Quantum Field Theory I: The One-Particle Hilbert Spaces of a Boson and an ElectronTextbook

Motivation

Quantum field theory begins, mathematically, with a question that has a completely precise answer: what is the state space of a single relativistic particle? Non-relativistic quantum mechanics answers L2(R3)L^2(\mathbb{R}^3)L2(R3) and moves on. Relativity does not allow that answer, because the state space must carry an action of the symmetry group of Minkowski spacetime — the Poincaré group — and the choice of Hilbert space is dictated by which such action one wants. The construction that results is the foundation on which Fock space, creation and annihilation operators, free fields and eventually interacting theories are built, and it is where the objects that reappear everywhere in the subject are introduced: the mass shell, the Lorentz-invariant measure on it, and the double cover SL(2,C)→SO↑(1,3)SL(2,\mathbb{C}) \to SO^{\uparrow}(1,3)SL(2,C)→SO↑(1,3) that is responsible for spin.

This mission formalizes that construction as it is presented in S. Chatterjee's Lectures on Quantum Field Theory (Stanford, 2018–19), Lectures 9–11 and Lecture 25: the one-particle space of a massive scalar boson, the one-particle space of an electron, and the statement that both carry inner products invariant under the Poincaré action.

Setting

Minkowski spacetime is R1,3\mathbb{R}^{1,3}R1,3 with the bilinear form

(x,y)  =  x0y0−(x1y1+x2y2+x3y3),x2:=(x,x).(x, y) \;=\; x^0 y^0 - \big(x^1y^1 + x^2y^2 + x^3y^3\big), \qquad x^2 := (x,x).(x,y)=x0y0−(x1y1+x2y2+x3y3),x2:=(x,x).

A Lorentz transformation is a linear map LLL with (Lx,Ly)=(x,y)(Lx, Ly) = (x,y)(Lx,Ly)=(x,y); the restricted Lorentz group SO↑(1,3)SO^{\uparrow}(1,3)SO↑(1,3) consists of those with det⁡L=1\det L = 1detL=1 and L00>0L^0{}_0 > 0L00​>0. The Poincaré group is P=R1,3⋊SO↑(1,3)\mathcal{P} = \mathbb{R}^{1,3} \rtimes SO^{\uparrow}(1,3)P=R1,3⋊SO↑(1,3) with the group law (a,A)(b,B)=(a+Ab, AB)(a,A)(b,B) = (a + Ab,\, AB)(a,A)(b,B)=(a+Ab,AB).

For a mass m>0m > 0m>0, the four-momentum of a particle satisfies p2=m2p^2 = m^2p2=m2 and p0≥0p^0 \ge 0p0≥0, so it lies on the mass shell

Xm  =  { p∈R1,3:p2=m2, p0≥0 },X_m \;=\; \{\, p \in \mathbb{R}^{1,3} : p^2 = m^2,\ p^0 \ge 0 \,\},Xm​={p∈R1,3:p2=m2, p0≥0},

a three-dimensional manifold parametrised by the spatial momentum q∈R3q \in \mathbb{R}^3q∈R3 through q↦(ωq,q)q \mapsto (\omega_q, q)q↦(ωq​,q) with ωq=m2+∣q∣2\omega_q = \sqrt{m^2 + |q|^2}ωq​=m2+∣q∣2​. On XmX_mXm​ there is, up to a multiplicative constant, exactly one measure invariant under SO↑(1,3)SO^{\uparrow}(1,3)SO↑(1,3); with the normalisation used in the lectures it is the measure λm\lambda_mλm​ determined by

∫Xmf dλm  =  ∫R3d3q(2π)3 2ωq f(ωq,q).\int_{X_m} f \, d\lambda_m \;=\; \int_{\mathbb{R}^3} \frac{d^3q}{(2\pi)^3\, 2\omega_q}\, f(\omega_q, q).∫Xm​​fdλm​=∫R3​(2π)32ωq​d3q​f(ωq​,q).

The state space of a massive scalar boson is H=L2(Xm,dλm)\mathcal{H} = L^2(X_m, d\lambda_m)H=L2(Xm​,dλm​), acted on by (U(a,L)ψ)(p)=ei(a,p)ψ(L−1p)(U(a,L)\psi)(p) = e^{i(a,p)}\psi(L^{-1}p)(U(a,L)ψ)(p)=ei(a,p)ψ(L−1p).

For an electron the wave function takes values in C2\mathbb{C}^2C2 and the group acts through the double cover. To each four-vector xxx one attaches the Hermitian matrix

M(x)=(x0+x3x1−ix2x1+ix2x0−x3),det⁡M(x)=(x,x),M(x) = \begin{pmatrix} x^0+x^3 & x^1 - ix^2\\ x^1+ix^2 & x^0-x^3\end{pmatrix}, \qquad \det M(x) = (x,x),M(x)=(x0+x3x1+ix2​x1−ix2x0−x3​),detM(x)=(x,x),

and for A∈SL(2,C)A \in SL(2,\mathbb{C})A∈SL(2,C) the transformation κ(A)\kappa(A)κ(A) of R1,3\mathbb{R}^{1,3}R1,3 is defined by M(κ(A)x)=AM(x)A†M(\kappa(A)x) = A M(x) A^{\dagger}M(κ(A)x)=AM(x)A†; the map κ\kappaκ is a surjective two-to-one homomorphism onto SO↑(1,3)SO^{\uparrow}(1,3)SO↑(1,3). Writing p∗=(m,0,0,0)p^* = (m,0,0,0)p∗=(m,0,0,0), each p∈Xmp \in X_mp∈Xm​ is reached from p∗p^*p∗ by a unique positive-definite Vp∈SL(2,C)V_p \in SL(2,\mathbb{C})Vp​∈SL(2,C), the pure boost, and the electron inner product is the Vp−2V_p^{-2}Vp−2​-weighted one,

(ψ,φ)  =  ∫Xmdλm(p)  ψ(p)†Vp−2φ(p),(\psi, \varphi) \;=\; \int_{X_m} d\lambda_m(p)\; \psi(p)^{\dagger} V_p^{-2} \varphi(p),(ψ,φ)=∫Xm​​dλm​(p)ψ(p)†Vp−2​φ(p),

with the group acting by (U(a,A)ψ)(p)=ei(a,p)A ψ(κ(A)−1p)(U(a,A)\psi)(p) = e^{i(a,p)} A\, \psi(\kappa(A)^{-1}p)(U(a,A)ψ)(p)=ei(a,p)Aψ(κ(A)−1p).

Formalization targets

Goal — both one-particle inner products are Poincaré invariant

For m>0m > 0m>0, a∈R1,3a \in \mathbb{R}^{1,3}a∈R1,3, A∈SL(2,C)A \in SL(2,\mathbb{C})A∈SL(2,C) and L=κ(A)L = \kappa(A)L=κ(A):

∫Xm(U(a,L)ψ)‾ (U(a,L)φ) dλm  =  ∫Xmψ‾ φ dλm(ψ,φ∈L2(Xm,dλm)),\int_{X_m} \overline{(U(a,L)\psi)}\,(U(a,L)\varphi)\, d\lambda_m \;=\; \int_{X_m} \overline{\psi}\,\varphi\, d\lambda_m \qquad (\psi,\varphi \in L^2(X_m, d\lambda_m)),∫Xm​​(U(a,L)ψ)​(U(a,L)φ)dλm​=∫Xm​​ψ​φdλm​(ψ,φ∈L2(Xm​,dλm​)), ∫Xm(U(a,A)ψ)† Vp−2 (U(a,A)φ) dλm  =  ∫Xmψ† Vp−2 φ dλm\int_{X_m} (U(a,A)\psi)^{\dagger}\,V_p^{-2}\,(U(a,A)\varphi)\, d\lambda_m \;=\; \int_{X_m} \psi^{\dagger}\,V_p^{-2}\,\varphi\, d\lambda_m∫Xm​​(U(a,A)ψ)†Vp−2​(U(a,A)φ)dλm​=∫Xm​​ψ†Vp−2​φdλm​

for ψ,φ\psi, \varphiψ,φ in the weighted L2L^2L2 space of C2\mathbb{C}^2C2-valued functions. The goal fixes no constants beyond the normalisation of λm\lambda_mλm​, and it is the statement that the spaces defined in the mission really are the one-particle spaces of the theory: a Hilbert space together with a Poincaré action by isometries.

Supporting targets

The milestone list follows the lectures: the parametrisation of XmX_mXm​; invariance of XmX_mXm​ under SO↑(1,3)SO^{\uparrow}(1,3)SO↑(1,3); the integration formula for λm\lambda_mλm​ (eq. (10.1)); invariance of λm\lambda_mλm​; uniqueness of the invariant measure up to a constant; the composition law and unitarity of the scalar representation; det⁡M(x)=(x,x)\det M(x) = (x,x)detM(x)=(x,x) and bijectivity of MMM onto Hermitian matrices; κ\kappaκ as a multiplicative map into SO↑(1,3)SO^{\uparrow}(1,3)SO↑(1,3); surjectivity of κ\kappaκ with fibres {±A}\{\pm A\}{±A}; existence and uniqueness of the pure boost VpV_pVp​; Lemma 25.1; and the identification of the weighted electron space with the plain C2\mathbb{C}^2C2-valued L2L^2L2 space via ψ↦V⋅−1ψ\psi \mapsto V_\cdot^{-1}\psiψ↦V⋅−1​ψ.

Significance

The objects here are used unchanged for the rest of a QFT course: the bosonic and fermionic Fock spaces are built on these one-particle spaces, and the free scalar and Dirac fields are operator-valued distributions written as integrals against dλmd\lambda_mdλm​ on XmX_mXm​. Formalizing them fixes, once and for all, the conventions later work must match — the normalisation of λm\lambda_mλm​, the sign convention of the metric, which of the two elements ±A\pm A±A of SL(2,C)SL(2,\mathbb{C})SL(2,C) acts, and the weight in the electron inner product.

What this mission adds beyond the lectures is a machine-checked development of material usually treated as routine but rarely written out: the uniqueness of the invariant measure, the covering map and its fibres, and the existence-uniqueness of the pure boost are all stated in the source either without proof or as exercises. Mathlib has the general theory of L2L^2L2 spaces, push-forward measures, Hermitian and positive-definite matrices, and SL2SL_2SL2​, but it has no mass shell, no invariant measure on it, and no covering map onto the restricted Lorentz group; all of that is constructed here and is reusable by any later mission on free fields or Fock spaces.

Difficulty

The obvious route to the invariant measure — "restrict Lebesgue measure to the submanifold XmX_mXm​" — does not work: the induced Riemannian volume of the hyperboloid in the Euclidean metric is not Lorentz invariant. The lectures instead take a scaling limit of Lebesgue measure on the invariant annuli {m2<p2<(m+ε)2}\{m^2 < p^2 < (m+\varepsilon)^2\}{m2<p2<(m+ε)2}; the formalization takes the resulting formula (10.1) as the definition and must then prove invariance, which amounts to a change-of-variables computation whose Jacobian is exactly ωq\omega_{q}ωq​-dependent. Uniqueness is harder: it is a statement about invariant measures on a homogeneous space of a non-compact group, with no finiteness available.

On the spinor side, the central difficulty is that the weight Vp−2V_p^{-2}Vp−2​ is unbounded on XmX_mXm​, so the electron space is not the naive C2\mathbb{C}^2C2-valued L2(Xm,dλm)L^2(X_m, d\lambda_m)L2(Xm​,dλm​) — the two spaces consist of different functions, and are related only through the measurable field of isomorphisms ψ↦Vp−1ψ\psi \mapsto V_p^{-1}\psiψ↦Vp−1​ψ. A formalization that silently uses the unweighted space would prove a different, and false, unitarity statement.

Formalization scope

Four-vectors are functions R1,3=(four-element index)→R\mathbb{R}^{1,3} = (\text{four-element index}) \to \mathbb{R}R1,3=(four-element index)→R, with the metric signature (+,−,−,−)(+,-,-,-)(+,−,−,−); Lorentz transformations are real 4×44\times44×4 matrices, and membership in SO↑(1,3)SO^{\uparrow}(1,3)SO↑(1,3) is the predicate (det⁡=1\det = 1det=1, L00>0L^0{}_0 > 0L00​>0, form preserved). λm\lambda_mλm​ is a Borel measure on all of R1,3\mathbb{R}^{1,3}R1,3 carried by XmX_mXm​, defined as the push-forward of (2π)−3(2ωq)−1 d3q(2\pi)^{-3}(2\omega_q)^{-1}\,d^3q(2π)−3(2ωq​)−1d3q; the boson space is the library L2L^2L2 space of that measure. The pure boost is given by the closed formula Vp=(M(p)/m+I)/2+2p0/mV_p = (M(p)/m + I)/\sqrt{2 + 2p^0/m}Vp​=(M(p)/m+I)/2+2p0/m​ — the positive-definite square root of M(p)/mM(p)/mM(p)/m — rather than by a choice function, and a milestone certifies that it is the unique positive-definite element of SL(2,C)SL(2,\mathbb{C})SL(2,C) carrying p∗p^*p∗ to ppp. The electron space is the set of C2\mathbb{C}^2C2-valued measurable functions of finite weighted norm, with the weighted pairing given explicitly; the milestone identifying it with the plain L2L^2L2 space via the inverse boost is what supplies its Hilbert-space structure.

The unitarity statements are formalized as equalities of integrals over pairs of wave functions rather than as statements about abstract operators, so that no trivializing reading is available: in particular the electron clause is stated for the weighted pairing, which is not the standard L2L^2L2 inner product, and the hypotheses (m>0m > 0m>0, det⁡A=1\det A = 1detA=1, ψ,φ\psi,\varphiψ,φ in the respective spaces) are satisfiable, so no clause holds vacuously. Total-function conventions of the library (inverse of a singular matrix is 000; integral of a non-integrable function is 000) are visible in the statements and are recorded in each item's read-back.

Contributions of any of the milestones are welcome; the measure-theoretic milestones (invariance and uniqueness) and the SL(2,C)SL(2,\mathbb{C})SL(2,C) covering milestones are independent of each other and can be attacked in parallel.

Selected references

  • S. Chatterjee, Lectures on Quantum Field Theory, Stanford University, 2018–19 (scribed lecture notes). https://souravchatterjee.su.domains/qft-lectures-combined.pdf
  • E. P. Wigner, On unitary representations of the inhomogeneous Lorentz group, Annals of Mathematics 40 (1939), 149–204. https://doi.org/10.2307/1968551
18 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: wenxinzhang

Vector Space Methods V: Convex Separation and Distance DualityTextbook

Motivation

Linear approximation is only one instance of distance minimization. Feasible sets in optimization are typically convex rather than subspaces, so a useful certificate must compare a target point with an entire convex set and must allow an affine offset. Chapter 5 of Luenberger's Optimization by Vector Space Methods builds this certificate through geometric forms of the Hahn--Banach theorem, supporting hyperplanes, and separation of convex sets. The resulting minimum-distance theorem expresses the distance from a point to a convex set as an optimal gap measured by a norm-bounded continuous linear functional (Luenberger, §§5.12--5.13, pp. 130--137).

This mission advances the series from subspace annihilators to affine separation. It formalizes the Minkowski gauge used by the chapter, three progressively stronger separation statements, and a capstone distance-duality certificate. These results are standard infrastructure for constrained optimization: they turn a geometric exclusion or distance into a scalar inequality that can later become a multiplier or a dual bound.

Setting

Let XXX be a real normed space and K⊆XK\subseteq XK⊆X a nonempty convex set. Convexity is represented by Convex ℝ K, and topological interior, closure, and infimum distance use Mathlib's interior, closure, and Metric.infDist. A continuous affine separator is described by a continuous linear functional f:X\toL[R]Rf:X\toL[\mathbb R]\mathbb Rf:X\toL[R]R and a scalar level ccc. The inequality f(k)≤cf(k)\le cf(k)≤c for all k∈Kk\in Kk∈K places KKK in one closed half-space.

When a convex set contains zero in its interior, its Minkowski gauge is the functional gauge K. The source characterizes it by nonnegativity, positive homogeneity, subadditivity, continuity, and the level sets

{x:gK(x)≤1}=K‾,{x:gK(x)<1}=int⁡K.\{x:g_K(x)\le 1\}=\overline K, \qquad \{x:g_K(x)<1\}=\operatorname{int}K.{x:gK​(x)≤1}=K,{x:gK​(x)<1}=intK.

These properties are bundled into the first milestone, following Lemma 1 of §5.12 (pp. 131--132).

For two convex sets K1,K2K_1,K_2K1​,K2​, Eidelheit separation means finding nonzero fff and ccc with f(x)≤c≤f(y)f(x)\le c\le f(y)f(x)≤c≤f(y) for x∈K1x\in K_1x∈K1​ and y∈K2y\in K_2y∈K2​. The source assumes that K1K_1K1​ has nonempty interior and that its interior does not meet K2K_2K2​. The Lean statement records the nonemptiness of K2K_2K2​ explicitly, since otherwise nonzero separation is not forced.

Formalization targets

Gauge and geometric Hahn--Banach milestones

Formalize the six gauge properties above. Then, for a convex KKK with nonempty interior and an affine subspace VVV disjoint from that interior, produce f≠0f\ne0f=0 and ccc such that

f(v)=c(v∈V),f(k)<c(k∈int⁡K).f(v)=c\quad(v\in V), \qquad f(k)<c\quad(k\in\operatorname{int}K).f(v)=c(v∈V),f(k)<c(k∈intK).

This is Mazur's geometric Hahn--Banach theorem as stated in §5.12, Theorem 1 (p. 133).

Supporting hyperplanes and convex-set separation

For x∉int⁡Kx\notin\operatorname{int}Kx∈/intK, formalize a nonzero functional satisfying f(k)≤f(x)f(k)\le f(x)f(k)≤f(x) for all k∈Kk\in Kk∈K. Next formalize Eidelheit separation:

f(x)≤c≤f(y)for all x∈K1, y∈K2.f(x)\le c\le f(y) \quad\text{for all }x\in K_1,\ y\in K_2.f(x)≤c≤f(y)for all x∈K1​, y∈K2​.

These are Theorems 2 and 3 of §5.12 (pp. 133--134).

Convex minimum-distance duality

Let x1x_1x1​ have positive distance ddd from KKK. Produce fff and a real upper-bound level ccc with ∥f∥≤1\|f\|\le1∥f∥≤1, f(k)≤cf(k)\le cf(k)≤c on KKK, and

f(x1)−c=d.f(x_1)-c=d.f(x1​)−c=d.

Every other feasible pair (g,b)(g,b)(g,b) must satisfy g(x1)−b≤dg(x_1)-b\le dg(x1​)−b≤d. If x0∈Kx_0\in Kx0​∈K realizes the distance, require −f-f−f to align with x0−x1x_0-x_1x0​−x1​. This is the finite real certificate form of §5.13, Theorem 1 (pp. 136--137).

Significance

The capstone is an exact strong-duality statement for distance to a convex set. A feasible pair (g,b)(g,b)(g,b) yields a certified lower bound on the distance, and the distinguished pair reaches the primal value. Unlike a nearest-point characterization, it remains meaningful when KKK is not closed and no minimizing point exists. The conditional alignment clause identifies the equality case when attainment is available.

Formalizing the chapter's progression creates more than one isolated equality. The gauge package links convex geometry to sublinear analysis; Mazur separation handles affine constraints; the supporting-hyperplane and Eidelheit statements provide reusable interfaces for later multiplier rules. The results are known and proved in the 1969 text; the mission's contribution is a coherent machine-checked Lean layer that preserves the source hypotheses and can support later chapters on duality and optimization.

Difficulty

A direct reuse of subspace distance duality is insufficient because a general convex set is neither closed under subtraction nor described by an annihilator. An affine level ccc is unavoidable. The common shorthand sup⁡k∈Kf(k)\sup_{k\in K} f(k)supk∈K​f(k) introduces a second problem: KKK need not be bounded, so a real-valued supremum is not available for an arbitrary functional. The capstone therefore quantifies over a real upper bound ccc and asserts its optimality through a universal inequality; this records the same finite support value without imposing boundedness absent from the source.

Topological hypotheses also differ across the milestones. Separation uses nonempty interior, whereas the final distance theorem only assumes convexity, nonemptiness, and positive distance. Replacing positive distance by mere exclusion x1∉Kx_1\notin Kx1​∈/K would be invalid for a nonclosed set. Similarly, requiring closure or compactness would make formalization easier but would lose the theorem's intended infinite-dimensional scope.

Formalization scope

The mission is restricted to real normed spaces. Sets use Set X; affine varieties use AffineSubspace ℝ X; separators use ContinuousLinearMap. The gauge is Mathlib's existing gauge, so no competing definition is introduced. The bundled gauge milestone deliberately includes both level-set identities as well as continuity, positive homogeneity for positive real scalars, subadditivity, and nonnegativity.

The Eidelheit theorem includes K₂.Nonempty, an assumption used implicitly by the source's separating conclusion. The capstone includes K.Nonempty and 0 < Metric.infDist x₁ K; it does not assume closedness, boundedness, compactness, or attainment. Its pair (f,c)(f,c)(f,c) represents a finite support level, and the universal comparison over all feasible (g,b)(g,b)(g,b) rules out a weakened statement in which an arbitrarily loose upper bound could trivialize existence. The optional nearest-point clause uses the exact equality ∥x0−x1∥=d\|x_0-x_1\|=d∥x0​−x1​∥=d and fixes the sign of alignment. Contributions may add reusable lemmas on gauges, interiors, affine subspaces, or support bounds, but the public results should remain independent of finite-dimensionality and completeness.

Selected references

  • David G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, 1969, Chapter 5, §§5.11--5.13, pp. 127--137. Public scan.
6 thms3 active usersReviewed
🏆Completed
Convex Optimization·Captain: wenxinzhang

Vector Space Methods VIII: Fenchel DualityTextbook

Motivation

Convex duality converts an optimization problem over points into one over linear functionals. It supplies lower bounds, certificates of optimality, and alternative formulations whose geometry can be simpler than the primal problem. In §§7.8–7.12 of David G. Luenberger's Optimization by Vector Space Methods, this theory is developed for finite-valued convex and concave functions on convex subsets of a real normed space. The capstone is Fenchel duality with restricted domains and an attained continuous-linear-functional dual optimum. This mission preserves that functional-analytic setting rather than reducing the theorem to Euclidean space or silently extending the functions to the whole space.

Setting

Let XXX be a real normed space, let C,D⊆XC,D\subseteq XC,D⊆X be nonempty convex sets, let f:X→Rf:X\to\mathbb Rf:X→R be convex on CCC, and let g:X→Rg:X\to\mathbb Rg:X→R be concave on DDD. For a continuous linear functional ℓ∈X∗\ell\in X^*ℓ∈X∗, the restricted convex conjugate and restricted concave conjugate are

fC∗(ℓ)=sup⁡x∈C(ℓ(x)−f(x)),gD∗(ℓ)=inf⁡x∈D(ℓ(x)−g(x)).f_C^*(\ell)=\sup_{x\in C}\bigl(\ell(x)-f(x)\bigr),\qquad g_D^*(\ell)=\inf_{x\in D}\bigl(\ell(x)-g(x)\bigr).fC∗​(ℓ)=x∈Csup​(ℓ(x)−f(x)),gD∗​(ℓ)=x∈Dinf​(ℓ(x)−g(x)).

The convex conjugate is admitted into C∗C^*C∗ only when its defining set is bounded above; the concave conjugate is admitted into D∗D^*D∗ only when its defining set is bounded below. Because CCC and DDD are nonempty and the functions are real-valued, these predicates exactly exclude the unwanted infinite endpoint. The Lean definitions use real sSup and sInf, with boundedness carried explicitly by theorem hypotheses.

The restricted epigraph of (f,C)(f,C)(f,C) is the set of (x,r)(x,r)(x,r) satisfying x∈Cx\in Cx∈C and f(x)≤rf(x)\le rf(x)≤r; the restricted hypograph of (g,D)(g,D)(g,D) reverses the scalar inequality. Luenberger's qualification requires a common point of the relative interiors of CCC and DDD, represented by Mathlib's intrinsicInterior, and also requires ordinary nonempty interior of at least one of these two graph sets.

Formalization targets

Main goal: Fenchel duality

Assume the finite primal value μ\muμ is the greatest lower bound of

{f(x)−g(x):x∈C∩D}.\{f(x)-g(x):x\in C\cap D\}.{f(x)−g(x):x∈C∩D}.

Prove that some ℓ0∈C∗∩D∗\ell_0\in C^*\cap D^*ℓ0​∈C∗∩D∗ attains

μ=gD∗(ℓ0)−fC∗(ℓ0)=max⁡ℓ∈C∗∩D∗(gD∗(ℓ)−fC∗(ℓ)).\mu=g_D^*(\ell_0)-f_C^*(\ell_0) =\max_{\ell\in C^*\cap D^*} \bigl(g_D^*(\ell)-f_C^*(\ell)\bigr).μ=gD∗​(ℓ0​)−fC∗​(ℓ0​)=ℓ∈C∗∩D∗max​(gD∗​(ℓ)−fC∗​(ℓ)).

If x0x_0x0​ attains the primal infimum, also prove that x0x_0x0​ attains both conjugate extrema at ℓ0\ell_0ℓ0​: fC∗(ℓ0)=ℓ0(x0)−f(x0)f_C^*(\ell_0)=\ell_0(x_0)-f(x_0)fC∗​(ℓ0​)=ℓ0​(x0​)−f(x0​) and gD∗(ℓ0)=ℓ0(x0)−g(x0)g_D^*(\ell_0)=\ell_0(x_0)-g(x_0)gD∗​(ℓ0​)=ℓ0​(x0​)−g(x0​).

Milestones

The mission records four source milestones. A local minimum of a convex function on its convex domain is global (§7.8, Proposition 1). Convexity of a restricted function is equivalent to convexity of its restricted epigraph (§7.8, Proposition 2). The finite-conjugate domain and the convex conjugate are convex (§7.10, Proposition 1). Finally, a closed restricted epigraph agrees pointwise on CCC with the continuous-linear biconjugate (§7.10, Proposition 2). Together these statements expose the geometric and conjugacy interfaces on which the capstone depends without turning every paragraph of the chapter into a separate item.

Significance

The theorem gives an attained dual certificate in an arbitrary real normed space. Equality of primal and dual values eliminates a duality gap, while attainment produces a specific functional that can certify an optimal primal point through simultaneous conjugate equality. The biconjugate milestone is independently useful: it expresses a closed convex function as a supremum of continuous affine minorants on its domain.

Formalizing this material adds a restricted-domain conjugacy API that is not supplied by the existing project artifact named fenchelConjugate. That artifact accepts finite-valued functions on a Euclidean space and has no independent convex domain or concave conjugate. Reusing it here would erase hypotheses that are central to Luenberger's theorem. The new definitions remain small, but their exact boundedness contracts make them reusable for later separation, minimax, and Lagrange-duality missions. The theorem is classical; the mission asks for a checked development faithful to the 1969 source and the current Mathlib representation of continuous dual spaces.

Difficulty

The qualification is not the usual finite-dimensional slogan that relative interiors merely intersect. The source additionally demands that either the restricted epigraph or restricted hypograph have nonempty ordinary interior. Dropping that condition changes the theorem in infinite-dimensional spaces. Replacing intrinsicInterior by topological interior would also make valid lower-dimensional domains appear empty.

Extended values create another boundary. Real sSup and sInf are meaningful here only together with nonempty domains and the respective boundedness hypotheses. Treating their default values outside those hypotheses as genuine conjugates would admit false dual candidates. A finite-dimensional conjugate definition avoids neither issue and would prove only a special case. The biconjugate target must quantify over continuous linear functionals, not all algebraic linear maps, because closed epigraph separation is topological. Finally, the dual statement must include actual attainment; proving only equality with a supremum would omit a principal assertion of §7.12.

Formalization scope

All primal functions are finite-valued real functions. Infinite conjugate values are represented by domain predicates—BddAbove for fC∗f_C^*fC∗​ and BddBelow for gD∗g_D^*gD∗​—rather than by changing the public conjugate codomain. The primal finiteness assumption is encoded by a real number μ\muμ together with IsGLB, which simultaneously rules out an empty feasible intersection and an infimum of −∞-\infty−∞. Epigraph pairs are ordered as (x,r)(x,r)(x,r) to match Mathlib conventions, although Luenberger prints the scalar coordinate first.

The ambient space is normed but is not assumed finite-dimensional, reflexive, or complete. Both CCC and DDD are explicitly nonempty. The main theorem keeps the common intrinsic-interior condition and the disjunctive ordinary-interior condition verbatim. Contributions may develop separation lemmas, boundedness facts for restricted conjugates, or direct proofs of the milestone statements. A whole-space Euclidean specialization is welcome only as a corollary, not as a replacement for the root. The minimax theorem of §7.13 and extended-real lower-semicontinuous variants are outside this mission.

Selected references

  • David G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, 1969, Chapter 7, §§7.8–7.12, pp. 191–202. Open Library record
  • R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press, 1970. DOI: 10.1515/9781400873173
7 thms3 active usersReviewed
🏆Completed
Mathematical PhysicsProbabilityTopology·Captain: Lucas

Ensemble spaces: monodecomposability and separatenessResearch Paper

Motivation

A physical law is a claim about what happens whenever a preparation is repeated, not about a single run. The objects of the law are therefore ensembles: the statistical outputs of a preparation procedure. Classical probability distributions and quantum density operators are two realizations of that idea, and they share a convex structure coming from statistical mixing. Gabriele Carcassi and Christine A. Aidala isolate that structure in the draft chapter Ensemble spaces (12 October 2026), as part of the Assumptions of Physics project (assumptionsofphysics.org).

The convex fragment already separates a classical behaviour from a non-classical one. In a classical ensemble space, an ensemble that is separate from two ensembles is separate from every mixture of them. In a quantum ensemble space it need not be: the equal mixture of two orthogonal pure states is not separate from a pure state in their span. The draft turns this distinction into a theorem that uses only mixing. Monodecomposability — every decomposable ensemble has no two decompositions in which one summand is separate from both summands of the other — holds if and only if mixtures preserve separateness (Proposition 1.35).

This mission formalizes that equivalence and the lemmas of §§1.2–1.3 that it depends on. Entropy, affine embedding, and the open problems of the same draft are later developments and are not assumed here.

Setting

An ensemble space is a nonempty topological space EEE that is T0T_0T0​ and second countable, together with a continuous mixing operation

(p,a,b)↦pa+pˉb,p∈[0,1],pˉ=1−p.(p,a,b)\mapsto pa+\bar p b,\qquad p\in[0,1],\quad \bar p=1-p.(p,a,b)↦pa+pˉ​b,p∈[0,1],pˉ​=1−p.

Mixing is the identity 1a+0b=a1a+0b=a1a+0b=a, idempotent (pa+pˉa=apa+\bar p a=apa+pˉ​a=a), commutative (pa+pˉb=pˉb+papa+\bar p b=\bar p b+papa+pˉ​b=pˉ​b+pa), and associative in the following sense. If p1,p3∈[0,1)p_1,p_3\in[0,1)p1​,p3​∈[0,1), p1+p3≤1p_1+p_3\le 1p1​+p3​≤1 and p2=1−p1−p3p_2=1-p_1-p_3p2​=1−p1​−p3​, then

p1e1+pˉ1(p2pˉ1e2+p3pˉ1e3)=pˉ3(p1pˉ3e1+p2pˉ3e2)+p3e3.p_1 e_1+\bar p_1\Bigl(\frac{p_2}{\bar p_1}e_2+\frac{p_3}{\bar p_1}e_3\Bigr) =\bar p_3\Bigl(\frac{p_1}{\bar p_3}e_1+\frac{p_2}{\bar p_3}e_2\Bigr)+p_3 e_3.p1​e1​+pˉ​1​(pˉ​1​p2​​e2​+pˉ​1​p3​​e3​)=pˉ​3​(pˉ​3​p1​​e1​+pˉ​3​p2​​e2​)+p3​e3​.

In the formalization the operation is mix p a b, equal to pa+pˉbpa+\bar p bpa+pˉ​b. Binary mixing records only the first coefficient.

A finite mixture ∑i=1npiei\sum_{i=1}^n p_i e_i∑i=1n​pi​ei​, for pi∈[0,1]p_i\in[0,1]pi​∈[0,1] with ∑ipi=1\sum_i p_i=1∑i​pi​=1, is the nested mixture (1.11) of the pairs with pi≠0p_i\neq 0pi​=0, in the given order. Reordering the pairs does not change the ensemble (Corollary 1.12).

An ensemble ccc is a component of aaa when a=pc+pˉda=pc+\bar p da=pc+pˉ​d for some ensemble ddd and some p∈(0,1]p\in(0,1]p∈(0,1]. Two ensembles are separate, written a⋔ba\pitchfork ba⋔b, when they have no common component. An extreme point has no component other than itself. An internal point admits every ensemble as a component. A boundary point is a point that is not internal.

A set AAA is bounded around eee when every open neighbourhood UUU of eee admits some p∈[0,1)p\in[0,1)p∈[0,1) with pe+pˉA⊆Upe+\bar p A\subseteq Upe+pˉ​A⊆U.

An ensemble is decomposable when it is a mixture pa+pˉbpa+\bar p bpa+pˉ​b with p∈(0,1)p\in(0,1)p∈(0,1) and a≠ba\neq ba=b; separately decomposable when the two summands may be taken separate; and multidecomposable when it admits two such decompositions

e=pa1+pˉa2=qb1+qˉb2e=pa_1+\bar p a_2=qb_1+\bar q b_2e=pa1​+pˉ​a2​=qb1​+qˉ​b2​

with a1⋔b1a_1\pitchfork b_1a1​⋔b1​ and a1⋔b2a_1\pitchfork b_2a1​⋔b2​. It is monodecomposable when it is not multidecomposable. The space is monodecomposable when every decomposable ensemble is. Mixtures preserve separateness when e⋔ae\pitchfork ae⋔a and e⋔be\pitchfork be⋔b imply e⋔(pa+pˉb)e\pitchfork(pa+\bar p b)e⋔(pa+pˉ​b) for every p∈[0,1]p\in[0,1]p∈[0,1].

Formalization targets

Proposition 1.35 — goal

For an ensemble space EEE,

E is monodecomposable⟺mixtures preserve separateness in E.\text{$E$ is monodecomposable} \quad\Longleftrightarrow\quad \text{mixtures preserve separateness in $E$.}E is monodecomposable⟺mixtures preserve separateness in E.

The two sides are exactly Definitions 1.33 and 1.28. No entropy, orthogonality, or finite-dimensionality hypothesis is added, and none is removed.

Corollary 1.12

For pi∈[0,1]p_i\in[0,1]pi​∈[0,1] with ∑ipi=1\sum_i p_i=1∑i​pi​=1 and any permutation τ\tauτ,

∑ipiei=∑ipτ(i)eτ(i),\sum_i p_i e_i=\sum_i p_{\tau(i)} e_{\tau(i)},i∑​pi​ei​=i∑​pτ(i)​eτ(i)​,

and the common value exists as an ensemble.

Proposition 1.17

A set AAA is bounded around eee if and only if pne+pˉnan→ep_n e+\bar p_n a_n\to epn​e+pˉ​n​an​→e whenever pn→1p_n\to 1pn​→1 in [0,1][0,1][0,1] and an∈Aa_n\in Aan​∈A.

Proposition 1.21

The set of internal points is convex: it is closed under mixing.

Corollary 1.25

Components and separateness satisfy the six properties listed in the draft: every ensemble is a component of itself; a component yields a common component, so the two ensembles are not separate; separateness is irreflexive and symmetric; distinct extreme points are separate; an internal point is not separate from any ensemble; separate ensembles are boundary points.

Proposition 1.27

If eee is separate from pe1+pˉe2pe_1+\bar p e_2pe1​+pˉ​e2​ for some p∈(0,1)p\in(0,1)p∈(0,1), then eee is separate from λe1+λˉe2\lambda e_1+\bar\lambda e_2λe1​+λˉe2​ for every λ∈[0,1]\lambda\in[0,1]λ∈[0,1].

Corollary 1.32

An ensemble is extreme if and only if it is not decomposable.

Significance

Proposition 1.35 is the convex form of the draft's classicality test. One direction says that if mixing can create a common component where none existed, then some ensemble has two genuinely different separate decompositions. The other says that if mixing never does this, then no decomposable ensemble is multidecomposable. The quantum Bloch ball is the draft's witness that the property can fail; the classical simplex is the witness that it can hold. Those two model statements (Proposition 1.34 and Propositions 1.29–1.30) are not part of this mission, but the interface they would plug into is.

The same interface is what the later sections of the draft extend: entropy is defined on a space that already mixes, and affine combinations are built from that mixing. A machine-checked Proposition 1.35 is a base those extensions can import without taking the entropy axiom as a hypothesis they do not use.

The argument in the draft is a proof, not an open problem. It had not been formalized against this 12 October 2026 text. An earlier formalization on this platform records Axioms 4.4, 4.7 and 4.55 of the 31 December 2025 book, in which entropy is part of the same structure. That package is a different source. Importing it here would add the entropy axiom to theorems proved in the draft before entropy is introduced, and would weaken them.

Difficulty

The equivalence is not a rephrasing of the definitions. One direction needs Proposition 1.27, whose proof places an auxiliary ensemble on a segment and rewrites coefficients so that a common component of eee and one mixture becomes a common component of eee and another. The arithmetic is sensitive to which endpoint is which, and to the restriction p∈(0,1)p\in(0,1)p∈(0,1) rather than p∈[0,1]p\in[0,1]p∈[0,1].

Corollary 1.12 is an induction on a bracketed expression, not on an unordered convex combination. Definition 1.10 deletes zero coefficients before bracketing. An encoding that feeds a zero coefficient to binary mixing denotes the same point only after the mixture axioms are applied; the draft's definition does not do that. The statement below follows the draft and deletes zeros first.

Proposition 1.17 is a topological fact about a continuous binary operation on a space that need not be a topological vector space. There is no scalar multiplication to rescale a neighbourhood, so the argument has to manufacture the shrink from mixing alone. Boundedness around eee is not the same as metric boundedness, and the draft does not assume a metric.

Formalization scope

The carrier is a type EEE with a topological-space instance. An EnsembleSpace packages nonemptiness, the T0T_0T0​ and second-countability axioms, and the mixing operation. Coefficients of the operation are elements of the unit interval. In the associativity axiom, each real expression is shown to lie in [0,1][0,1][0,1] and is then used as that element; it is not replaced by a projection.

Finite mixtures are partial. Zero coefficients are removed, order preserved, and the rest is folded by binary mixing as in (1.11). The fold returns no value if every coefficient was zero or a tail sum vanishes. On inputs with nonnegative coefficients at most 111 that sum to 111, Corollary 1.12 asserts that a value exists. Real coefficients that arise while rescaling a tail are passed through the projection onto [0,1][0,1][0,1], which is the identity for data obeying those hypotheses. The empty index set cannot occur under the sum hypothesis: the sum of no coefficients is 0≠10\neq 10=1.

Separateness, components, extreme and internal points, decomposability and monodecomposability are propositions on this structure. A component uses a coefficient in (0,1](0,1](0,1]. A decomposition uses a coefficient in (0,1)(0,1)(0,1) and two distinct ensembles. Multidecomposability asks for two such decompositions, with one summand of the first separate from both summands of the second.

Entropy, orthogonality, affine combinations, vector-space embeddings, metrics, and the classical and quantum models are out of scope. In particular the goal must not be restated as “every Choquet simplex is a simplex”, and separateness must not be replaced by disjointness of supports. Adding the entropy axiom, or cancellativity, is a different theorem. Contributions that build the missing model statements on top of these definitions, without changing them, are the natural continuation; changes to the definitions are not.

Selected references

  • G. Carcassi and C. A. Aidala, Ensemble spaces, draft chapter, 12 October 2026. Axiom 1.4 (p. 12), Axiom 1.7 (p. 13), Definition 1.10 (p. 15), Corollary 1.12 (p. 15), Definition 1.16 and Proposition 1.17 (pp. 17–19), Definitions 1.19, 1.20, 1.24 and Corollary 1.25 (pp. 19–22), Proposition 1.27 (p. 23), Definitions 1.28 and 1.31 (pp. 24–25), Corollary 1.32 (p. 25), Definition 1.33 and Proposition 1.35 (p. 26). The draft states that it is generated from the project sources.
  • G. Carcassi and C. A. Aidala, Assumptions of Physics, project site and sources: assumptionsofphysics.org and github.com/assumptionsofphysics/book.
  • T. Fritz, Convex spaces I: Definition and examples, arXiv:0903.5522, 2009. arXiv:0903.5522. Cited by the draft for the algebraic convex-space axioms matched by Axiom 1.7.
9 thms2 active usersReviewed
Captain: savarin

Sharp diagonal Hlawka constants: lower the cutoff to 16Open Problem

The Hlawka inequality for Schatten ppp-norms is a cousin of the triangle inequality: it relates the norms of three matrices to the norms of their pairwise sums and their total sum. The question is how large a comparison constant is needed to make this inequality hold.

This mission asks whether the best possible constant for complex diagonal matrices, already proved in Lean for every real p≥32p\ge32p≥32, also holds for every real p≥16p\ge16p≥16. This is an open problem: no proof is known. The constant is the one from the foundation mission: the largest comparison constant required by the cyclic family of three 3×33\times33×3 diagonal matrices. Because the cutoff-32 mission already covers every p≥32p\ge32p≥32, the new work is the range from 16 to 32.

The cutoff came down from 256 to 32 across eleven missions. The first phase (256 to 62) used a confinement estimate, exhausted at p=61p=61p=61. The second phase (62 to 32) used a new technique that broke through the confinement barrier. Whether it extends to 16 is not known; 16 asks for sixteen more units below the current best.

This is an entry in the sharp diagonal Hlawka campaign, which asks for the smallest cutoff at which the same formula holds. The campaign conjectures the formula for all p≥2p\ge2p≥2. Any proof for a cutoff of 16 or lower also settles this mission.

The broader question of optimal constants for Schatten norms appears in Audenaert and Kittaneh's Problem 7. Extending the sharp diagonal constant to general matrices is a separate challenge.

References

  • K. M. R. Audenaert and F. Kittaneh, Problems and Conjectures in Matrix and Operator Inequalities, arXiv preprint, 2012, §8.2, Problem 7. arXiv:1201.5232
  • Ezzeri Esa, Hlawka–Schatten inequalities: sharp diagonal construction, Lean source repository, 2026, revision 79aa498bfcf7b22bd91d771fb32ec278e2d4704b. Source library

Established results on Prove2Me

  • The accepted sharp diagonal bound for every real p ≥ 62.
  • The accepted real coordinate bound for every real p ≥ 62.
  • The accepted diagonal Schatten norm identity.
63 thms2 active usersReviewed
🏆Completed
Captain: @bwdaugherty

Sharp diagonal Hlawka constant: cutoff 32Open Problem

Extend the sharp diagonal Hlawka formula to smaller exponents.

The foundation mission establishes the least uniform complex coordinate Hlawka constant for every real exponent p ≥ 256. This entry proposes the cutoff 32: the same cyclic constant must be optimal for every real exponent at or above the proposed cutoff, across all finite complex coordinate dimensions and arbitrary triples, including unequal norms.

Use the foundation's unchanged definitions of the coordinate norm, Hlawka constant, and cyclic constant. The goal combines admissibility and uniform optimality in a single IsLeast statement.

Foundation: https://prove2.me/missions/Sharp_diagonal_Hlawka_constants%3A_foundation_and_proved_cutoff_256

4 thms2 active usersReviewed
🏆Completed
AnalysisProbability·Captain: Lucas

Hamburger Moment Problem (Wikipedia) I: Characterization and Uniqueness of SolutionsTextbook

Motivation

A sequence of real numbers (m0,m1,m2,… )(m_0, m_1, m_2, \dots)(m0​,m1​,m2​,…) often arrives as a list of moments: averages E[Xn]\mathbb E[X^n]E[Xn] of powers of a random variable, traces ⟨Tne,e⟩\langle T^n e, e\rangle⟨Tne,e⟩ of powers of a self-adjoint operator, or coefficients of a continued fraction. The Hamburger moment problem, named after Hans Ludwig Hamburger (1920–21), asks when such a list really comes from a measure on the whole real line, and, when it does, whether the measure is determined by its moments. The question sits at the junction of probability (the method of moments, identification of limit laws), spectral theory of symmetric operators and Jacobi matrices, and the theory of orthogonal polynomials; standard monographs include Shohat–Tamarkin (1943) and Schmüdgen (2017).

Timeline (as summarized in the source article and its references):

  1. 1894 — Stieltjes treats the analogous problem on [0,+∞)[0,+\infty)[0,+∞) (the Stieltjes moment problem).
  2. 1920–21 — Hamburger extends the theory to the whole real line: solvability is equivalent to positivity of the Hankel kernel (mj+k)(m_{j+k})(mj+k​).
  3. 1920s — Carleman gives a growth condition on the moments guaranteeing uniqueness (Carleman's condition); the factorial growth bound ∣mn∣≤CDnn!|m_n| \le C D^n n!∣mn​∣≤CDnn! is a special case (Reed–Simon 1975, p. 205).
  4. Later — the operator-theoretic treatment through self-adjoint extensions of the shift operator and its spectral measure becomes standard (Reed–Simon 1975, p. 145).

Setting

Let m=(mn)n≥0m = (m_n)_{n \ge 0}m=(mn​)n≥0​ be a sequence of real numbers. A solution of the Hamburger moment problem for mmm is a positive Borel measure μ\muμ on R\mathbb RR such that every power xnx^nxn is μ\muμ-integrable and

mn=∫−∞∞xn dμ(x)(n=0,1,2,… ).m_n = \int_{-\infty}^{\infty} x^n \, d\mu(x) \qquad (n = 0, 1, 2, \dots).mn​=∫−∞∞​xndμ(x)(n=0,1,2,…).

The sequence mmm is a moment sequence if at least one solution exists.

The Hankel kernel of mmm is the infinite matrix A=(mj+k)j,k≥0A = (m_{j+k})_{j,k \ge 0}A=(mj+k​)j,k≥0​. It is positive definite (in the sense of the source) if

∑j,k≥0mj+k cjck‾  ≥  0\sum_{j,k \ge 0} m_{j+k}\, c_j \overline{c_k} \;\ge\; 0j,k≥0∑​mj+k​cj​ck​​≥0

for every finitary complex sequence (cj)j≥0(c_j)_{j \ge 0}(cj​)j≥0​, i.e. cj=0c_j = 0cj​=0 for all but finitely many jjj. Its finite sections are the (n+1)×(n+1)(n+1)\times(n+1)(n+1)×(n+1) Hankel matrices

Δn=(mi+j)0≤i,j≤n.\Delta_n = (m_{i+j})_{0 \le i,j \le n}.Δn​=(mi+j​)0≤i,j≤n​.

In the Lean development these objects are IsMomentMeasure m μ, IsMomentSequence m, hankelForm m c, HankelPosDef m and hankelMatrix m n, all in the namespace HamburgerMoment.

Formalization targets

Goal — Hamburger's characterization

m is a moment sequence  ⟺  ∑j,k≥0mj+kcjck‾≥0 for every finitary (cj)⊂C.m \text{ is a moment sequence} \iff \sum_{j,k \ge 0} m_{j+k} c_j \overline{c_k} \ge 0 \text{ for every finitary } (c_j) \subset \mathbb C.m is a moment sequence⟺j,k≥0∑​mj+k​cj​ck​​≥0 for every finitary (cj​)⊂C.

Milestones

  1. The identity ∑j,kmj+kcjck‾=∫∣∑jcjxj∣2 dμ(x)\sum_{j,k} m_{j+k} c_j \overline{c_k} = \int |\sum_j c_j x^j|^2 \, d\mu(x)∑j,k​mj+k​cj​ck​​=∫∣∑j​cj​xj∣2dμ(x) for any solution μ\muμ, and the resulting "only if" direction.
  2. The "if" direction: a positive definite Hankel kernel is the kernel of a moment sequence.
  3. The solution set is convex; hence a solvable problem has either a unique solution or infinitely many.
  4. Positivity of AAA gives det⁡Δn≥0\det \Delta_n \ge 0detΔn​≥0 for all nnn; if det⁡Δn=0\det \Delta_n = 0detΔn​=0 for some nnn, the solution is unique and finitely supported.
  5. Uniqueness under the growth bound ∣mn∣≤CDnn!|m_n| \le C D^n n!∣mn​∣≤CDnn!.
  6. Existence of moment sequences with more than one solution.
  7. The real-polynomial identity ∫p2 dμ=∑j,kajakmj+k≥0\int p^2 \, d\mu = \sum_{j,k} a_j a_k m_{j+k} \ge 0∫p2dμ=∑j,k​aj​ak​mj+k​≥0, and the characterization of moment sequences by positive semidefiniteness of all real Hankel matrices Δn\Delta_nΔn​.

Significance

The result. Hamburger's theorem turns an existence question about measures into a family of finite-dimensional positivity conditions that can be checked on the data. It is the basic tool behind the method of moments in probability (identifying a distribution from its moments, when the problem is determinate), behind the spectral theory of Jacobi matrices, and behind Gauss quadrature and orthogonal polynomials on the line. The uniqueness criteria decide when moments determine a law; the non-uniqueness examples (for instance the log-normal distribution) show that they do not always do so.

Formalizing it. All results here are classical and proved in the literature; to the best of the captain's knowledge none of them is currently available as a formal statement in Mathlib, which has neither moment problems nor Hankel kernels. The mission produces a reusable vocabulary (moment measures, Hankel forms and matrices) and machine-checked versions of the existence theorem, the uniqueness criteria and the non-uniqueness phenomenon.

Difficulty

The "only if" direction is a direct computation. The converse is the substance: from positivity of countably many finite quadratic forms one must produce a countably additive measure on a non-compact space with all moments matching. Compactness arguments on finite sections give measures whose low-order moments match, but mass can escape to infinity and higher moments need not converge; the source's route instead goes through the Hilbert space completion of finitary sequences, self-adjoint extensions of the (generally unbounded) shift operator and the spectral theorem for unbounded self-adjoint operators — machinery that is only partly present in Mathlib. An alternative route via positive linear functionals on polynomials (M. Riesz extension, Riesz–Markov–Kakutani) has to control the same escape of mass. The uniqueness criterion requires quasi-analyticity or Carleman-type estimates.

Formalization scope

  1. Sequences are m : ℕ → ℝ; measures are Measure ℝ on the Borel σ-algebra of R\mathbb RR. A solution must have every power xnx^nxn integrable, so in particular μ\muμ is finite with total mass m0m_0m0​.
  2. Finitary complex sequences are finitely supported functions ℕ →₀ ℂ, and the Hankel form is the finite double sum over the support. "≥0\ge 0≥0" is the order on C\mathbb CC (the value is a nonnegative real number), matching the source.
  3. Δn\Delta_nΔn​ is the real matrix indexed by Fin (n + 1); positive semidefiniteness is Mathlib's Matrix.PosSemidef.
  4. Uniqueness statements quantify over all solutions; finite support means the solution vanishes outside a finite set.

Needed infrastructure and welcome contributions: polynomial integrability under finite moments, positive linear functionals on R[x]\mathbb R[x]R[x], a Riesz–Markov or spectral-measure construction on R\mathbb RR, Vandermonde arguments for finitely supported measures, and Carleman / quasi-analyticity estimates. The definitions of moment measures and Hankel kernels are reusable for the Stieltjes and Hausdorff moment problems.

Selected references

  • Wikipedia, Hamburger moment problem, revision oldid=1356180072, https://en.wikipedia.org/w/index.php?title=Hamburger_moment_problem&oldid=1356180072
  • H. Hamburger, Über eine Erweiterung des Stieltjesschen Momentenproblems, Math. Ann. 81 (1920), 235–319; 82 (1921), 120–164, 168–187.
  • M. Reed, B. Simon, Methods of Modern Mathematical Physics II: Fourier Analysis, Self-Adjointness, Academic Press, 1975, pp. 145, 205.
  • T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, 1978, pp. 56, 73.
  • K. Schmüdgen, The Moment Problem, Graduate Texts in Mathematics 277, Springer, 2017. https://doi.org/10.1007/978-3-319-64546-9
  • J. A. Shohat, J. D. Tamarkin, The Problem of Moments, AMS, 1943.
15 thms2 active usersReviewed
🏆Completed
Harmonic Analysis·Captain: Lucas

Schwartz Space (Wikipedia): the Fourier Transform is an Automorphism of 𝒮(ℝⁿ)Textbook

Motivation

The Schwartz space S(Rn)\mathcal{S}(\mathbb{R}^n)S(Rn) of smooth, rapidly decreasing functions is the standard domain on which Fourier analysis on Rn\mathbb{R}^nRn works without integrability caveats. Its defining property, singled out in the lead of the source article, is that the Fourier transform maps S(Rn)\mathcal{S}(\mathbb{R}^n)S(Rn) isomorphically onto itself. By duality this allows the Fourier transform to be defined on the dual space S′(Rn)\mathcal{S}'(\mathbb{R}^n)S′(Rn) of tempered distributions, which is the setting of the modern theory of linear partial differential equations (Hörmander, Vol. I) and of much of mathematical physics (Reed–Simon, Vol. I). The space is named after Laurent Schwartz.

This mission formalizes the definition and the elementary analytic properties of S(Rn)\mathcal{S}(\mathbb{R}^n)S(Rn) exactly as stated in the Wikipedia article Schwartz space (revision 1360762580), with the Fourier-automorphism property as the goal.

Setting

Write Rn\mathbb{R}^nRn for the coordinate space with the Euclidean norm ∣x∣=(x12+⋯+xn2)1/2|x| = (x_1^2 + \dots + x_n^2)^{1/2}∣x∣=(x12​+⋯+xn2​)1/2 and Lebesgue measure. A multi-index is a tuple α=(α1,…,αn)∈Nn\alpha = (\alpha_1, \dots, \alpha_n) \in \mathbb{N}^nα=(α1​,…,αn​)∈Nn, and xα=x1α1⋯xnαnx^\alpha = x_1^{\alpha_1} \cdots x_n^{\alpha_n}xα=x1α1​​⋯xnαn​​. For a function f:Rn→Cf : \mathbb{R}^n \to \mathbb{C}f:Rn→C, ∂if\partial_i f∂i​f denotes the partial derivative in the iii-th coordinate direction and

Dβf=∂1β1⋯∂nβnf.D^\beta f = \partial_1^{\beta_1} \cdots \partial_n^{\beta_n} f .Dβf=∂1β1​​⋯∂nβn​​f.

For α,β∈Nn\alpha, \beta \in \mathbb{N}^nα,β∈Nn put

∥f∥α,β=sup⁡x∈Rn∣xα(Dβf)(x)∣∈[0,∞].\|f\|_{\alpha,\beta} = \sup_{x \in \mathbb{R}^n} \bigl| x^\alpha (D^\beta f)(x) \bigr| \in [0, \infty].∥f∥α,β​=x∈Rnsup​​xα(Dβf)(x)​∈[0,∞].

The Schwartz space is

S(Rn,C)={f∈C∞(Rn,C):∥f∥α,β<∞ for all α,β∈Nn}.\mathcal{S}(\mathbb{R}^n, \mathbb{C}) = \bigl\{ f \in C^\infty(\mathbb{R}^n, \mathbb{C}) : \|f\|_{\alpha,\beta} < \infty \text{ for all } \alpha, \beta \in \mathbb{N}^n \bigr\}.S(Rn,C)={f∈C∞(Rn,C):∥f∥α,β​<∞ for all α,β∈Nn}.

Informally, fff and all its derivatives decay at infinity faster than any reciprocal power of ∣x∣|x|∣x∣.

The Fourier transform of f:Rn→Cf : \mathbb{R}^n \to \mathbb{C}f:Rn→C is

(Ff)(ξ)=∫Rne−2πi⟨x,ξ⟩f(x) dx.(\mathcal{F} f)(\xi) = \int_{\mathbb{R}^n} e^{-2\pi i \langle x, \xi \rangle} f(x) \, dx .(Ff)(ξ)=∫Rn​e−2πi⟨x,ξ⟩f(x)dx.

In the Lean development these objects are SchwartzSpaceWiki.monomial, partialDeriv, iteratedPartialDeriv, schwartzSeminorm, schwartzSpace n and fourierTransform.

Formalization targets

Goal: the Fourier transform is an automorphism of S(Rn)\mathcal{S}(\mathbb{R}^n)S(Rn)

F:S(Rn)→S(Rn) is a linear bijection.\mathcal{F} : \mathcal{S}(\mathbb{R}^n) \to \mathcal{S}(\mathbb{R}^n) \text{ is a linear bijection.}F:S(Rn)→S(Rn) is a linear bijection.

Formally: Set.BijOn fourierTransform (schwartzSpace n) (schwartzSpace n) together with F(f+cg)=Ff+c Fg\mathcal{F}(f + c g) = \mathcal{F} f + c\,\mathcal{F} gF(f+cg)=Ff+cFg for f,g∈S(Rn)f, g \in \mathcal{S}(\mathbb{R}^n)f,g∈S(Rn) and c∈Cc \in \mathbb{C}c∈C.

Milestones (in the order of the source)

  1. S(Rn)\mathcal{S}(\mathbb{R}^n)S(Rn) is a complex linear subspace of C∞(Rn,C)C^\infty(\mathbb{R}^n, \mathbb{C})C∞(Rn,C).
  2. xαe−a∣x∣2∈S(Rn)x^\alpha e^{-a|x|^2} \in \mathcal{S}(\mathbb{R}^n)xαe−a∣x∣2∈S(Rn) for every multi-index α\alphaα and every a>0a > 0a>0.
  3. Cc∞(Rn)⊆S(Rn)C_c^\infty(\mathbb{R}^n) \subseteq \mathcal{S}(\mathbb{R}^n)Cc∞​(Rn)⊆S(Rn): smooth compactly supported functions are Schwartz functions.
  4. P(x)e−a∣x∣2∈S(Rn)P(x) e^{-a|x|^2} \in \mathcal{S}(\mathbb{R}^n)P(x)e−a∣x∣2∈S(Rn) for every polynomial PPP and a>0a > 0a>0, and P↦Pe−a∣x∣2P \mapsto P e^{-a|x|^2}P↦Pe−a∣x∣2 is injective.
  5. f,g∈S(Rn)⇒fg∈S(Rn)f, g \in \mathcal{S}(\mathbb{R}^n) \Rightarrow fg \in \mathcal{S}(\mathbb{R}^n)f,g∈S(Rn)⇒fg∈S(Rn).
  6. If f∈S(Rn)f \in \mathcal{S}(\mathbb{R}^n)f∈S(Rn) and ggg is smooth and bounded with all its derivatives, then fg∈S(Rn)fg \in \mathcal{S}(\mathbb{R}^n)fg∈S(Rn).
  7. Every f∈S(Rn)f \in \mathcal{S}(\mathbb{R}^n)f∈S(Rn) is Lipschitz, hence uniformly continuous.
  8. For 1≤p<∞1 \le p < \infty1≤p<∞, S(Rn)⊆Lp(Rn)\mathcal{S}(\mathbb{R}^n) \subseteq L^p(\mathbb{R}^n)S(Rn)⊆Lp(Rn) and it is dense there.

Significance

The result itself. The automorphism property is what makes S(Rn)\mathcal{S}(\mathbb{R}^n)S(Rn) the natural test-function space for tempered distributions: the Fourier transform of a tempered distribution TTT is defined by ⟨FT,φ⟩=⟨T,Fφ⟩\langle \mathcal{F} T, \varphi \rangle = \langle T, \mathcal{F} \varphi \rangle⟨FT,φ⟩=⟨T,Fφ⟩, which only makes sense because Fφ\mathcal{F}\varphiFφ is again a Schwartz function. Density in LpL^pLp (milestone 8) is what lets identities proved on Schwartz functions, such as Plancherel's theorem, extend to L2L^2L2 and other LpL^pLp spaces. The closure properties (milestones 1, 5, 6) say that S(Rn)\mathcal{S}(\mathbb{R}^n)S(Rn) is an algebra and a module over smooth functions with bounded derivatives.

Formalizing it. All results here are classical. Mathlib contains a Schwartz-space type SchwartzMap built on iterated Fréchet derivatives and the norm ∥x∥k\|x\|^k∥x∥k, together with a Fourier transform on it. This mission instead states everything for the concrete, coordinate-wise multi-index definition used in the source. A complete development therefore includes a proof that the two definitions agree, which is reusable on its own.

Difficulty

The multi-index seminorms sup⁡∣xαDβf∣\sup |x^\alpha D^\beta f|sup∣xαDβf∣ are coordinate-wise, while the standard library works with the total derivative and the full norm ∣x∣k|x|^k∣x∣k. The comparison needs inequalities in both directions between ∣xα∣|x^\alpha|∣xα∣ and powers of ∣x∣|x|∣x∣, and between the iterated partial derivatives DβfD^\beta fDβf and the norm of the kkk-th Fréchet derivative. For the goal, surjectivity is the hard part: it needs the Fourier inversion formula on S(Rn)\mathcal{S}(\mathbb{R}^n)S(Rn), not only the fact that F\mathcal{F}F preserves decay and smoothness. For milestone 8, density requires approximating arbitrary LpL^pLp functions, e.g. by compactly supported smooth functions, and this does not follow from the definition of S\mathcal{S}S alone.

Formalization scope

  • Rn\mathbb{R}^nRn is EuclideanSpace ℝ (Fin n) (Euclidean norm, Lebesgue volume). Functions take values in C\mathbb{C}C. n=0n = 0n=0 is allowed.
  • Smoothness is ContDiff ℝ (⊤ : ℕ∞), i.e. C∞C^\inftyC∞ (not analyticity).
  • ∂if(x)\partial_i f(x)∂i​f(x) is fderiv ℝ f x (EuclideanSpace.single i 1), and DβD^\betaDβ applies ∂1β1,…,∂nβn\partial_1^{\beta_1}, \dots, \partial_n^{\beta_n}∂1β1​​,…,∂nβn​​ in a fixed order. For smooth fff the order does not matter.
  • The seminorm ∥f∥α,β\|f\|_{\alpha,\beta}∥f∥α,β​ is a supremum in [0,∞][0, \infty][0,∞] (ℝ≥0∞), so "<∞< \infty<∞" really means bounded. A real-valued supremum would return 000 on unbounded sets and trivialize the definition.
  • The source does not fix a Fourier normalisation. The convention e−2πi⟨x,ξ⟩e^{-2\pi i\langle x,\xi\rangle}e−2πi⟨x,ξ⟩ is used. fourierTransform is a Bochner integral, which is 000 for non-integrable integrands. Every target only applies it to Schwartz functions, which are integrable.
  • The goal is stated as a bijection of the set schwartzSpace n onto itself plus linearity on it. It does not presuppose that schwartzSpace n has been given a module structure.
  • Not included: the topological statements of the source (that S(Rn)\mathcal{S}(\mathbb{R}^n)S(Rn) is a nuclear Montel Fréchet space, ultrabornological, reflexive, etc., and the corresponding facts for its strong dual). They require equipping the set with its seminorm topology, which this mission does not define. They are natural follow-up missions.

Contributions welcome: the equivalence with Mathlib's SchwartzMap, coordinate–norm comparison lemmas for xαx^\alphaxα, and the Leibniz rule for iteratedPartialDeriv.

Selected references

  • Wikipedia contributors, Schwartz space, revision 1360762580. https://en.wikipedia.org/w/index.php?title=Schwartz_space&oldid=1360762580
  • L. Hörmander, The Analysis of Linear Partial Differential Operators I, 2nd ed., Springer, 1990. ISBN 3-540-52343-X.
  • M. Reed, B. Simon, Methods of Modern Mathematical Physics I: Functional Analysis, revised ed., Academic Press, 1980. ISBN 0-12-585050-6.
  • E. M. Stein, R. Shakarchi, Fourier Analysis: An Introduction, Princeton University Press, 2003. ISBN 0-691-11384-X.
  • F. Trèves, Topological Vector Spaces, Distributions and Kernels, Dover, 2006 [1967]. ISBN 978-0-486-45352-1.
10 thms2 active usersReviewed
🏆Completed
Mathematical Physics·Captain: Lucas

The unphysicality of Hilbert spaces (Carcassi–Aidala–Calderón)Research Paper

Motivation

Quantum states are standardly modelled as rays in a complex Hilbert space, following von Neumann's 1932 axiomatisation. Carcassi, Aidala and Calderón (arXiv:2308.06669) examine which parts of this definition can be justified by physical requirements. They argue that the inner product space structure is physically required — it is exactly what is needed to describe statistical mixtures of states and their entropy — while completeness in infinite dimensions is not: it forces the state space to contain states with infinite expectation values, coordinate changes that turn finite expectations into infinite ones, and time evolutions that do so in finite time. The paper suggests Schwartz spaces as a possible alternative.

The physical conclusions of the paper (its Propositions 19 and 31) are arguments, not mathematical theorems. Behind them, however, sits a set of precise mathematical statements in Section VI and Appendix A. This mission formalizes those statements.

Setting

Let HHH be a complex inner product space, not necessarily complete. For ψ∈H\psi\in Hψ∈H, ∣ψ⟩⟨ψ∣|\psi\rangle\langle\psi|∣ψ⟩⟨ψ∣ is the operator x↦⟨ψ,x⟩ψx\mapsto\langle\psi,x\rangle\psix↦⟨ψ,x⟩ψ. A finite mixture of pure states is an operator ∑iai∣ψi⟩⟨ψi∣\sum_i a_i|\psi_i\rangle\langle\psi_i|∑i​ai​∣ψi​⟩⟨ψi​∣ with finitely many unit vectors ψi\psi_iψi​ and weights ai>0a_i>0ai​>0 summing to 111. The von Neumann entropy of such an operator is S(ρ)=−∑kλklog⁡λkS(\rho)=-\sum_k\lambda_k\log\lambda_kS(ρ)=−∑k​λk​logλk​ over its eigenvalues, and I(ψ,ϕ)I(\psi,\phi)I(ψ,ϕ) denotes the entropy of the equal mixture 12∣ψ⟩⟨ψ∣+12∣ϕ⟩⟨ϕ∣\frac12|\psi\rangle\langle\psi|+\frac12|\phi\rangle\langle\phi|21​∣ψ⟩⟨ψ∣+21​∣ϕ⟩⟨ϕ∣.

On the position side, L2(R)L^2(\mathbb R)L2(R) is the Hilbert space of square-integrable complex wave functions. An orientation-preserving diffeomorphism f:R→Rf:\mathbb R\to\mathbb Rf:R→R (smooth, strictly increasing, with smooth inverse) acts on wave functions by

(Ufψ)(y)=ψ(f−1(y))∣(f−1)′(y)∣,(U_f\psi)(y)=\psi\bigl(f^{-1}(y)\bigr)\sqrt{|(f^{-1})'(y)|},(Uf​ψ)(y)=ψ(f−1(y))∣(f−1)′(y)∣​,

which is the transformation law of a wave function under the change of coordinate y=f(x)y=f(x)y=f(x). The nnn-th absolute position moment of a state ψ\psiψ is ∫∣x∣n∣ψ(x)∣2 dx∈[0,∞]\int|x|^n|\psi(x)|^2\,dx\in[0,\infty]∫∣x∣n∣ψ(x)∣2dx∈[0,∞]; finite moments of all orders are the natural minimal requirement for the statistics of position to be well defined.

Formalization targets

Goal

∃ f, U=Uf, ψ∈L2(R), ∥ψ∥=1:∫∣x∣n∣ψ∣2<∞  ∀n,∫y2 ∣Uψ(y)∣2 dy=∞.\exists\,f,\ U=U_f,\ \psi\in L^2(\mathbb R),\ \|\psi\|=1:\quad \int|x|^n|\psi|^2<\infty\ \ \forall n,\qquad \int y^2\,|U\psi(y)|^2\,dy=\infty .∃f, U=Uf​, ψ∈L2(R), ∥ψ∥=1:∫∣x∣n∣ψ∣2<∞  ∀n,∫y2∣Uψ(y)∣2dy=∞.

A unitary transformation of L2(R)L^2(\mathbb R)L2(R) that is nothing but a change of the position coordinate can map a state with all moments finite to one with infinite expected squared position. The goal is stated existentially, leaving the particular change of coordinates free.

Milestones

  1. Proposition 5 — rays alone do not determine the coefficients of a superposition.
  2. Proposition 7 — equal strictly convex mixtures span the same subspace.
  3. Proposition 8 — a finite-rank mixed state can be decomposed so as to include a given pure state from its range.
  4. Proposition 9 — ψ\psiψ is a superposition of {ϕj}\{\phi_j\}{ϕj​} iff some mixture of the ϕj\phi_jϕj​ can also be written as a mixture including ψ\psiψ.
  5. Proposition 10 — I(ψ,ϕ)=f(∣⟨ψ,ϕ⟩∣)I(\psi,\phi)=f(|\langle\psi,\phi\rangle|)I(ψ,ϕ)=f(∣⟨ψ,ϕ⟩∣) with an explicit fff injective on [0,1][0,1][0,1].
  6. Proposition 20 — the domain of an unbounded closed operator between Hilbert spaces is not complete.
  7. Proposition 21 — a unitary can move a vector out of such a domain.
  8. Proposition 24 — UfU_fUf​ is unitary on L2(R)L^2(\mathbb R)L2(R).
  9. Equation (29) — y(x)=tan⁡(π2erf⁡x)y(x)=\tan(\frac\pi2\operatorname{erf}x)y(x)=tan(2π​erfx) is an orientation-preserving diffeomorphism transporting the Gaussian state e−x2/π\sqrt{e^{-x^2}/\sqrt\pi}e−x2/π​​ to 1/π(y2+1)1/\sqrt{\pi(y^2+1)}1/π(y2+1)​.
  10. Equations (27)–(28) — the Gaussian state has all moments finite, the Lorentzian state has all moments of order ≥2\ge2≥2 infinite.

Significance

The goal makes precise one of the paper's three claims about completeness: being an isomorphism of Hilbert spaces does not respect finiteness of expectation values, even for a transformation as innocuous as a smooth change of coordinates. Propositions 20 and 21 make precise the companion claim that completeness forces the inclusion of states outside the domain of every unbounded observable, and that unitaries do not preserve such domains. Propositions 7–10 make precise the paper's case for the inner product: equivalence of superposition with non-unique decomposition of mixtures, and the entropic meaning of the transition probability.

All statements are mathematically elementary relative to modern functional analysis, and none of them, to the knowledge of the proposer, has a machine-checked proof. Formalizing them pins down hypotheses the paper leaves implicit: two statements needed corrections to be true (see the notes on Propositions 8 and 20).

Difficulty

Most of the work is infrastructure rather than a single hard step. Proposition 24 requires the change-of-variables formula for Lebesgue integrals and a construction of the induced operator on L2L^2L2 equivalence classes, including surjectivity. Equation (29) requires developing the error function (limits ±1\pm1±1 at ±∞\pm\infty±∞, smoothness, positivity of its derivative) and differentiating tan⁡∘(π2erf⁡)\tan\circ(\frac\pi2\operatorname{erf})tan∘(2π​erf). Proposition 10 requires computing the spectrum of a rank-two operator through the eigenvalue API for self-adjoint operators on a finite-dimensional space. Proposition 20 rests on the closed graph theorem. The moment statements require Gaussian integrability and a comparison of ∣y∣n/(1+y2)|y|^n/(1+y^2)∣y∣n/(1+y2) with 1/∣y∣1/|y|1/∣y∣ at infinity.

Formalization scope

All statements live in the namespace UnphysicalHilbert. State spaces are complex inner product spaces (InnerProductSpace ℂ H), completeness assumed only where the paper assumes a Hilbert space. Finite sets of states are finite indexed families; a finite-rank density operator is a finite strictly convex combination of pure states. The entropy of the equal mixture is computed on the span of the two vectors, on which the operator acts. L2(R)L^2(\mathbb R)L2(R) is Lp ℂ 2 volume, unitaries are linear isometric equivalences, and finiteness of a moment means Lebesgue integrability of ∣x∣n∣ψ(x)∣2|x|^n|\psi(x)|^2∣x∣n∣ψ(x)∣2.

Two departures from the text are deliberate and flagged in the item notes: Proposition 8 assumes ψ∈range⁡ρ\psi\in\operatorname{range}\rhoψ∈rangeρ instead of ⟨ψ∣ρ∣ψ⟩≠0\langle\psi|\rho|\psi\rangle\neq0⟨ψ∣ρ∣ψ⟩=0 (the latter admits a counterexample in C2\mathbb C^2C2), and Propositions 20–21 assume the operator is closed (without some such hypothesis an everywhere-defined discontinuous functional is a counterexample). Proposition 5 assumes the coefficients are nonzero, which its proof uses. The time evolution of eq. (30) and the remarks on Schwartz spaces in Section VIII are not formalized, because the paper does not state them as propositions. The existential goal cannot be satisfied trivially: the operator is pinned to the change-of-variables formula, and ψ\psiψ must be a unit vector with all moments finite.

Contributions of reusable infrastructure are welcome, in particular: the error function, the unitary on L2(R)L^2(\mathbb R)L2(R) induced by a diffeomorphism, and the spectrum of 12(∣ψ⟩⟨ψ∣+∣ϕ⟩⟨ϕ∣)\frac12(|\psi\rangle\langle\psi|+|\phi\rangle\langle\phi|)21​(∣ψ⟩⟨ψ∣+∣ϕ⟩⟨ϕ∣).

Selected references

  • G. Carcassi, C. A. Aidala, F. Calderón, The unphysicality of Hilbert spaces, arXiv:2308.06669v3, 2024. https://arxiv.org/abs/2308.06669
  • J. von Neumann, Mathematische Grundlagen der Quantenmechanik, Springer, 1932.
  • M. Reed, B. Simon, Methods of Modern Mathematical Physics I: Functional Analysis, Academic Press, 1980.
  • B. C. Hall, Quantum Theory for Mathematicians, Graduate Texts in Mathematics 267, Springer, 2013. https://doi.org/10.1007/978-1-4614-7116-5
13 thms2 active usersReviewed
🏆Completed
Captain: Lucas

Garrett Functional Analysis Notes I: Completeness and Quasi-completenessTextbook

Motivation

Completeness of a normed or metric space is the property behind most existence theorems in analysis: limits of approximations, fixed points, integrals. Many of the spaces that matter in analysis and in the theory of distributions are not metrizable, though: the space Cc∞(Rn)C_c^\infty(\mathbb R^n)Cc∞​(Rn) of test functions, weak-star duals, and spaces of operators with the strong or weak operator topology. For such topological vector spaces the right replacement for sequences is nets, and the plain notion "every Cauchy net converges" turns out to be too strong. Weak-star duals of infinite-dimensional Fréchet spaces, for example, never satisfy it.

Paul Garrett's lecture notes Completeness and quasi-completeness (PDF) argue that the right general notion is quasi-completeness: every bounded Cauchy net converges. They show that it holds for Hilbert, Banach, Fréchet and LF-spaces, for their weak-star duals, and for spaces of continuous linear maps with the topology of pointwise convergence. In the notes, one stated purpose is to justify Gelfand–Pettis integrals of compactly supported continuous functions with values in such spaces, for instance distribution-valued functions.

The results are classical. Boundedness in strict inductive limits goes back to Dieudonné and Schwartz, and the incompleteness of weak duals to Grothendieck (1950). See Bourbaki, Topological Vector Spaces, III.5, and Schaefer, Topological Vector Spaces.

Setting

All vector spaces are over K=R\mathbb K=\mathbb RK=R or C\mathbb CC and all topological vector spaces are Hausdorff. A set BBB in a topological vector space VVV is bounded if every neighbourhood of 000 absorbs it. A net is a map v:I→Vv:I\to Vv:I→V from a directed partially ordered set. It is Cauchy if for every neighbourhood NNN of 000 there is i0i_0i0​ with vi−vj∈Nv_i-v_j\in Nvi​−vj​∈N for all i,j≥i0i,j\ge i_0i,j≥i0​. VVV is complete if every Cauchy net converges, and quasi-complete if every bounded Cauchy net converges.

A Fréchet space is a locally convex, metrizable, complete topological vector space. A locally convex space VVV is the strict colimit of a chain V0⊊V1⊊⋯V_0\subsetneq V_1\subsetneq\cdotsV0​⊊V1​⊊⋯ of subspaces if V=⋃nVnV=\bigcup_n V_nV=⋃n​Vn​, each VnV_nVn​ is closed in Vn+1V_{n+1}Vn+1​, and the topology of VVV is the finest locally convex topology inducing the given topology on every VnV_nVn​. Concretely, a balanced convex set UUU is a neighbourhood of 000 in VVV as soon as every trace U∩VnU\cap V_nU∩Vn​ is a neighbourhood of 000 in VnV_nVn​. An LF-space is a strict colimit of Fréchet spaces; Cc∞(Rn)C_c^\infty(\mathbb R^n)Cc∞​(Rn) is the standard example.

For topological vector spaces X,YX,YX,Y, write Homo(X,Y)\mathrm{Hom}^o(X,Y)Homo(X,Y) for the continuous linear maps X→YX\to YX→Y with the topology given by the seminorms px,U(T)=inf⁡{t>0:Tx∈tU}p_{x,U}(T)=\inf\{t>0: Tx\in tU\}px,U​(T)=inf{t>0:Tx∈tU}, for x∈Xx\in Xx∈X and UUU a convex balanced neighbourhood of 000 in YYY. When YYY is locally convex this is the topology of pointwise convergence. A set EEE of linear maps is equicontinuous if for every neighbourhood UUU of 000 in YYY there is a neighbourhood NNN of 000 in XXX with T(N)⊆UT(N)\subseteq UT(N)⊆U for all T∈ET\in ET∈E.

Formalization targets

Goal: quasi-completeness of operator spaces (Theorem 4.1.1)

X Freˊchet or LF,Y locally convex and quasi-complete ⟹ Homo(X,Y) is quasi-complete.X \text{ Fréchet or LF},\quad Y \text{ locally convex and quasi-complete}\ \Longrightarrow\ \mathrm{Hom}^o(X,Y)\ \text{is quasi-complete.}X Freˊchet or LF,Y locally convex and quasi-complete ⟹ Homo(X,Y) is quasi-complete.

Supporting results (the milestones, in the order of the notes)

  1. Bounded sets and equicontinuous sets in strict colimits are detected on the steps VnV_nVn​ (Propositions 2.1.1 and 2.2.1).
  2. Banach–Steinhaus for Fréchet and LF domains, its Baire-category form, and joint continuity of separately continuous bilinear maps on Fréchet spaces (Theorem 3.0.1, Remark 3.0.2, Corollary 3.0.3).
  3. Sequential completeness implies completeness for nets in metric spaces (Proposition 4.0.1). Quasi-completeness of Fréchet spaces, of closed subspaces and of products. Strict colimits of quasi-complete spaces and test-function spaces are quasi-complete (Proposition 4.0.3 and the remarks around it).
  4. The weak dual of VVV is complete exactly when every linear functional on VVV is continuous (Theorem 5.0.1), so weak duals of infinite-dimensional Fréchet spaces are not complete (Corollary 5.0.2). Weak duals of Fréchet and LF-spaces are nonetheless quasi-complete (Remark 5.0.3). The finest locally convex topology VinitV_{\rm init}Vinit​ and the weak-dual claims 5.0.4–5.0.7 are also included.

Significance

Theorem 4.1.1 makes the strong-operator and weak-operator topologies on bounded operators between Hilbert spaces quasi-complete, and does the same for operators out of test-function spaces. Combined with quasi-completeness of weak-star duals of LF-spaces (Remark 5.0.3), it is what lets vector-valued integration and Cauchy–Goursat-type complex analysis be applied to families of distributions and operators. Banach–Steinhaus for LF-spaces (Theorem 3.0.1) and the Dieudonné–Schwartz description of bounded sets (Proposition 2.1.1) are among the most frequently used facts about distributions.

Mathlib has the Banach–Steinhaus theorem for Banach spaces and barrelled spaces, the topology of pointwise convergence on continuous linear maps, weak duals, and the test-function space D(Ω)\mathcal D(\Omega)D(Ω). It has no general theory of strict inductive limits and no quasi-completeness results of this kind. This mission formalizes that layer: the results are proved on paper, not yet formalized.

Difficulty

The obvious argument for Theorem 4.1.1 takes pointwise limits. That gives a linear map, but continuity of the limit is the real issue: it needs equicontinuity of a merely pointwise-bounded net of operators, which is a Baire-category statement and fails for general domains. For LF domains the Baire argument does not apply directly, because an LF-space is never metrizable when the chain is strictly increasing. The argument has to pass through the steps VnV_nVn​, which needs the description of bounded and equicontinuous sets in a strict colimit. That description depends on each VnV_nVn​ being closed in Vn+1V_{n+1}Vn+1​ and uses Hahn–Banach separation.

Formalization scope

Definitions (namespace GarrettFA, shared by any later missions on these notes):

  1. IsQuasiComplete 𝕜 E and IsNetComplete E follow the notes literally, with nets indexed by directed partial orders. The index type is taken in the universe of E, which is no restriction because Cauchy nets correspond to Cauchy filters.
  2. IsEquicontinuousSet S encodes equicontinuity at 000 as in §2.2.
  3. IsStrictColimit 𝕜 F is a predicate on a chain F : ℕ → Submodule 𝕜 V and the given topology on V, and IsLFSpace and IsFrechetSpace are built from it. The steps carry the subspace topology from VVV. By the Dieudonné–Schwartz theorem this is the same as giving the steps their own topologies, so the class of spaces is the source's.
  4. IsInitTopology 𝕜 V says that the topology of VVV is VinitV_{\rm init}Vinit​. Its existence is a separate theorem item, which rules out a vacuous predicate.

Local convexity is real local convexity (LocallyConvexSpace ℝ, with IsScalarTower ℝ 𝕜), as in Mathlib's distribution theory. Homo(X,Y)\mathrm{Hom}^o(X,Y)Homo(X,Y) is Mathlib's X →Lₚₜ[𝕜] Y. Its topology is the source's px,Up_{x,U}px,U​-topology because YYY is locally convex.

Two statements of the notes are corrected. Theorem 3.0.1 is stated there for arbitrary linear maps; it needs continuous ones, since a single discontinuous functional is pointwise bounded but not equicontinuous. Corollary 5.0.2 claims incompleteness of weak duals of all infinite-dimensional LF-spaces. That fails for the LF-space C∞\mathbb C^\inftyC∞ of Example 1.3.1, whose topology is the finest locally convex one, so its weak dual CN\mathbb C^{\mathbb N}CN is complete. The LF statement is therefore made for LF-spaces with an infinite-dimensional step. Proposition 1.3.5 is built into the formalization, where the steps are subspaces of VVV.

Contributions of reusable infrastructure on strict inductive limits and barrelled spaces are welcome.

Selected references

  • P. Garrett, Completeness and quasi-completeness, lecture notes, 2014. http://www.math.umn.edu/~garrett/m/fun/notes_2012-13/07d_quasi-completeness.pdf
  • N. Bourbaki, Topological Vector Spaces, Chapters 1–5, Springer, 1987. https://doi.org/10.1007/978-3-642-61715-7
  • H. H. Schaefer, M. P. Wolff, Topological Vector Spaces, 2nd ed., Springer GTM 3, 1999. https://doi.org/10.1007/978-1-4612-1468-7
  • A. Grothendieck, Sur la complétion du dual d'un espace vectoriel localement convexe, C. R. Acad. Sci. Paris 230 (1950), 605–606.
28 thms2 active usersReviewed
Analysis·Captain: Lucas

Invariant Subspace ProblemOpen Problem

Motivation

The invariant subspace problem asks whether every bounded linear operator on an infinite-dimensional separable complex Hilbert space leaves some non-trivial closed subspace invariant. It is listed as a high-importance open problem in analysis in the Open Problem Garden (entry) and is widely regarded as one of the most famous open problems in functional analysis. Invariant subspaces are the infinite-dimensional replacement for eigenvectors: in finite dimensions every complex matrix has an eigenvector, and the structure theory of matrices (triangular and Jordan forms) is built from chains of invariant subspaces. Whether any such structure is available for an arbitrary bounded operator on Hilbert space is exactly what the problem asks.

Timeline

  • 1930s (von Neumann, unpublished). Compact operators on Hilbert space have non-trivial closed invariant subspaces.
  • 1954 (Aronszajn–Smith). The compact case on arbitrary Banach spaces (doi:10.2307/1969637).
  • 1966 (Bernstein–Robinson; Halmos). Polynomially compact operators on Hilbert space.
  • 1973 (Lomonosov). Every non-zero compact operator has a non-trivial closed hyperinvariant subspace; consequently every operator commuting with a non-zero compact operator has a non-trivial closed invariant subspace (doi:10.1007/BF01080698).
  • 1975 announced / 1987 published (Enflo). A bounded operator on a separable Banach space with no non-trivial closed invariant subspace (doi:10.1007/BF02392260).
  • 1985 (Read). Such an operator on the classical space ℓ1\ell^1ℓ1 (doi:10.1112/blms/17.4.305).
  • 2011 (Argyros–Haydon). An infinite-dimensional Banach space on which every operator is a scalar plus a compact operator, so that every operator on it has a non-trivial closed invariant subspace (arXiv:0903.3921).

The Hilbert-space question remains open.

Setting

Let K\mathbb{K}K be R\mathbb{R}R or C\mathbb{C}C, let EEE be a normed space over K\mathbb{K}K, and let T ⁣:E→ET\colon E\to ET:E→E be a bounded linear operator. A linear subspace S⊆ES\subseteq ES⊆E is invariant under TTT if T(S)⊆ST(S)\subseteq ST(S)⊆S. It is a non-trivial closed invariant subspace if moreover SSS is closed in the norm topology and {0}≠S≠E\{0\}\neq S\neq E{0}=S=E. A closed subspace SSS with {0}≠S≠E\{0\}\neq S\neq E{0}=S=E is a non-trivial closed hyperinvariant subspace of TTT if A(S)⊆SA(S)\subseteq SA(S)⊆S for every bounded operator AAA with AT=TAAT=TAAT=TA.

A Hilbert space HHH is a complete complex inner product space; it is separable if it has a countable dense subset. An operator KKK is compact if it maps bounded sets to relatively compact sets, and TTT is normal if T∗T=TT∗T^*T=TT^*T∗T=TT∗. In the Lean development these notions are IsInvariantSubspace, IsNontrivialClosedInvariantSubspace, HasNontrivialClosedInvariantSubspace and HasNontrivialClosedHyperinvariantSubspace (namespace InvariantSubspaceProblem), together with Mathlib's IsCompactOperator and IsStarNormal.

Formalization targets

Goal: the invariant subspace problem

∀ H separable, dim⁡H=∞, ∀ T∈B(H):∃ S⊆H closed, {0}≠S≠H, T(S)⊆S.\forall\, H \text{ separable, } \dim H=\infty,\ \forall\, T\in\mathcal{B}(H):\quad \exists\, S\subseteq H \text{ closed},\ \{0\}\neq S\neq H,\ T(S)\subseteq S .∀H separable, dimH=∞, ∀T∈B(H):∃S⊆H closed, {0}=S=H, T(S)⊆S.

The source poses a yes/no question; the goal states the affirmative answer, and a formal proof of its negation equally settles the problem.

Milestones (known results)

  1. Finite-dimensional case: every operator on a complex space of dimension ≥2\ge 2≥2 has a non-trivial invariant subspace.
  2. Non-separable case: every operator on a non-separable complex normed space has a non-trivial closed invariant subspace.
  3. Normal operators on a complex Hilbert space of dimension ≥2\ge 2≥2.
  4. Aronszajn–Smith: compact operators on infinite-dimensional real or complex Banach spaces.
  5. Lomonosov: non-zero compact operators have non-trivial closed hyperinvariant subspaces.
  6. Lomonosov: operators commuting with a non-zero compact operator.
  7. Enflo: a separable infinite-dimensional complex Banach space with an operator having no non-trivial closed invariant subspace.
  8. Read: such an operator on ℓ1\ell^1ℓ1.
  9. Argyros–Haydon: a separable infinite-dimensional real Banach space on which every operator is λI+K\lambda I+KλI+K with KKK compact.
  10. Argyros–Haydon: a separable infinite-dimensional real Banach space on which every operator has a non-trivial closed invariant subspace.

Significance

The result itself. A positive answer would give every bounded operator on Hilbert space a non-trivial piece of structure and would be the first step towards triangular-form type theorems for general operators. A negative answer would, after Enflo and Read, show that even the Hilbert-space geometry does not force invariant subspaces. Either answer resolves a question that has organised much of operator theory since the 1930s.

Formalizing it. The goal is open; no proof, formal or informal, is known. The milestones are proved results whose formal proofs would build reusable infrastructure absent from Mathlib: the Aronszajn–Smith and Lomonosov theorems (the latter through Schauder's fixed point theorem), invariant subspaces from the spectral theorem for normal operators, and the large explicit constructions of Enflo, Read and Argyros–Haydon. None of these results is formalized in Mathlib at the time of writing.

Difficulty

The obvious approach, taking the closed linear span of an orbit {x,Tx,T2x,… }\{x, Tx, T^2x,\dots\}{x,Tx,T2x,…}, fails exactly when every non-zero vector is cyclic, which is the situation that has to be ruled out; for separable spaces nothing prevents this a priori. Spectral methods fail because an operator can have a one-point spectrum and no eigenvectors (quasinilpotent operators). Methods that work on Hilbert space must use the inner-product structure in an essential way, since Enflo's and Read's examples show that the statement is false on some Banach spaces. Lomonosov's technique needs a non-zero compact operator in the commutant, which a general operator need not have.

Formalization scope

Hilbert spaces are Mathlib types H with [NormedAddCommGroup H] [InnerProductSpace ℂ H] [CompleteSpace H]; separability is TopologicalSpace.SeparableSpace H and infinite dimension is ¬ FiniteDimensional ℂ H. Operators are continuous linear maps H →L[ℂ] H. Scalars are complex in the goal. Subspaces are Submodules, and closedness is required explicitly: without it the statement is trivially true in infinite dimensions (the algebraic span of an orbit is a proper invariant subspace), and a published platform statement that omits closedness should not be confused with this problem. Existential milestones quantify over spaces in Type.

Useful infrastructure includes: Schauder's fixed point theorem, Riesz theory of compact operators, the spectral theorem for normal operators, and ℓ1\ell^1ℓ1 machinery for Read's construction. Contributions of reusable lemmas, partial results (for instance further classes of operators known to have invariant subspaces), and proof sketches for the milestones are welcome.

Selected references

  • Open Problem Garden, Invariant subspace problem, posted by T. Chow, 2009. http://www.openproblemgarden.org/op/invariant_subspace_problem
  • N. Aronszajn, K. T. Smith, Invariant subspaces of completely continuous operators, Ann. of Math. 60 (1954) 345–350. https://doi.org/10.2307/1969637
  • V. I. Lomonosov, Invariant subspaces for the family of operators which commute with a completely continuous operator, Funct. Anal. Appl. 7 (1973) 213–214. https://doi.org/10.1007/BF01080698
  • P. Enflo, On the invariant subspace problem for Banach spaces, Acta Math. 158 (1987) 213–313. https://doi.org/10.1007/BF02392260
  • C. J. Read, A solution to the invariant subspace problem on the space ℓ1\ell_1ℓ1​, Bull. London Math. Soc. 17 (1985) 305–317. https://doi.org/10.1112/blms/17.4.305
  • S. A. Argyros, R. G. Haydon, A hereditarily indecomposable L∞\mathcal{L}_\inftyL∞​-space that solves the scalar-plus-compact problem, Acta Math. 206 (2011) 1–54. https://arxiv.org/abs/0903.3921
  • H. Radjavi, P. Rosenthal, The invariant subspace problem, Math. Intelligencer 4 (1982) 33–37.
  • B. S. Yadav, The present state and heritages of the invariant subspace problem, Milan J. Math. 73 (2005) 289–316.
12 thms2 active usersReviewed
🏆Completed
Captain: moona3k

Sharp diagonal Hlawka constants: lower the cutoff to 62Open Problem

This entry lowers the sufficient exponent cutoff for the sharp diagonal Hlawka formula from 63 to 62. For every real p≥62p\ge 62p≥62, the foundation's unchanged cyclic constant is the least constant comparing the triple deficit with the pair-deficit sum for every complex coordinate triple in every finite dimension.

The statement includes unequal and zero input vectors and dimension zero. It concerns complex diagonal matrices through their coordinate norms. It does not settle the conjectured cutoff 2 or the full noncommutative matrix problem.

Goal and companion

  • Exact complex cutoff 62 goal, proved.
  • Real coordinate bound for p≥62p\ge 62p≥62, the supporting milestone, proved.

The confinement radius on this integer is 3643/100003643/100003643/10000. The accepted cutoff-636363 theorem remains the tail this argument calls. Cutoffs 64, 65, 66, and 70 stay proved and are not restated here.

This is the last integer this confinement argument reaches. At p=61p=61p=61 every radius whose tangent model stays positive already makes the budget-777 box factor larger than 111.

5 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity 5: The Three-Operator Forward-Reflected-Backward Method Converges Weakly to a Zero of A + B + CResearch Paper

Three-operator monotone inclusions

Many problems in convex optimization and variational analysis have the form of a monotone inclusion with three pieces of structure: a nonsmooth part that is only accessible through its resolvent (a subdifferential of a proximable function, or a normal cone of a constraint set), a smooth convex part whose gradient is Lipschitz, and a monotone but non-gradient part such as the skew operator (z1,z2)↦(z2,−z1)(z_1,z_2)\mapsto(z_2,-z_1)(z1​,z2​)↦(z2​,−z1​) of a saddle-point problem. Composite saddle-point problems min⁡umax⁡v f(u)+h(u)+Φ(u,v)−g(v)\min_u\max_v\, f(u)+h(u)+\Phi(u,v)-g(v)minu​maxv​f(u)+h(u)+Φ(u,v)−g(v) with a smooth hhh and a bilinear coupling Φ\PhiΦ lead to such inclusions. Splitting methods that use each piece separately, and in the way that is cheapest for it, are the standard tools for these problems.

Timeline of the relevant results:

  • 1979: Lions and Mercier study splitting algorithms for the sum of two monotone operators, among them forward-backward splitting, which needs a cocoercive forward operator (Lions–Mercier 1979).
  • 2000: Tseng's forward-backward-forward method removes cocoercivity for a Lipschitz monotone operator, at the cost of two forward evaluations per iteration (Tseng 2000).
  • 2017: Davis and Yin's three-operator splitting handles A+B′+CA+B'+CA+B′+C with two resolvents and a cocoercive CCC (Davis–Yin 2017).
  • 2020: Malitsky and Tam introduce the forward-reflected-backward method for A+BA+BA+B with BBB monotone and Lipschitz, and in §5 a three-operator variant for A+B+CA+B+CA+B+C with CCC cocoercive (arXiv:1808.04162v4; SIAM J. Optim. 30(2), 2020).

Setting

Let HHH be a real Hilbert space with inner product ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle⟨⋅,⋅⟩. A set-valued operator A:H⇉HA:H\rightrightarrows HA:H⇉H assigns to each xxx a subset A(x)⊆HA(x)\subseteq HA(x)⊆H. It is monotone if ⟨x−y,u−v⟩≥0\langle x-y,u-v\rangle\ge0⟨x−y,u−v⟩≥0 whenever u∈A(x)u\in A(x)u∈A(x), v∈A(y)v\in A(y)v∈A(y), and maximally monotone if moreover its graph is not properly contained in the graph of another monotone operator. For γ>0\gamma>0γ>0, the resolvent JγA=(I+γA)−1J_{\gamma A}=(I+\gamma A)^{-1}JγA​=(I+γA)−1 sends www to the unique point ppp with γ−1(w−p)∈A(p)\gamma^{-1}(w-p)\in A(p)γ−1(w−p)∈A(p).

A single-valued B:H→HB:H\to HB:H→H is monotone if ⟨x−y,B(x)−B(y)⟩≥0\langle x-y,B(x)-B(y)\rangle\ge0⟨x−y,B(x)−B(y)⟩≥0 and L1L_1L1​-Lipschitz if ∥B(x)−B(y)∥≤L1∥x−y∥\|B(x)-B(y)\|\le L_1\|x-y\|∥B(x)−B(y)∥≤L1​∥x−y∥. A single-valued C:H→HC:H\to HC:H→H is 1L2\tfrac1{L_2}L2​1​-cocoercive (L2>0L_2>0L2​>0) if

1L2∥C(x)−C(y)∥2≤⟨C(x)−C(y),x−y⟩∀x,y∈H.\tfrac1{L_2}\|C(x)-C(y)\|^2\le\langle C(x)-C(y),x-y\rangle\qquad\forall x,y\in H.L2​1​∥C(x)−C(y)∥2≤⟨C(x)−C(y),x−y⟩∀x,y∈H.

The problem (46) is to find x∈Hx\in Hx∈H with 0∈(A+B+C)(x)0\in(A+B+C)(x)0∈(A+B+C)(x); its solution set is the zero set (A+B+C)−1(0)={x:−(B+C)(x)∈A(x)}(A+B+C)^{-1}(0)=\{x: -(B+C)(x)\in A(x)\}(A+B+C)−1(0)={x:−(B+C)(x)∈A(x)}. For a step size λ>0\lambda>0λ>0 and initial points x0,x−1∈Hx_0,x_{-1}\in Hx0​,x−1​∈H, the three-operator forward-reflected-backward scheme (47) is

xk+1=JλA(xk−2λB(xk)+λB(xk−1)−λC(xk))∀k∈N.x_{k+1}=J_{\lambda A}\big(x_k-2\lambda B(x_k)+\lambda B(x_{k-1})-\lambda C(x_k)\big)\qquad\forall k\in\mathbb N.xk+1​=JλA​(xk​−2λB(xk​)+λB(xk−1​)−λC(xk​))∀k∈N.

A sequence (xk)(x_k)(xk​) converges weakly to xˉ\bar xxˉ if ⟨xk,v⟩→⟨xˉ,v⟩\langle x_k,v\rangle\to\langle\bar x,v\rangle⟨xk​,v⟩→⟨xˉ,v⟩ for every v∈Hv\in Hv∈H.

Formalization targets

Goal: Theorem 5.2

If AAA is maximally monotone, BBB is monotone and L1L_1L1​-Lipschitz, CCC is 1L2\tfrac1{L_2}L2​1​-cocoercive, (A+B+C)−1(0)≠∅(A+B+C)^{-1}(0)\ne\varnothing(A+B+C)−1(0)=∅ and

0<λ<24L1+L2,0<\lambda<\frac{2}{4L_1+L_2},0<λ<4L1​+L2​2​,

then every sequence generated by (47) converges weakly to a point of (A+B+C)−1(0)(A+B+C)^{-1}(0)(A+B+C)−1(0).

Milestones

  1. (48), proof of Lemma 5.1: the monotonicity of AAA at xk+1x_{k+1}xk+1​ and at a zero xxx, expanded into six inner-product terms.
  2. Lemma 5.1: for x∈(A+B+C)−1(0)x\in(A+B+C)^{-1}(0)x∈(A+B+C)−1(0) there is ε>0\varepsilon>0ε>0 with
∥xk+1−x∥2+2λ⟨B(xk+1)−B(xk),x−xk+1⟩+(λL1+ε)∥xk+1−xk∥2≤∥xk−x∥2+2λ⟨B(xk)−B(xk−1),x−xk⟩+λL1∥xk−xk−1∥2.\|x_{k+1}-x\|^2+2\lambda\langle B(x_{k+1})-B(x_k),x-x_{k+1}\rangle+(\lambda L_1+\varepsilon)\|x_{k+1}-x_k\|^2\le\|x_k-x\|^2+2\lambda\langle B(x_k)-B(x_{k-1}),x-x_k\rangle+\lambda L_1\|x_k-x_{k-1}\|^2.∥xk+1​−x∥2+2λ⟨B(xk+1​)−B(xk​),x−xk+1​⟩+(λL1​+ε)∥xk+1​−xk​∥2≤∥xk​−x∥2+2λ⟨B(xk​)−B(xk−1​),x−xk​⟩+λL1​∥xk​−xk−1​∥2.
  1. Lower bound (proof of Theorem 5.2): the energy on the left of Lemma 5.1, with ε\varepsilonε removed, is nonnegative.

Significance

The two-operator forward-reflected-backward method applied to AAA and B+CB+CB+C would require λ<1/(2L1+2L2)\lambda<1/(2L_1+2L_2)λ<1/(2L1​+2L2​), since B+CB+CB+C is only known to be (L1+L2)(L_1+L_2)(L1​+L2​)-Lipschitz. Theorem 5.2 shows that using CCC through a plain forward step, without reflection, enlarges the range to λ<1/(2L1+12L2)\lambda<1/(2L_1+\tfrac12L_2)λ<1/(2L1​+21​L2​). In particular, with B=0B=0B=0 the scheme is the forward-backward method and the range is λ<2/L2\lambda<2/L_2λ<2/L2​, the classical one; with C=0C=0C=0 it is the forward-reflected-backward method with its range λ<1/(2L1)\lambda<1/(2L_1)λ<1/(2L1​). The result therefore interpolates between the two methods, with one resolvent, one new evaluation of BBB and one evaluation of CCC per iteration.

The theorem is proved in the paper, partly by reference: the proof says it is "more or less the same as Theorem 2.5" with Lemma 5.1 in place of Lemma 2.4. No machine-checked proof of Theorem 5.2 or of the two-operator Theorem 2.5 is known to exist. A formalization makes explicit the steps the paper leaves to the reader (the Opial-type argument and the identification of weak cluster points as zeros), and the energy inequality of Lemma 5.1 is reusable for rates and inertial variants.

Difficulty

The energy inequality is a careful but elementary computation with inner products. The difficulty lies in passing from it to weak convergence. The energy is not ∥xk−x∥2\|x_k-x\|^2∥xk​−x∥2 but ∥xk−x∥2\|x_k-x\|^2∥xk​−x∥2 plus a cross term in BBB and a step-length term, so Fejér monotonicity of (xk)(x_k)(xk​) with respect to the zero set is not available, and the existence of lim⁡∥xk−x∥\lim\|x_k-x\|lim∥xk​−x∥ for each zero xxx is not immediate from the energy inequality. The identification of weak cluster points as zeros requires that the graph of the maximally monotone operator A+B+CA+B+CA+B+C be sequentially closed in the weak-strong topology, which in turn needs maximal monotonicity of a sum of a maximally monotone operator and a continuous monotone operator. A naive approach that treats B+CB+CB+C as a single Lipschitz operator only reaches the smaller step range and does not prove the theorem.

Formalization scope

All statements live in a real inner product space H (NormedAddCommGroup, InnerProductSpace ℝ H), with CompleteSpace H for the goal. Set-valued operators are H → Set H. The operator vocabulary (monotone, maximally monotone, Lipschitz with a real constant, cocoercive, resolvent family) is the published module ThreeOpSplitting.Accel.MonotoneOperators. Conventions:

  • The resolvent is a hypothesis: a family J : ℝ → H → H with IsResolventFamily A J (for each γ>0\gamma>0γ>0, γ−1(w−Jγw)∈A(Jγw)\gamma^{-1}(w-J_\gamma w)\in A(J_\gamma w)γ−1(w−Jγ​w)∈A(Jγ​w)). For maximally monotone AAA it exists and is unique, so this is not an extra assumption.
  • Indices are shifted by one: Lean's x j is xj−1x_{j-1}xj−1​, and both initial points are arbitrary. The step size is one constant λ\lambdaλ.
  • "1L2\tfrac1{L_2}L2​1​-cocoercive" is IsCocoercive L₂⁻¹ C with L2>0L_2>0L2​>0; the Lipschitz constant satisfies L1≥0L_1\ge0L1​≥0, and L1=0L_1=0L1​=0 is allowed.
  • The zero set is {x:−(B+C)(x)∈A(x)}\{x: -(B+C)(x)\in A(x)\}{x:−(B+C)(x)∈A(x)}, and weak convergence is ⟨xk,v⟩→⟨xˉ,v⟩\langle x_k,v\rangle\to\langle\bar x,v\rangle⟨xk​,v⟩→⟨xˉ,v⟩ for all vvv.

The goal is not trivialized by these choices: the step range is exactly (0,2/(4L1+L2))(0,2/(4L_1+L_2))(0,2/(4L1​+L2​)), not the smaller two-operator range; CCC enters (47) through −λC(xk)-\lambda C(x_k)−λC(xk​) only; and the conclusion is weak convergence to a point of the zero set of A+B+CA+B+CA+B+C, not of A+BA+BA+B. A sorry-free sanity file shows that all hypotheses are jointly satisfiable.

A complete development needs: demiclosedness of maximally monotone graphs, maximal monotonicity of the sum of a maximally monotone and a continuous monotone single-valued operator, and Opial's lemma for weak convergence. These are general and reusable beyond this mission, as is the weak-convergence infrastructure via inner products. Contributions of these lemmas, of proofs of the milestones, and of the goal are welcome.

Selected references

  • Y. Malitsky and M. K. Tam, A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity, SIAM J. Optim. 30(2), 2020; arXiv:1808.04162v4. https://arxiv.org/abs/1808.04162v4
  • H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., Springer, 2017. https://doi.org/10.1007/978-3-319-48311-5
  • P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim. 38(2), 2000. https://doi.org/10.1137/S0363012998338806
  • D. Davis and W. Yin, A three-operator splitting scheme and its optimization applications, Set-Valued Var. Anal. 25, 2017. https://doi.org/10.1007/s11228-017-0421-z
  • P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16(6), 1979. https://doi.org/10.1137/0716071
7 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity 2: For Strongly Monotone A the Forward-Reflected-Backward Method Converges R-Linearly to the Unique ZeroResearch Paper

Motivation

Many problems in optimization, variational inequalities and saddle-point problems reduce to a monotone inclusion: find xxx in a real Hilbert space HHH with

0∈(A+B)(x),0\in (A+B)(x),0∈(A+B)(x),

where AAA is set-valued and maximally monotone and BBB is single-valued and monotone. Splitting methods solve such inclusions by evaluating BBB directly (a forward step) and AAA only through its resolvent (a backward step). The classical forward-backward method needs BBB to be cocoercive; Tseng's forward-backward-forward method removes that requirement at the price of two evaluations of BBB per iteration.

Malitsky and Tam (arXiv:1808.04162, SIAM J. Optim. 30(2), 2020, doi:10.1137/18M1207260) introduced the forward-reflected-backward method, which needs only monotonicity and Lipschitz continuity of BBB and one evaluation of BBB per iteration. Their Theorem 2.5 gives weak convergence (a separate mission of this series). This mission targets their Theorem 2.9: when AAA is strongly monotone, the method converges at a linear rate. Linear rates under strong monotonicity are the standard benchmark against which first-order methods for monotone inclusions are compared, and they decide how the method behaves on regularized saddle-point problems in practice.

Timeline:

  • 1979: Lions and Mercier analyse forward-backward splitting for cocoercive BBB.
  • 2000: Tseng's forward-backward-forward method handles Lipschitz monotone BBB with two forward steps per iteration (doi:10.1137/S0363012998338806).
  • 2015: Malitsky's projected reflected gradient method treats the variational-inequality special case A=NCA=N_CA=NC​ (doi:10.1137/14097238X).
  • 2018–2020: Malitsky and Tam prove weak convergence of the forward-reflected-backward method for general maximally monotone AAA, and R-linear convergence for strongly monotone AAA (Theorem 2.9).

Setting

HHH is a real Hilbert space with inner product ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle⟨⋅,⋅⟩. A set-valued operator A:H⇉HA:H\rightrightarrows HA:H⇉H is monotone if ⟨x−y,u−v⟩≥0\langle x-y,u-v\rangle\ge0⟨x−y,u−v⟩≥0 whenever u∈A(x)u\in A(x)u∈A(x), v∈A(y)v\in A(y)v∈A(y); it is maximally monotone if no monotone operator has a strictly larger graph; it is mmm-strongly monotone if m>0m>0m>0 and ⟨x−y,u−v⟩≥m∥x−y∥2\langle x-y,u-v\rangle\ge m\|x-y\|^2⟨x−y,u−v⟩≥m∥x−y∥2 for all such pairs. The resolvent of AAA with step γ>0\gamma>0γ>0 is JγA=(I+γA)−1J_{\gamma A}=(I+\gamma A)^{-1}JγA​=(I+γA)−1, characterised by γ−1(w−JγAw)∈A(JγAw)\gamma^{-1}(w-J_{\gamma A}w)\in A(J_{\gamma A}w)γ−1(w−JγA​w)∈A(JγA​w); for maximally monotone AAA it is single-valued and defined everywhere. A single-valued B:H→HB:H\to HB:H→H is monotone if ⟨x−y,B(x)−B(y)⟩≥0\langle x-y,B(x)-B(y)\rangle\ge0⟨x−y,B(x)−B(y)⟩≥0 and LLL-Lipschitz if ∥B(x)−B(y)∥≤L∥x−y∥\|B(x)-B(y)\|\le L\|x-y\|∥B(x)−B(y)∥≤L∥x−y∥.

The zero set is (A+B)−1(0)={x:−B(x)∈A(x)}(A+B)^{-1}(0)=\{x: -B(x)\in A(x)\}(A+B)−1(0)={x:−B(x)∈A(x)}. Given a step λ>0\lambda>0λ>0 and two starting points x0,x−1∈Hx_0,x_{-1}\in Hx0​,x−1​∈H, the constant-step forward-reflected-backward method is

xk+1=JλA(xk−2λB(xk)+λB(xk−1))(k∈N).x_{k+1}=J_{\lambda A}\big(x_k-2\lambda B(x_k)+\lambda B(x_{k-1})\big)\qquad(k\in\mathbb N).xk+1​=JλA​(xk​−2λB(xk​)+λB(xk−1​))(k∈N).

For a point xxx the proof uses the two sequences

ak=12∥xk−x∥2,bk=12∥xk−x∥2+2λ⟨B(xk)−B(xk−1),x−xk⟩+12∥xk−xk−1∥2.a_k=\tfrac12\|x_k-x\|^2,\qquad b_k=\tfrac12\|x_k-x\|^2+2\lambda\langle B(x_k)-B(x_{k-1}),x-x_k\rangle+\tfrac12\|x_k-x_{k-1}\|^2 .ak​=21​∥xk​−x∥2,bk​=21​∥xk​−x∥2+2λ⟨B(xk​)−B(xk−1​),x−xk​⟩+21​∥xk​−xk−1​∥2.

Formalization targets

Goal: Theorem 2.9 (p. 8)

Let AAA be maximally monotone and mmm-strongly monotone, BBB monotone and LLL-Lipschitz, (A+B)−1(0)≠∅(A+B)^{-1}(0)\ne\varnothing(A+B)−1(0)=∅, and λ∈(0,12L)\lambda\in(0,\tfrac1{2L})λ∈(0,2L1​). Then (A+B)−1(0)={xˉ}(A+B)^{-1}(0)=\{\bar x\}(A+B)−1(0)={xˉ} and there are q∈(0,1)q\in(0,1)q∈(0,1) and MMM with

∥xk−xˉ∥≤M qkfor all k.\|x_k-\bar x\|\le M\,q^k\qquad\text{for all }k.∥xk​−xˉ∥≤Mqkfor all k.

The rate qqq is left existential, as in the paper's phrase "converges R-linearly"; the explicit rate implied by the proof appears in the milestones.

Milestones (proof of Theorem 2.9, pp. 8–9)

  1. The energy inequality with strong monotonicity:
(1+2mλ)∥xk+1−x∥2+2λ⟨B(xk+1)−B(xk),x−xk+1⟩+(1−λL)∥xk+1−xk∥2≤∥xk−x∥2+2λ⟨B(xk)−B(xk−1),x−xk⟩+12∥xk−xk−1∥2.(1+2m\lambda)\|x_{k+1}-x\|^2+2\lambda\langle B(x_{k+1})-B(x_k),x-x_{k+1}\rangle+(1-\lambda L)\|x_{k+1}-x_k\|^2\le\|x_k-x\|^2+2\lambda\langle B(x_k)-B(x_{k-1}),x-x_k\rangle+\tfrac12\|x_k-x_{k-1}\|^2 .(1+2mλ)∥xk+1​−x∥2+2λ⟨B(xk+1​)−B(xk​),x−xk+1​⟩+(1−λL)∥xk+1​−xk​∥2≤∥xk​−x∥2+2λ⟨B(xk​)−B(xk−1​),x−xk​⟩+21​∥xk​−xk−1​∥2.
  1. (27): with ε=min⁡{12−λL,5mλ}>0\varepsilon=\min\{\tfrac12-\lambda L,5m\lambda\}>0ε=min{21​−λL,5mλ}>0,  (1+4mλ)ak+1+bk+1+ε∥xk+1−xk∥2≤ak+bk\ (1+4m\lambda)a_{k+1}+b_{k+1}+\varepsilon\|x_{k+1}-x_k\|^2\le a_k+b_k (1+4mλ)ak+1​+bk+1​+ε∥xk+1​−xk​∥2≤ak​+bk​.
  2. bk≥0b_k\ge0bk​≥0.
  3. With α=min⁡{1+4mλ−3ε4,1+ε2}>1\alpha=\min\{1+4m\lambda-\tfrac{3\varepsilon}4,1+\tfrac\varepsilon2\}>1α=min{1+4mλ−43ε​,1+2ε​}>1:  α(ak+1+bk+1)≤ak+bk\ \alpha(a_{k+1}+b_{k+1})\le a_k+b_k α(ak+1​+bk+1​)≤ak​+bk​.
  4. ak+1≤ak+1+bk+1≤α−(k+1)(a0+b0)a_{k+1}\le a_{k+1}+b_{k+1}\le\alpha^{-(k+1)}(a_0+b_0)ak+1​≤ak+1​+bk+1​≤α−(k+1)(a0​+b0​).
  5. (A+B)−1(0)(A+B)^{-1}(0)(A+B)−1(0) has at most one point.

Significance

The result. Theorem 2.9 shows that the single-forward-evaluation method keeps the linear rate that the forward-backward method enjoys under cocoercivity, and that Tseng's method enjoys at twice the cost per iteration. The paper also notes that strong monotonicity of BBB instead of AAA reduces to this case by shifting mImImI from BBB to AAA, so the theorem covers strongly monotone saddle-point problems with Lipschitz couplings, for which it gives a geometric bound on the distance to the solution with an explicit contraction factor α−1/2\alpha^{-1/2}α−1/2.

Formalizing it. The theorem is proved in the paper; nothing about it is open. As far as is known it has no machine-checked proof. The mission produces a checked proof of the rate together with the constants ε\varepsilonε and α\alphaα of the paper. One step of the printed derivation, the last inequality of (28), does not hold for every step λ∈(0,12L)\lambda\in(0,\tfrac1{2L})λ∈(0,2L1​) (it needs (λL)2≤18(\lambda L)^2\le\tfrac18(λL)2≤81​). The combined inequality of milestone 4, with the paper's constant α\alphaα, does hold on the whole range, and a formal proof settles this point.

Difficulty

The iteration is not a fixed-point iteration of a contraction in xkx_kxk​ alone: xk+1x_{k+1}xk+1​ depends on xkx_kxk​ and xk−1x_{k-1}xk−1​, and the natural Lyapunov quantity bkb_kbk​ contains the cross term 2λ⟨B(xk)−B(xk−1),x−xk⟩2\lambda\langle B(x_k)-B(x_{k-1}),x-x_k\rangle2λ⟨B(xk​)−B(xk−1​),x−xk​⟩, which has no sign. The obvious argument, bounding ∥xk+1−x∥\|x_{k+1}-x\|∥xk+1​−x∥ by a multiple of ∥xk−x∥\|x_k-x\|∥xk​−x∥, fails because the reflected term λB(xk−1)\lambda B(x_{k-1})λB(xk−1​) couples consecutive steps; the contraction holds only for a combined energy, and only after showing that energy is nonnegative. The constants must be balanced so that the gain 4mλ4m\lambda4mλ from strong monotonicity outweighs what is spent controlling the cross term, uniformly in λ\lambdaλ up to 12L\tfrac1{2L}2L1​.

Formalization scope

  • HHH is a type with [NormedAddCommGroup H] [InnerProductSpace ℝ H], plus [CompleteSpace H] in the goal. Operators are A : H → Set H and B : H → H. Monotonicity, strong monotonicity, maximal monotonicity, Lipschitz continuity and resolvents come from the published definition module ThreeOpSplitting.Accel.MonotoneOperators. Strong monotonicity sits on AAA, with 0<m0<m0<m a separate hypothesis; BBB is only monotone.
  • The resolvent is a hypothesis, not a construction: the method is driven by a family J : ℝ → H → H with J γ a resolvent of AAA for every γ>0\gamma>0γ>0. For maximally monotone AAA such a family exists and is unique.
  • Indices are shifted by one: Lean's x j is the paper's xj−1x_{j-1}xj−1​, so x 0 is x−1x_{-1}x−1​ and x 1 is x0x_0x0​. The starting points are arbitrary. The energies aSeq, bSeq follow the same shift.
  • L>0L>0L>0 is pinned, because the step range (0,12L)(0,\tfrac1{2L})(0,2L1​) divides by LLL.
  • "R-linear convergence" is stated as an explicit geometric bound ∥xk−xˉ∥≤Mqk\|x_k-\bar x\|\le Mq^k∥xk​−xˉ∥≤Mqk with a fixed q∈(0,1)q\in(0,1)q∈(0,1), and uniqueness of the zero is part of the conclusion, not a hypothesis. A statement with plain norm convergence, a rate depending on kkk, a hypothesis that the zero is unique, or strong monotonicity on BBB or on A+BA+BA+B instead of AAA is not the theorem; neither is a variable-step run.
  • The milestones drop maximality of AAA and completeness of HHH where the step does not use them, and milestones 3 and 6 are stated with fewer hypotheses than in the proof; each is a stronger statement.
  • No infrastructure beyond Mathlib and the published operator module is needed. Proofs of the milestones, alternative proofs of the goal and sharper rates are all useful contributions.

Selected references

  • Y. Malitsky, M. K. Tam, A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity, SIAM J. Optim. 30(2), 2020. arXiv:1808.04162v4. https://arxiv.org/abs/1808.04162, https://doi.org/10.1137/18M1207260
  • P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim. 38(2), 2000. https://doi.org/10.1137/S0363012998338806
  • P.-L. Lions, B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16(6), 1979. https://doi.org/10.1137/0716071
  • Y. Malitsky, Projected reflected gradient methods for monotone variational inequalities, SIAM J. Optim. 25(1), 2015. https://doi.org/10.1137/14097238X
  • H. H. Bauschke, P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed., Springer, 2017. https://doi.org/10.1007/978-3-319-48311-5
10 thms2 active usersReviewed
PreviousPage 3 of 10Next

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