AFTD Auto-Formalizing Theoretical Domains

op_1592_not_always_n_sq_minus_one_queens

theoremverifiedformalization

It is not the case that for every integer n ≥ 2 all of whose prime factors are at most 7, one can place n^2 - 1 mutually non-attacking queens in (Z/nZ)^3.

Statement

theorem op_1592_not_always_n_sq_minus_one_queens :
    ¬ (∀ n : ℕ, 2 ≤ n → (∀ p : ℕ, p.Prime → p ∣ n → p ≤ 7) →
      ∃ s : Finset (Fin 3 → ZMod n), is_non_attacking_queens s ∧ s.card = n^2 - 1)
Formalizes
arXiv:2611.14754 Sec. 4
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

It is not the case that for every natural number $n \ge 2$ whose prime factors are all at most 7, there exists a subset $s \subseteq (\mathbb{Z}/n\mathbb{Z})^3$ of cardinality $n^2 - 1$ such that $s$ is a set of mutually non-attacking modular queens (i.e., no two distinct elements of $s$ attack each other under modular_queens_attack).

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

The statement is refuted by showing that it fails for n = 2. First, an auxiliary lemma establishes that any two distinct points in (Z/2Z)^d attack each other, because every non-zero coordinate difference in Z/2Z is 1 and can be expressed via a sign vector with scalar c = 1. Consequently, any mutually non-attacking set of queens in (Z/2Z)^3 can contain at most one queen. However, the assumed claim for n = 2 provides a non-attacking set of size 2^2 - 1 = 3, yielding a contradiction.

  1. To show that distinct points x, y ∈ (Z/2Z)^d attack each other, it suffices to show that the sign vector v(i) = (if x(i) - y(i) = 1 then pos else zero) is non-zero and satisfies x(i) - y(i) = 1 * v(i) for all coordinates i.

    By definition, two queens attack each other if their difference vector is a non-zero scalar multiple c of a non-zero sign vector v. We choose scalar c = 1 ∈ Z/2Z (which is non-zero) and define the sign vector v coordinatewise to be +1 where x(i) - y(i) = 1 and 0 otherwise. This leaves the obligations to verify v ≠ 0 and x(i) - y(i) = 1 * v(i).

    lines 3–6

      use 1
      let v : Fin d → SignType := fun i => if x i - y i = 1 then SignType.pos else SignType.zero
      use v
      refine ⟨by decide, ?_, ?_⟩
  2. The direction vector v is non-zero.

    Suppose for contradiction that v = 0. Then v(i) = 0 for every coordinate i. If x(i) - y(i) = 1, then v(i) = 1 by definition, giving a contradiction 1 = 0. Hence x(i) - y(i) ≠ 1. Because the only elements of Z/2Z are 0 and 1, this forces x(i) - y(i) = 0, so x(i) = y(i) for all i. Therefore x = y, contradicting the assumption that x ≠ y.

    lines 7–21

    uses congr_fun, if_pos, False.elim, if_neg, sub_eq_zero.mp

      · intro hv
        apply h
        ext i
        have hvi : v i = 0 := congr_fun hv i
        dsimp [v] at hvi
        by_cases hxy : x i - y i = 1
        · rw [if_pos hxy] at hvi
          exact False.elim (by revert hvi; decide)
        · rw [if_neg hxy] at hvi
          have hz0 : x i - y i = 0 := by
            generalize hz : x i - y i = z at *
            fin_cases z
            · rfl
            · contradiction
          exact sub_eq_zero.mp hz0
  3. For every coordinate i, the difference x(i) - y(i) equals 1 * v(i).

    At each coordinate i, we split into cases on whether x(i) - y(i) = 1. If it is 1, then v(i) = 1, and 1 * 1 = 1 matches the difference. If x(i) - y(i) ≠ 1, then x(i) - y(i) = 0 by exhaustion on Z/2Z, and v(i) = 0, so 1 * 0 = 0 also matches. This completes the proof that any distinct pair in (Z/2Z)^d attacks each other.

    lines 22–33

    uses if_pos, SignType.cast, if_neg

      · intro i
        dsimp [v]
        by_cases hxy : x i - y i = 1
        · rw [if_pos hxy]
          simp [SignType.cast, hxy]
        · rw [if_neg hxy]
          have hz0 : x i - y i = 0 := by
            generalize hz : x i - y i = z at *
            fin_cases z
            · rfl
            · contradiction
          simp [SignType.cast, hz0]
  4. Assuming the general statement holds, there exists a set s ⊆ (Z/2Z)^3 of mutually non-attacking queens of cardinality 3.

    We assume the universal statement H for contradiction. Choosing n = 2, we have 2 ≤ 2 by reflexivity, and every prime divisor p of 2 satisfies p ≤ 2 ≤ 7. Applying H to n = 2 yields a set s of non-attacking queens in (Z/2Z)^3 with cardinality 2^2 - 1 = 3.

    lines 39–45

    uses le_rfl, Nat.le_of_dvd

      intro H
      have h2 : 2 ≤ 2 := le_rfl
      have hprime : ∀ p : ℕ, p.Prime → p ∣ 2 → p ≤ 7 := by
        intro p _ hp2
        have : p ≤ 2 := Nat.le_of_dvd (by decide) hp2
        omega
      obtain ⟨s, hs, hcard⟩ := H 2 h2 hprime
  5. Any set s ⊆ (Z/2Z)^3 of mutually non-attacking queens has cardinality at most 1.

    By Finset.card_le_one_iff, a set has at most one element if and only if any two of its elements are equal. If s contained distinct elements a and b, the helper lemma op_1592_not_always_n_sq_minus_one_queens_zmod2_attack would imply that a and b attack each other, contradicting the non-attacking hypothesis on s. Thus |s| ≤ 1.

    lines 46–50

    uses Finset.card_le_one_iff, op_1592_not_always_n_sq_minus_one_queens_zmod2_attack

      have hle : s.card ≤ 1 := by
        rw [Finset.card_le_one_iff]
        intro a b ha hb
        by_contra h
        exact hs ha hb h (op_1592_not_always_n_sq_minus_one_queens_zmod2_attack a b h)
  6. A contradiction is reached, completing the proof.

    The two deductions |s| = 3 and |s| ≤ 1 are mutually contradictory by linear arithmetic over ℕ.

    line 51

      omega
