# Reconstructing almost all of a point set in $\mathbb{R}^{d}$ from randomly
revealed pairwise distances

Douglas Barnes , Jan Petr∗, Julien Portier∗, Benedict Randall Shaw∗, Alan
Sergeev∗ {db875, jp895, jp899, bwr26<EMAIL_ADDRESS>Department of Pure
Mathematics and Mathematical Statistics (DPMMS), University of Cambridge,
Wilberforce Road, Cambridge, CB3 0WA, United Kingdom

###### Abstract

Let $V$ be a set of $n$ points in $\mathbb{R}^{d}$, and suppose that the
distance between each pair of points is revealed independently with
probability $p$. We study when this information is sufficient to reconstruct
large subsets of $V$, up to isometry.

Strong results for $d=1$ have been obtained by Girão, Illingworth, Michel,
Powierski, and Scott. In this paper, we investigate higher dimensions, and
show that if $p>n^{-2/(d+4)}$, then we can reconstruct almost all of $V$ up to
isometry, with high probability. We do this by relating it to a polluted graph
bootstrap percolation result, for which we adapt the methods of Balogh,
Bollobás, and Morris.

##  1 Introduction

Let $V$ be a set of $n$ points in $\mathbb{R}^{d}$, and suppose that all we
know about $V$ are the distances between each pair in $V$ independently with
probability $p$—that is to say, the distance between points $x$ and $y$ is
revealed to us whenever $\\{x,y\\}\in\mathcal{P}\subset{V}^{(2)}$, for
$(V,\mathcal{P})$ distributed as $G(n,p)$, the Erdős-Rényi random graph. We
want to determine the range of $p$ for which we can reconstruct $V$, or
alternatively some large $Y\subseteq V$, where reconstruction of a set here
means determining the positions of its points up to isometry. A set
$Y\subseteq V$ whose position can be determined up to isometry given
$(V,\mathcal{P})$ will be called _reconstructible_.

Recently, Benjamini and Tzalik [3] proved the following result.

######  Theorem 1.1.

There exists an absolute constant $C$ such that if $V$ is a set of $n$ points
in $\mathbb{R}$ and each pairwise distance of points in $V$ is revealed with
probability $p=\frac{C\ln n}{n}$ independently, then $V$ is reconstructible
w.h.p.

Girão, Illingworth, Michel, Powierski, and Scott [11] improved upon this
result, proving a sharp threshold for reconstructing the whole of $V$.

######  Theorem 1.2.

Let $V$ be a set of $n$ points in $\mathbb{R}$. Suppose the graph
$G=(V,\mathcal{P})$ of revealed pairwise distances is distributed as $G(n,p)$.
Then the following hold w.h.p.

  1. (a)

If $p\leq\frac{\log n+\log\log n-\omega(1)}{n}$, then $V$ is not
reconstructible.

  2. (b)

If $p\geq\frac{\log n+\log\log n+\omega(1)}{n}$, then $V$ is reconstructible.

Moreover, the authors of [11] asked whether similar results could be proved
for sets lying in $\mathbb{R}^{d}$ for $d\geq 2$. They observed that we cannot
expect to reconstruct the whole of $V$ for non-trivial $p$. Indeed, for an
embedding where $n-2$ points lie in a hyperplane and the other two points
$u,v$ do not, the whole of $V$ can only be reconstructed if the distance
between $u$ and $v$ is revealed, as otherwise each of $u,v$ could be on any of
the two sides of the hyperplane, as shown in Figure 1 for $d=2$.

$x_{1}$$x_{2}$$x_{3}$$\cdots$$x_{n-2}$$u$$v$$x_{1}$$\cdots$$x_{n-2}$$u$$v$
Figure 1: These two configurations differ only in the distance marked in red.

Therefore, Girão, Illingworth, Michel, Powierski, and Scott asked the
following question.

######  Question 1.3.

Let $V$ be a set of $n$ points in $\mathbb{R}^{d}$. For which range of $p$ are
we able to reconstruct $\Omega(n)$ points of $V$ w.h.p.?

In the one-dimensional case $d=1$, they proved the following result.

######  Theorem 1.4.

Let $V$ be a set of $n$ points in $\mathbb{R}$. Suppose the graph
$G=(V,\mathcal{P})$ of revealed pairwise distances is distributed as $G(n,p)$.

  1. (a)

If $p\geq 42/n$, then there is a reconstructible set of size $\Omega(n)$
w.h.p.

  2. (b)

If $pn\to\infty$, then there is a reconstructible set of size $n-o(n)$ w.h.p.

Note that for $p\leq\frac{1}{n}$, a graph sampled as $G(n,p)$ does not have
any connected component of linear size w.h.p., and so the previous result
gives a weak threshold about reconstructibility of a linear size subset.

Our main contribution in this paper is the first non-trivial upper bound
towards an answer to 1.3.

######  Theorem 1.5.

Let $d\geq 1$ and $V$ be a set of $n$ points in $\mathbb{R}^{d}$. Suppose the
graph $G=(V,\mathcal{P})$ of revealed pairwise distances is distributed as
$G(n,p)$. Then for $p\gg q(n,d)$, we can reconstruct the configuration of
$n-o(n)$ vertices w.h.p., where

$q(n,d):=n^{-1/\eta(d)+o(1)},$ $\eta(d):=\frac{{{d+3}\choose
2}-2}{(d+3)-2}=\frac{d+4}{2}-\frac{1}{d+1}.$

Although Benjamini and Tzalik [3] were the first to study those problems in
this setting, a long line of research has already been conducted in the
generic setting. A set of vertices $V$ in $\mathbb{R}^{d}$ is said to be
_generic_ if the $d|V|$ coordinates of the vertices are algebraically
independent over $\mathbb{Q}$. A graph $(V,\mathcal{P})$ is _globally rigid in
$\mathbb{R}^{d}$_ if it has some generic embedding in $\mathbb{R}^{d}$ which
is reconstructible from its edge lengths, i.e. the distances $uv$ such that
$uv\in\mathcal{P}$. It has been shown [6, 12] that a graph is globally rigid
if and only if all of its generic embeddings are reconstructible from their
edge lengths.

The global rigidity of random graphs has attracted significant attention. For
instance, Lew, Nevo, Peled and Raz [18] proved that $G(n,p)$ is globally
$d$-rigid w.h.p. exactly when it has minimum degree $d+1$, which has a sharp
threshold at $p=\frac{\log{n}+d\log{\log{n}}}{n}$. We would like to remark
that the restriction to generic embeddings in the definition of global
rigidity is a significant weakening. For example, it is folklore (see for
example Thm 63.2.7 in [16]) that a graph is globally rigid in $\mathbb{R}$ if
and only if it is $2$-connected, which is not the case for reconstructing
arbitrary point sets. Indeed, Girão, Illingworth, Michel, Powierski, and Scott
showed [11] that there are graphs with arbitrarily high connectivity which can
be embedded in $\mathbb{R}$ in such a way that their vertex sets cannot be
reconstructed from their edge lengths.

We close this introduction by noting that the scope of reconstruction problems
is quite broad. For example, Lemke, Skiena and Smith [17] considered the
problem of reconstructing a point set based on pairwise distances, where the
correspondence between distances and the pairs of points to which they belong
is not known. As mentioned in their paper, this problem has natural
applications in the worlds of X-ray crystallography and site mapping of DNA.
On the other hand, the problems of reconstructing a point set based on
labelled distances have applications in network localisation [9] and molecular
conformation [14].

###  1.1 Proof outline

In this paper, we by default conceive of $\mathbb{R}^{m}$ as an affine space,
in that the origin does not play a special role. A _subspace_ will mean an
affine subspace. Given $d$, we call a multiset $X$ of $d+1$ points _$d$
-dependent_ if there is a subspace of dimension $d-1$ that contains $X$. If
there is no such subspace, we will say that $X$ is _$d$ -independent_. Any
multiset of size $1$ is $0$-independent.

The main idea of our proof is based on the following observation, proved in a
stronger form as Corollary 2.3.

######  Observation 1.6.

Given any $d+3$ points $u,v,x_{1},x_{2},...x_{d+1}$ in $\mathbb{R}^{d}$ with
all pairwise distances known except $uv$, we can reconstruct the distance $uv$
unless $\\{x_{i}|i\in[d+1]\\}$ is $d$-dependent.

Therefore if we knew that $V$ was in general position, i.e. with no set of
$d+1$ points being $d$-dependent, then repeatedly applying 1.6 would allow us
to follow a $K_{d+3}$-percolation, defined in Section 2, on the graph of known
edges. We would then immediately deduce Theorem 1.5 by Theorem 2.1, a general
result about graph bootstrap percolation by Balogh, Bollobás, and Morris. For
a set of points $V$ not compulsory in general position, we still want to apply
a $K_{d+3}$-bootstrap percolation on the graph of known distances, but only
reconstructing $uv$ from copies of $K_{d+3}$ such that
$V(K_{d+3})\setminus\\{u,v\\}$ is $d$-independent, so that 1.6 applies.

To account for $d$-dependent sets, we will work with a _polluted graph
bootstrap percolation_ , defined in Section 3, which is similar to the
classical graph bootstrap percolation, except that there is a set of
hyperedges $E(\mathcal{H})$ on which the bootstrap percolation cannot spread.
We then show that Theorem 2.1 essentially still holds for the same range of
$p$ for a polluted graph bootstrap percolation if the set of hyperedges
$E(\mathcal{H})$ is small enough, see Theorem 3.1. As the hyperedge set, we
will take precisely the $d$-dependent subsets of $V$ of size $d+1$. Then we
can deduce our main result, Theorem 1.5, from our polluted bootstrap
percolation result, Theorem 3.1, provided $|E(\mathcal{H})|$ is small enough
in term of $n$. In the general case, $|E(\mathcal{H})|$ is not always
sufficiently small to apply Theorem 3.1, and consequently we use Corollary 4.2
to find a reasonably large subset of $V$ where we can apply Theorem 3.1.

More precisely, we show in Corollary 4.2 that for every multiset of points
$V$, there exists a subspace $\Pi$ of dimension $d^{\prime}$ which contains
reasonably many points of $V$, and such that most families of $\Pi\cap V$ of
size $d^{\prime}+1$ are $d^{\prime}$-independent. The particular case where
$d^{\prime}=0$ needs to be taken care of separately, but in the general case
where $d^{\prime}\geq 1$, we can indeed reconstruct the pairwise distances
between almost all of $\Pi\cap V$ by using our polluted graph bootstrap
percolation result in Theorem 3.1. We then show that we can reconstruct the
projections of almost all of $V$ onto the subspace $\Pi$ in Lemma 4.3.
Combining all of the above results, we obtain Lemma 4.4, which enables us to
reduce the problem to one with $V$ projected onto $\Pi^{\perp}$ as its point
set, reducing the dimension of the problem by at least $1$. By sprinkling and
iterating this at most $d$ times, we are able to deduce Theorem 1.5.

The rest of the paper is structured as follows. In Section 2 we introduce some
tools. In Section 3 we prove our polluted graph bootstrap percolation result.
In Section 4 we proceed to the proof of our main result. Finally, in Section
5, we give a few concluding remarks.

##  2 Tools from geometry and graph theory

Graph bootstrap percolation processes were introduced over 40 years ago by
Bollobás [4], as a particular case of cellular automaton, introduced by von
Neumann [19] after a suggestion by Ulam [20]. For a given graph $H$, the
$H$-_bootstrap percolation_ is defined as follows. Given an initial set of
edges $G\subset E\left(K_{n}\right)$, and graph $H$, we set $G_{0}=G$, and
thereafter define

$G_{t+1}=G_{t}\cup\left\\{e\in E\left(K_{n}\right):\exists K\cong H\mbox{ s.t.
}e\in E(K)\subset G_{t}\cup\\{e\\}\right\\}.$

Then $\langle G\rangle_{H}=\cup_{t}G_{t}$ is the closure of $G$ under this
process. This is to say, $\langle G\rangle_{H}$ is the graph obtained by
adding an edge wherever doing so would create a new copy of $H$, and repeating
this on the resulting graph until no new edges are added. A graph $G$ is said
to $H$-_percolate_ if $\langle G\rangle_{H}=E(K_{n})$.

$G=G_{0}$$G_{1}$$G_{2}$$G_{3}=\langle G\rangle_{K_{4}}=K_{6}$ Figure 2: The
process of $K_{4}$-bootstrap percolation for the graph $G_{0}$, which
$K_{4}$-percolates.

In [1], Balogh, Bollobás, and Morris studied the critical threshold for
$G(n,p)$ to $H$-percolate. The critical threshold is defined as

$p_{c}(n,H):=\inf\left\\{p:\mathbb{P}\left(G\sim G(n,p)\text{
}H\text{-percolates}\right)\geq\frac{1}{2}\right\\}.$

Balogh, Bollobás, and Morris determined the critical threshold for
$K_{d+3}$-percolation up to a polylogarithmic factor [1].

######  Theorem 2.1.

For $d\geq 1$ and sufficiently large $n$, there exists $c=c(d)>0$ such that

$\frac{n^{-1/\eta(d)}}{c\log{n}}\leq p_{c}\left(n,K_{d+3}\right)\leq
n^{-1/\eta(d)}\log n.$ (1)

They further remarked [1] that by a general result of Bollobás and Thomason
[5] this is a threshold, i.e. for $p\gg p_{c}(n,H)$, the probability of
percolation is $1-o(1)$, and for $p\ll p_{c}(n,H)$, the probability of
percolation is $o(1)$. We will not use Theorem 2.1 per se, but we will use
their proof method to deduce our polluted graph bootstrap percolation result
in Theorem 3.1.

We will need the two following geometrical results. Their proofs are quite
classical, and therefore deferred to Appendix A.

######  Lemma 2.2.

Given all pairwise distances within some
$S=\\{v_{1},\dots,v_{r}\\}\subset\mathbb{R}^{d}$, we can reconstruct the
configuration of $S$ up to isometry.

######  Corollary 2.3.

Suppose a multiset $R$ of $d+3$ points of $\mathbb{R}^{m}$ ($m\geq d$) lies in
a $d$-dimensional subspace (but we do not necessarily know this yet). Then,
given all pairwise distances within $R$ except some pair $uv$, we can identify
whether $Q=R\setminus\\{u,v\\}$ is $d$-independent. If so, we can also
determine the distance $uv$.

We will also employ a classical supersaturation result extending Turán’s
theorem due to Erdős and Simonovits [7].

######  Theorem 2.4.

If $\ell\geq 3$ and $\gamma>\frac{\ell-2}{2(\ell-1)}$, then every graph on $n$
vertices and at least $\gamma n^{2}$ edges contains
$\Omega_{\gamma}(n^{\ell})$ many $\ell$-cliques.

Additionally, we will make use of one more classical result, on the
connectivity of random graphs due to Erdős and Rényi [8] (see also Thm 4.1 of
[10] for a more modern reference).

######  Theorem 2.5.

Let $\varepsilon>0$ and $p\geq(1+\varepsilon)\frac{\log n}{n}$. Then w.h.p.
the random graph $G(n,p)$ is connected.

##  3 Polluted graph bootstrap percolation

We define $K_{d+3}$-percolation with pollution $\mathscr{P}\subset X^{(d+1)}$,
or $\mathscr{P}$-polluted $K_{d+3}$-percolation as follows: starting with a
graph $G$, we repeatedly add to the graph any edge $e=uv$ where adding $e$
would create another copy of $K_{d+3}$ in the graph, on vertices
$Q\cup\\{u,v\\}$ for some $Q\in X^{(d+1)}\setminus\mathscr{P}$. More formally,
given an initial set of edges $G\subset X^{(2)}$, we set $G_{0}=G$, and
thereafter define

$G_{t+1}=G_{t}\cup\left\\{e=uv\in X^{(2)}:\exists K\cong K_{d+3}\mbox{ s.t.
}e\in E(K)\subset G_{t}\cup\\{e\\}\mbox{ and
}V(K)\setminus\\{u,v\\}\notin\mathscr{P}\right\\}.$

Then $\langle G\rangle^{\mathscr{P}}_{K_{d+3}}=\cup_{t}G_{t}$ is the closure
of $G$ under this process.111Note that our definition of polluted graph
bootstrap percolation is unrelated to the one of bootstrap percolation in a
polluted environment, which was introduced by Gravner and McDonald [13].

Throughout the paper, we let $p_{*}(n,d)=(\frac{\log n}{\log\log
n})^{2/\eta(d)}n^{-1/\eta(d)}$. The main result of this section is the
following.

######  Theorem 3.1.

Let $0<\mu<1$, $\delta>0$ be fixed and $\mathcal{H}$ be a $(d+1)$-uniform
hypergraph on $[n]$ such that $|E(\mathcal{H})|\leq n^{d+\mu}$. Let $G\sim
G(n,p)$ and $G^{\prime}=\langle G\rangle^{\mathcal{H}}_{K_{d+3}}$. If $p\gg
p_{*}(n,d)$, then $G^{\prime}$ contains a clique of size $(1-\delta)n$ w.h.p.

Before proving Theorem 3.1, we introduce a little more notation. Firstly, in
their proof of Theorem 2.1, for $H=K_{d+3}$, the authors of [1] define $H_{r}$
to be the graph obtained as follows: take $H^{(1)},\dots,H^{(r)}$ to be copies
of $H$, and choose edges $e_{1}=u_{1}v_{1},\dots,e_{r}=u_{r}v_{r}$ of $H$ such
that for each $i$, the edges $e_{i},e_{i+1}$ share no endpoints. Then for each
$i=2,\dots,r$, remove the edge $e_{i}$ from $H^{(i-1)},H^{(i)}$, and identify
its endpoints in $H^{(i-1)}$ with those in $H^{(i)}$. Finally, remove $e_{1}$
from $H^{(1)}$. The edge $e_{1}$ is said to be the root of $H_{r}$, written
$\operatorname{root}(H_{r})=e_{1}$. Additionally, for each $i\leq r$, we call
$V(H^{(i)})\setminus\\{u_{i},v_{i}\\}$ the _base_ of $H^{(i)}$.

$e_{1}$$e_{2}$$e_{3}$ Figure 3: $H_{3}$, for $H=K_{6}$. Removed edges are
shown in dashed red.

We say $H_{r}$ is $\mathcal{H}$-clean if for each $1\leq i\leq r$,
$V\left(H^{(i)}\right)\setminus\\{u_{i},v_{i}\\}\notin\mathcal{H}$. Notice
that in this case, by Corollary 2.3 we can percolate with pollution
$\mathcal{H}$ on $H_{r}$ to obtain edges $e_{r},\dots,e_{1}$ in that order.
Now we define $X_{r}(e)$ to be the number of embeddings of $H_{r}$ in $G\sim
G(n,p)$ rooted at $e$, and $X^{\mathcal{H}}_{r}(e)$ to be the number of
$\mathcal{H}$-clean embeddings of $H_{r}$ in $G$ rooted at $e$. Notice that if
$X^{\mathcal{H}}_{r}(e)>0$, then $e\in\langle
G\rangle^{\mathcal{H}}_{K_{d+3}}$. Note that we are counting different
embeddings of the graph $H_{r}$ as distinct, e.g., a $K_{3}$ contains six
embeddings of a $K_{3}$.

Balogh, Bollobás, and Morris proved [1] the following result as the key lemma
in order to deduce Theorem 2.1.

######  Lemma 3.2.

If $p=p(n),r=r(n),\omega=\omega(n)$ are chosen such that

  1. (a)

$p^{\eta(d)}n\geq(d+3)\omega r,$

  2. (b)

$\omega^{(d+1)r}\geq n,$

  3. (c)

$pn\to\infty$ as $n\to\infty,$ and

  4. (d)

$v(H_{r})^{-2}p^{\eta(d)}n\to\infty$ as $n\to\infty$,

then for $e\in[n]^{(2)}$ and $G\sim G(n,p)$, as $n\to\infty$, we have
$\mathbb{E}\left(X_{r}(e)\right)\to\infty$ and

$\frac{\operatorname{Var}\left(X_{r}(e)\right)}{\mathbb{E}\left(X_{r}(e)\right)^{2}}<\left(\frac{p^{\eta(d)}n}{4v(H_{r})^{2}}-1\right)^{-1}\to
0.$

We prove that under additional conditions, this result holds for
$X^{\mathcal{H}}_{r}(e)$ also.

######  Lemma 3.3.

Let $0<\mu<1$ be fixed such that $|E(\mathcal{H})|\leq n^{d+\mu}$ and suppose
that $p=p(n),r=r(n),\omega=\omega(n)$ meet the conditions of Lemma 3.2, as
well as

  1. (e)

$r(d+1)\leq\frac{1}{2}n$, and

  2. (f)

$rn^{\mu-1}\leq c$ for some constant $c$.

Then there exists a constant $K_{d,c}$ depending only on $d$ and $c$ such that
for $e\in[n]^{(2)}$ and $G\sim G(n,p)$, as $n\to\infty$, we have
$\mathbb{E}\left(X^{\mathcal{H}}_{r}(e)\right)\to\infty$ and

$\dfrac{\operatorname{Var}\left(X^{\mathcal{H}}_{r}(e)\right)}{\mathbb{E}\left(X^{\mathcal{H}}_{r}(e)\right)^{2}}<K_{d,c}\left(\frac{p^{\eta(d)}n}{4v(H_{r})^{2}}-1\right)^{-1}\to
0.$

###### Proof.

Take $T=\left\\{E\left(K\right):K\text{ is an embedding of }H_{r}\text{ rooted
at }e\text{ with vertices in }X\right\\}$, and $T^{\mathcal{H}}\subset T$ to
be $T^{\mathcal{H}}=\left\\{E\left(K\right):K\text{ is a $\mathcal{H}$-clean
embedding of }H_{r}\text{ rooted at }e\text{ with vertices in }X\right\\}$.
Now we can write $X_{r}(e)$ as $\sum_{S\in T}\mathbf{1}\left(S\subset
E\left(G\right)\right)$, and likewise $X^{\mathcal{H}}_{r}(e)=\sum_{S\in
T^{\mathcal{H}}}\mathbf{1}\left(S\subset E\left(G\right)\right)$, from which
we can derive

$\begin{split}\operatorname{Var}\left(X_{r}(e)\right)&{}=\sum_{S_{1},S_{2}\in
T}\Bigl{(}\mathbb{P}\bigl{(}S_{1}\cup S_{2}\subset
E\left(G\bigr{)}\right)-\mathbb{P}\bigl{(}S_{1}\subset
E\left(G\right)\bigr{)}\mathbb{P}\bigl{(}S_{2}\subset
E\left(G\right)\bigr{)}\Bigr{)}\\\ &{}=\sum_{S_{1},S_{2}\in
T}\left(p^{\left|S_{1}\cup S_{2}\right|}-p^{2e\left(H_{r}\right)}\right)\\\
&{}\geq\sum_{S_{1},S_{2}\in T^{\mathcal{H}}}\left(p^{\left|S_{1}\cup
S_{2}\right|}-p^{2e\left(H_{r}\right)}\right)=\operatorname{Var}\left(X^{\mathcal{H}}_{r}(e)\right).\end{split}$

But now
$\mathbb{E}\left(X_{r}(e)\right)=\left|T\right|p^{e\left(H_{r}\right)}$, and
likewise
$\mathbb{E}\left(X^{\mathcal{H}}_{r}(e)\right)=\left|T^{\mathcal{H}}\right|p^{e\left(H_{r}\right)}$.
We choose an element of $T$ by choosing in turn $V(H^{(r)})\setminus
e_{r},V(H^{(r-1)})\setminus e_{r-1},\dots,V(H^{(2)})\setminus
e_{2},V(H^{(1)})\setminus e_{1}$. Note that these are the bases of the
$H^{(i)}$, and that $e_{1}=e$ is already fixed. Thus

$\left|T\right|=\left(\prod_{i=0}^{r-1}{{n-i(d+1)}\choose{d+1}}\right)\left((d+1)!\right)^{r}.$

By a similar counting, making sure that the base of $H^{(i)}$ is never an
element of $E(\mathcal{H})$, we have that

$\left|T^{\mathcal{H}}\right|\geq\left(\prod_{i=0}^{r-1}\left({{n-i(d+1)}\choose{d+1}}-|E(\mathcal{H})|\right)\right)\left((d+1)!\right)^{r}.$

Therefore, using $|E(\mathcal{H})|\leq n^{d+\mu}$, the inequality
${{N}\choose{k}}\geq(\frac{N}{k})^{k}$, and condition (e) we have

$\displaystyle|T^{\mathcal{H}}|$
$\displaystyle\geq|T|\prod_{i=0}^{r-1}\left(1-\frac{n^{d+\mu}}{(\frac{n/2}{d+1})^{d+1}}\right)$
$\displaystyle=|T|\left(1-\frac{(2(d+1))^{d+1}}{n^{1-\mu}}\right)^{r}$

Note that for small enough $x>0$, $(1-x)\geq e^{-2x}$. Thus for large enough
$n$, condition (f) gives

$\frac{\mathbb{E}\left(X^{\mathcal{H}}_{r}(e)\right)}{\mathbb{E}\left(X_{r}(e)\right)}=\frac{\left|T^{\mathcal{H}}\right|}{\left|T\right|}\geq\left(1-\frac{(2(d+1))^{d+1}}{n^{1-\mu}}\right)^{r}\geq
e^{-2(2(d+1))^{d+1}rn^{\mu-1}}\geq e^{-2(2(d+1))^{d+1}c}=K_{d,c}^{-1/2},$

where $K_{d,c}=e^{4(2(d+1))^{d+1}c}$ is a constant. Hence
$\mathbb{E}\left(X^{\mathcal{H}}_{r}(e)\right)\to\infty$, and

$\frac{\operatorname{Var}\left(X^{\mathcal{H}}_{r}(e)\right)}{\mathbb{E}\left(X^{\mathcal{H}}_{r}(e)\right)^{2}}\leq
K_{d,c}\frac{\operatorname{Var}\left(X_{r}(e)\right)}{\mathbb{E}\left(X_{r}(e)\right)^{2}}<K_{d,c}\left(\frac{p^{\eta(d)}n}{4v(H_{r})^{2}}-1\right)^{-1}\to
0$

∎

We now proceed to the proof of Theorem 3.1.

###### Proof of Theorem 3.1..

We may assume that $\delta^{2}(1-2\delta)^{-2}<(2d)^{-1}$. We let $p\gg
p_{*}(n,d)$, $r=\omega=\left\lceil\frac{\log n}{\log\log n}\right\rceil$ and
apply Lemma 3.3. The authors of [1] have already shown that conditions (a) to
(d) are satisfied, and it is clear that the additional conditions (e) and (f)
are also satisfied. It follows by Chebyshev’s inequality that

$\mathbb{P}\left(X^{\mathcal{H}}_{r}(e)=0\right)\leq\frac{\operatorname{Var}\left(X^{\mathcal{H}}_{r}(e)\right)}{\mathbb{E}\left(X^{\mathcal{H}}_{r}(e)\right)^{2}}<K_{d,c}\left(\frac{p^{\eta(d)}n}{4v(H_{r})^{2}}-1\right)^{-1}\to
0.$

Hence, by Markov’s inequality, $G^{\prime}$ has at least
$n^{2}/2-\delta^{2}n^{2}/2$ edges w.h.p. We now show that w.h.p., $G^{\prime}$
contains a clique on $(1-\delta)n$ vertices by combining a similar claim and
its proof from [1] with the classical supersaturation result in Theorem 2.4.

Let $D=\left\\{x\in[n]:d_{G^{\prime}}(x)>(1-\delta)n\right\\}$. Then

$\displaystyle n^{2}-\delta^{2}n^{2}$ $\displaystyle\leq 2|E(G^{\prime})|$
$\displaystyle=\sum_{v\in D}d_{G^{\prime}}(v)+\sum_{v\in
D^{c}}d_{G^{\prime}}(v)$ $\displaystyle\leq|D|n+(n-|D|)(1-\delta)n$
$\displaystyle=|D|\delta n+(1-\delta)n^{2}.$

Rearranging, this gives $|D|\geq(1-\delta)n$.

We now claim that $D$ is a clique for sufficiently large $n$. Suppose for
contradiction that there exist $x,y\in D$ such that there is no edge between
$x$ and $y$ in $G^{\prime}$. Let $n_{*}=\left|N_{G^{\prime}}(x)\cap
N_{G^{\prime}}(y)\right|\geq(1-2\delta)n$, and let $G^{*}$ be the induced
subgraph of $G^{\prime}$ on vertex set $N_{G^{\prime}}(x)\cap
N_{G^{\prime}}(y)$. For sufficiently large $n$ we have

$\displaystyle|E(G^{*})|$
$\displaystyle\geq\binom{n_{*}}{2}-\delta^{2}n^{2}/2$
$\displaystyle\geq\binom{n_{*}}{2}-\delta^{2}(1-2\delta)^{-2}n_{*}^{2}/2$
$\displaystyle\geq\left(\frac{1}{2}-\delta^{2}(1-2\delta)^{-2}\right)n_{*}^{2}.$

Let $\gamma=1/2-\delta^{2}(1-2\delta)^{-2}$. By Theorem 2.4, the graph $G^{*}$
contains $\Omega_{\gamma}(n^{d+1})$ many $(d+1)$-cliques. As
$|E(\mathcal{H})|\leq n^{d+\mu}$, there exists a $(d+1)$-clique in
$N_{G^{\prime}}(x)\cap N_{G^{\prime}}(y)\cap E(\mathcal{H})^{c}$. This is a
contradiction. Hence, $D$ is a clique, which finishes the proof. ∎

##  4 Proof of Theorem 1.5

We start with the following lemma.

######  Lemma 4.1.

Let $0<\mu<1$ and $V$ be a multiset of $n$ points in $\mathbb{R}^{d}$. Then

  * •

either there exists a subspace $\Pi_{d^{\prime}}$ of dimension $0\leq
d^{\prime}\leq d-1$ such that $|V\cap\Pi_{d^{\prime}}|\geq n^{\mu}$, or

  * •

the number of $d$-dependent families of $V$ of size $d+1$ is at most
$dn^{d+\mu}$.

###### Proof.

Suppose that there is no subspace $\Pi_{d^{\prime}}$ of dimension $0\leq
d^{\prime}\leq d-1$ such that $|V\cap\Pi_{d^{\prime}}|\geq n^{\mu}$. Let $I$
be the set of $d$-dependent families of $V$ of size $d+1$, and for each $0\leq
i\leq d-1$, let $I_{i}$ be the set of families of $V$ of size $d+1$ whose
affine span has dimension exactly $i$. We have $I=\cup_{i=0}^{d-1}I_{i}$ and
therefore $|I|=\sum_{i=0}^{d-1}|I_{i}|$. By definition, for each element $S$
of $I_{i}$, there exist $x_{1},\dots,x_{i},x_{i+1}\in S$ such that the
subspace $\Pi_{S}$ spanned by $x_{1},\dots,x_{i},x_{i+1}$ has dimension
exactly $i$, and $S\setminus\\{x_{1},\dots,x_{i+1}\\}$ lies in $\Pi_{S}$. As
we assumed that no subspace $\Pi_{S}$ of dimension $0\leq d^{\prime}\leq d-1$
satisfies $|V\cap\Pi_{S}|\geq n^{\mu}$, it follows that once
$x_{1},\dots,x_{i+1}$ are fixed, there are at most $n^{(d-i)\mu}$
possibilities for $S\setminus\\{x_{1},\dots,x_{i+1}\\}$. Therefore,
$|I_{i}|\leq n^{i+1+(d-i)\mu}$, and consequently
$|I|\leq\sum_{i=0}^{d-1}n^{i+1+(d-i)\mu}\leq dn^{d+\mu}$. ∎

From Lemma 4.1 we deduce the following corollary.

######  Corollary 4.2.

Let $0<\mu<1$ and $V$ be a multiset of $n$ points in $\mathbb{R}^{d}$. Then
there exists a subspace $\Pi_{d^{\prime}}$ of dimension $0\leq d^{\prime}\leq
d$ such that $|V\cap\Pi_{d^{\prime}}|\geq n^{\mu^{d-d^{\prime}}}$ and the
number of $d^{\prime}$-dependent families of size $d^{\prime}+1$ in
$V\cap\Pi_{d^{\prime}}$ is at most
$d|V\cap\Pi_{d^{\prime}}|^{d^{\prime}+\mu}$.

###### Proof.

We prove this corollary by induction on $d$. For $d=0$, the corollary is
trivially true. Suppose now $d\geq 1$. We apply Lemma 4.1 and distinguish
whether the first or second outcome of it is realised.

  * •

In the first case, there exists a subspace $\Pi_{d^{\prime}}$ of dimension
$0\leq d^{\prime}\leq d-1$ such that $|V\cap\Pi_{d^{\prime}}|\geq n^{\mu}$. We
now apply the induction hypothesis on $V^{\prime}=V\cap\Pi_{d^{\prime}}$,
giving a subspace $\Pi_{d^{\prime\prime}}$ of dimension $d^{\prime\prime}$
such that $0\leq d^{\prime\prime}\leq d^{\prime}\leq d-1$ and
$|V\cap\Pi_{d^{\prime\prime}}|=|V^{\prime}\cap\Pi_{d^{\prime\prime}}|\geq|V^{\prime}|^{\mu^{d^{\prime}-d^{\prime\prime}}}\geq
n^{\mu^{d-d^{\prime\prime}}}$ and the number of $d^{\prime\prime}$-dependent
families of $V\cap\Pi_{d^{\prime\prime}}=V^{\prime}\cap\Pi_{d^{\prime\prime}}$
is at most $d|V\cap\Pi_{d^{\prime\prime}}|^{d^{\prime\prime}+\mu}$, as wanted.

  * •

In the second case, we immediately get the desired outcome for $d^{\prime}=d$
and $\Pi_{d}=\mathbb{R}^{d}$.

∎

By the corollary above, for any set of $n$ points $V$ in $\mathbb{R}^{d}$,
there is a subspace $\Pi_{d^{\prime}}$ that contains many of these points and
such that there are not many $d^{\prime}$-dependent families in
$V\cap\Pi_{d^{\prime}}$. The aim of the next lemma is to give sufficient
conditions for when it is possible to reconstruct
$\mathrm{dist}(v,\Pi_{d^{\prime}})$ and the projections of $v$ onto
$\Pi_{d^{\prime}}$ (relative to the embedding of $V\cap\Pi_{d^{\prime}}$) for
almost all of $v\in V$.

######  Lemma 4.3.

Let $d\geq 1$ be an integer and $\alpha$, $\delta$, $\lambda$ be positive
constants such that $\alpha-(d+1)\delta\geq\lambda$. Let $V$ be a multiset of
$n$ points in $\mathbb{R}^{d}$. Let $A\subset V$ and $p\gg p_{*}(n,d)$.
Suppose that

  1. 1.

there exists a $d^{\prime}$-dimensional subspace $\Pi_{d^{\prime}}$ in
$\mathbb{R}^{d}$ such that $A\subset\Pi_{d^{\prime}}$ and at least
$\alpha\binom{|A|}{d^{\prime}+1}$ of sets of $d^{\prime}+1$ points of $A$ are
$d^{\prime}$-independent,

  2. 2.

$p|A|\gg 1$, and

  3. 3.

there exists a set $A^{\prime}\subseteq A$ such that
$|A^{\prime}|\geq(1-\delta/2)|A|$ and for every $u,v\in A^{\prime}$, we know
the distance $\mathrm{dist}(u,v)$.

If the distances are revealed according to a random graph $G(n,p)$, then
w.h.p. there exists a subset $V^{\prime}\subseteq V$ of size
$|V^{\prime}|\geq(1-\delta)|V|$ such that for every $v^{\prime}\in
V^{\prime}$, we can reconstruct $\mathrm{dist}(v^{\prime},\Pi_{d^{\prime}})$
and the projection of $v^{\prime}$ onto $\Pi_{d^{\prime}}$ relative to the
embedding of $A^{\prime}$.

###### Proof.

Let $\mathcal{I}$ be the set of $d^{\prime}$-independent sets in $A^{\prime}$.
Note that
$|\mathcal{I}|\geq\alpha\binom{|A|}{d^{\prime}+1}-\delta/2|A|\binom{|A|}{d^{\prime}}$,
and that
$\binom{|A|}{d^{\prime}+1}=\binom{|A|}{d^{\prime}}\frac{|A|-d^{\prime}-1}{d^{\prime}+1}\geq\binom{|A|}{d^{\prime}}\frac{|A|}{2(d+1)}$
when $n$ is large enough. Therefore, we have
$|\mathcal{I}|\geq\lambda\binom{|A|}{d^{\prime}+1}$ for $n$ large enough.

Let $B=V\setminus A$. Let $u\in B$, and for each $I\in\mathcal{I}$ we define
the random variable $I_{u}$ to be the indicator of $u$ having an edge to each
element of $I$. We also define the random variable
$V_{u}=\sum_{I\in\mathcal{I}}I_{u}$. Since $|A|p\to\infty$, we have

$\mathbb{E}V_{u}\geq
p^{d^{\prime}+1}{|A|\choose{d^{\prime}+1}}\lambda=\Omega_{d,\lambda}\left(\left(|A|p\right)^{d^{\prime}+1}\right),\mbox{
and }$

$\begin{split}\operatorname{Var}V_{u}&{}=\sum_{I,I^{\prime}\in\mathcal{I}}\left(p^{\left|I\cup
I^{\prime}\right|}-p^{2\left(d^{\prime}+1\right)}\right)\\\
&{}\leq\sum_{I,I^{\prime}\in A^{(d^{\prime}+1)}}\left(p^{\left|I\cup
I^{\prime}\right|}-p^{2\left(d^{\prime}+1\right)}\right)\\\
&=\sum_{i=0}^{d^{\prime}+1}{|A|\choose{d^{\prime}+1+i}}{{d^{\prime}+1+i}\choose{i}}{{d^{\prime}+1}\choose{i}}(p^{d^{\prime}+1+i}-p^{2(d^{\prime}+1)})\\\
&<\sum_{i=0}^{d^{\prime}}{|A|\choose{d^{\prime}+1+i}}{{d^{\prime}+1+i}\choose{i}}{{d^{\prime}+1}\choose{i}}p^{d^{\prime}+1+i}\\\
&{}{}=O_{d}\left(\left(|A|p\right)^{2d^{\prime}+1}\right).\end{split}$

Let $B^{\prime}=\\{u\in B:V_{u}>1\\}$. By Chebyshev’s inequality, we have
$\mathbb{P}\left(V_{u}=0\right)=O_{d,\lambda}\left(\left(|A|p\right)^{-1}\right)\to
0$, and therefore $\mathbb{E}|B^{\prime}|=(1-o(1))|B|$. Hence, w.h.p.
$|B^{\prime}|\geq(1-\delta/2)|B|$. Now by Lemma 2.2, for every $b^{\prime}\in
B^{\prime}$, there is an $I\in\mathcal{I}$ such that we can reconstruct
$\\{b^{\prime}\\}\cup I$. Since $I$ is $d^{\prime}$-independent, we can extend
this embedding uniquely to reconstruct $\\{b^{\prime}\\}\cup A^{\prime}$. Thus
we can reconstruct $\mathrm{dist}(b^{\prime},\Pi_{d^{\prime}})$ and the
projection of $b^{\prime}$ onto $\Pi_{d^{\prime}}$ relative to the embedding
of $A^{\prime}$. Letting $V^{\prime}=B^{\prime}\cup A^{\prime}$, we reach the
desired conclusion. ∎

We now present the following technical lemma, which allows us to reduce the
problem to a lower dimension.

######  Lemma 4.4.

Let $d\geq 1$, $0<\varepsilon<\frac{1}{2(d+1)}$ be fixed and
$V=\\{v_{1},\dots,v_{n}\\}$ be a multiset of $n$ points in $\mathbb{R}^{d}$.
Suppose the graph $G=(V,\mathcal{P})$ of revealed pairwise distances is
distributed as $G(n,p)$ and that $p\gg p_{*}(n,d)$. Then, w.h.p., we can
explicitly construct some constants $b_{i,j}$ such that there exists a set
$J\subseteq[n]$ such that $|J|\geq(1-\varepsilon)n$ and
$\tilde{V}=\\{\tilde{v}_{1},\dots,\tilde{v}_{n}\\}$ a multiset of
$\mathbb{R}^{d^{\prime}}$ for some $d^{\prime}<d$ such that for every $i,j\in
J$, we have
$\mathrm{dist}(v_{i},v_{j})^{2}=b_{i,j}+\mathrm{dist}(\tilde{v}_{i},\tilde{v}_{j})^{2}$.

Note that while we obtain the values of the $b_{i,j}$, we do not claim to know
the configuration of $\tilde{V}$. However, given $b_{i,j}$, we can compute
$\mathrm{dist}(\tilde{v}_{i},\tilde{v}_{j})$ from $\mathrm{dist}(v_{i},v_{j})$
and vice versa. Before proving Lemma 4.4, we show that a simple iteration of
Lemma 4.4 enables us to deduce Theorem 1.5.

###### Proof of Theorem 1.5 assuming Lemma 4.4.

We let $q(n,d)=p_{*}(n,d)$ and $p\gg p_{*}(n,d)$. Note that $G$ sampled
according to $G(n,p)$ can also be sampled as $\cup_{i=0}^{d-1}G_{i}$ where the
$G_{i}$ are independent from each other and each $G_{i}$ is sampled according
to $G(n,p^{\prime})$ where $1-p=(1-p^{\prime})^{d}$. By Bernoulli’s
inequality, $p^{\prime}\geq p/d$, and therefore $p^{\prime}\gg p_{*}(n,d)$.

Let $\kappa>0$, and let $\varepsilon=\min(\frac{1}{2(d+1)},\kappa/d)$. We
start by applying Lemma 4.4 to $V^{(0)}=V$ with the random graph $G_{0}$, and
w.h.p. get explicit constants $b^{(0)}_{i,j}$, a set $J^{(0)}\subseteq[n]$
such that $|J^{(0)}|\geq(1-\varepsilon)n$, an integer $d^{(1)}<d$ and a set
$V^{(1)}=\\{v^{(1)}_{1},\dots,v^{(1)}_{n}\\}$ lying in $\mathbb{R}^{d^{(1)}}$
such that for every $i,j\in J^{(0)}$, we have
$\mathrm{dist}(v^{(0)}_{i},v^{(0)}_{j})^{2}=b^{(0)}_{i,j}+\mathrm{dist}(v^{(1)}_{i},v^{(1)}_{j})^{2}$.
If $d^{(1)}\neq 0$, we apply Lemma 4.4 again to $V^{(1)}$ with the random
graph $G_{1}$, and get explicit constants $b^{(1)}_{i,j}$, a set
$J^{(1)}\subseteq[n]$ such that $|J^{(1)}|\geq(1-\varepsilon)n$, an integer
$d^{(2)}<d^{(1)}$ and a set $V^{(2)}=\\{v^{(2)}_{1},\dots,v^{(2)}_{n}\\}$
lying in $\mathbb{R}^{d^{(2)}}$ such that for every $i,j\in J^{(2)}$, we have
$\mathrm{dist}(v^{(1)}_{i},v^{(1)}_{j})^{2}=b^{(1)}_{i,j}+\mathrm{dist}(v^{(2)}_{i},v^{(2)}_{j})^{2}$.

We continue in the same fashion until we have $d^{(k)}=0$ for some integer
$k$. As $d^{(i+1)}\leq d^{(i)}-1$ for all $i\leq k-1$, we have $k\leq d$. Let
$J=J^{(0)}\cap\dots J^{(k-1)}$. We have $|J|=|J^{(0)}\cap\dots
J^{(k-1)}|\geq(1-d\varepsilon)n\geq(1-\kappa)n$, and for every $i,j\in J$, it
follows that
$\mathrm{dist}(v_{i},v_{j})^{2}=\mathrm{dist}(v^{(0)}_{i},v^{(0)}_{j})^{2}=b^{(0)}_{i,j}+\mathrm{dist}(v^{(1)}_{i},v^{(1)}_{j})^{2}=\dots=b^{(0)}_{i,j}+\dots+b^{(k-1)}_{i,j}$.
Therefore we can reconstruct all the pairwise distances in $J$ w.h.p. This
finishes the proof. ∎

Now we are left to prove Lemma 4.4.

###### Proof of Lemma 4.4.

Let $p\gg p_{*}(n,d)$. Note that $G$ sampled according to $G(n,p)$ can also be
sampled as $G_{1}\cup G_{2}\cup G_{3}$ where $G_{1}$, $G_{2}$ and $G_{3}$ are
independent from each other and $G_{1}$, $G_{2}$ and $G_{3}$ are each sampled
according to $G(n,p^{\prime})$ where $1-p=(1-p^{\prime})^{3}$. By Bernoulli’s
inequality, $p^{\prime}\geq p/3$, and therefore $p^{\prime}\gg p_{*}(n,d)$. By
Corollary 4.2 applied to $V$ and $(1/\eta(d))^{1/d}<\mu<1$ there exists a
subspace $\Pi_{d^{\prime}}$ of dimension $0\leq d^{\prime}\leq d-1$ such that
$|V\cap\Pi_{d^{\prime}}|\geq n^{\mu^{d-d^{\prime}}}$ and the number of
$d^{\prime}$-dependent families of $V\cap\Pi_{d^{\prime}}$ is at most
$d|V\cap\Pi_{d^{\prime}}|^{d^{\prime}+\mu}$.

If $d^{\prime}\geq 1$, let $A=V\cap\Pi_{d^{\prime}}$ and let $\mu^{\prime}$ be
fixed such that $\mu<\mu^{\prime}<1$. The number of $d^{\prime}$-dependent
families of $A$ is at most
$d|A|^{\mu+d^{\prime}}\leq|A|^{\mu^{\prime}+d^{\prime}}$ for $n$ large enough.
Therefore by Theorem 3.1 with the pairwise distances revealed as $G_{1}$,
w.h.p. we can reconstruct the pairwise distances within a set
$A^{\prime}\subseteq A$ of size $|A^{\prime}|\geq(1-\varepsilon/2)|A|$. By
Lemma 4.3 with the pairwise distances revealed as $G_{2}$, since
$p^{\prime}|A|\geq p^{\prime}n^{\mu^{d}}\gg 1$, w.h.p. there is a set
$W\subseteq V$ such that $|W|\geq(1-\varepsilon)|V|$ and for every element of
$W$, we can reconstruct the distance to $\Pi_{d^{\prime}}$ and the projection
onto $\Pi_{d^{\prime}}$ relative to the embedding of $A^{\prime}$. For every
$v_{i}\in W$, let $v^{\parallel}_{i}$ be the projection of $v_{i}$ on
$\Pi_{d^{\prime}}$ and $\tilde{v}_{i}=v_{i}-v^{\parallel}_{i}$. For every
$v_{i},v_{j}\in W$, let
$b_{i,j}=\mathrm{dist}(v^{\parallel}_{i},v^{\parallel}_{j})^{2}$, and note
that we have knowledge of the value of $b_{i,j}$. The $\tilde{v}_{i}$ lie
inside of a space isomorphic to $\mathbb{R}^{d-d^{\prime}}$, and for every
$v_{i},v_{j}\in W$, we have
$\mathrm{dist}(v_{i},v_{j})^{2}=b_{i,j}+\mathrm{dist}(\tilde{v}_{i},\tilde{v}_{j})^{2}$.
This finishes the first case.

If $d^{\prime}=0$, we have a point of multiplicity $m\geq n^{\mu^{d}}$ in $V$,
and let $M$ be the multiset corresponding to it. If $m\geq(1-\varepsilon)n$,
then as $p^{\prime}\geq p_{*}(n,d)/3\geq 4\frac{\log n}{n}\geq 2\frac{\log
m}{m}$ for $n$ large enough, by Theorem 2.5 we have that w.h.p. $G_{1}$
restricted to the set $M$ is connected. Therefore we can reconstruct the set
$M$, as wanted. If $m\leq(1-\varepsilon)n$, then $Y=V\setminus M$ has size
$|Y|\geq\varepsilon n$. We apply Corollary 4.2 again, but this time to $Y$.
Therefore there exists a subspace $\Pi_{d^{\prime\prime}}$ of dimension $0\leq
d^{\prime\prime}\leq d-1$ such that
$|Y\cap\Pi_{d^{\prime\prime}}|\geq\varepsilon^{\mu^{d-d^{\prime\prime}}}n^{\mu^{d-d^{\prime\prime}}}$
and the number of $d^{\prime\prime}$-dependent families of
$Y\cap\Pi_{d^{\prime\prime}}$ is at most
$d|Y\cap\Pi_{d^{\prime\prime}}|^{d^{\prime\prime}+\mu}$. If
$d^{\prime\prime}\geq 1$, then one concludes the same way as in the case
$d^{\prime}\geq 1$.

If $d^{\prime\prime}=0$, then there exists a point of multiplicity
$m^{\prime}\geq|Y|^{\mu^{d}}\geq\varepsilon^{\mu^{d}}n^{\mu^{d}}$ in $Y$, and
we let $M^{\prime}$ be the multiset corresponding to it. Note that for $n$
large enough we have $p^{\prime}\geq p_{*}(n,d)/3\geq 2\frac{\log
n}{\varepsilon n}\geq 2\frac{\log m^{\prime}}{m^{\prime}}$, and therefore by
Theorem 2.5 with the pairwise distances revealed as $G_{2}$ w.h.p. we can
reconstruct the set $M^{\prime}$. Let $\Pi_{1}$ be the line in
$\mathbb{R}^{d}$ containing both $M$ and $M^{\prime}$ and let
$M^{\prime\prime}=M\cup M^{\prime}$. Clearly, w.h.p. the distance between $M$
and $M^{\prime}$ is among the revealed distances. Note that $p|M|\gg 1$ and
$p|M^{\prime}|\gg 1$, so we may apply twice Lemma 4.3, once for $A=M$, and
once for $A=M^{\prime}$, with $d^{\prime}=0$, $\alpha=1$,
$\delta=\varepsilon/2$, $\lambda=1/2$. We obtain sets $X,X^{\prime}\subset V$
such that $|X|\geq(1-\varepsilon/2)n$ and
$|X^{\prime}|\geq(1-\varepsilon/2)n$, and for each $x\in X$, we have
reconstructed $\mathrm{dist}(x,M)$ and for each $x^{\prime}\in X^{\prime}$, we
have reconstructed $\mathrm{dist}(x^{\prime},M^{\prime})$. Letting $Z=X\cap
X^{\prime}$, we have $|Z|\geq(1-\varepsilon)n$, and for every $z\in Z$, we
have reconstructed $\mathrm{dist}(z,\Pi_{1})$ and the projection $z^{\prime}$
of $z$ onto $\Pi_{1}$ relative to the embedding of $M^{\prime\prime}$. From
there, we can conclude the same way as in the first outcome above. This
finishes the proof. ∎

##  5 Concluding remarks

For any set of $n$ points $V$ in $\mathbb{R}^{d}$, we have obtained in Theorem
1.5 a non-trivial bound on $p$ under which, w.h.p., we can reconstruct the
pairwise distances within a subset of $V$ of size $n-o(n)$. However, we do not
believe that our bound is tight. For instance, for $d=1$, much stronger
results have been obtained in Theorem 1.4 by Girão, Illingworth, Michel,
Powierski, and Scott, suggesting that the criticial probability could be
$c_{d}/n$ for some constant $c_{d}$. Additionally, we have sought to
reconstruct $n-o(n)$ points, rather than $\Omega(n)$ as posed by them in
1.3—we do not know whether the thresholds of these two problems are different.

We remark that Bartha and Kolesnik [2] recently improved upon Balogh,
Bollobás, and Morris’s result Theorem 2.1 and determined $p_{c}(n,K_{d+3})$ up
to a multiplicative constant, i.e.,
$p_{c}(n,K_{d+3})=\Theta\left(n^{-1/\eta(d)}\right)$. It is possible that
adapting their method to the reconstructibility problem could improve the
result of Theorem 1.5 up to a polylogarithmic factor, but such attempts were
not made in this paper, since, as mentioned earlier, we do not believe that
the range of $p$ in Theorem 1.5 is close to optimal. We would also like to
remark that, instead of Theorem 3.1, one could have applied a second moment
method to find the number of embeddings of $K_{d+3}-e$ rooted on each edge.
This corresponds to taking $r=1$ in this analysis, and would give a slightly
larger exponent of $n$ in $q(n,d)=p_{*}(n,d)$.

##  6 Acknowledgements

The research was mostly conducted while the first, the fourth and the fifth
authors were students taking part in the University of Cambridge Summer
Research in Mathematics (SRIM) programme, and were supervised by Prof Julian
Sahasrabudhe. The authors would like to thank Prof Julian Sahasrabudhe for the
many hours of helpful discussions.

The first and fourth authors were supported by the Trinity College Summer
Studentship Scheme fund. The fifth author was supported by the Churchill
College Summer Opportunities Bursary and the CMS Bursary. The second and third
author are supported by EPSRC (Engineering and Physical Sciences Research
Council): the second author’s reference is EP/V52024X/1, the third author’s
reference is EP/T517847/1. The second author is also supported by the
Department of Pure Mathematics and Mathematical Statistics of the University
of Cambridge, and the third author is also supported by the Cambridge
Commonwealth, European and International Trust.

## References

  * [1] József Balogh, Béla Bollobás, and Robert Morris, _Graph bootstrap percolation_ , Random Structures & Algorithms 41 (2012), no. 4, 413–440.
  * [2] Zsolt Bartha and Brett Kolesnik, _Weakly saturated random graphs_ , April 2023, arXiv:2007.14716 [math].
  * [3] Itai Benjamini and Elad Tzalik, _Determining a Points Configuration on the Line from a Subset of the Pairwise Distances_ , October 2022, arXiv:2208.13855 [math].
  * [4] Béla Bollobás, _Weakly k-saturated graphs_ , Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), vol. 25, 1968, p. 31.
  * [5] Béla Bollobás and Arthur G. Thomason, _Threshold functions_ , Combinatorica 7 (1987), no. 1, 35–38.
  * [6] Robert Connelly, _Generic global rigidity_ , Discrete & Computational Geometry 33 (2005), 549–563.
  * [7] Paul Erdős and Miklós Simonovits, _Supersaturated graphs and hypergraphs_ , Combinatorica 3 (1983), 181–192.
  * [8] Paul Erdős and Alfréd Rényi, _On the evolution of random graphs_ , Publ. math. inst. hung. acad. sci 5 (1960), no. 1, 17–60.
  * [9] Tolga Eren, David Goldenberg, Walter Whiteley, Yang Yang, A. Morse, Brian Anderson, and Peter Belhumeur, _Rigidity, Computation, and Randomization in Network Localization._ , vol. 4, January 2004.
  * [10] Alan Frieze and Michał Karoński, _Introduction to random graphs_ , Cambridge University Press, 2016.
  * [11] António Girão, Freddie Illingworth, Lukas Michel, Emil Powierski, and Alex Scott, _Reconstructing a point set from a random subset of its pairwise distances_ , January 2023, arXiv:2301.11019 [math].
  * [12] Steven J. Gortler, Alexander D. Healy, and Dylan P. Thurston, _Characterizing generic global rigidity_ , American Journal of Mathematics 132 (2010), no. 4, 897–939.
  * [13] Janko Gravner and Elaine McDonald, _Bootstrap percolation in a polluted environment_ , Journal of Statistical Physics 87 (1997), 915–927.
  * [14] Bruce Alan Hendrickson, _The molecule problem: Determining conformation from pairwise distances_ , Cornell University, 1991.
  * [15] Roger A. Horn and Charles R. Johnson, _Matrix analysis_ , Cambridge University Press, 2013.
  * [16] Tibor Jordán and Walter Whiteley, _Global rigidity_ , Handbook of Discrete and Computational Geometry, Chapman and Hall/CRC, 2017, pp. 1661–1694.
  * [17] Paul Lemke, Steven S. Skiena, and Warren D. Smith, _Reconstructing sets from interpoint distances_ , Discrete and Computational Geometry: The Goodman-Pollack Festschrift, Springer, 2003, pp. 597–631.
  * [18] Alan Lew, Eran Nevo, Yuval Peled, and Orit E. Raz, _Sharp threshold for rigidity of random graphs_ , Bulletin of the London Mathematical Society 55 (2023), no. 1, 490–501.
  * [19] J von Neumann, _Theory of self-reproducing automata_ , Edited by Arthur W. Burks (1966).
  * [20] Stanislaw Ulam, _Random processes and transformations_ , Proceedings of the international congress on mathematics, vol. 2, Citeseer, 1952, pp. 264–275.

