This motivates the definition of pseudodensity, which relaxes the notion of
density:

######  Definition 5.1 (Pseudodensity [Imp09]).

Given a class $\mathcal{F}$ of functions $f:\mathcal{X}\rightarrow[0,1]$,
distributions $\mathcal{D},\mathcal{S}$ on $\mathcal{X}$, and
$\epsilon,\delta>0$, we say that $\mathcal{S}$ is
_$(\mathcal{F},\epsilon,\delta)$ -pseudodense_ in $\mathcal{D}$ if for all
$f\in\mathcal{F}$,

$\mathop{\mathbb{E}}_{x\sim\mathcal{D}}[f(x)]\geq\delta\cdot\mathop{\mathbb{E}}_{x\sim\mathcal{S}}[f(x)]-\epsilon.$

We can think of pseudodensity as saying that the distinguishers
$f\in\mathcal{F}$ cannot tell whether $\mathcal{S}$ has low density or not. As
showed above, if $\mathcal{S}$ is $\delta$-dense, then $\mathcal{S}$ is
$(\mathcal{F},\epsilon,\delta)$-pseudodense. But another way for $\mathcal{S}$
to be pseudodense in $\mathcal{D}$ is the following: If there is a
distribution $\mu$ that is $(\mathcal{F},\epsilon)$-indistinguishable from
$\mathcal{S}$ by $\mathcal{F}$ and such that $\mu$ is $\delta$-dense in
$\mathcal{D}$ [Imp17]. Assuming the pseudodensity of $\mathcal{S}$, the Dense
Model Theorem precisely states that we can always find such a $\mu$. Hence,
the interesting case occurs when the density of $\mathcal{S}$ is much smaller
than $\delta$, because then the DMT shows that, even in that case, we can
still find a distribution of large density that is indistinguishable from
$\mathcal{S}$ to $\mathcal{F}$. Similar to the difference of the classes of
distinguishers in the assumption and the conclusion of IHCL and DMT, the
pseudodensity assumption on $\mathcal{S}$ is with respect an enlarged class of
distinguishers, whereas the conclusion is with respect to the original class
$\mathcal{F}$.

We can now state the Dense Model Theorem:

######  Theorem 5.2 (DMT, [Imp09, Thm. 3], [Rei+08]).

Let $\mathcal{X}$ be a finite domain, $\mathcal{F}$ a family of functions
$f\colon\mathcal{X}\rightarrow[0,1]$, $\mathcal{V}$ and $\mathcal{S}$ two
distributions on $\mathcal{X}$, and $\epsilon,\delta>0$. Then there exist
$t,q=\emph{poly}(1/\epsilon,1/\delta)$ such that if $\mathcal{S}$ is
$(\mathcal{F}_{t,q},\epsilon,\delta)$-pseudodense in $\mathcal{V}$, then there
exists a $(\delta-O(\epsilon))$-dense distribution $\mu$ in $\mathcal{V}$ such
that $\mu$ is $(\mathcal{F},O(\epsilon/\delta))$-indistinguishable from
$\mathcal{S}$.

Therefore, in order to prove the DMT, we need to construct a distribution
$\mu$ such that:

  1. 1.

_Density._ Distribution $\mu$ has density $\delta-O(\epsilon)$ in
$\mathcal{V}$.

  2. 2.

_Indistinguishability._ Distributions $\mu$ and $\mathcal{S}$ are
$O(\mathcal{F},\epsilon/\delta)$-indistinguishable.

Similarities to Impagliazzo’s Hardcore Lemma. The Dense Model Theorem shares
many similarities to Impagliazzo’s Hardcore Lemma (Section 3). We highlight
some of their parallels, which also apply to their $++$ counterparts, as we
will see with our DMT$++$ statement.

  1. 1.

The assumption. In IHCL, we assume that the function $g$ is
$(F_{t,q},\delta)$-hard. In DMT, we assume that $\mathcal{S}$ is
$(\mathcal{F}_{t,q},\epsilon,\delta)$-pseudodense in $\mathcal{V}$.

  2. 2.

The density. In IHCL, we want to ensure that the hardcore distribution $\mu$
is dense enough; more concretely, $2\delta$-dense. In DMT, we want the
distribution $\mu$ to be dense enough; more concretely,
$(\delta-O(\epsilon))$-dense.

  3. 3.

Indistinguishability. In IHCL, we need to ensure that $g$ is strongly hard
when sampling according to $\mu$, which corresponds to $g$ being
indistinguishable from the constant $1/2$ function when sampling according to
$\mu$. In DMT, we want the distribution $\mu$ to be indistinguishable from
$\mathcal{S}$.

###  5.2 The DMT++ Theorem

We can now state our DMT$++$ theorem:

######  Theorem 5.3 (DMT$++$).

Let $\mathcal{X}$ be a finite domain, let $\mathcal{F}$ be a family of
functions $f\colon\mathcal{X}\rightarrow[0,1]$, let $S,V\subseteq\mathcal{X}$
be two disjoint sets, let distributions $\mathcal{S}$ and $\mathcal{V}$ be
defined on $S$ and $V$, respectively, and let $\epsilon,\gamma>0$. There
exists a partition $\mathcal{P}\in\mathcal{F}_{t,q,k}$ of $S\cup V$ with
$t=O(1/(\epsilon^{4}\gamma)\cdot\log(|\mathcal{X}|/\epsilon))$,
$q=O(1/\epsilon^{2})$, $k=O(1/\epsilon)$, which satisfies that for each
$P\in\mathcal{P}$ such that $\eta_{P}\geq\gamma$, distributions
$\mathcal{S}|_{P}$ and $\mathcal{V}|_{P}$ are
$(\mathcal{F},\epsilon_{P})$-indistinguishable for all $P\in\mathcal{P}$,
where

$\eta_{P}=\dfrac{1}{2}\Big{(}\Pr_{x\sim\mathcal{S}}[x\in
P]+\Pr_{x\sim\mathcal{V}}[x\in P]\Big{)},\quad
v_{P}=\dfrac{\Pr_{x\sim\mathcal{S}}[x\in
P]}{2\eta_{P}},\quad\epsilon_{P}=\dfrac{\epsilon}{v_{P}\cdot(1-v_{P})}.$

By the definition of density of a distribution, it immediately follows that
$\mathcal{V}|_{P}$ is $\delta_{P}$-dense in $\mathcal{V}$ for
$\delta_{P}=\Pr_{x\sim\mathcal{V}}[x\in P]$. By letting
$g:\mathcal{X}\rightarrow\\{0,1\\}$ be defined as the indicator function for
the set $S$, we can also write the density of $\mathcal{V}|_{p}$ in
$\mathcal{V}$ as a function of $v_{P}$ and $\eta_{P}$. More concretely,
$\delta_{P}=Pr_{x\sim\mathcal{V}}[x\in P]=2\eta_{P}\cdot(1-v_{P})$.

We remark that, since $b_{P}=\min\\{v_{P},1-v_{P}\\}$, it follows that
$\frac{1}{2}\cdot b_{P}\leq v_{P}(1-v_{P})\leq b_{P}$. Therefore, the term
$v_{P}(1-v_{P})$ in $\epsilon_{P}$ is capturing the balance of $g$ (i.e., the
characteristic function of the set $S$) on the set $P\in\mathcal{P}$.

Interpretation of the DMT$++$. Before going into the proof of Theorem 5.3, we
explain what our DMT++ theorem entails and how it is a stronger and more
general version of the original DMT theorem.

  * •

In Theorem 5.3, we remove the assumption that the $\mathcal{S}$ is
$(\mathcal{F}_{t,q},\epsilon,\delta)$-pseudodense, but we can still create a
partition $\mathcal{P}$ of the domain $S\cup V$ such that every piece $P$ in
the partition has a “model” for a partition of the distribution $\mathcal{S}$.

  * •

We provide a generalization of the notion of pseudodensity, and we are able to
argue about the density of each model with the general parameter
$\delta_{P}=\Pr_{x\sim\mathcal{D}}[x\in P]$, rather than using the parameter
$\delta$ in the original DMT statement (which we do not have, since we do not
have the $(\epsilon,\delta)$-pseudodensity assumption on $\mathcal{S}$).

  * •

In our $++$ theorem, the original DMT occurs both “locally” (on each
$P\in\mathcal{P}$) and “globally” (on $\mathcal{X})$. Moreover, as it was the
case of IHCL$++$ and PAME$++$, we can recover the original DMT theorem from
our DMT$++$ by “gluing” together the “models” $\mathcal{V}|_{P}$ of each piece
$P$ (according to the weight of each piece as dictated by the distribution
$\mathcal{V}$). The density $\Pr_{x\sim\mathcal{V}}[x\in P]$ of each model is
such that when we bring back the assumption that $\mathcal{S}$ is
$(\mathcal{F}_{t,q},\epsilon,\delta)$-pseudodense, we obtain that the “global”
model for $\mathcal{S}$ has density $O(\delta-O(\epsilon))$, as in the
original DMT (Theorem 5.2).

An illustration of a simplified version of the DMT$++$ Theorem can be found in
Figure 2.

Figure 2: Visual depiction of Theorem 5.3 in the case where $\mathcal{S}$ and
$\mathcal{V}$ correspond to the uniform distributions over $S$ and $V$,
respectively. In this case, $\Pr_{x\sim\mathcal{S}}[x\in P]=|P\cap S|/|S|$ and
$\Pr_{x\sim\mathcal{V}}[x\in P]=|P\cap V|/|V|$. The MC partition (indicated
with black lines in the right figure) is such that, for each level set $P$ in
the partition, the uniform distribution over $P\cap V$ is a model for the
corresponding uniform distribution over $P\cap S$. One such level set is
illustrated in purple in the right figure.

###### Proof of Theorem 5.3.

Let $g:\mathcal{X}\rightarrow\\{0,1\\}$ be the indicator function for the set
$S$, and we let $\mathcal{D}$ be the distribution over $\mathcal{X}$ defined
as $\frac{1}{2}\mathcal{S}+\frac{1}{2}\mathcal{V}$. We invoke the MC Theorem
(Theorem 2.12) with the domain $\mathcal{X}$, function family $\mathcal{F}$,
function $g$, distribution $\mathcal{V}$, and the original $\epsilon,\gamma$
parameters. This yields a partition $\mathcal{P}\in\mathcal{F}_{t,q,k}$ with
$t=O(1/(\epsilon^{4}\gamma)\cdot\log(|\mathcal{X}|/\epsilon))$,
$q=O(1/\epsilon^{2})$, $k=O(1/\epsilon)$ satisfying

$\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{R}|_{P}}[f(x)\cdot(g(x)-v_{P})]\Big{|}\leq\epsilon$

for all $P\in\mathcal{P}$ such that $\eta_{P}\geq\gamma$. We claim that this
partition $\mathcal{P}$ satisfies the conditions of Theorem 5.3.888Note that
there is no function $g$ in the statement of Theorem 5.3, and so here $v_{P}$
and $\eta_{P}$ are as defined in the theorem statement. The point is that when
$g$ corresponds to the characteristic function of the set $S$ and
$\mathcal{D}$ corresponds to $\frac{1}{2}\mathcal{S}+\frac{1}{2}\mathcal{V}$,
then $v_{P}$ and $\eta_{P}$ correspond to our usual balance and size
parameters (Definitions 2.4, 2.5). By the definition of the distribution
$\mathcal{V}$, it follows that

$\eta_{P}=\Pr_{x\sim\mathcal{D}}[x\in
P]=\dfrac{1}{2}\Big{(}\Pr_{x\sim\mathcal{S}}[x\in
P]+\Pr_{x\sim\mathcal{V}}[x\in P]\Big{)}.$

Fix any $P\in\mathcal{P}$ such that $\eta_{P}\geq\gamma$. First, we notice
that since $g$ is boolean and $g(x)=1$ if and only if $x\in S$ by definition,
it follows that

$v_{P}=\dfrac{\Pr_{x\sim\mathcal{S}}[x\in P]}{\Pr_{x\sim\mathcal{S}}[x\in
P]+\Pr_{x\sim\mathcal{V}}[x\in P]}=\dfrac{\Pr_{x\sim\mathcal{S}}[x\in
P]}{2\eta_{P}}.$

We need to show that the distributions $\mathcal{S}|_{P}$ and
$\mathcal{V}|_{P}$ are $(\mathcal{F},\epsilon_{P})$-indistinguishable, where

$\epsilon_{P}=\dfrac{\epsilon}{v_{P}(1-v_{P})}.$

By definition of indistinguishability, this corresponds to showing that

$\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{S}|_{P}}[f(x)]-\mathop{\mathbb{E}}_{x\sim\mathcal{V}|_{P}}[f(x)]\Big{|}\leq\dfrac{\epsilon}{v_{P}(1-v_{P})}.$

This follows from our Lemma 2.17: by the MC Theorem, we satisfy the assumption
of Lemma 2.17 within each $P\in\mathcal{P}$ such that $\eta_{P}\geq\gamma$.
Therefore, by statement (3) in Lemma 2.17 it follows that the 0s and the 1s of
$g$ are indistinguishable. By our definition of $g$ as the characteristic
function of $S$, this corresponds precisely to saying that the distinguishers
$f\in\mathcal{F}$ cannot tell whether we are sampling from $\mathcal{S}|_{P}$
or from $\mathcal{V}|_{P}$ with advantage larger than
$\frac{\epsilon}{v_{P}(1-v_{P})}$, as we wanted to show. ∎

###  5.3 Recovering the original DMT from DMT$++$

We show how to recover the original DMT theorem from our DMT$++$. As it was
the case of IHCL and PAME, the key idea is to “glue together” the models
$\mathcal{D}|_{P}$ for each “good” $P\in\mathcal{P}$. Namely, those
$P\in\mathcal{P}$ that have $\eta_{P}\geq\gamma$ and $b_{P}\geq\tau$ for
parameters $\gamma,\tau$ (Definition 3.4 from Section 3). Recall that in the
DMT statement we are bringing back the assumption that $\mathcal{S}$ is
$(\mathcal{F}_{t,q},\epsilon,\delta)$-pseudodense. As we did in Section 3, we
begin by showing an intermediate proposition:

