$\displaystyle\mathsf{\widehat{col}}(\pi)=\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma^{\\#}_{2}))$
$\displaystyle=\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A}_{a},s,\sigma^{\prime}_{1},\sigma^{a}_{2}))$
$\displaystyle\text{because }\pi\text{ stays in }\mathcal{A}_{a}\text{ and
never visits }t,$
$\displaystyle\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A}_{a},s,\sigma^{a}_{1},\sigma^{a}_{2}))$
$\displaystyle\text{because }(\sigma_{1}^{a},\sigma^{a}_{2})\text{ is an NE
from }s\text{ in }\mathcal{A}_{a},$
$\displaystyle=\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{\\#}_{1},\sigma^{\\#}_{2}))$
$\displaystyle\text{because these strategies stay in }\mathcal{A}_{a},$

hence the leftmost inequality is verified in the case where $\pi$ never visits
$t$.

It remains to consider the case where $\pi$ does visit $t$. Observe that for
the moment, we have not used $\mathcal{M}^{\mathsf{c}}$-selectivity and the
fact that $s\in S_{\mathsf{cov}}$: they will be crucial to solve this (more
complex) case.

We define
$K^{\mathsf{c}}_{j}=\mathsf{\widehat{col}}\big{(}\\{\rho\in\mathsf{Hists}(\mathcal{A}_{j},t,\sigma_{2}^{j})\mid\mathsf{out}(\rho)=t\\}\big{)}$,
for $j\in\\{a,b\\}$, that is, $K^{\mathsf{c}}_{j}$ contains all (projections
to colors of) cycles on $t$ consistent with $\sigma_{2}^{j}$ (i.e., the
strategy from the subgame NE) in subarena $\mathcal{A}_{j}$. Since the unique
play $\pi\in\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma^{\\#}_{2})$ visits
$t$ at least once, we write $\pi=\rho\cdot\pi^{\prime}$ for $\rho$, the prefix
ending with the first visit of $t$. Let $w=\mathsf{\widehat{col}}(\rho)$.
Observe that

$\mathsf{\widehat{col}}(\pi)\in[w(K^{\mathsf{c}}_{a}\cup
K^{\mathsf{c}}_{b})^{\ast}(K^{\mathsf{p}}_{a}\cup K^{\mathsf{p}}_{b})]$

since $\sigma_{2}^{\\#}$ alternates between $\sigma_{2}^{a}$ and
$\sigma_{2}^{b}$ depending on what $\mathcal{P}_{1}$ plays in $t$.
Intuitively, either $\pi$ cycles infinitely often on $t$ using cycles of
$(K^{\mathsf{c}}_{a}\cup K^{\mathsf{c}}_{b})$, or it does it for a while, then
switches to $(K^{\mathsf{p}}_{a}\cup K^{\mathsf{p}}_{b})$, which induces that
$\pi$ commits to a subarena. Thus, we trivially have
$\mathsf{\widehat{col}}(\pi)\sqsubseteq[w(K^{\mathsf{c}}_{a}\cup
K^{\mathsf{c}}_{b})^{\ast}(K^{\mathsf{p}}_{a}\cup K^{\mathsf{p}}_{b})]$.

Since $\mathcal{M}^{\mathsf{c}}$ is a cyclic-cover of $S_{\mathsf{cov}}$ in
$\mathcal{A}$, and $\rho$ starts in $S_{\mathsf{cov}}$, we know that for
$m^{\mathsf{c}}=\widehat{\alpha_{\mathsf{upd}}^{\mathsf{c}}}(m_{\mathsf{init}}^{\mathsf{c}},\mathsf{\widehat{col}}(\rho))$,
and for all $\rho^{\prime}\in\mathsf{Hists}(\mathcal{A})$ such that
$\mathsf{in}(\rho^{\prime})=\mathsf{out}(\rho^{\prime})=t$, we have
$\widehat{\alpha_{\mathsf{upd}}^{\mathsf{c}}}(m^{\mathsf{c}},\mathsf{\widehat{col}}(\rho^{\prime}))=m^{\mathsf{c}}$.
That is, all cycles on $t$ are read as cycles on $m^{\mathsf{c}}$ in
$\mathcal{M}^{\mathsf{c}}$. This implies that
$K^{\mathsf{c}}_{a},K^{\mathsf{c}}_{b}\subseteq
L_{m^{\mathsf{c}},m^{\mathsf{c}}}$. Knowing that, we can invoke the
$\mathcal{M}^{\mathsf{c}}$-selectivity (Equation (8)) of the preference
relation to obtain

$\displaystyle\mathsf{\widehat{col}}(\pi)$
$\displaystyle\sqsubseteq[w(K^{\mathsf{c}}_{a})^{\ast}]\cup[w(K^{\mathsf{c}}_{b})^{\ast}]\cup[w(K^{\mathsf{p}}_{a}\cup
K^{\mathsf{p}}_{b})].$

Using Lemma 1, we have

$\displaystyle\mathsf{\widehat{col}}(\pi)\sqsubseteq[w(K^{\mathsf{c}}_{a})^{\ast}]\cup[w(K^{\mathsf{c}}_{b})^{\ast}]\cup[wK^{\mathsf{p}}_{a}]\cup[wK^{\mathsf{p}}_{b}].$

Observe that $[w(K^{\mathsf{c}}_{j})^{\ast}]\subseteq[wK^{\mathsf{p}}_{j}]$,
for $j\in\\{a,b\\}$. Hence, we have

$\displaystyle\mathsf{\widehat{col}}(\pi)$
$\displaystyle\sqsubseteq[wK^{\mathsf{p}}_{a}]\cup[wK^{\mathsf{p}}_{b}].$

Now, recall that using the $\mathcal{M}^{\mathsf{p}}$-monotony of
$\sqsubseteq$, we assumed that $\forall\,w\in
L^{\mathsf{p}}_{m_{\mathsf{init}}^{\mathsf{p}},m_{t}^{\mathsf{p}}},\;[wK^{\mathsf{p}}_{b}]\sqsubseteq[wK^{\mathsf{p}}_{a}]$.
Since $\rho$ starts in $S_{\mathsf{cov}}$ and $\mathcal{M}^{\mathsf{p}}$ is a
prefix-cover of $S_{\mathsf{cov}}$, this inequality is in particular true for
$w=\mathsf{\widehat{col}}(\rho)$. Hence, we have

$\displaystyle\mathsf{\widehat{col}}(\pi)$
$\displaystyle\sqsubseteq[wK^{\mathsf{p}}_{a}].$

Now, recall that $(\sigma_{1}^{a},\sigma_{2}^{a})$ is an NE from
$S_{\mathsf{cov}}$ in $\mathcal{G}_{a}$. Recall also that $w$ represents the
history up to the first visit of $t$ consistent with
$(\sigma_{1},\sigma_{2}^{\\#})$; it is also consistent with
$(\sigma_{1},\sigma_{2}^{a})$ since $\sigma_{2}^{\\#}$ follows
$\sigma_{2}^{a}$ up to the first visit of $t$. Hence, we also have

$[wK^{\mathsf{p}}_{a}]\subseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A}_{a},s,\sigma_{2}^{a}))\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A}_{a},s,\sigma_{1}^{a},\sigma_{2}^{a})).$

Therefore,

$\displaystyle\mathsf{\widehat{col}}(\pi)$
$\displaystyle\sqsubseteq\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A}_{a},s,\sigma_{1}^{a},\sigma_{2}^{a}))$
$\displaystyle=\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1}^{\\#},\sigma_{2}^{\\#}))$
$\displaystyle\text{ because these strategies stay in }\mathcal{A}_{a}.$

Recalling that $\pi$ is the only play in
$\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma^{\\#}_{2})$, we are done with
proving the leftmost inequality of Equation (15).

Summing up our arguments, we have established that the couple of strategies
$(\sigma^{\\#}_{1},\sigma^{\\#}_{2})$ is indeed a Nash equilibrium in
$\mathcal{G}$ from $S_{\mathsf{cov}}$. Note that this in particular implies,
via Lemma 5, that $\sigma^{\\#}_{1}$ is an $S_{\mathsf{cov}}$-optimal
memoryless strategy in $\mathcal{G}$.∎

Memoryless Nash equilibria. We are now armed to establish the implication
sketched earlier. As motivated before, we first state the result in the
context of memoryless NE on “covered” arenas, the finite-memory case on
general arenas will follow almost trivially.

###### Theorem 5.1

Let $\sqsubseteq$ be a preference relation and $\mathcal{M}^{\mathsf{p}}_{1}$,
$\mathcal{M}^{\mathsf{p}}_{2}$, $\mathcal{M}^{\mathsf{c}}_{1}$ and
$\mathcal{M}^{\mathsf{c}}_{2}$ be four memory skeletons. Assume that
$\sqsubseteq$ is $\mathcal{M}^{\mathsf{p}}_{1}$-monotone and
$\mathcal{M}^{\mathsf{c}}_{1}$-selective, and that ${\sqsubseteq}^{-1}$ is
$\mathcal{M}^{\mathsf{p}}_{2}$-monotone and
$\mathcal{M}^{\mathsf{c}}_{2}$-selective. Then, for all arenas
$\mathcal{A}=(S_{1},S_{2},E)$, for all subsets of states
$S_{\mathsf{cov}}\subseteq S$ for which $\mathcal{M}^{\mathsf{p}}_{1}$ and
$\mathcal{M}^{\mathsf{p}}_{2}$ are prefix-covers, and
$\mathcal{M}^{\mathsf{c}}_{1}$ and $\mathcal{M}^{\mathsf{c}}_{2}$ are cyclic-
covers, there exists a memoryless Nash equilibrium
$(\sigma_{1},\sigma_{2})\in\Sigma^{\mathsf{ML}}_{1}(\mathcal{A})\times\Sigma^{\mathsf{ML}}_{2}(\mathcal{A})$
from $S_{\mathsf{cov}}$ in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$.

As always, we want to keep our results as general and compositional as
possible, hence we consider different skeletons for the two players. As argued
before, one can always take a single skeleton for the two players, as well as
for the two notions, by taking their product and using Lemma 6 and Lemma 7.

As discussed previously, this theorem in particular implies the existence of
memoryless $S_{\mathsf{cov}}$-optimal strategies for both players (via Lemma
5).

It is fairly straightforward to prove Theorem 5.1 once Lemma 8 is established:
the main idea is to invoke Lemma 8 for both players while doing the induction,
and obtain two Nash equilibria, both of which being memoryless for only one-
player. Then, to conclude, we resort to Lemma 4 which gives us the possibility
to mix these two NE into one that is now memoryless for both players.

###### Remark 6

Recall that a crucial hypothesis for Lemma 4 to hold is that our games are
antagonistic, i.e., that we consider $\sqsubseteq$ and its inverse relation
${\sqsubseteq}^{-1}$. It is quite interesting to observe that our use of Lemma
4 is the only circumstance in which this hypothesis matters (and it is indeed
of utmost importance) in all our reasoning.222To be more precise: we wrote
everything in the antagonistic setting, but Equation (4) can be written as two
inequalities in the general setting —
$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma^{\prime}_{1},\sigma_{2}))\sqsubseteq_{1}\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma_{2}))$
and
$\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma^{\prime}_{2}))\sqsubseteq_{2}\mathsf{\widehat{col}}(\mathsf{Plays}(\mathcal{A},s,\sigma_{1},\sigma_{2}))$
— and all our previous reasoning can be rewritten accordingly. In other words,
most of our arguments would hold for two different preference relations,
$\sqsubseteq_{1}$ and $\sqsubseteq_{2}$, without the hypothesis that
$\sqsubseteq_{2}$ equals $(\sqsubseteq_{1})^{-1}$. The problem would be that
we cannot mix the two equilibria in a single equilibrium with both strategies
being memoryless — while we do need it in the hypothesis of the induction step
Lemma 8.

