$v$ is placed in the OCT, or in one of the two sides of the bipartition. Each
of these states satisfies the conclusion.

Let $t$ be a disjoint union node with children $t_{1},t_{2}$ such that
${G_{t}=G_{t_{1}}\oplus\,G_{t_{2}}}$, and $(t,\mathbf{x})$ be a reachable
state. By the described transitions, there exist reachable states
$(t_{1},\mathbf{x}_{1})$ and $(t_{2},\mathbf{x}_{2})$ such that
$\mathbf{x}\geq\mathbf{x}_{1}\vee\mathbf{x}_{2}$ and
$d[t,\mathbf{x}]=d[t_{1},\mathbf{x}_{1}]+d[t_{2},\mathbf{x}_{2}].$ By
induction hypothesis, for $i\in[2]$, there exist triples $(X_{i},A_{i},B_{i})$
compatible with $(t_{i},\mathbf{x}_{i})$ such that
$c(X_{i})=d[t_{i},\mathbf{x}_{i}]$. As ${G_{t}=G_{t_{1}}\oplus\,G_{t_{2}}}$,
$X=X_{1}\cup X_{2}$ is an OCT of $G_{t}$ and $(A_{1}\cup A_{2},B_{1}\cup
B_{2})$ defines a bipartition of $G_{t}-X$. Furthermore as
$\mathbf{x}\geq\mathbf{x}_{1}\vee\mathbf{x}_{2}$, it is straightforward to
check that $(X,A_{1}\cup A_{2},B_{1}\cup B_{2})$ are compatible with
$(t,\mathbf{x})$. We conclude noting that
$c(X)=c(X_{1})+c(X_{2})=d[t_{1},\mathbf{x}_{1}]+d[t_{2},\mathbf{x}_{2}]=d[t,\mathbf{x}]$.

Let $t$ be a join node with child $t^{\prime}$ such that $G_{t}=\eta_{i\times
j}(G_{t^{\prime}})$, and $(t,\mathbf{x})$ be a reachable state. By the
described transitions $(t^{\prime},\mathbf{x})$ is also a reachable state
satisfying one of the conditions $\mathbf{x}[i]=0$, or $\mathbf{x}[j]=0$, or
($\mathbf{x}[i]=1$ and $\mathbf{x}[j]=2$), or ($\mathbf{x}[i]=2$ and
$\mathbf{x}[j]=1$). Furthermore, $d[t,\mathbf{x}]=d[t^{\prime},\mathbf{x}]$.
By induction hypothesis, there exists a triple $(X,A,B)$ compatible with
$(t^{\prime},\mathbf{x})$ such that $c(X)=d[t^{\prime},\mathbf{x}]$, and hence
such that $c(X)=d[t,\mathbf{x}]$. According to the transition, as $(X,A,B)$
and $(t^{\prime},\mathbf{x})$ are compatible, every edge added to
$G_{t^{\prime}}$ when performing the join operation either has an endpoint in
$X$, or one in $A$ and the other in $B$. We deduce that $X$ is also an OCT of
$G_{t}$, and that $(A,B)$ also defines a bipartition of $G_{t}$. Hence,
$(X,A,B)$ is compatible with $(t,\mathbf{x})$.

Let $t$ be a renaming label node with child $t^{\prime}$ such that
$G_{t}=\rho_{i\rightarrow j}(G_{t^{\prime}})$, and let $(t,\mathbf{x})$ be a
reachable state. By the described transitions there exists
$\mathbf{x}^{\prime}$ such that $\mathbf{x}[i]=0$,
$\mathbf{x}[j]=\mathbf{x}^{\prime}[i]\vee\mathbf{x}^{\prime}[j]$, and
$\mathbf{x}[\ell]=\mathbf{x}^{\prime}[\ell]$ for $\ell\not\in\\{i,j\\}$, and
such that $d[t,\mathbf{x}]=d[t^{\prime},\mathbf{x}^{\prime}]$. By induction
hypothesis, there exists a triple $(X,A,B)$ compatible with
$(t^{\prime},\mathbf{x}^{\prime})$ such that
$c(X)=d[t^{\prime},\mathbf{x}^{\prime}]$, and hence such that
$c(X)=d[t,\mathbf{x}]$. As $G_{t}$ and $G_{t^{\prime}}$ are isomorphic, $X$ is
also an OCT of $G_{t}$, and $(A,B)$ also defines a bipartition of $G_{t}-X$.
As $\mathbf{x}[i]=0$ and
$\mathbf{x}[j]=\mathbf{x}^{\prime}[i]\vee\mathbf{x}^{\prime}[j]$ are the only
modifications made to $\mathbf{x}^{\prime}$, it is easy to check that
$(X,A,B)$ is compatible with $(t,\mathbf{x})$. ∎

######  Lemma 5.2.

For every node $t\in V(T)$, for every OCT $X$ of $G_{t}$ and bipartition
$(A,B)$ of $G_{t}-X$, there exists $\mathbf{x}\in\\{0,1,2,3\\}^{k}$ such that
$(t,\mathbf{x})$ is reachable, compatible with $(X,A,B)$, and satisfies
$c(X)\geq d[t,\mathbf{x}]$.

###### Proof.

We proceed by induction on $T$.

Let $t$ be a leaf node with $G_{t}=i(v)$ for some vertex $v$ and label
$i\in[k]$, then three different cases arise depending on whether $v$ is placed
in the OCT, or in one of the two sides of the bipartition. For each of these
cases, a compatible state is constructed and a value satisfying $c(X)\geq
d[t,\mathbf{x}]$ is initialized.

Let $t$ be a disjoint union node with children $t_{1},t_{2}$ such that
${G_{t}=G_{t_{1}}\oplus\,G_{t_{2}}}$, $X$ be an OCT of $G_{t}$, and $(A,B)$ be
a bipartition of $G_{t}-X$. As ${G_{t}=G_{t_{1}}\oplus\,G_{t_{2}}}$,
$X_{1}=X\cap V(G_{t_{1}})$ and $X_{2}=X\cap V(G_{t_{2}})$ are OCTs of
$G_{t_{1}}$ and $G_{t_{2}}$, and the ordered pairs $(A_{1}=A\cap
V(G_{t_{1}}),B_{1}=B\cap V(G_{t_{1}}))$ and $(A_{2}=A\cap
V(G_{t_{2}}),B_{2}=B\cap V(G_{t_{2}}))$ define bipartitions of
$G_{t_{1}}-X_{1}$ and $G_{t_{2}}-X_{2}$, respectively. By induction
hypothesis, there exist reachable states $(t_{1},\mathbf{x}_{1})$ and
$(t_{2},\mathbf{x}_{2})$ with $d[t_{1},\mathbf{x}_{1}]\leq c(X_{1})$ and
$d[t_{2},\mathbf{x}_{2}]\leq c(X_{2})$ that are compatible with
$(X_{1},A_{1},B_{1})$ and $(X_{2},A_{2},B_{2})$, respectively. By the
described transitions, the state $(t,\mathbf{x})$ defined by
$\mathbf{x}:=\mathbf{x}_{1}\vee\mathbf{x}_{2}$ is computed, and it is
compatible with $(X,A,B)$. Since $c(X)=c(X_{1})+c(X_{2})$ we deduce
$d[t,\mathbf{x}]\leq d[t_{1},\mathbf{x}_{1}]+d[t_{2},\mathbf{x}_{2}]\leq c(X)$
as desired.

Let $t$ be a join node with child $t^{\prime}$ such that $G_{t}=\eta_{i\times
j}(G_{t^{\prime}})$, $X$ be an OCT of $G_{t}$, and $(A,B)$ be a bipartition of
$G_{t}-X$. Since $E(G_{t^{\prime}}-X)\subseteq E(G_{t}-X)$, $X$ is also an OCT
of $G_{t^{\prime}}-X$, and $(A,B)$ is also a bipartition of
$G_{t^{\prime}}-X$. By induction hypothesis, there exists a reachable state
$(t^{\prime},\mathbf{x})$ that is compatible with $(X,A,B)$, and which
satisfies $d[t^{\prime},\mathbf{x}]\leq c(X)$. Since $(A,B)$ is a bipartition
of $G_{t}-X$, the edges that were added to $G_{t^{\prime}}$ by the join
operation either had an endpoint in $X$, or one in $A$ and the other in $B$.
Hence, either one of the labels $i$ and $j$ is empty (category 0), or $i$ and
$j$ are on distinct sides of the partition. We conclude to a transition from
$(t^{\prime},\mathbf{x})$ to $(t,\mathbf{x})$, and hence $d[t,\mathbf{x}]\leq
d[t^{\prime},\mathbf{x}]\leq c(X)$.

Let $t$ be a renaming label node with child $t^{\prime}$ such that
$G_{t}=\rho_{i\rightarrow j}(G_{t^{\prime}})$, $X$ be an OCT of $G_{t}$ and
$(A,B)$ be a bipartition of $G_{t}-X$. Since $G_{t}$ and $G_{t^{\prime}}$ are
isomorphic, $X$ is also an OCT of $G_{t^{\prime}}$, and $(A,B)$ is also a
bipartition of $G_{t^{\prime}}-X$. By induction hypothesis, there exists a
reachable state $(t^{\prime},\mathbf{x}^{\prime})$ that is compatible with
$(X,A,B)$, and which satisfies $d[t^{\prime},\mathbf{x}^{\prime}]\leq c(X)$.
The transition from this state gives us a reachable state $(t,\mathbf{x})$
such that $d[t,\mathbf{x}]\leq d[t^{\prime},\mathbf{x}^{\prime}]\leq c(X)$.
The obtained state $(t,\mathbf{x})$ is still compatible with $(A,B)$, as its
modification exactly translates the change of label of the concerned vertices.
∎

We deduce the correctness of our algorithm.

######  Theorem 5.3.

The minimum size of an OCT for $G$ is equal to the minimum, among
$\mathbf{x}\in\\{0,1,2,3\\}^{k}$, of $d[r,\mathbf{x}]$.

###### Proof.

Let $X^{*}$ be an OCT of $G$ of minimum size, and $(A,B)$ be a bipartition of
$G-X^{*}$. By Lemma 5.2, there exists a reachable state $(r,\mathbf{x})$
compatible with $(X^{*},A,B)$ such that $c(X^{*})\geq d[r,\mathbf{x}]$. By
Lemma 5.1, for every other state $(r,\mathbf{y})$, either $(r,\mathbf{y})$ is
not reachable and $d[r,\mathbf{y}]=+\infty$, or it is reachable and there
exists an OCT $Y$ of $G$ such that $c(Y)=d[r,\mathbf{y}]$. We conclude by
noting that $c(X^{*})\leq c(Y)$ for every such set $Y$. ∎

We conclude the section with the time analysis.

######  Theorem 5.4.

There are at most $\mathcal{O}(4^{k}\cdot n)$ possible states in total, and
computing all reachable states takes $\mathcal{O}(4^{k}\cdot k\cdot n)$ time.

###### Proof.

There are $4^{k}$ states per node of the $k$-expression, hence there are at
most $\mathcal{O}(4^{k}\cdot n\cdot k^{2})$ possible states in total in the
algorithm.

The computation of a leaf node takes $\mathcal{O}(1)$ time, and the
computations of a join or renaming label node is done within
$\mathcal{O}(4^{k})$ time. Let us show that the computation of a disjoint
union node $t$ takes $\mathcal{O}(4^{k}\cdot k)$ time. We first compute
$\delta_{i}(\mathbf{x})=\min\\{d[t_{i},\mathbf{x}^{\prime}]:\mathbf{x}^{\prime}\leq\mathbf{x}\\}$
for $i\in[2]$ and every $\mathbf{x}\in\\{0,1,2,3\\}^{k}$. This is done in
$\mathcal{O}(4^{k}\cdot k)$ time starting from
$\delta_{i}(\\{0\\}^{k})=d[t_{i},\\{0\\}^{k}]$, and computing the other values
from bottom to top, observing that, by monotonicity of $\delta_{i}$,
$\delta_{i}(\mathbf{x})=\min\\{d[t_{i},\mathbf{x}],\delta_{i}(\mathbf{x}^{\prime})\colon\mathbf{x}^{\prime}\in\operatorname{pred}(\mathbf{x})\\}$,
where $\operatorname{pred}(\mathbf{x})$ denote the immediate predecessors of
$\mathbf{x}$ in $\\{0,1,2,3\\}^{k}$ with respect to $\leq$. Now, note that by
definition of the supremum, we have the following identity:

$\min_{\mathbf{x}_{1}\vee\mathbf{x}_{2}\leq
x}d[t_{1},\mathbf{x}_{1}]+d[t_{2},\mathbf{x}_{2}]=\min_{\mathbf{x}_{1}\leq\mathbf{x}}d[t_{1},\mathbf{x}_{1}]+\min_{\mathbf{x}_{2}\leq\mathbf{x}}d[t_{2},\mathbf{x}_{2}].$

We deduce that
$d[t,\mathbf{x}]=\delta_{1}(\mathbf{x})+\delta_{2}(\mathbf{x})$.

Summing up, our algorithm runs in time $\mathcal{O}(4^{k}\cdot k\cdot n)$. ∎

###  5.2 The lower bound

Our construction follows the line of the ones for Independent Set and Odd
Cycle Transversal in [LMS11a]. Let $\varphi$ be an instance of SAT on $n$
variable and $m$ clauses. Note that we may assume that $n$ is even, as
otherwise we can add a single extra dummy variable to the instance with no
impact on the satisfiability of $\varphi$. We denote by $\rho$ the sum of the
sizes of the clauses in $\varphi$, i.e., the total number of occurrences of
literals in $\varphi$.

Let us first describe a gadget introduced in [LMS11a, Section 7]. For two
vertices $u,v$ we call _arrow from $u$ to $v$_ and denote by $A(u,v)$ the
graph consisting of a path $ua_{1}a_{2}a_{3}v$ on five vertices, together with
the additional four vertices $b_{1},b_{2},b_{3},b_{4}$ and eight edges
$ub_{1},b_{1}a_{1},a_{1}b_{2},b_{2}a_{2},a_{2}b_{3},b_{3}a_{3},a_{3}b_{4},b_{4}v$.
This graph is illustrated in Figure 3. Note that such a graph has a unique
smallest OCT of size $2$, which is $\\{a_{1},a_{3}\\}$: we call _passive OCT_
of the arrow such an OCT. In $A(u,v)\setminus\\{u\\}$, $\\{a_{2},v\\}$ is a
smallest OCT: we call it _active OCT_ of the arrow.

$b_{1}$$b_{2}$$b_{3}$$b_{4}$$a_{1}$$a_{3}$$u$$a_{2}$$v$ Figure 3: The arrow
$A(u,v)$. Vertices in blue form the passive OCT of $A(u,v)$, and those in red
form the active OCT of $A(u,v)\setminus\\{u\\}$.

For a clause $C=\\{\ell_{1},\dots,\ell_{t}\\}$ with $t$ an odd integer greater
than $2$, let us denote by $\widehat{C}$ the graph consisting of a simple
cycle on vertex set $\\{c_{1},\dots,c_{t}\\}$ with $c_{i}$ representing
literal $\ell_{i}$, and with edges linking $c_{i}$’s in the natural way:
$c_{i}c_{i+1}$ for every $i\in[t-1]$, and $c_{t}c_{1}$. For a clause $C$ of
even size $t\geq 2$, we proceed similarly but subdivide an arbitrary edge so
that the obtained graph $\widehat{C}$ is an odd cycle. For a clause $C$ of
size one, we simply create a triangle $\widehat{C}$, one of its vertices
representing the unique literal of the clause.

We construct a graph $G_{1}$ as follows. We create $n$ paths
$P_{1},\dots,P_{n}$ each of length $2m$, and denote by $p_{i,j}$ the
$j^{\text{th}}$ vertex on path $P_{i}$. Each $P_{i}$ will be referred to as
the path of variable $x_{i}$ in the following. We add “crossing” edges as
follows: for every odd $i\in[n-1]$ and even $j\in[2m-1]$, we add edges
$p_{i,j}p_{i+1,j+1}$ and $p_{i+1,j}p_{i,j+1}$; this is illustrated in Figure
4. Crossing edges will serve no other purpose than allowing to construct these
paths with $n/2$ labels. At this stage, paths of $G_{1}$ may be seen as rows
representing variables of $\varphi$, and vertices
$\bigcup_{i\in[n]}\\{p_{i,2j},p_{i,2j-1}\\}$ for $j\in[m]$ may be seen as
columns grouped two by two representing the two possible values variables
$x_{i}$ may take in clause $C_{j}$. For every clause
$C_{j}=\\{\ell_{1},\dots,\ell_{|C_{j}|}\\}$ in $\varphi$, we add cycle
$\widehat{C}_{j}$ to $G_{1}$, and make the following connections. If variable
$x_{i}$ appears positively in $C_{j}$ on position $p$, i.e., $\ell_{p}=x_{i}$,
then we add arrow $A(p_{i,2j-1},c_{p})$ to $G_{1}$. If $x_{i}$ appears
negatively in $C_{j}$ on position $p$, then we add arrow $A(p_{i,2j},c_{p})$
to $G_{1}$. This concludes the construction of the graph $G_{1}$.

We now consider $n+1$ copies of $G_{1}$ that we name $G_{1},\dots,G_{n+1}$.
Let us denote by $P^{k}_{1},\dots,P^{k}_{n}$ the $n$ paths of $G_{k}$,
$p^{k}_{i,j}$ the $j^{\text{th}}$ vertex of $P^{k}_{i}$, and $C^{k}$ the cycle
representing clause $C$ in $G_{k}$, for every $k\in[n+1]$. We link consecutive
graphs $G_{k},G_{k+1},k\in[n]$ by adding edges $p^{k}_{i,2m}p^{k+1}_{i,1}$ for
every $i\in[n]$, and denote by $P^{*}_{i}$ the resulting path of length
$2m\cdot(n+1)$ obtained by concatenating $P^{1}_{i},\dots,P^{n+1}_{i}$ in such
a way. In addition, we add crossing edges $p^{k}_{i,2m}p^{k+1}_{i+1,1}$ and
$p^{k}_{i+1,2m}p^{k+1}_{i,1}$ for every $k\in[n]$ and odd $i\in[n]$. We
complete our construction by creating a biclique of bipartition $\\{A,B\\}$
with $A$ and $B$ of size $\alpha+1=(n+1)(nm+2\rho)+1$, by connecting every
vertex of $A$ to every vertex of $P^{*}_{i}$ for odd $i\in[n]$, and by
connecting every vertex of $B$ to every vertex of $P^{*}_{i}$ for even
$i\in[n]$. We call $G$ the obtained graph.

