In the statement of the next lemma $K$ refers to the constant used to define
$T$.

######  Lemma 5.18.

It holds that

$H(X_{1},X_{2},\ldots,X_{T})=n\left(H_{q}^{M}(\delta)+2\log n-1\right)\pm
n^{1-1/K^{3}}.$

###### Proof.

By the chain rule:

$H(X_{1},X_{2},\ldots,X_{T})=\sum_{t=1}^{T}H(X_{t}{|}X_{1},\ldots,X_{t-1}).$

By Claim 3.2, for $\alpha\in J_{M}$ and $*\in\\{+,-\\}$:

$\displaystyle\sum_{t=0}^{T-1}$
$\displaystyle\delta^{*}(\alpha)\log(1-M\delta^{*}(\alpha)t/n)$
$\displaystyle=-\frac{n}{M}\left((1-M\delta^{*}(\alpha)\log(1-M\delta^{*}(\alpha))+M\delta^{*}(\alpha)\right)\pm\frac{1}{M}2(n-T)\log(1-T/n)$
$\displaystyle=-\frac{n}{M}\left(M\overline{\delta}^{*}(\alpha)\log\left(M\overline{\delta}^{*}(\alpha)\right)+M\delta^{*}(\alpha)\right)\pm\frac{1}{M}2(n-T)\log(1-T/n)$
$\displaystyle=-n\left(\overline{\delta}^{*}(\alpha)\log\left(\frac{\overline{\delta}^{*}(\alpha)}{1/(2M)}\right)-\overline{\delta}^{*}(\alpha)\log(2)+\delta^{*}(\alpha)\right)\pm\frac{2}{M}(n-T)\log(1-T/n).$

Therefore:

$\displaystyle\sum_{t=0}^{T-1}$ $\displaystyle\sum_{\alpha\in
J_{M}}\delta^{*}(\alpha)\log(1-M\delta^{*}(\alpha)t/n)$
$\displaystyle=-nD(\\{\overline{\delta}^{*}(\alpha)\\}_{\alpha\in
J_{M}})+n\log(2)-n\pm 4(n-T)\log(1-T/n).$

Applying Claim 5.17:

$\displaystyle\sum_{t=1}^{T}$ $\displaystyle H(X_{t}{|}X_{1},\ldots,X_{t-1})$
$\displaystyle=$
$\displaystyle\sum_{t=0}^{T-1}2\log(n-t)-TD^{M}(\delta)-nD(\\{{\overline{{\delta}}^{+}}(\alpha)\\}_{\alpha\in
J_{M}})-nD(\\{{\overline{{\delta}}^{-}}(\alpha)\\}_{\alpha\in J_{M}})$
$\displaystyle+2n\log(2)-2n\pm
O\left((n-T)\log(1-T/n)+\sum_{t=0}^{T-1}\frac{ME(t)}{n(1-t/n)^{2}}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{Claim \ref{clm:log
integral}}}}{{=}}$ $\displaystyle n(H_{q}^{M}(\delta)+2\log(n)-1)\pm
O\left((n-T)\log(1-T/n)+\frac{nME(T)}{n-T}\right).$

Taking account the definition of $E(t)$ and $T$ we have $nME(T)/(n-T)\leq
n-T=O(n^{1-1/K^{2}})$. Therefore:

$\displaystyle\sum_{t=1}^{T}H(X_{t}{|}X_{1},\ldots,X_{t-1})=n\left(H_{q}(\delta)+2\log
n-1\right)\pm n^{1-1/K^{3}},$

as claimed. ∎

###  5.2. Absorbers

In this section we analyze Algorithm 5.3. We wish to show that it is unlikely
to abort. The next lemma provides a sufficient condition.

######  Definition 5.19.

Let $\ell>0$. A partial $n$-queens configuration $Q$ is $\ell$-absorbing if
for every $(c,r)\in[n]^{2}$, it holds that
$\left|{\mathcal{B}}_{Q}(c,r)\right|\geq\ell$.

The following is Lemma 4.2 in [19].

######  Lemma 5.20.

Suppose $|Q(T)|=T$ and $Q(T)$ is $10(n-T)$-absorbing. Then Algorithm 5.3 does
not abort.

For the proof we refer the reader to [19]. We mention only that the key
observation is that for every $(c,r)\in[n]^{2}$, every step of Algorithm 5.3
“destroys” at most $9$ absorbers in ${\mathcal{B}}_{Q(T)}(c,r)$.

The next lemma asserts that w.h.p. $Q(T)$ is $\Omega(n)$-absorbing. By
Proposition 5.7, w.h.p. $n-|Q(T)|=n-T=o(n)$. It then follows from Lemma 5.20
that Algorithm 5.3 succeeds in constructing an $n$-queens configuration.

######  Lemma 5.21.

W.h.p. $Q(T)$ is $\Omega(n)$-absorbing.

The intuition is that $Q(T)$ contains approximately $n$ queens, each occupying
a single diagonal of each type. However, the grid $[n]^{2}$ contains
approximately $2n$ diagonals of each type. Therefore, if one chooses a
diagonal uniformly at random the probability that it is unoccupied is bounded
away from $0$. If we fix $(c,r)$ and choose $(x,y)\in Q(T)$ uniformly at
random, we might imagine that the (four) diagonals containing $(c,y)$ and
$(x,r)$ are distributed uniformly at random, which would imply that with
constant probability they are unoccupied, in which case $(x,y)$ is an absorber
for $(c,r)$.

In order to prove Lemma 5.21 we couple the random process
$\\{Q(t)\\}_{t=0}^{T}$ with a random set that is the union of binomial random
subsets of $[n]^{2}$. Let $\\{s_{x}\\}_{x\in[n]^{2}}$ be i.i.d. uniform random
variables in $[0,1]$. Consider the following process: Let
${\tilde{Q}}(0)=\emptyset$. Define $Y_{1},\ldots,Y_{T}\in I_{M}$ as in
Algorithm 5.2. Suppose we have constructed ${\tilde{Q}}(t-1)$. Let
$\alpha=Y_{t}$. Then, let $X_{t}$ be the element of
$\alpha_{n}\cap{\mathcal{A}}_{{\tilde{Q}}(t-1)}$ minimizing $s_{x}$. If
$\alpha_{n}\cap{\mathcal{A}}_{{\tilde{Q}}(t-1)}=\emptyset$, abort and set
$X_{t}=X_{t+1}=\ldots=X_{T}=*$. Clearly, $\\{Q(t)\\}_{t=0}^{T}$ and
$\\{{\tilde{Q}}(t)\\}_{t=0}^{T}$ have identical distributions, so we may (and
do) identify them.

Define $R\subseteq[n]^{2}$ as follows: Recall that for $x\in[n]^{2}$,
$\alpha(x)$ is the $\alpha\in I_{M}$ such that $x\in\alpha_{n}$. Include $x$
in $R$ if $s_{x}<\varepsilon\delta(\alpha(x))M^{2}/n$. Let
$R^{\prime}\subseteq R$ be the set of elements $x\in R$ that do not share a
row, column, or diagonal with any other element of $R$. Let
${\tilde{R}}=\\{x\in
R^{\prime}:s_{x}<\varepsilon\delta(\alpha(x))M^{2}/(20n)\\}$. Clearly,
${\tilde{R}}$ is a partial $n$-queens configuration. We will show that w.h.p.
every partial configuration containing ${\tilde{R}}$ and contained in $R$ is
$\Omega(n)$-absorbing. Furthermore, we will show that w.h.p. there exists some
$0\leq T_{R}\leq T$ such that ${\tilde{R}}\subseteq Q(T_{R})\subseteq R$. This
implies that $Q(T_{R})$ is $\Omega(n)$-absorbing. Finally, we will show that
w.h.p. a constant fraction of the absorbers in $Q(T_{R})$ survive until the
end of the random process, which will imply Lemma 5.21.

Let $T_{R}\coloneqq\lfloor\frac{1}{8}\varepsilon n\rfloor$. In order to show
that $Q(T_{R})\subseteq R$ we first prove that $R^{\prime}$ intersects every
$\alpha\in I_{M}$ in many places. We will use the following concentration
inequality, which is a special case of [27, Theorem 1.10].

######  Theorem 5.22.

Let $X_{1},\ldots,X_{N}$ be independent random variables taking values in a
finite set $\Lambda$. Let $p\in(0,1]$ satisfy
$\max\\{{\mathbb{P}}[X_{i}=\eta]:\eta\in\Lambda,i\in[N]\\}\geq 1-p$. Assume
that for $K>0$ the function $f:\Lambda^{N}\to\mathbb{R}$ satisfies the
Lipschitz condition $\left|f(\omega)-f(\omega^{\prime})\right|\leq K$ whenever
$\omega,\omega^{\prime}\in\Lambda^{N}$ differ by a single coordinate. Then,
for all $t\geq 0$:

${\mathbb{P}}\left[\left|f(X_{1},\ldots,X_{N})-{\mathbb{E}}\left[f(X_{1},\ldots,X_{N})\right]\right|\geq
t\right]\leq 2\exp\left(-\frac{t^{2}}{2K^{2}Np+2Kt/3}\right).$

We will need the following bounds on the probability that all values
$s_{(x,y)}$, where $(x,y)$ is all positions on a row, column, or diagonal,
exceed a given threshold.

######  Claim 5.23.

Let $(x,y)\in[n]^{2}$ and let $\varepsilon\geq\varepsilon_{0}>0$. The
following hold:

  1. (a)

$\prod_{a\in[n]}\left(1-\frac{\varepsilon_{0}\delta(\alpha(a,y))M^{2}}{n}\right)\geq
1-\varepsilon_{0}$,

  2. (b)

$\prod_{a\in[n]}\left(1-\frac{\varepsilon_{0}\delta(\alpha(x,a))M^{2}}{n}\right)\geq
1-\varepsilon_{0}$,

  3. (c)

$\prod_{(a,b)\in[n]^{2},a+b=x+y}\left(1-\frac{\varepsilon_{0}\delta(\alpha(a,b))M^{2}}{n}\right)\geq
1-\varepsilon_{0}$,

  4. (d)

$\prod_{(a,b)\in[n]^{2},a-b=x-y}\left(1-\frac{\varepsilon_{0}\delta(\alpha(a,b))M^{2}}{n}\right)\geq
1-\varepsilon_{0}$.

###### Proof.

We will prove (a) and (c). (b) and (d) follow by symmetry. We use the fact
that for sufficiently small $z$, $\log(1-z)\geq-z-z^{2}$. This implies:

$\prod_{a\in[n]}\left(1-\frac{\varepsilon_{0}\delta(\alpha(a,y))M^{2}}{n}\right)\geq\exp\left(-\sum_{a\in[n]}\left(\frac{\varepsilon_{0}\delta(\alpha(a,y))M^{2}}{n}+\left(\frac{\varepsilon_{0}\delta(\alpha(a,y))M^{2}}{n}\right)^{2}\right)\right).$

Because $\delta$ has uniform marginals, $\delta(\alpha)\leq 1/M$ for every
$\alpha\in I_{M}$. Thus
$\sum_{a\in[n]}(\varepsilon_{0}\delta(\alpha(a,y))M^{2}/n)^{2}\leq\varepsilon_{0}^{2}M^{2}/n={o\left(1\right)}$.
Therefore:

$\displaystyle\prod_{a\in[n]}\left(1-\frac{\varepsilon_{0}\delta(\alpha(a,y))M^{2}}{n}\right)$
$\displaystyle\geq(1-{o\left(1\right)})\exp\left(-\frac{\varepsilon_{0}M^{2}}{n}\sum_{a\in[n]}\delta(\alpha(a,b))\right)$
$\displaystyle=(1-{o\left(1\right)})\exp\left(-\frac{\varepsilon_{0}M^{2}}{n}\sum_{\alpha\in
I_{M}}\delta(\alpha)L_{y,\alpha}^{r}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{Claim \ref{clm:line sums}
\ref{itm:row
sum}}}}{{=}}(1-{o\left(1\right)})\exp\left(-\frac{\varepsilon_{0}M^{2}}{n}\times\frac{n}{2M^{2}}\right)\geq
1-\varepsilon_{0},$

proving (a).

We turn to (c), which is proved similarly.

$\displaystyle\prod_{(a,b)\in[n]^{2},a+b=x+y}\left(1-\frac{\varepsilon_{0}\delta(\alpha(a,b))M^{2}}{n}\right)$
$\displaystyle\geq(1-{o\left(1\right)})\exp\left(-\frac{\varepsilon_{0}M^{2}}{n}\sum_{\alpha\in
I_{M}}\delta(\alpha)L_{x+y,\alpha}^{+}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{Claim \ref{clm:line sums}
\ref{itm:plus diagonal
sum}}}}{{\geq}}(1-{o\left(1\right)})\exp\left(-\frac{\varepsilon_{0}M^{2}}{n}\times\frac{\delta^{+}(\alpha)n}{2M}\right).$

$\delta$ has sub-uniform marginals, so $\delta^{+}(\alpha)\leq 1/M$. Hence:

$\displaystyle\prod_{(a,b)\in[n]^{2},a+b=x+y}\left(1-\frac{\varepsilon_{0}\delta(\alpha(a,b))M^{2}}{n}\right)\geq(1-{o\left(1\right)})\exp\left(-\frac{\varepsilon_{0}}{2}\right)\geq
1-\varepsilon_{0},$

proving (c). ∎

######  Claim 5.24.

W.h.p. for every $\alpha\in I_{M}$ it holds that $\left|\alpha_{n}\cap
R^{\prime}\right|\geq\frac{7}{6}\delta(\alpha)T_{R}$.

###### Proof.

Let $\alpha\in I_{M}$ and let $(x,y)\in\alpha_{n}$. By definition, $(x,y)\in
R^{\prime}$ if and only if $(x,y)\in R$ and $(a,b)\notin R$ for every
$(a,b)\in[n]^{2}$ that shares a row, column, or diagonal with $(x,y)$. Because
the elements of $[n]^{2}$ are chosen independently of each other:

$\displaystyle{\mathbb{P}}$ $\displaystyle\left[(x,y)\in
R^{\prime}\right]={\mathbb{P}}\left[(x,y)\in
R\right]\left(\prod_{a\in[n],a\neq x}{\mathbb{P}}\left[(a,y)\notin
R\right]\right)\left(\prod_{a\in[n],a\neq y}{\mathbb{P}}\left[(x,a)\notin
R\right]\right)\times$
$\displaystyle\left(\prod_{(a,b)\in[n]^{2},a+b=x+y,(a,b)\neq(x,y)}{\mathbb{P}}\left[(a,b)\notin
R\right]\right)\left(\prod_{(a,b)\in[n]^{2},a-b=x-y,(a,b)\neq(x,y)}{\mathbb{P}}\left[(a,b)\notin
R\right]\right).$

By definition, ${\mathbb{P}}[(x,y)\in R]=\varepsilon\delta(\alpha)M^{2}/n$.
Similarly, for every $(a,b)\in[n]^{2}$ we have ${\mathbb{P}}\left[(a,b)\notin
R\right]=1-\varepsilon\delta(\alpha{(a,b)})M^{2}/n$. Therefore, by Claim 5.7:

${\mathbb{P}}\left[(x,y)\in
R^{\prime}\right]\geq\frac{\varepsilon\delta(\alpha)M^{2}}{n}(1-\varepsilon)^{4}.$

Thus, since $|\alpha_{n}|\geq n^{2}/(4M^{2})-O(n/M)$ for every $\alpha$:

${\mathbb{E}}\left[|\alpha_{n}\cap
R^{\prime}|\right]\geq\frac{\varepsilon\delta(\alpha)M^{2}}{n}(1-\varepsilon)^{4}|\alpha_{n}|\geq\frac{\varepsilon\delta(\alpha)n}{5}\geq\frac{7\delta(\alpha)T_{R}}{5}.$

We now observe that adding or removing an element from $R$ changes
$R^{\prime}$ by at most $4$ elements. Therefore, by Theorem 5.22, with
$\lambda={\mathbb{E}}\left[|\alpha_{n}\cap
R^{\prime}|\right]-\frac{7}{6}\delta(\alpha)T_{R}=\Omega\left(n/M^{2}\right)$:

$\displaystyle{\mathbb{P}}\left[|\alpha_{n}\cap
R^{\prime}|<\frac{7}{6}\delta(\alpha)T_{R}\right]$ $\displaystyle\leq
2\exp\left(-\frac{\lambda^{2}}{32\sum_{(x,y)\in[n]^{2}}\varepsilon\delta(\alpha)M^{2}/n+32\lambda/3}\right)$
$\displaystyle=\exp\left(-\Omega\left(n/M^{4}\right)\right)=\exp\left(-\Omega\left(n^{0.6}\right)\right).$

The claim follows by applying a union bound to the polynomially many elements
of $I_{M}$. ∎

For $\alpha\in I_{M}$ let $W_{\alpha}$ be the number of $1\leq t\leq T_{R}$
such that $Y_{t}=\alpha$.

######  Claim 5.25.

W.h.p. for every $\alpha\in I_{M}$,
$W_{\alpha}=\left(1\pm\frac{1}{12}\right)\delta(\alpha)T_{R}$.

###### Proof.

Observe that $W_{\alpha}$ is distributed binomially with parameters
$T_{R},\delta(\alpha)$. The claim follows by applying Chernoff’s inequality
and a union bound. ∎

######  Claim 5.26.

W.h.p. for every $\alpha\in I_{M}$ there are at most
$\frac{1}{2}\delta(\alpha)T_{R}$ positions $(x,y)\in\alpha_{n}$ such that
$s_{(x,y)}<\varepsilon\delta(\alpha)M^{2}/(20n)$.

###### Proof.

Let $\alpha\in I_{M}$ and let
$S(\alpha)=|\\{(x,y)\in\alpha_{n}:s_{(x,y)}<\varepsilon\delta(\alpha)M^{2}/(20n)\\}|$.
Then $S(\alpha)$ is distributed binomially with parameters
$|\alpha_{n}|,\varepsilon\delta(\alpha)M^{2}/(20n)$. Therefore
${\mathbb{E}}S(\alpha)=|\alpha_{n}|\varepsilon\delta(\alpha)M^{2}/(20n)$. For
every $\alpha$, $|\alpha_{n}|\leq n^{2}/(2M^{2})+O(n/M)$. Hence
${\mathbb{E}}S(\alpha)\leq\frac{2}{5}\delta(\alpha)T_{R}$. The claim follows
from Chernoff’s inequality and a union bound. ∎

######  Claim 5.27.

W.h.p. ${\tilde{R}}\subseteq Q(T_{R})\subseteq R$.

###### Proof.

We first prove that w.h.p. $Q(T_{R})\subseteq R$. We will show that if
$Q(T_{R})\nsubseteq R$ then there exists some $\alpha\in I_{M}$ such that
$W_{\alpha}>|\alpha_{n}\cap R^{\prime}|$. Indeed, suppose that
$Q(T_{R})\nsubseteq R$. Then there exists a minimal $t\leq T_{R}$ such that
$X_{t}\notin R$. Let $x=X_{t}$ and $\alpha=\alpha(x)$. By definition of $R$,
$s_{x}\geq\varepsilon\delta(\alpha)M^{2}/n$. We claim that $\alpha_{n}\cap
R^{\prime}\subseteq Q(t-1)$. Let $y\in\alpha_{n}\cap R^{\prime}$. It holds
that $s_{y}<\varepsilon\delta(\alpha)M^{2}/n\leq s_{x}$. By definition of the
process, $s_{x}$ is smaller than $s_{z}$ for every
$z\in\alpha_{n}\cap{\mathcal{A}}_{Q(t-1)}$. Therefore,
$y\notin{\mathcal{A}}_{Q(t-1)}$. By definition of $R^{\prime}$, $y$ is not
threatened by any element of $R$. Since $Q(t-1)\subseteq R$ this means that
$y$ is not threatened by any element of $Q(t-1)$. Therefore, since $y$ is
unavailable, it must be that $y\in Q(t-1)$. This means that
$W_{\alpha}\geq|\alpha_{n}\cap R^{\prime}|+1>|\alpha_{n}\cap R^{\prime}|$.

We have shown that if $Q(T_{R})\nsubseteq R$ then there exists some $\alpha\in
I_{M}$ such that $W_{\alpha}>|\alpha_{n}\cap R^{\prime}|$. However, Claims
5.24 and 5.25 imply that w.h.p. for every $\alpha\in I_{M}$:

$W_{\alpha}\leq\frac{13}{12}\delta(\alpha)T_{R}<\frac{7}{6}\delta(\alpha)T_{R}\leq|\alpha_{n}\cap
R^{\prime}|.$

Therefore $Q(T_{R})\subseteq R$ w.h.p.

We now show that w.h.p. ${\tilde{R}}\subseteq Q(T_{R})$. If
${\tilde{R}}\nsubseteq Q(T_{R})$ then there exists some
$x\in{\tilde{R}}\setminus Q(T_{R})$. Let $\alpha=\alpha(x)$. By definition,
$s_{x}<\varepsilon\delta(\alpha)M^{2}/(20n)$ and $x$ is not threatened by any
element of $R$. Therefore, if $Q(T_{R})\subseteq R$ then for every $0\leq
t\leq T_{R}$, $x\in{\mathcal{A}}_{Q(t)}$. Since $x\notin Q(T_{R})$ this means
that for every $1\leq t\leq T_{R}$ $x$ did not minimize $s_{x}$ among all
elements of ${\mathcal{A}}_{Q(t)}\cap\alpha_{n}$. Therefore there exist at
least $W_{\alpha}$ elements $z\in\alpha_{n}$ such that
$s_{z}<s_{x}<\varepsilon\delta(\alpha)M^{2}/(20n)$.

We have shown that if ${\tilde{R}}\nsubseteq Q(T_{R})$ then either
$Q(T_{R})\nsubseteq R$ or there exists some $\alpha\in I_{M}$ such that
$|\\{z\in\alpha_{n}:s_{z}<\varepsilon\delta(\alpha)M^{2}/(20n)\\}|\geq
W_{\alpha}$. However, we have shown that w.h.p. $Q(T_{R})\subseteq R$.
Furthermore, by Claims 5.25 and 5.26 w.h.p. for every $\alpha\in I_{M}$:

$|\\{z\in\alpha_{n}:s_{z}<\varepsilon\delta(\alpha)M^{2}/(20n)\\}|\leq\frac{1}{2}\delta(\alpha)T_{R}<\frac{11}{12}\delta(\alpha)T_{R}\leq
W_{\alpha}.$

Therefore w.h.p. ${\tilde{R}}\subseteq Q(T_{R})$, as desired. ∎

Next, we show that w.h.p. $Q(T_{R})$ is $\Omega(n)$-absorbing. In the
statement of the next claim, $\rho>0$ is the constant used to define $\delta$.

######  Claim 5.28.

Let $C=\varepsilon\rho/1000$. W.h.p. $Q(T_{R})$ is $Cn$-absorbing.

###### Proof.

We will show that w.h.p. for every $(x,y)\in[n]^{2}$ there are at least $Cn$
queens $(a,b)\in{\tilde{R}}$ such that:

  * •

$(a,b)$ and $(x,y)$ do not share a diagonal.

  * •

The diagonals passing through $(x,b)$ and $(a,y)$ do not contain any elements
of $R$.

If, as happens w.h.p., ${\tilde{R}}\subseteq Q(T_{R})\subseteq R$, every such
position satisfies $(a,b)\in{\mathcal{B}}_{Q(T_{R})}(x,y)$. Hence, w.h.p.
$Q(T_{R})$ is $Cn$-absorbing.

Let $(x,y)\in[n]^{2}$. Let $K_{(x,y)}$ be the number of queens $(a,b)$
satisfying the conditions above. We wish to apply Theorem 5.22 to $K_{(x,y)}$.
We first show that $K_{(x,y)}$ can be expressed as a function of independent
random variables. Let $\Lambda=\\{0,1,2\\}$. For $(a,b)\in[n]^{2}$, let

$S_{(a,b)}=\begin{cases}0&s_{(a,b)}<\varepsilon\delta(\alpha(a,b))M^{2}/(20n)\\\
1&s_{(a,b)}\in(\varepsilon\delta(\alpha(a,b))M^{2}/(20n),\varepsilon\delta(\alpha(a,b))M^{2}/n)\\\
2&\text{otherwise}.\end{cases}$

Note that the sets $R$ and ${\tilde{R}}$, and hence the value of $K_{(x,y)}$,
can be recovered from the random variables
$\\{S_{(a,b)}\\}_{(a,b)\in[n]^{2}}$. Hence, we may apply Theorem 5.22 together
with a union bound over the $n^{2}$ positions. To do so it suffices to show
the following:

  1. (a)

${\mathbb{E}}\left[K_{(x,y)}\right]\geq 2Cn$.

  2. (b)

If we change $R$ or ${\tilde{R}}$ by either removing or adding a queen then
$K_{(x,y)}$ changes by at most $O(1)$.

  3. (c)

For $p=M/n$ and every $(a,b)\in[n]^{2}$ it holds that
${\mathbb{P}}\left[S_{(a,b)}=2\right]\geq 1-p$.

Indeed, if these conditions hold then by Theorem 5.22:

$\displaystyle{\mathbb{P}}\left[K_{(x,y)}\leq
Cn\right]\leq{\mathbb{P}}\left[K_{(x,y)}\leq{\mathbb{E}}\left[K_{(x,y)}\right]-Cn\right]$
$\displaystyle\leq 2\exp\left(-\frac{C^{2}n^{2}}{O(n^{2}M/n)+8Cn/3}\right)$
$\displaystyle=\exp\left(-\Omega(n/M)\right).$

We begin with (a). Let $(a,b)\in[n]^{2}$ such that $(a,b)$ and $(x,y)$ do not
share a diagonal, row, or column. By a calculation similar to the one in the
proof of Claim 5.24,
${\mathbb{P}}\left[(a,b)\in{\tilde{R}}\right]\geq{\mathbb{P}}[s_{(a,b)}<\varepsilon\delta(\alpha(a,b))M^{2}/(20n)](1-\varepsilon^{4})=(1-\varepsilon)^{4}\varepsilon\delta(\alpha(a,b))M^{2}/(20n)$.
Now $\delta(\alpha(a,b))\geq 0.6\rho/(4M^{2})$. Thus:

${\mathbb{P}}\left[(a,b)\in{\tilde{R}}\right]\geq(1-\varepsilon)^{4}\varepsilon\frac{3\rho}{20M^{2}}\times\frac{M^{2}}{20n}=\frac{3(1-\varepsilon)^{4}\varepsilon\rho}{400n}.$

Now, by Claim 5.23 the probability that the four diagonals incident with
$(a,y)$ and $(x,b)$ do not contain elements of $R$ is
$\geq(1-\varepsilon)^{4}$. Therefore:

${\mathbb{E}}\left[K_{(x,y)}\right]\geq{\left(1\pm{o\left(1\right)}\right)}n^{2}\frac{3(1-\varepsilon)^{4}\varepsilon\rho}{400n}(1-\varepsilon)^{4}\geq
2Cn,$

proving (a).

To see that (b) holds observe that adding a queen $(a,b)$ to $R$ or
${\tilde{R}}$ can increase $K_{(x,y)}$ by at most $1$. At the same time,
$K_{(x,y)}$ can decrease by at most $4$, as there are at most $4$ queens
$(c,r)\in{\tilde{R}}$ such that $(a,b)$ occupied a diagonal incident to
$(c,y)$ or $(x,r)$, and at most $2$ queens in ${\tilde{R}}$ sharing a row or
column with $(a,b)$.

Finally, (c) holds because for every $(a,b)\in[n]^{2}$ it holds that

${\mathbb{P}}\left[S_{(a,b)}=2\right]=1-\frac{\varepsilon\delta(\alpha(a,b))M^{2}}{n}\geq
1-\frac{\varepsilon M^{-1}M^{2}}{n}\geq 1-\frac{M}{n}.\qed$

We now show that w.h.p. a constant fraction of the absorbers in $Q(T_{R})$ are
also absorbers in $Q(T)$ (i.e., the outcome of Algorithm 5.2). In the next
claim, $\tau$ refers to the stopping time in Definition 5.6 and the constant
$C$ is the same as in the statement of Claim 5.28. Define
$\zeta\coloneqq\eta/(1-\eta)$, where $\eta$ is the constant from Observation
5.1.

######  Claim 5.29.

Suppose that $Q(T_{R})$ is $Cn$-absorbing and that $\tau>T_{R}$. Then, for
$D=e^{-15\zeta}C$, with probability
$1-\exp\left(-\Omega\left(n^{0.75}\right)\right)$, $Q(T)$ is $Dn$-absorbing.

###### Proof.

Let $(x,y)\in[n]^{2}$. By assumption, $|{\mathcal{B}}_{Q(T_{R})}(x,y)|\geq
Cn$. For $T_{R}\leq t\leq T$, let
${\mathcal{C}}(t)={\mathcal{B}}_{Q(T_{R})}(x,y)\cap{\mathcal{B}}_{Q(t)}(x,y)$.
We will use a martingale analysis to prove that

${\mathbb{P}}\left[|{\mathcal{C}}(T)|<Dn\right]\leq\exp\left(-\Omega(n^{0.75})\right).$

Since $|{\mathcal{B}}_{Q(T)}(x,y)|\geq|{\mathcal{C}}(T)|$ the result then
follows from a union bound over the $n^{2}$ positions in $[n]^{2}$. We define
the random variables $\\{C_{t}\\}_{t=T_{R}}^{T}$ as follows:

$C_{t}=\begin{cases}\left|{\mathcal{C}}(t)\right|&\tau\geq t\\\
C_{t-1}&\tau<t.\end{cases}$

Observe that for every $T_{R}\leq t<T$ it holds that

(11) $|C_{t+1}-C_{t}|=O(1).$

This is because every queen added to a partial configuration can “destroy” at
most $4$ absorbers for $(x,y)$. We will now show that for every $T_{R}\leq
t<T$:

(12)
${\mathbb{E}}\left[C_{t+1}{|}Q(t)\right]\geq\left(1-\frac{4\zeta}{n}\right)C_{t}.$

Indeed, if $\tau\leq t$ then, by definition, $C_{t+1}=C_{t}$ and (12) holds.
On the other hand, if $\tau>t$, then $C_{t+1}=\left|{\mathcal{C}}(t+1)\right|$
and $C_{t}=\left|{\mathcal{C}}(t)\right|$. We note that
${\mathcal{C}}(t+1)\subseteq{\mathcal{C}}(t)$. Thus, to prove (12), it
suffices to show that for every $(a,b)\in{\mathcal{C}}(t)$,

${\mathbb{P}}\left[(a,b)\notin{\mathcal{C}}(t+1){|}\tau>t\right]\leq\frac{4\zeta}{n}.$

The event $(a,b)\notin{\mathcal{C}}(t+1)$ occurs only if the queen added at
time $t+1$ occupied one of the four diagonals containing $(x,b)$ or $(a,y)$.
By Claim 5.10, since $t<\tau$ for every diagonal the probability that it is
occupied at time $t+1$ is $\leq\zeta/n$. By a union bound, the probability
that one of the four diagonals incident to $(x,b)$ and $(a,y)$ is occupied is
$\leq 4\zeta/n$. Thus:

