AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_boundary_pairing_alternates

theoremverified

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

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.

  1. $4 \le 2^m$

    Since $m \ge 2$, we have $4 = 2^2 \le 2^m$ by monotonicity of powers of 2.

    lines 6–8

    uses Nat.pow_le_pow_right

      have hD : 4 ≤ 2^m := by
        calc 4 = 2^2 := by norm_num
          _ ≤ 2^m := Nat.pow_le_pow_right (by norm_num) hm
  2. 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.

    line 9

    uses cycle_power_dyadic_exact_endpoints

      have ends := cycle_power_dyadic_exact_endpoints m (by omega) x hexact
  3. 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.

    lines 10–14

    uses pow_one, Finset.sum_range_succ, Finset.sum_range_zero, zero_add, Nat.cast_zero, sub_zero, Nat.cast_one, add_sub_cancel_right

      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
  4. 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.

    line 15

    uses Bool.true_and, Bool.and_true

      simp only [(ends (p + 1)).1, (ends p).2, ← h1 (p + 1), Bool.true_and, Bool.and_true] at e
  5. $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.

    lines 16–17

      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$.

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_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
See it in the graphDiscuss this resultChallenge it