$\dots$$\dots$$\dots$$\dots$$\dots$$\dots$ Figure 4: The crossing edges on
paths $P_{1},\dots,P_{n}$ in $G_{1}$.

######  Lemma 5.5.

If $\varphi$ is satisfiable, then there exists an OCT of size
$\alpha=(n+1)(nm+2\rho)$ in $G$.

###### Proof.

Let $\tau$ be a satisfying truth assignment of $\varphi$. We construct an OCT
$T$ of $G$ as follows. If $\tau(x_{i})$ is true, then we add $p^{k}_{i,j}$ to
$T$ for every $k\in[n+1]$ and odd $j\in[2m]$. Otherwise we add $p^{k}_{i,j}$
to $T$ for every $k\in[n+1]$ and even $j\in[2m]$. For each of the
$\rho\cdot(n+1)$ arrows $A(u,v)$ in $G$, we add its active OCT if $u$ is part
of $T$, and its passive OCT otherwise, each of size two. The obtained set $T$
is of size $\alpha$.

Since each clause $C$ is satisfied by $\tau$, at least one of its literals is
satisfied. Thus for each cycle in $\widehat{C}^{k},k\in[n+1]$ there exists an
arrow $A(u,v)$ having an endpoint $u$ being part of $T$. Hence that arrow is
active and we conclude that $v$ as well is part of $T$. We conclude that every
(odd) cycle $\widehat{C}^{1},\dots,\widehat{C}^{n+1}$ corresponding to $C$ is
hit by $T$. Since $T$ is a vertex cover of the paths $P^{*}_{i},i\in[n]$ every
remaining edge in $G-T$ that is not part of a clause cycle nor an arrow is
either a crossing edge, or an edge incident to a vertex of $A$ or $B$. Since
these edges do not induce odd cycles, we conclude that $T$ is an OCT of $G$,
as desired. ∎

######  Lemma 5.6.

If there exists an OCT of size $\alpha=(n+1)(nm+2\rho)$ in $G$, then $\varphi$
is satisfiable.

###### Proof.

First note that an OCT of $G$ must either contain a vertex cover of each
$P^{*}_{i},i\in[n]$ or contain all of $A$ or $B$. Since $|A|=|B|>\alpha$, we
can assume the existence of an OCT $T$ of size $\alpha$ satisfying the first
condition. Hence $T$ contains at least half of the vertices of paths
$P^{*}_{i},i\in[n]$, that is, at least $nm\cdot(n+1)$ vertices in total. Since
we need at least two additional vertices to intersect the odd cycles of every
arrow (even if an endpoint of the arrow is part of $T$), and that there are
$\rho$ of them, we conclude that $T$ contains precisely $nm\cdot(n+1)$
vertices from $P^{*}_{1},\dots,P^{*}_{n}$, and $2\rho\cdot(n+1)$ vertices from
the arrows. Now, observe that a vertex cover of size $k$ in a path of size
$2k$ may contain at most once two consecutive vertices. Since $P^{*}_{i}$’s
are made from $n+1$ repetitions of $n$ paths, there exists $G_{j},j\in[n+1]$
for which none of the paths $P^{j}_{i},i\in[n]$ contains consecutive vertices
from $T$. We construct a truth assignment $\tau$ for $\varphi$ out of these
paths as follows. For a variable $x_{i},i\in[n]$ we set $\tau(x_{i})$ to true
if the vertices of $T$ coincide with odd vertices of $P^{j}_{i}$, and
$\tau(x_{i})$ to false otherwise.

Since every clause cycle in $G_{j}$ has to be hit by $T$, and $T$ already
contains $\alpha$ vertices from $P^{*}_{1},\dots,P^{*}_{n}$ and the arrows, we
conclude that each clause cycle in $G_{j}$ contains at least one incoming
arrow $A(u,v)$ with $v\in T$. Hence $T$ contains at least three vertices from
that arrow; see Figure 3. Since $T$ intersects $A(u,v)-\\{u\\}$ on at most two
vertices, the only way to hit every cycle of $A(u,v)$ that way is for $T$ to
contain $\\{u,a_{2},v\\}$: the arrow is active and $T$ contains $u$. By
construction, the variable corresponding to vertex $u$ satisfies the clause in
$\varphi$. We conclude to a satisfying truth assignment of $\varphi$ as
desired. ∎

######  Lemma 5.7.

The constructed graph $G$ satisfies $\mathbf{cw}(G)\leq\mathbf{lcw}(G)\leq
n/2+10$.

###### Proof.

We describe a construction of $G$ by a linear $K$-expression with $K=n/2+10$
labels. This proves $\mathbf{lcw}(G)\leq K$, and $\mathbf{cw}\leq\mathbf{lcw}$
follows from definition.

During the construction, $n/2$ labels will be used to maintain the current
path extremities, grouped two by two. These labels are indexed by $[n/2]$. Two
labels will be dedicated to build clause cycles, denoted $a$ and $b$. No more
than five labels will be used to build arrows, and to prolongate current paths
extremities. These labels are referred to as _working labels_ in the
following. At last, two labels will be used for the biclique induced by $A$
and $B$, and one _final_ label indexed by $0$ will contain the rest of the
graph: no further modifications will be made to vertices once they are put in
that label. We first construct the biclique with its two dedicated labels.
Then, we will construct the rest of $G$ from $G_{1}$ to $G_{n+1}$, column
after column (recall that columns consist of groups of two vertices from each
$P^{*}_{i},i\in[n]$), with each column constructed from top to bottom two rows
at a time. At each step, four vertices are added to the $P^{*}_{i}$’s, and the
gadgets are constructed along the way.

Let us focus on the graph $G_{1}$ and assume that we are currently
constructing the column described by indices $j,j+1$ for an odd $j\in[2m]$,
and are willing to construct rows $i,i+1$ of that column for an odd $i\in[n]$.
First, we create vertices $p_{i,j}$ and $p_{i+1,j}$ using one distinct working
label for each, call them $y_{1}$ and $y_{2}$, respectively. If one of
$p_{i,j}$ and $p_{i+1,j}$, name it $u$, participates to an arrow $A(u,c_{k})$
linking $u$ to a clause cycle $\widehat{C}$ on vertex $c_{k},k\in[|C|]$, we
construct that arrow using other working labels. Clearly, three additional
labels suffice to proceed with the construction of the arrow (not counting
label 0). The vertices of the clause cycles will in fact be constructed by
adding arrows one after the other. When creating arrow $A(u,c_{k})$, $c_{k}$
is joined with label $a$, the vertex labeled $a$ is relabeled 0, and $c_{k}$
is relabeled $a$. We point out that the order of the vertices in the cycle
does not matter. Note that to this extent, we only need three labels for
$\widehat{C}$: two labels $a$ and $b$ for the extremities of paths that
constitute the cycle for now, and label $0$ for internal vertices in these
path (they will not be joined anymore). We point out that during the
construction of the column described by $j,j+1$, only the clause cycle
$\widehat{C}$ is constructed. When finishing to build the column, the possible
extra vertices that were added to $\widehat{C}$ so that it is of odd size are
added by joins between $a$ and a working label, emptying label $a$, and
labeling them $a$. Once all vertices of $\widehat{C}$ have been added, the
cycle is closed by joining labels $a$ and $b$, which are then relabeled to $0$
and hence, labels $a$ and $b$ are free to be used for the next column.

When constructing an arrow, we move every internal vertex in
$A(u,v)\setminus\\{u,v\\}$ that has edges to all of its neighbours into label
$0$. Then, we join $p_{i,j}$ and $p_{i+1,j}$ to the extremities of paths
$P^{*}_{i}$,$P^{*}_{i+1}$ if they exist by joining label $\left\lceil
i/2\right\rceil$ (containing the extremities of these paths only) to $y_{1}$
and $y_{2}$. This yields the crossing edges described in Figure 4. We then
rename label $\left\lceil i/2\right\rceil$ to 0. Lastly, we join $p_{i,j}$ and
$p_{i+1,j}$ accordingly to $A$ and $B$.

The creation of vertices $p_{i,j+1}$ and $p_{i+1,j+1}$ follows the same
principle regarding the gadgets. Only we join them to $p_{i,j}$ and
$p_{i+1,j}$ using working labels $z_{1}$ and $z_{2}$ for $p_{i,j+1}$ and
$p_{i+1,j+1}$, respectively, and joining $y_{1}$ to $z_{1}$ and $y_{2}$ to
$z_{2}$. This is followed by renaming $y_{1}$ and $y_{2}$ to $0$. The vertices
labeled $z_{1}$ and $z_{2}$ can each be renamed to $\left\lceil
i/2\right\rceil$ as soon as joins to $y_{1}$ and $y_{2}$ respectively, and to
neighbours in the possible arrow are done.

Repeating this process to the next row, column, until $G_{n+1}$ is constructed
yields our graph $G$ with the desired number of labels. ∎

