cycle_power_dyadic_outer_eighth_owner_order
In a tight exact fully ordinarily covered dyadic model of radius2^(k+3), monotone outer eighths imply that roots owning consecutive edges of distance7*2^k are nondecreasing. Counts and periodicity are not assumed.
Statement
theorem cycle_power_dyadic_outer_eighth_owner_order (k : ℕ) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (k+3) (x p) = (range (2^(k+3))).sum (fun a => (x p a).toNat)) (hexact : ∀ j < k+3, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+3)-2^j)).toNat) = 1) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(k+3) → ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+3)-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) (houter : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^k → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 7*2^k ≤ a → a ≤ b → b < 2^(k+3) → x p a = true → x p b = true)) : ∀ (v : ℤ) (a b : ℕ), a < 2^k → b < 2^k → x (v-(a : ℤ)) a = true → x (v-(a : ℤ)) (a+7*2^k) = true → x (v+1-(b : ℤ)) b = true → x (v+1-(b : ℤ)) (b+7*2^k) = true → b ≤ a+1
- Source
- Uniform structural helpers for OP-205 / RT-1, following arXiv:2610.15635. The new eight-block local extension remains unproved. These lemmas retain explicit shape/selected-missing hypotheses and do not settle any graph covering value; no research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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.
- 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_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_no_island_rank_owner_orderUnder no-island class shape, tightness, exact dyadic edges and full ordinary coverage, the unique owner roots of consecutive edges are…
The proof, explained
The original dyadic model x has radius 2^(k+3) = 8 * 2^k and is monotone on its two outer eighths [0, 2^k) and [7 * 2^k, 8 * 2^k). Applying dyadic pruning twice cuts out the middle six eighths, compressing the two outer eighths into a smaller model z of radius 2^(k+1) = 2 * 2^k that inherits tightness, exactness, and covering. Monotonicity of the outer eighths ensures that z satisfies the "no island" shape condition, while edges of distance 7 * 2^k in x correspond to edges of distance 2^k at level k in z. The result b ≤ a + 1 then follows by applying the known owner-ordering theorem cycle_power_dyadic_no_island_rank_owner_order to z.
The dyadic scales k+1, k+2, and k+3 correspond to lengths 2q, 4q, and 8q, where q = 2^k > 0.
We set q = 2^k, which is strictly positive by `Nat.two_pow_pos`. Applying the successor rule for powers `pow_succ` and linear arithmetic shows that 2^(k+1) = 2q, 2^(k+2) = 4q, and 2^(k+3) = 8q.
uses
Nat.two_pow_pos,pow_succlet q := 2^k have hq : 0 < q := Nat.two_pow_pos _ have hP₁ : 2^(k+1)=2*q := by dsimp [q]; rw [pow_succ]; omega have hP₂ : 2^(k+2)=4*q := by rw [show k+2=(k+1)+1 by omega,pow_succ,hP₁]; omega have hP₃ : 2^(k+3)=8*q := by rw [show k+3=(k+2)+1 by omega,pow_succ,hP₂]; omega
Two successive dyadic pruning steps reduce the model from radius 8q to radius 2q, preserving tightness, exactness, and covering.
We define y by pruning x at scale k+1 (reducing size from 8q to 4q), and z by pruning y at scale k (reducing size from 4q to 2q). Applying the preservation lemmas `cycle_power_dyadic_tight_class_prune`, `cycle_power_dyadic_prune_exact`, and `cycle_power_dyadic_prune_cover` at each stage ensures that y and z inherit tightness, exactness, and the full covering property from x.
uses
cycle_power_dyadic_tight_class_prune,cycle_power_dyadic_prune_exact,cycle_power_dyadic_prune_coverlet y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift (k+1) (x p) let z : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (y p) have hyT := fun p => cycle_power_dyadic_tight_class_prune (k+1) (x p) (htight p) have hyE := cycle_power_dyadic_prune_exact (k+1) x hexact have hyC := cycle_power_dyadic_prune_cover (k+1) x htight hcover have hzT := fun p => cycle_power_dyadic_tight_class_prune k (y p) (hyT p) have hzE := cycle_power_dyadic_prune_exact k y hyE have hzC := cycle_power_dyadic_prune_cover k y hyT hyC
The pruned model z on [0, 2q) satisfies z(p, i) = x(p, i) for i < q and z(p, i) = x(p, i + 6q) for q ≤ i < 2q.
Unfolding the two pruning lifts, an index i < q takes the first branch of both conditionals via `if_pos`, giving z(p, i) = x(p, i) (`hzLow`). For q ≤ i < 2q, both conditionals take the second branch via `if_neg`, adding an accumulated offset of 2q + 4q = 6q, which yields z(p, i) = x(p, i + 6q) (`hzHigh`). The pruned model z thus glues together the first eighth [0, q) and the last eighth [7q, 8q) of x.
uses
if_pos,if_neghave hzLow (p : ℤ) (i : ℕ) (hi : i < q) : z p i = x p i := by dsimp [z,y,cycle_power_dyadic_b_lift] rw [if_pos hi,if_pos (by omega)] have hzHigh (p : ℤ) (i : ℕ) (hi₀ : q ≤ i) (hi₁ : i < 2*q) : z p i = x p (i+6*q) := by dsimp [z,y,cycle_power_dyadic_b_lift] rw [if_neg (by omega),if_neg (by omega)] congr 1 omega
The pruned model z satisfies the "no island" shape condition: no true value is flanked by false values.
Suppose a < b < c < 2^(k+1) with z(p, a) = false and z(p, b) = true. If b < q, then a < q, so both a and b fall in the first eighth where z coincides with x; the downward monotonicity of x on [0, q) forces x(p, a) = true, a contradiction. If b ≥ q, then c > b ≥ q, so both b and c fall in the second half where z maps to the eighth eighth [7q, 8q); the upward monotonicity of x on [7q, 8q) implies x(p, c + 6q) = true, so z(p, c) = true.
have hzShape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+1) → z p a = false → z p b = true → z p c = true := by intro p a b c hab hbc hc ha hb by_cases hbq : b < q · have haq : a < q := by omega rw [hzLow p a haq] at ha rw [hzLow p b hbq] at hb have hh := (houter p).1 a b (by omega) hbq hb rw [ha] at hh contradiction · have hcb : q ≤ c := by omega rw [hzHigh p b (by omega) (by omega)] at hb rw [hzHigh p c hcb (by omega)] exact (houter p).2 (b+6*q) (c+6*q) (by dsimp [q] at *; omega) (by omega) (by omega) hb
At level k in z, the upper pairing partner of a < q corresponds to an edge of length 7q in x.
For a < q, the edge endpoint at level k in z is a + 2^(k+1) - 2^k = a + q. Because q ≤ a + q < 2q, `hzHigh` rewrites z(p, a + q) to x(p, a + q + 6q) = x(p, a + 7q) (`hzPair`).
have hzPair (p : ℤ) (a : ℕ) (ha : a < q) : z p (a+2^(k+1)-2^k) = x p (a+7*q) := by have hi : a+2^(k+1)-2^k=a+q := by dsimp [q]; omega rw [hi,hzHigh p (a+q) (by omega) (by omega)] congr 1 omega
Consecutive edge owners satisfy b ≤ a + 1.
We introduce the vertices v, v+1 and edge owners a, b < 2^k. The edge ownership hypotheses for x at distance 7 * 2^k translate directly via `hzLow` and `hzPair` into edge ownership hypotheses in z at scale k+1 and level k. Applying the existing owner-ordering theorem `cycle_power_dyadic_no_island_rank_owner_order` to z closes the goal.
uses
cycle_power_dyadic_no_island_rank_owner_orderintro v a b ha hb ha₀ ha₁ hb₀ hb₁ apply cycle_power_dyadic_no_island_rank_owner_order (k+1) z hzT hzE hzShape hzC k (by omega) v a b ha hb · simpa only [hzLow _ a ha] using ha₀ · simpa only [hzPair _ a ha] using ha₁ · simpa only [hzLow _ b hb] using hb₀ · simpa only [hzPair _ b hb] using hb₁
Nat.two_pow_pos- Powers of 2 with natural exponents are strictly positive (0 < 2^w).
pow_succ- Successor power rule in a monoid: a^(n+1) = a^n * a.
cycle_power_dyadic_tight_class_prune- Pruning a tight configuration at scale k+2 preserves the tight class weight condition at scale k+1.
cycle_power_dyadic_prune_exact- Pruning an exact dyadic model at scale k+2 preserves exactness at scale k+1 for all levels j < k+1.
cycle_power_dyadic_prune_cover- In a tight model, if every distance d < 2^(k+2) is covered by a true-true pair, then pruning to scale k+1 preserves covering for all distances d < 2^(k+1).
if_pos- An if-then-else evaluates to its then-branch when the condition is true.
if_neg- An if-then-else evaluates to its else-branch when the condition is false.
cycle_power_dyadic_no_island_rank_owner_order- In a tight, exact, covered dyadic model of radius 2^m satisfying the "no island" shape condition, consecutive edge owners at level j < m satisfy b ≤ a + 1.
- The proof prunes the dyadic model twice in succession (first from radius 8q to 4q, then to 2q) rather than in a single step, reflecting the single-step definition of `cycle_power_dyadic_b_lift`.
- Index arithmetic for the offsets and bounds is dispatched by `omega`.
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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_dyadic_outer_eighth_owner_order (k : ℕ) (x : ℤ → ℕ → Bool) (htight : ∀ p, cycle_power_dyadic_class_weight (k+3) (x p) = (range (2^(k+3))).sum (fun a => (x p a).toNat)) (hexact : ∀ j < k+3, ∀ v : ℤ, (range (2^j)).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^(k+3)-2^j)).toNat) = 1) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^(k+3) → ∀ v : ℤ, ∃ a : ℕ, a < 2^(k+3)-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) (houter : ∀ p : ℤ, (∀ a b : ℕ, a ≤ b → b < 2^k → x p b = true → x p a = true) ∧ (∀ a b : ℕ, 7*2^k ≤ a → a ≤ b → b < 2^(k+3) → x p a = true → x p b = true)) : ∀ (v : ℤ) (a b : ℕ), a < 2^k → b < 2^k → x (v-(a : ℤ)) a = true → x (v-(a : ℤ)) (a+7*2^k) = true → x (v+1-(b : ℤ)) b = true → x (v+1-(b : ℤ)) (b+7*2^k) = true → b ≤ a+1 := by let q := 2^k have hq : 0 < q := Nat.two_pow_pos _ have hP₁ : 2^(k+1)=2*q := by dsimp [q]; rw [pow_succ]; omega have hP₂ : 2^(k+2)=4*q := by rw [show k+2=(k+1)+1 by omega,pow_succ,hP₁]; omega have hP₃ : 2^(k+3)=8*q := by rw [show k+3=(k+2)+1 by omega,pow_succ,hP₂]; omega let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift (k+1) (x p) let z : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (y p) have hyT := fun p => cycle_power_dyadic_tight_class_prune (k+1) (x p) (htight p) have hyE := cycle_power_dyadic_prune_exact (k+1) x hexact have hyC := cycle_power_dyadic_prune_cover (k+1) x htight hcover have hzT := fun p => cycle_power_dyadic_tight_class_prune k (y p) (hyT p) have hzE := cycle_power_dyadic_prune_exact k y hyE have hzC := cycle_power_dyadic_prune_cover k y hyT hyC have hzLow (p : ℤ) (i : ℕ) (hi : i < q) : z p i = x p i := by dsimp [z,y,cycle_power_dyadic_b_lift] rw [if_pos hi,if_pos (by omega)] have hzHigh (p : ℤ) (i : ℕ) (hi₀ : q ≤ i) (hi₁ : i < 2*q) : z p i = x p (i+6*q) := by dsimp [z,y,cycle_power_dyadic_b_lift] rw [if_neg (by omega),if_neg (by omega)] congr 1 omega have hzShape : ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^(k+1) → z p a = false → z p b = true → z p c = true := by intro p a b c hab hbc hc ha hb by_cases hbq : b < q · have haq : a < q := by omega rw [hzLow p a haq] at ha rw [hzLow p b hbq] at hb have hh := (houter p).1 a b (by omega) hbq hb rw [ha] at hh contradiction · have hcb : q ≤ c := by omega rw [hzHigh p b (by omega) (by omega)] at hb rw [hzHigh p c hcb (by omega)] exact (houter p).2 (b+6*q) (c+6*q) (by dsimp [q] at *; omega) (by omega) (by omega) hb have hzPair (p : ℤ) (a : ℕ) (ha : a < q) : z p (a+2^(k+1)-2^k) = x p (a+7*q) := by have hi : a+2^(k+1)-2^k=a+q := by dsimp [q]; omega rw [hi,hzHigh p (a+q) (by omega) (by omega)] congr 1 omega intro v a b ha hb ha₀ ha₁ hb₀ hb₁ apply cycle_power_dyadic_no_island_rank_owner_order (k+1) z hzT hzE hzShape hzC k (by omega) v a b ha hb · simpa only [hzLow _ a ha] using ha₀ · simpa only [hzPair _ a ha] using ha₁ · simpa only [hzLow _ b hb] using hb₀ · simpa only [hzPair _ b hb] using hb₁