AFTD Auto-Formalizing Theoretical Domains

cycle_power_fifteen_tight_class_spanning

theoremverified

Every nonempty subset attaining equality in the sixteen-position weighted-pair bound contains both positions 0 and 15.

Statement

theorem cycle_power_fifteen_tight_class_spanning(b : Fin 16 → Bool)
    (hw :
    2 * (b 0 && b 15).toNat +
      (∑ i : Fin 2, (b ⟨i.val, by omega⟩ && b ⟨i.val + 14, by omega⟩).toNat) +
      (∑ i : Fin 4, (b ⟨i.val, by omega⟩ && b ⟨i.val + 12, by omega⟩).toNat) +
      (∑ i : Fin 8, (b ⟨i.val, by omega⟩ && b ⟨i.val + 8, by omega⟩).toNat) =
      ∑ i : Fin 16, (b i).toNat) (i : Fin 16) (hi : b i = true) :
    b 0 = true ∧ b 15 = true
Source
Counting step for the k = 15 case of OP-205, arXiv:2610.15635. Experiment 3978 identifies the weights; the proof assigns one weighted edge to each vertex in a rooted forest.
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The theorem shows that any nonempty subset of positions satisfying equality in the 16-position weighted-pair bound must include both positions 0 and 15. Using an ancestor lemma that organizes the tight configuration into implication chains converging to 0 and 15 along with the equality b 0 = b 15, the proof exhausts all 16 possibilities for the assumed element to establish that position 0 is active, which then immediately forces position 15 to be active as well.

  1. The shifted indices used in the weighted sums lie strictly below 16.

    In the theorem formulation, the summations over pairs require bounding the indices: when i < 2, i + 14 < 16; when i < 4, i + 12 < 16; and when i < 8, i + 8 < 16. These index bounds are verified by linear integer arithmetic.

    lines 4–6

          (∑ i : Fin 2, (b ⟨i.val, by omega⟩ && b ⟨i.val + 14, by omega⟩).toNat) +
          (∑ i : Fin 4, (b ⟨i.val, by omega⟩ && b ⟨i.val + 12, by omega⟩).toNat) +
          (∑ i : Fin 8, (b ⟨i.val, by omega⟩ && b ⟨i.val + 8, by omega⟩).toNat) =
  2. Under the equality condition, position 0 matches position 15, and each position implies an ancestor position.

    We apply cycle_power_fifteen_tight_class_ancestors to the tightness assumption hw to extract the equality b 0 = b 15 and fourteen implications, one for each intermediate index k, showing that if b k is true, then another designated position is true.

    line 9

    uses cycle_power_fifteen_tight_class_ancestors

      obtain ⟨hroot, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11, h12, h13, h14⟩ := cycle_power_fifteen_tight_class_ancestors b hw
  3. Position 0 is true.

    We perform a case analysis on the given witness index i from 0 to 15. In every case, following the chain of implications provided by the ancestors lemma and using the equality b 0 = b 15 when reaching position 15, we deduce that b 0 must be true.

    lines 10–27

      have htop : b 0 = true := by
        fin_cases i
        · exact hi
        · exact hroot.symm ▸ (h1 (hi))
        · exact h14 (h2 (hi))
        · exact hroot.symm ▸ (h3 (hi))
        · exact h12 (h4 (hi))
        · exact hroot.symm ▸ (h1 (h13 (h5 (hi))))
        · exact h14 (h6 (hi))
        · exact hroot.symm ▸ (h7 (hi))
        · exact h8 (hi)
        · exact hroot.symm ▸ (h1 (h9 (hi)))
        · exact h14 (h2 (h10 (hi)))
        · exact hroot.symm ▸ (h3 (h11 (hi)))
        · exact h12 (hi)
        · exact hroot.symm ▸ (h1 (h13 (hi)))
        · exact h14 (hi)
        · exact hroot.symm ▸ (hi)
  4. Both position 0 and position 15 are true.

    We combine the fact that b 0 is true with the equality b 0 = b 15 to conclude that both b 0 and b 15 are true.

    line 28

      exact ⟨htop, hroot ▸ htop⟩
cycle_power_fifteen_tight_class_ancestors
For any boolean configuration attaining equality in the weighted-pair bound on 16 positions, position 0 equals position 15, and every other active position implies an active ancestor position.

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_tight_class_spanning(b : Fin 16 → Bool)    (hw :    2 * (b 0 && b 15).toNat +      (∑ i : Fin 2, (b ⟨i.val, by omega⟩ && b ⟨i.val + 14, by omega⟩).toNat) +      (∑ i : Fin 4, (b ⟨i.val, by omega⟩ && b ⟨i.val + 12, by omega⟩).toNat) +      (∑ i : Fin 8, (b ⟨i.val, by omega⟩ && b ⟨i.val + 8, by omega⟩).toNat) =      ∑ i : Fin 16, (b i).toNat) (i : Fin 16) (hi : b i = true) :    b 0 = true ∧ b 15 = true := by  obtain ⟨hroot, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11, h12, h13, h14⟩ := cycle_power_fifteen_tight_class_ancestors b hw  have htop : b 0 = true := by    fin_cases i    · exact hi    · exact hroot.symm ▸ (h1 (hi))    · exact h14 (h2 (hi))    · exact hroot.symm ▸ (h3 (hi))    · exact h12 (h4 (hi))    · exact hroot.symm ▸ (h1 (h13 (h5 (hi))))    · exact h14 (h6 (hi))    · exact hroot.symm ▸ (h7 (hi))    · exact h8 (hi)    · exact hroot.symm ▸ (h1 (h9 (hi)))    · exact h14 (h2 (h10 (hi)))    · exact hroot.symm ▸ (h3 (h11 (hi)))    · exact h12 (hi)    · exact hroot.symm ▸ (h1 (h13 (hi)))    · exact h14 (hi)    · exact hroot.symm ▸ (hi)  exact ⟨htop, hroot ▸ htop⟩
See it in the graphDiscuss this resultChallenge it