# Relation between finite topological spaces and finitely presentable groups

Samuel Roldán, Jose Luis Mora, Edward Becerra  Mathematics Department
Universidad Nacional de Colombia  Carrera 30 calle 45, Ciudad Universitaria,
Bogotá, Colombia

###### Abstract

In this paper it is shown how to construct a finite topological space $X$ for
a given finitely presentable group $G$ such that $\pi_{1}(X)\cong G$. Our
construction is not optimal in the sense that the cardinality of the space $X$
might not be the smallest possible. Our main result applies to a large class
of interesting groups, including all finite groups.

###### keywords:

Finite topological space, Finitely presented group, Properly discontinuous
actions, Simplicial complex, Fundamental group

††journal: .myfootnotemyfootnotefootnotetext:  This research did not receive
any specific grant from funding agencies in the public, commercial, or not-
for-profit sectors.

##  1 Introduction

Finite topological spaces are naturally related via a combinatorial focus,
based on the famous bijective correspondence between topologies defined on a
finite set $X$ and preorders on $X$, as shown by Alexandroff [1]. Under this
bijection, partial orders on $X$ correspond to $T_{0}$ topologies on $X$.
Moreover, there is a weak homotopy equivalence between any finite
$T_{0}$–space and the geometric realization of its associated partial ordered
set [2]. These results allow the study of properties of the order complex of a
finite partially ordered set by means of its associated finite $T_{0}$–space.
The latter has proved to be very useful [3]. Indeed, the theory of finite
topological spaces gives interesting tools to study partial ordered sets and
polyhedra.

From a naive viewpoint, the topology defined on a finite space could seem
uninteresting. Nevertheless, for a finite set $X$ and a fixed topology defined
on it, we can define continuous functions from an interval $I$ to $X$ in a
very natural way. Namely, we can consider paths, loops and homotopies on $X$.
This paper begins with an effort to understand how the classical tools from
algebraic topology translate to finite topological spaces. Later on, more
interesting questions are considered relating the topological structure of $X$
with the classical topological invariants introduced in algebraic topology.
Namely, for a finite topological space $X$ we consider its fundamental group
$\pi_{1}(X)$. The group $\pi_{1}(X)$ does not have to be a finite group. We
can find some interesting examples where a given topology on $X$ leads to
$\pi_{1}(X)\cong\mathbb{Z}$. This leads us to the main topic in question:

######  Question 1.1.

Let $G$ a finitely presentable group. Is it possible to find some finite
topological space $X$ such that $\pi_{1}(X)\cong G$?

Finitely presentable groups appear in many topics in topology and algebra. For
instance, the fundamental group of any compact surface (i.e. a closed surface
without frontier) is a finitely presentable group. In fact, any finitely
presentable group is the fundamental group of a compact 4-dimensional space-
time manifold. On the other side, the theory of finitely presentable groups is
largely related to coding theory. We might look for such connections between
our result and those applied fields in future papers.

This paper is organized as follows: In Section 2 we describe some tools from
algebraic topology to be used throughout Sections 3 and 4, in order to justify
our developments. In Section 3 we introduce an interesting construction of a
finite topological space associated to a given finitely presentable group $G$.
Then the main result is presented, Theorem 3.6, which can be applied to a
large class of groups, including finite groups. Also in Section 3, another
construction of a finite topological space associated to the finite abelian
group $\mathbb{Z}_{n}$ for $n\in\mathbb{N}$ is shown. This construction has
the advantage of enabling the presentation of explicit examples, because the
commutativity of the group $\mathbb{Z}_{n}$ provides a simpler construction
than the one presented in Section 2.

The authors want to express their gratitude to Alexis Sanchez and Roberto
Vargas for contributing to this paper with stimulating discussions about Hasse
diagrams. The third author wants to thank the first and second authors for
their efforts in order to clarify the initial idea behind this paper.

##  2 Preliminaries

In this section, in order to obtain an easier explanation of the results
presented in later sections, some tools from algebraic topology are shown.
These tools are standard in a classical course on this topic. Our main
references are the book in General Topology by J. Munkres [4] Chapters 9-12,
and Chapter 1 in [5].

Let $X$ be a path-connected topological space. We consider $\pi_{1}(X,x_{0})$
the set of _loops_ in $X$ based on a fixed point $x_{0}\in X$, up to homotopy.
This set is actually a group, called the _fundamental group_ of the space $X$,
with the composing operation defined for $[\alpha]$ and $[\beta]$ two classes
in $\pi_{1}(X,x_{0})$, via $[\alpha][\beta]:=[\alpha*\beta]$, where $*$
denotes concatenation ([4], Chapter 9, §51) of loops based on $x_{0}$. It is
an easy exercise to prove that for a path-connected space $X$ the group
$\pi_{1}(X,x_{0})$ does not depend on the point $x_{0}$, so we can write
$\pi_{1}(X)$. A topological space is called simply connected if its
fundamental group is the trivial group.

###  2.1 Group actions

Let $X$ be a topological space, and let $G$ be group. An _action_ from the
group $G$ onto the space $X$ is a map:

$\tau:G\times X\rightarrow X\text{ for each }g\in G$ (1)

such that for each $g\in G$, the map $\tau|_{\\{g\\}\times
X}:=\tau_{g}:X\rightarrow X$ is a homeomorphism and satisfies:

  * i.

$\tau_{e}=id_{X}$ for $e$ the identity element in $G$.

  * ii.

$\tau_{g}(\tau_{h}(x))=\tau_{gh}(x)$ for all $g,h\in G$ and any $x\in X$.

For short, we set $\tau_{g}(x)=gx$. The _orbit space_ $X/G$ is defined to be
the quotient space obtained from $X$ by means of the equivalence relation
$x\sim gx$ for all $x\in X$ and all $g\in G$. The equivalence class of $x$ is
called the _orbit_ of $x$.

######  Example 2.1.

Let $X$ be a set. Suppose that we have an action from a group $G$ on $X$. We
can define an action from the group $G$ on the set $\wp(X)$ (parts of $X$) via
the formula

$g(A)=\\{ga\in X\mid a\in A\\}\mbox{ for }g\in G,A\subset X.$ (2)

It is a straightforward verification that the action defined in Equation 2
satisfies the conditions to be a well defined action on $\wp(X)$.

######  Definition 2.2.

If $G$ is a group of homeomorphisms of $X$, the action of $G$ on $X$ is said
to be properly discontinuous if for every $x\in X$ there is a neighborhood $U$
of $x$ such that $g(U)$ is disjoint from $U$ whenever $g\not=e$. ($e$ is the
identity element of $G$.)

A topological space $X$ is defined to be locally path-connected if for each
point $x\in X$ there exists a neighbourhood $U_{x}$ of $x$ such that $U_{x}$
is path-connected.

######  Theorem 2.3.

[[5], Ch.1 Proposition 1.40 Part (c)] Let X be a simply connected and locally
path-connected topological space endowed with an action from a group $G$. If
the action is provided to be properly discontinuous, the group $G$ is
isomorphic to the group $\pi_{1}(X/G)$.

##  3 Construction for a finitely presentable group $G$

Let $G$ be a finitely presentable group with presentation $\langle S\mid
R\rangle$ where $S$ is a non empty finite set and $R$ a finite subset of
$F_{S}$, the free group generated by $S$. By definition, every $r\in R$ is a
word of $F_{S}$ with $length(r)$ letters in the alphabet $S$. Let us denote
$r[i]$ the $i-$th letter of $r$, $r[0]=e$ be the identity element of $F_{S}$
and $r[i,j]=r[i]r[i+1]\cdots r[j]$ for $0\leq i\leq j\leq length(r)$. Note
that there is a homomorphism $\varphi:F_{S}\rightarrow G$ such that
$Ker(\varphi)=\langle R\rangle$ and $G\cong F_{S}/\langle R\rangle$;
therefore, two elements $w,w^{\prime}\in F_{S}$ will represent the same
element in $G$ if $\varphi(w)=\varphi(w^{\prime})$. This will be denoted
$w=_{{}_{G}}w^{\prime}$.

######  Theorem 3.1.

Let G be a finitely presentable group. There exists a reduced presentation
$\langle S\mid R\rangle$ in the sense that for every $s\in S$ and every $r\in
R$, $s\neq_{G}e$ and $r[i,j]=_{{}_{G}}e$ only for $i=0,1$ and $j=length(r)$.

###### Proof.

The case when there is a $s\in S$ such that $s=_{{}_{G}}e$ is trivial, and if
there exists $r\in R$ and $n<m$ such that $r[n,m]=_{{}_{G}}e$, then we replace
$R$ by

$\left(R-\\{r\\}\right)\cup\\{r[n,m],r[1]\cdots r[n-1]r[m+1]\cdots
r[length(r)]\\}$

∎

For each presentation $\langle S\mid R\rangle$ we can construct its Cayley
complex $X_{G}$. To do this we will perform an inductive construction. Let the
vertices or 0-cells be the elements of G; these will form the 0-skeleton of
the complex $X_{G,0}$. Inductively, we will attach (n+1)-cells to the
n-skeleton $X_{G,n}$ with attachment maps $\gamma_{n}:S^{n}\rightarrow
X_{G,n}$. For each element $(g,s)\in G\times S$ we put a 1-cell connecting the
vertices $g$ and $gs$. Now, for every element $(g,r)\in G\times R$ we attach a
2-cell to the path given by the edges denoted by

$(gr[0,0],r[1])(gr[0,1],r[2])\cdots(gr[0,length(r)-1],r[length(r)])$

or equivalently, the path that passes through the vertices

$gr[0,0],gr[0,1],\ldots,gr[0,length(r)].$

######  Remark 3.2.

We will denote by $\Sigma_{G}$ the set of cells of the Cayley complex $X_{G}$.
We can identify the 0-cells with $G$, the 1-cells with $G\times S$ and the
2-cells with $G\times R$; therefore, we will denote the elements of
$\Sigma_{G}$ with elements of $G\cup(G\times S)\cup(G\times R)$.

We want the closure of every cell to be homeomorphic to a closed ball in some
$\mathbb{R}^{n}$, or equivalently, for the attaching maps to be embeddings. By
construction, it is sufficient that the attaching maps are injective. This
means that each 1-cell has non overlapping endpoints and the closed path in
the boundary of each 2-cell does not self-intersect. Without loss of
generality, we can assume that we are working with a reduced presentation.
With such presentation, the edge $(g,s)$ has endpoints $g,gs\in G$ and
$g=_{{}_{G}}gs$ would imply the contradiction $s=_{{}_{G}}e$. If the closed
path in the boundary of a 2-cell $(g,r)$ self-intersects, it has to self
intersect at a vertex; this would mean that $gr[0,n]=_{{}_{G}}gr[0,m]$ and
therefore $r[n+1,m]=_{{}_{G}}e$ for $n\neq 0,1$ or $m\neq length(r)$ which
would be a contradiction.

