# 3$d$ Quantum Gravity Partition Function at 3 Loops: a brute force
computation

Mauricio Leston  Instituto de Astronomía y Física del Espacio IAFE-CONICET,
Ciudad Universitaria, IAFE, 1428, Buenos Aires, Argentina.  Departamento de
Física, Universidad de Buenos Aires FCEN-UBA and IFIBA-CONICET, Ciudad
Universitaria, Pabellón 1, 1428, Buenos Aires, Argentina.  Andrés Goya
Instituto de Astronomía y Física del Espacio IAFE-CONICET, Ciudad
Universitaria, IAFE, 1428, Buenos Aires, Argentina.  Guillem Pérez-Nadal
Departamento de Física, Universidad de Buenos Aires FCEN-UBA and IFIBA-
CONICET, Ciudad Universitaria, Pabellón 1, 1428, Buenos Aires, Argentina.
Mario Passaglia  Departamento de Física, Universidad de Buenos Aires FCEN-UBA
and IFIBA-CONICET, Ciudad Universitaria, Pabellón 1, 1428, Buenos Aires,
Argentina.  Gaston Giribet  Department of Physics, New York University, 726
Broadway, New York, NY10003, USA.

###### Abstract

The partition function of 3-dimensional quantum gravity has been argued to be
1-loop exact. Here, we verify the vanishing of higher-orders in perturbation
theory by explicit computation in the second-order, metric formulation at
3-loops. The number of 1-particle irreducible Feynman diagrams involving both
gravitons and ghosts turns out to be 17. Using dimensional regularization, we
solve all the diagrams. At 2-loops, we find that all such diagrams vanish
separately after regularization. At 3-loops, in contrast, a series of
remarkable cancellations between different diagrams takes place, with 9
diagrams beautifully conspiring to yield a vanishing result. Our techniques
are suitable to be applied to higher loops as well as to similar computations
in higher dimensions.

##  I Introduction

The partition function of 3-dimensional quantum gravity has been shown to be
1-loop exact. In the case of the theory around Anti-de Sitter (AdS) space,
this was proven by Maloney and Witten by the explicit computation of the sum
over configurations MaloneyWitten , and this turns out to be consistent with
the following argument: In 3-dimensional gravity around AdS, in addition to
the classical action, the partition function receives contributions of states
that are Virasoro descendants of the background geometry. This follows from
the analysis of the asymptotic symmetries in AdS performed by Brown and
Henneaux BrownHenneaux . Such contributions, often referred to as boundary
gravitons, organize themselves as Virasoro descendants, and their logarithm,
being independent of the Planck length, is identified as the 1-loop
contribution to the effective action. This insight led Maloney and Witten to
argue that, without further contributions, the full gravity partition function
around AdS turns out to be 1-loop exact, with the only non-vanishing
contributions being the classical action and the Virasoro character, cf.
Witten ; MaloneyWitten ; Giombi . In the case of the theory with zero
cosmological constant the 1-loop exactness of the 3$d$ gravity partition
function was discussed by Witten in an earlier paper Witten0 , where a
computation in the first-order formulation was given, cf. CS . Witten argued
that the perturbative expansion in the theory must terminate at 1-loop. More
recently, the authors of Glenn  found that the 1-loop determinant computation
of the gravity partition function reproduces the character of the Bondi-
Metzner-Sachs (BMS) group, namely the group of asymptotic diffeomorphisms
preserving the boundary conditions of Minkowski space at null infinity Glenn2
; Glenn4 ; Glenn5 . This led to the conclusion that, as it happens in AdS, the
partition function of 3$d$ Einstein gravity in flat space is also 1-loop
exact, with the full effective action being given by the classical
contribution plus a group character, cf. Glenn6 ; Glenn7 ; Mau ; Bianca1 .
However, it still remains to be seen how the 1-loop exactness of the partition
function manifests itself in the second-order, metric formulation. As the
authors of Glenn  stated it, it would be interesting to verify the 1-loop
exacteness of the 3$d$ gravity from a direct gravitational computation. This
is exactly the computation we will address in this paper: we will compute the
partition function of 3$d$ gravity partition function around flat space in the
metric formalism at third order in perturbation theory. That is to say, we
will perform an explicit field theory computation of the gravitational
effective action at 2- and 3-loops.

The paper is organized as follows: In section II, we present the tools that
will equip us for the perturbative computation. We write down the gravity
action in a convenient form, discuss the Faddeev-Popov gauge fixing terms and
the action for the ghost fields; then, we write the vertices and the
propagators for the ghost and the graviton; all these ingredients suffice to
derive the Feynman rules. In section III, we compute all the Feynman diagrams.
At 2-loops, we find that all connected diagrams vanish separately after
dimensional regularization, in agreement with previous computations in the
literature. At 3-loops, in contrast, a series of remarkable cancellations
between different diagrams takes place, with 9 1-particle irreducible (1PI)
diagrams beautifully conspiring to yield a vanishing result. As our techniques
are suitable to be applicable to higher loops as well as to higher dimensions,
we briefly comment on that at the end of section III. Section IV contains our
conclusions.

##  II Perturbation theory

The Einstein-Hilbert gravitational action is

$S_{\rm
EH}=-\dfrac{2}{\kappa^{2}}\int_{M_{d}}d^{d}x\sqrt{|g|}\,R\,+\,B_{\partial{M_{d}}}\,,$
(1)

where $|g|$ is the determinant of the metric and $R$ is the scalar curvature
on the $d$-dimensional manifold $M_{d}$. $B_{\partial{M_{d}}}$ stands for
boundary terms that render the variational principle well-posed. The coupling
constant $\kappa^{2}=32\pi\ell_{P}^{d-2}$ gives the Planck length, $\ell_{P}$,
in $d$ spacetime dimensions. The quantity $\kappa^{2}\hbar$ organizes the loop
expansion. Hereafter, we set $\hbar=1$ and keep track of powers of $\kappa$.

A convenient way to rewrite the Einstein-Hilbert action is the following

$\begin{split}S_{\rm
EH}=-\frac{1}{2\kappa^{2}}&\int_{M_{d}}d^{d}x\sqrt{|g|}\,g^{mn}g^{ab}g^{rs}\Big{(}\partial_{m}{g_{ab}}\partial_{n}{g_{rs}}-\\\
&\partial_{m}{g_{ar}}\partial_{n}{g_{bs}}+2\partial_{m}{g_{br}}\partial_{a}{g_{ns}}-2\partial_{m}{g_{na}}\partial_{b}{g_{rs}}\Big{)}\,\end{split}$

where we are excluding boundary terms LandauLifshitz.Vol2 .

We will perform an expansion of the gravitational field around a background
metric $\bar{g}_{ab}$, namely

$g_{ab}=\bar{g}_{ab}+\kappa\,h_{ab}\,.$ (2)

In our case, the background metric will be that of flat space, i.e.
$\bar{g}_{ab}\equiv\eta_{ab}$; nevertheless, for completeness, let us write
some formulae in full generality; this will allow to show that the techniques
we employ are applicable to computations around other maximally symmetric
solutions. In the action above one replaces the perturbation around
$\bar{g}_{ab}$ and obtains an infinite series in $h_{ab}$; this obviously
follows from expanding $\sqrt{|g|}$, $g_{ab}$ and $g^{ab}$ in terms of
$h_{mn}$. The first terms of the expansion come from
${|g|}^{\frac{1}{2}}={|\bar{g}|^{\frac{1}{2}}}(1+\frac{1}{2}\kappa\bar{g}^{mn}h_{mn}+\ldots)$
and $g^{ab}=\bar{g}^{ab}-\kappa\bar{g}^{am}\bar{g}^{bn}h_{mn}+\ldots$, where
the ellipsis stand for subleading (higher order) contributions. At order
$\mathcal{O}(\kappa^{0}h^{2})$ we have the canonically normalized quadratic
kinematic operator; at order $\mathcal{O}(\kappa h^{3})$, the 3-graviton
vertex; at order $\mathcal{O}(\kappa^{2}h^{4})$, the 4-graviton vertex, and so
on and so forth. At 3-loops, there are be contributions up to order
$\mathcal{O}(\kappa^{4}h^{6})$; see diagram $D_{4}^{(3)}$ below.

Einstein-Hilbert action has to be supplemented with gauge-fixing terms. The
piece of the full action that implements the gauge fixing reads

$S_{\rm gf}=\int_{M_{d}}d^{d}x\sqrt{|g|}\,f^{m}\bar{g}_{mn}f^{n}\,,$ (3)

where the function $f^{m}$ on the background metric $\bar{g}_{mn}$ with a
perturbation $h_{mn}$ is given by

$f^{m}=\left(\bar{g}^{lm}\bar{\nabla}^{n}-\frac{1}{2}\bar{g}^{ln}\bar{\nabla}^{m}\right)h_{nl}\,;$
(4)

$\bar{\nabla}$ is the covariant derivative compatible with the background
metric $\bar{g}$; namely $\bar{\nabla}_{a}\bar{g}_{cb}=0$.

The action for the ghost field $c^{s}$ and the anti-ghost field $\bar{c}^{l}$
is

$S_{\rm gh}=\int_{M_{d}}d^{d}x\sqrt{|g|}\,\bar{c}^{m}\,\dfrac{\delta
f_{m}}{\delta h_{rs}}\,\mathcal{L}_{c}g_{rs}\,,$ (5)

where ${\mathcal{L}}_{c}g_{rs}$ is a Lie derivative of the full metric
$g_{ab}$ with the respect to the ghost field $c^{l}$

${\mathcal{L}}_{c}g_{rs}=2\bar{g}_{l(s}\bar{\nabla}_{r)}{c^{l}}+c^{l}\bar{\nabla}_{l}{h_{rs}}+2h_{l(s}\bar{\nabla}_{r)}{c^{l}}\,.$
(6)

Then, up to a total derivative, the ghost action takes the form

$\displaystyle S_{\rm gh}$
$\displaystyle=\int_{M_{d}}d^{d}x\sqrt{|g|}\,\Big{[}\bar{g}_{ls}\bar{c}^{s}\bar{\nabla}^{2}{c^{l}}+\bar{c}^{r}\bar{\nabla}_{l}\bar{\nabla}_{r}{c^{l}}-\bar{c}^{m}\bar{\nabla}_{m}\bar{\nabla}_{l}{c^{l}}$
(7)
$\displaystyle-\kappa\Big{(}\bar{\nabla}^{r}{\bar{c}^{s}}\bar{\nabla}_{l}{h_{sr}}c^{l}+\bar{\nabla}^{r}{\bar{c}^{s}}h_{ls}\bar{\nabla}_{r}{c^{l}}+\bar{\nabla}^{s}{\bar{c}^{r}}h_{ls}\bar{\nabla}_{r}{c^{l}}$
$\displaystyle-\frac{1}{2}\bar{\nabla}_{m}{\bar{c}^{m}}\bar{\nabla}_{l}{{h}_{r}^{\,r}}\,c^{l}-\bar{\nabla}_{m}{\bar{c}^{m}}h_{ls}\bar{\nabla}^{s}{c^{l}}\Big{)}\Big{]}$

These formulae are consistent with the ones in the literature Grisaru ;
Sagnotti ; deWitt .

Hereafter, we restrict the discussion to flat space. This amounts to replacing
$\bar{g}_{ab}\to\eta_{ab}$ and $\bar{\nabla}_{m}\to\partial_{m}$ in the
expressions above. In flat space, the ghost propagator is

$\Delta_{\rm(gh)}^{ab}[k]=-i\dfrac{\eta^{ab}}{k^{2}}\,.$ (8)

with $k$ being the momentum.

The Einstein-Hilbert action takes the form

$\begin{split}S_{\rm
EH}=&-\frac{1}{2}\int_{M_{d}}d^{d}x\sqrt{|g|}\,g^{mn}g^{ab}g^{rs}\Big{(}\partial_{m}{h_{ab}}\partial_{n}{h_{rs}}-\\\
&\partial_{m}{h_{ar}}\partial_{n}{h_{bs}}+2\partial_{m}{h_{br}}\partial_{a}{h_{ns}}-2\partial_{m}{h_{na}}\partial_{b}{h_{rs}}\Big{)}\,,\,\end{split}$

which can further be expanded in powers of $\kappa h^{ab}$. This yields the
graviton vertices and the graviton propagator

$\Delta_{\rm(gr)}^{mnab}[k]=\dfrac{i}{2k^{2}}\left(\eta^{ma}\eta^{nb}+\eta^{mb}\eta^{na}-\dfrac{2}{d-2}\eta^{mn}\eta^{ab}\right)\,$
(9)

Propagators (8) and (9) are written Minkowski signature. Here, however, we
will work in the Euclidean formalism. This amounts to carefully collect
relative signs of vertices and propagators in the diagrams. In momentum space
$k^{\mu}=(k^{0},k^{1},k^{2})$, we perform the Wick rotation $k^{0}\to ik^{3}$,
with $M_{3}$ being now locally equivalent to $\mathbb{R}^{3}$ with Euclidean
signature. Since we are interested in computing the partition function at
finite temperature, we consider the periodic Euclidean time direction,
$M_{3}=\mathbb{R}^{2}\times S^{1}_{\beta}$, which demands the momentum $k^{3}$
along the thermal cycle to be quantized; namely $k^{3}=2\pi n/\beta$, with
$n\in\mathbb{Z}$ and $\beta\in\mathbb{R}_{>0}$ being the inverse of the
temperature. Nevertheless, we will abuse of notation and write the formal sum
$\int d^{d}k_{l}\,(.)$ to refer to the integration measure on the $l^{\rm th}$
$d$-momentum, while keeping in mind the sum over discrete values for the
component $k_{l}^{3}$.

