Averaging outside a set of coordinates
Lax253009.FourierProjection · concepts/Lax253009/FourierProjection.lean · lax-253009
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
For , average a function over the coordinates outside , retaining the input on . The resulting function has Fourier coefficient when , and zero otherwise. This is Lemma 4.18 of Håstad's paper: take to be the set of possible encoded words, and 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 . Averaging preserves the bound . At an input whose entire averaging fiber has one value, that value is preserved.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax253009.BooleanFourier |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Averaging outside a set of coordinates |
| 6 | type: theorem |
| 7 | --- |
| 8 | For , average a function over the coordinates outside |
| 9 | , retaining the input on . The resulting function has Fourier |
| 10 | coefficient when , and zero otherwise. |
| 11 | This is Lemma 4.18 of Håstad's paper: take to be the set of possible |
| 12 | encoded words, and to be the words satisfying the side condition. |
| 13 | |
| 14 | The definition averages over a full independent cube; the unused coordinates |
| 15 | give equal multiplicities, hence the same uniform average as over just the |
| 16 | coordinates outside . Averaging preserves the bound . At an |
| 17 | input whose entire averaging fiber has one value, that value is preserved. |
| 18 | -/ |
| 19 | |
| 20 | namespace Lax253009.FourierProjection |
| 21 | |
| 22 | open BooleanFourier |
| 23 | |
| 24 | def splice {ι : Type} [DecidableEq ι] (U : Finset ι) (x y : Cube ι) : Cube ι := |
| 25 | fun i ↦ if i ∈ U then x i else y i |
| 26 | |
| 27 | noncomputable def project {ι : Type} [Fintype ι] [DecidableEq ι] |
| 28 | (F : Cube ι → ℝ) (U : Finset ι) (x : Cube ι) : ℝ := |
| 29 | average fun y ↦ F (splice U x y) |
| 30 | |
| 31 | axiom 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 | |
| 35 | axiom bounded_project {ι : Type} [Fintype ι] [DecidableEq ι] |
| 36 | (F : Cube ι → ℝ) (hF : ∀ x, |F x| ≤ 1) (U : Finset ι) (x : Cube ι) : |
| 37 | |project F U x| ≤ 1 |
| 38 | |
| 39 | axiom 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 | |
| 44 | end Lax253009.FourierProjection |
| 45 |
Builds on
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments