# Koszulity, supersolvability and Stirling Representations

Ayah Almousa  ,  Victor Reiner  and  Sheila Sundaram  University of Minnesota
- Twin Cities, Minneapolis MN 55455<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Supersolvable hyperplane arrangements and matroids are known to give rise to
certain Koszul algebras, namely their Orlik-Solomon algebras and graded
Varchenko-Gel’fand algebras. We explore how this interacts with group actions,
particularly for the braid arrangement and the action of the symmetric group,
where the Hilbert functions of the algebras and their Koszul duals are given
by Stirling numbers of the first and second kinds, respectively. The
corresponding symmetric group representations exhibit branching rules that
interpret Stirling number recurrences, which are shown to apply to all
supersolvable arrangements. They also enjoy representation stability
properties that follow from Koszul duality.

###### Key words and phrases:

Stirling number, Koszul algebra, Orlik-Solomon, Varchenko-Gelfand, quadratic
algebra, Groebner basis, branching, holonomy Lie algebra, Drinfeld-Kohno,
infinitesimal braid, chord diagrams

###### 2020 Mathematics Subject Classification:

16S37, 05B35

###### Contents

  1. 1 Introduction
  2. 2 Koszul algebras
  3. 3 Review of noncommutative, commutative, exterior Gröbner bases
  4. 4 Matroids, oriented matroids, and supersolvability
  5. 5 Orlik-Solomon and Varchenko-Gel’fand rings
  6. 6 Examples: Boolean matroids and matroids of low rank
  7. 7 Branching rules for supersolvable matroids
  8. 8 Homotopy and holonomy Lie algebras
  9. 9 Topological interpretations of $\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ and Koszul duality
  10. 10 Representation stability and Koszul algebras
  11. 11 The motivating example: braid matroids and Stirling representations
  12. 12 Further remarks and questions
  13. A Tables of characters for Stirling representations
  14. References

##  1\. Introduction

This paper was motivated by a connection between Stirling numbers and Koszul
algebras. The (signless) Stirling numbers of the first kind $c(n,k)$ and
Stirling numbers of the second kind $S(n,k)$ are centuries-old answers to
certain counting problems: $c(n,k)$ is the number of permutations
$\\{1,2,\ldots,n\\}$ with $k$ cycles, while $S(n,k)$ is the number of set
partitions of $\\{1,2,\ldots,n\\}$ with $k$ blocks. On the other hand, Koszul
algebras $A$ and their Koszul dual algebras $A^{!}$ originated in work of
Priddy [Priddy] and Fröberg [Froberg-original] in the 1970s, playing an
important role in topology, and in homological and commutative algebra.

The connection stems from a particular Koszul dual pair of graded
$\mathbf{k}$-algebras $A=\bigoplus_{d=0}^{\infty}A_{d}$ and
$A^{!}=\bigoplus_{d=0}^{\infty}A^{!}_{d}$, described later, carrying actions
of the symmetric group $\mathfrak{S}_{n}$. Their Hilbert series

$\displaystyle\operatorname{Hilb}(A,t):=\sum_{d=0}^{\infty}\dim_{\mathbf{k}}A_{d}t^{d}$
$\displaystyle=(1+t)(1+2t)\cdots(1+(n-1)t)$ (1)
$\displaystyle=\sum_{k=0}^{n-1}c(n,n-k)t^{k},$ (2)
$\displaystyle\operatorname{Hilb}(A^{!},t):=\sum_{d=0}^{\infty}\dim_{\mathbf{k}}A^{!}_{d}\,t^{d}$
$\displaystyle=\frac{1}{(1-t)(1-2t)\cdots(1-(n-1)t)}$ (3)
$\displaystyle=\sum_{k=0}^{\infty}S((n-1)+k,n-1)\,t^{k}$ (4)

re-interpret the Stirling numbers $c(n,k),S(n,k)$.

In fact, there are two different well-studied algebras $A$ that can play the
role of the algebra $A$ above: the Orlik-Solomon algebra
$\mathrm{OS}(\operatorname{Br}_{n})$, or the graded Varchenko-Gel’fand algebra
$\mathrm{VG}(\operatorname{Br}_{n})$, associated to the matroid and oriented
matroid $\operatorname{Br}_{n}$ for the braid arrangement on $n$ strands, also
known as the type $A$ reflection hyperplane arrangement, or the graphic
arrangement associated to the complete graph on $n$ vertices. A great deal is
known about the $\mathfrak{S}_{n}$-representations on the graded components
$A_{d}$ for either one of these algebras
$A=\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$, due to their importance in the
topology of configuration spaces and in combinatorics. Their Koszul duals
$A^{!}$ have seen less study from a combinatorial representation theory
viewpoint, and were our original main interest.

A natural framework here turns out to be the combinatorial notion of
supersolvability. Well-known results show that the algebras
$A=\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ for supersolvable matroids $M$ and
oriented matroids $\mathcal{M}$ have quadratic Gröbner basis presentations,
which then implies their Koszulity.

Sections 2, 3, 4 give background for this story. Section 2 is mainly a review
of basic theory of Koszul algebras carrying group actions, although it
contains one new observation on branching rules (Proposition 2.16). Section 3
recalls notions from noncommutative Gröbner bases, along with special features
of commutative or anti-commutative rings, connecting quadratic Gröbner bases
with Koszulity. Section 4 reviews matroids, oriented matroids and the notion
of supersolvability.

Section 5 starts with a review of the well-studied anti-commutative Orlik-
Solmon algebras $\mathrm{OS}(M)$ and their not quite as well-studied
commutative counterparts, the graded Varchenko-Gel’fand rings
$\mathrm{VG}(\mathcal{M})$. After recalling why both
$A=\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ are Koszul algebras whenever
$M,\mathcal{M}$ are supersolvable, the first main result, Theorem 5.18, gives
an explicit (noncommutative) quadratic Gröbner basis presentation for their
Koszul duals $A^{!}$. In the case of $A=\mathrm{OS}(M)$, the presentation for
$A^{!}$ is consistent with Kohno’s presentation [kohno1983holonomy, Kohno] of
the holonomy Lie algebra for the cohomology of the complement of a complex
hyperplane arrangement; in the case of $A=\mathrm{VG}(\mathcal{M})$, the
presentation for $A^{!}$ appears to be new. An application of the
presentation, Corollary 5.22, gives a Koszul dual analogue of the fact that
multiplication by the sum of the variables $\sum_{i}x_{i}$ endows
$A=\mathrm{OS}(M)$ with an (equivariant) exact chain complex structure: in the
supersolvable case, right-multiplication by the sum of the dual variables
$\sum_{i}y_{i}$ within $A^{!}=\mathrm{OS}(M)^{!}$ gives an (equivariant)
injective self-map of degree one.

Section 6 pauses to illustrate the foregoing theory on simple examples of
supersolvable matroids, such as Boolean matroids and rank two matroids,
including discussion of equivariant structure.

Section 7 proves the next main result, Theorem 7.1 giving branching rules for
$A=\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ and their Koszul duals $A^{!}$, in
the form of short exact sequences that apply whenever $M,\mathcal{M}$ are
supersolvable. For braid matroids $\operatorname{Br}_{n}$, these short exact
sequences re-interpret the two classical Stirling number recurrences:

$\displaystyle c(n,k)$ $\displaystyle=(n-1)\cdot c(n-1,k)+c(n-1,k-1),$ (5)
$\displaystyle S(n,k)$ $\displaystyle=k\cdot S(n-1,k)+S(n-1,k-1).$

Sections 8, 9, and 10 review more general theory of Koszul algebras $A$,
particularly when $A$ is either anti-commutative (like $\mathrm{OS}(M)$) or
commutative (like $\mathrm{VG}(\mathcal{M})$). Sections 8 recalls why the
Koszul dual $A^{!}$ is the universal enveloping algebra for its Lie
(super-)algebra of primitive elements, also known as its homotopy Lie algebra,
and why the latter coincides in this setting with its own linear strand, the
holonomy Lie algebra. The Poincaré-Birkhoff-Witt Theorem for universal
enveloping algebras then leads to equivariant versions of results such as the
lower central series formula in the anti-commutative case, and the theory of
acyclic closures and deviations in the commutative case. Section 9 briefly
reviews the topological interpretations of Koszul duality, and the
interpretation of $\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ in terms of the
cohomology of complements of subspace arrangements. Section 10 reviews Church
and Farb’s notion of representation stability for
$\mathfrak{S}_{n}$-representations [ChurchFarb]. It then proves two results on
its interaction with Koszul duality (Corollaries 10.6, 10.10) showing that
after fixing $d$, representation stability for the $d^{th}$ graded components
$\\{A_{d}(n)\\}_{n\geq 1}$ in a family of Koszul algebras implies the
analogous representation stability for their Koszul duals
$\\{A^{!}_{d}(n)\\}_{n\geq 1}$, along with a similar statement for their
holonomy Lie algebras.

Finally, Section 11 returns to the motivating example of the braid arrangement
matroids $\operatorname{Br}_{n}$, examining the consequences of all the
previous results for
$\mathrm{OS}(\operatorname{Br}_{n}),\mathrm{VG}(\operatorname{Br}_{n})$,
including the aforementioned branching rules re-interpreting the Stirling
number recurrences, Corollary 11.5. One surprise here is Theorem 11.15, on the
prevalence of permutation representations of $\mathfrak{S}_{n}$ among the
homogeneous components $A^{!}_{i}$ of the Koszul dual $A^{!}$ when
$A=\mathrm{OS}(\operatorname{Br}_{n})$.

Section 12 collects some further remarks and questions. Appendix A includes
tables of data for the characters of the Stirling representations of the first
and second kind for $\mathrm{OS}(\operatorname{Br}_{n})$ and
$\mathrm{VG}(\operatorname{Br}_{n})$ and the primitives of their corresponding
holonomy Lie algebras. In addition, the code at
[Almousa_StirlingRepresentations_2024] can also be used to generate more data.

### Summary of main results

For the ease of the reader, we summarize below the main results and their
applications to the type $A$ braid arrangement $\operatorname{Br}_{n}$.

  * •

Theorem 5.18 provides an explicit noncommutative Gröbner basis for Koszul
duals of Orlik-Solomon and Varchenko-Gel’fand rings of supersolvable matroids.

    * –

The discussion following Remark 11.2 explains the bijection between standard
monomials for $\mathrm{OS}(\operatorname{Br}_{n})$ and
$\mathrm{VG}(\operatorname{Br}_{n})$ and restricted growth functions.

  * •

5.22 shows that for a supersolvable matroid $M$ or oriented matroid
$\mathcal{M}$, right-multiplication by the sum of the dual variables
$\sum_{i}y_{i}$ in $A^{!}=\mathrm{OS}(M)^{!}$ gives a degree one injective
self-map, and the sum of the squares of the dual variables $\sum_{i}y_{i}^{2}$
in $A^{!}=\mathrm{VG}(\mathcal{M})^{!}$ gives a degree two injective self-map.
These maps are equivariant with respect to any group $G$ of automorphisms of
$M,\mathcal{M}$.

    * –

We conjecture the existence of $\mathfrak{S}_{n}$-equivariant degree one
injective self-maps for $\mathrm{VG}(\operatorname{Br}_{n})$ in 12.3.

  * •

2.16 shows that the graded pieces of an equivariant Koszul algebra $A$ satisfy
branching rules of a certain form if and only if the corresponding graded
pieces for $A^{!}$ do. Theorem 7.1 gives short exact sequences for
$\mathrm{OS}(M)$, $\mathrm{VG}(\mathcal{M})$ and their Koszul duals that lift
such branching rules whenever one has supersolvable matroids.

    * –

11.5 gives these branching rules for the Stirling representations, which lift
the classical Stirling number recurrences (5).

  * •

Theorem 8.6 gives a presentation for the holonomy Lie algebra of
$\mathrm{VG}(\mathcal{M})$ for an arbitrary oriented matroid $\mathcal{M}$. In
the supersolvable case, this presentation is consistent with the Gröbner basis
for $\mathrm{VG}(\mathcal{M})^{!}$ from Theorem 5.18.

  * •

10.6 shows that if a family of Koszul algebras $A(n)$ with actions by
$\mathfrak{S}_{n}$ are representation stable, then so are their Koszul duals.

    * –

11.9 applies this to show representation stability for
$\mathrm{OS}(\operatorname{Br}_{n})^{!}$ and
$\mathrm{VG}(\operatorname{Br}_{n})^{!}$. 11.11 conjectures that the bounds
for the onset of stability given in 11.9 are tight.

  * •

10.10 shows families of representation stable commutative or anti-commutative
Koszul algebras $A(n)$ pass this representation stability to their holonomy
Lie algebras $\mathcal{L}(n)$.

    * –

11.12 states that this holds for the holonomy Lie algebras of
$\mathrm{OS}(\operatorname{Br}_{n})$ and $\mathrm{VG}(\operatorname{Br}_{n})$.
In 11.14, we conjecture that the onset of stability is at $2i$ for high enough
$i$.

  * •

Theorem 11.15 summarizes several cases where
$[\mathrm{OS}(\operatorname{Br}_{n})_{i}^{!}]$ are permutation
representations.

##  2\. Koszul algebras

We review here the definitions and properties of Koszul algebras. Useful
surveys and references are Berglund [Berglund], Faber et al [Faber]*§2,
Fröberg [Froberg-survey], McCullough and Peeva [mcculloughPeevaSurvey]*§ 8,
Polishchuk and Positselski [PolishchukPositselski], and Priddy [Priddy].

###  2.1. Standard graded algebras and Koszul algebras

Fix a field $\mathbf{k}$ throughout this discussion.

######  Definition 2.1.

(Standard graded $\mathbf{k}$-algebras) For $V$ a $\mathbf{k}$-vector space
with $\mathbf{k}$-basis $x_{1},\ldots,x_{n}$, let

$T^{i}(V):=V^{\otimes i}:=\underbrace{V\otimes\cdots\otimes V}_{i\text{ tensor
factors}},$

and define the tensor algebra
$T_{\mathbf{k}}(V)=\bigoplus_{i=0}^{\infty}T^{i}(V),$ with concatenation
product. We identify it with

$T_{\mathbf{k}}(V)\cong\mathbf{k}\langle x_{1},\ldots,x_{n}\rangle,$

the free associative $\mathbf{k}$-algebra on $n$ letters. It is a graded
$\mathbf{k}$-algebra, in which $T^{i}(V)$ is the $i^{th}$ homogeneous
component, and is generated as an algebra in degree $1$ by $V$, the span of
$x_{1},\ldots,x_{n}$.

A standard graded (associative) $\mathbf{k}$-algebra is a graded quotient ring
$A$ of $T_{\mathbf{k}}(V)$, that is,

$A=T_{\mathbf{k}}(V)/I$ (6)

for some two-sided ideal $I\subset T_{\mathbf{k}}(V)$ which is homogeneous:
$I=\bigoplus_{i=0}^{\infty}I_{i}$ where $I_{i}:=I\cap T^{i}(V)$. We will
generally assume that the images of $x_{1},\ldots,x_{n}$ within $A$ (which we
still denote $x_{1},\ldots,x_{n}$, abusing notation) are minimal generators
for $A$ as a $\mathbf{k}$-algebra, or equivalently, that $I=I_{2}\oplus
I_{3}\oplus\cdots$.

######  Definition 2.2.

(Koszul algebras) Given a standard graded $\mathbf{k}$-algebra $A$, let
$A_{+}:=\bigoplus_{i=1}^{\infty}A_{i}$, and regard the field
$\mathbf{k}=A/A_{+}$ as the trivial (graded, left-)$A$-module, generated in
degree $0$.

Call $A$ a Koszul algebra if the surjection
$A\twoheadrightarrow\mathbf{k}=A/A_{+}$ can be extended as the first step in a
graded resolution of $\mathbf{k}$ by free left $A$-modules, which is linear in
the sense that it has this form:

$\begin{array}[]{ccrcccccccl}0\longleftarrow&\mathbf{k}&{\longleftarrow}&F_{0}&\overset{d_{1}}{\longleftarrow}&F_{1}&\overset{d_{2}}{\longleftarrow}&F_{2}&\overset{d_{3}}{\longleftarrow}&F_{3}&\leftarrow\cdots\\\
&&&\|&&\|&&\|&&\|&\\\
&&&A&&A(-1)^{\beta_{1}}&&A(-2)^{\beta_{2}}&&A(-3)^{\beta_{3}}&\\\ \end{array}$
(7)

Here $F_{i}=A(-i)^{\beta_{i}}$ is a graded free left $A$-module of rank
$\beta_{i}$, all of whose $A$-basis elements have been shifted to degree $i$,
that is $A(-i)_{j}:=A_{j-i}$. Linearity of the above resolution is equivalent
to saying that the matrices for the differentials $d_{i}:A_{i}\longrightarrow
A_{i-1}$ in the resolution have only linear (degree one) entries, that is, all
matrix entries lie in $A_{1}$.

Koszulity of $A$ has strong consequences for its algebra presentation, and for
the form of the resolution (7), related to the notion of quadratic algebras
and their quadratic duals.

######  Definition 2.3.

(Quadratic algebras and quadratic duals) Say that the standard graded
$\mathbf{k}$-algebra $A$ presented as in (6) is a quadratic algebra if $I$ is
generated as a two-sided ideal by

$I_{2}=I\cap T^{2}(V)=I\cap(V\otimes V).$

For $A$ any quadratic algebra, presented as in (6), one defines its quadratic
dual algebra $A^{!}$ as follows. Let $V^{*}$ have $\mathbf{k}$-dual basis
$y_{1},\ldots,y_{n}$ to the ordered $\mathbf{k}$-basis $x_{1},\ldots,x_{n}$
for $V$, so that the bilinear pairing $V^{*}\times V\rightarrow\mathbf{k}$ has
$(y_{i},x_{j})=\delta_{ij}$. Then $T^{2}(V^{*})$ and $T^{2}(V)$ have dual
$\mathbf{k}$-bases

$\\{y_{i}\otimes y_{j}\\}_{1\leq i,j\leq n}\text{ and }\\{x_{i}\otimes
x_{j}\\}_{1\leq i,j\leq n}$

with respect to the bilinear pairing $T^{2}(V^{*})\times
T^{2}(V)\rightarrow\mathbf{k}$ defined by

$(y\otimes y^{\prime},x\otimes
x^{\prime}):=(y,x)\cdot(y^{\prime},x^{\prime}).$ (8)

Define $A^{!}$ as this quadratic algebra quotient of the free associative
algebra $T_{\mathbf{k}}(V^{*})=\mathbf{k}\langle y_{1},\ldots,y_{n}\rangle$:

$A^{!}:=T_{\mathbf{k}}(V^{*})/J$

where $J$ is the two-sided ideal generated by

$J_{2}=I_{2}^{\perp}=\\{p\in T^{2}(V^{*}):(p,q)=0\text{ for all }q\in
I_{2}\\}.$

Note that this really is a duality, in the sense that, $(A^{!})^{!}\cong A$.

######  Example 2.4.

A commutative polynomial ring $\mathbf{k}[x_{1},\ldots,x_{n}]$ is a quadratic
$\mathbf{k}$-algebra:

$A=\operatorname{Sym}(V)=\mathbf{k}[x_{1},\ldots,x_{n}]\cong\mathbf{k}\langle
x_{1},\ldots,x_{n}\rangle/I$

where $I=(x_{i}x_{j}-x_{j}x_{i})_{1\leq i<j\leq n}.$ Its quadratic dual
$A^{!}$ is the anti-commutative exterior algebra

$A^{!}=\wedge(V^{*})=\wedge(y_{1},\ldots,y_{n})=\mathbf{k}\langle
y_{1},\ldots,y_{n}\rangle/J$

where $J=(y_{i}y_{j}+y_{j}y_{i})_{1\leq i<j\leq n}+(y_{i}^{2})_{1\leq i\leq
n}.$

###  2.2. Priddy’s resolution and its consequences

It is not hard to show that Koszul algebras $A$ are always
quadratic111Quadraticity is equivalent to having a partial linear resolution
$0\leftarrow\mathbf{k}\leftarrow A\leftarrow F_{1}\leftarrow F_{2}$ up to
homological degree $2$.. What is more remarkable is a result of Priddy
[Priddy], using $A^{!}$ to construct a simple, explicit linear $A$-resolution
of $\mathbf{k}$ whenever $A$ is Koszul. Before describing it, let us point out
certain maps on $A$ and on the graded $\mathbf{k}$-dual $(A^{!})^{*}$. The
latter is defined to be the following graded $\mathbf{k}$-vector subspace of
the usual dual $\text{Hom}_{\mathbf{k}}(A^{!},\mathbf{k})$:

$(A^{!})^{*}:=\bigoplus_{i=0}^{\infty}(A^{!}_{i})^{*}.$

  * •

For $x$ in $A_{1}$, the map on $A$ which right-multiplies by $x$, that is
$a\mapsto x.a:=ax$, gives a left $A$-module map $A\longrightarrow A$, raising
degree by one.

  * •

For $y$ in $A^{!}_{1}$, the map precomposing $\varphi$ in $(A^{!})^{*}$ with
right-multiplication by $y$, that is $\varphi\mapsto y.\varphi$ where
$(y.\varphi)(b):=\varphi(by)$, gives a $\mathbf{k}$-linear map
$(A^{!})^{*}\rightarrow(A^{!})^{*}$, lowering degree by one.

  * •

Combining these, any $x\otimes y$ in $A_{1}\otimes A^{!}_{1}=V\otimes V^{*}$
gives rise to a (left $A$-module) map $A\otimes(A^{!})^{*}\longrightarrow
A\otimes(A^{!})^{*}$ that sends $a\otimes\varphi\longmapsto(x\otimes
y).(a\otimes\varphi):=x.a\otimes y.\varphi$.

######  Theorem 2.5.

(The Priddy resolution) When $A$ is Koszul, the element
$c:=\sum_{j=1}^{n}x_{i}\otimes y_{j}$ in $A_{1}\otimes A^{!}_{1}$ acting on
$A\otimes_{\mathbf{k}}(A^{!})^{*}$ as a left $A$-module map gives a linear
resolution of $\mathbf{k}$ as in (7),

$0\longleftarrow\mathbf{k}{\longleftarrow}A\otimes_{\mathbf{k}}(A^{!}_{0})^{*}\overset{d_{1}}{\longleftarrow}A\otimes_{\mathbf{k}}(A^{!}_{1})^{*}\overset{d_{2}}{\longleftarrow}A\otimes_{\mathbf{k}}(A^{!}_{2})^{*}\overset{d_{3}}{\longleftarrow}\cdots$

Its differential
$d_{i}:A\otimes_{k}(A^{!}_{i})^{*}\overset{d_{i}}{\longrightarrow}A\otimes_{k}(A^{!}_{i-1})^{*}$
is given explicitly as follows:

$a\otimes\varphi\longmapsto
c\cdot\left(a\otimes\varphi\right)=\sum_{j=1}^{n}ax_{j}\otimes y_{j}.\varphi.$

######  Example 2.6.

Continuing Example 2.4, one can check that the Priddy resolution for
$\mathbf{k}$ over $A=\mathbf{k}[x_{1},\ldots,x_{n}]=\operatorname{Sym}(V)$
becomes the usual Koszul resolution

$0\leftarrow\mathbf{k}\leftarrow\operatorname{Sym}(V)\otimes_{\mathbf{k}}\wedge^{0}(V)\leftarrow\operatorname{Sym}(V)\otimes_{\mathbf{k}}\wedge^{1}(V)\leftarrow\operatorname{Sym}(V)\otimes_{\mathbf{k}}\wedge^{2}(V)\leftarrow\cdots\leftarrow\operatorname{Sym}(V)\otimes_{\mathbf{k}}\wedge^{n}(V)\leftarrow
0,$

using that fact that
$(A^{!}_{i})^{*}=(\wedge^{i}(V^{*}))^{*}\cong\wedge^{i}(V)$.

We note some important consequences of Priddy’s resolution. Taking graded
$\mathbf{k}$-duals swaps the roles of $A$ and $A^{!}$ in the resolution.
Consequently, $A$ is Koszul if and only if $A^{!}$ is Koszul. In this case,
one calls $A^{!}$ the Koszul dual algebra of $A$. Priddy’s resolution also has
an important consequence for the Hilbert series of $A,A^{!}$:

$\displaystyle\operatorname{Hilb}(A,t)$
$\displaystyle:=\sum_{i=0}^{\infty}\dim_{\mathbf{k}}A_{i}t^{i},$
$\displaystyle\operatorname{Hilb}(A^{!},t)$
$\displaystyle:=\sum_{i=0}^{\infty}\dim_{\mathbf{k}}A^{!}_{i}t^{i}=\sum_{i=0}^{\infty}\dim_{\mathbf{k}}(A^{!}_{i})^{*}t^{i}=\operatorname{Hilb}((A^{!})^{*},t).$

######  Corollary 2.7.

Whenever $A,A^{!}$ are Koszul, one has
$\operatorname{Hilb}(A,t)\cdot\operatorname{Hilb}(A^{!},-t)=1.$

###### Proof.

For each degree $d\geq 1$, taking the coefficient of $t^{d}$ on both sides in
the corollary is the identity

$\sum_{i=0}^{d}(-1)^{i}\dim_{\mathbf{k}}A_{d-i}\cdot\dim_{\mathbf{k}}(A^{!}_{i})^{*}=0$

asserting vanishing of Euler characteristic for the (exact) $d^{th}$ graded
component in Priddy’s resolution

$0\rightarrow A_{d}\otimes_{\mathbf{k}}(A^{!}_{0})^{*}\rightarrow
A_{d-1}\otimes_{\mathbf{k}}(A^{!}_{1})^{*}\rightarrow\cdots\rightarrow
A_{1}\otimes_{\mathbf{k}}(A^{!}_{d-1})^{*}\rightarrow
A_{0}\otimes_{\mathbf{k}}(A^{!}_{d})^{*}\rightarrow 0.$ (9)

∎

######  Example 2.8.

For the pair of Koszul dual algebras

$\displaystyle A$
$\displaystyle=\operatorname{Sym}(V)=\mathbf{k}[x_{1},\ldots,x_{n}],$
$\displaystyle A^{!}$
$\displaystyle=\wedge(V^{*})=\wedge(y_{1},\ldots,y_{n}),$

one has these Hilbert series

$\displaystyle\operatorname{Hilb}(A,t)$
$\displaystyle=\frac{1}{(1-t)^{n}}\quad\text{ with
}\dim_{\mathbf{k}}A_{i}=\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n}{i}\right)\kern-3.00003pt\right):=\binom{n+i-1}{i},$
$\displaystyle\operatorname{Hilb}(A^{!},t)$
$\displaystyle=(1+t)^{n}\quad\text{ with
}\dim_{\mathbf{k}}A^{!}_{i}=\binom{n}{i}.$

######  Example 2.9.

(Noncommutative monomial Koszul algebras) A two-sided ideal $I\subset
T(V)=\mathbf{k}\langle x_{1},\ldots,x_{n}\rangle$ is called a monomial ideal
when it is generated by monomials. It is called a quadratic monomial ideal if
its generating monomials are quadratic. Thus a quadratic monomial ideal $I$ is
of the form $I_{D}=(x_{i}x_{j}:(i,j)\in D)$ for some choice of a binary
relation $D\subset[n]\times[n]$ on $[n]:=\\{1,2,\ldots,n\\}$; alternatively,
one can view $D$ as a choice of a directed graph on vertex $[n]$ having no
repeated directed arcs $i\rightarrow j$, but allowing (single) copies of loops
$i\rightarrow i$ and (single) pairs of antiparallel arcs $i\rightarrow j$ and
$j\rightarrow i$.

It turns out that quadratic monomial $\mathbf{k}$-algebras, which are the
quotients $A_{D}=T(V)/I$ for such quadratic monomial ideals, are always Koszul
– an explicit linear resolution of $\mathbf{k}$ over $A_{D}$ was constructed
by Bruns, Herzog and Vetter [BrunsHerzogVetter]*§3. Note that the quadratic
dual algebra to $A_{D}$ takes the form $A_{D}^{!}=T(V^{*})/J_{D^{c}}$ where

$J_{D^{c}}=(y_{i}y_{j}:(i,j)\in D^{c})=J=(y_{i}y_{j}:(i,j)\not\in D).$

so $D^{c}:=([n]\times[n])\setminus D$ is the complementary binary
relation/digraph. Hence $A_{D}^{!}\cong A_{D^{c}}$ and

$\operatorname{Hilb}(A_{D},t)\cdot\operatorname{Hilb}(A_{D^{c}},-t)=1.$ (10)

Here $\operatorname{Hilb}(A_{D},t)=1+\sum_{i=1}^{\infty}a_{D^{c}}(i)t^{i}$
where $a_{D^{c}}(i)$ counts $i$-step vertex-to-vertex walks along arcs in the
complement digraph $D^{c}$. Identity (10) appeared earlier in work of Brenti
[Brenti]*§7.5.

Our goal is to study Koszul algebras $A$ together with symmetries coming from
a finite group $G$ of graded ring automorphisms. We will regard each graded
component $A_{i}$ and $A^{!}_{i}$ as representations of $G$, or equivalently,
as $\mathbf{k}G$-modules. In order to work over arbitrary fields $\mathbf{k}$
where $\mathbf{k}G$ might not be semisimple, we introduce the Grothendieck
ring $R_{\mathbf{k}}(G)$.

######  Definition 2.10.

(Grothendieck ring) As a ${\mathbb{Z}}$-module, the Grothendieck group of
$\mathbf{k}G$-modules $R_{\mathbf{k}}(G)$ is a quotient of the free
${\mathbb{Z}}$-module whose basis is the set of isomorphism classes $[V]$ of
$\mathbf{k}G$-modules $V$, and where one mods out by the ${\mathbb{Z}}$-span
of these relations:

$\\{\,\,[V]-([U]+[W]):\text{ for all }\mathbf{k}G\text{-module short exact
sequences }0\rightarrow U\rightarrow V\rightarrow W\rightarrow 0\,\,\\}$ (11)

In particular, in $R_{\mathbf{k}}(G)$ one has $[U\oplus W]=[U]+[W]$.
Multiplication in $R_{\mathbf{k}}(G)$ is induced by the rule
$[V]\cdot[W]:=[V\otimes_{\mathbf{k}}W]$, which one can check is consistent
with the relations in (11).

We collect here a few standard facts about $R_{\mathbf{k}}(G)$, omitting the
proofs.

######  Proposition 2.11.

For any finite group $G$, one has the following.

  * (i)

The relations in $R_{\mathbf{k}}(G)$ imply
$\sum_{i=0}^{\ell}(-1)^{i}[V_{i}]=0$ for longer exact sequences of
$\mathbf{k}G$-modules

$0\leftarrow V_{0}\leftarrow V_{1}\leftarrow\cdots\leftarrow
V_{\ell}\leftarrow 0.$

  * (ii)

More generally, a finite $\mathbf{k}G$-module complex $0\leftarrow
C_{0}\overset{\partial}{\leftarrow}\cdots\overset{\partial}{\leftarrow}C_{\ell}\leftarrow
0$ with homology $\\{H_{*}\\}$ gives an Euler-Poincaré-Hopf-Lefschetz relation
$\sum_{i=0}^{\ell}(-1)^{i}[C_{i}]=\sum_{i=0}^{\ell}(-1)^{i}[H_{i}]$ in
$R_{\mathbf{k}}(G)$.

  * (iii)

Short exact sequences $0\rightarrow U\rightarrow V\rightarrow W\rightarrow 0$
of $\mathbf{k}G$-modules lead to dual/contragredient exact sequences
$0\rightarrow W^{*}\rightarrow V^{*}\rightarrow U^{*}\rightarrow 0$, and also
$(U\otimes V)^{*}\cong U^{*}\otimes V^{*}$. Hence the involution
$[U]\mapsto[U^{*}]$ induces a well-defined involutive ring automorphism
$(-)^{*}:R_{\mathbf{k}}(G)\rightarrow R_{\mathbf{k}}(G)$.

  * (iv)

For subgroups $H$ of $G$, the map $[U]\mapsto[U\downarrow^{G}_{H}]$, where
$U\downarrow^{G}_{H}$ is the restriction of the $\mathbf{k}G$-module $U$ to a
$\mathbf{k}H$-module, induces a well-defined ring map
$(-)\downarrow:R_{\mathbf{k}}(G)\rightarrow R_{\mathbf{k}}(H)$.

  * (v)

Since $(U^{*})\downarrow^{G}_{H}\cong\left(U\downarrow^{G}_{H}\right)^{*}$ as
$\mathbf{k}H$-modules, the maps in (iii),(iv) commute.

######  Remark 2.12.

We explain here why a group $G$ acting on a Koszul algebra $A$ also acts on
the Koszul dual $A^{!}$. When a standard graded $\mathbf{k}$-algebra
$A=T(V)/I$ carries the action of a group $G$ of graded $\mathbf{k}$-algebra
automorphisms, the fact that $G$ preserves $A_{1}=V$, and $A_{1}$ generates
$A$, implies that one can regard $G$ as a subgroup of $GL(V)$, possible
replacing $G$ by $G/K$ if $K$ is the kernel of its action on $V$. Then $G$
also acts contragrediently on $V^{*}$, via $\varphi\mapsto\varphi\circ
g^{-1}$. This gives the natural $\mathbf{k}$-bilinear pairing $V^{*}\otimes
V\rightarrow\mathbf{k}$ defined by $\varphi\otimes v\mapsto\varphi(v)$ a
certain $G$-invariance:

$g(\varphi\otimes v)=(\varphi\circ g^{-1})\otimes
g(v)\mapsto\varphi(g^{-1}(g(v))=\varphi(v).$

The dual pairing (8) between $T^{2}(V^{*})$ and $T^{2}(V)$ then inherits this
same $G$-invariance.

Consequently, when $A=T(V)/I$ is a quadratic algebra with the action of a
group $G$ preserving the subspace $I_{2}\subset T^{2}(V)$ that generates the
ideal $I$, then $G$ also preserves the subspace $J_{2}=I_{2}^{\perp}$ that
generates the ideal $J$ defining the quadratic dual $A^{!}=T(V^{*})/J$. Thus
$G$ also acts on $A^{!}$.

The following proposition should not be surprising.

######  Proposition 2.13.

When $A,A^{!}$ are Koszul, the Priddy resolution is $G$-equivariant for any
group of graded $\mathbf{k}$-algebra automorphisms acting on $A$ (and hence on
$A^{!}$).

###### Proof.

This follows because the differential acts by $c=\sum_{j=1}^{n}x_{j}\otimes
y_{j}$ in $A_{1}\otimes A^{!}_{1}=V\otimes V^{*}$, and $c$ is $G$-fixed: under
the $G$-equivariant isomorphism $V\otimes
V^{*}\cong\operatorname{End}_{\mathbf{k}}(V)$ that sends $v\otimes f$ to
$\varphi:V\rightarrow V$ given by $\varphi(w)=f(w)\cdot v$, one can check that
$c\mapsto 1_{V}$, which is a $G$-fixed element of
$\operatorname{End}_{\mathbf{k}}(V)$. ∎

This gives a version of Corollary 2.7, regarding the equivariant Hilbert
series in $R_{\mathbf{k}}(G)[[t]]$

$\operatorname{Hilb}_{\mathrm{eq}}(A,t):=\sum_{i=0}^{\infty}[A_{i}]t^{i}.$
(12)

######  Corollary 2.14.

(cf. [JosuatvergesNadeau, Prop. 8.1]) Let $A,A^{!}$ be Koszul dual algebras,
both with the action of a group $G$ of graded $\mathbf{k}$-algebra
automorphisms. Then one has this identity in $R_{\mathbf{k}}(G)[[t]]$:

$\operatorname{Hilb}_{\mathrm{eq}}(A,t)\cdot\operatorname{Hilb}_{\mathrm{eq}}((A^{!})^{*},-t)=1$
(13)

Equivalently, $[A_{0}]=[(A^{!}_{0})^{*}]=[\mathbb{1}_{G}]$ and one has these
identities in $R_{\mathbf{k}}(G)$ for $d\geq 1$:

$\sum_{i=0}^{d}(-1)^{i}[A_{d-i}]\cdot[(A^{!}_{i})^{*}]=0$ (14)

which can be rewritten as this recurrence for $[(A^{!}_{d})^{*}]$:

$[(A^{!}_{d})^{*}]=\sum_{i=1}^{d}(-1)^{i-1}[A_{i}]\cdot[(A^{!}_{d-i})^{*}]$
(15)

and this unraveled formula:

$[(A^{!}_{d})^{*}]=\sum_{\begin{subarray}{c}\alpha=(\alpha_{1},\ldots,\alpha_{\ell}):\\\
\alpha_{1}+\cdots+\alpha_{\ell}=d\end{subarray}}(-1)^{d-\ell}[A_{\alpha_{1}}][A_{\alpha_{2}}]\cdots[A_{\alpha_{\ell}}].$
(16)

This last sums runs over all (strict) ordered compositions
$\alpha=(\alpha_{1},\ldots,\alpha_{\ell})$ of $d$, of any length $\ell\geq 1$,
that is, $\alpha_{i}$ are positive integers summing to $d$.

###### Proof.

It suffices to prove (14), which follows from the $G$-equivariance and
exactness of (9) . ∎

######  Example 2.15.

Continuing Examples 2.4, 2.6, 2.8, the Koszul algebras
$A=\operatorname{Sym}(V),\,A^{!}=\wedge(V^{*})$ carry the action of $G=GL(V)$.
There is a ring homomorphism from $R_{\mathbf{k}}(G)$ to the ring

$\Lambda_{\mathbf{k}}(\mathbf{z}):=\Lambda_{\mathbf{k}}(z_{1},\ldots,z_{n})=\mathbf{k}[z_{1},\ldots,z_{n}]^{\mathfrak{S}_{n}}$

of symmetric polynomials in $n$ variables with $\mathbf{k}$ coefficients,
mapping the class $[U]$ of a $\mathbf{k}G$-module $U$ to
$\mathrm{trace}(g|_{U})$ where $g=\mathrm{diag}(z_{1},\ldots,z_{n})$ in
$GL(V)$ is the diagonal matrix in $GL(V)$ having $g(x_{i})=z_{i}\cdot x_{i}$
in $V$ for $i=1,2,\ldots,n$, so that $g(y_{i})=z_{i}^{-1}\cdot y_{i}$ in
$V^{*}$.

Applying this homomorphism to (13) gives a standard identity $H(t)E(-t)=1$ in
$\Lambda_{\mathbf{k}}(\mathbf{z})[[t]]$, where

$\displaystyle
H(t):=\sum_{k=0}^{\infty}h_{k}(z_{1},\ldots,z_{n})t^{k}=\prod_{j=1}^{n}\frac{1}{1-z_{j}t},$
$\displaystyle
E(t):=\sum_{k=0}^{n}e_{k}(z_{1},\ldots,z_{n})t^{k}=\prod_{j=1}^{n}(1+z_{j}t).$

This can be viewed as the specialization of a well-known identity in the ring
of symmetric functions in infinitely many variables
$\Lambda:=\Lambda_{\mathbb{Z}}(z_{1},z_{2},\ldots)$ with integer coefficients,
relating the two sets of algebraically independent generators
$\\{h_{1},h_{2},\ldots\\}$ and $\\{e_{1},e_{2},\ldots\\}$; see
[Macdonald]*Chap. 1, eqn. (2.6), [StanleyEC2]*Thm. 7.6.1. Rewritten as in
(15), one has $e_{0}=h_{0}=1$ and $e_{d}=\sum_{i=1}^{d}(-1)^{i-1}h_{i}\cdot
e_{d-i}$ for all $d\geq 1.$ Due to their algebraic independence, any symmetric
function identities in $\Lambda$ among $\\{h_{i}\\},\\{e_{i}\\}$ lead to the
same identities relating
$\\{[A_{1}],[A_{2}],\ldots\\},\\{[(A^{!}_{1})^{*}],[(A^{!}_{2})^{*}],\ldots\\}$
in $R_{\mathbf{k}}(G)$ for any Koszul algebra $A$ over any field $\mathbf{k}$.
For example, a special case of the Jacobi-Trudi identity [Macdonald, Chap. 1,
eqn. (3.4)], [StanleyEC2, Thm. 7.16.1] expresses the $\\{e_{k}\\}$ in terms of
the $\\{h_{k}\\}$:

$e_{d}=\det\left[\begin{matrix}h_{1}&h_{2}&h_{3}&\cdots&&\\\
1&h_{1}&h_{2}&\cdots&&\\\ 0&1&h_{1}&\cdots&&\\\ 0&0&1&&&\\\
\vdots&\vdots&&\ddots&\ddots\\\
0&0&0&\cdots&1&h_{1}\end{matrix}\right]=\sum_{\alpha=(\alpha_{1},\ldots,\alpha_{\ell})}(-1)^{d-\ell}h_{\alpha_{1}}h_{\alpha_{2}}\cdots
h_{\alpha_{\ell}}.$

where $\alpha$ runs over all compositions of $d$. One now recovers the
unraveled formula (16) for $[(A^{!}_{d})^{*}]$.

###  2.3. A Koszul branching relation

We wish to lift several combinatorial recurrences to branching rules for
Koszul algebras $A$ and their Koszul duals $A^{!}$. Recall from Proposition
2.11(iv) that for any subgroup $H$ of a group $G$, the map
$[U]\mapsto[U\downarrow^{G}_{H}]$ induces a ring map
$(-)\downarrow:R_{\mathbf{k}}(G)\rightarrow R_{\mathbf{k}}(H)$.

######  Proposition 2.16.

Let $A,B$ be two Koszul $\mathbf{k}$-algebras, with actions of groups $G,H$,
where $H$ is a subgroup of $G$, and let $\mathcal{X}$ be a
$\mathbf{k}H$-module. Then in $R_{\mathbf{k}}(H)$, one has

$\displaystyle[A_{i}\downarrow]=[B_{i}]+[{\mathcal{X}}]\cdot[B_{i-1}]$ if and
only if
$\displaystyle[(A^{!}_{i})^{*}\downarrow]=[(B^{!}_{i})^{*}]+[{\mathcal{X}}]\cdot\left([(A^{!}_{i-1})^{*}\downarrow]\right)$
if and only if
$\displaystyle[A^{!}_{i}\downarrow]=[B^{!}_{i}]+[{\mathcal{X}}^{*}]\cdot\left([A^{!}_{i-1}\downarrow]\right)$

###### Proof.

The last equivalence uses the properties of the ring automorphism
$(-)^{*}:R_{\mathbf{k}}(G)\rightarrow R_{\mathbf{k}}(G)$ from Proposition
2.11(iii),(iv),(v). Hence it suffices to prove the first equivalence.

Introduce a few abbreviated notations

$\displaystyle a_{i}$ $\displaystyle:=[A_{i}]\text{ and
}a^{!*}_{i}:=[(A^{!}_{i})^{*}]\text{ in }R_{\mathbf{k}}(G),$ $\displaystyle
b_{i}$ $\displaystyle:=[B_{i}]\text{ and }b^{!*}_{i}=[(B^{!}_{i})^{*}]\text{
in }R_{\mathbf{k}}(H),$ $\displaystyle\bar{a}_{i}$
$\displaystyle:=[A_{i}\downarrow]\text{ and
}\bar{a}^{!*}_{i}:=[(A^{!}_{i})^{*}\downarrow]\text{ in }R_{\mathbf{k}}(H),$
$\displaystyle x$ $\displaystyle:=[{\mathcal{X}}]\text{ in }R_{\mathbf{k}}(H)$

along with analogous generating functions in $R_{\mathbf{k}}(G)[[t]]$ and
$R_{\mathbf{k}}(H)[[t]]$, such as $a(t):=\sum_{i}a_{i}t^{i}$, and similarly
$b(t),a^{!*}(t),b^{!*}(t),\bar{a}(t)$. In this notation, the first equivalence
of the proposition asserts

$\bar{a}_{i}=b_{i}+xb_{i-1}\Leftrightarrow\bar{a}^{!*}_{i}=b^{!*}_{i}+x\bar{a}^{!*}_{i-1}.$

Note that one has these three relations, coming from Corollary 2.14 for the
Koszul algebras $A,B$, and applying the ring map $(-)\downarrow$ to the first
relation:

$\displaystyle a^{!*}(t)a(-t)$ $\displaystyle=1$ $\displaystyle
b^{!*}(t)b(-t)$ $\displaystyle=1$ $\displaystyle\bar{a}^{!*}(t)\bar{a}(-t)$
$\displaystyle=1$

This lets one compute as follows::

$\displaystyle\bar{a}_{i}=b_{i}+xb_{i-1}$ $\displaystyle\Leftrightarrow\quad$
$\displaystyle\bar{a}(t)=(1+xt)\cdot b(t)$ $\displaystyle\Leftrightarrow\quad$
$\displaystyle\frac{1}{\bar{a}(-t)}=\frac{1}{1-xt}\cdot\frac{1}{b(-t)}$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle\bar{a}^{!*}(t)=\frac{1}{1-xt}\cdot b^{!*}(t)$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle(1-xt)\cdot\bar{a}^{!*}(t)=b^{!*}(t)$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle\bar{a}^{!*}_{i}-x\bar{a}^{!*}_{i-1}=b^{!}_{i}$
$\displaystyle\Leftrightarrow\quad$
$\displaystyle\bar{a}^{!*}_{i}=b^{!*}_{i}+x\bar{a}^{!*}_{i-1}.\qed$

######  Example 2.17.

Continuing Example 2.8, the symmetric group $G=\mathfrak{S}_{n}$ acts on the
Koszul dual algebras
$A(n):=\mathbf{k}[x_{1},\ldots,x_{n}]=\operatorname{Sym}(V)$ and
$A(n)^{!}=\wedge(y_{1},\ldots,y_{n})=\wedge(V^{*})$ by permuting variables.
One can apply Proposition 2.16 with
$B=A(n-1)=\mathbf{k}[x_{1},\ldots,x_{n-1}],B^{!}=\wedge(y_{1},\ldots,y_{n-1})$,
which are both $\mathbf{k}H$-modules for $H=\mathfrak{S}_{n-1}$, and with
$\mathcal{X}=\mathbb{1}_{H}$ the trivial $\mathbf{k}H$-module. One then sees
that the proposition lifts the equivalence of these two versions of the Pascal
recurrence

$\displaystyle\binom{n}{i}$ $\displaystyle=\binom{n-1}{i}+\binom{n-1}{i-1},$
$\displaystyle\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n}{i}\right)\kern-3.00003pt\right)$
$\displaystyle=\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n-1}{i}\right)\kern-3.00003pt\right)+\left(\kern-3.00003pt\left(\genfrac{}{}{0.0pt}{}{n}{i-1}\right)\kern-3.00003pt\right),$

to an equivalence of statements on restricting $A(n)_{i},A(n)^{!}_{i}$ from
$\mathfrak{S}_{n}$ to $\mathfrak{S}_{n-1}$:

$\displaystyle[A(n)^{!}_{i}\downarrow]$
$\displaystyle=[A(n-1)^{!}_{i}]+[A(n-1)^{!}_{i-1}],$
$\displaystyle[A(n)_{i}\downarrow]$
$\displaystyle=[A(n-1)_{i}]+[A(n)_{i-1}\downarrow].$

Both also follow from segregating the degree $i$ monomials in
$\mathbf{k}[x_{1},\ldots,x_{n}]$ or $\wedge(y_{1},\ldots,y_{n})$, counted by
the left sides, into monomials not divisible by the last variable
$x_{n},y_{n}$, versus those divisible by it.

##  3\. Review of noncommutative, commutative, exterior Gröbner bases

We review here some of the theory of Gröbner bases for two-sided ideals $I$ in
noncommutative, commutative and exterior algebras over a field $\mathbf{k}$,
emphasizing aspects that are special to the situation where $I$ is
homogeneous, and/or quadratic. Useful references for the

  * •

commutative theory: Cox, Little and O’Shea [CoxLittleOShea], Adams and
Loustaunau [AdamsLoustaunau],

  * •

exterior algebra theory: Aramova, Herzog and Hibi [AramovaHerzogHibi], Stokes
[Stokes],

  * •

noncommutative theory: Mora [Mora], Polishchuk and Positselski
[PolishchukPositselski, Ch. 4], Shepler and Witherspoon [SheplerWitherspoon,
§3].

###  3.1. Monomial orders, initial forms, and initial ideals

Fix a positive integer $n$, and abbreviate the free associative, commutative,
and exterior algebras $R$ in $n$ variables $z_{1},\ldots,z_{n}$ as follows:

$\displaystyle\mathbf{k}\langle\mathbf{z}\rangle$
$\displaystyle:=\mathbf{k}\langle z_{1},\ldots,z_{n}\rangle,$
$\displaystyle\mathbf{k}[\mathbf{z}]$
$\displaystyle:=\mathbf{k}[z_{1},\ldots,z_{n}],$
$\displaystyle\wedge(\mathbf{z})$ $\displaystyle:=\wedge(z_{1},\ldots,z_{n}).$

The set of monomials in each these rings $R$ will be denoted

$\displaystyle\operatorname{Mons}(\mathbf{k}\langle\mathbf{z}\rangle)$
$\displaystyle:=\\{z_{i_{1}}z_{i_{2}}\cdots z_{i_{\ell}}:\ell\geq 0\text{ and
}(i_{1},\ldots,i_{\ell})\in[n]^{\ell}\\}$
$\displaystyle\operatorname{Mons}(\mathbf{k}[\mathbf{z}])$
$\displaystyle:=\\{\mathbf{z}^{\mathbf{a}}=z_{1}^{a_{1}}z_{2}^{a_{2}}\cdots
z_{n}^{a_{n}}:\mathbf{a}=(a_{1},\ldots,a_{n})\in{\mathbb{N}}^{n}\\}$
$\displaystyle\operatorname{Mons}(\wedge(\mathbf{z}))$
$\displaystyle:=\\{\mathbf{z}_{S}=z_{i_{1}}\wedge z_{i_{2}}\wedge\cdots\wedge
z_{i_{\ell}}:S=\\{i_{1}<i_{2}<\cdots<i_{\ell}\\}\subseteq[n]\\}.$

######  Definition 3.1.

(Monomial orders, initial forms, initial ideals) A linear ordering $\prec$ on
$\operatorname{Mons}(R)$ for any of the above three rings $R$ is called a
monomial ordering if

  * •

it is a well-ordering: there are no infinite descending chains $m_{1}\succ
m_{2}\succ m_{3}\succ\cdots$, and

  * •

whenever $m\prec m^{\prime}$, then $m_{1}mm_{2}\prec m_{1}m^{\prime}m_{2}$ for
any other monomials $m_{1},m_{2}$.

Having fixed a monomial order $\prec$ on one of these rings
$R=\mathbf{k}\langle\mathbf{z}\rangle,\mathbf{k}[\mathbf{z}],\wedge(\mathbf{z})$,
write any ring element as a finite $\mathbf{k}$-linear sum of monomials $m$
with nonzero coefficients $c_{m}$ in $\mathbf{k}$

$\displaystyle f=\sum_{m\in\operatorname{Mons}(R)}c_{m}m\,\,=c_{m_{0}}\cdot
m_{0}+\sum_{\begin{subarray}{c}m\in\operatorname{Mons}(R):\\\ m\prec
m_{0}\end{subarray}}c_{m}m$

and then define $m_{0}$ to be its unique $\prec$-initial term or
$\prec$-leading monomial, denoted $\mathrm{in}_{\prec}(f):=m_{0}.$ Given a
(two-sided) ideal $I\subset R$, define its $\prec$-initial ideal to be this
two-sided monomial ideal of $R$:

$\mathrm{in}_{\prec}(I):=(\mathrm{in}_{\prec}(f):f\in I).$

######  Definition 3.2.

Given a monomial order $\prec$ on one of
$R=\mathbf{k}\langle\mathbf{z}\rangle,\mathbf{k}[\mathbf{z}],\wedge(\mathbf{z})$,
and a two-sided ideal $I\subset R$, one says that a subset $\mathcal{G}\subset
I$ is a Gröbner basis (GB) for $I$ with respect to $\prec$ if

$\mathrm{in}_{\prec}(I)=(\\{\mathrm{in}_{\prec}(g):g\in\mathcal{G}\\})=:(\mathrm{in}_{\prec}(\mathcal{G})).$

Equivalently, every $f$ in $I$ has $\mathrm{in}_{\prec}(f)=m_{0}$ (left-right)
divisible by at least one $\mathrm{in}_{\prec}(g)=m$ for some $g$ in
$\mathcal{G}$, meaning that $m_{0}=m_{1}mm_{2}$ for some $m_{1},m_{2}$ in
$\operatorname{Mons}(R)$. One calls a Gröbner basis $\mathcal{G}$ reduced if
for each pair $g\neq g^{\prime}$ in $\mathcal{G}$, none of the monomials $m$
appearing in $g$ with nonzero coefficient are divisible by
$\mathrm{in}_{\prec}(g^{\prime})$.

Gröbner bases for $I$ exist, but may need to be infinite when working in
$R=\mathbf{k}\langle\mathbf{z}\rangle$. For example,

$\mathcal{G}_{0}=\\{\mathrm{in}_{\prec}(f):f\in I\\}$ (17)

always gives a GB for $I$, but is infinite as long as $I\neq\\{0\\}$. The fact
that a GB for an ideal always generates the ideal will follow from a certain
division algorithm.

######  Definition 3.3.

($\mathcal{G}$-standard monomials and the division algorithm) Call a monomial
$m$ in $\operatorname{Mons}(R)$ a $\mathcal{G}$-standard monomial with respect
to $\prec$ if it is (left-right) divisible by none of
$\\{\mathrm{in}_{\prec}(g):g\in\mathcal{G}\\}$.

The division algorithm on $R$ with respect to $\mathcal{G}$ and $\prec$ starts
with any $f$ in $R$ and produces a remainder $r$ having $f\equiv r\bmod I$
(and written $f\rightarrow_{\mathcal{G}}r$) which is a $\mathbf{k}$-linear
combination of $\mathcal{G}$-standard monomials, as follows. Assuming
$f=\sum_{m}c_{m}m$ contains any monomials which are not
$\mathcal{G}$-standard, pick the $\prec$-largest such monomial $m$, and write
it as $m=m_{1}m^{\prime}m_{2}$ where $m^{\prime}=\mathrm{in}_{\prec}(g)$ for
some222Without loss of generality, assume that all $g$ in $\mathcal{G}$ are
$\prec$-monic, meaning that $\mathrm{in}_{\prec}(g)$ has coefficient $+1$ in
$g$. $g$ in $\mathcal{G}$. Then replace $f$ by

$f^{\prime}:=f-c_{m}\cdot m_{1}\cdot g\cdot m_{2}$

which has $f\equiv f^{\prime}\bmod I$. Repeat the process with $f^{\prime}$.
One can show that, because $\prec$ is a well-ordering, this algorithm will
eventually terminate with a remainder $r$ that contains only
$\mathcal{G}$-standard monomials. However, the remainder $r$ may not be
unique, due to choices of which element $g$ in $\mathcal{G}$ has
$m^{\prime}=\mathrm{in}_{\prec}(g)$ dividing the non-$\mathcal{G}$-standard
term $m$ of $f$ at each stage.

The following equivalent conditions defining Gröbner bases are standard
verifications.

######  Proposition 3.4.

Fixing $\prec$ and the two-sided ideal $I\subset R$, the following are
equivalent for $\mathcal{G}\subset I$:

  1. (i)

$\mathcal{G}$ is a GB for $I$ with respect to $\prec$.

  2. (ii)

The division algorithm $f\rightarrow_{\mathcal{G}}r$ always gives the same
remainder $r$ for $f$.

  3. (iii)

One has $f\in I$ if and only if $f\rightarrow_{\mathcal{G}}0$, regardless of
choices in the division algorithm. In particular, $\mathcal{G}$ generates $I$.

  4. (iv)

The (images of the) $\mathcal{G}$-standard monomials with respect to $\prec$
give a $\mathbf{k}$-basis for $R/I$.

The GB condition has a useful rephrasing for homogeneous ideals $I$, meaning
$I=\bigoplus_{d=0}^{\infty}(I\cap R_{d})$.

######  Proposition 3.5.

For a homogeneous two-sided ideal $I\subset R$, a subset $\mathcal{G}\subset
I$ forms a GB of $I$ with respect to $\prec$ if and only if
$\operatorname{Hilb}(S/(\mathrm{in}_{\prec}(\mathcal{G})),t)=\operatorname{Hilb}(S/I,t).$

###### Proof.

By definition $\mathcal{G}\subset I$ is a GB if and only if the inclusion
$(\mathrm{in}_{\prec}(\mathcal{G}))\subseteq\mathrm{in}_{\prec}(I)$ is an
equality. This occurs if and only if the graded $\mathbf{k}$-algebra
surjection $R/(\mathrm{in}_{\prec}(\mathcal{G}))\twoheadrightarrow
R/\mathrm{in}_{\prec}(I)$ is a $\mathbf{k}$-vector space isomorphism in each
degree. By dimension-counting, this occurs if and only if

$\operatorname{Hilb}(S/(\mathrm{in}_{\prec}(\mathcal{G})),t)=\operatorname{Hilb}(S/\mathrm{in}_{\prec}(I),t)$

However one also has
$\operatorname{Hilb}(S/\mathrm{in}_{\prec}(I),t)=\operatorname{Hilb}(S/I,t)$,
since the Gröbner basis $\mathcal{G}_{0}:=\\{\mathrm{in}_{\prec}(f):f\in I\\}$
from (17) has its $\mathcal{G}_{0}$-standard monomials giving a (homogeneous)
$\mathbf{k}$-basis for both $S/\mathrm{in}_{\prec}(I)$ by definition, and for
$S/I$ by Proposition 3.4(iv). ∎

There are some advantages to working with Gröbner bases in the commutative
polynomial algebra $\mathbf{k}[\mathbf{z}]$ and exterior algebra
$\wedge(\mathbf{z})$, where GBs for ideals are always finite, and can be
computed via versions of Buchberger’s algorithm. One can always view quotients
$\mathbf{k}[\mathbf{z}]/I$ and $\wedge(\mathbf{z})/I$ as quotients of
$\mathbf{k}\langle\mathbf{z}\rangle$ via the surjections

$\begin{array}[]{rcl}\mathbf{k}\langle\mathbf{z}\rangle\overset{\pi}{\longrightarrow}\mathbf{k}[\mathbf{z}]&\text{
with }&\ker(\pi)=(z_{i}z_{j}-z_{j}z_{i}:1\leq i<j\leq n)\\\
\mathbf{k}\langle\mathbf{z}\rangle\overset{\pi}{\longrightarrow}\wedge(\mathbf{z})&\text{
with }&\ker(\pi)=(z_{i}z_{j}+z_{j}z_{i}:1\leq i<j\leq n)+(z_{i}^{2}:1\leq
i\leq n)\end{array}$

In other words, $\mathbf{k}[\mathbf{z}]/I$ or $\wedge(\mathbf{z})/I$ is
isomorphic to $\mathbf{k}\langle\mathbf{z}\rangle/\pi^{-1}(I)$. Note that
since the

  * •

commutators $[z_{i},z_{j}]_{+}:=z_{i}z_{j}-z_{j}z_{i}$,

  * •

anti-commutators $[z_{i},z_{j}]_{-}:=z_{i}z_{j}+z_{j}z_{i}$, and

  * •

squares $z_{i}^{2}$

that generate $\ker(\pi)$ are homogeneous and quadratic, this means that if
$I$ is a homogeneous ideal of $\mathbf{k}[\mathbf{z}]$ or
$\wedge(\mathbf{z})$, then $\pi^{-1}(I)$ will be a homogeneous two-sided ideal
of $\mathbf{k}\langle\mathbf{z}\rangle$. Similarly, if $I$ is a quadratic
ideal, then the same holds for $\pi^{-1}(I)$, and
$\mathbf{k}\langle\mathbf{z}\rangle/\pi^{-1}(I)$ will be a quadratic algebra.

This leads to one of the most common techniques for proving Koszulity.

######  Theorem 3.6.

Consider ideals $I\subset R=\mathbf{k}[\mathbf{z}]$ or $I\subset
R=\wedge(\mathbf{z})$.

  1. (i)

(Fröberg [Froberg-original]) If $I$ is a quadratic monomial ideal, then $R/I$
is Koszul.

  2. (ii)

(Folklore333 In [EisenbudReevesTotaro] it is credited it to Fröberg’s result
(i) “and a deformation argument noticed by Kempf and others”.; see [Froberg-
survey, §4], [mcculloughPeevaSurvey, Thm. 8.14], [Peeva, §3]) If $I$ has a
quadratic Gröbner basis $\mathcal{G}$ with respect to some monomial order
$\prec$ on $R$, then $R/I$ is Koszul.

##  4\. Matroids, oriented matroids, and supersolvability

The Koszul algebras of interest to us are Orlik-Solomon algebras of matroids
and graded Varchenko-Gel’fand algebras of oriented matroids, in the case where
the matroids are supersolvable. We therefore review here the basics of
matroids, oriented matroids, and supersolvability.

###  4.1. Matroid and oriented matroid review

A useful reference for matroids is Oxley [Oxley], and for oriented matroids is
Björner, Las Vergnas, Sturmfels, White and Ziegler [BLSWZ].

A matroid $M$ (respectively, oriented matroid $\mathcal{M}$) on ground set
$E=\\{1,2,\ldots,n\\}$ is an abstraction of the linear dependence information
about a list of vectors $v_{1},v_{2},\ldots,v_{n}$ in a vector space over a
field $\mathbf{k}$ (respectively, $\mathbf{k}={\mathbb{R}}$), forgetting the
coordinates of the vectors themselves, but recording which subsets are
linearly dependent (respectively, the $\pm$ signs in their linear
dependences). One way to record this information is with the matroid or
oriented matroid’s circuits, abstracting the minimal dependences.

######  Definition 4.1.

A matroid $M$ on ground set $E=\\{1,2,\ldots,n\\}$ is defined by its
collection $\mathcal{C}\subset 2^{E}$ of circuits, satisfying these axioms:

  1. C1.

$\varnothing\not\in\mathcal{C}$

  2. C2.

If $C,C^{\prime}$ in $\mathcal{C}$, and $C\subseteq C^{\prime}$ then
$C=C^{\prime}$

  3. C3.

If $C,C^{\prime}$ in $\mathcal{C}$, and $e\in C\cap C^{\prime}\subsetneq
C,C^{\prime}$, then there exists $C^{\prime\prime}\in\mathcal{C}$ with
$C^{\prime\prime}\subseteq C\cup C^{\prime}\setminus\\{e\\}$.

An oriented matroid $M$ on ground set $E=\\{1,2,\ldots,n\\}$ is defined by its
collection $\mathcal{C}^{\pm}=\\{(C_{+},C_{-})\\}$ of signed circuits which
are pairs $(C_{+},C_{-})$ of disjoint subsets $C_{+}\sqcup C_{-}\subseteq E$,
satisfying these axioms:

  1. C1±.

$(\varnothing,\varnothing)\not\in\mathcal{C}^{\pm}$

  2. C2±.

If $(C_{+},C_{-})$ in $\mathcal{C}^{\pm}$, then $(C_{-},C_{+})$ in
$\mathcal{C}^{\pm}$

  3. C3±.

If $(C_{+},C_{-}),(C^{\prime}_{+},C^{\prime}_{-})$ in $\mathcal{C}^{\pm}$, and
$C_{+}\cup C_{-}\subseteq C^{\prime}_{+}\cup C^{\prime}_{-}$ then
$(C^{\prime}_{+},C^{\prime}_{-})=(C_{+},C_{-})$ or $(C_{-},C_{+})$.

  4. C4±.

If $(C_{+},C_{-}),(C^{\prime}_{+},C^{\prime}_{-})$ in $\mathcal{C}^{\pm}$ and
$e\in C_{+}\cap C^{\prime}_{-}$, then there exists
$(C^{\prime\prime}_{+},C^{\prime\prime}_{-})\in\mathcal{C}^{\pm}$ with
$C^{\prime\prime}\subseteq C\cup C^{\prime}\setminus\\{e\\}$ having
$C^{\prime\prime}_{+}\subseteq\left(C_{+}\cup
C^{\prime}_{+}\right)\setminus\\{e\\}$, and
$C^{\prime\prime}_{-}\subseteq\left(C_{-}\cup
C^{\prime}_{-}\right)\setminus\\{e\\}$.

One can check that every oriented matroid $\mathcal{M}$ with signed circuits
$\mathcal{C}^{\pm}$ gives rise to a matroid $M$ having circuits
$\mathcal{C}:=\\{C_{+}\cup C_{-}:(C_{+},C_{-})\in\mathcal{C}^{\pm}\\}$; one
calls the matroid $M$ orientable whenever it comes from such an oriented
matroid $\mathcal{M}$, and one calls $\mathcal{C}$ the (matroid) circuits of
$\mathcal{M}$.

One calls $M$ a representable matroid (over the field $\mathbf{k}$) if there
exists a list of vectors $v_{1},v_{2},\ldots,v_{n}$ in a $\mathbf{k}$-vector
space such that the subsets $C$ in $\mathcal{C}$ index the minimal dependent
subsets $\\{v_{j}\\}_{j\in C}$, that is, $\sum_{j\in C}c_{j}v_{j}=0$ for some
$c_{j}$ in $\mathbf{k}$, but every proper subset of $\\{v_{j}\\}_{j\in C}$ is
independent. Similarly, $\mathcal{M}$ is a representable oriented matroid if
additionally $\mathbf{k}={\mathbb{R}}$ and the pairs $(C_{+},C_{-})$ in
$\mathcal{C}^{\pm}$ give the subsets
$C^{+}=\\{j:c_{j}>0\\},\,C^{-}=\\{j:c_{j}<0\\}$. for all such minimal
dependent subsets of $v_{1},\ldots,v_{n}$.

A matroid $M$ on ground set $E$ can also be specified by its collection of
flats $\mathcal{F}=\\{F\\}\subseteq 2^{E}$, where $F\subseteq E$ is a flat if
every circuit $C$ in $\mathcal{C}$ with $|C\cap F|=|C|-1$ has $C\subseteq F$.
We will consider $\mathcal{F}$ as a poset ordered via inclusion. This poset
turns out to always be a geometric lattice meaning that

  * •

any pair of flats $F,F^{\prime}$ have a meet (greatest lower bound) $F\wedge
F^{\prime}=F\cap F^{\prime}$ and a join (least upper bound) $F\vee
F^{\prime}$,

  * •

it is an atomic lattice in the sense that every flat $F$ has

$F=\bigvee_{\text{ atoms }G\leq F}G,$

where atoms are flats that cover the unique bottom element, and

  * •

it is upper semimodular, meaning that there is a rank function
$r:\mathcal{F}\rightarrow\\{0,1,2,\ldots\\}$ satisfying

$r(F\vee F^{\prime})\leq r(F)+r(F^{\prime})-r(F\wedge F^{\prime}).$ (18)

The rank of the matroid $M$ is defined to be $r(M):=r(E)$.

It will also be convenient later (in Definition 5.15 below) to note that every
oriented matroid $\mathcal{M}$ on $E$ of rank $r$ can be specified via its
chirotope. This is a function $\chi_{\mathcal{M}}:E^{r}\rightarrow\\{0,\pm
1\\}$ satisfying certain axioms; see [BLSWZ, §1.9, 3.5]), and the values
$\chi_{\mathcal{M}}(i_{1},i_{2},\ldots,i_{r})$ are defined only up to an
overall rescaling by $\pm 1$. In the case where $\mathcal{M}$ is realized by
vectors $v_{1},v_{2},\ldots,v_{n}$, then
$\chi_{\mathcal{M}}(i_{1},i_{2},\ldots,i_{r})$ is the $\\{0,\pm 1\\}$-valued
sign of the determinant of the $r\times r$ matrix having
$v_{i_{1}},v_{i_{2}},\ldots,v_{i_{r}}$ as its columns.

In studying Orlik-Solomon and Varchenko-Gel’fand rings, it will turn out (see
Remark 5.3 below) that we lose no generality by restricting to matroids and
oriented matroids which are simple, meaning that they have no loops (=
singleton circuits $C=\\{i\\}$) and no parallel elements (= circuits
$C=\\{i,j\\}$ of size two). Consequently, their matroid structure $M$ is
completely determined by the poset of flats $\mathcal{F}$ up to isomorphism,
whose unique bottom element will be the empty flat $F=\varnothing$, and whose
atoms at rank $1$ are the singleton flats $F=\\{1\\},\\{2\\},\ldots,\\{n\\}$,
identified with the ground set $E$.

###  4.2. Supersolvability

We will be focussing on matroids that satisfy the strong condition of
supersolvability, reviewed here.

######  Definition 4.2.

Say that a flat $F$ in a matroid $M$ is modular if one always has equality in
(18):

$r(F\vee F^{\prime})=r(F)+r(F^{\prime})-r(F\wedge F^{\prime})\text{ for all
}F^{\prime}\in\mathcal{F}.$

A matroid $M$ is called supersolvable if the poset $\mathcal{F}$ contains a
complete flag $\underline{F}$ of modular flats

$\underline{F}:=(\varnothing=F_{0}\subsetneq F_{1}\subsetneq\cdots\subsetneq
F_{r(M)-1}\subsetneq F_{r(M)}=E).$

We consider as examples the (strict) subset of supersolvable matroids among
the uniform matroids, which we recall here.

######  Definition 4.3.

(Uniform matroids) The uniform matroid $M=U_{r,n}$ of rank $r$ on ground set
$E=\\{1,2,\ldots,n\\}$ has circuits $\mathcal{C}$ equal to all $(r+1)$-element
subsets of $E$. Its poset of flats $\mathcal{F}$ is obtained from $2^{E}$, the
Boolean algebra of rank $n$, by removing all subsets of cardinalities
$r,r+1,\cdots,n-2,n-1$.

######  Remark 4.4.

The uniform matroid $U_{r,n}$ is represented by any list of $n$ vectors
$v_{1},v_{2},\ldots,v_{n}$ in $\mathbf{k}^{r}$ that are sufficiently generic,
in the sense that every $r$-element subset $\\{v_{i_{1}},\ldots,v_{i_{r}}\\}$
is linearly independent. This imposes restrictions on the cardinality of the
field $\mathbf{k}$, depending upon $n$ and $r$, but means that $U_{r,n}$ is
always representable over an infinite field, such as
$\mathbf{k}={\mathbb{R}}$, and hence is always orientable. Nevertheless, some
of these orientations $\mathcal{M}$ of $M=U_{r,n}$ can behave differently, for
example in their group of automorphisms $\text{Aut}(\mathcal{M})$. In the
examples of this section, we will consider only the unoriented matroid
$M=U_{r,n}$.

It is not hard to see that the uniform matroid $M=U_{r,n}$ is

  * •

simple if and only if $r\geq 1$,

  * •

simple and supersolvable if and only if $r\in\\{1,2,n\\}$.

######  Example 4.5.

The Boolean matroid $M=U_{n,n}$ on ground set $E=\\{1,2,\ldots,n\\}$ has no
circuits, that is, $\mathcal{C}=\varnothing$, and poset of flats
$\mathcal{F}=2^{E}$. Every flat $F$ is modular, so every complete flag
$\underline{F}$ of flats is modular and $M$ is supersolvable.

######  Example 4.6.

Every rank two simple matroid is a uniform matroid $M=U_{2,n}$ on
$E=\\{1,2,\ldots,n\\}$, with this flat poset $\mathcal{F}$:

$E$$\\{1\\}$$\\{2\\}$$\\{3\\}$$...$$\\{n\\}$$\varnothing$

Again, every flat $F$ is modular, and every complete flag
$\varnothing\subset\\{i\\}\subset E$ shows that $M$ is supersolvable.

Our original motivation came from braid matroids.

######  Example 4.7.

(Supersolvable graphic matroids and braid matroids) Let $G$ be a graph on
vertex set $\\{1,2,\ldots,n\\}$ with edge set $E\subseteq\\{\\{i,j\\}:1\leq
i<j\leq n\\}$ which is simple, that is, $G$ no self-loops and no parallel
edges. Then $G$ gives rise to a simple graphic matroid $M$ (and oriented
matroid $\mathcal{M}$) represented by the list of vectors
$\\{v_{ij}=e_{i}-e_{j}\\}_{\\{i,j\\}\in E}\subset{\mathbb{R}}^{n}$, where
$e_{1},\dots,e_{n}$ are standard basis vectors. The matroid circuits
$\mathcal{C}$ are indexed by subsets $C\subseteq E$ of edges that form a cycle
within $G$. Stanley showed [stanley1972supersolvable, Prop. 2.8] that this
graphic matroid is supersolvable if and only $G$ is a chordal graph, meaning
that for every minimal cycle of edges $u_{1}-u_{2}-\cdots-
u_{\ell-1}-u_{\ell}-u_{1}$ in $G$ having $\ell\geq 4$, there will be another
edge $\\{u_{i},u_{j}\\}$ of $G$ with $i\not\equiv j\pm 1\bmod{\ell}$ forming a
chord.

In particular, the complete graph $K_{n}$ on $n$ vertices with all
$\binom{n}{2}$ edges is a chordal graph, and its graphic matroid is called the
braid matroid $\operatorname{Br}_{n}$ on $n$ strands. Its poset of flats
$\mathcal{F}$ is isomorphic to the lattice $\Pi_{n}$ of all set partitions
$\pi=(B_{1},\ldots,B_{\ell})$ of
$\\{1,2,\ldots,n\\}=\sqcup_{i=1}^{\ell}B_{i}$, with ordering by refinement:
$\pi\leq\pi^{\prime}$ if for every block $B_{i}$ of $\pi$ there exists some
block $B^{\prime}_{i^{\prime}}$ of $\pi^{\prime}$ having $B_{i}\subseteq
B^{\prime}_{i^{\prime}}$. The flat $F$ corresponding to $\pi$ contains all
edges $\\{i,j\\}$ whose endvertices $i,j$ lie in the same block $B_{k}$ of
$\pi$. The modular flats correspond to partitions $\pi$ with at most one non-
singleton block. For example, one modular complete flag $\underline{F}$ of
flats corresponds to the set partitions $\pi_{1}<\pi_{2}<\cdots<\pi_{n}$ where

$\pi_{k}:=\\{\\{1,2,\ldots,k\\},\\{k+1\\},\\{k+2\\},\ldots,\\{n-1\\},\\{n\\}\\}.$

##  5\. Orlik-Solomon and Varchenko-Gel’fand rings

We review here the Orlik-Solomon algebra of a matroid $M$ and graded
Varchenko-Gel’fand algebra444Also called the Cordovil algebra in
[MatherneMiyataProudfootRamos]. of an oriented matroid $\mathcal{M}$. Useful
references for Orlik-Solomon algebras are Dimca [Dimca, Ch. 3], Dimca and
Yuzvinsky [DimcaYuzvinsky], Orlik and Terao [OrlikTerao, Ch. 3], Yuzvinsky
[Yuzvinsky]. Useful references for graded Varchenko-Gel’fand algebras are
Brauner [Brauner, Secs. 3.3, 5.2], Cordovil [Cordovil], Dorpalen-Barry
[Dorpalen-Barry], Dorpalen-Barry, Proudfoot and Wang
[DorpalenBarryProudfootWang], Moseley [Moseley], Varchenko and Gel’fand
[VarchenkoGelfand].

For the remainder of this section, let $\mathbf{k}$ be any commutative ring
with $1$.

######  Definition 5.1.

(Orlik-Solomon algebra) For a simple matroid $M$ on $E=\\{1,2,\ldots,n\\}$,
define its Orlik-Solomon algebra over $\mathbf{k}$ as an anti-commutative
quotient

$\mathrm{OS}(M):=\wedge(x_{1},\ldots,x_{n})/I_{\mathrm{OS}(M)}$

where $\wedge(x_{1},\ldots,x_{n})$ is the exterior algebra over $\mathbf{k}$
on $n$ generators. The Orlik-Solomon ideal

$I_{\mathrm{OS}(M)}=(\partial(x_{C}):C\in\mathcal{C})$ (19)

has one generator $\partial(x_{C})$ for each circuit
$C=\\{c_{1},c_{2},\ldots,c_{k}\\}$ in $\mathcal{C}$, with $\partial(x_{C})$
defined by

$\partial x_{C}:=\sum_{j=1}^{k}(-1)^{j-1}x_{c_{1}}\wedge\cdots\wedge
x_{c_{j-1}}\wedge\widehat{x_{c_{j}}}\wedge x_{c_{j+1}}\cdots\wedge x_{c_{k}}.$
(20)

######  Definition 5.2.

(Graded Varchenko-Gel’fand ring) For a simple oriented matroid $\mathcal{M}$
on $E=\\{1,2,\ldots,n\\}$, define its graded Varchenko-Gel’fand ring over
$\mathbf{k}$ as the commutative quotient

$\mathrm{VG}(\mathcal{M}):=\mathbf{k}[x_{1},\ldots,x_{n}]/I_{\mathrm{VG}(\mathcal{M})}$

where $\mathbf{k}[x_{1},\ldots,x_{n}]$ is the polynomial algebra over
$\mathbf{k}$. The graded Varchenko-Gel’fand ideal

$I_{\mathrm{VG}(\mathcal{M})}=(x_{1}^{2},\ldots,x_{n}^{2})+(\partial^{\pm}(x_{C}):C\in\mathcal{C})$
(21)

contains the squares $\\{x_{i}^{2}\\}_{i=1}^{n}$ along with one generator
$\partial^{\pm}(x_{C})$ for each circuit $C$ in $\mathcal{C}$, with
$\partial^{\pm}(x_{C})$ defined by choosing one of the two signed
circuits555The choice is immaterial – making the other choice replaces
$\partial^{\pm}(x_{C})$ by its negative. $(C_{+},C_{-})$ in $\mathcal{C}$ with
$C=C_{+}\cup C_{-}$, and setting

$\partial^{\pm}(x_{C}):=\sum_{c_{j}\in C_{+}\cup
C_{-}}{\mathrm{sgn}_{{C},{c_{j}}}}\cdot x_{c_{1}}\cdots
x_{c_{j-1}}\widehat{x_{c_{j}}}x_{c_{j+1}}\cdots x_{c_{k}}.$ (22)

Here ${\mathrm{sgn}_{{C},{c_{j}}}}=\pm 1$, namely $+1$ when $c_{j}\in C_{+}$
and $-1$ when $c_{j}\in C_{-}$.

######  Remark 5.3.

Our assumption that $M,\mathcal{M}$ are simple really presents no restriction.
In either case,

  * •

a loop $i$ in $E$ would give a circuit $C=\\{i\\}\in\mathcal{C}$, causing the
collapse $\mathrm{OS}(M)=0=\mathrm{VG}(\mathcal{M})$ since
$I_{\mathrm{OS}(M)}$ or $I_{\mathrm{VG}(\mathcal{M})}$ contains the generator
$\partial(x_{C})=1$ or $\partial^{\pm}(x_{C})=1$, and

  * •

parallel elements $i,j$ in $E$ would give rise to a circuit
$C=\\{i,j\\}\in\mathcal{C}$, making $x_{i}=\pm x_{j}$ in the rings
$\mathrm{OS}(M)$ or $VG(\mathcal{M})$ because $I_{\mathrm{OS}(M)}$ or
$I_{\mathrm{VG}(\mathcal{M})}$ contains a generator $\partial(x_{C})$ or
$\partial^{\pm}(x_{C})$ of of the form $x_{i}\pm x_{j}$.

Thus our assumption in Section 2 that our standard graded
$\mathbf{k}$-algebras are minimally generated by the variables
$x_{1},\ldots,x_{n}$ is consistent with assuming that $M,\mathcal{M}$ are
simple matroids.

###  5.1. Flat decomposition

An important feature of both $\mathrm{OS}(M)$ and $\mathrm{VG}(\mathcal{M})$
is that their ${\mathbb{N}}$-grading is refined by a $\mathbf{k}$-vector space
decompsition indexed by the matroid flats $F$ in $\mathcal{F}$.

######  Definition 5.4.

Given matroid $M$ or oriented matroid $\mathcal{M}$ on $E=\\{1,\dots,n\\}$
with flats $\mathcal{F}$, abbreviating the variable sets
$\mathbf{x}=(x_{1},\ldots,x_{n})$, consider the $\mathbf{k}$-vector space
decompositions

$\displaystyle T(V)$
$\displaystyle=\mathbf{k}\langle\mathbf{x}\rangle=\bigoplus_{F\in\mathcal{F}}\underbrace{T(V)_{F}}_{=\mathbf{k}\langle\mathbf{x}\rangle_{F}},$
$\displaystyle\operatorname{Sym}(V)$
$\displaystyle=\mathbf{k}[\mathbf{x}]=\bigoplus_{F\in\mathcal{F}}\underbrace{\operatorname{Sym}(V)_{F}}_{=\mathbf{k}[\mathbf{x}]_{F}},$
$\displaystyle\wedge(V)$
$\displaystyle=\wedge(\mathbf{x})=\bigoplus_{X\in\mathcal{F}}\underbrace{\wedge(V)_{F}}_{=\wedge(\mathbf{x})_{F}},$

where
$\mathbf{k}\langle\mathbf{x}\rangle_{F},\mathbf{k}[\mathbf{x}]_{F},\wedge(\mathbf{x})_{F}$
are the $\mathbf{k}$-spans of monomials $x_{j_{1}}x_{j_{2}}\cdots x_{j_{k}}$
with $\\{j_{1}\\}\vee\cdots\vee\\{j_{k}\\}=F$.

Both $\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ inherit these
$\mathbf{k}$-vector space decompositions by flats; for $\mathrm{OS}(M)$, see
[OrlikTerao]*Thm 3.26, Cor. 3.27, [DimcaYuzvinsky]*§2.3, [Yuzvinsky]*§2.3, and
for $\mathrm{VG}(\mathcal{M})$ see [Brauner]*Theorem 5.5.

######  Proposition 5.5.

For a matroid $M$ or oriented matroid $\mathcal{M}$, the ideals
$I_{\mathrm{OS}(M)},I_{\mathrm{VG}(\mathcal{M})}$ are homogeneous with respect
to the decomposition in Definition 5.4, that is,

$\displaystyle I_{\mathrm{OS}(M)}$
$\displaystyle=\bigoplus_{F\in\mathcal{F}}\mathbf{k}(\mathbf{x})_{F}\cap
I_{\mathrm{OS}(M)},$ $\displaystyle I_{\mathrm{VG}(\mathcal{M})}$
$\displaystyle=\bigoplus_{F\in cF}\mathbf{k}[\mathbf{x}]_{F}\cap
I_{\mathrm{VG}(\mathcal{M})}.$

Hence they induce $\mathbf{k}$-vector space decompositions of the quotients
$\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$:

$\displaystyle\mathrm{OS}(M)$
$\displaystyle=\bigoplus_{F\in\mathcal{F}}\mathrm{OS}(M)_{F},$ (23)
$\displaystyle\mathrm{VG}(\mathcal{M})$
$\displaystyle=\bigoplus_{F\in\mathcal{F}}\mathrm{VG}(\mathcal{M})_{F}.$ (24)

We note here an implication for quadratic duals that will become important
later, in Section 8.1. When considering
$\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ as quotients
$A=\mathbf{k}\langle\mathbf{x}\rangle/I$ of the tensor algebra for a two-sided
ideal $I$, the quadratic part $I_{2}\subset
T^{2}(V)=\mathbf{k}\langle\mathbf{x}\rangle_{2}$ inherits the flat
decomposition $I_{2}=\bigoplus_{F\in\mathcal{F}}[T^{2}(V)_{F}\cap I]$ from
$T^{2}(V)=\bigoplus_{F\in\mathcal{F}}T^{2}(V)_{F}$. On the other hand, if one
defines the analogous flat decomposition for the dual tensor algebra and its
dual variables $\mathbf{y}=(y_{1},\ldots,y_{n})$

$T(V^{*})=\mathbf{k}\langle\mathbf{y}\rangle=\bigoplus_{F\in\mathcal{F}}\underbrace{T(V)_{F}}_{=\mathbf{k}\langle\mathbf{y}\rangle_{F}},$

then the pairing $T^{2}(V^{*})\times T^{2}(V)\rightarrow\mathbf{k}$ from (8)
makes $T^{2}(V^{*})_{F}$ and $T^{2}(V)_{F^{\prime}}$ orthogonal for $F\neq
F^{\prime}$. This implies that the computation of $J_{2}:=I_{2}^{\perp}$ can
be done flat-by-flat:

$J_{2}=\bigoplus_{F\in\mathcal{F}}[T^{2}(V^{*})_{F}\cap J_{2}]\quad\text{
where }\quad[T^{2}(V^{*})_{F}\cap J_{2}]:=[T^{2}(V)_{F}\cap I_{2}]^{\perp}.$
(25)

In particular, whenever $A=\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ are
Koszul, or even just quadratic algebras
$A=\mathbf{k}\langle\mathbf{x}\rangle/I$ with $I=(I_{2})$, their quadratic
duals $A^{!}=\mathbf{k}\langle\mathbf{x}\rangle/J$ where
$J=(J_{2})=(I_{2}^{\perp})$ inherit a flat decomposition:

$A^{!}=\bigoplus_{F\in\mathcal{F}}A^{!}_{F}.$ (26)

###  5.2. Symmetry

Symmetries of a matroid $M$ or oriented matroid $\mathcal{M}$ lead to
$\mathbf{k}$-algebra automorphisms of $\mathrm{OS}(M)$ or
$\mathrm{VG}(\mathcal{M})$, as we explain next.

######  Definition 5.6.

Let $M$ be a matroid on $E=\\{1,2,\ldots,n\\}$ with circuits $\mathcal{C}$. A
permutation $\sigma$ in the symmetric group $\mathfrak{S}_{n}$ is an
automorphism of $M$, written $\sigma\in\text{Aut}(M)$, if
$\sigma(\mathcal{C})=\mathcal{C}$, that is, for every $C$ in $\mathcal{C}$,
one has $\sigma(C)\in\mathcal{C}$.

One can then check that for any matroid $M$ and $\sigma$ in $\text{Aut}(M)$,
letting $\sigma$ act on $\wedge(x_{1},\ldots,x_{n})$ permuting subscripts of
the variables, that is, $\sigma(x_{i}):=x_{\sigma(i)},$ then the generator
$\partial(x_{C})$ for the Orlik-Solomon ideal $I_{\mathrm{OS}(M)}$ has

$\sigma(\partial(x_{C}))=\pm\partial(x_{\sigma(C)}).$

Consequently, $\sigma$ preserves $I_{\mathrm{OS}(M)}$ and induces a graded
$\mathbf{k}$-algebra automorphism of $\mathrm{OS}(M)$.

######  Definition 5.7.

Let $\mathcal{M}$ be an oriented matroid on $E=\\{1,2,\ldots,n\\}$. Its
automorphism group $\text{Aut}(\mathcal{M})$ will be a subgroup of the
hyperoctahedral group $\mathfrak{S}^{\pm}_{n}$; this is the set of all signed
permutations $\sigma$ of $\\{\pm 1,\pm 2,\ldots,\pm n\\}$, meaning those
permutations which commute with the involution $+i\leftrightarrow-i$, or in
other words, $\sigma(\pm i)=-\sigma(\mp i)$. As notation, for
$i,j\in\\{1,2,\ldots,n\\}$, define

$\displaystyle|\sigma(i)|$ $\displaystyle:=j\quad\text{ if
}\sigma(+i)\in\\{\pm j\\},$ $\displaystyle\epsilon(\sigma(i))$
$\displaystyle=\begin{cases}+&\text{ if }\sigma(+i)=+j,\\\ -&\text{ if
}\sigma(+i)=-j.\end{cases}$

Then a signed permutation $\sigma$ is an automorphism of $\mathcal{M}$ if for
every signed circuit $(C_{+},C_{-})$ in $\mathcal{C}^{\pm}$, the following
pair $(C^{\prime}_{+},C^{\prime}_{-})$ is also a signed circuit in
$\mathcal{C}^{\pm}$, where

$\displaystyle C^{\prime}_{+}$ $\displaystyle:=\\{|\sigma(i)|:i\in C_{+}\text{
and }\epsilon(\sigma(i))=+\\}\sqcup\\{|\sigma(i)|:i\in C_{-}\text{ and
}\epsilon(\sigma(i))=-\\},$ (27) $\displaystyle C^{\prime}_{-}$
$\displaystyle:=\\{|\sigma(i)|:i\in C_{-}\text{ and
}\epsilon(\sigma(i))=+\\}\sqcup\\{|\sigma(i)|:i\in C_{+}\text{ and
}\epsilon(\sigma(i))=-\\}.$

For $\sigma$ in $\text{Aut}(\mathcal{M})$, let $\sigma$ act on
$\mathbf{k}[x_{1},\ldots,x_{n}]$ via

$\sigma(x_{i}):=\epsilon(\sigma(i))\cdot x_{|\sigma(i)|}.$

One can then check that for signed circuits
$(C_{+},C_{-}),(C^{\prime}_{+},C^{\prime}_{-})$ related as in (27), if
$C=C_{+}\cup C_{-}$ and $C^{\prime}=C^{\prime}_{+}\cup C^{\prime}_{-}$, then
the generator $\partial^{\pm}(x_{C})$ for the ideal
$I_{\mathrm{VG}(\mathcal{M})}$ has

$\sigma(\partial^{\pm}(x_{C}))=\pm\partial^{\pm}(x_{C^{\prime}}).$

Consequently, $\sigma$ gives rise to a graded $\mathbf{k}$-algebra
automorphism of $\mathrm{VG}(\mathcal{M})$.

In this way, when $M,\mathcal{M}$ have some group $G$ of automorphisms, we
consider $A=\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ as graded
$\mathbf{k}G$-modules, and study their equivariant Hilbert series as in (12).
Similarly, when these algebras $A$ are Koszul, we will study the equivariant
Hilbert series for their Koszul dual $A^{!}$. Note that in the dual setting,
the dual variables $y_{1},\ldots,y_{n}$ that give a basis for $V^{*}$ obey the
same rules

$\displaystyle\sigma(y_{i})$ $\displaystyle=y_{\sigma(i)}\text{ for
}\mathrm{OS}(M)^{!},$ $\displaystyle\sigma(y_{i})$
$\displaystyle=\epsilon(\sigma(i))\cdot y_{|\sigma(i)|}\text{ for
}\mathrm{VG}(\mathcal{M})^{!}.$

This is because $V^{*}$ carries the contragredient representation to $V$,
where the matrix for the action of $\sigma$ in the basis of
$y_{1},\ldots,y_{n}$ is the inverse transpose $(A^{-1})^{t}$ of the matrix $A$
for its action on $x_{1},\ldots,x_{n}$. However, signed (or unsigned)
permutation matrices $A$ are orthogonal: $(A^{-1})^{t}=A$.

###  5.3. Gröbner bases and broken circuits

It turns out that the above generators for the ideals presenting
$\mathrm{OS}(M)$ and $\mathrm{VG}(\mathcal{M})$ are actually Gröbner bases,
with easily-identified standard monomials.

######  Definition 5.8.

Given a matroid $M$ on $E=\\{1,2,\ldots,n\\}$ and any circuit
$C=\\{c_{1}<c_{2}<\cdots<c_{k}\\}$ in $\mathcal{C}$, the associated broken
circuit is

$C\setminus\\{\min(C)\\}=C\setminus\\{c_{1}\\}=\\{c_{2}<\cdots<c_{k}\\}.$

A subset $I\subset E$ is an NBC (no-broken-circuit) set if it contains none of
the sets $\\{C\setminus\\{\min(C)\\}\\}_{C\in\mathcal{C}}$.

######  Theorem 5.9.

Fix a matroid $M$ and oriented matroid $\mathcal{M}$ on
$E=\\{1,2,\ldots,n\\}$, with circuits $\mathcal{C}$. Choose any monomial
orders $\prec$ on $\wedge(x_{1},\ldots,x_{n})$ and
$\mathbf{k}[x_{1},\ldots,x_{n}]$ having $x_{1}\prec x_{2}\prec\cdots\prec
x_{n}$.

  1. (i)

[Yuzvinsky, Thm. 2.8] The generators
$\mathcal{G}=\\{\partial(x_{C})\\}_{C\in\mathcal{C}}$ in (19) form a Gröbner
basis for $I_{\mathrm{OS}(M)}$ with respect to $\prec$.

  2. (ii)

[Dorpalen-Barry, Thm 1] The generators
$\mathcal{G}=\\{x_{i}^{2}\\}_{i=1}^{n}\cup\\{\partial^{\pm}(x_{C})\\}_{C\in\mathcal{C}}$
in (21) form a Gröbner basis for $I_{\mathrm{VG}(\mathcal{M})}$ with respect
to $\prec$.

Furthermore, in both cases, if $C=\\{c_{1}<c_{2}<\cdots<c_{k}\\}$ in
$\mathcal{C}$, then the $\prec$-initial term
$\mathrm{in}_{\prec}(\partial(x_{C}))$ or
$\mathrm{in}_{\prec}(\partial^{\pm}(x_{C}))$ is the monomial $x_{c_{2}}\cdots
x_{c_{k}}$, supported on the broken circuit associated to $C$. Consequently,
in either case, the $\mathcal{G}$-standard monomials are the NBC monomials

$\\{x_{I}=x_{i_{1}}\cdots x_{i_{\ell}}:\text{NBC sets
}I=\\{i_{1},\ldots,i_{\ell}\\}\subseteq E\\}.$

In particular, $\mathrm{OS}(M)$ and $\mathrm{VG}(\mathcal{M})$ have the same
Hilbert series, given by

$\operatorname{Hilb}(\mathrm{OS}(M),t)=\operatorname{Hilb}(\mathrm{VG}(\mathcal{M}),t)=\sum_{\text{NBC
sets }I\subseteq E}t^{|I|}.$

######  Remark 5.10.

One can readily check that the NBC standard monomial bases for
$\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ respect the flat decompositions
(23), (24) in this sense: for each flat $F\in\mathcal{F}$, the components
$\mathrm{OS}(M)_{F},\mathrm{VG}(M)_{F}$ both have as $\mathbf{k}$-bases the
monomials $\\{x_{I}:I\text{ an NBC set with }\vee_{i\in I}\\{i\\}=F\\}$.

For supersolvable $M$, one has quadratic Gröbner bases, making
$\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ Koszul, as we explain next. Björner,
Edelman and Ziegler [BEZ] gave a useful alternate characterization of the
modular complete flags of flats witnessing supersolvability. To state it,
recall that a flat $F$ with $r(F)=r(M)-1$ is called a coatom in $\mathcal{F}$.
Also recall that for a matroid $M$ on $E$ and subset $A\subseteq E$, the
restriction $M|_{A}$ is the matroid on ground set $A$ defined with circuits
$\\{C\in\mathcal{C}:C\subseteq A\\}.$

######  Proposition 5.11.

[BEZ, Thm. 4.3] Let $M$ be a simple matroid on ground set $E$.

  * (i)

For flats $F$ which are coatoms, being a modular element is equivalent to the
following condition: for any $j\neq k$ in $E\setminus F$, there exists $i$ in
$F$ with $\\{i\\}\leq\\{j\\}\vee\\{k\\}$.

  * (ii)

The flats in a complete flag $\underline{F}=(\varnothing=F_{0}\subsetneq
F_{1}\subsetneq\cdots\subsetneq F_{r(M)-1}\subsetneq F_{r(M)}=E)$ are all
modular if and only if $F_{i-1}$ is a modular coatom within $M|_{F_{i}}$ for
each $i=1,2,\ldots,r(M)$.

Björner and Ziegler [BjornerZiegler] later elaborated on this, proving the
following.

######  Proposition 5.12.

[BjornerZiegler]*Theorem 2.8 Let $M$ be any simple matroid of rank $r$ on
ground set $E$. The following are equivalent:

  1. (i)

$M$ is supersolvable, say with a modular complete flag of flats
$\underline{F}=(F_{i})_{i=0,1,\ldots,r}$.

  2. (ii)

There exists an ordered set partition
$\underline{E}=(E_{1},E_{2},\dots,E_{r})$ of $E=E_{1}\sqcup\cdots\sqcup E_{r}$
such that if $j,k$ in $E_{q}$ with $j\neq k$, then there exists $p<q$ and $i$
in $E_{p}$ with $C=\\{i,j,k\\}$ in $\mathcal{C}$.

  3. (iii)

One can reindex/order $E=\\{1<2<\cdots<n\\}$ so that the minimal broken
circuits (with respect to inclusion) are all of size $2$.

Furthermore, when these conditions hold,

  * (a)

a modular flag $\underline{F}$ as in (i) gives an ordered set partition
$\underline{E}$ as in (ii) via $E_{i}:=F_{i}\setminus F_{i-1}$, and

  * (b)

an ordered set partition $\underline{E}$ as in (ii) gives an ordering $\prec$
on $E$ as in (iii) by extending the partial order that makes elements of
$E_{p}$ come $\prec$-earlier than elements of $E_{q}$ when $p<q$,

  * (c)

the minimal broken circuits with respect inclusion are all pairs of the form
$\\{j,k\\}$ in some set $E_{q}$ for $q=1,2,\ldots,r$; hence the NBC sets
$I\subset E$ are the subsets containing at most one element from each $E_{p}$
for $p=1,2,\ldots,r$.

######  Definition 5.13.

For a supersolvable matroid $M$, with $\underline{F},\underline{E}$ as in
Proposition 5.12, denote by
$\mathcal{C}_{\operatorname{BEZ}}(\underline{E})\subseteq\mathcal{C}$ the
circuits $C=\\{i,j,k\\}$ with $i\in E_{p}$ and $j\neq k\in E_{q}$ for $p<q$
from Proposition 5.12(ii).

######  Corollary 5.14.

Let $M,\mathcal{M}$ be supersolvable simple matroids or oriented matroids on
$E$, with $\underline{E}$ as in Proposition 5.12. Fix a field $\mathbf{k}$,
and monomial orderings $\prec$ on
$\wedge(x_{1},\ldots,x_{n}),\mathbf{k}[x_{1},\ldots,x_{n}]$ with $x_{1}\prec
x_{2}\prec\cdots\prec x_{n}$.

  * •

[Peeva], [Yuzvinsky, §6.3] $I_{\mathrm{OS}(M)}$ has quadratic Gröbner basis
$\mathcal{G}=\\{\partial(x_{C})\\}_{C\in\mathcal{C}_{\operatorname{BEZ}}}$,
where

$\partial(x_{C})=x_{i}\wedge x_{j}-x_{i}\wedge x_{k}+\underline{x_{j}\wedge
x_{k}}.$ (28)

  * •

[Dorpalen-Barry] $I_{\mathrm{VG}(\mathcal{M})}$ has quadratic Gröbner basis
$\mathcal{G}=\\{x_{i}^{2}\\}_{i=1}^{n}\cup\\{\partial^{\pm}(x_{C})\\}_{C\in\mathcal{C}_{\operatorname{BEZ}}}$
where

$\partial^{\pm}(x_{C})={\mathrm{sgn}_{{C},{k}}}\cdot
x_{i}x_{j}+{\mathrm{sgn}_{{C},{j}}}\cdot
x_{i}x_{k}+{\mathrm{sgn}_{{C},{i}}}\cdot\underline{x_{j}x_{k}}.$ (29)

In both cases,

  * •

the $\prec$-initial terms of the elements of $\mathcal{G}$ are shown
underlined above,

  * •

the $\mathcal{G}$-standard monomial basis $\\{x_{I}\\}$ are indexed by the NBC
sets $I\subseteq E$, which are exactly those sets containing at most one
element from each $E_{p}$ for $p=1,2,\ldots,r$,

  * •

$\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ are Koszul algebras,

  * •

with the same Hilbert series

$\operatorname{Hilb}(\mathrm{OS}(M),t)=\operatorname{Hilb}(\mathrm{VG}(\mathcal{M}),t)=(1+e_{1}t)(1+e_{2}t)\cdots(1+e_{r}t)$
(30)

where $e_{p}=|E_{p}|$ for $p=1,2,\ldots,r$.

The integers $(e_{1},e_{2},\ldots,e_{p})$ are often called the exponents of
the supersolvable matroid $M$, due to their connection with the theory of free
hyperplane arrangements and the exponents of reflection arrangements; see
Orlik and Terao [OrlikTerao, §4.2].

###  5.4. Quadratic Gröbner basis for the Koszul dual

We next prove a counterpart to Corollary 5.14 for the Koszul duals $A^{!}$ of
$A=\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ in the supersolvable case. Since
$A=\mathrm{OS}(M)$ or $\mathrm{VG}(\mathcal{M})$ are Koszul algebras, one can
view them as noncommutative quotients $A=\mathbf{k}\langle
x_{1},\ldots,x_{n}\rangle/I$, and form their Koszul duals
$A^{!}=\mathbf{k}\langle y_{1},\ldots,y_{n}\rangle/J$, as in Section 2.
Certain relations in $A^{!}$ will play a key role.

######  Definition 5.15.

Let $M$ be a simple matroid on $E=\\{1,2,\ldots,n\\}$. For each rank two flat
$F\subset E$ and each $j$ in $F$, define an element of
$\mathbf{k}\langle\mathbf{y}\rangle:=\mathbf{k}\langle
y_{1},\ldots,y_{n}\rangle$ by

$\displaystyle r(j,F):=\sum_{k\in
F\setminus\\{j\\}}[y_{j},y_{k}]_{+}=\sum_{k\in
F\setminus\\{j\\}}(y_{j}y_{k}-y_{k}y_{j}).$ (31)

Let $\mathcal{M}$ be a simple oriented matroid on $E=\\{1,2,\ldots,n\\}$. For
each rank two flat $F\subset E$, pick one of the two chirotopes
$\chi_{\mathcal{M}|_{F}}:F^{2}\rightarrow\\{0,\pm 1\\}$ on the restriction
$\mathcal{M}|_{F}$, up to the overall scaling by $\pm 1$. Then for each $j$ in
$F$ define an element of $\mathbf{k}\langle\mathbf{y}\rangle$ by

$\displaystyle r^{\pm}(j,F):=\sum_{k\in
F\setminus\\{j\\}}\chi_{\mathcal{M}|_{F}}(j,k)\cdot[y_{j},y_{k}]_{-}=\sum_{k\in
F\setminus\\{j\\}}\chi_{\mathcal{M}|_{F}}(j,k)\cdot(y_{j}y_{k}+y_{k}y_{j}),$
(32)

.

The relations (31) appear in work of Kohno [kohno1983holonomy] presenting the
holonomy Lie algebra for the complement of any complex hyperplane arrangement;
see Section 8.1 for further discussion. As far as we know, relations (32) are
new. Certain subsets of these relations in (31) or (32) play a distinguished
role in the supersolvable case.

######  Definition 5.16.

Let $M,\mathcal{M}$ be supersolvable simple matroids or oriented matroids, and
$\overline{E}=(E_{1},\ldots,E_{r})$ a choice of an ordered partition of its
ground set $E$ as in Proposition 5.12. Call $(j,i)$ in $E^{2}$ a retrograde
(ordered) pair with respect to $\overline{E}$ if $i\in E_{p}$ and $j\in E_{q}$
with $p<q$.

For each retrograde pair $(j,i)$, let $F:=\\{j\\}\vee\\{i\\}$ be the rank two
flat that they span, and denote by $r(j,i),r^{\pm}(j,i)$ the following two
relations, equivalent to $r(j,F)$ from (31) and $r^{\pm}(j,F)$ from (32):

$\displaystyle r(j,i)$
$\displaystyle:=\underline{y_{j}y_{i}}-y_{i}y_{j}+\sum_{k\in
F\setminus\\{i,j\\}}[y_{j},y_{k}]_{+}.$ (33) $\displaystyle r^{\pm}(j,i)$
$\displaystyle=\underline{y_{j}y_{i}}-y_{i}y_{j}+\chi_{\mathcal{M}|_{F}}(j,i)\sum_{k\in
F\setminus\\{i,j\\}}\chi_{\mathcal{M}|_{F}}(j,k)\cdot[y_{j},y_{k}]_{-}.$ (34)

The following key point will be used in the proofs of Theorems 5.18 and 5.21.

######  Lemma 5.17.

In the context of Definition 5.16 of a retrograde pair $(j,i)$ with $i\in
E_{p}$ and $j\in E_{q}$ for $p<q$, the rank two flat $F:=\\{j\\}\vee\\{i\\}$
has $F\setminus\\{i,j\\}\subset E_{q}$.

Consequently, (33) and (34) can be viewed as rewriting rules that replace the
underlined term $y_{j}y_{i}$ by the term $y_{i}y_{j}$ together with a sum of
monomials $y_{j}y_{k},y_{k}y_{j}$ whose subscripts $j,k$ both lie in $E_{q}$.

###### Proof.

Any $k\in F\setminus\\{i,j\\}$ leads to a circuit $C=\\{i,j,k\\}$ since $M$ is
a simple matroid and $F$ has rank two. As $j>i$, one knows $j\neq\min C$, so
the associated broken circuit $B\subset C$ is either $B=\\{j,i\\}$ or
$B=\\{j,k\\}$. But assertion (c) in Proposition 5.12 implies $B$ contains a
pair lying in some set $E_{q^{\prime}}$. This implies $q^{\prime}=q$, and
$\ell\neq i$ since $i\in E_{p}\neq E_{q}$. Thus $B=\\{j,k\\}$, and $k$ lies in
$E_{q}$. ∎

######  Theorem 5.18.

Let $M,\mathcal{M}$ be matroids and oriented matroids which are supersolvable,
with ground set $E=\\{1,2,\ldots,n\\}$ and $\underline{E}$ as in Proposition
5.12. Consider the Koszul algebras $A=\mathrm{OS}(M)$ or
$\mathrm{VG}(\mathcal{M})$, and their Koszul dual $A^{!}=\mathbf{k}\langle
y_{1},\ldots,y_{n}\rangle/J$. Then there exist monomial orderings $\prec$ on
$\mathbf{k}\langle y_{1},\ldots,y_{n}\rangle$ with these properties.

  1. (i)

$A^{!}=\mathrm{OS}(M)^{!}=\mathbf{k}\langle\mathbf{y}\rangle/J$ has
$\\{r(j,F):j\in F\text{ a rank two flat }\\}$ as a Gröbner basis for $J$, and
a reduced Gröbner basis

$\mathcal{G}:=\\{r(j,i):\text{ retrograde pairs }(j,i)\\}$

with the $\prec$-initial term of $r(j,i)$ underlined in (33).

  2. (ii)

$A^{!}=\mathrm{VG}(\mathcal{M})^{!}=\mathbf{k}\langle\mathbf{y}\rangle/J$ has
$\\{r^{\pm}(j,F):j\in F\text{ a rank two flat }\\}$ as a Gröbner basis for
$J$, and a reduced Gröbner basis

$\mathcal{G}:=\\{r^{\pm}(j,i):\text{ retrograde pairs }(j,i)\\}$

with the $\prec$-initial term of $r^{\pm}(j,i)$ underlined in (34).

In particular,

  * (iii)

their ideals $J$ share the same initial ideal

$\mathrm{in}_{\prec}(J)=(\mathrm{in}_{\prec}(\mathcal{G}))=(\\{y_{j}y_{i}:\text{retrograde
pairs }(i,j)\\}),$

  * (iv)

and hence the same $\mathcal{G}$-standard monomial $\mathbf{k}$-basis for
$A^{!}$, of the form $\\{m_{1}\cdot m_{2}\cdots m_{r-1}\cdot m_{r}\\}$ where
each $m_{p}$ is any noncommutative monomial in the variable set
$\\{y_{j}\\}_{j\in E_{p}}$,

  * (v)

and they have the same Hilbert series

$\operatorname{Hilb}(\mathrm{OS}(M)^{!},t)=\operatorname{Hilb}(\mathrm{VG}(\mathcal{M})^{!},t)=\frac{1}{(1-e_{1}t)(1-e_{2}t)\cdots(1-e_{r}t)}$
(35)

where $e_{p}=|E_{p}|$ are the exponents from Corollary 5.14.

###### Proof.

First let us specify a monomial order $\prec$ on $\mathbf{k}\langle
y_{1},\ldots,y_{n}\rangle$ for which the underlined terms in (33), (34) are
their $\prec$-initial terms. Recall that our indexing has $i<j$ for each
retrograde pair $(j,i)$. We claim that it suffices to let $\prec$ be a graded
version of a lexicographic order having $y_{1}\succ y_{2}\succ\cdots\succ
y_{n}$ that reads monomials from the right. More precisely, this means that
for two unequal monomials

$\displaystyle m=y_{i_{1}}\cdots y_{i_{d}},$ $\displaystyle
m^{\prime}=y_{j_{1}}\cdots y_{j_{e}},$

one has $m\prec m^{\prime}$ if either $\deg(m)=d<e=\deg(m^{\prime})$, or if
$d=e$ and there exists some $k\in\\{1,2,\ldots,d\\}$ with
$i_{d}=j_{d},i_{d-1}=j_{d-1},\ldots,i_{k+1}=j_{k+1}$ but $i_{k}>j_{k}$. It
follows from Lemma 5.17 that for any retrograde pair $(j,i)$ with
$F=\overline{\\{j,i\\}}$, every $k$ in $F\setminus\\{i,j\\}$ lies in $E_{q}$,
so that $k>i$ and $y_{j}y_{k}\prec y_{j}y_{i}$. Since also $j>i$, this makes
$y_{j}y_{i}$ the $\prec$-initial term in either (33) or (34).

We next check that the relations $r(j,F),r^{\pm}(j,F)$ lie in
$J_{2}=I_{2}^{\perp}\subset V^{*}\otimes V^{*}$, with the pairing defined by
$(y_{i}y_{j},x_{k}x_{\ell})=\delta_{(i,j),(k,\ell)}$. We do the check here for
$r^{\pm}(j,F)$; the check for $r(j,F)$ is similar, but slightly easier. One
must check that $r^{\pm}(j,F)$ is orthogonal to three types of generators of
$I$ in $\mathrm{VG}(\mathcal{M})=\mathbf{k}\langle\mathbf{x}\rangle/I$:

$\displaystyle x_{k}^{2}$ $\displaystyle\text{ for }k=1,2,\ldots,n,$ (36)
$\displaystyle x_{k}x_{\ell}-x_{\ell}x_{k}$ $\displaystyle\text{ for }1\leq
k\leq\ell\leq n,$ (37)
$\displaystyle\partial^{\pm}(C):={\mathrm{sgn}_{{C},{m}}}x_{k}x_{\ell}+{\mathrm{sgn}_{{C},{\ell}}}x_{k}x_{m}+{\mathrm{sgn}_{{C},{k}}}x_{\ell}x_{m}$
$\displaystyle\text{ for circuits }C=\\{k,\ell,m\\}\text{ of size three.}$
(38)

Note that $r^{\pm}(j,F)$ pairs to zero with any commutator in (37), because
$r^{\pm}(j,F)$ is a sum of anti-commutators
$[y_{a},y_{b}]_{-}=y_{a}y_{b}+y_{b}y_{a}$. Note also that whenever quadratic
monomials $f(\mathbf{y}),g(\mathbf{x})$ have disjoint $E^{2}$-support sets

$\displaystyle\operatorname{supp}f(\mathbf{y})$ $\displaystyle:=\\{(i,j)\in
E^{2}:y_{i}y_{j}\text{ appears in }f\text{ with nonzero coefficient}\\},$
$\displaystyle\operatorname{supp}g(\mathbf{x})$ $\displaystyle:=\\{(k,\ell)\in
E^{2}:x_{k}x_{\ell}\text{ appears in }f\text{ with nonzero coefficient}\\},$

then one will have $(f(\mathbf{y}),g(\mathbf{x}))=0$. This already implies
$r^{\pm}(j,F)$ pairs to zero with the $x_{k}^{2}$ in (36). It also shows that
in order for $r^{\pm}(j,F)$ to have nonzero pairing with some
$\partial^{\pm}(x_{C})$ in (38), one must have that $C=\\{k,\ell,m\\}$
satisfies $F=\\{k\\}\vee\\{\ell\\}\vee\\{m\\}$, and furthermore one must have
$j\in C$. In other words, without loss of generality, $C=\\{j,\ell,m\\}\subset
F$. It remains to check that $r^{\pm}(j,F)$ still pairs to zero with
$\partial^{\pm}(x_{C})$ in this situation. Calculating the pairing, one finds

$\displaystyle(\partial^{\pm}(x_{C}),r^{\pm}(j,F))$
$\displaystyle=\left({\mathrm{sgn}_{{C},{m}}}x_{j}x_{\ell}+{\mathrm{sgn}_{{C},{\ell}}}x_{j}x_{m}+{\mathrm{sgn}_{{C},{j}}}x_{\ell}x_{m}\,\,,\,\,\sum_{h\in
F\setminus\\{j\\}}\chi_{\mathcal{M}|_{F}}(j,h)\cdot[y_{j},y_{h}]_{-}\right)$
$\displaystyle={\mathrm{sgn}_{{C},{m}}}\cdot\chi_{\mathcal{M}|_{F}}(j,\ell)+{\mathrm{sgn}_{{C},{\ell}}}\cdot\chi_{\mathcal{M}|_{F}}(j,m).$
(39)

Vanishing of the sum in (39) can be checked based on cases for the signed
circuit $C=C_{+}\sqcup C_{-}$ supported by $C=\\{j,\ell,m\\}$. One can relabel
so that $|C_{+}|\geq|C_{-}|$, and hence $(|C_{+}|,|C_{-}|)=(3,0)$ or $(2,1)$.
As the indices $\ell,m$ play a symmetric role in (39), one may assume without
loss of generality that the oriented matroid $\mathcal{M}|_{\\{j,\ell,m\\}}$
matches that of one of these vector configurations in ${\mathbb{R}}^{2}$:

$\ell$$m$$j$$m$$\ell$$j$$m$$j$$\ell$$j$$\ell$$m$

In each case, one can check that the sum in (39) vanishes.

Once one has checked that the elements of $\mathcal{G}$ lie in $J_{2}$,
Proposition 3.5 together with the following Hilbert series calculations will
show that they form a quadratic (noncommutative) GB for $J$. First note that
the $\mathcal{G}$-standard monomials $m$ in $y_{1},\ldots,y_{n}$ are those
that avoid all factors $y_{j}y_{i}$ in which $(j,i)$ are a retrograde pair,
and these are exactly the monomials described in (iv). Thus one has

$\displaystyle\operatorname{Hilb}(\mathbf{k}\langle\mathbf{y}\rangle/(\mathrm{in}_{\prec}(\mathcal{G})),t)$
$\displaystyle=\sum_{\begin{subarray}{c}\mathcal{G}\text{-standard}\\\
\text{monomials }m\end{subarray}}t^{\deg(m)}$
$\displaystyle\overset{(a)}{=}\left(1+e_{1}t+e_{1}^{2}t^{2}+e_{1}^{3}t^{3}+\cdots\right)\cdots\left(1+e_{r}t+e_{r}^{2}t^{2}+e_{r}^{3}t^{3}+\cdots\right)\text{
with }e_{p}=|E_{p}|$ $\displaystyle=\frac{1}{(1-e_{1}t)\cdots(1-e_{r}t)}$
$\displaystyle\overset{(b)}{=}\frac{1}{\operatorname{Hilb}(A,-t)}$
$\displaystyle\overset{(c)}{=}\operatorname{Hilb}(A^{!},t)=\operatorname{Hilb}(\mathbf{k}\langle\mathbf{y}\rangle/J,t).$

where equalities (a), (b), (c) above are justified as follows. Equality (a)
follows from the description in (iv) of $\mathcal{G}$-standard monomials as
$m=m_{1}\cdot m_{2}\cdots m_{r}$ where $m_{p}$ is any noncommutative monomial
in the variable set $\\{y_{j}\\}_{y\in E_{p}}$. Equality (b) comes from (30),
and equality (c) from Corollary 2.7.

Finally, to see that $\mathcal{G}$ is a reduced Gröbner basis, note that Lemma
5.17 implies that for each retrograde pair $(j,i)$, the initial term
$y_{j}y_{i}$ for the relations $r(j,i),r^{\pm}(j,i)$ cannot appear as a term
in any of the other $r(k,\ell),r^{\pm}(k,\ell)$ with $(k,\ell)\neq(j,i)$. ∎

###  5.5. Acyclicity and injectivity

As an application of the Gröbner basis presentations for the algebras
$A^{!}=\mathrm{OS}(M)^{!},\mathrm{VG}(\mathcal{M})^{!}$ in Theorem 5.18, we
explore a counterpart to an interesting fact about
$A=\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$: their Hilbert series contains a
factor of $1+t$,

$\operatorname{Hilb}(\mathrm{OS}(M),t)=\operatorname{Hilb}(\mathrm{VG}(\mathcal{M}),t)=(1+t)\cdot
H(t)$ (40)

and the remaining polynomial factor $H(t)\in{\mathbb{Z}}[t]$ always has
nonnegative coefficients.

This fact has several explanations: combinatorial, topological, and algebraic.
One algebraic explanation views the Orlik-Solomon algebra $A=\mathrm{OS}(M)$
as an algebraic cochain complex

$0\rightarrow
A_{0}\overset{d}{\rightarrow}A_{1}\overset{d}{\rightarrow}\cdots\overset{d}{\rightarrow}A_{r-1}\overset{d}{\rightarrow}A_{r}\rightarrow
0$ (41)

whose differential $d$ is given by multiplication by an element
$x=\sum_{i=1}^{n}c_{i}x_{i}$ in $A_{1}$. The fact that $A$ is a quotient of an
exterior algebra implies that $x^{2}=0$ in $A$, so that indeed $d\circ d=0$.

######  Theorem 5.19.

[Yuzvinsky, Thm. 7.2] The cochain complex (41) on $A=\mathrm{OS}(M)$ is exact
whenever $x=\sum_{i=1}^{n}c_{i}x_{i}$ has coefficients $c_{i}$ satisfying the
following genericity condition: $\sum_{i\in F}c_{i}\neq 0$ in $\mathbf{k}$ for
all flats $F$ whose restriction $M|_{F}$ is not a nontrivial direct sum.

Thus whenever $x$ is generic, multiplication by $x$ on $A=OS(M)$ is “as
injective as possible”, given the constraint that $x^{2}=0$. This
algebraically interprets the factor $H(t)$ in (40), since $tH(t)$ is the
Hilbert series for the subspace of cocycles (= coboundaries) in the above
cochain complex.

For $M,\mathcal{M}$ supersolvable, the Koszul duals
$A^{!}=\mathrm{OS}(M)^{!},\mathrm{VG}(\mathcal{M})^{!}$ inherit a similar
factorization

$\operatorname{Hilb}(A^{!},t)=\frac{1}{\operatorname{Hilb}(A,-t)}=\frac{1}{1-t}\cdot\frac{1}{H(-t)}=(1+t+t^{2}+t^{3}+\cdots)\cdot
H(-t)^{-1}.$ (42)

There is nothing that says, a priori, the rightmost factor $H(-t)^{-1}$ above
should have nonnegative coefficients. However, this is a consequence of our
next result.

######  Definition 5.20.

Let $M,\mathcal{M}$ be supersolvable matroids or oriented matroids of rank $r$
on the ground set $E=\\{1,2,\ldots,n\\}$, with partition $\underline{E}$ as in
Proposition 5.12. For a fixed $d\geq 1$, say that the power sum
$p_{d}(\mathbf{y})=\sum_{i=1}^{n}c_{i}y_{i}^{d}\in A^{!}_{d}\subset
A^{!}=\mathrm{OS}(M)^{!}$ or $\mathrm{VG}(\mathcal{M})^{!}$ is E-generic if
for each $q=1,2,\ldots,r$, there exists $i\in E_{q}$ with the coefficient
$c_{i}\neq 0$.

######  Theorem 5.21.

Let $M,\mathcal{M}$ be supersolvable matroids or oriented matroids of rank $r$
on $E$, with partition $\underline{E}$ as in Proposition 5.12. Then for either
$A^{!}=\mathrm{OS}(M)^{!}$ or $\mathrm{VG}(\mathcal{M})^{!}$, right-
multiplication $a\longmapsto ay$ by any E-generic element $p_{d}(\mathbf{y})$
in $A^{!}_{d}$ gives an injective map $A^{!}\longrightarrow A^{!}$. That is,
every $\underline{E}$-generic $y$ is a right-non-zero-divisor on $A$.

###### Proof.

Proceed by induction on the rank $r$. In the base case $r=1$, the ring
$A^{!}=\mathbf{k}\langle y\rangle\cong\mathbf{k}[y]$ is a univariate
polynomial ring, and $y^{d}$ is a nonzero element of $A^{!}_{d}$, so $y^{d}$
is a nonzero divisor.

Preparing for the inductive step, segregate $E=F\sqcup E_{r}$ where
$F:=F_{r-1}=E_{1}\sqcup E_{2}\sqcup\cdots\sqcup E_{r-1}$ is the modular coatom
in the modular flag $\underline{F}$, and define the early and late variables:

$\\{y_{1},\ldots,y_{n}\\}=\underbrace{\\{y_{i}\\}_{i\in
F}}_{\text{early}}\,\,\sqcup\,\,\underbrace{\\{y_{j}\\}_{j\in
E_{r}}}_{\text{late}}.$

Note that, by Theorem 5.11, the restriction $M|_{F}$ is a rank $r-1$
supersolvable matroid to which induction applies. Also, note that the
presentations in Theorem 5.18 and the standard monomial bases show that the
early variables generate a subalgebra of $A^{!}$ isomorphic to the Koszul dual
$\mathrm{OS}(M|_{F})^{!}$ or $\mathrm{VG}(\mathcal{M}|_{F})^{!}$.

The standard monomial basis shows that every $a$ in $A^{!}$ has a unique
decomposition

$a=\sum_{m}a(m)\cdot m$ (43)

where $m$ runs over all monomials in the late variables, and each $a(m)$ lies
in the subalgebra generated by the early variables. Grouping this more
coarsely via $\deg(m)$, one obtains a unique decomposition

$a=\sum_{\ell=0}^{\infty}a^{(\ell)}\quad\text{ where
}a^{(\ell)}:=\sum_{\begin{subarray}{c}m:\\\
\deg(m)=\ell\end{subarray}}a(m)\cdot m.$ (44)

In particular,
$p_{d}(\mathbf{y})=\sum_{i=1}^{n}c_{i}y_{i}^{d}=y^{(0)}+y^{(d)}.$

Let $A^{!}_{(\ell)}$ denote the set of elements of the form $a^{(\ell)}$
above, so there is a $\mathbf{k}$-vector space decomposition

$A^{!}=\bigoplus_{\ell=0}^{\infty}A^{!}_{(\ell)}$

and also define

$A^{!}_{(\geq\ell)}:=\bigoplus_{p=\ell}^{\infty}A^{!}_{(p)}=A^{!}_{(\ell)}\oplus
A^{!}_{(\geq\ell+1)}.$ (45)

We will use these two facts, justified below:

$\displaystyle A^{!}_{(0)}\cdot A^{!}_{(0)}$ $\displaystyle\subseteq
A^{!}_{(0)},$ $\displaystyle A^{!}_{(\geq p)}\cdot A^{!}_{(\geq q)}$
$\displaystyle\subseteq A^{!}_{(\geq p+q)}.$

These follow ultimately from Lemma 5.17, as we now explain. One can use the
Gröbner basis relations $r(j,i),r^{\pm}(j,i)$ for retrograde pairs $(j,i)$
appearing in Theorem 5.18 as rewriting rules, performing the division
$f\rightarrow_{\mathcal{G}}r$ and rewriting $f$ as a sum $r$ of
$\mathcal{G}$-standard monomials. Lemma 5.17 implies that at each division
step, one is always replacing

  * •

quadratic initial terms with no late variables by a sum of terms with no late
variables,

  * •

quadratic initial terms with one late variable by a sum of terms with one or
two late variables.

Continuing the inductive step, assume $a\in A_{q}^{!}$ has $a\cdot
p_{d}(\mathbf{y})=0$, and we want to conclude that $a=0$. Writing
$a=\sum_{\ell=0}^{q}a^{(\ell)}$ as in (44), we will show each $a^{(\ell)}=0$
via an inner induction on $\ell$.

In the inner induction base case $\ell=0$, write

$0=a\cdot p_{d}(\mathbf{y})={a^{(0)}\cdot y^{(0)}}+\underbrace{a^{(0)}\cdot
y^{(d)}+\sum_{\ell=1}^{q}a^{(\ell)}\cdot p_{d}(\mathbf{y})}_{\in A^{!}_{(\geq
d)}}.$

so that $0\equiv a^{(0)}\cdot y^{(0)}\bmod A^{!}_{(\geq d)}$. By the direct
sum decomposition (45), this means $a^{(0)}\cdot y^{(0)}=0$. By induction on
the rank applied to $M|_{F}$, since $y^{(0)}$ is still generic for $M|_{F}$,
this implies $a^{(0)}=0$.

In the inner inductive step, assume $a\cdot p_{d}(\mathbf{y})=0$ and that
$a^{(0)}=a^{(1)}=\cdots=a^{(\ell-1)}=0$, that is, $a$ lies in
$A^{!}_{(\geq\ell)}$. We wish to show that $a^{(\ell)}=0$. Write

$\displaystyle 0=a\cdot y$
$\displaystyle=(a^{(\ell)}+a^{(\ell+1)}+\cdots)\cdot(y^{(0)}+y^{(1)})$
$\displaystyle=a^{(\ell)}\cdot y^{(0)}+\underbrace{a^{(\ell)}\cdot
y^{(d)}+(a^{(\ell+1)}+a^{(\ell+2)}+\dots)\cdot p_{d}(\mathbf{y})}_{\in
A^{!}_{(\geq\ell+1)}}$

so that $0\equiv a^{(\ell)}\cdot y^{(0)}\bmod A^{!}_{(\geq\ell+d)}$.

Write $a^{(\ell)}=\sum_{m}a(m)m$ as in (44), so that $m$ runs through all
degree $\ell$ monomials in the late variables. Note that for any early
variable $y_{i}$ and any monomial $m$ of degree $\ell$ in the late variables,
the division algorithm $f\rightarrow_{\mathcal{G}}r$ and the form of the
relations $r(j,i),r^{\pm}(j,i)$ in $\mathcal{G}$ (again using Lemma 5.17) will
rewrite

$m\cdot y_{i}^{d}\equiv y_{i}^{d}\cdot m\bmod A^{!}_{(\geq\ell+d)}.$

Since $y^{(0)}$ is a sum of early variables, similarly $m\cdot y^{(0)}\equiv
y^{(0)}\cdot m\bmod A^{!}_{(\geq\ell+d)},$ which implies

$\displaystyle a^{(\ell)}\cdot y^{(0)}=\sum_{m}a(m)\cdot m\cdot
y^{(0)}\equiv\sum_{m}a(m)\cdot y^{(0)}\cdot m\bmod A^{!}_{(\geq\ell+d)}$

Hence one concludes that $0\equiv\sum_{m}a(m)\cdot y^{(0)}\cdot m\bmod
A^{!}_{(\geq\ell+d)}$. Since $\sum_{m}a(m)\cdot y^{(0)}\cdot m$ lies in
$A^{!}_{(\ell)}$, by the direct sum decomposition (45), it must vanish. But by
the uniqueness in (43), this implies each $a(m)\cdot y^{(0)}=0$. Then by
induction on $r$, each $a(m)=0$. Hence $a^{(\ell)}=0$, as desired. ∎

One has the following corollary to Theorems 5.19 and 5.21.

######  Corollary 5.22.

Let $M,\mathcal{M}$ be a matroid or oriented matroid, and $G$ a group of
automorphisms, that is, a subgroup of $\text{Aut}(M)$ or
$\text{Aut}(\mathcal{M})$. Consider $G$ as a group of $\mathbf{k}$-algebra
automorphisms of $A:=\mathrm{OS}(M)$ or $\mathrm{VG}(\mathcal{M})$.

  1. (i)

Any $x\in A_{1}$ which is $G$-fixed and generic in the sense of Theorem 5.19
(e.g., $x=\sum_{i=1}^{n}x_{i}$ when $\mathbf{k}$ has characteristic zero)
gives rise to a factorization in $R_{\mathbf{k}}(G)[[t]]$

$\operatorname{Hilb}_{\mathrm{eq}}(\mathrm{OS}(M),t)=(1+t)\cdot H(t)$

where $tH(t)$ is the equivariant Hilbert series for the cocycles
(=coboundaries) of the $\mathbf{k}G$-module complex in (41).

  2. (ii)

Assuming that $M$ is supersolvable with decomposition $\underline{E}$ as in
Proposition 5.12, any $y\in A^{!}_{1}$ which is $G$-fixed and
$\underline{E}$-generic (e.g., $y=\sum_{i=1}^{n}y_{i}$) gives a factorization
in $R_{\mathbf{k}}(G)[[t]]$

$\operatorname{Hilb}_{\mathrm{eq}}(\mathrm{OS}(M)^{!},t)=\frac{1}{1-t}\cdot
H^{!}(t)$

where $H^{!}(t)$ is the equivariant Hilbert series for the quotient
$\mathbf{k}G$-module $A^{!}/A^{!}y$.

  3. (iii)

Assuming that $\mathcal{M}$ is supersolvable with decomposition
$\underline{E}$ as in Proposition 5.12, any $p_{2}(\mathbf{y})\in A^{!}_{2}$
which is $G$-fixed and $\underline{E}$-generic (e.g.,
$p_{2}(\mathbf{y})=\sum_{i=1}^{n}y_{i}^{2}$) gives a factorization in
$R_{\mathbf{k}}(G)[[t]]$

$\operatorname{Hilb}_{\mathrm{eq}}(\mathrm{VG}(\mathcal{M})^{!},t)=\frac{1}{1-t^{2}}\cdot
H^{!}(t)$

where $H^{!}(t)$ is the equivariant Hilbert series for the quotient
$\mathbf{k}G$-module $A^{!}/A^{!}\cdot p_{2}(\mathbf{y})$.

Examples of the factorizations in the various parts of Corollary 5.22 appear
later:

  * •

Part (i) is illustrated by (48), (51) (57).

  * •

Part (ii) is illustrated by (49), (52), (58).

  * •

Part (iii) is illustrated by (53), (79).

##  6\. Examples: Boolean matroids and matroids of low rank

Before developing further theory for supersolvable matroids and oriented
matroids, we digress to discuss the action of symmetries in a few of our
earlier examples, illustrating the results so far.

###  6.1. Boolean matroids

We return to Example 4.5 and the Boolean matroid $M=U_{n,n}$. Although
$M=U_{n,n}$ is orientable, we will focus here on $\mathrm{OS}(M)$, where a bit
more is known about the action of symmetries, rather than on
$\mathrm{VG}(\mathcal{M})$. The discussion of $\mathrm{VG}(\mathcal{M})$ is
deferred to Example 8.10 later.

The Boolean matroid $M$ of of rank $n$ has no circuits, so
$A=\mathrm{OS}(M)=\wedge V=\wedge(x_{1},\ldots,x_{n})$, and
$A^{!}=\mathrm{OS}(M)^{!}=\operatorname{Sym}V=\mathbf{k}[y_{1},\ldots,y_{n}]$,
swapping the roles of $A,A^{!}$ from Examples 2.4, 2.6, 2.8. Here
$\text{Aut}(M)=\mathfrak{S}_{n}$, and both $V,V^{*}$ carry the defining
representation of $\mathfrak{S}_{n}$ permuting the subscripts of the variables
$x_{i}$ or $y_{i}$.

Thus $V$ is the defining representation of $\mathfrak{S}_{n}$ by permutation
matrices. Assuming that $\mathbf{k}$ has characteristic zero, $V,V^{*}$ both
decompose into irreducible $\mathbf{k}\mathfrak{S}_{n}$-modules as

$V\cong V^{*}\cong\mathcal{S}^{(n)}\oplus\mathcal{S}^{(n-1,1)}$

where $\mathcal{S}^{\lambda}$ denotes the simple
$\mathbf{k}\mathfrak{S}_{n}$-module indexed by a partition $\lambda$ of $n$;
here $\mathcal{S}^{(n)}$ is the trivial $\mathfrak{S}_{n}$-representation,
while $\mathcal{S}^{(n-1,1)}$ is the irreducible reflection representation of
$\mathfrak{S}_{n}$. Consequently, in this situation,

$\displaystyle A$
$\displaystyle=\wedge(\mathcal{S}^{(n)}\oplus\mathcal{S}^{(n-1,1)})=\wedge\mathcal{S}^{(n)}\otimes\wedge\mathcal{S}^{(n-1,1)}$
(46) $\displaystyle A^{!}$
$\displaystyle=\operatorname{Sym}(\mathcal{S}^{(n)}\oplus\mathcal{S}^{(n-1,1)})=\operatorname{Sym}\mathcal{S}^{(n)}\otimes\operatorname{Sym}\mathcal{S}^{(n-1,1)},$
(47)

and the factorizations in Corollary 5.22 become

$\displaystyle\operatorname{Hilb}_{\mathrm{eq}}(A,t)$
$\displaystyle=(1+t)\operatorname{Hilb}_{\mathrm{eq}}(\wedge\mathcal{S}^{(n-1,1)},t)$
(48) $\displaystyle\operatorname{Hilb}_{\mathrm{eq}}(A^{!},t)$
$\displaystyle=\frac{1}{1-t}\operatorname{Hilb}_{\mathrm{eq}}(\operatorname{Sym}\mathcal{S}^{(n-1,1)},t).$
(49)

Both (48) and (49) can be refined to explicit
$\mathbf{k}\mathfrak{S}_{n}$-irreducible expansions. For (48), since it is
known that $\wedge^{i}\mathcal{S}^{(n-1,1)}\cong\mathcal{S}^{(n-i,1^{i})}$,
one has

$\operatorname{Hilb}_{\mathrm{eq}}(\wedge\mathcal{S}^{(n-1,1)},t)=\sum_{i=0}^{n-1}[\mathcal{S}^{(n-i,1^{i})}]\,t^{i}.$

For (49), one can extend the tensor decomposition (47). The
$\mathfrak{S}_{n}$-invariant subalgebra of $\mathbf{k}[\mathbf{y}]$ is
$\mathbf{k}[\mathbf{y}]^{\mathfrak{S}_{n}}=\mathbf{k}[e_{1},e_{2},\ldots,e_{n}]$
where $e_{k}=e_{k}(\mathbf{y})$ is the $k^{th}$ elementary symmetric function
in the variables $\mathbf{y}$, and the theory of Cohen-Macaulay rings gives a
graded $\mathbf{k}\mathfrak{S}_{n}$-module tensor product decomposition

$\mathbf{k}[\mathbf{y}]\cong\mathbf{k}[e_{1},e_{2},\ldots,e_{n}]\,\,\otimes\,\,\mathbf{k}[\mathbf{y}]/(e_{1},e_{2},\ldots,e_{n})$

where $\mathbf{k}[\mathbf{y}]/(e_{1},e_{2},\ldots,e_{n})$ is the type $A$
coinvariant algebra. Hence one has

$\displaystyle\operatorname{Hilb}_{\mathrm{eq}}(A^{!},t)$
$\displaystyle=\operatorname{Hilb}(\mathbf{k}[e_{1},e_{2},\ldots,e_{n}],t)\cdot\operatorname{Hilb}_{\mathrm{eq}}(\mathbf{k}[\mathbf{y}]/(e_{1},e_{2},\ldots,e_{n}),t)$
(50)
$\displaystyle=\frac{1}{(1-t)(1-t^{2})\cdots(1-t^{n})}\cdot\sum_{Q}[\mathcal{S}^{\lambda(Q)}]\,t^{\mathrm{maj}(Q)}$

where the sum on the right, due to Lusztig and Stanley [Stanley-invariants,
Prop. 4.11]), has $Q$ running over all standard Young tableaux with $n$ cells,
with $\lambda(Q)$ the partition shape of $Q$, and $\mathrm{maj}(Q)$ the sum of
all entries $i$ in $Q$ for which $i+1$ appears weakly southwest of $i$ (using
English notation for tableaux).

We note for future reference in Section 11.6 that $\mathfrak{S}_{n}$ permutes
the monomial basis $\\{\mathbf{y}^{\mathbf{a}}=y_{1}^{a_{1}}\cdots
y_{n}^{a_{n}}:\mathbf{a}\in{\mathbb{N}}^{n}\\}$ of
$A^{!}=\mathbf{k}[\mathbf{y}]$, making each graded component $A^{!}_{i}$ of
$A^{!}$ a permutation representation.

###  6.2. Rank one matroids

A simple rank one matroid $M$ has ground set $E=\\{e\\}$ of size one and no
circuits. It is always orientable, and has

$\displaystyle A$
$\displaystyle=\mathrm{OS}(M)\cong\mathrm{VG}(\mathcal{M})=\mathbf{k}[x]/(x^{2})$
$\displaystyle A^{!}$ $\displaystyle=\mathbf{k}[y].$

The only difference between $M,\mathcal{M}$ arises when one takes into account
symmetries. The matroid $M$ has no nontrivial automorphisms, while the
oriented matroid $\mathcal{M}$ carries the action of the two-element group
$G=\text{Aut}(\mathcal{M})=\mathfrak{S}^{\pm}_{1}\cong{\mathbb{Z}}/2{\mathbb{Z}}$.
Assuming that the characteristic of $\mathbf{k}$ is not $2$, then the
generator of $G$ negates both $x,y$ when it acts on
$A=\mathrm{VG}(\mathcal{M})=\mathbf{k}[x]/(x^{2})$ or
$A^{!}=\mathrm{VG}(\mathcal{M})^{!}=\mathbf{k}[y]$. Denoting the class of this
nontrivial $1$-dimensional representation by $\epsilon$ in the Grothendieck
ring

$R_{\mathbf{k}}(G)\cong{\mathbb{Z}}[\epsilon]/(\epsilon^{2}-1)$

then in the power series ring $R_{\mathbf{k}}(G)[[t]]$ one has

$\displaystyle\operatorname{Hilb}_{\mathrm{eq}}(\mathrm{OS}(M),t)$
$\displaystyle=1+t,$ (51)
$\displaystyle\operatorname{Hilb}_{\mathrm{eq}}(\mathrm{VG}(\mathcal{M}),t)$
$\displaystyle=1+\epsilon t,$
$\displaystyle\operatorname{Hilb}_{\mathrm{eq}}(\mathrm{OS}(M)^{!},t)$
$\displaystyle=1+t+t^{2}+t^{3}+\cdots=\frac{1}{1-t}$ (52)
$\displaystyle\operatorname{Hilb}_{\mathrm{eq}}(\mathrm{VG}(\mathcal{M})^{!},t)$
$\displaystyle=1+\epsilon
t+\epsilon^{2}t^{2}+\epsilon^{3}t^{3}+\cdots=\frac{1}{1-\epsilon t}$
$\displaystyle=1+\epsilon t+t^{2}+\epsilon t^{3}+\cdots=\frac{1+\epsilon
t}{1-t^{2}}.$ (53)

###  6.3. Rank two matroids

As discussed in Example 4.6, a simple rank two matroid $M$ on ground set
$E=\\{1,2,\ldots,n\\}$ is always orientable, and supersolvable. Any rank $1$
flat, such as $F=\\{1\\}$ is a modular coatom, and one has the corresponding
set partition decomposition
$\underline{E}=(E_{1},E_{2})=(\\{1\\},\\{2,3,\ldots,n\\})$ with
$(e_{1},e_{2})=(1,n-1)$ Therefore,

$\displaystyle\operatorname{Hilb}(\mathrm{OS}(M),t)$
$\displaystyle=\operatorname{Hilb}(\mathrm{VG}(\mathcal{M}),t)=(1+t)(1+(n-1)t)=1+nt+(n-1)t^{2},$
(54) $\displaystyle\operatorname{Hilb}(\mathrm{OS}(M)^{!}!,t)$
$\displaystyle=\operatorname{Hilb}(\mathrm{VG}(\mathcal{M})^{!},t)$
$\displaystyle=\frac{1}{(1-t)(1-(n-1)t)}$
$\displaystyle=1+(1+(n-1))t+(1+(n-1)+(n-1)^{2})t^{2}+\cdots$
$\displaystyle=\sum_{i=0}^{\infty}f(n,i)t^{i}\,\,\text{ where
}f(n,i):=\sum_{j=0}^{i}(n-1)^{i}=\frac{(n-1)^{i+1}-1}{n-2}.$

In considering symmetries, it is somewhat easier to compute with
$\mathrm{OS}(M)$, rather than $\mathrm{VG}(\mathcal{M})$. The matroid $M$ has
as its symmetries the full symmetric group $G=\text{Aut}(M)=\mathfrak{S}_{n}$,
arbitrarily permuting $E=\\{1,2,\ldots,n\\}$. It is also helpful to introduce
a notation $\varphi_{\lambda}$ for the class
$\left[\mathbf{k}[\mathfrak{S}_{n}/\mathfrak{S}_{\lambda}]\right]$ within
$R_{\mathbf{k}}(\mathfrak{S}_{n})$ of the $\mathfrak{S}_{n}$-permutation
representation on the cosets of the Young subgroup
$\mathfrak{S}_{\lambda}:=\mathfrak{S}_{\lambda_{1}}\times\cdots\times\mathfrak{S}_{\lambda_{\ell}}$
where $\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{\ell})$ is a partition
of $n=|\lambda|:=\sum_{i=1}^{\ell}\lambda_{i}$. Hence, if $\mathbf{k}$ were a
field of characteristic zero (which we do not assume here), then this class
$\varphi_{\lambda}$ corresponds to the product of complete homogeneous
symmetric functions

$h_{\lambda}:=h_{\lambda_{1}}\cdots h_{\lambda_{\ell}}$

under the Frobenius characteristic isomorphism
$R_{\mathbf{k}}(\mathfrak{S}_{n})\cong\Lambda_{n}$, where $\Lambda_{n}$ are
the degree $n$ homogeneous symmetric functions
$\Lambda(z_{1},z_{2},\ldots)_{n}$ in infinitely many variables.

One finds that $\mathrm{OS}(M)_{1}$ carries the defining permutation
representation of $\mathfrak{S}_{n}$ permuting coordinates in
$\mathbf{k}^{n}$, whose class in $R_{\mathbf{k}}(\mathfrak{S}_{n})$ is
$\varphi_{(n-1,1)}$. Introducing the $\mathbf{k}\mathfrak{S}_{n}$-submodule

$\mathcal{S}^{(n-1,1)}:=\\{\mathbf{x}\in\mathbf{k}^{n}:x_{1}+\cdots+x_{n}=0\\},$
(55)

the quotient $\varphi_{(n-1,1)}/\mathcal{S}^{(n-1,1)}$ carries the trivial
$\mathbf{k}\mathfrak{S}_{n}$-module $\mathcal{S}^{(n)}$, giving this identity
in $R_{\mathbf{k}}(\mathfrak{S}_{n})$:

$[\mathrm{OS}(M)_{1}]=\varphi_{(n-1,1)}=[\mathcal{S}^{(n)}]+[\mathcal{S}^{(n-1,1)}]=1+[\mathcal{S}^{(n-1,1)}].$
(56)

The Hilbert series in (54) have the following equivariant lifts to
$R_{\mathbf{k}}(\mathfrak{S}_{n})[[t]]$:

$\displaystyle\operatorname{Hilb}_{\mathrm{eq}}(\mathrm{OS}(M),t)$
$\displaystyle=(1+t)(1+[\mathcal{S}^{(n-1,1)}]t)=1+\varphi_{(n-1,1)}t+[\mathcal{S}^{(n-1,1)}]t^{2},$
(57) $\displaystyle\operatorname{Hilb}_{\mathrm{eq}}(\mathrm{OS}(M)^{!},t)$
$\displaystyle=\frac{1}{(1-t)(1-[\mathcal{S}^{(n-1,1)}]t)}$ (58)
$\displaystyle=1+(1+[\mathcal{S}^{(n-1,1)}])t+(1+[\mathcal{S}^{(n-1,1)}]+[\mathcal{S}^{(n-1,1)}]^{2})t^{2}+\cdots$
$\displaystyle=\sum_{i=0}^{\infty}t^{i}\left(\sum_{k=0}^{i}[\mathcal{S}^{(n-1,1)}]^{k}\right)$
(59)

We find the next proposition somewhat unexpected.

######  Proposition 6.1.

In $R_{\mathbf{k}}(\mathfrak{S}_{n})$, the element
$[\mathrm{OS}(M)^{!}_{i}]=\sum_{k=0}^{i}[\mathcal{S}^{(n-1,1)}]^{k}$ is the
class of a permutation representation, expressible in the following form:

$[\mathrm{OS}(M)^{!}_{i}]=\begin{cases}\varphi_{(n)}+\displaystyle\sum_{d=2}^{i}a_{d,i}\,\varphi_{(n-d,1^{d})},&i\text{
even},\\\
\varphi_{(n-1,1)}+\displaystyle\sum_{d=2}^{i}b_{d,i}\,\varphi_{(n-d,1^{d})},&i\text{
odd},\end{cases}$

where $\\{a_{d,i}\\},\\{b_{d,i}\\}$ are positive integers, independent of $n$,
given by sums of Stirling numbers:

$\displaystyle a_{d,i}$
$\displaystyle=\sum_{k=\lfloor\frac{d}{2}\rfloor}^{\frac{i}{2}}S(2k-1,d-1)\text{
for }i\text{ even,}$ $\displaystyle b_{d,i}$
$\displaystyle=\sum_{k=\lfloor\frac{d-1}{2}\rfloor}^{\frac{i-1}{2}}S(2k,d-1)\text{
for }i\text{ odd.}$

###### Proof.

The following identity is established in [Sundaram-reflection-rep, Prop. 7.6,
Thm 7.7] for $j\geq 2$.

$[\mathcal{S}^{(n-1,1)}]^{j}+[\mathcal{S}^{(n-1,1)}]^{j-1}=\sum_{d=2}^{j}S(j-1,d-1)\,\,\varphi_{(n-d,1^{d})}.$
(60)

Since the proofs in [Sundaram-reflection-rep] are phrased in terms of
symmetric functions, over a ground field of characteristic zero, we explain
why this identity still holds in the Grothendieck ring
$R_{\mathbf{k}}(\mathfrak{S}_{n})$ for arbitrary fields $\mathbf{k}$. Sundaram
constructs an explicit $\mathbf{k}\mathfrak{S}_{n}$-module realizing the $j$th
tensor power of the $\mathfrak{S}_{n}$-permutation module $V_{1,n}$, whose
class is $\varphi_{(n-1,1)}$, and decomposes it in terms of the coset
permutation submodules
$V_{d,n}=\left(\mathbf{k}\mathfrak{S}_{d}\right)\uparrow_{\mathfrak{S}_{n-d}\times\mathfrak{S}_{1}^{d}}^{\mathfrak{S}_{n}}$
whose class is $\varphi_{(n-d,1^{d})}$, obtaining [Sundaram-reflection-rep,
Eqn. 18, Lemma. 6.1])

$V_{1,n}^{\otimes j}=\sum_{d=1}^{\min{(n,j)}}S(j,d)\,V_{d,n}.$ (61)

In addition we will use the following three facts (1),(2),(3).

  1. (1)

$[\mathcal{S}^{(n-1,1)}\downarrow^{\mathfrak{S}_{n}}_{\mathfrak{S}_{n-1}\times\mathfrak{S}_{1}}]=[V_{1,n-1}]$.
We show this as follows.

First, if $\mathcal{S}^{(n-1)}$ is the span of a fixed standard basis vector,
and $V_{1,n-1}$ is the span of the $n-1$ non-fixed standard basis vectors, we
clearly have $V_{1,n}\downarrow=\mathcal{S}^{(n-1)}\oplus V_{1,n-1},$ which in
turn gives

$[V_{1,n}\downarrow]=[\mathcal{S}^{(n-1)}]+[V_{1,n-1}].$ (62)

Now recall the definition in (55) of $\mathcal{S}^{(n-1,1)}$ and the
Grothendieck group identity (56). The discussion around (55) and (56) in
effect establishes the existence of a short exact sequence of
$\mathbf{k}\mathfrak{S}_{n}$-modules

$0\rightarrow\mathcal{S}^{(n-1,1)}\rightarrow
V_{1,n}\rightarrow\mathcal{S}^{(n)}\rightarrow 0,$

which restricts to the same sequence as
$(\mathfrak{S}_{n-1}\times\mathfrak{S}_{1})$-modules. Hence we have

$[V_{1,n}\downarrow]=[\mathcal{S}^{(n)}\downarrow]+[\mathcal{S}^{(n-1,1)}\downarrow]$
(63)

Since $\mathcal{S}^{(n)}\\!\downarrow\,=\mathcal{S}^{(n-1)}$, comparing (62)
and (63) we obtain $[\mathcal{S}^{(n-1,1)}\downarrow]=[V_{1,n-1}].$

  2. (2)

[webb, Corollary 4.3.8, Part (2)] Transitivity of induction;

  3. (3)

[webb, Corollary 4.3.8, Part (4)] For a finite group $G$ and subgroup $H$, and
$\mathbf{k}G$-module $U$, $\mathbf{k}H$-module $V$, over any field
$\mathbf{k}$,

$U\otimes(V\uparrow_{H}^{G})\,\cong(U\downarrow_{H}\otimes
V)\uparrow_{H}^{G}.$

In the present situation we have $G=\mathfrak{S}_{n}$,
$H=\mathfrak{S}_{n-1}\times\mathfrak{S}_{1}$,
$V=1_{\mathfrak{S}_{n-1}\times\mathfrak{S}_{1}}$, so that the class of
$V\uparrow_{H}^{G}$ is $\varphi_{(n-1,1)}$, and
$U={\mathcal{S}^{(n-1,1)}}^{\otimes j-1}$. Following the proof of [Sundaram-
reflection-rep, Prop. 7.6]), we have

$\displaystyle[\mathcal{S}^{(n-1,1)}]^{j}+[\mathcal{S}^{(n-1,1)}]^{j-1}$
$\displaystyle=[\mathcal{S}^{(n-1,1)}]^{j-1}\left([\mathcal{S}^{(n)}]+[\mathcal{S}^{(n-1,1)}]\right)$
$\displaystyle=[U\otimes V_{1,n}]\quad\text{ by \eqref{defining-S_n-rep-
decomposed} and definition of }U,$
$\displaystyle=[U\otimes\left(\mathbb{1}_{H}\right)\uparrow_{H}^{G}]\quad\text{
by definition of }H,G,V_{1,n},$
$\displaystyle=[\left(U\downarrow^{G}_{H}\right)\uparrow_{H}^{G}]\quad\text{
by item (3) above,}$
$\displaystyle=\left[\left((\mathcal{S}^{(n-1,1)})^{\otimes(j-1)}\downarrow^{\mathfrak{S}_{n}}_{\mathfrak{S}_{1}\times\mathfrak{S}_{n-1}}\right)\uparrow_{\mathfrak{S}_{1}\times\mathfrak{S}_{n-1}}^{\mathfrak{S}_{n}}\right]$
$\displaystyle=[V_{1,n-1}^{\otimes
j-1}\uparrow_{\mathfrak{S}_{1}\times\mathfrak{S}_{n-1}}^{\mathfrak{S}_{n}}]\
\text{by item (1) above,}$
$\displaystyle=\sum_{d^{\prime}=1}^{\min{(n-1,j-1)}}S(j-1,d^{\prime})\,[V_{d^{\prime},n-1}\big{\uparrow}_{\mathfrak{S}_{n-1}}^{\mathfrak{S}_{n}}]\
\text{using~{}\eqref{eqn:Eq.18-Lemma6.1-Sun21}}$
$\displaystyle=\sum_{d^{\prime}=1}^{\min{(n-1,j-1)}}S(j-1,d^{\prime})\,[V_{d^{\prime}+1,n}]\
\text{by item (2) above,}$
$\displaystyle=\sum_{d=2}^{\min{(n,j)}}S(j-1,d-1)\,[V_{d,n}].$

