Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in

Get started

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

Functional Analysis

233 missions · 145 completed

Missions

Open88Completed145All233
Probability·Captain: mikedeng1

Markov Processes: Characterization and Convergence 17: Nonlocal jump and Lévy generatorsTextbook

Why nonlocal generators matter

Markov processes with jumps model changes that cannot be represented by continuous diffusion paths: arrivals in queueing systems, sudden failures, population events, and discontinuous changes in financial or physical systems. Their infinitesimal descriptions are nonlocal generators, because the value of the operator at a state depends on test-function values at displaced states rather than only on derivatives at the current point. Chapter 8, Section 3 of Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence (Wiley, 1986), treats three complementary regimes. Theorem 3.1 covers finite-rate jumps on a general locally compact state space. Theorem 3.4 treats homogeneous Lévy operators on Euclidean space, including infinite jump activity and degenerate covariance. Theorem 3.3 gives the main target here: well-posedness for a time- and state-dependent compensated Lévy-type martingale problem.

These results connect concrete jump kernels and integro-differential operators to two standard descriptions of stochastic dynamics. Autonomous operators are realized as generators of conservative Feller semigroups, while time-dependent operators are characterized through martingale identities. Keeping all three source results in one mission records the nonlocal-generator theme without claiming that their distinct hypotheses imply one another.

The setting

For the Euclidean results, the state space is Rd\mathbb R^dRd, represented in Lean as EuclideanSpace ℝ (Fin d), with d>0d>0d>0. A covariance field a(t,x)a(t,x)a(t,x) is a continuous linear endomorphism, a drift field b(t,x)b(t,x)b(t,x) is a vector, and ν(t,x,dy)\nu(t,x,dy)ν(t,x,dy) is a measure of jump displacements. For a smooth compactly supported test function fff, the compensated Lévy-type operator is

Ltf(x)=12∑i,jaij(t,x) ∂ijf(x)+Df(x)[b(t,x)]+∫ ⁣(f(x+y)−f(x)−Df(x)[y]1+∥y∥2)ν(t,x,dy).L_t f(x)=\frac12\sum_{i,j}a_{ij}(t,x)\,\partial_{ij}f(x) +Df(x)[b(t,x)] +\int\!\left(f(x+y)-f(x)-\frac{Df(x)[y]}{1+\lVert y\rVert^2}\right)\nu(t,x,dy).Lt​f(x)=21​i,j∑​aij​(t,x)∂ij​f(x)+Df(x)[b(t,x)]+∫(f(x+y)−f(x)−1+∥y∥2Df(x)[y]​)ν(t,x,dy).

The denominator in the compensation term is part of the source convention. The covariance factor 1/21/21/2 applies only to the second-order term; the drift is unscaled. The weighted moment ∥y∥2/(1+∥y∥2)\lVert y\rVert^2/(1+\lVert y\rVert^2)∥y∥2/(1+∥y∥2) permits measures with infinite total mass while controlling the compensated integral.

A solution of the Lévy-type martingale problem is a jointly measurable process with the prescribed initial pushforward law whose integrated-generator increments have zero expectation against every bounded continuous function of any finite history. Smooth compactly supported functions are the spatial tests. This definition imposes no path-continuity requirement.

The finite-rate model uses a locally compact, noncompact, separable metric space EEE, a nonnegative rate λ(x)\lambda(x)λ(x), and a weakly continuous probability transition kernel μ(x,dy)\mu(x,dy)μ(x,dy). Its operator is Af(x)=λ(x)∫(f(y)−f(x))μ(x,dy)Af(x)=\lambda(x)\int(f(y)-f(x))\mu(x,dy)Af(x)=λ(x)∫(f(y)−f(x))μ(x,dy). Positive weights γ\gammaγ and η\etaη specify the graph domain and control behavior at infinity.

Formalization targets

Goal: nonautonomous Lévy-type well-posedness

The main target is Chapter 8, Section 3, Theorem 3.3. The covariance is continuous, symmetric, bounded, and strictly positive definite at every nonzero vector, without a uniform ellipticity constant. The drift is measurable and bounded. The weighted jump measure is integrable, and for every measurable set its weighted mass is a bounded continuous function of time and state.

For every initial probability measure, the conclusion asserts existence of a measurable-process solution on some probability space and uniqueness of all finite-dimensional distributions among every solution on every probability space. Setwise continuity is retained exactly; it is not replaced by weak convergence of measures or by finite total jump intensity.

Related target: homogeneous Lévy generation

Theorem 3.4 freezes the coefficients in time and space. The covariance may be degenerate but is symmetric and nonnegative, and the jump measure needs only the finite weighted integral. The full C^2\widehat C^2C2 graph consists of functions, first derivatives, and second derivatives that vanish at infinity. Its closure is the exact generator of a positive conservative strongly continuous contraction semigroup on C0(Rd)C_0(\mathbb R^d)C0​(Rd), and smooth compactly supported functions form a core.

Related target: finite-rate jump generation

Theorem 3.1 retains the general-state-space jump model. The transition kernel is both setwise measurable and weakly continuous; the rate and weights satisfy the source's vanishing and signed integral bounds. The weighted graph closes to a single-valued conservative Feller generator, and compactly supported continuous functions form a core.

Significance

The main theorem says that the displayed nonlocal characteristics determine stochastic dynamics in distribution even when the drift is only measurable and jump activity need not be finite. The two autonomous theorems identify concrete domains whose closures are genuine Feller generators, including positivity, contraction, strong continuity, conservativity, and core statements. Together they distinguish finite-rate kernels, homogeneous compensated Lévy dynamics, and nonautonomous Lévy-type dynamics while sharing the same generator language.

The formal contribution is a machine-checkable statement layer, not a proof claim. It exposes the exact compensation, weighted-integrability, graph-domain, semigroup, and finite-history conventions on which later proofs depend. The common diffusion operator, bounded-pointwise closure, and strongly continuous contraction-semigroup predicate are reused from earlier private missions in the same textbook series rather than duplicated under conflicting identifiers.

Where the difficulty lies

The obvious finite-jump approximation does not by itself preserve the full conclusions. Infinite jump activity requires compensation near zero, and convergence of the associated operators must still identify the intended martingale problem or the exact closed Feller generator. In the nonautonomous theorem, setwise continuity of weighted jump masses must coexist with merely measurable drift, while uniqueness ranges over arbitrary probability-space realizations and all finite-dimensional laws. Strengthening to continuous drift, imposing finite total jump intensity, assuming uniform ellipticity, or comparing only continuous-path solutions would materially weaken or alter the source theorem.

Formalization scope and conventions

Nonnegative real time is represented by ℝ≥0; Euclidean coordinates use Fin d. Fréchet derivatives express both gradient and Hessian terms. The jump measure is a measure of displacements yyy, so the operator evaluates f(x+y)f(x+y)f(x+y). Integrable hypotheses prevent Lean's totalized integral from silently assigning zero to a divergent positive weighted moment. Positive dimension is explicit through [NeZero d].