False.elim
From a proof of False, any proposition follows (the principle of explosion).
Finset.card_le_one_iff
A finite set has cardinality at most 1 if and only if any two of its elements are equal.
Nat.le_of_dvd
If a natural number m divides a strictly positive natural number n, then m ≤ n.
SignType.cast
The canonical coercion of a sign value (pos, zero, neg) into a type equipped with 0, 1, and negation.
congr_fun
If two functions are equal, then their values at any argument are equal.
if_neg
If condition c is false, the conditional expression if c then t else e evaluates to e.
if_pos
If condition c is true, the conditional expression if c then t else e evaluates to t.
le_rfl
Every element in a preorder is less than or equal to itself (reflexivity of ≤).
op_1592_not_always_n_sq_minus_one_queens_zmod2_attack
Any two distinct points in (Z/2Z)^d attack each other as modular queens.
sub_eq_zero.mp
If a - b = 0, then 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

lemma op_1592_not_always_n_sq_minus_one_queens_zmod2_attack {d : ℕ} (x y : Fin d → ZMod 2) (h : x ≠ y) :    modular_queens_attack x y := by  use 1  let v : Fin d → SignType := fun i => if x i - y i = 1 then SignType.pos else SignType.zero  use v  refine ⟨by decide, ?_, ?_⟩  · intro hv    apply h    ext i    have hvi : v i = 0 := congr_fun hv i    dsimp [v] at hvi    by_cases hxy : x i - y i = 1    · rw [if_pos hxy] at hvi      exact False.elim (by revert hvi; decide)    · rw [if_neg hxy] at hvi      have hz0 : x i - y i = 0 := by        generalize hz : x i - y i = z at *        fin_cases z        · rfl        · contradiction      exact sub_eq_zero.mp hz0  · intro i    dsimp [v]    by_cases hxy : x i - y i = 1    · rw [if_pos hxy]      simp [SignType.cast, hxy]    · rw [if_neg hxy]      have hz0 : x i - y i = 0 := by        generalize hz : x i - y i = z at *        fin_cases z        · rfl        · contradiction      simp [SignType.cast, hz0]/-- Refutation of the sub-question in OP-1592: it is false that n^2 - 1 non-attacking queens can always be placed on (Z/nZ)^3 when prime factors of n are at most 7. -/theorem op_1592_not_always_n_sq_minus_one_queens :    ¬ (∀ n : ℕ, 2 ≤ n → (∀ p : ℕ, p.Prime → p ∣ n → p ≤ 7) →      ∃ s : Finset (Fin 3 → ZMod n), is_non_attacking_queens s ∧ s.card = n^2 - 1) := by  intro H  have h2 : 2 ≤ 2 := le_rfl  have hprime : ∀ p : ℕ, p.Prime → p ∣ 2 → p ≤ 7 := by    intro p _ hp2    have : p ≤ 2 := Nat.le_of_dvd (by decide) hp2    omega  obtain ⟨s, hs, hcard⟩ := H 2 h2 hprime  have hle : s.card ≤ 1 := by    rw [Finset.card_le_one_iff]    intro a b ha hb    by_contra h    exact hs ha hb h (op_1592_not_always_n_sq_minus_one_queens_zmod2_attack a b h)  omega
See it in the graphDiscuss this resultChallenge it