Introduction
Let h = ( h ( 1 ) , … , h ( n ) ) h=(h(1),\ldots,h(n)) h = ( h ( 1 ) , … , h ( n )) i ≤ h ( i ) ≤ n i\le h(i)\le n i ≤ h ( i ) ≤ n natural unit interval graph has vertex set [ n ] = { 1 , … , n } [n]=\{1,\ldots,n\} [ n ] = { 1 , … , n }
E ( G ) = { { i , j } : i < j ≤ h ( i ) } . E(G)=\{\{i,j\}:i<j\le h(i)\}. E ( G ) = {{ i , j } : i < j ≤ h ( i )} . These are also called naturally labeled Dyck graphs. A proper coloring is a map f : [ n ] → N > 0 f:[n]\to\mathbb{N}_{>0} f : [ n ] → N > 0 X = ( x 1 , x 2 , … ) X=(x_1,x_2,\ldots) X = ( x 1 , x 2 , … )
χ G ( X ; q ) = ∑ f p r o p e r q asc G ( f ) ∏ a = 1 n x f ( a ) , asc G ( f ) = # { { a , b } ∈ E ( G ) : a < b , f ( a ) < f ( b ) } . (1) \chi_G(X;q)=\sum_{f\ \mathrm{proper}}q^{\operatorname{asc}_G(f)}\prod_{a=1}^{n}x_{f(a)},\qquad\operatorname{asc}_G(f)=\#\{\{a,b\}\in E(G):a<b,\ f(a)<f(b)\}. \tag*{(1)} χ G ( X ; q ) = f proper ∑ q asc G ( f ) a = 1 ∏ n x f ( a ) , asc G ( f ) = # {{ a , b } ∈ E ( G ) : a < b , f ( a ) < f ( b )} . (1) Shareshian and Wachs proved that this function is symmetric for this graph class and conjectured that its coefficients in the elementary basis belong to N [ q ] \mathbb{N}[q] N [ q ] [37 ] . Here e k ( X ) = ∑ i 1 < ⋯ < i k x i 1 ⋯ x i k e_k(X)=\sum_{i_1<\cdots<i_k}x_{i_1}\cdots x_{i_k} e k ( X ) = ∑ i 1 < ⋯ < i k x i 1 ⋯ x i k e λ = ∏ i e λ i e_\lambda=\prod_i e_{\lambda_i} e λ = ∏ i e λ i λ \lambda λ
The coefficients admit a more precise interpretation in terms of permutations. Define
D G 0 = { σ ∈ S n : σ i > σ i + 1 ⇒ { σ i , σ i + 1 } ∈ E ( G ) } , D_G^0=\{\sigma\in S_n:\sigma_i>\sigma_{i+1}\mathrel{\Rightarrow}\{\sigma_i,\sigma_{i+1}\}\in E(G)\}, D G 0 = { σ ∈ S n : σ i > σ i + 1 ⇒ { σ i , σ i + 1 } ∈ E ( G )} , ginv G ( σ ) = # { ( i , j ) : i < j , σ i > σ j , { σ i , σ j } ∈ E ( G ) } . \operatorname{ginv}_G(\sigma)=\#\{(i,j):i<j,\ \sigma_i>\sigma_j,\ \{\sigma_i,\sigma_j\}\in E(G)\}. ginv G ( σ ) = # {( i , j ) : i < j , σ i > σ j , { σ i , σ j } ∈ E ( G )} . Thus D G 0 D_G^0 D G 0 ginv G \operatorname{ginv}_G ginv G
Theorem 1.1 (Elementary positivity and a permutation witness). There is a deterministic terminating procedure which, given a natural unit interval graph G G G [ n ] [n] [ n ] σ ∈ D G 0 \sigma\in D_G^0 σ ∈ D G 0 θ G ( σ ) ⊢ n \theta_G(\sigma)\vdash n θ G ( σ ) ⊢ n
χ G ( X ; q ) = ∑ σ ∈ D G 0 q ginv G ( σ ) e θ G ( σ ) ( X ) . (2) \chi_G(X;q)=\sum_{\sigma\in D_G^0}q^{\operatorname{ginv}_G(\sigma)}e_{\theta_G(\sigma)}(X). \tag*{(2)} χ G ( X ; q ) = σ ∈ D G 0 ∑ q ginv G ( σ ) e θ G ( σ ) ( X ) . (2) In particular every elementary coefficient of χ G ( X ; q ) \chi_G(X;q) χ G ( X ; q ) N [ q ] \mathbb{N}[q] N [ q ] n n n G G G
This proves the elementary-positivity part of the Shareshian–Wachs conjecture. The theorem makes no assertion of elementary unimodality. The construction specifies a map on individual inputs: it does not take the elementary coefficient list as input and redistribute permutations according to that list. Its running time may nevertheless be large.
For example, let G G G 1 1 1 2 2 2 3 3 3
χ G ( X ; q ) = q e ( 2 , 1 ) ( X ) + ( 1 + q + q 2 ) e ( 3 ) ( X ) . \chi_G(X;q)=q e_{(2,1)}(X)+(1+q+q^2)e_{(3)}(X). χ G ( X ; q ) = q e ( 2 , 1 ) ( X ) + ( 1 + q + q 2 ) e ( 3 ) ( X ) . Write m λ m_{\lambda} m λ λ \lambda λ q m ( 2 , 1 ) ( X ) q m_{(2,1)}(X) q m ( 2 , 1 ) ( X ) ( 1 + 4 q + q 2 ) m ( 1 , 1 , 1 ) ( X ) (1+4q+q^2)m_{(1,1,1)}(X) ( 1 + 4 q + q 2 ) m ( 1 , 1 , 1 ) ( X ) e ( 2 , 1 ) = m ( 2 , 1 ) + 3 m ( 1 , 1 , 1 ) e_{(2,1)}=m_{(2,1)}+3m_{(1,1,1)} e ( 2 , 1 ) = m ( 2 , 1 ) + 3 m ( 1 , 1 , 1 ) e ( 3 ) = m ( 1 , 1 , 1 ) e_{(3)}=m_{(1,1,1)} e ( 3 ) = m ( 1 , 1 , 1 ) D G 0 D_G^0 D G 0 ( 2 , 1 ) (2,1) ( 2 , 1 ) ( 3 ) (3) ( 3 ) (1.3) alone does not specify which of 132 and 213 receives which partition; the procedure in Section 6 makes that individual choice.
The positivity question is difficult because the coloring definition already has nonnegative coefficients in the monomial variables, whereas rewriting it in the elementary basis can involve subtraction. Our proof separates this issue from the individual assignment. It first identifies each relevant elementary coefficient with a positive algebraic object. It then realizes the algebraic identities by finite bijections between ordered collections of independent sets. Neither stage uses the sought elementary coefficient list as input to the permutation rule.
History and significance
The problem grew out of positivity questions for immanants of Jacobi–Trudi matrices, studied by Haiman and by Stanley and Stembridge [24 , 41 ] . Stanley introduced the chromatic symmetric function as a symmetric-function refinement of the chromatic polynomial [39 ] ; it is the specialization of Equation (1) at q = 1 q=1 q = 1 ( 3 + 1 ) (3+1) ( 3 + 1 ) [41 ] , Conjecture 5.5}. The incomparability graph joins two elements exactly when neither is below the other. A poset is ( 3 + 1 ) (3+1) ( 3 + 1 ) [22 ] , Theorem 5.1}. Their naturally labeled incomparability graphs are the graphs in Theorem 1.1. Specializing our theorem at q = 1 q=1 q = 1 [26 ] .
Positive expansions in other bases provided important earlier structure. Haiman’s immanant results imply Schur positivity for incomparability graphs of ( 3 + 1 ) (3+1) ( 3 + 1 ) [24 ] ; Gasharov gave a positive formula using poset tableaux [17 ] . Chow’s quasisymmetric expansion related chromatic symmetric functions to permutation descents [8 ] . Shareshian and Wachs introduced the q q q (1) , proved its symmetry and Schur positivity for natural unit interval graphs, and formulated the elementary-positivity and elementary-unimodality conjecture [36 , 37 ] . Their acyclic-orientation formula gives elementary coefficients after grouping partitions by their number of parts [37 ] , Theorem 5.3}; Athanasiadis supplied a power-sum expansion [2 ] . These descriptions do not determine a nonnegative coefficient formula for each elementary partition.
The geometric connection gives another reason to study the q q q [42 ] , and Shareshian and Wachs related their chromatic functions conjecturally to the graded representation on regular semisimple Hessenberg varieties [36 , 37 ] . Brosnan–Chow and Guay-Paquet proved this representation-theoretic identity [6 , 23 ] . That result is distinct from the elementary-positivity assertion addressed here. Geometric, combinatorial and algebraic approaches subsequently established positivity for substantial families: abelian Hessenberg varieties [25 ] , classes treated by explicit elementary expansions [7 ] , melting lollipops [27 ] , and the q q q [10 ] . The modular law also provided a systematic tool for organizing chromatic functions and their relations [1 ] .
Hikita’s proof uses a probabilistic formula [26 ] . His formula gives numerical nonnegativity for every positive real q q q q q q N [ q ] \mathbb{N}[q] N [ q ] [26 ] , Section 1.3. Griffin, Mellit, Romero, Weigl and Wen gave an independent proof through Macdonald expansions, recovering Hikita’s elementary formula [19 ] . Further developments include positivity at q = 1 q = 1 q = 1 g g g [28 ] , Chow’s combinatorial interpretation of the probabilities [9 ] , and lower bounds for elementary coefficients studied by Siegl [38 ] . Theorem 1.1 gives a formal polynomial formula with nonnegative integer coefficients and an individual assignment preserving the specified graph-inversion weight.
The representation identity and Theorem 1.1 give the following degreewise consequence.
Corollary 1.2 (Young permutation modules in Hessenberg cohomology). Let n ≥ 1 n \ge1 n ≥ 1 h h h G = G ( h ) G = G(h) G = G ( h ) S ∈ M n ( C ) S \in M_n(\mathbb{C}) S ∈ M n ( C )
Hess ( S , h ) = { F ∙ ∈ Flag ( C n ) : S F i ⊆ F h ( i ) for all i } . \operatorname{Hess}(S,h)=\{F_{\bullet}\in\operatorname{Flag}(\mathbb{C}^{n}):SF_i\subseteq F_{h(i)}\text{ for all }i\}. Hess ( S , h ) = { F ∙ ∈ Flag ( C n ) : S F i ⊆ F h ( i ) for all i } . For λ = ( λ 1 , … , λ ℓ ) ⊢ n \lambda= (\lambda_1,\ldots,\lambda_{\ell}) \vdash n λ = ( λ 1 , … , λ ℓ ) ⊢ n M λ = Ind S λ S n 1 C M^{\lambda} = \operatorname{Ind}_{S_{\lambda}}^{S_n} \mathbf{1}_{\mathbb{C}} M λ = Ind S λ S n 1 C S λ = S λ 1 × ⋯ × S λ ℓ S_{\lambda} = S_{\lambda_1} \times\cdots\times S_{\lambda_{\ell}} S λ = S λ 1 × ⋯ × S λ ℓ
m λ , d ( h ) = # { σ ∈ D G 0 : θ G ( σ ) = λ , ginv G ( σ ) = d } . m_{\lambda,d}(h)=\#\{\sigma\in D_G^0:\theta_G(\sigma)=\lambda,\ \operatorname{ginv}_G(\sigma)=d\}. m λ , d ( h ) = # { σ ∈ D G 0 : θ G ( σ ) = λ , ginv G ( σ ) = d } . Then for every integer d ≥ 0 d \ge0 d ≥ 0 C [ S n ] \mathbb{C}[S_n] C [ S n ]
H 2 d ( Hess ( S , h ) ; C ) ≅ ⨁ λ ⊢ n ( M λ ) ⊕ m λ , d ( h ) . H^{2d}(\operatorname{Hess}(S,h);\mathbb{C})\cong\bigoplus_{\lambda\vdash n}(M^{\lambda})^{\oplus m_{\lambda,d}(h)}. H 2 d ( Hess ( S , h ) ; C ) ≅ λ ⊢ n ⨁ ( M λ ) ⊕ m λ , d ( h ) . Proof. Write ch \operatorname{ch} ch ω \omega ω ω ( e λ ) = h λ \omega(e_{\lambda}) = h_{\lambda} ω ( e λ ) = h λ [6 ] and Guay-Paquet [23 ] , followed by Equation (2) , gives
ch H 2 d ( Hess ( S , h ) ; C ) = [ q d ] ω χ G ( X ; q ) = ∑ λ ⊢ n m λ , d ( h ) h λ . \operatorname{ch} H^{2d}(\operatorname{Hess}(S,h);\mathbb{C})=[q^d]\omega\chi_G(X;q)=\sum_{\lambda\vdash n}m_{\lambda,d}(h)h_{\lambda}. ch H 2 d ( Hess ( S , h ) ; C ) = [ q d ] ω χ G ( X ; q ) = λ ⊢ n ∑ m λ , d ( h ) h λ . Since ch M λ = h λ \operatorname{ch}M^{\lambda}=h_{\lambda} ch M λ = h λ [6 ] , proof of Proposition 10, injectivity of the Frobenius characteristic and complete reducibility of finite-dimensional complex S n S_n S n
There is also a direct precedent for asking for a partition-valued permutation rule. Stanley and Stembridge proposed such an assignment on their compatible permutations [41 ] , Remark 5.6. That proposal concerns the ungraded elementary expansion. The rule here retains the full graph-inversion degree and specifies a terminating procedure on each input. The finite cancellation used to pass from required ascents to exact ascents belongs to the bijective-cancellation tradition represented by the Garsia–Milne involution principle [16 ] .
Our algebraic reduction likewise has substantial antecedents. Stanley’s graph specialization [40 ] , Section 2, chromatic functions in noncommuting variables [18 ] , and the noncommutative symmetric-function methods of Fomin–Greene and Blasiak–Fomin [3 ] , [14 ] provide a framework for commuting symmetric expressions inside a noncommutative algebra. Hwang’s noncommutative P P P [29 ] and the poset algebras of Blasiak, Eriksson, Pyrlyavskyy and Siegl [4 ] provide direct predecessors of the graph-alphabet evaluation and its elementary/monomial coefficient pairing. We give a short proof in the centered quantum torus conventions needed for the subsequent argument.
The positive factorization and transport stages use the mathematical framework of Hall algebras and scattering diagrams. Ordered slope factorization and polynomial shuffle products were developed in [31 , 34 ] , with semistable quotient and integrality results in [12 , 13 , 15 ] . The connection from Hall factorization to wall transformations appears in Reineke’s Poisson automorphisms and Bridgeland’s stability scattering diagrams [5 , 35 ] . Scattering constructions originate in work of Kontsevich–Soibelman and Gross–Siebert [20 , 30 , 32 ] ; theta bases and mutation are central to the cluster framework of Gross–Hacking–Keel–Kontsevich [21 ] , and Davison–Mandel prove strong quantum positivity [11 ] . We prove the particular reordering, completion and transport statements needed here with their explicit gradings and finite coefficient bounds. The graph-specific step is then an identification: general positivity of theta sections does not itself show that a graph-alphabet monomial symmetric function is one such section. The triangular chart below proves that identity before the packet construction extracts the individual witness.
Proof structure
The first reduction replaces colorings by coefficients in an algebra whose monomials record vertex multiplicities. Write q = v 2 q=v^2 q = v 2 X m X_m X m m m m Γ \Gamma Γ G G G E k E_k E k k k k E k E_k E k e k ( Y ) e_k(Y) e k ( Y ) Y Y Y u u u M = ∣ E ( G ) ∣ M=\lvert E(G)\rvert M = ∣ E ( G )∣
[ e λ ( X ) ] χ G ( X ; v 2 ) = v M [ X u ] m λ ( Y ) . [e_\lambda(X)]\chi_G(X;v^2)=v^M[X_u]m_\lambda(Y). [ e λ ( X )] χ G ( X ; v 2 ) = v M [ X u ] m λ ( Y ) . Here m λ m_\lambda m λ
The central step is to identify m λ ( Y ) m_\lambda(Y) m λ ( Y ) Θ m \Theta_m Θ m d 1 , … , d D d_1,\ldots,d_D d 1 , … , d D λ \lambda λ D D D D D D
m λ ( Y ) = Θ λ 1 d 1 + ⋯ + λ D d D . m_\lambda(Y)=\Theta_{\lambda_1d_1+\cdots+\lambda_Dd_D}. m λ ( Y ) = Θ λ 1 d 1 + ⋯ + λ D d D . Repeated interval rotations establish this identity. A support argument using positive powers of E 1 E_1 E 1
The proof has three main components. First, positive quantum factors remain positive when their order is reversed. We realize the new multiplicities as dimensions of explicit graded vector spaces, and prove the coefficient bounds needed for all infinite series. Second, the interval rotations identify a family of graph symmetric functions with single positive theta sections. Together with (1.4) , this already proves coefficientwise elementary positivity. Third, we extract the individual assignment. After reversing an input permutation, we group vertices into packets, each an independent set written in increasing order. A local packet bijection transports them to subsets of the independent anchors and records weighted jumps. The total jump histories are independent of packet sizes. Finite matching cancellation refines required nonedge ascents of input words and required strict ascents of anchor words to exact sets of such positions. The empty set on the anchor side leaves a weakly decreasing word, whose multiplicities give the output partition. The finite matching argument supplies termination without consulting the desired final shape counts. Section 2 proves the coloring reduction and fixes permutation conventions. Section 3 proves the reordering result. Section 4 constructs the wall sections and proves their positivity and mutation rules. Section 5 establishes (1.5) , and Section 6 constructs the individual permutation map. Section 7 returns to the original graph and proves Theorem 1.1, including the reversal needed for the convention in D G 0 D^0_G D G 0
Graph alphabets and the coloring reduction
This section reduces the elementary expansion to coefficients of monomial symmetric functions evaluated in a quantum torus. It also fixes the permutation convention used by the transport construction.
Admissible words and insertion digits
For the graph G G G l a = # { b < a : { b , a } ∈ E ( G ) } l_a = \#\{b < a : \{b,a\} \in E(G)\} l a = # { b < a : { b , a } ∈ E ( G )} M = ∑ a l a M = \sum_a l_a M = ∑ a l a a a a [ a − 1 ] [a-1] [ a − 1 ]
A G = { w ∈ S n : w i < w i + 1 ⟹ { w i , w i + 1 } ∈ E ( G ) } . \mathcal{A}_G = \{w \in S_n : w_i < w_{i+1} \Longrightarrow\{w_i,w_{i+1}\} \in E(G)\}. A G = { w ∈ S n : w i < w i + 1 ⟹ { w i , w i + 1 } ∈ E ( G )} . We call these words admissible . Their forbidden adjacent pairs are nonedge ascents. Write inv G ( w ) \operatorname{inv}_G(w) inv G ( w ) ginv G \operatorname{ginv}_G ginv G
Lemma 2.1 (Insertion digits). There is a bijection between A G \mathcal{A}_G A G ( j 1 , … , j n ) (j_1,\ldots,j_n) ( j 1 , … , j n ) 0 ≤ j a ≤ l a 0 \le j_a \le l_a 0 ≤ j a ≤ l a inv G ( w ) = ∑ a j a \operatorname{inv}_G(w) = \sum_a j_a inv G ( w ) = ∑ a j a D G 0 → A G D^0_G \to\mathcal{A}_G D G 0 → A G
inv G ( reverse σ ) = M − ginv G ( σ ) . (3) \operatorname{inv}_G(\operatorname{reverse}\sigma) = M - \operatorname{ginv}_G(\sigma). \tag*{(3)} inv G ( reverse σ ) = M − ginv G ( σ ) . (3) Proof. Delete the largest letter a a a [ a ] [a] [ a ] b b b c c c b < a b < a b < a h ( b ) ≥ a > c h(b) \ge a > c h ( b ) ≥ a > c ( b , c ) (b,c) ( b , c ) a a a l a , l a − 1 , … , 0 l_a,l_a-1,\ldots,0 l a , l a − 1 , … , 0 (3) .
The relation a < b a < b a < b { a , b } ∉ E ( G ) \{a,b\} \notin E(G) { a , b } ∈ / E ( G ) h ( a ) < b h(a) < b h ( a ) < b
The quantum torus of an ordered graph
For this subsection let Γ \Gamma Γ L Γ L_\Gamma L Γ
Ω ( b , a ) = { 1 , a < b and { a , b } ∈ E ( Γ ) , 0 , a < b and { a , b } ∉ E ( Γ ) , \Omega(b,a)=\begin{cases}
1, & a<b\text{ and }\{a,b\}\in E(\Gamma),\\
0, & a<b\text{ and }\{a,b\}\notin E(\Gamma),
\end{cases} Ω ( b , a ) = { 1 , 0 , a < b and { a , b } ∈ E ( Γ ) , a < b and { a , b } ∈ / E ( Γ ) , and extend by bilinearity and skew symmetry. Over Q ( ( v − 1 ) ) \mathbb{Q}((v^{-1})) Q (( v − 1 )) X m X_m X m m ∈ L Γ m\in L_\Gamma m ∈ L Γ
X m X m ′ = v Ω ( m , m ′ ) X m + m ′ . X_mX_{m'}=v^{\Omega(m,m')}X_{m+m'}. X m X m ′ = v Ω ( m , m ′ ) X m + m ′ . The coefficient field consists of Laurent series with bounded upper powers of v v v
For a set I I I a I = ∑ a ∈ I a a_I=\sum_{a\in I}a a I = ∑ a ∈ I a
E k ( Γ ) = ∑ I ⊆ V ( Γ ) independent ∣ I ∣ = k X a I , E 0 ( Γ ) = 1. (4) E_k(\Gamma)=\sum_{\substack{I\subseteq V(\Gamma)\ \text{independent}\\ |I|=k}}X_{a_I},\qquad E_0(\Gamma)=1. \tag*{(4)} E k ( Γ ) = I ⊆ V ( Γ ) independent ∣ I ∣ = k ∑ X a I , E 0 ( Γ ) = 1. (4) The graph alphabet used here is a centered quantum-torus version of noncommutative poset symmetric functions [4 , 29 ] . More precisely, on V ( Γ ) V(\Gamma) V ( Γ ) a < P b a<_P b a < P b a < b a<b a < b { a , b } \{a,b\} { a , b } [4 ] , (4) become our independent-set sums, and the relations in [4 ] , Definition 3.16 become the relations above under u a ↦ X a u_a\mapsto X_a u a ↦ X a t ↦ v 2 t\mapsto v^2 t ↦ v 2
Proposition 2.2 (Commuting independent-set sums). For every natural unit interval graph Γ \Gamma Γ and all j , k ≥ 0 j,k\geq0 j , k ≥ 0 E j ( Γ ) E k ( Γ ) = E k ( Γ ) E j ( Γ ) E_j(\Gamma)E_k(\Gamma)=E_k(\Gamma)E_j(\Gamma) E j ( Γ ) E k ( Γ ) = E k ( Γ ) E j ( Γ )
Proof. We adapt the two-color involution underlying [37 ] , Lemma 4.4 and Theorem 4.5. A term on the left is an ordered pair of independent sets ( I , J ) (I,J) ( I , J ) a I + a J a_I+a_J a I + a J v Ω ( a I , a J ) v^{\Omega(a_I,a_J)} v Ω ( a I , a J ) I ∩ J I\cap J I ∩ J I ∪ J I\cup J I ∪ J I ∖ J I\setminus J I ∖ J J ∖ I J\setminus I J ∖ I I ∪ J I\cup J I ∪ J I I I J J J
On every component with an odd number of vertices, exchange the two memberships; keep the even components and the doubled isolated vertices unchanged. Every even component has equally many vertices in the two sets. Every odd component reverses its size difference, so the new ordered pair ( I ′ , J ′ ) (I',J') ( I ′ , J ′ ) k , j k,j k , j Ω ( a I , a J ) \Omega(a_I,a_J) Ω ( a I , a J ) 1 1 1 − 1 -1 − 1 ( I , J ) (I,J) ( I , J )
Let α ( Γ ) \alpha(\Gamma) α ( Γ ) Γ \Gamma Γ α ( Γ ) ≤ D \alpha(\Gamma)\leq D α ( Γ ) ≤ D D D D e 1 , … , e D e_1,\ldots,e_D e 1 , … , e D e k ↦ E k ( Γ ) e_k\mapsto E_k(\Gamma) e k ↦ E k ( Γ ) E k = 0 E_k=0 E k = 0 k > D k>D k > D F F F F ( Y ) F(Y) F ( Y ) e k ( Y ) = E k e_k(Y)=E_k e k ( Y ) = E k Y Y Y y i y_i y i m λ ( Y ) m_\lambda(Y) m λ ( Y ) D D D m λ m_\lambda m λ λ \lambda λ
The elementary coefficient identity
Let G G G a 1 , … , a n a_1,\ldots,a_n a 1 , … , a n Γ \Gamma Γ u = a 1 + ⋯ + a n u=a_1+\cdots+a_n u = a 1 + ⋯ + a n f f f inv G ( f ) = # { a < b : { a , b } ∈ E ( G ) , f ( a ) > f ( b ) } \operatorname{inv}_G(f)=\#\{a<b:\{a,b\}\in E(G), f(a)>f(b)\} inv G ( f ) = # { a < b : { a , b } ∈ E ( G ) , f ( a ) > f ( b )} X G ( X ; q ) X_G(X;q) X G ( X ; q )
The following coefficient reduction is the elementary/monomial form of the noncommutative Cauchy pairing in [29 ] , Theorem 4.4, Corollary 4.5 and Proposition 4.25 and [4 ] , Proposition 2.9 and Corollary 2.10. We include its proof to fix the graph-inversion and centered-monomial factors.
Proposition 2.3 (Coloring kernel). If α ( Γ ) ≤ D \alpha(\Gamma)\le D α ( Γ ) ≤ D X G ( X ; q ) X_G(X;q) X G ( X ; q )
X G ( X ; v 2 ) = ∑ λ ⊢ n ℓ ( λ ) ≤ D v M [ X u ] m λ ( Y ) e λ ( X ) . X_G(X;v^2)=\sum_{\substack{\lambda\vdash n\\ \ell(\lambda)\le D}}v^M[X_u]m_\lambda(Y)e_\lambda(X). X G ( X ; v 2 ) = λ ⊢ n ℓ ( λ ) ≤ D ∑ v M [ X u ] m λ ( Y ) e λ ( X ) . The equality is independent of the extra vertices of Γ \Gamma Γ
Proof. Work first with r r r
∏ c = 1 r ( ∑ k = 0 D x c k E k ) . \prod_{c=1}^{r}\left(\sum_{k=0}^{D}x_c^kE_k\right). c = 1 ∏ r ( k = 0 ∑ D x c k E k ) . Its X u X_u X u + 1 +1 + 1 − 1 -1 − 1 2 inv G ( f ) − M 2\operatorname{inv}_G(f)-M 2 inv G ( f ) − M v M v^M v M X G ( x 1 , … , x r ; v 2 ) X_G(x_1,\ldots,x_r;v^2) X G ( x 1 , … , x r ; v 2 )
For ordinary variables y 1 , … , y D y_1,\ldots,y_D y 1 , … , y D
∏ c = 1 r ∏ i = 1 D ( 1 + x c y i ) = ∑ λ e λ ( x 1 , … , x r ) m λ ( y 1 , … , y D ) . \prod_{c=1}^{r}\prod_{i=1}^{D}(1+x_cy_i)=\sum_{\lambda}e_\lambda(x_1,\ldots,x_r)m_\lambda(y_1,\ldots,y_D). c = 1 ∏ r i = 1 ∏ D ( 1 + x c y i ) = λ ∑ e λ ( x 1 , … , x r ) m λ ( y 1 , … , y D ) . Indeed, select for each labeled y i y_i y i x x x y y y Y Y Y X u X_u X u v M v^M v M r r r □ \square □
Example 2.4 (The centered normalization on two vertices). Let Γ = G \Gamma=G Γ = G a < b a<b a < b E 2 = 0 E_2=0 E 2 = 0 m ( 2 ) ( Y ) = E 1 2 m_{(2)}(Y)=E_1^2 m ( 2 ) ( Y ) = E 1 2 X a + b X_{a+b} X a + b v + v − 1 v+v^{-1} v + v − 1 v M = v v^M=v v M = v X G ( X ; q ) = ( 1 + q ) e 2 ( X ) X_G(X;q)=(1+q)e_2(X) X G ( X ; q ) = ( 1 + q ) e 2 ( X ) E 2 = X a + b E_2=X_{a+b} E 2 = X a + b E 1 2 E_1^2 E 1 2 [ X a + b ] m ( 2 ) ( Y ) = [ X a + b ] ( E 1 2 − 2 E 2 ) = 0 [X_{a+b}]m_{(2)}(Y)=[X_{a+b}](E_1^2-2E_2)=0 [ X a + b ] m ( 2 ) ( Y ) = [ X a + b ] ( E 1 2 − 2 E 2 ) = 0 [ X a + b ] m ( 1 , 1 ) ( Y ) = [ X a + b ] E 2 = 1 [X_{a+b}]m_{(1,1)}(Y)=[X_{a+b}]E_2=1 [ X a + b ] m ( 1 , 1 ) ( Y ) = [ X a + b ] E 2 = 1 X G ( X ; q ) = e 1 ( X ) 2 X_G(X;q)=e_1(X)^2 X G ( X ; q ) = e 1 ( X ) 2 E k E_k E k
Lemma 2.5 (Color reversal and shape reciprocity). For every natural unit interval graph G G G X G ( X ; q ) = X G ( X ; q ) X_G(X;q)=X_G(X;q) X G ( X ; q ) = X G ( X ; q ) c λ ( q ) = [ e λ ] X G ( X ; q ) c_\lambda(q)=[e_\lambda]X_G(X;q) c λ ( q ) = [ e λ ] X G ( X ; q )
c λ ( q ) = q M c λ ( q − 1 ) c_\lambda(q)=q^M c_\lambda(q^{-1}) c λ ( q ) = q M c λ ( q − 1 ) for every partition λ \lambda λ Proof. Use r r r f f f r + 1 − f r+1-f r + 1 − f Γ = G \Gamma=G Γ = G X G = χ G X_G=\chi_G X G = χ G asc G ( f ) + inv G ( f ) = M \operatorname{asc}_G(f)+\operatorname{inv}_G(f)=M asc G ( f ) + inv G ( f ) = M X G ( X ; q ) = q M X G ( X ; q − 1 ) X_G(X;q)=q^M X_G(X;q^{-1}) X G ( X ; q ) = q M X G ( X ; q − 1 ) r ≥ n r\ge n r ≥ n n n n (2.6) .
It now suffices to prove positivity of [ X u ] m λ ( Y ) [X_u]m_\lambda(Y) [ X u ] m λ ( Y ) D D D D − 1 D-1 D − 1 D D D
Positive reordering in a quantum torus
We prove the algebraic statement that supplies positivity at a wall joint. The proof keeps two gradings distinct: polynomial degree records powers of v v v
Let Γ \Gamma Γ Ω \Omega Ω C ⊂ Γ C\subset\Gamma C ⊂ Γ c : C → N c:C\to\mathbb{N} c : C → N { p ∈ C : c ( p ) ≤ B } \{p\in C:c(p)\le B\} { p ∈ C : c ( p ) ≤ B } B B B
X p X q = v Ω ( p , q ) X p + q X_pX_q=v^{\Omega(p,q)}X_{p+q} X p X q = v Ω ( p , q ) X p + q and coefficients in Q ( ( v − 1 ) ) \mathbb{Q}((v^{-1})) Q (( v − 1 )) v v v p ∈ C ∖ { 0 } p\in C\setminus\{0\} p ∈ C ∖ { 0 } k ∈ Z k\in\mathbb{Z} k ∈ Z
E p , k = ∏ j ≥ 0 ( 1 + v k − 2 j X p ) , H p , k = ∏ j ≥ 0 ( 1 − v k − 2 j X p ) − 1 . E_{p,k}=\prod_{j\ge0}(1+v^{k-2j}X_p),\qquad H_{p,k}=\prod_{j\ge0}(1-v^{k-2j}X_p)^{-1}. E p , k = j ≥ 0 ∏ ( 1 + v k − 2 j X p ) , H p , k = j ≥ 0 ∏ ( 1 − v k − 2 j X p ) − 1 . We call these elementary units . A list of their occurrences is admissible if, for each charge bound B B B k k k c ( p ) ≤ B c(p)\le B c ( p ) ≤ B k ≥ L k\ge L k ≥ L L ∈ Z L\in\mathbb{Z} L ∈ Z
Theorem 3.1 (Positive reordering). Suppose an admissible product of elementary units is written in ray order, with Ω ( p i , p j ) > 0 \Omega(p_i,p_j)>0 Ω ( p i , p j ) > 0 p i p_i p i p j p_j p j
Every coefficient at fixed exponent and fixed v v v v v v Ω \Omega Ω B B B A B ≥ 1 A_B\ge1 A B ≥ 1
∣ Ω ( p , q ) ∣ ≤ A B whenever p , q ∈ C , c ( p ) , c ( q ) ≤ B . \lvert\Omega(p,q)\rvert\le A_B\qquad\text{whenever }p,q\in C,\quad c(p),c(q)\le B. ∣ Ω ( p , q )∣ ≤ A B whenever p , q ∈ C , c ( p ) , c ( q ) ≤ B . Then every prescribed coefficient and every bounded part of the output unit list can be calculated by finite rational linear algebra.
We first decompose shuffle spaces by slope and use separated-center restrictions to construct a coproduct on an auxiliary associated graded space. Polynomiality of the restriction symbols removes negative separation powers before evaluation at zero. A signed vector-space PBW decomposition and primitive strings then give the positive elementary factors. Throughout, polynomial degree with its shifts records powers of v v v
A ray factorization with constant term one exists uniquely over Q ( ( v − 1 ) ) \mathbb{Q}((v^{-1})) Q (( v − 1 )) B B B X p X_p X p p p p
Shuffle spaces and destabilizing quotients
Begin with finitely many input occurrences, indexed by 1 , … , t 1,\ldots,t 1 , … , t a i i = 0 a_{ii}=0 a ii = 0 E p i , k i E_{p_i,k_i} E p i , k i a i i = 1 a_{ii}=1 a ii = 1 H p i , k i H_{p_i,k_i} H p i , k i i ≠ j i\ne j i = j
a j i = max { Ω ( p i , p j ) , 0 } . a_{ji}=\max\{\Omega(p_i,p_j),0\}. a j i = max { Ω ( p i , p j ) , 0 } . For dimension vectors d , e ∈ N t d,e\in\mathbb{N}^t d , e ∈ N t
p ( d ) = ∑ i d i p i , χ ( d , e ) = ∑ i d i e i − ∑ i , j a i j d i e j . (5) p(d)=\sum_i d_i p_i,\qquad\chi(d,e)=\sum_i d_i e_i-\sum_{i,j}a_{ij}d_i e_j. \tag*{(5)} p ( d ) = i ∑ d i p i , χ ( d , e ) = i ∑ d i e i − i , j ∑ a ij d i e j . (5) s ( d ) = 1 2 χ ( d , d ) , u ( d ) = ∑ i d i ( k i + 1 − a i i ) . (6) s(d)=\frac{1}{2}\chi(d,d),\qquad u(d)=\sum_i d_i(k_i+1-a_{ii}). \tag*{(6)} s ( d ) = 2 1 χ ( d , d ) , u ( d ) = i ∑ d i ( k i + 1 − a ii ) . (6) Then
χ ( d , e ) − χ ( e , d ) = Ω ( p ( d ) , p ( e ) ) . (7) \chi(d,e)-\chi(e,d)=\Omega(p(d),p(e)). \tag*{(7)} χ ( d , e ) − χ ( e , d ) = Ω ( p ( d ) , p ( e )) . (7) Choose a linear functional η \eta η μ ( d ) = η ( p ( d ) ) / c ( p ( d ) ) \mu(d)=\eta(p(d))/c(p(d)) μ ( d ) = η ( p ( d )) / c ( p ( d )) c = 1 c=1 c = 1 χ \chi χ ∣ d ∣ 1 = ∑ i d i |d|_1=\sum_i d_i ∣ d ∣ 1 = ∑ i d i
Let
S d = Q [ x i , α : 1 ≤ i ≤ t , 1 ≤ α ≤ d i ] ∏ i S d i , S 0 = Q , S_d=\mathbb{Q}[x_{i,\alpha}:1\le i\le t,\ 1\le\alpha\le d_i]^{\prod_i\mathfrak{S}_{d_i}},\qquad S_0=\mathbb{Q}, S d = Q [ x i , α : 1 ≤ i ≤ t , 1 ≤ α ≤ d i ] ∏ i S d i , S 0 = Q , with every variable of polynomial degree one. Variables with a fixed i i i [31 ] , Section 2.4, Theorem 2; see also [13 ] , Theorem 2.2. In our normalization it is
f ∗ g = ∑ pack shuffles f ( x ) g ( y ) K d , e ( x , y ) , K d , e ( x , y ) = ∏ i , j ∏ α ≤ d i β ≤ e j ( y j , β − x i , α ) a i j − 1 i = j . (8) f*g=\sum_{\text{pack shuffles}}f(x)g(y)K_{d,e}(x,y),\qquad K_{d,e}(x,y)=\prod_{i,j}\prod_{\substack{\alpha\le d_i\\ \beta\le e_j}}(y_{j,\beta}-x_{i,\alpha})^{a_{ij}-1_{i=j}}. \tag*{(8)} f ∗ g = pack shuffles ∑ f ( x ) g ( y ) K d , e ( x , y ) , K d , e ( x , y ) = i , j ∏ α ≤ d i β ≤ e j ∏ ( y j , β − x i , α ) a ij − 1 i = j . (8) Each shuffle chooses, in each output pack, the variables assigned to the first input; there is no factorial normalization. The only possible poles are simple poles between two variables of the same output pack. Interchanging those two variables pairs the residues with opposite signs. After taking a common denominator, the numerator is therefore divisible by every such difference. The differences are relatively prime irreducible polynomials, so all poles cancel. Consequently f ∗ g ∈ S d + e f*g\in S_{d+e} f ∗ g ∈ S d + e − χ ( d , e ) -\chi(d,e) − χ ( d , e )
The destabilizing quotient below is the polynomial form of the semistable restriction quotient in [15 ] , Theorem 8.1. We establish its needed properties directly for our charge-weighted slope. For d ≠ 0 d \ne0 d = 0
I d = ∑ a + b = d , a , b ≠ 0 μ ( a ) > μ ( d ) S a ∗ S b , B d = S d / I d , B 0 = Q . (9) I_d=\sum_{\substack{a+b=d,\ a,b\ne0\\ \mu(a)>\mu(d)}} S_a * S_b,\qquad B_d=S_d/I_d,\qquad B_0=\mathbb{Q}. \tag*{(9)} I d = a + b = d , a , b = 0 μ ( a ) > μ ( d ) ∑ S a ∗ S b , B d = S d / I d , B 0 = Q . (9) Every image S a ∗ S b S_a * S_b S a ∗ S b S d S_d S d I d I_d I d
The product descends to B d ⊗ B e → B d + e B_d\otimes B_e\to B_{d+e} B d ⊗ B e → B d + e μ ( d ) = μ ( e ) = θ \mu(d)=\mu(e)=\theta μ ( d ) = μ ( e ) = θ a + b = d a+b=d a + b = d μ ( a ) > θ \mu(a)>\theta μ ( a ) > θ ( S a ∗ S b ) ∗ S e (S_a*S_b)*S_e ( S a ∗ S b ) ∗ S e a a a a + b = e a+b=e a + b = e μ ( a ) > θ \mu(a)>\theta μ ( a ) > θ S d ∗ ( S a ∗ S b ) = ( S d ∗ S a ) ∗ S b S_d*(S_a*S_b)=(S_d*S_a)*S_b S d ∗ ( S a ∗ S b ) = ( S d ∗ S a ) ∗ S b d + a d+a d + a B d B_d B d
deg s h f = deg p o l f + s ( d ) . (10) \deg_{\mathrm{sh}} f=\deg_{\mathrm{pol}} f+s(d). \tag*{(10)} deg sh f = deg pol f + s ( d ) . (10) On a common slope, s ( d + e ) = s ( d ) + s ( e ) + χ ( d , e ) s(d+e)=s(d)+s(e)+\chi(d,e) s ( d + e ) = s ( d ) + s ( e ) + χ ( d , e )
Separated centers and ordered decomposition
We record carefully the restriction operation used throughout the proof. For an ordered list P = ( r 1 , … , r m ) P=(r_1,\ldots,r_m) P = ( r 1 , … , r m ) d d d d d d r ℓ r_\ell r ℓ ℓ \ell ℓ x ℓ + z ℓ x^\ell+z_\ell x ℓ + z ℓ I r ℓ I_{r_\ell} I r ℓ
R ~ P z : S d ⟶ ( ⨂ ℓ = 1 m B r ℓ ) [ z 1 , … , z m ] . (11) \widetilde{R}^{z}_{P}:S_d\longrightarrow\left(\bigotimes_{\ell=1}^{m}B_{r_\ell}\right)[z_1,\ldots,z_m]. \tag*{(11)} R P z : S d ⟶ ( ℓ = 1 ⨂ m B r ℓ ) [ z 1 , … , z m ] . (11) The choices inside a pack do not matter because its input is symmetric. Common translation preserves I d I_d I d (8) depend on differences. Hence translation also defines an automorphism of B d [ z ] B_d[z] B d [ z ]
Here is the useful way to apply Equation (11) to a shuffle expression. Split each source group into subgroups assigned to the target groups. At distinct centers expand the kernels between different targets in their internal variables, over Q ( z 1 , … , z m ) \mathbb{Q}(z_1,\ldots,z_m) Q ( z 1 , … , z m ) b b b r r r μ ( b ) > μ ( r ) \mu(b)>\mu(r) μ ( b ) > μ ( r ) I r I_r I r Q ( z 1 , … , z m ) \mathbb{Q}(z_1,\ldots,z_m) Q ( z 1 , … , z m )
The slope ordering follows the Harder–Narasimhan factorization formalism [34 ] , Propositions 4.8 and 4.12, [31 ] , Sections 5.2–5.3. Ordered multiplication of semistable pieces is established in [15 ] , Theorem 6.2; the next argument proves the required decomposition for the explicit quotients above. Here the locator for [15 ] refers to its published version.
Lemma 3.2 (Ordered decomposition). Choose graded vector-space sections B d → S d B_d \to S_d B d → S d of all quotient maps. For every d d d multiplication induces a vector-space isomorphism
S d ≅ ⨁ d ( 1 ) + ⋯ + d ( m ) = d μ ( d ( 1 ) ) > ⋯ > μ ( d ( m ) ) B d ( 1 ) ⊗ ⋯ ⊗ B d ( m ) , (12) S_d \cong\bigoplus_{\substack{d^{(1)}+\cdots+d^{(m)}=d\\ \mu(d^{(1)})>\cdots>\mu(d^{(m)})}} B_{d^{(1)}}\otimes\cdots\otimes B_{d^{(m)}}, \tag*{(12)} S d ≅ d ( 1 ) + ⋯ + d ( m ) = d μ ( d ( 1 ) ) > ⋯ > μ ( d ( m ) ) ⨁ B d ( 1 ) ⊗ ⋯ ⊗ B d ( m ) , (12) with the polynomial-degree shifts prescribed by the shuffle kernels.
Proof. Induct on ∣ d ∣ 1 |d|_1 ∣ d ∣ 1 B d B_d B d
( c ( p ( d ( 1 ) + ⋯ + d ( j ) ) ) , η ( p ( d ( 1 ) + ⋯ + d ( j ) ) ) ) . \left(c\left(p\left(d^{(1)}+\cdots+d^{(j)}\right)\right),\eta\left(p\left(d^{(1)}+\cdots+d^{(j)}\right)\right)\right). ( c ( p ( d ( 1 ) + ⋯ + d ( j ) ) ) , η ( p ( d ( 1 ) + ⋯ + d ( j ) ) ) ) . The original destabilizing cut lies strictly above the chord joining the endpoints. If adjacent slopes are nondecreasing, merge those two factors and apply the induction hypothesis to their product. Their total dimension is smaller than d d d d d d
For independence, restrict an ordered product to targets r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m r j r_j r j b j b_j b j b j μ ( r j ) b_j\mu(r_j) b j μ ( r j ) ∑ j b j \sum_j b_j ∑ j b j dimension vectors , not only their charges and slopes, must agree.
In a finite relation choose a polygon minimal under pointwise comparison. Restriction to its dimension-vector list kills every other list: a surviving source polygon would have to be smaller, or equal with that same list. For the matching list the restriction is the tensor of the translated lifts, multiplied by all intergroup kernels. These kernels are invertible Taylor series at separated centers. They act on the quotient tensor because they are separately symmetric in each whole target group. Cancel them. Translation is an automorphism of each quotient, and the chosen lifts identify with the quotient vector spaces. Thus the original tensor in that summand must be zero. Applying this to a minimal nonzero summand contradicts the proposed relation. □ \square □
Lemma 3.3 (Restrictions on a slope). If all r ℓ r_\ell r ℓ have the slope of d d d (11) factors through a map
R P z : B d ⟶ ( ⨂ ℓ B r ℓ ) [ z ] . (13) R_P^z:B_d\longrightarrow\left(\bigotimes_\ell B_{r_\ell}\right)[z]. \tag*{(13)} R P z : B d ⟶ ( ℓ ⨂ B r ℓ ) [ z ] . (13) These maps compose under refinement, with the successive centers added. When a same-slope product is restricted, only splits whose nonempty subgroups have this slope survive; the restrictions of its two factors may already be taken in their respective quotients.
Proof. Consider a destabilizing product with first dimension a a a a a a μ ( a ) > μ ( d ) \mu(a) > \mu(d) μ ( a ) > μ ( d )
For a product with first total dimension of the common slope, split that dimension among equal-slope targets. If any nonempty piece is off the slope, some piece must lie above it, by the weighted-average identity for slopes. That target is destabilized. In every remaining split both pieces of a target have the common slope. Internal shuffle products descend by Equation (9) ; multiplication by the Taylor coefficients preserves the quotient ideals because they are ordinary ideals. This justifies taking all input subgroups in their quotients before the remaining computation.
The Hilbert-series target
The ordered decomposition gives a formula for each factor in the reversed ray order. We derive that formula now, so that the remaining problem is a precise statement about graded dimensions.
The Hilbert series of the ordinary pack-symmetric polynomial space is
Hilb S d ( t ) = ∏ i ∏ j = 1 d i ( 1 − t j ) − 1 . (14) \operatorname{Hilb}_{S_d}(t) = \prod_i \prod_{j=1}^{d_i} (1-t^j)^{-1}. \tag*{(14)} Hilb S d ( t ) = i ∏ j = 1 ∏ d i ( 1 − t j ) − 1 . (14) Indeed monomial orbit sums are indexed by weakly decreasing exponent lists in each pack, and their successive differences contribute independent degrees 1 , … , d i 1,\ldots,d_i 1 , … , d i
The coefficient of X m p X_{mp} X m p E p , k E_{p,k} E p , k 0 ≤ j 1 < ⋯ < j m 0 \leq j_1 < \cdots< j_m 0 ≤ j 1 < ⋯ < j m v k m − 2 ∑ j r v^{km-2\sum j_r} v k m − 2 ∑ j r 0 , 1 , … , m − 1 0,1,\ldots,m-1 0 , 1 , … , m − 1 H p , k H_{p,k} H p , k
v k m − m ( m − 1 ) ∏ j = 1 m ( 1 − v − 2 j ) , v k m ∏ j = 1 m ( 1 − v − 2 j ) . \frac{v^{km-m(m-1)}}{\prod_{j=1}^{m}(1-v^{-2j})}, \qquad\frac{v^{km}}{\prod_{j=1}^{m}(1-v^{-2j})}. ∏ j = 1 m ( 1 − v − 2 j ) v k m − m ( m − 1 ) , ∏ j = 1 m ( 1 − v − 2 j ) v k m . Taking the ordered torus product shows that the finite input is
∑ d ∈ N t X p ( d ) v u ( d ) − χ ( d , d ) Hilb S d ( v − 2 ) . (15) \sum_{d\in\mathbb{N}^t} X_{p(d)}v^{u(d)-\chi(d,d)}\operatorname{Hilb}_{S_d}(v^{-2}). \tag*{(15)} d ∈ N t ∑ X p ( d ) v u ( d ) − χ ( d , d ) Hilb S d ( v − 2 ) . (15) The diagonal terms give exactly the two displayed unit coefficients; the off-diagonal terms − χ ( d , d ) -\chi(d,d) − χ ( d , d ) ∑ i < j d i d j Ω ( p i , p j ) \sum_{i<j}d_i d_j\Omega(p_i,p_j) ∑ i < j d i d j Ω ( p i , p j )
Apply Lemma 3.2. For two blocks a , b a,b a , b − χ ( a , b ) -\chi(a,b) − χ ( a , b ) v − χ ( d , d ) v^{-\chi(d,d)} v − χ ( d , d )
2 χ ( a , b ) − χ ( a , b ) − χ ( b , a ) = χ ( a , b ) − χ ( b , a ) = Ω ( p ( a ) , p ( b ) ) . 2\chi(a,b)-\chi(a,b)-\chi(b,a)=\chi(a,b)-\chi(b,a)=\Omega(p(a),p(b)). 2 χ ( a , b ) − χ ( a , b ) − χ ( b , a ) = χ ( a , b ) − χ ( b , a ) = Ω ( p ( a ) , p ( b )) . This is precisely Equation (3.1) . Equation (15) therefore factors in decreasing slope order, with slope factor
1 + ∑ μ ( d ) = θ X p ( d ) v u ( d ) − χ ( d , d ) Hilb B d ( v − 2 ) , (16) 1+\sum_{\mu(d)=\theta}X_{p(d)}v^{u(d)-\chi(d,d)}\operatorname{Hilb}_{B_d}(v^{-2}), \tag*{(16)} 1 + μ ( d ) = θ ∑ X p ( d ) v u ( d ) − χ ( d , d ) Hilb B d ( v − 2 ) , (16) where Hilb B d \operatorname{Hilb}_{B_d} Hilb B d
In this formula an element of shifted degree h h h v u ( d ) − 2 h v^{u(d)-2h} v u ( d ) − 2 h B 0 B_0 B 0 B d B_d B d d d d h h h h + 1 h+1 h + 1 h + 2 h+2 h + 2 … \ldots … H p ( d ) , u ( d ) − 2 h H_{p(d),u(d)-2h} H p ( d ) , u ( d ) − 2 h E p ( d ) , u ( d ) − 2 h E_{p(d),u(d)-2h} E p ( d ) , u ( d ) − 2 h χ ( d , d ) \chi(d,d) χ ( d , d )
The next construction supplies this decomposition through a coproduct. Its auxiliary filtration makes separated restrictions regular at coincident centers, while retaining the original shifted degree that appears in the weight v u ( d ) − 2 h v^{u(d)-2h} v u ( d ) − 2 h
A filtration and polynomial restriction symbols
Fix a slope θ \theta θ θ \theta θ d ≠ 0 d \ne0 d = 0 w ∈ 1 2 Z w \in\frac{1}{2}\mathbb{Z} w ∈ 2 1 Z
f ∈ F w B d ⟺ every term of R P z f has internal degree + ∑ r ∈ P s ( r ) ≥ w for every P . (17) f \in F_w B_d \quad\Longleftrightarrow\quad\text{every term of } R_P^z f \text{ has internal degree}+\sum_{r\in P}s(r)\ge w \text{ for every } P. \tag*{(17)} f ∈ F w B d ⟺ every term of R P z f has internal degree + r ∈ P ∑ s ( r ) ≥ w for every P . (17) Centers have degree zero in this test; the one-block list ( d ) (d) ( d ) P P P d d d ℓ \ell ℓ ℓ \ell ℓ ℓ + s ( d ) \ell+s(d) ℓ + s ( d ) gr w B d = F w B d / F w + 1 / 2 B d \operatorname{gr}_w B_d=F_wB_d/F_{w+1/2}B_d gr w B d = F w B d / F w + 1/2 B d B 0 = Q B_0=\mathbb{Q} B 0 = Q
For f ∈ gr w B d f\in\operatorname{gr}_w B_d f ∈ gr w B d P = ( r 1 , … , r m ) P=(r_1,\ldots,r_m) P = ( r 1 , … , r m )
L P ( f ) = ∏ i < j ( z j − z i ) χ ( r i , r j ) ( R P z f ) w , (18) L_P(f)=\prod_{i<j}(z_j-z_i)^{\chi(r_i,r_j)}(R_P^z f)_w, \tag*{(18)} L P ( f ) = i < j ∏ ( z j − z i ) χ ( r i , r j ) ( R P z f ) w , (18) where the subscript retains internal degree w − ∑ i s ( r i ) w-\sum_i s(r_i) w − ∑ i s ( r i )
Example 3.4 (The two gradings in one variable). Let d i = 1 d_i=1 d i = 1 d d d d d d B d = Q [ x ] B_d=\mathbb{Q}[x] B d = Q [ x ] R ( d ) z f = f ( x + z ) R_{(d)}^z f=f(x+z) R ( d ) z f = f ( x + z ) f = x ℓ f=x^\ell f = x ℓ ℓ ≥ 0 \ell\ge0 ℓ ≥ 0 z ℓ z^\ell z ℓ x ℓ x^\ell x ℓ s ( d ) = ( 1 − a i i ) / 2 s(d)=(1-a_{ii})/2 s ( d ) = ( 1 − a ii ) /2 ℓ + s ( d ) \ell+s(d) ℓ + s ( d )
L ( d ) ( [ x ℓ ] ) = z ℓ . L_{(d)}([x^\ell])=z^\ell. L ( d ) ([ x ℓ ]) = z ℓ . The auxiliary grade therefore retains every polynomial degree, even though they all have the same filtration weight. On these symbols, multiplication by x x x z z z z z z
Lemma 3.5 (Polynomial symbols and detection). Every L P ( f ) L_P(f) L P ( f ) is polynomial in its centers. The maps L P L_P L P jointly inject gr w B d \operatorname{gr}_w B_d gr w B d into their polynomial targets. For the additive tensor filtration
F w ( B a ⊗ B b ) = ∑ u + v ≥ w F u B a ⊗ F v B b , (19) F_w(B_a\otimes B_b)=\sum_{u+v\ge w}F_uB_a\otimes F_vB_b, \tag*{(19)} F w ( B a ⊗ B b ) = u + v ≥ w ∑ F u B a ⊗ F v B b , (19) tensor products of the restriction tests characterize membership, and tensor products L R ⊗ L S L_R\otimes L_S L R ⊗ L S jointly detect its associated grades.
Proof. Write S ( P ) = ∑ r ∈ P s ( r ) S(P)=\sum_{r\in P}s(r) S ( P ) = ∑ r ∈ P s ( r ) a , b a,b a , b P P P S ( P ) + χ ( a , b ) S(P)+\chi(a,b) S ( P ) + χ ( a , b ) δ = z b − z a \delta=z_b-z_a δ = z b − z a δ \delta δ w − S ( P ) − χ ( a , b ) w-S(P)-\chi(a,b) w − S ( P ) − χ ( a , b ) w − S ( P ) w-S(P) w − S ( P ) δ \delta δ − χ ( a , b ) -\chi(a,b) − χ ( a , b ) χ ( a , b ) < 0 \chi(a,b)<0 χ ( a , b ) < 0 (18) . Perform this argument for every pair. To justify simultaneous cancellation, choose a Q \mathbb{Q} Q z j − z i z_j-z_i z j − z i { i , j } \{i,j\} { i , j }
Joint injectivity follows directly from (17) : if all leading restrictions vanish, the representative belongs to F w + 1 / 2 \mathcal{F}_{w+1/2} F w + 1/2
For completeness, a tensor satisfies all lower-bound restriction tests exactly when it belongs to (19) . One implication follows by applying the defining tests to each factor. For the other, choose filtration complements in each finite-dimensional original-degree space. If a tensor violated the bound, take its lowest nonzero total filtration grade below w w w Q \mathbb{Q} Q u , v u,v u , v R , S R,S R , S u − S ( R ) u-S(R) u − S ( R ) v − S ( S ) v-S(S) v − S ( S )
Product symbols
Lemma 3.6 (Product symbols). The same-slope product preserves the sum of filtration weights. For f ∈ gr u B d f\in\operatorname{gr}_{u}B_d f ∈ gr u B d g ∈ gr v B e g\in\operatorname{gr}_{v}B_e g ∈ gr v B e R = ( r 1 , … , r m ) R=(r_1,\ldots,r_m) R = ( r 1 , … , r m )
L R ( f ∗ g ) = ∑ r i = d i ′ + e i ′ ∑ i d i ′ = d , ∑ i e i ′ = e ( − 1 ) ∑ i > j χ ( d i ′ , e j ′ ) ( ∗ ⊗ R ) ( L ( d i ′ ) ( f ) ⊗ L ( e i ′ ) ( g ) ) . (20) L_R(f\ast g)=\sum_{\substack{r_i=d'_i+e'_i\\ \sum_i d'_i=d,\ \sum_i e'_i=e}}(-1)^{\sum_{i>j}\chi(d'_i,e'_j)}\left(\ast\otimes^{R}\right)\left(L_{(d'_i)}(f)\otimes L_{(e'_i)}(g)\right). \tag*{(20)} L R ( f ∗ g ) = r i = d i ′ + e i ′ ∑ i d i ′ = d , ∑ i e i ′ = e ∑ ( − 1 ) ∑ i > j χ ( d i ′ , e j ′ ) ( ∗ ⊗ R ) ( L ( d i ′ ) ( f ) ⊗ L ( e i ′ ) ( g ) ) . (20) All nonzero entries in this sum have slope θ \theta θ ∗ ⊗ R \ast\otimes^{R} ∗ ⊗ R
Proof. Use Lemma 3.3 and expand intergroup kernels at separated centers. Every nonconstant internal Taylor term increases internal degree. In target i i i − χ ( d i ′ , e i ′ ) -\chi(d'_i,e'_i) − χ ( d i ′ , e i ′ )
s ( r i ) − s ( d i ′ ) − s ( e i ′ ) = χ ( d i ′ , e i ′ ) . s(r_i)-s(d'_i)-s(e'_i)=\chi(d'_i,e'_i). s ( r i ) − s ( d i ′ ) − s ( e i ′ ) = χ ( d i ′ , e i ′ ) . This proves the filtration bound. On its leading grade only the scalar intergroup kernels remain. For i < j i<j i < j
( z j − z i ) − χ ( d i ′ , e j ′ ) ( z i − z j ) − χ ( d j ′ , e i ′ ) . (z_j-z_i)^{-\chi(d'_i,e'_j)}(z_i-z_j)^{-\chi(d'_j,e'_i)}. ( z j − z i ) − χ ( d i ′ , e j ′ ) ( z i − z j ) − χ ( d j ′ , e i ′ ) . Multiplication by the L R L_R L R χ ( r i , r j ) \chi(r_i,r_j) χ ( r i , r j ) ( − 1 ) χ ( d j ′ , e i ′ ) (-1)^{\chi(d'_j,e'_i)} ( − 1 ) χ ( d j ′ , e i ′ ) i < j i<j i < j (20) . ∎
The coproduct and its regular specialization
Let H = ⨁ μ ( d ) = θ gr B d \mathcal{H}=\bigoplus_{\mu(d)=\theta}\operatorname{gr} B_d H = ⨁ μ ( d ) = θ gr B d H 0 = Q \mathcal{H}_0=\mathbb{Q} H 0 = Q
Lemma 3.7 (Graded coproduct). For d = a + b d=a+b d = a + b
Δ a , b : gr B d ⟶ gr B a ⊗ gr B b \Delta_{a,b}:\operatorname{gr} B_d\longrightarrow\operatorname{gr} B_a\otimes\operatorname{gr} B_b Δ a , b : gr B d ⟶ gr B a ⊗ gr B b preserving both original shifted degree and total filtration weight, characterized by
( L R ⊗ L S ) ( Δ a , b f ) = L R , S ( f ) (21) (L_R\otimes L_S)(\Delta_{a,b}f)=L_{R,S}(f) \tag*{(21)} ( L R ⊗ L S ) ( Δ a , b f ) = L R , S ( f ) (21) for all lists R , S R,S R , S a , b a,b a , b
Proof. Take first a , b ≠ 0 a,b\ne0 a , b = 0 f ∈ F w B d f\in\mathcal{F}_wB_d f ∈ F w B d ℓ \ell ℓ Z = ∞ Z=\infty Z = ∞
K a , b ( x + Z , y ) − 1 f ( x + Z , y ) = ∑ j C j ( f ) Z j in ( B a ⊗ B b ) ( ( Z − 1 ) ) . (22) K_{a,b}(x+Z,y)^{-1}f(x+Z,y)=\sum_j C_j(f)Z^j\quad\text{in }(B_a\otimes B_b)((Z^{-1})). \tag*{(22)} K a , b ( x + Z , y ) − 1 f ( x + Z , y ) = j ∑ C j ( f ) Z j in ( B a ⊗ B b ) (( Z − 1 )) . (22) Each coefficient is an actual polynomial tensor before quotienting: expand the finitely many integer powers of linear factors, and note that a specified Z Z Z B d B_d B d Z Z Z
deg p o l C j ( f ) = ℓ + χ ( a , b ) − j . (23) \deg_{\mathrm{pol}} C_j(f)=\ell+\chi(a,b)-j. \tag*{(23)} deg pol C j ( f ) = ℓ + χ ( a , b ) − j . (23) In particular C j ( f ) = 0 C_j(f)=0 C j ( f ) = 0 j > ℓ + χ ( a , b ) j>\ell+\chi(a,b) j > ℓ + χ ( a , b )
Apply arbitrary refinements R = ( r i ) R=(r_i) R = ( r i ) a a a S = ( s j ) S=(s_j) S = ( s j ) b b b Z Z Z
∏ i , j ( z j S − z i R − Z ) χ ( r i , s j ) , (24) \prod_{i,j}(z_j^S-z_i^R-Z)^{\chi(r_i,s_j)}, \tag*{(24)} i , j ∏ ( z j S − z i R − Z ) χ ( r i , s j ) , (24) and all its other internal terms have positive degree. The restriction of f f f w w w C j ( f ) C_j(f) C j ( f ) C j ( f ) ∈ F w ( B a ⊗ B b ) C_j(f)\in\mathcal{F}_w(B_a\otimes B_b) C j ( f ) ∈ F w ( B a ⊗ B b )
On the weight-w w w (24) contributes. Multiplying by the two separate symbol prefactors supplies exactly the missing cross-list factors, so
( L R ⊗ L S ) ( ∑ j [ C j ( f ) ] Z j ) = L R , S ( [ f ] ) ( z R + Z , z S ) . (25) (L_R\otimes L_S)\left(\sum_j[C_j(f)]Z^j\right)=L_{R,S}([f])(z^R+Z,z^S). \tag*{(25)} ( L R ⊗ L S ) ( j ∑ [ C j ( f )] Z j ) = L R , S ([ f ]) ( z R + Z , z S ) . (25) By Lemma 3.5, the right side is a polynomial in all its centers and in Z Z Z j < 0 j<0 j < 0 [ C j ( f ) ] = 0 [C_j(f)]=0 [ C j ( f )] = 0 j < 0 j<0 j < 0
Equation (23) leaves only finitely many nonnegative Z Z Z
Δ a , b [ f ] = [ C 0 ( f ) ] . \Delta_{a,b}[f]=[C_0(f)]. Δ a , b [ f ] = [ C 0 ( f )] . Changing f f f F w + 1 / 2 F_{w+1/2} F w + 1/2 Z = 0 Z=0 Z = 0 (25) proves Equation (21) . Finally the original shifted degree of C 0 ( f ) C_0(f) C 0 ( f )
ℓ + χ ( a , b ) + s ( a ) + s ( b ) = ℓ + s ( d ) , \ell+\chi(a,b)+s(a)+s(b)=\ell+s(d), ℓ + χ ( a , b ) + s ( a ) + s ( b ) = ℓ + s ( d ) , as required.
Write ε ( a , b ) = ( − 1 ) χ ( a , b ) \varepsilon(a,b)=(-1)^{\chi(a,b)} ε ( a , b ) = ( − 1 ) χ ( a , b ) χ \chi χ
( x ⊗ y ) ( x ′ ⊗ y ′ ) = ε ( deg y , deg x ′ ) ( x ∗ x ′ ) ⊗ ( y ∗ y ′ ) . (26) (x\otimes y)(x'\otimes y')=\varepsilon(\deg y,\deg x')(x*x')\otimes(y*y'). \tag*{(26)} ( x ⊗ y ) ( x ′ ⊗ y ′ ) = ε ( deg y , deg x ′ ) ( x ∗ x ′ ) ⊗ ( y ∗ y ′ ) . (26) where degrees in this formula are dimension vectors.
Proposition 3.8. *With Δ = ∑ a + b = d Δ a , b \Delta=\sum_{a+b=d}\Delta_{a,b} Δ = ∑ a + b = d Δ a , b H \mathcal{H} H ε ( a , b ) \varepsilon(a,b) ε ( a , b )
Proof. Testing either iterated coproduct against three independent lists of symbols gives the symbol for their concatenation. Joint tensor detection gives coassociativity. Swapping two lists changes their cross-list prefactor by ( − 1 ) χ ( a , b ) (-1)^{\chi(a,b)} ( − 1 ) χ ( a , b )
For multiplicativity apply Equation (20) to the two tensor factors separately. If the first input contributes dimensions d R , d S d_R,d_S d R , d S e R , e S e_R,e_S e R , e S
∑ i ∈ S , j ∈ R χ ( d i ′ , e j ′ ) = χ ( d S , e R ) . \sum_{\substack{i\in S,\ j\in R}}\chi(d'_i,e'_j)=\chi(d_S,e_R). i ∈ S , j ∈ R ∑ χ ( d i ′ , e j ′ ) = χ ( d S , e R ) . This is the interchange sign in Equation (26) . Both sides therefore have the symbols of the product restricted to the concatenation, and detection proves multiplicativity. Positive dimension grading and H 0 = Q \mathcal{H}_0=\mathbb{Q} H 0 = Q
Primitive vectors and polynomial strings
The symmetric-algebra form of the graded dimensions is the cohomological-integrality and PBW phenomenon developed in [12 , 13 , 31 ] . Efimov’s freeness theorem assumes a symmetric quiver, whereas our quiver need only have symmetric Euler pairing on the selected slope. Davison–Meinhardt use a perverse associated graded in [12 ] ; the separated-center filtration here has its own explicit construction. We include the vector-space argument needed from our bialgebra, because its conclusion does not require commutativity of the product. Let P ⊂ H \mathcal{P}\subset\mathcal{H} P ⊂ H Δ a , b \Delta_{a,b} Δ a , b (21) and tensor detection, these are exactly the elements killed by all proper symbols L P L_P L P
The convolution-logarithm proof below is the signed/braided Eulerian-idempotent argument. For the classical commutative characteristic-zero method, see [33 ] , Sections 3–4, Theorem 3.5 and Lemma 4.1; the proof here supplies the bilinear-sign adaptation.
Lemma 3.9 (Signed vector-space PBW). Symmetrized multiplication gives an isomorphism of graded vector spaces
Sym ε ( P ) ⟶ H . (27) \operatorname{Sym}_{\varepsilon}(\mathcal{P}) \longrightarrow\mathcal{H}. \tag*{(27)} Sym ε ( P ) ⟶ H . (27) Here the left side is the signed symmetric vector space : exchanging homogeneous vectors of dimensions a , b a,b a , b ε ( a , b ) \varepsilon(a,b) ε ( a , b )
Proof. For linear maps out of H \mathcal{H} H e e e
J = id − e , P = log ∗ ( id ) = ∑ r ≥ 1 ( − 1 ) r − 1 r J ∗ r . J=\operatorname{id}-e,\qquad P=\log^{*}(\operatorname{id})=\sum_{r\geq1}\frac{(-1)^{r-1}}{r}J^{*r}. J = id − e , P = log ∗ ( id ) = r ≥ 1 ∑ r ( − 1 ) r − 1 J ∗ r . On dimension d d d ∣ d ∣ 1 \lvert d\rvert_{1} ∣ d ∣ 1 H ⊗ H \mathcal{H}\otimes\mathcal{H} H ⊗ H α ( h ) = h ⊗ 1 \alpha(h)=h\otimes1 α ( h ) = h ⊗ 1 β ( h ) = 1 ⊗ h \beta(h)=1\otimes h β ( h ) = 1 ⊗ h α ∗ β = Δ \alpha* \beta=\Delta α ∗ β = Δ β ∗ α = Δ \beta* \alpha=\Delta β ∗ α = Δ Δ \Delta Δ
Δ ∘ P = log ∗ ( Δ ) = log ∗ ( α ) + log ∗ ( β ) = P ⊗ 1 + 1 ⊗ P . \Delta\circ P=\log^{*}(\Delta)=\log^{*}(\alpha)+\log^{*}(\beta)=P\otimes1+1\otimes P. Δ ∘ P = log ∗ ( Δ ) = log ∗ ( α ) + log ∗ ( β ) = P ⊗ 1 + 1 ⊗ P . Thus P P P P \mathcal{P} P
id = e + ∑ r ≥ 1 1 r ! P ∗ r . \operatorname{id}=e+\sum_{r\geq1}\frac{1}{r!}P^{*r}. id = e + r ≥ 1 ∑ r ! 1 P ∗ r . The iterated coproduct is invariant under signed permutations, and P P P H \mathcal{H} H
To prove independence, identify signed symmetric tensors in characteristic zero with the invariant tensors obtained by averaging over signed permutations. In a finite relation among their products, let r r r r r r r r r r r r r ! r! r ! r ! r! r ! r r r r r r
For a homogeneous basis of P \mathcal{P} P − 1 -1 − 1 H \mathcal{H} H (27) .
Lemma 3.10 (Primitive strings). For each nonzero dimension d d d
h , h + 1 , h + 2 , … , h − s ( d ) ∈ N . h,h+1,h+2,\ldots,\qquad h-s(d)\in\mathbb{N}. h , h + 1 , h + 2 , … , h − s ( d ) ∈ N . Each degree has finite dimension. Every vector in these strings has self-interchange sign ( − 1 ) χ ( d , d ) (-1)^{\chi(d,d)} ( − 1 ) χ ( d , d )
Proof. On S d S_d S d
D d = ∑ i , α ∂ ∂ x i , α , T d f = ( 1 ∣ d ∣ 1 ∑ i , α x i , α ) f . D_d=\sum_{i,\alpha}\frac{\partial}{\partial x_{i,\alpha}},\qquad
T_df=\left(\frac{1}{\lvert d\rvert_1}\sum_{i,\alpha}x_{i,\alpha}\right)f. D d = i , α ∑ ∂ x i , α ∂ , T d f = ( ∣ d ∣ 1 1 i , α ∑ x i , α ) f . The translation invariance of the shuffle kernels implies D d ( I d ) ⊂ I d D_d(I_d) \subset I_d D d ( I d ) ⊂ I d T d ( I d ) ⊂ I d T_d(I_d) \subset I_d T d ( I d ) ⊂ I d B d B_d B d P = ( r 1 , … , r m ) P=(r_1,\ldots,r_m) P = ( r 1 , … , r m )
R P z ( D d f ) = ( ∑ ℓ ∂ z ℓ ) R P z f , R_P^z(D_df)=\left(\sum_\ell\partial_{z_\ell}\right)R_P^z f, R P z ( D d f ) = ( ℓ ∑ ∂ z ℓ ) R P z f , R P z ( T d f ) = ( ∑ ℓ ∣ r ℓ ∣ 1 ∣ z ℓ ∣ ∣ d ∣ 1 + ∑ ℓ , i , α x ℓ , α i ∣ d ∣ 1 ) R P z f . R_P^z(T_df)=\left(\frac{\sum_\ell|r_\ell|_1|z_\ell|}{|d|_1}+\frac{\sum_{\ell,i,\alpha}x_{\ell,\alpha}^i}{|d|_1}\right)R_P^z f. R P z ( T d f ) = ( ∣ d ∣ 1 ∑ ℓ ∣ r ℓ ∣ 1 ∣ z ℓ ∣ + ∣ d ∣ 1 ∑ ℓ , i , α x ℓ , α i ) R P z f . Both preserve the filtration lower bound. On the associated grade, the internal-variable term in the second line raises internal degree and disappears. The prefactor of L P L_P L P
L P ( D d f ) = ( ∑ ℓ ∂ z ℓ ) L P ( f ) , L_P(D_df)=\left(\sum_\ell\partial_{z_\ell}\right)L_P(f), L P ( D d f ) = ( ℓ ∑ ∂ z ℓ ) L P ( f ) , L P ( T d f ) = ∑ ℓ ∣ r ℓ ∣ 1 ∣ z ℓ ∣ ∣ d ∣ 1 L P ( f ) . L_P(T_df)=\frac{\sum_\ell|r_\ell|_1|z_\ell|}{|d|_1}L_P(f). L P ( T d f ) = ∣ d ∣ 1 ∑ ℓ ∣ r ℓ ∣ 1 ∣ z ℓ ∣ L P ( f ) . They preserve the common kernel of all proper symbols, hence the primitive space. They satisfy D d T d − T d D d = id D_dT_d-T_dD_d=\operatorname{id} D d T d − T d D d = id D d D_d D d T d T_d T d
π ( f ) = ∑ j ≥ 0 ( − 1 ) j j ! T d j D d j f . \pi(f)=\sum_{j\geq0}\frac{(-1)^j}{j!}T_d^jD_d^j f. π ( f ) = j ≥ 0 ∑ j ! ( − 1 ) j T d j D d j f . The commutator identity gives D d π = 0 D_d\pi=0 D d π = 0
f = ∑ j ≥ 0 T d j j ! π ( D d j f ) . f=\sum_{j\geq0}\frac{T_d^j}{j!}\pi(D_d^j f). f = j ≥ 0 ∑ j ! T d j π ( D d j f ) . Choose a homogeneous basis of ker D d \ker D_d ker D d T d T_d T d ∑ j = 0 r T d j b j = 0 \sum_{j=0}^rT_d^jb_j=0 ∑ j = 0 r T d j b j = 0 D d b j = 0 D_db_j=0 D d b j = 0 D d r D_d^r D d r r ! b r = 0 r!b_r=0 r ! b r = 0
Every component of H d \mathcal{H}_d H d B d B_d B d s ( d ) s(d) s ( d ) h ≥ s ( d ) h\geq s(d) h ≥ s ( d )
Combining Lemmas 3.9 and 3.10, the shifted Hilbert series on a slope is the Hilbert series of independent polynomial strings when χ ( d , d ) \chi(d,d) χ ( d , d )
Elementary factors and the infinite-list bounds
We now finish the finite-input case of Theorem 3.1 using the slope factor (16) . Lemmas 3.9 and 3.10 give exactly the polynomial and exterior strings required above. In shifted degree h h h v u ( d ) − 2 h v^{u(d)-2h} v u ( d ) − 2 h
A primitive string beginning at h h h
p = p ( d ) , k = u ( d ) − 2 h , (28) p = p(d), \qquad k = u(d) - 2h, \tag*{(28)} p = p ( d ) , k = u ( d ) − 2 h , (28) of type E E E χ ( d , d ) \chi(d,d) χ ( d , d ) H H H 2 h 2h 2 h
Now allow an admissible infinite input list. Give each occurrence its own index and use finite-support dimension vectors d d d d d d
We give uniform bounds to justify this passage. Fix an integer charge cutoff B ≥ 1 B \ge1 B ≥ 1 p i p_i p i C B = { p ∈ C : 0 < c ( p ) ≤ B } C_B = \{p \in C : 0 < c(p) \le B\} C B = { p ∈ C : 0 < c ( p ) ≤ B } D = ∣ d ∣ 1 ≤ B D = \lvert d\rvert_1 \le B D = ∣ d ∣ 1 ≤ B c ( p ( d ) ) ≤ B c(p(d)) \le B c ( p ( d )) ≤ B K ≥ 0 K \ge0 K ≥ 0 A ≥ 1 A \ge1 A ≥ 1 1 1 1 ∣ Ω ( p , q ) ∣ \lvert\Omega(p,q)\rvert ∣ Ω ( p , q )∣ p , q ∈ C B p,q \in C_B p , q ∈ C B
χ ( d , d ) ≥ − A D 2 , u ( d ) ≤ ∑ i d i k i + D . \chi(d,d) \ge-AD^2, \qquad u(d) \le\sum_i d_i k_i + D. χ ( d , d ) ≥ − A D 2 , u ( d ) ≤ i ∑ d i k i + D . Since h ≥ s ( d ) h \ge s(d) h ≥ s ( d ) (28) gives
k ≤ u ( d ) − χ ( d , d ) ≤ ∑ i d i k i + B + A B 2 ≤ B K + B + A B 2 . (29) k \le u(d) - \chi(d,d) \le\sum_i d_i k_i + B + AB^2 \le BK + B + AB^2. \tag*{(29)} k ≤ u ( d ) − χ ( d , d ) ≤ i ∑ d i k i + B + A B 2 ≤ B K + B + A B 2 . (29) If an output parameter satisfies k ≥ L k \ge L k ≥ L
k i ≥ L − ( B − 1 ) K − B − A B 2 . (30) k_i \ge L - (B-1)K - B - AB^2. \tag*{(30)} k i ≥ L − ( B − 1 ) K − B − A B 2 . (30) To see this, single out one of its d i d_i d i B − 1 B-1 B − 1 K K K (30) , hence only finitely many possible d d d k ≥ L k \ge L k ≥ L h ≤ ( u ( d ) − L ) / 2 h \le(u(d)-L)/2 h ≤ ( u ( d ) − L ) /2
Finally, consider a coefficient at exponent of charge at most B B B v e v^e v e B B B K ′ ≥ 0 K' \ge0 K ′ ≥ 0 A ′ A' A ′
e = ∑ ν = 1 D k ν − 2 ∑ ν = 1 D j ν + Q , D ≤ B , j ν ≥ 0 , ∣ Q ∣ ≤ A ′ B 2 . (31) e = \sum_{\nu=1}^{D} k_\nu- 2\sum_{\nu=1}^{D} j_\nu+ Q, \qquad D \le B,\quad j_\nu\ge0,\quad\lvert Q\rvert\le A'B^2. \tag*{(31)} e = ν = 1 ∑ D k ν − 2 ν = 1 ∑ D j ν + Q , D ≤ B , j ν ≥ 0 , ∣ Q ∣ ≤ A ′ B 2 . (31) It follows that
e ≤ B K ′ + A ′ B 2 , k ν ≥ e − ( B − 1 ) K ′ − A ′ B 2 , ∑ ν j ν ≤ B K ′ + A ′ B 2 − e 2 . e \le BK' + A'B^2, \qquad k_\nu\ge e - (B-1)K' - A'B^2, \qquad\sum_\nu j_\nu\le\frac{BK' + A'B^2 - e}{2}. e ≤ B K ′ + A ′ B 2 , k ν ≥ e − ( B − 1 ) K ′ − A ′ B 2 , ν ∑ j ν ≤ 2 B K ′ + A ′ B 2 − e . Only finitely many unit occurrences meet the lower parameter bound, and only finitely many nonnegative index lists meet the last bound. Thus the coefficient is a finite nonnegative integer and its upper energy is bounded. These bounds justify all coefficientwise limits of the finite-list identities, proving the infinite case.
For effectiveness, compute K K K B B B A = A B A=A_B A = A B (30) . For each resulting d d d h h h D d D_d D d Q \mathbb{Q} Q (31) then computes any desired product coefficient from a finite list.
The effective bound is available in the wall applications below. There the roots lie in an explicit finite free cone with basis r 1 , … , r s r_1,\ldots,r_s r 1 , … , r s c ( p ) , c ( q ) ≤ B c(p),c(q)\le B c ( p ) , c ( q ) ≤ B
∣ Ω ( p , q ) ∣ ≤ B 2 max i , j ∣ Ω ( r i , r j ) ∣ . \lvert\Omega(p,q)\rvert\le B^2 \max_{i,j}\lvert\Omega(r_i,r_j)\rvert. ∣ Ω ( p , q )∣ ≤ B 2 i , j max ∣ Ω ( r i , r j )∣ . Taking the maximum of this integer and one supplies A B A_B A B
Positive wall transport and change of chart
The reordering theorem gives positive local changes of coordinates. We now assemble them into a consistent system, define its incoming coordinates, and prove the two properties needed later: positivity of sections and compatibility with a change of simple roots. All wall arrangements in the argument are finite after a specified truncation.
This is a scattering-diagram construction in the framework originating with Kontsevich–Soibelman and Gross–Siebert [20 , 30 ] . Its description by a total transport element is the wall-crossing construction of [32 ] , expressed here in completed quantum-torus coordinates; the locators refer to the version recorded in the bibliography. Quantum wall and theta positivity are developed in [11 ] . We retain direct proofs to specify exactly the support bounds and coefficient algorithms used by the permutation map.
The completion and the incoming prescription
Let M M M Ω \Omega Ω K = Q ( ( v − 1 ) ) K=\mathbb{Q}((v^{-1})) K = Q (( v − 1 ))
X a X b = v Ω ( a , b ) X a + b , V ( a ) = Ω ( ⋅ , a ) ∈ M R ∨ . (32) X_aX_b=v^{\Omega(a,b)}X_{a+b},\qquad V(a)=\Omega(\mathord{\cdot},a)\in M^\vee_{\mathbb{R}}. \tag*{(32)} X a X b = v Ω ( a , b ) X a + b , V ( a ) = Ω ( ⋅ , a ) ∈ M R ∨ . (32) We may assume that Ω \Omega Ω M M M M ⊕ M ∨ M\oplus M^\vee M ⊕ M ∨ Ω ( ( a , f ) , ( b , g ) ) = Ω ( a , b ) + f ( b ) − g ( a ) \Omega((a,f),(b,g))=\Omega(a,b)+f(b)-g(a) Ω (( a , f ) , ( b , g )) = Ω ( a , b ) + f ( b ) − g ( a )
A chart is a finite set C ⊂ M C\subset M C ⊂ M
C + = ∑ c ∈ C N c , ∣ ∑ c u c c ∣ C = ∑ c u c , a ⪯ C b ⟺ b − a ∈ C + . C^+=\sum_{c\in C}\mathbb{N}c,\qquad
\left|\sum_c u_cc\right|_C=\sum_c u_c,\qquad
a\preceq_C b\Longleftrightarrow b-a\in C^+. C + = c ∈ C ∑ N c , c ∑ u c c C = c ∑ u c , a ⪯ C b ⟺ b − a ∈ C + . Every interval { a : m ⪯ C a ⪯ C n } \{a:m\preceq_C a\preceq_C n\} { a : m ⪯ C a ⪯ C n }
G C = 1 + ∏ r ∈ C + ∖ { 0 } K X r . G_C=1+\prod_{r\in C^+\setminus\{0\}}KX_r. G C = 1 + r ∈ C + ∖ { 0 } ∏ K X r . Multiplication, inversion, logarithms, and exponentials are defined by root degree. A coefficient of any such operation is a finite sum over decompositions of its exponent. A section value will belong to the corresponding completed torus module supported in a finite union of translates of C + C^{+} C +
For a covector h h h G C , + ( h ) G_{C,+}(h) G C , + ( h ) G C , 0 ( h ) G_{C,0}(h) G C , 0 ( h ) G C , − ( h ) G_{C,-}(h) G C , − ( h ) h h h g ∈ G C g \in G_C g ∈ G C
g = g + ( h ) g 0 ( h ) g − ( h ) . (33) g = g_{+}(h)g_0(h)g_{-}(h). \tag*{(33)} g = g + ( h ) g 0 ( h ) g − ( h ) . (33) Indeed, suppose all coefficients below degree d d d r r r d d d h h h g 0 ( h ) g_0(h) g 0 ( h ) h h h
The factors define walls. At a generic point of r ⊥ r^{\perp} r ⊥ r r r Ad ( g 0 ) : F ↦ g 0 F g 0 − 1 \operatorname{Ad}(g_0): F \mapsto g_0 F g_0^{-1} Ad ( g 0 ) : F ↦ g 0 F g 0 − 1 h h h Ad ( g − ( h ) ) \operatorname{Ad}(g_{-}(h)) Ad ( g − ( h )) I I I I I II I I
g − ( I I ) = g 0 g − ( I ) , Ad ( g − ( I I ) ) = Ad ( g 0 ) ∘ Ad ( g − ( I ) ) . g_{-}(II) = g_0g_{-}(I), \qquad\operatorname{Ad}(g_{-}(II)) = \operatorname{Ad}(g_0) \circ\operatorname{Ad}(g_{-}(I)). g − ( I I ) = g 0 g − ( I ) , Ad ( g − ( I I )) = Ad ( g 0 ) ∘ Ad ( g − ( I )) . Thus each crossing agrees with the transformation determined by its endpoint, proving path independence and the stated order of composition. At degree at most d d d
Conversely, a consistent assignment of such wall elements, constant on the cells of finite arrangements at each order, comes from (4.2). Take g g g g g g
Each simple root carries the specific unit
D p = ∏ j ≥ 0 ( 1 + v − 1 − 2 j X p ) , p ∈ C . D_p = \prod_{j \ge0}(1+v^{-1-2j}X_p), \qquad p \in C. D p = j ≥ 0 ∏ ( 1 + v − 1 − 2 j X p ) , p ∈ C . Define the wall system by requiring
[ X r ] log g 0 ( V ( r ) ) = { [ X r ] log D p , r = j p , p ∈ C , j ≥ 1 , 0 , otherwise . [X_r]\log g_0(V(r)) =
\begin{cases}
[X_r]\log D_p, & r = jp,\quad p \in C,\ j \ge1,\\
0, & \text{otherwise}.
\end{cases} [ X r ] log g 0 ( V ( r )) = { [ X r ] log D p , 0 , r = j p , p ∈ C , j ≥ 1 , otherwise . These equations determine g g g log g = ∑ r ℓ r X r \log g = \sum_r \ell_r X_r log g = ∑ r ℓ r X r ∣ r ∣ C |r|_C ∣ r ∣ C V ( r ) V(r) V ( r ) ℓ r X r \ell_r X_r ℓ r X r V ( r ) ( r ) = 0 V(r)(r) = 0 V ( r ) ( r ) = 0 r r r ℓ r \ell_r ℓ r
Here and below, “incoming” refers to the end of a wall in the direction V ( r ) V(r) V ( r ) (4.4) , even when V ( r ) V(r) V ( r ) ker V ( r ) \ker V(r) ker V ( r ) τ r ( B ) = [ X r ] B \tau_r(B)=[X_r]B τ r ( B ) = [ X r ] B a + b = r a+b=r a + b = r Ω ( a , b ) = Ω ( a , r ) = 0 \Omega(a,b)=\Omega(a,r)=0 Ω ( a , b ) = Ω ( a , r ) = 0
τ r log ( B 1 B 2 ) = τ r log B 1 + τ r log B 2 \tau_r\log(B_1B_2)=\tau_r\log B_1+\tau_r\log B_2 τ r log ( B 1 B 2 ) = τ r log B 1 + τ r log B 2 for elements with constant term one in that algebra. For completeness, replace each X a X_a X a z ∣ a ∣ C X a z^{|a|_{\mathbb C}}X_a z ∣ a ∣ C X a τ r ( ( log B ) ′ ) = τ r ( B ′ B − 1 ) \tau_r((\log B)')=\tau_r(B'B^{-1}) τ r (( log B ) ′ ) = τ r ( B ′ B − 1 ) (4.5) , and the constant terms are zero. This is a formal calculation at each root degree. Factor g 0 ( V ( r ) ) g_0(V(r)) g 0 ( V ( r )) r ⊥ r^\perp r ⊥ X r X_r X r (4.5) therefore identifies its logarithmic r r r D p D_p D p
Positive wall factors and incoming coordinates
Recall the two elementary unit types from Theorem 3.1:
U a , k , f = ∏ j ≥ 0 f ( v k − 2 j X a ) , f ( T ) = 1 + T or f ( T ) = ( 1 − T ) − 1 . U_{a,k,f}=\prod_{j\geq0}f(v^{k-2j}X_a),\qquad f(T)=1+T\quad\text{or}\quad f(T)=(1-T)^{-1}. U a , k , f = j ≥ 0 ∏ f ( v k − 2 j X a ) , f ( T ) = 1 + T or f ( T ) = ( 1 − T ) − 1 . An allowed list has its parameters k k k k k k
Lemma 4.1 (The unit normalization and positive crossing). For j ≥ 0 j\geq0 j ≥ 0
[ X j p ] D p = v − j 2 ∏ i = 1 j ( 1 − v − 2 i ) . (34) [X_{jp}]D_p=\frac{v^{-j^2}}{\prod_{i=1}^{j}(1-v^{-2i})}. \tag*{(34)} [ X j p ] D p = ∏ i = 1 j ( 1 − v − 2 i ) v − j 2 . (34) Let t = Ω ( a , m ) t=\Omega(a,m) t = Ω ( a , m )
Ad ( U a , k , f ) X m = X m U a , k , f ( v 2 t X a ) U a , k , f ( X a ) . (35) \operatorname{Ad}(U_{a,k,f})X_m=X_m\frac{U_{a,k,f}(v^{2t}X_a)}{U_{a,k,f}(X_a)}. \tag*{(35)} Ad ( U a , k , f ) X m = X m U a , k , f ( X a ) U a , k , f ( v 2 t X a ) . (35) For t > 0 t>0 t > 0 ∏ ℓ = 1 t f ( v k + 2 ℓ X a ) \prod_{\ell=1}^{t}f(v^{k+2\ell}X_a) ∏ ℓ = 1 t f ( v k + 2 ℓ X a ) t < 0 t<0 t < 0 ∏ ℓ = t + 1 0 f ( v k + 2 ℓ X a ) \prod_{\ell=t+1}^{0}f(v^{k+2\ell}X_a) ∏ ℓ = t + 1 0 f ( v k + 2 ℓ X a ) Ad ( U a , k , f ) ε X m \operatorname{Ad}(U_{a,k,f})^\varepsilon X_m Ad ( U a , k , f ) ε X m ε t ≥ 0 \varepsilon t\geq0 εt ≥ 0
Proof. Choosing j j j 0 ≤ i 1 < ⋯ < i j 0\leq i_1<\cdots<i_j 0 ≤ i 1 < ⋯ < i j (4.3) gives weight v − j − 2 ∑ i s v^{-j-2\sum i_s} v − j − 2 ∑ i s 0 , 1 , … , j − 1 0,1,\ldots,j-1 0 , 1 , … , j − 1 v − 2 , … , v − 2 j v^{-2},\ldots,v^{-2j} v − 2 , … , v − 2 j (34) . The commutation relation X a X m = v 2 t X m X a X_aX_m=v^{2t}X_mX_a X a X m = v 2 t X m X a (35) . Cancellation of the two infinite strings leaves the displayed finite strings. Each factor 1 + v b X a 1+v^bX_a 1 + v b X a ( 1 − v b X a ) − 1 (1-v^bX_a)^{-1} ( 1 − v b X a ) − 1 X m X a j X_mX_a^j X m X a j v v v t = 0 t=0 t = 0
For later use, the finite formula for the normalized simple unit is particularly convenient. If t = Ω ( p , m ) ≠ 0 t=\Omega(p,m)\ne0 t = Ω ( p , m ) = 0 a = ∣ t ∣ a=|t| a = ∣ t ∣
Ad ( D p ) sign ( t ) X m = ∑ j = 0 a e j ( v 1 − a , v 3 − a , … , v a − 1 ) X m + j p . (36) \operatorname{Ad}(D_p)^{\operatorname{sign}(t)}X_m=\sum_{j=0}^{a}e_j(v^{1-a},v^{3-a},\ldots,v^{a-1})X_{m+jp}. \tag*{(36)} Ad ( D p ) sign ( t ) X m = j = 0 ∑ a e j ( v 1 − a , v 3 − a , … , v a − 1 ) X m + j p . (36) Here e j e_j e j a a a t = 1 t=1 t = 1 X m + X m + p X_m+X_{m+p} X m + X m + p
Proposition 4.2 (Positive factors on every wall). At every generic point of a wall, and to every specified root order, its element is a product of elementary units on its ray with the finiteness conditions above. The same conclusion holds if the simple incoming data are replaced by allowed products of elementary units. If a crossing has the sign of − V ( m ) -V(m) − V ( m ) X m X_m X m N ( ( v − 1 ) ) \mathbb{N}((v^{-1})) N (( v − 1 ))
Proof. Fix a root-degree bound d d d d d d R > 0 r \mathbb{R}_{>0}r R > 0 r r ⊥ r^\perp r ⊥ V ( r ) V(r) V ( r ) r r r s s s Ω ( s , r ) = 0 \Omega(s,r)=0 Ω ( s , r ) = 0
Order the positive rays in this plane so that the skew pairing of an earlier ray with a later ray is positive. At the incoming end V ( a ) V(a) V ( a ) a a a C + C^+ C +
There is a small induction issue at degree d d d d d d d − 1 d-1 d − 1 d d d d d d d d d
For the last assertion, a positive-to-negative crossing has Ω ( r , m ) > 0 \Omega(r,m)>0 Ω ( r , m ) > 0 Ω ( r , m ) < 0 \Omega(r,m)<0 Ω ( r , m ) < 0 r r r
We spell out why infinite lists still give finite integer coefficients at a specified energy. At a fixed root bound there are finitely many possible arguments, the total multiplicity of selected nonconstant factors is bounded, and all skew-pairing shifts between these factors are bounded. Their parameters have a common upper bound K 0 K_0 K 0 E E E − ∞ -\infty − ∞ E E E N ( ( v − 1 ) ) \mathbb{N}((v^{-1})) N (( v − 1 ))
A section is a family of values transported by these consistent wall operations. Any value with the stipulated support in one generic chamber determines a section. Its incoming coefficient is
A n ( F ) = [ X n ] F ( V ( n ) + ϵ ) , A_n(F)=[X_n]F(V(n)+\epsilon), A n ( F ) = [ X n ] F ( V ( n ) + ϵ ) , where a sufficiently small generic perturbation is chosen at the finite order needed for that coefficient. This does not depend on the perturbation. A wall that can separate two such choices has normal r r r Ω ( r , n ) = 0 \Omega(r,n)=0 Ω ( r , n ) = 0 X n X_n X n n − j r n-jr n − j r r r r
In any fixed chamber H H H A n ( F ) A_n(F) A n ( F ) [ X n ] F ( H ) [X_n]F(H) [ X n ] F ( H ) Θ m \Theta_m Θ m m + C + m+C^+ m + C +
A n ( Θ m ) = { 1 , n = m , 0 , n ≠ m . A_n(\Theta_m)=
\begin{cases}
1, & n=m,\\
0, & n\ne m.
\end{cases} A n ( Θ m ) = { 1 , 0 , n = m , n = m . Its leading monomial is X m X_m X m [11 , 21 ] . The definition and positivity argument below use only the explicit coefficient recursion in our convention. More generally, within any fixed finite union of translates of C + C^+ C +
F = ∑ n A n ( F ) Θ n . F=\sum_n A_n(F)\Theta_n. F = n ∑ A n ( F ) Θ n . For a requested exponent this is a finite sum, by the interval property of the free cone.
Lemma 4.3 (The positive coefficient recursion). Fix a generic target chamber H H H h h h n n n h + s V ( n ) h+sV(n) h + s V ( n ) s s s s = 0 s=0 s = 0 W i : I i ⟶ I i + 1 W_i:I_i\longrightarrow I_{i+1} W i : I i ⟶ I i + 1 p i p_i p i
J i ( a , j ) = [ X a + j p i ] W i ( X a ) , j ≥ 0. J_i(a,j)=[X^{a+jp_i}]W_i(X^a),\qquad j\ge0. J i ( a , j ) = [ X a + j p i ] W i ( X a ) , j ≥ 0. Then J i ( a , 0 ) = 1 J_i(a,0)=1 J i ( a , 0 ) = 1 a = n − j p i a=n-jp_i a = n − j p i J i ( a , j ) ∈ N ( ( v − 1 ) ) J_i(a,j)\in\mathbb{N}((v^{-1})) J i ( a , j ) ∈ N (( v − 1 ))
[ X n ] F ( H ) = A n ( F ) + ∑ i ∑ j > 0 n − j p i in the support bound J i ( n − j p i , j ) [ X n − j p i ] F ( I i ) . (37) [X_n]F(H)=A_n(F)+\sum_i\sum_{\substack{j>0\\ n-jp_i\ \text{in the support bound}}}J_i(n-jp_i,j)[X_{n-jp_i}]F(I_i). \tag*{(37)} [ X n ] F ( H ) = A n ( F ) + i ∑ j > 0 n − j p i in the support bound ∑ J i ( n − j p i , j ) [ X n − j p i ] F ( I i ) . (37) All sums are finite at a fixed exponent. With the simple data (4.3) , the jump coefficients are effectively computable at every fixed energy by finite rational arithmetic and Laurent expansion in v − 1 v^{-1} v − 1 v v v
Proof. After rescaling by s s s V ( n ) V(n) V ( n ) X n X_n X n A n ( F ) A_n(F) A n ( F ) n n n h h h − V ( n ) -V(n) − V ( n ) n − j p i n-jp_i n − j p i n n n X n X_n X n (37) . The exponents in each inner sum lie in a finite cone interval. The arrangement contains only the roots needed for those intervals, so the outer sum is finite as well.
For effectivity, (34) gives rational functions of v v v (4.4) and (33) , followed by inversion and multiplication at bounded root order, therefore give rational functions of v v v v − 1 = 0 v^{-1}=0 v − 1 = 0 (37) . Recursing on its strictly smaller exponents terminates, since the cone intervals are finite. At fixed total energy, upper bounds on the finitely many factor energies also give lower bounds on each of them. Hence the required integer coefficient is obtained by a finite computation.
Theorem 4.4 (Positive sections). Every Θ m \Theta_m Θ m has coefficients in N ( ( v − 1 ) ) \mathbb{N}((v^{-1})) N (( v − 1 )) in every chamber. More generally, the same is true of a section F F F all of whose incoming coefficients belong to N ( ( v − 1 ) ) \mathbb{N}((v^{-1})) N (( v − 1 ))
Proof. Fix a target exponent and its finite interval above the support lower bounds. Induct on the addition order in this interval, using (37) . Its initial term is nonnegative by hypothesis, and every other term is a nonnegative jump coefficient times a coefficient at a strictly smaller exponent. The induction proves positivity. The energy bounds in Proposition 4.2 and Lemma 4.3 justify each multiplication and sum in the Laurent completion. Equation (4.10) gives the special case.
Corollary 4.5 (Positive products). The structure coefficients in
Θ m 1 ⋯ Θ m b = ∑ n A n ( Θ m 1 ⋯ Θ m b ) Θ n \Theta_{m_1}\cdots\Theta_{m_b}=\sum_n A_n(\Theta_{m_1}\cdots\Theta_{m_b})\Theta_n Θ m 1 ⋯ Θ m b = n ∑ A n ( Θ m 1 ⋯ Θ m b ) Θ n belong to N ( ( v − 1 ) ) \mathbb{N}((v^{-1})) N (( v − 1 )) Products and expansions are locally finite at every specified exponent.
Proof. Evaluate the product near V ( n ) V(n) V ( n ) n n n v v v (4.11) proves the assertion.
A finite bound in the mutation direction
Mutation compatibility is a basic feature of classical cluster theta functions [21 ] and their quantum counterparts [11 ] . We next compare two different cone completions, keeping the finite-fiber argument needed for equality of actual coefficients. From this point the simple incoming data are exactly (4.3) . Fix p ∈ C p\in C p ∈ C
α c = Ω ( p , c ) , c ′ = c + [ − α c ] + p ( c ≠ p ) , C ′ = { − p } ∪ { c ′ : c ∈ C ∖ { p } } . (38) \alpha_c=\Omega(p,c),\qquad c'=c+[-\alpha_c]_+p\quad(c\ne p),\qquad C'=\{-p\}\cup\{c'\colon c\in C\setminus\{p\}\}. \tag*{(38)} α c = Ω ( p , c ) , c ′ = c + [ − α c ] + p ( c = p ) , C ′ = { − p } ∪ { c ′ : c ∈ C ∖ { p }} . (38) where [ x ] + = max ( x , 0 ) [x]_+=\max(x,0) [ x ] + = max ( x , 0 ) C ′ C' C ′
S ( m ) = m − Ω ( p , m ) p , S ∨ h = h ∘ S − 1 . S(m)=m-\Omega(p,m)p,\qquad S^\vee h=h\circ S^{-1}. S ( m ) = m − Ω ( p , m ) p , S ∨ h = h ∘ S − 1 . The map S S S Ω \Omega Ω X m ↦ X S ( m ) X_m\mapsto X_{S(m)} X m ↦ X S ( m )
T ( h ) = { h , h ( p ) ≥ 0 , S ∨ h , h ( p ) ≤ 0. T(h)=
\begin{cases}
h, & h(p)\ge0,\\
S^\vee h, & h(p)\le0.
\end{cases} T ( h ) = { h , S ∨ h , h ( p ) ≥ 0 , h ( p ) ≤ 0. The two definitions coincide on p ⊥ p^\perp p ⊥
For a non-pure root, write
r = k p + u , u = ∑ c ≠ p u c c ≠ 0 , k , u c ∈ N . r=kp+u,\qquad u=\sum_{c\ne p}u_c c\ne0,\qquad k,u_c\in\mathbb{N}. r = k p + u , u = c = p ∑ u c c = 0 , k , u c ∈ N . Its non-p p p is ∣ u ∣ = ∑ c ≠ p u c |u|=\sum_{c\ne p}u_c ∣ u ∣ = ∑ c = p u c σ ∈ { + 1 , − 1 } \sigma\in\{+1,-1\} σ ∈ { + 1 , − 1 }
M σ ( u ) = ∑ c ≠ p [ − σ α c ] + u c . M_\sigma(u)=\sum_{c\ne p}[-\sigma\alpha_c]_+u_c. M σ ( u ) = c = p ∑ [ − σ α c ] + u c . Lemma 4.6 (Finite support in each p p p On the open side sign h ( p ) = σ h(p)=\sigma h ( p ) = σ k p + u kp+u k p + u
0 ≤ k ≤ M σ ( u ) . 0\le k\le M_\sigma(u). 0 ≤ k ≤ M σ ( u ) . The pure p p p D p D_p D p
Proof. Projection to the face N p N_p N p p p p p ⊥ p^\perp p ⊥ g g g D p D_p D p
We prove (4.17) by induction on ∣ u ∣ |u| ∣ u ∣ k + ∣ u ∣ k+|u| k + ∣ u ∣ k p + u kp+u k p + u k k k
Put t = Ω ( p , u ) = ∑ c α c u c t=\Omega(p,u)=\sum_c\alpha_cu_c t = Ω ( p , u ) = ∑ c α c u c t ≠ 0 t\ne0 t = 0 σ = sign ( t ) \sigma=\operatorname{sign}(t) σ = sign ( t ) ( k p + u ) ⊥ (kp+u)^\perp ( k p + u ) ⊥ V ( k p + u ) V(kp+u) V ( k p + u ) p ⊥ p^\perp p ⊥ p p p h ( p ) + s t h(p)+st h ( p ) + s t s ≥ 0 s\ge0 s ≥ 0 t = 0 t=0 t = 0 k = 0 k=0 k = 0
Consider a joint off the cut along this line. Every normal involved has positive non-p p p p p p ∣ u ∣ |u| ∣ u ∣ p p p ∣ u ∣ |u| ∣ u ∣ (4.17) . The bound is additive in u u u
{ k p + u : 0 ≤ k ≤ M σ ( u ) } . \{kp+u:0\le k\le M_\sigma(u)\}. { k p + u : 0 ≤ k ≤ M σ ( u )} . It follows, by the coefficient recursion for ray factorization, that the bound persists at this joint. This proves the upstream assertion for each k k k k k k M σ ( u ) M_\sigma(u) M σ ( u )
Suppose t ≠ 0 t\ne0 t = 0 p ⊥ ∩ u ⊥ p^\perp\cap u^\perp p ⊥ ∩ u ⊥ p p p u u u u u u p p p σ \sigma σ p p p
Separate the pure factor D p D_p D p σ = + 1 \sigma=+1 σ = + 1 p p p D p D_p D p σ = − 1 \sigma=-1 σ = − 1 p p p D p − 1 D_p^{-1} D p − 1 X k p + w X_{kp+w} X k p + w j p jp j p
0 ≤ j ≤ ∣ Ω ( p , w ) ∣ . 0\le j\le|\Omega(p,w)|. 0 ≤ j ≤ ∣Ω ( p , w ) ∣. All relevant w w w
M − σ ( w ) = M σ ( w ) + ∣ Ω ( p , w ) ∣ . M_{-\sigma}(w)=M_\sigma(w)+|\Omega(p,w)|. M − σ ( w ) = M σ ( w ) + ∣Ω ( p , w ) ∣. ends_mid=1 Thus the whole conjugated non-pure product has the downstream bound. So do its ray factors: coefficientwise factorization cannot introduce an exponent outside an additive support monoid containing the product’s support. Explicitly, for the first putative such exponent the defining coefficient is zero in the product, and every term subtracted from it is a sum of already permitted exponents, a contradiction.
At the current degree, the coefficients needed at the cut are either of smaller non-p p p
The numerical bound also controls the change of completion. Let L + = id L_+ = \operatorname{id} L + = id L − = S L_- = S L − = S
L σ ( k p + u ) = ∑ c ≠ p u c c ′ + ( M σ ( u ) − k ) ( − p ) . L_\sigma(kp+u)=\sum_{c\ne p}u_c c' + (M_\sigma(u)-k)(-p). L σ ( k p + u ) = c = p ∑ u c c ′ + ( M σ ( u ) − k ) ( − p ) . Thus every supported root off the cut maps into C ′ + C^{\prime+} C ′ + B = max c ≠ p ∣ α c ∣ B=\max_{c\ne p}|\alpha_c| B = max c = p ∣ α c ∣ B = 0 B=0 B = 0 M σ ( u ) ≤ B ∣ u ∣ M_\sigma(u)\le B|u| M σ ( u ) ≤ B ∣ u ∣ d d d ∣ u ∣ ≤ d |u|\le d ∣ u ∣ ≤ d ( B + 1 ) d (B+1)d ( B + 1 ) d
Mutation and equality of actual coefficients
Theorem 4.7 (Change of chart). The wall system for C C C D c D_c D c C ′ C' C ′ D c ′ D_{c'} D c ′ p ⊥ p^\perp p ⊥ T T T (4.15) and act on exponents by L σ L_\sigma L σ σ \sigma σ D − p D_{-p} D − p F F F F ′ F' F ′
F = Ad ( D p ) F ′ . (39) F=\operatorname{Ad}(D_p)F'. \tag*{(39)} F = Ad ( D p ) F ′ . (39) For h ( p ) > 0 h(p)>0 h ( p ) > 0 h ( p ) < 0 h(p)<0 h ( p ) < 0 S S S
A n ( F ) = A μ p ( n ) ( F ′ ) , μ p ( n ) = n + [ − Ω ( p , n ) ] + p . A_n(F)=A_{\mu_p(n)}(F'),\qquad\mu_p(n)=n+[-\Omega(p,n)]_+p. A n ( F ) = A μ p ( n ) ( F ′ ) , μ p ( n ) = n + [ − Ω ( p , n ) ] + p . The map μ p : M → M \mu_p:M\to M μ p : M → M
Proof. First we establish the identity of transformations at the cut, with the normalization of Lemma 4.1:
S ∘ Ad ( D p ) = Ad ( D − p ) − 1 . (40) S\circ\operatorname{Ad}(D_p)=\operatorname{Ad}(D_{-p})^{-1}. \tag*{(40)} S ∘ Ad ( D p ) = Ad ( D − p ) − 1 . (40) For t = Ω ( p , m ) ≥ 0 t=\Omega(p,m)\ge0 t = Ω ( p , m ) ≥ 0 X m + j p X^{m+jp} X m + j p Ad ( D p ) X m \operatorname{Ad}(D_p)X^m Ad ( D p ) X m
b t , j = e j ( v 1 − t , v 3 − t , … , v t − 1 ) . b_{t,j}=e_j(v^{1-t},v^{3-t},\ldots,v^{t-1}). b t , j = e j ( v 1 − t , v 3 − t , … , v t − 1 ) . The displayed letters are invariant under inversion and have product one, so b t , j = b t , t − j b_{t,j}=b_{t,t-j} b t , j = b t , t − j S S S m + j p m+jp m + j p m − ( t − j ) p m-(t-j)p m − ( t − j ) p Ad ( D − p ) − 1 X m \operatorname{Ad}(D_{-p})^{-1}X^m Ad ( D − p ) − 1 X m b t , j b_{t,j} b t , j m − j p m-jp m − j p (40) on X m X^m X m t < 0 t<0 t < 0 X − m X_{-m} X − m
A common ring for the comparison. Set Z = X p Z=X_p Z = X p M = Z p ⊕ L M=Zp\oplus L M = Z p ⊕ L C ∖ { p } C\setminus\{p\} C ∖ { p } K ( Z ) K(Z) K ( Z ) X ℓ X_\ell X ℓ ℓ ∈ L \ell\in L ℓ ∈ L C ∖ { p } C\setminus\{p\} C ∖ { p } p p p (32) and the rule
X ℓ f ( Z ) = f ( v − 2 Ω ( p , ℓ ) Z ) X ℓ . X_\ell f(Z)=f\left(v^{-2\Omega(p,\ell)}Z\right)X_\ell. X ℓ f ( Z ) = f ( v − 2Ω ( p , ℓ ) Z ) X ℓ . Consequently a coefficient at each specified non-p p p Z Z Z p p p Z Z Z
By Lemma 4.6, a non-cut wall element is polynomial in Z Z Z p p p p p p p p p Z Z Z D p ± 1 D_p^{\pm1} D p ± 1 Z Z Z X ℓ X_\ell X ℓ Z Z Z X ℓ X_\ell X ℓ (35) . It, too, acts on this ring. The map S S S p p p p p p
We justify importing the old consistency into this ring. The expansion homomorphism
K ( Z ) ⟶ K ( ( Z ) ) K(Z)\longrightarrow K((Z)) K ( Z ) ⟶ K (( Z )) at Z = 0 Z=0 Z = 0 C + C^+ C + p p p Z Z Z p p p
Consistency and incoming data after mutation. Push the non-cut elements by L σ L_\sigma L σ D − p D_{-p} D − p (4.18) shows that this is a system in the new cone completion, finite to every new root order. On any loop, the linear identifications on successive open sides cancel; at a cut crossing their discrepancy is exactly corrected by (40) . Thus the pushed path operations are consistent in the common rational ring. Expand now at Z − 1 = 0 Z^{-1}=0 Z − 1 = 0 c c c c ′ = c + [ − α c ] + p c'=c+[-\alpha_c]+p c ′ = c + [ − α c ] + p Z Z Z v v v (4.18) ensures that every pushed increment is C ′ + C'^+ C ′ + r r r m m m Ω ( r , m ) ≠ 0 \Omega(r,m)\ne0 Ω ( r , m ) = 0 X m X_m X m
It remains to identify this system by its incoming prescription. A symplectic linear map L L L V ( L r ) = L V ( r ) V(Lr)=L^V(r) V ( L r ) = L V ( r ) c ≠ p c \ne p c = p V ( c ) ( p ) = α c V(c)(p)=\alpha_c V ( c ) ( p ) = α c c c c c ′ = c + [ − α c ] + p c'=c+[-\alpha_c]_+p c ′ = c + [ − α c ] + p D c ′ D_{c'} D c ′ p p p (4.5) . A component with no preimage wall has zero coefficient. The pure incoming element is D − p D_{-p} D − p (4.4) identifies the pushed system with the system for C ′ C' C ′
Actual coefficients of polynomial sections. We now use the finite-polynomial hypothesis in (39) . Choose a point on the cut with h ( c ) < − 1 h(c)<-1 h ( c ) < − 1 c ≠ p c\ne p c = p h ( p ) h(p) h ( p ) C C C B B B (4.18) , choosing ∣ h ( p ) ∣ < ( B + 1 ) − 1 |h(p)|<(B+1)^{-1} ∣ h ( p ) ∣ < ( B + 1 ) − 1
h ( k p + u ) ≤ B ∣ u ∣ ∣ h ( p ) ∣ − ∣ u ∣ < 0. h(kp+u)\le B|u|\,|h(p)|-|u|<0. h ( k p + u ) ≤ B ∣ u ∣ ∣ h ( p ) ∣ − ∣ u ∣ < 0. At the cut itself h ( u ) < 0 h(u)<0 h ( u ) < 0 h ( − p ) < 0 h(-p)<0 h ( − p ) < 0 h ( c ′ ) < 0 h(c')<0 h ( c ′ ) < 0
On the positive side, the old value is
Ad ( D p ) − 1 F = F ′ , \operatorname{Ad}(D_p)^{-1}F=F', Ad ( D p ) − 1 F = F ′ , which is the actual finite Laurent polynomial specified in the new chamber. On the negative side the pushed old value is S F SF S F (40) and (39) give
S F = Ad ( D − p ) − 1 F ′ . SF=\operatorname{Ad}(D_{-p})^{-1}F'. S F = Ad ( D − p ) − 1 F ′ . This too is a finite Laurent polynomial, because F F F S S S
To reach any other chamber on a fixed open side, transport entirely within that half-space. Only non-cut walls occur. Their elements and inverses have finite Laurent support in the p p p p p p p p p L σ L_\sigma L σ
Finally, put t = Ω ( p , n ) t=\Omega(p,n) t = Ω ( p , n ) V ( n ) V(n) V ( n ) t t t n n n n n n t > 0 t>0 t > 0 S ( n ) = n − t p S(n)=n-tp S ( n ) = n − tp t < 0 t<0 t < 0 t = 0 t=0 t = 0 n n n (4.20) . Its label map preserves Ω ( p , n ) \Omega(p,n) Ω ( p , n ) [ − Ω ( p , n ) ] + p [-\Omega(p,n)]_+p [ − Ω ( p , n ) ] + p
The triangular chart and monomial sections
We now identify the evaluated monomial symmetric polynomials with single positive sections. The auxiliary graph used for this purpose contains every naturally labeled unit interval graph as an ordered induced subgraph. All lattice vectors in this section belong to the free lattice on the vertices; the extra dual directions, if used to make the skew form nondegenerate, never occur in their support.
Positive theta sections do not yet give elementary positivity: we must identify each evaluated monomial symmetric function with a single such section. We first introduce an auxiliary graph with a distinguished independent set of vertices. Repeated rotations constrain the incoming coefficients, but those constraints alone do not force the desired identity. A separate analysis of the degree-one symmetric function will give a positive support bound for its higher-degree analogues; that bound is what makes the final subtraction argument possible.
The chart and its rotations
Fix an integer D ≥ 1 D \ge1 D ≥ 1 n 0 = D − 1 n_0 = D - 1 n 0 = D − 1 d 1 , … , d D d_1,\ldots,d_D d 1 , … , d D 1 , … , D 1,\ldots,D 1 , … , D 1 ≤ j ≤ i ≤ n 0 1 \le j \le i \le n_0 1 ≤ j ≤ i ≤ n 0 b j , i b_{j,i} b j , i i + θ j , i i+\theta_{j,i} i + θ j , i 0 < θ j , i < 1 0 < \theta_{j,i} < 1 0 < θ j , i < 1 D > 1 D > 1 D > 1
( n 0 , n 0 ) ; ( n 0 − 1 , n 0 − 1 ) , ( n 0 − 1 , n 0 ) ; … ; ( 1 , 1 ) , ( 1 , 2 ) , … , ( 1 , n 0 ) . (n_0,n_0);\quad(n_0-1,n_0-1),(n_0-1,n_0);\quad\ldots;\quad(1,1),(1,2),\ldots,(1,n_0). ( n 0 , n 0 ) ; ( n 0 − 1 , n 0 − 1 ) , ( n 0 − 1 , n 0 ) ; … ; ( 1 , 1 ) , ( 1 , 2 ) , … , ( 1 , n 0 ) . The index i i i level , and j j j row . Two vertices are adjacent precisely when their times differ by less than 1. In particular, the anchors are independent, bridges on one level form a clique, and bridges on neighboring levels are adjacent precisely when the bridge on the higher level has the earlier phase.
Use the vertex names also for their independent lattice vectors. The skew form has Ω ( b , a ) = 1 \Omega(b,a)=1 Ω ( b , a ) = 1 a a a b b b X a X b = v Ω ( a , b ) X a + b X_aX_b=v^{\Omega(a,b)}X_{a+b} X a X b = v Ω ( a , b ) X a + b
E k = e k ( Y ) = ∑ I i n d e p e n d e n t ∣ I ∣ = k X ∑ a ∈ I a , U = E 1 , E_k=e_k(Y)=\sum_{\substack{I\ \mathrm{independent}\\ |I|=k}}X_{\sum_{a\in I}a},\qquad U=E_1, E k = e k ( Y ) = I independent ∣ I ∣ = k ∑ X ∑ a ∈ I a , U = E 1 , commute by Proposition [2 ] . An independent set has at most D D D [ 1 , D ] [1,D] [ 1 , D ] P ( Y ) P(Y) P ( Y ) P P P D D D
Lemma 5.1 (Embedding). Every naturally labeled unit interval graph on n n n n n n
Proof. For n = 0 n=0 n = 0 D = 1 D=1 D = 1 n > 0 n>0 n > 0 t 1 , … , t n t_1,\ldots,t_n t 1 , … , t n a < b a<b a < b t b − t a < 1 t_b-t_a<1 t b − t a < 1 t 1 t_1 t 1 k ≥ 2 k \ge2 k ≥ 2 t k − 1 t_{k-1} t k − 1 k k k s , s + 1 , … , k − 1 s,s+1,\ldots,k-1 s , s + 1 , … , k − 1 h h h t k > t k − 1 + 1 t_k>t_{k-1}+1 t k > t k − 1 + 1
max { t k − 1 , t s − 1 + 1 } < t k < t s + 1 , \max\{t_{k-1},t_{s-1}+1\}<t_k<t_s+1, max { t k − 1 , t s − 1 + 1 } < t k < t s + 1 , omitting t s − 1 + 1 t_{s-1}+1 t s − 1 + 1 s = 1 s=1 s = 1 s > 1 s>1 s > 1 t s − 1 < t s t_{s-1}<t_s t s − 1 < t s s = k − 1 s=k-1 s = k − 1 s s s k − 1 k-1 k − 1 h ( s ) ≥ k h(s)\ge k h ( s ) ≥ k
Shift every time by a common integer so that every level ⌊ t a ⌋ \lfloor t_a\rfloor ⌊ t a ⌋ n n n D D D D − 1 D-1 D − 1 n n n n , n − 1 , … , 1 n,n-1,\ldots,1 n , n − 1 , … , 1 i ≥ n i\ge n i ≥ n □ \square □
Give every vertex weight 1 1 1
d i , b i , i , b i − 1 , i , … , b 1 , i , d i + 1 . d_i,b_{i,i},b_{i-1,i},\ldots,b_{1,i},d_{i+1}. d i , b i , i , b i − 1 , i , … , b 1 , i , d i + 1 . Let C C C d 1 d_1 d 1 C C C C + = ∑ c ∈ C N c C^+=\sum_{c\in C}\mathbb{N}c C + = ∑ c ∈ C N c D c D_c D c a a a a − d 1 a-d_1 a − d 1 C + C^+ C + P ( Y ) P(Y) P ( Y ) N N N
Here and below P ( Y ) P(Y) P ( Y )
A rotation moves the globally first bridge b b b i i i
b ′ = b + δ i , δ i = d i + 1 − d i , p = b − d i . b'=b+\delta_i,\qquad\delta_i=d_{i+1}-d_i,\qquad p=b-d_i. b ′ = b + δ i , δ i = d i + 1 − d i , p = b − d i . The anchors are fixed. At this step
Ω ( p , d i ) = 1 , Ω ( p , d i + 1 ) = − 1 , Ω ( p , b ) = 1 , \Omega(p,d_i)=1,\qquad\Omega(p,d_{i+1})=-1,\qquad\Omega(p,b)=1, Ω ( p , d i ) = 1 , Ω ( p , d i + 1 ) = − 1 , Ω ( p , b ) = 1 , and p p p p ↦ − p p\mapsto-p p ↦ − p c ↦ c + [ − Ω ( p , c ) ] + p c\mapsto c+[-\Omega(p,c)]_+p c ↦ c + [ − Ω ( p , c ) ] + p p p p 2 p 2p 2 p − p -p − p d i + 1 − b ′ d_{i+1}-b' d i + 1 − b ′ b ′ b' b ′
Lemma 5.2 (Polynomial comparison under rotation). Let Y ′ Y' Y ′ symmetric polynomial P P P
P ( Y ) = Ad ( D p ) P ( Y ′ ) . (41) P(Y)=\operatorname{Ad}(D_p)P(Y'). \tag*{(41)} P ( Y ) = Ad ( D p ) P ( Y ′ ) . (41) Both sides are finite Laurent polynomials, so the actual incoming coefficients satisfy
A m ( P ( Y ) ) = A m + [ − Ω ( p , m ) ] + p ( P ( Y ′ ) ) . A_m(P(Y))=A_{m+[-\Omega(p,m)]_+p}(P(Y')). A m ( P ( Y )) = A m + [ − Ω ( p , m ) ] + p ( P ( Y ′ )) . Proof. It suffices to prove (5.5) for E k E_k E k { d i , b , d i + 1 } \{d_i,b,d_{i+1}\} { d i , b , d i + 1 } b b b d i d_i d i b ′ b' b ′ d i + 1 d_{i+1} d i + 1
Ad ( D p ) X d i = X d i + X b , Ad ( D p ) ( X d i + 1 + X b ′ ) = X d i + 1 , Ad ( D p ) X d i + d i + 1 = X d i + d i + 1 . \begin{aligned}
\operatorname{Ad}(D_p)X_{d_i}&=X_{d_i}+X_b,\\
\operatorname{Ad}(D_p)(X_{d_{i+1}}+X_{b'})&=X_{d_{i+1}},\\
\operatorname{Ad}(D_p)X_{d_i+d_{i+1}}&=X_{d_i+d_{i+1}}.
\end{aligned} Ad ( D p ) X d i Ad ( D p ) ( X d i + 1 + X b ′ ) Ad ( D p ) X d i + d i + 1 = X d i + X b , = X d i + 1 , = X d i + d i + 1 . For completeness, the first identity is the centered binomial formula with pairing 1 and d i + p = b d_i+p=b d i + p = b − 1 -1 − 1 d i + 1 + p = b ′ d_{i+1}+p=b' d i + 1 + p = b ′ X p X_p X p { d i , d i + 1 } \{d_i,d_{i+1}\} { d i , d i + 1 } E k E_k E k E k E_k E k P P P (5.6) . □ \square □
Repeat the rotations indefinitely. One period moves every bridge once. After L L L i i i b + L δ i b+L\delta_i b + L δ i (5.1) , and the roots are denoted by C L C_L C L
Stationarity and pure incoming coefficients
Lemma 5.3 (Stationary incoming labels). Let P P P N N N A m ( P ( Y ) ) ≠ 0 A_m(P(Y))\ne0 A m ( P ( Y )) = 0
m = ∑ i = 1 D ν i d i + ∑ j ≤ i κ j , i b j , i , K i = ∑ j = 1 i κ j , i , K 0 = K D = 0. m=\sum_{i=1}^{D}\nu_i d_i+\sum_{j\le i}\kappa_{j,i}b_{j,i},\qquad K_i=\sum_{j=1}^{i}\kappa_{j,i},\qquad K_0=K_D=0. m = i = 1 ∑ D ν i d i + j ≤ i ∑ κ j , i b j , i , K i = j = 1 ∑ i κ j , i , K 0 = K D = 0. Then
K i = 0 ( 1 ≤ i < D ) , ξ j , i : = Ω ( b j , i − d i , m ) ≥ 0 ( 1 ≤ j ≤ i < D ) . (42) K_i=0\quad(1\le i<D),\qquad\xi_{j,i}:=\Omega(b_{j,i}-d_i,m)\ge0\quad(1\le j\le i<D). \tag*{(42)} K i = 0 ( 1 ≤ i < D ) , ξ j , i := Ω ( b j , i − d i , m ) ≥ 0 ( 1 ≤ j ≤ i < D ) . (42) The lattice label m m m (5.6) . If m m m m = ∑ i μ i d i m=\sum_i\mu_i d_i m = ∑ i μ i d i μ 1 ≥ ⋯ ≥ μ D ≥ 0 \mu_1\ge\cdots\ge\mu_D\ge0 μ 1 ≥ ⋯ ≥ μ D ≥ 0 ∑ i μ i = N \sum_i\mu_i=N ∑ i μ i = N
Proof. For D = 1 D=1 D = 1 m = N d 1 m=Nd_1 m = N d 1 D > 1 D>1 D > 1 (5.6) . At each stage use the current vertex basis to write its current label as ∑ ν i d i + ∑ κ b b \sum\nu_i d_i+\sum\kappa_b b ∑ ν i d i + ∑ κ b b b b b i i i t = [ − Ω ( b − d i , m ) ] + t=[-\Omega(b-d_i,m)]_+ t = [ − Ω ( b − d i , m ) ] + m + t ( b − d i ) m+t(b-d_i) m + t ( b − d i ) b ′ = b + d i + 1 − d i b'=b+d_{i+1}-d_i b ′ = b + d i + 1 − d i
κ b ′ = κ b + t , ν i ′ = ν i + κ b , ν i + 1 ′ = ν i + 1 − κ b ′ . (43) \kappa'_b=\kappa_b+t,\qquad\nu'_i=\nu_i+\kappa_b,\qquad\nu'_{i+1}=\nu_{i+1}-\kappa'_b. \tag*{(43)} κ b ′ = κ b + t , ν i ′ = ν i + κ b , ν i + 1 ′ = ν i + 1 − κ b ′ . (43) with all other coordinates unchanged. Thus every individual bridge coordinate, and every K i K_i K i
In every chart the current polynomial has support N d 1 + C + Nd_1+C^+ N d 1 + C + d i + 1 d_{i+1} d i + 1
B i = N − ∑ j ≤ i ( ν j + K j ) ≥ 0. (44) B_i=N-\sum_{j\le i}(\nu_j+K_j)\ge0. \tag*{(44)} B i = N − j ≤ i ∑ ( ν j + K j ) ≥ 0. (44) Equation (43) shows that B i B_i B i i i i − κ b ′ -\kappa'_b − κ b ′ K i K_i K i B i B_i B i (44) . Therefore K i ≤ 0 K_i\le0 K i ≤ 0
Since each κ b \kappa_b κ b κ b \kappa_b κ b t t t lattice vector of the tracked label is a fixed vector m ∗ m_* m ∗
At the event originally named b b b i i i L L L b − d i + L δ i b-d_i+L\delta_i b − d i + L δ i L L L m ∗ m_\ast m ∗ L L L
Ω ( δ i , m ∗ ) = 2 K i − K i − 1 − K i + 1 ≥ 0. (45) \Omega(\delta_i,m_\ast)=2K_i-K_{i-1}-K_{i+1}\ge0. \tag*{(45)} Ω ( δ i , m ∗ ) = 2 K i − K i − 1 − K i + 1 ≥ 0. (45) Indeed δ i \delta_i δ i 2 2 2 i i i − 1 -1 − 1 K 0 , … , K D K_0,\ldots,K_D K 0 , … , K D K i ≥ 0 K_i\ge0 K i ≥ 0 K i ≤ 0 K_i\le0 K i ≤ 0 K i = 0 K_i=0 K i = 0
The slopes in (45) now vanish. Consequently m ∗ m_\ast m ∗ T p ( x ) = x + [ − Ω ( p , x ) ] + p T_p(x)=x+[-\Omega(p,x)]_+p T p ( x ) = x + [ − Ω ( p , x ) ] + p x ↦ x − [ − Ω ( p , x ) ] + p x\mapsto x-[-\Omega(p,x)]_+p x ↦ x − [ − Ω ( p , x ) ] + p p p p p p p m ∗ m_\ast m ∗ (42) for the original label.
For a pure label, ξ j , i = μ i − μ i + 1 \xi_{j,i}=\mu_i-\mu_{i+1} ξ j , i = μ i − μ i + 1 (44) says μ D ≥ 0 \mu_D\ge0 μ D ≥ 0 ∑ i μ i = N \sum_i\mu_i=N ∑ i μ i = N
Example 5.4. Stationarity permits mixed labels. For D = 3 D=3 D = 3 b 2 , 2 , b 1 , 1 , b 1 , 2 b_{2,2},b_{1,1},b_{1,2} b 2 , 2 , b 1 , 1 , b 1 , 2
m = d 2 + b 1 , 2 − b 2 , 2 m=d_2+b_{1,2}-b_{2,2} m = d 2 + b 1 , 2 − b 2 , 2 satisfies K 1 = K 2 = 0 K_1=K_2=0 K 1 = K 2 = 0 ξ 1 , 1 = ξ 2 , 2 = ξ 1 , 2 = 0 \xi_{1,1}=\xi_{2,2}=\xi_{1,2}=0 ξ 1 , 1 = ξ 2 , 2 = ξ 1 , 2 = 0
m − d 1 = ( b 1 , 1 − d 1 ) + ( d 2 − b 1 , 1 ) + ( b 1 , 2 − b 2 , 2 ) ∈ C + . m-d_1=(b_{1,1}-d_1)+(d_2-b_{1,1})+(b_{1,2}-b_{2,2})\in C^+. m − d 1 = ( b 1 , 1 − d 1 ) + ( d 2 − b 1 , 1 ) + ( b 1 , 2 − b 2 , 2 ) ∈ C + . It is therefore a stationary candidate of weight 1 1 1 b 2 , 2 b_{2,2} b 2 , 2 U U U
Lemma 5.5 (Pure coefficient extraction). Let P P P N N N m = ∑ i μ i d i m=\sum_i\mu_i d_i m = ∑ i μ i d i μ 1 ≥ ⋯ ≥ μ D ≥ 0 \mu_1\ge\cdots\ge\mu_D\ge0 μ 1 ≥ ⋯ ≥ μ D ≥ 0 ∑ i μ i = N \sum_i\mu_i=N ∑ i μ i = N z 1 , … , z D z_1,\ldots,z_D z 1 , … , z D
A m ( P ( Y ) ) = [ z 1 μ 1 ⋯ z D μ D ] P ( z 1 , … , z D ) . A_m(P(Y))=[z_1^{\mu_1}\cdots z_D^{\mu_D}]P(z_1,\ldots,z_D). A m ( P ( Y )) = [ z 1 μ 1 ⋯ z D μ D ] P ( z 1 , … , z D ) . Proof. We choose a single sufficiently large integer L L L m − N d 1 ∈ C + m-Nd_1\in C^+ m − N d 1 ∈ C +
R m = { r ∈ C + : 0 < r ≤ m − N d 1 } . (46) R_m=\{r\in C^+:0<r\le m-Nd_1\}. \tag*{(46)} R m = { r ∈ C + : 0 < r ≤ m − N d 1 } . (46) where r ≤ s r\le s r ≤ s s − r ∈ C + s-r\in C^+ s − r ∈ C + C C C L L L
Define a covector by
Q L ( d i ) = D − i , Q L ( b − d i ) = L − θ b for an original bridge on level i . Q_L(d_i)=D-i,\qquad Q_L(b-d_i)=L-\theta_b\quad\text{for an original bridge on level }i. Q L ( d i ) = D − i , Q L ( b − d i ) = L − θ b for an original bridge on level i . For the moved bridge b ( L ) = b + L δ i b^{(L)}=b+L\delta_i b ( L ) = b + L δ i Q L ( b ( L ) ) = D − i − θ b Q_L(b^{(L)})=D-i-\theta_b Q L ( b ( L ) ) = D − i − θ b Q L Q_L Q L C L C_L C L L L L p b ( ℓ ) = b − d i + ℓ δ i p_b^{(\ell)}=b-d_i+\ell\delta_i p b ( ℓ ) = b − d i + ℓ δ i 0 ≤ ℓ < L 0\le\ell<L 0 ≤ ℓ < L
Q L ( p b ( ℓ ) ) = L − θ b − ℓ > 0 , Ω ( p b ( ℓ ) , m ) = μ i − μ i + 1 ≥ 0. Q_L(p_b^{(\ell)})=L-\theta_b-\ell>0,\qquad\Omega(p_b^{(\ell)},m)=\mu_i-\mu_{i+1}\ge0. Q L ( p b ( ℓ ) ) = L − θ b − ℓ > 0 , Ω ( p b ( ℓ ) , m ) = μ i − μ i + 1 ≥ 0. Hence the entire ray Q L + s V ( m ) Q_L+sV(m) Q L + s V ( m ) s ≥ 0 s\ge0 s ≥ 0 Q L Q_L Q L L L L X m X_m X m R m \mathcal{R}_m R m N d 1 N d_1 N d 1 C L + C_L^+ C L +
For r ∈ R m r \in\mathcal{R}_m r ∈ R m ν i ( r ) \nu_i(r) ν i ( r ) κ b ( r ) \kappa_b(r) κ b ( r )
P i ( r ) = ∑ j ≤ i ( ν j ( r ) + K j ( r ) ) . P_i(r) = \sum_{j \le i} \left(\nu_j(r) + K_j(r)\right). P i ( r ) = j ≤ i ∑ ( ν j ( r ) + K j ( r ) ) . As a fixed vector reexpressed after L L L r r r
ν i ( L ) ( r ) = ν i ( r ) + L ( K i ( r ) − K i − 1 ( r ) ) . \nu_i^{(L)}(r) = \nu_i(r) + L\left(K_i(r) - K_{i-1}(r)\right). ν i ( L ) ( r ) = ν i ( r ) + L ( K i ( r ) − K i − 1 ( r ) ) . Thus its moved prefix is P i ( r ) + L K i ( r ) P_i(r) + L K_i(r) P i ( r ) + L K i ( r ) C L + C_L^+ C L + P i ( r ) + L K i ( r ) ≤ 0 P_i(r) + L K_i(r) \le0 P i ( r ) + L K i ( r ) ≤ 0 L L L − P i ( r ) -P_i(r) − P i ( r ) r ∈ R m r \in\mathcal{R}_m r ∈ R m 1 ≤ i < D 1 \le i < D 1 ≤ i < D K i ( r ) K_i(r) K i ( r ) K i ( r ) ≤ 0 K_i(r) \le0 K i ( r ) ≤ 0 i i i
There is also an L L L q 0 ( r ) q_0(r) q 0 ( r )
Q L ( r ) = L ∑ i K i ( r ) + q 0 ( r ) . Q_L(r) = L \sum_i K_i(r) + q_0(r). Q L ( r ) = L i ∑ K i ( r ) + q 0 ( r ) . Increasing the same L L L q 0 ( r ) q_0(r) q 0 ( r ) Q L ( r ) < 0 Q_L(r) < 0 Q L ( r ) < 0 K i ( r ) < 0 K_i(r) < 0 K i ( r ) < 0
Ω ( r , m ) = ∑ i = 1 D − 1 K i ( r ) ( μ i − μ i + 1 ) ≤ 0. (47) \Omega(r,m) = \sum_{i=1}^{D-1} K_i(r)(\mu_i-\mu_{i+1}) \le0. \tag*{(47)} Ω ( r , m ) = i = 1 ∑ D − 1 K i ( r ) ( μ i − μ i + 1 ) ≤ 0. (47) If some K i ( r ) < 0 K_i(r) < 0 K i ( r ) < 0 ( Q L + s V ( m ) ) ( r ) = Q L ( r ) + s Ω ( r , m ) < 0 (Q_L+sV(m))(r) = Q_L(r) + s\Omega(r,m) < 0 ( Q L + s V ( m )) ( r ) = Q L ( r ) + s Ω ( r , m ) < 0 s ≥ 0 s \ge0 s ≥ 0 K i ( r ) K_i(r) K i ( r ) X m − a r X_{m-ar} X m − a r Ω ( r , m − a r ) = 0 \Omega(r,m-ar)=0 Ω ( r , m − a r ) = 0 X m X_m X m
All these comparisons require only finitely many orders for the fixed target and the chosen L L L Q L Q_L Q L s s s Q L + s V ( m ) Q_L+sV(m) Q L + s V ( m ) Q L Q_L Q L
Finally, in the moved vertex basis the target m m m v v v Q L Q_L Q L (5.11) .
The linear section and its gap recurrence
Lemma 5.6. In the all-negative chamber of the triangular chart,
U = Θ d 1 . U = \Theta_{d_1}. U = Θ d 1 . Proof. Assume D > 1 D > 1 D > 1 D = 1 D = 1 D = 1 m m m A m ( U ) ≠ 0 A_m(U) \ne0 A m ( U ) = 0 m − d 1 m-d_1 m − d 1 K i K_i K i ξ j , i \xi_{j,i} ξ j , i i i i u j , i u_{j,i} u j , i b j , i b_{j,i} b j , i a i = u 1 , i a_i=u_{1,i} a i = u 1 , i a 0 = 0 a_0=0 a 0 = 0 K i = 0 K_i=0 K i = 0 b i , i − d i b_{i,i}-d_i b i , i − d i a i a_i a i Figure 1 illustrates these coefficients. All the u j , i u_{j,i} u j , i a i a_i a i
Figure 1. The gap coefficients for D = 3 D=3 D = 3 b 2 , 2 , b 1 , 1 , b 1 , 2 b_{2,2},b_{1,1},b_{1,2} b 2 , 2 , b 1 , 1 , b 1 , 2
We spell out the pairing calculation underlying the recurrence. For p = b j , i − d i p=b_{j,i}-d_i p = b j , i − d i b j , i b_{j,i} b j , i b j , i b_{j,i} b j , i − 1 -1 − 1 d i d_i d i − 1 -1 − 1 d i + 1 d_{i+1} d i + 1 b j , i b_{j,i} b j , i i − 1 i-1 i − 1 b j , i b_{j,i} b j , i i + 1 i+1 i + 1 d 1 d_1 d 1 1 i = 1 \mathbf{1}_{i=1} 1 i = 1
ξ j , i = 1 i = 1 − u j , i − { u j + 1 , i , j < i , a i , j = i , + { u j , i − 1 , j < i , a j − 1 , j = i , + u j + 1 , i + 1 . (48) \xi_{j,i}=\mathbf{1}_{i=1}-u_{j,i}-
\begin{cases}
u_{j+1,i}, & j<i,\\
a_i, & j=i,
\end{cases}
+
\begin{cases}
u_{j,i-1}, & j<i,\\
a_{j-1}, & j=i,
\end{cases}
+u_{j+1,i+1}. \tag*{(48)} ξ j , i = 1 i = 1 − u j , i − { u j + 1 , i , a i , j < i , j = i , + { u j , i − 1 , a j − 1 , j < i , j = i , + u j + 1 , i + 1 . (48) Indeed the upper neighboring gap follows the event in row j + 1 j+1 j + 1 j j j j < i j<i j < i j = i j=i j = i
Set
T j , i = u j , i − u j + 1 , i + 1 , 1 ≤ j ≤ i ≤ n 0 , T_{j,i}=u_{j,i}-u_{j+1,i+1}, \qquad1\le j\le i\le n_0, T j , i = u j , i − u j + 1 , i + 1 , 1 ≤ j ≤ i ≤ n 0 , again using zero for nonexistent terms. Equation (48) is equivalently
T j , j = 1 j = 1 + a j − 1 − a j − ξ j , j , T_{j,j}=\mathbf{1}_{j=1}+a_{j-1}-a_j-\xi_{j,j}, T j , j = 1 j = 1 + a j − 1 − a j − ξ j , j , T j , i = T j , i − 1 − ξ j , i ( i > j ) . (49) T_{j,i}=T_{j,i-1}-\xi_{j,i} \qquad(i>j). \tag*{(49)} T j , i = T j , i − 1 − ξ j , i ( i > j ) . (49) Each row of T T T T j , n 0 = u j , n 0 ≥ 0 T_{j,n_0}=u_{j,n_0}\ge0 T j , n 0 = u j , n 0 ≥ 0 T j , i ≥ 0 T_{j,i}\ge0 T j , i ≥ 0 a 1 ≤ 1 a_1\le1 a 1 ≤ 1 a j ≤ a j − 1 a_j\le a_{j-1} a j ≤ a j − 1 j > 1 j>1 j > 1
a 1 , … , a n 0 = 1 , … , 1 ⏟ e , 0 , … , 0 a_1,\ldots,a_{n_0}=\underbrace{1,\ldots,1}_{e},0,\ldots,0 a 1 , … , a n 0 = e 1 , … , 1 , 0 , … , 0 for some 0 ≤ e ≤ n 0 0\le e\le n_0 0 ≤ e ≤ n 0 e = n 0 e=n_0 e = n 0 (49) would be zero, giving T = 0 T=0 T = 0 u = 0 u=0 u = 0 a 1 = 1 a_1=1 a 1 = 1
All rows of T T T e + 1 e+1 e + 1 e + 1 e+1 e + 1 e + 1 , … , t e+1,\ldots,t e + 1 , … , t t = e t=e t = e T T T
u j , i = ∑ a ≥ 0 T j + a , i + a . u_{j,i}=\sum_{a\geq0}T_{j+a,i+a}. u j , i = a ≥ 0 ∑ T j + a , i + a . In particular u 1 , i = a i u_{1,i}=a_i u 1 , i = a i 1 1 1 1 ≤ i ≤ t − e 1\leq i\leq t-e 1 ≤ i ≤ t − e e e e t = 2 e t=2e t = 2 e i ≤ 2 e i\leq2e i ≤ 2 e (49) , a positive ξ j , i \xi_{j,i} ξ j , i 2 e + 1 2e+1 2 e + 1 ξ j , i \xi_{j,i} ξ j , i e = 0 e=0 e = 0 ξ 1 , 1 \xi_{1,1} ξ 1 , 1
Every positively used forward root therefore pairs trivially with m m m ξ \xi ξ ξ i , i \xi_{i,i} ξ i , i
Ω ( d i + 1 − b 1 , i , m ) = Ω ( δ i , m ) − ξ 1 , i = 0 , \Omega(d_{i+1}-b_{1,i},m)=\Omega(\delta_i,m)-\xi_{1,i}=0, Ω ( d i + 1 − b 1 , i , m ) = Ω ( δ i , m ) − ξ 1 , i = 0 , since K = 0 K=0 K = 0 Ω ( δ i , m ) = 0 \Omega(\delta_i,m)=0 Ω ( δ i , m ) = 0 (45) . This verifies both end gaps as well as the interior ones.
A wall increment capable of changing [ X m ] [X_m] [ X m ] 0 < r ≤ m − d 1 0<r\leq m-d_1 0 < r ≤ m − d 1 C C C r r r Ω ( r , m ) = 0 \Omega(r,m)=0 Ω ( r , m ) = 0 m m m A m ( U ) = [ X m ] U A_m(U)=[X_m]U A m ( U ) = [ X m ] U d 1 d_1 d 1 U U U A d 1 ( U ) = 1 A_{d_1}(U)=1 A d 1 ( U ) = 1 U = Θ d 1 U=\Theta_{d_1} U = Θ d 1
Positive domination and the monomial identity
Lemma 5.7 (Vertex support before subtraction). For every partition μ ⊢ N \mu\vdash N μ ⊢ N with at most D D D parts, padded by zeroes, put x μ = ∑ i μ i d i x_\mu=\sum_i\mu_i d_i x μ = ∑ i μ i d i In the all-negative chamber, Θ x μ \Theta_{x_\mu} Θ x μ has nonnegative vertex exponents and coefficients in N [ v , v − 1 ] \mathbb{N}[v,v^{-1}] N [ v , v − 1 ] and is a finite Laurent polynomial. More precisely, coefficientwise in both vertex exponents and v v v
N ! ∏ i μ i ! Θ x μ ≤ U N . (50) \frac{N!}{\prod_i\mu_i!}\Theta_{x_\mu}\leq U^N. \tag*{(50)} ∏ i μ i ! N ! Θ x μ ≤ U N . (50) Proof. Lemma 5.6 and Corollary 4.5 give a nonnegative incoming expansion of U N U^N U N ( z 1 + ⋯ + z D ) N (z_1+\cdots+z_D)^N ( z 1 + ⋯ + z D ) N
A x μ ( U N ) = N ! ∏ i μ i ! > 0. A_{x_\mu}(U^N)=\frac{N!}{\prod_i\mu_i!}>0. A x μ ( U N ) = ∏ i μ i ! N ! > 0. Every section in this expansion has nonnegative coefficients in every chamber by Theorem 4.4. Retaining the one displayed summand therefore gives (50) . The right side is a finite Laurent polynomial with nonnegative vertex exponents and nonnegative integral coefficients in v v v N = 0 N=0 N = 0
Theorem 5.8 (Monomial sections). For every partition λ \lambda λ D D D D D D
m λ ( Y ) = Θ ∑ i = 1 D λ i d i . (51) m_\lambda(Y)=\Theta_{\sum_{i=1}^{D}\lambda_i d_i}. \tag*{(51)} m λ ( Y ) = Θ ∑ i = 1 D λ i d i . (51) In particular,
E k = Θ d 1 + ⋯ + d k ( 0 ≤ k ≤ D ) . E_k=\Theta_{d_1+\cdots+d_k}\qquad(0\leq k\leq D). E k = Θ d 1 + ⋯ + d k ( 0 ≤ k ≤ D ) . Proof. For D = 1 D=1 D = 1 N = ∣ λ ∣ N=|\lambda| N = ∣ λ ∣ x λ = ∑ i λ i d i x_\lambda=\sum_i\lambda_i d_i x λ = ∑ i λ i d i m λ ( Y ) m_\lambda(Y) m λ ( Y ) Θ x λ \Theta_{x_\lambda} Θ x λ
By Lemmas 5.3 and 5.5, the pure incoming coefficients of m λ ( Y ) m_\lambda(Y) m λ ( Y ) x λ x_\lambda x λ m λ m_\lambda m λ λ \lambda λ
F = m λ ( Y ) − Θ x λ . F=m_\lambda(Y)-\Theta_{x_\lambda}. F = m λ ( Y ) − Θ x λ . Its ordinary support still has nonnegative vertex coordinates, all its pure incoming coefficients vanish, and both its ordinary and incoming support lie in N d 1 + C + N d_1+C^+ N d 1 + C +
If an incoming coefficient remains nonzero, its label m m m K i ( m ) = 0 K_i(m)=0 K i ( m ) = 0 Θ x λ \Theta_{x_\lambda} Θ x λ N d 1 + C + N d_1+C^+ N d 1 + C + N \mathbb{N} N [ X m ] F = A m ( F ) ≠ 0 [X_m]F=A_m(F)\ne0 [ X m ] F = A m ( F ) = 0 m m m (51) . Finally m ( 1 k ) = e k m_{(1^k)}=e_k m ( 1 k ) = e k (5.21) . □
Corollary 5.9 (Elementary positivity). Let G G G n n n M = ∣ E ( G ) ∣ M=|E(G)| M = ∣ E ( G ) ∣
χ G ( X ; q ) = ∑ λ ⊢ n c λ ( q ) e λ ( X ) , \chi_G(X;q)=\sum_{\lambda\vdash n}c_\lambda(q)e_\lambda(X), χ G ( X ; q ) = λ ⊢ n ∑ c λ ( q ) e λ ( X ) , every c λ ( q ) c_\lambda(q) c λ ( q ) N [ q ] \mathbb{N}[q] N [ q ] M M M D ≥ n D\geq n D ≥ n u u u x λ = ∑ i λ i d i x_\lambda=\sum_i\lambda_i d_i x λ = ∑ i λ i d i λ \lambda λ
[ X u ] Θ x λ H − = v − M c λ ( v 2 ) ∈ ∑ d = 0 M N v 2 d − M , (52) [X_u]\Theta_{x_\lambda}^{H_-}=v^{-M}c_\lambda(v^2)\in\sum_{d=0}^{M}\mathbb{N}v^{2d-M}, \tag*{(52)} [ X u ] Θ x λ H − = v − M c λ ( v 2 ) ∈ d = 0 ∑ M N v 2 d − M , (52) where H − H_- H −
Proof. Choose the embedding of Lemma 5.1, taking D ≥ n D\geq n D ≥ n
c λ ( v 2 ) = v M [ X u ] m λ ( Y ) = v M [ X u ] Θ x λ H − . c_\lambda(v^2)=v^M[X_u]m_\lambda(Y)=v^M[X_u]\Theta_{x_\lambda}^{H_-}. c λ ( v 2 ) = v M [ X u ] m λ ( Y ) = v M [ X u ] Θ x λ H − . The last expression has nonnegative integral coefficients at every power of v v v q q q M M M n n n n n n c λ ( q ) ∈ Z [ q ] c_{\lambda}(q) \in\mathbb{Z}[q] c λ ( q ) ∈ Z [ q ] M M M (52) . □ \square □
This completes the coefficientwise positivity assertion. The remaining construction assigns a partition to each individual graph-nondescent permutation and proves the weight-preserving formula in Theorem 1.1. The finite coefficient bounds in (52) will also bound the histories used by that construction.
A finite witness on individual words
Corollary 5.9 proves positivity of the elementary coefficients. We now construct the partition assigned to each individual word. The construction matches ordered packets of vertices with finite wall histories and anchor words; the anchor multiplicities specify the partition. Its local matchings use coefficients of elementary sections and individual wall operators, without taking the final elementary coefficient list as input.
Fix a triangular embedding with D ≥ max { 1 , n } D \ge\max\{1,n\} D ≥ max { 1 , n } N = n N=n N = n u u u H − H_{-} H − M = ∣ E ( G ) ∣ M = \lvert E(G)\rvert M = ∣ E ( G )∣
R = u − N d 1 ∈ C + , B = { y : N d 1 ≤ y ≤ u } . R = u - N d_{1} \in C^{+}, \qquad B = \{y : N d_{1} \le y \le u\}. R = u − N d 1 ∈ C + , B = { y : N d 1 ≤ y ≤ u } . The order in this display is the free-cone order. If R = ∑ c ∈ C R c c R = \sum_{c \in C} R_{c}c R = ∑ c ∈ C R c c h ( R ) = ∑ c R c h(R) = \sum_{c} R_{c} h ( R ) = ∑ c R c B B B ∏ c ( R c + 1 ) \prod_{c}(R_{c} + 1) ∏ c ( R c + 1 ) 0 < r ≤ R 0 < r \le R 0 < r ≤ R
Decorated coefficients and their finite orders
For 1 ≤ k ≤ N 1 \le k \le N 1 ≤ k ≤ N
E k = e k ( Y ) = Θ d 1 + ⋯ + d k , E k H = ∑ a , e c k H ( a , e ) v e X a . E_{k} = e_{k}(Y) = \Theta_{d_{1}+\cdots+d_{k}}, \qquad E_{k}^{H} = \sum_{a,e} c_{k}^{H}(a,e)v^{e}X_{a}. E k = e k ( Y ) = Θ d 1 + ⋯ + d k , E k H = a , e ∑ c k H ( a , e ) v e X a . The identity is Theorem 5.8. The coefficients c k H ( a , e ) c_{k}^{H}(a,e) c k H ( a , e ) k k k H H H ( a , e , t ) (a,e,t) ( a , e , t ) 1 ≤ t ≤ c k H ( a , e ) 1 \le t \le c_{k}^{H}(a,e) 1 ≤ t ≤ c k H ( a , e ) e e e k = ( k 1 , … , k b ) k = (k_{1},\ldots,k_{b}) k = ( k 1 , … , k b ) N N N
a = ∑ i = 1 b a i , E = ∑ i = 1 b e i + ∑ i < j Ω ( a i , a j ) . (53) a = \sum_{i=1}^{b} a_{i}, \qquad E = \sum_{i=1}^{b} e_{i} + \sum_{i<j} \Omega(a_{i},a_{j}). \tag*{(53)} a = i = 1 ∑ b a i , E = i = 1 ∑ b e i + i < j ∑ Ω ( a i , a j ) . (53) Thus these states count the coefficients of P k = E k 1 ⋯ E k b P_{k} = E_{k_{1}}\cdots E_{k_{b}} P k = E k 1 ⋯ E k b H − H_{-} H − k k k
If a wall operator W W W X a X_{a} X a a a a a + j p a + jp a + j p ( j , e , t ) (j,e,t) ( j , e , t )
j ≥ 0 , 1 ≤ t ≤ [ v e X a + j p ] W ( X a ) . (54) j \ge0, \qquad1 \le t \le\left[v^{e}X_{a+jp}\right]W(X_{a}). \tag*{(54)} j ≥ 0 , 1 ≤ t ≤ [ v e X a + j p ] W ( X a ) . (54) Here p p p (54) are in centered torus notation and already include the shift arising from multiplication by X a X_{a} X a ( 0 , 0 , 1 ) (0,0,1) ( 0 , 0 , 1 )
Lemma 6.1 (Effective coefficient slices). At fixed total exponent in B B B h ( R ) h(R) h ( R )
Proof. The support of E k E_k E k k d 1 + C + kd_1+C^+ k d 1 + C + u u u R R R
At each fixed exponent the coefficient of a section or wall jump lies in Z ( ( v − 1 ) ) \mathbb{Z}((v^{-1})) Z (( v − 1 ))
E = κ + e 1 + ⋯ + e s , E=\kappa+e_1+\cdots+e_s, E = κ + e 1 + ⋯ + e s , where κ \kappa κ i i i U i U_i U i
E − κ − ∑ j ≠ i U j ≤ e i ≤ U i . (55) E-\kappa-\sum_{j\ne i}U_j\le e_i\le U_i. \tag*{(55)} E − κ − j = i ∑ U j ≤ e i ≤ U i . (55) Thus each energy and each decoration ranges over a finite set. For bounded sequences there are again only finitely many exponent types, so the same argument applies to all their pieces at once.
These are effective bounds. The initial units have the rational coefficients
[ X j p ] D p = v − j 2 ∏ i = 1 j ( 1 − v − 2 i ) . [X_{jp}]_{D_p}=\frac{v^{-j^2}}{\prod_{i=1}^{j}(1-v^{-2i})}. [ X j p ] D p = ∏ i = 1 j ( 1 − v − 2 i ) v − j 2 . The triangular factorization and incoming equations of Section 4 determine every wall coefficient to the required root order by finite rational arithmetic in v v v E k H E_k^H E k H v − 1 = 0 v^{-1}=0 v − 1 = 0 (55) , enumerate all choices in them, and compute their multiplicities. No factorization into positive units needs to be found in order to perform these coefficient calculations; positivity justifies interpreting the computed integers as multiplicities.
We specify the finite choices used by these definitions. Order lattice coordinates in the basis d 1 d_1 d 1 C C C a a a b ( a ) b(a) b ( a ) b ( 0 ) = 0 b(0)=0 b ( 0 ) = 0 1 ∣ b ( a ) ∣ 0 b ( a ) 1|b(a)|0b(a) 1∣ b ( a ) ∣0 b ( a ) D ≥ max { 1 , n } D\ge\max\{1,n\} D ≥ max { 1 , n } (5.1) , and n n n G G G D = 1 D=1 D = 1
All later generic rational choices mean the first code satisfying the listed open inequalities and avoidance conditions. These are decidable finite systems of rational linear conditions. In particular, for a line h + t V ( y ) h+tV(y) h + t V ( y ) h ( r ) Ω ( s , y ) − h ( s ) Ω ( r , y ) = 0 h(r)\Omega(s,y)-h(s)\Omega(r,y)=0 h ( r ) Ω ( s , y ) − h ( s ) Ω ( r , y ) = 0 r r r Ω ( r , y ) = 0 \Omega(r,y)=0 Ω ( r , y ) = 0
The local packet switch
Let W : I ⟶ I I W:I\longrightarrow II W : I ⟶ I I N p \mathbb{N}p N p Ad ( g p ) ε \operatorname{Ad}(g_p)^\varepsilon Ad ( g p ) ε ε = 1 \varepsilon=1 ε = 1 ε = − 1 \varepsilon=-1 ε = − 1 y y y
ε Ω ( p , y ) ≥ 0. \varepsilon\Omega(p,y)\ge0. ε Ω ( p , y ) ≥ 0. This is exactly the positive bend direction of Proposition 4.2, with the identity direction included as in Lemma 4.1.
The total pairing in Equation (6.4) can be nonnegative even when an individual packet has negative pairing. The switch must therefore use both directions of single-packet transport. Its invariant is a tuple of packet states retained on the side from which their jumps have nonnegative coefficients.
Proposition 6.2 (Packet switch). There is a computable energy-preserving bijection
{ product states of exponent y in I I } ⟷ { product states of exponent z in I , together with a decorated jump of W from z to y } . (56) \{ \textit{product states of exponent }y\text{ in }II\}
\longleftrightarrow
\left\{
\begin{array}{c}
\textit{product states of exponent }z\text{ in }I,\text{ together with}\\
\textit{a decorated jump of }W\text{ from }z\text{ to }y
\end{array}
\right\}. \tag*{(56)} { product states of exponent y in I I } ⟷ { product states of exponent z in I , together with a decorated jump of W from z to y } . (56) On the right the energy is the state energy plus the jump energy. If Ω ( p , y ) = 0 \Omega(p,y)=0 Ω ( p , y ) = 0
Proof. For a packet with exponent a a a ε Ω ( p , a ) ≥ 0 \varepsilon\Omega(p,a)\ge0 ε Ω ( p , a ) ≥ 0 p p p (56) .
For a positive packet the section identity E k I I = W ( E k I ) E_k^{II}=W(E_k^I) E k I I = W ( E k I ) I I II I I I I I W W W E k I = W − 1 ( E k I I ) E_k^I=W^{-1}(E_k^{II}) E k I = W − 1 ( E k I I ) I I I I I II I I W − 1 W^{-1} W − 1
Fix the retained state of each packet: in chamber I I I I I II I I x i x_i x i
Table 1.
Via the single-packet bijections, a decorated term of L i L_i L i I I II I I R i R_i R i I I I L i = W ( R i ) L_i=W(R_i) L i = W ( R i )
L 1 ⋯ L b = W ( R 1 ⋯ R b ) . L_1\cdots L_b=W(R_1\cdots R_b). L 1 ⋯ L b = W ( R 1 ⋯ R b ) . The left side opens only positive packets. The right side opens only negative packets and then applies one total jump. For a term at X y X_y X y y y y p p p Ω ( p , y ) \Omega(p,y) Ω ( p , y ) (6.4) makes that jump positive.
We spell out the energy in Equation (6.6) . If the individual increments in a term are j i p j_i p j i p
∑ i < j Ω ( x i + j i p , x j + j j p ) = ∑ i < j Ω ( x i , x j ) + ∑ i < j ( j i Ω ( p , x j ) + j j Ω ( x i , p ) ) . (57) \sum_{i<j}\Omega(x_i+j_i p,x_j+j_j p)=\sum_{i<j}\Omega(x_i,x_j)+\sum_{i<j}\left(j_i\Omega(p,x_j)+j_j\Omega(x_i,p)\right). \tag*{(57)} i < j ∑ Ω ( x i + j i p , x j + j j p ) = i < j ∑ Ω ( x i , x j ) + i < j ∑ ( j i Ω ( p , x j ) + j j Ω ( x i , p ) ) . (57) There is no quadratic term because Ω ( p , p ) = 0 \Omega(p,p)=0 Ω ( p , p ) = 0 (6.6) , add the energy of the final total jump to this expression and to the individual inverse-jump energies. On the left, add the individual forward-jump energies. Taking a fixed v v v X y X_y X y
The bijection is now explicit in either direction. From the left of Equation eq:5 , open its positive packets by their single-packet bijections, keep its negative packets as underlying states, apply the jump-tuple rank bijection, and close the negative packets into states in I I I I I II I I Ω ( p , y ) = 0 \Omega(p,y)=0 Ω ( p , y ) = 0 y + Z p y+\mathbb{Z}p y + Z p g p g_p g p
Example 6.3 (Zero total jump with changing packets). In the monomial identity of the switch, take W = Ad ( D p ) W=\operatorname{Ad}(D_p) W = Ad ( D p ) Ω ( p , x 1 ) = 1 \Omega(p,x_1)=1 Ω ( p , x 1 ) = 1 Ω ( p , x 2 ) = − 1 \Omega(p,x_2)=-1 Ω ( p , x 2 ) = − 1 (6.6) become
( X x 1 + X x 1 + p ) X x 2 = X x 1 ( X x 2 + X x 2 + p ) . (X_{x_1}+X_{x_1+p})X_{x_2}=X_{x_1}(X_{x_2}+X_{x_2+p}). ( X x 1 + X x 1 + p ) X x 2 = X x 1 ( X x 2 + X x 2 + p ) . The total pairing is zero, so W W W x 1 + x 2 + p x_1+x_2+p x 1 + x 2 + p
Ω ( x 1 + p , x 2 ) = Ω ( x 1 , x 2 + p ) = Ω ( x 1 , x 2 ) − 1. \Omega(x_1+p,x_2)=\Omega(x_1,x_2+p)=\Omega(x_1,x_2)-1. Ω ( x 1 + p , x 2 ) = Ω ( x 1 , x 2 + p ) = Ω ( x 1 , x 2 ) − 1. Thus the local matching transfers the increment from the positive packet to the negative packet while its recorded total jump is zero. The example concerns the monomial matching with retained exponents fixed; its point is that zero total jump need not fix each packet.
Common histories and terminal anchor states
Before choosing a composition, fix a generic rational representative h H , y ∈ H h_{H,y}\in H h H , y ∈ H H H H y ∈ B y\in B y ∈ B h H , y + t V ( y ) h_{H,y}+tV(y) h H , y + t V ( y ) t ≥ 0 t\ge0 t ≥ 0 t t t V ( y ) V(y) V ( y ) V ( y ) = 0 V(y)=0 V ( y ) = 0 t t t H H H (6.4) . The choices depend on ( H , y ) (H,y) ( H , y )
For a section P P P N d 1 Nd_1 N d 1
[ X y ] P H = A y ( P ) + ∑ W : I → I I ∑ N d 1 ≤ z < y [ X y ] W ( X z ) [ X z ] P I . (58) [X_y]P^{H}=A_y(P)+\sum_{W:I\to II}\sum_{Nd_1\leq z<y}[X_y]W(X_z)[X_z]P^{I}. \tag*{(58)} [ X y ] P H = A y ( P ) + W : I → I I ∑ N d 1 ≤ z < y ∑ [ X y ] W ( X z ) [ X z ] P I . (58) The outer sum follows the selected line, oriented toward H H H eq:6.8 is a sum of increments rather than a product of separate wall choices.
Define a total history from ( H − , u ) (H_{-},u) ( H − , u ) ( H , y ) (H,y) ( H , y ) y y y W : I → I I W:I\to II W : I → I I eq:6.8 , an exponent z < y z<y z < y z z z y y y ( I , z ) (I,z) ( I , z ) T x T_x T x x x x T x ( E ) T_x(E) T x ( E ) E E E
Every nonzero jump lowers the cone height by at least one, so a history has at most h ( R ) h(R) h ( R ) T x ( E ) T_x(E) T x ( E ) eq:6.8 to Θ x \Theta_x Θ x A y ( Θ x ) = 1 y = x A_y(\Theta_x)=\mathbf{1}_{y=x} A y ( Θ x ) = 1 y = x
∑ t ∈ T x v E ( t ) = [ X u ] Θ x H − . \sum_{t\in T_x} v^{E(t)}=[X_u]\Theta_x^{H_-}. t ∈ T x ∑ v E ( t ) = [ X u ] Θ x H − . This is a coefficientwise identity in the Laurent completion. The definition of T x T_x T x
The packet realization of this recursion is also reversible. Start with a product state of exponent y y y H H H ( I , z ) (I,z) ( I , z ) z → y z\to y z → y H H H T x T_x T x
Lemma 6.4 (Return to the anchors). A nonempty terminal product state has label x = x μ = ∑ i = 1 D μ i d i x=x_\mu=\sum_{i=1}^{D}\mu_i d_i x = x μ = ∑ i = 1 D μ i d i μ ⊢ N \mu\vdash N μ ⊢ N k 1 , … , k b k_1,\ldots,k_b k 1 , … , k b x μ x_\mu x μ
Proof. In ordinary commuting variables z 1 , … , z D z_1,\ldots,z_D z 1 , … , z D
∏ j = 1 b e k j ( z ) = ∑ μ ⊢ N a k , μ m μ ( z ) . (59) \prod_{j=1}^{b}e_{k_j}(z)=\sum_{\mu\vdash N}a_{k,\mu}m_\mu(z). \tag*{(59)} j = 1 ∏ b e k j ( z ) = μ ⊢ N ∑ a k , μ m μ ( z ) . (59) The nonnegative integer a k , μ a_{k,\mu} a k , μ [ D ] [D] [ D ] i i i μ i \mu_i μ i P k P_k P k x μ x_\mu x μ a k , μ a_{k,\mu} a k , μ
The coefficient at the same pure label in H − H_- H − a k , μ a_{k,\mu} a k , μ h − h_- h − V ( x ) V(x) V ( x ) h − + t V ( x ) h_- + tV(x) h − + t V ( x ) t t t Ω ( p , x ) = 0 \Omega(p,x) = 0 Ω ( p , x ) = 0 h − + t V ( x ) h_- + tV(x) h − + t V ( x ) t = 0 t = 0 t = 0 p p p Ω ( p , x ) > 0 \Omega(p,x) > 0 Ω ( p , x ) > 0 X x X_x X x a k , μ a_{k,\mu} a k , μ
It follows that, in (56) for these product states at x x x H − H_- H −
Proposition 6.5 (Formal degree bounds). For every partition μ ⊢ N \mu\vdash N μ ⊢ N T x μ T_{x\mu} T xμ
− M ≤ E ( t ) ≤ M , E ( t ) ≡ M ( m o d 2 ) . (60) -M \le E(t) \le M,\qquad E(t) \equiv M \pmod{2}. \tag*{(60)} − M ≤ E ( t ) ≤ M , E ( t ) ≡ M ( mod 2 ) . (60) Consequently T x μ T_{x\mu} T xμ v M [ X u ] Θ x μ H − v^M[X_u]\Theta^{H_-}_{x\mu} v M [ X u ] Θ xμ H − N [ q ] \mathbb{N}[q] N [ q ] q = v 2 q = v^2 q = v 2 M M M
Proof. (6.9) identifies the history enumerator with [ X u ] Θ x μ H − [X_u]\Theta^{H_-}_{x\mu} [ X u ] Θ xμ H − (52) , this coefficient is v − M c μ ( v 2 ) v^{-M}c_\mu(v^2) v − M c μ ( v 2 ) c μ ( q ) ∈ N [ q ] c_\mu(q) \in\mathbb{N}[q] c μ ( q ) ∈ N [ q ] M M M v v v − M , − M + 2 , … , M -M,-M+2,\ldots,M − M , − M + 2 , … , M T x μ T_{x\mu} T xμ v M v^M v M q ( E ( t ) + M ) / 2 q^{(E(t)+M)/2} q ( E ( t ) + M ) /2
Required masks and exact masks
For a permutation word w = w 1 ⋯ w N w = w_1 \cdots w_N w = w 1 ⋯ w N
P G ( w ) = { j : w j < w j + 1 , { w j , w j + 1 } ∉ E ( G ) } . \mathcal{P}_G(w) = \{j : w_j < w_{j+1},\ \{w_j,w_{j+1}\} \notin E(G)\}. P G ( w ) = { j : w j < w j + 1 , { w j , w j + 1 } ∈ / E ( G )} . For a word s = s 1 ⋯ s N s = s_1 \cdots s_N s = s 1 ⋯ s N [ D ] [D] [ D ] Q ( s ) = { j : s j < s j + 1 } Q(s) = \{j : s_j < s_{j+1}\} Q ( s ) = { j : s j < s j + 1 } J ⊆ [ N − 1 ] J \subseteq[N-1] J ⊆ [ N − 1 ] required mask means J ⊆ P G ( w ) J \subseteq\mathcal{P}_G(w) J ⊆ P G ( w ) J ⊆ Q ( s ) J \subseteq Q(s) J ⊆ Q ( s ) exact mask means equality. These are different conditions.
Place packet boundaries exactly at the complement of J J J k ( J ) k(J) k ( J ) N N N J ⊆ P G ( w ) J \subseteq\mathcal{P}_G(w) J ⊆ P G ( w ) a < b a < b a < b h ( a ) < b h(a) < b h ( a ) < b c ≥ b c \ge b c ≥ b h ( a ) < c h(a) < c h ( a ) < c u u u J J J
E ( w ) = 2 inv G ( w ) − M , (61) E(w) = 2\operatorname{inv}_G(w) - M, \tag*{(61)} E ( w ) = 2 inv G ( w ) − M , (61) since no edge is internal to a packet and (53) counts every edge between packets.
At a terminal label x μ x_\mu x μ ( μ 1 , … , μ D ) (\mu_1,\ldots,\mu_D) ( μ 1 , … , μ D ) J ⊆ Q ( s ) J \subseteq Q(s) J ⊆ Q ( s )
B J : { w : J ⊆ P G ( w ) } ⟶ ⨆ μ ⊢ N { ( t , s ) : t ∈ T x μ , mult ( s ) = μ , J ⊆ Q ( s ) } . (62) B_J:\{w:J\subseteq P_G(w)\}\longrightarrow\bigsqcup_{\mu\vdash N}\{(t,s):t\in T_{x_\mu},\operatorname{mult}(s)=\mu,\ J\subseteq Q(s)\}. \tag*{(62)} B J : { w : J ⊆ P G ( w )} ⟶ μ ⊢ N ⨆ {( t , s ) : t ∈ T x μ , mult ( s ) = μ , J ⊆ Q ( s )} . (62) It satisfies E ( t ) = E ( w ) E(t)=E(w) E ( t ) = E ( w ) J J J s s s
We convert the required-mask bijections to exact-mask bijections by finite bijective cancellation, in the spirit of the Garsia–Milne involution principle [16 ] . The complete alternating-path argument below also supplies termination in both directions.
Lemma 6.6 (Exact-mask refinement). For every J ⊆ [ N − 1 ] J\subseteq[N-1] J ⊆ [ N − 1 ] there is a computable energy-preserving bijection Φ J \Phi_J Φ J between the two sides of (62) with their masks required to be exactly J J J Both directions terminate on every input.
Proof. Construct the bijections in decreasing order of ∣ J ∣ |J| ∣ J ∣ J J J w w w B J B_J B J ( t , s ) (t,s) ( t , s ) J J J K = Q ( s ) ⊋ J K=Q(s)\supsetneq J K = Q ( s ) ⊋ J Φ K − 1 \Phi_K^{-1} Φ K − 1 B J B_J B J J J J B J − 1 B_J^{-1} B J − 1 K ⊋ J K\supsetneq J K ⊋ J Φ K \Phi_K Φ K B J − 1 B_J^{-1} B J − 1
To prove that the outer repetition terminates, fix its energy E E E J J J B J B_J B J J J J Φ K \Phi_K Φ K K ⊋ J K\supsetneq J K ⊋ J Figure 2 illustrates the alternating path in their union.
Figure 2. The exact-mask algorithm follows a finite alternating path. An endpoint cannot enter a cycle in the union of two matchings.
An exact-J J J J J J E E E
The partition assigned to a word
Let A G = { w : P G ( w ) = ∅ } \mathcal{A}_G=\{w:\mathcal{P}_G(w)=\varnothing\} A G = { w : P G ( w ) = ∅ } w ∈ A G w\in\mathcal{A}_G w ∈ A G
Φ ∅ ( w ) = ( t , s ) , t ∈ T x μ , Λ G ( w ) = μ . \Phi_{\varnothing}(w)=(t,s),\qquad t\in T_{x_\mu},\qquad\Lambda_G(w)=\mu. Φ ∅ ( w ) = ( t , s ) , t ∈ T x μ , Λ G ( w ) = μ . The finite algorithm on an individual input has four steps.
Construct the triangular embedding and finite cone interval, and fix the common rational path representatives for every required ( H , y ) (H,y) ( H , y )
For each required mask encountered, form its packets and evaluate B J B_J B J
Evaluate Φ ∅ \Phi_{\varnothing} Φ ∅
Read the multiplicities of the resulting weakly decreasing anchor word as the partition Λ G ( w ) \Lambda_G(w) Λ G ( w )
Nested calls strictly increase mask size, while each outer repetition follows an endpoint path in the finite union of two matchings. Thus the call depth is bounded and each alternating walk terminates. There is no need to enumerate the final fibers of Λ G \Lambda_G Λ G
Theorem 6.7 (Permutation witness). For every naturally labeled unit interval graph G G G Λ G ( w ) ⊢ n \Lambda_G(w)\vdash n Λ G ( w ) ⊢ n w ∈ A G w\in\mathcal{A}_G w ∈ A G
X G ( X ; q ) = ∑ w ∈ A G q inv G ( w ) e Λ G ( w ) ( X ) . (63) X_G(X;q)=\sum_{w\in\mathcal{A}_G}q^{\operatorname{inv}_G(w)}e_{\Lambda_G(w)}(X). \tag*{(63)} X G ( X ; q ) = w ∈ A G ∑ q inv G ( w ) e Λ G ( w ) ( X ) . (63) In particular, every elementary coefficient is in N [ q ] \mathbb{N}[q] N [ q ] ∣ E ( G ) ∣ |E(G)| ∣ E ( G ) ∣
Proof. For any padded partition μ \mu μ ( μ 1 , … , μ D ) (\mu_1,\ldots,\mu_D) ( μ 1 , … , μ D ) μ \mu μ Φ ∅ \Phi_{\varnothing} Φ ∅ μ \mu μ T x μ T_{x_\mu} T x μ (61) , and (6.9) give
∑ w ∈ A G Λ G ( w ) = μ v 2 inv G ( w ) − M = ∑ t ∈ T x μ v E ( t ) = [ X u ] Θ x μ H − = [ X u ] m μ ( Y ) . \sum_{\substack{w\in\mathcal{A}_G\\ \Lambda_G(w)=\mu}}v^{2\operatorname{inv}_G(w)-M}
=
\sum_{t\in T_{x_\mu}}v^{E(t)}
=
[X_u]\Theta_{x_\mu}^{H-}
=
[X_u]m_\mu(Y). w ∈ A G Λ G ( w ) = μ ∑ v 2 inv G ( w ) − M = t ∈ T x μ ∑ v E ( t ) = [ X u ] Θ x μ H − = [ X u ] m μ ( Y ) . Multiply by v M v^M v M q = v 2 q=v^2 q = v 2 [ e μ ] X G ( X ; q ) [e_\mu]X_G(X;q) [ e μ ] X G ( X ; q ) (63) . The algorithms producing Λ G ( w ) \Lambda_G(w) Λ G ( w )
The chromatic expansion
We return to the original graph and its graph-nondescent permutations.
Proof of Theorem 1.1. Choose the triangular embedding of Lemma 5.1, and fix the rational generic choices and finite local orders in Section 6 by the enumeration specified there. Theorem 6.7 gives a terminating map Λ G : A G → { λ : λ ⊢ n } \Lambda_G : \mathcal{A}_G \to\{\lambda: \lambda\vdash n\} Λ G : A G → { λ : λ ⊢ n }
∑ w ∈ A G Λ G ( w ) = λ q inv G ( w ) = [ e λ ] X G ( X ; q ) = c λ ( q ) . \sum_{\substack{w \in\mathcal{A}_G \\ \Lambda_G(w)=\lambda}} q^{\operatorname{inv}_G(w)} = [e_\lambda]X_G(X;q) = c_\lambda(q). w ∈ A G Λ G ( w ) = λ ∑ q inv G ( w ) = [ e λ ] X G ( X ; q ) = c λ ( q ) . For σ ∈ D G 0 \sigma\in D_G^0 σ ∈ D G 0
θ G ( σ ) = Λ G ( reverse σ ) . \theta_G(\sigma) = \Lambda_G(\operatorname{reverse}\sigma). θ G ( σ ) = Λ G ( reverse σ ) . By Lemma 2.1, reversal gives the required input to Λ G \Lambda_G Λ G λ \lambda λ
∑ σ ∈ D G 0 θ G ( σ ) = λ q ginv G ( σ ) = q M c λ ( q − 1 ) = c λ ( q ) . \sum_{\substack{\sigma\in D_G^0 \\ \theta_G(\sigma)=\lambda}} q^{\operatorname{ginv}_G(\sigma)} = q^M c_\lambda(q^{-1}) = c_\lambda(q). σ ∈ D G 0 θ G ( σ ) = λ ∑ q ginv G ( σ ) = q M c λ ( q − 1 ) = c λ ( q ) . Together with X G = χ G X_G = \chi_G X G = χ G (2) . Every coefficient is the generating polynomial of a finite set, so it belongs to N [ q ] \mathbb{N}[q] N [ q ] n = 0 n=0 n = 0
Remark 7.1 (Scope of the algorithm). The map uses the graph, the input permutation, finite wall recursions and local coefficient indexings. The elementary coefficient list is not supplied to it. The result proves termination, but gives no polynomial-time bound. The construction is a mathematical algorithm based on finite rational arithmetic and ordered finite sets.
