cycle_power_dyadic_outer_pair_forward
In a fully covered exact dyadic Boolean class model with exponent at least three and matching boundary bits in every class, if a class selects offsets 1 and 3 it also selects offset 2.
Statement
theorem cycle_power_dyadic_outer_pair_forward (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)) : ∀ p : ℤ, x p 1 = true → x p 3 = true → x p 2 = true
- Source
- RT-1, OP-205, arXiv:2610.15635; auxiliary rigidity lemmas for the dyadic cycle-power covering problem.
- Verified
- 02 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 that a class p has x(p, 1) = true and x(p, 3) = true but x(p, 2) = false. The boundary alternation theorem implies that the bit at offset 1 alternates along classes, forcing x(p+1, 1) = false and x(p+2, 1) = true. Uniqueness of the exact dyadic pairing for block size 4 at line p+3 then prevents x(p+2, 2^m - 3) from being true, as offsets 1 and 3 would otherwise both form valid pairs. Finally, the covering condition for distance 2^m - 3 at line p+2 provides a witness offset a < 3, but testing a ∈ {0, 1, 2} contradicts the previous determinations in every case.
8 ≤ 2^m
Since m ≥ 3, monotonicity of powers with base 2 (Nat.pow_le_pow_right) gives 8 = 2^3 ≤ 2^m.
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
Endpoints are true in all classes, offset 1 alternates between consecutive classes, and exact dyadic pairing holds for block size R = 4.
Since m ≥ 3, we have m ≥ 1 and m ≥ 2. Applying cycle_power_dyadic_exact_endpoints shows that x(p, 0) = true and x(p, 2^m - 1) = true for all classes p. Applying cycle_power_dyadic_boundary_pairing_alternates shows x(p+1, 1) = ¬x(p, 1). Specializing the dyadic exactness hypothesis hexact to j = 2 < m yields the exact pairing condition for block size 2^2 = 4.
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, 1) = true and x(p, 3) = true, but x(p, 2) = false.
We fix an arbitrary class p with x(p, 1) = true and x(p, 3) = true. To deduce x(p, 2) = true, we assume for contradiction that x(p, 2) ≠ true, which by Bool.eq_false_of_not_eq_true means x(p, 2) = false.
uses
Bool.eq_false_of_not_eq_trueintro p hbit h3 by_contra h2' have h2 : x p 2 = false := Bool.eq_false_of_not_eq_true h2'
x(p+1, 1) = false and x(p+2, 1) = true
Because x(p, 1) = true, the alternating property along classes gives x(p+1, 1) = ¬true = false. Alternating once more at class p+1 gives x(p+2, 1) = ¬false = true.
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
x(p+2, 2^m - 3) = false
Suppose for contradiction that x(p+2, 2^m - 3) = true (via Bool.eq_true_of_not_eq_false). In the exact pairing for block size R = 4 evaluated along the line v = p + 3, the candidate offset a = 1 pairs x(p+2, 1) with x(p+2, 2^m - 3) (both true), while the candidate offset a = 3 pairs x(p, 3) with x(p, 2^m - 1) (both true). By uniqueness of the satisfying pair (cycle_power_exact_pair_unique), this forces 1 = 3, an arithmetic contradiction.
uses
Bool.eq_true_of_not_eq_false,cycle_power_exact_pair_uniquehave hp21 : x (p+2) (2^m-3) = false := by by_contra hn have hx : x (p+2) (2^m-3) = true := Bool.eq_true_of_not_eq_false hn have eq := cycle_power_exact_pair_unique (2^m) 4 x ex4 (p+3) 1 3 (by omega) (by omega) (by simpa [show p+3-1 = p+2 by ring] using hp2) (by simpa [show p+3-1 = p+2 by ring, show 1 + 2^m - 4 = 2^m - 3 by omega] using hx) (by simpa using h3) (by simpa [show 3 + 2^m - 4 = 2^m - 1 by omega] using (ends p).2) omega
Covering for distance d = 2^m - 3 along line v = p + 2 produces a witness a < 3.
Because 8 ≤ 2^m, the distance d = 2^m - 3 satisfies 1 ≤ d < 2^m. The covering hypothesis hcover along line v = p + 2 guarantees an offset a < 2^m - (2^m - 3) = 3 such that both x(p + 2 - a, a) = true and x(p + 2 - a, a + 2^m - 3) = true. We then split into cases on a ∈ {0, 1, 2}.
obtain ⟨a, ha, ha1, ha2⟩ := hcover (2^m-3) (by omega) (by omega) (p+2) have ha' : a < 3 := by omega interval_cases a
The case a = 0 is impossible.
If a = 0, the second covering condition asserts x(p+2, 2^m - 3) = true, directly contradicting that x(p+2, 2^m - 3) = false.
· have hh : x (p+2) (2^m-3) = true := by simpa using ha2 rw [hp21] at hh; contradiction
The case a = 1 is impossible.
If a = 1, the first covering condition asserts x(p+1, 1) = true, directly contradicting that x(p+1, 1) = false.
· have hh : x (p+1) 1 = true := by simpa [show p+2-1 = p+1 by ring] using ha1 rw [hp1] at hh; contradiction
The case a = 2 is impossible, concluding the proof.
If a = 2, the first covering condition asserts x(p, 2) = true, directly contradicting the contradiction hypothesis x(p, 2) = false. All three cases for a lead to a contradiction.
· have hh : x p 2 = true := by simpa using ha1 rw [h2] at hh; contradiction
Nat.pow_le_pow_right- For any positive base n, exponentiation is monotonic in the exponent: if i ≤ j, then n^i ≤ n^j.
cycle_power_dyadic_exact_endpoints- In an exact dyadic model with exponent m ≥ 1, every class selects both boundary endpoints: offset 0 and offset 2^m - 1 are both true.
cycle_power_dyadic_boundary_pairing_alternates- In an exact dyadic model with m ≥ 2 and matching boundary bits at offsets 1 and 2^m - 2, the bit at offset 1 strictly alternates between consecutive classes: x(p+1, 1) = ¬x(p, 1).
Bool.eq_false_of_not_eq_true- A Boolean value that is not equal to true must equal false.
Bool.eq_true_of_not_eq_false- A Boolean value that is not equal to false must equal true.
cycle_power_exact_pair_unique- In an exact pairing model of block size R, any two offsets a, b < R along the same line v that satisfy the paired-bit condition must be equal.
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_forward (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)) : ∀ p : ℤ, x p 1 = true → x p 3 = true → x p 2 = 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 h3 by_contra h2' have h2 : x p 2 = false := Bool.eq_false_of_not_eq_true h2' 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 hp21 : x (p+2) (2^m-3) = false := by by_contra hn have hx : x (p+2) (2^m-3) = true := Bool.eq_true_of_not_eq_false hn have eq := cycle_power_exact_pair_unique (2^m) 4 x ex4 (p+3) 1 3 (by omega) (by omega) (by simpa [show p+3-1 = p+2 by ring] using hp2) (by simpa [show p+3-1 = p+2 by ring, show 1 + 2^m - 4 = 2^m - 3 by omega] using hx) (by simpa using h3) (by simpa [show 3 + 2^m - 4 = 2^m - 1 by omega] using (ends p).2) omega obtain ⟨a, ha, ha1, ha2⟩ := hcover (2^m-3) (by omega) (by omega) (p+2) have ha' : a < 3 := by omega interval_cases a · have hh : x (p+2) (2^m-3) = true := by simpa using ha2 rw [hp21] at hh; contradiction · have hh : x (p+1) 1 = true := by simpa [show p+2-1 = p+1 by ring] using ha1 rw [hp1] at hh; contradiction · have hh : x p 2 = true := by simpa using ha1 rw [h2] at hh; contradiction