11institutetext: Department of Physics, Gustaf Hällströmin katu 2 A,
University of Helsnki, Helsinki, Finland 22institutetext: Helsinki Institute
of Physics, Gustaf Hällströmin katu 2, University of Helsinki, Helsinki,
Finland 33institutetext: Max-Planck institute for Extraterrestrial physics,
Giessebachstr, Garching 85748, Germany 44institutetext: Kavli Institute for
Particle Astrophysics & Cosmology, P. O. Box 2450, Stanford University,
Stanford, CA 94305, USA; SLAC National Accelerator Laboratory, Menlo Park, CA
94025, USA 55institutetext: IRAP, Université de Toulouse, CNRS, UPS, CNES,
Toulouse, France 66institutetext: Astrophyics Research Institute, Liverpool
John Moores University, IC2, Liverpool Science Park, 146 Brownlow Hill,
Liverpool L3 5RF, UK 77institutetext: Instituto de Astrofísica, Pontificia
Universidad Católica de Chile, Av. Vicuna Mackenna 4860, 782-0436 Macul,
Santiago, Chile

# Clustering of CODEX clusters

V. Lindholm 1122 A. Finoguenov 11 J. Comparat 33 C. C. Kirkpatrick 1122 E.
Rykoff 44 N. Clerc 55 C. Collins 66 S. Damsted 11 J. Ider Chitham 33 N.
Padilla 77

(Received ; accepted later)

###### Abstract

Context. The clustering of galaxy clusters links the spatial nonuniformity of
dark matter halos to the growth of the primordial spectrum of perturbations.
The amplitude of the clustering signal is widely used to estimate the halo
mass of astrophysical objects. The advent of cluster mass calibrations enables
using clustering in cosmological studies.

Aims. We analyze the autocorrelation function of a large contiguous sample of
galaxy clusters, the Constrain Dark Energy with X-ray (CODEX) sample, in which
we take particular care of cluster definition. These clusters were X-ray
selected using the ROentgen SATellite (ROSAT) All-Sky Survey (RASS) and then
identified as galaxy clusters using the code redMaPPer run on the photometry
of the Sloan Digital Sky Survey (SDSS). We develop methods for precisely
accounting for the sample selection effects on the clustering and demonstrate
their robustness using numerical simulations.

Methods. Using the clean CODEX sample, which was obtained by applying a
redshift-dependent richness selection, we computed the two-point
autocorrelation function of galaxy clusters in the $0.1<z<0.3$ and $0.3<z<0.5$
redshift bins. We compared the bias in the measured correlation function with
values obtained in numerical simulations using a similar cluster mass range.

Results. By fitting a power law, we measured a correlation length
$r_{0}=18.7\pm 1.1$ and slope $\gamma=1.98\pm 0.14$ for the correlation
function in the full redshift range. By fixing the other cosmological
parameters to their nine-year Wilkinson Microwave Anisotropy Probe (WMAP)
values, we reproduced the observed shape of the correlation function under the
following cosmological conditions: $\Omega_{m_{0}}=0.22^{+0.04}_{-0.03}$ and
$S_{8}=\sigma_{8}(\Omega_{m_{0}}/0.3)^{0.5}=0.85^{+0.10}_{-0.08}$ with
estimated additional systematic errors of $\sigma_{\Omega_{m_{0}}}=0.02$ and
$\sigma_{S_{8}}=0.20$. We illustrate the complementarity of clustering
constraints by combining them with CODEX cosmological constraints based on the
X-ray luminosity function, deriving $\Omega_{m_{0}}=0.25\pm 0.01$ and
$\sigma_{8}=0.81^{+0.01}_{-0.02}$ with an estimated additional systematic
error of $\sigma_{\Omega_{m_{0}}}=0.07$ and $\sigma_{\sigma_{8}}=0.04$. The
mass calibration and statistical quality of the mass tracers are the dominant
source of uncertainty.

###### Key Words.:

galaxy clusters – cosmology

##  1 Introduction

Galaxy clusters are the largest gravitationally bound objects in the Universe.
A common assumption is that they completely and uniquely trace the population
of the high-mass dark matter halos. Thus galaxy clusters form a powerful probe
for the large-scale structure of the Universe. This power is further enhanced
by the fact that several of the galaxy cluster properties, such as the
abundance as a function of total mass and spatial clustering, can be predicted
based on a cosmological model. A particularly important aspect of the
clustering of clusters is that they are biased tracers of the underlying
matter distribution, meaning that their clustering amplitude is higher than
that of the full distribution of matter. Moreover, the amount of enhancement
grows with increasing cluster masses. By studying the relationship between
cluster masses and bias, we can gain further insights into the cosmology (see,
e.g., Mo & White, 1996 and Sheth & Tormen, 1999)

Because the clustering amplitude of dark matter halos of a given mass is
sensitive to the underlying cosmology, the application of the clustering
theory to galaxy clusters is theoretically highly motivated. Moreover, galaxy
clusters exhibit scaling relations between their baryonic properties and the
total mass of their hosting halos. These properties include the cluster X-ray
luminosity and richness (i.e., the number of galaxies belonging to the
cluster). Using these observable quantities as mass proxies on the one hand
and the connection between cluster masses and their bias on the other, we can
make inference on the cosmological model. Most attempts to follow this route
have resulted in cosmological parameters that disagree with the constraints
obtained using the number counts of the same sample (Schuecker et al., 2002),
however, or lead to strongly disagreeing scaling relations (Jimeno et al.,
2017). Remarkably, Allevato et al. (2012) obtained a precise agreement between
the modeling of the clustering based on the weak-lensing mass calibration and
the measured clustering amplitudes of galaxy groups by taking the definition
of the object and the effects of sample variance into account.

The goal of this paper is to measure the clustering of galaxy clusters
detected in the galaxy cluster survey called Constrain Dark Energy with X-ray
(CODEX) (Finoguenov et al., 2020) by computing their auto two-point
correlation function. A brief description of the CODEX catalog is given in
Sect. 2. Furthermore, we aim at predicting the excess clustering, quantified
by the bias factor, based on the cluster masses and a cosmological prediction
for the total matter distribution. The details of this procedure are presented
in Sect. 3, which is a continuation of the developments presented in Allevato
et al. (2011) and Allevato et al. (2012). In Sect. 4 we apply this pipeline to
a simulated dark matter halo catalog to ensure that the predicted and measured
clustering amplitudes match. In Sect. 5 we present the clustering measurements
for the CODEX cluster catalog. Finally, in Sect. 6 we use the measured and
predicted clustering amplitudes to constrain two parameters within the
spatially flat $\Lambda$CDM cosmology: the matter density parameter
$\Omega_{m_{0}}$ , and the power spectrum normalization $\sigma_{8}$. Similar
analyses have been performed, for example, by Marulli et al. (2018) using data
from another X-ray selected survey, the XXL survey (Pierre et al., 2016), and
by Mana et al. (2013) for a cluster sample selected using the maxBCG red-
sequence method from Sloan Digital Sky Survey (SDSS) photometric data (Koester
et al., 2017). A key improvement with the CODEX catalog compared to the first
analysis is the significantly larger sample size (1892 clusters in our
analysis here compared to 187 clusters), and compared to the second analysis,
we gain an improvement through the X-ray selection.

##  2 CODEX galaxy cluster survey and its modeling

The CODEX galaxy cluster survey is constructed by performing the detection of
faint X-ray sources in the ROentgen SATellite (ROSAT) All-Sky Survey (RASS)
and a subsequent identification of those sources using the redMaPPer algorithm
(Rykoff et al., 2014) applied to the SDSS photometry inside the 10,000 square
degree area of the Baryon Oscillation Spectroscopic Survey (BOSS) footprint. A
detailed description of the survey and the catalog is presented in Finoguenov
et al. (2020). Spectroscopic identification of the sample has been a target of
the SPectroscopic IDentification of eROSITA Sources (SPIDERS) program of SDSS-
IV, with first results presented in Clerc et al. (2016) and Clerc et al.
(2020). These first results confirmed the high quality of the redMaPPer
redshifts and the virialized nature of CODEX clusters.

To perform the clustering analysis, we selected the clean CODEX catalog by
applying a richness cut

$\exp(\lambda)>22(z/0.15)^{0.8},$ (1)

where z denotes the redshift of the cluster and
$\lambda\equiv\ln(\mathrm{SDSS\;Richness})$ (defined at the optical peak, with
a detailed description provided in Rykoff et al., 2014). We describe the
effect of this cleaning as a $P^{\mathrm{RASS}}(I|\lambda,z)$ term in the
modeling. Because we use multivariate log-normal distributions throughout this
paper, we conveniently define the quantities $r_{c}\equiv\ln(R_{c})$ (core
radius of the X-ray surface brightness), $l\equiv\ln(L_{x})$ (rest-frame X-ray
luminosity in the 0.1-2.4 keV band), $\mu\equiv\ln(M_{200c}$) (total mass
measured within the overdensity of 200 with respect to the critical density).
In addition to the redshift-dependent richness cut, we also discarded all
clusters with richness below 25. The lowest and highest redshifts in the
cleaned catalog are 0.047 and 0.682, respectively, but we restrict our
analysis to the range $0.1<z<0.5$. After the richness cut, 1892 clusters lie
within this redshift range.

We applied the BOSS stellar mask to remove the areas affecting optical cluster
detection. We considered that the optical completeness of the CODEX catalog
above the applied richness cut does not to vary over the BOSS area and modeled
it using

$\lambda_{50\%}(z)=\ln(17.2+e^{\left(\frac{z}{0.32}\right)^{2}}),$ (2)

which was obtained using the tabulations of Rykoff et al. (2014). We used an
error function with the mean of $\lambda_{50\%}(z)$ and a $\sigma=0.2$, which
reproduces the 75% and 90% quantiles of the distribution tabulated in Rykoff
et al. (2014). We used the probability of the optical detection of the cluster
in SDSS data as

$P^{\mathrm{SDSS}}(I|\lambda,z)=1-0.5\mathrm{erfc}\left(\frac{\lambda-\lambda_{50\%}}{0.2\sqrt{2}}\right).$
(3)

We verified the lack of sensitivity toward variations in the photometric
depths using an agreement in the clustering signal between Northern and
Southern Galactic Cap areas and using the tests for the presence of artificial
correlation due to the bright stars.

The RASS survey has large spatial inhomogeneities in its coverage; the
limiting flux changes by a factor of 10. To properly account for the variation
in the spatial distribution caused by it, we generated a random catalog in
which the number of objects was six times higher than in the real catalog. We
divided the survey area into 100 zones of equal sensitivity $S$, with a 12%
step in flux sensitivity between the subsequent zones. We denote the sky area
of these zones as $\Delta\Omega_{S}$. We computed the probability of cluster
detection

$P(I|S,\mu,z,\nu)=\iiint\mathrm{d}l^{\rm
true}\mathrm{d}r_{c}\mathrm{d}\eta^{\rm ob}P(I|\eta^{\rm
ob},\beta(\mu),r_{c})\\\ P(\eta^{\rm ob}|\eta^{\rm true}(l^{\rm
true},S,z))P(r_{c},l^{\rm true}|\mu,\nu,z),$ (4)

where $\eta$ denotes X-ray count (superscript ”true” stands for predicted and
”ob” for observed),
$\nu\equiv\frac{\lambda-\langle\lambda|\mu,z\rangle}{\sigma_{\lambda|\mu}}$,
and all the probabilities are described in detail in Finoguenov et al. (2020).
This modeling accounts for the effect of the X-ray shape ($r_{c}$, $\beta$) of
the clusters and for the RASS sensitivity on the cluster selection, and
predicts changes in the distribution of X-ray shapes based on the measured
covariance of cluster properties (Cavaliere & Fusco-Femiano, 1976; Mulroy et
al., 2019; Farahi et al., 2019; Käfer et al., 2019). In this way, we accounted
for the effect of the anticorrelation between the scatter of the X-ray
luminosity and the optical richness and of the anticorrelation of the core
radii of galaxy clusters and their scatter in luminosity. Our simulations
reproduce the correct mix of shapes, luminosities, and richnesses of galaxy
clusters. They were then used for the cluster detection modeling in all areas
of the survey.

We estimated the expected number of clusters in each bin of redshift as

$\langle N(\Delta z)\rangle=\Delta\Omega_{S}\int_{\Delta
z}\mathrm{d}z\frac{\mathrm{d}V}{\mathrm{d}z\mathrm{d}\Omega}(z)\iint\mathrm{d}\mu\mathrm{d}\lambda\frac{\mathrm{d}n(\mu,\lambda,S,z)}{\mathrm{d}\mu\mathrm{d}\lambda\mathrm{d}V},$
(5)

where

$\frac{\mathrm{d}n(\mu,\lambda,S,z)}{\mathrm{d}\mu\mathrm{d}\lambda\mathrm{d}V}=P^{\mathrm{RASS}}(I|\lambda,z)P^{\mathrm{SDSS}}(I|\lambda,z)\\\
P(I|S,\mu,z,\nu)P(\lambda|\nu,\mu)\frac{\mathrm{d}n(\mu,z)}{\mathrm{d}V\mathrm{d}\mu}\,.$
(6)

Fig. 2 shows a correspondence of the slope of the dn/dz distribution of the
real clusters and the random catalog. They agree well.

Figure 1: Sky footprint of the subset of the CODEX catalog used to compute the
two-point correlation function. Orange points show the clusters, and blue
points show the random points. Figure 2: Redshift distribution ($dn/dz$) of
the subset of the CODEX catalog used to compute the two-point correlation
function along with the corresponding random catalog. The area of the two
histograms is normalized to 1.

##  3 Analysis methods

Our clustering analysis consists of first estimating the clustering of the
clusters by computing their two-point correlation function; next, computing
the expected bias of the sample from the cluster masses and redshifts; then,
computing a prediction for the clustering signal by scaling a prediction for
dark matter two-point correlation by the square of the predicted bias; and
finally, comparison between the measured and predicted signals.

