# Packed words and quotient rings

Daniël Kroes and Brendon Rhoades  Department of Mathematics
University of California, San Diego
La Jolla, CA, 92093-0112, USA<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The coinvariant algebra is a quotient of the polynomial ring
$\mathbb{Q}[x_{1},\ldots,x_{n}]$ whose algebraic properties are governed by
the combinatorics of permutations of length $n$. A word $w=w_{1}\dots w_{n}$
over the positive integers is packed if whenever $i>2$ appears as a letter of
$w$, so does $i-1$. We introduce a quotient $S_{n}$ of
$\mathbb{Q}[x_{1},\ldots,x_{n}]$ which is governed by the combinatorics of
packed words. We relate our quotient $S_{n}$ to the generalized coinvariant
rings of Haglund, Rhoades, and Shimozono as well as the superspace coinvariant
ring.

##  1\. Introduction

Consider the polynomial ring
$\mathbb{Q}[\mathbf{x}_{n}]:=\mathbb{Q}[x_{1},\ldots,x_{n}]$ in $n$ variables.
The symmetric group $\mathfrak{S}_{n}$ acts on $\mathbb{Q}[\mathbf{x}_{n}]$ by
variable permutation. It is known that the corresponding invariant subring
$\mathbb{Q}[\mathbf{x}_{n}]^{\mathfrak{S}_{n}}$ of _symmetric functions_ has
algebraically independent homogeneous generators
$e_{1}(\mathbf{x}_{n}),\ldots,e_{n}(\mathbf{x}_{n})$, where

$e_{d}:=\sum_{1\leq i_{1}<\ldots<i_{d}\leq n}x_{i_{1}}\cdots x_{i_{d}}$

is the degree $d$ _elementary symmetric polynomial_. The _invariant ideal_ is
the ideal generated by the symmetric functions with constant term:

$I_{n}:=\langle\mathbb{Q}[\mathbf{x}_{n}]_{+}^{\mathfrak{S}_{n}}\rangle=\langle
e_{1},\ldots,e_{n}\rangle.$

The _coinvariant algebra_ $R_{n}:=\mathbb{Q}[x_{n}]/I_{n}$ has long been
studied. In particular, as ungraded $\mathfrak{S}_{n}$-module
$R_{n}\cong_{\mathfrak{S}_{n}}\mathbb{Q}[\mathfrak{S}_{n}]$ coincides with the
regular representation of $\mathfrak{S}_{n}$. Moreover, the Hilbert series
$\mathrm{Hilb}(R_{n};q)=(1+q)(1+q+q^{2})\cdots(1+q+\ldots+q^{n-1})$ coincides
with the generating function of both the inversion and major index statistic
on permutations.

Traditionally studied in physics, the superspace ring $\Omega_{n}$ has
received significant recent attention in coinvariant theory [9, 11]. For a
positive integer $n$, superspace of rank $n$ is the tensor product

$\Omega_{n}:=\mathbb{Q}[x_{1},\dots,x_{n}]\otimes\wedge\\{\theta_{1},\dots,\theta_{n}\\}$

of a rank $n$ polynomial ring with a rank $n$ exterior algebra. The group
$\mathfrak{S}_{n}$ acts diagonally on $\Omega_{n}$, viz. $w.x_{i}:=x_{w(i)}$,
$w.\theta_{i}:=\theta_{w(i)}$. Let
$(\Omega_{n})^{\mathfrak{S}_{n}}_{+}\subseteq\Omega_{n}$ denote the space of
$\mathfrak{S}_{n}$-invariants with vanishing constant term and let
$\langle(\Omega_{n})^{\mathfrak{S}_{n}}_{+}\rangle\subseteq\Omega_{n}$ be the
ideal generated by this subspace. Considering commuting and anticommuting
variables separately, the superspace coinvariant ring
$\Omega_{n}/\langle(\Omega_{n})^{\mathfrak{S}_{n}}_{+}\rangle$ carries a
bigraded action of $\mathfrak{S}_{n}$. One recovers the classical coinvariant
algebra by setting the $\theta$-variables to zero.

The Combinatorics Group and the Fields Institute conjectured (see [11]) a
formula for the bigraded $\mathfrak{S}_{n}$-Frobenius image type of the
superspace coinvariant ring. Let $\mathrm{SYT}(n)$ be the family of standard
Young tableaux with $n$ boxes. Given $T\in\mathrm{SYT}(n)$, let
$\mathrm{des}(T)$ be the number of descents in $T$ and let $\mathrm{maj}(T)$
be its major index. We use the $q$-analog notation

$[n]_{q}:=1+q+\cdots+q^{n-1},\quad[n]!_{q}:=[n]_{q}[n-1]_{q}\cdots[1]_{q},\quad{n\brack
k}_{q}:=\frac{[n]!_{q}}{[k]!_{q}\cdot[n-k]!_{q}}.$

The Fields Group conjectured [11] that

(1.1)
$\mathrm{grFrob}(\Omega_{n}/\langle(\Omega_{n})^{\mathfrak{S}_{n}}_{+}\rangle;q,z)=\sum_{k=1}^{n}z^{n-k}\cdot
C_{n,k}(\mathbf{x};q)$

where

(1.2)
$C_{n,k}(\mathbf{x};q):=\sum_{T\in\mathrm{SYT}(n)}q^{\mathrm{maj}(T)+{n-k\choose
2}+(n-k)\cdot\mathrm{des}(T)}{\mathrm{des}(T)\brack
n-k}_{q}s_{\mathrm{shape}(T)^{\prime}}(\mathbf{x}).$

Here $s_{\mathrm{shape}(T)^{\prime}}(\mathbf{x})$ is the Schur function
corresponding to the conjugate of the shape of $T$.

The symmetric function $C_{n,k}(\mathbf{x};q)$ appearing in Equation (1.1) has
appeared in the literature before. Combinatorially, it is the $t=0$
specialization of the function $\Delta^{\prime}_{e_{k-1}}e_{n}$ appearing in
the Haglund-Remmel-Wilson Delta Conjecture [4, 3]. Algebraically, it is (up to
a minor twist) the graded Frobenius image of the generalized coinvariant
algebras $R_{n,k}$ introduced by Haglund-Rhoades-Shimozono [5]. Geometrically,
it is (up to the same minor twist) the graded Frobenius image of the
cohomology representation afforded by the $\mathfrak{S}_{n}$-action on the
variety $X_{n,k}$ of $n$-tuples of lines $(\ell_{1},\dots,\ell_{n})$ spanning
$\mathbb{C}^{k}$ [7]. Despite these varied interpretations of
$C_{n,k}(\mathbf{x};q)$, the formula (1.1) remains conjectural as of this
writing.

Whereas algebraic properties of the classical coinvariant ring are governed by
permutations, the superspace coinvariants appear to be governed by packed
words. A word $w=w_{1}\dots w_{n}$ over the positive integers is packed if,
for all $i>0$, whenever $i+1$ appears as a letter in $w$, so does $i$. Let
$\mathcal{W}_{n}$ be the family of packed words of length $n$. For example, we
have

$\mathcal{W}_{3}=\\{123,213,132,231,312,321,112,121,211,122,212,221,111\\}.$

Packed words in $\mathcal{W}_{n}$ are in natural bijection with the family
$\mathcal{OP}_{n}$ of all ordered set partitions of $[n]$ and have appeared in
various settings including Hopf algebras [6] and polytopes [1].

The symmetric group $\mathfrak{S}_{n}$ acts on the set $\mathcal{W}_{n}$ by
letter permutation. The conjecture (1.1) implies that

(1.3)
$\Omega_{n}/\langle(\Omega_{n})^{\mathfrak{S}_{n}}_{+}\rangle\cong\mathbb{Q}[\mathcal{W}_{n}]\otimes\mathrm{sign}$

as ungraded $\mathfrak{S}_{n}$-modules, where $\mathrm{sign}$ is the
1-dimensional sign representation of $\mathfrak{S}_{n}$. Proving the
isomorphism (1.3) remains an open problem. Even the dimension equality
$\dim\Omega_{n}/\langle(\Omega_{n})^{\mathfrak{S}_{n}}_{+}\rangle=|\mathcal{W}_{n}|$
is presently out of reach.

Motivated by the conjecture (1.1), we define the following family of singly-
graded $\mathfrak{S}_{n}$-modules $S_{n}$ which provably have vector space
dimension $|\mathcal{W}_{n}|$ and satisfy algebraic properties similar to
(1.3) and (1.1). We let
$e_{d}^{(i)}:=e_{d}(x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{n})$ be the degree
$d$ elementary symmetric polynomial with the variable $x_{i}$ omitted.

######  Definition 1.1.

Let $J_{n}\subseteq\mathbb{Q}[\mathbf{x}_{n}]$ be the ideal

$J_{n}=\langle x_{i}^{d}\cdot e_{n-r}^{(i)}\ :\ 1\leq i\leq n,\,1\leq r\leq
d\rangle$

and let $S_{n}:=\mathbb{Q}[\mathbf{x}_{n}]/J_{n}$ be the corresponding
quotient ring.

By convention, the degree 0 elementary symmetric polynomial is 1, so that
$J_{n}$ contains the variable powers $x_{i}^{n}$. Additionally, we use the
convention that $e_{d}\equiv 0$ for $d<0$.

Although the generators of the ideal $J_{n}$ may appear unusual, they will
arise naturally from the perspective of orbit harmonics as follows. More
precisely, suppose $X\subseteq\mathbb{Q}^{n}$ is a finite locus of points.
Consider the ideal

(1.4)
$\mathbf{I}(X):=\\{f\in\mathbb{Q}[\mathbf{x}_{n}]\,:\,f(\mathbf{x})=0\text{
for all $\mathbf{x}\in X$}\\}$

