AFTD Auto-Formalizing Theoretical Domains

ndeg_le_n

theoremverifiedformalization

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.

  1. 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.

    lines 2–3

      use fun x => if f x = true then (1 : ℝ) else 0
      constructor
  2. 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.

    lines 4–11

    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
  3. 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.

    lines 12–17

    uses Submodule.subset_span, Submodule.smul_mem, Submodule.add_mem

          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
  4. 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.

    lines 18–25

          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
  5. 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.

    lines 26–32

    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
  6. 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.

    lines 33–42

    uses Fin.elim0

          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
  7. 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.

    lines 43–55

    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 _
  8. 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.

    lines 56–57

      · intro x
        by_cases hx : f x = true <;> simp [hx]
  9. 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.

    lines 61–62

    uses ndeg_le_n_hasNondetPoly, Nat.sInf_le

      have 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.

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

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