text:
# Ionic criticality : an exactly soluble model

## Abstract

Gas-liquid criticality in ionic fluids is studied in exactly soluble spherical models that use interlaced sublattices to represent hard-core multicomponent systems. Short range attractions in the uncharged fluid drive criticality but charged ions do not alter the universality class. Debye screening remains exponential at criticality in charge-symmetric 1:1 models. However, asymmetry couples charge and density fluctuations in a direct manner: the charge correlation length then diverges precisely as the density correlation length and the Stillinger-Lovett rule is violated at criticality.

The nature of gas-liquid (or, more generally fluid-fluid) criticality in systems in which long-range ionic interactions play a significant role has been a focus of attention since still-puzzling experiments questioned the appropriate universality class Weingärtner and Schröer (2001). Beyond further experiments Weingärtner and Schröer (2001), numerous theoretical Fisher (1994); Stell (1995); Lee and Fisher (1996); Muratov (2000) and computational Romero-Enrique et al. (2000) studies have been reported; however, basic questions remain open. Certainly, the character of criticality depends on the range of the interactions: One expects an Ising critical point in a fluid with short-range couplings but mean-field behavior for interactions of sufficiently long-range. So, might the introduction of ions interacting via long-range Coulomb forces destroy an Ising-type critical point? Coulomb interactions are exponentially screened in a conducting classical fluid, as proved rigorously at low densities Brydges and Federbush (1980). Charge fluctuations in a fluid of $`𝒮`$ species of charges $`q_\sigma `$ and valences $`z_\sigma =q_\sigma /q`$ (where $`q`$ is an elementary charge), thus decay over a few Debye screening lengths $`\xi _D`$, where

$$\xi _D^2(T,\rho )=4\pi \rho q^2_{\sigma =1}^𝒮z_\sigma ^2x_\sigma /k_BT,$$
(1)
in which $`\rho =_\sigma \rho _\sigma `$ is the overall density while the mole fractions are $`x_\sigma =\rho _\sigma /\rho `$. But, does exponential screening on this scale hold near and at criticality?

Indeed, a major open issue is the behavior of the pairwize charge correlations near the critical point, where the density fluctuations diverge strongly. With

$$G_{\sigma \tau }(𝐫)=\rho _\sigma (\mathrm{𝟎})\rho _\tau (𝐫)\rho _\sigma \rho _\tau ,$$
(2)
the correlation functions, $`G_{NN}`$, $`G_{ZZ}`$, and $`G_{NZ}`$ for the density, charge, and charge-density, are Lee and Fisher (1996)

$$G_{XY}(𝐫;T,\rho )=_{\sigma ,\tau }q_\sigma ^{\vartheta _X}q_\tau ^{\vartheta _Y}G_{\sigma \tau }(𝐫;T,\rho ),$$
(3)
where $`X`$ and $`Y`$ may be $`N`$ or $`Z`$ while $`\vartheta _N=0`$ and $`\vartheta _Z=1`$. Except at the critical point $`(T_c,\rho _c)`$, itself, we may suppose that the corresponding structure factor, $`S_{NN}`$, has the small $`k=|𝐤|`$ expansion

$$S_{NN}(𝐤)/S_{NN}(\mathrm{𝟎})=1+_{p1}()^p\xi _{N,p}^{2p}(T,\rho )k^{2p}.$$
(4)
Near criticality, $`S_{NN}(\mathrm{𝟎};T,\rho _c)`$ diverges as $`1/t^\gamma `$ when $`t(TT_c)/T_c0+`$, while the length $`\xi _{N,\mathrm{}}`$ characterizing the exponential decay of $`G_{NN}(𝐫;T,\rho _c)`$ diverges as $`\xi _N^0/t^\nu `$ (where short-range forces have been assumed). At criticality, density fluctuations are long-ranged and $`S_{NN}(𝐤;T_c,\rho _c)1/k^{2\eta }`$.

By contrast, the charge structure factor should obey

$$S_{ZZ}(𝐤)=0+\xi _{Z,1}^2k^2_{p2}()^p\xi _{Z,p}^{2p}(T,\rho )k^{2p},$$
(5)
where the first vanishing term results from electroneutrality reflecting the internal screening in an ionic fluid, while the Stillinger-Lovett sum-rule Stillinger and Lovett (1968); Martin (1988)

$$\xi _{Z,1}(T,\rho )=\xi _D(T,\rho ),$$
(6)
characterizes the screening of external charges. Does this hold near and at criticality? Finally, we focus also on the charge correlation length $`\xi _{Z,\mathrm{}}(T,\rho )`$, that specifies the exponential decay of $`G_{ZZ}(𝐫)`$ when $`r\mathrm{}`$. How does $`\xi _{Z,\mathrm{}}`$ vary when $`\xi _{N,\mathrm{}}`$ diverges near criticality?

To obtain insight into these questions, we study multicomponent lattice gas generalizations of the spherical model Joyce (1972); Smith (2003); Barbosa and Fisher (1991) specifically designed to represent hard-core interactions and thus avoid the mutual “annihilation” of oppositely charged ions on the same site. This crucial feature, which (in contrast to Smith (2003)) allows gas-liquid criticality to survive in the presence of Coulomb interactions, is accomplished by using a set of equivalent interlacing sublattices (with sites $`i`$ at $`𝐑_i^\sigma `$ with spacing $`a`$), one for each of the $`\sigma =1,2,\mathrm{},𝒮`$ distinct particle species Cornu and Jancovici (1987). Thereby unlike charges cannot approach closer than an effective hard-core diameter $`a_0`$: see, e.g., Fig. 1.

To specify the models more fully, consider a multicomponent grand canonical lattice gas with site occupancy variables $`n_i^\sigma =0,1`$; this is equivalent to an Ising magnet with spins $`s_i^\sigma =2n_i^\sigma 1=\pm 1`$, subject to fields $`h_\sigma `$ (linearly related to the chemical potentials, $`\mu _\sigma `$). For attractive interparticle potentials, the corresponding spin-spin couplings, $`J_{\sigma \tau }(𝐑)`$, at lattice separations $`𝐑`$, are positive. We decompose these couplings as

$$J_{\sigma \tau }(𝐑)=J_{\sigma \tau }^0(𝐑)\frac{1}{4}q_\sigma q_\tau \phi ^C(𝐑),$$
(7)
where $`J_{\sigma \tau }^0(𝐑)`$ represents short-range or, more generally, integrable interparticle interactions which we suppose suffice to drive gas-liquid criticality (even if the charges $`q_\sigma `$ vanish). We take the $`d`$-dimensional Coulomb potential, $`\phi ^C(𝐑)1/R^{d2}`$ ($`d>2`$), as the solution of an appropriate discrete Laplace equation Aqua and Fisher  (with, for convenience, a uniform neutralizing background so that electroneutrality, $`_\sigma x_\sigma q_\sigma =0`$, must be imposed). Fourier transforms, $`\widehat{J}_{\sigma \tau }(𝐤)`$, are defined by summing over one sub-lattice, with Brillouin zone $``$, and it is useful to introduce

$$\mathrm{\Delta }J_{\sigma \tau }(𝐤)\frac{1}{2}[\widehat{J}_{\sigma \tau }(\mathrm{𝟎})\widehat{J}_{\sigma \tau }(𝐤)].$$
(8)
To model a simple 1:1 electrolyte one needs only $`𝒮=2`$ components, say $`+`$ and $``$ with $`q_\pm =\pm q`$. We may then identify basic energy and range scales, $`j_0`$ and $`R_0`$, via

$$\widehat{J}_+^{\mathrm{\hspace{0.17em}0}}(\mathrm{𝟎})k_BT_02j_0>0,$$
(9)
and, assuming short-range isotropic nonionic couplings,

$$\mathrm{\Delta }J_{++}^0+2\mathrm{\Delta }J_+^0+\mathrm{\Delta }J_{}^02j_0R_0^2k^2>0,$$
(10)
as $`k0`$. Now, if $`J_{++}(𝐑)=J_{}(𝐑)`$, the model is (fully) charge symmetric (as is the well known continuum Restricted Primitive Model or RPM Weingärtner and Schröer (2001); Fisher (1994); Stell (1995); Romero-Enrique et al. (2000)). A suitable charge asymmetry parameter is then Aqua and Fisher

$$\delta _J=\underset{𝐤}{\mathrm{max}}|\mathrm{\Delta }J_{++}(𝐤)\mathrm{\Delta }J_{}(𝐤)|/k_BT_0,$$
(11)
which might, e.g., be used to represent distinct ionic sizes, $`a_+`$ and $`a_{}`$ \[6(a)\]. As the simplest “Basic Ionic Model” it suffices to take only nearest neighbor couplings, $`J_+^0>0`$ and $`J_{++}^0=J_{}^0`$; then one has $`j_0=2^{d1}J_+^0`$ and $`\delta _J=d|J_{++}^0|/2^{d2}|J_+^0|`$. Finally, as a dimensionless measure of the relative strength of the Coulomb interactions, it is helpful to introduce the ionicity Moreira et al. (1999)

$$_0=q^2/a^{d2}k_BT_0.$$
(12)
Of course, even this Basic Ionic Model is insoluble for $`d2`$. Accordingly, in the standard way Joyce (1972); Smith (2003); Barbosa and Fisher (1991), we “sphericalize” these multicomponent models by taking the spins $`s_i^\sigma `$ as unbounded continuous variables subject only to $`𝒮`$ spherical constraints, $`s_\sigma ^2=1`$, enforced with the aid of $`𝒮`$ Lagrange multipliers which, for later convenience, we write as $`\lambda _\sigma +\frac{1}{2}\widehat{J}_{\sigma \sigma }(\mathrm{𝟎})`$. In full generality, the singular part of the total free energy $`f[T,𝐡;𝝀(T,𝐡)]`$ in the thermodynamic limit, is then Aqua and Fisher

$$f_s(T;𝝀)=\frac{1}{2}k_BT_𝐤\mathrm{ln}\left\{\left|𝚲(𝐤;𝝀)\right|/(k_BT)^𝒮\right\},$$
(13)
where $`_𝐤(a/2\pi )^d_𝐤d^d𝐤`$ and $`𝐡=(h_\sigma )`$ and $`𝝀=(\lambda _\sigma )`$, while the $`𝒮\times 𝒮`$ matrix $`𝚲`$ has elements

$$\mathrm{\Lambda }_{\sigma \tau }=\left[\lambda _\sigma +\mathrm{\Delta }J_{\sigma \sigma }(𝐤)\right]\delta _{\sigma \tau }\frac{1}{2}(1\delta _{\sigma \tau })\widehat{J}_{\sigma \tau }(𝐤).$$
(14)
The field-dependent contribution to the free energy is

$$f_h=\frac{1}{4}𝐡|𝚲^1(\mathrm{𝟎};𝝀)|𝐡\text{with}𝐡=2𝚲(\mathrm{𝟎};𝝀)𝐦,$$
(15)
where $`𝐦=(m_\sigma )`$ and $`m_\sigma =s_\sigma =2n_\sigma 1`$ so that $`\rho _\sigma =\frac{1}{2}\rho _\sigma ^{max}(1+m_\sigma )`$. Finally, the Lagrange multipliers $`𝝀(T,𝐡)`$ are determined implicitly via the $`𝒮`$ spherical constraints $`s_\sigma ^2=\left(f/\lambda _\sigma \right)=1`$. These results are valid while the eigenvalues of $`𝚲`$ remain positive; the vanishing of any one of them signals a thermodynamic singularity.

For brevity hereon we focus on the two-species, 1:1 case (with $`q_\pm =\pm q`$), the $`+`$ and $``$ ions residing on one of two hypercubic sublattices displaced by $`\frac{1}{2}(a,a,\mathrm{},a)`$: see Fig.1 for $`d=3`$. The eigenvalues of $`𝚲`$, to be called $`\mathrm{\Lambda }_Z`$ and $`\mathrm{\Lambda }_N`$ for reasons soon to be evident, are then simply the $`+`$ and $``$ roots of the quadratic equation $`|𝚲x𝐈|=0`$,

$$\mathrm{\Lambda }_X(𝐤;𝝀)=\overline{\lambda }+\mathrm{\Delta }\overline{J}(𝐤)()^{\vartheta _X}𝒟(𝐤;𝝀)\text{with}$$
(16)
$$𝒟^2(𝐤;𝝀)[\lambda ^{}+\mathrm{\Delta }J^{}(𝐤)]^2+\frac{1}{4}\widehat{J}_+^{\mathrm{\hspace{0.17em}2}}(𝐤),$$
(17)
where, for each variable $`g_+`$, $`g_{}`$, $`g_{++}`$, etc., we have introduced the mean $`\overline{g}=\frac{1}{2}(g_++g_{})`$ and difference $`g^{}=\frac{1}{2}(g_+g_{})`$, while the square root is chosen so that $`𝒟(\mathrm{𝟎};𝝀)>0`$ and $`\mathrm{\Lambda }_X(𝐤)`$ is analytic.

A pivotal result now transpires Aqua and Fisher , namely, the linear decomposition of the structure factors via

$$\frac{S_{XY}(𝐤;𝝀)}{k_BT/4\rho a^d}=\frac{B_{XY}^N(𝐤;𝝀)}{\mathrm{\Lambda }_N(𝐤;𝝀)}+\frac{B_{XY}^Z(𝐤;𝝀)}{\mathrm{\Lambda }_Z(𝐤;𝝀)},$$
(18)
in which $`B_{NN}^N=B_{ZZ}^Z=1B_{NN}^Z=1B_{ZZ}^N`$, while

$$B_{NN}^N(𝐤;𝝀)=\frac{1}{2}+\frac{1}{4}|\widehat{J}_+(𝐤)|/𝒟(𝐤;𝝀),$$
(19)
and $`B_{NZ}^N+B_{NZ}^Z=0`$. In the charge symmetric cases, all the $`g^{}`$ variables vanish by definition, so $`B_{NN}^N1`$ and $`B_{NN}^Z=B_{ZZ}^N0`$: this implies that $`S_{NN}`$ is entirely governed by $`\mathrm{\Lambda }_N`$, and, likewise, $`S_{ZZ}`$ by $`\mathrm{\Lambda }_Z`$, so justifying the notation. Conversely, in nonsymmetric models, both $`\mathrm{\Lambda }_N`$ and $`\mathrm{\Lambda }_Z`$ contribute to all the structure functions.

Finally, the spherical constraints reduce, first, to

$$k_BT𝒥_d(𝝀)+\overline{h}^2/4\lambda ^2=1\text{with}\lambda =\overline{\lambda }j_0^{},$$
(20)
where $`j_0^{}=\frac{1}{2}\widehat{J}_+(\mathrm{𝟎})`$ Aqua and Fisher , while the basic integral

$$𝒥_d(𝝀)=\frac{1}{4}_𝐤\left[\mathrm{\Lambda }_N^1(𝐤;𝝀)+\mathrm{\Lambda }_Z^1(𝐤;𝝀)\right],$$
(21)
becomes singular, typically as $`\mathrm{\Delta }𝒥_d\lambda ^{1/\gamma }`$, when $`\lambda `$ $`(t^\gamma )`$ vanishes, where $`\gamma `$ is the appropriate critical exponent Joyce (1972); Barbosa and Fisher (1991); Aqua and Fisher ; lastly $`\lambda ^{}`$ is given (implicitly) by

$$\lambda ^{}_𝐤1/\left|𝚲(𝐤;𝝀)\right|=_𝐤\mathrm{\Delta }J^{}(𝐤)/\left|𝚲(𝐤;𝝀)\right|.$$
(22)
Recall, however, that $`\lambda ^{}`$ vanishes identically in charge symmetric cases: more generally, this result relates $`\lambda ^{}`$ to the asymmetry parameter $`\delta _J`$ \[see Eq. (11)\] via

$$\lambda _c^{}c_\delta [J_{\sigma \tau }]\delta _J,$$
(23)
where, however, $`c_\delta [J_{\sigma \tau }]`$ might vanish “accidentally”.

We are now in a position to answer, with explanations, the questions posed after Eqns. (1)-(6). For specific numerical results we will invoke the Basic Ionic Spherical Model (BISM), i.e., the sphericalized version of the $`d=3`$, $`𝒮=2`$, 1:1 model with $`\rho _+=\rho _{}=\frac{1}{2}\rho `$ and nearest-neighbor interactions as set out with Eqns. (9)-(12). When $`\delta _J=_0=0`$ one readily finds from the vanishing of $`\mathrm{\Lambda }_N(\mathrm{𝟎})`$ when $`\lambda 0`$ Joyce (1972); Smith (2003); Barbosa and Fisher (1991); Aqua and Fisher  that standard spherical-model criticality and scaling pertains, with exponents $`\beta =\frac{1}{2}`$ and $`\gamma =1\alpha =(2\eta )\nu `$, where short-range (non-Coulomb) interactions footnote  lead to $`\eta =0`$ and $`\gamma =\mathrm{max}\{2/(d2);1\}`$ (for $`d2`$).

For $`_0`$ and $`\delta _J`$ not too large, the same situation prevails—contrary to speculations (for hard-core continuum ionic models) that lack of symmetry might lead to mean-field criticality Stell (1995). This follows most directly from the small $`𝐤`$ behavior of the eigenvalues, namely,

$`\mathrm{\Lambda }_N(𝐤;𝝀)`$ $`=\lambda +j_0R_N^2(𝝀)k^2+𝒪(k^4),`$
$`\mathrm{\Lambda }_Z(𝐤;𝝀)`$ $`=(S_dq^2/4a^d)[1/k^2+R_Z^2+𝒪(k^2)],`$ (24)
where $`S_d`$ is the area of a unit $`d`$-sphere, while Aqua and Fisher

$`R_N^2(𝝀)`$ $`=R_0^2S_d^{}a^2_02a^2\lambda ^^2/S_d_0j_0^2,`$
$`R_Z^2(𝝀,\widehat{𝐤})`$ $`=2a^2(\lambda +j_0^{})/S_d_0j_0+a^2\mathrm{\Sigma }_4(\widehat{𝐤}),`$ (25)
in which $`S_3^{}=\pi /144`$ and $`\mathrm{\Sigma }_4\frac{1}{48}_\alpha k_\alpha ^4/k^4`$. The crucial feature, following directly from (16), is that the Coulomb singularity, characterized by $`\widehat{\phi }^C(𝐤)\mathrm{\hspace{0.17em}1}/k^2`$, cancels out of $`\mathrm{\Lambda }_N`$ exactly thanks to electroneutrality. (The absence of this possibility for $`𝒮=1`$ results in the destruction of gas-liquid criticality by Coulomb interactions \[11(b)\].)

To ensure the stability of the critical point, one also needs Aqua and Fisher : (i) $`_0<_d^{max}`$, with $`_3^{max}=\frac{96}{11}\pi 2.77`$; (ii) $`R_N^2>0`$, which restricts $`_0`$ and $`\delta _J`$ to the interior of an ellipsoid with a vertex at $`\delta _J=_0=0`$, which, for $`d=3`$, is $`\frac{1}{72}\delta _J^2+[\frac{1}{72}\pi _0(R_0^2/a^2)]^2<R_0^4/a^4`$; and (iv) the absence of competing minima in $`\mathrm{\Lambda }_N(𝐤)`$, which is satisfied for sufficiently small $`\delta _J`$, specifically by $`\delta _J<1\frac{1}{12}\pi _0`$ in the BISM. The solution $`\lambda ^{}(\lambda )`$ of (22) then varies smoothly when $`\lambda 0`$ and (23) applies. By (20) criticality is restricted to $`\overline{h}=0`$ and occurs at $`k_BT_c=1/𝒥_d(0,\lambda _c^{})`$ and $`\rho _c=a^d=\frac{1}{2}\rho _{max}`$. For the BISM, we find $`T_cT_0/K_{bcc}`$, to lowest order in $`\delta _J`$ and $`_0`$, with $`K_{bcc}1.39`$ Joyce (1972). It transpires Aqua and Fisher  that $`T_c(\delta _J)`$ is a decreasing function of the asymmetry in accord with recent simulations of hard-core continuum electrolyte models \[6(a)\] that, however, contradict various approximate theories. Furthermore, a term varying as $`_0^{3/2}`$ (in $`d=3`$) appears Aqua and Fisher , in accord with Moreira et al. (1999) and in analogy with Kim and Fisher (2001).

As regards the density correlation lengths, (18) yields

$$\xi _{N,1}(T,\rho )=R_N\left[𝝀(T,\rho )\right]\left[j_0/\lambda (T,\rho )\right]^{1/2},$$
(26)
for all acceptable $`_0`$ and $`\delta _J`$; when $`\rho =\rho _c`$, this diverges as $`\xi _N^0/t^\nu `$. Furthermore, all higher moments \[see (4)\], including the “true” correlation length $`\xi _{N,\mathrm{}}`$ Fisher and Burford (1967), satisfy $`\xi _{N,p}/\xi _{N,1}1`$ when $`(T,\rho )(T_c,\rho _c)`$. For the BISM, with small $`_0`$ and $`\delta _J`$ we have $`\xi _N^0a/\pi K_{bcc}0.229a`$, close to the $`d=3`$, nearest neighbor Ising model value Fisher and Burford (1967).

By contrast, the near-critical charge correlation lengths depend radically on symmetry. In charge symmetric models, where $`B_{ZZ}^Z=1`$, it follows from (18) and (24) that the Stillinger-Lovett sum-rule (6) is valid for all fluid regimes including the critical point. However, the true charge screening length is given by

$$\xi _{Z,\mathrm{}}(T,\rho )=R_Z(T,\rho )[1+𝒪(_0^2)],$$
(27)
where, from (25) we find $`R_Z/\xi _D1`$ as $`\rho 0`$ whereas near criticality one has $`R_{Z,c}/\xi _{D,c}2\sqrt{T_0/T_c}`$; that yields $`R_{Z,c}/\xi _{D,c}2.36`$ for the BISM (for $`_0`$ and $`\delta _J`$ not too large). Furthermore, when $`t0`$, the screening length, $`\xi _{Z,\mathrm{}}(\rho _c,T)`$ gains, in general, a singular correction factor $`[1+c_{1\alpha }t^{1\alpha }]`$ Aqua and Fisher . Up to $`𝒪(_0)`$, the higher moments of $`S_{ZZ}`$ satisfy $`(\xi _{Z,p})^p\xi _DR_Z^{p1}`$.

On the other hand, in nonsymmetric cases $`B_{ZZ}^N`$ in (18) does not vanish : rather one has

$$B_{ZZ}^N(𝐤;𝝀)=4\lambda ^^2k^4a^4/S_d^2_0^2j_0^2[1+𝒪(k^2)]>0.$$
(28)
Consequently, all charge correlations become infected by the divergent density fluctuations controlled by $`\mathrm{\Lambda }_N(𝐤)`$. Nevertheless, because of the factor $`k^4`$, the Stillinger-Lovett relation (6) remains valid in the fluid regime except at criticality where it fails and we find Aqua and Fisher ; footnote

$$(\xi _{Z,1}/\xi _D)_c^2=1+w_c^2\lambda _c^^2=1+w_c^2c_\delta ^2\delta _J^2+\mathrm{},$$
(29)
where $`w^2=2a^2/S_d_0R_N^2j_0^2`$ and, recalling (23), we note that $`c_\delta [J_{\sigma \tau }]0`$ for the BISM. This critical point failure implies a breakdown of full screening that is necessarily associated with slow decay of certain ionic correlations Martin (1988). Indeed, when $`(T,\rho )(T_c,\rho _c)`$ the charge decay length $`\xi _{Z,\mathrm{}}`$ asymptotically approaches the density correlation length, $`\xi _{N,\mathrm{}}`$, and thus diverges as $`\xi _N^0/t^\nu `$ (for $`\rho =\rho _c`$).

However, the fourth charge correlation moment is given (except at criticality) by

$$\xi _{Z,2}^4(T,\rho )=\xi _D^2[R_Z^2\xi _{N,1}^2w^2\lambda ^^2],$$
(30)
so that $`|\xi _{Z,2}(\rho _c,T)|`$ diverges more weakly as $`1/t^{\nu /2}`$. Note also that on approaching criticality, $`\xi _{Z,2}^4`$ changes sign (with respect to the symmetric case); for small $`\delta _J`$ this crossover occurs in the BISM at $`t=t_\times 0.265\delta _J`$. More generally the higher moments in nonsymmetric systems satisfy $`\xi _{Z,p}^{2p}\xi _{N,\mathrm{}}^{2(p1)}\xi _{D,c}^2w_c^2\lambda _c^^2`$ leading to a hierarchy of critical exponents $`|\xi _{Z,p}|1/t^{\nu (11/p)}`$. Notwithstanding the divergence of the charge correlation length, $`\xi _{Z,\mathrm{}}\xi _N\mathrm{}`$, the charge-charge pair correlation function, $`G_{ZZ}(𝐫)`$, decays exponentially at $`(T_c,\rho _c)`$! Indeed on approach to criticality we obtain

$$G_{ZZ}(𝐫)2\delta _J^2\frac{T_0}{T_c}\frac{c_\delta ^2}{j_0^2}\frac{\xi _D^4}{R_N^2}\frac{e^{r/\xi _N}}{\xi _N^4(T,\rho )r}\frac{\xi _D^2}{R_Z^4}\frac{e^{r/R_Z}}{r},$$
(31)
to leading orders for $`d=3`$. At $`T_c`$ only the second term survives since the first vanishes as $`t^{4\nu }`$.

Finally, as regards the cross-correlations embodied in the charge-density structure factor $`S_{NZ}`$, we find $`S_{NZ}(𝐤=\mathrm{𝟎};T,\rho )0`$ except at $`(T_c,\rho _c)`$ where the value $`(\lambda ^^2\xi _D^2/j_0R_N^2)_c`$ is realized. Moreover, on defining moments in analogy to (5), one obtains

$$\xi _{NZ,p}^{2p}(T,\rho )(\lambda ^{}\xi _D^2/j_0R_N^2)\xi _{N,\mathrm{}}^{2p}(T,\rho ),$$
(32)
near criticality; of course, all these moments vanish identically in charge symmetric models since $`\lambda ^{}0`$.

In summary, we have analyzed a class of exactly soluble spherical models for 1:1 ionic systems and shown that the Coulomb interactions do not change the gas-liquid critical universality class—contrary to some suggestions Weingärtner and Schröer (2001); Stell (1995). The couplings between the charge correlations and the divergent critical density fluctuations Aqua and Fisher ; footnote  follow mainly from a remarkable structure-function decomposition, Eq. (18), that respects the Stillinger-Lovett (SL) sum rule (unlike Muratov (2000)). Our principal results are collected in Table 1 : they are broadly consistent with Ornstein-Zernike-based arguments advanced for hard-core continuum electrolytes Stell (1995). In charge-symmetric models density fluctuations are not directly coupled to two-point charge correlations which remain of short-range and obey SL near and at criticality; but in more realistic nonsymmetric systems the density fluctuations “infect” the charge correlations which hence exhibit the same diverging correlation length. Moreover, the SL rule is then violated at criticality Aqua and Fisher ; footnote  indicating an anomalous conducting state Martin (1988).

###### Acknowledgements.

The authors are grateful to F. Cornu, B. Jancovici, E.R. Smith and G. Stell for correspondence, and to Y. C. Kim for his interest. Support from the NSF (under grants CHE 99-81772 and 03-01101) and assistance to J.-N.A. from the French Ministry of Foreign Affairs under the Lavoisier Fellowship program, is gratefully acknowledged.


format: text

text:
# Reconstructing Trees from Subtree Weights

## 1 Introduction

The problem of reconstructing a graph from measurements of distances between certain nodes was first proposed by Hakimi and Yau  in 1965, and has since developed into a myriad of related questions arising from diverse applications such as phylogeny reconstruction and internet tomography. These problems all have in common the notion of a graph realization of a matrix. That is, if $`D`$ is a matrix whose rows and columns are indexed by a set $`X`$, then $`D`$ has a realization if there is a weighted graph $`G`$ whose node set contains $`X`$, and that satisfies $`d(u,v)=D(u,v)`$ where $`d(u,v)`$ is the distance between two nodes in the graph. In what follows we will assume that our matrices $`D`$ are symmetric and have zeros on the diagonal; in phylogenetics these are called dissimilarity matrices . A non-negative dissimilarity matrix that has a graph realization is called a distance matrix. The Hakimi-Yau problem is therefore:

###### Problem 1 (Hakimi-Yau).

Given a distance matrix on a set $`X`$, find a graph $`G`$ which is a realization of $`D`$ so that the sum of the edge lengths of $`G`$ is minimized.

The general problem is notoriously difficult , however the case when $`G`$ is restricted to be a tree (and $`X`$ corresponds to leaves of the tree) has been well understood. Distance matrices realized by trees are said to be tree metrics, and the main result is the classic tree-metric theorem :

###### Theorem (Tree-Metric Theorem).

Let $`D`$ be non-negative dissimilarity matrix on $`X`$ . Then $`D`$ is a tree metric on $`X`$ if and only if, for every four (not necessarily distinct) elements $`i,j,k,lX`$, two of the three terms in the following equation are equal and greater than or equal to the third:

$$D(i,j)+D(k,l),D(i,k)+D(j,l),D(i,l)+D(j,k)$$
(1)
Furthermore, the tree $`T`$ with leaves $`X`$ that realizes $`D`$ is unique.

The four point condition (1) is therefore a necessary and sufficient condition for a matrix to be realized by a tree.

The algorithmic question of how to construct a tree from a tree metric is particularly important for the reconstruction of phylogenetic trees from genomic sequences, because the tree-metric theorem suggests the approach of estimating pairwise distances between the sequences and then reconstructing the tree. Methods that reconstruct the correct unique tree given a tree-metric, are called consistent, and biologists are particularly interested in consistent methods that are able to reconstruct the correct tree topology even with inaccurate distance matrices. Numerous polynomial time consistent algorithms have been proposed, of which we mention the classic Buneman method  and the neighbor-joining method . The neighbor-joining algorithm (NJ) is very popular because it is fast and performs well in practice; we mention the Buneman construction because the proof of our main result is based on it.

In this paper we propose the following generalization of the Hakimi-Yau problem: An $`m`$-dissimilarity map is a map $`D:X^m`$ ($`X^m`$ denotes the $`m`$th Cartesian product of $`X`$) with $`D(x_1,\mathrm{},x_m)=D(x_{\pi (1)},\mathrm{},x_{\pi (m)})`$ for all permutations $`\pi S_m`$ and $`D(x,x,\mathrm{},x)=0`$. We say that a graph $`G`$ realizes $`D`$ if the node set of $`G`$ contains $`X`$ and for every $`x_1,\mathrm{},x_mX`$, the weight of the smallest subgraph in $`G`$ containing $`x_1,\mathrm{},x_m`$ is $`D(x_1,\mathrm{},x_m)`$. We call an $`m`$-dissimilarity map that is realizable an $`m`$-distance map.

###### Problem 2.

Given an m-distance map $`D`$ on a set $`X`$, find a graph $`G`$ which is a realization of $`D`$ so that the sum of the edge lengths of $`G`$ is minimized.

Our main result is a weak version of the tree-metric theorem for $`m`$-dissimilarity maps: we show that an $`m`$-dissimilarity map does determine the tree it comes from (as long as $`m`$ is small compared to the number of leaves) although we give no explicit criterion for an $`m`$-dissimilarity map to come from a tree. We also discuss the ramifications of our result for phylogenetic tree reconstruction, in particular the relationship between our reconstruction theorem and maximum-likelihood methods for phylogenetic trees.

## 2 Reconstructing Trees

Let $`T`$ be a (finite) tree, with a positive weight $`w(e)`$ assigned to each edge $`e`$. Let $`L(T)`$ denote the set of leaves of $`T`$. For any $`VL(T)`$ of leaves, let $`[V]`$ denote the smallest subtree of $`T`$ containing $`V`$. For $`T^{}`$ any subtree of $`T`$, let $`w(T^{})`$ be the sum of the weights of the edges of $`T^{}`$. The main result of this paper is

###### Theorem.

Let $`T`$ be a tree with $`n`$ leaves and no vertices of degree 2. Let $`m3`$ be an integer. If $`n2m1`$, then $`T`$ is determined by the set of values $`w([V])`$ as $`V`$ ranges over all $`m`$ element subsets of $`L(T)`$. If $`n=2m2`$, this is not true.

In other words, if $`m`$ is fixed and the number of leaves in a tree $`T`$ is sufficiently large, then $`T`$ is uniquely determined from the $`m`$-dissimilarity map corresponding to the weights of the subtrees on $`m`$ leaves.

We will engage in the following abuse of notation: when $`SL(T)`$ and $`v_1`$,…, $`v_rL(T)`$, we will write $`v_1\mathrm{}v_r`$ to denote $`\{v_1,\mathrm{},v_r\}`$ and we will write $`Sv_1\mathrm{}v_r`$ to mean $`S\{v_1,\mathrm{},v_r\}`$. We will also write $`w(V)`$ to mean $`w([V])`$.

Let $`T`$ be a tree and let $`i`$, $`j`$, $`k`$ and $`l`$ be distinct members of $`L(T)`$. We will say $`i`$ and $`j`$ *are opposite* $`k`$ and $`l`$ if $`[ijkl]`$ is of the following form: there are two (distinct) vertices $`v`$ and $`w`$ of $`T`$ such that $`[ijkl]`$ consists of five edge distinct paths: a path from $`i`$ to $`v`$, a path from $`j`$ to $`v`$, a path from $`v`$ to $`w`$, a path from $`w`$ to $`k`$ and a path from $`w`$ to $`l`$. We will denote this state of affairs by $`(i,j;k,l)`$ and we will denote the path from $`v`$ to $`w`$ by $`\gamma _{ijkl}`$. It is clear that $`\gamma _{ijkl}`$ is well defined; in phylogenetics it is known as the Buneman index of the split $`(i,j;k,l)`$. Finally, if $`S`$ is a set, $`\left(\genfrac{}{}{0pt}{}{S}{m}\right)`$ denotes the set of $`m`$ element subsets of $`S`$.

In order to prove the main theorem, we first show that if $`T`$ is a tree with no vertices of degree 2 and having $`n`$ leaves ($`n2m1`$, $`m3`$) then we can reconstruct the topology of $`T`$. We will rely on the well known result that $`T`$ can be recovered as an abstract graph (without determining the edge weights) by knowing the signs of the Buneman indices, i.e. for which $`i`$, $`j`$, $`k`$ and $`l`$ we have $`(i,j;k,l)`$. The following Lemma that shows that this data can be recovered from the values $`w([V])`$ as $`V`$ ranges over $`\left(\genfrac{}{}{0pt}{}{L(T)}{m}\right)`$.

###### Lemma.

Let $`i`$, $`j`$, $`k`$ and $`l`$ be distinct members of $`L(T)`$. Then $`(i,j;k,l)`$ iff there is an $`R\left(\genfrac{}{}{0pt}{}{L(T)\{i,j,k,l\}}{m2}\right)`$ such that

$$w(Rij)+w(Rkl)<w(Rik)+w(Rjl)=w(Ril)+w(Rjk).$$
(2)
###### Proof.

Let $`R\left(\genfrac{}{}{0pt}{}{L(T)\{i,j,k,l\}}{m2}\right)`$. Let $`\stackrel{~}{T}`$ be the tree that arises by contracting $`[R]`$ to a point. We will denote the images of $`i`$, $`j`$, etc. in $`T`$ by $`\stackrel{~}{i}`$, $`\stackrel{~}{j}`$, etc. We note that $`\stackrel{~}{R}`$ is a leaf of $`\stackrel{~}{T}`$. Now,

$$w(Rij)=w(\stackrel{~}{R}\stackrel{~}{i}\stackrel{~}{j})+w(R),$$

so (2) holds iff the corresponding statement holds in $`\stackrel{~}{T}`$.

If $`(\stackrel{~}{i},\stackrel{~}{j};\stackrel{~}{k},\stackrel{~}{l})`$ then clearly $`(i,j;k,l)`$. We claim that, conversely, if $`(i,j;k,l)`$ then there exists some $`R`$ such that $`(\stackrel{~}{i},\stackrel{~}{j};\stackrel{~}{k},\stackrel{~}{l})`$. To see this, let $`e`$ be an edge in $`\gamma _{ijkl}`$. Removing $`e`$ from $`T`$ divides $`T`$ into two trees, let $`L_1`$ and $`L_2`$ be the leaves of these trees. Now, $`|L(T)\{i,j,k,l\}|=n42m5`$ so either $`L_1\{i,j,k,l\}`$ or $`L_2\{i,j,k,l\}`$ has at least $`m2`$ members, without loss of generality suppose the former does. Then take $`R\left(\genfrac{}{}{0pt}{}{L_1\{i,j,k,l\}}{m2}\right)`$ and you will have $`eR`$ so $`(\stackrel{~}{i},\stackrel{~}{j};\stackrel{~}{k},\stackrel{~}{l})`$.

The previous two paragraphs reduce us to the case where $`|R|=1`$, that is, where $`m=3`$ and $`R=\{r\}`$ for some $`rL(T)`$. We may delete all leaves other than $`i`$, $`j`$, $`k`$, $`l`$ and $`r`$. Now the claim is reduced to the case where $`m=3`$ and $`n=5`$, and can be verified by checking it for all trees with five leaves. ∎

Remark: One can check that, if the subtree weights are modified by less that $`e/2`$, where $`e`$ is the weight of the smallest edge, the reconstructed tree will not be altered. This bound of $`e/2`$ is the same as for the classical case of $`m=2`$ .

We still need to show that we can recover the edge weights of $`T`$. Continue to assume $`T`$ has no vertices of degree 2, $`|L(T)|=n`$ and $`n2m1`$. By the Lemma, the values $`w(V)`$, $`V\left(\genfrac{}{}{0pt}{}{L(T)}{m}\right)`$, determine the graph of $`T`$, so we may assume that this is known.

Let $`e`$ be an edge of $`T`$. We first consider the case in which neither of the endpoints of $`e`$ is a leaf. Then we can find $`i`$, $`j`$, $`k`$ and $`l`$ in $`L(T)`$ such that $`(i,j;k,l)`$ and $`\gamma _{ijkl}=e`$ (here and at many points in the future, we use that we already know the graph of $`T`$). Moreover, using $`n42m5`$ as before, we can find $`R\left(\genfrac{}{}{0pt}{}{L(T)\{i,j,k,l\}}{m2}\right)`$ such that $`e[R]`$. Then

$$w(Rik)+w(Rjl)w(Rij)w(Rkl)=2w(e)$$

so we can determine $`w(e)`$.

Let $`vL(T)`$, let $`e_v`$ be the unique edge incident to $`v`$. Let us assume that we have already computed $`w(e)`$ for all $`eT`$ not of the form $`e_v`$. Then, for all $`V\left(\genfrac{}{}{0pt}{}{L(T)}{m}\right)`$, we can compute

$$\underset{vV}{}w(e_v)=w(V)\underset{\begin{array}{c}eV\\ ee_v\end{array}}{}w(e).$$

Now, let $`i`$ and $`j`$ be distinct members of $`L(T)`$. For any $`S\left(\genfrac{}{}{0pt}{}{L(T)\{i,j\}}{m1}\right)`$ we have

$$\underset{vSi}{}w(e_v)\underset{vSj}{}w(e_v)=w(e_i)w(e_j).$$

Thus, we can determine the $`w(e_v)`$ up to a common additive constant. We may determine that constant from $`w(V)`$ for any $`V\left(\genfrac{}{}{0pt}{}{L(T)}{m}\right)`$.

It remains to show that if $`n=2m2`$ it may not be possible to reconstruct the tree. Let $`T`$ be the following tree: the vertices of $`T`$ are known as $`v_1`$, …, $`v_n`$ and $`w_2`$, …$`w_{n1}`$. The edges of $`T`$ are of the following two forms: $`(v_{i1},v_i)`$ and $`(v_i,w_i)`$. We will set $`w_1=v_1`$ and $`w_n=v_n`$. Clearly, $`L(T)=\{w_1=v_1,w_2,\mathrm{},w_{n1},w_n=v_n\}`$. The edge weights may be chosen arbitrarily.

Let $`T^{}`$ be the same tree except that the edges $`(v_{m1},w_{m1})`$ and $`(v_m,w_m)`$ are deleted and replaced by $`(v_m,w_{m1})`$ and $`(v_{m1},w_m)`$. We place the edges of $`T`$ and those of $`T^{}`$ in bijection by making $`v_{m1}w_{m1}`$ correspond to $`v_mw_{m1}`$, $`v_mw_m`$ correspond to $`v_{m1}w_m`$ and pairing all other edges in the obvious way. Assign the weights to the edges of $`T^{}`$ that are assigned to the corresponding edges of $`T`$.

We claim that, for any $`V\left(\genfrac{}{}{0pt}{}{L(T)}{m}\right)=\left(\genfrac{}{}{0pt}{}{L(T^{})}{m}\right)`$, the same edges (using the above bijection) appear in $`[V]`$ and $`[V]^{}`$, where $`[V]^{}`$ denotes the minimal subtree of $`T^{}`$ containing $`V`$. To prove this, we consider divide the edges $`e`$ of $`T`$ into three types.

First, we could have $`e=(v_i,w_i)`$. Then $`e[V]`$ iff $`w_iV`$ and the same is true for $`[V]^{}`$. Secondly, we could have $`e=(v_{i1},v_i)`$ with $`im`$. Then $`e[V]`$ iff $`w_j`$ and $`w_kV`$ for some $`ji<i+1k`$. This also holds for $`[V]^{}`$.

So far, we have used the fact that $`|V|=m`$, the previous paragraph is correct for any $`VL(T)`$. We now consider the final case, $`e=(v_{m1},v_m)`$. Removing $`e`$ from $`T`$ divides $`L(T)`$ into two sets $`L_1`$ and $`L_2`$, each of size $`m1`$. As $`|V|=m`$, $`VL_1`$ and $`VL_2\mathrm{}`$ so $`e[V]`$. Similarly, $`e[V]^{}`$. ∎

Our main result shows that, when $`n`$ is large enough compared to $`m`$, we can reconstruct a tree from the weights of its $`m`$-leaf subtrees. However, if we are simply given an $`m`$-dissimilarity map $`D:\left(\genfrac{}{}{0pt}{}{[n]}{m}\right)`$, we do not know how to test whether this map comes from a tree.

When $`m=2`$, this is given by the tree metric theorem. When $`m`$ is larger than $`2`$, an obviously necessary condition is that, for every $`R\left(\genfrac{}{}{0pt}{}{[n]}{m2}\right)`$ and $`i`$, $`j`$, $`k`$ and $`l[n]R`$, two out of three of the following expressions must be equal to each other and greater than or equal to the third:

$$D(Rij)+D(Rkl),D(Rik)+D(Rjl),D(Ril)+D(Rjk).$$

Moreover, we can impose the combinatorial requirement that when we consider the above equation with the same $`(i,j,k,l)`$ and different $`R`$ and $`R^{}`$, that the same one of the three terms above is minimized. However, by counting dimensions, we can see that this condition is not adequate in any case except $`n=5`$, $`m=3`$.

## 3 The Tropical Analogy

In this section, we describe a connection between subtree weights and an area of algebraic geometry known as “tropical geometry”, and inquire whether the analogy can be made tighter. The basic reference for our discussions is , although we reverse the sign conventions of that paper to more closely match those occurring elsewhere in this one.

Let $`f=_{eE}f_{e_1\mathrm{}e_n}x_1^{e_1}\mathrm{}x_n^{e_n}`$ be a polynomial in $`n`$ variables, where the $`f_{e_1\mathrm{}e_n}`$ are nonzero. Define $`\mathrm{Trop}f`$ to be the subset of $`w=(w_1,\mathrm{},w_n)^n`$ such that, of the collection of numbers $`_{i=1}^ne_iw_i`$ where $`e`$ runs over $`E`$, the maximum occurs twice. If $`IK[x_1,\mathrm{},x_n]`$ is an ideal, set $`\mathrm{Trop}I=_{fI}\mathrm{Trop}f`$.

Now, consider the case of a polynomial ring whose variables are indexed by the $`m`$ element subsets of $`[n]`$, we will write these variables as $`p_S`$ for $`S\left(\genfrac{}{}{0pt}{}{[n]}{m}\right)`$. Let $`w^{\left(\genfrac{}{}{0pt}{}{n}{m}\right)}`$. The statement that the maximum of

$$w_{Rij}+w_{Rkl},w_{Rik}+w_{Rjl},w_{Ril}+w_{Rjk}$$

occurs twice precisely says that

$$w\mathrm{Trop}(p_{Rij}p_{Rkl}p_{Rik}p_{Rjl}+p_{Ril}p_{Rjk}).$$

So, if $`w`$ arises from the $`m`$-leaf subtree weights of a tree, the $`w\mathrm{Trop}f`$, where $`f`$ is any polynomial of the form $`p_{Rij}p_{Rkl}p_{Rik}p_{Rjl}+p_{Ril}p_{Rjk}`$, $`i<j<k<l`$. Such polynomials are called the *three term Plucker relations*. It is well known that all of these relations lie in the ideal of the Grassmanian $`G(m,n)`$.

In the case where $`m=2`$, it was shown in  that $`\mathrm{Trop}G(2,n)`$ is exactly the space of tree metrics. This raises several natural problems:

###### Problem 3.

Does the space of $`m`$-leaf subtree weights lie in $`\mathrm{Trop}G(m,n)`$?

(It can be shown that the two spaces are not equal: $`\mathrm{Trop}G(m,n)`$ has larger dimension.) Assuming the answer to the above problem is “yes”, and inspired by the bijection between tree metrics and points of $`\mathrm{Trop}G(2,n)`$, we can ask for more.

###### Problem 4.

Is there a map $`G(2,n)G(m,n)`$ with image $`X`$ such that $`\mathrm{Trop}X`$ is the space of $`m`$-leaf subtree weights?

A positive answer to the above problem is known in the case where $`m=3`$. Write a point of $`G(m,n)`$ as a matrix with $`n`$ rows and $`m`$-columns, considered up to the right action of $`GL_n`$. One can check that the following map $`Mat_{2\times n}Mat_{3\times n}`$ descends to a map $`G(2,n)G(3,n)`$:

$$\left(\begin{array}{cccc}x_{11}& x_{12}& \mathrm{}& x_{1n}\\ x_{21}& x_{22}& \mathrm{}& x_{2n}\end{array}\right)\left(\begin{array}{cccc}x_{11}^2& x_{12}^2& \mathrm{}& x_{1n}^2\\ x_{11}x_{21}& x_{12}x_{22}& \mathrm{}& x_{1n}x_{2n}\\ x_{21}& x_{22}& \mathrm{}& x_{2n}\end{array}\right)$$

This map takes a tree metric to twice the corresponding $`3`$-leaf subtree weight. We have not found such a “geometric lifting” for $`m>3`$.

## 4 Applications

The fundamental problem in phylogenetics is to reconstruct trees from sets of sequences related by an evolutionary tree. The sequences can be DNA or protein sequences, or more generally can encode the order of genes in a genome or other evolving features. Some of the most popular methods for reconstructing trees are distance based methods. Distance based methods begin by estimating pairwise distances between the sequences, thus leading to a dissimilarity map (although it need not be an actual tree-metric). A tree is then reconstructed from the dissimilarity map, and it is hoped that the topology of the tree is correct.

Distance-based method are typically based on maximum-likelihood estimates of the pairwise distances. Suppose that the sequences are labeled $`s^1,\mathrm{},s^n`$ and that position $`k`$ in the $`j`$th sequence is denoted by $`s_k^j`$. For a pair of sequences $`i,j`$ we assume that one of them, $`s^j`$ has a the $`k`$ position picked from a distribution $`q_{s_k}^i`$, and that the other is related by a multiplicative substitution process to the first sequence, i.e. the $`k`$th character in $`s^i`$ is distributed according to $`P(s_k^i|s_k^j,t)`$ where $`_bP(s_k^i|s_k^l,t_1)P(s_k^l|s_k^j,t_2)=P(s_kk^i|s_k^j,t_1+t_2)`$. Furthermore, we assume that the substitution process is reversible so that we can switch the indices $`i,j`$.

Then the pairwise distances are computed by

$$d_{ij}=argmax_t\left(\underset{k}{}q_{s_k}^jP(s_k^i|s_k^j,t)\right).$$

Since the terms $`q_{s_k}^j`$ do not depend on $`t`$ we can write this as

$$d_{ij}=argmax_t\left(\underset{k}{}P(s_k^i|s_k^j,t)\right).$$

When the number of sites is large the consistency of maximum likelihood implies that these estimates will converge to the true branch lengths in the tree (assuming that the probabilistic model is correct). Thus, distance methods based on ML pairwise distance estimates can be viewed as generating approximations of the actual ML tree.

In practice, the use of short sequences can lead to inaccurate estimates, especially for longer branch lengths, and this is a common source of error for methods such as neighbor joining . A number of solutions to this problem have been proposed: for example variants of neighbor joining exist that are less sensitive to long branch lengths . Ranwez and Gascuel have shown that long pairwise branch lengths can be corrected by considering ML estimates of distances using three taxa . Quartet methods such as quartet puzzling  attempt to reconstruct the tree from more reliable quartets rather than pairwise distances. However a major problem with quartet methods has been how to reconcile the different topologies of the quartets into one tree.

Our approach can be seen as generating a better approximation to the ML tree, by relying on more accurate $`m`$-tree weights rather than pairwise distance. By avoiding the need to reconcile diverse topologies, we avoid the difficulties of standard quartet methods. Furthermore, as $`m`$ increases, the splits can be more accurately identified and thus a more accurate tree reconstructed. Although the computational complexity of subtree weight reconstruction grows rapidly with $`m`$, it remains polynomial, and furthermore many key steps are trivially parallelizable.

## Acknowledgments

We thank Bernd Sturmfels for many comments which improved the manuscript. Lior Pachter was partially supported by a grant from the NIH (R01-HG02362-02).


text:
# Observation of disorder-induced weakening of electron-phonon interaction in thin noble metal films

## Abstract

We have used symmetric normal metal-insulator-superconductor (NIS) tunnel junction pairs, known as SINIS structures, for ultrasensitive thermometry in the temperature range 50 - 700 mK. By Joule heating the electron gas and measuring the electron temperature, we show that the electron-phonon (e-p) scattering rate in the simplest noble metal disordered thin films (Cu,Au) follows a $`T^4`$ temperature dependence, leading to a stronger decoupling of the electron gas from the lattice at the lowest temperatures. This power law is indicative e-p coupling mediated by vibrating disorder, in contrast to the previously observed $`T^3`$ and $`T^2`$ laws.

Although the interaction between conduction electrons and thermal phonons is elementary for many processes and phenomena at low temperatures, there are still relatively few experimental studies that conclusively support the theoretical description, particularly for typical disordered thin film samples. Several earlier results rou ; kansk ; urbina  indicated that even for disordered films, the temperature dependence for the electron-phonon (e-p) scattering rate $`1/\tau _{ep}`$ follows the power law expected for pure samples with coupling to longitudinal phonons only gant : $`1/\tau _{ep}T^3`$. These results confirmed the relation $`P=\mathrm{\Sigma }\mathrm{\Omega }(T_e^5T_p^5)`$ between heating power $`P`$ and electron and phonon temperatures $`T_e`$ and $`T_p`$ in a volume $`\mathrm{\Omega }`$, and it is widely used for thin film metallic samples at low temperatures ($`\mathrm{\Sigma }`$ is a material dependent parameter). However, the theory for disordered thin films schmid ; alt ; reiz ; serg  predicts that the scattering rate from vibrating disorder (impurities, boundaries etc.) is $`1/\tau _{ep}T^4`$ in the limit $`ql<1`$, where $`q`$ is the wavevector of the dominant thermal phonons and $`l`$ the electron mean free path. This leads to the relation

$$P=\mathrm{\Sigma }^{}\mathrm{\Omega }(T_e^6T_p^6),$$
(1)
a result that has not been widely confirmed. In fact, we are not aware of any observation of it in standard normal metal films like Cu, Al, Au etc., and some evidence exists only for strongly disordered ($`l1`$ nm) Ti, Hf ger  and Bi kom  films.

Here, we report the observation of disorder-weakened electron-phonon (e-p) scattering in ordinary evaporated Cu and Au thin films. We have measured the rate at which electrons in a normal metal wire overheat, when DC power is applied to it by Joule heating, at sub-Kelvin temperatures jenni . This technique has been shown rou ; kansk ; urbina  to give the energy-loss rate directly, in contrast to the temperature dependence of the weak localization resistance lin , which gives the dephasing rate depha . The overheating rate is determined by measuring the electron temperature $`T_e`$ directly with the help of symmetric normal metal-insulator-superconductor (NIS) tunnel junction pairs, known as SINIS structures. SINIS-thermometers have been shown row ; nah1 ; leivo  to be extremely sensitive thermometers, operating at the lowest experimentally achievable temperatures. Therefore, they are also candidates for ultrasensitive microbolometers Nahum ; Kuzmin  in the sub-Kelvin temperature range.

All the samples used in this work have two normal metal wires of length $``$ 500 $`\mu `$m, and width $``$ 300-400 nm, separated by a distance 2 $`\mu `$m and electrically isolated from each other, as shown in the SEM image \[Fig. 1(a)\]. They were fabricated by e-beam lithography and three-angle shadow-mask evaporation technique on thermally oxidized (oxide thickness 250 nm) Si substrates, with film thicknesses varying from 33 nm to 140 nm, corresponding to a measured $`l=`$ 24-53 nm. The deposition was done by e-beam evaporation in a UHV chamber with a growth rate $`12`$ Å/s.

The normal metal wires were connected to the measurement circuit by superconducting Al leads. One pair of leads forms SINIS tunnel junctions for each wire, and are used to measure the electron temperature of the normal metal wire. These tunnel junctions were formed by thermal oxidation of the Al films, yielding tunneling resistances $`R_T`$ 20-50 k$`\mathrm{\Omega }`$, typically. In contrast, the junctions connecting the lower wire in Fig. 1 to a voltage source are NS-junctions without tunneling barriers, and are used to heat the sample. Clean NS-junctions have a small electrical resistance compared to the residual low-temperature resistance of the wire, between 100 and 1500 $`\mathrm{\Omega }`$ for all the samples. For all heating voltages used in this paper, we have measured that the NS-junctions are biased within the superconducting gap $`\mathrm{\Delta }`$ of the leads. Then, the process of Andreev reflection can take place, making the junctions good thermal insulators despite being electrically conducting. This way we can achieve conditions in which the wire is uniformly Joule heated short . Moreover, since the wires are much longer than a typical electron-electron scattering length hug , the electrons in the wire have a well defined Fermi-distribution, and a temperature $`T_e`$. In addition, the effect of multiple Andreev reflections on the distribution is negligible for these wire lengths anne . Also, the thermal resistance of the tunnel junctions is estimated to be at least an order of magnitude larger than the thermal resistance due to the e-p coupling $`R_{ep}`$ at the temperature range of this experimentdragos , and can be neglected in the analysis.

All measurements were performed by current biasing the two SINIS thermometers and measuring their DC voltages simultaneously \[Fig 1(b)\] in a dilution refrigerator with a base temperature $`60`$ mK. All wiring connected to the sample was filtered at 4.2 K, to minimize the overheating by external noise. This was seen to be very critical for good measurements at the lowest temperatures, as we also performed measurements without the filtering, and observed significant overheating below 0.3 K. The SINIS thermometers were calibrated by varying the bath temperature ($`T_{bath}`$) of the refrigerator very slowly, to ensure the sample stage was in equilibrium with the bath. The temperature of the sample stage was measured with a calibrated Ruthenium Oxide thermometer.

Figure 2 shows an example of a calibration measurement. The theoretical points (red) were calculated numerically from the BCS theory. This calculation has essentially no free parameters, since the current bias $`I`$ is known, and $`R_T`$ and $`\mathrm{\Delta }`$ are determined independently from the I-V characteristics (not shown). The agreement with the data is good except at the very lowest temperatures, where a slight deviation can be seen below $`T_{bath}=`$0.1 K. This deviation could arise by at least two major mechanisms: (i) a component of leakage or noise current affects the measurement, and (ii) the electrons overheat at the low-$`T`$ range ($`T_e>T_{bath}`$). We have ruled out (i) by directly measuring the responsivities $`dV/dP`$ of the thermometers as a function of $`I`$ using a lock-in amplifier (Fig. 2 inset). The theoretical $`dV/dP`$ is a monotonically decreasing function of $`I`$. However, experimentally at low $`I`$ the responsivity deviates from theory, and we find a maximum. Thus, by setting the bias current above the maximum ($`I60`$ pA in Fig. 2 inset), where the BCS-theory is accurate, problem (i) can be avoided. Mechanism (ii), overheating by noise power $`P_{noise}`$ is an obvious explanation, since we observed a clear improvement with added filtering of the lines. Thus, at the lowest temperatures ($`<0.1`$ K) the SINIS thermometers start to saturate to a temperature $`T_e`$ determined by the absorbed noise power $`P_{noise}T_e^nT_p^n`$, where $`n=5,6`$ depending on the mechanism of e-p scattering involved. The correct $`T_e(V)`$ is therefore always given by the BCS-theory function, instead of the measured phenomenological $`V(T_{bath})`$ plot.

Using the calibrated SINIS thermometers, we then studied what happened when only the lower wire is directly heated by Ohmic dissipation at $`T_{bath}`$ 60 mK. Heating power $`P`$ was applied by slowly ramping a DC voltage across the wire, and determined by measuring the heating current and voltage directly in a 4-wire configuration. In all the samples studied, the temperature of the upper wire rises also, when the lower wire is heated jenni . This indirect heating can be either due to phonons emitted from the hot wire and backscattered, or by photons (thermal noise) coupling capacitively. Since we don’t know the relative contributions of these two channels, we only obtain an upper limit for the local phonon temperature fooot  $`T_p`$. However, the main conclusion is that all the data satisfy the condition $`T_e^nT_p^n`$ for powers $`n=5,6`$, and the error introduced by approximating Eq. (1) by $`P=\mathrm{\Sigma }^{}\mathrm{\Omega }T_e^6`$ is less than 4% (for $`n=5`$ 6%). Thus, analysis can proceed without the knowledge of $`T_p`$, and the slope of $`T_e`$ vs. $`P`$ in a log-log plot will directly give $`1/n`$. We also note that thermal relaxation by radiation into the leads sch  is estimated to be insignificant compared to the e-p scattering, due to the large volume of our samples.

In Fig. 3 we plot the electron temperatures in the heated wire vs. $`P`$ obtained from several sweeps for four different samples in log-log scale. Data for the thinner Cu and Au samples is shown in Fig. 3(a), whereas Fig. 3(b) plots the results for the thicker Cu samples. The agreement with $`n=6`$ is strikingly good for the thin Cu and Au samples, from $`0.1`$ pW to $`1`$ nW. The 84 nm thick Cu sample also agrees with $`n=6`$ at higher power, but the thickest Cu sample does not, and is consistent with $`n=5`$. The saturation of $`T_e`$ by $`P_{noise}`$ at the lowest $`P`$ is clearly visible for all the samples, and the effect seems to be stronger for the thicker Cu samples. This is most likely due to the changing resistance of the wire: the thicker wires have lower resistance approaching the characteristic impedance of the wiring, causing more absorption of $`P_{noise}`$.

To obtain a more detailed picture, we also plot the numerically computed logarithmic derivatives of the data vs. $`P`$ in Fig. 4. Even though numerical differentiation is sensitive to noise, we can still strengthen our case. Again, for the thinner samples $`n=6`$ is obviously more consistent than any other integer power. Some deviations start to appear above a few hundred pW, which are not fully understood at the moment. The thicker samples show the effect of $`P_{noise}`$ by a smooth increase of the derivative at low powers. However, the 84 nm thick sample does seem to develop a plateau at around $`n=6`$, whereas the thickest sample is more consistent with $`n=5`$ in the high power limit.

By determining the volumes of the normal metal wires accurately with AFM and SEM measurements, we can extract the parameters $`\mathrm{\Sigma }^{}`$ and $`\mathrm{\Sigma }`$ from the one parameter fits in Fig. 3. We get for the Cu samples $`\mathrm{\Sigma }^{}=2\times 10^{10}`$ W/K6m3 ($`t=33`$ nm), $`\mathrm{\Sigma }^{}=6\times 10^9`$ W/K6m3 ($`t=84`$ nm) and $`\mathrm{\Sigma }=3\times 10^9`$ W/K5m3 ($`t=140`$ nm), whereas for the Au sample $`\mathrm{\Sigma }^{}=6\times 10^{10}`$ W/K6m3. We note that the value of $`\mathrm{\Sigma }`$ in the thickest Cu sample is consistent with earlier studies Nahum , since it is a material parameter in the pure limit. However, theory serg  predicts that $`\mathrm{\Sigma }^{}`$ depends on the level of disorder, and thus if $`ql<1`$, each sample can have a different $`\mathrm{\Sigma }^{}`$. This is clearly the case in our experiment. Comparing the measured $`\mathrm{\Sigma }^{}`$ with the microscopic theory, we can estimate the transverse sound velocity $`c_t`$. We get $`c_t=1800`$ m/s and $`c_t=2700`$ m/s for the Cu wires $`t=33`$ nm and $`t=84`$ nm, respectively, and $`c_t=1200`$ m/s for the Au wire, a reasonable result. As the bulk longitudinal sound velocities in Cu and Au are about twice as large, we have indirect evidence that transverse modes are dominant for $`ql<1`$.

In conclusion, we have for the first time obtained clear evidence that the electron-phonon scattering rate scales with temperature as $`1/\tau _{ep}T^4`$ in disordered, evaporated Cu and Au thin films. This power law corresponds to electrons scattering from phonons mediated by vibrating disorder. In our measurement boundary scattering is likely to be significant, since $`lt`$. In contrast, e-p scattering in the presence of static disorder leads to $`1/\tau _{ep}T^2`$, a result that has been confirmed in many materials and samples lin . Our result has several practical consequences. Compared to a lower power dependence, it is harder to cool the electrons with cold phonons, i.e. the electron gas decouples from the lattice more strongly at the lowest temperatures. Direct electron cooling nah1 ; leivo  then becomes more important. On the other hand, a sensor based on the hot electron effect is even more sensitive, since the ultimate noise equivalent power of such a detector is proportional to $`1/R_{ep}^{1/2}`$. We stress that in order to obtain $`1/\tau _{ep}T^4`$ the sample needs to be a regular metal, have $`ql<1`$, contain little non-vibrating disorder and have 3D phonons coupled to electrons by the deformation potential. We believe most earlier experiments do not satisfy all these conditions (e.g. Ref. rou  has $`ql>1`$, Ref. yung  has a suspended GaAs substrate, Refs. kansk ; urbina ; ditusa  studied alloys and Ref. kivin  studied degenerately doped Si in the strong screening limit.)

We thank D.-V. Anghel, A. N. Cleland, J. P. Pekola, H. Pothier, A. Savin and A. Sergeev for discussions. This work was supported by the Academy of Finland under the Finnish Center of Excellence Program 2000-2005 project No. 44875, and by the projects No. 105258 and 205476 (TULE programme).


text:
# Thermodynamical Detection of Entanglement by Maxwell’s Demons

## I Introduction

Entanglement is a form of correlations between two or more quantum systems whose amount exceeds anything that can be obtained by the laws of classical physics. Bell was first to clarify the difference between these correlations by measuring statistical regularities between local measurements on two separated systems bell64 . However, even though it is now well established that quantum systems can be more correlated than classical ones, the central question is whether we can use these excess correlations to do something useful. There are many indications from the field of quantum information that entanglement can result in a computational speed up, nonetheless, there is no precise and proven link between the two at present. In this paper, we show that there is indeed a more basic relationship between entanglement and its utility in thermodynamics: We find a particular work-extracting scenario that reveals the difference between classical and quantum correlations.

There have been some papers on the work-extraction from correlated quantum states. For example, Refs. oppenheim02 ; zurek03  have analyzed the difference between globally and locally extractable work. It was shown in Ref. oppenheim02  that a global observer can extract more work from a pair of quantum systems than two local observers. In Ref. zurek03 , a similar difference is discussed in terms of “discord”.

Our goal here is to clarify the difference between classical and quantum correlations, using locally extractable work from a heat bath via a given state, without comparing it with globally extractable work. The expected result will be Bell-type inequalities, which witness entanglement terhal00 , written with locally observable thermodynamical quantities. We will present thermodynamical inequalities that are satisfied by all classically correlated states, but can be violated by entangled states. By classically correlated states, we mean separable states as in Ref. werner89 . Our results suggest a novel connection between the separability of a quantum state and thermodynamics. Metaphorically, Maxwell’s demons can violate the inequalities in an attempt to break the Second Law of thermodynamics with the excess work due to the non-classicality of entanglement, although they can never be successful.

## II Work-extraction scheme

Suppose that we have a two dimensional classical system, such as a “one-molecule gas” which can only be in either the right or the left side of a chamber. If we have full information about this molecule, i.e., we know its position with certainty, we can extract $`k_BT\mathrm{ln}2`$ of work out of a heat bath of temperature $`T`$ by letting the gas expand isothermally. If we have only partial information about the system, the extractable work becomes $`k_BT\mathrm{ln}2[1H(X)]`$, where $`H(X)`$ is the Shannon entropy and $`X`$ is a binary random variable representing the position of the molecule oppenheim02 ; szilard29 ; bennett82 ; vonneumann . For simplicity, we set $`k_BT\mathrm{ln}2=1`$ hereafter so that we can identify the amount of work with the amount of information in bits.

The same argument can be applied to quantum cases provided that we know the nature of projection operators $`\{P_0,P_1(=P_0^{})\}`$ employed to obtain the information. The corresponding Shannon entropy is $`H(p)=p\mathrm{log}_2p(1p)\mathrm{log}_2(1p)`$, where $`p=\mathrm{Tr}(P_0\rho )`$ and $`\rho `$ is the density matrix for the state. In order to extract work, we can store the measurement results in classical bits so that the same process as above can be applied. Or, equivalently, we can copy the information about the quantum state to an ancilla by using controlled-NOT (CNOT) operation with respect to the basis defined by projectors $`\{P_0,P_1\}`$, and use this ancilla to extract work after letting it dephase. A CNOT is a two-bit unitary operation, which flips one of the two bits, the target bit, if the other, the control bit, is in 1 and does nothing otherwise.

Let us now consider a bipartite correlated system, retained by Alice and Bob. Suppose a set of identically prepared copies of the system for which Alice chooses $`A_\theta =\{P_\theta ,P_\theta ^{}\}`$ and Bob chooses $`B_\theta ^{}=\{P_\theta ^{},P_\theta ^{}^{}\}`$ as bases of their measurements with $`\theta (\theta ^{})`$ representing the direction of the basis. Alice performs her measurement with $`A_\theta `$ and sends all ancillae containing results to Bob. Then, by analogy with the single molecule case, Bob can extract $`1H(B_\theta ^{}|A_\theta )`$ bits of work per pair on his side after compressing the information of his measurement outcomes, where $`H(X|Y)`$ is the Shannon entropy of $`X`$, conditional on the knowledge of $`Y`$.

