[intoc] spacing=nonfrench

ON THE MÖBIUS
FUNCTION OF
PERMUTATIONS
UNDER
THE PATTERN
CONTAINMENT ORDER
DAVID WILLIAM MARCHANT

A thesis submitted to The Open University

for the degree of Doctor of Philosophy

in Mathematics

April 2020

## Abstract

We study several aspects of the Möbius function, $\mu[\sigma,\pi]$, on the
poset of permutations under the pattern containment order.

First, we consider cases where the lower bound of the poset is indecomposable.
We show that $\mu[\sigma,\pi]$ can be computed by considering just the
indecomposable permutations contained in the upper bound. We apply this to the
case where the upper bound is an increasing oscillation, and give a method for
computing the value of the Möbius function that only involves evaluating
simple inequalities.

We then consider conditions on an interval which guarantee that the value of
the Möbius function is zero. In particular, we show that if a permutation
$\pi$ contains two intervals of length 2, which are not order-isomorphic to
one another, then $\mu[1,\pi]=0$. This allows us to prove that the proportion
of permutations of length $n$ with principal Möbius function equal to zero is
asymptotically bounded below by $(1-1/e)^{2}\geq 0.3995$. This is the first
result determining the value of $\mu[1,\pi]$ for an asymptotically positive
proportion of permutations $\pi$.

Following this, we use “2413-balloon” permutations to show that the growth of
the principal Möbius function on the permutation poset is exponential. This
improves on previous work, which has shown that the growth is at least
polynomial.

We then generalise 2413-balloon permutations, and find a recursion for the
value of the principal Möbius function of these generalisations.

Finally, we look back at the results found, and discuss ways to relate the
results from each chapter. We then consider further research avenues.

## Dedication

This thesis is dedicated to Jo. Five years ago she agreed that I could stop
work in order to study for a PhD – which has been the hardest I have ever
worked. There is no way for me to adequately express my gratitude for her
support, her tolerance for my mathematical adventures, or the way that she
makes me complete.

’a:niy l:dwodiy w:dwodiy liy

+sir ha+s*iyriym w;g

## Acknowledgements

I would like to thank my supervisor, Robert Brignall, for introducing me to
the Möbius function on the permutation pattern poset, and for offering me the
chance to study under his supervision. Robert has always been patient and
forbearing in our interactions, and has allowed me the freedom to find my own
mathematical “voice”.

As a part-time student, living some distance from The Open University campus,
my opportunities to meet with other PhD students have been somewhat limited.
Where these opportunities have arisen, I have been warmly welcomed. I would
especially like to thank Grahame Erskine, Jakub Sliačan, James Tuite, Margaret
Stanier, Olivia Jeans, and Rob Lewis for their support and discussions.

Part-time students are not entitled to any funding support from the School of
Mathematics and Statistics at The Open University. I am therefore most
grateful to the School for providing funding for conferences and visits over
the last four years. I am also grateful for the support received from the
National Science Foundation for contributions towards travel and accommodation
costs for attending conferences, and for the support from Charles University
in Prague for my visit in 2019.

The Permutation Patterns community is small and vibrant. I was made to feel
welcome by everyone I encountered. I would particularly like to thank Einar
Steingrímsson, Vít Jelínek, and Jan Kynčl for their support and encouragement.
I would also like to thank the anonymous referees of the papers which underpin
this thesis for all their work.

## Declarations

Some chapters of this thesis are based on work that has been published. The
relevant chapters are as follows:

  1. 1.

Chapter 4 is based on published joint work with Robert Brignall. The paper
[16] was published in _Discrete Mathematics_.

  2. 2.

Chapter 5 is based on published joint work with Robert Brignall, Vít Jelínek
and Jan Kynčl. The paper [15] was published in _Mathematika_. I thank the
London Mathematical Society for granting permission to include edited extracts
from the published article in this thesis.

  3. 3.

Chapter 6 is based on published sole work by the author. The paper [31] was
published in _The Electronic Journal of Combinatorics_.

None of the results appear in any other thesis, and all co-authors have agreed
with the inclusion of joint work in this thesis. Where work has been
published, the publishers have given permission for edited extracts of the
published article to be included in this thesis.

This thesis is approximately 49,000 words.

###### Contents

  1. Abstract
  2. Dedication
  3. Acknowledgements
  4. Declarations
  5. 1 Overview
    1. 1.1 Introductory material
    2. 1.2 Chapters based on published material
    3. 1.3 Conclusion
    4. 1.4 Details of chapters based on published material
      1. 1.4.1 The Möbius function of permutations with an indecomposable lower bound
      2. 1.4.2 Zeros of the Möbius function of permutations
      3. 1.4.3 2413-balloons and the growth of the Möbius function
      4. 1.4.4 The principal Möbius function of balloon permutations
  6. 2 Common definitions
  7. 3 Background and history
    1. 3.1 Permutations
    2. 3.2 The Möbius function
      1. 3.2.1 Simplicial complexes
      2. 3.2.2 Incidence algebras and incidence matrices
    3. 3.3 The Möbius function for general posets
    4. 3.4 The Möbius function of the permutation poset under pattern containment
    5. 3.5 Motivation
  8. 4 The Möbius function of permutations with an indecomposable lower bound
    1. 4.1 Preamble
    2. 4.2 Introduction
    3. 4.3 Definitions and notation
    4. 4.4 Preliminary lemmas and main theorem
    5. 4.5 Increasing oscillations
      1. 4.5.1 Example of Theorem 23
    6. 4.6 Concluding remarks
    7. 4.7 Chapter summary
  9. 5 Zeros of the Möbius function of permutations
    1. 5.1 Preamble
    2. 5.2 Introduction
    3. 5.3 Definitions and notation
      1. 5.3.1 Intervals with vanishing Möbius function
      2. 5.3.2 Embeddings
      3. 5.3.3 Möbius function via normal embeddings
    4. 5.4 Permutations with opposing adjacencies
    5. 5.5 A general construction of $\sigma$-annihilators
    6. 5.6 The density of zeros
    7. 5.7 More complicated examples
    8. 5.8 Concluding remarks
    9. 5.9 Chapter summary
      1. 5.9.1 Improving the lower bound for the density of zeros, $d_{n}$
      2. 5.9.2 Extending the “opposing adjacencies” theorem
  10. 6 2413-balloons and the growth of the Möbius function
    1. 6.1 Preamble
    2. 6.2 Introduction
    3. 6.3 Essential definitions, notation, and results
    4. 6.4 2413-Balloons
    5. 6.5 The principal Möbius function of double 2413-balloons
    6. 6.6 The growth of the Möbius function
    7. 6.7 The principal Möbius function of 2413-balloons
    8. 6.8 Concluding remarks
      1. 6.8.1 Generalising the balloon operator
      2. 6.8.2 Generalised 2413-balloons
      3. 6.8.3 Bounding the Möbius function on hereditary classes
    9. 6.9 Chapter summary
  11. 7 The principal Möbius function of balloon permutations
    1. 7.1 Preamble
    2. 7.2 Introduction
    3. 7.3 Definitions, examples and notation
      1. 7.3.1 Balloon permutations
      2. 7.3.2 Types of balloon permutations
      3. 7.3.3 Notation
    4. 7.4 The principal Möbius function of balloon permutations
    5. 7.5 The principal Möbius function of wedge permutations
    6. 7.6 Chapter summary
  12. 8 Conclusion
    1. 8.1 A review of our results
    2. 8.2 Further research into the Möbius function
      1. 8.2.1 The Möbius function of simple permutations
    3. 8.3 Further research into global properties of the poset
      1. 8.3.1 Extremal values of $\mu[\pi]$ as a function of the length of the permutations
      2. 8.3.2 Characterising permutations where $\mu[\pi]$ achieves extreme values
  13. A Values of $\mu[\pi]$ where $\pi$ is a specific simple permutation
    1. A.1 Values of $\mu[W_{1}(n)]$
    2. A.2 Values of $\mu[W_{2}(n)]$
    3. A.3 Values of $\mu[E_{1}(2n,k)]$
    4. A.4 Values of $\mu[E_{2}(2n)]$
    5. A.5 Values of $\mu[O(2n+1,k)]$
  14. B Canonical permutations that achieve $\operatorname{Max_{\mu}}(n)$ or $\operatorname{Min_{\mu}}(n)$

##  Chapter 1 Overview

This thesis is primarily concerned with the Möbius function on the poset of
permutations ordered by classic pattern containment.

This thesis consists of eight chapters.

###  1.1 Introductory material

This chapter (Chapter 1), is an overview of the thesis. Following this
overview, we have Chapter 2, which defines the terminology and notation for
the subject area as a whole. Subsequent chapters will also include definitions
of terminology and notation that is only used in those chapters. This is then
followed, in Chapter 3, with a brief overview of the history of the subject
area, and a description of the motivation for the work described in this
thesis.

###  1.2 Chapters based on published material

Chapters 4, 5, and 6 are based on material that has been published in peer-
reviewed journals. Chapter 7 is based on material currently being prepared for
publication.

These chapters start with a section (“Preamble”) that introduces the subject
matter. This is based on the abstract of the published paper, but may include
additional material to help place the subject into the context of this thesis.
This is then followed by sections that are based on the published material. We
then conclude each chapter with a section (“Chapter summary”) that summarises
the impact of the results, discusses how they relate to this thesis, and
considers possible avenues for further research following on from the results
described in the chapter.

###  1.3 Conclusion

Chapter 8 looks back at the results from chapters 4, 5, 6, and 7. Here we
summarise the results that we presented in the preceding four chapters, and
discuss whether it is possible to find a common theme (beyond the obvious
“related to the Möbius function”) in the work presented. We then consider
possible avenues for future research.

###  1.4 Details of chapters based on published material

We now provide a more detailed description of the chapters based on published
material, or on material being prepared for publication.

In the description that follows, we may use terminology that is in common use
in the field, but which will not be formally defined until Chapter 2.

####  1.4.1 The Möbius function of permutations with an indecomposable lower
bound

Chapter 4 is based on a published paper, “The Möbius function of permutations
with an indecomposable lower bound” [16], which is joint work with Robert
Brignall. In this paper we show that, given some interval $[\sigma,\pi]$ in
the permutation poset, if $\sigma$ is sum (resp. skew) indecomposable, then
the value of the Möbius function $\mu[\sigma,\pi]$ depends solely on the sum
(resp. skew) indecomposable permutations contained in the upper bound $\pi$.

The basic methodology is to first use existing results to show that certain
permutations that are contained in the interval do not contribute to the value
of the Möbius function. We then show that the permutations that remain can be
partitioned into families, defined by a single sum (resp. skew) indecomposable
permutation $\alpha$, and that the net contribution of a family will be in
$\\{\pm\mu[\sigma,\alpha],0\\}$. We derive a $\\{\pm 1,0\\}$ weighting
function $W(\sigma,\alpha,\pi)$, and using this, we then show that
$\mu[\sigma,\pi]$ can be calculated by summing the value of
$\mu[\sigma,\alpha]W(\sigma,\alpha,\pi)$, over all permutations $\alpha$ that
are sum (resp. skew) indecomposable and contained in the interval.

We then set $\pi$ to be an increasing oscillation. This allows us to define a
revised weighting function specific to these intervals which can be computed
by using simple inequalities. This then leads to a fast algorithm for
calculating $\mu[\sigma,\pi]$, where $\pi$ is an increasing oscillation.

We then have some conjectures relating to the long-term behaviour of the
absolute value of $\mu[1,\pi]$, where $\pi$ is an increasing oscillation.

The chapter concludes by summarising the impact of the results, particularly
from a computational perspective.

####  1.4.2 Zeros of the Möbius function of permutations

Chapter 5 is based on a published paper “Zeros of the Möbius function of
permutations” [15], which is joint work with Robert Brignall, Vít Jelínek and
Jan Kynčl.

In this paper we show that if a permutation $\pi$ contains two opposing
adjacencies, then $\mu[1,\pi]=0$. We then use this result to show that the
proportion of permutations of length $n$ with principal Möbius function equal
to zero is, asymptotically, bounded below by 0.3995.

We start by showing that if a poset $P$ has a particular structure, then
$\mu[P]=0$. We then show that if a permutation $\pi$ contains two opposing
adjacencies, then the poset interval $[1,\pi]$ has the required structure, and
it follows that $\mu[1,\pi]=0$. We then provide a second proof of the same
result based on normal embeddings. The techniques used in both proofs are used
in later, more complicated, settings.

We then show that if $\sigma$ is any permutation, and $\phi$ meets certain
requirements, then any permutation $\pi$ that contains an interval order-
isomorphic to $\phi$ has $\mu[\sigma,\pi]=0$. We use this result to show if
$\sigma$ meets a particular condition, and $\pi$ contains an interval copy in
the form $\alpha\oplus 1\oplus\beta$, then $\mu[\sigma,\pi]=0$. We then show
that if $\sigma=1$, then $\sigma$ meets the condition required, and thus we
prove that if a permutation contains an interval copy in the form
$\alpha\oplus 1\oplus\beta$, then $\mu[1,\pi]=0$.

In the next part of this chapter, we show that, asymptotically, the proportion
of permutations of length $n$ that have a principal Möbius function value of
zero, $d_{n}$, is bounded below by
$\left(1-\dfrac{1}{\mathrm{e}}\right)^{2}\approxeq 0.3995$.

We then use the techniques already introduced to show that there are pairs of
permutations, $\alpha,\beta$, such that if $\pi$ contains interval copies of
$\alpha$ and $\beta$, then $\mu[1,\pi]=0$. We further show that there are
individual permutations $\alpha$ with the property that if $\pi$ contains an
interval copies of $\alpha$, then $\mu[1,\pi]=0$.

We then discuss further ways in which we could find a permutation $\pi$ where
the presence of a specific interval or intervals in $\pi$ would guarantee
$\mu[1,\pi]=0$. We discuss $d_{n}$, including a conjecture on an upper bound
for $d_{n}$.

The chapter concludes by summarising the impact of the results. We show that
there is some numerical evidence that a large proportion of permutations with
multiple non-opposing adjacencies have a principal Möbius function value of
zero, and show that if we could prove this for a positive proportion of these
permutations, then we could improve the lower bound of $d_{n}$.

We discuss extending the opposing adjacency result to more general poset
intervals and show that this is not possible in all cases. We then present two
minor results. The first shows that certain intervals $[\sigma,\pi]$ have
$\mu[\sigma,\pi]=0$. The second result shows that if $\sigma$ is adjacency-
free, and $\pi$ is an inflation of $\sigma$, and $\mu[\sigma,\pi]=0$, then we
have some information about the permutations used in the inflation.

####  1.4.3 2413-balloons and the growth of the Möbius function

Chapter 6 is based on a published paper “2413-balloons and the growth of the
Möbius function” [31], which is sole work by the author. In this paper we show
that the growth of the principal Möbius function on the permutation poset is
exponential.

We start by defining the “2413-balloon” of some permutation $\beta.$ The
resulting permutation has extremal points that are order-isomorphic to 2413,
and the non-extremal points are an interval copy of $\beta$. A double
2413-balloon is the result of ballooning a permutation that is already a
2413-balloon.

We take a poset where the upper bound is a double 2413-balloon, and the lower
bound is 1, and we show how we can partition the chains in the poset into
three sets. We then show that two of these subsets contribute zero to the
value of the Möbius function.

The remaining set of chains has the property that the second-highest element
of every chain is in a particular set of permutations. We show that the Hall
sum over the remaining chains is equivalent to summing the Möbius function
over the set of permutations. The permutations in this set have the property
that they can all be formed as the sum of $\beta$ and either one, two or three
copies of the permutation $1$. For example, one of these permutations is
$1\oplus\beta$, and another is $1\ominus((\beta\ominus 1)\oplus 1)$. If we let
$\rho$ be one of the permutations in the set, then this means that we can use
a well-known result to show that $\mu[1,\rho]=\pm\mu[1,\beta]$.

We use this to show that if $\beta$ is a 2413-balloon, and $\pi$ is the
2413-balloon of $\beta$, then $\mu[1,\pi]=2\mu[1,\beta]$, and this in turn
allows us to show that the growth of the principal Möbius function on the
permutation poset is exponential.

We then consider 2413-balloons where the permutation being ballooned is not
itself a 2413-balloon. Using a similar argument to that used for double
2413-balloons, we derive an expression for $\mu[1,\pi]$, where $\pi$ is the
2413-balloon of some permutation $\beta$, and $\beta$ is not a 2413-balloon.
For all but trivial cases we prove that $\mu[1,\pi]=\mu[1,\beta]$.

We discuss generalising the “balloon” operation. We provide two conjectures
which, up to symmetry, cover all generalised 2413-balloons.

The chapter concludes with a brief discussion of a set of permutations where
it is believed that the growth of the principal Möbius function is also
exponential, but the “growth rate” is faster than that found for double
2413-balloons. We also discuss generalised balloons.

####  1.4.4 The principal Möbius function of balloon permutations

