AFTD Auto-Formalizing Theoretical Domains

cycle_power_fifteen_tight_class_ancestors

theoremverified

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

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.

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

    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. 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`.

    lines 23–24

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

    lines 25–40

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

    lines 41–43

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

      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
  5. 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`.

    lines 44–45

      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
  6. 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.

    line 46

      refine ⟨hroot (b 0) (b 15) (by omega) (by omega), ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_ , ?_⟩
  7. 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}$.

    lines 47–53

      · 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)
  8. 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}$.

    lines 54–74

    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`.

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