The size of the decoding set from large coefficients
Lax253009.SmallSupport · concepts/Lax253009/SmallSupport.lean · lax-253009
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Let real coefficients be indexed by subsets of an -element set and satisfy . For , take the union of the sets with and . Then .
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 , it gives . The statement below isolates the counting argument; its energy bound is an explicit hypothesis, not an assumed Fourier identity.
Concept map
Lean source view on GitHub
| 1 | import Mathlib.Data.Real.Basic |
| 2 | import Mathlib.Data.Fintype.Powerset |
| 3 | import Mathlib.Algebra.Order.BigOperators.Group.Finset |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: The size of the decoding set from large coefficients |
| 8 | type: theorem |
| 9 | --- |
| 10 | Let real coefficients be indexed by subsets of an -element |
| 11 | set and satisfy . For , take the |
| 12 | union of the sets with and |
| 13 | . Then . |
| 14 | |
| 15 | This is the counting argument for the decoding set in equation (2) of |
| 16 | Håstad's paper. Applied to Fourier coefficients using Parseval's identity |
| 17 | and , it gives . |
| 18 | The statement below isolates the counting argument; its energy bound is an |
| 19 | explicit hypothesis, not an assumed Fourier identity. |
| 20 | -/ |
| 21 | |
| 22 | namespace Lax253009.SmallSupport |
| 23 | |
| 24 | noncomputable 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 | |
| 29 | noncomputable def decodingSet {ι : Type} [Fintype ι] [DecidableEq ι] (c : Finset ι → ℝ) (l : ℕ) |
| 30 | (δ : ℝ) : Finset ι := |
| 31 | (largeSets c l δ).biUnion id |
| 32 | |
| 33 | axiom decodingSet_bound {ι : Type} [Fintype ι] [DecidableEq ι] (c : Finset ι → ℝ) (l : ℕ) |
| 34 | (δ : ℝ) (hδ : 0 < δ) (henergy : ∑ a, c a ^ 2 ≤ 1) : |
| 35 | ((decodingSet c l δ).card : ℝ) ≤ 1 / δ |
| 36 | |
| 37 | end Lax253009.SmallSupport |
| 38 |
Builds on
none
Used by
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments