ndeg_le_n
For any natural number n and any Boolean function f : (Fin n → Bool) → Bool, the non-deterministic degree of f is at most n.
Statement
theorem ndeg_le_n (n : ℕ) (f : (Fin n → Bool) → Bool) : ndeg f ≤ n- Formalizes
- arXiv:2611.11966 Prop 22
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- ndegThe non-deterministic degree ndeg f of a Boolean function f : (Fin n → Bool) → Bool is the minimal natural number d such that f admits a…
- HasNondetPolyA Boolean function f : (Fin n → Bool) → Bool admits a non-deterministic polynomial of degree at most d if there exists a polynomial p :…
- 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…
- fullMonomialThe full monomial x_[n] = ∏_{i=1}^n x_i evaluated at a point in {0,1}^n.
- 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…
- degreeSpaceFor a commutative ring K, a finite type ι with decidable equality, and a natural number d, degreeSpace K ι d is the K-submodule of (ι →…
- topCoefficientFor an implicit natural number n and a Boolean-valued function f : (Fin n → Bool) → Bool, topCoefficient f is the integer defined by the…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
For every natural number $n$ and every Boolean function $f : (\text{Fin } n \to \text{Bool}) \to \text{Bool}$, the nondeterministic degree of $f$ (denoted $\text{ndeg } f$) is less than or equal to $n$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To prove that any Boolean function f on n variables has non-deterministic degree at most n, the proof explicitly constructs the indicator function x ↦ 1_{f(x)=true} as a non-deterministic polynomial for f of degree at most n. The non-zero condition p(x) ≠ 0 ↔ f(x) = true is immediate from the definition of the indicator. For the degree bound, when n > 0, the indicator is decomposed into the top-degree monomial scaled by the top Fourier coefficient plus an (n - 1)-degree remainder; when n = 0, the domain consists of a single point, so the indicator is either the constant 1 or 0 function (both of degree 0). Since the non-deterministic degree is defined as the infimum of valid polynomial degrees, exhibiting a degree-n witness shows ndeg f ≤ n.
Propose the indicator function of f as a candidate non-deterministic polynomial of degree n, reducing the goal to a degree bound and a non-zero equivalence.
The witness candidate is the indicator function x ↦ if f x = true then 1 else 0. By definition, being a non-deterministic polynomial of degree n means belonging to degreeSpace ℝ (Fin n) n and satisfying p x ≠ 0 ↔ f x = true for all x. Applying constructor separates these two requirements into distinct subgoals.
use fun x => if f x = true then (1 : ℝ) else 0 constructor
For n > 0, the indicator function minus its top-degree monomial term belongs to degreeSpace ℝ (Fin n) n.
Assuming 0 < n, lemma explicitApproximant_function_sub_top_mem shows that subtracting the full monomial scaled by the top coefficient from the indicator function yields an element of degreeSpace ℝ (Fin n) (n - 1). Since n - 1 ≤ n by Nat.sub_le, monotonicity of span (Submodule.span_mono) implies degreeSpace ℝ (Fin n) (n - 1) ≤ degreeSpace ℝ (Fin n) n, so this difference belongs to degreeSpace ℝ (Fin n) n.
uses
explicitApproximant_function_sub_top_mem,Submodule.span_mono,Nat.sub_le· by_cases hn : 0 < n · have h1 : (fun x => (if f x = true then 1 else 0) - (topCoefficient f : ℝ) * fullMonomial x) ∈ degreeSpace ℝ (Fin n) (n - 1) := explicitApproximant_function_sub_top_mem hn f have hmono : degreeSpace ℝ (Fin n) (n - 1) ≤ degreeSpace ℝ (Fin n) n := by apply Submodule.span_mono rintro g ⟨S, hS, rfl⟩ exact ⟨S, hS.trans (Nat.sub_le n 1), rfl⟩ have h1' := hmono h1
The top-degree monomial term, and its sum with the lower-degree difference, belong to degreeSpace ℝ (Fin n) n.
The full monomial corresponds to the product over all n variables (Finset.univ), which has cardinality n ≤ n, so by Submodule.subset_span it belongs to degreeSpace ℝ (Fin n) n. By Submodule.smul_mem, scaling it by the real top coefficient leaves it in the submodule. By Submodule.add_mem, adding this term to the lower-degree difference from the previous step yields an element of degreeSpace ℝ (Fin n) n.
uses
Submodule.subset_span,Submodule.smul_mem,Submodule.add_memhave h2 : (fullMonomial : (Fin n → Bool) → ℝ) ∈ degreeSpace ℝ (Fin n) n := by apply Submodule.subset_span exact ⟨Finset.univ, by simp, rfl⟩ have h3 : ((topCoefficient f : ℝ) • (fullMonomial : (Fin n → Bool) → ℝ)) ∈ degreeSpace ℝ (Fin n) n := Submodule.smul_mem _ _ h2 have hsum := Submodule.add_mem _ h1' h3
The indicator function is identically equal to the sum of the difference and the top term, completing the case n > 0.
For any input x, ring arithmetic confirms that (p(x) - c * M(x)) + c * M(x) = p(x). Rewriting with this identity shows that the indicator function equals the sum from the previous step, establishing that it belongs to degreeSpace ℝ (Fin n) n.
have heq : (fun x => if f x = true then (1 : ℝ) else 0) = (fun x => (if f x = true then 1 else 0) - (topCoefficient f : ℝ) * fullMonomial x) + ((topCoefficient f : ℝ) • (fullMonomial : (Fin n → Bool) → ℝ)) := by ext x dsimp ring rw [heq] exact hsum
When n = 0, the constant function 1 belongs to degreeSpace ℝ (Fin 0) 0.
When ¬(0 < n), omega gives n = 0. On Fin 0 → Bool, the constant function 1 corresponds to the empty product (S = ∅), which has size 0 ≤ 0. Thus Submodule.subset_span places it in degreeSpace ℝ (Fin 0) 0.
uses
Submodule.subset_span· have hn0 : n = 0 := by omega subst hn0 have hone : (fun (_ : Fin 0 → Bool) => (1 : ℝ)) ∈ degreeSpace ℝ (Fin 0) 0 := by apply Submodule.subset_span refine ⟨∅, by simp, ?_⟩ ext x simp
When n = 0 and f evaluates to true on the empty input, the indicator function belongs to degreeSpace ℝ (Fin 0) 0.
Because any index in Fin 0 is eliminated by Fin.elim0, every input x : Fin 0 → Bool equals the unique empty assignment fun _ => false. When f evaluates to true on this assignment, f x = true for all x, so the indicator function is identically the constant function 1, which lies in degreeSpace ℝ (Fin 0) 0.
uses
Fin.elim0by_cases h : f (fun _ => false) = true · have heq : (fun x => if f x = true then (1 : ℝ) else 0) = (fun _ => 1) := by ext x have hx : x = (fun _ => false) := by ext i exact Fin.elim0 i rw [hx, h] simp rw [heq] exact hone
When n = 0 and f evaluates to false on the empty input, the indicator function belongs to degreeSpace ℝ (Fin 0) 0.
Every input x again equals the empty assignment by Fin.elim0. When f does not evaluate to true on the empty input, a boolean case split shows f x = false for all x. Thus the indicator function is identically 0, which belongs to degreeSpace ℝ (Fin 0) 0 by Submodule.zero_mem.
uses
Fin.elim0,Submodule.zero_mem· have heq : (fun x => if f x = true then (1 : ℝ) else 0) = 0 := by ext x have hx : x = (fun _ => false) := by ext i exact Fin.elim0 i rw [hx] have : f (fun _ => false) = false := by revert h cases f (fun _ => false) <;> simp rw [this] simp rw [heq] exact Submodule.zero_mem _
The indicator function is non-zero if and only if f x = true, for all inputs x.
For any input x, if f x = true then the indicator function evaluates to 1 ≠ 0; if f x = false then it evaluates to 0, which is not non-zero. Hence p x ≠ 0 ↔ f x = true holds in both cases.
· intro x by_cases hx : f x = true <;> simp [hx]
The non-deterministic degree of f is at most n.
Lemma ndeg_le_n_hasNondetPoly proves that f has a non-deterministic polynomial of degree n, so n belongs to the set {d | HasNondetPoly f d}. The non-deterministic degree ndeg f is the infimum of this set, so Nat.sInf_le implies ndeg f ≤ n.
uses
ndeg_le_n_hasNondetPoly,Nat.sInf_lehave h : HasNondetPoly f n := ndeg_le_n_hasNondetPoly n f exact Nat.sInf_le h
explicitApproximant_function_sub_top_mem- For any Boolean function f on n > 0 variables, subtracting the full monomial scaled by its top coefficient from the indicator function of f yields a function of degree at most n - 1.
Submodule.span_mono- Linear span is order-preserving: if a set s is contained in a set t, then the submodule spanned by s is contained in the submodule spanned by t.
Nat.sub_le- For any natural numbers n and m, n - m ≤ n.
Submodule.subset_span- Every element of a set s belongs to the submodule spanned by s.
Submodule.smul_mem- A submodule is closed under scalar multiplication.
Submodule.add_mem- A submodule is closed under addition.
Fin.elim0- The type Fin 0 is empty, so any element of Fin 0 yields a contradiction (principle of explosion).
Submodule.zero_mem- The zero element belongs to every submodule.
ndeg_le_n_hasNondetPoly- Every Boolean function on n variables has a non-deterministic polynomial of degree at most n.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element in that set.
- The degreeSpace definition represents polynomials as functions (Fin n → Bool) → ℝ lying in the linear span of products of input bits, rather than formal polynomials.
- For the n = 0 case, the domain Fin 0 → Bool has exactly one element; Lean verifies this uniqueness using Fin.elim0 to rule out any coordinates, reducing f to either constant true or constant false.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma ndeg_le_n_hasNondetPoly (n : ℕ) (f : (Fin n → Bool) → Bool) : HasNondetPoly f n := by use fun x => if f x = true then (1 : ℝ) else 0 constructor · by_cases hn : 0 < n · have h1 : (fun x => (if f x = true then 1 else 0) - (topCoefficient f : ℝ) * fullMonomial x) ∈ degreeSpace ℝ (Fin n) (n - 1) := explicitApproximant_function_sub_top_mem hn f have hmono : degreeSpace ℝ (Fin n) (n - 1) ≤ degreeSpace ℝ (Fin n) n := by apply Submodule.span_mono rintro g ⟨S, hS, rfl⟩ exact ⟨S, hS.trans (Nat.sub_le n 1), rfl⟩ have h1' := hmono h1 have h2 : (fullMonomial : (Fin n → Bool) → ℝ) ∈ degreeSpace ℝ (Fin n) n := by apply Submodule.subset_span exact ⟨Finset.univ, by simp, rfl⟩ have h3 : ((topCoefficient f : ℝ) • (fullMonomial : (Fin n → Bool) → ℝ)) ∈ degreeSpace ℝ (Fin n) n := Submodule.smul_mem _ _ h2 have hsum := Submodule.add_mem _ h1' h3 have heq : (fun x => if f x = true then (1 : ℝ) else 0) = (fun x => (if f x = true then 1 else 0) - (topCoefficient f : ℝ) * fullMonomial x) + ((topCoefficient f : ℝ) • (fullMonomial : (Fin n → Bool) → ℝ)) := by ext x dsimp ring rw [heq] exact hsum · have hn0 : n = 0 := by omega subst hn0 have hone : (fun (_ : Fin 0 → Bool) => (1 : ℝ)) ∈ degreeSpace ℝ (Fin 0) 0 := by apply Submodule.subset_span refine ⟨∅, by simp, ?_⟩ ext x simp by_cases h : f (fun _ => false) = true · have heq : (fun x => if f x = true then (1 : ℝ) else 0) = (fun _ => 1) := by ext x have hx : x = (fun _ => false) := by ext i exact Fin.elim0 i rw [hx, h] simp rw [heq] exact hone · have heq : (fun x => if f x = true then (1 : ℝ) else 0) = 0 := by ext x have hx : x = (fun _ => false) := by ext i exact Fin.elim0 i rw [hx] have : f (fun _ => false) = false := by revert h cases f (fun _ => false) <;> simp rw [this] simp rw [heq] exact Submodule.zero_mem _ · intro x by_cases hx : f x = true <;> simp [hx]/-- Every Boolean function on n variables has non-deterministic degree at most n. -/theorem ndeg_le_n (n : ℕ) (f : (Fin n → Bool) → Bool) : ndeg f ≤ n := by have h : HasNondetPoly f n := ndeg_le_n_hasNondetPoly n f exact Nat.sInf_le h