cycle_power_dyadic_no_island_rank_owner_order
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
- 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_no_island_pruneDeleting middle quarters preserves the no-island property of a Boolean class.
- cycle_power_dyadic_prune_exactDeleting the middle two quarters of every class preserves every smaller-scale exact dyadic long-edge count, without changing the class…
- cycle_power_dyadic_prune_coverDeleting each tight dyadic class's middle two quarters and compressing its outer quarters preserves coverage of all distances smaller than…
- cycle_power_dyadic_tight_class_pruneDeleting a tight dyadic class's middle two quarters and compressing the remaining outer quarters preserves equality between its dyadic…
- cycle_power_dyadic_b_lift_lowMiddle-quarter pruning preserves every smaller-scale left position.
- cycle_power_dyadic_b_lift_highMiddle-quarter pruning maps every smaller-scale right endpoint to its original larger-scale position.
- cycle_power_dyadic_no_island_half_owner_orderIn a tight dyadic full-coverage class model with explicit no-island shapes, the root owning the next half-radius edge is at least the root…
- 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.
- Used by 1
- cycle_power_dyadic_outer_eighth_owner_orderIn a tight exact fully ordinarily covered dyadic model of radius2^(k+3), monotone outer eighths imply that roots owning consecutive edges…
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.
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.
uses
Nat.strong_induction_oninduction m using Nat.strong_induction_on generalizing x with | h m ih => intro j hj v a b ha hb ha0 ha1 hb0 hb1
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.
by_cases hj0 : j=0 · subst j; norm_num at ha hb; omega
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.
have hm : 2 ≤ m := by omega obtain ⟨k,hk⟩ : ∃ k, m=k+2 := ⟨m-2,by omega⟩ subst m
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.
uses
pow_succ,cycle_power_dyadic_no_island_half_owner_orderby_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)
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.
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
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.
uses
cycle_power_dyadic_b_lift_low,cycle_power_dyadic_b_lift_highapply 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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