explicitApproximant_mem_degreeSpace
For any Boolean function f : (Fin n → Bool) → Bool on n > 0 variables, the explicit approximant P_f belongs to degreeSpace (K := ℝ) (Fin n) (n - 1).
Statement
theorem explicitApproximant_mem_degreeSpace {n : ℕ} (hn : 0 < n)
(f : (Fin n → Bool) → Bool) :
explicitApproximant f ∈ degreeSpace (K := ℝ) (Fin n) (n - 1)- Formalizes
- arXiv:2610.19174, Listing A.14
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- explicitApproximantFor a Boolean function f : (Fin n → Bool) → Bool and input x : Fin n → Bool, explicitApproximant f x is (if f x then 1 else 0)/2 -…
- degreeSpaceFor a commutative ring K, a finite type ι with decidable equality, and a natural number d, degreeSpace K ι d is the K-submodule of (ι →…
- BooleanAnalysis.instAddCommGroupBooleanFuncBoolean functions form an
ℝ-vector space. - topCoefficientFor an implicit natural number n and a Boolean-valued function f : (Fin n → Bool) → Bool, topCoefficient f is the integer defined by the…
- fullMonomialThe full monomial x_[n] = ∏_{i=1}^n x_i evaluated at a point in {0,1}^n.
- parityCharacterFor an implicit natural number n and a Boolean assignment x : Fin n → Bool, parityCharacter x is the real number defined by the product…
- bitThe real embedding of a Boolean value, sending false to 0 and true to 1.
- Used by 1
- 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.
Read back from the Lean
For any natural number $n$ such that $0 < n$, and for every Boolean function $f : (\text{Fin } n \to \text{Bool}) \to \text{Bool}$, the function explicitApproximant f belongs to degreeSpace (K := ℝ) (Fin n) (n - 1), which is the $\mathbb{R}$-submodule of functions $(\text{Fin } n \to \text{Bool}) \to \mathbb{R}$ spanned by multilinear monomials of degree at most $n - 1$.
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
The theorem proves that for any Boolean function f on n > 0 variables, its explicit approximant P_f has polynomial degree at most n - 1. The proof first shows that subtracting the top-degree monomial from any product of affine linear factors leaves a polynomial in degreeSpace (n - 1); specializing this gives that both f minus its top Fourier component and the parity character minus 2^n times the full monomial lie in degreeSpace (n - 1). Finally, P_f is algebraically expressed as an explicit linear combination of these two functions, placing it in degreeSpace (n - 1) by submodule closure.
The product ∏ (a i * bit(x i) + b i) minus (∏ a i) * fullMonomial(x) equals the sum over all proper subsets t ⊂ univ of ((∏_{i ∈ t} a i) * (∏_{i ∉ t} b i)) * ∏_{i ∈ t} bit(x i).
Using `prod_add`, the product ∏ (a i * bit(x i) + b i) expands as a sum over all subsets t ⊆ univ. Separating the full set t = univ via `add_sum_erase` isolates the top-degree term (∏ a i) * fullMonomial(x), which cancels the subtracted term, leaving only the sum over proper subsets t.
uses
prod_add,add_sum_erasehave H : (fun x : Fin n → Bool => (∏ i : Fin n, (a i * bit (x i) + b i)) - (∏ i : Fin n, a i) * fullMonomial x) = ∑ t ∈ univ.powerset.erase univ, ((∏ i ∈ t, a i) * (∏ i ∈ univ \ t, b i)) • (fun x => ∏ i ∈ t, bit (x i)) := by ext x rw [Finset.sum_apply] simp only [Pi.smul_apply, smul_eq_mul] have hprod : ∏ i : Fin n, (a i * bit (x i) + b i) = (∏ i : Fin n, a i) * fullMonomial x + ∑ t ∈ univ.powerset.erase univ, (∏ i ∈ t, a i) * (∏ i ∈ univ \ t, b i) * (∏ i ∈ t, bit (x i)) := by rw [prod_add] have h_mem : univ ∈ (univ : Finset (Fin n)).powerset := mem_powerset_self univ rw [← add_sum_erase _ _ h_mem] congr 1 · have : (univ : Finset (Fin n)) \ univ = ∅ := sdiff_self rw [this, prod_empty, mul_one, prod_mul_distrib] rfl · apply sum_congr rfl intro t _ rw [prod_mul_distrib] ring rw [hprod] ring
The function ∏ (a i * bit(x i) + b i) - (∏ a i) * fullMonomial(x) belongs to degreeSpace ℝ (Fin n) (n - 1).
Every subset t in the erased powerset is strictly contained in univ, so its cardinality is strictly less than n (hence ≤ n - 1). Each corresponding monomial ∏_{i ∈ t} bit(x i) is therefore in the generating set for degreeSpace (n - 1) by `Submodule.subset_span`. Since a submodule is closed under linear combinations (`Submodule.sum_mem` and `Submodule.smul_mem`), the whole sum belongs to degreeSpace (n - 1).
uses
Submodule.sum_mem,card_lt_card,Fintype.card_fin,Submodule.smul_mem,Submodule.subset_spanrw [H] apply Submodule.sum_mem intro t ht have ht_ne : t ≠ univ := (mem_erase.mp ht).1 have ht_sub : t ⊂ univ := ssubset_univ_iff.mpr ht_ne have hcard : t.card < Fintype.card (Fin n) := card_lt_card ht_sub simp only [Fintype.card_fin] at hcard apply Submodule.smul_mem apply Submodule.subset_span exact ⟨t, by omega, rfl⟩
The parity character minus 2^n * fullMonomial belongs to degreeSpace ℝ (Fin n) (n - 1).
We specialize `explicitApproximant_prod_add_sub_top_mem` with a i = 2 and b i = -1. On each coordinate, 2 * bit(x i) - 1 equals 1 if x i is true and -1 if x i is false, matching the definition of parityCharacter. The product of the coefficients a i is 2^n, so the function matches the specialized lemma.
uses
explicitApproximant_prod_add_sub_top_mem,prod_congrhave h := explicitApproximant_prod_add_sub_top_mem hn (fun _ => 2) (fun _ => -1) have hprod : (∏ i : Fin n, (2 : ℝ)) = (2 : ℝ) ^ n := by simp have heq : (fun x : Fin n → Bool => parityCharacter x - (2 : ℝ) ^ n * fullMonomial x) = (fun x => (∏ i : Fin n, ((2 : ℝ) * bit (x i) + -1)) - (∏ i : Fin n, (2 : ℝ)) * fullMonomial x) := by ext x congr 1 · dsimp [parityCharacter] apply prod_congr rfl intro i _ cases x i <;> simp [bit] <;> norm_num · rw [hprod] rw [heq] exact h
For any y : Fin n → Bool, the point indicator function δ_y minus parityCharacter(y) * fullMonomial belongs to degreeSpace ℝ (Fin n) (n - 1).
We specialize `explicitApproximant_prod_add_sub_top_mem` with a i = 1 (if y i is true) or -1 (if false), and b i = 0 (if y i is true) or 1 (if false). Each factor a i * bit(x i) + b i is 1 if x i = y i and 0 otherwise. Their product equals the indicator δ_y(x) (which vanishes if x ≠ y by `prod_eq_zero`), and the coefficient product is parityCharacter(y).
uses
explicitApproximant_prod_add_sub_top_mem,prod_eq_zerohave h := explicitApproximant_prod_add_sub_top_mem hn (fun i => if y i = true then 1 else -1) (fun i => if y i = true then 0 else 1) have heq : (fun x : Fin n → Bool => (if x = y then (1 : ℝ) else 0) - parityCharacter y * fullMonomial x) = (fun x => (∏ i : Fin n, ((if y i = true then (1:ℝ) else -1) * bit (x i) + (if y i = true then 0 else 1))) - (∏ i : Fin n, (if y i = true then (1:ℝ) else -1)) * fullMonomial x) := by ext x have Hfactor : ∀ i : Fin n, (if x i = y i then (1 : ℝ) else 0) = ((if y i = true then 1 else -1) * bit (x i) + (if y i = true then 0 else 1)) := by intro i cases x i <;> cases y i <;> simp [bit] have Hprod : (if x = y then (1 : ℝ) else 0) = ∏ i : Fin n, (if x i = y i then (1 : ℝ) else 0) := by split_ifs with hxy · subst hxy; simp · have : ∃ i : Fin n, x i ≠ y i := by contrapose! hxy ext i exact hxy i rcases this with ⟨i, hi⟩ symm exact prod_eq_zero (mem_univ i) (if_neg hi) dsimp [parityCharacter] rw [Hprod, prod_congr rfl (fun i _ => Hfactor i)] rw [heq] exact h
Any Boolean function f minus topCoefficient(f) * fullMonomial can be written as the sum over y of f(y) • (δ_y - parityCharacter(y) * fullMonomial).
The sum over y of f(y) * δ_y(x) collapses to f(x) by `sum_eq_single`. Factoring out fullMonomial(x) from the second part via `sum_mul` leaves the sum over y of f(y) * parityCharacter(y), which is topCoefficient(f) by definition. Distributing the subtraction yields the identity.
uses
sum_eq_single,sum_mul,sum_sub_distribhave H : (fun x : Fin n → Bool => (if f x = true then (1 : ℝ) else 0) - (topCoefficient f : ℝ) * fullMonomial x) = ∑ y, (if f y = true then (1 : ℝ) else 0) • (fun x => (if x = y then 1 else 0) - parityCharacter y * fullMonomial x) := by ext x rw [Finset.sum_apply] simp only [Pi.smul_apply, smul_eq_mul] have H1 : (∑ y, (if f y = true then (1 : ℝ) else 0) * (if x = y then 1 else 0)) = (if f x = true then 1 else 0) := by rw [sum_eq_single x] · simp · intro y _ hy have : ¬x = y := ne_comm.mp hy rw [if_neg this, mul_zero] · intro h exact False.elim (h (mem_univ x)) have H2 : (∑ y, (if f y = true then (1 : ℝ) else 0) * (parityCharacter y * fullMonomial x)) = (topCoefficient f : ℝ) * fullMonomial x := by dsimp [topCoefficient, parityCharacter] push_cast rw [sum_mul] apply sum_congr rfl intro y _ split_ifs with h <;> ring rw [← H1, ← H2, ← sum_sub_distrib] apply sum_congr rfl intro y _ ring
The function f minus topCoefficient(f) * fullMonomial belongs to degreeSpace ℝ (Fin n) (n - 1).
Since f - topCoefficient(f) * fullMonomial is expressed as a linear combination of terms δ_y - parityCharacter(y) * fullMonomial, each of which belongs to degreeSpace (n - 1) by `explicitApproximant_delta_sub_top_mem`, the submodule closure properties `Submodule.sum_mem` and `Submodule.smul_mem` guarantee membership.
uses
Submodule.sum_mem,Submodule.smul_mem,explicitApproximant_delta_sub_top_memrw [H] apply Submodule.sum_mem intro y _ apply Submodule.smul_mem exact explicitApproximant_delta_sub_top_mem hn y
The components f - topCoefficient(f) * fullMonomial and parityCharacter - 2^n * fullMonomial belong to degreeSpace (n - 1), and topCoefficient(f) decomposes via division by 2 with remainder. automation
We invoke `explicitApproximant_function_sub_top_mem` and `explicitApproximant_parityCharacter_sub_top_mem`. The integer division identity topCoefficient(f) = 2 * (topCoefficient(f) / 2) + topCoefficient(f) % 2 is proved by omega, 2^(n + 1) = 2^n * 2 holds by `pow_succ`, and 2^n ≠ 0 holds by positivity.
uses
explicitApproximant_function_sub_top_mem,explicitApproximant_parityCharacter_sub_top_mem,pow_succhave h1 := explicitApproximant_function_sub_top_mem hn f have h2 := explicitApproximant_parityCharacter_sub_top_mem hn have hdiv : topCoefficient f = 2 * (topCoefficient f / 2) + topCoefficient f % 2 := by omega have hdivR : (topCoefficient f : ℝ) = 2 * ((topCoefficient f / 2 : ℤ) : ℝ) + ((topCoefficient f % 2 : ℤ) : ℝ) := by exact_mod_cast hdiv have hpow : (2 : ℝ) ^ (n + 1) = (2 : ℝ) ^ n * 2 := pow_succ 2 n have he2n : (2 : ℝ) ^ n ≠ 0 := by positivity
The explicit approximant P_f decomposes as (1 / 2) • (f - topCoefficient(f) * fullMonomial) - ((topCoefficient(f) % 2) / 2^(n + 1)) • (parityCharacter - 2^n * fullMonomial).
Unfolding the definition of explicitApproximant, substituting the division decomposition of topCoefficient(f), and cancelling 2^n via `mul_div_mul_right`, an elementary algebraic calculation shows that the two expressions evaluate to the same value on every input x.
uses
mul_div_mul_righthave Heq : explicitApproximant f = (1 / 2 : ℝ) • (fun x => (if f x = true then 1 else 0) - (topCoefficient f : ℝ) * fullMonomial x) - (((topCoefficient f % 2 : ℤ) : ℝ) / 2 ^ (n + 1)) • (fun x => parityCharacter x - (2 : ℝ) ^ n * fullMonomial x) := by ext x dsimp [explicitApproximant] rw [hdivR, hpow] have hcalc : ∀ (a b c d e p : ℝ), e ≠ 0 → a / 2 - b * d - c * p / (e * 2) = (1 / 2) * (a - (2 * b + c) * d) - (c / (e * 2)) * (p - e * d) := by intro a b c d e p he have : c / (e * 2) * (p - e * d) = c * p / (e * 2) - c * e * d / (e * 2) := by ring rw [this] have he_cancel : c * e * d / (e * 2) = c * d / 2 := by calc c * e * d / (e * 2) = (c * d) * e / (2 * e) := by ring _ = c * d / 2 := mul_div_mul_right (c * d) 2 he rw [he_cancel] ring exact hcalc (if f x = true then 1 else 0) ((topCoefficient f / 2 : ℤ) : ℝ) ((topCoefficient f % 2 : ℤ) : ℝ) (fullMonomial x) (2 ^ n) (parityCharacter x) he2n
The explicit approximant P_f belongs to degreeSpace ℝ (Fin n) (n - 1).
Because P_f is a linear combination (scalar multiples and subtraction) of two functions already known to belong to degreeSpace (n - 1), `Submodule.sub_mem` and `Submodule.smul_mem` establish that P_f belongs to degreeSpace ℝ (Fin n) (n - 1).
uses
Submodule.sub_mem,Submodule.smul_memrw [Heq] exact Submodule.sub_mem _ (Submodule.smul_mem _ _ h1) (Submodule.smul_mem _ _ h2)
add_sum_erase- Separating an element a from a sum over s gives f a plus the sum over s with a removed.
card_lt_card- A strict subset of a finite set has strictly smaller cardinality.
explicitApproximant_delta_sub_top_mem- The indicator function of a single point y minus parityCharacter(y) * fullMonomial belongs to degreeSpace (n - 1).
explicitApproximant_function_sub_top_mem- Any Boolean function f minus topCoefficient(f) * fullMonomial belongs to degreeSpace (n - 1).
explicitApproximant_parityCharacter_sub_top_mem- The parity character minus 2^n * fullMonomial belongs to degreeSpace (n - 1).
explicitApproximant_prod_add_sub_top_mem- The product ∏ (a i * bit(x i) + b i) minus (∏ a i) * fullMonomial(x) belongs to degreeSpace (n - 1).
Fintype.card_fin- The cardinality of Fin n is n.
mul_div_mul_right- In a group with zero, a non-zero factor c cancels from numerator and denominator: (a * c) / (b * c) = a / b.
pow_succ- a^(n + 1) = a^n * a in any monoid.
prod_add- Expanding the product of binomials ∏ (f i + g i) yields the sum over all subsets t of (∏_{i ∈ t} f i) * (∏_{i ∉ t} g i).
prod_congr- Two products over equal sets are equal if their terms agree pointwise.
prod_eq_zero- A product over a finite set is zero if one of its factors is zero.
Submodule.smul_mem- A submodule is closed under scalar multiplication.
Submodule.sub_mem- A submodule is closed under subtraction.
Submodule.subset_span- Every element of a generating set s belongs to the submodule spanned by s.
Submodule.sum_mem- A submodule is closed under finite sums.
sum_eq_single- A sum over a finite set collapses to f a if every term other than a vanishes.
sum_mul- Multiplication distributes over finite sums on the right.
sum_sub_distrib- Finite sums distribute over subtraction.
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.
open Finsettheorem explicitApproximant_prod_add_sub_top_mem {n : ℕ} (hn : 0 < n) (a b : Fin n → ℝ) : (fun x : Fin n → Bool => (∏ i : Fin n, (a i * bit (x i) + b i)) - (∏ i : Fin n, a i) * fullMonomial x) ∈ degreeSpace ℝ (Fin n) (n - 1) := by have H : (fun x : Fin n → Bool => (∏ i : Fin n, (a i * bit (x i) + b i)) - (∏ i : Fin n, a i) * fullMonomial x) = ∑ t ∈ univ.powerset.erase univ, ((∏ i ∈ t, a i) * (∏ i ∈ univ \ t, b i)) • (fun x => ∏ i ∈ t, bit (x i)) := by ext x rw [Finset.sum_apply] simp only [Pi.smul_apply, smul_eq_mul] have hprod : ∏ i : Fin n, (a i * bit (x i) + b i) = (∏ i : Fin n, a i) * fullMonomial x + ∑ t ∈ univ.powerset.erase univ, (∏ i ∈ t, a i) * (∏ i ∈ univ \ t, b i) * (∏ i ∈ t, bit (x i)) := by rw [prod_add] have h_mem : univ ∈ (univ : Finset (Fin n)).powerset := mem_powerset_self univ rw [← add_sum_erase _ _ h_mem] congr 1 · have : (univ : Finset (Fin n)) \ univ = ∅ := sdiff_self rw [this, prod_empty, mul_one, prod_mul_distrib] rfl · apply sum_congr rfl intro t _ rw [prod_mul_distrib] ring rw [hprod] ring rw [H] apply Submodule.sum_mem intro t ht have ht_ne : t ≠ univ := (mem_erase.mp ht).1 have ht_sub : t ⊂ univ := ssubset_univ_iff.mpr ht_ne have hcard : t.card < Fintype.card (Fin n) := card_lt_card ht_sub simp only [Fintype.card_fin] at hcard apply Submodule.smul_mem apply Submodule.subset_span exact ⟨t, by omega, rfl⟩lemma explicitApproximant_parityCharacter_sub_top_mem {n : ℕ} (hn : 0 < n) : (fun x : Fin n → Bool => parityCharacter x - (2 : ℝ) ^ n * fullMonomial x) ∈ degreeSpace ℝ (Fin n) (n - 1) := by have h := explicitApproximant_prod_add_sub_top_mem hn (fun _ => 2) (fun _ => -1) have hprod : (∏ i : Fin n, (2 : ℝ)) = (2 : ℝ) ^ n := by simp have heq : (fun x : Fin n → Bool => parityCharacter x - (2 : ℝ) ^ n * fullMonomial x) = (fun x => (∏ i : Fin n, ((2 : ℝ) * bit (x i) + -1)) - (∏ i : Fin n, (2 : ℝ)) * fullMonomial x) := by ext x congr 1 · dsimp [parityCharacter] apply prod_congr rfl intro i _ cases x i <;> simp [bit] <;> norm_num · rw [hprod] rw [heq] exact hlemma explicitApproximant_delta_sub_top_mem {n : ℕ} (hn : 0 < n) (y : Fin n → Bool) : (fun x : Fin n → Bool => (if x = y then (1 : ℝ) else 0) - parityCharacter y * fullMonomial x) ∈ degreeSpace ℝ (Fin n) (n - 1) := by have h := explicitApproximant_prod_add_sub_top_mem hn (fun i => if y i = true then 1 else -1) (fun i => if y i = true then 0 else 1) have heq : (fun x : Fin n → Bool => (if x = y then (1 : ℝ) else 0) - parityCharacter y * fullMonomial x) = (fun x => (∏ i : Fin n, ((if y i = true then (1:ℝ) else -1) * bit (x i) + (if y i = true then 0 else 1))) - (∏ i : Fin n, (if y i = true then (1:ℝ) else -1)) * fullMonomial x) := by ext x have Hfactor : ∀ i : Fin n, (if x i = y i then (1 : ℝ) else 0) = ((if y i = true then 1 else -1) * bit (x i) + (if y i = true then 0 else 1)) := by intro i cases x i <;> cases y i <;> simp [bit] have Hprod : (if x = y then (1 : ℝ) else 0) = ∏ i : Fin n, (if x i = y i then (1 : ℝ) else 0) := by split_ifs with hxy · subst hxy; simp · have : ∃ i : Fin n, x i ≠ y i := by contrapose! hxy ext i exact hxy i rcases this with ⟨i, hi⟩ symm exact prod_eq_zero (mem_univ i) (if_neg hi) dsimp [parityCharacter] rw [Hprod, prod_congr rfl (fun i _ => Hfactor i)] rw [heq] exact hlemma explicitApproximant_function_sub_top_mem {n : ℕ} (hn : 0 < n) (f : (Fin n → Bool) → Bool) : (fun x : Fin n → Bool => (if f x = true then (1 : ℝ) else 0) - (topCoefficient f : ℝ) * fullMonomial x) ∈ degreeSpace ℝ (Fin n) (n - 1) := by have H : (fun x : Fin n → Bool => (if f x = true then (1 : ℝ) else 0) - (topCoefficient f : ℝ) * fullMonomial x) = ∑ y, (if f y = true then (1 : ℝ) else 0) • (fun x => (if x = y then 1 else 0) - parityCharacter y * fullMonomial x) := by ext x rw [Finset.sum_apply] simp only [Pi.smul_apply, smul_eq_mul] have H1 : (∑ y, (if f y = true then (1 : ℝ) else 0) * (if x = y then 1 else 0)) = (if f x = true then 1 else 0) := by rw [sum_eq_single x] · simp · intro y _ hy have : ¬x = y := ne_comm.mp hy rw [if_neg this, mul_zero] · intro h exact False.elim (h (mem_univ x)) have H2 : (∑ y, (if f y = true then (1 : ℝ) else 0) * (parityCharacter y * fullMonomial x)) = (topCoefficient f : ℝ) * fullMonomial x := by dsimp [topCoefficient, parityCharacter] push_cast rw [sum_mul] apply sum_congr rfl intro y _ split_ifs with h <;> ring rw [← H1, ← H2, ← sum_sub_distrib] apply sum_congr rfl intro y _ ring rw [H] apply Submodule.sum_mem intro y _ apply Submodule.smul_mem exact explicitApproximant_delta_sub_top_mem hn y/-- The explicit approximant has degree at most n - 1. -/theorem explicitApproximant_mem_degreeSpace {n : ℕ} (hn : 0 < n) (f : (Fin n → Bool) → Bool) : explicitApproximant f ∈ degreeSpace (K := ℝ) (Fin n) (n - 1) := by have h1 := explicitApproximant_function_sub_top_mem hn f have h2 := explicitApproximant_parityCharacter_sub_top_mem hn have hdiv : topCoefficient f = 2 * (topCoefficient f / 2) + topCoefficient f % 2 := by omega have hdivR : (topCoefficient f : ℝ) = 2 * ((topCoefficient f / 2 : ℤ) : ℝ) + ((topCoefficient f % 2 : ℤ) : ℝ) := by exact_mod_cast hdiv have hpow : (2 : ℝ) ^ (n + 1) = (2 : ℝ) ^ n * 2 := pow_succ 2 n have he2n : (2 : ℝ) ^ n ≠ 0 := by positivity have Heq : explicitApproximant f = (1 / 2 : ℝ) • (fun x => (if f x = true then 1 else 0) - (topCoefficient f : ℝ) * fullMonomial x) - (((topCoefficient f % 2 : ℤ) : ℝ) / 2 ^ (n + 1)) • (fun x => parityCharacter x - (2 : ℝ) ^ n * fullMonomial x) := by ext x dsimp [explicitApproximant] rw [hdivR, hpow] have hcalc : ∀ (a b c d e p : ℝ), e ≠ 0 → a / 2 - b * d - c * p / (e * 2) = (1 / 2) * (a - (2 * b + c) * d) - (c / (e * 2)) * (p - e * d) := by intro a b c d e p he have : c / (e * 2) * (p - e * d) = c * p / (e * 2) - c * e * d / (e * 2) := by ring rw [this] have he_cancel : c * e * d / (e * 2) = c * d / 2 := by calc c * e * d / (e * 2) = (c * d) * e / (2 * e) := by ring _ = c * d / 2 := mul_div_mul_right (c * d) 2 he rw [he_cancel] ring exact hcalc (if f x = true then 1 else 0) ((topCoefficient f / 2 : ℤ) : ℝ) ((topCoefficient f % 2 : ℤ) : ℝ) (fullMonomial x) (2 ^ n) (parityCharacter x) he2n rw [Heq] exact Submodule.sub_mem _ (Submodule.smul_mem _ _ h1) (Submodule.smul_mem _ _ h2)