cycle_power_dyadic_full_gap_sides_convex
In a tight exact full ordinary-coverage dyadic model, all compressed sides between full roots zero and g are intervals when g lies between half and the full radius.
Statement
theorem cycle_power_dyadic_full_gap_sides_convex (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool) (htight : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) = (range (2^m)).sum (fun i => (x p i).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) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ, ∃ a : ℕ, a < 2^m-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) (g : ℕ) (hlo : 2^(m-1) ≤ g) (hg : g ≤ 2^m) (hfull₀ : ∀ i < 2^m, x 0 i = true) (hfullg : ∀ i < 2^m, x (g : ℤ) i = true) : let A : Fin (g-1) → Finset (Fin g) := fun r => cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) let B : Fin (g-1) → Finset (Fin g) := fun r => cycle_power_gap_right_side (2^m) g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ A r → k ∈ A r → j ∈ A r) ∧ (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ B r → k ∈ B r → j ∈ B r)
- Source
- Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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_exact_endpointsExact ownership of all dyadic distances in a radius-2^m model with positive exponent forces both endpoints of every rooted class to be…
- ordered_biclique_dyadic_tree_intervalsA nonempty biclique at each cut of Fin g, separated by that cut and covering every ordered pair, has interval sides when each biclique…
- cycle_power_gap_left_sideThe lower-block vertices of a rooted profile, represented by their absolute positions in Fin g.
- cycle_power_gap_right_sideThe upper-block vertices of a rooted profile, represented in Fin g after subtracting the radius.
- cycle_power_gap_ordinary_side_coverOrdinary distance coverage in an integer radius-D model, restricted to g at most D, gives a cut-separated biclique cover of the complete…
- cycle_power_gap_exact_side_ownerExact distance D-R ownership in an integer model gives unique compressed gap-side owners for every forward distance-R pair on Fin g, when…
- cycle_power_dyadic_gap_side_treeBetween two full roots at distance g at most the radius, the compressed sides of every interior tight class satisfy the tree identity:…
- Used by 1
- cycle_power_dyadic_full_gap_class_no_islandIn a tight exact full ordinary-coverage dyadic model, every class rooted strictly between full roots zero and g has no selected island…
The proof, explained
The proof reduces convexity of the gap sides A(r) and B(r) to a general graph-theoretic theorem, `ordered_biclique_dyadic_tree_intervals`, which guarantees interval-convexity for any ordered dyadic biclique family satisfying six structural axioms. The separation bounds follow from the definition of the gap sides, and each side is nonempty because exactness forces the origin of every fiber to be true. The remaining hypotheses—pair coverage, the dyadic tree cardinality formula, and unique coverage of dyadic steps—are discharged directly by library lemmas establishing these properties for tight and exact dyadic models.
To show that each A(r) and B(r) is convex, it suffices to verify the six structural hypotheses of the ordered dyadic tree theorem.
We invoke `ordered_biclique_dyadic_tree_intervals` for g and m. This reduces interval-convexity of the families A(r) and B(r) to six properties: left-side lower bounds, right-side upper bounds, nonemptiness of each union A(r) ∪ B(r), coverage of all pairs i < j, the tree cardinality equation, and unique coverage of dyadic steps k + 2ʲ = i.
uses
ordered_biclique_dyadic_tree_intervalsclassical dsimp only apply ordered_biclique_dyadic_tree_intervals g m hm hlo
For every r < g - 1 and every i ∈ A(r), we have r < i.
By the definition of the left gap side A(r), every element i satisfies r + 1 ≤ i. Linear arithmetic then yields r < i.
· intro r i hi have := (mem_filter.mp hi).2.1 omega
For every r < g - 1 and every i ∈ B(r), we have i ≤ r.
By the definition of the right gap side B(r), every element i satisfies i < r + 1. Linear arithmetic then yields i ≤ r.
· intro r i hi have := (mem_filter.mp hi).2.1 omega
For every r < g - 1, the union A(r) ∪ B(r) is nonempty.
Since r < g - 1, the index i = r + 1 satisfies i < g. By `cycle_power_dyadic_exact_endpoints`, the sequence x(r + 1) takes the value true at index 0. Because i - (r + 1) = 0 by `Nat.sub_self` and r + 1 ≤ i holds reflexively by `le_rfl`, this element i belongs to A(r), so the union A(r) ∪ B(r) is nonempty.
uses
cycle_power_dyadic_exact_endpoints,mem_univ,le_rfl,Nat.sub_self· intro r have hrg : r.val+1 < g := by have := r.isLt; omega let i : Fin g := ⟨r.val+1, hrg⟩ have hend := (cycle_power_dyadic_exact_endpoints m hm x hexact ((r.val+1 : ℕ) : ℤ)).1 refine ⟨i, mem_union.mpr (Or.inl ?_)⟩ apply mem_filter.mpr refine ⟨mem_univ _, le_rfl, ?_⟩ simpa only [i, Nat.sub_self] using hend
Every pair i < j in Fin g is covered by some root r: i ∈ B(r) and j ∈ A(r).
This is immediate from the lemma `cycle_power_gap_ordinary_side_cover`, which transfers the ordinary coverage assumption `hcover` on the full cylinder of size 2ᵐ to the compressed gap of length g ≤ 2ᵐ.
uses
cycle_power_gap_ordinary_side_cover· exact cycle_power_gap_ordinary_side_cover (2^m) g hg x hcoverFor every root r, the tree cardinality identity holds: |A(r)| + |B(r)| = 1 + ∑_{j < m} |E_j(r)|.
This tree-like Euler characteristic relation follows directly from `cycle_power_dyadic_gap_side_tree`, which uses the tightness assumption `htight`, the exactness condition `hexact`, and the fact that rows 0 and g are identically true (`hfull₀` and `hfullg`).
uses
cycle_power_dyadic_gap_side_tree· exact cycle_power_dyadic_gap_side_tree m hm x htight hexact g hg hfull₀ hfullgFor each scale j < m and each pair k + 2ʲ = i in Fin g, there is a unique root r covering it with i ∈ A(r) and k ∈ B(r).
Since j < m, we have 2ʲ ≤ 2ᵐ by `Nat.pow_le_pow_right` and `Nat.le_of_lt`. The result then follows from `cycle_power_gap_exact_side_owner`, using the exactness hypothesis `hexact` at scale j.
uses
cycle_power_gap_exact_side_owner,Nat.pow_le_pow_right,Nat.le_of_lt· intro j hj exact cycle_power_gap_exact_side_owner (2^m) (2^j) g (Nat.pow_le_pow_right (by decide) (Nat.le_of_lt hj)) hg x (hexact j hj)
ordered_biclique_dyadic_tree_intervals- If a family of pairs of subsets (A(r), B(r)) on {0, …, g - 1} satisfies strict separation (r < i for i ∈ A(r) and i ≤ r for i ∈ B(r)), has nonempty unions, covers all pairs i < j, satisfies the dyadic tree cardinality formula, and uniquely covers dyadic pairs of length 2ʲ for j < m, then every A(r) and B(r) is an interval (convex).
cycle_power_dyadic_exact_endpoints- In an exact dyadic model of dimension m ≥ 1, both endpoints 0 and 2ᵐ - 1 evaluate to true on every fiber.
mem_univ- Every element of a finite type belongs to the universal finset.
le_rfl- The preorder relation ≤ is reflexive (a ≤ a).
Nat.sub_self- Subtracting any natural number from itself yields 0.
cycle_power_gap_ordinary_side_cover- In a model with ordinary coverage up to diameter D, every pair i < j < g is covered by the gap sides at some root r.
cycle_power_dyadic_gap_side_tree- In a tight, exact dyadic model with full boundary rows at 0 and g, the compressed gap sides satisfy the dyadic tree cardinality formula.
cycle_power_gap_exact_side_owner- If an exactness condition at distance R holds, then every pair (k, i) with k + R = i is covered by the gap sides at a unique root r.
Nat.pow_le_pow_right- For any base n > 0, exponentiation nⁱ is monotone in the exponent i.
Nat.le_of_lt- A strict inequality between natural numbers implies a weak inequality.
- In Lean, roots in the gap are indexed by r : Fin (g - 1), corresponding to the integer coordinate r + 1 ∈ {1, …, g - 1}.
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_full_gap_sides_convex (m : ℕ) (hm : 1 ≤ m) (x : ℤ → ℕ → Bool) (htight : ∀ p : ℤ, cycle_power_dyadic_class_weight m (x p) = (range (2^m)).sum (fun i => (x p i).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) (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^m → ∀ v : ℤ, ∃ a : ℕ, a < 2^m-d ∧ x (v-(a : ℤ)) a = true ∧ x (v-(a : ℤ)) (a+d) = true) (g : ℕ) (hlo : 2^(m-1) ≤ g) (hg : g ≤ 2^m) (hfull₀ : ∀ i < 2^m, x 0 i = true) (hfullg : ∀ i < 2^m, x (g : ℤ) i = true) : let A : Fin (g-1) → Finset (Fin g) := fun r => cycle_power_gap_left_side g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) let B : Fin (g-1) → Finset (Fin g) := fun r => cycle_power_gap_right_side (2^m) g (r.val+1) (x ((r.val+1 : ℕ) : ℤ)) (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ A r → k ∈ A r → j ∈ A r) ∧ (∀ r (i j k : Fin g), i ≤ j → j ≤ k → i ∈ B r → k ∈ B r → j ∈ B r) := by classical dsimp only apply ordered_biclique_dyadic_tree_intervals g m hm hlo · intro r i hi have := (mem_filter.mp hi).2.1 omega · intro r i hi have := (mem_filter.mp hi).2.1 omega · intro r have hrg : r.val+1 < g := by have := r.isLt; omega let i : Fin g := ⟨r.val+1, hrg⟩ have hend := (cycle_power_dyadic_exact_endpoints m hm x hexact ((r.val+1 : ℕ) : ℤ)).1 refine ⟨i, mem_union.mpr (Or.inl ?_)⟩ apply mem_filter.mpr refine ⟨mem_univ _, le_rfl, ?_⟩ simpa only [i, Nat.sub_self] using hend · exact cycle_power_gap_ordinary_side_cover (2^m) g hg x hcover · exact cycle_power_dyadic_gap_side_tree m hm x htight hexact g hg hfull₀ hfullg · intro j hj exact cycle_power_gap_exact_side_owner (2^m) (2^j) g (Nat.pow_le_pow_right (by decide) (Nat.le_of_lt hj)) hg x (hexact j hj)