1 Introduction
1.1
Let X be a (noncompact) toric Calabi–Yau threefold. To X, one can associate a two-dimensional quantum field theory with four supercharges, and we will be interested in two features of this theory: its vector space of BPS states, and more importantly for us, the BPS algebra which acts on said vector space. The latter algebra has been dubbed the quiver quantum toroidal algebra ([Reference Galakhov, Li and Yamazaki4, Reference Galakhov, Li and Yamazaki5, Reference Noshita and Watanabe13, Reference Noshita and Watanabe14], following [Reference Li and Yamazaki9]).
Before we dive into the definition of the quiver quantum toroidal algebra
${\widetilde {\mathbf {U}}}$
, let us recall certain objects associated to the Calabi–Yau threefold X
$$ \begin{align*}X \leadsto \text{toric diagram} \leadsto \text{brane tiling} \leadsto \text{quiver}. \end{align*} $$
We refer the reader to [Reference Noshita and Watanabe14, Appendix C] for a detailed review of the procedures
$\leadsto $
listed above, and we simply contend ourselves with stating the following properties of the objects involved.
-
• The toric diagram associated to X is a particular collection of points in
${\mathbb {Z}}^2$
and line segments between them. -
• The normals to the aforementioned line segments can be drawn on the torus
${\mathbb {T}}^2$
, and they define a brane tiling, that is, a decomposition of the torus into polygonal regions called faces. Very importantly, the faces can be colored in blue and red such that any two faces which share an edge have different colors.Footnote
1
-
• The vertices and edges of the aforementioned faces determine a quiver Q drawn on
${\mathbb {T}}^2$
. The bicolorability property of the brane tiling implies that the edges of Q can be oriented so that they go clockwise around the blue faces and counterclockwise around the red faces. The interested reader may find the quiver associated to the Calabi–Yau threefold
$X = {\mathbb {C}}^3$
in Figure 1.Figure 1 The quiver associated to
$X = {\mathbb {C}}^3$
. The above square is the usual representation of the flat torus, so the quiver has one vertex, three edges and two faces.
1.2
As the definition of the quiver quantum toroidal algebra
${\widetilde {\mathbf {U}}^+}$
only takes the quiver as input, one can state the construction in generality greater than those quivers which arise from toric Calabi–Yau threefolds via the procedure above.
Definition 1.3. Let Q be a quiver drawn on a torus (with vertex set I and edge set E), whose faces are colored in blue and red such that the two incident faces to a given edge have different colors. We assume that the edges of the quiver are oriented so as to go clockwise around the blue faces.
We will write
$\widetilde {Q}$
for the lift of Q to the universal cover
${\mathbb {R}}^2$
of
${\mathbb {T}}^2$
and note that
$\widetilde {Q}$
inherits the blue/red colored faces of Q. In the present paper, ‘paths’ and ‘cycles’ in a quiver will refer to the oriented notions.
Definition 1.4. A broken wheel refers to a path obtained by removing a single edge e from the boundary of any face F of
$\widetilde {Q}$
. The mirror image of the aforementioned broken wheel is the path obtained by removing e from the boundary of the other face
$F' \neq F$
incident to e. The edge e will be called the interface of the broken wheel (and of its mirror image).
Figure 2 A broken wheel (the path in red) and its mirror image (the path in blue). The black arrow is the interface.
Definition 1.5. The quiver Q is called shrubby if, given any paths
$p \neq p'$
in
$\widetilde {Q}$
with the same start and end points, at least one of p and
$p'$
contains a broken wheel whose interface lies in the closed region between the two paths.
When one of p and
$p'$
is trivial, Definition 1.5 states that any cycle in
$\widetilde {Q}$
must contain a broken wheel in the closure of its interior. We will see in Lemma A.3 that the shrubbiness condition above is implied by more traditional notions of consistency of brane tilings and dimer models, such as the existence of a nondegenerate R-charge. We do not know (and it is an interesting question) whether all quivers which arise from Calabi–Yau threefolds as in Subsection 1.1 are shrubby.
1.6
Let
${\mathbb {K}}$
be a field of characteristic 0. To every edge e of the quiver Q, we associate a parameter
$t_e \in {\mathbb {K}}^\times $
such that for every face F of Q we haveFootnote
2
$$ \begin{align} \prod_{e \text{ edge around }F} t_e = 1. \end{align} $$
We make the following genericity assumption on the parameters
$\{t_e\}_{e \text { edge}}$
.
Assumption 1.7. There exists a field homomorphism
$\rho : {\mathbb {K}} \rightarrow {\mathbb {C}}$
such that
$$ \begin{align} \left| \prod_{e \text{ edge along } p} \rho(t_e) \right| \neq \left| \prod_{e \text{ edge along } p'} \rho(t_e) \right| \end{align} $$
for any paths p and
$p'$
in
$\widetilde {Q}$
with the same end point but different starting points.
In [Reference Li and Yamazaki9] and related works, products of the parameters
$t_e$
along paths in
$\widetilde {Q}$
are interpreted as coordinate functions of atoms in crystals; in this language, condition (1.2) is equivalent to requiring that different atoms have different coordinates. Thus, Assumption 1.7 holds in the physical settings that motivated the present paper.
The edge parameters can be assembled into the following rational functions
$$ \begin{align} \zeta_{ij}(x) = \frac {\alpha_{ij} x^{s_{ij}}}{(1-x)^{\delta_{ij}}} \prod_{e \text{ arrow from }i \text{ to }j} (1-xt_e) \in {\mathbb{K}}(x) \end{align} $$
for all
$i,j \in I$
, where
$\alpha _{ij} \in {\mathbb {K}}^\times $
and
$s_{ij} \in {\mathbb {Z}}$
are suitably chosen (but will not play an important role in the present paper, so we will not specify them explicitly).
Remark 1.8. Moreover, different authors use different conventions on
$\alpha _{ij}$
and
$s_{ij}$
. For example, [Reference Galakhov, Li and Yamazaki4] requires
$s_{ij}$
to be minus half the number of arrows from i to j; this situation can also be accommodated by the present paper, at the cost of replacing polynomials built out of integer powers by polynomials built out of half-integer powers. We will avoid this setup in order to not overburden our notation.
1.9
Using the data in Subsection 1.6, we will now review the definition of the quantum toroidal algebra associated to the quiver Q and parameters
$\{t_e\}_{e \in E}$
, which was introduced in [Reference Galakhov, Li and Yamazaki4, Reference Noshita and Watanabe13] as a trigonometric version of the quiver Yangian of [Reference Li and Yamazaki9] (see also [Reference Rapcak, Soibelman, Yang and Zhao16] for a closely related mathematical construction).
Definition 1.10. The (half) quiver quantum toroidal algebra
${\widetilde {\mathbf {U}}^+}$
is
$$ \begin{align} {\widetilde{\mathbf{U}}^+} = {\mathbb{K}} \Big\langle e_{i,d} \Big \rangle_{i \in I, d \in {\mathbb{Z}}} \Big / \text{relation (1.5)}, \end{align} $$
where if we write
$$ \begin{align*}e_i(z) = \sum_{d \in {\mathbb{Z}}} \frac {e_{i,d}}{z^d}, \end{align*} $$
then the defining relations are given by the formula
$$ \begin{align} e_i(z) e_j(w) \zeta_{ji} \left(\frac wz\right) = e_j(w) e_i(z) \zeta_{ij} \left( \frac zw \right) \end{align} $$
for all
$i,j \in I$
.Footnote
3
Define
${\widetilde {\mathbf {U}}^-} = {\widetilde {\mathbf {U}}}^{+,\text {op}}$
, and denote its generators by
$f_{i,d}$
instead of
$e_{i,d}$
. Finally, let us consider the commutative algebra
$$ \begin{align*}\mathbf{U}^0 = {\mathbb{K}}\left[h_{i,d}, h^{\prime}_{i,d'}\right]_{i \in I, d,d' \geq \text{ appropriately chosen integers}}. \end{align*} $$
Then the (full) quiver quantum toroidal algebra is defined as
$$ \begin{align} {\widetilde{\mathbf{U}}} = {\widetilde{\mathbf{U}}^+} \otimes \mathbf{U}^0 \otimes {\widetilde{\mathbf{U}}^-} \end{align} $$
with certain commutation relations imposed between elements in the three tensor factors above. We refer the reader to [Reference Galakhov, Li and Yamazaki4, Reference Noshita and Watanabe13] for the explicit commutation relations, as they will not be used in the present paper; instead, we will only focus on
${\widetilde {\mathbf {U}}^+}$
.
1.11
The main motivation for defining the algebra
${\widetilde {\mathbf {U}}}$
is that it acts on the vector space of so-called BPS crystal configurations
$$ \begin{align} {\widetilde{\mathbf{U}}} \curvearrowright M = \bigoplus_{\Lambda \text{ 3d crystal configuration}} {\mathbb{K}} \cdot |\Lambda\rangle \end{align} $$
(see [Reference Noshita and Watanabe13, Section 5] for a review of three-dimensional crystal configurations, which are generalizations of plane partitions). We will not make the action (1.7) explicit, so we will not make any rigorous claims about it and merely use it as motivation for our subsequent constructions. The main goal of the present paper is to describe the kernel of the action (1.7), that is, to define the smallest possible quotient
$$ \begin{align} {\widetilde{\mathbf{U}}} \twoheadrightarrow \mathbf{U} \end{align} $$
such that the action (1.7) factors through an action of
$\mathbf {U}$
. To this end, we will consider the shuffle algebra realization of quiver quantum toroidal algebras
$$ \begin{align*}{\widetilde{\mathbf{U}}^\pm} \xrightarrow{\widetilde{\Upsilon}^\pm} {\mathcal{V}}^\pm = \bigoplus_{\boldsymbol{n} \in {\mathbb{N}}^I} {\mathbb{K}}[z_{i1},z_{i1}^{-1},\dots,z_{in_i}, z_{in_i}^{-1}]_{i \in I}^{\textrm{sym}} \end{align*} $$
(we refer the reader to Subsection 2.1 for a description of the shuffle product on
${\mathcal {V}}^\pm $
and to Subsection 2.3 for the definition of the homomorphism
$\widetilde {\Upsilon }^\pm $
). Set
$$ \begin{align} \mathbf{U}^\pm = {\widetilde{\mathbf{U}}^\pm} \Big / \text{Ker }\widetilde{\Upsilon}^{\pm}. \end{align} $$
As noted in [Reference Galakhov, Li and Yamazaki4, Section 5], the action (1.7) factors through the shuffle algebra. Therefore, the reduced (full) quiver quantum toroidal algebra
$$ \begin{align} \mathbf{U} = \mathbf{U}^+ \otimes \mathbf{U}^0 \otimes \mathbf{U}^- \end{align} $$
will inherit an action on M from Equation (1.7). To define this action, one needs to impose the same commutation relations between the tensor factors of Equation (1.10) as between the tensor factors of Equation (1.6). We will not present these relations explicitly in the present paper and make no rigorous claims about them. Instead, we will focus on
$\mathbf {U}^+$
.
1.12
The main purpose of the present paper is to describe
$\mathbf {U}^\pm $
by explicitly presenting the quotient (1.9). More specifically, we will describe a collection of generators for the two-sided ideal
$\text {Ker } \widetilde {\Upsilon }^\pm $
. For every face
$F = \{i_0,i_1,\dots ,i_{k-1},i_k=i_0\}$
of the quiver Q (note that some of the indices
$i_0,\dots ,i_{k-1}$
may be repeated within a given face), consider the following parameters corresponding to the edges of F
$$ \begin{align} t_a = t_{\overrightarrow{i_{a-1}i_a}}. \end{align} $$
Note that
$t_1\dots t_k = 1$
due to (1.1). Let
$\widetilde {\zeta }_{ij}(x) = \zeta _{ij}(x) (1-x)^{\delta _{ij}}$
for all
$i,j \in I$
. Then we may define the formal series
$$ \begin{align} e_F(x_1,\dots,x_k) \in {\widetilde{\mathbf{U}}^+}[[x_1, x_1^{-1}, \dots, x_k,x_k^{-1}]] \end{align} $$
by the following formula
$$ \begin{align} \sum_{a=1}^k \frac {x_1t_2\dots t_a}{x_a} \cdot & \frac { \prod_{b \succ c} \widetilde{\zeta}_{i_ci_b} \left(\frac {x_c}{x_b} \right)\left( - \frac {x_b}{x_c} \right)^{\delta_{i_bi_c} \delta_{b<c}} }{\prod_{b \sim c + 1} \left(1 - \frac {x_ct_b}{x_b} \right)} \cdot \nonumber\\ & \qquad\qquad\qquad\cdot e_{i_{a}}(x_{a}) \dots e_{i_1}(x_1) e_{i_k}(x_k) \dots e_{i_{a+1}}(x_{a+1}) \end{align} $$
In Equation (1.13), the notation
$b \succ c$
(respectively
$b \sim c+1$
) means that b precedes (respectively immediately precedes) c in the sequence
$(a,\dots ,1,k,\dots ,a+1)$
. The symbols
$\delta _{b<c}$
and
$\delta _{i_bi_c}$
are defined as in Subsection 3.1. Note that the first line of Equation (1.13) is a Laurent polynomial in
$x_1,\dots ,x_k$
due to the fact that all the denominators
$$ \begin{align*}1-\frac {x_ct_b}{x_b} \end{align*} $$
are canceled by the
$\widetilde {\zeta }$
functions in the numerator. The following is our main result.
Theorem 1.13. If Q is shrubby (as in Definition 1.5), then the coefficients of the series (1.12) generate
$\mathrm {Ker } \widetilde {\Upsilon }^+$
as a two-sided ideal. In other words, we have
$$ \begin{align} \mathbf{U}^+ = {\widetilde{\mathbf{U}}^+} \Big / \Big(\text{series coefficients of }e_F(x_1,\dots,x_k) \Big)_{F \text{ face of }Q}. \end{align} $$
Similar results hold for
$\mathbf {U}^-$
by replacing e’s with f’s and reversing the order of the factors in the product on the second line of Equation (1.13).Footnote
4
Lemma A.3 implies that a large family of physically interesting Calabi–Yau threefolds X correspond to shrubby quivers, and so Theorem 1.13 applies to them. We conclude that the relations which we factor in Equation (1.14) are the sought-for ‘Serre relations’ of [Reference Galakhov, Li and Yamazaki4]. The terminology of these relations is historically motivated by the analogous situation of quantum loop groups associated to finite type Dynkin diagrams, in which the role of relations (1.14) is played by the Drinfeld–Serre relations. Note, however, that the classic Drinfeld–Serre relations are not enough to characterize quantum loop groups associated to general Dynkin diagrams (see [Reference Neguţ12]).
Remark 1.14. If Q is not shrubby, then we expect that one needs additional relations besides Equation (1.13). In this situation, the ideal
$\mathrm {Ker}\ \widetilde {\Upsilon }^+$
can be studied according to the general principles of [Reference Neguţ11], but we do not know explicit generators of this ideal.
Remark 1.15. It is straightforward to write down rational/elliptic versions of the relations (1.13), which would give necessary relations that hold in the rational/elliptic counterparts of the reduced algebra
$\mathbf {U}^+$
(see [Reference Galakhov, Li and Yamazaki4] for an overview). However, in the rational/elliptic settings, we do not know whether these relations are also sufficient, that is, if they generate the analogue of the two-sided ideal
$\mathrm {Ker }\widetilde {\Upsilon }^+$
.
1.16
Let us spell out the constructions above in the case
$X = {\mathbb {C}}^3$
, when the quiver is the one in Figure 1. There is a single vertex, so
$I = \{\bullet \}$
and we will henceforth suppress the indices
$i \in I$
from all our formulas. There are three edges, whose associated parameters
$t_1,t_2,t_3$
satisfy the equation
$$ \begin{align*}t_3 = \frac 1{t_1t_2}. \end{align*} $$
We take the ground field to be
${\mathbb {K}} = {\mathbb {Q}}(t_1,t_2)$
. The only
$\zeta $
function (1.3) is
$$ \begin{align*}\zeta(x) = \frac {x^{-1}(1-xt_1)(1-xt_2)(1-xt_3)}{1-x} \end{align*} $$
(the particular choice of the monomial
$x^{-1}$
was made in order to match existing conventions in the literature). The (half) quiver quantum toroidal algebra (1.4) is generated by a single formal series
$e(z)$
modulo the quadratic relation
$$ \begin{align} e(z) e(w) (z-wt_1)(z-wt_2)& (z-wt_3) = \nonumber \\ &\qquad = e(w) e(z) (zt_1-w)(zt_2-w)(zt_3-w). \end{align} $$
Meanwhile, formula (1.13) for the red face in Figure 1 reads
$$ \begin{align} \hspace{-25pt}e_{F_{\text{red}}}(x_1,x_2,x_3)& = \frac {\prod_{i=1}^3 [ (x_1-x_2t_i)(x_1-x_3t_i)(x_3-x_2t_i) ]}{x_1x_2^3x_3^3(x_1-x_3t_1)(x_3-x_2t_3)} e(x_1)e(x_3)e(x_2) \nonumber\\ &\quad + \frac {t_2\prod_{i=1}^3 [ (x_2-x_1t_i)(x_1-x_3t_i)(x_2-x_3t_i) ]}{x_2^3x_3^4(x_2-x_1t_2)(x_1-x_3t_1)} e(x_2)e(x_1)e(x_3) \\ \nonumber &\quad + \frac {t_2t_3\prod_{i=1}^3 [ (x_2-x_1t_i)(x_3-x_1t_i)(x_3-x_2t_i) ]}{x_1x_2^2x_3^4(x_3-x_2t_3)(x_2-x_1t_2)} e(x_3)e(x_2)e(x_1) \end{align} $$
while the analogous expression
$e_{F_{\text {blue}}}$
for the blue face is obtained by replacing
$\{t_1,t_2,t_3\} \leftrightarrow \{t_3,t_2,t_1\}$
. Note that the expressions in
$x_1,x_2,x_3$
that precede the series
$e(\dots )$
in the three lines of Equation (1.16) are actually Laurent polynomials, and so it makes sense to talk about their coefficients. Theorem 1.13 states that
$$ \begin{align*}\mathbf{U}^+ = \frac {{\mathbb{Q}}(t_1,t_2) \langle \dots, e_{-1},e_0,e_1,\dots \rangle}{\text{Equation}\ (1.5)\ \text{and coefficients of } e_{F_{\text{red}}}(x_1,x_2,x_3) \text{ and } e_{F_{\text{blue}}}(x_1,x_2,x_3)}. \end{align*} $$
Let us make two observations about formulas (1.16), which apply equally well in the more general context of Theorem 1.13. Firstly, as explained in Remark 3.8, many of the coefficients of
$e_{F_{\text {red}}}$
and
$e_{F_{\text {blue}}}$
are superfluous; we would obtain the same reduced quiver quantum toroidal algebra
$\mathbf {U}^+$
if we only imposed relations given by a single coefficient of Equation (1.16) of every total homogeneous degree in
$x_1,x_2,x_3$
. This is because any two such coefficients of the same total homogeneous degree are equivalent to each other up to multiples of the quadratic relation (1.15).
Secondly (and perhaps most importantly) there is nothing ‘canonical’ about the relations in
$\mathbf {U}^+$
given by setting the coefficients of
$e_{F_{\text {red}}}$
and
$e_{F_{\text {blue}}}$
equal to 0 since we would obtain the exact same algebra by adding various multiples of relation (1.15) to the aforementioned coefficients. For example, if we consider the positive half of the well-known quantum toroidal algebra
$$ \begin{align*}U_{t_1,t_2}^+(\widehat{\widehat{{\mathfrak{gl}}}}_1) = \frac {{\mathbb{Q}}(t_1,t_2) \langle \dots, e_{-1},e_0,e_1,\dots \rangle}{\text{Equation}\ (1.5)\ \text{and}\ [[e_{k+1},e_{k-1}],e_k]=0, \ \forall k \in {\mathbb{Z}}}, \end{align*} $$
then we have an isomorphism
$$ \begin{align*}\mathbf{U}^+ \cong U_{t_1,t_2}^+(\widehat{\widehat{{\mathfrak{gl}}}}_1), \quad e_k \mapsto e_k, \ \forall k \in {\mathbb{Z}} \end{align*} $$
on account of the fact that both algebras are isomorphic to the shuffle algebra
${\mathcal {S}}^+$
of Section 2 (see Theorem 2.7 and [Reference Tsymbaliuk17, Theorem 7.3]). However, the cubic relations in the two algebras look quite different, and the fact that they can be obtained from each other by adding multiples of Equation (1.15) is a very involved computation.
1.17
Quiver quantum toroidal algebras are related to the K-theoretic Hall algebras (defined in [Reference Pădurariu15], by analogy with the cohomological Hall algebras of [Reference Kontsevich and Soibelman6])
$$ \begin{align*}K(Q,W) \end{align*} $$
defined with respect to the following potential
$$ \begin{align*}W = \sum_{F \text{ face of }Q} (-1)^F \prod_{e \text{ edge around }F} \phi_e \in {\mathbb{C}}[Q], \end{align*} $$
where
$(-1)^F$
is
$+1$
or
$-1$
depending on whether the face F is blue or red, and the symbols
$\phi _e$
denote generators of the path algebra
${\mathbb {C}}[Q]$
. We consider
$K(Q,W)$
as an algebra over the ring
${\mathbb {L}}$
of polynomials in the edge parameters (modulo (1.1)), and let our ground field be
${\mathbb {K}} = \text {Frac}({\mathbb {L}})$
. Then the localized K-theoretic Hall algebra
$$ \begin{align*}K(Q,W)_{\text{loc}} = K(Q,W) \bigotimes_{{\mathbb{L}}} {\mathbb{K}} \end{align*} $$
is endowed with an algebra homomorphism
$$ \begin{align*}K(Q,W)_{\text{loc}} \xrightarrow{\iota} {\mathcal{V}}^+. \end{align*} $$
By combining Theorem 2.7, Definition 3.7 and Proposition 3.10, the image of
$\widetilde {\Upsilon }^+$
can be described as the subspace
${\mathcal {S}}^+ \subset {\mathcal {V}}^+$
of Laurent polynomialsFootnote
5
$R(z_1,\dots ,z_k,\dots )$
which vanish whenever their variables are specialized according to the rule
$$ \begin{align} \Big\{ z_a = z_{a-1} t_a \Big\}_{a \in \{1,\dots,k\}} \end{align} $$
(in the notation of Equation (1.11)) for any face F of Q. This yields the following result.
Corollary 1.18. If Q is shrubby, the images of
$\iota $
and
$\widetilde {\Upsilon }^+$
coincide, that is, the localized K-theoretic Hall algebra surjects onto the subspace
${\mathcal {S}}^+ \subset {\mathcal {V}}^+$
of Laurent polynomials which vanish when their variables are specialized to (1.17), for any face F.
Proof. The fact that the image of
$\widetilde {\Upsilon }^+$
is (tautologically) generated by
$\{z_{i1}^d\}_{i \in I, d\in {\mathbb {Z}}}$
, which all lie in the image of
$\iota $
, implies that
$$ \begin{align} \text{Im } \widetilde{\Upsilon}^+ \subseteq \text{Im }\iota. \end{align} $$
To prove the opposite inclusion, one needs to show that the image of
$\iota $
is contained in the subspace of Laurent polynomials which vanish when their variables are specialized according to Equation (1.17) for every face F. This is achieved by noting that the specialization in question can be realized as restriction to the locally closed subset Z of quiver representations
$(\phi _{e} : {\mathbb {C}}^{n_i} \rightarrow {\mathbb {C}}^{n_j})_{e = \overrightarrow {ij}}$
whose only nonzero elements are
$$ \begin{align*}\phi_{\overrightarrow{i{}_1i{}_2}} \in {\mathbb{C}}^* E_{\bullet{}_{1}\bullet{}_{2}}, \dots, \phi_{\overrightarrow{i{}_{k-1}i_k}} \in {\mathbb{C}}^* E_{\bullet{}_{k-1}\bullet{}_k} \end{align*} $$
(where
$E_{ab}$
denote the matrix units with respect to the standard basis of
$\{{\mathbb {C}}^{n_i}\}_{i \in I}$
, and the natural numbers
$\bullet _1,\dots ,\bullet _k$
are chosen as in Equation (2.9)). Since the locally closed subset Z does not intersect the critical locus of W (on which
$K(Q,W)$
is supported), this implies the opposite inclusion to Equation (1.18)
$$ \begin{align} \text{Im } \widetilde{\Upsilon}^+ \supseteq \text{Im }\iota. \end{align} $$
1.19
The structure of the present paper is the following.
-
• In Section 2, we discuss
${\widetilde {\mathbf {U}}^+}$
and its shuffle algebra interpretation for general quivers Q. -
• In Section 3, we study
${\widetilde {\mathbf {U}}^+}$
for the particular quivers Q of Definition 1.3 and prove Theorem 1.13. -
• In Section A, we provide some key results on shrubs (which are certain subgraphs of the universal cover of Q that we use in the proof of Theorem 1.13).
1.20
I would like to thank Ben Davison, Richard Kenyon and Masahito Yamazaki for very useful conversations about the topics in the present paper. I gratefully acknowledge NSF grant DMS-
$1845034$
, as well as support from the MIT Research Support Committee.
2 Shuffle algebras in general
We will now recall the basic theory of trigonometric shuffle algebras, in the generality of [Reference Neguţ11]. Thus, throughout the present section, Q will denote an arbitrary quiver (whose vertex and edge sets will be denoted by I and E, respectively),
${\mathbb {K}}$
will denote an arbitrary field of characteristic zero, and
$\zeta _{ij}(x)(1-x)^{\delta _{ij}}$
will denote arbitrary Laurent polynomials with coefficients in
${\mathbb {K}}$
for all
$i,j \in I$
. Throughout the present paper, the set
${\mathbb {N}}$
will be thought to contain 0.
2.1
Let us consider an infinite collection of variables
$z_{i1},z_{i2},\dots $
for all
$i \in I$
. For any
$\boldsymbol {n} = (n_i)_{i \in I} \in {{{\mathbb {N}}}}^I$
, we will write
$\boldsymbol {n}! = \prod _{i \in I} n_i!$
. The following construction is a straightforward generalization of the trigonometric quantum loop groups of [Reference Enriquez2, Reference Feigin and Odesski3].
Definition 2.2. The big shuffle algebra associated to the datum
$\{\zeta _{ij}(x)\}_{i,j \in I}$
is
$$ \begin{align*}{\mathcal{V}}^+ = \bigoplus_{\boldsymbol{n} \in {\mathbb{N}}^I} {\mathbb{K}}[z_{i1}^{\pm 1},\dots,z_{in_i}^{\pm 1}]_{i \in I}^{\mathrm{sym}} \end{align*} $$
endowed with the multiplication
$$ \begin{align} R(\dots,z_{i1},\dots,z_{in_i},\dots) * R'(\dots,z_{i1},\dots,z_{in_i'},\dots ) = \end{align} $$
$$ \begin{align*}\mathrm{Sym} \left[ \frac {R(\dots,z_{i1},\dots,z_{in_i},\dots) R'(\dots,z_{i,n_i+1},\dots,z_{i,n_i+n_i'},\dots)}{\boldsymbol{n}! \boldsymbol{n}'!} \mathop{\prod^{i,j \in I}_{1\leq a\leq n_i}}_{n_j < b \leq n_j+n_j'} \zeta_{ij} \left(\frac {z_{ia}}{z_{jb}} \right) \right]. \end{align*} $$
Above and henceforth, ‘sym’ (resp. ‘Sym’) denotes symmetric functions (resp. symmetrization) with respect to the variables
$z_{i1},z_{i2},\dots $
for each
$i \in I$
separately.Footnote
6
By defining the subspace
${\mathcal {V}}_{\boldsymbol {n}} \subset {\mathcal {V}}^+$
to consist of rational functions in
$\boldsymbol {n} = (n_i)_{i \in I}$
variables, we obtain a decomposition
$$ \begin{align} {\mathcal{V}}^+ = \bigoplus_{\boldsymbol{n} \in {{{\mathbb{N}}}}^I} {\mathcal{V}}_{\boldsymbol{n}}. \end{align} $$
For example, the Laurent polynomial in a single variable
$z_{i1}^d$
lies in
${\mathcal {V}}_{{\boldsymbol {\varsigma }}^i}$
, where
$$ \begin{align*}{\boldsymbol{\varsigma}}^i = (\underbrace{0,\dots,0,1,0,\dots,0}_{1\text{ on }i\text{-th position}}) \in {{{\mathbb{N}}}}^I. \end{align*} $$
We will also consider the opposite big shuffle algebra
${\mathcal {V}}^- = {\mathcal {V}}^{+,\text {op}}$
, whose graded components analogous to Equation (2.2) will be denoted by
${\mathcal {V}}_{-\boldsymbol {n}}$
, for all
$\boldsymbol {n} \in {{{\mathbb {N}}}}^I$
.
2.3
Recall that
${\widetilde {\mathbf {U}}^+}$
is the quiver quantum toroidal algebra of Definition 1.10, and
${\widetilde {\mathbf {U}}^-}$
denotes its opposite. There exist
${\mathbb {K}}$
-algebra homomorphisms
$$ \begin{align} {\widetilde{\mathbf{U}}^\pm} \xrightarrow{\widetilde{\Upsilon}^\pm} {\mathcal{V}}^{\pm}, \qquad e_{i,d}, f_{i,d} \mapsto z_{i1}^d \end{align} $$
which can be easily established by checking the fact that relations (1.5) are respected by the shuffle product (2.1). Let us consider the kernel and image of the maps (2.3)
$$ \begin{align} &K^\pm = \text{Ker } \widetilde{\Upsilon}^\pm \subset {\widetilde{\mathbf{U}}^\pm} \end{align} $$
$$ \begin{align} &\mathring{{\mathcal{S}}}^\pm = \ \text{Im } \widetilde{\Upsilon}^\pm \ \subset {\mathcal{V}}^\pm. \end{align} $$
The subalgebra
$\mathring {{\mathcal {S}}}^+$
will be called the shuffle algebra to differentiate it from the big shuffle algebra of Definition 2.2.
2.4
An important role in the present paper will be played by a certain integral pairing, which we will now describe. Let us consider the following notation for all rational functions
$f(z_1,\dots ,z_n)$
. If
$Dz_a = \frac {dz_a}{2\pi i z_a}$
, then we will write
$$ \begin{align} \int_{|z_1| \gg \dots \gg |z_n|} f(z_1,\dots,z_n) \prod_{a=1}^n Dz_a \end{align} $$
for the constant term in the expansion of f as a power series in
$$ \begin{align*}\frac {z_2}{z_1}, \dots, \frac {z_n}{z_{n-1}}. \end{align*} $$
The notation in Equation (2.6) is motivated by the fact that if
${\mathbb {K}} = {\mathbb {C}}$
, one could compute this constant term as a contour integral (with the contours being concentric circles, situated very far from each other compared to the absolute values of the coefficients of f).
Definition 2.5. There exists a nondegenerate bilinear pairingFootnote 7
$$ \begin{align} {\widetilde{\mathbf{U}}^+} \otimes {\mathcal{V}}^- \xrightarrow{\langle \cdot, \cdot \rangle} {\mathbb{K}} \end{align} $$
given for all
$R \in {\mathcal {V}}_{-\boldsymbol {n}}$
and all
$i_1,\dots ,i_n \in I$
,
$d_1,\dots ,d_n \in {\mathbb {Z}}$
by
$$ \begin{align} \Big \langle e_{i_1,d_1} \cdots e_{i_n,d_n}, R \Big \rangle = \int_{|z_1| \gg \dots \gg |z_n|} \frac {z_1^{d_1}\dots z_n^{d_n} R(z_1,\dots,z_n)}{\prod_{1\leq a < b \leq n} \zeta_{i_bi_a} \left(\frac {z_b}{z_a} \right)} \prod_{a=1}^n Dz_a \end{align} $$
if
${\boldsymbol {\varsigma }}^{i_1}+\dots +{\boldsymbol {\varsigma }}^{i_n} = \boldsymbol {n}$
, and 0 otherwise. In the right-hand side of Equation (2.8), we identify
$$ \begin{align} z_a \quad \text{with} \quad z_{i{}_a\bullet{}_a}, \quad \forall a \in \{1,\dots, n\}, \end{align} $$
where
$\bullet _a \in \{1,2,\dots ,n_{i{}_a}\}$
may be chosen arbitrarily due to the symmetry of R (however, we require
$\bullet _a \neq \bullet _b$
if
$a\neq b$
and
$i_a = i_b$
). We will call Equation (2.9) a relabeling.
There is also an analogous pairing
$$ \begin{align} {\mathcal{V}}^+ \otimes {\widetilde{\mathbf{U}}^-} \xrightarrow{\langle \cdot, \cdot \rangle} {\mathbb{K}} \end{align} $$
whose formula the interested reader may find in [Reference Neguţ11, Definition 2.8]. We refer to formulas (2.17), (2.18) and (3.59) of loc. cit. for the proof of nondegeneracy.
2.6
Let
${\mathcal {S}}^\mp \subset {\mathcal {V}}^\mp $
denote the dual of
$K^\pm = \text {Ker }\widetilde {\Upsilon }^\pm $
under the pairings (2.7) and (2.10), respectively, that is,
$$ \begin{align} &R^- \in {\mathcal{S}}^- \quad \Leftrightarrow \quad \Big \langle K^+, R^- \Big \rangle = 0 \end{align} $$
$$ \begin{align} &R^+ \in {\mathcal{S}}^+ \quad \Leftrightarrow \quad \Big \langle R^+, K^- \Big \rangle = 0. \end{align} $$
It is easy to check that
${\mathcal {S}}^\pm $
are subalgebras of
${\mathcal {V}}^{\pm }$
(in fact, this also follows from the fact that Equations (2.7) and (2.10) yield bialgebra pairings). Thus, we have
$$ \begin{align*}\mathring{{\mathcal{S}}}^\pm \subseteq {\mathcal{S}}^\pm \qquad \qquad \end{align*} $$
because the generators
$\{z_{i1}^d\}_{i \in I, d\in {\mathbb {Z}}}$
of the algebras on the left lie in the algebras on the right. Moreover, if we consider the reduced quiver quantum toroidal algebra
$$ \begin{align*}\mathbf{U}^\pm = {\widetilde{\mathbf{U}}^\pm} \Big / K^\pm, \end{align*} $$
then the pairings (2.7) and (2.10) descend to nondegenerate pairings
$$ \begin{align} &\mathbf{U}^+ \otimes {\mathcal{S}}^- \xrightarrow{\langle \cdot, \cdot \rangle} {\mathbb{K}} \end{align} $$
$$ \begin{align} &{\mathcal{S}}^+ \otimes \mathbf{U}^- \xrightarrow{\langle \cdot, \cdot \rangle} {\mathbb{K}}. \end{align} $$
One of the main results of [Reference Neguţ11] (specifically, Theorem 1.5 therein) is the following.
Theorem 2.7. We have
${\mathcal {S}}^\pm = \mathring {{\mathcal {S}}}^\pm $
, and hence
$\widetilde {\Upsilon }^\pm $
induce isomorphisms
$$ \begin{align} \mathbf{U}^\pm \xrightarrow{\Upsilon^\pm} {\mathcal{S}}^\pm. \end{align} $$
Moreover, the pairings (2.13) and (2.14) match under these isomorphisms, thus yielding a nondegenerate pairing
$$ \begin{align} {\mathcal{S}}^+ \otimes {\mathcal{S}}^- \xrightarrow{\langle \cdot, \cdot \rangle} {\mathbb{K}}. \end{align} $$
We wish to describe
$\mathbf {U}^\pm $
explicitly, that is, to give formulas for a system of generators of the kernel
$K^\pm $
of the map
${\widetilde {\mathbf {U}}^\pm } \twoheadrightarrow \mathbf {U}^\pm $
. By formulas (2.11)–(2.12), these sought-for generators are precisely dual to the linear conditions describing the inclusions
${\mathcal {S}}^\mp \subset {\mathcal {V}}^\mp $
. We will exploit this duality in the following Section.
3 Shuffle algebras for shrubby quivers
From now onward, we will consider the special case when Q is a quiver drawn on the torus, as in Definition 1.3. Moreover, we assume the edges of Q are endowed with parameters
$t_e$
as in Subsection 1.6, and we define the rational functions
$\zeta _{ij}(x)$
by formula (1.3). Our goal is to obtain explicit generators of the ideals
$K^\pm $
so that we may realize the reduced quiver quantum toroidal algebras
$\mathbf {U}^\pm $
as being determined by explicit relations. In what follows, we will only focus on the case
$\pm = +$
, as the opposite case
$\pm = -$
can be obtained by reversing all products.
3.1
In Definition 3.2, we will construct formal series
$e_F$
of elements of
$K^+$
associated to the faces of the quiver Q. When the quiver Q is shrubby (in the sense of Definition 1.5), we will show that the coefficients of the series
$e_F$
generate
$K^+$
, thus concluding the proof of Theorem 1.13. For every face
$F = \{i_0,i_1,\dots ,i_{k-1},i_k=i_0\}$
of Q, consider
$$ \begin{align} t_a = t_{\overrightarrow{i_{a-1}i_a}}, \end{align} $$
and note that
$t_1\dots t_k = 1$
due to Equation (1.1). The arrows in Equation (3.1) are the boundary edges of the face F (these edges are uniquely defined, even though it is possible that Q has multiple edges between
$i_a$
and
$i_b$
for various
$ a \neq b$
). We will write
$$ \begin{align} \widetilde{\zeta}_{ij}(x) = \zeta_{ij}(x) (1-x)^{\delta_{ij}} \in {\mathbb{K}}[x^{\pm 1}] \end{align} $$
for all
$i,j \in I$
. For any
$1 \leq b \neq c \leq k$
, we will write
$$ \begin{align*} &\delta_{b<c} = \begin{cases} 1 &\text{if } b < c \\ 0 &\text{if } b>c \end{cases} \\ &\delta_{i_bi_c} = \begin{cases} 1 &\text{if } i_b=i_c \in I \\ 0 &\text{otherwise}. \end{cases} \end{align*} $$
Definition 3.2. For any face F as above, consider the formal series
$$ \begin{align} & e_F(x_1,\dots,x_k) = \sum_{a=1}^k \frac {x_1t_2\dots t_a}{x_a} \cdot \frac { \prod_{b \succ c} \widetilde{\zeta}_{i_ci_b} \left(\frac {x_c}{x_b} \right)\left( - \frac {x_b}{x_c} \right)^{\delta_{i_bi_c} \delta_{b<c}} }{\prod_{b \sim c + 1} \left(1 - \frac {x_ct_b}{x_b} \right)} \cdot \nonumber\\ & \qquad\cdot e_{i_{a}}(x_{a}) \dots e_{i_1}(x_1) e_{i_k}(x_k) \dots e_{i_{a+1}}(x_{a+1}) \quad \in \quad {\widetilde{\mathbf{U}}^+}[[x_1^{\pm 1}, \dots, x_k^{\pm 1}]]. \end{align} $$
In expression (3.3), the notation
$b \succ c$
(respectively
$b \sim c+1$
) means that b precedes (respectively immediately precedes) c in the sequence
$(a,\dots ,1,k,\dots ,a+1)$
.
Proposition 3.3. The coefficients of the series (3.3) all lie in
$K^+$
.
Proof. Let us consider the formal delta series
$$ \begin{align*}\delta\left(z \right) = \sum_{d \in {\mathbb{Z}}} z^d \end{align*} $$
which has the following property for all Laurent polynomials
$f(x)$
$$ \begin{align} \delta \left( \frac zx \right) f(z) = \delta \left( \frac zx \right) f(x). \end{align} $$
To prove Proposition 3.3, we must apply the map
$\widetilde {\Upsilon }^+$
to the right-hand side of Equation (3.3) and show that the result is 0. By the definition of the shuffle product in Equation (2.1), we have
$$ \begin{align*} & \widetilde{\Upsilon}^+ \left( e_F(x_1,\dots,x_k) \right) = \textrm{Sym} \left[ \sum_{a=1}^k \frac {x_1t_2\dots t_a}{x_a} \cdot \right. \\ & \left. \frac { \prod_{b \succ c} \widetilde{\zeta}_{i_ci_b} \left(\frac {x_c}{x_b} \right) \prod_{b < c, b \succ c} \left(- \frac {x_b}{x_c} \right)^{\delta_{i_bi_c}} \prod_{c \succ b} \zeta_{i_ci_b} \left(\frac {z_c}{z_b} \right)}{\prod_{b \sim c + 1} \left(1 - \frac {x_ct_b}{x_b} \right)} \cdot \delta\left(\frac {z_1}{x_1} \right) \dots \delta\left(\frac {z_k}{x_k} \right) \right] \stackrel{(3.4)}= \end{align*} $$
$$ \begin{align*} & \qquad \qquad \qquad \qquad \quad \stackrel{(3.4)}= \textrm{Sym} \left[ \sum_{a=1}^k \frac {z_1t_2\dots t_a}{z_a} \cdot \right. \\ & \left. \frac { \prod_{b \succ c} \widetilde{\zeta}_{i_ci_b} \left(\frac {z_c}{z_b} \right) \prod_{b < c, b \succ c} \left(- \frac {z_b}{z_c} \right)^{\delta_{i_bi_c}} \prod_{c \succ b} \zeta_{i_ci_b} \left(\frac {z_c}{z_b} \right)}{\prod_{b \sim c + 1} \left(1 - \frac {z_ct_b}{z_b} \right)} \cdot \delta\left(\frac {z_1}{x_1} \right) \dots \delta\left(\frac {z_k}{x_k} \right) \right] = \end{align*} $$
$$ \begin{align*}= \textrm{Sym} \left[ \sum_{a=1}^k \frac {z_1t_2\dots t_a}{z_a} \cdot \frac { \prod_{1 \leq b \neq c \leq k} \zeta_{i_ci_b} \left(\frac {z_c}{z_b} \right) \prod_{b> c, i_b = i_c} \left(1 - \frac {z_c}{z_b} \right)}{\prod_{b \sim c + 1} \left(1 - \frac {z_ct_b}{z_b} \right)} \cdot \delta\left(\frac {z_1}{x_1} \right) \dots \delta\left(\frac {z_k}{x_k} \right) \right], \end{align*} $$
where we let
$z_a = z_{i_a\bullet _a}$
as in the relabeling (2.9), and ‘Sym’ refers to symmetrization with respect to all
$z_a$
and
$z_b$
such that
$i_a = i_b$
. Therefore,
$\widetilde {\Upsilon }^+ (e_F)$
equals
$$ \begin{align} & \textrm{Sym} \left[ \frac { \prod_{1 \leq b \neq c \leq k} \zeta_{i_ci_b} \left(\frac {z_c}{z_b} \right) \prod_{b> c, i_b = i_c} \left(1 - \frac {z_c}{z_b} \right)}{\left(1 - \frac {z_1t_2}{z_2} \right)\dots \left(1 - \frac {z_{k-1}t_k}{z_k} \right)\left(1 - \frac {z_kt_1}{z_1} \right) } \cdot \right. \nonumber\\ & \qquad\qquad\qquad\qquad\quad\left. \delta\left(\frac {z_1}{x_1} \right) \dots \delta\left(\frac {z_k}{x_k} \right) \sum_{a=1}^k \frac {z_1t_2\dots t_a}{z_a} \left(1 - \frac {z_a t_{a+1}}{z_{a+1}} \right) \right], \end{align} $$
where
$z_{k+1}=z_1$
. As
$t_1\dots t_k = 1$
, the sum in Equation (3.5) vanishes, hence so does
$\widetilde {\Upsilon }^+ (e_F)$
.
3.4
We will now consider the dual to the series
$e_F(x_1,\dots ,x_k) \in {\widetilde {\mathbf {U}}^+}[[x_1^{\pm 1}, \dots , x_k^{\pm 1}]]$
under the pairing (2.7). We still write F for an arbitrary face of Q.
Proposition 3.5. For anyFootnote
8
$R(z_1,\dots ,z_k) \in {\mathcal {V}}_{-{\boldsymbol {\varsigma }}^{i_1}-\dots -{\boldsymbol {\varsigma }}^{i_k}}$
, we have
$$ \begin{align} \Big\langle e_F(x_1,\dots,x_k), R \Big \rangle = 0 \qquad \Leftrightarrow \qquad R\Big|_{z_a = z_{a-1} t_a, \forall a \in \{1,\dots,k\}} = 0. \end{align} $$
Proof. As a consequence of Equation (2.8), we have
$$ \begin{align} \Big\langle e_F(x_1,\dots,x_k), R \Big \rangle = \end{align} $$
$$ \begin{align*}= \sum_{a=1}^k \textrm{ev}_{|x_a| \gg \dots \gg |x_1| \gg |x_k| \gg \dots \gg |x_{a+1}|} \left[ \frac {x_1t_2\dots t_a}{x_a} \cdot \frac {R(x_1,\dots,x_k) \prod_{b>c}^{i_b = i_c} \left(1-\frac {x_c}{x_b}\right) }{\prod_{b \sim c + 1} \left(1 - \frac {x_ct_b}{x_b} \right)} \right], \end{align*} $$
where
$\textrm {ev}_{\star }[f]$
denotes the expansion of any rational function f in the region prescribed by the inequalities
$\star $
. Using the fact that
$t_1\dots t_k=1$
, it is elementary to prove the following identity of formal series
$$ \begin{align*}\sum_{a=1}^k \textrm{ev}_{|x_a| \gg \dots \gg |x_1| \gg |x_k| \gg \dots \gg |x_{a+1}|} \left[ \frac {\frac {x_1t_2\dots t_a}{x_a}}{\prod_{b \sim c + 1} \left(1 - \frac {x_ct_b}{x_b} \right)} \right] = \delta\left(\frac {x_1t_2}{x_2} \right) \dots \delta\left( \frac {x_{k-1}t_k}{x_k} \right). \end{align*} $$
Therefore, the right-hand side of Equation (3.7) is equal to
$$ \begin{align*}\delta\left(\frac {x_1t_2}{x_2} \right) \dots \delta\left( \frac {x_{k-1}t_k}{x_k} \right) R(x_1,\dots,x_k) \prod_{b>c}^{i_b = i_c} \left(1-\frac {x_c}{x_b}\right) \end{align*} $$
and vanishes if and only if
$$ \begin{align} R\Big|_{z_a = z_{a-1}t_a, \forall a\in \{1,\dots,k\}} \prod_{b>c}^{i_b = i_c} \left(1-\frac 1{t_{c+1} \dots t_{b}}\right) = 0. \end{align} $$
Because of Equation (1.2), we cannot have
$t_{c+1}\dots t_b = 1$
for any
$b> c$
with
$i_b=i_c$
, and therefore, Equation (3.8) only holds if
$R|_{z_a = z_{a-1}t_a, \forall a\in \{1,\dots ,k\}}= 0$
, as we needed to show.
More generally, if
$R(z_1,\dots ,z_n,\dots ) \in {\mathcal {V}}^-$
is arbitrary, then
$$ \begin{align} \Big\langle {\widetilde{\mathbf{U}}^+} e_F(x_1,\dots,x_k) {\widetilde{\mathbf{U}}^+}, R \Big \rangle = 0 \qquad \Leftrightarrow \qquad R\Big|_{z_a = z_{a-1}t_a, \forall a \in \{1,\dots,k\}} = 0, \end{align} $$
where
$z_a$
denotes any variable of R of the form
$z_{i_a\bullet _a}$
, for all
$a \in \{1,\dots ,k\}$
(the choice of
$\bullet _a$
does not matter due to the symmetry of R). Implicit in the notation above is that R may have other variables besides
$z_1,\dots ,z_n$
, and these are not specialized at all. Property (3.9) is proved like [Reference Neguţ12, Proposition 3.13]; we leave the details as an exercise to the reader.
3.6
Motivated by Proposition 3.5 and Equation (3.9), we consider the following.
Definition 3.7. Let 
denote the subspace consisting of Laurent polynomials
$R(z_1,\dots ,z_k,\dots )$
such that
$$ \begin{align} R\Big|_{z_a = z_{a-1}t_a, \forall a \in \{1,\dots,k\}} = 0 \end{align} $$
for any face
$F = \{i_0,i_1,\dots ,i_{k-1},i_k=i_0\}$
of Q (the notation
$t_a$
is that of Equation (3.1)).
We call Equation (3.10) a wheel condition by analogy with the constructions of [Reference Enriquez2, Reference Feigin and Odesski3]. It is straightforward to show that 
are closed under the shuffle product, although this will also follow from Proposition 3.10. Thus, if we consider the two-sided ideal
$$ \begin{align*}J^+ = \Big(\text{series coefficients of }e_F(x_1,\dots,x_k) \Big)_{F \text{ face of }Q} \subset {\widetilde{\mathbf{U}}^+}, \end{align*} $$
then property (3.9) reads
Remark 3.8. Property (3.11) would still hold if we defined
$J^+$
as the ideal generated by a single coefficient of the series
$e_F(x_1,\dots ,x_k)$
of every given homogeneous degree in
$x_1,\dots ,x_k$
, for all faces F of the quiver Q. In other words, including all the coefficients of all the series
$e_F$
as generators of
$J^+$
is superfluous; a single coefficient of each homogeneous degree for all faces F would suffice (see [Reference Neguţ11, Claim 3.18] or [Reference Neguţ12, Remark 3.14]).
3.9
Proposition 3.3 implies that
$J^+ \subseteq K^+$
, and therefore
Our main goal for the remainder of the paper is to prove the opposite inclusion.
. We also have 
; the proof is analogous and we will not repeat it.
Proof. Proof of Theorem 1.13.
With Equations (2.11) and (3.11) in mind, the fact that 
implies that
$$ \begin{align*}\Big\langle K^+, R \Big \rangle = 0 \quad \Leftrightarrow \quad \Big\langle J^+, R \Big \rangle = 0 \end{align*} $$
for any
$R \in {\mathcal {V}}^-$
. If Equation (2.7) were a pairing of finite-dimensional vector spaces over
${\mathbb {K}}$
, this would imply that
$J^+ = K^+$
and we would be done. In the infinite-dimensional setting at hand, one needs to emulate the proof of [Reference Neguţ11, Theorem 1.8] to conclude that
$J^+ = K^+$
. The details are straightforward, and we leave them to the reader.
3.11
Assume that Q is shrubby, according to Definition 1.5, and let
$\widetilde {Q}$
be its universal cover. The following notion will be key to our proof of Proposition 3.10.
Definition 3.12. A preshrub S is an subgraph of
$\widetilde {Q}$
which does not contain the entire boundary of any face, and moreover has the property that if S contains a broken wheel then it must also contain its mirror image.
Proposition 3.13. A preshrub cannot contain any cycles.
The proposition above will be proved in the appendix. Although a preshrub cannot contain any oriented cycles, it can contain unoriented ones (for example, a broken wheel together with its mirror image). The interior of a preshrub S is the region completely enclosed by the unoriented cycles belonging to S.
Recall that any oriented graph with no cycles yields a partial order on the set of its vertices, with
$i>j$
if there exists a path in the graph from i to j. Having established that preshrubs do not contain any cycles in Proposition 3.13, we may consider the corresponding partial order on the set of vertices. With respect to this order, a root of a preshrub will refer to a maximal vertex.
Definition 3.14. A shrub S is a preshrub with a single root, which contains all the vertices in its interior. We identify shrubs up to deck transformations of
$\widetilde {Q}$
over Q.
The identification of shrubs can also be visualized by fixing a vertex
$\tilde {i} \in \widetilde {Q}$
for every
$i \in Q$
; then we may simply restrict attention to shrubs that are rooted at a vertex in
$\{\tilde {i}| i \in Q\}$
. The following proposition will also be proved in the appendix.
Proposition 3.15. If
$i,i'$
are vertices of a shrub S and
$i \xrightarrow {e} i'$
is an edge not contained in S, then e must be the interface of a broken wheel contained in S.
3.16
Consider a shrub
$S \subset \widetilde {Q}$
and a vertex
$i \notin S$
. Assume that there are
$k>0$
edges from vertices of S to i, labeled
$e_1,\dots ,e_k$
in counterclockwise order around i, as in Figures 3 and 4. The difference between these figures will be explained in Definition 3.19 when we discuss the notion of i being addable or nonaddable to S.
Figure 3 An addable vertex i (in black) to a shrub S (in red).
Figure 4 Two situations of nonaddable vertices i (in black) to a shrub S (in red).
In the situation above, consider any two consecutive edges
$e_s$
and
$e_{s+1}$
(we make the convention that
$e_{k+1} = e_1$
). Because S is a shrub (and thus has a root), we may continue these edges in S until they meet, thus yielding paths
$$ \begin{align} &p_s : j \rightarrow \dots \xrightarrow{e_s} i \end{align} $$
$$ \begin{align} &p^{\prime}_s : j \rightarrow \dots \xrightarrow{e_{s+1}} i. \end{align} $$
We may assume the paths
$p_s$
and
$p_s'$
are simple, nonintersecting (except for the endpoints) and that the region
$r_s$
of the plane between
$p_s$
and
$p_s'$
is minimal with respect to inclusion; this guarantees the uniqueness of
$p_s,p_s',r_s$
since the intersection of two minimal regions thus constructed would yield an even smaller acceptable region. Because the vertex i does not belong to the interior of the shrub, a single one of the regions
$r_s$
does not contain the counterclockwise angle at i between
$e_s$
and
$e_{s+1}$
. By relabeling the edges if necessary, we assume that the aforementioned region is
$r_k$
. With this in mind, an index
$s\in \{1,\dots ,k-1\}$
is called
-
• good if
$p_s$
and
$p^{\prime }_s$
are broken wheels, which are mirror images of each other -
• bad if there exist edges
$i \xrightarrow {e} v \in p_s$
and
$i \xrightarrow {e'} v' \in p^{\prime }_s$
with
$v,v' \neq j$
such that the subregions of
$r_s$
between e and
$p_s$
(respectively between
$e'$
and
$p^{\prime }_s$
) are faces
For example, both
$s \in \{1,2\}$
in Figure 3 are good. However, in the picture on the left of Figure 4,
$s = 1$
is bad and
$s = 2$
is good. Meanwhile, we call the index
$s = k$
-
• good if there are no edges from i to S in the counterclockwise region from
$e_k$
to
$e_1$
(i.e., the region
${\mathbb {R}}^2 \backslash r_k$
); this is the case in Figure 3. -
• bad if there exists an edge from i to S in the region
${\mathbb {R}}^2 \backslash r_k$
, which determines a face together with the other edges in S and exactly one of the edges
$e_1$
and
$e_k$
; this is the case in the picture on the right of Figure 4.
The following result will be proved in the appendix.
Proposition 3.17. For
$i \notin S$
as above, every
$s \in \{1,\dots ,k\}$
is either good or bad.
3.18
If S is a shrub and
$i \notin S$
, let
$S+i$
denote the subgraph obtained from S by adding the vertex i and the edges from S to i (we assume such edges exist).
Definition 3.19. In the situation above, we call i addable to S if all
$s \in \{1,\dots ,k\}$
are good, and nonaddable to S otherwise.
Figures 3 and 4 provide examples of addable and nonaddable vertices. The terminology above is motivated by the following result, which will be proved in the appendix.
Proposition 3.20. Assume
$S \subset \widetilde {Q}$
is a shrub and
$i \notin S$
is a vertex. Then
$S+i$
is a shrub if and only if i is an addable vertex to S.
The main distinction to us between addable and nonaddable vertices is the following result, which will also be proved in the appendix.
Proposition 3.21. Assume
$S \subset \widetilde {Q}$
is a shrub and
$i \notin S$
is a vertex with
$k> 0$
edges from S to i. The maximal number of broken wheels in
$S+i$
that all pass through i and do not pairwise intersect at any other vertex is
$$ \begin{align*}\begin{cases} k-1 &\text{if }i\text{ is addable to }S \\ \geq k &\text{otherwise}. \end{cases} \end{align*} $$
3.22
We are now ready to give the proof of Proposition 3.10. Since we are operating under Assumption 1.7, we will assume throughout the present Subsection that the edge parameters
$t_e$
are nonzero complex numbers (i.e., abuse notation by writing
$t_e$
instead of
$\rho (t_e)$
, where
$\rho : {\mathbb {K}} \rightarrow {\mathbb {C}}$
is a field homomorphism). This assumption is merely cosmetic, as all our formulas are rational functions in the
$t_e$
’s.
Proof. Proof of Proposition 3.10.
Let us consider any
$$ \begin{align*}\phi = \mathop{\sum_{i_1,\dots,i_n \in I}}_{d_1,\dots,d_n \in {\mathbb{Z}}} \text{coefficient} \cdot e_{i_1,d_1} \dots e_{i_n,d_n} \in K^+ \end{align*} $$
and any 
. Our goal is to show that
$$ \begin{align} \Big \langle \phi, R \Big \rangle = 0 \end{align} $$
as this would imply the required
$R \in {\mathcal {S}}^-$
. Recall from formula (2.8) that
$$ \begin{align} \Big \langle e_{i_1,d_1} \cdots e_{i_n,d_n}, R \Big \rangle = \int_{|z_1| \gg \dots \gg |z_n|} f(z_1,\dots,z_n) \prod_{a=1}^n Dz_a, \end{align} $$
where
$$ \begin{align} f(z_1,\dots,z_n) = \frac {z_1^{d_1}\dots z_n^{d_n} R(z_1,\dots,z_n)}{\prod_{1\leq a < b \leq n} \zeta_{i_bi_a} \left(\frac {z_b}{z_a} \right)}. \end{align} $$
A labeling of a shrub
$S \subset \widetilde {Q}$
will refer to a labeling of the s vertices of S by one of the variables
$z_{a_1},\dots ,z_{a_s}$
(for certain
$a_1<\dots <a_s \in {\mathbb {N}}$
) such that the increasing order of the indices of the variables refines the partial order on the vertices given by the shrub, that is,
$a_x < a_{x'}$
if the corresponding vertices
$i_x, i_{x'} \in S$
are connected in S by a path going from
$i_{x'}$
to
$i_x$
. In particular, the root of S must be labeled by the variable
$z_{a_s}$
. For every
$x \in \{1,\dots ,s-1\}$
, choose a path from the root
$i_s$
to
$i_x$
$$ \begin{align*}i_s \xrightarrow{\alpha} i_{s'} \xrightarrow{\beta} \dots \xrightarrow{\omega} i_x, \end{align*} $$
and define
$q_x = t_\alpha t_{\beta }\dots t_{\omega }$
. Because such paths are unique up to removing cycles or replacing a broken wheel by its mirror image (according to Definition 1.5), and because such removals/replacements do not change the product of parameters along the path, the quantity
$q_x$
does not depend on any choices made. An acceptable labeled shrub is one for which
$|q_x|> 1$
for all
$x \in \{1,\dots ,s-1\}$
(note that the situation of
$p'$
being the empty path in (1.2) precludes
$|q_x| = 1$
).
Proposition 3.23. For any labeled shrub S and function f as in Equation (3.18) with at least as many variables as vertices of S (corresponding to any
$i \in I$
), define
$$ \begin{align} \mathop{\mathrm{Res}}_S f \end{align} $$
as a function in
$\{z_a\}_{a \notin \{a_1,\dots ,a_{s-1}\}}$
by the following iterated residue procedure.
At step number
$x \in \{1,\dots ,s-1\}$
, the variables
$z_{a_{s-x+1}},\dots ,z_{a_{s-1}}$
have all been specialized to
$z_{a_s}$
times
$q_{s-x+1},\dots ,q_{s-1}$
, respectively. Upon this specialization, we claim that the rational function f has at most a simple pole at
$$ \begin{align} z_{a_{s-x}} = z_{a_s} q_{s-x}. \end{align} $$
Replace f by its residue at the pole (3.20), and move on to step number
$x+1$
.
Because one only encounters simple poles in the algorithm above, the value of Equation (3.19) would not change if we replaced (in the recursive procedure of Proposition 3.23) the total order
$a_1 < \dots < a_s$
by any other total order refining the partial order on the vertices of the shrub.
Proof. Consider the induced subgraph
$S' \subset S$
consisting of all vertices
$>i:=i_{s-x}$
. It is easy to see that
$S'$
is a shrub and that i is an addable vertex to
$S'$
. Therefore, we may assume that the there are
$k> 0$
edges
$$ \begin{align*}i_{b_1} \xrightarrow{e_1} i_{s-x}, \dots, i_{b_k} \xrightarrow{e_k} i_{s-x} \end{align*} $$
from the shrub
$S'$
to the vertex i, for certain
$b_1,\dots ,b_k> s-x$
. Since these edges must be distributed as in Figure 3, the denominator of (3.18) includes the k factors
$$ \begin{align*}1 - \frac {z_{a_{b_1}} t_{e_1}}{z_{a_{s-x}}}, \dots, 1 - \frac {z_{a_{b_k}} t_{e_k}}{z_{a_{s-x}}}. \end{align*} $$
Once the variables
$z_{a_{b_1}},\dots ,z_{a_{b_k}}$
are specialized to
$z_{a_s}$
times
$q_{b_1},\dots , q_{b_k}$
, respectively, the fact that
$q_{s-x} = q_{b_1}t_{e_1} = \dots = q_{b_k}t_{e_k}$
implies that the denominator of (3.18) will feature the factor
$$ \begin{align*}\left(1 - \frac {z_{a_s} q_{s-x}}{z_{a_{s-x}}} \right)^k. \end{align*} $$
Thus, to prove that the pole invoked in the statement of the Proposition is at most simple, we need to show that the numerator of Equation (3.18) vanishes to order at least
$k-1$
at the specialization (3.20). However, the numerator of f vanishes whenever any subset of its variables are specialized according to Equation (3.10) for any face F. As there exist
$k-1$
broken wheels whose only common vertex is
$i = i_{s-x}$
(see Proposition 3.21), property (3.10) for the
$k-1$
faces enclosed by said broken wheels implies that the numerator of f vanishes to order
$\geq k-1$
at the specialization (3.20).Footnote
9
An m-labeled shrubbery
$\mathscr {S}$
is a disjoint union of labeled shrubs in
$\widetilde {Q}$
(whose
$n-m+1$
vertices are endowed with distinct labels among
$z_m,\dots ,z_n$
) such that the order of the indices of the variables refines the partial order on the vertices given by each constituent shrub of
$\mathscr {S}$
. An m-labeled shrubbery is called acceptable if all of its constituent shrubs are acceptable.
Claim 3.24. For any
$m \in \{1,\dots ,n\}$
, consider
$$ \begin{align} X_m = \sum^{m\text{-labeled acceptable}}_{\text{shrubberies }\mathscr{S} = S_1 \sqcup \dots \sqcup S_t} & \int_{|z_1| \gg \dots \gg |z_{m-1}|\gg |z_{r_1}| = \dots = |z_{r_t}|} \nonumber\\ & \qquad\qquad\quad \mathop{\mathrm{Res}}_{S_1} \dots \mathop{\mathrm{Res}}_{S_t} f \prod_{a=1}^{m-1} Dz_a \prod_{u = 1}^t Dz_{r_u}, \end{align} $$
where
$z_{r_1},\dots ,z_{r_t}$
are the labels of the roots of the shrubs
$S_1,\dots ,S_t$
. Then we have
$$ \begin{align} X_{m-1} = X_m \end{align} $$
for all
$m \in \{2,\dots ,n\}$
.
Note that there are finitely many m-labeled shrubberies due to the fact that shrubs that only differ by a deck transformation of
$\widetilde {Q}$
over Q are identified. The purpose of assumption (1.2) is to ensure that the specialization of the rational function f corresponding to the shrubbery
$\mathscr {S}$
, which has linear factors of the form
$$ \begin{align*}1 - \frac {z_{r_u} q_x t_e}{z_{r_v} q_y} \end{align*} $$
in the denominator (where e is any edge from any vertex
$i_x$
in the shrub
$S_u$
to any vertex
$i_y$
in the shrub
$S_v$
) has no poles on the circles
$|z_{r_u}| = |z_{r_v}|$
themselves.
Proof. To prove Equation (3.22), one needs to move the contour of the variable
$z_{m-1}$
toward the contours
$|z_{r_1}| = \dots = |z_{r_t}|$
. If the former contour reaches the latter contours, this corresponds to adding the one-vertex shrub
$\{i_{m-1}\}$
to the shrubbery
$\mathscr {S}$
. Otherwise, the variable
$z_{m-1}$
must be ‘caught’ in one of the poles of the form
$$ \begin{align} 1 - \frac {z_b t_{e}}{z_{m-1}} \end{align} $$
for some
$b> m-1$
and some edge
$e = \overrightarrow {i_b i_{m-1}}$
. Assume
$i_b$
belongs to one of the constituent shrubs
$S_u \subset \mathscr {S}$
, and suppose there is a number
$k> 0$
of edges from the shrub
$S_u$
to
$i = i_{m-1}$
. Then we have one of the following three possibilities.
-
• If the vertex i is addable to
$S_u$
as in Definition 3.19, then Proposition 3.20 implies that
$S_u' = S_u+i$
is a shrub. Thus, the operation shows how to obtain
$$ \begin{align*} m\text{-labeled shrubbery } & \mathscr{S} = S_1 \sqcup \dots \sqcup S_u \sqcup \dots \sqcup S_t \leadsto \\ & \leadsto (m-1)\text{-labeled shrubbery } \mathscr{S}' = S_1 \sqcup \dots \sqcup S^{\prime}_u \sqcup \dots \sqcup S_t \end{align*} $$
$X_{m-1}$
by applying the contour moving procedure to
$X_m$
(the fact that we only encounter acceptable shrubs is due to the fact that we move the contour of
$z_{m-1}$
from infinity down to the contour of
$z_{r_u}$
, but no further).
-
• If the vertex i is nonaddable to
$S_u$
, then Proposition 3.21 states that there exist k broken wheels completely contained in
$S_u + i$
that only intersect pairwise at the vertex i. As we have seen at the end of the proof of Proposition 3.23, this means that the numerator of f has enough factors to cancel the k copies of the factor (3.23) from the denominator of f. We conclude that nonaddable vertices do not correspond to actual poles. -
• If the vertex i is already in
$S_u$
(say with label
$z_c$
for some
$c> m-1$
), then the linear factor of
$z_{m-1}-z_c$
in the denominator of allows the numerator of f to annihilate the pole of the form (3.23).
$$ \begin{align*}\zeta_{i_ci_{m-1}} \left(\frac {z_c}{z_{m-1}}\right) \end{align*} $$
Repeated applications of Claim 3.24 imply the fact that
$X_1 = X_n$
. Since
$X_n$
is the right-hand side of Equation (3.17), we conclude that
$$ \begin{align} & \Big \langle e_{i_1,d_1} \cdots e_{i_n,d_n}, R \Big \rangle = \sum^{1\text{-labeled acceptable}}_{\text{shrubberies }\mathscr{S} = S_1 \sqcup \dots \sqcup S_t} \nonumber \\ & \qquad\qquad\qquad \int_{|z_{r_1}| = \dots = |z_{r_t}|} \mathop{\text{Res}}_{S_1} \dots \mathop{\text{Res}}_{S_t} \frac {z_1^{d_1}\dots z_n^{d_n} R(z_1,\dots,z_n)}{\prod_{1\leq a < b \leq n} \zeta_{i_bi_a} \left(\frac {z_b}{z_a} \right)} \prod_{u = 1}^t Dz_{r_u}. \end{align} $$
The fact that all the contours coincide means that we can symmetrize the integrand (with respect to all variables
$z_1,\dots ,z_n$
) without changing the value of the integral
$$ \begin{align*} & \Big \langle e_{i_1,d_1} \cdots e_{i_n,d_n}, R \Big \rangle = \sum^{\text{fixed }1\text{-labeled acceptable}}_{\text{shrubberies } \bar{\mathscr{S}} = \bar{S}_1 \sqcup \dots \sqcup \bar{S}_t} \\ &\qquad\qquad\qquad \int_{|z_{r_1}| = \dots = |z_{r_t}|} \mathop{\text{Res}}_{\bar{S}_1} \dots \mathop{\text{Res}}_{\bar{S}_t} \text{ Sym} \left[ \frac {z_1^{d_1}\dots z_n^{d_n} R(z_1,\dots,z_n)}{\prod_{1\leq a < b \leq n} \zeta_{i_bi_a} \left(\frac {z_b}{z_a} \right)} \right] \prod_{u = 1}^t Dz_{r_u}, \end{align*} $$
where the adjective ‘fixed’ means that we are summing over a given 1-labeled acceptable shrubbery in every equivalence class given by permuting the labels on the vertices. Because of the identity
$$ \begin{align*}\widetilde{\Upsilon}^+(e_{i_1,d_1} \cdots e_{i_n,d_n}) \stackrel{2.1}= \textrm{Sym} \left[ z_1^{d_1}\dots z_n^{d_n} \prod_{1\leq a < b \leq n} \zeta_{i_ai_b} \left(\frac {z_a}{z_b} \right) \right], \end{align*} $$
we conclude that
$$ \begin{align} \Big \langle e_{i_1,d_1} \cdots e_{i_n,d_n}, R \Big \rangle = \sum^{\text{fixed }1\text{-labeled acceptable}}_{\text{shrubberies } \bar{\mathscr{S}} = \bar{S}_1 \sqcup \dots \sqcup \bar{S}_t} \end{align} $$
$$ \begin{align*}\int_{|z_{r_1}| = \dots = |z_{r_t}|} \mathop{\text{Res}}_{\bar{S}_1} \dots \mathop{\text{Res}}_{\bar{S}_t} \frac {\widetilde{\Upsilon}^+(e_{i_1,d_1} \cdots e_{i_n,d_n}) R(z_1,\dots,z_n)}{\prod_{1\leq a \neq b \leq n} \zeta_{i_bi_a} \left(\frac {z_b}{z_a} \right)} \prod_{u = 1}^t Dz_{r_u}. \end{align*} $$
We conclude that
$\langle \phi , R \rangle $
is a linear functional of
$\widetilde {\Upsilon }^+(\phi )$
. Since the latter expression is 0 due to the fact that
$\phi \in K^+$
, we conclude the required formula (3.16).
Note that Equation (3.25) implies the following formula for the descended pairing (2.16), under the assumption that Q is shrubby
$$ \begin{align} \Big \langle R^+, R^- \Big \rangle = \sum^{\text{fixed }1\text{-labeled acceptable}}_{\text{shrubberies } \bar{\mathscr{S}} = \bar{S}_1 \sqcup \dots \sqcup \bar{S}_t} \end{align} $$
$$ \begin{align*}\int_{|z_{r_1}| = \dots = |z_{r_t}|} \mathop{\text{Res}}_{\bar{S}_1} \dots \mathop{\text{Res}}_{\bar{S}_t} \text{ Sym} \left[ \frac {R^+(z_1,\dots,z_n)R^-(z_1,\dots,z_n)}{\prod_{1\leq a \neq b \leq n} \zeta_{i_bi_a} \left(\frac {z_b}{z_a} \right)} \right] \prod_{u = 1}^t Dz_{r_u} \end{align*} $$
for any
$R^\pm \in {\mathcal {S}}^\pm $
of opposite degrees. Formula (3.26) shows that shrubberies are not just technical tools used in the proof of Proposition 3.10, but natural combinatorial objects which parameterize the summands in the formula for the pairing (2.16).
Appendix A: the joys of gardening
In the present section, we will motivate our notion of shrubby quivers by relating it with more traditional consistency conditions in the theory of brane tilings and dimer models. We also prove several technical results from Section 3.
A.1
Let Q denote a quiver in
${\mathbb {T}}^2$
, as in Definition 1.3, that is, the faces of Q are colored in blue/red such that any two faces which share an edge have different colors.
Definition A.2. A nondegenerate R-charge (see, for instance, [Reference Hanany, Herzog and Vegh7, Reference Hanany and Vegh8]) is a function
$$ \begin{align*}R : E \rightarrow (0,1) \end{align*} $$
such that for any vertex i and any face F of the quiver Q, we have
$$ \begin{align*} &\sum_{e \text{ edge around }F} R(e) = 2 \\ &\sum_{e \text{ edge incident to }i} (1-R(e)) = 2. \end{align*} $$
Footnote
10
Geometrically, the properties above imply that the quiver Q can be drawn on the torus so that all faces are polygons circumscribed in circles of the same radius, and the centers of these circles lie strictly inside the faces (the number
$\pi R(e)$
is the central angle subtended by the chord e in the aforementioned circles).
The existence of a nondegenerate R-charge allows one to define a rhombus tiling of the torus, as follows. Draw the centers of the (circles circumscribing the) blue/red polygonal faces as blue/red bullets. Then the condition that the segments between the vertices and the bullets all have the same length means that
${\mathbb {T}}^2$
is tiled by rhombi. To recover the arrows in the quiver Q from the rhombus tiling, one need only draw the diagonals between nonbullet vertices of the rhombi and orient them so that they keep the blue/red bullets on the right/left (see Figure A1).
Figure A1 A rhombus. The blue/red bullets represent the centers of the blue/red faces, while the other two vertices of the rhombus are vertices of Q (with an arrow between them).
Recall the notion of shrubby quivers from Definition 1.5. Lemma A.3 below is proved just like [Reference Hanany, Herzog and Vegh7, Lemma 5.3.1] (note that the topology of shrubby quivers underlies the notion of F-term equivalent paths, see [Reference Davison1, Definition 2.5] and [Reference Mozgovoy and Reineke10, Condition 4.12]).
Lemma A.3. If there exists a nondegenerate R-charge, then Q is shrubby.
A.4
In the remainder of the paper, we provide proofs of some technical results about shrubs and preshrubs, specifically Propositions 3.13, 3.15, 3.17, 3.20 and 3.21. Throughout the present section, we assume Q to be a shrubby quiver, with universal cover
$\widetilde {Q}$
. All paths and cycles in a quiver are understood to be oriented.
Definition A.5. Given two paths p and
$p'$
in
$\widetilde {Q}$
with the same endpoints, we will write
$r(p,p')$
for the closed region inside
${\mathbb {R}}^2$
contained between p and
$p'$
. The area of this region, denoted by
$a(p,p') \in {\mathbb {N}}$
, will refer to the number of faces contained inside
$r(p,p')$
. In particular, if C is a cycle, we will write
$r(C)$
and
$a(C)$
for the closed region and area (respectively) contained inside C.
Proof. Proof of Proposition 3.13.
Assume for the purpose of contradiction that a preshrub S contains a cycle, and let us fix such a cycle C of minimal area (as in Definition A.5). We must have
$a(C)> 2$
, since otherwise C would be the boundary of a face, or the union of boundaries of two faces which meet at a single point, both situations being forbidden for preshrubs. Definition 1.5 for
$p=C$
and
$p' = \text {trivial}$
implies that there exist two adjacent faces (as in Figure 2) for which, for example, the red path is completely contained in C, and the red and blue regions are contained inside
$r(C)$
. By the defining property of a preshrub, S also contains the blue path. Thus, the cycle
$$ \begin{align*}C' = C - \{\text{red path}\} + \{\text{blue path}\} \end{align*} $$
is contained in S, and moreover,
$a(C') = a(C) - 2$
. This contradicts the minimality of the area of C.
Proof. Proof of Proposition 3.15.
Assume that e is an edge from vertex i to vertex
$i'$
, where
$i,i' \in S$
but
$e \not \subset S$
. By the very definition of the root r of a shrub, there are paths from r to i and
$i'$
, respectively. Following the aforementioned paths until they first intersect, we conclude that there exist simple paths
$$ \begin{align*} &p : j \rightarrow \dots \rightarrow i \\ &p' : j \rightarrow \dots \rightarrow i' \end{align*} $$
with no vertices in common other than the source j. We have three scenarios.
(1) If
$j=i$
, then e and
$p'$
are both paths from i to
$i'$
. We may assume that
$p'$
is chosen such that
$a(e,p')$
is minimal. Definition 1.5 implies that
$p'$
contains a broken wheel B (since e consists of a single edge, it cannot contain a broken wheel). Since S is a shrub, it therefore contains the mirror image
$B'$
of B. Thus, if we modify
$p'$
by replacing its sub-path B with
$B'$
, then we contradict the minimality of
$a(e,p')$
. We conclude that this scenario is impossible.
(2) If
$j = i'$
, then
$C = p \cup e$
is a cycle, and we assume that p is chosen so that
$a(C)$
is minimal. If
$a (C) = 1$
, then we are done (since
$r(C)$
would be precisely the face that realizes e as the interface of a broken wheel contained in S), so let us assume for the purpose of contradiction that
$a(C)> 1$
. Definition 1.5 implies that C contains a broken wheel B. There are two subcases.
-
• If
$e \not \subset B$
, then S must also contain the mirror image
$B'$
of B. If we modify p by replacing its subpath B with
$B'$
, then we contradict the minimality of
$a(C)$
. -
• If
$e \subset B$
, then the interface
$e'$
of the broken wheel B is an edge between two vertices of the shrub S. If
$e' \subset S$
, then we contradict the minimality of
$a(C)$
and the fact that
$a(C)> 1$
. If
$e' \not \subset S$
, then there is a subpath of p from the source to the tail of
$e'$
, and we are thus in the self-contradictory situation of item (1).
(3) If
$j \notin \{i,i'\}$
, then let us choose
$p,p',e$
such that
$a(p \cup e, p')$
is minimal. In this case, Definition 1.5 implies that one of
$p \cup e$
or
$p'$
contains a broken wheel B whose interface is contained in
$r(p \cup e, p')$
. If
$B \subseteq p$
or
$B \subseteq p'$
, then we may modify the path p or
$p'$
by replacing its subpath B with its mirror image, and contradict the minimality of
$a(p \cup e, p')$
. The only other possibility is that
$e \subset B$
, in which case the interface of B must be an edge
$e' : i' \rightarrow v$
for some vertex
$v \in p$
, as in Figure A2.
Figure A2 The situation in item (3).
If
$e' \subset S$
, then concatenating
$e'$
with the subpath of p that goes from v to i puts us in the situation of item (2) above. Meanwhile, if
$e' \not \subset S$
and
$v = j$
, the cycle formed by
$p'$
and
$e'$
also puts us in the situation of item (2); since
$e'$
must therefore be the interface of a broken wheel B contained in S, replacing
$p'$
by the mirror image
$B'$
of B would contradict the minimality of
$a(p \cup e, p')$
. Finally, if
$e' \not \subset S$
and
$v \neq j$
, then we note that
$$ \begin{align*}a(p' \cup e', p") < a(p \cup e, p') \end{align*} $$
(where
$p"$
is the sub-path of p that goes from j to v) contradicts the minimality of
$a(p \cup e, p')$
.
Proof. Proof of Proposition 3.17.
We will treat the case
$s \in \{1,\dots ,k-1\}$
and leave the analogous case
$s = k$
as an exercise to the reader. Consider the paths
$p_s$
and
$p^{\prime }_s$
of Equations 3.14–3.15. Definition 1.5 states that one of these paths must contain a broken wheel B; without loss of generality, let us assume that
$B \subseteq p_s$
. If
$e_s$
were not part of B, then we would be able to modify
$p_s$
by replacing its sub-path B with its mirror image
$B'$
, and thus contradict the minimality of
$a(p_s,p^{\prime }_s)$
. Therefore, we may assume that
$e_s$
is part of B, and thus there exists
$v \in p_s$
and an edge
$$ \begin{align*}i \xrightarrow{e} v \end{align*} $$
such that the region bounded by e and
$p_s$
is a face. If
$v = j$
, then the index s is good (since the whole of
$p_s$
is the sought-for broken wheel, and its mirror image must coincide with
$p^{\prime }_s$
by minimality). Otherwise,
$v \neq j$
and let us consider the paths
$$ \begin{align*} &\tilde{p}_s : j \rightarrow \dots \rightarrow v \\ &\tilde{p}^{\prime}_s : j \rightarrow \dots \xrightarrow{e_{s+1}} i \xrightarrow{e} v \end{align*} $$
as in Figure A3.
Figure A3 A bad case.
Figure A4 An impossible case.
Definition 1.5 implies that one of the paths
$\tilde {p}_s$
and
$\tilde {p}^{\prime }_s$
must contain a broken wheel
$\tilde {B}$
. If
$\tilde {B}$
did not contain the edges
$e_{s+1}$
or e, then we could contradict the minimality of
$a(p_s,p^{\prime }_s)$
by replacing
$\tilde {B}$
with its mirror image
$\tilde {B}'$
. We are left only with the possibility of
$\tilde {B}$
containing the edges
$e_{s+1}$
or e, and we have two cases
-
• If the interface
$e'$
of
$\tilde {B}$
is an edge from i to some
$v' \in p^{\prime }_s$
, then we assume
$v' \neq j$
(as the case
$v' = j$
can be treated like the case
$v=j$
was treated above). We are thus in the situation of Figure A3 and the index s is bad. -
• If the interface
$e'$
of
$\tilde {B}$
is an edge from v to some vertex
$v' \in p^{\prime }_s \backslash \{i\}$
, then we are in the situation of Figure A4. We have two subcases. If
$e' \subset S$
, then we contradict the minimality of
$a(p_s,p^{\prime }_s)$
. On the other hand, if
$e' \not \subset S$
, then Proposition 3.15 forces
$e'$
to be the interface of a broken wheel
$\bar {B} \subset S$
. The paths and
$$ \begin{align*}v' \xrightarrow{\bar{B}} v \rightarrow \dots \xrightarrow{e_s} i \end{align*} $$
$v' \rightarrow \dots \xrightarrow {e_{s+1}} i$
contradict the minimality of
$a(p_s,p^{\prime }_s)$
.
Proof. Proof of Proposition 3.20.
If i is not an addable vertex, there must exist a bad index
$s \in \{1,\dots ,k\}$
, that is, either the situation of
$s=1$
in the picture on the left of Figure 4 or the situation of
$s=3$
in the picture on the right of Figure 4. In both of these cases, one can see a broken wheel in
$S+i$
whose mirror image is not contained in
$S+i$
, thus precluding
$S+i$
from being a shrub.
Conversely, suppose that i is an addable vertex, and let us show that
$S+i$
is a shrub. It is clear that i can be reached via a path from the root and that there are no vertices
$\notin S+i$
inside the polygonal regions incident to i in Figure 3.
Assume for the purpose of contradiction that
$S+i$
contains the entire boundary of a face. Since S cannot contain the entire boundary of a face (as S is a shrub), then the boundary in question must involve the vertex i. However, this would require an edge from i to a vertex of S, which is not in
$S+i$
by assumption.
Now, let us assume that
$S+i$
contains a broken wheel B, and let us show that it also contains its mirror image. Since S is already a shrub, we may assume that the broken wheel B involves the vertex i. By the definition of an addable vertex, all possible edges between i and S are as in Figure 3. Thus, the interface of the broken wheel B must be one of the dotted edges in Figure 3, and it is clear that the mirror image of B is also contained in
$S+i$
.
Proof. Proof of Proposition 3.21.
If i is addable to S, then all
$s \in \{1,\dots ,k\}$
are good. Therefore, there exist only
$k-1$
outgoing edges from i to S, and they are arrayed as in Figure 3. Among any family of faces passing through i and without other pairwise intersections, no two faces can pass through the same outgoing edge, so the cardinality of the family is at most
$k-1$
. It is also easy to see that this maximum can be achieved, by taking for instance the collection of faces incident to
$e_1,\dots ,e_{k-1}$
in clockwise order around i.
If i is nonaddable to S, then there exists a bad index s. Assume first that
$s \in \{1,\dots , k-1\}$
, for example, we are in the situation of
$s=1$
in the picture on the left of Figure 4. The two faces contained in the region
$r_s$
, together with the faces incident to
$e_1,\dots ,e_{s-1}$
in clockwise order around i, and the faces incident to
$e_{s+2},\dots ,e_k$
in counterclockwise order around i, yield altogether a family of k faces which only pairwise intersect at i.
If
$s = k$
is a bad index, then we are in the situation in the picture on the right of Figure 4. Without loss of generality, let us assume that there is a face incident to
$e_k$
in clockwise order around i. Then this face together with the faces incident to
$e_1,\dots ,e_{k-1}$
in clockwise order around i, yield the required family of k faces which only pairwise intersect at i.
Competing interests
The authors have no competing interest to declare.
