AFTD Auto-Formalizing Theoretical Domains

cycle_power_exact_rank_boundary_successor

theoremverified

For an exact dyadic-rank matching with both parent implications, if a root selects the last lower offset2q-1 and the edge one unit longer than that rank is covered, its owner has offset a<q and root at least p+q. Unless a=q-1, it also owns the next exact-rank edge. This is uniform in the radius and rank, with no count or periodicity assumption.

Statement

theorem cycle_power_exact_rank_boundary_successor
    (D q : ℕ) (hq : 0 < q) (hD : 2*q < D)
    (x : ℤ → ℕ → Bool)
    (hparent : ∀ r a, a < 2*q →
      (a < q → x r (a+D-2*q) = true → x r a = true) ∧
      (q ≤ a → x r a = true → x r (a+D-2*q) = true))
    (hexact : ∀ v : ℤ, (Finset.range (2*q)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-2*q)).toNat) = 1)
    (p : ℤ) (hboundary : x p (2*q-1) = true)
    (hcover : ∃ a : ℕ, a < 2*q-1 ∧
      x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) a = true ∧
      x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) (a+(D-2*q+1)) = true) :
    ∃ a : ℕ, a < q ∧
      p+(q : ℤ) ≤ p+((2*q-1 : ℕ) : ℤ)-(a : ℤ) ∧
      x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) a = true ∧
      x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) (a+(D-2*q+1)) = true ∧
      (a+1 < q → x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) (a+1) = true ∧
        x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) (a+1+D-2*q) = true)
