{'fraction_non_alphanumeric': 0.04897959183673469, 'fraction_numerical': 0.006019377447948876, 'mean_word_length': 3.9847924373201806, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Pattern groups and a poset based Hopf monoid

The supercharacter theory of algebra groups gave us a representation theoretic realization of the Hopf algebra of symmetric functions in noncommuting variables. The underlying representation theoretic framework comes equipped with two canonical bases, one of which was completely new in terms of symmetric functions. This paper simultaneously generalizes this Hopf structure by considering a larger class of groups while also restricting the representation theory to a more combinatorially tractable one. Using the normal lattice supercharacter theory of pattern groups, we not only gain a third canonical basis, but also are able to compute numerous structure constants in the corresponding Hopf monoid, including coproducts and antipodes for the new bases.


Introduction
A supercharacter theory of the unipotent upper-triangular matrices of the finite general linear groups gave a representation theoretic interpretation to the Hopf algebra of symmetric functions in non-commuting variables [1]. In fact, these supercharacter theories glue together most naturally as a Hopf monoid as described in [2], where we obtain the Hopf algebra as a quotient structure. They give a rich combinatorics on set partitions explored in [10,11,12]. However, the overall Hopf structure remains mysterious, especially with regard to the coproduct on the character basis. This paper explores a supercharacter theory that is simultaneously computable for a larger swath of groups (including in our case all pattern groups), and yet is more amenable to explicit computation of structure constants.
Formally introduced by Diaconis-Isaacs [13], a supercharacter theory can be thought of as an approximation to the usual character theory of a group. Given any set partition K of a group G, one can study the subspace of the space of functions f(G) = {ψ : G → C} that are constant on the parts of K. If this subspace additionally has a basis of orthogonal characters, then we say that the parts of K are the superclasses of a supercharacter theory. The interplay between the parts of K and the basis of characters (called supercharacters) mimic the interplay between conjugacy classes and irreducible characters. This point of view then gives a framework for studying the representation theory of coarser (and often more combinatorial) partitions of groups.
This paper uses a specific supercharacter theory introduced by Aliniaeifard [5] in his Ph.D. thesis work. It gives a general construction for arbitrary groups (though it prefers groups with nontrivial normal subgroups) that has many combinatorial properties baked in. The paper [6] explores some more combinatorial implications of such theories in general, giving lattice-based formulas for the supercharacter values and for the restriction of supercharacters. This paper applies these techniques to the case of pattern groups (which is in fact the original motivation for the work).
Pattern groups are a family of unipotent groups that are built out of finite posets, roughly a group version of an incidence algebra. While they were a fundamental example in [13], the supercharacter theory they give in that paper for pattern groups is not generally well understood. Andrews introduced a different supercharacter theory called a non-nesting supercharacter theory that has nice combinatorial properties [8]; in fact, [9] used this theory to study generalize Gelfand-Graev characters for the finite general linear groups. While his theory differs from ours, it is in fact morally equivalent. This paper explores a Hopf monoid first defined (up to moral equivalence) by Andrews; however, the Aliniaeifard supercharacter theory gives us some additional tools, including a third canonical basis and a restriction formula from [6]. These tools allow us to give more explicit structural results, including a coproduct on supercharacters and antipode formulas.
After reviewing some of the background material in Section 2, we apply the results of [6] to the pattern group case in Section 3. The main result of this section, Corollary 3.6, gives a combinatorial formula for restricting between pattern groups. Section 4 reviews the monoid constructed in [8] and examines the structure constants of various bases. Here we have a new third basis coming from the normal lattice supercharacter theory and Theorem 4.6 gives a formula for the coproduct on supercharacters. We then explore some of the structure of this monoid, establish an algebraically independent set of free generators (as a monoid), and construct the primitive elements in the style of [10]. Along the way, we also compute the antipode on several bases.

Preliminaries
This section reviews the necessary background on pattern groups, supercharacter theories, and distributive lattices. Throughout we will make use of different posets on an underlying set, so given a set A, let PO(A) = {partial orders on A}.

Pattern groups
Fix a finite field F q , a set A, and a poset R ∈ PO(A), let be the interval poset of R (ordered by inclusion). The corresponding pattern group is given by In the case where R is a linear order, we obtain the maximal group of upper triangular matrices in the finite general linear group with rows and columns indexed by R.
be the set of proper intervals. Since this paper is concerned with normal subgroups, we would like an easy characterization of when these subgroups UT O is in fact normal. Recall, that a co-ideal I in a poset R is a subset that satisfies K ∈ I implies L ∈ I for all L R K.
The converse follows easily from the definition of multiplication in a pattern group.
Remark. For each linearization L of R, there is a corresponding inclusion of UT R in the unipotent group UT L . However, some of these choices may lead to normal subgroups while others may not. For example, The left-hand inclusion is as a non-normal subgroup and the right-hand one is as a normal subgroup.
Given a poset R, the pattern group UT R generally has many normal subgroups, and in general it is not clear that it is possible to find them all. However, we are primarily interested in the subset of normal subgroups These subgroups are well-behaved in the sense that Thus, we obtain a poset with unique greatest lower bounds and smallest upper bounds. In Section 2.3, we will show that NPtt(R) in fact forms a distributive lattice.

Normal lattice supercharacter theories
Given a set partition K of G, let be the set of functions constant on the blocks of K.
A supercharacter theory S of a finite group G is a pair (Cl(S), Ch(S)) where Cl(S) is a set partition of G and Ch(S) is a set partition of the irreducible characters Irr(G) of G, such that We refer to the blocks of Cl(S) as the superclasses of S, and the elements of as supercharacters of S. In fact, the supercharacters of S will form an orthogonal basis for f(G; Cl(S)); thus, the superclasses are unions of conjugacy classes. In general, one only needs to specify one partition (Cl or Ch) since the two determine one-another. There are several standard supercharacter theories that get applied to pattern groups. Since a pattern group UT R is in fact an algebra group, [13] defines a supercharacter theory whose superclasses are the equivalence classes of the set partition However, it is not even known whether this theory is in general wild, and they certainly are not generally understood. Andrews [8] defines a more suitable theory which he calls a non-nesting supercharacter theory for UT R . Given u ∈ UT R , let N u be the smallest normal pattern subgroup containing u. Then the superclass containing u is This theory is very close to the supercharacter theory that this paper focuses on.
The following supercharacter theory defined in [5] begins with a set of normal subgroups and constructs a supercharacter theory that has these normal subgroups as unions of superclasses. [5]). Let N be a set of normal subgroups such that

