cycle_power_fifteen_tight_class_spanning
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
- cycle_power_fifteen_tight_class_ancestorsEquality in the sixteen-position weighted-pair bound forces equal endpoint bits and closure under the fourteen parent edges of its rooted…
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.
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.
(∑ 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) =
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.
uses
cycle_power_fifteen_tight_class_ancestorsobtain ⟨hroot, h1, h2, h3, h4, h5, h6, h7, h8, h9, h10, h11, h12, h13, h14⟩ := cycle_power_fifteen_tight_class_ancestors b hwPosition 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.
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)
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.
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.
- The theorem statement itself contains embedded proofs (via `omega`) verifying that shifted index bounds do not exceed 15.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