AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_class_weight_eq_of_sum_eq

theoremverified

If the total sum of dyadic class weights over all residues equals the total sum of active counts, then pointwise equality holds for every residue.

Statement

theorem cycle_power_dyadic_class_weight_eq_of_sum_eq
    (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (b : ZMod n → ℕ → Bool)
    (hsum : (∑ p : ZMod n, cycle_power_dyadic_class_weight m (b p)) =
      ∑ p : ZMod n, (Finset.range (2 ^ m)).sum (fun a => (b p a).toNat)) :
    ∀ p : ZMod n, cycle_power_dyadic_class_weight m (b p) =
      (Finset.range (2 ^ m)).sum (fun a => (b p a).toNat)
Source
step towards simple_graph_cycle_power_dyadic_cover_class_model
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 2

The proof, explained

The proof proceeds by contradiction. Since each residue's dyadic class weight is individually at most its count of active bits, a failure of equality at any residue would make the weight strictly smaller there. Summing over all residues would then force the total dyadic class weight to be strictly less than the total active count, contradicting the hypothesis that the two sums are equal.

  1. For an arbitrary residue p, the dyadic class weight is bounded above by the active bit count.

    Fix a residue p ∈ ℤ/nℤ. By `cycle_power_dyadic_class_weight_le`, the dyadic class weight of b(p) is at most the sum of (b(p, a)).toNat over a ∈ {0, …, 2^m - 1}.

    lines 12–13

    uses cycle_power_dyadic_class_weight_le

      intro p
      have hle := cycle_power_dyadic_class_weight_le m hm (b p)
  2. If equality fails at residue p, the dyadic class weight at p is strictly less than the active bit count.

    Assume for contradiction that equality does not hold at p. Since the dyadic class weight is bounded above by the active count, non-equality forces it to be strictly smaller, which linear arithmetic (`omega`) verifies.

    lines 14–15

      by_contra hne
      have hlt : cycle_power_dyadic_class_weight m (b p) < (Finset.range (2^m)).sum (fun a => (b p a).toNat) := by omega
  3. The total sum of dyadic class weights over all residues is strictly less than the total sum of active counts.

    By `sum_lt_sum`, because the weak inequality holds for all residues q via `cycle_power_dyadic_class_weight_le` and the strict inequality holds at p (which belongs to the universe of residues by `mem_univ`), summing over all residues in ℤ/nℤ produces a strict inequality between the total sums.

    lines 16–17

    uses sum_lt_sum, cycle_power_dyadic_class_weight_le, mem_univ

      have hslt := sum_lt_sum (fun q _ => cycle_power_dyadic_class_weight_le m hm (b q))
        ⟨p, mem_univ _, hlt⟩
  4. Contradiction.

    The strict inequality between the total sums directly contradicts the hypothesis `hsum` asserting that they are equal. Linear integer arithmetic (`omega`) identifies this contradiction and concludes the proof.

    line 18

      omega
cycle_power_dyadic_class_weight_le
For any m ≥ 1 and boolean sequence b, the dyadic class weight of b is at most the sum of the active bits over indices 0 ≤ i < 2^m.
sum_lt_sum
A finite sum of terms is strictly less than another if the summands satisfy a pointwise weak inequality everywhere and a strict inequality at at least one element of the index set.
mem_univ
Every element of a finite type belongs to the universal finite set univ.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000/-- If the total sum of dyadic class weights over all residues equals the total sum of active counts, then pointwise equality holds for every residue. -/theorem cycle_power_dyadic_class_weight_eq_of_sum_eq    (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (b : ZMod n → ℕ → Bool)    (hsum : (∑ p : ZMod n, cycle_power_dyadic_class_weight m (b p)) =      ∑ p : ZMod n, (Finset.range (2 ^ m)).sum (fun a => (b p a).toNat)) :    ∀ p : ZMod n, cycle_power_dyadic_class_weight m (b p) =      (Finset.range (2 ^ m)).sum (fun a => (b p a).toNat) := by  intro p  have hle := cycle_power_dyadic_class_weight_le m hm (b p)  by_contra hne  have hlt : cycle_power_dyadic_class_weight m (b p) < (Finset.range (2^m)).sum (fun a => (b p a).toNat) := by omega  have hslt := sum_lt_sum (fun q _ => cycle_power_dyadic_class_weight_le m hm (b q))    ⟨p, mem_univ _, hlt⟩  omega
See it in the graphDiscuss this resultChallenge it