digraph_strict54_out_mask_double_count
In the out-mask graph exactly 15 unordered pairs of vertices have exactly two common predecessors.
Statement
theorem digraph_strict54_out_mask_double_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) ∧ (Finset.univ.filter fun p : Fin 54 => (digraph_strict54_out_mask p.val).testBit x.1.val = true ∧ (digraph_strict54_out_mask p.val).testBit x.2.val = true).card = 2).card = 15
- 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 asserts that in a specific 54-vertex directed graph given by explicit bitmasks, exactly 15 pairs of distinct vertices have exactly two common predecessors. Because the vertex set is finite and edge existence is decidable via bit-testing, the set filtering and counting operations reduce to a finite computation. The entire claim is verified mechanically by kernel evaluation via `decide +kernel`.
The number of pairs of vertices (x₁, x₂) with x₁ < x₂ that have exactly two common predecessors in the directed graph is 15. automation
The vertices range over the finite domain `Fin 54`, and directed edges are determined by the bit values of the explicitly defined bitmasks `digraph_strict54_out_mask`. Consequently, membership in the filtered finsets, the existential quantifier, and the set cardinalities are decidable by finite enumeration. The `decide +kernel` tactic verifies the identity by direct finite computation inside Lean's trusted kernel.
decide +kernel
- The proof contains no manual deductive steps; it relies entirely on computational reflection (`decide +kernel`), where the Lean kernel evaluates the boolean decision procedure for this finite counting problem to `true`.
- The existential clause `∃ w, ...` asserting the existence of at least one common predecessor is mathematically redundant given the subsequent cardinality condition that the number of such predecessors is exactly 2, but it is evaluated as part of the filter condition.
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_double_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) ∧ (Finset.univ.filter fun p : Fin 54 => (digraph_strict54_out_mask p.val).testBit x.1.val = true ∧ (digraph_strict54_out_mask p.val).testBit x.2.val = true).card = 2).card = 15 := by decide +kernel