##  Appendix A Appendix

We now prove Lemma 2.2 and its Corollary 2.3, repeated here for ease of
reading.

######  Lemma 2.2.

Given all pairwise distances within some
$S=\\{v_{1},\dots,v_{r}\\}\subset\mathbb{R}^{d}$, we can reconstruct the
configuration of $S$ up to isometry.

###### Proof.

Write $u_{i}=v_{i}-v_{r}$ for $1\leq i<r$. Recall that the Gram matrix of the
vectors $u_{1},\dots,u_{r-1}$ is the matrix given by $G_{ij}=\langle
u_{i},u_{j}\rangle$. For $i=j$, this is $|v_{i}-v_{r}|^{2}$. For $i\neq j$, we
have $|v_{i}-v_{j}|^{2}=|u_{i}-u_{j}|^{2}=G_{ii}+G_{jj}-2G_{ij}$, so
$G_{ij}=\frac{1}{2}\left(|v_{i}-v_{r}|^{2}+|v_{j}-v_{r}|^{2}-|v_{i}-v_{j}|^{2}\right)$.
Thus we can compute the Gram matrix of $u_{1},\dots,u_{r-1}$ from the
distances within $S$.

The Gram matrix of a set of points determines their positions up to orthogonal
transformations (see for instance Theorem 7.3.11, [15]). So the pairwise
distances within $S$ determine $u_{i}$ up to orthogonal transformations, and
thus determine $S$ up to isometry. ∎

