Elementary positivity of chromatic quasisymmetric functions

Proof. Write \operatorname{ch} for the Frobenius characteristic and \omega for the usual symmetric-function involution, so \omega(e_\lambda)=h_\lambda, the product of complete homogeneous symmetric functions. The identity of Brosnan–Chow [6, Theorem 129] and Guay-Paquet [23], followed by Equation (1.2), gives

Since \operatorname{ch}M^\lambda=h_\lambda [6, proof of Proposition 10], injectivity of the Frobenius characteristic and complete reducibility of finite-dimensional complex S_n-modules give the isomorphism. The argument supplies no preferred isomorphism, geometric basis, or compatibility with cup product.□

Proof. Delete the largest letter a from an admissible word on [a]. If it has predecessor b and successor c, then b<a and h(b)\ge a>c, so the newly consecutive pair (b,c) is allowed. The cases without a predecessor or successor are immediate. Conversely, a can be inserted at the beginning or immediately after any earlier neighbor, and these are exactly the allowed positions. At such a position the new inversions are the earlier neighbors lying to its right. Reading those neighbors in their order in the shorter word shows that the available counts are l_a,l_a-1,\ldots,0, each once. Successive insertion and deletion prove the bijection and degree formula. Reversal exchanges nonedge descents and nonedge ascents and reverses the order of the endpoints of every edge, proving Equation (2.1).□

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), with exponent a_I+a_J and weight v^{\Omega(a_I,a_J)}. Vertices in I\cap J have no neighbors in I\cup J and contribute no skew weight. In the remaining induced graph, every earlier-neighbor set and every later-neighbor set is a clique. Since the graph is bipartite with parts I\setminus J and J\setminus I, each vertex has at most one earlier and one later neighbor. More explicitly, an edge that skipped a vertex of I\cup J in the total order would make a triangle: the interval-closure property supplies both intervening edges. Thus each nontrivial component is an increasing path with alternating membership in I and 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') has sizes k,j. On an odd component the successive edge contributions to \Omega(a_I,a_J) alternate between 1 and -1, with equally many of each. Its skew contribution is therefore zero before and after the exchange. There are no edges between components. Exponents and weights are preserved, and repeating the exchanges recovers (I,J). This is the required bijection of terms.□

Proof. Work first with r colors. Expand the product, in increasing color order,

Its X_u coefficient chooses a disjoint independent set for each color, covering precisely the original vertices. Extra vertices cannot occur because each exponent in each factor has nonnegative vertex coordinates. These choices are exactly the proper colorings. An edge whose later vertex has smaller color contributes +1 to the torus exponent, and an edge whose earlier vertex has smaller color contributes -1. The total exponent is 2\operatorname{inv}_G(f)-M. Hence multiplying this coefficient by v^M gives X_G(x_1,\ldots,x_r;v^2).

For ordinary variables y_1,\ldots,y_D the elementary dual kernel identity is

Indeed, select for each labeled y_i a subset of the x variables; grouping its subset sizes by their multiset gives the displayed sum. Evaluate the symmetric y polynomials at Y, extract X_u, and multiply by v^M. This proves Equation (2.5) for every r, and therefore as a symmetric-function identity. The coloring interpretation proves independence of the ambient graph.□

Proof. Use r colors and send f to r+1-f. This interchanges color ascents and inversions and reverses the variable alphabet. Symmetry, which follows from Proposition 2.3 with \Gamma=G, removes the variable reversal and gives X_G=\chi_G. Since a proper coloring has \operatorname{asc}_G(f)+\operatorname{inv}_G(f)=M, the same argument gives X_G(X;q)=q^M X_G(X;q^{-1}). Take r\ge n, so the elementary functions of degree n are independent, and compare their coefficients. Passing to the symmetric-function limit proves Equation (2.6).□

Proof. Induct on |d|_1. Modulo the chosen lift of B_d, every element is a sum of destabilizing products. Expand their two factors by induction. Draw a polygon for a resulting list by joining the successive points

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: a list of only two such factors could not have a destabilizing cut. The replacement polygons are concave and lie above the chord of the merged pair, hence above the old pair. Equality can occur only for a straight pair, in which case the number of segments decreases. The polygon remains strictly above the total chord somewhere. There are only finitely many lists of nonzero subdimension vectors of d, so this process terminates at strictly decreasing slopes. This proves spanning.

For independence, restrict an ordered product to targets r_1,\ldots,r_m of strictly decreasing slopes. A surviving split has no destabilizing source prefix in any target. At a source cut, if the portion in target r_j has charge b_j, its height is at most b_j\mu(r_j). Among all choices with fixed sum \sum_jb_j, this upper bound is maximized by filling the targets in decreasing slope order. Thus the source polygon lies below the target polygon at every source corner, and hence everywhere: the target polygon is concave. If the polygons coincide, strictness of their slopes forces equality at each corner. The first target must be completely filled at the first corner, the first two at the second, and so on. Consequently the only surviving split assigns whole source groups to the matching whole targets. In particular the 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.□

Proof. Consider a destabilizing product with first dimension a. If every piece of a in a target had slope at most the common slope, their sum would too, contrary to \mu(a)>\mu(d). Some target is therefore destabilized, and the preceding Taylor test kills the term. This proves descent. Refinement is composition of polynomial substitutions; the descended maps therefore compose as claimed.

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 (3.7); 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.□

Proof. Write S(P)=\sum_{r\in P}s(r). Merge two groups a,b of P. The shift sum becomes S(P)+\chi(a,b). Refine this merged group again, giving the two groups a relative center \delta=z_b-z_a. This refinement is homogeneous if \delta is counted, together with the internal variables, as degree one. By the coarse filtration test, every term before this refinement has degree at least w-S(P)-\chi(a,b). Therefore a term of fine internal degree w-S(P) must have \delta-degree at least -\chi(a,b). When \chi(a,b)<0, this proves exactly the divisibility required to cancel the denominator in Equation (3.16). Perform this argument for every pair. To justify simultaneous cancellation, choose a \Q-basis of the quotient tensor space and write the polynomial in that basis. Each scalar coefficient is divisible by the requisite power of each diagonal difference. Distinct differences z_j-z_i, for unordered pairs \{i,j\}, are relatively prime irreducibles, so their product divides that coefficient. No domain property of a quotient algebra is needed.

