Cancellation outside double covers in higher moments
Lax253009.HigherMoments · concepts/Lax253009/HigherMoments.lean · lax-253009
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
For a family of supports and independently sampled labels , the expectation of factors over coordinates . 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 . This is the union-size bound used in the reduction from double covers to even covers in Lemma 4.15. Whenever , one can retain exactly positions that still cover each point at least twice. This is the subcover extraction used in Lemma 4.16.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax253009.ProductMoments |
| 2 | import Mathlib.Algebra.Order.BigOperators.Group.Finset |
| 3 | |
| 4 | /-! |
| 5 | --- |
| 6 | title: Cancellation outside double covers in higher moments |
| 7 | type: theorem |
| 8 | --- |
| 9 | For a family of supports and independently sampled labels , |
| 10 | the expectation of factors over |
| 11 | coordinates . If the predicates are balanced and a coordinate occurs |
| 12 | in exactly one support, the expectation vanishes. Thus only double covers |
| 13 | contribute to the higher-moment expansion in equation (12). |
| 14 | |
| 15 | A double cover uses every point of its union at least twice, so |
| 16 | . This is the union-size bound used in |
| 17 | the reduction from double covers to even covers in Lemma 4.15. Whenever |
| 18 | , one can retain exactly positions |
| 19 | that still cover each point at least twice. This is the subcover |
| 20 | extraction used in Lemma 4.16. |
| 21 | -/ |
| 22 | |
| 23 | namespace Lax253009.HigherMoments |
| 24 | |
| 25 | open scoped BigOperators |
| 26 | |
| 27 | def DoubleCover {ι α : Type} [DecidableEq ι] [Fintype α] (S : α → Finset ι) : Prop := |
| 28 | ∀ i ∈ Finset.univ.biUnion S, 2 ≤ (Finset.univ.filter fun j ↦ i ∈ S j).card |
| 29 | |
| 30 | axiom 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 | |
| 35 | axiom 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 | |
| 41 | axiom 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 | |
| 45 | axiom 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 | |
| 51 | end Lax253009.HigherMoments |
| 52 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments