op_1592_not_always_n_sq_minus_one_queens
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.
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).
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, ?_, ?_⟩
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.
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
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.
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]
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.
uses
le_rfl,Nat.le_of_dvdintro 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
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.
uses
Finset.card_le_one_iff,op_1592_not_always_n_sq_minus_one_queens_zmod2_attackhave 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)
A contradiction is reached, completing the proof.
The two deductions |s| = 3 and |s| ≤ 1 are mutually contradictory by linear arithmetic over ℕ.
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
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.
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