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

Dimension-independent bounds for weighted double covers

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

    Let nonnegative coefficients cSc_S be supported on sets of size at most ℓ\ell, with ∑ScS2≤1\sum_S c_S^2\leq1. For every mm, the sum of ∏j=1mcSj\prod_{j=1}^m c_{S_j} over double-cover tuples is bounded by a constant depending only on ℓ,m\ell,m, not on the underlying coordinate set. We give the explicit, nonoptimal bound 1+3ℓ(2m+1)2m1+3^{\ell(2m+1)2^m}.

    This is the normalized form of Lemma 4.15 needed for the small-coefficient analysis. The proof uses a centered variable equal to 3 with probability 1/4 and -1 otherwise. Its moments vanish at order one and are at least one at every order at least two. Representing it on two Boolean coordinates allows the low-degree moment bound to control all double-cover terms.

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

    Lean source view on GitHub

    1import Lax253009.HigherMoments
    2import Lax253009.Hypercontractivity
    3
    4/-!
    5---
    6title: Dimension-independent bounds for weighted double covers
    7type: theorem
    8---
    9Let nonnegative coefficients cSc_S be supported on sets of size at most
    10ℓ\ell, with ∑ScS2≤1\sum_S c_S^2\leq1. For every mm, the sum of
    11∏j=1mcSj\prod_{j=1}^m c_{S_j} over double-cover tuples is bounded by a constant
    12depending only on ℓ,m\ell,m, not on the underlying coordinate set.
    13We give the explicit, nonoptimal bound 1+3ℓ(2m+1)2m1+3^{\ell(2m+1)2^m}.
    14
    15This is the normalized form of Lemma 4.15 needed for the small-coefficient
    16analysis. The proof uses a centered variable equal to 3 with probability
    171/4 and -1 otherwise. Its moments vanish at order one and are at least one
    18at every order at least two. Representing it on two Boolean coordinates
    19allows the low-degree moment bound to control all double-cover terms.
    20-/
    21
    22namespace Lax253009.DoubleCoverBounds
    23
    24open HigherMoments
    25open scoped BigOperators
    26
    27noncomputable def weight {ι : Type} [Fintype ι] [DecidableEq ι]
    28 (c : Finset ι → ℝ) (m : ℕ) : ℝ := by
    29 classical
    30 exact ∑ S : Fin m → Finset ι, if DoubleCover S then ∏ j, c (S j) else 0
    31
    32axiom bound {ι : Type} [Fintype ι] [DecidableEq ι]
    33 (c : Finset ι → ℝ) (l m : ℕ) (hc : ∀ S, 0 ≤ c S)
    34 (hdegree : ∀ S, l < S.card → c S = 0) (henergy : ∑ S, c S ^ 2 ≤ 1) :
    35 weight c m ≤ 1 + (3 : ℝ) ^ (l * (2 * m + 1) * 2 ^ m)
    36
    37end Lax253009.DoubleCoverBounds
    38
    Show Proof

    Discussion

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

    Loading discussion…