cycle_power_dyadic_boundary_pairing_alternates
In an exact dyadic Boolean class model with exponent at least two, equality of the two boundary bits in every class forces the first inner bit to alternate between successive classes.
Statement
theorem cycle_power_dyadic_boundary_pairing_alternates (m : ℕ) (hm : 2 ≤ 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) (h1 : ∀ p : ℤ, x p 1 = x p (2^m-2)) : ∀ p : ℤ, x (p+1) 1 = !x p 1
- 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 1
- 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…
- Used by 3
- cycle_power_dyadic_outer_pair_forwardIn a fully covered exact dyadic Boolean class model with exponent at least three and matching boundary bits in every class, if a class…
- cycle_power_dyadic_outer_pair_reverseFor exponent m at least three, consider a Boolean integer-indexed dyadic class model with exact dyadic ownership at every rank, coverage…
- cycle_power_fifteen_model_alternating_endpointAt exponent 4 (bandwidth 15) every tight, exactly dyadically covered, fully covered integer Boolean class model with five active classes…
The proof, explained
We evaluate the exactness condition at scale $j = 1$ for class shift $p + 1$, yielding a two-term sum of Boolean conjunctions. By the endpoint property of exact models, the outer boundary bits $x(p+1, 0)$ and $x(p, 2^m - 1)$ are true, and the boundary pairing hypothesis equates $x(p+1, 2^m - 2)$ to $x(p+1, 1)$. This reduces the exactness condition to $(x(p+1, 1)).\text{toNat} + (x(p, 1)).\text{toNat} = 1$, which forces the first inner bits of successive classes to alternate.
$4 \le 2^m$
Since $m \ge 2$, we have $4 = 2^2 \le 2^m$ by monotonicity of powers of 2.
uses
Nat.pow_le_pow_righthave hD : 4 ≤ 2^m := by calc 4 = 2^2 := by norm_num _ ≤ 2^m := Nat.pow_le_pow_right (by norm_num) hm
For every class $q \in \mathbb{Z}$, the boundary bits are true: $x(q, 0) = \text{true}$ and $x(q, 2^m - 1) = \text{true}$.
Applying the theorem `cycle_power_dyadic_exact_endpoints` with $m \ge 1$ (which follows from $m \ge 2$), the exactness hypothesis implies that the first and last bits of every class are true.
uses
cycle_power_dyadic_exact_endpointshave ends := cycle_power_dyadic_exact_endpoints m (by omega) x hexact
For any class $p$, the exactness sum at scale $j = 1$ and position $p + 1$ expands to $(x(p+1, 0) \land x(p+1, 2^m - 2)).\text{toNat} + (x(p, 1) \land x(p, 2^m - 1)).\text{toNat} = 1$.
We fix an arbitrary class index $p$. Since $2 \le m$, we have $1 < m$, so we instantiate the exactness hypothesis `hexact` at scale $j = 1$ with position $v = p + 1$. The sum has $2^1 = 2$ terms (for $a = 0$ and $a = 1$). Expanding the range summation and simplifying the integer and index arithmetic leaves a two-term sum of Boolean conjunctions.
uses
pow_one,Finset.sum_range_succ,Finset.sum_range_zero,zero_add,Nat.cast_zero,sub_zero,Nat.cast_one,add_sub_cancel_rightintro p have e := hexact 1 (by omega) (p + 1) simp only [pow_one, Finset.sum_range_succ, Finset.sum_range_zero, zero_add, Nat.cast_zero, sub_zero, Nat.cast_one, add_sub_cancel_right] at e rw [show 1 + 2 ^ m - 2 = 2 ^ m - 1 by omega] at e
The expanded sum simplifies to $(x(p+1, 1)).\text{toNat} + (x(p, 1)).\text{toNat} = 1$.
Using the endpoint results (`ends`), the boundary bits $x(p+1, 0)$ and $x(p, 2^m - 1)$ are both true, which simplifies the conjunctions. Furthermore, the boundary pairing hypothesis `h1` at $p + 1$ equates $x(p+1, 2^m - 2)$ with $x(p+1, 1)$, leaving only the inner bits.
uses
Bool.true_and,Bool.and_truesimp only [(ends (p + 1)).1, (ends p).2, ← h1 (p + 1), Bool.true_and, Bool.and_true] at e
$x(p+1, 1) = \neg x(p, 1)$
The two Booleans $x(p+1, 1)$ and $x(p, 1)$ have numerical values in $\{0, 1\}$ summing to $1$, meaning exactly one of them is true and the other is false. A case analysis over all four combinations of truth values verifies that $x(p+1, 1) = \neg x(p, 1)$ in every case.
revert e cases x (p + 1) 1 <;> cases x p 1 <;> decide
Nat.pow_le_pow_right- For a positive integer base $n$, $n^i \le n^j$ whenever $i \le j$.
cycle_power_dyadic_exact_endpoints- In an exact dyadic Boolean class model with exponent $m \ge 1$, the first and last bits of every class $p$ are true: $x(p, 0) = \text{true}$ and $x(p, 2^m - 1) = \text{true}$.
pow_one- Raising an element to the first power yields the element itself ($a^1 = a$).
Finset.sum_range_succ- A finite sum over $\{0, \ldots, n\}$ equals the sum over $\{0, \ldots, n-1\}$ plus the term at $n$.
Finset.sum_range_zero- The sum of a function over the empty range `Finset.range 0` is zero.
zero_add- Zero is the left additive identity ($0 + a = a$).
Nat.cast_zero- The canonical cast of the natural number $0$ into an additive monoid with one is $0$.
sub_zero- Subtracting zero leaves an element unchanged ($a - 0 = a$).
Nat.cast_one- The canonical cast of the natural number $1$ into an additive monoid with one is $1$.
add_sub_cancel_right- Adding and then subtracting the same element cancels out ($(a + b) - b = a$).
Bool.true_and- The Boolean conjunction $\text{true} \land b$ evaluates to $b$.
Bool.and_true- The Boolean conjunction $b \land \text{true}$ evaluates to $b$.
- The bound $4 \le 2^m$ established on lines 6–8 (`hD`) is an unused helper; the subsequent steps rely only on $m \ge 2$ via arithmetic automation.
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_boundary_pairing_alternates (m : ℕ) (hm : 2 ≤ 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) (h1 : ∀ p : ℤ, x p 1 = x p (2^m-2)) : ∀ p : ℤ, x (p+1) 1 = !x p 1 := by have hD : 4 ≤ 2^m := by calc 4 = 2^2 := 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 intro p have e := hexact 1 (by omega) (p + 1) simp only [pow_one, Finset.sum_range_succ, Finset.sum_range_zero, zero_add, Nat.cast_zero, sub_zero, Nat.cast_one, add_sub_cancel_right] at e rw [show 1 + 2 ^ m - 2 = 2 ^ m - 1 by omega] at e simp only [(ends (p + 1)).1, (ends p).2, ← h1 (p + 1), Bool.true_and, Bool.and_true] at e revert e cases x (p + 1) 1 <;> cases x p 1 <;> decide