Observe that here we deduced a lower bound for the parameter linear clique-
width from a lower bound for the parameter pathwidth. Both parameters are
respectively a linearized version of clique-width and a linearized version of
treewidth, the parameters of the algorithms for which we prove tight
complexity.

##  Appendix A Appendix

######  Lemma A.1.

Given a $k$-expression of a graph $G$ with associated tree $T$, if an edge of
$j$ appears in two join operations, then in $T$ the nodes associated to the
operations satisfy that one is an ancestor of the other. If we denote them
$a,b\in V(T)$ with $a$ the ancestor, then $b$ can be replaced by its child.

###### Proof.

Suppose edge $uv$ appears in two join operations associated to nodes
$t,t^{\prime}\in V(T)$.

Because vertices are introduced only once in a $k$-expression, the vertices
$s\in V(T)$ satisfying $u\in V(G_{s})$ are exactly the ancestors of the node
$s^{\prime}\in V(T)$ creating $u$. Because $t$ and $t^{\prime}$ must contain
$u$, this means that one of $t$ and $t^{\prime}$ is an ancestor of the other.
We denote $a$ the ancestor and $b$ the descendant. Denote by $i$ the label of
$u$ in $a$ and $i^{\prime}$ its label in $b$. Denote by $j$ the label of $v$
in $a$ and $j^{\prime}$ its label in $b$.

Note that because there is no operation that separates vertices that have the
same label, $V_{i^{\prime}}(G_{b})\subseteq V_{i}(G_{a})$ and
$V_{j^{\prime}}(G_{b})\subseteq V_{j}(G_{a})$. As $uv$ appears in the join
induced by nodes $a$ and $b$, it must be that the performed joins are
$\eta_{i\times j}$ and $\eta_{i^{\prime}\times j^{\prime}}$, respectively.
These joins introduce edges $A=\\{xy:x\in V_{i}(G_{a}),\ y\in V_{j}(G_{a})\\}$
and $B=\\{xy:x\in V_{i^{\prime}}(G_{b}),\ y\in V_{j^{\prime}}(G_{b})\\}$. From
the previous inclusions, we deduce $B\subseteq A$. Hence, if $b$ is replaced
by its child in $T$, which removes $b$ from the tree of the expression, the
constructed graph is the unchanged. ∎

######  Lemma A.2.

Given a $k$-expression of a graph $G$, and its associated tree $T$, there is
an algorithm running in time $\mathcal{O}(k^{2}\cdot|V(T)|)$ that produces a
$k$-expression of $G$ with associated tree $T^{\prime}$ in which every edge of
$G$ appears once in a join node, and such that each join node introduces an
edge (i.e., it does not involve an empty label).

###### Proof.

We will make two traversals of $T$: the first one will determine the nodes to
be removed in $T$, while the second will compute the desired $k$-expression
tree $T^{\prime}$. Let $R$ be a table of Boolean variables indexed by vertices
of $T$, and which will indicate vertices to be deleted from $T$; this variable
is global and has its values initialized to $\bot$. The first traversal of $T$
is described by the function FindRepetition, which, given a node $t\in V(T)$,
computes for each pair of labels $\\{i,j\\}$ a list $L(i,j)$ of join nodes of
$T$, descendant of $t$ and taken maximal w.r.t. the ancestor-descendant
relation $\leq$, involving edges between vertices that are currently in labels
$i$ and $j$. Recall that by Lemma A.1, these joins are in fact redundant:
every edge involved in one such join is an edge involved in the join of the
current node $t$. The function also computes, for each label $i$, a Boolean
value $B[i]$ indicating whether label $i$ is nonempty. This will be used in
order to detect and remove trivial join involving an empty label.

We now describe the computation of FindRepetition according to each type of
node in the $k$-expression.

Leaf node.

If $t=i(v)$ is a leaf node, we set:

  * •

$L(a,b):=\varnothing$ for all $a,b\in[k]$;

  * •

$B[i]=\top$; and

  * •

$B[j]=\bot$ for all $j\neq i$.

Disjoint node.

If $t=t_{1}\oplus t_{2}$, we call FindRepetition on $t_{1}$ and $t_{2}$,
respectively returning $(L_{1},B_{1})$ and $(L_{2},B_{2})$. Then, we set:

  * •

$L(i,j):=L_{1}(i,j)\sqcup L_{2}(i,j)$ for all $i,j\in[k]$, where $\sqcup$
denotes the list concatenation; and

  * •

$B[i]:=B_{1}[i]\cup B_{2}[i]$ for all $i\in[k]$.

Join node.

If $t=\eta_{i\times j}(t^{\prime})$, we call FindRepetition on $t^{\prime}$,
returning $(L^{\prime},B^{\prime})$. We then set $B:=B^{\prime}$, and proceed
as follows:

  * •

for $\\{a,b\\}\neq\\{i,j\\}$, we set $L(a,b):=L^{\prime}(a,b)$;

  * •

for $\\{i,j\\}$, if $B[i]=\bot$ or $B[j]=\bot$, we set $R[t]:=\top$ and
$L(i,j):=\varnothing$; and

  * •

otherwise, we set $L(i,j):=(t)$, and for each $s\in L^{\prime}(i,j)$, we set
$R[s]:=\top$.

Renaming label node.

If $t=\rho_{i\rightarrow j}(t^{\prime})$, we call FindRepetition on
$t^{\prime}$ and gets $(L^{\prime},B^{\prime})$ as its return. Then:

  * •

for $\\{a,b\\}$ such that $i,j\notin\\{a,b\\}$, we set
$L(a,b):=L^{\prime}(a,b)$;

  * •

for $\\{a,i\\}$, we set $L(a,i):=\varnothing$.

  * •

for $\\{a,j\\}$, $a\neq i$, we set $L(a,i):=L^{\prime}(a,i)\sqcup
L^{\prime}(a,j)$;

  * •

we set $B[i]:=\bot$, $B[j]:=B^{\prime}[i]\cup B^{\prime}[j]$; and

  * •

for all $a\in[k]\setminus\\{i,j\\}$, we set $B[a]:=B^{\prime}[a]$.

The second traversal of the tree simply consists in replacing nodes $t$ such
that $R[t]=\top$ by their child, as in Lemma A.1.

For the complexity analysis, first note that using double linked for $L(i,j)$,
attributions and concatenations may be performed in $\mathcal{O}(1)$ time.
Parsing $L(i,j)$ in join nodes takes at most $\mathcal{O}(n)$ time in total,
because each node is put in at most one list, and the list is discarded after
it is parsed. The conclusion follow from the fact that there are
$\mathcal{O}(k^{2})$ pairs of labels, and $n$ nodes in $T$.

In order to prove the correctness, we make the following observations.

  * •

If $R[t]=\top$, $t$ is either a trivial join node (involving an empty label),
or a join node that can be replaced by its child from $T$ by Lemma A.1.

  * •

At node $t$, $B[i]=\top$ if and only if there is a vertex labeled $i$.

  * •

At node $t$, $L(i,j)$ contains exactly join nodes $s$ that added an edge
between a vertex labeled $i$ for $t$ and a vertex labeled $j$ for $t$ and such
that $R[s]=\bot$.

  * •

At join node $t$ joining $i$ and $j$, for all join nodes $s$ under $t$ that
added an edge between a vertex labeled $i$ for $t$ and a vertex labeled $j$
for $t$, $R[s]=\top$, and if $R[t]=\bot$, it adds at least one edge.

It is straightforward to prove these claims by induction on $t$. From them we
can conclude. ∎