The martingale predicate includes empty finite histories and repeated observation times. Its bounded continuous history tests determine the same finite-dimensional identities used by the source, and no sample-path regularity is inserted. The autonomous graphs live in C0×C0C_0\times C_0C0​×C0​; bounded-pointwise closure means closure under uniformly bounded pointwise sequential limits, not ordinary norm closure. The finite-rate theorem preserves its restriction of the additional integrability clause to states with positive rate. No vacuous solution predicate, unweighted moment assumption, hidden nonzero-rate condition, or proof-only theorem dependency is introduced.

Selected references

  • Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence, Wiley, 1986, Chapter 8, Section 3, Theorems 3.1, 3.3, and 3.4. Wiley DOI
  • Stewart N. Ethier and Thomas G. Kurtz, same volume, Chapter 4, Sections 2–3 for Feller and martingale-problem conventions, and Appendix 3 for bounded-pointwise closure. Wiley DOI
12 thms1 active userReviewed
Probability·Captain: mikedeng1

Markov Processes: Characterization and Convergence 16: Degenerate diffusion on a simplexTextbook

Why simplex diffusions matter

Finite-dimensional simplices are the natural state spaces for proportions: allele frequencies, population shares, and other collections of nonnegative coordinates whose total cannot exceed one. A diffusion on such a space must do more than solve an unconstrained stochastic equation. Its covariance degenerates on the boundary, and its drift must respect every face so that the process remains in the simplex. Chapter 8 of Ethier and Kurtz develops generator results for this setting as part of the analytic foundation for Markov-process models with constrained state spaces Ethier and Kurtz, Chapter 8, §2.

This mission formalizes their Theorem 2.8, a known generation theorem rather than an open conjecture. The theorem treats arbitrary Lipschitz drift satisfying the inward boundary inequalities. It identifies the closed diffusion graph as a Feller generator and also states that polynomial restrictions form a core. The generality of the drift distinguishes this result from later population-model applications with particular mutation or selection coefficients.

The simplex and its boundary

For a positive integer ddd, the simplex state space is

Kd={x∈Rd:xi≥0 for every i,∑i=1dxi≤1}.K_d=\left\{x\in\mathbb R^d: x_i\ge 0\ \text{for every }i, \quad \sum_{i=1}^d x_i\le 1\right\}.Kd​={x∈Rd:xi​≥0 for every i,i=1∑d​xi​≤1}.

The missing mass 1−∑ixi1-\sum_i x_i1−∑i​xi​ may be viewed as an additional coordinate. In Lean, WFState d is the subtype of functions Fin d → ℝ satisfying precisely nonnegativity and the upper bound on the coordinate sum. These conditions already imply xi≤1x_i\le 1xi​≤1 for every coordinate.

Let b:Kd→Rdb:K_d\to\mathbb R^db:Kd​→Rd be the drift. The boundary conditions say that bi(x)≥0b_i(x)\ge 0bi​(x)≥0 whenever xi=0x_i=0xi​=0, while ∑ibi(x)≤0\sum_i b_i(x)\le 0∑i​bi​(x)≤0 whenever ∑ixi=1\sum_i x_i=1∑i​xi​=1. Thus the drift cannot point outward through a coordinate face or through the top face. No mutation–selection formula or extra smoothness condition is imposed: global Lipschitz continuity and these face inequalities are the complete drift hypotheses retained here.

The operator and target theorem

The covariance matrix is

aij(x)=xi(δij−xj),a_{ij}(x)=x_i(\delta_{ij}-x_j),aij​(x)=xi​(δij​−xj​),

and the associated simplex diffusion operator is

Gf(x)=12∑i,jxi(δij−xj) ∂i∂jf(x)+∑ibi(x) ∂if(x).Gf(x)=\frac12\sum_{i,j}x_i(\delta_{ij}-x_j) \,\partial_i\partial_j f(x)+\sum_i b_i(x)\,\partial_i f(x).Gf(x)=21​i,j∑​xi​(δij​−xj​)∂i​∂j​f(x)+i∑​bi​(x)∂i​f(x).

Only the second-order sum is multiplied by 1/21/21/2. The covariance becomes singular on boundary faces, so this is not an immediate instance of a uniformly elliptic whole-space theorem.

The formal target asserts that the uniform graph closure of

{(f,Gf):f∈C2(Kd)}\{(f,Gf):f\in C^2(K_d)\}{(f,Gf):f∈C2(Kd​)}

is single-valued and is exactly the generator graph of a positive, conservative, strongly continuous contraction semigroup on C(Kd)C(K_d)C(Kd​). Conservativity is expressed by preservation of the constant function 111. The generator is identified by the right derivative at time zero, not merely by containment of a convenient operator restriction.

The final clause says that polynomials restricted to KdK_dKd​ are a core: closing the graph obtained from polynomial first coordinates gives the same full generator graph. This is a graph-closure statement and is stronger than uniform density of polynomials as functions.

What the result provides

Single-valuedness shows that the closed graph behaves as an operator rather than a multivalued relation. Generation supplies a Feller semigroup whose positivity and preservation of constants give the Markov interpretation. The exact generator biconditional fixes the full infinitesimal domain, while the polynomial-core conclusion permits generator questions to be reduced to algebraically structured test functions without changing the closed operator.

The source theorem is already proved in the book. The formalization task is to recover its generator statement and core conclusion in Lean with all boundary, closure, and semigroup conventions explicit. The current mission contributes a source-reviewed statement and its expression-level definitions; it does not claim a completed Lean proof.

Why the formalization is delicate

The obvious route through standard elliptic diffusion generation does not apply because a(x)a(x)a(x) degenerates as coordinates approach the boundary. It is also insufficient to prove only that the displayed differential operator is contained in some generator: the theorem identifies the closure of the entire C2(Kd)C^2(K_d)C2(Kd​) graph and separately asserts the polynomial core.

Boundary semantics create another source of possible weakening. Dropping either inward condition would permit outward drift at a face. Replacing the arbitrary Lipschitz drift by a special population-genetics formula would narrow the theorem. Replacing graph equality by inclusion, or polynomial graph density by ordinary function density, would lose a stated conclusion. These distinctions are all preserved in the target.

Formalization scope

The Lean development uses the book-wide namespace EthierKurtz. The compact space C(Kd)C(K_d)C(Kd​) is represented by real-valued bounded continuous functions on WFState d; compactness makes this the intended continuous-function space with the uniform norm. A C2(Kd)C^2(K_d)C2(Kd​) function is represented through a globally twice continuously differentiable extension on the ambient finite-coordinate space, following the book’s Appendix 6 extension convention for closed convex sets.

The operator uses Fréchet derivatives evaluated on coordinate vectors, which represent the first and second partial derivatives in the finite-dimensional ambient space. The graph is closed in the product uniform norm. IsStronglyContinuousContractionSemigroup records identity at zero, the nonnegative-time semigroup law, contraction, and strong right continuity at zero. The target additionally records positivity, preservation of one, and equality between its derivative graph and the closed diffusion graph.

The scope excludes the zero-dimensional case, as required by 0 < d. It does not introduce a continuous-path hypothesis, a special drift parameterization, or uniform ellipticity. The only packaged declarations beyond the goal are the state space, operator, graph, and the already published semigroup predicate needed to state it. Proof-only lemmas and unrelated Chapter 8 results are outside this mission.

