AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_rank_count_balance

theoremverified

At every nontrivial dyadic tree rank, exact long-edge coverage is a two-term occupancy balance L_j(v)+R_j(v+D-2^j)=1, uniformly in the radius. Each term is therefore at most one.

Statement

theorem cycle_power_dyadic_rank_count_balance
    (m j : ℕ) (hj : 1 ≤ j) (hjm : j < m) (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) =
      (range (2 ^ m)).sum (fun a => (x p a).toNat))
    (hexact : ∀ v : ℤ, (range (2 ^ j)).sum (fun a =>
      (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j)).toNat) = 1) :
    ∀ v : ℤ,
      (range (2 ^ (j - 1))).sum (fun a =>
        (x (v - ((2 ^ (j - 1) + a : ℕ) : ℤ)) (2 ^ (j - 1) + a)).toNat) +
      (range (2 ^ (j - 1))).sum (fun a =>
        (x (v + ((2 ^ m - 2 ^ j : ℕ) : ℤ) -
          ((2 ^ m - 2 ^ j + a : ℕ) : ℤ)) (2 ^ m - 2 ^ j + a)).toNat) = 1
Source
Uniform structural helper for OP-205 / RT-1 following arXiv:2610.15635 Section 3. This exact rank-flow identity is a helper, not a new graph covering theorem or research advance.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 2

The proof, explained

