11institutetext: Department of Physics, Pusan National University, Busan
46241, Korea 22institutetext: Institute for Extreme Physics, Pusan National
University, Busan 46241, Korea 33institutetext: Swansea Academy of Advanced
Computing, Swansea University (Bay Campus), Fabian Way, SA1 8EN Swansea,
Wales, United Kingdom 44institutetext: Institute of Physics, National Yang
Ming Chiao Tung University, 1001 Ta-Hsueh Road, Hsinchu 30010, Taiwan
55institutetext: Center for High Energy Physics, Chung-Yuan Christian
University, Chung-Li 32023, Taiwan 66institutetext: Department of Mathematics,
Faculty of Science and Engineering, Swansea University (Bay Campus), Fabian
Way, SA1 8EN Swansea, Wales, United Kingdom 77institutetext: Department of
Physics, Faculty of Science and Engineering, Swansea University (Park Campus),
Singleton Park, SA2 8PP Swansea, Wales, United Kingdom 88institutetext: Centre
for Mathematical Science, University of Plymouth, Plymouth, PL4 8AA, United
Kingdom

# Composite dynamics in Sp($2N$) gauge theories

Jong-Wan Lee 1122<EMAIL_ADDRESS>Ed Bennett 33 Deog Ki Hong 11 Ho Hsiao
44 C.-J. David Lin 4455 Biagio Lucini 3366 Maurizio Piai 77 Davide Vadacchino
88

###### Abstract

Sp($2N$) gauge theories with fermonic matter provide an ideal laboratory to
build extensions of the standard model based on novel composite dynamics.
Examples include composite Higgs along with top partial compositeness and
composite dark matter. Without fermions, their study also complements those
based on SU($N_{c}$) gauge theories with which they share a common sector in
the large $N_{c}=2N$ limit. We report on our recent progress in the numerical
studies of Sp($2N$) gauge theories discretised on a four-dimensional Euclidean
lattice. In particular, we present preliminary results for the low-lying mass
spectra of mesons and chimera baryons in the theories with $N=2$. We also
compute the topological susceptibility for various values of $N$, extrapolate
the results to the large $N$ limit, and discuss certain universal properties
in Yang-Mills theories.

##  1 Introduction

Non-abelian gauge theories based on Sp($N_{c}=2N$) groups coupled to fermions
exhibit interesting nonperturbative phenomena, such as confinement and global
symmetry breaking, analogous to the SU($N_{c}$) gauge theories. In Yang-Mills
theories, they provide another family of groups in which certain universal
features are expected to emerge in the large $N_{c}$ limit. In the opposite
extreme limit we have SU($2$) $=$ Sp($2$). A distinctive feature is that the
fundamental representation of Sp($2N$) is pseudoreal. When the gauge dynamics
is coupled to $N_{f}$ fundamental Dirac flavours, the main consequences are
two-fold. On the one hand, finite density calculations are free from the sign
problem, a notorious hindrance in the numerical studies of QCD, and thus may
provide new physical insights on the phase diagram. On the other hand, the
global symmetry associated with the flavour is enhanced to SU($2N_{f}$), which
is spontaneously and explicitly broken into Sp($2N_{f}$) in the presence of
fermion condensation and non-zero (degenerate) mass. Because such a symmetry
breaking pattern yields a comparatively large coset space, one can take
advantage of it when constructing certain classes of phenomenological
extensions of the standard model (SM), such as composite Higgs, top partial
compositeness, and a strongly interacting massive particle (SIMP) as dark
matter candidate. Furthermore, it is known that the finite-temperature
transition of pure Sp($2N$) gauge theories is first order for $N\geq 2$
Holland:2003kg , which has a potential impact on studies of the cosmological
evolution of the early universe and on gravitational wave experiments. It
should be emphasized that, in principle, Sp($2N$) gauge theories are equally
important as SU($N_{c}$) in the searches for new physics based on novel
strongly coupled gauge theories.

Figure 1: Phase diagram of Sp($4$) gauge theory with $N_{f}$ fundamental and
$n_{f}$ antisymmetric Dirac fermions. The shaded region denotes the conformal
window recently estimated in Ref. Kim:2020yvr , while dashed lines denote
other analytical estimations in the literature, which are discussed in the
same reference. The coloured dots represent the theories realising the
phenomenological models discussed in the main text.

To perform lattice simulation, we need to choose a concrete model, well
motivated by both theoretical and phenomenological arguments. We concentrate
on the minimal Sp($4$) theory with which one can build both composite Higgs
and top partial compositeness. In Fig. 1, we show the theory space of Sp($4$)
with $N_{f}$ fundamental and $n_{f}$ $2$-index antisymmetric Dirac fermions.
Representative models taken from the literature are denoted by red
Barnard:2013zea ; Ferretti:2016upr , blue Ferretti:2016upr  and black
Cacciapaglia:2019dsq  colours. As the infrared (IR) behaviour of strongly
coupled gauge theories determines what type of applications they suit, in the
figure we also present the results of a recent analytical study of the edge of
the conformal window (CW), compared with other analytical estimations (see
Ref. Kim:2020yvr  and references therein for the details).

The theory with $N_{f}=2$ fundamental and $n_{f}=3$ antisymmetric Dirac
fermions is expected to be in the chirally broken phase. The resulting $5$
pseudo Nambu-Goldstone bosons (pNGBs) in the fundamental sector include the SM
Higgs doublets. This theory can be studied by employing currently available
numerical lattice techniques without altering the flavour structure of the
original, phenomenologically motivated model. Since numerical studies of gauge
theories with mixed representations are relatively new to the lattice
community, and computationally demanding in the presence of dynamical
fermions, we have first considered the quenched approximation Bennett:2017kga
; Bennett:2019cxd  and in stages introduced dynamical Dirac flavours in the
form of two fundamental Bennett:2019jzz , three antisymmetric Lee:2022elf  and
both combined Bennett:2022yfa .

In parallel, we have been studying pure Sp($2N$) gauge theories on the lattice
with various values of $N$, $N=1,\,2,\,3,\,4$, and furthermore considered the
extrapolation towards the large $N$ limit. We have studied the string tension,
the mass spectra of glueballs with many different quantum numbers (including
some excited states) Bennett:2020qtj , the Wilson flow and the topological
susceptibility Bennett:2022ftz , and found empirical evidence of the emergence
of universal patterns in Yang-Mills theories Hong:2017suj ; Bennett:2020hqd ;
Bennett:2022gdz .

##  2 Lattice setup

The lattice action of Sp($2N$) gauge theories is discretised in a four-
dimensional Euclidean space with temporal and spatial extents $T$ and $L$,
respectively. We adopt the standard plaquette action for pure gauge
interactions and the Wilson-Dirac action for gauge-fermion interactions.
Details can be found in Refs. Bennett:2022ftz ; Bennett:2022yfa  and
references therein. Numerical calculations have been carried out by employing
the Heat Bath algorithms for the pure Sp($2N$) theories and the (rational)
hybrid Monte Carlo algorithms for the Sp($4$) theories with dynamical
fermions. The lattice action contains a lattice coupling $\beta\equiv
4N/g^{2}$ and fermion masses $am_{0}^{f}$ and $am_{0}^{as}$ for the
fundamental and antisymmetric representations, respectively. Here, $g$ is the
bare gauge coupling and $a$ is the lattice spacing.

The lattice parameters need to be chosen carefully so that the lattice
measurements can be extrapolated to the corresponding continuum ones by taking
$\beta\rightarrow\infty$ in a controlled way. In particular, we invegstigated
the presence of a first-order bulk phase transition and, if it exists,
determined the critical coupling $\beta^{c}$ associated with the boundary
between strong and weak coupling regimes. We have shown that Sp($2N$) Yang-
Mills for $N=1,\,2,\,3,\,4$ exhibits a smooth crossover Bennett:2020qtj ,
while dynamical Sp($4$) theories undergo a first-order transition in the
strong coupling regime Bennett:2017kga ; Lee:2018ztv ; Bennett:2022yfa .
Having the values of $\beta^{c}$ in hand, we have performed all the numerical
simulations in the weak coupling regime, $\beta>\beta^{c}$, and extrapolated
to the continuum, if possible. Furthermore, we have used choices of the
lattice volume for which finite size corrections to the observables are
statistically negligible. We elected to set a scale for dimensionful
quantities by using the gradient flow method Luscher:2010iy . Two different
definitions of the flow scale, $t_{0}$ Luscher:2010iy  and $w_{0}$
Borsanyi:2012zs , are available. Furthermore, the string tension $\sigma$ can
be used in the case of pure Sp($2N$) Yang-Mills.

##  3 Results: Sp($2N$) Yang-Mills

In this section, we briefly summarise our main findings on Sp($N_{c}=2N$) pure
gauge theories with $N=1,\,2,\,3,\,4$ and discuss certain universal features
in Yang-Mills theories by comparing to SU($N_{c}$) and SO($N_{c}$) gauge
theories. We refer the reader to Refs. Bennett:2020qtj ; Bennett:2022ftz ;
Bennett:2020hqd ; Bennett:2022gdz  for the full details of lattice
technicalities and numerical results.

Two main observables are the mass of glueballs and the string tension, which
are extracted from the large-time behaviour of the $2$-point correlation
functions built out of Wilson and Polyakov loops, respectively. Two-point
functions involving Polyakov loops have been measured to extract the string
tension. The masses of glueballs are obtained by studying a variational
problem involving correlators between two Wilson loops of various shapes and
sizes. The spin quantum numbers $J$ of the glueball states in the continuum
theory are determined through the decomposition of the irreducible
representations of the octahedral group—the symmetry group of a cubic
lattice—in the lattice theory. Using variational techniques, we were able to
extract the masses for the ground states with
$J^{P}=0^{\pm},\,1^{\pm},\,2^{\pm},\,3^{\pm}$ as well as for the first excited
states with $0^{\pm}$ Bennett:2020qtj . After performing the continuum
extrapolations of the glueball masses in units of $\sqrt{\sigma}$ at each
$N_{c}$, we took the large $N_{c}$ limit by including a $\mathcal{O}(1/N_{c})$
correction term. We found that the resulting values at $N_{c}=\infty$ are in
good agreement with those for SU($N_{c}$) Bennett:2020qtj ; Lucini:2021xke .
We also note that the lightest and the second lightest states are the
positive-parity scalar and tensor glueballs.

Figure 2: Numerical results and extrapolations towards the large $N_{c}$
limit, showing the convergence of the SU($N_{c}$), Sp($N_{c}$) and SO($N_{c}$)
Yang-Mills theories: (left) Casimir scaling in the lightest scalar glueballs,
and (right) mass ratio between the lightest scalar and tensor glueballs,
$R\equiv m_{2^{++}}/m_{0^{++}}$. The constant $\eta$ is defined in Eq. (1).
Figures from Refs. Hong:2017suj ; Bennett:2020qtj ; Bennett:2020hqd .

Recently, it has been argued that certain ratios between physical observables,
up to appropriate gauge-group factors, might exhibit universal behaviours even
at finite $N_{c}$ in SU($N_{c}$), Sp($N_{c}$) and SO($N_{c}$) Yang-Mills
Hong:2017suj ; Athenodorou:2016ndx . Here, universal means that the ratio only
depends on the space-time dimension of the theory, $d$, regardless of the
number of colours $N_{c}$ and the gauge groups. First of all, in Ref.
Hong:2017suj  the authors conjectured that the ratio $m_{0^{++}}^{2}/\sigma$
is proportional to the ratio of eigenvalues of quadratic Casimir operators in
the adjoint (Adj) and the fundamental (F) representations, which is supported
by existing lattice results for SO($N_{c}$) in $d=(2+1)$ and SU($N_{c}$) in
both $d=(2+1)$ and $(3+1)$ theories. Combining our results for Sp($N_{c}$), as
shown in Fig. 2, we obtained the following results for the universal constant
$\eta$ Hong:2017suj ; Bennett:2020qtj

$\eta\equiv\frac{m_{0^{++}}^{2}}{\sigma}\cdot\frac{C_{2}(F)}{C_{2}(Adj)}=\begin{cases}5.388(81)(60),&d=(3+1),\\\
8.440(14)(76),&d=(2+1),\end{cases}$ (1)

where the first and second parentheses denote the statistical and systematic
errors, respectively.

A second interesting quantity is the mass ratio between the lightest parity-
even scalar and tensor glueballs, $R\equiv m_{2^{++}}/m_{0^{++}}$, first
proposed in Ref. Athenodorou:2016ndx . In Fig. 2, we present the lattice
results available in the literature as well as analytical results obtained by
gauge-gravity dualities and field-theoretical calculations. Details are found
in Ref. Bennett:2020hqd . As seen in the figure, it is evident that the ratio
$R$ is independent of $N_{c}$ and the gauge group, but gives rise to different
values for $d=(2+1)$ and $(3+1)$ dimensions.

Figure 3: Topological susceptibilities $\chi$ in units of the string tension
$\sigma$, rescaled by group factors $C_{2}(F)^{2}/d_{G}$, for SU($N_{c}$) and
Sp($N_{c}$) Yang-Mills as a function of the dimension of the group $d_{G}$.
The figure is taken from Ref. Bennett:2022gdz .

An interesting non-perturbative quantity, which is closely related with the
$U(1)_{A}$ problem and the $\theta$-term, is the topological susceptibility
$\chi$. Since $\chi$ is defined as a second derivative of the vacuum density
$F(\theta)$ with respect to $\theta$, and each gauge field contributes
equally, it has been conjectured to be proportional to the dimension of group
$d_{G}$. We hence investigate the behaviour of the ratio
$\eta_{\chi}\equiv\chi C_{2}(F)^{2}/\sigma^{2}d_{G}$ Bennett:2022gdz . A
survey of lattice results for $d=(3+1)$ SU($N_{c}$) and Sp($N_{c}$) Yang-Mills
can be found in Fig. 3. While the two sequences of gauge groups agree with
each other, we observe a visible dependence on $d_{G}$. After accounting for
the $N_{c}$ dependence, we took the large-$N_{c}$ extrapolation and obtained
Bennett:2022gdz :

$\eta_{\chi}(N_{c}=\infty)=48.4(8)(33)\times 10^{-4},$ (2)

where the first and second parentheses again denote the statistical and the
systematic errors.

##  4 Results: Sp($4$) with fermions

We restrict ourselves to the Sp($4$) gauge group for the cases involving
fermionic matter fields. Because these are the first numerical studies of
fermions in the fundamental and antisymmetric representations transforming
under Sp($2N$) with $N\geq 2$, we have performed nontrivial tests of the
algorithms. A particularly important cross-check pertains the breaking pattern
of the flavour symmetry. Following the work in Ref. Cossu:2019hse , we
calculated the eigenvalues of the Dirac operators in the quenched ensemble on
a small lattice of size $4^{4}$, and compared the unfolded density of
spacings, $P(s)$, with the predictions of chiral random matrix theory
($\chi$RMT) Bennett:2022yfa . As seen in Fig. 4, the histograms of our
numerical data are well described by the $\chi$RMT predictions, denoted as
solid lines, with the expected breaking patterns of SU($2N_{f}$)/Sp($2N_{f}$)
and SU($2N_{f}$)/SO($2N_{f}$) for the fundamental and antisymmetric fermions,
respectively.

Figure 4: The unfolded density of the spacings between subsequent Dirac
eigenvalues for the fundamental (left) and antisymmetric (right)
representations. The black histogram denotes the numerical data, while the
coloured solid lines are the $\chi$RMT predictions. Figures from Ref.
Bennett:2022yfa .

We now turn our attention to the results for dynamical fermions. In Ref.
Bennett:2019jzz , we reported the spectral results for flavoured mesons in the
lightest spin-$0$ and -$1$ channels, measured on dynamical ensembles with
$N_{f}=2$ fundamental Dirac fermions. We examined the fermion mass dependence
of the mass and decay constant of pseudoscalar meson, the lightest state in
the spectrum, and found clear evidence of the spontaneous breaking of the
global symmetry: the mass squared is proportional to the fermion mass and the
decay constant extrapolates to a non-zero value in the massless limit. This is
expected by the fact that the pNGBs span the SU($4$)/Sp($4$) coset relevant
for models of composite Higgs and SIMP dark matter. Concerning the theory with
$n_{f}=3$ antisymmetric Dirac fermions, we also found some evidence of the
spontaneous beaking of the global symmetry in our preliminary results
Lee:2022elf , which need to be further confirmed by extending the calculations
to smaller fermion mass. In the case of a fully dynamical Sp($4$) theory with
both two fundamental and three antisymmetric fermions, we have carried out
lattice studies on a single ensemble so far Bennett:2022yfa , and thus cannot
yet make any statement on its IR nature.

Figure 5: (left) Vector meson masses in various gauge theories with $N_{f}=2$
fundamental Dirac flavours: different colours are for various gauge groups,
while the black dot denotes the QCD value. (right) Vector meson masses in
Sp($4$) theory with $N_{f}=2$ fundamental (in the continuum, black) and
$n_{f}=3$ antisymmetric (colours for different $\beta$ values) Dirac flavours.
The hatted notation denotes the mass in units of the gradient flow scale,
$w_{0}$, e.g. $\hat{m}_{\rm PS}=m_{\rm PS}w_{0}$. Figures are taken from Refs.
Bennett:2019jzz ; Lee:2022elf .

The lightest state in the spin-$1$ channel is the vector meson. Its mass is
expected to be non-zero in the massless limit. A particularly interesting
quantity is its mass in units of the pseudoscalar decay constant, $m_{\rm
V}/\sqrt{2}f_{\rm PS}$, which is closely related with the low-energy constant
associated with its decay to two pseudoscalar mesons via the phenomenological
KSRF relation Kawarabayashi:1966kd ; Riazuddin:1966sw . In Fig. 5, we show our
results for the $N_{f}=2$ fundamental Sp($4$) theory in the continuum limit,
compared to other gauge theories Bennett:2019jzz . The resulting masses are
below the threshold of the two-pseudoscalar decay, yet our results indicate a
value for the ratio in Sp($4$) that is somewhere between SU($3$) and SU($4$)
theories near the threshold.

The right panel of Fig. 5 shows our preliminary results for the same ratio for
the $n_{f}=3$ antisymmetric Sp($4$) theory measured at different $\beta$
values. For comparison, we also present the continuum results of the $N_{f}=2$
fundamental Sp($4$) theory. Although a direct comparison may not be possible
due to the different mass range (and the absence so far of a continuum
extrapolation in the former case), we can see that the former is slightly
smaller than the latter. This result is consistent with large-$N_{c}$
argument: $m_{\rm V}$ is independent on the representation while $f_{\rm
PS}^{2}$ is proportional to the dimension of the representation. A survey of
the lattice results of $m_{\rm V}/f_{\rm PS}$ for various gauge theories, e.g.
different numbers of colours and flavours, and different gauge groups and
fermion representations, can be found in Ref. Nogradi:2019auv .

Figure 6: Effective mass plots for the lightest spin-$1/2$ and $3/2$ chimera
baryons in partially quenched approximation. The details of the ensemble can
be found in Ref. Bennett:2022yfa . The valence fermions masses are
$(am^{f}_{v},\,am^{as}_{v})=(-0.71,\,-1.01)$ and $(-0.75,\,-0.8)$ for the left
and right panels, respectively.

The most interesting and distinct feature of gauge theories with mixed
representations is the existence of colour-singlet baryonic objects, dubbed
chimera baryons, some of which have the same SM quantum numbers of the top
quark. In modern scenarios of composite Higgs, in particular, this feature is
exploited to explain the large mass of the top quark, through partial
compositeness. In the Sp($4$) theory considered in this work, the
interpolating operators for the chimera baryons can be constructed from two
fundamental and one antisymmetric fermion constituents. Even though the colour
contraction and the flavour symmetry are completely different from QCD, the
structure of these operators is similar to that for the QCD baryons involving
one heavy quark. More explicitly, we label the lightest spin-$1/2$ and $3/2$
chimera states, $(J,R)=(1/2,5)$, $(1/2,10)$ and $(3/2,10)$ by $\Lambda$,
$\Sigma$ and $\Sigma^{*}$, respectively, where, $J$ and $R$ denote the spin
and the irreducible representation of the flavour group acting on the
fundamental fermions.

We refer the reader to Refs. Bennett:2022yfa ; Hsiao:2022kxf  for details on
the interpolating operators, the parity and spin projections, the
measurements, and exploratory studies of the spectrum. One observation we
immediately made from our preliminary studies, using the dynamical ensemble
with $(\beta,am^{f}_{0},am^{as}_{0})=(6.5,-0.71,-1.01)$, was that $\Lambda$,
being a natural choice of top partner, e.g. Ref. Gripaios:2009pe  (but, see
also Ref. Banerjee:2022izw  for the other possibilities), is not the lightest
state, as shown in the left panel of Fig. 6. To further investigate the mass
hierarchy of chimera baryons, we performed additional measurements in a
partially quenched setup using the same ensemble—the valence fermion mass is
different to the sea fermion, $m^{f,as}_{v}\neq m^{f,as}_{0}$. With the
choices of $(am^{f}_{v},am^{as}_{v})=(-0.75,-0.8)$, we find that the mass
ratio between pseudoscalar mesons composed of antisymmetric and fundamental
constituents $m_{\rm PS}^{as}/m_{\rm PS}^{f}$ is about $4.3$, and $\Lambda$ is
almost degenerate with $\Sigma$ and thus the lightest state in the baryon
spectrum. A similar behaviour has been observed in the quenched approximation
Hsiao:2022kxf .

Acknowledgements - We thank Gabriele Ferretti for useful communications. The
work of J. W. L is supported by the National Research Foundation of Korea
(NRF) grant funded by the Korea government (MSIT) (NRF-2018R1C1B3001379). The
work of E. B. has been funded in part by the UKRI Science and Technology
Facilities Council (STFC) Research Software Engineering Fellowship
EP/V052489/1. The work of D. K. H. was supported by Basic Science Research
Program through the National Research Foundation of Korea (NRF) funded by the
Ministry of Education (NRF-2017R1D1A1B06033701). The work of H. H. and C. J.
D. L. is supported by the Taiwanese MoST Grant No. 109-2112-M-009 -006 -MY3.
The work of B. L. and M. P. has been supported in part by the STFC
Consolidated Grants No. ST/P00055X/1 and No. ST/T000813/1. B. L. and M. P.
received funding from the European Research Council (ERC) under the European
Unionâs Horizon 2020 research and innovation program under Grant Agreement No.
813942. The work of B. L. is further supported in part by the Royal Society
Wolfson Research Merit Award No. WM170010 and by the Leverhulme Trust Research
Fellowship No. RF-2020-4619. The work of D. V. is supported in part the Simons
Foundation under the program âTargeted Grants to Institutesâ awarded to the
Hamilton Mathematics Institute. Numerical simulations have been performed on
the Swansea SUNBIRD cluster (part of the Supercomputing Wales project) and
AccelerateAI A100 GPU system, on the local HPC clusters in Pusan National
University (PNU) and in National Yang Ming Chiao Tung University (NYCU), and
on the DiRAC Data Intensive service at Leicester. The Swansea SUNBIRD system
and AccelerateAI are part funded by the European Regional Development Fund
(ERDF) via Welsh Government. The DiRAC Data Intensive service at Leicester is
operated by the University of Leicester IT Services, which forms part of the
STFC DiRAC HPC Facility (www.dirac.ac.uk). The DiRAC Data Intensive service
equipment at Leicester was funded by BEIS capital funding via STFC capital
grants ST/K000373/1 and ST/R002363/1 and STFC DiRAC Operations grant
ST/R001014/1. DiRAC is part of the National e-Infrastructure.

Open Access Statement- For the purpose of open access, the authors have
applied a Creative Commons Attribution (CC BY) licence to any Author Accepted
Manuscript version arising.

## References

  * (1) K. Holland, M. Pepe, U.J. Wiese, Nucl. Phys. B 694, 35 (2004), hep-lat/0312022
  * (2) B.S. Kim, D.K. Hong, J.W. Lee, Phys. Rev. D 101, 056008 (2020), 2001.02690
  * (3) J. Barnard, T. Gherghetta, T.S. Ray, JHEP 02, 002 (2014), 1311.6562
  * (4) G. Ferretti, JHEP 06, 107 (2016), 1604.06467
  * (5) G. Cacciapaglia, S. Vatani, C. Zhang, Phys. Lett. B 815, 136177 (2021), 1911.05454
  * (6) E. Bennett, D.K. Hong, J.W. Lee, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino, JHEP 03, 185 (2018), 1712.04220
  * (7) E. Bennett, D.K. Hong, J.W. Lee, C.J.D. Lin, B. Lucini, M. Mesiti, M. Piai, J. Rantaharju, D. Vadacchino, Phys. Rev. D 101, 074516 (2020), 1912.06505
  * (8) E. Bennett, D.K. Hong, J.W. Lee, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino, JHEP 12, 053 (2019), 1909.12662
  * (9) J.W. Lee, E. Bennett, D.K. Hong, H. Hsiao, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino, PoS LATTICE2022, 214 (2022), 2210.08154
  * (10) E. Bennett, D.K. Hong, H. Hsiao, J.W. Lee, C.J.D. Lin, B. Lucini, M. Mesiti, M. Piai, D. Vadacchino, Phys. Rev. D 106, 014501 (2022), 2202.05516
  * (11) E. Bennett, J. Holligan, D.K. Hong, J.W. Lee, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino, Phys. Rev. D 103, 054509 (2021), 2010.15781
  * (12) E. Bennett, D.K. Hong, J.W. Lee, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino, Phys. Rev. D 106, 094503 (2022), 2205.09364
  * (13) D.K. Hong, J.W. Lee, B. Lucini, M. Piai, D. Vadacchino, Phys. Lett. B 775, 89 (2017), 1705.00286
  * (14) E. Bennett, J. Holligan, D.K. Hong, J.W. Lee, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino, Phys. Rev. D 102, 011501 (2020), 2004.11063
  * (15) E. Bennett, D.K. Hong, J.W. Lee, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino, Phys. Lett. B 835, 137504 (2022), 2205.09254
  * (16) J.W. Lee, E. Bennett, D.K. Hong, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino, PoS LATTICE2018, 192 (2018), 1811.00276
  * (17) M. Lüscher, JHEP 08, 071 (2010), [Erratum: JHEP 03, 092 (2014)], 1006.4518
  * (18) S. Borsanyi et al., JHEP 09, 010 (2012), 1203.4469
  * (19) B. Lucini, E. Bennett, J. Holligan, D.K. Hong, H. Hsiao, J.W. Lee, C.J.D. Lin, M. Mesiti, M. Piai, D. Vadacchino, EPJ Web Conf. 258, 08003 (2022), 2111.12125
  * (20) A. Athenodorou, E. Bennett, G. Bergner, D. Elander, C.J.D. Lin, B. Lucini, M. Piai, JHEP 06, 114 (2016), 1605.04258
  * (21) G. Cossu, L. Del Debbio, M. Panero, D. Preti, Eur. Phys. J. C 79, 638 (2019), 1904.08885
  * (22) K. Kawarabayashi, M. Suzuki, Phys. Rev. Lett. 16, 255 (1966)
  * (23) Riazuddin, Fayyazuddin, Phys. Rev. 147, 1071 (1966)
  * (24) D. Nogradi, L. Szikszai, PoS LATTICE2019, 237 (2019), 1912.04114
  * (25) H. Hsiao, Bennett, D.K. Hong, J.W. Lee, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino (2022), 2211.03955
  * (26) B. Gripaios, A. Pomarol, F. Riva, J. Serra, JHEP 04, 070 (2009), 0902.1483
  * (27) A. Banerjee, D.B. Franzosi, G. Ferretti, JHEP 03, 200 (2022), 2202.00037


# Insulated primes

Abhimanyu Kumar∗ Electrical and Instrumentation Engineering Department
Thapar Institute of Engineering and Technology
Patiala–147004, Punjab, India<EMAIL_ADDRESS>and  Anuraag Saxena
Electronics and Communication Engineering Department
Thapar Institute of Engineering and Technology
Patiala–147004, Punjab, India<EMAIL_ADDRESS>
###### Abstract.

The degree of insulation $D(p)$ of a prime $p$ is defined as the largest
interval around the prime $p$ in which no other prime is present. Based on
this, the $n$-th prime $p_{n}$ is said to be insulated if and only if its
degree of insulation is higher than its surrounding primes. Thus, a new
special sequence emerges which is 7, 13, 23, 37, 53, 67, 89, 103, 113, 131,
139, 157, 173, 181, 193, 211, 233, 277, 293, and so on. Therefore, this paper
thoroughly investigates its properties and explores the connection of $D(p)$
with the gap between consecutive primes. Heuristically, it is shown that
$n$-th insulated prime grows almost linearly, which is a property in contrast
to the effort to obtain a general formula for $n$-th prime. Finally, the paper
leaves the readers with a captivating open problem.

###### Key words and phrases:

Special prime sequences; Prime gaps

###### 2010 Mathematics Subject Classification:

11A41, 11K31

##  1\. Introduction

Since centuries, prime numbers have both puzzled and fascinated researchers.
Several interesting subsets of primes have been identified and analyzed in
literature [3]. For example, primes that are present in a specific form such
as Proth prime, Mersenne prime, and Fermat prime [7]. Sequences of primes are
also defined if they obey certain property, for instance, Chen prime [1],
Lucky prime [4], Wilson prime [2], Ramanujan prime [11], etc. which have
captured huge attention due to associated unsolved problems.

Similarly, this paper defines a new special subset of primes denoted by
$\mathbb{I}$, called the insulated primes, which is defined based on
conditions related to the gaps between consecutive primes. Sequences such as
twin primes, cousin primes, sexy primes, etc. are also based on the gaps
between consecutive primes. Other sequence associated with gaps is the
sequence of least prime of distance $n$ from nearest prime
$(n=1,~{}\text{even})$ called the lonely/isolated primes which is given as 2,
5, 23, 53, 409, 293, 211, 1847, 3137, 2179, 3967, 23719, 16033, 40387, 44417,
and so on [9]. Another interesting sequence is prime islands which is the
least prime whose adjacent primes are exactly $2n$ apart given as 3, 5, 7, 29,
23, 53, 89, 223, 113, 331, 631, 211, 1381, 1129, 1637, 4759, 2579, 3433, and
so on [10].

In order to pursue the said objective, we begin by defining degree of
insulation and then proceed to the insulated primes.

######  Definition 1.1.

Degree of insulation $D(p)$ of a prime $p$ is defined as the maximum value of
the set $X=\\{m:\pi(p-m)=\pi(p+m)-1,m\in\mathbb{N}\\}$, where $\pi(n)$ is the
prime counting function.

######  Definition 1.2.

The $n$-th prime $p_{n}$ is said to be insulated if and only if
$D(p_{n-1})<D(p_{n})$ and $D(p_{n+1})<D(p_{n})$.

The degree of insulation essentially gives the largest bracket around $p$ such
that $p$ is the only prime in that spread, thus insulating $p$ from
neighboring primes. That is why, the set $\mathbb{I}$ is named insulated
primes.

Let us begin with an illustration using the prime triplet $(19,23,29)$.
Consider number $23$ which is solved as

$\displaystyle\pi(23-1)$
$\displaystyle\overset{\mathrm{?}}{=}\pi(23+1)-1\Rightarrow
8\overset{\mathrm{?}}{=}9-1\Rightarrow 8=8$ $\displaystyle\pi(23-2)$
$\displaystyle\overset{\mathrm{?}}{=}\pi(23+2)-1\Rightarrow
8\overset{\mathrm{?}}{=}9-1\Rightarrow 8=8$ $\displaystyle\pi(23-3)$
$\displaystyle\overset{\mathrm{?}}{=}\pi(23+3)-1\Rightarrow
8\overset{\mathrm{?}}{=}9-1\Rightarrow 8=8$ $\displaystyle\pi(23-4)$
$\displaystyle\overset{\mathrm{?}}{=}\pi(23+4)-1\Rightarrow
8\overset{\mathrm{?}}{=}9-1\Rightarrow 8=8$ $\displaystyle\pi(23-5)$
$\displaystyle\overset{\mathrm{?}}{=}\pi(23+5)-1\Rightarrow
7\overset{\mathrm{?}}{=}9-1\Rightarrow 7\neq 8,$

so $D(23)=4$. Now, for $19$ and $29$, we have

$\displaystyle\pi(19-2)\overset{\mathrm{?}}{=}\pi(19+2)-1\Rightarrow
7\overset{\mathrm{?}}{=}8-1\Rightarrow 7=7$

and

$\displaystyle\pi(29-1)\overset{\mathrm{?}}{=}\pi(29+1)-1\Rightarrow
9\overset{\mathrm{?}}{=}10-1\Rightarrow 9=9,$

so $D(19)=2$ and $D(29)=1$, hence $23$ is an insulated prime.

As the determination of insulated primes requires the calculation of $D(p)$,
so the above procedure is coded in python and the resulting line plot of the
values of $D(p)$ vs primes is shown in Figure 1.

Figure 1. Plot of $D(p)$ for primes less than $1000$

The sequence of insulated primes can be understood as the set of local maximas
in the $D(p)$ plot. Thus, the sequence $\mathbb{I}$ is 7, 13, 23, 37, 53, 67,
89, 103, 113, 131, 139, 157, 173, 181, 193, 211, 233, 277, 293, 337, 359, 389,
409, 421, 449, 479, 491, 509, 547, 577, 607, 631, 653, 691, 709, 751, 761,
797, 811, 823, 839, 863, 887, 919, 953, 983, and so on. Figure 2 is the plot
of $n$-th insulated prime $i_{n}$ vs $n$.

Figure 2. Plot of $i_{n}$ versus $n$ for primes less than $1000$

Note that this sequence is neither present on the Online Encyclopedia of
Integer Sequences (OEIS) nor its explored earlier, hence, this paper aims to
investigate it.

##  2\. Analysis of degree of insulation

Certain patterns can be observed from the graphs shown earlier, but these need
to be rigorously proven, which is done below along with other critical
results.

######  Theorem 2.1.

Primes just adjacent to an insulated prime can never be insulated.

###### Proof.

Let $p_{n}$ be insulated prime, then $D(p_{n-1})<D(p_{n})$ and
$D(p_{n+1})<D(p_{n})$ by definition. Now, for $p_{n-1}$ to be insulated prime,
the conditions $D(p_{n-2})<D(p_{n-1})$ and $D(p_{n})<D(p_{n-1})$ must hold.
Clearly, the latter condition is contradictory to condition of $p_{n}$,
therefore, $p_{n-1}$ is not an insulated prime. For $p_{n+1}$ to be an
insulated prime, the conditions $D(p_{n})<D(p_{n+1})$ and
$D(p_{n+2})<D(p_{n+1})$ must hold. But the prior condition is not feasible,
therefore, $p_{n+1}$ is also not an insulated prime. Hence, proved. ∎

######  Theorem 2.2.

If $\alpha\notin X$ then $(\alpha+r)\notin X$ for all $r\geq 0$.

###### Proof.

For some $r\geq 0$, we have $\pi(p+\alpha+r)\geq\pi(p+\alpha)$ and
$\pi(p-\alpha)\geq\pi(p-\alpha-r)$ because $\pi(n)$ is an increasing function.
This implies $\pi(p+\alpha+r)-\pi(p-\alpha-r)\geq\pi(p+\alpha)-\pi(p-\alpha)$.
As $X$ contains all the possible candidates for being $D(p)$ and $\alpha\notin
X$, then $\pi(p+\alpha)-\pi(p-\alpha)>1$ because there exists at least one
prime $p$ such that $p-\alpha\leq p\leq p+\alpha$. Using this gives
$\pi(p+\alpha+r)-\pi(p-\alpha-r)\geq\pi(p+\alpha)-\pi(p-\alpha)>1$ which
implies $\pi(p+\alpha+r)-\pi(p-\alpha-r)\neq 1$. Thus, $\alpha+r$ is also not
a possible candidate for $D(p)$. ∎

######  Corollary 2.3.

For prime $p$, if $\alpha\notin X$ then $D(p)<\alpha$.

###### Proof.

As $(\alpha+r)\notin X$ that is $\alpha+r$ is not a candidate for being $D(p)$
for all $r\geq 0$. Now, if non-zero $D(p)$ exists then $D(p)$ must be less
than $\alpha$. ∎

######  Theorem 2.4.

For a prime $p$, every $m\in X$ obeys

(1)
$\log(p+m)\log(p-m)<m\log\left((p-m)^{c}(p+m)\right)+p\log\left(\frac{(p-m)^{c}}{p+m}\right)$

provided $p\geq 17$, where $c=30\frac{\ln{113}}{113}$.

###### Proof.

From [8], we have

$\frac{x}{\log{x}}<\pi(x)<\frac{cx}{\log{x}}$

which gives

$\pi(p+m)-\pi(p-m)<\frac{c(p+m)}{\log(p+m)}-\frac{p-m}{\log(p-m)}.$

For $m$ to belong to set $X$, the left hand side of the inequality must be
one. On solving the expression and rearranging the terms, we get the desired
result. ∎

######  Theorem 2.5.

For any $N>N_{0}$, there exists an $n\in[N+1,2N+1]$ such that $D(p_{n})\approx
g_{n}$ where $g_{n}=p_{n+1}-p_{n}$.

###### Proof.

By definition of degree of insulation, we also have

(2) $\displaystyle D(p_{n})$
$\displaystyle\approx\min(p_{n+1}-p_{n},p_{n}-p_{n-1})$ (3)
$\displaystyle=(p_{n}-p_{n-1})\times\min\left(1,~{}\frac{p_{n+1}-p_{n}}{p_{n}-p_{n-1}}\right)$

The ratio of consecutive prime gaps appears in the above expression. Using
Theorem 3.8 in [6], for $n\in[N+1,2N+1]$, we have

(4)
$\frac{p_{n+1}-p_{n}}{p_{n}-p_{n-1}}>\frac{c_{0}\log{N}\log_{2}{N}\log_{4}{N}}{(\log_{3}{N})^{2}}$

where $c_{0}$ is a constant and $\log_{t}{N}$ is the t-fold iterated
logarithmic function. As $N$ is sufficiently large, so it turns out the right
side of the inequality is greater than one. Thus, $D(p_{n})\approx
p_{n}-p_{n-1}=g_{n}$. ∎

For a particular prime $p$, the natural procedure for finding $D(p)$ is
inspired from the definition itself, which was illustrated in the previous
section for number $23$. The process began from $m=1$ and kept on checking
until the relation is violated. So, it either requires to compute prime
counting function or to determine the surrounding primes of the given prime.
For extremely large primes, the second approach is highly difficult. However,
the prior approach can be improved in view of the above theorems to reduce the
effort of checking at all the values, as they allow to use bracketing
techniques for faster numerical computation of $D(p)$. Additionally, reader
may refer to Appendix A where a faster algorithm is presented for large $p$.

In addition to the above results, which confirm the connection of $D(p)$ with
gaps between primes, the definition of $D(p)$ also allows us to directly show
the following theorem.

######  Theorem 2.6.

For a prime $p$, we have

  1. 1)

$p-(D(p)+1)$ or $p+(D(p)+1)$ is prime if $D(p)$ is odd, and

  2. 2)

$p-D(p)$ or $p+D(p)$ is prime if $D(p)$ is even.

######  Corollary 2.7.

If $D(p)=1$ then either $p-2$ or $p+2$ is a prime.

Therefore, counting the number of primes with $D(p)=1$ gives the count of
twin-prime pairs. Let $f_{k}$ be the probability of finding a prime $p<1000$
with $D(p)=k$, then Figure 3 is a line plot of $f_{k}$ with $k$ for primes
upto $1000$.