We used the widely adopted Landy-Szalay estimator (Landy & Szalay, 1993) to
estimate the two-point correlation function from our cluster sample. The
estimator was constructed from pairs within the cluster catalog ($DD$), pairs
within the random catalog ($RR$), and pairs between the two ($DR$):

$\xi(\@vec{r})=\frac{n_{R}(n_{R}-1)}{n_{D}(n_{D}-1)}\frac{DD(\@vec{r})}{RR(\@vec{r})}-\frac{n_{R}(n_{R}-1)}{n_{D}n_{R}}\frac{DR(\@vec{r})}{RR(\@vec{r})}+1,$
(7)

where $\@vec{r}$ is a vector encoding arbitrary separation bins, $n_{D}$ is
the total number of clusters, and $n_{R}$ is the total number of random
points. The simplest way to bin number counts is by their three-dimensional
distance. This estimate is distorted by changes in cluster positions along the
line-of- sight direction due to redshift caused by their peculiar velocities,
however. These redshift space distortions can be minimized by estimating the
so-called projected two-point correlation function (Dabis & Peebles, 1983).
The projected two-point correlation function is the line-of-sight integral of
two-point correlation function that has been binned in distance of the points
along directions parallel and perpendicular to the line-of-sight direction:

$w_{p}(r_{p})=2\int_{\pi_{\mathrm{min}}}^{\pi_{\mathrm{max}}}\xi(r_{p},\pi)\mathrm{d}\pi.$
(8)

The upper limit of the integral is selected in a way that increasing it would
only increase noise and not the signal.

We estimated the covariance matrix of the two-point correlation function using
the jackknife method: we split the sample into $M$ subsections of the sky and
computed a set of two-point correlation functions by excluding one subsection
at a time. The covariance matrix element $C_{ij}$ was then computed as

$C_{ij}=\frac{M-1}{M}\sum_{k=1}^{M}[\xi_{k}(r_{i})-\langle\xi_{k}(r_{i})\rangle][\xi_{k}(r_{j})-\langle\xi_{k}(r_{j})\rangle],$
(9)

where $\langle\xi_{k}(r_{j})\rangle$ is the mean over $M$ subsections. All the
error bars we show for the two-point correlation function estimates are then
the square root of the diagonal of this matrix, $\sigma_{i}=\sqrt{C_{ii}}$

As discussed in the introduction, galaxy clusters are biased tracers of the
total matter distribution, and their clustering bias is connected to dark
matter masses of their host halos. The goal of our analysis is to compare
mass-based cluster bias predictions to the actual bias measured from the two-
point correlation function estimate. Thus a key ingredient in our analysis is
the relation between cluster masses and their biases. It is possible to
predict the clustering bias based on the mass function $n(M)$, that is, the
number density of halos of a given mass, using the so-called peak background
split (see, e.g., Mo & White, 1996 and Sheth & Tormen, 1999). In this approach
it is customary to consider masses in terms of the variance of the linear
matter power spectrum $P(k,z)$,

$\sigma^{2}(M,z)=4\pi^{2}\int_{0}^{\infty}P(K,z)W^{2}(k,M)k^{2}\mathrm{d}k,$
(10)

where $W(k,M)$ is the Fourier transform of a top-hat window function at
$R=(3M/4\pi\overline{\rho}_{M})^{1/3}$ that encloses mass $M$. Here
$\overline{\rho}_{M}$ is the mean matter density in the Universe. For cleaner
notation, we write in in Eqs. 11-14 $\sigma$ instead of $\sigma(M,z)$. Now the
halo mass function can be expressed as

$n(M)\mathrm{d}M=f(\sigma)\frac{\overline{\rho}_{M}}{M^{2}}\frac{\mathrm{d}\ln\sigma^{-1}}{\mathrm{d}\ln
M}\mathrm{d}M,$ (11)

where $f(\sigma)$ is so-called multiplicity function. It is simply the
fraction of mass contained in halos in a unit range of $\mathrm{d}\ln\sigma$.
Using the ellipsoidal collapse model, Sheth, Mo & Tormen (2001) arrived at a
parameterized multiplicity function,

$\begin{split}f_{\mathrm{ST}}(\sigma;A,a,p)&=A\sqrt{\frac{2}{\pi}}\left[1+\left(\frac{\sigma^{2}}{a^{2}\delta_{c}^{2}}\right)^{p}\right]\cdots\\\
\cdots&\left(\frac{\sqrt{a}\delta_{c}}{\sigma}\right)\exp\left[-\frac{a}{2}\frac{\delta_{c}^{2}}{\sigma^{2}}\right],\end{split}$
(12)

where$\delta_{c}=1.686$ is the critical density for halo collapse. To improve
the compatibility with $N$-body simulations, Bhattacharya et al. (2011)
introduced an additional ad hoc parameter $q$, which is a function of
redshift, and changed

$\left(\frac{\sqrt{a}\delta_{c}}{\sigma}\right)\rightarrow\left(\frac{\sqrt{a}\delta_{c}}{\sigma}\right)^{q}$

and consequently allowed parameters $(A,a,p)$ in Eq. 12 to evolve with
redshift. By following the procedure of computing ratio of conditional and
unconditional mass function (from Sheth & Tormen, 1999), we can express the
halo bias using the parameters $(a,p,q)$ of the halo mass function model,

$\begin{split}b(\sigma,a,p,q)&=1+\frac{a(\delta_{c}/\sigma)^{2}-q}{\delta_{c}}\\\
&\cdots+\frac{2p/\delta_{c}}{1+(a(\delta_{c}/\sigma)^{2})^{p}}\end{split}.$
(13)

The parameters of this model can be calibrated by identifying dark matter
halos in $N$-body simulations and estimating the clustering amplitudes of halo
populations in different mass bins and comparing them to the total matter
distribution. Instead of semianalytical formulas based on halo mass function,
we can also consider purely empirical fitting functions, as was done by Tinker
et al. (2010), for instance. They allow a more flexible functional form,

$b(\sigma,A,a,B,b,C,c)=1-A\frac{(\delta_{c}/\sigma)^{a}}{(\delta_{c}/\sigma)^{a}+\delta_{c}^{a}}+B(\delta_{c}/\sigma)^{b}+C(\delta_{c}/\sigma)^{c}.$
(14)

Again, the parameters $(A,a,B,b,C,c)$ were fixed by fitting $N$-body
simulations. In section 4 we consider both mass-function-based and empirical
bias-to-mass models.

With equations 13 and 14, we can predict the clustering bias of a halo
population of a given mass at a given redshift. The simplest way to use this
to estimate the clustering bias within a cluster sample is to compute the mean
bias within the sample as

$\overline{b}=\frac{1}{n_{D}}\sum_{i=1}^{n_{d}}b(M_{i},z_{i})g(z_{i}),$ (15)

where $n_{D}$ is again the number of clusters in the sample, and
$b(M_{i},z_{i})$ is the predicted bias for cluster with mass $M_{i}$ at
redshift $z_{i}$. Factor $g(z_{i})$ is a redshift-dependent correction for the
growth of structure, which is required because we include estimates across a
wide redshift range. The correction factor is defined as

$g(z)=\sqrt{\frac{w_{p}^{DM}(z,r)}{w_{p}^{DM}(0,r)}}.$ (16)

Here $w_{p}^{DM}(z,r)$ is the dark matter projected two-point correlation
function at a redshift $z$ and a scale $r$. Thus in principle, factor $g(z)$
is also a function of scale $r,$ but following Allevato et al. (2011), we
approximated it simply by $D_{1}(z)/D_{1}(0)$, where $D_{1}(z)$ is the growth
function (see, e.g., Eisenstein & Hu, 1999). If the mass estimates and mass-
to-bias conversion are correct, we expect the bias-scaled dark matter two-
point correlation function at $z=0$, that is,
$\overline{b}^{\;2}\xi_{\rm{DM}}(0,r)$, to agree with the measured two-point
correlation function. Throughout this paper all the predictions for the dark
matter two-point correlation functions are Fourier transforms from linear dark
matter power spectra computed based on Eisenstein & Hu (1998) and Eisenstein &
Hu (1999) (referred to as Eisenstein & Hu hereinafter) at redshift $z=0$. We
also tried using power spectra from the Code for Anisotropies in the Microwave
Background (CAMB) (Lewis et al., 2000), but the differences were negligible
and our pipeline implementation is faster by roughly a factor of ten when
using Eisenstein & Hu (which is important for cosmological parameter space
scanning). Thus all the results we present are based on Eisenstein & Hu.

We used the
CosmoBolognaLib111https://github.com/federicomarulli/CosmoBolognaLib
C++/python library (Marulli et al., 2016) to compute the pair counts needed to
estimate the two-point correlation function and also to divide sky into
subregions to compute the covariance matrix from the corresponding jackknife
sample. Dark matter two-point correlation function predictions, mass-to-bias
conversion, and all the other theoretical cosmology-dependent computations
were performed using the COLOSSUS222https://bitbucket.org/bdiemer/colossus
python library (Diemer, 2018).

##  4 Comparison with simulations

To validate our analysis pipeline, we ran it using a dark matter halo catalog
from the Huge MultiDark Planck (HMDPL) simulation (Prada et al., 2012; Klypin
et al., 2016). This is a dark matter only $N$-body simulation in a
$4h^{-1}\mathrm{Gpc}$ box with a cosmology that is consistent with the results
of Planck Collaboration (2014). In the case of the simulated catalog, we know
the underlying cosmology and halo masses exactly, therefore we expect to be
able to recover the halo bias at a high accuracy. The catalog we used in our
test is a light cone obtained from the HMDPL simulation. This light cone
covers the full sky in the redshift range $0.00<z<1.8$. In our clustering
analysis we masked galactic latitudes $g_{\mathrm{lat}}<10$ and picked a
subset of halos with redshifts $0.1<z<0.5$ and masses $M_{200c}>4.8\times
10^{14}h^{-1}\mathrm{M_{\odot}}\,\,$, which produces a sample with similar
masses and redshift as in our CODEX sample. After these selections, the
catalog contained 6350 halos. We estimated the covariance matrix for the two-
point correlation function by splitting the sky area into 35 jackknife
subsections.

The HMDPL catalog contains halo redshifts with and without their peculiar
motion. To validate our method in a scenario that is free of complications
from redshift-space effects and binning in two dimensions we first computed
the one-dimensional two-point correlation function $\xi(r)$ using purely
cosmological redshifts. In this case, the pair counts were binned simply in
the three-dimensional distance of the points. We computed the two-point
correlation function estimate in six bins spaced logarithmically over scales
of $10h^{-1}\mathrm{Mpc}<r<200h^{-1}\mathrm{Mpc}$. Figure 3 shows a comparison
between the measured halo two-point correlation function and a dark matter
two-point correlation prediction scaled by the square of the halo bias. The
bias estimate was obtained from the known halo masses using Eq. 15 and the
$b(M)$ calibration from Comparat et al. (2017), which is based on the HMDPL
simulation. In addition to Comparat et al. (2017) we tested three other models
for $b(M)$ from Sheth, Mo & Tormen (2001), Tinker et al. (2010), and
Bhattacharya et al. (2011). The resulting biases are presented in Table 1.
They can be compared to the bias estimate we obtained by directly fitting the
bias factor, using its definition as

$b=\sqrt{\frac{\xi(r)}{\xi_{\rm{DM}}(r)}}.$ (17)

We used our jackknife covariance matrix estimate to obtain a least-squares fit
for the bias factor, which in this case gives $b=4.33\pm 0.07$. Comparat et
al. (2017) predicted a value of $\overline{b}=4.29,$ which agrees best with
the predicted bias as expected because it was calibrated on the same
simulation that we used for validation. For the rest of this paper we use the
model of Comparat et al. (2017) as our baseline model and treat the deviations
from this as the source of the systematic uncertainty.

Figure 3: One-dimensional two-point correlation function from HMDPL halos. Top panel: Data points are the two-point correlation function estimate from the halo distribution. The solid curve is the predicted dark matter two-point correlation function scaled by $\overline{b}^{\;2}$. Bottom panel: Relative difference between the measured and predicted two-point correlation functions.  Table 1: Biases predicted using different models $b(M)$. $b(M)$ | $\overline{b}$
---|---
Sheth, Mo & Tormen (2001) | 4.04
Tinker et al. (2010) | 4.79
Bhattacharya et al. (2011) | 3.68
Comparat et al. (2017) | 4.29

We then studied the effect of including halo peculiar velocities in their
redshifts. In this case, the appropriate clustering statistics is the
projected two-point correlation function introduced in Sec. 3. Our dark matter
prediction is purely isotropic and obtained from the one-dimensional two-point
correlation function by setting
$\xi_{\rm{DM}}(r_{p},\pi)=\xi_{\rm{DM}}\left(\sqrt{r_{p}^{2}+\pi^{2}}\right)$.
The binning in $r_{p}$ direction was the same as in distance $r$ for our one-
dimensional $\xi(r)$ estimate. We chose
$\pi_{\mathrm{min}}=0h^{-1}\mathrm{Mpc}$ and
$\pi_{\mathrm{max}}=120h^{-1}\mathrm{Mpc}$ for the integral in Eq. 8. The
result of this integral is the projected two-point correlation function
$w_{p}(r_{p})$ shown in Fig. 4 along with the corresponding bias-scaled dark
matter prediction. Because the halo sample is still the same, the mass-based
bias prediction does not change compared to the one-dimensional case, but
fitting the bias gives a slightly higher value of $b=4.41\pm 0.11$. The
difference of the predicted and measured bias is slightly larger than the
$1\sigma$ uncertainty in the latter. The difference is $3\%$ of the predicted
bias, which is well within the estimated uncertainty of the $b(M)$ model
(Comparat et al., 2017).