The theorem shows that exact long-edge coverage at rank j decomposes into a balance between two occupancy sums over 2^(j-1) points that total 1. The proof splits the exact-coverage sum of length 2^j into lower and upper halves of length q = 2^(j-1). The tightness hypothesis implies parent-child implications that simplify the conjunction in each half to a single indicator: the upper half reduces to the indicators at positions q + a, while the lower half reduces to shifted indicators at d + a where d = 2^m - 2^j. Substituting both reductions back into the coverage equation yields the two-term balance.

  1. Fix an arbitrary vertex v ∈ ℤ, define the block size q = 2^(j-1) and shift d = 2^m - 2^j, and establish 2^j = q + q and 2^j ≤ 2^m.

    We introduce the vertex v and define the half-rank length q = 2^(j-1) and displacement d = 2^m - 2^j. Arithmetic on exponents shows 2^j = 2^(j-1) * 2 = q + q, and monotonicity of powers gives 2^j ≤ 2^m since j < m.

    lines 15–23

    uses pow_succ, Nat.pow_le_pow_right

      intro v
      let q := 2 ^ (j - 1)
      let d := 2 ^ m - 2 ^ j
      have hpow : 2 ^ j = q + q := by
        have he : j = (j - 1) + 1 := by omega
        rw [he, pow_succ]
        dsimp [q]
        omega
      have hdm : 2 ^ j ≤ 2 ^ m := Nat.pow_le_pow_right (by decide) (by omega)
  2. Split the exact coverage sum of length 2^j at vertex v into a lower half and an upper half, both of length q, summing to 1.

    We instantiate the tightness property across all positions using cycle_power_dyadic_tight_class_parent. We then take the exact coverage hypothesis at v, replace 2^j with q + q, and split the sum over [0, q + q) into two sums over [0, q) via sum_range_add.

    lines 24–26

    uses cycle_power_dyadic_tight_class_parent, sum_range_add

      have hp := fun p => cycle_power_dyadic_tight_class_parent m j hj hjm (x p) (htight p)
      have he := hexact v
      rw [hpow, sum_range_add] at he
  3. The lower half of the sum simplifies to the sum over a ∈ [0, q) of x(v + d - (d + a), d + a).

    For every index a in the lower half (a < q = 2^(j-1)), the tightness implication states that if x is true at a + 2^m - 2^j = d + a, it must also be true at a. Hence the conjunction x(v - a, a) && x(v - a, d + a) simplifies to just x(v - a, d + a). Rewriting the vertex coordinate v - a as v + d - (d + a) gives the claimed lower sum.

    lines 27–42

    uses sum_congr, mem_range.mp

      have hlow : (range q).sum (fun a =>
          (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - (q + q))).toNat) =
          (range q).sum (fun a =>
            (x (v + (d : ℤ) - ((d + a : ℕ) : ℤ)) (d + a)).toNat) := by
        apply sum_congr rfl
        intro a ha
        have haq : a < q := mem_range.mp ha
        have hp' := (hp (v - (a : ℤ)) a (by omega)).1 haq
        have hi : a + 2 ^ m - 2 ^ j = d + a := by dsimp [d]; omega
        have hi' : a + 2 ^ m - (q + q) = d + a := by dsimp [d]; omega
        have hv : v + (d : ℤ) - ((d + a : ℕ) : ℤ) = v - (a : ℤ) := by push_cast; ring
        rw [hi] at hp'
        rw [hi', hv]
        cases hb : x (v - (a : ℤ)) (d + a)
        · simp [hb]
        · simp [hb, hp' hb]
  4. The upper half of the sum simplifies to the sum over a ∈ [0, q) of x(v - (q + a), q + a).

    For an index in the upper half, written as q + a with a < q, the rank index satisfies 2^(j-1) ≤ q + a < 2^j. By the tightness property, an active bit at q + a forces an active bit at q + a + 2^m - 2^j. Therefore, the conjunction reduces directly to the indicator at q + a.

    lines 43–55

    uses sum_congr, mem_range.mp, Bool.true_and, congrArg

      have hhigh : (range q).sum (fun a =>
          (x (v - ((q + a : ℕ) : ℤ)) (q + a) &&
            x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 ^ m - (q + q))).toNat) =
          (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat) := by
        apply sum_congr rfl
        intro a ha
        have haq : a < q := mem_range.mp ha
        have hp' := (hp (v - ((q + a : ℕ) : ℤ)) (q + a) (by omega)).2 (by omega)
        have hi : q + a + 2 ^ m - (q + q) = q + a + 2 ^ m - 2 ^ j := by omega
        rw [hi]
        cases hb : x (v - ((q + a : ℕ) : ℤ)) (q + a)
        · simp [hb]
        · simpa only [Bool.true_and] using congrArg Bool.toNat (hp' hb)
  5. The sum of the upper-half and lower-half occupancy terms equals 1. automation

    Substituting the simplified expressions for the lower and upper halves into the split exact-coverage equation yields lower + upper = 1. Commutativity of integer addition establishes upper + lower = 1, closing the goal.

    lines 56–59

      rw [hlow, hhigh] at he
      change (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat) +
        (range q).sum (fun a => (x (v + (d : ℤ) - ((d + a : ℕ) : ℤ)) (d + a)).toNat) = 1
      omega
pow_succ
For any element a of a monoid and natural number n, a^(n+1) = a^n * a.
Nat.pow_le_pow_right
For a positive base n, the power function is monotonic in the exponent: if i ≤ j, then n^i ≤ n^j.
cycle_power_dyadic_tight_class_parent
For a tight dyadic class of order m at rank j < m, an active bit at position a + 2^m - 2^j implies an active bit at position a when a < 2^(j-1), and an active bit at position a implies an active bit at a + 2^m - 2^j when 2^(j-1) ≤ a < 2^j.
sum_range_add
A sum over the range [0, n+m) splits into the sum over [0, n) plus the sum over [0, m) with indices shifted by n.
sum_congr
Two sums over finite sets are equal if the sets are equal and their summands agree at every element.
mem_range.mp
If m belongs to the range of n, then m < n.
Bool.true_and
The boolean conjunction true && b simplifies to b.
congrArg
Equality is preserved under function application: if a₁ = a₂, then f a₁ = f a₂.

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_rank_count_balance    (m j : ℕ) (hj : 1 ≤ j) (hjm : j < m) (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) =      (range (2 ^ m)).sum (fun a => (x p a).toNat))    (hexact : ∀ v : ℤ, (range (2 ^ j)).sum (fun a =>      (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j)).toNat) = 1) :    ∀ v : ℤ,      (range (2 ^ (j - 1))).sum (fun a =>        (x (v - ((2 ^ (j - 1) + a : ℕ) : ℤ)) (2 ^ (j - 1) + a)).toNat) +      (range (2 ^ (j - 1))).sum (fun a =>        (x (v + ((2 ^ m - 2 ^ j : ℕ) : ℤ) -          ((2 ^ m - 2 ^ j + a : ℕ) : ℤ)) (2 ^ m - 2 ^ j + a)).toNat) = 1 := by  intro v  let q := 2 ^ (j - 1)  let d := 2 ^ m - 2 ^ j  have hpow : 2 ^ j = q + q := by    have he : j = (j - 1) + 1 := by omega    rw [he, pow_succ]    dsimp [q]    omega  have hdm : 2 ^ j ≤ 2 ^ m := Nat.pow_le_pow_right (by decide) (by omega)  have hp := fun p => cycle_power_dyadic_tight_class_parent m j hj hjm (x p) (htight p)  have he := hexact v  rw [hpow, sum_range_add] at he  have hlow : (range q).sum (fun a =>      (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - (q + q))).toNat) =      (range q).sum (fun a =>        (x (v + (d : ℤ) - ((d + a : ℕ) : ℤ)) (d + a)).toNat) := by    apply sum_congr rfl    intro a ha    have haq : a < q := mem_range.mp ha    have hp' := (hp (v - (a : ℤ)) a (by omega)).1 haq    have hi : a + 2 ^ m - 2 ^ j = d + a := by dsimp [d]; omega    have hi' : a + 2 ^ m - (q + q) = d + a := by dsimp [d]; omega    have hv : v + (d : ℤ) - ((d + a : ℕ) : ℤ) = v - (a : ℤ) := by push_cast; ring    rw [hi] at hp'    rw [hi', hv]    cases hb : x (v - (a : ℤ)) (d + a)    · simp [hb]    · simp [hb, hp' hb]  have hhigh : (range q).sum (fun a =>      (x (v - ((q + a : ℕ) : ℤ)) (q + a) &&        x (v - ((q + a : ℕ) : ℤ)) (q + a + 2 ^ m - (q + q))).toNat) =      (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat) := by    apply sum_congr rfl    intro a ha    have haq : a < q := mem_range.mp ha    have hp' := (hp (v - ((q + a : ℕ) : ℤ)) (q + a) (by omega)).2 (by omega)    have hi : q + a + 2 ^ m - (q + q) = q + a + 2 ^ m - 2 ^ j := by omega    rw [hi]    cases hb : x (v - ((q + a : ℕ) : ℤ)) (q + a)    · simp [hb]    · simpa only [Bool.true_and] using congrArg Bool.toNat (hp' hb)  rw [hlow, hhigh] at he  change (range q).sum (fun a => (x (v - ((q + a : ℕ) : ℤ)) (q + a)).toNat) +    (range q).sum (fun a => (x (v + (d : ℤ) - ((d + a : ℕ) : ℤ)) (d + a)).toNat) = 1  omega
See it in the graphDiscuss this resultChallenge it