AFTD Auto-Formalizing Theoretical Domains

digraph_strict54_nonadj_mask_four

theoremverified

Three pairwise nonadjacent vertices of the nonadjacency masks have no common nonneighbour.

Statement

theorem digraph_strict54_nonadj_mask_four :
    ∀ a b c : Fin 54, (digraph_strict54_nonadj_mask a.val).testBit b.val = true →
      (digraph_strict54_nonadj_mask a.val).testBit c.val = true → (digraph_strict54_nonadj_mask b.val).testBit c.val = true →
      (digraph_strict54_nonadj_mask a.val &&& digraph_strict54_nonadj_mask b.val &&& digraph_strict54_nonadj_mask c.val) = 0
Source
Bitmask certificate for the 54-vertex strictness witness of the weighted center route (IN-522).
Verified
04 Nov 2026
Axioms
propext
Built on 1
  • 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 asserts that in a 54-vertex graph represented by nonadjacency bitmasks, any three pairwise nonadjacent vertices share no common nonneighbour, meaning the graph has no independent set of size four. Because the quantification is over the finite domain Fin 54 and all bitwise operations are computable, the proposition is decidable. The proof proceeds by exhaustive computation checked directly by the Lean kernel.

  1. For every triple of vertices a, b, c ∈ Fin 54, if they are pairwise nonadjacent, their nonadjacency masks share no common bits (their bitwise AND is 0). automation

    Because Fin 54 is finite (leaving 54³ = 157,464 triples to consider) and all operations—evaluating the nonadjacency mask, testing bits, and bitwise conjunction—are primitive arithmetic and boolean computations, the goal is a decidable proposition. The `decide +kernel` tactic evaluates the entire exhaustive check directly inside the Lean kernel via computational reflection.

    line 5

      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_four :    ∀ a b c : Fin 54, (digraph_strict54_nonadj_mask a.val).testBit b.val = true →      (digraph_strict54_nonadj_mask a.val).testBit c.val = true → (digraph_strict54_nonadj_mask b.val).testBit c.val = true →      (digraph_strict54_nonadj_mask a.val &&& digraph_strict54_nonadj_mask b.val &&& digraph_strict54_nonadj_mask c.val) = 0 := by  decide +kernel
See it in the graphDiscuss this resultChallenge it