ComparatorChallenges/UniformFourier.lean
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.
- def
OAI.ExactFourier.zetaline 6Also declared: ComparatorChallenges/ExactFourier.lean:44 (same declaration text), OAI/Computability/FourierCircuit/Core.lean:40 (same declaration text).
- structure
OAI.PowerSaving.TapeRegister arrays line 51Source documentation
Register arrays.
L4DEL explanation
Register arrays.
- 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 …
- def
OAI.PowerSaving.Tape.emptyline 57Also declared: OAI/Computability/FourierTransform/RAM.lean:53 (same declaration text).
- def
OAI.PowerSaving.Tape.tabMaterialized array line 60Source documentation
Materialized array.
L4DEL explanation
Materialized array.
- 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
- def
OAI.PowerSaving.Tape.lookRead with fixed out of bounds default line 63Source documentation
Read with fixed out of bounds default.
L4DEL explanation
Read with fixed out of bounds default.
- 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
- theorem
OAI.PowerSaving.Tape.look_of_ltline 66Also declared: OAI/Computability/FourierTransform/RAM.lean:62 (same declaration text).
- theorem
OAI.PowerSaving.Tape.look_of_leline 69Also declared: OAI/Computability/FourierTransform/RAM.lean:65 (same declaration text).
- def
OAI.PowerSaving.Tape.setSemantics of a write into fresh storage; out-of-range writes are ignored line 74Source 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.
- 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
- def
OAI.PowerSaving.Tape.sowline 77Also declared: OAI/Computability/FourierTransform/RAM.lean:73 (same declaration text).
- def
OAI.PowerSaving.Tape.mapline 84Also declared: OAI/Computability/FourierTransform/RAM.lean:80 (same declaration text).
- inductive
OAI.PowerSaving.RAM.Paintline 90Also declared: OAI/Computability/FourierTransform/RAM.lean:86 (same declaration text).
- inductive
OAI.PowerSaving.RAM.Tyline 96Also declared: OAI/Computability/FourierTransform/RAM.lean:92 (same declaration text).
- abbrev
OAI.PowerSaving.RAM.scline 104Also declared: OAI/Computability/FourierTransform/RAM.lean:100 (same declaration text).
- def
OAI.PowerSaving.RAM.Ty.Tline 106Also declared: OAI/Computability/FourierTransform/RAM.lean:102 (same declaration text).
- def
OAI.PowerSaving.RAM.Ty.blankline 112Also declared: OAI/Computability/FourierTransform/RAM.lean:108 (same declaration text).
- structure
OAI.PowerSaving.RAM.BillOne basic work unit below pays for O(1) primitive RAM operations; includes loop and stack overhead line 121Source documentation
One basic work unit below pays for O(1) primitive RAM operations; includes loop and stack overhead.
peaktracks 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.
peaktracks produced/needed integer quantities beyond inputs (total allocation for stack and array bases is covered separately by work).- 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 …
- def
OAI.PowerSaving.RAM.Bill.payCharge some work and optionally a new word bound line 130Source documentation
Charge some work and optionally a new word bound.
L4DEL explanation
Charge some work and optionally a new word bound.
- 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
- def
OAI.PowerSaving.RAM.Bill.passBoth computations are evaluated line 134Source documentation
Both computations are evaluated.
L4DEL explanation
Both computations are evaluated.
- 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
- def
OAI.PowerSaving.RAM.Bill.oneline 138Also declared: OAI/Computability/FourierTransform/RAM.lean:134 (same declaration text).
- def
OAI.PowerSaving.RAM.Bill.wordline 139Also declared: OAI/Computability/FourierTransform/RAM.lean:135 (same declaration text).
- def
OAI.PowerSaving.RAM.Bill.stepsExecute f 0 through f (n-1), iterating an accumulator line 142Source documentation
Execute f 0 through f (n-1), iterating an accumulator.
L4DEL explanation
Execute f 0 through f (n-1), iterating an accumulator.
- 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
- def
OAI.PowerSaving.RAM.Bill.sowBuild Tape len by count writes (initialized with a blank z) line 147Source 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).
- 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
- def
OAI.PowerSaving.RAM.Bill.tabBuild Tape len line 152Source 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.
- 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
- inductive
OAI.PowerSaving.RAM.NOpline 157Also declared: OAI/Computability/FourierTransform/RAM.lean:153 (same declaration text).
- inductive
OAI.PowerSaving.RAM.Atomline 160Also declared: OAI/Computability/FourierTransform/RAM.lean:156 (same declaration text).
- def
OAI.PowerSaving.RAM.NOp.runline 177Also declared: OAI/Computability/FourierTransform/RAM.lean:173 (same declaration text).
- def
OAI.PowerSaving.RAM.Atom.runline 185Also declared: OAI/Computability/FourierTransform/RAM.lean:181 (same declaration text).
- abbrev
OAI.PowerSaving.RAM.Portline 201Also declared: OAI/Computability/FourierTransform/RAM.lean:197 (same declaration text).
- inductive
OAI.PowerSaving.RAM.Codecallis internal for bounded recursion; a program has Port = none line 206Source documentation
callis internal for bounded recursion; a program has Port = none.loop,tabandsowretain the input to access parameters in the body.descendsets up bounded recursion, reading fuel and initial argument.L4DEL explanation
callis internal for bounded recursion; a program has Port = none.loop,tabandsowretain the input to access parameters in the body.descendsets up bounded recursion, reading fuel and initial argument.- 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
- def
OAI.PowerSaving.RAM.Handlerline 222Also declared: OAI/Computability/FourierTransform/RAM.lean:218 (same declaration text).
- def
OAI.PowerSaving.RAM.depthRunline 226Also declared: OAI/Computability/FourierTransform/RAM.lean:222 (same declaration text).
- def
OAI.PowerSaving.RAM.Code.runline 231Also declared: OAI/Computability/FourierTransform/RAM.lean:227 (same declaration text).
- abbrev
OAI.PowerSaving.RAM.Progline 251Also declared: OAI/Computability/FourierTransform/RAM.lean:247 (same declaration text).
- abbrev
OAI.PowerSaving.RAM.runline 253Also declared: OAI/Computability/FourierTransform/RAM.lean:249 (same declaration text).
- def
OAI.PowerSaving.paperMline 264Also declared: OAI/Computability/FourierTransform/Goal.lean:25 (same declaration text).
- def
OAI.PowerSaving.paperWline 265Also declared: OAI/Computability/FourierTransform/Goal.lean:26 (same declaration text).
- def
OAI.PowerSaving.paperDeltaline 266Also declared: OAI/Computability/FourierTransform/Goal.lean:27 (same declaration text).
- def
OAI.PowerSaving.paperMultiplierline 267Also declared: OAI/Computability/FourierTransform/Goal.lean:28 (same declaration text).
- def
OAI.PowerSaving.thetaline 268Also declared: OAI/Computability/FourierTransform/Goal.lean:29 (same declaration text).
- def
OAI.PowerSaving.decimalExponentline 269Also declared: OAI/Computability/FourierTransform/Goal.lean:30 (same declaration text).
- def
OAI.PowerSaving.paperTimeline 271Also declared: OAI/Computability/FourierTransform/Goal.lean:32 (same declaration text).
- def
OAI.PowerSaving.decimalTimeline 274Also declared: OAI/Computability/FourierTransform/Goal.lean:35 (same declaration text).
- def
OAI.PowerSaving.nlognline 276Also declared: OAI/Computability/FourierTransform/Goal.lean:37 (same declaration text).
- abbrev
OAI.PowerSaving.rootline 278Also declared: OAI/Computability/FourierTransform/Goal.lean:12 (same declaration text).
- abbrev
OAI.PowerSaving.Vecline 280Also declared: OAI/Computability/FourierTransform/Goal.lean:14 (same declaration text).
- def
OAI.PowerSaving.dftline 282Also declared: OAI/Computability/FourierTransform/Goal.lean:18 (same declaration text).
- def
OAI.PowerSaving.convline 285Also declared: OAI/Computability/FourierTransform/Goal.lean:21 (same declaration text).
- abbrev
OAI.PowerSaving.dftInKindline 288Also declared: OAI/Computability/FourierTransform/Goal.lean:39 (same declaration text).
- abbrev
OAI.PowerSaving.dftOutKindline 289Also declared: OAI/Computability/FourierTransform/Goal.lean:40 (same declaration text).
- abbrev
OAI.PowerSaving.convInKindline 290Also declared: OAI/Computability/FourierTransform/Goal.lean:41 (same declaration text).
- abbrev
OAI.PowerSaving.convOutKindline 291Also declared: OAI/Computability/FourierTransform/Goal.lean:42 (same declaration text).
- def
OAI.PowerSaving.DFTProgramline 293Also declared: OAI/Computability/FourierTransform/Goal.lean:48 (same declaration text).
- def
OAI.PowerSaving.ConvProgramline 305Also declared: OAI/Computability/FourierTransform/Goal.lean:62 (same declaration text).
- def
OAI.PowerSaving.TimeBoundsline 317Also declared: OAI/Computability/FourierTransform/Goal.lean:75 (same declaration text).
- def
OAI.PowerSaving.DFTGoalline 321Also declared: OAI/Computability/FourierTransform/Goal.lean:79 (same declaration text).
- def
OAI.PowerSaving.ConvGoalline 323Also declared: OAI/Computability/FourierTransform/Goal.lean:81 (same declaration text).
- theorem
OAI.PowerSaving.transform_mainChallenge statement: Uniform exact DFT and convolution with a power saving sorry line 326Source 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.
- This explanation is a condensed rendering of this declaration's own doc comment at the pinned source commit.
- The linked formalization note covers 2 distinct comparator results, so its combined Scope prose is not copied onto this declaration.
- 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
- theorem
OAI.PowerSaving.convolution_mainChallenge statement: Uniform exact DFT and convolution with a power saving sorry line 330Source 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.
- This explanation is a condensed rendering of this declaration's own doc comment at the pinned source commit.
- The linked formalization note covers 2 distinct comparator results, so its combined Scope prose is not copied onto this declaration.
- 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