Figure 3. Plot of $f_{k}$ for $1\leq k\leq 11$ with primes $p<1000$

The quantity $f_{k}$ is simply the fraction of primes with $D(p)=k$ over total
primes below $1000$. The graph depicts that probability falls with increasing
$k$. The probability of prime with $D(p)=1$ is highest. Note that $D(p)=1$
corresponds to twin primes. For primes upto $10^{5}$, the pattern is slightly
deviated as evident from Figure 4. It is expected to behave nicely for
extremely set of primes.

Figure 4. Plot of $f_{k}$ for $1\leq k\leq 30$ with primes $p<10^{5}$

If the above trend follows, that is, the number of twin primes are larger than
number of primes with other gaps, then its convenient to show the infinitude
of number of twin-primes. There is huge literature in this direction as well,
but this problem lies out of the scope of this paper.

##  3\. Formula for insulated primes

In addition to the results listed above, one must also be curious about an
approximate/asymptotic formula for the insulated primes. Figure 2 indicated an
almost linear growth, which was further strengthened by evaluating larger
insulated primes.

Figure 5. Comparison of $i_{n}$ plots for primes less than $10^{5}$

Using MATLAB command cftool for the Curve fitting toolbox, a variety of curves
(with different settings) were tested. It was observed that the equation
$y=19.18n^{1.093}$ is an extremely good fit as indicated in Figure 5.

Figure 6. Comparison of $i_{n}$ plots for primes less than $10^{6}$

The equation performs even better when tested for primes upto one million as
shown in Figure 6. It has an R-square value of unity which is extremely good.
This allows to conclude that $i_{n}\sim 19.18n^{1.093}$ is heuristically an
accurate fit. However, this result needs to be rigorously proven, but this
analysis is sufficient to convince that insulated primes are definitely well-
behaved in comparison to primes or other prime subsets.

##  4\. Conclusion and Future scope

This paper defines and explores the properties of a new sequence called the
insulated primes. The sequence is 7, 13, 23, 37, 53, 67, 89, 103, 113, 131,
139, 157, 173, 181, 193, 211, 233, 277, 293, and so on. The insulated primes
are defined using the concept of degree of insulation, which is also shown to
have deep connection with gaps between consecutive primes. A detailed
mathematical analysis is conducted which unravels several characteristics.
Based on this analysis, a faster algorithm for evaluation of $D(p)$ was
suggested as well as a quick discussion on Twin-Prime conjecture was also
conducted. Finally, heuristics show that $n$-th insulated prime $i_{n}$ obeys
a power law. A strong form of this result is the conjecture that $i_{n}$ is
varies almost linearly for $n\to\infty$. The authors encourage inquisitive
readers to ponder upon the ideas presented in the paper.

An extension of the insulated primes is the highly insulated primes. The set
of highly insulated primes $\mathbb{I}_{H}\subset\mathbb{I}\subset\mathbb{P}$
can be defined by treating insulation as an operation on the set $\mathbb{I}$.
This is done by applying the definition of insulation on $i_{n}$, that is,
$i_{n}$ is highly insulated prime if $D(i_{n-1})<D(i_{n})$ and
$D(i_{n+1})<D(i_{n})$. This is demonstrated by investigating the triplet of
insulated primes $(i_{n-1},i_{n},i_{n+1})=(13,23,37)$. As $D(13)=2$, $D(23)=4$
and $D(37)=3$, so $23$ is also an highly insulated prime. Similarly, other
highly insulated primes are 23, 53, 89, 211, 293, and so on. The interested
readers may investigate this sequence.

## References

  * [1] J. R. Chen, _On the representation of a large even integer as the sum of a prime and the product of at most two primes_ , Kexue Tongbao 17 (1966), 385–386.
  * [2] K. Goldberg, _A table of wilson quotients and the third wilson prime_ , J. London Math. Soc. 28 (1953), 252–256.
  * [3] R. K. Guy, _Unsolved problems in number theory_ , Springer Verlag, New York, 2004.
  * [4] D. Hawkins and W. E. Briggs, _The lucky number theorem_ , Mathematics Magazine 31 (1957), 81–84.
  * [5] James Maynard, _Sums of two squares in short intervals_ , Analytic Number Theory (C. Pomerance and M. Rassias, eds.), Springer, 2015, pp. 253–273.
  * [6] János Pintz, _On the ratio of consecutive gaps between primes_ , Analytic number theory (C. Pomerance and M. Rassias, eds.), Springer, 2015, pp. 285–304.
  * [7] R. M. Robinson, _Mersenne and fermat numbers_ , Proceedings of the American Mathematical Society 5 (1954), 842–846.
  * [8] J. B. Rosser and L. Schoenfeld, _Approximate formulas for some functions of prime numbers_ , Illinois Journal of Mathematics 6 (1962), no. 1, 64–94.
  * [9] N. J. A. Sloane, _A023188 in: On-line encyclopedia of integer sequences_ , https://oeis.org/A023188.
  * [10] by same author, _A046931 in: On-line encyclopedia of integer sequences_ , https://oeis.org/A046931.
  * [11] J. Sondow, _Ramanujan primes and bertrand’s postulate_ , Amer. Math. Monthly 116 (2009), 630–635.

##  Appendix A Modified algorithm for $D(p)$ when $p$ is large

For large $X$ and $y\in(0,X]$, the prime number theorem shows that on average
for $x\in[X,2X]$, we have

$\pi(x+y)-\pi(x)\approx\frac{y}{\log{x}}.$

Substitute $x+y=p+m$ and $x=p-m$ then

$\pi(p+m)-\pi(p-m)\approx\frac{2m}{\log(p-m)}$

for $2m\in(0,X]$ and $p\in[X+m,2X+m]$.

For $D(p)$, the left hand side must be unity, therefore we get
$2m\approx\log(p-m)$. Let $\operatorname{W}$(.) is Lambert’s W function then
$m$ can be explicitly written as $m=p-0.5\operatorname{W}(2e^{2p})$. For large
primes $p$, evaluation of $e^{2p}$ is an tough task, so using the asymptotic
relation for Lambert’s W function, we get $m\sim
p-0.5(\log{2e^{2p}}-\log{\log{2e^{2p}}})$ which simplifies to give
$m\sim\frac{1}{2}\log\left(\frac{2p}{\log{2}}+1\right)$.

The above step provides a better way to determine $m$ rather than aimlessly
beginning from $1$ and linearly searching as it was illustrated for prime
$23$. However, the derivation of the above step imposes certain conditions
which can be relaxed by not treating the obtained $m$ as the final answer.
This is done by considering $m$ as just a better candidate to be $D(p)$ which
is then substituted in $\pi(p+m)-\pi(p-m)-1$ to cross-check. If its value is
zero, then assign $m_{0}=m$ and $m_{1}=p$, else set $m_{0}=1$ and $m_{1}=m$.
Now, apply bisection method to search $D(p)$ in the interval $[m_{0},m_{1}]$.
This procedure immensely reduces the number of times one needs to evaluate
$\pi(x)$. An additional note here is that using sharper results on gaps
between primes, one can choose a better $m_{1}$ than just assigning to $p$ in
the first case.


05A05, 05A15, 06A07, 68R05, 68R15, 68W32 inversion sequence, permutation
pattern, sorting algorithm, pop stack, generating tree

# Sorting inversion sequences

Toufik Mansour
Department of Mathematics
University of Haifa
3498838 Haifa, Israel
Howard Skogman
Excellus BlueCross BlueShield
Rochester, New York
Rebecca Smith
Department of Mathematics
SUNY Brockport
Brockport, New York

###### Abstract

We consider the avoidance of patterns in inversion sequences that relate
sorting via sorting machines including data structures such as pop stacks and
stacks. Such machines have been studied under a variety of additional
constraints and generalizations, some of which we apply here. We give the
classification of several classes of sortable inversion sequences in terms of
pattern avoidance. We are able to provide an exact enumeration of some of the
sortable classes in question using both classical approaches and a more recent
strategy utilizing generating trees.

## 1\. Introduction

An _inversion_ in a permutation $\pi=\pi_{1}\pi_{2}\pi_{3}\cdots\pi_{n}$ is a
pair of entries $\pi_{i},\pi_{j}$ where $i<j$, but $\pi_{i}>\pi_{j}$. An
_inversion sequence_ of length $n$ is a word $e=e_{0}\dotsb e_{n}$ which
satisfies for each $i\in[n]=\\{0,1,\ldots,n\\}$ the inequalities $0\leq
e_{i}\leq i$. These sequences correspond to permutations via a variant of the
Lehmer code [17, 18] by mapping each entry $\pi_{j}$ of the permutation $\pi$
to $e_{j}$ where $e_{j}$ is the number of inversions $\pi_{j}$ is a part in
$\pi$ as the second, smaller entry of the pair. The set of inversion sequences
of length $n$ is denoted ${\mathbf{I}}_{n}$.

The study of pattern avoidance in inversion sequences began with work by
Corteel, Martinez, Savage, and Weselcouch [8] and Shattuck and the first
author [21]. Since then, extensive work has been done in this area, including
recent work by Kotsireas, Yıldırım, and the first author [16] that introduces
an algorithmic technique involving generating trees to determine enumeration
of many pattern classes of inversion sequences (for example, see [6, 19, 20,
30] and the references therein). We utilize this algorithm ourselves in
Section 4 to obtain a generating function for the number of inversion
sequences sortable by two particular machines.

However, there remain many open problems when it comes to characterizing and
enumerating the inversion sequences that avoid a class of consisting of a
small number of relatively short (length less than five) patterns. Our
interest is in the characterization and enumeration of inversion sequences
sortable by stacks and pop stacks. We also study the characterization of
inversion sequences sortable by data structures obtained by generalizing or
further restricting the pop stacks.

A stack is a last-in, first-out sorting device with push and pop operations.
Knuth [15] showed the permutation $\pi$ can be sorted (that is, by applying
push and pop operations to the sequence $\pi_{1},\dots,\pi_{n}$ one can output
the identity $1,\dots,n$) exactly if $\pi$ avoids the permutation $231$.

######  Definition 1.1.

A permutation $\pi=\pi_{1}\pi_{2}\dots\pi_{n}\in S_{n}$ is said to _contain_ a
permutation $\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{k}$ if there exist
indices $1\leq\alpha_{1}<\alpha_{2}<\ldots<\alpha_{k}\leq n$ such that
$\pi_{\alpha_{i}}<\pi_{\alpha_{j}}$ if and only if $\sigma_{i}<\sigma_{j}$.
Otherwise, we say $\pi$ _avoids_ $\sigma$.

These definitions of _containment_ and _avoidance_ have been naturally
extended to words (and specifically inversion sequences) with the added
allowance of entries being equal to one another.

###### Example 1.2.

The permutation $\pi=241563$ contains $312$ since the $4,1,3$ appear in the
same relative order as $3,1,2$. However, $\pi$ avoids $321$ since there is no
decreasing subsequence of length three in $\pi$.

Similarly, the inversion sequence $\tau=0021104$ contains $1002$ from
$2,1,1,4$, but avoids $201$.

Describing the permutations that are sortable by these machines is a point of
interest in the field. To this end, it often possible to describe the sortable
machine in terms of its _basis_.

######  Definition 1.3.

A _permutation class_ is a downset of permutations under the containment
order. Every permutation class can be specified by the set of minimal
permutations which are _not_ in the class called its _basis_. For a set $B$ of
permutations, we denote by $\operatorname{Av}(B)$ the class of permutations
which do not contain any element of $B$.

As mentioned above, the stack-sortable permutations are the class
$\operatorname{Av}(231)$.

A restricted version of a stack that has received a fair amount of attention
is a pop stack, first introduced by Avis and Newborn [4]. A pop stack has the
same push and pop operations as a stack, but whenever a pop operation occurs,
every entry in the pop stack is popped immediately. One foundational result is
that the permutations that can be sorted by a single pop stack are exactly
those that avoid $231$ and $312$. Some later works involving pop stacks
include [1, 3, 7, 9, 12, 14, 25, 28].

Atkinson [2] explored a variation of a stack called an $(r,s)$-stack which
allowed for an extension of the traditional push and pop operations.
Specifically, the first index of an $(r,s)$-stack allowed for one to push an
entry not only to the top of the stack, but to any of the top $r$ spots.
Similarly, the second index expanded the options of the pop operation to allow
one to pop any of the top $s$ entries from the stack. Thus a $(1,1)$-stack is
simply a traditional stack. Atkinson was able to characterize these
permutations when one of $r,s$ was fixed at $1$ and when $r=s=2$. Natural
variations on stacks arise when studying inversion sequences that are similar
in flavor to these generalized stacks.

Murray [10] considered restricting the depth of a stack, that is the maximum
number of entries allowed in a stack at any given time, in the context of
generating permutations with two stacks in series. Murray later continued this
study with Lee and Rechnitzer [13] and then extended to sorting and pop stack
sorting with Goh [11, 12]. While this work focused on a permutation sorting
(or generating) machine consisting of two stacks in series, we will consider a
similar restriction for a single stack or pop stack when sorting inversion
sequences.

## 2\. Stack sorting inversion sequences

We give the standard optimal stack sorting algorithm in Algorithm 1.

Algorithm 1 Stack Sorting Algorithm

$p=p_{1}p_{2}\cdots p_{n}$ is a permutation of length $[n]$.

$S$ is a stack.

$O$ is an empty array.

$i=1$

procedure StackSort($p,n$)

