Stanford University, USA{paulliu<EMAIL_ADDRESS>Paul Liu and Jan
Vondrak 2nd Symposium on Simplicity in Algorithms (SOSA 2019) SOSA 2019 SOSA
2019 San Diego, United States

# Submodular Optimization in the MapReduce Model

Paul Liu and Jan Vondrak

###### Abstract.

Submodular optimization has received significant attention in both practice
and theory, as a wide array of problems in machine learning, auction theory,
and combinatorial optimization have submodular structure. In practice, these
problems often involve large amounts of data, and must be solved in a
distributed way. One popular framework for running such distributed algorithms
is MapReduce. In this paper, we present two simple algorithms for cardinality
constrained submodular optimization in the MapReduce model: the first is a
$(1/2-o(1))$-approximation in 2 MapReduce rounds, and the second is a
$(1-1/e-\epsilon)$-approximation in $\frac{1+o(1)}{\epsilon}$ MapReduce
rounds.

###### Key words and phrases:

mapreduce, submodular, optimization, approximation algorithms

###### 1991 Mathematics Subject Classification:

Theory of computation $\rightarrow$ MapReduce algorithms; Distributed
computing models; Algorithm design techniques; Submodular optimization and
polymatroids

##  1\. Introduction

Let $f:2^{V}\rightarrow\mathbb{R}^{+}$ be a function satisfying
$f(A\cup\\{e\\})-f(A)\geq f(B\cup\\{e\\})-f(B)$ for all $A\subseteq B$ and
$e\notin B$. Such a function is called _submodular_. When $f$ satisfies the
additional property $f(A\cup\\{e\\})-f(A)\geq 0$ for all $A$ and $e\notin A$,
we say $f$ is _monotone_.

Many combinatorial optimization problems can be cast as submodular
optimization problems. Such problems include classics such as max cut, min
cut, maximum coverage, and minimum spanning tree [3]. Although submodular
optimization encompasses several NP-Hard problems, well-known greedy
approximation algorithms are known [8]. We focus on the special case of
monotone submodular maximization under a cardinality constraint $k$, i.e.

$OPT:=\max_{S\subseteq V,|S|\leq k}f(S),\,\textrm{$f$ is monotone}.$

In particular, it is known that one can approximate a cardinality constrained
monotone submodular maximization problem to a factor of $1-1/e$ of optimal.

Due to rapidly growing datasets, recent focus has been on submodular
optimization in distributed models. In this work, we focus on the MapReduce
model, where complexity is measured as the number of synchronous communication
rounds between the machines involved. The current state of the art for
cardinality constrained submodular maximization is the algorithm of Barbosa et
al. [2], which achieves a $1/2-\epsilon$ approximation in 2 rounds and was the
first to achieve a $1-1/e-\epsilon$ approximation in
$O\left(\frac{1}{\epsilon}\right)$ rounds. Both algorithms actually require
significant duplication of the ground set (each element being sent to
$\Omega(\frac{1}{\epsilon})$ machines). Since this might be an issue in
practice, [2] mentions that without duplication, the two algorithms could be
implemented in $O(\frac{1}{\epsilon}\log\frac{1}{\epsilon})$ and
$O(\frac{1}{\epsilon^{2}})$ rounds, respectively. Earlier, Mirrokni and
Zadimoghaddam [7] gave a $0.27$-approximation in 2 rounds without duplication
and a $0.545$-approximation with
$\Theta(\frac{1}{\epsilon}\log\frac{1}{\epsilon})$ duplication.

Our contribution. We focus on the most practical regime of MapReduce
algorithms for cardinality constrained submodular maximization, which is a
small constant number of rounds and no duplication of the dataset. To our
knowledge, the 0.27-approximation of [7] has been the best result in this
regime so far.

We describe a simple thresholding algorithm which achieves the following: In 2
rounds of MapReduce, with one random partitioning of the dataset (no
duplication), we obtain a $(1/2-\epsilon)$-approximation. In 4 rounds, we
obtain a $5/9$-approximation. More generally, in $2t$ rounds, we obtain a
$(1-(1-\frac{1}{t+1})^{t}-\epsilon)$-approximation, which we show to be
optimal for this type of algorithm. Crucially, the parameter $\epsilon$ does
not affect the number of rounds, and only mildly affects the memory (in that
$\epsilon$ can be taken to $\tilde{O}(\sqrt{k/n})$ without asymptotically
increasing the memory).

Our algorithm is inspired by the work of Kumar et al. [5] and McGregor-Vu [6]
in the streaming setting. It is also similar to a recent algorithm of Assadi-
Khanna [1], who study the communication complexity of the maximum coverage
problem. As such, our algorithm is not particularly novel, but we believe that
our analysis of its performance in the MapReduce model is, thus simplifying
and improving the previous work of [2] and [7].

Open question. The most intriguing remaining question in our opinion (for the
cardinality constrained submodular problem) is whether $\Theta(1/\epsilon)$
rounds are necessary to achieve a $(1-1/e-\epsilon)$-approximation. So far
there is no evidence that a $(1-1/e)$-approximation in a constant number of
rounds is impossible.

###  1.1. The MapReduce Model

There are many variants of MapReduce models, and algorithms between the
different models are largely transferable. We use a variant of the
$\mathcal{MRC}$ model of Karloff et al. [4]. In this model, an input of size
$N$ is distributed across $O(N^{\delta})$ machines, each with
$O(N^{1-\delta})$ memory. We relax the model slightly, and allow one central
machine to have memory slightly expanded to $\tilde{O}(N^{1-\delta})$.

Computation then proceeds in a sequence of synchronous communication rounds.
In each round, each machine receives an input of size $O(N^{1-\delta})$. Each
machine then performs computations on that input, and produces output messages
which are delivered to other machines (specified in the message) as input at
the start of the next round. The total size of these output messages must also
be $O(N^{1-\delta})$ per machine. We refer the reader to the work of Karloff
et al. [4] for additional details.

In our applications, we assume the input is a set of elements $V$ and a
cardinality parameter $k$. Each machine has an oracle that allows it to
evaluate $f$. Under these constraints, we assume that each machine has memory
$O(\sqrt{nk})$ (except for a single ‘central’ machine with $O(\sqrt{nk}\log
k)$ memory) and that there are $\sqrt{n/k}$ machines in total.

##  2\. A thresholding algorithm for submodular maximization

In the following algorithms, let $f:2^{V}\rightarrow\mathbb{R}^{+}$ be a
monotone submodular function, $n=|V|$, and $f_{S}(e)=f(S\cup\\{e\\})-f(S)$. We
refer to $f_{S}(e)$ as the _marginal_ of $e$ with respect to $S$. Let $k$ be
the maximum cardinality of the solution, and $m=\sqrt{n/k}$ be the number of
machines.

###  2.1. A $1/2-o(1)$ approximation in 2 rounds

First, we present a simple 1/2-approximation in 2 rounds, assuming we know the
exact value of $OPT$. We will relax this assumption later. The algorithm
requires two helper functions ThresholdGreedy and ThresholdFilter, which forms
the basis of all of our algorithms. Roughly speaking, ThresholdGreedy greedily
adds to a set of elements while there exists an element of high marginal in
the input set. ThresholdFilter filters elements of low marginal out of the
input set.

Input: An input set $S$, a partial greedy solution $G$ with $|G|\leq k$, and a
threshold $\tau$.

Output: A set $G^{\prime}\supseteq G$ such that $f_{G^{\prime}}(e)<\tau$ for
all $e\in S$ if $|G|<k$ or $f(G)\geq\tau k$.

$G^{\prime}\leftarrow G$

for  _$e\in S$_ do

if  _$f_{G^{\prime}}(e)\geq\tau$ and $|G^{\prime}|<k$_ then
$G^{\prime}\leftarrow G^{\prime}\cup\\{e\\}$

return _$G^{\prime}$_

Algorithm 1 ThresholdGreedy$(S,G,\tau)$

Input: An input set $S$, a partial greedy solution $G$, and a threshold
$\tau$.

Output: A set $S^{\prime}\subseteq S$ such that $f_{G}(e)\geq\tau$ for all
$e\in S^{\prime}$.

$S^{\prime}\leftarrow S$

for  _$e\in S$_ do

if  _$f_{G}(e) <\tau$_ then $S^{\prime}\leftarrow S^{\prime}\setminus\\{e\\}$

return _$S^{\prime}$_

Algorithm 2 ThresholdFilter$(S,G,\tau)$

We define an additional function PartitionAndSample which simply initializes
all of our algorithms by partitioning the input set randomly and drawing a
random sample from it.

$S\leftarrow\textrm{sample each $e\in V$ with probability $p=4\sqrt{k/n}$}$

partition $V$ randomly into sets $V_{1},V_{2},\ldots V_{m}$ to the $m$
machines (one set per machine)

send $S$ to each machine and a central machine $C$

Algorithm 3 PartitionAndSample$(V)$

Using these three helper algorithms, our approximation algorithm is quite easy
to implement, and can be found in Algorithm 4.

round 1:

$S,V_{1},\ldots,V_{m}\leftarrow\textsc{PartitionAndSample}(V)$111Note that $S$
and the $V_{i}$ are not stored on one machine by PartitionAndSample. We simply
use the assignment to denote that the variables have been initialized and sent
to their respective machines.

on  _each machine $M_{i}$ (in parallel)_ do

$\tau\leftarrow\frac{OPT}{2k}$

$G_{0}\leftarrow\textsc{ThresholdGreedy}\left(S,\emptyset,\tau\right)$

if  _$|G_{0}| <k$_ then
$R_{i}\leftarrow\textsc{ThresholdFilter}\left(V_{i},G_{0},\tau\right)$

else $R_{i}\leftarrow\emptyset$

send $R_{i}$ to a central machine $C$

round 2 (only on $C$):

compute $G_{0}$ from $S$ as in first round

$G\leftarrow\textsc{ThresholdGreedy}\left(\cup_{i}R_{i},G_{0},\tau\right)$

return _$G$_

Algorithm 4 A simple 2-round 1/2 approximation, assuming $OPT$ is known.

######  Lemma 2.1.

The approximation ratio of Algorithm 4 is at least $1/2$.

######  Proof 2.2.

The following lemma is folklore, but we present it for completeness.

First, we note that $G_{0}$ is the same on each machine so long as the loop
iterating through $S$ is done in a fixed order. We assume that this is the
case. From this, it is clear that Algorithm 4 returns a set $G$ for which
$f_{G}(e)<\frac{OPT}{2k}$ for any $e\in V$.

Let $G$ be the set returned at the end of the algorithm. Either $|G|=k$, or
there is no $e\in V$ for which the marginal with respect to $G$ is greater
than $OPT/2$. In the former case, we have $k$ elements of value at least
$\frac{OPT}{2k}$ so we are done. In the latter case, let $O$ be the optimal
solution. By monotonicity and submodularity,

$OPT=f(O)\leq f(O\cup G)\leq f(G)+\sum_{e\in O\setminus G}f_{G}(e)\leq
f(G)+k\cdot\frac{OPT}{2k}.$

Lemma 2.1 shows that the algorithm is correct. Each machine in round 1 clearly
uses $O(\sqrt{nk})$ memory. It remains to bound the memory of the central
machine in round 2.

######  Lemma 2.3.

With probability $1-e^{-\Omega(k)}$, the number of elements sent to the
central machine $C$ has cardinality at most $\sqrt{nk}$.

######  Proof 2.4.

The expected number of elements in $S$ is $4\sqrt{nk}$. By a Chernoff bound
(Theorem B.1) the probability that $|S|<3\sqrt{nk}$ is at most
$e^{-\Omega(\sqrt{nk})}\leq e^{-\Omega(k)}$. So we can assume that $|S|\geq
3\sqrt{nk}$. Let $N_{S}$ denote the number of elements of marginal at least
$OPT/(2k)$ with respect to $G_{0}$. The number of elements sent to $C$ in
round two is exactly $N_{S}+|S|$.

Consider breaking the sample set $S$ into $3k$ blocks of size $\sqrt{n/k}$ and
processing each block sequentially. If before each block, there are at least
$\sqrt{nk}$ remaining elements of marginal value at least $OPT/(2k)$, we have
probability at least
$1-\left(1-\sqrt{\frac{k}{n}}\right)^{\sqrt{\frac{n}{k}}}>1/2$ of adding an
additional element to $G_{0}$. This happens conditioned on any prior history
of the algorithm, since we can imagine that the blocks are sampled
independently one at a time. Therefore, we can use a martingale argument to
bound the number of elements selected in $S$. If $X_{i}$ is the indicator
random variable for the event that at least one element is selected from the
$i$-th block, then we have $E[X_{i}\mid X_{1},\ldots,X_{i-1}]\geq 1/2$. Hence
we can define $Y_{i}=\sum_{j=1}^{i}(X_{i}-1/2)$ and the sequence
$Y_{1},Y_{2},\ldots$ is a submartingale, which means $E[Y_{i}\mid
Y_{1},\ldots,Y_{i-1}]\geq Y_{i-1}$. Moreover, $|Y_{i}-Y_{i-1}|\leq 1$. By
Azuma’s inequality (Theorem B.2), $\Pr[Y_{3k}<-\frac{1}{2}k]<e^{-\Omega(k)}$.
This means that with probability $1-e^{-\Omega(k)}$,
$\sum_{j=1}^{3k}X_{j}=Y_{3k}+\frac{3}{2}k\geq k$, and we include at least $k$
elements overall. In that case, we are done and do not send anything to the
central machine. Otherwise, the number of remaining elements of marginal value
at least $OPT/(2k)$ drops below $\sqrt{nk}$.

Remaining issues. Since we do not know the exact value of $OPT$, we will need
to guess the value within a factor of $\epsilon$ without increasing the number
of rounds. This will increase memory usage on the central machine by a factor
of $\frac{1}{\epsilon}\log k$. To do this, we classify the inputs into two
classes: when a the input contains more than $\sqrt{nk}$ elements of value at
least $\frac{OPT}{2k}$, and when there are less than $\sqrt{nk}$ such
elements. We call the former class of inputs “dense” and the latter class
“sparse”. For each input class, we design a 1/2-approximation in 2 rounds.
Given the input, we can run both in parallel and return the better of the two
solutions: each machine simply runs both algorithms at the same time, keeping
the number of machines the same. The full analysis is given in the Appendix,
but we outline the algorithms below.

#### A 2-round algorithm for “dense” inputs

Let $v$ be the maximum value of a single element of the random sample $S$ in
Algorithm 4. When the input is dense, $v$ is likely to be at least
$\frac{OPT}{2k}$ and at most $OPT$. A straightforward analysis shows that
$\tau_{j}:=v(1+\epsilon)^{j}$ is within a $(1+\epsilon)$ multiplicative factor
of $OPT/2$ for some $j\in\\{1,\ldots,\frac{1}{\epsilon}\log k\\}$. Running
Algorithm 4 with $\tau_{j}$ instead of $OPT/2$ produces an approximation of
value at least $\frac{OPT}{2(1+\epsilon)}>\frac{OPT}{2}(1-\epsilon)$. Thus if
each machine runs $\frac{1}{\epsilon}\log k$ copies of Algorithm 4, the best
solution must have value at least $\frac{OPT}{2}(1-\epsilon)$.

#### A 2-round algorithm for “sparse” inputs

Call an element $e$ “large” if $f(e)\geq\frac{OPT}{2k}$. The algorithm simply
sends all the large elements of the input onto one machine and then runs a
sequential algorithm in the second round. To get all the large elements onto
one machine, we randomly partition the input set onto the $m$ machines, and
then send the $O(k)$ largest elements on each machine to the central machine.
On the central machine, we can run the same thresholding procedure as in the
“dense” case to find a threshold close to $OPT/(2k)$. We then run a sequential
version of Algorithm 4.

In both the algorithms, $\epsilon$ can be taken to $\tilde{O}(\sqrt{k/n})$
without asymptotically increasing the memory, so we have a
$(1/2-o(1)$-approximation.

###  2.2. A $1-\left(1-\frac{1}{t+1}\right)^{t}$ approximation in $2t$ rounds

Here we show how our algorithm extends to $t$ thresholds. The number of
MapReduce rounds becomes $2t+2$. This can be reduced to $2t$ using tricks
similar to Section 2.1, but we omit this here. The approximation factor with
$t$ thresholds is $1-(1-\frac{1}{t+1})^{t}$, which converges to $1-1/e$. We
note that we need $\Theta(1/\epsilon)$ rounds to obtain a
$(1-1/e-\epsilon)$-approximation, similar to Barbosa et al. [2], but in
contrast we do not need any duplication of the ground set. Barbosa et al. does
not specify the constant factor in $\Theta(1/\epsilon)$ but it seems that our
dependence is better; a calculation yields that we need $(1+o(1))/\epsilon$
rounds to get a $(1-1/e-\epsilon)$-approximation.

For now, we assume (as in Algorithm 4) that we know the exact value of $OPT$.
We deal with this assumption later. In a nutshell our algorithm works just
like Algorithm 1 but with multiple thresholds used in a sequence. We set the
threshold values as follows:

$\alpha_{\ell}=\left(1-\frac{1}{t+1}\right)^{\ell}\frac{OPT}{k}$

for $1\leq\ell\leq t$. (Note that for $t=1$, we get
$\alpha_{1}=\frac{OPT}{2k}$ as in Algorithm 1.) For each threshold, we first
select elements above the threshold from a random sample set, and then use
this partial solution to prune the remaining elements. Finally, the solution
at this threshold is completed on a central machine, and we proceed to the
next threshold. The full description of the algorithm is presented in
Algorithm 5. The analysis is as follows.

######  Lemma 2.5.

The approximation ratio of Algorithm 5 is at least
$1-\left(1-\frac{1}{t+1}\right)^{t}$.

######  Proof 2.6.

By induction, we prove the following statement: The value of the first
$\frac{\ell}{t}k$ elements selected by the algorithm is at least
$(1-(1-\frac{1}{t+1})^{\ell})OPT$. (If $\frac{\ell}{t}k$ is not an integer, we
count the marginal value of the $\lceil\frac{\ell}{k}k\rceil$-th selected
element weighted by its respective fraction.)

Clearly this is true for $\ell=0$. Assume that the claim is true for $\ell-1$.
We consider two cases.

Either all the elements among the first $\lceil\frac{\ell}{t}k\rceil$ are
selected above the $\alpha_{\ell}$ threshold. This means that since the value
of the first $\frac{\ell-1}{t}k$ elements was at least
$(1-(1-\frac{1}{t+1})^{\ell-1})OPT$, and the marginal value of each additional
element is at least $\alpha_{\ell}$, the total value of the first
$\frac{\ell}{k}OPT$ (with fractional elements counted appropriately) is at
least

$\left(1-\left(1-\frac{1}{t+1}\right)^{\ell-1}\right)OPT+\frac{1}{t}\cdot\left(1-\frac{1}{t+1}\right)^{\ell}OPT=\left(1-\left(1-\frac{1}{t+1}\right)^{\ell}\right)OPT.$

The other case is that not all these elements are selected above the
$\alpha_{\ell}$ threshold, which means that if we denote by $S_{\ell}$ the set
of the first $\lfloor\frac{\ell}{t}k\rfloor$ selected elements, then there are
no elements with marginal value more than $\alpha_{\ell}$ with respect to
$S_{\ell}$. But then for the optimal solution $O$, we get

$OPT-f(S_{\ell})\leq f_{S_{\ell}}(O)\leq
k\alpha_{\ell}=\left(1-\frac{1}{t+1}\right)^{\ell}OPT$

which means that $f(S_{\ell})\geq(1-(1-\frac{1}{t+1})^{\ell})OPT.$

For $\ell=t$, we obtain the statement of the lemma.

The probabilistic analysis of the number of pruned elements that need to be
sent to the central machine is exactly the same as in Section 2.1. The
requirement of knowing $OPT$ can be also handled in the same way — we can use
an extra initial round to determine the maximum-value element on the input,
which gives us an estimate of the optimum within a factor of $k$. Then we can
try $O(\frac{1}{\epsilon}\log k)$ different estimates of $OPT$ to ensure that
one of them is within a relative error of $1+\epsilon$ of the correct value.
Finally, we use an extra final round to choose the best of the solutions that
we found for different estimates of $OPT$. Alternatively, we can use
additional tricks as in Section 2.1 to eliminate these 2 extra rounds, but we
omit the details here.

$G\leftarrow\emptyset$

for  _$\ell=1,\ldots\,t$_ do

round $2\ell-1$:

$S,V_{1},\ldots,V_{m}\leftarrow\textsc{PartitionAndSample}(V)$

on  _each machine $M_{i}$ (in parallel)_ do

$G_{0}\leftarrow\textsc{ThresholdGreedy}\left(S,G,\alpha_{\ell}\right)$

if  _$|G_{0}| <k$_ then
$R_{i}\leftarrow\textsc{ThresholdFilter}\left(V_{i},G_{0},\alpha_{\ell}\right)$

else $R_{i}\leftarrow\emptyset$

send $R_{i}$ to a central machine $C$

round $2\ell$ (only on $C$):

compute $G_{0}$ from $S$ as in first round

$G\leftarrow\textsc{ThresholdGreedy}\left(\cup_{i}R_{i},G_{0},\alpha_{\ell}\right)$

return _$G$_

Algorithm 5 A $2t$-round $1-\left(\frac{t}{t+1}\right)^{t}$ approximation,
assuming $OPT$ is known.

##  3\. Optimality of our choice of thresholds

Here we present a proof that there is no way to modify the thresholding
algorithm and achieve a better approximation factor with a different choice of
thresholds.

######  Theorem 3.1.

The thresholding algorithm with $t$ thresholds cannot achieve a factor better
than $1-\left(1-\frac{1}{t+1}\right)^{t}$.

######  Proof 3.2.

Assume that the optimum $O$ consists of $k$ elements of total value $kv^{*}$.
Since we are proving a hardness result, we can assume that the algorithm has
this information and we can even let it choose $v^{*}$; in the following, we
denote this choice $v^{*}=\alpha_{0}$. In addition, the algorithm chooses
thresholds $\alpha_{1}\geq\alpha_{2}\geq\ldots\geq\alpha_{t}$. It might be the
case that $\alpha_{0}<\alpha_{1}$, but then we can ignore all the thresholds
above $\alpha_{0}$ and design our hard instance based on the thresholds below
$\alpha_{0}$, which would reduce to a case with fewer thresholds. Thus we can
assume $\alpha_{0}\geq\alpha_{1}\geq\ldots\geq\alpha_{t}$.

We design an adversarial instance as follows. In addition to the $k$ elements
of value $v^{*}$, we have a set $S$ of other elements where element $i$ has
value $v_{i}$, such that $\sum_{i\in S}v_{i}\leq kv^{*}$. The objective
function is defined as follows: for $O^{\prime}\subseteq O$ and
$S^{\prime}\subseteq S$,

$f(S^{\prime}\cup O^{\prime})=\sum_{i\in
S^{\prime}}v_{i}+\left(1-\frac{\sum_{i\in
S^{\prime}}v_{i}}{kv^{*}}\right)|O^{\prime}|v^{*}.$

It is easy to verify that this is a monotone submodular function. (It can be
realized as a coverage function, which we leave as an exercise.)

Now we specify more precisely the values of elements in $S$. We will have
$n_{\ell}$ elements of value $\alpha_{\ell}$, for each $1\leq\ell\leq t$. The
idea is that the algorithm will pick these $n_{\ell}$ elements at threshold
value $\alpha_{\ell}$, at which point the marginal value of the optimal
elements drops below $\alpha_{\ell}$, so we have to move on to the next
threshold. A computation yields that we should have
$n_{\ell}=(\frac{\alpha_{\ell-1}}{\alpha_{\ell}}-1)k$.222We ignore the issue
that $n_{\ell}$ might not be an integer. For large $k$, it is easy to see that
the rounding errors are negligible. The total value of these elements is
$\sum_{i\in
S}v_{i}=\sum_{\ell=1}^{t}n_{\ell}\alpha_{\ell}=\sum_{\ell=1}^{t}(\alpha_{\ell}-\alpha_{\ell-1})k=(\alpha_{0}-\alpha_{t})k\leq
v^{*}k$ as required above.

Then, assuming that the marginal value of the optimum after processing
$\ell-1$ thresholds was $\alpha_{\ell-1}k$, the marginal value after
processing the $\ell$-th threshold will be
$\alpha_{\ell-1}k-n_{\ell}\alpha_{\ell}=\alpha_{\ell}k$. By induction, the
algorithm selects exactly $n_{\ell}$ elements of value $\alpha_{\ell}$, unless
the constraint of $k$ selected elements is reached. Let us denote by
$n^{\prime}_{\ell}$ the actual number of elements selected by the algorithm at
threshold level $\alpha_{\ell}$. We have $n^{\prime}_{\ell}\leq n_{\ell}$, and
$\sum_{\ell=1}^{t}n^{\prime}_{\ell}\leq k$, as discussed above.

The total value collected by the algorithm is
$\sum_{\ell=1}^{t}n^{\prime}_{\ell}\alpha_{\ell}$. Since we have
$n^{\prime}_{\ell}\leq n_{\ell}=(\frac{\alpha_{\ell-1}}{\alpha_{\ell}}-1)k$,
and $\alpha_{\ell}\leq\alpha_{\ell-1}$, we can define inductively
$\alpha^{\prime}_{0}=\alpha_{0}$ and $\alpha^{\prime}_{\ell}\geq\alpha_{\ell}$
such that
$n^{\prime}_{\ell}=(\frac{\alpha^{\prime}_{\ell-1}}{\alpha^{\prime}_{\ell}}-1)k$.
Then the total value collected by the algorithm is

$\sum_{\ell=1}^{t}n^{\prime}_{\ell}\alpha_{\ell}\leq\sum_{\ell=1}^{t}n^{\prime}_{\ell}\alpha^{\prime}_{\ell}=\sum_{\ell=1}^{t}(\alpha^{\prime}_{\ell-1}-\alpha^{\prime}_{\ell})k=(\alpha^{\prime}_{0}-\alpha^{\prime}_{t})k.$

Let us denote
$\beta^{\prime}_{\ell}=\frac{\alpha^{\prime}_{\ell-1}}{\alpha^{\prime}_{\ell}}$.
We have
$\sum_{\ell=1}^{t}(\beta^{\prime}_{\ell}-1)=\frac{1}{k}\sum_{\ell=1}^{t}n^{\prime}_{\ell}\leq
1$, hence $\sum_{\ell=1}^{t}\beta^{\prime}_{\ell}\leq t+1$. Recall that the
value achieved by the algorithm is
$\sum_{\ell=1}^{t}n^{\prime}_{\ell}\alpha_{\ell}\leq(\alpha^{\prime}_{0}-\alpha^{\prime}_{t})k=(1-1/\prod_{\ell=1}^{t}\beta^{\prime}_{\ell})v^{*}k$.
By the AMGM inequality, $\prod_{\ell=1}^{t}\beta^{\prime}_{\ell}$ is maximized
subject to $\sum_{\ell=1}^{t}\beta^{\prime}_{\ell}\leq t+1$ when all the
$\beta^{\prime}_{\ell}$ are equal, $\beta^{\prime}_{\ell}=\frac{t+1}{t}$.
Then, the value achieved by the algorithm is
$(1-1/\prod_{\ell=1}^{t}\beta^{\prime}_{\ell})v^{*}k=(1-(\frac{t}{t+1})^{t})OPT$.

## References

  * [1] Sepehr Assadi and Sanjeev Khanna.  Tight bounds on the round complexity of the distributed maximum coverage problem.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2412–2431, 2018.  URL: https://doi.org/10.1137/1.9781611975031.155, doi:10.1137/1.9781611975031.155.
  * [2] Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, and Justin Ward.  A new framework for distributed submodular maximization.  In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016.
  * [3] Satoru Fujishige.  Submodular functions and optimization, volume 58.  Elsevier, 2005.
  * [4] Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii.  A model of computation for MapReduce.  In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938–948, 2010.  doi:10.1137/1.9781611973075.76.
  * [5] Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, and Andrea Vattani.  Fast greedy algorithms in MapReduce and streaming.  TOPC, 2(3):14:1–14:22, 2015.  doi:10.1145/2809814.
  * [6] Andrew McGregor and Hoa T. Vu.  Better streaming algorithms for the maximum coverage problem.  In 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, pages 22:1–22:18, 2017.  URL: https://doi.org/10.4230/LIPIcs.ICDT.2017.22, doi:10.4230/LIPIcs.ICDT.2017.22.
  * [7] Vahab S. Mirrokni and Morteza Zadimoghaddam.  Randomized composable core-sets for distributed submodular maximization.  In ACM Symposium on Theory of Computing (STOC), pages 153–162, 2015\.
  * [8] George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher.  An analysis of approximations for maximizing submodular set functions \- I.  Math. Program., 14(1):265–294, 1978.  URL: https://doi.org/10.1007/BF01588971, doi:10.1007/BF01588971.
  * [9] Martin Raab and Angelika Steger.  “balls into bins” — a simple and tight analysis.  In Michael Luby, José D. P. Rolim, and Maria Serna, editors, Randomization and Approximation Techniques in Computer Science, pages 159–170, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.

##  Appendix A Appendix

In Algorithm 6, we design a 2-round $1/2-\epsilon$ approximation for “dense”
inputs.

round 1:

$S,V_{1},\ldots,V_{m}\leftarrow\textsc{PartitionAndSample}(V)$

on  _each machine $M_{i}$ (in parallel)_ do

$v\leftarrow\max_{e\textrm{ on $M_{i}$}}f(\\{e\\})$

for  _$j=1,\ldots,\frac{1}{\epsilon}\log k$_ do

$\tau_{j}\leftarrow v(1+\epsilon)^{j}/k$

$G_{0,j}\leftarrow\textsc{ThresholdGreedy}\left(S,\emptyset,\tau_{j}\right)$

if  _$|G_{0,j}| <k$_ then
$R_{i,j}\leftarrow\textsc{ThresholdFilter}\left(V_{i},G_{0,j},\tau_{j}\right)$

else $R_{i,j}\leftarrow\emptyset$

send all $R_{i,j}$ to a central machine $C$

round 2 (only on $C$):

compute $v$, $\tau_{j}$, and $G_{0,j}$ from $S$ as in first round

for  _$j=1,\ldots,\frac{1}{\epsilon}\log k$_ do

$G_{j}\leftarrow\textsc{ThresholdGreedy}\left(\cup_{i}R_{i,j},G_{0,j},\tau_{j}\right)$

$G^{\star}=\text{argmax}_{G_{j}}f(G_{j})$

return _$G^{\star}$_

Algorithm 6 A $1/2-\epsilon$ approximation in 2 rounds for “dense” inputs.

######  Lemma A.1.

Algorithm 6 returns a $1/2-\epsilon$ approximation.

######  Proof A.2.

Note that Algorithm 6 essentially runs Algorithm 4 with
$O(\frac{1}{\epsilon}\log k)$ guesses for $OPT/2$. To get a $1/2-\epsilon$
approximation, one of these guesses needs to be within a multiplicative factor
of $1+\epsilon$ from $\frac{OPT}{2k}$. By the denseness assumption on the
input, we know $\frac{OPT}{2k}\leq v\leq OPT$ with high probability. Suppose
we try $j=1,\ldots,\ell$ for some number of thresholds $\ell$. For one of the
$\tau_{j}$’s to be within a multiplicative factor of $1+\epsilon$ from
$\frac{OPT}{2k}$, we require
$\ell\geq\log\left(\frac{OPT}{2kv\log(1+\epsilon)}\right)\geq\frac{1}{\epsilon}$.

######  Lemma A.3.

The number of elements sent to the central machine is
$O\left(\frac{1}{\epsilon}\sqrt{nk}\log k\right)$.

######  Proof A.4.

This follows from Lemma 2.3 and the fact that there are only $\frac{\log
k}{\epsilon}$ thresholds.

Next, we design a 2-round $1/2-\epsilon$ approximation for “sparse” inputs
(Algorithm 7).

round 1:

partition $V$ uniformly at random to the $m$ machines

on  _each machine $M_{i}$_ do

send its $O(k)$ largest elements to a central machine $C$

round 2 (only on $C$):

$S\leftarrow\textrm{all elements sent to $C$}$

$v\leftarrow\max_{e\in S}f(\\{e\\})$

for  _$j=1,\ldots,\frac{1}{\epsilon}\log k$_ do

$\tau_{j}\leftarrow v(1+\epsilon)^{j}/k$

$G_{j}\leftarrow\textsc{ThresholdGreedy}\left(S,\emptyset,\tau_{j}\right)$

$G^{\star}=\text{argmax}_{G_{j}}f(G_{j})$

return _$G^{\star}$_

Algorithm 7 A $1/2-\epsilon$ approximation in 2 rounds for “sparse” inputs.

######  Lemma A.5.

Algorithm 7 gives a $1/2-\epsilon$ approximation.

######  Proof A.6.

There are two things to check: that one of the $\tau_{j}$’s is close to
$OPT/2$, and that the machine $C$ is not missing any of the elements that it
needs.

For the former, its clear that by similar reasoning to Lemma A.1, one of the
$\tau_{j}$’s will be within a $1+\epsilon$ multiplicative factor to $OPT/2$.

For the latter, note that the “sparseness” assumption implies that with high
probability, the $\sqrt{nk}$ large elements will be equally distributed among
the machines, and each machine will get $k$ elements in expectation. Since we
send $O(k)$ elements to the central machine, $C$ will have all the large
elements in $V$ with high probability. This can be shown by a standard balls-
and-bins analysis [9].

Finally, we note that the total memory use on $C$ is $O(\sqrt{nk})$ since each
machine sends $O(k)$ elements and there are $O(\sqrt{\frac{n}{k}})$ machines
in total.

######  Theorem A.7.

By running Algorithms 6 and 7 in parallel, we have a 2-round $1/2-\epsilon$
approximation.

##  Appendix B Auxiliary Results

######  Theorem B.1 (Chernoff bound).

Let $X_{1},\ldots,X_{n}$ be independent random variables such that
$X_{i}\in[0,1]$ with probability 1. Define $X=\sum_{i=1}^{n}X_{i}$ and let
$\mu=\mathbb{E}X$. Then, for any $\epsilon>0$, we have

$\Pr[X\geq(1+\epsilon)\mu]\leq\exp\left(-\frac{\min\\{\epsilon,\epsilon^{2}\\}\mu}{3}\right).$

######  Theorem B.2 (Azuma’s inequality).

Suppose $X_{1},\ldots,X_{n}$ is a submartingale and $|X_{i}-X_{i+1}|\leq
c_{i}$. Then, we have

$\Pr[X_{n}-X_{0}\leq-t]\leq\exp\left(\frac{-t^{2}}{2\sum_{i}c_{i}^{2}}\right).$


A New Gravitational Action For The Trace Anomaly

Gregory Gabadadze

Center for Cosmology and Particle Physics, Department of Physics

New York University, 726 Broadway, New York, NY, 10003, USA

###### Abstract

The question of building a local diff-invariant effective gravitational action
for the trace anomaly is reconsidered. General Relativity (GR) combined with
the existing action for the trace anomaly is an inconsistent low energy
effective field theory. This issue is addressed by extending GR into a certain
scalar-tensor theory, which preserves the GR trace anomaly equation, up to
higher order corrections. The extension introduces a new mass scale – assumed
to be below the Planck scale – that governs four high dimensional terms in a
local diff-invariant trace anomaly action. Such terms can be kept, while an
infinite number of Planck-suppressed invariants are neglected. The resulting
theory maintains two derivative equations of motion. In a certain
approximation it reduces to the conformal Gallileon, which could have physical
consequences.

##  1 Introduction and summary

General Relativity (GR), combined with a quantum field theory exhibiting the
gravitational trace anomaly [1], and described by its effective action [2, 3],
is an inconsistent field theory, despite the existence of a local diff-
invariant trace anomaly action (see, [4, 5], and discussions below). Such a
theory is strongly coupled at an arbitrarily low energy scale, as was shown in
[6] in a different context. The inconsistency stems from the fact that the
conformal part of a metric is not a propagating degree of freedom in classical
GR111A propagating degree of freedom is defined as a mode with proper
quadratic time derivative and spatial gradient terms in Minkowski space-time,
which is not removable by gauge transformations or by field redefinitions, nor
it is restricted by constraints. The scale factor of the Fridmann-Lemaitre-
Robertson-Walker (FLRW) metric is a conformal mode which has a ghost-like
(”wrong sign”) quadratic time derivative term in the GR action. This ”wrong-
sign” is crucial for FLRW cosmology. However, the scale factor is not a
propagating degree of freedom because its spatial dynamics is constrained
within GR; had it been a propagating mode, it would have led to unsurmountable
instabilities because of its ghost-like quadratic time derivative term. The GR
action supports only two propagating modes, the helicity $\pm 2$ states of a
massless graviton, often referred as the tensor modes.. This issue is fully
relevant to GR coupled to the Standard Model (SM) of particle physics.

One way to avoid the inconsistency is to augment GR so that the conformal mode
turns into a proper propagating degree of freedom, without spoiling
observational consequences of GR, as it is proposed in this work. An
alternative to the augmentation of GR would be to cancel the trace anomaly by
introducing additional low energy degrees of freedom.

As a reminder, one is concerned with the invariance of a quantum field theory
(QFT) – such as the SM – with respect to global scale transformations. At the
classical level the scale invariance could be exact, as in the Maxwell theory,
or it could be violated explicitly, as in a massive scalar theory, or in GR.
The quantum theory violates the scale invariance generically, irrespective of
whether the classical theory is or is not scale invariant. This violation
appears in the trace of a stress-tensor, as it was first shown for gauge
fields [7, 8], and subsequently for a gravitational field [1]. The latter will
be the focus on this work.

It is useful to build a low energy effective action that would incorporate
quantum loops of the matter fields (see, [9] and references therein). The
variation of such a quantum effective action would give rise to the equations
of motion which capture the trace anomaly [2, 3]. These equations could then
be solved in various physical settings, notably in astrophysics and cosmology,
with a benefit that the solutions would automatically contain quantum effects
due to the trace anomaly.

Riegert constructed a local effective action, $S_{A}$, which captures the
trace anomaly in its equations of motion [2] (Efim Fradkin and Tseytlin [3],
built the same action in conformal gravity, practically at the same time [2]).
This construction was done for a particular class of constrained fields, and
hence was regarded by Riegert as breaking diff-invariance.

Komargodski and Schwimmer [4] showed that the same functional, $S_{A}$, but
written in terms of unconstrained fields, gives a diff-invariant trace anomaly
action. This finding placed the Riegert action on a solid footing, which it
lacked for many years. Moreover, ref. [5], showed that the Riegert action
emerges as a local diff-invariant Wess-Zumino term in a coset for a non-
linearly realized conformal symmetry, broken by the scale anomaly.

These findings offer an important perspective: the GR action depends on the
metric $g$ and its derivatives. The metric $g$ can formally be decomposed as
$g=e^{2\sigma}{\bar{g}}$, and GR can be viewed as a theory non-linearly
realizing a Weyl symmetry that shifts $\sigma$ and conformally transforms
$\bar{g}$, keeping $g$ invariant. In GR this is a "spurious" symmetry since
the above split of $g$ is arbitrary, and the $\sigma$ field can be gauged away
by the very same Weyl transformations. However, the Riegert action is a local
diff-invariant functional of $\sigma$ and $\bar{g}$ which is not invariant
under the "spurious" Weyl transformations [4]. Thus, the local diff-invariant
action containing the Einstein-Hilbert and Riegert terms, both written in
terms of $\sigma$ and $\bar{g}$, can be viewed as an action non-linearly
realizing the "spurious" Weyl symmetry [5].

The above arguments, however, suggests that something must be wrong: the field
$\sigma$ was "spurious" in GR, but becomes unremovable once GR is supplemented
by the Riegert action. Indeed, in the GR action the metric field can absorb
the kinetic term of $\sigma$, rendering it in the Riegert action infinitely
strongly coupled at arbitrarily low energies [6] 222Komargodski and Schwimmer
constructed the local diff-invariant Riegert action, and combined it with GR
to prove the a-theorem (for an earlier work using a non-local Riegert action
for the a-theorem, see [10]). They used the metric field for symmetry
bookkeeping, but its dynamics was unimportant for the proof itself; hence the
metric was frozen, and only the conformal mode (a dilaton) was utilized [4].
The issue discussed here does not affect the Komargodski-Schwimmer proof of
the a-theorem, since their construction does not require a dynamical tensor
field [4]. See more comments in Section 4..

One way to resolve this problem is to augment the classical GR action and only
then couple it to a quantum field theory. I will show that the following
action

$\displaystyle S_{R-\bar{R}}=M^{2}\,\int
d^{4}x\sqrt{-g}\,R\,-{\bar{M}}^{2}\,\int
d^{4}x\sqrt{-{\bar{g}}}\,{\bar{R}}\,,$ (1)

with ${\bar{R}}\equiv R(\bar{g})$, $M=M_{\rm Pl}/\sqrt{2}>>{\bar{M}}$, and the
two metric tensors connected as

$\displaystyle g_{\mu\nu}=e^{2\sigma}\,{\bar{g}}_{\mu\nu}\,,$ (2)

gives a viable low energy theory of gravity with a proper propagating
conformal mode, that can be consistently coupled to the Riegert action. The
"spurious" Weyl transformation, $\sigma\to\sigma+\beta(x)$ , $\bar{g}\to
e^{-2\beta(x)}\bar{g}$, with an arbitrary $\beta(x)$, would have made $\sigma$
gauge-removable in GR, however, this is not a symmetry of the second term in
the action (1), and therefore $\sigma$ can’t be gauged away. Furthermore, the
action (1) possesses a global symmetry that neither the first nor the second
term on the r.h.s. separately has (Section 2).

Combining (1) with the results of [2, 3, 4], the total effective action that
captures the GR trace anomaly equation reads as follows:

$\displaystyle S_{eff}=S_{R-\bar{R}}\,+\,S_{A}(\sigma,{\bar{g}})\,,$ (3)

where $S_{A}$ has the form [2, 3, 4]

$\displaystyle S_{A}=a\int
d^{4}x\sqrt{-{\bar{g}}}\left(\sigma{\bar{E}}-4{\bar{G}}^{\mu\nu}{\bar{\nabla}}_{\mu}\sigma{\bar{\nabla}}_{\nu}\sigma-4({\bar{\nabla}}^{2}\sigma)({\bar{\nabla}}\sigma)^{2}-2({\bar{\nabla}}\sigma)^{4}\right)+c\int
d^{4}x\sqrt{-{\bar{g}}}\sigma{\bar{W}}^{2},$ (4)

with the Euler (Gauss-Bonnet) invariant,
${\bar{E}}={\bar{R}}_{\mu\nu\alpha\beta}^{2}-4{\bar{R}}_{\mu\nu}^{2}+{\bar{R}}^{2}$,
and the Weyl tensor squared,
${\bar{W}}^{2}={\bar{R}}_{\mu\nu\alpha\beta}^{2}-2{\bar{R}}_{\mu\nu}^{2}+{\bar{R}}^{2}/3$.
The action (4) emerges as a Wess-Zumino term in a $SO(2,4)/ISO(1,3)$ coset,
which can be recast as a boundary term in 5D [5]; this distinguishes (4) from
other terms in the effective field theory. Note that the terms in $S_{A}$
belong to the general class of the Horndeski theories giving rise to second
order equations of motion [11].

There are an infinite number of additional higher dimensional counter-terms
supplementing (3). All these terms will be suppressed by respective powers of
the scale $M=M_{\rm Pl}/\sqrt{2}$, or of higher scales, such as
$M(M/\bar{M})^{2}$; they will be neglected. At the same time, $S_{A}$ retains
a finite number of terms which are suppressed by $\bar{M}<<M$, or by certain
geometric mean scales such as $(\bar{M}M^{2})^{1/3}$, all of them lower than
$M$.

It is due to the separation of scales between $\bar{M}$ and $M$ that one can
regard (3) as a meaningful low energy action obtained by "integrating out"
quantum loops of a QFT. The coefficients $a$ and $c$ depend on numbers and
representations of the low energy physical degrees of freedom [1]. The very
same degrees of freedom, could also give rise to classical sources for the
gravitational field. Hence the action (3) should be supplemented by the
classical action for the fields representing those low energy degrees of
freedom, but without quantizing those fields further333Not all quantum loops
are proportional to the positive powers of $\hbar$ when massive fields are
involved, some classical effects emerge from such loops [12]. Hence, one might
worry that without considering the quantum loops some classical effects would
be lost. However, keeping the respective classical fields in the effective
action would enable one to retain those classical effects via nonlinear
classical perturbation theory (or via exact classical or numerical
solutions)..

The signature used in this work is "mostly plus", $(-,+++)$. The Ricci tensor
convention is as follows,
$R_{\mu\nu}=\partial_{\alpha}\Gamma^{\alpha}_{\mu\nu}-...$; Riegert, following
Ref. [9], uses the "mostly minus" signature, and the opposite sign for the
curvature tensor. Ref. [4] uses the "mostly minus" signature, the curvature
convention opposite to Riegert’s, and their $\tau$ and $g$ are, respectively,
$-\sigma$ and $\bar{g}$ here. The actions in refs. [2, 3], [4], and in eq. (4)
agree with each other after these different conventions are taken into
consideration.

##  2 The $R-\bar{R}$ theory

Consider the action already quoted in the previous section

$\displaystyle S_{R-\bar{R}}=M^{2}\,\int
d^{4}x\sqrt{-g}\,R\,-{\bar{M}}^{2}\,\int
d^{4}x\sqrt{-{\bar{g}}}\,{\bar{R}}\,,$ (5)

with the two metric tensors, $g$ and $\bar{g}$, related to one another by (2).
At the classical level, the above can be viewed as an action for one metric
field – say, the metric $g$ – and for the scalar $\sigma$, which gets its
proper-sign kinetic term from the $\bar{R}$ term444This would correspond to
the Einstein frame. Section 4 will instead regard this action as a functional
of $\bar{g}$ and $\sigma$, corresponding to the Jordan frame..

Let us consider metric fluctuations above a flat background,
$h_{\mu\nu}=g_{\mu\nu}-\eta_{\mu\nu}$, and decompose them in a standard
fashion according to the representations of the 3D rotation group (these
approximate well fluctuations about an arbitrary nonsingular classical
background at length scales much shorter than the characteristic curvature
radius of the background):

$\displaystyle
h_{00}=2n\,,~{}~{}h_{0j}=v_{j}+\partial_{j}u\,,~{}~{}h_{ij}=t_{ij}+\partial_{i}w_{j}+\partial_{j}w_{i}+2\partial_{i}\partial_{j}\rho-2\delta_{ij}\tau\,,$
(6)

where $i,j=1,2,3$, $v_{j}$ and $w_{j}$ are transverse three-vectors, $t_{ij}$
is a transverse–traceless tensor, and $\tau$ is the conformal mode.
Furthermore, one can choose the gauge, $u=0,\rho=0$. Then, the scalar part of
the action (5) – which decouples from the tensor and vector parts – equals to
the space-time integral of the following expression:

$\displaystyle
2M^{2}\left(-3{\dot{\tau}}^{2}+(\partial_{j}\tau)^{2}-2n\partial_{j}^{2}\tau\right)-2{\bar{M}}^{2}\left(-3({\dot{\tau}}+\dot{\sigma})^{2}+(\partial_{j}(\tau+\sigma))^{2}-2(n+\sigma)\partial_{j}^{2}(\tau+\sigma)\right)\,.$
(7)

If the terms proportional to $\bar{M}^{2}$ were absent, the variation of (7)
w.r.t. $n$ would have given a constraint, $\partial_{j}^{2}\tau=0$, rendering
the conformal mode, $\tau$, non-propagating. This however is no longer the
case in (7): its variation w.r.t. $n$ gives another constraint,
$\partial_{j}^{2}\tau={\epsilon}^{2}{\partial_{j}^{2}\sigma}/(1-{\epsilon}^{2})$,
that relates the conformal mode $\tau$ to the scalar $\sigma$,
$\tau={\epsilon}^{2}\sigma/(1-{\epsilon}^{2})$ (here,
${\epsilon}=\bar{M}/M<<1$, and a zero mode of the Laplacian has been removed
by choosing the appropriate spatial boundary conditions.) Substituting the
latter into (7), one gets

$\displaystyle-\,6M^{2}{(1-{\epsilon}^{2})\over{\epsilon}^{2}}\left(\partial_{\mu}\tau\right)\left(\partial^{\mu}\tau\right)=-\,6{\bar{M}}^{2}{1\over(1-{\epsilon}^{2})}\left(\partial_{\mu}\sigma\right)\left(\partial^{\mu}\sigma\right)\,,$
(8)

which is the kinetic term for the conformal mode with the proper sign. This is
the key feature of the $R-\bar{R}$ theory.

It is convenient to rewrite (5) as follows:

$\displaystyle S_{R-\bar{R}}=\int
d^{4}x\sqrt{-g}\,\left(M^{2}\,R(g)-\Phi^{2}\,R(g)\,-6\,(\nabla\Phi)^{2}\right)\,,$
(9)

where $\Phi\equiv{\bar{M}}e^{-\sigma}$, and the covariant derivative,
$\nabla$, is that of the metric $g$. Owing to the choice of the sign of the
second term on the right hand side of (5), the kinetic term for the scalar
$\Phi$ has the proper sign in (9); this sign will remain the same after
complete diagonalization of the action (9), as shown in Appendix.

The scale $\bar{M}$ enters the action (9) only through the vacuum expectation
value (VEV), $\langle\Phi\rangle=\bar{M}$. Since $\bar{M}<<M$, this VEV is
within the realm of the effective field theory. The last two terms in (9) non-
linearly realize a Weyl symmetry which transforms $g$, and is explicitly
broken by the Einstein-Hilbert term.

It is straightforward to check that the action (9) is invariant w.r.t. the
following transformations of the fields

$\displaystyle{\Phi}\to{\Phi}\,+{\omega\,M\,(1-(\Phi/M)^{2})\over
1+\omega\,\Phi/M},~{}~{}~{}g_{\mu\nu}\to
g_{\mu\nu}\,{(1+\omega\,\Phi/M)^{2}\over 1-\omega^{2}}\,,$ (10)

where $\omega\equiv{\rm tanh}(\lambda)$, with $\lambda$ being an arbitrary
constant555The symmetry transformations (10) may look mysterious, but their
essence is simple: in Appendix it is shown that certain non-linear conformal
transformations of $g$ and $\Phi$, bring the action (9) to that of GR coupled
to a massless scalar field kinetic term, which is invariant w.r.t. the shift
symmetry. The shift transformation, once rewritten in terms of the original
variables, gives (10)..

Furthermore, there exists an invariant combination of the metrics $g$ and
$\bar{g}$

$\displaystyle{\hat{g}}_{\mu\nu}=g_{\mu\nu}-{\epsilon}^{2}\,\bar{g}_{\mu\nu}=g_{\mu\nu}\,\left(1-{\Phi^{2}\over
M^{2}}\right)\,,$ (11)

and if a QFT coupled to $\hat{g}$ in a conventional manner, ${\cal L}_{\rm
SM}=-{1\over
4}\sqrt{-\hat{g}}\,\hat{g}^{\mu\nu}\hat{g}^{\alpha\beta}F_{\mu\alpha}F_{\nu\beta}+\cdots$,
then it will also be invariant. Since one should require,
${\epsilon}\equiv(\bar{M}/M)<<1$, the coupling to the QFT is approximated by
the coupling to the metric $g_{\mu\nu}$. The resulting classical equations
approximate GR, as long as $\bar{M}<<M$ 666 One could consider a different
approach in which QFT fields would couple to $g$, instead of $\hat{g}$, thus
breaking the symmetry (10). This would result in new terms generated in the
effective action due to the QFT loops, notably the mass term for the $\sigma$
field would be induced. The latter would be proportional to some positive
power of the UV scale of the QFT, suppressed by powers of $M$. Furthermore,
$\sigma$ would couple to the stress-tensor in the linearized approximation,
providing a gravity-competing force at distances smaller than inverse mass of
$\sigma$. One would then need to impose a constraint on $\bar{M}$ to suppress
the coupling of $\sigma$ to the stress-tensor. While this is a logical
possibility, it would also lead to the trace anomaly equation being modified
as compared with that of GR (such modifications can be kept small by imposing
constraints on $\bar{M}$). The present work focuses on a scenario where the
symmetry (10) is preserved by the QFT coupling, but can be adopted to the case
when the matter couples to $g$..

The requirement of the invariance under (10) prohibits certain terms to be
added to the action (9). For instance, an additional kinetic term for $\Phi$,
the cosmological constant, $\sqrt{-g}$, the quadratic mass term,
$\sqrt{-g}\Phi^{2}$, and the quartic term, $\sqrt{-g}\Phi^{4}$, don’t respect
the symmetry (10), and are prohibited to enter the action with arbitrary
coefficients. That said, there is a particular combination of the latter three
terms which is invariant under (10)

$\displaystyle\pm\,\Lambda^{4}\sqrt{-g}\,\left(1-{\Phi^{2}\over
M^{2}}\right)^{2}\,,$ (12)

with $\Lambda$ being some arbitrary dimensionful constant. If the above term
is included in the action then both the quadratic and quartic terms for $\Phi$
will be connected to the cosmological constant. The cosmological constant
$\Lambda$ will be tuned to zero (or be vanishingly small as compared to
$\bar{M}$) and this will also nullify the quadratic and quartic terms in (12).

The term in (12) is nothing other than $\pm\Lambda^{4}\sqrt{-\hat{g}}$. One
could also consider the terms, $\sqrt{-\hat{g}}\,{\hat{R}}$, and
$\sqrt{-\hat{g}}{(\hat{\nabla}\Phi)^{2}}/(1-\Phi^{2}/M^{2})^{2}$, to be added
to the action (9), with arbitrary coefficients; these terms would individually
respect the symmetry (10). However, only one linear combination of the above
two terms retains the structure of the action (1) intact, which is necessary
to preserve the same trace anomaly equation as one gets in GR (see Section 4).
Therefore, in addition to the fine tuning of the cosmological constant, one
needs to adopt another fine tuning of the relative coefficients between the
above two terms777One could relax this tuning somewhat to obtain the trace
anomaly equation that would slightly differ from that of GR; this is easy to
do but there is no urgency to pursue such extensions..

The action (1), and the relation (2), are invariant under the following
"duality" transformations: $M\leftrightarrow\bar{M}$,
$g\leftrightarrow-\bar{g}$, $\sigma\rightarrow-\sigma$. The latter leads to
$\hat{g}\rightarrow{\epsilon}^{-2}\hat{g}$, rendering the following three
terms invariant, $M^{4}\sqrt{-\hat{g}}$, $M^{2}\sqrt{-\hat{g}}\,{\hat{R}}$ and
$\sqrt{-\hat{g}}{(\hat{\nabla}\Phi)^{2}}/(1-\Phi^{2}/M^{2})^{2}$; furthermore,
coupling of $\hat{g}$ to massless scalars, spinors, and vector fields can be
made invariant by inserting appropriate powers of $M$ in front of their
kinetic terms. Therefore, the above "duality symmetry" does not help to avoid
the need for the fine tuning of the two parameters discussed above.

The equations of motion that follow from (9) read:

$\displaystyle(M^{2}$ $\displaystyle-$
$\displaystyle\Phi^{2})\left(R_{\mu\nu}-{1\over
2}g_{\mu\nu}R\right)+\left(\nabla_{\mu}\nabla_{\nu}-g_{\mu\nu}\nabla^{2}\right)\Phi^{2}=6\left(\nabla_{\mu}\Phi\nabla_{\nu}\Phi-{1\over
2}g_{\mu\nu}(\nabla\Phi)^{2}\right),$ (13) $\displaystyle-$ $\displaystyle\Phi
R+6\nabla^{2}\Phi=0\,,$

where one can easily include the matter stress-tensor on the r.h.s. of the
first equation. It is straightforward to show that a flat FLRW solution of GR
is also a solution of (13), amended by the matter stress-tensor.

##  3 Toward the quantum effective theory

In general, one could quantize (9) as an effective low energy action (see
[13], and references to earlier literature). However, there is no need for a
general approach here. Instead, one could regard gravity as a dynamical
classical field coupled to a QFT [9]. This is justified at energy scales much
below the Planck scale.

Quantum loops of the QFT, including the loops by which one would integrate out
possible Planck scale physics, will generate an infinite number of higher-
dimensional terms that one needs to include in the effective action. To deal
with the loop divergencies one could use, e.g., dimensional regularization.

Due to the symmetry (10) of the action (9) and of its coupling to a QFT, all
the higher dimensional terms should also be invariant under (10)888I will
neglect non-perturbative quantum gravity effects due to, e.g., black holes or
worm holes, which are expected to violate global symmetries, and in particular
to violate (10). Such violations are exponentially suppressed at low energies
in the quasi-classical approximation [14]; they should be contrasted to the
violation due to the trace anomaly, which is suppressed only by the powers of
the scale $\bar{M}$, and will be included in the effective action.. Hence, one
could identify all the symmetry preserving terms by writing all possible
invariants in terms of the metric $\hat{g}$, expressed in terms of $g$ and
$\Phi$. Furthermore, the metric $\hat{g}$ approximately equals to $g$, up to
the corrections of the order of $1/M^{2}$, hence, one could just use $g$ as an
approximation. The goal of this section is to understand at what energy scales
are those counter-terms significant.

To achieve this goal, let us introduce dimensionful fields

$\displaystyle{H}_{\mu\nu}={M\left(g_{\mu\nu}-\eta_{\mu\nu}\right)},~{}~{}~{}~{}{\Sigma}={\bar{M}}-\Phi\,,$
(14)

and consider two different limits of the theory (9).

First, consider the limit $M\to\infty$, while $\bar{M}$ is fixed, and ${H}$
and $\Sigma$ are finite. It is then straightforward to see that the Lagrangian
in (9) reduces to a free field theory of ${H}$ and $\Sigma$

$\displaystyle-{1\over
4}\,{H}^{\mu\nu}G_{\mu\nu}({H})-6(\partial{\Sigma})^{2}\,,$ (15)

where $G_{\mu\nu}({H})$ denotes the linearized Einstein tensor. The coupling
to the stress-tensor, $T_{\mu\nu}$, is proportional to
${H}_{\mu\nu}T^{\mu\nu}/M$, up to additional corrections of the order of
${\cal O}\left(\bar{M}^{2}/M^{3}\right)$, and also vanishes in the limit as
long as the stress-tensor is held finite. These considerations show that the
loop-generated counter-terms in the full nonlinear theory should vanish in the
$M\to\infty$ limit.

Second, consider the limit $M\to\infty$, $\bar{M}\to\infty$, with
${\epsilon}=(\bar{M}/M)<<1$ being fixed; the fields ${H}$ and $\Sigma$ are
held finite in this limit, too. The resulting Lagrangian reads

$\displaystyle-{1-{\epsilon}^{2}\over
4}\,{H}^{\mu\nu}G_{\mu\nu}({H})+2{\epsilon}\,{\Sigma}\,R_{L}({H})-6(\partial{\Sigma})^{2}\,,$
(16)

where $R_{L}({H})$ denotes the linearized Ricci scalar, and the coupling to
the matter stress-tensor is proportional to ${H}_{\mu\nu}T^{\mu\nu}/M$, up to
the additional corrections of the order of ${\cal
O}\left(\bar{M}^{2}/M^{3}\right)$. The expression (16) represents a free field
theory of a kinetically mixed tensor and scalar fields, and can easily be
diagonalized by a linear conformal transformation of ${H}_{\mu\nu}$.
Therefore, the counter terms of the full nonlinear theory ought to vanish in
the second limit, too. The latter condition is more restrictive than the one
obtained from the first limit above. It implies that there will not exist
counter-terms proportional to $\bar{M}^{p}/M^{q}$, with $p\geq q$. In
particular, the following counter terms

$\displaystyle\bar{M}^{2}\left({\bar{M}\over
M}\right)^{n}\sqrt{-g}\,{\Sigma}^{2},~{}~{}~{}\left({\bar{M}\over
M}\right)^{m}\sqrt{-g}\,{\Sigma}^{4},$ (17)

will be absent for arbitrary integers $n\geq 0$ and $m\geq 0$ (i.e., such
terms will not be generated with $n\geq 0$ and $m\geq 0$ even if they form
combinations that are invariant under (10)).

Let us now summarize the results of the above discussions in terms of the
fields of the action (9). One concludes that the counter-terms in (9) will be
proportional to

$\displaystyle{R^{3}\over M^{2}},~{}~{}{R\square R\over
M^{2}},~{}~{}{\Sigma^{2}R^{2}\over M^{2}},~{}~{}{\Sigma^{2}R\square R\over
M^{4}}\,,...$ (18)

Each of these counter-terms will have corrections that make them invariant
under (10), however, each of these corrections are higher order in $1/M^{2}$.

All of these counter terms are suppressed by $M$. Furthermore, due to the VEV,
$\langle\Phi\rangle=\bar{M}$, some of the higher dimensional operators will
end up depending on $\bar{M}$, too:

$\displaystyle{\bar{M}^{2}R^{2}\over M^{2}},~{}~{}{\bar{M}^{2}R\square R\over
M^{4}}\,...$ (19)

The lowest scale that suppresses the latter operators is $M(M/\bar{M})$, which
is significantly higher than $M$, thanks to $\bar{M}<<M$.

All the arguments above apply to conventional local counter-terms encountered
in the conventional perturbative series expansion in powers of
$\nabla^{2}/M^{2}$ [13]. This however says nothing about possible non-local
terms that may arise from the loops. Due to their nonlocal nature such terms
could remain significant even when $\nabla^{2}<<M^{2}$. The trace anomaly
introduces precisely such terms, which can then be rewritten as local term but
at the expense of introducing a new field, $\sigma$. The new terms in the
effective action are suppressed by the scale much smaller than $M$. Hence, it
is meaningful to keep the trace-anomaly induced terms, but ignore all the
other conventional higher dimensional counter terms suppressed by $M$ and
higher scales, as done below.

##  4 The effective action

The scale anomaly in the trace of a massless QFT stress-tensor reads [1]:

$\displaystyle T^{\mu}_{\mu}=aE(g)+cW^{2}(g)+b\square R(g)\,,$ (20)

where the coefficients $a$ and $c$ depend on the field content of the theory,
while $b$ is arbitrary, and for that reason will not be included999Both, $b$,
and the gauge field trace anomaly [7, 8], can easily be included in the
effective action [2].. The goal is to find an effective action,
${\tilde{S}}_{A}(g)$, which incorporates the loop effects of the QFT so that
the trace of its metric variation gives (20)

$\displaystyle\,T^{\mu}_{\mu}=\,g^{\alpha\beta}{2\over\sqrt{-g}}\,{\delta{\tilde{S}}_{A}(g)\over\delta
g^{\alpha\beta}}\,=aE(g)+cW^{2}(g)\,.$ (21)

Riegert [2], argued that ${\tilde{S}}_{A}(g)$ cannot be written as a local
diff-invariant functional if one uses only one field, $g$. Yet, the variation
of the total action, $S_{GR}(g)+{\tilde{S}}_{A}(g)$, should give rise to a
local equation for the trace anomaly, with the r.h.s. defined by (21).

To find the action, Riegert introduced a decomposition,
$g_{\mu\nu}=e^{2\sigma}\,{\bar{g}}_{\mu\nu}$, with the metric $\bar{g}$
restricted to have a fixed determinant [2]. Using this decomposition, Riegert
constructed a local action, $S_{A}(\bar{g},\sigma)$, such that the variation
of $S_{GR}(e^{2\sigma}\bar{g})+{S}_{A}(\bar{g},\sigma)$ w.r.t. $\sigma$ gives
the trace anomaly equation. The functional $S_{A}(\bar{g},\sigma)$ was
regarded in [2] as breaking diff-invariance since the determinant of $\bar{g}$
had been fixed [2].

It is however straightforward to restore diff-invariance in
$S_{A}(\bar{g},\sigma)$: one could use exactly the same action,
$S_{A}(\bar{g},\sigma)$, but declare that the restriction on the determinant
of $\bar{g}$ has been lifted. Conversely, such a diff-invariant
$S_{A}(\bar{g},\sigma)$ would yield back Riegert’s original local but non-
invariant $S_{A}(\bar{g},\sigma)$, after gauge-fixing the determinant of
$\bar{g}$.

Logically, Komargodski and Schwimmer [4] reconstructed Riegert’s action
$S_{A}(\bar{g},\sigma)$, as a functional of two fields, $\sigma$ and
$\bar{g}$, without assuming any constraint on $\bar{g}$, only requiring that
the action reproduce the trace anomaly upon simultaneous Weyl transformations
of $\sigma$ and $\bar{g}$.

Furthermore, the same $S_{A}(\bar{g},\sigma)$ was obtained as a Wess-Zumino
term in a coset construction for non-linearly realized conformal symmetry [5].

The above facts suggest that the local and invariant Riegert action,
$S_{A}(\bar{g},\sigma)$, given in (4), should perhaps play a more fundamental
role than it did in Riegert’s construction, where it was merely used as an
intermediate step toward motivating a non-local action101010Riegert’s
subsequent procedure of constructing a non-local but diff-invariant functional
introduces a four derivative term in the action [2]. This rout unavoidably
leads to a negative energy state, a ghost (or to violation to unitarity). It
is also an unnecessary rout – as argued, a local and diff-invariant effective
action for the trace anomaly does exist. More general actions with four-
derivative terms were explored in [15], with some potentially interesting
applications. Regretfully, these actions also have ghosts..

To this end, one could add the action (4) to the GR action expressed in terms
of $\sigma$ and $\bar{g}$, $S_{GR}(e^{2\sigma}\bar{g})$, and treat both
$\sigma$ and $\bar{g}$ as dynamical fields without assuming any constraint on
$\bar{g}$. This theory, however, describes an infinitely strongly coupled
system when restricted to its Minkowski background [6]. It is a strongly
coupled theory with an unacceptably low strong coupling scale on any small
curvature background. This is so because the theory,
$S_{GR}(e^{2\sigma}\bar{g})+{S}_{A}(\bar{g},\sigma)$, does not contain a
kinetic term for $\sigma$. An apparent kinetic term for $\sigma$ in
$S_{GR}(e^{2\sigma}\bar{g})$ can be removed by a field redefinition of the
metric, $\bar{g}=e^{-2\sigma}g$, rendering the $\sigma$ field endowed with
nonlinear interactions in ${S}_{A}(g,\sigma)$, but without a quadratic kinetic
term. Such a theory is intractable as an effective field theory111111This is
not an issue for the work [4] insofar as $\bar{g}$ is not a dynamical field
and is frozen to equal to the flat space metric; in the latter case the GR
action gives a kinetic term for $\sigma$, albeit with a wrong overall sign.
This sign can be flipped to the correct one by choosing a ”wrong sign” GR term
to start with; this does not cause a problem in [4] since the theory does not
use the dynamics of tensor perturbations..

To bring some normalcy, one needs to introduce a kinetic term for $\sigma$.
However, adding in any new term explicitly depending on $\sigma$ – besides the
ones already present in (4) – would spoil the recovery of the correct trace
anomaly. One way out is to use the $R-\bar{R}$ theory as a functional of
$\bar{g}$ and $\sigma$, where the new term, $\bar{R}$, does not depend on
$\sigma$.

This leads one to explore a new action consisting of the $R-\bar{R}$ theory
plus (4):

$\displaystyle S_{eff}(\bar{g},\sigma)=M^{2}\,\int
d^{4}x\sqrt{-{\bar{g}}}\,e^{2\sigma}\left({R}({\bar{g}})+6\,({\bar{\nabla}}\sigma)^{2}\right)-{\bar{M}}^{2}\,\int
d^{4}x\sqrt{-{\bar{g}}}\,R({\bar{g}})+$ $\displaystyle a\int
d^{4}x\sqrt{-{\bar{g}}}\left(\sigma{\bar{E}}-4{\bar{G}}^{\mu\nu}{\bar{\nabla}}_{\mu}\sigma{\bar{\nabla}}_{\nu}\sigma-4({\bar{\nabla}}^{2}\sigma)({\bar{\nabla}}\sigma)^{2}-2({\bar{\nabla}}\sigma)^{4}\right)+c\int
d^{4}x\sqrt{-{\bar{g}}}\,\sigma\,{\bar{W}}^{2}\,.$ (22)

This is a local diff-invariant functional of $\sigma$ and $\bar{g}$. It can be
viewed as an effective action for quantized $\sigma$ and QFT 121212Note that
the Riegert action in the second line in (22) contains the Galileon terms that
are not suppressed by $M$. These can be understood as terms obtained by
”integrating in” the $\sigma$ field to make the otherwise nonlocal anomaly
action be local. In such a case, not all the terms containing $\sigma$ should
be suppressed by $M$. Conversely, integrating out $\sigma$ would lead to
nonlocal terms, all of them suppressed by $M$..

The classical matter fields – not shown in (22) – couple to the metric
${\hat{g}}_{\mu\nu}=g_{\mu\nu}(1-\bar{M}^{2}e^{-2\sigma}/M^{2})\simeq
g_{\mu\nu}=e^{2\sigma}\bar{g}_{\mu\nu}$. Variation of the action (22) with
respect to $\sigma$, with a subsequent substitution of
$\bar{g}=e^{-2\sigma}g$, gives an equation that does not depend on $\sigma$

$\displaystyle{\delta
S_{eff}(\sigma,{\bar{g}})\over\delta\sigma}|_{{\bar{g}}_{\mu\nu}=e^{-2\sigma}\,{g}_{\mu\nu}\
}=0\,,~{}\Rightarrow~{}2M^{2}R=aE(g)+cW^{2}(g)\,,$ (23)

which is exactly the trace-anomaly equation.

Now that the tensor $\bar{g}$ is an unconstrained dynamical field, one should
vary (22) w.r.t. $\bar{g}$, too. This variation will give ten modified
Einstein’s equations. One can show that the trace of these equations does not
coincide with the equation (23). Thus, there are eleven independent equations:
one equation of motion of $\sigma$, and ten equations for ten components of
the symmetric tensor $\bar{g}$. By determining $\sigma$ and $\bar{g}$ from
these equations, one can determine ${\hat{g}}\simeq g$, which is the metric
experienced by the classical matter fields. The modified Einstein equations
approximate well the conventional equations as long as $\bar{M}<<M$, and as
long as the stress-tensor is much smaller than $\bar{M}^{4}$.

Alternatively, one could rewrite the ten equations for $\bar{g}$ as ten
equations for $g$, which would also depend on $\sigma$. The $\sigma$ equation,
on the other hand, can entirely be kept in terms of $g$ (23). Thus, there
would still be eleven equations for eleven unknowns, $g$ and $\sigma$.

The theory given by (22) is strongly coupled at the scale $\bar{M}$. This can
be seen in the flat space expansion of (22) obtained either by taking the
limit $M\to\infty$, or by the substitution

$\displaystyle
g_{\mu\nu}=\eta_{\mu\nu}\left(1-{\Phi^{2}/M^{2}}\right)^{-1},~{}~{}~{}\bar{g}_{\mu\nu}=e^{-2\sigma}\,\left(1-{\Phi^{2}/M^{2}}\right)^{-1}\eta_{\mu\nu}.$
(24)

In either case, the theory reduces to a conformal Galileon of the canonically
normalized field, ${\pi}\equiv\sigma\bar{M}$[16], with the nonlinear Galileon
terms suppressed by the scale $\bar{M}$

$\displaystyle S_{eff}|_{\bar{g}_{\mu\nu}\simeq
e^{-2\pi/\bar{M}}\eta_{\mu\nu}}\simeq\int
d^{4}x\left(-6e^{-2\pi/\bar{M}}(\partial\pi)^{2}+4a\left(-{{\partial^{2}\pi}(\partial\pi)^{2}\over\bar{M}^{3}}+{(\partial\pi)^{2}(\partial\pi)^{2}\over
2\bar{M}^{4}}\right)+\dots\right),$ (25)

where the dots stand for sub-leading terms suppressed by powers of $M$.

Below the scale $\bar{M}$ the full theory (22) is weakly coupled and describes
three degrees of freedom – two helicity states of a massless graviton, and one
massless scalar, ${\pi}\equiv\sigma\bar{M}$. The later becomes strongly
coupled at the scale of the order of $\bar{M}$, as seen from the Galileon
terms in (25). The Lagrangian (25) makes it clear that the theory without the
$\bar{M}^{2}\sqrt{-\bar{g}}{\bar{R}}$ term is untenable – taking $\bar{M}\to
0$ leaves the nonlinear terms in (25) infinitely strongly coupled.

The additional scalar, $\sigma$, does not couple to the stress tensor in the
linearized approximation in Minkowski space, therefore there is no fifth force
constraint. It can couple to matter on curved backgrounds. Physical
consequences of the action (22) will be studies elsewhere.

Acknowledgments: I’d like to thank Massimo Porrati, David Spergel, and Giorgi
Tukhashvili for useful discussions, and Pedro Fernandes and Arkady Tseytlin
for helpful communications. The work was supported in part by NSF grant
PHY-2210349.

Comments added: After this article appeared in the arXiv, Pedro Fernandes
communicated that the action which he derived in [17] using different
principles, is equivalent to the action given above in (22) (up to some
obvious terms). Indeed, if one transforms the action (22) from the Jordan
frame to the Einstein frame, and then changes the field $\sigma$ to $-\phi$,
one obtains the respective terms in the action (14) of [17]. Moreover, the
"duality" discussed in the present work in Section 2, transforms the action
(22) into the action (14) of ref. [17].

The action in ref. [17] was derived based on purely classical principles, by
answering the question: what is the most general scalar-tensor theory of
gravity with the second order equations of motion that has the scalar equation
invariant under the conformal transformations, even if the action is not
conformally invariant? Furthermore, the invariance of the scalar equation of
motion enabled Fernandes to find exact analytic solutions of the theory [17].

It is encouraging that such a different principle gave rise to the action of
[17], which was derived in the present work based on the consistency of the
effective field theory of gravity with the quantum trace anomaly. The anomaly
perspective of the present work is essential: its outcome is that GR needs to
be amended by a scalar degree of freedom – as it is done in the trace anomaly
action (22) – in order for GR to be consistently coupled to a QFT with the
trace anomaly. If so, then there has to exist a new physical scale,
$\bar{M}<<M_{\rm Pl}$, governing the interactions of the scalar with itself,
and governing – along with $M_{\rm Pl}$ – its interactions with the SM fields.
An alternative to the above is to cancel the trace anomaly by introducing
other light degrees of freedom.

### Appendix

A complete diagonalization of (9) can be done by using the following conformal
transformation

$\displaystyle g_{\alpha\beta}={\hat{g}}_{\alpha\beta}\,\left(1-{\Phi^{2}\over
M^{2}}\right)^{-1}\,.$ (26)

It brings the action for the metric $\hat{g}$ to the canonical form

$\displaystyle S_{R-\bar{R}}=\int
d^{4}x\sqrt{-\hat{g}}\,\left(M^{2}\,R(\hat{g})\,-\,{6\,{(\hat{\nabla}\Phi)^{2}}\over(1-\Phi^{2}/M^{2})^{2}}\right)\,.$
(27)

The above conformal transformation is non-singular, and (27) is sensible, as
long as

$\displaystyle\Phi=\bar{M}e^{-\sigma}<<M,~{}~{}~{}\Rightarrow~{}~{}~{}\sigma>>-\,ln(M/\bar{M})\,.$
(28)

In addition, the effective theory is valid if $|\sigma|<<1$, which is a
stronger constraint.

The scalar field action in (27) can be simplified further: it can be reduced
to a free field interacting with gravity, thanks to the following non-linear
field redefinition

$\displaystyle U=\left({1+\Phi/M\over 1-\Phi/M}\right)^{1/2}\,.$ (29)

The resulting action reads:

$\displaystyle S_{R-\bar{R}}=M^{2}\,\int
d^{4}x\sqrt{-\hat{g}}\,\left(R(\hat{g})\,-\,6\,(U^{-1}\hat{\nabla}U)^{2}\right)\,.$
(30)

The latter makes the symmetries of the sigma model more explicit: the
Lagrangian is invariant w.r.t. the rescaling

$\displaystyle U\,\to e^{\lambda}\,U\,,$ (31)

where $\lambda$ is an arbitrary constant. This symmetry is the shift symmetry
of the scalar field ${\rm ln}(U)$ that has only a kinetic term in (30).

Note that $\hat{g}$ and $U$ are related to $\bar{g}$ and $\sigma$ through
nonlinear transformations. However, the path integral $Z(\hat{g})$ does not
equal to the path integral $Z(g)$. In other words, the nonlinear conformal
transformation from $\bar{g}$ to $\hat{g}$, and the quantization procedure for
the scalar and QFT, do not commute with one another. If one were to start with
(30) and combine it with the Riegert action for $\hat{g}$, one would get an
infinitely strongly coupled theory. Instead, the Riegert action that needs to
be added to (30) can be obtained from the Riegert action for $\bar{g}$, by
using the respective nonlinear conformal transformation from $\bar{g}$ to
$\hat{g}$. The obtained action will be strongly coupled at the scale
$\bar{M}$.

## References

  * [1] D. M. Capper and M. J. Duff, Phys. Lett. A 53, 361 (1975) M. J. Duff, Nucl. Phys. B 125, 334-348 (1977) S. M. Christensen and M. J. Duff, Phys. Lett. B 76, 571 (1978)
  * [2] R. J. Riegert, Phys. Lett. B 134, 56-60 (1984)
  * [3] E. S. Fradkin and A. A. Tseytlin, Phys. Lett. B 134, 187 (1984)
  * [4] Z. Komargodski and A. Schwimmer, JHEP 12, 099 (2011) [arXiv:1107.3987 [hep-th]].
  * [5] G. Gabadadze and G. Tukhashvili, Phys. Rev. D 102, no.2, 024054 (2020) [arXiv:2005.01729 [hep-th]].
  * [6] J. Bonifacio, K. Hinterbichler and L. A. Johnson, Phys. Rev. D 102, no.2, 024029 (2020) [arXiv:2004.10716 [hep-th]].
  * [7] R. J. Crewther, Phys. Rev. Lett. 28, 1421 (1972)
  * [8] M. S. Chanowitz and J. R. Ellis, Phys. Lett. B 40, 397-400 (1972)
  * [9] N.D. Birrell, P.C.W. Davies, "Quantum Fields in Curved Space", Cambridge University Press, 1994.
  * [10] D. Anselmi, Annals Phys. 276, 361-390 (1999) [arXiv:hep-th/9903059 [hep-th]].
  * [11] G. W. Horndeski, Int. J. Theor. Phys. 10, 363-384 (1974)
  * [12] B. R. Holstein and J. F. Donoghue, Phys. Rev. Lett. 93, 201602 (2004) [arXiv:hep-th/0405239 [hep-th]].
  * [13] J. F. Donoghue, Phys. Rev. D 50, 3874-3888 (1994) [arXiv:gr-qc/9405057 [gr-qc]]. [arXiv:gr-qc/9512024 [gr-qc]]. [arXiv:1209.3511 [gr-qc]].
  * [14] R. Kallosh, A. D. Linde, D. A. Linde and L. Susskind, Phys. Rev. D 52, 912-935 (1995) [arXiv:hep-th/9502069 [hep-th]].
  * [15] I. Antoniadis and E. Mottola, Phys. Rev. D 45, 2013-2025 (1992) I. Antoniadis, P. O. Mazur and E. Mottola, Phys. Rev. D 55, 4770-4784 (1997) [arXiv:hep-th/9509169 [hep-th]]. Phys. Rev. Lett. 79, 14-17 (1997) [arXiv:astro-ph/9611208 [astro-ph]]. E. Mottola, JHEP 11, 037 (2022) [arXiv:2205.04703 [hep-th]].
  * [16] A. Nicolis, R. Rattazzi and E. Trincherini, Phys. Rev. D 79, 064036 (2009) [arXiv:0811.2197 [hep-th]].
  * [17] P. G. S. Fernandes, Phys. Rev. D 103, no.10, 104065 (2021) [arXiv:2105.04687 [gr-qc]].