# The number of $n$-queens configurations

Michael Simkin  Harvard University Center of Mathematical Sciences and
Applications, Cambridge, MA, USA<EMAIL_ADDRESS>
###### Abstract.

The $n$-queens problem is to determine $\mathcal{Q}(n)$, the number of ways to
place $n$ mutually non-threatening queens on an $n\times n$ board. We show
that there exists a constant $\alpha=1.942\pm 3\times 10^{-3}$ such that
$\mathcal{Q}(n)=((1\pm o(1)ne^{-\alpha})^{n}$. The constant $\alpha$ is
characterized as the solution to a convex optimization problem in
$\mathcal{P}([-1/2,1/2]^{2})$, the space of Borel probability measures on the
square.

The chief innovation is the introduction of limit objects for $n$-queens
configurations, which we call queenons. These are a convex set in
$\mathcal{P}([-1/2,1/2]^{2})$. We define an entropy function that counts the
number of $n$-queens configurations that approximate a given queenon. The
upper bound uses the entropy method. For the lower bound we describe a
randomized algorithm that constructs a configuration near a prespecified
queenon and whose entropy matches that found in the upper bound. The
enumeration of $n$-queens configurations is then obtained by maximizing the
(concave) entropy function in the space of queenons.

Along the way we prove a large deviations principle for $n$-queens
configurations that can be used to study their typical structure.

##  1\. Introduction

An $n$-queens configuration is a placement of $n$ mutually non-threatening
queens on an $n\times n$ chessboard. As queens attack along rows, columns, and
diagonals, this is equivalent to an order-$n$ permutation matrix in which each
diagonal contains at most one $1$. The $n$-queens problem is to determine
${\mathcal{Q}}(n)$, the number of such configurations. In this paper we prove
the following result on the asymptotics of ${\mathcal{Q}}(n)$.

######  Theorem 1.1.

There exists a constant ${1.94}<\alpha<{1.9449}$ such that

$\lim_{n\to\infty}\frac{{\mathcal{Q}}(n)^{1/n}}{n}=e^{-\alpha}.$

Previously, the best known bounds were

$e^{-1.58}>\limsup_{n\to\infty}\frac{{\mathcal{Q}}(n)^{1/n}}{n}\geq\liminf_{n\to\infty}\frac{{\mathcal{Q}}(n)^{1/n}}{n}\geq
e^{-3},$

due to Luria [18] (upper bound) and Luria and the author [19] (lower bound).
Before these, the best upper bound was the trivial ${\mathcal{Q}}(n)\leq n!$
and the best lower bounds held only for infinite families of natural numbers
$n$ (cf. [23]), whereas the only bound for all $n$ was
${\mathcal{Q}}(n)=\Omega(1)$. We note, however, that [30], which is a physics
paper, used Monte Carlo simulations to empirically estimate
$\log\left(\frac{1}{n}{\mathcal{Q}}(n)^{1/n}\right)\approx-1.944000$.
Previously, Benoit Cloitre [25, Sequence A000170] conjectured that the limit
above is equal to a constant $\approx-1.940$. Theorem 1.1 justifies these
claims. For more on the history of the problem, as well as an extensive list
of open problems, we refer the reader to Bell and Stevens’s survey [1].

Our methods also allow us to study the typical structure of $n$-queens
configurations. To state the main result in this vein we introduce some
notation. Let ${\mathcal{R}}$ be the collection of subsets of the plane with
the form

$\left\\{(x,y)\in{[-1/2,1/2]}^{2}:a_{1}\leq x+y\leq b_{1},a_{2}\leq y-x\leq
b_{2}\right\\}$

for $a_{1},a_{2},b_{1},b_{2}\in[-1,1]$. (We use the square ${[-1/2,1/2]}^{2}$
rather than $[0,1]^{2}$ because it better respects the natural symmetries of
the problem.) Let $\gamma_{1},\gamma_{2}$ be two finite Borel measures on
${[-1/2,1/2]}^{2}$. We define the distance between $\gamma_{1}$ and
$\gamma_{2}$ by

${d_{\diamond}\left({\gamma_{1}},{\gamma_{2}}\right)}=\sup\left\\{\left|\gamma_{1}(\alpha)-\gamma_{2}(\alpha)\right|:\alpha\in{\mathcal{R}}\right\\}.$

Let $q$ be an $n$-queens configuration. Define the step function
$g_{q}:{[-1/2,1/2]}^{2}\to\mathbb{R}$ by $g_{q}\equiv n$ on every square
$[(i-1)/n-1/2,i/n-1/2]\times[(j-1)/n-1/2,j/n-1/2]$ such that $(i,j)\in q$ and
$g_{q}\equiv 0$ elsewhere. Let $\gamma_{q}$ be the probability measure with
density function $g_{q}$. Our main structural result is the following.

Figure 1. The density function of $\gamma^{*}$. This is the distribution of
queens in a typical $n$-queens configuration.

######  Theorem 1.2.

There exists a Borel probability measure $\gamma^{*}$ on ${[-1/2,1/2]}^{2}$
such that the following holds: Let $\varepsilon>0$ be fixed and let $q$ be a
uniformly random $n$-queens configuration. W.h.p.111We say that a sequence of
events parametrized by $n$ occurs with high probability (w.h.p.) if the
probability of its occurence tends to $1$ as $n\to\infty$.
${d_{\diamond}\left({\gamma_{q}},{\gamma^{*}}\right)}<\varepsilon$.

Both the constant $\alpha$ from Theorem 1.1 and the measure $\gamma^{*}$ are
characterized as the solution to a concave optimization problem defined in
Section 2. For a visualization of $\gamma^{*}$ see Figure 1.

###  1.1. Designs, entropy, and randomized algorithms

We view $n$-queens configurations as an example of combinatorial design. In
recent years there have been several breakthroughs relating to the
construction, enumeration, and analysis of designs. These include the
Radhakrishnan entropy method [22], extended by Linial and Luria [15, 16] to
give upper bounds on the number of designs; the Rödl nibble [24] and random
greedy algorithms [26], used to construct approximate designs; and completion
methods, such as randomized algebraic constructions [10] and iterative
absorption [8], used to complete approximate designs. We also mention the
emerging limit theory of combinatorial designs [6, 4] from which this paper
draws inspiration.

These methods are powerful enough to enumerate many classes of designs. In
particular, the combination of random greedy algorithms and completion [11]
often yields lower bounds that match the upper bounds obtained with the
entropy method. Nevertheless, the $n$-queens problem has remained challenging
for two reasons. The first is the asymmetry of the constraints: Since the
diagonals vary in lengths from $1$ to $n$, some board positions are more
“threatened” than others. This makes the analysis of nibble-style arguments
difficult. Additionally, the constraints are not regular: In a complete
configuration, some diagonals contain a queen and some do not. This creates
difficulties for the entropy method.

To overcome these challenges we define limit objects for $n$-queens
configurations, which we call queenons. We give their precise definition in
Section 2. For the current discussion it suffices to think of these as Borel
probability measures on ${[-1/2,1/2]}^{2}$. To count $n$-queens configurations
we take the following approach. Rather than attempting to estimate
${\mathcal{Q}}(n)$ directly, we fix a queenon $\gamma$, a parameter
$\varepsilon>0$ and set ourselves the easier task of estimating
$|B_{n}(\gamma,\varepsilon)|$, where $B_{n}(\gamma,\varepsilon)$ is the set of
$n$-queens configurations $q$ satisfying
${d_{\diamond}\left({\gamma_{q}},{\gamma}\right)}<\varepsilon$.

For the upper bound we use the entropy method: We choose $q\in
B_{n}(\gamma,\varepsilon)$ uniformly at random and reveal its queens in a
random order. The knowledge that $q$ is close to $\gamma$ allows us to obtain
tight bounds on the entropy of each step in this process, which in turn gives
a tight upper bound on $|B_{n}(\gamma,\varepsilon)|$ in terms of a “queenon
entropy” function $H_{q}$.

For the lower bound we design a randomized algorithm that constructs an
element of $B_{n}(\gamma,\varepsilon)$ by placing one queen at a time on the
board. The algorithm has the additional property that the entropy of each step
matches the entropy of the corresponding step in the upper bound. Very
roughly, in each step of the algorithm we first choose a small area of the
board according to the distribution $\gamma$. We then place a queen in a
uniformly random position from that area subject to the constraint that it
does not conflict with previously placed queens. We show that w.h.p. this
algorithm places $n-o(n)$ queens on the board and, furthermore, w.h.p. the
outcome of the algorithm is close to a complete configuration. Since the
entropy of this process matches the entropy in the upper bound we obtain a
matching lower bound on $|B_{n}(\gamma,\varepsilon)|$.

Notably, we do not use a simple random greedy algorithm for the lower bound.
Instead, we use queenons as a “bridge” between the entropy method on the one
side and a randomized construction on the other. Thus, the upper and lower
bounds are two sides of the same coin: each follows from estimating the
entropy of a process in which a configuration is constructed one queen at a
time.

After finding tight bounds for $|B_{n}(\gamma,\varepsilon)|$ we use a
compactness argument to reduce estimating ${\mathcal{Q}}(n)$ to maximizing the
(concave) entropy function $H_{q}$ over the (convex) space of queenons.

The rest of this paper is organized as follows. At the end of this section we
introduce notation. In Section 2 we define queenons and their entropy function
$H_{q}$. We state an enumeration theorem (Theorem 2.11) which we use to prove
a large deviations principle (Theorem 2.23). We then use Theorem 2.23 to prove
Theorem 1.2. In Section 3 we collect technical claims that are useful in the
proof. In Section 4 we prove the upper bound in Theorem 2.11 and we prove the
lower bound in Section 5. These two sections can be read independently of each
other. In Section 6 we bound the optimal value of $H_{q}$, which ultimately
implies Theorem 1.1. We close with a few comments and open problems in Section
7.

###  1.2. Notation

For $n\in\mathbb{N}$ we write $[n]=\\{1,2,\ldots,n\\}$. For $a,b\in\mathbb{R}$
we use $a\pm b$ to denote an unknown quantity in the interval $[a-|b|,a+|b|]$.

Let $n\in\mathbb{N}$. A row in $[n]^{2}$ is a set of the form
$\\{(1,y),(2,y),\ldots,(n,y)\\}$ and a column is a set of the form
$\\{(x,1),(x,2),\ldots,(x,n)\\}$. For $c\in\mathbb{Z}$, plus-diagonal $c$ is
the set $\\{(x,y)\in[n]^{2}:x+y=c\\}$ and minus-diagonal $c$ is the set
$\\{(x,y)\in[n]^{2}:y-x=c\\}$. The term “diagonal” refers to a diagonal of
either type.

A partial $n$-queens configuration is a set $Q\subseteq[n]^{2}$ containing at
most one element in each row, column, and diagonal. We say $(x,y)\in[n]^{2}$
is available in $Q$ if it does not share a row, column, or diagonal with any
element of $Q$. We denote the set of such positions by ${\mathcal{A}}_{Q}$.

Throughout the paper, unless stated otherwise, all asymptotics are as
$n\to\infty$ and other parameters fixed. In general, we will assume $n$ is
sufficiently large for asymptotic inequalities to hold. For example, we may
write $n^{2}>10n$ without explicitly requiring $n>10$.

###  1.3. Partitions of ${[-1/2,1/2]}^{2}$, $[n]^{2}$, and $[-1,1]$

Although $n$-queens configurations are discrete objects, in this paper we
consider their limits as analytic objects. The following notation is useful
when moving from the discrete set $[n]^{2}$ to the continuous set
${[-1/2,1/2]}^{2}$. Let $n\in\mathbb{N}$ and let $i,j\in[n]$. Define

$\sigma_{i,j}^{n}\coloneqq[-1/2+(i-1)/n,-1/2+i/n]\times[-1/2+(j-1)/n,-1/2+j/n].$

For $N\in\mathbb{N}$ let $I_{N}$ be the division of ${[-1/2,1/2]}^{2}$ into
squares and half-squares of the form

$\\{(x,y)\in{[-1/2,1/2]}^{2}:-1+\frac{i-1}{N}\leq
x+y\leq-1+\frac{i}{N},-1+\frac{j-1}{N}\leq y-x\leq-1+\frac{j}{N}\\}$

for $i,j\in[2N]$ (see Figure 2). Note that these sets are $\ell_{1}$-balls of
radius $1/(2N)$ (intersected with ${[-1/2,1/2]}^{2}$). We denote the squares
in $I_{N}$ by $S_{N}$ and the half-squares by $T_{N}$. For $\alpha\in I_{N}$
we write $|\alpha|$ for its area (so that $|\alpha|=1/(2N^{2})$ if $\alpha\in
S_{N}$ and $|\alpha|=1/(4N^{2})$ if $\alpha\in T_{N}$).

Figure 2. On the left, the division of ${[-1/2,1/2]}^{2}$ into $I_{N}$, for
$N=5$. The squares have area $1/(2N^{2})$ while the half-squares have area
$1/(4N^{2})$. On the right, the corresponding partition of $[n]^{2}$ into
$\\{\alpha_{n}\\}_{\alpha\in I_{N}}$, for $n=35$.

Let $n,N\in\mathbb{N}$. We partition $[n]^{2}$ into sets
$\\{\alpha_{n}\\}_{\alpha\in I_{N}}$ as follows: For each $(i,j)\in[n]^{2}$,
assign $(i,j)$ to the set $\alpha_{n}$ such that
$\alpha\cap\sigma_{i,j}^{n}\neq\emptyset$ and such that the center-point of
$\alpha$ is minimal in the lexicographic order. We observe that
$|\alpha_{n}|=|\alpha|n^{2}\pm 8\lceil n/N\rceil$ for every $\alpha\in I_{N}$.
We write $\alpha^{N}(i,j)$ for the element $\alpha\in I_{N}$ such that
$(i,j)\in\alpha_{n}$. Usually, $N$ will be clear from context in which case we
write $\alpha(i,j)$.

Let $(x,y)\in[n]^{2}$ and $\alpha\in I_{N}$. We write $L_{y,\alpha}^{r}$,
$L_{x,\alpha}^{c}$, $D_{x+y,\alpha}^{+}$, and $D_{y-x,\alpha}^{-}$ for the
number of positions in $\alpha_{n}$ and, respectively, row $y$, column $x$,
plus-diagonal $x+y$, and minus-diagonal $y-x$.

Let $J_{N}$ be the division of $[-1,1]$ into the intervals
$\\{[-1+(i-1)/N,-1+i/N]\\}_{1\leq i\leq 2N}$.

We remark that neither $I_{N}$ nor $\\{\sigma_{i,j}^{n}\\}_{i,j\in[n]}$ is a
partition of ${[-1/2,1/2]}^{2}$. However, they are partitions up to sets of
measure zero under all measures considered in the paper. Similarly, $J_{N}$ is
a partition of $[-1,1]$ up to sets of measure zero under all measures we
consider.

##  2\. Queenons

In this section we define queenons - the limits of $n$-queens configurations.
We also define an associated entropy function and prove basic properties of
these objects.

The limit theory of combinatorial objects is interesting in its own right
(see, for example, [17, 9, 2, 6]). Nevertheless, it is beyond our scope to
develop a comprehensive theory of queenons. Instead, we restrict ourselves to
statements needed for the proofs of Theorems 1.1 and 1.2.

###  2.1. Definitions and basic properties

Queens configurations are, in particular, permutation matrices. There is
already a well-developed limit theory for permutation matrices, in which the
limiting objects are called permutons [9, 14, 7, 13]. Let us recall their
definition.

######  Definition 2.1.

A permuton is a probability measure on ${[-1/2,1/2]}^{2}$ with uniform
marginals:

$\forall-1/2\leq a\leq b\leq
1,\gamma([a,b]\times{[-1/2,1/2]})=\gamma({[-1/2,1/2]}\times[a,b])=b-a.$

For $N\in\mathbb{N}$, a permuton $\gamma$ is an $N$-step permuton if for every
$i,j\in[N]$, $\gamma$ has constant density on $\sigma_{i,j}^{N}$. We call
$\gamma$ a step permuton if it is an $N$-step permuton for some $N$.

######  Remark 2.2.

In the definition above we follow [13]. There are other, equivalent
definitions.

Before defining queenons we recall that since ${[-1/2,1/2]}^{2}$ is a compact
metric space, the space ${\mathcal{P}}$ of Borel probability measures on
${[-1/2,1/2]}^{2}$ is compact and metrizable with respect to the weak topology
(cf. [20, Lemma 6.4]).

The characterization of $n$-queens configurations as permutation matrices in
which the sum of every diagonal is at most $1$ suggests the following
definitions.

######  Definition 2.3.

Let $\mu\in{\mathcal{P}}$. We say that $\mu$ has sub-uniform diagonal
marginals if for every $-1\leq a\leq b\leq 1$ it holds that

$\displaystyle\mu\left(\left\\{(x,y):a\leq x-y\leq
b\right\\}\cap{[-1/2,1/2]}^{2}\right)\leq b-a,$
$\displaystyle\mu\left(\left\\{(x,y):a\leq x+y\leq
b\right\\}\cap{[-1/2,1/2]}^{2}\right)\leq b-a.$

######  Definition 2.4.

Let $\tilde{{\Gamma}}\subseteq{\mathcal{P}}$ be the set of step permutons with
sub-uniform diagonal marginals. Let ${\Gamma}=\overline{\tilde{{\Gamma}}}$ be
its closure in the weak topology. We call the elements of ${\Gamma}$ queenons
and the elements of $\tilde{{\Gamma}}$ step queenons.

######  Observation 2.5.

Let $q\subseteq[n]^{2}$ be an $n$-queens configuration. Then
$\gamma_{q}\in\tilde{{\Gamma}}$ and, in particular, is a queenon.

######  Remark 2.6.

A corollary of the enumeration theorem below (Theorem 2.11) is that for every
$\gamma\in{\Gamma}$ there is a sequence of queens configurations
$\\{q_{n}\\}_{n\in\mathbb{N}}$ such that $\gamma_{q_{n}}\to\gamma$. This,
together with Observation 2.5, justifies the perspective of queenons as limits
of $n$-queens configurations.

######  Observation 2.7.

Every queenon has sub-uniform diagonal marginals.

###### Proof.

This follows immediately from the fact that the set of measures in
${\mathcal{P}}$ with sub-uniform diagonal marginals is closed in the weak
topology. ∎

Every queenon carries with it information about the distribution of queens in
the diagonals. This is encapsulated by the measures on $[-1,1]$ in the next
definition. We remind the reader that by Caratheodory’s extension theorem in
order to define a finite Borel measure on $[-1,1]$ it is enough to specify the
measures of closed intervals.

######  Definition 2.8.

For $\gamma\in{\mathcal{P}}$ we define the probability measures
$\gamma^{+},\gamma^{-}$ on $[-1,1]$ by

$\displaystyle\gamma^{+}([a,b])=\gamma\left(\left\\{(x,y)\in{[-1/2,1/2]}^{2}:a\leq
x+y\leq b\right\\}\right),$
$\displaystyle\gamma^{-}([a,b])=\gamma\left(\left\\{(x,y)\in{[-1/2,1/2]}^{2}:a\leq
y-x\leq b\right\\}\right).$

If $\gamma$ has sub-uniform diagonal marginals, for every $-1\leq a\leq b\leq
1$ it holds that $\gamma^{+}([a,b]),\gamma^{-}([a,b])\leq b-a$. Thus, we can
define the probability measures
${\overline{{\gamma}}^{+}},{\overline{{\gamma}}^{-}}$ on $[-1,1]$ by

$\displaystyle{\overline{{\gamma}}^{+}}([a,b])=b-a-\gamma^{+}([a,b]),$
$\displaystyle{\overline{{\gamma}}^{-}}([a,b])=b-a-\gamma^{-}([a,b]).$

We also define the following notation: Let $\gamma\in{\mathcal{P}}$, $N\in
I_{N}$, and $\alpha\in I_{N}$. There exists a unique $\beta\in J_{N}$ such
that $\gamma(\alpha)$ contributes to $\gamma^{+}(\beta)$. We define
$\gamma^{+}(\alpha)=\gamma^{+}(\beta)$. Similarly, we write
$\gamma^{-}(\alpha)$ for $\gamma^{-}(\beta)$, where $\beta$ is the unique
element of $J_{N}$ such that $\gamma(\alpha)$ contributes to
$\gamma^{-}(\beta)$.

We are ready to define the entropy of a queenon.

Let $\mathcal{U}_{\square}$ denote the uniform distribution on
${[-1/2,1/2]}^{2}$ and let ${\mathcal{U}}_{[-1,1]}$ denote the uniform
distribution on $[-1,1]$. We remind the reader that if $\mu$ is a probability
measure on ${[-1/2,1/2]}^{2}$ with density function $f$ then the
Kullback–Leibler (KL) divergence is defined by

$D_{KL}(\mu||{\mathcal{U}}_{\square})\coloneqq\int_{{[-1/2,1/2]}^{2}}f(x)\log(f(x))dx.$

We remark that this may be infinite. If $\mu$ does not have a density function
we define $D_{KL}(\mu||{\mathcal{U}}_{\square})=\infty$. The KL divergence of
a probability measure $\nu$ on ${[-1/2,1/2]}$ with density function $g$ is
denoted and defined by

$D_{KL}(\nu||{\mathcal{U}}_{[-1,1]})\coloneqq\int_{[-1,1]}g(x)\log(2g(x))dx.$

When it is clear from context if a measure $\rho$ is defined on
${[-1/2,1/2]}^{2}$ or on $[-1,1]$ we may write simply $D_{KL}(\rho)$ for the
KL divergence of $\rho$ with respect to the uniform distribution.

######  Definition 2.9.

Let $\gamma\in{\Gamma}$. We define its Q-entropy by

$H_{q}(\gamma)=-D_{KL}\left(\gamma||{\mathcal{U}}_{\square}\right)-D_{KL}({\overline{{\gamma}}^{+}}||{\mathcal{U}}_{[-1/2,1/2]})-D_{KL}({\overline{{\gamma}}^{-}}||{\mathcal{U}}_{[-1/2,1/2]})+2\log
2-3.$

We will use the following discrete approximations of $H_{q}$. For a finite
probability distribution $p_{1},\ldots,p_{n}$ we write
$D(\\{p_{i}\\}_{i=1,\ldots,n})=\sum_{i=1}^{n}p_{i}\log\left(np_{i}\right)$ for
its KL divergence with respect to the uniform distribution. Also, for
$N\in\mathbb{N}$ and $\gamma\in{\Gamma}$ we define

$D^{N}(\gamma)=\sum_{\alpha\in
I_{N}}\gamma(\alpha)\log\left(\frac{\gamma(\alpha)}{|\alpha|}\right)$

(recall that $|\alpha|$ is the area of $\alpha$).

######  Definition 2.10.

Let $N\in\mathbb{N}$ and let $\gamma\in{\Gamma}$. Then

$H_{q}^{N}(\gamma)\coloneqq-D^{N}(\gamma)-D\left(\\{{\overline{{\gamma}}^{+}}(\alpha)\\}_{\alpha\in
J_{N}}\right)-D\left(\\{{\overline{{\gamma}}^{-}}(\alpha)\\}_{\alpha\in
J_{N}}\right)+2\log 2-3.$

We are now in a position to state our enumeration theorem.

######  Theorem 2.11.

Let $\gamma\in{\Gamma}$. Then:

  * •

Upper bound: For all sufficiently small $\varepsilon>0$ there exists some
$\varepsilon^{-1/3}\leq N\in\mathbb{N}$ such that:

$\limsup_{n\to\infty}\frac{|B_{n}(\gamma,\varepsilon)|^{1/n}}{n}\leq\exp\left(H_{q}^{N}(\gamma)+\varepsilon^{1/200}\right).$

  * •

Lower bound: For every $\varepsilon>0$:

$\liminf_{n\to\infty}\frac{|B_{n}(\gamma,\varepsilon)|^{1/n}}{n}\geq\exp\left((1-\varepsilon)H_{q}(\gamma)\right).$

We prove the upper bound in Section 4 and the lower bound in Section 5.

######  Remark 2.12.

The asymmetry between the upper and lower bounds is due to the way we approach
each proof. In Lemma 2.18 we prove that for every $\gamma\in{\Gamma}$,
$\lim_{N\to\infty}H_{q}^{N}(\gamma)=H_{q}(\gamma)$. Together with Theorem 2.11
this implies the more symmetric statement

$e^{H_{q}(\gamma)}\leq\liminf_{\varepsilon\downarrow
0}\liminf_{n\to\infty}\frac{|B_{n}(\gamma,\varepsilon)|^{1/n}}{n}\leq\limsup_{\varepsilon\downarrow
0}\limsup_{n\to\infty}\frac{|B_{n}(\gamma,\varepsilon)|^{1/n}}{n}\leq
e^{H_{q}(\gamma)}$

which itself implies

$\lim_{\varepsilon\downarrow
0}\liminf_{n\to\infty}\frac{|B_{n}(\gamma,\varepsilon)|^{1/n}}{n}=\lim_{\varepsilon\downarrow
0}\limsup_{n\to\infty}\frac{|B_{n}(\gamma,\varepsilon)|^{1/n}}{n}=e^{H_{q}(\gamma)}.$

######  Example 2.13.

Let $\gamma$ be the uniform distribution on ${[-1/2,1/2]}^{2}$. We will show
that $H_{q}(\gamma)=-2$. This implies that
${\mathcal{Q}}(n)\geq((1-{o\left(1\right)})ne^{-2})^{n}$ (which already
improves on the previous best bound
${\mathcal{Q}}(n)\geq((1-{o\left(1\right)})ne^{-3})^{n}$ [19]).

Since $\gamma$ is uniform $D_{KL}(\gamma)=0$. By symmetry,
$D_{KL}({\overline{{\gamma}}^{+}})=D_{KL}({\overline{{\gamma}}^{-}})$. The
density function of $\gamma^{+}$ is $1-|c|$ (where $c$ varies from $-1$ to
$1$). Therefore the density function of ${\overline{{\gamma}}^{+}}$ is $|c|$.
Recall that the density function of the uniform distribution on $[-1,1]$ is
the constant function $1/2$. Therefore:

$D_{KL}({\overline{{\gamma}}^{+}})=\int_{-1}^{1}|c|\log(2|c|)dc=\log(2)-1/2.$

Consequently

$H_{q}(\gamma)=-D_{KL}(\gamma)-D_{KL}({\overline{{\gamma}}^{+}})-D_{KL}({\overline{{\gamma}}^{-}})+2\log
2-3=-2.$

The next claims summarize basic properties of queenons and ${d_{\diamond}}$.
We will rely on the following covering lemma. Recall the definition of
${\mathcal{R}}$ from the introduction. We say the width of a diagonal
$\\{(x,y):a\leq x+y\leq b\\}$ is $b-a$.

######  Lemma 2.14.

Let $\alpha\in{\mathcal{R}}$ and $N\in\mathbb{N}$. There exists a set
$X\subseteq I_{N}$ such that $\alpha\subseteq\cup_{\beta\in X}\beta$ and
$\left(\cup_{\beta\in X}\beta\right)\setminus\alpha$ is contained in four
diagonals, each of width $2/N$.

###### Proof.

By definition of ${\mathcal{R}}$ there exist
$a_{1},a_{2},b_{1},b_{2}\in[-1,1]$ such that

$\alpha=\\{(x,y)\in{[-1/2,1/2]}^{2}:a_{1}\leq x+y\leq b_{1},a_{2}\leq y-x\leq
b_{2}\\}.$

Let $X=\\{\beta\in I_{N}:\alpha\cap\beta\neq\emptyset\\}$. Then, by
definition, $\alpha\subseteq\cup_{\beta\in X}\beta$. Now, if
$\beta\cap\alpha\neq\emptyset$ but $\beta\nsubseteq\alpha$ then $\beta$
intersects one of the four lines $y=a_{1}-x,y=b_{1}-x,y=a_{2}+x,y=b_{2}+x$.
For each diagonal, the set of elements $\beta\in I_{N}$ intersecting it forms
a diagonal of width $\leq 2/N$, proving the lemma. ∎

######  Claim 2.15.

Let $\gamma_{1},\gamma_{2}\in{\Gamma}$, $N\in\mathbb{N}$, and $\varepsilon>0$.
Suppose that for every $\alpha\in I_{N}$ we have
$|\gamma_{1}(\alpha)-\gamma_{2}(\alpha)|<\varepsilon$. Then
${d_{\diamond}\left({\gamma_{1}},{\gamma_{2}}\right)}<8/N+4N^{2}\varepsilon$.

###### Proof.

Let $\alpha\in{\mathcal{R}}$. Let $X\subseteq I_{N}$ be a cover of $\alpha$ as
guaranteed by Lemma 2.14. Let $U=\cup_{\beta\in X}\beta$. Then, for $i=1,2$:

$\gamma_{i}(\alpha)=\gamma_{i}(U)-\gamma_{i}(U\setminus\alpha).$

Since $\gamma_{i}$ has sub-uniform diagonal marginals, by Lemma 2.14 we have
$\gamma_{i}(U\setminus\alpha)\leq 8/N$. Additionally, using the fact that
$|X|\leq|I_{N}|\leq 4N^{2}$:

$\gamma_{1}(U)=\sum_{\beta\in X}\gamma_{1}(\beta)=\sum_{\beta\in
X}\gamma_{2}(\beta)\pm|X|\varepsilon=\gamma_{2}(U)\pm 4N^{2}\varepsilon.$

Therefore:

$|\gamma_{1}(\alpha)-\gamma_{2}(\alpha)|\leq|\gamma_{1}(U)-\gamma_{2}(U)|+|\gamma_{1}(U\setminus\alpha)-\gamma_{2}(U\setminus\alpha)|\leq
4N^{2}\varepsilon+8/N.$

We conclude that ${d_{\diamond}\left({\gamma_{1}},{\gamma_{2}}\right)}\leq
4N^{2}\varepsilon+8/N$. ∎

######  Claim 2.16.

Let $\gamma\in{\Gamma}$, $N\in\mathbb{N}$, $\varepsilon>0$, and let $q$ be an
$n$-queens configuration satisfying

$\forall\alpha\in I_{N},|\alpha_{n}\cap Q|=(\gamma(\alpha)\pm\varepsilon)n.$

Then ${d_{\diamond}\left({\gamma_{q}},{\gamma}\right)}\leq
4N^{2}\left(\varepsilon+8/n\right)+8/N$.

###### Proof.

By Claim 2.15 it is enough to show that for every $\alpha\in I_{N}$,
$|\gamma_{q}(\alpha)-\gamma(\alpha)|\leq\varepsilon+8/n$. Let $\alpha\in
I_{N}$. Let $X$ be the set of queens $(i,j)\in q$ such that
$\sigma_{i,j}^{n}\subseteq\alpha$ and let $Y$ be the set of queens $(i,j)\in
q$ such that $\sigma_{i,j}^{n}\cap\alpha\neq\emptyset$. For every $(i,j)\in
Y\setminus X$, $\sigma_{i,j}^{n}$ intersects one of the four diagonals
defining $\alpha$. Since $q$ is a queens configuration, each diagonal line
intersects at most $2$ queens. Therefore $|Y\setminus X|\leq 8$. Observe that
$X\subseteq\alpha_{n}\cap q\subseteq Y\implies|X|\leq|\alpha_{n}\cap
q|\leq|Y|\leq|X|+8$. Similarly:

$|X|/n\leq\gamma_{q}(\alpha)\leq|Y|/n\leq(|X|+8)/n.$

Therefore $\gamma_{q}(\alpha)=(|\alpha_{n}\cap q|\pm
8)/n=\gamma(\alpha)\pm(\varepsilon+8/n)$, as desired. ∎

######  Claim 2.17.

$({\Gamma},{d_{\diamond}})$ is a convex, compact, metric space.

###### Proof.

We first remark that ${d_{\diamond}}$ is a metric on ${\mathcal{P}}$ (and, in
fact, on the space of all finite Borel measures on ${[-1/2,1/2]}^{2}$).
Symmetry and the triangle inequality clearly hold, so we need only prove that
for $\gamma_{1},\gamma_{2}\in{\mathcal{P}}$,
${d_{\diamond}\left({\gamma_{1}},{\gamma_{2}}\right)}=0\implies\gamma_{1}=\gamma_{2}$.
Since ${\mathcal{R}}$ is closed under finite intersections and generates the
Borel $\sigma$-algebra, this follows from [3, Lemma 1.9.4].

To see that ${\Gamma}$ is convex it is enough to observe that
$\tilde{{\Gamma}}$ is convex.

We have already mentioned that ${\Gamma}$, with the weak topology, is compact
and metrizable. Thus it suffices to show that sequential convergence in
$({\Gamma},{d_{\diamond}})$ is equivalent to weak sequential convergence. We
remark that convergence in $({\mathcal{P}},{d_{\diamond}})$ is stronger than
weak convergence. Their equivalence in $({\Gamma},{d_{\diamond}})$ is due to
the sub-uniform diagonal marginals property.

Let $\gamma,\gamma_{1},\gamma_{2},\ldots\in{\Gamma}$. First, suppose that
${d_{\diamond}\left({\gamma_{n}},{\gamma}\right)}\to 0$. Let $f\in
C({[-1/2,1/2]}^{2})$ and $\varepsilon>0$. Let $N\in\mathbb{N}$ be large enough
that for every $x,y\in{[-1/2,1/2]}^{2}$, if ${\lVert{x-y}\rVert}_{1}<1/N$ then
$|f(x)-f(y)|<\varepsilon$. Then, for every $n\geq N$:

$\displaystyle\left|\int fd\gamma_{n}-\int fd\gamma\right|$
$\displaystyle\leq\sum_{\alpha\in
I_{N}}\left|\int_{\alpha}fd\gamma_{n}-\int_{\alpha}fd\gamma\right|$
$\displaystyle\leq\sum_{\alpha\in
I_{N}}\left(\left|\gamma_{n}(\alpha)-\gamma(\alpha)\right|\max_{x\in\alpha}|f(x)|+\varepsilon(\gamma_{n}(\alpha)+\gamma(\alpha))\right)$
$\displaystyle\leq|I_{N}|{d_{\diamond}\left({\gamma_{n}},{\gamma}\right)}\max_{x\in{[-1/2,1/2]}^{2}}|f(x)|+2\varepsilon\xrightarrow[n\to\infty]{}2\varepsilon.$

Since $\varepsilon$ and $f$ were arbitrary this means that
$\gamma_{n}\to\gamma$ in the weak topology.

Now assume that $\gamma_{n}\to\gamma$ in the weak topology. We first show that
for every $\alpha\in{\mathcal{R}}$ it holds that
$\gamma_{n}(\alpha)\to\gamma(\alpha)$. Let $\alpha\in{\mathcal{R}}$ and let
$\varepsilon>0$. Let $\beta$ be the $\varepsilon$-neighborhood of $\alpha$ in
the $\ell_{1}$ norm. Then $\beta\setminus\alpha$ is contained in four
diagonals of width $\varepsilon$. Hence $\delta(\beta\setminus\alpha)\leq
4\varepsilon$ for every $\delta\in{\Gamma}$. Let $f:{[-1/2,1/2]}^{2}\to[0,1]$
be continuous, equal to $1$ on $\alpha$, and equal to $0$ outside $\beta$.
Then, for every $\delta\in{\Gamma}$:

$\int fd\delta\geq\delta(\alpha)=\int
fd\delta-\int_{\beta\setminus\alpha}fd\delta\geq\int fd\delta-4\varepsilon.$

Thus

$|\gamma_{n}(\alpha)-\gamma(\alpha)|\leq\left|\int fd\gamma_{n}-\int
fd\gamma\right|+4\varepsilon\xrightarrow[n\to\infty]{}4\varepsilon.$

Since $\varepsilon>0$ was arbitrary, we conclude that
$\gamma_{n}(\alpha)\to\gamma(\alpha)$.

We now show that ${d_{\diamond}\left({\gamma_{n}},{\gamma}\right)}\to 0$. Let
$\varepsilon>0$. Let $N=\lfloor\varepsilon^{-1}\rfloor$ and let $n_{0}$ be
large enough such that for all $n\geq n_{0}$ and for every $\alpha\in I_{N}$
it holds that $|\gamma_{n}(\alpha)-\gamma(\alpha)|<\varepsilon^{3}$. Then, by
Claim 2.15, for every $n\geq n_{0}$ we have
${d_{\diamond}\left({\gamma_{n}},{\gamma}\right)}<100\varepsilon$. Hence
${d_{\diamond}\left({\gamma_{n}},{\gamma}\right)}\to 0$. We conclude that
$({\Gamma},{d_{\diamond}})$ is compact. ∎

We now show that $H_{q}^{N}$ approximates $H_{q}$.

######  Lemma 2.18.

Let $\gamma\in{\Gamma}$. Then
$\lim_{N\to\infty}H_{q}^{N}(\gamma)=H_{q}(\gamma)$.

###### Proof.

It suffices to show that $\lim_{N\to\infty}D^{N}(\gamma)=D_{KL}(\gamma)$,
$\lim_{N\to\infty}D(\\{{\overline{{\gamma}}^{+}}(\alpha)\\}_{\alpha\in
J_{N}})=D_{KL}({\overline{{\gamma}}^{+}})$, and
$\lim_{N\to\infty}D(\\{{\overline{{\gamma}}^{-}}(\alpha)\\}_{\alpha\in
J_{N}})=D_{KL}({\overline{{\gamma}}^{-}})$.

By definition $D^{N}(\gamma)=\sum_{\alpha\in
I_{N}}\gamma(\alpha)\log\left(\gamma(\alpha)/|\alpha|\right)$. Therefore,
$D^{N}(\gamma)$ is a Riemann sum for $D_{KL}(\gamma)$. Of course, $\gamma$ may
not have a density function, and even if it does it may not be Riemann-
integrable. Therefore, it is not immediate that the Riemann sums converge.
This can be shown using a standard measure-theoretic argument relying on
specific properties of the function $x\log x$. Rather than give the details,
we derive our lemma from the following general claim used to prove the
analogous statement for permutons.

######  Claim 2.19 ([13, Proposition 9]).

Let $\mu$ be a finite measure on $[0,1]^{2}$. For $m\in\mathbb{N}$ and
$i,j\in[m]$, let $\mu_{i,j}=m^{2}\mu([(i-1)/m,i/m]\times[(j-1)/m,j/m])$.
Define:

$R_{m}=\frac{1}{m^{2}}\sum_{i,j\in[m]^{2}}\mu_{i,j}\log(\mu_{i,j}).$

Then:

  1. (a)

If $\mu$ is absolutely continuous with density $f$ and $f\log f$ is integrable
then $\lim_{m\to\infty}R_{m}=\int_{[0,1]^{2}}f\log f$.

  2. (b)

If $\mu$ is absolutely continuous with density $f$ and $f\log f$ is not
integrable then $\lim_{m\to\infty}R_{m}=\infty$.

  3. (c)

If $\mu$ has a singular component then $\lim_{m\to\infty}R_{m}=\infty$.

In order to show that $\lim_{N\to\infty}D^{N}(\gamma)=D_{KL}(\gamma)$ we will
define a finite measure $\mu$ on $[0,1]^{2}$ such that for every
$N\in\mathbb{N}$, $R_{2N}=D^{N}(\gamma)+\log(2)-O(1/N)$. Let
$F:{[-1/2,1/2]}^{2}\to[0,1]^{2}$ be the function

$F(x,y)=(1/2,1/2)+\frac{1}{2}(x+y,x-y).$

$F$ is a rotation of the plane by $\pi/4$ followed by rescaling and
translation. It easily follows that for every $N\in\mathbb{N}$ and
$i,j\in[2N]$ it holds that
$F^{-1}([(i-1)/(2N),i/(2N)]\times[(j-1)/(2N),j/(2N)])$ is either empty or an
element of $I_{N}$. Define the measure $\mu$ on $[0,1]^{2}$ by setting, for
every Borel $U\subseteq[0,1]^{2}$, $\mu(U)=\gamma(F^{-1}(U))$. Now, for every
$N\in\mathbb{N}$ there holds

$R_{2N}=\sum_{\alpha\in
I_{N}}\gamma(\alpha)\log\left(4N^{2}\gamma(\alpha)\right)=\sum_{\alpha\in
I_{N}}\gamma(\alpha)\log\left(\frac{2\gamma(\alpha)}{|\alpha|}\right)-\sum_{\alpha\in
T_{N}}\gamma(\alpha)\log(2).$

The half-squares in $T_{N}$ satisfy $\sum_{\alpha\in
T_{N}}\gamma(\alpha)=O(1/N)$, so:

$\displaystyle R_{2N}=\sum_{\alpha\in
I_{N}}\gamma(\alpha)\log\left(\frac{2\gamma(\alpha)}{|\alpha|}\right)-O\left(\frac{1}{N}\right)=D^{N}(\gamma)+\log(2)-O\left(\frac{1}{N}\right).$

Hence

$\lim_{N\to\infty}D^{N}(\gamma)=\lim_{N\to\infty}R_{2N}-\log
2.=D_{KL}(\gamma).$

Now $D_{KL}(\gamma)<\infty$ if and only if $\mu$ is absolutely continuous with
density $f$ and $f\log f$ is integrable. Thus, if $D_{KL}(\gamma)=\infty$ then
$\lim_{N\to\infty}D^{N}(\gamma)=\lim_{N\to\infty}R_{2N}-\log 2=\infty$.
Otherwise, if $\gamma$ has density function $g$ then $f=2g\circ F^{-1}$.
Hence, by the change of variables formula:

$\int_{[0,1]^{2}}f\log f=\int_{[0,1]^{2}}2g\circ F^{-1}\log(2g\circ
F^{-1})=\frac{1}{2}\int_{{[-1/2,1/2]}^{2}}2g\log(2g)=D_{KL}(\gamma)+\log(2),$

implying $\lim_{N\to\infty}D^{N}(\gamma)=D_{KL}(\gamma)$.

We now show that for $*\in\\{+,-\\}$,
$\lim_{N\to\infty}D(\\{\overline{\gamma}^{*}(\alpha)\\}_{\alpha\in
J_{N}})=D_{KL}(\overline{\gamma}^{*})$. We define a measure $\nu$ on
$[0,1]^{2}$ as follows: Let $G:[-1,1]\to[0,1]$ be given by $G(x)=(x+1)/2$.
Define the measure $\tilde{\nu}$ on $[0,1]$ by
$\tilde{\nu}(U)=\overline{\gamma}^{*}(G^{-1}(U))$. Then, let $\nu$ be the
product measure of $\tilde{\nu}$ with the uniform distribution on $[0,1]$. It
then holds that

$D_{KL}(\nu||{\mathcal{U}}_{[0,1]^{2}})=D_{KL}(\tilde{\nu}||{\mathcal{U}}_{[0,1]})=D_{KL}(\overline{\gamma}^{*}||{\mathcal{U}}_{[-1,1]}).$

For every $N$ it holds that
$R_{N}=D(\\{\overline{\gamma}^{*}(\alpha)\\}_{\alpha\in J_{N}})$. Therefore

$\lim_{N\to\infty}D(\\{\overline{\gamma}^{*}(\alpha)\\}_{\alpha\in
J_{N}})=\lim_{N\to\infty}R_{N}=D_{KL}(\nu||{\mathcal{U}}_{[0,1]^{2}})=D_{KL}(\overline{\gamma}^{*}||{\mathcal{U}}_{[-1,1]}),$

completing the proof. ∎

######  Lemma 2.20.

$H_{q}$ is strictly concave and upper semi-continuous.

###### Proof.

Strict concavity of $H_{q}$ follows from strict convexity of KL divergence and
the fact that ${\overline{{\gamma}}^{+}},{\overline{{\gamma}}^{-}}$ are linear
in $\gamma$.

To show upper semi-continuity we adapt the proof of the analogous claim for
permutons [13, Lemma 19]. Let $\gamma_{1},\gamma_{2},\ldots$ be a sequence of
queenons congerging to $\gamma\in{\Gamma}$. We must show that
$H_{q}(\gamma)\geq\limsup_{n\to\infty}H_{q}(\gamma_{n})$. If $H_{q}(\gamma)$
is finite, let $\varepsilon>0$ and let $N$ be large enough that
$|H_{q}^{N}(\gamma)-H_{q}(\gamma)|<\varepsilon$. Then, since
$H_{q}^{N}(\gamma_{n})\geq H_{q}(\gamma_{n})$ be cacavity,

$\limsup_{n\to\infty}H_{q}(\gamma_{n})\leq\limsup_{n\to\infty}H_{q}^{N}(\gamma_{n})=H_{q}^{N}(\gamma)<H_{q}(\gamma)+\varepsilon.$

Since this is true for every $\varepsilon>0$ we are done.

If $H_{q}(\gamma)=-\infty$, fix $t<0$ and take $N\in\mathbb{N}$ large enough
that $H_{q}^{N}(\gamma)<t$. Then:

$\limsup_{n\to\infty}H_{q}(\gamma_{n})\leq\limsup_{n\to\infty}H_{q}^{N}(\gamma_{n})=H_{q}^{N}(\gamma)<t$

for all $t<0$, so $\limsup_{n\to\infty}H_{q}(\gamma_{n})=-\infty$, as desired.
∎

######  Lemma 2.21.

There exists a unique maximizer $\gamma^{*}\in{\Gamma}$ for $H_{q}$.

###### Proof.

Uniqueness follows from the strict concavity of $H_{q}$. It remains to prove
that $H_{q}$ has a maximizer. Since KL divergence is non-negative, $H_{q}$ is
bounded above by $2\log 2-3$. Let $\gamma_{1},\gamma_{2},\ldots\in{\Gamma}$ be
a sequence such that

$\lim_{n\to\infty}H_{q}(\gamma_{n})=\sup_{\gamma\in{\Gamma}}H_{q}(\gamma).$

Since ${\Gamma}$ is compact we may assume that the sequence converges to a
queenon $\gamma^{*}$. We claim that
$H_{q}(\gamma^{*})=\sup_{\gamma\in{\Gamma}}H_{q}(\gamma)$. This follows from
upper semi-continuity of $H_{q}$. ∎

In Section 6 we will prove the following bounds on $H_{q}(\gamma^{*})$.

######  Claim 2.22.

The following holds: $-{1.9449}\leq H_{q}(\gamma^{*})\leq-{1.94}$.

###  2.2. Large deviations for queenons

Theorems 1.1 and 1.2 both follow from the following large deviations
principle.

For $\Delta\subseteq{\Gamma}$ we write $\mathring{\Delta}$ for the interior of
$\Delta$ and $\overline{\Delta}$ for its closure. For $n\in\mathbb{N}$ we
write $\Delta_{n}$ for the set of $n$-queens configurations $q$ such that
$\gamma_{q}\in\Delta$.

######  Theorem 2.23.

Let $\Delta\subseteq{\Gamma}$. The following hold:

$\sup_{\gamma\in\mathring{\Delta}}H_{q}(\gamma)\leq\liminf_{n\to\infty}\frac{1}{n}\log\left(\frac{|\Delta_{n}|}{n^{n}}\right)\leq\limsup_{n\to\infty}\frac{1}{n}\log\left(\frac{|\Delta_{n}|}{n^{n}}\right)\leq\sup_{\gamma\in\overline{\Delta}}H_{q}(\gamma).$

Taking $\Delta={\Gamma}$ and using Lemma 2.21 and Claim 2.22, we derive
Theorem 1.2.

To prove Theorem 1.2, let $\varepsilon>0$, and take
$\Delta=\left\\{\gamma\in{\Gamma}:{d_{\diamond}\left({\gamma},{\gamma^{*}}\right)}\geq\varepsilon\right\\}$.
Then, by upper semi-continuity and the fact that $\gamma^{*}$ uniquely
maximizes $H_{q}$, we conclude that
$\sup_{\gamma\in\Delta}H_{q}(\gamma)<H_{q}(\gamma^{*})$. Additionally, if an
$n$-queens configuration $q$ satisfies
${d_{\diamond}\left({\gamma_{q}},{\gamma^{*}}\right)}\geq\varepsilon$ then
$q\in\Delta_{n}$. By Theorem 2.23 there exists some $\delta>0$ such that for
large enough $n$,

$\frac{1}{n}\log\left(\frac{{\mathcal{Q}}(n)}{n^{n}}\right)\geq
H_{q}(\gamma^{*})-\delta>H_{q}(\gamma^{*})-2\delta\geq\frac{1}{n}\log\left(\frac{|\Delta_{n}|}{n^{n}}\right).$

This implies

$\frac{|\Delta_{n}|}{{\mathcal{Q}}(n)}\leq\exp\left(-n\delta\right)\to 0,$

proving Theorem 1.2.

###### Proof of Theorem 2.23.

The proof is modeled on that of [13, Theorem 1].

We first prove the lower bound, for which we may assume
$\sup_{\gamma\in\mathring{\Delta}}H_{q}(\gamma)>-\infty$. Let $\varepsilon>0$
and let $\delta\in\mathring{\Delta}$ satisfy
$H_{q}(\delta)>\sup_{\gamma\in\mathring{\Delta}}H_{q}(\gamma)-\varepsilon$.
Let $\varepsilon>\rho>0$ satisfy $B_{\rho}(\delta)\subseteq\Delta$. Then, for
every $n\in\mathbb{N}$, $B_{n}(\delta,\rho)\subseteq\Delta_{n}$. By the lower
bound in Theorem 2.11

$\displaystyle\liminf_{n\to\infty}\frac{1}{n}\log\left(\frac{|\Delta_{n}|}{n^{n}}\right)\geq\liminf_{n\to\infty}\frac{1}{n}\log\left(\frac{|B_{n}(\delta,\rho)|}{n^{n}}\right)$
$\displaystyle\geq(1-\rho)H_{q}(\delta)$
$\displaystyle\geq(1-\varepsilon)(\sup_{\gamma\in\mathring{\Delta}}H_{q}(\gamma)-\varepsilon).$

Since this is true for every $\varepsilon>0$ the lower bound follows.

For the upper bound we first handle the case that
$\beta\coloneqq\sup_{\gamma\in\overline{\Delta}}H_{q}(\gamma)>-\infty$. Let
$\varepsilon>0$. By Theorem 2.11 and Lemma 2.18, for every
$\delta\in\overline{\Delta}$ there exists some $n_{\delta}\in\mathbb{N}$ and
some $\varepsilon_{\delta}>0$ such that for all $n\geq n_{\delta}$:

$\left(\frac{|B_{n}(\delta,\varepsilon_{\delta})|}{n^{n}}\right)^{1/n}\leq\exp\left(\beta+\varepsilon\right).$

Since $\overline{\Delta}$ is compact there exists a finite set
$X\subseteq\overline{\Delta}$ such that $\Delta_{n}\subseteq\cup_{\delta\in
X}B_{n}(\delta,\varepsilon_{\delta})$. Thus:

$\limsup_{n\to\infty}\frac{1}{n}\log\left(\frac{|\Delta_{n}|}{n^{n}}\right)\leq\sup_{\gamma\in\overline{\Delta}}H_{q}(\gamma)+\varepsilon.$

Since this is true for every $\varepsilon>0$, we obtain the upper bound.

The case that $\beta=-\infty$ is proved similarly. Let $t<0$. By Theorem 2.11
and Lemma 2.18, for every $\delta\in\overline{\Delta}$ there exists some
$n_{\delta}\in\mathbb{N}$ and some $\varepsilon_{\delta}>0$ such that for all
$n\geq n_{\delta}$:

$\left(\frac{|B_{n}(\delta,\varepsilon_{\delta})|}{n^{n}}\right)^{1/n}\leq
e^{t}.$

Applying a compactness argument we obtain

$\limsup_{n\to\infty}\frac{1}{n}\log\left(\frac{|\Delta_{n}|}{n^{n}}\right)\leq
t.$

Since this is true for every $t<0$, the proof is complete. ∎

##  3\. Useful calculations

We collect here several calculations that will be useful in the sequel. On a
first reading the reader may wish to skip this section and refer to it as each
claim is used in the proof.

######  Claim 3.1.

Let $N\in\mathbb{N}$ and $1/e>\varepsilon>0$. Suppose that
$\gamma_{1},\gamma_{2}\in{\Gamma}$ satisfy
${d_{\diamond}\left({\gamma_{1}},{\gamma_{2}}\right)}<\varepsilon$. Then
$|H_{q}^{N}(\gamma_{1})-H_{q}^{N}(\gamma_{2})|<8N^{2}\varepsilon\log\left(\frac{N}{2\varepsilon^{2}}\right)$.

###### Proof.

Let $f:[0,1]\to\mathbb{R}$ be the function $f(x)=x\log(x)$. Let $x,y\in[0,1]$
such that $|x-y|\leq\varepsilon$. We claim that
$|f(x)-f(y)|\leq-2\varepsilon\log(2\varepsilon)$. If $0\leq x\leq\varepsilon$
then:

$|f(x)-f(y)|\leq|f(2\varepsilon)-f(0)|=-2\varepsilon\log(2\varepsilon).$

Otherwise, $x\in[\varepsilon,1]$. We observe that for every
$\zeta\in[\varepsilon,1]$, $|f^{\prime}(\zeta)|\leq-2\log(\varepsilon)$.
Hence, by the mean value theorem:

$|f(x)-f(y)|\leq-2|y-x|\log(\varepsilon)\leq-2\varepsilon\log(2\varepsilon).$

Now, by definition:

$\displaystyle D^{N}(\gamma_{1})$ $\displaystyle-D^{N}(\gamma_{2})$
$\displaystyle=\sum_{\alpha\in
I_{N}}\left(\gamma_{1}(\alpha)\log\left(\gamma_{1}(\alpha)\right)-\gamma_{2}(\alpha)\log(\gamma_{2}(\alpha))-(\gamma_{1}(\alpha)-\gamma_{2}(\alpha))\log(|\alpha|)\right)$
$\displaystyle=\sum_{\alpha\in
I_{N}}\left(f(\gamma_{1}(\alpha))-f(\gamma_{2}(\alpha))-(\gamma_{1}(\alpha)-\gamma_{2}(\alpha))\log(|\alpha|)\right).$

Since both $\gamma_{1}$ and $\gamma_{2}$ are probability measures:

$\left|\sum_{\alpha\in
I_{N}}(\gamma_{1}(\alpha)-\gamma_{2}(\alpha))\log(|\alpha|)\right|\leq
8N^{2}{d_{\diamond}\left({\gamma_{1}},{\gamma_{2}}\right)}\log(2N)\leq
8N^{2}\varepsilon\log(2N).$

Additionally:

$\left|\sum_{\alpha\in
I_{N}}(f(\gamma_{1}(\alpha))-f(\gamma_{2}(\alpha)))\right|\leq-|I_{N}|2\varepsilon\log(2\varepsilon)\leq-8N^{2}\varepsilon\log(2\varepsilon).$

By similar considerations:

$\left|D\left(\\{{\overline{{\gamma_{1}}}^{+}}(\alpha)\\}_{\alpha\in
J_{N}}\right)-D\left(\\{{\overline{{\gamma_{2}}}^{+}}(\alpha)\\}_{\alpha\in
J_{N}}\right)\right|\leq-4N\varepsilon\log(2\varepsilon)$

and

$\left|D\left(\\{{\overline{{\gamma_{1}}}^{-}}(\alpha)\\}_{\alpha\in
J_{N}}\right)-D\left(\\{{\overline{{\gamma_{2}}}^{-}}(\alpha)\\}_{\alpha\in
J_{N}}\right)\right|\leq-4N\varepsilon\log(2\varepsilon).$

Therefore:

$\left|H_{q}^{N}(\gamma_{1})-H_{q}^{N}(\gamma_{2})\right|\leq
8N^{2}\varepsilon\log\left(\frac{N}{\varepsilon}\right)-8N\varepsilon\log(2\varepsilon)\leq
8N^{2}\varepsilon\log\left(\frac{N}{2\varepsilon^{2}}\right),$

as claimed. ∎

######  Claim 3.2.

Let $0<b\leq 1$, $n\in\mathbb{N}$ and let $(1-1/e)n\leq T<n$ be an integer.
Then

$\sum_{t=0}^{T-1}b\log\left(1-bt/n\right)=n\left(-(1-b)\log(1-b)-b\right)\pm
2(n-T)\log(1-T/n).$

###### Proof.

Let $f(x)=b\log(1-bx)$ and observe that
$\frac{b}{n}\sum_{t=0}^{T-1}\log\left(1-bt/n\right)$ is a Riemann sum for the
integral $\int_{0}^{T/n}f(x)dx$. Also, for every $x\in[0,T/n]$:

$|f^{\prime}(x)|=\frac{b^{2}}{1-bx}\leq\frac{1}{1-T/n}.$

Therefore:

$\int_{0}^{T/n}f(x)dx=\frac{b}{n}\sum_{t=0}^{T-1}\log\left(1-bt/n\right)\pm\frac{1}{n}\max_{x\in[0,T/n]}|f^{\prime}(x)|=\frac{b}{n}\sum_{t=0}^{T-1}\log\left(1-bt/n\right)\pm\frac{1}{n-T}.$

We can calculate the integral exactly. Let
$F(x)=-\left(bx+(1-bx)\log(1-bx)\right)$. Then $F^{\prime}(x)=f(x)$. Thus:

$\displaystyle\int_{0}^{T/n}f(x)dx$
$\displaystyle=F(T/n)-F(0)=F(1)-F(0)+F(T/n)-F(1)$
$\displaystyle=-b-(1-b)\log(1-b)+F(T/n)-F(1),$

Now, for $g(x)=x\log(x)$:

$F(T/n)-F(1)=b(1-T/n)+g(1-b)-g(1-bT/n).$

For every $x,y\in[0,1]$ it holds that $|g(x)-g(y)|\leq|y-x||\log(|y-x|)|$.
Therefore $g(1-b)-g(1-bT/n)\leq
b(1-T/n)|\log(b(1-T/n))|\leq(1-T/n)|\log(1-T/n)|$. Finally, since
$T\geq(1-1/e)n$, $|\log(1-T/n)|\geq 1$. Therefore:

$|F(T/n)-F(1)|\leq 2(1-T/n)|\log(1-T/n)|.$

Hence:

$\sum_{t=0}^{T-1}b\log\left(1-bt/n\right)=n\left(-(1-b)\log(1-b)-b\right)\pm
2(n-T)\log(1-T/n),$

as claimed. ∎

######  Claim 3.3.

There exists a constant $C>0$ such that the following holds: Let $\gamma$ be
an $N$-step queenon. Let $G_{M}$ be the maximal density of $\gamma$. Let
$n\in\mathbb{N}$ satisfy $n\geq N^{2}$ and let $(x,y)\in[n]^{2}$. The
following hold:

  1. (a)

$\sum_{\alpha\in
I_{N}}\frac{\gamma(\alpha)L_{y,\alpha}^{r}}{|\alpha_{n}|}=\frac{1}{n}\pm\frac{CNG_{M}}{n^{2}}$.

  2. (b)

$\sum_{\alpha\in
I_{N}}\frac{\gamma(\alpha)L_{x,\alpha}^{c}}{|\alpha_{n}|}=\frac{1}{n}\pm\frac{CNG_{M}}{n^{2}}$.

  3. (c)

$\sum_{\alpha\in
I_{N}}\frac{\gamma(\alpha)D_{x+y,\alpha}^{+}}{|\alpha_{n}|}=\frac{N\gamma^{+}(\alpha)}{n}\pm\frac{CG_{M}}{Nn}$.

  4. (d)

$\sum_{\alpha\in
I_{N}}\frac{\gamma(\alpha)D_{y-x,\alpha}^{-}}{|\alpha_{n}|}=\frac{N\gamma^{-}(\alpha)}{n}\pm\frac{CG_{M}}{Nn}$.

###### Proof.

Let $G$ be the $N\times N$ matrix such that for every $i,j\in[N]$, the density
of $\gamma$ on $\sigma_{i,j}^{N}$ is $G_{i,j}$.

Let $\delta$ be the probability measure on ${[-1/2,1/2]}^{2}$ that, for every
$\alpha\in I_{N}$, has constant density on $\alpha$ and satisfies
$\delta(\alpha)=\gamma(\alpha)$. We claim that $\delta$ is a permuton, i.e.,
has uniform marginals. We will show that it has uniform marginals along
columns; this suffices because of the symmetry between rows and columns.

Let $f:{[-1/2,1/2]}\to\mathbb{R}$ be the density function of the marginal
distribution of $\delta$ along vertical lines (i.e., for every $-1/2\leq a\leq
b\leq 1/2$ we have $\delta(\\{(x,y):x\in[a,b]\\})=\int_{a}^{b}f(x)dx$). We
need to show that $f\equiv 1$. We observe that $f$ is piecewise-linear with
respect to the intervals $\\{[-1/2+(i-1)/(2N),-1/2+i/(2N)]\\}_{i\in[2N]}$.
Thus, it suffices to show that for every integer $0\leq i\leq 2N$ it holds
that $f(-1/2+i/(2N))=1$.

We must take a closer look at $\delta$. For this we need some notation. We
recommend the reader have Figure 2 at hand. For $(a,b)\in\mathbb{R}^{2}$ and
$\varepsilon>0$ let $B_{\varepsilon}^{1}(a,b)$ be the closed $\ell_{1}$-ball
of radius $\varepsilon$ centered at $(a,b)$. Observe that every element of
$I_{N}$ is the intersection of an $\ell_{1}$-ball of radius $1/(2N)$ with
${[-1/2,1/2]}^{2}$. For $0\leq i\leq 2N$ even and $j\in[N]$, let

$\alpha_{i,j}\coloneqq
B_{1/(2N)}^{1}(-1/2+i/(2N),-1/2+1/(2N)+j/N)\cap{[-1/2,1/2]}^{2}\in I_{N}$

and for $1\leq i<2N$ odd and $0\leq j\leq N$ let

$\alpha_{i,j}\coloneqq
B_{1/(2N)}^{1}(-1/2+i/(2N),-1/2+j/N)\cap{[-1/2,1/2]}^{2}\in I_{N}.$

We make the following observations.

  * •

If $i=0$ then, for every $j\in[N]$, $\alpha_{i,j}=\alpha_{0,j}$ is a half-
square contained in $\sigma_{1,j}^{N}$. Thus,
$\delta(\alpha_{0,j})=G_{1,j}/(4N^{2})$. Therefore
$f(-1/2)=\sum_{j=1}^{N}G_{1,j}/N$. Because $G$ is the density matrix of a
permuton, the sum along each row is $N$. Therefore $f(-1/2)=1$.

  * •

The case $i=2N$ is handled similarly: $f(1/2)=\sum_{j=1}^{N}G_{N,j}/N=1$.

  * •

If $1<i<2N$ is even, then every $\alpha_{i,j}$ is a square, the left half of
which is contained in $\sigma_{i/2,j}^{N}$ and the right half of which is
contained in $\sigma_{i/2+1,j}^{N}$. Therefore
$\delta(\alpha_{i,j})=(G_{i/2,j}+G_{i/2+1,j})/(4N^{2})$. Hence
$f(-1/2+i/(2N))=\sum_{j=1}^{N}(G_{i/2,j}+G_{i/2+1,j})/(2N)=1$.

  * •

If $1\leq i<2N$ is odd then for $1\leq j<N$, $\alpha_{i,j}$ is a square, the
lower half of which is contained in $\sigma_{(i+1)/2,j}^{N}$ and the upper
half of which is contained in $\sigma_{(i+1)/2,j+1}^{N}$. In this case
$\delta(\alpha_{i,j})=(G_{(i+1)/2,j}+G_{(i+1)/2,j+1})/(4N^{2})$. Additionally,
$\alpha_{i,0}$ is a half-square contained in $\sigma_{(i+1)/2,1}^{N}$ and
$\alpha_{i,N}$ is a half-square contained in $\sigma_{(i+1)/2,N}^{N}$.
Therefore $\delta(\alpha_{i,1})=G_{(i+1)/2,1}/(4N^{2})$ and
$\delta(\alpha_{i,N})=G_{(i+1)/2,N}/(4N^{2})$. Hence

$\displaystyle f(-1/2+i/(2N))$
$\displaystyle=\frac{1}{2N}\left(G_{(i+1)/2,1}+G_{(i+1)/2,N}+\sum_{j=1}^{N-1}\left(G_{(i+1)/2,j}+G_{(i+1)/2,j+1}\right)\right)$
$\displaystyle=\frac{1}{N}\sum_{j=1}^{N}G_{(i+1)/2,j}=1.$

This completes the proof that $\delta$ is a permuton.

In the following, the constants $0<C_{1}<C_{2}<\ldots$ are each chosen to be
sufficiently large with respect to the previous choices. However, none of them
depend on $\gamma,N$, or $n$.

We now prove (a), which will imply (b) by the symmetry between rows and
columns. By construction: $\sum_{\alpha\in
I_{N}}\frac{\gamma(\alpha)L_{y,\alpha}^{r}}{|\alpha_{n}|}=\sum_{\alpha\in
I_{N}}\frac{\delta(\alpha)L_{y,\alpha}^{r}}{|\alpha_{n}|}$. Because $\delta$
is a permuton it has uniform marginals and so:

$\sum_{a=1}^{n}\delta(\sigma_{a,y}^{n})=\delta(\\{(a,b):-1/2+(y-1)/n\leq
b\leq-1/2+y/n\\})=\frac{1}{n}.$

Hence it suffices to prove that

(1) $\left|\sum_{\alpha\in
I_{N}}\frac{\delta(\alpha)L_{y,\alpha}^{r}}{|\alpha_{n}|}-\sum_{a=1}^{n}\delta(\sigma_{a,y}^{n})\right|\leq\frac{CNG_{M}}{n^{2}}$

for a suitable constant $C$ (independent of $\gamma,N$, and $n$).

Recall that for every $\alpha\in I_{N}$, $|\alpha_{n}|=|\alpha|n^{2}\pm
8n/N=|\alpha|n^{2}(1\pm C_{1}N/n)$. Therefore, $\sum_{\alpha\in
I_{N}}\frac{\delta(\alpha)L_{y,\alpha}^{r}}{|\alpha_{n}|}=\left(1\pm\frac{C_{2}N}{n}\right)\frac{1}{n^{2}}\sum_{\alpha\in
I_{N}}\frac{\delta(\alpha)L_{y,\alpha}^{r}}{|\alpha|}$. Now, there are fewer
than $2N$ elements $\alpha\in I_{N}$ such that $L_{y,\alpha}^{r}>0$.
Additionally, for each one, $L_{y,\alpha}^{r}\leq 2n/N$. Finally, for every
$\alpha$, there holds $\delta(\alpha)/|\alpha|\leq G_{M}$. Hence:
$\left(1\pm\frac{C_{2}N}{n}\right)\frac{1}{n^{2}}\sum_{\alpha\in
I_{N}}\frac{\delta(\alpha)L_{y,\alpha}^{r}}{|\alpha|}=\frac{1}{n^{2}}\sum_{\alpha\in
I_{N}}\frac{\delta(\alpha)L_{y,\alpha}^{r}}{|\alpha|}\pm\frac{C_{3}G_{M}N}{n^{2}}$.
Now consider $\frac{1}{n^{2}}\sum_{\alpha\in
I_{N}}\frac{\delta(\alpha)L_{y,\alpha}^{r}}{|\alpha|}$. This may be rewritten
as $\sum_{a=1}^{n}\frac{\delta(\alpha(a,y))}{|\alpha(a,y)|n^{2}}$. Let
$X\subseteq[n]$ be the set of indices $a$ such that
$\sigma_{a,y}^{n}\subseteq\alpha(a,y)$. For every $a\in X$ there holds
$\delta(\sigma_{a,y}^{n})=\delta(\alpha(a,y))/(|\alpha(a,y)|n^{2})$.
Therefore:

$\left|\sum_{a=1}^{n}\frac{\delta(\alpha(a,y))}{|\alpha(a,y)|n^{2}}-\sum_{a=1}^{n}\delta(\sigma_{a,y}^{n})\right|\leq\sum_{a\notin
X}\left(\frac{\delta(\alpha(a,y))}{|\alpha(a,y)|n^{2}}+\delta(\sigma_{a,y}^{n})\right)\leq\frac{2G_{M}}{n^{2}}(n-|X|).$

Since there are at most $2N$ indices $a$ such that $\sigma_{a,y}^{n}$
intersects more than one element of $I_{N}$ we have:

$\left|\sum_{\alpha\in
I_{N}}\frac{\delta(\alpha)L_{y,\alpha}^{r}}{|\alpha_{n}|}-\sum_{a=1}^{n}\delta(\sigma_{a,y}^{n})\right|\leq\frac{C_{3}G_{M}N}{n^{2}}+\frac{4G_{M}N}{n^{2}}\leq\frac{C_{4}G_{M}N}{n^{2}},$

proving (1) and hence (a).

Next, we prove (c), which will imply (d) by the symmetry between plus- and
minus-diagonals. The argument is similar to the proof of (a). Consider

$\sum_{\alpha\in
I_{N}}\frac{\gamma(\alpha)D_{x+y,\alpha}^{+}}{|\alpha_{n}|}=\sum_{\alpha\in
I_{N}}\frac{\delta(\alpha)D_{x+y,\alpha}^{+}}{|\alpha_{n}|}=\sum_{\alpha\in
S_{N}}\frac{\delta(\alpha)D_{x+y,\alpha}^{+}}{|\alpha_{n}|}+\sum_{\alpha\in
T_{N}}\frac{\delta(\alpha)D_{x+y,\alpha}^{+}}{|\alpha_{n}|}.$

We first show that the contribution from $T_{N}$ is negligible. Indeed, there
are at most $4$ elements $\alpha\in T_{N}$ such that $D_{x+y,\alpha}^{+}>0$.
For every $\alpha$ it holds that $D_{x+y,\alpha}^{+}\leq 3n/N$. Therefore

$\sum_{\alpha\in
T_{N}}\frac{\delta(\alpha)D_{x+y,\alpha}^{+}}{|\alpha_{n}|}\leq\frac{C_{5}G_{M}}{nN}.$

Now, for every $\alpha\in S_{N}$ such that $D_{x+y,\alpha}^{+}>0$ we have
$D_{x+y,\alpha}^{+}=n/(2N)\pm 1$ and $|\alpha_{n}|=n^{2}/(2N^{2})\pm 4n/N$.
Therefore:

$\displaystyle\sum_{\alpha\in
S_{N}}\frac{\delta(\alpha)D_{x+y,\alpha}^{+}}{|\alpha_{n}|}$
$\displaystyle=\left(1\pm\frac{C_{6}N}{n}\right)\frac{N}{n}\sum_{\alpha\in
S_{N}:D_{x+y,\alpha}^{+}>0}\delta(\alpha)$
$\displaystyle=\left(1\pm\frac{C_{6}N}{n}\right)\frac{N}{n}\left(\delta^{+}(\alpha)-\sum_{\alpha\in
T_{N}:D_{x+y,\alpha}^{+}>0}\delta(\alpha)\right).$

Again using the fact that there are at most $4$ half-squares $\alpha\in T_{N}$
such that $D_{x+y,\alpha}^{+}>0$:

$\displaystyle\sum_{\alpha\in
S_{N}}\frac{\delta(\alpha)D_{x+y,\alpha}^{+}}{|\alpha_{n}|}$
$\displaystyle=\left(1\pm\frac{C_{6}N}{n}\right)\frac{N}{n}\left(\delta^{+}(\alpha)\pm\frac{G_{M}}{N^{2}}\right)=\frac{N\delta^{+}(\alpha)}{n}\pm\left(\frac{C_{6}N}{n^{2}}+\frac{G_{M}}{Nn}+\frac{C_{6}G_{M}}{n}\right).$

By assumption, $n\geq N^{2}$. Additionally, because $\gamma$ is a permuton,
$G_{M}\geq 1$. Therefore
$\frac{C_{6}N}{n^{2}}+\frac{G_{M}}{Nn}+\frac{C_{6}G_{M}}{n}\leq\frac{C_{7}G_{M}}{Nn}$.
Finally, we note that by construction $\delta^{+}(\alpha)=\gamma^{+}(\alpha)$.
Therefore:

$\sum_{\alpha\in
I_{N}}\frac{\gamma(\alpha)D_{x+y,\alpha}^{+}}{|\alpha_{n}|}=\frac{N\gamma^{+}(\alpha)}{n}\pm\frac{C_{7}G_{M}}{nN},$

as desired. ∎

##  4\. Upper bound

###  4.1. Entropy preliminaries

In this section we prove the upper bound in Theorem 2.11. The main tool is the
entropy method. We briefly recall the definitions and properties we will use.

If $X$ is a random variable taking values in a finite set $S$ then its entropy
is defined as

$H(X)=-\sum_{s\in
S}{\mathbb{P}}\left[X=s\right]\log\left({\mathbb{P}}\left[X=s\right]\right).$

The entropy function is strictly concave and so $H(X)\leq\log(|S|)$ with
equality holding if and only if $X$ is uniform.

If $X,Y$ are two random variables taking values in a set $S\times T$ we write
$(X{|}Y=t)$ for the marginal distribution of $X$ given that $Y=t\in T$. the
conditional entropy of $X$ given $Y$ is defined as:

$H(X{|}Y)=\sum_{t\in
T}{\mathbb{P}}[Y=t]H(X{|}Y=t)={\mathbb{E}}_{Y}H(X{|}Y=t).$

We will also use the chain rule. If $X_{1},\ldots,X_{n}$ are a sequence of
random variables then

$H(X_{1},\ldots,X_{n})=\sum_{i=1}^{n}H(X_{i}{|}X_{1},\ldots,X_{i-1}).$

###  4.2. Proof overview

In this subsection we outline the proof and give some intuition. We emphasize
that the the outline is informal, and we do not rely on it for the proof.

Let $\gamma\in{\Gamma}$ and let $\varepsilon>0$ be sufficiently small.
Consider the following random process: Let $q\in B_{n}(\gamma,\varepsilon)$ be
chosen uniformly at random, and let $X_{1},X_{2},\ldots,X_{n}$ be a uniformly
random ordering of the queens in $q$. Then

(2)
$H(X_{1},\ldots,X_{n})=H(q)+\log(n!)=\log|B_{n}(\gamma,\varepsilon)|+\log(n!).$

We will bound $H(X_{1},\ldots,X_{n})$ using the chain rule. Specifically, we
will bound $H(X_{t}{|}X_{1},\ldots,X_{t-1})$ for every $1\leq t\leq n$. We do
this by introducing additional random variables: Let $N$ be a large, fixed
constant. For every $1\leq t\leq n$, let $Y_{t}\in I_{N}$ be the $\alpha$ such
that $X_{t}\in\alpha_{n}$. By the chain rule:

$H(X_{t}{|}X_{1},\ldots,X_{t-1})=H(Y_{t}{|}X_{1},\ldots,X_{t-1})+H(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t}).$

Since $q\in B_{n}(\gamma,\varepsilon)$, for every $\alpha\in I_{N}$ it holds
that $|q\cap\alpha_{n}|\approx n\gamma(\alpha)$. Therefore:

$H(Y_{t})\approx-\sum_{\alpha\in I_{n}}\gamma(\alpha)\log(\gamma(\alpha)).$

It is not difficult to show that this holds even when conditioning on
$X_{1},\ldots,X_{t-1}$. We now wish to bound
$H(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t})$. Let $Q(t)$ be the partial $n$-queens
configuration $\\{X_{1},\ldots,X_{t}\\}$. Recall that a position is available
in $Q(t)$ if it does not share a row, column, or diagonal with an element of
$Q(t)$. Let $A_{\alpha}(t)=|\alpha_{n}\cap{\mathcal{A}}_{Q(t)}|$. Then
$X_{t}$, given $X_{1},\ldots,X_{t-1},Y_{t}$ is an element of
$\alpha_{n}\cap{\mathcal{A}}_{Q(t)}$. Therefore:

$H(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t})\leq{\mathbb{E}}\left[\log\left(A_{Y_{t}}(t-1)\right)\right].$

By Jensen’s inequality:

$H(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t})\leq\log\left({\mathbb{E}}\left[A_{Y_{t}}(t-1)\right]\right).$

