text:
# STRING VERSUS EINSTEIN FRAME IN AdS/CFT INDUCED QUANTUM DILATONIC BRANE-WORLD UNIVERSE

## I Introduction

Brane-worlds are alternative to the standard Kaluza-Klein compactification. They naturally lead to the following nice features of mutli-dimensional theory like trapping of 4d gravity on the brane , resolution of hierarchy problem and possibly resolution of cosmological constant problem. Different aspects of brane-world cosmology (for very incomplete list of references see ) are under very active investigation.

The essential element of original brane-world models is the presence in the theory of two free parameters (bulk cosmological constant and brane tension, or brane cosmological constant). These parameters are fine-tuned (up to some extent) in order to construct the successful classical brane-world. This is most standard prescription which may be not completely satisfactory if one wishes to have the dynamical mechanism of brane tension origin.

From another side, one can fix the classical action on AdS-like space from the very beginning with the help of surface terms added in accordance with AdS/CFT correspondence. Such terms should make the variational procedure to be well-defined and also they should eliminate the leading divergence of the action. Brane tension is not considered as free parameter anymore but it is fixed by the condition of finiteness of spacetime when brane goes to infinity. In this case, as parameters are fixed the consistent brane-world scenario is impossible, as a rule. However, other parameters may improve the situation when quantum effects are taken into account. Taking quantum CFT (including quantum gravity!) on the brane one adds its contribution (the corresponding conformal anomaly induced effective action) to the total action. As a result, it changes the brane tension, the quantum induced brane-world occurs as it has been discovered in refs.. Actually, this represents the embedding of warped compactification (brane-worlds) to AdS/CFT correspondence, hence one gets AdS/CFT induced quantum brane-worlds  where 4d boundary may be flat or de Sitter or Anti-de Sitter spacetime. This is clearly the dynamical mechanism to get curved brane-world. It is easily generalized for the presence of non-trivial dilaton, i.e. AdS/CFT induced quantum dilatonic brane-worlds occur. In other words, brane-worlds are the consequence of the presence of quantum fields on the brane in accord with AdS/CFT set-up. Moreover, such induced dilatonic brane-worlds are even more related with AdS/CFT correspondence as 5d dilatonic gravity represents the bosonic sector of 5d gauged supergravity (special parametrization). Even more, the dynamical determination of 4d dilaton occurs.

In the study of quantum induced brane-worlds, in the same way as for any other dilatonic gravity the following question appears: which frame to work with is the physical one? There are two convenient frames: string (or Jordan) one where scalar curvature explicitly couples with dilaton and Einstein frame where scalar curvature does not couple with dilaton. Basically speaking, one should expect that results obtained in these two frames are not equivalent.

Indeed, in QFT the choice of different variables and (or) form of action corresponds to different parametrizations. QFT results are parametrization dependent, only S-matrix is gauge and parametrization independent. (Even the quantization procedure (for review, see ) is parametrization dependent.) As usually the consideration is one-loop ,one should expect in many cases the explicit parametrization dependence. Moreover, it is known that even for classical dilatonic gravity the (singular) solution may exist in only one parametrization. Hence, the question of frame dependence should be carefully analyzed for all solutions at hands. This is the main purpose of the present work: to compare string frame quantum induced dilatonic brane-worlds with their analogs in Einstein frame.

In the next section as the simple example, 4d dilatonic (Brans-Dicke) theory with large $`N`$ quantum spinor corrections is considered. In the Einstein frame where spinor is dilaton coupled one the de Sitter Universe solution with decaying dilaton exists. Working with the same theory in string (Jordan) frame where spinor is getting minimal, one finds that above solution does not exist. Hence, it is shown that two frames in 4d dilatonic gravity with quantum corrections are not equivalent.

In third section we consider 5d dilatonic gravity action with 4d boundary term induced by conformal anomaly of brane, dilaton coupled spinor. Explicit examples of de Sitter, flat and Anti-de Sitter dilatonic branes are constructed in Einstein frame. The dynamical mechanism to determine the dilaton on the brane is presented. In section four the same investigation is done in string frame. Brane spinor is now minimal. The same AdS/CFT induced quantum brane-worlds are proven to exist. Hence, for quantum corrected cosmological dilatonic brane-worlds one has the equivalency of string and Einstein frames.

In fifth section the equivalency of string and Einstein frames is demonstrated for number of classical dilatonic brane-world black holes. In section six some remarks on massive graviton modes around dilatonic AdS4 brane are made. The role of brane quantum corrections for massive graviton modes is clarified. Brief summary and some outlook are given in final section.

## II Jordan and Einstein frames for 4d quantum corrected dilatonic gravity

In the study of dilatonic gravities the interesting question appears: which frame among few possible ones is the physical one? Basically speaking, there are two convenient frames to work with: string (or Jordan) frame and Einstein frame. These two are related by conformal transformation. The best known example is provided by the standard Brans-Dicke theory (with matter). The 4-dimensional action in the Jordan frame is:

$$S_{BD}=\frac{1}{16\pi }d^4x\sqrt{g}\left[\varphi R\frac{\omega }{\varphi }(_\mu \varphi )(^\mu \varphi )\right]+S_M,$$
(1)
where $`\varphi `$ is the Brans-Dicke (dilaton) field with $`\omega `$ being the coupling constant and $`S_M`$ is the matter action.

Performing the following conformal transformation and a redefinition of the scalar field

$$\stackrel{~}{g}_{\mu \nu }=G\varphi g_{\mu \nu },\stackrel{~}{\varphi }=\sqrt{\frac{2\omega +3}{16\pi G}}\mathrm{ln}\left(G\varphi \right),\mathrm{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}2}\omega +3>0.$$
(2)
one gets the action in the Einstein frame

$$S=d^4x\sqrt{\stackrel{~}{g}(x)}\left[\frac{\stackrel{~}{R}}{16\pi G}\frac{1}{2}(\stackrel{~}{}_\mu \stackrel{~}{\varphi })(\stackrel{~}{}^\mu \stackrel{~}{\varphi })+\mathrm{exp}(A\stackrel{~}{\varphi })L_M(\stackrel{~}{g})\right],$$
(3)
where $`A=8\sqrt{\frac{\pi G}{2\omega +3}}`$. It is expected that these two actions (at least for regular solutions) should lead to equivalent results. However, the explicit consideration shows that it is not always so (for a review, see ). That is why it was argued in ref. that it is Einstein frame which is physical one. Of course, such state of affairs is not satisfactory.

In quantum field theory the choice of different variables corresponds to different parametrizations. It is known that generally speaking it leads to parametrization dependent results: it is only S-matrix should be the same in different parametrizations. Of course, this should be true only in complete theory where account of all loops is taken. As usually the consideration is one-loop, one should expect parametrization dependence already at one-loop.

Let us consider the explicit example in Einstein frame where quantum corrections are taken into account. As matter Lagrangian we take the one associated with $`N`$ massless (Dirac) spinors, i.e. $`L_M=_{i=1}^N\overline{\psi }_i\gamma ^\mu _\mu \psi ^i`$. There is no problem to add other types of matter (say scalar or vector fields). The above choice is made only for the sake of simplicity.

We shall make use of the EA formalism (for an introduction, see ). The corresponding 4d anomaly–induced EA for dilaton coupled scalars, vectors and spinors has been found in Refs. .

Hence, starting from the theory with the action (no classical background spinors)

$$S=d^4x\sqrt{g}\left[\frac{R}{16\pi G}\frac{1}{2}(_\mu \varphi )(^\mu \varphi )+\mathrm{exp}(A\varphi )\underset{i=1}{\overset{N}{}}\overline{\psi }_i\gamma ^\mu _\mu \psi ^i\right],$$
(4)
we will discuss FRW type cosmologies

$$ds^2=dt^2+a(t)^2dl^2,$$
(5)
where $`dl^2`$ is the line metric element of a 3-dimensional flat space.

The computation of the anomaly–induced EA for the dilaton coupled spinor field has been done in , and the result, in the non-covariant local form, reads:

$`W={\displaystyle }d^4x\sqrt{\overline{g}}\{b\overline{F}\sigma _1+2b^{}\sigma _1[\overline{\mathrm{}}^2+2\overline{R}^{\mu \nu }\overline{}_\mu \overline{}_\nu {\displaystyle \frac{2}{3}}\overline{R}\overline{\mathrm{}}+{\displaystyle \frac{1}{3}}(\overline{}^\mu \overline{R})\overline{}_\mu ]\sigma _1`$ (7)
$`+b^{}\sigma _1(\overline{G}{\displaystyle \frac{2}{3}}\overline{\mathrm{}}\overline{R}){\displaystyle \frac{1}{18}}(b+b^{})[\overline{R}6\overline{\mathrm{}}\sigma _16(\overline{}_\mu \sigma _1)(\overline{}^\mu \sigma _1)]^2\},`$
where $`\sigma _1=\sigma +A\varphi /3`$, the square of the Weyl tensor is given by $`F=R_{\mu \nu \rho \sigma }R^{\mu \nu \rho \sigma }2R_{\mu \nu }R^{\mu \nu }+\frac{1}{3}R^2`$ and Gauss-Bonnet invariant is $`G=R_{\mu \nu \rho \sigma }R^{\mu \nu \rho \sigma }4R_{\mu \nu }R^{\mu \nu }+R^2`$. For Dirac spinors $`b=\frac{3N}{60(4\pi )^2}`$, $`b^{}=\frac{11N}{360(4\pi )^2}`$.

Then we find the following Einstein frame, quantum-corrected solution whose metric is expressed in Jordan frame as

$`ds_J^2`$ $`=`$ $`a_J^2(\eta )\left(d\eta ^2+dl^2\right)`$ (8)
$`a_J^2(\eta )`$ $`=`$ $`\mathrm{e}^{\frac{\varphi }{\sqrt{\frac{2\omega +3}{16G}}}}a^2(\eta )`$ (9)
$`=`$ $`a_0\eta ^{2\zeta }`$ (10)
$`\zeta `$ $``$ $`{\displaystyle \frac{1}{2H_1}}\sqrt{{\displaystyle \frac{16\pi G}{2\omega +3}}}+1`$ (11)
$`=`$ $`{\displaystyle \frac{1}{\sqrt{2\omega +3}\left\{\frac{3}{16}\sqrt{2\omega +3}\pm \sqrt{\frac{9}{256}(2\omega +3)\frac{1}{6}}\right\}}}+1`$ (12)
$`=`$ $`{\displaystyle \frac{1}{8}}\sqrt{{\displaystyle \frac{81}{64}}{\displaystyle \frac{6}{2\omega +3}}}.`$ (13)
Here $`a_0`$ is an arbitrary constant. On the other hand, one finds the dilaton field $`\varphi _J`$ in the Jordan frame as

$$\varphi =\varphi _0\eta ^{\frac{1}{H_1}\sqrt{\frac{16\pi G}{2\omega +3}}}=\varphi _0\eta ^{2(\zeta 1)},\varphi _0=\frac{1}{a_0G}.$$
(14)
Let us analyze the equations of motion in the Jordan frame (for the form of transformation to string frame see section 5). The variations over $`\varphi `$ and $`\sigma `$ give the following equations:

$`0`$ $`=`$ $`6\left(\sigma ^{\prime \prime }+\sigma _{}^{}{}_{}{}^{2}\right)\mathrm{e}^{2\sigma }{\displaystyle \frac{\omega \varphi _{}^{}{}_{}{}^{2}}{\varphi ^2}}\mathrm{e}^{2\sigma }2\omega \left({\displaystyle \frac{\varphi ^{}\mathrm{e}^{2\sigma }}{\varphi }}\right),`$ (15)
$`0`$ $`=`$ $`{\displaystyle \frac{2}{16\pi }}\left(6\left(\sigma ^{\prime \prime }+\sigma _{}^{}{}_{}{}^{2}\right)+{\displaystyle \frac{\omega \varphi _{}^{}{}_{}{}^{2}}{\varphi }}\right)\mathrm{e}^{2\sigma }+{\displaystyle \frac{6\left(\mathrm{e}^{2\sigma }\right)^{\prime \prime }12\left(\sigma ^{}\mathrm{e}^{2\sigma }\right)^{}}{16\pi }}`$ (17)
$`+4b^{}\sigma ^{\prime \prime \prime \prime }4\left(b+b^{}\right)\left\{\left(\sigma ^{\prime \prime }\sigma _{}^{}{}_{}{}^{2}\right)^{\prime \prime }+2\left(\sigma ^{}\left(\sigma ^{\prime \prime }\sigma _{}^{}{}_{}{}^{2}\right)\right)^{}\right\}.`$
Here $`{}_{}{}^{}\frac{d}{d\eta }`$. We can check that the solution (8) and (14) does not satisfy (15). If the solution in the Jordan frame would be equivalent to that in the Einstein frame even in the quantum level, we should have $`\sigma _1=\sigma _J\mathrm{ln}a_J`$ but we have $`\sigma _1=\sigma +\frac{A\varphi }{3}=\sigma \frac{4}{3}\mathrm{ln}G\varphi _J`$ and $`\sigma _J=\sigma \frac{1}{2}\mathrm{ln}G\varphi _J`$. This is an origin of the inequivalence. Thus, it is demonstrated that for the Universe model under consideration the Jordan and Einstein frames in 4d dilatonic gravity with quantum corrections are not equivalent. Different parametrizations lead to different results (parametrization choice dependence). The physical results are expecting to be the same only for S-matrix in full theory (non-perturbative regime).

## III Inflationary dilatonic brane-world Universe in Einstein frame

In this section we present the review of quantum induced dilatonic brane-worlds found in ref.. The model is discussed in Einstein frame and using euclidean notations. This scenario represents the extension to non-constant dilaton case the earlier scenario of refs. where quantum brane-worlds were realized in frames of AdS/CFT correspondence, by adding quantum CFT on the brane to effective action.

We start with Euclidean signature action $`S`$ which is the sum of the Einstein-Hilbert action $`S_{\mathrm{EH}}`$ including dilaton $`\varphi `$ with potential $`V(\varphi )=\frac{12}{l^2}+\mathrm{\Phi }(\varphi )`$, the Gibbons-Hawking surface term $`S_{\mathrm{GH}}`$, the surface counter term $`S_1`$***We use the following curvature conventions:    $`R`$ $`=`$ $`g^{\mu \nu }R_{\mu \nu }`$    $`R_{\mu \nu }`$ $`=`$ $`R_{\mu \lambda \nu }^\lambda `$    $`R_{\mu \rho \nu }^\lambda `$ $`=`$ $`\mathrm{\Gamma }_{\mu \rho ,\nu }^\lambda +\mathrm{\Gamma }_{\mu \nu ,\rho }^\lambda \mathrm{\Gamma }_{\mu \rho }^\eta \mathrm{\Gamma }_{\nu \eta }^\lambda +\mathrm{\Gamma }_{\mu \nu }^\eta \mathrm{\Gamma }_{\rho \eta }^\lambda `$    $`\mathrm{\Gamma }_{\mu \lambda }^\eta `$ $`=`$ $`{\displaystyle \frac{1}{2}}g^{\eta \nu }\left(g_{\mu \nu ,\lambda }+g_{\lambda \nu ,\mu }g_{\mu \lambda ,\nu }\right).`$

$`S`$ $`=`$ $`S_{\mathrm{EH}}+S_{\mathrm{GH}}+2S_1,`$ (18)
$`S_{\mathrm{EH}}`$ $`=`$ $`{\displaystyle \frac{1}{16\pi G}}{\displaystyle d^5x\sqrt{g_{(5)}}\left(R_{(5)}\frac{1}{2}_\mu \varphi ^\mu \varphi +\frac{12}{l^2}+\mathrm{\Phi }(\varphi )\right)},`$ (19)
$`S_{\mathrm{GH}}`$ $`=`$ $`{\displaystyle \frac{1}{8\pi G}}{\displaystyle d^4x\sqrt{g_{(4)}}_\mu n^\mu },`$ (20)
$`S_1`$ $`=`$ $`{\displaystyle \frac{1}{16\pi G}}{\displaystyle d^4\sqrt{g_{(4)}}\left(\frac{6}{l}+\frac{l}{4}\mathrm{\Phi }(\varphi )\right)}.`$ (21)
Here the quantities in the 5 dimensional bulk spacetime are specified by the suffices (5) and those in the boundary 4 dimensional spacetime are specified by (4). The factor $`2`$ in front of $`S_1`$ in (18) is coming from that we have two bulk regions which are connected with each other by the brane. It is clear that above representation corresponds to Einstein frame. In (20), $`n^\mu `$ is the unit vector normal to the boundary.

### A Bulk solutions

In this subsection, we find some explicit solutions in the bulk space.

We now assume the metric in the following form

$$ds^2=f(y)dy^2+y\underset{i,j=0}{\overset{3}{}}\widehat{g}_{ij}(x^k)dx^idx^j,$$
(22)
and $`\varphi `$ depends only on $`y`$: $`\varphi =\varphi (y)`$. Here $`\widehat{g}_{ij}`$ is the metric of the Einstein manifold, which is defined by $`r_{ij}=k\widehat{g}_{ij}`$, where $`r_{ij}`$ is the Ricci tensor constructed with $`\widehat{g}_{ij}`$ and $`k`$ is a constant. Then we obtain the following equations of motion in the bulk:

$`0`$ $`=`$ $`{\displaystyle \frac{3}{2y^2}}{\displaystyle \frac{2kf}{y}}{\displaystyle \frac{1}{4}}\left({\displaystyle \frac{d\varphi }{dy}}\right)^2\left({\displaystyle \frac{6}{l^2}}+{\displaystyle \frac{1}{2}}\mathrm{\Phi }(\varphi )\right)f,`$ (23)
$`0`$ $`=`$ $`{\displaystyle \frac{d}{dy}}\left({\displaystyle \frac{y^2}{\sqrt{f}}}{\displaystyle \frac{d\varphi }{dy}}\right)+\mathrm{\Phi }^{}(\varphi )y^2\sqrt{f}.`$ (24)
It is convenient to introduce the new coordinate $`z`$

$$z=𝑑y\sqrt{f(y)}.$$
(25)
By solving $`y`$ with respect to $`z`$, we obtain the warp factor $`l^2\mathrm{e}^{2\widehat{A}(z,k)}=y(z)`$. Here one assumes the metric of 5 dimensional space time as follows:

$$ds^2=dz^2+\mathrm{e}^{2A(z,\sigma )}\stackrel{~}{g}_{\mu \nu }dx^\mu dx^\nu ,\stackrel{~}{g}_{\mu \nu }dx^\mu dx^\nu l^2\left(d\sigma ^2+d\mathrm{\Omega }_3^2\right).$$
(26)
where $`d\mathrm{\Omega }_3^2`$ corresponds to the metric of 3 dimensional unit sphere. Suppose that $`A(z,\sigma )`$ can be decomposed into the sum of $`z`$-dependent part $`\widehat{A}(z)`$ and $`\sigma `$-dependent part and therefore $`l^2\mathrm{e}^{2\widehat{A}(z)}\widehat{g}_{\mu \nu }=\mathrm{e}^{2A(z,\sigma )}\stackrel{~}{g}_{\mu \nu }`$. Then for the unit sphere ($`k=3`$)

$$A(z,\sigma )=\widehat{A}(z,k=3)\mathrm{ln}\mathrm{cosh}\sigma ,$$
(27)
for the flat Euclidean space ($`k=0`$)

$$A(z,\sigma )=\widehat{A}(z,k=0)+\sigma ,$$
(28)
and for the unit hyperboloid ($`k=3`$)

$$A(z,\sigma )=\widehat{A}(z,k=3)\mathrm{ln}\mathrm{sinh}\sigma .$$
(29)
When $`\mathrm{\Phi }(\varphi )=0`$, there exists the following AdS-like solution of the equations of motion

$`ds^2`$ $`=`$ $`f(y)dy^2+y{\displaystyle \underset{i,j=0}{\overset{d1}{}}}\widehat{g}_{ij}(x^k)dx^idx^j`$ (30)
$`f`$ $`=`$ $`{\displaystyle \frac{d(d1)}{4y^2\lambda ^2\left(1+\frac{c^2}{2\lambda ^2y^d}+\frac{kd}{\lambda ^2y}\right)}}`$ (31)
$`\varphi `$ $`=`$ $`c{\displaystyle 𝑑y\sqrt{\frac{d(d1)}{4y^{d+2}\lambda ^2\left(1+\frac{c^2}{2\lambda ^2y^d}+\frac{kd}{\lambda ^2y}\right)}}}.`$ (32)
Here $`\lambda ^2=\frac{12}{l^2}`$.

When $`\mathrm{\Phi }(\varphi )0`$, by using (23) and (24), one can delete $`f`$ from the equations and we obtain an equation that contains only the dilaton field $`\varphi `$:

$`0`$ $`=`$ $`\left\{{\displaystyle \frac{5k}{2}}{\displaystyle \frac{k}{4}}y^2\left({\displaystyle \frac{d\varphi }{dy}}\right)^2+\left({\displaystyle \frac{3}{2}}y{\displaystyle \frac{y^3}{6}}\left({\displaystyle \frac{d\varphi }{dy}}\right)^2\right)\left({\displaystyle \frac{6}{l^2}}+{\displaystyle \frac{1}{2}}\mathrm{\Phi }(\varphi )\right)\right\}{\displaystyle \frac{d\varphi }{dy}}`$ (34)
$`+{\displaystyle \frac{y^2}{2}}\left({\displaystyle \frac{2k}{y}}+{\displaystyle \frac{6}{l^2}}+{\displaystyle \frac{1}{2}}\mathrm{\Phi }(\varphi )\right){\displaystyle \frac{d^2\varphi }{dy^2}}+\left({\displaystyle \frac{3}{4}}{\displaystyle \frac{y^2}{8}}\left({\displaystyle \frac{d\varphi }{dy}}\right)^2\right)\mathrm{\Phi }^{}(\varphi ).`$
We now consider a solvable case where

$$\frac{6}{l^2}+\frac{1}{2}\mathrm{\Phi }(\varphi )=\frac{2k}{y}.$$
(35)
The explicit form, or $`\varphi `$ dependence, of $`\mathrm{\Phi }(\varphi )`$ can be determined after solving the equations of motion as the following

$$\varphi =\pm \sqrt{6}\mathrm{ln}(m^2y).$$
(36)
Here $`m^2`$ is a constant of the integration. The explicit form of $`\mathrm{\Phi }(\varphi )`$ is:

$$\mathrm{\Phi }(\varphi )=\frac{12}{l^2}4km^2\mathrm{e}^{\frac{\varphi }{\sqrt{6}}}.$$
(37)
One can also find that Eq.(23) is trivially satisfied. Integrating (24), we obtain

$$f=\frac{1}{\frac{2ky}{9}+\frac{f_0}{y^2}}.$$
(38)
Here $`f_0`$ is a constant of the integration and $`f_0`$ should be positive in order that $`f`$ is positive for large $`y`$. There is a (curvature) singularity at $`y=0`$. One should also note that when $`k>0`$, the horizon appears at

$$y^3=y_0^3\frac{9f_0}{2k}$$
(39)
and we find

$$yy_0.$$
(40)
### B Brane solutions

In this subsection, we investigate if there is a solution with brane including the quantum correction from $`N`$ massless brane Majorana spinors coupled with the dilaton. For simplicity, only the case that the potential is constant.

On the brane, one obtains the following equations by the variations over $`A`$ and $`\varphi `$:

$`0`$ $`=`$ $`{\displaystyle \frac{48l^4}{16\pi G}}\left(_zA{\displaystyle \frac{1}{l}}{\displaystyle \frac{l}{24}}\mathrm{\Phi }(\varphi )\right)\mathrm{e}^{4A},`$ (41)
$`0`$ $`=`$ $`{\displaystyle \frac{l^4}{8\pi G}}\mathrm{e}^{4A}_z\varphi {\displaystyle \frac{l^5}{32\pi G}}\mathrm{e}^{4A}\mathrm{\Phi }^{}(\varphi ).`$ (42)
With (37) and the solution (38), these equations look

$`0`$ $`=`$ $`{\displaystyle \frac{1}{2R^2}}\sqrt{{\displaystyle \frac{f_0}{R^4}}{\displaystyle \frac{2kR^2}{9}}}{\displaystyle \frac{1}{2l}}+{\displaystyle \frac{kl}{3R^2}},`$ (43)
$`0`$ $`=`$ $`\sqrt{{\displaystyle \frac{f_0}{R^4}}{\displaystyle \frac{2kR^2}{9}}}+{\displaystyle \frac{kl}{kl}}.`$ (44)
Here we assume that the brane lies at $`y=y_0`$ or $`z=z_0`$. The radius $`R`$ of the brane is defined by $`R=\mathrm{e}^{\widehat{A}(z_0)}`$. Eq.(44) tells that $`k0`$ but by combining (43) and (44), we find $`R^2=\frac{kl^2}{2}`$. Then there is no consistent classical solution.

We now consider the case that the matter on the brane is some QFT like QED or QCD. Of course, such a theory is classically conformally invariant one. As an explicit example in order to be able to apply large $`N`$-expansion we suppose that dominant contribution is due to $`N`$ massless Majorana spinors coupled with the dilaton, whose action is given by

$$S=\sqrt{g_{(4)}}\mathrm{e}^{a\varphi }\underset{i=1}{\overset{N}{}}\overline{\mathrm{\Psi }}_i\gamma ^\mu D_\mu \mathrm{\Psi }_i.$$
(45)
The case of minimal spinor coupling corresponds to the choice $`a=0`$. Note that from Brans-Dicke theory consideration one knows that for Einstein frame the non-minimal dilaton coupling with the matter is the typical case. Then the trace anomaly induced action $`W`$ has the following form :

$`W`$ $`=`$ $`b{\displaystyle d^4x\sqrt{\stackrel{~}{g}}\stackrel{~}{F}A_1}`$ (49)
$`+b^{}{\displaystyle }d^4x\{A_1[2\stackrel{~}{\mathrm{}}^2+\stackrel{~}{R}_{\mu \nu }\stackrel{~}{}_\mu \stackrel{~}{}_\nu {\displaystyle \frac{4}{3}}\stackrel{~}{R}\stackrel{~}{\mathrm{}}^2+{\displaystyle \frac{2}{3}}(\stackrel{~}{}^\mu \stackrel{~}{R})\stackrel{~}{}_\mu ]A_1`$
$`+(\stackrel{~}{G}{\displaystyle \frac{2}{3}}\stackrel{~}{\mathrm{}}\stackrel{~}{R})A_1\}`$
$`{\displaystyle \frac{1}{12}}\left\{b^{\prime \prime }+{\displaystyle \frac{2}{3}}(b+b^{})\right\}{\displaystyle d^4x\left[\stackrel{~}{R}6\stackrel{~}{\mathrm{}}A_16(\stackrel{~}{}_\mu A_1)(\stackrel{~}{}^\mu A_1)\right]^2}.`$
Here

$$A_1=A+\frac{a\varphi }{3},$$
(50)
and

