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