Chapter 7 is based on an unpublished paper which is being prepared for
submission in parallel with this thesis, and which is sole work by the author.
In this paper we generalise the 2413-balloon permutations used in Chapter 6,
and derive an expression for the value of the principal Möbius function of
these permutations.

We start by defining a method of constructing a permutation from two smaller
permutations $\alpha$ and $\beta$. This construction method requires that the
constructed permutation contains $\beta$ as an interval copy, and that the
remaining points are order-isomorphic to $\alpha$. We call such a permutation
a “balloon” permutation, which we write as $\alpha\circledcirc_{i,j}\beta$. We
describe several sub-types of balloon permutation, including one that we call
a “wedge” permutation.

We show that the chains in the poset interval
$[1,\alpha\circledcirc_{i,j}\beta]$ can be partitioned into three sets. We
further show that one of these subsets contributes zero to the value of the
Möbius function. We then prove that the contribution of a second subset can be
written as the sum of the principal Möbius function of a set of permutations,
all of which contain $\beta$ as an interval copy. This leads to an expression
for $\mu[1,\alpha\circledcirc_{i,j}\beta]$. This expression includes a
“correction factor”, expressed as a sum over a particular set of (hard to
handle) chains.

We then consider wedge permutations, and we show that the correction factor is
always zero, thus leading to a simplified expression for the principal Möbius
function of a wedge permutation.

We further show that the principal Möbius function of a wedge permutation is
always a multiple of the principal Möbius function of $\beta$.

We discuss some of the problems that need to be overcome in order to extend
our result to any interval where the upper bound is a balloon permutation.

##  Chapter 2 Common definitions

A _permutation_ of length $n$ is an ordering of the natural numbers
$1,\ldots,n$. For short (length less than 10) permutations, we write the
permutation without delimiters, so $2413$ represents a permutation of length
4, where the first element has value $2$. For longer permutations, we use
commas to delimit values, so, for example, we would write
$1,7,4,3,10,9,2,5,8,6$. We may occasionally use commas as delimiters in short
permutations, where this will aid the reader. We use $\pi_{i}$ to refer to the
$i$-th element of the permutation $\pi$, so, for example, if $\pi=2413$, then
$\pi_{1}=2$. We let $\epsilon$ denote the unique permutation of length $0$. We
write the length of a permutation $\pi$ as $\left\lvert\pi\right\rvert$.

If $L$ is a list of distinct integers, then we can treat $L$ as a permutation
by replacing the $i$-th smallest entry with $i$. As an example, if
$L=4,9,2,6$, then $L$ represents the permutation 2413.

A permutation $\pi$ can be represented graphically by plotting the points
$(i,\pi_{i})$, with $1\leq i\leq\left\lvert\pi\right\rvert$, as shown in
Figure 2.1. Throughout we treat a permutation and its plot interchangeably.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$$\bullet$$\circ$$\bullet$$\circ$$\bullet$$\circ$
Figure 2.1: The permutation $1,7,4,3,10,9,2,5,8,6$, highlighting one of the
copies of $2413$ that it contains.

The set of all permutations of length $n$ is written $\mathcal{S}_{n}$. A
sequence of numbers $a_{1},a_{2},\dots,a_{n}$ is _order-isomorphic_ to a
sequence $b_{1},b_{2},\allowbreak\dots,b_{n}$ if for every $i,j\in[1,n]$ we
have $a_{i}<a_{j}\Leftrightarrow b_{i}<b_{j}$. A permutation
$\pi\in\mathcal{S}_{n}$ _contains_ a permutation $\sigma\in\mathcal{S}_{k}$ as
a _pattern_ if $\pi$ has a subsequence of length $k$ order-isomorphic to
$\sigma$. We say that $\pi$ _avoids_ $\sigma$ if $\pi$ does not contain
$\sigma$. There are other ways to define pattern containment, some of which
are more specific, and others more general. We discuss some of these in
Chapter 3, and in that chapter we refer to containment as defined above as
_classic pattern containment_. Throughout the rest of this document we omit
the qualifier “classic”.

As an example of containment, the permutation $2413$ is contained in the
permutation $1,7,4,3,10,9,2,5,8,6$, as shown in Figure 2.1.

If $\sigma$ is contained in $\pi$, then there will be at least one set of
points of $\pi$, with cardinality $\left\lvert\sigma\right\rvert$, such that
the set of points is order-isomorphic to $\sigma$. We call such a set of
points an _embedding_ of $\sigma$ into $\pi$. The points highlighted in Figure
2.1, (4,9,2,6), represent one possible embedding of $2413$ in
$1,7,4,3,10,9,2,5,8,6$. Typically, where embeddings are used, the arguments
used require that only some of the embeddings are counted, and these are
generally referred to as _normal embeddings_. It is notable that the precise
definition of a normal embedding varies between papers, and indeed, in
Brignall et al [15], several different definitions of normal embedding are
used.

We note here that one problem with embeddings arises in cases such as
$\mu[1,24153]$. Here there are plainly only five ways to embed the permutation
$1$ into $24153$, however $\mu[1,24153]=6$, and thus the embedding approach is
not sufficient. One possible solution to this issue is to count the normal
embeddings and then add a correction factor.

The set of all permutations, ordered by pattern containment, is a _poset_
(partially ordered set).

If we have two permutations $\sigma$ and $\pi$ such that $\sigma$ is not
contained in $\pi$, and $\pi$ is not contained in $\sigma$, then we say that
$\sigma$ and $\pi$ are _incomparable_.

A closed interval $[\sigma,\pi]$ in a poset is the set defined as
$\\{\tau:\sigma\leq\tau\leq\pi\\}$. A half-open interval $[\sigma,\pi)$ is the
set $\\{\tau:\sigma\leq\tau<\pi\\}$, and the open interval $(\sigma,\pi)$ is
the set $\\{\tau:\sigma<\tau<\pi\\}$, The _Möbius function_ ,
$\mu[\sigma,\pi]$, is defined for an ordered pair of elements $(\sigma,\pi)$
from any poset. If $\sigma\not\leq\pi$, then $\mu[\sigma,\pi]=0$, and if
$\sigma=\pi$, then $\mu[\sigma,\pi]=1$. The remaining possibility is that
$\sigma<\pi$, and in this case we have

$\displaystyle\mu[\sigma,\pi]$
$\displaystyle=-\sum_{\lambda\in[\sigma,\pi)}\mu[\sigma,\lambda].$ (2.1)

If we have $\sigma<\pi$, then from the definition above we also have

$\displaystyle\sum_{\lambda\in[\sigma,\pi]}\mu[\sigma,\lambda]$
$\displaystyle=0.$

For posets that possess a unique smallest element $\hat{0}$, we define the
_principal Möbius function_ , $\mu[\pi]=\mu[\hat{0},\pi]$. We will
occasionally want to discuss the Möbius function of a poset $P$ with a unique
minimal element $\hat{0}$, and unique maximal element $\hat{1}$. Here, we
define $\mu[P]=\mu[\hat{0},\hat{1}]=\sum_{\hat{0}\leq
x<\hat{1}}\mu[\hat{0},x]$.

The _Hasse diagram_ of a poset $P$ is a directed graph, where two vertices $u$
and $w$ are connected from $u$ to $w$ by a directed arc if and only if $w<u$,
and there is no $v$ such that $w<v<u$. The Hasse diagram of the permutation
poset $[1,13524]$ is shown in Figure 2.2. Note that we sometimes omit the
arrowheads for clarity, as Hasse diagrams, by convention, are always drawn
with the arc direction downwards.

135241243142313241342241312313231221323112211 Figure 2.2: The Hasse diagram of
the poset interval $[1,13524]$.

A _chain_ in a poset interval $[\sigma,\pi]$ is, for our purposes, a subset of
the elements in the interval $[\sigma,\pi]$, where the subset includes the
elements $\sigma$ and $\pi$, and every distinct pair of elements of the subset
are comparable. This last clause means that the subset has a total order. If a
chain $c$ has $k$ elements, then we say that the length of $c$, written
$\left\lvert c\right\rvert$, is $k-1$. One way to visualise a chain is to
first choose a path in the Hasse diagram from the highest entry to the lowest,
and then a chain is found by choosing a (possibly improper) subset of the
elements on the path, ensuring that the first and last elements (the upper and
lower bounds of the poset) are included in the subset.

Chains in a poset interval are related to the Möbius function by Hall’s
Theorem [50, Proposition 3.8.5], which says that

$\displaystyle\mu[\sigma,\pi]=\sum_{c\in\mathcal{C}(\sigma,\pi)}(-1)^{\left\lvert
c\right\rvert}=\sum_{i=1}^{\left\lvert\pi\right\rvert-1}(-1)^{i}K_{i}$

where $\mathcal{C}(\sigma,\pi)$ is the set of chains in the poset interval
$[\sigma,\pi]$, and $K_{i}$ is the number of chains of length $i$.

If $\mathcal{C}$ is a subset of the chains in some poset interval
$[\sigma,\pi]$, then the _Hall sum_ of $\mathcal{C}$ is
$\sum_{c\in\mathcal{C}}(-1)^{\left\lvert c\right\rvert}$.

A _parity-reversing involution_ , $\Phi:\mathcal{C}\mapsto\mathcal{C}$, is an
involution such that for any $c\in\mathcal{C}$, the parities of $c$ and
$\Phi(c)$ are different.

A simple corollary to Hall’s Theorem is

######  Corollary 1.

If we can find a set of chains $\mathcal{C}$ with a parity-reversing
involution, then the Hall sum of $\mathcal{C}$ is zero.

###### Proof.

Because there is a parity-reversing involution, the number of chains in
$\mathcal{C}$ with odd length is equal to the number of chains with even
length, so $\sum_{c\in\mathcal{C}}(-1)^{\left\lvert c\right\rvert}=0$. ∎

In Chapters 6 and 7 we will want to show that there is a parity-reversing
involution on a set of chains $\mathcal{C}$. Our basic methodology, given a
set of chains $\mathcal{C}$, and a chain $c\in\mathcal{C}$, will be to
construct a chain $c^{\prime}$ by using a parity-reversing involution $\Phi$.
Strictly speaking, $\Phi$ is a function that maps a set of permutations (which
is a chain) to a set of permutations (which may not be a chain). As examples,
if $\Phi(c)$ removes the largest or smallest element of $c$, or adds an
element so that $\Phi(c)$ does not have a total order, then $\Phi(c)$ is not a
chain. To show that $\Phi$ is a parity-reversing involution we will need to
show that $\Phi(c)$ is a chain in $\mathcal{C}$, and that $c$ and $\Phi(c)$
have opposite parities. In our discussions, we will typically set
$c^{\prime}=\Phi(c)$, and then show that the set of permutations $c^{\prime}$
is a chain. We will then, without further comment, treat $c^{\prime}$ as a
chain.

When discussing chains, in general we will only be interested in a small
subset of the chain containing two or three elements. We say that a _segment_
of some chain $c$ is a non-empty subset of the elements in $c$ with the
property that any element not in the segment is either less than every element
in the segment, or is greater than every element in the segment.

A _direct sum_ of two permutations $\alpha$ and $\beta$ of lengths $m$ and $n$
respectively is the permutation
$\alpha_{1},\ldots,\alpha_{m},\beta_{1}+m,\ldots,\beta_{n}+m$. We write a sum
as $\alpha\oplus\beta$. A _skew sum_ , $\alpha\ominus\beta$, is the
permutation $\alpha_{1}+n,\ldots,\alpha_{m}+n,\beta_{1},\ldots,\beta_{n}$. As
examples, $321\oplus 213=321546$, and $321\ominus 213=654213$, and these are
shown in Figure 2.3. A _sum-indecomposable_ (resp. _skew-indecomposable_)
permutation is a permutation that cannot be written as the direct sum (resp.
skew sum) of two smaller permutations. If a permutation is not sum-
indecomposable, then it is _sum-decomposable_ , and if a permutation is not
skew-indecomposable, then it is _skew-decomposable_ ,

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$ $321\oplus 213$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$ $321\ominus 213$

Figure 2.3: Examples of direct and skew sums.

Given a permutation $\pi$, the _finest_ sum decomposition (resp. skew
decomposition) of $\pi$ is a decomposition into the maximum number of sum-
indecomposable (resp. skew-indecomposable) permutations. As examples, using
Figure 2.3, the finest sum decomposition of $321546$ is $321\oplus 21\oplus
1$, and the finest skew-decomposition of $654213$ is $1\ominus 1\ominus
1\ominus 213$.

Let $\alpha$ be a permutation, and $r$ a positive integer. Then
$\oplus^{r}\alpha$ is
$\alpha\oplus\alpha\oplus\ldots\oplus\alpha\oplus\alpha$, with $r$ occurrences
of $\alpha$. If $S$ is a set of permutations, then
$\oplus^{r}S=\cup_{\lambda\in S}\\{\oplus^{r}\lambda\\}$.

A _layered_ permutation is a permutation that can be written as the direct sum
of one or more decreasing permutations. Egge and Mansour, in [20], show that
layered permutations can also be defined as permutations that avoid the
permutations $231$ and $312$. The first example in Figure 2.3 is a layered
permutation.

If a permutation $\pi$ can be written as $1\oplus 1\oplus\tau$, $1\ominus
1\ominus\tau$, $\tau\oplus 1\oplus 1$, or $\tau\ominus 1\ominus 1$, where
$\tau$ is non-empty (so $\left\lvert\pi\right\rvert\geq 3$), then we say that
$\pi$ has a _long corner_.

We will occasionally want to discuss situations where some permutation $\pi$
is known to have a sum-decomposable (resp. skew-decomposable) decomposition,
but we do not know exactly which permutations form the decomposition. In such
cases we will write $\pi=\alpha_{1}\oplus\ldots\oplus\alpha_{n}$ or
$\pi=\alpha_{1}\ominus\ldots\ominus\alpha_{n}$. Similarly, if we want to
discuss an arbitrary set of permutations then we will write
$\\{\alpha_{1},\ldots,\alpha_{n}\\}$. It will always be clear from the context
whether $\alpha_{i}$ refers to the $i$-th element of the permutation $\alpha$,
the $i$-th permutation in a sum, or the $i$-th permutation in a set of
permutations.

An _interval_ in a permutation $\pi$ is a non-empty contiguous set of indexes
$i,i+1,\ldots,j$ such that the set of values
$\\{\pi_{i},\pi_{i+1},\ldots,\pi_{j}\\}$ is also contiguous. Every permutation
$\pi$ has intervals of length 1 and of length $\left\lvert\pi\right\rvert$,
which we call _trivial intervals_. A _simple_ permutation is a permutation
that only has trivial intervals. As examples, $1324$ is not simple, as, for
example, the second and third points $(32)$ form a non-trivial interval,
whereas $2413$ is simple.

We say that $\pi$ has an _interval copy_ of a permutation $\alpha$ if it
contains an interval of length $\left\lvert\alpha\right\rvert$ whose elements
form a subsequence order-isomorphic to $\alpha$.

We note here that the term “interval” is used in relation to both posets and
permutations. This is standard terminology in the field, and when we use the
term “interval” it will be clear from the context whether we are referring to
a poset interval or an interval in a permutation.

An interval of length 2 is termed an _adjacency_ in this thesis. An adjacency
is clearly order-isomorphic to either $12$, an _up-adjacency_ , or to $21$, a
_down-adjacency_. If a permutation contains at least one up-adjacency and at
least one down-adjacency, then we say that the permutation has _opposing
adjacencies_. An interval of length 3 that is monotonic, that is, order-
isomorphic to either 123 or 321, is a _triple-adjacency_. We note here that
some sources use “adjacency” to refer to a non-trivial interval of any length
that is monotonic.

A _descent_ in a permutation $\pi$ is a position $i$ such that
$\pi_{i}>\pi_{i+1}$. Similarly, an _ascent_ in a permutation $\pi$ is a
position $i$ such that $\pi_{i}<\pi_{i+1}$.

A _permutation class_ is a set of permutations $C$ with the property that if
$c\in C$, and $d<c$, then $d\in C$. Every permutation class can be defined by
the minimal set of permutations that are not contained in the class, and this
minimal set is referred to as the _basis_. If a permutation class $C$ has
basis $B$, then we write $C=\operatorname{Av}(B)$. Where we want to discuss a
permutation class $C$ that contains a specific set of (normally simple)
permutations, we refer to $C$ as a _hereditary class_. There is no difference
between a permutation class and a hereditary class, the distinction is simply
used to draw attention to the properties of the class that we are discussing.

Permutations can be represented by plotting points in a square grid, as
described earlier. It is clear that any symmetry of the square, if applied to
a permutation plot, will result in another permutation plot. If $\alpha$ is a
permutation, then a reflection in a vertical bisector of the plot is called a
_reversal_ , written $\alpha^{R}$, a reflection in a horizontal bisector of
the plot is called a _complement_ , written $\alpha^{C}$. The inverse of a
permutation, written $\alpha^{-1}$ is also a symmetry. These three operations
are the generating set of the group of symmetries of permutations.

We can now see that for any permutations $\sigma$ and $\pi$, and any symmetry
$S$,