## References

  * [BBBK20] Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, and O-joung Kwon.  Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth.  In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), volume 180 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [BCKN15] Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof.  Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth.  Inf. Comput., 243:86–111, 2015.
  * [BKN+18] Marthe Bonamy, Lukasz Kowalik, Jesper Nederlof, Michal Pilipczuk, Arkadiusz Socala, and Marcin Wrochna.  On directed feedback vertex set parameterized by treewidth.  In Andreas Brandstädt, Ekkehard Köhler, and Klaus Meer, editors, Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, volume 11159 of Lecture Notes in Computer Science, pages 65–78. Springer, 2018.
  * [BST19] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.  Hitting minors on bounded treewidth graphs. IV. an optimal algorithm.  CoRR, abs/1907.04442, 2019.
  * [BST20a] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.  Hitting minors on bounded treewidth graphs. I. general upper bounds.  SIAM J. Discret. Math., 34(3):1623–1648, 2020.
  * [BST20b] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.  Hitting minors on bounded treewidth graphs. II. single-exponential algorithms.  Theor. Comput. Sci., 814:135–152, 2020.
  * [BST20c] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos.  Hitting minors on bounded treewidth graphs. III. lower bounds.  J. Comput. Syst. Sci., 109:56–77, 2020.
  * [BSTV13] Binh-Minh Bui-Xuan, Ondrej Suchý, Jan Arne Telle, and Martin Vatshelle.  Feedback vertex set on graphs of low clique-width.  Eur. J. Comb., 34(3):666–679, 2013.
  * [CER93] Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg.  Handle-rewriting hypergraph grammars.  J. Comput. Syst. Sci., 46(2):218–270, 1993.
  * [CFK+15] Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.  Parameterized algorithms, volume 5.  Springer, 2015.
  * [CKN18] Marek Cygan, Stefan Kratsch, and Jesper Nederlof.  Fast hamiltonicity checking via bases of perfect matchings.  J. ACM, 65(3):12:1–12:46, 2018.
  * [CMPP17] Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk.  Hitting forbidden subgraphs in graphs of bounded treewidth.  Inf. Comput., 256:62–82, 2017.
  * [CMR00] Bruno Courcelle, Johann A. Makowsky, and Udi Rotics.  Linear time solvable optimization problems on graphs of bounded clique-width.  Theory Comput. Syst., 33(2):125–150, 2000.
  * [CNP+11] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk.  Solving connectivity problems parameterized by treewidth in single exponential time.  In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 150–159. IEEE Computer Society, 2011.
  * [Cou90] Bruno Courcelle.  The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.  Inf. Comput., 85(1):12–75, 1990.
  * [FGL+19] Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  Clique-width III: hamiltonian cycle and the odd case of graph coloring.  ACM Trans. Algorithms, 15(1):9:1–9:27, 2019.
  * [FGLS10] Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh.  Intractability of clique-width parameterizations.  SIAM J. Comput., 39(5):1941–1956, 2010.
  * [FGLS14] Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh.  Almost optimal lower bounds for problems parameterized by clique-width.  SIAM J. Comput., 43(5):1541–1563, 2014.
  * [FHRV08] Samuel Fiorini, Nadia Hardy, Bruce A. Reed, and Adrian Vetta.  Planar graph bipartization in linear time.  Discret. Appl. Math., 156(7):1175–1180, 2008.
  * [Klo94] Ton Kloks.  Treewidth: computations and approximations, volume 842.  Springer Science & Business Media, 1994.
  * [LMS11a] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.  Known algorithms on graphs of bounded treewidth are probably optimal.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 777–789. SIAM, 2011.
  * [LMS11b] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.  Slightly superexponential parameterized problems.  In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 760–776. SIAM, 2011.
  * [LMS18a] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.  Known algorithms on graphs of bounded treewidth are probably optimal.  ACM Trans. Algorithms, 14(2):13:1–13:30, 2018.
  * [LMS18b] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.  Slightly superexponential parameterized problems.  SIAM J. Comput., 47(3):675–702, 2018.
  * [MRRS12] Pranabendu Misra, Venkatesh Raman, MS Ramanujan, and Saket Saurabh.  Parameterized algorithms for even cycle transversal.  In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 172–183. Springer, 2012.
  * [Pil11] Michal Pilipczuk.  Problems parameterized by treewidth tractable in single exponential time: A logical approach.  In Filip Murlak and Piotr Sankowski, editors, Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011. Proceedings, volume 6907 of Lecture Notes in Computer Science, pages 520–531. Springer, 2011.
  * [RS84] Neil Robertson and Paul D. Seymour.  Graph minors. III. planar tree-width.  J. Comb. Theory, Ser. B, 36(1):49–64, 1984.
  * [SdSS20] Ignasi Sau and Uéverton dos Santos Souza.  Hitting forbidden induced subgraphs on bounded treewidth graphs.  In Javier Esparza and Daniel Král’, editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 82:1–82:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [Wan94] Egon Wanke.  k-nlc graphs and polynomial algorithms.  Discret. Appl. Math., 54(2-3):251–266, 1994.


#  $S$-matrix approach to general gravity and beyond111IPhT-T21/019, CERN-
TH-2021-062
Contribution to the 2021 Gravitation session of the 55th Rencontres de Moriond
March 9-11, 2021.

Pierre Vanhove  Institut de Physique Theorique, Université Paris-Saclay, CEA,
CNRS, F-91191 Gif-sur-Yvette Cedex, France
National Research University Higher School of Economics, Russian Federation
Theoretical Physics Department, CERN, 1211 Geneva 23, Switzerland

###### Abstract

In this text we outline the motivation for developping a quantum $S$-matrix
approach for the classical gravitational two-body scattering. As an
application we briefly present the derivation of black-hole metrics in various
dimensions.

##  1 Motiviation

The detection of the first gravitational wave signal has opened an area of
_precision_ gravity. The measurement of the gravitational wave signal is a
formidable window on gravity at various scales, involving the dynamics of
black holes. This gives precious information on Einstein gravity and possibly
gravitational physics beyond it. Ultimately, this would tell us how good we
understand gravity both in the weak and strong coupling regimes. The binary
mergers detected until now by the LIGO-Virgo [1, 2] collaboration are clean
sources of gravitational waves and the gravitational-wave signal is currently
modelled by general relativity in vacuum, at accuracy close to second order in
the mass ratio parameter. The next generation gravitational-wave detectors,
such as the Laser Interferometer Space Antenna (LISA) will be sensitive to the
environement of the sources and the signal will be more “dirty” [3]. The lack
of clear predictions for nonlinearities (from the accretion disk for instance)
in the post-merger phase means that these could be confused with modifications
of the signal predicted by theories beyond general relativity.

For this we need to produce accurate theoretical gravitational waveform
templates. We have to clarify how much can be understood from exact
theoretical computations. We have to answer the questions about how much we
understand about gravity in the weak and strong coupling regime. And whether
we can learn about gravitational physics beyond Einstein gravity, like
modified gravity scenarii (extra dimensions, massive gravity, …), or quantum
effects.

In this context it is important to work with gravity effective field theories.
Although the status of the high-energy behaviour of quantum gravity is still
open, considering effective field theory of gravity at low energy does not
pose a problem. One can safely extract low-energy physics from the
quantization of the gravitational interactions observables that are
independent of the high-energy behaviour. There are the classical
contributions (post-Minkowskian expansion) but as well infra-red effects which
are only sensitive to low-energy degrees of freedom. As argued by J. D.
Bjorken [4] […] as an open theory, quantum gravity is arguably our best
quantum field theory, not the worst.

##  2 Classical gravity from quantum $S$-matrix

Einstein’s theory of gravity is the first term of an effective field theory
coupling gravity to matter [5, 6]

${\cal S}_{EH}=\int d^{4}x\sqrt{-g}\Bigg{[}\frac{R}{16\pi
G_{N}}+g^{\mu\nu}T_{\mu\nu}^{\rm matter}+\mathcal{L}_{\rm
corrections}\Bigg{]}\,.$ (1)

We assume that the effective field theory satisfies the standard requierements
of locality, unitarity and Lorentz invariance, and of course that the theory
is diffeomorphism invariant (i.e. we have the symmetries of General
relativity). The low-energy degrees of freedom are the massless graviton and
the usual massive matter fields.

We are interested in extracting physical observables from the gravitational
interactions222One could as well include electro-magnetic interactions as
considered in [7] but in this text we will only consider the exchange of the
graviton and focus on the gravitational sector. between two massive body of
masses $m_{i}$ and spin $S_{i}$ with $i=1,2$ interacting via the exchange of
massless spin-2 graviton [8, 9, 10, 11, 12]. The two-body scattering matrix

${\mathcal{M}}(p_{1},p_{2},p_{1}^{\prime},p_{2}^{\prime})=\\!\\!\\!\\!\begin{gathered}\includegraphics[width=42.67912pt]{2body.pdf}\end{gathered}\\!\\!\\!\\!=\sum_{L\,=\,0}^{\infty}\mathcal{M}_{L}(p_{1},p_{2},p_{1}^{\prime},p_{2}^{\prime}),$
(2)

can be expanded in perturbation $\mathcal{M}_{L}\sim{\cal O}(G_{N}^{L+1})$.
The quantum scattering matrix
${\mathcal{M}}(p_{1},p_{2},p_{1}^{\prime},p_{2}^{\prime})$ depends on the
incoming energy $p_{1}\cdot p_{2}/(m_{1}m_{2})$, the momentum transfer
$(p_{1}-p_{1}^{\prime})^{2}=q^{2}$ and $\hbar$. At a given order in
perturbation one gets the exchange of gravitons (curly lines) between massive
external matters (solid lines)

From the limit $\hbar\to 0$ with $q^{2}/\hbar$ held fixed of the quantum
scattering amplitudes [14, 15, 16] , one can extract the classical Hamiltonian
$\mathcal{H}_{\rm PM}(p,r)$ for the gravitational interactions between two
classical massive body in general dimensions

$\lim_{"\hbar\to
0"}\begin{gathered}\includegraphics[width=42.67912pt]{2body.pdf}\end{gathered}=\sqrt{p^{2}+m_{1}^{2}}+\sqrt{p^{2}+m_{2}^{2}}+\sum_{L\geq
0}G_{N}^{L+1}V_{\rm L+1-PM}(p,r).$ (3)

The relativistic potential $G_{N}^{L+1}V_{\rm L+1-PM}(p,r)=\sum_{n\geq
0}c_{L,n}G_{N}^{L+1}v^{n}$, with $p=p_{1}-p_{1}^{\prime}=(E,v)$, resums an
infinite number of post-Newtonian contributions in the small velocity
expansion $v/c\ll 1$. The approach described here works in any space-time
dimension and applies to gravity in higher dimensions [17, 18]. We will see an
illustration of this when discussing the black hole metric in section 3.