$$b=\frac{3N}{60(4\pi )^2},b^{}=\frac{11N}{360(4\pi )^2}.$$
(51)
We also choose $`b^{\prime \prime }=0`$ as it may be changed by finite renormalization of classical gravitational action. In (49), one chooses the 4 dimensional boundary metric as

$$g_{(4)}^{}{}_{\mu \nu }{}^{}=\mathrm{e}^{2A}\stackrel{~}{g}_{\mu \nu },$$
(52)
and we specify the quantities given by $`\stackrel{~}{g}_{\mu \nu }`$ by using $`\stackrel{~}{}`$. $`G`$ ($`\stackrel{~}{G}`$) and $`F`$ ($`\stackrel{~}{F}`$) are the Gauss-Bonnet invariant and the square of the Weyl tensor, which are given as

$`G`$ $`=`$ $`R^24R_{ij}R^{ij}+R_{ijkl}R^{ijkl},`$ (53)
$`F`$ $`=`$ $`{\displaystyle \frac{1}{3}}R^22R_{ij}R^{ij}+R_{ijkl}R^{ijkl},`$ (54)
For simplicity, we consider a constant potential ($`\mathrm{\Phi }(\varphi )=0`$) case. Then brane equations are

$`0`$ $`=`$ $`{\displaystyle \frac{48l^4}{16\pi G}}\left(_zA{\displaystyle \frac{1}{l}}\right)\mathrm{e}^{4A}+b^{}\left(4_\sigma ^4A_116_\sigma ^2A_1\right)`$ (56)
$`4(b+b^{})\left(_\sigma ^4A_1+2_\sigma ^2A_16(_\sigma A_1)^2_\sigma ^2A_1\right),`$
$`0`$ $`=`$ $`{\displaystyle \frac{l^4}{8\pi G}}\mathrm{e}^{4A}_z\varphi +{\displaystyle \frac{4}{3}}ab^{}\left(4_\sigma ^4A_116_\sigma ^2A_1\right).`$ (57)
Then one gets

$`0`$ $`=`$ $`{\displaystyle \frac{1}{\pi Gl}}\left\{\sqrt{1+{\displaystyle \frac{kl^2}{3R^2}}+{\displaystyle \frac{l^2c^2}{24R^8}}}1\right\}R^4+8b^{},`$ (58)
$`0`$ $`=`$ $`{\displaystyle \frac{c}{8\pi G}}+32ab^{}.`$ (59)
Note that for minimal spinor coupling the second equation does not have a solution. Eq.(59) can be solved with respect to $`c`$:

$$c=32\times 8\pi Gab^{},$$
(60)
but the boundary value $`\varphi _0`$ of $`\varphi `$ becomes a free parameter.

We should also note that in the classical case that $`b^{}=0`$, there is no solution for (58) and (59). From Eq.(59), we find $`c=0`$ if $`b^{}=0`$. Then if we put $`c=0`$ and $`b^{}=0`$ in (58), there is no solution.

When the dilaton vanishes ($`c=0`$) and the brane is the unit sphere ($`k=3`$), the equation (58) reproduces the result of ref. for $`𝒩=4`$ $`SU(N)`$ super Yang-Mills theory in case of the large $`N`$ limit where $`b^{}`$ is replaced by $`\frac{N^2}{4(4\pi )^2}`$:

$$\frac{R^3}{l^3}\sqrt{1+\frac{R^2}{l^2}}=\frac{R^4}{l^4}+\frac{GN^2}{8\pi l^3}.$$
(61)
Let us define a function $`F(R,c)`$ as

$$F(R,c)\frac{1}{\pi Gl}\left(\sqrt{1+\frac{kl^2}{3R^2}+\frac{l^2c^2}{24R^8}}1\right)R^4,$$
(62)
which appears in the r.h.s. in (58).

For the $`k>0`$ case, $`F(R,c)`$ has a minimum at $`R=R_0`$, where $`R_0`$ is defined by

$$0=\frac{8kl^2}{3R_0^2}+\frac{k^2l^4}{R_0^4}\frac{2l^2c^2}{3R_0^8}.$$
(63)
When $`k>0`$, there is only one solution for $`R_0`$. Therefore $`F(R,c)`$ in the case of $`k>0`$ (sphere case) is a monotonically increasing function of $`R`$ when $`R>R_0`$ and a decreasing function when $`R<R_0`$. Since $`F(R,c)`$ is clearly a monotonically increasing function of $`c`$, we find for $`k>0`$ and $`b^{}<0`$ case that $`R`$ decreases when $`c`$ increases if $`R>R_0`$, that is, the non-trivial dilaton makes the radius smaller. We can also find that there is no solution for $`R`$ in (58) for very large $`|c|`$.

We can consider the $`k<0`$ case. When $`c=0`$, there is no solution for $`R`$ in (58). We can find, however, there is a solution if $`|c|`$ is large enough:

$$\frac{|c|}{\pi G\sqrt{24}}>8b^{}.$$
(64)
Hence, for constant bulk potential there is the possibility of quantum creation of a 4d de Sitter or a 4d hyperbolic brane living in 5d AdS bulk space. This occurs even for not exactly conformal invariant quantum brane matter. This finishes our consideration of quantum induced dilatonic brane-worlds in Einstein frame.

## IV Quantum induced dilatonic brane-worlds in string frame.

We now transform the brane-world action in the Einstein frame (see (18)) into the Jordan frame. If we consider the scale transformation

$$g_{\mu \nu }\mathrm{e}^\rho g_{\mu \nu },$$
(65)
with the choice

$$\mathrm{e}^{\left(\frac{D}{2}1\right)\rho }=\alpha \varphi ,(\alpha \text{ is a constant}),$$
(66)
we find that the actions (19), (20) and (21) are transformed as

$`S_{\mathrm{EH}}`$ $`=`$ $`{\displaystyle \frac{1}{16\pi G}}{\displaystyle }d^5x\sqrt{g_{(5)}}(\alpha \varphi R_{(5)}+{\displaystyle \frac{4\alpha }{3\varphi }}_\mu \varphi ^\mu \varphi {\displaystyle \frac{\alpha }{2}}\varphi _\mu \varphi ^\mu \varphi `$ (68)
$`+({\displaystyle \frac{12}{l^2}}+\mathrm{\Phi }(\varphi ))\left(\alpha \varphi \right)^{\frac{5}{3}}),`$
$`S_{\mathrm{GH}}`$ $`=`$ $`{\displaystyle \frac{1}{8\pi G}}{\displaystyle d^4x\alpha \varphi \sqrt{g_{(4)}}_\mu n^\mu },`$ (69)
$`S_1`$ $`=`$ $`{\displaystyle \frac{1}{16\pi G}}{\displaystyle d^4x\left(\alpha \varphi \right)^{\frac{4}{3}}\sqrt{g_{(4)}}\left(\frac{6}{l}+\frac{l}{4}\mathrm{\Phi }(\varphi )\right)}.`$ (70)
### A Bulk solution in the string frame

In the bulk, the variation over $`\varphi `$ gives the following equation of motion:

$`0`$ $`=`$ $`\alpha R_{(5)}{\displaystyle \frac{4\alpha }{3\varphi ^2}}_\mu \varphi ^\mu \varphi {\displaystyle \frac{\alpha }{2}}_\mu \varphi ^\mu \varphi +{\displaystyle \frac{5}{3}}\left({\displaystyle \frac{12}{l^2}}+\mathrm{\Phi }(\varphi )\right)\alpha ^{\frac{5}{3}}\varphi ^{\frac{2}{3}}`$ (72)
$`+\mathrm{\Phi }^{}(\varphi )\left(\alpha \varphi \right)^{\frac{5}{3}}{\displaystyle \frac{8\alpha }{3}}_\mu \left({\displaystyle \frac{1}{\varphi }}^\mu \varphi \right)+\alpha _\mu \left(\varphi ^\mu \varphi \right).`$
On the other hand, the variation over the metric $`g^{\mu \nu }`$ gives

$`0`$ $`=`$ $`{\displaystyle \frac{1}{2}}\left(\alpha \varphi R_{(5)}+{\displaystyle \frac{4\alpha }{3\varphi }}_\mu \varphi ^\mu \varphi {\displaystyle \frac{\alpha }{2}}\varphi _\mu \varphi ^\mu \varphi +\left({\displaystyle \frac{12}{l^2}}+\mathrm{\Phi }(\varphi )\right)\left(\alpha \varphi \right)^{\frac{5}{3}}\right)g_{(5)\mu \nu }`$ (75)
$`+\alpha \varphi R_{(5)\mu \nu }\alpha _\mu _\nu \varphi +\alpha g_{(5)\mu \nu }\mathrm{}\varphi `$
$`+{\displaystyle \frac{4\alpha }{3\varphi }}_\mu \varphi _\nu \varphi {\displaystyle \frac{\alpha }{2}}_\mu \varphi _\nu \varphi .`$
Thus, one gets the bulk equations of motion in string frame. Using (75), we have

$`0`$ $`=`$ $`{\displaystyle \frac{3}{2}}\left(\alpha \varphi R_{(5)}+{\displaystyle \frac{4\alpha }{3\varphi }}_\mu \varphi ^\mu \varphi {\displaystyle \frac{\alpha }{2}}\varphi _\mu \varphi ^\mu \varphi \right)`$ (77)
$`{\displaystyle \frac{5}{2}}\left({\displaystyle \frac{12}{l^2}}+\mathrm{\Phi }(\varphi )\right)\left(\alpha \varphi \right)^{\frac{5}{3}}+4\alpha \mathrm{}\varphi .`$
Substituting (77) into (72) and (75), one obtains

$`0`$ $`=`$ $`\alpha _\mu \left(\varphi ^\mu \varphi \right)+\mathrm{\Phi }^{}(\varphi )\left(\alpha \varphi \right)^{\frac{5}{3}}`$ (78)
$`0`$ $`=`$ $`\alpha _\mu _\nu \varphi {\displaystyle \frac{\alpha }{3}}g_{(5)\mu \nu }\mathrm{}\varphi +\alpha \varphi R_{(5)\mu \nu }`$ (80)
$`+{\displaystyle \frac{1}{3}}\left({\displaystyle \frac{12}{l^2}}+\mathrm{\Phi }(\varphi )\right)\left(\alpha \varphi \right)^{\frac{5}{3}}g_{(5)\mu \nu }+{\displaystyle \frac{4\alpha }{3\varphi }}_\mu \varphi _\nu \varphi {\displaystyle \frac{\alpha }{2}}\varphi _\mu \varphi _\nu \varphi .`$
First, let us consider $`\mathrm{\Phi }(\varphi )=0`$ case. In the Einstein frame, the solution is given by (30). The metric $`g_{(5)\mu \nu }^\mathrm{J}`$ in the Jordan frame is obtained with the help of (65) and (66), or more explicitly

$`g_{(5)\mu \nu }^\mathrm{J}dx^\mu dx^\nu `$ $`=`$ $`\left(\alpha \varphi \right)^{\frac{2}{3}}\left(f(y)dy^2+y{\displaystyle \underset{i,j=0}{\overset{3}{}}}\widehat{g}_{ij}(x^k)dx^idx^j\right)`$ (81)
$`f`$ $`=`$ $`{\displaystyle \frac{l^2}{4y^2\left(1+\frac{c^2l^2}{24y^4}+\frac{kl^2}{3y}\right)}}`$ (82)
$`\varphi `$ $`=`$ $`c{\displaystyle 𝑑y\frac{l}{2\sqrt{y^6\left(1+\frac{c^2l^2}{24y^4}+\frac{kl^2}{3y}\right)}}}.`$ (83)
One can check directly that the metric (81) satisfies Eqs.(78) and (80). Although the classical bulk solution in the Einstein frame is equivalent to the one in the Jordan frame, the physical interpretation of the spacetime is changed due to the factor of $`\left(\alpha \varphi \right)^{\frac{2}{3}}`$. Since the transformation is conformal, the causal structure of the spacetime is not changed, especially the situation that there is a curvature singularity at $`y=0`$ is not changed. When $`y\mathrm{}`$, however, the spacetime is not asymptotically AdS but the metric behaves as

$$g_{(5)\mu \nu }^\mathrm{J}dx^\mu dx^\nu \left(\frac{\alpha cl}{4}\right)^{\frac{2}{3}}\left(\frac{l^2}{4y^{\frac{2}{3}}}dy^2+y^{\frac{7}{3}}\underset{i,j=0}{\overset{3}{}}\widehat{g}_{ij}(x^k)dx^idx^j\right).$$
(84)
If one defines a coordinate $`z`$ by

$$z\left(\frac{\alpha cl}{4}\right)^{\frac{1}{3}}\frac{3l}{4}y^{\frac{2}{3}},$$
(85)
the metric in (84) is rewritten by

$$g_{(5)\mu \nu }^\mathrm{J}dx^\mu dx^\nu dz^2+\left(\frac{\alpha cl}{4}\right)^{\frac{1}{2}}\left(\frac{4z}{3l}\right)^{\frac{7}{2}}\underset{i,j=0}{\overset{3}{}}\widehat{g}_{ij}(x^k)dx^idx^j.$$
(86)
Then the warp factor behaves as the power of $`z`$, instead of the exponential function in Einstein frame.

One can also consider the case that the dilaton potential $`\frac{12}{l^2}+\mathrm{\Phi }(\varphi )`$ is given by (37). Using the relation (65) and (66) between the Einstein frame and the Jordan frame, from (36) and (38), we find the following solution:

$`g_{(5)\mu \nu }^\mathrm{J}dx^\mu dx^\nu `$ $`=`$ $`\left(\pm \alpha \sqrt{6}\mathrm{ln}(m^2y)\right)^{\frac{2}{3}}\left({\displaystyle \frac{1}{\frac{2ky}{9}+\frac{f_0}{y^2}}}dy^2+y{\displaystyle \underset{i,j=0}{\overset{3}{}}}\widehat{g}_{ij}(x^k)dx^idx^j\right)`$ (87)
$`\varphi `$ $`=`$ $`\pm \sqrt{6}\mathrm{ln}(m^2y).`$ (88)
One can again check that the above solution satisfies Eqs.(78) and (80). Then the above result is equivalent with that in the Einstein frame. Comparing the obtained metric with that in the Einstein frame in (36) and (38), there appears the factor of the logarithmic function of $`y`$, coming from the conformal transformation. In other words, the interpretation of lenghts in both frames is different while solutions are equivalent.

### B Brane solutions in the string frame

Having proof of explicit equivalency of bulk solutions, one can analyze the brane. From the actions in (68), (69) and (70), the variation over $`\varphi `$ gives the following equation on the boundary

$`0`$ $`=`$ $`{\displaystyle \frac{l^4\mathrm{e}^{4A}}{8\pi G}}\{({\displaystyle \frac{8\alpha }{3\varphi _0}}\alpha \varphi _0)_z\varphi +8\alpha _zA`$ (90)
$`{\displaystyle \frac{4\alpha }{3}}({\displaystyle \frac{6}{l}}+{\displaystyle \frac{l}{4}}\mathrm{\Phi }(\varphi ))\left(\alpha \varphi _0\right)^{\frac{1}{3}}{\displaystyle \frac{l}{4}}\mathrm{\Phi }^{}(\varphi )\left(\alpha \varphi \right)^{\frac{4}{3}}\}.`$
Here we choose the metric as in (26) and $`\varphi _0`$ is the value of $`\varphi `$ on the boundary. The variation over $`A`$ gives the following equation

$$0=\frac{48l^4}{16\pi G}\mathrm{e}^{4A}\left(\alpha \varphi _0_zA+\frac{\alpha }{3}_z\varphi \frac{1}{6}\left(\frac{6}{l}+\frac{l}{4}\mathrm{\Phi }(\varphi )\right)\left(\alpha \varphi _0\right)^{\frac{4}{3}}\right).$$
(91)
The coordinate $`z`$ and $`A`$ in the warp factor are related with those in the Einstein frame, $`z_E`$ and $`A_E`$ by

$$dz_E=\left(\alpha \varphi \right)^{\frac{1}{3}}dz,A_E=A+\frac{1}{3}\mathrm{ln}\left(\alpha \varphi \right).$$
(92)
Then Eqs.(90) and (91) are rewritten as

$`0`$ $`=`$ $`{\displaystyle \frac{l^4\mathrm{e}^{4A_E}}{8\pi G}}\{_{z_E}\varphi +\alpha \left(\alpha \varphi _0\right)(8_{z_E}A_E{\displaystyle \frac{4\alpha }{3}}({\displaystyle \frac{6}{l}}+{\displaystyle \frac{l}{4}}\mathrm{\Phi }(\varphi ))`$ (94)
$`{\displaystyle \frac{l}{4}}\mathrm{\Phi }^{}(\varphi ))\}`$
$`0`$ $`=`$ $`{\displaystyle \frac{48l^4}{16\pi G}}\mathrm{e}^{4A_E}\left\{_{z_E}A_E{\displaystyle \frac{1}{6}}\left({\displaystyle \frac{6}{l}}+{\displaystyle \frac{l}{4}}\mathrm{\Phi }(\varphi )\right)\right\}.`$ (95)
Combining (94) and (95), we obtain

$$0=\frac{l^4\mathrm{e}^{4A_E}}{8\pi G}\left\{_{z_E}\varphi \frac{l}{4}\mathrm{\Phi }^{}(\varphi )\right\}.$$
(96)
The obtained equations (95) and (96) are identical with the corresponding equations (41) and (42) without the quantum correction, respectively.

Choosing the metric of 5 dimensional space-time as in (26):

$$ds^2=dz^2+\mathrm{e}^{2A(z,\sigma )}\stackrel{~}{g}_{\mu \nu }dx^\mu dx^\nu ,\stackrel{~}{g}_{\mu \nu }dx^\mu dx^\nu l^2\left(d\sigma ^2+d\mathrm{\Omega }_3^2\right),$$
(97)
where $`d\mathrm{\Omega }_3^2`$ corresponds to the metric of 3 dimensional unit sphere, we now include the quantum correction as in (49):

$`W`$ $`=`$ $`b{\displaystyle d^4x\sqrt{\stackrel{~}{g}}\stackrel{~}{F}A}`$ (101)
$`+b^{}{\displaystyle }d^4x\{A[2\stackrel{~}{\mathrm{}}^2+\stackrel{~}{R}_{\mu \nu }\stackrel{~}{}_\mu \stackrel{~}{}_\nu {\displaystyle \frac{4}{3}}\stackrel{~}{R}\stackrel{~}{\mathrm{}}^2+{\displaystyle \frac{2}{3}}(\stackrel{~}{}^\mu \stackrel{~}{R})\stackrel{~}{}_\mu ]A`$
$`+(\stackrel{~}{G}{\displaystyle \frac{2}{3}}\stackrel{~}{\mathrm{}}\stackrel{~}{R})A\}`$
$`{\displaystyle \frac{1}{12}}\left\{b^{\prime \prime }+{\displaystyle \frac{2}{3}}(b+b^{})\right\}{\displaystyle d^4x\left[\stackrel{~}{R}6\stackrel{~}{\mathrm{}}A6(\stackrel{~}{}_\mu A)(\stackrel{~}{}^\mu A)\right]^2}.`$
Note that as typically in Jordan frame there is no non-minimal dilaton coupling with matter we took minimal spinors, i.e. $`a=0`$. Then one obtains the following brane equations (instead of (90) and (91)):

$`0`$ $`=`$ $`{\displaystyle \frac{l^4\mathrm{e}^{4A}}{8\pi G}}\{({\displaystyle \frac{8\alpha }{3\varphi _0}}\alpha \varphi _0)_z\varphi +8\alpha _zA`$ (105)
$`{\displaystyle \frac{4\alpha }{3}}({\displaystyle \frac{6}{l}}+{\displaystyle \frac{l}{4}}\mathrm{\Phi }(\varphi ))\left(\alpha \varphi _0\right)^{\frac{1}{3}}{\displaystyle \frac{l}{4}}\mathrm{\Phi }^{}(\varphi )\left(\alpha \varphi \right)^{\frac{4}{3}}\}`$
$`+b^{}\left(4_\sigma ^4A16_\sigma ^2A\right)`$
$`4(b+b^{})\left(_\sigma ^4A+2_\sigma ^2A6(_\sigma A)^2_\sigma ^2A\right),`$
$`0`$ $`=`$ $`{\displaystyle \frac{48l^4}{16\pi G}}\mathrm{e}^{4A}\left(\alpha \varphi _0_zA+{\displaystyle \frac{\alpha }{3}}_z\varphi {\displaystyle \frac{1}{6}}\left({\displaystyle \frac{6}{l}}+{\displaystyle \frac{l}{4}}\mathrm{\Phi }(\varphi )\right)\left(\alpha \varphi _0\right)^{\frac{4}{3}}\right)`$ (107)
$`+{\displaystyle \frac{4}{3}}ab^{}\left(4_\sigma ^4A16_\sigma ^2A\right).`$
For $`\mathrm{\Phi }(\varphi )=0`$ case, substituting the solution in (81), one finds

$`0`$ $`=`$ $`{\displaystyle \frac{1}{\pi Gl}}\left\{\sqrt{1+{\displaystyle \frac{kl^2}{3\left(\alpha \varphi _0\right)^{\frac{2}{3}}R^2}}+{\displaystyle \frac{l^2c^2}{24\left(\alpha \varphi _0\right)^{\frac{8}{3}}R^8}}}1\right\}\left(\alpha \varphi _0\right)^{\frac{4}{3}}R^4`$ (109)
$`+8b^{},`$
$`0`$ $`=`$ $`{\displaystyle \frac{c}{8\pi G}}`$ (111)
$`+{\displaystyle \frac{1}{\pi Gl\varphi _0}}\left\{\sqrt{1+{\displaystyle \frac{kl^2}{3\left(\alpha \varphi _0\right)^{\frac{2}{3}}R^2}}+{\displaystyle \frac{l^2c^2}{24\left(\alpha \varphi _0\right)^{\frac{8}{3}}R^8}}}1\right\}\left(\alpha \varphi _0\right)^{\frac{4}{3}}R^4.`$
Combining (109) and (111), one gets

$$0=\frac{c}{8\pi G}\frac{8b^{}}{\varphi _0}.$$
(112)
Eq.(112) has non-trivial solution and can be solved with respect to $`\varphi _0`$:

$$\varphi _0=\frac{64\pi Gb^{}}{c}.$$
(113)
In the classical case that $`b^{}=0`$, there is no solution for (109). Let us define a function $`F(R,c)`$ as

$$F(R,c)\frac{1}{\pi Gl}\left\{\sqrt{1+\frac{kl^2}{3\left(\alpha \varphi _0\right)^{\frac{2}{3}}R^2}+\frac{l^2c^2}{24\left(\alpha \varphi _0\right)^{\frac{8}{3}}R^8}}1\right\}\left(\alpha \varphi _0\right)^{\frac{4}{3}}R^4,$$
(114)
It appears in the r.h.s. in (109).

For $`k>0`$ case, $`F(R,c)`$ has a minimum at $`R=R_0`$, where $`R_0`$ is defined by

$$0=\frac{8kl^2}{3\left(\alpha \varphi _0\right)^{\frac{2}{3}}R_0^2}+\frac{k^2l^4}{\left(\alpha \varphi _0\right)^{\frac{4}{3}}R_0^4}\frac{2l^2c^2}{3\left(\alpha \varphi _0\right)^{\frac{8}{3}}R_0^8}.$$
(115)
When $`k>0`$, there is only one solution for $`R_0`$. Therefore $`F(R,c)`$ in the case of $`k>0`$ (sphere case) is a monotonically increasing function of $`R`$ when $`R>R_0`$ and a decreasing function when $`R<R_0`$. Since $`F(R,c)`$ is clearly a monotonically increasing function of $`c`$, we find for $`k>0`$ and $`b^{}<0`$ case that $`R`$ decreases when $`c`$ increases if $`R>R_0`$, that is, the non-trivial dilaton makes the radius smaller.

Since one finds

$$F(R_0,c)=\frac{kl\left(\alpha \varphi _0\right)^{\frac{2}{3}}R_0^2}{4\pi G},$$
(116)
using (114) and (115), Eq.(109) has a solution if

$$\frac{kl\left(\alpha \varphi _0\right)^{\frac{2}{3}}R_0^2}{4\pi G}8b^{}.$$
(117)
That puts again some bounds to the dilaton value. When $`|c|`$ is small, using (115), one obtains

$$R_0^4\frac{2c^2\left(\alpha \varphi _0\right)^{\frac{4}{3}}}{3k^2l^2},F(R_0,c)\frac{1}{4\pi G}\frac{|c|}{\sqrt{3}}.$$
(118)
Therefore Eq.(117) is satisfied for small $`|c|`$. On the other hand, when $`c`$ is large, we get

$$R_0^6\frac{c^2\left(\alpha \varphi _0\right)^{\frac{6}{3}}}{4k},F(R_0,c)\frac{\left(k|c|\right)^{\frac{2}{3}}}{4^{\frac{4}{3}}\pi G}.$$
(119)
Therefore Eq.(117) is not always satisfied and we have no solution for $`R`$ in (58) for very large $`|c|`$.

We now consider the $`k<0`$ case. When $`c=0`$, there is no solution for $`R`$ in (109). Let us define another function $`G(R,c)`$ as follows:

$$G(R,c)1+\frac{l^2c^2}{24\left(\alpha \varphi _0\right)^{\frac{8}{3}}R^8}+\frac{kl^2}{3\left(\alpha \varphi _0\right)^{\frac{2}{3}}R^2}.$$
(120)
Since $`G(R,c)`$ appears in the root of $`F(R,c)`$ in (114), $`G(R,c)`$ must be positive. Then since

$$\frac{G(R,c)}{R}=\frac{l^2c^2}{3\left(\alpha \varphi _0\right)^{\frac{8}{3}}R^9}\frac{2kl^2}{3\left(\alpha \varphi _0\right)^{\frac{2}{3}}R^3},$$
(121)
$`G(R,c)`$ has a minimum

$$1+\frac{kl^2}{4}\left(\frac{2k}{c^2}\right)^{\frac{1}{3}},$$
(122)
when

$$R^6=\frac{c^2\left(\alpha \varphi _0\right)^{\frac{6}{3}}}{2k}.$$
(123)
Therefore if

$$c^2\frac{k^4l^6}{32},$$
(124)
$`F(R,c)`$ is real for any positive value of $`R`$. Since

$$F(0,c)=\frac{|c|}{\pi G\sqrt{24}},$$
(125)
and when $`R\mathrm{}`$

$$F(R,c)\frac{kl\left(\alpha \varphi _0\right)^{\frac{2}{3}}R^2}{6\pi G}<0,$$
(126)
there is a solution $`R`$ in (109) if

$$\frac{|c|}{\pi G\sqrt{24}}>8b^{}.$$
(127)
This is the same bound as in Einstein frame (previous section).

Thus we demonstrated the complete equivalency of quantum induced inflationary (hyperbolic) dilatonic brane-worlds in Einstein and string (Jordan) frames.