In order to bound $A_{Y_{t}}(t-1)$ we make the following observations: Every
position in $\alpha_{n}$ shares its row and column with queens from $q$.
Additionally, each position can share between $0$ and $2$ of its diagonals
with queens from $q$. For an arbitrary $n$-queens configuration it would be
challenging to proceed further. Fortunately, we know that $q\in
B_{n}(\gamma,\varepsilon)$, and we can use this to our advantage. Indeed, the
number of plus-diagonals passing through $\alpha_{n}$ that are occupied by
elements of $q$ is $\approx\gamma^{+}(\alpha)n$ and the number of occupied
minus-diagonals is $\approx\gamma^{-}(\alpha_{n})n$. The total number of each
kind of diagonal passing through $\alpha_{n}$ is $\approx n/N$. If we assume
that the occupied diagonals in each direction are approximately independent
(over the choice of $q$), then there are $\approx
B_{2}(\alpha)\coloneqq|\alpha_{n}|N^{2}\gamma^{+}(\alpha)\gamma^{-}(\alpha)$
positions threatened along both diagonals, $\approx
B_{1}(\alpha)\coloneqq|\alpha_{n}|N\left(\gamma^{+}(\alpha)(1-N\gamma^{-}(\alpha))+\gamma^{-}(\alpha)(1-N\gamma^{+}(\alpha))\right)$
positions threatened by exactly one diagonal, and $\approx
B_{0}(\alpha)\coloneqq|\alpha_{n}|(1-N\gamma^{+}(\alpha))(1-N\gamma^{-}(\alpha))$
positions unthreatened by diagonals. Now, if a position is threatened by $i$
diagonals then the probability that it is available at time $t$ is
$\approx(1-t/n)^{2+i}$. This is because it is available only if the $2+i$
queens threatening it are not in $Q(t)$ and these events are approximately
independent. Therefore, for every $\alpha\in I_{N}$:

${\mathbb{E}}\left[A_{\alpha}(t-1)\right]\approx\sum_{i=0}^{2}B_{i}(\alpha)\left(1-\frac{t}{n}\right)^{2+i}.$

In light of (2), to obtain the bound on $|B_{n}(\gamma,\varepsilon)|$, it
remains to verify that

$\displaystyle\sum_{t=1}^{n}H(X_{t}{|}X_{1},\ldots,X_{t-1})\leq$
$\displaystyle\sum_{t=1}^{n}\left(-\sum_{\alpha\in
I_{n}}\gamma(\alpha)\log(\gamma(\alpha))+\log\left(\sum_{i=0}^{2}B_{i}(\alpha)\left(1-\frac{t}{n}\right)^{2+i}\right)\right)$
$\displaystyle\approx n\log(n)+nH_{q}(\gamma)+\log(n!).$

Most of the assertions above can be justified routinely. There is one
heuristic, however, that needs more work. This is the statement that the
occupied plus-diagonals and the occupied minus-diagonals passing through
$\alpha_{n}$ are distributed independently. At first glance it might not be
clear why this is important. Indeed, one might make the mistake of thinking
that every plus diagonal passing through $\alpha_{n}$ intersects every minus-
diagonal passing through $\alpha_{n}$ in exactly one position. However, as
every chess player will immediately point out, this is not the case -
diagonals on a chess board intersect only if they are both black or both
white. Intuitively, our heuristic is justified by the assertion that the
entropy is maximized when the configuration is “color-blind”, and black and
white diagonals are equally likely to be occupied. In order to prove this we
introduce a new limit object that includes information regarding the
distribution of queens on board positions of each color.

###  4.3. BW decompositions

Given a queenon, we will consider the various ways of decomposing it into a
distribution of queens on black and white spaces. Given such a decomposition
we will bound, from above, the number of $n$-queens configurations close to
it. We will show that the bound is maximized when the partition is equitable.

######  Definition 4.1.

Let $\gamma\in{\Gamma}$. A BW-decomposition of $\gamma$ is a pair
${(\gamma_{b},\gamma_{w})}$ of Borel measures on ${[-1/2,1/2]}^{2}$
satisfying:

  1. (a)

$\gamma_{b}+\gamma_{w}=\gamma$.

  2. (b)

For every $-1\leq a<b\leq 1$ both of the sets

$\left\\{(x,y):a\leq x+y\leq b\right\\},\quad\left\\{(x,y):a\leq x-y\leq
b\right\\}$

have measure at most $(b-a)/2$ under both $\gamma_{b}$ and $\gamma_{w}$.

Let ${\mathbf{BW}\left({\gamma}\right)}$ be the set of BW-decompositions of
$\gamma$. Let
$\mathbf{BW}=\bigcup_{\gamma\in{\Gamma}}{\mathbf{BW}\left({\gamma}\right)}$.
We endow it with the metric

${{d_{\mathbf{BW}}}\left({{(\gamma_{b},\gamma_{w})}},{(\delta_{b},\delta_{w})}\right)}=\max\left\\{{d_{\diamond}\left({\gamma_{b}},{\delta_{b}}\right)},{d_{\diamond}\left({\gamma_{w}},{\gamma_{b}}\right)}\right\\}.$

Given ${(\gamma_{b},\gamma_{w})}\in\mathbf{BW}$, for $i\in\\{b,w\\}$ we define
the measures
$\gamma_{i}^{+},\gamma_{i}^{-},{\overline{{\gamma_{i}}}^{+}},{\overline{{\gamma_{i}}}^{-}}$
on the interval $[-1,1]$ by:

$\displaystyle\gamma_{i}^{+}([a,b])=\gamma_{i}\left(\left\\{(x,y):a\leq
x+y\leq b\right\\}\right),$
$\displaystyle\gamma_{i}^{-}([a,b])=\gamma_{i}\left(\left\\{(x,y):a\leq
x-y\leq b\right\\}\right),$
$\displaystyle{\overline{{\gamma_{i}}}^{+}}([a,b])=(b-a)/2-\gamma_{i}^{+}([a,b]),$
$\displaystyle{\overline{{\gamma_{i}}}^{-}}([a,b])=(b-a)/2-\gamma_{i}^{-}([a,b]).$

Let ${(\gamma_{b},\gamma_{w})}\in{\mathbf{BW}\left({\gamma}\right)}$ for
$\gamma\in{\Gamma}$. Observe that ${(\gamma_{b},\gamma_{w})}$ can be viewed as
a probability measure on two copies of the unit square. Similarly,
$({\overline{{\gamma_{b}}}^{+}},{\overline{{\gamma_{w}}}^{+}})$ and
$({\overline{{\gamma_{b}}}^{-}},{\overline{{\gamma_{w}}}^{-}})$ can each be
viewed as probability measures on two copies of the interval $[-1,1]$. With
this in mind we define, for $N\in\mathbb{N}$, the discrete approximation of
the KL divergence of ${(\gamma_{b},\gamma_{w})}$ with respect to the uniform
distribution:

$\displaystyle D^{N}{(\gamma_{b},\gamma_{w})}=\sum_{i=b,w}\sum_{\alpha\in
I_{N}}\gamma_{i}(\alpha)\log\left(\frac{2\gamma_{i}(\alpha)}{|\alpha|}\right).$

We define the function

$\displaystyle
G^{N}{(\gamma_{b},\gamma_{w})}\coloneqq-D^{N}{(\gamma_{b},\gamma_{w})}-D\left(\\{{\overline{{\gamma_{i}}}^{+}}(\alpha)\\}_{\alpha\in
J_{N},i\in\\{b,w\\}}\right)-D\left(\\{{\overline{{\gamma_{i}}}^{-}}(\alpha)\\}_{\alpha\in
J_{N},i\in\\{b,w\\}}\right)+2\log 2-3.$

$G^{N}$ should be thought of as a modification of the discrete q-entropy
function $H_{q}^{N}$ that is suitable for BW-decompositions.

Let $q$ be an $n$-queens configuration. Then $q$ can be partitioned into
$q_{b},q_{w}$, where $q_{b}$ consists of the queens occupying black positions
(i.e., positions $(x,y)$ such that $x+y=0\pmod{2}$) and $q_{w}$ is the set of
queens on white positions. We define a BW-decomposition
$(\gamma_{q,b},\gamma_{q,w})$ as follows: For $i\in\\{b,w\\}$, let
$\gamma_{q,i}$ be the measure that has constant density $n$ on every square of
the form $[-1/2+(x-1)/n,-1/2+x/n]\times[-1/2+(y-1)/n,-1/2+y/n]$ for $(x,y)\in
q_{i}$ and density $0$ elsewhere. For
${(\gamma_{b},\gamma_{w})}\in\mathbf{BW}$ and $\varepsilon>0$ let
$B_{n}({(\gamma_{b},\gamma_{w})},\varepsilon)$ be the set of $n$-queens
configurations $q$ such that
${{d_{\mathbf{BW}}}\left({{(\gamma_{b},\gamma_{w})}},{(\gamma_{q,b},\gamma_{q,w})}\right)}<\varepsilon$.

The main result of this section is a bound on
$|B_{n}({(\gamma_{b},\gamma_{w})},\varepsilon)|$.

######  Lemma 4.2.

For all $\varepsilon>0$ sufficiently small the following holds. Let
${(\gamma_{b},\gamma_{w})}\in\mathbf{BW}$. Set
$N=\lfloor\varepsilon^{-1/3}\rfloor$. Then

$\limsup_{n\to\infty}\frac{|B_{n}({(\gamma_{b},\gamma_{w})},\varepsilon)|^{1/n}}{n}\leq\exp\left(G^{N}{(\gamma_{b},\gamma_{w})}+\varepsilon^{1/100}\right).$

Before proving Lemma 4.2 we make the following observations.

######  Observation 4.3.

Let $\gamma\in{\Gamma}$ and $N\in\mathbb{N}$. The following hold.

  1. (a)

$G^{N}$ is concave.

  2. (b)

$G^{N}\left(\frac{1}{2}(\gamma,\gamma)\right)=H_{q}^{N}(\gamma)$.

  3. (c)

$G^{N}$ is maximized on ${\mathbf{BW}\left({\gamma}\right)}$ by
$\frac{1}{2}(\gamma,\gamma)$.

  4. (d)

$\mathbf{BW}$ with the topology induced by ${d_{\mathbf{BW}}}$ is compact.

###### Proof.

$G^{N}$ is concave because the logarithmic function is concave and
$({\overline{{\gamma_{b}}}^{+}},{\overline{{\gamma_{w}}}^{+}})$,
$({\overline{{\gamma_{b}}}^{-}},{\overline{{\gamma_{w}}}^{-}})$ are linear
functions of ${(\gamma_{b},\gamma_{w})}$.

The fact that $G^{N}\left(\frac{1}{2}(\gamma,\gamma)\right)=H_{q}^{N}(\gamma)$
is seen by unpacking the definitions.

Let ${(\gamma_{b},\gamma_{w})}\in{\mathbf{BW}\left({\gamma}\right)}$. Then
$(\gamma_{w},\gamma_{b})\in{\mathbf{BW}\left({\gamma}\right)}$ as well.
$G^{N}$ is symmetric in $\gamma_{b}$ and $\gamma_{w}$. Thus
$G^{N}(\gamma_{w},\gamma_{b})=G^{N}{(\gamma_{b},\gamma_{w})}$. By concavity:

$\displaystyle
G^{N}{(\gamma_{b},\gamma_{w})}=\frac{1}{2}\left(G^{N}{(\gamma_{b},\gamma_{w})}+G^{N}(\gamma_{w},\gamma_{b})\right)\leq
G^{N}\left(\frac{1}{2}\left({(\gamma_{b},\gamma_{w})}+(\gamma_{w},\gamma_{b})\right)\right)=G^{N}\left(\frac{1}{2}(\gamma,\gamma)\right).$

