Lexical tableaux and quasisymmetric functions
John M. Campbell, Spencer Daugherty · 2025
Read Lexical tableaux and quasisymmetric functions by John M. Campbell, Spencer Daugherty (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00713.txt.
Introduction
John Campbell and Spencer Daugherty generalize a family of combinatorial tableaux. Standard immaculate tableaux of a given composition shape are known to match, in exact count, the set partitions of a number range into blocks, counted by Stirling numbers of the second kind. The authors define lexical tableaux, which replace block structure with cycle structure: standard lexical tableaux of the same shape now match permutations with a given number of disjoint cycles.
A row's reading word must be the lexicographically smallest among its own cyclic rotations, a rule that includes the weakly increasing words of the older theory. Lexical tableaux then define a pair of dual bases for the Hopf algebras of quasisymmetric and noncommutative symmetric functions. Expansions into monomial and fundamental bases, and their duals, follow through Kostka-like coefficients.
Catalog record
| CREATOR | John M. Campbell, Spencer Daugherty |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 129 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-00713
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lexical tableaux and quasisymmetric functions John M. Campbell, Spencer Daugherty Abstract . There is a natural bijection between standard immaculate tableaux of composition shape α ⊨ n \alpha\vDash n and length ℓ ( α ) = k \ell(\alpha)=k and the { n k } \left\{\begin{smallmatrix}n\\ k\end{smallmatrix}\right\} set-partitions of { 1 , 2 , … , n } \{1,2,\ldots,n\} into k k blocks, for the Stirling number { n k } \left\{\begin{smallmatrix}n\\ k\end{smallmatrix}\right\} of the second kind. We introduce a family of tableaux that we refer to as lexical tableaux that generalize immaculate tableaux in such a way that there is a bijection between standard lexical tableaux of shape α ⊨ n \alpha\vDash n and length ℓ ( α ) = k \ell(\alpha)=k and the [ n k ] \left[\begin{smallmatrix}n\\ k\end{smallmatrix}\right] permutations on { 1 , 2 , … , n } \{1,2,\ldots,n\} with k k disjoint cycles. In addition to the entries in the first column strictly increasing, the defining characteristic of lexical tableaux is that the word w w formed by the consecutive labels in any row is the lexicographically smallest out of all cyclic permutations of w w . This includes weakly increasing words, and thus lexical tableaux provide a natural generalization of immaculate tableaux. Extending this generalization, we introduce a pair of dual bases of the Hopf algebras QSym and NSym defined in terms of lexical tableaux. We present two expansions of these bases, involving the monomial and fundamental bases (or, dually, the ribbon and complete homogeneous bases), using Kostka coefficient analogues and coefficients derived from standard lexical tableaux. MSC: 05E05, 05E10 Keywords: tableau, quasisymmetric function, symmetric function, noncommutative symmetric function, symmetric group, tabloid, permutation, integer partition, integer composition, Hopf algebra, Young tableau, immaculate tableau 1. Introduction An integer partition is a weakly decreasing and finite tuple \lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell(\lambda)}) of positive integers, where |\lambda| denotes the sum of the parts of \lambda , and we write \lambda\vdash n if |\lambda|=n . Similarly, an integer composition \alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{\ell(\alpha)}) is a finite tuple of positive integers, where we write |\alpha| in place of the sum of the entries of \alpha , and we write \alpha\vDash n if |\alpha|=n . A tableau , for the purposes of this paper, may be understood as a two-dimensional arrangement of (labeled or unlabelled) cells that are positioned into left-justified rows, with the shape of a tableau T forming an integer composition \alpha such that the number of cells in the i^{\text{th}} row of T (from the bottom according to the so-called French convention) is equal to \alpha_{i} for i\in\{1,2,\ldots,\ell(\alpha)\} . Tableaux and tableaux-like objects are of fundamental importance in the representation theory of the symmetric group and many related areas of algebraic combinatorics. Young tableaux , in particular, are especially significant in the study of and application of symmetric group representations. A family of Young-like tableaux that arose in the construction of a noncommutative analogue of the Schur symmetric functions are the immaculate tableaux introduced in a seminal paper by Berg et al. [ 7 ] . Our explorations based on the combinatorics of immaculate tableaux have led us to generalize such tableaux via a family of tableaux that we refer to as lexical tableaux and that we apply to introduce new bases of the Hopf algebras QSym and NSym (reviewed in Section 2 below) of quasisymmetric functions and of noncommutative symmetric functions. One of the most significant results in the representation theory of the symmetric group is that the isomorphism classes of the simple \mathbb{C}S_{n} -modules are in bijection with partitions \lambda\vdash n , and, moreover, that the dimension and multiplicity of the irreducible \mathbb{C}S_{n} -module corresponding to \lambda is equal to the number f^{\lambda} of standard Young tableaux of shape \lambda . This raises questions as to how similar properties could be obtained with the use of composition tableaux in place of partition tableaux, and immaculate tableaux can be thought of as arising in this way. The interest in the study of combinatorial properties associated with standard immaculate tableaux is evidenced by Gao and Yang’s bijective proof of the hook-length formula for standard immaculate tableaux [ 14 ] together with Sun and Hu’s probabilistic method for determining the number of standard immaculate tableaux of a given shape [ 26 ] . Since evaluations of finite summations involving f^{\lambda} often arise in the context of applications of Young tableaux, this raises questions as to what would be appropriate as analogues of such evaluations involving standard immaculate tableaux, letting g^{\alpha} denote the number of standard immaculate tableaux (reviewed in Section 2 below) of a composition shape \alpha . In this direction, the summation (1) \sum_{\begin{subarray}{c}\lambda\vdash n\\ \ell(\lambda)=k\end{subarray}}f^{\lambda}=\text{$\#$ of Young tableaux with $n$ cells and $k$ rows}, which gives rise to a number triangle indexed in the Online Encyclopedia of Integer Sequences as A047884 , has led us to experimentally discover, using the OEIS, a property (given in Theorem 3.1 below) concerning a corresponding sum for immaculate tableaux given by replacing f^{\lambda} with g^{\alpha} and summing over compositions \alpha\vDash n of a fixed length k . This, in turn, has led us to construct a new family of immaculate-like tableaux. Given a construction involving all possible permutations of a set of objects, it is natural to consider a corresponding construction whereby the permutations involved are required to be cyclic. For example, the abelian complexity function on infinite words counts subwords up to all possible permutations of characters, whereas the cyclic complexity function introduced in 2017 [ 11 ] counts subwords up to cyclic permutations of characters. The way our definition of a lexical tableau, as given in Section 3 below, relates to that of an immaculate tableau may be seen by analogy with how the definition of a cyclic complexity function relates to that of an abelian complexity function. Similarly, the way the cyclic quasisymmetric functions introduced by Adin et al. [ 1 ] are defined via an invariance property associated with cyclic permutations, relative to the corresponding invariance property for symmetric functions holding for all possible permutations, further illustrates how the definition of a lexical tableau provides a natural generalization of immaculate tableaux. Indeed, our construction of lexical tableaux makes use of cyclic shifts by direct analogy with the work of Adin et al. [ 1 ] . As the term lexical tableau suggests, there is a close connection between the study of such tableau and the field combinatorics on words. Given a property associated with Schur or immaculate functions, by deriving an analogous identity using lexical tableaux, this, ideally, could help to shed light on the use of new methods that could be applied toward unsolved problems related to the Schur and immaculate bases and representation-theoretic uses of these bases. The problem of extending immaculate and dual immaculate functions using the combinatorial objects involved in the construction of \{\mathfrak{S}_{\alpha}\}_{\alpha} and its dual is motivated by much in the way of past research on immaculate and dual immaculate functions, including research on the indecomposable modules for the dual immaculate basis [ 6 ] , Pieri rules for dual immaculate functions and generalizations [ 9 , 18 , 23 ] , multiplicative structures of the immaculate basis [ 8 , 18 ] , the