AFTD Auto-Formalizing Theoretical Domains

op_1592_zmod2_queens_card_le_one

theoremverifiedformalization

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.

  1. 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}$.

    line 6

      revert a; decide
  2. The 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}$.

    line 10

      revert a; decide
  3. To 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)$.

    lines 14–17

      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, ?_, ?_⟩
  4. 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$.

    lines 18–23

    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
  5. 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.

    lines 24–25

    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]
  6. 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$.

    lines 30–32

    uses Finset.card_le_one_iff

      rw [Finset.card_le_one_iff]
      intro a b ha hb
      by_contra h
  7. 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.

    lines 33–34

    uses op_1592_zmod2_queens_card_le_one_attack_of_ne

      have 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$.

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

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
See it in the graphDiscuss this resultChallenge it