When their system is in a maximally entangled state, such as $`|\mathrm{\Phi }^+=(|00+|11)/\sqrt{2}`$, $`H(A_\theta |B_\theta )`$ vanishes for all $`\theta `$, unlike any other forms of correlation for which $`H(A_\theta |B_\theta )`$ can take any value between 0 and 1. This means that we can extract more work from entangled pairs than from classically correlated pairs.

Figuratively speaking, demons, Alice and Bob, who share entangled states with each other, can outdo those who have only classically correlated ones in terms of the amount of extractable work. By demons we mean here any fictitious entities that manipulate microscopic objects using information available to them, in analogy with Maxwell’s demon demon . Their everlasting wish is to violate the Second Law of thermodynamics by extracting extra work from a heat bath thanks to entanglement, although this attempt turns out to be thwarted as we will see below.

The overall protocol to extract work from correlated pairs is depicted in Fig. 1. They first divide their shared ensemble into groups of two pairs to make the process symmetric with respect to Alice and Bob. For each group, they both choose a projection operator randomly and independently out of a set, $`\{A_1,A_2,\mathrm{},A_n\}`$ for Alice and $`\{B_1,B_2,\mathrm{},B_n\}`$ for Bob, just before their measurement. Then, Alice measures one of the two qubits in a group with the projector she chose and informs Bob of the outcome as well as her basis choice. Bob performs the same on his qubit of the other pair in the group. As a result of collective manipulations on the set of those groups for which they chose $`A_i`$ and $`B_j`$, they can extract $`2H(A_i|B_j)H(B_j|A_i)`$ bits of work per two pairs at maximum.

## III Thermodynamical separability criterion

Let us find a general description of correlations in terms of work to clarify the difference between classical and quantum ones. It turns out that it suffices to sum up all the work that can be obtained by varying the basis continuously over a great circle on the Bloch sphere, i.e., the circle of maximum possible size on a sphere (see Fig. 2). This is similar in approach to the chained Bell’s inequalities discussed in Ref. braunstein90 . The circle should be chosen to maximize the sum.

Let $`\xi _\rho (A_i,B_j)`$ denote the extractable work from two copies of bipartite system $`\rho `$ in the asymptotic limit when Alice chooses $`A_i`$ (and $`A_i^{}`$) as her measurement and work-extracting basis while Bob chooses $`B_j`$ (and $`B_j^{}`$). For a two-dimensional bipartite system, $`\xi `$ is given by

$`\xi _\rho (A_i,B_j)`$ $`:=`$ $`2H(A_i|B_j)H(B_j|A_i)`$ (1)
$`=`$ $`22H(A_i,B_j)+H(A_i)+H(B_j),`$
which is symmetric with respect to $`A_i`$ and $`B_j`$.

The quantity we consider is $`lim_n\mathrm{}1/(2n1)[_{k=1}^n\xi (A(\theta _k),B(\theta _k))+_{k=1}^{n1}\xi (B(\theta _k),A(\theta _{k+1}))]`$ for a state $`\rho `$ and we let $`\mathrm{\Xi }(\rho )`$ denote it as

$$\mathrm{\Xi }(\rho ):=\frac{1}{2\pi }_0^{2\pi }\xi _\rho (A(\theta ),B(\theta ))𝑑\theta ,$$
(2)
where $`\theta `$ is the angle representing the direction of measurement on the great circle. The great circle is the one that maximizes the integral, as mentioned above. Note that $`\mathrm{\Xi }(\rho )`$ represents the extractable work under local operations and classical communication, which is a standard framework to deal with entanglement in quantum information theory.

We now present an inequality that shows a connection between the thermodynamically extractable work and the separability of bipartite quantum systems.

Proposition. An inequality

$$\mathrm{\Xi }(\rho )\mathrm{\Xi }(|00)$$
(3)
is a necessary condition for a two-dimensional bipartite state $`\rho `$ to be separable, that is, $`\rho =_ip_i\rho _i^A\rho _i^B`$. The state $`|00`$ in the right-hand side (RHS) can be any pure product state $`|\psi \psi ^{}`$. We obtained the value of $`\mathrm{\Xi }(|00)`$ numerically as 0.8854 bits. We will refer to this inequality (3) as “thermodynamical separability criterion”.

Proof. Without loss of generality, all $`\rho _i^A`$ and $`\rho _i^B`$ can be assumed as pure states. The key point of the proof is that even if the information from the other side could always be used to specify the pure state component $`\rho _i^B`$ (or $`\rho _i^A`$) on his/her side, the average extractable work $`\mathrm{\Xi }(\rho )`$ is always not larger than $`\mathrm{\Xi }(|00)`$. This is because for any pure product state $`|\psi \psi ^{}`$, $`\mathrm{\Xi }(|\psi \psi ^{})\mathrm{\Xi }(|00)`$ with equality when both $`|\psi `$ and $`|\psi ^{}`$ are on the integral path for $`\mathrm{\Xi }`$. Thus, $`\mathrm{\Xi }^{pcs}(\rho )=_ip_i\mathrm{\Xi }(\rho _i^A\rho _i^B)_ip_i\mathrm{\Xi }(|00)=\mathrm{\Xi }(|00)`$, where $`\mathrm{\Xi }^{pcs}(\rho )`$ is the extractable work from $`\rho `$ when “pure component specification (pcs)” is possible. We show below that $`\mathrm{\Xi }(\rho )\mathrm{\Xi }^{pcs}(\rho )`$.

The conditional entropy in the definition of $`\xi _\rho (A,B)`$ can be written as $`H(B|A)=_{j=0}^1p_j^AH(p(B^0|A^j))`$, where $`p_j^A=\mathrm{Tr}[(A^jI)\rho ]=_ip_i\mathrm{Tr}(A^j\rho _i^A)`$ is the probability for Alice to obtain the outcome $`j`$ and $`A^j`$ is a projection operator for the outcome $`j`$ along the direction of $`\theta `$ note\_ent . Namely, $`A^0(=A^0(\theta ))`$ corresponds to $`A(\theta )`$ in Eq. (2), however, we do not write $`\theta `$ explicitly in this proof for simplicity. As the density operator for Bob after Alice obtained $`j`$ is $`\rho _{A^j}^B=(1/p_j^A)_ip_i\mathrm{Tr}(A^j\rho _i^A)\rho _i^B`$, $`H(B|A)`$ is given by

$$H(B|A)=\underset{j}{}p_j^AH\left(\underset{i}{}\frac{p_i}{p_j^A}\mathrm{Tr}(A^j\rho _i^A)\mathrm{Tr}(B^0\rho _i^B)\right).$$
(4)
On the other hand, if the pcs is possible, the corresponding entropy can be written as

$$H^{pcs}(B|A)=\underset{i}{}p_iH(\mathrm{Tr}(B^0\rho _i^B)).$$
(5)
By letting $`p_{ji}^A`$ denote $`\mathrm{Tr}(A^j\rho _i^A)`$ and noting $`p_j^A=_ip_ip_{ji}^A`$, we can have an inequality as

$`H(B|A)`$ $`=`$ $`{\displaystyle \underset{j}{}}p_j^AH\left({\displaystyle \underset{i}{}}{\displaystyle \frac{p_ip_{ji}^A}{p_j^A}}p_{0i}^B\right)`$ (6)
$``$ $`{\displaystyle \underset{i}{}}{\displaystyle \underset{j}{}}p_j^A{\displaystyle \frac{p_ip_{ji}^A}{p_j^A}}H(p_{0i}^B)`$
$`=`$ $`{\displaystyle \underset{i}{}}p_iH(p_{0i}^B)=H^{pcs}(B|A),`$
due to the concavity of Shannon entropy. As all $`p_{ji}^A`$ and $`p_{0i}^B`$ can be regarded as distinct, the equality in Eq. (6) holds when there exists only one pure component, i.e., $`p_k=1`$ for a certain $`k`$ and $`p_i=0`$ for $`ik`$. Similarly, $`H(A|B)H^{pcs}(A|B)`$. Hence, for all separable, or classically correlated, states $`\rho `$, $`\mathrm{\Xi }(\rho )\mathrm{\Xi }^{pcs}(\rho )`$ and thus $`\mathrm{\Xi }(\rho )\mathrm{\Xi }(|00)`$. $`\mathrm{}`$

The dashed lines in Fig. 3 show numerically plotted $`\mathrm{\Xi }(\sigma _{\mathrm{cl}.})`$ as a function of $`c_0`$, where $`\sigma _{\mathrm{cl}.}=c_0|0000|+c_1|\phi \phi \phi \phi |`$ is a classically correlated state with respect to two vectors, $`|0`$ and $`|\phi :=\mathrm{cos}(\phi /2)|0+\mathrm{sin}(\phi /2)|1`$ There are five dashed lines, each of which corresponds to $`\sigma _{\mathrm{cl}.}`$ with one $`\phi `$ out of the set $`\{0.2\pi ,0.4\pi ,\mathrm{},\pi \}`$. The near-horizontal one corresponds to $`\phi =0.2\pi `$, which gives a state “close” to $`|00`$. We can see that none of $`\mathrm{\Xi }(\sigma _{\mathrm{cl}.})`$ exceeds $`\mathrm{\Xi }(|00)`$, whose value is 0.8854 bits, as the above proposition claims. Also, above the threshold $`\mathrm{\Xi }(|00)`$, the extractable work from a (pure) entangled state is a monotonic function of the amount of entanglement vedral97 , taking its maximum when maximally entangled.

As the RHS of Eq. (3) represents the maximum amount of work obtainable from classically correlated states with our protocol, any excess of extractable work should be the manifestation of entanglement. Thus, violating the inequality (3), demons can exploit the extra work from entanglement, which is unavailable from classically correlated states.

Even if we choose a part of the great circle as the integral path of Eq. (2) without closing it, the inequality corresponding to Eq. (3) should be violated for states that are entangled strongly enough. This is because for a strongly entangled state $`|\varphi `$, $`\xi _{|\varphi }(A_\theta ,B_\theta )`$ is close to 2 for all $`\theta `$, while $`\xi _{|00}(A_\theta ,B_\theta )`$ is always less than 2 unless $`\theta `$ indicates $`|0`$. This also means that the violation criterion, i.e., the RHS of Eq. (3), depends on the range of the path in such a case.

We can also perform the integral in Eq. (2) over the whole Bloch sphere, instead of the great circle, to have another separability criterion. Then, Eq. (3) becomes

$$\mathrm{\Xi }_{BS}(\rho ):=\frac{1}{4\pi }_{BS}\xi _\rho (A,B)𝑑\mathrm{\Omega }\mathrm{\Xi }_{BS}(|00),$$
(7)
where $`BS`$ stands for the Bloch sphere and we obtained $`\mathrm{\Xi }_{BS}(|00)=0.5573`$ numerically. The proposition also holds for $`\mathrm{\Xi }_{BS}(\rho )`$ as there is no need to change the proof except that $`\mathrm{\Xi }_{BS}^{pcs}(\rho )`$ is always equal to $`\mathrm{\Xi }_{BS}(|00)`$ in this case. Let us now compute the value of $`\mathrm{\Xi }_{BS}(\rho _W)`$, where $`\rho _W=p|\mathrm{\Psi }^{}\mathrm{\Psi }^{}|+(1p)/4I`$ is the Werner state werner89 , to see the extent to which the inequality can be satisfied when we vary $`p`$. It has been known that Bell-CHSH inequalities chsh  are violated for $`p>1/\sqrt{2}=0.7071`$, while $`\rho _W`$ is inseparable iff $`p>1/3`$. A bit of algebraic calculations lead to $`\mathrm{\Xi }_{BS}(\rho _W)=(1p)\mathrm{log}_2(1p)+(1+p)\mathrm{log}_2(1+p)`$ and this is greater than $`\mathrm{\Xi }_{BS}(|00)`$ when $`p>0.6006`$. Therefore, the inequality (7) is significantly stronger than Bell-CHSH inequalities.

Since we have obtained the inequalities (3) and (7) without discussing the non-locality of quantum mechanics, they are different from Bell’s inequalities, but similar to them in the sense that they discriminate non-classical correlations from classical ones. With reference to Bell’s inequalities, the form of extractable work, Eq. (1), reminds us of the “information theoretic Bell’s inequalities” derived by Schumacher by defining the information distance using conditional entropies schumacher91 .

Schumacher obtained his inequalities from the triangle inequality for a metric. However, it is possible to derive the same inequalities directly from our definition of the extractable work, Eq. (1). The result becomes

$$\xi (A,B)+\xi (B,C)2+\xi (A,C),$$
(8)
with equality when $`H(A)=0`$ or $`H(C)=0`$. This is a direct consequence of Eq. (1) and the strong subadditivity of the Shannon entropy. From Eq. (8), we can obtain “chained” inequalities

$`\xi (A_1,B_1)+\xi (B_1,A_2)+\mathrm{}+\xi (A_n,B_n)`$
$`2(2n2)+\xi (A_1,B_n).`$ (9)
Note that the left-hand side of Eq. (III) becomes the same as that of Eq. (3) if we take bases $`A_1,\mathrm{},B_n`$ as those in Fig. 2, divide the sum by $`2n1`$, and let $`n`$ tend to infinity. However, the same procedure on the RHS gives $`2`$, thus Eq. (III) becomes a trivial inequality $`\mathrm{\Xi }(\rho )2`$. Hence, our inequality (3) is essentially independent of Bell-Schumacher inequalities and gives a stronger bound on $`\mathrm{\Xi }(\rho )`$ in the continuous limit.

## IV Analysis of demons’ attempt

Let us analyze how demons’ attempt to violate the Second Law of thermodynamics will end in failure. In order to discuss the Second Law, which states “there does not exist any cycle of a heat engine that converts heat to work without leaving any change in its environment,” we need to restore the initial state after extracting work and check the balance of work. The impossibility of breaking the Second Law by the protocol described above follows from the fact that the net work investment is always nonnegative, regardless of the direction of measurement/work extraction, thus, it is necessarily nonnegative after averaging over the great circle or the Bloch sphere.

Suppose that Bob performs measurement on his part and Alice extracts work on her side. The state after work extraction is $`\sigma =I/2|00|`$. If Bob’s outcome was 1, he can flip it with $`\sigma _x=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)`$ without energy consumption. Generically, unitary operations require no energy consumption as entropy stays constant with them. Let us consider first the case in which there was only classical correlation initially, as $`\rho ^{\mathrm{cl}.}=_ip_i\rho _i^A\rho _i^B`$. The simplest method to restore $`n`$ copies of this initial state from $`\sigma `$ is to make use of quantum data compression/decompression schumacher95 . To do this, they need $`nS(\rho ^{\mathrm{cl}.})`$ copies of $`I/2`$ and $`n[1S(\rho ^{\mathrm{cl}.})]`$ copies of the standard pure state, $`|0`$, where $`S(\rho )=\mathrm{Tr}\rho \mathrm{log}_2\rho `$ is the von Neumann entropy. Let them have the same number of copies of $`I/2`$ (See Fig. 4). Alice compresses $`n[1S(\rho ^{\mathrm{cl}.})/2]`$ copies of $`I/2`$ on her side isothermally to $`|0`$, consuming $`w_{\mathrm{con}}^A=1S(\rho ^{\mathrm{cl}.})/2`$ bits of work per qubit. On the other hand, Bob acquires $`w_{\mathrm{ext}}^B=S(\rho ^{\mathrm{cl}.})/2`$ bits of work per qubit by transforming $`nS(\rho ^{\mathrm{cl}.})/2`$ copies of $`|0`$ to $`I/2`$. They can restore $`n`$ copies of $`\rho ^{\mathrm{cl}.}`$ by decompressing the mixture of $`I/2I/2`$ and $`|00`$ globally without any work consumption.

When the initial state is entangled as $`|\psi ^{AB}=\alpha |00+\beta |11`$, the restoration process becomes simpler. Alice transforms her state $`I/2`$ into $`|0`$ by consuming one bit of energy to make $`|00`$. Then rotating Alice’s state to $`(\alpha |0+\beta |1)|0`$ unitarily and applying a global CNOT restore the initial entanglement. In either case, we also need to erase the information of Bob’s measurement outcome and this requires $`H(B(\theta ))`$ bits of work demon ; landauer .

Combining the work extracted before, we can now calculate the work investment $`W_{\mathrm{inv}}`$ to close the cycle: $`W_{\mathrm{inv}}^{\mathrm{cl}.}=w_{\mathrm{con}}^Aw_{\mathrm{ext}}^B+H(B(\theta ))[1H(A(\theta )|B(\theta ))]=H(A(\theta ),B(\theta ))S(\rho ^{\mathrm{cl}.})`$ bits of work for an initial state of $`\rho ^{\mathrm{cl}.}`$ and, similarly, $`W_{\mathrm{inv}}^{\mathrm{ent}.}=H(A(\theta ),B(\theta ))`$ bits for an entangled state, $`|\psi ^{AB}`$. These $`W_{\mathrm{inv}}`$ must be nonnegative in order for the Second Law not to be violated. It turns out that both $`W_{\mathrm{inv}}^{\mathrm{cl}.}`$ and $`W_{\mathrm{inv}}^{\mathrm{ent}.}`$ are indeed nonnegative due to the properties of the Shannon and von Neumann entropies and the effect of projective measurements.

## V Summary

We have devised a scenario in which two demons, Alice and Bob, can distill more work from entanglement than from classical correlation. We have cast this discrimination of correlations in the form of the thermodynamical separability criteria. Although we can re-derive Schumacher’s inequalities by considering a set of discrete basis of measurement, our inequalities are essentially different. Interestingly, our inequality (7) is more effective than Bell-CHSH inequalities, as well as Schumacher’s, in detecting inseparability of the Werner state. Lastly, our analysis of the energy balance after closing the thermodynamical cycle illustrates, quite expectedly, that the demons cannot violate the Second Law even with the excess work extracted from entangled states.

One important step we should make next is to devise a method to test the inequality experimentally, for example, by using NMR as proposed in Ref. lloyd97 . Also, it would be very interesting if we can find a connection between our inequalities and the non-locality of quantum mechanics.

## Acknowledgments

KM acknowledges financial support by Fuji Xerox. FM appreciates the warmth and hospitality of the quantum information group at Imperial College. VV is supported by the European Community, the Engineering and Physical Sciences Research Council, Hewlett-Packard and Elsag Spa.


text:
# There may be no Hausdorff ultrafilters

## 1. Introduction

For $`f\omega ^\omega `$ and an ultrafilter $`U`$ on $`\omega `$ define $`f(U)=\{X\omega :f^1(X)U\}`$. Let $`\mathrm{𝖥𝗍𝖮}`$ be the collection of all finite-to-one functions $`f\omega ^\omega `$.

###### Definition 1.

Let $`U`$ be an ultrafilter on $`\omega `$. We say that

1. $`U`$ is Hausdorff if for any two functions $`f,g\omega ^\omega `$, if $`f(U)=g(U)`$ then $`f\mathrm{}X=g\mathrm{}X`$ for some $`XU`$.
2. $`U`$ is weakly Hausdorff if for any two functions $`f,g\mathrm{𝖥𝗍𝖮}`$, if $`f(U)=g(U)`$ then $`f\mathrm{}X=g\mathrm{}X`$ for some $`XU`$.

It is easy to see that

1. Ramsey ultrafilters are Hausdorff.
2. $`q`$-points are weakly Hausdorff.
3. Weakly Hausdorff $`p`$-points are Hausdorff.

It is worth mentioning that the following appears as an exercise in .

###### Lemma 2.

If $`f(U)=U`$ then there exists $`XU`$ such that $`f(n)=n`$ for $`nX`$.

Therefore, if $`U`$ is not Hausdorff, then this is witnessed by two functions, both not one-to-one mod $`U`$.

The notion of a Hausdorff ultrafilters was reintroduced and studied by Mauro Di Nasso, Marco Forti and others in a sequence of papers (, ,  and ) in context of topological extensions. They used the name Hausdorff because Hausdorff ultrafilters are precisely those ultrafilters whose ultrapowers equipped with the standard topology are Hausdorff topological spaces. They asked whether the existence of a Hausdorff ultrafilter can be proved in $`\mathrm{𝖹𝖥𝖢}`$. We will show that, at least for ultrafilters on $`\omega `$, the answer is negative. However such ultrafilters (with various extra properties) may be constructed under from additional set theoretical assumptions (see ).

## 2. Construction of the model

In this section we will show how to build a model where there are no Hausdorff ultrafilters modulo the proofs of theorems 4 and 6 below.

###### Definition 3.

An ultrafilter $`U`$ is strongly non-Hausdorff if for every $`f\mathrm{𝖥𝗍𝖮}`$, $`f(U)`$ is not weakly Hausdorff.

###### Theorem 4.

Assume $`\mathrm{𝖢𝖧}`$. There exists a strongly non-Hausdorff $`p`$-point.

###### Definition 5.

, , . Let $`\mathrm{𝖭𝖢𝖥}`$ stand for the following statement:

for any ultrafilters $`U,V`$ on $`\omega `$ there exists $`h\mathrm{𝖥𝗍𝖮}`$ such that $`h(U)=h(V)`$.

###### Theorem 6.

There exists a proper forcing notion $`𝒫`$ such that

1. If $`𝐕\mathrm{𝖦𝖢𝖧}`$ then $`𝐕^𝒫2^\mathrm{}_0=\mathrm{}_2`$,
2. If $`U`$ is a $`p`$-point then $`𝐕^𝒫U`$ generates a $`p`$-point.
3. If $`U`$ is strongly non-Hausdorff filter then $`𝐕^𝒫U`$ generates a strongly non-Hausdorff filter.
4. $`𝐕^𝒫\mathrm{𝖭𝖢𝖥}`$.

###### Theorem 7.

Suppose that $`𝐕\mathrm{𝖦𝖢𝖧}`$. Then in $`𝐕^𝒫`$ there are no weakly Hausdorff ultrafilters. In particular, there are no Hausdorff ultrafilters in this model.

###### Proof.

Let $`U_0`$ be a strongly non-Hausdorff $`p`$-point in $`𝐕`$ given by theorem 4. By theorem 6, $`U_0`$ generates a strongly non-Hausdorff $`p`$-point in $`𝐕^𝒫`$, and $`𝐕^𝒫`$ satisfies $`\mathrm{𝖭𝖢𝖥}`$. So suppose that $`U`$ is an ultrafilter in $`𝐕^𝒫`$. By $`\mathrm{𝖭𝖢𝖥}`$ there exists $`h\mathrm{𝖥𝗍𝖮}`$ such that $`h(U)=h(U_0)`$. Since $`U_0`$ is strongly non-Hausdorff in $`𝐕^𝒫`$ it follows that $`h(U_0)`$ is not Hausdorff. On the other hand if $`U`$ was Hausdorff then the following lemma would imply that $`h(U)`$ is Hausdorff as well, a contradiction.

###### Lemma 8.

If $`U`$ is Hausdorff then $`h(U)`$ is also Hausdorff.

###### Proof.

Let $`f,g\mathrm{𝖥𝗍𝖮}`$ be such that $`f(h(U))=g(h(U))`$. It follows that there is $`XU`$ such that $`fh\mathrm{}X=gh\mathrm{}X`$. Thus $`f\mathrm{}h[X]=g\mathrm{}h[X]`$ and $`h[X]h(U)`$. ∎

## 3. A strongly non-Hausdorff ultrafilter

Let $`I\omega `$ be a finite set and let $`\mathrm{\Delta }=\{(n,n):n\omega \}`$. Denote by $`[I]^2=(I\times I)\mathrm{\Delta }`$. For a set $`X[I]^2`$ define

$$X_I=\mathrm{min}\left\{k:\{A_i,B_i:ik\}ikA_iB_i=\mathrm{}\text{ and }X\underset{ik}{}A_i\times B_i\right\}.$$

We will drop the subscript $`I`$ if it is clear from the context what it is.

###### Lemma 9.

1. $`[I]^2_I\mathrm{}`$ as $`|I|\mathrm{}`$.
2. $`XY_IX_I+Y_I`$,
3. if $`ZI`$ and $`X[I]^2`$, $`X_I>2`$, then either $`[Z]^2X_IX_I/21`$ or $`[IZ]^2X_IX_I/21.`$

###### Proof.

If (1) fails then there is $`k\omega `$ and sets $`\{A_j^n,B_j^n:n,jk\}`$ such that $`A_j^nB_j^n=\mathrm{}`$ for $`jk`$ and $`[n]^2=_{jk}A_j^n\times B_j^n`$. By compactness we get sets $`\{A_j^\omega ,B_j^\omega :jk\}`$ such that $`A_j^\omega B_j^\omega =\mathrm{}`$ for $`jk`$ and $`[\omega ]^2=_{jk}A_j^\omega \times B_j^\omega `$, which is not possible.

A more direct argument shows that the following strategy is optimal for covering $`[I]^2`$, when $`|I|`$ is a power of two. Write $`I=I_0I_1`$ of equal size and use $`I_0\times I_1`$ and $`I_1\times I_0`$ to cover part of $`I\times I`$. For the rest, that is $`(I_0\times I_0)(I_1\times I_1)`$ apply the same strategy by writing $`I_0=I_{00}I_{01}`$ and $`I_1=I_{10}I_{11}`$. The procedure terminates when squares have size $`2\times 2`$, that is after $`\mathrm{log}_2(|I|)1`$ steps. At that time we have used $`2+22+24+\mathrm{}+2\times 2^{\mathrm{log}_2(|I|)1}=2|I|2`$ rectangles. For $`I`$ of arbitrary size we get (by rounding down to the nearest power of two) that $`[I]^2_I|I|2`$.

(2) is obvious.

(3) Note that

$$\begin{array}{c}X_I\left([Z]^2[IZ]^2(Z\times (IZ))((IZ)\times Z)\right)X_I\hfill \\ \hfill [Z]^2X_I+[IZ]^2X_I+1+1.\end{array}$$

Thus

$$[Z]^2X_I+[IZ]^2X_IX_I2.$$

For $`I[\omega ]^{<\omega }`$ let $`\pi _1,\pi _2:[I]^2I`$ be projections onto first and second coordinate respectively.

###### Lemma 10.

Suppose that $`X[I]^2`$, and $`X_I>2`$. Then $`\pi _0(X)\pi _1(X)\mathrm{}`$.

###### Proof.

Suppose that $`\pi _0(X)=u`$ and $`\pi _1(X)=v`$. If $`uv=\mathrm{}`$ then $`X(u\times v)(v\times u)`$. Thus $`X_I2`$. ∎

Next we define functions $`f^0,g^0\mathrm{𝖥𝗍𝖮}`$ that will witness that ultrafilter $`U_0`$ that we are about to construct is not Hausdorff.

Let $`\{I_k,J_k:k\omega \}`$ be two sequences of disjoint consecutive intervals such that for $`k\omega `$,

1. $`[I_k]^2_{I_k}2^{2^k}`$,
2. $`|J_k|=|[I_k]^2|`$.

Bijection implicit in (2) allows us to define projections $`\pi _0^k,\pi _1^k:J_kI_k`$. Let $`f^0=_k\pi _0^k`$ and $`g^0=_k\pi _1^k`$. Note that $`f^0(x)g^0(x)`$ for any $`xJ_k=[I_k]^2`$, $`k\omega `$.

