symmetric_counterexample_bent_weight_diff_div_sixteen
For any even n ≥ 8 and any two bent functions g and h on (Fin n → ZMod 2), the difference between the Hamming weight of h and the Hamming weight of g is divisible by 16 in the integers.
Statement
theorem symmetric_counterexample_bent_weight_diff_div_sixteen (n : ℕ) (hn_even : Even n) (hn8 : 8 ≤ n) (g h : (Fin n → ZMod 2) → ZMod 2) (hg : is_bent g) (hh : is_bent h) : (16 : ℤ) ∣ (((Finset.filter (fun x => h x = 1) Finset.univ).card : ℤ) - ((Finset.filter (fun x => g x = 1) Finset.univ).card : ℤ))
- Formalizes
- arXiv:2611.06744, Section 3.4
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- is_bentA Boolean function f on (Fin n → ZMod 2) is bent if its Walsh-Hadamard transform has absolute value 2^(n/2) everywhere.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
Read back from the Lean
For any natural number $n$, assuming $n$ is even and $8 \le n$, and for any two Boolean functions $g, h : (\text{Fin } n \to \mathbb{Z}/2\mathbb{Z}) \to \mathbb{Z}/2\mathbb{Z}$, if both $g$ and $h$ are bent (satisfying is_bent), then $16$ divides the integer difference between the Hamming weight of $h$ (the number of inputs $x$ where $h(x) = 1$) and the Hamming weight of $g$ (the number of inputs $x$ where $g(x) = 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 character sum ∑ x, (-1)^(f x) of a Boolean function f on n variables is related to its Hamming weight W(f) by ∑ x, (-1)^(f x) = 2^n - 2 * W(f). Evaluating the bent condition at frequency ω = 0 gives |2^n - 2 * W(f)| = 2^(n/2), so 2^n - 2 * W(f) is either 2^(n/2) or -2^(n/2). For any two bent functions g and h, subtracting these equations shows that W(h) - W(g) must equal 0, 2^(n/2), or -2^(n/2). Since n ≥ 8 implies n / 2 ≥ 4, 16 = 2^4 divides 2^(n/2), and therefore 16 divides W(h) - W(g) in all cases.
For any Boolean function f on (Fin n → ZMod 2), the character sum ∑ x, (-1)^(f x) equals 2^n - 2 * W(f), where W(f) is the Hamming weight of f.
Line 3 records the evenness hypothesis. Lines 7–11 prove the pointwise identity (-1)^(f x) = 1 - 2 * [f x = 1] by case analysis on f x ∈ {0, 1} via fin_cases and decide. Lines 12–15 then rewrite the character sum using this identity, split the sum over the difference (Finset.sum_sub_distrib), sum the constant 1 to the domain size 2^n (Finset.sum_const, nsmul_one), and factor out 2 (Finset.mul_sum) to express the sum of the indicator function as the cardinality of the support W(f) (Finset.sum_boole).
uses
Finset.sum_sub_distrib,Finset.sum_const,nsmul_one,Finset.mul_sum,Finset.sum_boolehave _ := hn_even have h_sum (f : (Fin n → ZMod 2) → ZMod 2) : (∑ x : Fin n → ZMod 2, if f x = 0 then (1 : ℤ) else -1) = ((Finset.univ : Finset (Fin n → ZMod 2)).card : ℤ) - 2 * ((Finset.filter (fun x => f x = 1) Finset.univ).card : ℤ) := by have h_term : ∀ x : Fin n → ZMod 2, (if f x = 0 then (1 : ℤ) else -1) = 1 - 2 * (if f x = 1 then (1 : ℤ) else 0) := by intro x generalize f x = a fin_cases a <;> decide simp_rw [h_term] rw [Finset.sum_sub_distrib, Finset.sum_const, nsmul_one, ← Finset.mul_sum] congr 1 rw [Finset.sum_boole]
Evaluating the bentness definition for g and h at frequency ω = 0 yields |∑ x, (-1)^(g x)| = 2^(n/2) and |∑ x, (-1)^(h x)| = 2^(n/2).
By definition, a function is bent when its Walsh transform at every frequency ω has absolute value 2^(n/2). Specializing to frequency ω = 0 (lines 17–18), the linear phase x ⬝ 0 vanishes identically (lines 19–21). Simplifying by x ⬝ 0 = 0 and f x + 0 = f x (add_zero) reduces the Walsh transform at ω = 0 directly to the character sum of the function (line 22).
uses
add_zerohave hg0 := hg 0 have hh0 := hh 0 have h_zero : ∀ x : Fin n → ZMod 2, (∑ i : Fin n, x i * (0 : Fin n → ZMod 2) i) = 0 := by intro x simp simp_rw [h_zero, add_zero] at hg0 hh0
The Hamming weights of g and h satisfy 2^n - 2 * W(g) = ± 2^(n/2) and 2^n - 2 * W(h) = ± 2^(n/2).
Since |a| = b implies a = b or a = -b (eq_or_eq_neg_of_abs_eq), each character sum is either 2^(n/2) or -2^(n/2). Rewriting the character sums using the identity relating them to Hamming weights (h_sum) yields the two sign possibilities for both g and h.
uses
eq_or_eq_neg_of_abs_eqhave hg_cases := eq_or_eq_neg_of_abs_eq hg0 have hh_cases := eq_or_eq_neg_of_abs_eq hh0 rw [h_sum g] at hg_cases rw [h_sum h] at hh_cases
16 divides 2^(n/2).
From 8 ≤ n, linear integer arithmetic (omega) gives 4 ≤ n / 2. Since 16 = 2^4 (norm_num), the monotonicity of prime powers under divisibility (pow_dvd_pow) ensures that 16 divides 2^(n/2).
uses
pow_dvd_powhave h4 : 4 ≤ n / 2 := by omega have h16 : (16 : ℤ) ∣ (2 : ℤ) ^ (n / 2) := by have : (16 : ℤ) = (2 : ℤ) ^ 4 := by norm_num rw [this] exact pow_dvd_pow (2 : ℤ) h4
The difference in Hamming weights W(h) - W(g) is divisible by 16.
Lines 35–38 introduce shorthands for the weights Wg and Wh, the total domain size U = 2^n, and the bent power P = 2^(n/2). Line 40 branches on the signs of U - 2 * Wg = ± P and U - 2 * Wh = ± P. If both signs are identical, subtracting the equations gives Wh - Wg = 0 by linear arithmetic (linarith), which 16 divides (dvd_zero). If the signs differ, subtracting gives Wh - Wg = P or Wh - Wg = -P (linarith); in either case, 16 divides the difference because 16 ∣ P (and dvd_neg.mpr).
uses
dvd_zero,dvd_neg.mprset Wg := ((Finset.filter (fun x => g x = 1) Finset.univ).card : ℤ) set Wh := ((Finset.filter (fun x => h x = 1) Finset.univ).card : ℤ) set U := ((Finset.univ : Finset (Fin n → ZMod 2)).card : ℤ) set P := (2 : ℤ) ^ (n / 2) rcases hg_cases with hg_val | hg_val <;> rcases hh_cases with hh_val | hh_val · have : Wh - Wg = 0 := by linarith rw [this] exact dvd_zero 16 · have : Wh - Wg = P := by linarith rw [this] exact h16 · have : Wh - Wg = -P := by linarith rw [this] exact dvd_neg.mpr h16 · have : Wh - Wg = 0 := by linarith rw [this] exact dvd_zero 16
Finset.sum_sub_distrib- The sum of a difference of functions over a finite set equals the difference of their sums: ∑ x ∈ s, (f x - g x) = ∑ x ∈ s, f x - ∑ x ∈ s, g x.
Finset.sum_const- Summing a constant value c over a finite set s equals |s| • c.
nsmul_one- Natural scalar multiplication of n with 1 in an additive monoid with one equals n.
Finset.mul_sum- Multiplication distributes over a finite sum: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_boole- The sum of the indicator function of a predicate p over a finite set s equals the number of elements in s satisfying p.
add_zero- Adding zero to any element leaves it unchanged: a + 0 = a.
eq_or_eq_neg_of_abs_eq- If the absolute value of a equals b, then either a = b or a = -b.
pow_dvd_pow- If m ≤ n, then a ^ m divides a ^ n in any monoid.
dvd_zero- Every element divides zero: a ∣ 0.
dvd_neg.mpr- If a divides b, then a divides -b.
- The hypothesis that n is even (hn_even) is recorded on line 3 but not directly used in the proof, as integer division with 8 ≤ n is sufficient for the arithmetic tactic omega to deduce 4 ≤ n / 2.
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.
/-- The difference between the Hamming weights of two bent functions in n variables is divisible by 16 for n ≥ 8. -/theorem symmetric_counterexample_bent_weight_diff_div_sixteen (n : ℕ) (hn_even : Even n) (hn8 : 8 ≤ n) (g h : (Fin n → ZMod 2) → ZMod 2) (hg : is_bent g) (hh : is_bent h) : (16 : ℤ) ∣ (((Finset.filter (fun x => h x = 1) Finset.univ).card : ℤ) - ((Finset.filter (fun x => g x = 1) Finset.univ).card : ℤ)) := by have _ := hn_even have h_sum (f : (Fin n → ZMod 2) → ZMod 2) : (∑ x : Fin n → ZMod 2, if f x = 0 then (1 : ℤ) else -1) = ((Finset.univ : Finset (Fin n → ZMod 2)).card : ℤ) - 2 * ((Finset.filter (fun x => f x = 1) Finset.univ).card : ℤ) := by have h_term : ∀ x : Fin n → ZMod 2, (if f x = 0 then (1 : ℤ) else -1) = 1 - 2 * (if f x = 1 then (1 : ℤ) else 0) := by intro x generalize f x = a fin_cases a <;> decide simp_rw [h_term] rw [Finset.sum_sub_distrib, Finset.sum_const, nsmul_one, ← Finset.mul_sum] congr 1 rw [Finset.sum_boole] have hg0 := hg 0 have hh0 := hh 0 have h_zero : ∀ x : Fin n → ZMod 2, (∑ i : Fin n, x i * (0 : Fin n → ZMod 2) i) = 0 := by intro x simp simp_rw [h_zero, add_zero] at hg0 hh0 have hg_cases := eq_or_eq_neg_of_abs_eq hg0 have hh_cases := eq_or_eq_neg_of_abs_eq hh0 rw [h_sum g] at hg_cases rw [h_sum h] at hh_cases have h4 : 4 ≤ n / 2 := by omega have h16 : (16 : ℤ) ∣ (2 : ℤ) ^ (n / 2) := by have : (16 : ℤ) = (2 : ℤ) ^ 4 := by norm_num rw [this] exact pow_dvd_pow (2 : ℤ) h4 set Wg := ((Finset.filter (fun x => g x = 1) Finset.univ).card : ℤ) set Wh := ((Finset.filter (fun x => h x = 1) Finset.univ).card : ℤ) set U := ((Finset.univ : Finset (Fin n → ZMod 2)).card : ℤ) set P := (2 : ℤ) ^ (n / 2) rcases hg_cases with hg_val | hg_val <;> rcases hh_cases with hh_val | hh_val · have : Wh - Wg = 0 := by linarith rw [this] exact dvd_zero 16 · have : Wh - Wg = P := by linarith rw [this] exact h16 · have : Wh - Wg = -P := by linarith rw [this] exact dvd_neg.mpr h16 · have : Wh - Wg = 0 := by linarith rw [this] exact dvd_zero 16