AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_tight_class_spanning

theoremverified

A nonempty subset attaining equality in the uniform dyadic weight bound contains both endpoints of its arc.

Statement

theorem cycle_power_dyadic_tight_class_spanning (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool)
    (hw : cycle_power_dyadic_class_weight m b =
      (Finset.range (2 ^ m)).sum (fun i => (b i).toNat))
    (hne : ∃ i < 2 ^ m, b i = true) : b 0 = true ∧ b (2 ^ m - 1) = true
Source
Uniform route for OP-205 and RT-1, arXiv:2610.15635 Section 3. Existing k=3,7,15 weight certificates suggest this dyadic tree. The sparse distance graph is obtained recursively by attaching one leaf to every vertex; tight classes are connected subtrees containing the distinguished endpoint edge.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
  • cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

The theorem is proved by induction on k where the scale is m = k + 1, established in an auxiliary lemma for all non-negative k. In the base case m = 1, the tightness condition forces 2 * (b 0 && b 1) = b 0 + b 1, which requires both endpoints to be true whenever at least one is true. In the induction step, the indicator b is compressed into a lifted indicator b_lift at scale k+1; a weight decomposition and the general upper bound sandwich the weight of b_lift, showing that b_lift is tight and nonempty. Applying the induction hypothesis to b_lift and reading off its endpoints through the definition of the lift proves that both endpoints of b are true.

  1. In the base case k = 0, the dyadic weight equality reduces to 2 * (b 0 && b 1).toNat = (b 0).toNat + (b 1).toNat.

    We proceed by induction on k. In the base case k = 0, the arc length is 2^1 = 2. Unfolding the definition of dyadic class weight for m = 1, the inner sum over intermediate dyadic scales contains only j = 0 and thus evaluates to 0, leaving only the boundary term 2 * (b 0 && b 1).toNat. The sum of b(i) over the range of size 2 is (b 0).toNat + (b 1).toNat. Equating the weight with the sum yields the simplified equality.

    lines 6–13

    uses Finset.sum_range_succ

      induction' k with k ih
      · intro b hw hne
        have hw' : 2 * (b 0 && b 1).toNat = (b 0).toNat + (b 1).toNat := by
          have h1 : cycle_power_dyadic_class_weight 1 b = 2 * (b 0 && b 1).toNat := by
            dsimp [cycle_power_dyadic_class_weight]; simp
          have h2 : (Finset.range (2 ^ 1)).sum (fun i => (b i).toNat) = (b 0).toNat + (b 1).toNat := by
            simp [Finset.sum_range_succ]
          linarith [hw, h1, h2]
  2. In the base case, both endpoints b 0 and b 1 are true.

    From the nonemptiness hypothesis, there exists an index i < 2 such that b i = true. If b 0 were false, then i must be 1, giving b 1 = true; substituting these into the base case equation yields 2 * 0 = 0 + 1, a contradiction. Thus b 0 = true. Similarly, if b 1 were false, then 2 * 0 = 1 + 0, another contradiction. Hence both b 0 = true and b 1 = true.

    lines 14–29

        obtain ⟨i, hi, hbi⟩ := hne
        have h0 : b 0 = true := by
          by_contra h
          have hb0 : b 0 = false := Bool.eq_false_iff.2 h
          have hb1 : b 1 = true := by
            interval_cases i
            · rw [hb0] at hbi; contradiction
            · exact hbi
          rw [hb0, hb1] at hw'
          revert hw'; decide
        have h1 : b 1 = true := by
          by_contra h
          have hb1 : b 1 = false := Bool.eq_false_iff.2 h
          rw [h0, hb1] at hw'
          revert hw'; decide
        exact ⟨h0, h1⟩
  3. At the induction step, the lifted indicator b_lift attains equality in the dyadic weight bound at scale k+1.

    For the induction step, define b_lift by b(x) for x < 2^k and b(x + 2^(k+1)) for x ≥ 2^k. The dyadic weight at scale k+2 splits into the weight of b_lift at scale k+1 plus the sum of cross-terms b(i) && b(i + 2^(k+1)). By general bounds, the weight of b_lift is at most its sum, and the sum of b_lift plus the cross-terms is at most the total sum of b. Because b attains equality overall, each inequality in this chain must hold with equality, so b_lift is tight at scale k+1.

    lines 30–37

    uses cycle_power_dyadic_class_weight_succ, cycle_power_dyadic_class_weight_le_aux, cycle_power_dyadic_sum_lift_and_cross_le

      · intro b hw hne
        let b_lift := cycle_power_dyadic_b_lift k b
        have h_split := cycle_power_dyadic_class_weight_succ k b
        have h_le1 := cycle_power_dyadic_class_weight_le_aux k b_lift
        have h_le2 := cycle_power_dyadic_sum_lift_and_cross_le k b
        have hw_lift : cycle_power_dyadic_class_weight (k + 1) b_lift =
            ∑ i ∈ Finset.range (2 ^ (k + 1)), (b_lift i).toNat := by
          linarith [hw, h_split, h_le1, h_le2]
  4. The lifted indicator b_lift is nonempty on the range 0 to 2^(k+1)-1.

    Suppose for contradiction that b_lift is identically false on the range 0 to 2^(k+1)-1. By the definition of b_lift, this implies b(j) = false for j < 2^k and b(j + 2^(k+1)) = false for j ≥ 2^k. Consequently, every cross term b(j) && b(j + 2^(k+1)) is false, so both the sum of b_lift and the sum of cross-terms vanish. This would force the weight of b to be at most 0. But by nonemptiness of b, at least one value is true, so the total sum is at least 1, contradicting the equality between weight and sum.

    lines 38–62

    uses Finset.sum_congr, Bool.toNat_false, Bool.toNat_true, Finset.single_le_sum, Nat.zero_le

        have hne_lift : ∃ j < 2 ^ (k + 1), b_lift j = true := by
          by_contra h
          have hall : ∀ j < 2 ^ (k + 1), b_lift j = false := by
            intro j hj
            have : ¬ (b_lift j = true) := fun ht => h ⟨j, hj, ht⟩
            exact Bool.eq_false_iff.2 this
          have h_cross : ∀ j < 2 ^ (k + 1), (b j && b (j + 2 ^ (k + 1))) = false := by
            intro j hj
            dsimp [b_lift, cycle_power_dyadic_b_lift] at hall
            have hj_lift := hall j hj
            split_ifs at hj_lift with h_lt
            · rw [hj_lift]; rfl
            · rw [hj_lift]; cases b j <;> rfl
          have s1 : ∑ i ∈ Finset.range (2 ^ (k + 1)), (b_lift i).toNat = 0 := by
            rw [Finset.sum_congr rfl (fun x hx => by rw [hall x (Finset.mem_range.1 hx), Bool.toNat_false])]
            simp
          have s2 : ∑ i ∈ Finset.range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat = 0 := by
            rw [Finset.sum_congr rfl (fun x hx => by rw [h_cross x (Finset.mem_range.1 hx), Bool.toNat_false])]
            simp
          obtain ⟨i, hi, hbi⟩ := hne
          have h_sum_pos : 1 ≤ ∑ x ∈ Finset.range (2 ^ (k + 2)), (b x).toNat := by
            calc 1 = (b i).toNat := by rw [hbi, Bool.toNat_true]
            _ ≤ ∑ x ∈ Finset.range (2 ^ (k + 2)), (b x).toNat :=
              Finset.single_le_sum (f := fun x => (b x).toNat) (fun _ _ => Nat.zero_le _) (Finset.mem_range.2 hi)
          linarith [hw, h_split, h_le1, s1, s2, h_sum_pos]
  5. Both endpoints b 0 and b (2^(k+2) - 1) are true, completing the induction step.

    Applying the induction hypothesis to b_lift, which is tight and nonempty at scale k+1, shows that both b_lift 0 = true and b_lift (2^(k+1) - 1) = true. Since 0 < 2^k, the definition of b_lift gives b_lift 0 = b 0. Since 2^(k+1) - 1 ≥ 2^k, the upper endpoint evaluates via the second branch to b((2^(k+1) - 1) + 2^(k+1)) = b(2^(k+2) - 1). Thus both endpoints of b are true.

    lines 63–82

    uses Nat.two_pow_pos, pow_succ, Nat.one_le_two_pow, if_neg, mul_two

        have ih_res := ih b_lift hw_lift hne_lift
        have h0_lift : b_lift 0 = b 0 := by
          dsimp [b_lift, cycle_power_dyadic_b_lift]
          have : 0 < 2 ^ k := Nat.two_pow_pos k
          simp [this]
        have hlast_lift : b_lift (2 ^ (k + 1) - 1) = b (2 ^ (k + 2) - 1) := by
          dsimp [b_lift, cycle_power_dyadic_b_lift]
          have hge : ¬ (2 ^ (k + 1) - 1 < 2 ^ k) := by
            rw [pow_succ]
            have : 1 ≤ 2 ^ k := Nat.one_le_two_pow
            omega
          simp only [if_neg hge]
          congr 1
          have : 2 ^ (k + 2) = 2 ^ (k + 1) + 2 ^ (k + 1) := by
            rw [pow_succ, mul_two]
          have : 1 ≤ 2 ^ (k + 1) := Nat.one_le_two_pow
          omega
        rw [h0_lift] at ih_res
        rw [hlast_lift] at ih_res
        exact ih_res
  6. The main theorem holds for any m ≥ 1.

    Using the hypothesis m ≥ 1, we write m = (m - 1) + 1 and invoke the auxiliary lemma with k = m - 1.

    lines 88–90

    uses Nat.sub_add_cancel, cycle_power_dyadic_tight_class_spanning_aux

      have h : m = (m - 1) + 1 := (Nat.sub_add_cancel hm).symm
      rw [h] at hw hne ⊢
      exact cycle_power_dyadic_tight_class_spanning_aux (m - 1) b hw hne