In real data, the radial cluster distances are distorted by redshift
measurement errors in addition to their peculiar velocities. For a discussion
of this effect, see Estrada et al. (2009), for instance. To model the effect,
we measured the redshift error distribution from the CODEX clusters.
Spectroscopic redshifts are available for a subset of CODEX clusters from the
SDSS IV DR16 release of the SPIDERS cluster catalog (Ahumada et al., 2019).
Descriptions of the survey area and spectroscopic redshift assignment are
provided in Clerc et al. (2020) and Kirkpatrick et al. (2020), respectively.
For areas outside of the SPIDERS footprint, redshifts were collected from
public SDSS III data and several Nordic Optical Telescope (NOT) programs (PI
A. Finoguenov, NOT Program IDs: 48-025, 52-026, 53-020, 51-034). The redshift
assignment follows the same procedure as we used for the DR16 catalog. The
number of clusters with spectroscopic redshifts is 1223, or 65% of the entire
sample. We estimated the redshift error distribution as the difference between
spectroscopic and photometric redshift for each cluster. We then fit this
distribution with a Gaussian function of width $\sigma_{z}$ and used this
function to draw a random redshift error for each halo in the simulated
catalog. We obtained $\sigma_{z}=0.0071$ in the range $0.1<z<0.5$. The effect
this has on measured projected two-point correlation function is shown in Fig.
4. The corresponding measured bias of $4.29\pm 0.07$, which is compatible with
the bias without redshift errors and also with the predicted bias within the
statistical errors. Thus we do not expect the measurement of the projected
two-point correlation function to be biased by the redshift measurement errors
in the CODEX catalog.

Figure 4: Effect of redshift errors on the projected two-point correlation
function estimate. Top panel: Projected two-point correlation function from
HMDPL halos. Blue data points are the two-point correlation function estimate
from the halo distribution without redshift errors, and orange data points are
this estimate including redshift errors. The solid curve shows the predicted
dark matter two-point correlation function scaled by $\overline{b}^{\;2}$
computed from the halo masses. Bottom panel: Relative difference between the
measured and predicted two-point correlation functions.

##  5 Clustering of CODEX clusters

Because the predicted halo bias is compatible with the measured bias for the
simulated halos, we proceeded to apply the same analysis to the CODEX cluster
catalog. We again estimated the projected two-point correlation function. We
chose five logarithmically spaced bins over scales of
$10h^{-1}\mathrm{Mpc}<r_{p}<200h^{-1}\mathrm{Mpc}$ and integrated over scales
of $0h^{-1}\mathrm{Mpc}<\pi<120h^{-1}\mathrm{Mpc}$. We also tried using other
values for $\pi_{\mathrm{max}}$ , but $120h^{-1}\mathrm{Mpc}$ maximizes the
clustering amplitude with minimum noise. Figure 5 shows the fitted bias as a
function of $\pi_{\mathrm{max}}$. To derive the covariance matrix estimates,
we split the sky area into 16 jackknife subsections.

Fig. 6 shows the projected two-point correlation function obtained from the
CODEX catalog compared with dark matter two-point correlation functions scaled
with the predicted bias factors based on three different mass estimates. Two
estimates come from cluster X-ray luminosities ($L_{X}$) using two different
scaling relations, one adopted in the CODEX main paper (Finoguenov et al.,
2020), and the other from Capasso et al. (2020). The third estimate comes from
the cluster richness, using the summary of weak-lensing richness calibrations
presented in Kiiveri et al. (subm.). In Table 2 we show the mass-based bias
predictions. These can be compared to the bias estimate obtained by direct
fitting, which in this case is $b=3.70\pm 0.13$. The richness-based mass
estimates predict a bias of $\overline{b}=4.33,$ which is closest to the
measured value, the difference being $17\%$ of the fitted value. The
superiority of the richness-based masses is most likely due to the better
quality of its measurement compared to $L_{X}$ based on a few counts in RASS
data. Thus, we selected richness to be our baseline case in the following
sections and used the deviating results from other mass estimates to
illustrate an associated systematic uncertainty.

Figure 5: Effect of $\pi_{\mathrm{max}}$ to the clustering amplitude quantified via fitted bias $b$. Table 2: Predicted biases using different mass estimates. Mass proxy | Calibration | $\overline{b}$
---|---|---
$M_{200c}(L_{x})$ | Finoguenov et al. (2020) | 5.16
$M_{200c}(L_{x})$ | Capasso et al. (2020) | 4.52
$M_{200c}$($\lambda$) | Kiiveri et al. (subm.) | 4.33
Figure 6: Comparison of different cluster mass estimates. Top panel: projected
two-point correlation function in redshift range $0.1<z<0.5$. Data points are
two-point correlation function estimate from CODEX clusters. The solid curves
show the predicted dark matter two-point correlation function scaled by
$\overline{b}^{\;2}$ computed using the different halo mass estimates. Bottom
panel: Relative difference between the measured and predicted two-point
correlation functions. The data points have been shifted horizontally for
clarity.

To verify the robustness of our results against the $r_{p}$ range, we also ran
the analysis in the ranges $10h^{-1}\mathrm{Mpc}<r_{p}<100h^{-1}\mathrm{Mpc}$
and $20h^{-1}\mathrm{Mpc}<r_{p}<200h^{-1}\mathrm{Mpc}$. The results are listed
in Table 3. Increasing the lower limit has a stronger effect on the fitted
bias than decreasing the upper limit, but all the results are compatible
within the statistical uncertainty.

Table 3: Fitted bias using different $r_{p}$ ranges. Range | $b$
---|---
$10h^{-1}\mathrm{Mpc}<r_{p}<200h^{-1}\mathrm{Mpc}$ | $3.70\pm 0.13$
$10h^{-1}\mathrm{Mpc}<r_{p}<100h^{-1}\mathrm{Mpc}$ | $3.68\pm 0.33$
$20h^{-1}\mathrm{Mpc}<r_{p}<200h^{-1}\mathrm{Mpc}$ | $3.99\pm 0.25$

We also studied the effect of redshift binning on clustering. Figure 7
compares the CODEX clusters and predicted bias-scaled dark matter two-point
correlation functions in lower $0.1<z<0.3$ and higher $0.3<z<0.5$ redshift
samples, and for reference, also in the full range of $0.1<z<0.5$. The
corresponding comparison between predicted and fitted biases is presented in
Table 4. The difference between the predicted and measured bias for the low-
and high-redshift samples is 5% and 8% of the measured bias, respectively. The
measured high-redshift two-point correlation function appears to deviate from
the prediction at the largest scales. This might be a residual from the
limitations caused by modeling the survey effects at high redshifts. We give a
more detailed account of this matter in Appendix A. The predicted and measured
biases are also higher for the high-redshift sample. This is expected because
with increasing redshift, only massive clusters can be detected in RASS. This
effect is further reinforced by our richness cut, which discards increasingly
rich clusters at higher redshifts.

Table 4: Comparison of the measured and predicted biases in different redshift ranges. Column $b$ is the measured bias and $\overline{b}$ is the mass-based prediction. Column $n_{D}$ shows the number of clusters in each redshift bin. Redshift range | $n_{D}$ | $\overline{b}$ | $b$
---|---|---|---
$0.1<z<0.5$ | 1892 | 4.33 | $3.70\pm 0.13$
$0.1<z<0.3$ | 1250 | 3.95 | $3.78\pm 0.10$
$0.3<z<0.5$ | 642 | 5.08 | $4.71\pm 0.66$
Figure 7: Comparison of different redshift ranges. Top panel: Projected two-
point correlation function in three redshift ranges $0.1<z<0.5$, $0.1<z<0.3$
and $0.3<z<0.5$. Data points are the two-point correlation function estimates
from the CODEX clusters. The solid curves in corresponding colors show the
predicted dark matter two-point correlation function scaled by
$\overline{b}^{\;2}$ computed within each cluster subsample. Bottom panel:
Relative difference between the two-point correlation function estimate and
the corresponding prediction. The data points have been shifted horizontally
for clarity.

A common way to characterize the amplitude of the cluster two-point
correlation function is to fit a power law,

$\xi(r)=\left(\frac{r}{r_{0}}\right)^{-\gamma},$ (18)

which is found to be a good approximation at the scales $\lesssim
100\mathrm{Mpc}/h$ (see, e.g., Peacock & West, 1992). The scale at which the
correlation function crosses unity, $r_{0}$, is called the correlation length,
and determining its value has been the goal of many galaxy cluster studies.
Collins et al. (2000) measured the correlation length from another smaller
X-ray selected sample provided by the ROSAT-ESO Flux-Limited X-ray (REFLEX,
Böhringer et al., 2001) survey. The value they obtained is $r_{0}=18.8\pm
0.9,$ with a slope of $\gamma=1.83^{+0.15}_{-0.08}$ over the range of
$4\mathrm{Mpc}/h<r<40\mathrm{Mpc}/h$. To compare with this result, we
performed a least-squares fit for parameters $r_{0}$ and $\gamma$. The results
for our three redshift ranges are listed in Table 5. We measure a slightly
steeper slope, especially for the high-redshift sample, but within the errors
all the results are compatible with those of Collins et al. (2000).

Table 5: Fitted power-law parameters for different redshift ranges. Redshift range | $r_{0}$ | $\gamma$
---|---|---
$0.1<z<0.5$ | $18.7\pm 1.1$ | $1.98\pm 0.14$
$0.1<z<0.3$ | $18.2\pm 1.1$ | $2.13\pm 0.15$
$0.3<z<0.5$ | $18.1\pm 1.3$ | $1.97\pm 0.14$

##  6 Cosmology

