AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_alternating_paired_of_pairing

theoremverified

For m ≥ 2, a tight, exactly dyadically covered integer Boolean class model x : ℤ → ℕ → Bool at exponent m with x p 1 = x p (2^m - 2) for every p and the pairings x p (2i) = x p (2i+1) for 1 ≤ i, i + 1 < 2^(m-1), has the alternating-paired structure: x (p+1) 1 = !(x p 1); a class with x p 1 = false has x p j = false for 0 < j < 2^m - 1; a class with x p 1 = true has x p (2j) = x p (2j+1) for every j < 2^(m-1).

Statement

theorem cycle_power_dyadic_alternating_paired_of_pairing (m : ℕ) (hm : 2 ≤ m) (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) =
      (Finset.range (2^m)).sum (fun a => (x p a).toNat))
    (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))
    (hpr : ∀ p : ℤ, ∀ i, 1 ≤ i → i + 1 < 2^(m-1) → x p (2*i) = x p (2*i+1)) :
    (∀ p : ℤ, x (p+1) 1 = !x p 1) ∧
      (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^m - 1 → x p j = false) ∧
      (∀ p : ℤ, x p 1 = true → ∀ j < 2^(m-1), x p (2*j) = x p (2*j+1))
Source
Research thread RT-1, OP-205 (arXiv:2610.15635, Theorems 1.3-1.4: eq(C_n^k) for k+1 = 2^m, n even, (k+1) not dividing n). Reduces the hypothesis of simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_alternating_paired to pairing lemmas of the form of the proved m = 4 lemmas one_iff_fourteen, two_iff_three, ..., twelve_iff_thirteen.
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The proof establishes the alternating-paired structure of a tight, dyadically covered class model by analyzing the dyadic covering constraints at low scales. The scale j = 0 constraint forces both boundary bits x(v, 0) and x(v, 2^m - 1) to be true for every class v. The scale j = 1 constraint links adjacent classes, forcing the sum of x(p+1, 1) and x(p, 1) to equal 1, which establishes the alternation x(p+1, 1) = !(x p 1). Finally, classes with x(p, 1) = false have no true inner bits by an established tightness lemma, while classes with x(p, 1) = true extend the interior pairing to all blocks by matching boundary values.

  1. 2^m = 2 * 2^(m - 1) and 2 ≤ 2^(m - 1).

    Since m ≥ 2, we can rewrite m as (m - 1) + 1, so the exponent law `pow_succ'` gives 2^m = 2 * 2^(m - 1). Furthermore, since m - 1 ≥ 1, monotonicity of powers of 2 (`Nat.pow_le_pow_right`) yields 2 = 2^1 ≤ 2^(m - 1).

    lines 11–15

    uses pow_succ', Nat.pow_le_pow_right

      have hD : 2 ^ m = 2 * 2 ^ (m - 1) := by
        rw [← pow_succ']; congr 1; omega
      have hH : 2 ≤ 2 ^ (m - 1) := by
        calc 2 = 2 ^ 1 := by norm_num
          _ ≤ 2 ^ (m - 1) := Nat.pow_le_pow_right (by norm_num) (by omega)
  2. For every class v ∈ ℤ, both boundary bits are true: x v 0 = true and x v (2^m - 1) = true.

    Instantiate the exact dyadic covering condition `hexact` at scale j = 0 for class v. The sum over range 2^0 = 1 has only the term a = 0, which reduces to (x v 0 && x v (2^m - 1)).toNat = 1. A boolean conjunction can only evaluate to 1 if both components are true, verified by checking truth values.

    lines 16–22

    uses pow_zero, Finset.range_one, Finset.sum_singleton, Nat.cast_zero, sub_zero, zero_add

      have hends : ∀ v : ℤ, x v 0 = true ∧ x v (2 ^ m - 1) = true := by
        intro v
        have e := hexact 0 (by omega) v
        simp only [pow_zero, Finset.range_one, Finset.sum_singleton, Nat.cast_zero, sub_zero,
          zero_add] at e
        revert e
        cases x v 0 <;> cases x v (2 ^ m - 1) <;> decide
  3. For every class p, the bit at index 1 alternates with parity: x (p + 1) 1 = !(x p 1).

    Decompose the main conjunction into its three constituent parts and consider the first. Evaluating `hexact` at scale j = 1 for class p + 1 yields a sum of two terms: a = 0 gives x (p + 1) 0 && x (p + 1) (2^m - 2), and a = 1 gives x p 1 && x p (2^m - 1). Since the endpoints x (p + 1) 0 and x p (2^m - 1) are true by `hends`, and x (p + 1) (2^m - 2) = x (p + 1) 1 by hypothesis `h1`, this sum simplifies to (x (p + 1) 1).toNat + (x p 1).toNat = 1. Evaluating all four boolean combinations confirms that x (p + 1) 1 = !(x p 1).

    lines 23–31

    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, Bool.true_and, Bool.and_true

      refine ⟨?_, ?_, ?_⟩
      · 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 [(hends (p + 1)).1, (hends 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
  4. If x p 1 = false, then all inner bits vanish: x p j = false for every 0 < j < 2^m - 1.

    Suppose for contradiction that some inner bit x p j is true. By lemma `cycle_power_dyadic_tight_class_inner_imp_one`, in any class satisfying tightness (`htight`), symmetry (`h1`), and internal pairing (`hpr`), a single true inner bit forces x p 1 = true. This contradicts the assumption x p 1 = false.

    lines 32–36

    uses cycle_power_dyadic_tight_class_inner_imp_one

      · intro p hp j hj0 hj1
        by_contra hne
        have hb : x p j = true := by simpa using hne
        have := cycle_power_dyadic_tight_class_inner_imp_one m hm (x p) (htight p) (h1 p) (hpr p) j hj0 hj1 hb
        rw [hp] at this; exact absurd this (by decide)
  5. If x p 1 = true, then pairing extends to all blocks: x p (2 * j) = x p (2 * j + 1) for every j < 2^(m - 1).

    We split on j using `Nat.eq_zero_or_pos`. If j = 0, the pair is indices 0 and 1; x p 0 = true by `hends` and x p 1 = true by assumption, so they are equal. If j > 0, we split into j + 1 < 2^(m - 1) and j + 1 = 2^(m - 1). The strictly interior case is covered directly by the pairing hypothesis `hpr`. The boundary case j + 1 = 2^(m - 1) corresponds to indices 2^m - 2 and 2^m - 1; here x p (2^m - 2) = x p 1 = true by `h1` and x p (2^m - 1) = true by `hends`, so both sides are true.

    lines 37–43

    uses Nat.eq_zero_or_pos, Nat.mul_zero, zero_add

      · intro p hp j hj
        rcases Nat.eq_zero_or_pos j with h0 | h0
        · subst h0; simp only [Nat.mul_zero, zero_add]; rw [hp, (hends p).1]
        rcases (show j + 1 < 2 ^ (m - 1) ∨ j + 1 = 2 ^ (m - 1) by omega) with hlt | heq
        · exact hpr p j h0 hlt
        · rw [show 2 * j = 2 ^ m - 2 by omega, show 2 ^ m - 2 + 1 = 2 ^ m - 1 by omega, ← h1 p, hp,
            (hends p).2]
pow_succ'
For any element a of a monoid, a^(n+1) = a * a^n.
Nat.pow_le_pow_right
If n > 0 and i ≤ j, then n^i ≤ n^j.
pow_zero
Any element raised to the zeroth power is 1.
Finset.range_one
The range of length 1 is the singleton set {0}.
Finset.sum_singleton
The sum of a function over a singleton set {a} is the value f(a).
Nat.cast_zero
The natural number 0 casts to 0 in any additive monoid with one.
sub_zero
Subtracting 0 leaves an element unchanged.
zero_add
Adding 0 on the left leaves an element unchanged.
pow_one
Any element raised to the first power is itself.
Finset.sum_range_succ
Summing over the range 0, ..., n equals the sum over 0, ..., n-1 plus the term at n.
Finset.sum_range_zero
The sum over an empty range of natural numbers is 0.
Nat.cast_one
The natural number 1 casts to 1 in any additive monoid with one.
add_sub_cancel_right
Adding b and then subtracting b returns the original element.
Bool.true_and
The conjunction true && b evaluates to b.
Bool.and_true
The conjunction b && true evaluates to b.
cycle_power_dyadic_tight_class_inner_imp_one
In a tight dyadic class with pairing and outer symmetry, if any inner bit b(j) is true for 0 < j < 2^m - 1, then b(1) must be true.
Nat.eq_zero_or_pos
Every natural number is either zero or strictly positive.
Nat.mul_zero
Multiplying any natural number by zero yields zero.

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_alternating_paired_of_pairing (m : ℕ) (hm : 2 ≤ m) (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) =      (Finset.range (2^m)).sum (fun a => (x p a).toNat))    (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))    (hpr : ∀ p : ℤ, ∀ i, 1 ≤ i → i + 1 < 2^(m-1) → x p (2*i) = x p (2*i+1)) :    (∀ p : ℤ, x (p+1) 1 = !x p 1) ∧      (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^m - 1 → x p j = false) ∧      (∀ p : ℤ, x p 1 = true → ∀ j < 2^(m-1), x p (2*j) = x p (2*j+1)) := by  have hD : 2 ^ m = 2 * 2 ^ (m - 1) := by    rw [← pow_succ']; congr 1; omega  have hH : 2 ≤ 2 ^ (m - 1) := by    calc 2 = 2 ^ 1 := by norm_num      _ ≤ 2 ^ (m - 1) := Nat.pow_le_pow_right (by norm_num) (by omega)  have hends : ∀ v : ℤ, x v 0 = true ∧ x v (2 ^ m - 1) = true := by    intro v    have e := hexact 0 (by omega) v    simp only [pow_zero, Finset.range_one, Finset.sum_singleton, Nat.cast_zero, sub_zero,      zero_add] at e    revert e    cases x v 0 <;> cases x v (2 ^ m - 1) <;> decide  refine ⟨?_, ?_, ?_⟩  · 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 [(hends (p + 1)).1, (hends 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  · intro p hp j hj0 hj1    by_contra hne    have hb : x p j = true := by simpa using hne    have := cycle_power_dyadic_tight_class_inner_imp_one m hm (x p) (htight p) (h1 p) (hpr p) j hj0 hj1 hb    rw [hp] at this; exact absurd this (by decide)  · intro p hp j hj    rcases Nat.eq_zero_or_pos j with h0 | h0    · subst h0; simp only [Nat.mul_zero, zero_add]; rw [hp, (hends p).1]    rcases (show j + 1 < 2 ^ (m - 1) ∨ j + 1 = 2 ^ (m - 1) by omega) with hlt | heq    · exact hpr p j h0 hlt    · rw [show 2 * j = 2 ^ m - 2 by omega, show 2 ^ m - 2 + 1 = 2 ^ m - 1 by omega, ← h1 p, hp,        (hends p).2]
See it in the graphDiscuss this resultChallenge it