Compactness follows in much the same way as the analogous statement for
queenons (Claim 2.17): Every element of $\mathbf{BW}$ is, in particular, a
Borel probability measure on two copies of ${[-1/2,1/2]}^{2}$. Thus,
$\mathbf{BW}$ is compact with respect to the weak topology. One then argues
similarly to the proof of Claim 2.17 that ${d_{\mathbf{BW}}}$ induces the weak
topology on $\mathbf{BW}$. ∎

###  4.4. Proof of Lemma 4.2

We prove Lemma 4.2 using the entropy method. Fix (a sufficiently small)
$\varepsilon>0$ and (a sufficiently large) $n\in\mathbb{N}$. Define the
following constants:

$N\coloneqq\lfloor\varepsilon^{-1/3}\rfloor,\quad
T\coloneqq{\lfloor(1-\varepsilon^{1/13})n\rfloor}.$

Consider the following random process: Choose $q\in
B_{n}({(\gamma_{b},\gamma_{w})},\varepsilon)$ uniformly at random and let
$X_{1},X_{2},\ldots,X_{n}$ be a uniformly random ordering of the elements of
$q$. Then

(3)
$H(X_{1},\ldots,X_{n})=H(q)+\log(n!)=\log|B_{n}({(\gamma_{b},\gamma_{w})},\varepsilon)|+\log(n!).$

By the chain rule:

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

For every $\alpha\in I_{N}$ and $i\in\\{b,w\\}$, it holds that

(4) $|\alpha_{n}\cap q_{i}|=(\gamma_{i}(\alpha)\pm 2\varepsilon)n.$

Now define the sequences $Y_{1},Y_{2},\ldots,Y_{n}$ and
$Z_{1},Z_{2},\ldots,Z_{n}$, where $Y_{t}$ is equal to the $\alpha\in I_{N}$
such that $X_{t}\in\alpha_{n}$ and $Z_{t}=b$ if $X_{t}$ is on a black square
and $Z_{t}=w$ otherwise.

######  Claim 4.4.

For every $1\leq t\leq T$ it holds that

$H(Y_{t},Z_{t}{|},X_{1},\ldots,X_{t-1})=-D^{N}{(\gamma_{b},\gamma_{w})}+2\log\left(2N\right)\pm\varepsilon^{5/39}.$

To prove Claim 4.4 we introduce, for every $\alpha\in I_{N}$, $i\in\\{b,w\\}$,
and $0\leq t<T$ the random variable $W_{\alpha,i}(t)$, equal to the number of
indices $1\leq s\leq t$ such that $(Y_{s},Z_{s})=(\alpha,i)$. Observe that
${\mathbb{E}}W_{\alpha,i}(t)=|q_{i}\cap\alpha_{n}|t/n=(\gamma_{i}(\alpha)\pm
2\varepsilon)t$. Let ${\mathcal{B}}(t)$ be the event that for some $\alpha\in
I_{N}$ and $i\in\\{b,w\\}$, it holds that
$|W_{\alpha,i}(t)-\gamma_{i}(\alpha)t|\geq 3\varepsilon n$.

######  Claim 4.5.

For every $0\leq t<T$ there holds:

${\mathbb{P}}\left[{\mathcal{B}}(t)\right]\leq\exp\left(-\Omega\left(n\right)\right).$

The proof uses the following concentration inequality for random permutations.

######  Theorem 4.6 ([11, Lemma 2.7]).

Let $S_{n}$ be the order-$n$ symmetric group, $b>0$, and let
$f:S_{n}\to\mathbb{R}$ be a function satisfying: for every $\sigma\in S_{n}$
and every transposition $\tau$, $|f(\tau\circ\sigma)-f(\sigma)|<b$. Let $X$ be
a uniformly random element of $S_{n}$. Then, for every $\lambda>0$:

${\mathbb{P}}\left[|f(X)-{\mathbb{E}}[f(X)]|>\lambda\right]\leq
2\exp\left(-\frac{\lambda^{2}}{2nb^{2}}\right).$

###### Proof of Claim 4.5.

Let $\alpha\in I_{N}$ and let $i\in\\{b,w\\}$. Conditioning on $q$,
$W_{\alpha,i}(t)$ is a function of the uniformly random permutation that
determines the order $X_{1},\ldots,X_{n}$. Furthermore, changing this order by
a single transposition affects $W_{\alpha,i}(t)$ by at most $1$. We have
already noted that ${\mathbb{E}}W_{\alpha,i}(t)=(\gamma_{i}(\alpha)\pm
2\varepsilon)t$. Therefore

${\mathbb{P}}\left[|W_{\alpha,i}(t)-\gamma_{i}(\alpha)|>3\varepsilon
n\right]\leq 2\exp\left(-\frac{(\varepsilon
n)^{2}}{2n}\right)=\exp\left(-\Omega(n)\right).$

The claim follows by applying a union bound to the $2|I_{N}|(T+1)$ choices for
$i,\alpha,t$. ∎

###### Proof of Claim 4.4.

Observe that for every $\alpha\in I_{N},i\in\\{b,w\\}$:

(5)
${\mathbb{P}}\left[(Y_{t},Z_{t})=(\alpha,i){|}{\mathcal{B}}^{c}(t-1)\right]=\frac{(\gamma_{i}(\alpha)\pm
5\varepsilon)n-\gamma_{i}(\alpha)t}{n-t}=\gamma_{i}(\alpha)\pm\frac{5\varepsilon
n}{n-T}=\gamma_{i}(\alpha)\pm\varepsilon^{11/13}.$

By the law of total probability:

$\displaystyle H(Y_{t},Z_{t}{|}X_{1},\ldots,X_{t-1})=$ $\displaystyle
H(Y_{t},Z_{t}{|}X_{1},\ldots,X_{t-1},{\mathcal{B}}(t-1)){\mathbb{P}}[{\mathcal{B}}(t-1)]$
$\displaystyle+H(Y_{t},Z_{t}{|}X_{1},\ldots,X_{t-1},{\mathcal{B}}^{c}(t-1))(1-{\mathbb{P}}[{\mathcal{B}}(t-1)])$
$\displaystyle\stackrel{{\scriptstyle\text{Claim \ref{clm:Y entropy}}}}{{=}}$
$\displaystyle
H(Y_{t},Z_{t}{|}X_{1},\ldots,X_{t-1},{\mathcal{B}}^{c}(t-1))\pm\exp\left(-\Omega\left(n\right)\right).$

By (5):

(6)
$H(Y_{t},Z_{t}{|}X_{1},\ldots,X_{t-1},{\mathcal{B}}^{c}(t-1))=-\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\left(\gamma_{i}(\alpha)\pm\varepsilon^{11/13}\right)\log\left(\gamma_{i}(\alpha)\pm\varepsilon^{11/13}\right).$

Let $B\subseteq I_{N}\times\\{b,w\\}$ be the set of indices $(\alpha,i)$ such
that $\gamma_{i}(\alpha)\leq 2\varepsilon^{11/13}$. Observe that $|B|\leq
2|I_{N}|=O(\varepsilon^{-2/3})$. Continuing (6):

$\displaystyle H$
$\displaystyle(Y_{t},Z_{t}{|}X_{1},\ldots,X_{t-1},{\mathcal{B}}^{c}(t-1))$
$\displaystyle=$ $\displaystyle-\sum_{(\alpha,i)\in
B}(\gamma_{i}(\alpha)\pm\varepsilon^{11/13})\log\left(\gamma_{i}(\alpha)\pm\varepsilon^{11/13}\right)\quad-\sum_{(\alpha,i)\notin
B}(\gamma_{i}(\alpha)\pm\varepsilon^{11/13})\log\left(\gamma_{i}(\alpha)\pm\varepsilon^{11/13}\right)$
$\displaystyle=$ $\displaystyle-\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log(\gamma_{i}(\alpha))\pm\varepsilon^{6/39}$
$\displaystyle=$ $\displaystyle-\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(\frac{2\gamma_{i}(\alpha)}{|\alpha|}\right)-\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(\frac{|\alpha|}{2}\right)\pm\varepsilon^{6/39}$
$\displaystyle=$ $\displaystyle-D^{N}{(\gamma_{b},\gamma_{w})}-\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(\frac{|\alpha|}{2}\right)\pm\varepsilon^{6/39}.$

We turn our attention to the sum $\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log(|\alpha|/2)$. Recall that
$S_{N}\cup T_{N}$ is the partition of $I_{N}$ into squares and half-squares,
respectively. For every square $\alpha\in S_{N}$ we have $|\alpha|=1/(2N^{2})$
and for every half-square $\alpha\in T_{N}$ we have $|\alpha|=1/(4N^{2})$.
Thus:

$\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log(|\alpha|/2)=-\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log(4N^{2})-\sum_{\alpha\in
T_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log(2).$

The half-squares in $T_{N}$ are contained in four axis-parallel lines of width
$1/(2N)$ each. Thus, since $\gamma_{b}+\gamma_{w}$ has uniform marginals,
$\sum_{\alpha\in T_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log(2)\leq(2\log
2)/N$. Therefore:

$\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(\frac{|\alpha|}{2}\right)=-\log(4N^{2})\pm\frac{2\log
2}{N}=-2\log(2N)\pm\varepsilon^{6/39}.$

Hence:

$H(Y_{t},Z_{t}{|}X_{1},\ldots,X_{t-1})=-D^{N}{(\gamma_{b},\gamma_{w})}+\log(4N^{2})\pm\varepsilon^{5/39},$

as claimed. ∎

We will now estimate $H(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t},Z_{t})$.

For $(\alpha,i)\in I_{N}\times\\{b,w\\}$ and $0\leq t<T$ let
${\mathcal{A}}_{\alpha,i}(t)$ denote the set of available positions of color
$i$ in $\alpha_{n}$ at time $t$. Let
$A_{\alpha,i}(t)=|{\mathcal{A}}_{\alpha,i}(t)|$. We note that given
$X_{1},\ldots,X_{t-1},Y_{t},Z_{t}$, the queen $X_{t}$ is chosen from
${\mathcal{A}}_{Y_{t},Z_{t}}(t-1)$. Thus:

$H(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t},Z_{t})\leq{\mathbb{E}}[\log\left(A_{Y_{t},Z_{t}}(t-1)\right)].$

For notational conciseness we define

$\displaystyle
E_{\alpha,i}(t-1)={\mathbb{E}}[A_{\alpha,i}(t-1){|}(Y_{t},Z_{t})=(\alpha,i)],$
$\displaystyle
p_{\alpha,i}(t)={\mathbb{P}}\left[(Y_{t},Z_{t})=(\alpha,i)\right].$

By concavity of the logarithm:

(7)
$\begin{split}H(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t},Z_{t})&\leq\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}p_{\alpha,i}(t)\log\left(E_{\alpha,i}(t-1)\right)\\\
&\stackrel{{\scriptstyle\text{\eqref{eq:q_i close to
gamma_i}}}}{{\leq}}\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(E_{\alpha,i}(t-1)\right)+2|I_{N}|\varepsilon\log(n^{2})\\\
&\leq\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(E_{\alpha,i}(t-1)\right)+16N^{2}\varepsilon\log(n).\end{split}$

In order to estimate ${\mathbb{E}}[A_{\alpha,i}(t-1)]$ we look carefully at
the positions in $\alpha_{n}$. Given $q$, each position of color $i$ in
$\alpha_{n}$ falls into exactly one of the following categories:

  * •

It is a queen in $q$.

  * •

It is not a queen, and the diagonals incident to it are unoccupied in $q$.

  * •

It is not a queen and exactly one of the diagonals incident to it is occupied
in $q$.

  * •

It is not a queen and both diagonals incident to it are occupied in $q$.

Denote the number of positions in each category by, respectively,
$C(q,\alpha,i)$, $D_{0}(q,\alpha,i)$, $D_{1}(q,\alpha,i)$, $D_{2}(q,\alpha,i)$
(for the $D$s, the subscript denotes the number of threats for each position).
Although these are random variables, the fact that $q\in
B_{n}({(\gamma_{b},\gamma_{w})},\varepsilon)$ means they cannot vary too much.
For $\alpha,i\in I_{N}\times\\{b,w\\}$ define:

$\displaystyle
D_{0}(\alpha,i)={\overline{{\gamma_{i}}}^{+}}(\alpha){\overline{{\gamma_{i}}}^{-}}(\alpha),$
$\displaystyle
D_{1}(\alpha,i)={\overline{{\gamma_{i}}}^{+}}(\alpha)\gamma_{i}^{-}(\alpha)+{\overline{{\gamma_{i}}}^{-}}(\alpha)\gamma_{i}^{+}(\alpha),$
$\displaystyle D_{2}(\alpha,i)=\gamma_{i}^{+}(\alpha)\gamma_{i}^{-}(\alpha).$

The following observation can be proved by expanding the definitions.

######  Observation 4.7.

For every $(\alpha,i)\in I_{N}\times\\{b,w\\}$ and every $0\leq t<T$:

$\sum_{j=0}^{2}D_{j}(\alpha,i)\left(1-\frac{t}{n}\right)^{j+2}=\frac{1}{4N^{2}}\left(1-\frac{t}{n}\right)^{2}\left(1-2N\gamma_{i}^{+}(\alpha)\frac{t}{n}\right)\left(1-2N\gamma_{i}^{-}(\alpha)\frac{t}{n}\right).$

######  Claim 4.8.

The following hold for every $q\in
B_{n}({(\gamma_{b},\gamma_{w})},\varepsilon)$ and every $(\alpha,i)\in
S_{N}\times\\{b,w\\}$.

$\displaystyle C(q,\alpha,i)\leq n,$ $\displaystyle
D_{0}(q,\alpha,i)=\left(D_{0}(\alpha,i)\pm O(\varepsilon)\right)n^{2},$
$\displaystyle D_{1}(q,\alpha,i)=\left(D_{1}(\alpha,i)\pm
O(\varepsilon)\right)n^{2},$ $\displaystyle
D_{2}(q,\alpha,i)=\left(D_{2}(\alpha,i)\pm O(\varepsilon)\right)n^{2}.$

###### Proof.

Let $q\in B_{n}({(\gamma_{b},\gamma_{w})},\varepsilon)$ and $(\alpha,i)\in
S_{N}\times\\{b,w\\}$. $C(q,\alpha,i)$ is the number of color $i$ queens in
$\alpha_{n}$. Since $q$ contains $n$ queens, $C(q,\alpha,i)\leq n$.

Let $P^{+},P^{-}\subseteq I_{N}$ be those elements sharing, respectively,
their plus-diagonal and minus-diagonal with $\alpha$. Then, by (4), for
$*=+,-$:

$\sum_{\beta\in P^{*}}|q_{i}\cap\beta_{n}|=\sum_{\beta\in
P^{*}}(\gamma_{i}(\beta)\pm 2\varepsilon)n=\left(\gamma_{i}^{*}(\alpha)\pm
2N\varepsilon\right)n.$

Now, every line containing an element of $\cup_{\beta\in
P^{+}}(q_{i}\cap\beta_{n})$ intersects every line containing an element of
$\cup_{\beta\in P^{-}}(q_{i}\cap\beta_{n})$ in exactly one color-$i$ square in
$\alpha_{n}$. Furthermore, every color-$i$ square in two occupied diagonals
(including the color-$i$ queens in $\alpha_{n}$) is obtained in this way.
Hence:

$\displaystyle D_{2}(q,\alpha,i)$
$\displaystyle=\left(\gamma_{i}^{+}(\alpha)\pm
2N\varepsilon\right)\left(\gamma_{i}^{-}(\alpha)\pm
2N\varepsilon\right)n^{2}\pm C(q,\alpha,i)$
$\displaystyle=\left(D_{2}(\alpha,i)\pm
2N\varepsilon(\gamma_{i}^{+}(\alpha)+\gamma_{i}^{-}(\alpha)+2N\varepsilon)\right)n^{2}\pm
n.$

Since $\gamma$ has sub-uniform diagonal marginals,
$\gamma^{+}(\alpha)+\gamma^{-}(\alpha)\leq 1/N$. Additionally, by definition,
$(N\varepsilon)^{2}<\varepsilon$ Hence:

$D_{2}(q,\alpha,i)=\left(D_{2}(\alpha,i)\pm 8\varepsilon\right)n^{2},$

as desired.

The bounds on $D_{1}(\alpha,i)$ and $D_{0}(\alpha,i)$ are proved similarly,
after noting that for $*=+,-$, the number of unoccupied $*$-diagonals of color
$i$ passing through $\alpha_{n}$ is $(1/(2N)-\gamma_{i}^{*}(\alpha)\pm
4N\varepsilon)n=(\overline{\gamma_{i}}^{*}(\alpha)\pm 4N\varepsilon)n$. ∎

Claim 4.8 allows us to estimate ${\mathbb{E}}[A_{\alpha,i}(t-1)]$. We remark
that Claim 4.8 only holds for $\alpha\in S_{N}$. The half-squares in $T_{N}$
constitute only a small part of the measure of $\gamma$ and so for them the
weak bound $A_{\alpha,i}(t-1)\leq(1+{o\left(1\right)})|\alpha_{n}|/2$ is all
we need.

######  Claim 4.9.

For every $1\leq t\leq T$ and every $\alpha,i\in S_{N}\times\\{b,w\\}$ it
holds that

$E_{\alpha,i}(t-1)=\left(1\pm
O\left(N^{2}\varepsilon\right)\right)\left(1-\frac{t}{n}\right)^{2}\left(1-2N\gamma_{i}^{+}(\alpha)\frac{t}{n}\right)\left(1-2N\gamma_{i}^{-}(\alpha)\frac{t}{n}\right)\frac{n^{2}}{4N^{2}}.$

###### Proof.

Fix $q$, $\alpha\in S_{N},i\in\\{b,w\\}$ and $1\leq t\leq T$. For $j=0,1,2$
there are $D_{j}(q,\alpha,i)$ positions in $\alpha_{n}$ that are not queens
and exactly $j$ of the diagonals incident to them are occupied. Hence, for
each position counted by $D_{j}(q,\alpha,i_{)}$, the probability that it is
available at time $t-1$ is
${\left(1\pm{o\left(1\right)}\right)}(1-t/n)^{j+2}$. Therefore:

$\displaystyle
E_{\alpha,i}(t-1)={\left(1\pm{o\left(1\right)}\right)}\sum_{j=0}^{2}\left(1-\frac{t}{n}\right)^{j+2}D_{j}(q,\alpha,i)\pm
C(q,\alpha,i)$ $\displaystyle\stackrel{{\scriptstyle\text{Claim
\ref{clm:partition by threat
number}}}}{{=}}{\left(1\pm{o\left(1\right)}\right)}\sum_{j=0}^{2}\left(1-\frac{t}{n}\right)^{j+2}\left(D_{j}(\alpha,i)\pm
O(\varepsilon)\right)n^{2}\pm n$
$\displaystyle\stackrel{{\scriptstyle\text{Observation \ref{obs:D_j weighted
sum}}}}{{=}}\left(1-\frac{t}{n}\right)^{2}\left(1-2N\gamma_{i}^{+}(\alpha)\frac{t}{n}\right)\left(1-2N\gamma_{i}^{-}(\alpha)\frac{t}{n}\right)\frac{n^{2}}{4N^{2}}\pm
O\left(\varepsilon n^{2}\right).$

Finally, since $t/n\leq T/n=1-\Omega(1)$ and $\gamma_{i}^{+}(\alpha)\leq
1/(2N)$, each of $1-t/n,1-2N\gamma_{i}^{+}(\alpha)t/n$ and
$1-2N\gamma_{i}^{-}(\alpha)t/n$ is $\Omega(1)$. Hence:

$E_{\alpha,i}(t-1)=\left(1\pm
O\left(N^{2}\varepsilon\right)\right)\left(1-\frac{t}{n}\right)^{2}\left(1-2N\gamma_{i}^{+}(\alpha)\frac{t}{n}\right)\left(1-2N\gamma_{i}^{-}(\alpha)\frac{t}{n}\right)\frac{n^{2}}{4N^{2}},$

as claimed. ∎

Continuing from (7) and using the fact that $16N^{2}\varepsilon\leq 17/N$:

$\displaystyle H$
$\displaystyle(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t},Z_{t})\leq\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(E_{\alpha,i}(t-1)\right)+16N^{2}\varepsilon\log(n)$
$\displaystyle\leq\sum_{\alpha\in
S_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log(E_{\alpha,i}(t-1))+\sum_{\alpha\in
T_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log(E_{\alpha,i}(t-1))+\frac{17}{N}\log(n).$

As mentioned above we bound the second sum using the trivial bound
$E_{\alpha,i}(t-1)\leq n^{2}$ and the fact that the half-squares in $T_{N}$
are contained in four axis parallel rectangles of width $\leq 1/(2N)$. We now
use Claim 4.9 to bound the contribution of the squares in $S_{N}$.

$\displaystyle H$ $\displaystyle(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t},Z_{t})$
$\displaystyle\leq$ $\displaystyle\sum_{\alpha\in
S_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log(E_{\alpha,i}(t-1))+\frac{4}{N}\log(n)+\frac{17}{N}\log(n)$
$\displaystyle\leq$ $\displaystyle\sum_{\alpha\in
S_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(1\pm
O(N^{2}\varepsilon)\right)+2\sum_{\alpha\in
S_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(1-\frac{t}{n}\right)$
$\displaystyle+\sum_{\alpha\in
S_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(1-2N\gamma_{i}^{+}(\alpha)\frac{t}{n}\right)+\sum_{\alpha\in
S_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(1-2N\gamma_{i}^{-}(\alpha)\frac{t}{n}\right)$
$\displaystyle+\sum_{\alpha\in
S_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(\frac{n^{2}}{4N^{2}}\right)+\frac{25}{N}\log(n).$

We will now bound the contribution of each of the terms as we sum over $t$. To
begin:

$\sum_{t=0}^{T-1}\sum_{\alpha\in
S_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(1\pm
O(N^{2}\varepsilon)\right)=O\left(N^{2}\varepsilon
T\right)=O\left(\frac{n}{N}\right).$

Next:

$\sum_{t=0}^{T-1}\sum_{\alpha\in
S_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(\frac{n^{2}}{4N^{2}}\right)\leq
n\log\left(\frac{n^{2}}{4N^{2}}\right).$

Now:

$\displaystyle\sum_{t=0}^{T-1}\sum_{\alpha\in S_{N},i\in\\{b,w\\}}$
$\displaystyle\gamma_{i}(\alpha)\log\left(1-\frac{t}{n}\right)\leq\left(1-O\left(\frac{1}{N}\right)\right)\sum_{t=1}^{T}\log\left(1-\frac{t}{n}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{Claim \ref{clm:log
integral}}}}{{\leq}}\left(1-O\left(\frac{1}{N}\right)\right)\left(-1\pm\varepsilon^{2/39}\right)n=-n\pm
O\left(\varepsilon^{2/39}n\right).$

We now note that

$\displaystyle\sum_{\alpha\in S_{N},i\in\\{b,w\\}}$
$\displaystyle\gamma_{i}(\alpha)\log\left(1-2N\gamma_{i}^{+}(\alpha)\frac{t}{n}\right)$
$\displaystyle\leq\sum_{\alpha\in
I_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(1-2N\gamma_{i}^{+}(\alpha)\frac{t}{n}\right)+\frac{4}{N}\log\left(1-\frac{T}{n}\right)$
$\displaystyle=\sum_{\alpha\in
J_{N},i\in\\{b,w\\}}\gamma_{i}^{+}(\alpha)\log\left(1-2N\gamma_{i}^{+}(\alpha)\frac{t}{n}\right)+\frac{4}{N}\log\left(1-\frac{T}{n}\right).$

Applying Claim 3.2:

$\displaystyle\sum_{t=1}^{T}$ $\displaystyle\sum_{\alpha\in
S_{N},i\in\\{b,w\\}}\gamma_{i}(\alpha)\log\left(1-2N\gamma_{i}^{+}(\alpha)\frac{t}{n}\right)$
$\displaystyle\leq-\sum_{\alpha\in
J_{N},i\in\\{b,w\\}}\frac{n}{2N}\left((1-2N\gamma_{i}^{+}(\alpha))\log(1-2N\gamma_{i}^{+}(\alpha))+2N\gamma_{i}^{+}(\alpha)\right)$
$\displaystyle\qquad+\frac{4T}{N}\log\left(1-\frac{T}{n}\right)$
$\displaystyle=-n\sum_{\alpha\in
J_{N},i\in\\{b,w\\}}{\overline{{\gamma_{i}}}^{+}}(\alpha)\log\left(2N{\overline{{\gamma_{i}}}^{+}}(\alpha)\right)-n+\frac{4T}{N}\log\left(1-\frac{T}{n}\right)$
$\displaystyle=-nD\left(\\{{\overline{{\gamma_{i}}}^{+}}(\alpha)\\}_{\alpha\in
I_{N},i\in\\{b,w\\}}\right)+n\log(2)-n+\frac{4T}{N}\log\left(1-\frac{T}{n}\right).$

Similarly:

$\displaystyle\sum_{t=1}^{T}\sum_{\alpha\in S_{N},i\in\\{b,w\\}}$
$\displaystyle\gamma_{i}(\alpha)\log\left(1-2N\gamma_{i}^{-}(\alpha)\frac{t}{n}\right)$
$\displaystyle\leq-
nD\left(\\{{\overline{{\gamma_{i}}}^{-}}(\alpha)\\}_{\alpha\in
I_{N},i\in\\{b,w\\}}\right)+n\log(2)-n+\frac{4T}{N}\log\left(1-\frac{T}{n}\right).$

As a consequence we obtain:

(8)
$\begin{split}\sum_{t=1}^{T}&H(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t},Z_{t})\\\
\leq&-nD\left(\\{{\overline{{\gamma_{i}}}^{+}}(\alpha)\\}_{\alpha\in
I_{N},i\in\\{b,w\\}}\right)-nD\left(\\{{\overline{{\gamma_{i}}}^{-}}(\alpha)\\}_{\alpha\in
I_{N},i\in\\{b,w\\}}\right)\\\
&+2n\log(2)-4n+n\log\left(\frac{n^{2}}{4N^{2}}\right)+\frac{8T}{N}\log\left(1-\frac{T}{n}\right)+O\left(\varepsilon^{2/39}n\right)\\\
\leq&-nD\left(\\{{\overline{{\gamma_{i}}}^{+}}(\alpha)\\}_{\alpha\in
I_{N},i\in\\{b,w\\}}\right)-nD\left(\\{{\overline{{\gamma_{i}}}^{-}}(\alpha)\\}_{\alpha\in
I_{N},i\in\\{b,w\\}}\right)\\\
&-2n\log(2N)-4n+2n\log(2)+2n\log\left(n\right)+O\left(\varepsilon^{2/39}n\right).\end{split}$

We are ready to prove Lemma 4.2.

###### Proof of Lemma 4.2.

By the chain rule:

$H(X_{1},\ldots,X_{n})=\sum_{t=1}^{n}H(Y_{t},Z_{t}{|}X_{1},\ldots,X_{t-1})+\sum_{t=1}^{n}H(X_{t}{|}X_{1},\ldots,X_{t-1},Y_{t},Z_{t}).$

By Claim 4.4 and using the fact that for every $t$,
$H(Y_{t},Z_{t}{|}X_{1},\ldots,X_{t-1})\leq\log(2|I_{N}|)$:

$\displaystyle\sum_{t=1}^{n}H(Y_{t},Z_{t}{|}X_{1},\ldots,X_{t-1})\leq-
nD^{N}{(\gamma_{b},\gamma_{w})}+2n\log(2N)+O\left(\varepsilon^{2/39}n\right).$

Together with (8) this implies

$\displaystyle H$ $\displaystyle(X_{1},\ldots,X_{n})\leq$ $\displaystyle-
nD^{N}{(\gamma_{b},\gamma_{w})}-nD\left(\\{{\overline{{\gamma_{i}}}^{+}}(\alpha)\\}_{\alpha\in
I_{N},i\in\\{b,w\\}}\right)-nD\left(\\{{\overline{{\gamma_{i}}}^{-}}(\alpha)\\}_{\alpha\in
I_{N},i\in\\{b,w\\}}\right)$
$\displaystyle-4n+2n\log\left(n\right)+2n\log(2)+O\left(\varepsilon^{2/39}n\right)$
$\displaystyle=$ $\displaystyle
nG^{N}{(\gamma_{b},\gamma_{w})}+2n\log(n)-n+O\left(\varepsilon^{2/39}n\right)$
$\displaystyle=$ $\displaystyle
nG^{N}{(\gamma_{b},\gamma_{w})}+n\log(n)+\log(n!)+\varepsilon^{1/100}n.$

Therefore, by (3):

$\log\left(|B_{n}({(\gamma_{b},\gamma_{w})},\varepsilon)|\right)=H(X_{1},\ldots,X_{n})-\log(n!)\leq
nG^{N}{(\gamma_{b},\gamma_{w})}+n\log(n)+\varepsilon^{1/100}n.$

Hence

$\frac{|B_{n}({(\gamma_{b},\gamma_{w})},\varepsilon)|^{1/n}}{n}\leq\exp\left(G^{N}{(\gamma_{b},\gamma_{w})}+\varepsilon^{1/100}\right),$

proving the lemma. ∎

We will now use Lemma 4.2 to prove the upper bound in Theorem 2.11.

###### Proof of Theorem 2.11 upper bound.

Define

$X\coloneqq\left\\{{(\gamma_{b},\gamma_{w})}\in\mathbf{BW}:{d_{\diamond}\left({\gamma_{b}+\gamma_{w}},{\gamma}\right)}\leq\varepsilon\right\\}.$

Note that $X\subseteq\mathbf{BW}$ is closed and therefore compact. Let
$(\gamma_{b}^{1},\gamma_{w}^{1}),\ldots,(\gamma_{b}^{M},\gamma_{w}^{M})\in X$
be such that
$X\subseteq\cup_{i=1}^{M}B_{\varepsilon}(\gamma_{b}^{i},\gamma_{w}^{i})$.
Observe that

$B_{n}(\gamma,\varepsilon)\subseteq\bigcup_{i=1}^{M}B_{n}((\gamma_{b}^{i},\gamma_{w}^{i}),\varepsilon).$

Now, by Lemma 4.2, for each $i$:

$|B_{n}((\gamma_{b}^{i},\gamma_{w}^{i}),\varepsilon)|\leq
n^{n}\exp\left(n\left(G^{N}(\gamma_{b}^{i},\gamma_{w}^{i})+\varepsilon^{1/100}+{o\left(1\right)}\right)\right)$

where $N=\lfloor\varepsilon^{-1/3}\rfloor$. By Observation 4.3
$G^{N}(\gamma_{b}^{i},\gamma_{w}^{i})\leq
H_{q}^{N}(\gamma_{b}^{i}+\gamma_{w}^{i})$. Since
$(\gamma_{b}^{i},\gamma_{w}^{i})\in X$ by definition
${d_{\diamond}\left({\gamma_{b}^{i}+\gamma_{w}^{i}},{\gamma}\right)}\leq\varepsilon$.
Therefore by Claim 3.1 ${H_{q}^{N}(\gamma_{b}^{i}+\gamma_{w}^{i})}\leq
H_{q}^{N}(\gamma)+\varepsilon^{1/4}$. Therefore, for every $1\leq i\leq M$:

$\displaystyle\frac{|B_{n}((\gamma_{b}^{i},\gamma_{w}^{i}),\varepsilon)|}{n^{n}}$
$\displaystyle\leq\exp\left(n\left(H_{q}^{N}(\gamma)+\varepsilon^{1/4}+\varepsilon^{1/100}+{o\left(1\right)}\right)\right)$
$\displaystyle\leq\exp\left(n\left(H_{q}^{N}(\gamma_{N})+2\varepsilon^{1/100}\right)\right).$

Therefore:

$\frac{|B_{n}(\gamma,\varepsilon)|}{n^{n}}\leq
M\exp\left(n\left(H_{q}^{N}(\gamma)+2\varepsilon^{1/100}\right)\right)\leq\exp\left(n\left(H_{q}^{N}(\gamma)+\varepsilon^{1/200}\right)\right),$

proving the theorem. ∎

##  5\. Lower bound

In this section we prove the lower bound in Theorem 2.11.

Let $\gamma$ be a queenon, let $\varepsilon>0$, and let $n\in\mathbb{N}$. We
may assume $H_{q}(\gamma)>-\infty$. We will describe a randomized algorithm
that constructs an element of $B_{n}(\gamma,\varepsilon)$. We will derive the
lower bound by counting the number of possible outcomes.

The algorithm has two phases: a random phase, in which most of the queens are
placed on the board, and a correction phase, in which a small number of
modifications are made to obtain a complete solution.

It is helpful to replace $\gamma$ with a queenon that is close to $\gamma$ and
has some additional desirable properties. For a natural number
$\tilde{N}\geq\varepsilon^{-2}$ let $\tilde{\gamma}$ be a $\tilde{N}$-step
queenon satisfying $H_{q}(\tilde{\gamma})\geq H_{q}(\gamma)-\varepsilon^{2}$
and ${d_{\diamond}\left({\tilde{\gamma}},{\gamma}\right)}<\varepsilon^{2}$.
Let $\kappa$ be the queenon whose density function is the step function

$\begin{bmatrix}0.9&1.2&0.9\\\ 1.2&0.6&1.2\\\ 0.9&1.2&0.9\end{bmatrix}.$

Let $\varepsilon^{2}>\rho>0$ be small enough that
$H_{q}((1-\rho)\tilde{\gamma}+\rho\kappa)>(1-\varepsilon)H_{q}(\gamma)$. Set

$\delta\coloneqq(1-\rho)\tilde{\gamma}+\rho\kappa.$

We now list the properties of $\delta$ that are useful for our proof.

######  Observation 5.1.

The following hold.

  1. (a)

${d_{\diamond}\left({\gamma},{\delta}\right)}=O(\varepsilon^{2})$.

  2. (b)

For $N\coloneqq 3\tilde{N}$, $\delta$ is an $N$-step queenon.

  3. (c)

$\delta$ has density $\Theta(1)$ everywhere. Indeed, $\delta$ has density
bounded below by $0.6\rho$ and bounded above by the maximal density of
$\kappa$ and $\tilde{\gamma}$.

  4. (d)

There exists a constant $\eta<1$ such that ${\overline{{\delta}}^{+}}$ and
${\overline{{\delta}}^{-}}$ have density $\leq\eta$ everywhere.

The fact that $\delta$ has positive density everywhere will make it easier to
find the absorbers required for the correction phase of the algorithm.
Additionally, (d) ensures that every diagonal has at most constant probability
of being occupied in the random phase of the algorithm.

Choose a sufficiently large $K\in\mathbb{N}$ (that may depend on $\varepsilon$
and $\gamma$ but not on $n$) and define:

$M\coloneqq\lfloor n^{0.1}\rfloor N,\quad T\coloneqq n-\lfloor
n^{1-1/K^{2}}\rfloor,$

Observe that because $N$ divides $M$, $\delta$ is an $M$-step queenon. We now
describe the first phase of the algorithm.

######  Algorithm 5.2.

  * •

Let $Y_{1},Y_{2},\ldots,Y_{T}\in I_{M}$ be i.i.d. random variables, where for
every $\alpha\in I_{M}$, ${\mathbb{P}}[Y_{1}=\alpha]=\delta(\alpha)$.

  * •

Set $Q(0)=\emptyset$.

  * •

For every $0<t\leq T$:

    * –

Let ${\mathcal{A}}_{Y_{t}}(t-1)$ be the set of available positions in $Y_{t}$.
If ${\mathcal{A}}_{Y_{t}}(t-1)=\emptyset$ abort and define
$X_{t}=X_{t+1}=\ldots=X_{T}=*$.

    * –

Otherwise, choose $X_{t}\in{\mathcal{A}}_{Y_{t}}(t-1)$ uniformly at random and
set $Q(t)=Q(t-1)\cup\\{X_{t}\\}$.

We will show that w.h.p. Algorithm 5.2 does not abort. We will also calculate
the entropy $H(X_{t}{|}X_{1},\ldots,X_{t-1})$ which will allow us to estimate
the number of possible outcomes. By design, the number of queens placed in
each $\alpha\in I_{M}$ is $\approx\gamma(\alpha)n$. Hence, we expect that any
queen configuration close to $Q(T)$ (i.e., the outcome of Algorithm 5.2) is an
element of $B_{n}(\gamma,\varepsilon)$.

In the second phase of the algorithm we seek to make a small number of
modifications to $Q(T)$ in order to obtain an $n$-queens configuration. The
key is the idea of absorption, which we now illustrate: Suppose $Q$ is a
partial $n$-queens configuration that does not cover row $r$ and column $c$.
We wish to obtain a partial $n$-queens configuration $Q^{\prime}$ that covers
all rows and columns covered by $Q$, and also covers row $r$ and column $c$.
We might try adding $(c,r)$ to $Q$, but if either of the diagonals incident to
$(c,r)$ is occupied this will not work. Instead, we look for a queen $(x,y)\in
Q$ satisfying:

  1. (a)

$(c,y)$ and $(x,r)$ do not share a diagonal (equivalently, $(c,r)$ and $(x,y)$
do not share a diagonal),

  2. (b)

none of the (four) diagonals containing $(c,y)$ or $(x,r)$ are occupied.

Supposing such a queen exists, we observe that
$Q^{\prime}\coloneqq\left(Q\setminus\\{(x,y)\\}\right)\cup\\{(c,y),(x,r)\\}$
is a partial $n$-queens configuration satisfying the conditions above. In this
way, we have absorbed row $r$ and column $c$ into our configuration. We call
such a queen an absorber for $(c,r)$ in $Q$ (see Figure 3). We denote the set
of absorbers for $(c,r)$ in $Q$ by ${\mathcal{B}}_{Q}(c,r)$.

[ showmover=false,labelbottomformat=0, setwhite=qa4, qb7, qc1,
qg3,addblack=qh8] [ showmover=false,labelbottomformat=0, setwhite=qa4, qb7,
qc1, qg3,addblack=qd8,qh5]

Figure 3. In the partial $8$-queens configuration on the left the black queen
at $(8,8)$ is an absorber for the square $(4,5)$. In the configuration on the
right the queen at $(8,8)$ has been removed, while the black queens at $(4,8)$
and $(8,5)$ have been added, thus absorbing row $5$ and column $4$ into the
configuration.

The following algorithm attempts to use absorbers to complete $Q(T)$.

######  Algorithm 5.3.

  * •

Let $L_{R}$ and $L_{C}$ be, respectively, the sets of rows and columns not
covered by $Q(T)$. Note that $|L_{R}|=|L_{C}|\eqqcolon k$.

  * •

Let $(c_{1},r_{1}),(c_{2},r_{2}),\ldots,(c_{k},r_{k})$ be an arbitrary
matching of $L_{C}$ to $L_{R}$.

  * •

Set $R(0)\coloneqq Q(T)$.

  * •

For $i=1,2,\ldots,k$:

    * –

If ${\mathcal{B}}_{i}\coloneqq{\mathcal{B}}_{R(i-1)}(c_{i},r_{i})=\emptyset$
abort.

    * –

Otherwise, choose some $(x_{i},y_{i})\in{\mathcal{B}}_{i}$ and set

$R(i)\coloneqq\left(R(i-1)\setminus\\{(x_{i},y_{i})\\}\right)\cup\\{(x_{i},r_{i}),(c_{i},y_{i})\\}.$

Clearly, if Algorithm 5.3 does not abort then $R(k)$ is an $n$-queens
configuration. In Section 5.2 we show that w.h.p. $Q(T)$ satisfies a
combinatorial condition that guarantees the success of Algorithm 5.3.

######  Remark 5.4.

The absorption procedure described above was introduced in [19]. There, it was
used in combination with a simple random greedy algorithm to show that
${\mathcal{Q}}(n)\geq((1-{o\left(1\right)}))ne^{-3})^{n}$. While the analysis
of Algorithm 5.3 shares some details with [19], there are additional
difficulties due to the fact that $\gamma$ may be far from uniform.

We analyze Algorithm 5.2 in Section 5.1. We analyze Algorithm 5.3 in Section
5.2. Then, in Section 5.3 we put everything together and prove the lower bound
in Theorem 2.11.

###  5.1. Analysis of Algorithm 5.2

The analysis of Algorithm 5.2 is somewhat technical and calls for some
motivation. The overarching intuition is that because each $Y_{t}$ is
distributed according to $\\{\gamma(\alpha)\\}_{\alpha\in I_{M}}$, after $t$
steps of the process approximately $\gamma(\alpha)t$ queens have been placed
in $\alpha_{n}$. Thus, $Q(t)$ “looks like” a random size-$t$ subset of a
random element of $B_{n}(\delta,\varepsilon)$. Indeed, an outside observer may
not know if the process $\\{Q(t)\\}_{t=0}^{T}$ is governed by Algorithm 5.2 or
by choosing $q\in B_{n}(\gamma,\varepsilon)$ uniformly at random and revealing
its queens in a random order (though this is not literally true in an
information-theoretic sense).

In order to analyze Algorithm 5.2 we need to track the distribution of
available positions on the board. For example, we will need to know the number
of available positions in each row. Our general strategy is to track random
variables by showing they are close to smooth trajectory functions. However,
this means we cannot track available positions directly: Whenever a queen is
added to a row the number of available positions it contains jumps down to
zero. Thus, we cannot expect this random variable to follow a smooth
trajectory. To overcome this we define a related notion.

######  Definition 5.5.

Let $Q$ be a partial $n$-queens configuration. A position $(x,y)\in[n]^{2}$ is
row-safe in $Q$ if the column and both diagonals incident to it are
unoccupied. It is column-safe if the row and both diagonals incident to it are
unoccupied in and it is plus (minus)-safe if the row, column, and minus
(plus)-diagonal incident to it are unoccupied.

Observe that a position is available if and only if it is row-safe and its row
is unoccupied. Analogous statements hold for column, plus-, and minus-safe
positions.

We will track the number of safe positions located in small strips of the
board.

Let $\alpha\in I_{M}$ and let $(x,y)\in[n]^{2}$. Let
${\mathcal{R}}_{y,\alpha}(t)$ be the set of row safe positions in $Q(t)$ that
are in row $y$ and in $\alpha_{n}$. Let ${\mathcal{C}}_{x,\alpha}(t)$ be the
set of column-safe positions in $Q(t)$ in column $x$ and in $\alpha_{n}$. Let
${\mathcal{D}}^{+}_{x+y,\alpha}(t)$ (${\mathcal{D}}^{-}_{y-x,\alpha}(t)$) be
the set of plus- (minus-)safe positions in $Q(t)$ in plus- (minus-)diagonal
$x+y$ ($y-x$) and in $\alpha_{n}$. Finally, let ${\mathcal{Z}}_{\alpha}(t)$ be
the set of unoccupied plus-diagonals incident to $\alpha_{n}$.

For each of these (random) sets, which are denoted using stylized Latin
letters, we use the capital Latin letter equivalent for its cardinality. For
example, $R_{y,\alpha}(t)=|{\mathcal{R}}_{y,\alpha}(t)|$. For $\alpha\in
I_{M}$ we also define
${\mathcal{A}}_{\alpha}(t)\coloneqq\alpha_{n}\cap{\mathcal{A}}_{Q(t)}$ and
$A_{\alpha}(t)=|{\mathcal{A}}_{\alpha}(t)|$.

We now define the expected trajectories of these random variables. Let
$(x,y)\in[n]^{2}$ and $\alpha\in I_{M}$. Recall the definitions of
$L_{y,\alpha}^{r},L_{x,\alpha}^{c},L_{x+y,\alpha}^{+},$ and
$L_{x-y,\alpha}^{-}$ from Section 1.2. For $t\in[0,T]$ define:

$\displaystyle
r_{y,\alpha}(t)=L^{r}_{y,\alpha}\left(1-\frac{t}{n}\right)\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right),$
$\displaystyle
c_{x,\alpha}(t)=L^{c}_{x,\alpha}\left(1-\frac{t}{n}\right)\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right),$
$\displaystyle
d_{x+y,\alpha}^{+}(t)=L_{x+y,\alpha}^{+}\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right),$
$\displaystyle
d_{x-y,\alpha}^{-}(t)=L_{x-y,\alpha}^{-}\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right),$
$\displaystyle
z_{\alpha}(t)=\frac{n}{M}\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right).$

We also define the error function:

$E(t)=\frac{n}{M^{5/4}(1-t/n)^{K}}$

(where $K$ is the (large) constant used to define $T$).

We will use a differential equation method [29] style martingale analysis to
show that w.h.p. the random variables above closely follow their trajectories.
Informally, the method states that if a sequence of random variables
$F(0),F(1),\ldots,F(T)$ and a smooth function $f:[0,T]\to\mathbb{R}$ satisfy:

  * •

Initial condition: $F(0)\approx f(0)$;

  * •

Trajectory condition: For every $t<T$,
${\mathbb{E}}[F(t+1)-F(t){|}F(t)]\approx f^{\prime}(t)$; and

  * •

Boundedness condition: There exists a constant $C$ such that
${\lVert{f^{\prime}}\rVert}_{\infty}\leq C$ and $|F(t+1)-F(t)|\leq C$;

then w.h.p. $F(t)\approx f(t)$.

In general, it may not be the case that the expected one-step changes in the
random variables we have defined are close to the derivatives of their
respective trajectories. However, we will show that this is the case for as
long as they remain close to their trajectories. This motivates the next
definition.

######  Definition 5.6.

Let the stopping time $0<\tau\leq T$ be the smallest $t$ such that one of the
random variables deviates by more than $E(t)$ from its expected trajectory.
That is, $\tau$ is the smallest $t$ such that there exists some
$(x,y)\in[n]^{2}$ and $\alpha\in I_{M}$ such that at least one of

$\displaystyle|R_{y,\alpha}(t)-r_{y,\alpha}(t)|,|C_{x,\alpha}(t)-c_{x,\alpha}(t)|,|D^{+}_{x+y,\alpha}(t)-d^{+}_{x+y,\alpha}(t)|,$
$\displaystyle|D^{-}_{x-y,\alpha}(t)-d^{-}_{x-y}(t)|,|{\mathcal{Z}}_{\alpha}(t)-z_{\alpha}(t)|$

is larger than $E(t)$. If there is no such $t$ set $\tau=\infty$.

Most of this section is devoted to proving the next proposition, which implies
that w.h.p. Algorithm 5.2 does not abort.

######  Proposition 5.7.

${\mathbb{P}}\left[\tau<\infty\right]=\exp\left(-\Omega\left(n^{0.75}\right)\right).$

Before proving Proposition 5.7 we show how the assumption that $\tau>t$ allows
us to estimate other parameters of the process at time $t$.

Recall that $S_{M}\cup T_{M}$ is the partition of $I_{M}$ into squares and
half-squares.

######  Claim 5.8.

Suppose that $\tau>t$. Then, for every $\alpha\in S_{M}$:

$\displaystyle A_{\alpha}(t)$
$\displaystyle=|\alpha_{n}|\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)\pm\frac{3nE(t)}{M}$
$\displaystyle=\left(1\pm\frac{10ME(t)}{(1-\eta)^{2}n(1-t/n)^{2}}\right)|\alpha_{n}|\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right).$

