digraph_strict54_out_mask_facts
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
- digraph_weighted_center_strict54_certificateThe displayed 54-vertex graph is loopless, oriented, triangle-free and arc-dominated, has minimum outdegree seven and auxiliary…
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`.
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`.
decide +kernel
- The entire proof relies on computational reflection (`decide +kernel`). Lean evaluates all finite quantifiers over `Fin 54`, the bit-testing operations, and the arithmetic summation directly in the trusted kernel without generating intermediate manual deduction steps.
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 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