Source
Uniform structural route for OP-205 / RT-1, following arXiv:2610.15635. These are helper reductions, not a proof of the open covering value and not a research advance. The upper-vertical core remains an explicit unproved hypothesis.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The proof unpacks the covering offset a < 2q - 1 at vertex v = p + (2q - 1) and shows a < q by contradiction: if a ≥ q, the parent condition would make offset a an exact-rank matching pair at v, clashing with the boundary matching pair at offset 2q - 1 by uniqueness (cycle_power_exact_pair_unique). Because a < q, the root r = p + (2q - 1) - a is at least p + q. Finally, observing that the covering edge index a + (D - 2q + 1) equals (a + 1) + D - 2q allows the downward parent implication to supply the matching lower edge at offset a + 1 whenever a + 1 < q.

  1. We unpack the covering offset a < 2q - 1 for vertex v = p + (2q - 1) and establish that root p also has the upper boundary edge 2q - 1 + D - 2q.

    From the covering hypothesis (hcover), we obtain an offset a < 2q - 1 such that the root r = p + (2q - 1) - a has both the lower edge at offset a (hlo) and the edge at offset a + (D - 2q + 1) (hhi). For the boundary offset 2q - 1 at root p, since q ≤ 2q - 1 < 2q (using q > 0), the second parent implication (hparent) guarantees that the active boundary edge x p (2q - 1) = true implies the active upper edge x p (2q - 1 + D - 2q) = true (hlast).

    lines 22–24

      obtain ⟨a,ha,hlo,hhi⟩ := hcover
      have hb : 2*q-1 < 2*q := by omega
      have hlast := (hparent p (2*q-1) hb).2 (by omega) hboundary
  2. a < q

    Suppose, for contradiction, that a ≥ q. Since a < 2q - 1 < 2q, the parent implication applies to root r = p + (2q - 1) - a at offset a, ensuring that the upper edge x r (a + D - 2q) = true is also active (hap). But then both offset a (from root r) and offset 2q - 1 (from root p, since v - (2q - 1) = p) form exact-rank matching pairs covering the same vertex v = p + (2q - 1). By uniqueness of exact matching pairs at v (cycle_power_exact_pair_unique), this forces a = 2q - 1, contradicting a < 2q - 1. Thus a < q.

    lines 25–31

    uses cycle_power_exact_pair_unique

      have haq : a < q := by
        by_contra hn
        have hap := (hparent (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) a (by omega)).2 (by omega) hlo
        have hu := cycle_power_exact_pair_unique D (2*q) x hexact
          (p+((2*q-1 : ℕ) : ℤ)) a (2*q-1) (by omega) hb
          hlo hap (by simpa using hboundary) (by simpa using hlast)
        omega
  3. Offset a satisfies the existential conditions, reducing the goal to showing the successor edge when a + 1 < q.

    We supply a as the witness. We have shown a < q, and since a ≤ q - 1, linear integer arithmetic gives p + q ≤ p + (2q - 1) - a. The edges x r a = true and x r (a + (D - 2q + 1)) = true are provided directly by hlo and hhi. It remains only to verify the conditional successor property.

    line 32

      refine ⟨a,haq,by omega,hlo,hhi,?_⟩
  4. If a + 1 < q, root r also owns both exact-rank edges at offset a + 1: x r (a + 1) = true and x r (a + 1 + D - 2q) = true.

    Assume a + 1 < q. The offset index a + (D - 2q + 1) is algebraically identical to a + 1 + D - 2q, so hypothesis hhi immediately shows x r (a + 1 + D - 2q) = true (hhi'). Since a + 1 < q < 2q, the downward parent implication applies to offset a + 1, showing that the long edge hhi' implies the short edge x r (a + 1) = true.

    lines 33–36

      intro hn
      have hhi' : x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) (a+1+D-2*q) = true := by
        convert hhi using 1 <;> congr 1 <;> omega
      exact ⟨(hparent _ (a+1) (by omega)).1 hn hhi',hhi'⟩
cycle_power_exact_pair_unique
In an exact matching where every vertex sum over offsets up to R is 1, if two offsets a, b < R both satisfy the matching pair conditions for the same vertex v, then a = b.

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

set_option maxHeartbeats 2000000set_option maxRecDepth 10000theorem cycle_power_exact_rank_boundary_successor    (D q : ℕ) (hq : 0 < q) (hD : 2*q < D)    (x : ℤ → ℕ → Bool)    (hparent : ∀ r a, a < 2*q →      (a < q → x r (a+D-2*q) = true → x r a = true) ∧      (q ≤ a → x r a = true → x r (a+D-2*q) = true))    (hexact : ∀ v : ℤ, (Finset.range (2*q)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+D-2*q)).toNat) = 1)    (p : ℤ) (hboundary : x p (2*q-1) = true)    (hcover : ∃ a : ℕ, a < 2*q-1 ∧      x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) a = true ∧      x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) (a+(D-2*q+1)) = true) :    ∃ a : ℕ, a < q ∧      p+(q : ℤ) ≤ p+((2*q-1 : ℕ) : ℤ)-(a : ℤ) ∧      x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) a = true ∧      x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) (a+(D-2*q+1)) = true ∧      (a+1 < q → x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) (a+1) = true ∧        x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) (a+1+D-2*q) = true) := by  obtain ⟨a,ha,hlo,hhi⟩ := hcover  have hb : 2*q-1 < 2*q := by omega  have hlast := (hparent p (2*q-1) hb).2 (by omega) hboundary  have haq : a < q := by    by_contra hn    have hap := (hparent (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) a (by omega)).2 (by omega) hlo    have hu := cycle_power_exact_pair_unique D (2*q) x hexact      (p+((2*q-1 : ℕ) : ℤ)) a (2*q-1) (by omega) hb      hlo hap (by simpa using hboundary) (by simpa using hlast)    omega  refine ⟨a,haq,by omega,hlo,hhi,?_⟩  intro hn  have hhi' : x (p+((2*q-1 : ℕ) : ℤ)-(a : ℤ)) (a+1+D-2*q) = true := by    convert hhi using 1 <;> congr 1 <;> omega  exact ⟨(hparent _ (a+1) (by omega)).1 hn hhi',hhi'⟩
See it in the graphDiscuss this resultChallenge it