AFTD Auto-Formalizing Theoretical Domains

magic_square_even_diff_card_two

theoremverified

Two distinct 3-bit sign strings of even parity differ in exactly two coordinates.

Statement

theorem magic_square_even_diff_card_two (s k : Fin 3 → Bool)
    (hs : (s 0 ^^ s 1 ^^ s 2) = false) (hk : (k 0 ^^ k 1 ^^ k 2) = false) (hne : s ≠ k) :
    (Finset.univ.filter (fun j : Fin 3 => s j ≠ k j)).card = 2
Source
step towards magic_square_score_le_threshold_add_guess
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The theorem is proved by finite case exhaustion. A 3-bit string has only $2^3 = 8$ possible values, exactly 4 of which have even parity (000, 011, 101, and 110). After generalizing all variables and assumptions into the goal, Lean's `decide` tactic exhaustively evaluates all pairs of bitstrings by computation to verify that any two distinct strings of even parity differ in exactly two positions.

  1. Two distinct 3-bit strings of even parity differ in exactly two coordinates. automation

    The bitstrings $s, k$ and the hypotheses $hs, hk, hne$ are generalized back into the goal as universal quantifiers. Because the space of 3-bit strings $\text{Fin } 3 \to \text{Bool}$ has cardinality $2^3 = 8$, the universally quantified statement is a decidable proposition over $8 \times 8 = 64$ pairs of strings. The `decide` tactic checks every pair by exhaustive boolean computation, verifying that whenever two strings are distinct and both have parity false (an even number of ones), the number of coordinates where they differ is exactly 2.

    lines 5–6

      revert hs hk hne s k
      decide

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

/-- Two distinct 3-bit sign strings of even parity differ in exactly two coordinates. -/theorem magic_square_even_diff_card_two (s k : Fin 3 → Bool)    (hs : (s 0 ^^ s 1 ^^ s 2) = false) (hk : (k 0 ^^ k 1 ^^ k 2) = false) (hne : s ≠ k) :    (Finset.univ.filter (fun j : Fin 3 => s j ≠ k j)).card = 2 := by  revert hs hk hne s k  decide
See it in the graphDiscuss this resultChallenge it