The previous condition on the Cayley complex allows us to construct a
simplicial complex performing a generalized barycentric subdivision ([6], pp.
80-82). Let $\tilde{\Sigma}_{G}\subseteq\wp(\Sigma_{G})$ be the simplicial
complex with n-simplexes corresponding to the non-empty chains with the order
$\preccurlyeq$ given by the condition “is in the boundary of” in $\Sigma_{G}$.
This way our simpleces have n-cells of $X_{G}$ such that for every pair of
them, one is in the boundary of the other; as an example, for every $r\in R$
there is a 2-simplex $\\{(e,r),(e,r[1]),e\\}\in\tilde{\Sigma}_{G}$. We want
$\tilde{\Sigma}_{G}$ to be a topological space. With this in mind, we endow
$\tilde{\Sigma}_{G}$ with the Alexandrov topology induced by inclusion; that
is, the topology
$\tau=\\{S\subseteq\tilde{\Sigma}_{G}:\forall\sigma,\sigma^{\prime}\in S\,\
(\sigma\in S\ \land\ \sigma^{\prime}\subseteq\sigma)\ \rightarrow\
\sigma^{\prime}\in S\\}$ with base
$\\{star(\sigma):\sigma\in\tilde{\Sigma}_{G}\\}$ and
$star(\sigma)=\\{\lambda\in\tilde{\Sigma}_{G}:\sigma\subseteq\lambda\\}$, the
usual definition for simplicial complexes.

######  Lemma 3.3.

$\tilde{\Sigma}_{G}$ is path connected, simply connected and locally path
connected.

###### Proof.

We know that there is a weak homotopy equivalence between $\tilde{\Sigma}_{G}$
and its geometric realization $|\tilde{\Sigma}_{G}|$ ([2], Theorem 2). Also,
we know that the latter is homeomorphic to $X_{G}$ as $\tilde{\Sigma}_{G}$ is
the generalized barycentric subdivision of $X_{G}$. Therefore, there is a weak
homotopy equivalence between $X_{G}$ and $\tilde{\Sigma}_{G}$. In particular,

$0=\pi_{0}(X_{G},x_{0})=\pi_{0}(\tilde{\Sigma}_{G},\sigma_{0}),$
$0=\pi_{1}(X_{G},x_{0})=\pi_{1}(\tilde{\Sigma}_{G},\sigma_{0}),$

which means that $\tilde{\Sigma}_{G}$ is path connected and simply connected.
We also have that a space with an Alexandrov topology is locally path
connected ([2], Corollary of lemma 6). ∎

Now, we want to define an action of $G$ on $\tilde{\Sigma}_{G}$. For this, we
will define an action of $G$ over $\Sigma_{G}$ and for each
$\sigma\in\tilde{\Sigma}_{G}\subset\wp(\Sigma_{G})$, we define the action of
$G$ with $g\sigma=\\{gx:x\in\sigma\\}$. Note that this is well defined as an
action on $\tilde{\Sigma}_{G}$ if and only if the action of $G$ over
$\Sigma_{G}$ sends chains to chains, or equivalently, if the action of $G$
over $\Sigma_{G}$ preserves the order induced by inclusion. Every action of
$G$ on a set $A\subseteq\wp(\Sigma_{G})$ that can be defined this way will be
called an induced action.

######  Lemma 3.4.

Let $G$ act on $\tilde{\Sigma}_{G}\subseteq\wp(\Sigma_{G})$ as an induced
action, $\sigma\in\tilde{\Sigma}_{G}$ and $g\in G$ different from the identity
of $G$. If the action of $g$ on $\Sigma_{G}$ does not have fixed points and
the action of $g$ on $\Sigma_{G}$ preserves the dimension of the n-cells, then
$star(\sigma)\cap g(star(\sigma))=\phi$.

###### Proof.

As $\sigma$ is non-empty, let $\lambda\in\sigma$ so that
$star(\sigma)\subseteq star(\\{\lambda\\})$ and therefore
$star(g\sigma)\subseteq star(\\{g\lambda\\})$. If we assume that there exists
$\alpha\in star(\sigma)\cap star(g\sigma)$, then $\alpha\in
star(\\{\lambda\\})\cap star(\\{g\lambda\\})$. Thus
$\lambda,g\lambda\in\alpha$ but we have that $\lambda\neq g\lambda$ as the
action of $g$ on $\Sigma_{G}$ does not have fixed points. Now, as $\alpha$ is
a chain, $\lambda$ is in the boundary of $g\lambda$ or $g\lambda$ is in the
boundary of $\lambda$ which would give us a contradiction as $\lambda$ and
$g\lambda$ are n-cells of the same dimension. ∎

We define an action of an element $g\in G$ on $\Sigma_{G}$ for each n-cell
with n=0,1,2 using Remark 3.2.This is:

  * 1.

$g\in G$ acting on the 0-cell $h\in G$ is the 0-cell $gh\in G$

  * 2.

$g\in G$ acting on the 1-cell $(h,s)\in G\times S$ is the 1-cell
$g(h,s)=(gh,s)\in G\times S$

  * 3.

$g\in G$ acting on the 2-cell $(h,r)\in G\times R$ is the 2-cell
$g(h,r)=(gh,r)\in G\times R$

With the induced action of $G$ over $\tilde{\Sigma}_{G}$, we can form a space
$\tilde{\Sigma}_{G}/G$, the quotient space of $\tilde{\Sigma}_{G}$ in which
each point $\sigma$ is identified with all its images $g\sigma$ as $g$ ranges
over $G$. The points of $\tilde{\Sigma}_{G}/G$ are thus the orbits
$G\sigma={g\sigma:g\in G}$ in $\tilde{\Sigma}_{G}$.

######  Theorem 3.5.

G is isomorphic to $\pi_{1}(\tilde{\Sigma}_{G}/G)$.

###### Proof.

It is clear that the action of $G$ on $\Sigma_{G}$ we defined satisfies the
hypothesis of Theorem 3.4 for every $g\in G$ different from the group identity
element. Therefore, the fact that the action is properly discontinuous follows
directly from Lemma 3.4 and that
$\\{star(\sigma):\sigma\in\tilde{\Sigma}_{G}\\}$ is a base for
$\tilde{\Sigma}_{G}$. Now, using Lemma 3.3, we have all the hypothesis of
Theorem 2.3 (also including the path-connectedness assumed in all of Section
2) and therefore, using Theorem 2.3, we conclude that $G$ is isomorphic to
$\pi_{1}(\tilde{\Sigma}_{G}/G)$. ∎

Now, we want to prove that $\tilde{\Sigma}_{G}/G$ is finite. First we will
characterize every orbit of $\tilde{\Sigma}_{G}/G$. Let
$G\sigma\in\tilde{\Sigma}_{G}/G$. As $\sigma$ is a non-empty finite chain,
there exists $\alpha=\max\sigma$. For all $g\in G$, $G(g\sigma)=G\sigma$;
therefore, without loss of generality, we can assume that
$\alpha\in\\{e\\}\cup(\\{e\\}\times S)\cup(\\{e\\}\times R)$. If we fix
$\alpha$, we have that there is only a finite number of $\beta\in\Sigma_{G}$
such that $\beta\preccurlyeq\alpha$ and therefore there is a finite number of
$\sigma\in\tilde{\Sigma}_{G}/G$ with $\alpha=\max\sigma$. Furthermore, as $G$
is finitely presentable, there is only a finite amount of
$\alpha\in\\{e\\}\cup(\\{e\\}\times S)\cup(\\{e\\}\times R)$ and we can
conclude that $\tilde{\Sigma}_{G}/G$ is finite.

######  Theorem 3.6.

Let G have a finite presentation $\langle S\mid R\rangle$. Then
$G\cong\pi_{1}(\tilde{\Sigma}_{G}/G)$ with

$|\tilde{\Sigma}_{G}/G|=1+3|S|+\Sigma_{r\in
R}\left(4\text{length}(r)+1\right)$

###### Proof.

We will prove the last statement of the theorem. Let
$G\sigma\in\tilde{\Sigma}_{G}/G$ and $\alpha=\max\sigma$. As we saw in the
last paragraph, we can assume $\alpha\in\\{e\\}\cup(\\{e\\}\times
S)\cup(\\{e\\}\times R)$. Therefore, there are three possibilities:

  1. 1.

$\alpha=e$: As $e$ is minimal in $\Sigma_{G}$, $\sigma=\\{e\\}$.

  2. 2.

$\alpha=(e,s)$ for $s\in S$:
$\sigma\in\\{\\{\alpha\\},\\{\alpha,e\\},\\{\alpha,s\\}\\}$.

  3. 3.

$\alpha=(e,r)$ for $r\in R$: As we can assume $S\subset G$, we can interpret
$r[0,i]\in F_{G}$ as an element of $G$ , and this case can be split in five:

    1. (a)

$\sigma=\\{\alpha,r[0,i]\\}$ for $i=0,\cdots,length(r)-1$.

    2. (b)

$\sigma=\\{\alpha,(r[0,i],r[i+1])\\}$ for $i=0,\cdots,length(r)-1$.

    3. (c)

$\sigma=\\{\alpha,(r[0,i],r[i+1]),r[0,i]\\}$ for $i=0,\cdots,length(r)-1$.

    4. (d)

$\sigma=\\{\alpha,(r[0,i],r[i+1]),r[0,i+1]\\}$ for $i=0,\cdots,length(r)-1$

    5. (e)

$\sigma=\\{\alpha\\}$.

and the formula $|\tilde{\Sigma}_{G}/G|=1+3|S|+\Sigma_{r\in
R}\left(4\text{length}(r)+1\right)$ should be clear.

∎

##  4 The case of $G$ a finite abelian group

Despite the generality and beauty of the presentation described in the
previous section, it is important to highlight the difficulty in finding
explicit examples using the results therein. Nevertheless, we know that finite
abelian groups are more handleable than non-abelian ones. We realize that if a
group $G$ is an abelian group, we can find an explicit finite topological
space $X$ associated to the group $G$ in the sense that $\pi_{1}(X)\cong G$.
This is great news, since explicit examples can be considered.

In general, for a finite abelian group $G$ it is possible to define explicitly
the topology on a finite set $X$ such that $\pi_{1}(X)\cong G$. For the groups
$\mathbb{Z}_{n}\cong\mathbb{Z}/n\mathbb{Z}$ there is a simpler way to do it
than for an arbitrary group. Furthermore, by the known property
$\pi_{1}(X\times Y)\cong\pi_{1}(X)\times\pi_{1}(Y)$ of the fundamental group
together with the Theorem of Classification of Finite Abelian Groups, it is
enough to present the construction for the group $\mathbb{Z}_{n}$ for
$n\in\mathbb{N}$.

###  4.1 The construction for the group $\mathbb{Z}_{n}$

