AFTD Auto-Formalizing Theoretical Domains

cycle_power_fifteen_class_weight_certificate

theoremverified

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.

  1. 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$.

    lines 3–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) ≤
          ∑ i : Fin 16, (b i).toNat := by
  2. A boolean conjunction is at most either of its arguments. automation

    Verified by truth-table evaluation (`decide`) over all 4 combinations of booleans.

    lines 7–8

      have hl : ∀ x y : Bool, (x && y).toNat ≤ x.toNat := by decide
      have hr : ∀ x y : Bool, (x && y).toNat ≤ y.toNat := by decide
  3. 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}$.

    lines 9–24

      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)
  4. 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.

    lines 25–27

    uses Fin.sum_univ_succ, Fin.succ_mk, Fin.reduceFinMk

      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)))))))))))))))
  5. The inequality holds by summing the 16 bounds. automation

    Linear integer arithmetic (`omega`) combines the 16 individual inequalities to conclude the overall inequality.

    line 28

      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

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
See it in the graphDiscuss this resultChallenge it