AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_full_gap_sides_convex

theoremverified

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
Used by 1

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.

  1. 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.

    lines 22–24

    uses ordered_biclique_dyadic_tree_intervals

      classical
      dsimp only
      apply ordered_biclique_dyadic_tree_intervals g m hm hlo
  2. 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.

    lines 25–27

      · intro r i hi
        have := (mem_filter.mp hi).2.1
        omega
  3. 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.

    lines 28–30

      · intro r i hi
        have := (mem_filter.mp hi).2.1
        omega
  4. 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.

    lines 31–39

    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
  5. 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ᵐ.

    line 40

    uses cycle_power_gap_ordinary_side_cover

      · exact cycle_power_gap_ordinary_side_cover (2^m) g hg x hcover
  6. For 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`).

    line 41

    uses cycle_power_dyadic_gap_side_tree

      · exact cycle_power_dyadic_gap_side_tree m hm x htight hexact g hg hfull₀ hfullg
  7. For 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.

    lines 42–44

    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.

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 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)
See it in the graphDiscuss this resultChallenge it