# Decline and Fall of the ICALP 2008 Modular Decomposition algorithm

William Atherton  Department of Computer Science, University of Oxford
<EMAIL_ADDRESS>and  Dmitrii V. Pasechnik  Department of
Computer Science, University of Oxford<EMAIL_ADDRESS>
###### Abstract.

We provide a counterexample to a crucial lemma in ICALP 2008 paper [7],
invalidating the algorithm described there.

##  1\. Introduction

Graph modular decomoposition is an important technique in graph theory, and a
well-studied algorithmic problem, with dozens of different algorithms
published since the pioneering work [3], see e.g. [4]. One highly cited linear
time algorithm has been presented at ICALP 2008 [7], also publised as [6]. A
Java implementation [5] has been made available by the first author of
[loc.cit.]. An archival copy of this implementation can be found in [8]. As
well, a number of attempts has been made to implement it in a different
language, one of them by the first author of this note, as a part of an
undergraduate project [1] supervised by the second author in Spring of 2023.
At the testing phase of the implementation, done in SageMath [9], an example,
see Sect. 2, has been found which produced an obviously incorrect output. The
problem was traced back to a lemma in [6], which is invalidated by the
example. As well, the implementation [5] run on this example produced
basically the same incorrect output.

We contacted the authors of [6] in May 2023, who were quick to acknowledge the
problem to us. In March 2024 they published a revision [2] of [6], without
mentioning the problem in [loc.cit.] and in the associated with it
implementation [5], and without mentioning our communication. The main purpose
of this note is to publicise the problem in [6], [7], and thus to stop further
waste of time stemming from attempts to implement the incorrect algorithm.

