format: text

text:
# Fully nonlinear equations on Riemannian manifolds with negative curvature

## 1 Introduction

Let $`(M^n,g)`$ be a compact, connected, $`n`$-dimensional Riemannian manifold, $`n3`$, and let the Ricci tensor and scalar curvature be denoted by $`Ric`$ and $`R`$, respectively. For a symmetric tensor $`A`$, we let $`\text{det}(A)`$ denote the determinant of $`A`$, that is, the product of the eigenvalues of $`A`$.

###### Theorem 1.1.

Assume that $`(M^n,g)`$ has negative Ricci curvature. Then there exists a unique conformal metric $`\stackrel{~}{g}=e^{2u}g`$ with negative Ricci curvature satisfying

$`\text{det}(Ric_{\stackrel{~}{g}})=\text{constant}.`$ (1.1)
By results of , , and , every compact manifold of dimension $`n3`$ admits a metric with negative Ricci curvature. Therefore we have

###### Corollary 1.1.

Every smooth compact $`n`$-manifold, $`n3`$, admits a Riemannian metric with $`Ric<0`$ and

$`\text{det}(Ric)=\text{constant}.`$ (1.2)
This theorem may be viewed as a Monge-Ampère version of a theorem of Aubin for the scalar curvature (). Theorem 1.1 is a special case of a more general theorem involving symmetric functions of eigenvalues of $`Ric`$, which we describe next. Let $`A`$ be a symmetric $`n\times n`$ matrix, and let $`\sigma _k(A)`$ denote the $`k`$th elementary symmetric of $`A`$.

###### Definition 1.

Let $`(\lambda _1,\mathrm{},\lambda _n)𝐑^n`$. We view the elementary symmetric functions as functions on $`𝐑^n`$

$$\sigma _k(\lambda _1,\mathrm{},\lambda _n)=\underset{i_1<\mathrm{}<i_k}{}\lambda _{i_1}\mathrm{}\lambda _{i_k},$$

and we define

$$\mathrm{\Gamma }_k^+=\text{component of }\{\sigma _k>0\}\text{ containing the positive cone}.$$

We also define $`\mathrm{\Gamma }_k^{}=\mathrm{\Gamma }_k^+`$.

For a symmetric linear transformation $`A:VV`$, where $`V`$ is an $`n`$-dimensional inner product space, the notation $`A\mathrm{\Gamma }_k^\pm `$ will mean that the eigenvalues of $`A`$ lie in the corresponding set. We note that this notation also makes sense for a symmetric tensor on a Riemannian manifold. If $`A\mathrm{\Gamma }_k^+`$, let $`\sigma _k^{1/k}(A)=\{\sigma _k(A)\}^{1/k}`$, and if $`A\mathrm{\Gamma }_k^{}`$, let $`\sigma _k^{1/k}(A)=|\sigma _k(A)|^{1/k}`$.

Let $`t𝐑`$, and define

$`A^t={\displaystyle \frac{1}{n2}}\left(Ric{\displaystyle \frac{t}{2(n1)}}Rg\right).`$ (1.3)
Note that for $`t=1`$, $`A^1`$ is the classical Schouten tensor ().

The following is our main theorem.

###### Theorem 1.2.

Assume that $`A_g^t\mathrm{\Gamma }_k^{}`$ for some $`t<1`$, and let $`f(x)<0`$ be any smooth function on $`M^n`$. Then there exists a unique conformal metric $`\stackrel{~}{g}=e^{2w}g`$ satisfying

$`\sigma _k^{1/k}(A_{\stackrel{~}{g}}^t)=f(x).`$ (1.4)
Note that we take the elementary symmetric function with respect to the metric $`\stackrel{~}{g}`$. As noted previously in , the $`C^2`$ estimate does not work for $`t=1`$, which is why we must make the restriction $`t<1`$. Also, for $`t>1`$, the equation is not necessarily elliptic, therefore $`t=1`$ is critical for several reasons. It is an interesting problem to investigate the limiting behaviour of the solutions in Theorem 1.2 as $`t1`$.

We next write this curvature equation as a partial differential equation. We have the following formula for the transformation of $`A^t`$ under a conformal change of metric $`\stackrel{~}{g}=e^{2w}g`$:

$`\stackrel{~}{A}^t`$ $`=A^t^2w{\displaystyle \frac{1t}{n2}}(\mathrm{\Delta }w)g+dwdw{\displaystyle \frac{2t}{2}}|w|^2g.`$ (1.5)
Since $`A^t=A^1+\frac{1t}{n2}tr(A^1)g`$, this formula follows easily from the standard formula for the transformation of the Schouten tensor (see ):

$`\stackrel{~}{A}^1=A^1^2w+dwdw(1/2)|w|^2g.`$ (1.6)
From (1.5), we may write (1.4) with respect to the background metric $`g`$

$`\sigma _k^{1/k}\left(^2w+{\displaystyle \frac{1t}{n2}}(\mathrm{\Delta }w)g+{\displaystyle \frac{2t}{2}}|w|^2gdwdwA_g^t\right)=f(x)e^{2w}>0.`$ (1.7)
In the following sections we will derive a priori estimates for solutions of (1.7), culminating in the existence proof in Section 6. In Section 7, we make some remarks on the positive curvature case.

We also point out that the Hessian equation

$`\sigma _k^{1/k}(^2w+S)=\mathrm{\Psi }(x,w)`$ (1.8)
where $`S`$ is a symmetric tensor was considered in , . For a general existence theorem, one must assume that the background metric has non-negative sectional curvature. We emphasize that, because of special properties of (1.7), we do not need such an assumption.

### 1.1 Acknowledgements

A substantial part of the research for this paper was carried out while both authors were visiting the Forschungsinstitut für Mathematik at ETH, Zurich. The authors wish to acknowledge the generous support of the Institute, and the hospitality of Professor Michael Struwe. The authors would also like to thank Pengfei Guan for helpful suggestions.

## 2 Ellipticity

In this section we will discuss the ellipticity properties of equation (1.7).

###### Definition 2.

Let $`A:VV`$ be a symmetric linear transformation, where $`V`$ is an $`n`$-dimensional inner product space. For $`0qn`$, the $`q`$th Newton transformation associated with $`A`$ is

$`T_q(A)=\sigma _q(A)I\sigma _{q1}(A)A+\mathrm{}+(1)^qA^q.`$
Several useful identities involving the Newton tranformation and elementary symmetric polynomials were derived in . First, if $`A_j^i`$ are the components of $`A`$ with respect to some basis of $`V`$, then

$`T_q(A)_j^i={\displaystyle \frac{1}{q!}}\delta _{j_1\mathrm{}j_qj}^{i_1\mathrm{}i_qi}A_{i_1}^{j_1}\mathrm{}A_{i_q}^{j_q}.`$ (2.1)
Here $`\delta _{j_1\mathrm{}j_qj}^{i_1\mathrm{}i_qi}`$ is the generalized Kronecker delta symbol, and we are using the Einstein summation convention. Also,

$`\sigma _k(A)={\displaystyle \frac{1}{k!}}\delta _{j_1\mathrm{}j_k}^{i_1\mathrm{}i_k}A_{i_1}^{j_1}\mathrm{}A_{i_k}^{j_k}.`$ (2.2)
We note that if $`A:𝐑\text{Hom}(V,V)`$, then

$`{\displaystyle \frac{d}{dt}}\sigma _k(A(t))=T_{k1}(A(t))_j^i{\displaystyle \frac{d}{dt}}A(t)_i^j=T_{k1}(A(t))^{ij}{\displaystyle \frac{d}{dt}}A(t)_{ij},`$ (2.3)
that is, the ($`k1`$)-Newton transformation is what we get when we differentiate $`\sigma _k`$. We also note the identities

$`\begin{array}{cc}\hfill T_{k1}(A)_j^iA_i^j& =k\sigma _k(A),\hfill \\ \hfill trT_{k1}(A)& =T_{k1}(A)_k^k=(nk+1)\sigma _k(A).\hfill \end{array}`$ (2.4)
The following Proposition describes some important properties of the cones $`\mathrm{\Gamma }_k^\pm `$, and their relation to the Newton transformations:

###### Proposition 2.1.

(i) Each set $`\mathrm{\Gamma }_k^+`$ is an open convex cone with vertex at the origin, and we have the following sequence of inclusions

$$\mathrm{\Gamma }_n^+\mathrm{\Gamma }_{n1}^+\mathrm{}\mathrm{\Gamma }_1^+.$$

(ii) If the eigenvalues of $`A`$ are in $`\mathrm{\Gamma }_k^+`$ (resp., $`\mathrm{\Gamma }_k^{}`$), then $`T_{k1}`$ is positive (resp., negative) definite.
(iii) For symmetric linear transformations $`A\mathrm{\Gamma }_k^+`$, $`B\mathrm{\Gamma }_k^+`$, and $`t[0,1]`$, we have the following inequality

$`\{\sigma _k((1t)A+tB)\}^{1/k}(1t)\{\sigma _k(A)\}^{1/k}+t\{\sigma _k(B)\}^{1/k}.`$ (2.5)
###### Proof.

The proof of this proposition is standard, and may be found in  and . ∎

Note that the inequality (2.5) states that $`\sigma _k^{1/k}`$ is a concave function in $`\mathrm{\Gamma }_k^+`$. This will be essential in proving the $`C^2`$ and $`C^{2,\alpha }`$ estimates in later sections.

###### Proposition 2.2.

If $`w`$ is a solution of (1.7) with $`A_g^t\mathrm{\Gamma }_k^{}`$ for some $`t1`$, then

$`\overline{}^2w`$ $`\mathrm{\Gamma }_k^+,\text{ where}`$
$`\overline{}^2w`$ $`^2w+{\displaystyle \frac{1t}{n2}}(\mathrm{\Delta }w)g+{\displaystyle \frac{2t}{2}}|w|^2gdwdwA_g^t`$
###### Proof.

Since $`M`$ is compact, at a minimum of the solution $`w`$ we have

$`\sigma _k^{1/k}\left(^2w(p)+{\displaystyle \frac{1t}{n2}}\mathrm{\Delta }w(p)gA_g^t(p)\right)=f(p)e^{2w(p)}>0,`$
with $`^2w(p)`$ positive semidefinite, and therefore $`^2w(p)+\frac{1t}{n2}\mathrm{\Delta }w(p)g0`$. From Proposition 2.1, we conclude that $`\overline{}^2w(p)\mathrm{\Gamma }_k^+`$. Since the cones are connected, by continuity we have $`\overline{}^2w\mathrm{\Gamma }_k^+`$. ∎

###### Proposition 2.3.

If $`A_g^t\mathrm{\Gamma }_k^{}`$ for some $`t1`$, then equation (1.7) is elliptic at any solution.

###### Proof.

We define

$`F_t[w,w,^2w]=\sigma _k(^2w`$ $`+{\displaystyle \frac{1t}{n2}}(\mathrm{\Delta }w)g+{\displaystyle \frac{2t}{2}}|w|^2gdwdwA_g^t)`$
$`|f(x)|^ke^{2kw},`$
so that solutions of (1.7) are exactly the zeroes of $`F_t`$. We then suppose that $`wC^2(M)`$ satisfies $`F_t[w,w,^2w]=0`$. Define $`w_s=w+s\phi `$, then

$`\begin{array}{cc}\hfill ^t(\phi )& ={\displaystyle \frac{d}{ds}}F_t[w_s,w_s,^2w_s]|_{s=0}\hfill \\ & ={\displaystyle \frac{d}{ds}}\left(\sigma _k(\overline{}^2w_s)\right)|_{s=0}{\displaystyle \frac{d}{ds}}\left(|f(x)|^ke^{2kw_s}\right)|_{s=0}.\hfill \end{array}`$ (2.6)
From (2.3), we have

$`{\displaystyle \frac{d}{ds}}\left(\sigma _k(\overline{}^2w_s)\right)|_{s=0}=T_{k1}(\overline{}^2w)_{ij}(\overline{}^2w_s)_{ij}^{}.`$
where

$`(\overline{}^2w_s)^{}={\displaystyle \frac{d}{ds}}\left(\overline{}^2w_s\right)|_{s=0}.`$
We compute

$`(\overline{}^2w_s)^{}=^2\phi +{\displaystyle \frac{1t}{n2}}(\mathrm{\Delta }\phi )g+(2t)dw,d\phi g2dwd\phi .`$
Therefore,

$`{\displaystyle \frac{d}{ds}}\left(\sigma _k(\overline{}^2w_s)\right)|_{s=0}=T_{k1}(\overline{}^2w)_{ij}(_i_j\phi `$ $`+{\displaystyle \frac{1t}{n2}}(\mathrm{\Delta }\phi )g_{ij}`$
$`+(2t)dw,d\phi g_{ij}2w_i\phi _j).`$ (2.7)
For the second term on the $`RHS`$ of (2.6) we have

$`{\displaystyle \frac{d}{ds}}\left(|f(x)|^ke^{2kw_s}\right)|_{s=0}=2k|f(x)|^ke^{2kw}\phi .`$ (2.8)
Combining (2.7) and (2.8), we conclude

$`^t(\phi )=T_{k1}(\overline{}^2w)_{ij}(_i_j\phi +{\displaystyle \frac{1t}{n2}}\mathrm{\Delta }\phi g_{ij})2k|f(x)|^ke^{2kw}\phi +\mathrm{}`$ (2.9)
where $`+\mathrm{}`$ denotes additional terms which are linear in $`\phi `$. Defining

$`(Q_{k1})_{ij}=(T_{k1})_{ij}+{\displaystyle \frac{1t}{n2}}(T_{k1})_{ll}\delta _{ij},`$ (2.10)
we have

$`^t(\phi )=Q_{k1}(\overline{}^2w)_{ij}(_i_j\phi )2k|f(x)|^ke^{2kw}\phi +\mathrm{}`$ (2.11)
By Propositions 2.1 and 2.2, $`Q_{k1}(\overline{}^2w)_{ij}>0`$, so $`^t`$ is elliptic. ∎

Since the coefficient of $`\phi `$ in the zeroth-order term of (2.11) is strictly negative, we have

###### Corollary 2.1.

If $`A_g^t\mathrm{\Gamma }_k^{}`$ for some $`t1`$, then at any solution of (1.7), the linearized operator $`^t:C^{2,\alpha }(M)C^\alpha (M)`$ is invertible.

## 3 $`C^0`$ estimate

We begin with an important property of $`\sigma _k`$ in the cone $`\mathrm{\Gamma }_k^+`$.

###### Lemma 3.1.

Let $`A`$ and $`B`$ be symmetric $`n\times n`$ matrices. Assume that $`A`$ is positive semi-definite, $`B\mathrm{\Gamma }_k^+`$, and $`A+B\mathrm{\Gamma }_k^+`$. Then

$$\sigma _k(A+B)\sigma _k(B).$$

If $`A`$ is negative semi-definite, then

$$\sigma _k(A+B)\sigma _k(B).$$

###### Proof.

Let $`F(t)=\sigma _k(tA+B)\sigma _k(B)`$ for $`t[0,1]`$. Note that from convexity of the cone $`\mathrm{\Gamma }_k^+`$, we have $`t(A+B)+(1t)B=tA+B\mathrm{\Gamma }_k^+`$. Using (2.3), we have

$`F^{}(t)=T_{k1}(tA+B)^{ij}A_{ij}0,`$
since $`T_{k1}(tA+B)`$ is positive definite from Proposition 2.1. Therefore $`F(t)`$ is non-decreasing, and $`F(0)=0`$, so we have $`F(1)=\sigma _k(A+B)\sigma _k(B)0.`$ The negative case is similar. ∎