######  Corollary 2.3.

Suppose a multiset $R$ of $d+3$ points of $\mathbb{R}^{m}$ ($m\geq d$) lies in
a $d$-dimensional subspace (but we do not necessarily know this yet). Then,
given all pairwise distances within $R$ except some pair $uv$, we can identify
whether $Q=R\setminus\\{u,v\\}$ is $d$-independent. If so, we can also
determine the distance $uv$.

###### Proof of Corollary 2.3.

From these distances, Lemma 2.2 allows us to reconstruct $Q$ up to isometry.
This allows us to identify whether $Q$ is $d$-independent by checking the
reconstruction of $Q$. Indeed, $Q$ is $d$-independent if and only if the
$u_{i}$ as in the proof of Lemma 2.2 are linearly independent. This holds if
and only if $G$ is positive definite (see for instance Theorem 7.2.10, [15]),
which we can compute and check.

Suppose $Q$ is $d$-independent. Note that by Lemma 2.2 we can also reconstruct
each of $Q\cup\\{u\\}$ and $Q\cup\\{v\\}$, up to isometry. But $u,v$ lie in
the $d$-dimensional subspace spanned by $Q$, so any isometry fixing $Q$ also
fixes $u,v$. So given an embedding of $Q$, we can uniquely extend this to
embed $u,v$. Thus we can reconstruct the distance $uv$. ∎


