# The minimum degree of
minimal Ramsey graphs for cliques

John Bamberg1 ,  Anurag Bishnoi1 1Centre for the Mathematics of Symmetry and
Computation, The University of Western Australia, Australia.
<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Thomas Lesgourgues2 2School
of Mathematics and Statistics, UNSW, Australia<EMAIL_ADDRESS>
###### Abstract.

We prove that $s_{r}(K_{k})=O(k^{5}r^{5/2})$, where $s_{r}(K_{k})$ is the
Ramsey parameter introduced by Burr, Erdős and Lovász in 1976, which is
defined as the smallest minimum degree of a graph $G$ such that any
$r$-colouring of the edges of $G$ contains a monochromatic $K_{k}$, whereas no
proper subgraph of $G$ has this property. The construction used in our proof
relies on a group theoretic model of generalised quadrangles introduced by
Kantor in 1980.

###### Key words and phrases:

Ramsey graphs, generalised quadrangles, Kantor family

###### 2010 Mathematics Subject Classification:

05C55,05D10,51E12

Anurag Bishnoi’s research supported by a Discovery Early Career Award of the
Australian Research Council (No. DE190100666)

Thomas Lesgourgues’ research supported by an Australian Government Research
Training Program Scholarship and the School of Mathematics and Statistics,
UNSW

##  1\. Introduction

A graph $G$ is called $r$-Ramsey for another graph $H$, denoted by
$G\rightarrow(H)_{r}$, if every $r$-colouring of the edges of $G$ contains a
monochromatic copy of $H$. Observe that if $G\rightarrow(H)_{r}$, then every
graph containing $G$ as a subgraph is also $r$-Ramsey for $H$. Some very
interesting questions arise when we study graphs $G$ which are minimal with
respect to $G\rightarrow(H)_{r}$, that is, $G\rightarrow(H)_{r}$ but there is
no proper subgraph $G^{\prime}$ of $G$ such that
$G^{\prime}\rightarrow(H)_{r}$. We call such graphs $r$-Ramsey minimal for $H$
and we denote the set of all $r$-Ramsey minimal graphs for $H$ by
$\mathcal{M}_{r}(H)$. The classical result of Ramsey [22] implies that for any
finite graph $H$ and positive integer $r$, there exists a graph $G$ that is
$r$-Ramsey for $H$, that is, $\mathcal{M}_{r}(H)$ is non-empty.

Some of the central problems in graph Ramsey theory are concerned with the
case where $H$ is a clique $K_{k}$. For example, the most well studied
parameter is the Ramsey number $R_{r}(k)$, that denotes the smallest number of
vertices of any graph in $\mathcal{M}_{r}(K_{k})$. The classical work of Erdős
[9] and Erdős and Szekeres [10] shows that $2^{k/2}\leqslant R_{2}(k)\leqslant
2^{2k}$. While these bounds have been improved since then, most recently by
Sah [24] (also see [25] and [5]), the constants in the exponent have stayed
the same. We refer the reader to the survey of Conlon, Fox and Sudakov [6] for
more on this and other graph Ramsey problems.

Several other questions on $\mathcal{M}_{r}(H)$ have also been explored; for
example, the well studied size-Ramsey number $\hat{R}_{r}(H)$ which is the
minimum number of edges of a graph in $\mathcal{M}_{r}(H)$. We refer the
reader to [1, 3, 19, 23] for various results on minimal Ramsey problems. In
this paper, we will be interested in the smallest minimum degree of an
$r$-Ramsey minimal graph, which is defined by

$s_{r}(H)\coloneqq\min_{G\in\mathcal{M}_{r}(H)}\delta(G),$

for a finite graph $H$ and positive integer $r$, where $\delta(G)$ denotes the
minimum degree of $G$. Trivially, we have $s_{r}(H)\leqslant R_{r}(H)-1$,
since the complete graph on $R_{r}(H)$ vertices is $r$-Ramsey for $H$ and has
minimum degree $R_{r}(H)-1$. The study of this parameter was initiated by
Burr, Erdős and Lovász [2] in 1976. They were able to show the rather
surprising exact result, $s_{2}(K_{k})=(k-1)^{2}$, which is far away from the
trivial exponential bound of $s_{2}(K_{k})\leqslant R_{r}(k)-1$. The behaviour
of this function is still not so well understood for $r>2$ colours. Fox et al.
[11] determined this function asymptotically for every fixed $k$ up-to a
polylogarithmic factor, and for $k=3$ their result was further improved by Guo
and Warnke [13] who managed to obtain matching logarithmic factors.

######  Theorem 1.1 (Fox, Grinshpun, Liebenau, Person, Szabó).

  1. (i)

There exist constants $c,C>0$ such that for all $r\geqslant 2$, we have

$cr^{2}\ln r\leqslant s_{r}(K_{3})\leqslant Cr^{2}\ln^{2}r.$

  2. (ii)

For all $k\geqslant 4$ there exist constants $c_{k},C_{k}>0$ such that for all
$r\geqslant 3$, we have

$c_{k}r^{2}\frac{\ln r}{\ln{\ln r}}\leqslant s_{r}(K_{k})\leqslant
C_{k}r^{2}(\ln r)^{8(k-1)^{2}}.$

######  Theorem 1.2 (Guo, Warnke).

$s_{r}(K_{3})=\Theta(r^{2}\ln r)$.

The constant in the upper bound of Theorem 1.1(ii) is rather large ($C_{k}\sim
k^{2}e^{4k^{2}\ln 2}$), and in particular not polynomial in $k$. To remedy
this, they proved the following general upper bound which is polynomial in
both $k$ and $r$.

######  Theorem 1.3 (Fox, Grinshpun, Liebenau, Person, Szabó).

For all $k,r\geqslant 3$, $s_{r}(K_{k})\leqslant 8(k-1)^{6}r^{3}$.

For a fixed $r$ and $k\rightarrow\infty$, Hàn, Rödl and Szabó [14] determined
this function up-to polylogarithmic factors by proving the following.

######  Theorem 1.4 (Hàn, Rödl, Szabó).

There exists a constant $k_{0}$ such that for every $k>k_{0}$ and $r<k^{2}$

$s_{r}(K_{k})\leqslant 80^{3}(r\ln r)^{3}(k\ln k)^{2}.$

We prove the following general upper bound that improves Theorem 1.3, and thus
provides the best known upper bound on $s_{r}(K_{k})$ outside the special
ranges covered by Theorem 1.1 and 1.4.

######  Theorem 1.5.

There exists an absolute constant $C$ such that for all $r\geqslant
2,k\geqslant 3$, $s_{r}(K_{k})\leqslant C(k-1)^{5}r^{5/2}$.

Our proof uses the equivalence between $s_{r}(K_{k})$ and another extremal
function, called the $r$-colour $k$-clique packing number [11], defined as
follows. Let $P_{r}(k)$ denote the minimum $n$ for which there exist
$K_{k+1}$-free pairwise edge disjoint graphs $G_{1},\dots,G_{r}$ on a common
vertex set $V$ of size $n$ such that for any $r$-colouring of $V$, there
exists an $i$ such that $G_{i}$ contains a $K_{k}$ all of whose vertices are
coloured in the $i$th colour.

######  Lemma 1.6 (see [11, Theorem 1.5]).

For all integers $r,k\geqslant 2$ we have $s_{r}(K_{k+1})=P_{r}(k)$.

Our graphs $G_{i}$ in the packing would come from certain point-line
geometries known as generalised quadrangles that we define in the next
section. In Section 3, we show that any packing of ‘triangle-free’ point-line
geometries implies an upper bound on $P_{r}(k)$, assuming certain conditions
on the parameters of the geometry. In Section, 4 we give a packing of certain
subgeometries of the so-called Hermitian generalised quadrangles using a group
theoretic model given by Kantor in the 1980’s [16], and deduce that this
packing implies our main result.

##  2\. Background

A (finite) generalised quadrangle $\mathcal{Q}$ of order $(s,t)$ is an
incidence structure of points $\mathcal{P}$, lines $\mathcal{L}$, together
with a symmetric point-line incidence relation satisfying the following
axioms:

  1. (i)

Each point lies on $t+1$ lines ($t\geqslant 1$) and two distinct points are
incident with at most one line.

  2. (ii)

Each line lies on $s+1$ points ($s\geqslant 1$) and two distinct lines are
incident with at most one point.

  3. (iii)

If $P$ is a point and $\ell$ is a line not incident with $P$, then there is a
unique point on $\ell$ collinear with $P$.

Notice that the third axiom above ensures that there are no triangles (i.e.,
three distinct lines pairwise meeting in three distinct points) in
$\mathcal{Q}$. The standard reference on finite generalised quadrangles is the
book by Payne and Thas [21]. The collinearity graph of a generalised
quadrangle is the graph on the set of points with two points adjacent when
they are both incident with a common line. A collineation $\theta$ of
$\mathcal{Q}$, that is, an automorphism of its collinearity graph, is an
elation about the point $P$ if it is either the identity collineation, or it
fixes each line incident with $P$ and fixes no point not collinear with $P$.
If there is a group $E$ of elations of $\mathcal{Q}$ about the point $P$ such
that $E$ acts regularly on the points not collinear with $P$, then we say that
$\mathcal{Q}$ is an elation generalised quadrangle with elation group $E$ and
base point $P$. Necessarily, $E$ has order $s^{2}t$, as there are $s^{2}t$
points not collinear to a given point in any generalised quadrangle.

Now suppose we have a finite group $E$ of order $s^{2}t$ where $s,t>1$. A
_Kantor family_ of $E$ is a set $\mathcal{A}:=\\{A_{i}\colon i=0,\ldots,t\\}$
of subgroups of order $s$, and a set $\mathcal{A}^{*}:=\\{A_{i}^{*}\colon
i=0,\ldots,t\\}$ of subgroups of order $st$, such that the following are
satisfied:

  1. (K0)

$A_{i}\leqslant A_{i}^{*}$ for all $i\in\\{0,\ldots,t\\}$;

  2. (K1)

$A_{i}\cap A_{j}^{*}=\\{1\\}$ whenever $i\neq j$;

  3. (K2)

$A_{i}A_{j}\cap A_{k}=\\{1\\}$ whenever $i,j,k$ are distinct.

Due to a theorem of Kantor (c.f., [16, Theorem A.3.1]), a Kantor family as
described above, gives rise to an _elation_ generalised quadrangle of order
$(s,t)$, which we briefly describe in Table 1.

Points | Lines
---|---
elements $g$ of $E$ | the right cosets $A_{i}g$
right cosets $A_{i}^{*}g$ | symbols $[A_{i}]$
a symbol $\infty$. |

Incidence: $g$ $\sim$ $A_{i}g$ $A_{i}^{*}h$ $\sim$ $A_{i}g$, where
$A_{i}g\subseteq A_{i}^{*}h$ $A_{i}^{*}h$ $\sim$ $[A_{i}]$ $\infty$ $\sim$
$[A_{i}]$

Table 1. The points and lines of the elation generalised quadrangle arising
from a Kantor family (n.b., $A_{i}\in\mathcal{A}$,
$A_{i}^{*}\in\mathcal{A}^{*}$, $g\in E$).

We will simply be needing to use the Kantor family for a well-known family of
generalised quadrangles, where the Heisenberg groups appear as the group $E$
in the description above. We remark that the main property we will need is
(K2), since it ensures that lines of the form $A_{i}g$, never form a triangle.

##  3\. Packing Generalised Quadrangles

A partial linear space is a point-line incidence structure with the property
that any two distinct points are incident to at most one common line. A
triangle-free partial linear space of order $(s,t)$ is an incidence structure
satisfying Axioms (i) and (ii) of a generalised quadrangle, and (iii)′ there
are no three distinct lines pairwise meeting each other in three distinct
points. Clearly, any subgeometry of a generalised quadrangle where the number
of points on a line and the number of lines through a point are constants is a
triangle-free partial linear space. We now prove the main lemma that will
imply Theorem 1.5 once we have the construction outlined in Section 4. Our
proof follows the same idea as in Dudek and Rödl [8], and Fox et al. [11].

######  Lemma 3.1.

Let $r,k,s,t$ be positive integers. Say there exists a family
$(\mathcal{I}_{i})_{i=1}^{r}$ of triangle-free partial linear spaces of order
$(s,t)$, on the same point set $\mathcal{P}$ and pairwise disjoint line-sets
$\mathcal{L}_{1},\dots,\mathcal{L}_{r}$, such that the point-line geometry
$\left(\mathcal{P},\bigcup_{i=1}^{r}\mathcal{L}_{i}\right)$ is also a partial
linear space. If $s\geqslant 2rk\ln k$ and $t\geqslant 2k(1+\ln r)$, then
$P_{r}(k)\leqslant\lvert\mathcal{P}\rvert$.

###### Proof.

In order to show that $P_{r}(k)\leqslant\lvert\mathcal{P}\rvert$, we will
exhibit $K_{k+1}$-free pairwise edge disjoint graphs $G_{1},\dots,G_{r}$ on
the common vertex set $V=\mathcal{P}$, such that for any $r$-colouring of $V$,
there exists an $i$ such that $G_{i}$ contains a $K_{k}$ all of whose vertices
are coloured in the $i$th colour. We start by recalling the following
properties about each partial linear space $\mathcal{I}_{i}$,
$i\in\\{1,\ldots,r\\}$:

  1. (P1)

Every point $p\in\mathcal{P}$ is incident with $t+1$ lines of
$\mathcal{L}_{i}$.

  2. (P2)

Every line $\ell\in\mathcal{L}_{i}$ contains $s+1$ points from $\mathcal{P}$.

  3. (P3)

Any two points of $\mathcal{P}$ lie on at most one line of $\mathcal{L}_{i}$.

  4. (P4)

$\mathcal{I}_{i}$ is triangle-free.