###### Proposition 3.1.

Suppose $`A_g^t\mathrm{\Gamma }_k^{}`$ for some $`t1`$. Then there exist constants $`\underset{¯}{\delta }<0<\overline{\delta }`$ depending only upon $`f`$, $`A_g^t`$ and $`k`$, such that for any solution $`w(x)`$ of (1.7), we have $`\underset{¯}{\delta }<w(x)<\overline{\delta }`$.

###### Proof.

Since $`N`$ is compact, at a minimum of the function $`w(x)`$ we have

$`\sigma _k^{1/k}\left(^2w(p)+{\displaystyle \frac{1t}{n2}}\mathrm{\Delta }wg(p)A_g^t(p)\right)=f(p)e^{w(p)}`$
with $`^2w(p)`$ positive semidefinite, and therefore $`^2w(p)+\frac{1t}{n2}\mathrm{\Delta }wg(p)0`$. From Proposition 2.2 and Lemma 3.1 we have

$`\sigma _k^{1/k}(A_g^t(p))f(p)e^{w(p)},`$
and certainly we can choose $`\underset{¯}{\delta }`$ such that

$`w(x)w(p)\text{ln}\left({\displaystyle \frac{\sigma _k^{1/k}(A_g^t(p))}{f(p)}}\right)\text{ln}\left(\underset{xN}{\text{min}}{\displaystyle \frac{\sigma _k^{1/k}(A_g^t(x))}{f(x)}}\right)>\underset{¯}{\delta }.`$
Similarly, if the maximum of $`w(x)`$ is at $`qN`$, we can choose $`\overline{\delta }`$ such that

$`w(x)w(q)\text{ln}\left({\displaystyle \frac{\sigma _k^{1/k}(A_g^t(q))}{f(q)}}\right)\text{ln}\left(\underset{xN}{\text{max}}{\displaystyle \frac{\sigma _k^{1/k}(A_g^t(x))}{f(x)}}\right)<\overline{\delta }.`$
## 4 $`C^1`$ estimate

###### Proposition 4.1.

Let $`w`$ be a $`C^3`$ solution of (1.7) for some $`t1`$, satisfying $`\underset{¯}{\delta }<w<\overline{\delta }`$. Then $`w_L^{\mathrm{}}<C_2`$, where $`C_2`$ depends only upon $`\underset{¯}{\delta },\overline{\delta },g,t`$.

We consider the following function

$`h=\left(1+{\displaystyle \frac{|w|^2}{2}}\right)e^{\varphi (w)},`$
where $`\varphi :𝐑𝐑`$ is a function of the form

$`\varphi (s)=c_1(c_2+s)^p.`$
The constants $`c_1,c_2,`$ and $`p`$ will be chosen later. We will estimate the maximum value of the function $`h`$, and this will give us the gradient estimate.

Since $`N`$ is compact, and $`h`$ is continuous, we suppose the maximum of $`h`$ occurs and a point $`pN`$. We take a normal coordinate system $`(x^1,\mathrm{},x^n)`$ at $`p`$. Then we have $`g_{ij}(p)=\delta _{ij}`$, and $`\mathrm{\Gamma }_{jk}^i(p)=0`$, where $`g=g_{ij}dx^idx^j`$, and $`\mathrm{\Gamma }_{jk}^i`$ is the Christoffel symbol (see ).

Locally, we may write $`h`$ as

$`h=\left(1+{\displaystyle \frac{1}{2}}g^{lm}w_lw_m\right)e^{\varphi (w)}=ve^{\varphi (w)}.`$
In a neighborhood of $`p`$, differentiating $`h`$ in the $`x^i`$ direction we have

$`_ih`$ $`=h_i={\displaystyle \frac{1}{2}}_i(g^{lm}w_lw_m)e^{\varphi (w)}+ve^{\varphi (w)}\varphi ^{}(w)w_i`$
$`={\displaystyle \frac{1}{2}}_i(g^{lm})w_lw_me^{\varphi (w)}+g^{lm}_i(w_l)w_me^{\varphi (w)}+ve^{\varphi (w)}\varphi ^{}(w)w_i`$ (4.1)
Since in a normal coordinate system, the first derivatives of the metric vanish at $`p`$, and since $`p`$ is a maximum for $`h`$, evaluating (4.1) at $`p`$, we have

$`w_{li}w_l=v\varphi ^{}(w)w_i.`$ (4.2)
Next we differentiate (4.1) in the $`x^j`$ direction. Since $`p`$ is a maximum, $`_j_ih=h_{ij}`$ is negative semidefinite, and we get (at $`p`$)

$`0h_{ij}`$ $`={\displaystyle \frac{1}{2}}_j_ig^{lm}w_lw_me^{\varphi (w)}+w_{lij}w_le^{\varphi (w)}+w_{li}w_{lj}e^{\varphi (w)}+w_{li}w_le^{\varphi (w)}\varphi ^{}(w)w_j`$
$`+v_je^{\varphi (w)}\varphi ^{}(w)w_i+ve^{\varphi (w)}(\varphi ^{}(w))^2w_iw_j+ve^{\varphi (w)}\varphi ^{\prime \prime }(w)w_jw_i+ve^{\varphi (w)}\varphi ^{}(w)w_{ij}`$
Next we note that $`v_j=w_{lj}w_l`$, and using (4.2), we have

$`0h_{ij}`$ $`={\displaystyle \frac{1}{2}}_j_ig^{lm}w_lw_me^{\varphi (w)}+w_{lij}w_le^{\varphi (w)}+w_{li}w_{lj}e^{\varphi (w)}`$
$`+(\varphi ^{\prime \prime }(w)\varphi ^{}(w)^2)ve^{\varphi (w)}w_iw_j+ve^{\varphi (w)}\varphi ^{}(w)w_{ij}.`$
We recall from Section 2 that

$`\overline{Q}_{ij}^t=\overline{T}_{ij}+{\displaystyle \frac{1t}{n2}}\overline{T}_{ll}\delta _{ij},`$ (4.3)
is positive definite, where $`\overline{T}_{ij}`$ means $`T_{k1}(\overline{}^2w)_{ij}`$.

So we divide by $`ve^{\varphi (w)}`$, sum with $`\overline{Q}_{ij}^t`$, and we have the inequality

$`0{\displaystyle \frac{1}{2v}}\overline{Q}_{ij}^t_i_jg^{lm}w_lw_m+{\displaystyle \frac{1}{v}}\overline{Q}_{ij}^tw_{lij}w_l+(\varphi ^{\prime \prime }(w)\varphi ^{}(w)^2)\overline{Q}_{ij}^tw_iw_j+\varphi ^{}(w)\overline{Q}_{ij}^tw_{ij},`$ (4.4)
since $`w_{li}w_{lj}`$ is positive semidefinite.

We will use equation (1.7) to replace the $`w_{ij}`$ term with lower order terms, and then differentiate equation (1.7) in order to replace the $`w_{lij}`$ term with lower order terms. With respect to our local coordinate system, from (1.5) we have

$`\overline{}^2w_{ij}=`$ $`A_{ij}^t+w_{ij}w_r\mathrm{\Gamma }_{ij}^r+{\displaystyle \frac{1t}{n2}}(w_{kk}w_r\mathrm{\Gamma }_{kk}^r)g_{ij}w_iw_j`$
$`+{\displaystyle \frac{2t}{2}}(g^{r_1r_2}w_{r_1}w_{r_2})g_{ij}.`$ (4.5)
At the point $`p`$, this simplifies to

$`\overline{}^2w_{ij}=A_{ij}^t+w_{ij}+{\displaystyle \frac{1t}{n2}}(w_{kk})g_{ij}w_iw_j+{\displaystyle \frac{2t}{2}}(|w|^2)\delta _{ij}.`$ (4.6)
We write equation (1.7) in our local coordinate system

$`\sigma _k(g^{lj}(\overline{}^2w)_{ij})=|f(x)|e^{2kw}.`$ (4.7)
Note that the $`g^{lj}`$ term is present since we need to raise an index on the tensor before we apply $`\sigma _k`$. From (4.6), we have at $`p`$,

$`\overline{Q}_{ij}^tw_{ij}`$ $`=\overline{T}_{ij}\left(\overline{}^2w_{ij}+A_{ij}^t{\displaystyle \frac{1t}{n2}}(\mathrm{\Delta }w)g_{ij}+w_iw_j{\displaystyle \frac{2t}{2}}(|w|^2)\delta _{ij}\right)`$
$`+{\displaystyle \frac{1t}{n2}}\mathrm{\Delta }w\overline{T}_{ll}`$
$`=\overline{T}_{ij}\left(\overline{}^2w_{ij}+A_{ij}^t+w_iw_j{\displaystyle \frac{2t}{2}}(|w|^2)\delta _{ij}\right).`$
From the identities in (2.4), we have

$`\overline{T}_{ij}(\overline{}^2w)_{ij}=k\sigma _k(\overline{}^2w).`$
Therefore, using equation (4.7), we have

$`\overline{Q}_{ij}^tw_{ij}`$ $`=k\sigma _k(\overline{}^2w)+\overline{T}_{ij}\left(A_{ij}^t+w_iw_j{\displaystyle \frac{2t}{2}}(|w|^2)\delta _{ij}\right)`$
$`=k|f(x)|e^{2kw}+\overline{T}_{ij}\left(A_{ij}^t+w_iw_j{\displaystyle \frac{2t}{2}}(|w|^2)\delta _{ij}\right).`$ (4.8)
Next we take $`m`$ with $`1mn`$, and apply $`_m`$ to (4.7)

$`_m\left\{\sigma _k(g^{lj}\overline{}^2w_{ij})\right\}=_m(|f(x)|e^{2kw}).`$ (4.9)
For the left side we have

$`_m\left\{\sigma _k(g^{lj}\overline{}^2w_{ij})\right\}=\overline{T}_{il}_m(g^{lj}\overline{}^2w_{ij})=\overline{T}_{il}\left(_mg^{lj}\overline{}^2w_{ij}+g^{lj}_m\overline{}^2w_{ij}\right)`$
$`=\overline{T}_{il}(_mg^{lj}\overline{}^2w_{ij}+g^{lj}_m\{A_{ij}^t+w_{ij}w_r\mathrm{\Gamma }_{ij}^r+{\displaystyle \frac{1t}{n2}}(w_{kk}w_r\mathrm{\Gamma }_{kk}^r)g_{ij}`$
$`w_iw_j+{\displaystyle \frac{2t}{2}}(g^{r_1r_2}w_{r_1}w_{r_2})g_{ij}\})`$
$`=\overline{T}_{il}(_mg^{lj}\overline{}^2w_{ij}+g^{lj}\{_mA_{ij}^t+w_{ijm}w_{rm}\mathrm{\Gamma }_{ij}^rw_r_m\mathrm{\Gamma }_{ij}^r`$
$`+{\displaystyle \frac{1t}{n2}}(w_{kkm}w_{rm}\mathrm{\Gamma }_{kk}^rw_r_m\mathrm{\Gamma }_{kk}^r)g_{ij}+{\displaystyle \frac{1t}{n2}}(w_{kk}w_r\mathrm{\Gamma }_{kk}^r)_mg_{ij}2w_{im}w_j`$
$`+{\displaystyle \frac{2t}{2}}((_mg^{r_1r_2})w_{r_1}w_{r_2}g_{ij}+2g^{r_1r_2}w_{r_1m}w_{r_2}g_{ij}+g^{r_1r_2}w_{r_1}w_{r_2}_mg_{ij})\}).`$
Evaluating this expression at $`p`$, we have

$`_m\left\{\sigma _k(g^{lj}\overline{}^2w_{ij})\right\}`$ $`=\overline{T}_{ij}(_mA_{ij}^t+w_{ijm}w_r_m\mathrm{\Gamma }_{ij}^r+{\displaystyle \frac{1t}{n2}}(w_{kkm}w_r_m\mathrm{\Gamma }_{kk}^r)g_{ij}`$
$`2w_{im}w_j+(2t)(w_{lm}w_l)g_{ij}).`$ (4.10)
For the right hand side of (4.9) we have

$`_m\left(|f(x)|e^{2kw}\right)`$ $`=_m|f(x)|e^{2kw}+2k|f(x)|e^{2kw}w_m.`$ (4.11)
We have obtained the expansion of (4.9):

$`\begin{array}{cc}& \overline{T}_{ij}(_mA_{ij}^t+w_{ijm}w_r_m\mathrm{\Gamma }_{ij}^r+{\displaystyle \frac{1t}{n2}}(w_{kkm}w_r_m\mathrm{\Gamma }_{kk}^r)\delta _{ij}\hfill \\ & 2w_{im}w_j(2t)v\varphi ^{}(w)w_m\delta _{ij})=(_m|f(x)|)e^{2kw}+2k|f(x)|e^{2kw}w_m.\hfill \end{array}`$ (4.12)
Note that the third order terms in the above expression are

$`\overline{T}_{ij}\left(w_{ijm}+{\displaystyle \frac{1t}{n2}}w_{kkm}\delta _{ij}\right)=\overline{Q}_{ij}^tw_{ijm}.`$
Next we sum (LABEL:fullfirstder) with $`w_m`$, using (4.2) we have the following formula

$`\begin{array}{cc}& \overline{Q}_{ij}w_mw_{ijm}+\overline{T}_{ij}(w_m_mA_{ij}^tw_mw_r_m\mathrm{\Gamma }_{ij}^r{\displaystyle \frac{1t}{n2}}(w_rw_m_m\mathrm{\Gamma }_{kk}^r)\delta _{ij}\hfill \\ & +2v\varphi ^{}(w)w_iw_j(2t)v\varphi ^{}(w)|w|^2\delta _{ij})\hfill \\ & =w_m(_mf(x))e^{2kw}+2k|f(x)|e^{2kw}|w|^2.\hfill \end{array}`$ (4.13)
Substituting (4.8) and (LABEL:firstderterm) into (4.4), we arrive at the inequality

$`0`$ $`{\displaystyle \frac{1}{2v}}\overline{Q}_{ij}^t_i_jg^{lm}w_lw_m+(\varphi ^{\prime \prime }(w)\varphi ^{}(w)^2)\overline{Q}_{ij}^tw_iw_j`$
$`+{\displaystyle \frac{1}{v}}\overline{T}_{ij}(w_m_mA_{ij}^t+w_mw_r_m\mathrm{\Gamma }_{ij}^r+{\displaystyle \frac{1t}{n2}}(w_rw_m_m\mathrm{\Gamma }_{kk}^r)\delta _{ij}2v\varphi ^{}(w)w_iw_j`$
$`+(2t)v\varphi ^{}(w)|w|^2\delta _{ij})+{\displaystyle \frac{1}{v}}(w_m(_m|f(x)|)e^{2kw}+2k|f(x)|e^{2kw}|w|^2)`$
$`+\varphi ^{}(w)\left(k|f(x)|e^{2kw}+\overline{T}_{ij}\left(A_{ij}^t+w_iw_j{\displaystyle \frac{2t}{2}}(|w|^2)\delta _{ij}\right)\right).`$
Recalling that $`\overline{Q}_{ij}^t=\overline{T}_{ij}+\frac{1t}{n2}\overline{T}_{ll}\delta _{ij}`$, we have