Bool.toNat_false
The natural number representation of the boolean value false is 0.
Bool.toNat_true
The natural number representation of the boolean value true is 1.
Finset.single_le_sum
For any non-negative function on a finite set, the value at an individual element is at most the total sum over the set.
Finset.sum_congr
If two finite sets are equal and two functions agree on every element of the set, their sums over the set are equal.
Finset.sum_range_succ
The sum of a function over the range 0 to n equals the sum over 0 to n-1 plus the term at n.
Nat.zero_le
Every natural number is greater than or equal to zero.
Nat.one_le_two_pow
Any power of two is at least one.
Nat.sub_add_cancel
Subtracting m from n and then adding m yields n, provided m ≤ n.
Nat.two_pow_pos
Any power of two is strictly positive.
cycle_power_dyadic_class_weight_le_aux
The dyadic class weight of a boolean function at scale k+1 is at most the sum of its values over the range 0 to 2^(k+1)-1.
cycle_power_dyadic_class_weight_succ
The dyadic class weight at scale k+2 decomposes as the dyadic class weight of the lifted indicator at scale k+1 plus the sum of cross terms between the lower and upper halves.
cycle_power_dyadic_sum_lift_and_cross_le
The sum of the lifted indicator plus the sum of cross terms over the lower half is bounded above by the total sum of the original function over the full range 0 to 2^(k+2)-1.
cycle_power_dyadic_tight_class_spanning_aux
A nonempty boolean function achieving equality in the dyadic weight bound at scale k+1 is true at both endpoints 0 and 2^(k+1)-1.
if_neg
If the condition of an if-then-else expression is false, the expression evaluates to the else branch.
mul_two
Multiplying a number by two is equivalent to adding the number to itself.
pow_succ
Raising a base to the power n + 1 equals the base raised to n multiplied by the base.

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