of polynomials in $\mathbb{Q}[\mathbf{x}_{n}]$ which vanish on $X$ and let

(1.5) $\mathbf{T}(X):=\langle\tau(f)\,:\,f\in\mathbf{I}(X)-\\{0\\}\rangle,$

where $\tau(f)$ denotes the highest degree component of a nonzero polynomial
$f\in\mathbb{Q}[\mathbf{x}_{n}]$. The homogeneous ideal $\mathbf{T}(X)$ is the
associated graded ideal of $\mathbf{I}(X)$ and we have isomorphisms of
$\mathbb{Q}$-vector spaces

(1.6)
$\mathbb{Q}[X]\cong\mathbb{Q}[\mathbf{x}_{n}]/\mathbf{I}(X)\cong\mathbb{Q}[\mathbf{x}_{n}]/\mathbf{T}(X)$

which are isomorphisms of ungraded $\mathfrak{S}_{n}$-modules when $X$ is
closed under the natural action of $\mathfrak{S}_{n}$ on $\mathbb{Q}^{n}$; the
quotient $\mathbb{Q}[\mathbf{x}_{n}]/\mathbf{T}(X)$ has the additional
structure of a graded $\mathfrak{S}_{n}$-module.

Given $n$ distinct rational parameters $\alpha_{1},\dots,\alpha_{n}$, we have
a natural point locus $X_{n}\subseteq\mathbb{Q}^{n}$ in bijection with
$\mathcal{W}_{n}$, namely

(1.7)
$X_{n}=\\{(\beta_{1},\dots,\beta_{n})\in\mathbb{Q}^{n}\,:\,\\{\beta_{1},\dots,\beta_{n}\\}=\\{\alpha_{1},\dots,\alpha_{k}\\}\text{
for some $k$}\\}.$

It will develop that

(1.8) $\mathbf{T}(X_{n})=J_{n}.$

In other words, the quotient
$S_{n}=\mathbb{Q}[\mathbf{x}_{n}]/\mathbf{T}(X_{n})$ is the graded quotient of
$\mathbb{Q}[\mathbf{x}_{n}]$ arising from the packed word locus $X_{n}$.
Equation (1.8) may be viewed as a more natural, if less computationally
useful, alternative to Definition 1.1. We prove the following facts regarding
the module $S_{n}$.

  * •

The ungraded $\mathfrak{S}_{n}$-structure of $S_{n}$ coincides with the
natural $\mathfrak{S}_{n}$-action on $\mathcal{W}_{n}$ (without sign twist)

(1.9) $S_{n}\cong\mathbb{Q}[\mathcal{W}_{n}].$

  * •

The graded $\mathfrak{S}_{n}$-structure is described by

(1.10)
$\mathrm{grFrob}(S_{n};q)=\sum_{k=1}^{n}q^{n-k}\cdot(\mathrm{rev}_{q}\circ\omega)C_{n,k}(\mathbf{x};q).$

Here $\mathrm{rev}_{q}$ is the operator on polynomials in $q$ which reverses
their coefficient sequences and $\omega$ is the symmetric function involution
which trades $e_{n}(\mathbf{x})$ for $h_{n}(\mathbf{x})$.

Finding an algebraic explanation for the similarity between the provable
(1.10) and the conjectural (1.1) could shed light on a proof of (1.1).

The outline of the paper is as follows. In Section 2 we cover some of the
necessary background, including symmetric functions, representation theory of
the symmetric group, and Gröbner theory. In Section 3 we describe a bijection
between ordered set partitions in $\mathcal{OP}_{n}$ and certain sequences
$(c_{1},\dots,c_{n})$ of nonnegative integers. This bijection will translate
to a bijection between a monomial basis of $S_{n}$ and $\mathcal{W}_{n}$. In
Section 4 we use this bijection to prove (1.9) and its graded refinement
Equation (1.10). In Section 5 we end with some concluding remarks and open
questions.

##  2\. Background

###  2.1. Symmetric functions and the representation theory of
$\mathfrak{S}_{n}$

A _partition_ $\lambda$ of size $n$, denoted $\lambda\vdash n$, is a sequence
$\lambda=(\lambda_{1},\ldots,\lambda_{m})$ of integers
$\lambda_{1}\geq\ldots\geq\lambda_{m}>0$ with
$\lambda_{1}+\ldots+\lambda_{m}=n$.

Let $\mathbf{x}=(x_{1},x_{2},x_{3},\ldots)$ be an infinite set of variables
and let $\Lambda\subseteq\mathbb{Q}[[\mathbf{x}]]$ be the _ring of symmetric
functions_. It is known that the degree $n$ homogeneous piece of $\Lambda$ has
a basis given by the _Schur functions_ $s_{\lambda}(\mathbf{x})$ where the
index $\lambda$ ranges over all partitions of size $n$. For thorough
definitions of the ring of symmetric functions and Schur functions, we refer
to [10].

We will now recall the fundamentals of the representation theory of
$\mathfrak{S}_{n}$. The irreducible representations of $\mathfrak{S}_{n}$ are
naturally in bijections with the partitions $\lambda\vdash n$. For every such
$\lambda$, the corresponding irreducible $\mathfrak{S}_{n}$-module is denoted
by $S^{\lambda}$.

Consequently, every $\mathfrak{S}_{n}$-module $V$ decomposes as

$V=\bigoplus_{\lambda\vdash n}\left(S^{\lambda}\right)^{c_{\lambda}}$

for some integers $c_{\lambda}\geq 0$. The _Frobenius character_ of $V$ is the
symmetric function

$\mathrm{Frob}(V)=\sum_{\lambda\vdash n}c_{\lambda}\cdot
s_{\lambda}(\mathbf{x}).$

Lastly, let $V$ be a graded vector space such that for every $d\geq 0$ the
degree $d$ homogeneous component $V_{d}$ is finite dimensional. The _Hilbert
series_ of $V$ is the power series in $q$ given by

$\mathrm{Hilb}(V;q)=\sum_{d\geq 0}\dim(V_{d})\cdot q^{d}.$

If further $V$ carries a graded $\mathfrak{S}_{n}$-action, we define the
_graded Frobenius character_ by

$\mathrm{grFrob}(V;q)=\sum_{d\geq 0}\mathrm{Frob}(V_{d})\cdot q^{d}.$

More details on the representation theory of $\mathfrak{S}_{n}$ can be found
in [10].

###  2.2. Gröbner theory

In this section we will review some of the Gröbner theory used in this paper.
The main starting point of Gröbner theory is a polynomial ring
$k[\mathbf{x}_{n}]$ over a field $k$ equipped with a total order $<$ on its
monomials that satisfies:

  * 1.

$1\leq m$ for any monomial $m$;

  * 2.

for monomials $m_{1}<m_{2}$ and any monomial $m$ we have $m\cdot m_{1}<m\cdot
m_{2}$.

Such a total order is called a _monomial order_. Given a monomial order $<$,
for any $0\neq f\in k[\mathbf{x}_{n}]$ we define the _leading monomial_
$\mathrm{LM}(f)$ as the monomial $m$ such that $m$ has nonzero coefficient in
$f$ and $n\leq m$ for any monomial $n$ with nonzero coefficient in $f$. For an
ideal $I\leq k[\mathbf{x}_{n}]$ we set $\mathrm{LM}(I)$ as the ideal generated
by the leading monomials of all non-zero $f\in I$.

We know [2] that a basis for the $k$-vector space $k[\mathbf{x}_{n}]/I$ is
given by all monomials $m$ that do not belong to $\mathrm{LM}(I)$, which is
equivalent to $m$ not being divisible by any monomial of the form $LM(f)$ with
$f\in I$. This basis for $k[\mathbf{x}_{n}]/I$ is called the _standard
monomial basis_ with respect to the total order $<$.

The monomial order on $\mathbb{Q}[\mathbf{x}_{n}]$ used in this paper is the
_lexicographic order_. In this order, two monomials $m_{1}=x_{1}^{a_{1}}\cdots
x_{n}^{a_{n}}$ and $m_{2}=x_{1}^{b_{1}}\cdots x_{n}^{b_{n}}$ are compared as
follows. Assuming $m_{1}\neq m_{2}$, let $j\in\\{1,2,\ldots,n\\}$ be minimal
such that $a_{j}\neq b_{j}$, then $m_{1}<m_{2}$ if and only if $a_{j}<b_{j}$.

##  3\. The combinatorial bijection

In this section we will establish a bijection between ordered set partitions
and coinversion codes. The starting point will be a bijection established by
Rhoades and Wilson [8, Thm. 2.2]. Let $\mathcal{OP}_{n,k}$ be the family of
ordered set partitions $(B_{1}\mid\cdots\mid B_{k})$ of $[n]$ into $k$ blocks.
Given an ordered set partition $\sigma=(B_{1}\ |\ \cdots\ |\
B_{k})\in\mathcal{OP}_{n,k}$, define a sequence
$\mathbf{code}(\sigma)=(c_{1},\ldots,c_{n})$ as follows. If $1\leq i\leq n$
and $i\in B_{j}$, then

$c_{i}=\begin{cases}|\\{\ell>j\ :\ \min(B_{\ell})>i\\}|&\text{if
}i=\min(B_{j});\\\ |\\{\ell>j\ :\ \min(B_{\ell})>i\\}|+(j-1)&\text{if
}i\neq\min(B_{j}).\end{cases}$

The sequence $\mathbf{code}(\sigma)$ was called the coinversion code of
$\sigma$ in [8]. This is a variant of the classical Lehmer code on
permutations in the case $k=n$.

The coinversion $\mathbf{code}(\sigma)$ of ordered set partitions
$\sigma\in\mathcal{OP}_{n,k}$ were characterized in [8] as follows. Given a
subset $S=\\{s_{1}<\cdots<s_{d}\\}\subseteq[n]$, define the skip sequence by
$\gamma(S)=(\gamma_{1},\dots,\gamma_{n})$ where

(3.1) $\gamma_{i}=\begin{cases}i-j+1&\text{if $i=s_{j}\in S$}\\\ 0&\text{if
$i\notin S$.}\end{cases}$

Also let $\gamma(S)^{*}=(\gamma_{n},\dots,\gamma_{1})$ be the reverse skip
sequence. For example, if $n=7$ and $S=\\{2,3,6\\}$ we have
$\gamma(S)=(0,2,2,0,0,4,0)$ and $\gamma(S)^{*}=(0,4,0,0,2,2,0).$

######  Theorem 3.1.

([8, Thm. 2.2]) Let $1\leq k\leq n$. The map
$\sigma\mapsto\mathbf{code}(\sigma)$ is a bijection from ordered set
partitions of $[n]$ with $k$ blocks to the family of nonnegative integer
sequences $(c_{1},\ldots,c_{n})$ such that

  * •

for all $1\leq i\leq n$ we have $c_{i}<k$,

  * •

for any subset $S\subseteq[n]$ with $|S|=n-k+1$, the componentwise inequality
$\gamma(S)^{*}\leq(c_{1},\ldots,c_{n})$ fails to hold.

For future reference we recall the inverse map introduced in the proof of the
above theorem. This inverse map uses the following insertion procedure.

For $(B_{1}\ |\ \cdots\ |\ B_{k})$ a sequence of $k$ (possibly empty) sets of
positive integers we define the _coinversion labels_ as follows. First, label
the empty sets $0,1,\ldots,j$ from right to left, and then label the nonempty
sets $j+1,\ldots,j+k-1$ from left to right.

For a sequence $(c_{1},\ldots,c_{n})$ satisfying the conditions in Theorem
3.1, we construct an ordered set partition as follows. Start with a sequence
$(\emptyset\ |\ \cdots\ |\ \emptyset)$ of $k$ copies of the empty set, and for
$i=1,2,\ldots,n$ insert the number $i$ in the block with label $c_{i}$ under
the coinversion labeling.

For example, let $n=7$, $k=4$ and consider the sequence $c=(2,1,2,0,2,0,2)$.
The resulting ordered set partition will be $(6\ |\ 13\ |\ 257\ |\ 4)$, as
shown by the following process, starting with the labeled sequence of blocks
$(\emptyset^{3}\ |\ \emptyset^{2}\ |\ \emptyset^{1}\ |\ \emptyset^{0})$.

$i$ | $c_{i}$ | updated labeled sequence of blocks
---|---|---
$1$ | $2$ | $(\emptyset^{2}\ |\ 1^{3}\ |\ \emptyset^{1}\ |\ \emptyset^{0})$
$2$ | $1$ | $(\emptyset^{1}\ |\ 1^{2}\ |\ 2^{3}\ |\ \emptyset^{0})$
$3$ | $2$ | $(\emptyset^{1}\ |\ 13^{2}\ |\ 2^{3}\ |\ \emptyset^{0})$
$4$ | $0$ | $(\emptyset^{0}\ |\ 13^{1}\ |\ 2^{2}\ |\ 4^{3})$
$5$ | $2$ | $(\emptyset^{0}\ |\ 13^{1}\ |\ 25^{2}\ |\ 4^{3})$
$6$ | $0$ | $(6^{0}\ |\ 13^{1}\ |\ 25^{2}\ |\ 4^{3})$
$7$ | $2$ | $(6^{0}\ |\ 13^{1}\ |\ 257^{2}\ |\ 4^{3})$

In our algebraic analysis of $S_{n}$ we will need a version of this insertion
which maps the family of ordered set partitions of $[n]$ with _at least_ $k$
blocks bijectively onto a certain collection $(c_{1},\dots,c_{n})$ of length
$n$ ‘code words’ over the nonnegative integers. In the bijection
$\mathbf{code}$ of Theorem 3.1, the ordered set partition
$(1|2|\cdots|m,m+1,\ldots,n)$ has code $(0,0,\ldots,0)$ for any number of
blocks $m$, so we cannot simply take the union of these maps for $m\geq k$.

We resolve the problem in the above paragraph by working with a different
version of the coinversion code, which we will call the _boosted coinversion
code_. For an ordered set partition $\sigma=(B_{1}\ |\ \cdots\ |\ B_{k})$ we
define $\overline{\mathbf{code}}(\sigma)=(c_{1},\ldots,c_{n})$ as follows.
Suppose $1\leq i\leq n$ and $i\in B_{j}$, then

$c_{i}=\begin{cases}|\\{\ell>j\ :\ \min(B_{\ell})>i\\}|&\text{if
}i=\min(B_{j});\\\ |\\{\ell>j\ :\ \min(B_{\ell})>i\\}|+j&\text{if
}i\neq\min(B_{j}).\end{cases}$

Compared to the coinversion codes from before, the difference is that all the
numbers corresponding to non-minimal elements of blocks are raised by one, and
we say that these numbers are _boosted_.

The remainder of the section will be devoted to the proof of the following
theorem.

######  Theorem 3.2.

Let $1\leq k\leq n$. The map $\sigma\mapsto\overline{\mathbf{code}}(\sigma)$
is a bijection from the set of ordered set partitions of $[n]$ with at least
$k$ blocks to the family of nonnegative integer sequences such that

  * •

for all $1\leq i\leq n$ we have $c_{i}<n$.

  * •

for any subset $S\subseteq[n]$ with $|S|=n-k+1$ the componentwise inequality
$\gamma(S)^{*}\leq(c_{1},\ldots,c_{n})$ fails to hold.

  * •

for any $1\leq i,d\leq n$ and any $T\subseteq[n-1]$ with $|T|=n-d$ and
$\gamma(T)^{*}=(\gamma_{n-1},\ldots,\gamma_{1})$, the componentwise inequality
$(\gamma_{n-1},\ldots,\gamma_{i},d,\gamma_{i-1},\ldots,\gamma_{1})\leq(c_{1},\ldots,c_{n})$
fails to hold.

The proof of the necessity of these conditions will be similar to that of the
proof of [8, Thm.2.2]. For the sufficiency of the conditions we use an
insertion map similar to that considered above. We begin by showing that both
the number of blocks of an ordered set partition of $[n]$, as well as its
classical coinversion code, can be recovered from its boosted coinversion
code.

######  Lemma 3.3.

Let $\sigma$ be an ordered set partition of $[n]$. Given the boosted
coinversion code $\overline{\mathbf{code}}(\sigma)$ one can recover the
coinversion code $\mathbf{code}(\sigma)$, as well as the number of blocks of
$\sigma$.

###### Proof.

Note that the second part is immediate once we have recovered
$\mathbf{code}(\sigma)$, as the number of blocks will be equal to the number
of unboosted numbers, which is easily found by comparing
$\overline{\mathbf{code}}(\sigma)$ and $\mathbf{code}(\sigma)$.

Given a boosted coinversion code $(c_{1},\ldots,c_{n})$ corresponding to an
ordered set partition with $\ell$ blocks (where $\ell$ is unknown), we can
think of creating the ordered set partition by following the same procedure as
described before, with the only difference that the labels of all the nonempty
blocks should be raised by one.

No matter what, at some point we will fill in the last nonempty block with
some number $i$, which necessarily has $c_{i}=0$. Additionally, from the
boosting, it is clear that $c_{j}>0$ for all $j>i$, hence we can recover $i$
by looking for the last entry in our sequence that equals $0$.

Now, assume that we have identified that $i_{1}<\ldots<i_{j}$ are minimal in
their block and that all other numbers in $[i_{1},n]$ are not minimal in their
block. If $i_{1}=1$ we are done. Otherwise, it is clear that we must have at
least $j+1$ blocks (as clearly $1$ will be minimal in its block). Now, let
$i_{0}<i_{1}$ be the largest number that is also minimal in its block. By the
inverse map, this must correspond to some index with $c_{i_{0}}\leq j$, as at
the time of inserting $i_{0}$ there are exactly $j+1$ empty blocks, labeled
$0,1,\ldots,j$. Additionally, for any $i_{0}<i<i_{1}$, at the time of
insertion there will be exactly $j$ empty blocks, hence the coinversion label
of $i$ will be at least $j+1$ (because of the boosting). Therefore, given
$\overline{\mathbf{code}}(\sigma)$ we can recognize $i_{0}$ as the largest
index $i_{0}<i_{1}$ with $c_{i_{0}}\leq j$. By induction we are done. ∎

Explicitly, the procedure above is as follows. Given a sequence
$(c_{1},\ldots,c_{n})$, trace the sequence from right to left, marking the
first $0$, then the first $0$ or $1$, then the first $0$, $1$ or $2$,
etcetera. Now, decrease all the unmarked numbers by $1$ and one recovers the
coinversion code. We call this procedure the _unboosting_ of a sequence
$(c_{1},\ldots,c_{n})$.

As an example, consider the boosted coinversion code $c=(2,4,2,4,0,0,1,4)$.
Working from right to left we mark $c_{6}$ as it is the first $0$, then
$c_{5}$ as it is at most $1$, then $c_{3}$ as it is the next number at most
$2$ and finally $c_{1}$ as it is the next number that is at most $3$.
Therefore, the number of blocks is equal to $4$ and the unboosted coinversion
code is given by $(2,3,2,3,0,0,0,3)$. Applying the earlier bijection this
coinversion code corresponds to $(37\ |\ 124\ |\ 6\ |\ 58)$.

