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

The size of the decoding set from large coefficients

Lax253009.SmallSupport · concepts/Lax253009/SmallSupport.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 real coefficients cαc_\alpha be indexed by subsets of an nn-element set and satisfy ∑αcα2≤1\sum_\alpha c_\alpha^2\leq1. For δ>0\delta>0, take the union SS of the sets α\alpha with ∣α∣≤ℓ|\alpha|\leq\ell and cα2≥ℓδc_\alpha^2\geq\ell\delta. Then ∣S∣≤1/δ|S|\leq1/\delta.

    This is the counting argument for the decoding set in equation (2) of Håstad's paper. Applied to Fourier coefficients using Parseval's identity and δ=2−εs\delta=2^{-\varepsilon s}, it gives ∣S∣≤2εs|S|\leq2^{\varepsilon s}. The statement below isolates the counting argument; its energy bound is an explicit hypothesis, not an assumed Fourier identity.

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

    Each proof establishes this claim relative to its assumptions.

    Lean source view on GitHub

    1import Mathlib.Data.Real.Basic
    2import Mathlib.Data.Fintype.Powerset
    3import Mathlib.Algebra.Order.BigOperators.Group.Finset
    4
    5/-!
    6---
    7title: The size of the decoding set from large coefficients
    8type: theorem
    9---
    10Let real coefficients cαc_\alpha be indexed by subsets of an nn-element
    11set and satisfy ∑αcα2≤1\sum_\alpha c_\alpha^2\leq1. For δ>0\delta>0, take the
    12union SS of the sets α\alpha with ∣α∣≤ℓ|\alpha|\leq\ell and
    13cα2≥ℓδc_\alpha^2\geq\ell\delta. Then ∣S∣≤1/δ|S|\leq1/\delta.
    14
    15This is the counting argument for the decoding set in equation (2) of
    16Håstad's paper. Applied to Fourier coefficients using Parseval's identity
    17and δ=2−εs\delta=2^{-\varepsilon s}, it gives ∣S∣≤2εs|S|\leq2^{\varepsilon s}.
    18The statement below isolates the counting argument; its energy bound is an
    19explicit hypothesis, not an assumed Fourier identity.
    20-/
    21
    22namespace Lax253009.SmallSupport
    23
    24noncomputable def largeSets {ι : Type} [Fintype ι] [DecidableEq ι] (c : Finset ι → ℝ) (l : ℕ)
    25 (δ : ℝ) : Finset (Finset ι) := by
    26 classical
    27 exact Finset.univ.filter fun a ↦ a.card ≤ l ∧ (l : ℝ) * δ ≤ c a ^ 2
    28
    29noncomputable def decodingSet {ι : Type} [Fintype ι] [DecidableEq ι] (c : Finset ι → ℝ) (l : ℕ)
    30 (δ : ℝ) : Finset ι :=
    31 (largeSets c l δ).biUnion id
    32
    33axiom decodingSet_bound {ι : Type} [Fintype ι] [DecidableEq ι] (c : Finset ι → ℝ) (l : ℕ)
    34 (δ : ℝ) (hδ : 0 < δ) (henergy : ∑ a, c a ^ 2 ≤ 1) :
    35 ((decodingSet c l δ).card : ℝ) ≤ 1 / δ
    36
    37end Lax253009.SmallSupport
    38
    Show Proof

    Discussion

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

    Loading discussion…