AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_no_island_rank_owner_order

theoremverified

Under no-island class shape, tightness, exact dyadic edges and full ordinary coverage, the unique owner roots of consecutive edges are nondecreasing at every dyadic long distance.

Statement

theorem cycle_power_dyadic_no_island_rank_owner_order
    (m : ℕ) (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) =
      (range (2^m)).sum (fun a => (x p a).toNat))
    (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1)
    (hshape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^m →
      x p a = false → x p b = true → x p c = true)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ,
      ∃ a : ℕ, a < 2^m-d ∧ x (v-(a : ℤ)) a = true ∧
        x (v-(a : ℤ)) (a+d) = true) :
    ∀ j < m, ∀ (v : ℤ) (a b : ℕ), a < 2^j → b < 2^j →
      x (v-(a : ℤ)) a = true →
      x (v-(a : ℤ)) (a+2^m-2^j) = true →
      x (v+1-(b : ℤ)) b = true →
      x (v+1-(b : ℤ)) (b+2^m-2^j) = true → b ≤ a+1
Source
Uniform conditional structural helper for OP-205 / RT-1 following arXiv:2610.15635 Section 3. The middle-bit fullness assumptions and smaller-quarter monotonicity are explicit when used; no optimal-count classification, graph covering value or research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
Used by 1

The proof, explained

The theorem is proved by strong induction on m. For the base scale j = 0, the roots a, b < 2^0 are forced to 0, making b ≤ a + 1 trivial. For j > 0, we write m = k + 2; when j is the top scale k + 1, the claim reduces directly to the half-scale owner ordering theorem. When j ≤ k, we prune the configuration to scale k + 1 using a dyadic lift operator that preserves tightness, exactness, no-island shape, and coverage, allowing the induction hypothesis at scale k + 1 to conclude the result.

  1. We set up a strong induction on m, generalizing over the configuration x, and introduce the scale j < m, base position v, and edge roots a, b < 2^j.

    We induct on m using strong induction while generalizing x, so that the inductive hypothesis can be applied to pruned configurations at smaller scales. We then introduce the dyadic scale j < m, the fibre coordinate v ∈ ℤ, the edge roots a, b < 2^j, and the hypotheses that a and b are endpoints of dyadic edges of length 2^m - 2^j along the fibres at v and v + 1 respectively.

    lines 19–21

    uses Nat.strong_induction_on

      induction m using Nat.strong_induction_on generalizing x with
      | h m ih =>
        intro j hj v a b ha hb ha0 ha1 hb0 hb1
  2. If j = 0, the inequality b ≤ a + 1 holds trivially.

    When j = 0, the upper bounds a < 2^0 = 1 and b < 2^0 = 1 force a = 0 and b = 0. The inequality b ≤ a + 1 then reduces to 0 ≤ 1, which holds immediately.

    lines 22–23

        by_cases hj0 : j=0
        · subst j; norm_num at ha hb; omega
  3. For j > 0, the dimension satisfies m ≥ 2, so we can write m = k + 2 for some k ∈ ℕ.

    Because 0 < j < m, we have m ≥ 2. We can therefore substitute m = k + 2 with k = m - 2.

    lines 24–26

        have hm : 2 ≤ m := by omega
        obtain ⟨k,hk⟩ : ∃ k, m=k+2 := ⟨m-2,by omega⟩
        subst m
  4. If j = k + 1, the inequality b ≤ a + 1 follows from the half-scale owner ordering theorem.

    When j = k + 1 = m - 1, the edge jump distance is 2^(k+2) - 2^(k+1) = 2^(k+1). This corresponds to half-length edges, so the claim b ≤ a + 1 follows directly from the previously established half-length owner ordering theorem cycle_power_dyadic_no_island_half_owner_order.

    lines 27–34

    uses pow_succ, cycle_power_dyadic_no_island_half_owner_order

        by_cases hjtop : j=k+1
        · subst j
          have hD : 2^(k+2)=2*2^(k+1) := by rw [pow_succ]; omega
          have hiA : a+2^(k+2)-2^(k+1)=a+2^(k+1) := by omega
          have hiB : b+2^(k+2)-2^(k+1)=b+2^(k+1) := by omega
          exact cycle_power_dyadic_no_island_half_owner_order k x htight hexact
            hshape hcover v a b ha hb ha0 (by simpa only [hiA] using ha1)
            hb0 (by simpa only [hiB] using hb1)
  5. When j ≤ k, the pruned configuration y satisfies tightness, exactness, no-island shape, and coverage at scale k + 1.

    For scales j < k + 1, we define a reduced configuration y at scale k + 1 by applying cycle_power_dyadic_b_lift k to each fibre of x. We verify that all four structural hypotheses are inherited at scale k + 1: tightness via cycle_power_dyadic_tight_class_prune, exact dyadic edge counts via cycle_power_dyadic_prune_exact, no-island shape via cycle_power_dyadic_no_island_prune, and ordinary coverage via cycle_power_dyadic_prune_cover.

    lines 35–41

    uses cycle_power_dyadic_tight_class_prune, cycle_power_dyadic_prune_exact, cycle_power_dyadic_no_island_prune, cycle_power_dyadic_prune_cover

        · let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (x p)
          have hty : ∀ p, cycle_power_dyadic_class_weight (k+1) (y p) =
              (range (2^(k+1))).sum (fun a => (y p a).toNat) :=
            fun p => cycle_power_dyadic_tight_class_prune k (x p) (htight p)
          have hey := cycle_power_dyadic_prune_exact k x hexact
          have hsy := fun p => cycle_power_dyadic_no_island_prune k (x p) (hshape p)
          have hcy := cycle_power_dyadic_prune_cover k x htight hcover
  6. Applying the induction hypothesis to y at scale k + 1 yields b ≤ a + 1.

    We invoke the induction hypothesis at scale k + 1 < m on configuration y with scale index j ≤ k. Because a, b < 2^j, the lift operator preserves the values at the lower endpoints a and b (by cycle_power_dyadic_b_lift_low) and at the upper endpoints a + 2^(k+1) - 2^j and b + 2^(k+1) - 2^j (by cycle_power_dyadic_b_lift_high). Thus the edge hypotheses for y match those given for x, and the induction hypothesis concludes b ≤ a + 1.

    lines 42–46

    uses cycle_power_dyadic_b_lift_low, cycle_power_dyadic_b_lift_high

          apply ih (k+1) (by omega) y hty hey hsy hcy j (by omega) v a b ha hb
          · simpa only [y,cycle_power_dyadic_b_lift_low k j a (by omega) ha] using ha0
          · simpa only [y,cycle_power_dyadic_b_lift_high k j a (by omega) ha] using ha1
          · simpa only [y,cycle_power_dyadic_b_lift_low k j b (by omega) hb] using hb0
          · simpa only [y,cycle_power_dyadic_b_lift_high k j b (by omega) hb] using hb1
