As they explain, these games are logarithmic space equivalent to the same
games replacing mean payoff by energy, and polynomial time equivalent to games
with weights [SWZ19], extending games with costs [FZ14].

Combining Theorem 43 with Theorem 15 yields the following result.

######  Theorem 44.

Let $n,d,N\in\mathbb{N}$. There exists an algorithm 555In the RAM model with
word size $w=\log(n)+\log(N)$. for solving disjunctions of parity and mean
payoff games with $n$ vertices, $m$ edges, weights in $(-N,N)$ and priorities
in $[0,d]$ of time complexity

$O\left(md\cdot\underbrace{n\cdot\binom{\lceil\log(n)\rceil+d/2-1}{\lceil\log(n)\rceil}}_{\text{Parity}}\cdot\underbrace{nN}_{\text{Mean
Payoff}}\right).$

and space complexity $O(n)$.

Our algorithm is similar to the one constructed in [DJL18]: they are both
value iteration algorithms (called progress measure lifting algorithm in
[DJL18]), combining the two value iteration algorithms for parity and mean
payoff games. However, the set of values are not the same (our algorithm
stores an additional priority) and the proofs are very different. Besides
being much shorter666The only generic result we use from universal graphs here
is the equivalence between $\mathcal{G}$ and $\mathcal{G}\times\mathcal{A}$
when $\mathcal{A}$ is a separating automaton., one advantage of our proof is
that it works with abstract universal graphs for both parity and mean payoff
objectives, and shows how to combine them, whereas in [DJL18] the proof is
done from scratch, extending both proofs for the parity and mean payoff
objectives.

##  9\. Disjunction of mean payoff

The fourth objective we consider is disjunctions of mean payoff objectives. We
refer to Subsection 9.3 for a discussion on existing results.

The set of colours is a finite set $W^{d}\subseteq\mathbb{Z}^{d}$ for some
$W\subseteq\mathbb{Z}$ with $0\in W$. For $w\in(W^{d})^{\omega}$ and
$i\in[1,d]$ we write $w_{i}\in W^{\omega}$ for the projection on the $i$-th
component.

$\bigvee_{i\in[1,d]}\mathtt{MeanPayoff}(W)_{i}=\left\\{w\in(W^{d})^{\omega}:\exists
i\in[1,d],w_{i}\in\mathtt{MeanPayoff}(W)\right\\}.$

The following theorem states that disjunctions of mean payoff objectives
satisfy our assumptions.

######  Theorem 45 (Lemma 9 in [VCD+15]).

Disjunctions of mean payoff objectives are positionally determined, prefix
independent, and have $\overline{0}$ as neutral letter.

Our approach for constructing universal graphs for disjunctions of mean payoff
objectives differs from the previous two cases. Here we will rely on the
existing constructions of universal graphs for mean payoff objectives, and
show general principles for combining universal graphs for disjunctions of
objectives.

###  9.1. A general reduction of universal graphs for strongly connected
graphs

The first idea is very general, it roughly says that if we know how to
construct universal graphs for strongly connected graphs, then we can use them
to construct universal graphs for general graphs.

We say that a graph $G$ is strongly connected if for every pair of vertices
there exists a path from one vertex to the other. Let us refine the notion of
universal graphs.

[Universal graphs for strongly connected graphs] A graph $\mathcal{U}$ is
$(n,\Omega)$-universal for strongly connected graphs if it satisfies $\Omega$
and all strongly connected graphs of size at most $n$ satisfying $\Omega$ map
into $\mathcal{U}$.

Let us give a first construction, which we refine later. Let $G_{1}$ and
$G_{2}$ two graphs, we define their sequential product $\langle
G_{1},G_{2}\rangle$ as follows: the set of vertices is $V(G_{1})\cup
V(G_{2})$, and the set of edges is

$E(G_{1})\ \cup\ E(G_{2})\ \cup\ \left(V(G_{1})\times C\times
V(G_{2})\right).$

The sequential product is extended inductively: $\langle
G_{1},\dots,G_{p}\rangle=\langle\langle
G_{1},\dots,G_{p-1}\rangle,G_{p}\rangle$. Intuitively, $\langle
G_{1},\dots,G_{p}\rangle$ is the disjoint union of the graphs $G_{i}$’s with
all possible forward edges from $G_{i}$ to $G_{j}$ for any $i<j$.

######  Lemma 46.

Let $\Omega$ be a prefix independent objective, $n\in\mathbb{N}$, and
$\mathcal{U}$ an $(n,\Omega)$-universal graph for strongly connected graphs.
Then
$\mathcal{U}^{n}=\langle\underbrace{\mathcal{U},\dots,\mathcal{U}}_{n\text{
times}}\rangle$ is an $(n,\Omega)$-universal graph.

######  Proof 9.1.

We first note that any infinite path in $\mathcal{U}^{n}$ eventually remains
in one copy of $\mathcal{U}$. Since $\mathcal{U}$ satisfies $\Omega$ and by
prefix independence of $\Omega$, this implies that the infinite path satisfies
$\Omega$, thus so does $\mathcal{U}^{n}$.

Let $G$ be a graph satisfying $\Omega$, we show that $G$ maps into
$\mathcal{U}$. We decompose $G$ into strongly connected components: let
$G_{1},\dots,G_{p}$ be the maximal strongly connected components in $G$
indexed such that if there exists an edge from $G_{i}$ to $G_{j}$ then $i<j$.
Then $V(G)$ is the disjoint union of the $V(G_{i})$’s. Each $G_{i}$ is a
subgraph of $G$, and since $G$ satisfies $\Omega$ then so does $G_{i}$. It
follows that each $G_{i}$ maps into $\mathcal{U}$, let $\phi_{i}$ a
homomorphism $\phi_{i}:G_{i}\to\mathcal{U}$.

Let us define $\phi:G\to\mathcal{U}^{n}$ by $\phi(v)=\phi_{i}(v)$ if $v\in
V(G_{i})$. We now argue that $\phi$ is a homomorphism
$\phi:G\to\mathcal{U}^{n}$. Let $e=(v,c,v^{\prime})\in E(G)$, then either
$e\in E(G_{i})$, and then $(\phi(v),c,\phi(v^{\prime}))\in E(\mathcal{U}^{n})$
because $\phi_{i}$ is a homomorphism, or $e$ goes from $G_{i}$ to $G_{j}$ with
$i<j$, and then again $(\phi(v),c,\phi(v^{\prime}))\in E(\mathcal{U}^{n})$.
Thus $\phi$ is a homomorphism and $\mathcal{U}^{n}$ is $(n,\Omega)$-universal.

In the construction above we have used the fact that $G$ decomposes into at
most $n$ strongly connected components of size $n$. We refine this argument:
the total size of the strongly connected components is $n$. The issue we are
facing in taking advantage of this observation is that the sequence of sizes
is not known a priori, it depends on the graph. To address this we use a
universal sequence. First, here a sequence means a finite sequence of non-
negative integer, for instance $(5,2,3,3)$. The size of a sequence is the
total sum of its elements, so $(5,2,3,3)$ has size $13$. We say that
$v=(v_{1},\dots,v_{k})$ embeds into $u=(u_{1},\dots,u_{k^{\prime}})$ if there
exists an increasing function $f:[1,k]\to[1,k^{\prime}]$ such that for all
$i\in[1,k]$, we have $v_{i}\leq u_{f(i)}$. For example $(5,2,3,3)$ embeds into
$(4,6,1,2,4,1,3)$ but not in $(3,2,5,3,3)$. A sequence $u$ is $n$-universal if
all sequences of size at most $n$ embed into $u$.

######  Remark 9.2.

The notion of $n$-universal sequence is equivalent to that of
$(n,2)$-universal trees: a tree of height $2$ is given by a sequence
consisting of the number of leaves of each subtree of height $1$. This
explains why the constructions that follow may feel familiar after reading
Section 6.

Let us define an $n$-universal sequence $u_{n}$, inductively on
$n\in\mathbb{N}$. We set $u_{0}=()$ (the empty sequence), $u_{1}=(1)$, and
$u_{n}$ is the concatenation of $u_{\lfloor n/2\rfloor}$ with the singleton
sequence $(n)$ followed by $u_{n-1-\lfloor n/2\rfloor}$. Writing $+$ for
concatenation, the definition reads $u_{n}=u_{\lfloor
n/2\rfloor}+(n)+u_{n-1-\lfloor n/2\rfloor}$ Let us write the first sequences:

$u_{2}=(1,2),\quad u_{3}=(1,3,1),\quad u_{4}=(1,2,4,1),\quad
u_{5}=(1,2,5,1,2),\quad u_{6}=(1,3,1,6,1,2),\dots$

######  Lemma 47.

The sequence $u_{n}$ is $n$-universal and has size $O(n\log(n))$.

######  Proof 9.3.

We proceed by induction on $n$. The case $n=0$ is clear, let us assume that
$n>0$. Let $v=(v_{1},\dots,v_{k})$ be a sequence of size $n$, we show that $v$
embeds into $u_{n}$. There exists a unique $p\in[1,k]$ such that
$(v_{1},\dots,v_{p-1})$ has size smaller than or equal to $\lfloor n/2\rfloor$
and $(v_{1},\dots,v_{p})$ has size larger than $\lfloor n/2\rfloor$. This
implies that $(v_{p+1},\dots,v_{k})$ has size at most $n-1-\lfloor
n/2\rfloor$. By induction hypothesis $(v_{1},\dots,v_{p-1})$ embeds into
$u_{\lfloor n/2\rfloor}$ and $(v_{p+1},\dots,v_{k})$ embeds into
$u_{n-1-\lfloor n/2\rfloor}$, so $v$ embeds into $u_{n}$.

The recurrence on size is $|u_{n}|=|u_{\lfloor n/2\rfloor}|+n+|u_{n-1-\lfloor
n/2\rfloor}|$, it implies that $|u_{n}|$ is bounded by $O(n\log(n))$.

We now use the universal sequence to improve on Lemma 46

######  Lemma 48.

Let $\Omega$ be a positionally determined prefix independent objective and
$n\in\mathbb{N}$. For each $k\in[1,n]$, let $\mathcal{U}_{k}$ be a
$(k,\Omega)$-universal graph for strongly connected graphs. Let us write
$u_{n}=(x_{1},\dots,x_{k})$, then
$\mathcal{U}(u_{n})=\langle\mathcal{U}_{x_{1}},\dots,\mathcal{U}_{x_{k}}\rangle$
is an $(n,\Omega)$-universal graph.

######  Proof 9.4.

We follow the same lines as for Lemma 46, in particular the same argument
implies that $\mathcal{U}(u_{n})$ satisfies $\Omega$.

Let $G$ be a graph satisfying $\Omega$, we show that $G$ maps into
$\mathcal{U}(u_{n})$. We decompose $G$ into strongly connected components as
before. Let us write $v=(|V(G_{1})|,\dots,|V(G_{p})|)$ the sequence of sizes
of the components. The sequence $v$ has size at most $n$, implying that $v$
embeds into $u_{n}$: there exists an increasing function
$f:[1,p]\to[1,|u_{n}|]$ such that for all $i\in[1,p]$ we have $|V(G_{i})|\leq
u_{f(i)}$. It follows that for each $i\in[1,p]$, there exists a homomorphism
$\phi_{i}:G_{i}\to\mathcal{U}_{f(i)}$.

Let us define $\phi:G\to\mathcal{U}(u_{n})$ by $\phi(v)=\phi_{i}(v)$ if $v\in
V(G_{i})$. We now argue that $\phi$ is a homomorphism
$\phi:G\to\mathcal{U}^{n}$. Let $e=(v,c,v^{\prime})\in E(G)$, then either
$e\in E(G_{i})$, and then $(\phi(v),c,\phi(v^{\prime}))\in
E(\mathcal{U}(u_{n}))$ because $\phi_{i}$ is a homomorphism, or $e$ goes from
$G_{i}$ to $G_{j}$ with $i<j$, and then again $(\phi(v),c,\phi(v^{\prime}))\in
E(\mathcal{U}(u_{n}))$ because $f$ is increasing. Thus $\phi$ is a
homomorphism and $\mathcal{U}(u_{n})$ is $(n,\Omega)$-universal.

######  Remark 9.5.

To appreciate the improvement of Lemma 48 over Lemma 46, let us consider the
case where the $(k,\Omega)$-universal graph $\mathcal{U}_{k}$ for strongly
connected graphs has size $\alpha k$, where $\alpha$ does not depend on $k$.
Then Lemma 46 yields an $(n,\Omega)$-universal graph of size $\alpha n^{2}$
while Lemma 48 brings it down to $O(\alpha n\log(n))$.

###  9.2. Universal graphs for disjunctions of mean payoff objectives

We state in the following theorem an upper bound on the construction of
universal graphs for disjunctions of mean payoff objectives.

######  Theorem 49.

Let $n,d,N\in\mathbb{N}$ and $W\subseteq\mathbb{Z}$ of largest weight in
absolute value $N$. There exists an
$(n,\bigvee_{i\in[1,d]}\mathtt{MeanPayoff}(W)_{i})$-universal graph of size
$O(n\log(n)\cdot dN)$.

As suggested by the previous subsection, we first construct
$(n,\bigvee_{i\in[1,d]}\mathtt{MeanPayoff}(W)_{i})$-universal graphs for
strongly connected components. The following result shows a decomposition
property.

######  Lemma 50.

Let $G$ be a strongly connected graph and $W\subseteq\mathbb{Z}$. Assume that
$G$ satisfies $\bigvee_{i\in[1,d]}\mathtt{MeanPayoff}(W)_{i}$ then there
exists $i\in[1,d]$ such that $G$ satisfies $\mathtt{MeanPayoff}(W)_{i}$.

######  Proof 9.6.

We prove the contrapositive: assume that for all $i\in[1,d]$ the graph does
not satisfy $\mathtt{MeanPayoff}(W)_{i}$, implying that for each $i\in[1,d]$
there exists a negative cycle $C_{i}$ around some vertex $v_{i}$. By iterating
each cycle an increasing number of times, we construct a path in $G$ which
does not satisfy $\bigvee_{i}\mathtt{MeanPayoff}(W)_{i}$.

To make this statement formal, we use the following property: for any
$i\in[1,d]$, any finite path $\pi$ can be extended to a finite path
$\pi\pi^{\prime}$ with weight $\leq-1$ on the $i$th component. This is
achieved simply by first going to $v_{i}$ using strong connectedness, then
iterating through cycle $C_{i}$ a sufficient number of times.

We then apply this process repeatedly and in a cyclic way over $i\in[1,d]$ to
construct an infinite path such that for each $i\in[1,d]$, infinitely many
times the $i$-th component is less than $-1$. This produces a path which does
not satisfy $\bigvee_{i\in[1,d]}\mathtt{MeanPayoff}(W)_{i}$, a contradiction.

######  Corollary 51.

Let $n\in\mathbb{N},W\subseteq\mathbb{Z}$, and $\mathcal{U}$ be an
$(n,\mathtt{MeanPayoff}(W))$-universal graph for strongly connected graphs. We
construct $d\cdot\mathcal{U}$ the disjoint union of $d$ copies of
$\mathcal{U}$, where the $i$-th copy reads the $i$-th component. Then
$d\cdot\mathcal{U}$ is an
$(n,\bigvee_{i\in[1,d]}\mathtt{MeanPayoff}(W)_{i})$-universal graph for
strongly connected graphs.

We can now prove Theorem 49.

Thanks to Lemma 36, there exists an $(n,\mathtt{MeanPayoff}(W))$-universal
graph of size $nN$. Thanks to Corollary 51, this implies an
$(n,\bigvee_{i\in[1,d]}\mathtt{MeanPayoff}(W)_{i})$-universal graph for
strongly connected graphs of size $ndN$. Now Lemma 48 yields an
$(n,\bigvee_{i}\mathtt{MeanPayoff}(W)_{i})$-universal graph of size
$O(n\log(n)\cdot dN)$ (see Remark 9.5).

###  9.3. The complexity of solving disjunctions of mean payoff games using
universal graphs

As in the previous case disjunction of mean payoff games were studied
focussing on the objective of the opponent, who has a conjunction of mean
payoff objectives to satisfy [VCD+15]. Let us note here that there are
actually two variants of the mean payoff objective: using infimum limit or
supremum limit. In many cases the two variants are equivalent: this is the
case when considering mean payoff games or disjunctions of parity and mean
payoff games. However, this is not true anymore for disjunctions of mean
payoff objectives, as explained in [VCD+15]. Our constructions and results
apply using the infimum limit, and do not extend to the supremum limit

The main result related to disjunction of mean payoff games in [VCD+15]
(Theorem 6) is that the problem is in $\text{NP}\cap\text{coNP}$ and can be
solved in time $O(m\cdot n^{2}\cdot d\cdot N)$. (Note that since we consider
the dual objectives, the infimum limit becomes a supremum limit in [VCD+15].)

Combining Theorem 49 with Theorem 15 yields the following result.

######  Corollary 52.

Let $n,m,d,N\in\mathbb{N}$. In the RAM model with word size
$w=\log(n)+\log(N)+\log(d)$, there exists an algorithm for solving
disjunctions of mean payoff games with weights in $(-N,N)$ with time
complexity $O(m\cdot n\log(n)\cdot d\cdot N)$ and space complexity $O(n)$.

Note that for the choice of word size, the two tasks for manipulating
universal graphs, namely computing $\delta(q,w)$ and checking whether $q\leq
q^{\prime}$ are indeed unitary operations as they manipulate numbers of order
$nN$.

##  10\. Conclusions

In this paper we have introduced the notion of universal graphs for
constructing generic value iteration algorithms for games with positionally
determined objectives. We have instantiated this to four classes of games,
achieving or improving the state of the art for solving these games. There are
many other potential applications, for instance Rabin objectives or
disjunctions of parity objectives.

We laid the first brick for the theory of universal graphs, and we hope that
this new tool will open new perspectives. An exciting research direction is to
construct universal graphs for subclasses of graphs. For instance, it is known
that solving parity games over graphs of bounded tree width or clique width is
polynomial [Obd03, Obd07]. Are there universal graphs of polynomial size for
these classes of graphs? A step in this direction was made recently by
Daviaud, Jurdziński, and Thejaswini [DJT20]: revisiting the register games
algorithm [Leh18, LB20], they introduced a new parameter called the Strahler
number and constructed universal trees for bounded Strahler numbers.

Another promising direction is to extend the use of universal graphs from
games to automata. The first brick in the wall was thrown by Daviaud,
Jurdziński, and Lehtinen [DJL19], who showed that universal trees can be used
to improve constructions for alternating automata over infinite words.

## References

  * [BC18] Mikołaj Bojańczyk and Wojciech Czerwiński.  An automata toolbox, February 2018.  https://www.mimuw.edu.pl/~bojan/papers/toolbox-reduced-feb6.pdf.
  * [BCD+11] Lubos Brim, Jakub Chaloupka, Laurent Doyen, Raffaella Gentilini, and Jean-François Raskin.  Faster algorithms for mean-payoff games.  Formal Methods in System Design, 38(2):97–118, 2011.
  * [CDF+18] Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdziński, Ranko Lazić, and Paweł Parys.  Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games.  CoRR, abs/1807.10546, 2018.
  * [CDHS18] Krishnendu Chatterjee, Wolfgang Dvorák, Monika Henzinger, and Alexander Svozil.  Quasipolynomial set-based symbolic algorithms for parity games.  In LPAR, pages 233–253, 2018.
  * [CF16] Thomas Colcombet and Nathanaël Fijalkow.  The bridge between regular cost functions and $\omega$-regular languages.  In ICALP, pages 126:1–126:13, 2016.
  * [CF18] Thomas Colcombet and Nathanaël Fijalkow.  Parity games and universal graphs.  CoRR, abs/1810.05106, 2018.
  * [CF19] Thomas Colcombet and Nathanaël Fijalkow.  Universal graphs and good for games automata: New tools for infinite duration games.  In FoSSaCS, pages 1–26, 2019.
  * [CHJ05] Krishnendu Chatterjee, Thomas A. Henzinger, and Marcin Jurdziński.  Mean-payoff parity games.  In LICS, pages 178–187, 2005.
  * [CJK+17] Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.  Deciding parity games in quasipolynomial time.  In STOC, pages 252–263, 2017.
  * [Col09] Thomas Colcombet.  The theory of stabilisation monoids and regular cost functions.  In ICALP, 2009.
  * [CR17] Carlo Comin and Romeo Rizzi.  Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games.  Algorithmica, 77(4):995–1021, 2017.
  * [DJL18] Laure Daviaud, Marcin Jurdziński, and Ranko Lazić.  A pseudo-quasi-polynomial algorithm for mean-payoff parity games.  In LICS, pages 325–334, 2018.
  * [DJL19] Laure Daviaud, Marcin Jurdziński, and Karoliina Lehtinen.  Alternating weak automata from universal trees.  In Wan J. Fokkink and Rob van Glabbeek, editors, CONCUR, volume 140 of LIPIcs, pages 18:1–18:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [DJT20] Laure Daviaud, Marcin Jurdziński, and K. S. Thejaswini.  The strahler number of a parity game.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, ICALP, volume 168 of LIPIcs, pages 123:1–123:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [DKZ19] Dani Dorfman, Haim Kaplan, and Uri Zwick.  A faster deterministic exponential time algorithm for energy games and mean payoff games.  In ICALP, pages 114:1–114:14, 2019.
  * [EJ91] E. Allen Emerson and Charanjit S. Jutla.  Tree automata, $\mu$-calculus and determinacy.  In FOCS, pages 368–377. IEEE Computer Society, 1991.
  * [EM79] Andrzej Ehrenfeucht and Jan Mycielski.  Positional strategies for mean payoff games.  International Journal of Game Theory, 109(8):109–113, 1979.
  * [FGO20] Nathanaël Fijalkow, Paweł Gawrychowski, and Pierre Ohlmann.  Value iteration using universal graphs and the complexity of mean payoff games.  In MFCS, volume 170 of LIPIcs, pages 34:1–34:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [Fij18] Nathanaël Fijalkow.  An optimal value iteration algorithm for parity games.  CoRR, abs/1801.09618, 2018.
  * [FJS+17] John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, and Dominik Wojtczak.  An ordered approach to solving parity games in quasi polynomial time and quasi linear space.  In SPIN, pages 112–121, 2017.
  * [FT87] András Frank and Éva Tardos.  An application of simultaneous diophantine approximation in combinatorial optimization.  Combinatorica, 7(1):49–65, 1987.
  * [FZ14] Nathanaël Fijalkow and Martin Zimmermann.  Parity and streett games with costs.  Logical Methods in Computer Science, 10(2), 2014.
  * [GKK88] Vladimir A. Gurvich, Aleksander V. Karzanov, and Leonid G. Khachiyan.  Cyclic games and an algorithm to find minimax cycle means in directed graphs.  USSR Computational Mathematics and Mathematical Physics, 28:85–91, 1988.
  * [HP06] Thomas A. Henzinger and Nir Piterman.  Solving games without determinization.  In CSL, pages 395–410, 2006.
  * [JL17] Marcin Jurdziński and Ranko Lazić.  Succinct progress measures for solving parity games.  In LICS, pages 1–9, 2017.
  * [JM20] Marcin Jurdziński and Rémi Morvan.  A universal attractor decomposition algorithm for parity games.  CoRR, abs/2001.04333, 2020.
  * [JMOT20] Marcin Jurdziński, Rémi Morvan, Pierre Ohlmann, and K. S. Thejaswini.  A symmetric attractor-decomposition lifting algorithm for parity games.  CoRR, abs/2010.08288, 2020.
  * [Jur00] Marcin Jurdziński.  Small progress measures for solving parity games.  In STACS, pages 290–301, 2000.
  * [Kal92] Gil Kalai.  A subexponential randomized simplex algorithm (extended abstract).  In STOC, pages 475–482, 1992.
  * [Kal97] Gil Kalai.  Linear programming, the simplex algorithm and simple polytopes.  Mathematical Programming, 79:217–233, 1997.
  * [LB20] Karoliina Lehtinen and Udi Boker.  Register games.  Logical Methods in Computer Science, 16(2), 2020.
  * [Leh18] Karoliina Lehtinen.  A modal-$\mu$ perspective on solving parity games in quasi-polynomial time.  In LICS, pages 639–648, 2018.
  * [LP07] Y.M. Lifshits and D.S. Pavlov.  Potential theory for mean payoff games.  Journal of Mathematical Sciences, 145:4967–4974, 2007.
  * [LSW19] Karoliina Lehtinen, Sven Schewe, and Dominik Wojtczak.  Improving the complexity of Parys’ recursive algorithm.  CoRR, abs/1904.11810, 2019.
  * [McN93] Robert McNaughton.  Infinite games played on finite graphs.  Annals of Pure and Applied Logic, 65(2):149–184, 1993.
  * [Mos91] Andrzej W. Mostowski.  Games with forbidden positions.  Technical Report 78, University of Gdansk, 1991.
  * [MSW96] Jiří Matoušek, Micha Sharir, and Emo Welzl.  A subexponential bound for linear programming.  Algorithmica, 16(4/5):498–516, 1996.
  * [Obd03] Jan Obdrzálek.  Fast mu-calculus model checking when tree-width is bounded.  In Warren A. Hunt Jr. and Fabio Somenzi, editors, CAV, volume 2725 of Lecture Notes in Computer Science, pages 80–92. Springer, 2003\.
  * [Obd07] Jan Obdrzálek.  Clique-width and parity games.  In Jacques Duparc and Thomas A. Henzinger, editors, CSL, volume 4646 of Lecture Notes in Computer Science, pages 54–68. Springer, 2007\.
  * [Par19] Paweł Parys.  Parity games: Zielonka’s algorithm in quasi-polynomial time.  In MFCS, pages 10:1–10:13, 2019.
  * [Par20] Paweł Parys.  Parity games: Another view on lehtinen’s algorithm.  In CSL, pages 32:1–32:15, 2020.
  * [SWZ19] Sven Schewe, Alexander Weinert, and Martin Zimmermann.  Parity games with weights.  Logical Methods in Computer Science, 15(3), 2019.
  * [VCD+15] Yaron Velner, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Alexander M. Rabinovich, and Jean-François Raskin.  The complexity of multi-mean-payoff and multi-energy games.  Information and Computation, 241:177–196, 2015.
  * [Zie98] Wiesław Zielonka.  Infinite games on finitely coloured graphs with applications to automata on infinite trees.  Theoretical Computer Science, 200(1-2):135–183, 1998.
  * [ZP96] Uri Zwick and Mike Paterson.  The complexity of mean payoff games on graphs.  Theoretical Computer Science, 158(1-2):343–359, 1996.

##  Appendix A Analysis of the function $F$

Define $F(p,h)=f(2^{p},h)$ for $p\geq 0$ and $h\geq 1$. Then we have

$\begin{array}[]{lll}F(p,h)&\leq&F(p,h-1)+2F(p-1,h),\\\ F(p,1)&=&2^{p},\\\
F(0,h)&=&1.\end{array}$

To obtain an upper bound on $F$ we define $\overline{F}$ by

$\begin{array}[]{lll}\overline{F}(p,h)&=&\overline{F}(p,h-1)+2\overline{F}(p-1,h),\\\
\overline{F}(p,1)&=&2^{p},\\\ \overline{F}(0,h)&=&1,\end{array}$

so that $F(p,h)\leq\overline{F}(p,h)$. Define the bivariate generating
function

$\mathcal{F}(x,y)=\sum_{p\geq 0,h\geq 1}\overline{F}(p,h)x^{p}y^{h}.$

Plugging the inductive equalities we obtain

$\mathcal{F}(x,y)=\frac{y}{1-2x-y},$

from which we extract that $\overline{F}(p,h)=2^{p}\binom{p+h-1}{p}$, implying
$F(p,h)\leq 2^{p}\binom{p+h-1}{p}$. Putting everything together we obtain

$f(n,h)\leq
2^{\lceil\log(n)\rceil}\cdot\binom{\lceil\log(n)\rceil+h-1}{\lceil\log(n)\rceil}.$

##  Appendix B Analysis of the function $G$

Define $G(p,h)=g(2^{p},h)$ for $p\geq 0$ and $h\geq 1$. Then we have

$\begin{array}[]{lll}G(p,h)&\geq&\sum_{k=0}^{p}G(p-k,h-1),\\\
G(p,1)&\geq&1,\\\ G(0,h)&=&1.\end{array}$

To obtain a lower bound on $G$ we proceed similarly as for $F$. We define
$\overline{G}$ by

$\begin{array}[]{lll}\overline{G}(p,h)&=&\overline{G}(p,h-1)+\overline{G}(p-1,h),\\\
\overline{G}(p,1)&=&1,\\\ \overline{G}(0,h)&=&1,\end{array}$

so that $G(p,h)\geq\overline{G}(p,h)$. We verify by induction that
$\overline{G}(p,h)=\binom{p+h-1}{p}$, which follows from the identity

$\binom{p+h-1}{p}=\binom{p+h-2}{p}+\binom{p+h-2}{p-1}.$

This implies that $G(p,h)\geq\binom{p+h-1}{p}$. Putting everything together we
obtain

$g(n,h)\geq\binom{\lfloor\log(n)\rfloor+h-1}{\lfloor\log(n)\rfloor}.$

##  Appendix C Pseudo-code for linear time algorithm solving safety games

Data: A safety game $\mathcal{G}=(V,E)$

Function  _Solve(_$\mathcal{G}$_)_:

$X\leftarrow V$

$R\leftarrow\\{v\in\text{V}_{\text{Eve}}\mid v\text{ is a sink}\\}$

for  _$v\in\text{V}_{\text{Eve}}$_ do

$\texttt{Count}(v)\leftarrow$ number of edges outgoing from $v$

while  _$R\neq\emptyset$_ do

$R\leftarrow\textnormal{{Upd}}(X,R,\texttt{Count})$

return _$X$_

Function  _Upd(_$X,R,\texttt{Count}$_)_:

$R^{\prime}\leftarrow\emptyset$

for  _edge $e=(v,v^{\prime})$ from $X$ to $R$_ do

if  _$v\in\text{V}_{\text{Adam}}$_ then

$R^{\prime}\leftarrow R^{\prime}\cup\\{v\\}$

else

$\texttt{Count}(v)=\texttt{Count}(v)-1$

if  _$\texttt{Count}(v)=0$_ then

$R^{\prime}\leftarrow R^{\prime}\cup\\{v\\}$

$X\leftarrow X\setminus R^{\prime}$

return _$R^{\prime}$_

Algorithm 1 A linear time algorithm for solving safety games. Note that the
procedure Upd, which computes $X_{i+1}$ and $R_{i}$ from $X_{i}$ and
$R_{i-1}$, updates $X$ and Count in place.

## Pseudo-code for generic value iteration algorithm

Data: A game $\mathcal{G}=(V,E)$ and a linear graph $\mathcal{A}=(Q,\Delta)$.

Function  _Solve(_$\mathcal{G},\mathcal{A}$_)_:

for  _$v\in V$_ do

$\theta(v)\leftarrow\min Q$

for  _$v\in\text{V}_{\text{Eve}}$_ do

$\texttt{Count}(v)\leftarrow|\\{(v,c,v^{\prime})\in
E\mid\theta(v^{\prime})\leq\delta(\theta(v),c)\\}|$

$\mathrm{Inv}\leftarrow\\{v\in\text{V}_{\text{Eve}}\mid\texttt{Count}(v)=0\\}\cup\\{v\in\text{V}_{\text{Adam}}\mid\exists(v,c,v^{\prime})\in
E,\theta(v^{\prime})>\delta(\theta(v),c)\\}$

while  _$\mathrm{Inv}\neq\emptyset$_ do

$\mathrm{Inv}\leftarrow\textnormal{{Upd}}(\theta,\mathrm{Inv},\texttt{Count})$

return _$\\{v\in V\mid\theta(v) <\top\\}$_

Function  _Upd(_$\theta,\mathrm{Inv},\texttt{Count}$_)_:

$\mathrm{Inv}^{\prime}\leftarrow\emptyset$

for  _$v\in\mathrm{Inv}$_ do

if  _$v\in\text{V}_{\text{Eve}}$_ then

$\theta^{\prime}(v)\leftarrow\min\\{\rho(\theta(v^{\prime}),c),(v,c,v^{\prime})\in
E\\}$

else

$\theta^{\prime}(v)\leftarrow\max\\{\rho(\theta(v^{\prime}),c),(v,c,v^{\prime})\in
E\\}$

for  _$e=(u,c,v)\in E$ such that
$\theta(v)\leq\delta(\theta(u),c)<\theta^{\prime}(v)$_ do

if  _$u\in\text{V}_{\text{Adam}}$_ then

$\mathrm{Inv}^{\prime}\leftarrow\mathrm{Inv}^{\prime}\cup\\{u\\}$

else

$\texttt{Count}(u)\leftarrow\texttt{Count}(u)-1$

if  _$\texttt{Count}(u)=0$_ then

$\mathrm{Inv}^{\prime}\leftarrow\mathrm{Inv}^{\prime}\cup\\{u\\}$

$\theta(v)\leftarrow\theta^{\prime}(v)$

if  _$v\in\text{V}_{\text{Eve}}$_ then

$\texttt{Count}(v)\leftarrow|\\{(v,c,v^{\prime})\in
E\mid\theta(v^{\prime})\leq\delta(\theta(v),c)\\}|$

return _$\mathrm{Inv}^{\prime}$_

Algorithm 2 A generic value iteration algorithm obtained by solving the safety
game $\mathcal{G}\triangleright\mathcal{A}$ when $\mathcal{A}$ is linear.


# The Schwarzschild Black Hole from Perturbation Theory to all Orders

Poul H. Damgaard<EMAIL_ADDRESS>Niels Bohr International Academy, The Niels
Bohr Institute, Blegdamsvej 17, DK-2100 Copenhagen Ø, DENMARK  Kanghoon Lee
<EMAIL_ADDRESS>Asia Pacific Center for Theoretical Physics, Postech,
Pohang 37673, Korea  Department of Physics, Postech, Pohang 37673, Korea

###### Abstract

Applying the quantum field theoretic perturbiner approach to Einstein gravity,
we compute the metric of a Schwarzschild black hole order by order in
perturbation theory. Using recursion, this calculation can be carried out in
de Donder gauge to all orders in Newton’s constant. The result is a geometric
series which is convergent outside a disk of finite radius, and it agrees
within its region of convergence with the known de Donder gauge metric of a
Schwarzschild black hole. It thus provides a first all-order perturbative
computation in Einstein gravity with a matter source, and this series
converges to the known non-perturbative expression in the expected range of
convergence.

