Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 10.3.3 — finite Krylov membership criterion

Disproved
PutermanMDP.Sensitive.krylov_membership

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

blackwell-optimalitymdpp2o-gran-per-chapterp2o-plan-bookp2o-v1sensitive-discount

Let HHH be a real m×mm\times mm×m matrix of rank ppp, let U⊆RmU\subseteq\mathbb R^mU⊆Rm have dimension qqq, and let x∈Rmx\in\mathbb R^mx∈Rm. The printed statement asserts

[Hkx∈U for k=1,…,min⁡(p,q)] ⟹ [Hkx∈U for all k≥1].[H^kx\in U\text{ for }k=1,\ldots,\min(p,q)]\ \Longrightarrow\ [H^kx\in U\text{ for all }k\ge1].[Hkx∈U for k=1,…,min(p,q)] ⟹ [Hkx∈U for all k≥1].

This is the linear-algebra statement used by the chapter's finite-determination argument. It is retained as printed; FINDINGS F1 gives a counterexample and a disproof is expected.

Formalization Note Rank and dimension are computed from HHH and UUU, respectively; no invariance assumption is added.

Preamble
import Mathlib
Formal statement
namespace PutermanMDP.Sensitive

/-- Printed Lemma 10.3.3, retained faithfully; FINDINGS F1 gives a counterexample. -/
theorem krylov_membership (m : ℕ) (H : Matrix (Fin m) (Fin m) ℝ)
    (U : Submodule ℝ (Fin m → ℝ)) (x : Fin m → ℝ)
    (h : ∀ k : ℕ, 1 ≤ k → k ≤ min H.rank (Module.finrank ℝ U) →
      (H ^ k).mulVec x ∈ U) :
    ∀ k : ℕ, 1 ≤ k → (H ^ k).mulVec x ∈ U := by sorry

end PutermanMDP.Sensitive
Source
Puterman, Markov Decision Processes, Wiley, 1994, p. 517 (PDF 533), Lemma 10.3.3; https://doi.org/10.1002/9780470316887
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let m∈Nm\in\mathbb Nm∈N, let HHH be a real m×mm\times mm×m matrix, let UUU be a linear subspace of Rm\mathbb R^mRm, and let x∈Rmx\in\mathbb R^mx∈Rm. Write rank⁡H\operatorname{rank}HrankH for the dimension of the column space of HHH, and dim⁡U\dim UdimU for the dimension of UUU.

Hypothesis. Hkx∈UH^kx\in UHkx∈U for every integer kkk with

1≤k≤min⁡(rank⁡H, dim⁡U).1\le k\le\min(\operatorname{rank}H,\ \dim U).1≤k≤min(rankH, dimU).

Conclusion. Hkx∈UH^kx\in UHkx∈U for every integer k≥1k\ge1k≥1.

Degenerate cases. If min⁡(rank⁡H,dim⁡U)=0\min(\operatorname{rank}H,\dim U)=0min(rankH,dimU)=0, the hypothesis is vacuous, and the statement asserts Hkx∈UH^kx\in UHkx∈U for every xxx and every k≥1k\ge1k≥1. Two cases arise:

  • H=0H=0H=0: then Hkx=0∈UH^kx=0\in UHkx=0∈U, so the conclusion is immediate.
  • U={0}U=\{0\}U={0}: then the statement asserts Hkx=0H^kx=0Hkx=0 for every x∈Rmx\in\mathbb R^mx∈Rm and every k≥1k\ge1k≥1. Taking k=1k=1k=1, this says HHH is the zero matrix, for every HHH.

If m=0m=0m=0, every vector is zero and the statement holds trivially.

Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 2026

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

View graph

Get started

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

About Prove2Me

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

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me