Selected references

  • Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence, Wiley, 1986, Chapter 8, §2, Theorem 2.8, printed p. 375; equation (1.15), printed p. 368; Appendix 6, printed pp. 499–500. DOI
5 thms1 active userReviewed
Probability·Captain: mikedeng1

Markov Processes: Characterization and Convergence 14: One-dimensional boundary classificationTextbook

Why endpoint classification matters

A one-dimensional diffusion is governed in the interior by a second-order differential operator, but the interior coefficients alone do not determine what happens when the process approaches the edge of its state space. An endpoint may be reachable from the interior or inaccessible; after arrival it may absorb, reflect, or retain the process according to a boundary parameter. The same issue persists when an endpoint is infinite. Chapter 8 of Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence (Wiley, 1986), organizes these alternatives through scale and speed integrals and identifies the exact operator domain that generates the corresponding Feller evolution. This mission formalizes Chapter 8, Section 1, Theorem 1.1, printed page 367.

The setting

Let −∞≤r0<r1≤∞-\infty\le r_0<r_1\le\infty−∞≤r0​<r1​≤∞. The real state interval is I=[r0,r1]∩RI=[r_0,r_1]\cap\mathbb RI=[r0​,r1​]∩R, its interior is I∘=(r0,r1)I^\circ=(r_0,r_1)I∘=(r0​,r1​), and Iˉ\bar IIˉ is the closed interval in the extended real line. A function in C(Iˉ)C(\bar I)C(Iˉ) is represented by a continuous function on that compact extended interval, so finite endpoint limits are part of the object even when an endpoint is infinite.

The interior diffusion operator is

Gf(x)=a(x)2f′′(x)+b(x)f′(x),Gf(x)=\frac{a(x)}2 f''(x)+b(x)f'(x),Gf(x)=2a(x)​f′′(x)+b(x)f′(x),

where aaa and bbb are continuous on I∘I^\circI∘ and a(x)>0a(x)>0a(x)>0 there. Choose an interior reference point rrr. Define

B(x)=∫rx2b(y)a(y) dy,p(x)=∫rxe−B(y) dy,m(x)=∫rx2eB(y)a(y) dy.B(x)=\int_r^x \frac{2b(y)}{a(y)}\,dy, \qquad p(x)=\int_r^x e^{-B(y)}\,dy, \qquad m(x)=\int_r^x \frac{2e^{B(y)}}{a(y)}\,dy.B(x)=∫rx​a(y)2b(y)​dy,p(x)=∫rx​e−B(y)dy,m(x)=∫rx​a(y)2eB(y)​dy.

The corresponding endpoint tests uuu and vvv are nonnegative extended-real integrals. Their values may be +∞+\infty+∞; preserving that possibility is essential because the four boundary classes are distinguished precisely by which of the two tests are finite.

Formalization target

Theorem 1.1 — one-dimensional boundary diffusion generation

At either endpoint, the pair (u,v)(u,v)(u,v) gives the Feller boundary class:

classuvregular<∞<∞exit<∞=∞entrance=∞<∞natural=∞=∞.\begin{array}{c|cc} \text{class} & u & v\\ \hline \text{regular} & <\infty & <\infty\\ \text{exit} & <\infty & =\infty\\ \text{entrance} & =\infty & <\infty\\ \text{natural} & =\infty & =\infty. \end{array}classregularexitentrancenatural​u<∞<∞=∞=∞​v<∞=∞<∞=∞.​​

Entrance and natural endpoints are inaccessible, so the generator domain imposes no boundary equation there. At an exit endpoint the limiting generator value must be zero. At a regular endpoint rir_iri​, a parameter qi∈[0,1]q_i\in[0,1]qi​∈[0,1] determines the boundary condition

qilim⁡x→riGf(x)=(−1)i(1−qi)lim⁡x→rieB(x)f′(x).q_i\lim_{x\to r_i}Gf(x) =(-1)^i(1-q_i)\lim_{x\to r_i}e^{B(x)}f'(x).qi​x→ri​lim​Gf(x)=(−1)i(1−qi​)x→ri​lim​eB(x)f′(x).

The target states that the graph consisting of f∈C(Iˉ)f\in C(\bar I)f∈C(Iˉ) that are twice continuously differentiable in the interior, whose GfGfGf extends continuously to Iˉ\bar IIˉ, and that satisfy the applicable condition at both endpoints is exactly the infinitesimal generator of a Feller semigroup on C(Iˉ)C(\bar I)C(Iˉ). The conclusion includes the semigroup law, contraction, strong right continuity at zero, positivity, preservation of the constant function 111, and a biconditional identifying the complete generator graph rather than merely an included core or its closure.

Significance

The theorem translates local coefficients into a global Markov evolution while retaining every possible finite or infinite endpoint type. The endpoint tests determine which boundary behavior is available, and the regular-boundary parameter records absorbing, reflecting, and intermediate behavior in one equation. Without the classification, writing down the differential expression does not specify a unique Feller generator because distinct domains can encode different stochastic behavior at the same endpoint.

The formal contribution is a machine-checkable statement layer for the source theorem. It makes the compactified state space, improper endpoint integrals, one-sided endpoint filters, and exact generator graph explicit. The theorem itself remains an open proof obligation in this statement-only mission. The definitions can also support later formal work on hitting distributions, killed or reflected diffusions, and comparison of boundary regimes.

Where the difficulty lies

The main difficulty is that the classification cannot be reduced to ordinary finite integrals or to boundary values at finite real points. Infinite endpoints and divergent scale or speed tests carry mathematical information; replacing extended-real integrals by totalized real integrals would collapse boundary classes. A second difficulty is identifying the full closed generator domain. Showing that the differential expression is meaningful on smooth interior functions is insufficient: the proof must connect its endpoint asymptotics to positivity, conservativity, strong continuity, and exact generation on the uniform-norm space.

Formalization scope and conventions

Endpoints use EReal, and the state space is Set.Icc r₀ r₁ in the extended line. Coefficients are constrained only on the open real interior; no boundedness or uniform ellipticity is added. The drift primitive and scale/speed tests use oriented interval integrals internally and ENNReal endpoint integrals externally, retaining +∞+\infty+∞. Absolute values correct the orientation on the left of the reference point.

The graph stores continuous endpoint extensions of both fff and GfGfGf. Interior C2C^2C2 regularity is expressed by ContDiffOn ℝ 2, and endpoint limits use the one-sided neighborhood filter induced from the extended interval. The regular parameter is required to lie in [0,1][0,1][0,1] only when both boundary tests are finite. The mission does not replace the four cases by an opaque classifier, assume finite endpoints, add a pathwise stochastic differential equation, or weaken exact generation to graph inclusion. The shared book definition of a strongly continuous contraction semigroup is reused from the earlier semigroup-generation mission rather than redeclared.

Selected references

  • Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence, Wiley, 1986, Chapter 8, Section 1, Theorem 1.1 and equations (1.1)–(1.11), printed pp. 366–367. Wiley DOI
  • Stewart N. Ethier and Thomas G. Kurtz, same volume, Chapter 4, printed p. 166, for the Feller semigroup convention used in the conclusion. Wiley DOI
