AFTD Auto-Formalizing Theoretical Domains

digraph_strict54_adj_iff_out_mask

theoremverified

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
Used by 1

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.

  1. 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.

    lines 2–4

      intro u v
      unfold digraph_weighted_center_strict54_graph
      infer_instance
  2. 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.

    line 8

      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

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
See it in the graphDiscuss this resultChallenge it