Lax Lean Archive

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

Dyadic span deficit estimates

Lax342547.DyadicDeficits · concepts/Lax342547/DyadicDeficits.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 finite telescoping deficit recurrence yields a common scale with small combined row and column deficit.

    Concept map
    1 concept
    100%
    Proven claimThis conceptDescendants are omitted for concepts with more than 10 descendants.
    Evidence

    This concept declares 4 statements. Each proof establishes one of them relative to its assumptions.

    1 deficit_ratio_sum proven

    2 sum_differences proven

    3 sum_shift proven

    4 two_mode_scale proven

    Lean source view on GitHub

    1import Mathlib.Tactic
    2import Mathlib.Algebra.BigOperators.Ring.Finset
    3
    4/-!
    5---
    6title: Dyadic span deficit estimates
    7type: lemma
    8---
    9The finite telescoping deficit recurrence yields a common scale with small combined row and column deficit.
    10-/
    11
    12namespace Lax342547.DyadicDeficits
    13
    14open scoped BigOperators
    15
    16axiom sum_shift (v : ℕ → ℝ) (n : ℕ) :
    17 (∑ j ∈ Finset.range n, v (j+1)) = (∑ j ∈ Finset.range n, v j)-v 0+v n
    18
    19axiom sum_differences (f : ℕ → ℝ) (n : ℕ) :
    20 (∑ j ∈ Finset.range n, (f j-f (j+1))) = f 0-f n
    21
    22axiom deficit_ratio_sum (f v : ℕ → ℝ) (n : ℕ) (r : ℝ)
    23 (hrec : ∀ j < n, 2*v j ≤ 2*(f j-f (j+1))+v (j+1))
    24 (hf0 : f 0 ≤ r) (hfn : 0 ≤ f n) (hv0 : 0 ≤ v 0) (hvn : v n ≤ f n) :
    25 (∑ j ∈ Finset.range n, v j) ≤ 2*r
    26
    27axiom two_mode_scale (fC fR vC vR : ℕ → ℝ) (n : ℕ) (r : ℝ)
    28 (hC : ∀ j < n, 2*vC j ≤ 2*(fC j-fC (j+1))+vC (j+1))
    29 (hR : ∀ j < n, 2*vR j ≤ 2*(fR j-fR (j+1))+vR (j+1))
    30 (hfC0 : fC 0 ≤ r) (hfR0 : fR 0 ≤ r)
    31 (hfCn : 0 ≤ fC n) (hfRn : 0 ≤ fR n)
    32 (hvC0 : 0 ≤ vC 0) (hvR0 : 0 ≤ vR 0)
    33 (hvCn : vC n ≤ fC n) (hvRn : vR n ≤ fR n) (hn : 16*r < n) :
    34 ∃ j < n, vC j+vR j < 1/4
    35
    36end Lax342547.DyadicDeficits
    37
    Show ProofShow ProofShow ProofShow Proof
    Builds on

    none

    Used by
    From Mathlib

    Discussion

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

    Loading discussion…