Nat.strong_induction_on
Strong induction on natural numbers: to prove a property for all n, it suffices to prove it for n assuming it holds for all strictly smaller m < n.
pow_succ
In any monoid, a^(n + 1) = a^n * a.
cycle_power_dyadic_no_island_half_owner_order
Under tightness, exact dyadic edges, no-island shape, and coverage at scale k + 2, consecutive roots of half-length edges (scale j = k + 1, jump 2^(k + 1)) satisfy b ≤ a + 1.
cycle_power_dyadic_tight_class_prune
Pruning a tight configuration at scale k + 2 via the dyadic lift operator yields a tight configuration at scale k + 1.
cycle_power_dyadic_prune_exact
Pruning an exact dyadic configuration at scale k + 2 preserves exact dyadic edge counts for all j < k + 1 at scale k + 1.
cycle_power_dyadic_no_island_prune
Pruning a configuration satisfying the no-island shape condition at scale k + 2 preserves the no-island shape condition at scale k + 1.
cycle_power_dyadic_prune_cover
Pruning a tight configuration with full ordinary edge coverage at scale k + 2 yields full ordinary edge coverage at scale k + 1.
cycle_power_dyadic_b_lift_low
For j ≤ k and offset a < 2^j, the pruned configuration at a agrees with the original configuration at a.
cycle_power_dyadic_b_lift_high
For j ≤ k and offset a < 2^j, the pruned configuration at a + 2^(k+1) - 2^j agrees with the original configuration 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_no_island_rank_owner_order    (m : ℕ) (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) =      (range (2^m)).sum (fun a => (x p a).toNat))    (hexact : ∀ j < m, ∀ v : ℤ, (range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1)    (hshape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^m →      x p a = false → x p b = true → x p c = true)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ,      ∃ a : ℕ, a < 2^m-d ∧ x (v-(a : ℤ)) a = true ∧        x (v-(a : ℤ)) (a+d) = true) :    ∀ j < m, ∀ (v : ℤ) (a b : ℕ), a < 2^j → b < 2^j →      x (v-(a : ℤ)) a = true →      x (v-(a : ℤ)) (a+2^m-2^j) = true →      x (v+1-(b : ℤ)) b = true →      x (v+1-(b : ℤ)) (b+2^m-2^j) = true → b ≤ a+1 := by  induction m using Nat.strong_induction_on generalizing x with  | h m ih =>    intro j hj v a b ha hb ha0 ha1 hb0 hb1    by_cases hj0 : j=0    · subst j; norm_num at ha hb; omega    have hm : 2 ≤ m := by omega    obtain ⟨k,hk⟩ : ∃ k, m=k+2 := ⟨m-2,by omega⟩    subst m    by_cases hjtop : j=k+1    · subst j      have hD : 2^(k+2)=2*2^(k+1) := by rw [pow_succ]; omega      have hiA : a+2^(k+2)-2^(k+1)=a+2^(k+1) := by omega      have hiB : b+2^(k+2)-2^(k+1)=b+2^(k+1) := by omega      exact cycle_power_dyadic_no_island_half_owner_order k x htight hexact        hshape hcover v a b ha hb ha0 (by simpa only [hiA] using ha1)        hb0 (by simpa only [hiB] using hb1)    · let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (x p)      have hty : ∀ p, cycle_power_dyadic_class_weight (k+1) (y p) =          (range (2^(k+1))).sum (fun a => (y p a).toNat) :=        fun p => cycle_power_dyadic_tight_class_prune k (x p) (htight p)      have hey := cycle_power_dyadic_prune_exact k x hexact      have hsy := fun p => cycle_power_dyadic_no_island_prune k (x p) (hshape p)      have hcy := cycle_power_dyadic_prune_cover k x htight hcover      apply ih (k+1) (by omega) y hty hey hsy hcy j (by omega) v a b ha hb      · simpa only [y,cycle_power_dyadic_b_lift_low k j a (by omega) ha] using ha0      · simpa only [y,cycle_power_dyadic_b_lift_high k j a (by omega) ha] using ha1      · simpa only [y,cycle_power_dyadic_b_lift_low k j b (by omega) hb] using hb0      · simpa only [y,cycle_power_dyadic_b_lift_high k j b (by omega) hb] using hb1
See it in the graphDiscuss this resultChallenge it