magic_square_even_diff_card_two
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
- magic_square_winning_op_sub_det_row0_leFor any valid measurement effects A for Alice and B for Bob in the magic square game (where each A x is a POVM with support on even…
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.
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.
revert hs hk hne s k decide
- The `revert` tactic is a Lean-specific formal detail needed to turn the free variables and hypotheses into a closed, universally quantified goal over the finite type `Fin 3 → Bool`. The decision procedure `decide` then verifies the goal by internal kernel computation over all 64 pairs, without recording individual case proofs.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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