We are now ready to prove the main result of this section.

###### Proof of Theorem 3.2.

We first prove the necessity of the conditions. Let $\sigma$ be an ordered set
partition of $[n]$ with at least $k$ blocks and let
$\overline{\mathbf{code}}(\sigma)=(c_{1},\dots,c_{n})$ be its boosted
coinversion code.

  * •

If $i$ is minimal in its block, $c_{i}$ will be at most the number of blocks
following the block containing $i$, which is at most $n-1$. If $i$ is not
minimal we have at most $n-1$ blocks, and if $i\in B_{j}$ we have

$c_{i}=j+|\\{\ell>j\ :\ \min(B_{\ell})>i\\}|\leq j+|\\{\ell>j\ :\ \text{the
$\ell^{\text{th}}$ block exists}\\}|\leq n-1.$

  * •

Suppose $S=\\{n+1-t_{n-k+1},\ldots,n+1-t_{1}\\}$ (with
$t_{1}<\ldots<t_{n-k+1}$) satisfies $\gamma(S)^{*}\leq(c_{1},\ldots,c_{n})$.
We show that none of the numbers $\\{t_{1},\ldots,t_{n-k+1}\\}$ is minimal in
its block of $\sigma$, contradicting that $\sigma$ has at least $k$ blocks.

If $t_{n-k+1}$ is minimal in its block, then

$\displaystyle c_{t_{n-k+1}}$
$\displaystyle=|\\{\ell>t_{n-k+1}:\begin{smallmatrix}\ell\text{ is minimal in
its block and}\\\ \text{occurs to the right of }t_{n-k+1}\text{ in
}\sigma\end{smallmatrix}\\}|$
$\displaystyle\leq|\\{t_{n-k+1}+1,\ldots,n-1,n\\}|=n-t_{n-k+1}.$

However, the term in $\gamma(S)^{*}$ in position $t_{n-k+1}$ equals
$n-t_{n-k+1}+1$, hence we conclude that $t_{n-k+1}$ is not minimal in its
block.

Now, if $t_{n-k}$ were minimal in its block, we would have

$\displaystyle c_{t_{n-k}}$ $\displaystyle=|\\{\ell>t_{n-k}:\ell\text{ is
minimal in its block and occurs to the right of }t_{n-k}\text{ in }\sigma\\}|$
$\displaystyle\leq|\\{t_{n-k}+1,\ldots,n-1,n\\}-\\{t_{n-k+1}\\}|=n-t_{n-k}-1.$

But again, the term in $\gamma(S)^{*}$ in position $t_{n-k}$ equals
$n-t_{n-k}$, which shows that $t_{n-k}$ cannot be minimal in its block either.
An inductive argument now shows that none of $\\{t_{1},\ldots,t_{n-k+1}\\}$ is
minimal in its block.

  * •

For $d=n$ this is equivalent to the fact that $c_{i}<n$ for all $i$, so assume
$1\leq d<n$. Assume for contradiction that
$(\gamma_{n-1},\ldots,\gamma_{i},d,\gamma_{i-1},\ldots,\gamma_{1})\leq(c_{1},\ldots,c_{n})$
where $(\gamma_{n-1},\dots,\gamma_{1})=\gamma(T)^{*}$ for some
$T\subseteq[n-1]$ of size $|T|=n-d$. Since $c_{n+1-i}\geq d$, this implies
that $\sigma$ has at least $d$ blocks. Let $T=\\{i_{1}<\ldots<i_{t}\leq
n+1-i<i_{t+1}<\ldots<i_{t+s}\\}$. By the same argument used in the previous
bullet, we see that all $n+1-i_{j}$ with $j\leq t$ are not minimal in their
block. Now we consider two cases.

    * –

If $n+1-i$ is not minimal in its block either, we can continue the argument as
in the previous case to show that none of $n+1-i_{j}$ is minimal in its block.
In particular we have $1+(n-d)$ elements that are not minimal in their
respective blocks, contradicting the fact that $\sigma$ has at least $d$
blocks.

    * –

Now suppose that $n+1-i$ is minimal in its block. Since $c_{n+1-i}=d$, this
implies that among $\\{n+2-i,\ldots,n\\}$ at least $d$ numbers are also
minimal in their respective blocks. In particular, there are at least $d$
numbers that are not of the form $n+1-j$ with $j\in T$. But this implies that
$T$ has size at most $(n-1)-d<n-d$, which is a contradiction.

Now, we show that these conditions are sufficient. Given a sequence
$(c_{1},\ldots,c_{n})$ we can first unboost the sequence (as we can apply this
procedure to every sequence of nonnegative integers) to determine how many
blocks our intended ordered set partition must have. Given this extra
information, we can basically run the same inverse map as before, with the
exception that we should increase the label of every nonempty block by $1$. It
now suffices to check that we don’t run into any troubles by doing so. Our
proof will go through the following steps.

  * •

First we will show that the unboosting procedure concludes that there are at
most $n-k$ boosted numbers, as this will ensure that the ordered set partition
we aim for has at least $k$ blocks.

  * •

Then we will inductively show that can basically run the same inverse map as
before.

    * –

First we show that the conclusion of the unboosting is that $1$ is unboosted,
ensuring we have enough blocks to insert $1$ as a minimal element in its
block.

    * –

After that we will show that if the first $j-1$ numbers have been placed, we
can place $j$ following the appropriate procedure. This argument will depend
on whether $j$ is supposed to be minimal in its block or not (something that
we know from the unboosting procedure).

We will now prove each of these steps.

  * •

Assume that we have $t$ boosted numbers $c_{n+1-i_{j}}$ (with
$i_{1}<\ldots<i_{t}$) and assume that $t\geq n-k+1$. Let
$S=\\{i_{1},\ldots,i_{n-k+1}\\}$, then we claim that
$(c_{1},\ldots,c_{n})\geq\gamma(S)^{*}$. If $i\not\in S$, we have
$\gamma(S)*_{n+1-i}=0$, so $c_{n+1-i}\geq\gamma(S)^{*}_{n+1-i}$ indeed holds.
Furthermore, for $i=i_{j}$ by assumption on $c_{n+1-i_{j}}$ there are
$(i_{j}-j)$ unboosted numbers to the right of $n+1-i_{j}$. Therefore, since
$c_{n+1-i_{j}}$ was boosted, we have $c_{n+1-i_{j}}\geq
i_{j}-j+1=\gamma(S)^{*}_{n+1-i_{j}}$, as desired.

  * •

As mentioned before, we now show that we can run the inverse map without any
issues.

    * –

If $c_{1}=0$ it is clear that we can insert $1$, so assume $c_{1}=d$ with
$1\leq d\leq n-1$. Our goal is to show that in the unboosting procedure we
conclude that $1$ has to be minimal in its block. As $c_{1}=d$ this happens
precisely if the procedure shows that among $\\{2,3,\ldots,n\\}$ at least $d$
numbers were not boosted. For the sake of contradiction, assume that we have
at least $n-d$ boosted numbers, and let the largest $n-d$ be
$n+1-i_{1}>n+1-i_{2}>\ldots>n+1-i_{n-d}$. Let $T=\\{i_{1},\ldots,i_{n-d}\\}$
then by a similar argument to before we have
$(c_{1},c_{2},\ldots,c_{n})\geq(d,\gamma_{n-1},\ldots,\gamma_{1})$ where
$(\gamma_{n-1},\ldots,\gamma_{1})=\gamma(T)^{*}$.

    * –

Assume that the inverse map successfully inserted all the numbers in $[j-1]$
(with $j\geq 2$) and that we now try to insert $j$ according to $c_{j}$.

First assume that $c_{j}=t$ is unboosted. Since this is unboosted, there are
still at least $t$ unboosted numbers among $\\{c_{j+1},\ldots,c_{n}\\}$. As so
far only indices corresponding to unboosted numbers have been inserted in
empty blocks, and the number of total blocks it the number of unboosted
numbers, we have at least $t+1$ empty blocks at this point. As a result, there
will be some empty block labeled with $t$, so we can insert $j$ into an empty
block, as desired.

Hence, assume that $c_{j}$ was boosted. Suppose that at the time we still have
$t$ nonempty blocks, then by the unboosting procedure we know that $c_{j}\geq
t+1$, so we can insert $j$ appropriately, unless $c_{j}$ is too big. In other
words, the only thing that can go wrong is that there were $\ell$ unboosted
numbers (hence $\ell$ blocks in the ordered set partition), but that
$c_{j}\geq\ell+1$. Let
$n+1-i_{1}>\ldots>n+1-i_{a}>j>n-i_{a+1}>\ldots>n-i_{n-\ell-1}$ be all the
boosted numbers. But then, for $T=\\{i_{1},\ldots,i_{n-\ell-1}\\}$ of size
$n-(\ell+1)$, with $\gamma(T)^{*}=(\gamma_{n-1},\ldots,\gamma_{1})$, we have
$(c_{1},\ldots,c_{n})\geq(\gamma_{n-1},\ldots,\gamma_{n-j+1},\ell+1,\gamma_{n-j},\ldots,\gamma_{1})$,
a contradiction. ∎

##  4\. The algebraic quotient

Recall from the introduction that a word $w=w_{1}w_{2}\cdots w_{n}$ on the
alphabet $\mathbb{Z}_{>0}$ is _packed_ if whenever $i+1$ appears, then so does
$i$. It will be convenient for our inductive arguments to consider packed
words in which every letter in some segment $1\leq i\leq k$ must appear. To
this end, we define

(4.1) $\mathcal{W}_{n,k}:=\\{\text{length $n$ packed words $w=w_{1}w_{2}\dots
w_{n}$ \,:\, the letters $1,2,\dots,k$ appear in $w$}\\}.$

Words in $\mathcal{W}_{n,k}$ are in bijection with ordered set partitions of
$[n]$ with at least $k$ blocks. We have the further identifications
$\mathcal{W}_{n,1}=\mathcal{W}_{n}$ and $\mathcal{W}_{n,n}=\mathfrak{S}_{n}.$

The symmetric group $\mathfrak{S}_{n}$ acts on $\mathcal{W}_{n,k}$ by the rule
$\sigma\cdot(w_{1}\dots w_{n}):=w_{\sigma(1)}\dots w_{\sigma(n)}$. The
quotient rings $S_{n,k}$ of the following definition will give a graded
refinement of this action. Their defining ideals $J_{n,k}$ contain the ideal
$J_{n}$ defining the ring $S_{n}$ appearing in the introduction.

######  Definition 4.1.

Let $J_{n,k}\subseteq\mathbb{Q}[\mathbf{x}_{n}]$ be the ideal

$J_{n,k}:=J_{n}+\langle e_{n},e_{n-1},\ldots,e_{n-k+1}\rangle$

and let $S_{n,k}:=\mathbb{Q}[\mathbf{x}_{n}]/J_{n,k}$ be the corresponding
quotient ring.

Each of the quotients $S_{n,k}$ is a graded $\mathfrak{S}_{n}$-module. Their
defining ideals are nested according to $J_{n}=J_{n,n}\subseteq
J_{n,n-1}\subseteq\cdots\subseteq J_{n,1}$. We study $S_{n,k}$ by making use
of a point locus $X_{n,k}\subseteq\mathbb{Q}^{n}$ corresponding to
$\mathcal{W}_{n,k}.$ Fix $n$ distinct rational numbers
$\alpha_{1},\dots,\alpha_{n}\in\mathbb{Q}$. For any packed word $w_{1}\dots
w_{n}\in\mathcal{W}_{n,k}$, we have a corresponding point
$(\alpha_{w_{1}},\dots,\alpha_{w_{n}})\in\mathbb{Q}^{n}$. We let
$X_{n,k}\subseteq\mathbb{Q}^{n}$ be the family of points corresponding to all
packed words in $\mathcal{W}_{n,k}.$

The set $X_{n,k}\subseteq\mathbb{Q}^{n}$ is closed under the coordinate-
permuting action of $\mathfrak{S}_{n}$ and we have an identification
$\mathbb{Q}[\mathcal{W}_{n,k}]\cong\mathbb{Q}[X_{n,k}]$. As explained in the
introduction, we have isomorphisms of ungraded $\mathfrak{S}_{n}$-modules

$\mathbb{Q}[\mathcal{W}_{n,k}]\cong\mathbb{Q}[X_{n,k}]\cong\mathbb{Q}[\mathbf{x}_{n}]/\mathbf{I}(X_{n,k})\cong\mathbb{Q}[\mathbf{x}_{n}]/\mathbf{T}(X_{n,k}).$

It turns out that $\mathbf{T}(X_{n,k})$ coincides with $J_{n,k}$.

######  Theorem 4.2.

For any $1\leq k\leq n$, we have the ideal equality
$J_{n,k}=\mathbf{T}(X_{n,k})$. Consequently, we have an isomorphism of
ungraded $\mathfrak{S}_{n}$-modules $\mathbb{Q}[\mathcal{W}_{n,k}]\cong
S_{n,k}$.

###### Proof.

To show that $J_{n,k}\subseteq\mathbf{T}(X_{n,k})$, it suffices to show that
every generator of $J_{n,k}$ arises as the highest degree component of some
polynomial in $\mathbf{I}(X_{n,k}).$ Fix $1\leq i\leq n$ and $1\leq r\leq d$;
we begin by showing that the generator $x_{i}^{d}e_{n-r}^{(i)}$ lies in
$\mathbf{T}(X_{n,k}).$

Note that if $(x_{1},\ldots,x_{n})\in X_{n,k}$, we either have
$x_{i}\in\\{\alpha_{1},\ldots,\alpha_{d}\\}$, or for any $1\leq j\leq d$ the
number $\alpha_{d}$ must appear among
$\\{x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{n}\\}$. We let $t$ be a new
variable, and define the function

$f(x_{1},\ldots,x_{n},t):=(x_{i}-\alpha_{1})\cdots(x_{i}-\alpha_{d})\cdot\frac{(1-tx_{1})\cdots(1-tx_{i-1})(1-tx_{i+1})\cdots(1-tx_{n})}{(1-t\alpha_{1})\cdots(1-t\alpha_{d})}$

and expanding this function in terms of the parameter $t$ yields

$\displaystyle f(x_{1},$ $\displaystyle\ldots,x_{n},t)=$
$\displaystyle(x_{i}-\alpha_{1})\cdots(x_{i}-\alpha_{d})\cdot\sum_{r\geq
0}\left(\sum_{a+b=r}(-1)^{a}e_{a}^{(i)}\cdot
h_{b}(\alpha_{1},\ldots,\alpha_{d})\right)t^{r}$

Specialization of $f(x_{1},\ldots,x_{n},t)$ at
$(x_{1},\ldots,x_{n})=(\beta_{1},\ldots,\beta_{n})$ yields an element of
$\mathbb{Q}[[t]]$. We analyze this specialization when
$(\beta_{1},\ldots,\beta_{n})\in X_{n,k}$. If
$\beta_{i}\in\\{\alpha_{1},\ldots,\alpha_{d}\\}$, then
$f(\beta_{1},\ldots,\beta_{n},t)=0$. Otherwise, $d$ of the terms in the
numerator of $f$ will cancel with the $d$ terms in the denominator, so that
hence $f(\beta_{1},\ldots,\beta_{n},t)$ is a polynomial of degree $(n-1)-d$ in
$t$. Either way, the coefficient of $t^{n-r}$ in $f(x_{1},\ldots,x_{n},t)$
vanishes on $X_{n,k}$, so that

$(x_{i}-\alpha_{1})\cdots(x_{i}-\alpha_{d})\cdot\left(\sum_{a+b=n-r}(-1)^{a}e_{a}^{(i)}\cdot
h_{b}(\alpha_{1},\ldots,\alpha_{d})\right)\in\mathbf{I}(X_{n,k})$

and taking the highest degree component gives

$x_{i}^{d}\cdot(-1)^{n-r}e_{n-r}^{(i)}\in\mathbf{T}(X_{n,k}).$

The remaining generators $e_{d}$ (for $d>n-k$) are handled by a similar
argument. We consider the rational function

$\displaystyle g(x_{1},\dots,x_{n},t)$
$\displaystyle:=\frac{(1-tx_{1})(1-tx_{2})\cdots(1-tx_{n})}{(1-t\alpha_{1})(1-t\alpha_{2})\cdots(1-t\alpha_{k})}$
$\displaystyle=\sum_{r\geq 0}\left(\sum_{a+b=r}(-1)^{a}e_{a}\cdot
h_{b}(\alpha_{1},\dots,\alpha_{k})\right)\cdot t^{r}.$

Evaluating $(x_{1},\dots,x_{n})$ at a point in $X_{n,k}$ forces the $k$
factors in the denominator to cancel with $k$ factors in the numerator,
yielding a polynomial of degree $n-k$ in $t$. For any $d>n-k$, we conclude
that

$\sum_{a+b=d}(-1)^{a}e_{a}\cdot
h_{b}(\alpha_{1},\dots,\alpha_{k})\in\mathbf{I}(X_{n,k}),$

which implies

$e_{d}\in\mathbf{T}(X_{n,k}).$

This proves the containment $J_{n,k}\subseteq\mathbf{T}(X_{n,k}),$ so that

(4.2)
$\dim\mathbb{Q}[\mathbf{x}_{n}]/J_{n,k}\geq\dim\mathbb{Q}[\mathbf{x}_{n}]/\mathbf{T}(X_{n,k})=|\mathcal{W}_{n,k}|$

In light of Equation (4.2), to prove the desired equality
$J_{n,k}=\mathbf{T}(X_{n,k})$ it is enough to show that
$\dim(\mathbb{Q}[\mathbf{x}_{n}]/J_{n,k})\leq|\mathcal{W}_{n,k}|$. This is a
Gröbner theory argument.

Since the elementary symmetric polynomials $e_{n},e_{n-1},\dots,e_{n-k+1}$ in
the full variable set $\\{x_{1},\dots,x_{n}\\}$ lie in $J_{n,k}$, [5, Lem.
3.4] implies that for any subset $S\subseteq[n]$ with $|S|=n-k+1$, the
Demazure character $\kappa_{\gamma(S)}$ corresponding to the length $n$
sequence $\gamma(S)$ also lies in $J_{n,k}$. The lexicographical leading
monomial of $\kappa_{\gamma(S)}$ has exponent sequence $\gamma(S)^{*}$.
Similarly, for $1\leq i,d\leq n$, since

$x_{i}^{d}\cdot e_{n-d}^{(i)},\dots,x_{i}^{d}\cdot e_{n-1}^{(i)}\in J_{n,k},$

for any $T\subseteq[n-1]$ of size $|T|=n-d$, [5, Lem. 3.4] again implies that

$x_{i}^{d}\cdot\kappa_{\gamma(T)}(x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{n})\in
J_{n,k}.$

Writing $\gamma(T)^{*}=(\gamma_{n-1},\dots,\gamma_{1})$, the lexicographical
leading term of
$x_{i}^{d}\cdot\kappa_{\gamma(T)}(x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{n})$ is
$(\gamma_{n-1},\dots,\gamma_{i},d,\gamma_{i-1},\dots,\gamma_{1})$. It follows
that