while $i<n+1$ do

if $S$ is empty then

push $p_{i}$ to the top of $S$

$i=i+1$

else if $p_{i}<$ top element of $S$ then

push $p_{i}$ to the top of $S$

$i=i+1$

else

pop the top entry of $S$ to the end of $O$

end if

end while

return $O$

end procedure

For a word $w$ to be stack sortable, $w$ must avoid $120$, the same as
avoiding $231$ to be able to sort permutation. The repetition allowed in words
does not change this requirement from being both necessary and sufficient and
so the proof does not change either. It is included below for completeness.

######  Proposition 2.1.

The words that are stack sortable are exactly the words that avoid $120$.

###### Proof.

The first $2$ of a $120$ pattern forces the smaller entry $1$ to the output
before the $0$ even enters the stack which creates an inversion with the
$1,0$. Hence words containing a $120$ pattern are not stack sortable.

Next consider a word $w$ that is not stack sortable. The output $S(w)$ must
contain an inversion, say an entry $b>a$ that appears before $a$. For $a$ to
not have exited the stack before $b$, we know $a$ appears after $b$ in $w$.
Further, for $b$ to have been forced out of the stack before $a$ entered,
there must have been a larger entry $c$ that appeared after $b$, but before
$a$ to force $b$ out before $a$ could enter the stack. Thus $w$ contains a
$120$ pattern $bca$. ∎

As inversion sequences are words with added restrictions, Proposition 2.1 also
gives us a basis for the stack sortable inversion sequences.

######  Corollary 2.2.

The inversion sequences that are stack sortable are exactly those that avoid
$120$.

The enumeration of these sortable inversion sequences has been studied, but
thus far remains open. See [21, Section 4] and [8] for initial study and
further work on avoiding $120$ in [30].

## 3\. Pop stack sorting inversion sequences

The optimal pop stack sorting algorithm is mostly the same procedure as that
for stacks, but when a pop stack is popped, all entries must exit the stack as
described in Algorithm 2.

Algorithm 2 Pop Stack Sorting Algorithm

$p=p_{1}p_{2}\cdots p_{n}$ is a permutation of length $[n]$.

$PS$ is a pop stack.

$O$ is an empty array.

$i=1$

procedure PopStackSort($p,n$)

while $i<n+1$ do

if $PS$ is empty then

push $p_{i}$ to the top of $PS$

$i=i+1$

else if $p_{i}<$ top element of $PS$ then

push $p_{i}$ to the top of $PS$

$i=i+1$

else

while $PS$ is nonempty do

pop the top entry of $PS$ to the end of $O$

end while

end if

end while

return $O$

end procedure

Note that $120,201$ are the patterns whose avoidance completely determines the
pop stack sortability of a permutation. However, due to the repetition allowed
in words, a copy of a larger element already in the stack can force the entire
stack to be popped while there is still a copy of a smaller entry appearing
later in the permutation.

######  Theorem 3.1.

The words that are pop stack sortable are exactly the words that avoid
$120,201,$ and $1010$.

###### Proof.

One can check that each of $120,201,$ and $1010$ are not pop stack sortable.
As such, a word that contains any of these patterns cannot be sorted by a pop
stack.

Conversely, suppose $w$ is not pop stack sortable. Consider what happens to
force an entry to the output that is larger than an entry that appears later
in the permutation. Using Algorithm 2, we had an entry $d$ that appears
(immediately) after a smaller entry $b$ which forces $b$ out before $d$ can
enter. If $b$ is the larger entry forced out, then there exists a smaller
entry $a$ after $d$ and $bda$ form a $120$ pattern. If not, then there exists
an entry $c>b$ that entered the pop stack before $b$ and there is an entry $a$
that appears after $d$ such that $c>a\geq b$. Note if $a>b$, then $cba$ form a
$201$ pattern. Otherwise, if $a=b$, possible patterns $cbda$ are
$1010,2010,1020$, but only $1010$ does not contain one of the smaller
forbidden patterns $120,201$. ∎

As inversion sequences are words with added restrictions, Theorem 3.1 also
gives us a basis for the pop stack sortable inversion sequences.

######  Corollary 3.2.

The inversion sequences that are pop stack sortable are exactly those that
avoid $120,201,$ and $1010$.

The pop stack sortable permutations are also known as _layered_ permutations
which are permutations of the form $\pi=\sigma_{1}\sigma_{2}\cdots\sigma_{k}$
where each _layer_ $\sigma_{i}$ is a maximal length contiguous decreasing
sequence such that all of the entries of $\sigma_{i}$ are less than all of the
entries of $\sigma_{i+1}$. For example, the permutation $\pi=543216987$ is a
layered permutation with layers $\sigma_{1}=54321,\sigma_{2}=6,\sigma_{3}=987$
as shown in Figure 1.

Figure 1: The layered permutation $\pi=543216987$

We can define layered words similarly as follows.

######  Definition 3.3.

A _layered_ word $w$ is such that $w=\tau_{1}\tau_{2}\cdots\tau_{k}$ where
each $\tau_{i}$ is

  1. 1.

maximal in length,

  2. 2.

weakly decreasing, and

  3. 3.

such that the last (weakly smallest) entry of $\tau_{i+1}$ is at least as
large as the first (weakly largest) entry of $\tau_{i}$ for all $i$.

For example, the word $w=211033275$ is a layered word with layers
$2110,332,75$ shown in Figure 2.

Figure 2: The layered word $\pi=211033275$

It can then be seen that these layered words are exactly the pop stack
sortable words.

######  Proposition 3.4.

Layered words are exactly the words that avoid $120,201,1010$.

###### Proof.

Suppose $w$ is layered. Then $w$ cannot contain $120$ because if not, the
layer containing the $0$ of the pattern must appear after the layer containing
the $1$ which violates the third condition. The same argument can be made for
the $1$ of the $201$ pattern appearing in a later consecutive decreasing
pattern than that of the $2$ and once again for the second $0$ of the $1010$
pattern appearing in a later consecutive decreasing pattern than that of the
first $1$.

Now suppose $w$ avoids $120,201,1010$. Then $w$ is pop stack sortable.
Consider the output from sorting $w$ broken into segments based on the pops.
Reversing those segments reverts the word back to $w$. Further, by the
algorithm, these breaks occur at exactly the strict ascents in $w$. The
segments are then weakly decreasing and such that the smallest entry of any
segment is at least as large as the largest entry of the previous segment for
$w$ to be sortable and also maximal in length. Hence $w$ is layered. ∎

When restricting to inversion sequences, we are able to describe the
generating tree which we describe in subsection 4.2. There are also some
partial results we can obtain combinatorially based on the number of layers
(which is also the number of pops needed to sort the sequence). Recall the
Eulerian numbers $E(n,k)$ count the number of permutations of length $n$ with
$k-1$ descents.

######  Proposition 3.5.

The number of pop stack sortable inversion sequences of length $n$ with
$k=1,2$ layers are counted by $E(n,k)$.

###### Proof.

In fact, the pop sortable inversion sequences of length $n$ with $k=1,2$
layers correspond exactly to the permutations of length $n$ with $k$ descents
by the variant of Lehmer code used to create inversion sequences. In the
trivial case of $k=1$, a permutation of length $n$ with $k-1=0$ descents is
the identity permutation which is the only permutation of length $n$ to have
an inversion sequence with one layer, namely the inversion sequence consisting
of all $0$s.

Now consider the case when $k=2$. A permutation $\pi$ with exactly one
descent, say at index $i$, will have an inversion sequence that begins with
$i$ 0s which will be the first layer. Since the permutation $\pi$ is such that
$\pi_{i+1}$ is the smaller entry in an inversion with at least $\pi_{i}$, the
corresponding inversion sequence now has a positive entry in position $i+1$.
As the remainder of the entries of $\pi$ are all in increasing order, each
subsequent entry of $\pi$ can be the smaller entry of at most as many
inversions as the previous entry. Thus, the rest of the inversion sequence is
in weakly decreasing order meaning that the entries from position $i+1$ to
position $n$ form the second and final layer. ∎

As not all inversion sequences are pop stack sortable, this correspondence can
clearly not continue indefinitely. Indeed, a permutation with even $k-1=2$
descents is not guaranteed a corresponding pop stack sortable inversion
sequence. For example, the permutation $\pi=3214$ has the inversion sequence
$e(\pi)=0120$ which is not sortable by a pop stack.

At the other extreme, only one inversion sequence of any given length $n\geq
1$ can have $n$ layers, namely the increasing sequence $012\ldots(n-1)$.
Reducing the number of layers by one to $n-1$ layers gives a set of inversion
sequences enumerated by the Tetrahedral numbers, sequence number A000292 in
OEIS [27].

######  Proposition 3.6.

The number of pop stack sortable inversion sequences of length $n\geq 1$ with
$n-1$ layers is $\binom{n+1}{3}$.

###### Proof.

A pop stack sortable inversion sequence of length $n\geq 1$ with $n-1$ layers
will have exactly one entry $e_{i}$ as the second entry of a layer where
$i\in\\{2,3,4,\ldots,n\\}$. It must be the case that $e_{m}=m-1$ for all $m<i$
for those entries to have all started new layers. This means
$e_{i}=e_{i-1}=i-2$ or $e_{i}=e_{i-2}=i-3$. Further, we know
$e_{i},e_{i+1},e_{i+2},\ldots,e_{n}$ are in increasing order as they are all
in different layers.

In the case that $e_{i}=i-2$, since we must have $i-1\leq
e_{i+1}<e_{i+2}<\cdots<e_{n}\leq n-1$, we can select up to one of these later
entries to be two greater than the previous entry. Consider positions
$\\{2,3,4,\ldots,n,n+1\\}$ where we pick two positions; the first to be the
position of the second entry in the layer of length two and the second to be
the position of the entry that is two more (as opposed to one more) than the
previous. In the case that $n+1$ is one of the selected options, then we do
not have any entry that is two more than the one before it. Hence there are
$\binom{n}{2}$ such inversion sequences.

Otherwise, $e_{i}=i-3$ and so $i\geq 3$. Now because $i-2\leq
e_{i+1}<e_{i+2}<\cdots<e_{n}\leq n-1$, up to two of these later entries could
be two greater than the previous entry or one of these later entries could be
three greater than the previous entry. For the cases when no entry is three
more than the previous entry, we have
$\binom{n-2}{1}+\binom{n-2}{2}+\binom{n-2}{3}$ ways to select the second entry
of the length two layer and the entries that are two greater than the entry
they follow. In the case where we have one entry that is three more than the
previous entry, there are $\binom{n-2}{2}$ ways to select this entry and the
entry that was the second in the longest layer. This gives us a total of
$\binom{n-2}{1}+2\binom{n-2}{2}+\binom{n-2}{3}=\binom{n}{3}$ via a
generalization of Pascal’s Identity.

By another application of Pascal’s Identity, there are
$\binom{n}{2}+\binom{n}{3}=\binom{n+1}{3}$ pop stack sortable inversion
sequences of length $n\geq 1$ with $n-1$ layers. ∎

One last special case is when the sortable inversion sequence contains only
$0$s and $1$s and thus only needs to avoid $1010$, thereby having at most
three layers. The number of such sequences is the number of compositions of
$n$ into at most four parts because we must begin with a $0$ and can only
alternate values at most three times after that. These numbers (with an offset
of one) are better known as the “Cake numbers" [29], sequence number A000125
in OEIS [27], which count the maximum number of slices of a cylindrical cake
one can have after making $n-1$ planar cuts perpendicular to the top circular
surface.

######  Proposition 3.7.

The number of pop sortable inversion sequences of length $n$ only containing
$0,1$ is $(n-1)$st Cake number:
$\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\binom{n-1}{3}$.

###  3.1 Restricting pop stack depth

When extending the notion of the depth of a stack to words, we could continue
to use the definition in terms of the number of elements allowed in the stack
as introduced by Murray [10]. However, given the repetition that distinguishes
words from permutations, we will instead use the following definition that is
also consistent with the original definition applied to permutations.

######  Definition 3.8.

The _depth_ of a stack (or pop stack) will be the number of entries with
distinct values allowed in the stack (or pop stack) at any stage.

For example, a stack of depth three under this definition would still only
allow three entries of a permutation to be in the stack at one time. However,
this same restricted stack could allow arbitrarily many entries of a word in
the stack, provided that no more than three distinct letters were represented
at any time. We begin by considering pop stacks of limited depth.

######  Proposition 3.9.

A word is sortable by a pop stack of depth $k$ if and only if avoids
$120,201,1010$ and also $k(k-1)\cdots 10$.

###### Proof.

As before any word $w$ must avoid $120,201,1010$ to be pop stack sortable.
Additionally, a decreasing sequence that is too long to fit in a limited depth
pop stack is also not sortable.

Conversely, if $w$ is not pop stack sortable by a pop stack of depth $k$ and
avoids $120,201,1010$, then the problem is a result of the limitation of the
pop stack’s capacity. Hence $w$ must contain a $k(k-1)\cdots 10$ pattern. ∎

######  Corollary 3.10.

An inversion sequence is sortable by a pop stack of depth $k$ if and only if
avoids $120,201,1010$ and also $k(k-1)\cdots 10$.

In the case of depth one, the number of sortable inversion sequences is the
number of weakly increasing inversion sequences which are known to be
enumerated by the Catalan numbers due to Martinez and Savage [24]. The proof
shows these inversion sequences to correspond to the $213$ avoiding
permutations enumerated by Simion and Schmidt [26].