As a warm-up let us use these definitions to show the following:

###### Lemma 11.

Assume $`\mathrm{𝖢𝖧}`$. There exists a $`p`$-point that is not weakly Hausdorff.

###### Proof.

We will need the following easy observation:

###### Lemma 12.

If $`f,g\mathrm{𝖥𝗍𝖮}`$ and $`U`$ is an ultrafilter then the following conditions are equivalent:

1. $`f(U)g(U)`$,
2. $`f[X]g[X]=\mathrm{}`$ for some $`XU`$$`\mathrm{}`$

We will build an ultrafilter $`V_0`$ on the set $`_k[I_k]^2`$ which we identified with $`\omega `$. Let $`\{Z_\alpha :\alpha <\omega _1\}`$ be enumeration of $`[\omega ]^\omega `$.

We will build by induction a sequence $`\{X_\alpha :\alpha <\omega _1\}`$ so that

1. $`\beta <\alpha X_\alpha ^{}X_\beta `$,
2. $`X_{\alpha +1}Z_\alpha =\mathrm{}`$ or $`X_{\alpha +1}Z_\alpha `$ for all $`\alpha `$.
3. for every $`\alpha <\omega _1`$, $`f^0[X_\alpha ]g^0[X_\alpha ]\mathrm{}`$.
4. for every $`\alpha <\omega _1`$, $`lim\; sup_kX_\alpha J_k_{I_k}=\mathrm{}`$.

Let $`V_0=\{X:\alpha X_\alpha ^{}X\}`$. Note that the conditions (1) and (2) guarantee that $`V_0`$ is a $`p`$-point, and lemma 12 and (3) implies that $`f^0(V_0)=g^0(V_0)`$. Finally, (4) is the requirement that (by lemma 10) implies (3).

Successor step. Suppose that $`X_\alpha `$ is given. Find a strictly increasing sequence $`\{\mathrm{}_k:k\omega \}`$ such that the set $`A=\{k:X_\alpha J_k_{I_k}=\mathrm{}_k\}`$ is infinite. Let $`A_0=\{k:X_\alpha Z_\alpha J_k_{I_k}\mathrm{}_k/21\}`$ and $`A_1=\{k:(X_\alpha Z_\alpha )J_k_{I_k}\mathrm{}_k/21\}`$. By lemma 9(3), one of these sets, say $`A_0`$, is infinite. Let $`X_{\alpha +1}=_{kA_0}X_\alpha Z_\alpha J_k`$. The other case is the same.

Limit step. Given $`\{X_\beta :\beta <\alpha <\omega _1\}`$ let $`\{\beta _k:k\omega \}`$ be an increasing sequence cofinal in $`\alpha `$. By finite modifications we can assume that $`X_{\beta _{k+1}}X_{\beta _k}`$ for all $`k`$. Build by recursion a strictly increasing sequence $`\{u_k:k\omega \}`$ such that

$$kjki[u_k,u_{k+1})X_{\beta _j}J_i_{I_i}k,$$

and let

$$X_\alpha =\underset{k}{}\left(X_{\beta _k}\underset{i[u_k,u_{k+1})}{}J_i\right).$$

It is clear that $`X_\alpha `$ satisfies (1) and (4). ∎

Observe that $`\mathrm{𝖢𝖧}`$ was only needed in the limit step. If we do not require that that $`U`$ is a $`p`$-point then we have the following:

###### Theorem 13.

There exists an ultrafilter that is not weakly Hausdorff.

###### Proof.

As in lemma 11, we will build an ultrafilter on the set $`_k[I_k]^2`$. Let

$$=\{X\underset{k}{}[I_k]^2:\underset{k}{lim\; sup}XJ_k_{I_k}<\mathrm{}\}.$$

Note that $``$ is an ideal, and let $`U`$ be any ultrafilter orthogonal to $``$. Functions $`f^0,g^0`$ witness that $`U`$ is not Hausdorff. ∎

Proof of Theorem 4.

Now we are ready to construct a $`p`$-point ultrafilter $`U_0`$ whose all finite-to-one images are not weakly Hausdorff.

Let $`\{h_\alpha ,Z_\alpha :\alpha <\omega _1\}`$ be enumeration of $`\mathrm{𝖥𝗍𝖮}`$ and $`[\omega ]^\omega `$ respectively. We will build by induction sequences $`\{f^\alpha ,g^\alpha :\alpha <\omega _1\}`$, $`\{X_\alpha :\alpha <\omega _1\}`$ so that

1. $`\beta <\alpha X_\alpha ^{}X_\beta `$
2. $`X_{\alpha +1}Z_\alpha =\mathrm{}`$ or $`X_{\alpha +1}Z_\alpha `$ for all $`\alpha `$.
3. for every $`\alpha `$, $`f^{\alpha +1},g^{\alpha +1}`$ witness that $`h_\alpha (U_0)`$ is not Hausdorff, where $`U_0=\{X\omega :\alpha X_\alpha ^{}X\}`$.
4. $`\beta \alpha \beta f^{\beta +1}h_\beta [X_\alpha ]g^{\beta +1}h_\beta [X_\alpha ]\mathrm{}`$.

As before, (1) and (2) guarantee that $`U_0`$ is a $`p`$-point, and (3) implies that $`U_0`$ is strongly non-Hausdorff, and (4) is a specific form of (3). Note that at the limit stages we only have to preserve the induction hypothesis. At the successor step we will first define an auxiliary function $`e_{\alpha +1}`$, and put $`f^{\alpha +1}=f^0e_{\alpha +1}:h_\alpha [X_\alpha ]\omega `$ and $`g^{\alpha +1}=g^0e_{\alpha +1}:h_\alpha [X_\alpha ]\omega `$. In other words, $`f^{\alpha +1},g^{\alpha +1}`$ are copies of $`f^0,g^0`$ on the image of $`X_\alpha `$ via $`e_{\alpha +1}h_\alpha `$.

Therefore we need to clarify condition (3) by imposing conditions on $`e_\alpha `$ and specifying the induction hypothesis.

###### Definition 14.

Let us say that a finite set $`YX_\alpha `$ is a $`(n,\beta ,\alpha )`$-witness if there exists $`k\omega `$ such that $`e_{\beta +1}h_\beta [Y]J_k_{I_k}n`$.

To satisfy (3), we demand that for $`\beta <\alpha <\omega _1`$,

1. $`lim\; sup_ke_{\beta +1}h_\beta [X_\alpha ]J_k_{I_k}=\mathrm{},`$ or equivalently
2. $`nY[X_\alpha ]^{<\omega }Y\text{ is a }(n,\beta ,\alpha )\text{-witness}`$.

Limit step.

Suppose that $`\{X_\beta :\beta <\alpha \}`$ are defined and $`\alpha `$ is a limit ordinal. Let $`\{\beta _k:k\omega \}`$ be an increasing sequence cofinal in $`\alpha `$, and let $`\{\gamma _k:k\omega \}`$ be an enumeration of $`\alpha `$ such that $`\gamma _j\beta _k`$ for $`jk`$. Without loss of generality we can assume that $`X_{\beta _n}X_{\beta _m}`$ for $`nm`$.

Build by recursion a strictly increasing sequence $`\{u_k:k\omega \}`$ such that

$$kl,jki[u_k,u_{k+1})e_{\gamma _l+1}h_{\gamma _l}[X_{\beta _j}]J_i_{I_i}k,$$

and let

$$X_\alpha =\underset{k}{}\left(X_{\beta _k}\underset{i[u_k,u_{k+1})}{}J_i\right).$$

It is clear that $`X_\alpha `$ satisfies (1) and (4).

Successor step.

Suppose that $`X_\alpha `$ satisfying (4) is already defined and we want to define $`X_{\alpha +1}`$ and $`e_{\alpha +1}`$ satisfying (2) and (5). Recall that by the induction hypothesis, for $`\beta <\alpha `$,

$$nY[X_\alpha ]^{<\omega }Y\text{ is a }(n,\beta ,\alpha )\text{-witness}.$$

Let $`\{\beta _k:k\omega \}`$ be an enumeration of $`\alpha `$. Find a sequence $`\{E_k:k\omega \}`$ of consecutive intervals such that

1. $`kjkh_\alpha ^1(E_k)`$ contains a $`(k,\beta _j,\alpha )`$-witness.
2. $`kE_kh_\alpha [X_\alpha ]\mathrm{}`$.

Let $`e_{\alpha +1}(j)=kjE_k`$ for $`j\omega `$. Condition (2) implies that $`e_{\alpha +1}h_\alpha [X_\alpha ]=\omega `$. In particular, either $`lim\; sup_ke_{\alpha +1}h_\alpha [Z_\alpha X_\alpha ]J_k_{I_k}=\mathrm{},`$ or $`lim\; sup_ke_{\alpha +1}h_\alpha [X_\alpha Z_\alpha ]J_k_{I_k}=\mathrm{}`$. Let $`X_{\alpha +1}`$ be the appropriate set. It remains to check that for $`\beta \alpha `$, $`lim\; sup_ke_{\beta +1}h_\beta [X_{\alpha +1}]J_k_{I_k}=\mathrm{}.`$ If $`\beta =\alpha `$ it follows immediately from the definition of $`X_{\alpha +1}`$, so suppose that $`\beta =\beta _j<\alpha `$.

Let $`me_{\alpha +1}h_\alpha [X_{\alpha +1}]j`$ and note that $`(e_{\alpha +1}h_\alpha )^1(m)`$ contains a $`(m,\beta _j,\alpha )`$-witness. It follows that $`lim\; sup_ke_{\beta +1}h_\beta [X_{\alpha +1}]J_k_{I_k}=\mathrm{},`$ which finishes the construction.

## 4. Forcing

Since known models for $`\mathrm{𝖭𝖢𝖥}`$ are obtained by countable support iteration we will look for a proper forcing notion $``$ such that the iteration of $``$ has the required properties.

Suppose that $``$ is a proper forcing notion. $``$ preserves non-meager sets if for every countable elementary submodel $`N𝐇(\chi )`$ containing $``$, a condition $`pN`$ and a Cohen real $`c`$ over $`N`$ there exists $`qp`$ such that $`q`$ is $`(N,)`$ generic and $`q_{}c\text{ is Cohen over }N[\dot{G}].`$

By , 6.3.16 this is equivalent to the property $`^{\text{Cohen}}`$ defined in .

Let $``$ be a proper forcing notion such that:

1. $``$ preserves $`p`$-points,
2. $``$ preserves non-meager sets, that is it preserves $`^{\text{Cohen}}`$.

Let $`𝒫=_{\omega _2}`$ be the countable support iteration of $``$ of length $`\omega _2`$. We have the following:

1. $`𝒫`$ preserves $`p`$-points (see  or  6.2.6),
2. $`𝒫`$ preserves non-meager sets (, 6.3.20).

Recall that if $``$ is either Blass-Shelah forcing from  or Miller superperfect forcing, then $`𝒫`$ has the above properties (7.3.46 and 7.3.48 of ) and $`𝐕^𝒫\mathrm{𝖭𝖢𝖥}`$,  or . Therefore the following theorem concludes the proof of theorem 6.

###### Theorem 15.

Suppose that $`𝒫`$ is a proper forcing that preserves non-meager sets and $`U_0𝐕`$ is a strongly non-Hausdorff ultrafilter defined earlier. Then

$$𝐕^𝒫U_0\text{ generates a a strongly non-Hausdorff filter}.$$

###### Proof.

Clearly, $`U_0`$ may not generate an ultrafilter in the extension, for example when $`𝒫`$ is Cohen forcing.

Let $`𝐂`$ be the Cohen forcing interpreted as adding a function $`c\mathrm{𝖥𝗍𝖮}`$. Specifically, the conditions are finite sequences of consecutive intervals $`\{I_k:k<n\}`$ and $`c(i)=kiI_k`$.

###### Lemma 16.

Let $`c`$ be Cohen reals over $`𝐕`$. Then for every $`h𝐕\mathrm{𝖥𝗍𝖮}`$, $`h(U_0)`$ is not Hausdorff as witnessed by $`f^h=f^0c`$ and $`g^h=g^0c`$.

###### Proof.

This is quite easy. Given $`s=\{L_k:k<n\}𝐂`$, $`X=X_\alpha U_0`$ we extend $`s`$ by adding an interval $`L_n`$ so large that $`L_n(e_{\alpha +1})^1(k)`$ for some $`k>n`$. That means that $`f^0c`$ and $`g^h=g^0c`$ agree with $`f^0e_{\alpha +1}`$ and $`g^0e_{\alpha +1}`$ on long enough segments to witness that $`f^0c[X]g^0c[X]\mathrm{}.`$

Let $`\dot{h}`$ be a $`𝒫`$-name for an element of $`\mathrm{𝖥𝗍𝖮}`$. Let $`N𝐇(\chi )`$ be a countable submodel containing $`U_0,\dot{h},p,𝒫`$ and let $`c𝐕\mathrm{𝖥𝗍𝖮}`$ be a Cohen real over $`N`$. Since $`𝒫`$ preserves non-meager sets there is $`qp`$ which is $`(N,𝒫)`$ generic and $`q_𝒫c\text{ is Cohen over }N[\dot{G}].`$ In particular, by lemma 16,

$$q_𝒫\dot{h}(U_0)\text{ is not Hausdorff as witnessed by }f^0c\text{ and }g^0c\text{}$$

By elementarity, it means that $`𝐕^𝒫h(U_0)\text{ is not Hausdorff.}`$. ∎

Acknowledgements: We would like to thank Mauro Di Nasso and Marco Forti for introducing us to the problem, and many helpful comments concerning the draft versions of this paper.