> the exponent sequence $(c_{1},\dots,c_{n})$ of any member of the standard
> monomial basis of $\mathbb{Q}[\mathbf{x}_{n}]/J_{n,k}$ satisfies the
> conditions in the statement of Theorem 3.2.

Theorem 3.2 implies the desired dimension bound
$\dim\mathbb{Q}[\mathbf{x}_{n}]/J_{n,k}\leq|\mathcal{W}_{n,k}|$, completing
the proof. ∎

The standard monomial basis of $S_{n,k}$ is governed by coinversion codes.

######  Corollary 4.3.

The standard monomial basis of $S_{n,k}$ with respect to the lexicographical
term ordering are the monomials $x_{1}^{c_{1}}\cdots x_{n}^{c_{n}}$ where
$(c_{1},\dots,c_{n})=\overline{\mathbf{code}}(\sigma)$ is the boosted
coinversion code of some ordered set partition $\sigma$ of $[n]$ with at least
$k$ blocks.

###### Proof.

This follows from Theorem 3.2 and the last paragraph of the above proof. ∎

Our next goal is to derive the graded $\mathfrak{S}_{n}$-module structure of
the quotients $S_{n,k}$. This result is stated most cleanly in terms of the
following rings defined by Haglund, Rhoades, and Shimozono [5].

######  Definition 4.4.

Let $1\leq k\leq n$ be integers. Define the ideal
$I_{n,k}\subseteq\mathbb{Q}[\mathbf{x}_{n}]$ by

$I_{n,k}:=\langle
x_{1}^{k},x_{2}^{k},\ldots,x_{n}^{k},e_{n},e_{n-1},\ldots,e_{n-k+1}\rangle$

and let $R_{n,k}:=\mathbb{Q}[\mathbf{x}_{n}]/I_{n,k}$ be the corresponding
quotient ring.

We can now state the graded $\mathfrak{S}_{n}$-module structure of $S_{n}$ in
terms of the graded $\mathfrak{S}_{n}$-module structure of these $R_{n,k}$,
which have been extensively studied in [5].

######  Theorem 4.5.

As graded $\mathfrak{S}_{n}$-module we have

$S_{n,k}\cong R_{n,n}\langle 0\rangle\oplus
R_{n,n-1}\langle-1\rangle\oplus\cdots\oplus R_{n,k}\langle-n+k\rangle.$

We are now ready to prove Theorem 4.5.

###### Proof.

We proceed by descending induction on $k$. In the case $n=k$, we claim that
$J_{n,n}=I_{n,n}=\langle e_{1},\dots,e_{n}\rangle$ is the classical invariant
ideal so that $S_{n,n}=R_{n,n}$. Indeed, each elementary symmetric polynomial
$e_{d}$ appears as a generator of $J_{n,n}$. On the other hand, Theorem 4.2
implies that $\dim S_{n,n}=n!=\dim R_{n,n}$. This finishes the proof in the
case $k=n$.

Now suppose $1\leq k\leq n-1$. We exhibit a short exact sequence of
$\mathfrak{S}_{n}$-modules

(4.3) $0\rightarrow
R_{n,k}\overset{\varphi}{\rightarrow}S_{n,k}\overset{\pi}{\rightarrow}S_{n,k+1}\rightarrow
0,$

where $\varphi$ is homogeneous of degree $n-k$ and $\pi$ is homogeneous of
degree $0$. The exactness of this sequence implies

$S_{n,k}\cong S_{n,k+1}\oplus R_{n,k}\langle-n+k\rangle,$

proving the theorem by induction.

Since every generator of $J_{n,k+1}$ is also a generator of $J_{n,k}$, we may
take $\pi:S_{n,k}\twoheadrightarrow S_{n,k+1}$ to be the canonical projection.
We have a map

(4.4) $\widetilde{\varphi}:\mathbb{Q}[\mathbf{x}_{n}]\rightarrow S_{n,k}$

given by multiplication by $e_{n-k}$ followed by projection onto $S_{n,k}$. We
verify that $\widetilde{\varphi}$ descends to a map
$\varphi:R_{n,k}\rightarrow S_{n,k}$ by showing that $\widetilde{\varphi}$
sends every generator of $I_{n,k}$ to zero. Indeed, we have
$\widetilde{\varphi}(e_{j}(x_{1},\dots,x_{n}))=0$ for any $j>n-k$ since
$e_{j}(x_{1},\dots,x_{n})$ is a generator of $J_{n,k}$. Furthermore, for
$1\leq i\leq n$ we have

$\widetilde{\varphi}(x_{i}^{k})=x_{i}^{k}e_{n-k}=x_{i}^{k}e_{n-k}^{(i)}+x_{i}^{k+1}e_{n-k-1}^{(i)}=0,$

where the final equality follows because both $x_{i}^{k}e_{n-k}^{(i)}$ and
$x_{i}^{k+1}e_{n-k-1}^{(i)}$ are generators of $J_{n,k}$. We conclude that
$\widetilde{\varphi}$ descends to a map $\varphi:R_{n,k}\rightarrow S_{n,k}$
of $\mathfrak{S}_{n}$-modules which is homogeneous of degree $n-k$. It is
clear that $\varphi$ surjects onto the kernel of $\pi$. The exactness of the
sequence (4.3) follows from the dimensional equality

$\dim(S_{n,k})=|\mathcal{W}_{n,k}|=|\mathcal{W}_{n,k+1}|+|\mathcal{OP}_{n,k}|=\dim(S_{n,k+1})+\dim(R_{n,k}).\qed$

The graded Frobenius image of $S_{n,k}$ is most naturally stated in terms of
the $C$-functions defined in Equation (1.2).

######  Corollary 4.6.

For any $1\leq k\leq n$, the graded Frobenius image of $S_{n,k}$ is given by

(4.5)
$\mathrm{grFrob}(S_{n,k};q)=\sum_{j=k}^{n}q^{n-j}\cdot(\omega\circ\mathrm{rev}_{q})C_{n,j}(\mathbf{x};q).$

###### Proof.

Apply [5, Thm. 6.11] and Theorem 4.5. ∎

##  5\. Conclusion

In this paper we have described an quotient $S_{n}$ of
$\mathbb{Q}[\mathbf{x}_{n}]$ whose algebraic properties are governed by the
combinatorics of packed words in $\mathcal{W}_{n}$. The ring $S_{n}$ has
provable algebraic properties which are similar to conjectural properties of
the superspace coinvariant ring
$\Omega_{n}/\langle(\Omega_{n})^{\mathfrak{S}_{n}}_{+}\rangle$. With an eye
towards proving these conjectures, it would be desirable to have a more direct
connection between the packed word quotient $S_{n}$ and the superspace
coinvariant ring.

Generalized coinvariant rings related to delta operators have seen ties to
cohomology theory. In the context of the rings $R_{n,k}$ of Definition 4.4,
Pawlowski and Rhoades showed that $H^{\bullet}(X_{n,k};\mathbb{Q})=R_{n,k}$,
where $X_{n,k}$ is the variety of $n$-tuples $(\ell_{1},\dots,\ell_{n})$ of
1-dimensional subspaces of $\mathbb{C}^{k}$ which satisfy
$\ell_{1}+\cdots+\ell_{n}=\mathbb{C}^{k}$. Rhoades and Wilson [8] refined this
result by considering the open subvariety $X^{(r)}_{n,k}$ obtained by
requiring the the sum $\ell_{1}+\cdots+\ell_{r}$ of the first $r$ lines is
direct. In light of [7, 8], it is natural to ask for a geometric perspective
on the ring $S_{n}$ appearing in this paper.

######  Problem 5.1.

Find a variety $Y_{n}$ whose rational cohomology ring
$H^{\bullet}(Y_{n};\mathbb{Q})$ is isomorphic to $S_{n}$.

The results in [7] suggest that $Y_{n}$ could be taken to be an open
subvariety of the $n$-fold Cartesian product $(\mathbb{P}^{k-1})^{n}$ of
$(k-1)$-dimensional projective space with itself with the property that the
cohomology map
$i^{*}:H^{\bullet}((\mathbb{P}^{k-1})^{n};\mathbb{Q})\rightarrow
H^{\bullet}(Y_{n};\mathbb{Q})$ induced by the inclusion
$i:Y_{n}\hookrightarrow(\mathbb{P}^{k-1})^{n}$ is surjective.

##  6\. Acknowledgements

B. Rhoades was partially supported by NSF Grant DMS-1953781. The authors are
grateful for Christopher O’Neill for helpful discussions about this project.

## References

  * [1] F. Castillo and F. Liu. Deformation cones of nested Braid fans. Int. Math. Res. Not. IMRN, rnaa090. https://doi.org/10.1093/imrn/rnaa090
  * [2] D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms. Springer International Publishing Switzerland, 2015.
  * [3] M. D’Adderio, A. Mellit. A proof of the compositional Delta Conjecture. Preprint, 2020. arXiv:2011.11467.
  * [4] J. Haglund, J. B. Remmel, and A. T. Wilson. The Delta Conjecture. Trans. Amer. Math. Soc., 370 (2018), 4029–4057
  * [5] J. Haglund, B. Rhoades, and M. Shimozono. Ordered set partitions, generalized coinvariant algebras, and the Delta Conjecture. Adv. Math., 329 (2018), 851–915.
  * [6] J. Novelli and J.-Y. Thibon. Polynomial realizations of some trialgebras. Proceedings of Formal Power Series and Algebraic Combinatorics (FPSAC), (2006). 243–255
  * [7] B. Pawlowski and B. Rhoades. A flag variety for the Delta Conjecture. Transactions of the American Mathematical Society, 372, (2019). 8195–8248
  * [8] B. Rhoades and A. T. Wilson. Line configurations and r-Stirling partitions. J. Comb., 10 (3), (2019), 411–431.
  * [9] B. Rhoades and A. T. Wilson. Vandermondes in superspace. Trans. Amer. Math. Soc., 373 (6), (2020), 4483–4516.
  * [10] B. E. Sagan. The Symmetric Group. Springer-Verlag New York, Inc. 2001
  * [11] M. Zabrocki. A module for the Delta Conjecture. Preprint, 2019. arXiv:1902.08966