Whether the same reasoning can be extended to (general) Nash equilibria by
adapting Lemma 8 to take into account the unavoidable blow-up of memory is a
question we leave open for future work. Note that the memory bounds would be
awful in any case: as the induction would unroll, the memory needed in the
equilibria would build up (essentially one bit of memory is added at each call
of the induction step in our easier setting, which is then discarded thanks to
Lemma 8). $\lhd$

###### Proof

Let $\sqsubseteq$ be a preference relation and $\mathcal{M}^{\mathsf{p}}_{1}$,
$\mathcal{M}^{\mathsf{p}}_{2}$, $\mathcal{M}^{\mathsf{c}}_{1}$ and
$\mathcal{M}^{\mathsf{c}}_{2}$ be four memory skeletons such that
$\sqsubseteq$ is $\mathcal{M}^{\mathsf{p}}_{1}$-monotone and
$\mathcal{M}^{\mathsf{c}}_{1}$-selective, and ${\sqsubseteq}^{-1}$ is
$\mathcal{M}^{\mathsf{p}}_{2}$-monotone and
$\mathcal{M}^{\mathsf{c}}_{2}$-selective.

We will proceed by induction on the number of choices in the arena, as
described before. The base case, $n_{\mathcal{A}}=0$, is trivial. Now let
$n\in\mathbb{N}\setminus\\{0\\}$ and assume the result holds for
$n_{\mathcal{A}}<n$. Let $\mathcal{A}=(S_{1},S_{2},E)$ be an arena such that
$n_{\mathcal{A}}=n$, and let $S_{\mathsf{cov}}\subseteq S$ be a subset of
states for which $\mathcal{M}^{\mathsf{p}}_{1}$ and
$\mathcal{M}^{\mathsf{p}}_{2}$ are prefix-covers, and
$\mathcal{M}^{\mathsf{c}}_{1}$ and $\mathcal{M}^{\mathsf{c}}_{2}$ are cyclic-
covers.

Focusing on $\mathcal{P}_{1}$ and $\sqsubseteq$, we invoke Lemma 8 (using
$\mathcal{M}^{\mathsf{p}}_{1}$ and $\mathcal{M}^{\mathsf{c}}_{1}$, and the
induction hypothesis) and obtain an NE
$(\sigma^{\spadesuit}_{1},\sigma^{\spadesuit}_{2})\in\Sigma^{\mathsf{ML}}_{1}(\mathcal{A})\times\Sigma_{2}(\mathcal{A})$
from $S_{\mathsf{cov}}$ in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$. Note that
this NE is only memoryless for $\mathcal{P}_{1}$! Symmetrically, focusing on
$\mathcal{P}_{2}$ and ${\sqsubseteq}^{-1}$, we invoke Lemma 8 (using
$\mathcal{M}^{\mathsf{p}}_{2}$ and $\mathcal{M}^{\mathsf{c}}_{2}$, and the
induction hypothesis) and obtain an NE
$(\sigma^{\clubsuit}_{1},\sigma^{\clubsuit}_{2})\in\Sigma_{1}(\mathcal{A})\times\Sigma^{\mathsf{ML}}_{2}(\mathcal{A})$
from $S_{\mathsf{cov}}$ in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$. Again,
note that this NE is only memoryless for $\mathcal{P}_{2}$.

To conclude, it suffices to use Lemma 4:
$(\sigma^{\spadesuit}_{1},\sigma^{\spadesuit}_{2})$ can be mixed with
$(\sigma^{\clubsuit}_{1},\sigma^{\clubsuit}_{2})$ into an equivalent NE
$(\sigma^{\spadesuit}_{1},\sigma^{\clubsuit}_{2})\in\Sigma^{\mathsf{ML}}_{1}(\mathcal{A})\times\Sigma^{\mathsf{ML}}_{2}(\mathcal{A})$,
which is now memoryless for both players. This concludes our induction step
and our proof.∎

Finite-memory Nash equilibria and UFM strategies. Finally, we conclude this
section by establishing our long-sought result as a corollary.

###### Corollary 2

Let $\sqsubseteq$ be a preference relation and $\mathcal{M}^{\mathsf{p}}_{1}$,
$\mathcal{M}^{\mathsf{p}}_{2}$, $\mathcal{M}^{\mathsf{c}}_{1}$ and
$\mathcal{M}^{\mathsf{c}}_{2}$ be four memory skeletons. Assume that
$\sqsubseteq$ is $\mathcal{M}^{\mathsf{p}}_{1}$-monotone and
$\mathcal{M}^{\mathsf{c}}_{1}$-selective, and that ${\sqsubseteq}^{-1}$ is
$\mathcal{M}^{\mathsf{p}}_{2}$-monotone and
$\mathcal{M}^{\mathsf{c}}_{2}$-selective. Then, for all arenas
$\mathcal{A}=(S_{1},S_{2},E)$, there exists a uniform finite-memory Nash
equilibrium
$(\sigma_{1},\sigma_{2})\in\Sigma^{\mathsf{FM}}_{1}(\mathcal{A})\times\Sigma^{\mathsf{FM}}_{2}(\mathcal{A})$
in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$, such that strategies $\sigma_{i}$
are encoded as Mealy machines
$\Gamma_{\sigma_{i}}=(\mathcal{M},\alpha_{\mathsf{nxt}}^{i})$ based on the
joint memory skeleton
$\mathcal{M}=\mathcal{M}^{\mathsf{p}}_{1}\otimes\mathcal{M}^{\mathsf{p}}_{2}\otimes\mathcal{M}^{\mathsf{c}}_{1}\otimes\mathcal{M}^{\mathsf{c}}_{2}$.

As usual in this section, we state our result for the slightly stronger notion
of Nash equilibria: it involves in particular the existence of UFM strategies
for both players. As for Theorem 5.1, we use four memory skeletons to keep the
approach compositional and player-based, and we provide strategies based on
their product memory. However, if there exists a skeleton $\mathcal{M}$ that
is already such that both $\sqsubseteq$ and ${\sqsubseteq}^{-1}$ are
$\mathcal{M}$-monotone and $\mathcal{M}$-selective, this skeleton suffices to
build both strategies (this is transparent in the following proof).

This corollary is fairly easy to obtain. We build the joint memory skeleton
$\mathcal{M}$ as defined above. By Lemma 6 and Lemma 7, we can invoke Theorem
5.1 on the product arena $\mathcal{A}\ltimes\mathcal{M}$ and obtain a
memoryless NE on it, or equivalently, a finite-memory one on the original
arena, through Lemma 3.

###### Proof

Let $\sqsubseteq$ be a preference relation and let
$\mathcal{M}^{\mathsf{p}}_{1}$, $\mathcal{M}^{\mathsf{p}}_{2}$,
$\mathcal{M}^{\mathsf{c}}_{1}$ and $\mathcal{M}^{\mathsf{c}}_{2}$ be four
memory skeletons such that $\sqsubseteq$ is
$\mathcal{M}^{\mathsf{p}}_{1}$-monotone and
$\mathcal{M}^{\mathsf{c}}_{1}$-selective, and that ${\sqsubseteq}^{-1}$ is
$\mathcal{M}^{\mathsf{p}}_{2}$-monotone and
$\mathcal{M}^{\mathsf{c}}_{2}$-selective. Let $\mathcal{A}=(S_{1},S_{2},E)$ be
an arena.

We define
$\mathcal{M}=(M,m_{\mathsf{init}},\alpha_{\mathsf{upd}})=\mathcal{M}^{\mathsf{p}}_{1}\otimes\mathcal{M}^{\mathsf{p}}_{2}\otimes\mathcal{M}^{\mathsf{c}}_{1}\otimes\mathcal{M}^{\mathsf{c}}_{2}$,
the joint memory skeleton. By Lemma 6, $\sqsubseteq$ and ${\sqsubseteq}^{-1}$
are both $\mathcal{M}$-monotone and $\mathcal{M}$-selective.

Consider the product arena
$\mathcal{A}^{\prime}=\mathcal{A}\ltimes\mathcal{M}$, as defined in Section 2.
Recall that $S^{\prime}=S\times M$. By Lemma 7, the set of states
$S_{\mathsf{cov}}^{\prime}=S\times\\{m_{\mathsf{init}}\\}\subseteq S^{\prime}$
is both prefix-covered and cyclic-covered by $\mathcal{M}$.

Putting the last two arguments together, we may invoke Theorem 5.1 on
$\mathcal{A}^{\prime}$ and obtain a memoryless Nash equilibrium
$(\sigma^{\prime}_{1},\sigma^{\prime}_{2})\in\Sigma^{\mathsf{ML}}_{1}(\mathcal{A}^{\prime})\times\Sigma^{\mathsf{ML}}_{2}(\mathcal{A}^{\prime})$
from $S_{\mathsf{cov}}^{\prime}$ in
$\mathcal{G}^{\prime}=(\mathcal{A}^{\prime},\sqsubseteq)$.

To conclude, it suffices to use Lemma 3 (stated using NE, as discussed in
Remark 4): the memoryless equilibrium
$(\sigma^{\prime}_{1},\sigma^{\prime}_{2})$ in the product game
$\mathcal{G}^{\prime}$ can be seen as a finite-memory equilibrium
$(\sigma_{1},\sigma_{2})\in\Sigma^{\mathsf{FM}}_{1}(\mathcal{A})\times\Sigma^{\mathsf{FM}}_{2}(\mathcal{A})$
in $\mathcal{G}=(\mathcal{A},\sqsubseteq)$, where strategies $\sigma_{i}$ are
encoded as Mealy machines
$\Gamma_{\sigma_{i}}=(\mathcal{M},\alpha_{\mathsf{nxt}}^{i})$.∎

##  6 Discussion

We close our paper with a discussion of the assets and limits of our approach,
its applicability with regard to the current research landscape, and the
directions we aim to follow in future work.

Technical features of our approach. As observed through Remark 2 and Remark 5,
our results are established using the weakest assumptions and granting the
strongest conclusions, whenever possible. They also preserve compositionality,
splitting the reasoning for $\mathcal{M}$-monotony and
$\mathcal{M}$-selectivity, and for the two players. As pointed out in Remark
5, this methodology yields stronger results and helps in highlighting the
precise role of each concept in the mechanism leading to the existence of UFM
strategies.

Alongside $\mathcal{M}$-monotony and $\mathcal{M}$-selectivity, we define two
other key concepts to solve the technical issues related to the induction on
product arenas: prefix-covers and cyclic-covers. These notions are crucial
tools to prove the results in Section 5.

Some advantages. The aforementioned concepts of prefix-covers and cyclic-
covers also have benefits from a practical point of view: given a preference
relation $\sqsubseteq$ and the corresponding memory skeleton $\mathcal{M}$,
they let us identify game arenas where memoryless strategies suffice whereas
finite memory (based on $\mathcal{M}$) might be necessary in general. Such
arenas are the ones covered by $\mathcal{M}$. Hence in practice, this approach
permits to obtain UML strategies for many arenas where a coarser approach
would only provide UFM ones.

Our approach yields two methods to establish that a preference relation (or
equivalently a payoff function or a winning condition) admits UFM strategies.
The first one, exhibiting appropriate memory skeletons and proving
$\mathcal{M}$-monotony and $\mathcal{M}$-selectivity, is based on Theorem 3.1
and can be used compositionally through Corollary 2. The second one follows
the lifting corollary, Corollary 1: one only has to study the one-player
subcases then invoke this result to lift the existence of UFM strategies to
the two-player case, without checking for $\mathcal{M}$-monotony and
$\mathcal{M}$-selectivity at all. Hence this second method is often painless
in practice.