$\displaystyle{\mathbb{P}}\left[(a,b)\notin{\mathcal{C}}(t+1){|}\tau>t\right]\leq\frac{4\zeta}{n},$

as desired.

Equation (12) suggests that $C_{T}\geq(1-4\zeta/n)^{T-T_{R}}C_{T_{R}}\geq Dn$.
We will justify this heuristic with a martingale analysis. We first transform
$\\{C_{t}\\}$ in order to apply Azuma’s inequality (Theorem 5.11). Define
$C^{\prime}_{t}=\max\\{C_{t},Dn\\}$. It holds that

(13)
${\mathbb{E}}\left[C^{\prime}_{t+1}{|}Q(t)\right]\geq\left(1-\frac{4\zeta}{n}\right)C^{\prime}_{t}.$

Indeed, if $C_{t}\leq Dn$ then
$C^{\prime}_{t+1}=Dn=C^{\prime}_{t}\geq\left(1-\frac{20}{\zeta
n}\right)C^{\prime}_{t}$. Otherwise $C_{t}>Dn$, implying
$C^{\prime}_{t}=C_{t}$. In this case

$\displaystyle{\mathbb{E}}\left[C^{\prime}_{t+1}{|}Q(t)\right]\geq{\mathbb{E}}\left[C_{t+1}{|}Q(t)\right]\stackrel{{\scriptstyle\eqref{eq:absorber
one step
change}}}{{\geq}}\left(1-\frac{4\zeta}{n}\right)C_{t}=\left(1-\frac{4\zeta}{n}\right)C^{\prime}_{t}.$

Now define, for $T_{R}\leq t<T$:

${\tilde{C}}_{t}=\frac{C^{\prime}_{t+1}}{C^{\prime}_{t}}.$

We note that

$C^{\prime}_{T}=C^{\prime}_{T_{R}}\times{\tilde{C}}_{T_{R}}\times{\tilde{C}}_{T_{R}+1}\times\ldots\times{\tilde{C}}_{T-1}.$

Thus

$\log(C^{\prime}_{T})=\log(C^{\prime}_{T_{R}})+\log({\tilde{C}}_{T_{R}})+\log({\tilde{C}}_{T_{R}+1})+\ldots+\log({\tilde{C}}_{T-1}).$

It holds that

$\displaystyle{\mathbb{E}}\left[\log({\tilde{C}}_{t}){|}Q(t-1)\right]$
$\displaystyle={\mathbb{E}}\left[\log\left(1+\frac{C^{\prime}_{t+1}-C^{\prime}_{t}}{C^{\prime}_{t}}\right){|}Q(t-1)\right]$
$\displaystyle\geq{\mathbb{E}}\left[\frac{C^{\prime}_{t+1}-C^{\prime}_{t}}{C^{\prime}_{t}}-O\left(\left(\frac{C^{\prime}_{t+1}-C^{\prime}_{t}}{C^{\prime}_{t}}\right)^{2}\right){|}Q(t-1)\right].$

By definition, $C^{\prime}_{t}=\Omega(n)$ and by (11)
$\left|C^{\prime}_{t+1}-C^{\prime}_{t}\right|=O(1)$. Therefore:

(14)
$\begin{split}{\mathbb{E}}\left[\log({\tilde{C}}_{t}){|}Q(t-1)\right]&\geq{\mathbb{E}}\left[\frac{C^{\prime}_{t+1}-C^{\prime}_{t}}{C^{\prime}_{t}}{|}Q(t-1)\right]-O\left(\frac{1}{n^{2}}\right)\\\
&\stackrel{{\scriptstyle\eqref{eq:Y expected
difference}}}{{\geq}}-\frac{4\zeta}{n}-O\left(\frac{1}{n^{2}}\right)\geq-\frac{5\zeta}{n}.\end{split}$

Finally, we define, for $T_{R}\leq t\leq T$:

${\tilde{Z}}_{t}=-\left(\log(C^{\prime}_{T_{R}})+\sum_{s=T_{R}}^{t-1}\left(\log({\tilde{C}}_{s})+\frac{5\zeta}{n}\right)\right).$

By (14), the sequence $\\{{\tilde{Z}}_{t}\\}_{t=T_{R}}^{T}$ is a
supermartingale. Additionally, for every $T_{R}\leq t<T$:

$\displaystyle\left|{\tilde{Z}}_{t+1}-{\tilde{Z}}_{t}\right|$
$\displaystyle\leq\left|\log({\tilde{C}}_{t})\right|+\frac{5\zeta}{n}=\left|\log\left(1+\frac{C^{\prime}_{t+1}-C^{\prime}_{t}}{C^{\prime}_{t}}\right)\right|+O\left(\frac{1}{n}\right)$
$\displaystyle=\left|\log\left(1-O\left(\frac{1}{n}\right)\right)\right|+O\left(\frac{1}{n}\right)=O\left(\frac{1}{n}\right).$

Hence, by Theorem 5.11 (the Azuma-Hoeffding inequality):

${\mathbb{P}}\left[{\tilde{Z}}_{T}>{\tilde{Z}}_{T_{R}}+10\zeta\right]=\exp\left(-\Omega(n)\right).$

Rewriting the inequality for $e^{-{\tilde{Z}}_{T}}$ in place of
${\tilde{Z}}_{T}$ we obtain:

${\mathbb{P}}\left[e^{-{\tilde{Z}}_{T}}<\frac{C^{\prime}_{T_{R}}}{e^{10\zeta}}\right]=\exp\left(-\Omega(n)\right).$

It holds that

$\displaystyle\log(C^{\prime}_{T})=\log(C^{\prime}_{T_{R}})+\sum_{t=T_{R}}^{T-1}\log({\tilde{C}}_{t})=-{\tilde{Z}}_{T}-\sum_{t=T_{R}}^{T-1}\frac{5\zeta}{n}\geq-{\tilde{Z}}_{T}-5\zeta.$

Thus:

$C^{\prime}_{T}\geq\frac{e^{-{\tilde{Z}}_{T}}}{e^{5\zeta}}.$

Therefore:

${\mathbb{P}}\left[C^{\prime}_{T}<\frac{C^{\prime}_{T_{R}}}{e^{15\zeta}}\right]\leq{\mathbb{P}}\left[e^{-{\tilde{Z}}_{T}}<\frac{C^{\prime}_{T_{R}}}{e^{10\zeta}}\right]=\exp\left(-\Omega(n)\right).$

Now, the events $C^{\prime}_{T}\geq C^{\prime}_{T_{R}}e^{-15\zeta}\geq Dn$ and
$\tau=\infty$ imply that $|{\mathcal{C}}_{T}|=C^{\prime}_{T}\geq Dn$.
Therefore,

${\mathbb{P}}\left[|{\mathcal{C}}_{T}|<Dn\right]\leq{\mathbb{P}}[\tau<\infty]+{\mathbb{P}}\left[C^{\prime}_{T}<\frac{C^{\prime}_{T_{R}}}{e^{15\zeta}}\right]\stackrel{{\scriptstyle\text{Proposition
\ref{prop:tau inf whp}}}}{{=}}\exp\left(-\Omega\left(n^{0.75}\right)\right),$

proving the claim. ∎

###  5.3. Proof of the lower bound

We are ready to prove the lower bound in Theorem 2.11. Recalling the
definition of the queenon $\delta$, it holds that
$B_{n}(\delta,\varepsilon/2)\subseteq B_{n}(\gamma,\varepsilon)$. Let $B$ be
the set of $n$-queens configurations $q$ such that for every $\alpha\in I_{N}$
it holds that $|\alpha_{n}\cap q|=\delta(\alpha)n\pm 2\varepsilon^{5}n$ (where
$N$ is the constant used to define $\delta$). By Claim 2.16 $B\subseteq
B_{n}(\delta,\varepsilon/2)$.