Joint injectivity follows directly from Equation (3.15): if all leading restrictions vanish, the representative belongs to \cF_{w+1/2}. Multiplication by the nonzero center prefactors cannot change this conclusion, as can be seen after adjoining the independent centers as a field extension.

For completeness, a tensor satisfies all lower-bound restriction tests exactly when it belongs to Equation (3.17). 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. Tensoring the two injective families of graded restriction maps over \Q is injective. At a fixed total grade, contributions of different factor grades u,v cannot cancel: in tests R,S their two separate internal degrees are u-S(R) and v-S(S), respectively. Thus some tensor test detects the violating grade. The same argument proves joint detection on every associated tensor grade, including after adjoining center variables or localizing their nonzero differences.□

Proof. Use Lemma 3.3 and expand intergroup kernels at separated centers. Every nonconstant internal Taylor term increases internal degree. In target i, internal shuffling changes polynomial degree by -\chi(d_i',e_i'), exactly compensated by

This proves the filtration bound. On its leading grade only the scalar intergroup kernels remain. For i<j, their contribution is

Multiplication by the L_R prefactor cancels these exponents against the cross terms in \chi(r_i,r_j), leaving the two input prefactors and the sign (-1)^{\chi(d_j',e_i')}. Multiplying these signs over i<j gives Equation (3.18).□

Proof. Take first a,b\ne0 and a representative f\in\cF_wB_d homogeneous of polynomial degree \ell. Form the Laurent expansion at Z=\infty

Each coefficient is an actual polynomial tensor before quotienting: expand the finitely many integer powers of linear factors, and note that a specified Z-power receives only finitely many binomial choices. The expansion is separately symmetric in the two packs. It descends from B_d because the restriction descends and the target ideals are ordinary ideals. Homogeneity, counting Z as degree one, gives

In particular C_j(f)=0 for j>\ell+\chi(a,b).

Apply arbitrary refinements R=(r_i) of a and S=(s_j) of b to each coefficient. Their centers in the first list are shifted by Z. The internal-degree-zero part of the inverse kernel is

and all its other internal terms have positive degree. The restriction of f to the concatenated list has internal shifted degree at least w, by its defining filtration tests. Thus the refined tests of every C_j(f) have the same lower bound. Tensor detection in Lemma 3.5 proves C_j(f)\in\cF_w(B_a\otimes B_b), coefficient by coefficient.

On the weight-w grade only Equation (3.22) contributes. Multiplying by the two separate symbol prefactors supplies exactly the missing cross-list factors, so

By Lemma 3.5, the right side is a polynomial in all its centers and in Z. Consequently every j<0 has zero image under every tensor symbol. The same Lemma implies [C_j(f)]=0 for each j<0. This conclusion holds in the actual associated graded tensor space; it is not a conclusion drawn after a specialization of a rational kernel.

Equation (3.21) leaves only finitely many nonnegative Z-powers. We may therefore evaluate this finite tensor polynomial at zero and define

Changing f by \cF_{w+1/2} changes every coefficient by that higher tensor filtration, so the definition is independent of the representative. Setting Z=0 in Equation (3.23) proves Equation (3.19). Finally the original shifted degree of C_0(f) is

as required.□

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)^{\chi(a,b)}; the underlying restriction is simply permuted. Detection therefore gives signed cocommutativity. The empty-list components give the counit and the unit identities.

For multiplicativity apply Equation (3.18) to the two tensor factors separately. If the first input contributes dimensions d_R,d_S to the two lists, and the second contributes e_R,e_S, concatenating the lists adds to the two separate symbol signs exactly

This is the interchange sign in Equation (3.24). Both sides therefore have the symbols of the product restricted to the concatenation, and detection proves multiplicativity. Positive dimension grading and \mathcal H_0=\Q give connectedness.□

Proof. For linear maps out of \mathcal H, convolution uses its coproduct and multiplication in the target. Let e be augmentation followed by inclusion of the unit, and put

On dimension d, a nonzero term has at most |d|_1 positive dimensions, so this sum and all subsequent convolution series are finite there. In the target algebra \mathcal H\otimes\mathcal H define \alpha(h)=h\otimes1 and \beta(h)=1\otimes h. Then \alpha*\beta=\Delta, while signed cocommutativity gives \beta*\alpha=\Delta as well. Since \Delta is multiplicative,

Thus \mathsf P takes values in \mathcal P. Exponentiating,

The iterated coproduct is invariant under signed permutations, and \mathsf P preserves all gradings. This expression therefore spans \mathcal H by signed symmetrized products of primitives.

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 be the largest tensor length. Apply the iterated coproduct with r factors and project each factor to positive dimension. Terms of length less than r vanish. A product of r primitives gives the sum of their r! signed permutations; on its symmetrized tensor this is r! times that tensor. Hence the length-r part of the relation is zero. Descending on r proves independence.

For a homogeneous basis of \mathcal P, a multiset contributes one signed symmetric tensor unless an element with self-sign -1 repeats, in which case it contributes zero. This proves the stated description of dimensions. In particular, an odd primitive may have a nonzero square in \mathcal H. Its square is then an even primitive, since the two middle coproduct terms cancel, and is accounted for in the even primitive subspace. No assertion that raw odd squares vanish is used in Equation (3.25).□

Proof. On S_d, consider common differentiation and multiplication by the variable mean,

The translation invariance of the shuffle kernels implies D_d(I_d)\subset I_d. The ideal property implies T_d(I_d)\subset I_d. Thus both operators descend to B_d. For P=(r_1,\ldots,r_m), restriction gives

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 depends only on center differences, so its common center derivative vanishes. Consequently

They preserve the common kernel of all proper symbols, hence the primitive space. They satisfy D_dT_d-T_dD_d=\id there; D_d is locally nilpotent, and T_d raises original shifted degree by one.

Here is an explicit string decomposition. On a space with these operators define the finite-on-each-vector operator

The commutator identity gives D_d\pi=0. Binomial cancellation gives

Choose a homogeneous basis of \ker D_d in the primitive space. Its T_d-iterates therefore span. They are independent: in a finite relation \sum_{j=0}^rT_d^jb_j=0 with D_db_j=0, applying D_d^r gives r!b_r=0, and induction removes the other terms.

Every component of \mathcal H_d is a subquotient of B_d, with original shifted degree equal to nonnegative polynomial degree plus s(d). Thus every string begins at h\ge s(d) with the indicated integral difference. The polynomial spaces in any fixed degree are finite-dimensional, and the filtration is finite there, proving the finiteness assertion. Finally the self-sign depends only on the dimension vector, as stated.□

Proof. Choosing j distinct indices 0\le i_1<\cdots<i_j in (4.3) gives weight v^{-j-2\sum i_s}. Subtracting 0,1,\ldots,j-1 from these indices leaves a weakly increasing nonnegative list. Its successive differences have weights v^{-2},\ldots,v^{-2j}, which proves (4.6). The commutation relation X_aX_m=v^{2t}X_mX_a proves (4.7). Cancellation of the two infinite strings leaves the displayed finite strings. Each factor 1+v^bX_a, or (1-v^bX_a)^{-1}, has nonnegative coefficients. Replacing X_mX_{ja} by its centered monomial changes only the power of v. The case t=0 is the identity.□

Proof. Fix a root-degree bound d, and argue inductively in d. For a given ray \R_{>0}r, follow a generic line in r^\perp, parallel to V(r), from far in the positive direction towards the specified cell. The initial element is the incoming element just proved. At the finitely many joints met by the line, all relevant normals lie in a two-dimensional plane containing r. A normal s with \Omega(s,r)=0 gives a hyperplane parallel to the line, which a generic offset avoids. Thus a joint at which a change occurs has nonzero skew form on its plane. The offset can also avoid every intersection involving three independent normals.

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) of a ray a, earlier normals evaluate positively and later ones negatively. The local middle element is therefore the ordered product of its incoming ray elements in this order. Its factorization in the reverse order gives its outgoing ray elements. Theorem 3.1 applies to precisely this positive ordering and to the pointed monoid obtained by intersecting the plane with C^+.

There is a small induction issue at degree d. The incoming element on the ray being followed is already known through degree d from the previous segment. On all other incoming rays it is enough to know positive factorizations through degree d-1. Indeed, a degree-d input term can affect an output term of degree d only linearly: multiplication with any nonconstant term raises the degree. Its linear contribution remains on its own ray. Unknown degree-d terms on other rays consequently do not affect the ray under consideration. Extend their known positive lists arbitrarily to the required truncation, apply Theorem 3.1, and use uniqueness of ray factorization. This proves the assertion at each successive joint and completes the induction.

For the last assertion, a positive-to-negative crossing has \Omega(r,m)>0 and uses the adjoint of the wall element; a negative-to-positive crossing has \Omega(r,m)<0 and uses its inverse. All elementary arguments are positive multiples of r, so Lemma 4.1 applies to every factor.

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. If a contribution has energy E, no selected parameter can tend to -\infty: the bounded number of other parameters and the bounded interaction shifts could not compensate for it. Every selected parameter is therefore above an explicit lower threshold depending on the root bound and E. Only finitely many occurrences lie above that threshold. Their nonnegative string indices are then bounded as well. This proves both finite multiplicity at each energy and a common upper energy bound. The corresponding output-list bounds are supplied by Theorem 3.1. Thus all the asserted coefficients belong to \N((v^{-1})), rather than merely being formal infinite sums of nonnegative integers.□

Proof. After rescaling by s, the initial point tends to V(n), so its X_n-coefficient is A_n(F). Hyperplanes whose normals pair trivially with n are parallel to this line and are avoided by choosing h generically. Every actual crossing has the sign of -V(n); the input n-jp_i has the same pairing with the wall as n. Proposition 4.2 proves the stated positivity and the no-jump assertion. Taking the X_n-coefficient in each crossing identity and summing the successive differences proves (4.12). 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, (4.6) gives rational functions of v for the input coefficients. The triangular equations (4.4) and (4.2), followed by inversion and multiplication at bounded root order, therefore give rational functions of v for every required wall coefficient. Their Laurent expansions at v^{-1}=0 compute the requested jump coefficients and their upper energy bounds. No positive factorization needs to be found by the algorithm. A finite polynomial initial value can be transported by these same finite rational operations; finitely specified incoming data can instead be used in (4.12). 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.□

Proof. Fix a target exponent and its finite interval above the support lower bounds. Induct on the addition order in this interval, using (4.12). 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.□

Proof. Evaluate the product near V(n) to compute its incoming n-coefficient. Each factor is positive by Theorem 4.4; the scalar contributed by torus multiplication is a power of v. For fixed total exponent there are only finitely many tuples of factor exponents above their specified lower bounds. Their Laurent products have finite coefficients at each energy. Thus the incoming coefficient is nonnegative, and (4.11) proves the assertion.□

Proof. Projection to the face \N p is an algebra homomorphism: a sum of roots with a nonzero non-p component cannot be pure. At any point of p^\perp, the pure part of the middle factor is thus the pure part of g, which is D_p by (4.4). This proves the last assertion.

We prove (4.17) by induction on |u|, not on k+|u|. During this induction, an assertion about an individual coefficient at kp+u is always checked first in a finite full-degree truncation containing that coefficient. No uniform finiteness in k is presumed.

Put t=\Omega(p,u)=\sum_c\alpha_cu_c. If t\ne0, call the side \sigma=\operatorname{sign}(t) upstream. A line in (kp+u)^\perp, followed from the incoming direction V(kp+u) to a point on that side, never crosses p^\perp: the evaluation on p along its forward tail is h(p)+st with s\ge0. If t=0, the line is parallel to the cut and the same argument applies on either side. At its incoming end the bound holds, since the only nontrivial incoming rays are simple ones, with k=0.

Consider a joint off the cut along this line. Every normal involved has positive non-p degree. In an ordered refactorization, a genuinely new contribution of non-p degree |u| is a product of at least two such terms and therefore uses only smaller non-p degrees. A term already of degree |u| contributes linearly on its own ray, so it is merely carried to the next segment. By induction every smaller term satisfies (4.17). The bound is additive in u: sums of supported exponents are still supported in