Two interesting facts can be seen through Corollary 1. First, there is no
blow-up in the memory required when going from one-player games to two-player
games: the overall memory simply combines the memory skeletons of the two
players. Second, assuming that one has an algorithm to solve333I.e., decide
who has a winning strategy from a given state. one-player games — say for
$\mathcal{P}_{1}$ — for a winning condition satisfying our hypotheses, this
lifting corollary also induces a naive algorithm for the two-player case for
free: thanks to the bounds on memory, one may enumerate the strategies of the
adversary, $\mathcal{P}_{2}$ — or guess one if one aims for a non-
deterministic algorithm — and solve the corresponding $\mathcal{P}_{1}$’s
game(s) where the strategy of $\mathcal{P}_{2}$ is fixed. Note that while such
a simple algorithm might not be optimal, it does correspond to the approach
giving the best complexity class known for the renowned family of games in
$\mathsf{NP}\cap\mathsf{coNP}$, such as, e.g., parity or mean-payoff games
(e.g., [28]).

Applicability. Let us give a quick tour of some classical (combinations of)
objectives — expressed through winning conditions, payoffs or preference
relations — and assess whether our approach permits to establish the existence
of UFM strategies in the corresponding games.

Note that when considering multiple (quantitative) objectives, optimal
strategies usually do not exist, and one has to settle for Pareto-optimal ones
(e.g., [17]). However, in many cases, the (decision) problem under study is as
follows: given a threshold (vector), define the winning condition as all the
plays achieving at least this threshold, and check for a winning strategy.
Hence multi-objective quantitative games are often de facto reduced to
qualitative win-lose games for this so-called threshold problem. Observe that,
given a multi-objective setting, if UFM strategies exist for all threshold
problems, then finite-memory strategies suffice to realize the Pareto front
(as each point of this front can be considered as a threshold). Therefore, our
approach also enables reasoning about the existence of finite-memory Pareto-
optimal strategies in multi-objective games.

We start our overview with some game settings that fall under the scope of our
approach. Obviously, all memoryless-determined objectives are among them,
since we generalize Gimbert and Zielonka’s work [25]: this includes, e.g.,
mean-payoff [18], parity [19, 39], energy [11] or average-energy games [5]. As
established in Section 1, our results encompass all cases where arena-
independent memory suffices. Hence they permit to rediscover the existence of
UFM strategies for games such as, e.g., generalized reachability [20],
generalized parity [15], window parity games [9], or lower- and upper-bounded
(multi-dimension) energy games [3, 5, 4]. Our approach can also be useful to
extend these known results to more general combinations, either via
appropriate memory skeletons or through the lifting corollary (see an
application in Section 3.3).

There are many games that do not fit our approach for good reasons, as they do
not admit UFM strategies in general: e.g., multi-dimension mean-payoff [38],
mean-payoff parity [14], or energy mean-payoff games [10]. More interesting
are games for which UFM strategies exist, but the memory is arena-dependent.
These notably include games with multi-dimension lower-bounded energy
objectives and no upper bound [16, 29], or window mean-payoff games [13]. In
such games, the players usually have to keep track of information such as,
e.g., the sum of weights along an acyclic path, which is bounded for any given
arena, but by a value that grows when the arena grows. Hence the need for
memory that grows with the arena parameters. Our results cannot be applied
directly to such cases in order to obtain the existence of UFM strategies for
all games. An adaptation of our approach could potentially be used for
subclasses of arenas where the parameters are bounded (in order to regain a
skeleton working on all arenas of the class).

Comparison with related work. We already discussed extensively the most
important related articles [24, 25, 30, 1, 31, 37] in Section 1, alongside a
technical comparison between our work and Gimbert and Zielonka’s seminal
result [25]. Here, we simply want to highlight interesting directions of
research inspired by some of these papers. First, Aminof and Rubin provide a
simpler (but incomplete) approach to memoryless determinacy through the prism
of first-cycle games in [1]: a similar take on finite-memory determinacy could
be appealing — it could provide sufficient conditions easier to test than
$\mathcal{M}$-monotony and $\mathcal{M}$-selectivity. Second, Kopczynski
establishes sufficient (and relaxed) conditions to ensure the existence of UML
strategies for one player in [30]: it would be interesting to study the
corresponding problem in the finite-memory case. Indeed, in many games where
infinite memory is needed, it is only the case for one of the players (e.g.,
[38, 14, 10]) and conditions à la Kopczynski could thus prove useful. Finally,
recall that Le Roux et al. give a rather tight characterization of
combinations of objectives preserving the sufficiency of finite-memory
strategies in [37]. Their techniques, as well as the scope of their results,
is somewhat orthogonal to ours. Whether both approaches can be intertwined to
obtain results on more general settings remains an open question.

Limits and future work. To close this paper, we recall two limits of our
approach, and the corresponding open problems.

First, as explained throughout the paper, our results cover all cases where
arena-independent memory suffices, and are limited to these cases. We have
argued that the approach cannot be fully lifted to the general case, for good
reasons, as the lifting corollary breaks in some situations (Section 1).
Still, we have hope to generalize our approach to some extent to the arena-
dependent case, through some function associating memory skeletons to arenas,
as discussed in Section 1. Obtaining a lifting corollary — under well-chosen
conditions — in the arena-dependent case would be of tremendous help in
practice: see for example [5, 4, 10]. Hence this is clearly the next step in
our quest.

Second, as explained in Remark 1 and Remark 6, most of our arguments carry
over to the case of general Nash equilibria. That is, when considering not
necessarily antagonistic games where the two players use different, not
necessarily inverse, preference relations. Whether our approach can be adapted
in this case, at the price of an unavoidable blow-up of memory, is an open
question worth considering. In particular, we want to study the links between
our results (including the lifting from one-player to two-player games) and
recent results lifting finite-memory determinacy from two-player to multi-
player games [36].

## References

  * [1] Benjamin Aminof and Sasha Rubin.  First-cycle games.  Inf. Comput., 254:195–216, 2017.
  * [2] Roderick Bloem, Krishnendu Chatterjee, and Barbara Jobstmann.  Graph games and reactive synthesis.  In Edmund M. Clarke, Thomas A. Henzinger, Helmut Veith, and Roderick Bloem, editors, Handbook of Model Checking, pages 921–962. Springer, 2018\.
  * [3] Patricia Bouyer, Ulrich Fahrenberg, Kim Guldstrand Larsen, Nicolas Markey, and Jirí Srba.  Infinite runs in weighted timed automata with energy constraints.  In Franck Cassez and Claude Jard, editors, Formal Modeling and Analysis of Timed Systems, 6th International Conference, FORMATS 2008, Saint Malo, France, September 15-17, 2008. Proceedings, volume 5215 of Lecture Notes in Computer Science, pages 33–47. Springer, 2008.
  * [4] Patricia Bouyer, Piotr Hofman, Nicolas Markey, Mickael Randour, and Martin Zimmermann.  Bounding average-energy games.  In Javier Esparza and Andrzej S. Murawski, editors, Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22-29, 2017, Proceedings, volume 10203 of Lecture Notes in Computer Science, pages 179–195, 2017.
  * [5] Patricia Bouyer, Nicolas Markey, Mickael Randour, Kim G. Larsen, and Simon Laursen.  Average-energy games.  Acta Inf., 55(2):91–127, 2018.
  * [6] Romain Brenguier, Lorenzo Clemente, Paul Hunter, Guillermo A. Pérez, Mickael Randour, Jean-François Raskin, Ocan Sankur, and Mathieu Sassolas.  Non-zero sum games for reactive synthesis.  In Adrian-Horia Dediu, Jan Janousek, Carlos Martín-Vide, and Bianca Truthe, editors, Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings, volume 9618 of Lecture Notes in Computer Science, pages 3–23. Springer, 2016.
  * [7] Thomas Brihaye, Florent Delgrange, Youssouf Oualhadj, and Mickael Randour.  Life is random, time is not: Markov decision processes with window objectives.  In Fokkink and van Glabbeek [22], pages 8:1–8:18.
  * [8] Véronique Bruyère, Emmanuel Filiot, Mickael Randour, and Jean-François Raskin.  Meet your expectations with guarantees: Beyond worst-case synthesis in quantitative games.  Inf. Comput., 254:259–295, 2017.
  * [9] Véronique Bruyère, Quentin Hautem, and Mickael Randour.  Window parity games: an alternative approach toward parity games with time bounds.  In Domenico Cantone and Giorgio Delzanno, editors, Proceedings of the Seventh International Symposium on Games, Automata, Logics and Formal Verification, GandALF 2016, Catania, Italy, 14-16 September 2016, volume 226 of EPTCS, pages 135–148, 2016.
  * [10] Véronique Bruyère, Quentin Hautem, Mickael Randour, and Jean-François Raskin.  Energy mean-payoff games.  In Fokkink and van Glabbeek [22], pages 21:1–21:17.
  * [11] Arindam Chakrabarti, Luca de Alfaro, Thomas A. Henzinger, and Mariëlle Stoelinga.  Resource interfaces.  In Rajeev Alur and Insup Lee, editors, EMSOFT, volume 2855 of Lecture Notes in Computer Science, pages 117–133. Springer, 2003.
  * [12] Krishnendu Chatterjee and Laurent Doyen.  Energy parity games.  Theor. Comput. Sci., 458:49–60, 2012.
  * [13] Krishnendu Chatterjee, Laurent Doyen, Mickael Randour, and Jean-François Raskin.  Looking at mean-payoff and total-payoff through windows.  Inf. Comput., 242:25–52, 2015.
  * [14] Krishnendu Chatterjee, Thomas A. Henzinger, and Marcin Jurdzinski.  Mean-payoff parity games.  In 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26-29 June 2005, Chicago, IL, USA, Proceedings, pages 178–187. IEEE Computer Society, 2005.
  * [15] Krishnendu Chatterjee, Thomas A. Henzinger, and Nir Piterman.  Generalized parity games.  In Helmut Seidl, editor, Foundations of Software Science and Computational Structures, 10th International Conference, FOSSACS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007, Braga, Portugal, March 24-April 1, 2007, Proceedings, volume 4423 of Lecture Notes in Computer Science, pages 153–167. Springer, 2007\.
  * [16] Krishnendu Chatterjee, Mickael Randour, and Jean-François Raskin.  Strategy synthesis for multi-dimensional quantitative objectives.  Acta Inf., 51(3-4):129–163, 2014.
  * [17] Florent Delgrange, Joost-Pieter Katoen, Tim Quatmann, and Mickael Randour.  Simple strategies in multi-objective MDPs.  In 26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2020, Lecture Notes in Computer Science. Springer, 2020.  To appear.
  * [18] Andrzej Ehrenfeucht and Jan Mycielski.  Positional strategies for mean payoff games.  Int. Journal of Game Theory, 8(2):109–113, 1979.
  * [19] E. Allen Emerson and Charanjit S. Jutla.  The complexity of tree automata and logics of programs.  In FOCS, pages 328–337. IEEE Computer Society, 1988.
  * [20] Nathanaël Fijalkow and Florian Horn.  The surprizing complexity of reachability games.  CoRR, abs/1010.2420, 2010.
  * [21] Nathanaël Fijalkow, Florian Horn, Denis Kuperberg, and Michal Skrzypczak.  Trading bounds for memory in games with counters.  In Halldórsson et al. [27], pages 197–208.
  * [22] Wan Fokkink and Rob van Glabbeek, editors.  30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Netherlands, volume 140 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [23] Hugo Gimbert.  Pure stationary optimal strategies in Markov decision processes.  In Wolfgang Thomas and Pascal Weil, editors, STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, volume 4393 of Lecture Notes in Computer Science, pages 200–211. Springer, 2007.
  * [24] Hugo Gimbert and Wieslaw Zielonka.  When can you play positionally?  In Jirí Fiala, Václav Koubek, and Jan Kratochvíl, editors, Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings, volume 3153 of Lecture Notes in Computer Science, pages 686–697. Springer, 2004.
  * [25] Hugo Gimbert and Wieslaw Zielonka.  Games where you can play optimally without any memory.  In Martín Abadi and Luca de Alfaro, editors, CONCUR 2005 - Concurrency Theory, 16th International Conference, CONCUR 2005, San Francisco, CA, USA, August 23-26, 2005, Proceedings, volume 3653 of Lecture Notes in Computer Science, pages 428–442. Springer, 2005.
  * [26] Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors.  Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science. Springer, 2002.
  * [27] Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors.  Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 of Lecture Notes in Computer Science. Springer, 2015\.
  * [28] Marcin Jurdzinski.  Deciding the winner in parity games is in UP $\cap$ co-UP.  Inf. Process. Lett., 68(3):119–124, 1998.
  * [29] Marcin Jurdzinski, Ranko Lazic, and Sylvain Schmitz.  Fixed-dimensional energy games are in pseudo-polynomial time.  In Halldórsson et al. [27], pages 260–272.
  * [30] Eryk Kopczynski.  Half-positional determinacy of infinite games.  In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, volume 4052 of Lecture Notes in Computer Science, pages 336–347. Springer, 2006.
  * [31] Donald A. Martin.  Borel determinacy.  Annals of Mathematics, 102(2):363–371, 1975.
  * [32] Martin J. Osborne and Ariel Rubinstein.  A course in game theory.  The MIT Press, Cambridge, USA, 1994.
  * [33] Mickael Randour.  Automated synthesis of reliable and efficient systems through game theory: A case study.  In Proc. of ECCS 2012, Springer Proceedings in Complexity XVII, pages 731–738. Springer, 2013.
  * [34] Stéphane Le Roux.  Infinite sequential Nash equilibrium.  Logical Methods in Computer Science, 9(2), 2013.
  * [35] Stéphane Le Roux.  Concurrent games and semi-random determinacy.  In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 40:1–40:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.
  * [36] Stéphane Le Roux and Arno Pauly.  Extending finite-memory determinacy to multi-player games.  Inf. Comput., 261(Part):676–694, 2018.
  * [37] Stéphane Le Roux, Arno Pauly, and Mickael Randour.  Extending finite-memory determinacy by Boolean combination of winning conditions.  In Sumit Ganguly and Paritosh K. Pandya, editors, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India, volume 122 of LIPIcs, pages 38:1–38:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018.
  * [38] Yaron Velner, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Alexander Moshe Rabinovich, and Jean-François Raskin.  The complexity of multi-mean-payoff and multi-energy games.  Inf. Comput., 241:177–196, 2015.
  * [39] Wieslaw Zielonka.  Infinite games on finitely coloured graphs with applications to automata on infinite trees.  Theor. Comput. Sci., 200(1-2):135–183, 1998.