$\mu[\sigma,\pi]=\mu[\sigma^{S},\pi^{S}].$

We will occasionally want to discuss permutations where we want a unique
representative from the symmetries. We say that such a representative is the
_canonical_ form of the permutation, and for our purposes we choose the
symmetry which is smallest under the lexicographic order. As an example, 2413
and 3142 are symmetries of one another, and the canonical representation is
2413.

##  Chapter 3 Background and history

###  3.1 Permutations

The first, albeit implicit, reference to permutations in the literature
appears to be due to Euler in [22], where he describes polynomials which
essentially define what are now known as the Eulerian numbers $A_{n,m}$. In
permutational terms, $A_{n,m}$ counts the number of permutations of length $n$
that have $m$ descents. The next significant set of results comes some 150
years later, where MacMahon [30] has a result that, interpreted in
permutational terms, shows that $\operatorname{Av}(123)$ is counted by the
Catalan numbers. The Erdős-Szekeres theorem [21] can be interpreted as saying
that a permutation of length $(a-1)(b-1)+1$ must contain either an increasing
sequence of length $a$ or a decreasing sequence of length $b$.

The study of pattern avoidance in permutations can be said to have started
with exercise 2.2.1(5) in Knuth [29], where readers are essentially asked to
show that a permutation that can be stack-sorted must avoid 231. This work was
further developed in the 1970s and 1980s in papers by Knuth [28], Rogers [35],
Rotem [37], and Simion and Schmidt [42].

This initial development then turned into a veritable explosion of papers,
most of which are too specific to relate to this general background. A good
summary of the way in which the field has developed can be found in the book
by Kitaev [27], the book by Bona [10], the survey article by Steingrímsson
[51], and the chapter by Vatter on permutation classes in [9].

###  3.2 The Möbius function

The Möbius function was first defined in the context of number theory by
August Möbius in 1832 in [34]. In that paper, Möbius defines
$\mu(n):\mathbb{N}\mapsto\mathbb{N}$ as 0 if $n$ has a repeated prime factor,
and as $(-1)^{k}$ if $n$ is the product of $k$ distinct prime factors. If we
say that a positive integer $a$ is contained in a positive integer $b$ if $a$
divides $b$, then the integers under this relationship form a poset, and
$\mu(n)=\mu[1,n]$.

The number-theoretic Möbius function has been extensively studied since its
definition. The combinatorial Möbius function does not seem to have any
significant presence in the literature until a seminal paper by Rota in 1964
[36], which made an explicit link between the principle of inclusion–exclusion
and the combinatorial Möbius function.

While there are many papers that have results relating to the Möbius function
on a variety of posets, we refer the reader to Cameron [19] or Stanley [50]
for a general background to the area.

The classic definition of the Möbius function, as given in Equation 2.1, is,
essentially, a recursive sum over the elements of the poset. This thesis, in
general, restricts itself to this view. A simple consequence of the
fundamental definition is Hall’s Theorem [50, Proposition 3.8.5] which defines
the Möbius function as a sum over the chains in the poset. There are, however,
other ways in which we can understand the Möbius function, and in order to
provide a broad background, we briefly describe two of them here.

####  3.2.1 Simplicial complexes

Given a set of vertices $V$, a _simplicial complex_ $\Delta$ is a non-empty
set of subsets of $V$ such that if $v\in V$, then $\\{v\\}\in\Delta$; and if
$G\in\Delta$, and $F\subset G$, then $F\in\Delta$. If $F\in\Delta$, then we
say that $F$ has dimension $\left\lvert F\right\rvert-1$. We then refer to $F$
as a _face_ of $V$. Note that the empty subset $\emptyset$ is a face of $V$.
If we have two elements of a poset $\sigma$ and $\pi$, with $\sigma<\pi$, and
$(\sigma,\pi)$ is non-empty, then we can set $V$ to be the set of chains in
the open interval $(\sigma,\pi)$, and this gives a simplicial complex
$\Delta$. Given a simplicial complex $\Delta$, the reduced Euler
characteristic of $\Delta$, $\chi(\Delta)$ is defined as

$\chi(\Delta)=\sum_{k=-1}^{\operatorname{Dim}\Delta}(-1)^{k}f_{k}(\Delta),$

where $f_{k}(\Delta)$ is the number of faces of dimension $k$. If we have a
poset $P$ with unique minimal and maximal elements $\hat{0}$ and $\hat{1}$
respectively, and set $\Delta$ to be the chains in the open interval
$(\hat{0},\hat{1})$, then Hall’s Theorem (see, for example, Stanley [50,
Proposition 3.8.5] or Wachs [53, Proposition 1.2.6]) gives us that
$\mu[P]=\chi(\Delta)$.

Since a simplicial complex is a topological entity, in addition to the
possibility of using the Möbius function to determine the value of the reduced
Euler characteristic, it is possible to pose questions about the topology of
the poset. While this approach has been taken in some papers (discussed in
Section 3.4 below), this thesis does not use this approach or provide any
topological results. The interested reader is referred to the material in [53]
for further details.

####  3.2.2 Incidence algebras and incidence matrices

A poset $P$ is _locally finite_ if, for every $\sigma,\pi\in P$, the interval
$[\sigma,\pi]$ has a finite number of elements. Following Rota [36], we define
an _incidence algebra_ by first taking a locally finite partially ordered set
$P$, and considering the set of all real-valued functions $f(x,y)$, where
$x,y\in P$ and $f(x,y)=0$ if $x\not\leq y$. We then define the incidence
algebra of $P$ by convolution:

$(f*g)(x,y)=\sum_{x\leq z\leq y}f(x,z)g(z,y).$

This algebra has an identity element, normally written as $\delta(x,y)$, which
is defined as

$\delta(x,y)=\begin{cases}1&\text{If }x=y\\\ 0&\text{Otherwise}.\end{cases}$

The _zeta function_ is defined as

$\zeta(x,y)=\begin{cases}1&\text{If }x\leq y\\\
0&\text{Otherwise}.\end{cases}$

With these definitions, it can be shown that the Möbius function is the
convolutional inverse of $\zeta$, so

$\zeta*\mu(x,y)=\mu*\zeta(x,y)=\delta(x,y).$

Let $Z$ be a square matrix, with rows and columns indexed by the elements of a
poset $P$, and with $Z_{x,y}=\zeta(x,y)$. We call this the _zeta matrix_ of
$P$. It is now possible to show that if $x$ and $y$ are elements of the poset,
then

$\mu[x,y]=(Z^{-1})_{x,y}.$

We remark here that the result above implies that we can determine the value
of the Möbius function for every interval in a poset by (simply) calculating
the inverse of the zeta matrix. We have some computational evidence that using
the “matrix inverse” method to determine the value of the Möbius function for
a significant number of intervals in a poset is computationally more efficient
than using the fundamental definition given in Equation 2.1. On the other
hand, if we want to determine the value of the Möbius function for a single
interval, then the fundamental definition seems to be significantly faster
than the matrix inverse method. Of course, our ideal is to find methods that
can determine the value of the Möbius function faster than either the matrix
inverse method, or using the fundamental definition.

###  3.3 The Möbius function for general posets

Before we move on to consider the Möbius function of the permutation poset
under classic pattern containment, we divert slightly to review some results
relating to the Möbius function on other posets. We start by remarking that,
for a general poset, using the recursive definition of the Möbius function is
computationally hard. Our purpose in this section is to establish that
determining the Möbius function need not be computationally hard in some
cases. We refer the reader to [27] for a good overview of most of the
containment types discussed in this section.

There are some well-known cases where an explicit formula exists for the
Möbius function. For example, the Möbius function on a Boolean algebra is
given by $\mu[R,S]=(-1)^{\\#(S-R)}$ (see, for instance, Example 3.8.3 in
[50]).

A slightly more complex example is given by the poset of subspaces of a vector
space $V\subseteq GF(q)^{n}$. If we have $U\subseteq W\subseteq V$, then

$\mu[U,W]=(-1)^{k}q^{\binom{k}{2}},\text{ where }k=\dim(W)-\dim(U).$

This result is attributed to Hall in Rota [36]. The poset of subspaces of a
vector space is an example of a lattice, and the proof given in Rota utilises
this fact. The Möbius function for general lattices is also well-known (see,
for instance, Section 3.9 in [50]).

We now turn to posets that are defined by free monoids over alphabets, or by
permutations using a containment other than classic pattern containment.

Björner completely determined the Möbius function of subword order in [7], and
then completely determined the Möbius function for factor order in [8].

Sagan and Vatter, in [39], considered ordered partitions (compositions) of an
integer, with a partial order given by subwords, and completely determined the
Möbius function on this poset. This paper also has the first result for the
permutation poset under classic pattern containment, which we discuss in
Section 3.4.

Bernini, Ferrari and Steingrímsson, in [6], considered permutations using
consecutive pattern containment. For most intervals $[\sigma,\pi]$ they have a
set of explicit formulae for $\mu[\sigma,\pi]$, based mainly on how many times
$\sigma$ occurs in $\pi$. For intervals not covered by their formulae, they
provide a polynomial algorithm to calculate the Möbius function. We consider
that the Möbius function of permutations under consecutive pattern containment
is, therefore, completely known. Sagan and Willenbring, in [40], reproduced
this result using a technique known as discrete Morse theory.

Bernini and Ferrari, in [5], introduced the quasi-consecutive pattern poset of
permutations, where $\sigma$ is contained in $\pi$ if $\pi$ contains an
occurrence of $\sigma$ where all entries are adjacent, except possibly the
first and second. They completely determine the Möbius function for any
interval $[\sigma,\pi]$ where $\sigma$ occurs exactly once in $\pi$.

A recent preprint by Bernini, Cervetti, Ferrari and Steingrímsson [4]
considers the poset of Dyck paths, where we say that a path $P$ contains a
path $Q$ if the steps in $Q$ are a subsequence of the steps in $P$. The
preprint includes expressions for the Möbius function of some specific
intervals in this poset.

The posets discussed so far are, in some way, simpler than the permutation
poset under classic pattern containment, and we have seen that the Möbius
function has either been completely determined, or, as in the last two
examples, has been determined for a particular subset of intervals in the
poset. We now consider posets that, in some sense, generalize classic pattern
containment.

Mesh patterns are a generalization of classic pattern containment on
permutations, and the poset of mesh patterns contains the poset of
permutations as an induced subposet. We refer the reader to [11] for a formal
definition of mesh patterns. In [49], Smith and Ulfarsson present some initial
results on the Möbius function of the mesh pattern poset, and show that as
$n\to\infty$, the proportion of mesh patterns $p$ of length $n$ with
$\mu[1^{\emptyset},p]=0$ approaches 1, where $1^{\emptyset}$ is the unshaded
singleton mesh pattern. The mesh pattern $1^{\emptyset}$ corresponds to the
permutation $1$ in the induced poset of permutations. In the permutation
pattern poset, we know [2] that the number of simple permutations of length
$n$ is, asymptotically, $\frac{n!}{\mathrm{e}^{2}}$, and it is generally
believed that for most simple permutations the value of the principal Möbius
function is non-zero, thus in the permutation pattern poset we do not expect
the proportion of permutations $\pi$ of length $n$ with $\mu[\pi]=0$ to
approach 1.

Smith generalised pattern containment in [48], and found some explicit
formulae for the Möbius function. These formulae have the general form

$\mu[\sigma,\pi]=(-1)^{\left\lvert\pi\right\rvert-\left\lvert\sigma\right\rvert}E(\sigma,\pi)+\sum_{\lambda\in[\sigma,\pi)}\mu[\sigma,\lambda]\mu[\hat{P}(\lambda,\pi)],$

where $E(\sigma,\pi)$ counts specific types of embeddings of $\sigma$ into
$\pi$, and $\hat{P}(\lambda,\pi)$ is a poset derived from the interval
$[\lambda,\pi]$.

Although this last example does have a complete characterisation of the Möbius
function on all intervals of the poset, from a computational perspective the
result is only useful if, outside the result given, we can show that the
second term is zero. This result is a generalisation of some of the results
given by Smith in [46], which we discuss in the following section.

###  3.4 The Möbius function of the permutation poset under pattern
containment

The study of the Möbius function in the (classic) permutation poset was
introduced by Wilf [54], who wrote

> We can partially order the set of all permutations of all numbers of letters
> by declaring that $\sigma\leq\tau$ if $\sigma$ is contained as a pattern in
> $\tau$. It would be interesting to study this as a poset. For example, what
> can be said about its Möbius function?

The first result in this area was by Sagan and Vatter [39]. Their paper
primarily concerns itself with the Möbius function of a composition poset. An
integer composition can be thought of as an ordered list of positive integers,
and a layered permutation can be completely specified by such a list, so there
is a bijection between integer compositions and layered permutations. From
this it follows that there is a bijection between the poset of compositions of
integers and the poset of layered permutations. In the final section of their
paper, they use this bijection to essentially give an expression for the
Möbius function on intervals in the poset of layered permutations under
classic pattern containment.

Steingrímsson and Tenner [52] found a large class of pairs of permutations
$(\sigma,\pi)$ where $\mu[\sigma,\pi]=0$. They show that the (poset) interval
$[\sigma,\pi]$ has $\mu[\sigma,\pi]=0$ if $\pi$ contains a non-trivial
interval where none of the elements of the (permutation) interval are part of
an embedding of $\sigma$ into $\pi$. They also show that if there is exactly
one embedding of $\sigma$ into $\pi$, and the complement of the embedding
satisfies certain conditions, then $\mu[\sigma,\pi]\in\\{0,\pm 1\\}$.

In a seminal paper, Burstein, Jelínek, Jelínková and Steingrímsson [18] found
a recursion for the Möbius function for sum/skew decomposable permutations in
terms of the sum/skew indecomposable permutations in the lower and upper
bounds. They also found a method to determine the Möbius function for
separable permutations by counting embeddings. The recursions for decomposable
permutations are used extensively in this thesis.

McNamara and Steingrímsson [33] investigated the topology of intervals in the
permutation poset, and in doing so found a single recurrence equivalent to the
recursions in [18].

We now compare the recursions from Burstein et al [18] with those from
McNamara and Steingrímsson [33]. The recursions from Burstein, Jelínek,
Jelínková and Steingrímsson [18] can be written as follows.

> ######  Proposition 2 (McNamara and Steingrímsson [33, Proposition 8.3],
> following Burstein, Jelínek, Jelínková and Steingrímsson [18, Proposition
> 1]).
>
> Let $\sigma$ and $\pi$ be non-empty permutations with finest decompositions
> $\sigma=\sigma_{1}\oplus\ldots\oplus\sigma_{s}$ and
> $\pi=\pi_{1}\oplus\ldots\oplus\pi_{t}$, where $t\geq 2$. Suppose that
> $\pi_{1}=1$. Let $k\geq 1$ be the largest integer such that all the
> components $\pi_{1},\ldots,\pi_{k}$ are equal to 1, and let $\ell\geq 0$ be
> the largest integer such that all the components
> $\sigma_{1},\ldots,\sigma_{\ell}$ are equal to 1. Then
>
> $\mu[\sigma,\pi]=\begin{cases}0&\text{if $k-1>\ell$,}\\\
> -\mu[\sigma_{>k-1},\pi_{>k}]&\text{if $k-1=\ell$,}\\\
> \mu[\sigma_{>k},\pi_{>k}]-\mu[\sigma_{>k-1},\pi_{>k}]&\text{if
> $k-1<\ell$.}\end{cases}$
>
> The remaining case is $\pi_{1}>1$, and is covered by the next proposition.
>
> ######  Proposition 3 (McNamara and Steingrímsson [33, Proposition 8.4],
> following Burstein, Jelínek, Jelínková and Steingrímsson [18, Proposition
> 2]).
>
> Let $\sigma$ and $\pi$ be non-empty permutations with finest decompositions
> $\sigma=\sigma_{1}\oplus\ldots\oplus\sigma_{s}$ and
> $\pi=\pi_{1}\oplus\ldots\oplus\pi_{t}$, where $t\geq 2$. Suppose that
> $\pi_{1}>1$. Let $k\geq 1$ be the largest integer such that all the
> $\pi_{1},\ldots,\pi_{k}$ are equal to $\pi_{1}$. Then
> $\mu[\sigma,\pi]=\sum_{i=1}^{s}\sum_{j=1}^{k}\mu[\sigma_{\leq
> i},\pi_{1}]\mu[\sigma_{>i},\pi_{>j}].$

The recursion found by McNamara and Steingrímsson can be written as follows.