We now show that Algorithm 5.2 followed by Algorithm 5.3 is likely to produce
an element of $B$. Let ${\mathcal{F}}$ be the event that

  1. (a)

Algorithm 5.2 does not abort,

  2. (b)

$Q(T)$ is $\Omega(n)$-absorbing, and

  3. (c)

for every $\alpha\in I_{N}$,
$|Q(T)\cap\alpha_{n}|=\delta(\alpha)n\pm\varepsilon^{5}n$.

By Proposition 5.7, Claim 5.16, and Claim 5.29 we have
${\mathbb{P}}[{\mathcal{F}}]=1-\exp\left(\Omega\left(n^{-0.75}\right)\right)$.
Let $B^{\prime}$ be the set of size $T$ partial $n$-queens configurations
satisfying (b) and (c). If ${\mathcal{F}}$ holds then
$(X_{1},X_{2},\ldots,X_{T})$ is an ordered element of $B^{\prime}$. Thus
$H(X_{1},X_{2},\ldots,X_{T}{|}{\mathcal{F}})\leq\log|B^{\prime}|+\log(T!)$.
Additionally, by the law of total probability:

$\displaystyle H(X_{1},X_{2},\ldots,X_{T}{|}{\mathcal{F}})$
$\displaystyle=\frac{H(X_{1},\ldots,X_{T})-H(X_{1},X_{2},\ldots,X_{T}{|}{\mathcal{F}}^{c})(1-{\mathbb{P}}[{\mathcal{F}}])}{{\mathbb{P}}[{\mathcal{F}}]}$
$\displaystyle\stackrel{{\scriptstyle\text{Lemma \ref{lem:random phase
entropy}}}}{{=}}n(H_{q}^{M}(\delta)+2\log n-1)\pm 2n^{1-1/K^{3}}.$

Therefore, recalling that $T=n(1-O(n^{-1/K^{2}}))$:

$|B^{\prime}|\geq\frac{1}{T!}\left(\left(1-{o\left(1\right)}\right)\frac{n^{2}e^{H_{q}^{M}(\delta)}}{e}\right)^{n}=\left(\left(1-{o\left(1\right)}\right)ne^{H_{q}(\delta)}\right)^{n},$

where the last equality follows from Stirling’s approximation and Lemma 2.18.
Let $q^{\prime}\in B^{\prime}$. By Lemma 5.20 if Algorithm 5.3 is begun from
$q^{\prime}$ the result is an $n$-queens configuration $q$ satisfying
$|q\Delta q^{\prime}|\leq 3(n-T)$. We now show that $q\in B$.

######  Claim 5.30.

Let $q^{\prime}\in B^{\prime}$ and suppose that $q$ is an $n$-queens
configuration satisfying $|q\Delta q^{\prime}|\leq 3(n-T)$. Then $q\in B$.

###### Proof.

We need to show that for every $\alpha\in I_{N}$ it holds that
$|\alpha_{n}\cap q|=\delta(\alpha)\pm 2\varepsilon^{5}n$. Let $\alpha\in
I_{N}$. Then:

$\displaystyle|\alpha_{n}\cap q|$ $\displaystyle=|\alpha_{n}\cap
q^{\prime}|\pm|q\Delta q^{\prime}|\stackrel{{\scriptstyle q^{\prime}\in
B^{\prime}}}{{=}}\delta(\alpha)n\pm\left(\varepsilon^{5}n+3(n-T)\right)$
$\displaystyle=\delta(\alpha)n\pm\left(\varepsilon^{5}+O\left(n^{-1/K^{2}}\right)\right)n=\delta(\alpha)n\pm
2\varepsilon^{5}n,$

as desired. ∎

We now consider the number of ways a given $n$-queens configuration may be
obtained as a result of running Algorithm 5.3.

######  Claim 5.31.

Let $q$ be an $n$-queens configuration. There are at most $n^{2(n-T)}$ partial
configurations $q^{\prime}\in B^{\prime}$ such that $q$ can be obtained by
beginning Algorithm 5.3 from $q^{\prime}$.

###### Proof.

At each step of Algorithm 5.3 two queens are added to the board and one is
removed. Consider the number of ways to reverse this process, beginning from
$q$. At each step we must remove two queens $(a,b)$ and $(c,d)$ from the board
and add either $(a,d)$ or $(c,b)$. Since there are always at most $n$ queens
on the board there are $\leq\binom{n}{2}$ choices for the queens to remove.
There are then at most $2$ choices which queen to add. Since there are $n-T$
steps in Algorithm 5.3 there are at most $\left(\binom{n}{2}2\right)^{n-T}\leq
n^{2(n-T)}$ ways to reverse it. ∎

Since Algorithm 5.3 maps every element of $B^{\prime}$ to an element of $B$,
and every element of $B$ can be obtained in this manner from at most
$n^{2(n-T)}$ elements of $B^{\prime}$ we conclude:

$|B_{n}(\gamma,\varepsilon)|\geq|B|\geq\frac{|B^{\prime}|}{n^{2(n-T)}}\geq\left(\left(1-{o\left(1\right)}\right)ne^{H_{q}(\delta)}\right)^{n}.$

Therefore:

$\liminf_{n\to\infty}\frac{|B_{n}(\gamma,\varepsilon)|^{1/n}}{n}\geq
e^{H_{q}(\delta)}.$

Now, by definition of $\delta$: $H_{q}(\delta)>(1-\varepsilon)H_{q}(\gamma)$.
This proves the lower bound in Theorem 2.11.

##  6\. Explicit bounds on $H_{q}(\gamma^{*})$

######  Remark 6.1.

This section relies on numerical calculations. Code verifying the calculations
can be obtained by downloading the source of this arXiv submission.

In this section we prove Claim 2.22. We begin with the lower bound.

######  Claim 6.2.

$H_{q}(\gamma^{*})\geq-{1.9449}$.

###### Proof.

It suffices to exhibit an explicit queenon $\gamma$ such that
$H_{q}(\gamma)\geq-{1.9449}$. Define the $12\times 12$ matrix

$A=\frac{1}{100}\setcounter{MaxMatrixCols}{12}\begin{bmatrix}59&76&95&113&125&132&132&125&113&95&76&59\\\
76&87&99&108&114&116&116&114&108&99&87&76\\\
95&99&100&102&102&102&102&102&102&100&99&95\\\
113&108&102&94&92&91&91&92&94&102&108&113\\\
125&114&102&92&85&82&82&85&92&102&114&125\\\
132&116&102&91&82&77&77&82&91&102&116&132\\\
132&116&102&91&82&77&77&82&91&102&116&132\\\
125&114&102&92&85&82&82&85&92&102&114&125\\\
113&108&102&94&92&91&91&92&94&102&108&113\\\
95&99&100&102&102&102&102&102&102&100&99&95\\\
76&87&99&108&114&116&116&114&108&99&87&76\\\
59&76&95&113&125&132&132&125&113&95&76&59\end{bmatrix}.$

The sum of each row and column of $A$ is $12$. Additionally, every diagonal in
$A$ has sum $\leq 12$. (These assertions can be verified with the provided
code.) Let $\gamma$ be the $12$-step queenon whose density function has
constant value $A_{i,j}$ on the square $\sigma_{i,j}^{12}$, for $i,j\in[12]$.
It remains to verify that $H_{q}(\gamma)>-{1.9449}$, for which the reader is
invited to use the provided code. ∎

Figure 4. The division of ${[-1/2,1/2]}^{2}$ into $K_{N}$, for $N=5$.