$`0`$ $`\left(\varphi ^{\prime \prime }(w)\varphi ^{}(w)^2\varphi ^{}(w)\right)\overline{T}_{ij}w_iw_j`$
$`+{\displaystyle \frac{1}{v}}\overline{T}_{ij}({\displaystyle \frac{1t}{n2}}_k_kg^{lm}w_lw_m(\delta _{ij}/2)+{\displaystyle \frac{1t}{n2}}v(\varphi ^{\prime \prime }(w)\varphi ^{}(w)^2)|w|^2g_{ij}`$
$`+{\displaystyle \frac{1}{2}}_i_jg^{lm}w_lw_m+w_m_mA_{ij}^t+w_mw_r_m\mathrm{\Gamma }_{ij}^r+{\displaystyle \frac{1t}{n2}}(w_rw_m_m\mathrm{\Gamma }_{kk}^r)\delta _{ij}`$
$`+v\varphi ^{}(w)A_{ij}^t+{\displaystyle \frac{2t}{2}}v\varphi ^{}(w)|w|^2\delta _{ij})`$
$`+{\displaystyle \frac{1}{v}}\left(w_m(_mf(x))e^{2kw}+2k|f(x)|e^{2kw}|w|^2\right)+\varphi ^{}(w)\left(k|f(x)|e^{2kw}\right).`$ (4.14)
###### Lemma 4.1.

At $`p`$, in normal coordinates, we have

$`{\displaystyle \underset{l,m}{}}(_i_jg^{lm}+2_l\mathrm{\Gamma }_{ij}^m)u_lu_m=2{\displaystyle \underset{l,m}{}}R_{iljm}u_lu_m,`$
where $`R_{iljm}`$ are the components of the Riemann curvature tensor of $`g`$.

###### Proof.

For the proof, see . ∎

Using the lemma, and collecting terms in (4.14), we arrive at

$`0`$ $`\left(\varphi ^{\prime \prime }(w)\varphi ^{}(w)^2\varphi ^{}(w)\right)\overline{T}_{ij}w_iw_j`$
$`+\overline{T}_{ij}({\displaystyle \frac{1t}{n2}}R_{klkm}{\displaystyle \frac{w_lw_m}{v}}\delta _{ij}+R_{iljm}{\displaystyle \frac{w_lw_m}{v}}+{\displaystyle \frac{1t}{n2}}(\varphi ^{\prime \prime }(w)\varphi ^{}(w)^2)|w|^2g_{ij}`$
$`+{\displaystyle \frac{w_m}{v}}_mA_{ij}^t+\varphi ^{}(w)A_{ij}^t+{\displaystyle \frac{2t}{2}}\varphi ^{}(w)|w|^2\delta _{ij})`$
$`+{\displaystyle \frac{1}{v}}\left(w_m(_mf(x))e^{2kw}+2k|f(x)|e^{2kw}|w|^2\right)+\varphi ^{}(w)\left(k|f(x)|e^{2kw}\right).`$ (4.15)
Now we will choose $`\varphi (s)`$.

###### Lemma 4.2.

Assume that $`\underset{¯}{\delta }<s<\overline{\delta }`$. Then we may choose constants $`c_1,c_2,`$ and $`p`$ depending only upon $`\underset{¯}{\delta }`$, and $`\overline{\delta }`$. so that $`\varphi (s)=c_1(c_2+s)^p`$ satisfies

$`\varphi ^{}(s)>0,`$ (4.16)
and

$`\varphi ^{\prime \prime }(s)\varphi ^{}(s)^2\varphi ^{}(s)>0.`$ (4.17)
###### Proof.

We have

$`\varphi ^{}(s)=pc_1(c_2+s)^{p1},`$
and

$`\varphi ^{\prime \prime }(s)=p(p1)c_1(c_2+s)^{p2}.`$
To satisfy (4.16) we need $`c_1>0`$, $`p>0`$, and $`c_2+s>0`$. So choose $`c_2>\underset{¯}{\delta }`$. Next we have

$`\varphi ^{\prime \prime }(s)\varphi ^{}(s)^2\varphi ^{}(s)`$ $`=p(p1)c_1(c_2+s)^{p2}(pc_1(c_2+s)^{p1})^2pc_1(c_2+s)^{p1}`$
$`=pc_1(c_2+s)^{p2}\left((p1)pc_1(c_2+s)^p(c_2+s)\right).`$
Now choose

$`c_1={\displaystyle \frac{1}{p^2\text{ max}\{(c_2+s)^p\}}},`$
and $`p`$ so large that

$`\underset{¯}{\delta }<c_2<\overline{\delta }+p1{\displaystyle \frac{1}{p}}.`$
Then we have

$`\varphi ^{\prime \prime }(s)\varphi ^{}(s)^2\varphi ^{}(s)`$ $`{\displaystyle \frac{1}{p\text{ max}\{(c_2+s)^p\}}}(c_2+s)^{p2}\left(p1{\displaystyle \frac{1}{p}}c_2s\right)`$
$`>{\displaystyle \frac{1}{p\text{ max}\{(c_2+s)^p\}}}(c_2+s)^{p2}(\overline{\delta }s)>0.`$
With $`\varphi (s)`$ chosen as above, for $`s[\underset{¯}{\delta },\overline{\delta }]`$, we let

$$ϵ_1=\text{min}\{\varphi ^{}(s)\},$$

and

$$ϵ_2=\text{min}\{\varphi ^{\prime \prime }(s)\varphi ^{}(s)^2\varphi ^{}(s)\}.$$

From the inequality (4.15), we have

$`0`$ $`ϵ_2\overline{T}_{ij}w_iw_j+\overline{T}_{ij}({\displaystyle \frac{1t}{n2}}R_{klkm}{\displaystyle \frac{w_lw_m}{v}}\delta _{ij}+R_{iljm}{\displaystyle \frac{w_lw_m}{v}}`$
$`+{\displaystyle \frac{w_m}{v}}_mA_{ij}^t+\varphi ^{}(w)A_{ij}^t+({\displaystyle \frac{2t}{2}}+{\displaystyle \frac{1t}{n2}})ϵ_1|w|^2\delta _{ij})`$
$`+{\displaystyle \frac{1}{v}}\left(w_m(_mf(x))e^{2kw}+2k|f(x)|e^{2kw}|w|^2\right)+ϵ_1\left(k|f(x)|e^{2kw}\right).`$ (4.18)
If the matrix

$`\begin{array}{cc}& \left({\displaystyle \frac{1t}{n2}}R_{klkm}\delta _{ij}+R_{iljm}\right){\displaystyle \frac{w_lw_m}{v}}+{\displaystyle \frac{w_m}{v}}_mA_{ij}^t+\varphi ^{}(w)A_{ij}^t+\left({\displaystyle \frac{2t}{2}}+{\displaystyle \frac{1t}{n2}}\right)ϵ_1|w|^2\delta _{ij}\hfill \end{array}`$ (4.19)
has an eigenvalue less than $`1`$, then the gradient estimate is immediate since the last term dominates ($`\frac{2t}{2}+\frac{1t}{n2}>0`$). Otherwise, absorbing lower order terms in (4.18), we have

$`C`$ $`ϵ_2\overline{T}_{ij}w_iw_j+\overline{T}_{ll}.`$ (4.20)
From (2.4) we obtain

$`\sigma _{k1}C.`$
###### Proposition 4.2.

Let $`k2`$, and $`A\mathrm{\Gamma }_k^+`$ be a symmetric linear transformation. If $`0<c_1\sigma _k(A)`$, and $`\sigma _{k1}(A)c_2`$, then we have a bound on the eigenvalues of $`A`$, that is, $`|\lambda (A)|C`$, where $`C`$ depends only on $`c_1`$ and $`c_2`$.

###### Proof.

The proof may be found in . ∎

Using this result, if $`k2`$, we see that

$`|\lambda |C,`$
and since $`\overline{T}_{k1}`$ is positive definite, this implies (see )

$`\overline{T}_{k1}^{ii}{\displaystyle \frac{1}{C}}>0,\text{ for }i=1\mathrm{}n.`$
Equation (4.20) then implies that

$`|w|^2C.`$
Note that in the case $`k=1`$, we do not require the proposition since $`T_0^{ij}=\delta ^{ij}`$, and therefore (4.20) gives the gradient bound.

## 5 $`C^2`$ estimate

###### Proposition 5.1.

Let $`w`$ be a $`C^4`$ solution of (1.7) for some $`t<1`$ satisfying $`\underset{¯}{\delta }<w<\overline{\delta }`$, and $`w_L^{\mathrm{}}<C_1`$. Then $`^2w_L^{\mathrm{}}C_2`$, where $`C_2`$ depends only upon $`\underset{¯}{\delta },\overline{\delta },C_1,g,t`$.

Let $`S(TN)`$ denote the unit tangent bundle of $`N`$, and we consider the following function $`h:S(TN)𝐑`$,

$`h(e_p)=(^2w+\mathrm{\Lambda }|w|^2g)(e_p,e_p),`$
where $`\mathrm{\Lambda }`$ is a constant to be chosen later. Since $`S(TN)`$ is compact, let $`h`$ have a maximum at the vector $`\stackrel{~}{e}_p`$. We use normal coordinates at $`p`$, and by rotating, assume that the tensor is diagonal at $`p`$, and without loss of generality, we may assume that $`\stackrel{~}{e}_p=/x^1`$, and that $`^2w`$ is diagonal at $`p`$.

We let $`\stackrel{~}{h}`$ denote the function defined in a neighborhood of $`p`$

$`\stackrel{~}{h}(x)`$ $`=(^2w+\mathrm{\Lambda }|w|^2g)(/x^1,/x^1)`$
$`=(^2w)_{11}+\mathrm{\Lambda }|w|^2`$
$`=w_{11}\mathrm{\Gamma }_{11}^lw_l+\mathrm{\Lambda }|w|^2.`$
Differentiating in the $`i`$th coordinate direction, we obtain

$`\stackrel{~}{h}_i=w_{11i}_i\mathrm{\Gamma }_{11}^lw_l\mathrm{\Gamma }_{11}^lw_{li}+\mathrm{\Lambda }_ig^{kl}w_kw_l+2\mathrm{\Lambda }g^{kl}(_iw_k)w_l.`$ (5.1)
The function $`\stackrel{~}{h}(x)`$ has a maximum at $`p`$, so evaluating (5.1) at $`p`$, we obtain

$`w_{11i}=_i\mathrm{\Gamma }_{11}^lu_l+2\mathrm{\Lambda }w_{ik}w_k.`$ (5.2)
Next we differentiate (5.1) in the $`x^j`$ direction. Since $`p`$ is a maximum, $`_j_i\stackrel{~}{h}=\stackrel{~}{h}_{ij}`$ is negative semidefinite, and we get (at $`p`$)

$`0\stackrel{~}{w}_{ij}`$ $`=w_{11ij}_i_j\mathrm{\Gamma }_{11}^lw_l_i\mathrm{\Gamma }_{11}^lw_{lj}_j\mathrm{\Gamma }_{11}^lu_{li}`$
$`+\mathrm{\Lambda }_j_ig^{kl}w_kw_l+2\mathrm{\Lambda }w_{ikj}w_k+2\mathrm{\Lambda }w_{ik}w_{kj}.`$
We again recall from Section 2 that

$`\overline{Q}_{ij}^t=\overline{T}_{ij}+{\displaystyle \frac{1t}{n2}}\overline{T}_{ll}\delta _{ij},`$ (5.3)
is positive definite, where $`\overline{T}_{ij}`$ means $`T_{k1}(\overline{}^2w)_{ij}`$. We sum with $`\overline{Q}_{ij}^t`$ and we have the inequality

$`\begin{array}{cc}\hfill 0& \overline{Q}_{ij}^tw_{11ij}\overline{Q}_{ij}^t_i_j\mathrm{\Gamma }_{11}^lw_l2\overline{Q}_{ij}^t_i\mathrm{\Gamma }_{11}^lw_{lj}+2\mathrm{\Lambda }\overline{Q}_{ij}^t_j_ig^{kl}w_kw_l\hfill \\ & +2\mathrm{\Lambda }\overline{Q}_{ij}^tw_{ik}w_{kj}+2\mathrm{\Lambda }\overline{Q}_{ij}^tw_{ijk}w_k\hfill \end{array}`$ (5.4)
We will use (4.10) to replace the last term, and we will differentiate equation (1.7) twice to replace the first term.

Using (4.10) and (4.11), we have at $`p`$,

$`\begin{array}{cc}\hfill \overline{T}_{ij}& \left(_mA_{ij}^tw_r_m\mathrm{\Gamma }_{ij}^r{\displaystyle \frac{1t}{n2}}(w_r_m\mathrm{\Gamma }_{kk}^r)g_{ij}2w_{im}w_j+(2t)(w_{lm}w_l)g_{ij}\right)\hfill \\ & +\overline{Q}_{ij}^tw_{ijm}=_m|f(x)|e^{2kw}+2k|f(x)|e^{2kw}w_m.\hfill \end{array}`$ (5.5)
The next step is to rewrite the second derivative terms in terms of $`\overline{}^2w`$. To further simplify notation, we let $`\overline{w}_{ij}=(\overline{}^2w)_{ij}`$. We have

$`w_{ij}=\overline{w}_{ij}{\displaystyle \frac{1t}{n2}}\mathrm{\Delta }w\delta _{ij}{\displaystyle \frac{2t}{2}}|w|^2\delta _{ij}+w_iw_j+(A_g^t)_{ij}.`$ (5.6)
Since we are in the cone $`\mathrm{\Gamma }_k^+`$, the trace is positive by Proposition 2.1, and since $`\overline{w}_{11}`$ is the largest eigenvalue, we have

$`|\overline{w}_{ii}|(n1)\overline{w}_{11},i=1\mathrm{}n.`$ (5.7)
Using (5.6) and (5.7), we may estimate (5.5)

$`\overline{Q}_{ij}^tw_{ijm}w_m`$ $`C+C{\displaystyle \underset{i}{}}\overline{T}_{ii}+C\overline{w}_{11}{\displaystyle \underset{i}{}}\overline{T}_{ii}.`$ (5.8)
Inequality (5.4) may then be rewritten as

$`\begin{array}{cc}\hfill 0& \overline{Q}_{ij}^tw_{11ij}+C+C{\displaystyle \underset{i}{}}\overline{T}_{ii}+C\overline{w}_{11}{\displaystyle \underset{i}{}}\overline{T}_{ii}.+{\displaystyle \frac{2\mathrm{\Lambda }(1t)}{n2}}\overline{w}_{11}^2{\displaystyle \underset{i}{}}\overline{T}_{ii}.\hfill \end{array}`$ (5.9)
We recall that the equation is

$$\sigma _k^{1/k}(\overline{}^2w)=f(x)e^{2w}.$$

To simplify notation, write $`\sigma =\sigma _k^{1/k}`$. Differentiating once in the $`x^1`$ direction, we have

$`{\displaystyle \frac{\sigma }{r_{ij}}}(_1(\overline{}^2w)_j^i)=f_1e^{2w}2fe^{2w}w_1.`$
Differentiating twice, we obtain

$`_1\left({\displaystyle \frac{\sigma }{r_{ij}}}\right)(_1(\overline{}^2w)_j^i)+{\displaystyle \frac{\sigma }{r_{ij}}}(_1_1(\overline{}^2w)_j^i)`$
$`=\left({\displaystyle \frac{^2\sigma }{r_{ij}r_{lm}}}\right)(_1(\overline{}^2w)_m^l)(_1(\overline{}^2w)_j^i)+{\displaystyle \frac{\sigma }{r_{ij}}}(_1_1(\overline{}^2w)_j^i)`$
$`=f_{11}e^{2w}4f_1e^{2w}w_i4fe^{2w}w_1^22fe^{2w}w_{11}.`$
Since $`\sigma _k^{1/k}`$ is concave in $`\mathrm{\Gamma }_k^+`$, we have the inequality