Additionally, for every $\alpha\in I_{M}$:

$A_{\alpha}(t)\geq\frac{n^{2}}{40M^{2}}(1-\eta)^{3}\left(1-\frac{t}{n}\right)^{2}.$

###### Proof.

Let $\alpha\in I_{M}$. By definition:

$\displaystyle A_{\alpha}(t)$
$\displaystyle=\sum_{c\in{\mathcal{Z}}_{\alpha}(t)}D_{c,\alpha}^{+}(t)\stackrel{{\scriptstyle\tau>t}}{{=}}\sum_{c\in{\mathcal{Z}}_{\alpha}(t)}\left(d_{c,\alpha}^{+}(t)\pm
E(t)\right)$
$\displaystyle=\sum_{c\in{\mathcal{Z}}_{\alpha}\alpha(t)}L_{c,\alpha}^{+}\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)\pm
Z_{\alpha}(t)E(t).$

Now, because $\tau>t$, $Z_{\alpha}(t)\leq z_{\alpha}(t)+E(t)\leq 2n/M$. If
$\alpha\in S_{M}$ then, for every plus-diagonal $c$ incident to $\alpha_{n}$,
$L_{c,\alpha}^{+}=n/(2M)\pm O(1)=(1\pm O(M/n))n/(2M)$. Therefore, in this
case:

$\displaystyle A_{\alpha}(t)$ $\displaystyle=\left(z_{\alpha}(t)\pm
E(t)\right)\left(1\pm
O\left(\frac{M}{n}\right)\right)\frac{n}{2M}\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)\pm\frac{2nE(t)}{M}$
$\displaystyle=\frac{n^{2}}{2M^{2}}\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)\pm\frac{3nE(t)}{M}.$

Since $\alpha\in S_{N}$, $|\alpha_{n}|=n^{2}/(2M^{2})\pm O(n/M)$, proving the
first assertion. This also proves the second assertion in the case that
$\alpha\in S_{M}$.

We now consider $\alpha\in T_{M}$. Of the $Z_{\alpha}(t)$ unoccupied diagonals
incident to $\alpha_{n}$, at least $Z_{\alpha}(t)/2$ satisfy
$L_{c,\alpha}^{+}\geq Z_{\alpha}(t)/4$. Therefore:

$A_{\alpha}(t)\geq\frac{Z_{\alpha}(t)^{2}}{10}\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)\geq\frac{Z_{\alpha}(t)^{2}}{10}(1-\eta)\left(1-\frac{t}{n}\right)^{2}.$

Since $\tau>t$, $Z_{\alpha}(t)\geq(1-\eta)n/(2M)$. Therefore:

$A_{\alpha}(t)\geq\frac{n^{2}}{40M^{2}}(1-\eta)^{3}\left(1-\frac{t}{n}\right)^{2},$

completing the proof. ∎

The next claim shows that for as long as $\tau>t$, every unoccupied row and
column is approximately equally likely to be occupied in each step.

######  Claim 5.9.

Suppose that $\tau>t$. Then, for every unoccupied row or column in $Q(t)$, the
probability that it is occupied in $Q(t+1)$ is

$\frac{1}{n-t}\pm O\left(\frac{ME(t)}{(n-t)^{2}}\right).$

###### Proof.

By symmetry it suffices to prove only the statement for unoccupied rows.

Let $y\in[n]$. For $0\leq t\leq T$ let $B(t)$ be the event that row $y$ is
occupied in $Q(t)$. Given $Q(t)$ such that row $y$ is unoccupied (i.e., $B(t)$
does not hold), we have

${\mathbb{P}}[B(t+1){|}Q(t)]=\sum_{x=1}^{n}{\mathbb{P}}\left[X_{t}=(x,y){|}Q(t)\right]=\sum_{\alpha\in
I_{M}}\frac{\delta(\alpha)R_{y,\alpha}(t)}{A_{\alpha}(t)}.$

If $\tau>t$ then for every $\alpha$ we have
$R_{y,\alpha}(t)=r_{y,\alpha}(t)\pm E(t)\leq 4n(1-t/n)/M$ and (by Claim 5.8)
for $C=10/(1-\eta)^{2}$ and $\alpha\in S_{M}$:

$A_{\alpha}(t)=\left(1\pm\frac{CME(t)}{n(1-t/n)^{2}}\right)|\alpha_{n}|\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right).$

Additionally, for $D=(1-\eta)^{3}/40$ every $\alpha\in I_{M}$:

$A_{\alpha}(t)\geq\frac{Dn^{2}}{M^{2}}\left(1-\frac{t}{n}\right)^{2}.$

Therefore:

$\displaystyle{\mathbb{P}}$
$\displaystyle\left[B(t+1){|}B^{c}(t)\land\tau>t\right]$ $\displaystyle=$
$\displaystyle\left(1\pm\frac{CME(t)}{n-t}\right)\sum_{\alpha\in
S_{M}:L_{y,\alpha}^{r}>0}\frac{\delta(\alpha)\left(L^{r}_{y,\alpha}\left(1-\frac{t}{n}\right)\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)\pm
E(t)\right)}{|\alpha_{n}|\left(1-t/n\right)^{2}\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}$
$\displaystyle\pm\sum_{\alpha\in
T_{M}:L_{y,\alpha}^{r}>0}\frac{\delta(\alpha)4n(1-t/n)/M}{Dn^{2}(1-t/n)^{2}/M^{2}}$
$\displaystyle=$
$\displaystyle\left(1\pm\frac{CME(t)}{n-t}\right)\sum_{\alpha\in
S_{M}}\frac{\delta(\alpha)L^{r}_{y,\alpha}}{|\alpha_{n}|\left(1-t/n\right)}\pm\frac{M^{2}E(t)}{Dn^{2}(1-t/n)^{2}}\sum_{\alpha\in
S_{M}:L_{y,\alpha}^{r}>0}\delta(\alpha)$
$\displaystyle\pm\frac{4M}{Dn(1-t/n)}\sum_{\alpha\in
T_{M}:L_{y,\alpha}^{r}>0}\delta(\alpha).$

Observe that the set of $\alpha\in I_{M}$ such that $L_{y,\alpha}>0$ all
intersect row $y$. Therefore these sets are all contained in an axis parallel
rectangle of height $\leq 4/M$. Since $\delta$ has uniform marginals, we have
$\sum_{\alpha\in I_{M}:L_{y,\alpha}>0}\delta(\alpha)\leq 4/M$. Therefore:

$\frac{M^{2}E(t)}{Dn^{2}(1-t/n)^{2}}\sum_{\alpha\in
S_{M}:L_{y,\alpha}^{r}>0}\delta(\alpha)\leq\frac{4ME(t)}{Dn^{2}(1-t/n)^{2}}.$

Additionally, there are only $O(1)$ half-squares $\alpha\in T_{M}$ that
intersect row $y$. For each such $\alpha$, we have
$\delta(\alpha)=O(1/M^{2})$. Hence:

$\frac{4M}{Dn(1-t/n)}\sum_{\alpha\in
T_{M}:L_{y,\alpha}^{r}>0}\delta(\alpha)=O\left(\frac{1}{Mn(1-t/n)}\right).$

We turn our attention to the first sum. By Claim 3.3 (a):

$\sum_{\alpha\in
S_{M}}\frac{\delta(\alpha)L_{y,\alpha}^{r}}{|\alpha_{n}|}=\sum_{\alpha\in
I_{M}}\frac{\delta(\alpha)L^{r}_{y,\alpha}}{|\alpha_{n}|}-\sum_{\alpha\in
T_{M}}\frac{\delta(\alpha)L_{y,\alpha}^{r}}{|\alpha_{n}|}=\frac{1}{n}\pm
O\left(\frac{1}{nM}\right).$

Therefore

$\displaystyle\left(1\pm\frac{CME(t)}{n-t}\right)$
$\displaystyle\sum_{\alpha\in
S_{M}}\frac{\delta(\alpha)L^{r}_{y,\alpha}}{|\alpha_{n}|\left(1-t/n\right)}=\left(1\pm\frac{CME(t)}{n-t}\right)\left(1\pm
O\left(\frac{1}{M}\right)\right)\frac{1}{n-t}$
$\displaystyle=\left(1\pm\frac{2CME(t)}{n-t}\right)\frac{1}{n-t}=\frac{1}{n-t}\pm\frac{2CME(t)}{(n-t)^{2}}.$

Therefore:

$\displaystyle{\mathbb{P}}\left[B(t+1){|}B^{c}(t)\land\tau>t\right]$
$\displaystyle=\frac{1}{n-t}\pm\left(\frac{2CME(t)}{(n-t)^{2}}+\frac{4ME(t)}{D(n-t)^{2}}+\frac{1}{M(n-t)}\right)$
$\displaystyle=\frac{1}{n-t}\pm O\left(\frac{ME(t)}{(n-t)^{2}}\right),$

as desired. ∎

######  Claim 5.10.

Let $*\in\\{+,-\\}$. Suppose that $\tau>t$ and that $*$-diagonal $c$, which
intersects $\alpha_{n}$, is unoccupied in $Q(t)$. Then, the probability that
$*$-diagonal $c$ is occupied in $Q(t+1)$ is

$\frac{M\delta^{*}(\alpha)}{n\left(1-M\delta^{*}(\alpha)\frac{t}{n}\right)}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right).$

The term $M\delta^{*}(\alpha)/(n-M\delta^{*}(\alpha)t)$ can be interpreted as
follows: In a configuration $q\in B_{n}(\delta,\varepsilon)$, approximately
$nM\delta^{*}(\alpha)$ of the $*$-diagonals passing through $\alpha_{n}$ are
occupied. Thus, after $t$ steps of the process, the probability that the next
queen placed should occupy one of these diagonals is proportional to
$M\delta^{*}(\alpha)$ (i.e., the fraction of the $*$-diagonals that pass
through $\alpha_{n}$) and also $1/(n-M\delta^{*}(\alpha)t)$ (i.e., the inverse
of the number of remaining unoccupied diagonals that pass through
$\alpha_{n}$).

###### Proof.

The proof is similar to that of Claim 5.9. We prove only the case $*=+$. For
$0\leq t\leq T$ let $B(t)$ be the event that plus-diagonal $c$ is occupied in
$Q(t)$. Given $Q(t)$ such that plus-diagonal $c$ is unoccupied, we have

${\mathbb{P}}\left[B(t+1){|}Q(t)\right]=\sum_{\beta\in
I_{M}}\frac{\delta(\beta)D^{+}_{c,\beta}(t)}{A_{\beta}(t)}.$

If $\tau>t$ we have, for $C=10/(1-\eta)^{2}$:

$\displaystyle{\mathbb{P}}$
$\displaystyle\left[B(t+1){|}B^{c}(t)\land\tau>t\right]$ $\displaystyle=$
$\displaystyle\left(1\pm\frac{CME(t)}{n(1-t/n)^{2}}\right)\sum_{\beta\in
S_{M}}\frac{\delta(\beta)\left(L^{+}_{c,\beta}\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{-}(\beta)\frac{t}{n}\right)\pm
E(t)\right)}{|\beta_{n}|\left(1-t/n\right)^{2}\left(1-M\delta^{+}(\beta)\frac{t}{n}\right)\left(1-M\delta^{-}(\beta)\frac{t}{n}\right)}\pm
O\left(\frac{1}{M(n-t)}\right)$ $\displaystyle=$
$\displaystyle\left(1\pm\frac{CME(t)}{n(1-t/n)^{2}}\right)\sum_{\beta\in
S_{M}}\frac{\delta(\beta)L^{+}_{c,\beta}}{|\beta_{n}|\left(1-M\delta^{+}(\beta)\frac{t}{n}\right)}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right).$

We note that for every $\beta\in I_{M}$ such that $L_{c,\beta}^{+}>0$ it holds
that $\delta^{+}(\beta)=\delta^{+}(\alpha)$. Therefore, by Claim 3.3 (c) and
(d):

$\displaystyle\sum_{\beta\in
S_{M}}\frac{\delta(\beta)L^{+}_{c,\beta}}{|\beta_{n}|\left(1-M\delta^{+}(\beta)\frac{t}{n}\right)}$
$\displaystyle=\frac{1}{1-M\delta^{+}(\alpha)\frac{t}{n}}\sum_{\beta\in
I_{M}}\frac{\delta(\beta)L^{+}_{c,\beta}}{|\beta_{n}|}\pm
O\left(\frac{1}{Mn}\right)$
$\displaystyle=\frac{M\delta^{+}(\alpha)}{n-M\delta^{+}(\alpha)t}\pm
O\left(\frac{1}{Mn}\right).$

Hence:

$\displaystyle{\mathbb{P}}\left[B(t+1){|}B^{c}(t)\land\tau>t\right]$
$\displaystyle=\left(1\pm\frac{CME(t)}{n-t}\right)\frac{M\delta^{+}(\alpha)}{n-M\delta^{+}(\alpha)t}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right)$
$\displaystyle=\frac{M\delta^{+}(\alpha)}{n-M\delta^{+}(\alpha)t}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right),$

as desired. ∎

We now transform the random variables so that we can apply a martingale
analysis. Let $X(t)$ be one of the random variables in

$\\{R_{y,\alpha}(t),C_{x,\alpha}(t),D^{+}_{x+y,\alpha}(t),D^{-}_{x-y,\alpha}(t),Z_{\alpha}(t):\alpha\in
I_{M},(x,y)\in[n]^{2},0\leq t\leq T\\}.$

We write the corresponding trajectory function as $x(t)$ (for example, if
$X(t)=R_{y,\alpha}(t)$ then $x(t)=r_{y,\alpha}(t)$). Define the following
random variables:

$\displaystyle X^{+}(t)=\begin{cases}X(t)-x(t)-\frac{1}{2}E(t)&t\leq\tau\\\
X^{+}(t-1)&t>\tau.\end{cases},$ $\displaystyle
X^{-}(t)=\begin{cases}x(t)-X(t)-\frac{1}{2}E(t)&t\leq\tau\\\
X^{-}(t-1)&t>\tau\end{cases}.$

We will show that these sequences are supermartingales with respect to the
filtration induced by $Q(0),Q(1),\ldots,Q(T)$. We will then apply the Azuma-
Hoeffding inequality to show that they closely follow their trajectories. This
will imply Proposition 5.7.

As we have seen in Claims 5.9 and 5.10, conditioning on $\tau>t$ implies that
a certain regularity holds at time $t$. This makes it easy to calculate
expected one-step changes. This motivates freezing the random variables at the
stopping time $\tau$.

We will use the following version of the Azuma-Hoeffding inequality.

######  Theorem 5.11 ([28, Lemma 1]).

Let $X_{0},X_{1},\ldots$ be a supermartingale with respect to a filtration
${\mathcal{F}}_{0},{\mathcal{F}}_{1},\ldots$. Let $C>0$ satisfy
$C\geq|X_{i}-X_{i-1}|$ for every $i$. Then, for every $\lambda>0$ and $t\geq
0$, it holds that

${\mathbb{P}}\left[X_{t}\geq
X_{0}+\lambda\right]\leq\exp\left(-\frac{\lambda^{2}}{2tC^{2}}\right).$

The next lemma establishes the boundedness condition required by Theorem 5.11.

######  Lemma 5.12.

Let $\\{X(t)\\}_{t=0}^{T}$ be one of the sequences $\\{R_{y,\alpha}(t)\\}$,
$\\{C_{x,\alpha}(t)\\}$, $\\{D^{+}_{x+y,\alpha}(t)\\}$,
$\\{D^{-}_{x-y,\alpha}(t)\\}$, $\\{Z_{\alpha}(t)\\}$, for $(x,y)\in[n]^{2}$
and $\alpha\in I_{M}$. Then, for every $0\leq t<T$:

$|X^{+}(t+1)-X^{+}(t)|,|X^{-}(t+1)-X^{-}(t)|=O(1).$

###### Proof.

Let $(x,y)\in[n]^{2}$ and $\alpha\in I_{M}$.

We first note that the derivatives of the functions $r_{y,\alpha}$,
$c_{x,\alpha}$, $d^{+}_{x+y,\alpha}$, $d^{-}_{y-x,\alpha}$, and $E$ are
bounded in absolute value by $1$.

Next, we observe that whenever a queen is added to a partial $n$-queens
configuration, exactly one row, one column, one plus-diagonal, and one minus-
diagonal are occupied. Thus, in every time step, each of $\\{R_{y,\alpha}\\}$,
$\\{C_{x,\alpha}\\}$, $\\{D^{+}_{x+y,\alpha}\\}$, $\\{D^{-}_{x-y,\alpha}\\}$,
$\\{Z_{\alpha}\\}$ changes by at most $3$.

Together, these observations imply that $X^{+}$ and $X^{-}$ can change by at
most $5$ in every time step. ∎

The next step is to show that the random variables are supermartingales.

######  Lemma 5.13.

Let $\\{X(t)\\}_{t=0}^{T}$ be one of the sequences $\\{R_{y,\alpha}(t)\\}$,
$\\{C_{x,\alpha}(t)\\}$, $\\{D^{+}_{x+y,\alpha}(t)\\}$,
$\\{D^{-}_{x-y,\alpha}(t)\\}$, $\\{Z_{\alpha}(t)\\}$, for $(x,y)\in[n]^{2}$
and $\alpha\in I_{M}$. Then, for every $0\leq t<T$:

${\mathbb{E}}\left[X^{+}(t+1)-X^{+}(t){|}Q(t)\right]\leq 0$

and

${\mathbb{E}}\left[X^{-}(t+1)-X^{-}(t){|}Q(t)\right]\leq 0.$

Before proving Lemma 5.13 we calculate the expected one step changes of our
random variables.

######  Claim 5.14.

Let $(x,y)\in[n]^{2}$, $\alpha\in I_{M}$, and $0\leq t<T$. The following hold:

  1. (a)

${\mathbb{E}}\left[R_{y,\alpha}(t+1)-R_{y,\alpha}(t){|}\tau>t\right]=r^{\prime}_{y,\alpha}(t)\pm
O\left(\frac{E(t)}{n-t}\right)$.

  2. (b)

${\mathbb{E}}\left[C_{x,\alpha}(t+1)-C_{x,\alpha}(t){|}\tau>t\right]=c^{\prime}_{x,\alpha}(t)\pm
O\left(\frac{E(t)}{n-t}\right)$.

  3. (c)

${\mathbb{E}}\left[D_{x+y,\alpha}^{+}(t+1)-D_{x+y,\alpha}^{+}(t){|}\tau>t\right]={d^{+}_{x+y,\alpha}}^{\prime}(t)\pm
O\left(\frac{E(t)}{n-t}\right)$.

  4. (d)

