1 Introduction↩︎

The symmetric group \(S_d\), and more generally any Coxeter group, possesses a useful associative operation \(\star\), variously called the Demazure, \(0\)-Hecke, or greedy product. If \(\alpha \in S_d\) and \(\sigma_n\) is the simple transposition of \(n\) and \(n+1\), then \[\label{eq:demazureBasic} \alpha \star \sigma_n = \begin{cases} \alpha \sigma_n &if\alpha(n) < \alpha(n+1),\\ \alpha &otherwise. \end{cases}\tag{1}\] Since \(\star\) is associative and every \(\beta \in S_d\) factors into simple transpositions, Equation 1 is enough to compute any Demazure product in \(S_d\). A similar formulation is valid in any Coxeter group.

The Demazure product on \(S_d\) has an equivalent formulation that is transparently independent of choice of factorization. To state it, first define, for any permutation \(\alpha\), a counting function \[s_\alpha(a,b) = \# \{ \ell \geq b:\;\alpha(\ell) < a \}.\] See Figure 1 for an illustration. The Demazure product on \(S_d\) then has the following characterization,

\[\label{eq:demazureMin} s_{\alpha \star \beta}(a,b) = \min_{1 \leq \ell \leq d+1} \Big[ s_\alpha(a,\ell) + s_\beta(\ell,b) \Big],for all1 \leq a,b \leq d+1.\tag{2}\]

This min-plus formulation of \(\star\) on \(S_d\) was found in a different form by Tiskin [1], which also gave an efficient algorithm for its computation. Tiskin’s point of view has also been generalized to some other infinite contexts including biwords on \(\{1,\cdots,n\}\) [2], permutons on \([0,1]\) [3], and affine permutations [4]. Other algorithmic extensions include [5].

Functions like \(s_\alpha\) (perhaps with reversed inequalities or other minor modifications) are sometimes called “rank functions;” they provide a convenient way to state the strong Bruhat order on \(S_d\) [6] and are used to define Schubert varieties in flag varieties [7]. If we view the functions \(s_\alpha, s_\beta\) as \((d+1) \times (d+1)\) matrices, Equation 2 says that \(s_{\alpha \star \beta}\) is obtained by matrix multiplication in the min-plus (tropical) semiring. It has a nice geometric interpretation in terms of relative position of flags; see Appendix 9.

We will follow the convention that elements of \(S_d\) are extended to permutations of \(\ZZ\) that fix all \(n \not\in [1,d]\). This does not affect the values \(s_\alpha(a,b)\) for \(1 \leq a,b \leq d+1\), but it does allow an alternative form of Equation 2 that does not depend on the choice of \(d\):

\[\label{eq:demazureMinZ} s_{\alpha \star \beta}(a,b) = \min_{\ell \in \ZZ} \Big[ s_\alpha(a,\ell) + s_\beta(\ell,b) \Big],for alla,b \in \ZZ.\tag{3}\]

This equation generalizes nicely to larger groups than \(S_d\). For example, the affine symmetric groups \(\widetilde{S}_k\) (see Example [eg:extAffine] or Section 8.4 for a definition) are Coxeter groups embedded as subgroups of the permutations of \(\ZZ\), and Equation 3 holds, with \(\sigma_n\) replaced by different generators, in \(\widetilde{S}_k\) as well. A simple proof is in [8] and is sketched in [9]; this also follows from this paper’s results.

The present paper uses the min-plus description of \(\star\) to generalize it to a much wider class of permutations. This generalization makes it possible to combine elements of \(S_d\) and elements of \(\widetilde{S}_k\) for different values of \(k\). Though this may appear at first glance to be an idle curiosity, such “mixed modulus” Demazure products occur in the theory of divisors on graphs and algebraic curves. Indeed, the impetus to write this paper was originally to provide a self-contained reference for various facts needed for work on tropical and algebraic curves. A brief discussion of these applications may be found in Appendix 10.

The group considered herein is the group of almost-sign-preserving permutations, which are the largest class of permutations \(\alpha: \ZZ \to \ZZ\) for which \(s_\alpha\) and \(s_{\alpha^{-1}}\) both take only finite values. This group is uncountable, and defining \(\star\) in terms of a generating set is not feasible. We prove the existence of an associative product \(\star\) in this context, defined by the min-plus formulation (Theorem [thm:starExists]), and demonstrate that it shares several nice aspects of the Demazure product on \(S_d\), including a characterization as a “greedy product” in Bruhat order (Theorem [thm:starGreedy]) and a “reduction theorem” (Theorem [thm:reduce]) for simplifying inequalities of the form \(\alpha \star \beta \geq \gamma\).

We also study a slightly broader context than \(\operatorname{ASP}\), namely a set \(\operatorname{SF}\) of functions which we call slipface functions \(s: \ZZ^2 \to \NN\). Then \(\operatorname{ASP}\) is embedded in \(\operatorname{SF}\) by \(\alpha \mapsto s_\alpha\); the image of this embedding consists of submodular slipface functions. The non-submodular slipface functions occur in tropical geometry, so there is some utility in this further generalization. The generalization from \(\operatorname{ASP}\) to \(\operatorname{SF}\) is analogous to the generalization from permutations matrices to alternating sign matrices; see Remark [rem:asm].

It is plausible that many of this paper’s results can be deduced from existing theory of Coxeter groups, via limit arguments. This would certainly be interesting to carry out, and indeed earlier drafts of this paper follow this approach in some parts (for example, Theorem [thm:starGreedy] may be proved by multiplying simple transpositions one at a time and applying Zorn’s lemma). However, this paper avoids this approach, and instead frames everything in terms of the functions \(s_\alpha\) and Equation 3 . This reveals some intriguing combinatorics hiding in the min-plus matrix multiplication expression, and also means that this paper is entirely self-contained.

The main theorems of this paper, and many but not yet all of the auxiliary results, have been formally verified in the Lean 4 proof assistant. The source code is available at the following repository, which also contains instructions for building and verifying the code.

paper also contains links to documentation of the formalizations of specific results, which are formatted like this, and shown near the right margin: . This project is still in development, with the objective eventually of using it as a tool with which to formalize aspects of combinatorial Brill–Noether theory. I welcome collaborators who wish to contribute or build upon the code.

1.1 Conventions and key definitions↩︎

The symbol \(\NN\) denotes the set of nonnegative numbers. The symbol \(\delta\) is used for an indicator function, equal to \(1\) if the statement within is true, and \(0\) otherwise. A permutation always refers to a bijective function \(\ZZ \to \ZZ\). Whenever we refer to a permutation of \(\{1, \cdots, d\}\), or any other finite set, we implicitly extend this to a permutation of all of \(\ZZ\) that fixes every other integer; so \(S_d\) is always implicitly understood to be embedded in the full permutation group of \(\ZZ\).

Call a permutation \(\alpha: \ZZ \to \ZZ\) almost-sign-preserving if there are only finitely many \(n\) such that exactly one of \(n, \alpha(n)\) is negative. We denote the group of almost-sign-preserving permutations by \(\operatorname{ASP}\). For any \(\alpha \in \operatorname{ASP}\), define a function \(s_\alpha: \ZZ^2 \to \NN\) by \[\label{eq:sa} s_\alpha(a,b) = \# \{ n \geq b: \alpha(n) < a \}.\tag{4}\] This function will be called (somewhat whimsically) the slipface function of \(\alpha\); see Section 2.

The shift of a permutation \(\alpha \in \operatorname{ASP}\) is the number \[\chi_\alpha= s_\alpha(0,0) - s_{\alpha^{-1}}(0,0).\] The importance of this number will become clear as we develop our results; some intuition about it is provided by observing that elements of \(S_d\) have shift \(0\), and more generally a permutation \(\alpha\) with finitely many inversions satisfies \(\alpha(n) = n - \chi_\alpha\) for all but finitely many \(n \in \ZZ\) (see Proposition [prop:reconstruction] for a precise general form of this fact).

The Bruhat order on \(\operatorname{ASP}\) is the partial order \(\leq\), where \[\alpha \leq \beta \quadmeans that \quad s_\alpha(a,b) \leq s_\beta(a,b)for alla,b \in \ZZ.\] In principle this definition involves infinitely many inequalities, but in practice it often suffices to check only those \((a,b)\) in the essential set; this is examined in Section 7.

Restricted to \(S_d\), this is the usual “strong” Bruhat order [6], which can also be deduced from Theorem [thm:reduceSeveral]. We discuss an analog in \(\operatorname{ASP}\) of the “weak” Bruhat orders in Section 5. We will also use the following shorthand: \[\alpha \leq_\chi\beta \;\quad \text{means that} \quad \alpha \leq \beta \text{ and } \chi_\alpha = \chi_\beta.\]

1.2 Main results↩︎

The following existence theorem combines Theorems [thm:starExists1] and [thm:alphaStarSigma].

The \(S_d\) case has a geometric interpretation in terms of the relative position of three flags; see Appendix 9.

The Demazure product coincides with the ordinary product in an important special case. We will see (Lemma 19) that \(\alpha \star \beta \geq \alpha \beta\), and that equality holds if and only if \(\alpha\) and \(\beta^{-1}\) have no inversions in common. In this situation, we will say later that \(\alpha \star \beta = \alpha \beta\) is a reduced product and write \(\alpha \mathbin{{\star}_{\mathrm{red}}}\beta\). I encourage the reader to attempt to prove this before reading on, as it provides useful intuition about Equation 5 .

We also prove a second characterization of this operation. It generalizes [10], [11] from \(S_d\) to \(\operatorname{ASP}\), and is proved in Section 6.

One way to understand Equation 1 is that for \(\beta \in S_d\), factoring \(\beta\) into adjacent transpositions allows you to find the \(\beta_1\) in Equation [eq:starGreedyBeta] by a greedy algorithm.

The last main objective of this paper is a “reduction theorem” for inequalities of the form \(\alpha \star \beta \geq \gamma\). We will prove that such an inequality implies an equation \(\alpha_1 \star \beta_1 = \gamma\). Furthermore, we will want these \(\alpha_1, \beta_1\) to satisfy \(\alpha_1 \beta_1 = \alpha_1 \star \beta_1\), and we wish to show that if \(\alpha, \beta, \gamma\) are from a suitable subgroup of \(\operatorname{ASP}\), then we may choose \(\alpha_1, \beta_1\) from the same subgroup. Several examples of such subgroups are discussed in Section 8, including symmetric and affine symmetric groups. To state our result, we first require an auxiliary operation that will prove to be a useful accomplice to \(\star\). This operation was identified by He in [12] for Coxeter groups.

Most of this theorem is proved in Theorem [thm:resLExists], except the statement about \(\sigma_n\), which is proved in Theorem [thm:alphaStarSigma]. The operation \(\triangleleft\) also has a characterization analogous to Theorem [thm:starGreedy], stated in Theorem [thm:resLStingy], which is closer to He’s definition in [12].

There is also a dual operation to \(\triangleleft\), which we denote \(\triangleright\) and call the right residual. It is characterized by \[\label{eq:resRMin} \alpha^{-1} \triangleright\beta = \min \{ \gamma \in \operatorname{ASP}: \alpha \star \gamma \geq \beta \}.\tag{8}\] It suffices to focus on \(\triangleleft\), since we will prove that \(\alpha \triangleright\beta = (\beta^{-1} \triangleleft\alpha^{-1})^{-1}\) (Theorem [thm:resLExists]).

We mention the case \(\beta = \sigma_n\) in the statement above to support the following intuition: where \(\star\) is a greedy multiplication, \(\triangleleft\) is a “stingy multiplication;” \(\beta\) attempts to make \(\alpha\) as Bruhat-small as possible using part of itself. This is made precise in Theorem [thm:resLStingy], in analogy to Theorem [thm:starGreedy].

Our reduction theorem for inequalities \(\alpha \star \beta \geq \gamma\) is the following. It is proved in Section 6, along with a generalization to products of three or more permutations (Theorem [thm:reduceSeveral]).

In addition to Theorems [thm:starExists], [thm:starGreedy], and [thm:reduce], we also examine some other properties of Bruhat order and \(\star\) on certain subgroups of \(\operatorname{ASP}\) that will be useful in our applications; see Sections 7 and 8.

1.3 Background on Demazure products↩︎

We use the name Demazure product in reference to [13], in which a collection of operators \(L_\alpha\) are defined such that, in our notation, \(L_\alpha L_\beta = L_{\alpha \star \beta}\) (see §5.6 of that paper). The same operation occurred around the same time in [14]. This point of view, realizing the Demazure product in terms of composition of operators, occurs in many other contexts, e.g. [15], which considers operators \(\overline{\partial}_i\), \(1 \leq i < n\), on a polynomial ring \(R[x_1, \cdots, x_n]\) defined by \[\overline{\partial_i}(f) = \frac{x_{i+1} f - x_i (s_i \cdot f)}{x_{i+1}-x_i},\] and considers the Demazure algebra generated by these operators. These difference operators are related, but not identical to, the difference operators used to define Schubert polynomials, e.g. as in [7]. I do not know if there is a useful way to relate the min-plus formulation of \(\star\) to this operator formulation, or whether the Demazure product on \(\operatorname{ASP}\) can be understood in a similar way.

The other principal point of view on \(\star\) is from the Hecke algebra, in which it arises (up to sign) by setting the parameter \(q\) to \(0\), hence called the \(0\)-Hecke product. See [16] or [6].

Applications of the Demazure product to algebraic geometry typically relate to the geometry of Schubert varieties. Another interesting example of such applications is [11], which shows that a curve neighborhood of a Schubert variety results in another Schubert variety, indexed by the permutation given by the Demazure product.

1.4 Outline of the paper↩︎

We begin with some preliminary facts about \(\operatorname{ASP}\) and the functions \(s_\alpha\) in Section 2. Section 3 introduces the set \(\operatorname{SF}\) of slipfaces, formulates the Demazure product and residuals at this level of generality, and proves a few basic facts. Section 4 identifies the functions \(s_\alpha\) as those slipfaces that are submodular, thereby constructs \(\star\) and \(\triangleleft\) on \(\operatorname{ASP}\) and proves Theorem [thm:starExists], and analyzes the locations of inversions after these operations. Sections 5 and 6 leverage the earlier results to relate \(\star\) and \(\triangleleft\) to reduced products and weak Bruhat orders, to prove Theorems [thm:starGreedy] and [thm:reduce]. Section 7 generalizes a concept called the essential set to \(\operatorname{ASP}\), in order to study Bruhat order. Section 8 considers a number of subgroups of \(\operatorname{ASP}\) of special interest, and identifies some aspects of \(\star\) and \(\triangleleft\) specific to those subgroups. Finally, two appendices follow to provide context. Appendix 9 provides a concrete geometric interpretation of the “min-plus matrix multiplication” formula in the \(S_d\) case, in terms of relative positions of flags. Appendix 10 briefly summarizes applications to divisor theory on algebraic curves and (metric) graphs.

2 Preliminaries on almost-sign-preserving permutations↩︎

This section collects a few preliminary facts about almost-sign-preserving permutations and their slipface functions, and also attempts to explain my somewhat whimsical choice of the word “slipface.” First observe the following characterizations of finite differences of \(s_\alpha\). Note that Equation [eq:Deltasa] shows that the slipface function \(s_\alpha\) uniquely determines the permutation \(\alpha\). \[\begin{align} \refstepcounter{equation}\ltx@label{eq:b+1} \normalfont\normalcolor(\theequation)&& s_\alpha(a,b) - s_\alpha(a,b+1) &= \delta\left( \alpha(b) < a \right) & \leanlink{AspPerm.b_step} \\ \refstepcounter{equation}\ltx@label{eq:a+1} \normalfont\normalcolor(\theequation)&& s_\alpha(a+1,b) - s_\alpha(a,b) &= \delta\left( \alpha^{-1}(a) \geq b \right) & \leanlink{AspPerm.a_step} \\ \refstepcounter{equation}\ltx@label{eq:Deltasa} \normalfont\normalcolor(\theequation)&& s_\alpha(a+1,b) - s_\alpha(a,b) - s_\alpha(a+1,b+1) + s_\alpha(a,b+1) &= \delta(\alpha(b) = a) & \leanlink{AspPerm.Delta_eq} \end{align}\]

I will now attempt to convince you that the word “slipface” does indeed evoke the basic properties of these functions \(s_\alpha\). The function \(s_\alpha\) may be usefully visualized as a sequence of functions \(f(n) = s_\alpha(n,b)\) for various choices of \(b\). For \(b\) fixed, this function is a nondecreasing function, beginning at \(0\), and eventually stabilizing to have slope \(1\). When \(b\) increases, Equation [eq:b+1] shows that part of the function drops, namely all points with \(n > \alpha(b)\), so the slope-\(1\) line that the graph approaches shifts one unit to the right. Some examples are shown in Figure 2. In these three examples, we consider three permutations in \(S_9\). To me at least, this sequence of graphs evokes a dune of sand which, over time, drops in height as sand slips and falls down the face, and thereby appears to move to the right.

2.1 Some properties of the shift \(\chi_\alpha\)↩︎

Equations [eq:b+1] and [eq:a+1] show that the function \(f(a,b) = s_\alpha(a,b) - s_{\alpha^{-1}}(b,a) -a + b\) is constant. Since \(\chi_\alpha= f(0,0)\) by definition, we have the following duality between \(s_\alpha\) and \(s_{\alpha^{-1}}\), reminiscent (not coincidentally!) of the Riemann-Roch formula. \[\renewcommand{\theequation}{\dagger} \refstepcounter{equation}\label{eq:saDuality} \makebox[0pt][l]{\normalfont\normalcolor(\theequation)} \makebox[\displaywidth][c]{\displaystyle s_\alpha(a,b) - s_{\alpha^{-1}}(b,a) = \chi_\alpha+ a - b.} \makebox[0pt][r]{ \leanboxframe{\tiny \doclink{AspPerm.duality}} }\tag{9}\] Equation 9 shows that \(s_\alpha(a,b) \geq \max\{0, \chi_\alpha+ a - b\}\), with equality if and only if either \(s_\alpha(a,b) = 0\) or \(s_{\alpha^{-1}}(b, a) = 0\). For \(a\) fixed and \(b \ll 0\), or \(b\) fixed and \(a \gg 0\), \(s_{\alpha^{-1}}(b,a) = 0\), so \(s_\alpha(a,b) = \chi_\alpha+ a - b\). In this sense, the shift \(\chi_\alpha\) governs the asymptotic behavior of \(s_\alpha\). We mention a few other immediate consequences of Equation 9 .

If we define \(\operatorname{sgn}(n)\) to be \(1\) for \(n \geq 0\) and \(-1\) for \(n < 0\), then \[\chi_\alpha= \frac{1}{2} \sum_{n \in \ZZ} \Big( \operatorname{sgn}(n) - \operatorname{sgn}(\alpha(n)) \Big).\] It follows from this description, rearranging a sum and cancelling, that \(\chi\) is a homomorphism: \[\refstepcounter{equation}\label{eq:chiHom} \makebox[0pt][l]{\normalfont\normalcolor(\theequation)} \makebox[\displaywidth][c]{\displaystyle \chi_{\alpha \beta} = \chi_\alpha + \chi_\beta.} \makebox[0pt][r]{ \leanboxframe{\tiny \doclink{AspPerm.chi_mul}} }\tag{10}\] Thus shift sorts \(\operatorname{ASP}\) into cosets of a homomorphism \(\chi: \operatorname{ASP}\to \ZZ\). This homomorphism has a nice splitting, given by \(\chi \mapsto \iota_\chi\). We will see that \(\chi\) is also a monoid homomorphism for the Demazure product: \(\chi_{\alpha \star \beta} = \chi_\alpha+ \chi_\beta\) (Theorem [thm:starExists1]). Furthermore, \(\iota_m \star \alpha = \iota_m \alpha\) and \(\alpha \star \iota_m = \alpha \iota_m\) for all \(\alpha \in \operatorname{ASP}\) (this follows from Lemma 19, since \(\iota_\chi\) has no inversions). This means that essentially everything we might wish to know about \(\star\) on \(\operatorname{ASP}\) is determined by its restriction to \(\operatorname{ASP}_0 = \{ \alpha \in \operatorname{ASP}: \chi_\alpha= 0 \}\).

2.2 Inversions, reduced products, and the weak orders↩︎

Much of our analysis will be based on careful study of inversions.

The set of inversions leads to two other preorders on \(\operatorname{ASP}\). The terms below are chosen to mirror terminology from Coxeter groups; see e.g. [6], especially §1.4, Exercise 1.13, §3.1, Proposition 3.1.3, and Corollary 3.1.4.

These are not partial orders on all of \(\operatorname{ASP}\): for instance, \(\iota_m \leq_L \iota_n\) and \(\iota_n \leq_L \iota_m\) for all \(m,n \in \ZZ\). Proposition [prop:reconstruction] shows that they become partial orders after restricting to permutations with fixed shift.

Closely related to the weak orders is the notion of a reduced product.

In fact, we prove in Lemma 19 that \(\alpha \beta\) is a reduced product if and only if \(\alpha \star \beta = \alpha \beta\), which is why we have chosen the notation \(\mathbin{{\star}_{\mathrm{red}}}\).

The two weak orders and the notion of reduced products are closely related.

2.3 Reconstruction from the inversion set↩︎

This subsection is not logically needed elsewhere in the present paper. It is included to give another conceptual view on \(\operatorname{ASP}\): the permutations in \(\operatorname{ASP}\) are in bijection with the pairs consisting of a shift \(\chi\) and a subset \(I \subseteq \ZZ^2\) satisfying some simple assumptions. Characterizations of this kind are known in many similar contexts; see for example [17]. The utility is that this provides a convenient route to efficiently describing the set of all permutations below a fixed \(\alpha \in \operatorname{ASP}\) in the weak preorders.

The first observation is that the shift and inversion set uniquely determine the permutation.

So mapping a permutation \(\alpha\) to the pair \((\chi_\alpha, \operatorname{Inv}\alpha)\) is an injective map, and one may ask for a characterization of its image. Such a characterization is happily quite simple.

3 Slipface functions↩︎

In this section, we define a broader class of functions \(\ZZ^2 \to \NN\), possessing several of the features ascribed to the slipface functions \(s_\alpha\). We call this broader class slipfaces as well, and will characterize those slipface functions equal to \(s_\alpha\) for some \(\alpha \in \operatorname{ASP}\) as submodular slipfaces. There are two reasons to step back to this more general setting. First, many of our proofs are naturally organized by first reasoning about general slipfaces and then adding the submodularity condition. Second, in our intended application to metric graphs, non-submodular slipfaces naturally occur.

Slipfaces possess a duality, analogous to Equation 9 .

Substituting into Definition [defn:slipface] shows \(s^\vee\) is indeed a slipface, with shift \(-\chi\).

One convenient aspect of duality is that it provides a streamlined criterion for checking that a given function is indeed a slipface, and determining its shift, in many situations. For a function \(f: \ZZ^2 \to \ZZ\), we consider the following two criteria on \(f\).

1. For all \(a,b \in \ZZ\), \(f(a+1,b) \geq f(a,b)\) and \(f(a,b+1) \leq f(a,b)\).

2. For fixed \(a\) and any \(b \gg 0\), \(f(a,b) = 0\); similarly, for fixed \(b\) and any \(a \ll 0\), \(f(a,b) = 0\).

3.1 The operations \(\star, \triangleleft, \triangleright\) on \(\operatorname{SF}\)↩︎

We are concerned with the following operations on \(\operatorname{SF}\).

To see that the maxima defining \(\triangleleft\) and \(\triangleright\) exist, note that as \(k \to \pm \infty\), the fact that \(s,t\) are slipfaces means that the expressions \(s(a,k) - t^\vee(b,k)\) and \(s^\vee(k,b) - t(k,a)\) converge, with one of the two limits converging to \(0\). This implies that the maxima are well-defined, and nonnegative.

The following compatibilities with \(\leq\) are immediate from this definition.

3.2 Example computations↩︎

We now illustrate the definitions of \(\star\) and \(\triangleleft\) in two particularly simple cases: when one permutation is increasing, or a disjoint product, possibly infinite, of adjacent transpositions. In these and other computations, it is useful to shrink the set on which the extremum defining \(\star, \triangleleft,\) or \(\triangleright\) is computed. The following lemma provides one way to do so (by no means the only way). For convenience this lemma is stated only for \(\star\) and \(\triangleleft\), but it can be applied to \(\triangleright\) as well using the identity \(s \triangleright t = (t^\vee \triangleleft s^\vee)^\vee\).

These include the simple transpositions \(\sigma_n = \sigma_{\{n\}}\) used to generate symmetric groups, as well as the involutions \(\widetilde{\sigma}_n = \sigma_{n + k \ZZ}\) used to generate the affine symmetric group \(\widetilde{S}_k\).

A more general formula for \(\alpha \star \sigma_S\) is proved in Theorem [thm:alphaStarSigma].

4 The image of \(\operatorname{ASP}\) in \(\operatorname{SF}\): submodular slipfaces↩︎

The map \(\alpha \mapsto s_\alpha\) embeds \(\operatorname{ASP}\hookrightarrow \operatorname{SF}\). We demonstrate in this section that the image is closed under the operations \(\star, \triangleleft, \triangleright\), and thereby obtain corresponding operations on \(\operatorname{ASP}\). A key tool is a characterization of the image of this inclusion as the set of submodular slipfaces.

The following shorthand will prove useful. For \(s \in \operatorname{SF}\), define \(\Delta s: \ZZ^2 \to \{-1,0,1\}\) by \[\Delta s(a,b) = s(a+1,b) - s(a,b) - s(a+1,b+1) + s(a,b+1).\] The fact that \(\Delta s(a,b) \in \{-1,0,1\}\) follows from Criterion (S1). The function \(s\) can be reconstructed from \(\Delta s\). Observe that for \(a,b\) fixed, there are only finitely many \((a',b') \in \ZZ\) such that \(a' \leq a, b' \geq b\) and \(s(a',b') > 0\). From this and a telescoping sum, it follows that \[\label{eq:sumDelta} s(a,b) = \sum_{ \substack{a' < a\\b' \geq b} } \Delta s(a',b').\tag{13}\] Here and throughout this section, an equation involving a sum of infinitely many integers is understood to mean implicitly that only finitely many terms are nonzero; equivalently, the sum converges absolutely. The definition of \(s^\vee\) and some cancellation shows that \[\label{eq:DeltasDual} \Delta s^\vee(a,b) = \Delta s(b,a),\tag{14}\] and then Equation 13 implies that \[\label{eq:sumDeltaDual} s^\vee(b,a) = \sum_{ \substack{a' \geq a\\b' < b} } \Delta s(a',b').\tag{15}\] Therefore any slipface \(s\) can be reconstructed from the knowledge of the points \((a,b)\) where \(\Delta s(a,b) =1\) and the points where \(\Delta s(a,b) = -1\). These two sets are fairly constrained, however. Since \(\displaystyle \lim_{b \to \infty} \left( s(a+1,b) - s(a,b) \right) = 1\), and \(\displaystyle \lim_{a \to \infty} \left( s^\vee(b+1,a) - s^\vee(b,a) \right) = 1\), we deduce

4.1 The Demazure product \(\star\) on \(\operatorname{ASP}\)↩︎

This subsection proves the following theorem and develops a few combinatorial properties of \(\star\) on \(\operatorname{ASP}\).

We will use the following elementary lemma several times. We omit the straightforward proof.

The discussion above also provides information about the inversions of \(\alpha \star \beta\).

4.2 The operations \(\triangleleft, \triangleright\) on \(\operatorname{ASP}\)↩︎

This subsection parallels the previous. We will prove

The analog of Lemma 15 for the operations \(\triangleleft, \triangleright\) is the following.

5 When \(\star, \triangleleft, \triangleright\) are ordinary products↩︎

This section examines the relation between \(\star, \triangleleft, \triangleright\) on \(\operatorname{ASP}\) and the ordinary product.

Among other things, this clarifies the relationship between the weak and strong Bruhat orders.

6 Greediness, stinginess, and the reduction theorem↩︎

The tools of the previous section furnish proofs of the greedy characterization of \(\star\), the “stingy” characterizations of \(\triangleleft\) and \(\triangleright\), and the reduction theorem.

The analogy of the “greedy theorem” for \(\star\) is the following “stingy theorem” for \(\triangleleft\).

The reduction theorem from the introduction follows by similar techniques.

In some applications, it is convenient to use a form of Theorem [thm:reduce] for products of more than two permutations; we give such a statement here for convenience. To state it, we must first clarify what is meant by a reduced product of three or more permutations; the definition below is based on the standard definition of a reduced word in a Coxeter group, adapted both to products of non-generators and to permutations that may have infinitely many inversions.

7 Bounded-difference permutations and the essential set↩︎

Having proved our main theorems, this section addresses a somewhat different question that will prove useful in applications: when comparing two permutations in Bruhat order, or more generally two slipfaces, does it suffice to check the inequality \(s(a,b) \leq t(a,b)\) for some small subset of \(\ZZ \times \ZZ\)? There is a standard tool for this in \(S_d\), called the essential set, introduced in [20] for applications to degeneracy loci, which we adapt herein to \(\operatorname{SF}\) and \(\operatorname{ASP}\). Unfortunately, a subtle finiteness issue restricts the use of this tool to certain slipfaces, which we call Clifford slipfaces. In the submodular case, these correspond to bounded-difference permutations, which we define below.

7.1 The essential set of a slipface↩︎

The key definition is the following.

As in the theory of degeneracy loci, the purpose of \(\mathop{\mathrm{Ess}}(s)\) is to identify a smaller, often finite, set on which to verify inequalities \(s(a,b) \leq t(a,b)\). The basic observation is

Lemma 22 almost implies that \(s \leq t\) if and only if \(s(a,b) \leq t(a,b)\) for all \((a,b) \in \mathop{\mathrm{Ess}}(s)\). The only catch is that the process of \((a,b)\) by \((a',b')\) might not terminate. A quick, if perhaps slightly unsatisfying, fix is simply to restrict the classes of slipfaces \(s\) considered. Fortunately this restriction still encompasses all slipfaces that occur in our intended applications. The name Clifford refers to Clifford’s theorem from the theory of algebraic curves.

7.2 The essential set of a permutation↩︎

Now consider the submodular case.

Equations [eq:b+1] and [eq:a+1] imply that \[\refstepcounter{equation}\label{eq:essPermSa} \makebox[0pt][l]{\normalfont\normalcolor(\theequation)} \makebox[\displaywidth][c]{\displaystyle \mathop{\mathrm{Ess}}(s_\alpha) = \mathop{\mathrm{Ess}}(\alpha).} \makebox[0pt][r]{ \leanboxframe{\tiny \doclink{AspPerm.ess_asp_eq_ess_sf}} }\tag{18}\] The expression in Definition [defn:essPerm] matches the definition in [20], used in the study of degeneracy loci. For this to be useful, we must understand which \(\alpha \in \operatorname{ASP}\) have Clifford slipfaces \(s_\alpha\). If there is an integer \(M\) such that \(|\alpha(n) - n| \leq M\) for all \(n \in \ZZ\), we will say that \(\alpha\) has bounded difference.

One additional benefit of bounded-difference permutations is that we can state a slightly simplified criterion for checking that a given function is the slipface function of a bounded-difference permutation (or equivalently, a submodular Clifford slipface).

8 Some subgroups of \(\operatorname{ASP}\) closed under \(\star\) and \(\triangleleft\)↩︎

We conclude this paper by examining a few types of commonly-encountered subgroups of \(\operatorname{ASP}\) that are closed under \(\star\) and \(\triangleleft\) (and therefore also \(\triangleright\)), and pointing out some notable special features on the operations on these groups. Several of these examples have the following feature, which is a convenient way to verify closure under \(\star\) and \(\triangleleft\).

8.1 Permutations of bounded difference↩︎

As in Section 7, we say that \(\alpha\) has bounded difference if there exists an integer \(M\) such that \(|\alpha(n) - n| \leq M\) for all \(n \in \ZZ\). These permutations naturally occur in our application to algebraic curves and graphs (see Appendix 10), where the bound \(M\) is determined by the genus, and we have seen that they have the virtue of being more easily compared in Bruhat order by using the essential set.

A permutation has difference bounded by \(M\) if and only if \(s_\alpha(a-M,a) = s_{\alpha^{-1}}(a-M,a) = 0\) for all \(a \in \ZZ\). Denote the group of such permutations by \(B_M\). Then using again the fact that, if \(\chi_\alpha= \chi_\beta\), then \(\alpha \leq \beta\) is equivalent to \(\alpha^{-1} \leq \beta^{-1}\), it follows that \(B_M\) is closed downwards. Thus so is the union of all the \(B_M\). So the group of permutations of bounded difference is closed under \(\star\) and \(\triangleleft\).

In fact, we can say a bit more: if \(\alpha \in B_{M_1}\) and \(\beta \in B_{M_2}\), then the permutations \(\alpha_1, \beta_1\) in the proof of Lemma 24 lie in \(B_{M_1}\) and \(B_{M_2}\), respectively. It follows that \(\alpha \star \beta = \alpha_1 \beta\) and \(\alpha \triangleleft\beta = \alpha \beta_1\) both must lie in \(B_{M_1+M_2}\). So the bound on the difference cannot grow too quickly under \(\star\) and \(\triangleleft\).

8.2 Symmetric groups↩︎

To study symmetric groups, it is useful to first examine somewhat larger groups, of which symmetric groups may be formed as intersections.

Equivalently, \(\alpha \in F_M\) if and only if \(s_\alpha(M,M) = s_{\alpha^{-1}}(M,M) = 0\). This implies

Now, \(S_d = \bigcap_{M \leq 1} F_M \cap \bigcap_{M \geq d+1} F_M\) and therefore

As promised in the introduction, we can conveniently restrict arguments to \(s_\alpha\) to the set \([1,d+1]\) when working in \(S_d\).

Of course, one often want to work with elements of \(S_d\) via their reduced words, i.e. factorization into simple transpositions (or “bubble-sorts”). We can formulate the necessary tools here somewhat generally, so we do so for later use. In the following statements, recall the notation \(\sigma_S\) from Definition [defn:simpleInv] for a product of simple transpositions.

So Demazure products and residuals may be conveniently computed by factoring one of the permutations into adjacent transpositions, and this can also be slightly “parallelized” by considering many non-overlapping adjacent transpositions at once. Theorem [thm:alphaStarSigma] implies the last sentences of Theorems [thm:starExists] and [thm:resL] from the introduction, by taking \(S = \{n\}\).

8.3 Permutations with finitely many inversions↩︎

Let \(G\) denote the group of permutations \(\alpha\) such that \(\operatorname{Inv}(\alpha)\) is finite. Alternatively, \(G\) is the semidirect product \(S_\ZZ \rtimes \ZZ\) of the symmetric group of \(S_\ZZ\) of permutations fixing all but finitely many integers with the group \(\ZZ \cong \{\iota_\chi: \chi \in \ZZ\}\) of shift permutations. Then \(G\) is closed under \(\triangleleft\) in a strong sense: for any \(\alpha \in G\) and \(\beta \in \operatorname{ASP}\) (not necessarily in \(G\)), \(\alpha \triangleleft\beta \in G\). This is because \(\alpha \triangleleft\beta \leq_R \alpha\) (Lemma 18), so \(\operatorname{Inv}((\alpha \triangleleft\beta)^{-1}) \subseteq \operatorname{Inv}(\alpha^{-1})\) is finite.

This group is also closed downward, and therefore closed under \(\star\). This can be seen from a quick induction argument. If \(\alpha \leq_\chi\beta\), and \(\operatorname{Inv}(\beta) \neq \emptyset\), then there exists some adjacent inversion \((n,n+1) \in \operatorname{Inv}(\beta)\). Then \(\alpha \triangleleft\sigma_n \leq \beta \triangleleft\sigma_n\). Theorem [thm:alphaStarSigma] implies that \(\beta \triangleleft\sigma_n = \beta \sigma_n\) has one fewer inversion, and \(\alpha \triangleleft\sigma_n\) is either \(\alpha\) or \(\alpha \sigma_n\), which either both have finitely many inversions or both do not. In the base case, if \(\beta\) has no inversions, then \(\beta = \iota_{\chi_\beta}\), so \(\alpha = \iota_{\chi_\beta}\) as well.

In fact, with just a bit more care the inductive argument above shows the subword property [6]: if \(\beta = \iota_\chi \sigma_{n_1} \cdots \sigma_{n_\ell}\), where \(\ell = \# \operatorname{Inv}(\beta)\), and \(\alpha \leq_\chi\beta\), then there exists a subsequence \(1 \leq i_1 < \cdots < i_m \leq \ell\) such that \(\alpha = \iota_\chi \alpha_{i_1} \cdots \alpha_{i_m}\) and \(m = \# \operatorname{Inv}(\alpha)\). In particular, \(\# \operatorname{Inv}(\alpha) \leq \# \operatorname{Inv}(\beta)\). This fact provides quick proofs of the following two inequalities. If both \(\alpha,\beta\) have finitely many inversions, then \[\# \operatorname{Inv}(\alpha \star \beta) \leq \# \operatorname{Inv}(\alpha) + \# \operatorname{Inv}(\beta)and\# \operatorname{Inv}(\alpha \triangleleft\beta) \geq \# \operatorname{Inv}(\alpha) - \# \operatorname{Inv}(\beta).\] For the first, write \(\alpha \star \beta = \alpha_1 \beta\), with \(\alpha_1 \leq \alpha\) (Theorem [thm:starGreedy]). Equality holds if and only if \(\alpha \mathbin{{\star}_{\mathrm{red}}}\beta\). For the second, write \(\alpha \triangleleft\beta = \alpha \beta_1\) with \(\beta_1 \leq \beta\) (Theorem [thm:resLStingy]). Equality holds if and only if \(\beta^{-1} \leq_L \alpha\).

The stronger form of closure under \(\triangleleft\) allows the following strong form of the reduction theorem. This follows from the second paragraph of Theorem [thm:reduce].

Observe also that permutations with finitely many inversions must also have bounded difference and finite essential set.

8.4 The (extended) affine symmetric groups↩︎

Fix an integer \(k \geq 2\). The extended affine symmetric group of modulus \(k\) is the group of permutations \(\alpha\) such that \(\alpha(n+k) = \alpha(n) + k\) for all \(n \in \ZZ\). This condition is equivalent to \(\iota_k \alpha \iota_{-k} = \alpha\), and therefore is equivalent to the condition \[s_\alpha(a,b) = s_\alpha(a+k,b+k)for alla,b \in \ZZ.\] See for example [6] for background on affine symmetry groups. In particular, see [6] for discussion of functions like the slipfaces \(s_\alpha\) of the present paper in the context of these groups.

It is immediate from the definitions of \(\star\) and \(\triangleleft\) that if \(s_\alpha, s_\beta\) satisfy this condition, then so does \(s_{\alpha \star \beta}\). So the extended affine symmetric group is closed under \(\star\) and \(\triangleleft\). As mentioned in Example [eg:extAffine], the affine symmetric group \(\widetilde{S}_k\) is the subgroup of the shift-\(0\) permutations in the extended affine symmetric group. Since shift-\(0\) permutations are closed under \(\star\) and \(\triangleleft\), so is \(\widetilde{S}_k\).

The affine symmetric group \(\widetilde{S}_k\) is generated by the permutations \(\widetilde{\sigma}_n = \sigma_{n + k \ZZ}\) (one quick way to see this is to define the length of \(\alpha \in \widetilde{S}_k\) to be the number of inversions \((m,n)\) with \(0 \leq m < k\), and show that this is finite and, if positive, can be reduced by multiplying by some \(\widetilde{\sigma}_n\)). Therefore the operations \(\star\) and \(\triangleleft\) can be easily computed via factorization into the elements \(\widetilde{\sigma}_n\), using Theorem [thm:alphaStarSigma]. If \(S = n + k \ZZ\) in the theorem statement, and \(\alpha \in \widetilde{S}_k\), then one of \(S_1, S_2\) is empty, so one of \(\alpha \star \widetilde{\sigma}_n, \alpha \triangleleft\widetilde{\sigma}_n\) is \(\alpha \widetilde{\sigma}_n\), and the other is \(\alpha\), according to whether or not \(\alpha(n) < \alpha(n+1)\).

Since \(\widetilde{S}_k\) is a Coxeter group, this description of \(\star\) and \(\triangleleft\) is known, so there is nothing novel here except verifying that the standard definition of these operations in a Coxeter group accords with the definition on \(\operatorname{ASP}\) via Equation 5 .

9 A geometric interpretation of the min-plus formula for \(\star\)↩︎

The Demazure product on \(S_d\) arises naturally in the geometry of flag varieties and Schubert calculus; we briefly summarize a situation that provides useful intuition for Equation 5 . This discussion parallels the discussion in [9], although the notation is different.

Elements of \(S_d\) can be used to measure the “distance” between two complete flags in an \(n\)-dimensional vector space; the identity permutation corresponds to identical flags, and the descending permutation to transverse flags. Let \(H\) be a \(d\)-dimensional vector space. Let \(U_\sbu = (U_a)_{0 \leq a \leq d}, V_\sbu = (V_b)_{0 \leq b \leq d}\) be two complete flags in \(H\), indexed by dimension. There exists a unique permutation \(\sigma = \sigma(U_\sbu, V_\sbu)\) such that for all \(0 \leq a,b \leq d\), \[\label{eq:suv} \dim U_a \cap V_b = \# \{ n \leq b: \sigma(n) \leq a \} = a - s_\sigma(a+1,b+1).\tag{22}\] Note that this definition of \(\sigma(U_\sbu, V_\sbu)\) differs from the one used in [9] and some other sources; we use it here to fit better the notation of this paper. Another description of \(\sigma\) is via adapted bases. A basis \(\cB\) is adapted to a flag \(U_\sbu\) if \(\cB \cap U_a\) is a basis for \(U_a\), for all \(0 \leq a \leq d\). It is always possible to find a basis \(\cB\) that is adapted to both of two given flags \(U_\sbu, V_\sbu\); this can be proved by an argument in Gaussian elimination. If this basis is ordered \(\{u_1, \cdots, u_d\}\) such that \(\{u_1, \cdots, u_b\}\) is a basis of \(V_b\) for all \(b\), then there is a unique permutation \(\sigma\) of \(\{1, \cdots, d\}\) such that for all \(a\), \(\{ u_{\sigma(1)}, \cdots, u_{\sigma(a)} \}\) is a basis for \(U_a\). Then \(U_a \cap V_b\) has basis \(\{ u_i: i \leq b and \sigma(i) \leq a\}\), and Equation 22 follows.

For example, if \(U_\sbu = V_\sbu\), then \(\dim U_a \cap V_b = \min(a,b)\), so \[s_\sigma(a,b) = a-1-\min\{a-1,b-1\} = \max \{0,a-b\},\] and \(\sigma(U_\sbu, V_\sbu)\) is the identity permutation. At the other extreme, if the flags are transverse then \(\dim U_a \cap V_b = \max\{0,a + b - d\}\) and \(\sigma(U_\sbu, V_\sbu)\) is the descending permutation.

The Demazure product answers the question: given three flags \(U_\sbu, V_\sbu, W_\sbu\) and two permutations \(\alpha, \beta\), if \(\sigma(U_\sbu, V_\sbu) = \alpha\) and \(\sigma(V_\sbu,W_\sbu) = \beta\), then what is the Bruhat-maximum of all possible \(\sigma(U_\sbu, W_\sbu)\)?

To see why the Demazure product answers this question, note that for all \(a,b,\ell \in \{0,\cdots, d\}\), \[\dim U_a \cap W_b \geq \dim U_a \cap V_\ell \cap W_b \geq \dim U_a \cap V_\ell + \dim V_\ell \cap W_b - \dim V_\ell.\] In the notation of slipface functions, this may be rewritten, after subtracting both sides from \(a\), as \[s_{\sigma(U_\sbu, W_\sbu)}(a+1,b+1) \leq s_{\sigma(U_\sbu, V_\sbu)}(a+1,\ell+1) + s_{\sigma(V_\sbu, W_\sbu)}(\ell+1,b+1).\]

Taking the maximum over \(\ell \in \{0, \cdots, d\}\), Corollary [cor:SdMin] gives \[\sigma(U_\sbu, W_\sbu) \leq \sigma(U_\sbu, V_\sbu) \star \sigma(V_\sbu, W_\sbu).\] In fact, for “generic” choices of flags, equality is obtained (see e.g. [9]).

The discussion in this section can be generalized, with some care, from \(S_d\) to \(\operatorname{ASP}\) if one considers infinite flags, indexed by \(\ZZ\), in an infinite-dimensional vector space. Rather than expressing the dimension of \(U_a \cap V_b\) as \(a - s_\sigma(a+1,b+1)\), we may write \(\operatorname{rank} \left( U_a \to H / V_b \right) = s_{\sigma}(a+1,b+1)\), which is applicable in this infinite-dimensional setting provided that these ranks are all finite.

10 Applications to curves and graphs↩︎

This paper originated in service of applications to Brill-Noether theory of curves and graphs. We summarize the basic ideas without full details in this appendix to motivate the content of this paper; for more details the reader may consult the references mentioned. This appendix assumes vocabulary from algebraic curves and the divisor theory of metric graphs. The basic goal in both settings is to provide a toolkit for inductive arguments, in which the geometry of a curve or graph with two marked points is reduced to the geometry of two such curves/graphs that are glued at a single point.

Applications to algebraic curves are developed in [21]. Let \(C\) be a smooth projective algebraic curve over an algebraically closed field, and let \(p,q\) be two distinct points on \(C\). Then a line bundle \(\cL\) on \(C\) determines a permutation \(\tau = \tau_\cL^{p,q}\) by \[\begin{align} \label{eq:tauL} h^0(\cL(ap-bq)) &=& \# \{ n \geq b:\;\tau(n) \leq a \}\\ &=& s_\tau(a+1,b). \end{align}\tag{23}\]

The existence of \(\tau\) follows from Proposition [prop:alphaExists], which also proves that \(\tau\) has bounded difference. The submodularity of \(s_\tau\) amounts to the following linear algebraic observation. \[h^0(\cL) - h^0(\cL(-p)) - h^0(\cL(-q)) + h^0(\cL(-p-q)) = \dim H^0(\cL) / \left[ H^0(\cL(-p)) + H^0(\cL(-q)) \right] \geq 0\] Call \(\tau^{p,q}_\cL\) the transmission permutation of \(\cL\) with respect to \(p,q\). The shift of \(\tau^{p,q}_\cL\) is given by the Euler characteristic as \(\chi_\tau = \chi(\cL)-1 = d-g\), where \(d = \deg \cL\) and \(g\) is the genus of \(C\). Reversing this process, we may define for any \(\tau \in \operatorname{ASP}\) a transmission locus \[W^\tau(C,p,q) = \{ [\cL] \in \Pic^{\chi_\tau + g}(C):\;\tau^{p,q}_\cL \geq \tau \}.\] In particular, for any choice of \(r,d\), we may consider the permutation \(\gamma = \gamma^{g-d+r}_{r+1}\) from Example [eg:bnPerm], for which \(\chi_\gamma = d-g\) and \(\mathop{\mathrm{Ess}}(\gamma) = \{(1,0)\}\). Therefore \[\begin{align} W^\gamma(C,p,q) &=& W^r_d(C)\\ &:=& \{ [\cL] \in \Pic^d(C):\;h^0(C,\cL) \geq r+1 \}. \end{align}\] This locus is called a Brill–Noether locus. These loci play a central role in the theory of algebraic curves. So these transmission loci provide a reframing, and generalization, of Brill–Noether loci.

In another direction, there has been substantial recent interest in Hurwitz–Brill–Noether theory, which concerns the classification of line bundles on a general \(k\)-gonal curve of genus \(g\). See for example [22] and the references therein. The principal objects of study are splitting loci \(W^{\vec{e}}(C)\), for \(k\)-gonal curves \(C\). Transmission loci are a useful tool for studying these loci in a special case: if \((C,p,q)\) is a \(k\)-gonal curve with \(p,q\) points of total ramification for the degree-\(k\) cover \(\pi: C \to \PP^1\), then for every splitting type \(\vec{e}\) there exists an extended \(k\)-affine permutation \(\gamma_{\vec{e}}\) such that \[W^{\gamma_{\vec{e}}}(C,p,q) = W^{\vec{e}}(C).\]

The utility of this reframing is that transmission loci are very well-suited to induction arguments, once the Demazure product is in hand. The construction of transmission permutations and transmission loci can be generalized in a natural way to chains of smooth curves. The Demazure product provides a “gluing” operation. Precisely, if \((C_1, p_1, q_1), (C_2,p_2,q_2)\) are two twice-marked smooth curves, \(X~=~C_1~\cup~C_2\) is the nodal curve obtained by gluing \(q_1\) to \(p_2\), and \(\cL\) is a line bundle on \(X\) restricting to \(\cL_1\) on \(C_1\) and \(\cL_2\) on \(C_2\), then \[\label{eq:glueCurves} \tau_\cL^{p_1, q_2} = \tau_{\cL_1}^{p_1, q_1} \star \tau_{\cL_2}^{p_2,q_2}.\tag{24}\]

In other words, the transmission locus on a union of two curves (or chains of curves) decomposes: \[\label{eq:WtauDecomp} W^\tau(C, p_1, q_2) = \bigcup_{\alpha \star \beta \geq \tau} W^\alpha(C_1, p_1, q_1) \times W^\beta(C_2, p_2, q_2).\tag{25}\] This union is indexed over quite a large set: all pairs of permutations \(\alpha, \beta \in \operatorname{ASP}\) with these shifts such that \(\alpha \star \beta \geq \tau\). The utility of the reduction Theorem [thm:reduce] is to shrink this to a finite union of pieces that all have the same expected dimension. Namely, \[\label{eq:WtauRedDecomp} W^\tau(C, p_1, q_2) = \bigcup_{\alpha \mathbin{{\star}_{\mathrm{red}}}\beta = \tau} W^\alpha(C_1, p_1, q_1) \times W^\beta(C_2, p_2, q_2).\tag{26}\] We have omitted the constraints on \(\chi_\alpha,\chi_\beta\) from the notation for simplicity. Equation 26 now provides a convenient inductive tool for analyzing both

1. local geometry of transmission loci, and thereby Brill–Noether loci, and

2. enumerative aspects of transmission loci, and thereby Brill–Noether loci.

In particular, [21] uses this perspective to obtain a new proof of the classical Brill–Noether theorem and the main dimension upper bound of Hurwitz–Brill–Noether theory within a single framework.

A completely parallel story may be developed for finite graphs, and also for metric graphs. Details and applications can be found in [8], [23]. Let \(G\) be either a graph or metric graph, and \(p,q\) two distinct vertices on \(G\). If \(D\) is a divisor on \(G\), then we may associate a slipface function to \(D\), by \[\label{eq:tauD} s_D^{p,q}(a,b) = r(D + (a+1)p - bq) + 1.\tag{27}\] Here \(r\) is the Baker-Norine rank. As in the curve case, the shift of this slipface is \(d-g\). Unfortunately, this slipface need not be submodular (though it is always Clifford), so there may not be a well-defined “transmission permutation.” The problem, compared to algebraic curves, is that the Baker-Norine rank is not the dimension of a vector space. However, it appears that in many cases, such as chains of loops, all divisors do have submodular slipfaces.

In either case, this slipface still satisfies an easy-to-remember gluing equation. Let \(G_1\) be a (metric) graph with two points \(p_1, q_1\), and \(G_2\) a (metric) graph with two points \(p_2, q_2\). Let \(G\) be obtained by gluing \(q_1\) to \(p_2\). Then for any pair of divisors \(D_1\) on \(G_1\), \(D_2\) on \(G_2\), if we let \(D\) denote the sum of these two divisors on \(G\), then the analog of Equation 24 holds for (metric) graphs: \[\label{eq:glueGraphs} s_D^{p_1, q_2} = s_{D_1}^{p_1,q_1} \star s_{D_2}^{p_2, q_2}.\tag{28}\] This framework now provides a tool for the Brill–Noether theory of chains of graphs, in the same fashion as for chains of curves.

The paper [8] studies this situation in a simple case: chains of twice marked loops, all of the same torsion order. This situation is somewhat simple, in that all transmission permutations involved belong to the same extended affine symmetric group. The stronger results in this paper make somewhat more subtle arguments possible, in which different torsion orders are used in a chain, and therefore it is necessary to intermingle extended affine permutations of different moduli. This is carried out, for example, in [23] to construct new families of Brill–Noether general graphs.

Acknowledgements↩︎

This work was supported by a Miner D. Crary Sabbatical Fellowship from Amherst College, and the author was hosted by the Max Planck Institute for Mathematics in the Sciences during revisions and the Lean formalization process. I am grateful to Will Erickson, Darij Grinberg, Allen Knutson, Thomas Lam, Leonardo Mihalcea, Travis Scrimshaw, and Mark Shimozono for references and suggestions, and to Alex Tiskin for directing me to his original proof of the min-plus formula for the Demazure product on symmetric groups.

References↩︎