By computing the two-body scattering in perturbation one derives a Lorentz
invariant expression valid in all regime of relative velocity between the two
interacting massive bodies. The scattering amplitude approach completes the
post-Newtonian computations by providing information beyond its regime of
validity, and leads to surprising results connecting the conservative part and
gravitational radiation effects [19, 20, 21, 22, 23, 24, 25, 26]. It gives a
new perspective on the traditional methods [27, 28, 29, 30, 31] used for
computing the gravitational wave templates. This approach allows to connect
the resummed post-Newtonian results [32, 33, 34] and the high-energy behaviour
[35, 24].

##  3 The Schwarzschild-Tangherlini metric from scalar field amplitudes

The Nobel prize citation for Roger Penrose states that “black hole formation
is a robust prediction of the general theory of relativity”. Subrahmanyan
Chandrasekhar explained that they are the most perfect macroscopic objects
there are in the universe since the only elements in their construction are
our concepts of space and time. Black-hole solutions are a perfect play ground
to validate the formalism of deriving classical gravity from quantum
scattering amplitudes. This also opens new avenues for studying black holes in
generalized theories of gravity.

In 1973 Duff analyzed [36] the question of the classical limit of quantum
gravity by extracting the Schwarzschild back hole metric from quantum tree
graphs to $G_{N}^{3}$ order. This was a consistency check on the way classical
Einstein’s gravity is embedded into the standard massless spin-2 quantization
of the gravitational interactions.

By evaluating the vertex function of the emission of a graviton from a
particle of mass $m$, spin $S$ and charge $Q$, in $d$ dimensions

$\begin{gathered}\includegraphics{gravemission.pdf}\end{gathered}=-{i\sqrt{32\pi
G_{N}}\over 2}\sum_{l\geq 0}\langle
T^{(l)\,\mu\nu}(q^{2})\rangle\epsilon_{\mu\nu}$ (4)

with the action

$\mathcal{S}=\int d^{d+1}x\sqrt{-g}\left({R\over 16\pi
G_{N}}+\frac{1}{2}g^{\mu\nu}\partial_{\mu}\phi\partial_{\nu}\phi-\frac{1}{2}m^{2}\phi^{2}\right)\,.$
(5)

one can extract the metric of physical black holes [58]

  * •

Schwarzschild black hole: Scalar field $S=0$, mass $m$ [13, 39, 37, 38]

  * •

Reissner-Nordström black hole: Scalar field $S=0$, charge $Q$, mass $m$ [7]

  * •

Kerr-Newman black hole: Fermionic field $S=\frac{1}{2}$, charge $Q$, mass $m$
[37, 7]

At each loop order we extract the $l$-loop contribution to the transition
density of the stress-energy tensor $\langle
T_{\mu\nu}(q^{2})\rangle=\sum_{l\geq 0}\langle T^{(l)}_{\mu\nu}(q^{2})\rangle$

$i\mathcal{M}^{(l)}_{3}(p_{1},q)=-{i\sqrt{32\pi G_{N}}\over 2}\langle
T^{(l)\,\mu\nu}(q^{2})\rangle\epsilon_{\mu\nu},$ (6)

where $\epsilon^{\mu\nu}$ is the polarisation of the graviton with momentum
$q=p_{1}-p_{2}$ is the momentum transfer.

The scattering amplitude computation is not done in the harmonic gauge
coordinates $g^{\mu\nu}\Gamma^{\lambda}_{\mu\nu}(g)=0$ but in the de Donder
gauge coordinate system [9, 39, 40, 41, 42]

${\eta^{\mu\nu}}\Gamma^{\lambda}_{\mu\nu}(g)={\eta^{\mu\nu}}g^{\lambda\rho}\left({\partial
g_{\rho\mu}\over\partial x^{\nu}}+{\partial g_{\rho\nu}\over\partial
x^{\mu}}-{\partial g_{\mu\nu}\over\partial x^{\rho}}\right)=0$ (7)

the metric perturbations $g_{\mu\nu}=\eta_{\mu\nu}+\sum_{n\geq
1}h^{(n)}_{\mu\nu}$ satisfy333The harmonic gauge linearized at the first order
in perturbation gives (8) with $n=1$. The higher-order expansions of the
harmonic gauge differ from these conditions.

${\partial\over\partial
x^{\lambda}}h^{\lambda(n)}_{\nu}-\frac{1}{2}{\partial\over\partial
x^{\nu}}h^{(n)}=0\,.$ (8)

The de Donder gauge relation between the metric perturbation and the stress-
energy tensor reads

$h^{(l+1)}_{\mu\nu}(\vec{x})=-16\pi
G_{N}\int{d^{d}{\vec{q}}\over(2\pi)^{d}}e^{i\vec{q}\cdot\vec{x}}{1\over\vec{q}^{2}}\left(\langle
T_{\mu\nu}^{(l)}\rangle^{\rm class.}(q^{2})-\frac{1}{d-1}\eta_{\mu\nu}\langle
T^{(l)}\rangle^{\rm class.}(q^{2})\right)\,.$ (9)

In this relation enters the classical contribution at $l$ loop order $\langle
T^{(l)}_{\mu\nu}\rangle^{\rm class.}(q^{2})$ defined by the classical limit of
the quantum scattering amplitude [14, 15, 16] and its application to black
hole solutions [59].

In [38], the Schwarzschild metric up to $G_{N}^{4}$ obtained in four ($d=3$),
five ($d=4$) and six ($d=5$) dimensions. The Schwarzschild-Tangherlini metric
in the de donder coordinate system

$ds^{2}=\left(1-4{d-2\over
d-1}\,{\rho(r,d)\over{f(r)}^{d-2}}\right)dt^{2}-{f(r)}^{2}d\vec{x}^{2}-\left(-{f(r)}^{2}-{f(r)}^{d-2}{({f(r)}+r{d{f(r)}\over
dr})^{2}\over{f(r)}^{d-2}-4{d-2\over d-1}\rho(r,d)}\right){(\vec{x}\cdot
d\vec{x})^{2}\over\vec{x}^{2}}$ (10)

and to the first order the components of the metric are given [38] In four
dimensions ($d=3$)444Similar results are obtained in higher dimensions where
we matched the Schwarzschild-Tangherlini up to the order $G_{N}^{4}$.

$h^{\rm
dD}_{0}(r)=1-\frac{2G_{N}m}{r}+2\left(\frac{G_{N}m}{r}\right)^{2}+2\left(\frac{G_{N}m}{r}\right)^{3}+\left(\frac{4}{3}{\log\left(\frac{rC_{3}}{G_{N}m}\right)}-6\right)\left(G_{N}m\over
r\right)^{4}+\cdots$ (11) $h^{\rm
dD}_{1}(r)=1+2\frac{G_{N}m}{r}+5\left(\frac{G_{N}m}{r}\right)^{2}+\left({4\over
3}{\log\left(\frac{rC_{3}}{G_{N}m}\right)}+4\right)\left(G_{N}m\over
r\right)^{3}\cr+\left(-\frac{4}{3}\log\left(\frac{rC_{3}}{G_{N}m}\right)+\frac{16}{3}\right)\left(G_{N}m\over
r\right)^{4}+\left(\frac{64}{15}\log\left(\frac{rC_{3}}{G_{N}m}\right)-\frac{26}{75}\right)\left(G_{N}m\over
r\right)^{5}\cr+\Bigg{(}\frac{4}{9}{\log\left(\frac{rC_{3}}{G_{N}m}\right)^{2}}-\frac{24}{5}\log\left(\frac{rC_{3}}{G_{N}m}\right)+\frac{298}{75}\Bigg{)}\left(G_{N}m\over
r\right)^{6}+\cdots$

One notices that in this gauge the metric components contain finite-size
powers of $\log(rC_{3}/G_{N}m)$ where $C_{3}$ is the single constant of
integration. These logarithms are generated by the cancellation of the
ultraviolet divergences of the scattering amplitudes in (6) regulated by the
introduction of higher-derivative non-minimal couplings [39, 42, 38]. These
contributions are finite size effects [39, 43, 29, 44, 45, 46, 47, 48]. At the
level of the metric components, they are reabsorbed in the coordinate change
from the de Donder gauge used for the amplitude computation to the standard
Schwarzschild-Tangherlini metric in spherical coordinates

$ds^{2}=\left(1-4{d-2\over
d-1}\rho(r,d)\right)dt^{2}-d{\vec{x}}^{2}-{4{d-2\over d-1}\rho(r,d)\over
1-4{d-2\over d-1}\rho(r,d)}{(\vec{x}\cdot d\vec{x})^{2}\over
r^{2}};\qquad\rho(r,d)={\Gamma\left(d-2\over 2\right)\over\pi^{d-2\over
2}}{G_{N}m\over r^{d-2}}\,,$ (12)

and the finite-size effects do not affect the static metric.

##  4 Discussion

General relativity can be considered in space-times of various dimensions.
Gravity is richer in higher dimensions as black-hole solutions develop non
trivial properties in general dimensions [49, 50]. It is therefore important
to validate our current understanding of the connection between the quantum
scattering amplitudes and classical general relativity in general dimensions
[17, 18]. By reproducing the classical Schwarzschild-Tangherlini metric from
scattering amplitudes in four, five and six dimensions, we validate the
procedure for extracting the classical piece from the quantum scattering
amplitudes. The method can be applied to derive other black-hole metrics, like
the Kerr-Newman and Reissner-Nordström metrics by considering the vertex
function of the emission of the graviton from a massive particle with spin and
charge. [7, 37, 51, 52, 53, 54, 55, 56].

