# 4-Chromatic Graphs Have At Least 4 Cycles of Length 0 mod $3$

Sean Kim Department of Mathematics, California State University San Marcos,
San Marcos, CA 92096. E-mail addresses<EMAIL_ADDRESS><EMAIL_ADDRESS>Michael E. Picollelli11footnotemark: 1

###### Abstract

A 2018 conjecture of Brewster, McGuinness, Moore, and Noel [2] asserts that
for $k\geq 3$, if a graph has chromatic number greater than $k$, then it
contains at least as many cycles of length $0\bmod k$ as the complete graph on
$k+1$ vertices. Our main result confirms this in the $k=3$ case by showing
every $4$-critical graph contains at least $4$ cycles of length $0\bmod 3$,
and that $K_{4}$ is the unique such graph achieving the minimum.

We make progress on the general conjecture as well, showing that
$(k+1)$-critical graphs with minimum degree $k$ have at least as many cycles
of length $0\bmod r$ as $K_{k+1}$, provided $k+1\neq 0\bmod r$. We also show
that $K_{k+1}$ uniquely minimizes the number of cycles of length $1\bmod k$
among all $(k+1)$-critical graphs, strengthening a recent result of Moore and
West [12] and extending it to the $k=3$ case.

##  1 Introduction

The study of cycles with a given length modulo an integer $k$ began with work
of Burr and Erdős [8], who conjectured that for odd values of $k$, graphs of
sufficiently large average degree contain cycles of all lengths modulo $k$.
This conjecture was proven by Bollobás [1], with the bound subsequently
improved by Thomassen [16]. Further work, building in part on conjectures of
Thomassen [16], has largely focused on the existence of such cycles under
minimum degree or connectivity assumptions – see, for example, [5], [7], [9],
or [15].

This paper is concerned with bounding the number of cycles of length $0\bmod
k$ and $1\bmod k$ in non-$k$-colorable graphs. The first result in this
direction is due to Tuza [17], who showed that graphs without cycles of length
$1\bmod k$ are $k$-colorable, generalizing König’s classic characterization of
bipartite graphs. For cycles of length $0\bmod k$, Chen and Saito [3] showed
that graphs without cycles of length $0\bmod 3$ are $3$-colorable; Dean,
Lesniak and Saito [6] achieved the same conclusion for graphs without cycles
of length $0\bmod 4$. Chen, Ma and Zang [4] established that any
non-$k$-colorable graph is guaranteed cycles of every length $\ell\bmod k$
except possibly $\ell=2$, settling the existence case in the $\ell=0$ case.
Very recent work has essentially settled the existence question entirely: Gao,
Huo, and Ma [10] showed every $(k+1)$-critical non-complete graph has cycles
of all lengths modulo $k$ when $k\geq 6$. The same conclusion for the $k=3$
case was implied by work in [3], [13], and [14], and the case where
$k\in\\{4,5\\}$ is the subject of recent work of Huo [11].

The question of how many such cycles must occur has received considerably less
attention. Brewster, McGuinness, Moore and Noel [2] generalized a proof of
Chen and Saito’s result due to Wrochna to show that any graph which is not
$k$-colorable has at least $(k-1)!/2$ cycles of length $0\bmod k$. They
further conjectured that the complete graph $K_{k+1}$ achieves the minimum
number of such cycles among all non-$k$-colorable graphs.

######  Conjecture 1 (Brewster, McGuinness, Moore, and Noel, [2]).

If $\chi(G)>k$, then $G$ contains at least $(k+1)(k-1)!/2$ cycles of length
$0\bmod k$.

We will establish this conjecture for $(k+1)$-critical graphs with minimum
degree $k$ (see Corollary 2.5), but our main contribution is to settle it in
the affirmative in the $k=3$ case.

######  Theorem 1.1.

If $G$ is $4$-critical, then $G$ has at least $4$ cycles of length $0\mod 3$,
with equality only for $K_{4}$.

Building on the arguments in [2], Moore and West [12] established bounds on
the number of cycles of length $0\bmod r$ and $1\bmod r$ in non-$k$-colorable
graphs, where $3\leq r\leq k$. While their bound on cycles of length $0\bmod
k$ was the same as in [2], they were able to bound the number of cycles of
length $1\bmod k$ in non-$k$-colorable graphs below by $k!/2$. This is best
possible as it is achieved by $K_{k+1}$. Their argument, a probabilistic
application of Tuza’s strengthening of Minty’s Theorem, also established a
structural condition for equality when $k\geq 4$.

######  Theorem 1.2 (Moore and West [12], Theorem 5).

For $k\geq 3$, a non-$k$-colorable graph has at least $k!/2$ cycles with
lengths congruent to 1 modulo $k$, with equality for $k\geq 4$ only when these
cycles all have length $k+1$.

By modifying their arguments, we achieve a slight strengthening of their
result that extends to the $k=3$ case, and relies on a simpler constructive
argument.

######  Theorem 1.3.

Let $k\geq 3$ and let $G$ be a $(k+1)$-critical graph. Then $G$ has at least
$k!/2$ cycles of length $1\bmod k$, with equality only for the complete graph
$K_{k+1}$.

The remainder of this paper is organized as follows: in Section 2 we establish
some results for $(k+1)$-critical graphs, followed by the proof of Theorem 1.3
in Section 3. Section 4 is then focused on the proof of Theorem 1.1.

##  2 Cycles in $(k+1)$-critical graphs

In this section we will establish our results on $(k+1)$-chromatic graphs. We
remark that our notation largely follows [18], and we note that a graph $G$ is
$(k+1)$-critical if $G$ has chromatic number $k+1$ but every proper subgraph
has chromatic number at most $k$.

The results in this section are primarily established by modifying the
approach to generalized Kempe chains used by Moore and West in [12]. To that
end, we will use the the following definition from [12]:

######  Definition 2.1 (Moore and West [12]).

Let $G$ be a $k$-colorable graph and let $\varphi$ be a proper $k$-coloring of
$G$, where we assume the set of colors is $[k]=\\{1,2,\ldots,k\\}$. For some
$r$, $3\leq r\leq k$, let $\sigma$ be a cyclic permutation of $r$ distinct
elements from $[k]$. Then we define the $\sigma$-subdigraph $D_{\sigma}$ to be
the directed graph satisfying

  1. 1.

$V(D_{\sigma})=V(G)$.

  2. 2.

For $u,v\in V(G)$, $uv\in E(D_{\sigma})$ if and only if $uv\in E(G)$ and
$\sigma(\varphi(u))=\varphi(v)$.

For $v\in V(G)$, let $A_{v}$ be the set of vertices accessible from $v$ along
directed paths in $D_{\sigma}$. A key observation in [12] is that we may
“shift” the colors in $A_{v}$ by recoloring each $w\in A_{v}$ with the color
$\sigma(\varphi(w))$; the resulting $k$-coloring will still be a proper.
Otherwise, a monochromatic edge $xy$ under the recoloring would have one end
$x\in A_{v}$ and the other end $y\notin A_{v}$, and must satisfy
$\sigma(\varphi(x))=\varphi(y)$, contradicting $y\notin A_{v}$.

As an illustration, we begin with a slight strengthening of Theorem 4 from
[12] that bounds the number of cycles of a given modular length in a graph $G$
such that $G$ is $(k+1)$-chromatic but $G-e$ is not. We show further that the
bound holds on the number of cycles through each vertex of $e$, although we do
not claim that all such cycles found contain both vertices of $e$. We will use
this stronger conclusion later in the proof of Theorem 1.1.

######  Theorem 2.2 (See Moore and West [12], Theorem 4).

Fix $r,k\in\mathbb{N}$ with $3\leq r\leq k$, and let $e$ be an edge in a graph
$G$. If $\chi(G)=k+1$ but $\chi(G-e)=k$, then letting $x$ be an endpoint of
$e$, $G-e$ contains at least $\frac{1}{2}\prod_{i=1}^{r-1}(k-i)$ cycles of
length $0\bmod r$.

###### Proof.

Letting $e=xy$, we fix a proper $k$-coloring $\varphi$ of $G-e$ using colors
$1,2,\ldots,k$ and let $\sigma$ be a cyclic $r$-permutation of $[k]$ that
includes $\varphi(x)$. We note that $\varphi(x)=\varphi(y)$ must hold, else
$\varphi$ is a proper $k$-coloring of $G$.

Consider the $\sigma$-subdigraph $D_{\sigma}$ of $G$ under $\varphi$ and
$\sigma$, and let $A_{x}$ be the set of vertices accessible from $x$ via
directed paths. By construction of $D_{\sigma}$, the mapping
$\varphi^{\prime}$ formed by setting $\varphi^{\prime}(v)=\sigma(\varphi(v))$
for $v\in A_{x}$ and $\varphi^{\prime}(v)=\varphi(v)$ otherwise is a proper
coloring.

If $y\notin A_{x}$ then $\varphi^{\prime}$ yields a proper $k$-coloring of
$G$, a contradiction. Therefore $D_{\sigma}$ contains a directed path $P$ from
$x$ to $y$. By symmetry, it also contains a directed path $Q$ from $y$ to $x$.
The concatenation of $P$ and $Q$ yields a closed directed walk in
$D_{\sigma}$. It’s routine to show that the edges traversed by a closed
directed walk can be decomposed into directed cycles, so every vertex on $P$
and $Q$ lies on a directed cycle in $D_{\sigma}$.

Thus, $D_{\sigma}$ has a directed cycle containing $x$: let $C_{\sigma}$ be
its underlying cycle in $G$. Every directed cycle in $D_{\sigma}$ visits every
color from $\sigma$ in order, implying that $C_{\sigma}$ has length $0\bmod
r$, and thus the only other $r$-permutation which could produce the same cycle
is the inverse $\sigma^{-1}$. Consequently, the number of cycles found is at
least half the number of cyclic $r$-permutations,
$\frac{1}{2}\prod_{i=1}^{r-1}(k-i)$. ∎

As mentioned above, this bound generalizes a result from [2] in the case $r=k$
that establishes that $(k+1)$-chromatic graphs contain at least $(k-1)!/2$
cycles of length $0\bmod k$. Our goal now is to show the stronger bound of
Conjecture 1 holds for $(k+1)$-critical graphs of minimum degree $k$. We
remark that while there exist $(k+1)$-critical graphs of arbitrarily large
minimum degree for all $k\geq 3$, we are unaware of any results estimating
what proportion of $(k+1)$-critical graphs have minimum degree greater than
$k$. Since the minimum-degree-$k$ case appears to be very ‘typical’ in the
literature, and as such graphs are easily produced through the Hajós
construction, we still think this result is of interest.

We begin with a technical lemma.

######  Lemma 2.3.

Let $k\geq 3$ and let $G$ be a $(k+1)$-critical graph with $\delta(G)=k$. Let
$v$ be a vertex of degree $k$ in $G$ with neighbors $v_{1},\ldots,v_{k}$, and
let $\varphi$ be a proper $k$-coloring of $G-v$ satisfying $\varphi(v_{i})=i$.
Finally, let $\sigma$ be a cyclic $r$-permutation of elements in $[k]$. Then
the $\sigma$-subdigraph of $G-v$ under $\varphi$ contains directed
$v_{i},v_{\sigma^{-1}(i)}$-paths $R^{i}$ for each color $i$ in $\sigma$.

###### Proof.

Fixing $i$ in $\sigma$, we extend $\varphi$ to a proper $k$-coloring
$\varphi^{i}$ of $G-vv_{i}$ by setting $\varphi^{i}(v)=i$. Let
$D^{i}_{\sigma}$ denote the $\sigma$-subdigraph of $G-vv_{i}$ under
$\varphi^{i}$, noting that it contains the $\sigma$-subdigraph of $G-v$ under
$\varphi$. We claim that $D_{\sigma}^{i}$ contains a directed path $Q$ from
$v_{i}$ to $v$. Otherwise, we can shift the colors of the vertices accessible
from $v_{i}$ according to $\sigma$, yielding a proper $k$-coloring of $G$, a
contradiction.

By definition of $D_{\sigma}^{i}$, the vertex preceding $v$ on $Q$ must be
$v_{\sigma^{-1}(i)}$, and therefore $R^{i}=Q-v$ is a directed
$v_{i},v_{\sigma^{-1}(i)}$-path lying in the $\sigma$-subdigraph of $G-v$ as
claimed. ∎

Our bound on the number of cycles of length $0\bmod k$ will follow immediately
from the next result. To state it, we introduce some further notation: for a
graph $H$, let $\mathcal{C}(H)$ denote the set of all cycles in $H$, and
$\mathcal{C}_{\leq i}(H)$ the set of cycles of length at most $i$.

######  Theorem 2.4.

Let $k\geq 3$ and let $G$ be a $(k+1)$-critical graph with $\delta(G)=k$. Then
there exists an injective mapping $f:\mathcal{C}_{\leq
k}(K_{k+1})\to\mathcal{C}(G)$ such that $|V(f(C))|\equiv 0\bmod|V(C)|$.

###### Proof.

We begin by taking $K_{k+1}$ to have vertex set $[k+1]$. Let $v$ be a vertex
in $G$ of degree $k$, and let $v_{1},\ldots,v_{k}$ be its neighbors. Since $G$
is $(k+1)$-critical, let $\varphi$ be a proper $k$-coloring of $G-v$ using
colors $1,2,\ldots,k$. Since each neighbor $v_{i}$ of $v$ must receive a
different color under $\varphi$, without loss of generality we assume
$\varphi(v_{i})=i$.

We turn now to defining our mapping $f$. Let $C$ be a cycle in $K_{k+1}$ of
length $r\leq k$. Our construction of $f(C)$ differs depending on whether or
not $k+1\in V(C)$.

Suppose first that $k+1\notin V(C)$: we orient $C$ into a directed cycle, and
let $\sigma$ denote the corresponding cyclic $r$-permutation of $[k]$.
Consider the $\sigma$-subdigraph of $G-v$ under $\varphi$: by Lemma 2.3, for
each color $i$ in $\sigma$ it contains a directed
$v_{i},v_{\sigma^{-1}(i)}$-path $R^{i}$. The concatenation of these $r$ paths,
in the order
$(R^{i},R^{\sigma^{-1}(i)},R^{\sigma^{-1}(\sigma^{-1}(i))},\ldots,R^{\sigma(i)})$,
produces a closed directed walk (see Figure 1), which must include the edges
of at least one directed cycle $\widehat{C}$. We note that $\widehat{C}$ must
follow the colors of $\sigma$ in order, so letting $f(C)$ be its underlying
cycle in $G-v$, $f(C)$ has length $0\bmod r$, as required.

Suppose instead that $k+1\in V(C)$: we construct $f(C)$ to include vertex $v$
as follows. As above, we orient $C$ into a directed cycle and let $\sigma$ be
the corresponding cyclic $r$-permutation, which includes color $k+1$. Since
$r\leq k$, let $i\in[k+1]$ be a color not on $\sigma$ and let
$\sigma^{\prime}$ be the cyclic $r$-permutation of $[k]$ formed by replacing
$k+1$ with $i$.

We next extend $\varphi$ to a proper $k$-coloring $\varphi^{i}$ of $G-vv_{i}$
by setting $\varphi^{i}(v)=i$, and let $D_{\sigma^{\prime}}$ denote the
$\sigma^{\prime}$-subdigraph of $G-vv_{i}$ under $\varphi^{i}$. By Lemma 2.3,
it contains directed paths $R^{\sigma^{\prime}(i)}$ and $R^{i}$ from
$v_{\sigma^{\prime}(i)}$ to $v_{i}$ and $v_{i}$ to $v_{\sigma^{\prime-1}(i)}$,
respectively. Thus, the concatenation $(v,R^{\sigma^{\prime}(i)},R^{i},v)$ is
a closed directed walk in $D_{\sigma^{\prime}}$, and therefore contains the
edges of a directed cycle $\widehat{C}$ through vertex $v$. Let $f(C)$ be the
underlying cycle of $\widehat{C}$, noting that $f(C)$ has length $0\bmod r$.

Turning to injectivity, suppose that $f(C^{1})=f(C^{2})$ for some
$C^{1},C^{2}\in\mathcal{C}^{\leq k}(K_{k+1})$, and let $\sigma_{1},\sigma_{2}$
be the cyclic permutations of $C^{1},C^{2}$ used in the construction above. We
observe that $v\in V(f(C))$ if and only if $k+1\in V(C)$, and we first suppose
that $v\notin V(f(C^{1}))$. Then under $\varphi$, $f(C^{1})$ can be oriented
into a directed cycle so that it follows the colors of $\sigma_{1}$ in order,
and it can be oriented so that follows the colors of $\sigma_{2}$ in order.
But this implies that either $\sigma_{1}=\sigma_{2}$, or $\sigma_{2}$ follows
the colors of $\sigma_{1}$ in the reverse order
($\sigma_{2}=\sigma_{1}^{-1}$), and in either case $C^{1}=C^{2}$.

Suppose instead that $v\in f(C^{1})$, and let $\sigma_{1}^{\prime}$ and
$\sigma_{2}^{\prime}$ be the cyclic permutations in $[k]$ formed above from
$\sigma_{1},\sigma_{2}$ by replacing $k+1$ with some colors $i_{1},i_{2}$,
respectively. Then $f(C^{1})$ can be oriented into directed cycle(s)
$\widehat{C}^{1},\widehat{C}^{2}$ so that by giving vertex $v$ color $i_{j}$,
$\widehat{C}^{j}$ follows the colors of $\sigma_{j}^{\prime}$ in order. If
$f(C^{1})-v$ has no repeated color under $\varphi$, the directed path
$\widehat{C}^{j}-v$ follows the colors of the permutation
$\sigma_{j}^{\prime}-\\{i_{j}\\}=\sigma_{j}-\\{k+1\\}$ in order. Thus, either
$\sigma_{2}=\sigma_{1}$ or $\sigma_{2}=\sigma_{1}^{-1}$, and $C^{1}=C^{2}$
follows.

If, instead, $f(C^{1})-v$ has repeated colors under $\varphi$, then letting
$r$ be the least length between repeated entries, it must hold that
$\sigma_{1}^{\prime},\sigma_{2}^{\prime}$ are cyclic $r$-permutations, the
first $r-1$ entries of $\widehat{C}^{j}-v$ form the permutation
$\sigma^{\prime}_{j}-\\{i_{j}\\}$, and the $r$th vertex of $\widehat{C}^{j}-v$
is $i_{j}$. But this implies $i_{1}=i_{2}$, and that either
$\sigma_{2}^{\prime}=\sigma_{1}^{\prime}$ or
$\sigma_{2}^{\prime}=\sigma_{1}^{\prime-1}$, which then implies either
$\sigma_{2}=\sigma_{1}$ or $\sigma_{2}=\sigma_{1}^{-1}$, and $C^{1}=C^{2}$
follows, completing the proof that $f$ is injective. ∎

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}R^{1}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}R^{2}}$$v$$v_{2}$$v_{1}$$v_{3}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}R^{1}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}R^{2}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}R^{3}}$$v$$v_{2}$$v_{1}$$v_{3}$
Figure 1: In the proof of Theorem 2.4 in the case $k=3$, we give a view of the
closed directed walks used to construct the cycles $f(C)$. On the left we have
the case where $C$ is the triangle on $\\{1,2,3\\}$ with $\sigma=(1\,2\,3)$,
and on the right, the case where $C$ is the triangle on $\\{2,3,4\\}$ where we
take $\sigma=(1\,2\,4)$ and then let $\sigma^{\prime}=(2\,3\,1)=(1\,2\,3)$. We
remark that despite the depiction, the paths $R^{i}$ may not be vertex-
disjoint.

As an immediate consequence we obtain the following corollary.

######  Corollary 2.5.

Let $k\geq 3$ and let $G$ be a $(k+1)$-critical graph with $\delta(G)=k$. Then
for each $r$, $2\leq r\leq k$, with $k+1\neq 0\bmod r$, $G$ contains at least
as many cycles of length $0\bmod r$ as the complete graph $K_{k+1}$. In
particular, $G$ has at least $(k+1)(k-1)!/2$ cycles of length $0\bmod k$.

##  3 Proof of Theorem 1.3

Our aim now is to prove Theorem 1.3: let $k\geq 3$ and let $G$ be a
$(k+1)$-critical graph. Let $v$ be an arbitrary vertex, and let $\varphi$ be a
$k$-coloring of $G-v$ using colors $1,2,...,k$. We first show that $G$
contains at least $k!/2$ cycles of length $1\bmod k$ that include $v$.

For each $i\in[k]$, let $N_{i}$ be the set of neighbors of $v$ with color $i$
under $\varphi$, noting $N_{i}\neq\varnothing$ since $G$ is not $k$-colorable.
Let $G_{i}$ be the subgraph of $G$ formed by deleting the edges between $v$
and $N_{i}$, and let $\varphi^{i}$ denote the extension of $\varphi$ to a
proper $k$-coloring of $G_{i}$ by setting $\varphi^{i}(v)=i$.

Let $\sigma$ be a cyclic permutation of $[k]$, and consider the
$\sigma$-subdigraph $D^{i}_{\sigma}$ of $G_{i}$ under $\varphi^{i}$. We claim
that $D^{i}_{\sigma}$ must contain a directed path from $v$ into $N_{i}$.
Otherwise, letting $W$ denote the set of vertices in $D^{i}_{\sigma}$
accessible from $v$, we can recolor $G_{i}$ by shifting the colors in $W$
according to $\sigma$, producing a proper $k$-coloring $\varphi^{\prime}$ of
$G_{i}$ in which all vertices in $N_{i}$ have color $i$ and $v$ has color
$\sigma(i)$. But in that case $\varphi^{\prime}$ is a proper coloring of $G$,
a contradiction.

With foresight we let $v_{i}\in N_{i}$ be a vertex on a shortest directed path
$P$ in $D_{\sigma}^{i}$ from $v$ to $N_{i}$, noting $P$ has length $0\bmod k$
since it begins and ends on a vertex of color $i$. Then $P$ along with the
edge $v_{i}v$ forms a directed cycle $\widehat{C}_{\sigma}^{i}$ in $G$ of
length $1\bmod k$; let $C^{i}_{\sigma}$ be its underlying cycle in $G$. Since
$P$ visits all the colors of $\sigma$ in order and contains the edge $v_{i}v$,
$\widehat{C}_{\sigma}^{i}$, viewed now as an oriented subgraph of $G$,
determines $i$ and $\sigma$. Consequently, $C_{\sigma}^{i}$ could also be the
underlying cycle of $\widehat{C}_{\sigma^{-1}}^{\sigma(i)}$, but of no other
such directed cycle constructed this way. So as $i$ and $\sigma$ vary, this
construction produces at least $k\cdot(k-1)!/2=k!/2$ distinct cycles of length
$1\bmod k$ containing $v$.

Suppose now that $G$ has exactly $k!/2$ cycles of length $1\bmod k$ in total.
Our argument shows every vertex lies on at least $k!/2$ such cycles, so every
such cycle is spanning. Fixing a cyclic permutation $\sigma$ of $[k]$ and an
$i\in[k]$, the constructed cycle $C^{i}_{\sigma}$ is spanning, and therefore
so is the shortest directed path from $v$ to $N_{i}$ in $D_{\sigma}^{i}$.
Consequently, $|N_{i}|=1$, implying that $v$ has degree $k$ and thus $G$ is
$k$-regular. Brooks’ Theorem then implies $G=K_{k+1}$, completing the proof.

##  4 Proof of Theorem 1.1

This section is focused on providing the proof of Theorem 1.1. Our argument
consists of the following three claims, noting that any 4-critical graph has
minimum degree at least 3.

  1. 1.

A 4-critical graph $G$ with $\delta(G)=3$ has at least 4 cycles of length
$0\bmod 3$.

  2. 2.

$K_{4}$ is the only 4-critical graph with $\delta(G)=3$ and exactly 4 cycles
of length $0\bmod 3$.

  3. 3.

A 4-critical graph $G$ with $\delta(G)\geq 4$ has at least 5 cycles of length
$0\bmod 3$.

The first claim follows from Corollary 2.5. The second claim is the subject of
Lemma 4.1 below. The third claim, which is the most technical argument of this
paper, follows from Lemmas 4.3 and 4.7 in Section 4.1 below.

######  Lemma 4.1.

$K_{4}$ is the only 4-critical graph with minimum degree 3 that has exactly 4
cycles of length $0\bmod 3$.

###### Proof.

Suppose $G$ is 4-critical, $\delta(G)=3$, and $G$ has exactly 4 cycles of
length $0\bmod 3$. Let $v$ be a vertex in $G$ with degree 3 and label its
neighbors $v_{1},v_{2},v_{3}$. Let $\varphi$ be a proper $3$-coloring of $G-v$
satisfying $\varphi(v_{i})=i$, and let $\sigma=(1\,2\,3)$. Finally, we let
$R^{1},R^{2},R^{3}$ denote the three directed paths in the $\sigma$-subdigraph
of $G-v$ guaranteed to exist by Lemma 2.3.

For $i\in[3]$, let $\varphi^{i}$ be the extension of $\varphi$ to $G-vv_{i}$
formed by setting $\varphi^{i}(v)=i$, and let $D_{\sigma}^{i}$ be the
$\sigma$-subdigraph of $G-vv_{i}$ under $\varphi^{i}$. Then the closed walk in
$D_{\sigma}^{i}$ formed by the concatenation $(v,R^{\sigma(i)},R^{i},v)$
includes the (oriented) edges of a cycle $C^{i}$ in $G$ containing edges
$vv_{i}$ and $vv_{\sigma^{-1}(i)}$ in $G$ of length $0\bmod 3$, and the closed
walk formed by the concatenation $(R_{1},R_{3},R_{2})$ includes the edges of a
cycle $C^{4}$ in $G-v$ of length $0\bmod 3$. (The closed walks are also
illustrated in Figure 1.)

As the cycles $C^{1},C^{2},C^{3},C^{4}$ are distinct, these are the only
cycles of length $0\bmod 3$ in $G$. It follows then that the closed walk
$(R_{1},R_{3},R_{2})$ includes only the edges of $C^{4}$, and, by
construction, $C^{4}$ contains the paths $C^{i}-v$, $i\in[3]$. We further
claim that $C^{4}$ spans $G-v$, as any vertex $x$ in $G-v$ not lying on
$C^{4}$ must lie on a (fifth) cycle of length $0\bmod 3$ by Theorem 2.2,
taking $e$ to be any edge incident to $x$, a contradiction.

If $C^{4}$ is a triangle then it follows that $G=K_{4}$, so we suppose
otherwise. Since $\sigma=(1\,2\,3)$, we can label $C^{4}$’s vertices
$x_{1},x_{2},x_{3},\ldots,x_{3k}$ so that
$E(C^{4})=\\{x_{1}x_{2},x_{2}x_{3},\ldots,x_{3k-1}x_{3k},x_{3k}x_{1}\\}$ and

$\varphi(x_{i})=\begin{cases}1&\mbox{ if }i\equiv 1\bmod 3,\\\ 2&\mbox{ if
}i\equiv 2\bmod 3,\\\ 3&\mbox{ if }i\equiv 0\bmod 3.\end{cases}$

Since $G$ has minimum degree 3 and $v$ has only three neighbors, $C^{4}$
contains chords. But chords can only connect vertices of different colors, and
any such chord cuts $C^{4}$ into two cycles, one of which has length $0\bmod
3$, a contradiction that completes the proof. (See Figure 2.)

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$$x_{9}$ Figure 2: In
the proof of Lemma 4.1, an illustration of the cycle $C^{4}$ containing a
chord, which necessarily produces a fifth cycle of length $0\bmod 3$.

∎

###  4.1 4-critical graphs with minimum degree at least 4

To finish the proof of Theorem 1.1, we must now show that every 4-critical
graph $G$ with minimum degree at least 4 contains at least 5 cycles of length
$0\bmod 3$. In this case, the argument used in Theorem 2.4 does not directly
adapt as it obtained cycles from closed directed walks. A key to constructing
these walks was that every neighbor of a vertex $v$ of degree 3 in a
4-critical graph receives a different color under a proper 3-coloring of
$G-v$, which does not apply once $\delta(G)\geq 4$.

Instead, our arguments will rely on two other results. The first is a
sufficient condition for cycles of length $0\bmod 3$ to exist due to Chen and
Saito [3]:

######  Theorem 4.2 (Chen and Saito [3], Theorem 1).

If $G$ is a graph with $n\geq 2$ vertices and at most one vertex of degree 2
or less, then $G$ contains a cycle of length $0\bmod 3$.

We remark that in [3], the authors refer to cycles with length divisible by
$3$ as good cycles, and we will do so for the remainder of this section. Our
first application of this will be to handle the case where a vertex lies on at
least three good cycles.

######  Lemma 4.3.

If $G$ is a 4-critical graph with $\delta(G)\geq 4$ and there exists a vertex
$v\in V(G)$ such that $v$ lies on at least 3 good cycles, then $G$ contains at
least 5 good cycles.

###### Proof.

Suppose $v\in V(G)$ lies on at least 3 good cycles, call them
$C^{1},C^{2},C^{3}$. Since $\delta(G)\geq 4$, $\delta(G-v)\geq 3$, so $G-v$
contains at least one good cycle $C^{4}$ by Theorem 4.2.

If $V(C^{4})\nsubseteq N(v)$ then $C^{4}$ contains an edge $e$ with at most
one endpoint in $N(v)$. Deleting $e$ from $G-v$ produces a subgraph with at
most one vertex of degree 2, and thus it contains a good cycle $C^{5}\neq
C^{4}$ by Theorem 4.2, yielding the result.

If $V(C^{4})\subseteq N(v)$, then every edge of $C^{4}$ forms a triangle with
$v$, and we’re done if $|V(C^{4})|\geq 5$. But if $|V(C^{4})|<5$, then
$|V(C^{4})|=3$ since $C^{4}$ is good. This implies $G$ contains a $K_{4}$ on
$C^{4}\cup\\{v\\}$, contradicting $G$’s 4-criticality and completing the
proof.

∎

We’ll also appeal to a recent result of Gao, Huo, Liu and Ma [9], which was
used to resolve a number of conjectures regarding the existence of cycles of
prescribed lengths.

######  Definition 4.4 (Gao, Huo, Liu and Ma [9]).

A collection of $\ell$ paths is admissible if the length of every path is at
least two, and the lengths form an arithmetic progression with common
difference one or two.

######  Theorem 4.5 (Gao, Huo, Liu, and Ma [9], Theorem 1.2 ).

Let $G$ be a 2-connected graph and let $x,y$ be distinct vertices of $G$. If
every vertex in $G$ other than $x$ and $y$ has degree at least $\ell+1$, then
there exist $\ell$ admissible paths from $x$ to $y$ in $G$.

We note that Theorem 2.2 implies that every vertex $v$ in a 4-critical graph
lies on at least two good cycles, by applying the Theorem first with an
arbitrary edge incident with $v$, then with an edge incident with $v$ on the
found cycle.

######  Lemma 4.6.

If $G$ is $4$-critical with $\delta(G)\geq 4$ and every vertex is on at most
two good cycles, then:

  1. 1.

$G$ is $4$-regular, and

  2. 2.

Every edge of $G$ lies on exactly one good cycle.

###### Proof.

It suffices to argue that every edge lies on at least one good cycle. This
will imply that every vertex lies on at least $d(v)/2$ good cycles, yielding a
maximum degree of at most 4 under the assumptions given and therefore $G$ is
$4$-regular. Furthermore, if any edge $uv$ lies on at least two good cycles,
then those two cycles only cover three edges incident with $v$, implying $v$
lies on a third good cycle, a contradiction.

To that end, pick any edge $e=uv$. It is routine to show that a color-critical
graph is $2$-connected (e.g., see [18], Exercise 8.2.11), so by Theorem 4.5
there exist $3$ admissible paths from $u$ to $v$. Since the common difference
is one or two, their lengths cover the congruence classes modulo 3, so one of
these paths has length $2\bmod 3$ and forms a good cycle with $e$. ∎

The next lemma will complete the proof of Theorem 1.1.

######  Lemma 4.7.

If $G$ is a 4-critical graph with minimum degree at least 4 and every vertex
is on at most two good cycles, then $G$ contains at least 5 good cycles.

###### Proof.

We first observe that under the given assumptions and by Theorem 2.2, every
vertex lies on exactly two good cycles. Furthermore, deleting any vertex
yields a subgraph with minimum degree at least 3, which contains a good cycle
by Theorem 4.2. Thus, $G$ has at least three good cycles, at least one of
which is not spanning.

Let $C^{1}$ be a non-spanning good cycle, and let $uv$ be an edge connecting
$C^{1}$ to the rest of $G$, where $u\in V(C^{1})$ and $v\in V(G)-V(C^{1})$.
Then, by Lemma 4.6, the edge $uv$ lies on a good cycle $C^{2}$, and then $v$
must lie on a second good cycle $C^{3}$. Our argument proceeds by considering
two cases: whether or not $C^{2}$ is a triangle.

Case 1: $C^{2}$ is not a triangle. By Lemma 4.6, $C^{2}$ is the only good
cycle containing edge $uv$, and $G$ is $4$-regular. Consequently,
$N_{G}(u)\cap N_{G}(v)=\emptyset$, so let $U=N_{G}(u)-v$ and $V=N_{G}(v)-u$,
and label their vertices $u_{1},u_{2},u_{3}$ and $v_{1},v_{2},v_{3}$,
respectively. Observe that if $H=G-u-v$, then for any vertex $w\in U\cup V$,
$d_{H}(w)=3$, while for any vertex $x\in(V(H)-U\cup V)$, $d_{H}(x)=4$. Thus,
by Theorem 4.2, there exists a fourth good cycle that does not include $u$ nor
$v$; label it $C$. We have 2 subcases for $C$:

  1. 1.

$C$ has an edge $e$ with an endpoint not in $U\cup V$

  2. 2.

$V(C)\subseteq U\cup V$.

In Subcase 1, the edge $e$ has at most one endpoint of degree 3. So, its
removal will result in a graph with at most one vertex of degree 2. Therefore,
by Theorem 4.2, we can see that there must exist another good cycle, call it
$C^{\prime}$, that does not contain $u$, $v$, nor $e$. Thus, $C^{\prime}$ is
our fifth good cycle in $G$.

For Subcase 2, note that no edge in $C$ is contained in $U$ or in $V$, else it
lies on a triangle, contradicting the fact that every edge is on exactly one
good cycle. Therefore, $C$ is bipartite, and because $C$ is good, it must be a
6-cycle that spans $U\cup V$.

Without loss of generality, we may assume
$C=[u_{1},v_{1},u_{2},v_{2},u_{3},v_{3}]$. Now, let
$C^{\prime}=[u,u_{1},v_{1},u_{2},v_{2},v]$. $C$ and $C^{\prime}$ are two
different good cycles that share common edges; a contradiction. (See Figure
3.) Thus, in Case 1, $G$ has at least 5 good cycles.

$u$$v$$u$$v$$C$$C^{\prime}$ Figure 3: This image represents the fourth and
fifth good cycles constructed in Subcase 2 of Case 1, noting this yields a
contradiction as they share edges.

Case 2: $C^{2}$ is a triangle. Since $C^{2}$ is a triangle, there is a vertex
$w$ such that $V(C^{2})=\\{u,v,w\\}$. Let $U=N_{G}(u)-v-w$, $V=N_{G}(v)-u-w$,
and $W=N_{G}(w)-u-v$. We note that $U,V,W$ are pairwise disjoint, else we
contradict Lemma 4.6, and we may label their vertices
$U=\\{u_{1},u_{2}\\},V=\\{v_{1},v_{2}\\}$, and $W=\\{w_{1},w_{2}\\}$. In the
subgraph $H=G-u-v-w$, all vertices in $U$, $V$, and $W$ will have degree 3,
while all other vertices in $H$ will have degree 4. So by Theorem 4.2, $H$ has
a good cycle $C$ which does not use vertices $u$ or $v$. Thus, $C$ is a fourth
good cycle in $G$, and we consider 2 subcases:

  1. 1.

$C$ has an edge $e$ that has an endpoint not in $U\cup V\cup W$,

  2. 2.

$V(C)$ is a subset of $U\cup V\cup W$.

In Subcase 1, similar to our argument in Case 1, removing $e$ will result in a
graph with at most one vertex with degree at most 2. Then Theorem 4.2 yields
that $G$ contains a fifth distinct good cycle.

So we will focus on Subcase 2. By similar reasoning as in Subcase 2 of Case 1,
we know that $C$ cannot have an edge between $u_{1}$ and $u_{2}$, between
$v_{1}$ and $v_{2}$, or between $w_{1}$ and $w_{2}$. So, $C$ is tripartite.
Suppose first that $C$ contains a vertex whose neighbors lie in different
parts: without loss of generality, we may suppose that $C$ contains
$u_{1},v_{1},w_{1}$ and $u_{1}$ is adjacent to $v_{1},w_{1}$. Then the cycle
$C^{\prime}=[u_{1},v_{1},v,u,w,w_{1}]$ is a different good cycle that shares
edges with $C$; a contradiction. (See Figure 4.)

$u$$v$$w$$u$$w$$v$ Figure 4: In Case 2, Subcase 2, the image on the left
represents $G$ with a good cycle $C$ containing a vertex with neighbors in
both other parts. The image on the right illustrates a second good cycle
$C^{\prime}$ outlined in green, sharing edges with $C$.

If no vertex of $C$ has neighbors in different parts, then letting $x\in
V(C)$, $x$’s neighbors lie in one part, and its neighbors’ neighbors lie in
the same part as $x$. That is, $C$ must be contained in two parts and is
therefore bipartite on at most 4 vertices, contradicting that $C$ is good.
Thus, in Case 2, $G$ has at least 5 good cycles, completing the proof.

∎

### Acknowledgement

The authors wish to thank André Kündgen for a careful reading of an early
draft and many helpful comments.

## References

  * [1] B. Bollobás, Cycles modulo $k$, Bull. London Math. Soc. 9 (1977), no. 1, 97-98.
  * [2] R. C. Brewster, S. McGuinness, B. Moore, and J. A. Noel, _A Dichotomy Theorem for Circular Colouring Reconfiguration_. Theoret. Comput. Sci. 639 (2016), 1-13.
  * [3] G.T. Chen, A. Saito, _Graphs with a Cycle of Length Divisible by Three_. Journal of Combin. Theory, Ser. B, 60 (1994), 277-292.
  * [4] Z. Chen, J. Ma, and W. Zang, Colouring digraphs with forbidden cycles, J. Combin. Theory Ser. B 115 (2015), 210-223.
  * [5] N. Dean, _Which graphs are pancyclic modulo k?_ , Sixth Internat. Conf. on the Theory of Applications of Graphs, Kalamazoo, Michigan (1988) 315-326.
  * [6] N. Dean, L. Lesniak and A. Saito, _Cycles of length 0 modulo 4 in graphs_ , Discrete Math. 121 (1993), 37-49.
  * [7] A. Diwan, Cycles of even lengths modulo $k$, J. Graph Theory 65 (2010), no. 3, 246-252.
  * [8] P. Erdős, Some recent problems and results in graph theory, combinatorics and number theory, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), Congress. Numer. XVII , pp. 3–14,
  * [9] J. Gao, Q. Huo, C. Liu, and J. Ma, _A Unified Proof of Conjectures on Cycle Lengths in Graphs_ , International Mathematics Research Notices 10 (2021), 7615-7653.
  * [10] J. Gao, Q. Huo, and J. Ma, A strengthening on odd cycles in graphs of given chromatic number, SIAM J. Discrete Math. 35 (2021), 2317-2327.
  * [11] Q. Huo, A note on cycle lengths in graphs of chromatic number five and six, arXiv:2104.01382.
  * [12] B. Moore and D. B. West, _Cycles in Color-Critical Graphs_. Electron. J. Comb. 28 (2021).
  * [13] M. Lu and Z. Yu, Cycles of length 1 modulo 3 in graph, Discrete Applied Mathematics 113 (2001), 329-336.
  * [14] A. Saito, Cycles of length 2 modulo 3 in graphs, Discrete Mathematics 101 (1992), 285-289.
  * [15] B. Sudakov and J. Verstraëte, _The extremal function for cycles of length $\ell\bmod k$_, Electron. J. Combin. 24(1) (2017), #P1.7
  * [16] C. Thomassen, _Graph decomposition with applications to subdivisions and path systems modulo k_ , J. Graph Theory 7 (1983), 261-271.
  * [17] Zs. Tuza, _Graph coloring in linear time._ , J. Combin. Theory Ser. B 55 (1992), no. 2, 236-243.
  * [18] D. West, _Combinatorial Mathematics_. Cambridge University Press, Cambridge, 2021.


# Photon echo and fractional excitation lensing of $S=1/2$ XY spin chain

Zi-Long Li  Institute of Physics, Chinese Academy of Sciences, Beijing 100190,
China  University of Chinese Academy of Sciences, Beijing 100049, China  Yuan
Wan<EMAIL_ADDRESS>Institute of Physics, Chinese Academy of Sciences,
Beijing 100190, China  University of Chinese Academy of Sciences, Beijing
100049, China  Songshan Lake Materials Laboratory, Dongguan, Guangdong 523808,
China

###### Abstract

We study numerically the two-dimensional coherent spectrum (2DCS) of the
Tomonaga-Luttinger liquid hosted by the $S=1/2$ XY spin chain. The 2DCS
characterizes the system’s third order nonlinear magnetic response triggered
by three pulses, separated successively by the delay time and the waiting
time. It exhibits a photon echo signal resulting from a lensing process of the
fractional excitations: A pair of photon-excited fractional excitations,
initially moving apart, reverse their direction of motion, and annihilate each
other. In the XY chain, the nonlinearity in the dispersion relation of the
Jordan-Wigner fermions leads to the dispersion of the fractional excitation
wave packets and thereby suppresses lensing. The magnitude of the echo signal
decreases exponentially with increasing delay time. The decay rate scales with
the temperature $T$ as $T^{n}$ at low temperature, where $n$ is the leading
order of the Jordan-Wigner fermion dispersion, and as $T$ at high temperature.
By contrast, as the waiting time increases, the magnitude of the echo signal
saturates, reflecting the integrability of the system. Our results illustrate
the effectiveness of the 2DCS in detecting subtle dynamical properties of
optical excitations in spin chains.

##  I Introduction

The latest emergence of terahertz two-dimensional coherent spectroscopy (THz
2DCS) offers a new lens on the rich dynamical phenomena in condensed matter
[1]. Being a time domain, nonlinear optical spectroscopy, the 2DCS triggers
quantum interference processes of the optical excitations with successive
phase coherent pulses, thereby accessing information that is usually
unavailable to conventional, linear optical spectroscopies [2, 3]. Operating
in the meV energy window, THz 2DCS is well positioned to study collective
excitations in quantum materials. Experimentally, it has revealed a host of
interesting phenomena in quantum wells [1], antiferromagnets [4], electronic
glasses [5], and superconductors [6, 7]. Meanwhile, theorists have predicted
its potential utility for a wide range of systems from quantum spin liquids to
topological insulators [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19].

A prominent feature of the 2DCS is its ability to measure the _photon echo_
[20]. Photon echo is a third-order nonlinear optical response initiated by
three optical pulses, separated successively on the time axis by the delay
time $\tau$ and the waiting time $t_{w}$ (Fig. 1(a)). After the arrival of the
last pulse, the echo appears as the sudden rise of the nonlinear response at a
later time $t\approx\tau$. Closely analogous to the spin echo [21] in nuclear
magnetic resonance, the photon echo is a sensitive probe for dissipation.
Taking few-body systems as example, the fading of the echo with an increasing
delay time $\tau$ is a direct manifestation of decoherence, whereas the echo’s
falling off with increasing waiting time $t_{w}$ reflects depopulation.

This unique property of photon echo is traced back to the quantum interference
process that produces the echo. In the case of few-body systems, the photon
echo arises from an evolution trajectory of the density matrix (known as the
Liouville pathway) that executes an effective time reversal operation. Such an
operation erases all effects from the unitary evolution, and, consequently,
exposes the dissipation [2, 3].

The profound connection between the photon echo and the quantum interference
is amply demonstrated, as well as enriched, by examining many-body systems. In
a previous analysis, we consider the Tomonaga-Luttinger liquid (TLL) [11]
hosted by quantum spin chains. We find that its nonlinear magnetic response
features a photon echo similar to few-body systems. However, the physical
mechanism responsible for the echo is quite different. In this system, the
photon echo arises from _lensing_ (Fig. 1(b)), a spacetime interference
process of the fractional excitations in TLL such as spinons and Laughlin
quasiparticles [22]. The first optical pulse creates a pair of fractional
exctiations that are moving apart. Under the action of the second and the
third pulses, they reverse their directions of motion, and heading toward each
other. In the last stage, the annihilation of the two excitations produces the
echo.

Akin to the interference of waves, the lensing requires the coherent
propagation of the wave packets of fractional excitations. Basing on the
bosonization technique, the previous analysis approximates the TLL as a system
of non-interacting bosons with linear dispersion relation. In this highly
idealized situation, the photon echo is found to be independent of both the
delay time $\tau$ and the waiting time $t_{w}$, i.e. the echo does not fade
away. It is expected that dissipation and/or dispersion of the fractional
excitations, which must occur in any realistic, microscopic spin chains,
suppress lensing, and, consequently, the photon echo. Yet, these effects have
not been subjected to quantitative analysis by far.