# FactorizeNet: Progressive Depth Factorization for Efficient Network
Architecture Exploration Under Quantization Constraints

Stone Yun
<EMAIL_ADDRESS>
University of Waterloo
Vision and Image Processing Lab Alexander Wong
<EMAIL_ADDRESS>
University of Waterloo
Waterloo Artificial Intelligence Institute

###### Abstract

Depth factorization and quantization have emerged as two of the principal
strategies for designing efficient deep convolutional neural network (CNN)
architectures tailored for low-power inference on the edge. However, there is
still little detailed understanding of how different depth factorization
choices affect the final, trained distributions of each layer in a CNN,
particularly in the situation of quantized weights and activations. In this
study, we introduce a progressive depth factorization strategy for efficient
CNN architecture exploration under quantization constraints. By
algorithmically increasing the granularity of depth factorization in a
progressive manner, the proposed strategy enables a fine-grained, low-level
analysis of layer-wise distributions. Thus enabling the gain of in-depth,
layer-level insights on efficiency-accuracy tradeoffs under fixed-precision
quantization. Such a progressive depth factorization strategy also enables
efficient identification of the optimal depth-factorized macroarchitecture
design (which we will refer to here as FactorizeNet) based on the desired
efficiency-accuracy requirements.

##  1 Introduction

Following the recent explosion in deep learning research, there has been
increased attention on complexity reduction strategies for deep convolutional
neural networks (CNN) to enable inference on mobile processors. Quantization
[1, 2, 3], and depth factorization [4, 5, 6, 7] have quickly emerged as two
highly effective strategies for reducing the power and computational budget
needed for on-device inference. These two methods work orthogonally. Fixed
point quantization enables simple, low bit-width integer operations which are
several times faster/less power than floating point (fp32) operations. Depth
factorization reduces the number of CNN parameters and multiply-accumulate
(MAC) operations. For depth factorization, we split the input channels into f
groups and apply f groups of filters independently to their respective channel
groups. For a given factorization rate, f, the number of MACs in a convolution
layer goes from (1) to (2), thus reducing computation by a factor of f. For
simplicity, our equations have excluded the MAC contribution from the
pointwise convolution that typically follows the group convolution. Pointwise
convolution is often used for the dual purpose of mixing channel information
and increasing channel depth.

$\vspace{-0.1in}\ K\times K\times H\times W\times C_{in}\times C_{out}\ $ (1)
$\ K\times K\times H\times
W\times\frac{C_{in}}{f}\times\frac{C_{out}}{f}\times f\ \vspace{-0.03in}$ (2)

Depthwise separable convolution as described in MobileNets [4] has become a
staple in efficient network design. It represents the extreme end of the depth
factorization spectrum with one convolution filter per input channel. However,
perhaps we do not always need to go to the extreme. A key tradeoff when
designing CNNs for limited compute is efficiency vs. accuracy. As we scale
down our architectures, we will necessarily lose accuracy. While depthwise
separable convolutions are extremely efficient, they suffer from low data
parallelism making them less suited to hardware acceleration. Also as
mentioned in [7], they should not be assumed as the optimal point on the
depth-factorization-spectrum. Furthermore, with quantization emerging as
essential for on-device inference, we must consider the additional component
of quantization error. In general, efficient architectures have so few
parameters that they often suffer more quantized accuracy loss compared to
higher complexity networks. However, there is still limited understanding of
how different architectural choices impact quantized accuracy. Given the
significant investment involved with architecture search/design, it would be
beneficial to gain detailed insights on the potential quantizability of an
architecture during the design phase. Thus, helping speed-up the quantization
optimization process.

We introduce a systematic, progressive depth factorization strategy for
exploring the efficiency/accuracy trade-offs of scaling down CNN architectures
under quantization and computation constraints. Starting with a simple, fixed
macroarchitecture (see Figure 2) we algorithmically increase the granularity
of depth factorization in a progressive manner while analyzing the final
trained layerwise distributions of weights and activations at each step. Our
proposed strategy enables a fine-grained, low-level analysis of layer-wise
distributions to gain in-depth, layer-level insights on efficiency-accuracy
tradeoffs under fixed-precision quantization. Furthermore, we can identify
optimal depth-factorized macroarchitectures which we will refer to as
FactorizeNet. While previous studies [8, 6] have performed ablation studies on
the effect of different factorization choices on testing accuracy, they used a
high-level approach and were mainly concerned with fp32 accuracy. [9] performs
layerwise analysis of the signal-to-quantization-noise-ratio (SQNR) to
identify layers that were hurting the quantized accuracy of MobileNetsv1
before retraining a modified MobileNets architecture. Our method can be seen
as expanding on this approach and going to an even lower level, directly
analyzing the distributions at each layer. Insights gained from such a fine-
grained approach can help guide further exploration for quantization-based
optimizations or provide a baseline expectation of quantized accuracy trade-
offs when engineers deploy their quantized model as-is.

Figure 1:  The depthwise factorization spectrum. On one end, we have regular
convolution, with factorization rate of f = 1. On the other end we have
depthwise convolution with factorization rate of f = input-depth. For a given
layer in a CNN architecture, the optimal level of factorization could lie
anywhere on this spectrum.

Figure 2: FactorizeNet Macroarchitecture. For our progressive, fine-grained
analysis we start with a simple regular CNN and fix the macroarchitecture. We
then progressively increase the level of factorization of each block using
Groupwise Separable Convolution with varying f. The very first convolution
layer stays fixed.

##  2 Progressive Depth Factorization and Fine-Grained Layer Analysis

Consider a spectrum of depth factorization (see Figure 1) with regular
convolution on one end (factorization rate f = 1) and depthwise convolution on
the other (factorization rate f = input depth). As we turn the knob from f = 1
to f = input depth for each layer or set of layers in a given
macroarchitecture, we will observe a range of efficiency/accuracy trade-offs.
Thus, a given CNN macroarchitecture is a search space in itself where a large
range of factorization levels and combinations of factorizations can be
realized to meet given efficiency-accuracy constraints. Besides searching for
the optimal factorization configuration, we also wish to gain detailed insight
on the impact of various factorization choices on the layer-wise distributions
of final trained weights and activations. This information can help us
understand which factorization settings are the most amenable to quantization
as well as provide detailed insight on the response of various stages of a CNN
to depth factorization. We propose algorithmically increasing the
factorization of a given CNN macroarchitecture in a progressive manner while
conducting a low-level analysis of the layerwise distributions for each level
of factorization. At each factorization step, we train the factorized CNN and
track the dynamic ranges of each layer’s weights and activations as well as
their “average channel precision". Average channel precision is defined as
(3). Channel precision in this context is the ratio between an individual
channel’s range and the range of the entire layer. [3] algorithmically
maximizes the channel precisions of each layer in a network prior to
quantization. It can be seen as a measure of how well the overall layer-wise
quantization encodings represent the information in each channel. For dynamic
ranges of activations, we randomly sample N training samples and observe the
corresponding activation responses. To reduce outlier noise, we perform
percentile clipping (Eg. top and bottom 1%) and track the dynamic range and
average precision of the clipped activations. As percentile clipping has
become a ubiquitous default quantization setting we feel that this method
establishes a realistic baseline of what can be expected at inference-time.
Finally, there is one more set of dynamic ranges to observe. Batch
Normalization (BatchNorm) [10] has become the best-practice in CNNs. However,
their vanilla form is not well-suited for mobile hardware processing. Best
practices for mobile inference usually involve folding the scale and variance
parameters of BatchNorm into the preceding layer’s convolution parameters as
described in [1]. Therefore, we track the dynamic range and precision of the
CNN’s batchnorm-folded (BN-Fold) weights.

$\vspace{0.1in}average\\_precision=\frac{1}{K}\sum_{i=1}^{K}\frac{range_{channel\\_i}}{range_{tensor}}\
\vspace{-0.2in}$ (3)

In this manner, we can iterate through progressively increasing factorization
configurations, gaining insights on the efficiency/accuracy trade-offs at each
step as well as the final layerwise distributions. Besides enabling analysis
of depth factorization, this fine-grained approach is applicable to helping us
understand the impact of other architecture choices such as skip/residual
connections as well as training hyperparameters such as weight
initializations, learning rate schedules etc. Progressive Depth Factorization
provides a general framework not only for systematically understanding the
efficiency/accuracy trade-offs of factorization, but also for finding the
optimal factorization configuration. As there are many directions that can be
taken through the “Progressive Depth Factorization space", our method can be
merged with automated search methods such as GenSynth [11] to trace out
various paths through the space, especially for increasingly complex
architectures.

Figure 3:  Reverse Pyramid Factorization Scheme. For this factorization
scheme, we start with an initial factorization rate, finit, and double the
factorization rate each time the input depth doubles, thus preserving the
number of channels per group throughout the network. For finit = 64, we
recover the depthwise separable CNN.

Figure 4:  Best viewed in colour. Far left: Accuracy vs MACs (fp32 and quint8
accuracy) under depth factorization. Since the Dense layers are fixed, we only
compare the MAC totals of the convolution layers. Center left: QMSE vs MACs.
Center right: QCE vs MACs. Far right: Percent accuracy decrease vs MACs.

