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

Cancellation outside double covers in higher moments

Lax253009.HigherMoments · concepts/Lax253009/HigherMoments.lean · lax-253009

proven

Loading review…

Sign in with ORCID

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

    Theorem

    For a family of supports SjS_j and independently sampled labels f(i)f(i), the expectation of ∏j∏i∈SjBj(f(i))\prod_j\prod_{i\in S_j}B_j(f(i)) factors over coordinates ii. If the predicates are balanced and a coordinate occurs in exactly one support, the expectation vanishes. Thus only double covers contribute to the higher-moment expansion in equation (12).

    A double cover uses every point of its union at least twice, so 2∣⋃jSj∣≤∑j∣Sj∣2|\bigcup_jS_j|\leq\sum_j|S_j|. This is the union-size bound used in the reduction from double covers to even covers in Lemma 4.15. Whenever 2∣⋃jSj∣≤r≤m2|\bigcup_jS_j|\leq r\leq m, one can retain exactly rr positions that still cover each point at least twice. This is the subcover extraction used in Lemma 4.16.

    Concept map
    2 concepts; 7 descendants hidden
    100%
    Proven claimThis conceptRelated conceptA → B: B builds on A
    Evidence

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

    1 double_cover_union_bound proven

    2 double_subcover proven

    Lean source view on GitHub

    1import Lax253009.ProductMoments
    2import Mathlib.Algebra.Order.BigOperators.Group.Finset
    3
    4/-!
    5---
    6title: Cancellation outside double covers in higher moments
    7type: theorem
    8---
    9For a family of supports SjS_j and independently sampled labels f(i)f(i),
    10the expectation of ∏j∏i∈SjBj(f(i))\prod_j\prod_{i\in S_j}B_j(f(i)) factors over
    11coordinates ii. If the predicates are balanced and a coordinate occurs
    12in exactly one support, the expectation vanishes. Thus only double covers
    13contribute to the higher-moment expansion in equation (12).
    14
    15A double cover uses every point of its union at least twice, so
    162∣⋃jSj∣≤∑j∣Sj∣2|\bigcup_jS_j|\leq\sum_j|S_j|. This is the union-size bound used in
    17the reduction from double covers to even covers in Lemma 4.15. Whenever
    182∣⋃jSj∣≤r≤m2|\bigcup_jS_j|\leq r\leq m, one can retain exactly rr positions
    19that still cover each point at least twice. This is the subcover
    20extraction used in Lemma 4.16.
    21-/
    22
    23namespace Lax253009.HigherMoments
    24
    25open scoped BigOperators
    26
    27def DoubleCover {ι α : Type} [DecidableEq ι] [Fintype α] (S : α → Finset ι) : Prop :=
    28 ∀ i ∈ Finset.univ.biUnion S, 2 ≤ (Finset.univ.filter fun j ↦ i ∈ S j).card
    29
    30axiom factorization {ι κ : Type} [Fintype ι] [DecidableEq ι]
    31 [Fintype κ] {m : ℕ} (S : Fin m → Finset ι) (B : Fin m → κ → ℝ) :
    32 (𝔼 f : ι → κ, ∏ j, ∏ i ∈ S j, B j (f i)) =
    33 ∏ i, (𝔼 z, ∏ j with i ∈ S j, B j z)
    34
    35axiom singleton_cancellation {ι κ : Type} [Fintype ι] [DecidableEq ι]
    36 [Fintype κ] {m : ℕ} (S : Fin m → Finset ι) (B : Fin m → κ → ℝ)
    37 (hbalanced : ∀ j, (𝔼 z, B j z) = 0) (i : ι) (j : Fin m)
    38 (hij : i ∈ S j) (hunique : ∀ j', i ∈ S j' → j' = j) :
    39 (𝔼 f : ι → κ, ∏ j, ∏ i ∈ S j, B j (f i)) = 0
    40
    41axiom double_cover_union_bound {ι : Type} [DecidableEq ι] {m : ℕ}
    42 (S : Fin m → Finset ι) (hS : DoubleCover S) :
    43 2 * (Finset.univ.biUnion S).card ≤ ∑ j, (S j).card
    44
    45axiom double_subcover {ι : Type} [DecidableEq ι] {m : ℕ}
    46 (S : Fin m → Finset ι) (hS : DoubleCover S) (r : ℕ)
    47 (hr : 2 * (Finset.univ.biUnion S).card ≤ r) (hrm : r ≤ m) :
    48 ∃ J : Finset (Fin m), J.card = r ∧
    49 ∀ i ∈ Finset.univ.biUnion S, 2 ≤ (J.filter fun j ↦ i ∈ S j).card
    50
    51end Lax253009.HigherMoments
    52
    Show ProofShow ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…