###### pacs:

04.60.-m, 04.62.+v, 04.80.Cc

##  I Introduction

The recent surge of interest in gravitational-wave physics associated with the
merging of two black holes has led to a number of powerful new analytical
approaches to Einstein gravity. This has put the post-Minkowskian expansion,
the perturbative evaluation of physical observables as a power series in
Newton’s constant $G$ around flat Minkowski space, into focus. Because of its
close connection to the classical limit of quantum field theoretical
scattering amplitudes in gravity Bjerrum-Bohr:2018xdl ; Cheung:2018wkq ;
Kosower:2018adc ; Cristofoli:2019neg , rapid progress has led to the exact
analytical evaluation of physical observables up to (and including) fourth
order in the perturbative expansion in the coupling constant $G$ Bern:2019nnu
; Bern:2019crd ; Kalin:2019rwq ; Bjerrum-Bohr:2019kec ; Damour:2019lcq ;
DiVecchia:2020ymx ; Damour:2020tta ; DiVecchia:2021ndb ; DiVecchia:2021bdo ;
Herrmann:2021tct ; Bjerrum-Bohr:2021vuf ; Bjerrum-Bohr:2021din ;
Damgaard:2021ipf ; Brandhuber:2021eyq ; Brandhuber:2021bsf ; Kalin:2020mvi ;
Kalin:2020fhe ; Mogull:2020sak ; Jakobsen:2021smu ; Mougiakakos:2021ckm ;
Riva:2021vnj ; Bern:2021dqo ; Dlapa:2021npj ; Bern:2021yeh ; Adamo:2022ooq ;
Dlapa:2023hsl ; Jakobsen:2023ndj ; Damgaard:2023vnx ; Damgaard:2023ttc ;
Jakobsen:2023hig ; DiVecchia:2023frv ; Driesse:2024xad , also in some cases
including low orders in the spin multipole expansion. Such a successful
program, which has already reached fifth order in the expansion
Driesse:2024xad , prompts the question as to whether the perturbative series
expansion in Einstein gravity is convergent. One of the first examinations of
this issue dates back to ref. Christodoulou ; see also ref. Damour:1990rm .
Here we shall investigate the question of convergence of the post-Minkowskian
expansion in its simplest possible setting: that of vacuum solutions to the
Einstein equations in the presence of a point-like source. The surprising
difficulty in deriving the metric perturbatively in this context was noted
first by Florides and Synge Synge . Low-order perturbative calculations of the
gravitational metric of such a non-spinning black hole have since been pursued
by means of several different quantum field theoretical formalisms Duff:1973zz
; Bjerrum-Bohr:2002fji ; Goldberger:2004jt ; Neill:2013wsa ;
KoemansCollado:2018hss ; Jakobsen:2020ksu ; Mougiakakos:2020laz ;
DOnofrio:2022cvn . Eventually, and typically at quite low orders, they run
into a problem posed by the complexity of the perturbatively expanded
Einstein-Hilbert action. This pushes the calculations to prohibitively
complicated levels beyond the first few orders. In the amplitude-based
approach to general relativity this problem is partly circumvented by the use
of on-shell unitarity methods. Such techniques are, however, not immediately
amenable to the off-shell situation needed for the calculation of the
gravitational metric itself. Instead, as we shall demonstrate below, a
judicious choice of variables, combined with off-shell recursion relations of
the current as well as relevant loop integrals, can lead to drastic
simplifications.

Our tool shall be the perturbiner approach to quantum field theory
Rosly:1996vr ; Rosly:1997ap ; Mafra:2016ltu ; Mizera:2018jbh ; Gomez:2021shh ;
Gomez:2022dzk ; Cho:2021nim ; Lee:2022aiu ; Cho:2022faq ; Adamo:2023cfp ;
Lee:2023zuu ; Cho:2023kux ; Tao:2023yxy . This method provides an alternative
path towards scattering amplitudes and in the case of the gravitational field
yields an analog of Berends-Giele Berends:1987me  off-shell recursion
relations for gravity. The perturbiner method combines very well with the
post-Minkowskian expansion of gravity Cho:2021nim ; Lee:2022aiu ; Cho:2022faq
; Adamo:2023cfp ; Lee:2023zuu ; Cho:2023kux , leading to the pertinent two-
body scattering amplitudes in a manner that is closely linked to the classical
equations of motion or, at loop level, the Schwinger-Dyson equations.
Combining the perturbiner method with good variables for the gravitational
field is the first key ingredient towards obtaining an all-order result in
perturbation theory. This still leaves us with the problem that the Einstein-
Hilbert action expanded in coupling $G$ becomes immensely complicated beyond
lowest orders. An important observation is that the complexity arises to a
large degree from iterations of lower-point vertices and this can be used to
advantage, leading us to the second key ingredient of our approach which is to
expand the Einstein-Hilbert action perturbatively in a doubled set of fields.
The required constraint among the two sets of fields is imposed afterward.
Finally, we will need to evaluate a series of momentum-space integrals. Our
third key observation is that these integrals reduce to generalized 1-loop
bubble diagrams. They are then all solvable by iteration. The various new
recursive identities that have been discovered in the theory of scattering
amplitudes rely on the observation that each new order can be built up from
combinations of lower-order terms. This is also the mechanism behind the
present calculation and it illustrates how modern quantum field theory methods
can provide a surprising new avenue to general relativity.

##  II The metric

The Schwarzschild metric in harmonic gauge is given by

$\displaystyle\mathrm{d}s^{2}$
$\displaystyle=-N\mathrm{d}t^{2}+\Bigg{[}F\delta^{ij}+\frac{G^{2}M^{2}}{N}\frac{x^{i}x^{j}}{r^{4}}\Bigg{]}\mathrm{d}x^{i}\mathrm{d}x^{j}\,,$
(1)

where $r^{2}=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}$, and

$N(r)=\frac{r-GM}{r+GM}\,,\qquad F(r)=\frac{(r+GM)^{2}}{r^{2}}\,.$ (2)

We choose to work with Landau-Lifshitz variables and expand perturbatively
around flat Minkowski space as follows:

$\mathfrak{g}^{\mu\nu}\equiv\sqrt{-g}g^{\mu\nu}=\eta^{\mu\nu}-h^{\mu\nu}\,.$
(3)

With this choice of variables, the fluctuation field $h^{\mu\nu}$ reads

$h^{00}=-1+\frac{\left(r+GM\right)^{3}}{r^{2}\left(r-GM\right)}~{}~{},~{}~{}~{}h^{ij}=\frac{G^{2}M^{2}x^{i}x^{j}}{r^{4}}\,.$
(4)

Expanding $h^{00}$ as a Laurent series around 1 we get

$\displaystyle h^{00}$ $\displaystyle=$ $\displaystyle
8\left(1-\frac{GM}{r}\right)^{-1}-8-\frac{4GM}{r}-\frac{G^{2}M^{2}}{r^{2}}$
(5) $\displaystyle=$
$\displaystyle\frac{4GM}{r}+\frac{7G^{2}M^{2}}{r^{2}}+\frac{8G^{3}M^{3}}{r^{3}}\ldots$
(6)

Except for the few low-order corrections $h^{00}$ is thus a geometric series
in $GM/r$ with fixed coefficient 8, while $h^{ij}$ truncates at second order.
The fluctuation field $h^{\mu\nu}$ satisfies the de Donder gauge condition
$\partial_{\mu}(\sqrt{-g}g^{\mu\nu})=\partial_{\mu}h^{\mu\nu}=0$ which is
equivalent to the harmonic gauge condition in these variables.

##  III The Perturbiner method

We now set up the post-Minkowskian perturbative expansion for the
Schwarzschild black hole metric as defined in eq. (3). We do this by
generalizing the usual perturbiner method for scattering amplitudes to
solutions of the perturbative Einstein equations. Specifically, we wish to
generate the perturbative vacuum solution of Einstein gravity for a point-like
source at the origin, corresponding to a Schwarzschild black hole.

The action is thus given by

$S=\int\mathrm{d}^{4}x\bigg{[}\frac{1}{2\kappa^{2}}\sqrt{-g}R+\frac{1}{2}j_{\mu\nu}(x)g^{\mu\nu}(x)\bigg{]}\,,$
(7)

where $R$ is the Ricci scalar and the source $j_{\mu\nu}(x)$ is

$j_{\mu\nu}(x)=Mv_{\mu}v_{\nu}\delta^{3}(\boldsymbol{x})\,,\qquad
v_{\mu}=(-1,0,0,0)\,.$ (8)

Here $\boldsymbol{x}$ denotes the position 3-vector. Let us consider the one-
point function of $h^{\mu\nu}_{x}\equiv h^{\mu\nu}(x)$ in the presence of the
source $j_{\mu\nu}$,

$\mathsf{h}^{\mu\nu}_{x}=\left\langle
0|h^{\mu\nu}_{x}|0\right\rangle_{j}=\frac{\delta W[j]}{\delta
j_{x}^{\mu\nu}}\,,$ (9)

where $W[j_{\mu\nu}]$ is the generating functional

$e^{W[j_{\mu\nu}]}\equiv\int\mathcal{D}h^{\mu\nu}\exp\left[\frac{i}{\hbar}S[h^{\mu\nu},j_{\mu\nu}]\right]\,.$
(10)

Note that $\mathsf{h}^{\mu\nu}_{x}$ satisfies the classical equations of
motion at tree level. Since we are considering a time-independent solution, we
restrict $\mathsf{h}^{\mu\nu}(x)=\mathsf{h}^{\mu\nu}(\boldsymbol{x})$.

Expanding the generating functional in powers of $j_{\mu\nu}$,
$\mathsf{h}^{\mu\nu}_{x}$ is given in terms of connected correlation
functions,

$\displaystyle\mathsf{h}^{\mu\nu}_{\boldsymbol{x}}$
$\displaystyle=\sum_{n=1}^{\infty}\frac{1}{n!}\int_{y_{1},\cdots,y_{n}}\\!\\!\\!\\!\big{\langle}0\big{|}T\big{[}h_{x}^{\mu\nu}h_{y_{1}}^{\kappa_{1}\lambda_{1}}\cdots
h_{y_{n}}^{\kappa_{n}\lambda_{n}}\big{]}\big{|}0\big{\rangle}_{c}$ (11)
$\displaystyle\quad\times\frac{ij_{y_{1}}^{\kappa_{1}\lambda_{1}}}{\hbar}\cdots\frac{ij_{y_{n}}^{\kappa_{n}\lambda_{n}}}{\hbar}\,,$

where

$\int_{x,y\cdots}=\int\mathrm{d}^{d}x\mathrm{d}^{d}y\cdots\text{ and
}\int_{p,q,\cdots}=\int\frac{\mathrm{d}^{d}p}{(2\pi)^{d}}\frac{\mathrm{d}^{d}q}{(2\pi)^{d}}\cdots\,.$
(12)

Hereafter, we will ignore the position of indices while keeping the summation
convention for repeated indices.

Next, we substitute $j_{\mu\nu}$ as defined in (8). It is useful to represent
the delta function as

$j^{\mu\nu}_{\boldsymbol{x}}=Mv^{\mu}v^{\nu}\int_{\boldsymbol{\ell}}e^{-i\boldsymbol{\ell}\cdot\boldsymbol{x}}\,.$
(13)

Then $\mathsf{h}^{\mu\nu}_{x}$ reduces to

$\displaystyle\mathsf{h}^{\mu\nu}(\boldsymbol{x})$
$\displaystyle=\sum_{n=1}^{\infty}\frac{1}{n!}\int_{\boldsymbol{\ell}_{1},\boldsymbol{\ell}_{2},\cdots,\boldsymbol{\ell}_{n}}J^{\mu\nu}_{\boldsymbol{\ell}_{1}\boldsymbol{\ell}_{2}\cdots\boldsymbol{\ell}_{n}}e^{-i\boldsymbol{\ell}_{12\cdots
n}\cdot\boldsymbol{x}}\,,$ (14)

where

$J^{\mu\nu}_{\boldsymbol{\ell}_{1}\boldsymbol{\ell}_{2}\cdots\boldsymbol{\ell}_{n}}=\left(\frac{iM}{\hbar}\right)^{n}\big{\langle}0\big{|}T\big{[}\tilde{h}_{-\boldsymbol{\ell}_{12\cdots
n}}^{\mu\nu}\tilde{h}_{\boldsymbol{\ell}_{1}}^{00}\cdots\tilde{h}_{\boldsymbol{\ell}_{n}}^{00}\big{]}\big{|}0\big{\rangle}_{c}\,,$
(15)

and $\boldsymbol{\ell}_{12\cdots
n}=\boldsymbol{\ell}_{1}+\boldsymbol{\ell}_{2}+\cdots+\boldsymbol{\ell}_{n}$.
Here $\tilde{h}_{\ell}^{\mu\nu}$ is the Fourier transform of $h_{x}^{\mu\nu}$.
It is convenient to shift the loop momentum
$\boldsymbol{\ell}_{1}\to-\boldsymbol{\ell}_{12\cdots n}$ so that

$\mathsf{h}^{\mu\nu}(\boldsymbol{x})=\sum_{n=1}^{\infty}\int_{\boldsymbol{\ell}_{1}}e^{i\boldsymbol{\ell}_{1}\cdot\boldsymbol{x}}J^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}_{1}}\,,$
(16)

where

$J^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}_{1}}=\int_{\boldsymbol{\ell}_{2},\cdots,\boldsymbol{\ell}_{n}}\frac{1}{(n-1)!}J^{\mu\nu}_{-\boldsymbol{\ell}_{12\cdots
n}\boldsymbol{\ell}_{2}\cdots\boldsymbol{\ell}_{n}}\,.$ (17)

We denote the number of loop momenta of an off-shell current by its ‘rank’.
For instance, the rank of $J^{\mu\nu}_{\ell_{1}\cdots\ell_{n}}$ is $n$. We
then expand $\mathsf{h}^{\mu\nu}$ according to this rank, $i.e.$

$\mathsf{h}^{\mu\nu}=\sum_{n=0}^{\infty}G^{n}\mathsf{h}^{\mu\nu}_{{\scriptscriptstyle(n)}}~{}~{},~{}~{}~{}\mathsf{h}^{\mu\nu}_{{\scriptscriptstyle(n)}}\equiv\int_{\boldsymbol{\ell}}J^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{{\ell}}}e^{i\boldsymbol{\ell}\cdot\boldsymbol{x}}\,.$
(18)

We now proceed to organize the perturbative expansion of the Einstein-Hilbert
action. Because $\mathsf{h}^{\mu\nu}$ satisfies the classical equations of
motion at tree level, we substitute (3) into (7) and expand the equation of
motion in powers of $G$,

$\Box\mathsf{h}^{\mu\nu}=-2j^{\mu\nu}-\sum_{n=1}^{\infty}\tau^{\mu\nu}_{[n]}~{},$
(19)

where the $\tau^{\mu\nu}_{[n]}$’s arise in the well-known manner from
gravitational self-interactions. This expansion is by construction also
ordering the number of fields $\mathsf{h}^{\mu\nu}$ so that
$\tau^{\mu\nu}_{[n]}$ contains $(n+1)$ fields. The off-shell recursion
relations are now obtained by substituting the perturbiner expansion. The
initial condition of the recursion is given by the rank-1 current,

$\Delta\mathsf{h}^{\mu\nu}_{{\scriptscriptstyle(1)}}=-2j^{\mu\nu}=-2Mv^{\mu}v^{\nu}\int_{\boldsymbol{k}}e^{i\boldsymbol{k}\cdot\boldsymbol{x}}\,,$
(20)

where $\Delta$ is the Laplacian. Substituting the perturbiner expansion (18)
for $\mathsf{h}^{\mu\nu}_{{\scriptscriptstyle(1)}}$ this provides us with the
initial condition for the off-shell recursion relation

$J^{\mu\nu}_{{\scriptscriptstyle(1)}|\boldsymbol{\ell}}=\frac{16\pi
M}{|\boldsymbol{\ell}|^{2}}v^{\mu}v^{\nu}\,,$ (21)

or

$J^{00}_{{\scriptscriptstyle(1)}|\boldsymbol{\ell}}=\frac{16\pi
M}{|\boldsymbol{\ell}|^{2}}\,,\qquad
J^{0i}_{{\scriptscriptstyle(1)}|\boldsymbol{\ell}}=0\,,\qquad
J^{ij}_{{\scriptscriptstyle(1)}|\boldsymbol{\ell}}=0\,.$ (22)

We now proceed to rank-2 level. According to the initial condition in (22),
the only nonvanishing component of
$\mathsf{h}_{{\scriptscriptstyle(1)}}^{\mu\nu}$ is
$\mathsf{h}_{{\scriptscriptstyle(1)}}^{00}$. Inserting the equations of motion
to this order, we get the off-shell recursion relations at rank-2 from the
perturbiner expansion,

$\displaystyle J^{00}_{{\scriptscriptstyle(2)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=\frac{1}{|\boldsymbol{\ell}_{1}|^{2}}\int_{\boldsymbol{\ell_{2}}}\bigg{[}\frac{5}{4}|\boldsymbol{\ell}_{2}|^{2}-\frac{7}{8}\boldsymbol{\ell}_{12}\cdot\boldsymbol{\ell}_{2}\bigg{]}J^{00}_{{\scriptscriptstyle(1)}|-\boldsymbol{\ell}_{12}}J^{00}_{{\scriptscriptstyle(1)}|\boldsymbol{\ell}_{2}}\,,$
(23) $\displaystyle J^{ij}_{{\scriptscriptstyle(2)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=\frac{1}{|\boldsymbol{\ell}_{1}|^{2}}\int_{\boldsymbol{\ell_{2}}}\bigg{[}\frac{\ell^{(i}_{12}\ell^{j)}_{2}}{4}-\frac{\delta^{ij}\boldsymbol{\ell}_{12}\cdot\boldsymbol{\ell}_{2}}{8}\bigg{]}J^{00}_{{\scriptscriptstyle(1)}|-\boldsymbol{\ell}_{12}}J^{00}_{{\scriptscriptstyle(1)}|\boldsymbol{\ell}_{2}}\,,$

which shows how $J^{ij}$-components build up from the recursion. Performing
the integrals, we get

$\displaystyle
J^{00}_{{\scriptscriptstyle(2)}|\boldsymbol{\ell}}=\frac{14\pi^{2}M^{2}}{|\boldsymbol{\ell}|},~{}~{}J^{ij}_{{\scriptscriptstyle(2)}|\boldsymbol{\ell}}=\pi^{2}M^{2}\left[\frac{\delta^{ij}}{|\boldsymbol{\ell}|}-\frac{\ell^{i}\ell^{j}}{|\boldsymbol{\ell}|^{3}}\right]\,.$
(24)

Computational tedium would seem to prevent us from proceeding to rank-3 level
(and beyond). However, we do need the explicit evaluation for rank-3 in order
to establish an all-order result by induction. This is the first level at
which we need to regularize the integrals and we choose to work with
dimensional regularization by going to $d=3-2\epsilon$ dimensions at
intermediate steps. We first find
$\mathsf{h}^{\mu\nu}_{{\scriptscriptstyle(3)}}$ from the explicit forms of
$\tau^{\mu\nu}_{[1]}$ and $\tau^{\mu\nu}_{[2]}$ by using the expansion of
$\mathsf{h}^{\mu\nu}$ in (18). This gives

$\displaystyle J^{00}_{{\scriptscriptstyle(3)}|\boldsymbol{\ell}}$
$\displaystyle=$
$\displaystyle\frac{M^{3}\pi^{\epsilon+\frac{3}{2}}}{2^{-4\epsilon-1}|\boldsymbol{\ell}|^{2\epsilon}}\frac{(\epsilon(2\epsilon+5)+6)\Gamma[1-2\epsilon]}{\Gamma\left[\frac{5}{2}-2\epsilon\right]}\Gamma[\epsilon]$
(25) $\displaystyle J^{ij}_{{\scriptscriptstyle(3)}|\boldsymbol{\ell}}$
$\displaystyle=$
$\displaystyle\frac{M^{3}\pi^{\epsilon+\frac{3}{2}}}{4^{-2\epsilon-1}|\boldsymbol{\ell}|^{2\epsilon}}\frac{\delta^{ij}\epsilon\Gamma[3-2\epsilon]\Gamma[\epsilon-1]}{(2\epsilon-1)\Gamma[\frac{5}{2}-2\epsilon]}\,.$
(26)

Fourier-transforming all of these results according to (18) and going to $d=3$
dimensions, we obtain

$\mathsf{h}^{\mu\nu}_{{\scriptscriptstyle(1)}}=\frac{4M}{r}v^{\mu}v^{\nu}\,,$
(27)

so that

$\mathsf{h}^{00}_{{\scriptscriptstyle(1)}}=\frac{4M}{r}\,,\qquad\mathsf{h}^{0i}_{{\scriptscriptstyle(1)}}=\mathsf{h}^{ij}_{{\scriptscriptstyle(1)}}=0\,.$
(28)

at rank-1 level. At rank-2,

$\displaystyle\mathsf{h}^{00}_{{\scriptscriptstyle(2)}}$
$\displaystyle=\int_{\boldsymbol{\ell}}e^{i\boldsymbol{\ell}\cdot\boldsymbol{x}}J^{00}_{{\scriptscriptstyle(2)}|\boldsymbol{\ell}}=\frac{7M^{2}}{r^{2}}\,,$
(29) $\displaystyle\mathsf{h}^{ij}_{{\scriptscriptstyle(2)}}$
$\displaystyle=\int_{\boldsymbol{\ell}}e^{i\boldsymbol{\ell}\cdot\boldsymbol{x}}J^{ij}_{{\scriptscriptstyle(2)}|\boldsymbol{\ell}}=\frac{M^{2}x^{i}x^{j}}{r^{4}}\,.$

while at rank-3 we get

$\displaystyle\mathsf{h}^{00}_{{\scriptscriptstyle(3)}}=\frac{8M^{3}}{r^{3}}\,,\qquad\mathsf{h}^{ij}_{{\scriptscriptstyle(3)}}=0\,.$
(30)

These results match the metric of (3) to ${\mathcal{O}}(G^{3})$.

##  IV Iterated loop integrals

As an intermediate step towards extending the above analysis to all orders we
now demonstrate that the loop integrals to any order are iterated one-loop
bubble integrals, and hence solvable recursively. We use the fact that a
generic one-loop bubble integral is of the form

$\int_{\boldsymbol{\ell}}\frac{\ell^{\rho_{1}}\cdots\ell^{\rho_{m}}}{|\boldsymbol{\ell}|^{\alpha_{1}}|\boldsymbol{\ell}+\boldsymbol{p}|^{\alpha_{2}}}=\frac{M^{\rho_{1}\cdots\rho_{m}}[\boldsymbol{p}]}{|\boldsymbol{p}|^{\beta}}\,,$
(31)

and apply it recursively to integrals of the perturbiner method,

$\displaystyle\mathcal{J}^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}_{1}}=$
$\displaystyle\int_{\boldsymbol{\ell}_{2},\cdots,\boldsymbol{\ell}_{i}}I^{\mu\nu,\kappa_{1}\lambda_{1},\kappa_{2}\lambda_{2},\cdots,\kappa_{i}\lambda_{i}}[\boldsymbol{\ell}_{1},\cdots,\boldsymbol{\ell}_{i}]$
(32) $\displaystyle\quad\times$ $\displaystyle
J^{\kappa_{1}\lambda_{1}}_{{\scriptscriptstyle(N_{1})}|-\boldsymbol{\ell}_{12\cdots
n}}J^{\kappa_{2}\lambda_{2}}_{{\scriptscriptstyle(N_{2})}|\boldsymbol{\ell}_{2}}\cdots
J^{\kappa_{i}\lambda_{i}}_{{\scriptscriptstyle(N_{i})}|\boldsymbol{\ell}_{i}}\,,$

where $n=N_{1}+N_{2}+\cdots N_{i}$. For off-shell currents of a single
propagator,

$J^{\mu\nu}_{{\scriptscriptstyle(m)}|\boldsymbol{\ell}}=\frac{N^{\mu\nu}_{{\scriptscriptstyle(m)}}[\boldsymbol{\ell}]}{|\boldsymbol{\ell}|^{\alpha_{m}}}\,,$
(33)

we will now show that
$\mathcal{J}^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}_{1}}$ in (32)
again contains a single propagator by using (33) and (31). For currents (33),
we thus have