$`\overline{T}_{k1}^{ij}\left(_1_1(\overline{}^2w)_j^i\right)(f(x)e^{2w})^{k1}(f_{11}e^{2w}4f_1e^{2w}w_i4fe^{2w}w_1^22fe^{2w}w_{11}).`$ (5.10)
Using our assumptions, we have

$`\overline{T}_{k1}^{ij}\left(_1_1(\overline{}^2w)_j^i\right)C+C\overline{w}_{11}.`$ (5.11)
We differentiate (4.5) twice, and evaluate at $`p`$ to obtain

$`_1_1`$ $`(\overline{}^2w)_{ij}=A_{ij11}^t+w_{ij11}+2w_{r1}_1(\mathrm{\Gamma }_{ij}^r)+w_r_1_1(\mathrm{\Gamma }_{ij}^r)`$
$`+{\displaystyle \frac{1t}{n2}}(w_{kk11})g_{ij}+{\displaystyle \frac{1t}{n2}}w_{kk}_1_1(g_{ij})`$
$`{\displaystyle \frac{1t}{n2}}(2w_{r1}_1\mathrm{\Gamma }_{kk}^r+w_r_1_1\mathrm{\Gamma }_{kk}^r)(w_{i11}w_j+2w_{i1}w_{j1}+w_iw_{j11})`$
$`+{\displaystyle \frac{2t}{2}}\left(_1_1g^{r_1r_2}w_{r_1}w_{r_2}\delta _{ij}+2(w_{r11}w_r+w_{r1}w_{r1})\delta _{ij}+|w|^2_1_1(g_{ij})\right).`$
From (5.2) we can replace terms of the form $`w_{11i}`$ and we have

$`\begin{array}{cc}& \overline{T}_{k1}^{ij}\overline{w}_{ij11}=\overline{Q}_{ij}^t\overline{w}_{ij11}+\overline{T}_{k1}^{ij}\{A_{ij11}^t+2w_{r1}_1(\mathrm{\Gamma }_{ij}^r)+w_r_1_1(\mathrm{\Gamma }_{ij}^r)\hfill \\ & +{\displaystyle \frac{1t}{n2}}w_{kk}_1_1(g_{ij}){\displaystyle \frac{1t}{n2}}(2w_{r1}_1\mathrm{\Gamma }_{kk}^r+w_r_1_1\mathrm{\Gamma }_{kk}^r)+4\mathrm{\Lambda }w_{ik}w_kw_j2w_{i1}w_{j1}\hfill \\ & +{\displaystyle \frac{2t}{2}}(_1_1g^{r_1r_2}w_{r_1}w_{r_2}\delta _{ij}4\mathrm{\Lambda }w_{rm}w_mw_r\delta _{ij}+2w_{r1}w_{r1})\delta _{ij}+|w|^2_1_1(g_{ij}))\}\hfill \end{array}`$ (5.12)
Substituting (5.12) in (5.11), we have

$`\begin{array}{c}\hfill \overline{Q}_{ij}^tw_{ij11}C+C\overline{w}_{11}+C{\displaystyle \underset{i}{}}\overline{T}_{ii}+C\overline{w}_{11}{\displaystyle \underset{i}{}}\overline{T}_{ii}(2t)\overline{w}_{11}^2{\displaystyle \underset{i}{}}\overline{T}_{ii}.\end{array}`$ (5.13)
Next we substitute inequality (5.13) into (5.9) and we obtain

$`\begin{array}{cc}\hfill 0& C+C\overline{w}_{11}+C{\displaystyle \underset{i}{}}\overline{T}_{ii}+C\overline{w}_{11}{\displaystyle \underset{i}{}}\overline{T}_{ii}+\left({\displaystyle \frac{2\mathrm{\Lambda }(1t)}{n2}}(2t)\right)\overline{w}_{11}^2{\displaystyle \underset{i}{}}\overline{T}_{ii}.\hfill \end{array}`$ (5.14)
Since $`t<1`$, we may choose $`\mathrm{\Lambda }`$ large to dominate the $`(2t)`$ term (this is the point where the assumption $`t<1`$ is crucial). Choosing

$`\mathrm{\Lambda }{\displaystyle \frac{n2}{1t}}\left(1+{\displaystyle \frac{2t}{2}}\right),`$
we obtain

$`C+C\overline{w}_{11}+C{\displaystyle \underset{i}{}}\overline{T}_{k1}^{ii}+C\overline{w}_{11}{\displaystyle \underset{i}{}}\overline{T}_{k1}^{ii}2\overline{w}_{11}^2{\displaystyle \underset{i}{}}\overline{T}_{k1}^{ii}.`$ (5.15)
Dividing by $`2\overline{w}_{11}^2`$ and using (2.4), we obtain

$`\begin{array}{c}\hfill \sigma _{k1}\left({\displaystyle \frac{C_1}{\overline{w}_{11}^2}}+{\displaystyle \frac{C_2}{\overline{w}_{11}}}\right)\sigma _{k1}+{\displaystyle \frac{C}{\overline{w}_{11}^2}}+{\displaystyle \frac{C}{\overline{w}_{11}}}.\end{array}`$ (5.16)
If

$`{\displaystyle \frac{C_1}{\overline{w}_{11}^2}}+{\displaystyle \frac{C_2}{\overline{w}_{11}}}{\displaystyle \frac{1}{2}},`$
then we have the necessary eigenvalue bound. So we may assume that

$`{\displaystyle \frac{C_1}{\overline{w}_{11}^2}}+{\displaystyle \frac{C_2}{\overline{w}_{11}}}{\displaystyle \frac{1}{2}},`$
and substitution into inequality (5.16) yields

$`{\displaystyle \frac{1}{2}}\sigma _{k1}{\displaystyle \frac{C}{\overline{w}_{11}^2}}+{\displaystyle \frac{C}{\overline{w}_{11}}}.`$
Without loss of generality we may assume that $`\overline{w}_{11}1`$, and from the above inequality we obtain

$`\sigma _{k1}C,`$
which by Proposition 4.2 yields the eigenvalue bound in the case $`k2`$. In the case $`k=1`$, (5.16) already gives the eigenvalue estimate.

## 6 Proof of Theorem 1.2

In the previous sections we have demonstrated an a priori $`C^2`$ estimate for solutions of (1.7). Therefore (1.7) is uniformly elliptic with respect to any solution. It is straightforward to verify that (1.7) is a concave function of the second derivative variables. It follows from the work of Evans , and Krylov  that there exists a constant $`C`$ such that for any solution $`w`$ of (1.7) we have

$$w_{C^{2,\alpha }}<C.$$

For $`s[0,1]`$, we consider the equation

$`\begin{array}{cc}\hfill \sigma _k^{1/k}& \left(^2w^s+{\displaystyle \frac{1t}{n2}}(\mathrm{\Delta }w^s)g+{\displaystyle \frac{2t}{2}}|w^s|^2gdw^sdw^sH(s)\right)\hfill \\ & =\left(s|f(x)|+(1s)\right)e^{2w^s}>0,\hfill \end{array}`$ (6.1)
where $`H(s)=sA_g^t(1s)\left(\genfrac{}{}{0pt}{}{n}{k}\right)^{1/k}g`$. Define

$$S=\{s[0,1]:(\text{6.1})\text{ has a solution }w^sC^{2,\alpha }\}.$$

It follows from Corollary 2.1 and the implicit function theorem (see ) that $`S`$ is open. For $`s=0`$, we have the solution $`w0`$, therefore $`S`$ is non-empty. Clearly, the estimates from the previous sections remain valid upon replacing $`A_g^t`$ by $`H(s)`$, and $`|f(x)|`$ by $`s|f(x)|+(1s)`$. Consequently there exists a constant $`C`$ independent of $`s`$ such that

$$w^s_{C^{2,\alpha }}<C,$$

which implies that $`S`$ is closed. From connectedness, $`S=[0,1]`$, therefore there exists a solution at $`s=1`$.

Using the maximum principle as in Proposition 3.1, it follows that $`w0`$ is the unique solution at $`s=0`$. To prove uniqueness at $`s=1`$, assume by contradiction that we have solutions $`w_1`$ and $`w_2`$ for $`s=1`$. Then we may run the continuity method in reverse, starting at $`s=1`$ and descending to $`s=0`$. From the a priori estimates, we obtain 2 paths of solutions, one starting at $`w_1`$, and another starting at $`w_2`$. Since there is a unique solution at $`s=0`$, the paths must coincide at some $`s0`$. This contradicts local invertibility.

## 7 Remarks on the positive curvature case

In this paper, we have concentrated on the case that $`A_g^t\mathrm{\Gamma }_k^{}`$, but it is also interesting to consider the case $`A_g^t\mathrm{\Gamma }_k^+`$. This problem was studied in  for $`t=1`$, where the compactness was reduced to an $`L^{\mathrm{}}`$ estimate. The estimate proved in this paper also reduce the compactness to an $`L^{\mathrm{}}`$ estimate for $`\mathrm{}<t1`$.

For $`f(x)>0`$, and background metric $`g`$ with $`A_g^t\mathrm{\Gamma }_k^+`$, we consider a conformal change of metric $`\stackrel{~}{g}=e^{2w}g`$. Then (1.4) becomes

$`\sigma _k^{1/k}\left(^2w+{\displaystyle \frac{1t}{n2}}(\mathrm{\Delta }w)g{\displaystyle \frac{2t}{2}}|w|^2g+dwdw+A_g^t\right)=f(x)e^{2w}>0.`$ (7.1)
Note the gradient terms have a different sign now, but the estimates for higher derivatives still work. In particular, for the $`C^1`$ estimate, the only modification necessary is the following variant of Lemma 4.2

###### Lemma 7.1.

Assume that $`\underset{¯}{\delta }<s<\overline{\delta }`$. Then we may choose constants $`c_1,c_2,`$ and $`p`$ depending only upon $`\underset{¯}{\delta }`$, and $`\overline{\delta }`$. so that $`\varphi (s)=c_1(c_2+s)^p`$ satisfies

$`\varphi ^{}(s)<0,`$ (7.2)
and

$`\varphi ^{\prime \prime }(s)\varphi ^{}(s)^2\varphi ^{}(s)>0.`$ (7.3)
The proof given in Section 4 then works as before for all $`t1`$. For the $`C^2`$ estimate, using the following test function

$`h(e_p)=(^2w+\mathrm{\Lambda }|w|^2g+dwdw)(e_p,e_p),`$
the estimate (5.14) becomes

$`\begin{array}{c}\hfill 0C+C\overline{w}_{11}+C{\displaystyle \underset{i}{}}\overline{T}_{ii}+C\overline{w}_{11}{\displaystyle \underset{i}{}}\overline{T}_{ii}+\left({\displaystyle \frac{2\mathrm{\Lambda }(1t)}{n2}}+(2t)\right)\overline{w}_{11}^2{\displaystyle \underset{i}{}}T_{ii}.\end{array}`$ (7.4)
The estimate now works for all $`\mathrm{}<t1`$. Note we can include the endpoint $`t=1`$ in the positive case.

We conclude with an outline of some progress that has been made for $`t=1`$ in the positive case. For $`\sigma _2`$ in dimension 4, the $`L^{\mathrm{}}`$ estimate has been proved (if $`M`$ is not conformally equivalent to $`S^4`$) in Chang, Gursky and Yang (see ). Existence of solutions in the locally conformally flat case has been demonstrated in  and . A sufficient condition for the $`L^{\mathrm{}}`$ estimate in the determinant case may be found in .

Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556
E-mail Address: mgursky@nd.edu
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139
E-mail Address: jeffv@math.mit.edu


text:
# Contribution of Kaluza-Klein modes to vacuum energy in models with large extra dimensions & the Cosmological constant

## Introduction

The Einstein equations with the cosmological constant are given by

$$R_{\mu \nu }\frac{1}{2}g_{\mu \nu }R=g_{\mu \nu }\mathrm{\Lambda }8\pi GT_{\mu \nu }$$
(1)
where $`\mathrm{\Lambda }`$ is the cosmological constant, or vacuum energy. Modulo the factor of $`8\pi G`$, this constant is identical to the stress tensor associated with vacuum. It can be seen on grounds of covariance that the vacuum expectation value of the stress tensor is of the form

$$T_{\mu \nu }=\rho _{vac}g_{\mu \nu }$$
(2)
No known symmetry forbids a cosmological term in Einstain equations. Based on observations, it is seen that in suitable units, $`\mathrm{\Lambda }`$ is at most of the order of $`10^{47}`$ (GeV)4. At the same time, the vacuum energy evaluated with an ultraviolet cut-off at the Planck scale $`M_{pl}10^{19}`$ GeV gives

$$E_{vac}\frac{1}{2}_0^{M_{pl}}\frac{d^3k}{(2\pi )^3}\sqrt{k^2+m^2}M_{pl}^4$$
(3)
which is about 120 orders of magnitude higher. Attempts have been made to account for this discrepancy  and it has been realized that even if the cut-off is taken at the Supersymmetry (SUSY) scale, the discrepancy is still about 60 orders of magnitude. It is seen that an ultraviolet cut-off of the order of $`10^3`$ eV is required to account for the observed value of the vacuum energy. Therefore, even very low energy quantum effects at sizes much larger than the size of atoms lead to untolerable contributions to the cosmological constant.
Several suggestions such as SUSY, scalar dilatons, 3-form fields and quintessence have been made, but no satisfactory resolution is seen to emerge (for a review, see ).
Recently, there have been developments in Kaluza-Klein theories that claim to remove the so called hierarchy problem between the Electroweak and Planck scales . In these recent models, it is assumed that all matter is confined to a four dimensional hypersurface, a 3-brane, in a higher dimensional spacetime. Gravity, unlike matter, is assumed to propagate in all dimensions. There are essentially two models and their variants. The first model, the ADD model , assumes the existence of n large extra dimensions with size of the order of a millimeter and a bulk scale of gravitation of the order of a TeV, instead of $`M_{pl}`$. The metric of spacetime is a direct product of the usual 4-dimensional spacetime and the compact extra dimensional space. Due to the large volume of the compact space, gravitation on the 3-brane is diluted down to the observed Planck scale, instead of a TeV scale, which is the gravitational scale of the bulk spacetime. The large size of the extra dimensions removes the hierarchy between the two scales and is not in conflict with micro-experiments, since matter cannot directly probe these extra dimensions, being stuck on the 3-brane. The most studied model from a cosmological point of view is the RS model  and it’s variants. In this model, there is only one extra dimension and one or more branes. This model differs from the ADD model in that spacetime is not a direct product of the four dimensional spacetime and the extra dimensional manifold (as is the case in the ADD scenario), but has a warp factor multiplying the four dimensional metric. This warp factor is a function of the extra dimension. There are cosmological constant terms on the 3-branes and in addition, a bulk cosmological constant. The 5-dimensional equations are solved to obtain the 4-dimensional effective gravitational constant and the effective induced 4-dimensional cosmological constant. However, fine-tuning is required to get the effective cosmological constant to agree with the observational value. For a recent review on various approaches used to solve the cosmological constant problem, see
In the ADD model, the vacuum solution is taken to be the standard bulk Minkowski metric, with the n extra dimensions compactified on an n-torus. A torus is obviously a zero curvature manifold. However, it is topologically very dissimilar to a situation in which the extra dimensions are non-compact. As a result, the vacuum of the former manifold is dissimilar to the vacuum of the latter, non-compact manifold. It is a standard result in quantum field theory that if a quantum field propagates in all the dimensions, the vacuum energy associated with it will be different in the two topologically dissimilar manifolds considered above. To get a finite, renormalized value for the vacuum energy associated with the compact manifold, the non-compact contribution is subtracted out. (For a detailed discussion, see ). This is equivalent to stating that the absolute zero of energy is taken to be a state in which all dimensions are non-compact, and the metric Minkowskian. In the ADD model, the gravitational field is the only field which propagates in all the dimensions, with the matter fields being forever stuck on the 3-brane. Even in the so-called vacuum state, since the extra dimensions are compact, there will be a vacuum stress due to compactification, giving rise to zero point vacuum fluctuations which after renormalization will be shown to be finite. It will be seen that this net vacuum energy is nothing but the renormalized zero-point energy of all the massive Kaluza-Klein modes associated with the gravitational field. In the following, this vacuum energy is explicitly calculated for two extra compact dimensions, and the result generalized to $`n`$ extra dimensions. It is seen that if this vacuum energy is to contribute to the observed cosmalogical constant, this imposes serious constraints on the number of extra dimensions and their size.