Note that Eq.(109) is identical with the corresponding equation (58) in the Einstein frame if we regard $`\left(\alpha \varphi _0\right)^{\frac{1}{3}}R`$ as the radius $`R_E`$ in the Einstein frame:

$$R=\left(\alpha \varphi _0\right)^{\frac{1}{3}}R_E.$$
(128)
Then the solution has properties similar to those in the Einstein frame. Since $`b^{}`$ is order $`N`$ quantity from (51), Eq.(113) and (128) might tell that the radius $`R`$ in the Jordan frame is much smaller than the radius $`R_E`$ in the Einstein frame if $`N`$ is large. In case that the brane is sphere, the brane becomes de Sitter space. Since the rate of the expansion is given by $`\frac{1}{R}`$ in de Sitter space, the rate might become much larger if compare with that in the Einstein frame when $`N`$ is large. Thus, even having formal equivalency, the physical interpretation of results obtained in Jordan and Einstein frames may be different.

## V Brane-world black holes in string and Einstein frames

In analogy with Randall-Sundrum model , we now consider the following classical action of the gravity coupled with dilaton $`\varphi `$ in the Einstein frame with Lorentzian signature:

$`S`$ $`=`$ $`{\displaystyle \frac{1}{16\pi G}}[{\displaystyle }d^5x\sqrt{g_{(5)}}(R_{(5)}{\displaystyle \frac{1}{2}}_\mu \varphi ^\mu \varphi V(\varphi ))`$ (130)
$`{\displaystyle \underset{i=\mathrm{hid},\mathrm{vis}}{}}{\displaystyle _{B_i}}d^4x\sqrt{g_{(4)}}U_i(\varphi )].`$
Here $`B_{\mathrm{hid}}`$ and $`B_{\mathrm{vis}}`$ are branes corresponding to hidden and visible sectors respectively and $`U_i(\varphi )`$ corresponds to the vacuum energies on the branes in . One assumes $`U(\varphi )`$ is dilaton dependent and its form is explicitly given later on from the consistency of the equations of motion. The dilaton potential $`V(\varphi )`$ is often given in terms of the superpotential $`W(\varphi )`$ :

$$V=\left(\frac{W}{\varphi }\right)^2\frac{4}{6}W^2.$$
(131)
We assume again $`\varphi `$ only depends on $`z`$ and the metric has the following form:

$$ds^2=dz^2+\mathrm{e}^{2A(z)}\stackrel{~}{g}_{ij}dx^idx^j.$$
(132)
Here $`\stackrel{~}{g}_{ij}`$ is the metric of the Einstein manifold. We also suppose the hidden and visible branes sit on $`z=z_{\mathrm{hid}}`$ and $`z=z_{\mathrm{vis}}`$, respectively. Then the equations of motion are given by

$`\varphi ^{\prime \prime }+4A^{}\varphi ^{}={\displaystyle \frac{V}{\varphi }}+{\displaystyle \underset{i=\mathrm{hid},\mathrm{vis}}{}}{\displaystyle \frac{U_i(\varphi )}{\varphi }}\delta (zz_i),`$ (133)
$`4A^{\prime \prime }+4(A^{})^2+{\displaystyle \frac{1}{2}}(\varphi ^{})^2`$ (134)
$`={\displaystyle \frac{1}{3}}V(\varphi ){\displaystyle \frac{2}{3}}{\displaystyle \underset{i=\mathrm{hid},\mathrm{vis}}{}}U_i(\varphi )\delta (zz_i),`$ (135)
$`A^{\prime \prime }+4(A^{})^2=k\mathrm{e}^{2A}{\displaystyle \frac{1}{3}}V(\varphi ){\displaystyle \frac{1}{6}}{\displaystyle \underset{i=\mathrm{hid},\mathrm{vis}}{}}U_i(\varphi )\delta (zz_i).`$ (136)
Here $`{}_{}{}^{}\frac{d}{dz}`$. Especially when $`k=0`$, Eqs. (133-136) have the following first integrals in the bulk:

$`\varphi ^{}=\sqrt{2}{\displaystyle \frac{W}{\varphi }},A^{}={\displaystyle \frac{1}{3\sqrt{2}}}W.`$ (137)
Near the branes, Eqs. (133-136) have the following form :

$$\varphi ^{\prime \prime }\frac{U_i(\varphi )}{\varphi }\delta (zz_i),A^{\prime \prime }\frac{U_i(\varphi )}{6}\delta (zz_i),$$
(138)
or

$$2\varphi ^{}\frac{U_i(\varphi )}{\varphi },2A^{}\frac{U_i(\varphi )}{6},$$
(139)
at $`z=z_i`$. Comparing (139) with (137), we find

$$U_{\mathrm{hid}}(\varphi )=2\sqrt{2}W(\varphi ),U_{\mathrm{vis}}(\varphi )=2\sqrt{2}W(\varphi ).$$
(140)
We should note that $`k=0`$ does not always mean the brane is flat. As well-known, the Einstein equations are given by,

$$R_{\mu \nu }\frac{1}{2}g_{\mu \nu }R+\frac{1}{2}\mathrm{\Lambda }g_{\mu \nu }=T_{\mu \nu }^{\mathrm{matter}}.$$
(141)
Here $`T_{\mu \nu }^{\mathrm{matter}}`$ is the energy-momentum tensor of the matter fields. If we consider the vacuum solution where $`T_{\mu \nu }^{\mathrm{matter}}=0`$, Eq.(141) can be rewritten as

$$R_{\mu \nu }=\frac{\mathrm{\Lambda }}{2}g_{\mu \nu }.$$
(142)
If we put $`\mathrm{\Lambda }=2k`$, Eq.(142) is nothing but the equation for the Einstein manifold. The Einstein manifolds are not always homogeneous manifolds like flat Minkowski, (anti-)de Sitter space

$$ds_4^2=V(r)dt^2+V^1(r)dr^2+r^2d\mathrm{\Omega }^2,V(r)=1\frac{\mathrm{\Lambda }}{6}r^2,$$
(143)
or Nariai space

$$ds_4^2=\frac{1}{\mathrm{\Lambda }}\left(\mathrm{sin}^2\chi d\psi ^2d\chi ^2d\mathrm{\Omega }^2\right).$$
(144)
but they can be some black hole solutions like Schwarzschild-(anti-)de Sitter black hole

$$ds_4^2=V(r)dt^2+V^1(r)dr^2+r^2d\mathrm{\Omega }^2,V(r)=1\frac{\stackrel{~}{G}_4M}{r}\frac{\mathrm{\Lambda }}{6}r^2.$$
(145)
As a special case, one can also consider $`k=0`$ solution like Schwarzschild black hole,

$$ds_4^2\stackrel{~}{g}_{ij}dx^idx^j=\left(1\frac{\stackrel{~}{G}_4M}{r}\right)dt^2+\frac{dr^2}{\left(1\frac{\stackrel{~}{G}_4M}{r}\right)}+r^2d\mathrm{\Omega }^2.$$
(146)
In (145) and (146), $`M`$ is the mass of the black hole on the brane and the effective gravitational constant $`G_4`$ on the 3-brane (here $`d=4`$) is given by

$$\frac{1}{G_4}=\frac{1}{G}_{z_{\mathrm{hid}}}^{z_{\mathrm{vis}}}𝑑z\mathrm{e}^{(d2)A}.$$
(147)
In these solutions, the curvature singularity at $`r=0`$ has a form of line penetrating the bulk 5d universe and the horizon makes a tube surrounding the singularity. The singularity and the horizon connect the hidden and visible branes. These black holes have been discussed in ref..

We now consider the Jordan frame, in order to see if singularity supports (or breaks) the equivalency on classical level. Using scale transformation given by (65) and (66) with $`D=5`$, the action (130) is rewritten as

$`S`$ $`=`$ $`{\displaystyle \frac{1}{16\pi G}}{\displaystyle }d^5x\sqrt{g_{(5)}}(\alpha \varphi R_{(5)}+{\displaystyle \frac{4\alpha }{3\varphi }}_\mu \varphi ^\mu \varphi {\displaystyle \frac{\alpha }{2}}\varphi _\mu \varphi ^\mu \varphi `$ (150)
$`V(\varphi )\left(\alpha \varphi \right)^{\frac{5}{3}})`$
$`{\displaystyle \underset{i=\mathrm{hid},\mathrm{vis}}{}}{\displaystyle _{B_i}}d^4x\sqrt{g_{(4)}}\left(\alpha \varphi \right)^{\frac{4}{3}}U_i(\varphi )].`$
Then if we choose the metric as in (132) in the Jordan frame and $`\varphi `$ only depends on $`z`$ again, we obtain the following equations instead of (133), (134) and (136),

$`\alpha \left(\varphi \varphi ^{\prime \prime }+4A^{}\varphi \varphi ^{}+\left(\varphi ^{}\right)^2\right)`$ (151)
$`={\displaystyle \frac{V}{\varphi }}\left(\alpha \varphi \right)^{\frac{5}{3}}+{\displaystyle \underset{i=\mathrm{hid},\mathrm{vis}}{}}{\displaystyle \frac{U_i(\varphi )}{\varphi }}\left(\alpha \varphi \right)^{\frac{4}{3}}\delta (zz_i),`$ (152)
$`\alpha \varphi \left(4A^{\prime \prime }+4(A^{})^2\right)+{\displaystyle \frac{\alpha }{2}}\varphi (\varphi ^{})^2{\displaystyle \frac{4\alpha }{3\varphi }}(\varphi ^{})^2+{\displaystyle \frac{4\alpha }{3}}\left(\varphi ^{\prime \prime }+A^{}\varphi ^{}\right)`$ (153)
$`={\displaystyle \frac{1}{3}}V(\varphi )\left(\alpha \varphi \right)^{\frac{5}{3}}{\displaystyle \frac{2}{3}}{\displaystyle \underset{i=\mathrm{hid},\mathrm{vis}}{}}U_i(\varphi )\left(\alpha \varphi \right)^{\frac{4}{3}}\delta (zz_i),`$ (154)
$`\alpha \varphi \left(A^{\prime \prime }+4(A^{})^2\right)+{\displaystyle \frac{\alpha }{3}}\left(\varphi ^{\prime \prime }+7A^{}\varphi ^{}\right)`$ (155)
$`=k\alpha \varphi \mathrm{e}^{2A}{\displaystyle \frac{1}{3}}V(\varphi )\left(\alpha \varphi \right)^{\frac{5}{3}}{\displaystyle \frac{1}{6}}{\displaystyle \underset{i=\mathrm{hid},\mathrm{vis}}{}}U_i(\varphi )\left(\alpha \varphi \right)^{\frac{4}{3}}\delta (zz_i).`$ (156)
If one transforms the above equations to those in the Einstein frame by changing

$`A`$ $``$ $`A{\displaystyle \frac{1}{3}}\mathrm{ln}\left(\alpha \varphi \right)`$ (157)
$`dz`$ $``$ $`\left(\alpha \varphi \right)^{\frac{1}{3}}dz`$ (161)
$`\left(\begin{array}{ccc}\hfill ^{}_z& & \left(\alpha \varphi \right)^{\frac{1}{3}}_z\hfill \\ \hfill ^{\prime \prime }=_z^2& & \left(\alpha \varphi \right)^{\frac{2}{3}}\left(_z^2+\frac{_z\varphi }{3\varphi }_z\right)\hfill \end{array}\right),`$
then Eqs.(133), (134) and (136), which are the corresponding equations in the Einstein frame, are reproduced. Thus we can confirm the equivalence between the Jordan frame and the Einstein frame description of dilatonic brane-world black holes on the classical level. Their physical interpretation may be again different.

## VI Discussion

In summary, we discussed AdS/CFT induced quantum dilatonic brane-worlds where branes may be flat, de Sitter (inflationary) or Anti-de Sitter Universe. Actually, such objects appear in frames of AdS/CFT correspondence  as warped compactification of relevant holographic RG flow . The role of free parameter (brane tension) is played by effective brane tension produced by conformal anomaly of QFT sitting on the brane. Hence, only brane quantum effects are considered. We compared the construction of such quantum dilatonic brane-worlds in two frames: string and Einstein one. The very nice feature of brane-worlds is discovered: in all examples under consideration the string and Einstein frames are eqiuvalent! This holds to be true also for the number of classical dilatonic brane-world black holes. This is completely different from the case of quantum corrected 4d dilatonic gravity (section 2) where de Sitter Universe with decaying dilaton exists in Einstein frame but does not exist in Jordan frame.

Quantum effects may be useful in other aspects of brane-worlds. In particulary, for flat branes the bulk quantum effects (Casimir force) may be estimated  and used for radion stabilization. Unfortunately, in usual Randall-Sundrum Universe such quantum effects are actually supporting the radion destabilization. Nevertheless, in the case of thermal Randall-Sundrum scenario  such quantum effects may not only stabilize the radion but also may provide the necessary mass hierarchy  (at least, for some temperatures). It would be extremely interesting to estimate the bulk quantum effects for dilatonic backgrounds and to understand their role (as well as frame dependence of such Casimir effect) in the creation of dilatonic brane-worlds.

Another interesting line of research is related with account of quantum effects on graviton perturbations around the brane. As is demonstrated in previous section, they may modify the massive graviton modes around hyperbolic brane. Clearly, in other regimes for quantum induced dilatonic (asymptotically) AdS brane more complicated dynamics may be expected.

## Acknowledgements

We thank J. Socorro for participation at the early stage of this work. SDO is grateful to L. Randall for useful discussion. The work by O.O., S.D.O. and V.I.T. has been supported in part by CONACyT grant 28454E and that by S.D.O. in part by CONACyT(CP, ref.990356).

