Lax Lean Archive

While this submission is a draft, it cannot be used by other submissions.

A low rank sum supplies an actual adaptive cover

Lax342547.NoCoverCertificate · concepts/Lax342547/NoCoverCertificate.lean · lax-342547

proven

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Lemma

    The complete deterministic greedy exposure proof turns a low rank sum into disjoint exposed and covered index sets, with the cover determined by the exposed column and row spans.

    Concept map
    28 concepts
    100%
    Proven claimThis conceptRelated conceptA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.
    Evidence

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Lax342547.ProjectedCounts
    2import Lax342547.ExposedSums
    3import Lax342547.FilterOccurrences
    4import Lax342547.CoverCounts
    5
    6/-!
    7---
    8title: A low rank sum supplies an actual adaptive cover
    9type: lemma
    10---
    11The complete deterministic greedy exposure proof turns a low rank sum into disjoint exposed and covered index sets, with the cover determined by the exposed column and row spans.
    12-/
    13
    14namespace Lax342547.NoCoverCertificate
    15
    16open Lax342547.GreedySpans Lax342547.GreedyTails Lax342547.CoverProjection
    17open scoped BigOperators
    18
    19axiom low_rank_cover_certificate {K V W ι : Type} [Field K] [Fintype ι] [DecidableEq ι]
    20 [AddCommGroup V] [Module K V] [AddCommGroup W] [Module K W]
    21 [FiniteDimensional K V] [FiniteDimensional K W]
    22 (M : ι → V →ₗ[K] W) (r : ℝ) (k n : ℕ)
    23 (hM : ∀ i, (Module.finrank K (LinearMap.range (M i)) : ℝ) ≤ r)
    24 (hcard : Fintype.card ι = 2^k) (hnk : n ≤ k) (hn : 16*r < n)
    25 (hlow : (Module.finrank K (LinearMap.range (∑ i, M i)) : ℝ) < (2^(k-n) : ℝ)/4) :
    26 ∃ E J : Finset ι, Disjoint E J ∧ 2^(k-n) ≤ J.card ∧
    27 ∀ j ∈ J, projection (M j) (E.sup (fun i => LinearMap.range (M i)))
    28 (E.sup (fun i => LinearMap.range (M i).dualMap)) = 0
    29
    30end Lax342547.NoCoverCertificate
    31
    Show Proof
    Builds on
    Used by
    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…