As a of a proof-of-concept study, we performed a Markov chain Monte Carlo
(MCMC) sampling (implemented using the emcee
library333https://github.com/dfm/emcee, Foreman-Mackey et al., 2013) of the
matter density parameter $\Omega_{m_{0}}$ and power spectrum amplitude
$\sigma_{8}$ within the $\Lambda$CDM model by comparing the two-point
correlation function obtained from cluster distribution (halo distribution in
case of simulations) and one obtained by scaling dark matter two-point
correlation function with predicted bias. All the other cosmological
parameters were fixed at values based on Wilkinson Microwave Anisotropy Probe
(WMAP) nine-year results (Hinshaw et al., 2013) in the case of CODEX clusters
(we later combine the posterior with one based on cluster mass function and
WMAP nine-year cosmology) or Planck 2015 results in the case of HMDPL halos
(the simulation was run using this cosmology). We restricted ourselves to
spatially flat cosmologies so that the dark energy density parameter is
determined by the matter density parameter:
$\Omega_{\rm{DE}_{0}}=1-\Omega_{m_{0}}$ for each value of $\Omega_{m_{0}}$. We
assumed a Gaussian likelihood,

$\ln{\mathcal{L}}=-\frac{1}{2}\left[\left(\boldsymbol{\xi}-\overline{b}^{\;2}\boldsymbol{\xi}^{\mathrm{DM}}\right)^{T}\mathbf{C}^{-1}\left(\boldsymbol{\xi}-\overline{b}^{\;2}\boldsymbol{\xi}^{\mathrm{DM}}\right)+c\right],$
(19)

where $c$ is a constant. The predicted two-point correlation function
$\boldsymbol{\xi}^{\mathrm{DM}}$ and the mean bias $\overline{b}$ are both
functions of cosmological parameters and thus updated at each MCMC step. For
simplicity, we ignored the effect of errors in cluster masses on
$\overline{b}$ and on the likelihood.

The estimated two-point correlation function $\boldsymbol{\xi}$ changes with
cosmology as well as with the cosmology-dependent transformation of redshifts
to distances; in principle, it should therefore be reestimated at each
cosmology. This effect is small, however. Figure 8 compares two-point
correlation function estimates from HMDPL halos using drastically differing
values of $\Omega_{m_{0}}$. The fitted biases are presented in Table 6. Both
of the extreme values are compatible with the central value within the
statistical errors. To take the difference into account, we modeled the effect
of comparing estimated and predicted two-point correlation functions computed
at different cosmologies (so-called geometrical distortions, GD) following
Marulli et al. (2012). Distances perpendicular and parallel to the line of
sight, $r_{p}$ and $\pi$, are related in the two different cosmologies,
labeled 1 and 2, by

$r_{p,1}=\frac{D_{A,1}(z)}{D_{A,2}(z)}r_{p,2};\quad\pi_{1}=\frac{H_{2}(z)}{H_{1}(z)}\pi_{2},$
(20)

where $D_{A}(z)$ is the angular diameter distance and $H(z)$ is the Hubble
parameter at redshift $z$. To compare theoretical predictions at varying
cosmologies with the measurement at the fiducial cosmology at scales
$(r_{p},\pi),$ we therefore evaluated them at scales
$\left(D_{A}(z)/D_{A,f}(z)r_{p},H(z)_{f}/H(z)\pi\right)$, where $f$ refers to
the fiducial cosmology, and we took $z$ to be the mean redshift of the sample.

Figure 8: Effect of changing $\Omega_{m_{0}}$ on the two-point correlation function estimate. Top panel: Bias-scaled dark matter prediction for HMDPL cosmology $\Omega_{m_{0}}=0.307115$ (solid curve) and two-point correlation function estimates obtained using this same value and values $\pm 0.1$. Bottom panel: Relative difference between the estimates and the dark matter prediction. The data points have been shifted horizontally for clarity. Table 6: Comparison of fitted biases using different values of $\Omega_{m_{0}}$ while estimating the two-point correlation function. These should be compared to the mass-based prediction of $\overline{b}=4.29$. $\Omega_{m_{0}}$ | $b$
---|---
0.21 | $4.48\pm 0.08$
0.31 | $4.33\pm 0.07$
0.41 | $4.18\pm 0.09$

To verify that we are able to recover the correct cosmology, we first ran the
MCMC sampling using the HMDPL halo catalog. We used the same redshift, mass
ranges, and binning for the projected two-point correlation function as in
Sect. 4. We also included photometric redshift errors estimated from the CODEX
catalog. The resulting posterior distributions of the cosmological parameters
are shown in Fig. 9, displaying the full two-dimensional likelihood contours
and marginalized posterior distributions for $\Omega_{m_{0}}$ and
$\sigma_{8}$. The parameter values that were used to run the simulation are
$\Omega_{m_{0}}=0.307115$ and $\sigma_{8}=0.8228$. The marginalized
constraints we obtain are $\Omega_{m_{0}}=0.28^{+0.04}_{-0.03}$ and
$\sigma_{8}=0.91^{+0.18}_{-0.13}$ , which are clearly compatible with the
simulation cosmology.

Figure 9: Posterior distribution for the parameters $\Omega_{m_{0}}$ and
$\sigma_{8}$ for the HMDPL catalog. The contours show the 68% and 95%
confidence regions, and the values used in the simulation are shown by the
dashed red lines. The dashed black lines in the marginalized posteriors show
the 16%, 50%, and 84% quantiles.

We then performed the same analysis on the CODEX clusters. All the details of
the two-point correlation function estimates (such as binning) were exactly
the same as described in Sect. 5. We applied flat priors in the range of
$0.05<\Omega_{m_{0}}<0.5$ and $0.4<\sigma_{8}<1.9$. Figure 10 shows the
posterior distributions obtained for the full CODEX cluster catalog. It favors
extremely high values of $\sigma_{8}$. The richness-to-mass scaling relation
we used, however, has a quite significant uncertainty. When we take the lower
$1\sigma$ extreme value for its normalization instead of the mean value, which
is supported by calibrations obtained for Sunyaev-Zeldovich (SZ) clusters
(Bleem et al., 2020), we obtain the posterior distribution of Fig. 11. The
obtained value of $\sigma_{8}$ is more compatible with canonical values. We
adopt this $1\sigma$ lower limit as our baseline for the rest of the analysis.

Figure 10: Posterior distribution for the parameters $\Omega_{m_{0}}$ and
$\sigma_{8}$ for the CODEX catalog in the full redshift range of $0.1<z<0.5$.
The contours show the 68% and 95% confidence regions, and the best fit, values
are shown by the dashed red lines. The dashed black lines in the marginalized
posteriors show the 16%, 50%, and 84% quantiles. Figure 11: Same as Fig. 10,
but with the richness-to-mass scaling relation with $1\sigma$ deviation.

For high values of $\sigma_{8}$ the distributions are very flat providing poor
constraints. However, Pillepich et al. (2012) and Pillepich et al. (2018), for
example, showed that it is possible to make the angular clustering of clusters
more sensitive to the cosmology by splitting the cluster sample into redshift
bins. Motivated by this, we ran the MCMC sampling using two redshift bins,
$0.1<z<0.3$ and $0.3<z<0.5$, and computed a two-point correlation function
estimate for both bins (see Fig. 7 for a display). The resulting posterior
distributions for $\Omega_{m_{0}}$ and $\sigma_{8}$ are shown in Fig. 12. The
distribution is in this case far less skewed toward high $\sigma_{8}$ , and we
obtain marginalized parameter constraints of
$\Omega_{m_{0}}=0.22^{+0.04}_{-0.03}$ and $\sigma_{8}=0.98^{+0.19}_{-0.15}$
(or correcting for the dependency on $\Omega_{m_{0}}$,
$S_{8}=\sigma_{8}(\Omega_{m_{0}}/0.3)^{0.5}=0.85^{+0.10}_{-0.08}$). The
constraints we obtain from the two redshift bins separately are
$\Omega_{m_{0}}=0.22^{+0.05}_{-0.04}$, $\sigma_{8}=0.99^{+0.25}_{-0.20}$ for
the low-redshift bin and $\Omega_{m_{0}}=0.22^{+0.08}_{-0.05}$,
$\sigma_{8}=1.02^{+0.36}_{-0.24}$ for the high-redshift bin. When the two
redshift bins are combined in the analysis, the constraints become tighter.
However, the sampling was made assuming that the two redshifts bins are
independent. This might not be the case, especially with photometric
redshifts. Taking the covariance between the bins into account might loosen
the constraints by some amount. For comparison with the WMAP9 cosmology, we
also ran the MCMC sampling using Planck Collaboration (2016) values for the
fixed parameters. In this case, we obtain constraints
$\Omega_{m_{0}}=0.23^{+0.03}_{-0.03}$ and $\sigma_{8}=0.93^{+0.16}_{-0.13}$.
Both are compatible with values using WMAP9 cosmology within the statistical
errors.

Figure 12: Posterior distribution for the parameters $\Omega_{m_{0}}$,
$\sigma_{8}$ , and $S_{8}$ for the CODEX catalog split into two redshift bins
$0.1<z<0.3$ and $0.3<z<0.5$. The contours show the 68% and 95% confidence
regions, and the best fit values are shown by the dashed red lines. The dashed
black lines in the marginalized posteriors show the 16%, 50%, and 84%
quantiles.

Figs. 10-12 show a strong degeneracy between $\Omega_{m_{0}}$ and $\sigma_{8}$
when clustering data alone are used. It is possible to break some of this
degeneracy by combining the likelihood from the clustering analysis with that
from the cluster mass function. Finoguenov et al. (2020) used the cluster
X-ray luminosity function, which is essentially a proxy for their mass
function, to obtain constraints $\Omega_{m_{0}}=0.270\pm 0.06$ and
$\sigma_{8}=0.79\pm 0.05$. In the top panel of Fig. 13 we show the constraints
we obtain by combining the two likelihoods. The individual likelihood
functions are mutually nearly orthogonal, and by combining them, we can
significantly tighten the parameter constraints. The bottom panel of Fig. 13
shows the marginalized posterior distributions for $\Omega_{m_{0}}$ and
$\sigma_{8}$ obtained from the joint likelihood. From these we derive the
parameter constraints $\Omega_{m_{0}}=0.27^{+0.01}_{-0.02}$,
$\sigma_{8}=0.79^{+0.02}_{-0.02}$. It should be noted, however, that we have
estimated the joint likelihood by a simple product of the two likelihoods.
This can result in an overly optimistic estimate because the two quantities
involved are correlated; see, for example, Lacasa & Rosenfeld (2016), who
estimated the cross-correlations of cluster counts (essentially their mass
function) and galaxy power spectrum to be at $\sim 20\%$ level.

Figure 13: Parameter constraints combining two-point correlation function and
luminosity function likelihoods. Top panel: Likelihood function of
$(\Omega_{m_{0}}$, $\sigma_{8})$ from the cluster two-point correlation
function (blue), X-ray luminosity function (red), and joint distribution
(green). The light and dark contours are the 68 % and 95 % confidence regions,
respectively, and the dashed red lines show the best-fit values for the joint
likelihood. Bottom panel: Marginalized posterior distributions for
$\Omega_{m_{0}}$ and $\sigma_{8}$ obtained from the joint likelihood in the
top panel. The dashed black lines show the 16%, 50%, and 84% quantiles.

To estimate the effect of systematic uncertainties in our parameter
constraints, we ran set of MCMC samplings using a variety of redshift
measurements, selection functions, mass proxies, and bias-to-mass
calibrations. A full account of this exercise is provided in Appendix A. We
estimate the systematic error of parameter $p$ as the sum of the squared
differences between best-fit parameter values in the baseline case (presented
in Fig.12) and the comparison cases,

$\sigma_{p}=\sqrt{\frac{1}{N}\sum_{i=1}^{N}\left(\overline{p}-p_{i}\right)^{2}},$
(21)

where $\overline{p}$ is the best-fit value in the baseline case, and $p$ are
the best fit values for the comparison cases. We separately estimated the
systematic error originating from survey effects (redshift measurement and
selection function) and the systematic error from predicting the bias. The
results along with the combination of the two error categories are shown in
Table 7. The total systematic errors are $\sigma_{\Omega_{m_{0}}}=0.02$ and
$\sigma_{\sigma_{8}}=0.23$ for the two-point correlation function alone and
$\sigma_{\Omega_{m_{0}}}=0.07$ and $\sigma_{\sigma_{8}}=0.04$ for the
combination of the two-point correlation function and the X-ray luminosity
function. Both are of similar magnitude than the statistical errors in their
respective cases.

Table 7: Systematic errors from survey effects and bias prediction, and their combination. The second and third column list the two-point correlation function alone, and the fourth and fifth column list the combination of the two-point correlation function and the X-ray luminosity function. | 2PCF | 2PCF $\times$ XLF
---|---|---
Source | $\Omega_{m_{0}}$ | $\sigma_{8}$ | $\Omega_{m_{0}}$ | $\sigma_{8}$
Survey | 0.018 | 0.031 | 0.014 | 0.017
Mass | 0.005 | 0.231 | 0.070 | 0.039
Combined | 0.019 | 0.233 | 0.072 | 0.042

A summary of our results along with a comparison with the WMAP9 and Planck
2018 results (Planck Collaboration, 2020) is listed in Table 8. Our results
from combining clustering and mass function are fully consistent with the
WMAP9 results within the statistical uncertainty. A difference larger than
$1\sigma$ between our values and those from Planck 2018 for $\Omega_{m_{0}}$
is visible, but this difference is smaller than our estimated systematic
uncertainty.

Table 8: Summary of cosmological constraints obtained from the cluster two-point correlation function, two-point correlation function combined with the X-ray luminosity function, the X-ray luminosity function alone, and for CMB datasets. Our error estimates include only the statistical errors. Dataset | $\Omega_{m_{0}}$ | $\sigma_{8}$
---|---|---
2PCF | $0.22^{+0.04}_{-0.03}$ | $0.98^{+0.19}_{-0.15}$
2PCF $\times$ XLF | $0.27^{+0.01}_{-0.02}$ | $0.79^{+0.02}_{-0.02}$
CODEX XLF | $0.27\pm 0.06$ | $0.79\pm 0.05$
WMAP9 | $0.279\pm 0.025$ | $0.821\pm 0.023$
Planck 2018 | $0.3147\pm 0.0074$ | $0.8101\pm 0.0061$

All the posterior distribution corner plots in this work were plotted using
the python library corner444https://github.com/dfm/corner.py (Foreman-Mackey,
2016).

##  7 Conclusions

We performed a clustering analysis on the CODEX galaxy cluster catalog. As a
part of this analysis, we aimed at predicting the clustering bias of these
clusters based on their masses. We first verified with a halo catalog from the
HMDPL simulation that using this approach we can predict the clustering bias
of dark matter halos with perfectly known masses in a known cosmology. We
showed that we can recover the observed clustering bias within the statistical
errors by simply averaging over the mass-based bias prediction for each
individual halo in the sample. All three components in the analysis, the
clustering of galaxy clusters (or dark matter halos in the case of
simulations), the expected dark matter distribution, and the mass-to-bias
conversion, depend on the cosmology, thus the agreement of them is a test of
the cosmological model. We performed an MCMC sampling of parameters
$\Omega_{m_{0}}$ and $\sigma_{8}$ to find the best-fit values by comparing the
measured two-correlation function of HMDPL halos to the total matter
distribution scaled by the predicted bias factor. We recovered the input
cosmological parameters within the statistical uncertainty.

We applied the same analysis to the CODEX catalog. Cluster masses can be
estimated from their X-ray luminosities or their richness. We determined which
of these estimates of bias was best compatible with the data. We found that
the mass estimates predict bias factors that agree with the measured value at
a level of 17-39%; the richness-based estimates give the best agreement. We
also tested how splitting the sample into redshifts bins affects the results
and found that the predicted bias agrees with the measured value at the 5-17%
level depending on the redshift range used. We applied the same MCMC sampling
as to the HMDPL halo catalog to CODEX clusters. We found that in order to have
a constraining power on $\sigma_{8}$ , we need to split the cluster sample
into redshift bins (two in the case of our analysis). By binning the sample
according to redshift, we obtained the following parameter constraints:
$\Omega_{m_{0}}=0.22^{+0.04}_{-0.03}$ and $\sigma_{8}=0.98^{+0.19}_{-0.15}$.
We estimated an additional error of $\pm 0.02$ and $\pm 0.19$, respectively,
that originates from systematic effects related to survey effects and bias
modeling. After combining the clustering-based likelihood with one from the
cluster mass function, we obtained the following parameter constraints:
$\Omega_{m_{0}}=0.27^{+0.01}_{-0.02}$ and $\sigma_{8}=0.79^{+0.02}_{-0.02}$.
In this case, we estimated that the systematic uncertainties contribute $\pm
0.07$ and $\pm 0.04$ additionally, respectively. It should be noted, however,
that proper handling of the covariance between the two quantities would most
likely loosen the constraints by some amount. In any case, our parameter
constraints from clustering bias are consistent with the WMAP nine-year
cosmology, and when systematic uncertainties are included, also with the
Planck 2018 cosmology.

###### Acknowledgements.

The authors wish to acknowledge CSC – IT Center for Science, Finland, for
computational resources. We acknowledge grants of computer capacity from the
Finnish Grid and Cloud Infrastructure (persistent identifier
urn:nbn:fi:research-infras-2016072533 ). Based on observations made with the
Nordic Optical Telescope, operated by the Nordic Optical Telescope Scientific
Association at the Observatorio del Roque de los Muchachos, La Palma, Spain,
of the Instituto de Astrofisica de Canarias. The authors gratefully
acknowledge the Gauss Centre for Supercomputing e.V. (www.gauss-centre.eu) and
the Partnership for Advanced Supercomputing in Europe (PRACE, www.prace-ri.eu)
for funding the MultiDark simulation project by providing computing time on
the GCS Supercomputer SuperMUC at Leibniz Supercomputing Centre (LRZ,
www.lrz.de). Funding for the Sloan Digital Sky Survey IV has been provided by
the Alfred P. Sloan Foundation, the U.S. Department of Energy Office of
Science, and the Participating Institutions. SDSS-IV acknowledges support and
resources from the Center for High-Performance Computing at the University of
Utah. The SDSS web site is www.sdss.org. SDSS-IV is managed by the
Astrophysical Research Consortium for the Participating Institutions of the
SDSS Collaboration including the Brazilian Participation Group, the Carnegie
Institution for Science, Carnegie Mellon University, the Chilean Participation
Group, the French Participation Group, Harvard-Smithsonian Center for
Astrophysics, Instituto de Astrofísica de Canarias, The Johns Hopkins
University, Kavli Institute for the Physics and Mathematics of the Universe
(IPMU) / University of Tokyo, the Korean Participation Group, Lawrence
Berkeley National Laboratory, Leibniz Institut für Astrophysik Potsdam (AIP),
Max-Planck-Institut für Astronomie (MPIA Heidelberg), Max-Planck-Institut für
Astrophysik (MPA Garching), Max-Planck-Institut für Extraterrestrische Physik
(MPE), National Astronomical Observatories of China, New Mexico State
University, New York University, University of Notre Dame, Observatário
Nacional / MCTI, The Ohio State University, Pennsylvania State University,
Shanghai Astronomical Observatory, United Kingdom Participation Group,
Universidad Nacional Autónoma de México, University of Arizona, University of
Colorado Boulder, University of Oxford, University of Portsmouth, University
of Utah, University of Virginia, University of Washington, University of
Wisconsin, Vanderbilt University, and Yale University.

## References

  * Ahumada et al. (2019) Ahumada R. Allende P., Carlos A. P. et al. 2019, arXiv:1912.02905 [astro-ph.GA]
  * Allevato et al. (2011) Allevato, V., Finoguenov, A., Cappelluti, N., et al. 2011, ApJ, 736, 99
  * Allevato et al. (2012) Allevato, V., Finoguenov, A., Hasinger, G., et al. 2012, ApJ, 758, 47
  * Bhattacharya et al. (2011) Bhattacharya S., Heitmann K., White M., Lukić Z., Wagner C. Habib S. 2011, ApJ, 732, 122
  * Böhringer et al. (2001) Böhringer H., Schuecker P., Guzzo L. et al. 2011, A&A, 369, 826
  * Bleem et al. (2020) Bleem, L. E., Bocquet, S., Stalder, B., et al. 2020, ApJS, 247, 25
  * Capasso et al. (2019) Capasso, R., Mohr, J. J., Saro, A., et al. 2019, MNRAS, 486, 1594
  * Cavaliere & Fusco-Femiano (1976) Cavaliere A., Fusco-Femiano R., 1976, A&A, 49, 137
  * Clerc et al. (2016) Clerc, N., Merloni, A., Zhang, Y.-Y., et al. 2016, MNRAS, 463, 4490
  * Clerc et al. (2020) Clerc, N., Kirkpatrick, C. C., Finoguenov, A., et al. 2020, MNRAS, 497, 3976
  * Capasso et al. (2020) Capasso, R., Mohr, J. J., Saro, A., et al. 2020, MNRAS, 494, 2736
  * Collins et al. (2000) Collins C. A.,Guzzo L., Böhringer H. et al. 2000, MNRAS, 319, 939
  * Comparat et al. (2017) Comparat J., Prada F., Yepes G., Klypin A. 2017, MNRAS, 469, 4157
  * Comparat et al. (2019) Comparat J., Merloni, A., Salvato, M. et al. 2019, MNRAS, 487, 2005
  * Comparat et al. (2020) Comparat J., Eckert D., Finoguenov A. et al. 2020, arXiv:2008.08404 [astro-ph.CO]
  * Dabis & Peebles (1983) Davis M., Peebles P. J. E., 1983, ApJ, 267, 465
  * Diemer (2018) Diemer B. 2018, ApJS, 239, 13
  * Estrada et al. (2009) Estrada J., Sefusatti E., Frieman J. A., 2009, ApJ, 692, 265
  * Eisenstein & Hu (1998) Eisenstein D. J., Hu W. 1998, ApJ, 496, 605
  * Eisenstein & Hu (1999) Eisenstein D. J., Hu W. 1999, ApJ, 511, 5
  * Farahi et al. (2019) Farahi, A., Mulroy, S. L., Evrard, A. E., et al. 2019, Nature Com., 10, 2504
  * Finoguenov et al. (2020) Finoguenov, A., Rykoff, E., Clerc, N., et al. 2020, A&A, 638, A114
  * Foreman-Mackey et al. (2013) Foreman-Mackey D., Hogg D. W., Lang D., Goodman J. 2013, PASP, 125, 306
  * Foreman-Mackey (2016) Foreman-Mackey D., 2016, The Journal of Open Source Software, 1(2), 24
  * Hinshaw et al. (2013) Hinshaw, G., Larson, D., Komatsu, E., et al. 2013, ApJS, 208, 19
  * Jimeno et al. (2017) Jimeno, P., Broadhurst, T., Lazkoz, R., et al. 2017, MNRAS, 466, 2658
  * Käfer et al. (2019) Käfer, F., Finoguenov, A., Eckert, D., et al. 2019, A&A, 628, A43
  * Kiiveri et al. (subm.) Kiiveri K. et al. 2020, MNRAS, subm.
  * Kirkpatrick et al. (2020) Kirkpatrick, C. C., Clerc, N., Finoguenov, A., et al. 2020, MNRAS, subm.
  * Klein et al. (2019) Klein, M., Grandis, S., Mohr, J. J., et al. 2019, MNRAS, 488, 739
  * Klypin et al. (2016) Klypin A., Yepes G., Gottlöber S., Prada F., Heß, S. 2016, MNRAS, 457, 4340
  * Koester et al. (2017) Koester B. P., McKay T. A., Annis J. et al. 2007 ApJ, 660, 239
  * Lacasa & Rosenfeld (2016) Lacasa F., Rosenfeld R. 2016 J. Cosmology Astropart. Phys., issue 08, article id. 005
  * Landy & Szalay (1993) Landy S.D., Szalay A.S. 1993, ApJ, 412, 64
  * Lewis et al. (2000) Lewis, A., Challinor A., Lasenby A., 2000, ApJ, 538, 473
  * Mana et al. (2013) Annalisa Mana A., Giannantonio T., Weller J. 2013, MNRAS434, 684
  * Marulli et al. (2012) Marulli F., Bianchi D., Branchini E. et al.
2012 MNRAS426, 2566

  * Marulli et al. (2016) Marulli F., Veropalumbo A., & Moresco M. 2016, Astronomy and Computing, 14, 35
  * Marulli et al. (2018) Marulli F., Veropalumbo A., M. Sereno et al. 2018 A&A, 620, A1 (XXL Paper XVI)
  * Mo & White (1996) Mo H. J. & White S. D. M. 1996, MNRAS, 282, 347
  * Mulroy et al. (2019) Mulroy, S. L., Farahi, A., Evrard, A. E., et al. 2019, MNRAS, 484, 60
  * Navarro, Frenk, White (1997) Navarro J. F., Frenk C. S., White S. D. M., 1997, ApJ, 490, 493
  * Peacock & West (1992) Peacock J. A., West M. J., 1992, MNRAS, 259, 494
  * Pierre et al. (2016) Pierre M., Pacaud F., Adami C. et al. 2016 A&A, 592, A1 (XXL Paper I)
  * Pillepich et al. (2012) Pillepich, A., Porciani, C., & Reiprich, T. H. 2012, MNRAS, 422, 44
  * Pillepich et al. (2018) Pillepich, A., Reiprich, T. H., Porciani, C., et al. 2018, MNRAS, 481, 613
  * Planck Collaboration (2014) Planck Collaboration, Ade, P. A. R., Aghanim, N., et al. 2014, A&A, 571, A16
  * Planck Collaboration (2016) Planck Collaboration, Ade, P. A. R., Aghanim, N., et al. 2016, A&A, 594, A13
  * Planck Collaboration (2020) Planck Collaboration, Aghanim, N., Akrami, Y., et al. 2020, A&A, 641, A6
  * Prada et al. (2012) Prada F., Klypin A. A., Cuesta A. J., Betancort-Rijo J. E., Primack J. 2012,MNRAS, 423, 3018
  * Rykoff et al. (2014) Rykoff, E. S., Rozo, E., Busha, M. T., et al. 2014, ApJ, 785, 104
  * Schuecker et al. (2002) Schuecker, P., Guzzo, L., Collins, C. A., et al. 2002, MNRAS, 335, 807
  * Sheth & Tormen (1999) Sheth R. K. & Tormen G. 1999, MNRAS, 308, 119
  * Sheth, Mo & Tormen (2001) Sheth R. K., Mo H. J., Tormen G. 2001, MNRAS, 323, 1
  * Tinker et al. (2010) Tinker J. L., Robertson B. E., Kravtsov, A. V. et al.
2010, ApJ, 724, 878

##  Appendix A Systematic effects

We report the different systematic effects in the cosmological parameter
constraints we obtain. Our baseline case is the one where we split the CODEX
sample in two redshift bins $0.1<z<0.3$ and $0.3<z<0.5$ and use richness-based
mass estimates and the $b(M)$ model from Comparat et al. (2017). We compared
the best-fit parameter values for $\Omega_{m_{0}}$ and $\sigma_{8}$ from MCMC
samplings by varying survey effects, mass estimates, and the $b(M)$ model. All
of the best-fit parameter values we obtain for different comparison cases are
summarized in Table 11.

As mentioned in Sec. 4, a subset of CODEX clusters has spectroscopic redshifts
associated with them in addition to photometric redshifts. To verify the
robustness of the photometric redshifts, we computed the two-point correlation
function using spectroscopic redshifts when available and photometric
redshifts for the remaining clusters. A comparison between measured and
predicted correlation functions in the full redshift range is presented in
Fig. 14, where we also show the results for a purely spectroscopic sample
limited to the SDSS DR16 area. In this case, we have a slightly smaller set of
spectroscopic redshifts (880 within $0.1<z<0.5$) because we required
spectroscopic completeness. The measured and predicted biases for both cases
in all the redshift bins are listed in Table 9. At lower redshifts, the
measured biases are compatible with those from the purely photometric sample,
but at higher redshifts, there is some difference.

Figure 14: Comparison of photometric, mixed, and spectroscopic redshifts. Top
panel: Projected two-point correlation functions in the redshift range
$0.1<z<0.5$. Data points are the two-point correlation function estimate from
CODEX clusters. The solid curve is the predicted dark matter two-point
correlation function scaled by $\overline{b}^{\;2}$ computed from the halo
mass estimates. Bottom panel: Relative difference between the measured and
predicted two-point correlation functions. The data points have been shifted
horizontally for clarity. Table 9: Bias values obtained for a mixture of
photometric and spectroscopic redshifts (column $b_{\mathrm{mix}}$) and those
of a purely photometric sample (column $b_{\mathrm{phz}}$), and a purely
spectroscopic sample (columns $b_{\mathrm{spe}}$) as well as the mass-based
prediction (column $\overline{b}$) from Table 4. Column $n_{\mathrm{spe}}$
shows the number of clusters with spectroscopic redshifts in each redshift
bin.

Redshift range $n_{\mathrm{spe}}$ $b_{\mathrm{phz}}$ $b_{\mathrm{spe}}$
$b_{\mathrm{mix}}$ $\overline{b}$ $0.1<z<0.5$ 1223 $3.70\pm 0.13$ $4.07\pm
0.30$ $3.77\pm 0.08$ 4.33 $0.1<z<0.3$ 823 $3.78\pm 0.10$ $3.90\pm 0.27$
$3.72\pm 0.09$ 3.95 $0.3<z<0.5$ 400 $4.71\pm 0.66$ $6.67\pm 0.40$ $6.45\pm
0.77$ 5.08

In Fig. 7 the slope of the measured correlation function in the high-redshift
bin and at large scales appears to be flatter than the prediction and the low-
redshift bin. To test whether this is due to an incorrect characterization of
the selection function, we ran the analysis forcing the redshift distribution
of the random catalog to be exactly that of the data catalog in redshift bins
of $\Delta z=0.027$. Another test we ran was to use the subregion of the CODEX
survey area in which the X-ray sensitivity is uniform. A comparison of the
fitted biases obtained using different selection functions is given in Table
10.

Table 10: Comparison of fitted and predicted biases using different selection functions. Column $b$ is the fitted bias, $\overline{b}$ is the mass-based prediction. ”Full” indicates the whole CODEX survey area, and ”Uniform” the subregion of uniform X-ray sensitivity. Column $n_{D}$ shows the number of clusters in each combination of redshift range and sky area. Redshift range | Sky area | $n_{D}$ | $\overline{b}$ | $b$
---|---|---|---|---
$0.1<z<0.5$ | Full | 1892 | 4.33 | $3.91\pm 0.14$
$0.1<z<0.3$ | Full | 1250 | 3.95 | $3.68\pm 0.18$
$0.3<z<0.5$ | Full | 642 | 5.08 | $6.64\pm 2.17$
$0.1<z<0.5$ | Uniform | 1831 | 4.32 | $3.92\pm 0.16$
$0.1<z<0.3$ | Uniform | 1206 | 3.94 | $3.66\pm 0.21$
$0.3<z<0.5$ | Uniform | 625 | 5.06 | $7.02\pm 1.49$

Fig. 15 shows the two-point correlation function results in a high-z bin using
different selection functions. They show that the flattening of the measured
two-point correlation function at large scales at high redshifts occurs
regardless of the selection function used, and we therefore suspect that this
is not the cause of the effect.

Figure 15: Comparison of different selection functions in high-z bin. Top
panel: Projected two-point correlation function in redshift range $0.3<z<0.5$.
Data points are the two-point correlation function estimate from CODEX
clusters. The solid curve shows the predicted dark matter two-point
correlation function scaled by $\overline{b}^{\;2}$ computed from the halo
mass estimates. Bottom panel: Relative difference between the measured and
predicted two-point correlation functions. The data points have been shifted
horizontally for clarity.

The effect of redshift errors and selection function on the cosmological
parameter constraints is demonstrated by the corresponding changes in the
best-fit parameter values presented in Table 11.

