AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_tight_class_parent

theoremverified

Equality in the dyadic class weight bound forces all rooted-tree parent implications at every smaller dyadic scale, uniformly in the arc length.

Statement

theorem cycle_power_dyadic_tight_class_parent
    (m j : ℕ) (hj : 1 ≤ j) (hjm : j < m) (b : ℕ → Bool)
    (htight : cycle_power_dyadic_class_weight m b =
      (range (2 ^ m)).sum (fun a => (b a).toNat)) :
    ∀ a < 2 ^ j,
      (a < 2 ^ (j - 1) → b (a + 2 ^ m - 2 ^ j) = true → b a = true) ∧
      (2 ^ (j - 1) ≤ a → b a = true → b (a + 2 ^ m - 2 ^ j) = true)
Source
Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635 Section 3. These class-model, pruning and colour-rigidity lemmas do not establish the unresolved graph covering value. No research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 16

The proof, explained

The theorem is proved by strong induction on the cycle dimension m = k + 2. For the maximal scale j = k + 1, the parent implications follow directly from the middle-parent tightness lemma cycle_power_dyadic_tight_class_middle_parent. For any strictly smaller scale j ≤ k, pruning produces a tight configuration at dimension k + 1, allowing the induction hypothesis to be applied and translated back to the original configuration via index preservation lemmas.

  1. Set up strong induction on m and rewrite m = k + 2 using m ≥ 2.

    We proceed by strong induction on m, generalizing over the scale j and configuration b. Since 1 ≤ j < m, we must have m ≥ 2, so we can write m = k + 2 for k = m - 2. The recurrence pow_succ gives 2^(k+1) = 2 * 2^k and 2^(k+2) = 2 * 2^(k+1).

    lines 10–16

    uses Nat.strong_induction_on, pow_succ

      induction m using Nat.strong_induction_on generalizing j b with
      | h m ih =>
        have hm : 2 ≤ m := by omega
        obtain ⟨k, hk⟩ : ∃ k, m = k + 2 := ⟨m - 2, by omega⟩
        subst m
        have hH : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega
        have hD : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega
  2. When j = k + 1, reduce the claim for any a < 2^(k+1) to two parent implications on the middle intervals.

    We branch on whether j = k + 1. In this top-scale case, cycle_power_dyadic_tight_class_middle_parent establishes forward and backward implications between the middle halves. For any a < 2^(k+1), the shifted index a + 2^(k+2) - 2^(k+1) simplifies to a + 2^(k+1) and the scale exponent j - 1 simplifies to k. Splitting the goal conjunction leaves one implication for a < 2^k and one for 2^k ≤ a.

    lines 17–24

    uses cycle_power_dyadic_tight_class_middle_parent

        by_cases hjtop : j = k + 1
        · subst j
          have hp := cycle_power_dyadic_tight_class_middle_parent k b htight
          intro a ha
          have hindex : a + 2 ^ (k + 2) - 2 ^ (k + 1) = a + 2 ^ (k + 1) := by omega
          have hpred : k + 1 - 1 = k := by omega
          rw [hindex, hpred]
          constructor
  3. When j = k + 1 and a < 2^k, b(a + 2^(k+1)) = true implies b(a) = true.

    Assuming a < 2^k and b(a + 2^(k+1)) = true, the shifted index satisfies 2^(k+1) ≤ a + 2^(k+1) < 3 * 2^k. The backward implication of the middle parent lemma applies to this index, yielding b((a + 2^(k+1)) - 2^(k+1)) = true, which simplifies to b(a) = true by Nat.add_sub_cancel_right.

    lines 25–27

    uses Nat.add_sub_cancel_right

          · intro haq hx
            have hh := hp.2 (a + 2 ^ (k + 1)) (by omega) (by omega) hx
            simpa only [Nat.add_sub_cancel_right] using hh
  4. When j = k + 1 and 2^k ≤ a < 2^(k+1), b(a) = true implies b(a + 2^(k+1)) = true.

    Assuming 2^k ≤ a < 2^(k+1) and b(a) = true, the forward implication of the middle parent lemma directly yields b(a + 2^(k+1)) = true.

    lines 28–29

          · intro haq hx
            exact hp.1 a haq ha hx
  5. When j ≤ k, the induction hypothesis applies to the pruned lift configuration at dimension k + 1.

    When j ≠ k + 1, we have j ≤ k since j < k + 2. Lemma cycle_power_dyadic_tight_class_prune shows that pruning the configuration produces a tight configuration at dimension k + 1. Since k + 1 < k + 2 and j < k + 1, we may apply the induction hypothesis ih to this pruned lift configuration at scale j.

    lines 30–33

    uses cycle_power_dyadic_tight_class_prune

        · have hjk : j ≤ k := by omega
          have hs := cycle_power_dyadic_tight_class_prune k b htight
          have hi := ih (k + 1) (by omega) j hj (by omega)
            (cycle_power_dyadic_b_lift k b) hs
  6. The parent implications for the pruned lift transfer to b, completing the case j ≤ k.

    Evaluating the induction hypothesis at any a < 2^j gives the parent implications for the lifted configuration. Because j ≤ k and a < 2^j, cycle_power_dyadic_b_lift_low rewrites the base index to b(a), and cycle_power_dyadic_b_lift_high rewrites the shifted index to b(a + 2^(k+2) - 2^j), concluding the proof.

    lines 34–37

    uses cycle_power_dyadic_b_lift_low, cycle_power_dyadic_b_lift_high

          intro a ha
          have hh := hi a ha
          simpa only [cycle_power_dyadic_b_lift_low k j a hjk ha,
            cycle_power_dyadic_b_lift_high k j a hjk ha] using hh