# The influence of crystalline electric field on the magnetic properties of
CeCd${}_{3}X_{3}$ ($X$ = P and As)

Obinna P. Uzoh1, Suyoung Kim1, and Eundeok Mun1,2 1 Department of Physics,
Simon Fraser University, 8888 University Drive, Burnaby, B.C. Canada  2 Center
for Quantum Materials and Superconductivity (CQMS), Sungkyunkwan University,
Suwon 16419, South Korea

###### Abstract

CeCd3P3 and CeCd3As3 compounds adopt the hexagonal ScAl3C3-type structure,
where magnetic Ce ions on a triangular lattice order antiferromagnetically
below $T_{\text{N}}\sim$0.42 K. Their crystalline electric field (CEF) level
scheme has been determined by fitting magnetic susceptibility curves,
magnetization isotherms, and Schottky anomalies in specific heat. The
calculated results, incorporating the CEF excitation, Zeeman splitting, and
molecular field, are in good agreement with the experimental data. The CEF
model, with Ce3+ ions in a trigonal symmetry, explains the strong easy-plane
magnetic anisotropy that has been observed in this family of materials. A
detailed examination of the CEF parameters suggests that the fourth order CEF
parameter $B_{4}^{3}$ is responsible for the strong CEF induced
magnetocrystalline anisotropy, with a large $ab$-plane moment and a small
$c$-axis moment. The reliability of our CEF analysis is assessed by comparing
the current study with earlier reports of CeCd3As3. For both CeCd${}_{3}X_{3}$
($X$ = P and As) compounds, less than 40 % of $R\ln(2)$ magnetic entropy is
recovered by $T_{\text{N}}$ and full $R\ln(2)$ entropy is achieved at the
Weiss temperature $\theta_{p}$. Although the observed magnetic entropy is
reminiscent of delocalized 4$f$-electron magnetism with significant Kondo
screening, the electrical resistivity of these compounds follows a typical
metallic behavior. Measurements of thermoelectric power further validate the
absence of Kondo contribution in CeCd${}_{3}X_{3}$.