$\displaystyle\mathcal{J}^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}_{1}}$
$\displaystyle=\int_{\boldsymbol{\ell}_{2},\cdots,\boldsymbol{\ell}_{n}}\frac{N^{\mu\nu}[\boldsymbol{\ell}_{1},\cdots,\boldsymbol{\ell}_{n}]}{|\boldsymbol{\ell}_{12\cdots
n}|^{\alpha_{1}}|\boldsymbol{\ell}_{2}|^{\alpha_{2}}\cdots|\boldsymbol{\ell}_{n}|^{\alpha_{n}}}\,,$
(34)

where the numerator is polynomial in the arguments. We now perform the
$\boldsymbol{\ell}_{2}$-integration to get

$\displaystyle\mathcal{J}^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}_{1}}$
$\displaystyle=\int_{\boldsymbol{\ell}_{3},\cdots,\boldsymbol{\ell}_{n}}\frac{N_{2}^{\mu\nu}[\boldsymbol{\ell}_{1},\boldsymbol{\ell}_{3}\cdots,\boldsymbol{\ell}_{n}]}{|\boldsymbol{\ell}_{13\cdots
n}|^{\beta_{2}}|\boldsymbol{\ell}_{3}|^{\alpha_{3}}\cdots|\boldsymbol{\ell}_{n}|^{\alpha_{n}}}\,,$
(35)

with a new numerator $N_{2}^{\mu\nu}$. Since the structure of the integrand is
the same as before integration, we may repeat the previous procedure and
perform the $\boldsymbol{\ell}_{3}$ integral to get

$\mathcal{J}^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}_{1}}=\int_{\boldsymbol{\ell}_{4},\cdots,\boldsymbol{\ell}_{n}}\frac{N_{3}^{\mu\nu}[\boldsymbol{\ell}_{1},\boldsymbol{\ell}_{4},\cdots,\boldsymbol{\ell}_{n}]}{|\boldsymbol{\ell}_{14\cdots
n}|^{\beta_{3}}|\boldsymbol{\ell}_{4}|^{\alpha_{4}}\cdots|\boldsymbol{\ell}_{n}|^{\alpha_{n}}}\,,$
(36)

with numerator $N_{3}^{\mu\nu}$. This continues until all loop integrals are
exhausted, leading to

$\displaystyle\mathcal{J}^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}_{1}}$
$\displaystyle=\frac{N^{\mu\nu}_{n}[\boldsymbol{\ell}_{1}]}{|\boldsymbol{\ell}_{1}|^{\beta_{n}}}\,,$
(37)

where $N_{n}^{\mu\nu}$ follows recursively in the manner indicated.

##  V Perturbative solution to all orders

So far we have exploited off-shell recursion relations and iterated momentum
integrals. Our third step towards deriving an all-order result is to encode
the fact that the metric and its inverse expanded around flat Minkowski space
are related by a geometric series which again is of iterative form. We
implement this by first considering $\mathfrak{g}^{\mu\nu}$ and its inverse
$\mathfrak{g}_{\mu\nu}$ as independent fields, introducing an auxiliary field
$\tilde{\mathfrak{g}}_{\mu\nu}$ whose value is fixed to be the inverse of
$\mathfrak{g}^{\mu\nu}$:
$\mathfrak{g}^{\mu\rho}\tilde{\mathfrak{g}}_{\rho\nu}=\delta^{\mu}{}_{\nu}$.
We thus introduce perturbations of both $\mathfrak{g}^{\mu\nu}$ and
$\tilde{\mathfrak{g}}_{\mu\nu}$ Gomez:2021shh ,

$\displaystyle\mathfrak{g}^{\mu\nu}=\eta^{\mu\nu}-\mathsf{h}^{\mu\nu}\,,\qquad\tilde{\mathfrak{g}}_{\mu\nu}=\eta_{\mu\nu}+\tilde{\mathsf{h}}_{\mu\nu}\,,$
(38)

which we expand in Newton’s constant $G$,

$\mathsf{h}^{\mu\nu}=\sum_{n=1}^{\infty}G^{n}\mathsf{h}^{\mu\nu}_{{\scriptscriptstyle(n)}}\,,\qquad\tilde{\mathsf{h}}^{\mu\nu}=\sum^{\infty}_{n=1}G^{n}\tilde{\mathsf{h}}^{\mu\nu}_{{\scriptscriptstyle(n)}}\,,$
(39)

with the constraint

$\tilde{\mathsf{h}}^{\mu\nu}_{{\scriptscriptstyle(n)}}=\mathsf{h}^{\mu\nu}_{{\scriptscriptstyle(n)}}+\sum_{m=1}^{n-1}\tilde{\mathsf{h}}^{\mu\rho}_{{\scriptscriptstyle(n-m)}}\mathsf{h}^{\rho\nu}_{{\scriptscriptstyle(m)}}\,.$
(40)

We also introduce off-shell currents for
$\tilde{\mathsf{h}}^{\mu\nu}_{{\scriptscriptstyle(n)}}$

$\tilde{\mathsf{h}}^{\mu\nu}_{{\scriptscriptstyle(n)}}=\int_{\boldsymbol{\ell}}e^{i\boldsymbol{\ell}\cdot\boldsymbol{x}}\tilde{J}^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}}\,,$
(41)

where $\tilde{J}^{\mu\nu}_{{\scriptscriptstyle(n)}}$ satifies the following
recursion relation:

$\displaystyle\tilde{J}^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{p}}=J^{\mu\nu}_{{\scriptscriptstyle(n)}|\boldsymbol{p}}+\sum_{m=1}^{n-1}\int_{\boldsymbol{\ell}}\tilde{J}^{\mu\rho}_{{\scriptscriptstyle(n-m)}|\boldsymbol{p}-\boldsymbol{\ell}}J^{\rho\nu}_{{\scriptscriptstyle(m)}|\boldsymbol{\ell}}\,.$
(42)

We will now show that the expansion of $\mathsf{h}^{\mu\nu}$ is

$\displaystyle\mathsf{h}^{00}_{{\scriptscriptstyle(n)}}$
$\displaystyle=\frac{8M^{n}}{r^{n}}\,,$
$\displaystyle\qquad\mathsf{h}^{ij}_{{\scriptscriptstyle(n)}}$
$\displaystyle=0\,,\qquad\text{for}~{}n\geq 3\,,$ (43)

while $\tilde{\mathsf{h}}^{00}$ and $\tilde{\mathsf{h}}^{ij}$ are given by

$\displaystyle\tilde{\mathsf{h}}^{00}$
$\displaystyle=\sum_{n=1}^{\infty}(-1)^{n+1}\frac{(n+1)^{2}M^{n}}{r^{n}}\,,$
(44) $\displaystyle\tilde{\mathsf{h}}^{ij}$
$\displaystyle=\sum_{n=1}^{\infty}\frac{M^{2n}x^{i}x^{j}}{r^{2n+2}}\,.$

As a first step, we will show by induction that the corresponding off-shell
currents are given by

$\displaystyle\tilde{J}^{00}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}}$
$\displaystyle=(-1)^{n+1}\frac{(n+1)^{2}M^{n}\pi^{\frac{d}{2}}\Gamma[\frac{d-n}{2}]}{2^{n-d}\Gamma[\frac{n}{2}]}\frac{1}{|\boldsymbol{\ell}|^{d-n}}\,,$
(45)
$\displaystyle\tilde{J}^{ij}_{{\scriptscriptstyle(2n)}|\boldsymbol{\ell}}$
$\displaystyle=\frac{M^{2n}\pi^{\frac{d}{2}}2^{d-2n}\Gamma[\frac{d-2n}{2}]}{2\Gamma[n+1]|\boldsymbol{\ell}|^{d-2n}}\Bigg{[}\delta^{ij}{-}\frac{(d{+}2n)\ell^{i}\ell^{j}}{|\boldsymbol{\ell}|^{2}}\Bigg{]}\,,$
$\displaystyle J^{00}_{{\scriptscriptstyle(n)}|\boldsymbol{\ell}}$
$\displaystyle=\frac{8M^{n}\pi^{\frac{d}{2}}\Gamma\left[\frac{d-n}{2}\right]}{2^{n-d}\Gamma[\frac{n}{2}]}\frac{1}{|\boldsymbol{\ell}|^{d-n}}\,,\qquad\text{for~{}}n\geq
3$

We begin by expressing the 00-component of the Einstein tensor in terms of the
new variables. From this we find that
$\mathsf{h}^{00}_{{\scriptscriptstyle(n)}}$ ($n\geq 4$) satisfies

$\displaystyle\Delta\mathsf{h}^{00}_{{\scriptscriptstyle(n)}}\\!\\!\\!$
$\displaystyle=$
$\displaystyle\\!\\!\\!\partial_{i}\Bigg{[}\mathsf{h}^{ij}_{{\scriptscriptstyle(2)}}\partial_{j}\mathsf{h}^{00}_{{\scriptscriptstyle(n-2)}}+\tilde{\mathsf{h}}{}^{kl}_{{\scriptscriptstyle(n-2)}}\partial^{i}\mathsf{h}^{kl}_{{\scriptscriptstyle(2)}}-\tilde{\mathsf{h}}{}^{kl}_{{\scriptscriptstyle(n-4)}}\partial_{j}\mathsf{h}^{kl}_{{\scriptscriptstyle(2)}}\mathsf{h}^{ij}_{{\scriptscriptstyle(2)}}$
(47)
$\displaystyle\quad-\\!\sum_{m=1}^{n-1}\tilde{\mathsf{h}}^{00}_{{\scriptscriptstyle(n-m)}}\Big{(}\partial^{i}\mathsf{h}^{00}_{{\scriptscriptstyle(m)}}-\partial_{j}\mathsf{h}^{00}_{{\scriptscriptstyle(m-2)}}\mathsf{h}^{ij}_{{\scriptscriptstyle(2)}}\Big{)}\Bigg{]}\,.$

We recast this in terms of the off-shell currents whose 00-components we write
as
$J^{00}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}}=\mathcal{E}^{[1]}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}}-\mathcal{E}^{[2]}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}}$,
with

