AFTD Auto-Formalizing Theoretical Domains

not_boolean_subspace_degree_reduction_criterion

theoremverifiedoriginal

The statement boolean_subspace_degree_reduction_criterion is false: The statement is false for d = 0. When d = 0: Let n = 1, p : (Fin 1 → ZMod 2) → ZMod 2 be the constant 1 function, and U = ⊥. 1. booleanDegree p = 0, because the ANF coefficient for S = ∅ is p(0) = 1 ≠ 0, while for S = {0} the sum is p(0) + p(1) = 2 = 0 in ZMod 2. Thus hp : booleanDegree p = 0 holds. 2. For U = ⊥, Module.finrank (ZMod 2) ↥⊥ = 0. Any function on Fin 0 → ZMod 2 has booleanDegree ≤ 0. In Lean's natural number arithmetic, d - 1 = 0 - 1 = 0. Thus booleanDegree (booleanAffineRestriction p a ⊥) ≤ 0 - 1 holds for all a, so the RHS of the equivalence is TRUE. 3. The LHS states that booleanTopForm 0 p u = 0 for all u : Fin 0 → (Fin 1 → ZMod 2). But by definition, booleanTopForm 0 p u = ∑ S : Finset (Fin 0), p (∑ i ∈ S, u i) = p(0) = 1 ≠ 0. Thus the LHS is FALSE. Since LHS is false and RHS is true, the equivalence fails.

Statement

theorem not_boolean_subspace_degree_reduction_criterion : ¬ (∀ {n d : ℕ}
    (p : (Fin n → ZMod 2) → ZMod 2) (hp : booleanDegree p = d)
    (U : Submodule (ZMod 2) (Fin n → ZMod 2)), (∀ u : Fin d → (Fin n → ZMod 2), (∀ i, u i ∈ U) → booleanTopForm d p u = 0) ↔
      (∀ a : Fin n → ZMod 2, booleanDegree (booleanAffineRestriction p a U) ≤ d - 1))
Related work
refutes `boolean_subspace_degree_reduction_criterion`
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • booleanTopFormGiven a type V with an additive commutative group structure [AddCommGroup V], a natural number d, a function p : V → ZMod 2, and a tuple h…
  • booleanDegreeThe degree of a Boolean function p : (Fin n → ZMod 2) → ZMod 2 is the maximum cardinality of a subset S of coordinates such that the…
  • booleanAffineRestrictionThe restriction of a Boolean function p to an affine subspace a + U is the function on Fin (dim U) → ZMod 2 obtained by evaluating p at a…

The proof, explained

