cycle_power_fifteen_class_weight_certificate
For a subset of the sixteen positions of an arc, the weighted number of pairs at distances 8, 12, 14, 15, with weights 1, 1, 1, 2, is at most its cardinality.
Statement
theorem cycle_power_fifteen_class_weight_certificate(b : Fin 16 → Bool) : 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
- 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
The proof, explained
The proof decomposes the weighted sum of 16 pairs into 16 individual boolean conjunctions (with distance 15 counted twice). Each conjunction x ∧ y is bounded above by either x or y such that each position in {0, ..., 15} appears as an upper bound exactly once. Summing these 16 inequalities gives the desired bound.
The indices in the summands of the theorem statement are valid elements of Fin 16.
The inline `by omega` proofs verify that $i < 16$ and $i + 14 < 16$ for $i < 2$, $i + 12 < 16$ for $i < 4$, and $i + 8 < 16$ for $i < 8$.
(∑ 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 := by
A boolean conjunction is at most either of its arguments. automation
Verified by truth-table evaluation (`decide`) over all 4 combinations of booleans.
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 terms on the left-hand side is bounded by a distinct b i.
For each of the 16 terms in the weighted sum (counting the term for distance 15 twice), we apply either `hl` or `hr` to bound it by a unique variable $b_0, \dots, b_{15}$.
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 sums over Fin 2, Fin 4, Fin 8, and Fin 16 are unrolled into explicit additions.
Unfolding the summations using `Fin.sum_univ_succ` and evaluating indices expands the sum into an explicit inequality between two sums of 16 terms.
uses
Fin.sum_univ_succ,Fin.succ_mk,Fin.reduceFinMknorm_num [Fin.sum_univ_succ, Fin.succ_mk, Fin.reduceFinMk] 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)))))))))))))))
The inequality holds by summing the 16 bounds. automation
Linear integer arithmetic (`omega`) combines the 16 individual inequalities to conclude the overall inequality.
omega
Fin.sum_univ_succ- Splits a sum over Fin (n + 1) into the term at 0 and the sum of the remaining terms.
Fin.succ_mk- The successor of ⟨i, h⟩ in Fin (n + 1) is ⟨i + 1, _⟩.
Fin.reduceFinMk- A simplification procedure that reduces Fin literals.
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_class_weight_certificate(b : Fin 16 → Bool) : 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 := 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] 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))))))))))))))) omega