## A Toy Model

We begin by studying a toy model in 1+1 dimensions, in which the single spatial dimension is compact (See ) and spacetime is $`R^1\times S^1`$. The spatial points $`x`$ and $`x+R`$ are identified, where $`R`$ is the periodicity length or ’circumference’ of the spatial section. Consider a massless scalar field propagating in this spacetime. Then, the effect of the compactification is to restrict the modes of propagation of the scalar field to the form

$$\varphi _k=\frac{1}{\sqrt{2R\omega }}e^{ı(kx\omega t)}$$
(4)
where $`k=(2m\pi )/R`$ and $`\omega =|k|`$, $`m`$ being an integer. The field $`\varphi `$ is expanded in terms of creation and annihilation operators and the modes $`\varphi _k`$ as

$$\varphi (t,x)=\underset{m}{}[a_m\varphi _m+a_m^{}\varphi _m^{}]$$
(5)
The vacuum expectation value of the energy density is calculated to be

$$0_R|T_{00}|0_R=\frac{2\pi }{R^2}\underset{m=0}{\overset{\mathrm{}}{}}m$$
(6)
where $`|0_R`$ is the vacuum state for this compact manifold and is defined by $`a_m|0_R=0`$. As expected, this is infinite. However, we renormalize it by demanding that the vacuum energy associated with the manifold $`R^1\times R^1`$ should be zero, which is the standard Minkowski manifold in the limit $`R\mathrm{}`$. This renormalization implies that we subtract the vacuum contribution as $`R\mathrm{}`$ from the expression given in eqn.(6),i.e., the renormalized energy density of the compactified vacuum is given by

$$0_R|T_{00}|0_R_{ren}=0_R|T_{00}|0_R0_R|T_{00}|0_R|_R\mathrm{}$$
(7)
This can be achieved by standard regularization techniques (see) in which the vacuum expectation value is regularized by a cutoff and the limit $`R\mathrm{}`$ is subtracted from the result and finally, the regularization removed. The result is finite, giving

$$0_R|T_{00}|0_R_{ren}=\frac{\pi }{6R^2}$$
(8)
One convenient regularization is the zeta function regularization (see ), in which the expression $`_{m=0}^{\mathrm{}}m`$ is identified with the analytically continued value of the Reimann zeta function $`\zeta (s)`$ at the point $`s=1`$. This is finite, and is given by $`\zeta (1)=1/12`$, giving the vacuum energy in eqn.(8) directly, without any explicit subtraction. This technique is very common in the study of quantum field theory in curved spacetime. This is the technique we shall employ in this paper.

## Calculation Of Vacuum Energy In The ADD Model

The calculation of the vacuum energy due to compactification will now be carried out in the ADD scenario. We shall consider a spacetime which is a direct product of a non-compact 4-dimensional spacetime and two compact spatial extra dimensions compactified to a 2-torus. The matter fields forever reside on the 3-brane (the non-compact 4-dimensional spacetime) and gravity propagates in the bulk. The vacuum metric is Minkowskian. We consider the propagation of linearized gravity in this bulk spacetime. The Lagrangian for the system is the Fierz-Pauli Lagrangian given by

$$=\frac{1}{4}(^{\widehat{\mu }}\widehat{h}^{\widehat{\nu }\widehat{\rho }}_{\widehat{\mu }}\widehat{h}_{\widehat{\nu }\widehat{\rho }}^{\widehat{\mu }}\widehat{h}_{\widehat{\mu }}\widehat{h}2\widehat{h}^{\widehat{\mu }}\widehat{h}_{hat\mu }+2\widehat{h}^{\widehat{\mu }}_{\widehat{\mu }}\widehat{h})$$
(9)
where $`\widehat{h}=\widehat{h}_{\widehat{\mu }}^{\widehat{\mu }},\widehat{h}_{\widehat{\nu }}=^{\widehat{\mu }}\widehat{h}_{\widehat{\mu }\widehat{\nu }}`$ and the Greek indices run over the 6 bulk coordinates. Raising and lowering of indices has been carried out using the bulk Minkowski metric $`\eta ^{\widehat{\mu }\widehat{\nu }}=diag(1,1,1,1,1,1)`$. The equations of motion in the de Donder gauge are the d’Alembert equations

$$\mathrm{}_{(4+2)}\left(\widehat{h}_{\widehat{\mu }\widehat{\nu }}\frac{1}{2}\eta _{\widehat{\mu }\widehat{\nu }}\widehat{h}\right)=0$$
(10)
Now, a Kaluza-Klein reduction is carried out as (see )

$$\widehat{h}_{\widehat{\mu }\widehat{\nu }}=\frac{1}{R}\left(\begin{array}{cc}h_{\mu \nu }+\eta _{\mu \nu }\varphi & A_{\mu i}\hfill \\ A_{\nu j}& 2\varphi _{ij}\hfill \end{array}\right)$$
(11)
where $`R`$ is the size of each extra spatial dimension, $`\varphi =\varphi _{ii}`$, $`\mu ,\nu =0,1,2,3`$ and $`ı,j=1,2`$. The bulk linearized field can be expanded in terms of creation and annihilation operators. For notational simplicity, we shall suppress the tensor indices and the polarization states of the bulk graviton field and denote it by $`\mathrm{\Phi }`$. Then, in terms of the modes, it is given by

$$\mathrm{\Phi }(x,y)=\frac{1}{R}\underset{n_1,n_2}{}\frac{d^3k}{(2\pi )^32\omega (k)_{n_1,n_2}}[a(k)_{n_1,n_2}e^{ık.x}e^{ı\frac{2\pi }{R}(n_1y_1+n_2y_2)}+h.c.]$$
(12)
where $`x`$ denotes the four brane spacetime coordinates and $`y`$ are the two compact coordinates. The commutation relations satisfied by the operators $`a(k)_{n_1,n_2}`$ are

$$[a(k)_{n_1,n_2},a(k^{})_{m_1,m_2}]=\delta _{n_1m_1}\delta _{n_2m_2}2(2\pi )^3\omega (k)_{n_1,n_2}\delta (\stackrel{}{k}\stackrel{}{k^{}})$$
(13)
where $`\omega (k)_{n_1,n_2}=\sqrt{\stackrel{}{k}^2+4\pi ^2(n_1^2+n_2^2)/R^2}`$.
The vacuum state is defined as $`a(k)_{n_1,n_2}|0_R=0`$. The vacuum expectation value of the stress-tensor associated with the field $`\mathrm{\Phi }`$ is calculated and identifying the quantity $`R\mathrm{\Phi }`$ as the effective four dimensional field (analogous to eqn.(11)) , the four dimensional vacuum energy density is given by

$$0_R|T_{00}|0_R=E_{vac}=\underset{n1,n2=1}{\overset{\mathrm{}}{}}\frac{d^3k}{(2\pi )^3}\sqrt{\stackrel{}{k}^2+\frac{4\pi ^2(n_1^2+n_2^2)}{R^2}}$$
(14)
To regularize the $`k`$ integration, we write the integral as

$$I(m_𝐧)=\mu ^{2ϵ}\frac{d^3k}{(2\pi )^3}(\stackrel{}{k}^2+m_𝐧^2)^{\frac{1}{2}ϵ}$$
(15)
where $`m_𝐧^2=\frac{4\pi ^2(n_1^2+n_2^2)}{R^2}`$ and $`\mu `$ is a parameter with dimensions of mass. The parameter $`ϵ`$ is introduced for regularization, and will finally be taken to be zero. In this form, eqn.(14) is seen to represent simply the zero point energy of the massive Kaluza-Klein tower on the brane. The $`k`$ integral is given in terms of the beta function as

$`I(m_𝐧)`$ $`=`$ $`{\displaystyle \frac{m_𝐧^4}{4\pi ^2}}\left({\displaystyle \frac{\mu ^2}{m_𝐧^2}}\right)^ϵB(3/2,2+ϵ)`$ (16)
$`=`$ $`{\displaystyle \frac{m_𝐧^4}{32\pi ^2}}\left({\displaystyle \frac{1}{ϵ}}+2\mathrm{log}2{\displaystyle \frac{1}{2}}\mathrm{log}({\displaystyle \frac{m_𝐧^2}{\mu ^2}})\right)`$
where the final expression holds for infinitesimal $`ϵ`$. Then, the vacuum energy is given by

$$E_{vac}=\frac{1}{32\pi ^2}\underset{n1,n2=1}{\overset{\mathrm{}}{}}m_𝐧^4\left(\frac{1}{ϵ}+2\mathrm{log}2\frac{1}{2}\mathrm{log}(\frac{m_𝐧^2}{\mu ^2})\right)$$
(17)
The $`k`$ integral has been regularized, but the summation over modes is still to be regularized and the renormalized value obtained. This operation is carried out using the zeta-function regularization. We identify the summations over $`n_1`$ and $`n_2`$ as analytically continued values of the zeta-function and it’s derivatives. Then,

$`{\displaystyle \underset{n1,n2=1}{\overset{\mathrm{}}{}}}m_𝐧^4`$ $`=`$ $`\left({\displaystyle \frac{4\pi ^2}{R^2}}\right)^2{\displaystyle \underset{n1,n2=1}{\overset{\mathrm{}}{}}}(n_1^4+n_2^4+2n_1^2n_2^2)`$ (18)
$`=`$ $`\left({\displaystyle \frac{4\pi ^2}{R^2}}\right)^22[\zeta (0)\zeta (4)+\zeta ^2(2)]`$
$`=`$ $`0`$
since $`\zeta (2m)=0`$, if $`m`$ is a natural number. Therefore, the resulting vacuum energy is given by

$`E_{vac}`$ $`=`$ $`{\displaystyle \frac{1}{32\pi ^2}}{\displaystyle \underset{n1,n2=1}{\overset{\mathrm{}}{}}}m_𝐧^4\mathrm{log}({\displaystyle \frac{m_𝐧^2}{\mu ^2}})`$
$`=`$ $`{\displaystyle \frac{\pi ^2}{2R^4}}{\displaystyle \underset{n1,n2=1}{\overset{\mathrm{}}{}}}(n_1^2+n_2^2)^2\mathrm{log}(n_1^2+n_2^2)`$
$`=`$ $`{\displaystyle \frac{\pi ^2}{R^4}}\zeta (0)\zeta ^{}(4)`$ (20)
where $`\zeta (0)=1/2`$ and $`\zeta ^{}(4)=0.008`$. Since we had suppressed the graviton polarization indices in making this calculation, we multiply the final result with the number of degrees of freedom for a graviton in $`4+2`$ dimensions, which is $`9`$. Therefore, the final vacuum energy is given by

$$E_{vac}_{4+2}=\frac{9\pi ^2}{R^4}\zeta (0)\zeta ^{}(4)$$
(21)
A straightforward calculation genaralizes the result to $`4+n`$ dimensions, and is given by

$$E_{vac}_{4+n}=\frac{\pi ^2}{R^4}\left[\frac{(2+n)(3+n)}{2}1\right][\zeta (0)]^{n1}\zeta ^{}(4)$$
(22)
where the factor in the brackets is just the number of graviton degrees of freedom in $`4+n`$ dimensions.

## Constraints On The ADD Model

If the vacuum energy associated with the massive Kaluza-Klein modes is to account for the origin of the cosmological constant, it would put severe constraints on the number of extra dimensions and the compactification radius of the extra dimensions. Firstly, it is to be noted that the sign of the vacuum energy depends on the number of the extra dimensions, being positive for even and negative for odd number of extra dimensions. We would like to put bounds on $`n`$ and $`R`$ in the above expression by demanding that

$$E_{vac}_{4+n}10^{47}(GeV)^4$$
(23)
Then, it is seen that the bound on $`R`$ is not very sensitive to the number of extra dimensions, $`n`$. It is seen that for $`n`$ varying from $`2`$ to $`10`$, the above inequality approximately constrains $`R`$ to essentially the same lower value, $`R0.1`$ mm. However, there is a consistency condition relating the 4-dimensional Planck scale $`M_{pl}`$ and the bulk scale of gravitation, $`M_s`$. This relation goes as

$$M_{pl}^2R^nM_s^{n+2}$$
(24)
For $`R`$ constrained to $`R0.1`$ mm., this consistency equation gives sensible values of $`M_s`$ for $`n=1,2`$ only. For $`n=2`$, this gives $`M_s1`$ TeV, which is acceptable and interesting from the hierarchy problem point of view. For $`n=3`$, $`M_s`$ is constrained to lie below a few GeV, which is phenomenologically ruled out. Higher values of $`n`$ become more and more unacceptable. The situation for $`n=1`$ gives $`M_s10^8`$ Gev, the equality holding for $`R=0.1`$ mm, and the inequality for $`R>0.1`$mm. Therefore, since $`R>0.1`$ mm. will be in conflict with macroscopic gravitational experiments, this situation is acceptable only for $`M_s10^8`$ GeV, which would however not get rid of the hierarchy problem.

$`n=2`$ therefore seems to be the only viable possibility which would solve the hierarchy problem and not be in conflict with high-energy experiments at the same time. However, since the lower constraint on $`R`$ is of the order of $`0.1`$ mm., this simply

means that macroscopic tests of gravitation ought to reveal deviations from Newton’s law of gravitation at distances comparable to this. Thus, if the ADD model is the correct description of spacetime and if this vacuum energy is to contribute to the observed cosmological constant, then deviations from Newtonian gravity at scales of the order of $`0.1`$ mm. should show up. Any failure in observing such deviations at length scales $`0.1`$ mm. will imply that unless there exists some deeper symmetry/mechanism that removes this finite vacuum energy associated with compactification, the ADD model fails to give an accurate description of spacetime.

## Conclusions

We have calculated the topological vacuum energy of linearized gravity in the ADD scenario and shown that if this is to account for the observational bounds on the cosmological constant, the size of the compact dimensions should be $`0.1`$ mm. The vacuum energy is shown to be just the zero point energy of the massive Kaluza-Klein modes. The calculation has been carried out for a toroidal topology of the compact manifold, but the essential features of the calculation are not expected to change if some other locally flat non-trivial topology is taken. The result after zeta-function regularization and appropriate renormalization condition is seen to be finite, and not sensitive to the UV cut-off of the theory, as would have been dimensionally expected. The reason is the subtraction of infinite (or large but finite in case of a finite UV cut-off) vacuum energy associated with the trivial topology when the extra dimensions are not curled up or compact. The result has been generelized for the case of an n-torus. If this vacuum energy is to account for observational constraints on the cosmological constant, this would put severe constraints on the volume of the compact manifold and it’s dimensionality.


