digraph_strict54_adj_iff_out_mask
The out-mask table describes the arcs of the 54-vertex strictness witness exactly.
Statement
theorem digraph_strict54_adj_iff_out_mask :
∀ u v : Fin 54, digraph_weighted_center_strict54_graph.Adj u v ↔ (digraph_strict54_out_mask u.val).testBit v.val = true- 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 2
- digraph_weighted_center_strict54_graphThe cyclic 53-vertex digraph with steps 1, 8, 14, 16, 28, 32, 33, extended by a new vertex with in-neighbors 0, 1, 17, 25 and…
- 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 equivalence between the adjacency relation of the 54-vertex graph and its bitmask representation is proved by computational exhaustion. First, decidability of the adjacency relation is established by unfolding its definition into elementary arithmetic and finite set membership checks. Then, the kernel evaluates both sides of the equivalence across all 54 × 54 = 2916 vertex pairs, confirming that the bitmask correctly encodes the edges in every case.
The adjacency relation of `digraph_weighted_center_strict54_graph` is decidable.
Given vertices u and v, unfolding the definition of the graph expands adjacency into a finite boolean combination of integer inequalities, modular arithmetic conditions, and memberships in explicit finite sets. Typeclass inference (`infer_instance`) combines the standard decision procedures for these components into a decision procedure for adjacency.
intro u v unfold digraph_weighted_center_strict54_graph infer_instance
For every pair of vertices u and v in Fin 54, u is adjacent to v if and only if bit v of the out-mask of u is 1. automation
Because Fin 54 is a finite type, the universally quantified statement over all pairs u, v ranges over exactly 54 × 54 = 2916 cases. Both the adjacency relation and the bitmask computation are decidable, so `decide +kernel` evaluates the equivalence for each pair directly inside the Lean kernel to close the goal.
decide +kernel
- The entire verification of the equivalence is performed by kernel evaluation (`decide +kernel`), which exhaustively evaluates all 54 × 54 = 2916 pairs of vertices by computational reduction rather than symbolic proof.
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.
private instance in522_strict54_adj : DecidableRel digraph_weighted_center_strict54_graph.Adj := by intro u v unfold digraph_weighted_center_strict54_graph infer_instancetheorem digraph_strict54_adj_iff_out_mask : ∀ u v : Fin 54, digraph_weighted_center_strict54_graph.Adj u v ↔ (digraph_strict54_out_mask u.val).testBit v.val = true := by decide +kernel