Furthermore, given that
$\left(\mathcal{P},\bigcup_{i=1}^{r}\mathcal{L}_{i}\right)$ is a partial
linear space and the line-sets $\mathcal{L}_{1},\dots,\mathcal{L}_{r}$ are
disjoint,

  1. (P5)

For any $i\neq j$, and any $\ell\in\mathcal{L}_{i}$, $m\in\mathcal{L}_{j}$,
$\ell$ and $m$ are incident with at most one common point.

Let $i\in\\{1,\ldots,r\\}$, $\ell_{1}=\left\lfloor\frac{s+1}{k}\right\rfloor$
and $\ell_{2}=\left\lceil\frac{s+1}{k}\right\rceil$. For each line
$\ell\in\mathcal{L}_{i}$, we select uniformly at random one partition of
$\ell$ among all $\ell=\bigcup_{j=1}^{k}L_{j}^{(\ell)}$, where
$L_{j}^{(\ell)}$ denotes the $j$th component of the partition, such that for
some $k^{\prime}$, $\lvert L_{1}^{(\ell)}\rvert,\ldots,\lvert
L_{k^{\prime}}^{(\ell)}\rvert=\ell_{1}$ and $\lvert
L_{k^{\prime}+1}^{(\ell)}\rvert,\ldots,\lvert L_{k}^{(\ell)}\rvert=\ell_{2}$.
Choices for distinct lines in $\mathcal{L}_{i}$ are independent.

We define a graph $G_{i}=(V,E_{i})$ on the vertex set $V=\mathcal{P}$ as
follows. For every $\ell\in\mathcal{L}_{i}$, we include the edges of a
complete $k$-partite graph between the vertex sets $L_{j}^{(\ell)}$ for
$j\in\\{1,\ldots,k\\}$. Note that the graph $G_{i}$ is a collection of Turán
graphs on $(s+1)$ vertices with $k$ parts. Each Turán graph comes from one
line $\ell\in\mathcal{L}_{i}$. By property (P3), any two points are incident
with at most one line, therefore the different Turán graphs are edge-disjoint.
Furthermore, by property (P4), $G_{i}$ is $K_{k+1}$-free. Finally, by property
(P5), for any $i\neq j\in\\{1,\ldots,r\\}$, $G_{i}$ and $G_{j}$ are edge
disjoint.

In order to conclude, we need to show that with positive probability, for any
$r$-colouring of $V$, there exists an $i$ such that $G_{i}$ contains a $K_{k}$
all of whose vertices are coloured in the $i$th colour. Note that given
$G_{1},\ldots,G_{r}$ on the vertex set $V=\mathcal{P}$, in any $r$-colouring
of $V$, at least one of the colours occurs at least
$\lvert\mathcal{P}\rvert/r$ times. Therefore if for every $G_{i}$, every set
of at least $\lvert\mathcal{P}\rvert/r$ vertices contains a $K_{k}$, then we
get the desired property. The choices of partitions being done independently,
to conclude our proof it suffices to show that for each
$i\in\\{1,\ldots,r\\}$, with positive probability every set of at least
$\lvert\mathcal{P}\rvert/r$ vertices contains a $K_{k}$ in $G_{i}$.

Fix $i\in\\{1,\ldots,r\\}$. For a subset $W\subseteq\mathcal{P}$, let
$\mathcal{A}(W)$ denotes the event that the induced subgraph $G_{i}[W]$
contains no $K_{k}$. Let $U\subset\mathcal{P}$ with $\lvert
U\rvert=\left\lfloor\frac{\lvert\mathcal{P}\rvert}{r}\right\rfloor$. By
property (P4), any $K_{k}$ can only appear from one line
$\ell\in\mathcal{L}_{i}$, i.e.

$\mathcal{A}(U)\subseteq\bigcap_{\ell\in\mathcal{L}_{i}}\mathcal{A}(U\cap\ell).$

All the events $\mathcal{A}(U\cap\ell)$ are independent, therefore

$\mathbb{P}(\mathcal{A}(U))\leqslant\prod_{\ell\in\mathcal{L}_{i}}\mathbb{P}(\mathcal{A}(U\cap\ell)).$

For a given line $\ell\in\mathcal{L}_{i}$, let $u_{\ell}=\lvert
U\cap\ell\rvert$, and let $\ell=\bigcup_{j=1}^{k}L_{j}^{(\ell)}$ be the random
partition of $\ell$. Note that $U\cap\ell$ contains no $K_{k}$ if and only if
there exists $j\in\\{1,\ldots,k\\}$ such that $U\cap
L_{j}^{(\ell)}=\varnothing$. For a fixed $j\in\\{1,\ldots,k\\}$,

$\mathbb{P}\left(U\cap
L_{j}^{(\ell)}=\varnothing\right)=\frac{\binom{s+1-u_{\ell}}{|L_{j}^{(\ell)}|}}{\binom{s+1}{|L_{j}^{(\ell)}|}}\leqslant\left(1-\frac{u_{\ell}}{s+1}\right)^{|L_{j}^{(\ell)}|}\leqslant\exp\left(-\frac{\ell_{1}u_{\ell}}{s+1}\right).$

Therefore

$\displaystyle\mathbb{P}(\mathcal{A}(U))$
$\displaystyle\leqslant\prod_{\ell\in\mathcal{L}_{i}}\mathbb{P}\left(\exists\
j\in\\{1,\ldots,k\\},\ U\cap L_{j}^{(\ell)}=\varnothing\right)$
$\displaystyle\leqslant
k^{\lvert\mathcal{L}_{i}\rvert}\exp\left(-\sum_{\ell\in\mathcal{L}_{i}}\frac{\ell_{1}u_{\ell}}{s+1}\right).$

Because every point of $U$ is incident with $t+1$ lines from $\mathcal{L}_{i}$
(by property (P1)),
$\sum_{\ell\in\mathcal{L}_{i}}u_{\ell}=\sum_{\ell\in\mathcal{L}_{i}}\lvert
U\cap\ell\rvert=(t+1)\lvert U\rvert$, and thus

$\mathbb{P}(\mathcal{A}(U))\leqslant
k^{\lvert\mathcal{L}_{i}\rvert}\exp\left(-\frac{\ell_{1}(t+1)\lvert
U\rvert}{s+1}\right).$

Finally,

$\displaystyle\mathbb{P}\left(\exists
U\in\binom{\mathcal{P}}{\left\lfloor\frac{\lvert\mathcal{P}\rvert}{r}\right\rfloor}:\
\mathcal{A}(U)\right)$
$\displaystyle\leqslant\binom{\lvert\mathcal{P}\rvert}{\left\lfloor\frac{\lvert\mathcal{P}\rvert}{r}\right\rfloor}k^{\lvert\mathcal{L}_{i}\rvert}\exp\left(-\frac{t+1}{s+1}\ell_{1}\left\lfloor\frac{\lvert\mathcal{P}\rvert}{r}\right\rfloor\right)$
$\displaystyle\leqslant(re)^{\lvert\mathcal{P}\rvert/r}k^{\lvert\mathcal{L}_{i}\rvert}\exp\left(-\frac{t+1}{s+1}\frac{s+1}{k}\left\lfloor\frac{\lvert\mathcal{P}\rvert}{r}\right\rfloor\right)$
$\displaystyle\leqslant\exp\left[\lvert\mathcal{P}\rvert\left(\frac{1+\ln
r}{r}+\frac{\lvert\mathcal{L}_{i}\rvert}{\lvert\mathcal{P}\rvert}\ln{k}-\frac{t+1}{rk}\right)\right].$

By double counting (using properties (P1) and (P2)) we know that

$\lvert\mathcal{L}_{i}\rvert(s+1)=\lvert\mathcal{P}\rvert(t+1),$

and therefore

$\mathbb{P}\left(\exists
U\in\binom{\mathcal{P}}{\left\lfloor\frac{\lvert\mathcal{P}\rvert}{r}\right\rfloor}:\
\mathcal{A}(U)\right)\leqslant\exp\left[\lvert\mathcal{P}\rvert\left(\frac{1+\ln
r}{r}+\frac{t+1}{s+1}\ln k-\frac{t+1}{rk}\right)\right]$ (3.1)

Note that since $s\geqslant 2rk\ln k$ we have

$\frac{t+1}{rk}>\frac{2(t+1)}{s+1}\ln k,$

and since $t\geqslant 2k(1+\ln r)$ we have

$\frac{t+1}{rk}>\frac{2(1+\ln r)}{r}.$

Therefore,

$\mathbb{P}\left(\exists
U\in\binom{\mathcal{P}}{\left\lfloor\frac{\lvert\mathcal{P}\rvert}{r}\right\rfloor}:\
\mathcal{A}(U)\right)<1.$

Then there exists an instance of $G_{i}$ such that every subset of
$\mathcal{P}$ with at least
$\left\lfloor\frac{\lvert\mathcal{P}\rvert}{r}\right\rfloor$ vertices contains
a $K_{k}$ in $G_{i}$. ∎

##  4\. The construction

Let $q$ be a prime power, and denote the finite field of order $q^{2}$ by
$\mathbb{F}_{q^{2}}$. We will use the model of the Hermitian generalised
quadrangle $H(3,q^{2})$ that appears in [15, Section 3] (see Example 3). For a
definition of $H(3,q^{2})$ see [21, Chapter 3].

Let $E$ be the group defined on
$\mathbb{F}_{q^{2}}\times\mathbb{F}_{q}\times\mathbb{F}_{q^{2}}$ by the
following operation:

$(a,\gamma,b)\circ(a^{\prime},\gamma^{\prime},b^{\prime})=(a+a^{\prime},\gamma+\gamma^{\prime}+\operatorname{\mathsf{Tr}}(b^{q}a^{\prime}),b+b^{\prime}),$

where $\operatorname{\mathsf{Tr}}(x)=x+x^{q}$ is the relative trace map from
$\mathbb{F}_{q^{2}}$ to $\mathbb{F}_{q}$. It turns out that $E$ is the
_Heisenberg group_ of order $q^{5}$ with centre of order $q$. Recall that the
centre, derived subgroup, and Frattini subgroup of $E$ coincide; that is, $E$
is a special group. Indeed, the centre $Z$ of $E$ consists of the elements of
the form $(0,\gamma,0)$ with $\gamma\in\mathbb{F}_{q}$.

We can construct a generalised quadrangle by constructing a Kantor family of
$E$. Define

$\displaystyle A^{*}_{\infty}$ $\displaystyle=\\{(0,\gamma,a)\colon
a,\gamma\in\mathbb{F}_{q^{2}}\\},$ $\displaystyle A^{*}_{t}$
$\displaystyle=\\{(a,\gamma,at)\colon a,\gamma\in\mathbb{F}_{q^{2}}\\},\quad
t\in\mathbb{F}_{q},$ $\displaystyle A_{\infty}$
$\displaystyle=\\{(0,0,a)\colon\alpha\in\mathbb{F}_{q^{2}}\\},$ $\displaystyle
A_{t}$ $\displaystyle=\\{(a,a^{q+1}t,at)\colon a\in\mathbb{F}_{q^{2}}\\},\quad
t\in\mathbb{F}_{q}.$

Then $\mathcal{A}:=\\{A_{\infty}\\}\cup\\{A_{t}\colon t\in\mathbb{F}_{q}\\}$
and $\mathcal{A}^{*}:=\\{A^{*}_{\infty}\\}\cup\\{A^{*}_{b}\colon
b\in\mathbb{F}_{q}\\}$ form a Kantor family of $E$ giving rise to a
generalised quadrangle isomorphic to $H(3,q^{2})$.111In [15] the dual of this
generalised quadrangle is defined, denoted by $O^{-}(6,q)$, but it is well
known that $H(3,q^{2})$ is isomorphic to the dual of the elliptic generalised
quadrangle $O^{-}(6,q)$ (see [21, Chapter 3], where $O^{-}(6,q)$ is denoted by
$Q(5,q)$).

From now on we will assume that $q$ is odd. Let $\kappa$ be an element of
$\mathbb{F}_{q^{2}}$. For each $\lambda\in\mathbb{F}_{q^{2}}$, define
$\tau_{\lambda}:E\rightarrow E$ as follows. Let

$\displaystyle\tau_{\lambda}\colon$
$\displaystyle(a,0,0)\mapsto\left(a,\operatorname{\mathsf{Tr}}(\lambda
a+\kappa\lambda a^{q}+\tfrac{1}{2}\lambda^{q}a^{2}),\lambda a^{q}\right),$
$\displaystyle\tau_{\lambda}\colon$
$\displaystyle(0,\gamma,b)\mapsto(0,\gamma,b).$

Since $E=A_{0}A_{\infty}^{*}$ (by Axiom (K1)), we can write every element
$g\in E$ as $g=g_{0}g_{\infty}^{*}$, with $g_{0}\in A_{0}$ and
$g_{\infty}^{*}\in A_{\infty}^{*}$. Define
$\tau_{\lambda}(g)\coloneqq\tau_{\lambda}(g_{0})\circ\tau_{\lambda}(g_{\infty}^{*})$.

######  Lemma 4.1.

For every $\lambda\in\mathbb{F}_{q^{2}}$, $\tau_{\lambda}$ is an automorphism
of $E$.

###### Proof.

Let $\lambda\in\mathbb{F}_{q^{2}}$. It suffices to show that $\tau_{\lambda}$
is a homomorphism from $A_{0}$ to $E$, since $\tau_{\lambda}$ is clearly
bijective. Let $a_{1},a_{2}\in\mathbb{F}_{q^{2}}$. Then