text:
# Quantum Certificate Complexity

## 1 Background

Most of what is known about the power of quantum computing can be cast in the query or decision-tree model . Here one counts only the number of queries to the input, not the number of computational steps. The appeal of this model lies in its extreme simplicity—in contrast to (say) the Turing machine model, one feels the query model ought to be ‘completely understandable.’ In spite of this, open problems abound.

Let $`f:Dom\left(f\right)\{0,1\}`$ be a Boolean function with $`Dom\left(f\right)\{0,1\}^n`$, that takes input $`Y=y_1\mathrm{}y_n`$. Then the deterministic query complexity $`D\left(f\right)`$ is the minimum number of queries to the $`y_i`$’s needed to evaluate $`f`$, if $`Y`$ is chosen adversarially and if queries can be adaptive (that is, can depend on the outcomes of previous queries). Also, the bounded-error randomized query complexity, $`R_2\left(f\right)`$, is the minimum expected number of queries needed by a randomized algorithm that, for each $`YDom\left(f\right)`$, outputs $`f\left(Y\right)`$ with probability at least $`2/3`$. Here the ‘$`2`$’ refers to two-sided error; if instead we require $`f\left(Y\right)`$ to be output with probability $`1`$ for every $`Y`$, we obtain $`R_0\left(f\right)`$, or zero-error randomized query complexity.

Analogously, $`Q_2\left(f\right)`$ is the minimum number of queries needed by a quantum algorithm that outputs $`f\left(Y\right)`$ with probability at least $`2/3`$ for all $`Y`$. Also, for $`k\{0,1\}`$ let $`Q_0^k\left(f\right)`$ be the minimum number of queries needed by a quantum algorithm that outputs $`f\left(Y\right)`$ with probability $`1`$ if $`f\left(Y\right)=k`$, and with probability at least $`1/2`$ if $`f\left(Y\right)k`$. Then let $`Q_0\left(f\right)=\mathrm{max}\{Q_0^0\left(f\right),Q_0^1\left(f\right)\}`$. If we require a single algorithm that succeeds with probability $`1`$ for all $`Y`$, we obtain $`Q_E\left(f\right)`$, or exact quantum query complexity. See  for detailed definitions and a survey of these measures.

It is immediate that $`Q_2\left(f\right)R_2\left(f\right)R_0\left(f\right)D\left(f\right)n`$, that $`Q_0\left(f\right)R_0\left(f\right)`$, and that $`Q_E\left(f\right)D\left(f\right)`$. If $`f`$ is partial (i.e. $`Dom\left(f\right)\{0,1\}^n`$), then $`Q_2\left(f\right)`$ can be superpolynomially smaller than $`R_2\left(f\right)`$; this is what makes Shor’s period-finding algorithm  possible. For total $`f`$, by contrast, the largest known gap even between $`D\left(f\right)`$ and $`Q_2\left(f\right)`$ is quadratic, and is achieved by the $`OR`$ function on $`n`$ bits: $`D\left(OR\right)=n`$ (indeed $`R_2\left(OR\right)=\mathrm{\Omega }\left(n\right)`$), whereas $`Q_2\left(OR\right)=\mathrm{\Theta }\left(\sqrt{n}\right)`$ because of Grover’s search algorithm . Furthermore, for total $`f`$, Beals et al.  showed that $`D\left(f\right)=O\left(Q_2\left(f\right)^6\right)`$, while de Wolf  showed that $`D\left(f\right)=O\left(Q_2\left(f\right)^2Q_0\left(f\right)^2\right)`$.

The result of Beals et al.  relies on two intermediate complexity measures, the certificate complexity $`C\left(f\right)`$ and block sensitivity $`bs\left(f\right)`$, which we now define.

###### Definition 1

A certificate for an input $`X`$ is a set $`S\{1,\mathrm{},n\}`$ such that for all $`YDom\left(f\right)`$, if $`y_i=x_i`$ for all $`iS`$ then $`f\left(Y\right)=f\left(X\right)`$. Then $`C^X\left(f\right)`$ is the minimum size of a certificate for $`X`$, and $`C\left(f\right)`$ is the maximum of $`C^X\left(f\right)`$ over all $`X`$.

###### Definition 2

A sensitive block on input $`X`$ is a set $`B\{1,\mathrm{},n\}`$ such that $`f\left(X^{\left(B\right)}\right)f\left(X\right)`$, where $`X^{\left(B\right)}`$ is obtained from $`X`$ by flipping $`x_i`$ for each $`iB`$. Then $`bs^X\left(f\right)`$ is the maximum number of disjoint sensitive blocks on $`X`$, and $`bs\left(f\right)`$ is the maximum of $`bs^X\left(f\right)`$ over all $`X`$.

Clearly $`bs\left(f\right)C\left(f\right)D\left(f\right)`$. For total $`f`$, these measures are all polynomially related: Nisan  showed that $`C\left(f\right)bs\left(f\right)^2`$, while Beals et al.  showed that $`D\left(f\right)C\left(f\right)bs\left(f\right)`$. Combining these results with $`bs\left(f\right)=O\left(Q_2\left(f\right)^2\right)`$ (from the optimality of Grover’s algorithm), one obtains $`D\left(f\right)=O\left(Q_2\left(f\right)^6\right)`$.

## 2 Our Results

We investigate $`RC\left(f\right)`$ and $`QC\left(f\right)`$, the bounded-error randomized and quantum generalizations of the certificate complexity $`C\left(f\right)`$ (see Table 1). Our motivation is that, just as $`C\left(f\right)`$ was used to show a polynomial relation between $`D\left(f\right)`$ and $`Q_2\left(f\right)`$, so $`RC\left(f\right)`$ and $`QC\left(f\right)`$ can lead to new relations among fundamental query complexity measures.

| Table 1 |  |  |  |
| --- | --- | --- | --- |
| Query complexity | $`D\left(f\right)`$ | $`R_2\left(f\right)`$ | $`Q_2\left(f\right)`$ |
| Certificate complexity | $`C\left(f\right)`$ | $`RC\left(f\right)`$ | $`QC\left(f\right)`$ |

What the certificate complexity $`C\left(f\right)`$ measures is the number of queries used to verify a certificate, not the number of bits used to communicate it. Thus, if we want to generalize $`C\left(f\right)`$, we should assume the latter is unbounded. A consequence is that without loss of generality, a certificate is just a claimed value $`X`$ for the input $`Y`$111Throughout this paper, we use $`Y`$ to denote the ‘actual’ input being queried, and $`X`$ to denote the ‘claimed’ input (whose randomized certificate complexity, block sensitivity, and so on we want to study).—since any additional information that a prover might provide, the verifier can compute for itself. The verifier’s job is to check that $`f\left(Y\right)=f\left(X\right)`$. With this in mind we define $`RC\left(f\right)`$ as follows.

###### Definition 3

A randomized verifier for input $`X`$ is a randomized algorithm that, on input $`YDom\left(f\right)`$, (i) accepts with probability $`1`$ if $`Y=X`$, and (ii) rejects with probability at least $`1/2`$ if $`f\left(Y\right)f\left(X\right)`$. (If $`YX`$ but $`f\left(Y\right)=f\left(X\right)`$, the acceptance probability can be arbitrary.) Then $`RC^X\left(f\right)`$ is the minimum expected number of queries used by a randomized verifier for $`X`$, and $`RC\left(f\right)`$ is the maximum of $`RC^X\left(f\right)`$ over all $`X`$.

We define $`QC\left(f\right)`$ analogously, with quantum instead of randomized algorithms. The following justifies the definition (the $`RC\left(f\right)`$ part was originally shown by Raz et al. ).

###### Proposition 4

Making the error probability two-sided rather than one-sided changes $`RC\left(f\right)`$ and $`QC\left(f\right)`$ by at most a constant factor.

Proof. For $`RC\left(f\right)`$, let $`r_V^Y`$ be the event that verifier $`V`$ rejects on input $`Y`$, and let $`d_V^Y`$ be the event that $`V`$ encounters a disagreement with $`X`$ on $`Y`$. We may assume $`\mathrm{Pr}\left[r_V^Y|d_V^Y\right]=1`$. Suppose that $`Y=X`$ and $`f\left(Y\right)f\left(X\right)`$ both occur with probability $`1/2`$, and that $`\mathrm{Pr}\left[r_V^Y\right]\epsilon _0`$ in the former case and $`\mathrm{Pr}\left[r_V^Y\right]1\epsilon _1`$ in the latter. Then

$`\mathrm{Pr}\left[\mathrm{}d_V^Y|r_V^Y\right]`$ $`={\displaystyle \frac{\mathrm{Pr}\left[r_V^Y|\mathrm{}d_V^Y\right]\mathrm{Pr}\left[\mathrm{}d_V^Y\right]}{\mathrm{Pr}\left[r_V^Y\right]}}`$
$`{\displaystyle \frac{2\epsilon _0}{1\epsilon _1}}\text{.}`$
Now let $`V^{}`$ be identical to $`V`$ except that, whenever $`V`$ rejects despite having found no disagreement with $`X`$, $`V^{}`$ accepts. Clearly $`\mathrm{Pr}\left[r_V^{}^X\right]=0`$. Also, in the case $`f\left(Y\right)f\left(X\right)`$,

$`\mathrm{Pr}\left[r_V^{}^Y\right]`$ $`=\mathrm{Pr}\left[d_V^Y\right]`$
$`\mathrm{Pr}\left[r_V^Y\right]\mathrm{Pr}\left[d_V^Y|r_V^Y\right]`$
$`\left(1\epsilon _1\right)\left(1{\displaystyle \frac{2\epsilon _0}{1\epsilon _1}}\right)\text{.}`$
For $`QC\left(f\right)`$, suppose the verifier’s final state given input $`Y`$ is

$$\underset{z}{}\alpha _z^Y|z\left(\beta _z^Y|0+\gamma _z^Y|1\right)$$

where $`|0`$ is the reject state, $`|1`$ is the accept state, and $`\left|\beta _z^Y\right|^2+\left|\gamma _z^Y\right|^2=1`$ for all $`z`$. Suppose also that $`A^X1\epsilon _0`$ and that $`A^Y\epsilon _1`$ whenever $`f\left(Y\right)f\left(X\right)`$, where $`A^Y=_z\left|\alpha _z^Y\gamma _z^Y\right|^2`$ is the probability of accepting. Then the verifier can make $`A^X=1`$ by performing the conditional rotation

$$\left(\begin{array}{cc}\gamma _z^X& \beta _z^X\\ \beta _z^X& \gamma _z^X\end{array}\right)$$

on the second register prior to measurement. In the case $`f\left(Y\right)f\left(X\right)`$, this produces

$`A^Y`$ $`={\displaystyle \underset{z}{}}\left|\alpha _z^Y\right|^2\left|\beta _z^X\beta _z^Y+\gamma _z^X\gamma _z^Y\right|^2`$
$`2{\displaystyle \underset{z}{}}\left|\alpha _z^Y\right|^2\left(\left|\beta _z^X\right|^2+\left|\gamma _z^Y\right|^2\right)`$
$`2\left(\epsilon _0+\epsilon _1\right)\text{.}`$
It is immediate that $`QC\left(f\right)RC\left(f\right)C\left(f\right)`$, that $`QC\left(f\right)=O\left(Q_2\left(f\right)\right)`$, and that $`RC\left(f\right)=O\left(R_2\left(f\right)\right)`$. We also have $`RC\left(f\right)=\mathrm{\Omega }\left(bs\left(f\right)\right)`$, since a randomized verifier for $`X`$ must query each sensitive block on $`X`$ with $`1/2`$ probability. This suggests viewing $`RC\left(f\right)`$ as an ‘alloy’ of block sensitivity and certificate complexity, an interpretation for which Section 6 gives some justification.

Our results are as follows. In Section 4 we show that $`QC\left(f\right)=\mathrm{\Theta }\left(\sqrt{RC\left(f\right)}\right)`$ for all $`f`$ (partial or total), precisely characterizing quantum certificate complexity in terms of randomized certificate complexity. To do this, we first give a nonadaptive characterization of $`RC\left(f\right)`$, and then apply the adversary method of Ambainis  to lower-bound $`QC\left(f\right)`$ in terms of this characterization. Then, in Section 5, we extend results on polynomials due to de Wolf  and to Nisan and Smolensky (as described by Buhrman and de Wolf ), to show that $`R_0\left(f\right)=O\left(RC\left(f\right)ndeg\left(f\right)\mathrm{log}n\right)`$ for all total $`f`$, where $`ndeg\left(f\right)`$ is the minimum degree of a polynomial $`p`$ such that $`p\left(X\right)0`$ if and only if $`f\left(X\right)0`$. Combining the results of Sections 4 and 5 leads to a new lower bound on quantum query complexity: that $`R_0\left(f\right)=O\left(Q_2\left(f\right)^2Q_0\left(f\right)\mathrm{log}n\right)`$ for all total $`f`$. To our knowledge, this is the first quantum lower bound to use both the adversary method and the polynomial method at different points in the argument.

Finally, in Section 6, we exhibit asymptotic gaps between $`RC\left(f\right)`$ and other query complexity measures, including a total $`f`$ for which $`C\left(f\right)=\mathrm{\Theta }\left(QC\left(f\right)^{2.205}\right)`$, and a symmetric partial $`f`$ for which $`QC\left(f\right)=O\left(1\right)`$ yet $`Q_2\left(f\right)=\mathrm{\Omega }\left(n/\mathrm{log}n\right)`$. We conclude in Section 7 with some open problems.

## 3 Related Work

Raz et al.  studied a query complexity measure they called $`ma\left(f\right)`$, for Merlin-Arthur. In our notation, $`ma\left(f\right)`$ equals the maximum of $`RC^X\left(f\right)`$ over all $`X`$ with $`f\left(X\right)=1`$. Raz et al. observed that $`ma\left(f\right)=ip\left(f\right)`$, where $`ip\left(f\right)`$ is the number of queries needed given arbitrarily many rounds of interaction with a prover. They also used error-correcting codes to construct a total $`f`$ for which $`ma\left(f\right)=O\left(1\right)`$ but $`C\left(f\right)=\mathrm{\Omega }\left(n\right)`$. This has similarities to our construction, in Section 6.3, of a symmetric partial $`f`$ for which $`QC\left(f\right)=O\left(1\right)`$ but $`Q_2\left(f\right)=\mathrm{\Omega }\left(n/\mathrm{log}n\right)`$. Aside from that and from Proposition 4, Raz et al.’s results do not overlap with ours.

Watrous  has investigated a different notion of ‘quantum certificate complexity’—whether certificates that are quantum states can be superpolynomially smaller than any classical certificate. Also, de Wolf  has investigated ‘nondeterministic quantum query complexity’ in the alternate sense of algorithms that accept with zero probability when $`f\left(Y\right)=0`$, and with positive probability when $`f\left(Y\right)=1`$.

## 4 Characterization of Quantum Certificate Complexity

We wish to show that $`QC\left(f\right)=\mathrm{\Theta }\left(\sqrt{RC\left(f\right)}\right)`$, precisely characterizing quantum certificate complexity in terms of randomized certificate complexity. The first step is to give a simpler characterization of $`RC\left(f\right)`$.

###### Lemma 5