## A Remarks on gravitational perturbations around hyperbolic brane

In , the AdS4 branes in AdS5 were discussed and the existence of the massive normalizable mode of graviton was found. In these papers, the tensions of the branes are free parameters but in the case treated in the present paper, the tension is dynamically determined.

Let us study the role of dynamically generated tension in getting of massive graviton modes. Moreover, we consider dilatonic brane-world. We now regard the brane as an object with a tension $`U(\varphi )`$ and assume the brane can be effectively described by the folowing action:

$$S_{\mathrm{brane}}=\frac{1}{16\pi G}d^4x\sqrt{g_{(4)}}U(\varphi ).$$
(A1)
If one assumes the metric in the form of (26), then using the Einstein equation, we find

$$_z^2A+4\left(_zA\right)^2=k\mathrm{e}^{2A}+\frac{4}{l^2}+\frac{\mathrm{\Phi }(\varphi )}{3}\frac{U(\varphi )}{6}\delta (zz_0).$$
(A2)
Then at $`z=z_0`$,

$$_zA|_{z=z_0}=\frac{U(\varphi )}{12}.$$
(A3)
For simplicity, we consider the case of the constant dilaton potential $`\mathrm{\Phi }(\varphi )=0`$. Comparing (A3) with (56) and (58), one gets

$$U(\varphi )=\frac{12}{l}+\frac{96\pi Gb^{}}{R^4}.$$
(A4)
We should note that the tension becomes $`R`$ dependent due to the quantum correction. In case of AdS brane $`k<0`$, if no dilaton is included, the boundary equation (58) does not have any solution for $`R`$. When there is non-trivial dilaton and the parameter $`c`$ is large enough, Eq.(58) has a solution. If $`c`$ is very large

$$R^4\frac{c}{\pi G}+8b^{}.$$
(A5)
We now consider the perturbation by assuming the metric in the following form:

$$ds^2=\mathrm{e}^{2\widehat{A}(\zeta }\left(d\zeta ^2+\left(\widehat{g}_{\mu \nu }+\mathrm{e}^{\frac{3}{2}\widehat{A}(\zeta )}h_{\mu \nu }\right)dx^\mu dx^\nu \right).$$
(A6)
By choosing the gauge conditions $`h_\mu ^\mu =0`$ and $`^\mu h_{\mu \nu }=0`$, one obtains the following equation

$$\left(_\zeta ^2+\frac{9}{4}\left(_\zeta \widehat{A}\right)^2+\frac{3}{2}_\zeta ^2\widehat{A}\right)h_{\mu \nu }=m^2h_{\mu \nu }$$
(A7)
Here $`m^2`$ corresponds to the mass of the graviton on the brane

$$\left(\widehat{\mathrm{}}\pm \frac{1}{R^2}\right)h_{\mu \nu }=m^2h_{\mu \nu }.$$
(A8)
Here $`\widehat{\mathrm{}}`$ is 4- dimensional d’Alembertian constructed on $`\widehat{g}_{\mu \nu }`$ and the $`+`$ ($``$) sign corresponds to (anti-)de Sitter brane. Since $`\mathrm{e}^Ad\zeta =dz=\sqrt{f}dy`$ and $`\mathrm{e}^A=\frac{\sqrt{y}}{l}`$, we find, especially for the case of the constant dilaton potential,

$$\zeta =𝑑y\sqrt{\frac{f(y)}{y}}=\frac{l^2}{2}\frac{dy}{\sqrt{y^3\left(1+\frac{c^2l^2}{24y^4}+\frac{kl^2}{3y}\right)}}.$$
(A9)
We now consider the case that $`c`$ is very large, then

$$f(y)\frac{6y^2}{c^2}.$$
(A10)
Since $`y_0=R^2`$ if there is a brane at $`y=y_0`$, Eq.(A5) can be rewritten as

$$y_0^2\frac{c}{\pi G}+8b^{}.$$
(A11)
If we choose $`\zeta =0`$ when $`y=y_0`$, Eqs.(A9) and (A10) give

$$|\zeta |=\frac{1}{|c|}\sqrt{\frac{8}{3}}y^{\frac{3}{2}}+\zeta _0,\zeta _0\frac{1}{|c|}\sqrt{\frac{8}{3}}y_0^{\frac{3}{2}}>0.$$
(A12)
Note that the brane separates two bulk regions corresponding to $`\zeta <0`$ and $`\zeta >0`$, respectively. Since $`y`$ takes the value in $`[0,y_0]`$, $`\zeta `$ takes the value in $`[\zeta _0,\zeta _0]`$. Since $`A=\frac{1}{2}\mathrm{ln}y`$, from (A7), one gets

$$\left(_\zeta ^2\frac{1}{4\left(|\zeta |\zeta _0\right)^2}\frac{1}{\zeta _0}\delta (\zeta )\right)h_{\mu \nu }=m^2h_{\mu \nu }$$
(A13)
The zero mode solution with $`m^2`$ of (A13) is given by

$$h_{\mu \nu }=\sqrt{\zeta _0|\zeta |}.$$
(A14)
The general solution of (A13 with $`m^20`$ is given by the Bessel functions:

$$h_{\mu \nu }=aJ_0\left(m\left(\zeta _0|\zeta |\right)\right)+bN_0\left(m\left(\zeta _0|\zeta |\right)\right).$$
(A15)
The coefficients $`a`$ and $`b`$ are constants of the integration and they are determined to satisfy the boundary condition

$$\frac{_\zeta h_{\mu \nu }}{h_{\mu \nu }}|_{\zeta 0+}=\frac{1}{2\zeta _0}.$$
(A16)
Note that zero mode solution (A14) satisfies this boundary condition (A16). If $`b0`$, the solution in (A15) diverges at $`\zeta =\pm \zeta _0`$ and would not be normalizable. If $`b=0`$, the condition (A16) reduces to

$$J_1(m\zeta _0)=0,$$
(A17)
that is

$$m\zeta _0=0,\mathrm{\hspace{0.17em}3.8317}\mathrm{},\mathrm{\hspace{0.17em}7.0155}\mathrm{},\mathrm{}.$$
(A18)
The non-vanishing solutions for $`m^2`$ give the mass of the massive graviton modes. Thus, these results indicate that 4d dilatonic gravity on quantum induced hyperbolic brane may be trapped near the brane.

Since $`\zeta _0`$ is given by $`y_0`$ in (A12) and $`y_0`$ is expressed by (A11), with the help of $`b^{}`$, which comes from the quantum correction and is negative, the quantum correction makes $`\zeta _0`$ smaller and increases the massive graviton mode mass $`m`$. It would be of interest to discuss graviton/dilaton perturbations around asymptotically hyperbolic brane in other regimes and to compare the corresponding predictions in different frames.


format: text

text:
# Total Protection of Analytic Invariant Information in Cross Tabulated TablesA preliminary version of this work appeared in Proc. 11th Annual Symposium on Theoretical Aspects of Computer Science, Caen, France, February 24–26, 1994, pp. 723–734.

## 1 Introduction

Cross tabulated tables are used in a wide variety of documents to organize and exhibit information, often with the values of some cells suppressed in order to conceal sensitive information. Concerned with the effectiveness of the practice of cell suppression , statisticians have raised two fundamental issues and developed computational heuristics to various related problems . The detection issue is whether an adversary can deduce significant information about the suppressed cells from the published data of a table. The protection issue is how a table maker can suppress a small number of cells in addition to the sensitive ones so that the resulting table does not leak significant information.

This paper investigates the complexity of how to protect a broad class of information contained in a two-dimensional table that publishes (1) the values of all cells except a set of sensitive ones, which are suppressed, and (2) an upper bound and a lower bound for each cell, and (3) all row sums and column sums of the complete set of cells. The cells may have real or integer values. They may have different bounds, and the bounds may be finite or infinite. The upper bound of a cell should be strictly greater than its lower bound; otherwise, the value of that cell is immediately known even if that cell is suppressed. The cells that are not suppressed also have upper and lower bounds. These bounds are necessary because some of the unsuppressed cells may later be suppressed to protect the information in the sensitive cells. (See Figures 1 and 2 for an example of a complete table and its published version.)

An unbounded feasible assignment to a table is an assignment of values to the suppressed cells such that each row or column adds up to its published sum. An bounded feasible assignment is an unbounded one that also obeys the bounds of the suppressed cells. An analytic function of a table is a power series of the suppressed cells, each regarded as a variable, such that the convergence radius is $`\mathrm{}`$ . An analytic invariant is an analytic function that has a unique value at all the bounded feasible assignments. If an analytic invariant is formed by a linear combination of the suppressed cells, then it is called a linear invariant . Similarly, a suppressed cell is called an invariant cell  if it is an invariant by itself. For instance, in the published table in Figure 2, let $`X_{p,q}`$ be the cell at row $`p`$ and column $`q`$. $`X_{6,i}`$ is an invariant because it is the only suppressed cell in row $`6`$. $`X_{2,c}`$ and $`X_{3,c}`$ are invariant cells because their values are between 0 and 9.5, their sum is 19, and both cells are forced to have the same unique value $`9.5`$. Consequently, $`(X_{3,c}X_{2,c}+0.5X_{2,c}95)^2X_{1,b}+\mathrm{sin}(X_{2,c}X_{2,a}9.5X_{2,a})`$ is also an invariant.

Intuitively, the information contained in an analytic invariant is unprotected because its value can be uniquely deduced from the published data. In this paper, a set of suppressed cells is totally protected if there exists no analytic invariant in terms of the suppressed cells in the given set, except the trivial invariant that contains no nonzero terms. As the analytic power series form a very broad family of mathematical functions, total protection conceals from the adversary a very large class of information. This paper gives a very simple algorithm for testing whether a given set of suppress cells is totally protected. When a graph representation, called the suppressed graph, of a table is given as input, this algorithm runs in optimal $`O(m+n)`$ time, where $`m`$ is the number of suppressed cells and $`n`$ is the total number of rows and columns. This paper also considers the problem of computing and suppressing the minimum number of additional cells so that a given set of original suppressed cells becomes totally protected. This problem is shown to be NP-complete. For a large class of tables, this optimal suppression problem can be solved in $`O((m+n)\alpha (n,m+n))`$ time, where $`\alpha `$ is an Ackerman’s inverse function and its value is practically a small constant . Moreover, for this class of tables, every optimal set of cells for additional suppression forms a spanning forest of some sort. As a consequence, at most $`n1`$ additional cells need to be suppressed to achieve the total protection of a given set of original suppressed cells. As the size of a table may grow quadratically in $`n`$, the suppression of $`n1`$ additional cells is a negligible price to pay for total protection for a reasonably large table.

Previously, four other levels of data security have been considered that protect information contained, respectively, in individual suppressed cells , in a row or column as a whole, in a set of $`k`$ rows or $`k`$ columns as a whole, and in a table as a whole . These four levels of data security and total protection differ in two major aspects. First, these four levels of data security primarily protect information expressible as linear invariants, whereas total protection protects the much broader class of analytic invariant information. Second, these four levels of data security emphasize protecting regular regions of a table, whereas total protection protects any given set of suppressed cells and is more flexible. These four levels of data security and total protection share some interesting similarities. As total protection corresponds to spanning forests in suppressed graphs, these four levels of data security are equivalent to some forms of 2-edge connectivity , 2-vertex connectivity, $`k`$-vertex connectivity and graph completeness . In this paper, the NP-completeness results and efficient algorithms for total protection rely heavily on its graph characterizations. Similarly, the equivalence characterizations of these four levels of data security have been key in obtaining efficient algorithms  and NP-completeness proofs  for various detection and protection problems.

Section 2 discusses basic concepts. Section 3 formally defines the notion of total protection and gives a linear-time algorithm to test for this notion. Sections 4 and 5 give NP-completeness results and efficient algorithms for optimal suppression problems of total protection. Section 6 concludes this paper with discussions.

## 2 Basics of two-dimensional tables

This section discusses basic relationships between tables and graphs.

A mixed graph is one that may contain both undirected and directed edges. A traversable cycle or path in a mixed graph is one that can be traversed along the directions of its edges. A direction-blind cycle or path is one that can be traversed if the directions of its edges are disregarded. The word direction-blind is often omitted for brevity. A mixed graph is connected (respectively, strongly connected) if each pair of vertices are contained in a direction-blind path (respectively, traversable cycle). A connected component (respectively, strongly connected component) of a mixed graph is a maximal subgraph that is connected (respectively, strongly connected). A set of edges in a mixed graph is an edge cut if its removal disconnects one or more connected components of that graph. An edge cut is a minimal one if it has no proper subset that is also an edge cut.

From this point onwards, let $`𝒯`$ be a table, and let $`^{}=(A,B,E^{})`$ and $`=(A,B,E)`$ be the bipartite mixed graphs constructed below. $`^{}`$ and $``$ are called the total graph and the suppressed graph of $`𝒯`$, respectively . For each row (respectively, column) of $`𝒯`$, there is a unique vertex in $`A`$ (respectively, $`B`$). This vertex is called a row (respectively, column) vertex. For each cell $`X_{i,j}`$ at row $`i`$ and column $`j`$ in $`𝒯`$, there is a unique edge $`e`$ in $`E`$ between the vertices of row $`i`$ and column $`j`$. If the value of $`X_{i,j}`$ is strictly between its bounds, then $`e`$ is undirected. Otherwise, if the value is equal to the lower (respectively, upper) bound, then $`e`$ is directed towards to its column (respectively, row) endpoint. Note that $`^{}`$ is a complete bipartite mixed graph, i.e., there is exactly one edge between each pair of vertices from the two vertex sets of the graph. The graph $``$ is the subgraph of $`^{}`$ whose edge set consists of only those corresponding to the suppressed cells of $`𝒯`$. Figure 3 illustrates a table and its suppressed graph. For convenience, a row or column of $`𝒯`$ will be regarded as a vertex in $``$ and a cell as an edge, and vice versa.

###### Theorem 1 ().

A suppressed cell of $`𝒯`$ is an invariant cell if and only if it is not in an edge-simple traversable cycle of $``$.

The effective area of an analytic function $`F`$ of $`𝒯`$, denoted by $`EA(F)`$, is the set of variables in the nonzero terms of $`F`$. The function $`F`$ is called nonzero if $`EA(F)\mathrm{}`$. Note that because the convergence radius of $`F`$ is $`\mathrm{}`$, $`EA(F)`$ is independent of the point at which $`F`$ is expanded into a power series.

###### Theorem 2 ().

For every minimal edge cut $`Y`$ of a strongly connected component of $``$, $`𝒯`$ has a linear invariant $`F`$ with $`EA(F)`$ = $`Y`$.

The bounded kernel (respectively, unbounded kernel) of $`𝒯`$, denoted by $`BK(𝒯)`$ (respectively, $`UK(𝒯)`$), is the real vector space consisting of all linear combinations of $`xy`$, where $`x`$ and $`y`$ are arbitrary bounded (respectively, unbounded) feasible assignments of $`𝒯`$.

Because $``$ is bipartite, every cycle of $``$ is of even length. Thus, the edges of an edge-simple direction-blind cycle of $``$ can be alternately labeled with $`+1`$ and $`1`$. Such a labeling is called a direction-blind labeling. A direction-blindly labeled cycle is regarded as an assignment to the suppressed cells of $`𝒯`$. If the corresponding edge of a suppressed cell is in the given cycle, then the value assigned to that cell is the label of that edge; otherwise, the value is 0. Note that this assignment needs not be an unbounded feasible assignment of $`𝒯`$.

###### Theorem 3 ().

1. $`UK(𝒯)=BK(𝒯)`$ if every connected component of $``$ is strongly connected.
2. Every direction-blindly labeled cycle of $``$ is a vector in $`UK(𝒯)`$.

## 3 Total protection

A set $`Q`$ of suppressed cells of $`𝒯`$ is totally protected in $`𝒯`$ if there is no nonzero analytic invariant $`F`$ of $`𝒯`$ with $`EA(F)Q`$. The goal of total protection can be better understood by considering $`Q`$ as the set of suppressed cells that contain sensitive data. The total protection of $`Q`$ means that no precise analytic information about these data, not even their row and column sums, can be deduced from the published data of $`𝒯`$. As analytic power series form a very large class of functions in mathematical sciences, this notion of protection requires a large class of information about $`Q`$ to be concealed from the adversary.

The next lemma and theorem characterize the notion of total protection in graph concepts.

###### Lemma 4.

If $`F`$ is a nonzero analytic invariant of $`𝒯`$ such that the edges in $`EA(F)`$ are contained in the strongly connected components of $``$, then for some strongly connected component $`D`$ of $``$, $`EA(F)D`$ is an edge cut of $`D`$.

Remark. The converse of this lemma is not true; for a counter example, consider the linear combination $`X_{1,a}+2X_{1,b}`$ for the table in Figure 3. Also, if $`F`$ is a nonzero linear invariant, then for every strongly connected component $`D`$ of $``$, the set $`DEA(F)`$ is either empty or is an edge cut of $`D`$ .

###### Proof.

Let $`𝒯_s`$ be the table constructed from $`𝒯`$ by also publishing the suppressed cells that are not in the strongly connected components of $``$. By Theorem 1, $`F`$ remains a nonzero analytic function of $`𝒯_s`$. Also, the connected components of the suppressed graph $`_s`$ of $`𝒯_s`$ are the strongly connected components of $``$. Thus, to prove the lemma, it suffices to prove it for $`𝒯_s`$, $`_s`$, and $`F`$.

Let $`x_0`$ be a fixed bounded feasible assignment of $`𝒯_s`$. Let $`K=\{xx_0|x`$ is a bounded feasible assignment of $`𝒯_s\}`$. Since $`F`$ is an analytic invariant of $`𝒯_s`$, the function $`G(x)=F(x)F(x_0)`$ is an analytic invariant of $`𝒯_s`$ with $`EA(G)=EA(F)`$ and its value is zero over $`x_0+K`$. Because $`K`$ contains a nonempty open subset of $`BK(𝒯_s)`$, $`G`$ is zero over $`x_0+BK(𝒯_s)`$. By Theorem 3(1) and the strong connectivity of the connected components of $`_s`$, $`BK(𝒯_s)=UK(𝒯_s)`$ and $`G`$ is zero over $`x_0+UK(𝒯_s)`$. Thus, it suffices to show that if $`DEA(F)`$ is connected for all connected components $`D`$ of $`_s`$, then $`G(x_0+z_0)0`$ for some $`z_0UK(𝒯_s)`$. To construct $`z_0`$, let $`EA(G)=\{e_1,\mathrm{},e_k\}`$. Let $`D_i`$ be the connected component of $`_s`$ that contains $`e_i`$. By the connectivity of $`D_iEA(F)`$, there is a vertex-simple path $`P_i`$ in $`D_iEA(F)`$ between the endpoints of $`e_i`$. Let $`C_i`$ be the vertex-simple cycle formed by $`e_i`$ and $`P_i`$. Next, direction-blindly label $`C_i`$ with $`e_i`$ labeled $`+1`$. Since $`G`$ is a nonzero power series, $`G(x_0+y_0)0`$ for some vector $`y_0`$. Note that $`y_0`$ is not necessarily in $`UK(𝒯_s)`$. So, let $`z_0=_{i=1}^kh_iC_i`$, where $`h_i`$ is the component of $`y_0`$ at variable $`e_i`$. Then, by Theorem 3(2), $`z_0UK(𝒯_s)`$. Because $`P_i`$ is in $`_sEA(F)`$, $`e_i`$ appears only in the term $`C_i`$ in $`_{i=1}^kh_iC_i`$. Thus $`z_0`$ and $`y_0`$ have the same component values at the variables in $`EA(G)`$. Since the variables not in $`EA(G)`$ do not appear in any expansion of $`G`$, $`G(x_0+z_0)=G(x_0+y_0)0`$, proving the lemma. ∎

###### Theorem 5.

A set $`Q`$ of suppressed cells is totally protected in $`𝒯`$ if and only if the two statements below are both true:

1. The edges in $`Q`$ are contained in the strongly connected components of $``$.
2. For each strongly connected component $`D`$ of $``$, the graph $`DQ`$ is connected.

###### Proof.

It is equivalent to show that $`Q`$ is not totally protected if and only if $`Q`$ contains some edges not in the strongly connected components of $``$ or for some strongly connected component $`D`$ of $``$, the graph $`DQ`$ is not connected. The $``$ direction follows from Lemma 4. As for the $``$ direction, if $`Q`$ contains some edges not in the strongly connected components of $``$, then by Theorem 1, $`Q`$ contains some invariant cells of $`𝒯`$ and thus cannot be totally protected. If for some strongly connected component $`D`$ of $``$, the graph $`DQ`$ is not connected, then some subset $`Y`$ of $`Q`$ is a minimal edge cut of $`D`$. By Theorem 2, $`𝒯`$ has a linear invariant $`F`$ with $`EA(F)=Y`$ and thus $`Q`$ is not totally protected. ∎

This paper investigates the following two problems concerning how to achieve total protection.

###### Problem 1 (Protection Test).

* Input: The suppressed graph $``$ and a set $`Q`$ of suppressed cells of a table $`𝒯`$.
* Output: Is $`Q`$ totally protected in $`𝒯`$?

###### Theorem 6.

Problem 1 can be solved in linear time in the size of $``$.

###### Proof.

This problem can be solved within the desired time bound by means of Theorem 5 and linear-time algorithms for computing connected components and strongly connected components . ∎

###### Problem 2 (Optimal Suppression).

* Input: A table $`𝒯`$, a subset $`Q`$ of $`E`$, and an integer $`p0`$, where $`E`$ is the set of all suppressed cells in $`𝒯`$.
* Output: Is there a set $`P`$ consisting of at most $`p`$ published cells of $`𝒯`$ such that $`Q`$ is totally protected in the table $`\overline{𝒯}`$ formed by $`𝒯`$ with the cells in $`P`$ also suppressed?

This problem is clearly in NP. Section 4 shows that this problem with $`Q=E`$ is NP-complete. In contrast, Section 5 proves that if the total graph of $`𝒯`$ is undirected, then this problem with general $`Q`$ can be solved in almost linear time.

## 4 NP-completeness of optimal suppression

Throughout this section, the total graph of $`𝒯`$ may or may not be undirected.

###### Theorem 7.

Problem 2 with $`Q=E`$ is NP-complete.

To prove this theorem, the idea is to first transform Problem 2 with $`Q=E`$ to the following graph problem and then prove the NP-completeness of the graph problem.

###### Problem 3.

* Input: A complete bipartite mixed graph $`^{}=(A,B,E^{})`$, a subgraph $`=(A,B,E)`$, and an integer $`p0`$.
* Output: Does any set $`P`$ of at most $`p`$ edges in $`E^{}E`$ hold the following two properties?

1. Property N1: Every connected component of $`(A,B,EP)`$ is strongly connected.
2. Property N2: The vertices of each connected component of $``$ are connected in $`(A,B,P)`$, i.e., contained in a connected component in $`(A,B,P)`$.

###### Lemma 8.

Problem 2 with $`Q=E`$ and Problem 3 can be reduced to each other in linear time.

###### Proof.

Given an instance $`𝒯`$ and $`p`$ of Problem 2 with $`Q=E`$, the desired instance of Problem 3 is the total graph $`^{}=(A,B,E^{})`$ and the suppressed graph $`=(A,B,E)`$ of $`𝒯`$, and $`p`$ itself. This transformation can easily be computed in linear time. There are two directions to show that it reduces Problem 2 to Problem 3. Assume that $`P`$ is a desired set for Problem 3. By Property N1, Statement 1 in Theorem 5 is true. Also, every strongly connected component of $`(A,B,EP)`$ is a union of edge-disjoint connected components in $``$ and $`(A,B,P)`$. Therefore, by Property N2, Statement 2 of Theorem 5 holds. As a result, $`P`$ itself is a desired set for Problem 2. On the other hand, assume that $`P`$ is a desired set for Problem 2. Let $`P^{}`$ be the set of all edges in $`P`$ that are also in the strongly connected components of $`(A,B,EP)`$. By Statement 1 of Theorem 5 and the total protection of $`E`$ in $`\overline{𝒯}`$, the connected components of $`(A,B,EP^{})`$ are the strongly connected components of $`(A,B,EP)`$. Thus, $`P^{}`$ holds Property N1. Next, because a connected component of $``$ is included in a strongly connected component of $`(A,B,EP^{})`$, by Statement 2 of Theorem 5, $`P^{}`$ also holds Property N2 and thus is a desired set for Problem 3.

Given an instance $`^{}`$, $``$, and $`p`$ of Problem 3, the desired instance of Problem 2 with $`Q=E`$ is $`p`$ itself and the table defined as follows. For each vertex in $`A`$ (respectively, $`B`$), there is a row (respectively, column). The upper and lower bounds for each cell are 2 and 0. For each edge $`e`$ in $`E^{}`$, its corresponding cell is at the row and column corresponding to its endpoints. The value of that cell is 1 (respectively, 0 and 2) if $`e`$ is undirected (respectively, directed from $`A`$ to $`B`$, or directed from $`B`$ to $`A`$). For each edge $`e`$ in $``$, its corresponding cell is suppressed. Note that the total and suppressed graphs of this table are $`^{}`$ and $``$ themselves. Thus, the remaining proof details for this reduction are essentially the same as for the other reduction. ∎

Both Problem 2 with $`Q=E`$ and Problem 3 are clearly in NP. To prove their completeness in NP, by Lemma 8 it suffices to reduce the following NP-complete problem to Problem 3.

###### Problem 4 (Hitting Set ).

* Input: A finite set $`S`$, a nonempty family $`W`$ of subsets of $`S`$, and an integer $`h0`$.
* Output: Is there a subset $`S^{}`$ of $`S`$ such that $`|S^{}|h`$ and $`S^{}`$ contains at least one element in each set in $`W`$?

Given an instance $`S=\{s_1,\mathrm{},s_q\}`$, $`W=\{S_1,\mathrm{},S_r\}`$, $`h`$ of Problem 4, an instance $`^{}=(A,B,E^{}),=(A,B,E),p`$ of Problem 3 is constructed as follows:

* Rule 1: Let $`A=\{a_0,a_1,\mathrm{},a_q\}`$. The vertices $`a_1,\mathrm{},a_q`$ correspond to $`s_1,\mathrm{},s_q`$, but $`a_0`$ corresponds to no $`s_i`$.
* Rule 2: Let $`B=\{b_0,b_1,\mathrm{},b_r\}`$. The vertices $`b_1,\mathrm{},b_r`$ correspond to $`S_1,\mathrm{},S_r`$ of $`S`$, but $`b_0`$ corresponds to no $`S_j`$.
* Rule 3: Let $`E^{}`$ be the union of the following sets of edges:

1. $`\{b_0a_0\}`$.
    2. $`\{a_0b_j`$ $`j`$ with $`1jr\}`$.
    3. $`\{a_ib_0`$ $`i`$ with $`1iq\}`$.
    4. $`\{b_ja_i`$ $`s_i`$ and $`S_j`$ with $`s_iS_j\}`$.
    5. $`\{a_ib_j`$ $`s_i`$ and $`S_j`$ with $`s_iS_j\}`$.
* Rule 4: Let $`E=\{a_0b_1,\mathrm{},a_0b_r\}`$.
* Rule 5: Let $`p=h+r+1`$.

The above construction can easily be computed in polynomial time. The next two lemmas show that it is indeed a desired reduction.

###### Lemma 9.

If some set $`S^{}S`$ with $`|S^{}|h`$ contains at least one element in each $`S_j`$, then there is a set $`PE^{}E`$ consisting of at most $`p`$ edges that holds Properties N1 and N2.

###### Proof.

For each $`S_j`$, let $`s_{i_j}`$ be an element in $`S^{}S_j`$; by the assumption of this lemma, these elements exist. Next, let $`P_1=\{b_1a_{i_1},\mathrm{},b_ra_{i_r}\}`$ and $`P_2=\{a_{i_1}b_0,\mathrm{},a_{i_r}b_0\}`$; by Rule 3, these two sets exist. Now, let $`P=P_1P_2\{b_0a_0\}`$. Note that $`PE^{}E`$. Since $`P_1`$ consists of $`r`$ edges and $`P_2`$ consists of at most $`|S^{}|`$ edges, $`P`$ has at most $`p`$ edges. $`P`$ holds Property N1 because $`EP`$ consists of the edges in the traversable cycles $`b_0a_0,a_0b_j,b_ja_{i_j},a_{i_j}b_0`$. Property N2 of $`P`$ follows from the fact that $`P`$ connects $`\{a_0,b_1,\mathrm{},b_r\}`$, which forms the only connected component of $``$ with more than one vertex. ∎

###### Lemma 10.

If some set $`PE^{}E`$ consisting of at most $`p`$ edges holds Properties N1 and N2, then there exists a set $`S^{}S`$ with $`|S^{}|h`$ that contains at least one element in each $`S_j`$.

###### Proof.

By Property N1, $`P`$ must contain some edge $`b_ja_{i_j}`$ for each $`j`$ with $`1jr`$. By Rule 3(4), $`s_{i_j}S_j`$. Now let $`S^{}=\{s_{i_1},\mathrm{},s_{i_r}\}`$. To calculate the size of $`S^{}`$, note that by Property N1, $`P`$ must also contain $`b_0a_0`$ and at least one edge leaving $`a_{i_j}`$ for each $`j`$. Thus $`|P||S^{}|+r+1`$. Then $`|S^{}|h`$ because $`|P|p=r+h+1`$. ∎

The above lemma completes the proof of Theorem 7.

## 5 Optimal suppression in almost linear time

Under the assumption that the total graph of $`𝒯`$ is undirected, this section considers the following optimization version of Problem 2.

###### Problem 5 (Optimal Suppression).

* Input: The suppressed graph $`=(A,B,E)`$ of a table $`𝒯`$ and a subset $`Q`$ of $`E`$.
* Output: A set $`P`$ consisting of the smallest number of published cells in $`𝒯`$ such that $`Q`$ is totally protected in the table $`\overline{𝒯}`$ formed by $`𝒯`$ with the cells in $`P`$ also suppressed.

For all positive integers $`n`$ and $`m`$, let $`\alpha `$ denote the best known function such that $`m+n`$ unions and finds of disjoint subsets of an $`n`$-element set can be performed in $`O((m+n)\alpha (n,m+n))`$ time .

###### Theorem 11.

Problem 5 can be solved in $`O((m+n)\alpha (n,m+n))`$ time, where $`m`$ is the number of suppressed cells and $`n`$ is the total number of rows and columns in $`𝒯`$.

To prove Theorem 11, Problem 5 is first converted to the next problem.

###### Problem 6.

* Input: An undirected bipartite graph $`=(A,B,E)`$ and a subset $`Q`$ of $`E`$.
* Output: A forest $`P`$ formed by the smallest number of undirected edges between $`A`$ and $`B`$ but not in $`E`$ such that the vertices of each connected component of $`(A,B,Q)`$ are connected in $`(A,B,(EQ)P)`$, i.e., contained in a connected component of $`(A,B,(EQ)P)`$.

###### Lemma 12.

Problems 5 and 6 can be reduced to each other in linear time.

###### Proof.

The proof uses arguments similar to those in the proof of Lemma 8. The strong connectivity properties in Problem 3 and Theorem 5 can be ignored because this section assumes that the total graph of $`𝒯`$ is undirected. The forest structure of $`P`$ follows from its minimality. ∎

Note that because $`QE`$, the vertices of each connected component of $`(A,B,Q)`$ are connected in $`(A,B,(EQ)P)`$ if and only if the vertices of each connected component of $``$ are connected in $`(A,B,(EQ)P)`$. Using this equivalence, the next stage of the proof of Theorem 11 further reduces Problem 6 to another graph problem with the steps below:

* Compute the connected components $`D_1,\mathrm{},D_r`$ of $``$.
* For each $`D_i`$, compute a maximal forest $`K_i`$ over the vertices of $`D_i`$ using only the edges in $`EQ`$.
* For each $`D_i`$, extend $`K_i`$ to a maximal forest $`L_i`$ over the vertices of $`D_i`$ using additional edges only from the complement graph $`D_i^c`$ of $`D_i`$.
* Construct a graph $`\widehat{}`$ from $``$ by contracting each tree in each $`L_i`$ into a single vertex.
* For each $`D_i`$, compute its contracted version $`\widehat{D}_i`$ in $`\widehat{}`$.
* Divide the vertices of $`\widehat{}`$ into three sets, $`V_A`$, $`V_B`$, $`V_{AB}`$, where a vertex in $`V_A`$ (respectively, $`V_B`$) consists of a single vertex from $`A`$ (respectively, $`B`$), and a vertex in $`V_{AB}`$ contains at least two vertices (thus with at least one from each of $`A`$ and $`B`$).

A set of undirected edges between vertices in $`V_A,V_B,V_{AB}`$ is called semi-tripartite if every edge in that set is between two of the three sets or is between two vertices in $`V_{AB}`$. Note that the set of edges in $`\widehat{}`$ is semi-tripartite.

###### Problem 7.

* Input: Three disjoint finite sets $`V_A,V_B,V_{AB}`$, and a partition $`\widehat{D_1},\mathrm{},\widehat{D_r}`$ of $`V_AV_BV_{AB}`$.
* Output: A semi-tripartite set $`\widehat{P}`$ consisting of the smallest number of edges such that no edge in $`\widehat{P}`$ connects two vertices in the same $`D_i`$ and the vertices in each $`D_i`$ are connected in the graph formed by is $`\widehat{P}`$.

###### Lemma 13.

Problem 6 can be reduced to Problem 7 in $`O((m+n)\alpha (n,m+n))`$ time, where $`m`$ is the number of edges and $`n`$ is the number of vertices in $``$.

###### Proof.

The key idea is that an optimal $`P`$ for Problem 6 can be obtained by connecting the vertices of each $`D_i`$ first with edges in $`EQ`$, which can be used for free, next with edges in $`D_i^c`$, and then with edges outside $`D_iD_i^c`$. Let $`P^{}`$ be a set of $`|\widehat{P}|`$ edges in the complement of $``$ that becomes $`\widehat{P}`$ after Step M4. Then, $`P^{}(L_1K_1)\mathrm{}(L_rK_r)`$ is a desired output $`P`$ for Problem 6, showing that Steps M1–M6 can indeed reduce Problem 6 to Problem 7. Step M3 is the only step that requires more than linear time. It is important to avoid directly computing $`D_i^c`$ at Step M3. Computing these complement graphs takes $`\mathrm{\Theta }(|A||B|)`$ time if some $`D_i`$ contains a constant fraction of the vertices in $``$. In such a case, if $``$ is sparse, then the time spent on computing $`D_i^c`$ alone is far greater than the desired complexity. Instead of this naive approach, Step M3 uses efficient techniques recently developed for complement graph problems  and takes the desired $`O((m+n)\alpha (n,m+n))`$ time. ∎

The last stage of the proof of Theorem 11 is to give a linear-time algorithm for Problem 7. A component $`\widehat{D_i}`$ is good if it has at least two vertices with at least one from $`V_{AB}`$; it is bad if it has at least two vertices with none from $`V_{AB}`$ (and thus with at least one from each of $`V_A`$ and $`V_B`$). The goal is to use as few edges as possible to connect the vertices in each of these components. Let $`w_g`$ and $`w_b`$ be the numbers of good and bad components, respectively. There are three cases based on the value of $`w_g`$.

Case 1: $`w_g=0`$. If $`w_b=0`$, then let $`\widehat{P}=\mathrm{}`$ because no $`\widehat{D_i}`$ needs to be connected. If $`w_b>0`$ and $`|V_{AB}|>0`$, then include in $`\widehat{P}`$ an edge between each vertex in the bad components and an arbitrary vertex in $`V_{AB}`$. If $`w_b>0`$ and $`|V_{AB}|=0`$, then there does not exist a desired $`\widehat{P}`$ and the given instance of Problem 7 has no solution.

Case 2: $`w_g=1`$. Let $`\widehat{D}_j`$ be the unique good component.

If $`w_b>0`$, then find a bad component $`\widehat{D}_k`$, and three vertices $`uV_{AB}\widehat{D}_j`$, $`v_1V_A\widehat{D}_k`$, $`v_2V_B\widehat{D}_k`$. Next, include in $`\widehat{P}`$ an edge between $`v_2`$ and each vertex in $`(\widehat{D}_j(V_AV_{AB}))\{u\}`$, an edge between $`v_1`$ and each vertex in $`\widehat{D}_jV_B`$, and an edge between $`u`$ and each vertex in the bad components.

If $`w_b=0`$ and $`V_{AB}\widehat{D}_j\mathrm{}`$, then include in $`\widehat{P}`$ an edge between every vertex in $`\widehat{D}_j`$ and an arbitrary vertex in $`V_{AB}\widehat{D}_j`$.

If $`w_b=0`$ and $`V_{AB}\widehat{D}_j=\mathrm{}`$, then there are sixteen subcases depending on whether $`V_A\widehat{D}_j=\mathrm{}`$, $`V_A\widehat{D}_j=\mathrm{}`$, $`V_B\widehat{D}_j=\mathrm{}`$, $`V_B\widehat{D}_j=\mathrm{}`$. If $`V_A\widehat{D}_j\mathrm{}`$, $`V_A\widehat{D}_j\mathrm{}`$, $`V_B\widehat{D}_j\mathrm{}`$, $`V_B\widehat{D}_j\mathrm{}`$, then include in $`\widehat{P}`$ an edge between each vertex in $`V_A\widehat{D}_j`$ and a vertex $`v_2V_B\widehat{D}_j`$, an edge between each vertex in $`V_B\widehat{D}_j`$ and a vertex $`v_1V_A\widehat{D}_j`$, and an edge between $`v_1`$ and each vertex in $`V_{AB}\{v_2\}`$. The other fifteen subcases are handled similarly.

Case 3: $`w_g2`$. Let $`d`$ be the total number of vertices in the good and bad components. Let $`w^{}`$ be the number of connected components in $`\widehat{P}`$ that contain the vertices of at least one good or bad $`\widehat{D}_i`$; let $`d^{}`$ be the number of vertices in these connected components of $`\widehat{P}`$ that are not in any good or bad $`\widehat{D}_i`$. By its minimality, $`\widehat{P}`$ forms a forest and $`|\widehat{P}|=d^{}+dw^{}`$. The techniques for Cases 1 and 2 can be used to show that there exists an optimal $`\widehat{P}`$ with $`d^{}=0`$. Thus, to minimize $`|\widehat{P}|`$ is to maximize $`w^{}`$. Because two bad components cannot be connected by edges between them alone, the strategy for maximizing $`w^{}`$ is to pair a good component with a bad one, whenever possible, and include in $`\widehat{P}`$ edges between them to connect their vertices into a tree. After this step, if there remain unconnected bad components but no unconnected good ones, then add to $`P`$ an edge between each vertex in the remaining bad components and an arbitrary vertex in the intersection of $`V_{AB}`$ and a good component. On the other hand, if there remain good components but no bad ones, then pair up these good components similarly. After this step, if there remains a good component, then add to $`\widehat{P}`$ an edge between each vertex in this last good component and an arbitrary vertex in the intersection of $`V_{AB}`$ and another good component. (As a result, if $`w_gw_b`$, then $`|\widehat{P}|=dw_g`$; otherwise, $`|\widehat{P}|=d\frac{w_g+w_b}{2}`$.)

The above discussion yields a linear-time algorithm for Problem 7 in a straightforward manner. This finishes the proof of Theorem 11.

## 6 Discussions

Lemma 12 has several significant implications. Since $`P`$ is a forest, it has at most $`n1`$ edges. Thus, for a table with an undirected total graph, no more than $`n1`$ additional cells need to be suppressed to achieve total protection. This is a small number compared to the size of the table, which may grow quadratically in $`n`$. Moreover, when $``$ is connected and $`E=Q`$, $`(A,B,P)`$ is a spanning tree. In this case, many well-studied tree-related computational concepts and tools, such as minimum-cost spanning trees, can be applied to consider other optimal suppression problems for total protection.

## Acknowledgements

The author is deeply grateful to Dan Gusfield for his constant encouragement and help. The author wishes to thank an anonymous referee for very helpful and thorough comments. The referee has also pointed out that some very interesting materials related to Theorems 2 and 3 have been developed in the context of protecting sums of suppressed cells .