######  Proposition 5.4.

Let
$\mathcal{X},\mathcal{F},S,V,\mathcal{S},\mathcal{V},\epsilon,\gamma,\mathcal{P},\eta_{P},t,q,k$
be as in Theorem 5.3. Moreover, assume that $\mathcal{S}$ is
$(F_{t+k,q},\epsilon,\delta)$-pseudodense in $\mathcal{V}$ for some
$\delta>0$. Then, for all $P\in\mathcal{P}$ such that $\eta_{P}\geq\gamma$,

$\delta\cdot\Pr_{x\sim\mathcal{S}}[x\in P]\leq\Pr_{x\sim\mathcal{V}}[x\in
P]+\epsilon.$

###### Proof.

Recall that by definition of pseudodensity, and by the assumption that
$\mathcal{S}$ is $(\mathcal{F}_{t+k,q},\epsilon,\delta)$-pseudodense in
$\mathcal{V}$, we know that for all $f\in\mathcal{F}_{t+k,q}$,

$\delta\cdot\Pr_{x\sim\mathcal{S}}[f(x)=1]-\epsilon\leq\Pr_{x\sim\mathcal{V}}[f(x)=1].$

Fix some $P\in\mathcal{P}$. Let $\hat{f}\in\mathcal{F}_{t,q}$ where
$t=O(1/(\epsilon^{4}\gamma)\cdot\log(|\mathcal{X}|/\epsilon))$,
$q=O(1/\epsilon^{2})$ be the partition membership function for $\mathcal{P}$
as given by Definition 2.11. That is,
$\mathcal{P}=\\{\hat{f}^{-1}(1),\ldots,\hat{f}^{-1}(k)\\}$. Given
$P\in\mathcal{P}$, we define the function $f^{P}$ as
$f^{P}=f^{P}_{\mathrm{post}}\circ\hat{f}$, where
$f^{P}_{\mathrm{post}}(i)=\mathbbm{1}[\hat{f}(i)=P]$. That is, we think of
$f^{P}$ as the indicator function for the set $P$. As argued in Section 3.3,
$f^{P}_{\mathrm{post}}$ can be computed by a circuit of size $k$ (see [Bar22,
§9.1.1.]), so $f^{P}\in\mathcal{F}_{t+k,q}$.

Then, by applying the pseudodensity assumption on $\mathcal{S}$ to this
function $f^{P}\in\mathcal{F}_{t+k,q}$, we obtain that

$\delta\cdot\Pr_{x\sim\mathcal{S}}[f^{P}(x)=1]-\epsilon\leq\Pr_{x\sim\mathcal{V}}[f^{P}(x)=1].$

Then, by the definition of $f^{P}$ it follows that

$\Pr_{x\sim\mathcal{S}}[f^{P}(x)=1]=\Pr_{x\sim\mathcal{S}}[x\in
P],\quad\Pr_{x\sim\mathcal{V}}[f^{P}(x)=1]=\Pr_{x\sim\mathcal{V}}[x\in P],$

Therefore, we have that

$\delta\cdot\Pr_{x\sim\mathcal{S}}[x\in
P]\leq\Pr_{x\sim\mathcal{V}}[f^{P}(x)=1]+\epsilon,$

which corresponds to the inequality stated in Proposition 5.4. ∎

Given this proposition, we can now prove the DMT from our DMT$++$. In doing
so, we use a trick originally due to Impagliazzo, in his series of works where
he explores the relationship between IHCL and the DMT [Imp08, Imp09, Gak12,
Imp17]. More specifically, Impagliazzo shows that IHCL implies the DMT: given
a pseudodense set $S$, one can prove that the function $g$ defined as the
characteristic function of $g$ is weakly hard, if we consider an appropriate
distribution $\mathcal{D}$ over an augmented domain
$\mathcal{X}^{\prime}$,999One needs to be careful with defining the
distribution $\mathcal{D}$, because the DMT is most interesting when $S$ has
very low density, and thus we need to magnify $S$ in order to ensure that we
sample from $S$ with some constant probability. where we append the bit $b=1$
to $x\in\mathcal{X}$ such that $x\in S$, and append the bit $b=0$ to
$x\in\mathcal{X}$ such that $x\in\mathcal{X}\setminus S$. We can then
construct a “model” for $S$ by using the hardcore distribution for $g$ given
by the IHCL. A full proof of this implication can be found in [Cas23, §6.2].

In the following proof, we use Impagliazzo’s trick of augmenting the domain
using $\mathcal{S}$:

###### Proof of DMT from DMT$++$.

Let $\mathcal{X},\mathcal{F},\mathcal{S},\mathcal{V},\epsilon,\delta$ be the
assumption parameters in the DMT statement (Theorem 5.2). We define the
parameters $\epsilon^{\prime}:=\epsilon^{2}\delta$,
$\gamma:=\epsilon\epsilon^{\prime}$, $\tau:=\epsilon\delta$, and invoke the
DMT$++$ Theorem (Theorem 5.3) with the domain
$\mathcal{X}^{\prime}=\mathcal{X}\times\\{0,1\\}$,
$S=\mathcal{X}\times\\{1\\}$, $V=\mathcal{X}\times\\{0\\}$,
$\mathcal{S}^{\prime}=\mathcal{S}\times\\{1\\}$, and
$\mathcal{V}^{\prime}=\mathcal{V}\times\\{0\\}$, the function family
$\mathcal{F}^{\prime}=\\{f^{\prime}(x,b)=f(x)\\}$ for some $f\in\mathcal{F}$,
and parameters $\epsilon^{\prime},\gamma$. By the DMT$++$ (Theorem 5.3), we
obtain a partition $\mathcal{P}\in\mathcal{F}_{t,q,k}$ of
$\mathcal{X}^{\prime}$ with $t=O(1/(\epsilon^{\prime
4}\gamma)\cdot\log(|\mathcal{X}^{\prime}|/\epsilon^{\prime}))$,
$q=O(1/\epsilon^{\prime 2})$, $k=O(1/\epsilon^{\prime})$ such that, for each
$P\in\mathcal{P}$ where $\eta_{P}\geq\gamma=\epsilon\epsilon^{\prime}$, the
distribution $\mathcal{V}^{\prime}|_{P}$ is
$(\mathcal{F}^{\prime},\epsilon^{\prime}_{P})$-indistinguishable from
$\mathcal{S}^{\prime}|_{P}$. Given these “local models”
$\mathcal{V}^{\prime}|_{P}$, we construct the claimed global distribution
$\mu$ as follows: we define $\mu$ to be the weighted average of the “models”
$\mathcal{V}^{\prime}|_{P}$ such that $P\in\mathcal{P}$ is
$(\gamma,\tau)$-good. Formally, for each $x\in V$, let

$\mu(x)=\dfrac{\Pr_{(x,1)\sim\mathcal{S}^{\prime}}[(x,1)\in
P]\cdot\mathcal{V}^{\prime}(x,0)\cdot\mathbbm{1}_{G}(P)}{\mathop{\mathbb{E}}_{Q\sim\mathcal{P}(\mathcal{S}^{\prime})}[\mathbbm{1}_{G}(Q)]},$

where $P$ corresponds to the unique $P\in\mathcal{P}$ such that $x\in P$
(which is unique since $\mathcal{P}$ is a partition). Note that the purpose of
the denominator is to normalize $\mu$ so that $\sum_{x}\mu(x)=1$. The
expression for $\mu(x)$ should be understood as follows: in order to choose a
$x\in V$, we can instead first choose a set $P$ with probability
$\Pr_{x\sim\mathcal{S}^{\prime}}[x\in P]$, and then sample from
$\mathcal{V}^{\prime}|_{P}$.

Let $v_{P}$ as in Theorem 5.3. First, by combining Proposition 5.4 and the
fact that

$\Pr_{x\sim\mathcal{V}^{\prime}}[x\in P]=2\eta_{P}(1-v_{P}),$

it follows that

$\dfrac{1}{\delta}+\dfrac{\epsilon^{\prime}}{\delta}\cdot\Pr_{x\sim\mathcal{V}^{\prime}}[x\in
P]=\dfrac{1}{\delta}+\dfrac{\epsilon^{\prime}}{2\delta\eta_{P}(1-v_{P})}=\dfrac{1}{\delta\cdot(1-O(\epsilon^{\prime}/(\eta_{P}(1-v_{P})))}.$

Recall that we only “glue up” the parts $P$ that are $(\gamma,\tau)$-good, and
recall that $\mathbbm{1}_{G}(P)$ returns 1 if $\eta_{P}\geq\gamma$ and
$k_{P}\geq\tau$, and 0 otherwise. Then, following a similar analysis as the
one described in Section 3.3, it follows that

$\mathop{\mathbb{E}}_{P\sim\mathcal{D}(\mathcal{P})}\Bigg{[}\dfrac{\epsilon^{\prime}}{v_{P}(1-v_{P})}\cdot\mathbbm{1}_{G}(P)\Bigg{]}\leq\dfrac{\epsilon^{\prime}}{\tau},$

where $\epsilon^{\prime}=\epsilon^{2}\delta$,
$\gamma=\epsilon\epsilon^{\prime}$, and $\tau=\epsilon\delta$. Therefore, the
density of the “glued up” distribution $\mu$ when we only glue up the
$(\gamma,\tau)$-good sets is equal to $\delta\cdot(1-O(\epsilon))$.

Next, we show the indistinguishability condition; namely, that $\mu$ is
$\mathcal{F},O(\epsilon/\delta)$-indistinguishable from $\mathcal{S}$. By
Theorem 5.3, we know that for all good $P\in\mathcal{P}$,

$\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{S}^{\prime}|_{P}}[f(x)]-\mathop{\mathbb{E}}_{x\sim\mathcal{V}^{\prime}|_{P}}[f(x)]\Big{|}\leq\epsilon^{\prime}_{P}.$

By the definition of $\mu$ (which implies that $\mu(x)$ is never contained in
$S$ given that all values $x\sim\mu$ are in $V$) and the law of total
probability, it follows that

$\displaystyle\big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{S}^{\prime}}[f(x)=1]-\mathop{\mathbb{E}}_{x\sim\mu}[f(x)]\big{|}$
$\displaystyle=\Big{|}\sum_{P\in\mathcal{P}}\Big{(}\Pr_{x\sim\mathcal{S}^{\prime}|_{P}}[f(x)=1]\cdot\Pr_{x\sim\mathcal{S}^{\prime}}[x\in
P]$
$\displaystyle\qquad\qquad\qquad\quad\,\,-\Pr_{x\sim\mathcal{V}^{\prime}}[f(x)=1]\cdot\Pr_{x\sim\mathcal{V}^{\prime}}[x\in
P]\Big{)}\cdot\mathbbm{1}_{G}(P)\Big{|}$
$\displaystyle\leq\sum_{P\in\mathcal{P}}\Pr_{x\sim\mathcal{S}^{\prime}}[x\in\mathcal{P}]\cdot\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{S}^{\prime}|_{P}}[f(x)]-\mathop{\mathbb{E}}_{x\sim\mathcal{V}^{\prime}|_{P}}[f(x)]\Big{|}\cdot\mathbbm{1}_{G}(P).$

By applying Theorem 5.3 to each of the summands, the above expression becomes

$\displaystyle\sum_{P\in\mathcal{P}}\epsilon^{\prime}_{P}\cdot\Pr_{x\sim\mathcal{S}^{\prime}}[x\in
P]\cdot\mathbbm{1}_{G}(P)$
$\displaystyle=\sum_{P\in\mathcal{P}}\dfrac{\epsilon^{\prime}}{v_{P}\cdot(1-v_{P})}\cdot\Pr_{x\sim\mathcal{S}^{\prime}}[x\in
P]\cdot\mathbbm{1}_{G}(P)$
$\displaystyle\leq\dfrac{1}{\delta}\sum_{P\in\mathcal{P}}\dfrac{\epsilon^{\prime}}{v_{P}\cdot(1-v_{P})}\cdot\Pr_{x\sim\mathcal{V}^{\prime}}[x\in
P]\cdot\mathbbm{1}_{G}(P).$

Since $\Pr_{x\sim\mathcal{V}^{\prime}}[x\in P]=2\eta_{P}\cdot(1-v_{P})$,
following the analysis from Section 3.3 it follows that each term in the
summand is at most $2\tau/v_{P}\leq 2\epsilon^{\prime}/\tau$. Since
$\epsilon^{\prime}=\epsilon^{2}\delta$ and $\tau=\epsilon\delta$ imply that
$\epsilon^{\prime}/\tau=\epsilon$, it follows that

$\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{S}^{\prime}}[f(x)=1]-\mathop{\mathbb{E}}_{x\sim\mu}[f(x)]\Big{|}\leq\dfrac{\epsilon}{\delta},$

as we wanted to show. As in Section 3, we can modify $\mu$ so that we obtain
density exactly $\delta-O(\epsilon)$ while maintaining
$O(\epsilon/\delta)$-indistinguishability for the model. Thus, we have
recovered the original DMT theorem. ∎

Entropy interpretation of the DMT$++$. To conclude, we observe that the DMT
and DMT$++$ theorems can also be re-state in terms of pseudo-min-entropy.
Indeed, Reingold, Trevisan, Tulsiani, and Vadhan related the DMT and the
notion of pseudoentropy (Definition 4.2) [Rei+08, §4.1]. Essentially, we can
relate the pseudodensity of a set $\mathcal{S}$ to the notion of pseudo-min-
entropy by re-stating the DMT theorem as follows: If a distribution
$\mathcal{D}$ is $\delta$-dense in an $\epsilon$-pseudorandom set (i.e.,
$\mathcal{D}$ is $\epsilon$-indistinguishable from the uniform distribution on
$\mathcal{X}$), then $\mathcal{D}$ has $\epsilon$-pseudo-min-entropy
$\log|\mathcal{X}|-\log(1/\delta)$ [Rei+08, Propositions 4.2, 4.3]. As future
work, we believe it would be illustrative to re-state our DMT$++$ theorem in
terms of pseudo-min-entropy and compare it to the conclusion of the PAME$++$
theorem, which would further clarify how the fundamental concepts that we have
considered in this paper (indistinguishability, hardness, pseudo-average min-
entropy, pseudo-min-entropy, pseudodensity) relate to each other.

##  6 Conclusions & Future Work

We conclude by providing some other directions for future work.

Further generalizations of our results. Our results regarding the PAME$++$
could be generalized in two different ways. First, while our results in
Section 4 only concern non-uniform distinguishers (i.e., where the
distinguishers correspond to boolean circuits), the original results by Vadhan
& Zheng also consider uniform distinguishers (i.e., where the distinguishers
correspond to polynomial time algorithms), and their PAME theorem is thus
stated for both the uniform and non-uniform settings [VZ12, Zhe14]. While we
expect our results to carry onto the uniform setting, they require a different
type of technical treatment. Second, given the exponential dependence on the
number of classes in the Multiclass MC Theorem [Gop+22], our PAME$++$ theorem
only holds for $\ell=O(\log\log n)$, whereas the original PAME theorem holds
for $\ell=O(\log n)$. We would hope to be able to recover the original
parameters.

Future multicalibration algorithms. There are two possible ways of improving
our PAME$++$ parameters: One is to design a multiclass multicalibration
algorithm with better complexity parameters (a topic which is already a
current line of work within the multicalibration literature), and the other is
to try to achieve the PAME$++$ conclusion with a weaker notion of
multicalibration instead that has a polynomial dependence on the number of
classes.

Relatedly, all of the partition complexity parameters in our $++$ theorems
directly depend on the state-of-the-art multicalibration parameters from the
MC literature, given that we use the approximate MC theorems of [Héb+18] and
[Gop+22] as black-boxes, and thus any future improvement of the MC algorithms
is applicable to our results. In particular, we expect that the number of
calls to the weak agnostic learner in these type of algorithms can be reduced,
given that the original MC algorithms were more concerned with showing
feasibility rather than efficiency.

Other possible applications of our $++$ approach. The observation that
Multicalibration Theorem corresponds to a stronger and more general version of
the Regularity Lemma, which is the starting point of both this paper and the
concurrent work by Dwork, Lee, Lin, and Tankala [Dwo+23], as well as the
framework and tools that we have developed in this paper (in particular, our
complexity-theoretic reframing of multicalibration), can be applied to other
important implications of the Regularity Lemma outside of IHCL, PAME, the DMT,
and Szemerédi’s Regularity Lemma. As mentioned in the introduction, other
implications of the Regularity Lemma include applications in leakage resilient
cryptography [JP14, CCL18], weak notions of zero-knowledge [CLP15], Yao’s XOR
Theorem [GNW11], chain rules for computational entropy [GNW11, JP14], and
Chang’s inequality in Fourier analysis of boolean functions [IMR14]. We expect
that viewing these theorems as corollaries of the Multiaccuracy Theorem will
provide new insights into these established results, as well as new
connections and insights into the power of a multicalibrated partition.

## Acknowledgements

We are indebted to Parikshit Gopalan, Fabian Gundlach, Daniel Lee, Huijia
(Rachel) Lin, Omer Reingold, Jessica Sorrell, Pranay Tankala, and Benjy
Firester for helpful conversations throughout the development of this work. We
are also thankful to the Simons’ workshop on Multigroup Fairness and the
Validity of Statistical Judgement that took place in April 2023, where we
presented this work and received insightful feedback.

## References

  * [Bar22] Boaz Barak  “Introduction to Theoretical Computer Science”  Creative Commons, 2022  URL: https://files.boazbarak.org/introtcs/lnotes_book.pdf
  * [Bar+21] Noam Barda, Gal Yona, Guy N Rothblum, Philip Greenland, Morton Leibowitz, Ran Balicer, Eitan Bachmat and Noa Dagan  “Addressing bias in prediction models by improving subpopulation calibration”  In _Journal of the American Medical Informatics Association_ 28.3 Oxford Academic, 2021, pp. 549–558
  * [BHN23] Solon Barocas, Moritz Hardt and Arvind Narayanan  “Fairness and machine learning: Limitations and opportunities”  MIT Press, 2023
  * [BG18] Joy Buolamwini and Timnit Gebru  “Gender shades: Intersectional accuracy disparities in commercial gender classification”  In _Conference on Fairness, Accountability and Transparency_ , 2018, pp. 77–91  PMLR
  * [Cas23] Sílvia Casacuberta Puig  “Finding Simple Models of Complex Objects: From Regularity Lemmas to Algorithmic Fairness”, 2023  URL: https://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37376430
  * [CCL18] Yi-Hsiu Chen, Kai-Min Chung and Jyun-Jie Liao  “On the Complexity of Simulating Auxiliary Input”  In _Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part III_ 10822, Lecture Notes in Computer Science  Springer, 2018, pp. 371–390  DOI: 10.1007/978-3-319-78372-7\\_12
  * [Cho17] Alexandra Chouldechova  “Fair Prediction with Disparate Impact: A Study of Bias in Recidivism Prediction Instruments”  In _Big Data_ 5.2, 2017, pp. 153–163  DOI: 10.1089/BIG.2016.0047
  * [CLP15] Kai-Min Chung, Edward Lui and Rafael Pass  “From Weak to Strong Zero-Knowledge and Applications”  In _Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I_ 9014, Lecture Notes in Computer Science  Springer, 2015, pp. 66–92  DOI: 10.1007/978-3-662-46494-6\\_4
  * [Dod+08] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin and Adam D. Smith  “Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data”  In _SIAM J. Comput._ 38.1, 2008, pp. 97–139  DOI: 10.1137/060651380
  * [Dwo+12] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold and Richard S. Zemel  “Fairness through awareness”  In _Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012_ ACM, 2012, pp. 214–226  DOI: 10.1145/2090236.2090255
  * [Dwo+21] Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum and Gal Yona  “Outcome indistinguishability”  In _STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021_ ACM, 2021, pp. 1095–1108  DOI: 10.1145/3406325.3451064
  * [Dwo+23] Cynthia Dwork, Daniel Lee, Huijia Lin and Pranay Tankala  “From Pseudorandomness to Multi-Group Fairness and Back”  In _The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India_ 195, Proceedings of Machine Learning Research  PMLR, 2023, pp. 3566–3614  URL: https://proceedings.mlr.press/v195/dwork23a.html
  * [FK99] Alan M. Frieze and Ravi Kannan  “Quick Approximation to Matrices and Applications”  In _Comb._ 19.2, 1999, pp. 175–220  DOI: 10.1007/S004930050052
  * [Gak12] Sitanshu Gakkhar  “Hardcore measures, dense models and low complexity approximations”, 2012
  * [Gar+23] Sumegha Garg, Christopher Jung, Omer Reingold and Aaron Roth  “Oracle Efficient Online Multicalibration and Omniprediction”  In _CoRR_ abs/2307.08999, 2023  DOI: 10.48550/ARXIV.2307.08999
  * [GW11] Craig Gentry and Daniel Wichs  “Separating succinct non-interactive arguments from all falsifiable assumptions”  In _Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011_ ACM, 2011, pp. 99–108  DOI: 10.1145/1993636.1993651
  * [Glo+23] Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth and Jessica Sorrell  “Multicalibration as Boosting for Regression”  In _International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA_ 202, Proceedings of Machine Learning Research  PMLR, 2023, pp. 11459–11492  URL: https://proceedings.mlr.press/v202/globus-harris23a.html
  * [GNW11] Oded Goldreich, Noam Nisan and Avi Wigderson  “On Yao’s XOR-Lemma”  In _Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman_ 6650, Lecture Notes in Computer Science  Springer, 2011, pp. 273–301  DOI: 10.1007/978-3-642-22670-0\\_23
  * [GM19] Shafi Goldwasser and Silvio Micali  “Probabilistic encryption & how to play mental poker keeping secret all partial information”  In _Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali_ ACM, 2019, pp. 173–201  DOI: 10.1145/3335741.3335749
  * [Gop+22] Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan and Udi Wieder  “Omnipredictors”  In _13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA_ 215, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 79:1–79:21  DOI: 10.4230/LIPICS.ITCS.2022.79
  * [GKR23] Parikshit Gopalan, Michael P. Kim and Omer Reingold  “Characterizing notions of omniprediction via multicalibration”  In _CoRR_ abs/2302.06726, 2023  DOI: 10.48550/ARXIV.2302.06726
  * [Gop+22a] Parikshit Gopalan, Michael P. Kim, Mihir Singhal and Shengjia Zhao  “Low-Degree Multicalibration”  In _Conference on Learning Theory, 2-5 July 2022, London, UK_ 178, Proceedings of Machine Learning Research  PMLR, 2022, pp. 3193–3234  URL: https://proceedings.mlr.press/v178/gopalan22a.html
  * [Gop+22b] Parikshit Gopalan, Omer Reingold, Vatsal Sharan and Udi Wieder  “Multicalibrated Partitions for Importance Weights”  In _International Conference on Algorithmic Learning Theory, 29 March - 1 April 2022, Paris, France_ 167, Proceedings of Machine Learning Research  PMLR, 2022, pp. 408–435  URL: https://proceedings.mlr.press/v167/gopalan22a.html
  * [Gow10] W.. Gowers  “Decompositions, approximate structure, transference, and the Hahn-Banach theorem”  In _Bull. Lond. Math. Soc._ 42.4, 2010, pp. 573–606  DOI: 10.1112/blms/bdq018
  * [GT08] Ben Green and Terence Tao  “The primes contain arbitrarily long arithmetic progressions”  In _Ann. of Math. (2)_ 167.2, 2008, pp. 481–547  DOI: 10.4007/annals.2008.167.481
  * [Hås+99] Johan Håstad, Russell Impagliazzo, Leonid A. Levin and Michael Luby  “A Pseudorandom Generator from any One-way Function”  In _SIAM J. Comput._ 28.4, 1999, pp. 1364–1396  DOI: 10.1137/S0097539793244708
  * [Héb+18] Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold and Guy N. Rothblum  “Multicalibration: Calibration for the (Computationally-Identifiable) Masses”  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ 80, Proceedings of Machine Learning Research  PMLR, 2018, pp. 1944–1953  URL: http://proceedings.mlr.press/v80/hebert-johnson18a.html
  * [Hol05] Thomas Holenstein  “Key agreement from weak bit agreement”  In _Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005_ ACM, 2005, pp. 664–673  DOI: 10.1145/1060590.1060689
  * [Ilv20] Christina Ilvento  “Metric Learning for Individual Fairness”  In _1st Symposium on Foundations of Responsible Computing, FORC 2020, June 1-3, 2020, Harvard University, Cambridge, MA, USA (virtual conference)_ 156, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 2:1–2:11  DOI: 10.4230/LIPICS.FORC.2020.2
  * [Imp95] Russell Impagliazzo  “Hard-Core Distributions for Somewhat Hard Problems”  In _36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995_ IEEE Computer Society, 1995, pp. 538–545  DOI: 10.1109/SFCS.1995.492584
  * [Imp08] Russell Impagliazzo  “When Do Sparse Sets Have Dense Models”  Talk at the Pseudorandomness in MathematicsComputer Science Miniworkshop. Institute for Advanced Study, 2008  URL: https://www.ias.edu/sites/default/files/math/russell_scribe.pdf
  * [Imp09] Russell Impagliazzo  “Algorithmic Dense Model Theorems and Weak Regularity”  Unpublished manuscript, 2009  URL: https://simons-institute.github.io/pseudorandomness/pdfs/nov09.pdf
  * [Imp17] Russell Impagliazzo  “Learning Models of Mathematical Objects”  Workshop at the Simons Institute, lecture notes, 2017  URL: https://simons-institute.github.io/pseudorandomness/pdfs/modelnotes-by-holdenlee.pdf
  * [IMR14] Russell Impagliazzo, Cristopher Moore and Alexander Russell  “An Entropic Proof of Chang’s Inequality”  In _SIAM J. Discret. Math._ 28.1, 2014, pp. 173–176  DOI: 10.1137/120877982
  * [JP14] Dimitar Jetchev and Krzysztof Pietrzak  “How to Fake Auxiliary Input”  In _Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings_ 8349, Lecture Notes in Computer Science  Springer, 2014, pp. 566–590  DOI: 10.1007/978-3-642-54242-8\\_24
  * [Kea+18] Michael J. Kearns, Seth Neel, Aaron Roth and Zhiwei Steven Wu  “Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness”  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ 80, Proceedings of Machine Learning Research  PMLR, 2018, pp. 2569–2577  URL: http://proceedings.mlr.press/v80/kearns18a.html
  * [Kim+22] Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter and Omer Reingold  “Universal adaptability: Target-independent inference that competes with propensity scoring”  In _Proceedings of the National Academy of Sciences_ 119.4 National Academy of Sciences, 2022
  * [KGZ19] Michael P. Kim, Amirata Ghorbani and James Y. Zou  “Multiaccuracy: Black-Box Post-Processing for Fairness in Classification”  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, AIES 2019, Honolulu, HI, USA, January 27-28, 2019_ ACM, 2019, pp. 247–254  DOI: 10.1145/3306618.3314287
  * [KS03] Adam R. Klivans and Rocco A. Servedio  “Boosting and Hard-Core Set Construction”  In _Mach. Learn._ 51.3, 2003, pp. 217–238  DOI: 10.1023/A:1022949332276
  * [Lar+16] Jeff Larson, Surya Mattu, Lauren Kirchner and Julia Angwin  “How we analyzed the COMPAS recidivism algorithm”  In _ProPublica (5 2016)_ 9.1, 2016
  * [Noa+23] Georgy Noarov, Ramya Ramalingam, Aaron Roth and Stephan Xie  “High-Dimensional Prediction for Sequential Decision Making”  In _CoRR_ abs/2310.17651, 2023  DOI: 10.48550/ARXIV.2310.17651
  * [Rei+08] Omer Reingold, Luca Trevisan, Madhur Tulsiani and Salil P. Vadhan  “Dense Subsets of Pseudorandom Sets”  In _49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA_ IEEE Computer Society, 2008, pp. 76–85  DOI: 10.1109/FOCS.2008.38
  * [Sze78] Endre Szemerédi  “Regular partitions of graphs”  In _Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976)_ 260, Colloq. Internat. CNRS  CNRS, Paris, 1978, pp. 399–401
  * [TZ08] Terence Tao and Tamar Ziegler  “The primes contain arbitrarily long polynomial progressions”  In _Acta Math._ 201.2, 2008, pp. 213–305  DOI: 10.1007/s11511-008-0032-5
  * [TTV09] Luca Trevisan, Madhur Tulsiani and Salil P. Vadhan  “Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution”  In _Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009_ IEEE Computer Society, 2009, pp. 126–136  DOI: 10.1109/CCC.2009.41
  * [VZ12] Salil P. Vadhan and Colin Jia Zheng  “Characterizing pseudoentropy and simplifying pseudorandom generator constructions”  In _Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012_ ACM, 2012, pp. 817–836  DOI: 10.1145/2213977.2214051
  * [VZ13] Salil P. Vadhan and Colin Jia Zheng  “A Uniform Min-Max Theorem with Applications in Cryptography”  In _Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I_ 8042, Lecture Notes in Computer Science  Springer, 2013, pp. 93–110  DOI: 10.1007/978-3-642-40041-4\\_6
  * [Vin18] James Vincent  “Amazon reportedly scraps internal AI recruiting tool that was biased against women”  In _The Verge_ 10, 2018
  * [Yao82] Andrew Chi-Chih Yao  “Theory and Applications of Trapdoor Functions (Extended Abstract)”  In _23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982_ IEEE Computer Society, 1982, pp. 80–91  DOI: 10.1109/SFCS.1982.45
  * [Zhe14] Colin Jia Zheng  “A uniform min-max theorem and characterizations of computational randomness”, 2014  URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:11745716

##  Appendix A Multicalibrated Partitions

In this section, we provide the proof for Theorem 2.12.

######  Theorem A.1 (Theorem 2.12, MC Theorem [Héb+18]).

Let $\mathcal{X}$ be a finite domain, $\mathcal{F}$ a class of functions
$f\colon\mathcal{X}\rightarrow[0,1]$, $g\colon\mathcal{X}\rightarrow[0,1]$ an
arbitrary function, $\mathcal{D}$ a probability distribution over
$\mathcal{X}$, and $\epsilon,\gamma>0$. There exists an
$(\mathcal{F},\epsilon,\gamma)$-approximately multicalibrated partition
$\mathcal{P}$ of $\mathcal{X}$ for $g$ on $\mathcal{D}$ such that
$\mathcal{P}\in\mathcal{F}_{t,q,k}$, where

  * 1.

$t=O(1/(\epsilon^{4}\gamma)\cdot\log(|\mathcal{X}|/\epsilon))$,

  * 2.

$q=k=O(1/\epsilon)$.

The goal is to build an approximate MC predictor $h$ that only has
$k=O(1/\epsilon)$ level sets; the parameters $t$ and $q$ are given by the
Hébert-Johnson et al. MC algorithm. From this predictor, we then obtain an MC
partition as stated in Theorem 2.12 by taking the partition induced by the
level sets of the predictor.

The intuitive idea behind why we can obtain an MC predictor $h$ with
$O(1/\epsilon)$ level sets is to discretize the domain $[0,1]$ into “buckets”
of width $\gamma$ and then round the values of $h$ to the closest point in the
discretization. After the rounding, $h$ has at most $1/\lambda$ level sets,
yet the rounding can only have changed each output of $h$ by at most
$\lambda$. Therefore, the MC property of $h$ is maintained after the rounding
(up to an additive factor of $\lambda$).

However, it is not enough to apply this procedure to an approximate
$\gamma$-MC predictor, given that we want the predictor to have
$k=O(1/\epsilon)$ level sets _independent of $\gamma$._ To do so, we use in
the proof a different relaxation of the notion of multicalibration which we
mentioned in the introduction; namely, _multicalibration on average (MCoA)_.
In the case of MCoA, there is no parameter $\gamma$; instead, in order to deal
with the small level sets, the MC condition is only required to hold on
average over the level sets:

######  Definition A.2.

Let $\mathcal{X}$ be a finite domain, $\mathcal{F}$ a collection of functions
$f\colon\mathcal{X}\rightarrow[0,1]$, $g\colon\mathcal{X}\rightarrow[0,1]$ an
arbitrary function, $\mathcal{D}$ a probability distribution over
$\mathcal{X}$, and $\epsilon>0$. We say that a predictor
$h\colon\mathcal{X}\rightarrow[0,1]$ is _$(\mathcal{F},\epsilon)$
-multicalibrated on average_ (MCoA) for $g$ on $\mathcal{D}$ if, for all
$f\in\mathcal{F}$,

$\mathop{\mathbb{E}}_{X_{v}\sim\mathcal{P}(\mathcal{D})}\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{D}|_{v}}[f(x)\cdot(g(x)-h(x))]\Big{|}\leq\epsilon,$

where $\mathcal{D}|_{v}$ denotes the conditional distribution
$\mathcal{D}|_{h(x)=v}$ for $v\in[0,1]$ in the image of $h$, and
$\mathcal{P}(\mathcal{D})$ denotes the distribution that selects each $X_{v}$
with probability $\big{(}\sum_{x\in
X_{v}}\mathcal{D}(x)\big{)}/\big{(}\sum_{x\in\mathcal{X}}\mathcal{D}(x)\big{)}$.

Then, when we consider a fixed level set $X_{v}=\\{x\in\mathcal{X}\mid
h(x)=v\\}$, it follows that

$\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{D}|_{v}}[f(x)\cdot(g(x)-h(x))]\Big{|}\leq\dfrac{\epsilon}{\Pr_{\mathcal{D}}[x\in
X_{v}]}.$

Therefore, in the case of MCoA, we allow the indistinguishability parameter to
degrade with the size of the level set (the smaller $X_{v}$, the worse the
guarantee becomes), but if we re-parametrize this second approach by setting
$\epsilon\leftarrow\epsilon\gamma$, we obtain exactly the definition of
approximate MC, given that

$\Big{|}\mathop{\mathbb{E}}_{x\in
X_{v}}[f(x)\cdot(g(x)-h(x))]\Big{|}\leq\epsilon\cdot\gamma\cdot\dfrac{|\mathcal{X}|}{|X_{v}|}\leq\epsilon\cdot\dfrac{|X_{v}|}{|\mathcal{X}|}\cdot\dfrac{|\mathcal{X}|}{|X_{v}|}=\epsilon.$

Similar to how we have an approximate MC theorem, the notion of MCoA is
likewise efficiently realizable.

Next, we formally introduce the discretization of the domain:

######  Definition A.3 ($\lambda$-discretization).

Let $0<\lambda<1$. The _$\lambda$ -discretization_ of $[0,1]$ is the set

$\Lambda[0,1]=\Big{\\{}0,\frac{\lambda}{2},\frac{3\lambda}{2},\frac{5\lambda}{2},\ldots,\frac{n\lambda}{2},1\Big{\\}},$

where $n$ is the largest odd integer smaller than $2/\lambda$.

Given a $\lambda$-discretization, we show that the number of level sets of an
MCoA predictor $h$ can be bounded by $O(1/\lambda)$:

######  Claim A.4.

Let $\mathcal{X}$ be a finite domain, let $\mathcal{F}$ be a family of
functions $f\colon\mathcal{X}\rightarrow[0,1]$, let
$g\colon\mathcal{X}\rightarrow[0,1]$ be an arbitrary function, and let
$\epsilon,\lambda\in(0,1)$. If $h$ is an $(\mathcal{F},\epsilon)$-MCoA
predictor for $g$, then there exists an
$(\mathcal{F},\epsilon+\lambda/2)$-MCoA predictor $h^{\prime}$ for $g$ such
that $h^{\prime}$ has $O(1/\lambda)$ level sets.

###### Proof.

We define $h^{\prime}$ as follows: for each $x\in\mathcal{X}$, the value
$h^{\prime}(x)$ is equal to $\textrm{Round}(h(x))$, where the function
$\textrm{Round}\colon[0,1]\rightarrow\Lambda[0,1]$ maps $h(x)$ to the closest
value in $\Lambda[0,1]$ (rounding up in the case of ties). By definition of
$\lambda$-discretization, this implies that
$|h(x)-h^{\prime}(x)|\leq\lambda/2$. If we denote
$X^{\prime}_{w}=\\{x\in\mathcal{X}\mid h^{\prime}(x)=w\\}$ for each $w\in{\rm
image}(h^{\prime})$, then $X^{\prime}_{w}=\cup_{v}\,X_{v}$, where
$w-\frac{\lambda}{2}\leq v\leq w+\frac{\lambda}{2}$ with $v\in{\rm image}(h)$.
For each $w\in{\rm image}(h^{\prime})$, we have