##  I Introduction

Several $f$-electron materials with triangular lattices (TL) have shown rich
phenomena, where the spin-orbit coupling enhances quantum fluctuations due to
the highly anisotropic interactions between 4$f$ moments [1, 2, 3, 4, 5, 6].
For example, a spin liquid state has been proposed in insulating YbMgGaO4 [7,
8, 9, 10, 11] and NaYbS2[12, 13]. The low carrier density system YbAl3C3 shows
a gap in the magnetic excitation spectrum due to the dimerization of the $f$
electrons in Yb3+ pairs [14, 15, 16, 17]. Of interest is the easy-plane
antiferromagnets CeCd${}_{3}X_{3}$ ($X$ = P and As), a new class of TL system,
with a low antiferromagnetic ordering temperature and extremely low carrier
density [18, 19, 20, 21, 22].

Figure 1: (a) Crystal structure of the hexagonal CeCd${}_{3}X_{3}$ ($X=$ P and
As). (b) Ce atoms forming two-dimensional triangular lattices. (c) Ce atom in
a trigonal ($D_{3d}$) point symmetry surrounded by P/As atoms.

The family of compounds Ce$M_{3}X_{3}$ ($M$ = Al, Cd, and Zn, $X$ = C, P, and
As) have been investigated for their robust ground state properties arising
from the interplay between crystalline electric field (CEF) and magnetic
exchange interaction on the triangular lattice [16, 18, 19, 20, 21, 22, 23,
24]. CeCd3$X$3 materials adopt the hexagonal ScAl3C3-type structure (space
group $P6_{3}/mmc$) with the magnetic Ce3+ ions having a trigonal ($D_{3d}$)
point symmetry as shown in Fig. 1(c) [20, 21, 22, 23]. In this crystal
structure, the Ce layers are well separated by the Cd and $X$ atoms, forming a
layered 2D TL in the $ab$-plane, as depicted in Figs. 1(a) and (b) [20, 21,
22, 23]. Thermodynamic and transport property measurements have characterized
CeCd3$X$3 as an low carrier density system, with a strong easy plane magnetic
anisotropy and antiferromagnetic ordering below $T_{\text{N}}$ $\sim$0.42 K
[19, 22]. The low carrier density means there are insufficient charge carriers
to screen all local moments and to mediate Ruderman-Kittel-Kasuya-Yosida
(RKKY) exchange interaction between moments. In this regard, both RKKY and
Kondo interactions are expected to be weakened in these compounds. We note
that the electrical resistivity measurement on CeCd3As3 grown by chemical
vapor transport shows a semiconductor-like enhancement as decreasing
temperature [20], while the flux grown CeCd3As3 sample is metallic [19]. At
the magnetic ordering temperature, roughly 40% of $R\ln(2)$ entropy is
recovered. This implies a doublet ground state resulting from CEF splitting of
localized Ce ion energy levels. The highly enhanced specific heat below 10 K
and the reduced magnetic entropy at $T_{\text{N}}$ are reminiscent of Kondo
lattice materials. However, the electrical resistivity of CeCd${}_{3}X_{3}$
shows no maximum or logarithmic upturns resulting from the Kondo scattering of
conduction electrons from magnetic Ce ions. The resistivity of
CeCd${}_{3}X_{3}$ is the same as that of LaCd${}_{3}X_{3}$, implying an
absence of Kondo screening in these materials [19, 22].