$\displaystyle\mathcal{E}^{[1]}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=\frac{-\ell^{i}_{1}}{|\boldsymbol{\ell}_{1}|^{2}}\Big{(}X^{i}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}-Y^{i}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}\Big{)}\,,$
(48)
$\displaystyle\mathcal{E}^{[2]}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=\frac{-\ell^{i}_{1}}{|\boldsymbol{\ell}_{1}|^{2}}\int_{\ell_{2}}\Big{(}X^{j}_{{\scriptscriptstyle(n-2)}|-\boldsymbol{\ell}_{12}}-Y^{j}_{{\scriptscriptstyle(n-2)}|-\boldsymbol{\ell}_{12}}$
$\displaystyle\qquad\qquad\qquad+\ell^{j}_{12}J^{00}_{{\scriptscriptstyle(n-2)}|-\boldsymbol{\ell}_{12}}\Big{)}J^{ij}_{{\scriptscriptstyle(2)}|\boldsymbol{\ell}_{2}}\,,$

where

$\displaystyle X^{i}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=\int_{\boldsymbol{\ell}_{2}}\ell^{i}_{2}\sum_{m=1}^{n-1}\tilde{J}^{00}_{{\scriptscriptstyle(n-m)}|-\boldsymbol{\ell}_{12}}J^{00}_{{\scriptscriptstyle(m)}|\boldsymbol{\ell}_{2}}\,,$
(49) $\displaystyle Y^{i}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=\int_{\boldsymbol{\ell}_{2}}\ell^{i}_{2}\tilde{J}^{kl}_{{\scriptscriptstyle(n-2)}|-\boldsymbol{\ell}_{12}}J^{kl}_{{\scriptscriptstyle(2)}|\boldsymbol{\ell_{2}}}\,.$

We start the proof by induction at $n=3$ where we have explicitly verified
that (45) holds. Assuming the currents are given by (45) up to the $(n-1)$-th
order, we next show that it also holds for the $n$-th order term. Dividing
into odd and even $n$, and assuming that (45) holds up to order $n-1$, we find

$\displaystyle\mathcal{E}^{[1]}_{{\scriptscriptstyle(2n)}|-\boldsymbol{{\ell}}}$
$\displaystyle=\frac{M^{2n}\pi^{\frac{d}{2}}2^{d-2n+3}\Gamma[\frac{d}{2}-n]}{\Gamma[n]}\frac{1}{|\boldsymbol{\ell}|^{d-2n}}\,,$
(50)
$\displaystyle\mathcal{E}^{[2]}_{{\scriptscriptstyle(2n)}|-\boldsymbol{{\ell}}}$
$\displaystyle=0\,,$

and

$\displaystyle\mathcal{E}^{[1]}_{{\scriptscriptstyle(2n+1)}|-\boldsymbol{{\ell}}}$
$\displaystyle=\frac{M^{2n+1}\pi^{\frac{d}{2}}(4n+1)2^{d-2n}\Gamma[\frac{d-2n-1}{2}]}{\Gamma[n+\frac{3}{2}]|\boldsymbol{\ell}|^{d-2n-1}}\,,$
(51)
$\displaystyle\mathcal{E}^{[2]}_{{\scriptscriptstyle(2n+1)}|-\boldsymbol{{\ell}}}$
$\displaystyle=\frac{M^{2n+1}\pi^{\frac{d}{2}}2^{d-2n}\Gamma[\frac{d-2n-1}{2}]}{\Gamma[n+\frac{3}{2}]|\boldsymbol{\ell}|^{d-2n-1}}\,.$

For both odd and even $n$ these terms combine to yield eq. (45). Going to four
space-time dimensions, we find

$\mathsf{h}^{00}_{{\scriptscriptstyle(n)}}=\frac{8M^{n}}{r^{n}}\,,$ (52)

for all $n\geq 3$.

The hardest parts to compute are the $ij$-components. We find it convenient to
first introduce

$\displaystyle Z^{ij}{}_{kl}$
$\displaystyle=\mathfrak{g}^{im}\partial_{m}\mathfrak{g}^{jn}\partial_{k}\tilde{\mathfrak{g}}_{nl}\,,$
(53) $\displaystyle W^{i}{}_{l}$
$\displaystyle=\mathfrak{g}^{ki}\partial_{k}\mathfrak{g}^{00}\partial_{l}\tilde{\mathfrak{g}}_{00}\,,$
$\displaystyle d^{i}$
$\displaystyle=\frac{1}{2(d-1)}\mathfrak{g}^{ij}\mathfrak{g}^{\rho\sigma}\partial_{j}\tilde{\mathfrak{g}}_{\rho\sigma}\,.$
$\displaystyle\Delta\mathsf{h}^{ij}$
$\displaystyle=\mathsf{h}^{kl}\partial_{k}\partial_{l}\mathsf{h}^{ij}{-}\partial_{l}\mathsf{h}^{ki}\partial_{k}\mathsf{h}^{lj}{+}2(d{-}1)d^{i}d^{j}{+}2\mathfrak{g}^{ij}\partial_{k}d^{k}$
(54)
$\displaystyle\quad{+}Z^{k(i}{}_{k}{}^{j)}{-}2Z^{(i|k|}{}_{k}{}^{j)}{+}\frac{1}{2}Z^{(i|k|j)}{}_{k}{+}\frac{1}{2}W^{ij}$
$\displaystyle\quad-\frac{1}{2}\Big{[}2Z^{k(i}{}_{kl}{-}4Z^{(i|k|}{}_{kl}{+}Z^{(i|k|}{}_{lk}{+}W^{i}{}_{l}\Big{]}\mathsf{h}^{j)l}\,.$

In terms of currents, we have

$d^{i}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}{=}\frac{i}{2(d-2)}\bigg{[}\mathcal{D}^{i}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}{-}\int_{\boldsymbol{\ell}_{2}}\mathcal{D}^{j}_{{\scriptscriptstyle(n-m)}|-\boldsymbol{\ell}_{12}}J^{ij}_{{\scriptscriptstyle(m)}|\boldsymbol{\ell}_{2}}\bigg{]}\,,$
(55)

where

$\mathcal{D}^{i}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}{=}\bigg{[}\ell^{i}_{1}J^{00}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}{-}\ell^{i}_{1}J^{kk}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}{+}X^{i}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}{+}Y^{i}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}\bigg{]}\,.$
(56)

Iterating, we find

$\displaystyle\mathcal{D}^{i}_{{\scriptscriptstyle(2n)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=\frac{\pi^{\frac{d}{2}}2^{d-2n+1}\Gamma[\frac{d}{2}-n]}{\Gamma[n+1]}\frac{\ell^{i}}{|\boldsymbol{\ell}|^{d-2n}}\,,$
(57)
$\displaystyle\mathcal{D}^{i}_{{\scriptscriptstyle(2n+1)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=-\frac{\pi^{\frac{d}{2}}2^{d-2n}\Gamma[\frac{d-1}{2}-n]}{\Gamma[n+\frac{3}{2}]}\frac{\ell^{i}}{|\boldsymbol{\ell}|^{d-2n-1}}\,,$

so that

$\displaystyle d^{i}_{{\scriptscriptstyle(1)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=2^{d-1}\pi^{\frac{d-1}{2}}|\boldsymbol{\ell}_{1}|^{1-d}\Gamma[\tfrac{d-1}{2}]\ell^{i}\,,$
(58) $\displaystyle d^{i}_{{\scriptscriptstyle(2)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=-2^{d-3}\pi^{\frac{d}{2}}|\boldsymbol{\ell}_{1}|^{2-d}\Gamma[\tfrac{d}{2}-1]\ell^{i}\,,$
$\displaystyle d^{i}_{{\scriptscriptstyle(n)}|-\boldsymbol{\ell}_{1}}$
$\displaystyle=0\,,~{}~{}~{}\text{for}~{}n\geq 3\,.$

Similarly, we find

$W^{ij}_{{\scriptscriptstyle(3)}|-\boldsymbol{\ell}_{1}}=\frac{\Gamma[\tfrac{d-5}{2}]\big{(}|\boldsymbol{\ell}_{1}|^{2}\delta^{ij}-(d-5)\ell_{1}^{i}\ell_{1}^{j}\big{)}}{2^{-d-1}15\pi^{\frac{1-d}{2}}}|\boldsymbol{\ell}_{1}|^{3-d}\,,$
(59)

and, for $n>2$,

$\displaystyle W^{ij}_{{\scriptscriptstyle(2n)}|-\boldsymbol{\ell}}$
$\displaystyle=\frac{5\pi^{\frac{d}{2}}\Gamma[\frac{d-2n-2}{2}]}{2^{2n+1-d}\Gamma[n{+}2]}\frac{(2n{+}2{-}d)\ell^{i}\ell^{j}{-}|\boldsymbol{\ell}|^{2}\delta^{ij}}{|\boldsymbol{\ell}|^{d-2n}}\,,$
(60) $\displaystyle W^{ij}_{{\scriptscriptstyle(2n+1)}|-\boldsymbol{\ell}}$
$\displaystyle=\frac{\pi^{\frac{d}{2}}\Gamma[\frac{d{-}2n{-}3}{2}]}{2^{2n-d}\Gamma[n{+}\frac{5}{2}]}\frac{(d{-}2n{-}3)\ell^{i}\ell^{j}{-}|\boldsymbol{\ell}|^{2}\delta^{ij}}{|\boldsymbol{\ell}|^{d-2n-1}}\,.$

Substituting these results all terms with auxiliary fields $d^{i}$ and
$W^{ij}$ cancel for $n\geq 4$. Finally, also all terms with the $Z$-fields
combine to cancel separately. Thus, in total,

$\mathsf{h}^{ij}_{(n)}=0\,,~{}~{}~{}n\geq 3~{}.$ (61)

To summarize this part, we have shown to all orders in perturbation theory
that $h^{\mu\nu}$ satisfies the expansions (4) and (6). The expansion for
$h^{00}$ is convergent for $GM/r>1$ and sums to the correct expression in that
region while the expansion for $h^{ij}$ truncates at order $G^{2}$, in
agreement with eq. (4).

As is well known, the harmonic gauge condition does not determine uniquely the
standard harmonic-gauge metric (4) due to a residual choice of coordinate
freedom within the harmonic gauge itself Fromholz:2013hka . This prompts the
question as to how such a residual freedom should manifest itself within our
recursive solution that seems to uniquely provide the standard form (4). The
issue is resolved by noticing that the perturbative solution requires
regularization of the pertinent loop integrals beyond the first few leading
orders. Indeed, up to order $G^{2}$ there is no need for regularizing the
integrals and there is correspondingly no additional coordinate freedom of the
harmonic-gauge metric Fromholz:2013hka . At order $G^{3}$ we need to
regularize the loop integrals. Simultaneously, we encounter constant
numerators in the loop integrands. Those terms lead to (unregularized)
integrals that are scale-free and they are set to zero in dimensional
regularization. Other equally valid regularization schemes may set those
integrals to other constant values, and thus introduce new scheme-dependent
constants in the metric. By iteration, such constants will enter at all higher
orders as well. This is in agreement with the arbitrariness stemming from
residual coordinate freedom in this gauge.

##  VI Conclusion

Applying the perturbiner method to Einstein gravity we have shown how to
derive the harmonic-gauge metric of a Schwarzschild black hole to all orders
in perturbation theory. This is the first example of a post-Minkowskian
expansion in general relativity that has been carried through to all orders
and which therefore teaches us about the convergence of such expansions. We
find that the series is convergent within the expected range based on the
closed expression of eq. (4). What makes this all-order result possible in
spite of the overwhelming complexity of perturbative gravity is the iterative
systematics of the perturbiner expansion for gravitational equations of
motion, combined with recursive structures of the involved loop integrals. In
addition, complications arising from the perturbative expansion of the
Einstein-Hilbert action can be controlled by a doubling of degrees of freedom
at intermediate steps. This highlights the fact that also the weak-field
expansion of the action contains iterative structures, here inherited from the
geometric series relation between metric and inverse metric, an observation
made earlier in ref. Cheung:2017kzx . In a broader perspective, one may hope
that the perturbiner approach to post-Minkowskian gravity Cho:2021nim ;
Lee:2022aiu ; Cho:2022faq ; Adamo:2023cfp ; Lee:2023zuu ; Cho:2023kux  could
lead to related simplifications for the general relativistic two-body problem.

###### Acknowledgements.

Acknowledgments: We thank Thibault Damour for discussions regarding
convergence properties of the post-Minkowskian expansion. The work of P.H.D.
is supported in part by DFF Grant No. 0135-00089A, and the work of K.L. has
been supported in part by appointment to the JRG Program at the APCTP through
the Science and Technology Promotion Fund and Lottery Fund of the Korean
Government. KL is also supported by the National Research Foundation of
Korea(NRF) grant funded by the Korean government(MSIT) RS-2023-00249451 and
the Korean Local Governments of Gyeongsangbuk-do Province and Pohang City.

## References

  * (1) N. E. J. Bjerrum-Bohr, P. H. Damgaard, G. Festuccia, L. Planté and P. Vanhove, Phys. Rev. Lett. 121, no.17, 171601 (2018) [arXiv:1806.04920 [hep-th]].
  * (2) C. Cheung, I. Z. Rothstein and M. P. Solon, Phys. Rev. Lett. 121, no.25, 251101 (2018) [arXiv:1808.02489 [hep-th]].
  * (3) D. A. Kosower, B. Maybee and D. O’Connell, JHEP 02, 137 (2019) [arXiv:1811.10950 [hep-th]].
  * (4) A. Cristofoli, N. E. J. Bjerrum-Bohr, P. H. Damgaard and P. Vanhove, Phys. Rev. D 100, no.8, 084040 (2019) [arXiv:1906.01579 [hep-th]].
  * (5) Z. Bern, C. Cheung, R. Roiban, C. H. Shen, M. P. Solon and M. Zeng, Phys. Rev. Lett. 122, no.20, 201603 (2019) [arXiv:1901.04424 [hep-th]].
  * (6) Z. Bern, C. Cheung, R. Roiban, C. H. Shen, M. P. Solon and M. Zeng, JHEP 10 (2019), 206 [arXiv:1908.01493 [hep-th]].
  * (7) G. Kälin and R. A. Porto, JHEP 01, 072 (2020) [arXiv:1910.03008 [hep-th]].
  * (8) N. E. J. Bjerrum-Bohr, A. Cristofoli and P. H. Damgaard, JHEP 08, 038 (2020) [arXiv:1910.09366 [hep-th]].
  * (9) T. Damour, Phys. Rev. D 102, no.2, 024060 (2020) [arXiv:1912.02139 [gr-qc]].
  * (10) P. Di Vecchia, C. Heissenberg, R. Russo and G. Veneziano, Phys. Lett. B 811, 135924 (2020) [arXiv:2008.12743 [hep-th]].
  * (11) T. Damour, Phys. Rev. D 102 (2020) no.12, 124008 [arXiv:2010.01641 [gr-qc]].
  * (12) P. Di Vecchia, C. Heissenberg, R. Russo and G. Veneziano, Phys. Lett. B 818 (2021), 136379 [arXiv:2101.05772 [hep-th]].
  * (13) P. Di Vecchia, C. Heissenberg, R. Russo and G. Veneziano, JHEP 07 (2021), 169 [arXiv:2104.03256 [hep-th]].
  * (14) E. Herrmann, J. Parra-Martinez, M. S. Ruf and M. Zeng, JHEP 10, 148 (2021) [arXiv:2104.03957 [hep-th]].
  * (15) N. E. J. Bjerrum-Bohr, P. H. Damgaard, L. Planté and P. Vanhove, Phys. Rev. D 104 (2021) no.2, 026009 [arXiv:2104.04510 [hep-th]].
  * (16) N. E. J. Bjerrum-Bohr, P. H. Damgaard, L. Planté and P. Vanhove, JHEP 08 (2021), 172 [arXiv:2105.05218 [hep-th]].
  * (17) P. H. Damgaard, L. Plante and P. Vanhove, JHEP 11 (2021), 213 [arXiv:2107.12891 [hep-th]].
  * (18) A. Brandhuber, G. Chen, G. Travaglini and C. Wen, JHEP 10 (2021), 118 [arXiv:2108.04216 [hep-th]].
  * (19) A. Brandhuber, G. Chen, H. Johansson, G. Travaglini and C. Wen, Phys. Rev. Lett. 128 (2022) no.12, 121601 [arXiv:2111.15649 [hep-th]].
  * (20) G. Kälin and R. A. Porto, JHEP 11 (2020), 106 [arXiv:2006.01184 [hep-th]].
  * (21) G. Kälin, Z. Liu and R. A. Porto, Phys. Rev. Lett. 125 (2020) no.26, 261103 [arXiv:2007.04977 [hep-th]].
  * (22) G. Mogull, J. Plefka and J. Steinhoff, JHEP 02 (2021), 048 [arXiv:2010.02865 [hep-th]].
  * (23) G. U. Jakobsen, G. Mogull, J. Plefka and J. Steinhoff, Phys. Rev. Lett. 126 (2021) no.20, 201103 [arXiv:2101.12688 [gr-qc]].
  * (24) S. Mougiakakos, M. M. Riva and F. Vernizzi, Phys. Rev. D 104 (2021) no.2, 024041 [arXiv:2102.08339 [gr-qc]].
  * (25) M. M. Riva and F. Vernizzi, JHEP 11 (2021), 228 [arXiv:2110.10140 [hep-th]].
  * (26) Z. Bern, J. Parra-Martinez, R. Roiban, M. S. Ruf, C. H. Shen, M. P. Solon and M. Zeng, Phys. Rev. Lett. 126, no.17, 171601 (2021) [arXiv:2101.07254 [hep-th]].
  * (27) C. Dlapa, G. Kälin, Z. Liu and R. A. Porto, Phys. Lett. B 831 (2022), 137203 [arXiv:2106.08276 [hep-th]].
  * (28) Z. Bern, J. Parra-Martinez, R. Roiban, M. S. Ruf, C. H. Shen, M. P. Solon and M. Zeng, Phys. Rev. Lett. 128, no.16, 161103 (2022) [arXiv:2112.10750 [hep-th]].
  * (29) T. Adamo and R. Gonzo, JHEP 05, 088 (2023) [arXiv:2212.13269 [hep-th]].
  * (30) C. Dlapa, G. Kälin, Z. Liu and R. A. Porto, JHEP 08, 109 (2023) [arXiv:2304.01275 [hep-th]].
  * (31) G. U. Jakobsen, G. Mogull, J. Plefka, B. Sauer and Y. Xu, Phys. Rev. Lett. 131, no.15, 151401 (2023) [arXiv:2306.01714 [hep-th]].
  * (32) P. H. Damgaard, E. R. Hansen, L. Planté and P. Vanhove, JHEP 09, 059 (2023) [arXiv:2306.11454 [hep-th]].
  * (33) P. H. Damgaard, E. R. Hansen, L. Planté and P. Vanhove, JHEP 09, 183 (2023) [arXiv:2307.04746 [hep-th]].
  * (34) G. U. Jakobsen, G. Mogull, J. Plefka and B. Sauer, Phys. Rev. Lett. 131, no.24, 241402 (2023) [arXiv:2308.11514 [hep-th]].
  * (35) P. Di Vecchia, C. Heissenberg, R. Russo and G. Veneziano, [arXiv:2306.16488 [hep-th]].
  * (36) M. Driesse, G. U. Jakobsen, G. Mogull, J. Plefka, B. Sauer and J. Usovitsch, [arXiv:2403.07781 [hep-th]].
  * (37) D. Christodoulou and B.G. Schmidt, Commun.Math. Phys. 68, 275–289 (1979)
  * (38) T. Damour and B. G. Schmidt, J. Math. Phys. 31, 2441-2453 (1990)
  * (39) P. S. Florides and J. L. Synge, “Notes on the Schwarzschild line-element”, Comm. Dublin Inst. f. Adv. Studies A14 (1961).
  * (40) M. J. Duff, Phys. Rev. D 7, 2317-2326 (1973)
  * (41) N. E. J. Bjerrum-Bohr, J. F. Donoghue and B. R. Holstein, Phys. Rev. D 68, 084005 (2003) [erratum: Phys. Rev. D 71, 069904 (2005)] [arXiv:hep-th/0211071 [hep-th]].
  * (42) W. D. Goldberger and I. Z. Rothstein, Phys. Rev. D 73, 104029 (2006) [arXiv:hep-th/0409156 [hep-th]].
  * (43) D. Neill and I. Z. Rothstein, Nucl. Phys. B 877, 177-189 (2013) [arXiv:1304.7263 [hep-th]].
  * (44) A. Koemans Collado, P. Di Vecchia, R. Russo and S. Thomas, JHEP 10, 038 (2018) [arXiv:1807.04588 [hep-th]].
  * (45) G. U. Jakobsen, Phys. Rev. D 102, no.10, 104065 (2020) [arXiv:2006.01734 [hep-th]].
  * (46) S. Mougiakakos and P. Vanhove, Phys. Rev. D 103, no.2, 026001 (2021) [arXiv:2010.08882 [hep-th]].
  * (47) S. D’Onofrio, F. Fragomeno, C. Gambino and F. Riccioni, JHEP 09, 013 (2022) [arXiv:2207.05841 [hep-th]].
  * (48) A. A. Rosly and K. G. Selivanov, Phys. Lett. B 399, 135-140 (1997) [arXiv:hep-th/9611101 [hep-th]].
  * (49) A. A. Rosly and K. G. Selivanov, [arXiv:hep-th/9710196 [hep-th]].
  * (50) C. R. Mafra, JHEP 07, 080 (2016) [arXiv:1603.09731 [hep-th]].
  * (51) S. Mizera and B. Skrzypek, JHEP 10, 018 (2018) [arXiv:1809.02096 [hep-th]].
  * (52) H. Gomez and R. L. Jusinskas, Phys. Rev. Lett. 127, no.18, 181603 (2021) [arXiv:2106.12584 [hep-th]].
  * (53) H. Gomez, R. Lipinski Jusinskas, C. Lopez-Arcos and A. Quintero Velez, Phys. Rev. Lett. 130, no.8, 081601 (2023) [arXiv:2208.02831 [hep-th]].
  * (54) K. Cho, K. Kim and K. Lee, JHEP 01, 186 (2022) [arXiv:2109.06392 [hep-th]].
  * (55) K. Lee, JHEP 05, 051 (2022) [arXiv:2202.08133 [hep-th]].
  * (56) K. Cho, K. Kim and K. Lee, JHEP 03, 112 (2023) [arXiv:2209.11424 [hep-th]].
  * (57) T. Adamo, A. Cristofoli, A. Ilderton and S. Klisch, [arXiv:2307.00431 [hep-th]].
  * (58) H. Lee, K. Lee and S. Lee, JHEP 10, 044 (2023) [arXiv:2307.05626 [hep-th]].
  * (59) K. Cho, K. Kim and K. Lee, [arXiv:2311.01284 [hep-th]].
  * (60) Y. X. Tao, Phys. Rev. D 108, no.12, 125020 (2023) [arXiv:2309.15657 [hep-th]].
  * (61) F. A. Berends and W. T. Giele, Nucl. Phys. B 306, 759-808 (1988)
  * (62) P. Fromholz, E. Poisson and C. M. Will, Am. J. Phys. 82, 295 (2014) [arXiv:1308.0394 [gr-qc]].
  * (63) C. Cheung and G. N. Remmen, JHEP 09, 002 (2017) [arXiv:1705.00626 [hep-th]].