Hence for $i\geq 2$, we have

$\displaystyle=\sum_{k=0}^{i}[\mathcal{S}^{(n-1,1)}]^{k}$
$\displaystyle=\begin{cases}[\mathcal{S}^{(n)}]+\sum_{k=1}^{i/2}\left([\mathcal{S}^{(n-1,1)}]^{2k}+[\mathcal{S}^{(n-1,1)}]^{2k-1}\right),&i\text{
even},\\\
[\mathcal{S}^{(n)}]+[\mathcal{S}^{(n-1,1)}]+\sum_{k=1}^{(i-1)/2}\left([\mathcal{S}^{(n-1,1)}]^{2k+1}+[\mathcal{S}^{(n-1,1)}]^{2k}\right),&i\text{
odd},\end{cases}$
$\displaystyle=\begin{cases}\varphi_{(n)}+\sum_{k=1}^{i/2}\,(\sum_{d=2}^{2k}S(2k-1,d-1)\,\varphi_{(n-d,1^{d})}),&i\text{
even},\\\
\varphi_{(n-1,1)}+\sum_{k=1}^{(i-1)/2}\,(\sum_{d=2}^{2k+1}S(2k,d-1)\,\varphi_{(n-d,1^{d})}),&i\text{
odd}.\end{cases}$

Interchanging the order of summation then gives the assertion of the
proposition for $i\geq 2$. For $i=0,1$ it is easy to check that
$[\mathrm{OS}(M)^{!}_{0}]=\varphi_{(n)}$ and
$[\mathrm{OS}(M)^{!}_{1}]=\varphi_{(n-1,1)}$. ∎

######  Remark 6.2.

Rather than all of $\mathfrak{S}_{n}$, one might restrict the action on
$\mathrm{OS}(M)$ to the dihedral group666 These are symmetries of the rank two
oriented matroid $\mathcal{M}$, although we are ignoring the action on
$\mathrm{VG}(\mathcal{M})$ here.

$W=I_{2}(n)=\langle r,s:r^{n}=s^{2}=1,srs=r^{-1}\rangle$

of order $2n$. Since $\mathfrak{S}_{n}$ acts on each $\mathrm{OS}(M)^{!}_{i}$
via permutation representations, the same must hold for $W$ by restriction.
One can check via character computations (omitted here) that
$\mathrm{OS}(M)^{!}_{i}$ is always a nonnegative combination of these four
permutation representations:

  * •

the trivial representation,

  * •

the defining representation $\rho_{\mathrm{def}}$ on $E=\\{1,2,\ldots,n\\}$
with $r=(12\cdots n)$, $s(i)=n+1-i$,

  * •

the regular representation $\rho_{\mathrm{reg}}:=\mathbf{k}W$, and

  * •

when $n$ is even, the half-regular representation
$\rho_{\frac{1}{2}\mathrm{reg}}:=\mathbf{k}[W/Z_{W}]$ where
$Z_{W}:=\\{1,r^{\frac{n}{2}}\\}$.

One has these expansions in $R_{\mathbf{k}}(W)$, where
$f(n,i):=\dim_{\mathbf{k}}\mathrm{OS}^{!}_{i}=\frac{(n-1)^{i+1}-1}{n-2}$ as in
(54):

$[\mathrm{OS}(M)^{!}_{i}]=\begin{cases}\frac{1}{2n}\left[f(n,i)-1\right]\cdot\rho_{\mathrm{reg}}+1&\text{
if }n\text{ is odd, and }i\text{ is even},\\\
\frac{1}{2n}\left[f(n,i)-n\right]\cdot\rho_{\mathrm{reg}}+\rho_{\mathrm{def}}&\text{
if }n\text{ is odd, and }i\text{ is odd},\\\ &\\\
\frac{1}{n}\left[f(n,i)-n\cdot\frac{i}{2}-1\right]\cdot\rho_{\frac{1}{2}\mathrm{reg}}+\frac{i}{2}\cdot\rho_{\mathrm{def}}+1&\text{
if }n\text{ is even, and }i\text{ is even},\\\
\frac{1}{n}\left[f(n,i)-n\cdot\frac{i+1}{2}\right]\cdot\rho_{\frac{1}{2}\mathrm{reg}}+\frac{i+1}{2}\cdot\rho_{\mathrm{def}}&\text{
if }n\text{ is even, and }i\text{ is odd}.\\\ \end{cases}$

######  Remark 6.3.

It was observed earlier that uniform matroids $U_{r,n}$ are supersolvable if
and only if $r\in\\{1,2,n\\}$. This means that $M=U_{3,n}$ for $n\geq 4$ are
not supersolvable, and in fact, $A=\mathrm{OS}(M)$ are not Koszul algebras,
and not even quadratic. If one nevertheless tries to define virtual
$\mathfrak{S}_{n}$-characters $\\{[A^{!}_{i}]\\}_{i\geq 0}$ in terms of the
genunine characters $\\{[A_{i}]\\}_{i\geq 0}$ via the recurrence (15), then
already $[A^{!}_{3}]$ are not genuine characters once $n\geq 4$.

##  7\. Branching rules for supersolvable matroids

Let $M,\mathcal{M}$ be supersolvable matroids or oriented matroids of rank $r$
on ground set $E$, with a modular complete flag $\underline{F}$ and
decomposition $\underline{E}$ as in Proposition 5.12. If $F=F_{r-1}$ denotes
the modular coatom within the flag $\overline{F}$, then the restrictions
$M|_{F},\mathcal{M}|_{F}$ are again supersolvable. Furthermore, the formulas
(30), (35) for the Hilbert series of the rings
$A=\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$ and their Koszul duals $A^{!}$
show that they are closely related to the Hilbert series of the same rings
$B,B^{!}$ for $M|_{F},\mathcal{M}|_{F}$:

$\displaystyle\operatorname{Hilb}(A,t)=(1+e_{1}t)\cdots(1+e_{r-1}t)(1+e_{r}t)$
$\displaystyle=\operatorname{Hilb}(B,t)\cdot(1+e_{r}t)$
$\displaystyle\operatorname{Hilb}(A^{!},t)=\frac{1}{(1-e_{1}t)\cdots(1-e_{r-1}t)(1-e_{r}t)}$
$\displaystyle=\operatorname{Hilb}(B^{!},t)\cdot\frac{1}{1-e_{r}t}$

which one can rewrite suggestively as follows, for comparison with Proposition
2.16:

$\displaystyle\operatorname{Hilb}(A,t)$
$\displaystyle=\operatorname{Hilb}(B,t)+t\cdot
e_{r}\cdot\operatorname{Hilb}(B,t)$ (64)
$\displaystyle\operatorname{Hilb}(A^{!},t)$
$\displaystyle=\operatorname{Hilb}(B^{!},t)+t\cdot
e_{r}\cdot\operatorname{Hilb}(A^{!},t).$ (65)

This suggests considering a group $G$ of automorphisms of $M$ or
$\mathcal{M}$, and how its action on $A,A^{!}$ restricts to the setwise
$G$-stabilizer subgroup of the modular coatom $F$

$H:=\\{g\in G:g(F)=F\\}.$

Note that $H$ also permutes the ground set elements $E_{r}:=E\setminus F$; in
the case where $G$ acts on the oriented matroid $\mathcal{M}$, so that $G$
acts via signed permutations in $\mathfrak{S}_{n}^{\pm}$ on $E$ as in
Definition 5.7, then $H$ acts via signed permutations on $E_{r}$. This gives
rise to either a permutation or signed permutation $\mathbf{k}H$-module
$\mathcal{X}:=\mathbf{k}[E_{r}]$, which in particular is self-contragredient.
Our goal in the next two subsections is to prove Theorem 7.1 below, which not
only lifts (64), (65) to these two branching relations in $R_{\mathbf{k}}(H)$

$\displaystyle[A_{i}\downarrow]$
$\displaystyle=[B_{i}]+[{\mathcal{X}}]\cdot[B_{i-1}]$ (66)
$\displaystyle[A^{!}_{i}\downarrow]$
$\displaystyle=[B^{!}_{i}]+[{\mathcal{X}}]\cdot\left([A^{!}_{i-1}\downarrow]\right).$
(67)

(equivalent by Proposition 2.16 as $\mathcal{X}^{*}\cong\mathcal{X}$ ), but
also lifts them to short exact sequences.

######  Theorem 7.1.

With the above notations, and letting $\mathbf{k}$ be any field, one has the
following short exact sequences of graded $\mathbf{k}H$-modules:

  * (i)

$0\longrightarrow B\longrightarrow
A\downarrow^{G}_{H}\longrightarrow\mathcal{X}\otimes B(-1)\longrightarrow 0,$

  * (ii)

$0\longrightarrow\mathcal{X}\otimes\left(A^{!}\downarrow^{G}_{H}\right)(-1)\longrightarrow
A^{!}\downarrow^{G}_{H}\longrightarrow B^{!}\longrightarrow 0.$

###  7.1. Proof of Theorem 7.1(i)

The injective maps $B\rightarrow A$ from Theorem 7.1(i) are instances of
injections of Orlik-Solomon and Varchenko-Gel’fand algebras coming from their
flat deocmpositions

$\displaystyle\mathrm{OS}(M)$
$\displaystyle=\bigoplus_{F\in\mathcal{F}}\mathrm{OS}(M)_{F},$
$\displaystyle\mathrm{VG}(\mathcal{M})$
$\displaystyle=\bigoplus_{F\in\mathcal{F}}\mathrm{OS}(M)_{F}$

discussed in Section 5.1. The NBC monomial $\mathbf{k}$-bases from Remark 5.10
show that for any flat $F$ in $\mathcal{F}$, one has $\mathbf{k}$-algebra
inclusions (see [OrlikTerao, Prop. 3.30], [Yuzvinsky, Prop. 2.5], and
[Brauner, Prop. 5.6])

$\displaystyle\mathrm{OS}(M|_{F})\cong\bigoplus_{F^{\prime}\leq
F}\mathrm{OS}(M)_{F^{\prime}}\hookrightarrow\mathrm{OS}(M),$
$\displaystyle\mathrm{VG}(\mathcal{M}|_{F})\cong\bigoplus_{F^{\prime}\leq
F}\mathrm{VG}(\mathcal{M})_{F^{\prime}}\hookrightarrow\mathrm{VG}(\mathcal{M}).$

Since $A=\mathrm{OS}(M)$ or $\mathrm{VG}(\mathcal{M})$ and
$B=\mathrm{OS}(M|_{F})$ or $\mathrm{VG}(\mathcal{M}|_{F})$, this explains the
injection $B\rightarrow A$ from the sequence Theorem 7.1(i). In fact, the
entire sequence actually holds in slightly more generality, and for Orlik-
Solomon algebras was essentially observed by Orlik and Terao [OrlikTerao,
Lemma 3.80]. One does not need to assume that $M,\mathcal{M}$ are
supersolvable, only that $F$ is a modular coatom within its lattice of flats
$\mathcal{F}$. Keeping the same notations so that
$A=\mathrm{OS}(M),\mathrm{VG}(\mathcal{M})$, and
$B=\mathrm{OS}(M|_{F}),\mathrm{VG}(\mathcal{M}|_{F})$, with $H$ the setwise
$G$-stabilizer of $F$ with a group of the autmorphisms $G$, one has the
following.

######  Proposition 7.2.

Any modular coatom $F$ gives rise to a $\mathbf{k}$-vector space direct sum
decomposition

$A=B\oplus\left(\bigoplus_{j\in E\setminus F}Bx_{j}\right),$

which can also be viewed as a graded $\mathbf{k}H$-module isomorphism

$A\downarrow^{G}_{H}\,\,\cong\,\,B\,\,\oplus\,\,{\mathcal{X}}\otimes B(-1),$

where ${\mathcal{X}}$ is the permutation or signed permutation representation
of $H$ on $E\setminus F$ as before.

###### Proof.

First note a consequence of Theorem 5.11: if one orders/indexes
$E=\\{1,2,\ldots,n\\}$ so that $i<j$ whenever $i\in F$ and $j\in E\setminus
F$, then every pair $\\{j,k\\}\subseteq E\setminus F$ with $j\neq k$ is a
broken-circuit, coming from the $3$-element circuit $\\{i,j,k\\}$ with
$\\{i\\}:=F\cap(\\{j\\}\vee\\{k\\})$. This implies NBC subsets for $M$ contain
at most one element $j$ of $E\setminus F$, so NBC monomials for $M$ are either
of the form

  * (a)

$x_{i_{1}}\cdots x_{i_{p}}$ for NBC sets $\\{i_{1},\ldots,i_{p}\\}\subseteq
F$, or

  * (b)

$x_{i_{1}}\cdots x_{i_{p}}x_{j}$ for NBC sets
$\\{i_{1},\ldots,i_{p}\\}\subseteq F$, and $j\in E\setminus F$.

Identifying $B$ with $\bigoplus_{F^{\prime}\subseteq
F}\mathrm{OS}(M)_{F^{\prime}}$ or $\bigoplus_{F^{\prime}\subseteq
F}\mathrm{VG}(\mathcal{M})_{F^{\prime}}$ expresses $A$ as a
$\mathbf{k}$-vector space sum

$A=B+\left(\sum_{j\in E\setminus F}Bx_{j}\right).$

However, these sums are direct, via dimension-counting: if $e:=|E\setminus
F|$, then one has

$\dim_{\mathbf{k}}A=\dim_{\mathbf{k}}B(1+e)$

as the $t=1$ specialization of the identity
$\operatorname{Hilb}(A,t)=\operatorname{Hilb}(B,t)(1+et)$ (cf. (64) above)
which follows either from Stanley [Stanley-modular, Thm. 2] or from Orlik and
Terao [OrlikTerao, Lem. 3.80].

Note that this dimension count also implies that the NBC monomials in (a),(b)
above form $\mathbf{k}$-bases for $B$ and $\bigoplus_{j\in E\setminus
F}Bx_{j}$, respectively. This lets one write a $\mathbf{k}$-vector space
isomorphism

${\mathcal{X}}\otimes B\overset{f}{\longrightarrow}\bigoplus_{j\in E\setminus
F}Bx_{j}$

as follows: naming the $\mathbf{k}$-basis elements $\\{t_{j}:j\in E\setminus
F\\}$ for the permutation or signed permutation representation ${\mathcal{X}}$
of $H$, let the isomorphism $f$ map $t_{j}\otimes x_{i_{1}}\cdots
x_{i_{p}}\longmapsto x_{i_{1}}\cdots x_{i_{p}}x_{j}$. Since this means that
$f(t_{j}\otimes b)=bx_{j}$ for $b\in B$, the $H$-equivariance follows from
this calculation: by definition, $g\in H$ has $g(t_{j})=\pm t_{k}$ for $j,k\in
E\setminus F$ if and only if $g(x_{j})=\pm x_{k}$, with the same $\pm$ signs
for both. ∎

###  7.2. Proof of Theorem 7.1(ii)

The surjective map $A^{!}\rightarrow B^{!}$ within the exact sequence of
Theorem 7.1(ii) is simple to define. As before, let $M,\mathcal{M}$ be
supersolvable matroids or oriented matroids on ground set
$E=\\{1,2,\ldots,n\\}$ and let $\underline{E}$ be as in Proposition 5.12, with
$F=F_{r-1}=E_{1}\sqcup\cdots\sqcup E_{r-1}$ and $E_{r}=E\setminus F$. Let
$A^{!}=\mathrm{OS}(M)^{!}$ or $\mathrm{VG}(\mathcal{M})^{!}$, and
$B^{!}=\mathrm{OS}(M|_{F})^{!}$ or $\mathrm{VG}(\mathcal{M}|_{F})^{!}$.

######  Proposition 7.3.

The surjective $\mathbf{k}$-algebra map

$\begin{array}[]{rcll}\mathbf{k}\langle
y_{1},\ldots,y_{n}\rangle&\longrightarrow&\mathbf{k}\langle
y_{i}\rangle_{i\not\in E_{r}}&\\\ y_{i}&\longmapsto&y_{i}&\text{ if }i\not\in
E_{r}\\\ y_{j}&\longmapsto&0&\text{ if }j\in E_{r},\end{array}$

induces a surjective $\mathbf{k}$-algebra map $A^{!}\twoheadrightarrow B^{!}$.

###### Proof.

Check that in the quadratic Gröbner basis presentation of Theoerem 5.18 for
$A^{!}$, if a quadratic term is divisible by a variable $y_{j}$ with $j\in
E_{r}$, then every term is divisible by such a variable. ∎

It only remains to identify the kernel of the surjection in Proposition 7.3.
Recall that $H$ is the setwise $G$-stabilizer subgroup for the modular coatom
$F$, and $\mathcal{X}$ is the permutation or signed permutation representation
of $H$ as it acts on $E_{r}$, with the $\mathbf{k}$-basis of $\mathcal{X}$
denoted $\\{t_{j}\\}_{j\in E_{r}}$.

######  Proposition 7.4.

The $\mathbf{k}$-linear map

$\begin{array}[]{rcl}{\mathcal{X}}\otimes A^{!}&\longrightarrow&A^{!}\\\
t_{j}\otimes y_{i_{1}}\cdots y_{i_{p}}&\longmapsto&y_{i_{1}}\cdots
y_{i_{p}}y_{j}\end{array}$

is injective, with image equal to the kernel of the surjection
$A^{!}\twoheadrightarrow B^{!}$ in Proposition 7.3.

###### Proof.

Since the surjection $A^{!}\twoheadrightarrow B^{!}$ is induced by sending the
variables $\\{y_{j}\\}_{j\in E_{r}}$ to zero, its kernel is the two-sided
ideal $I=(y_{j}:j\in E_{r})\subset A^{!}$ that they generate. As in the proof
of Theorem 5.21, the presentation for $A^{!}$ described in Theorem 5.18 and
its standard monomial $\mathbf{k}$-basis identify this ideal $I$ as
$A^{!}_{(\geq 1)}$, the span of standard monomials $m_{1}\cdots m_{2}\cdots
m_{r-1}\cdot m_{r}$ with $m_{p}$ in the variable set $\\{y_{j}\\}_{j\in
E_{p}}$ that have $\deg(m_{r})\geq 1$. Classifying such standard monomials
according to their rightmost variable $y_{j}$ shows that $I=A^{!}_{(\geq 1)}$
is the image of the map in the current proposition. The standard monomial
basis for $A^{!}$ also shows that this map is injective. ∎

Noting that the maps in Propositions 7.3 and 7.4 are both $H$-equivariant
proves Theorem 7.1(ii).

##  8\. Homotopy and holonomy Lie algebras

In Section 2, we defined a standard graded $\mathbf{k}$-algebra to be Koszul
if it had a (left-)free resolution of $\mathbf{k}=A/A_{+}$ which is linear. It
turns out (see [PolishchukPositselski, Section 2.1]) that this definition is
equivalent to any of the following conditions:

  1. (a)

$\operatorname{Ext}^{i}_{A}(\mathbf{k},\mathbf{k})_{j}=0$ for $i\neq j$,

  2. (b)

$A$ is quadratic and
$A^{!}\cong\operatorname{Ext}^{\bullet}_{A}(\mathbf{k},\mathbf{k})$,

  3. (c)

$A$ is quadratic and
$(A_{i}^{!})^{\ast}\cong\text{Tor}_{i}^{A}(\mathbf{k},\mathbf{k})$,

  4. (d)

$A$ is generated by $A_{1}$ and the algebra
$\operatorname{Ext}_{A}^{\bullet}(\mathbf{k},\mathbf{k})$ is generated by
$\operatorname{Ext}^{1}_{A}(\mathbf{k},\mathbf{k})$.

The next proposition explains why quadratic algebras $A$ that are either
commutative or anti-commutative have quadratic duals $A^{!}$ which inherit a
Hopf algebra structure from the tensor algebra, making $A^{!}$ the universal
enveloping algebra of a graded Lie (super)-algebra. It can be considered an
elaboration on [PolishchukPositselski, §I.2 Examples 4,5].

######  Proposition 8.1.

When a quadratic algebra $A$ is anti-commutative (resp. commutative), its
quadratic dual $A^{!}$ is not just a $\mathbf{k}$-algebra, but actually a co-
commutative Hopf algebra. Hence by the Cartier-Milnor-Moore Theorem, $A^{!}$
is the universal enveloping algebra $\mathcal{U}(\mathcal{L})$ of the graded
Lie algebra (resp. Lie superalgebra) $\mathcal{L}\subset A^{!}$ which is its
$\mathbf{k}$-subspace of primitive elements.

###### Proof.

Since $A^{!}:=\mathbf{k}\langle\mathbf{y}\rangle/J$ for a two-sided (algebra)
ideal $J$, it suffices to check that $J$ is also a co-ideal for the co-product
$\Delta$ on the Hopf algebra $H:=\mathbf{k}\langle\mathbf{y}\rangle=T(V)$,
that is, $\Delta(J)\subseteq H\otimes J+J\otimes H$. We give the argument for
the case where $A$ is commutative; the anti-commutative case is similar.

Since $J=HJ_{2}H$ is generated as a two-sided ideal by $J_{2}$, and since
$\Delta:H\rightarrow H\otimes H$ is an algebra morphism, it suffices to check
that $\Delta(J_{2})\subseteq H\otimes J+J\otimes H$. Note that since the
quadratic algebra $A=\mathbf{k}\langle\mathbf{x}\rangle/I$ is commutative, it
must be that $I=(I_{2})$ has $I_{2}$ containing the $\mathbf{k}$-span of all