5 thms1 active userReviewed
Probability·Captain: mikedeng1

Markov Processes: Characterization and Convergence 13: Whole-space diffusion generatorsTextbook

Why whole-space diffusion generators matter

Diffusion processes connect stochastic differential equations, partial differential equations, and Markov semigroups. On Euclidean space, their local behavior is encoded by a second-order operator built from a covariance field and a drift field. A central question is whether those local coefficients determine an actual Markov evolution, and whether the resulting evolution is unique. Ethier and Kurtz organize these questions through generator graphs and martingale problems, which allow the same language to cover smooth elliptic diffusions, degenerate models, and coefficients that vary measurably with time. This mission formalizes three complementary whole-space regimes from Chapter 8 of Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence (Wiley, 1986), principally Theorems 1.6, 1.7, and 2.5.

The setting

The state space is the finite-dimensional Euclidean space Rd\mathbb R^dRd, represented in Lean as EuclideanSpace ℝ (Fin d), with d>0d>0d>0. A covariance operator a(t,x)a(t,x)a(t,x) is a continuous linear endomorphism of this space, while a drift b(t,x)b(t,x)b(t,x) is a vector. For a smooth scalar test function fff, the diffusion operator is

Gtf(x)=12∑i,jaij(t,x) ∂ijf(x)+Df(x)[b(t,x)].G_t f(x)=\frac12\sum_{i,j} a_{ij}(t,x)\,\partial_{ij}f(x) + Df(x)[b(t,x)].Gt​f(x)=21​i,j∑​aij​(t,x)∂ij​f(x)+Df(x)[b(t,x)].

The factor 1/21/21/2 multiplies only the covariance-weighted second-order term. The formalization uses Fréchet derivatives evaluated in the standard coordinate directions. In the time-homogeneous cases, the smooth compactly supported graph consists of pairs (f,Gf)(f,Gf)(f,Gf) viewed in C0(Rd)×C0(Rd)C_0(\mathbb R^d)\times C_0(\mathbb R^d)C0​(Rd)×C0​(Rd), and its uniform closure is the candidate generator.

For time-dependent coefficients, a measurable process solves the time-inhomogeneous martingale problem when its initial pushforward law is prescribed and the integrated generator identity holds against every smooth compactly supported spatial test and every bounded continuous finite-history test. This formulation records the natural-past moment identities without imposing continuity of sample paths as an extra hypothesis.

Formalization targets

Goal: measurable-drift nonautonomous well-posedness

The main target is Chapter 8, Section 1, Theorem 1.7. The covariance and drift are jointly Borel measurable and locally bounded. The covariance is symmetric and nonnegative. At each fixed spatial point it is uniformly elliptic over every bounded positive time interval, and its spatial continuity is uniform over that interval. A common quadratic bound controls the covariance norm and the one-sided radial drift quantity ⟨x,b(t,x)⟩\langle x,b(t,x)\rangle⟨x,b(t,x)⟩.

For every initial probability measure, the conclusion asserts existence of a measurable-process solution on some probability space and uniqueness of all finite-dimensional distributions among every such solution on any probability space. The drift is not assumed continuous, and no stronger norm-growth condition on the drift or moment condition on the initial law is inserted.

Related target: uniformly elliptic Feller generation

Chapter 8, Section 1, Theorem 1.6 treats bounded Hölder continuous time-homogeneous coefficients with symmetric, globally uniformly elliptic covariance. It concludes that the closure of the smooth compactly supported graph is single-valued and is exactly the generator of a positive, strongly continuous contraction semigroup on C0(Rd)C_0(\mathbb R^d)C0​(Rd). Conservativity is retained through membership of the constant graph pair (1,0)(1,0)(1,0) in the bounded-pointwise closure.

Related target: degenerate smooth-core generation

Chapter 8, Section 2, Theorem 2.5 permits degenerate and unbounded covariance fields. Its assumptions are symmetry, nonnegativity, twice continuous differentiability of the matrix entries, bounded second partial derivatives, and a globally Lipschitz drift. Its conclusion is the same full Feller generation and conservativity statement. This regime is related to, but not implied by, the bounded uniformly elliptic regime.

Significance

Together the three statements separate distinct mechanisms for obtaining Markov dynamics from local diffusion data. The two autonomous theorems identify when a concrete smooth core closes to a Feller generator, including positivity, contraction, strong continuity, and conservativity. The nonautonomous theorem establishes existence and uniqueness in distribution under substantially rougher temporal behavior and merely measurable drift. Keeping the regimes together exposes the common operator while preserving their incompatible regularity hypotheses.

The formal contribution is a machine-checkable statement layer for these source results and their expression-essential definitions. It does not claim proofs of the theorems. The definitions make explicit the coordinate form of the generator, the C0C_0C0​ graph, the bounded-pointwise closure convention, and the complete finite-history martingale identities. These components can support later formal proofs and other diffusion or martingale-problem developments.

Where the difficulty lies

The source conclusions are not consequences of a single elementary continuity argument. In the Feller cases, identifying the closure of a graph with the generator requires simultaneous control of the operator domain, the semigroup properties, positivity, and conservativity. In the time-dependent case, measurability of the drift is deliberately weaker than continuity, while uniqueness must cover all measurable-process realizations and all finite collections of observation times. Replacing that conclusion by uniqueness only among continuous processes, or strengthening the drift hypotheses until a standard smooth theory applies, would change the theorem.

Formalization scope and conventions

The development uses nonnegative real time and finite-dimensional real Euclidean space. Covariance matrices act as continuous linear maps; their entries are recovered in the standard orthonormal basis. Smoothness is expressed with ContDiff, compact support with HasCompactSupport, and autonomous generator graphs in C₀. The bounded-pointwise closure is the smallest set closed under uniformly bounded pointwise sequential limits, not merely the set of one-step limits.

The martingale-problem predicate requires joint measurability of the process, equality of the initial pushforward measure, and all bounded continuous finite-history identities. Empty histories and repeated observation times are included. The goal compares the complete finite-dimensional laws of any two solutions. No vacuous solution predicate, arbitrary extension of the generator, chosen matrix square root, hidden path-continuity assumption, or proof-only theorem dependency is used.

Selected references

  • Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence, Wiley, 1986, Chapter 8, Theorems 1.6, 1.7, and 2.5. Wiley DOI
  • Stewart N. Ethier and Thomas G. Kurtz, same volume, Chapter 4 for martingale-problem well-posedness and Feller conventions, and Appendix 3 for bounded-pointwise closure. Wiley DOI
7 thms1 active userReviewed
Probability·Captain: mikedeng1

Markov Processes: Characterization and Convergence 01: Contraction semigroup generationTextbook

Motivation

Continuous-time Markov processes are often studied through operators that describe how observables evolve. The generation question asks when an operator specified on a domain actually determines a strongly continuous family of contractions. Ethier and Kurtz place this question at the start of Markov Processes: Characterization and Convergence because the resulting semigroup language supports their later treatment of processes and convergence. This mission records the full generation characterization in Chapter 1, Theorem 2.6, and retains the related perturbation result in Theorem 7.1.