In the next section, we will apply the ingredients presented above to the
computation of the gravitational effective action at 2-loops and 3-loops.

##  III 3-loop partition function

###  III.1 Partition function

The statement that the 3$d$ gravitational partition function is 1-loop exact
can easily be translated into a statement about the effective action. Consider
the expansion of partition function

$\log Z\,=\,\sum_{n=0}^{\infty}{\hbar}^{n-1}S_{\rm eff}^{(n)}$ (10)

with $S_{\rm eff}^{(n)}$ being the $n^{\text{t}h}$ order contribution to the
effective action, with $S_{\rm eff}^{(n)}\sim\mathcal{O}(\kappa^{2(n-1)})$;
$S_{\rm eff}^{(0)}$ and $S_{\rm eff}^{(1)}$ being given by the classical
action and the 1-loop determinant, respectively. Then, 1-loop exactness is
equivalent to assert that $S_{\rm eff}^{(n)}=0$ to all order $n>1$ in
perturbation theory – or, more precisely, that higher orders in perturbation
theory only contribute to the renormalization of the parameters appearing in
the semiclassical theory Giombi –. Here, we will prove that $S_{\rm
eff}^{(2)}$ and $S_{\rm eff}^{(3)}$ are actually zero.

###  III.2 2-loops

At 2-loops, there are only three 1PI diagrams, which are depicted in Figure 1.

Figure 1: 2-loop 1PI diagrams.

While we have to solve all connected diagrams, all those that are reducible
(Figure 2) vanish by dimensional regularization. This means that we have to
focus on the 1PI. We have to solve the Feynman type integrals corresponding to
each of such diagrams and perform dimensional regularization. We introduce the
notation $d_{i}^{(\ell)}=[D_{i}^{(\ell)}]$ to denote the result of the
calculation of the $i^{\rm th}$, $\ell$-loop diagram $D_{i}^{(\ell)}$. The
symbol $[X]$ refers to the value of the quantity $X$ after dimensional
regularization. It turns out that the three diagrams in Figure 1 also vanish
after dimensional regularization. That is to say,
$d_{1}^{(2)}=[D_{1}^{(2)}]=0$, $d_{2}^{(2)}=[D_{2}^{(2)}]=0$, and
$d_{2,1}^{(2)}=[D_{2,1}^{(2)}]=0$. Therefore, we find

$S_{\rm eff}^{(2)}\,=\,0\,,$ (11)

in full agreement with the argument in Glenn  and the calculations in
Odintsov1 ; Odintsov2 . In the next subsection we will prove that this results
holds at 3-loops.

###  III.3 3-loops

At 3-loops the story is much more involved. The difficulty resides, not only
in the fact that the number of 1PI diagrams is notably larger, but also in
that many diagrams do not vanish after dimensional regularization, and,
therefore, nontrivial cancellations have to occur for the effective action to
be zero. Some of the diagrams have terms proportional to the integral

$I=\kappa^{4}\int\prod_{i=1}^{3}d^{3}k_{i}\,\,\frac{(k_{1}\cdot
k_{2})\,(k_{1}\cdot
k_{3})}{k_{1}^{2}k_{2}^{2}k_{3}^{3}(k_{1}+k_{2}+k_{3})^{2}}\,.$ (12)

This integral is relatively simple to treat at zero temperature, but it
becomes more subtle at finite temperature: we have to be reminded of the fact
that the formal integral over momenta in (12) actually comprises the sum on
the component $k_{i}^{3}=2\pi n_{i}/\beta$ with $n_{i}\in\mathbb{Z}$,
$i=1,2,3$ and $\beta\in\mathbb{R}_{>0}$. That is to say, $I$ is defined as an
infinite sum over integers $n_{1},\,n_{2},\,n_{3}$; more precisely,

$\displaystyle I$ $\displaystyle=$
$\displaystyle{32\pi^{5}\kappa^{4}\beta^{-5}}\sum_{n_{1},n_{2},n_{3}}\int\prod_{i=1}^{3}d^{2}\vec{k}_{i}\,\prod_{j\neq
1}^{3}(\vec{k}_{j}\cdot\vec{k}_{1}+n_{j}\,n_{1})$ (13)
$\displaystyle\Big{[}\big{|}\sum_{t=1}^{3}\vec{k}_{t}\big{|}^{2}+\big{(}\sum_{t=1}^{3}n_{t}\big{)}^{2}\,\Big{]}^{-1}\,\prod_{l=1}^{3}\big{(}|\vec{k}_{l}|^{2}+n_{l}^{2}\,\big{)}^{-1}\,$

where $\vec{k}_{i}=\frac{\beta}{2\pi}(k_{i}^{1},k_{i}^{2})$, so that
$k_{i}=\frac{2\pi}{\beta}(\vec{k}_{i},n_{i}^{3})$. This integral is similar to
those appearing in other 3-loop computations at finite temperature Integrales1
; Integrales2 ; Integrales3 . As these integrals appear in several diagrams at
3-loops, cancellations among different diagrams are actually possible – and,
as we will see, they actually take place.

Figure 2: Two examples of the 6 reducible 3-loop diagrams

Other divergent integrals that may potentially appear in the 3-loop 1PI
diagrams are of the form

$J_{i}=\kappa^{4}\int\prod_{l=1}^{3}d^{3}k_{l}\,\,j_{i}(k_{1},k_{2},k_{3})\,,$
(14)

with integrands

$j_{1}=\frac{\mathcal{O}(k^{2})\,}{k_{1}^{2}k_{2}^{2}k_{3}^{2}}\,,\ \
j_{2}=\frac{\mathcal{O}(k^{4})\,}{k_{1}^{2}k_{2}^{2}k_{3}^{2}(k_{2}+k_{3})^{2}}\,,\
\ j_{3}=\frac{\mathcal{O}(k^{4})\,}{k_{1}^{4}k_{2}^{2}k_{3}^{2}}\,;\,$

however, the latter cancel in $d=3$, either by dimensional regularization
and/or the presence of factors $(d-3)$. This is one of the reasons why the
diagrams appearing in Figure 3 do not effectively contribute; i.e.
$d_{1}^{(3)}=d_{2}^{(3)}=d_{3}^{(3)}=d_{4}^{(3)}=0$.

Figure 3: 3-loop diagrams that vanish after regularization.

Next, we focus on the diagrams shown in Figure 4, whose propagator
contributions make their dimensional regularization analysis more involved.

Figure 4: 3-loop graviton diagrams.

In order to solve the diagrams
$D_{5}^{(3)},D_{6}^{(3)},D_{7}^{(3)},\,D_{8}^{(3)}$, first one needs to
compute the multiplicity factor associated to each of them. If $g_{i}^{(3)}$
denotes the multiplicity factor corresponding to the diagram $D_{i}^{(3)}$,
then combinatorics yields

$g_{5}^{(3)}=\frac{1}{24}\,,\ \ \ g_{6}^{(3)}=\frac{1}{16}\,,\ \ \
g_{7}^{(3)}=\frac{1}{8}\,,\ \ \ g_{8}^{(3)}=\frac{1}{24}\,.$

After multiplying these factors by the result of each diagram obtained after
dimensional regularization, we find

$\displaystyle d_{5}^{(3)}=\frac{45}{16}I\,,\ \ d_{6}^{(3)}=I\,,\ \
d_{7}^{(3)}=-\frac{61}{16}I\,,\ \ d_{8}^{(3)}=\frac{3}{2}I\,$

where $I$ is the integral given in (13). The evaluation of these diagrams,
especially the Melon $D_{5}^{(3)}$ and the Benz $D_{8}^{(3)}$, is lengthy and
requires precision.

Now, let us consider the diagrams with ghost field contributions. We begin
with the ghostly Benz diagrams shown in Figure 5.

Figure 5: 3-loop diagrams with ghosts fields; cf. deWitt .

It turns out that, after dimensional regularization, these diagrams also
result proportional to (13). Concretely, they yield

$\displaystyle d_{8,1}^{(3)}=\frac{11}{4}I\,,\ \ \ \
d_{8,2}^{(3)}=-\frac{13}{8}I\,;$

having multiplicity factors $g_{8,1}^{(3)}=1/3$ and $g_{8,2}^{(3)}=1/4$,
respectively. The different signs between $d_{8,1}^{(3)}$ and $d_{8,2}^{(3)}$
follows from the number of ghost propagators in each diagram.

There are also diagrams with ghost contributions that vanish directly by
dimensional regularization; the diagram $D_{1,1}^{(3)}$ shown in Figure 6 is
of that sort, i.e. $d_{1,1}^{(3)}=0$.

Figure 6: 3-loop diagrams with ghosts fields.

The non-vanishing 3-loop diagrams with ghost contributions are depicted in
Figure 7. Their evaluation is lengthy but can be done systematically. It
yields

$\displaystyle d_{6,1}^{(3)}=\,-\frac{1}{2}\,I\,,\ \ \
d_{6,2}^{(3)}=\,-\frac{3}{8}\,I\,,\ \ \ d_{6,3}^{(3)}=\,-\frac{7}{4}\,I\,.$

The multiplicity factors of these diagrams are $g_{6,1}^{(3)}=1/2$,
$g_{6,2}^{(3)}=1/4$, and $g_{6,3}^{(3)}=1/4$, respectively.

Figure 7: 3-loop diagrams with ghosts fields.

Finally, putting all this together, we find that the 3-loop contribution to
the gravitational effective action reduces to an expression proportional to
$I$, with a coefficient proportional to

$d_{5}^{(3)}+d_{6}^{(3)}+d_{6,1}^{(3)}+d_{6,2}^{(3)}+d_{6,3}^{(3)}+d_{7}^{(3)}+d_{8}^{(3)}+d_{8,1}^{(3)}+d_{8,2}^{(3)}=0$

Therefore, we finally find

$S_{\rm eff}^{(3)}\,=\,0\,.$ (15)

in full agreement with Glenn . This result follows from a notable cancellation
among different diagrams; a cancellation that decomposes as follows

$\Big{(}\frac{45}{16}+1-\frac{61}{16}+\frac{3}{2}+\frac{11}{4}-\frac{13}{8}-\frac{1}{2}-\frac{3}{8}-\frac{7}{4}\Big{)}\,I\,=\,0$

with each term in the sum coming from a different diagram. Notice that in this
cancellation there are also partial cancellations, e.g.
$d_{5}^{(3)}+d_{6}^{(3)}=-d_{6,1}^{(3)}$. It would be desirable to understand
if there is a precise reason for the cancellation of different subsets of
diagrams, and thus gain intuition that could serve us for calculations at
higher loops. The fact that all diagrams cancel is remarkable, as it might
have happened that the graviton and ghost contributions did not completely
cancel at higher loops; see the discussion in Glenn  about this point; see
also Guardini  and references thereof.

###  III.4 Higher dimensions

In order to further study the origin of the cancellation expressed by equation
(15), we find illustrative to discuss the computation in $d$ dimensions.
Besides, this allows us to emphasize that our techniques are well suited to be
extended to arbitrary dimension $d\geq 3$, something that to some extent is
obvious as we have been working with dimensional regularization.

It can be shown that the $d$-dimensional analog to (15) turns out to be
proportional to sum of terms of the form

${\kappa^{4}}\,\frac{(d-3)}{(d-2)^{2}}\,P_{i}(d)\,I_{i}$ (16)

where $I_{i}$ stand for the the $d$-dimensional extension of integral (13) and
for other integrals that appear in $d>3$, and $P_{i}(d)$ are polynomials. This
manifestly shows that the cancellation in (15) only happens for $d=3$. It is
worth mentioning that, in addition to the eight diagrams depicted in Figures
4, 5 and 7, other diagrams also contribute to (16) when $d>3$. In $d$
dimensions there may be additional integrals to be solved as we have checked
that several contributions throughout the computation vanish due to factors of
$(d-3)$. In spite of all that, our techniques can well be adapted to $d\geq
3$.

###  III.5 Higher loops

Before concluding, a few words about higher loops: While our techniques can in
principle be applied to higher-loops, the calculation becomes rapidly
unmanageable due to the increasing number of 1PI diagrams. At 4-loops the
number of diagrams happens to be, roughly, one order of magnitude larger than
the number of them at 3-loops. Graviton vertices of order
$\mathcal{O}(\kappa^{6}h^{8})$ start to contribute and the plethora of graphs
becomes unwieldy. Still, one can say a few things about the 4-loop 1PI
contributions; for example, that there are many diagrams that vanish after
dimensional regularization, while other diagrams, e.g. the one depicted in
Figure 8, happen to be more involved. Therefore, one also expects
cancellations similar to the one we obtained in (15) to take place at 4-loops.

Figure 8: Example of a 4-loop graviton diagram.

##  IV Conclusions

