AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_half_monotone_of_full_class_cover

theoremverified

A tight exact full ordinary-cover dyadic integer model with a full class covering every vertex is monotone toward the endpoints separately on its two halves.

Statement

theorem cycle_power_dyadic_half_monotone_of_full_class_cover
    (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)
    (hfullcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^m ∧ ∀ i < 2^m, x (v-(a : ℤ)) i = true) :
    ∀ p : ℤ,
      (∀ a b : ℕ, a ≤ b → b < 2^(m-1) → x p b = true → x p a = true) ∧
      (∀ a b : ℕ, 2^(m-1) ≤ a → a ≤ b → b < 2^m → x p a = true → x p b = true)
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 10
Used by 1

The proof, explained

The theorem is proved by strong induction on m ≥ 1. The base case m = 1 holds immediately because each half of the domain consists of a single point, making monotonicity trivial. For m = k + 2 ≥ 2, a structural 'no-island' property guarantees that any true value in the middle range $[2^k, 3 \cdot 2^k)$ forces the pruned configuration of order k + 1 (which removes that middle range) to be identically true everywhere. This pruned model inherits tightness, exactness, covering, and full-class covering, allowing the induction hypothesis to establish that it is half-monotone. Finally, this pruned half-monotonicity is lifted back to deduce half-monotonicity for the original model of order k + 2.

  1. The proof proceeds by strong induction on m, separating the base case m < 2 from the inductive step m ≥ 2.

    We apply strong induction on m, generalizing over the configuration x. A case distinction on 2 ≤ m isolates the base case m < 2 (which means m = 1 given 1 ≤ m), which is swapped to be treated first.

    lines 17–20

    uses Nat.strong_induction_on

      induction m using Nat.strong_induction_on generalizing x with
      | h m ih =>
        by_cases hm₂ : 2 ≤ m
        swap
  2. The configuration x is half-monotone when m = 1.

    When m = 1, the lower half $[0, 2^{m-1}) = [0, 1)$ contains only 0, so a ≤ b < 1 forces a = b = 0. Similarly, the upper half $[2^{m-1}, 2^m) = [1, 2)$ contains only 1, so 1 ≤ a ≤ b < 2 forces a = b = 1. In both cases a = b, so the monotonicity implications x(p, b) = true → x(p, a) = true and x(p, a) = true → x(p, b) = true are trivial equalities.

    lines 21–30

        · have he : m = 1 := by omega
          subst m
          intro p
          constructor
          · intro a b hab hb hx
            have heq : a = b := by norm_num at hb; omega
            simpa only [heq] using hx
          · intro a b ha hab hb hx
            have heq : a = b := by norm_num at ha hb; omega
            simpa only [heq] using hx
  3. Writing m = k + 2, the configuration x satisfies the no-island property.

    For m ≥ 2, we set k = m - 2 so that m = k + 2. Lemma cycle_power_dyadic_class_no_island_of_full_class_cover shows that the hypotheses of tightness, exactness, covering, and full-class covering ensure no slice has an isolated island: whenever a < b < c < 2^(k+2), if x(p, a) = false and x(p, b) = true, then x(p, c) must be true.

    lines 31–33

    uses cycle_power_dyadic_class_no_island_of_full_class_cover

        obtain ⟨k, rfl⟩ : ∃ k, m = k+2 := ⟨m-2, by omega⟩
        have hshape := cycle_power_dyadic_class_no_island_of_full_class_cover (k+2)
          (by omega) x htight hexact hcover hfullcover
  4. If any middle index a ∈ [2^k, 3 · 2^k) is true in slice p, then the pruned lift of x(p) is identically true everywhere on $[0, 2^{k+1})$.

    By lemma cycle_power_dyadic_no_island_middle_imp_full_prune, the combination of tightness and the no-island property implies that any true value in the middle half $[2^k, 3 \cdot 2^k)$ forces the pruned lift of the slice to evaluate to true at every index i < 2^(k+1).

    lines 34–38

    uses cycle_power_dyadic_no_island_middle_imp_full_prune

        have hmid : ∀ (p : ℤ) (a : ℕ), 2^k ≤ a → a < 3*2^k → x p a = true →
            ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true := by
          intro p a ha hb hx
          exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p) (htight p)
            (hshape p) a ha hb hx
  5. The pruned model y(p) = lift_k(x(p)) satisfies tightness, exactness, covering, and full-class covering at order k + 1.

    We define y(p) to be the pruned configuration cycle_power_dyadic_b_lift k (x(p)). Tightness transfers to order k+1 via cycle_power_dyadic_tight_class_prune, exactness transfers via cycle_power_dyadic_prune_exact, and ordinary covering transfers via cycle_power_dyadic_prune_cover. Full-class covering at order k+1 follows from cycle_power_dyadic_prune_full_class_cover_of_middle_fullness, which uses the middle-fullness property hmid together with the half-cover property derived from exactness by cycle_power_dyadic_exact_half_cover.

    lines 39–44

    uses cycle_power_dyadic_tight_class_prune, cycle_power_dyadic_prune_exact, cycle_power_dyadic_prune_cover, cycle_power_dyadic_prune_full_class_cover_of_middle_fullness, cycle_power_dyadic_exact_half_cover

        let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (x p)
        have hyt := fun p => cycle_power_dyadic_tight_class_prune k (x p) (htight p)
        have hye := cycle_power_dyadic_prune_exact k x hexact
        have hyc := cycle_power_dyadic_prune_cover k x htight hcover
        have hyf := cycle_power_dyadic_prune_full_class_cover_of_middle_fullness k x hmid
          (cycle_power_dyadic_exact_half_cover k x hexact)
  6. The pruned model y is half-monotone on each slice.

    Because k + 1 < k + 2 = m and 1 ≤ k + 1, we invoke the strong induction hypothesis ih on k + 1 and the pruned configuration y with its verified model properties. Simplifying the index (k + 1) - 1 to k with Nat.add_sub_cancel gives the half-monotonicity of the pruned model on both halves $[0, 2^k)$ and $[2^k, 2^{k+1})$.

    lines 45–51

    uses Nat.add_sub_cancel

        have hprev := ih (k+1) (by omega) (by omega) y hyt hye hyc hyf
        have hprev' : ∀ p : ℤ,
            (∀ a b : ℕ, a ≤ b → b < 2^k → cycle_power_dyadic_b_lift k (x p) b = true →
              cycle_power_dyadic_b_lift k (x p) a = true) ∧
            (∀ a b : ℕ, 2^k ≤ a → a ≤ b → b < 2^(k+1) →
              cycle_power_dyadic_b_lift k (x p) a = true → cycle_power_dyadic_b_lift k (x p) b = true) := by
          simpa only [y, Nat.add_sub_cancel] using hprev
  7. The original model x is half-monotone on each slice, completing the induction.

    Lemma cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono transfers half-monotonicity from the pruned model of order k + 1 back to the original model x of order k + 2, using middle-fullness, tightness, exactness, and ordinary covering. Simplifying (k + 2) - 1 to k + 1 closes the goal.

    lines 52–53

    uses cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono

        simpa only [show k+2-1=k+1 by omega] using
          cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono k x htight hexact hmid hcover hprev'