######  Theorem 3.11.

(Martinez and Savage) The number of inversion sequences of length $n$ which
avoid $10$ and thus are sortable by a pop stack of depth $1$ is the $n$th
Catalan number $C_{n}=\frac{\binom{2n}{n}}{n+1}$.

For a pop stack of depth two, the sortable inversion sequences would need to
avoid $120,201,210,1010$. The first few terms of the enumeration sequence are:
$1,1,2,6,23,100,471,2349$. We can define the generating tree for these
inversion sequences (using the algorithm introduced in [16]) as having a root
$a_{1}$ and satisfying the following rules

$\displaystyle a_{m}$ $\displaystyle\rightsquigarrow
a_{m+1},b_{m,1},\ldots,b_{m,m},\quad m\geq 1,$ $\displaystyle b_{m,j}$
$\displaystyle\rightsquigarrow(c_{m+1-j})^{j},b_{m+1,j},b_{m+1-j,1},\ldots,b_{m+1-j,m+1-j},\quad
1\leq j\leq m,$ $\displaystyle c_{m}$ $\displaystyle\rightsquigarrow
c_{m+1},a_{m+2},b_{m+1,1},\ldots,b_{m+1,m+1},\quad m\geq 1,$

where $a_{m}=0^{m}$, $b_{m,j}=0^{m}j$ and $c_{m}=0^{m}10$. However, it is hard
to get an explicit formula by translating this generating tree to system of
equations and is even more difficult for larger values of $k$.

Another approach is to count the inversion sequences recursively directly, but
this too is not as nice as we would hope. One recursive characterization is
given below.

A weakly decreasing word of length $n$ has depth $k$ if it has the form
$\\{a_{1},...a_{1},a_{2},...a_{2},...,a_{k+1},...a_{k+1}\\}$ where for each
$i$, $a_{i}>a_{i+1}\geq 0$ (so there are $k$ descents). Let $WD_{k}(n,a)$ be
the set of all such words whose first value is $a$ and whose depth is at most
$k$.

######  Lemma 3.12.

For all $n,k\in\mathbb{Z}^{+}$, with $k<n$

$|WD_{k}(n,a)|=1+\sum_{j=1}^{k}\binom{n-1}{j}\binom{a-1}{j-1}$ (1)

Note we assume $\binom{n}{k}=0$ if $k>n$. The result follows from choosing $j$
locations for a descent, then $j-1$ values for the weakly decreasing sequence,
and one for the sequence with no descents.

We say a word is a layered weakly decreasing word of depth at most $k$ and
length $n$ if it can be written as a sequence of subwords
$\\{w_{1},w_{2},...\\}$ where each $w_{i}\in WD_{k}(m_{i},a_{i})$ with
$\sum_{i}m_{i}=n$, and for each $i$, $a_{i}\geq 0$, and $min(w_{i+1})\geq
max(w_{i})$ (i.e. the largest (first) value of each word is bounded by the
smallest value of the succeeding word). Further, we consider the words of this
type which are also inversion sequences, i.e.
$max(w_{i})\leq\sum_{j=1}^{i-1}m_{j}$. Let $LDI_{k}(n)$ be the set of all such
layered depth at most $k$ inversion sequences of length $n$.

######  Lemma 3.13.

The set of sortable inversion sequences by a depth $k$ pop stack is exactly
$LDI_{k}(n)$.

The proof is simply to note that when the stack is popped, there are at most
$k$ distinct values, and they must be less than any later sequence values.

Given an element $\\{w_{1},w_{2},...w_{t}\\}\in LDI_{k}(n)$ as above with each
value of $w_{i+1}$ bounded below by the largest value in $w_{i}$, subtracting
$a_{i}$ from every value in $w_{i+1}$ yields an element of
$WD_{k}(m_{i},a_{i+1}-a_{i})$.

As a result we get the following formula.

######  Proposition 3.14.

For all $n,k>0$,

$|LDI_{k}(n)|=\sum_{m_{1}+m_{2}+...m_{t}=n,m_{i}\geq
0}\sum_{a,1,a_{2},...a_{t}}^{*}|WD(m_{i},a_{i})|,$ (2)

where the $\sum^{*}$ means to only sum on values of $\displaystyle{0\leq
a_{j}\leq\bigg{(}\sum_{h=1}^{j-1}m_{h}-a_{h}\bigg{)}-1}$.

Since the first word in an element of $LDI_{k}(n)$ must be a string of zeros,
we let $LDI_{k}(n,m_{1})$ denote the elements of $LDI_{k}(n)$ that begin with
$m_{1}$ zeros followed by a non-zero value. Further, let
$LDI_{k}(n,m_{1},a_{2})$ is the subset of these layered decreasing inversion
sequences which begin with $m_{1}$ zeros, and first non-zero value $a_{2}$
(and $a_{2}\leq m_{1}$). We now decompose our sequence of words as
$\\{\overline{0}_{m_{1}},w_{2},\hat{w}\\}$ where
$\hat{w}=\\{w_{3},...w_{t}\\}$. Now $w_{2}\in WD_{k}(m_{2},a_{2})$ for some
$0\leq m_{2}\leq n-m_{1}$, $a_{2}>0$. If we subtract $a_{2}$ from all the
elements in $\hat{w}$ the result is in
$LDI(n-m_{2}-m_{1},m_{1}+m_{2}-a_{2},a)$ for some $a$ with $a\leq
m_{1}+m_{2}-a_{2}$. Note that the number of starting zeros guarantees that
adding $a_{2}$ to all of these entries will still yield an element of
$LDI_{k}(n)$.

Hence we get the formula,

######  Proposition 3.15.

For all $n,k,m_{1}\in\mathbb{Z}^{+}$ with $m_{1}<n$,

$LDI_{k}(n,m_{1})=\sum_{m_{2}=0}^{n-m_{1}}\sum_{a_{2}\leq
m_{1}}WD_{k}(m_{2},a_{2})\sum_{a\leq
m_{1}+m_{2}-a_{2}}LDI_{k}(n-m_{1}-m_{2},m_{1}+m_{2}-a_{2},a).$ (3)

Both of the above formulas are rather difficult to use for computation.
However they are presented to give some insight into directly enumerating
these inversion sequences.

For completeness, we give some characterizations of words sortable by stacks
of depth $k$.

######  Proposition 3.16.

A word is sortable by a stack of depth $k$ if and only if avoids $120$ and
also $k(k-1)\cdots 10$.

######  Corollary 3.17.

The number of words of length $n$ on an alphabet $[k]$ sortable by a stack of
depth $1$, i.e. avoid $10$ is $\binom{n+k-1}{k-1}$.

###### Proof.

These weakly increasing words can be thought of as weak compositions of $n$
into $k$ parts where each part represents the next largest letter. ∎

The depth 2 stack sortable words are enumerated by Burstein [5] in the context
of avoiding $120,210$.

######  Theorem 3.18.

(Burstein) The number of words of length $n$ on an alphabet $[k]$ avoiding
$120,210$ and thus sortable by a stack of depth $2$ is given by

$\frac{1-(-1)^{k}}{2}+2^{n}\sum_{i=0}^{\lfloor\frac{k-2}{2}\rfloor}\binom{n+k-3-2i}{n-1}.$

Finally, we note Kotsireas, Yıldırım, and the first author [16] give a
functional equation for the inversion sequences of length $n$ avoiding
$120,210$ and thereby sortable by a stack of depth $2$.

###  3.2 Generalizing pop stacks

We can also expand the ability of our sorting machine using a similarly
defined version of Atkinson’s [2] extension of push and pop operations.
Specifically, we will define a $(r,1)$-pop stack that is also modified to take
into account the repetition of letters in inversion sequences (and more
generally words). In Atkinson’s work, an $(r,1)$-stack would have allowed for
push operations to push entries into the stack in any of the top $r$
positions. We can again naturally redefine generalized stacks for words in a
way that is consistent with Atkinson’s work on permutations.

######  Definition 3.19.

Let an $(r,1)$-stack allow the push operation to push an entry to any of the
top $r$ “value positions” in the stack where consecutive entries of the same
value in the stack are grouped together. Note that the same definition could
be extended to the broader notion of an $(r,s)$ stack where we allow the pop
operation to be defined in terms of these same value positions.

###### Example 3.20.

Suppose a $(3,1)$-stack contained the values $0,0,0,3,3,4,6,6$ as shown in
Figure 3. Then we could push a new entry $w_{i}$ to top, between the 0 and 3,
or between 3 and 4 as indicated by the $\square$s.

$w_{i}$$6$$6$$4$$\square$$3$$3$$\square$$0$$0$$0$$\square$

Figure 3: A $(3,1)$-stack

Varying the restrictions of depth and generalizations of the push operation as
described above, we get a family of stacks and a family of pop stacks. There
are some variations that no longer give us new machines though. Specifically,
if our stack or pop stack has limited depth, having the option to push entries
to (or pop entries from) spaces that do not exist does add any sorting power.

######  Proposition 3.21.

For a $(r,1)$-stack or $(r,1)$-pop stack of depth $d$, if $r>d$, the machine
sorts the same words as if $r=d$.

As such, we will restrict $r\leq d$.

We will first consider the case where $r=d=2$.

The $(2,1)$-pop stack of depth two has the nice characteristic where it sorts
words (and permutations) that avoid three patterns of length three.

######  Theorem 3.22.

A $(2,1)$-pop stack of depth two sorts exactly the words that avoid
$120,201,210$.

###### Proof.

Because the $(2,1)$-pop-stack we are using only has depth two, any pattern of
length three with three distinct values will have at least the first entry
popped out before the third entry can enter. For all of $120,201,210$, this
means the larger first entry is popped out before the smaller last entry
enters the stack. Thus no word containing $120,201,210$ is sortable by a
$(2,1)$-pop stack of depth two.

Now consider a word $w$ that cannot be sorted by a $(2,1)$-pop stack of depth
two. If a larger entry was forced out before a smaller entry could be pushed
into the stack due to the limited depth, there are two ways this could have
happened. One is that two distinct larger entries appeared before a smaller
entry, that is $w$ contains a $120$ or $210$ pattern. Otherwise, we have a
large entry that is below a small entry in the pop stack, and our third entry
waiting to enter is between the small and large entry in value. Because of the
$(2,1)$ generalization, in theory, the first two entries could appear in
either order in $w$ to form either a $021$ or a $201$ pattern. However, in the
case of a $021$ pattern, the $0$ entry could be popped out before pushing the
$2$ into the pop stack, so only the $201$ pattern presents a problem. ∎

Note: Algorithm 3 gives a procedure for sorting with a $(2,1)$-pop stack of
depth $2$. Because there are only two possible values in $PS2$, it would be
equivalent to simply push $w_{i}$ to the bottom of $PS2$ if it matched the
larger value in the $(2,1)$-pop stack of depth $2$ rather than keep track of
how many smaller entries there are. However, we present the algorithm in this
form for the option of generalization if desired.

Algorithm 3 $(2,1)$-Pop Stack of Depth $2$ Sorting Algorithm

$w=w_{1}w_{2}\cdots w_{n}$ is a word of length $[n]$.

$PS2$ is a $(2,1)$-Pop Stack of Depth $2$ .

$O$ is an empty array.

$i=1$ is the index of the next entry in the input

$j=0$ is the counter for the number of copies of the smallest value in the
$(2,1)$-Pop Stack of Depth $2$

procedure PopStackSort2($w,n$)

while $i<n+1$ do

if $PS2$ is empty then

push $w_{i}$ to the top of $PS2$

$i=i+1$

$j=1$

else if $w_{i}=$ the top/smallest element(s) in $PS2$ then

push $w_{i}$ to the top of $PS2$

$i=i+1$

$j=j+1$

else if $w_{i}=$ the larger element(s) in $PS2$ then

push $w_{i}$ to the $(j+1)$st position of $PS2$

$i=i+1$

else if there are already two distinct values in $PS2$ then

while $PS2$ is nonempty do

pop the top entry of $PS2$ to the end of $O$

end while

else if $p_{i}<$ top element of $PS2$ then

push $p_{i}$ to the top of $PS2$

$i=i+1$

$j=1$

else

while $PS2$ is nonempty do

pop the top entry of $PS2$ to the end of $O$

end while

end if

end while

return $O$

end procedure

######  Theorem 3.23.

Algorithm 3 is optimal for sorting words with an $(r,1)$-pop stack of depth
$2$.

###### Proof.

By way of contradiction let $w$ be a sortable word that is not sorted by our
algorithm on a $(2,1)$-pop stack of depth 2. Specifically, $S(w)$ must contain
a descent, say $w_{j}w_{k}$. Because Algorithm 3 never allows a descent in the
pop stack, $w_{j}$ must have been the last entry popped from one pop operation
and $w_{k}$ must have been the first entry popped from the next pop operation.
The entries $w_{j}$ and $w_{k}$ must have appeared in the same relative order
(forming an inversion) in $w$. The only way to remove this inversion would be
for both entries to be in the pop stack at the same time.

Notice Algorithm 3 only pops the pop stack in two cases. In the first case,
the pop stack already contained two distinct values that are different from
the next input value. In this case, $w_{j}$ is one of the larger entries in
the pop stack. Also, $w_{j}$ is the first entry in $w$ from the all of entries
of the same value popped at the same time as $w_{j}$ because a new entry only
enters in the pop stack if it is smaller than the other value represented or
the new entry matches a value already there and is placed above it in the pop
stack. In fact, $w_{j}$ must be pushed into an empty pop stack as we are not
inserting any unmatched larger entries into the pop stack after a smaller
entry. Thus there must be a smaller entry $w_{m}$ popped at the same time as
$w_{j}$ and was inserted into the pop stack after $w_{j}$. Notice
$w_{j}w_{m}w_{k}$ form a $201$ or $210$ pattern in $w$ which is forbidden.

Otherwise, when $w_{j}$ is popped from the pop stack, only values matching
$w_{j}$ can be in the pop stack. For the next entry $w_{i}$, not to enter the
pop stack, we must have $w_{j}<w_{i}$. In this case, $w_{j}w_{i}w_{k}$ form a
$120$ pattern in $w$ which is also forbidden. ∎

The enumeration problem for this $(2,1)$-pop stack of depth $2$ can be
considered for permutations, words, and specifically inversion sequences. The
permutations of length $n$ avoiding $231,312,321$, i.e. $120,201,210$, are
known as the _layered permutations_ where each layer can have size one or two.
Note that layered permutations are exactly the permutations that avoid
$231,312$. Further, the restriction of avoiding $321$ forces each layer
(consecutive decreasing subsequence) to have size at most two. These
restricted layered permutations are enumerated by the Fibonacci numbers as
shown by Simion and Schmidt [26].

######  Corollary 3.24.

The number of permutations of length $n$ sortable by a $(2,1)$-pop stack of
depth $2$ is the $(n+1)^{\text{st}}$ Fibonacci number $F_{n+1}$.

Burstein [5, Theorem 5.1], enumerated the words of length $n$ over alphabet
$[k]$ avoiding $120,201,210$.

######  Theorem 3.25.

(Burstein) The generating function for the number of words of length $n$ over
alphabet $[k]$ sortable by a $(2,1)$-pop stack of depth $2$ is given by the
coefficient of $x^{n}y^{k}$ in $F(x,y)$ where

$F(x,y)=\frac{(1-x)(1-2x)-((1-x)(1-2x)+x^{2})y}{(1-x)(1-2x)-(1-x)(2-3x)y+(1-2x)y^{2}}.$

The case for the enumeration of sortable inversion sequences by a $(2,1)$-pop
stack of depth $2$ (in the form of avoidance of $120,201,210$ or otherwise)
does not appear in the literature prior to this work, but can be solved using
generating trees as demonstrated in subsection 4.1. Specifically, the
generating function for these sortable inversion sequences is given in Theorem
4.3.

## 4\. The generating tree method

###  4.1 A formula for the generating function for the number of inversion
sequences of length $n$ that avoid $120,201,210$

To enumerate the inversion sequences of length $n$ avoiding $120,201,210$,
i.e. the inversion sequences sortable by a $(2,1)$-pop stack of depth $2$, we
use the generating tree method shown by Kotsireas, Yıldırım, and the first
author [16].

Let ${\mathbf{A}}=\cup_{n=0}^{\infty}{\mathbf{I}}_{n}(120,201,210)$ be the set
of all nonempty inversion sequences that avoid $120$, $201$, and $210$. We
construct a pattern-avoidance tree ${\mathbf{T}}$ for the class of pattern-
avoiding inversion sequences ${\mathbf{A}}$ as follows.

  1. 1.

The root is $0$ (inversion sequence with one letter), that is,
$0\in{\mathbf{T}}$ at level $1$.

  2. 2.

Recursively construct the nodes at level $n+1$ of tree ${\mathbf{T}}$ from the
nodes at level $n$ by inserting a new letter at the end of the inversion
sequence. That is, the children of $e=e_{0}\cdots
e_{n}\in{\mathbf{I}}_{n}\cap{\mathbf{A}}$ are the inversion sequences
$e^{*}=e_{0}\cdots e_{n}j$ with $j=0,1,\ldots,n+1$ where
$e^{*}\in{\mathbf{I}}_{n+1}\cap{\mathbf{A}}$.

Now, we relabel the vertices of the tree ${\mathbf{T}}$ as follows. Define
${\mathbf{T}}(e)$ to be the subtree consisting of the inversion sequence $e$
as the root and its descendants in ${\mathbf{T}}$. We say that $e$ is
equivalent to $e^{\prime}$, denoted by $e\sim e^{\prime}$, if and only if
${\mathbf{T}}(e)\cong{\mathbf{T}}(e^{\prime})$ (in the sense of plane trees).
Let ${\mathbf{T}}^{\prime}$ be the same tree ${\mathbf{T}}$ where we replace
each node $e$ by the first node $e^{\prime}\in{\mathbf{T}}$ from top to bottom
and from left to right in ${\mathbf{T}}$ such that
${\mathbf{T}}(e)\cong{\mathbf{T}}(e^{\prime})$.

######  Definition 4.1.

A _succession rule_ , denoted $x\rightsquigarrow y_{1},y_{2},\ldots,y_{k}$,
will indicate that the set $\\{y_{1},y_{2},\ldots,y_{k}\\}$ will be such that
the generating subtrees rooted at $y_{1},y_{2},\ldots,y_{k}$ are equivalent to
those rooted at $z_{1},z_{2},\ldots,z_{k}$ where
$\\{z_{1},z_{2},\ldots,z_{k}\\}$ is the complete set of children of $x$.

######  Lemma 4.2.

The generating tree ${\mathbf{T}}^{\prime}$ is given by root $0$ and the
following succession rules

$\displaystyle a_{m}$ $\displaystyle\rightsquigarrow
a_{m+1},b_{m,1},\ldots,b_{m,m},$ $\displaystyle b_{m,j}$
$\displaystyle\rightsquigarrow(b_{m+2-j,1})^{j},b_{m+1,j},b_{m+1-j,1},\ldots,b_{m+1-j,m+1-j},$

where $a_{m}=0^{m}$ and $b_{m,j}=a_{m}j$ for $1\leq j\leq m$.

###### Proof.

We label the inversion sequence $0\in{\mathbf{I}}_{0}$ by $a_{1}$. Thus,
$a_{1}\rightsquigarrow a_{2},b_{1,1}$. More generally, by the definitions, the
children of $a_{m}\in{\mathbf{T}}^{\prime}$ are $a_{m}0,a_{m}1,\ldots,a_{m}m$,
which can also be denoted $a_{m+1},b_{m,1},\ldots,b_{m,m}$, respectively.
Thus, the rule $a_{m}\rightsquigarrow a_{m+1},b_{m,1},\ldots,b_{m,m}$ holds.

Also, the children of $b_{m,j}\in{\mathbf{T}}^{\prime}$ are
$b_{m,j}0,b_{m,j}1,\ldots,b_{m,j}(m+1)$. Notice
${\mathbf{T}}(b_{m,j}k)\cong{\mathbf{T}}(b_{m+2-j,1})$ with
$k=0,1,\ldots,j-1$. Clearly, when $j=1$, any inversion sequence
$0^{m}10\pi^{\prime}$ in ${\mathbf{I}}_{n}(120,201,210)$ if any only if
$0^{m+1}1\pi^{\prime}$ in ${\mathbf{I}}_{n}(120,201,210)$. Thus, we can assume
that $1\leq j\leq k-1$. To prove the claim for such $j$, let
$\pi=0^{m}jk\pi^{\prime}\in{\mathbf{I}}_{n}(120,201,210)$. Since $j>k$ and
$\pi$ avoids both $201$ and $210$, we see that there are no letters in
$\pi^{\prime}$ belonging to the set $\\{0,\ldots,k-1,k+1,\ldots,j-1\\}$. Thus,
by mapping $\pi$ to $0^{m+2-k}1\pi^{\prime\prime}$, where $\pi^{\prime\prime}$
is obtained from $\pi^{\prime}$ by mapping each letter $x$ of $\pi^{\prime}$
to $x+1-j$ with $x\neq k$, and mapping the letter $k$ to $0$. Hence, we see
that $\pi\in{\mathbf{I}}_{n}(120,201,210)$ if and only if
$0^{m+2-j}1\pi^{\prime\prime}\in I_{n+2-j}(120,201,210)$.

As none of our patterns have repeated letters, it is not hard to see
${\mathbf{T}}(b_{m,j}j)\cong{\mathbf{T}}(b_{m+1,j})$. Here we map any
inversion sequence $0^{m}jj\pi^{\prime}\in{\mathbf{I}}_{n}$ to
$0^{m+1}j\pi^{\prime}\in I_{n}$ with $1\leq j\leq m$, so this map respects the
rule of avoiding $120,201,210$.

In the last cases when $k=j+1,j+2,\ldots,m+1$, we have a similar mapping as
with the smaller $k$ values. Specifically,
${\mathbf{T}}(b_{m,j}k)\cong{\mathbf{T}}(b_{m+1-j,k-j})$. To see this, again,
let $\pi=0^{m}jk\pi^{\prime}\in I_{n}(120,201,210)$. Since $\pi$ avoids $120$,
we see that each letter of $\pi^{\prime}$ is at least $j$. Let
$\pi^{\prime\prime}$ be the obtained sequence from $\pi^{\prime}$ by
decreasing each nonzero letter of $\pi^{\prime}$ by $j$. Then the map from
$\pi=0^{m}jk\pi^{\prime}\in{\mathbf{I}}_{n}(120,201,210)$ to
$0^{m+1-j}(k-j)\pi^{\prime\prime}\in{\mathbf{I}}_{n-j}(120,201,210)$ is a
bijection. Hence, we have the following rule
$b_{m,j}\rightsquigarrow(b_{m+2-j,1})^{j},b_{m+1,j},b_{m+1-j,1},\ldots,b_{m+1-j,m+1-j}$,
which completes the proof. ∎

Define $A_{m}(x)$ (respectively, $B_{m,j}(x)$) to be the generating function
for the number of nodes at level $n\geq 1$ for the subtree of
${\mathbf{T}}(B;a_{m})$ (respectively, ${\mathbf{T}}(B;b_{m,j})$), where the
root stays at level $0$. Thus, by Lemma 4.2, we have

$\displaystyle A_{m}(x)$
$\displaystyle=x+xA_{m+1}(x)+x\sum_{j=1}^{m}B_{m,j}(x),$ (4) $\displaystyle
B_{m,j}(x)$
$\displaystyle=x+jxB_{m+2-j,1}+xB_{m+1,j}(x)+x\sum_{k=1}^{m+1-j}B_{m+1-j,k}(x),$
(5)

for all $1\leq j\leq m$.

In order to solve the above recurrence relations, we define

$\displaystyle A(v)$ $\displaystyle=\sum_{m\geq 1}A_{m}(x)v^{m-1},$
$\displaystyle B(v,u)$ $\displaystyle=\sum_{m\geq
1}\sum_{j=1}^{m}B_{m,j}(x)u^{m-j}v^{m-1},\text{ and}$ $\displaystyle C(v)$
$\displaystyle=\sum_{m\geq 1}B_{m,1}(x)v^{m-1}.$

Thus Equations (4)-(5) can be written as

$\displaystyle A(v)$
$\displaystyle=\frac{x}{1-v}+\frac{x}{v}(A(v)-A(0))+xB(v,1),$ (6)
$\displaystyle B(v,u)$
$\displaystyle=\frac{x}{(1-v)(1-uv)}+\frac{x}{uv(1-v)^{2}}(C(vu)-C(0))+\frac{x}{uv}(B(v,u)-B(v,0))+\frac{x}{1-v}B(uv,1),$
(7) $\displaystyle C(v)$
$\displaystyle=\frac{x}{1-v}+\frac{2x}{v}(C(v)-C(0))+xB(v,1),$ (8)

where the last equation (8) is the translating of (5) with $j=1$.

To solve the system from Equations (7)-(8), we make the following guess based
on the first terms of the generating functions $B(v,1)$, $C(v)$, and $A(v)$:

$\displaystyle B(v,1)$
$\displaystyle=\frac{1}{(1-v)^{2}}C(v)-\frac{v}{(1-v)^{2}}A(v).$ (9)

Next, we solve the system from Equations (7)-(9), which satisfies the original
system from Equations (7)-(8). By substituting the expression of $B(v,1)$ from
Equation (9) into Equation (7), and solving for $C(v)$, we obtain

$\displaystyle C(v)$
$\displaystyle=\frac{v^{3}-2v^{2}+2vx+v-x}{vx}A(v)+\frac{(1-v)^{2}}{v}A(0)+v-1.$
(10)

From here, use Equation (9) and Equation (10) to rewrite Equation (8) as

$\displaystyle\frac{2x^{2}-3x(x+1)v+(5x+1)v^{2}-2(x+1)v^{3}+v^{4}}{v^{2}x}A(v)$
$\displaystyle=\frac{2x-(3x+1)v+2(x+1)v^{2}-v^{3}}{v^{2}}A(0)-\frac{2x}{v}C(0)-\frac{(v-2x)(v-1)}{v}.$
(11)

Let $K(v)=2x^{2}-3x(x+1)v+(5x+1)v^{2}-2(x+1)v^{3}+v^{4}$ be the kernel of this
equation. Note that for the kernel equation $K(v)=0$ there are four roots, say
$v_{1},v_{2},v_{3},v_{4}$, where