$\displaystyle(a_{1}+a_{2},0,0)^{\tau_{\lambda}}=$
$\displaystyle\left(a_{1}+a_{2},\operatorname{\mathsf{Tr}}(\lambda(a_{1}+a_{2})+\kappa\lambda(a_{1}+a_{2})^{q}+\tfrac{1}{2}\lambda^{q}(a_{1}+a_{2})^{2}),\lambda(a_{1}+a_{2})^{q}\right)$
$\displaystyle=$
$\displaystyle\big{(}a_{1}+a_{2},\operatorname{\mathsf{Tr}}(\lambda
a_{1}+\kappa\lambda a_{1}^{q}+\tfrac{1}{2}\lambda^{q}a_{1}^{2})+$
$\displaystyle\operatorname{\mathsf{Tr}}(\lambda a_{2}+\kappa\lambda
a_{2}^{q}+\tfrac{1}{2}\lambda^{q}a_{2}^{2})+\operatorname{\mathsf{Tr}}(\lambda^{q}a_{1}a_{2}),\lambda
a_{1}^{q}+\lambda a_{2}^{q}\big{)}$ $\displaystyle=$
$\displaystyle\left(a_{1},\operatorname{\mathsf{Tr}}(\lambda
a_{1}+\kappa\lambda a_{1}^{q}+\tfrac{1}{2}\lambda^{q}a_{1}^{2}),\lambda
a_{1}^{q}\right)\circ\left(a_{2},\operatorname{\mathsf{Tr}}(\lambda
a_{2}+\kappa\lambda a_{2}^{q}+\tfrac{1}{2}\lambda^{q}a_{2}^{2}),\lambda
a_{2}^{q}\right)$ $\displaystyle=$
$\displaystyle(a_{1},0,0)^{\tau_{\lambda}}\circ(a_{2},0,0)^{\tau_{\lambda}}.$

Therefore, $\tau_{\lambda}$ is an automorphism of $E$. ∎

######  Lemma 4.2.

For every odd prime power $q$, there exists $\kappa\in\mathbb{F}_{q^{2}}$ such
that $\operatorname{\mathsf{Tr}}(\kappa a+a^{2q-1})\neq 0$ for all nonzero
$a\in\mathbb{F}_{q^{2}}$.

###### Proof.

Suppose that $\operatorname{\mathsf{Tr}}(\kappa a+a^{2q-1})=\kappa
a+\kappa^{q}a^{q}+a^{2q-1}+a^{2-q}=0$ for some non-zero
$a\in\mathbb{F}_{q^{2}}$. Multiplying by $a^{q-2}$ and defining $y=-a^{q-1}$
we get the following cubic equation,

$y^{3}-\kappa^{q}y^{2}+\kappa y-1=0.$

Therefore if $\kappa$ is such that the cubic is irreducible, then we get a
contradiction. We show that such a choice of $\kappa$ exists. Let $t$ be a
non-square in $\mathbb{F}_{q}$ and suppose that $\alpha$ is an element of
$\mathbb{F}_{q^{2}}$ such that $\alpha^{2}=t$. By the Hansen-Mullen
Irreducibility Conjecture (which is true, see [4, Theorem 2.7]) there exists
an irreducible monic cubic of the form $x^{3}+ux^{2}-tx+v$. Let

$\kappa=\frac{-tu+3v}{tu+v}-\frac{4t}{tu+v}\alpha=\left(\frac{-tu+3v}{tu+v}+\frac{4t}{tu+v}\alpha\right)^{q}.$

By [17, Theorem 3], $y^{3}-\kappa^{q}y^{2}+\kappa y-1$ is irreducible in
$\mathbb{F}_{q^{2}}[y]$. ∎

######  Theorem 4.3.

Let $\kappa$ be an element of $\mathbb{F}_{q^{2}}$ such that
$\operatorname{\mathsf{Tr}}(\kappa a+a^{2q-1})\neq 0$ for all non-zero
$a\in\mathbb{F}_{q^{2}}$. For each $\lambda\in\mathbb{F}_{q^{2}}$ and
$t\in\mathbb{F}_{q}$, let

$A_{t}^{\lambda}=\\{(a,a^{q+1}t+\operatorname{\mathsf{Tr}}(\lambda
a+\kappa\lambda a^{q}+\tfrac{1}{2}\lambda^{q}a^{2}),at+\lambda
a^{q}):a\in\mathbb{F}_{q^{2}}\\},$

and let

$\mathcal{S}:=\\{\\{A_{t}^{\lambda}\colon
t\in\mathbb{F}_{q}\\}\colon\lambda\in\mathbb{F}_{q^{2}}\\}.$

Then:

  1. (i)

Every element of $\mathcal{S}$ is a subgroup and any two cosets from different
elements of $\mathcal{S}$ intersect each other in at most one element.

  2. (ii)

If we let $\mathcal{P}$ be the underlying set of $E$, then for every
$\lambda\in\mathbb{F}_{q^{2}}$ the set of lines
$\mathcal{L}_{\lambda}=\\{A_{t}^{\lambda}g:g\in E,t\in\mathbb{F}_{q}\\}$ gives
rise to triangle-free partial linear space
$(\mathcal{P},\mathcal{L}_{\lambda})$ of order $(q^{2}-1,q-1)$.

###### Proof.

First, for each $\lambda\in\mathbb{F}_{q^{2}}$ and $t\in\mathbb{F}_{q}$, we
have

$A_{t}^{\lambda}=A_{t}^{\tau_{\lambda}}.$

So each $A_{t}^{\lambda}$ is a subgroup of $E$, and moreover, each
$\mathcal{A}^{\lambda}:=\\{A_{t}^{\lambda}\colon t\in\mathbb{F}_{q}\\}$, along
with $A_{\infty}$ is a set of subgroups satisfying Axiom (K2). Now we prove
each component of the result.

  1. (i)

First we show that $A_{t_{1}}^{\lambda_{1}}\cap
A_{t_{2}}^{\lambda_{2}}=\\{(0,0,0)\\}$ whenever $\lambda_{1}\neq\lambda_{2}$.
An element of $A_{t_{1}}^{\lambda_{1}}\cap A_{t_{2}}^{\lambda_{2}}$ is of the
form
$(a,a^{q+1}t_{1}+\operatorname{\mathsf{Tr}}(\lambda_{1}a+\kappa\lambda_{1}a^{q}+\tfrac{1}{2}\lambda_{1}^{q}a^{2}),at_{1}+\lambda_{1}a^{q})$
for some $a\in\mathbb{F}_{q^{2}}$, but it is also
$(b,b^{q+1}t_{2}+\operatorname{\mathsf{Tr}}(\lambda_{2}b+\kappa\lambda_{2}b^{q}+\tfrac{1}{2}\lambda_{2}^{q}b^{2}),bt_{2}+\lambda_{2}b^{q})$
for some $b\in\mathbb{F}_{q^{2}}$. Therefore, $a=b$ and hence

$\displaystyle a^{q+1}(t_{1}-t_{2})$
$\displaystyle=\operatorname{\mathsf{Tr}}\left((\lambda_{2}-\lambda_{1})(a+\kappa
a^{q}+\tfrac{1}{2}a^{2q})\right)$ $\displaystyle a(t_{1}-t_{2})$
$\displaystyle=(\lambda_{2}-\lambda_{1})a^{q}.$

Now $a^{q+1}(t_{1}-t_{2})=a^{q}a(t_{1}-t_{2})$ and so

$\displaystyle\operatorname{\mathsf{Tr}}\left((\lambda_{2}-\lambda_{1})(a+\kappa
a^{q}+\tfrac{1}{2}a^{2q})\right)$
$\displaystyle=a^{2q}(\lambda_{2}-\lambda_{1}).$

Expanding this equation gives us

$(\lambda_{2}-\lambda_{1})(a+\kappa
a^{q}-\tfrac{1}{2}a^{2q})+(\lambda_{2}-\lambda_{1})^{q}(a+\kappa
a^{q}+\tfrac{1}{2}a^{2q})^{q}=0.$

Suppose, by way of contradiction, that $a\neq 0$. Since
$\lambda_{2}\neq\lambda_{1}$, we can rewrite the equation as

$(\lambda_{2}-\lambda_{1})^{q-1}=-\frac{a+\kappa
a^{q}-\tfrac{1}{2}a^{2q}}{(a+\kappa a^{q}+\tfrac{1}{2}a^{2q})^{q}}.$

Let $\mathsf{N}\colon\mathbb{F}_{q^{2}}\rightarrow\mathbb{F}_{q}$ be the
relative norm function, defined by $\mathsf{N}(x)=x^{q+1}$. The left-hand side
has norm 1 and hence

$\mathsf{N}(-(a^{q}+\kappa^{q}a-\tfrac{1}{2}a^{2}))=\mathsf{N}(a^{q}+\kappa^{q}a+\tfrac{1}{2}a^{2}).$

Now $\mathsf{N}(-1)=1$ and we can factor out $\mathsf{N}(a)$, so

$\mathsf{N}(a^{q-1}+\kappa^{q}+\tfrac{1}{2}a)-\mathsf{N}(a^{q-1}+\kappa^{q}-\tfrac{1}{2}a)=0.$

Therefore,

$\displaystyle 0=$
$\displaystyle\left(\mathsf{N}(a^{q-1})+\mathsf{N}(\kappa^{q})+\mathsf{N}(\tfrac{1}{2}a)+\operatorname{\mathsf{Tr}}(a^{q-1}\kappa+\tfrac{1}{2}a^{2q-1}+\tfrac{1}{2}\kappa
a)\right)$
$\displaystyle-\left(\mathsf{N}(a^{q-1})+\mathsf{N}(\kappa^{q})+\mathsf{N}(\tfrac{1}{2}a)+\operatorname{\mathsf{Tr}}(a^{q-1}\kappa-\tfrac{1}{2}a^{2q-1}-\tfrac{1}{2}\kappa
a)\right)$ $\displaystyle=$ $\displaystyle\operatorname{\mathsf{Tr}}(\kappa
a+a^{2q-1}),$

a contradiction. So $a=0$ and $A_{t_{1}}^{\lambda_{1}}\cap
A_{t_{2}}^{\lambda_{2}}=\\{(0,0,0)\\}$.

Now for any two subgroups $H,K$ of a group, the intersection of two cosets of
$H$ and $K$ is either empty, or a coset of $H\cap K$, which proves our claim.

  2. (ii)

Finally, as was remarked at the beginning of Section 3, each point-line
geometry arising from the line-sets given by $\mathcal{S}$ is a subgeometry of
a generalised quadrangle, and hence it is triangle-free partial linear space.
For self-containment, we give here a proof that they are triangle-free, using
Kantor’s axioms. Suppose $f,g,h$ are three elements of $E$ forming the
vertices of a triangle. Then there are three elements $A,B,C\in\mathcal{A}$
such that $Af=Ag$, $Bg=Bh$, $Ch=Cf$. Therefore, $fg^{-1}\in A$, $gh^{-1}\in
B$, $fh^{-1}\in C$, from which it follows that $fh^{-1}=(fg^{-1})(gh^{-1})\in
AB\cap C$. Since $f\neq h$, we have $AB\cap C\neq\\{1\\}$. So the condition
$AB\cap C=\\{1\\}$ given by (K2) ensures that there are no triangles.∎

######  Corollary 4.4.

There exists an absolute constant $C$ such that for all $r\geqslant
2,k\geqslant 3$, we have $s_{r}(K_{k})\leqslant C(k-1)^{5}r^{5/2}$.

###### Proof.

Let $r\geqslant 2$, $k\geqslant 3$, $c=\frac{7+6\ln{2}}{3\sqrt{2}}\approx
2.64$ and let $q$ be the smallest prime power such that $q\geqslant
ck\sqrt{r}$. By Lemma 4.2 and Theorem 4.3(ii), there exists a family of
$r\leqslant q^{2}$ triangle-free partial linear spaces of order
$(q^{2}-1,q-1)$, on the same point set $\mathcal{P}$ and pairwise disjoint
line-sets $\mathcal{L}_{1},\dots,\mathcal{L}_{r}$, and by Theorem 4.3(i), the
point-line geometry
$\left(\mathcal{P},\bigcup_{i=1}^{r}\mathcal{L}_{i}\right)$ is also a partial
linear space. Note that $q^{2}-1\geqslant 2rk\ln k$ and $q-1\geqslant 2k(1+\ln
r)$. By Lemma 3.1, $s_{r}(K_{k+1})=P_{r}(k)\leqslant\lvert\mathcal{P}\rvert$.
By Bertrand’s postulate, $q\leqslant 2ck\sqrt{r}$, and using
$\lvert\mathcal{P}\rvert=q^{5}$ yields the desired bound, with
$C=\lceil(2c)^{5}\rceil=4028$. ∎

##  5\. Concluding remarks

While generalised quadrangles have been used extensively in extremal
combinatorics, and particularly Ramsey theory (e.g. [8, 12, 18, 20, 26]), our
result appears to be the first instance in Ramsey theory where the group
theoretic structure of these geometries is exploited. We are hopeful that
Kantor’s model of generalised quadrangles will lead to new results in other
Ramsey problems as well.

In the probabilistic argument of Section 3, note that if we use $s+1=q^{2}$
and $t+1=q$, then from equation (3.1) it follows that we can solve the
following quadratic inequality in $q$ to ensure that the probability is $<1$:

$\frac{1}{rk}q^{2}-\frac{1+\ln r}{r}q-\ln k>0.$

One can check that this inequality is satisfied for all $q\geqslant k(1+\ln
r)+\sqrt{rk\ln k}$. Using that for any $a,b>0$, $(a+b)^{5}\leqslant
2^{4}(a^{5}+b^{5})$, we obtained the following more refined upper bound.

######  Theorem 5.1.

For all $r\geqslant 2,k\geqslant 2$,

$s_{r}(K_{k})\leqslant
2^{9}\left[(k-1)^{5}\ln^{5}r+(k-1)^{5/2}r^{5/2}\ln^{5/2}(k-1)\right]$

For further improvements to our upper bound we should perhaps explore
triangle-free partial linear spaces that do not arise from generalised
quadrangles. Moreover, if we could make the probabilistic argument of section
3 deterministic, then this could also lead to an improvement in the bound. We
would like to make the following conjecture.

