ComparatorChallenges/UniformFourier.lean

GitHub source file

Explanation legend Lean4 Domain Explanation Language (L4DEL)

L4DEL explanations are a separate layer. They do not change the Lean source. Intuition is explanatory prose; numbered items are a reading path; sources link the wording back to evidence.

L4DEL
Lean4 Domain Explanation Language

Credit: OpenAI's pinned repository says an unreleased internal model produced the manuscripts and supporting proof artifacts. The collection builds on the mathematics community's accumulated problems, results, language, and formal libraries; each manuscript's BibTeX and bibliography are the authority for individual scholarly credit.

Project sources: Pinned openai/math documentation, Pinned formalization catalogue

58 declarations, 2 contain sorry, 0 declared as axioms

Exact scalar and index RAM used for the algorithm

Finite, first-order, expression/program syntax. Arrays below are random-access arrays of registers (an array-valued register holds its address). An expression building an array uses a fresh array; sow builds by a loop of writes instead of a loop supplying consecutive entries. Programs have their usual sequential stack evaluation. Evaluation here records work (including stack, index and array work), the high water mark on produced/logically looped-over integer values (addresses within arrays are integers too), the value, and the side condition required along the executed path (in particular no division by zero). The charged units of work are constant time; as usual constant rescalings between ways to charge a fixed number of scalar or address operations are immaterial.

Enough address bits must be provided BOTH for the integer high water mark (and inputs), AND for the work bound together with input size, as will be required in the theorem. Indeed we use the particularly simple RAM convention where temporaries aren't reused: one work unit can leave at most a constant number of cells (stack, pairs or array cells); whenever many array entries are made their number is charged. So a constant number of words of those sizes also suffices for arena addresses. Nothing charges constant work for changing an already published array to a different array as a whole. Register and stack layouts, and the convention whether registers hold pairs or addresses of pairs, only have constant factors (the program is fixed).

Scalar and data field registers are separated. Tests and loop/request sizes are on nonnegative integer registers. There is no instruction for an arbitrary complex constant. A supplied specified root will be an input. Divisions are on prepared scalars; valid runs require every such denominator nonzero; the side condition is not a test performed by the algorithm. The Bool mode on the syntax allows or prohibits general products (two-input convolution versus the transform); even when allowed we use separate register kinds before and after the bilinear products.

