AFTD Auto-Formalizing Theoretical Domains

digraph_strict54_out_mask_facts

theoremverified

The out-mask graph is loopless, oriented, has no directed triangle, every arc has a common predecessor of its ends, every outdegree is at least seven, and the sum of C(outdegree, 2) is 1162.

Statement

theorem digraph_strict54_out_mask_facts :
    (∀ u : Fin 54, (digraph_strict54_out_mask u.val).testBit u.val = false) ∧
    (∀ u v : Fin 54, (digraph_strict54_out_mask u.val).testBit v.val = true → (digraph_strict54_out_mask v.val).testBit u.val = false) ∧
    (∀ u v : Fin 54, (digraph_strict54_out_mask u.val).testBit v.val = true → ∀ w : Fin 54,
      (digraph_strict54_out_mask v.val).testBit w.val = true → (digraph_strict54_out_mask w.val).testBit u.val = false) ∧
    (∀ u v : Fin 54, (digraph_strict54_out_mask u.val).testBit v.val = true →
      ∃ p : Fin 54, (digraph_strict54_out_mask p.val).testBit u.val = true ∧ (digraph_strict54_out_mask p.val).testBit v.val = true) ∧
    (∀ u : Fin 54, 7 ≤ (Finset.univ.filter fun v : Fin 54 => (digraph_strict54_out_mask u.val).testBit v.val = true).card) ∧
    (∑ v : Fin 54, Nat.choose (Finset.univ.filter fun w : Fin 54 => (digraph_strict54_out_mask v.val).testBit w.val = true).card 2) = 1162
Source
Bitmask certificate for the 54-vertex strictness witness of the weighted center route (IN-522).
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • digraph_strict54_out_maskBit v of the value at u is set exactly when u -> v is an arc of the 54-vertex strictness witness graph.
Used by 1

The proof, explained

The theorem establishes six structural and counting properties of an explicit 54-vertex directed graph defined by 64-bit integer masks: it is loopless, oriented (no 2-cycles), directed-triangle-free, has a common predecessor for every directed arc, has minimum outdegree at least 7, and has $\sum_v \binom{\mathrm{outdeg}(v)}{2} = 1162$. Because the vertex set is finite and all operations are computable, every claim is decidable, and the proof executes by exhaustive kernel computation using `decide +kernel`.

  1. All six structural and numerical properties hold for the 54-vertex directed graph defined by `digraph_strict54_out_mask`. automation

    The theorem consists of a conjunction of decidable propositions over the finite set of 54 vertices (`Fin 54`). Each condition—looplessness, absence of 2-cycles, absence of directed triangles, existence of a common predecessor for each directed edge, the lower bound of 7 on each vertex's outdegree, and the exact sum of 1162 for $\sum_v \binom{\mathrm{outdeg}(v)}{2}$—involves only bounded quantification, bitwise operations on natural numbers, and finite set cardinality/summation. The `decide +kernel` tactic evaluates the decision procedure directly within the Lean kernel to reduce the goal to `True`.

    line 10

      decide +kernel

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 digraph_strict54_out_mask_facts :    (∀ u : Fin 54, (digraph_strict54_out_mask u.val).testBit u.val = false) ∧    (∀ u v : Fin 54, (digraph_strict54_out_mask u.val).testBit v.val = true → (digraph_strict54_out_mask v.val).testBit u.val = false) ∧    (∀ u v : Fin 54, (digraph_strict54_out_mask u.val).testBit v.val = true → ∀ w : Fin 54,      (digraph_strict54_out_mask v.val).testBit w.val = true → (digraph_strict54_out_mask w.val).testBit u.val = false) ∧    (∀ u v : Fin 54, (digraph_strict54_out_mask u.val).testBit v.val = true →      ∃ p : Fin 54, (digraph_strict54_out_mask p.val).testBit u.val = true ∧ (digraph_strict54_out_mask p.val).testBit v.val = true) ∧    (∀ u : Fin 54, 7 ≤ (Finset.univ.filter fun v : Fin 54 => (digraph_strict54_out_mask u.val).testBit v.val = true).card) ∧    (∑ v : Fin 54, Nat.choose (Finset.univ.filter fun w : Fin 54 => (digraph_strict54_out_mask v.val).testBit w.val = true).card 2) = 1162 := by  decide +kernel
See it in the graphDiscuss this resultChallenge it