The scattering amplitude approach presented in this work can be applied to any
effective field theory of gravity coupled to matter fields. One can include
quantum corrections in (9) and examine the impact of quantum effects on the
black hole solution [37]. Or study the impact of higher derivative
contributions to the gravitational waves templates.

The amplitudes computations, being performed in general dimensions, lead to
results that have an analytic dependence on the space-time dimensions.

The higher order post-Minkowskian contributions should be obtained from
higher-loop amplitudes in a direct application of the methods described here.
Up to the third Post-Minkowskian order one can extract the classical
conservative potential and scattering angle of binary system in pure gravity
and maximal supergravity [57, 32, 33, 34, 22, 35, 24, 26].

We have improved our understanding of the relation between general relativity
and the quantum theory of gravity. This leads to many new exciting
developpements leading to a better understanding of the gravitational
interactions in binary system. This provides new techniques that can be
applied to any gravitational effective field theories which have amplitude
description : opening the possibility to search for deviation from Einstein
gravity.

## Acknowledgements

We would like to thank Emil Bjerrum-Bohr, Poul Damgaard, Stavros Mougiakakos
and Ludovic Planté for collaboration on the work reported here. The research
of P. Vanhove has received funding from the ANR grant “Amplitudes” ANR-17-
CE31-0001-01, and the ANR grant “SMAGP” ANR-20-CE40-0026-01 and is partially
supported by Laboratory of Mirror Symmetry NRU HSE, RF Government grant, ag.
No 14.641.31.0001.

## References

## References

  * [1] B. P. Abbott et al. [LIGO Scientific and Virgo], “Observation of Gravitational Waves from a Binary Black Hole Merger,” Phys. Rev. Lett. 116 (2016) no.6, 061102 [arXiv:1602.03837 [gr-qc]].
  * [2] B. P. Abbott et al. [LIGO Scientific and Virgo], “GW170817: Observation of Gravitational Waves from a Binary Neutron Star Inspiral,” Phys. Rev. Lett. 119 (2017) no.16, 161101 [arXiv:1710.05832 [gr-qc]].
  * [3] E. Barausse, E. Berti, T. Hertog, S. A. Hughes, P. Jetzer, P. Pani, T. P. Sotiriou, N. Tamanini, H. Witek and K. Yagi, et al. “Prospects for Fundamental Physics with Lisa,” Gen. Rel. Grav. 52 (2020) no.8, 81 doi:10.1007/s10714-020-02691-1 [arXiv:2001.09793 [gr-qc]].
  * [4] J. D. Bjorken, “The Future of Particle Physics,” Int. J. Mod. Phys. A 16 (2001), 483-502 [arXiv:hep-ph/0006180 [hep-ph]].
  * [5] J. F. Donoghue, “Leading Quantum Correction to the Newtonian Potential,” Phys. Rev. Lett. 72 (1994), 2996-2999 [arXiv:gr-qc/9310024 [gr-qc]].
  * [6] J. F. Donoghue, M. M. Ivanov and A. Shkerin, “Epfl Lectures on General Relativity as a Quantum Field Theory,” [arXiv:1702.00319 [hep-th]].
  * [7] J. F. Donoghue, B. R. Holstein, B. Garbrecht and T. Konstandin, “Quantum Corrections to the Reissner-NordstrÖm and Kerr-Newman Metrics,” Phys. Lett. B 529 (2002), 132-142 [erratum: Phys. Lett. B 612 (2005), 311-312] [arXiv:hep-th/0112237 [hep-th]].
  * [8] G. ’t Hooft and M. J. G. Veltman, “One Loop Divergencies in the Theory of Gravitation,” Ann. Inst. H. Poincare Phys. Theor. A 20 (1974), 69-94
  * [9] M. J. G. Veltman, “Quantum Theory of Gravitation,” Conf. Proc. C 7507281 (1975) 265.
  * [10] B. S. DeWitt, “Quantum Theory of Gravity. 1. The Canonical Theory,” Phys. Rev. 160 (1967), 1113-1148
  * [11] B. S. DeWitt, “Quantum Theory of Gravity. 2. The Manifestly Covariant Theory,” Phys. Rev. 162 (1967), 1195-1239
  * [12] B. S. DeWitt, “Quantum Theory of Gravity. 3. Applications of the Covariant Theory,” Phys. Rev. 162 (1967), 1239-1256
  * [13] D. Neill and I. Z. Rothstein, “Classical Space-Times from the S Matrix,” Nucl. Phys. B 877 (2013), 177-189 [arXiv:1304.7263 [hep-th]].
  * [14] B. R. Holstein and J. F. Donoghue, “Classical Physics and Quantum Loops,” Phys. Rev. Lett. 93 (2004), 201602 [arXiv:hep-th/0405239 [hep-th]].
  * [15] N. E. J. Bjerrum-Bohr, P. H. Damgaard, G. Festuccia, L. Planté and P. Vanhove, “General Relativity from Scattering Amplitudes,” Phys. Rev. Lett. 121 (2018) no.17, 171601 [arXiv:1806.04920 [hep-th]].
  * [16] D. A. Kosower, B. Maybee and D. O’Connell, “Amplitudes, Observables, and Classical Scattering,” JHEP 02 (2019), 137 [arXiv:1811.10950 [hep-th]].
  * [17] A. Koemans Collado, P. Di Vecchia and R. Russo, “Revisiting the second post-Minkowskian eikonal and the dynamics of binary black holes,” Phys. Rev. D 100 (2019) no.6, 066028 [arXiv:1904.02667 [hep-th]].
  * [18] A. Cristofoli, P. H. Damgaard, P. Di Vecchia and C. Heissenberg, “Second-order Post-Minkowskian scattering in arbitrary dimensions,” JHEP 07 (2020), 122 [arXiv:2003.10274 [hep-th]].
  * [19] T. Damour, “High-Energy Gravitational Scattering and the General Relativistic Two-Body Problem,” Phys. Rev. D 97 (2018) no.4, 044038 [arXiv:1710.10599 [gr-qc]].
  * [20] T. Damour, “Classical and Quantum Scattering in Post-Minkowskian Gravity,” Phys. Rev. D 102 (2020) no.2, 024060 [arXiv:1912.02139 [gr-qc]].
  * [21] T. Damour, “Radiative Contribution to Classical Gravitational Scattering at the Third Order in $G$,” Phys. Rev. D 102 (2020) no.12, 124008 [arXiv:2010.01641 [gr-qc]].
  * [22] J. Parra-Martínez, M. S. Ruf and M. Zeng, “Extremal Black Hole Scattering at $\mathcal{O}(G^{3})$: Graviton Dominance, Eikonal Exponentiation, and Differential Equations,” JHEP 11 (2020), 023 [arXiv:2005.04236 [hep-th]].
  * [23] P. Di Vecchia, C. Heissenberg, R. Russo and G. Veneziano, “Radiation Reaction from Soft Theorems,” [arXiv:2101.05772 [hep-th]].
  * [24] P. Di Vecchia, C. Heissenberg, R. Russo and G. Veneziano, “The Eikonal Approach to Gravitational Scattering and Radiation at $\mathcal{O}(G^{3})$,” [arXiv:2104.03256 [hep-th]].
  * [25] E. Herrmann, J. Parra-Martínez, M. S. Ruf and M. Zeng, “Radiative Classical Gravitational Observables at $\mathcal{O}(G^{3})$ from Scattering Amplitudes,” [arXiv:2104.03957 [hep-th]].
  * [26] N. E. J. Bjerrum-Bohr, P. H. Damgaard, L. Planté and P. Vanhove, “Classical Gravity from Loop Amplitudes,” [arXiv:2104.04510 [hep-th]].
  * [27] W. D. Goldberger, “Les Houches Lectures on Effective Field Theories and Gravitational Radiation,” [arXiv:hep-ph/0701129 [hep-ph]].
  * [28] L. Blanchet, “Gravitational Radiation from Post-Newtonian Sources and Inspiralling Compact Binaries,” Living Rev. Rel. 17 (2014), 2 [arXiv:1310.1528 [gr-qc]].
  * [29] R. A. Porto, “The Effective Field Theorist’s Approach to Gravitational Dynamics,” Phys. Rept. 633 (2016), 1-104 [arXiv:1601.04914 [hep-th]].
  * [30] L. Barack, V. Cardoso, S. Nissanke, T. P. Sotiriou, A. Askar, C. Belczynski, G. Bertone, E. Bon, D. Blas and R. Brito, et al. “Black Holes, Gravitational Waves and Fundamental Physics: a Roadmap,” Class. Quant. Grav. 36 (2019) no.14, 143001 [arXiv:1806.05195 [gr-qc]].
  * [31] S. Isoyama, R. Sturani and H. Nakano, “Post-Newtonian Templates for Gravitational Waves from Compact Binary Inspirals,” [arXiv:2012.01350 [gr-qc]].
  * [32] Z. Bern, C. Cheung, R. Roiban, C. H. Shen, M. P. Solon and M. Zeng, “Scattering Amplitudes and the Conservative Hamiltonian for Binary Systems at Third Post-Minkowskian Order,” Phys. Rev. Lett. 122 (2019) no.20, 201603 [arXiv:1901.04424 [hep-th]].
  * [33] Z. Bern, C. Cheung, R. Roiban, C. H. Shen, M. P. Solon and M. Zeng, “Black Hole Binary Dynamics from the Double Copy and Effective Theory,” JHEP 10 (2019), 206 [arXiv:1908.01493 [hep-th]].
  * [34] Z. Bern, J. Parra-Martínez, R. Roiban, M. S. Ruf, C. H. Shen, M. P. Solon and M. Zeng, “Scattering Amplitudes and Conservative Binary Dynamics at ${\cal O}(G^{4})$,” [arXiv:2101.07254 [hep-th]].
  * [35] P. Di Vecchia, C. Heissenberg, R. Russo and G. Veneziano, “Universality of Ultra-Relativistic Gravitational Scattering,” Phys. Lett. B 811 (2020), 135924 [arXiv:2008.12743 [hep-th]].
  * [36] M. J. Duff, “Quantum Tree Graphs and the Schwarzschild Solution,” Phys. Rev. D 7 (1973), 2317-2326
  * [37] N. E. J. Bjerrum-Bohr, J. F. Donoghue and B. R. Holstein, “Quantum Corrections to the Schwarzschild and Kerr Metrics,” Phys. Rev. D 68 (2003), 084005 [erratum: Phys. Rev. D 71 (2005), 069904] [arXiv:hep-th/0211071 [hep-th]].
  * [38] S. Mougiakakos and P. Vanhove, “Schwarzschild-Tangherlini Metric from Scattering Amplitudes in Various Dimensions,” Phys. Rev. D 103 (2021) no.2, 026001 [arXiv:2010.08882 [hep-th]].
  * [39] W. D. Goldberger and I. Z. Rothstein, “An Effective Field Theory of Gravity for Extended Objects,” Phys. Rev. D 73 (2006), 104029 [arXiv:hep-th/0409156 [hep-th]].
  * [40] C. Cheung and M. P. Solon, “Classical gravitational scattering at $\mathcal{O}(G^{3})$ from Feynman diagrams,” JHEP 06 (2020), 144 [arXiv:2003.08351 [hep-th]].
  * [41] A. K. Collado, P. Di Vecchia, R. Russo and S. Thomas, “The subleading eikonal in supergravity theories,” JHEP 10 (2018), 038 [arXiv:1807.04588 [hep-th]].
  * [42] G. U. Jakobsen, “Schwarzschild-Tangherlini Metric from Scattering Amplitudes,” Phys. Rev. D 102 (2020) no.10, 104065 [arXiv:2006.01734 [hep-th]].
  * [43] S. Foffa and R. Sturani, “Effective Field Theory Methods to Model Compact Binaries,” Class. Quant. Grav. 31 (2014) no.4, 043001 [arXiv:1309.3474 [gr-qc]].
  * [44] M. Accettulli Huber, A. Brandhuber, S. De Angelis and G. Travaglini, “From Amplitudes to Gravitational Radiation with Cubic Interactions and Tidal Effects,” Phys. Rev. D 103 (2021) no.4, 045015 [arXiv:2012.06548 [hep-th]].
  * [45] C. Cheung and M. P. Solon, “Tidal Effects in the Post-Minkowskian Expansion,” Phys. Rev. Lett. 125 (2020) no.19, 191601 [arXiv:2006.06665 [hep-th]].
  * [46] K. Haddad and A. Helset, “Tidal Effects in Quantum Field Theory,” JHEP 12 (2020), 024 [arXiv:2008.04920 [hep-th]].
  * [47] Z. Bern, J. Parra-Martínez, R. Roiban, E. Sawyer and C. H. Shen, “Leading Nonlinear Tidal Effects and Scattering Amplitudes,” [arXiv:2010.08559 [hep-th]].
  * [48] G. Kälin, Z. Liu and R. A. Porto, “Conservative Tidal Effects in Compact Binary Systems to Next-To-Leading Post-Minkowskian Order,” Phys. Rev. D 102 (2020), 124025 [arXiv:2008.06047 [hep-th]].
  * [49] R. Emparan and H. S. Reall, “Black Holes in Higher Dimensions,” Living Rev. Rel. 11 (2008), 6 [arXiv:0801.3471 [hep-th]].
  * [50] R. Emparan, R. Suzuki and K. Tanabe, “The large D limit of General Relativity,” JHEP 06 (2013), 009 [arXiv:1302.6382 [hep-th]].
  * [51] A. Guevara, A. Ochirov and J. Vines, “Scattering of Spinning Black Holes from Exponentiated Soft Factors,” JHEP 09 (2019), 056 [arXiv:1812.06895 [hep-th]].
  * [52] M. Z. Chung, Y. T. Huang, J. W. Kim and S. Lee, “The simplest massive S-matrix: from minimal coupling to Black Holes,” JHEP 04 (2019), 156 [arXiv:1812.08752 [hep-th]].
  * [53] N. Moynihan, “Kerr-Newman from Minimal Coupling,” JHEP 01 (2020), 014 [arXiv:1909.05217 [hep-th]].
  * [54] M. Z. Chung, Y. T. Huang and J. W. Kim, “Kerr-Newman stress-tensor from minimal coupling,” JHEP 12 (2020), 103 [arXiv:1911.12775 [hep-th]].
  * [55] A. Guevara, A. Ochirov and J. Vines, “Black-hole scattering with general spin directions from minimal-coupling amplitudes,” Phys. Rev. D 100 (2019) no.10, 104024 [arXiv:1906.10071 [hep-th]].
  * [56] A. Cristofoli, “Gravitational shock waves and scattering amplitudes,” JHEP 11 (2020), 160 [arXiv:2006.08283 [hep-th]].
  * [57] N. E. J. Bjerrum-Bohr, J. F. Donoghue and P. Vanhove, “On-Shell Techniques and Universal Results in Quantum Gravity,” JHEP 02 (2014), 111 [arXiv:1309.0804 [hep-th]].
  * [58] V. Vaidya, “Gravitational spin Hamiltonians from the S matrix,” Phys. Rev. D 91 (2015) no.2, 024017; [arXiv:1410.5348 [hep-th]].
  * [59] B. Maybee, D. O’Connell and J. Vines, “Observables and amplitudes for spinning particles and black holes,” JHEP 12 (2019), 156; [arXiv:1906.09260 [hep-th]].