Definitions are mathematical operation-count semantics, not a model of running Lean code. E.g. a function on Fin n represents the n cells of a random-access array, not a function closure at runtime.

  1. def OAI.ExactFourier.zeta line 6

    Also declared: ComparatorChallenges/ExactFourier.lean:44 (same declaration text), OAI/Computability/FourierCircuit/Core.lean:40 (same declaration text).

  2. structure OAI.PowerSaving.Tape Register arrays line 51

    Source documentation

    Register arrays.

    L4DEL explanation

    Register arrays.

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:47 (same declaration text).

    structure Tape (α : Type u) where
    …
  3. def OAI.PowerSaving.Tape.empty line 57

    Also declared: OAI/Computability/FourierTransform/RAM.lean:53 (same declaration text).

  4. def OAI.PowerSaving.Tape.tab Materialized array line 60

    Source documentation

    Materialized array.

    L4DEL explanation

    Materialized array.

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:56 (same declaration text).

    def tab (n : ℕ) (f : ℕ → α) : Tape α := ⟨n, fun i => f i.val⟩

    Mentions: OAI.PowerSaving.Tape

  5. def OAI.PowerSaving.Tape.look Read with fixed out of bounds default line 63

    Source documentation

    Read with fixed out of bounds default.

    L4DEL explanation

    Read with fixed out of bounds default.

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:59 (same declaration text).

    def look (v : Tape α) (i : ℕ) (z : α) : α :=
    …

    Mentions: OAI.PowerSaving.Tape

  6. theorem OAI.PowerSaving.Tape.look_of_lt line 66

    Also declared: OAI/Computability/FourierTransform/RAM.lean:62 (same declaration text).

  7. theorem OAI.PowerSaving.Tape.look_of_le line 69

    Also declared: OAI/Computability/FourierTransform/RAM.lean:65 (same declaration text).

  8. def OAI.PowerSaving.Tape.set Semantics of a write into fresh storage; out-of-range writes are ignored line 74

    Source documentation

    Semantics of a write into fresh storage; out-of-range writes are ignored. Only used during construction, never a whole-tape functional update instruction.

    L4DEL explanation

    Semantics of a write into fresh storage; out-of-range writes are ignored. Only used during construction, never a whole-tape functional update instruction.

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:70 (same declaration text).

    def set (v : Tape α) (i : ℕ) (x : α) : Tape α :=
    …

    Mentions: OAI.PowerSaving.Tape

  9. def OAI.PowerSaving.Tape.sow line 77

    Also declared: OAI/Computability/FourierTransform/RAM.lean:73 (same declaration text).

  10. def OAI.PowerSaving.Tape.map line 84

    Also declared: OAI/Computability/FourierTransform/RAM.lean:80 (same declaration text).

  11. inductive OAI.PowerSaving.RAM.Paint line 90

    Also declared: OAI/Computability/FourierTransform/RAM.lean:86 (same declaration text).

  12. inductive OAI.PowerSaving.RAM.Ty line 96

    Also declared: OAI/Computability/FourierTransform/RAM.lean:92 (same declaration text).

  13. abbrev OAI.PowerSaving.RAM.sc line 104

    Also declared: OAI/Computability/FourierTransform/RAM.lean:100 (same declaration text).

  14. def OAI.PowerSaving.RAM.Ty.T line 106

    Also declared: OAI/Computability/FourierTransform/RAM.lean:102 (same declaration text).

  15. def OAI.PowerSaving.RAM.Ty.blank line 112

    Also declared: OAI/Computability/FourierTransform/RAM.lean:108 (same declaration text).

  16. structure OAI.PowerSaving.RAM.Bill One basic work unit below pays for O(1) primitive RAM operations; includes loop and stack overhead line 121

    Source documentation

    One basic work unit below pays for O(1) primitive RAM operations; includes loop and stack overhead. peak tracks produced/needed integer quantities beyond inputs (total allocation for stack and array bases is covered separately by work).

    L4DEL explanation

    One basic work unit below pays for O(1) primitive RAM operations; includes loop and stack overhead. peak tracks produced/needed integer quantities beyond inputs (total allocation for stack and array bases is covered separately by work).

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:117 (same declaration text).

    structure Bill (α : Type u) where
    …
  17. def OAI.PowerSaving.RAM.Bill.pay Charge some work and optionally a new word bound line 130

    Source documentation

    Charge some work and optionally a new word bound.

    L4DEL explanation

    Charge some work and optionally a new word bound.

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:126 (same declaration text).

    def pay (b : Bill α) (n : ℕ) (m : ℕ) : Bill α :=
    …

    Mentions: OAI.PowerSaving.RAM.Bill

  18. def OAI.PowerSaving.RAM.Bill.pass Both computations are evaluated line 134

    Source documentation

    Both computations are evaluated.

    L4DEL explanation

    Both computations are evaluated.

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:130 (same declaration text).

    def pass (b : Bill α) (f : α → Bill β) : Bill β :=
    …

    Mentions: OAI.PowerSaving.RAM.Bill

  19. def OAI.PowerSaving.RAM.Bill.one line 138

    Also declared: OAI/Computability/FourierTransform/RAM.lean:134 (same declaration text).

  20. def OAI.PowerSaving.RAM.Bill.word line 139

    Also declared: OAI/Computability/FourierTransform/RAM.lean:135 (same declaration text).

  21. def OAI.PowerSaving.RAM.Bill.steps Execute f 0 through f (n-1), iterating an accumulator line 142

    Source documentation

    Execute f 0 through f (n-1), iterating an accumulator.

    L4DEL explanation

    Execute f 0 through f (n-1), iterating an accumulator.

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:138 (same declaration text).

    def steps (init : α) (f : ℕ → α → Bill α) : ℕ → Bill α
      | 0 => Bill.one init
      | i+1 => ((steps init f i).pass (f i)).pay 1 (i+1)
    
    /-- Build Tape len by count writes (initialized with a blank z). -/

    Mentions: OAI.PowerSaving.RAM.Bill, OAI.PowerSaving.RAM.Bill.one, OAI.PowerSaving.RAM.Bill.pass, OAI.PowerSaving.RAM.Bill.pay, OAI.PowerSaving.Tape

  22. def OAI.PowerSaving.RAM.Bill.sow Build Tape len by count writes (initialized with a blank z) line 147

    Source documentation

    Build Tape len by count writes (initialized with a blank z).

    L4DEL explanation

    Build Tape len by count writes (initialized with a blank z).

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:143 (same declaration text).

    def sow (len count : ℕ) (z : α) (f : ℕ → Bill (ℕ × α)) : Bill (Tape α) :=
    …

    Mentions: OAI.PowerSaving.RAM.Bill, OAI.PowerSaving.Tape

  23. def OAI.PowerSaving.RAM.Bill.tab Build Tape len line 152

    Source documentation

    Build Tape len. As for sow we can first allocate then perform writes.

    L4DEL explanation

    Build Tape len. As for sow we can first allocate then perform writes.

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:148 (same declaration text).

    def tab (len : ℕ) (z : α) (f : ℕ → Bill α) : Bill (Tape α) :=
    …

    Mentions: OAI.PowerSaving.RAM.Bill, OAI.PowerSaving.Tape

  24. inductive OAI.PowerSaving.RAM.NOp line 157

    Also declared: OAI/Computability/FourierTransform/RAM.lean:153 (same declaration text).

  25. inductive OAI.PowerSaving.RAM.Atom line 160

    Also declared: OAI/Computability/FourierTransform/RAM.lean:156 (same declaration text).

  26. def OAI.PowerSaving.RAM.NOp.run line 177

    Also declared: OAI/Computability/FourierTransform/RAM.lean:173 (same declaration text).

  27. def OAI.PowerSaving.RAM.Atom.run line 185

    Also declared: OAI/Computability/FourierTransform/RAM.lean:181 (same declaration text).

  28. abbrev OAI.PowerSaving.RAM.Port line 201

    Also declared: OAI/Computability/FourierTransform/RAM.lean:197 (same declaration text).

  29. inductive OAI.PowerSaving.RAM.Code call is internal for bounded recursion; a program has Port = none line 206

    Source documentation

    call is internal for bounded recursion; a program has Port = none. loop, tab and sow retain the input to access parameters in the body. descend sets up bounded recursion, reading fuel and initial argument.

    L4DEL explanation

    call is internal for bounded recursion; a program has Port = none. loop, tab and sow retain the input to access parameters in the body. descend sets up bounded recursion, reading fuel and initial argument.

    1. This explanation is a condensed rendering of the declaration's own doc comment at the pinned source commit; consult the exact Lean statement below for authority.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Also declared: OAI/Computability/FourierTransform/RAM.lean:202 (same declaration text).

    inductive Code (allow : Bool) : Port → Ty → Ty → Type
      | atom {r s t} (op : Atom allow s t) : Code allow r s t
      | comp {r s t u} (f : Code allow r s t) (g : Code allow r t u) : Code allow r s u
      | fork {r s t u} (f : Code allow r s t) (g : Code allow r s u) : Code allow r s (p t u)
      | ifz {r s t} (q : Code allow r s w) (f g : Code allow r s t) : Code allow r s t
      | loop {r s t} (n : Code allow r s w) (init : Code allow r s t)
          (body : Code allow r (p s (p w t)) t) : Code allow r s t
      | tab {r s t} (n : Code allow r s w)
          (body : Code allow r (p s w) t) : Code allow r s (a t)
      | sow {r s t} (n count : Code allow r s w)
          (body : Code allow r (p s w) (p w t)) : Code allow r s (a t)
      | importClosed {r s t} (f : Code allow none s t) : Code allow r s t
    …

    Mentions: OAI.PowerSaving.RAM.Port, OAI.PowerSaving.RAM.Ty, OAI.PowerSaving.RAM.Atom

  30. def OAI.PowerSaving.RAM.Handler line 222

    Also declared: OAI/Computability/FourierTransform/RAM.lean:218 (same declaration text).

  31. def OAI.PowerSaving.RAM.depthRun line 226

    Also declared: OAI/Computability/FourierTransform/RAM.lean:222 (same declaration text).

  32. def OAI.PowerSaving.RAM.Code.run line 231

    Also declared: OAI/Computability/FourierTransform/RAM.lean:227 (same declaration text).

  33. abbrev OAI.PowerSaving.RAM.Prog line 251

    Also declared: OAI/Computability/FourierTransform/RAM.lean:247 (same declaration text).

  34. abbrev OAI.PowerSaving.RAM.run line 253

    Also declared: OAI/Computability/FourierTransform/RAM.lean:249 (same declaration text).

  35. def OAI.PowerSaving.paperM line 264

    Also declared: OAI/Computability/FourierTransform/Goal.lean:25 (same declaration text).

  36. def OAI.PowerSaving.paperW line 265

    Also declared: OAI/Computability/FourierTransform/Goal.lean:26 (same declaration text).

  37. def OAI.PowerSaving.paperDelta line 266

    Also declared: OAI/Computability/FourierTransform/Goal.lean:27 (same declaration text).

  38. def OAI.PowerSaving.paperMultiplier line 267

    Also declared: OAI/Computability/FourierTransform/Goal.lean:28 (same declaration text).

  39. def OAI.PowerSaving.theta line 268

    Also declared: OAI/Computability/FourierTransform/Goal.lean:29 (same declaration text).

  40. def OAI.PowerSaving.decimalExponent line 269

    Also declared: OAI/Computability/FourierTransform/Goal.lean:30 (same declaration text).

  41. def OAI.PowerSaving.paperTime line 271

    Also declared: OAI/Computability/FourierTransform/Goal.lean:32 (same declaration text).

  42. def OAI.PowerSaving.decimalTime line 274

    Also declared: OAI/Computability/FourierTransform/Goal.lean:35 (same declaration text).

  43. def OAI.PowerSaving.nlogn line 276

    Also declared: OAI/Computability/FourierTransform/Goal.lean:37 (same declaration text).

  44. abbrev OAI.PowerSaving.root line 278

    Also declared: OAI/Computability/FourierTransform/Goal.lean:12 (same declaration text).

  45. abbrev OAI.PowerSaving.Vec line 280

    Also declared: OAI/Computability/FourierTransform/Goal.lean:14 (same declaration text).

  46. def OAI.PowerSaving.dft line 282

    Also declared: OAI/Computability/FourierTransform/Goal.lean:18 (same declaration text).

  47. def OAI.PowerSaving.conv line 285

    Also declared: OAI/Computability/FourierTransform/Goal.lean:21 (same declaration text).

  48. abbrev OAI.PowerSaving.dftInKind line 288

    Also declared: OAI/Computability/FourierTransform/Goal.lean:39 (same declaration text).

  49. abbrev OAI.PowerSaving.dftOutKind line 289

    Also declared: OAI/Computability/FourierTransform/Goal.lean:40 (same declaration text).

  50. abbrev OAI.PowerSaving.convInKind line 290

    Also declared: OAI/Computability/FourierTransform/Goal.lean:41 (same declaration text).

  51. abbrev OAI.PowerSaving.convOutKind line 291

    Also declared: OAI/Computability/FourierTransform/Goal.lean:42 (same declaration text).

  52. def OAI.PowerSaving.DFTProgram line 293

    Also declared: OAI/Computability/FourierTransform/Goal.lean:48 (same declaration text).

  53. def OAI.PowerSaving.ConvProgram line 305

    Also declared: OAI/Computability/FourierTransform/Goal.lean:62 (same declaration text).

  54. def OAI.PowerSaving.TimeBounds line 317

    Also declared: OAI/Computability/FourierTransform/Goal.lean:75 (same declaration text).

  55. def OAI.PowerSaving.DFTGoal line 321

    Also declared: OAI/Computability/FourierTransform/Goal.lean:79 (same declaration text).

  56. def OAI.PowerSaving.ConvGoal line 323

    Also declared: OAI/Computability/FourierTransform/Goal.lean:81 (same declaration text).

  57. theorem OAI.PowerSaving.transform_main Challenge statement: Uniform exact DFT and convolution with a power saving sorry line 326

    Source documentation

    One fixed program computes every positive-length canonical DFT, including preparation.

    L4DEL explanation

    One fixed program computes every positive-length canonical DFT, including preparation.

    1. This explanation is a condensed rendering of this declaration's own doc comment at the pinned source commit.
    2. The linked formalization note covers 2 distinct comparator results, so its combined Scope prose is not copied onto this declaration.
    3. The repository's comparator configuration selects OAI.Computability.FourierTransform.Main as the released solution module checked against this declaration.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Distinct definitions of this name: OAI/Computability/FourierTransform/Main.lean:137 (same statement text; different proof or body). Qualify references as OAI.PowerSaving.transform_main@path.

    theorem transform_main : DFTGoal := by
    …

    Mentions: OAI.PowerSaving.DFTGoal

  58. theorem OAI.PowerSaving.convolution_main Challenge statement: Uniform exact DFT and convolution with a power saving sorry line 330

    Source documentation

    One fixed bilinear program computes convolution with the same asymptotic bounds.

    L4DEL explanation

    One fixed bilinear program computes convolution with the same asymptotic bounds.

    1. This explanation is a condensed rendering of this declaration's own doc comment at the pinned source commit.
    2. The linked formalization note covers 2 distinct comparator results, so its combined Scope prose is not copied onto this declaration.
    3. The repository's comparator configuration selects OAI.Computability.FourierTransform.Main as the released solution module checked against this declaration.

    Sources and attribution: Pinned Lean source (fd4aeeb2ee4f)

    Distinct definitions of this name: OAI/Computability/FourierTransform/Main.lean:141 (same statement text; different proof or body). Qualify references as OAI.PowerSaving.convolution_main@path.

    theorem convolution_main : ConvGoal := by
    …

    Mentions: OAI.PowerSaving.ConvGoal