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

Mixed moments of balanced predicates on independent coordinates

Lax253009.ProductMoments · concepts/Lax253009/ProductMoments.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

    Choose independently and uniformly a label f(i)f(i) from a nonempty finite set for every coordinate ii. If two real predicates B,CB,C have mean zero, then Ef[∏i∈SB(f(i))∏i∈TC(f(i))]\mathbb E_f\bigl[\prod_{i\in S}B(f(i))\prod_{i\in T}C(f(i))\bigr] is zero for S≠TS\ne T, and is (EzB(z)C(z))∣S∣(\mathbb E_z B(z)C(z))^{|S|} for S=TS=T.

    This is the independence and cancellation argument from equation (6) to equation (7) in the proof of Lemma 4.5. For the application, labels are ss-bit words and the predicates are balanced sign-valued functions.

    For a finite family of balanced predicates, the second moment of a weighted sum over supports therefore contains only equal-support terms, weighted by the squares of their coefficients. This yields the exact expression in equation (7) before the correlation estimates are applied. For supports of size at least ℓ\ell and coefficients of total squared mass at most one, this second moment is bounded by the sum of the absolute correlations to the power ℓ\ell.

    Concept map
    1 concept; 10 descendants hidden
    100%
    Proven claimThis conceptRelated conceptA → B: B builds on A
    Evidence

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

    Lean source view on GitHub

    1import Mathlib.Data.Real.Basic
    2import Mathlib.Data.Fintype.Pi
    3import Mathlib.Algebra.BigOperators.Expect
    4import Mathlib.Algebra.BigOperators.Ring.Finset
    5
    6/-!
    7---
    8title: Mixed moments of balanced predicates on independent coordinates
    9type: theorem
    10---
    11Choose independently and uniformly a label f(i)f(i) from a nonempty finite
    12set for every coordinate ii. If two real predicates B,CB,C have mean zero,
    13then
    14Ef[∏i∈SB(f(i))∏i∈TC(f(i))]\mathbb E_f\bigl[\prod_{i\in S}B(f(i))\prod_{i\in T}C(f(i))\bigr]
    15is zero for S≠TS\ne T, and is
    16(EzB(z)C(z))∣S∣(\mathbb E_z B(z)C(z))^{|S|} for S=TS=T.
    17
    18This is the independence and cancellation argument from equation (6) to
    19equation (7) in the proof of Lemma 4.5. For the application, labels are
    20ss-bit words and the predicates are balanced sign-valued functions.
    21
    22For a finite family of balanced predicates, the second moment of a weighted
    23sum over supports therefore contains only equal-support terms, weighted
    24by the squares of their coefficients. This yields the exact expression
    25in equation (7) before the correlation estimates are applied.
    26For supports of size at least ℓ\ell and coefficients of total squared mass
    27at most one, this second moment is bounded by the sum of the absolute
    28correlations to the power ℓ\ell.
    29-/
    30
    31namespace Lax253009.ProductMoments
    32
    33open scoped BigOperators
    34
    35noncomputable def weightedSum {ι κ : Type} (supports : Finset (Finset ι))
    36 (c : Finset ι → ℝ) (predicates : Finset (κ → ℝ)) (f : ι → κ) : ℝ :=
    37 ∑ S ∈ supports, c S * ∑ B ∈ predicates, ∏ i ∈ S, B (f i)
    38
    39axiom mixed_moment {ι κ : Type} [Fintype ι] [DecidableEq ι]
    40 [Fintype κ] [Nonempty κ] (B C : κ → ℝ)
    41 (hB : (𝔼 z, B z) = 0) (hC : (𝔼 z, C z) = 0) (S T : Finset ι) :
    42 (𝔼 f : ι → κ, (∏ i ∈ S, B (f i)) * (∏ i ∈ T, C (f i))) =
    43 if S = T then (𝔼 z, B z * C z) ^ S.card else 0
    44
    45axiom second_moment {ι κ : Type} [Fintype ι] [DecidableEq ι]
    46 [Fintype κ] [Nonempty κ] (supports : Finset (Finset ι))
    47 (c : Finset ι → ℝ) (predicates : Finset (κ → ℝ))
    48 (hbalanced : ∀ B ∈ predicates, (𝔼 z, B z) = 0) :
    49 (𝔼 f : ι → κ, weightedSum supports c predicates f ^ 2) =
    50 ∑ S ∈ supports, c S ^ 2 *
    51 ∑ B ∈ predicates, ∑ C ∈ predicates, (𝔼 z, B z * C z) ^ S.card
    52
    53axiom high_degree_bound {ι κ : Type} [Fintype ι] [DecidableEq ι]
    54 [Fintype κ] [Nonempty κ] (supports : Finset (Finset ι))
    55 (c : Finset ι → ℝ) (predicates : Finset (κ → ℝ)) (l : ℕ)
    56 (hbalanced : ∀ B ∈ predicates, (𝔼 z, B z) = 0)
    57 (hbounded : ∀ B ∈ predicates, ∀ z, |B z| ≤ 1)
    58 (hdegree : ∀ S ∈ supports, l ≤ S.card)
    59 (henergy : ∑ S ∈ supports, c S ^ 2 ≤ 1) :
    60 (𝔼 f : ι → κ, weightedSum supports c predicates f ^ 2) ≤
    61 ∑ B ∈ predicates, ∑ C ∈ predicates, |𝔼 z, B z * C z| ^ l
    62
    63end Lax253009.ProductMoments
    64
    Show ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…