In addition to different survey effects, we studied the effect of varying the
mass and bias estimates. We ran MCMC sampling using the two X-ray luminosity
based mass calibrations (introduced in Sect. 5). From the bias models $b(M)$
in Table 1 we chose the two that gave the most extreme values, that is, Tinker
et al. (2010) and Bhattacharya et al. (2011), to be compared with the baseline
case. The resulting shifts in the best-fit parameter values are shown again in
Table 11.

Table 11: Best-fit parameter values for all the cases used to compute the
systematic error on the parameters $\Omega_{m_{0}}$ and $\sigma_{8}$. The
second and third column show clustering data alone, and the fourth and fifth
column list the combination of clustering and X-ray luminosity function.

2PCF 2PCF $\times$ XLF Case $\Omega_{m_{0}}$ $\sigma_{8}$ $\Omega_{m_{0}}$
$\sigma_{8}$ Baseline 0.22 0.99 0.27 0.79 Fixed $dn/dz$ 0.21 1.04 0.26 0.80
Fixed $dn/dz$, area of uniformity 0.22 0.97 0.25 0.81 Mixed redshifts 0.19
1.10 0.26 0.81 X-ray mass, Finoguenov et al. (2020) 0.22 1.35 0.37 0.78 X-ray
mass, Capasso et al. (2020) 0.22 1.17 0.33 0.74 $b(M)$, Tinker et al. (2010)
0.23 1.10 0.32 0.76 $b(M)$, Bhattacharya et al. (2011) 0.22 0.79 0.21 0.84


$S_{c}\subseteq[n]$ and $x,z\in\\{0,1\\}^{n}$, let us define
$x^{S_{c}}\coloneqq(x^{S_{c}}_{1},x^{S_{c}}_{2},\cdots,x^{S_{c}}_{n})$ and
$z^{S_{c}}\coloneqq(z^{S_{c}}_{1},z^{S_{c}}_{2},\cdots,z^{S_{c}}_{n})$, where
$x^{S_{c}}_{i}=x_{i}$ and $z^{S_{c}}_{i}=z_{i}$ for $i\in S_{c}$, and
$x^{S_{c}}_{i}=z^{S_{c}}_{i}=0$ for $i\notin S_{c}$.

For clarity, we describe how the interactive algorithm
$\langle\mathcal{P}(\mathsf{w}^{\otimes
k(|\mathsf{x}|)}),\mathcal{V}^{*}(\xi)\rangle(\mathsf{x})$ runs against a QPT
verifier $\mathcal{V}^{*}$ with an input $\xi$, where $\mathsf{w}$ is the
witness and $\mathsf{x}$ is the instance.

$\langle\mathcal{P}(\mathsf{w}^{\otimes
k(|\mathsf{x}|)}),\mathcal{V}^{*}(\xi)\rangle(\mathsf{x})$:

  1. 1.

$\mathcal{P}$ generates $x,z\leftarrow\\{0,1\\}^{n}$, and computes

$\displaystyle(\mathsf{com}_{i}(x_{i}),\mathsf{d}_{i}(x_{i}),\mathsf{ck}_{i}(x_{i}))\leftarrow\mathsf{Commit}(1^{\lambda},x_{i})$
(70)
$\displaystyle(\mathsf{com}_{i}(z_{i}),\mathsf{d}_{i}(z_{i}),\mathsf{ck}_{i}(z_{i}))\leftarrow\mathsf{Commit}(1^{\lambda},z_{i})$
(71)

for all $i\in[n]$. $\mathcal{P}$ sends
$\mathsf{msg}_{1}\coloneqq(X^{x}Z^{z}\rho_{\mathsf{hist}}Z^{z}X^{x})\otimes\mathsf{com}(x)\otimes\mathsf{com}(z)$
to $\mathcal{V}^{*}$.

  2. 2.

$\mathcal{V}^{*}$ appends $\xi$ to the received state, and runs a QPT circuit
$V_{1}^{*}$ on it to obtain
$(c,\\{\mathsf{cert}_{i,x}^{\prime},\mathsf{cert}_{i,z}^{\prime}\\}_{i\in\overline{S}_{c}})$.
$\mathcal{V}^{*}$ sends
$\mathsf{msg}_{2}\coloneqq(c,\\{\mathsf{cert}_{i,x}^{\prime},\mathsf{cert}_{i,z}^{\prime}\\}_{i\in\overline{S}_{c}})$
to $\mathcal{P}$.

  3. 3.

$\mathcal{P}$ sends
$\mathsf{msg}_{3}\coloneqq\\{\mathsf{d}_{i}(x_{i}),\mathsf{d}_{i}(z_{i})\\}_{i\in
S_{c}}$ to $\mathcal{V}^{*}$.

  4. 4.

$\mathcal{V}^{*}$ appends $\mathsf{msg}_{3}$ to its state, and runs a QPT
circuit $V_{2}^{*}$ on it. $\mathcal{V}^{*}$ outputs its state $\xi^{\prime}$.

Next let us define a simulator $\mathcal{S}^{(1)}$ as follows.

The simulator $\mathcal{S}^{(1)}(\mathsf{x},\mathcal{V}^{*},\xi)$:

  1. 1.

Pick $c\leftarrow[m]$ and $x,z\leftarrow\\{0,1\\}^{n}$. Compute

$\displaystyle(\mathsf{com}_{i}(x^{S_{c}}_{i}),\mathsf{d}_{i}(x^{S_{c}}_{i}),\mathsf{ck}_{i}(x^{S_{c}}_{i}))\leftarrow\mathsf{Commit}(1^{\lambda},x^{S_{c}}_{i})$
(72)
$\displaystyle(\mathsf{com}_{i}(z^{S_{c}}_{i}),\mathsf{d}_{i}(z^{S_{c}}_{i}),\mathsf{ck}_{i}(z^{S_{c}}_{i}))\leftarrow\mathsf{Commit}(1^{\lambda},z^{S_{c}}_{i})$
(73)

for all $i\in[n]$.

  2. 2.

Generate
$(X^{x}Z^{z}\sigma(c)Z^{z}X^{x})\otimes\mathsf{com}(x^{S_{c}})\otimes\mathsf{com}(z^{S_{c}})\otimes\xi$,
where
$\sigma(c)\coloneqq\rho_{\mathsf{sim}}^{\mathsf{x},S_{c}}\otimes\left(\prod_{i\in\overline{S}_{c}}|0\rangle\langle
0|_{i}\right)$. Run $V_{1}^{*}$ on the state to obtain
$(c^{\prime},\\{\mathsf{cert}_{i,x}^{\prime},\mathsf{cert}_{i,z}^{\prime}\\}_{i\in\overline{S}_{c^{\prime}}})$.

  3. 3.

If $c^{\prime}\neq c$, abort and output a fixed state $\eta$ and the flag
state $\mathsf{fail}$.

  4. 4.

Append
$\\{\mathsf{d}_{i}(x^{S_{c}}_{i}),\mathsf{d}_{i}(z^{S_{c}}_{i})\\}_{i\in
S_{c}}$ to its quantum state, and run $V_{2}^{*}$ on the state. $\mathcal{S}$
outputs the output state and the flag state $\mathsf{success}$.

Let us also define other two simulators $\mathcal{S}^{(2)}$ and
$\mathcal{S}^{(3)}$ as follows.

The modified simulator $\mathcal{S}^{(2)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\xi)$:

It is the same as $\mathcal{S}^{(1)}$ except that $\sigma(c)$ is replaced with
$\rho_{\mathsf{hist}}$.

The simulator $\mathcal{S}^{(3)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\xi)$:

$\mathcal{S}^{(3)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\cdot~{})$ is the channel that postselects
the output of
$\mathcal{S}^{(2)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\cdot~{})$ on the non-aborting state. More
precisely, if we write $\mathcal{S}^{(2)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\rho_{in})=p\rho_{out}\otimes\mathsf{success}+(1-p)\eta\otimes\mathsf{fail}$,
where $p$ is the non-aborting probability,
$\mathcal{S}^{(3)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\rho_{in})=\rho_{out}$.

Lemma 4.9 is shown from the following Propositions B.1, B.2 and B.3 (whose
proofs will be given later) and quantum rewinding lemma(Lemma 2.1), which is
used to reduce the probability that $\mathcal{S}^{(1)}$ aborts to
${\mathsf{negl}}(\lambda)$. In fact, from Propositions B.1 and 2.1, there
exists a quantum circuit $\mathcal{S}^{(0)}$ of size at most $O(m\,{\rm
poly}(n){\rm size}(\mathcal{S}^{(1)}))$ such that the probability
$\mathcal{S}^{(0)}$ aborts is ${\mathsf{negl}}(\lambda)$, and the output
quantum states of $\mathcal{S}^{(0)}$ and $\mathcal{S}^{(1)}$ are
${\mathsf{negl}}(\lambda)$-close when they do not abort. From Propositions B.2
and B.3, $\mathcal{S}^{(0)}$ is ${\mathsf{negl}}(\lambda)$-close to the run of
the real protocol, which completes the proof. ∎

###### Proposition B.1.

If $\Sigma_{\mathsf{ccd}}$ is computational hiding, then the probability that
$\mathcal{S}^{(1)}$ does not abort is
$\frac{1}{m}\pm{\mathsf{negl}}(\lambda)$.

###### Proposition B.2.

$\mathcal{S}^{(1)}(\mathsf{x},\mathcal{V}^{*},\cdot~{})\approx_{s}\mathcal{S}^{(2)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\cdot~{})$ for any $\mathsf{x}\in
A_{\mathsf{yes}}\cap\\{0,1\\}^{\lambda}$ and any $\mathsf{w}\in
R_{A}(\mathsf{x})$.

###### Proposition B.3.

If $\Sigma_{\mathsf{ccd}}$ is computational hiding,
$\mathcal{S}^{(3)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\cdot~{})\approx_{c}\mathsf{OUT}_{\mathcal{V}^{*}}\langle\mathcal{P}(\mathsf{w}^{\otimes
k(|\mathsf{x}|)}),\mathcal{V}^{*}(\cdot)\rangle(\mathsf{x})$.

###### Proof of Proposition B.1.

This proof is the same as the proof of Proposition 4.10. ∎

###### Proof of Proposition B.2.

This proof is the same as the proof of Proposition 4.11. ∎

###### Proof of Proposition B.3.

We prove the proposition by contradiction. We construct an adversary
$\mathcal{B}$ that breaks the security of the computationally hiding of
$\Sigma_{\mathsf{ccd}}$ by assuming the existence of a distinguisher
$\mathcal{D}$ that distinguishes two states $\delta_{0}$ and $\delta_{1}$,

$\displaystyle\delta_{0}\coloneqq(\mathsf{OUT}_{\mathcal{V}^{*}}\langle\mathcal{P}(\mathsf{w}^{\otimes
k(|\mathsf{x}|)}),\mathcal{V}^{*}(\cdot)\rangle(\mathsf{x})\otimes I)\sigma$
(74)
$\displaystyle\delta_{1}\coloneqq(\mathcal{S}^{(3)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\cdot~{})\otimes I)\sigma,$ (75)

with a certain state $\sigma$. Let us describe how $\mathcal{B}$ works.

  1. 1.

$\mathcal{B}$ generates $c\leftarrow[m]$ and $x,z\leftarrow\\{0,1\\}^{n}$.

  2. 2.

$\mathcal{B}$ sends $m_{0}\coloneqq\\{x_{i},z_{i}\\}_{i\in\overline{S}_{c}}$
and $m_{1}\coloneqq 0^{2n-10}$ to the challenger. $\mathcal{B}$ receives
commitments from the challenger which is either
$\\{\mathsf{com}_{i}(x_{i}),\mathsf{com}_{i}(z_{i})\\}_{i\in\overline{S}_{c}}$
or $\\{\mathsf{com}_{i}(0),\mathsf{com}_{i}(0)\\}_{i\in\overline{S}_{c}}$.

  3. 3.

$\mathcal{B}$ computes

$\displaystyle(\mathsf{com}_{i}(x_{i}),\mathsf{d}_{i}(x_{i}),\mathsf{ck}_{i}(x_{i}))\leftarrow\mathsf{Commit}(1^{\lambda},x_{i})$
(76)
$\displaystyle(\mathsf{com}_{i}(z_{i}),\mathsf{d}_{i}(z_{i}),\mathsf{ck}_{i}(z_{i}))\leftarrow\mathsf{Commit}(1^{\lambda},z_{i})$
(77)

for $i\in S_{c}$ by itself.

  4. 4.

$\mathcal{B}$ generates $X^{x}Z^{z}\rho_{\mathsf{hist}}Z^{z}X^{x}$.
$\mathcal{B}$ appends commitments and $\sigma$ to the quantum state. If the
commitments for ${i\in\overline{S}_{c}}$ are
$\\{\mathsf{com}_{i}(x_{i}),\mathsf{com}_{i}(z_{i})\\}_{i\in\overline{S}_{c}}$,
$\mathcal{B}$ obtains
$X^{x}Z^{z}\rho_{\mathsf{hist}}Z^{z}X^{x}\otimes\mathsf{com}(x)\otimes\mathsf{com}(z)\otimes\sigma$.
If the commitments for ${i\in\overline{S}_{c}}$ are
$\\{\mathsf{com}_{i}(0),\mathsf{com}_{i}(0)\\}_{i\in\overline{S}_{c}}$,
$\mathcal{B}$ obtains
$X^{x}Z^{z}\rho_{\mathsf{hist}}Z^{z}X^{x}\otimes\mathsf{com}(x^{S_{c}})\otimes\mathsf{com}(z^{S_{c}})\otimes\sigma$.

  5. 5.

$\mathcal{B}$ runs $V_{1}^{*}$ on it to obtain
$(c^{\prime},\\{\mathsf{cert}_{i,x}^{\prime},\mathsf{cert}_{i,z}^{\prime}\\}_{i\in\overline{S}_{c^{\prime}}})$.
$\mathcal{B}$ aborts when $c\neq c^{\prime}$.

  6. 6.