Here, we use the CEF scheme to clarify the anisotropic magnetic properties of
CeCd${}_{3}X_{3}$ ($X$ = P and As), where the CEF analysis is performed using
the $PyCrystalField$ package [26]. For CeCd3As3, the CEF analyses of two
previous independent studies [20, 25], carried out only considering magnetic
susceptibility and magnetization, have shown discrepancies in their energy
level splittings and first excited state wave functions. Thus, we extend the
CEF analysis to specific heat data to resolve these discrepancies. In contrast
to CeCd3As3, no CEF analysis has been carried out for CeCd3P3. We show that
the easy plane magnetic anisotropy observed in these compounds can be
explained by the strong CEF acting on Ce3+ ions. In addition, we provide
evidence of the lacking Kondo screening in these materials by way of
thermoelectric power measurements.

##  II Experimental

For this work, single crystals of LaCd${}_{3}X_{3}$ and CeCd${}_{3}X_{3}$ ($X$
= P and As) were grown by high temperature ternary melt [27, 22, 19].
Magnetization measurements as a function of temperature and magnetic field
were performed in a QD MPMS. Specific heat of these compounds was measured in
QD PPMS. The obtained results are consistent with earlier reports [19, 22].
Thermoelectric power measurements were performed in a home made two
thermometer and one heater setup. Detailed studies of thermodynamic and
transport properties of these compounds are presented in Ref. [19, 22].

##  III Results & Discussion

Figure 2: (a) Inverse magnetic susceptibility curves of CeCd3As3, taken at $H$
= 1 kOe for both $H\parallel ab$ and $H\parallel c$. (b) Magnetization
isotherms at 1.8 K for both $H\parallel ab$ and $H\parallel c$. (c) Magnetic
part of the specific heat at $H$ = 0 and 90 kOe along $H\parallel ab$. Open
symbols are experimental data. Dashed lines represent CEF fits with no
molecular field contribution. Solid lines are CEF fits with molecular field
terms $\lambda_{ab}~{}=~{}-5.7$ mole/emu and $\lambda_{c}~{}=~{}1.0$ mole/emu.
Table 1: CeCd3As3: CEF parameters, energy eigenvalues, eigenstates, and
molecular field parameters. CEF and molecular field parameters
---
|  $B_{2}^{0}$ (K) |  $B_{4}^{0}$ (K) |  $B_{4}^{3}$ (K) |  $\lambda_{i}$ (mole/emu) |  |
| 18.55 | -0.08 | 23.02 |  $\lambda_{ab}=-5.7$, |  |
|  |  |  | $\lambda_{c}=1.0$ |  |
Energy eigenvalues and eigenstates
E (K) | $|-\frac{5}{2}\rangle$ | $|-\frac{3}{2}\rangle$ | $|-\frac{1}{2}\rangle$ | $|\frac{1}{2}\rangle$ | $|\frac{3}{2}\rangle$ | $|\frac{5}{2}\rangle$
0 | 0.0 | 0.0 |  $-$0.898 | 0.0 | 0.0 | 0.440
0 | 0.440 | 0.0 | 0.0 | 0.898 | 0.0 | 0.0
242 | 0.0 | -1.0 | 0.0 | 0.0 | 0.0 | 0.0
242 | 0.0 | 0.0 | 0.0 | 0.0 | -1.0 | 0.0
553 | -0.898 | 0.0 | 0.0 | 0.440 | 0.0 | 0.0
553 | 0.0 | 0.0 | 0.440 | 0.0 | 0.0 | 0.898

For CeCd3$X$3 systems, Ce atoms occupy a single site at the 2$a$ Wyckoff
position that has a trigonal point symmetry, shown in Fig. 1(c). In this point
symmetry, the CEF Hamiltonian requires only three parameters [28, 29]: ${\cal
H}_{CEF}=B^{0}_{2}O^{0}_{2}+B^{0}_{4}O^{0}_{4}+B^{3}_{4}O^{3}_{4}$, where
$O^{m}_{n}$ are the Stevens operators and $B^{m}_{n}$ are known as the CEF
parameters [30, 31]. It has to be noted here that thermodynamic and transport
property measurements of these compounds indicate a possible structural phase
transition below 132 K [16, 19, 22]. Additional CEF parameters below the
transition temperature are probably required to account for the change in the
local environment of the Ce atoms. However, the magnetic susceptibility curves
show a smooth evolution through the transition temperature. Therefore, we
assume in our CEF analysis that the Ce ions have the same trigonal symmetry
below the transition temperature. To account for the Zeeman effect and the
interaction between magnetic ions, the eigenvalues and eigenfunctions are
determined by diagonalizing the total Hamiltonian: ${\cal H}={\cal
H}_{CEF}-g_{J}\mu_{B}J_{i}(H_{i}+\lambda_{i}M_{i})$ ($i$ = $x$, $y$, and $z$),
where $g_{J}$ is the Landé $g$-factor, $\mu_{B}$ is the Bohr magneton, $H_{i}$
is the applied field, $J_{i}$ is the angular momentum operator, and $M_{i}$ is
the magnetization. The second term is the Zeeman contribution and the third
term represents the effective molecular interactions $\lambda_{i}$.

The point charge CEF model assumes that the magnetic ions are well localized
with a stable valence state. The valence state of CeCd3$X$3 can be deduced
from the effective moment of Ce ions. Figures 2(a) and 3(a) show inverse
magnetic susceptibility, $\chi^{-1}=H/M$, curves of CeCd3As3 and CeCd3P3,
respectively. At sufficiently high temperatures, magnetic susceptibility
curves follow the Curie-Weiss (CW) behavior: $\chi(T)=C/(T-\theta_{p})$, where
$C$ is the Curie constant and $\theta_{p}$ is the Weiss temperature. The
effective moments of CeCd3P3 and CeCd3As3 are estimated by applying the CW law
to the polycrystalline averaged magnetic susceptibility to be
$\mu_{eff}=2.51~{}\mu_{B}$ and $\mu_{eff}=2.54~{}\mu_{B}$, respectively; which
agree very well with the theoretical value $\mu_{eff}=2.54~{}\mu_{B}$. From
the effective moment values, it is reasonable to assume that Ce ions in these
compounds are well localized with 3+ valence state. As shown in Ref. [32, 25]
the $B^{0}_{2}$ parameter mainly gives a measure of the magnetocrystalline
anisotropy and can be expressed in terms of the Weiss temperatures [33, 34,
35]. From the Curie-Weiss fit (not shown), anisotropic Weiss temperatures of
CeCd3As3 are estimated to be $\theta_{ab}\sim 9.3$ K and $\theta_{c}=-283$ K.
For CeCd3P3, $\theta_{ab}=9.3$ K and $\theta_{c}=-248$ K are obtained. The
obtained $\theta_{p}$ values are consistent with earlier reports [19, 22].
These values are used to estimate the leading CEF parameters: $B^{0}_{2}\sim
30.5$ K for CeCd3As3 and $B^{0}_{2}\sim 26.7$ K for CeCd3P3.

Figure 2 displays anisotropic magnetic susceptibility curves, magnetization
isotherms, and specific heat of CeCd3As3 with the results of CEF analysis.
Table 1 summarizes the obtained CEF parameters, including molecular field
parameters, and the energy eigenstates and eigenvalues. The $2J+1$ degenerate
levels for $J=5/2$ of Ce3+ split into three Kramers doublets with energy level
splittings $\Delta_{1}$ = 242 K and $\Delta_{2}$ = 553 K. The ground state and
second excited state are in a mixture of $|\pm 5/2\rangle$ and $|\mp
1/2\rangle$ states. However, the first excited state is a pure $|\pm
3/2\rangle$ state.

First, we discuss the CEF effects on thermodynamic properties of CeCd3As3
without the molecular field contribution. In Fig. 2, blue dashed-lines
represent the CEF evaluations with $\lambda_{i}$ = 0. The CEF fit generally
agrees with the inverse magnetic susceptibility as the large anisotropy
between crystallographic directions is captured. For $H\parallel c$ the broad
hump around 25 K is well reproduced. The CEF model aligns very well with the
magnetization isotherm, $M(H)$, for $H\parallel c$ at 1.8 K, whereas there is
an inconsistency between the CEF calculation and $M(H)$ for $H\parallel ab$,
as shown in Fig. 2(b). The magnetic contribution to the specific heat,
$C_{m}$, at $H$ = 0 and 90 kOe is presented in Fig. 2(c), where $C_{m}$ is
estimated by subtracting the specific heat of non-magnetic analog LaCd3As3. In
zero field, the broad maximum near 130 K in $C_{m}$ can be reproduced by the
CEF model. Note that the CEF calculation above the maximum cannot capture the
experimental data, which is caused by the very large subtraction error as
explained in Ref. [19]. Obviously, the sharp rise of $C_{m}$ below 10 K and
the sharp peak at $T_{\text{N}}$ = 0.42 K [19] are not captured by the CEF
model. At $H$ = 90 kOe for $H\parallel ab$, the overall shape of $C_{m}$ is
captured by the CEF model, but the maximum temperature is higher than that of
experimental data.

The CEF model without $\lambda_{i}$ does not adequately reproduce $M(H)$ and
$C_{m}$ data for $H\parallel ab$. In order to account for this mismatch, the
molecular field interactions between Ce3+ ions are incorporated. Red solid-
lines in Fig. 2 represent the CEF model in the presence of the molecular field
terms: $\lambda_{ab}=-5.7$ mole/emu and $\lambda_{c}=1$ mole/emu. The magnetic
susceptibility curves with $\lambda_{i}$ show a slightly better agreement than
that with $\lambda_{i}=0$. However, as can be clearly seen in Fig. 2(b), the
$M(H)$ curve for $H\parallel ab$ is well captured by the combination of the
CEF and $\lambda_{i}$. Moreover, although the absolute value of the maximum in
$C_{m}$ at 90 kOe is slightly higher, the position of the maximum temperature
is well reproduced by introducing $\lambda_{i}$. These results point to the
importance of including the exchange interactions between Ce3+ magnetic ions.

