AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_outer_pair_reverse

theoremverified

For exponent m at least three, consider a Boolean integer-indexed dyadic class model with exact dyadic ownership at every rank, coverage of every ordinary distance below 2^m, equal boundary bits at offsets 1 and 2^m-2, and only endpoints selected in every class whose bit 1 is false. If a class selects offsets 1 and 2, it also selects offset 3.

Statement

theorem cycle_power_dyadic_outer_pair_reverse (m : ℕ) (hm : 3 ≤ m) (x : ℤ → ℕ → Bool)
    (hexact : ∀ j < m, ∀ v : ℤ, (Finset.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)
    (h1 : ∀ p : ℤ, x p 1 = x p (2^m-2))
    (hend : ∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^m-1 → x p j = false) :
    ∀ p : ℤ, x p 1 = true → x p 2 = true → x p 3 = true
Source
Conditional outer pairing step for research thread RT-1 and OP-205, arXiv:2610.15635.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The proof proceeds by contradiction. Assuming x(p, 1) = true and x(p, 2) = true but x(p, 3) = false, boundary bit alternation forces bit 1 to be false in classes p - 1, p + 1, and p + 3, so all interior bits in these classes must be false. Uniqueness of the rank-2 dyadic owning shift further establishes that offset 2^m - 4 in class p + 2 must be false. Finally, covering distance 2^m - 5 at vertex p + 3 requires an owning shift a < 5, but every choice a ∈ {0, 1, 2, 3, 4} contradicts one of these established bit values.

  1. 8 ≤ 2^m

    Since m ≥ 3, the bound 8 = 2^3 ≤ 2^m follows by monotonicity of powers of 2 (Nat.pow_le_pow_right).

    lines 10–12

    uses Nat.pow_le_pow_right

      have hD : 8 ≤ 2^m := by
        calc 8 = 2^3 := by norm_num
          _ ≤ 2^m := Nat.pow_le_pow_right (by norm_num) hm
  2. Boundary endpoints are selected everywhere, bit 1 alternates between adjacent classes, and dyadic ownership holds at rank 2 (range 4).

    By cycle_power_dyadic_exact_endpoints, every class selects offsets 0 and 2^m - 1. By cycle_power_dyadic_boundary_pairing_alternates, bit 1 alternates across consecutive classes (x(p+1, 1) = ¬x(p, 1)). Specializing the exact dyadic ownership hypothesis hexact to rank j = 2 shows that for any vertex v, exactly one shift a < 4 satisfies x(v-a, a) = true and x(v-a, a + 2^m - 4) = true.

    lines 13–17

    uses cycle_power_dyadic_exact_endpoints, cycle_power_dyadic_boundary_pairing_alternates

      have ends := cycle_power_dyadic_exact_endpoints m (by omega) x hexact
      have alt := cycle_power_dyadic_boundary_pairing_alternates m (by omega) x hexact h1
      have ex4 : ∀ v : ℤ, (Finset.range 4).sum (fun a =>
          (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-4)).toNat) = 1 := by
        simpa using hexact 2 (by omega)
  3. Assume for contradiction that x(p, 3) = false for a class p where x(p, 1) = true and x(p, 2) = true.

    We fix a class p satisfying x(p, 1) = true and x(p, 2) = true, and assume the negation of x(p, 3) = true. Using Bool.eq_false_of_not_eq_true, this means x(p, 3) = false.

    lines 18–20

    uses Bool.eq_false_of_not_eq_true

      intro p hbit h2
      by_contra h3'
      have h3 : x p 3 = false := Bool.eq_false_of_not_eq_true h3'
  4. Bit 1 is false in classes p - 1, p + 1, and p + 3, and true in class p + 2.

    Since x(p, 1) = true, the alternation property x(k+1, 1) = ¬x(k, 1) forces x(p+1, 1) = false, then x(p+2, 1) = true, and then x(p+3, 1) = false. Stepping backward from p, x(p, 1) = ¬x(p-1, 1) likewise forces x(p-1, 1) = false.

    lines 21–33

      have hp1 : x (p+1) 1 = false := by rw [alt p, hbit]; rfl
      have hp2 : x (p+2) 1 = true := by
        have h := alt (p+1)
        rw [show p+1+1 = p+2 by ring, hp1] at h
        exact h
      have hp3 : x (p+3) 1 = false := by
        have h := alt (p+2)
        rw [show p+2+1 = p+3 by ring, hp2] at h
        exact h
      have hm1 : x (p-1) 1 = false := by
        have h := alt (p-1)
        rw [show p-1+1 = p by ring, hbit] at h
        cases hb : x (p-1) 1 <;> simp [hb] at h ⊢
  5. x(p+2, 2^m - 4) = false.

    Suppose for contradiction that x(p+2, 2^m - 4) = true (via Bool.eq_true_of_not_eq_false). Then at vertex v = p + 2, the rank-2 dyadic ownership condition (with R = 4 and distance 2^m - 4) is satisfied by shift a = 0 (using the endpoint offset 0 and x(p+2, 2^m - 4)) and by shift a = 2 (since x(p, 2) = true and x(p, 2^m - 2) = x(p, 1) = true). Uniqueness of the owning shift (cycle_power_exact_pair_unique) implies 0 = 2, a contradiction.

    lines 34–41

    uses Bool.eq_true_of_not_eq_false, cycle_power_exact_pair_unique

      have hp2high : x (p+2) (2^m-4) = false := by
        by_contra hn
        have hx : x (p+2) (2^m-4) = true := Bool.eq_true_of_not_eq_false hn
        have eq := cycle_power_exact_pair_unique (2^m) 4 x ex4 (p+2) 0 2 (by omega) (by omega)
          (by simpa using (ends (p+2)).1) (by simpa using hx)
          (by simpa using h2)
          (by simpa [show 2 + 2^m - 4 = 2^m - 2 by omega, ← h1 p] using hbit)
        omega
  6. Coverage of distance d = 2^m - 5 at vertex p + 3 yields an owning offset a < 5.

    Since 2^m ≥ 8, the distance d = 2^m - 5 satisfies 1 ≤ d < 2^m. Applying the coverage hypothesis hcover at vertex v = p + 3 gives an offset a < 2^m - d = 5 such that both x(p+3-a, a) and x(p+3-a, a + 2^m - 5) are true.

    lines 42–43

      obtain ⟨a, ha, ha1, ha2⟩ := hcover (2^m-5) (by omega) (by omega) (p+3)
      have ha' : a < 5 := by omega
  7. Every case for a ∈ {0, 1, 2, 3, 4} yields a contradiction.

    We test each of the five possible values for a: • If a = 0, then x(p+3, 2^m - 5) = true. But bit 1 is false at class p + 3, so hend implies all interior bits of that class are false, a contradiction. • If a = 1, then x(p+2, 2^m - 4) = true, contradicting the earlier result that this bit is false. • If a = 2, then x(p+1, 2) = true. But bit 1 is false at class p + 1, so by hend interior bit 2 must be false, a contradiction. • If a = 3, then x(p, 3) = true, directly contradicting the assumption x(p, 3) = false. • If a = 4, then x(p-1, 4) = true. But bit 1 is false at class p - 1, so by hend interior bit 4 must be false, a contradiction. Because all five cases fail, we conclude x(p, 3) = true.

    lines 44–58

      interval_cases a
      · have hh : x (p+3) (2^m-5) = true := by simpa using ha2
        have hh' := hend (p+3) hp3 (2^m-5) (by omega) (by omega)
        rw [hh'] at hh; contradiction
      · have hh : x (p+2) (2^m-4) = true := by
          simpa [show p+3-1 = p+2 by ring, show 1 + (2^m-5) = 2^m-4 by omega] using ha2
        rw [hp2high] at hh; contradiction
      · have hh : x (p+1) 2 = true := by simpa [show p+3-2 = p+1 by ring] using ha1
        have hh' := hend (p+1) hp1 2 (by omega) (by omega)
        rw [hh'] at hh; contradiction
      · have hh : x p 3 = true := by simpa using ha1
        rw [h3] at hh; contradiction
      · have hh : x (p-1) 4 = true := by simpa [show p+3-4 = p-1 by ring] using ha1
        have hh' := hend (p-1) hm1 4 (by omega) (by omega)
        rw [hh'] at hh; contradiction
Nat.pow_le_pow_right
If n > 0 and i ≤ j, then n^i ≤ n^j.
cycle_power_dyadic_exact_endpoints
In an exact dyadic ownership model with rank bound m ≥ 1, both boundary endpoints (offsets 0 and 2^m - 1) are selected in every class.
cycle_power_dyadic_boundary_pairing_alternates
In an exact dyadic ownership model with m ≥ 2 and equal boundary bits at offsets 1 and 2^m - 2, bit 1 strictly alternates between adjacent classes: x(p+1, 1) = ¬x(p, 1).
Bool.eq_false_of_not_eq_true
If a Boolean value is not equal to true, it equals false.
Bool.eq_true_of_not_eq_false
If a Boolean value is not equal to false, it equals true.
cycle_power_exact_pair_unique
In a model where exactly one shift in [0, R) owns a pair at distance D - R at vertex v, any two such owning shifts must be identical.

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

theorem cycle_power_dyadic_outer_pair_reverse (m : ℕ) (hm : 3 ≤ m) (x : ℤ → ℕ → Bool)    (hexact : ∀ j < m, ∀ v : ℤ, (Finset.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)    (h1 : ∀ p : ℤ, x p 1 = x p (2^m-2))    (hend : ∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^m-1 → x p j = false) :    ∀ p : ℤ, x p 1 = true → x p 2 = true → x p 3 = true := by  have hD : 8 ≤ 2^m := by    calc 8 = 2^3 := by norm_num      _ ≤ 2^m := Nat.pow_le_pow_right (by norm_num) hm  have ends := cycle_power_dyadic_exact_endpoints m (by omega) x hexact  have alt := cycle_power_dyadic_boundary_pairing_alternates m (by omega) x hexact h1  have ex4 : ∀ v : ℤ, (Finset.range 4).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-4)).toNat) = 1 := by    simpa using hexact 2 (by omega)  intro p hbit h2  by_contra h3'  have h3 : x p 3 = false := Bool.eq_false_of_not_eq_true h3'  have hp1 : x (p+1) 1 = false := by rw [alt p, hbit]; rfl  have hp2 : x (p+2) 1 = true := by    have h := alt (p+1)    rw [show p+1+1 = p+2 by ring, hp1] at h    exact h  have hp3 : x (p+3) 1 = false := by    have h := alt (p+2)    rw [show p+2+1 = p+3 by ring, hp2] at h    exact h  have hm1 : x (p-1) 1 = false := by    have h := alt (p-1)    rw [show p-1+1 = p by ring, hbit] at h    cases hb : x (p-1) 1 <;> simp [hb] at h ⊢  have hp2high : x (p+2) (2^m-4) = false := by    by_contra hn    have hx : x (p+2) (2^m-4) = true := Bool.eq_true_of_not_eq_false hn    have eq := cycle_power_exact_pair_unique (2^m) 4 x ex4 (p+2) 0 2 (by omega) (by omega)      (by simpa using (ends (p+2)).1) (by simpa using hx)      (by simpa using h2)      (by simpa [show 2 + 2^m - 4 = 2^m - 2 by omega, ← h1 p] using hbit)    omega  obtain ⟨a, ha, ha1, ha2⟩ := hcover (2^m-5) (by omega) (by omega) (p+3)  have ha' : a < 5 := by omega  interval_cases a  · have hh : x (p+3) (2^m-5) = true := by simpa using ha2    have hh' := hend (p+3) hp3 (2^m-5) (by omega) (by omega)    rw [hh'] at hh; contradiction  · have hh : x (p+2) (2^m-4) = true := by      simpa [show p+3-1 = p+2 by ring, show 1 + (2^m-5) = 2^m-4 by omega] using ha2    rw [hp2high] at hh; contradiction  · have hh : x (p+1) 2 = true := by simpa [show p+3-2 = p+1 by ring] using ha1    have hh' := hend (p+1) hp1 2 (by omega) (by omega)    rw [hh'] at hh; contradiction  · have hh : x p 3 = true := by simpa using ha1    rw [h3] at hh; contradiction  · have hh : x (p-1) 4 = true := by simpa [show p+3-4 = p-1 by ring] using ha1    have hh' := hend (p-1) hm1 4 (by omega) (by omega)    rw [hh'] at hh; contradiction
See it in the graphDiscuss this resultChallenge it