$\mathcal{B}$ appends $\\{\mathsf{d}_{i}(x_{i}),\mathsf{d}_{i}(z_{i})\\}_{i\in
S_{c}}$ to the post-measurement state and runs $V_{2}^{*}$ on it.

  7. 7.

$\mathcal{B}$ passes the output state to $\mathcal{D}$.

  8. 8.

When $\mathcal{D}$ outputs $b$, $\mathcal{B}$ outputs $b$.

When $\mathcal{B}$ receives
$\\{\mathsf{com}_{i}(x_{i}),\mathsf{com}_{i}(z_{i})\\}_{i\in\overline{S}_{c}}$
from the challenger and it does not abort, it simulates
$\mathsf{OUT}_{\mathcal{V}^{*}}\langle\mathcal{P}(\mathsf{w}^{\otimes
k(|\mathsf{x}|)}),\mathcal{V}^{*}(\cdot)\rangle(\mathsf{x})$. Because
$(X^{x}Z^{z}\rho_{\mathsf{hist}}Z^{z}X^{x})\otimes\mathsf{com}(x)\otimes\mathsf{com}(z)\otimes\sigma$
is independent of $c$, the probability that $\mathcal{B}$ does not abort is
$\frac{1}{m}$. Therefore, $\mathcal{B}$ can simulate
${\mathsf{OUT}}_{\mathcal{V}^{*}}\langle\mathcal{P}(\mathsf{w}^{\otimes
k(|\mathsf{x}|)}),\mathcal{V}^{*}(\cdot)\rangle(\mathsf{x})$ with probability
$\frac{1}{m}$.

When $\mathcal{B}$ receives
$\\{\mathsf{com}_{i}(0),\mathsf{com}_{i}(0)\\}_{i\in\overline{S}_{c}}$ from
the challenger and it does not abort, it simulates
$\mathcal{S}^{(3)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\cdot~{})$. The probability that
$\mathcal{B}$ does not abort is $\frac{1}{m}\pm{\mathsf{negl}}(\lambda)$ from
Propositions B.1 and B.2. Therefore, $\mathcal{B}$ can simulate
$\mathcal{S}^{(3)}(\mathsf{x},\mathsf{w}^{\otimes
k(|\mathsf{x}|)},\mathcal{V}^{*},\cdot~{})$ with probability
$\frac{1}{m}\pm{\mathsf{negl}}(\lambda)$.

Therefore, if there exists the distinguisher $\mathcal{D}$ that distinguishes
$\delta_{0}$ and $\delta_{1}$, $\mathcal{B}$ can distinguish
$\\{\mathsf{com}_{i}(x_{i}),\mathsf{com}_{i}(z_{i})\\}_{i\in\overline{S}_{c}}$
from $\\{\mathsf{com}_{i}(0),\mathsf{com}_{i}(0)\\}_{i\in\overline{S}_{c}}$.
From (the computational hiding version of) Lemma 3.7, this contradicts the
computational hiding of $\Sigma_{\mathsf{ccd}}$.

∎

##  Appendix C Commitment with Certified Everlasting Hiding and Sum-Binding

In this appendix, we define and construct commitment with certified
everlasting hiding and statistical sum-binding.

###  C.1 Definition

###### Definition C.1 (Commitment with Certified Everlasting Hiding and Sum-
Binding (Syntax)).

Let $\lambda$ be the security parameter, and let $p$, $q$, $r$ and $s$ be some
polynomials. Commitment with certified everlasting hiding and sum-binding
consists of a tuple of algorithms
$(\mathsf{Commit},\mathsf{Verify},\mathsf{Del},\mathsf{Cert})$ with message
space $\mathcal{M}:=\\{0,1\\}$, commitment space
$\mathcal{C}:=\mathcal{Q}^{\otimes p(\lambda)}$, decommitment space
$\mathcal{D}:=\\{0,1\\}^{q(\lambda)}$, key space
$\mathcal{K}:=\\{0,1\\}^{r(\lambda)}$ and deletion certificate space
$\mathcal{E}:=\\{0,1\\}^{s(\lambda)}$.

$\mathsf{Commit}(1^{\lambda},b)\rightarrow(\mathsf{com},\mathsf{d},\mathsf{ck})$:

The commitment algorithm takes as input a security parameter $1^{\lambda}$ and
a message $b\in\\{0,1\\}$, and outputs a commitment
$\mathsf{com}\in\mathcal{C}$, a decommitment $\mathsf{d}\in\mathcal{D}$, and a
key $\mathsf{ck}\in\mathcal{K}$.

$\mathsf{Verify}(\mathsf{com},\mathsf{d},b)\rightarrow\top~{}or~{}\bot$:

The verification algorithm takes as input $\mathsf{com}$, $\mathsf{d}$ and
$b$, and outputs $\top$ or $\bot$.

$\mathsf{Del}(\mathsf{com})\rightarrow\mathsf{cert}$:

The deletion algorithm takes $\mathsf{com}$ as input, and outputs a
certificate $\mathsf{cert}\in\mathcal{E}$.

$\mathsf{Cert}(\mathsf{cert},\mathsf{ck})\rightarrow\top~{}or~{}\bot$:

The certification algorithm takes $\mathsf{cert}$ and $\mathsf{ck}$ as input,
and outputs $\top$ or $\bot$.

###### Definition C.2 (Correctness).

There are two types of correctness, namely, decommitment correctness and
deletion correctness.

Decommitment correctness:

There exists a negligible function ${\mathsf{negl}}$ such that for any
$\lambda\in\mathbb{N}$ and $b\in\\{0,1\\}$,

$\displaystyle\Pr[\mathsf{Verify}(\mathsf{com},\mathsf{d},b)=\top\mid(\mathsf{com},\mathsf{d},\mathsf{ck})\leftarrow\mathsf{Commit}(1^{\lambda},b)]\geq
1-{\mathsf{negl}}(\lambda).$ (78)

Deletion correctness:

There exists a negligible function ${\mathsf{negl}}$ such that for any
$\lambda\in\mathbb{N}$ and $b\in\\{0,1\\}$,

$\displaystyle\Pr[\mathsf{Cert}(\mathsf{cert},\mathsf{ck})=\top\mid(\mathsf{com},\mathsf{d},\mathsf{ck})\leftarrow\mathsf{Commit}(1^{\lambda},b),\mathsf{cert}\leftarrow\mathsf{Del}(\mathsf{com})]\geq
1-{\mathsf{negl}}(\lambda).$ (79)

###### Definition C.3 ($\epsilon$-Sum-Binding).

For any $\mathsf{com}$, $\mathsf{d}$, and $\mathsf{d}^{\prime}$, it holds that

$\displaystyle\Pr[\mathsf{Verify}(\mathsf{com},\mathsf{d},0)=\top]+\Pr[\mathsf{Verify}(\mathsf{com},\mathsf{d}^{\prime},1)=\top]\leq
1+\epsilon.$ (80)

We call $\epsilon$-sum-binding just sum-binding if $\epsilon$ is negligible.

###### Definition C.4 (Computational Hiding).

Let
$\Sigma\coloneqq(\mathsf{Commit},\mathsf{Verify},\mathsf{Del},\mathsf{Cert})$.
Let us consider the following security experiment
$\mathsf{Exp}_{\Sigma,\mathcal{A}}^{\mathsf{c}\mbox{-}\mathsf{hide}}(\lambda,b)$
against any QPT adversary $\mathcal{A}$.

  1. 1.

The challenger computes
$(\mathsf{com},\mathsf{d},\mathsf{ck})\leftarrow\mathsf{Commit}(1^{\lambda},b)$,
and sends $\mathsf{com}$ to $\mathcal{A}$.

  2. 2.

$\mathcal{A}$ outputs $b^{\prime}\in\\{0,1\\}$.

  3. 3.

The output of the experiment is $b^{\prime}$.

Computational hiding means that the following is satisfied for any QPT
$\mathcal{A}$.

$\displaystyle\mathsf{Adv}_{\Sigma,\mathcal{A}}^{\mathsf{c}\mbox{-}\mathsf{hide}}(\lambda)\coloneqq\left|\Pr[\mathsf{Exp}_{\Sigma,\mathcal{A}}^{\mathsf{c}\mbox{-}\mathsf{hide}}(\lambda,0)=1]-\Pr[\mathsf{Exp}_{\Sigma,\mathcal{A}}^{\mathsf{c}\mbox{-}\mathsf{hide}}(\lambda,1)=1]\right|\leq{\mathsf{negl}}(\lambda).$
(81)

###### Definition C.5 (Certified Everlasting Hiding).

Let
$\Sigma\coloneqq(\mathsf{Commit},\mathsf{Verify},\mathsf{Del},\mathsf{Cert})$.
Let us consider the following security experiment
$\mathsf{Exp}_{\Sigma,\mathcal{A}}^{\mathsf{ever}\mbox{-}\mathsf{hide}}(\lambda,b)$
against $\mathcal{A}=(\mathcal{A}_{1},\mathcal{A}_{2})$ consisting of any QPT
adversary $\mathcal{A}_{1}$ and any unbounded adversary $\mathcal{A}_{2}$.

  1. 1.

The challenger computes
$(\mathsf{com},\mathsf{d},\mathsf{ck})\leftarrow\mathsf{Commit}(1^{\lambda},b)$,
and sends $\mathsf{com}$ to $\mathcal{A}_{1}$.

  2. 2.

At some point, $\mathcal{A}_{1}$ sends $\mathsf{cert}$ to the challenger, and
sends its internal state to $\mathcal{A}_{2}$.

  3. 3.

The challenger computes $\mathsf{Cert}(\mathsf{cert},\mathsf{ck})$. If the
output is $\top$, then the challenger outputs $\top$, and sends
$(\mathsf{d},\mathsf{ck})$ to $\mathcal{A}_{2}$. Else, the challenger outputs
$\bot$, and sends $\bot$ to $\mathcal{A}_{2}$.

  4. 4.

$\mathcal{A}_{2}$ outputs $b^{\prime}\in\\{0,1\\}$.

  5. 5.

If the challenger outputs $\top$, then the output of the experiment is
$b^{\prime}$. Otherwise, the output of the experiment is $\bot$.

We say that it is certified everlasting hiding if the following is satisfied
for any $\mathcal{A}=(\mathcal{A}_{1},\mathcal{A}_{2})$.

$\displaystyle\mathsf{Adv}_{\Sigma,\mathcal{A}}^{\mathsf{ever}\mbox{-}\mathsf{hide}}(\lambda)\coloneqq\left|\Pr[\mathsf{Exp}_{\Sigma,\mathcal{A}}^{\mathsf{ever}\mbox{-}\mathsf{hide}}(\lambda,0)=1]-\Pr[\mathsf{Exp}_{\Sigma,\mathcal{A}}^{\mathsf{ever}\mbox{-}\mathsf{hide}}(\lambda,1)=1]\right|\leq{\mathsf{negl}}(\lambda).$
(82)

###  C.2 Construction

Though the construction is essentially the same as that in Section 3.2, we
give the full description for clarity. Let $\lambda$ be the security
parameter, and let $p$, $q$, $r$, $s$, $t$ and $u$ be some polynomials. We
construct a bit commitment with certified everlasting hiding and sum-binding,
$\Sigma_{\mathsf{ccd}}=(\mathsf{Commit},\mathsf{Verify},\mathsf{Del},\mathsf{Cert})$,
with message space $\mathcal{M}=\\{0,1\\}$, commitment space
$\mathcal{C}=\mathcal{Q}^{\otimes
p(\lambda)}\times\\{0,1\\}^{q(\lambda)}\times\\{0,1\\}^{r(\lambda)}$,
decommitment space
$\mathcal{D}=\\{0,1\\}^{s(\lambda)}\times\\{0,1\\}^{t(\lambda)}$, key space
$\mathcal{K}=\\{0,1\\}^{r(\lambda)}$ and deletion certificate space
$\mathcal{E}=\\{0,1\\}^{u(\lambda)}$ from the following primitives:

  * •

Secret-key encryption with certified deletion
$\Sigma_{\mathsf{skcd}}=\mathsf{SKE}.(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec},\mathsf{Del},\mathsf{Verify})$,
with plaintext space $\mathcal{M}=\\{0,1\\}$, ciphertext space
$\mathcal{C}=\mathcal{Q}^{\otimes p(\lambda)}$, key space
$\mathcal{K}=\\{0,1\\}^{r(\lambda)}$, and deletion certificate space
$\mathcal{E}=\\{0,1\\}^{u(\lambda)}$.

  * •

Classical non-interactive commitment,
$\Sigma_{\mathsf{com}}=\mathsf{Classical}.\mathsf{Commit}$, with plaintext
space $\\{0,1\\}^{s(\lambda)}$, randomness space $\\{0,1\\}^{t(\lambda)}$, and
commitment space $\\{0,1\\}^{q(\lambda)}$.

  * •

A hash function $H$ from $\\{0,1\\}^{s(\lambda)}$ to $\\{0,1\\}^{r(\lambda)}$
modeled as a quantumly-accessible random oracle.

The construction is as follows.

$\mathsf{Commit}(1^{\lambda},b)$:

  * •

Generate $\mathsf{ske.sk}\leftarrow\mathsf{SKE}.\mathsf{KeyGen}(1^{\lambda})$,
$R\leftarrow\\{0,1\\}^{s(\lambda)}$,
$R^{\prime}\leftarrow\\{0,1\\}^{t(\lambda)}$, and a hash function $H$ from
$\\{0,1\\}^{s(\lambda)}$ to $\\{0,1\\}^{r(\lambda)}$.

  * •

Compute
$\mathsf{ske}.\mathsf{CT}\leftarrow\mathsf{SKE}.\mathsf{Enc}(\mathsf{ske}.\mathsf{sk},b)$,
$f\leftarrow\mathsf{Classical}.\mathsf{Commit}(R;R^{\prime})$, and $h\coloneqq
H(R)\oplus\mathsf{ske}.\mathsf{sk}$.

  * •