$a$$i$$b$$e$$c$$d$$f$$g$$h$series////primeseries Figure 1. The modular
decomposition of $G$, with ”series”, resp. ”parallel” (abbreviated ”//”),
resp. ”prime”, nodes of the decomposition tree are show by blue, resp. red,
resp. green boxes.

We quickly recall that for a graph $G$ with the vertex set $V:=V(G)$, a
_module_ is a subset of vertices $M\subseteq V$ s.t. $M$ any two $x,y\in M$
cannot be distinguished by any $v\in V\setminus M$, i.e. $v$ is either
simultaneously adjacent to $x$ and $y$, or non-adjacent to $x$ and $y$.
Modules $V$ and singleton modules are called _trivial_. Note that connected
components of $G$ and of the complement graph $\overline{G}$ are modules. A
module $M$ can be properly contained in another module $M^{\prime}\neq M$, or
they can _overlap_ , in the sense that $M\cap M^{\prime}\neq\emptyset$, but
neither $M^{\prime}\subset M$, nor $M\subset M^{\prime}$. A module which does
not overlap any module is called _strong_. A _modular decomposition tree_ is a
recursive partition (also known as a laminar set family) of $V$ into strong
modules; an example may be see on Fig. 1. More details may be found in e.g.
[4].

##  2\. The example

The counterexample graph $G$ which was discovered is described here. Note that
not only its isomorphism type matters here, but the particular vertex
ordering—different orderings lead to different outcomes, for some of them the
result is correct. We mark nodes with letters $a$, $b$,…, $i$, to adhere to
the vertex labeling conventions of [5]. $G$ is the join of two graphs: the
4-cycle with an extra edge attached at a vertex, and the disjoint union of a
vertex and the 3-cycle. $G$ and its modular decomposition is shown on Fig. 1.

The implementation [5] on this example produces

    (SERIES, numChildren=5
        (label=e, neighbours:a,b,d,f,i), (label=b, neighbours:a,d,e,f,g,h,i),
        (label=c, neighbours:a,d,f,g,h,i),
        (PARALLEL, numChildren=2
            (label=g, neighbours:a,b,c,d,f,i), (label=h, neighbours:a,b,c,d,f,i)),
        (PARALLEL, numChildren=2
            (label=f, neighbours:b,c,e,g,h),
            (SERIES, numChildren=3
                (label=j, neighbours:a,b,c,d,e,g,h), (label=a, neighbours:b,c,d,e,g,h,i),
                (label=d, neighbours:a,b,c,e,g,h,i))))

which is obviously incorrect, there is no prime node! Or, alternatively, note
that the top series node contains 5 children, i.e. the corresponding quotient
graph is $K_{5}$, and in particular there must be an edge between the
singleton nodes $b$ and $c$. The latter would only be possible if $(b,c)$ was
an egde in $G$—which is not the case.

Alternatively one could compute the decomposition of the complement
$\overline{G}$ of $G$. Such decompositions must be “dual” to each other, in
the sense that one must swap meanings of “series” and “parallel“. Indeed, [5]
works correctly on $\overline{G}$ and produces, modulo the swap just
mentioned, the decomposition at Fig. 1.

    (PARALLEL, numChildren=2
        (SERIES, numChildren=2
            (label=f, neighbours:a,d,i),
            (PARALLEL, numChildren=3
                (label=i, neighbours:f), (label=a, neighbours:f), (label=d, neighbours:f))),
        (PRIME, numChildren=4
            (label=b, neighbours:c), (label=c, neighbours:b,e), (label=e, neighbours:c,g,h),
            (SERIES, numChildren=2
                (label=h, neighbours:e,g), (label=g, neighbours:e,h))))

##  3\. Faulty lemma

We were able to trace the flaw down to Lemma 4 in [7] (which is Lemma 3.1 in
the preprint version [6]). The latter lemma plays a crucial role in the proof
of correctness and is shown false on our example.

Let $x$ be an arbitrary vertex of $G$.

######  Lemma (Lemma 4 in [7]).

The nodes in the ordered list of trees resulting from refinement that do not
have marked children correspond exactly to the strong modules not containing
$x$.

First, note a typo in the statement of Lemma 4, which we corrected above in
boldface \- the missing “not”.

This is a misprint. The proof of the Lemma is clearly proving the statement
with “not” inserted. As well, the way it is used in the proof of Lemma 3 in
[7] also indicated the correct statement should have the missing “not”.

We now show where the algorithm is going wrong on $G$. It starts by choosing a
vertex $x$ to be the first pivot (this choice is arbitrary in the algorithm),
and recurses on $G(x)$, the set of the neigbours of $x$, a tentative (strong)
module. Then it processes the non-neighbours $\overline{G(x)}$, resulting in a
number of tentative modules as in (1), and, finally, does a refinement step:
rearranging tentative modules into the modules for the tree. For a detailed
complete description, see [7].

(1)
$\underbrace{T(N_{0})}_{G(x)},x,\underbrace{T(N_{1}),\ldots,T(N_{k})}_{\overline{G(x)}},$

Let the algorithm choose the vertex $i$ to be the first pivot. We get the
neighbours of $i$, $G(i)=\\{a,b,c,d,e,g,h\\},$ $\\{i\\}$, and
$\overline{G(i)}=\\{f\\}$.

It then recursively processes the neighbour partition. The recursively
computed modular decomposition for $G(i)$ can be seen on Fig. 1; one has to
remove $i$, $f$, and the two nontrivial decomposition tree nodes (strong
modules) containing $i$ (i.e. the two nested boxes on the left of the green
box).

The next step of the algorithm, “pull-forward”, is skipped, as there is only
one node, $f$, in $\overline{G(i)}$.

It then calculates the modular decomposition of $\overline{G(i)}$, which is
just the single-vertex tree consisting of $f$.

It then goes on to the refinement step, where the error lies.

The refinement process consists of Algorithms 1 and 2 from [7], which we copy
here verbatim. We process the following decomposition of the vertices of $G$
into subtrees of modules.

foreach  _vertex $v$_ do

Let $\alpha(v)$ be its incident active edges;

Refine the list of trees using $\alpha(v)$ according to algorithm 2, such
that:

if  _$v$ is to $x$’s left_ then

refine using left splits, and when a node is marked, mark it with “left”;

else if  _$v$ is to $x$’s right and refines a tree to $x$’s left_ then

refine using left splits, and when a node is marked, mark it with “left”;

else if  _$v$ is to $x$’s right and refines a tree to $x$’s right_ then

refine using right splits, and when a node is marked, mark it with “right”;

end if

end foreach

Algorithm 1 Refinement of the ordered list of trees (1) by the active edges

Let $T_{1},\ldots,T_{k}$ be the maximal subtrees in the forest whose leaves
are all in $X$;

Let $P_{1},\ldots,P_{\ell}$ be the set of parents of the $T_{i}$’s;

foreach  _non-prime $P_{m}$_ do

Let $A$ be the set of $P_{m}$’s children amongst the $T_{j}$’s, and $B$ its
remaining children;

Let $T_{a}$ either be the single tree in $A$ or the tree formed by unifying
the trees in $A$ under a common root, and define $T_{b}$ symmetrically;

Assign $P_{m}$’s label to $T_{a}$ and $T_{b}$;

if  _$P_{m}$ is a root_ then

Replace $P_{m}$ in the forest with either $T_{a},T_{b}$ (left split) or
$T_{b},T_{a}$ (right split)

else

Replace the children of $P_{m}$ with $T_{a}$ and $T_{b}$;

end if

Mark the roots of $T_{a}$ and $T_{b}$ as well as all their ancestors;

end foreach

foreach  _prime $P_{m}$_ do

Mark $P_{m}$ as well as all of its children and all of its ancestors;

end foreach

Algorithm 2 Refinement of an ordered list of trees by the set $X$

Lemma 4 is necessary for the correctness of the main algorithm. However, we
will be going through Algorithm 1 on the given example $G$, and show that its
result contradicts Lemma 4. We start its loop from vertex $f$. Then $v=f$ and
$\alpha(f)$ is the list of incident active edges of $f$.

######  Definition 1 ([7]).

An edge becomes _active_ when one of its endpoints is a pivot or if its
endpoints reside in different layers.

As $f$ is in its own layer, all its incident edges are active. Therefore
$\alpha(f)=\\{bf,cf,ef,gf,hf\\}$. Algorithm 2 is then run on the ordered list
of trees, with the set $X=\\{b,c,e,g,h\\}$.

It first calculates $T_{1},\ldots,T_{k}$, the maximal subtrees in the forest
whose leaves are all in $X$. The list of maximal subtrees in this case is a
single subtree corresponding to the whole of $X$ is given by the prime node in
Fig. 1, which we refer to as $T_{1}$.

$P_{1}$, the parent of $T_{1}$, is the topmost node from the modular
decomposition of $G(i)$.

As there is only one $P_{k}$, the outer loop is only run once, on $P_{1}$.

$A$ is the set of $P_{1}$’s children among the $T_{j}$’s, which is just the
singleton set $T_{1}$, and $B$ is the set of remaining children, which is the
singleton—the bottommost parallel node from the modular decomposition of
$G(i)$.

As $|A|=|B|=1$, we have that $T_{a}=A=T_{1}$, and $T_{b}=B$.

$P_{m}$ is a root, so $P_{m}$ is replaced by $T_{a},T_{b}$, as the subtree is
to the left of the pivot.

Then, the roots of $T_{a}$ and $T_{b}$ are marked, and so are all their
ancestors.

This means that the root of $T_{a}$, the prime node at the top of $T_{1}$, is
marked.

The algorithm then marks the children of all prime nodes marked this way, so
the children of the prime node at the top of $T_{1}$ is marked, meaning the
nodes $b,$ $c,$ $e,$ and the parallel node from $T_{1}$ are all marked.

This is a contradiction to Lemma 4. Lemma 4 states that the nodes in the
ordered list of trees resulting from refinement that do not have marked
children correspond exactly to the strong modules not containing $x$. This
means that the strong modules not containing $i$ must not have a marked child.
However, as you can see from Fig. 1, $T_{1}$ is a strong module not containing
$i$, but it has marked children. ∎

##  4\. Conclusion

From the implmentation point of view, the fact that the children of $T_{1}$
get marked means that when the Promotion step happens, the children of $T_{1}$
get split from $T_{1}$, and the $T_{1}$ node gets deleted. As the rest of the
algorithm assumes that strong modules not containing $x$ are not affected by
refinement, these nodes do not get reassembled back into a prime node, so you
get the error occuring in the example implementation, where the prime node is
missing.

This is a fundamental problem with the algorithm, as Lemma 4 is used to prove
correctness of the algorithm, and the fact that children of prime nodes get
marked in Lemma 2 is important for other cases of the algorithm to work
correctly. Apparently the idea is not easy to salvage, as [2] appears to take
a quite different approach, using LexBFS.

## References

  * [1] William Atherton  “Implementing Linear-time Modular Decomposition in SageMath” 3rd year project dissertation, supervised by D. Pasechnik, 2023  Department of Computer Science, Oxford University
  * [2] Derek Corneil, Michel Habib, Christophe Paul and Marc Tedder  “A recursive linear time modular decomposition algorithm via LexBFS”, 2024  arXiv:0710.3901 [cs.DM]
  * [3] T. Gallai  “Transitiv orientierbare Graphen”  In _Acta Math. Acad. Sci. Hung._ 18, 1967, pp. 25–66  DOI: 10.1007/BF02020961
  * [4] Michel Habib and Christophe Paul  “A survey of the algorithmic aspects of modular decomposition”  In _Computer Science Review_ 4.1, 2010, pp. 41–59  DOI: j.cosrev.2010.01.001
  * [5] Marc Tedder  “Homepage with a link to Java code” The page was removed in Nov. 2023, a copy is in [8]. A copy of the code, retrieved earlier, is included here., 2008  URL: https://web.archive.org/web/20231117180003/https://www.cs.toronto.edu/~mtedder/
  * [6] Marc Tedder, Derek Corneil, Michel Habib and Christophe Paul  “A recursive linear time modular decomposition algorithm via LexBFS”, 2008  arXiv:0710.3901v2 [cs.DM]
  * [7] Marc Tedder, Derek Corneil, Michel Habib and Christophe Paul  “Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations”  In _Automata, Languages and Programming_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 634–645  DOI: 10.1007/978-3-540-70575-8˙52
  * [8] “Archive of M. Tedder’s Java code for [7]”  URL: https://github.com/dimpase/MDTreeJavacode
  * [9] The SageMath Developers  “SageMath, the Sage Mathematics Software System”, 2024  DOI: 10.5281/zenodo.8042260


takes the canonical form in the $t$-parametrization, and each
$\mathrm{R}$-operator (63) contributes one $d\log$ factor,

$\displaystyle\omega(C)=\frac{dt_{1}}{t_{1}}\wedge\frac{dt_{2}}{t_{2}}\wedge\ldots\wedge\frac{dt_{2n-4}}{t_{2n-4}}\,.$
(153)

The described procedure is equivalent to the BCFW-decomposition and positroid
stratification of the Grassmannians in the context of ${\cal N}=4$ sYM
amplitudes Arkani-Hamed:2016byb .

Let us also note that the decomposition (146) is not unique. We could
represent the Grassmanian top cell by another sequence of
$\mathrm{R}$-operators. However, not every decomposition is compatible with
the monodromy (59). In other words, the Yangian symmetry could be not
immediately obvious if we use a decomposition other than (146).

It is also instructive to consider the decomposition (146) at $n=4$,

$\displaystyle r_{4}=\underbrace{{\rm R}_{32}}_{t_{4}}\underbrace{{\rm
R}_{43}}_{t_{3}}\underbrace{{\rm R}_{23}}_{t_{2}}\underbrace{{\rm
R}_{12}}_{t_{1}}\,|{\Omega_{4}}\rangle=\int\omega(C_{4})\,\Delta(C_{4})$ (154)

where we explicitly indicate the labeling of the one-fold integrations (63),
and
$|{\Omega_{4}}\rangle=[\mu_{1}\mu_{4}]^{2}\,\delta^{2}(\lambda_{1})\delta^{2}(\lambda_{4})$
(68). The sequence of $\mathrm{R}$-operators from (154) corresponds to the
following sequence of $C_{0}$ column transformations (151), such that
$\mathrm{R}_{ij}$ acts as $\vec{c}_{j}\to\vec{c}_{j}+t\vec{c}_{i}$,

$\displaystyle C_{0}:=\begin{pmatrix}1&0&0&0\\\
0&0&0&1\end{pmatrix}\overset{{\rm
R}_{12}}{\to}C_{1}:=\begin{pmatrix}1&t_{1}&0&0\\\
0&0&0&1\end{pmatrix}\overset{{\rm
R}_{23}}{\to}C_{2}:=\begin{pmatrix}1&t_{1}&t_{1}t_{2}&0\\\
0&0&0&1\end{pmatrix}\to$ (155) $\displaystyle\overset{{\rm
R}_{43}}{\to}C_{3}:=\begin{pmatrix}1&t_{1}&t_{1}t_{2}&0\\\
0&0&t_{3}&1\end{pmatrix}\overset{{\rm
R}_{32}}{\to}C_{4}:=\begin{pmatrix}1&t_{1}(1+t_{2}t_{4})&t_{1}t_{2}&0\\\
0&t_{3}t_{4}&t_{3}&1\end{pmatrix}\,,$

and $C_{i}$ represents $i$-th dimensional cell of ${\rm Gr}(2,4)$; and
$\omega(C_{4})$ is the canonical form (153).

##  Appendix C Details of integrability proofs for $R_{n}$

In this Appendix we provide proofs of the symmetry relations for the leading
singularities $R_{n}$ presented in Sect. 4.3. The line of argumentation is
similar to that of Sect. 4.1.2 where the Yangian symmetries of $r_{n}$ are
considered, but requires several extra technical details. We split the proof
in several steps. In C.1 we provide the spin-chain formulation of the Yangian
algebra generators and define the R-operators. The latter are employed in C.2
to represent $R_{n}$ as a product of R-operators acting on the pseudo-vacuum
state of the spin-chain. In C.3 we discuss the cyclic shift transformations of
the Yangian. In C.4 we provide several technical statements which are used in
the proof of the Yangian invariance relations in C.5.

###  C.1 R-operators, Lax-operators, and the monodromy matrix

Let us denote ${\cal H}_{i}^{(\delta_{i})}$ the space of homogeneous functions
of $Z_{i}$ of the homogeneity degree $\delta_{i}$, namely $H_{i}=\delta_{i}$
is the dual-conformal weight (90). An elementary block in the decomposition of
the leading singularities $R_{n}$ will be the R-operator. We will need to
introduce the spectral parameter $u$ in the R-operator,

$\displaystyle\left[{\rm
R}_{ij}^{(u)}\,G\right](Z_{i},Z_{j}):=\int\frac{dt}{t^{1+u}}G(Z_{i}+tZ_{j},Z_{j})\,.$
(156)

The ${\rm R}$-operator (156) acts in the tensor product ${\cal
H}_{i}^{(\delta_{i})}\otimes{\cal H}_{j}^{(\delta_{j})}$ and maps it into
${\cal H}_{i}^{(\delta_{i}-u)}\otimes{\cal H}_{j}^{(\delta_{j}+u)}$. In other
words, the ${\rm R}$-operator does not preserve the dual-conformal weight,

$\displaystyle\left[H_{1},{\rm R}_{12}^{(u)}\right]=-u{\rm
R}_{12}^{(u)}\,,\qquad\left[H_{2},{\rm R}_{12}^{(u)}\right]=u{\rm
R}_{12}^{(u)}\,.$ (157)

In order to construct the Yangian generators (95), we combine the dual-
conformal generators (92) in the $4\times 4$ matrix depending on the spectral
parameter $u$, and call it the Lax operator,

$\displaystyle\left[{\rm
L}(u)\right]^{I}{}_{J}=u\,\delta^{I}_{J}+Z^{I}\frac{\partial}{\partial
Z^{J}}\,.$ (158)

The Lax operator is a local object acting in one site of the spin chain. We
also decorate the Lax operator with the dual-conformal weight, ${\rm
L}_{i}^{(\delta)}(u)$, to indicate that it acts onto ${\cal
H}_{i}^{(\delta)}\otimes\mathbb{C}^{4}$. The matrix product of a pair of Lax
operators acting in the $i$-th and $j$-th sites has nice exchange relations
with the R-operators (156),

$\displaystyle{\rm R}^{(a)}_{ij}\,{\rm L}_{i}^{(\delta_{i})}(u)\,{\rm
L}_{j}^{(\delta_{j})}(v)\,={\rm L}_{i}^{(\delta_{i}-a)}(v)\,{\rm
L}_{j}^{(\delta_{j}+a)}(u)\,{\rm R}^{(a)}_{ij}\,,\qquad a=v-u$ (159)

and

$\displaystyle{\rm R}^{(a)}_{ji}\,{\rm L}_{i}^{(\delta_{i})}(u)\,{\rm
L}_{j}^{(\delta_{j})}(v)\,={\rm L}_{i}^{(\delta_{i}+a)}(u)\,{\rm
L}_{j}^{(\delta_{j}-a)}(v)\,{\rm R}^{(a)}_{ji}\,,\qquad
a=v-u-\delta_{i}+\delta_{j}\,.$ (160)

These local exchange relations are exactly what we need to establish the
symmetries of $R_{n}$.

A simple corollary of the exchange relation (159) is the dual-conformal
invariance (92) of the R-operator

$\displaystyle\left[{\rm
R}^{(a)}_{ij},\mathfrak{J}_{i}+\mathfrak{J}_{j}\right]=0\,.$ (161)

We form the monodromy matrix ${\rm T}(u)$ as the matrix product of the Lax
operators (158) acting on spin-chain sites $1,2,\ldots,n$,

$\displaystyle\left[{\rm T}(u)\right]^{I}{}_{J}:=\left[{\rm
L}_{1}(u)\right]^{I}{}_{K_{1}}\left[{\rm
L}_{2}(u)\right]^{K_{1}}{}_{K_{2}}\ldots\left[{\rm
L}_{n}(u)\right]^{K_{n-1}}{}_{J}\,.$ (162)

The monodromy matrix is a polynomial in the spectral parameter $u$. The
coefficients of the polynomial are the Yangian generators (95) acting in the
spin-chain sites $1,2,\ldots,n$,

$\displaystyle\left[{\rm
T}(u)\right]^{I}{}_{J}=u^{n}\delta^{I}_{J}+u^{n-1}\left[\mathfrak{J}^{(0)}\right]^{I}{}_{J}+u^{n-2}\left[\mathfrak{J}^{(1)}\right]^{I}{}_{J}+\sum_{k=2}^{n-1}u^{n-k-1}\left[\mathfrak{J}^{(k)}\right]^{I}{}_{J}\,,$
(163)

where we recall $\mathfrak{J}^{(0)}=\mathfrak{J}$ (93) and
$\mathfrak{J}^{(1)}=\widehat{\mathfrak{J}}$ (96).

###  C.2 From R-operators to the Grassmannian

We will need an analogue of the R-operator decomposition (67) for $R_{n}$. The
presentation in this Section parallels the one in Sect. B.4. We define the
pseudo-vacuum of the spin chain which belongs to ${\cal
H}^{(-4)}_{1}\otimes{\cal H}^{(-4)}_{n}$,

$\displaystyle|{\Omega_{n}}\rangle:=\delta^{4}(Z_{1})\,\delta^{4}(Z_{n})\,.$
(164)

In order to represent the leading singularities $R_{n}$, we act onto the
pseudo-vacuum by the product of $2n$ R-operators (156) as follows,

$\displaystyle R_{n}={\rm R}_{AB}^{(-1)}{\rm
R}_{BA}^{(-1)}\,|{\Phi_{n}}\rangle\,,$ (165)
$\displaystyle|{\Phi_{n}}\rangle:={\rm R}_{1A}^{(-4)}{\rm
R}_{nB}^{(-4)}\,\overrightarrow{\prod_{i=2}^{n-1}}\mathrm{R}_{i+1i}^{(0)}\,\cdot\,\overleftarrow{\prod_{i=1}^{n-2}}\mathrm{R}_{ii+1}^{(0)}\,|{\Omega_{n}}\rangle\,,$
(166)

where for the sake of further convenience we split the product into two
factors containing two and $2n-2$ R-operators, and we introduced a shorthand
notation $|{\Phi_{n}}\rangle$ for the latter product acting on the pseudo-
vacuum. The dual-conformal weight counting of the R-operators (157) enables us
to find the weights of $R_{n}$ and $|{\Phi_{n}}\rangle$,

$\displaystyle R_{n},\,|{\Phi_{n}}\rangle\in{\cal H}^{(-4)}_{A}\otimes{\cal
H}^{(-4)}_{B}\otimes{\cal H}^{(0)}_{1}\otimes\ldots\otimes{\cal
H}^{(0)}_{n}\,.$ (167)

The resulting expression in (165) coincides with the contour integral (41)
representation of $R_{n}$,

$\displaystyle R_{n}=\int\omega(C)\Delta(C,Z)\,.$ (168)

Here we use notations $\omega(C)$ for the measure (see (42) and (43))

$\displaystyle\omega(C):=\frac{(AB)^{2}\,D^{2n}C}{(12)(23)\ldots(n1)}\,,$
(169)

and for the delta-function constraints $\Delta(C,Z)$,

$\displaystyle\Delta(C,Z):=\prod_{r=1,2}\delta^{4}\left(\sum_{i\in\\{A,B,1,\ldots,n\\}}c_{i}^{r}Z_{i}\right)\,.$
(170)

The pseudo-vacuum state (164) $|{\Omega_{n}}\rangle=\Delta(C_{0},Z)$
corresponds to the following $2\times(2n+2)$-matrix,

$\displaystyle C_{0}=\begin{pmatrix}0&0&1&0&\dots&0&0\\\
0&0&0&0&\dots&0&1\end{pmatrix}\,.$ (171)

Each $\mathrm{R}$-operator in the products (165) and (166) contains one-fold
integration. Let us label the corresponding integration variables as
$t_{1},t_{2},\ldots,t_{2n}$ from right to the left. Each shift $Z_{i}\to
Z_{i}+tZ_{j}$ produced by ${\rm R}_{ij}$ induces the shift
$\vec{c}_{j}\to\vec{c}_{j}+t\vec{c}_{i}$ in the matrix $C_{0}$. Thus the
sequence of R-operators in (165) and (166) brings us from $C_{0}$ to the top-
cell of ${\rm Gr}(2,n+2)$ parametrized with $t_{1},\ldots,t_{2n}$. The measure
$\omega(C)$ (169) takes the following form

$\displaystyle\omega(C)=\frac{(t_{2n-2}t_{2n-3})^{3}}{\prod_{i=1}^{2n-4}t_{i}}\,\bigwedge_{i=1}^{2n}dt_{i}\,.$
(172)

which agrees with values of spectral parameters carried by R-operators (156)
in (165) and (166) .

###  C.3 Cyclicity of the Yangian

The Yangian generators are entries of the monodromy matrix, which is a matrix
product of the Lax operators. We will need the cyclic shift transformations of
the Yangian generators, which we formulate in terms of the monodromy matrix.

If a homogeneous function $|{\Psi}\rangle$ of momentum twistors
$Z_{1},\ldots,Z_{m}$ is annihilated by the off-diagonal entries of the
$4\times 4$ matrix formed as the matrix product of $m$ Lax operators (158) and
the action of the diagonal entries results in an eigenvalue
$\varphi(u,\delta)$,

$\displaystyle\left[{\rm L}_{1}^{(\delta_{1})}(u_{1})\ldots{\rm
L}_{m-1}^{(\delta_{m-1})}(u_{m-1})\,{\rm
L}_{m}^{(\delta_{m})}(u_{m})\right]^{I}{}_{J}\,|{\Psi}\rangle=\varphi(u,\delta)\,\delta^{I}_{J}\,|{\Psi}\rangle$
(173)

then the matrix product of the cyclically shifted Lax operators has a similar
action on $|{\Psi}\rangle$

$\displaystyle\left[{\rm L}_{m}^{(\delta_{m})}(u_{m}-4)\,{\rm
L}_{1}^{(\delta_{1})}(u_{1})\ldots{\rm
L}_{m-1}^{(\delta_{m-1})}(u_{m-1})\right]^{I}{}_{J}\,|{\Psi}\rangle=\varphi^{\prime}(u,\delta)\,\delta^{I}_{J}\,|{\Psi}\rangle$
(174)

with another eigenvalue $\varphi^{\prime}(u,\delta)$,

$\displaystyle\varphi^{\prime}(u,\delta)=\varphi(u,\delta)\cdot\frac{(u_{m}-4)(u_{m}-1+\delta_{m})}{u_{m}(u_{m}-1+\delta_{m})-\delta_{m}}\,.$
(175)

One can check this statement following Chicherin:2013ora .

###  C.4 Lemmas

Here we collect several technical statements which will be instrumental in
section C.5. In the following we deal with multiple products of the dual-
conformal generators and we adopt the matrix notations,

$\displaystyle\left(\mathfrak{J}_{a}\,\mathfrak{J}_{b}\right)^{I}{}_{J}:=\left(\mathfrak{J}_{a}\right)^{I}{}_{K}\left(\mathfrak{J}_{b}\right)^{K}{}_{J}\,,\quad\left(\mathfrak{J}_{a}\,\mathfrak{J}_{b}\,\mathfrak{J}_{c}\right)^{I}{}_{J}:=\left(\mathfrak{J}_{a}\right)^{I}{}_{K}\left(\mathfrak{J}_{b}\right)^{K}{}_{L}\left(\mathfrak{J}_{c}\right)^{L}{}_{J}\,,\;\ldots$
(176)

We observe that the products of several local dual-conformal generators
$\mathfrak{J}_{a}$ (92) acting at the same spin-chain site labeled by $a$ are
proportional to $\mathfrak{J}_{a}$,

$\displaystyle\left(\mathfrak{J}_{a}\,\mathfrak{J}_{a}\right)^{I}{}_{J}=(3+H_{a})\,\left(\mathfrak{J}_{a}\right)^{I}{}_{J}\,,$
(177)

and the proportionality coefficient can be considered as a number. Indeed, the
dual-conformal weight counting operator $H_{a}$ (90) commutes with the dual-
conformal generators. The latter equation enables us to invert the Lax
operator (158),

$\displaystyle\left[\mathrm{L}^{(\delta)}_{a}(-u-3-\delta)\,\mathrm{L}^{(\delta)}_{a}(u)\right]^{I}{}_{J}=u(-u-3-\delta)\,\delta^{I}_{J}\,.$
(178)

Simplifications of the products of the dual-conformal generators
$\mathfrak{J}_{A}$ and $\mathfrak{J}_{B}$ also appear when they act on
functions of the twistor line $Z_{A}\wedge Z_{B}$,

$\displaystyle Z_{A}\wedge
Z_{B}:\qquad\left(\mathfrak{J}_{A}\mathfrak{J}_{B}\right)^{I}{}_{J}=-\left(\mathfrak{J}_{A}\right)^{I}{}_{J}\,,\quad\qquad\left(\mathfrak{J}_{B}\mathfrak{J}_{A}\right)^{I}{}_{J}=-\left(\mathfrak{J}_{B}\right)^{I}{}_{J}\,.$
(179)

In particular, we will need the product of the dual-conformal transformations
$\bar{\mathfrak{J}}$ (93), which acts on the spin-chain sites $A$ and $B$,
restricted to this space,

$\displaystyle Z_{A}\wedge
Z_{B}:\qquad\left(\bar{\mathfrak{J}}\,\bar{\mathfrak{J}}\right)^{I}{}_{J}=-2\bar{\mathfrak{J}}^{I}{}_{J}\,.$
(180)

A special role is played by the product of two R-operators which appear on the
r.h.s. of (165), namely ${\rm R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}$. In view of
(161), the product is invariant under the dual-conformal transformations with
$\bar{\mathfrak{J}}$ (93),

$\displaystyle\left[{\rm R}_{AB}^{(-1)}{\rm
R}_{BA}^{(-1)},\bar{\mathfrak{J}}^{I}{}_{J}\right]=0\,,$ (181)

and it does not alter the dual-conformal weight

$\displaystyle\left[H_{a}\,,\,{\rm R}_{AB}^{(-1)}{\rm
R}_{BA}^{(-1)}\right]=0\;,\qquad a=A,B\,.$ (182)

Given an arbitrary function $G(Z_{A},Z_{B})$ with equal dual-conformal weights
w.r.t. both twistor points $A$ and $B$,

$\displaystyle H_{A}\,G=H_{B}\,G\,,$ (183)

one can show that ${\rm R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}G(Z_{A},Z_{B})$ is a
function of the twistor line $Z_{A}\wedge Z_{B}$, namely it is invariant under
shifts $Z_{A}\to Z_{A}+\epsilon Z_{B}$ and $Z_{B}\to Z_{B}+\epsilon Z_{A}$.
Let us apply this observation to eq. (165). Indeed, $|{\Phi_{n}}\rangle$
depends on twistors $Z_{A}$ and $Z_{B}$, and it carries equal dual-conformal
weights at points $A$ and $B$, see eq. (167). Then $R_{n}$ given in (165) is a
function of the line $Z_{A}\wedge Z_{B}$ in the twistor space.

The local exchange relations (159) and (160) result in the exchange relation
satisfied by ${\rm R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}$ with the product of Lax
operators $\mathrm{L}_{A}\mathrm{L}_{B}$,

$\displaystyle{\rm R}_{AB}^{(-1)}{\rm
R}_{BA}^{(-1)}\,\left[\mathrm{L}^{(-4)}_{A}(v+1)\mathrm{L}^{(-4)}_{B}(v)\right]^{I}{}_{J}=\left[\mathrm{L}^{(-4)}_{A}(v)\mathrm{L}^{(-4)}_{B}(v+1)\right]^{I}{}_{J}\,{\rm
R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}\,.$ (184)

Expanding the latter equation in powers of the spectral parameter $v$, we
reproduce the statement of the dual-conformal invariance (181) as well as the
following exchange relation, which is quadratic in the dual-conformal
generators (92),

$\displaystyle{\rm R}_{AB}^{(-1)}{\rm
R}_{BA}^{(-1)}\left[\mathfrak{J}_{B}+\mathfrak{J}_{A}\mathfrak{J}_{B}\right]^{I}{}_{J}=\left[\mathfrak{J}_{A}+\mathfrak{J}_{A}\mathfrak{J}_{B}\right]^{I}{}_{J}{\rm
R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}\,.$ (185)

In order to obtain more exchange relations which involve products of the dual-
conformal generators, we contract the latter relation with the dual-conformal
generators $\bar{\mathfrak{J}}$ (93), which commute with the product of the
R-operators, see (181),

$\displaystyle{\rm R}_{AB}^{(-1)}{\rm
R}_{BA}^{(-1)}\left[\bar{\mathfrak{J}}\,\mathfrak{J}_{B}+\bar{\mathfrak{J}}\,\mathfrak{J}_{A}\mathfrak{J}_{B}\right]^{I}{}_{J}=\left[\bar{\mathfrak{J}}\,\mathfrak{J}_{A}+\bar{\mathfrak{J}}\,\mathfrak{J}_{A}\mathfrak{J}_{B}\right]^{I}{}_{J}{\rm
R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}\,.$ (186)

In the following we work on the space of homogeneous functions carrying the
dual-conformal weight equal to $-4$. The products of the dual-conformal
generators from (186) simplify as follows on this space

$\displaystyle{\cal H}_{A}^{(-4)}\otimes{\cal
H}_{B}^{(-4)}\;:\qquad\begin{array}[]{l}\bar{\mathfrak{J}}\,\mathfrak{J}_{B}+\bar{\mathfrak{J}}\,\mathfrak{J}_{A}\mathfrak{J}_{B}=-\mathfrak{J}_{B}+\mathfrak{J}_{B}\mathfrak{J}_{A}\mathfrak{J}_{B}\,,\\\
\bar{\mathfrak{J}}\,\mathfrak{J}_{A}+\bar{\mathfrak{J}}\,\mathfrak{J}_{A}\mathfrak{J}_{B}=-\mathfrak{J}_{A}+\mathfrak{J}_{B}\mathfrak{J}_{A}-\mathfrak{J}_{A}\mathfrak{J}_{B}+\mathfrak{J}_{B}\mathfrak{J}_{A}\mathfrak{J}_{B}\,,\end{array}$
(189)

in view of (177). We take the sum of (185) and (186) and restrict the relation
to the space of homogeneous functions, since the dual-conformal weights are
not altered by ${\rm R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}$, see (182),

$\displaystyle{\cal H}_{A}^{(-4)}\otimes{\cal H}_{B}^{(-4)}\;:\qquad{\rm
R}_{AB}^{(-1)}{\rm
R}_{BA}^{(-1)}\left[\mathfrak{J}_{A}\mathfrak{J}_{B}+\mathfrak{J}_{B}\mathfrak{J}_{A}\mathfrak{J}_{B}\right]^{I}{}_{J}=\left[\mathfrak{J}_{B}\mathfrak{J}_{A}+\mathfrak{J}_{B}\mathfrak{J}_{A}\mathfrak{J}_{B}\right]^{I}{}_{J}{\rm
R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}$ (190)

According to the discussion around eq. (183), the r.h.s. of (190) is a
function of the twistor line $Z_{A}\wedge Z_{B}$. The product of the dual-
conformal generators
$\mathfrak{J}_{B}\mathfrak{J}_{A}+\mathfrak{J}_{B}\mathfrak{J}_{A}\mathfrak{J}_{B}$
from the r.h.s. of (190) vanishes on this space, see (179). Finally, after
rewriting the product of the dual-conformal generators in the l.h.s. of (183),

$\displaystyle{\cal H}_{A}^{(-4)}\otimes{\cal
H}_{B}^{(-4)}\;:\qquad\mathfrak{J}_{A}\mathfrak{J}_{B}+\mathfrak{J}_{B}\mathfrak{J}_{A}\mathfrak{J}_{B}=2\mathfrak{J}_{A}\mathfrak{J}_{B}+\bar{\mathfrak{J}}\,\mathfrak{J}_{A}\mathfrak{J}_{B},$
(191)

eq. (183) takes the following form

$\displaystyle{\cal H}_{A}^{(-4)}\otimes{\cal H}_{B}^{(-4)}\;:\qquad{\rm
R}_{AB}^{(-1)}{\rm
R}_{BA}^{(-1)}\left[2\mathfrak{J}_{A}\mathfrak{J}_{B}+\bar{\mathfrak{J}}\,\mathfrak{J}_{A}\mathfrak{J}_{B}\right]^{I}{}_{J}=0\,.$
(192)

The relations established in this Section are required in the next Section.

###  C.5 Yangian invariances of $R_{n}$

We are going to establish how the Yangian generators from the monodromy matrix
expansion (163) act on the leading singularities $R_{n}$. To this end, we form
an auxiliary monodromy matrix out of the Lax operators (158) taken in the
order $A,1,2,\ldots,n,B$. The auxiliary monodromy matrix acts diagonally on
the pseudo-vacuum state $|{\Omega_{n}}\rangle$ (164),

$\displaystyle\left[{\rm L}_{A}^{(0)}(u){\rm L}_{1}^{(-4)}(u){\rm
L}_{2}^{(0)}(u)\ldots{\rm L}_{n-1}^{(0)}(u){\rm L}_{n}^{(-4)}(u+4){\rm
L}_{B}^{(0)}(u)\right]^{I}{}_{J}|{\Omega_{n}}\rangle=u^{n}(u-1)(u+3)\,\delta^{I}_{J}\,|{\Omega_{n}}\rangle\,,$
(193)

since each of the constituent Lax operators acts diagonally on the delta-
functions, see (158),

$\displaystyle\left[{\rm
L}_{i}(u)\right]^{I}{}_{J}\,\delta^{4}(Z_{j})=u\,\delta^{I}_{J}\,\delta^{4}(Z_{j})\;,\quad
i\neq j$ (194) $\displaystyle\left[{\rm
L}_{i}(u)\right]^{I}{}_{J}\,\delta^{4}(Z_{i})=(u-1)\,\delta^{I}_{J}\,\delta^{4}(Z_{i})\,.$
(195)

Then we act with $(2n-2)$ R-operators from (166) onto (193) and pull them
through the products of Lax operators by means of the local exchange relations
(159) and (160),

$\displaystyle\left[{\rm L}^{(-4)}_{A}(u){\rm L}_{1}^{(0)}(u){\rm
L}_{2}^{(0)}(u)\ldots{\rm L}_{n-1}^{(0)}(u){\rm L}_{n}^{(0)}(u){\rm
L}_{B}^{(-4)}(u+4)\right]^{I}{}_{J}|{\Phi_{n}}\rangle=u^{n}(u-1)(u+3)\,\delta^{I}_{J}\,|{\Phi_{n}}\rangle\,.$
(196)

We apply the cyclicity of App. C.3 to the previous monodromy relation
cyclically shifting the ordering of the Lax operators from $A,1,2,\ldots,n,B$
to $B,A,1,2,\ldots,n$ and replacing the monodromy matrix
$\mathrm{L}_{1}\ldots\mathrm{L}_{n}$ with the shorthand notation (162),

$\displaystyle\left[{\rm L}_{B}^{(-4)}(u){\rm L}_{A}^{(-4)}(u){\rm
T}(u)\right]^{I}{}_{J}|{\Phi_{n}}\rangle=u^{n}(u-1)^{2}\,\delta^{I}_{J}\,|{\Phi_{n}}\rangle\,,$
(197)

and we invert $\mathrm{L}_{A}$ and $\mathrm{L}_{B}$ on the l.h.s. of the
previous equation by means of (178),

$\displaystyle\left[{\rm
T}(u)\right]^{I}{}_{J}\,|{\Phi_{n}}\rangle=u^{n-2}\left[\mathrm{L}^{(-4)}_{A}(1-u)\mathrm{L}_{B}^{(-4)}(1-u)\right]^{I}{}_{J}|{\Phi_{n}}\rangle\,.$
(198)

We need to act with ${\rm R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}$ on both sides of
(198) in order to promote $|{\Phi_{n}}\rangle$ to the leading singularities
$R_{n}$ according to (165). This is straightforward in the l.h.s. of (198). If
we could pull this R-operator product through $\mathrm{L}_{A}\mathrm{L}_{B}$
in the r.h.s. of (198) then we would find that $R_{n}$ is invariant under all
Yangian generators. However, the latter is not true. The obstacle is that
values of spectral parameters in $\mathrm{L}_{A}\mathrm{L}_{B}$ in the r.h.s.
of (198) are not adjusted like in (184).

In order to obtain symmetry relations for $R_{n}$, we expand (198) in the
spectral parameter taking into account definitions in (163), (93) and (96),

$\displaystyle
u^{n-1}\;:\quad\mathfrak{J}^{I}{}_{J}|{\Phi_{n}}\rangle=-\bar{\mathfrak{J}}^{I}{}_{J}|{\Phi_{n}}\rangle-2\delta^{I}_{J}|{\Phi_{n}}\rangle\,,$
(199) $\displaystyle
u^{n-2}\;:\quad\widehat{\mathfrak{J}}^{I}{}_{J}|{\Phi_{n}}\rangle=\delta^{I}_{J}|{\Phi_{n}}\rangle+\bar{\mathfrak{J}}^{I}{}_{J}|{\Phi_{n}}\rangle+\left(\mathfrak{J}_{A}\mathfrak{J}_{B}\right)^{I}{}_{J}|{\Phi_{n}}\rangle\,,$
(200) $\displaystyle
u^{n-1-k}\;:\quad\left(\mathfrak{J}^{(k)}\right)^{I}{}_{J}|{\Phi_{n}}\rangle=0\;,\quad
k=2,\ldots,n-1\,.$ (201)

We act with ${\rm R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}$ onto (199) and (201) and
replace there $|{\Phi_{n}}\rangle$ with $R_{n}$ according to (165). Indeed,
the R-operators are dual-conformal invariant, see eq. (181). Thus, (199) is
equivalent to the dual-conformal invariance of the leading singularities
$R_{n}$ (161), while (201) is equivalent to the Yangian invariance of $R_{n}$
with the level-two and higher-level Yangian generators (97). Only (200) cannot
be immediately interpreted as the Yangian invariance relation, since ${\rm
R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}$ does not commute nicely with
$\mathfrak{J}_{A}\mathfrak{J}_{B}$ in the last term on the r.h.s. of (200).

Upon contraction of (200) with the tensor
$\langle{Z_{A},Z_{B},*,\star}\rangle$ the unwanted terms drop out,

$\displaystyle\epsilon_{IKLM}Z^{K}_{A}Z^{L}_{B}\,\widehat{\mathfrak{J}}^{I}{}_{J}\,|{\Phi_{n}}\rangle=\epsilon_{JKLM}Z^{K}_{A}Z^{L}_{B}\,|{\Phi_{n}}\rangle\,,$
(202)

and the latter relation is equivalent to (98) since both ${\rm R}_{AB}$ and
${\rm R}_{BA}$, which act as shifts on twistors $Z_{A}$ and $Z_{B}$, commute
with $\langle{Z_{A},Z_{B},*,\star}\rangle$.

Another way to acquire a symmetry relation with the level-one Yangian
generators $\widehat{\mathfrak{J}}$ from (200) is to cook up a polynomial in
the local dual-conformal generators $\mathfrak{J}_{A}$ and $\mathfrak{J}_{B}$
which nicely commutes with ${\rm R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}$. We have
established in (192) that this is the case for
$\bar{\mathfrak{J}}\,\mathfrak{J}_{A}\mathfrak{J}_{B}+2\mathfrak{J}_{A}\mathfrak{J}_{B}$.
Indeed, contracting (200) with $\bar{\mathfrak{J}}^{K}{}_{I}+2\delta^{K}_{I}$
we organize the unwanted terms into this polynomial,

$\displaystyle\left(\bar{\mathfrak{J}}\,\widehat{\mathfrak{J}}+2\widehat{\mathfrak{J}}\right)^{I}{}_{J}|{\Phi_{n}}\rangle=2\delta^{I}_{J}|{\Phi_{n}}\rangle+3\bar{\mathfrak{J}}^{I}{}_{J}|{\Phi_{n}}\rangle+\left(\bar{\mathfrak{J}}\,\bar{\mathfrak{J}}\right)^{I}{}_{J}|{\Phi_{n}}\rangle+\left(\bar{\mathfrak{J}}\,\mathfrak{J}_{A}\mathfrak{J}_{B}+2\mathfrak{J}_{A}\mathfrak{J}_{B}\right)^{I}{}_{J}|{\Phi_{n}}\rangle\,.$
(203)

We act on the previous relation with ${\rm R}_{AB}^{(-1)}{\rm R}_{BA}^{(-1)}$
pulling it through $\bar{\mathfrak{J}}$ (181), replacing
$\bar{\mathfrak{J}}\,\bar{\mathfrak{J}}\to-2\bar{\mathfrak{J}}$ according to
(180), and throwing out the last term on the r.h.s. in view of (192),

$\displaystyle\left(\bar{\mathfrak{J}}\,\widehat{\mathfrak{J}}+2\widehat{\mathfrak{J}}\right)^{I}{}_{J}\,R_{n}=2\delta^{I}_{J}\,R_{n}+\bar{\mathfrak{J}}^{I}{}_{J}\,R_{n}\,.$
(204)

The latter is the symmetry relation (99).

## References

  * (1) O. Almelid, C. Duhr and E. Gardi, _Three-loop corrections to the soft anomalous dimension in multileg scattering_ , _Phys. Rev. Lett._ 117 (2016) 172002 [1507.00047].
  * (2) L. F. Alday and J. M. Maldacena, _Gluon scattering amplitudes at strong coupling_ , _JHEP_ 06 (2007) 064 [0705.0303].
  * (3) J. M. Drummond, J. Henn, G. P. Korchemsky and E. Sokatchev, _Conformal Ward identities for Wilson loops and a test of the duality with gluon amplitudes_ , _Nucl. Phys._ B826 (2010) 337 [0712.1223].
  * (4) J. M. Drummond, J. M. Henn and J. Plefka, _Yangian symmetry of scattering amplitudes in N=4 super Yang-Mills theory_ , _JHEP_ 05 (2009) 046 [0902.2987].
  * (5) N. Arkani-Hamed, F. Cachazo, C. Cheung and J. Kaplan, _A Duality For The S Matrix_ , _JHEP_ 03 (2010) 020 [0907.5418].
  * (6) N. Arkani-Hamed, J. L. Bourjaily, F. Cachazo, A. B. Goncharov, A. Postnikov and J. Trnka, _Grassmannian Geometry of Scattering Amplitudes_. Cambridge University Press, 4, 2016, 10.1017/CBO9781316091548, [1212.5605].
  * (7) N. Arkani-Hamed, J. L. Bourjaily, F. Cachazo, S. Caron-Huot and J. Trnka, _The All-Loop Integrand For Scattering Amplitudes in Planar N=4 SYM_ , _JHEP_ 01 (2011) 041 [1008.2958].
  * (8) N. Arkani-Hamed and J. Trnka, _The Amplituhedron_ , _JHEP_ 10 (2014) 030 [1312.2007].
  * (9) J. L. Bourjaily, A. DiRe, A. Shaikh, M. Spradlin and A. Volovich, _The Soft-Collinear Bootstrap: N=4 Yang-Mills Amplitudes at Six and Seven Loops_ , _JHEP_ 03 (2012) 032 [1112.6432].
  * (10) J. L. Bourjaily, P. Heslop and V.-V. Tran, _Amplitudes and Correlators to Ten Loops Using Simple, Graphical Bootstraps_ , _JHEP_ 11 (2016) 125 [1609.00007].
  * (11) B. Eden, P. Heslop, G. P. Korchemsky and E. Sokatchev, _Hidden symmetry of four-point correlation functions and amplitudes in N=4 SYM_ , _Nucl. Phys. B_ 862 (2012) 193 [1108.3557].
  * (12) B. Eden, P. Heslop, G. P. Korchemsky and E. Sokatchev, _Constructing the correlation function of four stress-tensor multiplets and the four-particle amplitude in N=4 SYM_ , _Nucl. Phys._ B862 (2012) 450 [1201.5329].
  * (13) R. G. Ambrosio, B. Eden, T. Goddard, P. Heslop and C. Taylor, _Local integrands for the five-point amplitude in planar N=4 SYM up to five loops_ , _JHEP_ 01 (2015) 116 [1312.1163].
  * (14) L. J. Dixon, J. M. Drummond and J. M. Henn, _Bootstrapping the three-loop hexagon_ , _JHEP_ 11 (2011) 023 [1108.4461].
  * (15) J. M. Drummond, G. Papathanasiou and M. Spradlin, _A Symbol of Uniqueness: The Cluster Bootstrap for the 3-Loop MHV Heptagon_ , _JHEP_ 03 (2015) 072 [1412.3763].
  * (16) A. B. Goncharov, M. Spradlin, C. Vergu and A. Volovich, _Classical Polylogarithms for Amplitudes and Wilson Loops_ , _Phys. Rev. Lett._ 105 (2010) 151605 [1006.5703].
  * (17) J. Golden, A. B. Goncharov, M. Spradlin, C. Vergu and A. Volovich, _Motivic Amplitudes and Cluster Coordinates_ , _JHEP_ 01 (2014) 091 [1305.1617].
  * (18) S. Caron-Huot, L. J. Dixon, A. McLeod and M. von Hippel, _Bootstrapping a Five-Loop Amplitude Using Steinmann Relations_ , _Phys. Rev. Lett._ 117 (2016) 241601 [1609.00669].
  * (19) S. Caron-Huot, L. J. Dixon, F. Dulat, M. Von Hippel, A. J. McLeod and G. Papathanasiou, _The Cosmic Galois Group and Extended Steinmann Relations for Planar $\mathcal{N}=4$ SYM Amplitudes_, _JHEP_ 09 (2019) 061 [1906.07116].
  * (20) S. Caron-Huot, L. J. Dixon, J. M. Drummond, F. Dulat, J. Foster, O. Gürdoğan et al., _The Steinmann Cluster Bootstrap for $N$ = 4 Super Yang-Mills Amplitudes_, _PoS_ CORFU2019 (2020) 003 [2005.06735].
  * (21) J. M. Henn, _What can we learn about QCD and collider physics from $N$=4 super Yang-Mills?_, _Ann. Rev. Nucl. Part. Sci._ 71 (2021) 87 [2006.00361].
  * (22) J. M. Drummond, J. Henn, G. P. Korchemsky and E. Sokatchev, _Dual superconformal symmetry of scattering amplitudes in N=4 super-Yang-Mills theory_ , _Nucl. Phys. B_ 828 (2010) 317 [0807.1095].
  * (23) S. Weinzierl, _Does one need the $O(\epsilon)-$ and $O(\epsilon^{2})$-terms of one-loop amplitudes in an NNLO calculation ?_, _Phys. Rev. D_ 84 (2011) 074007 [1107.5131].
  * (24) C. Anastasiou and G. Sterman, _Removing infrared divergences from two-loop integrals_ , _JHEP_ 07 (2019) 056 [1812.03753].
  * (25) L. F. Alday, P. Heslop and J. Sikorowski, _Perturbative correlation functions of null Wilson loops and local operators_ , _JHEP_ 03 (2013) 074 [1207.4316].
  * (26) O. Erdoğan and G. Sterman, _Gauge Theory Webs and Surfaces_ , _Phys. Rev. D_ 91 (2015) 016003 [1112.4564].
  * (27) L. F. Alday, J. M. Henn and J. Sikorowski, _Higher loop mixed correlators in N=4 SYM_ , _JHEP_ 03 (2013) 058 [1301.0149].
  * (28) J. M. Henn, G. P. Korchemsky and B. Mistlberger, _The full four-loop cusp anomalous dimension in $\mathcal{N}=4$ super Yang-Mills and QCD_, _JHEP_ 04 (2020) 018 [1911.10174].
  * (29) N. Arkani-Hamed and J. Trnka, _Into the Amplituhedron_ , _JHEP_ 12 (2014) 182 [1312.7878].
  * (30) N. Arkani-Hamed, J. Henn and J. Trnka, _Nonperturbative Negative Geometries: Amplitudes at Strong Coupling and the Amplituhedron_ , 2112.06956.
  * (31) D. Chicherin and J. M. Henn, _to appear_ , .
  * (32) J. M. Drummond and L. Ferro, _Yangians, Grassmannians and T-duality_ , _JHEP_ 07 (2010) 027 [1001.3348].
  * (33) J. M. Drummond and L. Ferro, _The Yangian origin of the Grassmannian integral_ , _JHEP_ 12 (2010) 010 [1002.4622].
  * (34) G. P. Korchemsky and E. Sokatchev, _Superconformal invariants for scattering amplitudes in N=4 SYM theory_ , _Nucl. Phys. B_ 839 (2010) 377 [1002.4625].
  * (35) L. Ferro, T. Lukowski, A. Orta and M. Parisi, _Towards the Amplituhedron Volume_ , _JHEP_ 03 (2016) 014 [1512.04954].
  * (36) L. Ferro, T. Łukowski, A. Orta and M. Parisi, _Yangian symmetry for the tree amplituhedron_ , _J. Phys. A_ 50 (2017) 294005 [1612.04378].
  * (37) Y. Bai, S. He and T. Lam, _The Amplituhedron and the One-loop Grassmannian Measure_ , _JHEP_ 01 (2016) 112 [1510.03553].
  * (38) L. D. Faddeev, _How algebraic Bethe ansatz works for integrable model_ , in _Relativistic gravitation and gravitational radiation. Proceedings, School of Physics, Les Houches, France, September 26-October 6, 1995_ , pp. pp. 149–219, 1996, hep-th/9605187.
  * (39) E. K. Sklyanin, _Quantum inverse scattering method. Selected topics_ , hep-th/9211111.
  * (40) D. Chicherin, S. Derkachov and R. Kirschner, _Yang-Baxter operators and scattering amplitudes in N=4 super-Yang-Mills theory_ , _Nucl. Phys._ B881 (2014) 467 [1309.5748].
  * (41) R. Frassek, N. Kanning, Y. Ko and M. Staudacher, _Bethe Ansatz for Yangian Invariants: Towards Super Yang-Mills Scattering Amplitudes_ , _Nucl. Phys._ B883 (2014) 373 [1312.1693].
  * (42) N. Kanning, T. Lukowski and M. Staudacher, _A shortcut to general tree-level scattering amplitudes in $\mathcal{N}=4$ SYM via integrability_, _Fortsch. Phys._ 62 (2014) 556 [1403.3382].
  * (43) J. Broedel, M. de Leeuw and M. Rosso, _A dictionary between R-operators, on-shell graphs and Yangian algebras_ , _JHEP_ 06 (2014) 170 [1403.3670].
  * (44) T. Bargheer, Y.-t. Huang, F. Loebbert and M. Yamazaki, _Integrable Amplitude Deformations for N=4 Super Yang-Mills and ABJM Theory_ , _Phys. Rev. D_ 91 (2015) 026004 [1407.4449].
  * (45) L. V. Bork and A. I. Onishchenko, _On soft theorems and form factors in $\mathcal{N}=4$ SYM theory_, _JHEP_ 12 (2015) 030 [1506.07551].
  * (46) R. Frassek, D. Meidinger, D. Nandan and M. Wilhelm, _On-shell diagrams, Grassmannians and integrability for form factors_ , _JHEP_ 01 (2016) 182 [1506.08192].
  * (47) L. V. Bork and A. I. Onishchenko, _Wilson lines, Grassmannians and gauge invariant off-shell amplitudes in $\mathcal{N}=4$ SYM_, _JHEP_ 04 (2017) 019 [1607.02320].
  * (48) J. Fuksa and R. Kirschner, _Correlators with $s\ell_{2}$ Yangian symmetry_, _Nucl. Phys. B_ 914 (2017) 1 [1608.04912].
  * (49) R. Kirschner and G. Savvidy, _Yangian and SUSY symmetry of high spin parton splitting amplitudes in generalised Yang–Mills theory_ , _Mod. Phys. Lett. A_ 32 (2017) 1750121 [1701.06660].
  * (50) D. Chicherin, V. Kazakov, F. Loebbert, D. Müller and D.-l. Zhong, _Yangian Symmetry for Bi-Scalar Loop Amplitudes_ , _JHEP_ 05 (2018) 003 [1704.01967].
  * (51) D. Chicherin, V. Kazakov, F. Loebbert, D. Müller and D.-l. Zhong, _Yangian Symmetry for Fishnet Feynman Graphs_ , _Phys. Rev. D_ 96 (2017) 121901 [1708.00007].
  * (52) S. Badger, D. Chicherin, T. Gehrmann, G. Heinrich, J. M. Henn, T. Peraro et al., _Analytic form of the full two-loop five-gluon all-plus helicity amplitude_ , _Phys. Rev. Lett._ 123 (2019) 071601 [1905.03733].
  * (53) J. Henn, B. Power and S. Zoia, _Conformal Invariance of the One-Loop All-Plus Helicity Scattering Amplitudes_ , _JHEP_ 02 (2020) 019 [1911.12142].
  * (54) D. C. Dunbar, G. R. Jehu and W. B. Perkins, _The two-loop n-point all-plus helicity amplitude_ , _Phys. Rev. D_ 93 (2016) 125006 [1604.06631].
  * (55) R. Ben-Israel, A. G. Tumanov and A. Sever, _Scattering amplitudes — Wilson loops duality for the first non-planar correction_ , _JHEP_ 08 (2018) 122 [1802.09395].
  * (56) L. F. Alday and R. Roiban, _Scattering Amplitudes, Wilson Loops and the String/Gauge Theory Correspondence_ , _Phys. Rept._ 468 (2008) 153 [0807.1889].
  * (57) Z. Bern, L. J. Dixon and V. A. Smirnov, _Iteration of planar amplitudes in maximally supersymmetric Yang-Mills theory at three loops and beyond_ , _Phys. Rev. D_ 72 (2005) 085001 [hep-th/0505205].
  * (58) D. Chicherin, R. Doobary, B. Eden, P. Heslop, G. P. Korchemsky, L. Mason et al., _Correlation functions of the chiral stress-tensor multiplet in $\mathcal{N}=4$ SYM_, _JHEP_ 06 (2015) 198 [1412.8718].
  * (59) N. Berkovits and J. Maldacena, _Fermionic T-Duality, Dual Superconformal Symmetry, and the Amplitude/Wilson Loop Connection_ , _JHEP_ 09 (2008) 062 [0807.3196].
  * (60) B. Eden, P. Heslop, G. P. Korchemsky and E. Sokatchev, _The super-correlator/super-amplitude duality: Part I_ , _Nucl. Phys. B_ 869 (2013) 329 [1103.3714].
  * (61) B. Eden, G. P. Korchemsky and E. Sokatchev, _From correlation functions to scattering amplitudes_ , _JHEP_ 12 (2011) 002 [1007.3246].
  * (62) B. Eden, G. P. Korchemsky and E. Sokatchev, _More on the duality correlators/amplitudes_ , _Phys. Lett. B_ 709 (2012) 247 [1009.2488].
  * (63) B. Eden, P. Heslop, G. P. Korchemsky and E. Sokatchev, _The super-correlator/super-amplitude duality: Part II_ , _Nucl. Phys. B_ 869 (2013) 378 [1103.4353].
  * (64) R. A. Brandt, F. Neri and M.-a. Sato, _Renormalization of Loop Functions for All Loops_ , _Phys. Rev. D_ 24 (1981) 879.
  * (65) I. A. Korchemskaya and G. P. Korchemsky, _On lightlike Wilson loops_ , _Phys. Lett._ B287 (1992) 169.
  * (66) O. T. Engelund and R. Roiban, _On correlation functions of Wilson loops, local and non-local operators_ , _JHEP_ 05 (2012) 158 [1110.0758].
  * (67) A. Hodges, _Eliminating spurious poles from gauge-theoretic amplitudes_ , _JHEP_ 05 (2013) 135 [0905.1473].
  * (68) L. J. Mason and D. Skinner, _Dual Superconformal Invariance, Momentum Twistors and Grassmannians_ , _JHEP_ 11 (2009) 045 [0909.0250].
  * (69) Z. Bern, L. J. Dixon, D. C. Dunbar and D. A. Kosower, _One loop n point gauge theory amplitudes, unitarity and collinear limits_ , _Nucl. Phys._ B425 (1994) 217 [hep-ph/9403226].
  * (70) N. Arkani-Hamed, J. L. Bourjaily, F. Cachazo and J. Trnka, _Local Integrals for Planar Scattering Amplitudes_ , _JHEP_ 06 (2012) 125 [1012.6032].
  * (71) D. Chicherin, J. M. Henn and A. Tumanov, _in preparation_ , .
  * (72) E. Witten, _Perturbative gauge theory as a string theory in twistor space_ , _Commun. Math. Phys._ 252 (2004) 189 [hep-th/0312171].
  * (73) V. Drinfeld, _Hopf algebras and the quantum Yang-Baxter equation_ , _Sov.Math.Dokl._ 32 (1985) 254.
  * (74) A. Molev, M. Nazarov and G. Olshansky, _Yangians and classical Lie algebras_ , _Russ. Math. Surveys_ 51 (1996) 205 [hep-th/9409025].
  * (75) L. Ferro, T. Łukowski and M. Staudacher, _$\mathcal{N}=4$ scattering amplitudes and the deformed Graßmannian_, _Nucl. Phys. B_ 889 (2014) 192 [1407.6736].
  * (76) Z. Bern, G. Chalmers, L. J. Dixon and D. A. Kosower, _One loop N gluon amplitudes with maximal helicity violation via collinear limits_ , _Phys. Rev. Lett._ 72 (1994) 2134 [hep-ph/9312333].
  * (77) C. R. Mafra and O. Schlotterer, _The Structure of n-Point One-Loop Open Superstring Amplitudes_ , _JHEP_ 08 (2014) 099 [1203.6215].
  * (78) S. He, R. Monteiro and O. Schlotterer, _String-inspired BCJ numerators for one-loop MHV amplitudes_ , _JHEP_ 01 (2016) 171 [1507.06288].
  * (79) S. Catani, _The Singular behavior of QCD amplitudes at two loop order_ , _Phys. Lett. B_ 427 (1998) 161 [hep-ph/9802439].
  * (80) Z. Bern, A. De Freitas and L. J. Dixon, _Two loop helicity amplitudes for gluon-gluon scattering in QCD and supersymmetric Yang-Mills theory_ , _JHEP_ 03 (2002) 018 [hep-ph/0201161].
  * (81) Q. Jin and H. Luo, _Analytic Form of the Three-loop Four-gluon Scattering Amplitudes in Yang-Mills Theory_ , 1910.05889.
  * (82) F. Caola, A. Chakraborty, G. Gambuti, A. von Manteuffel and L. Tancredi, _Three-loop gluon scattering in QCD and the gluon Regge trajectory_ , 2112.11097.
  * (83) A. V. Kotikov and L. N. Lipatov, _DGLAP and BFKL equations in the $N=4$ supersymmetric gauge theory_, _Nucl. Phys. B_ 661 (2003) 19 [hep-ph/0208220].
  * (84) C. Anastasiou, Z. Bern, L. J. Dixon and D. A. Kosower, _Planar amplitudes in maximally supersymmetric Yang-Mills theory_ , _Phys. Rev. Lett._ 91 (2003) 251602 [hep-th/0309040].
  * (85) Z. Bern, L. J. Dixon, D. C. Dunbar and D. A. Kosower, _One loop selfdual and N=4 superYang-Mills_ , _Phys. Lett. B_ 394 (1997) 105 [hep-th/9611127].
  * (86) S. Badger, H. Frellesvig and Y. Zhang, _A Two-Loop Five-Gluon Helicity Amplitude in QCD_ , _JHEP_ 12 (2013) 045 [1310.1051].
  * (87) S. Badger, G. Mogull and T. Peraro, _Local integrands for two-loop all-plus Yang-Mills amplitudes_ , _JHEP_ 08 (2016) 063 [1606.02244].
  * (88) B. Mistlberger, _Higgs boson production at hadron colliders at N 3LO in QCD_, _JHEP_ 05 (2018) 028 [1802.00833].
  * (89) N. Arkani-Hamed, D. Chicherin, J. M. Henn and J. Trnka, _in preparation_ , .
  * (90) S. Caron-Huot and S. He, _Jumpstarting the All-Loop S-Matrix of Planar N=4 Super Yang-Mills_ , _JHEP_ 07 (2012) 174 [1112.1060].