> ######  Proposition 4 (McNamara and Steingrímsson [33, Proposition 8.1]).
>
> Consider permutations $\sigma$ and $\pi$ and let
> $\pi=\pi_{1}\oplus\ldots\oplus\pi_{t}$ be the finest decomposition of $\pi$.
> Then
>
>
> $\mu[\sigma,\pi]=\sum_{\sigma=\varsigma_{1}\oplus\ldots\oplus\varsigma_{t}}\prod_{1\leq
> m\leq t}\begin{cases}\mu[\varsigma_{m},\pi_{m}]+1&\text{If
> $\varsigma_{m}=\epsilon$ and $\pi_{m-1}=\pi_{m}$,}\\\
> \mu[\varsigma_{m},\pi_{m}]&\text{otherwise, }\end{cases}$
>
> where the sum is over all direct sums
> $\sigma=\varsigma_{1}\oplus\ldots\oplus\varsigma_{t}$, such that
> $\epsilon\leq\varsigma_{m}\leq\pi_{m}$ for all $1\leq m\leq t$.

We remark here that the recursion from McNamara and Steingrímsson is, in some
sense, a nicer recursion than that found by Burstein, Jelínek, Jelínková and
Steingrímsson. Despite this, in this thesis we use the Burstein et al
recursions as these are easier to work with in the context of our results.

Smith [44] found an explicit formula for the Möbius function on the interval
$[1,\pi]$ for all permutations $\pi$ with a single descent. Smith [45] has
explicit expressions for the Möbius function $\mu[\sigma,\pi]$ when $\sigma$
and $\pi$ have the same number of descents. In [46], Smith found an expression
that determines the Möbius function for all intervals in the poset. The main
result is

$\displaystyle\mu[\sigma,\pi]$
$\displaystyle=(-1)^{\left\lvert\pi\right\rvert-\left\lvert\sigma\right\rvert}\mathrm{NE}(\sigma,\pi)+\sum_{\lambda\in[\sigma,\pi)}\mu[\sigma,\lambda]\sum_{S\in
EZ^{\lambda,\pi}}(-1)^{\left\lvert S\right\rvert}$ (3.1)

where $\mathrm{NE}(\sigma,\pi)$ is the number of normal embeddings of $\sigma$
into $\pi$, and $EZ^{\lambda,\pi}$ is a set of sets of embeddings of $\lambda$
into $\pi$ that satisfy a particular condition.

One view of this result is that it tells us that the value of the Möbius
function on an interval $[\sigma,\pi]$ is given by the number of normal
embeddings of $\sigma$ into $\pi$, plus a correction factor. Smith notes [46,
Remark 22] that 95% of intervals with $\left\lvert\pi\right\rvert\leq 8$ have
$\mu[\sigma,\pi]=(-1)^{\left\lvert\pi\right\rvert-\left\lvert\sigma\right\rvert}\mathrm{NE}(\sigma,\pi)$,
so in these cases the correction factor is zero.

Smith remarks [46, Remark 23] that where we can show that

$\sum_{\lambda\in[\sigma,\pi)}\mu[\sigma,\lambda]\sum_{S\in
EZ^{\lambda,\pi}}(-1)^{\left\lvert S\right\rvert}=0,$

the normal embedding approach can determine the value of the Möbius function
in polynomial time, whereas using the recursive formula of Equation 2.1 is
exponential complexity.

One approach to showing that
$\sum_{\lambda\in[\sigma,\pi)}\mu[\sigma,\lambda]\sum_{S\in
EZ^{\lambda,\pi}}(-1)^{\left\lvert S\right\rvert}=0$ would be to find
permutations $\sigma$ and $\pi$ such that for any $\lambda\in[\sigma,\pi)$,
$EZ^{\lambda,\pi}$ is empty, as this would force the second term to be zero.
Some small-scale experiments by the author suggest that it is significantly
more likely that some of the sets $EZ^{\lambda,\pi}$ are non-empty, and
therefore when $\sum_{\lambda\in[\sigma,\pi)}\mu[\sigma,\lambda]\sum_{S\in
EZ^{\lambda,\pi}}(-1)^{\left\lvert S\right\rvert}=0$ it is likely to be
because, taken across every $\lambda\in[\sigma,\pi)$, the number of sets in
$EZ^{\lambda,\pi}$ with even order is the same as the number of sets with odd
order.

Brignall and Marchant [16] showed that if the lower bound of an interval is
indecomposable, then the Möbius function depends only on the indecomposable
permutations contained in the upper bound. They then used this result to find
a fast polynomial algorithm for computing $\mu[\pi]$ where $\pi$ is an
increasing oscillation. This paper forms the basis of Chapter 4 of this
thesis.

Brignall, Jelínek, Kynčl and Marchant [15] prove that if a permutation $\pi$
contains opposing adjacencies, then $\mu[\pi]=0$. They then use this to show
that the proportion of permutations of length $n$ with principal Möbius
function equal to zero is asymptotically bounded below by $(1-1/e)^{2}\geq
0.3995$. This paper forms the basis of Chapter 5 of this thesis.

Jelínek, Kantor, Kynčl and Tancer [25] show how to construct a sequence of
permutations $\pi_{n}$ with length $2n+2$, and they show that for $n\geq 2$,

$\mu[\pi_{n}]=-\binom{n+2}{7}-\binom{n+1}{7}+2\binom{n+2}{5}-\binom{n+2}{3}-\binom{n}{2}-2n,$

and thus demonstrate that the absolute value of the Möbius function grows
according to the seventh power of the length. In their paper they also show
that if $f:[\sigma,\pi]\to\mathbb{R}$ is any function satisfying $f(\pi)=1$,
then

$\mu[\sigma,\pi]=f(\sigma)-\sum_{\lambda\in[\sigma,\pi)}\mu[\sigma,\lambda]\sum_{\tau\in[\lambda,\pi]}f(\tau)$

and as a corollary, they then show that

$\mu[\sigma,\pi]=(-1)^{\left\lvert\pi\right\rvert-\left\lvert\sigma\right\rvert}\mathrm{E}(\sigma,\pi)-\sum_{\lambda\in[\sigma,\pi)}\mu[\sigma,\lambda]\sum_{\tau\in[\lambda,\pi]}(-1)^{\left\lvert\pi\right\rvert-\left\lvert\tau\right\rvert}\mathrm{E}(\tau,\pi),$

where $\mathrm{E}(\alpha,\beta)$ is the number of embeddings of $\alpha$ into
$\beta$. We note that the formula in the corollary has a similar structure to
Equation 3.1 described above, although in general it suffers from the same
restrictions as Smith’s equation.

Finally, Marchant [31] showed how to construct a sequence of permutations
$\pi_{1}$, $\pi_{2}$, $\pi_{3},\ldots$ with lengths $n,n+4,n+8,\ldots$ such
that $\mu[1,\pi_{i+1}]=2\mu[1,\pi_{i}]$, and this gives us that the growth of
the principal Möbius function on the permutation poset is exponential. This
paper forms the basis of Chapter 6 of this thesis.

###  3.5 Motivation

It seems reasonably clear that the Möbius function of the permutation poset
under classic pattern containment is a non-trivial problem. This contrasts
with some of the posets described in 3.3, where the Möbius function is
completely determined.

As we have described, the study of the permutation poset under classic pattern
containment was initiated by Wilf in 2002 in [54]. Anecdotally, Wilf is
believed to have later said that the Möbius function on the permutations
pattern poset was “A mess. Don’t touch it”.

We state here that we think that Wilf’s reported view is somewhat pessimistic.
While we think that it is unlikely that there is a polynomial-time procedure
for computing the value of the Möbius on an arbitrary interval of the
permutation poset, we believe, and we hope to show in this thesis, that there
is considerable scope for further research in this area.

The permutation pattern poset is the subject of considerable research activity
outside of the Möbius function, and we claim that the permutation pattern
poset is the underlying object for many studies related to patterns in
permutations. This then means that research into the Möbius function on the
permutation pattern poset may lead to a better understanding of this poset,
and hence to results in other areas related to permutation patterns.

We can summarise our motivation for research in this area by saying that the
Möbius function of the permutation poset under classic pattern containment is
not well-understood, and indeed up until recently the proportion of
permutations where we had a (computationally) simple way to determine the
value of the principal Möbius function was, asymptotically, zero.

The paper which forms the basis of Chapter 5 shows that, asymptotically, the
proportion of permutations where the principal Möbius function is zero is at
least 0.3995. The corollary to this result, however, is that we do not yet
have an effective means to compute the principal Möbius function for 60% of
all permutations.

Further, research into the Möbius function on the permutation pattern poset
may lead to a better understanding of the intrinsic properties of the poset,
which in turn may lead to results in related areas.

##  Chapter 4 The Möbius function of permutations with an indecomposable lower
bound

###  4.1 Preamble

This chapter is based on a published paper [16], which is joint work with
Robert Brignall.

In this chapter, we show that the Möbius function of an interval in a
permutation poset where the lower bound is sum (resp. skew) indecomposable
depends solely on the sum (resp. skew) indecomposable permutations contained
in the upper bound, and that this can simplify the calculation of the Möbius
sum. For increasing oscillations, we give a recursion for the Möbius sum which
only involves evaluating simple inequalities.

###  4.2 Introduction

Recall that the Möbius function on a poset interval $[\sigma,\pi]$ is defined
by

$\displaystyle\mu[\sigma,\pi]$ $\displaystyle=\begin{cases}1&\text{if
$\sigma=\pi$,}\\\
-\sum_{\lambda\in[\sigma,\pi)}\mu[\sigma,\lambda]&\text{otherwise.}\end{cases}$
(4.1)

Our motivation for this chapter is to find a _contributing set_
$\mathfrak{C}_{\sigma,\pi}$ that is significantly smaller than the poset
interval $[\sigma,\pi)$, and a $\\{0,\pm 1\\}$ weighting function
$W(\sigma,\alpha,\pi)$ such that

$\displaystyle\mu[\sigma,\pi]$
$\displaystyle=-\sum_{\alpha\in\mathfrak{C}_{\sigma,\pi}}\mu[\sigma,\alpha]W(\sigma,\alpha,\pi).$
(4.2)

Plainly, in Equation 4.2, we could set
$\mathfrak{C}_{\sigma,\pi}=[\sigma,\pi)$, and $W(\sigma,\alpha,\pi)=1$, which
is equivalent to Equation 4.1.

One approach here would be to take a permutation $\beta$ such that
$\sigma<\beta<\pi$. We could then set
$\mathfrak{C}_{\sigma,\pi}=\\{\lambda:\lambda\in[\sigma,\pi)\text{ and
}\lambda\not\in[\sigma,\beta]\\}$, and $W(\sigma,\alpha,\pi)=1$, since, from
Equation 4.1, $\sum_{\lambda\in[\sigma,\beta]}\mu[\sigma,\lambda]=0$. This
approach was used in Smith [44], who determined the Möbius function on the
interval $[1,\pi]$ for all permutations $\pi$ with a single descent. Smith’s
paper is unusual, in that it provides an explicit formula for the value of the
Möbius function.

Our approach is different. We identify individual elements (say $\lambda$), of
the poset that have $\mu[\sigma,\lambda]=0$. We also show that there are pairs
of elements, $\lambda$ and $\lambda^{\prime}$, where
$\mu[\sigma,\lambda]=-\mu[\sigma,\lambda^{\prime}]$, and so we can exclude
these pairs of elements. Finally, we show that there are quartets of
permutations $\lambda_{1},\ldots,\lambda_{4}$ where
$\sum_{i=1}^{4}\mu[\sigma,\lambda_{i}]=0$; and that we can systematically
identify these quartets. By excluding these permutations from
$\mathfrak{C}_{\sigma,\pi}$ we can significantly reduce the number of elements
in $\mathfrak{C}_{\sigma,\pi}$ compared to the number of elements in the
interval $[\sigma,\pi)$. This approach results in the ability to compute
$\mu[\sigma,\pi]$, where $\sigma$ is indecomposable, much faster than
evaluating Equation 4.1. For increasing oscillations, we will show that the
elements of $\mathfrak{C}_{\sigma,\pi}$ can be determined using simple
inequalities, and that as a consequence $\mu[\sigma,\pi]$ can be determined
using inequalities. With this approach, we have computed $\mu[1,\pi]$, where
$\pi$ is an increasing oscillation, up to
$\left\lvert\pi\right\rvert=\text{2,000,000}$.

Our main tool in the first part of this chapter comes from the results of
Burstein, Jelínek, Jelínková and Steingrímsson [18]. They found a recursion
for the Möbius function for sum/skew decomposable permutations in terms of the
sum/skew indecomposable permutations in the lower and upper bounds. They also
found a method to determine the Möbius function for separable permutations by
counting embeddings. We use the recursions for decomposable permutations to
underpin the first part of this chapter.

In this chapter we show that the Möbius function on intervals with a sum
indecomposable lower bound depends only on the sum indecomposable permutations
contained in the upper bound. We provide a weighting function that determines
which sum indecomposable permutations contribute to the Möbius sum. We then
consider increasing oscillations. For these permutations, we show how we can
find all of the permutations that contribute to the Möbius sum by applying
simple numeric inequalities, which leads to a fast polynomial algorithm for
determining the Möbius function.

We start with some essential definitions and notation relevant to this chapter
in Section 4.3, then in Section 4.4 we provide a number of preliminary lemmas.
We conclude this section with a theorem that gives $\mu[\sigma,\pi]$, where
$\sigma$ is a sum indecomposable permutation, for all $\pi$. In Section 4.5 we
consider $\mu[\sigma,\pi]$ where $\sigma$ is a sum indecomposable permutation,
and $\pi$ is an increasing oscillation. We finish with some concluding remarks
in Section 4.6.

###  4.3 Definitions and notation

When discussing the Möbius function,
$\mu[\sigma,\pi]=-\sum_{\lambda\in[\sigma,\pi)}\mu[\sigma,\lambda]$, we will
frequently be examining the value of $\mu[\sigma,\lambda]$ for a specific
permutation $\lambda$. We say that this is the _contribution_ that $\lambda$
makes to the sum. If we have a set of permutations $S\subseteq[\sigma,\pi)$
such that $\sum_{\lambda\in S}\mu[\sigma,\lambda]=0$, then we say that the set
$S$ makes _no net contribution_ to the sum.

The _interleave_ of two permutations $\alpha$ and $\beta$ is formed by taking
the sum $\alpha\oplus\beta$, and then exchanging the value of the largest
point from $\alpha$ with the value of the smallest point from $\beta$. We can
also view this as increasing the largest point from $\alpha$ by 1, and
simultaneously decreasing the smallest point from $\beta$ by 1. We write an
interleave as $\alpha\obslash\beta$. For example, $321\obslash 213=421536$,
see Figure 4.1.

For completeness, we also define a _skew interleave_ , $\alpha\oslash\beta$,
which is formed by taking the skew sum $\alpha\ominus\beta$, and then
exchanging the smallest point from $\alpha$ with the largest point from
$\beta$. As an example, $321\oslash 213=653214$, as shown in Figure 4.1.

The interleave operations, $\obslash$ and $\oslash$, are not associative, as
$1\obslash 1\obslash 1$ could represent $231$ or $312$. To avoid this
ambiguity, we require that the permutation $1$ can either be interleaved to
the left or to the right, but not both. It is easy to see that this
restriction establishes associativity. We note here that, with this
restriction, an expression involving $\oplus$ and $\obslash$ represents a
unique permutation regardless of the order in which the operations are
applied.

Let $\alpha$ be a permutation with length greater than 1. We will frequently
want to refer to permutations that have the form
$\alpha\obslash\alpha\obslash\ldots\obslash\alpha\obslash\alpha$. If there are
$n$ copies of $\alpha$ being interleaved, then we will write this as
$\obslash^{n}\alpha$, so, for example, we have $\obslash^{3}(21)=21\obslash
21\obslash 21=315264$.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$ $321\oplus 213$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$ $321\ominus 213$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$ $321\obslash 213$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$ $321\oslash 213$

Figure 4.1: Examples of direct and skew sums and interleaves.

For the remainder of this chapter, by symmetry it suffices to discuss
permutations in relation to sums and interleaves only. For the same reason,
references to (in)decomposable permutations may omit the “sum” qualifier.

The _increasing oscillating sequence_ is the sequence

$4,1,6,3,8,5,10,7,\ldots,2k+2,2k-1,\ldots.$

The start of the sequence is depicted in Figure 4.2.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
Figure 4.2: A depiction of the start of the increasing oscillating sequence.

An _increasing oscillation_ is a simple permutation contained in the
increasing oscillating sequence. For lengths greater than three, there are
exactly two increasing oscillations of each length. Let $W_{n}$ be the
increasing oscillation with $n$ elements which starts with a descent, and let
$M_{n}$ be the increasing oscillation with $n$ elements which starts with an
ascent. Then

$\displaystyle W_{2n}$ $\displaystyle=\obslash^{n}21,$ $\displaystyle M_{2n}$
$\displaystyle=1\obslash\left(\obslash^{n-1}21\right)\obslash 1,$
$\displaystyle W_{2n-1}$ $\displaystyle=\left(\obslash^{n-1}21\right)\obslash
1,\qquad\text{and}$ $\displaystyle M_{2n-1}$
$\displaystyle=1\obslash\left(\obslash^{n-1}21\right).$

Note that $W_{n}=M_{n}^{-1}$.