Nat.strong_induction_on
Strong induction principle on ℕ: to prove P(n) for all n, it suffices to prove P(n) assuming P(m) holds for all m < n.
pow_succ
In any monoid, a^(n + 1) = a^n * a.
cycle_power_dyadic_tight_class_middle_parent
For a tight configuration at dimension k + 2, truth of b(a) for 2^k ≤ a < 2^(k+1) implies truth of b(a + 2^(k+1)), and truth of b(a) for 2^(k+1) ≤ a < 3 * 2^k implies truth of b(a - 2^(k+1)).
Nat.add_sub_cancel_right
For natural numbers, (n + m) - m = n.
cycle_power_dyadic_tight_class_prune
If a configuration b is tight at dimension k + 2, then its pruned lift configuration is tight at dimension k + 1.
cycle_power_dyadic_b_lift_low
For a scale j ≤ k and an index a < 2^j, the pruned lift configuration agrees with b at a.
cycle_power_dyadic_b_lift_high
For a scale j ≤ k and an index a < 2^j, the pruned lift configuration at the shifted index a + 2^(k+1) - 2^j agrees with b at a + 2^(k+2) - 2^j.

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 Finsettheorem cycle_power_dyadic_tight_class_parent    (m j : ℕ) (hj : 1 ≤ j) (hjm : j < m) (b : ℕ → Bool)    (htight : cycle_power_dyadic_class_weight m b =      (range (2 ^ m)).sum (fun a => (b a).toNat)) :    ∀ a < 2 ^ j,      (a < 2 ^ (j - 1) → b (a + 2 ^ m - 2 ^ j) = true → b a = true) ∧      (2 ^ (j - 1) ≤ a → b a = true → b (a + 2 ^ m - 2 ^ j) = true) := by  induction m using Nat.strong_induction_on generalizing j b with  | h m ih =>    have hm : 2 ≤ m := by omega    obtain ⟨k, hk⟩ : ∃ k, m = k + 2 := ⟨m - 2, by omega⟩    subst m    have hH : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega    have hD : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ]; omega    by_cases hjtop : j = k + 1    · subst j      have hp := cycle_power_dyadic_tight_class_middle_parent k b htight      intro a ha      have hindex : a + 2 ^ (k + 2) - 2 ^ (k + 1) = a + 2 ^ (k + 1) := by omega      have hpred : k + 1 - 1 = k := by omega      rw [hindex, hpred]      constructor      · intro haq hx        have hh := hp.2 (a + 2 ^ (k + 1)) (by omega) (by omega) hx        simpa only [Nat.add_sub_cancel_right] using hh      · intro haq hx        exact hp.1 a haq ha hx    · have hjk : j ≤ k := by omega      have hs := cycle_power_dyadic_tight_class_prune k b htight      have hi := ih (k + 1) (by omega) j hj (by omega)        (cycle_power_dyadic_b_lift k b) hs      intro a ha      have hh := hi a ha      simpa only [cycle_power_dyadic_b_lift_low k j a hjk ha,        cycle_power_dyadic_b_lift_high k j a hjk ha] using hh
See it in the graphDiscuss this resultChallenge it