op_1592_zmod2_queens_card_le_one
On any d-dimensional modular board (Z/2Z)^d, any set of mutually non-attacking queens has cardinality at most 1.
Statement
theorem op_1592_zmod2_queens_card_le_one {d : ℕ} (s : Finset (Fin d → ZMod 2))
(hs : is_non_attacking_queens s) : s.card ≤ 1- Formalizes
- arXiv:2611.14754 Sec. 1
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_non_attacking_queensA finite set of queens in (Z/nZ)^d is mutually non-attacking if no two distinct queens in the set attack each other.
- modular_queens_attackTwo queens at positions x and y in (Z/nZ)^d attack each other if their difference x - y is a nonzero scalar multiple of a nonzero vector…
Read back from the Lean
For any natural number $d$, if $s$ is a finite set of points in $(\mathbb{Z}/2\mathbb{Z})^d$ (represented as functions Fin d → ZMod 2) such that no two distinct elements of $s$ modularly attack each other (that is, $s$ satisfies is_non_attacking_queens), then the cardinality of $s$ is at most 1.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that any set of non-attacking queens on $(\mathbb{Z}/2\mathbb{Z})^d$ has size at most 1, the proof establishes that every pair of distinct points on the board attacks each other. For any $x \ne y$, their difference $x - y$ has coordinates in $\{0, 1\}$ with at least one non-zero coordinate. Choosing scaling factor $c = 1$ and direction signs matching $x_i - y_i$, this difference satisfies the modular queen attack condition. Consequently, no two distinct queens can coexist in a non-attacking configuration.
Casting the sign representation of any element $a \in \mathbb{Z}/2\mathbb{Z}$ back into $\mathbb{Z}/2\mathbb{Z}$ recovers $a$. automation
By definition, `op_1592_zmod2_queens_card_le_one_to_sign` sends $0$ to `SignType.zero` and $1$ to `SignType.pos`. Their casts back to $\mathbb{Z}/2\mathbb{Z}$ evaluate to $0$ and $1$ respectively, which the `decide` tactic checks exhaustively for the two elements of $\mathbb{Z}/2\mathbb{Z}$.
revert a; decideThe sign representation of $a \in \mathbb{Z}/2\mathbb{Z}$ equals zero if and only if $a = 0$. automation
By definition, non-zero elements are mapped to `SignType.pos` while $0$ is mapped to `SignType.zero`. The `decide` tactic verifies this equivalence by exhaustive evaluation on $\mathbb{Z}/2\mathbb{Z}$.
revert a; decideTo show distinct points $x \ne y$ attack each other, it suffices to exhibit a non-zero direction vector and verify the attack equation with scalar $c = 1$.
Unfolding `modular_queens_attack`, an attack requires a non-zero scalar $c$ and a non-zero vector $v \in \{-1, 0, 1\}^d$ such that $x_i - y_i = c \cdot \operatorname{cast}(v_i)$ for all coordinates $i$. We choose $c = 1$ (which is non-zero in $\mathbb{Z}/2\mathbb{Z}$, verified by `decide`) and set the direction vector to be $v_i = \text{op\_1592\_zmod2\_queens\_card\_le\_one\_to\_sign}(x_i - y_i)$.
unfold modular_queens_attack use 1 use fun i => op_1592_zmod2_queens_card_le_one_to_sign (x i - y i) refine ⟨by decide, ?_, ?_⟩
The direction vector $v$ is non-zero because $x \ne y$.
Suppose for contradiction that $v = 0$. Evaluating at each coordinate $i$ via `congr_fun`, the sign of $x_i - y_i$ is zero. By `op_1592_zmod2_queens_card_le_one_to_sign_eq_zero_iff`, this means $x_i - y_i = 0$, which by `sub_eq_zero` implies $x_i = y_i$. By function extensionality this yields $x = y$, contradicting the hypothesis $h : x \ne y$.
uses
congr_fun,op_1592_zmod2_queens_card_le_one_to_sign_eq_zero_iff,sub_eq_zero· intro hv apply h ext i have hi : op_1592_zmod2_queens_card_le_one_to_sign (x i - y i) = 0 := congr_fun hv i rw [op_1592_zmod2_queens_card_le_one_to_sign_eq_zero_iff, sub_eq_zero] at hi exact hi
The attack equation $x_i - y_i = c \cdot \operatorname{cast}(v_i)$ holds at every coordinate.
For each coordinate $i$, `op_1592_zmod2_queens_card_le_one_to_sign_cast` rewrites $\operatorname{cast}(v_i)$ to $x_i - y_i$. Since $c = 1$, the scalar multiplication $1 \cdot (x_i - y_i)$ simplifies to $x_i - y_i$ by `one_mul`. This finishes showing that $x$ and $y$ attack each other.
uses
op_1592_zmod2_queens_card_le_one_to_sign_cast,one_mul· intro i rw [op_1592_zmod2_queens_card_le_one_to_sign_cast, one_mul]
To show $|s| \le 1$, it suffices to assume there are two distinct queens in $s$ and derive a contradiction.
By `Finset.card_le_one_iff`, a finite set has size at most 1 if and only if all pairs of elements in it are equal. We take arbitrary elements $a, b \in s$ and assume for contradiction that $a \ne b$.
uses
Finset.card_le_one_iffrw [Finset.card_le_one_iff] intro a b ha hb by_contra h
The distinct queens $a$ and $b$ attack each other, contradicting the assumption that $s$ is non-attacking.
Applying `op_1592_zmod2_queens_card_le_one_attack_of_ne` to $a \ne b$ shows that $a$ and $b$ attack each other. Since $a, b \in s$, this directly contradicts the hypothesis `hs` that $s$ contains no attacking pair of queens.
uses
op_1592_zmod2_queens_card_le_one_attack_of_nehave hatt := op_1592_zmod2_queens_card_le_one_attack_of_ne a b h exact hs ha hb h hatt
congr_fun- Equal functions take equal values when evaluated at the same point.
Finset.card_le_one_iff- A finite set has cardinality at most 1 if and only if any two of its elements are equal.
one_mul- Multiplying any element by 1 on the left leaves it unchanged.
op_1592_zmod2_queens_card_le_one_attack_of_ne- Any two distinct points on the modular board $(\mathbb{Z}/2\mathbb{Z})^d$ attack each other.
op_1592_zmod2_queens_card_le_one_to_sign_cast- Casting the sign representation of an element of $\mathbb{Z}/2\mathbb{Z}$ back into $\mathbb{Z}/2\mathbb{Z}$ recovers the original element.
op_1592_zmod2_queens_card_le_one_to_sign_eq_zero_iff- The sign assigned to an element of $\mathbb{Z}/2\mathbb{Z}$ is zero if and only if the element itself is zero.
sub_eq_zero- In an additive group, the difference $a - b$ is zero if and only if $a = b$.
- The definition of a modular queen attack requires the direction vector to take values in `SignType` ({-1, 0, 1}), which are then cast into the base ring. In $\mathbb{Z}/2\mathbb{Z}$, $+1$ and $-1$ coincide, so the helper function `op_1592_zmod2_queens_card_le_one_to_sign` only ever outputs `SignType.zero` and `SignType.pos`. The helper lemmas formally verify that this sign representation faithfully reflects the elements of $\mathbb{Z}/2\mathbb{Z}$.
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.
def op_1592_zmod2_queens_card_le_one_to_sign (a : ZMod 2) : SignType := if a = 0 then SignType.zero else SignType.poslemma op_1592_zmod2_queens_card_le_one_to_sign_cast (a : ZMod 2) : (SignType.cast (op_1592_zmod2_queens_card_le_one_to_sign a) : ZMod 2) = a := by revert a; decidelemma op_1592_zmod2_queens_card_le_one_to_sign_eq_zero_iff (a : ZMod 2) : op_1592_zmod2_queens_card_le_one_to_sign a = 0 ↔ a = 0 := by revert a; decidelemma op_1592_zmod2_queens_card_le_one_attack_of_ne {d : ℕ} (x y : Fin d → ZMod 2) (h : x ≠ y) : modular_queens_attack x y := by unfold modular_queens_attack use 1 use fun i => op_1592_zmod2_queens_card_le_one_to_sign (x i - y i) refine ⟨by decide, ?_, ?_⟩ · intro hv apply h ext i have hi : op_1592_zmod2_queens_card_le_one_to_sign (x i - y i) = 0 := congr_fun hv i rw [op_1592_zmod2_queens_card_le_one_to_sign_eq_zero_iff, sub_eq_zero] at hi exact hi · intro i rw [op_1592_zmod2_queens_card_le_one_to_sign_cast, one_mul]/-- On (Z/2Z)^d, every mutually non-attacking queens configuration has size at most 1. -/theorem op_1592_zmod2_queens_card_le_one {d : ℕ} (s : Finset (Fin d → ZMod 2)) (hs : is_non_attacking_queens s) : s.card ≤ 1 := by rw [Finset.card_le_one_iff] intro a b ha hb by_contra h have hatt := op_1592_zmod2_queens_card_le_one_attack_of_ne a b h exact hs ha hb h hatt