There are instances where, for some permutation $\alpha$, we are interested in
the set of permutations $\\{\alpha,\;1\oplus\alpha,\;\alpha\oplus
1,\;1\oplus\alpha\oplus 1\\}$. Given a permutation $\alpha$, we refer to this
set as $\mathcal{F}_{\oplus}(\alpha)$, and we say that this set is the
_family_ of $\alpha$. If $S$ is a set of permutations, then
$\mathcal{F}_{\oplus}(S)=\cup_{\alpha\in
S}\\{\mathcal{F}_{\oplus}(\alpha)\\}$.

There are also some instances where we are interested in the set of
permutations
$\mathcal{F}_{\obslash}(\alpha)=\\{\alpha,\;1\obslash\alpha,\;\alpha\obslash
1,\;1\obslash\alpha\obslash 1\\}$. Note that every increasing oscillation is
an element of $\mathcal{F}_{\obslash}(\obslash^{k}21)$ for some $k\geq 1$.

###  4.4 Preliminary lemmas and main theorem

In this section our aim is to show that if $\sigma$ is indecomposable, then
for any $\pi\geq\sigma$ there is a $\\{0,\pm 1\\}$ weighting function
$W(\sigma,\alpha,\pi)$ and a set of permutations $\mathfrak{C}_{\sigma,\pi}$,
such that

$\mu[\sigma,\pi]=-\sum_{\alpha\in\mathfrak{C}_{\sigma,\pi}}\mu[\sigma,\alpha]W(\sigma,\alpha,\pi).$

If $\pi$ is the identity permutation $1,2,\ldots,n$ or its reverse, then
$\mu[\sigma,\pi]$ is trivial for any $\sigma$, and we exclude the identity and
its reverse from being the upper bound of any interval under consideration.

As noted earlier, our approach is to show that there are permutations, pairs
of permutations, and quartets of permutations in $[\sigma,\pi)$ that make no
net contribution to the sum.

We use Proposition 1 and 2, and Corollary 3 from Burstein, Jelínek, Jelínková
and Steingrímsson [18]. Note that we have already introduced these
propositions on page 2, but we repeat them here for ease of use. We start with
some required notation. If $\pi$ is a non-empty permutation with decomposition
$\pi_{1}\oplus\ldots\oplus\pi_{n}$, then for any integer $i$ with $0\leq i\leq
n$, $\pi_{\leq i}$ is the permutation $\pi_{1}\oplus\ldots\oplus\pi_{i}$, and
$\pi_{>i}$ is the permutation $\pi_{i+1}\oplus\ldots\oplus\pi_{n}$. An empty
sum of permutations is defined as $\varepsilon$, and in particular $\pi_{\leq
0}=\pi_{>n}=\varepsilon$. We can see that $\mu[\varepsilon,\varepsilon]=1$,
$\mu[\varepsilon,1]=-1$ and $\mu[\varepsilon,\tau]=0$ for any $\tau>1$. We now
recall the results from Burstein, Jelínek, Jelínková and Steingrímsson:

######  Proposition 5 (Burstein, Jelínek, Jelínková and Steingrímsson [18,
Proposition 1]).

Let $\sigma$ and $\pi$ be non-empty permutations with decompositions
$\sigma=\sigma_{1}\oplus\ldots\oplus\sigma_{m}$ and
$\pi=\pi_{1}\oplus\ldots\oplus\pi_{n}$, with $n\geq 2$. Assume that
$\pi_{1}=1$, and let $k$ be the largest integer such that
$\pi_{1},\pi_{2},\ldots,\pi_{k}$ are all equal to $1$. Let $l\geq 0$ be the
largest integer such that $\sigma_{1},\sigma_{2},\ldots,\sigma_{l}$ are all
equal to $1$. Then

$\displaystyle\mu[\sigma,\pi]$ $\displaystyle=\begin{cases*}0&\text{if
$k-1>l$,}\\\ -\mu[\sigma_{>k-1},\pi_{>k}]&\text{if $k-1=l$,}\\\
\mu[\sigma_{>k},\pi_{>k}]-\mu[\sigma_{>k-1},\pi_{>k}]&\text{if
$k-1<l$.}\end{cases*}$

######  Proposition 6 ([18, Proposition 2]).

Let $\sigma$ and $\pi$ be non-empty permutations with decompositions
$\sigma=\sigma_{1}\oplus\ldots\oplus\sigma_{m}$ and
$\pi=\pi_{1}\oplus\ldots\oplus\pi_{n}$, with $n\geq 2$. Assume that
$\pi_{1}\neq 1$, and let $k$ be the largest integer such that
$\pi_{1},\pi_{2},\ldots,\pi_{k}$ are all equal to $\pi_{1}$. Then

$\displaystyle\mu[\sigma,\pi]$
$\displaystyle=\sum_{i=1}^{m}\sum_{j=1}^{k}\mu[\sigma_{\leq
i},\pi_{1}]\mu[\sigma_{>i},\pi_{>j}].$

######  Corollary 7 ([18, Corollary 3]).

Let $\sigma$ and $\pi$ be as in Proposition 6. Suppose that $\sigma$ is sum
indecomposable, so $m=1$. Then

$\displaystyle\mu[\sigma,\pi]$
$\displaystyle=\begin{cases*}\mu[\sigma,\pi_{1}]&\text{if
$\pi=\oplus^{k}\pi_{1}$,}\\\ -\mu[\sigma,\pi_{1}]&\text{if
$\pi=\left(\oplus^{k}\pi_{1}\right)\oplus 1$,}\\\
0&\text{otherwise,}\end{cases*}$

A simple consequence of Propositions 5 and 6 is the identification of some
intervals of permutations where the value of the Möbius function is zero.

######  Lemma 8.

Let $\pi\in\\{1\oplus 1\oplus\tau,\tau\oplus 1\oplus
1,\mathcal{F}_{\oplus}(\left(\oplus^{r}\alpha\right)\oplus\tau^{\prime})\\}$,
where $\tau$ is any permutation, $r$ is maximal, $\alpha$ is sum
indecomposable, and $\tau^{\prime}$ is any permutation greater than $1$. Let
$\sigma$ be a sum indecomposable permutation. Then $\mu[\sigma,\pi]=0$.

###### Proof.

Consider $\pi=1\oplus 1\oplus\tau$. We use Proposition 5. If $\tau_{1}=1$,
then $k\geq 3$, and $l\leq 1$, and the result follows immediately. Now assume
that $\tau_{1}\neq 1$. Then $k=2$. If $\sigma>1$, then again the result
follows immediately. If $\sigma=1$, then we have
$\mu[\sigma,\pi]=-\mu[\sigma_{>k-1},\pi_{>k}]=-\mu[\varepsilon,\tau]=0$. The
case for $\pi=\tau\oplus 1\oplus 1$ follows by symmetry.

Now consider
$\pi=\mathcal{F}_{\oplus}(\left(\oplus^{r}\alpha\right)\oplus\tau^{\prime})$.
If $\pi=\left(\oplus^{r}\alpha\right)\oplus\tau$, or
$\pi=\left(\oplus^{r}\alpha\right)\oplus\tau\oplus 1$, then we use Proposition
6. In that context we have $m=1$ and $k=r$, and so
$\mu[\sigma,\pi]=\sum_{j=1}^{r}\mu[\sigma,\pi_{1}]\mu[\varepsilon,\pi_{>j}]$
For every value of $j$, $\pi_{>j}$ is non-empty and greater than $1$, and so
$\mu[\varepsilon,\pi_{>j}]=0$ for all $j$, and hence every term in the sum is
zero. If $\pi=1\oplus\left(\oplus^{r}\alpha\right)\oplus\tau$ or
$\pi=1\oplus\left(\oplus^{r}\alpha\right)\oplus\tau\oplus 1$, then we use
Proposition 5, which reduces to one of the previous cases. ∎

We now turn to identifying pairs and quartets of permutations that make no net
contribution to the Möbius sum. We start by showing that if $\sigma$ and
$\alpha$ are indecomposable, and $r\geq 1$, and with
$\pi\in\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$, then $\mu[\sigma,\pi]$ and
$\mu[\sigma,\alpha]$ have the same magnitude.

######  Lemma 9.

Let $\pi\in\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$, where $r\geq 1$ and
$\alpha>1$ is sum indecomposable. Let $\sigma$ be a sum indecomposable
permutation. Then

$\mu[\sigma,\pi]=\begin{cases*}\mu[\sigma,\alpha]&\text{if
$\pi=\oplus^{r}\alpha$\; or\; $1\oplus\left(\oplus^{r}\alpha\right)\oplus
1$},\\\ -\mu[\sigma,\alpha]&\text{if
$\pi=1\oplus\left(\oplus^{r}\alpha\right)$\; or\;
$\left(\oplus^{r}\alpha\right)\oplus 1$}.\end{cases*}$

As a consequence, if
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)\subseteq[\sigma,\pi)$, then
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$ makes no net contribution to
$\mu[\sigma,\pi]$.

###### Proof.

If $\pi=\oplus^{r}\alpha$ or $\pi=\left(\oplus^{r}\alpha\right)\oplus 1$, then
this is immediate from Corollary 7. If
$\pi=1\oplus\left(\oplus^{r}\alpha\right)$ or
$\pi=1\oplus\left(\oplus^{r}\alpha\right)\oplus 1$, then we use Proposition 5.

For the net contribution of $\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$,
$\sum_{\lambda\in\mathcal{F}_{\oplus}(\oplus^{r}\alpha)}\mu[\sigma,\lambda]=0$.
∎

We now have a lemma that adds a further restriction to the permutations that
have a non-zero contribution to the Möbius sum.

######  Lemma 10.

If $\sigma\leq\pi$, and $\alpha\in[\sigma,\pi]$ is sum indecomposable, and $r$
is the smallest integer such that $1\oplus\left(\oplus^{r}\alpha\right)\oplus
1\not\leq\pi$, then
$\mathcal{F}_{\oplus}(\oplus^{k}\alpha)\subseteq[\sigma,\pi)$ for all
$k\in[1,r)$.

###### Proof.

For any $k<r$,
$\sigma\leq\oplus^{k}\alpha<1\oplus\left(\oplus^{k}\alpha\right)\oplus
1\leq\pi$. Note that by Lemma 9 the net contribution of the family
$\mathcal{F}_{\oplus}(\oplus^{k}\alpha)$ to $\mu[\sigma,\pi]$ is zero. ∎

######  Observation 11.

Using the same terminology as Lemma 10, if $k>r+1$ then we must have
$\oplus^{k}\alpha\not\leq\pi$. As a consequence, for each indecomposable
$\alpha\in[\sigma,\pi]$, the only families of $\alpha$ that can have a non-
zero net contribution to $\mu[\sigma,\pi]$ are
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$ and
$\mathcal{F}_{\oplus}(\oplus^{r+1}\alpha)$.

We now eliminate two specific permutations from the Möbius sum.

######  Lemma 12.

If $\pi$ is any permutation with $\left\lvert\pi\right\rvert>3$ apart from the
identity permutation and its reverse, and $\sigma$ is sum indecomposable, then
the permutations $1$ and $1\oplus 1$ make no net contribution to the Möbius
sum $\mu[\sigma,\pi]$.

###### Proof.

If $\sigma=1$, then the interval contains both $1$ and $1\oplus 1$. Since
$\mu[1,1]=1$ and $\mu[1,12]=-1$, there is no net contribution to
$\mu[\sigma,\pi]$. If $\sigma>1$, then $\sigma\neq 12$, and so neither $1$ nor
$12$ is in the interval. ∎

Before we present the main theorem for this section, we formally define the
weight function and the contributing set. Let $\alpha$ be a sum indecomposable
permutation. The weight function, $W(\sigma,\alpha,\pi)$, is defined as

