AFTD Auto-Formalizing Theoretical Domains

cycle_power_fifteen_model_alternating_endpoint

theoremverified

At exponent 4 (bandwidth 15) every tight, exactly dyadically covered, fully covered integer Boolean class model with five active classes per vertex has alternating bit 1, and every class without bit 1 has no inner bit.

Statement

theorem cycle_power_fifteen_model_alternating_endpoint (x : ℤ → ℕ → Bool)
    (htight : ∀ p, cycle_power_dyadic_class_weight 4 (x p) =
      (Finset.range (2^4)).sum (fun a => (x p a).toNat))
    (hexact : ∀ j < 4, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>
      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^4-2^j)).toNat) = 1)
    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^4 → ∀ v : ℤ,
      ∃ a : ℕ, a < 2^4-d ∧ x (v-(a : ℤ)) a = true ∧
        x (v-(a : ℤ)) (a+d) = true)
    (hcount : ∀ v : ℤ, (Finset.range (2^4)).sum (fun a =>
      (x (v-(a : ℤ)) a).toNat) = 4+1) :
    (∀ p : ℤ, x (p+1) 1 = !x p 1) ∧
    (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^4 - 1 → x p j = false)
Source
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). Session 2026-11-09: folding offsets modulo 2^t (experiment 19407).
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1

The proof, explained