Setting

Let (E) be a real Banach space. A linear operator (A) has a linear domain (D(A)\subseteq E), which need not equal (E). A family (T(t)), for nonnegative real (t), consists of bounded linear maps (E\to E). It is a strongly continuous contraction semigroup when (T(0)) is the identity, (T(s+t)=T(s)T(t)), every (T(t)) has norm at most one, and (T(t)x\to x) as (t\downarrow0) for every (x\in E). Its infinitesimal generator has exactly those (x) for which the right-hand difference quotient (t^{-1}(T(t)x-x)) converges, and sends each such (x) to the limit.

An operator is dissipative here when

r∥x∥≤∥rx−Ax∥(x∈D(A), r>0).r\lVert x\rVert\leq\lVert rx-Ax\rVert \quad(x\in D(A),\ r>0).r∥x∥≤∥rx−Ax∥(x∈D(A), r>0).

The range condition for a positive (r) says every vector in (E) is (rx-Ax) for some (x\in D(A)). Density means that vectors in (D(A)) approximate every vector in (E). These are independent requirements in the formal statement; neither the domain nor the operator is assumed closed or bounded.

For the related perturbation theorem, (A) and (B) may have different domains. Their sum uses the intersection of those domains. Closure is closure of the graph in (E\times E). A graph closure is required to be the graph of a single-valued operator before it can be called a generator.

Formalization targets

Theorem 2.6: generation characterization

The goal is the equivalence

A generates a strongly continuous contraction semigroup⟺D(A)‾=E,A is dissipative,Ran⁡(rI−A)=E for some r>0.A\text{ generates a strongly continuous contraction semigroup} \quad\Longleftrightarrow\quad \overline{D(A)}=E,\quad A\text{ is dissipative},\quad \operatorname{Ran}(rI-A)=E\text{ for some }r>0.A generates a strongly continuous contraction semigroup⟺D(A)​=E,A is dissipative,Ran(rI−A)=E for some r>0.

The left side uses the full infinitesimal-generator domain, rather than agreement with a generator only on a smaller subdomain. The right side includes dissipativity for every positive parameter and full surjectivity for at least one positive parameter.

Theorem 7.1: relatively bounded perturbation

The retained related result assumes that the closure of (A) is single-valued and generates a strongly continuous contraction semigroup, (D(A)\subseteq D(B)), and (B) is dissipative. It further assumes

∥Bx∥≤α∥Ax∥+β∥x∥(x∈D(A)),0≤α<1,β≥0.\lVert Bx\rVert\leq\alpha\lVert Ax\rVert+\beta\lVert x\rVert \quad(x\in D(A)),\qquad 0\leq\alpha<1,\quad\beta\geq0.∥Bx∥≤α∥Ax∥+β∥x∥(x∈D(A)),0≤α<1,β≥0.

It concludes that the closure of (A+B) is single-valued and generates such a semigroup, and that its entire graph equals the sum of the graph closures of (A) and (B). This theorem is a related generation variant within the same mission, not a separate main goal.

Significance

The equivalence turns an existence question about a family of operators into conditions on a single potentially unbounded operator. In particular, it preserves the exact-domain requirement: proving only that a semigroup generator extends (A) would answer a weaker question. The perturbation theorem then identifies circumstances under which an already generating operator remains useful after adding a dissipative term that need not itself be bounded.

The textbook proves both statements. The Lean files supplied here are statements with intentional proof holes; they do not claim machine-checked proofs. A completed formalization would supply proofs of these source results while keeping the domain, range, closure, and relative-bound conditions shown in the statements.

Difficulty

The hypotheses describe a linear map on only part of the Banach space, while the conclusion requires bounded operators on all of (E) at every nonnegative time. Checking a semigroup law on a convenient subspace is insufficient unless the resulting operators and generator have the stated full domains. For perturbations, graph closure can enlarge a domain. An equality of formulas on (D(A)) alone would therefore omit the theorem's graph and domain conclusion.

Formalization scope

Lean uses NormedAddCommGroup E, NormedSpace ℝ E, and CompleteSpace E for the real Banach space; Submodule ℝ E for each domain; D →ₗ[ℝ] E for an operator that need not be bounded; and E →L[ℝ] E for each semigroup operator. Semigroup values at negative real times are unconstrained. The derivative is the right limit through positive times. Graph closure is topological closure in the ambient product, and graph sum requires a common input. The strict relative bound (\alpha<1) and positive resolvent parameter remain explicit.

The reusable definitions are the semigroup predicate, full generator predicate, operator graph, and graph sum. The mission welcomes proofs of the two stated theorems and genuinely source-based supporting lemmas. A model with an empty operator domain, an operator restricted from a larger generator, or a conclusion that drops the graph equality would not satisfy the target.

Selected references

  • Stewart N. Ethier and Thomas G. Kurtz, Markov Processes: Characterization and Convergence, Wiley, 1986, Chapter 1, Sections 2 and 7, Theorems 2.6 and 7.1. Book record.
6 thms1 active userReviewed
🏆Completed
Convex OptimizationOptimization·Captain: Shuze Chen

Vector Space Methods IV: Hahn–Banach and Minimum Norm DualityTextbook

Motivation

Chapter 5 of Luenberger's Optimization by Vector Space Methods (Wiley, 1969) carries the minimum norm theory of Chapter 3 (Mission I of this series) from Hilbert space to arbitrary real normed spaces. The inner product is gone, so orthogonal projection is no longer available; its role is taken over by the Hahn–Banach theorem, in two classical forms. The extension form generalizes the projection theorem and yields a duality principle equating a minimum norm problem in a space XXX with a maximization problem in its dual X∗X^*X∗; the geometric form (separating hyperplanes) extends that duality from subspaces to convex sets. These duality theorems are the backbone of the optimization theory in the remainder of the book — conjugate functionals (Ch. 7) and Lagrange duality (Ch. 8) both trace back to them.

Setting

Throughout, XXX is a real normed linear space. A linear functional fff on XXX is bounded if ∣f(x)∣≤M∥x∥|f(x)| \le M\|x\|∣f(x)∣≤M∥x∥ for some constant MMM and all xxx; the least such MMM is the norm ∥f∥\|f\|∥f∥. The (normed) dual X∗X^*X∗ is the space of bounded (equivalently, continuous) linear functionals with this norm; ⟨x,x∗⟩\langle x, x^*\rangle⟨x,x∗⟩ denotes x∗(x)x^*(x)x∗(x). A functional p:X→Rp : X \to \mathbb{R}p:X→R is sublinear when p(x+y)≤p(x)+p(y)p(x+y) \le p(x) + p(y)p(x+y)≤p(x)+p(y) and p(αx)=α p(x)p(\alpha x) = \alpha\, p(x)p(αx)=αp(x) for α>0\alpha > 0α>0. Vectors x∈Xx \in Xx∈X and x∗∈X∗x^* \in X^*x∗∈X∗ are aligned when ⟨x,x∗⟩=∥x∗∥ ∥x∥\langle x, x^*\rangle = \|x^*\|\,\|x\|⟨x,x∗⟩=∥x∗∥∥x∥, and orthogonal when ⟨x,x∗⟩=0\langle x, x^*\rangle = 0⟨x,x∗⟩=0; for S⊆XS \subseteq XS⊆X, the complement S⊥⊆X∗S^\perp \subseteq X^*S⊥⊆X∗ consists of the functionals vanishing on SSS, and for U⊆X∗U \subseteq X^*U⊆X∗, ⊥U⊆X{}^\perp U \subseteq X⊥U⊆X consists of the vectors annihilated by every member of UUU. A hyperplane is a maximal proper linear variety; closed hyperplanes are the level sets {x:⟨x,x∗⟩=c}\{x : \langle x, x^*\rangle = c\}{x:⟨x,x∗⟩=c} of nonzero bounded functionals. The support functional of a convex set KKK is h(x∗)=sup⁡k∈K ⟨k,x∗⟩h(x^*) = \sup_{k \in K}\, \langle k, x^*\rangleh(x∗)=supk∈K​⟨k,x∗⟩.

