AFTD Auto-Formalizing Theoretical Domains

digraph_strict54_out_mask_pair_count

theoremverified

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

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.

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

    line 4

      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

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