not_boolean_subspace_degree_reduction_criterion
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.
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$.
intro hThe 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.
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_lehave 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 _
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$.
uses
Finset.sup_le,Finset.card_le_univ,Fintype.card_finhave 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
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.
uses
finrank_bothave 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
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.
uses
Fin.elim0have 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
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.
uses
Finset.sum_singletondsimp [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$.
- Lean uses truncated natural number arithmetic where $0 - 1 = 0$. Consequently, for $d = 0$, the degree condition $\le d - 1$ becomes $\le 0$ rather than $\le -1$, causing the right-hand side of the equivalence to hold vacuously for degree-0 functions on 0-dimensional spaces.
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.
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