######  Conjecture 5.2.

For all $r\geqslant 2,k\geqslant 2$

$s_{r}(K_{k})\leqslant Ck^{2}r^{2}f(\ln k,\ln r)$

for some constant $C>0$ and a constant degree polynomial function $f$.

The construction presented in this article can also be used to improve the
bound of Dudek and Rödl [7, Theorem 3]. Write
$G\xrightarrow[ind]{}(H)^{v}_{r}$ if for every $r$-colouring of the vertices
of $G$, there exists a monochromatic induced copy of $H$. Let $\omega(G)$ be
the clique number of $G$, i.e., the order of a maximal clique in $G$. We can
conclude the following from our graphs. For a given natural number $r$ there
exists a constant $C=C(r)$ such that for every graph $H$ of order $n$ we have

$\min\left\\{\lvert V(G)\rvert:\ G\xrightarrow[ind]{}(H)^{v}_{r}\text{ and
}\omega(G)=\omega(H)\right\\}\leqslant Cn^{5/2}\ln^{5/2}n.$

In fact, this also follows directly from the existence of generalised
quadrangles of order $(q^{2},q)$ as we just need a single graph and not a
packing.

### Acknowledgements

We are grateful to Anita Liebenau for helpful discussions. We also thank
Simona Boyadzhiyska for pointing out a significant gap in our first draft that
was fixed later.

## References

  * [1] S. A. Burr, P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp.  Ramsey-minimal graphs for star-forests.  Discrete Math., 33(3):227–237, 1981.
  * [2] S. A. Burr, P. Erdős, and L. Lovasz.  On graphs of Ramsey type.  Ars Combin., 1(1):167–190, 1976.
  * [3] S. A. Burr, J. Nešetřil, and V. Rödl.  On the use of senders in generalized Ramsey theory for graphs.  Discrete Math., 54(1):1–13, 1985.
  * [4] S. D. Cohen.  Explicit theorems on generator polynomials.  Finite Fields Appl., 11(3):337–357, 2005.
  * [5] D. Conlon.  A new upper bound for diagonal Ramsey numbers.  Ann. of Math. (2), 170(2):941–960, 2009.
  * [6] D. Conlon, J. Fox, and B. Sudakov.  Recent developments in graph Ramsey theory.  In Surveys in combinatorics 2015, volume 424 of London Math. Soc. Lecture Note Ser., pages 49–118. Cambridge Univ. Press, Cambridge, 2015.
  * [7] A. Dudek and V. Rödl.  An almost quadratic bound on vertex Folkman numbers.  J. Combin. Theory Ser. B, 100(2):132–140, 2010.
  * [8] A. Dudek and V. Rödl.  On $K_{s}$-free subgraphs in $K_{s+k}$-free graphs and vertex Folkman numbers.  Combinatorica, 31(1):39–53, 2011.
  * [9] P. Erdős.  Some remarks on the theory of graphs.  Bull. Amer. Math. Soc., 53:292–294, 1947.
  * [10] P. Erdős and G. Szekeres.  A combinatorial problem in geometry.  Compositio Math., 2:463–470, 1935.
  * [11] J. Fox, A. Grinshpun, A. Liebenau, Y. Person, and T. Szabó.  On the minimum degree of minimal Ramsey graphs for multiple colours.  J. Combin. Theory Ser. B, 120:64–82, 2016.
  * [12] Z. Füredi, A. Naor, and J. Verstraëte.  On the Turán number for the hexagon.  Advances in Mathematics, 203(2):476–496, July 2006.
  * [13] H. Guo and L. Warnke.  Packing nearly optimal Ramsey $R(3,t)$ graphs.  Combinatorica, 40(1):63–103, 2020.
  * [14] H. Hàn, V. Rödl, and T. Szabó.  Vertex Folkman numbers and the minimum degree of minimal Ramsey graphs.  SIAM J. Discrete Math., 32(2):826–838, 2018.
  * [15] W. M. Kantor.  Generalized quadrangles associated with ${G}_{2}(q)^{*}$.  J. Combin. Theory Ser. A, 29:212–219, 1980.
  * [16] W. M. Kantor.  Generalized polygons, SCABs and GABs.  In Buildings and the geometry of diagrams (Como, 1984), volume 1181 of Lecture Notes in Math., pages 79–158. Springer, Berlin, 1986\.
  * [17] H. D. Kim, J. M. Kim, and I. Yie.  Certain cubic polynomials over finite fields.  J. Korean Math. Soc., 46(1):1–12, 2009.
  * [18] A. Kostochka, D. Mubayi, and J. Verstraëte.  Hypergraph Ramsey numbers: triangles versus cliques.  J. Combin. Theory Ser. A, 120(7):1491–1507, 2013.
  * [19] T. Łuczak.  On Ramsey minimal graphs.  Electron. J. Combin., 1:Research Paper 4, approx. 4, 1994.
  * [20] D. Mubayi and J. Verstraëte.  A note on pseudorandom Ramsey graphs.  arXiv preprint, arXiv:/1909.01461., 2019.
  * [21] S. E. Payne and J. A. Thas.  Finite generalized quadrangles.  EMS Series of Lectures in Mathematics. European Mathematical Society (EMS), Zürich, second edition, 2009.
  * [22] F. P. Ramsey.  On a Problem of Formal Logic.  Proc. London Math. Soc. (2), 30(4):264–286, 1929.
  * [23] V. Rödl and M. Siggers.  On Ramsey minimal graphs.  SIAM J. Discrete Math., 22(2):467–488, 2008.
  * [24] A. Sah.  Diagonal Ramsey via effective quasirandomnes.  arXiv preprint, arXiv:2005.09251, 2020.
  * [25] J. Spencer.  Ramsey’s theorem—a new lower bound.  J. Combinatorial Theory Ser. A, 18:108–115, 1975.
  * [26] M. Tait.  Degree Ramsey numbers for even cycles.  Discrete Mathematics, 341(1):104–108, Jan. 2018.


# Ising-like models on Euclidean black holes

Mustafa Saeed<EMAIL_ADDRESS>Department of Mathematics and Statistics,
University of New Brunswick, Fredericton, NB, Canada E3B 5A3  Viqar Husain
<EMAIL_ADDRESS>Department of Mathematics and Statistics, University of New
Brunswick, Fredericton, NB, Canada E3B 5A3

###### Abstract

We study spin models on Euclidean black hole backgrounds. These resemble the
Ising model, but are inhomogeneous with two parameters, the black hole mass
and the cosmological constant. We use Monte-Carlo methods to study macroscopic
properties of these systems for Schwarzschild and anti-deSitter black holes in
four and five dimensions for spin-1/2 and spin-1. We find in every case that
increasing the black hole mass causes the spins to undergo a second order
phase transition from disorder to order and that the phase transition occurs
at sub-Planckian black hole mass.

##  I Introduction

Spin models are useful tools in studying interacting degrees of freedom in
thermal equilibrium. This is primarily due to two reasons. Firstly due to
their simplicity spin models can be solved either exactly or approximately by
analytical or numerical techniques. Secondly if the simple spin model shares
some global features (such as symmetries of the Hamiltonian and the number of
spatial dimensions) with a real system (such as a lattice of interacting
atoms) then some results of the spin model match the behaviour of the real
system Cardy (1996). Two well-studied spin systems are the Ising and Blume-
Capel models Blume (1966); Capel (1966).

The Blume-Capel model is a spin-1 generalization of the Ising model with an
additional self-interaction (or “mass” term) with Hamiltonian
$H=-J\sum_{i,j;nn}s_{i}s_{j}+K\sum_{i}s_{i}^{2}$ where $nn$ denotes that the
sum is over nearest neighbors. It has richer physics than the Ising model; in
two dimensions, if $K>J$ there is no phase transition; if $K\leq J$ then the
ratio $K/J$ not only determines whether the phase transition is continuous
(second order) or discontinuous (first order) but also fixes the critical
temperature. The Blume-Capel model has been rigorously investigated using not
only analytical techniques - such as renormalization group Burkhardt (1976) \-
but by numerical Monte Carlo simulations also Silva et al. (2006).

Monte Carlo studies of the Ising and Blume-Capel models typically use periodic
boundary conditions. Due to this choice the lattice has the topology of a 2
torus. There has been a growing interest in investigating the effects of using
different topologies such as the 2 sphere Hoelbling and Lang (1996) and a
random topology Fernandes et al. (2010). This interest is sourced from
multiple areas, including discrete models of quantum gravity, condensed matter
physics and the statistical mechanics of complex networks such as the internet
Albert and Barabási (2002). There is also a rich literature on investigating
the effects of geometric curvature on the thermodynamic properties of spins.
For example it is known that the Ising model on a 2d hyperbolic plane with
free boundary conditions exhibits multiple phase transitions Wu (1996). This
model is expected to have applications to quantum information Breuckmann et
al. (2020, 2017).

Our goal in this paper is to generalize the Ising and Blume-Capel models to
Schwarzschild and AdS black hole backgrounds and study their physical content.
This is of interest for several reasons: black hole backgrounds are
inhomogeneous (i.e. have explicit dependence on radial location) and thus
provide an interesting platform to generalize spin-models; Euclidean versions
of black hole metrics are used in attempts to understand black hole
thermodynamics Bardeen et al. (1973); Gibbons and Hawking (1977); black holes
metrics are considered as thermal backgrounds for quantum field theory where
the radius of Wick rotated time is proportional to black hole mass; the case
with a cosmological constant provides a generalization of spin models where
the connection between metric parameters and temperature is more involved
Hawking and Page (1983). We review these features before constructing the
models.

Our approach is to start with a scalar field action on a general form of a
Euclidean black hole background, discretize the action on a suitably defined
lattice, and then restrict the scalar field to take on spin values. This
process naturally introduces a point interaction from the scalar field mass
term, and nearest neighbour interactions from a finite difference of the
kinetic term.

In Section II we review the construction of the Euclidean black holes Gibbons
and Hawking (1977); Hawking and Page (1983); Wald (1984) ; in Section III we
define the spin-models; in Section IV we describe and present the Monte-Carlo
calculations for the spin-1/2 and spin-1 models, followed by a summary of the
work and possible extensions.

##  II Euclidean black holes

As a prelude to defining spins models on Euclidean black hole backgrounds, in
this section we summarize the main aspects of the metrics we will be using.

The Schwarzschild black hole metric in its original form is

$ds^{2}=-\left(1-\frac{2M}{r}\right)dt^{2}+\left(1-\frac{2M}{r}\right)^{-1}dr^{2}+r^{2}d\Omega^{2},$
(II.1)

in the coordinates $(t,r,\theta,\phi)$; it has a coordinate singularity at the
horizon $r=2M$ and a curvature singularity at $r=0$. In the Kruskal-Szekeres
(KS) coordinates $(T,X,\theta,\phi)$ defined as

$\displaystyle-T^{2}+X^{2}$ $\displaystyle=$
$\displaystyle\left(\frac{r}{2M}-1\right)\exp(-\frac{r}{2M})$ (II.2)
$\displaystyle\frac{T+X}{T-X}$ $\displaystyle=$
$\displaystyle\exp(-\frac{t}{2M})$ (II.3)

the geometry is

$ds^{2}=\frac{32M^{3}}{r}\exp\left(-\frac{r}{2M}\right)\left(-dT^{2}+dX^{2}\right)+r^{2}d\Omega^{2}.$
(II.4)

In these coordinates the event horizon $r=2M$ is given by $T=\pm X$, and the
singularity at $r=0$ is $T^{2}-X^{2}=1$. The KS coordinates provide a global
extension of the original Schwarzschild metric, and are best suited to
understanding its Euclidean version.

The Euclidean KS metric is defined by the Wick rotation $\tau=iT$

$ds^{2}=\frac{32M^{3}}{r}\exp(-\frac{r}{2M})\left(d\tau^{2}+dX^{2}\right)+r^{2}d\Omega^{2},$
(II.5)

where now $\displaystyle\tau^{2}+X^{2}=\left(r/2M-1\right)\exp(-r/2M)$. This
rotated metric is singularity free since $r=0$ now corresponds to
$\tau^{2}+X^{2}=-1$ which has no solution; the horizon $r=2M$ corresponds to
$\tau^{2}+X^{2}=0$, which is the origin of $(\tau,X)$ plane. Thus, the
Euclidean Schwarzschild geometry is singularity free and the interior of the
Lorentzian Schwarzschild metric ($r<2M$) is absent.

Having obtained the Euclidean Schwarzschild geometry in the KS coordinates, we
now see that the same result is obtained in the original coordinates by simply
restricting the radial coordinate to $r\in[2M,\infty)$, with $\tau=it$.

The near-horizon metric is obtained by setting $r=2M+\mu$; then for $\mu\ll 1$
the $\tau-\mu$ part of the metric is

$ds^{2}=\frac{2M}{\mu}d\mu^{2}+\frac{\mu}{2M}d\tau^{2};$ (II.6)

defining $d\rho^{2}=(2M/\mu)d\mu^{2}$ gives

$ds^{2}=d\rho^{2}+\left(\frac{\rho}{4M}\right)^{2}d\tau^{2}.$ (II.7)

The final observation is that absence of a conical singularity at $\rho=0$
requires $\tau/4M\in[0,2\pi)$.

This procedure is readily generalized Wald (1984) for obtaining a regular
Euclidean black hole geometry starting from the $d-$dimensional metric

$ds^{2}=-F(r)dt^{2}+F(r)\,^{-1}dr^{2}+r^{2}d\Omega_{d-2}\,^{2},$ (II.8)

where $F(r)$ is a one to one function such that there is an
$r_{0}\in[0,\infty)$ such that $F(r_{0})=0$ (the horizon),
$F^{\prime}(r_{0})>0$ and $\lim_{r\rightarrow 0}F(r)=\infty$ (the
singularity). Then, the Wick rotation $\tau=it$, the restriction
$r\in[r_{0},\infty)$ and the coordinate transformation