Table 2: CeCd3P3: CEF parameters, energy eigenvalues, eigenstates, and
molecular field parameters. CEF and molecular field parameters
---
|  $B_{2}^{0}$ (K) |  $B_{4}^{0}$ (K) |  $B_{4}^{3}$ (K) |  $\lambda_{i}$ (mole/emu) |  |
| 20.90 | -0.03 | 26.00 |  $\lambda_{ab}=-6.2$, |  |
|  |  |  | $\lambda_{c}=0.3$ |  |
Energy eigenvalues and eigenstates
E (K) | $|-\frac{5}{2}\rangle$ | $|-\frac{3}{2}\rangle$ | $|-\frac{1}{2}\rangle$ | $|\frac{1}{2}\rangle$ | $|\frac{3}{2}\rangle$ | $|\frac{5}{2}\rangle$
0 | 0.0 | 0.0 |  $-$0.897 | 0.0 | 0.0 | 0.442
0 | 0.442 | 0.0 | 0.0 | 0.897 | 0.0 | 0.0
257 | 0.0 | -1.0 | 0.0 | 0.0 | 0.0 | 0.0
257 | 0.0 | 0.0 | 0.0 | 0.0 | -1.0 | 0.0
621 | -0.897 | 0.0 | 0.0 | 0.442 | 0.0 | 0.0
621 | 0.0 | 0.0 | 0.442 | 0.0 | 0.0 | 0.897

Figure 3: (a) Inverse magnetic susceptibility curves of CeCd3P3, taken at $H$
= 1 kOe for both $H\parallel ab$ and $H\parallel c$. (b) Magnetization
isotherms at 1.8 K for both $H\parallel ab$ and $H\parallel c$. (c) Magnetic
part of the specific heat at $H$ = 0 and 90 kOe along $H\parallel ab$. Open
symbols are experimental data. Dashed lines represent CEF fits with no
molecular field contribution. Solid lines are CEF fits with molecular field
terms $\lambda_{ab}~{}=~{}-6.2$ mole/emu and $\lambda_{c}~{}=~{}0.3$ mole/emu.

Now turning to the CEF analysis for CeCd3P3, following the same procedure
applied to CeCd3As3. The isostructural compounds CeCd3P3 and CeCd3As3 show
remarkably similar magnetic properties, implying that their local CEF
environments are in close resemblance. Hence, it is expected that the CEF
parameters will be quite similar for both compounds, giving rise to very
similar CEF energy level splittings and eigenstates. Table 2 shows a summary
of CEF fit results of CeCd3P3. As expected, the obtained CEF parameters,
eigenstates, and eigenvalues for CeCd3P3 are very similar to those of CeCd3As3
(Table 1). The positive $B_{2}^{0}$ term indicates that the magnetization lies
in easy plane as seen in Fig. 3(b). The large $B_{4}^{3}$ term implies a mixed
ground state with $|\pm 5/2\rangle$ and $|\mp 1/2\rangle$, just like the case
for CeCd3As3. The first excited state is in a pure state of $|\pm 3/2\rangle$
and the second excited state is in an admixture of $|\pm 5/2\rangle$ and $|\mp
1/2\rangle$ states. The energy level splittings correspond to 257 K for the
first excited state and 621 K for the second excited state.

Figure 3 shows magnetic susceptibility, magnetization, and specific heat
curves of CeCd3P3 together with the CEF calculations. In the absence of
molecular field terms, the CEF calculations (dashed-lines) agree very well
with the experimental $H/M$ curves, as shown in Fig. 3(a). Also, in zero field
$C_{m}$ agrees with the CEF fit at high temperatures, as shown in Fig. 3(c),
implying the high temperature broad maximum (Schottky anomaly) is due to the
CEF effects. The inclusion of the molecular field terms greatly alters the
$M(H)$ curve calculation for $H\parallel ab$ and adequately captures the
experimental $M(H)$ data. In addition, the CEF calculation with molecular
field terms properly captures the low temperature maximum in $C_{m}$ at $H$ =
90 kOe. Therefore, the CEF model in the present of the molecular field
interaction should be used to describe the experimental data for CeCd3P3. As
expected from the layered crystal structure, the absolute value of
$\lambda_{ab}$ is greater than $\lambda_{c}$, implying a strong exchange
interaction in the $ab$-plane.

The obtained CEF parameters of CeCd3P3 are slightly larger than those of
CeCd3As3. The slight difference in the values of their CEF parameters is quite
surprising. When the distance between Ce and nearest As/P atoms is considered,
the difference between Ce-As distance (3.05 Å) and Ce-P distance (2.96 Å) is
about $\sim$9 pm [19, 20, 22], which might not be large enough to cause
different CEF energy level splittings. Note that the validity of the CEF
Hamiltonian must be verified below the (structural) phase transition
temperature $T_{s}$ = 127 K for CeCd3P3 [22] and $T_{s}$ = 136 K for CeCd3As3
[19].

Figure 4: CEF profiles of CeCd3As3 for three independent studies. Study A is
from Ref. [20] and Study B is from Ref. [25]. (a) CEF energy level splittings
and eigenstates. Present study: $\alpha~{}=~{}0.44$, $\beta~{}=~{}0.90$, and
$\gamma~{}=~{}-1$. Study A: $\alpha~{}=~{}0.32$, $\beta~{}=~{}0.95$, and
$\gamma~{}=~{}1$. Study B: $\alpha~{}=~{}0.28$, $\beta~{}=~{}0.96$, and
$\gamma~{}=~{}1$. (b) Comparison between $C_{m}$ of present study and CEF
calculations based on the three independent studies, where $\lambda_{i}=0$.

In Fig. 4(a) we compare the energy level splittings and eigenfunctions for
three independent CEF analyses of CeCd3As3. For all three studies the CEF
parameters are obtained from fits to the magnetic susceptibility curves. In
this study, the Hamiltonian includes the molecular field term. In Ref. [20]
(Study A), the CEF parameters are obtained in the presence of
antiferromagnetic exchange interaction based on a mean-field approach. In Ref.
[25] (Study B), the CEF parameters are evaluated by fitting the magnetic
susceptibility curves to only ${\cal H}_{CEF}$ (without any interaction term).

For all three studies, the ground state ($\Gamma_{1}$) is in a mixed state of
$|\pm 5/2\rangle$ and $|\mp 1/2\rangle$ with a higher probability in the $|\mp
1/2\rangle$ state. This requires a mixing angle $\theta$ in the wave function:
$\cos(\theta)|\pm 5/2\rangle+\sin(\theta)|\mp 1/2\rangle$. The obtained mixing
angle is roughly similar for all three studies: 64∘ in this study, 72∘ in Ref.
[20], and 74∘ in Ref. [25]. Unlike the ground state, the excited states
$\Gamma_{2}$ and $\Gamma_{3}$ do not entirely agree for all three studies. In
Ref. [20] there is a clear swap between $\Gamma_{2}$ and $\Gamma_{3}$ wave
functions (Study A). This is caused by the relatively high $|B_{4}^{0}|$ value
(= 1.4 K). In fact, we confirmed that any $|B_{4}^{0}|>0.7$ K would result in
the $\Gamma_{2}$ being in a mixed state and the $\Gamma_{3}$ being in a pure
state, just as the case in Ref. [20]. Another important distinction among
these three studies is in the energy level splittings. The energy eigenvalue
for the second excited state in Ref. [25] (Study B) is roughly two times
smaller than that of the other two studies. However, the energy level
splitting from the ground to the first excited state ($\sim$240 K) is
comparable for all studies, clearly indicating that the ground state is well
isolated from the excited states.

Figure 4 (b) shows the magnetic part of the specific heat, together with the
calculated specific heat curves by using CEF parameters. Solid lines, dashed
lines, and dotted lines are CEF calculations from the present study, Ref.
[20], and Ref. [25], respectively. As shown in the figure, when subtle
differences are ignored, the high temperature maximum is captured by all three
calculated curves. This implies that the high temperature maximum in $C_{m}$
is due to the CEF effect and the ground state doublet is well isolated from
the excited states. When measurement uncertainty and different sample quality
are considered, the best CEF parameters among three parameter sets cannot be
selected from the comparison with $C_{m}$. Therefore, further measurements
such as inelastic neutron scattering with Cd isotopes are necessary to
distinctly specify the best CEF parameters in this system. In addition, the
CEF scheme can be determined by optical spectroscopy techniques such as Raman
scattering. Note that CEF parameters evaluated by the three independent
studies provide a qualitatively good description of the experimental $M/H$
curves.

The significance of $B_{4}^{3}$ CEF parameter has been observed in Ce-based
antiferromagnets such as CeAuSn, CeIr3Ge7, and CeCd${}_{3}X_{3}$, where Ce
ions are in a trigonal environment [36, 28, 25]. These compounds indicate a
large magnetic anisotropy with the $ab$-plane being the magnetic easy plane,
which can be qualitatively explained by the CEF effect. A detailed CEF
analysis based on both the magnetic susceptibility and inelastic neutron
scattering data of hexagonal CeAuSn indicates a mixture of $|\pm 5/2\rangle$
and $|\mp 1/2\rangle$ CEF ground state doublet, a pure $|\pm 3/2\rangle$
doublet as the first excited state at $\sim$345 K, and a mixture of $|\pm
5/2\rangle$ and $|\mp 1/2\rangle$ doublet as the second excited state at
$\sim$440 K [36, 28]. The anisotropy ratio of magnetic susceptibility between
$H\parallel ab$ and $H\parallel c$ is found to be $\chi_{ab}/\chi_{c}\sim 15$
near $T_{N}$. Both magnetic susceptibility [28] and neutron scattering [36]
CEF evaluations clearly show a significant $B_{4}^{3}$ contribution ($\sim$19
K) with a large mixing angle, which is consistent with the CEF analysis of
CeCd${}_{3}X_{3}$. The anisotropy ratio of CeCd${}_{3}X_{3}$
($\chi_{ab}/\chi_{c}\sim 36$ at 1.8 K) is larger than that of CeAuSn because
both $B_{2}^{0}$ and $B_{4}^{3}$ CEF parameters of CeCd${}_{3}X_{3}$ are
larger than those of CeAuSn. The CEF investigation of the rhombohedral
CeIr3Ge7 compound shows a very similar CEF eigenstates and eigenvalues with
those of other compounds. However, in CeIr3Ge7, the reported CEF parameters
(especially the term $B_{4}^{3}=67.3$ K) are larger than that of other
compounds, thus inducing a huge energy level splittings of 374 K and 1398 K.
[25]. It has been suggested that the exceptionally large CEF splitting can be
related to the contribution of the $5d$ ligands of Ir atoms. [25]. In
addition, the CEF analysis on rhombohedral CePtAl4Ge2 antiferromagnet has also
been conducted [29]. Unlike the above mentioned compounds, the ground state
and the second excited state of CePtAl4Ge2 are not in a mixed configuration of
$|5/2\rangle$ and $|1/2\rangle$ states. The sign and magnitude of $B_{2}^{0}$
(= 13.26 K) and $B_{4}^{0}$ (= $-0.3$ K) CEF parameters in CePtAl4Ge2 are
comparable to that of CeAuSn, CeIr3Ge7, and CeCd3X3 ($X$ = P and As). However,
because the $B_{4}^{3}$ term responsible for mixing is exceptionally small in
CePtAl4Ge2 system ($B_{4}^{3}=0\pm 0.02$ K), the ground state and second
excited state is in a pure $|\pm 1/2\rangle$ state and a pure $|\mp
5/2\rangle$ state, respectively. We found that the ground and excited states
are without mixing for any $|B_{4}^{3}|<1.1$ K. The small value of $B_{2}^{0}$
and $B_{4}^{3}$ implies a relatively smaller magnetic anisotropy in
CePtAl4Ge2, which is clearly reflected on its magnetic susceptibility data
($\chi_{ab}/\chi_{c}\sim 4$ near $T_{N}$) [29].

Figure 5: Temperature dependence of the thermoelectric power, $S(T)$, of
$R$Cd3$X$3 ($R$ = La and Ce, $X$ = P and As). Vertical arrows indicate the
phase transition temperatures observed in electrical resistivity measurements
[22, 19].

