AFTD Auto-Formalizing Theoretical Domains

degreeSpace

def

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 }
See it in the graphDiscuss this resultChallenge it