AFTD Auto-Formalizing Theoretical Domains

IsNondetPolynomial

def

A real-valued function p on the Boolean hypercube (Fin n → Bool) is a non-deterministic polynomial for a Boolean function f of degree at most d if p belongs to degreeSpace ℝ (Fin n) d and for all x : Fin n → Bool, p x ≠ 0 if and only if f x = true.

Statement

def IsNondetPolynomial {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) (p : (Fin n → Bool) → ℝ) : Prop
Defined in
arXiv:2611.11966 Def 11
Verified
11 Nov 2026
Axioms
none listed
Built on 1
  • degreeSpaceFor a commutative ring K, a finite type ι with decidable equality, and a natural number d, degreeSpace K ι d is the K-submodule of (ι →…
Used by 2
  • 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.
  • HasNondetPolyA Boolean function f : (Fin n → Bool) → Bool admits a non-deterministic polynomial of degree at most d if there exists a polynomial p :…

Read back from the Lean

Given a natural number n, a Boolean function f : (Fin n → Bool) → Bool, a natural number d, and a function p : (Fin n → Bool) → ℝ, IsNondetPolynomial f d p asserts that: 1. p belongs to degreeSpace ℝ (Fin n) d (the ℝ-submodule spanned by monomials of degree at most d), and 2. for all inputs x : Fin n → Bool, p x ≠ 0 if and only if f x = true.

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

/-- A real function p is a non-deterministic polynomial for f of degree at most d. -/
def IsNondetPolynomial {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) (p : (Fin n → Bool) → ℝ) : Prop := p ∈ degreeSpace ℝ (Fin n) d ∧ ∀ x, p x ≠ 0 ↔ f x = true
See it in the graphDiscuss this resultChallenge it