Output $\mathsf{com}\coloneqq(\mathsf{ske}.\mathsf{CT},f,h)$,
$\mathsf{d}\coloneqq(R,R^{\prime})$, and
$\mathsf{ck}\coloneqq\mathsf{ske}.\mathsf{sk}$.

$\mathsf{Verify}(\mathsf{com},\mathsf{d},b)$:

  * •

Parse $\mathsf{com}=(\mathsf{ske}.\mathsf{CT},f,h)$ and
$\mathsf{d}=(R,R^{\prime})$.

  * •

Compute $\mathsf{ske}.\mathsf{sk}^{\prime}\coloneqq H(R)\oplus h$.

  * •

Compute
$b^{\prime}\leftarrow\mathsf{SKE}.\mathsf{Dec}(\mathsf{ske}.\mathsf{sk}^{\prime},\mathsf{ske}.\mathsf{CT})$.

  * •

Output $\top$ if $f=\mathsf{Classical}.\mathsf{Commit}(R;R^{\prime})$ and
$b^{\prime}=b$, and output $\bot$ otherwise.

$\mathsf{Del}(\mathsf{com})$:

  * •

Parse $\mathsf{com}=(\mathsf{ske}.\mathsf{CT},f,h)$.

  * •

Compute
$\mathsf{ske}.\mathsf{cert}\leftarrow\mathsf{SKE}.\mathsf{Del}(\mathsf{ske}.\mathsf{CT})$.

  * •

Output $\mathsf{cert}\coloneqq\mathsf{ske}.\mathsf{cert}$.

$\mathsf{Cert}(\mathsf{cert},\mathsf{ck})$:

  * •

Parse $\mathsf{cert}=\mathsf{ske}.\mathsf{cert}$ and
$\mathsf{ck}=\mathsf{ske}.\mathsf{sk}$.

  * •

Output
$\top/\bot\leftarrow\mathsf{SKE}.\mathsf{Verify}(\mathsf{ske}.\mathsf{sk},\mathsf{ske}.\mathsf{cert})$.

#### Correctness.

The decommitment and deletion correctness easily follow from the correctness
of $\Sigma_{\mathsf{skcd}}$.

#### Security.

We prove the following three theorems.

###### Theorem C.6.

If $\Sigma_{\mathsf{com}}$ is perfect binding, then $\Sigma_{\mathsf{ccd}}$ is
sum-binding.

###### Theorem C.7.

If $\Sigma_{\mathsf{com}}$ is unpredictable and $\Sigma_{\mathsf{skcd}}$ is
OT-CD secure, then $\Sigma_{\mathsf{ccd}}$ is certified everlasting hiding.

###### Theorem C.8.

If $\Sigma_{\mathsf{com}}$ is unpredictable and $\Sigma_{\mathsf{skcd}}$ is
OT-CD secure, then $\Sigma_{\mathsf{ccd}}$ is computationally hiding.

###### Proof of Theorem C.6.

What we have to prove is that for any $\mathsf{com}$, $\mathsf{d}$, and
$\mathsf{d}^{\prime}$, it holds that

$\displaystyle\Pr[\mathsf{Verify}(\mathsf{com},\mathsf{d},0)=\top]+\Pr[\mathsf{Verify}(\mathsf{com},\mathsf{d}^{\prime},1)=\top]\leq
1+{\mathsf{negl}}(\lambda).$ (83)

Let $\mathsf{d}=(R_{0},R_{0}^{\prime})$,
$\mathsf{d}^{\prime}=(R_{1},R_{1}^{\prime})$, and
$\mathsf{com}=(\mathsf{ske}.\mathsf{CT},f,h)$. Then,

$\displaystyle\Pr[\mathsf{Verify}(\mathsf{com},\mathsf{d},0)=\top]+\Pr[\mathsf{Verify}(\mathsf{com},\mathsf{d}^{\prime},1)=\top]$
(84) $\displaystyle=\Pr[0\leftarrow\mathsf{SKE}.\mathsf{Dec}(h\oplus
H(R_{0}),\mathsf{ske}.\mathsf{CT})\wedge
f=\mathsf{Classical}.\mathsf{Commit}(R_{0};R_{0}^{\prime})]$ (85)
$\displaystyle+\Pr[1\leftarrow\mathsf{SKE}.\mathsf{Dec}(h\oplus
H(R_{1}),\mathsf{ske}.\mathsf{CT})\wedge
f=\mathsf{Classical}.\mathsf{Commit}(R_{1};R_{1}^{\prime})]$ (86)
$\displaystyle\leq\Pr[0\leftarrow\mathsf{SKE}.\mathsf{Dec}(h\oplus
H(\tilde{R}),\mathsf{ske}.\mathsf{CT})\wedge
f=\mathsf{Classical}.\mathsf{Commit}(\tilde{R};R_{0}^{\prime})]$ (87)
$\displaystyle+\Pr[1\leftarrow\mathsf{SKE}.\mathsf{Dec}(h\oplus
H(\tilde{R}),\mathsf{ske}.\mathsf{CT})\wedge
f=\mathsf{Classical}.\mathsf{Commit}(\tilde{R};R_{1}^{\prime})]$ (88)
$\displaystyle\leq\Pr[0\leftarrow\mathsf{SKE}.\mathsf{Dec}(h\oplus
H(\tilde{R}),\mathsf{ske}.\mathsf{CT})]+\Pr[1\leftarrow\mathsf{SKE}.\mathsf{Dec}(h\oplus
H(\tilde{R}),\mathsf{ske}.\mathsf{CT})]$ (89)
$\displaystyle=\Pr[0\leftarrow\mathsf{SKE}.\mathsf{Dec}(h\oplus
H(\tilde{R}),\mathsf{ske}.\mathsf{CT})\vee
1\leftarrow\mathsf{SKE}.\mathsf{Dec}(h\oplus
H(\tilde{R}),\mathsf{ske}.\mathsf{CT})]$ (90) $\displaystyle\leq 1,$ (91)

where we have used perfect binding of $\Sigma_{\mathsf{com}}$ in the second
inequality.

∎

###### Proof of Theorem C.7.

It is the same as that of Theorem 3.9. ∎

###### Proof of Theorem C.8.

It is the same as that of Theorem 3.10. ∎

##  Appendix D Proof of Lemma 3.7

Let us consider the following hybrids for $j\in\\{0,1,...,n\\}$.

$\mathsf{Hyb}_{j}$:

  1. 1.

$\mathcal{A}_{1}$ generates $(m^{0},m^{1})\in\\{0,1\\}^{n}\times\\{0,1\\}^{n}$
and sends it to the challenger.

  2. 2.

The challenger computes

$\displaystyle(\mathsf{com}_{i}(m_{i}^{1}),\mathsf{d}_{i}(m_{i}^{1}),\mathsf{ck}_{i}(m_{i}^{1}))\leftarrow\mathsf{Commit}(1^{\lambda},m^{1}_{i})$
(92)

for $i\in[j]$ and

$\displaystyle(\mathsf{com}_{i}(m_{i}^{0}),\mathsf{d}_{i}(m_{i}^{0}),\mathsf{ck}_{i}(m_{i}^{0}))\leftarrow\mathsf{Commit}(1^{\lambda},m^{0}_{i})$
(93)

for each $i\in\\{j+1,...,n\\}$, and sends
$\\{\mathsf{com}_{i}(m_{i}^{1})\\}_{i\in[j]}$ and
$\\{\mathsf{com}_{i}(m_{i}^{0})\\}_{i\in\\{j+1,...,n\\}}$ to
$\mathcal{A}_{1}$. Here, $m_{i}^{b}$ is the $i$-th bit of $m^{b}$.

  3. 3.

At some point, $\mathcal{A}_{1}$ sends $\\{\mathsf{cert}_{i}\\}_{i\in[n]}$ to
the challenger, and sends its internal state to $\mathcal{A}_{2}$.

  4. 4.

The challenger computes
$\mathsf{Cert}(\mathsf{cert}_{i},\mathsf{ck}_{i}(m_{i}^{1}))$ for each
$i\in[j]$ and $\mathsf{Cert}(\mathsf{cert}_{i},\mathsf{ck}_{i}(m_{i}^{0}))$
for each $i\in\\{j+1,...,n\\}$. If the outputs are $\top$ for all $i\in[n]$,
then the challenger outputs $\top$, and sends
$\\{\mathsf{d}_{i}(m_{i}^{1}),\mathsf{ck}_{i}(m_{i}^{1})\\}_{i\in[j]}$ and
$\\{\mathsf{d}_{i}(m_{i}^{0}),\mathsf{ck}_{i}(m_{i}^{0})\\}_{i\in\\{j+1,...,n\\}}$
to $\mathcal{A}_{2}$. Else, the challenger outputs $\bot$, and sends $\bot$ to
$\mathcal{A}_{2}$.

  5. 5.

$\mathcal{A}_{2}$ outputs $b^{\prime}\in\\{0,1\\}$.

  6. 6.

If the challenger outputs $\top$, then the output of the experiment is
$b^{\prime}$. Otherwise, the output of the experiment is $\bot$.

It is clear that
$\mathsf{Hyb}_{0}=\mathsf{Exp}_{\Sigma,\mathcal{A}}^{\mathsf{bit}\mbox{-}\mathsf{ever}\mbox{-}\mathsf{hide}}(\lambda,0)$
and
$\mathsf{Hyb}_{n}=\mathsf{Exp}_{\Sigma,\mathcal{A}}^{\mathsf{bit}\mbox{-}\mathsf{ever}\mbox{-}\mathsf{hide}}(\lambda,1)$.
Furthermore, we can show

$\displaystyle\left|\Pr[\mathsf{Hyb}_{j}=1]-\Pr[\mathsf{Hyb}_{j+1}=1]\right|\leq{\mathsf{negl}}(\lambda)$
(94)

for each $j\in\\{0,1,...,n-1\\}$. (Its proof is given below.) From these
facts, we obtain Lemma 3.7.

Let us show the remaining one. To show it, let us assume that
$\left|\Pr[\mathsf{Hyb}_{j}=1]-\Pr[\mathsf{Hyb}_{j+1}=1]\right|$ is non-
negligible. Then, we can construct an adversary $\mathcal{B}$ that can break
the certified everlasting hiding of $\Sigma_{\mathsf{ccd}}$ as follows.

  1. 1.

$\mathcal{B}$ receives $(m^{0},m^{1})$ from $\mathcal{A}_{1}$, and computes

$\displaystyle(\mathsf{com}_{i}(m_{i}^{1}),\mathsf{d}_{i}(m_{i}^{1}),\mathsf{ck}_{i}(m_{i}^{1}))\leftarrow\mathsf{Commit}(1^{\lambda},m^{1}_{i})$
(95)

for $i\in[j]$ and

$\displaystyle(\mathsf{com}_{i}(m_{i}^{0}),\mathsf{d}_{i}(m_{i}^{0}),\mathsf{ck}_{i}(m_{i}^{0}))\leftarrow\mathsf{Commit}(1^{\lambda},m^{0}_{i})$
(96)

for $i\in\\{j+2,...,n\\}$.

  2. 2.

$\mathcal{B}$ sends $(m_{j+1}^{0},m_{j+1}^{1})$ to the challenger of
$\mathsf{Exp}_{\Sigma_{\mathsf{ccd}},\mathcal{B}}^{\mathsf{ever}\mbox{-}\mathsf{hide}}(\lambda,b^{\prime})$,
and receives $\mathsf{com}_{j+1}(m_{j+1}^{b^{\prime}})$ from the challenger.

  3. 3.

$\mathcal{B}$ sends $\\{\mathsf{com}_{i}(m_{i}^{1})\\}_{i\in[j]}$,
$\mathsf{com}_{j+1}(m_{j+1}^{b^{\prime}})$, and
$\\{\mathsf{com}_{i}(m_{i}^{0})\\}_{i\in\\{j+2,...,n\\}}$, to
$\mathcal{A}_{1}$.

  4. 4.

$\mathcal{A}_{1}$ sends $\\{\mathsf{cert}_{i}\\}_{i\in[n]}$ to $\mathcal{B}$,
and sends its internal state to $\mathcal{A}_{2}$.

  5. 5.

$\mathcal{B}$ sends $\mathsf{cert}_{j+1}$ to the challenger of
$\mathsf{Exp}_{\Sigma_{\mathsf{ccd}},\mathcal{B}}^{\mathsf{ever}\mbox{-}\mathsf{hide}}(\lambda,b^{\prime})$,
and receives
$(\mathsf{d}_{j+1}(m_{j+1}^{b^{\prime}}),\mathsf{ck}_{j+1}(m_{j+1}^{b^{\prime}}))$
or $\bot$ from the challenger. If $\mathcal{B}$ receives $\bot$ from the
challenger, it outputs $\bot$ and aborts.

  6. 6.

$\mathcal{B}$ sends all $\mathsf{d}_{i}$ and $\mathsf{ck}_{i}$ to
$\mathcal{A}_{2}$.

  7. 7.

$\mathcal{A}_{2}$ outputs $b^{\prime\prime}$.

  8. 8.

$\mathcal{B}$ computes $\mathsf{Cert}$ for all $\mathsf{cert}_{i}$, and
outputs $b^{\prime\prime}$ if all results are $\top$. Otherwise, $\mathcal{B}$
outputs $\bot$.

It is clear that $\Pr[\mathcal{B}\to 1\mid
b^{\prime}=0]=\Pr[\mathsf{Hyb}_{j}=1]$ and $\Pr[\mathcal{B}\to 1\mid
b^{\prime}=1]=\Pr[\mathsf{Hyb}_{j+1}=1]$. By assumption,
$|\Pr[\mathsf{Hyb}_{j}=1]-\Pr[\mathsf{Hyb}_{j+1}=1]|$ is non-negligible, and
therefore $|\Pr[\mathcal{B}\to 1\mid b^{\prime}=0]-\Pr[\mathcal{B}\to 1\mid
b^{\prime}=1]|$ is non-negligible, which contradict the certified everlasting
hiding of $\Sigma_{\mathsf{ccd}}$.