cycle_power_dyadic_outer_pair_reverse
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
- 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…
- cycle_power_exact_pair_uniqueAn exact Boolean long-edge count of one gives a unique owning rooted class.
- cycle_power_dyadic_boundary_pairing_alternatesIn an exact dyadic Boolean class model with exponent at least two, equality of the two boundary bits in every class forces the first inner…
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.
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).
uses
Nat.pow_le_pow_righthave hD : 8 ≤ 2^m := by calc 8 = 2^3 := by norm_num _ ≤ 2^m := Nat.pow_le_pow_right (by norm_num) hm
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.
uses
cycle_power_dyadic_exact_endpoints,cycle_power_dyadic_boundary_pairing_alternateshave 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)
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.
uses
Bool.eq_false_of_not_eq_trueintro p hbit h2 by_contra h3' have h3 : x p 3 = false := Bool.eq_false_of_not_eq_true h3'
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.
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 ⊢
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.
uses
Bool.eq_true_of_not_eq_false,cycle_power_exact_pair_uniquehave 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
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.
obtain ⟨a, ha, ha1, ha2⟩ := hcover (2^m-5) (by omega) (by omega) (p+3) have ha' : a < 5 := by omega
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.
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
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.
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