degreeSpace
For a commutative ring K, a finite type ι with decidable equality, and a natural number d, degreeSpace K ι d is the K-submodule of (ι → Bool) → K spanned by the set of functions f : (ι → Bool) → K for which there exists a finite subset S : Finset ι with S.card ≤ d such that f x = ∏ i ∈ S, if x i then (1 : K) else 0.
Statement
def degreeSpace (K : Type*) [CommRing K] (ι : Type*) [Fintype ι] [DecidableEq ι] (d : ℕ) : Submodule K ((ι → Bool) → K)
- Defined in
- arXiv:2610.19174, Section 2 and Listing A.1
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Used by 10
- hasTorusApproximation_of_hasRationalTorusApproximationFor any Boolean function f on n variables, natural degree d, and error ε, if f has a rational torus approximation of degree d with error…
- explicitApproximant_mem_degreeSpaceFor any Boolean function f : (Fin n → Bool) → Bool on n > 0 variables, the explicit approximant P_f belongs to degreeSpace (K := ℝ) (Fin…
- IsNondetPolynomialA real-valued function p on the Boolean hypercube (Fin n → Bool) is a non-deterministic polynomial for a Boolean function f of degree at…
- HasRealApproximationFor a Boolean function f : (Fin n → Bool) → Bool, natural number d, and real error ε, HasRealApproximation f d ε asserts the existence of…
- op_729_case_n_twoFor every Boolean function f : (Fin 2 → Bool) → Bool on 2 variables, optimalTorusError f 0 = predictedTorusError 2 f and…
- HasTorusApproximationFor a Boolean function f : (Fin n → Bool) → Bool, natural number d, and real error ε, HasTorusApproximation f d ε asserts the existence of…
- HasRationalTorusApproximationFor a Boolean function f : (Fin n → Bool) → Bool on n variables, natural degree d, and error ε : ℝ, HasRationalTorusApproximation f d ε…
- ternary_lift_realApproxDegree_leSuppose n, d : ℕ with 40 ≤ n. If f : (Fin n → Bool) → Bool, P : (Fin n → Bool) → ℝ is in degreeSpace ℝ (Fin n) d, and Z : (Fin n → Bool) →…
- op_729_and3_has_rational_torus_approximationThe 3-variable conjunction function on Fin 3 → Bool has a degree 1 rational torus approximation with error 1/6:…
- ndeg_le_nFor any natural number n and any Boolean function f : (Fin n → Bool) → Bool, the non-deterministic degree of f is at most n.
Read back from the Lean
degreeSpace K ι d is defined, for a commutative ring K, a finite type ι with decidable equality, and a natural number d, as the K-submodule of functions (ι → Bool) → K spanned by the set of all functions f for which there exists a finite subset S : Finset ι with cardinality card S ≤ d such that f equals the function mapping each x : ι → Bool to the product over i ∈ S of if x i then 1 else 0 (in K).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The submodule of functions on the Boolean cube represented by multilinear polynomials of degree at most d. -/ def degreeSpace (K : Type*) [CommRing K] (ι : Type*) [Fintype ι] [DecidableEq ι] (d : ℕ) : Submodule K ((ι → Bool) → K) := Submodule.span K { f | ∃ (S : Finset ι), S.card ≤ d ∧ f = fun x => ∏ i ∈ S, if x i then (1 : K) else 0 }