$\displaystyle v_{1}$
$\displaystyle=1+\frac{-1+\sqrt{5}}{2}x+\frac{-5+4\sqrt{5}}{5}x^{2}+\cdots,$
$\displaystyle v_{2}$
$\displaystyle=1+\frac{-1-\sqrt{5}}{2}x+\frac{-5-4\sqrt{5}}{5}x^{2}+\cdots,$
$\displaystyle v_{3}$ $\displaystyle=2x+2x^{2}+10x^{3}+\cdots,$ $\displaystyle
v_{4}$ $\displaystyle=x-x^{3}-x^{4}+\cdots.$

By taking Equation (11) with either $v=v_{3}$ or $v=v_{4}$, we obtain a system
of equations in $A(0)$ and $C(0)$. We solve this system, obtaining

$\displaystyle A(0)$
$\displaystyle=-\frac{(v_{1}+v_{2}-2x-1)v_{1}v_{2}}{v_{1}v_{2}(v_{1}+v_{2})-2(1+x)v_{1}v_{2}+2x},$
$\displaystyle C(0)$
$\displaystyle=-\frac{v_{1}v_{2}(v_{2}-1)(v_{1}-1)-(v_{1}^{2}v_{2}+v_{1}v_{2}^{2}-2v_{1}^{2}-3v_{1}v_{2}-2v_{2}^{2}+2v_{1}+2v_{2})x+2(v_{1}v_{2}-2v_{1}-2v_{2}+2)x^{2}}{2x(v_{1}v_{2}(v_{1}+v_{2})-2(1+x)v_{1}v_{2}+2x)}.$

By using expressions of $A(0),C(0)$, we obtain an explicit formula for $A(v)$
from Equation (11). We can then obtain an explicit formula for $C(v)$ from
Equation (10). Then we can use that formula to get an explicit formula for
$B(v,1)$ from Equation (9). Finally, we have the information we need to obtain
an explicit formula for $B(v,u)$ from Equation (7). We omit the presentations
of the expressions $A(v),C(v),B(v,1),B(v,u)$ because they are very lengthy.
However, these expressions are satisfy the system of Equations (6)-(8). Hence,
we can state the following result.

######  Theorem 4.3.

The generating function for the number of inversion sequences in
${\mathbf{I}}_{n}$ that avoid $120,201,210$ and thus are sortable by a
$(2,1)$-pop stack of depth $2$ is given by

$\displaystyle A(0)$
$\displaystyle=-\frac{(v_{1}+v_{2}-2x-1)v_{1}v_{2}}{v_{1}v_{2}(v_{1}+v_{2})-2(1+x)v_{1}v_{2}+2x}$
$\displaystyle=x+2x^{2}+6x^{3}+23x^{4}+101x^{5}+484x^{6}+2468x^{7}+13166x^{8}+72630x^{9}+411076x^{10}+2374188x^{11}$
$\displaystyle+13938018x^{12}+82932254x^{13}+499031324x^{14}+3031610924x^{15}+18568429963x^{16}+114541486785x^{17}$
$\displaystyle+710973143614x^{18}+4437415155234x^{19}+27831038618735x^{20}+175318861863701x^{21}$
$\displaystyle+1108762012137252x^{22}+7037137177329268x^{23}+44808588430903068x^{24}+\cdots.$

###  4.2 The generating tree for the pop stack sortable inversion sequences

As in other cases, one can show that the generating tree (based on Algorithm
[16]) of $I_{n}(120,201,1010)$, that is, of the pop stack sortable inversion
sequences, is given by a root $a_{1}$ and the rules

$\displaystyle a_{m}$ $\displaystyle\rightsquigarrow
a_{m+1},b_{m,1},\ldots,b_{m,m},$ $\displaystyle b_{m,j}$
$\displaystyle\rightsquigarrow
c_{m+1-j,1},\ldots,c_{m,j},b_{m+1,j},b_{m+1-j,1},\ldots,b_{m+1-j,m+1-j},$
$\displaystyle c_{m,j}$ $\displaystyle\rightsquigarrow
c_{m+2-j,1},\ldots,c_{m+1,j},a_{m+3-j},b_{m+2-j,1},\ldots,b_{m+2-j,m+2-j},$

where $a_{m}=0^{m}$, $b_{m,j}=0^{m}j$ and $c_{m,j}=0^{m}j(j-1)$.

For any sequence of nodes $f_{m,j}$, we define $F_{m,j}(x)$ as the generating
functions for the number of nodes in the subtrees $\mathcal{T}(B;f_{m,j})$,
where $f\in\\{a,b,c,d\\},F\in\\{A,B,C\\}$. Define

$\displaystyle A(v)$ $\displaystyle=\sum_{m\geq 1}A_{m}(x)v^{m-1},$
$\displaystyle B(v,u)$ $\displaystyle=\sum_{m\geq
1}\sum_{i=1}^{m}B_{m,i}v^{m-1}u^{m-i},$ $\displaystyle C(v,u)$
$\displaystyle=\sum_{m\geq 1}\sum_{i=1}^{m}C_{m,i}v^{m-1}u^{m-i}.$

Then the generating function for the case 120,201,1010 is
$\frac{x}{1-x}+xB(x,1)$, where $B(x,v)$ satisfies

$\displaystyle A(v)$
$\displaystyle=\frac{x}{1-v}+\frac{x}{v}(A(v)-A(0))+xB(v,1),$ $\displaystyle
B(v,u)$
$\displaystyle=\frac{x}{(1-v)(1-uv)}+\frac{x}{uv}(B(v,u)-B(v,0))+\frac{x}{1-v}C(v,u)+\frac{x}{1-v}B(vu,1),$
$\displaystyle C(v,u)$
$\displaystyle=\frac{x}{(1-v)(1-uv)}+\frac{x}{vu(1-v)}(C(v,u)-C(v,0))$
$\displaystyle+\frac{x}{v^{2}u^{2}(1-v)}(A(uv)-A(0)-\frac{uv}{x}A(0)+vu+vuB(vu,1)).$

By applying this system $20$ times starting from $A(x,v)=B(x,v,u)=C(x,v,u)=0$,
we obtain the first $20$ coefficients of $A(0)$ as

$\displaystyle A(0)$
$\displaystyle=x+2x^{2}+6x^{3}+23x^{4}+101x^{5}+485x^{6}+2488x^{7}+13414x^{8}+75126x^{9}+433546x^{10}$
$\displaystyle+2563335x^{11}+15461646x^{12}+94835817x^{13}+589997530x^{14}+3715451178x^{15}$
$\displaystyle+23645541066x^{16}+151874732111x^{17}+983428159871x^{18}$
$\displaystyle+6413887925931x^{19}+42100271440339x^{20}+\cdots.$

## 5\. Open Problems

There are many directions left to continue the study of sortable inversion
sequences. The most obvious question is the elusive enumeration problem for
the inversion sequences of length $n$ which avoid $120$. Already interesting
as a standalone pattern avoidance question, the fact that these inversion
sequences are exactly those sortable by the classic stack sorting algorithm by
Knuth [15] increases the intrigue.

######  Open Question 5.1.

How many inversion sequences of length $n$ are stack sortable, i.e. avoid
$120$?

We have classified the pop stack sortable inversion sequences and words and
provided a generating tree for the inversion sequence case in subsection 4.2.
However, the combinatorial enumeration is still open.

######  Open Question 5.2.

How many inversion sequences of length $n$ are pop stack sortable, i.e. avoid
$120,201,1010$?

And the cases restricting pop stacks to particular depths in an analogous way
to [10, 11, 12, 13] and/or the expansion in allowable pushes analogous to [2]
can be interesting for words and inversion sequences.

######  Open Question 5.3.

Classify and enumerate the inversion sequences of length $n$ that are
$(r,1)$-pop stack sortable for pop stacks of depth $k$ for $r\geq 2$ and/or
$k\geq 2$.

Another avenue of exploration is considering other sorting machines or
algorithms. For instance, the authors considered a sorting algorithm on a
single stack prioritizing outputting the next correct entry of the sequence
until no other moves were available and then either returning the elements in
order to be sorted again [22] or reversing the output for the next pass [23].
In particular, the $2$-reverse-pass sortable permutation class has a
reasonably small basis, namely $\\{2413,2431,23154\\}=\\{1302,1320,12043\\}$
that may prove tractable.

######  Open Question 5.4.

How many inversion sequences of length $n$ are $2$-reverse-pass sortable?

## References

  * [1] Asinowski, A., Banderier, C., Billey, S., Hackl, B., and Linusson, S. Pop-stack sorting and its image: permutations with overlapping runs.  Acta Math. Univ. Comenian. (N.S.) 88, 3 (2019), 395–402.
  * [2] Atkinson, M. D. Generalized stack permutations.  Combin. Probab. Comput. 7 (1998), 239–246.
  * [3] Atkinson, M. D., and Sack, J.-R. Pop-stacks in parallel.  Inform. Process. Lett. 70 (1999), 63–67.
  * [4] Avis, D., and Newborn, M. On pop-stacks in series.  Utilitas Math. 19 (1981), 129–140.
  * [5] Burstein, A. Enumeration of Words with Forbidden Patterns.  PhD thesis, University of Pennsylvania, 1998.
  * [6] Callan, D., Jelínek, J., and Mansour, T. Inversion sequences avoiding a triple of patterns of 3 letters  Electron. J. Combin. 30:3 (2023), #P3.19.
  * [7] Claesson, A., and Guðmundsson, B. A. Enumerating permutations sortable by $k$ passes through a pop-stack.  Sém. Lothar. Combin. 80B (2018), Art. 43, 12.
  * [8] Corteel, S., Martinez, M. A., Savage, C. D., and Weselcouch, M. Patterns in inversion sequences I.  Discrete Math. Theor. Comput. Sci. 18, 2 (2016), Paper No. 2, 21\.
  * [9] Defant, C., and Williams, N. Crystal pop-stack sorting and type $A$ crystal lattices.  European J. Combin. 103 (2022), Paper No. 103514, 19.
  * [10] Elder, M. Permutations generated by a stack of depth $2$ and an infinite stack in series.  Electron. J. Combin. 13 (2006), Research paper 68, 12 pp.
  * [11] Elder, M., and Goh, Y. K. Permutations sorted by a finite and an infinite stack in series.  In Language and automata theory and applications, vol. 10792 of Lecture Notes in Comput. Sci. Springer, Cham, 2018, pp. 220–231.
  * [12] Elder, M., and Goh, Y. K. $k$-pop stack sortable permutations and 2-avoidance.  Electron. J. Combin. 28, 1 (2021), Paper No. 1.54, 15.
  * [13] Elder, M., Lee, G., and Rechnitzer, A. Permutations generated by a depth 2 stack and an infinite stack in series are algebraic.  Electron. J. Combin. 22, 2 (2015), Paper 2.16, 23.
  * [14] Hong, L. The pop-stack-sorting operator on Tamari lattices.  Adv. in Appl. Math. 139 (2022), Paper No. 102362, 13.
  * [15] Knuth, D. E. The art of computer programming. Volume 1.  Addison-Wesley Publishing Co., Reading, Mass., 1969.  Fundamental Algorithms.
  * [16] Kotsireas, I., Mansour, T., and Yıldırım, G. An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences.  Journal of Symbolic Computation (to appear).  Preprint.
  * [17] Laisant, C.-A. Sur la numération factorielle, application aux permutations.  Bull. Soc. Math. France 16 (1888), 176–183.
  * [18] Lehmer, D. H. Teaching combinatorial tricks to a computer.  In Proc. Sympos. Appl. Math., Vol. 10. American Mathematical Society, Providence, R.I., 1960, pp. 179–193.
  * [19] Lin, Z. Patterns of relation triples in inversion and ascent sequences  Theoret. Comput. Sci. 804 (2020), 115–125.
  * [20] Lin, Z., and Kim, D. Refined restricted inversion sequences  Ann. Comb. 25 (2021), 849–875.
  * [21] Mansour, T., and Shattuck, M. Pattern avoidance in inversion sequences.  Pure Math. Appl. (PU.M.A.) 25, 2 (2015), 157–176.
  * [22] Mansour, T., Skogman, H., and Smith, R. Passing through a stack $k$ times.  Discrete Math. Algorithms Appl. 11, 1 (2019), 1950003, 22.
  * [23] Mansour, T., Skogman, H., and Smith, R. Passing through a stack $k$ times with reversals.  European J. Combin. 81 (2019), 309–327.
  * [24] Martinez, M., and Savage, C. Patterns in inversion sequences II: inversion sequences avoiding triples of relations.  J. Integer Seq. 21, 2 (2018), Art. 18.2.2, 44.
  * [25] Pudwell, L., and Smith, R. Two-stack-sorting with pop stacks.  Australas. J. Combin. 74 (2019), 179–195.
  * [26] Simion, R., and Schmidt, F. W. Restricted permutations.  European J. Combin. 6, 4 (1985), 383–406.
  * [27] Sloane, N. J. The Online Encyclopedia of Integer Sequences.  http://oeis.org.
  * [28] Smith, R., and Vatter, V. The enumeration of permutations sortable by pop stacks in parallel.  Inform. Process. Lett. 109, 12 (2009), 626–629.
  * [29] Yaglom, A. M., and Yaglom, I. M. Challenging Mathematical Problems with Elementary Solutions, vol. 1.  Dover Publications Inc., New York, 1987.
  * [30] Yan, C., and Lin, Z. Inversion sequences avoiding pairs of patterns,  Discrete Math. Theor. Comput. Sci. 22:1 (2020-2021), Paper No. 23.