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

Averaging outside a set of coordinates

Lax253009.FourierProjection · concepts/Lax253009/FourierProjection.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 U⊆IU\subseteq I, average a function FF over the coordinates outside UU, retaining the input on UU. The resulting function has Fourier coefficient F^(S)\widehat F(S) when S⊆US\subseteq U, and zero otherwise. This is Lemma 4.18 of Håstad's paper: take II to be the set of possible encoded words, and UU to be the words satisfying the side condition.

    The definition averages over a full independent cube; the unused coordinates give equal multiplicities, hence the same uniform average as over just the coordinates outside UU. Averaging preserves the bound ∣F∣≤1|F|\leq1. At an input whose entire averaging fiber has one value, that value is preserved.

    Concept map
    2 concepts; 4 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 Lax253009.BooleanFourier
    2
    3/-!
    4---
    5title: Averaging outside a set of coordinates
    6type: theorem
    7---
    8For U⊆IU\subseteq I, average a function FF over the coordinates outside
    9UU, retaining the input on UU. The resulting function has Fourier
    10coefficient F^(S)\widehat F(S) when S⊆US\subseteq U, and zero otherwise.
    11This is Lemma 4.18 of Håstad's paper: take II to be the set of possible
    12encoded words, and UU to be the words satisfying the side condition.
    13
    14The definition averages over a full independent cube; the unused coordinates
    15give equal multiplicities, hence the same uniform average as over just the
    16coordinates outside UU. Averaging preserves the bound ∣F∣≤1|F|\leq1. At an
    17input whose entire averaging fiber has one value, that value is preserved.
    18-/
    19
    20namespace Lax253009.FourierProjection
    21
    22open BooleanFourier
    23
    24def splice {ι : Type} [DecidableEq ι] (U : Finset ι) (x y : Cube ι) : Cube ι :=
    25 fun i ↦ if i ∈ U then x i else y i
    26
    27noncomputable def project {ι : Type} [Fintype ι] [DecidableEq ι]
    28 (F : Cube ι → ℝ) (U : Finset ι) (x : Cube ι) : ℝ :=
    29 average fun y ↦ F (splice U x y)
    30
    31axiom coefficient_project {ι : Type} [Fintype ι] [DecidableEq ι]
    32 (F : Cube ι → ℝ) (U S : Finset ι) :
    33 coefficient (project F U) S = if S ⊆ U then coefficient F S else 0
    34
    35axiom bounded_project {ι : Type} [Fintype ι] [DecidableEq ι]
    36 (F : Cube ι → ℝ) (hF : ∀ x, |F x| ≤ 1) (U : Finset ι) (x : Cube ι) :
    37 |project F U x| ≤ 1
    38
    39axiom constant_fiber {ι : Type} [Fintype ι] [DecidableEq ι]
    40 (F : Cube ι → ℝ) (U : Finset ι) (x : Cube ι)
    41 (hF : ∀ y, (∀ i ∈ U, y i = x i) → F y = F x) :
    42 project F U x = F x
    43
    44end Lax253009.FourierProjection
    45
    Show ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…