$\displaystyle W(\sigma,\alpha,\pi)$ $\displaystyle=\begin{cases*}1&If
$\left\\{\begin{array}[]{l}\sigma\leq\oplus^{r}\alpha\leq\pi\text{ and }\\\
1\oplus\left(\oplus^{r}\alpha\right)\not\leq\pi\text{ and }\\\
\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi,\end{array}\right.$\\\ -1&If
$\left\\{\begin{array}[]{l}\sigma\leq\oplus^{r}\alpha\leq\pi\text{ and }\\\
1\oplus\left(\oplus^{r}\alpha\right)\leq\pi\text{ and }\\\
\left(\oplus^{r}\alpha\right)\oplus 1\leq\pi\text{ and }\\\
\oplus^{r+1}\alpha\not\leq\pi,\end{array}\right.$\\\ 0&Otherwise,\end{cases*}$
(4.3)

where $r$ is the smallest integer such that
$1\oplus\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi$.

The contributing set $\mathfrak{C}_{\sigma,\pi}$ is defined as

$\displaystyle\mathfrak{C}_{\sigma,\pi}$
$\displaystyle=\left\\{\alpha:\begin{array}[]{l}\alpha\in[\sigma,\pi),\\\
\alpha\text{ is sum indecomposable, and }\\\ W(\sigma,\alpha,\pi)\neq
0\end{array}\right\\}.$

We have one last lemma before we move on to the main theorem.

######  Lemma 13.

If $\sigma$ and $\alpha$ are sum indecomposable, then for any permutation
$\pi$, $\mu[\sigma,\alpha]W(\sigma,\alpha,\pi)$ gives the contribution of the
set of families $\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$ to the Möbius sum,
where $r$ is any positive integer.

###### Proof.

By Observation 11, we only need consider the contribution made by
$\oplus^{r}\alpha$ and $\oplus^{r+1}\alpha$, where $r$ is the smallest integer
such that $1\oplus\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi$.

If $\sigma\not\leq\oplus^{r}\alpha$, or $\oplus^{r}\alpha\not\leq\pi$, then
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$ makes no net contribution to the
Möbius sum. Now assume that $\sigma\leq\oplus^{r}\alpha\leq\pi$. First, we can
see that if $1\oplus\left(\oplus^{r}\alpha\right)\not\leq\pi$, or
$\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi$ then
$\oplus^{r+1}\alpha\not\leq\pi$. We can also see that if
$1\oplus\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi$ then
$1\oplus\left(\oplus^{r+1}\alpha\right)\not\leq\pi$ and
$\oplus^{r+1}\alpha\not\leq\pi$. The possibilities remaining are itemised in
Table 4.1,

$1\oplus\left(\oplus^{r}\alpha\right)$ | $\left(\oplus^{r}\alpha\right)\oplus 1$ | $\oplus^{r+1}\alpha$ | Möbius contribution
---|---|---|---
$\leq\pi$ | $\leq\pi$ | $\leq\pi$ | $0$
$\leq\pi$ | $\leq\pi$ | $\not\leq\pi$ | $-\mu[\sigma,\alpha]$
$\leq\pi$ | $\not\leq\pi$ | $\not\leq\pi$ | $0$
$\not\leq\pi$ | $\leq\pi$ | $\not\leq\pi$ | $0$
$\not\leq\pi$ | $\not\leq\pi$ | $\not\leq\pi$ | $\mu[\sigma,\alpha]$
Table 4.1: Möbius contribution from family members.

where the Möbius contribution is determined by applying Lemma 9. We can see
that in every case $W(\sigma,\alpha,\pi)$ provides the correct weight for the
Möbius function $\mu[\sigma,\alpha]$. ∎

We are now in a position to present the main theorem for this section.

######  Theorem 14.

If $\sigma$ is a sum indecomposable permutation, and
$\left\lvert\pi\right\rvert>3$, then

$\mu[\sigma,\pi]=-\sum_{\alpha\in\mathfrak{C}_{\sigma,\pi}}\mu[\sigma,\alpha]W(\sigma,\alpha,\pi).$

###### Proof.

Let $\alpha\leq\pi$ be an indecomposable permutation.

Using Lemmas 8 and 12 we can see that any permutations not in the set
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$ can be excluded from
$\mathfrak{C}_{\sigma,\pi}$, as these permutations make no net contribution to
the Möbius sum.

For every $\alpha$, by Lemma 13, $\mu[\sigma,\alpha]W(\sigma,\alpha,\pi)$
provides the contribution to the Möbius sum of all families
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$, where $r$ is a positive integer. ∎

Theorem 14 reduces the number of permutations that need to be considered as
part of the Möbius sum. We can see that the largest permutation in
$\mathfrak{C}_{\sigma,\pi}$ must have length less than
$\left\lvert\pi\right\rvert$, and so we can apply Theorem 14 recursively to
the permutations in $\mathfrak{C}_{\sigma,\pi}$ to determine their Möbius
values. In this recursion, if we are attempting to determine
$\mu[\sigma,\lambda]$, we can stop if
$\left\lvert\sigma\right\rvert=\left\lvert\lambda\right\rvert$ or
$\left\lvert\sigma\right\rvert=\left\lvert\lambda\right\rvert-1$, as in these
cases $\mu[\sigma,\lambda]$ is $+1$ and $-1$ respectively.

###  4.5 Increasing oscillations

We now move on to increasing oscillations. Given an indecomposable permutation
$\sigma$, and an increasing oscillation $\pi$, our aim in this section is to
describe $\mathfrak{C}_{\sigma,\pi}$ in precise terms. We will find a sum for
the Möbius function, $\mu[\sigma,\pi]$, which only requires the evaluation of
simple inequalities.

If $\pi$ is an increasing oscillation with length less than 4, then
$\mu[\sigma,\pi]$ is trivial to determine for any $\sigma$. For the remainder
of this section we assume that $\pi$ has length at least 4.

We partition the set of increasing oscillations with length greater than 1
into five disjoint subsets. These subsets are $\\{21\\},\;$
$\\{\obslash^{{k+1}}21\\},\;$ $\\{1\obslash\left(\obslash^{k}21\right)\\},\;$
$\\{\left(\obslash^{k}21\right)\obslash 1\\},\;$ and
$\\{1\obslash\left(\obslash^{k}21\right)\obslash 1\\}$, where $k$ is a
positive integer. If two increasing oscillations are in the same subset, then
we say that they have the same _shape_.

We now determine what permutations contained in an increasing oscillation have
a non-zero contribution to the Möbius sum.

######  Lemma 15.

Let $\pi$ be an increasing oscillation, and let $\sigma\leq\pi$ be sum
indecomposable. Let $S$ be the subset of the permutations in the interval
$[\sigma,\pi)$ that can be written in the form
$\mathcal{F}_{\oplus}(\oplus^{r}\mathcal{F}_{\obslash}(\obslash^{k}21))$ for
some $k,r\geq 1$. If $\lambda\in[\sigma,\pi)$, and $\lambda\not\in S$, then
$\mu[\sigma,\lambda]=0$.

We note here that $\mathcal{F}_{\obslash}(\obslash^{k}21)$ is a set containing
only increasing oscillations.

###### Proof.

We start by showing that if $\pi$ is an increasing oscillation, and
$\lambda=\lambda_{1}\oplus\ldots\oplus\lambda_{m}\leq\pi$, where each
$\lambda_{i}$ is sum indecomposable, then every $\lambda_{i}$ is an increasing
oscillation. This is trivially true if $\lambda$ is itself an increasing
oscillation, thus it is sufficient to show that if $\lambda$ is an increasing
oscillation, then deleting a single point results in either an increasing
oscillation, or a permutation that is the sum of two increasing oscillations.

If $k=1$, then we can see that deleting a single point results in a
permutation with the required characteristic.

Now assume that $k>1$. Let $\lambda=1\obslash\left(\obslash^{k}21\right)$.
Deleting the leftmost point gives $\obslash^{k}21$, and deleting the rightmost
point gives $1\obslash\left(\obslash^{k-1}21\right)\oplus 1$. Deleting the
second point gives $21\oplus\left(\obslash^{k-1}21\right)$, and deleting the
last-but-one point gives $1\obslash\left(\obslash^{k-1}21\right)\obslash 1$.
Deleting any even point $2t$ except the second or second-to-last results in
$\left(1\obslash\left(\obslash^{t-1}21\right)\obslash
1\right)\oplus\left(\left(\obslash^{k-t}21\right)\right)$. Finally, deleting
any odd point $2t+1$ apart from the first or last results in
$\left(1\obslash\left(\obslash^{t-1}21\right)\right)\oplus\left(1\obslash\left(\obslash^{k-t}21\right)\right)$.
Thus if $\lambda=1\obslash\left(\obslash^{k}21\right)$, then deleting a single
point from $\lambda$ results in either an increasing oscillation, or a
permutation that is the sum of two increasing oscillations.

A similar argument applies to the other three cases, which we omit for
brevity.

To complete the proof, we now see that by Lemma 12, we can ignore $\lambda=1$
and $\lambda=1\oplus 1$. If
$\lambda=\lambda_{1}\oplus\lambda_{2}\oplus\ldots\oplus\lambda_{m}\leq\pi$,
then by the argument above, every $\lambda_{i}$ is an increasing oscillation.
Applying Lemma 8 completes the proof. ∎

Following Observation 11, it is clear that, if
$\alpha\in\mathcal{F}_{\obslash}(\obslash^{k}21)$, then for any family
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$, we only need consider the cases
$\oplus^{r}\alpha$ and $\oplus^{r+1}\alpha$ where $r$ is the smallest integer
such that $1\oplus\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi$.

Given some $\pi=W_{n}\text{ or }M_{n}$, we will find inequalities that relate
$n$, $r$ and $k$ and the shape of $\alpha$ that will allow us to find the
values that contribute to the Möbius sum. We know from Lemma 15 the shape of
the permutations that contribute to the Möbius sum. For each of the four types
of increasing oscillation ($W_{2n}$, $W_{2n-1}$, $M_{2n}$ and $M_{2n-1}$), we
can examine how each shape can be embedded so that the unused points at the
start of the increasing oscillation are minimised. Figure 4.3 shows examples
of embeddings into $W_{2n}$. This gives us an inequality relating to the start
of the embedding. Similarly, we can find inequalities for the end of the
embedding. We can also find inequalities that relate to the interior (when
$r>1$), and Figures 4.4 and 4.5 show examples of this. We can use these
inequalities to determine what values of $k$ will allow the shape to be
embedded. For each allowable value of $k$, we can then determine the maximum
value of $r$ such that $1\oplus\left(\oplus^{r}\alpha\right)\oplus
1\not\leq\pi$. This then means that, by evaluating inequalities alone, we can
identify the specific permutations that could contribute to the Möbius sum.

We first have two lemmas that examine inequalities at the start and end of an
embedding.

######  Lemma 16.

If $\pi$ is an increasing oscillation, and $\alpha\leq\pi$ is sum
indecomposable, then in any embedding of an element $\lambda$ of
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$ into $\pi$, the minimum number of
unused points at the start of $\pi$ depends on the start of $\lambda$, and on
$\pi$, and is as shown below:

Start of $\lambda$ | $\pi=W_{2n}$ | $\pi=W_{2n-1}$ | $\pi=M_{2n}$ | $\pi=M_{2n-1}$
---|---|---|---|---
$21\ldots$ | $0$ | $0$ | $0$ | $0$
$\obslash^{{k+1}}21\ldots$ | $0$ | $0$ | $1$ | $1$
$1\obslash\left(\obslash^{k}21\right)\ldots$ | $1$ | $1$ | $0$ | $0$
$1\oplus 21\ldots$ | $1$ | $1$ | $1$ | $1$
$1\oplus\left(\obslash^{{k+1}}21\right)\ldots$ | $1$ | $1$ | $2$ | $2$
$1\oplus 1\obslash\left(\obslash^{k}21\right)\ldots$ | $2$ | $2$ | $1$ | $1$

###### Proof.

It is clear that if we minimise the number of points at the start of an
embedding, then the number of unused points depends on $\pi$, and the start of
$\alpha$. The values in Lemma 16 are found by considering each of the
possibilities. We illustrate some of these cases in Figure 4.3.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
$\obslash^{4}21$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$
$1\obslash\left(\obslash^{3}21\right)$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$
$1\oplus\left(\obslash^{3}21\right)$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$$\bullet$$\circ$
$1\oplus 1\obslash\left(\obslash^{2}21\right)$

Figure 4.3: Embedding the start of $\alpha$ in $W_{2n}$.

∎

######  Lemma 17.

If $\pi$ is an increasing oscillation, and $\alpha\leq\pi$ is sum
indecomposable, then in any embedding of an element $\lambda$ of
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$ into $\pi$, the minimum number of
unused points at the end of $\pi$ depends on the end of $\lambda$, and on
$\pi$, and is as shown below:

End of $\lambda$ | $\pi=W_{2n}$ | $\pi=W_{2n-1}$ | $\pi=M_{2n}$ | $\pi=M_{2n-1}$
---|---|---|---|---
$\ldots 21$ | $0$ | $0$ | $0$ | $0$
$\ldots\obslash^{{k+1}}21$ | $0$ | $1$ | $1$ | $0$
$\ldots\left(\obslash^{k}21\right)\obslash 1$ | $1$ | $0$ | $0$ | $1$
$\ldots 21\oplus 1$ | $1$ | $1$ | $1$ | $1$
$\ldots\left(\obslash^{{k+1}}21\right)\oplus 1$ | $1$ | $2$ | $2$ | $1$
$\ldots\left(\obslash^{k}21\right)\obslash 1\oplus 1$ | $2$ | $1$ | $1$ | $2$

###### Proof.

We examine all the possibilities as we did in Lemma 16. ∎

We now consider how closely copies of some sum indecomposable $\alpha$ can be
embedded into $\pi$. This leads to two inequalities that relate $\alpha$,
$\pi$ and the maximum number of copies of $\alpha$ that can be embedded in
$\pi$. Where $\alpha\neq 21$, the shape of $\alpha$ fixes the way the two
copies can be embedded in an increasing oscillation. If $\alpha=21$, then we
will see that there are choices for the embedding.

######  Lemma 18.

If $\pi$ is an increasing oscillation, and $\alpha\neq 21$, and
$\alpha\leq\pi$ is sum indecomposable, then in any embedding of
$\oplus^{r}\alpha$ into $\pi$, the minimum number of points between the start
and end of $\oplus^{r}\alpha$ depends on $\alpha$, and is as shown below:

Shape of $\alpha$ |  Points in $\oplus^{r}\alpha$ | Unused points | Minimum points
---|---|---|---
$\obslash^{{k+1}}21$ | $2kr$ | $2r-2$ | $2kr+2r-2$
$1\obslash\left(\obslash^{k}21\right)$ | $2kr+r$ | $r-1$ | $2kr+2r-1$
$\left(\obslash^{k}21\right)\obslash 1$ | $2kr+r$ | $r-1$ | $2kr+2r-1$
$1\obslash\left(\obslash^{k}21\right)\obslash 1$ | $2kr+2r$ | $2r-2$ | $2kr+4r-2$

###### Proof.

If $r$ = 1, then there are no unused points, and so the minimum number of
points depends solely on the points in $\alpha$, and the table reflects this.

Assume now that $r>1$. If $\alpha\neq 21$, then we can see that the interleave
fixes the layout of each copy of $\alpha$, so we simply pack each copy as
close as possible. This packing clearly depends on the start and end of
$\alpha$, and it is simple to examine the four possibilities. Examples are
shown in Figure 4.4.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$$\bullet$$\circ$
$21\obslash 21\oplus$
$21\obslash 21$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$
$21\obslash 21\oplus$
$1\obslash 21\obslash 21$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$
$21\obslash 21\obslash 1\oplus$
$21\obslash 21$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$$\bullet$$\circ$
$21\obslash 21\obslash 1\oplus$
$1\obslash 21$

Figure 4.4: Packing $\alpha$ as close as possible when $\alpha\neq 21$.

∎

We now turn to the case where $\alpha=21$. This is more complex than the
previous cases. We can see that there must be at least one point between each
copy of $\alpha$. We can insert each copy of $21$ in two ways, one where the
points are horizontally adjacent, and one where the points are vertically
adjacent. These alternatives can be seen in Figure 4.5. Alternating these
means that there will be exactly one point between each copy of $\alpha$, so
this embedding minimises the number of points between the start and end of
$\oplus^{r}\alpha$. The complication in this case relates to how we start and
end the embedding. We illustrate this by showing, in Figure 4.5, maximal
embeddings where we are embedding into $W_{8}$, $W_{10}$ and $W_{12}$.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$$\bullet$$\circ$
$W_{8}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$$\bullet$$\circ$$\bullet$$\circ$$\bullet$$\circ$
$W_{10}$

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\circ$$\bullet$$\circ$$\bullet$$\circ$$\bullet$$\circ$
$W_{12}$

Figure 4.5: Examples of unused points when embedding $\oplus^{r}21$.

A detailed examination of each possible case gives us our second inequality.

######  Lemma 19.

If $\pi$ is an increasing oscillation, and $\alpha=21$ then for
$\oplus^{r}\alpha$ to be contained in $\pi$ we must have $3r-1\leq 2n$ for
$\pi\in\\{W_{2n},M_{2n}\\}$, and $3r\leq 2n$ for
$\pi\in\\{W_{2n-1},M_{2n-1}\\}$.

###### Proof.

In every case we start by embedding the first $21$ into the first two elements
of the permutation. Thereafter, we embed each successive $21$ as close as
possible to the preceding $21$. The minimum number of elements to embed $r$
copies of $21$ will be $2r$ elements to hold the points of the $21$s, and
$r-1$ intermediate empty elements. For $W_{2n}$ and $M_{2n}$, this then gives
$3r-1\leq 2n$, and for $W_{2n-1}$ and $M_{2n-1}$ we obtain $3r-1\leq 2n-1$. ∎

We now have a complete understanding of the number of points required to embed
any permutation that contributes to the Möbius sum into an increasing
oscillation. The following Lemma summarises the situation.

######  Lemma 20.

If $\pi$ is an increasing oscillation, and
$\alpha\in\mathcal{F}_{\obslash}(\obslash^{k}21)\leq\pi$ (so $\alpha$ is sum
indecomposable), then for $\oplus^{r}\alpha$ to be contained in $\pi$, the
inequality in the table below must be satisfied, where $k\geq 1$.

$\pi$xxxxxxx |  Shape of $\alpha$xxxxxxx | Inequality
---|---|---
$W_{2n},M_{2n}$xxxxxxx |  $21$xxxxxxx | $3r-1\leq 2n$
$W_{2n-1},M_{2n-1}$xxxxxxx |  $21$xxxxxxx | $3r\leq 2n$
$W_{2n}$xxxxxxx |  $\obslash^{{k+1}}21$xxxxxxx | $2kr+2r-2\leq 2n$
$W_{2n-1}$xxxxxxx |  $1\obslash\left(\obslash^{k}21\right)$xxxxxxx | $2kr+2r+2\leq 2n$
$M_{2n-1}$xxxxxxx |  $\left(\obslash^{k}21\right)\obslash 1$xxxxxxx | $2kr+2r+2\leq 2n$
$M_{2n}$xxxxxxx |  $1\obslash\left(\obslash^{k}21\right)\obslash 1$xxxxxxx | $2kr+4r-2\leq 2n$
$W_{2n},W_{2n-1},M_{2n-1}$xxxxxxx |  $1\obslash\left(\obslash^{k}21\right)\obslash 1$xxxxxxx | $2kr+4r\leq 2n$
All other cases | $2kr+2r\leq 2n$

###### Proof.

We apply Lemmas 16, 17, 18 and 19 to the possibilities for $\pi$ and $\alpha$.
∎

As a consequence of Lemmas 16 and 17 we can define a relationship between the
minimum number of points required to embed some $\oplus^{r}\alpha$, and the
minimum number of points required to embed
$1\oplus\left(\oplus^{r}\alpha\right)$, $\oplus^{r}\alpha\oplus 1$ and
$1\oplus\left(\oplus^{r}\alpha\right)\oplus 1$.

######  Corollary 21.

If $\pi$ is an increasing oscillation, and $\alpha\leq\pi$ is sum
indecomposable and if the minimum number of points required to embed
$\oplus^{r}\alpha$ into $\pi$ is $C$, then the minimum number of points
required to embed $1\oplus\left(\oplus^{r}\alpha\right)$ into $\pi$ is $C+2$,
the minimum number of points required to embed $\oplus^{r}\alpha\oplus 1$ into
$\pi$ is $C+2$, and the minimum number of points required to embed
$1\oplus\left(\oplus^{r}\alpha\right)\oplus 1$ into $\pi$ is $C+4$.

###### Proof.

We can see from Lemmas 16 and 17 that adding $1\oplus{}$ at the start of a
permutation increases the number of points required by two – one for the new
point, and one that is unused. Similarly, adding ${}\oplus 1$ at the end
increases the points required by two. ∎

Lemma 20 gives us inequalities that any $\oplus^{r}\alpha$ must satisfy to
ensure that $\oplus^{r}\alpha\leq\pi$. Further, Corollary 21 gives us
inequalities that, for a given $\oplus^{r}\alpha$ allow us to determine if
$1\oplus\left(\oplus^{r}\alpha\right)\leq\pi$,
$\left(\oplus^{r}\alpha\right)\oplus 1\leq\pi$ and
$1\oplus\left(\oplus^{r}\alpha\right)\oplus 1\leq\pi$. We can therefore
determine what values of $r$ and $k$ will result in
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$ contributing to the Möbius function.
We now consider inequalities that relate $\sigma$ and $\alpha$, so that we can
determine if $\sigma\leq\alpha$ using an inequality.

######  Lemma 22.

If $\sigma>1$ is an increasing oscillation, and
$\alpha\in\mathcal{F}_{\obslash}(\obslash^{k}21)$ for some $k$, then for
$\sigma$ to be contained in $\alpha$ the inequality in the table below must be
satisfied, where $k\geq 1$.

$\sigma$xxxxxxx |  Shape of $\alpha$xxxxxxx | Inequality
---|---|---
$W_{2n-1},M_{2n},M_{2n-1}$xxxxxxx |  $21$xxxxxxx | False
$W_{2n-1}$xxxxxxx |  $\left(\obslash^{k}21\right)\obslash 1$xxxxxxx | $k\geq n-1$
$M_{2n-1}$xxxxxxx |  $1\obslash\left(\obslash^{k}21\right)$xxxxxxx | $k\geq n-1$
$W_{2n-1},M_{2n},M_{2n-1}$xxxxxxx |  $1\obslash\left(\obslash^{k}21\right)\obslash 1$xxxxxxx | $k\geq n-1$
$M_{2n}$xxxxxxx |  $\obslash^{{k+1}}21$xxxxxxx | $k\geq n+1$
All other cases | $k\geq n$

###### Proof.

We examine all possible cases. ∎

We are now nearly ready to present the main theorem for this section.
Informally, for each possible shape of permutation $\alpha$, we will first
find the minimum and maximum values of $k$ such that
$\sigma\leq\alpha\leq\pi$, as any other values of $k$ result in $\alpha$ being
outside the interval. For each $\alpha$ and each $k$, we then determine the
minimum value of $r$ such that $1\oplus\left(\oplus^{r}\alpha\right)\oplus
1\not\leq\pi$. We can then use this value of $r$ (assuming it is non-zero) to
determine the weight to be applied to $\mu[\sigma,\alpha]$. The set of
$\alpha$’s with a non-zero weight is a contributing set
$\mathfrak{C}_{\sigma,\pi}$. At this point we can substitute a value for any
$\mu[\sigma,\alpha]$ where
$\left\lvert\sigma\right\rvert\leq\left\lvert\alpha\right\rvert-1$. We then
use the same process recursively to determine the contributing set for the
remaining elements of $\mathfrak{C}_{\sigma,\pi}$.

We first define some supporting functions. Let
$\operatorname{RawMinK}(\sigma,\alpha)$ be the minimum value of $k$ that
satisfies the inequality in Lemma 22. For the first inequality, which is
always false, we set $k=\left\lvert\pi\right\rvert$, as this will force the
sum, defined later in Theorem 23, to be empty.

Let $\operatorname{MinK}(\sigma,\alpha)$ be defined as

$\displaystyle\operatorname{MinK}(\sigma,\alpha)$
$\displaystyle=\begin{cases*}1&If $\sigma=1$ and
$\alpha\neq\obslash^{{k+1}}21$,\\\ 2&If $\sigma=1$ and
$\alpha=\obslash^{{k+1}}21$,\\\
\operatorname{RawMinK}(\sigma,\alpha)&otherwise.\end{cases*}$

Observe that for any $k<\operatorname{MinK}(\sigma,\alpha)$, we have
$\alpha<\sigma$, and so $\mathcal{F}_{\oplus}(\oplus^{k}\alpha)$ makes no net
contribution to the Möbius sum.

Let $\operatorname{MaxK}(\alpha,\pi)$ be defined as the maximum value of $k$
that satisfies the inequality in Lemma 20, if the shape of $\alpha$ and the
shape of $\pi$ are different; and one less than the maximum value of $k$ that
satisfies the inequality if the shape of $\alpha$ and the shape of $\pi$ are
the same. For the first two inequalities, which do not involve $k$, we set
$\operatorname{MaxK}(\alpha,\pi)=1$ if the inequality is satisfied, and
$\operatorname{MaxK}(\alpha,\pi)=0$ if not. Observe here that for any
$k>\operatorname{MaxK}(\alpha,\pi)$ we have $\alpha\not<\pi$, and so
$\mathcal{F}_{\oplus}(\oplus^{k}\alpha)$ makes no contribution to the Möbius
sum.

We define the weight function for increasing oscillations,
$W_{io}(\sigma,\alpha,\pi)$, as

$\displaystyle W_{io}(\sigma,\alpha,\pi)$ $\displaystyle=\begin{cases*}1&If
$\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi,$\\\ -1&If
$\left(\oplus^{r}\alpha\right)\oplus 1\leq\pi\text{ and
}\oplus^{r+1}\alpha\not\leq\pi,$\\\ 0&Otherwise,\end{cases*}$

where $r$ is the smallest integer such that
$1\oplus\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi$. These conditions
are simpler than those given in the weight function (4.3) for Theorem 14 as,
by Corollary 21, if $\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi$ then
$1\oplus\left(\oplus^{r}\alpha\right)\not\leq\pi$ and vice-versa. Furthermore,
we will see that this weight function is only used when
$\sigma\leq\oplus^{r}\alpha\leq\pi$.

We are now in a position to state our main theorem for this section. In this
theorem, we consider the contribution to the Möbius sum of each possible shape
of some sum indecomposable $\alpha$. There are five possible shapes, and,
given that the expression for each shape is identical, we abuse notation
slightly by writing our theorem as a sum over the shapes, thus the first sum
in Theorem 23 is over the possible shapes of $\alpha$, where four of the
shapes have a parameter $k$. For each shape, the limits on the interior sum
determine the minimum and maximum values of $k$, using the summation variable
$v$. We use the notation $\alpha_{v}$ to represent the actual permutation that
has the shape $\alpha$, where the parameter $k$ has been set to the value of
$v$. As an example, if $\alpha=1\obslash\left(\obslash^{k}21\right)$, and
$v=2$, then $\alpha_{v}=1\obslash\left(\obslash^{2}21\right)=24153$.

######  Theorem 23.

Let $\pi$ be an increasing oscillation, and let $\sigma\leq\pi$ be sum
indecomposable. Then

$\displaystyle\mu[\sigma,\pi]$ $\displaystyle=\sum_{\alpha\in\mathcal{S}}\
\sum_{v=\operatorname{MinK}(\sigma,\alpha)}^{\operatorname{MaxK}(\alpha,\pi)}\mu[\sigma,\alpha_{v}]W_{io}(\sigma,\alpha_{v},\pi)$

where the first sum is over the possible shapes of a sum indecomposable
permutation contained in an increasing oscillation, so $\mathcal{S}=\\{21,\;$
$\obslash^{{k+1}}21,\;$ $1\obslash\left(\obslash^{k}21\right),\;$
$\left(\obslash^{k}21\right)\obslash 1,\;$
$1\obslash\left(\obslash^{k}21\right)\obslash 1\\}$.

###### Proof.

By Lemma 15 the only sum-decomposable permutations contained in an increasing
oscillation that contribute to the Möbius sum are
$\mathcal{F}_{\oplus}(\oplus^{r}\alpha)$, where $\alpha\in\mathcal{S}$.

If we set $r=1$, then for each $\alpha$ in $\mathcal{S}$ Lemma 22 provides the
smallest value of $k$ such that $\sigma\leq\alpha$. If there is no such value
of $k$, then we use $\left\lvert\pi\right\rvert$, as the maximum value of $k$
must be smaller than this, and so the sum is empty.

Again setting $r=1$, for each $\alpha$ in $\mathcal{S}$ Lemma 20 provides the
maximum value of $k$ such that $\alpha\leq\pi$. If there is no value of $k$
that satisfies the inequality, then we set
$\operatorname{MaxK}(\alpha,\pi)=0$, thus forcing the sum to be empty.

Thus the permutations $\alpha_{v}$ in the sum

$\sum_{\alpha\in\mathcal{S}}\
\sum_{v=\operatorname{MinK}(\sigma,\alpha)}^{\operatorname{MaxK}(\alpha,\pi)}$

are those that could contribute to the Möbius sum, and for any $\alpha_{v}$
not included in the sum, $\mathcal{F}_{\oplus}(\oplus^{r}\alpha_{v})$ has a
zero contribution to the Möbius sum for any $r$.

Further, we can see from the construction method that any $\alpha_{v}$
included in the sum has $\sigma\leq\oplus^{r}\alpha_{v}\leq\pi$ for at least
one value of $r$, as if this was not the case, then we would have
$\operatorname{MinK}(\sigma,\alpha)>\operatorname{MaxK}(\alpha,\pi)$, and so
the sum would be empty.

We have therefore shown that the $\alpha_{v}$-s included in the sum form a
contributing set, and we could therefore set $\mathfrak{C}_{\sigma,\pi}$ to be
those $\alpha_{v}$-s, and use Theorem 14. We now show that the increasing
oscillation weight function $W_{io}(\sigma,\alpha,\pi)$ is equivalent to
$W(\sigma,\alpha,\pi)$ as defined in the general case.

By Corollary 21, if $\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi$ then
$1\oplus\left(\oplus^{r}\alpha\right)\not\leq\pi$ and vice-versa, and so the
condition for $\left(\oplus^{r}\alpha\right)\oplus 1$ also covers
$1\oplus\left(\oplus^{r}\alpha\right)$. As discussed above, we know that there
is at least one value of $r$ such that $\sigma\leq\oplus^{r}\alpha\leq\pi$,
and so $W_{io}(\sigma,\alpha,\pi)$ does not need to include this condition.
Thus the increasing oscillation weight function $W_{io}(\sigma,\alpha,\pi)$ is
equivalent to $W(\sigma,\alpha,\pi)$ as defined in the general case. ∎

####  4.5.1 Example of Theorem 23

As an example of Theorem 23 in action, we show how to determine

$\mu[3142,315274968]=\mu[\obslash^{2}21,\obslash^{4}21\obslash 1].$

We start by considering each possible shape of $\alpha$, setting $r=1$, and
then using the inequalities in Lemmas 20 and 22 to determine the minimum and
maximum values of $k$. This gives us

Shape of $\alpha$ | Minimum $k$ | Maximum $k$
---|---|---
$21$ | 1 | 1
$\obslash^{k}21$ | 2 | 4
$1\obslash\left(\obslash^{k}21\right)$ | 2 | 3
$\left(\obslash^{k}21\right)\obslash 1$ | 2 | 3
$1\obslash\left(\obslash^{k}21\right)\obslash 1$ | 2 | 3

For each shape of $\alpha$, and each value of $k$, we then use the
inequalities in Lemma 20 to determine the minimum value of $r$ such that
$1\oplus\left(\oplus^{r}\alpha\right)\oplus 1\not\leq\pi$, and we then
calculate the weight using this value of $r$. This gives

$\alpha$ | $r$ | Weight
---|---|---
$21$ | No possibilities
$\obslash^{2}21$ | $2$ | $1$
$\obslash^{3}21$ | $1$ | $-1$
$\obslash^{4}21$ | $1$ | $-1$
$1\obslash\left(\obslash^{2}21\right)$ | $1$ | $-1$
$1\obslash\left(\obslash^{3}21\right)$ | $1$ | $-1$
$\left(\obslash^{2}21\right)\obslash 1$ | $2$ | $1$
$\left(\obslash^{3}21\right)\obslash 1$ | $1$ | $-1$
$1\obslash\left(\obslash^{2}21\right)\obslash 1$ | $1$ | $-1$
$1\obslash\left(\obslash^{3}21\right)\obslash 1$ | $1$ | $-1$

This leads to the following initial expression:

$\displaystyle\mu[\obslash^{2}21,\obslash^{4}21\obslash 1]=$
$\displaystyle\mu[\obslash^{2}21,\obslash^{2}21]-\mu[\obslash^{2}21,\obslash^{3}21]-\mu[\obslash^{2}21,\obslash^{4}21]$
$\displaystyle-\mu[\obslash^{2}21,1\obslash\left(\obslash^{2}21\right)]-{}\mu[\obslash^{2}21,1\obslash\left(\obslash^{3}21\right)]$
$\displaystyle+\mu[\obslash^{2}21,\obslash^{2}21\obslash
1]-\mu[\obslash^{2}21,\obslash^{3}21\obslash 1]$
$\displaystyle-\mu[\obslash^{2}21,1\obslash\left(\obslash^{2}21\right)\obslash
1]-\mu[\obslash^{2}21,1\obslash\left(\obslash^{3}21\right)\obslash 1]$

We know that $\mu[\obslash^{2}21,\obslash^{2}21]=1$, and that

$\mu[\obslash^{2}21,1\obslash\left(\obslash^{2}21\right)]=\mu[\obslash^{2}21,\obslash^{2}21\obslash
1]=-1.$

Applying Theorem 23 recursively to the other intervals eventually yields

$\mu[\obslash^{2}21,\obslash^{4}21\obslash 1]=-6.$

###  4.6 Concluding remarks

The results in [18] provide two recurrences to handle the case where $\pi$ is
decomposable. This work handles the case where $\sigma$ is indecomposable. It
overlaps with [18] when $\sigma$ is indecomposable and $\pi$ is decomposable.
This leaves the case where $\sigma$ is decomposable and $\pi$ is
indecomposable for further investigation.

We can see that by symmetry $\mu[\sigma,W_{n}]=\mu[\sigma^{-1},M_{n}]$. If we
consider the value of the principal Möbius function, $\mu[1,\pi]$, where $\pi$
is either $W_{n}$ or $M_{n}$, then it is simple to show that the absolute
value of the principal Möbius function is bounded above by $2^{n}$. The weight
function for increasing oscillations can be $\pm 1$, and we can see no obvious
reason why there should not be two distinct values, $i$ and $j$, with the same
parity, such that the signs of $\mu[1,W_{i}]$ and $\mu[1,W_{j}]$ were
different. We have experimental evidence, based on the values of $W_{n}$ and
$M_{n}$ for $n=1\ldots\text{2,000,000}$ that suggests that $\mu[1,W_{2n}]<0$,
and that $\mu[1,W_{2n-1}]>0$.

Figure 4.6 is a log-log plot of the values of $-\mu[1,W_{2n}]$ from
$n=\text{8,000}$ to $n=\text{10,000}$. As can be seen, there seems to be some
evidence that the values fall into distinct bands, and we have confirmed that
this pattern continues up to $n=\text{1,000,000}$. Examination of the values
of $\mu[1,W_{2n-1}$] reveals the same patterns.

$8{,}000$$9{,}000$$10{,}000$$4\cdot 10^{8}$$10^{9}$$n$$-\mu[1,W_{2n}]$ Figure
4.6: Log-Log plot of $\left\lvert W_{2n}\right\rvert$.

Following discussions at Permutation Patterns 2017, Vít Jelínek [24] provided
the following conjecture (rephrased to reflect our notation).

######  Conjecture 24 (Jelínek [24]).

Let $M(n)$ denote the absolute value of the Möbius function
$\mu[1,W_{n}]=\mu[1,M_{n}]$. Then for $n>50$ we have

$\displaystyle M(2n)$ $\displaystyle=n^{2}\Longleftrightarrow\text{$n+1$ is
prime and $n\equiv 0\allowbreak\mkern 10.0mu({\operator@font mod}\,\,6)$}$
$\displaystyle M(2n)$ $\displaystyle=n^{2}-1\Longleftrightarrow\text{$n+1$ is
prime and $n\equiv 4\allowbreak\mkern 10.0mu({\operator@font mod}\,\,6)$}$
$\displaystyle M(2n+1)$ $\displaystyle=n^{2}-n\Longleftrightarrow\text{$n+1$
is prime and $n\equiv 0\allowbreak\mkern 10.0mu({\operator@font mod}\,\,6)$}$
$\displaystyle M(2n+1)$ $\displaystyle=n^{2}-n-1\Longleftrightarrow\text{$n+1$
is prime and $n\equiv 4\allowbreak\mkern 10.0mu({\operator@font mod}\,\,6)$}$

Further, Jelínek notes that there does not seem to be any other small constant
$k$ such that $M(n)=(n^{2}-k)/4$ infinitely often.

We also have the following conjecture relating to the banding of the values.

######  Conjecture 25.

Let $M(n)$ denote the absolute value of the Möbius function
$\mu[1,W_{n}]=\mu[1,M_{n}]$. Let $E(n)=M(n)/(n^{2})$, and let
$O(n)=M(n)/(n^{2}+n)$. Then, with $n\geq 1$, there exist constants
$0<a<b<c<d<e<f<g<1$ such that

$\displaystyle E(12n+10)$ $\displaystyle\in[a,b]$ $\displaystyle O(12n+11)$
$\displaystyle\in[a,b]$ $\displaystyle E(12n+2)$ $\displaystyle\in[c,d]$
$\displaystyle O(12n+3)$ $\displaystyle\in[c,d]$ $\displaystyle E(12n+6)$
$\displaystyle\in[c,d]$ $\displaystyle O(12n+7)$ $\displaystyle\in[c,d]$
$\displaystyle E(12n+4)$ $\displaystyle\in[e,f]$ $\displaystyle O(12n+5)$
$\displaystyle\in[e,f]$ $\displaystyle E(12n+8)$ $\displaystyle\in[g,1]$
$\displaystyle O(12n+9)$ $\displaystyle\in[g,1]$ $\displaystyle E(12n)$
$\displaystyle\in[g,1]$ $\displaystyle O(12n+1)$ $\displaystyle\in[g,1]$

Examining the first 2,000,000 values of $\mu[1,W_{n}]$ gives the following
estimates for the constants.

$\begin{array}[]{ccccccc}a&b&c&d&e&f&g\\\
0.615&0.680&0.692&0.760&0.821&0.896&0.923\end{array}$

The _complete nearly-layered_ permutations are formed by interleaving
descending permutations. Formally, a complete nearly-layered permutation has
the form

$\alpha_{1}\obslash\alpha_{2}\obslash\ldots\obslash\alpha_{k-1}\obslash\alpha_{k}$

where each $\alpha_{i}$ is a descending permutation, with $\alpha_{i}>1$ for
$i=2,\ldots,k-1$. If we set $\alpha_{i}=21$ for $i=2,\ldots,k-1$, and
$\alpha_{1},\alpha_{k}\in\\{1,21\\}$, then we obtain the increasing
oscillations.

The computational approach taken for increasing oscillations could, we think,
be adapted to complete nearly-layered permutations. It is clear that the
equivalent of the inequalities in Lemmas 20 and 22 would be somewhat more
complex than those found here, but we believe that it should be possible to
define an algorithm that could determine the Möbius function for complete
nearly-layered permutations where the lower bound is sum indecomposable.

###  4.7 Chapter summary

We started this chapter by saying that our motivation was to find a
contributing set $\mathfrak{C}_{\sigma,\pi}$ that is significantly smaller
than the poset interval $[\sigma,\pi)$, and a $\\{0,\pm 1\\}$ weighting
function $W(\sigma,\alpha,\pi)$ such that

$\displaystyle\mu[\sigma,\pi]$
$\displaystyle=-\sum_{\alpha\in\mathfrak{C}_{\sigma,\pi}}\mu[\sigma,\alpha]W(\sigma,\alpha,\pi).$

Our results are, essentially, computational. By this we mean that if $\sigma$
is indecomposable, then Theorem 14 can be used to compute the value of the
Möbius function on an interval $[\sigma,\pi]$ with less computational
resources than that required by the standard recursion of Equation 2.1. During
the preparation of this thesis the author generated 1000 random permutations
with length 14, then determined the poset $[1,\pi)$ defined by the random
permutation ($\pi$), and then counted the permutations in the poset, the sum-
indecomposable permutations in the poset, and the skew-indecomposable
permutations in the poset. The details are summarised in Table 4.2.

Average number of … | Value
---|---
Permutations | 3373
Sum-indecomposable permutations | 2492
Skew-indecomposable permutations | 2445
Table 4.2: Statistics for 1000 posets $[1,\pi)$ defined by a random
permutation of length 14, with figures rounded to the nearest integer.

These statistics seem to indicate that the improvement, at least for small
intervals, does not seem to be as significant as the author hoped. With
hindsight this is not unexpected. The proportion of permutations that are sum
or skew decomposable tends to zero as the length of the permutation increases,
from which one can readily deduce that the proportion of strongly
indecomposable permutations must tend to 1 as the length of the permutation
increases. This essentially means that the size of the contributing set
$\mathfrak{C}_{\sigma,\pi}$ is likely to be only slightly smaller than the
size of the overall poset.

The author wrote a computer program, Permutation WorkShop (PWS) [32], which
can be used to investigate the Möbius function on the permutation poset. The
author found that the overhead of identifying which permutations were in the
contributing set $\mathfrak{C}_{\sigma,\pi}$, and the overhead of calculating
$W(\sigma,\alpha,\pi)$ meant that, in general, calculations for permutations
with an indecomposable lower bound took longer than using the standard
recursive definition in Equation 2.1. This observation is, however, limited to
the way in which PWS operates, and, indeed, the hardware it runs on. We
suspect, however, that this observation is likely to be applicable to other
routines that calculate the Möbius function on the permutation poset.

Despite the comments above, we still feel that the overall approach of finding
a contributing set and a weighting function so that we can write

$\mu[\sigma,\pi]=-\sum_{\alpha\in\mathfrak{C}_{\sigma,\pi}}\mu[\sigma,\alpha]W(\sigma,\alpha,\pi).$

is valid, and indeed, although it is not phrased in these terms, the results
in Chapter 6 use this method successfully.

By contrast, when we consider intervals $[\sigma,\pi]$ where $\pi$ is an
increasing oscillation, we find that the number of indecomposable permutations
contained in $W(n)$ or $M(n)$ is, apart from trivial values of $\pi$, no
greater than $2n-4$, and this upper bound is only achieved when $\sigma=1$.
This is because any indecomposable permutation contained in an increasing
oscillation must itself be a (smaller) increasing oscillation, and there are
only two increasing oscillations of each length. It is well-known that, for
most intervals $[1,\pi]$, the number of permutations in the poset grows
exponentially as $\left\lvert\pi\right\rvert$ increases, and so we believe
that in this specific case we have indeed found a contributing set that is
significantly smaller than the poset. As supporting evidence for this claim,
we note that we were easily able to calculate $\mu[\pi]$ where $\pi$ was an
increasing oscillation with 2,000,000 elements.

This gave us the raw data to notice the banding shown in Figure 4.6, and led
to Conjecture 25. We are not aware of any other set of permutations with a
simple length-based construction where the values of the Möbius function fall
into bands as the length of the permutation(s) increase. The Möbius function
on the permutation pattern poset is, however, notoriously hard to compute in
general, so it is quite possible that such sets do exist, but we do not have
the understanding and/or the technology to be able to calculate values that
would exhibit banding.

We are not the only researchers to have considered the behaviour of
$\mu[W_{n}]$, and Conjecture 24 comes from a personal communication with Vít
Jelínek [24]. We have used our computations of $\mu[W_{n}]$ to confirm that
this conjecture holds for $50<n\leq\text{2,000,000}$.

We suspect that the banding behaviour in Conjecture 25 is a consequence of the
link with the prime numbers in Conjecture 24. While there are results that
give us expressions for the principal Möbius function value, we are not aware
of any result, whether relating to the value of the principal Möbius function,
or the growth of the principal Möbius function, where the result has a link to
the prime numbers. This suggest to us that one possible area for future
research would be to develop a better understanding of the behaviour of the
principal Möbius function of increasing oscillations. We would hope that if we
could find a relationship that accounted for the apparent link with prime
numbers, then we would also have a better understanding of the permutation
pattern poset.

##  Chapter 5 Zeros of the Möbius function of permutations

###  5.1 Preamble

This chapter is based on a published paper [15], which is joint work with
Robert Brignall, Vít Jelínek and Jan Kynčl.

In this chapter we show that if a permutation $\pi$ contains two intervals of
length 2, where one interval is an ascent and the other a descent, then the
Möbius function $\mu[1,\pi]$ of the interval $[1,\pi]$ is zero. As a
consequence, we prove that the proportion of permutations of length $n$ with
principal Möbius function equal to zero is asymptotically bounded below by
$(1-1/e)^{2}\geq 0.3995$. This is the first result determining the value of
$\mu[1,\pi]$ for an asymptotically positive proportion of permutations $\pi$.

We further establish other general conditions on a permutation $\pi$ that
ensure $\mu[1,\pi]=0$ including the occurrence in $\pi$ of any interval of the
form $\alpha\oplus 1\oplus\beta$.

###  5.2 Introduction

In this section we describe our principal results, and give an overview of the
previous work in this area. Formal definitions are given in the next section.

In this chapter, we are mainly concerned with the principal Möbius function.
We focus on the zeros of the principal Möbius function, that is, on the
permutations $\pi$ for which $\mu[\pi]=0$. We show that we can often determine
that a permutation $\pi$ is such a Möbius zero by examining small localities
of $\pi$. We formalize this idea using the notion of an “annihilator”.
Informally, an annihilator is a permutation $\alpha$ such that any permutation
$\pi$ containing an interval copy of $\alpha$ is a Möbius zero. We will
describe an infinite family of annihilators.

We will also prove that any permutation containing an increasing as well as a
decreasing interval of size 2 is a Möbius zero. Based on this result, we show
that the asymptotic proportion of Möbius zeros among the permutations of a
given length is at least $(1-1/e)^{2}\geq 0.3995$. This is the first known
result determining the values of the principal Möbius function for an
asymptotically positive fraction of permutations. We will also demonstrate how
our results on the principal Möbius function can be extended to intervals
whose lower bound is not $1$.

Burstein, Jelínek, Jelínková and Steingrímsson [18] found a recursion for the
Möbius function for sum and skew decomposable permutations. They used this to
determine the Möbius function for separable permutations. Their results for
sum and skew decomposable permutations implicitly include a result that only
concerns small localities, which is that, up to symmetry, if a permutation
$\pi$ of length greater than two begins $12$, then $\mu[\pi]=0$.

Smith [44] found an explicit formula for the Möbius function on the interval
$[1,\pi]$ for all permutations $\pi$ with a single descent. Smith’s paper
includes a lemma stating that if a permutation $\pi$ contains an interval
order-isomorphic to $123$, then $\mu[\pi]=0$. While the result in [18]
requires that the permutation starts with a particular sequence, Smith’s
result is, in some sense, more general, as the critical interval (123) can
occur in any position. Smith’s lemma may be viewed as the first instance of an
annihilator result. Our results on annihilators provide a common
generalization of Smith’s lemma and the above mentioned result of Burstein et
al. [18].

###  5.3 Definitions and notation

Recall that an _adjacency_ in a permutation is an interval of length two. If a
permutation contains a monotonic interval of length three or more, then each
subinterval of length two is an adjacency. As examples, $367249815$ has two
adjacencies, $67$ and $98$; and $1432$ also has two adjacencies, $43$ and
$32$. If an adjacency is ascending, then it is an _up-adjacency_ , otherwise
it is a _down-adjacency_.

If a permutation $\pi$ contains at least one up-adjacency, and at least one
down-adjacency, then we say that $\pi$ has _opposing adjacencies_. An example
of a permutation with opposing adjacencies is $367249815$, which is shown in
Figure 5.1.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
Figure 5.1: A permutation with opposing adjacencies.

A permutation that does not contain any adjacencies is _adjacency-free_. Some
early papers use the term “strongly irreducible” for what we call adjacency-
free permutations. See, for example, Atkinson and Stitt [3].

Given a permutation $\sigma$ of length $n$, and permutations
$\alpha_{1},\ldots,\alpha_{n}$, not all of them equal to the empty permutation
$\epsilon$, the _inflation_ of $\sigma$ by $\alpha_{1},\ldots,\alpha_{n}$,
written as $\sigma[\alpha_{1},\ldots,\alpha_{n}]$, is the permutation obtained
by removing the element $\sigma_{i}$ if $\alpha_{i}=\epsilon$, and replacing
$\sigma_{i}$ with an interval isomorphic to $\alpha_{i}$ otherwise. Note that
this is slightly different to the standard definition of inflation, originally
given in Albert and Atkinson [1], which does not allow inflation by the empty
permutation. As examples, $3624715[1,12,1,1,21,1,1]=367249815$, and
$3624715[\epsilon,1,1,\epsilon,1,\epsilon,1]=3142$.

In many cases we will be interested in permutations where most positions are
inflated by the singleton permutation $1$. If $\sigma=3624715$, then we will
write $\sigma[1,12,1,1,21,1,1]=367249815$ as $\sigma_{2,5}[12,21]$. Formally,
$\sigma_{i_{1},\ldots,i_{k}}[\alpha_{1},\ldots,\alpha_{k}]$ is the inflation
of $\sigma$ where $\sigma_{i_{j}}$ is inflated by $\alpha_{j}$ for
$j=1,\ldots,k$, and all other positions of $\sigma$ are inflated by $1$. When
using this notation, we always assume that the indices $i_{1},\dotsc,i_{k}$
are distinct; however, we make no assumption about their relative order.

Our aim is to study the Möbius function of the permutation poset, that is, the
poset of finite permutations ordered by containment. We are interested in
describing general examples of intervals $[\sigma,\pi]$ such that
$\mu[\sigma,\pi]=0$, with particular emphasis on the case $\sigma=1$. We say
that $\pi$ is a _Möbius zero_ (or just _zero_) if $\mu[\pi]=0$, and we say
that $\pi$ is a _$\sigma$ -zero_ if $\mu[\sigma,\pi]=0$.

It turns out that many sufficient conditions for $\pi$ to be a Möbius zero can
be stated in terms of inflations. We say that a permutation $\phi$ is an
_annihilator_ if every permutation that has an interval copy of $\phi$ is a
Möbius zero; in other words, for every $\tau$ and every $i\leq|\tau|$ the
permutation $\tau_{i}[\phi]$ is a Möbius zero. More generally, we say that
$\phi$ is a _$\sigma$ -annihilator_ if every permutation with an interval copy
of $\phi$ is a $\sigma$-zero.

We say that a pair of permutations $\phi$, $\psi$ is an _annihilator pair_ if
for every permutation $\tau$ and every pair of distinct indices
$i,j\leq|\tau|$, the permutation $\tau_{i,j}[\phi,\psi]$ is a Möbius zero.

Observe that for an annihilator $\phi$, any permutation containing an interval
copy of $\phi$ is also an annihilator. Likewise, if $\phi$ and $\psi$ form an
annihilator pair then any permutation containing disjoint interval copies of
$\phi$ and $\psi$ is an annihilator.

As our first main result, presented in Section 5.4, we show that the two
permutations $12$ and $21$ are an annihilator pair, or equivalently, any
permutation with opposing adjacencies is a Möbius zero. Later, in Section 5.6,
we use this result to prove that Möbius zeros have asymptotic density at least
$(1-1/e)^{2}$.

We also prove that for any two non-empty permutations $\alpha$ and $\beta$,
the permutation $\alpha\oplus 1\oplus\beta=123[\alpha,1,\beta]$ is an
annihilator, and generalize this result to a construction of
$\sigma$-annihilators for general $\sigma$. These results are presented in
Section 5.5.

Finally, in Section 5.7, we give several examples of annihilators and
annihilator pairs that do not directly follow from the results in the previous
sections.

####  5.3.1 Intervals with vanishing Möbius function

We will now present several basic facts about the Möbius function, which are
valid in an arbitrary finite poset. The first fact is a simple observation
following directly from the definition of the Möbius function, and we present
it without proof.

######  Fact 26.

Let $P$ be a finite poset with Möbius function $\mu_{P}$, and let $x$ and $y$
be two elements of $P$ satisfying $\mu_{P}[x,y]=0$. Let $Q$ be the poset
obtained from $P$ by deleting the element $y$, and let $\mu_{Q}$ be its Möbius
function. Then for every $z\in Q$, we have $\mu_{Q}[x,z]=\mu_{P}[x,z]$.

Next, we introduce two types of intervals whose specific structure ensures
that their Möbius function is zero.

Let $[x,y]$ be a finite interval in a poset $P$. We say that $[x,y]$ is
_narrow-tipped_ if it contains an element $z$ different from $x$ such that
$[x,y)=[x,z]$. The element $z$ is then called the _core_ of $[x,y]$.

We say that the interval $[x,y]$ is _diamond-tipped_ if there are three
elements $z$, $z^{\prime}$ and $w$, all different from $x$, and such that

  1. 1.

$[x,y)=[x,z]\cup[x,z^{\prime}]$ and

  2. 2.

$[x,z]\cap[x,z^{\prime}]=[x,w]$.

Condition 2 is equivalent to $w$ being the greatest lower bound of $z$ and
$z^{\prime}$ in the interval $[x,y]$. The triple of elements
$(z,z^{\prime},w)$ is again called the _core_ of $[x,y]$. Figure 5.2 shows
examples of narrow-tipped and diamond-tipped posets.

$y$$z$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$x$

$x$$\bullet$$\bullet$$\bullet$$w$$\bullet$$\bullet$$\bullet$$z^{\prime}$$z$$y$

Figure 5.2: Examples of narrow-tipped (left) and diamond-tipped (right)
posets.

######  Fact 27.

Let $P$ be a poset with Möbius function $\mu_{P}$, and let $[x,y]$ be a finite
interval in $P$. If $[x,y]$ is narrow-tipped or diamond-tipped, then
$\mu_{P}[x,y]=0$.

###### Proof.

If $[x,y]$ is narrow-tipped with core $z$, then

$\displaystyle\mu_{P}[x,y]=-\sum_{v\in[x,y)}\mu_{P}[x,v]=-\sum_{v\in[x,z]}\mu_{P}[x,v]=0.$

If $[x,y]$ is diamond-tipped with core $(z,z^{\prime},w)$ then

$\displaystyle\mu_{P}[x,y]$ $\displaystyle=-\sum_{v\in[x,y)}\mu_{P}[x,v]$
$\displaystyle=-\sum_{v\in[x,z]\cup[x,z^{\prime}]}\mu_{P}[x,v]$
$\displaystyle=-\sum_{v\in[x,z]}\mu_{P}[x,v]-\sum_{v\in[x,z^{\prime}]}\mu_{P}[x,v]+\sum_{v\in[x,z]\cap[x,z^{\prime}]}\mu_{P}[x,v]$
$\displaystyle=-\sum_{v\in[x,z]}\mu_{P}[x,v]-\sum_{v\in[x,z^{\prime}]}\mu_{P}[x,v]+\sum_{v\in[x,w]}\mu_{P}[x,v]$
$\displaystyle=0.\qed$

####  5.3.2 Embeddings

Recall that an _embedding_ of a permutation $\sigma\in\mathcal{S}_{k}$ into a