It follows, by the coefficient recursion for ray factorization, that the bound persists at this joint. This proves the upstream assertion for each k separately, through finitely many joints at the order needed for that k. Only now do we conclude that the entire upstream fiber has finite support, since the numerical upper bound M_\sigma(u) is independent of the truncation.

Suppose t\ne0 and continue to the other side. At a generic transverse joint on p^\perp\cap u^\perp, the normals lie in the plane spanned by p and u. Their non-pure projections are positive multiples of the same ray through u. Their pairings with p are consequently nonzero and have the common sign \sigma. Such genericity is imposed only through the finite non-p degrees currently needed; the upstream bounds just proved make the corresponding full-degree arrangement finite.

Separate the pure factor D_p from the incoming ordered product of non-pure factors. If \sigma=+1, p is first in the incoming order, and refactorization conjugates the non-pure product by D_p. If \sigma=-1, p is last, and it conjugates that product by D_p^{-1}. Formula (4.8) shows that an input monomial X_{kp+w} acquires only additional exponents jp with

All relevant w have the same pairing sign. On this ray,

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 degree, or already established upstream coefficients of the current degree. This avoids a circular appeal to downstream finiteness. Further joints off the cut are treated by the same smaller-degree argument as before. Finally, the support monoid is additive, so its bound is preserved by both logarithm and exponential. The statement holds for wall elements and their logarithms.□

Proof. First we establish the identity of transformations at the cut, with the normalization of Lemma 4.1:

For t=\Omega(p,m)\ge0, the coefficient of X_{m+jp} in \Ad(D_p)X_m is

The displayed letters are invariant under inversion and have product one, so b_{t,j}=b_{t,t-j}. Applying S sends the exponent m+jp to m-(t-j)p. On the other hand, the finite formula for \Ad(D_{-p})^{-1}X_m has coefficients b_{t,j} at m-jp. This proves (4.21) on X_m. When t<0, apply the proved identity to X_{-m} and take its inverse. Both sides are algebra homomorphisms, so the identity follows on all rational monomial expressions.

A common ring for the comparison. Set Z=X_p, choose a lattice complement M=\Z p\oplus L containing C\setminus\{p\}, and allow coefficients in K(Z) on the monomials X_\ell, \ell\in L. Complete in the free positive monoid generated by the images of C\setminus\{p\} modulo p, allowing a finite union of translates for section values. Multiplication is specified by (4.1) and the rule

Consequently a coefficient at each specified non-p exponent is a rational function of Z. Products use finitely many decompositions of that non-p exponent. This ring will be used only for comparisons; it does not identify the two Laurent completions in Z.

By Lemma 4.6, a non-cut wall element is polynomial in Z at each fixed non-p degree. Its constant term in non-p degree is one. Its inverse, computed by the geometric series in positive non-p degree, is therefore polynomial in Z at each such degree as well. The same assertions hold with Laurent polynomials after applying either linear piece of the chart map. Conjugation by these elements is thus a well-defined operation on the common ring. Pure conjugation by D_p^{\pm1} fixes Z and sends any X_\ell to a rational function of Z times X_\ell, by (4.7). It, too, acts on this ring. The map S is the identity modulo p, so it preserves the non-p degree and acts in the same ring.

We justify importing the old consistency into this ring. The expansion homomorphism

at Z=0 is injective. On a monomial input, expansion of every old crossing operation agrees with its operation in the old positive completion: its increments lie in C^+, and the pure ratios have their usual power-series expansions at zero. At bounded non-p degree, all non-cut wall elements are controlled by finitely many old roots by Lemma 4.6. The path may be made generic for these data. To test a further coefficient in its expansion in Z, perturb through the additional finite old order needed for that coefficient; this does not alter the already specified projected operations. Old path independence holds at each such full order. Hence a rational difference between two path operations has zero Laurent expansion in every non-p degree, and injectivity forces that difference to be zero. This proves old consistency in the common ring, on every monomial and therefore on its completed modules.

Consistency and incoming data after mutation. Push the non-cut elements by L_\sigma and put D_{-p} on the pure cut. Equation (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 (4.21). Thus the pushed path operations are consistent in the common rational ring. Expand now at Z^{-1}=0 to obtain their operations in the new cone completion. Replacing c by c'=c+[-\alpha_c]_+p changes the coefficient at a fixed projected exponent only by a Laurent monomial in Z and a scalar power of v. Equation (4.18) ensures that every pushed increment is C'^+-positive, so this fiberwise expansion is precisely the one in the new completion. The finite-order bounds already proved make this expansion coefficientwise legitimate. They are consistent there as well. Since the form is nondegenerate, adjoint actions detect the wall group elements: for a nonzero first root r in the logarithm of an element, choose m with \Omega(r,m)\ne0; its commutator with X_m is nonzero. Consequently consistency of the actions also gives consistency of the wall products.

It remains to identify this system by its incoming prescription. A symplectic linear map L satisfies V(Lr)=L^\vee V(r). Thus on each eventual open side, the incoming direction of a pushed ray is the image of its old incoming direction. For a simple c\ne p, V(c)(p)=\alpha_c, so that the relevant piece sends c to exactly c'=c+[-\alpha_c]_+p. Its unit is therefore D_{c'}. All other non-pure incoming logarithmic coefficients vanish. If an incoming direction is parallel to the cut, its pairing with p is zero; the two pieces agree on its exponent, and either sufficiently small generic offset gives the same conclusion by the trace argument (4.5). A component with no preimage wall has zero coefficient. The pure incoming element is D_{-p} by construction. Uniqueness of (4.4) identifies the pushed system with the system for C'.

Actual coefficients of polynomial sections. We now use the finite-polynomial hypothesis in (4.19). Choose a point on the cut with h(c)<-1 for all c\ne p, and take h(p) very small on either side. Such covectors exist because C is part of a basis. With the constant B defined after (4.18), choosing |h(p)|<(B+1)^{-1} ensures that every non-pure supported root off the cut has negative evaluation:

At the cut itself h(u)<0. Hence the short crossing between these points meets only the pure wall. The negative side is in the old all-negative chamber. The positive side is in the new all-negative chamber, since h(-p)<0 and h(c')<0.

On the positive side, the old value is

which is the actual finite Laurent polynomial specified in the new chamber. On the negative side the pushed old value is SF, while (4.21) and (4.19) give

This too is a finite Laurent polynomial, because F is one and S is linear. We have therefore established equality of actual finite values on both sides near the cut.

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-fiber at every fixed non-p degree, as proved above. Starting from a finite Laurent polynomial, successive transport consequently retains finite Laurent support in each such fiber: the required coefficient uses finitely many decompositions of the non-p degree and finitely many crossings in its bounded arrangement. Applying L_\sigma preserves this property. The compared fiber is therefore the same finite Laurent polynomial on the two sides of the identification. Its coefficient equality is independent of whether it is regarded in the old or the new completion. This establishes the claimed equality of actual section coefficients throughout both open sides. In particular, the argument never equates the expansions at zero and infinity of an arbitrary rational function.

Finally, put t=\Omega(p,n). The incoming direction V(n) lies on the side of sign t. The relevant linear piece sends n to n if t>0, and to S(n)=n-tp if t<0. If t=0, both pieces fix n, and either generic perturbation computes the same incoming coefficient. This proves (4.20). Its label map preserves \Omega(p,n), so its inverse subtracts [-\Omega(p,n)]_+p. The label map is thus a bijection, as asserted.□

Proof. For n=0 take D=1. For n>0, first construct strictly increasing positive rational times t_1,\ldots,t_n, with distinct nonzero fractional parts, such that a<b is an edge exactly when t_b-t_a<1. Choose any positive nonintegral rational t_1. For k\geq2, suppose the times through t_{k-1} have been chosen. The earlier neighbors of k form a suffix s,s+1,\ldots,k-1 because the defining function h is weakly increasing. If that suffix is empty, choose t_k>t_{k-1}+1. Otherwise choose

omitting t_{s-1}+1 when s=1. The interval is nonempty: when s>1 we have t_{s-1}<t_s, and either s=k-1 or s and k-1 are already adjacent, since h(s)\geq k. These inequalities give exactly the required earlier neighbors. At each step an open interval of choices remains, so rational choices avoiding all previously used fractional parts are possible.

Shift every time by a common integer so that every level \lfloor t_a\rfloor is at least n, and then choose D so large that all these levels are at most D-1. Order the n selected vertices by increasing fractional part and assign them, in that order, to the rows n,n-1,\ldots,1. A vertex of level i\geq n has an available bridge in every one of these rows. Set that bridge’s phase equal to the vertex’s fractional part. There is one prescribed phase per selected row, and they increase in the order (5.1). Insert all the other phases as rational numbers between these prescribed values, respecting the same order. The selected bridges have exactly the shifted original times, so their ordered induced graph is the given graph.□

Proof. It suffices to prove (5.5) for E_k. Relative to all vertices outside \{d_i,b,d_{i+1}\}, the old bridge b has the same neighbors as d_i, whereas the new bridge b' has the same neighbors as d_{i+1}. The elementary conjugation formulas give

For completeness, the first identity is the centered binomial formula with pairing 1 and d_i+p=b; the second is its inverse with pairing -1 and d_{i+1}+p=b'; the last uses pairing zero. Fix an independent set outside this triple. Its monomial commutes with X_p. The displayed identities match all ways to extend it by no vertex, one vertex, or the independent pair \{d_i,d_{i+1}\}. Their sum proves the assertion for each E_k. Since conjugation is an algebra automorphism and the E_k commute, the assertion follows for P. Theorem 4.7, applied to these finite polynomial values, now gives (5.6).□

Proof. For D=1 the support bound already gives m=Nd_1, so assume D>1. Track the nonzero coefficient using (5.6). At each stage use the current vertex basis to write its current label as \sum\nu_i d_i+\sum\kappa_b b. When b on level i is moved, put t=[-\Omega(b-d_i,m)]_+. Reexpressing m+t(b-d_i) using b'=b+d_{i+1}-d_i gives

with all other coordinates unchanged. Thus every individual bridge coordinate, and every K_i, is a nondecreasing integer along the tracked sequence.

In every chart the current polynomial has support Nd_1+C^+. Triangularity of incoming coordinates preserves this lower support bound. In particular the cut just before d_{i+1} gives the nonnegative deficit

Equation (5.8) shows that B_i changes only at moves on level i, and then changes by -\kappa_b'. If K_i were positive at any stage, each subsequent complete period would decrease B_i by at least this positive integer: each bridge’s coordinate at its next move is at least its coordinate at the start of the period. This contradicts (5.9). Therefore K_i\leq0 at every stage.

Since each \kappa_b is nondecreasing and their level sum is bounded above by zero, each \kappa_b is bounded above as well; one may use the initial lower bounds for the other bridge coordinates on its level. All these integer sequences stabilize. From that time on every t is zero, and the lattice vector of the tracked label is a fixed vector m_*. Its anchor coordinates in the moving vertex basis need not be fixed.

At the event originally named b on level i, the root in period L is b-d_i+L\delta_i. For all sufficiently large L its pairing with m_* is nonnegative. Its slope as a function of L is

Indeed \delta_i pairs by 2 with a bridge on level i, by -1 with a bridge on either neighboring level, and by zero with all other vertices. The sequence K_0,\ldots,K_D is therefore discretely concave. With zero endpoints it lies above the zero chord, so K_i\geq0. Together with K_i\leq0, this proves K_i=0.

The slopes in (5.10) now vanish. Consequently m_* pairs with every original event root just as it does with its late counterparts; all these pairings are nonnegative. It is fixed by every tropical step, including the earlier ones. Each map T_p(x)=x+[-\Omega(p,x)]_+p is invertible, with inverse x\mapsto x-[-\Omega(p,x)]_+p, because adding p leaves its pairing with p unchanged. Applying these inverses recovers the same m_* at every earlier stage. This proves (5.7) for the original label.

For a pure label, \xi_{j,i}=\mu_i-\mu_{i+1}, so its coordinates decrease. The last cut in (5.9) says \mu_D\geq0. Weight is unchanged by every operation, hence \sum_i\mu_i=N.□

Proof. We choose a single sufficiently large integer L after fixing the finite set of possible increments for this coefficient. Since m-Nd_1\in C^+, that set is

where r\leq s means s-r\in C^+. It is finite because C is a finite free basis. Its members have bounded original vertex coordinates, independently of L.

Define a covector by

For the moved bridge b^{(L)}=b+L\delta_i its value is Q_L(b^{(L)})=D-i-\theta_b. The values strictly decrease along each moved forward list, so Q_L is in the all-negative chamber for C_L. Every mutation cut used in the first L periods has root p_b^{(\ell)}=b-d_i+\ell\delta_i for some 0\leq\ell<L, and

Hence the entire ray Q_L+sV(m), s\geq0, lies on the identity side of all these cuts. Repeated application of Theorem 4.7 identifies the wall systems there by the identity on lattice vectors, and identifies the section at Q_L with the finite graph polynomial in the chart after L periods.

Consider a wall capable of changing the coefficient of X_m along this ray. Any positive increment on its ray belongs to \mathcal R_m: the starting exponent is at least Nd_1 in the original cone. Furthermore an actual contributing wall root belongs to C_L^+, by the successive identity-side wall identifications. This assertion concerns the roots on those walls; it does not assert an inclusion between the entire old and new cones.

For r\in\mathcal R_m, write its original coordinates as \nu_i(r),\kappa_b(r) and put

As a fixed vector reexpressed after L periods, r has unchanged bridge coordinates and anchor coordinates

Thus its moved prefix is P_i(r)+LK_i(r). A weight-zero member of C_L^+ has nonpositive prefixes, giving P_i(r)+LK_i(r)\leq0. Choose L larger than all -P_i(r) for r\in\mathcal R_m and 1\leq i<D. Since the K_i(r) are integers, every contributing candidate must then satisfy K_i(r)\leq0 for all i.

There is also an L-independent quantity q_0(r) such that

Increasing the same L to exceed all q_0(r) makes Q_L(r)<0 whenever some K_i(r)<0 and all are nonpositive. For every contributing candidate,

If some K_i(r)<0, then (Q_L+sV(m))(r)=Q_L(r)+s\Omega(r,m)<0 for every s\geq0, so the ray never crosses its hyperplane. If all K_i(r) vanish, the pairing is zero. A wall on this ray fixes every monomial X_{m-ar}, since \Omega(r,m-ar)=0, and cannot change the X_m coefficient.

All these comparisons require only finitely many orders for the fixed target and the chosen L. Perturb Q_L by a sufficiently small generic covector at these orders, retaining the strict cut inequalities and the strict negative inequalities just established. This also handles any walls parallel to the unperturbed ray; their zero-pairing actions still fix the target coefficient. For large s, the target coefficient at Q_L+sV(m) is the incoming coefficient by its definition. It therefore equals the coefficient at Q_L.

Finally, in the moved vertex basis the target m still has zero bridge coordinates. Every graph monomial using a bridge has a positive coordinate at that bridge, and hence cannot contribute. Suppressing all bridges leaves the independent anchors; their monomials commute without powers of v. The coefficient at Q_L is exactly the right side of (5.11).□

Proof. Assume D>1, as the assertion for D=1 is immediate. Take any label m with A_m(U)\ne0. By the support bound and Lemma 5.3, the vector m-d_1 is a nonnegative integer combination of the forward gaps, its bridge totals K_i vanish, and all \xi_{j,i} are nonnegative.

On level i, let u_{j,i} be the coefficient of the gap immediately following b_{j,i} in (5.2). Put a_i=u_{1,i}, and a_0=0. The sum of the bridge coordinates on that level is the first gap coefficient minus the last gap coefficient. Thus K_i=0 says that the initial gap b_{i,i}-d_i also has coefficient a_i. In particular both end gaps are included in this notation. Figure 1 illustrates these coefficients. All the u_{j,i} and a_i are nonnegative integers.

We spell out the pairing calculation underlying the recurrence. For p=b_{j,i}-d_i, its values on the same-level bridges are 2 before b_{j,i}, 1 at b_{j,i}, and 0 after it. On bridges of a neighboring level its values are -1 before this phase and 0 after it. Its anchor values are 1 at d_i, -1 at d_{i+1}, and zero elsewhere. Evaluate these values on successive differences. The contribution on its own level is minus the two gaps adjacent to b_{j,i}: the additional contributions from the two end gaps cancel because their coefficients agree. On level i-1 the same endpoint cancellation leaves the coefficient of the gap containing the phase of b_{j,i}; on level i+1 that coefficient is obtained directly. The contribution of the initial d_1 is \boldsymbol1_{i=1}. With nonexistent terms interpreted as zero, this gives

Indeed the upper neighboring gap follows the event in row j+1; the lower neighboring gap follows the event in row j when j<i, and is its initial gap when j=i.

Set

again using zero for nonexistent terms. Equation (5.16) is equivalently

Each row of T is weakly decreasing and ends in T_{j,n_0}=u_{j,n_0}\geq0. Hence every T_{j,i}\geq0. The row-start inequalities then give a_1\leq1 and a_j\leq a_{j-1} for j>1. Integrality shows that

for some 0\leq e\leq n_0. The case e=n_0 is impossible: every row-start upper bound in Equation (5.17) would be zero, giving T=0 and then u=0, contrary to a_1=1.

All rows of T except row e+1 have zero row-start upper bound. Row e+1 has upper bound 1, so its nonzero entries form an initial stretch of ones in columns e+1,\ldots,t, for some e\leq t\leq n_0; t=e denotes an empty stretch. The definition of T telescopes along southeast diagonals:

In particular u_{1,i}=a_i is 1 exactly for 1\leq i\leq t-e. Comparison with its already known run of length e gives t=2e. Thus every positive gap coefficient is on a level i\leq2e. From (5.17), a positive \xi_{j,i} can occur only at the drop after this stretch, in level 2e+1 (if that level exists). In particular all \xi_{j,i} on a positively used level are zero. When e=0, every gap coefficient is zero and the possible positive value is the initial term \xi_{1,1}; thus the same conclusion includes the empty stretch.

Every positively used forward root therefore pairs trivially with m. For an interior gap its pairing is the difference of the two adjacent \xi values; for the first gap it is \xi_{i,i}. For the last gap it is

since K=0 gives \Omega(\delta_i,m)=0 by Equation (5.10). This verifies both end gaps as well as the interior ones.

A wall increment capable of changing [X_m] lies in the finite interval 0<r\leq m-d_1. As C is free, such an r can use only positively used gaps, and hence \Omega(r,m)=0. Conjugation on that ray fixes every possible predecessor of m. It follows that transport from the all-negative chamber to the incoming direction does not change this coefficient, so A_m(U)=[X_m]U. The only vertex exponent consistent with Lemma 5.3 is d_1: bridges have nonzero level total, and a pure unit vector is dominant only at the first anchor. Therefore the only nonzero incoming coefficient of U is A_{d_1}(U)=1. The definition of the incoming basis proves U=\Theta_{d_1}.□

Proof. Lemma 5.6 and Corollary 4.5 give a nonnegative incoming expansion of U^N. Lemma 5.5, applied to (z_1+\cdots+z_D)^N, gives

Every section in this expansion has nonnegative coefficients in every chamber by Theorem 4.4. Retaining the one displayed summand therefore gives (5.19). The right side is a finite Laurent polynomial with nonnegative vertex exponents and nonnegative integral coefficients in v. No coefficient outside that finite support, and no negative vertex coordinate, can occur in the retained positive summand. This proves all the claims, including finiteness of its Laurent coefficients. The case N=0 is the identity section.□

Proof. For D=1 the cone is trivial and the assertion is immediate. Otherwise set N=|\lambda| and x_\lambda=\sum_i\lambda_i d_i. The polynomial m_\lambda(Y) has nonnegative vertex exponents: it is a polynomial in the independent-set generators, each of which has this support property. This assertion concerns its exponent support and does not assume coefficient positivity. Lemma 5.7 already gives the same support property for \Theta_{x_\lambda}.

By Lemmas 5.3 and 5.5, the pure incoming coefficients of m_\lambda(Y) are 1 at x_\lambda and zero at every other pure label. Indeed m_\lambda is the sum of the distinct ordinary monomials in the orbit of \lambda, and that orbit contains exactly one dominant vector. Subtract the indicated section and write

Its ordinary support still has nonnegative vertex coordinates, all its pure incoming coefficients vanish, and both its ordinary and incoming support lie in Nd_1+C^+.

If an incoming coefficient remains nonzero, its label m is mixed and satisfies K_i(m)=0 by Lemma 5.3; subtracting \Theta_{x_\lambda} changes only one pure incoming coefficient. A nonzero bridge-coordinate vector with zero sum on each level has some negative bridge coordinate. Among all remaining labels choose one with minimum height in Nd_1+C^+, where the height is the sum of its nonnegative simple root coordinates. A minimum exists in \N, even if the incoming expansion is infinite. Incoming triangularity says that the ordinary coefficient at this label equals its incoming coefficient plus contributions from strictly lower incoming labels. There are no such nonzero lower terms by the choice of height. Hence [X_m]F=A_m(F)\ne0, contradicting the negative bridge coordinate of m and the vertex support already proved. No coefficient remains, proving (5.20). Finally m_{(1^k)}=e_k gives (5.21).□

Proof. Choose the embedding of Lemma 5.1, taking D\geq n. Proposition 2.3, Lemma 2.5, and Theorem 5.8 give

The last expression has nonnegative integral coefficients at every power of v by Theorem 4.4. On the other hand, the coloring definition has q-degree at most M. In any number of variables at least n, the elementary monomials form an integral basis in degree n; symmetry therefore gives c_\lambda(q)\in\Z[q] of degree at most M. Comparing these finite polynomials with the displayed Laurent-series identity proves coefficientwise nonnegativity and Equation (5.22).□

Proof. The support of E_k in every chamber is contained in kd_1+C^+. Consequently every packet offset and every jump increment in a decomposition with total exponent at most u is at most R. There are finitely many exponent tuples, wall directions, and truncated chambers. This assertion applies to underlying packet states as well as to their states after jumps.

At each fixed exponent the coefficient of a section or wall jump lies in \Z((v^{-1})): it has a finite upper energy bound and finite coefficients at individual energies. For a fixed exponent tuple, write its energy equation as

where \kappa is the fixed sum of torus cross terms. If the coefficient of the ith piece has upper energy bound U_i, then

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

The triangular factorization and incoming equations of Section 4 determine every wall coefficient to the required root order by finite rational arithmetic in v. Transport of the finite independent-set sums determines the needed E_k^H in the same way. A rational function expanded at v^{-1}=0 has a computable upper degree, and any finite interval of its coefficients is computable by formal division. Reducing numerator and denominator first also decides whether it vanishes. One may therefore compute the bounds in Equation (6.3), 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.□

Proof. For a packet with exponent a, call its type positive if \varepsilon\Omega(p,a)\geq0, and negative otherwise. Adding a multiple of p does not change this type. In particular the types are recoverable on both sides of Equation (6.5).

For a positive packet the section identity E_k^{II}=W(E_k^I) expresses each decorated state in II as a state in I followed by a positive jump of W. More precisely, at fixed output exponent and energy the two sets have the same cardinality, so identify them by their finite ranks from Lemma 6.1. For a negative packet use instead E_k^I=W^{-1}(E_k^{II}): a state in I is identified with a state in II followed by a positive jump of W^{-1}. Packets of zero pairing are fixed. These identifications have computable inverses.

Fix the retained state of each packet: in chamber I for a positive packet, and in chamber II for a negative packet. Write x_i for its exponent, and keep its energy and decoration index fixed. The two positive expansions to be matched are

Via the single-packet bijections, a decorated term of L_i together with its retained state gives a packet in II; a decorated term of R_i together with that state gives a packet in I. Each row satisfies L_i=W(R_i), so the automorphism property gives

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, the input of the total jump differs from y by a multiple of p. Its pairing is therefore \Omega(p,y), and Equation (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, its cross-packet shift is

There is no quadratic term because \Omega(p,p)=0. On the right of Equation (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-coefficient of X_y in the identity gives equality of the two finite sets of jump tuples with exactly these energies. Match them by rank. Restoring the fixed underlying packet energies adds the same integer to both sides.

The bijection is now explicit in either direction. From the left of Equation (6.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. Conversely, from the right, open the negative packets, retain the positive packets, invert the jump-tuple bijection, and close the positive packets into states in II. Invariant packet types ensure that the same underlying data and rank sets are used on reversal. All ranks are finite by Lemma 6.1. Finally, if \Omega(p,y)=0, every monomial on the line y+\Z p commutes with g_p, so its total transform has only the zero jump.□

Proof. In ordinary commuting variables z_1,\ldots,z_D, expand

The nonnegative integer a_{\boldsymbol k,\mu} is the number of ordered subsets of [D] of the specified sizes in which index i occurs \mu_i times. By Theorem 5.8, the incoming coordinates of P_{\boldsymbol k} are exactly these constants at x_\mu and zero elsewhere. A testing-chamber state therefore has one of these labels, and its total coefficient there is the constant a_{\boldsymbol k,\mu}.

The coefficient at the same pure label in H_- is also a_{\boldsymbol k,\mu}. Indeed the initial independent-set monomials have nonnegative vertex coordinates, so a tuple using a bridge cannot contribute to an exponent with every bridge coordinate zero. All remaining tuples use anchors, which are mutually independent and pair by zero. Their packet energies and cross-packet shifts are zero.

Here is a transport of the states, rather than just an equality of their number. Fix a generic all-negative rational covector h_-. Within a sufficiently small neighborhood of the testing direction V(x), move the terminal chamber to the chamber of h_-+tV(x) for large t. Only hyperplanes with \Omega(p,x)=0 can separate these two perturbations. Their packet switches have zero total jump by Proposition 6.2. Next follow h_-+tV(x) down to t=0. Every crossed positive root p has \Omega(p,x)>0, and the crossing is from positive to negative. At each crossing, the coefficient of X_x gains only nonnegative contributions from lower exponents, with its old coefficient retained by the zero jump. Its starting and ending coefficients are the same constant a_{\boldsymbol k,\mu}. Coefficientwise positivity forces every gain along this finite path to be zero.

It follows that, in Equation (6.5) for these product states at x, only the zero-total-jump part occurs at every wall. The switches consequently give bijections all the way to the literal anchor tuples in H_-. Reversing the selected path gives the inverse. All intermediate choices can be fixed by the rational ordering above; they may use the composition but add no total jump to the recorded history. The history determines its terminal testing chamber, so the inverse loses no data.□

Proof. Equation (6.9) identifies the history enumerator with [X_u]\Theta_{x_\mu}^{H_-}. By Equation (5.22), this coefficient is v^{-M}c_\mu(v^2), where c_\mu(q)\in\N[q] has degree at most M. Its allowed powers of v are therefore exactly among -M,-M+2,\ldots,M. Histories have nonnegative multiplicities, so none can occur at any other energy. Each of these finitely many energy slices is finite by Lemma 6.1; hence their union T_{x_\mu} is finite as well. Multiplication by v^M changes each history weight to q^{(E(t)+M)/2}, proving the assertion.□

Proof. Construct the bijections in decreasing order of |J|, breaking ties by the fixed subset order. For an exact-J input w, apply B_J. If its output (t,s) has exact mask J, stop. Otherwise put K=\mathcal Q(s)\supsetneq J, apply the already constructed inverse \Phi_K^{-1}, and apply B_J again. Repeat this instruction. For the inverse procedure start at an exact-J pair, apply B_J^{-1}, and, whenever the resulting word has exact mask K\supsetneq J, apply \Phi_K followed by B_J^{-1}. Thus every nested call involves a strictly larger mask.

To prove that the outer repetition terminates, fix its energy E. The required-J source is finite, and its target is finite by Lemma 6.1 (also by Proposition 6.5). On their disjoint union draw the matching given by B_J. On the vertices whose exact masks strictly contain J, draw a second matching, the disjoint union of the already defined \Phi_K for K\supsetneq J. Each vertex has one edge of the first matching, and either zero or one edge of the second. Distinct edges that happen to have the same endpoints are retained as distinct matching edges. Figure 2 illustrates the alternating path in their union.

An exact-J starting vertex is an endpoint of this finite graph. Its component is a path, not a cycle: all vertices have degree at most two, and a component containing a degree-one vertex cannot be a cycle. Following its alternating edges therefore never revisits a vertex and eventually reaches the other endpoint. A return edge of the second matching always lands at a source with a larger exact mask, where the first matching can be followed again. Consequently the other endpoint lies on the target side and has exact mask J. Reversing the same path is precisely the inverse procedure described above. Every edge preserves E, proving the claimed energy preservation as well as termination.□

Proof. For any padded partition \mu, exactly one word of multiplicities (\mu_1,\ldots,\mu_D) has no strict ascent: the weakly decreasing word. This remains true when parts of \mu repeat, since the anchor indices themselves are distinct labels. Consequently \Phi_{\varnothing} identifies the individual words of shape \mu with T_{x_\mu}. Energy preservation, Equation (6.12), and Equation (6.9) give

Multiply by v^M. The conversion q=v^2 is legitimate as a formal polynomial conversion by Proposition 6.5, including both its parity and its degree bounds. The coefficient identity of Proposition 2.3 now identifies the right side with [e_\mu]X_G(X;q). This proves the identity for each shape and hence Equation (6.14). The algorithms producing \Lambda_G(w) use only elementary packets and local wall jumps; the coefficient identity certifies their output.□

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 \Lambda_G:\mathcal A_G\to\{\lambda:\lambda\vdash n\} with

For \sigma\in D_G^0 define

By Lemma 2.1, reversal gives the required input to \Lambda_G and complements graph inversions. Lemma 2.5 then gives, for every \lambda,

Together with X_G=\chi_G, this proves Equation (1.2). Every coefficient is the generating polynomial of a finite set, so it belongs to \N[q]. All choices and all recursions are finite procedures for each input. For n=0, take the empty graph, the empty permutation and the empty partition.□