lemma cycle_power_dyadic_tight_class_spanning_aux (k : ℕ) :    ∀ (b : ℕ → Bool),      cycle_power_dyadic_class_weight (k + 1) b = ∑ i ∈ Finset.range (2 ^ (k + 1)), (b i).toNat →      (∃ i < 2 ^ (k + 1), b i = true) →      b 0 = true ∧ b (2 ^ (k + 1) - 1) = true := by  induction' k with k ih  · intro b hw hne    have hw' : 2 * (b 0 && b 1).toNat = (b 0).toNat + (b 1).toNat := by      have h1 : cycle_power_dyadic_class_weight 1 b = 2 * (b 0 && b 1).toNat := by        dsimp [cycle_power_dyadic_class_weight]; simp      have h2 : (Finset.range (2 ^ 1)).sum (fun i => (b i).toNat) = (b 0).toNat + (b 1).toNat := by        simp [Finset.sum_range_succ]      linarith [hw, h1, h2]    obtain ⟨i, hi, hbi⟩ := hne    have h0 : b 0 = true := by      by_contra h      have hb0 : b 0 = false := Bool.eq_false_iff.2 h      have hb1 : b 1 = true := by        interval_cases i        · rw [hb0] at hbi; contradiction        · exact hbi      rw [hb0, hb1] at hw'      revert hw'; decide    have h1 : b 1 = true := by      by_contra h      have hb1 : b 1 = false := Bool.eq_false_iff.2 h      rw [h0, hb1] at hw'      revert hw'; decide    exact ⟨h0, h1⟩  · intro b hw hne    let b_lift := cycle_power_dyadic_b_lift k b    have h_split := cycle_power_dyadic_class_weight_succ k b    have h_le1 := cycle_power_dyadic_class_weight_le_aux k b_lift    have h_le2 := cycle_power_dyadic_sum_lift_and_cross_le k b    have hw_lift : cycle_power_dyadic_class_weight (k + 1) b_lift =        ∑ i ∈ Finset.range (2 ^ (k + 1)), (b_lift i).toNat := by      linarith [hw, h_split, h_le1, h_le2]    have hne_lift : ∃ j < 2 ^ (k + 1), b_lift j = true := by      by_contra h      have hall : ∀ j < 2 ^ (k + 1), b_lift j = false := by        intro j hj        have : ¬ (b_lift j = true) := fun ht => h ⟨j, hj, ht⟩        exact Bool.eq_false_iff.2 this      have h_cross : ∀ j < 2 ^ (k + 1), (b j && b (j + 2 ^ (k + 1))) = false := by        intro j hj        dsimp [b_lift, cycle_power_dyadic_b_lift] at hall        have hj_lift := hall j hj        split_ifs at hj_lift with h_lt        · rw [hj_lift]; rfl        · rw [hj_lift]; cases b j <;> rfl      have s1 : ∑ i ∈ Finset.range (2 ^ (k + 1)), (b_lift i).toNat = 0 := by        rw [Finset.sum_congr rfl (fun x hx => by rw [hall x (Finset.mem_range.1 hx), Bool.toNat_false])]        simp      have s2 : ∑ i ∈ Finset.range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat = 0 := by        rw [Finset.sum_congr rfl (fun x hx => by rw [h_cross x (Finset.mem_range.1 hx), Bool.toNat_false])]        simp      obtain ⟨i, hi, hbi⟩ := hne      have h_sum_pos : 1 ≤ ∑ x ∈ Finset.range (2 ^ (k + 2)), (b x).toNat := by        calc 1 = (b i).toNat := by rw [hbi, Bool.toNat_true]        _ ≤ ∑ x ∈ Finset.range (2 ^ (k + 2)), (b x).toNat :=          Finset.single_le_sum (f := fun x => (b x).toNat) (fun _ _ => Nat.zero_le _) (Finset.mem_range.2 hi)      linarith [hw, h_split, h_le1, s1, s2, h_sum_pos]    have ih_res := ih b_lift hw_lift hne_lift    have h0_lift : b_lift 0 = b 0 := by      dsimp [b_lift, cycle_power_dyadic_b_lift]      have : 0 < 2 ^ k := Nat.two_pow_pos k      simp [this]    have hlast_lift : b_lift (2 ^ (k + 1) - 1) = b (2 ^ (k + 2) - 1) := by      dsimp [b_lift, cycle_power_dyadic_b_lift]      have hge : ¬ (2 ^ (k + 1) - 1 < 2 ^ k) := by        rw [pow_succ]        have : 1 ≤ 2 ^ k := Nat.one_le_two_pow        omega      simp only [if_neg hge]      congr 1      have : 2 ^ (k + 2) = 2 ^ (k + 1) + 2 ^ (k + 1) := by        rw [pow_succ, mul_two]      have : 1 ≤ 2 ^ (k + 1) := Nat.one_le_two_pow      omega    rw [h0_lift] at ih_res    rw [hlast_lift] at ih_res    exact ih_restheorem cycle_power_dyadic_tight_class_spanning (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool)    (hw : cycle_power_dyadic_class_weight m b =      (Finset.range (2 ^ m)).sum (fun i => (b i).toNat))    (hne : ∃ i < 2 ^ m, b i = true) : b 0 = true ∧ b (2 ^ m - 1) = true := by  have h : m = (m - 1) + 1 := (Nat.sub_add_cancel hm).symm  rw [h] at hw hne ⊢  exact cycle_power_dyadic_tight_class_spanning_aux (m - 1) b hw hne
See it in the graphDiscuss this resultChallenge it