##  3 Experiment

We start with a VGG-like macroarchitecture (see Figure 2) trained and tested
on CIFAR-10. As we begin to factorize, the regular convolution layers (except
for the first layer, which stays constant) are replaced with “Groupwise
Separable" Convolution where factorization rate f is a programmable parameter.
We refer to the resulting set of architectures as FactorizeNet. The groupwise
separable convolution follows the structure of depthwise separable
convolutions [4]. Ie. GroupConv-BatchNorm-Relu-PointwiseConv. When f = input
depth, we recover depthwise separable convolutions. Following best practices,
we always use a Conv-BatchNorm-Relu op-pattern. We demonstrate two
progressively increasing factorization methods. The first is a uniform
factorization configuration. Ie. A single factorization rate is applied to
every Groupwise Separable Conv layer in the network. We progressively double
this factorization rate on each step through the search space. We train
networks with uniform factorizations of f = 2, 4, 8, 16. These networks are
denoted FactorizeNet-fj where j is uniform factorization rate (e.g.,
FactorizeNet-f2 is the network with a uniform factorization rate of 2). The
second approach is to progressively double the factorization rate as we go
deeper into the CNN in a Reverse Pyramid configuration (see Figure 3 for
details). For Reverse Pyramid factorization, we train networks with finit = 2,
4. These networks are denoted FactorizeNet-finitk where k is initial
factorization rate (eg. FactorizeNet-finit2 is the network with reverse
pyramid factorization and initial factorization rate of 2). We also train
FactorizeNet with regular convolution and depthwise separable convolution in
place of Groupwise Separable Conv (denoted Regular_Conv and DWS_Conv). Each
network is trained from scratch for 200 epochs of SGD with Momentum = 0.9,
batch-size = 128, and Glorot Uniform initializer [12] for all layers. Initial
learning rate is 0.01 and we scale it by 0.1 at the 75th, 120th, and 170th
epochs. For the activation range tracking we perform top/bottom 1% clipping
computed on a random sample of 1024 training samples. Basic data augmentation
includes vertical/horizontal shift, zoom, vertical/horizontal flip and
rotation. We use Tensorflow for training and quantizing the weights and
activations to quint8 format. Basic top/bottom 1% percentile clipping is used
for activation quantization as it is a common, low-overhead method.

For each network we observe the efficiency-accuracy trade-offs with respect to
4 quantities: fp32 accuracy, quantized 8-bit (quint8) accuracy, quantized
mean-squared error (QMSE), and quantized crossentropy (QCE). QMSE refers to
the MSE between the fp32 network outputs and the quint8 network outputs after
dequantization. Similarly, QCE measures the cross entropy between the fp32
network outputs and the dequantized quint8 network outputs. While QMSE
directly measures the difference in network output, QCE quantifies the
difference in distribution of the network outputs. For classification, QCE can
sometimes be more reflective of differences in behaviour. Additionally, we
also observe the relative accuracy degradation (change in accuracy divided by
fp32 accuracy) of each network after quantization. Figure 4 shows these
quantities vs MAC-count.

Figure 5:  Left: Weights ranges per layer. Center: BN-Fold weights ranges.
Right: Activations ranges. Note: Due to lack of space, we did not show the
average precisions. However, these are still valuable statistics.

Figure 6: Comparing DWS_Conv, FactorizeNet-f16, and FactorizeNet-ff2 Far left:
Weights ranges. Center left: BN-Fold weights ranges. Center right: Activations
ranges. Far right: BN-Fold weights precisions.

##  4 Discussion

From Figure 4, we have a high-level picture of the efficiency/accuracy trade-
offs. Interestingly, FactorizeNet-finit2 (104.3 MMACs, 86.01% fp32 acc, 80.31%
quint8 acc) has less MACs than FactorizeNet-f2 (153.8 MMACs, 86.54% fp32 acc,
80.05% quint8 acc) but similar accuracy. Furthermore, if targeting fp32
environments, FactorizeNet-finit2 would offer over 2.5x MAC reduction from
Regular_Conv (266.0 MMACs, 88.37% fp32 acc, 85.60% quint8 acc) with a very
small accuracy reduction. When analyzing quantized accuracy, some interesting
anomalies emerge. Specifically the sharp drop in accuracy for FactorizeNet-f16
(14.8% relative accuracy drop). Also worth noting is that while most of the
other models have higher quantized accuracy, DWS_Conv experiences a noticeably
smaller relative decrease in quantized accuracy (4.21% vs. 5.88% - 7.53%).
This may be due to the much smaller increase in range of the BN-Fold weights
in its first layer.

To get a better understanding of the factors contributing to the degradation
in FactorizeNet-f16, we move to our low-level analysis. Figure 5 shows the
dynamic ranges of each layer. This low-level information gives us a direct
look at the underlying distributions and how they interact with quantization
noise. For example, besides generally smaller weights ranges (both convolution
weights and batchnorm-folded weights), Regular_Conv activations ranges are
also noticeably lower. This begins to explain why Regular_Conv is so robust to
quantization (3.13% relative accuracy loss). Going back to FactorizeNet-f16,
the increased BN-Fold weights ranges early in the network may begin to explain
why this CNN experienced a sharp drop in quantized accuracy. Furthermore, if
we analyze the average precision of the BN-Fold weights in FactorizeNet-f16 we
see a combination of large range and low precision in the early, low-level
feature extraction layers. Interestingly, the BN-Fold weights in
FactorizeNet-f2 show an even worse average precision in the first layer.
However, the precision of BN-Fold weights in FactorizeNet-f2 is higher on
average and hints at a more representative projection of the network’s layers
from their continuous distribution into a discretized space. Furthermore, we
observe a generally lower range of activations for Factorizenet-f2. See Figure
6 for detailed comparison. Zooming back out to the inter-network trends, we
can see from the BN-Fold weights ranges that there may be a significant loss
of information in the early low-level feature extraction stages. It would be
interesting to see how these distributions change if we do not use BatchNorm
for the first layer since the pre-BN-Fold weights have a much smaller range.
While it is intractable to pinpoint any single reason for the observed
quantized behaviour, our layer-level analysis reveals a rich set of
interconnected factors contributing to each network’s system dynamics. We
could even further expand our analysis to use more rigorous, yet scalable
statistical methods for layerwise analysis. From these initial analyses, we
see that a fine-grained, systematic analysis can yield detailed insights to
help further guide our design process.

##  5 Conclusion

We introduce a systematic, progressive depth factorization strategy coupled
with a fine-grained layerwise analysis for exploring the efficiency/accuracy
trade-offs of factorizing CNN architectures. In doing so, we can gain detailed
insights on the impact of depth factorization on final floating point and
quantized accuracy and also identify the optimal factorization configuration
(ie. FactorizeNet). Future work includes using more sophisticated algorithms
for increasing factorization, investigating activation sparsity under
factorization, and factorizing more complex blocks/architectures.

## References

  * [1] B. Jacob, S. Kligys, B. Chen, M. Zhu, M. Tang, A. G. Howard, H. Adam, and D. Kalenichenko, “Quantization and training of neural networks for efficient integer-arithmetic-only inference,” _CoRR_ , vol. abs/1712.05877, 2017.
  * [2] S. R. Jain, A. Gural, M. Wu, and C. Dick, “Trained uniform quantization for accurate and efficient neural network inference on fixed-point hardware,” _CoRR_ , vol. abs/1903.08066, 2019.
  * [3] M. Nagel, M. van Baalen, T. Blankevoort, and M. Welling, “Data-free quantization through weight equalization and bias correction,” _CoRR_ , vol. abs/1906.04721, 2019.
  * [4] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam, “Mobilenets: Efficient convolutional neural networks for mobile vision applications,” _CoRR_ , vol. abs/1704.04861, 2017\.
  * [5] X. Zhang, X. Zhou, M. Lin, and J. Sun, “Shufflenet: An extremely efficient convolutional neural network for mobile devices,” _CoRR_ , vol. abs/1707.01083, 2017.
  * [6] S. Xie, R. B. Girshick, P. Dollár, Z. Tu, and K. He, “Aggregated residual transformations for deep neural networks,” _CoRR_ , vol. abs/1611.05431, 2016.
  * [7] F. Chollet, “Xception: Deep learning with depthwise separable convolutions,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 1251–1258.
  * [8] G. Huang, S. Liu, L. van der Maaten, and K. Q. Weinberger, “Condensenet: An efficient densenet using learned group convolutions,” _CoRR_ , vol. abs/1711.09224, 2017.
  * [9] T. Sheng, C. Feng, S. Zhuo, X. Zhang, L. Shen, and M. Aleksic, “A quantization-friendly separable convolution for mobilenets,” in _2018 1st Workshop on Energy Efficient Machine Learning and Cognitive Computing for Embedded Applications (EMC2)_ , 2018, pp. 14–18.
  * [10] S. Ioffe and C. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate shift,” _CoRR_ , vol. abs/1502.03167, 2015.
  * [11] A. Wong, M. Javad Shafiee, B. Chwyl, and F. Li, “Gensynth: a generative synthesis approach to learning generative machines for generate efficient neural networks,” _Electronics Letters_ , vol. 55, no. 18, pp. 986–989, 2019.
  * [12] X. Glorot and Y. Bengio, “Understanding the difficulty of training deep feedforward neural networks,” ser. Proceedings of Machine Learning Research, Y. W. Teh and M. Titterington, Eds., vol. 9. Chia Laguna Resort, Sardinia, Italy: JMLR Workshop and Conference Proceedings, 13–15 May 2010, pp. 249–256.