In this paper, we computed the 3-dimensional gravitational effective action in
flat spacetime at 2- and 3-loops in the second-order, metric formalism. We
showed that the result vanishes, in agreement with Witten0 ; MaloneyWitten ;
Giombi ; Glenn . The computation amounted to handle the ghost and graviton
contributions, and solve the integrals associated to all connected Feynman
diagrams. The calculation, being lengthy and requiring precision, demanded the
implementation of a systematic procedure. By dealing with dimensional
regularization, we solved all the connected 2- and 3-loop diagrams. At
2-loops, we found that all the diagrams vanish in any number of dimensions.
This led us to explore the next order in the loop expansion. At 3 loops, there
are 14 1PI diagrams, 9 of them surviving after carefully performing
dimensional regularization. Crucial to the final result was a remarkable
cancellation among the latter, with the 9 diagrams conspiring to yield a
vanishing result in $d=3$. Consequently, our computation turns out to be a
non-trivial check of the 1-loop exactness of the 3$d$ partition function
Witten0 . In other words, we have provided a consistency check of the result
presented in Glenn , where the authors argued that the quantum corrections to
3$d$ gravity partition function around flat space is fully determined by a
1-loop determinant that reproduces the character of the BMS group.

### Acknowledgments

The authors thank Glenn Barnich, David Blanco, Stephen Carlip, Alan Garbarz
for discussions. M.L. thanks the CCPP at NYU for the hospitality during his
stay, where part of this work was done. The computation presented in this
paper partially resorted to FeynCalc R1 ; R2 ; R3 . The computational
resources used in this work were provided in part by the HPC center DIRAC,
funded by IFIBA (UBA-CONICET) and part of SNCAD-MinCyT initiative, Argentina.
This work has been partially supported by grants PIP-(2022)-11220210100685CO,
PIP-(2022)-11220210100225CO, PICT-(2021)-GRFTI-00644, PICT-2020-SERIEA-00164.

## References

  * (1) A. Maloney and E. Witten, “Quantum Gravity Partition Functions in Three Dimensions,” JHEP 02 (2010) 029, [arXiv:0712.0155 [hep-th]].
  * (2) J. D. Brown and M. Henneaux, “Central Charges in the Canonical Realization of Asymptotic Symmetries: An Example from Three-Dimensional Gravity,” Commun.Math.Phys. 104 (1986) 207.
  * (3) E. Witten, “Three-Dimensional Gravity Revisited,” [arXiv:0706.3359 [hep-th]].
  * (4) S. Giombi, A. Maloney and X. Yin, “One-loop Partition Functions of 3D Gravity,” JHEP 08 (2008) 007, [arXiv:0804.1773 [hep-th]].
  * (5) G. Barnich, H. A. Gonzalez, A. Maloney and B. Oblak, “One-loop partition function of three-dimensional flat gravity,” JHEP 04 (2015) 178, [arXiv:1502.06185 [hep-th]].
  * (6) E. Witten, “Topology Changing Amplitudes in (2+1)-Dimensional Gravity,” Nucl. Phys. B 323 (1989) 113.
  * (7) E. Witten, “(2+1)-Dimensional Gravity as an Exactly Soluble System,” Nucl. Phys. B 311 (1988) 46
  * (8) G. Barnich, A. Gomberoff and H. A. Gonzalez, “The flat limit of three dimensional asymptotically anti-de Sitter spacetimes,” Phys. Rev. D 86 (2012) 024020, [arXiv:1204.3288 [gr-qc]].
  * (9) G. Barnich, A. Gomberoff and H. A. Gonzalez, “Dual dynamics of three dimensional asymptotically flat Einstein gravity at null infinity,” JHEP 05 (2013) 016, [arXiv:1303.1075 [hep-th]].
  * (10) G. Barnich, L. Donnay, J. Matulich and R. Troncoso, “Super-BMS3 invariant boundary theory from three-dimensional flat supergravity,” JHEP 01 (2017) 029, [arXiv:1510.08824 [hep-th]].
  * (11) G. Barnich and B. Oblak, “Notes on the BMS group in three dimensions: I. Induced representations,” JHEP 06 (2014) 129, [arXiv:1403.5803 [hep-th]].
  * (12) G. Barnich and B. Oblak, “Notes on the BMS group in three dimensions: II. Coadjoint representation,” JHEP 03 (2015) 033, [arXiv:1502.00010 [hep-th]].
  * (13) A. Garbarz and M. Leston, “Quantization of BMS3 orbits: a perturbative approach,” Nucl. Phys. B 906 (2016) 133, [arXiv:1507.00339 [hep-th]].
  * (14) C. Goeller, E. R. Livine and A. Riello, “Non-Perturbative 3D Quantum Gravity: Quantum Boundary States and Exact Partition Function,” Gen. Rel. Grav. 52 (2020) 24, [arXiv:1912.01968 [hep-th]].
  * (15) L. D. Landau and E. M. Lifschits, “The Classical Theory of Fields,” Pergamon Press, 1975.
  * (16) M. T. Grisaru, P. van Nieuwenhuizen and C. C. Wu, “Background Field Method Versus Normal Field Theory in Explicit Examples: One Loop Divergences in S Matrix and Green’s Functions for Yang-Mills and Gravitational Fields,” Phys. Rev. D 12 (1975) 3203.
  * (17) M. H. Goroff and A. Sagnotti, “Quantum gravity at two loops,” Phys. Lett. B 160 (1985) 81.
  * (18) B. S. DeWitt, “Quantum Theory of Gravity. 2. The Manifestly Covariant Theory,” Phys. Rev. 162 (1967) 1195.
  * (19) I. L. Buchbinder, S. D. Odintsov and O. A. Fonarev, “Two loop approach to effective action in quantum gravity,” Sov. J. Nucl. Phys. 52 (1990) 1101.
  * (20) I. L. Buchbinder, S. D. Odintsov and O. A. Fonarev, “Two loop approximation in quantum gravitation,” Phys. Lett. B 245 (1990) 365.
  * (21) R. Mertig, M. Böhm, and A. Denner, “FEYN CALC: Computer algebraic calculation of Feynman amplitudes,” Comput. Phys. Commun. 64 (1991) 345.
  * (22) V. Shtabovenko, R. Mertig and F. Orellana, “New Developments in FeynCalc 9.0,” Comput. Phys. Commun. 207 (2016) 432, [arXiv:1601.01167 [hep-ph]].
  * (23) V. Shtabovenko, R. Mertig and F. Orellana, “FeynCalc 9.3: New features and improvements,” Comput. Phys. Commun. 256 (2020) 107478, [arXiv:2001.04407 [hep-ph]].
  * (24) A. I. Bugrii and V. N. Shadura, “Three loop contributions to the free energy of lambda phi**4 QFT,” [arXiv:hep-th/9510232 [hep-th]].
  * (25) A. Freitas, “Three-loop vacuum integrals with arbitrary masses,” JHEP 11 (2016) 145, [arXiv:1609.09159 [hep-ph]].
  * (26) S. Bekavac, A. G. Grozin, D. Seidel and V. A. Smirnov, “Three-loop on-shell Feynman integrals with two masses,” Nucl. Phys. B 819 (2009) 183, [arXiv:0903.4760 [hep-ph]].
  * (27) E. Guadagnini, M. Martellini and M. Mintchev, “Perturbative Aspects of the Chern-Simons Field Theory,” Phys. Lett. B 227 (1989) 111.


# Continuous broadband Rydberg receiver using AC Stark shifts and Floquet
States

