AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_outer_pair_forward

theoremverified

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

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.

  1. 8 ≤ 2^m

    Since m ≥ 3, monotonicity of powers with base 2 (Nat.pow_le_pow_right) gives 8 = 2^3 ≤ 2^m.

    lines 9–11

    uses Nat.pow_le_pow_right

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

    lines 12–16

    uses cycle_power_dyadic_exact_endpoints, cycle_power_dyadic_boundary_pairing_alternates

      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)
  3. 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.

    lines 17–19

    uses Bool.eq_false_of_not_eq_true

      intro p hbit h3
      by_contra h2'
      have h2 : x p 2 = false := Bool.eq_false_of_not_eq_true h2'
  4. 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.

    lines 20–24

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

    lines 25–32

    uses Bool.eq_true_of_not_eq_false, cycle_power_exact_pair_unique

      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
  6. 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}.

    lines 33–35

      obtain ⟨a, ha, ha1, ha2⟩ := hcover (2^m-3) (by omega) (by omega) (p+2)
      have ha' : a < 3 := by omega
      interval_cases a
  7. 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.

    lines 36–37

      · have hh : x (p+2) (2^m-3) = true := by simpa using ha2
        rw [hp21] at hh; contradiction
  8. 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.

    lines 38–39

      · have hh : x (p+1) 1 = true := by simpa [show p+2-1 = p+1 by ring] using ha1
        rw [hp1] at hh; contradiction
  9. 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.

    lines 40–41

      · 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

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