The claimed criterion is disproved by an explicit counterexample at target degree $d = 0$. For the constant function $p \equiv 1$ on $\mathbb{F}_2^1$ ($n=1$) and the zero submodule $U = \bot$, the Boolean degree is $d = 0$. Because $\dim U = 0$, every affine restriction to $U$ has degree at most 0, which satisfies the condition $\le 0 - 1 = 0$ in natural number arithmetic, making the right-hand side hold. However, the degree-0 top form on the empty tuple of vectors evaluates to $p(0) = 1 \neq 0$, so the left-hand side fails, refuting the equivalence.

  1. Assume, for the sake of contradiction, that the proposed equivalence holds in general.

    We introduce the hypothesis h representing the universal statement: for all dimensions $n$, degrees $d$, functions $p$ with booleanDegree $p = d$, and submodules $U$, the top-form vanishing condition on $U$ is equivalent to the affine restrictions to $U$ having degree at most $d - 1$.

    line 5

      intro h
  2. The constant function $p \equiv 1$ on $\mathrm{Fin}\,1 \to \mathbb{Z}_2$ has Boolean degree 0.

    By definition, the Boolean degree is the maximum cardinality of a subset $S \subseteq \mathrm{Fin}\,1$ whose algebraic normal form coefficient is non-zero. For any subset $S$ with $|S| \ge 1$, the only possibility in $\mathrm{Fin}\,1$ is $S = \mathrm{univ}$. The corresponding coefficient is the sum of $p(x) = 1$ over all $2^1 = 2$ inputs, which vanishes in $\mathbb{Z}_2$ because $2 = 0$. Hence no subset of size $\ge 1$ has a non-zero coefficient, bounding the degree above by 0; since degrees are non-negative, the degree equals 0.

    lines 6–30

    uses le_antisymm, Finset.sup_le, Finset.mem_filter, Finset.mem_univ, true_and, Finset.card_le_univ, Fintype.card_fin, Finset.card_eq_iff_eq_univ, Finset.sum_const, Finset.card_univ, Fintype.card_fun, ZMod.card, nsmul_eq_mul, mul_one, Nat.zero_le

      have test_deg : booleanDegree (fun (_ : Fin 1 → ZMod 2) => (1 : ZMod 2)) = 0 := by
        dsimp [booleanDegree]
        apply le_antisymm
        · apply Finset.sup_le
          intro S hS
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hS
          by_contra hc
          have hS_card : S.card = 1 := by
            have := Finset.card_le_univ S
            simp only [Fintype.card_fin] at this
            omega
          have hS_univ : S = Finset.univ := by
            rw [← Finset.card_eq_iff_eq_univ]
            rw [Fintype.card_fin]
            exact hS_card
          subst hS_univ
          have h_sum : (∑ x ∈ Finset.univ.filter (fun (x : Fin 1 → ZMod 2) => ∀ i, x i ≠ 0 → i ∈ (Finset.univ : Finset (Fin 1))), (1 : ZMod 2)) = 0 := by
            have : (Finset.univ.filter (fun (x : Fin 1 → ZMod 2) => ∀ i, x i ≠ 0 → i ∈ (Finset.univ : Finset (Fin 1)))) = Finset.univ := by
              ext x; simp
            rw [this]
            simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fun, Fintype.card_fin,
              ZMod.card, nsmul_eq_mul, mul_one]
            rfl
          exact hS h_sum
        · exact Nat.zero_le _
  3. Any Boolean function on $k$ variables has Boolean degree at most $k$.

    The Boolean degree is the supremum of the cardinalities $|S|$ of subsets $S \subseteq \mathrm{Fin}\,k$ having non-zero coefficients. Because every subset of $\mathrm{Fin}\,k$ has cardinality at most $|\mathrm{Fin}\,k| = k$, the supremum is bounded by $k$.

    lines 31–38

    uses Finset.sup_le, Finset.card_le_univ, Fintype.card_fin

      have q_deg : ∀ (k : ℕ) (f : (Fin k → ZMod 2) → ZMod 2), booleanDegree f ≤ k := by
        intro k f
        dsimp [booleanDegree]
        apply Finset.sup_le
        intro S _
        have := Finset.card_le_univ S
        simp only [Fintype.card_fin] at this
        exact this
  4. Specializing to $n = 1$, $d = 0$, $p \equiv 1$, and $U = \bot$, the right-hand condition of the equivalence holds.

    We instantiate the universal hypothesis h with $n = 1$, $d = 0$, the constant function $p \equiv 1$, and the trivial submodule $\bot$. The submodule $\bot$ has dimension 0 by finrank_bot, so any affine restriction to $\bot$ is a function on $\mathrm{Fin}\,0 \to \mathbb{Z}_2$, whose degree is at most 0 by our general bound. Because natural number subtraction satisfies $0 - 1 = 0$, the degree bound $\le 0 - 1$ holds.

    lines 39–45

    uses finrank_bot

      have h_spec := @h 1 0 (fun _ => 1) test_deg ⊥
      have h_rhs : ∀ a : Fin 1 → ZMod 2, booleanDegree (booleanAffineRestriction (fun _ => 1) a ⊥) ≤ 0 - 1 := by
        intro a
        have h_deg := q_deg (Module.finrank (ZMod 2) (⊥ : Submodule (ZMod 2) (Fin 1 → ZMod 2))) (booleanAffineRestriction (fun _ => 1) a ⊥)
        have h_rk : Module.finrank (ZMod 2) (⊥ : Submodule (ZMod 2) (Fin 1 → ZMod 2)) = 0 :=
          finrank_bot (ZMod 2) (Fin 1 → ZMod 2)
        omega
  5. The left-hand condition holds, implying that the top form vanishes on the unique empty family of vectors in $\bot$.

    Applying the specialized equivalence from right to left, the verified right-hand side implies that booleanTopForm $0$ $p$ $u = 0$ for any tuple $u \colon \mathrm{Fin}\,0 \to (\mathrm{Fin}\,1 \to \mathbb{Z}_2)$ with components in $\bot$. Since $\mathrm{Fin}\,0$ is empty, the zero tuple vacuously has all its components in $\bot$ (by Fin.elim0), so the top form evaluated on this tuple must be 0.

    lines 46–50

    uses Fin.elim0

      have h_lhs := h_spec.mpr h_rhs
      have h_u_in : ∀ i : Fin 0, (fun _ : Fin 0 => (0 : Fin 1 → ZMod 2)) i ∈ (⊥ : Submodule (ZMod 2) (Fin 1 → ZMod 2)) := by
        intro i
        exact Fin.elim0 i
      have h_zero := h_lhs (fun _ => 0) h_u_in
  6. Evaluating the top form yields $1 = 0$, completing the contradiction.

    By definition, booleanTopForm on an empty family $u$ is the sum of $p(\sum_{i \in S} u_i)$ over all subsets $S \subseteq \mathrm{Fin}\,0$. Since the empty set is the only subset of $\mathrm{Fin}\,0$, this sum reduces to the single term $S = \emptyset$, giving $p(0) = 1$. This equates 1 to 0 in $\mathbb{Z}_2$, which is a contradiction.

    lines 51–57

    uses Finset.sum_singleton

      dsimp [booleanTopForm] at h_zero
      have h_univ : (Finset.univ : Finset (Finset (Fin 0))) = {∅} := by
        decide
      rw [h_univ] at h_zero
      simp only [Finset.sum_singleton] at h_zero
      revert h_zero
      decide
