digraph_strict54_out_mask_pair_count
In the out-mask graph exactly 1144 unordered pairs of vertices have a common predecessor.
Statement
theorem digraph_strict54_out_mask_pair_count : ((Finset.univ : Finset (Fin 54 × Fin 54)).filter fun x => x.1 < x.2 ∧ (∃ w : Fin 54, (digraph_strict54_out_mask w.val).testBit x.1.val = true ∧ (digraph_strict54_out_mask w.val).testBit x.2.val = true)).card = 1144
- 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 states that in a specific 54-vertex directed graph encoded by bitmasks, exactly 1144 unordered pairs of vertices share a common predecessor. Because the vertex set is finite and edge existence is given by computable bitwise operations, the set of such pairs and its cardinality are directly computable. The proof delegates the entire verification to Lean's kernel via `decide +kernel`, which computes the cardinality by exhaustive evaluation.
The number of pairs of vertices (x₁, x₂) with x₁ < x₂ sharing a common predecessor in the 54-vertex directed graph is exactly 1144. automation
The set of pairs is obtained by filtering the finite universe of pairs in Fin 54 × Fin 54 according to x₁ < x₂ and the existential condition that some vertex w has both its x₁-th and x₂-th outgoing edge bits set. Because Fin 54 is finite and bit testing is computable, this is a decidable proposition; the tactic `decide +kernel` evaluates the full search and cardinality computation by reflection inside the kernel.
decide +kernel
- The entire proof consists of an exhaustive finite computation performed by the Lean kernel, evaluating the existence of a common predecessor across all candidate pairs against all 54 possible vertices.
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_pair_count : ((Finset.univ : Finset (Fin 54 × Fin 54)).filter fun x => x.1 < x.2 ∧ (∃ w : Fin 54, (digraph_strict54_out_mask w.val).testBit x.1.val = true ∧ (digraph_strict54_out_mask w.val).testBit x.2.val = true)).card = 1144 := by decide +kernel