We turn to the upper bound. One difficulty in bounding $H_{q}$ from above is
that its domain is infinite dimensional. Hence we seek a finite dimensional
approximation of $H_{q}$ that bounds it from above. We take the following
approach: Let $N\in\mathbb{N}$. Let $K=K_{N}$ be the minimal mutual refinement
of $I_{N}$ and $\\{\sigma_{i,j}^{N}\\}_{i,j\in[N]}$ (see Figure 4). For
$\gamma\in{\Gamma}$ let $\gamma_{N}$ be the measure on ${[-1/2,1/2]}^{2}$ that
has constant density on every $\alpha\in K$ and satisfies
$\gamma_{N}(\alpha)=\gamma(\alpha)$. We do not claim that $\gamma_{N}$ is
necessarily a queenon or even a permuton. However, it is the case that for
every $i\in[N]$ there holds

$\sum_{j=1}^{N}\gamma_{N}(\sigma_{i,j}^{N})=\sum_{j=1}^{N}\gamma_{N}(\sigma_{j,i}^{N})=\frac{1}{N}$

(i.e., if we partition ${[-1/2,1/2]}^{2}$ into axis-parallel strips of width
$1/N$ then $\gamma_{N}$ induces the uniform distribution both vertically and
horizontally). Additionally, for every $\alpha\in J_{N}$ there holds:

$\gamma_{N}^{+}(\alpha)=\gamma^{+}(\alpha)\leq
1/N,\quad\gamma_{N}^{-}(\alpha)=\gamma^{-}(\alpha)\leq 1/N.$

Thus, we may define the distributions ${\overline{{\gamma_{N}}}^{+}}$ and
${\overline{{\gamma_{N}}}^{-}}$ on $J_{N}$ in the natural way by setting
${\overline{{\gamma_{N}}}^{+}}(\alpha)=1/N-\gamma_{N}^{+}(\alpha)$ and
${\overline{{\gamma_{N}}}^{-}}(\alpha)=1/N-\gamma_{N}^{-}(\alpha)$. By
concavity, for every $\gamma\in{\Gamma}$:

$-D_{KL}(\gamma)\leq-D_{KL}(\gamma_{N})=-\sum_{\alpha\in
K}\gamma_{N}(\alpha)\log\left(\gamma_{N}(\alpha)\right)-2\log(2N)$

and for $*\in\\{+,-\\}$:

$-D_{KL}(\overline{\gamma}^{*})\leq-D(\overline{\gamma_{N}}^{*})=-\sum_{\alpha\in
J_{N}}\overline{\gamma_{N}}^{*}(\alpha)\log\left(\overline{\gamma_{N}}^{*}(\alpha)\right)-\log(2N).$

We now reformulate the problem as entropy maximization. This will allow us to
bound $H_{q}(\gamma^{*})$ using the Lagrangian dual function. Let $J_{N}^{1}$
and $J_{N}^{2}$ be two disjoint copies of $J_{N}$. Let
$\Omega=\Omega_{N}\coloneqq K_{N}\cup J_{N}^{1}\cup J_{N}^{2}$. Let
${\mathcal{D}}={\mathcal{D}}_{N}\coloneqq(0,1/N)^{\Omega_{N}}$. Define the
function $f=f_{N}:{\mathcal{D}}_{N}\to\mathbb{R}$ by:

$f(x)=-\sum_{\alpha\in\Omega}x_{\alpha}\log(x_{\alpha})-4\log(2N)+2\log(2)-3.$

As observed, by concavity,
$f(\gamma_{N},{\overline{{\gamma_{N}}}^{+}},{\overline{{\gamma_{N}}}^{-}})\geq
H_{q}(\gamma)$ for every $\gamma\in{\Gamma}$.

To facilitate matrix notation we fix an identification of $\Omega$ with
$[|\Omega|]$. For $x\in{\mathcal{D}}$ we write
$x=(\gamma_{x},\gamma_{1,x},\gamma_{2,x})$ when we wish to access the three
measures that comprise $x$. Let $A$ be the $6N\times|\Omega|$ matrix and
$b\in\mathbb{R}^{6N}$ such that $Ax=b$ if and only if $x\in{\mathcal{D}}$
satisfies the linear equations

(15) $\begin{split}&\forall
i\in[N],\sum_{j=1}^{N}\gamma_{x}(\sigma_{i,j}^{N})=\sum_{j=1}^{N}\gamma_{x}(\sigma_{j,i}^{N})=\frac{1}{N},\\\
&\forall\alpha\in
J_{N}^{1},\gamma_{1,x}(\alpha)=\frac{1}{N}-\gamma_{x}^{+}(\alpha),\\\
&\forall\alpha\in
J_{N}^{2},\gamma_{2,x}(\alpha)=\frac{1}{N}-\gamma_{x}^{-}(\alpha).\end{split}$

Note that for every $\gamma\in{\Gamma}$,
$(\gamma_{N},{\overline{{\gamma_{N}}}^{+}},{\overline{{\gamma_{N}}}^{-}})$
satisfies (15). Therefore the following concave optimization problem bounds
$H_{q}(\gamma^{*})$ from above:

$\displaystyle\underset{x\in{\mathcal{D}}}{\text{maximize}}$ $\displaystyle
f(x)$ subject to: $\displaystyle Ax=b.$

We define the Lagrangian dual function
$\mathcal{L}:\mathbb{R}^{6N}\to\mathbb{R}$ by:

$\mathcal{L}(y)=\sup_{x\in{\mathcal{D}}}\left(f(x)+y^{T}(Ax-b)\right).$

Then, by definition, for every $y\in\mathbb{R}^{6N}$ there holds
$\mathcal{L}(y)\geq f(\gamma^{*}_{N})\geq H_{q}(\gamma^{*})$.

The next claim provides an explicit form for $\mathcal{L}(y)$ for a large
range of $y$. We denote the length-$4N^{2}$ all $1$s row vector by
$\mathbbm{1}_{4N^{2}}$.

######  Claim 6.3.

Let $N\in\mathbb{N}$ and let $y\in\mathbb{R}^{6N}$ satisfy
$y^{T}A-\mathbbm{1}_{4N^{2}}\leq-\log(N)\mathbbm{1}_{4N^{2}}$. Define
$\tilde{x}\in{\mathcal{D}}$ by $\tilde{x}_{\alpha}=\exp((y^{T}A)_{\alpha}-1)$.
Then $\mathcal{L}(y)=f(\tilde{x})+y^{T}(A\tilde{x}-b)$.

###### Proof.

We observe that if $y$ is fixed then $g(x)\coloneqq f(x)+y^{T}(Ax-b)$ is
strictly concave on ${\mathcal{D}}$. Therefore it suffices to show that
$\nabla g(\tilde{x})=0$. Indeed, for every $\alpha\in\Omega$ we have
$\frac{\partial g}{\partial
x_{\alpha}}(x)=-\log(x_{\alpha})-1+(y^{T}A)_{\alpha}$. By definition of
$\tilde{x}$ this is zero when $x=\tilde{x}$. ∎

We are ready to prove the upper bound.

######  Claim 6.4.

$H_{q}(\gamma^{*})<-{1.94}$.

###### Proof.

Set $N=17$. It suffices to exhibit some $y\in\mathbb{R}^{6N}$ satisfying
$\mathcal{L}(y)<-{1.94}$. For this we rely on Claim 6.3 and computer
calculation. The provided code contains a function that, given
$y\in\mathbb{R}^{6N}$ satisfying the conditions of Claim 6.3, calculates
$\mathcal{L}(y)$. The same file also contains an explicit vector $y$
satisfying these conditions and verifies that for this $y$,
$\mathcal{L}(y)<-{1.94}$. ∎

##  7\. Concluding remarks

  * •

This paper combined the entropy method and a randomized algorithm to determine
the first and second order terms of $\log({\mathcal{Q}}(n))$. We wonder
whether similar methods might succeed in obtaining more accurate estimates.
More generally, for many classes of combinatorial designs (such as Steiner
systems [15, 11] and high-dimensional permutations [16, 12]), denoting by
$X(n)$ the number of order-$n$ objects, the first and second order terms of
$\log(X(n))$ have been determined using similar methods. It would be very
interesting to improve these estimates.

  * •