Although our CEF analysis on CeCd3$X$3 ($X$ = P and As) provides a
comprehensive picture at high temperatures, a number of unanswered questions
remains at low temperatures. When the temperature is much lower than the CEF
splitting, the lowest Kramers doublet is only relevant to explain the observed
magnetic ordering at $T_{\text{N}}=0.42$ K and upturn in $C_{m}$ below 10 K.
It is obvious that the temperature dependence and absolute value of $C_{m}$
below 10 K cannot be explained by the CEF effects as shown in Figs. 3(c) and
4(c).

Since magnetization isotherms at $T$ = 1.8 K for both compounds are reproduced
well by CEF calculation with the ground state wave functions, the reduced
magnetization value cannot be associated with the Kondo screening. This is
consistent with the electrical resistivity results of CeCd3$X$3 [19, 22]. The
absence of Kondo effect in CeCd3$X$3 is also confirmed from thermoelectric
power (TEP) measurements, as shown in Fig. 5. The observed TEP value of
LaCd3$X$3 is an order of magnitude higher than that of typical metals,
implying low carrier density system. The temperature dependence of the TEP,
$S(T)$, of both La- and Ce-based compounds shows a hump at low temperatures,
which can be related to the phonon drag. In general, $S(T)$ of typical metals
shows a maximum, corresponding to the phonon-drag effect, where the maximum is
expected to be located between $\Theta_{D}/5$ and $\Theta_{D}/12$ [37]. Many
Ce- and Yb-based Kondo lattice systems have shown that $S(T)$ indicates an
extrema with enhanced value, corresponding to the Kondo effect in conjunction
with CEF effect. The TEP of CeCd3$X$3 exhibits behavior similar to that of
LaCd3$X$3, implying negligible Kondo contributions. Hence, as suggested in
Refs. [19, 22], the enhancement of the specific heat below 10 K is likely
related to either the magnetic frustration in triangular lattices [19, 22, 18,
20, 21] or simply the magnetic fluctuations observed in insulating
antiferromagnets [38].

The electrical resistivity of CeCd3$X$3 compounds exhibits a metallic
behavior, suggesting that Ruderman-Kittel-Kasuya-Yosida (RKKY) interaction may
be responsible for the magnetic ordering. However, it would have to be
mediated by an extremely small number of charge carriers [19, 22]. It has been
qualitatively shown that the magnetic ordering temperature of non-Kondo
materials scale with the distance between Ce ions, where the larger the Ce-Ce
distance results in a smaller ordering temperature [39]. For example, a non-
Kondo metal CeIr3Ge7 orders at an extremely low temperature
$T_{\text{N}}=0.63$ K due to the large Ce-Ce distance ($\sim$6 Å). When the
Ce-Ce distance ($\sim$4 Å) for CeCd3$X$3 is considered, the magnetic ordering
temperature is significantly suppressed compared to that of other Ce-based
non-Kondo systems. On the contrary, it has been suggested that the
superexchange interaction in low carrier density YbAl3C3 compound becomes
dominant instead of the RKKY interaction, where the carrier concentration is
estimated to be $n\sim$0.01 per formula unit (f.u.) [14]. When the carrier
concentrations of CeCd3As3 ($n\sim$ 0.003/f.u.) [19] and CeCd3P3 ($n\sim$
0.002/f.u.) [22] compounds are considered, it is reasonable to assume that the
superexchange interaction may be responsible for the antiferromagnetic
ordering below 0.42 K. In addition, the partial $H-T$ phase diagram of these
compounds, especially the field-induced increase of $T_{\text{N}}$, is similar
to that of 2D insulating triangular lattice systems with easy-plane anisotropy
[41, 40]. Furthermore, the low temperature specific heat of CeCd3As3 has been
explained by anisotropic exchange Hamiltonian for an insulating, layered
triangular lattice [20].

##  IV Conclusion

At high temperatures, the observed magnetic properties of CeCd3$X$3 triangular
lattice compounds can be well understood by considering the CEF effects with
molecular filed contributions. The large anisotropy in the magnetic
susceptibility and magnetization and the electronic Schottky anomaly in the
specific heat are explained by energy level splittings of the $J$ = 5/2 Hund’s
rule ground state of Ce3+ ions into three doublets. The striking similarity of
the CEF profile of both compounds implies a very close resemblance of their
crystal field environment. Three independent CEF analyses on CeCd3As3 indicate
inconsistent CEF profiles, requiring further studies such as inelastic neutron
scattering. When the temperature is well below the CEF splitting, the well-
isolated Kramers’ doublet ground state is responsible for the
antiferromagnetic ordering and the large enhancement of specific heat below 10
K. Further measurements such as magnetization, neutron scattering, and nuclear
magnetic resonance are necessary to provide additional insight into the nature
of magnetism below $T_{\text{N}}$ and the role of anisotropic exchange
interactions in the triangular motif.

###### Acknowledgements.

This work was supported by the Canada Research Chairs, Natural Sciences and
Engineering Research Council of Canada, and Canada Foundation for Innovation
program. EM was supported by the Korean Ministry of Science and ICT (No.
2021R1A2C2010925) and by BrainLink program funded by the Ministry of Science
and ICT (2022H1D3A3A01077468) through the National Research Foundation of
Korea.

## References

  * [1] W.-J. Hu, S.-S. Gong, W. Zhu, and D. N. Sheng, Phys. Rev. B 92, 140403(R) (2015).
  * [2] Y.-D. Li, X. Wang, and G. Chen, Phys. Rev. B 94, 035107 (2016).
  * [3] Y. Iqbal, W.-J. Hu, R. Thomale, D. Poilblanc, and F. Becca, Phys. Rev. B 93, 144411 (2016).
  * [4] S.-S. Gong, W. Zhu, J.-X. Zhu, D. N. Sheng, and K. Yang, Phys. Rev. B 96, 075116 (2017).
  * [5] Z. Zhu, P. A. Maksimov, S. R. White, and A. L. Chernyshev, Phys. Rev. Lett. 120, 207203 (2018).
  * [6] J. G. Rau and M. J. P. Gingras, Phys. Rev. B 98, 054408 (2018).
  * [7] Y. Li, H. Liao, Z. Zhang, S. Li, F. Jin, L. Ling, L. Zhang, Y. Zou, L. Pi, Z. Yang, J. Wang, Z. Wu, and Q. Zhang, Sci. Rep. 5, 16419 (2015).
  * [8] Y. Li, G. Chen, W. Tong, L. Pi, J. Liu, Z. Yang, X. Wang, and Q. Zhang, Phys. Rev. Lett. 115, 167203 (2015).
  * [9] Y. Shen, Y.-D. Li, H. Wo, Y. Li, S. Shen, B. Pan, Q. Wang, H. Walker, P. Steffens, M. Boehm, Y. Hao, D. L. Quintero-Castro, L. W. Harriger, M. D. Frontzek, L. Hao, S. Meng, Q. Zhang, G. Chen, and J. Zhao, Nature 540, 559 (2016).
  * [10] Y. Li, D. Adroja, P. K. Biswas, P. J. Baker, Q. Zhang, J. Liu, A. A. Tsirlin, P. Gegenwart, and Q. Zhang, Phys. Rev. Lett. 117, 097201 (2016).
  * [11] J. A. Paddison, M. Daum, Z. Dun, G. Ehlers, Y. Liu, M. B. Stone, H. Zhou, and M. Mourigal, Nat. Phys. 13, 117 (2017).
  * [12] M. Baenitz, P. Schlender, J. Sichelschmidt, Y. A. Onykiienko, Z. Zangeneh, K. M. Ranjith, R. Sarkar, L. Hozoi, H. C. Walker, J.-C. Orain, H. Yasuoka, J. van den Brink, H. H. Klauss, D. S. Inosov, and T. Doert, Phys. Rev. B 98, 220409(R) (2018).
  * [13] J. Sichelschmidt, P. Schlender, B. Schmidt, M. Baenitz, and T. Doert, J. Phys.: Condens. Matter 31, 205601 (2019).
  * [14] A. Ochiai, T. Inukai, T. Matsumura, A. Oyamada, and K. Katoh, J. Phys. Soc. Jpn. 76, 123703 (2007).
  * [15] Y. Kato, M. Kosaka, H. Nowatari, Y. Saiga, A. Yamada, T. Kobiyama, S. Katano, K. Ohoyama, H. S. Suzuki, N. Aso, and K. Iwasa, J. Phys. Soc. Jpn. 77, 053701 (2008).
  * [16] A. Ochiai, K. Hara, F. Kikuchi, T. Inukai, E. Matsuoka, H. Onodera, S. Nakamura, T. Nojima, and K. Katoh, J. Phys.: Conf. Ser. 200, 022040 (2010).
  * [17] K. Hara, S. Matsuda, E. Matsuoka, K. Tanigaki, A. Ochiai, S. Nakamura, T. Nojima, and K. Katoh, Phys. Rev. B 85, 144416 (2012).
  * [18] Y. Liu, S. Zhang, J. Lv, S. Su, T. Dong, G. Chen, and N. Wang, arXiv preprint arXiv:1612.03720 (2016).
  * [19] S. R. Dunsiger, J. Lee, J. E. Sonier, and E. D. Mun, Phys. Rev. B 102, 064405 (2020).
  * [20] K. E. Avers, P. A. Maksimov, P. F. S. Rosa, S. M. Thomas, J. D. Thompson, W. P. Halperin, R. Movshovich, and A. L. Chernyshev, Phys. Rev. B 103, L180406 (2021).
  * [21] S. Higuchi, Y. Noshima, N. Shirakawa, M. Tsubota, and J. Kitagawa, Mater. Res. Express 3, 056101 (2016).
  * [22] J. Lee, A. Rabus, N. R. Lee-Hone, D. M. Broun, and E. Mun, Phys. Rev. B 99, 245159 (2019).
  * [23] S. S. Stoyko and A. Mar, Inorg. Chem. 50, 11152 (2011).
  * [24] A. Ochiai, N. Kabeya, K. Maniwa, M. Saito, S. Nakamura, and K. Katoh, Phys. Rev. B 104, 144420 (2021).
  * [25] J. Banda, B. K. Rai, H. Rosner, E. Morosan, C. Geibel, and M. Brando, Phys. Rev. B 98, 195120 (2018).
  * [26] A. Scheie, J. Appl. Crystallogr. 54, 356 (2021).
  * [27] P. C. Canfield and Z. Fisk, Philos. Mag. B 65, 1117 (1992).
  * [28] C. L. Huang, V. Fritsch, B. Pilawa, C. C. Yang, M. Merz, and H. v. Löhneysen, Phys. Rev. B 91, 144413 (2015).
  * [29] S. Shin, V. Pomjakushin, L. Keller, P. F. S. Rosa, U. Stuhr, C. Niedermayer, R. Sibille, S. Toth, J. Kim, H. Jang, S.-K. Son, H.-O. Lee, T. Shang, M. Medarde, E. D. Bauer, M. Kenzelmann, and T. Park, Phys. Rev. B 101, 224421 (2020).
  * [30] K. W. H. Stevens, Proc. Phys. Soc. A 65, 209 (1952).
  * [31] M. T. Hutchings, Solid State Phys. 16, 227 (1964).
  * [32] C. Klingner, C. Krellner, M. Brando, C. Geibel, and F. Steglich1, New J. Phys. 13 083024 (2011).
  * [33] Y.-L. Wang, Physics Letters A 35, 383 (1971).
  * [34] G. J. Bowden, D. S. P. Bunbury, and M. A. H. McCausland, J. Phys. C: Solid State Phys. 4 1840 (1971).
  * [35] N. Shohata, J. Phys. Soc. Jpn. 42, 1873 (1977).
  * [36] D. T. Adroja, B. D. Rainford, and A. J. Neville, J. of Phys.: Condens. Matter 9, L391 (1997).
  * [37] F. J. Blatt, P. A. Schroeder, C. L. Foiles, and D. Greig, Springer US, Boston, MA (1976).
  * [38] W. K. Robinson and S. A. Friedberg, Phys. Rev. 117, 402 (1960).
  * [39] Binod K. Rai, Jacintha Banda, Macy Stavinoha, R. Borth, D.-J. Jang, Katherine A. Benavides, D. A. Sokolov, Julia Y. Chan, M. Nicklas, Manuel Brando, C.-L. Huang, and E. Morosan, Phys. Rev. B 98, 195119 (2018).
  * [40] L. Seabra, T. Momoi, P. Sindzingre, and N. Shannon, Phys. Rev. B 84, 214418 (2011).
  * [41] D. H. Lee, J. D. Joannopoulos, J. W. Negele, and D. P. Landau, Phys. Rev. B 33, 450 (1986).