Formalization targets

The goal is §5.13 Theorem 1 (Minimum Norm Duality): if x1∈Xx_1 \in Xx1​∈X has distance d>0d > 0d>0 from a convex set KKK with support functional hhh, then

d  =  inf⁡x∈K∥x−x1∥  =  max⁡∥x∗∥≤1 [⟨x1,x∗⟩−h(x∗)],d \;=\; \inf_{x \in K} \|x - x_1\| \;=\; \max_{\|x^*\| \le 1}\ \big[\langle x_1, x^*\rangle - h(x^*)\big],d=x∈Kinf​∥x−x1​∥=∥x∗∥≤1max​ [⟨x1​,x∗⟩−h(x∗)],

the maximum on the right being achieved by some x0∗x_0^*x0∗​; and if the infimum is achieved by x0∈Kx_0 \in Kx0​∈K, then −x0∗-x_0^*−x0∗​ is aligned with x0−x1x_0 - x_1x0​−x1​.

The milestones trace the chapter's route there: boundedness ⇔\Leftrightarrow⇔ continuity (§5.2); the Hahn–Banach theorem in sublinear form (§5.4 Theorem 1) with its norm-preserving extension and norming-functional corollaries; the annihilator identity ⊥(M⊥)=M{}^\perp(M^\perp) = M⊥(M⊥)=M for closed subspaces (§5.7 Theorem 1); the two subspace duality theorems and the alignment characterization of best approximations (§5.8 — the chapter's principal results); and the geometric form: Mazur's separation theorem, the support theorem, and Eidelheit's separation theorem (§5.12).

Significance

