AFTD Auto-Formalizing Theoretical Domains

digraph_strict54_nonadj_mask_sound

theoremverified

Two distinct vertices whose bit is clear in the nonadjacency mask have a common predecessor.

Statement

theorem digraph_strict54_nonadj_mask_sound :
    ∀ a b : Fin 54, a ≠ b → (digraph_strict54_nonadj_mask a.val).testBit b.val = false →
      ∃ w : Fin 54, (digraph_strict54_out_mask w.val).testBit a.val = true ∧ (digraph_strict54_out_mask w.val).testBit b.val = true
Source
Bitmask certificate for the 54-vertex strictness witness of the weighted center route (IN-522).
Verified
04 Nov 2026
Axioms
Quot.soundpropext
Built on 2
  • 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.
  • digraph_strict54_nonadj_maskBit v of the value at u is set exactly when v differs from u and u, v have no common predecessor in the 54-vertex strictness witness graph.
Used by 1

The proof, explained

The theorem establishes that any two distinct vertices in a 54-vertex directed graph whose nonadjacency mask bit is clear share a common predecessor. Because the vertex set Fin 54 is finite and the mask functions are explicitly defined, the proposition is decidable. The proof proceeds entirely by exhaustive computational verification in the Lean kernel.

  1. For any two distinct vertices a and b in Fin 54, if bit b of the nonadjacency mask of a is false, then there exists a vertex w in Fin 54 that has directed edges to both a and b. automation

    The theorem is a purely finite combinatorial statement: the universal quantifiers over a, b ∈ Fin 54 and the existential quantifier over w ∈ Fin 54 range over a finite set of 54 elements, and the masks `digraph_strict54_nonadj_mask` and `digraph_strict54_out_mask` are explicitly computable integer functions. Consequently, the statement has an instance of `Decidable`, and the `decide +kernel` tactic discharges the goal by exhaustive evaluation directly within the Lean 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_nonadj_mask_sound :    ∀ a b : Fin 54, a ≠ b → (digraph_strict54_nonadj_mask a.val).testBit b.val = false →      ∃ w : Fin 54, (digraph_strict54_out_mask w.val).testBit a.val = true ∧ (digraph_strict54_out_mask w.val).testBit b.val = true := by  decide +kernel
See it in the graphDiscuss this resultChallenge it