$\displaystyle\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{D}|_{w}}[f(x)\cdot(g(x)-h^{\prime}(x)]\Big{|}$
$\displaystyle\leq\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{D}|_{w}}[f(x)\cdot(g(x)-h(x)]\Big{|}+\mathop{\mathbb{E}}_{x\sim\mathcal{D}|_{w}}\Big{[}f(x)\cdot|h(x)-h^{\prime}(x)|\Big{]}$
$\displaystyle\leq\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{D}|_{w}}[f(x)\cdot(g(x)-h(x)]\Big{|}+\lambda/2,$

where $\mathcal{D}|_{w}$ denotes $\mathcal{D}|_{h^{\prime}(x)=w}$ in this
case. Moreover, if we denote by $\mathcal{P}^{\prime}(\mathcal{D})$ the
distribution that selects $X^{\prime}_{w}$ for $w\in{\rm image}(h^{\prime})$
and we denote by $\mathcal{P}(\mathcal{D}|_{w})$ the one that selects $X_{v}$
for $v\in{\rm image}(h)$ with $w-\frac{\lambda}{2}\leq v\leq
w+\frac{\lambda}{2}$, then

$\displaystyle\mathop{\mathbb{E}}_{X_{w}^{\prime}\sim\mathcal{P}^{\prime}(\mathcal{D})}\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{D}|_{w}}[f(x)$
$\displaystyle\cdot(g(x)-h(x)]\Big{|}=\mathop{\mathbb{E}}_{X_{w}^{\prime}\sim\mathcal{P}^{\prime}(\mathcal{D})}\Big{|}\mathop{\mathbb{E}}_{X_{v}\sim\mathcal{P}(\mathcal{D}|_{w})}\;\mathop{\mathbb{E}}_{x\sim\mathcal{D}|_{v}}[f(x)\cdot(g(x)-h(x)]\Big{|}$
$\displaystyle\leq\mathop{\mathbb{E}}_{X_{w}^{\prime}\sim\mathcal{P}^{\prime}(\mathcal{D})}\;\mathop{\mathbb{E}}_{X_{v}\sim\mathcal{P}(\mathcal{D}|_{w})}\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{D}|_{v}}[f(x)\cdot(g(x)-h(x)]\Big{|}$
$\displaystyle=\mathop{\mathbb{E}}_{X_{v}\in\mathcal{P}(\mathcal{D})}\Big{|}\mathop{\mathbb{E}}_{x\sim\mathcal{D}|_{v}}[f(x)\cdot(g(x)-h(x)]\Big{|}\leq\epsilon.$

Therefore, $h^{\prime}$ is $(\mathcal{F},\epsilon+\lambda/2)$-multicalibrated
on average. ∎

Now that we know how to construct an MCoA predictor with $O(1/\lambda)$ level
sets, we show how to build an approximate MC predictor with $O(1/\epsilon)$
(as required in Theorem 2.12).

######  Claim A.5.

Let $\mathcal{X}$ be a finite domain, $\mathcal{F}$ a family of functions
$f:\mathcal{X}\rightarrow[0,1]$, $g:\mathcal{X}\rightarrow[0,1]$ an arbitrary
function, and $\epsilon,\gamma\in(0,1)$. There exists a
$(\mathcal{F},\epsilon,\gamma)$-approximate MC predictor $h$ for $g$ such that
$h$ has $O(1/\epsilon)$ level sets.

###### Proof.

Given $\epsilon,\gamma$, we define $\epsilon^{\prime}$ and the discretization
parameter $\lambda$ as follows:

$\epsilon^{\prime}=\dfrac{\epsilon\gamma}{2},\quad\lambda=\dfrac{\epsilon}{2}.$

We build an MCoA predictor $h$ with parameter $\epsilon^{\prime}$ using the
MCoA algorithms from the multicalibration literature [Gop+22, GKR23]. Next, we
use the $\lambda$-discretization to transform this MCoA predictor $h$ into an
approximate MC predictor $h^{\prime}$ by merging the values of $h$ so that
they only take values in $\Lambda[0,1]$ for $\lambda=\epsilon/2$. By the re-
parametrization above, this gives an approximate MC predictor with
$O(1/\epsilon)$ level sets. ∎

We can now prove Theorem 2.12:

###### Proof of Theorem 2.12.

We begin by applying Claim A.5 to obtain an
$(\mathcal{F},\epsilon,\gamma)$-approximate MC predictor $h$ that has
$O(1/\epsilon)$ level sets. By the MC theorem given by Hébert-Johnson et al.,
$h\in\mathcal{F}_{t,q}$, where
$t=O(1/(\epsilon^{4}\gamma)\cdot\log(|\mathcal{X}|/\epsilon))$ and
$q=O(1/\epsilon)$ [Héb+18]. We remark that each iterations in the [Héb+18]
algorithm requires a scalar multiplication, a finite-precision addition, and
projection onto $[0,1]$, which can be handled by
$O(\log(1/\epsilon)+\log(1/|\mathcal{X}|))$ gates. The $\log(1/\epsilon)$ term
corresponds to the fact that we perform computations up to a fixed precision
of $\Theta(\epsilon)$, and the $\log(1/|\mathcal{X}|)$ term corresponds to
bitlength of the elements in $\mathcal{X}$, given that each $x\in\mathcal{X}$
requires $\log(1/|\mathcal{X}|)$ bits to represent. For full details on the
circuit implementation, see [Dwo+21, §5]. The partition $\mathcal{P}$ stated
in Theorem 2.12 is then given by the collection of level sets of this
approximate MC predictor $h$. ∎

##  Appendix B From Hardcore Distributions to Hardcore Sets

######  Lemma B.1 (From distributions to sets [KS03, Lemma 24]).

Let $\mathcal{X}=\\{0,1\\}^{n}$, $g\colon\mathcal{X}\rightarrow\\{0,1\\}$ an
arbitrary function, $\epsilon,\delta>0$, such that $\delta\geq
1/|\mathcal{X}|^{1/2}$, and $\mathcal{F}$ a class of functions $f\colon
X\rightarrow\\{0,1\\}$ such that
$\log(|\mathcal{F}|)\leq|\mathcal{X}|\epsilon^{2}\delta^{2}$. Suppose that
$\mu$ is an $(\mathcal{F},\epsilon)$-hardcore distribution for $g$ such that
$d(\mu)\geq\delta$. Then there exists a set $H$ with
$|H|\geq\delta\cdot|\mathcal{X}|$ such that $H$ is an
$(\mathcal{F},4\epsilon)$-hardcore set for $g$.

###### Proof.

Given the distribution $\mu$, we construct the claimed set $H$ as follows: for
each $x\in\mathcal{X}=\\{0,1\\}^{n}$, include $x$ to $H$ with probability
$\mu(x)$. This is a non-constructive set $H$, but we are still able to argue
about its density. We denote the characteristic function of $H$ by $\chi_{H}$.

Let $f\in\mathcal{F}$ and let $t(x)$ be an arbitrary function. We now use the
following fact, where without loss of generality we view functions $f$ and $t$
as taking values in $\\{-1,1\\}$:

######  Lemma B.2.

Let $\rho>0$. Then,

$\Pr_{\mathcal{D}_{\mu}}[f(x)=t(x)]=\dfrac{1}{2}+\rho\iff\sum_{x\in\\{0,1\\}^{n}}\mu(x)f(x)t(x)=2\rho|\mu|,$

where $\mathcal{D}_{\mu}$ denotes the probability distribution induced by
$\mu$ and $|\mu|=\sum_{x\in\mathcal{X}}\mu(x)$.

This is a direct consequence from the definition of $|\mu|$. Next, by the
definition of $\chi_{H}$, it follows that

$\mathop{\mathbb{E}}_{x\sim H}[\chi_{H}(x)]=\mu(x).$

By linearity of expectation, it follows that

$\mathop{\mathbb{E}}_{x\sim
H}\Big{[}\sum_{x\in\mathcal{X}}\chi_{H}(x)f(x)g(x)\Big{]}=\sum_{x\in\mathcal{X}}\mu(x)f(x)g(x).$

Then, by applying Lemma B.2 with $t:=g$, it follows that

$\sum_{x\in\mathcal{X}}\mu(x)f(x)g(x)\leq 2\epsilon|\mu|,$

since by assumption $\mu$ is an $(\mathcal{F}_{t},\epsilon)$-hardcore
distribution for $g$. By definition, $\Pr_{x\sim
D_{\mu}}[f(x)=g(x)]\leq\epsilon$, and hence the parameter $\rho$ in Lemma B.2
corresponds to $\epsilon$.

Next, we use Hoeffding’s inequality:

######  Claim B.3 (Hoeffding’s tail bound).

Let $X_{1},\ldots,X_{N}$ be independent random variables with $X_{i}\in[a,b]$
for all $i$. Then, for all $t\geq 0$,

$\Pr\Big{[}\frac{1}{n}\sum_{i=1}^{n}\left(X_{i}-\mathop{\mathbb{E}}[X_{i}]\right)\geq
t\Big{]}\leq\exp\Big{(}\dfrac{-2nt^{2}}{(b-a)^{2}}\Big{)}.$

In our case, for each value of $x\in\mathcal{X}$ the quantity
$X_{x}:=\chi_{H}(x)f(x)g(x)$ is a random variable in the interval $[-1,1]$.
Hence, each of these random variables corresponds to one $X_{i}$ in
Hoeffding’s bound. We just showed that

$\mathop{\mathbb{E}}_{x\sim\mathcal{X}}\Big{[}\sum_{x}\chi_{H}(x)f(x)g(x)\Big{]}\leq
2\epsilon|\mu|=2\epsilon\cdot|\mathcal{X}|\cdot d(\mu),$

since by definition of density of a distribution we know that

$d(\mu)=\dfrac{|\mu|}{|\mathcal{X}|}.$

Set $t:=2\epsilon d(\mu)$. Since $X_{x}\in[-1,1]$ for all $x\in\mathcal{X}$,
it follows that $(b-a)^{2}=4$. Then, by Hoeffding’s tail bound it follows that

$\Pr\Big{[}\dfrac{1}{|\mathcal{X}|}\sum_{x}X_{x}\geq 4\epsilon
d(\mu)\Big{]}\leq\exp\Big{(}\dfrac{-2\cdot|\mathcal{X}|(2\epsilon
d(\mu))^{2}}{4}\Big{)}.$

Since by assumption $d(\mu)\geq\delta$, it follows that the above probability
is less than $\exp(-2\cdot|\mathcal{X}|\cdot\epsilon^{2}\delta^{2})$. Since by
assumption $|\mathcal{F}|\leq
2^{|\mathcal{X}|\cdot\epsilon^{2}\cdot\delta^{2}}\ll\frac{1}{10}\exp(2\cdot|\mathcal{X}|\cdot\epsilon^{2}\delta^{2})$,
and hence by the the union bound this implies that the probability that there
exists some $f\in\mathcal{F}$ such that $\sum_{x}\chi_{H}(x)f(x)g(x)\geq
4\epsilon|\mu|$ is less than $1/10$.

Next, applying the Hoeffding bound to $|H|$ (which is a sum of $|\mathcal{X}|$
independent random variables), by similar calculations and using the
assumptions that $d(\mu)\geq\delta$ and $\delta\geq 1/|\mathcal{X}|^{1/2}$, it
follows that $|H|\geq 2\delta\cdot|\mathcal{X}|$.

Lastly, putting everything together, we conclude that there exists some set
$H$ such that

$\displaystyle(1)\quad|H|\geq\delta\cdot|\mathcal{X}|,$
$\displaystyle(2)\quad\sum_{x}\chi_{H}(x)f(x)g(x)\leq 4\epsilon|\mu|\leq
8\delta|H|=8\epsilon|\chi_{H}|.$

Using Lemma B.2 with $t:=g$ and $\rho:=4\epsilon$ we thus obtain that

$\Pr_{x\sim H}[f(x)=g(x)]\leq\dfrac{1}{2}+4\epsilon$

for all $f\in\mathcal{F}$. Hence, $H$ is an ($\mathcal{F},4\epsilon)$-hardcore
set for $g$, as we wanted to show. ∎

For further details, we defer to reader to Section 6 in [Imp95], Section 2.1.1
in [Hol05], or Section 4.4 in [KS03].

##  Appendix C Generalizing the IHCL statement from [Rei+08]

As summarized in Section 3.5, we claim that we can remove the assumption that
$g$ is $\delta$-hard in the IHCL statement shown by Reingold, Trevisan,
Tulsiani, and Vadhan ([Rei+08, Thm. 3.2]). More specifically, Theorem 3.2 in
[Rei+08] gives a partition $\mathcal{P}$ of $\mathcal{X}$ of complexity
$\exp(\mathrm{poly}(1/\epsilon,1/\tau))$ such that _either_ :

  1. 1.

$\bigcup_{P\in\mathcal{P}}P^{\mathrm{min}}\leq\tau\cdot|\mathcal{X}|$, or

  2. 2.

For every $f\in\mathcal{F}$,

$\mathop{\mathbb{E}}_{P\in D_{\min}}\big{[}|\Pr_{x\in
P^{\mathrm{maj}}}[f(x)=1]-\Pr_{x\in P^{\mathrm{min}}}[f(x)=1]|\big{]},$

where $D_{\min}$ is the distribution that selects $P\in\mathcal{P}$ with
probability proportional to $|P^{\min}|$.

Indeed, if Condition (1) does not hold, then there is a distinguisher that can
compute $g$ on more than a $1-\tau$ fraction of inputs. On the other hand, in
the energy potential argument given in [Rei+08], Condition (2) can only hold
if $\sum_{P}|P^{\mathrm{min}}|/|\mathcal{X}|\geq\tau$, which contradicts
Condition (1). Moreover, we remark that Condition (1) is analogous to our
condition that we cannot make guarantees about the pieces $P\in\mathcal{P}$
such that the balance parameter $b_{P}$ or the size parameter $\eta_{P}$ are
too small (indeed, the indistinguishability parameter in our IHCL$++$ degrades
with $b_{P}$, and by the approximate MC theorem we only consider the pieces
that satisfy $\eta_{P}\geq\gamma$), given that it implies that
$b_{P}\cdot\eta_{P}\leq\tau$ for all $P\in\mathcal{P}$ when $\mathcal{D}$ is
the uniform distribution. Indeed, we claim that Condition (1) implies that

$b_{P}\cdot\eta_{P}\leq\dfrac{\big{|}\bigcup_{P\in\mathcal{P}}P^{\mathrm{min}}\big{|}}{|\mathcal{X}|},$

which, by our definitions of $b_{P}$ and $\eta_{P}$, is equivalent to

$\min\\{\mathop{\mathbb{E}}_{P}[g(x)],1-\mathop{\mathbb{E}}_{P}[g(x)]\\}\cdot\dfrac{|P|}{|\mathcal{X}|}\leq\dfrac{\big{|}\bigcup_{P\in\mathcal{P}}P^{\mathrm{min}}\big{|}}{|\mathcal{X}|}.$

If $b_{P}\leq 1/2$, then the minority element in $P$ is 1 and
$\mathop{\mathbb{E}}_{P}[g(x)]\leq|\\{x\in P\mid g(x)=1\\}|/|P|$. Hence, the
inequality simplifies to
$|P^{\mathrm{min}}|\leq\big{|}\cup_{P\in\mathcal{P}}P^{\mathrm{min}}\big{|}$,
which is clearly true. If $b_{P}>1/2$, then the minority element in $P$ is 1
and and $\mathop{\mathbb{E}}_{P}[g(x)]\leq|\\{x\in P\mid g(x)=0\\}|/|P|$, so
the expression again simplifies to
$|P^{\mathrm{min}}|\leq\big{|}\cup_{P\in\mathcal{P}}P^{\mathrm{min}}\big{|}$.

Lastly, we show that Reingold’s et al. Theorem 3.2 modified as above to hold
for an arbitrary function $g$ implies the original IHCL. Hence, we bring back
the assumption that $g$ is $(\mathcal{F},\delta)$-weakly hard for
$s=\mathrm{poly}(1/\epsilon,1/\delta)$ and $\delta>\tau$. This implies that
$\cup_{P\in\mathcal{P}}P^{\mathrm{min}}\geq\delta\cdot|\mathcal{X}|$, because
otherwise this would contradict the assumption that $g$ is $\delta$-weakly
hard. Thus, Condition (1) does not hold, and by our modified version of
Reingold et al.’s Theorem 3.2, this implies that Condition (2) must hold,
which yields a hardcore distribution $D_{\min}$.


# On the maximum volume of collapsing structures

Jan J. Ostrowski 11footnotetext: Corresponding author. Ismael Delgado
Gaspar,22footnotetext: Corresponding author.

###### Abstract

In many cosmological models, including the $\Lambda$CDM concordance model,
there exist theoretical upper bounds on the size of collapsing structures. The
most common formulations in the literature refer to a turnaround radius in
spherical symmetry or a turnaround surface, defined as the zero-expansion
boundary separating the outer Hubble flow from the inner flow of a collapsing
fluid. In order to access a generic scenario, we propose an improvement of
this cosmological test in terms of the maximum volume of the cosmological
structures, which is equivalent to a zero-averaged expansion – instead of the
zero-local expansion. By combining the Lagrangian perturbations method and the
scalar averaging of Einstein’s equations, we obtain a maximum volume for a
collapse model without any restricting symmetries. We compare this result with
some exact, inhomogeneous solutions and discuss further potential
developments.

##  1 Introduction

Cosmological large-scale structures can, in principle, provide robust tests of
cosmological models. Due to the structures’ morphological and dynamical
complexity, such tests are required to cover a broad set of initial conditions
and dynamical scenarios. In this context, the whole branch of standard tests
considers the statistical properties of the density field, e.g. [15], [19],
[14], [4].

There exists, however, another complementary approach that does not aim at
determining the parameters of any given cosmological model but sets certain
bounds on observables and thus may be used to falsify or undermine a concrete
theory (see, e.g. [25], [10]). One of such tests is based on the turnaround
surface, i.e., the sphere of zero-expansion surrounding a collapsing structure
marking the surface where the Hubble expansion and the gravitational
attraction of the structure cancel each other out. However, this formulation
is a bit unfortunate as it suggests that there are two competing physical
processes: expansion and contraction, while according to general relativity,
both are just manifestations of the evolution of the spatial metric (from the
practical point of view, especially in the perturbation theory context, it is
sometimes helpful to introduce this artificial division into the background
and peculiar motion, keeping in mind that there is nothing fundamental behind
this distinction). This method was proposed, e.g., in [36], where authors
derive an upper limit on the radius of the zero-expansion sphere, i.e., its
maximum value, at the epoch of decoupling from the Hubble flow, that can be
regarded as a maximum value obtainable by any spherically symmetric structure
in the $\Lambda$CDM model.

In [36], three different methods are presented to derive the maximum
turnaround radius

$R_{max}=\left(\frac{3GM}{\Lambda}\right)^{1/3}\;,$ (1.1)

in the $\Lambda$CDM model (setting the speed of light to one). These methods
include using the geodesic equations in the Einstein-de Sitter space-time, the
standard perturbation theory, and the non-linear evolution of an over-
densities described by the Friedmann equations. All of the above methods treat
a spherical, homogeneous over-densities and thus are very restricted. Some
authors generalized this approach using the quasi-spherical models or the
standard perturbation theory [21], [11]. A possible violation of the (1.1)
bound was reported in [29]. However, as pointed out in [24], determination of
the zero-expansion surface can be observationally cumbersome and prone to
errors; thus, another similar test based on a different principle has the
potential to become very useful.

In this paper, we present a substantial improvement and modification of the
zero-expansion surface idea by extending the domain of applicability to the
non-spherical collapse. In the mean time, we define a different condition for
the turnaround. Namely, the maximum volume that the structure can attain
depending on the cosmological mode With this improvement, we are able to
derive an upper bound for a generic collapse scenario. The main motivations
for the use of a maximum volume method follows from two facts: (i) it
considerably simplifies the averaged Hamiltonian constraint due to the
corresponding zero-averaged expansion, (ii) it is, in principle, detectable.
We present this feature with examples, including the relativistic Zel’dovich
approximation (RZA) and some exact relativistic solutions.

This article is organized as follows. First, in Sec. 2, we introduce the
mathematical tools and concepts necessary to develop our approach, i.e., the
scalar averaging of Einstein’s equations and the relativistic Zel’dovich
approximation. The following section, Sec. 3, is dedicated to the derivation
of our main result, the maximum (zero-averaged expansion) volume of the cosmic
structure as a function of redshift, mass, and the background cosmology,
supplemented with some numerical solutions. Our results are discussed in Sec.
4, where we also look at some illustrative exact cases. Section 5 concludes
the paper with some final remarks and an outlook for future research.

##  2 Spatially averaged Einstein’s equations and the relativistic Zel’dovich
approximation

In the context of extended objects in general relativity, such as cosmological
structures, it is advantageous to utilize the scalar averaging scheme (see
e.g., [6]). This formalism takes the scalar parts of Einstein’s equations in
$3+1$ form and applies to them a spatial averaging operator. Since the spatial
averaging and time evolution do not commute, the resulting equations exhibit
an additional term, the backreaction. There has been a considerable debate on
the nature of backreaction in general relativity, see e.g. [13] and [23]. In
the context of this paper, however, the use of averaged equations seems to be
non-controversial as it is a part of the standard cosmological paradigm that
the global behaviour of the Universe is treated relativistically, while the
structures obey the laws of Newtonian physics. More specifically, in both
relativistic and Newtonian cases, the governing averaged equations are similar
apart from being subjected to different interpretations, e.g., in the general
relativistic context we use the extrinsic curvature tensor, while in the
Newtonian case we speak about the velocity gradient. In the following we will
use the relativistic equations; however, the main result of this paper remains
unaffected by this choice.

We continue this section by recalling the basic structure of scalar averaging.
Within the fluid-orthogonal foliation of space-time, we can define the spatial
averages of the scalar parts of Einstein’s equations with irrotational dust
chosen as the source. We define the averaging operator over a compact spatial
domain ${\cal D}$ as:

$\left\langle{\cal A}\right\rangle_{\cal D}=\frac{1}{V_{{\cal D}}}\int_{{\cal
D}}\,{\rm d}\mu\ {\cal A}\ \;,\,V_{{\cal D}}=\int_{{\cal D}}\,{\rm d}\mu\ \;,$
(2.1)

where ${\rm d}\mu$ is the Riemannian volume element.

The Friedmann equations of the Friedmann-Lemaître-Robertson-Walker (FLRW)
model find their generalization in an inhomogeneous model through the volume
expansion and acceleration equations [6]. We define the domain-dependent scale
factor as

$a_{{\cal D}}=\left(V_{{\cal D}}/V_{{\cal D}_{i}}\right)^{\frac{1}{3}}\ ;\quad
V_{{\cal D}_{i}}=V_{{\cal D}}(t_{i})\ .$ (2.2)

The spatially averaged energy constraint (the Hamiltonian constraint), the
Raychaudhuri’s equation, and mass conservation form a set of exact equations
which include the extrinsic curvature invariants collected in the backreaction
term:

$\displaystyle 3\left(\frac{\dot{a}_{\cal D}}{a_{\cal
D}}\right)^{2}=\Lambda+8\pi\left\langle\varrho\right\rangle_{\cal
D}-\frac{1}{2}\left\langle{}^{(3)}{\cal{R}}\right\rangle_{\cal
D}-\frac{1}{2}{\cal Q}_{{\cal D}}\ ;\qquad$ (2.3a) $\displaystyle
3\frac{\ddot{a}_{\cal D}}{a_{\cal
D}}=\Lambda-4\pi\left\langle\varrho\right\rangle_{\cal D}+{\cal Q}_{{\cal D}}\
;\qquad$ (2.3b)
$\displaystyle\left\langle\varrho\right\rangle^{\hbox{\bigastfont.}}_{\cal
D}=-3\frac{\dot{a}_{\cal D}}{a_{\cal D}}\left\langle\varrho\right\rangle_{\cal
D}\ ,\qquad$ (2.3c)

where the kinematical backreaction term reads:

${\cal Q}_{{\cal D}}\equiv 2\left\langle{\rm II}\right\rangle_{\cal
D}-\frac{2}{3}\left\langle{\rm I}\right\rangle_{\cal D}^{2}\ .$ (2.4)

$\left\langle{\rm I}\right\rangle_{\cal D}$ and $\left\langle{\rm
II}\right\rangle_{\cal D}$ are the averaged principal invariants of (minus)
the extrinsic curvature tensor, the expansion tensor $\Theta_{ij}$:

$\Theta_{ij}=\frac{1}{2}\dot{g}_{ij}\;,\;{\rm
I}=\mathrm{tr}\left(\Theta_{ij}\right)\;,\;{\rm
II}=\frac{1}{2}\left(\mathrm{tr}\left(\Theta_{ij}\right)^{2}-\mathrm{tr}\left(\left(\Theta_{ij}\right)^{2}\right)\right)\;,$
(2.5)

and $\left\langle{}^{(3)}{\cal{R}}\right\rangle_{\cal D}$ is the averaged
scalar curvature. This system of equations is undetermined. In the series of
papers [9, 8, 3, 2], the authors propose a closure condition derived from the
relativistic version of the Zel’dovich approximation. The main idea consists
of expressing the $3+1$ Einstein’s equations using only one tensorial
variable, the co-frame, and postulating its particular form as a perturbation
with respect to the background. No further linearization is performed, i.e.,
the perturbed co-frame is used to evaluate all the relevant fields without
truncating the higher order terms in functionals of the co-frames. This line
of reasoning leads to the closure condition of the averaged equations with the
backreaction term reading:

${\cal Q}_{{\cal D}}\equiv 2\left\langle{\rm II}\right\rangle_{\cal
D}-\frac{2}{3}\left\langle{\rm I}\right\rangle_{\cal
D}^{2}=\frac{\left\langle\ddot{{\mathfrak{J}}}\right\rangle_{{\cal
I}}}{\left\langle{\mathfrak{J}}\right\rangle_{{\cal
I}}}-\frac{\ddot{\xi}}{\dot{\xi}}\frac{\left\langle\dot{{\mathfrak{J}}}\right\rangle_{{\cal
I}}}{\left\langle{\mathfrak{J}}\right\rangle_{{\cal
I}}}-\frac{2}{3}\left(\frac{\left\langle\dot{{\mathfrak{J}}}\right\rangle_{{\cal
I}}}{\left\langle{\mathfrak{J}}\right\rangle_{{\cal I}}}\right)^{2}\ .$ (2.6)

In the above equation, ${\mathfrak{J}}$ is the peculiar-volume deformation:

${\mathfrak{J}}=1+\xi(t){\rm I}_{i}+\xi^{2}(t){\rm II}_{i}+\xi^{3}(t){\rm
III}_{i}\;,$ (2.7)

with the initial values of invariants (2.5) (subscript $i$), the third
invariant reading: ${\rm III}=\mathrm{det}\left(\Theta_{ij}\right)$, and
$\xi\left(t\right)$ being the background-dependent growth function defined by

$\xi(t):=[q(t)-q({t_{\rm\bf i}})]/{\dot{q}({t_{\rm\bf i}})}\ ,$ (2.8)

where $q(t)$ obeys

$\ddot{q}(t)+2H\dot{q}(t)-4\pi\varrho_{H}q(t)=0\ ,$ (2.9)

i.e., the same equation that leads to the growing and decaying modes in the
linear cosmological perturbation theory. In 2.6 we used the formal average
operator:

$\left\langle{\cal A}\right\rangle_{{\cal I}}=\frac{1}{V_{{{\cal D}_{\rm\bf
i}}}}\int_{{\cal D}}\,{\rm d}^{3}X\ {\cal A}\ ,$ (2.10)

where $X$ stands for the Lagrangian coordinates (see [8] for details). With
this definition, the volume Hubble expansion rate can be expressed as follows

$H_{\cal D}=\frac{\dot{a}_{\cal D}}{a_{\cal
D}}=H+\frac{1}{3}\frac{\left\langle\dot{\mathfrak{J}}\right\rangle_{{\cal
I}}}{\left\langle\mathfrak{J}\right\rangle_{{\cal I}}}\ .$ (2.11)

A similar relationship can be found for $\ddot{a}_{\cal D}/a_{\cal D}$:

$\frac{\ddot{a}_{\cal D}}{a_{\cal D}}+2H_{\cal
D}^{2}=\frac{\ddot{a}}{a}+2H^{2}+2H\frac{\left\langle\dot{\mathfrak{J}}\right\rangle_{{\cal
I}}}{\left\langle\mathfrak{J}\right\rangle_{{\cal
I}}}+\frac{1}{3}\frac{\left\langle\ddot{\mathfrak{J}}\right\rangle_{{\cal
I}}}{\left\langle\mathfrak{J}\right\rangle_{{\cal I}}}\ .$ (2.12)

In the following section we will use the tools briefly sketched here to
develop a general expression for the turnaround volume.

##  3 Turnaround condition

In the case of realistic structures, it is not always easy to define the
turnaround epoch since, in inhomogeneous spacetimes, each fluid element
follows different type of evolution and decouples from the Hubble flow at
different times. This problem is absent in the simplified homogeneous case
where the turnaround is synchronous. Throughout this paper we will use the
definition proposed in [41] based on the vanishing of the average Hubble
expansion:

$\mbox{Turnaround:}\qquad 3H_{\cal D}=\left\langle\Theta\right\rangle_{\cal
D}=\frac{\dot{V}_{{\cal D}}}{V_{{\cal D}}}=0\implies\dot{V}_{{\cal D}}=0\ .$
(3.1)

This criterion constitutes the most direct generalization of the zero
expansion surface. The standard representation of a homogenous dust ball
reaching a maximum radius (volume) and then recollapsing is recast in terms of
the averaged fields. In our case, the turnaround is marked by the time when
the volume ($\dot{V}_{\cal D}=0$) or the characteristic scale of the
configuration ($\ell\sim V^{1/3}$) reach their maximum.

Our definition of the turnaround is general and can be used in scenarios where
RZA is no longer applicable, e.g., in the case of exact cosmological solutions
that do not admit a clear distinction between the background and peculiar
fields. In fact, this kind of study offers an important insights into the
large-scale structure formation in the non-linear regime. In Sec. 4.1.2, we
will discuss two illustrative toy models based on Szekeres solutions; in this
section we will solely focus on the RZA approach.

The turnaround condition, Eq. (3.1), and equations (2.11), (2.12), and (2.4)
lead to

$\displaystyle\frac{\left\langle\dot{\mathfrak{J}}\right\rangle_{{\cal
I}}}{\left\langle\mathfrak{J}\right\rangle_{{\cal I}}}=-3H\ ,$ (3.2a)
$\displaystyle\frac{\ddot{a}_{\cal D}}{a_{\cal
D}}=-\frac{9}{2}H^{2}+\frac{\Lambda}{2}-\frac{k}{2a^{2}}+\frac{1}{3}\frac{\left\langle\ddot{\mathfrak{J}}\right\rangle_{{\cal
I}}}{\left\langle{\mathfrak{J}}\right\rangle_{{\cal I}}}\ ,$ (3.2b)
$\displaystyle{\cal Q}_{{\cal
D}}=\frac{\left\langle\ddot{{\mathfrak{J}}}\right\rangle_{{\cal
I}}}{\left\langle{\mathfrak{J}}\right\rangle_{{\cal
I}}}+3H\frac{\ddot{\xi}}{\dot{\xi}}-6H^{2}\ .$ (3.2c)

To relate the average and the background densities (at the turnaround), we
first insert (3.2) into (2.3b); then, considering only the growing solution to
$q$, we obtain

$\frac{\left\langle\varrho\right\rangle_{\cal
D}}{\varrho_{H}}=1+3\left[H\bigg{/}\left(\frac{\dot{q}}{q}\right)\right]\
,\quad\mbox{with}\quad q\simeq
q_{+}\propto\frac{\dot{a}}{a}\int_{0}^{a}\dot{\hat{a}}^{-3}{\hbox{d}}\hat{a}\
,$ (3.3)

which for an EdS model (i.e., $q=a$) reduces to
$\left\langle\varrho\right\rangle_{\cal D}/\varrho_{H}=4$, confirming the
result obtained by a slightly different method in [34] and [41]. Note that
$H$, $q$ and $\dot{q}$ are understood to be evaluated at the turnaround.
Equation (3.3) involves the structure mass and volume in addition to the
background functions, which establishes the maximum volume without specifying
the initial conditions and regardless of the details of the collapse.

As a final remark in this section, we would like to point out that this
derivation differs from the one in [41] and [34]. This is due to the subtle
ambiguity inherent to the RZA, where two definitions of the domain-dependent
scale factor, the kinematic and dynamical, are in principle possible. In our
derivation, we use the kinematic definition, which is usually considered
slightly inferior; however, since we are aiming at describing early stages of
the mildly non-linear regime (up to a turnaround), both definitions are
equally acceptable (see [7] for details and the direct comparison of these
definitions).

###  3.1 Turnaround “radius”

To pave the relation with other treatments in the literature, we supplement
this section with an estimation of the characteristic scale of the cosmic
structure at the turnaround. At the time of the last scattering, the density
distribution corresponds to fluctuations ($\Delta\rho_{H}({t_{\rm\bf i}})$)
around the density value predicted by the Friedmann model
($\rho_{H}({t_{\rm\bf i}})$). These fluctuations are usually several orders of
magnitude smaller than $\rho_{H}({t_{\rm\bf i}})$; hence,

$\left\langle\varrho\right\rangle_{\cal
D}=\frac{\left\langle\varrho({t_{\rm\bf i}})\right\rangle_{{\cal D}_{\rm\bf
i}}}{a_{{\cal D}}^{3}}=\frac{\int_{{\cal D}_{i}}\,{\rm
d}^{3}X\left(\rho_{H}({t_{\rm\bf i}})+\Delta\rho_{H}({t_{\rm\bf
i}})\right)}{a_{{\cal D}}^{3}V_{{{\cal D}_{\rm\bf
i}}}}\simeq\frac{\rho_{H}({t_{\rm\bf i}})}{a_{{\cal D}}^{3}}\ .$ (3.4)

Substituting (3.4) into (3.3), we find a relationship between the background
and average scale factors:

$\left(\frac{a}{a_{{\cal D}}}\right)^{3}\simeq
1+3\left[H\bigg{/}\left(\frac{\dot{q}}{q}\right)\right]\ .$ (3.5)

This expression can be rewritten as an estimate of the volume at the
turnaround

$V_{{\cal
D}}(t_{ta})=\frac{M}{\rho_{H}\left(1+3H\left(\frac{\dot{q}}{q}\right)^{-1}\right)}\
,$ (3.6)

where $M=M(t_{i})\simeq\varrho_{H}(t_{i})V_{{\cal D}_{i}}$ is the (conserved)
mass of the structure.

The structure volume $V_{{\cal D}}(t_{ta})$ could be associated with its
characteristic length or radius: $\ell^{3}(t_{ta})\sim V(t_{ta})$.

However, in an anisotropic (pancake or filamentary) collapse, the length scale
in one eigen-direction differs considerably from the others and thus we note
that the characteristic scale has only a limited applicability i.e. the
(quasi-)spherical models.

###  3.2 Some numerical results

To examine the predictions of formulas (3.3) and (3.6), it is convenient to
express them in terms of the redshift and the present-day cosmic parameters
([39]): $\Omega_{m0}=0.315$, $\Omega_{\Lambda 0}=1-\Omega_{m0}$,
$H_{0}=67.4\,\mbox{km}\,\mbox{s}^{-1}\mbox{Mpc}^{-1}$; also, we will formally
allow a non-vanishing spatial curvature, $\Omega_{k0}$. Then, Eq. (3.3) takes
the following form:

$\frac{\left\langle\varrho\right\rangle_{\cal
D}}{\varrho_{H}}=1+3\zeta(z)^{-1}\ ,$ (3.7)

with

$\displaystyle\zeta(z)$ $\displaystyle:=$
$\displaystyle\frac{\dot{q}}{qH}=-\frac{3}{2}\frac{\Omega_{m0}(1+z)^{3}}{E^{2}(z)}-\Omega_{k0}\frac{(1+z)^{2}}{E^{2}(z)}+\frac{(1+z)^{2}}{E^{3}(z)}\left(\int_{z}^{\infty}{\hbox{d}}z^{\prime}\frac{(1+z^{\prime})}{E^{3}(z^{\prime})}\right)^{-1},\qquad$
(3.8) $\displaystyle E^{2}(z)$ $\displaystyle:=$
$\displaystyle\frac{H^{2}}{H_{0}^{2}}=\left(\Omega_{m0}\left(1+z\right)^{3}+\Omega_{k0}(1+z)^{2}+\Omega_{\Lambda
0}\right)\ .$ (3.9)

Similarly, Eq. (3.6) leads to an approximate expression for the dimension of
the structures reaching the turnaround at a particular $z$:

$V(z)\simeq\frac{1}{(1+z)^{3}}\left(\frac{M}{\varrho_{c0}\Omega_{m0}\left(1+3\zeta(z)^{-1}\right)}\right)\
.$ (3.10)

As before, $M$ is the mass of the structure and
$\varrho_{c0}=\frac{3H_{0}^{2}}{8\pi G}$ is the critical density.

In Fig. 1 (left panel), we observe the maximum length scales as a function of
the mass in the $\Lambda$CDM cosmology. The zero expansion radius is plotted
for comparison. As expected, the zero expansion surface is contained within
the maximum volume region. As a proof-of-concept, we plot the maximum radius
at $z=1$ for different sets of cosmological parameters in the right panel. It
is worth noticing that the discrepancies between different background models
become substantial with the increase of the mass.

In the left panel of Fig. 2, the redshift dependence of the maximum radius is
plotted against the constant in time zero-expansion radius. These plots
suggest that the maximum turnaround radius (maximum volume) can complement the
zero-expansion radius test at lower redshifts as it becomes visibly less
correlated. The right panel of the same figure confirms that the low redshift
observations are the most sensible for testing different background models.

Figure 1:  Characteristic length as a function of the mass for $z=0,1,3$ (left
panel) and different cosmologies at $z=1$ (right panel). In the latter the
five models correspond to different values of $\Omega_{k0}$ at $z=0$:
$\Omega_{k0}=\left[-1+\Omega_{m0},-0.5,0,0.5,1-\Omega_{m0}\right]$, while
$\Omega_{m0}=0.315$ and $\Omega_{\Lambda}=1-\Omega_{m0}-\Omega^{(i)}_{k0}$.

Figure 2:  Characteristic length at the turnaround as a function of the
redshift for structures with $M=10^{13},10^{14},10^{15}M_{\odot}$ (left
panel), and different cosmological models with $M=10^{15}M_{\odot}$ (right
panel). In the left panel, the lines $R=3MG/\Lambda$ for each value of the
mass are displayed as a reference, and in the right panel, the models are the
same as in Fig. 1.

###  3.3 Applications

The turnaround epoch, as described in the previous sections, is a distinctive
stage in the evolution of cosmological structures that can be used to test
certain theories. In this section, we will briefly discuss two possible tests:
observational and numerical. Formula 3.6 gives us the upper bound on the
volume of any structure, during its collapse history, as a function of the
mass, the background-dependent growth function and the scale factor. In
principle, determination of these quantities is possible observationally, and
a very similar approach was attempted in order to determine the zero-expansion
surface ([30]). The main difference is that to claim that any particular zero
averaged expansion volume violates the upper bound we need to determine
whether the still expanding region of the given structure will be a part of
the collapsed object in the future. One possible method to obtain it is based
on the velocity analysis of the outer, still expanding regions of the galaxy
clusters and finding its correlation with the central structure [16].
Alternatively, by estimating the mass of the galaxy cluster or super-cluster
with the X-ray emission, velocity dispersion, gravitational lensing or
Sunayev-Zel’dovich effect, we can use the caustics method (see e.g. [42]) to
determine whether the given tracer (galaxy) has a velocity below the escape
velocity and thus is a part of the bound structure that has not yet
virialized.

Another application of the maximum volume is related to the N-body simulations
and the backreaction conjecture. Estimates of the backreaction have been so
far addressed either within the fluid formalism: e.g. [27] and [31] or within
the N-body codes but on the global scale: [1]. With the maximum volume
approach, we can test the predictions of the averaged scalar equations
together with the RZA serving as a closure condition by looking at the scales
of clusters and super-clusters in the N-body simulations. The construction of
the RZA is well suited for such comparisons as it relies on the notion of
background, a generic feature of the majority of the N-body architectures. In
[17], a related examination was performed to find the zero-expansion radius.

##  4 Discussion and comparison with exact cases

In Sec. 3, we introduced the turnaround stage as marked by the vanishing of
the average of the expansion scalar, furnishing the most direct generalization
of the analogous definition in the standard spherical collapse model. The
predictions coming from applying this definition reduce to well-known results
in the homogeneous limit.

As a part of our approach, we are averaging out the solution’s intrinsic
anisotropy and inhomogeneity, and reducing all the relevant physical
information to a single kinematical quantity, the volume. Such a description
matches our intuition in a (quasi-)isotropic collapse but should not be
applied to a highly anisotropic pancake collapse where the structure is found
collapsing along two directions but expanding along the third (see an explicit
solution further below).

Some comments are in order about the applicability of the expressions for the
density ratio and the estimation of the volume at the turnaround time. While
our definition of the turnaround is general, Eq. (3.7) and (3.10) were
obtained under the assumption that there exists a referential cosmological
background and that the structures form from a growing mode of the solution of
(2.9). This relates the domain of applicability of our model to the one of the
RZA, which is known to provide an accurate description of the structure
formation in the mildly non-linear regime. Consequently, our model and its
predictions are expected to be accurate for the turnaround of the galaxy
clusters and super-clusters.

###  4.1 Some exact models

In order to gain a better insight into the properties of the turnaround
condition, we examine some exact illustrative solutions. First, we consider
the Szekeres models of class II and interpret the solution as a fluctuation on
the FLRW background. This constitutes the exact limit of the model presented
in Sec. 3. Then, we relax the hypothesis of the coupling of the growing
fluctuations to the background, and search for possible extensions of the
current formalism.

####  4.1.1 Szekeres class II as exact fluctuations on an FLRW background

The RZA contains the Szekeres class II models as an exact subcase [20]. In
this sense, it is not surprising that the approximate expressions for the
density ratio and volume at the turnaround become exact for the Szekeres
universes. However, demonstration of this fact constitutes a necessary
consistency test for our model.

The line-element of Szekeres-II models can be cast as follows (see [22] for
the introduction of this parametrization and [28, 40, 5] for a detailed
analysis of the Szekeres solutions)

${\hbox{d}}s^{2}=-{\hbox{d}}t^{2}+a^{2}\left(({\cal{A}}(\bm{r})-{\cal{F}}(t,z))^{2}{\hbox{d}}z^{2}+e^{2\nu(\bm{r})}\left({\hbox{d}}x^{2}+{\hbox{d}}y^{2}\right)\right)\
,$ (4.1)

where ${\cal{A}}$ and $e^{\nu}$ are functions of the comoving coordinates333
The metric functions $e^{\nu}$ and ${\cal{A}}$ are given by
$e^{\nu}=\left(1+k_{0}(x^{2}+y^{2})/4\right)^{-1}$,
${\cal{A}}=e^{\nu}\Big{[}c_{0}(z)\left(1-\frac{k_{0}}{4}(x^{2}+y^{2})\right)+c_{1}(z)x+c_{2}(z)y\Big{]}-k_{0}\beta_{+}$
for $k_{0}=\pm 1$, and
${\cal{A}}=c_{0}(z)+c_{1}(z)x+c_{2}(z)y-\beta_{+}(z)(x^{2}+y^{2})/2$ for
$k_{0}=0$. . The conformal scale factor, $a(t)$, obeys a Friedmann-like
equation:

$\dot{a}^{2}=-k_{0}+\frac{2\mu}{a}+\frac{\Lambda}{3}a^{2}\ ,$ (4.2)

with $\mu=\mbox{const.}$, $k_{0}=0,\pm 1$ and
${\cal{F}}(t,z)=\beta_{+}(z)q_{+}(t)+\beta_{-}(z)q_{-}(t)$. The functions
$\beta_{\pm}$ are arbitrary, and $q_{\pm}(t)$ obey (2.9) but with
$4\pi\varrho_{H}\rightarrow 3\mu$. As in Sec. 3, we will neglect the
contribution of the decaying solution ($\beta_{-}=0$).

So far, this is only an ansatz; however, if the constant $\mu$ is identified
as the initial value of the background density, $3\mu=4\pi\varrho_{H}(t_{i})$,
the solution acquires an interpretation as an exact fluctuation evolving on
the Friedmann background.

To obtain the relationship between the physical quantities at the turnaround,
we first average the density and expansion scalar of the dust source,

$\displaystyle\varrho(t,\bm{r})=\frac{\varrho_{H}(t_{i})}{a^{3}}\left(\frac{{\cal{A}}}{{\cal{A}}-\beta\,q}\right)\
,\quad\mbox{and}\quad\mathcal{H}=\frac{\dot{a}}{a}-\frac{1}{3}\frac{\beta_{+}\dot{q}_{+}}{{\cal{A}}-\beta_{+}q_{+}}\
,$ (4.3)

which gives:

$\displaystyle\left\langle\varrho\right\rangle_{\cal
D}=\varrho_{H}\frac{1}{1-q_{+}(\chi_{\mathcal{D}}/\upsilon_{\mathcal{D}})}\
,\quad\mbox{and}\quad H_{{\cal
D}}=H-\frac{1}{3}\frac{\dot{q}_{+}\chi_{\mathcal{D}}}{\upsilon_{\mathcal{D}}-q_{+}\chi_{\mathcal{D}}}\
,$ (4.4)

with $\chi_{\mathcal{D}}:=\int_{\cal D}\beta_{+}e^{2\nu}d^{3}\bm{r}$ and
$\upsilon_{\mathcal{D}}:=\int_{\cal D}{\cal{A}}e^{2\nu}d^{3}\bm{r}$. Then,
imposing the turnaround condition, $H_{{\cal D}}=0$, solving it for
$\chi_{\mathcal{D}}/\upsilon_{\mathcal{D}}$, and substituting the result into
the first equation in (4.4), we obtain the same expression as in (3.3).
However, unlike the equations obtained in Sec. 3, this relation is exact.
Finally, Eq. (3.6) can be found by following the same steps as in the
approximate case.

####  4.1.2 Beyond the RZA

The existence of a cosmological background coupled to the inhomogeneities has
been one of our fundamental assumptions so far. However, there are physical
situations where one can treat the inhomogeneities as separate universes or
dispense with the existence of the background. The simplest example is the
standard spherical collapse model, for which our definition of the turnaround
leads to the same well-known results since $H_{{\cal D}}=H$.

The collapse of a spherical and homogeneous overdensity, evolving separately
from the background, can be easily generalized using the Szekeres models.
Taking $k_{0}=1$ and $\Lambda=0$ in (4.2), the Einstein’s equations have
analytical solutions (as before, we are neglecting the decaying solution for
$q$) [22]:

$\displaystyle t(\theta)=\mu\left(\theta-\sin\theta\right)\ ,\quad
a(\theta)=\mu\left(1-\cos\theta\right)\ ,\quad
q(\theta)=\frac{6\mu}{a}\left(1-\frac{\theta}{2}\cot\frac{\theta}{2}\right)-1\
.$ (4.5)

In this model, Eq. (4.2) does not describe the evolution of a physical
background but should be interpreted as a convenient ansatz. —To have a non-
FLRW model and avoid shell-crossing singularities the free functions should
satisfy: $\beta<0$ and $\mu>0$. Our definition of the turnaround leads to the
second equation in (4.4), which implies that:

$\frac{\dot{a}}{a}=-\frac{1}{3}\frac{\dot{q}\,\int_{\cal
D}|\beta|e^{2\nu}d^{3}\bm{r}}{\int_{\cal
D}{\cal{A}}e^{2\nu}d^{3}\bm{r}-q\,\int_{\cal
D}|\beta|e^{2\nu}d^{3}\bm{r}}<0\;.$ (4.6)

Thus the turnaround is reached at a certain time while the structure is
recollapsing along the directions $x$ and $y$, but expanding along $z$. This
mechanism allows for significant differences between the characteristic scales
of the structure along different eigendirections. Consequently, a description
based on a unique characteristic length ($\ell\sim V^{1/3}$) might not be
accurate.

##  5 Conclusions

The zero average expansion condition has been proposed to mark the turnaround
epoch of a generic collapsing structure to which the dust description applies.
The scalar averaged Einstein’s equations together with the RZA closure
condition were employed to model the evolution of spatially extended objects.
In particular, the averaged Hamiltonian constraint with the average zero-
expansion condition allows one to determine the maximum volume attainable by
cosmological structures as a function of redshift, mass and background model,
removing the dependence on the initial conditions. This formulation leads to
two possible cosmological tests: the upper bound on the volume of collapsing
objects which can be used to exclude particular background models, including
the concordance $\Lambda$CDM model, and the N-body tests directly related to
the backreaction conjecture on the scales of clusters and super-clusters
(similar considerations within alternative theories of gravity are in
principle possible). The observational determination of the volume of the
structure can be supplemented with the additional information on the mass of
the structure, estimated from the mass function of the galaxy clusters and
super-clusters. This was done in [35] within the RZA context, only for the
virialized structures. Replacing the virialization by the turnaround condition
would equip us with the statistical expectations for the masses of the
structures at the turnaround as a function of redshifts within the same
formalism. We leave the detailed examination of this concept to future work.

The turnaround epoch, at most, belongs to the mildly non-linear regime, where
the Lagrangian perturbation theory is expected to produce a reliable
predictions. One advantage of the Lagrangian approach is that, also at the
first order, it effectively reproduces higher orders in the standard Eulerian
perturbation theory. This property validates the applicability of the analysis
presented in this paper to the mildly non-linear scenarios [37]. At the same
time, the use of the RZA allows one to reproduce the results obtained within
the Szekeres class II solutions as a particular case of our model, thus
reinforcing its consistency. The fact that these formulas become exact for
such general solution to Einstein’s equations444 Szekeres models of class II
are a generalization of the FLRW and Kantowski-Sachs solutions commonly used
as a toy models for inhomogeneous universes [38, 26, 32, 33]. confirms that
their predictions are a direct consequence of relativistic modelling.

It is worth noticing that the utility of the zero-average expansion regions
extends beyond the applications proposed in this article. In particular, the
zero-average expansion condition was proposed in [43] as an attempt to define
the so-called finite infinity ([12]) i.e. a region that could effectively
replace the spatial infinity in the context of isolated objects in the
expanding Universe. The zero-expansion surface was examined in the context of
an intimately related notion of the quasi-local energy in [18]. For the non-
virialized objects, however, the local zero-expansion surface lies well within
the large-scale structure and thus is less relevant to the notion of finite
infinity. For these reasons we claim that the zero-average expansion idea is
potentially useful for cosmology and general relativity and deserves further
examination.

## Acknowledgments

The authors acknowledge the support of the National Science Centre (NCN,
Poland) under the Sonata-15 research grant UMO-2019/35/D/ST9/00342. We wish to
thank Thomas Buchert and Nezihe Uzun for many valuable comments on this
manuscript.

## References

  * [1] Julian Adamek, Chris Clarkson, David Daverio, Ruth Durrer, and Martin Kunz.  Safely smoothing spacetime: backreaction in relativistic cosmological simulations.  Classical and Quantum Gravity, 36(1):014001, January 2019.
  * [2] Fosca Al Roumi, Thomas Buchert, and Alexander Wiegand.  Lagrangian theory of structure formation in relativistic cosmology. IV. Lagrangian approach to gravitational waves.  Phys. Rev. D, 96(12):123538, December 2017.
  * [3] Alexandre Alles, Thomas Buchert, Fosca Al Roumi, and Alexander Wiegand.  Lagrangian theory of structure formation in relativistic cosmology. III. Gravitoelectric perturbation and solution schemes at any order.  Phys. Rev. D, 92(2):023512, July 2015.
  * [4] W. E. Ballinger, J. A. Peacock, and A. F. Heavens.  Measuring the cosmological constant with redshift surveys.  Mon. Not. R. Astr. Soc., 282:877, October 1996.
  * [5] Krzysztof Bolejko, Marie-Noëlle Célérier, and Andrzej Krasiński.  Inhomogeneous cosmological models: exact solutions and their applications.  Class. Quant. Grav., 28(16):164002, August 2011.
  * [6] Thomas Buchert.  On Average Properties of Inhomogeneous Fluids in General Relativity: Dust Cosmologies.  General Relativity and Gravitation, 32:105–126, January 2000.
  * [7] Thomas Buchert, Martin Kerscher, and Christian Sicka.  Back reaction of inhomogeneities on the expansion: The evolution of cosmological parameters.  Phys. Rev. D, 62(4):043525, August 2000.
  * [8] Thomas Buchert, Charly Nayet, and Alexander Wiegand.  Lagrangian theory of structure formation in relativistic cosmology. II. Average properties of a generic evolution model.  Phys. Rev. D, 87(12):123503, June 2013.
  * [9] Thomas Buchert and Matthias Ostermann.  Lagrangian theory of structure formation in relativistic cosmology: Lagrangian framework and definition of a nonperturbative approximation.  Phys. Rev. D, 86(2):023520, July 2012.
  * [10] Chris Clarkson, Bruce Bassett, and Teresa Hui-Ching Lu.  A General Test of the Copernican Principle.  Phys. Rev. Lett., 101(1):011301, July 2008.
  * [11] Antonino Del Popolo, Man Ho Chan, and David F. Mota.  Turnaround radius in $\Lambda$ CDM and dark matter cosmologies with shear and vorticity.  Phys. Rev. D, 101(8):083505, April 2020.
  * [12] G. F. R. Ellis.  Relativistic cosmology: its nature, aims and problems.  In General Relativity and Gravitation Conference, pages 215–288, January 1984.
  * [13] Buchert, T. et al.  Is there proof that backreaction of inhomogeneities is irrelevant in cosmology?  Classical and Quantum Gravity, 32(21):215021, November 2015.
  * [14] Chuang, Chia-Hsun et al.  The clustering of galaxies in the SDSS-III Baryon Oscillation Spectroscopic Survey: single-probe measurements from CMASS anisotropic galaxy clustering.  Mon. Not. R. Astr. Soc., 461(4):3781–3793, October 2016.
  * [15] Eisenstein, Daniel J. et al.  Detection of the Baryon Acoustic Peak in the Large-Scale Correlation Function of SDSS Luminous Red Galaxies.  Astrophys. J., 633(2):560–574, November 2005.
  * [16] Falco, Martina et al.  A new method to measure the mass of galaxy clusters.  Mon. Not. R. Astr. Soc., 442(2):1887–1896, August 2014.
  * [17] Korkidis, Giorgos et al.  Turnaround radius of galaxy clusters in N-body simulations.  Astron. Astrophys., 639:A122, July 2020.
  * [18] Valerio Faraoni, Marianne Lapierre-Léonard, and Angus Prain.  Turnaround radius in an accelerated universe with quasi-local mass.  JCAP, 2015(10):013, October 2015.
  * [19] Hume A. Feldman, Nick Kaiser, and John A. Peacock.  Power-Spectrum Analysis of Three-dimensional Redshift Surveys.  Astrophys. J., 426:23, May 1994.
  * [20] Ismael Delgado Gaspar and Thomas Buchert.  Lagrangian theory of structure formation in relativistic cosmology. VI. Comparison with Szekeres exact solutions.  Phys. Rev. D, 103(2):023513, January 2021.
  * [21] Andrea Giusti and Valerio Faraoni.  Turnaround physics beyond spherical symmetry.  Phys. Rev. D, 103(4):044049, February 2021.
  * [22] S. W. Goode and J. Wainwright.  Singularities and evolution of the Szekeres cosmological models.  Phys. Rev. D, 26(12):3315–3326, December 1982.
  * [23] Stephen R. Green and Robert M. Wald.  New framework for analyzing the effects of small scale inhomogeneities in cosmology.  Phys. Rev. D, 83(8):084020, April 2011.
  * [24] Steen H. Hansen, Farbod Hassani, Lucas Lombriser, and Martin Kunz.  Distinguishing cosmologies using the turn-around radius near galaxy clusters.  JCAP, 2020(1):048, January 2020.
  * [25] Daniel E. Holz and Saul Perlmutter.  The Most Massive Objects in the Universe.  Astrophys. J. Letters, 755(2):L36, August 2012.
  * [26] Mustapha Ishak and Austin Peel.  Growth of structure in the Szekeres class-II inhomogeneous cosmological models and the matter-dominated era.  Phys. Rev. D, 85(8):083502, April 2012.
  * [27] Tomasz A. Kazimierczak.  Newtonian kinematical backreaction in cosmological N-body simulations with Delaunay Tesselation: “Zero test” and scale dependence.  In Massimo Bianchi, Robert T. Jansen, and Remo Ruffini, editors, Fourteenth Marcel Grossmann Meeting - MG14, pages 2339–2344, January 2018.
  * [28] Andrzej Krasiński.  Inhomogeneous Cosmological Models.  Cambridge University Press, hardcover edition, 7 1997.
  * [29] Jounghun Lee, Suk Kim, and Soo-Chang Rey.  A Bound Violation on the Galaxy Group Scale: The Turn-around Radius of NGC 5353/4.  Astrophys. J., 815(1):43, December 2015.
  * [30] Jounghun Lee, Suk Kim, and Soo-Chang Rey.  A Bound Violation on the Galaxy Group Scale: The Turn-around Radius of NGC 5353/4.  Astrophys. J., 815(1):43, December 2015.
  * [31] Hayley J. Macpherson, Daniel J. Price, and Paul D. Lasky.  Einstein’s Universe: Cosmological structure formation in numerical relativity.  Phys. Rev. D, 99(6):063522, March 2019.
  * [32] Nikolai Meures and Marco Bruni.  Exact nonlinear inhomogeneities in $\Lambda$CDM cosmology.  Phys. Rev. D, 83(12):123519, June 2011.
  * [33] Nikolai Meures and Marco Bruni.  Redshift and distances in a $\Lambda$CDM cosmology with non-linear inhomogeneities.  Mon. Not. R. Astr. Soc., 419(3):1937–1950, January 2012.
  * [34] Jan J. Ostrowski.  A few numbers from the turnaround epoch of collapse.  arXiv e-prints, page arXiv:1912.12683, December 2019.
  * [35] Jan J. Ostrowski, Thomas Buchert, and Boudewijn F. Roukema.  Mass Function of Galaxy Clusters in Relativistic Inhomogeneous Cosmology.  Acta Physica Polonica B, Proceedings Supplement, 10(2):407, January 2017.
  * [36] V. Pavlidou and T. N. Tomaras.  Where the world stands still: turnaround as a strong test of $\Lambda$CDM cosmology.  JCAP, 2014(9):020, September 2014.
  * [37] John A. Peacock.  Cosmological Physics.  Cambridge University Press, paperback edition, 12 1998.
  * [38] Austin Peel, Mustapha Ishak, and M. A. Troxel.  Large-scale growth evolution in the Szekeres inhomogeneous cosmological models with comparison to growth data.  Phys. Rev. D, 86(12):123508, December 2012.
  * [39] Planck Collaboration.  Planck 2018 results. VI. Cosmological parameters.  Astron. Astrophys., 641:A6, September 2020.
  * [40] Jerzy Plebański and Andrzej Krasiński.  An Introduction to General Relativity and Cosmology.  Cambridge University Press, hardcover edition, 8 2006.
  * [41] Boudewijn F. Roukema and Jan J. Ostrowski.  Does spatial flatness forbid the turnaround epoch of collapsing structures?  JCAP, 2019(12):049, December 2019.
  * [42] Ana Laura Serra, Antonaldo Diaferio, Giuseppe Murante, and Stefano Borgani.  Measuring the escape velocity and mass profiles of galaxy clusters beyond their virial radius.  Mon. Not. R. Astr. Soc., 412(2):800–816, April 2011.
  * [43] David L. Wiltshire.  Cosmic clocks, cosmic variance and cosmic averages.  New Journal of Physics, 9:377, October 2007.