cycle_power_dyadic_boundary_pair_of_alternating
In an exactly dyadically covered model at exponent M >= 2 whose bit 1 alternates along the roots, every class has boundary pairing: offset 2^M - 2 is selected iff offset 1 is (exactness at distance 2^M - 2 at vertex p counts the pair (p, p + 2^M - 2) of the class at p and the pair (p, p + 2^M - 2) of the class at p - 1, whose bit 1 is the negation of bit 1 at p).
Statement
theorem cycle_power_dyadic_boundary_pair_of_alternating (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) (halt : ∀ p : ℤ, x (p+1) 1 = !x p 1) : ∀ p : ℤ, x p (2^M - 2) = x p 1
- Source
- Helper for RT-1 (OP-205, arXiv:2610.15635): rungs of cycle_power_dyadic_alternating_half_model (the even and odd halves of the bit-1 classes of an alternating endpoint-only dyadic model form a model one exponent lower)
- Verified
- 07 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 1
- cycle_power_dyadic_alternating_half_tightIn a tight, exactly dyadically covered model at exponent m+1 (m >= 1) with alternating bit 1, for every class with bit 1 both its even…
The proof, explained
The proof specializes the exact dyadic coverage condition to scale j = 1 centered at root p. Since 2^1 = 2, this sum contains exactly two terms, corresponding to offset 0 at root p and offset 1 at root p - 1. By the endpoint lemma, the outer bits at offsets 0 and 2^M - 1 are identically true, so exactness implies that exactly one of x(p, 2^M - 2) and x(p - 1, 1) is true. Finally, combining this with the alternating bit 1 hypothesis x(p, 1) = ¬x(p - 1, 1) forces x(p, 2^M - 2) = x(p, 1).
Fix an arbitrary class root p ∈ ℤ, note that endpoints at offsets 0 and 2^M - 1 are true for all roots, and instantiate exact coverage at scale j = 1 at root p.
We fix an arbitrary integer root p. By the lemma cycle_power_dyadic_exact_endpoints (applicable because M ≥ 2 ≥ 1), every root q has true endpoint bits: x(q, 0) = true and x(q, 2^M - 1) = true. We then instantiate the exact coverage hypothesis hexact at scale j = 1 (since 1 < M) and vertex v = p.
uses
cycle_power_dyadic_exact_endpointsintro p have hend := cycle_power_dyadic_exact_endpoints M (by omega) x hexact have h := hexact 1 (by omega) p
The inequality 4 ≤ 2^M holds, and the offset expressions 1 + 2^M - 2 and 0 + 2^M - 2 simplify to 2^M - 1 and 2^M - 2.
Because 2 > 0 and 2 ≤ M, monotonicity of powers (Nat.pow_le_pow_right) shows 4 = 2^2 ≤ 2^M. With 2^M ≥ 4, linear natural number arithmetic (omega) verifies that 1 + 2^M - 2 = 2^M - 1 and 0 + 2^M - 2 = 2^M - 2 without truncated subtraction.
uses
Nat.pow_le_pow_righthave hM4 : 4 ≤ 2 ^ M := by calc 4 = 2 ^ 2 := by norm_num _ ≤ 2 ^ M := Nat.pow_le_pow_right (by decide) hM have e1 : 1 + 2 ^ M - 2 = 2 ^ M - 1 := by omega have e0 : 0 + 2 ^ M - 2 = 2 ^ M - 2 := by omega
The exactness sum at scale j = 1 expands to (x(p, 0) && x(p, 2^M - 2)).toNat + (x(p - 1, 1) && x(p - 1, 2^M - 1)).toNat = 1.
Since 2^1 = 2 by pow_one, the sum over range (2^1) consists of two terms, a = 0 and a = 1, unpacked via Finset.sum_range_succ and Finset.sum_range_one. Simplifying the integer casts and subtractions p - 0 = p and p - 1, and replacing the index arithmetic using e0 and e1, yields the explicit two-term sum.
uses
pow_one,Finset.sum_range_succ,Finset.sum_range_one,Nat.cast_zero,sub_zero,Nat.cast_onerw [pow_one, Finset.sum_range_succ, Finset.sum_range_one] at h simp only [Nat.cast_zero, sub_zero, Nat.cast_one] at h rw [e0, e1] at h
The alternating bit 1 condition at root p - 1 gives x(p, 1) = !x(p - 1, 1).
We specialize the alternation hypothesis halt to root p - 1, which states that x((p - 1) + 1, 1) = !x(p - 1, 1). Since (p - 1) + 1 = p by sub_add_cancel, this relates the bit 1 values at p and p - 1.
uses
sub_add_cancelhave ha := halt (p - 1) rw [sub_add_cancel] at ha
Substituting the known true endpoint values into the exactness sum simplifies it to (true && x(p, 2^M - 2)).toNat + (x(p - 1, 1) && true).toNat = 1.
From the endpoint lemma, we extract x(p, 0) = true and x(p - 1, 2^M - 1) = true. Rewriting with these values removes the known outer bits from the two-term exactness sum.
have hp0 := (hend p).1 have hq1 := (hend (p - 1)).2 rw [hp0, hq1] at h
The boundary pairing identity x(p, 2^M - 2) = x(p, 1) holds. automation
Rewriting the target using x(p, 1) = !x(p - 1, 1) reduces the goal to x(p, 2^M - 2) = !x(p - 1, 1). A case split on the two boolean variables x(p, 2^M - 2) and x(p - 1, 1) produces four cases; the cases where both are false or both are true contradict the sum being 1, and simp_all closes all four cases.
rw [ha] cases h2 : x p (2 ^ M - 2) <;> cases h3 : x (p - 1) 1 <;> simp_all
cycle_power_dyadic_exact_endpoints- In an exact dyadic model with exponent m ≥ 1, the first (offset 0) and last (offset 2^m - 1) bits of every class p are both true.
Nat.pow_le_pow_right- Exponentiation with a positive base preserves weak inequality between exponents.
pow_one- Raising any element of a monoid to the first power yields the element itself.
Finset.sum_range_succ- The sum of a function over {0, ..., n} equals the sum over {0, ..., n - 1} plus the term at n.
Finset.sum_range_one- The sum of a function over the singleton range {0} is the value of the function at 0.
Nat.cast_zero- The canonical coercion of the natural number 0 into an additive monoid with one is 0.
sub_zero- Subtracting zero from an element leaves it unchanged.
Nat.cast_one- The canonical coercion of the natural number 1 into an additive monoid with one is 1.
sub_add_cancel- Subtracting an element and then adding it back recovers the original element.
- The auxiliary bound 4 ≤ 2^M is established to guarantee that the natural number subtractions in the index arithmetic do not underflow, allowing omega to simplify e0 and e1.
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_pair_of_alternating (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) (halt : ∀ p : ℤ, x (p+1) 1 = !x p 1) : ∀ p : ℤ, x p (2^M - 2) = x p 1 := by intro p have hend := cycle_power_dyadic_exact_endpoints M (by omega) x hexact have h := hexact 1 (by omega) p have hM4 : 4 ≤ 2 ^ M := by calc 4 = 2 ^ 2 := by norm_num _ ≤ 2 ^ M := Nat.pow_le_pow_right (by decide) hM have e1 : 1 + 2 ^ M - 2 = 2 ^ M - 1 := by omega have e0 : 0 + 2 ^ M - 2 = 2 ^ M - 2 := by omega rw [pow_one, Finset.sum_range_succ, Finset.sum_range_one] at h simp only [Nat.cast_zero, sub_zero, Nat.cast_one] at h rw [e0, e1] at h have ha := halt (p - 1) rw [sub_add_cancel] at ha have hp0 := (hend p).1 have hq1 := (hend (p - 1)).2 rw [hp0, hq1] at h rw [ha] cases h2 : x p (2 ^ M - 2) <;> cases h3 : x (p - 1) 1 <;> simp_all