Let $G=\mathbb{Z}_{n}$ with $n>1$ and $n\in\mathbb{N}$. Let us consider the
space $\tilde{X}_{G}$ consisting of $n$ disks $D_{1},\ldots,D_{n}$ with their
boundary circles identified. There is a generator $g$ of $G$ which acts on
this union by sending $D_{i}$ to $D_{i+1}$ via a $2\pi/n$ rotation with $i$
being taken mod $n$.
Let $a_{1},\ldots,a_{2n}$ be $2n$ equidistant points on the boundary of
$\tilde{X}_{G}$ and ordered in the clockwise direction. Also, let
$a^{\prime}_{1},\ldots,a^{\prime}_{n}$ be points in $\tilde{X}_{G}$ such that
$a^{\prime}_{i}$ is the center of the disk $D_{i}$ for $1\leq i\leq n$. We
denote $b_{i,1},\ldots,b_{i,2n}$ as the $2n$ open edges between
$a_{1},\ldots,a_{2n}$ and $a^{\prime}_{i}$ respectively for each $1\leq i\leq
n$. Notice that the edges $b_{i,1},\ldots,b_{i,2n}$ divide the disk $D_{i}$ in
$2n$ areas. Let us denote the open part of these $2n$ areas by
$c_{i,1},\ldots,c_{i,2n}$ maintaining the coherence between these and the
notation of the segments. The collection of all these elements will be denoted
by $\tilde{T}_{G}$. We proceed now to endow the set $\tilde{T}_{G}$ with a
topology that makes continuous the map
$F:\tilde{X}_{G}\rightarrow\tilde{T}_{G}$ which sends an element in
$\tilde{X}_{G}$ to the element in $\tilde{T}_{G}$ that represents the location
of the point. For instance, if $x\in\tilde{X}_{G}$ is located on the open edge
represented by $b_{1,1}$ then $F(x)=b_{1,1}$. Thus, we will endow
$\tilde{T}_{G}$ with the final topology with respect to the function $F$.

Now we are going to define the following equivalence relation in
$\tilde{X}_{G}$: $x\sim y$ if both elements are located in a region
represented by the same element in $\tilde{T}_{G}$. Then, we endow the set
$\tilde{T}_{G}$ with the topology that makes this space homeomorphic to the
quotient space $\tilde{X}_{G}/\sim$. This means that the map $F=H\circ
q:\tilde{X}_{G}\rightarrow\tilde{T}_{G}$ is continuous, where
$q:\tilde{X}_{G}\rightarrow\tilde{X}_{G}/\sim$ is the quotient map and
$H:\tilde{X}_{G}/\sim\ \rightarrow\tilde{T}_{G}$ is a homeomorphism. Notice
that the map

$q_{*}:\pi_{1}(\tilde{X}_{G})\rightarrow\pi_{1}(\tilde{X}_{G}/\sim)$

is surjective and hence we have that $\pi_{1}(\tilde{T}_{G})=0$. Thus, we have
that $\tilde{T}_{G}$ is simply-connected, path-connected, locally path-
connected and $G$ is a covering space action on it . Therefore, the map

$p:\tilde{T}_{G}\rightarrow\tilde{T}_{G}/G$

is the universal cover and hence $\pi_{1}(\tilde{T}_{G}/G)\cong
G=\mathbb{Z}_{n}$.

Lastly, if we take into account the Fundamental Theorem of finitely generated
abelian groups and the fact that the fundamental group of a finite product of
topological spaces is isomorphic to the finite product of the fundamental
groups of the topological spaces, then it is possible to construct a finite
topological space with fundamental group $G$ for $G$ any finitely generated
abelian group.

Now we are going to show explicitly what the open sets in the resulting
topology are. For $1<n\in\mathbb{N}$ we define the sets

$\displaystyle A^{\prime}$
$\displaystyle=\\{a^{\prime}_{1},\ldots,a^{\prime}_{2n}\\},$ $\displaystyle A$
$\displaystyle=\\{a_{1},\ldots,a_{n}\\},$ $\displaystyle B^{\prime}$
$\displaystyle=\\{b^{\prime}_{1},\ldots,b^{\prime}_{2n}\\},$ $\displaystyle
B_{i}$ $\displaystyle=\\{b_{i,1},\ldots,b_{i,2n}\\},$ $\displaystyle C_{i}$
$\displaystyle=\\{c_{i,1},\ldots,c_{i,2n}\\},$

for $1\leq i\leq n$. Let $\Sigma=A\cup A^{\prime}\cup B\cup B^{\prime}\cup C$,
where $B=\cup_{i=1}^{n}B_{i}$ and $C=\cup_{i=1}^{n}C_{i}$. Endow the set
$\Sigma$ with the following topology: for $c_{i,j}\in C$ the basic open set
will be $U_{c_{i,j}}=\\{c_{i,j}\\}$. For $b_{i,j}\in B$ the basic open set
will be $U_{b_{i,j}}=\\{b_{i,j}\\}\cup U_{c_{i,j-1}}\cup
U_{c_{i,j}}=\\{c_{i,j-1},b_{i,j},c_{i,j}\\}$ with $j$ taken mod $n$ and for
$b^{\prime}_{i}\in B^{\prime}$ it will be
$U_{b^{\prime}_{i}}=\bigcup_{j=1}^{n}U_{c_{j,i}}\cup\\{b^{\prime}_{i}\\}=\\{c_{1,i},\ldots,c_{n,i},b^{\prime}_{i}\\}$.
For $a_{i}\in A$ the basic open set will be $U_{a_{i}}=B_{i}\cup
C_{i}\cup\\{a_{i}\\}$ and for $a^{\prime}_{i}\in A^{\prime}$ it will be
$U_{a^{\prime}_{i}}=\bigcup_{j=1}^{n}U_{b_{j,i}}\cup\\{b^{\prime}_{i-1},a^{\prime}_{i},b^{\prime}_{i}\\}=\\{b^{\prime}_{i-1},a^{\prime}_{i},b^{\prime}_{i},b_{1,i},c_{1,i-1},c_{1,i},\ldots,b_{n,i},c_{n,i-1},c_{n,i}\\}$
with $j$ taken mod $n$ and $i$ taken mod $2n$. The collection of all these
open sets together with the empty set form a topological basis because every
intersection of any two elements is empty or contains at least one element of
the form $c_{i,j}$, and the latter implies that the open set $U_{c_{i,j}}$
(which belong to the collection) is contained in the intersection.

Now we define the following equivalence relation: $a^{\prime}_{i}\sim
a^{\prime}_{j}$ iff $i\equiv j\text{ mod }2$. $a_{i}\sim a_{j}$ for all $1\leq
i,j\leq n$. $b^{\prime}_{i}\sim b^{\prime}_{j}$ iff $i\equiv j\text{ mod }2$.
$b_{i,s}\sim b_{j,t}$ iff $2(j-i)\equiv t-s\text{ mod }2n$ and $c_{i,s}\sim
c_{j,t}$ iff $2(j-i)\equiv t-s\text{ mod }2n$.
Let $\Sigma/\sim$ be the quotient space and

$p:\Sigma\rightarrow\Sigma/\sim,$

the quotient map. Let $g:\Sigma\rightarrow\Sigma$ be the function defined by