Nat.strong_induction_on
The strong induction principle on ℕ: to prove a property holds for all n, it suffices to show it holds for n assuming it holds for all m < n.
cycle_power_dyadic_class_no_island_of_full_class_cover
In a tight, exact, covered dyadic model with a full-class cover, each slice has no 'islands': any true value occurring after a false value cannot be followed by a false value later in the range.
cycle_power_dyadic_no_island_middle_imp_full_prune
For a tight configuration of order k+2 satisfying the no-island property, having any true value in the middle range $[2^k, 3 \cdot 2^k)$ implies its pruned lift is identically true on all indices below $2^{k+1}$.
cycle_power_dyadic_tight_class_prune
Pruning a tight configuration of order k+2 yields a tight configuration of order k+1.
cycle_power_dyadic_prune_exact
The pruned model of an exact dyadic model of order k+2 is exact at order k+1.
cycle_power_dyadic_prune_cover
The pruned model of a tight and ordinary-covered dyadic model of order k+2 satisfies the ordinary covering condition at order k+1.
cycle_power_dyadic_exact_half_cover
In an exact dyadic model of order k+2, every vertex has a shift a < 2^(k+1) where both a and a + 2^(k+1) are true.
cycle_power_dyadic_prune_full_class_cover_of_middle_fullness
If middle-truth forces the pruned configuration to be everywhere true and every vertex has a half-distance pair of true values, then the pruned model has a full class covering every vertex.
Nat.add_sub_cancel
For any natural numbers n and m, (n + m) - m = n.
cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono
If a tight, exact, covered dyadic model of order k+2 satisfies middle-fullness and its pruned model of order k+1 is half-monotone, then the original model is half-monotone at order k+2.

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_half_monotone_of_full_class_cover    (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)    (hfullcover : ∀ v : ℤ, ∃ a : ℕ, a < 2^m ∧ ∀ i < 2^m, x (v-(a : ℤ)) i = true) :    ∀ p : ℤ,      (∀ a b : ℕ, a ≤ b → b < 2^(m-1) → x p b = true → x p a = true) ∧      (∀ a b : ℕ, 2^(m-1) ≤ a → a ≤ b → b < 2^m → x p a = true → x p b = true) := by  induction m using Nat.strong_induction_on generalizing x with  | h m ih =>    by_cases hm₂ : 2 ≤ m    swap    · have he : m = 1 := by omega      subst m      intro p      constructor      · intro a b hab hb hx        have heq : a = b := by norm_num at hb; omega        simpa only [heq] using hx      · intro a b ha hab hb hx        have heq : a = b := by norm_num at ha hb; omega        simpa only [heq] using hx    obtain ⟨k, rfl⟩ : ∃ k, m = k+2 := ⟨m-2, by omega⟩    have hshape := cycle_power_dyadic_class_no_island_of_full_class_cover (k+2)      (by omega) x htight hexact hcover hfullcover    have hmid : ∀ (p : ℤ) (a : ℕ), 2^k ≤ a → a < 3*2^k → x p a = true →        ∀ i < 2^(k+1), cycle_power_dyadic_b_lift k (x p) i = true := by      intro p a ha hb hx      exact cycle_power_dyadic_no_island_middle_imp_full_prune k (x p) (htight p)        (hshape p) a ha hb hx    let y : ℤ → ℕ → Bool := fun p => cycle_power_dyadic_b_lift k (x p)    have hyt := fun p => cycle_power_dyadic_tight_class_prune k (x p) (htight p)    have hye := cycle_power_dyadic_prune_exact k x hexact    have hyc := cycle_power_dyadic_prune_cover k x htight hcover    have hyf := cycle_power_dyadic_prune_full_class_cover_of_middle_fullness k x hmid      (cycle_power_dyadic_exact_half_cover k x hexact)    have hprev := ih (k+1) (by omega) (by omega) y hyt hye hyc hyf    have hprev' : ∀ p : ℤ,        (∀ a b : ℕ, a ≤ b → b < 2^k → cycle_power_dyadic_b_lift k (x p) b = true →          cycle_power_dyadic_b_lift k (x p) a = true) ∧        (∀ a b : ℕ, 2^k ≤ a → a ≤ b → b < 2^(k+1) →          cycle_power_dyadic_b_lift k (x p) a = true → cycle_power_dyadic_b_lift k (x p) b = true) := by      simpa only [y, Nat.add_sub_cancel] using hprev    simpa only [show k+2-1=k+1 by omega] using      cycle_power_dyadic_half_monotone_of_middle_full_and_pruned_mono k x htight hexact hmid hcover hprev'
See it in the graphDiscuss this resultChallenge it