$\rho(r)=\beta_{0}\sqrt{F(r)},\qquad\beta_{0}=\frac{2}{F^{\prime}(r_{0})}$
(II.9)

gives the metric

$\displaystyle ds^{2}$ $\displaystyle=$
$\displaystyle\left(\frac{\rho}{\beta_{0}}\right)^{2}d\tau^{2}+\left(\frac{2}{\beta_{0}F^{\prime}(r)}\right)^{2}d\rho^{2}$
(II.10) $\displaystyle\quad+\ r^{2}(\rho)\ d\Omega_{d-2}\,^{2},$

where $\tau\in(-\infty,\infty)$ and $\rho\in[0,\lim_{r\to\infty}\,\rho(r)]$.
The near-horizon $r\approx r_{0}$ metric is

$ds^{2}=d\rho^{2}+\left(\frac{\rho}{\beta_{0}}\right)^{2}d\tau^{2}+r^{2}(\rho)d\Omega_{d-2}\,^{2}.$
(II.11)

Thus the $\tau-\rho$ part of the metric is flat space with no conical
singularity provided $\tau\beta_{0}\,^{-1}$ is an angular coordinate with
period $2\pi$; this corresponds to $\tau$ having periodicity $\beta$

$\displaystyle\tau\in[0,\beta),\quad\beta=2\pi\beta_{0}.$ (II.12)

The inverse of the Euclidean time periodicity is the natural temperature of
the spacetime

$T=\left(2\pi\beta_{0}\right)^{-1}.$ (II.13)

In summary, we will use the metric (II.10) with the periodically identified
$\tau$ as the background for defining spin models, with the function

$F(r)=1-\frac{2M}{r^{d-3}}+\left(\frac{r}{L}\right)^{2};$ (II.14)

this is the AdS black hole in $d$ spacetime dimensions where the scale $L$ is
related to $d$ and the cosmological constant by
$\Lambda=-(d-1)(d-2)/(2L^{2})$. The cases we consider are 4d Schwarzschild
($L\rightarrow\infty$) and Schwarzschild AdS in 4d and 5d.

Figure 1:  Temperature-Mass relation for Euclidean AdS-Schwarzschild for
$L=0.3,0.4,0.5,0.6$ (top to bottom).

The temperature-mass relation for the 4d Schwarzschild case is $T=(4\pi
r_{0})^{-1}=(8\pi M)^{-1}$. However for the 4d anti-deSitter case it is

$T=\frac{3r_{0}\,^{2}+L^{2}}{4\pi r_{0}L^{2}};\quad
M=\frac{r_{0}}{2}\left[1+\left(\frac{r_{0}}{L}\right)^{2}\right].$ (II.15)

$T(M)$ has a minimum at $\displaystyle T_{\text{m}in}=\sqrt{3}/(2\pi L)$ at
mass $\displaystyle M_{*}=2L/(3\sqrt{3})$ (Fig. 1) and horizon radius
$r_{0*}=L/\sqrt{3}$; $T>T_{\text{m}in}$ corresponds to either a small or a
large mass black hole; a similar result holds the 5d Schwarzschild AdS case
also. This discussion will be relevant below where we discuss phase
transitions in spin models as functions of $T$ and $M$.

##  III Spin models on black holes

Spin models on Euclidean black hole backgrounds may be defined by starting
with the Euclidean action of a scalar field on the metrics reviewed in the
last section, discretizing the action, and then restricting the scalar field
variable to take discrete values, $\pm 1$ for Ising, and $0,\pm 1$ for Blume-
Capel models. The $d$-dimensional Euclidean action for a massive scalar field
on a background metric $g_{ab}$ is

$I_{E}\left[\Phi\right]=\frac{1}{2}\int d^{d}x\
\sqrt{g}\left(g^{ab}\partial_{a}\Phi\partial_{b}\Phi+m^{2}\Phi^{2}\right).$
(III.1)

The Euclidean black hole metrics (II.10) have the form

$ds^{2}=u(\rho)d\tau^{2}+v(\rho)d\rho^{2}+w(\rho)d\Omega_{d-2}\,^{2}.$ (III.2)

We consider only the $\tau-\rho$ plane since the sphere is not relevant for
the black hole properties of interest. Therefore the scalar field we consider
is $\Phi\equiv\Phi(\tau,\rho)$ with the Euclidean time periodicity
$\Phi(0,\rho)=\Phi(\beta,\rho)$. With these assumptions the Euclidean action
reduces to

$\displaystyle I_{E}\left[\Phi\right]$ $\displaystyle=$
$\displaystyle\frac{A_{d-2}}{2}\int^{\beta}_{0}\int_{0}^{\rho_{0}}d\tau
d\rho\sqrt{w^{d-2}}$ (III.3)
$\displaystyle\cdot\left(\sqrt{\frac{v}{u}}{\dot{\Phi}}^{2}+\sqrt{\frac{u}{v}}{\Phi^{\prime}}^{2}+m\sqrt{uv}\Phi^{2}\right)$

where $A_{d-2}$ is the area of $S^{d-2}$ and dots and primes denote partial
derivatives with respect to $\tau$ and $\rho$; the $\rho$ integration is
restricted to a finite value $\rho_{0}$ to define a discrete model on a finite
lattice. The object of interest is the partition function

$Z=\int{D\Phi\exp\left(-I_{E}\left[\Phi\right]\right)}.$ (III.4)

###  III.1 Discretization

Consider the $\tau-\rho$ plane as an $N_{\beta}\times N_{\rho}$ lattice with
spacing

$\epsilon=\frac{\beta}{N_{\beta}}=\frac{\rho_{0}}{N_{\rho}}.$ (III.5)

Through $\beta$ the lattice spacing depends on the metric parameters $M$ and
$\Lambda$, and a simple discretization is given by

$\displaystyle\tau\rightarrow\tau_{m}=m\epsilon,\qquad\rho\rightarrow\rho_{n}=n\epsilon;$
$\displaystyle f(\tau,\rho)\rightarrow f_{m,n},$
$\displaystyle\dot{f}\rightarrow\frac{f_{m+1,n}-f_{m,n}}{\epsilon},$
$\displaystyle f^{\prime}\rightarrow\frac{f_{m,n+1}-f_{m,n}}{\epsilon}.$
(III.6)

Lastly, the scalar field values are restricted to the set

$\Phi=\\{-s,\,-s+1,\,...\,\,s-1,\,s\\}\times s^{-1},\quad s\in\mathbb{N},$
(III.7)

so that the values of $\Phi$ are rational numbers in the interval $[-1,1]$.
With this discretization the Euclidean action becomes the sum

$\displaystyle I_{E}\left[\Phi\right]$ $\displaystyle=$ $\displaystyle
A_{d-2}\sum_{m,n=1}^{N_{\beta},N_{\rho}}\left\\{-\Phi_{m,n}\left[\sqrt{\frac{v_{n}w_{n}\,^{d-2}}{u_{n}}}\,\Phi_{m+1,n}+\sqrt{\frac{u_{n}w_{n}\,^{d-2}}{v_{n}}}\,\Phi_{m,n+1}\right]\right.$
(III.8)
$\displaystyle\left.+\,\Phi^{2}_{m,n}\left[\sqrt{\frac{v_{n}w_{n}\,^{d-2}}{u_{n}}}+\frac{1}{2}\left(\sqrt{\frac{u_{n}w_{n}\,^{d-2}}{v_{n}}}+\sqrt{\frac{u_{n-1}w_{n-1}\,^{d-2}}{v_{n-1}}}\right)+\frac{m\epsilon^{2}}{2}\sqrt{u_{n}v_{n}w_{n}\,^{d-2}}\right]\right\\}.$

This is the desired “spin” model. It is apparent that the coupling “constants”
vary across the lattice and depend on the metric functions from point to
point; the first line contains metric function-weighed nearest neighbour
interactions in the $\tau$ and $\rho$ directions; the second line represents
spin self-interactions which are either weighed by the metric functions or by
the determinant of the metric, scalar field mass and $\epsilon^{2}$ (a factor
that cancels out for the remaining terms); the choice $s=1/2$ or $s=1$ gives
an Ising or Blume Capel like model on Euclidean black hole background
respectively; the self interaction terms only affect statistical averages in
the latter case.

For the 4d Euclidean AdS-Schwarzschild geometry the metric functions are

$\displaystyle u(\rho)$
$\displaystyle=\left[\left(\frac{3r_{0}{}^{2}+L^{2}}{2r_{0}L^{2}}\right)\rho\right]^{2}$
(III.9) $\displaystyle v(\rho)$
$\displaystyle=\left[\left(\frac{3r_{0}{}^{2}+L^{2}}{2r_{0}L^{2}}\right)\left(\frac{L^{2}\,r^{2}(\rho)}{r^{3}(\rho)+ML^{2}}\right)\right]^{2}$
(III.10) $\displaystyle w(\rho)$ $\displaystyle=r^{2}(\rho),$ (III.11)

where $r(\rho)$ is given by (II.9) with $F(r)=(1-r/2M+r^{2}/L^{2})$; it is
readily verified that for this $F$ there is a single real root for $r(\rho)$,
a fact that leads to unambiguous values of $w(\rho)$. On the lattice these
functions are discretized with the replacements
$\rho\rightarrow\rho_{n}=n\epsilon$ and $r_{n}(\rho_{n})$. This results in the
specific spin model

$\begin{split}I_{E}\left[\Phi\right]=&\
4\pi\sum_{m,n=1}^{N_{\beta},N_{\rho}}\,\Bigg{\\{}-\Phi_{m,n}\left[\left(\frac{r_{n}{}^{4}}{\rho_{n}}\right)\left(\frac{L^{2}}{ML^{2}+r_{n}{}^{3}}\right)\Phi_{m+1,n}+\left(\rho_{n}\right)\left(\frac{ML^{2}+r_{n}{}^{3}}{L^{2}}\right)\Phi_{m,n+1}\right]\\\
&+\left[\left(\frac{r_{n}{}^{4}}{\rho_{n}}\right)\left(\frac{L^{2}}{ML^{2}+r_{n}{}^{3}}\right)+\left(\frac{ML^{2}+r_{n}{}^{3}}{2L^{2}}\right)\left(\rho_{n}+\rho_{n-1}\right)\right]\Phi_{m,n}\,^{2}\\\
&+\left(\frac{\rho_{n}r_{n}{}^{4}L^{2}}{ML^{2}+r_{n}{}^{3}}\right)\left(\frac{3r_{0}{}^{2}+L^{2}}{2r_{0}L^{2}}\right)^{2}\,\epsilon^{2}\,\left(\frac{m}{2}\right)\Phi_{m,n}\,^{2}\Bigg{\\}}.\end{split}$
(III.12)

The limit $L\rightarrow\infty$ gives the model on 4d Euclidean Schwarzschild
background:

$\begin{split}I_{E}\left[\Phi\right]=&4\pi\sum_{m,n=1}^{N_{\beta},N_{\rho}}\,\bBigg@{3.5}\\{-\Phi_{m,n}\left[\frac{16M^{3}}{\rho_{n}\left(1-\left(\frac{\rho_{n}}{4M}\right)^{2}\right)^{4}}\,\,\Phi_{m+1,n}+\left(\rho_{n}M\right)\Phi_{m,n+1}\right]\\\
<EMAIL_ADDRESS>(III.13)

A similar procedure gives the model on the 5d AdS-Schwarzschild metric, and
indeed any metric of the form (III.2).

This completes the prescription for defining spin models on Euclidean black
hole spaces. The process we have followed is similar to discretizing any
continuum theory on a lattice where certain discretization choices are made;
in our case this is the representation for time and space derivatives. The
procedure we have followed is analagous to discretized thermal quantum field
theory (TQFT) on Euclideanized Minkowski spacetime with periodic
identification of Wick rotated time. But there are important differences: in
the black hole case the metric comes with the mass and cosmological constant
parameters, and the periodicity of Euclidean time (which is guided by the
requirement to remove the conical singularity) depends on these parameters.

##  IV Simulation details and results

As we have noted, in accordance with the relation (II.12) between the $\tau$
dimension size and black hole mass, the lattice size in the $\tau$ direction
varies with $M$. Thus the thermodynamics properties of spins are best studied
as a function of $M$ with fixed lattice spacing $\epsilon$ but varying
$\tau$-dimension lattice size. We perform Monte Carlo simulations with
$\epsilon=0.01$, and take

$N_{\beta}=\left\lfloor\frac{\beta}{\epsilon}\right\rfloor,\quad
N_{\rho}=\left\lfloor\frac{\rho_{0}}{\epsilon}\right\rfloor$ (IV.1)

where $\beta$ is given by (II.12) and we take $\rho_{0}=\rho(5r_{0})$ as the
radial extent of the lattice. For convenience we use periodic boundary
conditions in the $\rho$ direction and $m=0$ for all simulations in addition
to $\Lambda=-4$ for the AdS simulations.

After choosing a particular Euclidean black hole metric (Schwarzschild, 4d
Schwarzschild-AdS or 5d Schwarzschild-AdS), we select a set of $M$ values;
each value of $M$ fixes the lattice size. We use an aligned lattice (a cold
start) once an $M$ value is selected. Subsequent configurations are generated
according to the probability distribution $\displaystyle P(x)=\exp[-I_{E}(x)]$
using a Monte Carlo Markov Chain (MCMC). We use the standard procedure where a
single Monte Carlo (MC) step entails flipping a randomly selected spin,
computing the resulting change in the action $\Delta I_{E}$, and keeping the
new configuration provided $\displaystyle\exp\left(-\Delta
I_{E}\right)\geq\text{rand}[0,1]$; a sweep is defined as $N_{\beta}\times
N_{\rho}$ MC steps.

Thermalization requires a number of sweeps from the starting cold
configurations. This is determined by computing $I_{E}$ as a function of the
number of sweeps until a steady state is reached. Fig. 2 shows that the
required number of sweeps to thermalization is about 50 for the Euclidean
Schwarzschild case with $M=0.025$ .

Figure 2: Spins on Euclidean Schwarzschild background with $M=0.025$ are
thermalized at around the $50^{th}$ MC sweep.

After thermalization we compute the average values of several thermodynamic
quantities ${\cal O}$ with an additional $N_{M}=2000$ sweeps for each value of
mass $M$ on its corresponding lattice using the formula

$\langle{\cal O}\rangle=\frac{1}{N_{M}}\ \sum_{k=1}^{N_{M}}{\cal O}_{i}.$
(IV.2)

Here $i$ is the number of the sweep and $\mathcal{O}_{i}$ is the corresponding
measurement of the thermodynamic quantity. The specific quantities ${\cal O}$
we calculate include the alignment, energy, susceptibility and specific heat:

$\displaystyle A$ $\displaystyle=$
$\displaystyle\left(\frac{1}{N_{\beta}N_{\rho}}\right)\,\Bigg{|}\,\sum_{m,n=1}^{N_{\beta},N_{\rho}}\Phi_{m,n}\,\Bigg{|},$
(IV.3) $\displaystyle E$ $\displaystyle=$
$\displaystyle\left(\frac{1}{N_{\beta}N_{\rho}}\right)\,I_{E},$ (IV.4)
$\displaystyle\chi$ $\displaystyle=$ $\displaystyle\frac{1}{T}\ \left(\langle
A^{2}\rangle-\langle A\rangle^{2}\right),$ (IV.5) $\displaystyle C$
$\displaystyle=$ $\displaystyle\frac{1}{T^{2}}\ \left(\langle
E^{2}\rangle-\langle E\rangle^{2}\right).$ (IV.6)

Another observable we calculate is entropy $S(T)$. A computation of $S(T)$
without using the partition function $Z$ (which is not available) is to
utilize a discrete version of the formula

$S(T)=\int_{0}^{T}\frac{C(T^{\prime})}{T^{\prime}}dT^{\prime}.$ (IV.7)

A discrete estimate is

$S(T)\approx\sum_{i=1}^{N_{T}}\left[\frac{C(T_{i})}{T_{i}}\right]\left(T_{i}-T_{i-1}\right),$
(IV.8)

where $N_{T}$ is the total number of temperatures simulated till $T$ in MC
runs, and $T_{i}$ represents the $i^{th}$ temperature in that list (where
$T_{1}$ is the minimum temperature possible due to computational or
theoretical constraints) and $C(T_{i})$ is the heat capacity numerically
evaluated at $T_{i}$.

For computing $A$, $\chi$, $C$ and $S$, let us recall that a lattice is
determined by $M$, and for the AdS black holes a value of $M$ uniquely
determines $T$, but not vice versa (Fig. 1). Therefore these quantities as
functions of $M$ are more naturally visualized for the AdS cases. However it
is also useful to see these quantities as functions of $T$; for a given $T$
there are two values of $M$, the small and large black holes; these correspond
to two different lattices, one for each mass. Therefore we expect two sets of
results for each of $A$, $\chi$, $C$ and $S$ as functions of $T$, one for the
small black hole and the other for the large black hole.

###  IV.1 Numerical results

We computed the alignment, susceptibility, specific heat, and entropy for
spin-1/2 and spin-1 models for Schwarzschild, and 4d and 5d Schwarzschild AdS.
In each case we find evidence of a phase transition at a critical value of
mass $M_{c}$; in each case it turns out that $M_{c}$ is sub-Planckian with
value indicated in the figures. We first plot these quantities as functions of
$M/M_{c}$, and again as functions of $T/T_{c}$, where $T_{c}$ for the AdS
cases is uniquely determined (as for $\Lambda=0$) by $M_{c}$.

Figures 3 and 4 exhibit thermodynamic quantities for the spin-1/2 case for the
three Euclidean black hole backgrounds, as functions of $M/M_{c}$ and
$T/T_{c}$ respectively; Figs. 5 and 6 show the same for spin-1.

Figure 3: Plots of thermodynamic quantities for spin 1/2 models on Euclidean
black holes with respect to $\frac{M}{M_{c}}$. The critical masses for
Schwarzschild, and 4d and 5d Schwarzschild AdS ($\Lambda=-4$) are 0.070, 0.072
and 0.023 respectively in Planck units.  Figure 4: Plots of thermodynamic
quantities for spin 1/2 models on Euclidean black holes with respect to
$\frac{T}{T_{c}}$. The critical temperatures for Schwarzschild, 4d
Schwarzschild AdS and 5d Schwarzschild AdS are 0.57, 0.61 and 0.80
respectively. For the AdS cases the point circled blue represents the black
hole that corresponds to $T_{min}$, the black diamonds correspond to the large
black holes, and the red dots correspond to the small black holes. Figure 5:
Plots of thermodynamic quantities for spin 1 models on Euclidean black holes
with respect to $\frac{M}{M_{c}}$. The critical masses for Schwarzschild, 4d
Schwarzschild AdS and 5d Schwarzschild AdS are 0.14, 0.17 and 0.065
respectively. Figure 6: Plots of thermodynamic quantities for spin 1 models on
Euclidean black holes with respect to $\frac{T}{T_{c}}$. The critical
temperatures for Schwarzschild, 4d Schwarzschild AdS and 5d Schwarzschild AdS
are 0.28, 0.36 and 0.53 respectively. For the AdS cases the point circled blue
represents the black hole that corresponds to $T_{min}$, the black diamonds
correspond to the large black holes, and the red dots correspond to the small
black holes.

Evidence of a second order phase transition is apparent in the figures;
specifically the specific heat and susceptibility exhibit an approximate
divergence at the respective critical values of the masses, whereas the
alignment indicates a transition from disorder to order as the mass increases.
A curious feature is that the value of the critical masses is sub-Planckian
(in the geometrized units $\hbar=c=G=1$).

The graphs of the thermodynamic variables as a function of $T/T_{c}$ contain
two curves for the AdS cases; these are constructed by identifying the two
possible black hole masses corresponding to a fixed $T$ value as in Fig. 1. To
illustrate the procedure, consider for example the alignment graph as a
function of $T/T_{c}$ for 4d Schwarzschild-AdS: a fixed $T$ identifies a large
and a small black hole mass above the minimum value $T_{\rm min}$; we take the
two alignment values for these two masses from the alignment vs. mass graph
and plot these values at the fixed $T$; this process is repeated for all data.
The critical temperature is obtained uniquely from the critical mass value.
Thus for example, in the alignment vs. $T/T_{c}$ graphs in Fig. 4, the circled
point corresponds to the minimum ($T_{\rm min}$) of the $T$ vs. $M$ curve in
Fig. 1; the black diamonds correspond to the large black holes, and the red
dots correspond to the small black holes; in the range of $T$ shown, the spins
are ordered (as functions of $T$) for the large black hole, but exhibit a
transition to disorder for the small black hole. Similar results hold for all
the other thermodynamic quantities: spins on the background of the small black
hole exhibit a phase transition as functions of $T$, but spins on the
background of the large black hole do not, at least for the range of $T$
values we were able to efficiently compute. Table 1 lists the critical masses
and corresponding temperatures for all the cases studied.

Background | Spin 1/2 | Spin 1
---|---|---
|  $M_{c}$ |  $T_{c}$ |  $M_{c}$ |  $T_{c}$
4d Schwarzschild |  0.070 |  0.57 |  0.14 |  0.28
4d Schwarzschild AdS |  0.072 |  0.61 |  0.17 |  0.36
5d Schwarzschild AdS |  0.023 |  0.80 |  0.065 |  0.53
Table 1: Table of critical masses and critical temperatures for spin 1/2 and
spin 1 models on the Euclidean black hole backgrounds considered.

Lastly Figs. 7 and 8 are log-log graphs of the thermodynamics quantities for
the spin-half and spin-one models as functions of the reduced temperature $t$,
where $t=1-\frac{T}{T_{c}}$; these figures exhibit linear behaviour and
therefore power laws of the form

$\displaystyle A$ $\displaystyle\approx$ $\displaystyle t^{b},$
$\displaystyle\chi$ $\displaystyle\approx$ $\displaystyle t^{-g},$
$\displaystyle C$ $\displaystyle\approx$ $\displaystyle t^{-a},$ (IV.9)

together with least square fit estimates for the critical exponents $b,g$ and
$a$. It is worth mentioning that for the Ising or Blume-Capel models, $\chi$
and $C$ from equation (IV.1) depend on $|t|$ and conventionally the critical
exponents are calculated separately for $t>0$ and $t<0$ following which they
are averaged; we use $t>0$ only since it corresponds to larger lattices and
therefore more accurate results.

Figure 7: Estimating critical exponents of thermodynamic quantities for spin
1/2 models on Euclidean black holes. The horizontal axis is ln($t$) and the
vertical axis is the ln of the thermodynamic variable in the corresponding
row. Figure 8: Estimating critical exponents of thermodynamic quantities for
spin 1 models on Euclidean black holes. The horizontal axis is ln($t$) and the
vertical axis is the ln of the thermodynamic variable in the corresponding
row.

This completes the description of the results: our main observation is that
spins on Euclidean black hole geometries in four and five dimensions undergo
phase transitions as a function of the mass parameter associated to the
geometries. Perhaps surprisingly, the phase transitions to order occur at
approximately a tenth of Planck mass in 4d (Table 1), whereas an intuitive
expectation might be a few Planck masses. Nevertheless a transition in this
range is not surprising considering the Planck mass is the only natural scale
in the spin model.

##  V Discussion

The model and results we have described may be viewed as falling in the broad
area of quantum fields on curved spacetime Birrell and Davies (1982); Paker
and Toms (2009). Most work in this area is concerned mainly with quantum
fields on Lorentzian rather than Euclidean curved geometries; the exception is
thermal QFT which is quantum fields on Wick rotated Minkowski space Schwinger
(1958); Nakano (1959); Symanzik (2004, 1969). The model and the calculations
we have performed are new in that (to our knowledge) there are no prior
studies of inhomogeneous spin models on Euclidean black holes. Our work may be
viewed as exploring the extent to which a Euclidean black hole is equivalent
to a thermal heat bath for matter degrees of freedom propagating on such a
geometry; our work does not concern or provide comment on the use of such
solutions as contributions to the path integral of Euclidean quantum gravity
without matter, which is the arena for the Hawking-Page transition Hawking and
Page (1983).

The inhomogeneity of the spin models comes from the radial dependence of the
coupling strength evident in the actions (III.12) and (III.13). This variation
of coupling strength across the lattice means that the probability of a spin
flip is dependent on radial position in the lattice; e.g. for Euclidean
Schwarzschild the nearest-neighbour coupling in the $\tau$-direction varies as
$M^{3}/[\rho_{n}(1-(\rho_{n}/4M)^{2})]^{4}$, whereas the coupling in the
$\rho$-direction varies as $\rho_{n}M$. This not only makes apparent the
inhomogeneous nature of the model but it also confirms that for small/large
$M$ the couplings are weak/strong which accounts for the observed
disorder/order. The radial dependence of couplings also means that at the
transition point from order to disorder does not have the scale invariance of
homogeneous models observed across the lattice. This in turn indicates that
the assignment of the term “second-order transition” comes with qualifications
despite the linearity observed in the log-log graphs in Figs. 7 and 8.

Numerical accuracy of our results can be improved. This may be accomplished by
an MC algorithm that is more efficient than the single spin flip one used in
this work. However it is worth noting that most MC algorithms - such as
Wolff’s algorithm Landau and Binder (2015); Pang (2006) and that proposed in
Wang and Landau (2001) \- are designed to study spins on a flat Euclidean
background for which temperature is an external parameter and is not related
to lattice size. Therefore the MC algorithm being used must first be
redesigned to apply to the type of inhomogeneous models that arise on black
hole backgrounds. Another way to improve accuracy is via the finite size
scaling technique Landau (1976); Landau and Binder (2015); Thijssen (2007),
where successively finer lattices are used to approach the continuum limit.

Beyond improving MC methods, there are several directions for extending this
work on spin models on Euclidean black hole backgrounds: exploring
thermodynamic properties while varying both mass and cosmological constant;
Reissner-Nördstrom black holes and other black holes, including extremal
cases; higher spin; continuum of scalar field values within a given range
rather than discrete; and adding mass and other self-interaction terms.

Acknowledgements This work was supported by the Natural Science and
Engineering Research Council of Canada.

## References

  * Cardy (1996) J. Cardy, _Scaling and Renormalization in Statistical Physics_ , Cambridge Lecture Notes in Physics (Cambridge University Press, 1996).
  * Blume (1966) M. Blume, Phys. Rev. 141, 517 (1966).
  * Capel (1966) H. W. Capel, Physica 32, 966 (1966).
  * Burkhardt (1976) T. W. Burkhardt, Phys. Rev. B 14, 1196 (1976).
  * Silva et al. (2006) C. J. Silva, A. A. Caparica, and J. A. Plascak, Phys. Rev. E 73, 036702 (2006).
  * Hoelbling and Lang (1996) C. Hoelbling and C. B. Lang, Phys. Rev. B 54, 3434 (1996).
  * Fernandes et al. (2010) F. Fernandes, F. Lima, and J. Plascak, Computer Physics Communications 181, 1218 (2010), ISSN 0010-4655.
  * Albert and Barabási (2002) R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
  * Wu (1996) C. C. Wu, Journal of Statistical Physics 85 (1996).
  * Breuckmann et al. (2020) N. P. Breuckmann, B. Placke, and A. Roy, Phys. Rev. E 101, 022124 (2020).
  * Breuckmann et al. (2017) N. P. Breuckmann, C. Vuillot, E. Campbell, A. Krishna, and B. M. Terhal, Quantum Science and Technology 2, 035007 (2017).
  * Bardeen et al. (1973) J. M. Bardeen, B. Carter, and S. W. Hawking, Communications in Mathematical Physics 31 (1973).
  * Gibbons and Hawking (1977) G. W. Gibbons and S. W. Hawking, Phys. Rev. D 15, 2752 (1977).
  * Hawking and Page (1983) S. W. Hawking and D. N. Page, Commun. Math. Phys. 87, 577 (1983).
  * Wald (1984) R. M. Wald, _General Relativity_ (Chicago Univ. Pr., Chicago, USA, 1984).
  * Birrell and Davies (1982) N. D. Birrell and P. C. W. Davies, _Quantum Fields in Curved Space_ , Cambridge Monographs on Mathematical Physics (Cambridge University Press, 1982).
  * Paker and Toms (2009) L. Paker and D. Toms, _Quantum Field Theory in Curved Spacetime_ (Cambridge University Press, Cambridge, UK, 2009).
  * Schwinger (1958) J. Schwinger, Proc. Nat. Acad. Sc. 44, 956 (1958).
  * Nakano (1959) T. Nakano, Progress of Theoretical Physics 21, 241 (1959), ISSN 0033-068X.
  * Symanzik (2004) K. Symanzik, Journal of Mathematical Physics 7, 510 (2004), ISSN 0022-2488.
  * Symanzik (1969) K. Symanzik, _Euclidean Quantum Field Theory_ (Academic Press, Chicago, USA, 1969).
  * Landau and Binder (2015) D. P. Landau and K. Binder, _A Guide to Monte Carlo Simulations in Statistical Physics_ (Cambridge University Press, Cambridge, UK, 2015).
  * Pang (2006) T. Pang, _An Introduction to Computational Physics_ (Cambridge University Press, Cambridge, UK, 2006).
  * Wang and Landau (2001) F. Wang and D. P. Landau, Phys. Rev. Lett. 86, 2050 (2001).
  * Landau (1976) D. P. Landau, Phys. Rev. B 13, 2997 (1976).
  * Thijssen (2007) J. Thijssen, _Computational Physics_ (Cambridge University Press, 2007), 2nd ed.


pnasresearcharticle Li Most contemporary statistics theories focus on
asymptotic analysis due to its tractability and simplicity. Non-asymptotic
statistics are crucial when dealing with small or moderate sample sizes, which
is often the case in practice. In situations where analytical results are
difficult or impossible to obtain, Monte Carlo studies serve as a powerful
tool for addressing non-asymptotic behavior. However, these studies can be
computationally expensive, particularly when high precision is required or
when the statistical model demands significant computational time. Here, we
propose calibrated Monte Carlo study that aims to approximate the randomness
structures using a small set of sequences. This approach sheds light on
understanding the general structure of randomness.

# Robust estimations from distribution structures: V. Non-asymptotic

Tuobang Li  Technion-Israel Institute of Technology, Haifa 32000, Israel
Guangdong Technion-Israel Institute of Technology, Shantou 515063, China
University of California, Berkeley, CA 94720

###### Abstract

Due to the complexity of order statistics, the finite sample behaviour of
robust statistics is generally not analytically solvable. While the Monte
Carlo method can provide approximate solutions, its convergence rate is
typically very slow, making the computational cost to achieve the desired
accuracy unaffordable for ordinary users. In this paper, we propose an
approach analogous to the Fourier transformation to decompose the finite
sample structure of the uniform distribution. By obtaining sets of sequences
that are consistent with parametric distributions for the first four sample
moments, we can approximate the finite sample behavior of other estimators
with significantly reduced computational costs. This article reveals the
underlying structure of randomness and presents a novel approach to integrate
multiple assumptions.

###### keywords:

finite sample bias $|$ order statistics $|$ variance reduction $|$ Monte Carlo
study $|$ uniform distribution

This manuscript was compiled on

In the early nineteenth century, Bessel deduced the unbiased sample variance
and found it has a correction term of $\frac{n}{n-1}$. One century later,
Cramér (1) in his classic textbook _Mathematical Methods of Statistics_
deduced unbiased sample central moments with a linear time complexity (2).
However, apart from the mean and central moments, the finite sample behavior
of nearly all other estimators depends on the underlying distribution and
lacks a simple non-parametric correction term. A widely used exact finite
sample bias correction for unbiased standard deviation in the Gaussian
distribution is the factor,
$\sqrt{\frac{n-1}{2}}\frac{\Gamma\left(\frac{n-1}{2}\right)}{\Gamma\left(\frac{n}{2}\right)}$,
which can be deduced using Cochran’s theorem (3). While this correction is
already more complex than Bessel’s correction, for robust statistics, the
situation is even much more complicated. For example, the simplest robust
estimator, the median, exhibits a highly complex finite sample behavior. If
$n$ is odd,
$E\left[median_{n}\right]=\int_{-\infty}^{\infty}{\left(\frac{n+1}{2}\right)\binom{n}{\frac{n}{2}-\frac{1}{2}}F\left(x\right)^{\frac{n}{2}-\frac{1}{2}}\left[1-F(x)\right]^{\frac{n}{2}-\frac{1}{2}}f(x)xdx}$
(4), where $F(x)$ and $f(x)$ represent the cumulative distribution function
(cdf) and probability density function (pdf) of the assumed distribution,
respectively. For the exponential distribution, the above equation is
analytically solvable, yielding
$E\left[median_{n}\right]=\frac{2^{-n-1}(n+1)\binom{n}{\frac{n-1}{2}}\left(H_{n}-H_{\frac{n-1}{2}}\right)\Gamma\left(\frac{n+1}{2}\right)\sqrt{\pi}}{\lambda\Gamma\left(\frac{n}{2}+1\right)}$,
where $H_{n}$ denotes the $n$th Harmonic number, $\Gamma$ represents the gamma
function, and $\lambda$ stands for the scale parameter of the exponential
distribution. However, for distributions with more complex pdfs, such
equations are generally unsolvable. For more complex estimators, writing their
exact finite-sample distribution formulas becomes challenging. In 2013,
Nagatsuka, Kawakami, Kamakura, and Yamamoto derived the exact finite-sample
distribution of the median absolute deviation, which consists of four cases,
each with a lengthy formula (5). In such cases, even obtaining a numerical
solution is challenging (4, 5). So, Monte Carlo simulation is currently the
only practical choice for estimating finite sample corrections. However, the
computational cost of Monte Carlo simulation is often too high to be processed
on a typical PC. For example, for median absolute deviation, Croux and
Rousseeuw (1992) provided correction factors with a precision of three decimal
places for $n\leq 9$ using 200,000 pseudorandom Gaussian sample (6). Hayes
(2014) reported correction factors for $n\leq 100$ using 1 million
pseudorandom samples for each value of $n$ to ensure the accuracy to four
decimal places (7). Recently, Akinshin (2022) (8) presented correction factors
for $n\leq 3000$ using 0.2-1 billion pseudorandom Gaussian samples. His result
suggest that, for the median absolute deviation, finite sample bias correction
is required to ensure a precision of three decimal places when the sample size
is smaller than 2000. This highlights the importance of finite sample bias
correction. However, since different correction factors are required for
different parametric assumptions, the computational cost of addressing all
possible cases in the real world becomes significant, especially for complex
models.

In addition to computational challenges, there exists an inherent difficulty
in dealing with randomness. The theory of probability provides a framework for
modeling and understanding random phenomena. However, the practical
implementation of these models can be challenging, as discussed, and their
complexity greatly hinders our comprehension. The quality of randomness can
significantly impact the validity of simulation results, and a deeper
understanding of randomness may offer a more effective and cost-efficient
solution. The purpose of this article is to demonstrate that the finite sample
structure of uniform random variables can be decomposed using a few well-
designed sequences with high accuracy. Furthermore, we show that the
computational cost of Monte Carlo study can be dramatically improved by
obtaining sets of sequences that are consistent with multiple parametric
distributions respectively for sample central moments.

Figure 1: The frequency histograms of pseudo-random sequences on the interval
[0,1] with size 80.

## Decomposing the Finite Sample Structure of Uniform Distribution

Any continuous distribution can be linked to the uniform distribution on the
interval [0, 1] through its quantile function. This fundamental concept in
Monte Carlo study implies that understanding the finite sample structure of
uniform random variables can be leveraged to understand the finite sample
structure of any other continuous random variable through the quantile
transform. The Glivenko–Cantelli theorem (9, 10) ensures the almost-sure
convergence of the empirical distribution function to the true distribution
function. However, the individual empirical distribution often deviates
significantly from the asymptotic distribution even when the sample size is
not small (Figure 1, sample size is 80), which cause finite sample biases and
variance of common estimators. Let $\mu$, $\mu_{2}$, $\ldots$,
$\mu_{\mathbf{k}}$ denote the first $\mathbf{k}$ central moments of a
probability distribution. According to the unbiased sample central moment (1),
the expected value of the sample central moment,
$m_{\mathbf{k}}=\frac{1}{n}\sum_{{\mathbf{k}}=1}^{n}\left(x_{\mathbf{k}}-\bar{x}\right)^{\mathbf{k}}$,
can be deduced, denoted as $E[m_{\mathbf{k}}]$. Let
$S=\\{sequence[i]|i\in\mathbb{N}\\}$ be a set of number sequences ranging from
0 to 1, where $sequence[i]$ represents the $i$th sequence in the set, and
$\mathbb{N}$ is the set of natural numbers, with $i\leq N$. Transform every
number in $S$ using the quantile function of a parametric distribution, $PD$.
The transformed sequences can be denoted as $S_{PD}$. Denote the set of the
$\mathbf{k}$th sample central moments for these transformed sequences as
$M_{\mathbf{k}}=\\{m_{\mathbf{k},i}|i\in\mathbb{N}\\}$. $S$ is consistent with
$PD$ for all $m_{\mathbf{k}}$ when $\mathbf{k}\leq k$, if and only if the
following system of linear equations is consistent,
$\begin{cases}m_{1,1}w_{1}+\ldots+m_{1,i}w_{i}+\ldots+m_{1,N}w_{N}=E[m_{\mathbf{1}}]\\\
\ldots\\\
m_{{\mathbf{k}},1}w_{1}+\ldots+m_{{\mathbf{k}},i}w_{i}+\ldots+m_{{\mathbf{k}},N}w_{N}=E[m_{\mathbf{{\mathbf{k}}}}]\\\
\ldots\\\ m_{k,1}w_{1}+\ldots+m_{k,i}w_{i}+\ldots+m_{k,N}w_{N}=E[m_{k}]\\\
w_{1}+\ldots+w_{i}+\ldots+w_{N}=1\end{cases}$, where $w_{1}$, $\ldots$,
$w_{i}$, $\ldots$, $w_{N}$ are the unknowns of the system, with $N\geq k+1$.
$w_{1}$, $\ldots$, $w_{i}$, $\ldots$, $w_{N}$ can be determined using a
typical constraint optimization algorithm. The Monte Carlo study can be seen
as a special case when $w_{1}=\ldots=w_{i}=\ldots=w_{N}$, and the sequences in
$S$ are all random number sequences. The strong law of large numbers (proven
by Kolmogorov in 1933) (11) ensures that in this case, when the number of
sequences $N\to\infty$ or when the sample size $n\to\infty$, the above system
of linear equations is always consistent. Another trivial but important
condition is introduced in the following theorem.

######  Theorem 0.0.1.

For any set of sequences, there is always a probability distribution that it
is consistent with.

###### Proof.

Since a sequence can be seen as a discreet probability distribution, the
conclusion is trivial if assigning one weight as 1 and other weights as zeros.
∎

Figure 2: A. The first four sample central moments for the Gaussian
distribution are plotted over a sample size ranging from 5 to 100. The red
lines represent the expected values, while the blue lines depict the values
estimated from the arithmetic sequences. B. The histograms of different beta-
sequences, their self-mixtures, and mixtures with arithmetic sequences.

Low-discrepancy sequences are commonly used as a replacement of uniformly
distributed random numbers to reduce computational cost. When considering a
sequence to approximate the structure of uniform random variables, the most
natural choice is the arithmetic sequence, denoted as
$\\{x_{i}\\}_{i=1}^{n}=\left\\{\frac{i}{n+1}\right\\}_{i=1}^{n}$. As
$n\to\infty$, the arithmetic sequence towards the continuous uniform
distribution. However, the arithmetic central moments estimated from the
arithmetic sequence for the Gaussian distribution differ significantly from
their expected values (Figure 2A). The arithmetic sequence lacks the
variability of true random samples which produce additional biases for even
order moments. The beta distribution is defined on the interval (0, 1) in
terms of two shape parameters, denoted by $\alpha$ and $\beta$. When
$\alpha=\beta$, the beta distribution is symmetric. To better replicate the
features of uniform random variables, we introduced beta distributions with a
variety of parameters. The arithmetic sequences were transformed by the
quantile functions of these beta distributions to form beta-sequences,
resulting in sequences that are U-shape ($\alpha=\beta=0.547$), left-skewed
($\alpha=46.761$, $\beta=20.108$), right-skewed ($\alpha=20.108$,
$\beta=46.761$), monotonic decreasing ($\alpha=0.478$, $\beta=38.53$),
monotonic increasing ($\alpha=38.53$, $\beta=0.478$), their left-skewed self-
mixtures ($\alpha=\beta=0.369$, $\alpha=\beta=18.933$), their right-skewed
self-mixtures ($\alpha=\beta=0.369$, $\alpha=\beta=18.933$), their left-skewed
mixture with the arithmetic sequence ($\alpha=\beta=0.328$), their right-
skewed mixture with the arithmetic sequence ($\alpha=\beta=0.328$) (Figure
2B). Besides beta-sequences with a U-shape, other sequences are paired by
symmetry so additional constraints is set to ensure equal weight for each
pair. Besides these 9 sequences and arithmetic sequences, a pseudo-random
sequence is introduced to further approximate the structure and avoid
inconsistent scenarios. Finally, a complement sequence is introduced which if
combining all the sequences with corresponding weights, the overall sequence
is nearly uniform.

Figure 3: The first plot shows the weights assigned to different sequences as
the sample size increases. The second plot depicts the sample standard
deviations estimated from random, beta-arith-random, 12 designed, and
arithmetic sequences and compares them to the true values. The numbers of
random, betaU-arith-random, and 12 designed sequences were both 120 in total.

## Estimating Finite Sample Bias from Calibrated Sequences

The most surprising result in this article is that, by carefully
selecting/designing sequences in $S$, even when $N$ and $n$ are very small,
e.g., less than 20, the above system of linear equations can still be
consistent, while the weight assigns to the random and complement sequences
are extremely small (<0.02 on average). Using just 12 sequences, when $n=10$,
the constraint optimization algorithm can assign weights to all these
sequences with errors less than $10^{-10}$, when $k\leq 4$. This means that
technically, these sequences are consistent with the Gaussian distribution for
the first four moments. More importantly, in the case of Gaussian
distirbution, the findings suggest the arithmetic sequence and beta sequence
with a U-shape accounts for more than 70% of the finite sample properties of
uniform random variables, while monotonic beta, beta-beta mixed, skewed beta
distributions each contribute about 2-10% (Figure 3). As the sample size
grows, as expected, the weight of the arithmetic sequence increases and
dominants while the weights of other sequences gradually decrease. However,
the beta-sequence with a U-shape still holds about 10% weight even when the
sample size is 100 (Figure 3).

The obtained weights can be used to estimate the finite sample behaviour of
other related estimators, such as the standard deviation for the Gaussian
distribution. We found that by using the 12 well-designed sequences, the
estimation of finite sample bias is much better than the arithmetic sequence
(Figure 3), but the accuracy is still poor. The RMSE is 0.0274 after repeated
10 times to reduce the variance caused by the random sequences, higher than
that of the Monte Carlo study with the same size of sequences, which is
0.0127. To further increase accuracy, we adopted a stochastic method. Since
the arithmetic and beta sequence with a U-shape accounts for most finite
sample properties, we preserve these two sequences and then pseudo-randomly
generated ten sequences to form another 12 sequences. Their efficacy in
approximating the finite sample structure of uniform random variables was
evaluated by solving the above system of linear equations for the first four
moments. Sequences that met the predetermined accuracy threshold (error less
than $10^{-10}$) were retained, while those that did not meet the requirement
were discarded in favor of a new set. Upon identifying enough qualified sets,
these sets were applied to assess the finite sample biases or variances in
other estimators for the Gaussian distribution. The outcomes indicate that
using merely 10 sets of sequences, totaling 120 sequences, which can be
executed on a standard PC in a negligible amount of time, can achieve a
accuracy of approximately 0.005 (root mean square error, RMSE) for the finite
sample bias of standard deviation. In contrast, the RMSE is about 0.012 if
using classic Monte Carlo methods with the same size of sequences.

Table 1: The root mean square error of using different kinds of sequenses to
estimate the finite sample behaviour of standard deviation for the Gaussian
distribution

Bias-sd-G | Random 10S | Arithmetic | 12 Designed 10S | BAR-G 10S | BAR-G 20S | BAR-G 30S | Random 50S | BAR-G 50S | BAR-5D 50S
---|---|---|---|---|---|---|---|---|---
RMSE | 0.0129 | 0.0736 | 0.0274 | 0.0051 | 0.005 | 0.0047 | 0.0044 | 0.0049 | 0.0024

Variance-sd-G | Random 10S | 12 Designed 10S | BAR-G 10S | BAR-G 20S | BAR-G 30S | Random 50S | BAR-G 50S | BAR-5D 50S
---|---|---|---|---|---|---|---|---
RMSE | 0.0085 | 0.1342 | 0.0350 | 0.0350 | 0.0340 | 0.0032 | 0.0341 | 0.0307

Bias-median-E | Random 10S | Arithmetic | BAR-E 10S | BAR-E 20S | BAR-E 30S | Random 50S | BAR-E 50S | BAR-5D 50S
---|---|---|---|---|---|---|---|---
RMSE | 0.0195 | 0.0213 | 0.0112 | 0.0079 | 0.0073 | 0.0074 | 0.0070 | 0.0071

S: set; sd: standard deviation; G: Gaussian distribution; E: Exopnential
distribution; 5D: five two-parametric distributions.

There are still limitations with these ten sets of betaU-arith-random (BAR)
sequences. 1, the obtained results, although much better than the 12 well-
designed sequences and Monte Carlo methods, are still constantly biased
(Figure 3). 2, the accuracy cannot be further improved by simply increasing
the sets of sequences (Table 1). Theorem 0.0.1 indicates that if finding sets
of sequences that are consistent for other distributions, as the kinds of
distributions grow, the combined sets of sequences will approach true
randomness. This suggests another way to further improve the accuracy.

Here, we calibrate 30 sets of sequences for the Weibull ($k=2$, $k=5$), gamma
($k=1$), lognormal ($\sigma=0.25$, $\sigma=0.5$), Pareto ($\alpha=7$,
$\alpha=10$, $\alpha=15$), and generalized Gaussian distributions ($\beta=2$,
$\beta=4$), we found that, by combing these 360 sequences with 20 sets of
sequences calibrated from the Gaussian distribution, the accuracy can be reach
0.0024 (RMSE) for the finite sample bias of standard deviation in the Gaussian
distribution. In contrast, the RMSE is about 0.0049 in classic Monte Carlo
methods with the same size of sequences (Table 1).

Besides the standard deviation, theoretically, this method can be used for any
estimator, another example we provided here is the median for the exponential
distribution. Besides the calibration to the Gaussian distribution changed to
the exponential distribution, other procedures are the same. The results show
similar performance as the standard deviation for the Gaussian distribution
when the number of sequences is 120, indicating the universality of this
approach (Figure 4, Table 1).

Figure 4: The first plot shows the estimations of the standard errors of
standard deviation for the Gaussian distribution by using different sequences
as the sample size increases. The second plot depicts the sample median
estimated from random, beta-arith-random, and arithmetic sequences and
compares them to the true values. The numbers of random and betaU-arith-random
sequences were both 120 in total.

## Variance

The calibrated sequences can also be used to estimate the variance of sample
standard deviation for the Gaussian distribution (Figure 4, Table 1). However,
the accuracy is much lower than the estimation of finite sample bias and the
Monte Carlo approach. When considering the variance of median for the
exponential distribution, there is another concern. As one of the fundamental
theorems in statistics, the central limit theorem declares that the standard
deviation of the limiting form of the sampling distribution of the sample mean
is $\frac{\sigma}{\sqrt{n}}$. The principle, asymptotic normality, was later
applied to the sampling distributions of robust location estimators (12, 13,
14, 15, 16, 17, 18, 19, 20, 21). Daniell (1920) stated (13) that comparing the
efficiencies of various kinds of estimators is useless unless they all tend to
coincide asymptotically. However, the median and mean do not coincide
asymptotically for the exponential distribution. Bickel and Lehmann, in 1976
(19, 20), argued that meaningful comparisons of the efficiencies of various
kinds of location estimators can be accomplished by studying their
standardized variances, asymptotic variances, and efficiency bounds.
Standardized variance,
$\frac{\text{Var}\left(\hat{\theta}\right)}{\theta^{2}}$, allows the use of
simulation studies or empirical data to compare the variances of estimators of
distinct parameters. However, a limitation of this approach is the inverse
square dependence of the standardized variance on $\theta$. If
$\text{Var}\left(\hat{\theta}_{1}\right)=\text{Var}\left(\hat{\theta}_{2}\right)$,
but $\theta_{1}$ is close to zero and $\theta_{2}$ is relatively large, their
standardized variances will still differ dramatically. Here, the scaled
standard error (SSE) is proposed as a method for estimating the variances of
estimators measuring the same attribute, offering a standard error more
comparable to that of the sample mean and much less influenced by the
magnitude of $\theta$.

######  Definition 0.0.1 (Scaled standard error).

Let $\mathcal{M}_{s_{i}s_{j}}\in\mathbb{R}^{i\times j}$ denote the sample-by-
statistics matrix, i.e., the first column corresponds to $\widehat{\theta}$,
which is the mean or a $U$-central moment measuring the same attribute of the
distribution as the other columns, the second to the $j$th column correspond
to $j-1$ statistics required to scale, ${\widehat{\theta_{r_{1}}}}$,
${\widehat{\theta_{r_{2}}}}$, $\ldots$, ${\widehat{\theta_{r_{j-1}}}}$. Then,
the scaling factor
${\mathcal{S}=\left[1,\frac{\bar{\theta_{r_{1}}}}{\bar{\theta_{m}}},\frac{\bar{\theta_{r_{2}}}}{\bar{\theta_{m}}},\ldots,\frac{\bar{\theta_{r_{j-1}}}}{\bar{\theta_{m}}}\right]}^{T}$
is a $j\times 1$ matrix, which $\bar{\theta}$ is the mean of the column of
$\mathcal{M}_{s_{i}s_{j}}$. The normalized matrix is
$\mathcal{M}_{s_{i}s_{j}}^{N}=\mathcal{M}_{s_{i}s_{j}}\mathcal{S}$. The SSEs
are the unbiased standard deviations of the corresponding columns of
$\mathcal{M}_{s_{i}s_{j}}^{N}$.

The $U$-central moment (the central moment estimated by using $U$-statistics)
is essentially the mean of the central moment kernel distribution, so its
standard error should be generally close to
$\frac{\sigma_{\mathbf{k}m}}{\sqrt{n}}$, although not exactly since the kernel
distribution is not i.i.d., where $\sigma_{\mathbf{k}m}$ is the asymptotic
standard deviation of the central moment kernel distribution. If the
statistics of interest coincide asymptotically, then the standard errors
should still be used, e.g, for symmetric location estimators and odd ordinal
central moments for the symmetric distributions, since the scaled standard
error will be too sensitive to small changes when they are zero. The scaled
standard error of median is higher than that of the mean for the exponential
distribution, while their standard errors are nearly identical (Figure 5).

Figure 5: The standard errors and scale standard errors of sample median and
sample mean with respect to the sample size.

## Data and Software Availability

All data are included in the brief report. All codes have been deposited in
Zenodo. Please include your acknowledgments here, set in a single paragraph.
Please do not include any acknowledgments in the Supporting Information, or
anywhere else in the manuscript.

## References

  * (1) H Cramér, Mathematical methods of statistics.  (Princeton university press) Vol. 43, (1999).
  * (2) I Gerlovina, AE Hubbard, Computer algebra and algorithms for unbiased moment estimation of arbitrary order.  Cogent mathematics & statistics 6, 1701917 (2019).
  * (3) WH Holtzman, The unbiased estimate of the population variance and standard deviation.  The American Journal of Psychology 63, 615–617 (1950).
  * (4) HA David, HN Nagaraja, Order statistics, third edition in Wiley Series in Probability and Statistics.  (2003).
  * (5) H Nagatsuka, H Kawakami, T Kamakura, H Yamamoto, The exact finite-sample distribution of the median absolute deviation about the median of continuous random variables.  Statistics & Probability Letters 83, 999–1005 (2013).
  * (6) C Croux, PJ Rousseeuw, Time-efficient algorithms for two highly robust estimators of scale.  (1992).
  * (7) K Hayes, Finite-sample bias-correction factors for the median absolute deviation.  Communications in Statistics - Simulation and Computation 43, 2205–2212 (2014).
  * (8) A Akinshin, Finite-sample bias-correction factors for the median absolute deviation based on the harrell-davis quantile estimator and its trimmed modification (2022).
  * (9) V Glivenko, Sulla determinazione empirica delle leggi di probabilita.  Gion. Ist. Ital. Attauri. 4, 92–99 (1933).
  * (10) FP Cantelli, Sulla determinazione empirica delle leggi di probabilita.  Giorn. Ist. Ital. Attuari 4 (1933).
  * (11) A Kolmogorov, Sulla determinazione empirica di una lgge di distribuzione.  Inst. Ital. Attuari, Giorn. 4, 83–91 (1933).
  * (12) S Newcomb, A generalized theory of the combination of observations so as to obtain the best result.  American journal of Mathematics 8, 343–366 (1886).
  * (13) P Daniell, Observations weighted according to order.  American Journal of Mathematics 42, 222–236 (1920).
  * (14) F Mosteller, On some useful" inefficient" statistics.  The Annals of Mathematical Statistics 17, 377–408 (1946).
  * (15) CR Rao, Advanced statistical methods in biometric research. (Wiley), (1952).
  * (16) PJ Bickel, Some contributions to the theory of order statistics in Proc. Fifth Berkeley Sympos. Math. Statist. and Probability.  Vol. 1, pp. 575–591 (1967).
  * (17) H Chernoff, JL Gastwirth, MV Johns, Asymptotic distribution of linear combinations of functions of order statistics with applications to estimation.  The Annals of Mathematical Statistics 38, 52–72 (1967).
  * (18) L LeCam, On the assumptions used to prove asymptotic normality of maximum likelihood estimates.  The Annals of Mathematical Statistics 41, 802–828 (1970).
  * (19) P Bickel, E Lehmann, Descriptive statistics for nonparametric models i. introduction in Selected Works of EL Lehmann.  (Springer), pp. 465–471 (2012).
  * (20) PJ Bickel, EL Lehmann, Descriptive statistics for nonparametric models ii. location in selected works of EL Lehmann.  (Springer), pp. 473–497 (2012).
  * (21) P Janssen, R Serfling, N Veraverbeke, Asymptotic normality for a general class of statistical functions and applications to measures of spread.  The Annals of Statistics 12, 1369–1379 (1984).