The §5.8 duality theorems are the exact normed-space analogue of the projection theorem: existence transfers to the dual problem (minimum norm problems should be formulated in a dual space to guarantee solutions — the chapter's methodological moral), orthogonality becomes alignment, and infinite-dimensional problems with finitely many constraints reduce to finite-dimensional dual problems. The geometric form underpins all of convex duality.

All results are classical and proved in the source. Mathlib contains the Hahn–Banach extension theorem and point/convex separation theorems, so several milestones are exercises in connecting Luenberger's formulations to existing library lemmas; the two §5.8 duality theorems, the alignment corollary, and the §5.13 convex duality theorem have no direct Mathlib counterpart and are the mission's genuinely new content.

Difficulty

Degenerate cases are the trap throughout. In §5.8 Corollary 1 the "only if" direction fails literally when MMM is dense and x∈Mx \in Mx∈M (then M⊥={0}M^\perp = \{0\}M⊥={0} and no nonzero aligned functional exists); the formalization therefore carries the hypothesis x∉M‾x \notin \overline{M}x∈/M. In the separation theorems the strict inequality holds only on the interior of the convex set — on the set itself only ≤\le≤ survives — and nonemptiness hypotheses (of the interior, of K2K_2K2​, of the variety) are what make the "nonzero functional" claims true; dropping any of them creates false statements in trivial spaces. In §5.13 the support functional may take the value +∞+\infty+∞, so the dual maximum is formalized by two quantified inequalities (the witness achieves ddd; no admissible functional exceeds ddd) rather than by a real-valued supremum. The infimum in the primal problems need not be attained — attainment appears only as a hypothesis in the alignment clauses.

Formalization scope

Real scalars throughout. The dual space is represented concretely as continuous linear maps X →L[ℝ] ℝ, and annihilators are written as explicit quantified conditions rather than named subspaces. Five notions the chapter needs and Mathlib lacks are published as definitions and used by the statements rather than inlined: alignment (⟨x,x∗⟩=∥x∗∥ ∥x∥\langle x, x^*\rangle = \|x^*\|\,\|x\|⟨x,x∗⟩=∥x∗∥∥x∥), the support functional (h(x∗)=sup⁡k∈K⟨k,x∗⟩h(x^*) = \sup_{k \in K} \langle k, x^*\rangleh(x∗)=supk∈K​⟨k,x∗⟩, valued in the extended reals since it may be infinite), the total variation of a function on an interval, the normalized space NBV[a,b]NBV[a,b]NBV[a,b], and the Riemann–Stieltjes integral (defined relationally, so that no existence claim is built into the definition). The Minkowski functional needed for Mazur's theorem is Mathlib's gauge. Minimum distances are infima ⨅ over coerced sets or submodules; in §5.8 Theorem 2 the dual-side supremum is a real sSup over {⟨x,x∗⟩:x∈M, ∥x∥≤1}\{\langle x, x^*\rangle : x \in M,\ \|x\| \le 1\}{⟨x,x∗⟩:x∈M, ∥x∥≤1}, which is nonempty and bounded. Sublinearity in §5.4 is hypothesized exactly as in the source (subadditivity plus positive homogeneity plus continuity). Linear varieties are parametrized as x0+Mx_0 + Mx0​+M with MMM a Submodule ℝ X. No completeness of XXX is assumed anywhere — the chapter's results are genuinely about normed spaces, and Hahn–Banach needs no completeness. The concrete dual of C[a,b]C[a,b]C[a,b] (§5.5) is in scope, and carries most of the mission's new infrastructure: Mathlib has the property of bounded variation (eVariationOn) but no total-variation norm, no normalized space NBV[a,b]NBV[a,b]NBV[a,b], and no Riemann–Stieltjes integral — its StieltjesFunction is the different object of a monotone right-continuous function inducing a Borel measure, and its Riesz–Markov–Kakutani development represents positive functionals on Cc(X)C_c(X)Cc​(X) by measures, not bounded functionals on C[a,b]C[a,b]C[a,b] by functions of bounded variation. This mission therefore publishes those notions as definitions and states the representation theorem in both directions. §5.3 (the Riesz–Fréchet theorem, i.e. self-duality of Hilbert space) is the one omission: Mathlib's InnerProductSpace.toDual already provides it. §5.6 (second dual, reflexivity) is definitional and likewise present in Mathlib.

Selected references

  • David G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, 1969. Chapter 5, pp. 103–142. ISBN 0-471-55359-X.
  • H. Hahn, Über lineare Gleichungssysteme in linearen Räumen, J. Reine Angew. Math. 157 (1927), 214–229; S. Banach, Sur les fonctionnelles linéaires II, Studia Math. 1 (1929), 223–239.
  • S. Mazur, Über konvexe Mengen in linearen normierten Räumen, Studia Math. 4 (1933), 70–84.
17 thms1 active userReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: Shuze Chen

Vector Space Methods II: Gauss–Markov EstimationTextbook

Motivation

Chapter 4 of Luenberger's Optimization by Vector Space Methods (Wiley, 1969) develops linear least-squares estimation as an application of the Hilbert space projection theorem formalized in Mission I of this series. The chapter's centerpiece is the classical Gauss–Markov theorem: among all linear unbiased estimators of an unknown parameter vector from noisy linear measurements, the estimator (W⊤Q−1W)−1W⊤Q−1y(W^\top Q^{-1} W)^{-1} W^\top Q^{-1} y(W⊤Q−1W)−1W⊤Q−1y has minimum variance — componentwise, not merely in trace. This result is foundational for statistics and econometrics, and its Hilbert-space derivation is the cleanest known.

Setting

Measurements are modeled as y=Wβ+εy = W\beta + \varepsilony=Wβ+ε, where yyy is an mmm-dimensional data vector, WWW a known m×nm \times nm×n matrix (n<mn < mn<m) with linearly independent columns, β\betaβ an unknown nnn-dimensional parameter vector, and ε\varepsilonε a random mmm-vector of measurement errors with Eε=0E\varepsilon = 0Eε=0 and covariance E[εε⊤]=QE[\varepsilon\varepsilon^\top] = QE[εε⊤]=Q, positive definite. A linear estimate is β^=Ky\hat\beta = Kyβ^​=Ky for a constant n×mn \times mn×m matrix KKK; it is unbiased when Eβ^=βE\hat\beta = \betaEβ^​=β for every β\betaβ, which holds iff KW=IKW = IKW=I. The optimality criterion is the error second moment E∥β^−β∥2E\|\hat\beta - \beta\|^2E∥β^​−β∥2, and the book's key observation (p. 85) is that the problem splits into nnn independent minimum norm problems, one per component, each solvable by the dual approximation theorem of Mission I.

Formally, randomness is carried by an abstract probability space: a measure space (Ω,μ)(\Omega, \mu)(Ω,μ) with μ\muμ a probability measure, random vectors as functions Ω→Rm\Omega \to \mathbb{R}^mΩ→Rm with explicit integrability hypotheses for all first and second moments, and E[⋅]=∫⋅ dμE[\cdot] = \int \cdot \, d\muE[⋅]=∫⋅dμ.

Formalization targets

The goal is §4.4 Theorem 1 (Gauss–Markov): with K0=(W⊤Q−1W)−1W⊤Q−1K_0 = (W^\top Q^{-1} W)^{-1} W^\top Q^{-1}K0​=(W⊤Q−1W)−1W⊤Q−1,

K0W=I,E[(K0y−β)i2]≤E[(Ky−β)i2]for every i and every K with KW=I,K_0 W = I, \qquad E\big[(K_0 y - \beta)_i^2\big] \le E\big[(K y - \beta)_i^2\big] \quad \text{for every } i \text{ and every } K \text{ with } KW = I,K0​W=I,E[(K0​y−β)i2​]≤E[(Ky−β)i2​]for every i and every K with KW=I,

with error covariance

E[(K0y−β)(K0y−β)⊤]=(W⊤Q−1W)−1.E\big[(K_0 y - \beta)(K_0 y - \beta)^\top\big] = (W^\top Q^{-1} W)^{-1}.E[(K0​y−β)(K0​y−β)⊤]=(W⊤Q−1W)−1.

Milestones: the deterministic least-squares estimate β^=(W⊤W)−1W⊤y\hat\beta = (W^\top W)^{-1} W^\top yβ^​=(W⊤W)−1W⊤y (§4.3 Theorem 1); the book's deterministic reduction — minimize the diagonal entries of KQK⊤KQK^\topKQK⊤ subject to KW=IKW = IKW=I (p. 85); the minimum-variance estimate β^=E[βy⊤](E[yy⊤])−1y\hat\beta = E[\beta y^\top] (E[y y^\top])^{-1} yβ^​=E[βy⊤](E[yy⊤])−1y for random β\betaβ (§4.5 Theorem 1); and the information-form identities RW⊤(WRW⊤+Q)−1=(W⊤Q−1W+R−1)−1W⊤Q−1RW^\top(WRW^\top + Q)^{-1} = (W^\top Q^{-1}W + R^{-1})^{-1}W^\top Q^{-1}RW⊤(WRW⊤+Q)−1=(W⊤Q−1W+R−1)−1W⊤Q−1 and R−RW⊤(WRW⊤+Q)−1WR=(W⊤Q−1W+R−1)−1R - RW^\top(WRW^\top+Q)^{-1}WR = (W^\top Q^{-1}W + R^{-1})^{-1}R−RW⊤(WRW⊤+Q)−1WR=(W⊤Q−1W+R−1)−1 (§4.5 Corollary 2).

Significance

The Gauss–Markov theorem justifies weighted least squares as the optimal linear unbiased procedure and is the standard benchmark against which biased and nonlinear estimators are measured. The minimum-variance estimate of §4.5 is the Bayesian counterpart with prior covariance RRR; the information-form identities connect the two and exhibit Gauss–Markov as the limit R−1→0R^{-1} \to 0R−1→0. Mission III builds the recursive (Kalman) estimator directly on these results.

All results are classical and proved in the source. Mathlib has mature measure-theoretic integration but, to date, no Gauss–Markov theorem and no linear estimation theory; the matrix milestones (trace reduction, information form) are also absent as stated. The probabilistic statements here are deliberately phrased with elementary integrals of products of real-valued components — no Bochner integration of vector-valued maps — so they are approachable with MeasureTheory.integral alone.

Difficulty

The subtlety is bookkeeping, not depth. Unbiasedness must be encoded as the algebraic constraint KW=IKW = IKW=I (the book proves the equivalence with Eβ^=βE\hat\beta = \betaEβ^​=β for all β\betaβ); the componentwise variance claim is strictly stronger than the trace claim and requires the per-component minimum norm argument, not a single matrix inequality. Positive definiteness of QQQ enters through invertibility of W⊤Q−1WW^\top Q^{-1} WW⊤Q−1W, which itself needs the linear independence of the columns of WWW — dropping either hypothesis makes the goal false. In the probabilistic statements every integral needs an integrability hypothesis; the drafts supply integrability of all pairwise products of components, from which integrability of every derived expression follows.

Formalization scope

Random vectors are plain functions Ω → Fin m → ℝ on a MeasurableSpace Ω with a probability measure μ; second moments are hypotheses of the form ∫ ω, ε ω i * ε ω j ∂μ = Q i j with explicit Integrable assumptions; no independence, Gaussianity, or distributional assumptions are used anywhere. Matrices are Matrix (Fin m) (Fin n) ℝ with Mathlib's Matrix.PosDef, nonconstructive inverse ⁻¹, and mulVec. Norms on parameter space are written as explicit finite sums of squares, avoiding any ambiguity between Euclidean and supremum norms on pi types. The estimators under comparison are strictly linear (β^=Ky\hat\beta = Kyβ^​=Ky, no affine offset), exactly as in the source; §4.5's affine extension (its Problem 6) is out of scope.

Selected references

  • David G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, 1969. Chapter 4, pp. 78–102. ISBN 0-471-55359-X.
  • A. C. Aitken, On least squares and linear combination of observations, Proc. Roy. Soc. Edinburgh 55 (1935), 42–48 (the weighted-least-squares form of Gauss–Markov).
8 thms1 active userReviewed
🏆Completed
Operations ResearchOptimization·Captain: Shuze Chen

Vector Space Methods I: Minimum Norm Problems in Hilbert SpaceTextbook

Motivation

Luenberger's Optimization by Vector Space Methods (Wiley, 1969) organizes a large part of optimization theory around a single geometric idea: minimum norm problems in inner product spaces, solved by orthogonal projection. Chapter 3 is the technical heart of that program. Its projection theorem and normal equations underlie least-squares data fitting, Fourier approximation, minimum-energy control, and the whole statistical estimation theory of Chapter 4 — which Missions II and III of this series formalize on top of the present one.

Setting

Throughout, spaces are real. A pre-Hilbert space is a real vector space XXX with an inner product ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle⟨⋅,⋅⟩ inducing the norm ∥x∥=⟨x,x⟩1/2\|x\| = \langle x,x\rangle^{1/2}∥x∥=⟨x,x⟩1/2; a Hilbert space HHH is a complete pre-Hilbert space. Vectors x,yx, yx,y are orthogonal when ⟨x,y⟩=0\langle x, y\rangle = 0⟨x,y⟩=0; for a subset SSS, the orthogonal complement S⊥S^\perpS⊥ is the set of vectors orthogonal to every element of SSS. Given y1,…,yn∈Hy_1,\dots,y_n \in Hy1​,…,yn​∈H, their Gram matrix is G(y1,…,yn)ij=⟨yi,yj⟩G(y_1,\dots,y_n)_{ij} = \langle y_i, y_j\rangleG(y1​,…,yn​)ij​=⟨yi​,yj​⟩ and its determinant g(y1,…,yn)g(y_1,\dots,y_n)g(y1​,…,yn​) is the Gram determinant. A linear variety is a translate x+Mx + Mx+M of a subspace MMM.

Formalization targets

The goal is §3.10 Theorem 2, the dual approximation problem: for linearly independent y1,…,yn∈Hy_1,\dots,y_n \in Hy1​,…,yn​∈H and constants c1,…,cnc_1,\dots,c_nc1​,…,cn​, among all x∈Hx \in Hx∈H satisfying the constraints

⟨x,yi⟩=ci,i=1,…,n,\langle x, y_i\rangle = c_i, \qquad i = 1,\dots,n,⟨x,yi​⟩=ci​,i=1,…,n,

there is a unique vector of minimum norm, and it has the form

x0=∑i=1nβi yi,where∑j=1nβj⟨yj,yi⟩=ci.x_0 = \sum_{i=1}^n \beta_i\, y_i, \qquad \text{where} \qquad \sum_{j=1}^n \beta_j \langle y_j, y_i\rangle = c_i .x0​=i=1∑n​βi​yi​,wherej=1∑n​βj​⟨yj​,yi​⟩=ci​.

The milestone list follows the chapter's own development: the projection theorem in its pre-Hilbert form (§3.3 Theorem 1) and classical form (§3.3 Theorem 2), the orthogonal decomposition H=M⊕M⊥H = M \oplus M^\perpH=M⊕M⊥ with M⊥⊥=MM^{\perp\perp} = MM⊥⊥=M (§3.4 Theorem 1), the normal equations and Gram matrices (§3.6), the Gram determinant formula δ2=g(y1,…,yn,x)/g(y1,…,yn)\delta^2 = g(y_1,\dots,y_n,x)/g(y_1,\dots,y_n)δ2=g(y1​,…,yn​,x)/g(y1​,…,yn​) for the minimum distance (§3.6 Theorem 1), best approximation by Fourier sums over orthonormal families (§3.7, §3.9), minimum norm over a linear variety (§3.10 Theorem 1), and the extension from subspaces to closed convex sets with its variational inequality characterization (§3.12 Theorem 1).

Significance

The dual approximation theorem converts an infinite-dimensional constrained minimum norm problem into an n×nn \times nn×n linear system — the book's model example of finite reduction, applied there to minimum-energy control of a motor (§3.11) and, in Chapter 4, to every linear estimation problem: least squares, Gauss–Markov, and recursive (Kalman) estimation are all instances of these results in a Hilbert space of random variables.

All results here are classical and proved in the source; the mission's product is a faithful machine-checked development with reusable statements. Mathlib already contains close relatives of several milestones (orthogonal projection onto complete subspaces, Submodule.orthogonal), so part of the work is connecting the book's formulations to that library; the Gram determinant distance formula and the dual approximation theorem itself have no direct Mathlib counterpart.

Difficulty

The individual milestones are standard Hilbert space theory. The care is in the statements, not tricks: the pre-Hilbert version of the projection theorem asserts uniqueness and the orthogonality characterization without existence, while existence requires completeness and closedness — conflating the two versions produces unprovable or vacuous statements. The Gram determinant formula requires the (n+1)×(n+1)(n+1) \times (n+1)(n+1)×(n+1) Gram matrix of the extended family (y1,…,yn,x)(y_1,\dots,y_n,x)(y1​,…,yn​,x), where index bookkeeping (Fin.snoc) is easy to get wrong. In §3.12 the variational inequality ⟨x−k0,k−k0⟩≤0\langle x - k_0, k - k_0\rangle \le 0⟨x−k0​,k−k0​⟩≤0 replaces the equality characterization valid for subspaces; the inequality direction is a known trap.

Formalization scope

The development commits to: real scalars (the book allows complex; this series does not), an abstract space H : Type with [NormedAddCommGroup H] [InnerProductSpace ℝ H] and [CompleteSpace H] exactly where the source assumes a Hilbert space; subspaces as Submodule ℝ H with explicit IsClosed hypotheses; finite families as Fin n → H; Gram matrices as Matrix (Fin n) (Fin n) ℝ via Matrix.of; minimum distances as infima (⨅) over coerced submodules. Best approximation statements are phrased as explicit inequalities ‖x - m₀‖ ≤ ‖x - m‖ rather than through any projection operator, so they are usable without choosing Mathlib's orthogonalProjection API. Statements deliberately carry no more hypotheses than the source: §3.3 Theorem 1 and the normal equations hold in any real inner product space; completeness appears only where existence is claimed.

Proofs are expected to lean on Mathlib's inner product space library; contributions of reusable bridging lemmas (e.g. between ⨅-formulations and orthogonalProjection) are welcome as child lemmas via proof sketches.

Selected references

  • David G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, 1969. Chapter 3, pp. 46–77. ISBN 0-471-55359-X.
10 thms1 active userReviewed
PreviousPage 10 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