$g(x)=\left\\{\begin{array}[]{lcc}a^{\prime}_{i+2}&if&x=a^{\prime}_{i}\\\ \\\
a_{i+1}&if&x=a_{i}\\\ \\\ b^{\prime}_{i+2}&if&x=b^{\prime}_{i}\\\ \\\
b_{i+1,j+2}&if&x=b_{i,j}\\\ \\\ c_{i+1,j+2}&if&x=c_{i,j}\end{array}\right.,$

with $i$ taken mod $n$, $j$ taken mod $2n$. We define the group $G=\langle
g\rangle$ with composition of functions as the binary operation. $G$ is
isomorphic to $\mathbb{Z}_{n}$ because $g^{n}(x)=x$; furthermore, the action
of the group on $\Sigma$ is properly discontinuous:

$\displaystyle g(U_{a^{\prime}_{i}})\cap U_{a^{\prime}_{i}}$
$\displaystyle=U_{a^{\prime}_{i+2}}\cap U_{a^{\prime}_{i}}=\emptyset,$
$\displaystyle g(U_{c_{i,j}})\cap U_{c_{i,j}}$
$\displaystyle=U_{c_{i+1,j+2}}\cap U_{c_{i,j}}=\emptyset,$ $\displaystyle
g(U_{b^{\prime}_{i}})\cap U_{b^{\prime}_{i}}$
$\displaystyle=U_{b^{\prime}_{i+2}}\cap U_{b^{\prime}_{i}}=\emptyset,$
$\displaystyle g(U_{b_{i,j}})\cap U_{b_{i,j}}$
$\displaystyle=U_{b_{i+1,j+2}}\cap U_{b_{i,j}}=\emptyset,$ $\displaystyle
g(U_{a_{i}})\cap U_{a_{i}}$ $\displaystyle=U_{a_{i+1}}\cap
U_{a_{i}}=\emptyset.$

Next we are going to prove that $\Sigma$ is path-connected and locally path-
connected: assume there are $U,V$ open sets with $U\not=\emptyset$ and
$V\not=\emptyset$ such that $U\cup V=\Sigma$ and $U\cap V=\emptyset$. Notice
that $(A\cup A^{\prime})\not\subset U$ because otherwise we would have
$V=\emptyset$. Similarly, $(A\cup A^{\prime})\not\subset V$. Therefore, there
exist $x,y\in A\cup A^{\prime}$ such that $x\in U$ and $y\in V$. Thus,
$U_{x}\subset U$ and $U_{y}\subset V$, but $U_{x}\cap U_{y}\not=\emptyset$
because $x,y\in A\cup A^{\prime}$. Hence, $U\cap V\not=\emptyset$ which is a
contradiction. Then, $\Sigma$ is connected and also path-connected (these two
invariants are equivalent in finite topological spaces).
To see that $\Sigma$ is locally path-connected the only thing remaining to be
proved is that each one of the basic open sets is path-connected. For
$x,y\in\Sigma$ we denote by $f_{y,x}:[0,1]\rightarrow U_{x}$ the function such
that $f_{y,x}(a)=y$ for $0\leq a<1$, $f_{y,x}(1)=x$. Notice that if
$U_{y}\subset U_{x}$, then $f_{y,x}$ is continuous; in fact $U_{y}\subset
U_{x}$ for every $x\in\Sigma$ and $y\in U_{x}$ because $\Sigma$ is finite.
Hence, for any $x\in\Sigma$ and $y\in U_{x}$ the function $f_{y,x}$ is
continuous. Thus, there exists a path connecting each element $y$ in $U_{x}$
with $x$ and therefore $U_{x}$ is path-connected.

Finally, it will be proved that $\Sigma$ is simply connected in order to apply
Theorem 2.3 to show that $\mathbb{Z}_{n}$ is the fundamental group of
$\Sigma/\sim$ and for this we need the following proposition.

######  Proposition 4.1.

Let $f:I\rightarrow T$, $g:I\rightarrow T$ be two paths such that $f(0)=g(0)$,
$f(1)=g(1)$ and for any $x\in I$, $f(x)\in U_{a^{\prime}_{i}}$ and $g(x)\in
U_{a^{\prime}_{i}}$. Then $f$ and $g$ are homotopic.

###### Proof.

From [3] Remark 1.2.8 we have that $U_{a}$ is simply connected and therefore
$f$ and $g$ must be homotopic. ∎

Let $\alpha:I\rightarrow\Sigma$ be any loop with
$\alpha(0)=\alpha(1)=a^{\prime}_{1}$. For a fixed $1\leq i\leq n$, the open
set $\alpha^{-1}(U_{a_{i}})$ can be viewed as the countable union of disjoint
open intervals. Let $(d,d^{\prime})$ be one of those intervals. Notice that
$\alpha(d)\in A^{\prime}\cup B^{\prime}$ and $\alpha(d^{\prime})\in
A^{\prime}\cup B^{\prime}$ as well. Moreover, we have that $A^{\prime}\cup
B^{\prime}\cap U_{a_{i}}=\emptyset$, and therefore there is $\epsilon>0$ such
that $\alpha(x)\not=a_{i}$ for
$x\in(d,d+\epsilon)\cup(d^{\prime}-\epsilon,d^{\prime})$. If we restrict the
function $\alpha$ to the interval $[d+\epsilon/2,d^{\prime}-\epsilon/2]$ and
consider it as a path, then by Proposition 4.1 we have that this path is
homotopic to a path $\gamma$ with $a_{i}\not\in\operatorname{Im}(\gamma)$.
Applying this process for every open interval in $\alpha^{-1}(U_{a_{i}})$ and
every $i$, we can construct a loop $\alpha_{1}$ homotopic to $\alpha$ such
that $A\cap\operatorname{im}(\alpha_{1})=\emptyset$. Let $\alpha_{2}$,
$\alpha_{3}$ be the paths defined by

$\displaystyle\alpha_{2}(x)$
$\displaystyle=\left\\{\begin{array}[]{lcc}a^{\prime}_{j}&if&\alpha_{1}(x)=b_{i,j}\\\
b^{\prime}_{j}&if&\alpha_{1}(x)=c_{i,j}\\\ \alpha_{1}(x)&if&\alpha_{1}(x)\in
A^{\prime}\cup B^{\prime}\end{array}\right.,$ $\displaystyle\alpha_{3}(x)$
$\displaystyle=\left\\{\begin{array}[]{lcc}b_{1,j}&if&\alpha_{2}(x)=a^{\prime}_{j}\\\
\\\ c_{1,j}&if&\alpha_{2}(x)=b^{\prime}_{j}\end{array}\right..$

Notice that $\alpha_{2}$ is indeed a path because
$\alpha_{2}^{-1}(U_{x})=\emptyset$ for $x\not\in A^{\prime}\cup B^{\prime}$,
$\alpha_{2}^{-1}(U_{a^{\prime}_{i}})=\alpha_{1}^{-1}(U_{a^{\prime}_{i}})$ and
$\alpha_{2}^{-1}(U_{b^{\prime}_{i}})=\alpha_{1}^{-1}(U_{b^{\prime}_{i}})$ for
$1\leq i\leq 2n$. Similarly, $\alpha_{3}$ is a path because
$\alpha_{3}^{-1}(U_{b_{1,j}})=\alpha_{2}^{-1}(U_{a^{\prime}_{j}})$ and
$\alpha_{3}^{-1}(U_{c_{1,j}})=\alpha_{2}^{-1}(U_{b^{\prime}_{j}})$.

The map $H:[0,1]\times[0,1]\rightarrow T$ defined by

$H(s,t)=\left\\{\begin{array}[]{lcl}\alpha_{1}(s)&\text{if}&t\in[0,1/4)\\\
\alpha_{2}(s)&\text{if}&t\in[1/4,1/2]\\\
\alpha_{3}(s)&\text{if}&t\in(1/2,3/4)\\\
a_{1}&\text{if}&t\in[3/4,1]\end{array}\right.$

is continuous: for $1\leq i\leq 2n$ we have
$H^{-1}(U_{b^{\prime}_{i}})=\alpha_{1}^{-1}(U_{b^{\prime}_{i}})\times[0,3/4)$
and
$H^{-1}(U_{a^{\prime}_{i}})=\alpha_{1}^{-1}(U_{a^{\prime}_{i}})\times[0,3/4)$.
For $1<i\leq n$,
$H^{-1}(U_{b_{i,j}})=\alpha_{1}^{-1}(U_{b_{i,j}})\times[0,1/4)$ and
$H^{-1}(U_{c_{i,j}})=\alpha_{1}^{-1}(U_{c_{i,j}})\times[0,1/4)$; in the case
$i=1$ we have

$H^{-1}(U_{b_{1,j}})=\left(\alpha_{1}^{-1}(U_{b_{1,j}})\times[0,1/4)\right)\cup\left(\alpha_{3}^{-1}(U_{b_{1,j}})\times(1/2,3/4)\right)$

and

$H^{-1}(U_{c_{1,j}})=\left(\alpha_{1}^{-1}(U_{c_{1,j}})\times[0,1/4)\right)\cup\left(\alpha_{3}^{-1}(U_{c_{1,j}})\times(1/2,3/4)\right).$

And lastly, we have

$H^{-1}(U_{a_{1}})=\left(\alpha_{1}^{-1}(U_{a_{1}})\times[0,1/4)\right)\cup\left((1/2,1]\times(1/2,1]\right).$

Then $\alpha_{1}$ is null-homotopic, and therefore $\alpha$ is null-homotopic
as well because these two loops are homotopic.

###  4.2 Examples

We present some examples by constructing finite topological spaces associated
to the finite groups $\mathbb{Z}_{2}$, $\mathbb{Z}_{3}$ and $\mathbb{Z}_{4}$
respectively. A useful way to describe finite spaces is by using _Hasse
diagrams_ (cf. [3] Example 1.1.1). The Hasse diagram of a partially ordered
space $X$ is a graph whose vertices are the points of $X$ and whose edges are
the ordered pairs $(x,y)$ such that $x<y$ and there exists no $z\in X$ such
that $x<z<y$. In the planar description of a Hasse diagram we will not draw an
arrow from $x$ to $y$, using a segment instead with $x$ lower than $y$. For a
finite topological space $X$ and $x,y\in X$, we define the order $\preceq$
where $x\preceq y$ if and only if $y\in U$ implies $x\in U$ for all $U$ open
in $X$.

  * I.

For $\mathbb{Z}_{2}$ we have the set
$\Sigma_{2}=\\{a_{1}^{\prime},a_{2}^{\prime},a,b_{1}^{\prime},b_{2}^{\prime},b_{1},\ldots,b_{4},c_{1},\ldots,c_{4}\\}$
with basic open sets $U_{c_{i}}=\\{c_{i}\\}$ for $1\leq i\leq 4$,
$U_{b_{i}}=\\{b_{i},c_{i-1},c_{i}\\}$ for $1\leq i\leq 4$ with $i$ taken mod
$4$, $U_{b^{\prime}_{1}}=\\{b^{\prime}_{1}\\}\cup\\{c_{i}\in\Sigma_{2}\mid
i\text{ is odd}\\}$,
$U_{b^{\prime}_{2}}=\\{b^{\prime}_{2}\\}\cup\\{c_{i}\in\Sigma_{2}\mid i\text{
is even}\\}$, $U_{a}=C\cup B\cup\\{a\\}$ with $C=\\{c_{1},\ldots,c_{4}\\}$ and
$B=\\{b_{1},\ldots,b_{4}\\}$,
$U_{a^{\prime}_{1}}=\\{a^{\prime}_{1},b^{\prime}_{1},b^{\prime}_{2}\\}\cup
C\cup\\{b_{i}\in\Sigma_{2}\mid i\text{ is odd}\\}$ and
$U_{a^{\prime}_{2}}=\\{a^{\prime}_{2},b^{\prime}_{1},b^{\prime}_{2}\\}\cup
C\cup\\{b_{i}\in\Sigma_{2}\mid i\text{ is even}\\}$. Below is the Hasse
diagram for $\Sigma_{2}$:

$a^{\prime}_{2}$$a$$a^{\prime}_{1}$$b_{2}$$b_{1}$$b^{\prime}_{1}$$b_{3}$$b_{4}$$b^{\prime}_{2}$$c_{1}$$c_{2}$$c_{3}$$c_{4}$
Figure 1: Hasse diagram for $\mathbb{Z}_{2}$

  * II.

For $\mathbb{Z}_{3}$ we have the set
$\Sigma_{2}=\\{a_{1}^{\prime},a_{2}^{\prime},a,b_{1}^{\prime},b_{2}^{\prime},b_{1},\ldots,b_{6},c_{1},\ldots,c_{6}\\}$
with basic open sets $U_{c_{i}}=\\{c_{i}\\}$ for $1\leq i\leq 6$,
$U_{b_{i}}=\\{b_{i},c_{i-1},c_{i}\\}$ for $1\leq i\leq 6$ with $i$ taken mod
$6$, $U_{b^{\prime}_{1}}=\\{b^{\prime}_{1}\\}\cup\\{c_{i}\in\Sigma_{2}\mid
i\text{ is odd}\\}$,
$U_{b^{\prime}_{2}}=\\{b^{\prime}_{2}\\}\cup\\{c_{i}\in\Sigma_{2}\mid i\text{
is even}\\}$, $U_{a}=C\cup B\cup\\{a\\}$ with $C=\\{c_{1},\ldots,c_{6}\\}$ and
$B=\\{b_{1},\ldots,b_{6}\\}$,
$U_{a^{\prime}_{1}}=\\{a^{\prime}_{1},b^{\prime}_{1},b^{\prime}_{2}\\}\cup
C\cup\\{b_{i}\in\Sigma_{2}\mid i\text{ is odd}\\}$ and
$U_{a^{\prime}_{2}}=\\{a^{\prime}_{2},b^{\prime}_{1},b^{\prime}_{2}\\}\cup
C\cup\\{b_{i}\in\Sigma_{2}\mid i\text{ is even}\\}$. The corresponding Hasse
diagram is:

$a^{\prime}_{2}$$a$$a^{\prime}_{1}$$b_{3}$$b_{2}$$b_{1}$$b^{\prime}_{1}$$b_{4}$$b_{5}$$b_{6}$$b^{\prime}_{2}$$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$$c_{6}$
Figure 2: Hasse diagram for $\mathbb{Z}_{3}$

  * III.

Finally, for $\mathbb{Z}_{4}$ we have the set
$\Sigma_{2}=\\{a_{1}^{\prime},a_{2}^{\prime},a,b_{1}^{\prime},b_{2}^{\prime},b_{1},\ldots,b_{8},c_{1},\ldots,c_{8}\\}$
with basic open sets $U_{c_{i}}=\\{c_{i}\\}$ for $1\leq i\leq 8$,
$U_{b_{i}}=\\{b_{i},c_{i-1},c_{i}\\}$ for $1\leq i\leq 8$ with $i$ taken mod
$8$, $U_{b^{\prime}_{1}}=\\{b^{\prime}_{1}\\}\cup\\{c_{i}\in\Sigma_{2}\mid
i\text{ is odd}\\}$,
$U_{b^{\prime}_{2}}=\\{b^{\prime}_{2}\\}\cup\\{c_{i}\in\Sigma_{2}\mid i\text{
is even}\\}$, $U_{a}=C\cup B\cup\\{a\\}$ with $C=\\{c_{1},\ldots,c_{8}\\}$ and
$B=\\{b_{1},\ldots,b_{8}\\}$,
$U_{a^{\prime}_{1}}=\\{a^{\prime}_{1},b^{\prime}_{1},b^{\prime}_{2}\\}\cup
C\cup\\{b_{i}\in\Sigma_{2}\mid i\text{ is odd}\\}$ and
$U_{a^{\prime}_{2}}=\\{a^{\prime}_{2},b^{\prime}_{1},b^{\prime}_{2}\\}\cup
C\cup\\{b_{i}\in\Sigma_{2}\mid i\text{ is even}\\}$. The corresponding Hasse
diagram is:

$a^{\prime}_{2}$$a$$a^{\prime}_{1}$$b_{4}$$b_{3}$$b_{2}$$b_{1}$$b^{\prime}_{1}$$b_{5}$$b_{6}$$b_{7}$$b_{8}$$b^{\prime}_{2}$$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$$c_{6}$$c_{7}$$c_{8}$
Figure 3: Hasse diagram for $\mathbb{Z}_{4}$

######  Remark 4.2.

The cardinality of the finite topological space $X_{\mathbb{Z}_{n}}$
constructed in this section for the group $\mathbb{Z}_{n}$ is the same as in
Theorem 3.6 of the previous section applied to the group $\mathbb{Z}_{n}$.
However, from the discussion at the beginning of this section, the finite
topological space associated to the group $\mathbb{Z}_{n}\times\mathbb{Z}_{m}$
by the method above turns out to be $X_{\mathbb{Z}_{n}}\times
X_{\mathbb{Z}_{m}}$. The cardinality of the latter is greater than the
cardinality provided by Theorem 3.6 applied to the group
$\mathbb{Z}_{n}\times\mathbb{Z}_{m}$. Actually, neither of the two
constructions presented in this paper provides us with a minimal finite
topological space associated to a finitely presented group $G$, in the sense
of having minimal cardinality in the class of spaces $X_{G}$ such that
$\pi(X_{G})\cong G$. The Hasse diagrams presented above show that the
construction described throughout Section 3 provides reduced spaces in the
sense that the topology described in $X_{\mathbb{Z}_{n}}$ can not be reduced
by using beat points [3].

## References

  * [1] P. Alexandroff, Mat. sbornik, Diskrete Raume 2 (1937) 501–519.
  * [2] M. C. McCord, et al., Singular homology groups and homotopy groups of finite topological spaces, Duke Mathematical Journal 33 (3) (1966) 465–474.
  * [3] J. Barmak, Algebraic Topology of Finite Topological Spaces and Applications, Lecture Notes in Mathematics, Springer Berlin Heidelberg, 2011.
URL https://books.google.com.co/books?id=KR3zCAAAQBAJ

  * [4] J. Munkres, Topology, Featured Titles for Topology Series, Prentice Hall, Incorporated, 2000.
  * [5] A. Hatcher, Algebraic topology, Cambridge Univ. Press, Cambridge, 2000.
URL https://cds.cern.ch/record/478079

  * [6] A. T. Lundell, S. Weingram, The topology of CW complexes, Springer Science & Business Media, 2012.


# Counting $N$ Queens

Nick<EMAIL_ADDRESS>
Booth School of Business
University of Chicago Vadim<EMAIL_ADDRESS>
Operations Research
George Mason University

###### Abstract

Gauss proposed the problem of how to enumerate the number of solutions for
placing $N$ queens on an $N\times N$ chess board, so no two queens attack each
other. The N-queen problem is a classic problem in combinatorics. We describe
a variety of Monte Carlo (MC) methods for counting the number of solutions. In
particular, we propose a quantile re-ordering based on the Lorenz curve of a
sum that is related to counting the number of solutions. We show his approach
leads to an efficient polynomial-time solution. Other MC methods include
vertical likelihood Monte Carlo, importance sampling, slice sampling,
simulated annealing, energy-level sampling, and nested-sampling. Sampling
binary matrices that identify the locations of the queens on the board can be
done with a Swendsen-Wang style algorithm. Our Monte Carlo approach counts the
number of solutions in polynomial time.

Keywords: N-Queens Problem, MCMC, Random Polynomial time, Split Sampling,
Vertical Likelihood.

##  1 Introduction

Gauss introduced the N-queens problem in 1850. The objective is to position
$n$ queens on an $n\times n$ chess board such that no one queen can be taken
by any other. The N-queen problem is a classic problem in combinatorics. It is
a generalization of the 8-queen problem, which asks for the number of ways to
place 8 queens on a $8\times 8$ chess board so that no two queens attack each
other. The 8-queen problem has 92 solutions. This follows from the fact that a
traditional chess board with $n=8$ we have $=12$ configurations. If we
consider the rotations, then the number of configurations become $12\times
8-1\times 4=92$ as 4 of the configurations are identical. Thus, we have $8$
possible rotations for all the 12 solutions.

The position of the Queens can be represented as a binary matrix. Thus, we can
view the problem of counting the number of solutions as a problem of sampling
from binary Markov random fields. Specifically, the position of the queens can
be represented as $x\in\\{1,\ldots,n\\}^{n}$, where $x_{i}$ is the column of
the queen on the $i$th row. Figure 1 shows the $\\{6,4,7,1,8,2,5,3\\}$
configuration. Naive Monte Carlo samples $x_{i}$ independently of
$\\{1,\ldots,n\\}$ for $i=1,\ldots,n$. Then the objective function $S$ could
be chosen as the number of pairs of queens that can attack each other. The
problem with this approach is that the probability of a correct configuration
is very small.

[setfen=5Q62/3Q4/6Q1/Q7/7Q/1Q6/4Q3/2Q5,moveid=16w]

Figure 1: A solution to the $8$-Queens problem

The problem with naive Monte Carlo (MC) is that the configurations represent
rare events and thus, are hard to sample using naive approaches. For example,
when $n$=9, there are $92$ correct configurations out of $4,426,165,368$
possible configurations, making the ratio to be $2.0785\times 10^{.}{-8}$.
This ratio decreases as $n$ goes up. The N-queen problem has been solved
exactly for $n$ up to 15 and estimated by Monte Carlo for $n$ between 16 and
25. Simkin [2022] showed that there exists a constant $\alpha=1.942\pm 3\times
10^{-3}$ such that the number of configuration sis $((1\pm
o(1))ne^{-\alpha})n$. Thus, for $n=25$ there are approximately $10^{15}$
configurations and $10^{31560}$ for $n$ = 10000. Counting # $N$-Queens can be
recast as a rare event expectation calculation.

$N$-Queens was previously analyzed by Higdon [1998], Swendsen and Wang [1987],
Polson [1996], Rubinstein and Kroese [2016]. Sampling from binary random
Markov field can be done in polynomial time using the algorithm that was first
proposed by Swendsen and Wang [1987]. The first key insight is to replace the
counting problem by a problem of calculating the probability of a rare event
Diaconis and Holmes [1995]. Second, we need to find a fast algorithm to sample
from a distribution, which can be done in polynomial time due to Swendsen and
Wang [1987]. Third, to reorder the sum as the sum involving the quantile
importance sampling. It is well known, that naive MCMC or the product
estimator is not polynomial. Thus, we must do the quantile reordering to
achieve the polynomial time.

A related important problem is the $N$-Queens completion problem and other
approach can be extended to this class of problems. Given an allocation of
queens can it be extended to a solution. This is related to the classic $P=NP$
problem as it is known to the #NP-hard If an efficient solution exists for one
#NP-hard problem, it can be used for all! Our class of algorithms provides an
avenue to finding RP-time algorithms.

The rest of the paper is outlined as follows. Section 2 describes Monte Carlo
counting methods. Including naive MC and sequential MC methods. By
constructing an equivalent rare event expectation problem. Section 3 provides
energy domain methods which increase efficiency. Finally, Section 4 concludes
with comments on the completion problem and the relationship to the $P=NP$
problem.

##  2 Monte Carlo MC Counting

Let $x\in\mathcal{X}$ be an element in the set of binary matrices. A matrix
describes a queen placement. The number of solutions will be counted as a rare
event probability problem due to Rubinstein et al. [2013]. Let

$S(x)=1\;\;{\rm if}\;x\;{\rm solution}\;\;{\rm and}\;\;S(x)=0\;\;{\rm
if}\;x\;{\rm not\;a\;solution}$

The key insight is the fact that the counting problem can be solved via
estimating the rare event probability

$\mathbb{P}\left(\\#solns\right)=E_{p}\left[\mathbb{I}_{S(x)>0}\right]=\frac{\\#solns}{\\#matrices},$

where $p(x)$ denotes the uniform distribution over the set of binary placement
matrices. This allows as to count the number of possible solutions as we can
count the number of possible matrices analytically.

The key insight is that counting is computationally equivalent to a rare event
probability problem For example, in the $8$-queens problem rather than
counting we can estimate using naive MC, the probability

$\rho=P(S(x)=0)=92/4,426,165,368=2.0785\times 10^{-8}$

where here $S(x)$ can be defined as the number of attacking positions of the
queens.

When $N=8$ there are $4,426,165,368$ possible binary matrices and this
provides the denominator. The problem now is how to calculate $\hat{\rho}$ in
random polynomial RP-time! Naive MC will not provide such a method.

When the counting problem can be embedded into a sub-problem we can save on
the efficient computation. For example the $N$-queen problem is a sun-problem
of the $N$-rook problem and there are far fewer $8^{8}=16,777,216$ possible
allocations for the denominator. One then samples a permutation of the Queens
with $8!=40,320$ possible permutations and simply counts the number of
solutions, This brute force approach will not provide a polynomial time
algorithm for general $N$.

###  2.1 Product Estimator

The issue then becomes how to calculate the rare event probability
$E_{p}\left[\mathbb{I}_{S(x)>0}\right]$ [Diaconis and Holmes, 1995]? We will
do this by a carefully chosen sequential Monte Carlo algorithm. The classic
Monte Carlo scheme uses random samples $x^{(i)},1\leq i\leq N$

$\hat{Z}=\frac{1}{N}\sum_{i=1}^{N}S(x^{(i)})$

The convergence of the variance of $\hat{Z}$ is $O(N^{-1})$.

It is more efficient to use a sequential procedure. Define

$Z_{\gamma}=E_{p}\left[\mathbb{I}_{S(x)>\gamma}\right]\;\;{\rm
where}\;\;0\leq\gamma\leq 1.$

Then, imagine an annealing schedule
$0:=\gamma_{0}<\gamma_{1}<\ldots<\gamma_{M}<1$. This allows us to write the
quantity of interest, with $Z_{1}:=1$, and

$Z:=Z_{0}=E_{p}\left[\mathbb{I}_{S(x)>0}\right]=\prod_{\gamma}\frac{Z(\gamma_{i})}{Z(\gamma_{i-1})}Z_{1}.$

The key is to (sequentially) find an optimal annealing schedule so that each
of the ratios $Z(\gamma_{i})/Z(\gamma_{i-1})$ can be calculated in polynomial
time.

Now one sequentially samples from $\pi(x|S(x)>m_{t-1})$ and counts how many
samples satisfy $S(x)>m_{t}$.

$\rho=\mathbb{P}\left(S(x)>m_{t}|S(x)>m_{t-1}\right)=\mathbb{P}\left(S(x)>m_{t}\right)\mathbb{P}\left(S(x)>m_{t-1}\right)=Z_{m_{t}}/Z_{m_{t-1}}$

Independent samples gives relative mean squared error

$\hat{Z}=\prod_{t=1}^{T}\widehat{\frac{Z_{m_{t}}}{Z_{m_{t}-1}}}\;\;{\rm
and}\;\;\frac{Var\left(\hat{Z}\right)}{\mathbb{E}(\hat{Z})^{2}}=\prod_{t=1}^{T}\left(\frac{\hat{\sigma}_{m_{t}}^{2}}{\hat{\mu}_{m_{t}}^{2}}+1\right)-1$

with mean $\mathbb{E}(\hat{Z}_{m_{t}}/\hat{Z}_{m_{t-1}})=\hat{\mu}_{m_{t}}$
and variance $\hat{\sigma}_{m_{t}}^{2}$.

The key is to pick i $m_{t}$ so coefficients of variation are all equal
reduces variance. A “well-balanced” cooling schedule, with Chebyshev-Hoeffding
bounds, leads to a running time of $O\left((\ln(1/Z))^{2}\right)$ steps.
However, this is not RP. See also the cross-entropy method of Rubenstein.

#### Cross-Entropy

CE [Rubinstein and Kroese, 2016] methods solve the problem of estimating

$Z=P_{h}(S(X)\geq\gamma)=E{I(S(X)\geq\gamma)}$

Here $X\sim h_{\theta}(X)$ and the parameters $\theta$ of the sampling
distribution $h$ and the temperature parameter $\gamma$ are estimated
sequential and jointly. The CE method estimates optimal $\theta^{*}$. This is
achieved by finding an importance sampling density $g$ that is close to the
optimal one

$g^{*}(x)=\dfrac{f(x;u)I(S(X)\geq\gamma)}{Z}.$

The closeness in measured uins KL divergence

$D(g^{*},g)=\mathbb{E}{\log\dfrac{g^{*}(X)}{g(X)}}=\int
g^{*}(x)\log\dfrac{g^{*}(X)}{g(X)}dx.$

Rubinstein and Kroese [2016] (p.211) use a different embedding and use a
combinatorial optimisation method to find solutions using a Gibbs sampler.
This requires exchanging queens on the chess board. They define $S(x)$ to
represent the amount of “threat” of the queens. They simply add the number of
queens minus one for each row and column. An optimal solution corresponds to
the minimum of $S$ namely zero. Our approach directly counts the number of
solutions and provides theoretical methods to address the random polynomial
time nature of our algorithm.

If the function $S(x)$ counts the number of solutions to the N-Queens problem,
we can use the Boltzman distribution

$\pi_{\gamma}(x)=\dfrac{1}{Z(\gamma)}\exp(-S(x)/\gamma).$

As $\gamma\rightarrow\infty$, $\pi_{\infty}$ collapses to uniform distribution
on the set of solutions $x_{\infty}=\\{x\in X~{}:~{}\arg\min_{x}S(x)\\}$.
Thus, the size of the set $x_{\infty}$ counts the number of solutions.

###  2.2 Swendsen-Wang sampling

Another problem is to count the number of the correct solutions. This problem
we can solve by sampling configurations $x\in\\{1,\ldots,n\\}^{n}$ where
$p_{i}$ is uniform on the column $x_{i}$ from

$p(x)=\prod_{i=1}^{n}p_{i}(x_{i}),$

Swendsen and Wang [1987] use a latent variable and introduce slice variables
$u_{i}$ and joint distribution

$p(x,u)=\prod_{i=1}^{n}I(0<u_{i}\leq p_{i}(x_{i})),$

The Swendsen-Wang sampling is a variation of the slice sampling algorithm
Higdon [1998]. We will take advantage of the “Fortuin-Kasteleyn-Swendsen-Wang”
(FKSW) joint distribution identified explicitly in Edwards and Sokal [1988]
over color variables $s$ and a bond variable for each edge $E$ in the graph.

The joint distribution is

$P(s,d)=\dfrac{1}{Z}\prod_{(i,j)\in
E}\left((1-p)\delta_{d_{ij,0}}+p\delta_{d_{ij,1}}\delta_{d_{s_{i},s_{j}}}\right).$

The marginal distribution over $s$ in the FKSW model is the Potts
distribution.

$p(s)\propto e^{H},~{}H=-J_{p}\sum_{(i,j)}\delta(s_{i},s_{j}).$

The marginal distribution over the bonds is the random cluster model of
Fortuin and Kasteleyn [1972]:

$P(d)=\dfrac{1}{Z}p^{D}(1-p)^{|E|-D}q^{C(d)}=\dfrac{1}{Z}\exp{\left(D\log\left(d^{J}-1\right)\right)}e^{-J|E|}q^{C(d)},$

where $C(d)$ is the number of connected components in a graph with edges
wherever $d_{ij}=1$, and $D=\sum_{(ij)\in E}d_{ij}$.

The algorithm of Swendsen and Wang [1987] performs block Gibbs sampling on the
joint model by alternately sampling from $P(d_{ij}\mid s)$ and $P(s\mid
d_{ij})$. This can convert a sample from any of the three distributions into a
sample from one of the others.

#### Clustering Algorithm

Pick $i,j$, choose symbols $a,b$. Then scan row $i$ and choose column $j$
where symbol $s_{ij}$ is $a$. Search other rows for the symbol $b$ at the same
column For each row $i$ use bond variable $u$. The joint distribution is

$\pi(x)\propto\pi_{0}(x)\prod_{k}e^{-\frac{1}{\gamma}S_{k}(x)}$

marginal from joint

$\pi(x,u)\propto\pi_{0}(x)\prod_{k}I\left(0<u_{k}<e^{-\frac{1}{\gamma}S_{k}(x)}\right)$

See also plit sampling Birge et al. [2013] and vertical likelihood Monte Carlo
Polson and Scott [2015] for optimal importance sampling choice.

Rubinstein and Kroese [2016] and Skilling [2006] nested sampling uses cross-
entropy to sample (not optimal) - and empirical quantiles of the Boltzmann
distribution. This is a family of distributions defined as

$\pi_{\gamma}(x)=\frac{e^{-\frac{1}{\gamma}S(x)}}{\sum_{x\in\mathcal{X}}e^{-\frac{1}{\gamma}S(x)}}$

Picking $\gamma$ can be done by using a discrete grid or by using an adaptive
schedule. Masry and Cambanis [1990] provide a trapezoidal rule.

##  3 Energy-domain counting

###  3.1 Vertical Likelihood Sampling

In the vertical likelihood approach Polson and Scott [2015], we express $Z$ in
a continuous fashion and use importance sampling

$\displaystyle Z$
$\displaystyle=E_{p}\left[\mathbb{I}_{S(x)>0}\right]=\int_{0}^{1}Z(\gamma)d\gamma=\int_{0}^{1}Z(\gamma)\frac{1}{\Omega(\gamma)}\Omega(\gamma)d\gamma$

The key is that $\Omega(\gamma)$ can be chosen in an optimal fashion.

This can be performed the simulation in a sequential fashion with an
increasing schedule as $\gamma$ goes from $0$ to $1$ as the simulation
proceeds. The key is to do this in polynomial time.

Some methods use fixed schemes for $\Omega(\gamma)$. For example, nested
sampling uses $\gamma_{i}=e^{-i/N}$ but there is no guarantee that this is
polynomial time.

Polson and Scott show that many of the commonly used SMC methods simply
correspond to difference choices of $\Omega(\gamma)$. We can think of
$\Omega(\gamma)$ as providing the optimal annealing schedule. How quickly can
you increase $\gamma$. Phase change when you increase $\gamma$ and the number
of solutions explodes exponentially. Hence, you have to be able to control
this.

Examples of energy-domain features include the micro-canonical distribution
over the equi-energy surface $\\{x:h(x)=s\\}$, as well as the microcanonical
average of a state function,

$\nu_{f}(s)=\mathbb{E}\\{S(x)\mid h(x)=s\\}\,,$

which is independent of temperature. Another energy-domain feature is the
density of states. In the discrete case, this is the number of states with a
given energy level: $N(s)=\\#\\{x:h(x)=s\\}$. In the case where $\mathcal{X}$
is a continuous state space, $N(s)$ is the function such that the volume of
the set $\\{x:h(x)\in(s,s+ds)\\}$ is approximately $N(s)ds$.

The statistical-mechanics community has developed a wide class of Monte Carlo
methods to approximate energy-domain features. We refer to these collectively
as energy-level samplers. These methods all share the goal of biasing the
draws toward higher-energy states by means of an iterative re-balancing
scheme.

To motivate these methods, let $X$ be a draw from the Boltzmann distribution,
assuming $T=1$ without loss of generality. Let $\eta=h(X)$ be the
corresponding random energy level, with distribution

$P(\eta=s)=\sum_{x:h(x)=s}e^{-s}=e^{-s}\ N(s)\,.$ (1)

The multi-canonical sampler of Berg and Neuhaus [1991] attempts to re-balance
the sampler so that the implied energy distribution becomes flat:
$P(\eta=s)\propto\mbox{constant}$. As (1) suggests, this is accomplished by
sampling states $x$ with weight inversely proportional to the density of
states $N(s)$.

If the density of states is unknown, the Wang–Landau algorithm [Wang and
Landau, 2001b, a] provides a suitable variation. It involves estimating $N(s)$
via an iterative re-balancing approach, and has been generalized to a wider
class of statistical problems [Bornn et al., 2013]. For a short overview of
the adaptive Wang–Landau algorithm, see the Appendix.

An even more extreme re-balancing is the $1/k$-ensemble sampler [Hesselbo and
Stinchcombe, 1995]. Let

$Z(s)=\\#\\{x:h(x)\leq s\\}=\sum_{t\leq s}N(t)$ (2)

define the cumulative number of states with energy as least as small as $s$.
In the $1/k$-ensemble sampler, states are sampled with weight proportional to
$Z(s)$, rather than $N(s)$ as in the multi-canonical sampler. This makes it
even easier for the sampler to traverse high-energy (low-probability) regions
of the state space.

#### The connection with latent-variable methods.

Here we note a connection between auxiliary-variable methods and energy-level
samplers that underlies our recommended approach for choosing an importance
function. Motivated by the latent-variable scheme at the heart of slice
sampling [Damlen et al., 1999], consider the joint distribution

$p(x,u)\propto w(u)\ \mathbb{I}\\{u\geq h(x)\\}\,.$ (3)

Let $(X,U)$ be a random draw from this joint distribution, and just as above,
consider the implied distribution over the random energy level $h(X)$:

$p(h(X)=s)\propto\sum_{x:h(x)=s}w(s)=w(s)N(s)\,.$

If $w(s)=e^{-s}$, we recover the canonical ensemble: that is, the distribution
over the energy level implied by the original Boltzmann distribution (1). On
the other hand, if we set $w(s)=1/N(s)$, we see that $P(h(X)=s)$ is now
constant in $s$, as in the multicanonical sampler and Wang–Landau algorithm.
Finally, if we set $w(s)=1/Z(s)$ as in (2), then we obtain

$P(h(X)=s)\propto N(s)/Z(s)\,,$

as in the $1/k$-ensemble sampler of Hesselbo and Stinchcombe [1995].

To summarize: many different sampling schemes historically used for energy-
domain features can be interpreted as different choices for the weight
function in a joint distribution defined via an auxiliary variable (3). The
particular form of this joint distribution suggests an interesting connection
between slice sampling and energy-level sampling that can be usefully
exploited.

###  3.2 Quantile Re-ordering

We can compute $Z=\mathbb{E}(X)=.\int_{\mathcal{X}}L(x)p(dx)$ In many cases,
we wish to calculate expectations: $Z=E(X)=\sum_{x\in\mathcal{X}}L(x)p(x)$
where $L(x)$ is typically in conflict with $p(x)$. It is useful to re-order
this sum in terms of quantiles before trying to enumerate with Monte Carlo.

Using the mean identity for a positive random variable and its CDF or
equivalently, via the Lorenz curve, we obtain the key identities

$\displaystyle E(X)$
$\displaystyle=\int_{\mathcal{X}}L(x)p(dx)=\int_{0}^{\infty}(1-F_{X}(x))dx=\int_{0}^{\infty}Z(u)du$
$\displaystyle E(X)$
$\displaystyle=\int_{0}^{1}F_{X}^{-1}(s)ds=\int_{0}^{1}\Lambda(1-s)ds=\int_{0}^{1}\Lambda(s)ds$

We do not have to assume that $F^{-1}(s)$, or equivalently $\Lambda(s)$, is
available in closed form, rather we can find an unbiased estimate of this by
simulating the Lorenz curve.

Lorenz curve of the likelihood ordinate $Y\equiv L(X)$ where $X\sim p(x)$. The
Lorenz curve, $\mathcal{L}$ of $X$ is defined in terms of its CDF, $F_{X}(x)$,
as

$\displaystyle\mathcal{L}(u)$
$\displaystyle=\frac{1}{Z}\int_{0}^{u}F_{X}^{-1}(s)ds\;\;\text{ where
}\;u\in[0,1]$ $\displaystyle Z$
$\displaystyle=\mathbb{E}(X)=\int_{\mathcal{X}}L(x)p(dx)\;.$

One feature of a Lorenz curve is that is provides a way to evaluate

$\mathbb{E}(X)=\int_{\mathcal{X}}L(x)p(dx)=\int_{0}^{1}F_{X}^{-1}(s)ds$

Note that under the transformation $u=F_{X}(x)$, we have

$E(X)=\int_{0}^{1}F_{X}^{-1}(u)du=\int_{0}^{\infty}xf_{X}(x)dx$

Here we use Lebesgue rather than Riemann integration. Yakowitz et al. [1978]
shows that the MC standard errors are lower for the quantile approach.

The pseudo-inverse of $Z(y)$, denoted $\Lambda(s)$ and defined as

$\Lambda(s)=\sup\\{y:Z(y)>s\\}\,,$ (4)

which, like $Z(y)$, is non-increasing.

Intuitively, $\Lambda(s)$ gives the value $y$ such that $s$ is the fraction of
prior draws with likelihood values larger than $y$.

$Z=\int_{\mathcal{X}}L(x)\
dP(x)=\int_{\mathcal{X}}\int_{0}^{\infty}I\\{y<L(x)\\}\ dy\
dP(x)=\int_{0}^{\infty}Z(y)\ dy\,$ (5)

Now, exploiting the fact that $s<Z(y)$ if and only if $y<\Lambda(s)$:

$Z=\int_{0}^{\infty}\int_{0}^{1}\mathbb{I}\\{s<Z(y)\\}\ ds\
dy=\int_{0}^{\infty}\int_{0}^{1}\mathbb{I}\\{y<\Lambda(s)\\}\ ds\
dy=\int_{0}^{1}\Lambda(s)\ ds\,.$ (6)

We start with the Lorenz identity, stated as a lemma, that is at the heart of
nested sampling and the quantile importance sampling.

Since $X\sim P$, and $U\sim U(0,1)$, it follows that
$\Lambda(U)\stackrel{{\scriptstyle D}}{{=}}L(X)$, that is the likelihood
ordinates are distributionally the same as the $\Lambda(u)$ values at uniform
grid points. It also follows from the definition of $Z$, that
$Z(L(X))\stackrel{{\scriptstyle D}}{{=}}U(0,1)$. Let us consider the slightly
modified alternative presentation of nested sampling by Polson and Scott
(2014).

The evidence $Z=\int_{0}^{1}\Lambda(s)ds$ is approximated at grid points
$(s_{1}>s_{2}>\ldots>s_{n})$ by a numerical integration rule:

$Z^{N}(s)=\int_{0}^{1}\Lambda(s_{i})w_{i},\;\;{\rm
for}\;\;w_{i}=s_{i-1}-s_{i},\;{\rm or}\;w_{i}=1/2(s_{i-1}-s_{i+1})$

In the case of nested sampling, one can use the deterministic grid points
$s_{i}=\exp(-i/n)$ for $i=1,\ldots,m$ for a moderate $n$ and a large $m$.
Polson and Scott (2014) recommends a modest $n=20$ and a large $n=1000$.

#### MC error

The advantage of this method is that the MC error bounds are $O(N^{-4})$. For
$p=\mathbb{I}_{[0,1]}$, a convergence rate of $0(N^{-4})$ is available for a
Riemann sum estimator of the form

$\hat{Z}=\sum_{i=1}^{N-1}(u_{(i+1)}-u_{(i)})\frac{L(u_{(i+1)})+L(u_{(i)})}{2}$

where $u_{(i)}\sim U(0,1)$ are ordered uniform draws from
$p=\mathbb{I}_{[0,1]}$.

$\hat{Z}=\sum_{i=1}^{N-1}(x_{(i+1)}-x_{(i)})p(x_{(i)})L(x_{(i)})$

where $x_{(1)}\leq\ldots\leq x_{(n)}$ are the ordered sample associated with
$(x_{1},\ldots,x_{n})\sim P$.

#### Concentration Function

Let $P,Q$ be probability measures on $x\in\mathcal{X}$. The likelihood ratio
$l_{P}(x):=P(x)/Q(x)$ is a random variable whose expectation, $E(l_{P})=1$.

Let $m(t)$ be the distribution function of $l_{P}$ and

$Q\left\\{x\in\mathcal{X}:l_{P}(x)\leq t\right\\}=\int_{l_{P}(x)\leq t}Q(x)dx$

with set-theoretic inverse $m^{-1}(x)=\sup\left\\{t:m(t)\leq x\right\\}$. The
concentration function is the Lorenz curve of the likelihood ratio r.v.
defined by

$\phi_{P}(u)=\int_{0}^{u}m^{-1}(z)dz$

Notice that $m(0)=0$ and $m(1)=1$

A weighted version of the concentration function can now be defined as
follows. First, define the titled measure

$Q^{L}(x):=\frac{L(x)Q(x)}{\int_{\mathcal{X}}L(x)Q(x)dx}$

where now the base measure $Q^{L}$ is chosen so that $\int L(x)Q(x)dx$ is
known in closed form.

Now $m^{L}(0)=0$ and $m^{L}(1)=Z/Z_{0}$ and we have the following identity:

$\frac{Z}{Z_{0}}=\frac{\int_{\mathcal{X}}L(x)P(dx)}{\int_{\mathcal{X}}L(x)Q(dx)}$

Hence a ratio of normalisation constants can be written in terms of a
concentration function.

###  3.3 Nested Sampling

Order states by their $x$-quantiles of the likelihood, $L$, under $\pi$.
Specifically, we assume $z(x)$ has a well defined inverse $x(z)$ where

$z(x)=Z_{L(x)}=\int_{L(x^{\prime})>L(x)}\pi(x^{\prime})dx^{\prime}$

Then under this change of variables, we can approximate the expectation of
interest via simple quadrature

$Z=\int_{0}^{1}L(x(z))dz\approx\sum_{i=1}^{N}L_{i}(x_{i}-x_{i-1})$

One caveat is that the $x(z)$ values near the origin contain all the mass.

The algorithm is as follows: if $L_{\max}=\sup_{x}\;L(x)$ is known, we sample
as follows: set $X=1,N=1,Z=0$

  * •

Generate $x^{(1)}\sim\pi(x)$ and set $L_{0}=0,L_{1}=L(x^{(1)})$.

  * •

If $L_{\max}X<\epsilon Z$, then set $Z=Z+(X/N)\sum_{j=1}^{N}L_{i+j-1}$ and
stop.

  * •

Repeat while $L_{i}X/N>\delta$

  * •

Generate $x^{(i+N)}\sim\pi(x)\mathbb{I}\left(L(x)>L_{i-1}\right)$ and set
$L_{i}=L(x^{(i+N)})$.

  * •

Set $N=N+1$ and sort $L_{i}$’s

  * •

Set $Z=Z+L_{i}X/N$ and $N=N-1,X=(1-1/N)X$.

###  3.4 Split sampling

Split sampling uses importance sampling blankets, indexed by a weight function
$\omega(m)$ which can be adaptively estimated

$g_{\omega}(x)=\frac{\left\\{\int_{0}^{L(x)}\omega_{s}ds\right\\}\pi(x)}{\int_{\mathcal{X}}\Omega(x)\pi(x)dx}\;\;{\rm
where}\;\;\Omega(L(x))=\int_{0}^{L(x)}\omega_{s}ds\;.$

Suppose that $X\sim P(x)$ and $Y\equiv L(X)$. Let
$F_{Y}(y)=\mathbb{P}\\{L(X)\leq y\\}$ be the cumulative distribution function
of $Y$. Now define

$Z(y)=1-F_{Y}(y)=\int_{L(x)>y}dP(x)$ (7)

Clearly $Z(y)$ has domain $y\in\mathbb{R}^{+}$ and range $s\in[0,1]$ and is
non-increasing in $y$.

Fubini interchange “splits” $Z$

$Z=\int_{\mathcal{X}}L(x)\pi(x)dx=\int\int_{L(x)>m}\pi(x)dm=\int Z_{m}dm\;.$

  * •

Weight function $\omega(m)$. Marginal splitting density by

$\pi_{IS}\left(m\right)=\frac{\omega(m)Z_{m}}{\int_{0}^{M}\omega(m)Z_{m}dm}\;.$

Run MC,equilibrium $\pi(x)$ conditioned to the set $\\{x:L(x)>m\\}$ namely

$\pi(x|m)\sim\pi\left(x|L(x)>m\right)\;.$

  * •

Auxiliary variable $m$: conditional doesn’t depend on $Z_{m}$.

$\pi(m|x)=\frac{\omega(m)L_{m}(x)}{\int_{0}^{M}\omega(m)L_{m}(x)dm}\;.$

#### Algorithm:

Draw samples $(x,m)^{(i)}\sim\pi_{IS}\left(x,m\right)$ by iterating
$\pi_{IS}\left(x|m\right)$ and $\pi_{IS}\left(m|x\right)$. Estimate the
marginal distribution $\hat{\pi}_{IS}(m)$ via

$\hat{\pi}_{IS}(m)=\frac{1}{N}\sum_{i=1}^{N}\frac{\omega(m)L_{m}(x^{(i)})}{\int_{0}^{M}\omega(m)L_{m}(x^{(i)})dm}\;.$

The new estimate of the individual normalisation constants, $Z_{m}$, is

$\hat{Z}_{m}=\omega^{-1}(m)\cdot\frac{\hat{\pi}_{IS}(m)}{\hat{\pi}_{IS}(0)}\;.$

Compute a new estimate, $\hat{Z}$, via

$\hat{Z}=\sum_{i=1}^{N}\frac{\Omega^{-1}\left(L(x^{(i)})\right)}{\sum_{i=1}^{N}\Omega^{-1}(L(x^{(i)}))}L(x^{(i)})\;.$

We can use a discrete “cooling” schedule
$\omega(m)=\sum_{t=0}^{T}\omega_{t}\delta_{m_{t}}(m)$.

Set $T=0$, $m_{0}=0$, $\Omega_{0}=1$, and $Z_{0}=1$. While $T<T_{max}$, set
$T=T+1$

  * •

Simulate $\pi_{SS}({\bf{x}})$ with $\\{m_{t}\\}_{0\leq t<T}$ and
$\\{\Omega_{t}\\}_{0\leq t<T}$ until $N_{level}$ visits to level $T-1$.

  * •

Choose the $(1-\rho)$-quantile of likelihoods of level $T-1$ as $m_{T}$.

  * •

Set $\hat{Z}_{T}=\rho^{-T}$.

  * •

Set $\Omega_{T}=\hat{Z}_{T}^{-1}$.

Favor upper levels with condition (d1) Set $\Omega_{T}=e^{\Lambda
T}Z_{T}^{-1}$. $\Lambda$ a boosting factor. Time complexity to be $O(T)$.
Place more weight on the top level $T$ with condition (d2) Set
$\Omega_{T-1}=e^{\Lambda(T-1)}Z_{T-1}^{-1}$ and
$\Omega_{T}=\beta\frac{e^{\Lambda T}-1}{e^{\Lambda}-1}Z_{T}^{-1}$.

#### Discrete Split Sampling

is defined as follows: once we have found all levels, our split sampling
algorithm runs:

  * •

Set $i=0$ and $\nu_{t}=\nu_{init}\hat{Z}_{t}$ for each $t=0,1,\dots,T$. While
$i\leq n$, set $i=i+1$.

    * –

Draws ${\bf{x}}^{(i)}$ using MH under weights $\Omega(m)$, and set
$L_{i}=L({\bf{x}}^{(i)})$.

    * –

Obtain $M^{(i)}=\Omega^{-1}(U_{i})$ where $U_{i}\sim U(0,\Omega(L_{i}))$ with
$\Omega(0)=1$.

    * –

For each $t$ with $m_{t}<L_{i}$, update $\nu_{t}=\nu_{t}+\Omega(L_{i})^{-1}$.

    * –

Update $\hat{Z}_{t}=\nu_{t}/\nu_{0}$ and set $\Omega_{t}=\hat{Z}_{t}^{-1}$.

If $\omega(m)=1$ and marginal, $\mu_{N}(m)\equiv\hat{\pi}_{IS}(m)$ given by

$\mu_{N}(m)=\left\\{\frac{1}{N}\sum_{i=1}^{N}\frac{\mathbb{I}{\\{m<L(x^{(i)})\\}}}{\Omega(L(x^{(i)}))}\right\\}\omega(m)\;.$

Rebalance inversely proportional to visitation probabilities adjusts weights
for $m<\max_{i}L(x^{(i)})$

$\frac{\omega^{\star}(m)}{\omega(m)}=\frac{\omega(m)}{\mu_{N}(m)}=\frac{\mathbb{I}{\\{m<L(x^{(i)})\\}}}{\Omega(L(x^{(i)}))}\;.$

The “flat histogram” (FH) condition is as follows: for a tolerance $c$,

$\max_{m\in\\{m_{t}\\}}\;\vline\;\mu_{N}(m)-\phi(m)\;\vline\;<c\;.$

Update rule guarantees convergence in finite time,

$\log\omega_{\kappa_{N}}(m)\leftarrow\log\omega_{\kappa_{N-1}}(m)+\gamma_{\kappa_{N}}\left(\mu_{\kappa_{N}}(m)-\phi(m)\right)\;.$

##  4 Discussion

The N-Queens completion problem is a conditional counting problem. Gent et al.
[2017] shows that the N-queen completion problem if solved efficiently would
imply that $P=NP$. In our framework, we need to compute

$Z_{O}=E_{X\mid X=X_{0}}[S(x)]=\int_{0}^{1}F^{-1}_{X\mid X=X_{0}}(u)du,$

where the expectation is taken with respect to the conditional distribution of
$X$ given $X=X_{0}$. Here $X_{0}$ is the initial configuration of queens. The
quantile re-ordering approach and the use of polynomial time sampling
algorithms is still available – we simply use the conditional density.

## References

  * Berg and Neuhaus [1991] Bernd A. Berg and Thomas Neuhaus.  Multicanonical algorithms for first order phase transitions.  _Phys. Lett. B_ , 267:249–253, 1991.
  * Birge et al. [2013] John R. Birge, Changgee Chang, and Nicholas G. Polson.  Split Sampling: Expectations, Normalisation and Rare Events.  _arXiv:1212.0534 [stat]_ , October 2013.
  * Bornn et al. [2013] Luke Bornn, Pierre E. Jacob, Pierre Del Moral, and Arnaud Doucet.  An Adaptive Interacting Wang-Landau Algorithm for Automatic Density Exploration.  _Journal of Computational and Graphical Statistics_ , 22(3):749–773, 2013.
  * Damlen et al. [1999] P. Damlen, J. Wakefield, and S. Walker.  Gibbs Sampling for Bayesian Non-Conjugate and Hierarchical Models by Using Auxiliary Variables.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , 61(2):331–344, July 1999.
  * Diaconis and Holmes [1995] Persi Diaconis and Susan Holmes.  Three Examples of Monte-Carlo Markov Chains: At the Interface Between Statistical Computing, Computer Science, and Statistical Mechanics.  In David Aldous, Persi Diaconis, Joel Spencer, and J. Michael Steele, editors, _Discrete Probability and Algorithms_ , The IMA Volumes in Mathematics and Its Applications, pages 43–56, New York, NY, 1995. Springer.  ISBN 978-1-4612-0801-3.
  * Edwards and Sokal [1988] Robert G. Edwards and Alan D. Sokal.  Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm.  _Physical Review D_ , 38(6):2009–2012, September 1988.
  * Fortuin and Kasteleyn [1972] C. M. Fortuin and P. W. Kasteleyn.  On the random-cluster model: I. Introduction and relation to other models.  _Physica_ , 57(4):536–564, February 1972.
  * Gent et al. [2017] Ian P. Gent, Christopher Jefferson, and Peter Nightingale.  Complexity of n-Queens Completion.  _Journal of Artificial Intelligence Research_ , 59:815–848, August 2017.
  * Hesselbo and Stinchcombe [1995] Bobby Hesselbo and R. B. Stinchcombe.  Monte Carlo Simulation and Global Optimization without Parameters.  _Physical Review Letters_ , 74(12):2151–2155, March 1995.
  * Higdon [1998] David M. Higdon.  Auxiliary Variable Methods for Markov Chain Monte Carlo with Applications.  _Journal of the American Statistical Association_ , 93(442):585–595, 1998.
  * Masry and Cambanis [1990] Elias Masry and Stamatis Cambanis.  Trapezoidal Monte Carlo Integration.  _SIAM Journal on Numerical Analysis_ , 27(1):225–246, February 1990.
  * Polson [1996] Nicholas Polson.  Convergence of Markov chain Monte Carlo algorithms (with discussion).  _Bayesian Statistics_ , 5:297–321, 1996.
  * Polson and Scott [2015] Nicholas G. Polson and James G. Scott.  Vertical-likelihood Monte Carlo.  _arXiv:1409.3601 [math, stat]_ , June 2015.
  * Rubinstein and Kroese [2016] Reuven Y. Rubinstein and Dirk P. Kroese.  _Simulation and the Monte Carlo Method_.  John Wiley & Sons, October 2016.  ISBN 978-1-118-63220-8.
  * Rubinstein et al. [2013] Reuven Y Rubinstein, Ad Ridder, and Radislav Vaisman.  _Fast Sequential Monte Carlo Methods for Counting and Optimization_.  John Wiley & Sons, 2013.
  * Simkin [2022] Michael Simkin.  The number of $n$-queens configurations, November 2022.
  * Skilling [2006] John Skilling.  Nested sampling for general Bayesian computation.  _Bayesian Analysis_ , 1(4):833–859, December 2006\.
  * Swendsen and Wang [1987] Robert H. Swendsen and Jian-Sheng Wang.  Nonuniversal critical dynamics in Monte Carlo simulations.  _Physical Review Letters_ , 58(2):86–88, January 1987.
  * Wang and Landau [2001a] F. Wang and D. P. Landau.  Efficient, multiple-range random walk algorithm to calculate the density of states.  _Physical Review Letters_ , 86(10):2050–2053, March 2001a.
  * Wang and Landau [2001b] Fugao Wang and D. P. Landau.  Determining the density of states for classical statistical models: A random walk algorithm to produce a flat histogram.  _Physical Review E_ , 64(5):056101, October 2001b.
  * Yakowitz et al. [1978] S Yakowitz, JE Krimmel, and F Szidarovszky.  Weighted monte carlo integration.  _SIAM Journal on Numerical Analysis_ , 15(6):1289–1300, 1978.