${\mathbb{E}}\left[D_{x+y,\alpha}^{-}(t+1)-D_{x+y,\alpha}^{-}(t){|}\tau>t\right]={d_{x-y,\alpha}^{-}}^{\prime}(t)\pm
O\left(\frac{E(t)}{n-t}\right)$.

  5. (e)

${\mathbb{E}}\left[Z_{\alpha}(t+1)-Z_{\alpha}(t){|}\tau>t\right]=z_{\alpha}^{\prime}(t)\pm
O\left(\frac{E(t)}{n-t}\right)$.

###### Proof.

All five assertion follow from Claims 5.9 and 5.10. We first prove (a).

By definition:

${\mathbb{E}}\left[R_{y,\alpha}(t+1)-R_{y,\alpha}(t)\right]=-\sum_{(c,r)\in{\mathcal{R}}_{y,\alpha}(t)}{\mathbb{P}}\left[(c,r)\notin{\mathcal{R}}_{y,\alpha}(t+1)\right].$

Let $(c,r)\in{\mathcal{R}}_{y,\alpha}(t)$. By definition,
$(c,r)\notin{\mathcal{R}}_{y,\alpha}(t+1)$ if and only if column $c$, plus-
diagonal $r+c$, or minus-diagonal $r-c$ is occupied at time $t+1$. By Claims
5.9 and 5.10 if $\tau>t$ then the respective probabilities of these events are

$\frac{1}{n-t}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right),\quad\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right),$

and

$\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right).$

Additionally, more than one of these events occurs if and only if
$X_{t+1}=(c,r)$. By Claim 5.8
${\mathbb{P}}[X_{t+1}=(c,r){|}\tau>t]=O\left(\delta(\alpha)M^{2}/(n-t)^{2}\right)=O\left(1/(n-t)^{2}\right)$.
Therefore:

$\displaystyle{\mathbb{P}}\left[(c,r)\notin{\mathcal{R}}_{y,\alpha}(t+1){|}\tau>t\right]=\frac{1}{n-t}+\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}+\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right).$

Hence:

$\displaystyle{\mathbb{E}}$
$\displaystyle\left[R_{y,\alpha}(t+1)-R_{y,\alpha}(t){|}\tau>t\right]$
$\displaystyle=-R_{y,\alpha}(t)\left(\frac{1}{n-t}+\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}+\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\right)\pm
O\left(\frac{R_{y,\alpha}(t)ME(t)}{(n-t)^{2}}\right).$

We note that if $\tau>t$ then $R_{y,\alpha}(t)\leq 2(n-t)/M$. Thus:

$\displaystyle{\mathbb{E}}$
$\displaystyle\left[R_{y,\alpha}(t+1)-R_{y,\alpha}(t){|}\tau>t\right]$
$\displaystyle=-R_{y,\alpha}(t)\left(\frac{1}{n-t}+\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}+\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\right)\pm
O\left(\frac{E(t)}{n-t}\right).$

Conditioning on $\tau>t$ implies $R_{y,\alpha}(t)=r_{y,\alpha}(t)\pm E(t)$.
Therefore:

$\displaystyle R_{y,\alpha}(t)$
$\displaystyle\left(\frac{1}{n-t}+\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}+\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\right)$
$\displaystyle=\left(r_{y,\alpha}(t)\pm
E(t)\right)\left(\frac{1}{n-t}+\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}+\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\right).$

Because $\delta$ has sub-uniform diagonal marginals,
$M\delta^{+}(\alpha),M\delta^{-}(\alpha)\leq 1$. Thus:

$\displaystyle R_{y,\alpha}(t)$
$\displaystyle\left(\frac{1}{n-t}+\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}+\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\right)$
$\displaystyle=r_{y,\alpha}(t)\left(\frac{1}{n-t}+\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}+\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\right)\pm\frac{3E(t)}{n-t}.$

Finally, we observe that

$r^{\prime}_{y,\alpha}(t)=-r_{y,\alpha}(t)\left(\frac{1}{n-t}+\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}+\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\right).$

Therefore:

$\displaystyle{\mathbb{E}}\left[R_{y,\alpha}(t+1)-R_{y,\alpha}(t){|}\tau>t\right]=r^{\prime}_{y,\alpha}(t)\pm
O\left(\frac{E(t)}{n-t}\right),$

proving (a). The proof of (b) follows from the symmetry between rows and
columns.

We prove (c) with a similar argument. By definition:

${\mathbb{E}}\left[D^{+}_{x+y,\alpha}(t+1)-D^{-}_{x-y,\alpha}(t){|}Q(t)\right]=-\sum_{(c,r)\in{\mathcal{D}}^{+}_{x+y,\alpha}(t)}{\mathbb{P}}\left[(c,r)\notin{\mathcal{D}}^{+}_{x+y,\alpha}(t+1)\right].$

For every $(c,r)\in{\mathcal{D}}^{+}_{x+y,\alpha}(t)$, the event
$(c,r)\notin{\mathcal{D}}^{+}_{x+y,\alpha}(t+1)$ occurs if and only if
$X_{t+1}$ is in column $c$, row $r$, or minus-diagonal $r-c$. By Claims 5.9
and 5.10 the probability of this occurrence is

$\frac{2}{n-t}+\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right).$

Additionally, if $\tau>t$ then $D^{+}_{x+y,\alpha}(t)=d^{+}_{x+y,\alpha}(t)\pm
E(t)$. Therefore:

$\displaystyle{\mathbb{E}}$
$\displaystyle\left[D^{+}_{x+y,\alpha}(t+1)-D^{-}_{x-y,\alpha}(t){|}\tau>t\right]$
$\displaystyle=-\left(d^{+}_{x+y,\alpha}(t)\pm
E(t)\right)\left(\frac{2}{n-t}+\frac{M\delta^{-}(\alpha)}{n\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right)\right)$
$\displaystyle={d^{+}_{x+y,\alpha}}^{\prime}(t)\pm
O\left(\frac{E(t)}{n-t}\right),$

proving (c). A proof of (d) is obtained by interchanging the roles of plus-
and minus-diagonals.

Finally, we prove (e). By definition:

${\mathbb{E}}\left[Z_{\alpha}(t+1)-Z_{\alpha}(t){|}Q(t)\right]=-\sum_{c\in{\mathcal{Z}}_{\alpha}(t)}{\mathbb{P}}\left[c\notin{\mathcal{Z}}_{\alpha}(t+1)\right].$

For every $c\in{\mathcal{Z}}_{\alpha}(t)$, the event
$c\notin{\mathcal{Z}}_{\alpha}(t+1)$ occurs if and only if $X_{t+1}$ is in
plus-diagonal $c$. By Claim 5.10 if $\tau>t$ then the probability of this
event is

$\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right).$

Also, if $\tau>t$ then $Z_{\alpha}(t)=z_{\alpha}(t)\pm E(t)$. Therefore:

$\displaystyle{\mathbb{E}}$
$\displaystyle\left[Z_{\alpha}(t+1)-Z_{\alpha}(t){|}\tau>t\right]=-\left(z_{\alpha}(t)\pm
E(t)\right)\left(\frac{M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}\pm
O\left(\frac{ME(t)}{(n-t)^{2}}\right)\right)$
$\displaystyle=-\frac{z_{\alpha}(t)M\delta^{+}(\alpha)}{n\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)}\pm
O\left(\frac{E(t)}{n-t}\right)=z_{\alpha}^{\prime}(t)\pm
O\left(\frac{E(t)}{n-t}\right),$

as desired. ∎

Next, we estimate the one-step changes of the trajectory functions.

######  Claim 5.15.

The following hold for every $(x,y)\in[n]^{2}$, $\alpha\in I_{M}$, and $0\leq
t<T$:

  1. (a)

$r_{y,\alpha}(t+1)-r_{y,\alpha}(t)=r^{\prime}_{y,\alpha}(t)\pm\frac{E(t)}{n-t}$.

  2. (b)

$c_{x,\alpha}(t+1)-c_{x,\alpha}(t)=c^{\prime}_{x,\alpha}(t)\pm\frac{E(t)}{n-t}$.

  3. (c)

$d_{x+y,\alpha}^{+}(t+1)-d_{x+y,\alpha}^{+}(t)={d^{+}_{x+y,\alpha}}^{\prime}(t)\pm\frac{E(t)}{n-t}$.

  4. (d)

$d_{x-y,\alpha}(t+1)-d_{x-y,\alpha}^{-}(t)={d_{x-y,\alpha}^{-}}^{\prime}(t)\pm\frac{E(t)}{n-t}$.

  5. (e)

$z_{\alpha}(t+1)-z_{\alpha}(t)=z_{\alpha}^{\prime}(t)\pm\frac{E(t)}{n-t}$.

  6. (f)

$E(t+1)-E(t)=\frac{KE(t)}{n-t}\pm\frac{E(t)}{n-t}$.

###### Proof.

Each of assertions follows from Taylor’s theorem. For every $x\in[0,T]$:

$E^{\prime}(x)=\frac{KE(x)}{n(1-x/n)},\quad
E^{\prime\prime}(x)=\frac{K(K+1)E(x)}{n^{2}(1-x/n)^{2}}\leq\frac{2E(x)}{n(1-x/n)}.$

By Taylor’s theorem for every $0\leq t\leq T-1$ there exists some
$\zeta\in(t,t+1)$ such that

$E(t+1)-E(t)=E^{\prime}(t)+\frac{1}{2}E^{\prime\prime}(\zeta)=\frac{KE(t)}{n(1-t/n)}\pm\frac{E(t)}{n-t},$

as desired.

For the remaining assertions it suffices to show that if $f$ is one of the
functions $r_{y,\alpha}$, $c_{x,\alpha}$, $d^{+}_{x+y,\alpha}$,
$d^{-}_{x-y,\alpha}$, or $z_{\alpha}$ then for every $0\leq t\leq T-1$ and
every $\zeta\in(t,t+1)$ it holds that

(9) $|f^{\prime\prime}(\zeta)|\leq\frac{2E(t)}{n(1-t/n)}.$

This follows from direct computation. We will demonstrate this for
$r_{y,\alpha}$ and $z_{\alpha}$. The other calculations are similar.

For every $\zeta\in[0,T]$ it holds that

$\displaystyle
r_{y,\alpha}^{\prime\prime}(\zeta)=\frac{2ML_{y,\alpha}^{r}\delta^{-}(\alpha)}{n^{2}}\left(1-M\delta^{+}(\alpha)\frac{\zeta}{n}\right)$
$\displaystyle+\frac{2ML_{y,\alpha}^{r}\delta^{-}(\alpha)}{n^{2}}\left(1-M\delta^{+}(\alpha)\frac{\zeta}{n}\right)$
$\displaystyle+\frac{2M^{2}L_{y,\alpha}^{r}\delta^{+}(\alpha)\delta^{-}(\alpha)}{n^{2}}\left(1-\frac{\zeta}{n}\right).$

Since $L_{y,\alpha}^{r}\leq 2n/M$ and
$\delta^{+}(\alpha),\delta^{-}(\alpha)\leq 1/M$, for every $0\leq t<T$:

$|r_{y,\alpha}^{\prime\prime}(\zeta)|\leq\frac{12}{nM}\leq\frac{E(t)}{n(1-t/n)},$

and (9) holds.

To see that Inequality (9) holds for $z_{\alpha}$ we observe that
$z_{\alpha}(t)$ is linear and therefore $z_{\alpha}^{\prime\prime}(t)=0$. ∎

We are ready to show that the random variables are supermartingales.

###### Proof of Lemma 5.13.

Let $X$ be one of the random variables and let $*\in\\{+,-\\}$. Let $\sigma=1$
if $*=+$ and $\sigma=-1$ if $*=-$. Consider

${\mathbb{E}}\left[X^{*}(t+1)-X^{*}(t){|}Q(t)\right].$

If $\tau\leq t$ then, by definition, $X^{*}(t+1)-X^{*}(t)=0$. On the other
hand, by the previous two claims:

$\displaystyle{\mathbb{E}}$
$\displaystyle\left[X^{*}(t+1)-X^{*}(t){|}\tau>t\right]$
$\displaystyle=\sigma\left({\mathbb{E}}\left[X(t+1)-X(t){|}\tau>t\right]-\left(x(t+1)-x(t)\right)\right)-\frac{1}{2}\left(E(t+1)-E(t)\right)$
$\displaystyle=\sigma\left(\left(x^{\prime}(t)\pm
O\left(\frac{E(t)}{n-t}\right)\right)-\left(x^{\prime}(t)\pm
O\left(\frac{E(t)}{n-t}\right)\right)\right)-\frac{1}{2}\left(\frac{KE(t)}{n-t}\pm\frac{E(t)}{n-t}\right)$
$\displaystyle=-\frac{KE(t)}{2(n-t)}\pm O\left(\frac{E(t)}{n-t}\right)\leq 0,$

where the last inequality holds provided the constant $K$ was chosen to be
large enough. ∎

We are ready to prove Proposition 5.7.

###### Proof of Proposition 5.7.

We observe that $\tau<\infty$ only if there exists some $0\leq t\leq T$,
$\alpha\in I_{M}$, and $(x,y)\in[n]^{2}$ such that for $X$ one of
$R_{y,\alpha},C_{x,\alpha}D^{+}_{x+y,\alpha},D^{-}_{x-y,\alpha}$, or
$Z_{\alpha}$ either $X^{+}(t)>E(t)/2$ or $X^{-}(t)>E(t)/2$.

Let $X$ be one of the sequences of random variables above. By Lemma 5.13, both
$X^{+}$ and $X^{-}$ are supermartingales. Furthermore, by Lemma 5.12, $X^{+}$
and $X^{-}$ change by at most $O(1)$ in each time step. Therefore, by Theorem
5.11, for every $0\leq t\leq T$:

${\mathbb{P}}\left[X^{+}(t)>\frac{1}{2}E(t)\right],{\mathbb{P}}\left[X^{-}(t)>\frac{1}{2}E(t)\right]\leq\exp\left(-\Omega\left(\frac{E(t)^{2}}{T}\right)\right)=\exp\left(-\Omega\left(n^{0.75}\right)\right).$

By applying a union bound to the polynomially many random variables and times
$0\leq t\leq T$, we conclude that

${\mathbb{P}}\left[\tau<\infty\right]=\exp\left(-\Omega\left(n^{0.75}\right)\right),$

as desired. ∎

We now show that w.h.p. $Q(T)$ approximates $\delta$. In the next claim,
$N\geq\varepsilon^{-2}$ is the constant used in defining $\delta$.

######  Claim 5.16.

For every $\alpha\in I_{N}$ it holds that

${\mathbb{P}}\left[\left||\alpha_{n}\cap
Q(T)|-\delta(\alpha)n\right|>\varepsilon^{5}n\right]\leq\exp\left(-\Omega\left(n^{0.75}\right)\right).$

###### Proof.

Observe that since $N$ divides $M$, the partition $I_{M}$ is a refinement of
$I_{N}$. For $\alpha\in I_{N}$, let $W_{\alpha}$ be the number of times $1\leq
t\leq T$ such that $Y_{t}\subseteq\alpha$. Then $W_{\alpha}$ is distributed
binomially with parameters $T,\delta(\alpha)$. Therefore, by Chernoff’s
inequality:

${\mathbb{P}}\left[|W_{\alpha}-{\mathbb{E}}W_{\alpha}>\varepsilon^{5}n/2|\right]=\exp\left(-\Omega(n)\right).$

Since $|{\mathbb{E}}W_{\alpha}-n\delta(\alpha)|=o(n)$:

(10)
${\mathbb{P}}\left[|W_{\alpha}-\delta(\alpha)n>\varepsilon^{5}n|\right]=\exp\left(-\Omega(n)\right).$

If $\tau=\infty$ then Algorithm 5.2 did not abort in which case
$|\alpha_{n}\cap Q(T)|=W_{\alpha}$. Therefore, by a union bound:

$\displaystyle{\mathbb{P}}\left[\left||\alpha_{n}\cap
Q(T)|-\delta(\alpha)n\right|>\varepsilon^{5}n\right]\leq{\mathbb{P}}\left[\tau\leq
T\right]+{\mathbb{P}}\left[\left|W_{\alpha}-\delta(\alpha)n\right|>\varepsilon^{5}n\right]$
$\displaystyle\stackrel{{\scriptstyle\text{\eqref{eq:W_alpha Chernoff},
Proposition \ref{prop:tau inf
whp}}}}{{\leq}}\exp\left(-\Omega\left(n^{0.75}\right)\right),$

as claimed. ∎

We conclude the section by calculating the entropy of Algorithm 5.2.

######  Claim 5.17.

Let $0\leq t<T$. Then

$\displaystyle H(X_{t+1}{|}X_{1},X_{2},\ldots,X_{t})=$ $\displaystyle
2\log(n-t)-D^{M}(\delta)+\sum_{\alpha\in
J_{M}}\delta^{+}(\alpha)\log(1-M\delta^{+}(\alpha)t/n)$
$\displaystyle+\sum_{\alpha\in
J_{M}}\delta^{-}(\alpha)\log(1-M\delta^{-}(\alpha)t/n)\pm
O\left(\frac{ME(t)}{n(1-t/n)^{2}}\right).$

###### Proof.

Let $0\leq t<T$. By the law of total probability:

$\displaystyle
H(X_{t+1}{|}X_{1},\ldots,X_{t})=H(X_{t+1}{|}X_{1},\ldots,X_{t},\tau>t){\mathbb{P}}[\tau>t]+H(X_{t+1}{|}X_{1},\ldots,X_{t},\tau\leq
t){\mathbb{P}}[\tau\leq t].$

By Proposition 5.7 ${\mathbb{P}}[\tau\leq
t]=\exp\left(-\Omega\left(n^{0.75}\right)\right)$. Additionally, $X_{t+1}$ is
distributed among at most $n^{2}$ elements. Therefore:

$H(X_{t+1}{|}X_{1},\ldots,X_{t},\tau\leq t){\mathbb{P}}[\tau\leq
t]\leq\log(n^{2})\exp\left(-\Omega\left(n^{0.75}\right)\right)=\exp\left(-\Omega\left(n^{0.75}\right)\right).$

Thus:

$H(X_{t+1}{|}X_{1},\ldots,X_{t})=H(X_{t+1}{|}X_{1},\ldots,X_{t},\tau>t)\pm\exp\left(-\Omega\left(n^{0.75}\right)\right).$

By the chain rule:

$\displaystyle
H(X_{t+1}{|}X_{1},\ldots,X_{t},\tau>t)=H(Y_{t+1}{|}X_{1},\ldots,X_{t},\tau>t)+H(X_{t+1}{|}X_{1},\ldots,X_{t},Y_{t+1},\tau>t).$

Recall that $Y_{t+1}$ is independent of $X_{1},\ldots,X_{t},\tau$. By its
definition:

$H(Y_{t+1}{|}X_{1},\ldots,X_{t},\tau>t)=-\sum_{\alpha\in
I_{M}}\delta(\alpha)\log(\delta(\alpha)).$

By definition of $X_{t+1}$:

$H(X_{t+1}{|}X_{1},\ldots,X_{t},Y_{t+1},\tau>t)=\sum_{\alpha\in
I_{M}}\delta(\alpha)\log(A_{\alpha}(t)).$

By Claim 5.8 if $\tau>t$ then for every $\alpha\in S_{M}$:

$A_{\alpha}(t)=|\alpha_{n}|\left(1-\frac{t}{n}\right)^{2}\left(1-M\delta^{+}(\alpha)\frac{t}{n}\right)\left(1-M\delta^{-}(\alpha)\frac{t}{n}\right)\left(1\pm
O\left(\frac{ME(t)}{n(1-t/n)^{2}}\right)\right).$

Thus:

$\displaystyle H(X_{t+1}{|}X_{1},\ldots,X_{t},Y_{t+1},\tau>t)=$
$\displaystyle\sum_{\alpha\in
I_{M}}\delta(\alpha)\left(\log(|\alpha_{n}|)+2\log(1-t/n)+\log(1-M\delta^{+}(\alpha)t/n)+\log(1-M\delta^{-}(\alpha)t/n)\right)$
$\displaystyle\qquad\pm O\left(\sum_{\alpha\in
T_{n}}\delta(\alpha)\log(n^{2})+\frac{ME(t)}{n(1-t/n)^{2}}\right)$
$\displaystyle=2\log(1-t/n)+\sum_{\alpha\in
I_{M}}\delta(\alpha)\log(|\alpha_{n}|)+\sum_{\alpha\in
J_{M}}\delta^{+}(\alpha)\log(1-M\delta^{+}(\alpha)t/n)$
$\displaystyle\qquad+\sum_{\alpha\in
J_{M}}\delta^{-}(\alpha)\log(1-M\delta^{-}(\alpha)t/n)\pm
O\left(\frac{ME(t)}{n(1-t/n)^{2}}\right).$

Recall that $|\alpha|$ is the area of $\alpha$. Observe that for every
$\alpha\in I_{M}$, $|\alpha_{n}|=n^{2}|\alpha|\pm
O(n/M)=n^{2}|\alpha|\left(1\pm O(M/n)\right)$. Thus

$\sum_{\alpha\in
I_{M}}\delta(\alpha)\log(|\alpha_{n}|)=2\log(n)+\sum_{\alpha\in
I_{M}}\delta(\alpha)\log(|\alpha|)\pm O\left(\frac{M}{n}\right).$

Finally, we recall that by definition

$-\sum_{\alpha\in I_{M}}\delta(\alpha)\log(\delta(\alpha))+\sum_{\alpha\in
I_{M}}\delta(\alpha)\log(|\alpha|)=-D^{M}(\delta).$

Therefore:

$\displaystyle H(X_{t+1}{|}X_{1},X_{2},\ldots,X_{t})=$ $\displaystyle
2\log(n-t)-D^{M}(\delta)+\sum_{\alpha\in
J_{M}}\delta^{+}(\alpha)\log(1-M\delta^{+}(\alpha)t/n)$
$\displaystyle+\sum_{\alpha\in
J_{M}}\delta^{-}(\alpha)\log(1-M\delta^{-}(\alpha)t/n)\pm
O\left(\frac{ME(t)}{n(1-t/n)^{2}}\right),$

as desired. ∎