Call a randomized verifier for $`X`$ nonadaptive if, on input $`Y`$, it queries each $`y_i`$ with independent probability $`\lambda _i`$, and rejects if and only if it encounters a disagreement with $`X`$. (Thus, we identify such a verifier with the vector $`(\lambda _1,\mathrm{},\lambda _n)`$.) Let $`RC_{na}^X\left(f\right)`$ be the minimum of $`\lambda _1+\mathrm{}+\lambda _n`$ over all nonadaptive verifiers for $`X`$. Then $`RC_{na}^X\left(f\right)=\mathrm{\Theta }\left(RC^X\left(f\right)\right)`$.

Proof. Clearly $`RC_{na}^X\left(f\right)=\mathrm{\Omega }\left(RC^X\left(f\right)\right)`$. For the upper bound, we can assume that a randomized verifier rejects immediately on finding a disagreement with $`X`$, and accepts if it finds no disagreement. Let $`𝒴=\{Y:f\left(Y\right)f\left(X\right)\}`$. Let $`V`$ be an optimal randomized verifier, and let $`p_t\left(Y\right)`$ be the probability that $`V`$, when given input $`Y𝒴`$, finds a disagreement with $`X`$ on the $`t^{th}`$ query. By Markov’s inequality, $`V`$ must have found a disagreement with probability at least $`1/2`$ after $`T=2RC^X\left(f\right)`$ queries. So by the union bound

$$p_1\left(Y\right)+\mathrm{}+p_T\left(Y\right)1/2$$

for each $`Y𝒴`$. Suppose we choose $`t\{1,\mathrm{},T\}`$ uniformly at random and simulate the $`t^{th}`$ query, pretending that queries $`1,\mathrm{},t1`$ have already been made and have returned agreement with $`X`$. Then we must find a disagreement with probability at least $`1/2T`$. By repeating this procedure $`4T`$ times, we can boost the probability to $`1e^2`$. For $`i\{1,\mathrm{},n\}`$, let $`\lambda _i`$ be the probability that $`y_i`$ is queried at least once. Then $`\lambda _1+\mathrm{}+\lambda _n4T`$, whereas for each $`Y𝒴`$,

$$\underset{i:y_ix_i}{}\lambda _i1e^2.$$

It follows that, if each $`y_i`$ is queried with independent probability $`\lambda _i`$, then the probability that at least one $`y_i`$ disagrees with $`X`$ is at least

$$1\underset{i:y_ix_i}{}\left(1\lambda _i\right)1\left(1\frac{1e^2}{n}\right)^n>0.57.$$

To obtain a lower bound on $`QC\left(f\right)`$, we use the following simple reformulation of the adversary method of Ambainis .

###### Theorem 6 (Ambainis)

Let $`\beta `$ be a function from $`Dom\left(f\right)`$ to nonnegative reals, and let $`R:Dom\left(f\right)^2\{0,1\}`$ be a relation such that $`R(X,Y)=R(Y,X)`$ for all $`X,Y`$ and $`R(X,Y)=0`$ whenever $`f\left(X\right)=f\left(Y\right)`$. Let $`\delta _0,\delta _1(0,1]`$ be such that for every $`XDom\left(f\right)`$ and $`i\{1,\mathrm{},n\}`$,

$`{\displaystyle \underset{Y:R(X,Y)=1}{}}\beta \left(Y\right)`$ $`1,`$
$`{\displaystyle \underset{Y:R(X,Y)=1,x_iy_i}{}}\beta \left(Y\right)`$ $`\delta _{f\left(X\right)}.`$
Then $`Q_2\left(f\right)=\mathrm{\Omega }\left(\sqrt{\frac{1}{\delta _0\delta _1}}\right)`$.

We now prove the main result of the section.

###### Theorem 7

For all $`f`$ (partial or total) and all $`X`$, $`QC^X\left(f\right)=\mathrm{\Theta }\left(\sqrt{RC^X\left(f\right)}\right)`$.

Proof. Let $`(\lambda _1,\mathrm{},\lambda _n)`$ be an optimal nonadaptive randomized verifier for $`X`$, and let

$$S=\lambda _1+\mathrm{}+\lambda _n.$$

First, $`QC^X\left(f\right)=O\left(\sqrt{S}\right)`$. We can run a “weighted Grover search,” in which the proportion of basis states querying index $`i`$ is within a constant factor of $`\lambda _i/S`$. (It suffices to use $`n^2`$ basis states.) Let $`𝒴=\{Y:f\left(Y\right)f\left(X\right)\}`$; then for any $`Y𝒴`$, $`O\left(\sqrt{S}\right)`$ iterations suffice to find a disagreement with $`X`$ with probability $`\mathrm{\Omega }\left(1\right)`$.

Second, $`QC^X\left(f\right)=\mathrm{\Omega }\left(\sqrt{S}\right)`$. Consider a matrix game in which Alice chooses an index $`i`$ to query and Bob chooses $`Y𝒴`$; Alice wins if and only if $`y_ix_i`$. If both players are rational, then Alice wins with probability $`O\left(1/S\right)`$, since otherwise Alice’s strategy would yield a verifier $`(\lambda _1^{},\mathrm{},\lambda _n^{})`$ with

$$\lambda _1^{}+\mathrm{}+\lambda _n^{}=o\left(S\right).$$

Hence by the minimax theorem, there exists a distribution $`\mu `$ over $`𝒴`$ such that for every $`i`$,

$$\underset{Y\mu }{\mathrm{Pr}}\left[y_ix_i\right]=O\left(1/S\right).$$

Let $`\beta \left(X\right)=1`$ and let $`\beta \left(Y\right)=\mu \left(Y\right)`$ for each $`Y𝒴`$. Also, let $`R(Y,Z)=1`$ if and only if $`Z=X`$ for each $`Y𝒴`$ and $`Z𝒴`$. Then we can take $`\delta _{f\left(Y\right)}=1`$ and $`\delta _{f\left(X\right)}=O\left(1/S\right)`$ in Theorem 6. So the quantum query complexity of distinguishing $`X`$ from an arbitrary $`Y𝒴`$ is $`\mathrm{\Omega }\left(\sqrt{S}\right)`$.

## 5 Quantum Lower Bound for Total Functions

Our goal is to show that

$$R_0\left(f\right)=O\left(Q_2\left(f\right)^2Q_0\left(f\right)\mathrm{log}n\right).$$

Say that a real multilinear polynomial $`p(x_1,\mathrm{},x_n)`$ nondeterministically represents $`f`$ if for all $`X\{0,1\}^n`$, $`p\left(X\right)0`$ if and only if $`f\left(X\right)0`$. Let $`ndeg\left(f\right)`$ be the minimum degree of a nondeterministic polynomial for $`f`$. Also, given such a polynomial $`p`$, say that a monomial $`M_1p`$ is covered by $`M_2p`$ if $`M_2`$ contains every variable in $`M_1`$. We call $`M`$ a maxonomial if it is not covered by any other monomial of $`p`$. The following is a simple generalization of a lemma attributed in  to Nisan and Smolensky.

###### Lemma 8 (Nisan-Smolensky)

Let $`p`$ nondeterministically represent $`f`$. Then for every maxonomial $`M`$ of $`p`$ and $`Xf^1\left(0\right)`$, there is a set $`B`$ of variables in $`M`$ such that $`f\left(X^{\left(B\right)}\right)f\left(X\right)`$, where $`X^{\left(B\right)}`$ is obtained from $`X`$ by flipping the variables in $`B`$.

Proof. Obtain a restricted function $`g`$ from $`f`$, and a restricted polynomial $`q`$ from $`p`$, by setting each variable outside of $`M`$ to $`x_i`$. Then $`g`$ cannot be constant, since its representing polynomial $`q`$ contains $`M`$ as a monomial. Thus there is a subset $`B`$ of variables in $`M`$ such that $`g\left(X^{\left(B\right)}\right)=1`$, and hence $`f\left(X^{\left(B\right)}\right)=1`$.

Using Lemma 8, de Wolf  showed that $`D\left(f\right)C\left(f\right)ndeg\left(f\right)`$ for all total $`f`$ (slightly improving the result $`D\left(f\right)C\left(f\right)\mathrm{deg}\left(f\right)`$ due to Buhrman and de Wolf ). In Theorem 10, we will give an analog of this result for randomized query and certificate complexities. However, we first need a probabilistic lemma.

###### Lemma 9

Suppose we repeatedly apply the following procedure: first identify the set $`B`$ of maxonomials of $`p`$, then ‘shrink’ each $`MB`$ with (not necessarily independent) probability at least $`1/2`$. Shrinking $`M`$ means replacing it by an arbitrary monomial of degree $`\mathrm{deg}\left(M\right)1`$. Then with high probability $`p`$ is a constant polynomial after $`O\left(\mathrm{deg}\left(p\right)\mathrm{log}n\right)`$ iterations.

Proof. For any set $`A`$ of monomials, consider the weighting function

$$\omega \left(A\right)=\underset{MA}{}\mathrm{deg}\left(M\right)!$$

Let $`S`$ be the set of monomials of $`p`$. Initially

$$\omega \left(S\right)n^{\mathrm{deg}\left(p\right)}\mathrm{deg}\left(p\right)!$$

and we are done when $`\omega \left(S\right)=0`$. We claim that at every iteration, $`\omega \left(B\right)\frac{1}{e}\omega \left(S\right)`$. For every $`M^{}SB`$ is covered by some $`MB`$, but a given $`MB`$ can cover at most $`\left(\genfrac{}{}{0pt}{}{\mathrm{deg}\left(M\right)}{l}\right)`$ distinct $`M^{}`$ with $`\mathrm{deg}\left(M^{}\right)=l`$. Hence

$`\omega \left(SB\right)`$ $`{\displaystyle \underset{MB}{}}{\displaystyle \underset{l=0}{\overset{\mathrm{deg}\left(M\right)1}{}}}\left(\genfrac{}{}{0pt}{}{\mathrm{deg}\left(M\right)}{l}\right)l!`$
$`{\displaystyle \underset{MB}{}}\mathrm{deg}\left(M\right)!({\displaystyle \frac{1}{1!}}+{\displaystyle \frac{1}{2!}}+\mathrm{})`$
$`\left(e1\right)\omega \left(B\right).`$
At every iteration, the contribution of each $`MB`$ to $`\omega \left(A\right)`$ has at least $`1/2`$ probability of shrinking from $`\mathrm{deg}\left(M\right)!`$ to $`\left(\mathrm{deg}\left(M\right)1\right)!`$ (or to $`0`$ if $`\mathrm{deg}\left(M\right)=1`$). Hence $`\omega \left(S\right)`$ decreases by an expected amount at least $`\frac{1}{4e}\omega \left(S\right)`$. Thus after

$$\mathrm{log}_{4e/\left(4e1\right)}(2n^{\mathrm{deg}\left(p\right)}\mathrm{deg}\left(p\right)!)=O\left(\mathrm{deg}\left(p\right)\mathrm{log}n\right)$$

iterations, the expectation of $`\omega \left(S\right)`$ is less than $`1/2`$, so $`S`$ is empty with probability at least $`1/2`$.

###### Theorem 10

For total $`f`$,

$$R_0\left(f\right)=O\left(RC\left(f\right)ndeg\left(f\right)\mathrm{log}n\right).$$

Proof. Choose an $`X`$ with $`f\left(X\right)=0`$, and let $`(\lambda _1,\mathrm{},\lambda _n)`$ be a nonadaptive randomized verifier for $`X`$. Form $`I\{1,\mathrm{},n\}`$ by placing each $`i`$ in $`I`$ with independent probability $`\lambda _i`$. Then for any $`Z\{0,1\}^n`$, let $`Z^{\left[I\right]}`$ be obtained from $`Z`$ by setting $`z_i`$ to $`x_i`$ for each $`iI`$. We have $`\mathrm{Pr}_I\left[f\left(Z^{\left[I\right]}\right)=0\right]1/2`$. But by Lemma 8, for every maxonomial $`M`$ of $`f`$, there exists a $`Z`$ that disagrees with $`X`$ only on variables occurring in $`M`$, such that $`f\left(Z\right)=1`$. It follows that for every $`M`$, $`I`$ contains the index of a variable in $`M`$ with probability at least $`1/2`$.

Given input $`Y`$, the randomized algorithm is as follows. First query the indices in $`I`$, and let $`f_1`$ be the restriction of $`f`$ induced by this. Then repeat the above procedure on $`f_1`$—that is, choose an $`X_1`$ with $`f_1\left(X_1\right)=0`$ (assuming one exists), and then query a set $`I_1`$ drawn using a nonadaptive randomized verifier for $`X_1`$. Continue in this manner until $`f`$ is restricted to a constant function $`f_T`$. At this point, if $`f_T`$ is identically $`0`$ then we know $`f\left(Y\right)=0`$; otherwise we know $`f\left(Y\right)=1`$.

Each iteration of the algorithm uses an expected number of queries at most $`RC\left(f\right)`$, since $`RC\left(g\right)RC\left(f\right)`$ for every restriction $`g`$ of $`f`$. Furthermore, since an iteration shrinks each maxonomial with probability at least $`1/2`$, Lemma 9 implies that with $`\mathrm{\Omega }\left(1\right)`$ probability, $`f_T`$ is constant after $`T=O\left(ndeg\left(f\right)\mathrm{log}n\right)`$ iterations.

Buhrman et al.  showed that $`ndeg\left(f\right)2Q_0\left(f\right)`$. Combining this with Theorems 7 and 10, we obtain a new relation between classical and quantum query complexity.

###### Theorem 11

For total $`f`$,

$$R_0\left(f\right)=O\left(Q_2\left(f\right)^2Q_0\left(f\right)\mathrm{log}n\right).$$

The best previous relation of this kind was $`R_0\left(f\right)=O\left(Q_2\left(f\right)^2Q_0\left(f\right)^2\right)`$, due to de Wolf .

## 6 Asymptotic Gaps

Having related $`RC\left(f\right)`$ and $`QC\left(f\right)`$ to other query complexity measures in Section 5, in what follows we seek the largest possible asymptotic gaps among the measures. In particular, Section 6.1 gives a total $`f`$ for which $`RC\left(f\right)=\mathrm{\Theta }\left(C\left(f\right)^{0.907}\right)`$ and hence $`C\left(f\right)=\mathrm{\Theta }\left(QC\left(f\right)^{2.205}\right)`$, as well as a total $`f`$ for which $`bs\left(f\right)=\mathrm{\Theta }\left(RC\left(f\right)^{0.922}\right)`$. Although these gaps are the largest of which we know, Section 6.2 shows that no ‘local’ technique can improve the relations $`C\left(f\right)=O\left(RC\left(f\right)^2\right)`$ and $`RC\left(f\right)=O\left(bs\left(f\right)^2\right)`$. Finally, Section 6.3 uses combinatorial designs to construct a symmetric partial $`f`$ for which $`RC\left(f\right)`$ and $`QC\left(f\right)`$ are $`O\left(1\right)`$, yet $`Q_2\left(f\right)=\mathrm{\Omega }\left(n/\mathrm{log}n\right)`$.

### 6.1 Certificate Complexity, Randomized Certificate Complexity, and Block Sensitivity

Wegener and Zádori  exhibited total Boolean functions with asymptotic gaps between $`C\left(f\right)`$ and $`bs\left(f\right)`$. In similar fashion, we give a function family $`\left\{g_t\right\}`$ with an asymptotic gap between $`C\left(g_t\right)`$ and $`RC\left(g_t\right)`$. Let $`g_1(x_1,\mathrm{},x_{29})`$ equal $`1`$ if and only if the Hamming weight of its input is $`13`$, $`14`$, $`15`$, or $`16`$. (The parameter $`29`$ was found via computer search to produce a maximal separation.) Then for $`t>1`$, let