In this work, we make a first pass at this problem by studying the photon echo
from $S=1/2$ spin XY chain [23], which hosts a TLL with the Luttinger
parameter $K=1$. Being equivalent to an ensemble of non-interacting Jordan-
Wigner fermions [24], this model possesses no inherent dissipation. However,
owing to the nonlinearity in the dispersion relation of the Jordan-Wigner
fermions, wave packets of fractional excitations disperse as they propagate
through the TLL. Meanwhile, the integrability of this model gives access to
its long time dynamics. Therefore, the $S=1/2$ spin XY chain is an ideal
platform for investigating the impact of dispersion on lensing and photon
echo.

Through numerical calculation, we verify that the dispersion of the fractional
excitations does lead to the decay of the photon echo. On one hand, the
magnitude of the echo signal decreases exponentially with increasing delay
time $\tau$. When the temperature $T$ is much less than the exchange energy
$J$, the decay constant is proportional to $T^{n}$, where $n$ is the order of
the Jordan-Wigner fermion dispersion, namely $n=3$ for the XY chain proper and
$n=2$ in the presence of a longitudinal magnetic field. When $T\gtrsim J$, the
decay constant scales linearly with $T$. On the other hand, as this model
possesses no inherent dissipation, the echo signal saturates to finite value
instead of fading away as the waiting time $t_{w}\to\infty$. These results
corroborate the physical picture presented in the previous work, and
illustrate the 2DCS’ capability in detecting subtle dynamical properties of
optical excitations in the context of spin chains.

The rest of this work is organized as follows. In Sec. II, we define the
problem. After describing the numerical method in Sec. III, we present our
results in Sec. IV. Finally, we discuss a few open problems in Sec. V.

