cycle_power_fifteen_tight_class_ancestors
Equality in the sixteen-position weighted-pair bound forces equal endpoint bits and closure under the fourteen parent edges of its rooted forest.
Statement
theorem cycle_power_fifteen_tight_class_ancestors(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) : b 0 = b 15 ∧ (b 1 = true → b 15 = true) ∧ (b 2 = true → b 14 = true) ∧ (b 3 = true → b 15 = true) ∧ (b 4 = true → b 12 = true) ∧ (b 5 = true → b 13 = true) ∧ (b 6 = true → b 14 = true) ∧ (b 7 = true → b 15 = true) ∧ (b 8 = true → b 0 = true) ∧ (b 9 = true → b 1 = true) ∧ (b 10 = true → b 2 = true) ∧ (b 11 = true → b 3 = true) ∧ (b 12 = true → b 0 = true) ∧ (b 13 = true → b 1 = true) ∧ (b 14 = true → b 0 = 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- Used by 1
- cycle_power_fifteen_tight_class_spanningEvery nonempty subset attaining equality in the sixteen-position weighted-pair bound contains both positions 0 and 15.
The proof, explained
The left-hand side of the hypothesis is a sum of 16 boolean conjunctions (counting $b_0 \land b_{15}$ twice), each bounded above by a distinct bit $b_k$ for $k \in \{0, \dots, 15\}$, so their sum cannot exceed $\sum_{k=0}^{15} b_k$. Because the hypothesis asserts equality between this sum and $\sum_{k=0}^{15} b_k$, every single upper-bound inequality must hold with equality. The double equality $(b_0 \land b_{15}) = b_0$ and $(b_0 \land b_{15}) = b_{15}$ forces the endpoint bits to coincide ($b_0 = b_{15}$). For each remaining pair, the tight bound $(b_i \land b_j) = b_i$ forces the implication $b_i = \text{true} \to b_j = \text{true}$ along the corresponding parent edge in the forest.
The offset indices in the theorem statement satisfy the bounds required to define elements of $\text{Fin } 16$.
Linear integer arithmetic (`omega`) verifies that $i < 16$ and $i + 14 < 16$ for $i < 2$, that $i + 12 < 16$ for $i < 4$, and that $i + 8 < 16$ for $i < 8$, ensuring that each indexing term in the sums is a well-formed element of $\text{Fin } 16$.
(∑ 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) =
For any two boolean values $x$ and $y$, $(x \land y) \le x$ and $(x \land y) \le y$ (when booleans are interpreted as 0 or 1 in $\mathbb{N}$).
Both bounds (`hl` and `hr`) are established by exhaustive case analysis over the four possible truth values of $x$ and $y$, checked by `decide`.
have hl : ∀ x y : Bool, (x && y).toNat ≤ x.toNat := by decide have hr : ∀ x y : Bool, (x && y).toNat ≤ y.toNat := by decide
Each of the 16 conjunction terms on the left-hand side is bounded by a distinct bit $b_k$ for $k \in \{0, \dots, 15\}$.
The proof instantiates `hl` or `hr` on each of the 16 pairs $(b_i, b_j)$ appearing in the sums. The weight-two term $(b_0 \land b_{15})$ is bounded once by $b_0$ (via `hl`, labeled $h_0$) and once by $b_{15}$ (via `hr`, labeled $h_{15}$). Each of the remaining 14 conjunctions is bounded by its appropriate bit ($h_1$ through $h_{14}$) so that every index $k \in \{0, \dots, 15\}$ serves as the upper bound for exactly one term.
have h0 := hl (b 0) (b 15) have h15 := hr (b 0) (b 15) have h14 := hr (b 0) (b 14) have h1 := hl (b 1) (b 15) have h12 := hr (b 0) (b 12) have h13 := hr (b 1) (b 13) have h2 := hl (b 2) (b 14) have h3 := hl (b 3) (b 15) have h8 := hr (b 0) (b 8) have h9 := hr (b 1) (b 9) have h10 := hr (b 2) (b 10) have h11 := hr (b 3) (b 11) have h4 := hl (b 4) (b 12) have h5 := hl (b 5) (b 13) have h6 := hl (b 6) (b 14) have h7 := hl (b 7) (b 15)
The hypothesis `hw` is expanded into an explicit sum of 16 conjunctions on the left and the sum of all 16 bits on the right.
`norm_num` unrolls the finite sums over `Fin 2`, `Fin 4`, `Fin 8`, and `Fin 16` using `Fin.sum_univ_succ`, `Fin.succ_mk`, and `Fin.reduceFinMk`. The `change` tactic then restructures the equation into an explicit addition of the 16 conjunction terms on the left equated to the sum $b_0 + \dots + b_{15}$ on the right.
uses
Fin.sum_univ_succ,Fin.succ_mk,Fin.reduceFinMknorm_num [Fin.sum_univ_succ, Fin.succ_mk, Fin.reduceFinMk] at hw change 2 * (b 0 && b 15).toNat + ((b 0 && b 14).toNat + ((b 1 && b 15).toNat)) + ((b 0 && b 12).toNat + ((b 1 && b 13).toNat + ((b 2 && b 14).toNat + ((b 3 && b 15).toNat)))) + ((b 0 && b 8).toNat + ((b 1 && b 9).toNat + ((b 2 && b 10).toNat + ((b 3 && b 11).toNat + ((b 4 && b 12).toNat + ((b 5 && b 13).toNat + ((b 6 && b 14).toNat + ((b 7 && b 15).toNat)))))))) = (b 0).toNat + ((b 1).toNat + ((b 2).toNat + ((b 3).toNat + ((b 4).toNat + ((b 5).toNat + ((b 6).toNat + ((b 7).toNat + ((b 8).toNat + ((b 9).toNat + ((b 10).toNat + ((b 11).toNat + ((b 12).toNat + ((b 13).toNat + ((b 14).toNat + ((b 15).toNat))))))))))))))) at hw
For booleans $x$ and $y$, the condition $(x \land y) = x$ implies $x = \text{true} \to y = \text{true}$, and the simultaneous conditions $(x \land y) = x$ and $(x \land y) = y$ imply $x = y$.
These two characterizations of tight boolean bounds (`he` and `hroot`) are verified by exhaustive case analysis over the truth values using `decide`.
have he : ∀ x y : Bool, (x && y).toNat = x.toNat → (x = true → y = true) := by decide have hroot : ∀ x y : Bool, (x && y).toNat = x.toNat → (x && y).toNat = y.toNat → x = y := by decide
The endpoint bits are equal: $b_0 = b_{15}$.
Since the sum of the 16 terms equals the sum of their individual upper bounds $b_0, \dots, b_{15}$, no term can be strictly less than its bound without violating the equality in `hw`. The arithmetic solver `omega` deduces that $(b_0 \land b_{15}) = b_0$ and $(b_0 \land b_{15}) = b_{15}$. Applying `hroot` to these two equalities proves $b_0 = b_{15}$, and `refine` sets up the remaining 14 implications as subgoals.
refine ⟨hroot (b 0) (b 15) (by omega) (by omega), ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_⟩
The parent implications $b_k = \text{true} \to b_{\text{parent}(k)} = \text{true}$ hold for child nodes $k \in \{1, 2, 3, 4, 5, 6, 7\}$.
For each child node $k \in \{1, \dots, 7\}$, the conjunction $(b_k \land b_m)$ was bounded above by $b_k$. By tightness of the total sum, `omega` deduces that $(b_k \land b_m) = b_k$. Applying `he` directly yields $b_k = \text{true} \to b_m = \text{true}$.
· exact he (b 1) (b 15) (by omega) · exact he (b 2) (b 14) (by omega) · exact he (b 3) (b 15) (by omega) · exact he (b 4) (b 12) (by omega) · exact he (b 5) (b 13) (by omega) · exact he (b 6) (b 14) (by omega) · exact he (b 7) (b 15) (by omega)
The parent implications $b_k = \text{true} \to b_{\text{parent}(k)} = \text{true}$ hold for child nodes $k \in \{8, 9, 10, 11, 12, 13, 14\}$.
For each node $k \in \{8, \dots, 14\}$, the term in the sum appeared as $(b_m \land b_k) \le b_k$. The proof rewrites the conjunction using commutativity (`Bool.and_comm`) to obtain $(b_k \land b_m)$, which `omega` shows must equal $b_k$ by tightness. Applying `he` then completes the implication $b_k = \text{true} \to b_m = \text{true}$.
uses
Bool.and_comm· apply he (b 8) (b 0) rw [Bool.and_comm] omega · apply he (b 9) (b 1) rw [Bool.and_comm] omega · apply he (b 10) (b 2) rw [Bool.and_comm] omega · apply he (b 11) (b 3) rw [Bool.and_comm] omega · apply he (b 12) (b 0) rw [Bool.and_comm] omega · apply he (b 13) (b 1) rw [Bool.and_comm] omega · apply he (b 14) (b 0) rw [Bool.and_comm] omega
Fin.sum_univ_succ- Splits a sum over `Fin (n + 1)` into the term at index 0 plus the sum over the remaining successors.
Fin.succ_mk- The successor of an element `⟨i, h⟩` in `Fin n` is represented by `⟨i + 1, _⟩`.
Fin.reduceFinMk- A simplifier procedure that evaluates and reduces numeric literals enclosed in `Fin.mk`.
Bool.and_comm- Boolean conjunction is commutative: `x && y = y && x`.
- The theorem statement includes inline tactic proofs (`by omega` on lines 4–6) ensuring the offset indices are strictly less than 16.
- The Presburger arithmetic tactic `omega` is used to deduce that when a sum of quantities $\sum x_i$ equals $\sum y_i$ with each $x_i \le y_i$, every individual equality $x_i = y_i$ must hold. This tightness deduction occurs automatically without manually rearranging or subtracting terms.
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_ancestors(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) : b 0 = b 15 ∧ (b 1 = true → b 15 = true) ∧ (b 2 = true → b 14 = true) ∧ (b 3 = true → b 15 = true) ∧ (b 4 = true → b 12 = true) ∧ (b 5 = true → b 13 = true) ∧ (b 6 = true → b 14 = true) ∧ (b 7 = true → b 15 = true) ∧ (b 8 = true → b 0 = true) ∧ (b 9 = true → b 1 = true) ∧ (b 10 = true → b 2 = true) ∧ (b 11 = true → b 3 = true) ∧ (b 12 = true → b 0 = true) ∧ (b 13 = true → b 1 = true) ∧ (b 14 = true → b 0 = true) := by have hl : ∀ x y : Bool, (x && y).toNat ≤ x.toNat := by decide have hr : ∀ x y : Bool, (x && y).toNat ≤ y.toNat := by decide have h0 := hl (b 0) (b 15) have h15 := hr (b 0) (b 15) have h14 := hr (b 0) (b 14) have h1 := hl (b 1) (b 15) have h12 := hr (b 0) (b 12) have h13 := hr (b 1) (b 13) have h2 := hl (b 2) (b 14) have h3 := hl (b 3) (b 15) have h8 := hr (b 0) (b 8) have h9 := hr (b 1) (b 9) have h10 := hr (b 2) (b 10) have h11 := hr (b 3) (b 11) have h4 := hl (b 4) (b 12) have h5 := hl (b 5) (b 13) have h6 := hl (b 6) (b 14) have h7 := hl (b 7) (b 15) norm_num [Fin.sum_univ_succ, Fin.succ_mk, Fin.reduceFinMk] at hw change 2 * (b 0 && b 15).toNat + ((b 0 && b 14).toNat + ((b 1 && b 15).toNat)) + ((b 0 && b 12).toNat + ((b 1 && b 13).toNat + ((b 2 && b 14).toNat + ((b 3 && b 15).toNat)))) + ((b 0 && b 8).toNat + ((b 1 && b 9).toNat + ((b 2 && b 10).toNat + ((b 3 && b 11).toNat + ((b 4 && b 12).toNat + ((b 5 && b 13).toNat + ((b 6 && b 14).toNat + ((b 7 && b 15).toNat)))))))) = (b 0).toNat + ((b 1).toNat + ((b 2).toNat + ((b 3).toNat + ((b 4).toNat + ((b 5).toNat + ((b 6).toNat + ((b 7).toNat + ((b 8).toNat + ((b 9).toNat + ((b 10).toNat + ((b 11).toNat + ((b 12).toNat + ((b 13).toNat + ((b 14).toNat + ((b 15).toNat))))))))))))))) at hw have he : ∀ x y : Bool, (x && y).toNat = x.toNat → (x = true → y = true) := by decide have hroot : ∀ x y : Bool, (x && y).toNat = x.toNat → (x && y).toNat = y.toNat → x = y := by decide refine ⟨hroot (b 0) (b 15) (by omega) (by omega), ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_⟩ · exact he (b 1) (b 15) (by omega) · exact he (b 2) (b 14) (by omega) · exact he (b 3) (b 15) (by omega) · exact he (b 4) (b 12) (by omega) · exact he (b 5) (b 13) (by omega) · exact he (b 6) (b 14) (by omega) · exact he (b 7) (b 15) (by omega) · apply he (b 8) (b 0) rw [Bool.and_comm] omega · apply he (b 9) (b 1) rw [Bool.and_comm] omega · apply he (b 10) (b 2) rw [Bool.and_comm] omega · apply he (b 11) (b 3) rw [Bool.and_comm] omega · apply he (b 12) (b 0) rw [Bool.and_comm] omega · apply he (b 13) (b 1) rw [Bool.and_comm] omega · apply he (b 14) (b 0) rw [Bool.and_comm] omega