/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilBen Green's Open Problem 97
References:
[Gr24] Green, Ben. "100 open problems." (2024).
[Si23] Simkin, M., The number of $n$-queens configurations. Adv. Math. 427 (2023), Paper No. 109127. arXiv:2107.13460
[BoKe21] Bowtell, C. and Keevash, P., The $n$-queens problem. arXiv:2109.08083 (2021).
[NAB23] Nobel, P., Agrawal, A. and Boyd, S., Computing tighter bounds on the $n$-queens constant via Newton's method. Optim. Lett. 17 (2023), 1229--1240. arXiv:2112.03336
[EMM19] Eberhard, S., Manners, F. and Mrazović, R., Additive triples of bijections, or the toroidal semiqueens problem. J. Eur. Math. Soc. 21 (2019), 441--463. arXiv:1510.05987
@[expose] public sectionopen Filter Asymptoticsopen scoped Nat Topologynamespace Green97
The permutation σ of Fin n is a placement of $n$ non-attacking queens on the $n \times n$
board, with the queen of row i in column σ i.
A placement of $n$ queens on an $n \times n$ board has exactly one queen in each row and in each
column, so it is a permutation. Two queens on the same diagonal have the same value of
σ i - i or of σ i + i, computed in $\mathbb{Z}$.
def IsQueens {n : ℕ} (σ : Equiv.Perm (Fin n)) : Prop :=
(Function.Injective fun i : Fin n ↦ ((σ i).val : ℤ) - (i.val : ℤ)) ∧
Function.Injective fun i : Fin n ↦ ((σ i).val : ℤ) + (i.val : ℤ)instance {n : ℕ} : DecidablePred (IsQueens (n := n)) := fun σ ↦ n:ℕσ:Equiv.Perm (Fin n)⊢ Decidable (IsQueens σ)
n:ℕσ:Equiv.Perm (Fin n)⊢ Decidable ((Function.Injective fun i ↦ ↑↑(σ i) - ↑↑i) ∧ Function.Injective fun i ↦ ↑↑(σ i) + ↑↑i)
All goals completed! 🐙
numQueens n is $Q(n)$, the number of ways to place $n$ non-attacking queens on an $n \times n$
chessboard (IsQueens). For $n = 0$ there is one (empty) placement.
def numQueens (n : ℕ) : ℕ :=
(Finset.univ.filter fun σ : Equiv.Perm (Fin n) ↦ IsQueens σ).card
The permutation σ of Fin n is a placement of $n$ non-attacking queens on the toroidal
$n \times n$ board: as for IsQueens, but the diagonals wrap around, so σ i - i and σ i + i
are computed in $\mathbb{Z}/n\mathbb{Z}$.
def IsToroidalQueens {n : ℕ} (σ : Equiv.Perm (Fin n)) : Prop :=
(Function.Injective fun i : Fin n ↦ ((σ i).val : ZMod n) - (i.val : ZMod n)) ∧
Function.Injective fun i : Fin n ↦ ((σ i).val : ZMod n) + (i.val : ZMod n)instance {n : ℕ} : DecidablePred (IsToroidalQueens (n := n)) := fun σ ↦ n:ℕσ:Equiv.Perm (Fin n)⊢ Decidable (IsToroidalQueens σ)
n:ℕσ:Equiv.Perm (Fin n)⊢ Decidable ((Function.Injective fun i ↦ ↑↑(σ i) - ↑↑i) ∧ Function.Injective fun i ↦ ↑↑(σ i) + ↑↑i)
All goals completed! 🐙
numToroidalQueens n is $T(n)$, the number of ways to place $n$ non-attacking queens on the
toroidal $n \times n$ board (IsToroidalQueens).
def numToroidalQueens (n : ℕ) : ℕ :=
(Finset.univ.filter fun σ : Equiv.Perm (Fin n) ↦ IsToroidalQueens σ).card
The filter on ℕ for $n \to \infty$ through the integers with $n \equiv 1, 5 \pmod 6$. For
$n \ge 1$, these are exactly the $n$ for which $T(n) > 0$ (Pólya, see [BoKe21, Chapter 1]).
noncomputable def toroidalDegrees : Filter ℕ :=
atTop ⊓ Filter.principal {n : ℕ | n % 6 = 1 ∨ n % 6 = 5}The 4-queens problem has $2$ solutions.
@[category test, AMS 5]
theorem numQueens_four : numQueens 4 = 2 := ⊢ numQueens 4 = 2
All goals completed! 🐙The 3-queens problem has no solution.
@[category test, AMS 5]
theorem numQueens_three : numQueens 3 = 0 := ⊢ numQueens 3 = 0
All goals completed! 🐙On the toroidal $5 \times 5$ board there are $10$ placements of $5$ non-attacking queens.
@[category test, AMS 5]
theorem numToroidalQueens_five : numToroidalQueens 5 = 10 := ⊢ numToroidalQueens 5 = 10
All goals completed! 🐙def green_97.answer : ℕ → ℝ := sorryIn how many ways (asymptotically) $Q(n)$ may $n$ non-attacking queens be placed on an $n \times n$ chessboard?
This is the $n$-queens problem, see [Gr24, Problem 97]. We read "asymptotically" as: find an
explicit function green_97.answer with $Q(n) \sim$ green_97.answer n. The function
$n \mapsto Q(n)$ itself is not an explicit answer. [Gr24] notes that an asymptotic "rather than
an asymptotic for the log" is open. What is known is $Q(n) = ((1+o(1)), n e^{-\alpha})^n$ for a
constant $1.94 < \alpha < 1.9449$ [Si23], see green_97.variants.simkin.
@[category research open, question value, AMS 5]
theorem green_97 :
(fun n : ℕ ↦ (numQueens n : ℝ)) ~[atTop] green_97.answer := ⊢ (fun n ↦ ↑(numQueens n)) ~[atTop] green_97.answer
All goals completed! 🐙Simkin's theorem. There is a constant $1.94 < \alpha < 1.9449$ such that $$\lim_{n \to \infty} \frac{Q(n)^{1/n}}{n} = e^{-\alpha},$$ that is, $Q(n) = ((1+o(1)), n e^{-\alpha})^n$ [Si23, Theorem 1.1]. The constant $\alpha$ is defined in [Si23] as the solution of a convex optimisation problem over Borel probability measures on the square $[-1/2, 1/2]^2$. The limit determines $\alpha$ uniquely. Nobel, Agrawal and Boyd [NAB23] combined Simkin's formulation with a sharper bound of Knuth, solved the resulting convex problems numerically, and report the tighter range $\alpha \in [1.944000752, 1.944001082]$.
@[category research solved, AMS 5]
theorem green_97.variants.simkin :
∃ α : ℝ, 1.94 < α ∧ α < 1.9449 ∧
Tendsto (fun n : ℕ ↦ (numQueens n : ℝ) ^ ((1 : ℝ) / n) / n) atTop
(𝓝 (Real.exp (-α))) := ⊢ ∃ α, 1.94 < α ∧ α < 1.9449 ∧ Tendsto (fun n ↦ ↑(numQueens n) ^ (1 / ↑n) / ↑n) atTop (𝓝 (Real.exp (-α)))
All goals completed! 🐙def green_97.variants.alpha.answer : ℝ := sorry
Find an explicit value for the constant $\alpha$ of green_97.variants.simkin, that is, the
number with $Q(n)^{1/n}/n \to e^{-\alpha}$.
[Gr24] writes that "an explicit solution remains an open problem". The value $\alpha$ is the
solution of an entropy optimisation problem [Si23]. As for green_97, an explicit closed form is
intended.
@[category research open, question value, AMS 5]
theorem green_97.variants.alpha :
Tendsto (fun n : ℕ ↦ (numQueens n : ℝ) ^ ((1 : ℝ) / n) / n) atTop
(𝓝 (Real.exp (-green_97.variants.alpha.answer))) := ⊢ Tendsto (fun n ↦ ↑(numQueens n) ^ (1 / ↑n) / ↑n) atTop (𝓝 (Real.exp (-alpha.answer)))
All goals completed! 🐙
Bowtell and Keevash. For $n \equiv 1, 5 \pmod 6$ the number of toroidal $n$-queens
configurations satisfies $T(n) = ((1+o(1)), n e^{-3})^n$ [BoKe21, Theorem 1.2]. The filter
toroidalDegrees restricts to these $n$, because $T(n) = 0$ for all other $n \ge 1$.
@[category research solved, AMS 5]
theorem green_97.variants.bowtell_keevash :
Tendsto (fun n : ℕ ↦ (numToroidalQueens n : ℝ) ^ ((1 : ℝ) / n) / n) toroidalDegrees
(𝓝 (Real.exp (-3))) := ⊢ Tendsto (fun n ↦ ↑(numToroidalQueens n) ^ (1 / ↑n) / ↑n) toroidalDegrees (𝓝 (Real.exp (-3)))
All goals completed! 🐙def green_97.variants.toroidal.answer : ℕ → ℝ := sorryFind an asymptotic for the number $T(n)$ of toroidal $n$-queens configurations, for $n \equiv 1, 5 \pmod 6$.
[Gr24] writes, after the result of [BoKe21], that the problem of "obtaining an asymptotic (rather
than an asymptotic for the log) remains open". [BoKe21] proved the asymptotic of the logarithm, see
green_97.variants.bowtell_keevash. We read "asymptotic" as for green_97: an explicit function
is intended.
@[category research open, question value, AMS 5]
theorem green_97.variants.toroidal :
(fun n : ℕ ↦ (numToroidalQueens n : ℝ)) ~[toroidalDegrees]
green_97.variants.toroidal.answer := ⊢ (fun n ↦ ↑(numToroidalQueens n)) ~[toroidalDegrees] toroidal.answer
All goals completed! 🐙
numAdditiveTriples n is the number of pairs $(\pi_1, \pi_2)$ of bijections
${1, \dots, n} \to \mathbb{Z}/n\mathbb{Z}$ such that $\pi_1 + \pi_2$ is also a bijection
[EMM19, Section 1]. It is $n!$ times the number of arrangements of $n$ mutually non-attacking
semiqueens on the toroidal $n \times n$ board, where a semiqueen moves along rows, columns and
one diagonal direction.
noncomputable def numAdditiveTriples (n : ℕ) : ℕ :=
Nat.card {π : (Fin n ≃ ZMod n) × (Fin n ≃ ZMod n) //
Function.Bijective fun i ↦ π.1 i + π.2 i}Eberhard, Manners and Mrazović. For odd $n$, the number $s_n$ of pairs $(\pi_1, \pi_2)$ of bijections ${1, \dots, n} \to \mathbb{Z}/n\mathbb{Z}$ with $\pi_1 + \pi_2$ also a bijection is $$s_n = (e^{-1/2} + o(1)), \frac{(n!)^3}{n^{n-1}}$$ [EMM19, Theorem 1.2]. [Gr24] refers to this paper for the variant of the toroidal question where only $\pi_1$, $\pi_2$ and $\pi_1 - \pi_2$ are required to be bijections. Replacing $\pi_2$ by $-\pi_2$ shows that this variant has the same count $s_n$. For even $n$, $s_n = 0$ [EMM19, Section 1], so the theorem is stated for odd $n$.
@[category research solved, AMS 5]
theorem green_97.variants.eberhard_manners_mrazovic :
(fun n : ℕ ↦ (numAdditiveTriples n : ℝ)) ~[atTop ⊓ Filter.principal {n : ℕ | Odd n}]
fun n : ℕ ↦ Real.exp (-(1 / 2)) * ((n ! : ℕ) : ℝ) ^ 3 / (n : ℝ) ^ (n - 1) := ⊢ (fun n ↦ ↑(numAdditiveTriples n)) ~[atTop ⊓ 𝓟 {n | Odd n}] fun n ↦ Real.exp (-(1 / 2)) * ↑n ! ^ 3 / ↑n ^ (n - 1)
All goals completed! 🐙end Green97