##  Appendix 0.A Counterexample to a general lifting corollary

We discuss in full details the counterexample presented in Section 1. Let
$C=\mathbb{Z}$. We consider the following two winning conditions:

$\displaystyle W_{1}$ $\displaystyle=\\{c_{1}c_{2}\ldots\in
C^{\omega}\mid\liminf_{n\rightarrow\infty}\sum_{i=1}^{n}c_{i}=+\infty\\},$
$\displaystyle W_{2}$ $\displaystyle=\\{c_{1}c_{2}\ldots\in
C^{\omega}\mid\sum_{i=1}^{n}c_{i}=0\text{ for infinitely many $n$'s}\\}.$

If the play obtained by playing a game is $\pi$, $\mathcal{P}_{1}$ wins if and
only if $\mathsf{\widehat{col}}(\pi)$ lies in $W=W_{1}\cup W_{2}$, and
$\mathcal{P}_{2}$ wins if and only if $\mathsf{\widehat{col}}(\pi)$ lies in
$\overline{W}=C^{\omega}\setminus W=\overline{W_{1}}\cap\overline{W_{2}}$
(which corresponds to the description given in Section 1). We prove that
$\mathcal{P}_{1}$ and $\mathcal{P}_{2}$ have finite-memory optimal strategies
in their respective one-player games.

Let us fix some terminology beforehand: we say that a cycle in an arena is a
zero cycle if the sum of its weights is zero, a positive cycle if this sum is
strictly positive, and a negative cycle if this sum is strictly negative.

We first consider $\mathcal{P}_{1}$’s one-player games. In a one-player arena,
$\mathcal{P}_{1}$ can create a play $\pi$ such that
$\mathsf{\widehat{col}}(\pi)\in W_{1}$ if and only if there is a reachable
positive cycle. In this case, $\mathcal{P}_{1}$ can win with a memoryless
strategy (simply reaching the cycle and then looping in it). If that is not
possible, in order to win, $\mathcal{P}_{1}$ has to induce a play $\pi$ such
that $\mathsf{\widehat{col}}(\pi)\in W_{2}$. We show that if possible, this
can be done using finite memory. Let us assume that there exists a play
$\pi=e_{1}e_{2}\ldots$ such that
$\mathsf{\widehat{col}}(\pi)=c_{1}c_{2}\ldots\in W_{2}$. Let us consider two
indices $k,l\in\mathbb{N}$ such that $k<l$, $e_{k}=e_{l}$,
$\sum_{i=1}^{k}c_{i}=0$, and $\sum_{i=1}^{l}c_{i}=0$. Such two indices
necessarily exist, as there are finitely many edges in the arena, but
infinitely many indices for which the running sum of weights is $0$. Notice in
particular that $\sum_{i=k+1}^{l}c_{i}=0$. Now, consider the play

$\pi^{\prime}=e_{1}\ldots e_{k}e_{k+1}\ldots e_{l}e_{k+1}\ldots
e_{l}e_{k+1}\ldots,$

with the sequence of edges $e_{k+1}\ldots e_{l}$ repeating ad infinitum
($\pi^{\prime}$ is a “lasso”). This is a valid play since $e_{k}=e_{l}$.
Moreover, we have that $\mathsf{\widehat{col}}(\pi^{\prime})\in W_{2}$ as
after repeating $m$ times the sequence $e_{k+1}\ldots e_{l}$, the sum of the
weights equals $\sum_{i=1}^{k}c_{i}+m\cdot\sum_{i=k+1}^{l}c_{i}=0+m\cdot 0=0$.
The play $\pi^{\prime}$ can be implemented with finite memory, as it consists
of a finite prefix and a repeated finite sequence, which corresponds to a zero
cycle.

We now turn our attention to $\mathcal{P}_{2}$’s one-player games;
$\mathcal{P}_{2}$ wins a play $\pi$ such that
$\mathsf{\widehat{col}}(\pi)=c_{1}c_{2}\ldots\in C^{\omega}$ if and only if

$\liminf_{n\rightarrow\infty}\sum_{i=1}^{n}c_{i}<+\infty\land\sum_{i=1}^{n}c_{i}=0\text{
for at most finitely many $n$'s}.$

In a one-player arena, if there is a reachable negative cycle,
$\mathcal{P}_{2}$ can ensure to win by pumping it forever, and can therefore
win with a memoryless strategy. We now consider an arena that has no reachable
negative cycle. As we did for $\mathcal{P}_{1}$, we show that if
$\mathcal{P}_{2}$ can win a game in such an arena, then he can do so using
finite memory. If $\mathcal{P}_{2}$ can win, let $\pi=e_{1}e_{2}\ldots$ be a
winning play for $\mathcal{P}_{2}$, i.e.,
$\mathsf{\widehat{col}}(\pi)=c_{1}c_{2}\ldots\in\overline{W_{1}}\cap\overline{W_{2}}$.
Let $s$ be a state visited infinitely often when $\pi$ is played, and
$m\in\mathbb{N}$ be the first index such that $\mathsf{out}(e_{m})=s$. We can
decompose $\pi$ into a finite prefix $e_{1}\ldots e_{m}$ followed by an
infinite sequence of cycles, all starting in $s$. Since there is no negative
cycle, we cannot have that infinitely many of these cycles are positive, as
this would imply that $\mathsf{\widehat{col}}(\pi)\in W_{1}$. Thus, infinitely
many zero cycles are taken from $s$. As
$\mathsf{\widehat{col}}(\pi)\in\overline{W_{2}}$, there exists such a cycle
$e_{k}\ldots e_{l}$ (that is, $\mathsf{in}(e_{k})=\mathsf{out}(e_{l})=s$ and
$\sum_{i=k}^{l}c_{i}=0$) such that for all $k\leq n\leq l$, it holds that
$\sum_{i=1}^{n}c_{i}\neq 0$. This also implies that $\sum_{i=1}^{k-1}c_{i}\neq
0$, i.e., the history up to this cycle has a non-zero sum. Now, let us
consider the play

$\pi^{\prime}=e_{1}\ldots e_{k-1}e_{k}\ldots e_{l}e_{k}\ldots
e_{l}e_{k}\ldots,$

with the sequence of edges $e_{k}\ldots e_{l}$ repeating ad infinitum
($\pi^{\prime}$ is a “lasso”). This is a valid play as
$\mathsf{in}(e_{k})=\mathsf{out}(e_{l})$. As $\sum_{i=k}^{l}c_{i}=0$, we have
that $\mathsf{\widehat{col}}(\pi^{\prime})\in\overline{W_{1}}$. Moreover,
every time the cycle starts again, the running sum of weights is equal to the
same value: $\sum_{i=1}^{k-1}c_{i}\neq 0$. Therefore, as the running sum of
weights does not reach zero the first time the cycle is taken, and it also
never reaches zero along the cycle, it can never reach zero after index $k-1$.
Hence, $\mathsf{\widehat{col}}(\pi^{\prime})$ is not in $W_{2}$ either, and
$\pi^{\prime}$ is winning for $\mathcal{P}_{2}$. For the same reason as for
$\mathcal{P}_{1}$, play $\pi^{\prime}$ only requires finite memory to be
implemented.

As argued in Section 1, the two-player game from Figure 1 illustrates that
$\mathcal{P}_{1}$ might need infinite memory to play optimally in the two-
player case. This proves that Gimbert and Zielonka’s approach cannot work in
full generality in the finite-memory case, as we cannot obtain the existence
of finite-memory optimal strategies in all two-player games from the existence
of finite-memory optimal strategies in all one-player games.


# Coupled Hubbard ladders at weak coupling: Pairing and spin excitations

Thomas A. Maier  Computational Sciences and Engineering Division, Oak Ridge
National Laboratory, Oak Ridge, Tennessee 37831-6164, USA  Elbio Dagotto
Department of Physics and Astronomy, The University of Tennessee, Knoxville,
Tennessee 37966, USA  Materials Science and Technology Division, Oak Ridge
National Laboratory, Oak Ridge, Tennessee 37831, USA

###### Abstract

The Hubbard model provides a simple framework in which one can study how
certain aspects of the electronic structure of strongly interacting systems
can be tuned to optimize the superconducting pairing correlations and how
these changes affect the mechanisms giving rise to them. Here we use a weak-
coupling random phase approximation to study a two-dimensional Hubbard model
with a unidirectional modulation of the hopping amplitudes as the system
evolves from the uniform square lattice to an array of weakly coupled two-leg
ladders. We find that the pairing correlations retain their dominant
$d_{x^{2}-y^{2}}$-wave like structure and that they are significantly enhanced
for a slightly modulated lattice. This enhancement is traced backed to an
increase in the strength of the spin-fluctuation pairing interacting due to
favorable Fermi surface nesting in the modulated system. We then use a random-
phase approximation BCS framework to examine the evolution of the neutron
resonance in the superconducting state. We find that it changes only weakly
for moderate modulations, but breaks up into two distinct resonances at
incommensurate wave-vectors in the limit of weakly coupled ladders.

##  I Introduction

The Hubbard model [1] provides a simple framework to study how a purely
repulsive interaction between fermions can give rise to a superconducting
instability. It has been extensively studied in the context of the cuprates,
for which it was argued to provide an appropriate low-energy effective
description of the electronic degrees of freedom [2, 3]. Advanced numerical
approaches have been extensively used to study this model on square lattices
[4, 5, 6, 7]. In this case, the ground state of the doped model is still under
debate [8, 9, 10, 11, 12, 13] and likely depends on details in the model
parameters, such as the plaquette diagonal hopping $t^{\prime}$ strength and
sign. Nevertheless, several studies have found evidence that it exhibits
properties remarkably similar to what is observed in the cuprates, including
antiferromagnetism, pseudogap and superconducting behavior, as well as striped
spin and charge density waves [5, 6, 7]. Related to these developments in
square lattices, in the 90’s it was predicted that two-leg ladders would have
a spin gap, exponentially decaying spin correlations, and they would
superconduct upon doping [14, 15, 16]. These predictions were experimentally
confirmed [17, 18, 19]. For this geometry, essentially exact calculations can
be carried out, and the doped model is known to support a Luther-Emery liquid
phase with power-law superconducting correlations [20, 21, 22].

Unbiased and controlled numerical calculations are necessary to accurately and
reliably predict the properties of the Hubbard model in the non-perturbative
regime relevant for the cuprates, where the Coulomb repulsion between the
electrons is of the same magnitude as their kinetic energy. On the other hand,
weak-coupling random-phase approximation (RPA) based approaches, while
perturbative, provide a level of simplicity and transparency, and therefore
insight, that numerical methods cannot offer. Recent studies have shown that
RPA-based weak coupling approaches describe certain behavior in Hubbard models
remarkably well. For example, systematic studies of the leading pairing
instabilities in a 2D square lattice Hubbard model with increasing Coulomb
repulsion $U$ found that weak coupling RPA predictions agreed exceptionally
well [23] with those of non-perturbative quantum Monte Carlo dynamic cluster
approximation (DCA) [24] results. Similarly, for a Hubbard model in a two-leg
ladder geometry, RPA calculations within a fluctuation exchange approximation
(FLEX) were shown to capture the main features of density matrix
renormalization group (DMRG) results for the magnetic and charge dynamical
response [25].

Here, we use RPA calculations to study the Hubbard model for geometries in
between these two limits, i.e. for an array of coupled two-leg ladders. In
particular, we are interested on how the superconducting pairing correlations
change when the system evolves from the uniform square lattice limit to the
two-leg ladder geometry, as the hopping amplitude between the ladders is
reduced (see Fig. 1). A very similar system with a unidirectional modulation
of the hopping amplitudes was recently investigated with the density matrix
renormalization group in the context of the question of whether striped charge
density wave order can enhance the superconducting correlations [26]. This
study found an order of magnitude enhancement of the superconducting
correlations even for modest modulations for reasons that remain investigated
in more detail. For the opposite limit of an isolated two-leg ladder, a
similar enhancement was found in recent RPA-based FLEX calculations when the
rung-to-leg ratio of the nearest neighbor hopping increases [27].
Understanding how superconductivity can be optimized by tuning certain aspects
of the electronic structure is not only useful for the search for new
materials with improved properties, but can also provide insight into the
nature of the mechanisms responsible for the pairing correlations. Here, we
find an enhancement of the superconducting pairing strength for a slightly
modulated hopping amplitude, and show that within RPA, this enhancement arises
from an increase in the strength of the spin-fluctuation pairing interaction.

We then use an RPA/BCS framework to study how the superconducting gap affects
the spin-fluctuation spectrum under variation of the inter-ladder coupling.
For the uniform square lattice, this formalism is known to provide a framework
in which one can understand the neutron resonance observed in the
superconducting state of the cuprates [28, 5]. Here, we examine how this
neutron resonance and its dispersion evolve as the inter-ladder coupling
decreases towards the isolated two-leg ladder limit. We find that the
resonance becomes stronger for the slightly modulated case with the largest
pairing correlations. For weakly coupled ladders, the resonance is still
present, albeit at a different wavevector.

##  II Model and Method

We consider a two-dimensional Hubbard model on a square lattice

${\cal
H}=\sum_{ij,\sigma}t_{ij}c^{\dagger}_{i\sigma}c^{\phantom{\dagger}}_{j\sigma}+U\sum_{i}n_{i\uparrow}n_{i\downarrow}\,,$
(1)

with modulated hopping amplitudes along the $x$-direction. Here,
$c^{\dagger}_{i\sigma}$ ($c^{\phantom{\dagger}}_{i\sigma}$) creates
(annihilates) an electron on site $i$ with spin $\sigma$,
$n_{i\sigma}=c^{\dagger}_{i\sigma}c^{\phantom{\dagger}}_{i\sigma}$ is the
electron number operator and $U$ is the on-site Coulomb repulsion. As
illustrated in Fig. 1, the system can be considered as an array of coupled
two-leg Hubbard ladders that run along the $y$-direction. We set the hopping
amplitudes within the ladders to $t_{ij}=-t$ for $i,j$ nearest neighbors
(along the rungs) and to $t_{ij}=-t^{\prime}$ when $i$ and $j$ are next-
nearest neighbors along the plaquette diagonals. The hopping between the
ladders is set to $t_{l}=rt$ for nearest-neighbor sites and
$t^{\prime}_{l}=rt^{\prime}$ for next-nearest neighbor sites. Here, $r$ is a
tunable parameter that controls the relative amplitudes between intra- and
inter-ladder hoppings. The Hamiltonian in Eq. (1) reduces to the usual uniform
2D Hubbard model for $r=1$. For $r\lesssim 1$, it describes a Hubbard model
with modulated hopping amplitudes along the $x$-direction and uniform
amplitudes along the $y$-direction. In the opposite limit of very small $r\ll
1$, it describes an array of weakly coupled Hubbard ladders. In the following,
we use $t=1$ as energy unit, and set $t^{\prime}=-0.25t$. Throughout the
manuscript, the electron density is fixed to $\langle n\rangle=0.85$.

We use a random-phase approximation framework to study this model. In the non-
uniform case, $r\neq 1$, there are two sites in the unit cell (left and right
legs of the ladders), and the model can be considered a two-orbital model,
where the two orbitals correspond to the two sites. In the multi-orbital RPA
framework [29, 30], the pairing vertex
$\Gamma_{\ell_{1}\ell_{2}\ell_{3}\ell_{4}}(k,k^{\prime})$ for scattering a
singlet pair $(k\uparrow\ell_{1},-k\downarrow\ell_{4})$ in orbitals (leg 1 or
2) $\ell_{1}$ and $\ell_{4}$ to a pair
$(k^{\prime}\uparrow\ell_{2},-k^{\prime}\downarrow\ell_{3})$ in orbitals
$\ell_{2}$ and $\ell_{3}$ is given by

$\displaystyle\Gamma_{\ell_{1}\ell_{2}\ell_{3}\ell_{4}}(k,k^{\prime})$
$\displaystyle=$ $\displaystyle\biggl{[}\frac{3}{2}\ {\cal U}\chi_{s}^{\rm
RPA}(k-k^{\prime},0){\cal U}$ $\displaystyle-$ $\displaystyle\frac{1}{2}\
{\cal U}\chi_{c}^{\rm RPA}(k-k^{\prime},0){\cal U}$ $\displaystyle+$
$\displaystyle{\cal U})\biggr{]}_{\ell_{1}\ell_{2}\ell_{3}\ell_{4}}.$

Here ${\cal U}$ is a $4\times 4$ matrix with elements ${\cal
U}_{\ell_{1}\ell_{2}\ell_{3}\ell_{4}}=U\delta_{\ell_{1}\ell_{2}}\delta_{\ell_{3}\ell_{4}}\delta_{\ell_{1}\ell_{4}}$.
The RPA spin $\chi^{\rm RPA}_{s}$ and charge $\chi^{\rm RPA}_{c}$
susceptibilities are

$\displaystyle\chi^{\rm RPA}_{s}(q,i\omega_{m})$ $\displaystyle=$
$\displaystyle\chi^{0}(q,i\omega_{m})[1-{\cal U}\chi^{0}(q,i\omega_{m})]^{-1}$
(3) $\displaystyle\chi^{\rm RPA}_{c}(q,i\omega_{m})$ $\displaystyle=$
$\displaystyle\chi^{0}(q,i\omega_{m})[1+{\cal
U}\chi^{0}(q,i\omega_{m})]^{-1},$

where $\omega_{m}=2m\pi T$ is a bosonic Matsubara frequency and the matrix
elements of the bare susceptibility $\chi^{0}(q)$ are given by

$\displaystyle\chi^{0}_{\ell_{1}\ell_{2}\ell_{3}\ell_{4}}(q,i\omega_{m})$
$\displaystyle=-\frac{T}{N}\sum_{k,\omega_{n}}G^{0}_{\ell_{3}\ell_{1}}(k+q,i\omega_{n}+i\omega_{m})$
$\displaystyle\,\,\,\;\;\times\,G^{0}_{\ell_{2}\ell_{4}}(k,i\omega_{n}),$

with $G^{0}_{\ell\ell^{\prime}}(k,i\omega_{n})$ the bare Green’s function

$G^{0}_{\ell\ell^{\prime}}(k,i\omega_{n})=\sum_{\mu}\frac{a^{\ell}_{\mu}(k)a^{\ell^{\prime}*}_{\mu}(k)}{i\omega_{n}-\xi_{\mu}(k)}\,$
(5)

and $\omega_{n}=(2n+1)\pi T$ a fermionic Matsubara frequency. The band
energies ($\mu=\pm$) are

$\displaystyle\xi_{\pm}(k)=-2t\cos k_{y}\mp\zeta(k),$ (6)

for the bonding (+) and anti-bonding (-) bands with

$\displaystyle\zeta(k)$ $\displaystyle=$
$\displaystyle\biggr{[}t^{2}+t_{l}^{2}+2tt_{l}\cos 2k_{x}$ $\displaystyle+$
$\displaystyle 4\cos
k_{y}[tt^{\prime}+t_{l}t^{\prime}_{l}+(tt^{\prime}_{l}+t^{\prime}t_{l})]\cos
2k_{x}$ $\displaystyle+$ $\displaystyle
4\cos^{2}k_{y}({t^{\prime}}^{2}+{t^{\prime}_{l}}^{2}+2t^{\prime}t^{\prime}_{l}\cos
2k_{x})\biggr{]}^{1/2}\,.$

The orbital matrix elements $a_{\pm}^{\ell}$ are given by

$\displaystyle a_{+}^{1}(k)$ $\displaystyle=$ $\displaystyle
a_{-}^{1}(k)=\frac{\zeta(k)}{\sqrt{\zeta^{2}(k)+|\epsilon_{12}(k)|^{2}}}$ (8)
$\displaystyle a_{+}^{2}(k)$ $\displaystyle=$ $\displaystyle-
a_{-}^{2}(k)=\frac{\epsilon^{*}_{12}(k)}{\sqrt{\zeta^{2}(k)+|\epsilon_{12}(k)|^{2}}}\,,$

with

$\epsilon_{12}(k)=-te^{ik_{x}}-t_{l}e^{-ik_{x}}-2\cos
k_{y}(t^{\prime}e^{ik_{x}}+t^{\prime}_{l}e^{-ik_{x}})\,.$ (9)

Carrying out the usual analytic continuation to the real frequency axis, the
dynamic spin susceptibility is given by

$\chi^{\rm RPA}_{s}(q,\omega)=\sum_{\ell_{1},\ell_{2}}\chi^{\rm
RPA}_{s,\ell_{1}\ell_{1}\ell_{2}\ell_{2}}(q,i\omega_{m}\rightarrow\omega+i\delta)\,.$
(10)

In terms of the scattering vertices, the pairing strength is given by the
leading eigenvalue $\lambda_{\alpha}$ of

$-\sum_{j}\oint\frac{dk^{\prime}_{\parallel}}{2\pi
v_{F_{j}}(k^{\prime}_{\parallel})}\Gamma_{ij}(k,k^{\prime})g^{\alpha}_{j}(k^{\prime})=\lambda_{\alpha}g^{\alpha}_{i}(k)$
(11)

with

$\displaystyle\Gamma_{ij}(k,k^{\prime})$ $\displaystyle=$
$\displaystyle\sum_{\ell_{1}\ell_{2}\ell_{3}\ell_{4}}a^{\ell_{1}}_{\nu_{i}}(k)a^{\ell_{4}}_{\nu_{i}}(-k)\Gamma_{\ell_{1}\ell_{2}\ell_{3}\ell_{4}}(k,k^{\prime})$
$\displaystyle\times$ $\displaystyle
a^{\ell_{2}*}_{\nu_{j}}(k^{\prime})a^{\ell_{3}*}_{\nu_{j}}(-k^{\prime}).$

Here $j$ sums over the Fermi surfaces, $v_{F_{j}}(k^{\prime}_{\parallel})$ is
the Fermi velocity $|\nabla_{k}\xi_{\nu_{j}}(k)|$ and the integral runs over
the Fermi surface. We generally find that for all values of $0<r<1$, the
leading eigenvalue $\lambda_{d}(k)$ has mostly $d_{x^{2}-y^{2}}$ character.
Note that for $r<1$, the C4 rotational symmetry of the square lattice is
broken, and mixing with an $s$-wave component is expected.

Figure 1: Illustration of the Hubbard model on a square lattice with modulated
hopping amplitudes. Here we consider nearest-neighbor hopping within the two-
leg ladders ($t$) that run along the $y$-direction and between the ladders
($t_{l}=rt$), as well as next nearest neighbor hopping within ($t^{\prime}$)
and between the ladders ($t^{\prime}_{l}=rt^{\prime}$). The parameter $r$
specifies the ratio between intra- and inter-ladder hopping amplitudes.

Before moving into our main results, what value of $r$ is realistic in our
definition of hoppings via expressions such as $t_{l}=rt$? From inelastic
neutron scattering (INS) experiments, estimations of how robust the ladder
couplings are can be made. For example, INS studies of large single crystals
of La4Sr10Cu24O41 [31], containing copper two-leg ladders in its atomic
structure, provided approximate values for the Heisenberg superexchange along
legs $J_{leg}=186$ meV, rungs $J_{rung}=124$ meV, and in between ladders
$J^{\prime}=36$ meV. For the latter the calculation was done within RPA, see
footnote 19 in Ref. [31]. This value is considered to be more uncertain than
the rest according to Ref. [31]). The theory was done using a continuous
unitary transformation. Another INS study [32], this time for La6Ca8Cu24O41,
reported that for their single crystals the values were $J_{leg}=J_{rung}=110$
meV, using for the theory component exact diagonalization of small clusters.
No results for the interladder coupling were given. Similar numbers were
obtained via optical conductivity experiments [33] as well. The common factor
of all these studies is that (a) the rung and ladder superexchanges are
similar even among different materials and when using different techniques,
(b) the cyclic four-spin interaction within a plaquette that appears in a
higher order expansion around the atomic limit is small but not negligible (in
our case we employ directly the Hubbard model and this plaquette-related
coupling is already taken into account), and (c) the largest uncertainty is in
the coupling between ladders, widely considered to be small because it
involves a 90o degree Cu-O-Cu bond. Due to the uncertainty in point (c), for a
crude estimation of the interladder coupling we will use the only value
available $J^{\prime}=36$ meV [31]. With regards to the leg and rung couplings
an average of the values quoted above will be used, namely we employ
$J_{leg}=J_{rung}=132$ meV. Assuming the canonical relation between
superexchange, hopping amplitude $t$ and Hubbard $U$, i.e. $J=4t^{2}/U$, we
deduce a ratio $r=t_{l}/t=\sqrt{36/132}=0.5$, well within the range $0.25<r<1$
to be discussed here. Because observables presented below appear to converge
starting at $r=0.5$ and for smaller $r$, we expect results at the realistic
$r$, likely smaller than the 0.5 previously discussed, to be approximately the
same.

##  III Results

We start by examining how the the leading $d$-wave eigenvalue $\lambda_{d}$ of
Eq. (11) depends on the ratio $r$ between intra- and inter-ladder hopping. The
Coulomb repulsion $U=1.5t$ is chosen so that $\lambda_{d}\lesssim 0.5$ in the
RPA treatment. Figure 2 shows the RPA results for $\lambda_{d}(r)$ for
$0.25<r<1$. Remarkably, we find that the maximum in $\lambda_{d}(r)$ does not
occur for the uniform $r=1$ limit. Rather, $\lambda_{d}(r)$ displays a rapid
initial rise as $r$ is reduced from $r=1$, and has a maximum for $r\approx
0.9$, before dropping again to smaller values for $0.9>r\gtrsim 0.4$. The
point $r\approx 0.9$, where the pairing strength is maximized, corresponds to
a system in which the nearest and next-nearest neighbor hopping amplitudes are
periodically modulated along the $x$-direction. As noted, a similar
enhancement of the superconducting correlations for modest hopping amplitude
modulations was also found in a recent density matrix renormalization group
study [26] of a Hubbard model with similar hopping amplitude modulations.
While the precise reason for this enhancement remains unclear, it was argued
that the spin fluctuation spectrum in the modulated array of effective two-leg
ladders is optimal for pairing (the undoped two-leg ladders have a spin gap
and thus lack the low-energy fluctuations that are detrimental to
superconductivity).

Figure 2:  The $d_{x^{2}-y^{2}}$-wave pairing strength $\lambda_{d}$ versus
hopping ratio $r$ for a Hubbard model with filling $\langle n\rangle=0.85$ and
Coulomb interaction $U=1.5t$. $\lambda_{d}$ is optimized for $r<1$
corresponding to a model with modulated hopping integrals along the
$x$-direction, i.e. effectively an array of coupled two-leg ladders.

To determine the origin of the enhanced pairing strength in our results, we
now take a closer look at the variation of the electronic structure and spin
susceptibility as the hopping ratio $r$ is reduced from one. Figure 3 shows
the bandstructure $E(k)$ (left panels), static spin susceptibility
$\chi_{s}^{\rm RPA}(q,\omega=0)$ (Eq.(10), middle panels) and $d$-wave
eigenfunction $g_{d}(k)$ of Eq. (11) (right panels) for three different values
of $r$ and the same parameters as used in Fig. 2.

Figure 3: Bandstructure $E({\bf k})$ (left panels a, d, g), static spin
susceptibility $\chi({\bf q},\omega=0)$ (middle panels b, e, h) and leading
eigenvector $g_{d}({\bf k})$ (right panels c, f, i) for the Hubbard model with
$U=1.5t$ and $\langle n\rangle=0.85$ for three different values of the hopping
ratio $r$. As $r$ is reduced from 1 and the hopping is modulated, the response
near ${\bf q}=(\pi,\pi)$ in $\chi({\bf q},0)$ increases first and then
decreases, leading to the non-mononotic behavior observed in $\lambda_{d}(r)$
in Fig. 2. The leading gap structure $g_{d}({\bf k})$ retains mostly
$d_{x^{2}-y^{2}}$ character, but also aquires an $s$-wave contribution due to
the breaking of the C4 lattice rotation symmetry. In the weakly coupled limit
($r=0.25$, panel i), the gap is nodeless and switches sign between the bonding
and antibonding Fermi surfaces. The green vector in panel f corresponds to
$q=(\pi,\pi)$ in the full Brillouin zone.

The top row (panels a \- c) shows the $r=1$ results for the uniform system.
Even in this case, the bandstructure has two bands, due to the use of a two-
site unit cell in the RPA treatment. The single band of the uniform model is
simply folded along the boundaries $(\pi/2,k_{y})$ and $(-\pi/2,k_{y})$ of the
reduced Brillouin zone of the two-site system, to give the two bands shown in
Fig. 3a. The susceptibility $\chi^{\rm RPA}_{s}(q,0)$ in panel b shows the
largest intensity at $q=(\pi,\pi)$ as expected. The eigenfunction $g_{d}(k)$
in panel c has the usual $d_{x^{2}-y^{2}}$ structure. Here the negative
(brown) regions near $k=(0,0)$ originate from the anti-bonding band, which
implicitly contains a shift of $k_{x}=\pi$, and therefore correspond to
$k=(\pi,0)$ in the full Brillouin zone. These regions are simply folded back
into the reduced Brillouin zone of the two-site system, for which $k=(0,0)$ is
equivalent to $k=(\pi,0)$.

As $r$ is reduced to 0.9 (middle row panels d-f), a small gap opens in the
bandstructure at the boundary of the reduced Brillouin zone at
$k=(\pi/2,k_{y})$. The spin susceptibility looses its C4 symmetry, but the
peak with the highest intensity remains at $q=(\pi,\pi)$. In fact, the
intensity of this peak is much higher, about 50%, than for $r=1$. This
explains the increase in $\lambda_{d}(r)$ for $r=0.9$, since, according to
Eqs. (11) and (II), the pairing strength is directly related to the magnitude
of the zero frequency spin susceptibility $\chi_{s}^{\rm RPA}(q,\omega=0)$.
This increase in $\chi_{s}^{\rm RPA}(q,\omega=0)$ can be traced to the change
in the Fermi surface and improved nesting. The vertical green vector shown in
panel f is $q=(0,\pi)$ in the reduced Brillouin zone and corresponds to
$q=(\pi,\pi)$ in the full Brillouin zone on which $\chi_{s}^{\rm
RPA}(q,\omega=0)$ is evaluated. It illustrates that the regions on the Fermi
surface that are connected by this vector are slightly more parallel than the
corresponding regions for $r=1$, thus leading to better nesting and an
increase in $\chi_{s}^{\rm RPA}(q,\omega=0)$ for $q=(\pi,\pi)$. The
eigenfunction $g_{d}(k)$ (panel f) changes slightly for $r=0.9$, but retains
mostly its $d_{x^{2}-y^{2}}$ structure. Due to the breaking of C4 rotational
symmetry, there is a small admixture of an $s$-wave component that manifests
itself in a change in the location of the nodal points ($g_{d}(k)=0$) away
from the diagonal line $k_{x}=k_{y}$ and also in a difference in the magnitude
of $g_{d}(k)$ for $k$ near $(0,0)$ ($(\pi,0)$ in full Brillouin zone) and $k$
near $(0,\pi)$.

For the $r=0.25$ case of weakly coupled ladders (bottom panels g-i), the
bandstructure has separated into bonding and anti-bonding bands, and the Fermi
surface, as can be seen from panel i, is becoming more one-dimensional.
Nevertheless, the wave vector of peak intensity in $\chi^{\rm RPA}_{s}(q,0)$
remains near $q=(\pi,\pi)$, although it has become slightly incommensurate.
The peak intensity is also reduced compared to $r=0.9$, but remains larger
than for $r=1$. We believe that the reduced pairing strength
$\lambda_{d}=0.16$ for this case is therefore due to the fact that the peak
position in $\chi^{\rm RPA}_{s}(q,0)$ has moved away from $(\pi,\pi)$. Even in
this limit, the leading eigenfunction $g_{d}(k)$ mostly retains its
$d_{x^{2}-y^{2}}$ symmetry, but due to the structure of the Fermi surface
becomes node-less. Moreover, it switches sign between the bonding (outer,
purple) and anti-bonding (inner, brown) Fermi surface segments, and shows very
little variation in magnitude along these segments, especially along the anti-
bonding segments.

We now use an RPA/BCS formalism [34, 28, 35, 36] to study the magnetic spin
excitation spectrum in the superconducting state as the hopping ratio $r$ is
tuned away from the uniform limit. For the uniform $r=1$ case, this formalism
is well known to give a resonance in $\chi^{\rm
RPA^{\prime\prime}}_{s}(q,\omega)$ [34, 28] and thus provides a framework in
which one can understand the superconducting state neutron resonance that is
found in the doped cuprates [5]. This resonance in $\chi^{\rm
RPA^{\prime\prime}}_{s}(q,\omega)$ is generally found for a wave-vector $q$
that connects regions on the Fermi surface between which the superconducting
gap $\Delta(k)$ changes sign, i.e. $\Delta(k+q)=-\Delta(k)$, and therefore has
been used as clear evidence for an unconventional superconducting state [5].
Here, we are studying how this neutron resonance evolves as the hopping
parameter $r$ is varied and the system changes from the uniform $r=1$ limit to
an array of weakly coupled Hubbard ladders. Since we generally find
eigenfunctions (gap structures) $g_{d}(k)$ that change sign on the Fermi
surface for all values of $r$, we expect a resonance to occur for all $r$.
However, the changes in the Fermi surface under variations of $r$ may
significantly affect the wave-vector $q$ at which this resonance appears, as
well its energy ($\omega$) dispersion as $q$ is varied.

In the superconducting state, the expression for $\chi^{0}$ in Eq. (II)
changes and aquires an additional term from the anomalous component $F^{0}$ of
the Green’s function

$\displaystyle\chi^{0}_{\ell_{1}\ell_{2}\ell_{3}\ell_{4}}(q,i\omega_{m})$
$\displaystyle=-\frac{T}{N}\sum_{k,\omega_{n}}\big{\\{}G^{0}_{\ell_{3}\ell_{1}}(k+q,i\omega_{n}+i\omega_{m})$
$\displaystyle\hskip 56.9055pt\times\,G^{0}_{\ell_{2}\ell_{4}}(k,i\omega_{n})$
$\displaystyle\hskip
56.9055pt+F^{0}_{\ell_{1}\ell_{3}}(-k-q,-i\omega_{n}-i\omega_{m})$
$\displaystyle\hskip 56.9055pt\times
F^{0}_{\ell_{2}\ell_{4}}(k,i\omega_{n})\big{\\}}$

with

$\displaystyle G^{0}_{\ell\ell^{\prime}}(k,i\omega_{n})$ $\displaystyle=$
$\displaystyle\sum_{\mu}a^{\ell}_{\mu}(k)a^{\ell^{\prime}*}_{\mu}(k)\frac{i\omega_{n}+\xi_{\mu}(k)}{\omega_{n}^{2}+E^{2}_{\mu}(k)}$
(14) $\displaystyle F^{0}_{\ell\ell^{\prime}}(k,i\omega_{n})$ $\displaystyle=$
$\displaystyle\sum_{\mu}a^{\ell}_{\mu}(k)a^{\ell^{\prime}}_{\mu}(k)\frac{\Delta_{\mu}(k)}{\omega_{n}^{2}+E^{2}_{\mu}(k)}\,.$
(15)

Here $E_{\mu}(k)=\sqrt{\xi_{\mu}^{2}(k)+\Delta_{\mu}^{2}(k)}$ and
$\Delta_{\mu}(k)$ is the superconducting gap on band $\mu$. To determine
$\Delta(k)$ for all $k$ in the Brillouin zone, one could take the RPA results
for the leading gap eigenfunction $g_{d}(k)$ and parametrize it in terms of
crystal harmonics [36, 37]. However, since $g_{d}(k)$ is only known for $k$ on
the Fermi surface, this procedure can lead to non-unique parametrizations. In
fact, for the system with $r<1$, we have indeed encountered difficulties in
finding unique solutions. This is possibly due the fact that C4 symmetry is
lost and other $s$-wave crystal harmonics contribute and the absence of
orthogonality of different crystal harmonics for $k$ only on the Fermi
surface.

Figure 4: Imaginary part of the RPA/BCS dynamic spin susceptibility
$\chi^{\prime\prime}_{SC}({\bf q},\omega)$ in the superconducting state along
${\bf q}=(\pi,0.5\pi)$ – $(\pi,1.5\pi)$ for the Hubbard model with $\langle
n\rangle=0.85$ and $U=1.8t$ for different values of the hopping ratio $r$
(panels a \- c). The superconducting gap structures shown in panels d \- f
were used. For the uniform case ($r=1$), the spectrum displays the usual hour
glass dispersion with a minimum in the resonance energy at ${\bf
q}=(\pi,\pi)$. For the weakly coupled ladders ($r=0.25$), a resonance appears
at incommensurate wave-vectors that disperses upward as ${\bf q}$ moves toward
$(\pi,\pi)$.

We therefore take a different approach and fix $\Delta_{\mu}(k,r)$ using the
following procedure, which defines the gap $\Delta_{\ell\ell^{\prime}}(k)$
first in orbital space: Considering only nearest-neighbor pairing, we set
$\Delta_{11/22}(k_{y})=\Delta_{0}\cos k_{y}$ along the leg-direction in the
ladder. Along the rung-direction, within the ladder, we set
$\Delta_{12/21}=-\Delta_{0}$ and between adjacent ladders
$\Delta_{12/21}=-r\Delta_{0}$, resulting in
$\Delta_{12}(k_{x})=\Delta^{*}_{21}(k_{x})=0.5e^{ik_{x}}+0.5re^{-ik_{x}}$.
This reduces to the usual $d_{x^{2}-y^{2}}$-wave $\Delta_{0}(\cos k_{x}-\cos
k_{y})$ gap for the uniform $r=1$ case. In the opposite $r=0$ limit, it
results in a gap that is only finite within the ladders, $\Delta_{0}$ along
the leg direction, $-\Delta_{0}$ along the rung direction. We then transform
$\Delta_{\ell\ell^{\prime}}(k)$ to the band representation to give

$\Delta_{\mu}(k)=\sum_{\ell\ell^{\prime}}a_{\mu}^{\ell}(k)\Delta_{\ell\ell^{\prime}}(k)a_{\mu}^{\ell^{\prime}}(-k)\,.$
(16)

In addition, in order to describe the behavior of the order parameter away
from the Fermi surface, we have multiplied $\Delta_{\mu}(k)$ by a Gaussian
cut-off $\exp\\{-[\xi_{\mu}(k)/\Omega_{0}]^{2}\\}$ with $\Omega_{0}=0.1t$. The
gap magnitude is set to $\Delta_{0}=0.06t$ for all calculations, resulting in
an anti-nodal gap magnitude of $2\Delta_{0}=0.12t$ for the uniform case. The
resulting gap $\Delta_{\mu}(k)$ in band representation is shown in Fig. 4,
panels d-f for $r=1$, $0.9$ and $0.25$, respectively. Comparing with panels c,
f and i in Fig. 3, one sees that this gap structure represents the leading RPA
eigenfunction $g_{d}(k)$ well, including in particular the rather isotropic
nature of the nodeless $r=0.25$ case.

Using this gap structure, we have calculated the dynamic spin susceptibility
$\chi^{RPA}_{s}(q,\omega)$ (Eq. (10)) using Eqs. (3) and (III) for different
$r$. The top panels a-c in Fig. 4 show the imaginary part of
$\chi^{RPA}_{SC}(q,\omega)$ calculated in the superconducting state for $q$
along the line from $(\pi,0.5\pi)$ to $(\pi,1.5\pi)$. For the uniform $r=1$
case, we find the usual hour-glass like spectrum [34, 28]. In the
superconducting state, a spin gap opens and low energy normal state spectral
weight is transferred to a resonance at $\omega\approx 0.15t$, i.e. inside the
spin gap $2\Delta_{0}=0.24t$. The resonance energy has a minimum at
$q=(\pi,\pi)$ and disperses upwards on either side. For the slightly modulated
$r=0.9$ case, the spectrum is very similar with the resonance becoming
slightly stronger and moving down in energy. This is due to the enhanced
nesting for this case as discussed already in the context of Fig. 3.

In the weakly coupled ladder case, $r=0.25$, the spectrum changes drastically
and displays two columns of scattering centered at incommensurate $q$-vectors.
The resonance completely disappears at $q=(\pi,\pi)$. At smaller (and larger)
$q_{y}\approx 0.85$ ($1.15$) a strong resonance is seen that displays a
downward dispersion as $q$ moves away from $(\pi,\pi)$. This result is
consistent with the static spin susceptibility shown for this case in Fig. 3
h, where the peak of highest intensity has moved away from $q=(\pi,\pi)$ to
smaller $q_{y}$. For this case, $q=(\pi,\pi)$ does not connect different
pieces of the Fermi surface. Rather, they are connected by $q=(\pi,q_{y})$
with $q_{y}$ reduced to $\sim 0.85\pi$. As $q_{y}$ decreases further,
$(\pi,q_{y})$ connects regions on the Fermi surface where the gap
$\Delta_{\mu}(k)$ has decreased, explaining the downward dispersion of the
resonance with decreasing $q_{y}$. Compared to the cases with $r\lesssim 1$,
the resonance for $r=0.25$ appears at much smaller energies. This is due to
the fact that the gap $\Delta_{\mu}(k)$ (panel f) is smaller for this case.

##  IV Summary and Conclusions

We have used a weak-coupling RPA spin-fluctuation formalism to analyze the
superconducting pairing properties of a two-dimensional Hubbard model with
modulated hopping amplitudes as it evolves from the uniform square lattice
limit to an array of weakly coupled two-leg ladder. For the values of the
inter-ladder to intra-ladder hopping ratio $r$ we have studied, we have found
a leading pairing instability with dominant $d_{x^{2}-y^{2}}$ structure. The
$d$-wave pairing strength $\lambda_{d}$ is found to have a maximum for $r=0.9$
representing a system with a slight unidirectional modulation in the hopping
amplitudes. This enhancement in the pairing correlations over the uniform 2D
limit arises from an increase in the spin-fluctuation pairing interaction due
to increased nesting in the Fermi surface.

We then calculated the dynamical magnetic susceptibility in the
superconducting state using an RPA/BCS formalism. We have shown that the
resonance that is found in the uniform model for commensurate $q=(\pi,\pi)$
becomes stronger for $r=0.9$, and then evolves into two distinct resonances at
incommensurate wave-vectors for $r=0.25$ when the two-leg ladders are weakly
coupled. These results provide new insight into the general question of how
the electronic structure can be changed to optimize superconductivity, and how
these changes in the electronic structure, and the resulting pairing
properties, manifest themselves in the magnetic excitation spectrum that can
be measured in inelastic neutron scattering experiments.

We conclude reminding readers that the study of ladders has received renewed
attention in the context of iron-based superconductors where it has been
reported that the ladder materials BaFe2X3 (X = S, Se) become superconducting
at high pressure [38, 39, 40, 41, 42, 43, 44, 45, 46], similarly as the Cu-
ladders do. Moreover, exotic spin states involving antiferromagnetically
coupled ferromagnetic spin “blocks” have been studied experimentally and
theoretically [47, 48, 49, 50, 51, 52, 53, 54], and predictions for such
unusual spins arrangement in diffraction neutron scattering were made and
confirmed. This is a fertile area where inelastic neutron scattering can make
an impact similar as in cuprates when single crystals become available.
Predicting their properties within RPA in the unusual $s\pm$ pairing state or
in the doped block states for an array of weakly coupled iron ladders is a
challenge to be addressed in the near future.

###### Acknowledgements.

This work was supported by the U.S. Department of Energy, Office of Basic
Energy Sciences, Materials Sciences and Engineering Division. This manuscript
has been authored by UT-Battelle, LLC, under Contract No. DE-AC0500OR22725
with the U.S. Department of Energy. The United States Government retains and
the publisher, by accepting the article for publication, acknowledges that the
United States Government retains a nonexclusive, paid-up, irrevocable, world-
wide license to publish or reproduce the published form of this manuscript, or
allow others to do so, for the United States Government purposes. The
Department of Energy will provide public access to these results of federally
sponsored research in accordance with the DOE Public Access Plan
(http://energy.gov/downloads/doe-public-access-plan).

## References

  * Hubbard [1963] J. Hubbard, Proc. Royal Soc. A 276, 238 (1963).
  * Anderson [1987] P. W. Anderson, Science 235, 1196 (1987).
  * Zhang and Rice [1988] F. C. Zhang and T. M. Rice, Phys. Rev. B 37, R3759 (1988).
  * Dagotto [1994] E. Dagotto, Rev. Mod. Phys. 66, 763 (1994).
  * Scalapino [2012] D. J. Scalapino, Rev. Mod. Phys. 84, 1383 (2012).
  * Qin  _et al._ [2021] M. Qin, T. Schäfer, S. Andergassen, P. Corboz, and E. Gull, preprint arxiv/2104.00064v1 (2021).
  * Arovas  _et al._ [2021] D. P. Arovas, E. Berg, S. Kivelson, and S. Raghu, preprint arxiv/2103.12097 (2021).
  * Maier  _et al._ [2005a] T. A. Maier, M. Jarrell, T. C. Schulthess, P. R. C. Kent, and J. B. White, Phys. Rev. Lett. 95, 237001 (2005a).
  * Staar  _et al._ [2014] P. Staar, T. Maier, and T. C. Schulthess, Phys. Rev. B 89, 195133 (2014).
  * Zheng  _et al._ [2017] B.-X. Zheng, C.-M. Chung, P. Corboz, G. Ehlers, M.-P. Qin, R. M. Noack, H. Shi, S. R. White, S. Zhang, and G. K.-L. Chan, Science 358, 1155 (2017).
  * Qin  _et al._ [2020] M. Qin, C. M. Chung, H. Shi, E. Vitali, C. Hubig, U. Schollwöck, S. R. White, and S. Zhang, Phys. Rev. X 10, 31016 (2020).
  * Jiang  _et al._ [2020a] Y.-F. Jiang, J. Zaanen, T. P. Devereaux, and H.-C. Jiang, Phys. Rev. Research 2, 33073 (2020a).
  * Chung  _et al._ [2020] C. M. Chung, M. Qin, S. Zhang, U. Schollwöck, and S. R. White, Phys. Rev. B 102, 041106 (2020).
  * Dagotto  _et al._ [1992] E. Dagotto, J. Riera, and D. Scalapino, Phys. Rev. B 45, 5744 (1992).
  * Dagotto and Rice [1996] E. Dagotto and T. M. Rice, Science 271, 618 (1996).
  * Vuletić  _et al._ [2006] T. Vuletić, B. Korin-Hamzić, T. Ivek, S. Tomić, B. Gorshunov, M. Dressel, and J. Akimitsu, Phys. Rep. 428, 169 (2006).
  * Uehara  _et al._ [1996] M. Uehara, T. Nagata, J. Akimitsu, H. Takahashi, N. Môri, and K. Kinoshita, J. Phys. Soc. Japan 65, 2764 (1996).
  * Piskunov  _et al._ [2005] Y. Piskunov, D. Jérome, P. Auban-Senzier, P. Wzietek, and A. Yakubovsky, Phys. Rev. B 72, 064512 (2005).
  * Dagotto [1999] E. Dagotto, Rep. Prog. Phys. 62, 1525 (1999).
  * Noack  _et al._ [1995] R. M. Noack, S. R. White, and D. J. Scalapino, Europhys. Lett. 30, 163 (1995).
  * Dolfi  _et al._ [2015] M. Dolfi, B. Bauer, S. Keller, and M. Troyer, Phys. Rev. B 92, 195139 (2015).
  * Jiang  _et al._ [2020b] H.-C. Jiang, S. Chen, and Z.-Y. Weng, Phys. Rev. B 102, 104512 (2020b).
  * Rømer  _et al._ [2020] A. T. Rømer, T. A. Maier, A. Kreisel, I. Eremin, P. J. Hirschfeld, and B. M. Andersen, Phys. Rev. Research 2, 13108 (2020).
  * Maier  _et al._ [2005b] T. Maier, M. Jarrell, T. Pruschke, and M. Hettler, Rev. Mod. Phys. 77, 1027 (2005b).
  * Nocera  _et al._ [2018] A. Nocera, Y. Wang, N. D. Patel, G. Alvarez, T. A. Maier, E. Dagotto, and S. Johnston, Phys. Rev. B 97, 195156 (2018).
  * Jiang and Kivelson [2021] H.-C. Jiang and S. A. Kivelson, preprint arXiv:2105.07048 (2021).
  * Sakamoto and Kuroki [2020] H. Sakamoto and K. Kuroki, Phys. Rev. Research 2, 22055 (2020).
  * Norman [2007] M. Norman, Phys. Rev. B 75, 184514 (2007).
  * Kubo [2007] K. Kubo, Phys. Rev. B 75, 224509 (2007).
  * Graser  _et al._ [2009] S. Graser, T. A. Maier, P. J. Hirschfeld, and D. J. Scalapino, New J. Phys. 11, 25016 (2009).
  * Notbohm  _et al._ [2007] S. Notbohm, P. Ribeiro, B. Lake, D. A. Tennant, K. P. Schmidt, G. S. Uhrig, C. Hess, R. Klingeler, G. Behr, B. Büchner, M. Reehuis, R. I. Bewley, C. D. Frost, P. Manuel, and R. S. Eccleston, Phys. Rev. Lett. 98, 027403 (2007).
  * Matsuda  _et al._ [2000] M. Matsuda, K. Katsumata, R. S. Eccleston, S. Brehmer, and H.-J. Mikeska, Phys. Rev. B 62, 8903 (2000).
  * Nunner  _et al._ [2002] T. S. Nunner, P. Brune, T. Kopp, M. Windt, and M. Grüninger, Phys. Rev. B 66, 180404 (2002).
  * Eremin  _et al._ [2005] I. Eremin, D. K. Morr, A. V. Chubukov, K. H. Bennemann, and M. R. Norman, Phys. Rev. Lett. 94, 147001 (2005).
  * Maier and Scalapino [2008] T. Maier and D. Scalapino, Phys. Rev. B 78, 20514 (2008).
  * Maier  _et al._ [2009] T. A. Maier, S. Graser, D. J. Scalapino, and P. J. Hirschfeld, Phys. Rev. B 79, 224510 (2009).
  * Maier  _et al._ [2012] T. A. Maier, P. J. Hirschfeld, and D. J. Scalapino, Phys. Rev. B 86, 94514 (2012).
  * Takahashi  _et al._ [2015] H. Takahashi, A. Sugimoto, Y. Nambu, T. Yamauchi, Y. Hirata, T. Kawakami, M. Avdeev, K. Matsubayashi, F. Du, C. Kawashima, H. Soeda, S. Nakano, Y. Uwatoko, Y. Ueda, T. J. Sato, and K. Ohgushi, Nat. Mat. 14, 1008 (2015).
  * Yamauchi  _et al._ [2015] T. Yamauchi, Y. Hirata, Y. Ueda, and K. Ohgushi, Phys. Rev. Lett. 115, 246402 (2015).
  * Lei  _et al._ [2011] H. Lei, H. Ryu, A. I. Frenkel, and C. Petrovic, Phys. Rev. B 84, 214511 (2011).
  * Dagotto [2013] E. Dagotto, Rev. Mod. Phys. 85, 849 (2013).
  * Patel  _et al._ [2016] N. D. Patel, A. Nocera, G. Alvarez, R. Arita, A. Moreo, and E. Dagotto, Phys. Rev. B 94, 075119 (2016).
  * Zhang  _et al._ [2017] Y. Zhang, L. Lin, J.-J. Zhang, E. Dagotto, and S. Dong, Phys. Rev. B 95, 115154 (2017).
  * Zhang  _et al._ [2018] Y. Zhang, L.-F. Lin, J.-J. Zhang, E. Dagotto, and S. Dong, Phys. Rev. B 97, 045119 (2018).
  * Zhang  _et al._ [2020a] Y. Zhang, L.-F. Lin, A. Moreo, S. Dong, and E. Dagotto, Phys. Rev. B 101, 144417 (2020a).
  * Patel  _et al._ [2017] N. D. Patel, A. Nocera, G. Alvarez, A. Moreo, and E. Dagotto, Phys. Rev. B 96, 024520 (2017).
  * Rincón  _et al._ [2014] J. Rincón, A. Moreo, G. Alvarez, and E. Dagotto, Phys. Rev. Lett. 112, 106405 (2014).
  * Caron  _et al._ [2012] J. M. Caron, J. R. Neilson, D. C. Miller, K. Arpino, A. Llobet, and T. M. McQueen, Phys. Rev. B 85, 180405 (2012).
  * Caron  _et al._ [2011] J. M. Caron, J. R. Neilson, D. C. Miller, A. Llobet, and T. M. McQueen, Phys. Rev. B 84, 180409 (2011).
  * Mourigal  _et al._ [2015] M. Mourigal, S. Wu, M. B. Stone, J. R. Neilson, J. M. Caron, T. M. McQueen, and C. L. Broholm, Phys. Rev. Lett. 115, 047401 (2015).
  * Wang  _et al._ [2016] M. Wang, M. Yi, S. Jin, H. Jiang, Y. Song, H. Luo, A. D. Christianson, C. de la Cruz, E. Bourret-Courchesne, D.-X. Yao, D. H. Lee, and R. J. Birgeneau, Phys. Rev. B 94, 041111 (2016).
  * Zhang  _et al._ [2019] Y. Zhang, L.-F. Lin, A. Moreo, S. Dong, and E. Dagotto, Phys. Rev. B 100, 184419 (2019).
  * Zhang  _et al._ [2020b] Y. Zhang, L.-F. Lin, A. Moreo, S. Dong, and E. Dagotto, Phys. Rev. B 101, 144417 (2020b).
  * Herbrych  _et al._ [2019] J. Herbrych, J. Heverhagen, N. D. Patel, G. Alvarez, M. Daghofer, A. Moreo, and E. Dagotto, Phys. Rev. Lett. 123, 027203 (2019).