The lower bounds for the number of Steiner systems and high-dimensional
permutations were obtained using a random greedy algorithm to construct an
approximate design. In contrast, the lower bound in our paper uses a more
sophisticated algorithm. There is, of course, a very natural random greedy
algorithm for the $n$-queens problem: beginning with an empty board, in each
step add a queen to a position chosen uniformly at random from the available
positions. As mentioned in the introduction, the asymmetry of the constraints
makes this algorithm challenging to analyze. However, based on simulations, it
is clear that this algorithm succeeds in placing almost $n$ queens and,
furthermore, Algorithm 5.3 successfuly completes the outcome. It is therefore
worth asking if the lower bound on ${\mathcal{Q}}(n)$ could conceivably be
proved by a successful analysis of this algorithm. Although we cannot prove
this, we believe this is not the case: Empirically, the outcomes of the random
greedy algorithm do not approximate $\gamma^{*}$. This implies that they are
contained in an atypical (and hence small) subset of the configurations.

  * •

Let $X_{n}$ be the random variable equal to the number of pairs of $1$s
sharing a diagonal in a uniformly random order-$n$ permutation matrix. This
paper can be interpreted as studying ${\mathbb{P}}[X_{n}=0]$. It would be
interesting to understand the tails of $X_{n}$ more generally. For certain
permutation parameters (most prominently “pattern density” [13]) large
deviations can be understood with the theory of permutons. However, $X_{n}$ is
not continuous in the permuton topology. This suggests additional tools must
be developed.

  * •

The $n$-queens problem has many variations. Perhaps the best-known is the
toroidal or modular problem, in which the diagonals wrap around the board. Let
$T(n)$ be the number of toroidal $n$-queens configurations. Pólya proved that
$T(n)>0$ if and only if $\gcd(n,6)=1$ [21]. Using the entropy method, Luria
showed that $T(n)\leq\left((1+{o\left(1\right)})n/e^{3}\right)^{n}$ [18]. It
is not difficult to show that the natural random greedy algorithm for
constructing a toroidal $n$-queens configuration w.h.p. succeeds in placing
$n-o(n)$ queens on the board (indeed, this is the source of the lower bound on
${\mathcal{Q}}(n)$ in [19]). Furthermore, if the outcome of the process can
w.h.p. be completed this would imply that
$T(n)\geq\left((1-{o\left(1\right)})n/e^{3}\right)^{n}$. Unfortunately, the
absorption method in this paper takes advantage of the fact that in a complete
non-toroidal configuration only a fraction of the diagonals are occupied. This
is not the case in the toroidal problem. We wonder if the methods of
randomized algebraic construction [10] or iterative absorption [8] might be
more appropriate.

It is also worth mentioning the toroidal semi-queens variant, in which queens
attack along rows, columns, and modular plus-diagonals (but not minus-
diagonals). Remarkably, an asymptotic formula for the number of such
configurations was found using tools from analytic number theory [5]. Perhaps
this is the toolbox required to understand $T(n)$.

## Acknowledgements

I wish to thank Zur Luria for bringing the problem to my attention and for
fascinating discussions.

## References

  * [1] Jordan Bell and Brett Stevens, _A survey of known results and research areas for n-queens_ , Discrete Mathematics 309 (2009), no. 1, 1–31.
  * [2] Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Yuichi Yoshida, _Ordered Graph Limits and Their Applications_ , 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) (Dagstuhl, Germany) (James R. Lee, ed.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 185, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021, pp. 42:1–42:20.
  * [3] Vladimir I Bogachev, _Measure theory_ , vol. 1, Springer Science & Business Media, 2007.
  * [4] Jacob W Cooper, Daniel Kral, Ander Lamaison, and Samuel Mohr, _Quasirandom Latin squares_ , arXiv preprint arXiv:2011.07572 (2020).
  * [5] Sean Eberhard, Freddie Manners, and Rudi Mrazović, _Additive triples of bijections, or the toroidal semiqueens problem_ , Journal of the European Mathematical Society 21 (2018), no. 2, 441–463.
  * [6] Frederik Garbe, Robert Hancock, Jan Hladkỳ, and Maryam Sharifzadeh, _Limits of Latin squares_ , arXiv preprint arXiv:2010.07854 (2020).
  * [7] Roman Glebov, Andrzej Grzesik, Tereza Klimošová, and Daniel Král’, _Finitely forcible graphons and permutons_ , Journal of Combinatorial Theory, Series B 110 (2015), 112–135.
  * [8] Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus, _The existence of designs via iterative absorption: hypergraph $F$-designs for arbitrary $F$_, arXiv preprint arXiv:1611.06827 (2016).
  * [9] Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, Balázs Ráth, and Rudini Menezes Sampaio, _Limits of permutation sequences_ , Journal of Combinatorial Theory, Series B 103 (2013), no. 1, 93–113.
  * [10] Peter Keevash, _The existence of designs_ , arXiv preprint arXiv:1401.3665 (2014).
  * [11] by same author, _Counting designs_ , Journal of the European Mathematical Society 20 (2018), no. 4, 903–927.
  * [12] by same author, _The existence of designs II_ , arXiv preprint arXiv:1802.05900 (2018).
  * [13] Richard Kenyon, Daniel Král’, Charles Radin, and Peter Winkler, _Permutations with fixed pattern densities_ , Random Structures & Algorithms 56 (2020), no. 1, 220–250.
  * [14] Daniel Král’ and Oleg Pikhurko, _Quasirandom permutations are characterized by 4-point densities_ , Geometric and Functional Analysis 23 (2013), no. 2, 570–579.
  * [15] Nathan Linial and Zur Luria, _An upper bound on the number of Steiner triple systems_ , Random Structures & Algorithms 43 (2013), no. 4, 399–406.
  * [16] by same author, _An upper bound on the number of high-dimensional permutations_ , Combinatorica 34 (2014), no. 4, 471–486.
  * [17] László Lovász, _Large networks and graph limits_ , vol. 60, American Mathematical Soc., 2012.
  * [18] Zur Luria, _New bounds on the number of n-queens configurations_ , arXiv preprint arXiv:1705.05225 (2017).
  * [19] Zur Luria and Michael Simkin, _A lower bound for the $n$-queens problem_, arXiv preprint arXiv:2105.11431v2 (2021).
  * [20] Kalyanapuram Rangachari Parthasarathy, _Probability measures on metric spaces_ , vol. 352, American Mathematical Soc., 2005.
  * [21] George Pólya, _Uber die “doppelt-periodischen” lösungen des n-damen-problems_ , W. Ahrens, Mathematische Unterhaltungen und Spiele 1 (1921), 364–374.
  * [22] Jaikumar Radhakrishnan, _An entropy proof of Bregman’s theorem_ , Journal of combinatorial theory, Series A 77 (1997), no. 1, 161–164.
  * [23] Igor Rivin, Ilan Vardi, and Paul Zimmermann, _The n-queens problem_ , The American Mathematical Monthly 101 (1994), no. 7, 629–639.
  * [24] Vojtěch Rödl, _On a packing and covering problem_ , European Journal of Combinatorics 6 (1985), no. 1, 69–78.
  * [25] Neil J. A. Sloane and The OEIS Foundation Inc., _The on-line encyclopedia of integer sequences_ , 2020.
  * [26] Joel Spencer, _Asymptotic packing via a branching process_ , Random Structures & Algorithms 7 (1995), no. 2, 167–172.
  * [27] Lutz Warnke, _On the method of typical bounded differences_ , Combinatorics, Probability and Computing 25 (2016), no. 2, 269–299.
  * [28] Nicholas C Wormald, _Differential equations for random processes and random graphs_ , The annals of applied probability 5 (1995), no. 4, 1217–1235.
  * [29] by same author, _The differential equation method for random graph processes and greedy algorithms_ , Lectures on approximation and randomized algorithms 73 (1999), 155.
  * [30] Cheng Zhang and Jianpeng Ma, _Counting solutions for the $N$-queens and Latin-square problems by Monte Carlo simulations_, Physical Review E 79 (2009), no. 1, 016703.