* (75) S. Pal and Z. Sun, Tauberian-Cardy formula with spin, JHEP 01 (2020) 135, [arXiv:1910.07727].
  * (76) G. E. Andrews and B. C. Berndt, Ramanujan’s lost notebook (Part II).  Springer New York, 2009.
  * (77) K. Bringmann and A. Milas, W-Algebras, False Theta Functions and Quantum Modular Forms, I, International Mathematics Research Notices 2015 (2015), no. 21 11351–11387.
  * (78) K. Bringmann, A. Folsom, and A. Milas, Asymptotic behavior of partial and false theta functions arising from Jacobi forms and regularized characters, J. Math. Phys. 58 (2017), no. 1 011702, [arXiv:1604.01977].
  * (79) K. Bringmann and C. Nazaroglu, A Framework for Modular Properties of False Theta Functions, Research in the Mathematical Sciences 6 (2019), no. 3 1–23, [arXiv:1904.05377].
  * (80) D. Das, S. Datta, and S. Pal, Charged structure constants from modularity, JHEP 11 (2017) 183, [arXiv:1706.04612].
  * (81) P. Calabrese and J. Cardy, Quantum Quenches in Extended Systems, J. Stat. Mech. 0706 (2007) P06008, [arXiv:0704.1880].
  * (82) G. A. Kotousov and S. L. Lukyanov, Bethe state norms for the Heisenberg spin chain in the scaling limit, Nucl. Phys. B 947 (2019) 114748, [arXiv:1906.07081].
  * (83) G. A. Kotousov and S. L. Lukyanov, Spectrum of the reflection operators in different integrable structures, JHEP 02 (2020) 029, [arXiv:1910.05947].
  * (84) E. Ilievski, J. De Nardis, B. Wouters, J.-S. Caux, F. H. Essler, and T. Prosen, Complete Generalized Gibbs Ensembles in an Interacting Theory, Physical review letters 115 (2015), no. 15 157201.
  * (85) O. Fuentealba, H. A. González, M. Pino, and R. Troncoso, The anisotropic chiral boson, JHEP 11 (2019) 123, [arXiv:1909.02699].
  * (86) D. M. Hofman and B. Rollier, Warped Conformal Field Theory as Lower Spin Gravity, Nucl. Phys. B 897 (2015) 1–38, [arXiv:1411.0672].
  * (87) T. Azeyanagi, S. Detournay, and M. Riegler, Warped Black Holes in Lower-Spin Gravity, Phys. Rev. D 99 (2019), no. 2 026013, [arXiv:1801.07263].
  * (88) S. L. Lukyanov, Low energy effective Hamiltonian for the XXZ spin chain, Nucl. Phys. B 522 (1998) 533–549, [cond-mat/9712314].
  * (89) C. Jordan and K. Jordán, Calculus of Finite Differences, vol. 33.  American Mathematical Soc., 1965.
  * (90) A. Morozov and S. Shakirov, Introduction to integral discriminants, Journal of High Energy Physics 2009 (2009), no. 12 002.