1 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.
Let
$\unicode[STIX]{x1D70E}$
and
$\unicode[STIX]{x1D70B}$
be permutations of positive integers. We say that
$\unicode[STIX]{x1D70B}$
contains
$\unicode[STIX]{x1D70E}$
if there is a subsequence of elements of
$\unicode[STIX]{x1D70B}$
that is order-isomorphic to
$\unicode[STIX]{x1D70E}$
. As an example, 3624715 contains 3142 as the subsequences 6275 and 6475. If
$\unicode[STIX]{x1D70E}$
is contained in
$\unicode[STIX]{x1D70B}$
, then we write
$\unicode[STIX]{x1D70E}\leqslant \unicode[STIX]{x1D70B}$
.
The set of all permutations is a poset under the partial order given by containment. A closed interval
$[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
in a poset is the set defined by
$\{\unicode[STIX]{x1D70F}:\unicode[STIX]{x1D70E}\leqslant \unicode[STIX]{x1D70F}\leqslant \unicode[STIX]{x1D70B}\}$
, and a half-open interval [
$\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}$
) is the set
$\{\unicode[STIX]{x1D70F}:\unicode[STIX]{x1D70E}\leqslant \unicode[STIX]{x1D70F}<\unicode[STIX]{x1D70B}\}$
. The Möbius function of an interval
$[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
is defined recursively as follows:
$$\begin{eqnarray}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]=\left\{\begin{array}{@{}lll@{}}0 & \quad & \text{if }\unicode[STIX]{x1D70E}\not \leqslant \unicode[STIX]{x1D70B},\\ 1 & \quad & \text{if }\unicode[STIX]{x1D70E}=\unicode[STIX]{x1D70B},\\ -\mathop{\sum }_{\unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70F}] & \quad & \text{otherwise.}\end{array}\right.\end{eqnarray}$$
From the definition of the Möbius function it follows that if
$\unicode[STIX]{x1D70E}<\unicode[STIX]{x1D70B}$
, then
$\sum _{\unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70F}]=0$
.
In this paper, we are mainly concerned with the principal Möbius function of a permutation
$\unicode[STIX]{x1D70B}$
, written
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]$
, defined by
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=\unicode[STIX]{x1D707}[1,\unicode[STIX]{x1D70B}]$
. We focus on the zeros of the principal Möbius function, that is, on the permutations
$\unicode[STIX]{x1D70B}$
for which
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=0$
. We show that we can often determine that a permutation
$\unicode[STIX]{x1D70B}$
is such a Möbius zero by examining small localities of
$\unicode[STIX]{x1D70B}$
. We formalize this idea using the notion of an “annihilator”. Informally, an annihilator is a permutation
$\unicode[STIX]{x1D6FC}$
such that any permutation
$\unicode[STIX]{x1D70B}$
containing an interval copy of
$\unicode[STIX]{x1D6FC}$
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}\geqslant 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$
.
The question of computing the Möbius function in the permutation poset was first raised by Wilf [Reference Wilf20]. The first result was by Sagan and Vatter [Reference Sagan and Vatter12], who determined the Möbius function on intervals of layered permutations. Steingrímsson and Tenner [Reference Steingrímsson and Tenner19] found pairs of permutations
$(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})$
, where
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]=0$
.
Burstein, Jelínek, Jelínková and Steingrímsson [Reference Burstein, Jelínek, Jelínková and Steingrímsson7] 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
$\unicode[STIX]{x1D70B}$
of length greater than 2 begins
$12$
, then
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=0$
.
Smith [Reference Smith14] found an explicit formula for the Möbius function on the interval
$[1,\unicode[STIX]{x1D70B}]$
for all permutations
$\unicode[STIX]{x1D70B}$
with a single descent. Smith’s paper includes a lemma stating that if a permutation
$\unicode[STIX]{x1D70B}$
contains an interval order-isomorphic to
$123$
, then
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=0$
. While the result in [Reference Burstein, Jelínek, Jelínková and Steingrímsson7] 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 [Reference Burstein, Jelínek, Jelínková and Steingrímsson7].
Smith [Reference Smith15] has explicit expressions for the Möbius function
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
when
$\unicode[STIX]{x1D70E}$
and
$\unicode[STIX]{x1D70B}$
have the same number of descents. In [Reference Smith16], Smith found an expression that determines the Möbius function for all intervals in the poset, although the expression involves a rather complicated double sum, starting with
$\sum _{\unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70F}]$
.
Brignall and Marchant [Reference Brignall and Marchant6] 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, and used this result to find a fast polynomial algorithm for computing
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]$
, where
$\unicode[STIX]{x1D70B}$
is an increasing oscillation.
2 Definitions and notation
We let
${\mathcal{S}}_{n}$
denote the set of permutations of length
$n$
. We represent a permutation
$\unicode[STIX]{x1D70B}\in {\mathcal{S}}_{n}$
as a sequence
$\unicode[STIX]{x1D70B}_{1},\unicode[STIX]{x1D70B}_{2},\ldots ,\unicode[STIX]{x1D70B}_{n}$
of integers from the set
$[n]=\{1,2,\ldots ,n\}$
in which each element of
$[n]$
appears exactly once. We let
$\unicode[STIX]{x1D716}$
denote the unique permutation of length
$0$
.
A sequence of numbers
$a_{1},a_{2},\ldots ,a_{n}$
is order-isomorphic to a sequence
$b_{1},b_{2},\ldots ,b_{n}$
if for every
$i,j\in [n]$
we have
$a_{i}<a_{j}\Leftrightarrow b_{i}<b_{j}$
. A permutation
$\unicode[STIX]{x1D70B}\in {\mathcal{S}}_{n}$
contains a permutation
$\unicode[STIX]{x1D70E}\in {\mathcal{S}}_{k}$
if
$\unicode[STIX]{x1D70B}$
has a subsequence of length
$k$
order-isomorphic to
$\unicode[STIX]{x1D70E}$
.
An interval of a permutation
$\unicode[STIX]{x1D70B}$
is a non-empty set of contiguous indices
$i,i+1,\ldots ,j$
, where the set of values
$\{\unicode[STIX]{x1D70B}_{i},\unicode[STIX]{x1D70B}_{i+1},\ldots ,\unicode[STIX]{x1D70B}_{j}\}$
is also contiguous. We say that
$\unicode[STIX]{x1D70B}$
has an interval copy of a permutation
$\unicode[STIX]{x1D6FC}$
if it contains an interval of length
$|\unicode[STIX]{x1D6FC}|$
whose elements form a subsequence order-isomorphic to
$\unicode[STIX]{x1D6FC}$
.
An adjacency in a permutation is an interval of length 2. If a permutation contains a monotonic interval of length 3 or more, then each subinterval of length 2 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
$\unicode[STIX]{x1D70B}$
contains at least one up-adjacency, and at least one down-adjacency, then we say that
$\unicode[STIX]{x1D70B}$
has opposing adjacencies. An example of a permutation with opposing adjacencies is
$367249815$
, which is shown in Figure 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 [Reference Atkinson and Stitt3].
Given a permutation
$\unicode[STIX]{x1D70E}$
of length
$n$
, and permutations
$\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{n}$
, not all of them equal to the empty permutation
$\unicode[STIX]{x1D716}$
, the inflation of
$\unicode[STIX]{x1D70E}$
by
$\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{n}$
, written as
$\unicode[STIX]{x1D70E}[\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{n}]$
, is the permutation obtained by removing the element
$\unicode[STIX]{x1D70E}_{i}$
if
$\unicode[STIX]{x1D6FC}_{i}=\unicode[STIX]{x1D716}$
, and replacing
$\unicode[STIX]{x1D70E}_{i}$
with an interval isomorphic to
$\unicode[STIX]{x1D6FC}_{i}$
otherwise. Note that this is slightly different to the standard definition of inflation, originally given in Albert and Atkinson [Reference Albert and Atkinson1], which does not allow inflation by the empty permutation. As examples,
$3624715[1,12,1,1,21,1,1]=367249815$
, and
$3624715[\unicode[STIX]{x1D716},1,1,\unicode[STIX]{x1D716},1,\unicode[STIX]{x1D716},1]=3142$
.
In many cases, we will be interested in permutations where most positions are inflated by the singleton permutation
$1$
. If
$\unicode[STIX]{x1D70E}=3624715$
, then we will write
$\unicode[STIX]{x1D70E}[1,12,1,1,21,1,1]=367249815$
as
$\unicode[STIX]{x1D70E}_{2,5}[12,21]$
. Formally,
$\unicode[STIX]{x1D70E}_{i_{1},\ldots ,i_{k}}[\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{k}]$
is the inflation of
$\unicode[STIX]{x1D70E}$
where
$\unicode[STIX]{x1D70E}_{i_{j}}$
is inflated by
$\unicode[STIX]{x1D6FC}_{j}$
for
$j=1,\ldots ,k$
, and all other positions of
$\unicode[STIX]{x1D70E}$
are inflated by
$1$
. When using this notation, we always assume that the indices
$i_{1},\ldots ,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
$[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
such that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]=0$
, with particular emphasis on the case
$\unicode[STIX]{x1D70E}=1$
. We say that
$\unicode[STIX]{x1D70B}$
is a Möbius zero (or just zero) if
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=0$
, and we say that
$\unicode[STIX]{x1D70B}$
is a
$\unicode[STIX]{x1D70E}$
-zero if
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]=0$
.
It turns out that many sufficient conditions for
$\unicode[STIX]{x1D70B}$
to be a Möbius zero can be stated in terms of inflations. We say that a permutation
$\unicode[STIX]{x1D719}$
is an annihilator if every permutation that has an interval copy of
$\unicode[STIX]{x1D719}$
is a Möbius zero; in other words, for every
$\unicode[STIX]{x1D70F}$
and every
$i\leqslant |\unicode[STIX]{x1D70F}|$
the permutation
$\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D719}]$
is a Möbius zero. More generally, we say that
$\unicode[STIX]{x1D719}$
is a
$\unicode[STIX]{x1D70E}$
-annihilator if every permutation with an interval copy of
$\unicode[STIX]{x1D719}$
is a
$\unicode[STIX]{x1D70E}$
-zero.
We say that a pair of permutations
$\unicode[STIX]{x1D719}$
,
$\unicode[STIX]{x1D713}$
is an annihilator pair if for every permutation
$\unicode[STIX]{x1D70F}$
and every pair of distinct indices
$i,j\leqslant |\unicode[STIX]{x1D70F}|$
, the permutation
$\unicode[STIX]{x1D70F}_{i,j}[\unicode[STIX]{x1D719},\unicode[STIX]{x1D713}]$
is a Möbius zero.
Observe that for an annihilator
$\unicode[STIX]{x1D719}$
, any permutation containing an interval copy of
$\unicode[STIX]{x1D719}$
is also an annihilator. Likewise, if
$\unicode[STIX]{x1D719}$
and
$\unicode[STIX]{x1D713}$
form an annihilator pair then any permutation containing disjoint interval copies of
$\unicode[STIX]{x1D719}$
and
$\unicode[STIX]{x1D713}$
is an annihilator.
As our first main result, presented in §3, 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 §5, 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
$\unicode[STIX]{x1D6FC}$
and
$\unicode[STIX]{x1D6FD}$
, the permutation
$\unicode[STIX]{x1D6FC}\oplus 1\oplus \unicode[STIX]{x1D6FD}=123[\unicode[STIX]{x1D6FC},1,\unicode[STIX]{x1D6FD}]$
is an annihilator, and generalize this result to a construction of
$\unicode[STIX]{x1D70E}$
-annihilators for general
$\unicode[STIX]{x1D70E}$
. These results are presented in §4.
Finally, in §6, we give several examples of annihilators and annihilator pairs that do not directly follow from the results in the previous sections.
2.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 1. Let
$P$
be a finite poset with Möbius function
$\unicode[STIX]{x1D707}_{P}$
, and let
$x$
and
$y$
be two elements of
$P$
satisfying
$\unicode[STIX]{x1D707}_{P}[x,y]=0$
. Let
$Q$
be the poset obtained from
$P$
by deleting the element
$y$
, and let
$\unicode[STIX]{x1D707}_{Q}$
be its Möbius function. Then for every
$z\in Q$
, we have
$\unicode[STIX]{x1D707}_{Q}[x,z]=\unicode[STIX]{x1D707}_{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)
$[x,y)=[x,z]\cup [x,z^{\prime }]$
; and(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 2 shows examples of narrow-tipped and diamond-tipped posets.
Examples of narrow-tipped (left) and diamond-tipped (right) posets.
Fact 2. Let
$P$
be a poset with Möbius function
$\unicode[STIX]{x1D707}_{P}$
, and let
$[x,y]$
be a finite interval in
$P$
. If
$[x,y]$
is narrow-tipped or diamond-tipped, then
$\unicode[STIX]{x1D707}_{P}[x,y]=0$
.
Proof. If
$[x,y]$
is narrow-tipped with core
$z$
, then
$$\begin{eqnarray}\unicode[STIX]{x1D707}_{P}[x,y]=-\mathop{\sum }_{v\in [x,y)}\unicode[STIX]{x1D707}_{P}[x,v]=-\mathop{\sum }_{v\in [x,z]}\unicode[STIX]{x1D707}_{P}[x,v]=0.\end{eqnarray}$$
If
$[x,y]$
is diamond-tipped with core
$(z,z^{\prime },w)$
then
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D707}_{P}[x,y] & = & \displaystyle -\mathop{\sum }_{v\in [x,y)}\unicode[STIX]{x1D707}_{P}[x,v]\nonumber\\ \displaystyle & = & \displaystyle -\mathop{\sum }_{v\in [x,z]\cup [x,z^{\prime }]}\unicode[STIX]{x1D707}_{P}[x,v]\nonumber\\ \displaystyle & = & \displaystyle -\mathop{\sum }_{v\in [x,z]}\unicode[STIX]{x1D707}_{P}[x,v]-\mathop{\sum }_{v\in [x,z^{\prime }]}\unicode[STIX]{x1D707}_{P}[x,v]+\mathop{\sum }_{v\in [x,z]\cap [x,z^{\prime }]}\unicode[STIX]{x1D707}_{P}[x,v]\nonumber\\ \displaystyle & = & \displaystyle -\mathop{\sum }_{v\in [x,z]}\unicode[STIX]{x1D707}_{P}[x,v]-\mathop{\sum }_{v\in [x,z^{\prime }]}\unicode[STIX]{x1D707}_{P}[x,v]+\mathop{\sum }_{v\in [x,w]}\unicode[STIX]{x1D707}_{P}[x,v]\nonumber\\ \displaystyle & = & \displaystyle 0.\nonumber\end{eqnarray}$$
◻
2.2 Embeddings
An embedding of a permutation
$\unicode[STIX]{x1D70E}\in {\mathcal{S}}_{k}$
into a permutation
$\unicode[STIX]{x1D70B}\in {\mathcal{S}}_{n}$
is a function
$f:[k]\rightarrow [n]$
with the following properties:
∙
$1\leqslant f(1)<f(2)<\cdots <f(k)\leqslant n$
;∙ for any
$i,j\in [k]$
, we have
$\unicode[STIX]{x1D70E}_{i}<\unicode[STIX]{x1D70E}_{j}$
if and only if
$\unicode[STIX]{x1D70B}_{f(i)}<\unicode[STIX]{x1D70B}_{f(j)}$
.
We let
${\mathcal{E}}(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})$
denote the set of embeddings of
$\unicode[STIX]{x1D70E}$
into
$\unicode[STIX]{x1D70B}$
, and
$E(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})$
denote the cardinality of
${\mathcal{E}}(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})$
.
For an embedding
$f$
of
$\unicode[STIX]{x1D70E}$
into
$\unicode[STIX]{x1D70B}$
, the image of
$f$
, denoted
$\text{Img}(f)$
, is the set
$\{f(i);\;i\in [k]\}$
. In particular,
$|\text{Img}(f)|=|\unicode[STIX]{x1D70E}|$
. The permutation
$\unicode[STIX]{x1D70E}$
is the source of the embedding
$f$
, denoted
$\text{src}_{\unicode[STIX]{x1D70B}}(f)$
. When
$\unicode[STIX]{x1D70B}$
is clear from the context (as it usually will be) we write
$\text{src}(f)$
instead of
$\text{src}_{\unicode[STIX]{x1D70B}}(f)$
. Note that for a fixed
$\unicode[STIX]{x1D70B}$
, the set
$\text{Img}(f)$
determines both
$f$
and
$\text{src}_{\unicode[STIX]{x1D70B}}(f)$
uniquely.
We say that an embedding
$f$
is even if the cardinality of
$\text{Img}(f)$
is even, otherwise
$f$
is odd. In our arguments, we will frequently consider sign-reversing mappings on sets of embeddings (with different sources), which are mappings that map an odd embedding to an even one and vice versa. A typical example of a sign-reversing mapping is the so-called
$i$
-switch, which we now define. For a permutation
$\unicode[STIX]{x1D70B}\in {\mathcal{S}}_{n}$
, let
${\mathcal{E}}(\ast ,\unicode[STIX]{x1D70B})$
be the set
$\bigcup _{\unicode[STIX]{x1D70E}\leqslant \unicode[STIX]{x1D70B}}{\mathcal{E}}(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})$
. For an index
$i\in [n]$
, the
$i$
-switch of an embedding
$f\in {\mathcal{E}}(\ast ,\unicode[STIX]{x1D70B})$
, denoted
$\unicode[STIX]{x1D6E5}_{i}(f)$
, is the embedding
$g\in {\mathcal{E}}(\ast ,\unicode[STIX]{x1D70B})$
uniquely determined by the following properties:
$$\begin{eqnarray}\displaystyle \text{Img}(g) & = & \displaystyle \text{Img}(f)\cup \{i\}\quad \text{if }i\not \in \text{Img}(f),\nonumber\\ \displaystyle \text{Img}(g) & = & \displaystyle \text{Img}(f)\setminus \{i\}\quad \text{if }i\in \text{Img}(f).\nonumber\end{eqnarray}$$
For example, consider the permutations
$\unicode[STIX]{x1D70E}=132$
and
$\unicode[STIX]{x1D70B}=41253$
, and the embedding
$f\in {\mathcal{E}}(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})$
satisfying
$f(1)=2$
,
$f(2)=4$
and
$f(3)=5$
. We then have
$\text{Img}(f)=\{2,4,5\}$
. Defining
$g=\unicode[STIX]{x1D6E5}_{3}(f)$
, we see that
$\text{Img}(g)=\{2,3,4,5\}$
, and
$\text{src}(g)$
is the permutation
$1243$
. Similarly, for
$h=\unicode[STIX]{x1D6E5}_{5}(g)$
, we have
$\text{Img}(h)=\{2,3,4\}$
and
$\text{src}(h)=123$
.
Note that for any
$\unicode[STIX]{x1D70B}\in {\mathcal{S}}_{n}$
and any
$i\in [n]$
, the function
$\unicode[STIX]{x1D6E5}_{i}$
is a sign-reversing involution on the set
${\mathcal{E}}(\ast ,\unicode[STIX]{x1D70B})$
.
Consider, for a given
$\unicode[STIX]{x1D70B}\in {\mathcal{S}}_{n}$
, two embeddings
$f,g\in {\mathcal{E}}(\ast ,\unicode[STIX]{x1D70B})$
. We say that
$f$
is contained in
$g$
if
$\text{Img}(f)\subseteq \text{Img}(g)$
. Note that if
$f$
is contained in
$g$
, then the permutation
$\text{src}(f)$
is contained in
$\text{src}(g)$
, and if a permutation
$\unicode[STIX]{x1D706}$
is contained in a permutation
$\unicode[STIX]{x1D70F}$
, then any embedding from
${\mathcal{E}}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B})$
contains at least one embedding from
${\mathcal{E}}(\unicode[STIX]{x1D706},\unicode[STIX]{x1D70B})$
. In particular, the mapping
$f\mapsto \text{src}(f)$
is a poset homomorphism from the set
${\mathcal{E}}(\ast ,\unicode[STIX]{x1D70B})$
ordered by containment onto the interval
$[\unicode[STIX]{x1D716},\unicode[STIX]{x1D70B}]$
in the permutation pattern poset.
2.3 Möbius function via normal embeddings
We will now derive a general formula, which will become useful in several subsequent arguments. The formula can be seen as a direct consequence of the well-known Möbius inversion formula. The following form of the Möbius inversion formula can be deduced, for example, from Proposition 3.7.2 in Stanley’s book [Reference Stanley18]. A poset is locally finite if each of its intervals is finite.
Fact 3 (Möbius inversion formula).
Let
$P$
be a locally finite poset with maximum element
$y$
, let
$\unicode[STIX]{x1D707}$
be the Möbius function of
$P$
, and let
$F:P\rightarrow \mathbb{R}$
be a function. If a function
$G:P\rightarrow \mathbb{R}$
is defined by
$$\begin{eqnarray}G(x)=\mathop{\sum }_{z\in [x,y]}F(z),\end{eqnarray}$$
then for every
$x\in P$
, we have
$$\begin{eqnarray}F(x)=\mathop{\sum }_{z\in [x,y]}\unicode[STIX]{x1D707}[x,z]G(z).\end{eqnarray}$$
As a consequence, we obtain the following result.
Proposition 4. Let
$\unicode[STIX]{x1D70E}$
and
$\unicode[STIX]{x1D70B}$
be arbitrary permutations, and let
$F:[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]\rightarrow \mathbb{R}$
be a function satisfying
$F(\unicode[STIX]{x1D70B})=1$
. We then have
$$\begin{eqnarray}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]=F(\unicode[STIX]{x1D70E})-\mathop{\sum }_{\unicode[STIX]{x1D706}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D706}]\mathop{\sum }_{\unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D706},\unicode[STIX]{x1D70B}]}F(\unicode[STIX]{x1D70F}).\end{eqnarray}$$
Proof. Fix
$\unicode[STIX]{x1D70E}$
,
$\unicode[STIX]{x1D70B}$
and
$F$
. For
$\unicode[STIX]{x1D706}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
, define
$G(\unicode[STIX]{x1D706})=\sum _{\unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D706},\unicode[STIX]{x1D70B}]}F(\unicode[STIX]{x1D70F})$
. Using Fact 3 for the poset
$P=[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
, we obtain
$$\begin{eqnarray}F(\unicode[STIX]{x1D70E})=\mathop{\sum }_{\unicode[STIX]{x1D706}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D706}]G(\unicode[STIX]{x1D706}).\end{eqnarray}$$
Substituting the definition of
$G(\unicode[STIX]{x1D706})$
into the above identity and noting that
$F(\unicode[STIX]{x1D70B})=1$
, we get
$$\begin{eqnarray}\displaystyle F(\unicode[STIX]{x1D70E}) & = & \displaystyle \mathop{\sum }_{\unicode[STIX]{x1D706}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D706}]\mathop{\sum }_{\unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D706},\unicode[STIX]{x1D70B}]}F(\unicode[STIX]{x1D70F})\nonumber\\ \displaystyle & = & \displaystyle \unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]+\mathop{\sum }_{\unicode[STIX]{x1D706}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D706}]\mathop{\sum }_{\unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D706},\unicode[STIX]{x1D70B}]}F(\unicode[STIX]{x1D70F}),\nonumber\end{eqnarray}$$
from which the proposition follows. ◻
In our applications, the function
$F(\unicode[STIX]{x1D70F})$
will usually be defined in terms of the number of embeddings of
$\unicode[STIX]{x1D70F}$
into
$\unicode[STIX]{x1D70B}$
satisfying certain additional conditions. In the literature, there are several definitions of such restricted embeddings, which are usually referred to as normal embeddings.
The notion of normal embedding seems to originate from the work of Björner [Reference Björner4], who defined normal embeddings between words, and showed that in the subword order of words over a finite alphabet, the Möbius function of any interval
$[x,y]$
is equal in absolute value to the number of normal embeddings of
$x$
into
$y$
.
Björner’s approach was later extended to the computation of the Möbius function in the composition poset [Reference Sagan and Vatter12], the poset of separable permutations [Reference Burstein, Jelínek, Jelínková and Steingrímsson7], or the poset of permutations with a fixed number of descents [Reference Smith15]. In all these cases, the authors define a notion of “normal” embeddings tailored for their poset, and then express the Möbius function of an interval
$[x,y]$
as the sum of weights of the “normal” embeddings of
$x$
into
$y$
, where each normal embedding has weight
$1$
or
$-1$
.
For general permutations, this simple approach fails, since the Möbius function
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
is sometimes larger than the number of all embeddings of
$\unicode[STIX]{x1D70E}$
into
$\unicode[STIX]{x1D70B}$
. However, Smith [Reference Smith16] introduced a notion of normal embedding applicable to arbitrary permutations, and proved a formula expressing
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
as a summation over certain sets of normal embeddings.
For consistency, we adopt the term “normal embedding” in this paper, although in our proofs, we will need to introduce several notions of normality, which are different from each other and from the notions of normality introduced by previous authors. We will always use
${\mathcal{N}}{\mathcal{E}}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B})$
to denote the set of embeddings of
$\unicode[STIX]{x1D70F}$
into
$\unicode[STIX]{x1D70B}$
satisfying the definition of normality used in the given context, and we let
$\text{NE}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B})$
be the cardinality of
${\mathcal{N}}{\mathcal{E}}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B})$
.
The next proposition provides a general basis for all our subsequent applications of normal embeddings.
Proposition 5. Let
$\unicode[STIX]{x1D70E}$
and
$\unicode[STIX]{x1D70B}$
be permutations. Suppose that for each
$\unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
we fix a subset
${\mathcal{N}}{\mathcal{E}}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B})$
of
${\mathcal{E}}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B})$
, with the elements of
${\mathcal{N}}{\mathcal{E}}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B})$
being referred to as
$\text{normal embeddings}$
of
$\unicode[STIX]{x1D70F}$
into
$\unicode[STIX]{x1D70B}$
. Assume that
${\mathcal{N}}{\mathcal{E}}(\unicode[STIX]{x1D70B},\unicode[STIX]{x1D70B})={\mathcal{E}}(\unicode[STIX]{x1D70B},\unicode[STIX]{x1D70B})$
, that is, the unique embedding of
$\unicode[STIX]{x1D70B}$
into
$\unicode[STIX]{x1D70B}$
is normal. For each
$\unicode[STIX]{x1D706}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})$
, define the two sets of embeddings
$$\begin{eqnarray}\displaystyle {\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{odd},\unicode[STIX]{x1D70B}) & = & \displaystyle \mathop{\bigcup }_{\substack{ \unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D706},\unicode[STIX]{x1D70B}] \\ |\unicode[STIX]{x1D70F}|\,\text{odd}}}{\mathcal{N}}{\mathcal{E}}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B})\quad \text{and}\nonumber\\ \displaystyle {\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{even},\unicode[STIX]{x1D70B}) & = & \displaystyle \mathop{\bigcup }_{\substack{ \unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D706},\unicode[STIX]{x1D70B}] \\ |\unicode[STIX]{x1D70F}|\,\text{even}}}{\mathcal{N}}{\mathcal{E}}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B}).\nonumber\end{eqnarray}$$
If for every
$\unicode[STIX]{x1D706}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})$
such that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D706}]\neq 0$
, we have the identity
$$\begin{eqnarray}|{\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{odd},\unicode[STIX]{x1D70B})|=|{\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{even},\unicode[STIX]{x1D70B})|,\end{eqnarray}$$
then
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]=(-1)^{|\unicode[STIX]{x1D70B}|-|\unicode[STIX]{x1D70E}|}\text{NE}(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})$
.
Proof. The trick is to define the function
$F(\unicode[STIX]{x1D70F})=(-1)^{|\unicode[STIX]{x1D70B}|-|\unicode[STIX]{x1D70F}|}\text{NE}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B})$
and apply Proposition 4. This yields
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}] & = & \displaystyle F(\unicode[STIX]{x1D70E})-\mathop{\sum }_{\unicode[STIX]{x1D706}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D706}]\mathop{\sum }_{\unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D706},\unicode[STIX]{x1D70B}]}F(\unicode[STIX]{x1D70F})\nonumber\\ \displaystyle & = & \displaystyle F(\unicode[STIX]{x1D70E})-\mathop{\sum }_{\unicode[STIX]{x1D706}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D706}]\mathop{\sum }_{\unicode[STIX]{x1D70F}\in [\unicode[STIX]{x1D706},\unicode[STIX]{x1D70B}]}(-1)^{|\unicode[STIX]{x1D70B}|-|\unicode[STIX]{x1D70F}|}\text{NE}(\unicode[STIX]{x1D70F},\unicode[STIX]{x1D70B})\nonumber\\ \displaystyle & = & \displaystyle F(\unicode[STIX]{x1D70E})-\mathop{\sum }_{\unicode[STIX]{x1D706}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})}\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D706}](-1)^{|\unicode[STIX]{x1D70B}|}(|{\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{even},\unicode[STIX]{x1D70B})|-|{\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{odd},\unicode[STIX]{x1D70B})|)\nonumber\\ \displaystyle & = & \displaystyle F(\unicode[STIX]{x1D70E})\nonumber\\ \displaystyle & = & \displaystyle (-1)^{|\unicode[STIX]{x1D70B}|-|\unicode[STIX]{x1D70E}|}\text{NE}(\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}),\nonumber\end{eqnarray}$$
as claimed. ◻
We remark that the general formula of Proposition 4 can be useful even in situations where the more restrictive assumptions of Proposition 5 fail. An example of such application of Proposition 4 will appear in an upcoming manuscript [Reference Jelínek, Kantor, Kynčl and Tancer9], which is being prepared in parallel to this publication.
3 Permutations with opposing adjacencies
In this section, we show that if a permutation has opposing adjacencies, then the value of the principal Möbius function is zero.
Theorem 6. If
$\unicode[STIX]{x1D70B}$
has opposing adjacencies, then
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=0$
.
For this theorem, we are able to give two proofs. One of them is based on the notion of diamond-tipped intervals, and the other uses the approach of normal embeddings. As both these approaches will later be adapted to more complicated settings, we find it instructive to include both proofs here.
Proof via diamond-tipped posets.
For contradiction, suppose that the theorem fails, and let
$\unicode[STIX]{x1D70B}$
be a shortest permutation with opposing adjacencies such that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]\neq 0$
. Since
$\unicode[STIX]{x1D70B}$
has opposing adjacencies, there is a permutation
$\unicode[STIX]{x1D70F}$
and indices
$i,j\leqslant |\unicode[STIX]{x1D70F}|$
such that
$\unicode[STIX]{x1D70B}=\unicode[STIX]{x1D70F}_{i,j}[12,21]$
. Define
$\unicode[STIX]{x1D719}=\unicode[STIX]{x1D70F}_{i,j}[1,21]$
and
$\unicode[STIX]{x1D719}^{\prime }=\unicode[STIX]{x1D70F}_{i,j}[12,1]$
.
We claim that the interval
$[1,\unicode[STIX]{x1D70B}]$
can be transformed into a diamond-tipped interval with core
$(\unicode[STIX]{x1D719},\unicode[STIX]{x1D719}^{\prime },\unicode[STIX]{x1D70F})$
by deleting a set of Möbius zeros from the interior of
$[1,\unicode[STIX]{x1D70B}]$
. Since by Fact 1, the deletion of Möbius zeros does not affect the value of
$\unicode[STIX]{x1D707}[1,\unicode[STIX]{x1D70B}]$
, and since diamond-tipped intervals have zero Möbius function by Fact 2, this claim will imply that
$\unicode[STIX]{x1D707}[1,\unicode[STIX]{x1D70B}]=0$
, a contradiction.
To prove the claim, note first that any permutation
$\unicode[STIX]{x1D706}\in [1,\unicode[STIX]{x1D70B})$
with opposing adjacencies is a Möbius zero, since
$\unicode[STIX]{x1D70B}$
is a minimal counterexample to the theorem. Choose any
$\unicode[STIX]{x1D706}\in [1,\unicode[STIX]{x1D70B})$
. Observe that if
$\unicode[STIX]{x1D706}$
has no up-adjacency, then
$\unicode[STIX]{x1D706}\leqslant \unicode[STIX]{x1D719}$
, and symmetrically, if
$\unicode[STIX]{x1D706}$
has no down-adjacency, then
$\unicode[STIX]{x1D706}\leqslant \unicode[STIX]{x1D719}^{\prime }$
. Thus, any
$\unicode[STIX]{x1D706}\in [1,\unicode[STIX]{x1D70B})$
not belonging to
$[1,\unicode[STIX]{x1D719}]\cup [1,\unicode[STIX]{x1D719}^{\prime }]$
has opposing adjacencies and can be deleted from
$[1,\unicode[STIX]{x1D70B}]$
.
Next, suppose that a permutation
$\unicode[STIX]{x1D706}$
is in
$[1,\unicode[STIX]{x1D719}]\cap [1,\unicode[STIX]{x1D719}^{\prime }]$
but not in
$[1,\unicode[STIX]{x1D70F}]$
. Observe that any permutation in
$[1,\unicode[STIX]{x1D719}]\setminus [1,\unicode[STIX]{x1D70F}]$
has a down-adjacency, while any permutation in
$[1,\unicode[STIX]{x1D719}^{\prime }]\setminus [1,\unicode[STIX]{x1D70F}]$
has an up-adjacency. It follows that
$\unicode[STIX]{x1D706}$
has opposing adjacencies and can again be deleted from
$[1,\unicode[STIX]{x1D70B}]$
.
After these deletions, the remaining poset is diamond-tipped with core
$(\unicode[STIX]{x1D719},\unicode[STIX]{x1D719}^{\prime },\unicode[STIX]{x1D70F})$
as claimed, and hence
$\unicode[STIX]{x1D707}[1,\unicode[STIX]{x1D70B}]=0$
, a contradiction.◻
Proof via normal embeddings.
Suppose again that
$\unicode[STIX]{x1D70B}\in {\mathcal{S}}_{n}$
is a shortest counterexample. Suppose that
$\unicode[STIX]{x1D70B}$
has an up-adjacency at positions
$i$
,
$i+1$
, and a down-adjacency at positions
$j$
,
$j+1$
. Note that the positions
$i$
,
$i+1$
,
$j$
and
$j+1$
are all distinct, and in particular
$n\geqslant 4$
.
We will say that an embedding
$f\in {\mathcal{E}}(\ast ,\unicode[STIX]{x1D70B})$
is normal if
$\text{Img}(f)$
is a superset of
$[n]\setminus \{i,j\}$
. In other words,
$\text{Img}(f)$
contains all positions of
$\unicode[STIX]{x1D70B}$
with the possible exception of
$i$
and
$j$
. Thus, there are four normal embeddings.
We will use Proposition 5 with the above notion of normal embeddings and with
$\unicode[STIX]{x1D70E}=1$
. Clearly, we have
${\mathcal{E}}(\unicode[STIX]{x1D70B},\unicode[STIX]{x1D70B})={\mathcal{N}}{\mathcal{E}}(\unicode[STIX]{x1D70B},\unicode[STIX]{x1D70B})$
. The main task is to verify equation (2), that is, to show that for every
$\unicode[STIX]{x1D706}\in [1,\unicode[STIX]{x1D70B})$
such that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D706}]\neq 0$
we have
$|{\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{odd},\unicode[STIX]{x1D70B})|=|{\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{even},\unicode[STIX]{x1D70B})|$
. To prove this identity, we let
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
denote the set
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{odd},\unicode[STIX]{x1D70B})\cup {\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{even},\unicode[STIX]{x1D70B})$
, and we will provide a sign-reversing involution on
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
.
Choose a
$\unicode[STIX]{x1D706}\in [1,\unicode[STIX]{x1D70B})$
with
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D706}]\neq 0$
. It follows that
$\unicode[STIX]{x1D706}$
does not have opposing adjacencies, otherwise it would be a counterexample shorter than
$\unicode[STIX]{x1D70B}$
. Without loss of generality, assume that
$\unicode[STIX]{x1D706}$
has no up-adjacency. We will prove that the
$i$
-switch operation
$\unicode[STIX]{x1D6E5}_{i}$
is a sign-reversing involution on
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
.
It is clear that
$\unicode[STIX]{x1D6E5}_{i}$
is sign-reversing. We need to demonstrate that for every
$f\in {\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
, the embedding
$g=\unicode[STIX]{x1D6E5}_{i}(f)$
is again in
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
. It is clear that
$g$
is normal. It remains to argue that
$\text{src}(g)$
contains
$\unicode[STIX]{x1D706}$
, or in other words, that there is an embedding of
$\unicode[STIX]{x1D706}$
into
$\unicode[STIX]{x1D70B}$
contained in
$g$
. Let
$h$
be a (not necessarily normal) embedding of
$\unicode[STIX]{x1D706}$
into
$\unicode[STIX]{x1D70B}$
contained in
$f$
. If
$i$
is not in
$\text{Img}(h)$
, then
$h$
is also contained in
$g$
, and we are done. Suppose now that
$i\in \text{Img}(h)$
. Then
$i+1\not \in \text{Img}(h)$
, because
$i$
and
$i+1$
form an up-adjacency in
$\unicode[STIX]{x1D70B}$
while
$\unicode[STIX]{x1D706}$
has no up-adjacency. We modify the embedding
$h$
so that the element mapped to
$i$
will be mapped to
$i+1$
instead, and the mapping of the remaining elements is unchanged; let
$h^{\prime }$
be the resulting embedding (formally, we have
$\unicode[STIX]{x1D6E5}_{i}(\unicode[STIX]{x1D6E5}_{i+1}(h))=h^{\prime }$
). Since
$i$
and
$i+1$
form an adjacency in
$\unicode[STIX]{x1D70B}$
, we have
$\text{src}(h^{\prime })=\text{src}(h)=\unicode[STIX]{x1D706}$
. Since
$i+1$
is in the image of all normal embeddings, we see that
$h^{\prime }$
is contained in
$g$
, and so
$g\in {\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
. This shows that
$\unicode[STIX]{x1D6E5}_{i}$
is the required sign-reversing involution on
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
, verifying the assumptions of Proposition 5.
Proposition 5 then gives us that
$\unicode[STIX]{x1D707}[1,\unicode[STIX]{x1D70B}]=(-1)^{n-1}\text{NE}(1,\unicode[STIX]{x1D70B})$
. Since every normal embedding into
$\unicode[STIX]{x1D70B}$
contains both
$i+1$
and
$j+1$
in its image, there is clearly no normal embedding of 1 into
$\unicode[STIX]{x1D70B}$
and therefore we get
$\unicode[STIX]{x1D707}[1,\unicode[STIX]{x1D70B}]=0$
. ◻
4 A general construction of
$\unicode[STIX]{x1D70E}$
-annihilators
Let
$\unicode[STIX]{x1D70E}$
be a fixed non-empty lower bound permutation (the case
$\unicode[STIX]{x1D70E}=1$
being the most interesting). Recall that a permutation
$\unicode[STIX]{x1D719}$
is a
$\unicode[STIX]{x1D70E}$
-zero if
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D719}]=0$
, and
$\unicode[STIX]{x1D719}$
is a
$\unicode[STIX]{x1D70E}$
-annihilator if every permutation with an interval copy of
$\unicode[STIX]{x1D719}$
is a
$\unicode[STIX]{x1D70E}$
-zero. Clearly, any
$\unicode[STIX]{x1D70E}$
-annihilator is also a
$\unicode[STIX]{x1D70E}$
-zero. Our goal in this section is to present a general construction of an infinite family of
$\unicode[STIX]{x1D70E}$
-annihilators.
A permutation
$\unicode[STIX]{x1D719}$
is
$\unicode[STIX]{x1D70E}$
-narrow if
$\unicode[STIX]{x1D719}$
contains a permutation
$\unicode[STIX]{x1D719}^{-}$
of size
$|\unicode[STIX]{x1D719}|-1$
such that every permutation in the set
$[1,\unicode[STIX]{x1D719})\setminus [1,\unicode[STIX]{x1D719}^{-}]$
is a
$\unicode[STIX]{x1D70E}$
-annihilator. In such a situation, we call
$\unicode[STIX]{x1D719}^{-}$
a
$\unicode[STIX]{x1D70E}$
-core of
$\unicode[STIX]{x1D719}$
.
Note that if
$\unicode[STIX]{x1D719}$
is
$\unicode[STIX]{x1D70E}$
-narrow with
$\unicode[STIX]{x1D70E}$
-core
$\unicode[STIX]{x1D719}^{-}$
, then the interval
$[1,\unicode[STIX]{x1D719}]$
can be transformed into a narrow-tipped interval by a deletion of
$\unicode[STIX]{x1D70E}$
-annihilators. Our first goal is to show that, with a few exceptions, all
$\unicode[STIX]{x1D70E}$
-narrow permutations are
$\unicode[STIX]{x1D70E}$
-annihilators.
Proposition 7. If a permutation
$\unicode[STIX]{x1D719}$
is
$\unicode[STIX]{x1D70E}$
-narrow with a
$\unicode[STIX]{x1D70E}$
-core
$\unicode[STIX]{x1D719}^{-}$
, and if
$\unicode[STIX]{x1D70E}$
has no interval copy of
$\unicode[STIX]{x1D719}$
or of
$\unicode[STIX]{x1D719}^{-}$
, then
$\unicode[STIX]{x1D719}$
is a
$\unicode[STIX]{x1D70E}$
-annihilator.
Proof. Let
$\unicode[STIX]{x1D719}$
be
$\unicode[STIX]{x1D70E}$
-narrow with a
$\unicode[STIX]{x1D70E}$
-core
$\unicode[STIX]{x1D719}^{-}$
. Let
$\unicode[STIX]{x1D70B}$
be a permutation with an interval copy of
$\unicode[STIX]{x1D719}$
, that is,
$\unicode[STIX]{x1D70B}=\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D719}]$
for some
$\unicode[STIX]{x1D70F}$
and
$i$
. We show that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]=0$
. We may assume that
$\unicode[STIX]{x1D70E}\leqslant \unicode[STIX]{x1D70B}$
, otherwise
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]=0$
trivially. Let
$\unicode[STIX]{x1D70B}^{-}$
be the permutation
$\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D719}^{-}]$
. Note that
$\unicode[STIX]{x1D70E}\neq \unicode[STIX]{x1D70B}$
and
$\unicode[STIX]{x1D70E}\neq \unicode[STIX]{x1D70B}^{-}$
, since
$\unicode[STIX]{x1D70E}$
has no interval copy of
$\unicode[STIX]{x1D719}$
or of
$\unicode[STIX]{x1D719}^{-}$
.
The key step of the proof is to show that any permutation in
$[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})\setminus [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}^{-}]$
is a
$\unicode[STIX]{x1D70E}$
-zero. After we have proved this, we may use Fact 1 to remove all such
$\unicode[STIX]{x1D70E}$
-zeros from the interval
$[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
without affecting the value of
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
; note that
$\unicode[STIX]{x1D70E}$
itself is clearly not a
$\unicode[STIX]{x1D70E}$
-zero, so it will not be removed, implying that
$\unicode[STIX]{x1D70E}<\unicode[STIX]{x1D70B}^{-}$
. After the removal of
$[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})\setminus [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}^{-}]$
, the remainder of the interval
$[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]$
is a narrow-tipped poset with core
$\unicode[STIX]{x1D70B}^{-}$
, yielding
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]=0$
by Fact 2.
Therefore, to prove that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}]=0$
for a particular
$\unicode[STIX]{x1D70B}=\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D719}]$
, it is enough to show that all the permutations in
$[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})\setminus [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}^{-}]$
are
$\unicode[STIX]{x1D70E}$
-zeros. We prove this by induction on
$|\unicode[STIX]{x1D70F}|$
.
If
$|\unicode[STIX]{x1D70F}|=1$
, we have
$\unicode[STIX]{x1D70B}=\unicode[STIX]{x1D719}$
and
$\unicode[STIX]{x1D70B}^{-}=\unicode[STIX]{x1D719}^{-}$
. Then all the permutations in
$[1,\unicode[STIX]{x1D70B})\setminus [1,\unicode[STIX]{x1D70B}^{-}]$
are
$\unicode[STIX]{x1D70E}$
-annihilators (and therefore
$\unicode[STIX]{x1D70E}$
-zeros) by definition of
$\unicode[STIX]{x1D70E}$
-narrowness, and in particular, restricting our attention to permutations containing
$\unicode[STIX]{x1D70E}$
, we see that all the permutations in
$[\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})\setminus [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}^{-}]$
are
$\unicode[STIX]{x1D70E}$
-zeros, as claimed.
Suppose that
$|\unicode[STIX]{x1D70F}|>1$
. Consider a permutation
$\unicode[STIX]{x1D6FE}\in [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B})\setminus [\unicode[STIX]{x1D70E},\unicode[STIX]{x1D70B}^{-}]$
. Since
$\unicode[STIX]{x1D6FE}$
is contained in
$\unicode[STIX]{x1D70B}=\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D719}]$
, it can be expressed as
$\unicode[STIX]{x1D6FE}=\unicode[STIX]{x1D70F}_{j}^{\ast }[\unicode[STIX]{x1D719}^{\ast }]$
for some
$\unicode[STIX]{x1D716}\leqslant \unicode[STIX]{x1D719}^{\ast }\leqslant \unicode[STIX]{x1D719}$
and
$1\leqslant \unicode[STIX]{x1D70F}^{\ast }\leqslant \unicode[STIX]{x1D70F}$
, where
$\unicode[STIX]{x1D70F}^{\ast }$
has an embedding into
$\unicode[STIX]{x1D70F}$
, which maps
$j$
to
$i$
. Note that
$\unicode[STIX]{x1D719}^{\ast }$
cannot be contained in
$\unicode[STIX]{x1D719}^{-}$
, because in such a case we would have
$\unicode[STIX]{x1D6FE}\leqslant \unicode[STIX]{x1D70B}^{-}$
. Moreover, if
$\unicode[STIX]{x1D719}^{\ast }=\unicode[STIX]{x1D719}$
, then necessarily
$\unicode[STIX]{x1D70F}^{\ast }<\unicode[STIX]{x1D70F}$
, and by induction
$\unicode[STIX]{x1D6FE}$
is a
$\unicode[STIX]{x1D70E}$
-zero. Finally, if
$\unicode[STIX]{x1D719}^{\ast }$
is in
$[1,\unicode[STIX]{x1D719})\setminus [1,\unicode[STIX]{x1D719}^{-}]$
, then
$\unicode[STIX]{x1D719}^{\ast }$
is a
$\unicode[STIX]{x1D70E}$
-annihilator by the
$\unicode[STIX]{x1D70E}$
-narrowness of
$\unicode[STIX]{x1D719}$
, and hence
$\unicode[STIX]{x1D6FE}$
is a
$\unicode[STIX]{x1D70E}$
-zero.◻
With the help of Proposition 7, we can now provide an explicit general construction of
$\unicode[STIX]{x1D70E}$
-annihilators.
Proposition 8. Let
$\unicode[STIX]{x1D6FC}$
and
$\unicode[STIX]{x1D6FD}$
be non-empty permutations. Assume that
$\unicode[STIX]{x1D70E}$
does not contain any interval copy of a permutation of the form
$\unicode[STIX]{x1D6FC}^{\prime }\oplus \unicode[STIX]{x1D6FD}^{\prime }$
with
$1\leqslant \unicode[STIX]{x1D6FC}^{\prime }\leqslant \unicode[STIX]{x1D6FC}$
and
$1\leqslant \unicode[STIX]{x1D6FD}^{\prime }\leqslant \unicode[STIX]{x1D6FD}$
(in particular,
$\unicode[STIX]{x1D70E}$
has no up-adjacency). Then
$\unicode[STIX]{x1D6FC}\oplus 1\oplus \unicode[STIX]{x1D6FD}$
is
$\unicode[STIX]{x1D70E}$
-narrow with
$\unicode[STIX]{x1D70E}$
-core
$\unicode[STIX]{x1D6FC}\oplus \unicode[STIX]{x1D6FD}$
, and
$\unicode[STIX]{x1D6FC}\oplus 1\oplus \unicode[STIX]{x1D6FD}$
is a
$\unicode[STIX]{x1D70E}$
-annihilator.
Proof. We proceed by induction on
$|\unicode[STIX]{x1D6FC}|+|\unicode[STIX]{x1D6FD}|$
. Suppose first that
$\unicode[STIX]{x1D6FC}=\unicode[STIX]{x1D6FD}=1$
. Then trivially
$\unicode[STIX]{x1D6FC}\oplus 1\oplus \unicode[STIX]{x1D6FD}=123$
is
$\unicode[STIX]{x1D70E}$
-narrow with
$\unicode[STIX]{x1D70E}$
-core
$\unicode[STIX]{x1D6FC}\oplus \unicode[STIX]{x1D6FD}=12$
, since the set
$[1,123)\setminus [1,12]$
is empty. Moreover, by assumption,
$\unicode[STIX]{x1D70E}$
has no interval copy of
$12$
, and therefore also no interval copy of
$123$
, hence
$123$
is a
$\unicode[STIX]{x1D70E}$
-annihilator by Proposition 7.
Suppose now that
$|\unicode[STIX]{x1D6FC}|+|\unicode[STIX]{x1D6FD}|>2$
. Define
$\unicode[STIX]{x1D719}=\unicode[STIX]{x1D6FC}\oplus 1\oplus \unicode[STIX]{x1D6FD}$
and
$\unicode[STIX]{x1D719}^{-}=\unicode[STIX]{x1D6FC}\oplus \unicode[STIX]{x1D6FD}$
. To prove that
$\unicode[STIX]{x1D719}$
is
$\unicode[STIX]{x1D70E}$
-narrow with
$\unicode[STIX]{x1D70E}$
-core
$\unicode[STIX]{x1D719}^{-}$
, we will show that any permutation
$\unicode[STIX]{x1D6FE}\in [1,\unicode[STIX]{x1D719})\setminus [1,\unicode[STIX]{x1D719}^{-}]$
is a
$\unicode[STIX]{x1D70E}$
-annihilator. Such a
$\unicode[STIX]{x1D6FE}$
has the form
$\unicode[STIX]{x1D6FC}^{\prime }\oplus 1\oplus \unicode[STIX]{x1D6FD}^{\prime }$
for some
$1\leqslant \unicode[STIX]{x1D6FC}^{\prime }\leqslant \unicode[STIX]{x1D6FC}$
and
$1\leqslant \unicode[STIX]{x1D6FD}^{\prime }\leqslant \unicode[STIX]{x1D6FD}$
, with
$|\unicode[STIX]{x1D6FC}^{\prime }|+|\unicode[STIX]{x1D6FD}^{\prime }|<|\unicode[STIX]{x1D6FC}|+|\unicode[STIX]{x1D6FD}|$
; note that we here exclude the cases
$\unicode[STIX]{x1D6FC}^{\prime }=\unicode[STIX]{x1D716}$
and
$\unicode[STIX]{x1D6FD}^{\prime }=\unicode[STIX]{x1D716}$
, because in these cases
$\unicode[STIX]{x1D6FE}$
would be contained in
$\unicode[STIX]{x1D719}^{-}$
. By induction,
$\unicode[STIX]{x1D6FE}$
is
$\unicode[STIX]{x1D70E}$
-narrow, with
$\unicode[STIX]{x1D70E}$
-core
$\unicode[STIX]{x1D6FE}^{-}=\unicode[STIX]{x1D6FC}^{\prime }\oplus \unicode[STIX]{x1D6FD}^{\prime }$
. Moreover,
$\unicode[STIX]{x1D70E}$
has no interval isomorphic to
$\unicode[STIX]{x1D6FE}$
or
$\unicode[STIX]{x1D6FE}^{-}$
: observe that if
$\unicode[STIX]{x1D70E}$
had an interval isomorphic to
$\unicode[STIX]{x1D6FE}$
, it would also have an interval isomorphic to
$\unicode[STIX]{x1D6FC}^{\prime }\oplus 1$
, which is forbidden by our assumptions on
$\unicode[STIX]{x1D70E}$
. Thus, we may apply Proposition 7 to conclude that
$\unicode[STIX]{x1D6FE}$
is a
$\unicode[STIX]{x1D70E}$
-annihilator, and in particular
$\unicode[STIX]{x1D719}$
is
$\unicode[STIX]{x1D70E}$
-narrow with
$\unicode[STIX]{x1D70E}$
-core
$\unicode[STIX]{x1D719}^{-}$
, as claimed. Proposition 7 then gives us that
$\unicode[STIX]{x1D719}$
is a
$\unicode[STIX]{x1D70E}$
-annihilator.◻
Focusing on the special case
$\unicode[STIX]{x1D70E}=1$
, which satisfies the assumptions of Proposition 8 trivially, we obtain the following result.
Corollary 9. For any non-empty permutations
$\unicode[STIX]{x1D6FC}$
and
$\unicode[STIX]{x1D6FD}$
, the permutation
$\unicode[STIX]{x1D6FC}\oplus 1\oplus \unicode[STIX]{x1D6FD}$
is an annihilator.
5 The density of zeros
Our goal is to find an asymptotic positive lower bound on the proportion of permutations of length
$n$
whose principal Möbius function is zero. The key step is the following lemma.
Lemma 10. Let
$s_{n}$
be the number of permutations of size
$n$
with opposing adjacencies. Then
$$\begin{eqnarray}\frac{s_{n}}{n!}=\biggl(1-\frac{1}{e}\biggr)^{2}+O\biggl(\frac{1}{n}\biggr).\end{eqnarray}$$
Proof. Let
$a_{n}$
be the number of permutations of size
$n$
that have no up-adjacency, and let
$b_{n}$
be the number of permutations of size
$n$
that have neither an up-adjacency nor a down-adjacency.
The numbers
$a_{n}$
(sequence A000255 in the OEIS [Reference Sloane13]) have already been studied by Euler [Reference Euler8], and it is known [Reference Rumney and Primrose11] that they satisfy
$a_{n}/n!=e^{-1}+O(n^{-1})$
.
The numbers
$b_{n}$
(sequence A002464 in the OEIS [Reference Sloane13]) satisfy the asymptotics
$b_{n}/n!=e^{-2}+O(n^{-1})$
, which follows from the results of Kaplansky [Reference Kaplansky10] (see also Albert et al [Reference Albert, Atkinson and Klazar2]).
We may now express the number
$s_{n}$
of permutations with opposing adjacencies by inclusion–exclusion as follows: we subtract from
$n!$
the number of permutations having no up-adjacency and the number of permutations having no down-adjacency, and then we add back the number of permutations having no adjacency at all. This yields
$s_{n}=n!-2a_{n}+b_{n}$
, from which the lemma follows by the above-mentioned asymptotics of
$a_{n}$
and
$b_{n}$
.◻
Combining Theorem 6 with Lemma 10 we obtain the following consequence, which is the main result of this section.
Corollary 11. For a given
$n$
and for
$\unicode[STIX]{x1D70B}$
a uniformly random permutation of length
$n$
, the probability that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=0$
is at least
$$\begin{eqnarray}\biggl(1-\frac{1}{e}\biggr)^{2}-O\biggl(\frac{1}{n}\biggr).\end{eqnarray}$$
6 More complicated examples
We will now construct several specific examples of annihilators and annihilator pairs, which are not covered by the general results obtained in the previous sections. We begin with a construction of four new annihilator pairs, which we will later use to construct new annihilators.
Theorem 12. The two permutations
$213$
and
$2431$
form an annihilator pair.
Proof. Our proof is based on the concept of normal embeddings and follows a similar structure as the normal embedding proof of Theorem 6.
Suppose for contradiction that there is a permutation
$\unicode[STIX]{x1D70B}$
that contains an interval isomorphic to
$213$
as well as an interval isomorphic to
$2431$
, and that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]\neq 0$
. Fix a smallest possible
$\unicode[STIX]{x1D70B}$
, and let
$n$
be its length. Note that an interval isomorphic to
$213$
is necessarily disjoint from an interval isomorphic to
$2431$
, and in particular,
$n\geqslant 7$
.
Let
$i$
,
$i+1$
and
$i+2$
be three positions of
$\unicode[STIX]{x1D70B}$
containing an interval copy of
$213$
, and let
$j$
,
$j+1$
,
$j+2$
and
$j+3$
be four positions containing an interval copy of
$2431$
. We will apply the approach of Proposition 5, with
$\unicode[STIX]{x1D70E}=1$
. We will say that an embedding
$f\in {\mathcal{E}}(\ast ,\unicode[STIX]{x1D70B})$
is normal if
$\text{Img}(f)$
is a superset of
$[n]\setminus \{i+2,j+2,j+3\}$
. Informally, the image of a normal embedding contains all the positions of
$\unicode[STIX]{x1D70B}$
, except possibly some of the three positions that correspond to the value
$3$
of
$213$
or the values
$3$
and
$1$
of
$2431$
in the chosen interval copies of
$213$
and
$2431$
, as shown in Figure 3. In particular, there are eight normal embeddings.
The intervals
$213$
and
$2431$
in Theorem 12. Normal embeddings may omit some of the hollow points.
We now verify the assumptions of Proposition 5. We obviously have
${\mathcal{N}}{\mathcal{E}}(\unicode[STIX]{x1D70B},\unicode[STIX]{x1D70B})={\mathcal{E}}(\unicode[STIX]{x1D70B},\unicode[STIX]{x1D70B})$
. The main task is to verify, for a given
$\unicode[STIX]{x1D706}\in [1,\unicode[STIX]{x1D70B})$
with
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D706}]\neq 0$
, the identity (2) of Proposition 5, that is, the identity
$|{\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{odd},\unicode[STIX]{x1D70B})|=|{\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{even},\unicode[STIX]{x1D70B})|$
.
Fix a
$\unicode[STIX]{x1D706}\in [1,\unicode[STIX]{x1D70B})$
such that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D706}]\neq 0$
, and let
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
be the set
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{odd},\unicode[STIX]{x1D70B})\cup {\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\text{even},\unicode[STIX]{x1D70B})$
. We will describe a sign-reversing involution
$\unicode[STIX]{x1D6F7}_{\unicode[STIX]{x1D706}}$
on
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
. The involution
$\unicode[STIX]{x1D6F7}_{\unicode[STIX]{x1D706}}$
will always be equal to a switch operation
$\unicode[STIX]{x1D6E5}_{k}$
, where the choice of
$k$
will depend on
$\unicode[STIX]{x1D706}$
.
Suppose first that
$\unicode[STIX]{x1D706}$
does not contain any down-adjacency. We claim that
$\unicode[STIX]{x1D6E5}_{j+2}$
is an involution on the set
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
. To see this, choose
$f\in {\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
and define
$g=\unicode[STIX]{x1D6E5}_{j+2}(f)$
. It is clear that
$g$
is a normal embedding.
To prove that
$g$
belongs to
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
, it remains to show that
$\text{src}(g)$
contains
$\unicode[STIX]{x1D706}$
, or equivalently, that there is an embedding of
$\unicode[STIX]{x1D706}$
into
$\unicode[STIX]{x1D70B}$
that is contained in
$g$
. Let
$h$
be an embedding of
$\unicode[STIX]{x1D706}$
into
$\unicode[STIX]{x1D70B}$
, which is contained in
$f$
. If
$j+2\not \in \text{Img}(h)$
, then
$h$
is also contained in
$g$
and we are done.
Suppose then that
$j+2\in \text{Img}(h)$
. This means that
$j+1$
is not in
$\text{Img}(h)$
, because
$\unicode[STIX]{x1D70B}$
has a down-adjacency at positions
$j+1$
and
$j+2$
, while
$\unicode[STIX]{x1D706}$
has no down-adjacency. We now modify
$h$
in such a way that the element previously mapped to
$j+2$
will be mapped to
$j+1$
, while the mapping of the remaining elements remains unchanged. Let
$h^{\prime }$
be the embedding obtained from
$h$
by this modification; formally, we have
$h^{\prime }=\unicode[STIX]{x1D6E5}_{j+1}(\unicode[STIX]{x1D6E5}_{j+2}(h))$
. Since the two elements
$\unicode[STIX]{x1D70B}_{j+1}$
and
$\unicode[STIX]{x1D70B}_{j+2}$
form an adjacency, we have
$\text{src}(h^{\prime })=\text{src}(h)=\unicode[STIX]{x1D706}$
. Moreover,
$h^{\prime }$
is contained in
$g$
(recall that
$g$
is normal, and therefore
$\text{Img}(g)$
contains
$j+1$
). Consequently,
$g$
is in
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
, as claimed.
We now deal with the case when
$\unicode[STIX]{x1D706}$
contains a down-adjacency. Since
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D706}]\neq 0$
, it follows by Theorem 6 that
$\unicode[STIX]{x1D706}$
has no up-adjacency. We distinguish two subcases, depending on whether
$\unicode[STIX]{x1D706}$
contains an interval copy of
$2431$
.
Suppose that
$\unicode[STIX]{x1D706}$
contains an interval copy of
$2431$
. We will prove that in this case,
$\unicode[STIX]{x1D6E5}_{i+2}$
is a sign-reversing involution on
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
. We begin by observing that
$\unicode[STIX]{x1D706}$
has no interval copy of
$213$
, otherwise
$\unicode[STIX]{x1D706}$
would be a counterexample to Theorem 12, contradicting the minimality of
$\unicode[STIX]{x1D70B}$
. Fix again an embedding
$f\in {\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
, and define
$g=\unicode[STIX]{x1D6E5}_{i+2}(f)$
. As in the previous case,
$g$
is clearly normal, and we only need to show that there is an embedding of
$\unicode[STIX]{x1D706}$
into
$\unicode[STIX]{x1D70B}$
contained in
$g$
. Let
$h$
be an embedding of
$\unicode[STIX]{x1D706}$
into
$\unicode[STIX]{x1D70B}$
contained in
$f$
. If
$i+2\not \in \text{Img}(h)$
, then
$h$
is contained in
$g$
and we are done, so suppose
$i+2\in \text{Img}(h)$
. If at least one of the two positions
$i$
and
$i+1$
belongs to
$\text{Img}(h)$
, then
$\unicode[STIX]{x1D706}$
contains an up-adjacency or an interval copy of
$213$
, contradicting our assumptions. Therefore, we can modify
$h$
so that the element mapped to
$i+2$
is mapped to
$i$
instead, obtaining an embedding of
$\unicode[STIX]{x1D706}$
contained in
$g$
and showing that
$g\in {\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
.
Finally, suppose that
$\unicode[STIX]{x1D706}$
has no interval copy of
$2431$
. In this case, we prove that
$\unicode[STIX]{x1D6E5}_{j+3}$
is the required involution on
${\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
. As in the previous cases, we fix
$f\in {\mathcal{N}}{\mathcal{E}}_{\unicode[STIX]{x1D706}}(\ast ,\unicode[STIX]{x1D70B})$
, define
$g=\unicode[STIX]{x1D6E5}_{j+3}(f)$
and let
$h$
be an embedding of
$\unicode[STIX]{x1D706}$
contained in
$f$
; we again want to modify
$h$
into an embedding
$\unicode[STIX]{x1D706}$
contained in
$g$
. Let
$\unicode[STIX]{x1D6FC}$
be the subpermutation of
$\unicode[STIX]{x1D706}$
formed by those positions that are mapped into the set
$J=\{j,j+1,j+2,j+3\}$
by
$h$
. Recall that the positions in
$J$
induce an interval copy of
$2431$
in
$\unicode[STIX]{x1D70B}$
. In particular,
$\unicode[STIX]{x1D6FC}\leqslant 2431$
, and
$\unicode[STIX]{x1D706}$
has an interval copy of
$\unicode[STIX]{x1D6FC}$
. We know that
$\unicode[STIX]{x1D6FC}\neq 2431$
, since we assume that
$\unicode[STIX]{x1D706}$
has no interval copy of
$2431$
. Also,
$\unicode[STIX]{x1D6FC}\neq 321$
, since
$321$
is an annihilator by Corollary 9, while
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D706}]\neq 0$
. Finally,
$\unicode[STIX]{x1D6FC}\neq 231$
, since
$\unicode[STIX]{x1D706}$
has no up-adjacency. This implies that
$\unicode[STIX]{x1D6FC}\leqslant 132$
, and we can modify
$h$
so that all the positions originally mapped into
$J$
will get mapped into
$J\setminus \{j+3\}$
, obtaining an embedding of
$\unicode[STIX]{x1D706}$
into
$\unicode[STIX]{x1D70B}$
contained in
$g$
.
Having thus verified the assumptions of Proposition 5, we can conclude that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=(-1)^{|\unicode[STIX]{x1D70B}|-1}\text{NE}(1,\unicode[STIX]{x1D70B})=0$
, a contradiction.◻
The following three results are proved using similar methods to those used in the proof of Theorem 12.
Theorem 13. The permutations
$2143$
and
$2431$
form an annihilator pair.
Theorem 14. The permutations
$312$
and
$23514$
form an annihilator pair.
Theorem 15. The permutations
$25134$
and
$23514$
form an annihilator pair.
We omit the proofs here, but they can be found in an extended version of this paper [Reference Brignall, Jelínek, Kynčl and Marchant5].
With the help of the new annihilator pairs established in Theorems 12 to 15, we are able to present several new examples of annihilators.
The three annihilators from Theorem 16, and the posets of their subpermutations. The figures omit the permutations with opposing adjacencies, as well as the permutations with an interval copy of a permutation of the form
$\unicode[STIX]{x1D6FC}\oplus 1\oplus \unicode[STIX]{x1D6FD}$
.
Theorem 16. Each of the three permutations
$215463$
,
$236145$
and
$214653$
is a Möbius annihilator.
Proof. We first present the proof for the permutation
$215463$
. Let
$\unicode[STIX]{x1D6FC}=215463$
,
$\unicode[STIX]{x1D6FD}=\unicode[STIX]{x1D6FC}_{1}[\unicode[STIX]{x1D716}]=14352$
,
$\unicode[STIX]{x1D6FD}^{\prime }=\unicode[STIX]{x1D6FC}_{6}[\unicode[STIX]{x1D716}]=21435$
and
$\unicode[STIX]{x1D6FE}=\unicode[STIX]{x1D6FC}_{1,6}[\unicode[STIX]{x1D716},\unicode[STIX]{x1D716}]=1324$
. From Figure 4 (left) we see that, after the removal of the annihilators
$\unicode[STIX]{x1D6FC}_{3}[\unicode[STIX]{x1D716}],\unicode[STIX]{x1D6FC}_{4}[\unicode[STIX]{x1D716}]$
and
$\unicode[STIX]{x1D6FC}_{5}[\unicode[STIX]{x1D716}]$
, the interval
$[1,\unicode[STIX]{x1D6FC}]$
becomes diamond-tipped with core
$(\unicode[STIX]{x1D6FD},\unicode[STIX]{x1D6FD}^{\prime },\unicode[STIX]{x1D6FE})$
. Hence by Facts 1 and 2 we have
$\unicode[STIX]{x1D707}[1,\unicode[STIX]{x1D6FC}]=0$
.
Let
$\unicode[STIX]{x1D70B}$
be a permutation of the form
$\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FC}]$
for some
$\unicode[STIX]{x1D70F}$
and
$i\leqslant |\unicode[STIX]{x1D70F}|$
. We will show, by induction on
$|\unicode[STIX]{x1D70F}|$
, that
$\unicode[STIX]{x1D70B}$
is a zero. The case
$|\unicode[STIX]{x1D70F}|=1$
has been proved in the previous paragraph.
Assume that
$|\unicode[STIX]{x1D70F}|>1$
. We will demonstrate that we can remove some zeros from the interval
$[1,\unicode[STIX]{x1D70B}]$
to end up with a diamond-tipped interval with core
$(\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FD}],\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FD}^{\prime }],\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FE}])$
. Choose a
$\unicode[STIX]{x1D706}\in [1,\unicode[STIX]{x1D70B})$
. We can then write
$\unicode[STIX]{x1D706}$
as
$\unicode[STIX]{x1D706}=\unicode[STIX]{x1D70F}_{j}^{\ast }[\unicode[STIX]{x1D6FC}^{\ast }]$
for some
$\unicode[STIX]{x1D70F}^{\ast }\leqslant \unicode[STIX]{x1D70F}$
and some (possibly empty)
$\unicode[STIX]{x1D6FC}^{\ast }\leqslant \unicode[STIX]{x1D6FC}$
, where
$\unicode[STIX]{x1D70F}^{\ast }$
has an embedding into
$\unicode[STIX]{x1D70F}$
mapping
$j$
to
$i$
.
If
$\unicode[STIX]{x1D6FC}^{\ast }$
is an annihilator, then
$\unicode[STIX]{x1D706}$
is a zero and can be removed. If
$\unicode[STIX]{x1D6FC}^{\ast }=\unicode[STIX]{x1D6FC}$
, then
$|\unicode[STIX]{x1D70F}^{\ast }|<|\unicode[STIX]{x1D70F}|$
, and by induction,
$\unicode[STIX]{x1D706}$
is a zero and can be removed. In all the other cases, we have
$\unicode[STIX]{x1D6FC}^{\ast }\leqslant \unicode[STIX]{x1D6FD}$
or
$\unicode[STIX]{x1D6FC}^{\ast }\leqslant \unicode[STIX]{x1D6FD}^{\prime }$
, and in particular,
$\unicode[STIX]{x1D706}$
belongs to
$[1,\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FD}]]\cup [1,\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FD}^{\prime }]]$
.
Suppose now that
$\unicode[STIX]{x1D706}$
is in
$[1,\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FD}]]\cap [1,\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FD}^{\prime }]]$
but not in
$[1,\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FE}]]$
. Since
$\unicode[STIX]{x1D706}\leqslant \unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FD}]$
, we can write it as
$\unicode[STIX]{x1D706}=\unicode[STIX]{x1D70F}_{j}^{L}[\unicode[STIX]{x1D6FD}^{L}]$
, for some
$\unicode[STIX]{x1D70F}^{L}\leqslant \unicode[STIX]{x1D70F}$
and
$\unicode[STIX]{x1D6FD}^{L}\leqslant \unicode[STIX]{x1D6FD}$
, where
$\unicode[STIX]{x1D70F}^{L}$
has an embedding into
$\unicode[STIX]{x1D70F}$
mapping
$j$
to
$i$
. Since
$\unicode[STIX]{x1D706}\not \leqslant \unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FE}]$
, we know that
$\unicode[STIX]{x1D6FD}^{L}\not \leqslant \unicode[STIX]{x1D6FE}$
. This means that
$\unicode[STIX]{x1D6FD}^{L}\in [1,\unicode[STIX]{x1D6FD}]\setminus [1,\unicode[STIX]{x1D6FE}]=\{14352,3241,1342,231\}$
. Similarly,
$\unicode[STIX]{x1D706}\in [1,\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FD}^{\prime }]]\setminus [1,\unicode[STIX]{x1D70F}_{i}[\unicode[STIX]{x1D6FE}]]$
means that
$\unicode[STIX]{x1D706}$
can be written as
$\unicode[STIX]{x1D706}=\unicode[STIX]{x1D70F}_{k}^{R}[\unicode[STIX]{x1D6FD}^{R}]$
, with
$\unicode[STIX]{x1D6FD}^{R}\in \{21435,2143\}$
. Since
$\unicode[STIX]{x1D706}$
has an interval copy of
$\unicode[STIX]{x1D6FD}^{L}$
as well as an interval copy of
$\unicode[STIX]{x1D6FD}^{R}$
, Theorem 6 shows that
$\unicode[STIX]{x1D706}$
is a zero if
$\unicode[STIX]{x1D6FD}^{L}\in \{1342,231\}$
, and Theorem 13 shows that
$\unicode[STIX]{x1D706}$
is a zero if
$\unicode[STIX]{x1D6FD}^{L}\in \{14352,3241\}$
(using that
$3241$
is a diagonal reflection of
$2431$
). Therefore,
$\unicode[STIX]{x1D706}$
can be removed.
After the removal described above,
$[1,\unicode[STIX]{x1D70B}]$
is transformed into a diamond-tipped interval, showing that
$\unicode[STIX]{x1D70B}$
is a zero.
The arguments for the other two permutations are completely analogous. For
$236145$
we have
$\unicode[STIX]{x1D6FC}=236145$
,
$\unicode[STIX]{x1D6FD}=25134$
,
$\unicode[STIX]{x1D6FD}^{\prime }=23514$
,
$\unicode[STIX]{x1D6FE}=2413$
,
$\unicode[STIX]{x1D6FD}^{L}\in \{25134,1423\}$
and
$\unicode[STIX]{x1D6FD}^{R}\in \{23514,2314\}$
, and use Theorems 12, 14 and 15. For
$214653$
we have
$\unicode[STIX]{x1D6FC}=214653$
,
$\unicode[STIX]{x1D6FD}=13542$
,
$\unicode[STIX]{x1D6FD}^{\prime }=2143$
,
$\unicode[STIX]{x1D6FE}=132$
,
$\unicode[STIX]{x1D6FD}^{L}\in \{13542,2431,1342,231\}$
and
$\unicode[STIX]{x1D6FD}^{R}\in \{2143,213\}$
, and use Theorems 6, 12 and 13.◻
The annihilator
$215463$
of Theorem 16 can be written as a sum of two intervals, namely
$215463=21\oplus 3241$
. One might wonder whether the two summands are in fact an annihilator pair. This, however, is not the case, as evidenced by the permutation
$32417685=3241\oplus 3241$
, which is not a Möbius zero. An analogous example applies to
$214653=21\oplus 2431$
.
In the proof of Theorem 16, it was crucial that for each
$\unicode[STIX]{x1D6FC}\in \{215463,236145,214653\}$
, the interval
$[1,\unicode[STIX]{x1D6FC}]$
becomes diamond-tipped after the removal of some annihilators. However, this property alone is not sufficient to make a permutation
$\unicode[STIX]{x1D6FC}$
an annihilator. Consider, for instance, the permutation
$\unicode[STIX]{x1D6FC}=214635$
. We may routinely check that by removing some annihilators, the interval
$[1,\unicode[STIX]{x1D6FC}]$
can be made diamond-tipped with core
$(\unicode[STIX]{x1D6FD}=13524,\unicode[STIX]{x1D6FD}^{\prime }=21435,\unicode[STIX]{x1D6FE}=1324)$
. This implies that
$\unicode[STIX]{x1D6FC}$
is a Möbius zero by Facts 1 and 2; however, it does not imply that
$\unicode[STIX]{x1D6FC}$
is an annihilator. In fact,
$\unicode[STIX]{x1D6FC}$
is not an annihilator, as demonstrated by the permutation
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D70B} & = & \displaystyle 582741936_{2,4,5}[\unicode[STIX]{x1D6FD},\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}^{\prime }]\nonumber\\ \displaystyle & = & \displaystyle 9,17,19,21,18,20,2,12,11,14,16,13,15,5,4,7,6,8,1,22,3,10,\nonumber\end{eqnarray}$$
whose principal Möbius function is 1, not 0. This example also shows that not all Möbius zeros are annihilators.
In fact, among permutations of size at most 6, there are up to symmetry four Möbius zeros that are not annihilators. Apart from the permutation
$214635$
pointed out above, there are these three more examples:
$235614$
,
$254613$
and
$465213$
. To see that these three permutations are not annihilators, it suffices to check that for any
$\unicode[STIX]{x1D6FC}\in \{235614,254613,465213\}$
, the permutation
$24153_{2}[\unicode[STIX]{x1D6FC}]$
has a non-zero principal Möbius function. We verified, with the help of a computer, that all the Möbius zeros of size at most 6 that are not symmetries of the four examples above can be shown to be annihilators by our results. This data is available at https://iuuk.mff.cuni.cz/∼jelinek/mf/zeros.txt.
7 Concluding remarks
Given Theorem 6, it is natural to wonder if we can find a similar result that applies to a permutation with multiple adjacencies, but no opposing adjacencies. One difficulty here is that there are permutations that have multiple adjacencies, and do not have opposing adjacencies, where the principal Möbius function value is non-zero. As an example, any permutation
$\unicode[STIX]{x1D70B}=2,1,4,3,\ldots ,2k,2k-1=\bigoplus ^{k}21$
has
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=-1$
by the results of Burstein et al [Reference Burstein, Jelínek, Jelínková and Steingrímsson7, Corollary 3].
Let
$d_{n}$
be the “density of zeros” of the Möbius function, that is, the probability that
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=0$
for a uniformly random permutation
$\unicode[STIX]{x1D70B}$
of size
$n$
. The asymptotic behaviour of
$d_{n}$
is still elusive.
Problem 17. Does the limit
$\lim _{n\rightarrow \infty }d_{n}$
exist? And if it does, what is its value?
Corollary 11 implies that
$\liminf _{n\rightarrow \infty }d_{n}\geqslant (1-1/e)^{2}\geqslant 0.3995$
. We have no upper bound on
$d_{n}$
apart from the trivial bound
$d_{n}\leqslant 1$
, but computational data suggest that simple permutations very often (though not always) have a non-zero principal Möbius function, where a permutation
$\unicode[STIX]{x1D70B}$
is simple if all its intervals have size 1 or
$|\unicode[STIX]{x1D70B}|$
. Since a random permutation is simple with probability approaching
$1/e^{2}$
[Reference Albert, Atkinson and Klazar2], this would suggest that
$\limsup _{n\rightarrow \infty }d_{n}$
is at most
$1-1/e^{2}\approx 0.8647$
.
The density of Möbius zeros among permutations of length
$n$
, with
$n=1,\ldots ,13$
.
Table 1 lists the values of
$d_{n}$
for
$n=1,\ldots ,13$
. The values are based on data supplied by Smith [Reference Smith17] for
$1\leqslant n\leqslant 9$
, and calculations performed by the fourth author. Data files with the values of the principal Möbius function for all permutations of length 12 or less are available from https://doi.org/10.21954/ou.rd.7171997.v2. Based on this somewhat limited numeric evidence, we make the following conjecture.
Conjecture 18. The values
$d_{n}$
are bounded from above by 0.6040.
It is natural to look for further ways to identify Möbius zeros and Möbius annihilators. Characterizing all the Möbius zeros would be an ambitious goal, since
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]$
might be zero as a result of “accidental” cancellations with no deeper structural significance for
$\unicode[STIX]{x1D70B}$
.
An annihilator multiset is a multiset of permutations
$A=\{\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{n}\}$
such that any permutation
$\unicode[STIX]{x1D70B}$
that contains disjoint interval copies of the permutations
$\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{n}$
has
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=0$
.
If
$A=\{\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{n}\}$
and
$B=\{\unicode[STIX]{x1D6FD}_{1},\ldots ,\unicode[STIX]{x1D6FD}_{m}\}$
are annihilator multisets, then we say that
$A$
contains
$B$
if
$A\neq B$
and we can find the elements of
$B$
as disjoint interval copies in the elements of
$A$
. An annihilator multiset
$A$
is minimal if there is no annihilator multiset contained in
$A$
.
Using [Reference Burstein, Jelínek, Jelínková and Steingrímsson7, Corollary 3], which implies
$\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}]=\unicode[STIX]{x1D707}[\unicode[STIX]{x1D70B}\oplus \unicode[STIX]{x1D70B}]$
for
$\unicode[STIX]{x1D70B}\neq 1$
, it is simple to show that the permutations in a minimal annihilator multiset are, in fact, all distinct, and so we can refer to minimal annihilator sets of permutations.
Problem 19. Which permutations are Möbius annihilators? Are there infinitely many minimal annihilator sets that contain just one element, and are not of the form
$\unicode[STIX]{x1D6FC}\oplus 1\oplus \unicode[STIX]{x1D6FD}$
?
It seems likely to us that the proofs of Theorems 12–15 might be extended to give several more annihilator pairs, such as
$(312,235614)$
. However, we do not see any general pattern in these examples yet.
Problem 20. Are there infinitely many minimal annihilator sets with two elements?
Problem 21. Are there any minimal annihilator sets with more than two elements?
Acknowledgments
We wish to thank Ida Kantor and Martin Tancer for helpful comments. We would also like to thank the anonymous reviewer for their feedback and suggestions.