The theorem proves that any tight, dyadically exact, fully covered integer Boolean class model of bandwidth 15 with 5 active classes per vertex has alternating bit 1 along the integer line (x (p + 1) 1 = ¬ x p 1) and that any class with x p 1 = false has all internal bits false (x p j = false for 0 < j < 15). The proof first shows the boundary bits x p 0 and x p 15 are identically true, then verifies the dyadic parent relations, the inner active class count of 3, and dyadic exact coverage at distances 8, 12, 14. These enable cycle_power_fifteen_tight_type_sequence_one_iff_fourteen, establishing x p 1 = x p 14. In turn, cycle_power_dyadic_boundary_pairing_alternates proves the alternating bit 1 property, and the 'no island' lemma cycle_power_fifteen_model_no_island ensures that no intermediate bit can be true when the boundary bits 1 and 14 are false.

  1. Every class has active boundary bits: x p 0 = true and x p 15 = true for all p.

    Specializing the exact dyadic covering hypothesis hexact at scale j = 0 for vertex v produces a single-term sum of (x v 0 && x v 15) = 1. This implies that both x v 0 and x v 15 are true for every class.

    lines 13–19

      have hends : ∀ v : ℤ, x v 0 = true ∧ x v 15 = true := by
        intro v
        have h := hexact 0 (by norm_num) v
        simp at h
        exact h
      have h0 : ∀ p, x p 0 = true := fun p => (hends p).1
      have h15 : ∀ p, x p 15 = true := fun p => (hends p).2
  2. Active bits satisfy all 14 parent-child implication edges of the dyadic tree in every class.

    For each edge (u, v) in the explicit set of 14 pairs, if bit u is active in class p, then bit v must also be active. When v is 0 or 15, the claim follows from the boundary bits being unconditionally true. For all other pairs, the implication is a dyadic parent relation established by cycle_power_dyadic_tight_class_parent at dyadic levels j = 2 and j = 3.

    lines 20–41

    uses cycle_power_dyadic_tight_class_parent, Finset.mem_insert, Finset.mem_singleton

      have hparent : ∀ p : ℤ, ∀ e ∈ ({(1,15),(2,14),(3,15),(4,12),(5,13),(6,14),(7,15),
          (8,0),(9,1),(10,2),(11,3),(12,0),(13,1),(14,0)} : Finset (ℕ × ℕ)),
          x p e.1 = true → x p e.2 = true := by
        intro p e he h
        have P2 := cycle_power_dyadic_tight_class_parent 4 2 (by norm_num) (by norm_num) (x p) (htight p)
        have P3 := cycle_power_dyadic_tight_class_parent 4 3 (by norm_num) (by norm_num) (x p) (htight p)
        simp only [Finset.mem_insert, Finset.mem_singleton] at he
        rcases he with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl
        · exact h15 p
        · exact (P2 2 (by norm_num)).2 (by norm_num) h
        · exact h15 p
        · exact (P3 4 (by norm_num)).2 (by norm_num) h
        · exact (P3 5 (by norm_num)).2 (by norm_num) h
        · exact (P3 6 (by norm_num)).2 (by norm_num) h
        · exact h15 p
        · exact h0 p
        · exact (P3 1 (by norm_num)).1 (by norm_num) h
        · exact (P3 2 (by norm_num)).1 (by norm_num) h
        · exact (P3 3 (by norm_num)).1 (by norm_num) h
        · exact h0 p
        · exact (P2 1 (by norm_num)).1 (by norm_num) h
        · exact h0 p
  3. For each vertex, the sum of its 14 internal bits equals 3.

    By hypothesis hcount, the total number of active classes covering any vertex v across all 16 bits is 5. Splitting off the boundary terms at a = 0 (which is x v 0 = 1) and a = 15 (which is x (v - 15) 15 = 1) using Finset.sum_range_succ and Finset.sum_range_succ', linear arithmetic confirms that the sum over the 14 internal bits j ∈ {1, ..., 14} is 5 - 1 - 1 = 3.

    lines 42–49

    uses Finset.sum_range_succ, Finset.sum_range_succ'

      have hcount' : ∀ v : ℤ, (Finset.range 14).sum
          (fun j => (x (v - ((j + 1 : ℕ) : ℤ)) (j + 1)).toNat) = 3 := by
        intro v
        have h := hcount v
        rw [show (2:ℕ)^4 = 14 + 1 + 1 by norm_num, Finset.sum_range_succ, Finset.sum_range_succ'] at h
        have e0 : (x (v - ((0 : ℕ) : ℤ)) 0).toNat = 1 := by rw [h0]; rfl
        have e15 : (x (v - ((14 + 1 : ℕ) : ℤ)) (14 + 1)).toNat = 1 := by rw [h15]; rfl
        omega
  4. Exact covering holds at distances d ∈ {8, 12, 14}.

    For each distance d ∈ {8, 12, 14}, the exact covering sum is rewritten to match the dyadic covering hypothesis hexact at scales j = 3, 2, 1 respectively, because 16 - d = 2^j and a + 2^4 - 2^j = a + d.

    lines 50–67

    uses Finset.mem_insert, Finset.mem_singleton, Eq.trans, Finset.sum_congr, Nat.reducePow

      have hexact' : ∀ d ∈ ({8,12,14} : Finset ℕ), ∀ v : ℤ,
          (Finset.range (16 - d)).sum (fun a =>
            (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + d)).toNat) = 1 := by
        intro d hd v
        simp only [Finset.mem_insert, Finset.mem_singleton] at hd
        rcases hd with rfl | rfl | rfl
        · rw [show 16 - 8 = 2^3 by norm_num]
          refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 3 (by norm_num) v)
          intro a _
          rw [show a + 2^4 - 2^3 = a + 8 by simp only [Nat.reducePow]; omega]
        · rw [show 16 - 12 = 2^2 by norm_num]
          refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 2 (by norm_num) v)
          intro a _
          rw [show a + 2^4 - 2^2 = a + 12 by simp only [Nat.reducePow]; omega]
        · rw [show 16 - 14 = 2^1 by norm_num]
          refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 1 (by norm_num) v)
          intro a _
          rw [show a + 2^4 - 2^1 = a + 14 by simp only [Nat.reducePow]; omega]
  5. The covering condition holds for all distances 1 ≤ d < 15.

    Given 1 ≤ d < 15, the covering hypothesis hcover immediately provides a witness a < 16 - d since 2^4 = 16.

    lines 68–72

    uses Nat.reducePow

      have hcover' : ∀ (d : ℕ), 1 ≤ d → d < 15 → ∀ v : ℤ,
          ∃ a < 16 - d, x (v - (a : ℤ)) a = true ∧ x (v - (a : ℤ)) (a + d) = true := by
        intro d hd1 hd v
        obtain ⟨a, ha, h1, h2⟩ := hcover d hd1 (by simp only [Nat.reducePow]; omega) v
        exact ⟨a, by simp only [Nat.reducePow] at ha; omega, h1, h2⟩
  6. In every class p, bit 1 is active if and only if bit 14 is active: x p 1 = x p 14.

    Applying the classification theorem cycle_power_fifteen_tight_type_sequence_one_iff_fourteen with the established boundary conditions, parent graph, inner sum of 3, exact covering at {8, 12, 14}, and general covering condition yields x p 1 = x p 14 for all p.

    line 73

    uses cycle_power_fifteen_tight_type_sequence_one_iff_fourteen

      have h114 := cycle_power_fifteen_tight_type_sequence_one_iff_fourteen x h0 h15 hparent hcount' hexact' hcover'
  7. Bit 1 alternates between consecutive classes: x (p + 1) 1 = ¬ x p 1 for all p.

    Applying cycle_power_dyadic_boundary_pairing_alternates at exponent m = 4, the exact dyadic coverage together with the boundary pairing x p 1 = x p 14 (noting 2^4 - 2 = 14) implies that bit 1 strictly alternates from one class to the next along the integer line.

    lines 74–76

    uses cycle_power_dyadic_boundary_pairing_alternates

      refine ⟨cycle_power_dyadic_boundary_pairing_alternates 4 (by norm_num) x hexact ?_, ?_⟩
      · intro p
        simpa using h114 p
  8. If bit 1 is false in class p, then all internal bits j ∈ {1, ..., 14} are false in class p.

    Suppose for contradiction that x p j = true for some 0 < j < 15 when x p 1 = false. Since x p 1 = x p 14, we also have x p 14 = false, which implies j ≠ 1 and j ≠ 14, hence 1 < j < 14. The 'no island' property cycle_power_fifteen_model_no_island applied with a = 1, b = j, and c = 14 states that x p 1 = false and x p j = true forces x p 14 = true, contradicting x p 14 = false.

    lines 77–88

    uses cycle_power_fifteen_model_no_island, Nat.reducePow

      · intro p hp j hj1 hj2
        cases hx : x p j with
        | false => rfl
        | true =>
          exfalso
          have h14 : x p 14 = false := by rw [← h114 p]; exact hp
          have hj3 : j ≠ 1 := fun e => by rw [e, hp] at hx; exact absurd hx (by simp)
          have hj4 : j ≠ 14 := fun e => by rw [e, h14] at hx; exact absurd hx (by simp)
          have := cycle_power_fifteen_model_no_island x htight hexact hcover hcount p 1 j 14
            (by omega) (by simp only [Nat.reducePow] at hj2; omega) (by norm_num) hp hx
          rw [h14] at this
          exact absurd this (by simp)