Danni Song  State Key Laboratory of Quantum Optics and Quantum Optics Devices,
Institute of Laser Spectroscopy, Shanxi University, Taiyuan 030006, P. R.
China  Yuechun Jiao  Authors to whom correspondence should be addressed:
[Yuechun Jiao<EMAIL_ADDRESS>State Key Laboratory of Quantum Optics and
Quantum Optics Devices, Institute of Laser Spectroscopy, Shanxi University,
Taiyuan 030006, P. R. China  Collaborative Innovation Center of Extreme
Optics, Shanxi University, Taiyuan 030006, China  Jinlian Hu  Yuwen Yin
Zhenhua Li  Yunhui He  State Key Laboratory of Quantum Optics and Quantum
Optics Devices, Institute of Laser Spectroscopy, Shanxi University, Taiyuan
030006, P. R. China  Jingxu Bai  Jianming Zhao  Authors to whom correspondence
should be addressed: [Jianming Zhao<EMAIL_ADDRESS>State Key Laboratory
of Quantum Optics and Quantum Optics Devices, Institute of Laser Spectroscopy,
Shanxi University, Taiyuan 030006, P. R. China  Collaborative Innovation
Center of Extreme Optics, Shanxi University, Taiyuan 030006, China  Suotang
Jia  State Key Laboratory of Quantum Optics and Quantum Optics Devices,
Institute of Laser Spectroscopy, Shanxi University, Taiyuan 030006, P. R.
China  Collaborative Innovation Center of Extreme Optics, Shanxi University,
Taiyuan 030006, China

###### Abstract

We demonstrate the continuous broadband microwave receivers based on AC Stark
shifts and Floquet States of Rydberg levels in a cesium atomic vapor cell. The
resonant transition frequency of two adjacent Rydberg states 78$S_{1/2}$ and
78$P_{1/2}$ is tuned based on AC Stark effect of 70 MHz Radio frequency (RF)
field that is applied outside the vapor cell. Meanwhile, the Rydberg states
also exhibit Floquet even-order sidebands that are used to extend the
bandwidths further. We achieve microwave electric field measurements over
1.172 GHz of continuous frequency range. The sensitivity of the Rydberg
receiver with heterodyne technique in the absence of RF field is 280.2
nVcm-1Hz-1/2, while it is dramatically decreased with tuning the resonant
transition frequency in the presence of RF field. Surprisingly, the
sensitivity can be greatly improved if the microwave field couples the Floquet
sideband transition. The achieving of continuous frequency and high
sensitivity microwave detection will promote the application of Rydberg
receiver in the radar technique and wireless communication.

††preprint: AIP/123-QED

> In recent years, remarkable progress has been made in Rydberg atom-based
> electrometry Fancher  _et al._ (2021); Yuan  _et al._ (2023) due to their
> advantages in the measurement of weak microwave fields with high
> sensitivity, calibration-free, stability, and accuracy. An optical Rydberg
> electromagnetically induced transparency (EIT) and Autler-Townes (AT)
> splitting spectroscopy has been employed to measure the properties of
> electric fields, including SI-traceable standards for electric field
> strength Sedlacek  _et al._ (2012); Holloway  _et al._ (2017), polarization
> measurements Sedlacek  _et al._ (2013), subwavelength imaging Holloway  _et
> al._ (2014) and the angle-of-arrival Robinson  _et al._ (2021) with a wide
> frequency range from DC to over 1 THz Fan  _et al._ (2015); Jiao  _et al._
> (2017); Jau and Carter (2020); Wade  _et al._ (2017). The sensitivity of
> Rydberg electrometry has been greatly improved to 55 nVcm-1Hz-1/2 using
> heterodyne technique Jing  _et al._ (2020) and later to 30 nVcm-1Hz-1/2 by
> adding a repumping method to enhance the EIT amplitude Prajapati  _et al._
> (2021). The state-of-the-art sensitivity of Rydberg microwave electrometry
> is improved to 5.1 nVcm-1Hz-1/2 by selection of higher Rydberg states Cai
> _et al._ (2023). Besides the sensitivity, Rydberg atom has plentiful energy
> levels that cover an ultra-wide microwave frequency range. However, the EIT-
> AT-based Rydberg electrometry restricts the measurement of microwave fields
> to a series of discrete frequencies with a narrow bandwidth since it relies
> on resonant or near-resonant transitions between two Rydberg states. To
> achieve continuous-frequency microwave field detection with high
> sensitivity, an auxiliary microwave field resonant with an adjacent Rydberg
> transition is applied to achieve a tunable Rydberg resonant AT splitting
> Simons  _et al._ (2021); Liu  _et al._ (2022); Cui  _et al._ (2023).
> Alternatively, the continuous frequency electric field with high sensitivity
> can also be achieved by utilizing AC Stark shift and in combination with
> heterodyne technique Meyer, Kunz, and Cox (2021); Hu  _et al._ (2022), where
> a strong far off-resonant field acts as the local field to shift the atomic
> energy levels Anderson and Raithel (2017), or by utilizing the DC Stark
> effect to alter the resonance frequency of the two Rydberg states, where the
> DC field is applied by a pair of parallel electrode plates inside the atomic
> vapor cell Ouyang  _et al._ (2023). However, the electrode plates inside the
> cell will reflect and perturb the microwave field, which will scramble its
> polarization. Additionally, the measurement frequency range can be expanded
> using Zeeman effect to split and modify adjacent Rydberg level intervals Shi
> _et al._ (2023). However, for the mentioned approaches above, the
> sensitivity has a significant decrease when the resonant transition
> frequency is largely tuned.

Figure 1: (a) Schematic diagram of the experimental setup. An 852 nm probe
laser counter-propagates and overlaps with a 510 nm Rydberg laser in the cell.
The transmission of the probe and reference beam is detected by a balanced
photodetector (DPD) after passing through a dichroic mirror (DM). An AC field
is applied by a pair of Aluminum parallel-plate electrodes outside the vapor
cell. Two microwave fields, denoted as a local oscillator (LO) field
$E_{\mathrm{LO}}$ and a weak signal field $E_{\mathrm{SIG}}$, are emitted from
two horn antennae. (b) Energy-level diagram for a four-level system. The probe
laser is resonant with the transition of $\arrowvert
6S_{1/2},F=4\rangle\to\arrowvert 6P_{3/2},F^{\prime}=5\rangle$ and the
coupling laser drives the transition of $\arrowvert
6P_{3/2},F^{\prime}=5\rangle\to\arrowvert 78S_{1/2}\rangle$. The LO field
$E_{\mathrm{LO}}$ couples the resonant transition of 78$S_{1/2}$ and
78$P_{1/2}$, sidebands of 78$P_{1/2}$ as well, while the signal field
$E_{\mathrm{SIG}}$ has a frequency difference $\delta_{f}$ with the LO field.
The right part shows the energy shift of two Rydberg states and the generation
of Floquet sidebands in the presence of an AC field.

In this work, we utilize the AC Stark effect of RF field and Rydberg Floquet
states to achieve continuous broadband measurements of microwave fields with
Rydberg atoms in a 133Cs vapor cell. The basic idea is that an RF field is
applied to shift the resonant transition frequency of two adjacent Rydberg
states and generate Floquet even-order sidebands that are coupled by the
microwave field to extend the bandwidths further. Specifically, we excite the
Cs ground atoms to 78$S_{1/2}$ state via a two-photon resonant EIT
spectroscopy, and the microwave field couples the transition of 78$S_{1/2}$
$\to$ 78$P_{1/2}$, and sidebands of 78$P_{1/2}$ as well. The choice of both
Rydberg states with $j=1/2$ is to make EIT spectrum exhibit only
$m_{j}=1/2$-dependent shift and sidebands in the presence of the 70 MHz RF
field. We achieve detection of microwave electric field from 7.377 GHz to
6.205 GHz. The sensitivity of continuous broadband microwave field receivers
is detected using the heterodyne technique. We demonstrate the sensitivity is
decreased with tuning the resonant transition frequency, e.g., when the
resonant frequency between 78$S_{1/2}$ and 78$P_{1/2}$ is tuned from 7.377 GHz
to 6.652 GHz, the sensitivity is decreased from 280.2 nVcm-1Hz-1/2 to 9.566
$\mu$Vcm-1Hz-1/2. However, we find the sensitivity can be greatly improved if
the 6.652 GHz microwave field couples the Floquet sidebands, and the
sensitivity is 1.636 $\mu$Vcm-1Hz-1/2, which is increased by a factor of 5.8.
The use of AC field allows us to place the metal electrodes outside the cell,
such the electrodes can be far away from the cell and will not perturb the
microwave field. Meanwhile, the Floquet sidebands can be utilized to further
extend the bandwidths and improve the sensitivity.

The experiments are performed in a cylindrical cesium room-temperature vapor
cell with 50 mm long and 25 mm diameter. The experimental setup and relevant
energy levels are shown in Fig. 1(a) and (b). Two identical 852 nm laser beams
act as a probe and a reference beam that are both parallel through the cell
along the z-axis. A 510 nm coupling laser counter-propagates and overlaps with
the probe laser, but not the reference beam. The probe laser couples the
$\arrowvert 6S_{1/2},F=4\rangle\to\arrowvert 6P_{3/2},F^{\prime}=5\rangle$
transition with a power of 175 $\mu$W and a diameter waist of 1600 $\mu$m,
while the coupling laser with a power of 56.6 mW and a diameter waist of 1800
$\mu$m drives the $\arrowvert 6P_{3/2},F\textquoteright=5\rangle\to\arrowvert
78S_{1/2}\rangle$ transition, such establishing EIT spectrum. The transmission
of the probe and reference beams pass through a dichroic mirror (DM) and are
detected by a balanced photodetector (DPD), reducing the laser intensity
noise. The probe and coupling lasers keep co-linear polarization along the
x-axis. A pair of Aluminum parallel-plate electrodes (size
$120~{}{\mathrm{mm}}\times 75~{}{\mathrm{mm}}\times 1~{}{\mathrm{mm}}$) is
placed outside the vapor cell with a spacing of 47 mm. A 70 MHz RF field is
provided by a signal generator (Tektronix AFG3102C) using two lead wires and
the electric field vector points along the x-axis. Two microwave fields,
denoted as a local oscillator (LO) field $E_{\mathrm{LO}}$ and a weak signal
fields $E_{\mathrm{SIG}}$, are emitted from two horn antenna (A-info
LB-20180SF) and incident to the cell with co-linear polarization along the
x-axis, simultaneously. The LO field frequency is resonant with the transition
of $\arrowvert 78S_{1/2}\rangle\to\arrowvert 78P_{1/2}\rangle$, while the
signal field has a 20 kHz detuning relative to the resonance transition. In
the presence of the RF field, the 78$S_{1/2}$ and 78$P_{1/2}$ Rydberg states
exhibit different Stark shifts due to their different polarizabilities,
thereby altering the resonant transition frequency of two Rydberg states, and
further the RF field induces the Floquet states of Rydberg atom Jiao  _et al._
(2016).

Figure 2: (a) The measured EIT spectra of 78$S_{1/2}$ state at RF field
strengths of 0 (black solid line), 22.75 V/m (red dashed line) and 32.86 V/m
(blue dotted line), respectively. The second-order sidebands are labeled with
blue circles. (b) Stark shifts of 78$S_{1/2}$ and 78$P_{1/2}$ Rydberg states.
Red diamonds represent the measured Stark shift of 78$S_{1/2}$ Rydberg state
as a function of the RF field strength $E_{\mathrm{RF}}$. The black solid line
and blue dashed line represent the theoretically calculated Stark shift for
the 78$S_{1/2}$ and 78$P_{1/2}$ states.

In Fig. 2(a), we demonstrate the 78$S_{1/2}$ EIT spectra by scanning the
detuning of the coupling laser $\Delta_{\mathrm{C}}$ at indicated RF field
$E_{\mathrm{RF}}=0$ (black solid line), 22.75 V/m (red dashed line) and 32.86
V/m (blue dotted line). The value of $E_{\mathrm{RF}}$ represents the root-
mean-square of RF field. The peak of the field-free EIT spectrum defines the
0-detuning position. It is seen that the EIT peak is red-shifted due to the AC
Stark effect of RF field and there is no splitting because of only one
magnetic substate $m_{j}=1/2$ for $S$ Rydberg states. Besides, we observe the
second-order sidebands, which have band indices $N=\pm 2$, separated by $\pm
140$ MHz from the main peak, labeled in the blue circles for EIT spectrum at
$E_{\mathrm{RF}}=32.86$ V/m. Then we perform a series of measurements such as
in Fig. 2(a) by varying the strength of RF field from 0 to 39.18 V/m in steps
of 1.26 V/m and obtain the Stark shift of EIT main peak as a function of the
RF field strength $E_{\mathrm{RF}}$, shown the red diamonds in Fig. 2(b). We
observe that the 78$S_{1/2}$ EIT peak exhibits two peaks due to the space of
avoided crossing larger than the linewidth of the EIT at
$E_{\mathrm{RF}}>32.86$ V/m. In the following, we demonstrate our experiments
at $E_{\mathrm{RF}}\leq 32.86$ V/m for simple illustration. The black solid
line and blue dashed line represent the calculated DC Stark shift for the
78$S_{1/2}$ and 78$P_{1/2}$ states using the Alkali-Rydberg Calculator (ARC)
Šibalić  _et al._ (2017). Since the RF field frequency is much smaller than
the characteristic atomic frequency, the AC shift follows from the DC
polarizability for the given 78$S_{1/2}$ state Jiao  _et al._ (2016). The
experimental RF field (x-axis) is calibrated by the theoretical calculations.
We can see the Stark shift of 78$P_{1/2}$ is much larger than that of
78$S_{1/2}$, thereby altering the microwave resonant transition frequency.

Figure 3: (a) The measured EIT-AT spectra with microwave coupling the
transition of 78$S_{1/2}$ $\to$ 78$P_{1/2}$ at RF electric field strengths of
0 V/m (black solid line) and 15.16 V/m (red dotted line). The corresponding
microwave resonance transition frequencies are 7.377 GHz and 7.283 GHz,
respectively. (b) The measured microwave resonance transition frequency as a
function of the RF electric field $E_{RF}$ for the transition of 78$S_{1/2}$
$\to$ 78$P_{1/2}$ (black square) and the transition of 78$S_{1/2}$ to the
Floquet sidebands of 78$P_{1/2}$ states (second-order (red circles), fourth-
order (blue triangles), and sixth-order (green inverted triangles)). The black
solid lines represent theoretical calculation and others are the guidelines
for the even-order sidebands.

In Fig. 3(a), we demonstrate two EIT-AT spectra with microwave coupling the
transition of 78$S_{1/2}$ $\to$ 78$P_{1/2}$ at indicated RF field
$E_{\mathrm{RF}}=0$ (black solid line), 15.16 V/m (red dotted line), where the
microwave frequency is adjusted to make the splitting of two peaks
symmetrically, such extracting the microwave resonant transition frequency
between 78$S_{1/2}$ and 78$P_{1/2}$ are 7.377 GHz and 7.283 GHz, respectively.
By measuring such EIT-AT spectra at different RF fields, we obtain the
dependence of microwave resonant transition frequency on the RF field
$E_{\mathrm{RF}}$, shown as the black squares in Fig. 3(b). The results show
that we continuously tune the resonant transition frequency of 78$S_{1/2}$
$\to$ 78$P_{1/2}$ transition for the frequency range of 7.377 GHz to 6.652 GHz
by varying the RF field strength. Then we use the microwave field to couple
the 78$S_{1/2}$ and sidebands of 78$P_{1/2}$ and extract their transition
frequency, shown as red circles (second-order sidebands), blue triangles
(fourth-order sidebands) and green inverted triangles (sixth-order sidebands).
By utilizing the sidebands, we further extend the measurement bandwidth to a
frequency range of 7.377 GHz to 6.205 GHz. The black solid line represents the
resonant transition frequency between 78$S_{1/2}$ and 78$P_{1/2}$ as a
function of $E_{\mathrm{RF}}$ calculated using ARC, and other solid lines
represent the guidelines for the resonant transition frequency between
78$S_{1/2}$ and even-order sidebands of 78$P_{1/2}$.

Figure 4: (a) The measurement of the signal microwave field at
$f_{\mathrm{LO}}=7.377$ GHz and $f_{\mathrm{LO}}=7.112$ GHz. The data were
obtained with heterodyne detection (black hollow squares and red hollow
circles) and EIT-AT splitting in a strong field region (blue solid squares).
The blue solid line shows the calibrated electric field as a function of the
microwave power $\sqrt{P_{\mathrm{SIG}}}$. The black dashed line and red dot-
dashed line indicate the detectable electric fields. (b) The measurement of
the sensitivity of the Rydberg receiver as a function of RF field strength
$E_{\mathrm{RF}}$, corresponding microwave frequency range of 7.377 GHz to
6.205 GHz. The microwave field resonant couples the transition of 78$S_{1/2}$
$\to$ 78$P_{1/2}$ (black squares), and the transition of 78$S_{1/2}$ to
Floquet sidebands of 78$P_{1/2}$ (red circles, blue triangles, and green
inverted triangles). (c) The optimized LO field strength is applied for each
frequency measurement in (b).

Finally, we test the sensitivity of the Rydberg microwave receiver using the
heterodyne technique for the microwave frequencies of 6.205 $\sim$7.377 GHz
range, where the LO and the signal microwave fields have a 20 kHz frequency
difference. When both the LO and the signal fields are incident on the Rydberg
system, the transmission of the probe laser exhibits 20 kHz oscillations that
are proportional to the strength of the applied signal microwave field, from
which we can obtain the detectable microwave field strength by measuring the
power of oscillation signals using a spectrum analyzer Jing  _et al._ (2020).
The inset of Fig. 4(a) shows the measured power spectrum of the oscillation
probe laser at three indicated signal fields $E_{\mathrm{SIG}}$. We can see
the center frequency is located at 20 kHz and the amplitude of the signal
increases with signal field strength. Here, both the probe and coupling lasers
are locked to their resonant transition using an ultrastable Fabry-Perot
cavity with a tunable offset-lock frequency Legaie, Picken, and Pritchard
(2018).

In Fig. 4(a), we demonstrate the measurement of sensitivity of the Rydberg
receiver for the resonant transition between 78$S_{1/2}$ and 78$P_{1/2}$ at
$E_{\mathrm{RF}}=0$ (black dashed line), 16.43 V/m (red dot-dashed line),
corresponding microwave resonant transition frequency of 7.377 GHz and 7.112
GHz. During the experiments, we first measure the EIT-AT splittings to
calibrate the signal field values by
$E_{\mathrm{SIG}}=\frac{h}{\mu}\Delta{f}_{\mathrm{AT}}$, in which the
$E_{\mathrm{SIG}}$ is proportional to the microwave power
$\sqrt{P_{\mathrm{SIG}}}$. The measured electric field is shown with blue
solid squares. The E-field strength at a distance of 60 cm from the cell was
calculated using $E=F{\sqrt{30P\cdot g}}/{d}$, where $g$ is a gain factor of
the antenna, $d$ is the distance between the horn antenna port and the center
of the cell, $F$ is the cell perturbation factor. The details of the
calibration process are shown in our previous work Hu  _et al._ (2022). The
calculated line is plotted in blue to calibrate the electric field strength in
the weak-field region. Measurements of weak signal fields as a function of
microwave power $\sqrt{P_{\mathrm{SIG}}}$ using a spectrum analyzer
(ROHDE$\&$SCHWARZ FSVA3013) with a resolution bandwidth of 1 Hz (measurement
time of T = 1 s), shown as black hollow squares ($f_{\mathrm{LO}}=7.377$ GHz)
and red hollow circles ($f_{\mathrm{LO}}=7.112$ GHz), respectively. The
results show that the output of the spectrum analyzer linearly increases with
the microwave power $\sqrt{P_{\mathrm{SIG}}}$. We identified the
$\sqrt{P_{\mathrm{SIG}}}$ value associated with the data point exhibiting the
detectable heterodyne response, then the amplitude of the microwave electric
field corresponding to this specific data point is obtained by referencing the
calibrated blue line, which is 280.2 nV/cm for $E_{\mathrm{RF}}=0$
($f_{\mathrm{LO}}=7.377$ GHz) and 1.223 $\mu$Vcm-1Hz-1/2 for
$E_{\mathrm{RF}}=16.43$ V/m ($f_{\mathrm{LO}}=7.112$ GHz), respectively.

Following the above process, we measure the detectable microwave electric
field in a frequency range from 7.377 GHz to 6.205 GHz with microwave field
coupling both the main peak and the sidebands, shown in Fig. 4(b). The black
squares represent the measured sensitivity as a function of $E_{\mathrm{RF}}$
for microwave field resonant coupling 78$S_{1/2}$ $\to$ 78$P_{1/2}$ transition
(zero-order sideband), the sensitivity is decreased from 280.2 nVcm-1Hz-1/2 to
9.566 $\mu$Vcm-1Hz-1/2 with tuning the transition frequency from 7.377 GHz to
6.652 GHz. The red circles, blue triangles, and green inverted triangles
represent the measured sensitivity for microwave field coupling the transition
of 78$S_{1/2}$ to the second, fourth, and sixth-order Floquet sidebands of
78$P_{1/2}$, respectively. We can see that the sensitivity is greatly
decreased when the microwave frequency is smaller than 7.2 GHz for the
78$S_{1/2}$ $\to$ 78$P_{1/2}$ transition, while it can be substantially
improved using the microwave field coupling the transition of 78$S_{1/2}$ to
sidebands of 78$P_{1/2}$. For example, the case of microwave of 6.652 GHz,
marked with the vertical dashed line. The sensitivity is 1.636
$\mu$Vcm-1Hz-1/2 for the microwave field coupling sidebands transition, which
is increased by a factor of 5.8 comparison with the sensitivity of 9.566
$\mu$Vcm-1Hz-1/2 for the microwave field coupling main transition. The reason
may be attributed to the different transition dipole moments for the
microwave-induced main transition and sideband transition, which will be our
further work to investigate the transition dipole moments. It should be noted
that before the sensitivity measurement, we first optimize the LO field
strength. Fig. 4(c) shows the optimized LO field strength applied for each
frequency measurement in Fig. 4(b), which varies from 10.58 V/m to 167.77 V/m.

In this work, we demonstrated the continuous-frequency measurement of a weak
microwave electric field over 1.0 GHz by using the AC Stark shift and Floquet
states of Rydberg atoms in a room-temperature cesium vapor cell. The applied
RF field (70 MHz here) is used to shift the Rydberg levels of 78$S_{1/2}$ and
78$P_{1/2}$ that exhibit different Stark shifts, altering the resonant
transition frequency of two Rydberg states. Meanwhile, the Rydberg levels
exhibit RF Floquet sidebands, which are used to extend the bandwidths further.
The Stark shift of 78$S_{1/2}$ is measured by utilizing Rydberg-EIT spectra,
and the corresponding resonant microwave transition is obtained by measuring
EIT-AT splittings for both the transition of 78$S_{1/2}$ $\to$ 78$P_{1/2}$ and
the transition of 78$S_{1/2}$ to sidebands of 78$P_{1/2}$. The sensitivity of
Rydberg microwave receiver is demonstrated by using the heterodyne technique.
The results show that the sensitivity can be greatly improved if we utilize
the microwave fields to couple the RF sidebands for typical microwave
frequency. Our work provides an effective method to extend the bandwidth and
sensitivity by using AC Stark shift and the Floquet state of Rydberg atom. In
principle, we can achieve a wider bandwidth with Rydberg levels after avoiding
crossing or using a high-frequency RF field. The work here is significant for
improving the Rydberg-EIT-based microwave field sensitivity and bandwidth
measurement.

The work is supported by the National Natural Science Foundation of China (No.
U2341211, No. 62175136, No. 12241408, and No. 12120101004); Innovation Program
for Quantum Science and Technology (No. 2023ZD0300902); Fundamental Research
Program of Shanxi Province (Grant No. 202303021224007); and the 1331 project
of Shanxi Province.

The data that support the findings of this study are available from the
corresponding author upon reasonable request.

## References

  * Fancher  _et al._ (2021) C. T. Fancher, D. R. Scherer, M. C. S. John, and B. L. S. Marlow, “Rydberg Atom Electric Field Sensors for Communications and Sensing,” IEEE Transactions on Quantum Engineering 2, 1–13 (2021).
  * Yuan  _et al._ (2023) J. Yuan, W. Yang, M. Jing, H. Zhang, Y. Jiao, W. Li, L. Zhang, L. Xiao, and S. Jia, “Quantum sensing of microwave electric fields based on Rydberg atoms,” Reports on Progress in Physics 86, 106001 (2023).
  * Sedlacek  _et al._ (2012) J. A. Sedlacek, A. Schwettmann, H. Kübler, R. Löw, T. Pfau, and J. P. Shaffer, “Microwave electrometry with Rydberg atoms in a vapour cell using bright atomic resonances,” Nature physics 8, 819–824 (2012).
  * Holloway  _et al._ (2017) C. L. Holloway, M. T. Simons, J. A. Gordon, A. Dienstfrey, D. A. Anderson, and G. Raithel, “Electric field metrology for SI traceability: Systematic measurement uncertainties in electromagnetically induced transparency in atomic vapor,” Journal of Applied Physics 121, 233106 (2017).
  * Sedlacek  _et al._ (2013) J. A. Sedlacek, A. Schwettmann, H. Kübler, and J. P. Shaffer, “Atom-Based Vector Microwave Electrometry Using Rubidium Rydberg Atoms in a Vapor Cell,” Phys. Rev. Lett. 111, 063001 (2013).
  * Holloway  _et al._ (2014) C. L. Holloway, J. A. Gordon, A. Schwarzkopf, D. A. Anderson, S. A. Miller, N. Thaicharoen, and G. Raithel, “Sub-wavelength imaging and field mapping via electromagnetically induced transparency and Autler-Townes splitting in Rydberg atoms,” Applied Physics Letters 104, 244102 (2014), https://doi.org/10.1063/1.4883635 .
  * Robinson  _et al._ (2021) A. K. Robinson, N. Prajapati, D. Senic, M. T. Simons, and C. L. Holloway, “Determining the angle-of-arrival of a radio-frequency source with a Rydberg atom-based sensor,” Applied Physics Letters 118, 114001 (2021), https://doi.org/10.1063/5.0045601 .
  * Fan  _et al._ (2015) H. Fan, S. Kumar, J. Sedlacek, H. Kübler, S. Karimkashi, and J. P. Shaffer, “Atom based RF electric field sensing,” Journal of Physics B: Atomic, Molecular and Optical Physics 48, 202001 (2015).
  * Jiao  _et al._ (2017) Y. Jiao, L. Hao, X. Han, S. Bai, G. Raithel, J. Zhao, and S. Jia, “Atom-Based Radio-Frequency Field Calibration and Polarization Measurement Using Cesium $n{D}_{J}$ Floquet States,” Phys. Rev. Applied 8, 014028 (2017).
  * Jau and Carter (2020) Y.-Y. Jau and T. Carter, “Vapor-Cell-Based Atomic Electrometry for Detection Frequencies below 1 kHz,” Phys. Rev. Applied 13, 054034 (2020).
  * Wade  _et al._ (2017) C. G. Wade, N. Š. N. de Melo, J. Kondo, C.S.Adams, and K. J. Weatherill, “Real-time near-field terahertz imaging with atomic optical fluorescence,” Nature Photonics 11, 40–43 (2017).
  * Jing  _et al._ (2020) M. Jing, Y. Hu, J. Ma, H. Zhang, L. Zhang, L. Xiao, and S. Jia, “Atomic superheterodyne receiver based on microwave-dressed Rydberg spectroscopy,” Nature Physics 16, 911–915 (2020).
  * Prajapati  _et al._ (2021) N. Prajapati, A. K. Robinson, S. Berweger, M. T. Simons, A. B. Artusio-Glimpse, and C. L. Holloway, “Enhancement of electromagnetically induced transparency based Rydberg-atom electrometry through population repumping,” Applied Physics Letters 119, 214001 (2021).
  * Cai  _et al._ (2023) M. Cai, S. You, S. Zhang, Z. Xu, and H. Liu, “Sensitivity extension of atom-based amplitude-modulation microwave electrometry via high Rydberg states,” Applied Physics Letters 122, 161103 (2023).
  * Simons  _et al._ (2021) M. T. Simons, A. B. Artusio-Glimpse, C. L. Holloway, E. Imhof, S. R. Jefferts, R. Wyllie, B. C. Sawyer, and T. G. Walker, “Continuous radio-frequency electric-field detection through adjacent Rydberg resonance tuning,” Physical Review A 104, 032824 (2021).
  * Liu  _et al._ (2022) X.-H. Liu, K.-Y. Liao, Z.-X. Zhang, H.-T. Tu, W. Bian, Z.-Q. Li, S.-Y. Zheng, H.-H. Li, W. Huang, H. Yan, and S.-L. Zhu, “Continuous-Frequency Microwave Heterodyne Detection in an Atomic Vapor Cell,” Physical Review Applied 18, 054003 (2022).
  * Cui  _et al._ (2023) Y. Cui, F.-D. Jia, J.-H. Hao, Y.-H. Wang, F. Zhou, X.-B. Liu, Y.-H. Yu, J. Mei, J.-H. Bai, Y.-Y. Bao, D. Hu, Y. Wang, Y. Liu, J. Zhang, F. Xie, and Z.-P. Zhong, “Extending bandwidth sensitivity of Rydberg-atom-based microwave electrometry using an auxiliary microwave field,” Physical Review A 107, 043102 (2023).
  * Meyer, Kunz, and Cox (2021) D. H. Meyer, P. D. Kunz, and K. C. Cox, “Waveguide-Coupled Rydberg Spectrum Analyzer from 0 to 20 GHz,” Physical Review Applied 15, 014053 (2021).
  * Hu  _et al._ (2022) J. Hu, H. Li, R. Song, J. Bai, Y. Jiao, J. Zhao, and S. Jia, “Continuously tunable radio frequency electrometry with Rydberg atoms,” Applied Physics Letters 121, 014002 (2022).
  * Anderson and Raithel (2017) D. A. Anderson and G. Raithel, “Continuous-Frequency Measurements of High-Intensity Microwave Electric Fields with Atomic Vapor Cells,” Applied Physics Letters 111, 053504 (2017).
  * Ouyang  _et al._ (2023) K. Ouyang, Y. Shi, M. Lei, and M. Shi, “Continuous broadband microwave electric field measurement in Rydberg atoms based on the DC Stark effect,” Applied Physics Letters 123, 264001 (2023).
  * Shi  _et al._ (2023) Y. Shi, C. Li, K. Ouyang, W. Ren, W. Li, M. Cao, Z. Xue, and M. Shi, “Tunable frequency of a microwave mixed receiver based on Rydberg atoms under the Zeeman effect,” Optics Express 31, 36255 (2023).
  * Jiao  _et al._ (2016) Y. Jiao, X. Han, Z. Yang, J. Li, G. Raithel, J. Zhao, and S. Jia, “Spectroscopy of cesium Rydberg atoms in strong radio-frequency fields,” Physical Review A 94, 023832 (2016).
  * Šibalić  _et al._ (2017) N. Šibalić, J. Pritchard, C. Adams, and K. Weatherill, “ARC: An open-source library for calculating properties of alkali Rydberg atoms,” Computer Physics Communications 220, 319–331 (2017).
  * Legaie, Picken, and Pritchard (2018) R. Legaie, C. J. Picken, and J. D. Pritchard, “Sub-kilohertz excitation lasers for quantum information processing with Rydberg atoms,” Journal of the Optical Society of America B 35, 892 (2018).


$\underline{\Lambda^{\prime}(\varphi_{c})}=\min\\{\Lambda^{\prime}(\underline{\varphi}_{c}),\Lambda^{\prime}(\overline{\varphi}_{c})\\},$
(81)
$\underline{\Lambda^{\prime}(\psi_{k})}=\min\\{\Lambda^{\prime}(\underline{\psi}_{k}),\Lambda^{\prime}(\overline{\psi}_{k})\\},$
(82)
$\underline{\Lambda^{\prime}}=\min\\{\Lambda^{\prime}\big{(}\theta_{0}+\underline{X^{\prime}\theta_{2}}\big{)},\Lambda^{\prime}\big{(}\theta_{0}+\theta_{1}+\overline{X^{\prime}\theta_{2}}+\overline{X^{\prime}\theta_{3}}+A_{N}(\theta_{4}+\theta_{5}+\theta_{6})\overline{m}\overline{N}\big{)}\\}.$
(83)

Then,

$\xi^{up}=1-\frac{1}{N}\underline{\Lambda^{\prime}}\cdot\big{(}A_{N}\theta_{4}\underline{N}\cdot\underline{m}+\theta_{1}\big{)}.$
(84)

Under Assumption 2 and 6

$\begin{split}\theta_{1},\theta_{4},A_{N},\underline{N},\underline{m}>0\Rightarrow\big{(}A_{N}\theta_{4}\underline{N}\cdot\underline{m}+\theta_{1}\big{)}>0.\end{split}$
(85)

In addition, we know that $\Lambda(x)$ is a logistic function, and so

$\begin{split}&\Lambda^{\prime}\big{(}\theta_{0}+\underline{X^{\prime}\theta_{2}}\big{)}\in(0,0.25],\\\
&\Lambda^{\prime}\big{(}\theta_{0}+\theta_{1}+\overline{X^{\prime}\theta_{2}}+\overline{X^{\prime}\theta_{3}}+A_{N}(\theta_{3}+\theta_{4}+\theta_{5})\overline{m}\overline{N}\big{)}\in(0,0.25].\\\
\end{split}$ (86)

Hence,

$\begin{split}\underline{\Lambda^{\prime}}\in(0,0.25).\end{split}$ (87)

By assuming that
$\big{(}A_{N}\theta_{4}\underline{N}\cdot\underline{m}+\theta_{1}\big{)}\leq
4N$, we obtain

$\begin{split}\underline{\Lambda^{\prime}}\cdot\big{(}A_{N}\theta_{4}\underline{N}\cdot\underline{m}+\theta_{1}\big{)}<N.\end{split}$
(88)

We conclude that $\xi^{up}<1$. From Bian et al. (2017), $\xi$ only equal to 0
if $\tilde{W}(\mathcal{D})$ is supermodular. Since $\tilde{W}(\mathcal{D})$ is
not supermodular, $\xi^{up}>\xi>0$.

Submodularity Ratio

The submodularity ratio of a non-negative set function is the largest $\gamma$
such that

$\sum_{k\in R\setminus
S}[\tilde{W}(S\cup\\{k\\})-\tilde{W}(S)]\geq\gamma[\tilde{W}(S\cup
R)-\tilde{W}(S)],\quad\forall S,R\subseteq\mathcal{N}.$ (89)

As a consequence,

$\begin{split}\gamma&=\min_{S\neq R}\frac{\sum_{k\in R\setminus
S}[\tilde{W}(S\cup\\{k\\})-\tilde{W}(S)]}{\tilde{W}(S\cup R)-\tilde{W}(S)}\\\
&=\min_{S\neq R}\frac{\sum_{k\in R\setminus
S}\sum_{i}[\tilde{W}_{i}(S\cup\\{k\\})-\tilde{W}_{i}(S)]}{\sum_{i}[\tilde{W}_{i}(S\cup
R)-\tilde{W}_{i}(S)]}\end{split}$ (90)

We can upper bound the denominator in Eq.90 by:

$\sum_{i=1}^{N}[\tilde{W}_{i}(S\cup R)-\tilde{W}_{i}(S)]\leq N.$ (91)

We first rewrite $\sum_{k\in R\setminus
S}[\tilde{W}(S\cup\\{k\\})-\tilde{W}(S)]$ with a view to deriving a lower
bound.

$\begin{split}&\quad\sum_{k\in R\setminus
S}\sum_{i}[\tilde{W}_{i}(S\cup\\{k\\})-\tilde{W}_{i}(S)]\\\ &=\sum_{k\in
R\setminus S}\Bigg{[}\sum_{i\in
S}\Big{[}\Lambda\big{(}\theta_{0}+\theta_{1}+X_{i}^{\prime}(\theta_{2}+\theta_{3})+A_{N}\theta_{5}\sum_{j\neq
i}m_{ij}G_{ij}\tilde{\mu}_{j}+A_{N}\sum_{\begin{subarray}{c}j\neq i\\\ j\in
S\end{subarray}}m_{ij}G_{ij}(\theta_{4}+\theta_{6}\tilde{\mu}_{j})\\\
&\quad+A_{N}m_{ik}G_{ik}(\theta_{4}+\theta_{6}\tilde{\mu}_{k})\big{)}-\Lambda\big{(}\theta_{0}+\theta_{1}+X_{i}^{\prime}(\theta_{2}+\theta_{3})+A_{N}\theta_{5}\sum_{j\neq
i}m_{ij}G_{ij}\tilde{\mu}_{j}^{\prime}+A_{N}\sum_{\begin{subarray}{c}j\neq
i\\\ j\in
S\end{subarray}}m_{ij}G_{ij}(\theta_{4}+\theta_{6}\tilde{\mu}_{j}^{\prime})\big{)}\Big{]}\\\
&\quad+\sum_{c\in\mathcal{N}\setminus
S\cup\\{k\\}}\Big{[}\Lambda\big{(}\theta_{0}+X_{c}^{\prime}\theta_{2}+A_{N}\theta_{5}\sum_{b\neq
c}G_{cb}m_{bc}\tilde{\mu}_{b}+A_{N}\theta_{4}\sum_{\begin{subarray}{c}z\in
S\end{subarray}}m_{cz}G_{cz}+A_{N}\theta_{4}m_{ck}G_{ck}\big{)}\\\
&\quad-\Lambda(\theta_{0}+X_{c}^{\prime}\theta_{2}+A_{N}\theta_{5}\sum_{b\neq
c}G_{cb}m_{bc}\tilde{\mu}_{b}^{\prime}+A_{N}\theta_{4}\sum_{\begin{subarray}{c}z\in
S\end{subarray}}m_{cz}G_{cz})\Big{]}\\\
&\quad+\Lambda(\theta_{0}+\theta_{1}+X_{k}^{\prime}(\theta_{2}+\theta_{3})+A_{N}\theta_{5}\sum_{e\neq
k}m_{ke}G_{ke}\tilde{\mu}_{e}+A_{N}\sum_{\begin{subarray}{c}l\in
S\end{subarray}}m_{kl}G_{kl}(\theta_{4}+\theta_{6}\tilde{\mu}_{l}))\\\
&\quad-\Lambda(\theta_{0}+X_{k}^{\prime}\theta_{2}+A_{N}\theta_{5}\sum_{e\neq
k}m_{ke}G_{ke}\tilde{\mu}_{e}^{\prime}+A_{N}\theta_{4}\sum_{l\in
S}m_{kl}G_{kl})\Bigg{]}.\end{split}$ (92)

We can lower bound the numerator in Eq.90 by:

$\begin{split}\sum_{k\in R\setminus
S}\sum_{i}[\tilde{W}_{i}(S\cup\\{k\\})-\tilde{W}_{i}(S)]&\geq\sum_{k\in
R\setminus
S}\underline{\Lambda^{\prime}}\cdot\big{(}A_{N}\theta_{4}\underline{N}\cdot\underline{m}+\theta_{1}\big{)}\\\
&(\text{By Eq.\ref{eqrk}})\\\
&\geq\underline{\Lambda^{\prime}}\cdot\big{(}A_{N}\theta_{4}\underline{N}\cdot\underline{m}+\theta_{1}\big{)}\end{split}$
(93)

Defining:

$\gamma^{low}=\frac{1}{N}\underline{\Lambda^{\prime}}\cdot\big{(}A_{N}\theta_{4}\underline{N}\cdot\underline{m}+\theta_{1}\big{)},$
(94)

the submodularity ratio can be bounded from below by:

$\gamma\geq\gamma^{low}=1-\xi^{up}\in(0,1).$ (95)

∎

###  A.2 Proof of Proposition 2.1

Under Assumptions 1 and 4, the potential function
$\Phi(y,\mathcal{X},D,G;\boldsymbol{\theta})$ for
$U_{i}(y,\mathcal{X},D,G;\boldsymbol{\theta})$ can be defined as:

$\begin{split}\Phi(y,\mathcal{X},D,G;\boldsymbol{\theta})&=\sum_{i=1}^{N}\left(\theta_{0}+\theta_{1}d_{i}+X_{i}^{\prime}(\theta_{2}+\theta_{3}d_{i})+A_{N}\sum_{j=1}^{N}\theta_{4}m_{ij}G_{ij}d_{j}\right)y_{i}\\\
&\quad+\frac{A_{N}}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}m_{ij}G_{ij}y_{i}y_{j}(\theta_{5}+\theta_{6}d_{i}d_{j}),\end{split},$
(96)

and our interacted decision game is a potential game.

###### Proof.

A potential function is a function $\Phi\mathrel{\mathop{\mathchar
58\relax}}Y\rightarrow\mathbb{R}$ such that:

$\Phi(y_{i}=1,y_{-i},\mathcal{X},D,G)-\Phi(y_{i}=0,y_{-i},\mathcal{X},D,G)=U_{i}(y_{i}=1,y_{-i},\mathcal{X},D,G)-U_{i}(y_{i}=0,y_{-i},\mathcal{X},D,G).$
(97)

Simple computation shows that for any $i\in\mathcal{N}$,

$\begin{split}&\quad\Phi(y_{i}=1,y_{-i},\mathcal{X},D,G)-\Phi(y_{i}=0,y_{-i},\mathcal{X},D,G)\\\
&=\theta_{0}+\theta_{1}d_{i}+X_{i}^{\prime}(\theta_{2}+\theta_{3}d_{i})+A_{N}\sum_{j=1}^{N}\theta_{4}m_{ij}G_{ij}d_{j}+A_{N}\sum_{j=1}^{N}m_{ij}G_{ij}y_{j}(\theta_{5}+\theta_{6}d_{i}d_{j})\\\
&=U_{i}(y_{i}=1,y_{-i},\mathcal{X},D,G)-U_{i}(y_{i}=0,y_{-i},\mathcal{X},D,G).\end{split}$
(98)

Therefore, $\Phi$ is the potential of our interacted decision game.

∎

###  A.3 Proof of Proposition 3.1

Under Assumptions 1 to 4, the optimization for $\tilde{\mu}$ has a unique
maximizer and the iteration procedure of Algorithm 1 converges to this
maximizer.

###### Proof.

To prove the existence of a unique maximizer, we need to show that two
conditions are satisfied.

  * 1.

The objective function is continuous and differentiable in the interior.

  * 2.

The boundary point cannot be a global optimum.

Since our objective function is the sum of linear terms, quadratic functions
and logarithmic functions, the first condition is trivially satisfied. To
check the second condition, we need to verify that the derivative is positive
at $\mu^{Q}_{i}=0$ and is negative at $\mu^{Q}_{i}=1$. The derivative is:

$\begin{split}\frac{\partial}{\partial\mu^{Q}_{i}}\mathcal{A}(\mu^{Q},\mathcal{X},D,G)&=\theta_{0}+\theta_{1}d_{i}+X_{i}^{\prime}\theta_{2}+X_{i}^{\prime}\theta_{3}d_{i}+A_{N}\sum_{j=1}^{N}\theta_{4}m_{ij}G_{ij}d_{j}\\\
&\quad+A_{N}\sum_{j=1}^{N}m_{ij}G_{ij}(\theta_{5}+\theta_{6}d_{i}d_{j})\mu^{Q}_{j}-\log(\mu^{Q}_{i})+\log(1-\mu^{Q}_{i}).\end{split}$
(99)

When $\mu^{Q}_{i}=0$,

$-\log(\mu^{Q}_{i})+\log(1-\mu^{Q}_{i})=-\log(0)+\log(1)=+\infty.$ (100)

When $\mu^{Q}_{i}=1$,

$-\log(\mu^{Q}_{i})+\log(1-\mu^{Q}_{i})=-\log(1)+\log(0)=-\infty.$ (101)

Since all of the elements in
$\theta_{0}+\theta_{1}d_{i}+X_{i}^{\prime}\theta_{2}+X_{i}^{\prime}\theta_{3}d_{i}+A_{N}\sum_{j=1}^{N}\theta_{4}m_{ij}G_{ij}d_{j}+A_{N}\sum_{j=1}^{N}m_{ij}G_{ij}(\theta_{5}+\theta_{6}d_{i}d_{j})\mu^{Q}_{j}$
are bounded,

$\frac{\partial}{\partial\mu^{Q}_{i}}\mathcal{A}(\mu^{Q},\mathcal{X},D,G)|_{\mu^{Q}_{i}=0}=+\infty,$
(102)

and

$\frac{\partial}{\partial\mu^{Q}_{i}}\mathcal{A}(\mu^{Q},\mathcal{X},D,G)|_{\mu^{Q}_{i}=1}=-\infty.$
(103)

Away from the boundary, the objective function increases. A global optimum, if
it exists, then has to be in the interior. Since the objective function is
continuous and differentiable, the first-order condition has to be satisfied
at the global optimum. The coordinate ascent property that holds at every
iterative step implies that the objective function increases at each step,
which further implies that the point that the algorithm converges to cannot be
a local maximum. ∎

###  A.4 Proof of Proposition 3.2

Under Assumptions 1 to 5, the iteration procedure in Algorithm 1 is a
contraction mapping for all $i\in\mathcal{N}$, for all
$\\{d_{i}\\}_{i=1}^{N}\in\\{0,1\\}^{N}$, for all
$\mathcal{X}\in\mathbb{R}^{N\times k}$, and for all $G\in\\{0,1\\}^{N\times
N}$.

###### Proof.

This proof is very similar to Lemma A.2. Recall the iteration in Algorithm 1:

$\tilde{\mu}_{i}^{t+1}=\Lambda\Big{[}\theta_{0}+\theta_{1}d_{i}+X_{i}^{\prime}(\theta_{2}+\theta_{3}d_{i})+A_{N}\theta_{4}\sum\limits_{j\neq
i}m_{ij}G_{ij}d_{j}+A_{N}\sum\limits_{j\neq
i}m_{ij}G_{ij}(\theta_{5}+\theta_{6}d_{i}d_{j})\tilde{\mu}_{j}^{t}\Big{]}.$
(104)

We denote this iteration process as
$\\{\tilde{\mu}^{t}\\}_{t=1}^{\mathcal{T}}$ and show the above mapping
$T\mathrel{\mathop{\mathchar 58\relax}}[0,1]^{N}\rightarrow[0,1]^{N}$ is a
contraction mapping. To prove the above iteration is a contraction mapping, we
use $\ell_{1}$-distance. For any $t\geq 1$,

$d(T(\tilde{\mu}^{t}),T(\tilde{\mu}^{s}))=\sum_{i=1}^{N}\big{|}\tilde{\mu}_{i}^{t+1}-\tilde{\mu}_{i}^{s+1}\big{|},$
(105)

$d(\tilde{\mu}^{t},\tilde{\mu}^{s})=\sum_{i=1}^{N}\big{|}\tilde{\mu}_{i}^{t}-\tilde{\mu}_{i}^{s}\big{|}.$
(106)

First, we know $\Lambda(\cdot)$ is a sigmoid function. Hence, its largest
slope is 0.25.

$\begin{split}\tilde{\mu}^{t+1}_{i}-\tilde{\mu}^{s+1}_{i}&\leq
0.25A_{N}\sum_{j\neq
i}(\theta_{5}+\theta_{6}d_{i}d_{j})m_{ij}G_{ij}(\tilde{\mu}_{j}^{t}-\tilde{\mu}_{j}^{s})\\\
&(\text{By Multivariate Mean Value Theorem})\\\ &\leq
0.25A_{N}\overline{m}(|\theta_{5}|+|\theta_{6}|)\sum_{j\neq
i}G_{ij}(\tilde{\mu}_{j}^{t}-\tilde{\mu}_{j}^{s}\big{)}\\\ &\leq
0.25A_{N}\overline{m}(|\theta_{5}|+|\theta_{6}|)\sum_{j\neq
i}G_{ij}|\tilde{\mu}_{j}^{t}-\tilde{\mu}_{j}^{s}\big{|}.\end{split}$ (107)

Therefore,

$\begin{split}\big{|}\tilde{\mu}^{t+1}_{i}-\tilde{\mu}^{s+1}_{i}\big{|}&\leq\frac{\overline{m}A_{N}(|\theta_{5}|+|\theta_{6}|)}{4}\sum_{j\neq
i}G_{ij}|\tilde{\mu}_{j}^{t}-\tilde{\mu}_{j}^{s}\big{|}.\end{split}$ (108)

Hence,

$\begin{split}\sum_{i=1}^{N}\big{|}\tilde{\mu}^{t+1}_{i}-\tilde{\mu}^{s+1}_{i}\big{|}&\leq\frac{\overline{m}A_{N}(|\theta_{5}|+|\theta_{6}|)}{4}\sum_{i=1}^{N}\sum_{j\neq
i}G_{ij}|\tilde{\mu}_{j}^{t}-\tilde{\mu}_{j}^{s}\big{|}\\\
&\leq\frac{\overline{m}A_{N}(|\theta_{5}|+|\theta_{6}|)\overline{N}}{4}\sum_{i=1}^{N}\big{|}\tilde{\mu}_{i}^{t}-\tilde{\mu}_{i}^{s}\big{|}.\end{split}$
(109)

Therefore, under Assumption 5, $T$ is a contraction mapping. In addition,
since $\tilde{\mu}^{t}\in[0,1]$ for all $t\geq 1$, the metric space
$(\tilde{\mu},d)$ is a complete metric space. By Theorem A.1,
$\\{\tilde{\mu}^{\prime},\tilde{\mu}^{1},...\\}$ will converge to a unique
fixed point, which is $\tilde{\mu}$. ∎

###  A.5 Proof of Lemma 3.1

Under Assumptions 1 to 6, $\tilde{W}(\mathcal{D})$ is a non-negative and non-
decreasing set function.

###### Proof.

First, since $\tilde{W}(\mathcal{D})$ is the summation of logistic functions
and the logistic function is non-negative, $\tilde{W}(\mathcal{D})$ is non-
negative. Second, if we assign one more unit $z$ to $\mathcal{D}$, by Lemma
A.2, for all $i\in\mathcal{N}$, $\tilde{\mu}_{i}$ is non-decreasing.
$\tilde{W}(\mathcal{D})$ is, therefore, a non-decreasing set function. ∎

##  Appendix B Theorem

###  B.1 Proof of Theorem 3.1

Let $Q^{*}$ denote the independent Bernoulli distribution that solves Eq.29.
Under Assumptions 1 to 4, the Kullback–Leibler divergence between $Q^{*}$ and
$P$ is bounded from above by:

$\mathbb{KL}(Q^{*}||P)\leq
C_{1}A_{N}\overline{N}+C_{2}N+\mathcal{O}\left(\sqrt{A_{N}^{2}\overline{N}^{2}N}\right)+\mathcal{O}\left(\sqrt{A_{N}^{3}\overline{N}^{2}N^{2}}\right)+\mathcal{O}\left(\sqrt{A_{N}^{3}\overline{N}N^{3}}\right)+o(N),$
(110)

where $C_{1},C_{2},C_{3},C_{4},C_{5},C_{6}$ are constants that depend only
upon $\boldsymbol{\theta}$, $\overline{m}$, $\max_{1\leq i\leq
N}|X_{i}^{\prime}\theta_{2}|$, and $\max_{1\leq i\leq
N}|X_{i}^{\prime}\theta_{3}|$.

For completeness, we present the statement of Theorem 1.6 in Chatterjee and
Dembo (2016).

######  Theorem B.1.

Chatterjee and Dembo (2016) Suppose that $f\mathrel{\mathop{\mathchar
58\relax}}[0,1]^{N}\rightarrow\mathbb{R}$ is twice continuously differentiable
in $(0,1)^{N}$, so that $f$ and all of its first- and second-order derivatives
extend continuously to the boundary. Let $\lVert f\rVert$ denote the supremum
norm of $f\mathrel{\mathop{\mathchar
58\relax}}[0,1]^{N}\rightarrow\mathbb{R}$. For each $i$ and $j$, denote

$f_{i}\mathrel{\mathop{\mathchar 58\relax}}=\frac{\partial f}{\partial
x_{i}},\quad f_{ij}\mathrel{\mathop{\mathchar
58\relax}}=\frac{\partial^{2}f}{\partial x_{i}\partial x_{j}},$ (111)

and let

$a\mathrel{\mathop{\mathchar 58\relax}}=\lVert f\rVert,\quad
b_{i}\mathrel{\mathop{\mathchar 58\relax}}=\lVert f_{i}\rVert,\quad
c_{ij}\mathrel{\mathop{\mathchar 58\relax}}=\lVert f_{ij}\rVert.$ (112)

Given $\epsilon>0$, $\mathcal{M}(\epsilon)$ is a finite subset of
$\mathbb{R}^{N}$ such that for any $\tilde{\mu}\in\\{0,1\\}^{N}$, there exists
$\eta=(\eta_{1},...,\eta_{N})\in\mathcal{M}(\epsilon)$ such that

$\sum_{i}\Big{(}\frac{\partial
f(\tilde{\mu})}{\partial\tilde{\mu}_{i}}-\eta_{i}\Big{)}^{2}\leq
N\epsilon^{2}.$ (113)

Let us define for any
$\tilde{\mu}=(\tilde{\mu}_{1},...,\tilde{\mu}_{N})\in[0,1]^{N}$,

$I(\tilde{\mu})=\sum_{i=1}^{N}\left[\tilde{\mu}_{i}\log\tilde{\mu}_{i}+(1-\tilde{\mu}_{i})\log(1-\tilde{\mu}_{i})\right].$
(114)

Let us define

$F=\sup_{\tilde{\mu}\in[0,1]^{N}}(f(\tilde{\mu})-I(\tilde{\mu}))+\text{lower
order terms}.$ (115)

Then for an $\epsilon>0,$

$F\leq\sup_{\tilde{\mu}\in[0,1]^{N}}(f(\tilde{\mu})-I(\tilde{\mu}))+\textit{complexity
term}+\textit{smoothness term}.$ (116)

where

$\textit{complexity
term}=\frac{1}{4}\Big{(}n\sum_{i=1}^{N}b_{i}^{2}\Big{)}^{1/2}\epsilon+3N\epsilon+\log|\mathcal{M}(\epsilon)|,$
(117)

and

$\begin{split}\textit{smoothness
term}&=4\Big{(}\sum_{i=1}^{N}(ac_{ii}+b_{i}^{2})+\frac{1}{4}\sum_{i,j=1}^{N}(ac_{ij}^{2}+b_{i}b_{j}c_{ij}+4b_{i}c_{ij})\Big{)}^{1/2}\\\
&\quad+\frac{1}{4}\Big{(}\sum_{i=1}^{N}b_{i}^{2}\Big{)}^{1/2}\Big{(}\sum_{i=1}^{N}c_{ii}^{2}\Big{)}^{1/2}+3\sum_{i=1}^{N}c_{ii}+\log
2.\end{split}$ (118)

###### Proof.

We need to apply Theorem B.1. We define $f\mathrel{\mathop{\mathchar
58\relax}}[0,1]^{N}\rightarrow\mathbb{R}$ as:

$f(\tilde{\mu})=\sum_{i}(\theta_{0}+\theta_{1}d_{i}+X_{i}^{\prime}(\theta_{2}+\theta_{3}d_{i})+A_{N}\theta_{4}\sum\limits_{j\neq
i}m_{ij}G_{ij}d_{j})\tilde{\mu}_{i}+\frac{A_{N}}{2}\sum_{i}\sum_{j}(\theta_{5}+\theta_{6}d_{i}d_{j})m_{ij}G_{ij}\tilde{\mu}_{i}\tilde{\mu}_{j}.$
(119)

Therefore,

$\begin{split}\lVert
f\rVert&\leq\sum_{i}(|\theta_{0}|+|\theta_{1}|+|X_{i}^{\prime}\theta_{2}|+|\theta_{3}X_{i}|)+A_{N}\sum_{i}\sum_{j}|\theta_{4}m_{ij}|G_{ij}+\frac{A_{N}}{2}\sum_{i}\sum_{j}G_{ij}(|\theta_{5}m_{ij}|+|\theta_{6}m_{ij}|)\\\
&\leq
N(|\theta_{0}|+|\theta_{1}|+\max_{i}|X_{i}^{\prime}\theta_{2}|+\max_{i}|X_{i}^{\prime}\theta_{3}|)+\overline{m}A_{N}(|\theta_{4}|+|\theta_{5}|+|\theta_{6}|)\sum_{i}\sum_{j}G_{ij}\\\
&\leq
N(|\theta_{0}|+|\theta_{1}|+\max_{i}|X_{i}^{\prime}\theta_{2}|+\max_{i}|X_{i}^{\prime}\theta_{3}|)+\overline{m}A_{N}N\overline{N}(|\theta_{4}|+|\theta_{5}|+|\theta_{6}|)\\\
&\eqqcolon\tilde{a}.\end{split}$ (120)

The partial derivative of $f(\tilde{\mu})$ with respect to $\tilde{\mu}_{i}$
is:

$\frac{\partial
f(\tilde{\mu})}{\partial\tilde{\mu}_{i}}=\theta_{0}+\theta_{1}+X_{i}^{\prime}\theta_{2}+X_{i}^{\prime}\theta_{3}d_{i}+A_{N}\sum_{j\neq
i}\theta_{4}m_{ij}G_{ij}d_{j}+A_{N}\sum_{j\neq
i}\theta_{5}m_{ij}G_{ij}\tilde{\mu}_{j}+A_{N}\sum_{j\neq
i}\theta_{6}m_{ij}G_{ij}d_{i}d_{j}\tilde{\mu}_{j}.$ (121)

Therefore,

$\begin{split}\lVert\nabla_{i}f(\tilde{\mu})\rVert\leq|\theta_{0}|+|\theta_{1}|+\max_{i}|X_{i}^{\prime}\theta_{2}|+\max_{i}|X_{i}^{\prime}\theta_{3}|+\overline{m}A_{N}\overline{N}(|\theta_{4}|+|\theta_{5}|+|\theta_{6}|)\eqqcolon\tilde{b}.\end{split}$
(122)

The second partial derivative with respect to $\tilde{\mu}_{j}$ is:

$\frac{\partial^{2}f(\tilde{\mu})}{\partial\tilde{\mu}_{i}\partial\tilde{\mu}_{j}}=A_{N}\theta_{5}m_{ij}G_{ij}+A_{N}\theta_{6}m_{ij}G_{ij}d_{i}d_{j}.$
(123)

Therefore, for all $j\neq i$,

$\lVert\nabla_{i}\nabla_{j}g(\tilde{\mu})\rVert\leq\overline{m}A_{N}(|\theta_{5}|+|\theta_{6}|)\eqqcolon\tilde{c},$
(124)

with the second derivative zero if $i=j$. Next, we need to compute
$|\mathcal{M}(\epsilon)|$, where $\mathcal{M}(\epsilon)$ is the finite subset
of $\mathbb{R}^{N}$ such that for any $\tilde{\mu}\in\\{0,1\\}^{N}$, there
exists $\eta=(\eta_{1},...,\eta_{N})\in\mathcal{M}(\epsilon)$ such that

$\sum_{i}\Big{(}\frac{\partial
f(\tilde{\mu})}{\partial\tilde{\mu}_{i}}-\eta_{i}\Big{)}^{2}\leq
N\epsilon^{2}.$ (125)

We note that this is requirement on the derivative at the boundary; we only
need the above condition to hold when $\tilde{\mu}\in\\{0,1\\}^{N}$ to define
$\mathcal{M}(\epsilon)$, and not more generally for $\tilde{\mu}\in(0,1)^{N}$.
Recalling Eq.121 and defining $T_{1}$ and $T_{2}$ as:

$\begin{split}T_{1}(\tilde{\mu})\coloneqq\frac{A_{N}\theta_{5}}{2}\sum_{i}\sum_{j}m_{ij}G_{ij}\tilde{\mu}_{i}\tilde{\mu}_{j},\quad
T_{2}(\tilde{\mu})\coloneqq\frac{A_{N}\theta_{6}}{2}\sum_{i}\sum_{j}m_{ij}G_{ij}d_{i}d_{j}\tilde{\mu}_{i}\tilde{\mu}_{j},\end{split}$
(126)

we state the partial derivative of $f(\tilde{\mu})$ as

$\begin{split}\frac{\partial
f(\tilde{\mu})}{\partial\tilde{\mu}_{i}}&=\theta_{0}+\theta_{1}+X_{i}^{\prime}\theta_{2}+X_{i}^{\prime}\theta_{3}d_{i}+\theta_{4}A_{N}\sum_{j}m_{ij}G_{ij}d_{j}+\frac{\partial
T_{1}(\tilde{\mu})}{\partial\tilde{\mu}_{i}}+\frac{\partial
T_{2}(\tilde{\mu})}{\partial\tilde{\mu}_{i}}.\end{split}$ (127)

Let $\mathcal{M}_{1}(\epsilon)$ be the finite subset of $\mathbb{R}^{N}$ such
that for any $\tilde{\mu}\in\\{0,1\\}^{N}$, there exists
$\lambda=(\lambda_{1},...,\lambda_{N})\in\mathcal{M}_{1}(\epsilon)$ such that

$\sum_{i}\Big{(}\frac{\partial
T_{1}(\tilde{\mu})}{\partial\tilde{\mu}_{i}}-\lambda_{i}\Big{)}^{2}\leq
N\epsilon^{2}.$ (128)

Let $\mathcal{M}_{2}(\epsilon)$ be the finite subset of $\mathbb{R}^{N}$ such
that for any $\tilde{\mu}\in\\{0,1\\}^{N}$, there exists
$\vartheta=(\vartheta_{1},...,\vartheta_{N})\in\mathcal{M}_{2}(\epsilon)$ such
that

$\sum_{i}\Big{(}\frac{\partial
T_{2}(\tilde{\mu})}{\partial\tilde{\mu}_{i}}-\vartheta_{i}\Big{)}^{2}\leq
N\epsilon^{2}.$ (129)

Defining $\lambda_{i}$ and $\vartheta_{i}$ for all $i\in\mathcal{N}$ to be:

$\lambda_{i}=A_{N}\theta_{5}\sum_{j}m_{ij}G_{ij}\tilde{y}_{j},\quad\vartheta_{i}=A_{N}\theta_{6}\sum_{j}m_{ij}G_{ij}d_{i}d_{j}\tilde{v}_{j},$
(130)

where $\tilde{y}_{j}\in\\{0,1\\}$ and $\tilde{v}_{j}\in\\{0,1\\}$ by Lemma
A.1, we can then define $\mathcal{M}(\epsilon)$ as:

$\begin{split}\mathcal{M}(\epsilon)&\mathrel{\mathop{\mathchar
58\relax}}=\Big{\\{}\theta_{0}+\theta_{1}+X_{i}^{\prime}\theta_{2}+X_{i}^{\prime}\theta_{3}d_{i}+A_{N}\theta_{4}\sum_{j}m_{ij}G_{ij}d_{j}+\ell_{1}+\ell_{2}\\\
&\quad\mathrel{\mathop{\mathchar
58\relax}}\ell_{1}\in\mathcal{M}_{1}\left(\frac{\epsilon}{\sqrt{2}}\right),\ell_{2}\in\mathcal{M}_{2}\left(\frac{\epsilon}{\sqrt{2}}\right),i\in\mathcal{N}\Big{\\}}.\end{split}$
(131)

Then,

$\begin{split}\Big{(}\frac{\partial
T_{1}(\tilde{\mu})}{\partial\tilde{\mu}_{i}}-\lambda_{i}\Big{)}^{2}&=\Big{(}A_{N}\theta_{5}\sum_{j}m_{ij}G_{ij}(\tilde{\mu}_{j}-\tilde{y}_{j})\Big{)}^{2}\\\
&\leq\Big{(}A_{N}\theta_{5}\sum_{j}m_{ij}^{2}G_{ij}\Big{)}\Big{(}A_{N}\theta_{5}\sum_{j}(\tilde{\mu}_{j}-\tilde{y}_{j})^{2}\Big{)}\\\
&(\text{By the Cauchy–Schwarz inequality})\\\ &\leq
A_{N}^{2}\theta_{5}^{2}N\sum_{j}(\tilde{\mu}_{j}-\tilde{y}_{j})^{2}\max_{i,j}m_{ij}^{2}\\\
&\leq A_{N}^{2}\theta_{5}^{2}N\tau_{1}^{2}\max_{i,j}m_{ij}^{2}\\\ &\text{(By
Lemma \ref{lemmatau})}\\\ &=\frac{\epsilon^{2}}{2}\quad\text{By choosing
$\tau_{1}=\sqrt{\frac{\epsilon^{2}}{2A_{N}^{2}\theta_{5}^{2}N\max_{ij}m_{ij}^{2}}}$}.\end{split}$
(132)

$\begin{split}\Big{(}\frac{\partial
T_{2}(\tilde{\mu})}{\partial\tilde{\mu}_{i}}-\vartheta_{i}\Big{)}^{2}&=\Big{(}A_{N}\theta_{6}\sum_{j}m_{ij}G_{ij}d_{i}d_{j}(\tilde{\mu}_{j}-\tilde{v}_{j})\Big{)}^{2}\\\
&\leq\Big{(}A_{N}\theta_{6}\sum_{j}m_{ij}^{2}G_{ij}d_{i}d_{j}\Big{)}\Big{(}A_{N}\theta_{6}\sum_{j}(\tilde{\mu}_{j}-\tilde{v}_{j})^{2}\Big{)}\\\
&(\text{By the Cauchy–Schwarz inequality})\\\ &\leq
A_{N}^{2}\theta_{6}^{2}N\sum_{j}(\tilde{\mu}_{j}-\tilde{v}_{j})^{2}\max_{i,j}m_{ij}^{2}\\\
&\leq A_{N}^{2}\theta_{6}^{2}N\tau_{2}^{2}\max_{i,j}m_{ij}^{2}\\\ &\text{(By
Lemma \ref{lemmatau})}\\\ &=\frac{\epsilon^{2}}{2}\quad\text{By choosing
$\tau_{2}=\sqrt{\frac{\epsilon^{2}}{2A_{N}^{2}\theta_{6}^{2}N\max_{ij}m_{ij}^{2}}}$}.\end{split}$
(133)

Therefore,

$|\mathcal{M}(\epsilon)|\leq
N\cdot\frac{N(N+1)}{2}\cdot\Big{|}\mathcal{M}_{1}\left(\frac{\epsilon}{\sqrt{2}}\right)\Big{|}\cdot\Big{|}\mathcal{M}_{2}\left(\frac{\epsilon}{\sqrt{2}}\right)\Big{|}\leq
2^{2N-1}N^{2}(N+1).$ (134)

We now apply Theorem B.1, choosing $\epsilon=N^{-1}$:

$\small\begin{split}\mathbb{K}(Q^{*}\lVert
P)&\leq\frac{1}{4}(N\sum_{i}b_{i}^{2})^{\frac{1}{2}}N^{-1}+3+\log(2^{2N-1}(N^{3}+N))\\\
&\quad+4\Big{(}\sum_{i}b_{i}^{2}+\frac{1}{4}\sum_{i,j}(ac_{ij}^{2}+b_{i}b_{j}c_{ij}+4b_{i}c_{ij})\Big{)}^{\frac{1}{2}}+\log
2\\\ &\leq\frac{\tilde{b}}{4}+3+2N\log
2+\log(N^{3}+N)+4\Big{(}\tilde{b}^{2}N+\frac{1}{4}N^{2}(\tilde{a}\tilde{c}^{2}+\tilde{b}^{2}\tilde{c}+4\tilde{b}\tilde{c})\Big{)}^{\frac{1}{2}}\\\
&=C_{1}A_{N}\overline{N}+C_{2}N\\\
&+\sqrt{(C_{3}A_{N}\overline{N}+C_{4}A_{N}^{2}\overline{N}^{2})N+(C_{5}A_{N}+C_{6}A_{N}^{2}\overline{N}+C_{7}A_{N}^{3}\overline{N}^{2})N^{2}+(C_{8}A_{N}^{2}+C_{9}\overline{N}A_{N}^{3})N^{3}}+o(N)\\\
&=C_{1}A_{N}\overline{N}+C_{2}N+\mathcal{O}\left(\sqrt{A_{N}^{2}\overline{N}^{2}N}\right)+\mathcal{O}\left(\sqrt{A_{N}^{3}\overline{N}^{2}N^{2}}\right)+\mathcal{O}\left(\sqrt{A_{N}^{3}\overline{N}N^{3}}\right)+o(N).\end{split}$
(135)

where $o(N)$ collects those elements that are constant or that grow at a
slower rate than $N$, and

$C_{1}=\frac{1}{4}\overline{m}(|\theta_{4}|+|\theta_{5}|+|\theta_{6}|),$ (136)
$C_{2}=2\log 2,$ (137)
$C_{3}=32\overline{m}(|\theta_{0}|+|\theta_{1}|+\max_{i}|X_{i}^{\prime}\theta_{2}|+\max_{i}|X_{i}^{\prime}\theta_{3}|)(|\theta_{4}|+|\theta_{5}|+|\theta_{6}|)$
(138) $C_{4}=16\overline{m}^{2}(|\theta_{4}|+|\theta_{5}|+|\theta_{6}|)^{2}$
(139)
$C_{5}=4\overline{m}(|\theta_{0}|+|\theta_{1}|+\max_{i}|X_{i}^{\prime}\theta_{2}|+\max_{i}|X_{i}^{\prime}\theta_{3}|+4)(|\theta_{0}|+|\theta_{1}|+\max_{i}|X_{i}^{\prime}\theta_{2}|+\max_{i}|X_{i}^{\prime}\theta_{3}|)(|\theta_{5}|+|\theta_{6}|).$
(140)
$C_{6}=8\overline{m}^{2}[(|\theta_{0}|+|\theta_{1}|+\max_{i}|X_{i}^{\prime}\theta_{2}|+\max_{i}|X_{i}^{\prime}\theta_{3}|)+2](|\theta_{4}|+|\theta_{5}|+|\theta_{6}|)(|\theta_{5}|+|\theta_{6}|),$
(141)
$C_{7}=4\overline{m}^{3}(|\theta_{4}|+|\theta_{5}|+|\theta_{6}|)^{2}(|\theta_{5}|+|\theta_{6}|),$
(142)
$C_{8}=4\overline{m}^{2}(|\theta_{0}|+|\theta_{1}|+\max_{i}|X_{i}^{\prime}\theta_{2}|+\max_{i}|X_{i}^{\prime}\theta_{3}|)(|\theta_{5}|+|\theta_{6}|)^{2},$
(143)
$C_{9}=4\overline{m}^{3}(|\theta_{4}|+|\theta_{5}|+|\theta_{6}|)(|\theta_{5}|+|\theta_{6}|)^{2}.$
(144)

∎

###  B.2 Proof of Theorem 3.2

Under Assumptions 1 to 7, the curvature $\xi$ and submodularity ratio $\gamma$
of $\tilde{W}(\mathcal{D})$ are in $(0,1)$. The greedy Algorithm enjoys an
approximation guarantee for solving the problem in Eq.34 of:

$\tilde{W}(D_{G})\geq\frac{1}{\xi}(1-e^{-\xi\gamma})\tilde{W}(\tilde{D}),$
(145)

where $D_{G}$ is the treatment assignment rule obtained by Algorithm 2.

For completeness, we present the statement of Theorem 1 in Bian et al. (2017).

######  Theorem B.2.

Theorem 1 (Bian et al., 2017) Let $F(\cdot)$ be a non-negative nondecreasing
set function with submodularity ratio $\gamma\in[0,1]$ and curvature
$\xi\in[0,1]$. The greedy algorithm enjoys the following approximation
guarantee for solving the maximization problem with cardinality constraint:

$F(D_{G})\geq\frac{1}{\xi}(1-e^{-\xi\gamma})F(D^{*}),$ (146)

where $D_{G}$ is the result of the greedy algorithm and $D^{*}$ is the optimal
solution.

###### Proof.

The first statement in Theorem 3.2 directly follows Lemma A.3. Then we apply
Theorem B.2 to get the second statement. ∎