Figure 1: (a) Photon echo is a third order nonlinear optical phenomenon
triggered by three successive pulses, separated by the pulse delay time $\tau$
and the waiting time $t_{w}$. The echo (gold solid line) is the sudden rise of
the response at a later time $t\approx\tau$. (b) The lensing of fractional
excitations in the Tomonaga-Luttinger liquid (TLL) hosted by spin chains. In
the case of the ferromagnetic XY chain ($J>0$ in Eq. (1), the first pulse
creates a pair of spinons. In the second stage, the second and third pulses
convert them to anti-spinons and reverse their directions of motion. Finally,
the two anti-spinons annihilate and emit echo. In the case of the
antiferromagnetic chain ($J<0$), the fractional excitations involved in the
lensing process are a spinon and a Laughlin quasiparticle. Due to the
dispersion of the wave packets, the second and the third pulses are no longer
effective in refocusing the excitations’ world lines. As a result, the lensing
is suppressed.

##  II Problem set up

The Hamiltonian for the $S=1/2$ XY spin chain is given by [23]:

$\displaystyle
H=-\frac{J}{2}\sum^{N-1}_{j=1}(S^{+}_{j}S^{-}_{j+1}+H.C.)-B\sum^{N}_{j=1}S^{z}_{j}.$
(1)

Here, $S^{\pm,z}_{j}$ are $S=1/2$ spin operators on site $j$. We employ the
open boundary condition. $J$ is the exchange constant, which is chosen to be
positive (ferromagnetic) without loss of generality. The antiferromagnetic
($J<0$) case is related to the present case by a staggered gauge
transformation, namely rotating the spins on even sites by $\pi$ with respect
to the $z$ axis. $B$ is a longitudinal field.

The system hosts a TLL when $B<J$. In this work, we consider the regime $B\ll
J$. The highly magnetized TLL ($B\lesssim J$) and the polarized phase ($B>J$)
are beyond the scope of this work as these regimes have very different
physics.

The quantities of central interest are the third order nonlinear magnetic
susceptibilities $\chi^{(3)}_{+--+}$ and $\chi^{(3)}_{-++-}$. Both exhibit the
photon echo described in Sec. I as per the analysis in [11]. As these two
susceptibilities show very similar behaviors, we only present results
concerning $\chi^{(3)}_{+--+}$ for brevity. To set the stage, we define the
following response function through the Kubo formula:

$\displaystyle\tilde{\chi}_{+--+}^{(3)}(3,2,1,0)=i^{3}\Theta(t_{1})\Theta(t_{2}-t_{1})\Theta(t_{3}-t_{2})$
$\displaystyle\times\langle[S_{j_{3}}^{+}(t_{3}),[S_{j_{2}}^{-}(t_{2}),[S_{j_{1}}^{-}(t_{1}),S_{N/2+1}^{+}(0)]]]\rangle.$
(2)

Here, $0\sim 3$ are shorthand notations for spacetime coordinates
$(t_{0},j_{0})\sim(t_{3},j_{3})$. We have utilized the space and time
translation symmetry to shift $t_{0}$ to $0$ and $x_{0}$ to the center of the
chain $N/2+1$. Since the wavelength of the THz electromagnetic wave is much
larger than the relevant microscopic length scales, we assume the spins couple
to the THz field homogeneously. Therefore, the optical response of the system
is obtained by summing over the lattice sites. It is convenient to define:

$\displaystyle\chi^{(3)}_{+--+}(q|t,t_{w},\tau)$
$\displaystyle=\sum_{j_{1}}\sum_{j_{2}}\sum_{j_{3}}\text{e}^{-iq(j_{1}+j_{2}-j_{3})}$
$\displaystyle\times\tilde{\chi}_{+--+}^{(3)}(3,2,1,0).$ (3)

Here, $t=t_{3}-t_{2}$, $t_{w}=t_{2}-t_{1}$, and $\tau=t_{1}$ are respectively
the gating time, the waiting time, and the delay time. $q=0$ for the
ferromagnetic chain, and $q=\pi$ for the antiferromagnetic chain owing to the
aforementioned staggered gauge transformation. Note the cases with other
values of $q$ are potentially relevant to XY chain with Dzyaloshinskii-Moriya
interactions [25, 26]. In this work, we solely consider $q=0$ and $\pi$.

$\chi^{(3)}_{+--+}$ and $\chi^{(3)}_{-++-}$ can be directly probed by 2DCS
using THz pulses with appropriate circular polarizations. Their contributions
are also visible with linearly polarized THz pulses since other third order
susceptibilities do not exhibit echo signal. This feature eases up on the
experimental conditions.

Finally, we obtain the two-dimensional spectrum by performing a Fourier
transform of $\chi^{(3)}_{+--+}(q|t,t_{w},\tau)$ with respect to $t$ and
$\tau$:

$\displaystyle\chi^{(3)}_{+--+}(q|\omega_{t},t_{w},\omega_{\tau})$
$\displaystyle=\int^{\infty}_{0}dt\int^{\infty}_{0}d\tau\,e^{i(\omega_{t}t+\omega_{\tau}\tau)}$
$\displaystyle\times\chi^{(3)}_{+--+}(q|t,t_{w},\tau).$ (4)

$\omega_{t}$ and $\omega_{\tau}$ are respectively the frequency variables
conjugate to the gating time $t$ and the pulse delay time $\tau$.

##  III Method

In this section, we sketch our numerical method for calculating Eq. (II) and
Eq. (II). Our procedure is similar in spirit to earlier works [27, 28], namely
expressing the spin correlation functions in terms of the non-local
correlation functions of Jordan-Wigner fermions. The main improvement lies in
the manner in which the non-local fermion correlation functions are treated.
In the preceding works, they are computed in terms of Pfaffians of fermion
Green’s functions. Here, we recast them as _determinants_ [29, 30, 31]. The
resulted expressions are more compact in form and faster to evaluate, which
speeds up the numerical calculation of the four-point spin correlation
functions considerably.

In the first step, we diagonalize the $S=1/2$ XY spin chain by way of the
Jordan-Wigner transformation,

$\displaystyle
S_{j}^{+}=\prod_{n<j}(1-2c_{n}^{\dagger}c^{\phantom{\dagger}}_{n})c_{j}^{\dagger},\quad
S_{j}^{z}=c_{j}^{\dagger}c^{\phantom{\dagger}}_{j}-1/2,$ (5)

where $c^{\dagger}_{j}$ and $c_{j}$ are fermion creation and annihilation
operators. After the transformation, Eq. (1) assumes the form of free fermion
chain:

$\displaystyle H$
$\displaystyle=-\frac{J}{2}\sum^{N-1}_{j=1}(c_{j}^{\dagger}c^{\phantom{\dagger}}_{j+1}+H.C.)-B\sum^{N}_{n=1}c_{j}^{\dagger}c_{j}$
$\displaystyle=\sum_{k}\epsilon(k)c^{\dagger}_{k}c^{\phantom{\dagger}}_{k}.\quad(N\to\infty)$
(6)

In the second line, we have taken the thermodynamic limit and switched to the
momentum space. $\epsilon(k)$ is the dispersion relation of the Jordan-Wigner
fermions:

$\displaystyle\epsilon(k)=-J\cos k-B.$ (7a) The ground state is thus given by
the Fermi sea. The dispersion near the Fermi point $k_{F}$ can be approximated
as:
$\displaystyle\epsilon(k)\approx\left\\{\begin{array}[]{cc}v_{F}(k-k_{F})-\frac{J}{6}(k-k_{F})^{3}&(B=0)\\\
v_{F}(k-k_{F})-\frac{B}{2}(k-k_{F})^{2}&(B\neq 0)\end{array}\right.,$ (7d)

with the Fermi velocity $v_{F}=\sqrt{J^{2}-B^{2}}$. We see that leading
correction to the linear dispersion relation is cubic (quadratic) in the
absence (presence) of the longitudinal field. We shall see their different
impacts on the photon echo in Sec. IV.

It is convenient for later purposes to define two sets of fermion Green’s
functions:

$\displaystyle G^{<}_{j_{1}j_{2}}(t_{1},t_{2})$ $\displaystyle=\langle
c^{\dagger}_{j_{1}}(t_{1})c_{j_{2}}(t_{2})\rangle.$ (8a) $\displaystyle
G^{>}_{j_{1}j_{2}}(t_{1},t_{2})$ $\displaystyle=-\langle
c_{j_{2}}(t_{2})c^{\dagger}_{j_{1}}(t_{1})\rangle.$ (8b)

Note their definitions differ from the usual “$G$-lesser” and “$G$-greater”
functions by a factor of $i$. They can be easily calculated from Eq. (III).

In the next step, we compute the four-point response function Eq. (II) by
expanding the nested commutators. This process yields a few four-point spin
correlation functions. These, in turn, are expressed as non-local correlation
functions of the Jordan-Wigner fermions. We recast these non-local correlation
functions as determinants of fermion Green’s functions $G^{>}$ and $G^{<}$.

The starting point is the following formula for a general multi-point fermion
correlation function:

$\displaystyle\left\langle\prod_{n=1}^{M}c^{\dagger}_{\alpha_{n}}c^{\phantom{\dagger}}_{\beta_{n}}\right\rangle=\det
Y,$ (9a) where $\alpha_{n}$ and $\beta_{n}$ are arbitrary labels of fermion
modes. Note the product is understood as an ordered product with $n=1$ on the
leftmost position and $n=M$ on the rightmost position. $Y$ is an $M\times M$
matrix whose entries are fermion Green’s functions: $\displaystyle
Y_{ij}=\left\\{\begin{array}[]{cc}\langle
c^{\dagger}_{\alpha_{i}}c^{\phantom{\dagger}}_{\beta_{j}}\rangle&i\leq j,\\\
-\langle
c^{\phantom{\dagger}}_{\beta_{j}}c^{\dagger}_{\alpha_{i}}\rangle&i>j.\end{array}\right..$
(9d)

Eq. (9) can be derived straightforwardly by using the Wick theorem.

As a preparation for later calculations, we consider the expectation value of
a non-local operator that resembles the Jordan-Wigner string:

$\displaystyle\left\langle\prod_{n=1}^{M}(1-2c^{\dagger}_{\alpha_{n}}c^{\phantom{\dagger}}_{\beta_{n}})\right\rangle$
$\displaystyle=\sum_{E}(-2)^{|E|}\left\langle\prod_{i\in
E}c^{\dagger}_{\alpha_{i}}c^{\phantom{\dagger}}_{\beta_{i}}\right\rangle$
$\displaystyle=\sum_{E}\det(-2Y_{E,E})$ $\displaystyle=\det(\text{I}-2Y).$
(10)

Here, $E$ is an subset of the $M$-element index set $\\{1,2,\cdots M\\}$. The
summation is over all possible subsets including the empty set. $|E|$ denotes
the number of elements of $E$. In the first line, we have expanded the
product. In the second line, we have used Eq. (9). Here, $Y_{E,E}$ is a
submatrix of $Y$ (Eq. (9d)), whose rows and columns are chosen from the set
$E$. Its determinant $\det Y_{EE}$ is known as the _principal minor_ of the
matrix $Y$. In the last line, we employ the summation formula for the
principal minors [32].

We proceed to calculate the spin correlation functions. It is sufficient for
our purpose to illustrate the procedure for the two-point spin correlation
functions. The four-point spin correlation functions is obtained in the same
vein. Consider:

$\displaystyle\langle S^{+}_{j_{1}}(t_{1})S^{-}_{j_{2}}(t_{2})\rangle$
$\displaystyle=\langle\prod_{n=1}^{j_{1}-1}(1-2c_{n}^{\dagger}(t_{1})c_{n}(t_{1}))c_{j_{1}}^{\dagger}(t_{1})$
$\displaystyle\times\prod_{m=1}^{j_{2}-1}(1-2c_{m}^{\dagger}(t_{2})c_{m}(t_{2}))c_{j_{2}}(t_{2})\rangle.$
(11)

We observe that the above expectation value, although resembles Eq. (III), is
not exactly identical to it. Specifically, the operator $c_{j_{1}}$ misses a
creation operator ($c^{\dagger}$) partner, and, likewise, $c_{j_{2}}$ misses
an annihilation operator ($c$) partner. We remedy this situation by
introducing auxiliary fermion operators $\psi$, $\psi^{\dagger}$, which we
take to be algebraically independent from $c$ fermions, i.e. $\psi$ and $c$
modes mutually anti-commute. We further assume the $\psi$ mode is unoccupied,
$\langle\psi^{\dagger}\psi\rangle=0$. Using these, we rewrite Eq. (III) as:

$\displaystyle\langle S^{+}_{j_{1}}(t_{1})S^{-}_{j_{2}}(t_{2})\rangle$
$\displaystyle=\frac{1}{4}\left\langle\prod_{n=1}^{j_{1}-1}(1-2c_{n}^{\dagger}(t_{1})c_{n}(t_{1}))(1-2c_{j_{1}}^{\dagger}(t_{1})\psi)\prod_{m=1}^{j_{2}-1}(1-2c_{m}^{\dagger}(t_{2})c_{m}(t_{2}))(1-2\psi^{\dagger}c_{j_{2}}(t_{2}))\right\rangle$
$\displaystyle-\frac{1}{4}\left\langle\prod_{n=1}^{j_{1}-1}(1-2c_{n}^{\dagger}(t_{1})c_{n}(t_{1}))\prod_{m=1}^{j_{2}-1}(1-2c_{m}^{\dagger}(t_{2})c_{m}(t_{2}))\right\rangle$
$\displaystyle=\frac{1}{4}(\det(I-2A)-\det(I-2B)).$ (12a) The first equality
follows from the definition of the $\psi$ fermions. The second equality
follows from Eq. (III). The matrices $A$ and $B$ are given by: $\displaystyle
A=\begin{pmatrix}G^{<}_{1:j_{1}-1,1:j_{1}-1}(t_{1},t_{1})&0_{(j_{1}-1)\times
1}&G^{<}_{1:j_{1}-1,1:j_{2}-1}(t_{1},t_{2})&G^{<}_{1:j_{1}-1,j_{2}}(t_{1},t_{2})\\\
G^{<}_{j_{1},1:j_{1}-1}(t_{1},t_{1})&0&G^{<}_{j_{1},1:j_{2}-1}(t_{1},t_{2})&G^{<}_{j_{1},j_{2}}(t_{1},t_{2})\\\
G^{>}_{1:j_{2}-1,1:j_{1}-1}(t_{2},t_{1})&0_{(j_{2}-1)\times
1}&G^{<}_{1:j_{2}-1,1:j_{2}-1}(t_{2},t_{2})&G^{<}_{1:j_{2}-1:j_{2}}(t_{2},t_{2})\\\
0_{1\times(j_{1}-1)}&-1&0_{1\times(j_{2}-1)}&0\end{pmatrix};$ (12b) and
$\displaystyle
B=\begin{pmatrix}G^{<}_{1:j_{1}-1,1:j_{1}-1}(t_{1},t_{1})&G^{<}_{1:j_{1}-1,1:j_{2}-1}(t_{1},t_{2})\\\
G^{>}_{1:j_{2}-1,1:j_{1}-1}(t_{1},t_{2})&G^{<}_{1:j_{2}-1,1:j_{2}-1}(t_{2},t_{2})\end{pmatrix}.$
(12c)

Here, the lesser and greater Green’s functions are defined in Eq. (8).
$G^{<}_{i:j,k:l}$ denotes the submatrix of $G^{<}$ whose rows and columns
range from $i$ to $j$ and $k$ to $l$, respectively. $G^{>}_{i:j,k:l}$ is
defined in the same vein. Substituting the above into Eq. (12), and performing
the Laplace expansion of $\det(I-2A)$ along the $j_{1}$-th column and the last
row yields:

$\displaystyle\langle S^{+}_{j_{1}}(t_{1})S^{-}_{j_{2}}(t_{2})\rangle$
$\displaystyle=\frac{(-1)^{j_{2}}}{2}\det\begin{pmatrix}[I-2G^{<}(t_{1},t_{1})]_{1:j_{1},1:j_{1}-1}&-2G^{<}_{1:j_{1},1:j_{2}}(t_{1},t_{2})\\\
-2G^{>}_{1:j_{2}-1,1:j_{1}-1}(t_{1},t_{2})&[I-2G^{<}(t_{2},t_{2})]_{1:j_{2}-1,1:j_{2}}\end{pmatrix}.$
(13)

The calculation of the four-point spin correlation function parallels that of
the two-point spin correlation function but is more involved. We only present
the result for brevity. All four point correlation function can be cast in a
fairly regular form:

$\displaystyle\langle
S^{\mu_{1}}_{j_{1}}(t_{1})S^{\mu_{1}}_{j_{2}}(t_{2})S^{\mu_{3}}_{j_{3}}(t_{3})S^{\mu_{4}}_{j_{4}}(t_{4})\rangle=\frac{(-1)^{j_{2}+j_{4}}}{4}$
$\displaystyle\times\det\begin{pmatrix}[I-2G^{<}(t_{1},t_{1})]_{J_{1},J^{\prime}_{1}}&-2G^{<}(t_{1},t_{2})_{J_{1},J^{\prime}_{2}}&-2G^{<}(t_{1},t_{3})_{J_{1},J^{\prime}_{3}}&-2G^{<}(t_{1},t_{4})_{J_{1},J^{\prime}_{4}}\\\
-2G^{>}(t_{1},t_{2})_{J_{2},J^{\prime}_{1}}&[I-2G^{<}(t_{2},t_{2})]_{J_{2},J^{\prime}_{2}}&-2G^{<}(t_{2},t_{3})_{J_{2},J^{\prime}_{3}}&-2G^{<}(t_{2},t_{4})_{J_{2},J^{\prime}_{4}}\\\
-2G^{>}(t_{1},t_{3})_{J_{3},J^{\prime}_{1}}&-2G^{>}(t_{2},t_{3})_{J_{3},J^{\prime}_{2}}&[I-2G^{<}(t_{3},t_{3})]_{J_{3},J^{\prime}_{3}}&-2G^{<}(t_{3},t_{4})_{J_{3}J^{\prime}_{4}}\\\
-2G^{>}(t_{1},t_{4})_{J_{4}.J^{\prime}_{1}}&-2G^{>}(t_{2},t_{4})_{J_{4},J^{\prime}_{2}}&-2G^{>}(t_{3},t_{4})_{J_{4},J^{\prime}_{3}}&[I-2G^{<}(t_{4},t_{4})]_{J_{4},J^{\prime}_{4}}\end{pmatrix}.$
(14)

Here, the greek indices $\mu_{1,2,3,4}=\pm$ refer to the raising/lowering type
of the spin operator. $J_{1,2,3,4}$ and $J^{\prime}_{1,2,3,4}$ are index sets.
$J_{i}=\\{1,2,\cdots j_{i}\\}$ ($\\{1,2,\cdots j_{i}-1\\}$) when $\mu_{i}=+$
($\mu_{i}=-$). Likewise, $J^{\prime}_{i}=\\{1,2,\cdots j_{i}-1\\}$
($\\{1,2,\cdots j_{i}\\}$) when $\mu_{i}=+$ ($\mu_{i}=-$).

The final step is carrying out the summation over the lattice sites
$j_{1,2,3}$ in Eq. (II). Instead of summing over all sites, we reduce the
computational work load by utilizing causality, namely
$\tilde{\chi}_{+--+}^{(3)}(0,1,2,3)$ falls off exponentially outside the light
cone about the center of the chain. Therefore, we may restrict the summation
over $j_{1,2,3}$ to $\pm(Jt_{1,2,3}+R)$, where $Jt$ is the radius of the light
cone at time $t$, and $R$ represents the size of a small interval outside the
cone. We choose $R=5$, which yields a relative error on the order of
$10^{-3}$. Furthermore, we reduce the work load by half by using the inversion
symmetry with respect to the center of the chain.

We close this section by commenting on the computational complexity. For a
chain with $N$ sites, computing a four-point spin correlation function
requires evaluating a single determinant of typical size $O(N)$, whose
complexity is $O(N^{3})$. Taking the triple lattice summation into account,
the complexity for computing the third-order susceptibility is thus
$O(N^{6})$. This scaling limits the numerically accessible system size, and,
as a result, the simulation time and temperature. With the various
improvements described in this section, we are able to compute the full two-
dimensional spectrum of systems up to $N=157$ with $O(10^{6})$ CPU hours. For
calculating the magnitude of photon echo signal, we can reach system size up
to $N=357$ by further restricting the lattice summation to sites close to the
lensing configurations (Fig. 1(b)).

Figure 2: (a) Nonlinear magnetic susceptibility $\chi_{+--+}^{(3)}$ as a
function of $t$ and $\tau$ for the ferromagnetic ($q=0$ in Eq. II) chain at
$T/J=0.3$ and in zero field. The waiting time $t_{w}=0$. The data are rescaled
such that its maximum magnitude equals to $1$. (b) A scan of the data with
constant $\tau$ as indicated by the arrow “(b)” in panel (a). The red dashed
line delineates the expected asymptotic behavior. (c) A constant $t$ scan of
the data as indicated by the arrow “(c)” in panel (a). The red dashed line
delineates the expected asymptotic behavior. (d) A constant $\tau$ scan of the
data as indicated by the arrow “(d)” in panel (a), which shows the full
profile of the photon echo. (e) The data along the diagonal direction of the
$t$-$\tau$ plane as indicated by the arrow “(e)” in panel (a). (f) The complex
modulus of the two dimensional spectrum. The data are rescaled similarly to
(a). Figure 3: The same as Fig 2 but for antiferromagnetic ($q=\pi$ in Eq.
(II)) chain.

##  IV Results

Fig. 2(a) shows the numerically calculated nonlinear magnetic susceptibility
$\chi_{+--+}^{(3)}$ as a function of $t$ and $\tau$ for the ferromagnetic
chain ($q=0$ in Eq. II) at $T/J=0.3$ and $B=0$. We set waiting time $t_{w}=0$.
Note the susceptibility is a real number in this case. The photon echo signal
appears as the feature running along the diagonal of the $t$-$\tau$ plane.
Taking a cut with constant $\tau$ reveals the structure of the echo signal
(Fig. 2(d), with $J\tau=15$). We see the nonlinear response reaches the
maximum at $t\approx\tau$, which is the characteristic of the photon echo. Our
previous analysis predicts the following asymptotic behavior for the photon
echo signal [11]:

$\displaystyle\chi_{+--+,q=0}^{(3)}\sim\left\\{\begin{array}[]{cc}(t-\tau)^{3}e^{-\gamma|t-\tau|}&(t\gg\tau\gg
0)\\\ (t-\tau)e^{-\gamma|t-\tau|}&(\tau\gg t\gg 0)\end{array}\right.,$ (17)

where $\gamma=\pi T/2$. The numerical results confirm these predictions (Fig.
2(b)(c)).

For the ideal TLL where the fractional excitations neither disperse nor
dissipate, our previous analysis shows that the echo persists along the
diagonal direction of the $t$-$\tau$ plane, i.e. the echo does not depend on
$\tau$. Here, the diagonal feature in Fig. 2(a) associated with the photon
echo gradually fades away at large $\tau,t$. The decay of the photon echo
signal is best illustrated by taking a cut of Fig. 2(a) along the diagonal
direction of the $t$-$\tau$ plane (Fig 2(e)). After the initial rise, the echo
signal decreases exponentially as $\tau=t$ increases. This information is also
encoded in the two-dimensional spectrum (Fig 2(f)), where the photon echo is
manifest as a pair of peaks on the $\omega_{t}$-$\omega_{\tau}$ plane. The
anti-diagonal width of photon echo peaks is inversely proportional to the
decay time of the echo signal, whereas the diagonal width of the peaks scales
with temperature linearly.

We attribute the decay of the photon echo signal to the nonlinearity of the
dispersion relation of the Jordan-Wigner fermions (Eq. (7)). A key step in
lensing is the refocusing of the excitation world lines by the second and
third pulses (Fig. 1(b)). This process occurs because acting the spin
raising/lowering operator on the fractional excitations reverses their
direction of motion and changes the topological charge they carry [11].
However, due to the aforementioned nonlinearity, a fractional excitation wave
packet disperses as it travels through the system. As a result, the refocusing
is no longer prefect, which suppresses the lensing process. We shall discuss
further on the decay of the photon echo momentarily.

Having discussed the ferromagnetic chain, we turn to the antiferromagnetic
case ($q=\pi$ in Eq. (II)). Fig 3(a) shows the nonlinear magnetic
susceptibility $\chi_{+--+}^{(3)}$ as a function of $t$ and $\tau$ with the
same set of model parameters. Compared to the ferromagnetic case, the photon
echo signal is disguised at early time by other nonlinear responses;
nonetheless, it is clearly visible at late times. Fig. 3(d) shows the profile
of the photon echo along a cut with constant $J\tau=15$. We note its overall
span on the time axis is shorter than that of the ferromagnetic case (Fig.
2(d)).

Our previous work predicts the following asymptotic behavior for the photon
echo in the antiferromagnetic case [11]:

$\displaystyle\chi_{+--+,q=\pi}^{(3)}\sim\left\\{\begin{array}[]{cc}(t-\tau)e^{-\gamma|t-\tau|}&(t\gg\tau\gg
0)\\\ e^{-\gamma|t-\tau|}&(\tau\gg t\gg 0)\end{array}\right.,$ (20)

where $\gamma$ is the same as before 111Note, however, the constant $\gamma$
taking the same value for the ferro- and antiferromagnetic chain is a special
feature of the XY chain, or TLL with $K=1$. See 11 for the expression of
$\gamma$ for general $K$.. We find good agreement between the numerical
results and the prediction for $t>\tau$ (Fig. 3(b)) but much less so for
$t<\tau$ (Fig. 3(c)). The small magnitude of the signal for the latter case
makes it challenging to numerically ascertain the asymptotic behavior. Similar
to the ferromagnetic case, the photon echo decreases exponentially with $\tau$
(Fig. 3(e)).

Fig 3(f) shows the two dimensional spectrum. Note we have masked out the data
with $Jt<3$ and $J\tau<3$ in the Fourier transform to enhance the photon echo
peaks. We see that the photon echo peaks are more extended in the frequency
plane compared with the ferromagnetic chain, which is directly related to its
shorter span on the time axis (Fig. 2(d)) relative to the ferromagnetic case.

Figure 4: (a) The behavior of $\chi_{+--+}^{(3)}$ at $t=\tau$ for the
ferromagnetic chain at various temperatures and in zero field. The waiting
time $t_{w}=0$. (b) The decay time $\tau_{\mathrm{disp}}$ as a function of
temperature. The blue and green open circles represent the case with $B=0$ and
$B=0.3J$, respectively. The blue solid line, the blue broken line, and the
green solid line delineate respectively the power law $T^{\alpha}$ with
exponents $\alpha=3$, $1$, and $2$, respectively. (c)(d) Same as (a)(b) but
for antiferromagnetic chain. Figure 5: The nonlinear magnetic susceptibility
$\chi^{(3)}_{+--+}$ as a function of $t_{w}$ at various values of $t=\tau$ for
the ferromagnetic (a) and antiferromagnetic (b) chain. The temperature
$T/J=0.25$, and the magnetic field $B=0$. Numerical data are denoted as filled
circles. Solid lines are fitting of the data to exponential functions. Arrows
mark the extrapolated value of $\chi^{(3)}_{+--+}$ at $t_{w}\to\infty$.

We now investigate the decay of the photon echo in more detail. Fig. 4(a)(c)
(solid lines) show the value of $\chi_{+--+}^{(3)}$ along the diagonal
direction ($\tau=t$) in the $t$-$\tau$ plane at various temperatures for both
the ferromagnetic and the antiferromagnetic chains. For both cases, and at all
numerically accessible temperatures, we find the echo signal decreases
exponentially at late time, i.e.

$\displaystyle\chi^{(3)}_{+--+}(t=\tau)\sim e^{-\tau/\tau_{\mathrm{disp}}},$
(21)

where $\tau_{\mathrm{disp}}$ is the decay time of the echo signal. Physically,
we interpret $\tau_{\mathrm{disp}}$ as an effective life time of the
fractional excitations created by the first pulse — in the case of the
ferromagnetic chain, they are a pair of spinons; in the case of the
antiferromagnetic chain, they are a spinon and a Laughlin quasiparticle [22].
Their wave packets broaden as they propagate. Beyond the time
$\tau_{\mathrm{disp}}$, they are virtually indistinguishable from the thermal
fluctuations. Fig. 4(b)(d) (open circles) present the dependence of
$\tau_{\mathrm{disp}}$ on temperature, extracted by fitting the
$\chi^{(3)}_{+--+}(t=\tau)$ data to an exponential function. We identify two
regimes: At low temperature $T\ll J$, $1/\tau_{\mathrm{disp}}\propto T^{3}$;
at higher temperature $T\sim J$ or higher, we find
$1/\tau_{\mathrm{disp}}\propto T$.

We may understand the low temperature $T^{3}$ scaling by a simple dimension
counting argument. At the renormalization group (RG) fixed point, the
Hamiltonian of TLL is that of free, relativistic bosons. At the fixed point,
the lensing is perfect, and the photon echo does not decay. Now, the
nonlinearity in the dispersion relation of the Jordan-Wigner fermions at $B=0$
gives rise to the following RG irrelevant perturbation to the fixed point
Hamiltonian:

$\displaystyle H^{\prime}=\int dx\,$
$\displaystyle\lambda_{+}(\nabla\phi_{R})^{2}(\nabla\phi_{L})^{2}$
$\displaystyle+$
$\displaystyle\lambda_{-}[(\nabla\phi_{R})^{4}+(\nabla\phi_{L})^{4})].$ (22)

The explicit value of $\lambda_{\pm}$ are determined by the microscopic model
[33, 34, 35]. Both $\lambda_{\pm}$ have dimension $2$ in unit of length. Given
that they are RG irrelevant, we expect $1/\tau_{\mathrm{disp}}$ admits a
perturbative expansion in $\lambda_{\pm}$. The dimensional analysis then
reveals $1/\tau_{\mathrm{disp}}\sim\lambda_{\pm}T^{3}$ to the leading order.

This analysis immediately implies that $1/\tau_{\mathrm{disp}}\sim T^{n}$,
where $n$ is the leading order of the Jordan-Wigner fermion dispersion. In the
presence of longitudinal magnetic field, the leading order changes from $n=3$
to $n=2$ (Eq. (7)). Thus, we expect a $T^{2}$ scaling in this case. Our
numerical results show that $1/\tau_{\mathrm{disp}}\propto T^{2}$ for both
ferromagnetic and antiferromagnetic chains, in agreement with the analysis
(Fig. 4(b),(d)).

So far, we have fixed the waiting time $t_{w}=0$. The dependence of the photon
echo on $t_{w}$ also contains important information about the dynamics of the
system. Fig. 5(a) and (b) present $\chi_{+--+}^{(3)}$ as a function of $t_{w}$
with fixed $t=\tau$ for ferromagnetic chain and antiferromagnetic chain,
respectively. We set the temperature $T/J=0.25$ and magnetic field $B=0$. For
both cases, we find the data can be well fit to an exponential function,
$A\exp(-\alpha t_{w})+A^{\prime}$. Crucially, we find $A^{\prime}\neq 0$; i.e.
the magnitude of the echo signal saturates at $t_{w}\to\infty$ instead of
decreasing to zero.

This behavior is associated to the integrability of the $S=1/2$ XY spin chain.
In a thermalizing system, so long as the response is not tied to any
conservation law or spontaneously broken symmetry, the nonlinear response
function _must_ tend to zero as $t_{w}\to\infty$ because the memory about the
first two pulses is lost. Therefore, the fact that $\chi^{(3)}_{+--+}$ does
_not_ decrease to zero is necessarily a consequence of the integrability. In
our previous work [11], we hypothesized that the saturation of the photon echo
signal with $t_{w}$ is a feature of integrable spin chains. Our results seem
to support this idea.

##  V Discussion

In this work, we have analyzed the photon echo of the $S=1/2$ XY spin chain.
Through numerical calculations, we show that the photon echo signal decays
with increasing pulse delay time $\tau$, whereas it saturates as the waiting
time $t_{w}\to\infty$. The former reflects the suppression of lensing due to
the dispersion of the fractional excitation wave packets. The latter, on the
other hand, is a manifestation of the integrability of the model. These
results are in broad agreement with the physical picture presented in the
previous work. Furthermore, the numerically extracted asymptotic behavior of
the echo signal is also quantitatively consistent with the prediction.

Our numerical calculation reveals that the decay rate of the photon echo (with
the delay time $\tau$) scales with the temperature $T$ as $T^{n}$, where $n$
is the order of the leading nonlinearity in the dispersion relation of the
Jordan-Wigner fermions. The nonlinearity in the fermion dispersion relation,
and its physical consequences, are the central topics of the nonlinear
Luttinger liquid theory [36, 37]. Although a formidable task, it would be
illuminating to treat the present problem analytically by using this approach.

Adding _generic_ longitudinal exchange interactions to the $S=1/2$ XY chain
breaks the integrability of the model. As a result, the fractional excitations
now disperse as well as dissipate, which leads to additional decay of the echo
signal with respect to the delay time $\tau$. In the bosonization language,
this perturbation is amount to an umklapp term in the bosonized Hamiltonian.
Comparing the RG eigenvalue of the umklapp term $2-4K$ to that of the
dispersion term $-2$, we expect that the dispersion-induced decay remains the
dominant mechanism when $K>1$ [34]. Outside this regime, a systematic
treatment of dissipation is necessary to clarify its impact.

Finally, we have seen that saturation of the echo signal with $t_{w}$ is
associated with the integrability of the $S=1/2$ XY spin chain. We think that
the integrability of a many-body system is manifest in a nonlinear response
function is remarkable. In light of the studies on the out-of-time-order
correlation functions [38, 39, 40], it is perhaps interesting to explore
whether the photon echo could provide an in-depth characterization of quantum
chaos, or the lack thereof, of many-body systems.

###### Acknowledgements.

This work is supported by the National Natural Science Foundation of China
(Grant No. 12250008, 11974396, and 12188101), by the National Key R&D Program
of China (Grant No. 2022YFA1403800), and by the Chinese Academy of Sciences
through the Strategic Priority Research Program (Grant No. XDB33020300), and
the Project for Young Scientists in Basic Research (Grant No. YSBR-059).

## References

  * Woerner  _et al._ [2013] M. Woerner, W. Kuehn, P. Bowlan, K. Reimann, and T. Elsaesser, Ultrafast two-dimensional terahertz spectroscopy of elementary excitations in solids, New Journal of Physics 15, 025039 (2013).
  * Mukamel [1995] S. Mukamel,  _Principles of Nonlinear Optical Spectroscopy_ (Oxford University Press, Oxford, 1995).
  * Hamm and Zanni [2011] P. Hamm and M. Zanni,  _Concepts and Methods of 2D Infrared Spectroscopy_ (Cambridge University Press, Cambridge, 2011).
  * Lu  _et al._ [2017] J. Lu, X. Li, H. Y. Hwang, B. K. Ofori-Okai, T. Kurihara, T. Suemoto, and K. A. Nelson, Coherent Two-Dimensional Terahertz Magnetic Resonance Spectroscopy of Collective Spin Waves, Phys. Rev. Lett. 118, 207204 (2017).
  * Mahmood  _et al._ [2021] F. Mahmood, D. Chaudhuri, S. Gopalakrishnan, R. Nandkishore, and N. Armitage, Observation of a marginal fermi glass, Nature Physics 17, 627 (2021).
  * Luo  _et al._ [2022] L. Luo, M. Mootz, J. Kang, C. Huang, K. Eom, J. Lee, C. Vaswani, Y. Collantes, E. Hellstrom, I. Perakis, _et al._ , Quantum coherence tomography of lightwave controlled superconductivity, Nature Physics 19, 201 (2022).
  * Zhang  _et al._ [2023] S. Zhang, Z. Sun, Q. Liu, Z. Wang, Q. Wu, L. Yue, S. Xu, T. Hu, R. Li, X. Zhou, _et al._ , Revealing the frequency-dependent oscillations in nonlinear terahertz response induced by Josephson current, National Science Review , nwad163 (2023).
  * Wan and Armitage [2019] Y. Wan and N. P. Armitage, Resolving Continua of Fractional Excitations by Spinon Echo in THz 2D Coherent Spectroscopy, Phys. Rev. Lett. 122, 257401 (2019).
  * Choi  _et al._ [2020] W. Choi, K. H. Lee, and Y. B. Kim, Theory of Two-Dimensional Nonlinear Spectroscopy for the Kitaev Spin Liquid, Phys. Rev. Lett. 124, 117205 (2020).
  * Parameswaran and Gopalakrishnan [2020] S. A. Parameswaran and S. Gopalakrishnan, Asymptotically Exact Theory for Nonlinear Spectroscopy of Random Quantum Magnets, Phys. Rev. Lett. 125, 237601 (2020).
  * Li  _et al._ [2021] Z.-L. Li, M. Oshikawa, and Y. Wan, Photon echo from lensing of fractional excitations in Tomonaga-Luttinger spin liquid, Physical Review X 11, 031035 (2021).
  * Nandkishore  _et al._ [2021] R. M. Nandkishore, W. Choi, and Y. B. Kim, Spectroscopic fingerprints of gapped quantum spin liquids, both conventional and fractonic, Physical Review Research 3, 013254 (2021).
  * Fava  _et al._ [2021] M. Fava, S. Biswas, S. Gopalakrishnan, R. Vasseur, and S. Parameswaran, Hydrodynamic nonlinear response of interacting integrable systems, Proceedings of the National Academy of Sciences 118, e2106945118 (2021).
  * Hart and Nandkishore [2023] O. Hart and R. Nandkishore, Extracting spinon self-energies from two-dimensional coherent spectroscopy, Physical Review B 107, 205143 (2023).
  * Gao  _et al._ [2023] Q. Gao, Y. Liu, H. Liao, and Y. Wan, Two-dimensional coherent spectrum of interacting spinons from matrix product states, Physical Review B 107, 165121 (2023).
  * Negahdari and Langari [2023] M. K. Negahdari and A. Langari, Nonlinear response of the Kitaev honeycomb lattice model in a weak magnetic field, Physical Review B 107, 134404 (2023).
  * Sim  _et al._ [2023a] G. Sim, J. Knolle, and F. Pollmann, Nonlinear spectroscopy of bound states in perturbed Ising spin chains, Physical Review B 107, L100404 (2023a).
  * Sim  _et al._ [2023b] G. Sim, F. Pollmann, and J. Knolle, Shedding Light on Microscopic Details: 2D Spectroscopy of 1D Quantum Ising Magnets (2023b), arXiv:2305.04920 [cond-mat.str-el] .
  * Qiang  _et al._ [2023] Y. Qiang, V. L. Quito, T. V. Trevisan, and P. P. Orth, Probing Majorana wavefunctions in Kitaev honeycomb spin liquids with second-order two-dimensional spectroscopy (2023), arXiv:2301.11243 [cond-mat.str-el] .
  * Kurnit  _et al._ [1964] N. A. Kurnit, I. D. Abella, and S. R. Hartmann, Observation of a Photon Echo, Phys. Rev. Lett. 13, 567 (1964).
  * Hahn [1950] E. L. Hahn, Spin Echoes, Phys. Rev. 80, 580 (1950).
  * Pham  _et al._ [2000] K.-V. Pham, M. Gabay, and P. Lederer, Fractional excitations in the Luttinger liquid, Phys. Rev. B 61, 16397 (2000).
  * Lieb  _et al._ [1961] E. Lieb, T. Schultz, and D. Mattis, Two soluble models of an antiferromagnetic chain, Annals of Physics 16, 407 (1961).
  * Jordan and Wigner [1928] P. Jordan and E. Wigner, Über das paulische äquivalenzverbot, Zeitschrift für Physik 47, 631 (1928).
  * Gangadharaiah  _et al._ [2008] S. Gangadharaiah, J. Sun, and O. A. Starykh, Spin-orbital effects in magnetized quantum wires and spin chains, Phys. Rev. B 78, 054436 (2008).
  * Povarov  _et al._ [2022] K. Y. Povarov, T. A. Soldatov, R.-B. Wang, A. Zheludev, A. I. Smirnov, and O. A. Starykh, Electron spin resonance of the interacting spinon liquid, Phys. Rev. Lett. 128, 187202 (2022).
  * Derzhko and Krokhmalskii [1998] O. Derzhko and T. Krokhmalskii, Numerical Approach for the Study of the Spin-$1/2$ XY Chains Dynamic Properties, Physica Status Solidi (B) 208, 221 (1998).
  * Maeda and Oshikawa [2003] Y. Maeda and M. Oshikawa, Numerical analysis of electron-spin resonance in the spin-$\frac{1}{2}$ $\mathrm{XY}$ model, Phys. Rev. B 67, 224424 (2003).
  * McCoy  _et al._ [1971] B. M. McCoy, E. Barouch, and D. B. Abraham, Statistical Mechanics of the $\mathrm{XY}$ Model. IV. Time-Dependent Spin-Correlation Functions, Phys. Rev. A 4, 2331 (1971).
  * Colomo  _et al._ [1993] F. Colomo, A. G. Izergin, V. E. Korepin, and V. Tognetti, Temperature correlation functions in the XX0 Heisenberg chain. I, Theoretical and Mathematical Physics 94, 11 (1993).
  * Zvonarev  _et al._ [2009] M. B. Zvonarev, V. V. Cheianov, and T. Giamarchi, The time-dependent correlation function of the Jordan–Wigner operator as a Fredholm determinant, Journal of Statistical Mechanics: Theory and Experiment 2009, P07035 (2009).
  * Meyer [2000] C. D. Meyer,  _Matrix Analysis and Applied Linear Algebra_ (Society for Industrial and Applied Mathematics, Philadelphia, 2000).
  * Lukyanov [1998] S. Lukyanov, Low energy effective Hamiltonian for the $\mathrm{XXZ}$ spin chain, Nuclear Physics B 522, 533 (1998).
  * Poboiko and Feigel’man [2016] I. Poboiko and M. Feigel’man, Spin correlation functions and decay of quasiparticles in $\mathrm{XXZ}$ spin chain at $T>0$, Phys. Rev. B 94, 195420 (2016).
  * Samokhin [1998] K. V. Samokhin, Lifetime of excitations in a clean Luttinger liquid, Journal of Physics: Condensed Matter 10, L533 (1998).
  * Imambekov  _et al._ [2012] A. Imambekov, T. L. Schmidt, and L. I. Glazman, One-dimensional quantum liquids: Beyond the Luttinger liquid paradigm, Rev. Mod. Phys. 84, 1253 (2012).
  * Imambekov and Glazman [2009] A. Imambekov and L. I. Glazman, Universal Theory of Nonlinear Luttinger Liquids, Science 323, 228 (2009).
  * Larkin and Ovchinnikov [1969] A. I. Larkin and Y. N. Ovchinnikov, Quasiclassical method in the theory of superconductivity, Sov Phys JETP 28, 1200 (1969).
  * Maldacena  _et al._ [2016] J. Maldacena, S. H. Shenker, and D. Stanford, A bound on chaos, Journal of High Energy Physics 2016, 1 (2016).
  * Maldacena and Stanford [2016] J. Maldacena and D. Stanford, Remarks on the Sachdev-Ye-Kitaev model, Physical Review D 94, 106002 (2016).