Eq.trans
Transitivity of equality: if a = b and b = c, then a = c.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their terms agree on all elements.
Finset.sum_range_succ
Splits a sum over range (n + 1) into the sum over range n plus the term at n.
Finset.sum_range_succ'
Splits a sum over range (n + 1) into the term at 0 plus the shifted sum of f (k + 1) over range n.
Nat.reducePow
Simplification procedure that computes natural number exponentiation.
cycle_power_dyadic_boundary_pairing_alternates
In an exact dyadic covering model where the boundary bits pair up (x p 1 = x p (2^m - 2)), bit 1 strictly alternates between adjacent classes: x (p + 1) 1 = ¬ x p 1.
cycle_power_dyadic_tight_class_parent
In a tight dyadic class, if an active bit belongs to a dyadic interval, its parent bit in the dyadic hierarchy must also be active.
cycle_power_fifteen_model_no_island
In a valid model of exponent 4, an active bit cannot be strictly flanked by inactive ones: if a < b < c, x p a = false, and x p b = true, then x p c must be true.
cycle_power_fifteen_tight_type_sequence_one_iff_fourteen
Under boundary, tree-parent, inner-sum, exact dyadic coverage, and general coverage conditions at bandwidth 15, bit 1 is active if and only if bit 14 is active in every class: x p 1 = x p 14.

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_fifteen_model_alternating_endpoint (x : ℤ → ℕ → Bool)    (htight : ∀ p, cycle_power_dyadic_class_weight 4 (x p) =      (Finset.range (2^4)).sum (fun a => (x p a).toNat))    (hexact : ∀ j < 4, ∀ v : ℤ, (Finset.range (2^j)).sum (fun a =>      (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^4-2^j)).toNat) = 1)    (hcover : ∀ d : ℕ, 1 ≤ d → d < 2^4 → ∀ v : ℤ,      ∃ a : ℕ, a < 2^4-d ∧ x (v-(a : ℤ)) a = true ∧        x (v-(a : ℤ)) (a+d) = true)    (hcount : ∀ v : ℤ, (Finset.range (2^4)).sum (fun a =>      (x (v-(a : ℤ)) a).toNat) = 4+1) :    (∀ p : ℤ, x (p+1) 1 = !x p 1) ∧    (∀ p : ℤ, x p 1 = false → ∀ j, 0 < j → j < 2^4 - 1 → x p j = false) := by  have hends : ∀ v : ℤ, x v 0 = true ∧ x v 15 = true := by    intro v    have h := hexact 0 (by norm_num) v    simp at h    exact h  have h0 : ∀ p, x p 0 = true := fun p => (hends p).1  have h15 : ∀ p, x p 15 = true := fun p => (hends p).2  have hparent : ∀ p : ℤ, ∀ e ∈ ({(1,15),(2,14),(3,15),(4,12),(5,13),(6,14),(7,15),      (8,0),(9,1),(10,2),(11,3),(12,0),(13,1),(14,0)} : Finset (ℕ × ℕ)),      x p e.1 = true → x p e.2 = true := by    intro p e he h    have P2 := cycle_power_dyadic_tight_class_parent 4 2 (by norm_num) (by norm_num) (x p) (htight p)    have P3 := cycle_power_dyadic_tight_class_parent 4 3 (by norm_num) (by norm_num) (x p) (htight p)    simp only [Finset.mem_insert, Finset.mem_singleton] at he    rcases he with rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl | rfl    · exact h15 p    · exact (P2 2 (by norm_num)).2 (by norm_num) h    · exact h15 p    · exact (P3 4 (by norm_num)).2 (by norm_num) h    · exact (P3 5 (by norm_num)).2 (by norm_num) h    · exact (P3 6 (by norm_num)).2 (by norm_num) h    · exact h15 p    · exact h0 p    · exact (P3 1 (by norm_num)).1 (by norm_num) h    · exact (P3 2 (by norm_num)).1 (by norm_num) h    · exact (P3 3 (by norm_num)).1 (by norm_num) h    · exact h0 p    · exact (P2 1 (by norm_num)).1 (by norm_num) h    · exact h0 p  have hcount' : ∀ v : ℤ, (Finset.range 14).sum      (fun j => (x (v - ((j + 1 : ℕ) : ℤ)) (j + 1)).toNat) = 3 := by    intro v    have h := hcount v    rw [show (2:ℕ)^4 = 14 + 1 + 1 by norm_num, Finset.sum_range_succ, Finset.sum_range_succ'] at h    have e0 : (x (v - ((0 : ℕ) : ℤ)) 0).toNat = 1 := by rw [h0]; rfl    have e15 : (x (v - ((14 + 1 : ℕ) : ℤ)) (14 + 1)).toNat = 1 := by rw [h15]; rfl    omega  have hexact' : ∀ d ∈ ({8,12,14} : Finset ℕ), ∀ v : ℤ,      (Finset.range (16 - d)).sum (fun a =>        (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + d)).toNat) = 1 := by    intro d hd v    simp only [Finset.mem_insert, Finset.mem_singleton] at hd    rcases hd with rfl | rfl | rfl    · rw [show 16 - 8 = 2^3 by norm_num]      refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 3 (by norm_num) v)      intro a _      rw [show a + 2^4 - 2^3 = a + 8 by simp only [Nat.reducePow]; omega]    · rw [show 16 - 12 = 2^2 by norm_num]      refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 2 (by norm_num) v)      intro a _      rw [show a + 2^4 - 2^2 = a + 12 by simp only [Nat.reducePow]; omega]    · rw [show 16 - 14 = 2^1 by norm_num]      refine Eq.trans (Finset.sum_congr rfl ?_) (hexact 1 (by norm_num) v)      intro a _      rw [show a + 2^4 - 2^1 = a + 14 by simp only [Nat.reducePow]; omega]  have hcover' : ∀ (d : ℕ), 1 ≤ d → d < 15 → ∀ v : ℤ,      ∃ a < 16 - d, x (v - (a : ℤ)) a = true ∧ x (v - (a : ℤ)) (a + d) = true := by    intro d hd1 hd v    obtain ⟨a, ha, h1, h2⟩ := hcover d hd1 (by simp only [Nat.reducePow]; omega) v    exact ⟨a, by simp only [Nat.reducePow] at ha; omega, h1, h2⟩  have h114 := cycle_power_fifteen_tight_type_sequence_one_iff_fourteen x h0 h15 hparent hcount' hexact' hcover'  refine ⟨cycle_power_dyadic_boundary_pairing_alternates 4 (by norm_num) x hexact ?_, ?_⟩  · intro p    simpa using h114 p  · intro p hp j hj1 hj2    cases hx : x p j with    | false => rfl    | true =>      exfalso      have h14 : x p 14 = false := by rw [← h114 p]; exact hp      have hj3 : j ≠ 1 := fun e => by rw [e, hp] at hx; exact absurd hx (by simp)      have hj4 : j ≠ 14 := fun e => by rw [e, h14] at hx; exact absurd hx (by simp)      have := cycle_power_fifteen_model_no_island x htight hexact hcover hcount p 1 j 14        (by omega) (by simp only [Nat.reducePow] at hj2; omega) (by norm_num) hp hx      rw [h14] at this      exact absurd this (by simp)
See it in the graphDiscuss this resultChallenge it