$$g_t(x_1,\mathrm{},x_{29^t})=g_0[g_{t1}\left(X_1\right),\mathrm{},g_{t1}\left(X_{29}\right)]$$

where $`X_1`$ is the first $`29^{t1}`$ input bits, $`X_2`$ is the second $`29^{t1}`$, and so on. For $`k\{0,1\}`$, let

$`bs^k\left(f\right)`$ $`=\underset{f\left(X\right)=k}{\mathrm{max}}bs^X\left(f\right),`$
$`C^k\left(f\right)`$ $`=\underset{f\left(X\right)=k}{\mathrm{max}}C^X\left(f\right).`$
Then since $`bs^0\left(g_1\right)=bs^1\left(g_1\right)=17`$, we have $`bs\left(g_t\right)=17^t`$. On the other hand, $`C^0\left(g_1\right)=17`$ but $`C^1\left(g_1\right)=26`$, so

$`C^1\left(g_t\right)`$ $`=13C^1\left(g_{t1}\right)+13C^0\left(g_{t1}\right),`$
$`C^0\left(g_t\right)`$ $`=17\mathrm{max}\{C^1\left(g_{t1}\right),C^0\left(g_{t1}\right)\}.`$
Solving this recurrence yields $`C\left(g_t\right)=\mathrm{\Theta }\left(22.725^t\right)`$. We can now show a gap between $`C`$ and $`RC`$.

###### Proposition 12

$`RC\left(g_t\right)=\mathrm{\Theta }\left(C\left(g_t\right)^{0.907}\right)`$.

Proof. Since $`bs\left(g_t\right)=\mathrm{\Omega }\left(C\left(g_t\right)^{0.907}\right)`$, it suffices to show that $`RC\left(g_t\right)=O\left(bs\left(g_t\right)\right)`$. The randomized verifier $`V`$ chooses an input variable to query as follows. Let $`X`$ be the claimed input, and let $`K=_{i=1}^{29}g_{t1}\left(X_i\right)`$. Let $`I_0=\{i:g_{t1}\left(X_i\right)=0\}`$ and $`I_1=\{i:g_{t1}\left(X_i\right)=1\}`$. With probability $`p_K`$, $`V`$ chooses an $`iI_1`$ uniformly at random; otherwise $`A`$ chooses an $`iI_0`$ uniformly at random. Here $`p_K`$ is as follows.

| $`K`$ | $`[0,12]`$ | $`13`$ | $`14`$ | $`15`$ | $`16`$ | $`[17,29]`$ |
| --- | --- | --- | --- | --- | --- | --- |
| $`p_K`$ | $`0`$ | $`\frac{13}{17}`$ | $`\frac{7}{12}`$ | $`\frac{5}{12}`$ | $`\frac{4}{17}`$ | $`1`$ |

Once $`i`$ is chosen, $`V`$ repeats the procedure for $`X_i`$, and continues recursively in this manner until reaching a variable $`y_j`$ to query. One can check that if $`g_t\left(X\right)g_t\left(Y\right)`$, then $`g_{t1}\left(X_i\right)g_{t1}\left(Y_i\right)`$ with probability at least $`1/17`$. Hence $`x_jy_j`$ with probability at least $`1/17^t`$, and $`RC\left(g_t\right)=O\left(17^t\right)`$.

By Theorem 7, it follows that $`C\left(g_t\right)=\mathrm{\Theta }\left(QC\left(g_t\right)^{2.205}\right)`$. This offers a surprising contrast with the query complexity setting, where the best known gap between the deterministic and quantum measures is quadratic ($`D\left(f\right)=\mathrm{\Theta }\left(Q_2\left(f\right)^2\right)`$).

The family $`\left\{g_t\right\}`$ happens not to yield an asymptotic gap between $`bs\left(f\right)`$ and $`RC\left(f\right)`$. The reason is that any input to $`g_0`$ can be covered perfectly by sensitive blocks of minimum size, with no variables left over. In general, though, we can have $`bs\left(f\right)=o\left(RC\left(f\right)\right)`$. As reported by Bublitz et al. , M. Paterson found a total Boolean function $`h_1(x_1,\mathrm{},x_6)`$ such that $`C^X\left(h_1\right)=5`$ and $`bs^X\left(h_1\right)=4`$ for all $`X`$. Composing $`h_1`$ recursively yields $`bs\left(h_t\right)=\mathrm{\Theta }\left(C\left(h_t\right)^{0.861}\right)`$ and $`bs\left(h_t\right)=\mathrm{\Theta }\left(RC\left(h_t\right)^{0.922}\right)`$, both of which are the largest such gaps of which we know.

### 6.2 Local Separations

It is a longstanding open question whether the relation $`C\left(f\right)bs\left(f\right)^2`$ due to Nisan  is tight. As a first step, one can ask whether the relations $`C\left(f\right)=O\left(RC\left(f\right)^2\right)`$ and $`RC\left(f\right)=O\left(bs\left(f\right)^2\right)`$ are tight. In this section we introduce a notion of local proof in query complexity, and then show there is no local proof that $`C\left(f\right)=o\left(RC\left(f\right)^2\right)`$ or that $`RC\left(f\right)=o\left(bs\left(f\right)^2\right)`$. This implies that proving either result would require techniques unlike those that are currently known. Our inspiration comes from computational complexity, where researchers first formalized known methods of proof, including relativizable proofs  and natural proofs , and then argued that these methods were not powerful enough to resolve the field’s outstanding problems.

Let $`G\left(f\right)`$ and $`H\left(f\right)`$ be query complexity measures obtained by maximizing over all inputs—that is, $`G\left(f\right)=\mathrm{max}_{XDom\left(f\right)}G^X\left(f\right)`$ and $`H\left(f\right)=\mathrm{max}_{XDom\left(f\right)}H^X\left(f\right)`$. Call $`B\{1,\mathrm{},n\}`$ a minimal block on $`X`$ if $`B`$ is sensitive on $`X`$ (meaning $`f\left(X^{\left(B\right)}\right)f\left(X\right)`$), and no sub-block $`B^{}B`$ is sensitive on $`X`$. Also, let $`X`$’s neighborhood $`𝒩\left(X\right)`$ consist of $`X`$ together with $`X^{\left(B\right)}`$ for every minimal block $`B`$ of $`X`$. Consider a proof that $`G\left(f\right)=O\left(t\left(H\left(f\right)\right)\right)`$ for some nondecreasing $`t`$. We call the proof local if it proceeds by showing that for every $`XDom\left(f\right)`$,

$$G^X\left(f\right)=O\left(\underset{Y𝒩\left(X\right)}{\mathrm{max}}\left\{t\left(H^Y\left(f\right)\right)\right\}\right).$$

As a canonical example, Nisan’s proof  that $`C\left(f\right)bs\left(f\right)^2`$ is local. For each $`X`$, Nisan observes that (i) a maximal set of disjoint minimal blocks is a certificate for $`X`$, (ii) such a set can contain at most $`bs^X\left(f\right)`$ blocks, and (iii) each block can have size at most $`\mathrm{max}_{Y𝒩\left(X\right)}bs^Y\left(f\right)`$. Another example of a local proof is our proof in Section 4 that $`RC\left(f\right)=O\left(QC\left(f\right)^2\right)`$.

###### Proposition 13

There is no local proof that $`C\left(f\right)=o\left(RC\left(f\right)^2\right)`$ or that $`RC\left(f\right)=o\left(bs\left(f\right)^2\right)`$ for total $`f`$.

Proof. The first part is easy: let $`f\left(X\right)=1`$ if $`\left|X\right|\sqrt{n}`$ (where $`\left|X\right|`$ denotes the Hamming weight of $`X`$), and $`f\left(X\right)=0`$ otherwise. Consider the all-zero input $`0^n`$. We have $`C^{0^n}\left(f\right)=n\sqrt{n}+1`$, but $`RC^{0^n}\left(f\right)=O\left(\sqrt{n}\right)`$, and indeed $`RC^Y\left(f\right)=O\left(\sqrt{n}\right)`$ for all $`Y𝒩\left(0^n\right)`$.

For the second part, arrange the input variables in a lattice of size $`\sqrt{n}\times \sqrt{n}`$. Take $`m=\mathrm{\Theta }\left(n^{1/3}\right)`$, and let $`g\left(X\right)`$ be the monotone Boolean function that outputs $`1`$ if and only if $`X`$ contains a $`1`$-square of size $`m\times m`$. This is a square of $`1`$’s that can wrap around the edges of the lattice; note that only the variables along the sides must be set to $`1`$, not those in the interior. An example input, with a $`1`$-square of size $`3\times 3`$, is shown below.

$$\begin{array}{ccccc}0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 1\\ 1& 0& 0& 1& 0\\ 1& 0& 0& 1& 1\end{array}$$

Clearly $`bs^{0^n}\left(g\right)=\mathrm{\Theta }\left(n^{1/3}\right)`$, since there can be at most $`n/m^2`$ disjoint $`1`$-squares of size $`m\times m`$. Also, $`bs^Y\left(g\right)=\mathrm{\Theta }\left(n^{1/3}\right)`$ for any $`Y`$ that is $`0`$ except for a single $`1`$-square. On the other hand, if we choose uniformly at random among all such $`Y`$’s, then at any lattice site $`i`$, $`\mathrm{Pr}_Y\left[y_i=1\right]=\mathrm{\Theta }\left(n^{2/3}\right)`$. Hence $`RC^{0^n}\left(g\right)=\mathrm{\Omega }\left(n^{2/3}\right)`$.

### 6.3 Symmetric Partial Functions

If $`f`$ is partial, then $`QC\left(f\right)`$ can be much smaller than $`Q_2\left(f\right)`$. This is strikingly illustrated by the collision problem: let $`Y=(y_1,\mathrm{},y_n)`$ be a sequence of integers in the range $`\{1,\mathrm{},n^2\}`$, each of which can be retrieved by a single query. Let $`Col\left(Y\right)=0`$ if $`Y`$ is one-to-one (each $`y_i`$ is unique), and $`Col\left(Y\right)=1`$ if $`Y`$ is two-to-one (each $`y_i`$ appears exactly twice), under the promise that one of these is the case. Then $`RC\left(Col\right)=QC\left(Col\right)=O\left(1\right)`$, since every one-to-one input differs from every two-to-one input on at least $`n/2`$ of the $`y_i`$’s. On the other hand, Aaronson  showed that $`Q_2\left(Col\right)=\mathrm{\Omega }\left(n^{1/5}\right)`$, and Shi  improved this to $`\mathrm{\Omega }\left(n^{1/3}\right)`$, which is tight .

From the example of the collision problem, it is tempting to conjecture that (say) $`Q_2\left(f\right)=O\left(n^{1/3}\right)`$ whenever $`QC\left(f\right)=O\left(1\right)`$—that is, ‘if every $`0`$-input is far from every $`1`$-input, then the quantum query complexity is sublinear.’ Here we disprove this conjecture, even for the special case of symmetric functions such as $`Col`$. (For a finite set $``$, we say that $`f:^n\{0,1\}`$ is symmetric if $`y_1\mathrm{}y_nDom\left(f\right)`$ implies $`y_{\sigma \left(1\right)}\mathrm{}y_{\sigma \left(n\right)}Dom\left(f\right)`$ and $`f\left(y_1\mathrm{}x_n\right)=f\left(y_{\sigma \left(1\right)}\mathrm{}y_{\sigma \left(n\right)}\right)`$ for every permutation $`\sigma `$.)

Our proof uses the following lemma, due to Nisan and Wigderson .

###### Lemma 14 (Nisan-Wigderson)

For any $`\gamma >1`$, there exists a family of sets

$$S_1,\mathrm{},S_m\{1,\mathrm{},\gamma n\}$$

such that $`m=\mathrm{\Omega }\left(2^{n/\gamma }\right)`$, $`\left|S_i\right|=n`$ for all $`i`$, and $`\left|S_iS_j\right|n/\gamma `$ for all $`ij`$.

We will also need to adapt a lemma of Ambainis . For $`Z\{0,1\}^N`$, say that a multivariate polynomial $`p\left(Z\right)`$ approximates $`g\left(Z\right)`$ if (i) $`p\left(Z\right)[0,1]`$ for every input $`Z`$ (not merely those in $`Dom\left(f\right)`$), and (ii) $`\left|p\left(Z\right)g\left(Z\right)\right|1/3`$ for every $`ZDom\left(f\right)`$. Also, let $`\mathrm{\Delta }(N,d)=_{i=0}^d\left(\genfrac{}{}{0pt}{}{N}{i}\right)`$.

###### Lemma 15 (Ambainis)

At most $`2^{O\left(\mathrm{\Delta }(N,d)dN^2\right)}`$ distinct Boolean functions (partial or total) can be approximated by polynomials of degree $`d`$.

We can now prove the main result.

###### Theorem 16

There exists a symmetric partial $`f`$ for which $`QC\left(f\right)=O\left(1\right)`$ and $`Q_2\left(f\right)=\mathrm{\Omega }\left(n/\mathrm{log}n\right)`$.

Proof. Let $`f:^n\{0,1\}`$ where $`=\{1,\mathrm{},3n\}`$, and let $`m=\mathrm{\Omega }\left(2^{n/3}\right)`$. Let $`S_1,\mathrm{},S_m`$ be as in Lemma 14. We put $`(y_1,\mathrm{},y_n)`$ in $`Dom\left(f\right)`$ if and only if $`\{y_1,\mathrm{},y_n\}=S_j`$ for some $`j`$. Clearly $`QC\left(f\right)=O\left(1\right)`$, since if $`ij`$ then every permutation of $`S_i`$ differs from every permutation of $`S_j`$ on at least $`n/3`$ indices.

The number of symmetric $`f`$ with $`Dom\left(f\right)`$ as above is $`2^m=2^{\mathrm{\Omega }\left(2^{n/3}\right)}`$. We can convert any such $`f`$ to a Boolean function $`g`$ on $`O\left(n\mathrm{log}n\right)`$ variables. But Beals et al.  showed that, if $`Q_2\left(g\right)=T`$, then $`g`$ is approximated by a polynomial of degree at most $`2T`$. So by Lemma 15, if $`Q_2\left(g\right)T`$ for every $`g`$ then

$$2T\mathrm{\Delta }(n\mathrm{log}n,2T)\left(n\mathrm{log}n\right)^2=\mathrm{\Omega }\left(2^{n/3}\right)$$

and we solve to obtain $`T=\mathrm{\Omega }\left(n/\mathrm{log}n\right)`$.

## 7 Open Problems

Is $`\stackrel{~}{\mathrm{deg}}\left(f\right)=\mathrm{\Omega }\left(\sqrt{RC\left(f\right)}\right)`$, where $`\stackrel{~}{\mathrm{deg}}\left(f\right)`$ is the minimum degree of a polynomial approximating $`f`$? In other words, can one lower-bound $`QC\left(f\right)`$ using the polynomial method of Beals et al. , rather than the adversary method of Ambainis ?

Also, is $`R_2\left(f\right)=O\left(RC\left(f\right)^2\right)`$? If so we obtain the new relation $`R_2\left(f\right)=O\left(Q_2\left(f\right)^4\right)`$.

## 8 Acknowledgments

I thank Ronald de Wolf for comments on the manuscript and for pointing out that $`Q_E\left(f\right)`$ can be replaced by $`Q_0\left(f\right)`$ in Theorem 11; and Umesh Vazirani and Ashwin Nayak for helpful discussions.