AFTD Auto-Formalizing Theoretical Domains

symmetric_counterexample_bent_weight_diff_div_sixteen

theoremverifiedformalization

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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.

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

    lines 3–15

    uses Finset.sum_sub_distrib, Finset.sum_const, nsmul_one, Finset.mul_sum, Finset.sum_boole

      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]
  2. 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).

    lines 17–22

    uses add_zero

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

    lines 24–27

    uses eq_or_eq_neg_of_abs_eq

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

    lines 29–33

    uses pow_dvd_pow

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

    lines 35–52

    uses dvd_zero, dvd_neg.mpr

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

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

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