Theorem 2.3 (Normal Lattice Supercharacter Theory
Then the partitions In the case of pattern subgroups, we let or the set of all normal pattern subgroups of UT R . In this case, from the definition of the superclasses it is not difficult to see that S NPtt(R) is a coarsening of Andrews' non-nesting theory. Write

Distributive lattices
In order to study normal lattice supercharacter theories we select lattices of normal pattern subgroups, and in our case they are in fact distributive lattices. In a poset L, a cover L ∈ L of an element K ∈ L is an element that satisfies K ≺ L L and if K ≺ L M L L then L = M . Let is the set of meet irreducible elements, then for each K ∈ L there exists a unique anti-chain A ⊆ M such that K is the unique largest element in L smaller than all elements in A. In this case, we write L = J ∨ (M).
In fact, this is equivalent to if is the set of join irreducible elements, then for each K ∈ L there exists a unique anti-chain A ⊆ J such that K is the unique smallest element in L bigger than all elements in A. In this case we write, L = J(J ).

Lemma 2.4. For each poset R, the poset NPtt(R) is a distributive lattice.
Proof. Let R be a poset. Each subposet Q such that UT Q ⊳ UT R corresponds to a co-ideal Int(Q) in Int(R). A cover of UT Q then corresponds to adding a maximal element in Int Thus the the set of meet irreducible elements is That is, each element in M corresponds to a principal ideal in Int By the previous lemma, for each UT Q ⊳ UT R , there is a unique anti-chain A ⊆ M such that Remark. The join irreducibles are also easily computed. By removing any minimal element in Int • (Q), we get a normal subgroup that has UT Q as a cover. Thus, That is, each element in M corresponds to a principal co-ideal in Int • (R).

The poset partition combinatorics of a normal lattice theory
This section applies [6] to the particular case of the normal lattice theory built on normal pattern subgroups. We first review the poset combinatorics introduced in [8] and connect it to the normal pattern subgroup lattice NPtt(R). We review the character formula of this theory from the point of view introduced in [6], and conclude with a combinatorial description of restriction between pattern groups.

Poset partitions
Fix a set A, and let R ∈ PO(A). An R-partition is a subset We may visualize these partitions by placing the Hasse diagram of R as the base, and then place an arc from i to j if [i, j] ∈ λ. For example, [4,5], [3,5] Note that if L is a linear order, then the transitive closure of the relation i ∼ λ j if [i, j] ∈ λ gives a set partition of the underlying set. Given a poset P, let Anti(P) = {λ ⊆ P | λ is an antichain}.
For example, is a bijection.
is a bijection.
(c) For UT R with normal pattern group sub-lattice, the superclasses and supercharacters are indexed by pp nn (R).
Remark. The functions in (a) and (b) do not invert one-another. However, they are both representation theoretically useful. Thus for λ ∈ pp nn (R), let In other words, in the first case, λ specifies the minimal elements in co-ideal of Int • (R), and in the second λ specifies the maximal elements not in the co-ideal of Int • (R).

Example 3.2.
When R ∈ PO(B) is a total order, then |pp nn (R)| is the |B|th Catalan number.
In fact, if we view UT R as upper-triangular matrices, then there is a natural Dyck path for each normal subgroup. If we let * indicate entries that may be nonzero, one such subgroup might be The set partitions λ and µ capture aspects of the Dyck path. That is, λ gives the coordinates of the peaks, so in the example λ = { [2,4], [4,7], [7,8]} (where we omit peaks with trivial coordinates), and µ gives the coordinates of the valleys, so µ = { [1,2], [3,5], [6,8]}.

The supercharacters of UT R
By Theorem 2.3, NPtt(R) corresponds to a normal lattice supercharacter theory S R = S NPtt(R) . By Proposition 3.1, we have that Cl and Ch are indexed by pp nn (R). However, we do this indexing slightly asymmetrically using Proposition 3.1 (a) and (b) for combinatorial reasons. Let λ, µ ∈ pp nn (R). For superclasses, let UT µ • be the superclass corresponding to µ, and for supercharacters, let These different choices make the computation of relevant statistics more straight-forward; for UT λ , the poset partition λ identifies the covers of UT λ and for UT µ • , the poset partition µ gives the entries required to be nonzero to be found in that superclass (or the subgroups that UT µ covers). In more detail, Applying [6,Corollary 3.4], we obtain the following character formula.
Remark. This is very close to a character formula given by [8] for his non-nesting supercharacter theories for pattern groups. In fact, one may obtain the normal lattice theory supercharacter theory from Andrews' theory be conjugating the superclasses by diagonal matrices.

A restriction formula
One motivation of this paper is to sort out the implications of the restriction rule in [6] for pattern groups. Let H ⊆ G be a subgroup and suppose we have sublattices of normal subgroups J ∨ (M G ) and In our case, all pattern subgroup containments turn out to be restriction favorable. Proof. Let M R = M UT R and M Q = M UT Q be the respective meet irreducible elements. Given UT P ∈ NPtt(R), we have that UT P ∩ UT Q ⊳ UT Q by the diamond isomorphism theorem, and since UT P ∩ UT Q = UT P∩Q it is also a pattern subgroup. We can conclude that the function · ∩ UT Q is well-defined, giving us (R1 For λ ∈ pp nn (R), let We can now apply Theorem 3.4 to our situation.
Proof. We may re-write

A Hopf monoid
The goal of this section is to revisit a Hopf monoid defined in [8] built out of the representation theory of pattern groups. For a more detailed background on Hopf monoids, we recommend [4]. While there has been more literature on Hopf algebras, it appears that Hopf monoids seem to be especially well-suited to the representation theory of unipotent groups [2]. As it happens, we can easily recover a corresponding Hopf algebra as a quotient, but the monoid structure allows easier computations than in the Hopf algebra. We begin with the definition of the main Hopf monoid ptt NPtt , and then give the structure constants on the main bases. We then show that ptt NPtt is free as a monoid, and compute the antipode on several of our favorite bases. We conclude with a construction of the primitive elements.

The pattern group Hopf monoid
Define a vector species ptt : {sets} → {F q -modules} by There is a corresponding projection π A,B : UT P.Q → UT P × UT Q given by Given P ∈ PO(C) and A ⊆ C, the restriction P| A ∈ PO(A) of P to A is given by There is a corresponding injective function ι A,B : UT P| A × UT P| B → UT P given by These constructions give us a product and coproduct on ptt via where these again give us the functors of inflation and restriction, respectively. As shown in [8], these functions are compatible and give us a Hopf monoid. Furthermore, every supercharacter theory on pattern groups that are compatible with inflation and restriction give us a sub Hopf monoid. Our focus for the rest of the paper will be on the sub Hopf monoid ptt NPtt : {sets} → {F q -spaces} given by where Cl(R) is the superclass partition given in (2.4).

Some related monoids
We already have that ptt NPtt ⊆ ptt as Hopf monoids. In fact, by varying the underlying supercharacter theory, we obtain various additional monoids (assuming these new supercharacter theories are compatible with restriction and inflation). In particular, ptt NPtt is contained in Andrews' Hopf monoid which is itself a sub Hopf monoid of the monoid corresponding to the usual algebra group supercharacter theory (2.3). However, this latter theory remains relatively mysterious for general pattern groups. Another approach is to find submonoids in ptt NPtt . For example, if then ptt PO is isomorphic to the usual Hopf monoid on posets. Given a poset R ∈ PO(A), recall that the width wdth(R) of R is the size of the maximal anti-chain. For w ∈ Z ≥1 , let Then it follows from the general product and coproduct definitions that ptt (w) NPtt is a sub Hopf monoid of ptt NPtt . In fact, ptt (1) NPtt is a subset of the Hopf monoid scf (U ) in [2] that gives the Hopf algebra SC isomorphic to the Hopf algebra of symmetric functions in noncommuting variables NCSym [1]. In fact, if Sym is the Hopf algebra of symmetric functions in commuting variables, then there is a functor π : scf (U ) → SC(U ) and an isomorphism ch : SC → NCSym (sending superclass identifier functions to monomial symmetric functions) and a surjective homomorphism rlx : NCSym → Sym (allowing variables to commute). In other words, we have where NCSym nn = ch • π(ptt (1) NPtt ). In [16], the authors define the Catalan quasi-symmetric Hopf algebra CQSym in which each degree has dimension C n , the nth Catalan number. In the last section we show that NCSym nn is isomorphic to CQSym.

Standard bases
As a supercharacter theory, S R equips f(UT R ; Cl(R)) with two natural bases is the superclass indicator function, and χ λ is the supercharacter as in (3.3). These two bases are orthogonal with respect to the usual inner product As a normal lattice supercharacter theory, we obtain a third canonical basis We might also be tempted by the dual construction giving the normal subgroup indicator functions However, as the character of the permutation module Ind UT R UT λ (1 1), so up to scaling these are in fact the same basis. Neither version is orthogonal, and we have However, they give a upper/lower triangular decomposition of the supercharacter table of UT R (similar to the situation in [11] for the full upper-triangulars). By keeping track of the corresponding diagonal entries, we obtain a formula for the determinant of the supercharacter table.
For these bases we can compute the structure constants as follows. First the superclass indicators give

Lemma 4.4. Let A, B be sets with
Proof. (a) For u ∈ UT R.Q ,  (a) For R ∈ PO(A), Q ∈ PO(B), λ ∈ pp nn (R) and ν ∈ pp nn (Q), Proof. (a) For u ∈ UT λ∪ν , Here there is a less direct combinatorial description, but the result follows from Lemma 4.4 (b).
Somewhat surprisingly, we can also compute the structure constants for the supercharacter basis. (a) For R ∈ PO(A), Q ∈ PO(B), λ ∈ pp nn (R) and ν ∈ pp nn (Q), Proof. (a) follows from a similar argument in [8] and (b) follows directly from Corollary 3.6 with Lemma 3.7.

Freeness
The first goal of this section is to show that ptt NPtt is a free monoid. Recall that a set composition (B 1 , . . . , B ℓ ) B of a set B is a sequence of nonempty sets (B 1 , . . . , B ℓ ) such that {B 1 , . . . , B ℓ } is a set partition of B. For a set B, P, Q ∈ PO(B) with UT Q ⊳ UT P , we say the pair (P, Q) factors if there exists a nonempty, proper subset A ⊆ B such that If no such subset exists, we say the pair (P, Q) is atomic.
In general, for a pair (P, Q) there exists a set composition (B 1 , . . . , B ℓ ) B such that for each 1 ≤ j ≤ ℓ, (P| B j , Q| B j ) is atomic and where we consider the pairs (R, Q) formally linearly independent. We upgrade this vector species into a free connected Hopf monoid Tppst : {sets} → {C-modules} by where each (A 1 , . . . , A ℓ ) A is a set composition of A. The product in Tppst is concatenation of tensors, and for nonintersecting sets A and B and (P, Q) ∈ ppst[A ∪ B], That is, (P, Q) are primitive.
Extend the function where (B 1 , . . . , B ℓ ) is the set composition coming from the unique decomposition (4.1). We have proven the following proposition.  Note that this formula does not depend on the ambient subgroup UT R in which UT Q is normal. In fact, we obtain some cancellation. The following result is similar to the power-sum result in [10].

Antipodes
Proof. Suppose Fac Q (P) = ∅. Let I ∈ Fac Q (P). If there exists I j ∈ I such that Fac Q| I j (P| I j ) = ∅, we may replace I j by any element of Fac Q| I j (P| I j ). If we continue in this way until no part splits further we obtain an element L = (L 1 , . . . , L ℓ ) ∈ Fac Q (P), so where µ is the Möbius function. This is nonzero exactly when M = L.
We also obtain a formula for the supercharacter basis. For R ∈ PO(B), λ ∈ pp nn (R) and a set composition A = (A 1 , . . . , A ℓ ) B, let Note that by Corollary 3.6 and Lemma 3.7 we have that if ν / ∈ Int λ For λ ∈ pp nn (R), a R-factorization (I 1 , . . . , I ℓ ) ∈ Fac R (P) has a λ-neutral cut if there exists 1 ≤ j ≤ ℓ − 1 such that We say Fac R (P) is λ-atomic if it is nonempty and the longest element has no λ-neutral cuts.
Theorem 4.9. For R ∈ PO(B), and λ ∈ pp nn (R), Furthermore, as polynomials in q, the coefficients are nonzero (though they may have integral roots).
Remark. An example that shows the coefficients can be zero is as follows. The coefficient of , which is generically nonzero, but zero if q = 2. However, if q is sufficiently large the coefficients are always nonzero.
Proof. By Takeuchi's formula and Lemma 3.7, an anti-chain Fix ν ∈ Res λ and P ∈ PO(B) such that Fac R (P) = ∅ and ν ∈ pp nn (P). Then the coefficient of χ ν in S(χ λ ) is Let L ∈ Fac R (P) be the longest element. If L has a λ-neutral cut, then P can be split into Thus, the bijection is sign reversing and the coefficient is zero if Fac R (P) is not λ-atomic. Suppose Fac R (P) is λ-atomic. If there exists I ∈ Fac R (P) such that ν I = ν and λ I = λ ∩ ν, then there exists a unique longest such element L. Then Since L has no λ-neutral cuts, any set composition in I ∈ Fac R (P) such that I = L will add elements in UT R| I that are not in UT λ ∩ UT R| I . Thus, Since all the quotients are powers of q, there exists k ∈ Z ≥0 and c l ∈ Z such that Generically this polynomial is nonzero, though for specific values of q it could have a root.
We can apply the theorem to the specific case of trivial characters to get a pleasing result. For P ∈ PO(B) let ∅ P = ∅ ∈ pp nn (P). Proof. Since UT ∅ R = UT R , we have that UT ∅ R ∩ UT R| A = UT R| A for all A B. Thus, if Fac R (P) is ∅ R -atomic, then for the longest element L = (L 1 , . . . , L ℓ ) ∈ Fac R (P) we must have that for each 1 ≤ j ≤ ℓ − 1 at least one maximal elements of L j is greater in R than a minimal element in L j+1 . Thus, L is also the minimal element in Fac R (P). The other elements of the formula reduce in a straightforward way.

Primitives
In [3], the authors indicate how to find the dimension of the lie algebra of primitive elements of a (co)free Hopf monoid in each degree. For ptt NPtt we go one step forward and give a full system of algebraic independent primitive elements. Fix a ∈ A. For Q atomic, define  If we put an ordering on PO(A) by Q R if |UT Q | ≤ |UT R |. Since Fac Q (R) = ∅ implies R has at least as many relations as Q, it also implies that |UT Q | ≤ |UT R | with equality only when Q = R. Thus, S UT Q are triangular in the δ UT R basis, with leading term the algebraically independent elements δ UT Q . Conversely, given R ∈ PO(A), there exists a factorization into atomics Thus, the S (a) UT Q generate a basis of ptt NPtt and are a full set of algebraically independent projective elements.
In [16], Novelli-Thibon define a graded Hopf algebra CQSym = n≥0 CQSym n with dim(CQSym n ) equal to the nth Catalan number C n . In the case of this paper they index a basis in each graded dimension by non-decreasing parking functions, which are easily seen to be in bijection with non-crossing partitions (which in turn are in bijection with non-nesting partitions). They also prove that CQSym is free over a set of primitive generators indexed by connected parking functions (parking functions that cannot be written as a shifted concatenation of two other parking functions). For degree n, these are enumerated by n j=2 C j−2 C n−j = C n−1 . Proof. We have that each algebra is free under the product of primitive (atomic) generators. The number of primitive generators in degree n for NCSym nn is the number of non-nesting partitions that that are not the concatenation of two other nontrivial non-nesting partitions. However, a non-nesting partition is atomic if and only if the corresponding non-crossing partition (the unique partition that has the same left and right endpoints) is atomic. The number of atomic non-crossing partitions of {1, 2, . . . , n} is n j=2 C j−2 C n−j = C n−1 .
Thus, the two Hopf algebras must be isomorphic.