AFTD Auto-Formalizing Theoretical Domains

digraph_strict54_out_mask_double_count

theoremverified

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

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

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

    line 6

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