le_antisymm
In a partially ordered set, if $a \le b$ and $b \le a$, then $a = b$.
Finset.sup_le
The supremum of a function $f$ over a finite set $s$ is at most $a$ if $f(b) \le a$ for every $b \in s$.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal set Finset.univ.
true_and
Conjunction of True with any proposition $p$ is equal to $p$.
Finset.card_le_univ
The cardinality of any finite subset is at most the cardinality of the ambient finite type.
Fintype.card_fin
The cardinality of the standard finite set Fin $n$ is $n$.
Finset.card_eq_iff_eq_univ
A finite subset of a finite type has the maximum cardinality if and only if it is the entire universe.
Finset.sum_const
The sum of a constant $b$ over a finite set $s$ equals the cardinality of $s$ scalar-multiplied by $b$.
Finset.card_univ
The cardinality of Finset.univ equals the cardinality of the underlying finite type.
Fintype.card_fun
The number of functions from a finite type $\alpha$ to a finite type $\beta$ is $|\beta|^{|\alpha|}$.
ZMod.card
The cardinality of the finite ring $\mathbb{Z}/n\mathbb{Z}$ is $n$.
nsmul_eq_mul
Scalar multiplication of an element by a natural number $n$ equals multiplication by the coercion of $n$.
mul_one
Multiplying an element by 1 on the right leaves it unchanged.
Nat.zero_le
Every natural number is greater than or equal to zero.
finrank_bot
The dimension (finite rank) of the trivial submodule $\bot$ over a non-trivial semiring is 0.
Fin.elim0
The empty type Fin 0 has no elements; given any element of Fin 0, one can prove any goal by ex falso.
Finset.sum_singleton
The sum of a function over a singleton set $\{a\}$ equals the value of the function at $a$.

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

theorem not_boolean_subspace_degree_reduction_criterion : ¬ (∀ {n d : ℕ}    (p : (Fin n → ZMod 2) → ZMod 2) (hp : booleanDegree p = d)    (U : Submodule (ZMod 2) (Fin n → ZMod 2)), (∀ u : Fin d → (Fin n → ZMod 2), (∀ i, u i ∈ U) → booleanTopForm d p u = 0) ↔      (∀ a : Fin n → ZMod 2, booleanDegree (booleanAffineRestriction p a U) ≤ d - 1)) := by  intro h  have test_deg : booleanDegree (fun (_ : Fin 1 → ZMod 2) => (1 : ZMod 2)) = 0 := by    dsimp [booleanDegree]    apply le_antisymm    · apply Finset.sup_le      intro S hS      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hS      by_contra hc      have hS_card : S.card = 1 := by        have := Finset.card_le_univ S        simp only [Fintype.card_fin] at this        omega      have hS_univ : S = Finset.univ := by        rw [← Finset.card_eq_iff_eq_univ]        rw [Fintype.card_fin]        exact hS_card      subst hS_univ      have h_sum : (∑ x ∈ Finset.univ.filter (fun (x : Fin 1 → ZMod 2) => ∀ i, x i ≠ 0 → i ∈ (Finset.univ : Finset (Fin 1))), (1 : ZMod 2)) = 0 := by        have : (Finset.univ.filter (fun (x : Fin 1 → ZMod 2) => ∀ i, x i ≠ 0 → i ∈ (Finset.univ : Finset (Fin 1)))) = Finset.univ := by          ext x; simp        rw [this]        simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fun, Fintype.card_fin,          ZMod.card, nsmul_eq_mul, mul_one]        rfl      exact hS h_sum    · exact Nat.zero_le _  have q_deg : ∀ (k : ℕ) (f : (Fin k → ZMod 2) → ZMod 2), booleanDegree f ≤ k := by    intro k f    dsimp [booleanDegree]    apply Finset.sup_le    intro S _    have := Finset.card_le_univ S    simp only [Fintype.card_fin] at this    exact this  have h_spec := @h 1 0 (fun _ => 1) test_deg ⊥  have h_rhs : ∀ a : Fin 1 → ZMod 2, booleanDegree (booleanAffineRestriction (fun _ => 1) a ⊥) ≤ 0 - 1 := by    intro a    have h_deg := q_deg (Module.finrank (ZMod 2) (⊥ : Submodule (ZMod 2) (Fin 1 → ZMod 2))) (booleanAffineRestriction (fun _ => 1) a ⊥)    have h_rk : Module.finrank (ZMod 2) (⊥ : Submodule (ZMod 2) (Fin 1 → ZMod 2)) = 0 :=      finrank_bot (ZMod 2) (Fin 1 → ZMod 2)    omega  have h_lhs := h_spec.mpr h_rhs  have h_u_in : ∀ i : Fin 0, (fun _ : Fin 0 => (0 : Fin 1 → ZMod 2)) i ∈ (⊥ : Submodule (ZMod 2) (Fin 1 → ZMod 2)) := by    intro i    exact Fin.elim0 i  have h_zero := h_lhs (fun _ => 0) h_u_in  dsimp [booleanTopForm] at h_zero  have h_univ : (Finset.univ : Finset (Finset (Fin 0))) = {∅} := by    decide  rw [h_univ] at h_zero  simp only [Finset.sum_singleton] at h_zero  revert h_zero  decide
See it in the graphDiscuss this resultChallenge it