1. Introduction
The interplay between densities of substructures and particularly determining the extremal points of the region of feasible densities is a theme underlying a large body of problems in extremal combinatorics. A fundamental question related to the region of feasible densities, which traces back to Whitney’s work [ Reference Whitney49 ] on the number of subgraphs with a given number of vertices and edges, is determining its number of degrees of freedom, i.e., its dimension. For example, while not obvious at first sight, the densities of all four 3-vertex graphs are determined by any two of them. In the late 1970s, Erdős, Lovász and Spencer [ Reference Erdős, Lovász and Spencer16 ] determined the dimension of the region of feasible subgraph/homomorphic densities of graphs. They showed that homomorphic densities of non-trivial connected graphs are independent and the density of any other graph is a function of densities of non-trivial connected graphs. The aim of this paper is to determine the dimension of the region of feasible pattern densities of permutations, where we describe a behaviour that unexpectedly differs from the graph case in a substantial way. In particular, in addition to being “connected” (which is captured as being indecomposable in the context of permutations), the linear order inherent to permutations plays an essential role in the number of degrees of freedom, which is manifested by a connection to algebraic and combinatorial properties of Lyndon words that we exploit.
We now state the above mentioned results on graphs and our new results on permutations formally using the language of the theory of combinatorial limits which we use throughout the paper. In the theory of combinatorial limits, large graphs are represented by an analytic object called a graphon and large permutations by an analytic object called a permuton (we refer the reader to Subsections 2·1 and 2·3 for definitions as needed). Let
${\mathcal{G}}_k$
be the set of all graphs with at most k vertices and
${\mathcal{G}}^C_k$
be the set of all connected graphs with at least two and at most k vertices. Erdős, Lovász and Spencer [
Reference Erdős, Lovász and Spencer16
] showed the following:
Theorem 1 (Erdős, Lovász and Spencer [
Reference Erdős, Lovász and Spencer16
]). For every
$k\ge 2$
, there exist
$x_0\in [0,1]^{{\mathcal{G}}^C_k}$
and
$\varepsilon \gt 0$
such that for every
$x\in B_{\varepsilon}(x_0)\subseteq [0,1]^{{\mathcal{G}}^C_k}$
, there exists a graphon W such that
\[t(G,W)_{G\in{\mathcal{G}}^C_k}=x.\]
Moreover, there exists a polynomial function
$f\;:\;[0,1]^{{\mathcal{G}}^C_k}\to [0,1]^{{\mathcal{G}}_k}$
such that the following holds for every graphon W:
\[f(t(G,W)_{G\in{\mathcal{G}}^C_k})=t(G,W)_{G\in{\mathcal{G}}_k}.\]
In other words, the densities of non-trivial connected graphs are independent, and moreover the homomorphic density of any other graph is a polynomial function of homomorphic densities of connected graphs. Therefore, the dimension of the feasible region of homomorphic densities of graphs with at most k vertices in large graphs is actually equal to the number of non-trivial connected graphs with at most k vertices.
Indecomposable permutations, i.e., permutations that cannot be expressed as the direct sum of two permutations, play the role of connected graphs in the realm of permutations, and it is plausible to assume that the dimension would be equal to the number of indecomposable permutations. Let
${\mathcal{P}}_k$
be the set of all permutations of size at most k, and let
${\mathcal{P}}^I_k$
be the set of all non-trivial indecomposable permutations of size at most k. Glebov et al. [
Reference Glebov, Hoppen, Klimošová, Kohayakawa, Král’ and Liu19
] showed that for every
$k\in{\mathbb {N}}$
, there exist
$x_0\in [0,1]^{{\mathcal{P}}^I_k}$
and
$\varepsilon \gt 0$
such that for every
$x\in B_{\varepsilon}(x_0)\subseteq [0,1]^{{\mathcal{P}}^I_k}$
there exists a permuton
$\Pi$
such that
$d(\sigma,\Pi)_{\sigma\in{\mathcal{P}}^I_k}=x$
, i.e., the densities of indecomposable permutations are independent in the analogy to the graph case covered by Theorem 1. However, the bound is not tight already for 3-point patterns: the dimension is five although there are only four non-trivial indecomposable permutations of size at most three.
Borga and the last author [
Reference Borga and Penaguiao6, Reference Borga and Penaguiao7
] studied the dimension of the feasible region of densities of patterns of size at most k and observed, utilising a result of Vargas [
Reference Vargas48
], a link between the dimension and Lyndon permutations. We say that a permutation is Lyndon if the word formed by its indecomposable blocks is Lyndon (a formal definition is given in Subsection 2·4), and use
${\mathcal{P}}^L_k$
for the set of all non-trivial Lyndon permutations of size at most k. In particular, they noted that the dimension of the region of feasible pattern densities is at most the number of non-trivial Lyndon permutations [
Reference Borga and Penaguiao6
], and conjectured [
Reference Borga and Penaguiao6
, conjecture 1·3] that this bound is tight. We combine methods from algebra and combinatorics to prove this conjecture; note that the set
${\mathcal{P}}^L_k$
of non-trivial Lyndon permutations is a superset of
${\mathcal{P}}^I_k$
of non-trivial indecomposable permutations.
Theorem 2. For every integer
$k\ge 2$
, there exists
$x_0\in [0,1]^{{\mathcal{P}}^L_k}$
and
$\varepsilon \gt 0$
such that for every
$x\in B_\varepsilon(x_0)\subseteq [0,1]^{{\mathcal{P}}^L_k}$
there exists a permuton
$\Pi$
such that
\[d(\sigma,\Pi)_{\sigma\in{\mathcal{P}}^L_k}=x.\]
Theorem 2 determines the dimension of the feasible region of densities of patterns of size at most k in large permutations. Since the statement that there exists a polynomial function
$f\;:\;[0,1]^{{\mathcal{P}}^L_k}\to [0,1]^{{\mathcal{P}}_k}$
such that, for every permuton
$\Pi$
, we have
$f(d(\sigma,\Pi)_{\sigma\in{\mathcal{P}}^L_k})=d(\sigma,W)_{\sigma\in{\mathcal{P}}_k}$
, is given in [
Reference Borga and Penaguiao6
] without particular details, we give a direct proof of the existence of the function f in Section 4 (Theorem 8) for completeness. The presented proof (unlike the one suggested in [
Reference Borga and Penaguiao6
]) uses only basic properties of Lyndon words and flag algebras, which are surveyed in Subsections 2·4 and 2·5. We remark that properties of Lyndon words seem to capture independence of “order-like” combinatorial structures and the ideas presented in this paper were followed in [
Reference Král’, Lamaison, Prorok and Shu29
] to determine the dimension of the feasible region of densities of subtournaments in large tournaments.
2. Preliminaries
We now introduce notation used throughout this manuscript. As we combine techniques from several different areas, we introduce the relevant techniques from each of the areas in one of the subsections that follow. Before doing so, we first fix some general notation. The set of the first n positive integers is denoted by [n], and if A is a set of integers and
$k\in{\mathbb {N}}$
, then
$A+k$
is the set
$\{a+k,a\in A\}$
. A subset A of integers is an interval if A consists of consecutive integers, i.e., there exist integers
$a,b\in{\mathbb {N}}$
,
$a\leq b$
, such that
$A=\{a,a+1,\ldots,b\}$
. Finally, two subsets I and J of integers are non-crossing if
$\max(I) \lt \min(J)$
or vice versa.
2·1. Graph limits
We now introduce basic notations related to graph limits as developed in particular in [
Reference Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi8–Reference Borgs, Chayes, Lovász, Sós and Vesztergombi10, Reference Lovász and Szegedy35, Reference Lovász and Szegedy36
]; we refer to the monograph by Lovász [
Reference Lovász34
] for a comprehensive introduction to graph limits. Given two graphs H and G, we say a map
$\phi\;:\;V(H)\rightarrow V(G)$
is a homomorphism if it preserves edges, i.e. if
$\phi(x)\phi(y)\in E(G)$
whenever
$xy\in E(H)$
. The homomorphic density of H in G, denoted by t(H, G), is the probability that a uniform random function
$f\;:\;V(H)\to V(G)$
, is a homomorphism of H to G. A sequence
$(G_n)_{n\in{\mathbb {N}}}$
of graphs is convergent if the number of vertices of
$G_n$
tends to infinity and, for every fixed H, the sequence of densities
$t(H,G_n)$
converges as n tends to infinity.
Convergent sequences of graphs are represented by an analytic object called a graphon: this is a symmetric measurable function
$W\;:\;[0,1]^2\to [0,1]$
, i.e.,
$W(x,y)=W(y,x)$
for
$(x,y)\in [0,1]^2$
. The homomorphic density of a graph H in a graphon W is defined by
\[t(H,W)=\int_{[0,1]^{V(H)}}\prod_{uv\in E(H)}W(x_u,x_v){\text{d}} x_{V(H)}.\]
We often just briefly say the density of a graph H in W rather than the homomorphic density of H in W. A graphon W is a limit of a convergent sequence
$(G_n)_{n\in{\mathbb {N}}}$
of graphs if, for every graph H, t(H, W) is the limit of
$(t(H,G_n))_{n\in\mathbb N}$
. Every convergent sequence of graphs has a limit graphon and every graphon is a limit of a convergent sequence of graphs as shown by Lovász and Szegedy [
Reference Lovász and Szegedy35
]; also see [
Reference Diaconis and Janson15
] for a relation to exchangeable arrays.
2·2. Permutations
A permutation of size n is a bijective function
$\pi$
from [n] to [n]; the size of
$\pi$
is denoted by
$\lvert\pi\rvert$
. The permutation
$\pi$
is represented as a word
$\pi(1)\pi(2)\ldots\pi(n)$
, e.g., 123 stands for the identity permutation of size 3. We say that a permutation is non-trivial if its size is at least two. The set of all permutations of size at most k is denoted by
${\mathcal{P}}_k$
, e.g.,
${\mathcal{P}}_3=\{1,12,21,123,132,213,231,312,321\}$
.
The direct sum of two permutations
$\pi_1$
and
$\pi_2$
is the permutation
$\pi$
of size
$\lvert\pi_1\rvert+\lvert\pi_2\rvert$
such that
$\pi(k)=\pi_1(k)$
for
$k\in[\lvert\pi_1\rvert]$
and
$\pi(\lvert\pi_1\rvert+k)=\lvert\pi_1\rvert+\pi_2(k)$
for
$k\in[\lvert\pi_2\rvert]$
; the permutation
$\pi$
is denoted by
$\pi_1\oplus\pi_2$
. A permutation is indecomposable if it is not a direct sum of two permutations. Every permutation
$\pi$
is a direct sum of indecomposable permutations (possibly with repetitions), which are referred to as the indecomposable blocks of the permutation
$\pi$
. For example, the permutation
$321645987=321\oplus 312\oplus 321$
consists of three indecomposable blocks. An increasing segment of a permutation
$\pi$
is an inclusion-wise maximal interval
$A\subseteq [\lvert\pi\rvert]$
such that
$\pi(a+1)=\pi(a)+1$
for every
$a\in A$
such that
$a+1\in A$
. For example, the permutation 312456 consists of three increasing segments.
The pattern induced by elements
$1\leq k_1 \lt \cdots \lt k_m\leq n$
in a permutation
$\pi$
is the unique permutation
$\sigma\;:\;[m]\to [m]$
such that
$\sigma(i) \lt \sigma(i')$
if and only if
$\pi(k_i) \lt \pi(k_{i'})$
for all
$i,i'\in [m]$
. The density of a permutation
$\sigma$
in a permutation
$\pi$
, denoted by
$d(\sigma,\pi)$
, is the probability that the pattern induced by
$\lvert\sigma\rvert$
uniformly randomly chosen elements of
$[\lvert\pi\rvert]$
in
$\pi$
is the permutation
$\sigma$
. Similarly to the graph case, we say that a sequence
$(\pi_n)_{n\in{\mathbb {N}}}$
of permutations is convergent if the size of
$\pi_n$
tends to infinity and, for every fixed
$\sigma$
, the sequence of densities
$d(\sigma,\pi_n)$
converges as n tends to infinity.
2·3. Permutation limits
We now introduce analytic representations of convergent sequences of permutations as originated in [
Reference Hoppen, Kohayakawa, de, Moreira, Ráth and Sampaio26, Reference Hoppen, Kohayakawa, de, Moreira and Sampaio27, Reference Král’ and Pikhurko32
] and further developed in [
Reference Balogh, Hu, Lidický, Pikhurko, Udvari and Volec5, Reference Chan, Král’, Noel, Pehova, Sharifzadeh and Volec11, Reference Garbe, Hladký, Kun and Pekárková17, Reference Glebov, Grzesik, Klimošová and Král’18, Reference Kenyon, Král’, Radin and Winkler28, Reference Kurečka33
]. A permuton is a probability measure
$\Pi$
on the
$\sigma$
-algebra of Borel subsets from
$[0,1]^2$
that has uniform marginals, i.e.,
\[\Pi([a,b]\times[0,1]) = \Pi([0,1]\times[a,b]) = b - a\]
for all
$0\leq a\leq b\leq 1$
(equivalently, its projection on each of the two dimensions is the uniform measure). A
$\Pi$
-random permutation of size n is the permutation
$\sigma$
obtained by sampling n points according to the measure
$\Pi$
(note that the x-coordinates and y-coordinates of the sampled points are pairwise distinct with probability 1), sorting them according to their x-coordinates, say
$(x_1,y_1),\ldots,(x_n,y_n)$
for
$x_1\lt \cdots \lt x_n$
, and defining
$\sigma$
so that
$\sigma(i) \lt \sigma(j)$
if and only if
$y_i \lt y_j$
for
$i,j\in [n]$
. The density of a permutation
$\sigma$
in a permuton
$\Pi$
, which is denoted by
$d(\sigma,\Pi)$
, is the probability that the
$\Pi$
-random permutation of size
$|\sigma|$
is
$\sigma$
. Finally, if S is a formal linear combination of permutations, then
$d(S,\Pi)$
is the linear combination of the densities of its constituents in
$\Pi$
, with coefficients given by the combination. For example, if
$S=({1}/{2})\,12+({1}/{3})\,123$
, then
$d(S,\Pi)=({1}/{2})\,d(12,\Pi)+({1}/{3})\,d(123,\Pi)$
.
A permuton
$\Pi$
is a limit of a convergent sequence
$(\pi_n)_{n\in{\mathbb {N}}}$
of permutations if, for every permutation
$\sigma$
,
$d(\sigma,\Pi)$
is the limit of
$d(\sigma,\pi_n)$
. Every permuton is a limit of a convergent sequence of permutations and every convergent sequence of permutations has a (unique) limit permuton [
Reference Hoppen, Kohayakawa, de, Moreira, Ráth and Sampaio26, Reference Hoppen, Kohayakawa, de, Moreira and Sampaio27
].
We next define a way of creating a permuton from a given permutation
$\pi$
. Let
$\pi$
be a permutation of size k and
$z_1,\ldots,z_k$
non-negative reals summing to one. The blow-up of the permutation
$\pi$
with parts scaled by the factors
$z_1,\ldots,z_k$
is the unique permuton
$\Pi$
defined as follows (an example is given in Figure 1). Let
$s_i$
,
$i\in [k]$
, be the sum of
$z_1+\cdots+z_{i-1}$
and let
$t_i$
,
$i\in [k]$
, be the sum of
$z_{\pi^{-1}(1)}+\cdots+z_{\pi^{-1}(i-1)}$
. The support of the permuton
$\Pi$
is the set
\[\bigcup_{i\in [k]}\{(s_i+x,t_{\pi(i)}+x),0\leq x\leq z_i\}.\]
Informally speaking, the support of the permuton
$\Pi$
is formed by k increasing segments that are arranged in the order given by the permutation
$\pi$
and scaled by the factors
$z_1,\ldots,z_k$
. Since the set
\[\{x\subseteq [0,1] \ |\ \exists \ y\neq y' \text{ with} \ (x, y), \ (x, y')\in {\text{supp}}(\Pi)\}\]
has measure zero, the support uniquely determines a probability measure on
$[0,1]^2$
with uniform marginals; this probability measure is the permuton
$\Pi$
. In particular,
$\Pi(X)$
for a Borel subset
$X\subseteq [0,1]^2$
is equal to the measure of the projection of the set
$X\cap{\text{supp}}(\Pi)$
on either of the two coordinates (the measure of either of the projections is the same).
2·4. Lyndon words and Lyndon permutations
Lyndon words, introduced by Širšov [
Reference Širšov46
] and by Lyndon [
Reference Lyndon37
] in the 1950s, form a notion that has nowadays many applications in algebra, combinatorics and computer science. Let
$\Sigma$
be a linearly ordered alphabet. The lexicographic order on words over
$\Sigma$
is denoted by
$\preceq$
. A word
$s_1\ldots s_n$
over the alphabet
$\Sigma$
is a Lyndon word if no proper suffix of the word
$s_1\cdots s_n$
is smaller (in the lexicographic order) than the word
$s_1\ldots s_n$
itself. For example, the word aab is Lyndon but the word aba is not (with respect to the usual order on letters). The following well-known property of Lyndon words [
Reference Chen, Fox and Lyndon12, Reference Penaguiao38, Reference Radford42
] is important for our arguments.
Proposition 3. Every word over a linearly ordered alphabet can be uniquely expressed as a concatenation of Lyndon words
$w_1,\ldots,w_{\ell}$
such that
$w_1\succeq\cdots\succeq w_{\ell}$
.
For example, the word aba is the concatenation of the Lyndon words ab and a, while the word ababa is the concatenation of the Lyndon words ab, ab and a.
Fig. 1. The support of the blow-up of the permutation 42315 scaled by
$0.4$
,
$0.2$
,
$0.1$
,
$0.1$
and
$0.2$
.
A subword of a word
$s_1\ldots s_n$
is any word
$s_{i_1}\ldots s_{i_m}$
with
$1\leq i_1 \lt \cdots \lt i_m\leq n$
. The shuffle product of words
$s_1\ldots s_n$
and
$t_1\ldots t_m$
, which is denoted by
$s_1\ldots s_n\otimes_S t_1\ldots t_m$
, is the formal sum of all
$\binom{n+m}{n}$
(not necessarily distinct) words of length
$n+m$
that contain the words
$s_1\ldots s_n$
and
$t_1\ldots t_m$
as subwords formed by disjoint sets of letters. For example,
$ab\otimes_S ac=2\,aabc+2\,aacb+abac+acab$
. The following statement can be found in [
Reference Radford42
, theorem 3·1·1(a)].
Lemma 4. Let
$w_1,\ldots,w_n$
be Lyndon words such that
$w_1\succeq\cdots\succeq w_n$
. The lexicographically largest constituent in the shuffle product
$w_1\otimes_S\cdots\otimes_S w_n$
is the term
$w_1\ldots w_n$
, and if the words
$w_1,\ldots,w_n$
are pairwise distinct, then the coefficient of this term is equal to one.
In this manuscript, we always work with the alphabet
$\Sigma$
of indecomposable permutations, i.e., the letters of the alphabet are indecomposable permutations and the linear order is defined in a way that indecomposable permutations of smaller size precede those of larger size and indecomposable permutations of the same size are ordered lexicographically. Hence, the first five letters of
$\Sigma$
are the following five (indecomposable) permutations: 1, 21, 231, 312 and 321 (in this order). Given a permutation
$\pi$
, we write
$\overline{\pi}$
for the word over the alphabet
$\Sigma$
consisting of the indecomposable blocks of
$\pi$
. We write
$\pi \lt _L\pi'$
if the word
$\overline{\pi}$
is lexicographically smaller than the word
$\overline{\pi'}$
, and use the symbols
$\leq_L$
,
$ \gt _L$
and
$\ge_L$
in regard to this order in the usual sense. In particular,
$1 \lt _L 12 \lt _L 132 \lt _L 21 \lt _L 231$
. A permutation
$\pi$
is a Lyndon permutation if the word
$\overline{\pi}$
is a Lyndon word. For example, the permutation
$21\oplus 231=21453$
is a Lyndon permutation but the permutations
$12=1\oplus 1$
,
$213=21\oplus 1$
and
$2143=21\oplus 21$
are not. Note that all indecomposable permutations are Lyndon. The set of all non-trivial Lyndon permutations of size at most k is denoted by
${\mathcal{P}}^L_k$
, e.g.,
${\mathcal{P}}^L_2=\{21\}$
and
${\mathcal{P}}^L_3=\{21,132,231,312,321\}$
.
The following is a folklore result; we include its short proof for completeness.
Proposition 5. The number
$\lvert{\mathcal{P}}_k^L\rvert$
of non-trivial Lyndon permutations of length at most k is independent of the choice of ordering of the alphabet
$\Sigma$
of indecomposable permutations.
Proof. Fix any ordering of
$\Sigma$
and let
$\ell_k$
be the number of Lyndon permutations of size exactly k that arise from this ordering. Proposition 3 implies the following power series identity:
\[ \prod_{n\geq 1} (1-x^n)^{-\ell_n} = \sum_{n\geq 1} n! x^n.\]
This uniquely determines each
$\ell_n$
, and hence
$|{\mathcal{P}}_k^L|$
.
2·5. Flag algebra products
The flag algebra method of Razborov [
Reference Razborov43
] catalyzed progress on many important problems in extremal combinatorics and has been successfully applied to problems concerning graphs [
Reference Baber and Talbot2, Reference Balogh, Hu, Lidický and Liu4, Reference Grzesik21–Reference Hatami, Hladký, Král’, Norine and Razborov24, Reference Král’, Liu, Sereni, Whalen and Yilma30, Reference Pikhurko and Razborov39–Reference Pikhurko and Vaughan41, Reference Razborov44
], digraphs [
Reference Coregliano and Razborov13, Reference Hladký, Král’ and Norin25
], hypergraphs [
Reference Baber and Talbot1, Reference Balogh, Clemen and Lidicky3, Reference Glebov, Král’ and Volec20, Reference Razborov45
], geometric settings [
Reference Král’, Mach and Sereni31
], permutations [
Reference Balogh, Hu, Lidický, Pikhurko, Udvari and Volec5, Reference Crudele, Dukes and Noel14, Reference Sliacčan and Stromquist47
], and other combinatorial objects. We will not introduce the method completely but we present the concept of a product, which will be important in our further considerations. To avoid confusion with other types of products considered in this manuscript, we refer to the product as a flag product. If
$\pi_1$
and
$\pi_2$
are two permutations of sizes
$k_1$
and
$k_2$
, respectively, then the flag product of
$\pi_1$
and
$\pi_2$
, which is denoted by
$\pi_1\times\pi_2$
, is a formal linear combination of all permutations
$\sigma$
of size
$k_1+k_2$
such that there exists a
$k_1$
-element set
$S\subseteq [k_1+k_2]$
such that the pattern induced by S in
$\sigma$
is
$\pi_1$
and the pattern induced by
$[k_1+k_2]\setminus S$
in
$\sigma$
is
$\pi_2$
; the coefficient at
$\sigma$
is equal to the number of choices of such S divided by
$\binom{k_1+k_2}{k_1}$
. We give an example:
\begin{equation}12\times 1=\frac{3}{3}\,123+\frac{2}{3}\,132+\frac{1}{3}\, 231+\frac{2}{3}\, 213+\frac{1}{3}\, 312.\end{equation}
The following identity follows from [
Reference Razborov43
] and holds for any permuton
$\Pi$
and any permutations
$\pi_1,\ldots,\pi_n$
:
\begin{equation}d\left(\pi_1\times\cdots\times\pi_n,\Pi\right)=d(\pi_1,\Pi)d(\pi_2,\Pi)\cdots d(\pi_n,\Pi).\end{equation}
For example, (1) and (2) yield that the following identity holds for any permuton
$\Pi$
:
\[d(1,\Pi)d(12,\Pi)=\frac{3}{3}d(123,\Pi)+\frac{2}{3}d(132,\Pi)+\frac{1}{3}d(231,\Pi)+\frac{2}{3}d(213,\Pi)+\frac{1}{3}d(312,\Pi).\]
3. Lower bound
In this section, we prove our lower bound on the dimension of the feasible region of densities of k-patterns; the matching upper bound is proven in the next section. We start with the following lemma, which is a key part of the proof of Theorem 2. The main idea of the proof of the lemma is similar to that used in the proof of Lemma 7.
Lemma 6. Let
$\pi_1,\ldots,\pi_n$
be Lyndon permutations such that
$\pi_1 \gt _L\pi_2 \gt _L\cdots \gt _L\pi_n$
, and let N be the size of the permutation
$\pi_1\oplus\cdots\oplus\pi_n$
. If
$J_1,\ldots,J_n$
are disjoint subsets of [N] such that the pattern induced by
$J_i$
in
$\pi_1\oplus\cdots\oplus\pi_n$
is
$\pi_i$
for every
$i\in [n]$
, then every
$J_i$
is an interval and
$J_i=[\lvert\pi_i\rvert]+\lvert\pi_1\rvert+\cdots+\lvert\pi_{i-1}\rvert$
for every
$i\in [n]$
.
Proof. Fix the permutations
$\pi_1,\ldots,\pi_n$
and the subsets
$J_1,\ldots,J_n$
as in the statement of the lemma. For
$i\in [n]$
, let
$m_i$
be the number of indecomposable blocks of
$\pi_i$
and let
$\sigma_{i,1},\ldots,\sigma_{i,m_i}$
be indecomposable permutations such that
$\pi_i=\sigma_{i,1}\oplus\cdots\oplus\sigma_{i,m_i}$
. Note that the permutation
$\pi_1\oplus\cdots\oplus\pi_n$
has
$m_1+\cdots+m_n$
indecomposable blocks. Further, let
$J_{i,1},\ldots,J_{i,m_i}$
be the unique partition of
$J_i$
into non-crossing disjoint sets such that
$J_{i,j}$
contains the indices that induce the pattern
$\sigma_{i,j}$
,
$j\in [m_i]$
. Since the pattern induced by
$J_{i,j}$
,
$i\in [n]$
and
$j\in [m_i]$
, is an indecomposable permutation, the indices contained in
$J_{i,j}$
are contained in the same indecomposable block of the permutation
$\pi_1\oplus\cdots\oplus\pi_n$
. Since the sets
$J_{i,j}$
,
$i\in [n]$
and
$j\in [m_i]$
, partition the set [N] and the number of indecomposable blocks of
$\pi_1\oplus\cdots\oplus\pi_n$
is
$m_1+\cdots+m_n$
, it follows that each set
$J_{i,j}$
,
$i\in [n]$
and
$j\in [m_i]$
, is the set of indices of one of the indecomposable blocks of
$\pi_1\oplus\cdots\oplus\pi_n$
. In particular, indecomposable blocks of the permutations
$\pi_1,\ldots,\pi_n$
one-to-one correspond to indecomposable blocks of the permutation
$\pi_1\oplus\cdots\oplus\pi_n$
. Since
$\overline{\pi_1\oplus\cdots\oplus\pi_n}$
is the lexicographically largest constituent in the shuffle product
$\overline{\pi_1}\otimes_S\cdots\otimes_S\overline{\pi_n}$
and the coefficient at this constituent is one by Lemma 4 (note that
$\pi_1,\ldots,\pi_n$
are pairwise distinct), it follows that each
$J_i$
,
$i\in [n]$
, is the set of indices corresponding to
$\pi_i$
in
$\pi_1\oplus\cdots\oplus\pi_n$
. The statement of the lemma now follows.
We are now ready to prove our main result, Theorem 2.
Proof of Theorem
2. Fix an integer
$k\ge 2$
. Let N be the number of non-trivial Lyndon permutations of size at most k, i.e.
$N=\lvert{\mathcal{P}}^L_k\rvert$
, and let
$\pi_1,\ldots,\pi_{N+1}$
be all Lyndon permutations of size at most k listed in a way that
$\pi_1 \gt _L\cdots \gt _L\pi_{N+1}$
; note that
$\pi_1=k(k-1)\ldots 1$
and
$\pi_{N+1}=1$
. Let
$n_i$
be the size of the permutation
$\pi_i$
,
$i\in [N+1]$
.
We next define a family of permutons parameterized by
$N+(n_{1}+\cdots+n_{N})$
variables, namely by
$s_1,\ldots,s_{N}$
and
$t_{i,1},\ldots,t_{i,n_{i}}$
for
$i\in [N]$
. For brevity, we will sometimes refer to
$s_1, \ldots, s_N$
as the s-variables and to
$t_{1, 1}, \ldots, t_{N, n_N}$
as the t-variables. The parameters will be positive reals such that
$s_1+\cdots+s_N \lt 1$
and
$t_{i,1}+\cdots+t_{i,n_{i}} \lt 1$
for every
$i\in [N]$
. The permuton
$\Pi^L(s_1,\ldots,s_{N},t_{1,1},\ldots,t_{N,n_{N}})$
is the blow-up of the permutation
$\pi_1\oplus\cdots\oplus\pi_{N+1}$
such that the
$n_1+\cdots+n_{N+1}$
parts of the blow-up are scaled by the factors
\[s_1t_{1,1},\ldots,s_1t_{1,n_1},\; s_2t_{2,1},\ldots,s_2t_{2,n_2},\; \ldots,\; s_Nt_{N,1},\ldots,s_Nt_{N,n_N},\; z,\]
where
$z= 1-\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{n_i}s_it_{i, j}$
. We illustrate the construction of a permuton
$\Pi^L$
for
$k=3$
. There are five non-trivial Lyndon permutations of size at most 3 (and so six Lyndon permutations of size at most 3 in total), i.e.,
$N=5$
,
$\pi_1=321$
,
$\pi_2=312$
,
$\pi_3=231$
,
$\pi_4=21$
,
$\pi_5=132$
and
$\pi_6=1$
. Hence, the permuton
$\Pi^L$
is parameterised by 19 variables
$s_1,\ldots,s_5$
and
$t_{i,j}$
for
$(i,j)\in [5]\times [3]\setminus \{(4,3)\}$
. The permuton
$\Pi^L$
itself is visualised in Figure 2.
Fig. 2. The permuton
$\Pi^L_3$
.
Fix
$i\in [N]$
and consider the permutation
$\pi_i$
. Observe that the probability that
$n_i$
points sampled based on the permuton
$\Pi^L$
form the pattern
$\pi_i$
, conditioned on at least one point sampled from the part corresponding to
$\pi_{N+1}$
, is zero, as none of the permutations
$\pi_1,\ldots,\pi_N$
ends with an indecomposable block of size one. It follows that the density
$d(\pi_i,\Pi^L)$
is a homogeneous polynomial of order
$2n_i$
such that each term of the polynomial contains
$n_i$
variables
$s_1,\ldots,s_N$
(possibly with multiplicities) and
$n_i$
variables
$t_{1,1},\ldots,t_{N,n_N}$
(again possibly with multiplicities); each monomial corresponds to one of the possible choices of points from parts of the permuton
$\Pi^L$
that yields
$\pi_i$
. Moreover, if each of the t-variables appears once in the monomial, then the pattern of
$\pi_1\oplus\cdots\oplus\pi_N$
induced by the elements corresponding to the t-variable of the monomial is
$\pi_i$
, and every pattern of
$\pi_1\oplus\cdots\oplus\pi_N$
that is
$\pi_i$
is associated with one such monomial.
We now analyse the Jacobian matrix
$\mathcal{J}$
of the function
$\left(d(\pi_1,\Pi^L),\ldots,d(\pi_N,\Pi^L)\right)$
with respect to the variables
$s_1,\ldots,s_N$
, i.e.
\[\mathcal{J}_{i, j}=\frac{\partial}{\partial s_j}d\left(\pi_i,\Pi^L(s_1,\ldots,s_{N},t_{1,1},\ldots,t_{N,n_{N}})\right).\]
Since the density
$d(\pi_i,\Pi^L)$
is a homogeneous polynomial of order
$2n_i$
with
$n_i$
s-variables and
$n_i$
t-variables, the Jacobian determinant
\begin{equation}\det(\mathcal{J})=\sum_{\sigma\in S_N} {\text{sgn}}(\sigma) \prod_{i=1}^N \mathcal{J}_{i, \sigma(i)}\end{equation}
is a homogeneous polynomial of order
$2(n_1+\cdots+n_N)-N$
such that each of its summands is a monomial with
$n_1+\cdots+n_N-N$
s-variables and
$n_1+\cdots+n_N$
t-variables (counted with multiplicity, in both cases). We next investigate those monomials of the Jacobian determinant that contain all of the
$n_1+\cdots+n_N$
t-variables, i.e. each of the t-variables appears once in the monomial.
Consider a permutation
$\sigma$
in (3) and note that the monomials that occur in
$\prod_{i=1}^N\mathcal{J}_{i, \sigma(i)}$
arise as products of monomials that occur in each of the
$\mathcal{J}_{i, \sigma(i)}$
. For such a product of monomials, let
$I_i$
be the multiset of (double) indices of the variables
$t_{1,1},\ldots,t_{N,n_N}$
contained in the monomial occurring in
$\mathcal{J}_{i, \sigma(i)}$
. Recall that each monomial of the polynomial
$d(\pi_i,\Pi^L)$
corresponds to one of the possible choices of points from parts of the permuton
$\Pi^L$
that yields
$\pi_i$
, and the chosen parts are determined by the variables contained in the monomial, and we never use the part of
$\Pi^L$
corresponding to
$\pi_{N+1}$
(as argued earlier). If the term in the product in (3) associated with
$I_1,\ldots,I_N$
contains each of the t-variables exactly once, then the term corresponds to sampling at most one point from each part of
$\Pi^L$
and so no double index occurs twice in
$I_1\cup\cdots\cup I_N$
(and each
$I_i$
is actually a set rather than just a multiset). Since an index
$(a, b)\in I_i$
corresponds to the bth element of the permutation
$\pi_a$
in
$\pi_1\oplus\cdots\oplus\pi_{N}$
, we can map each set
$I_i$
to a set
$J_i\subseteq [ n_1+\cdots +n_N]$
of (single) indices indicating the elements of
$\pi_1\oplus\cdots\oplus\pi_{N+1}$
inducing the pattern
$\pi_i$
; the mapping is simply
$(a, b) \rightarrow \sum_{j=1}^{a-1}|\pi_j| + b$
. Hence, if the term in the product in (3) associated with
$I_1,\ldots,I_N$
contains each of the t-variables exactly once, the sets
$J_1,\ldots,J_N$
form a partition of
$[n_1+\ldots+n_N]$
, and the pattern of
$\pi_1\oplus\cdots\oplus\pi_N$
induced by
$J_i$
is
$\pi_i$
for every
$i\in [N]$
.
Since the sets
$J_1,\ldots,J_N$
are disjoint and the pattern of
$\pi_1\oplus\cdots\oplus\pi_N$
induced by
$J_i$
is
$\pi_i$
for every
$i\in [N]$
, Lemma 6 yields that each of the sets
$J_i$
is an interval that corresponds to the entries of
$\pi_i$
in the permutation
$\pi_1\oplus\cdots\oplus\pi_N$
. It follows that the only permutation
$\sigma$
such that
$\prod_{i=1}^{N}\mathcal{J}_{i, \sigma(i)}$
yields a monomial term containing all t-variables is the identity permutation of size N, and the said monomial is obtained precisely by multiplying the terms
$s_i^{n_i-1}t_{i,1}\cdots t_{i,n_i}$
in the polynomials
$({\partial}/{\partial s_i})d\left(\pi_i,\Pi^L\right)$
,
$i\in [N]$
. Note that the coefficient of the term
$s_i^{n_i}t_{i,1}\cdots t_{i,n_i}$
in
$d\left(\pi_i,\Pi^L\right)$
is equal to
\[\ell_{i,1}!\ell_{i,2}!\cdots\ell_{i,m_i}!,\]
where
$m_i$
is the number of increasing segments of
$\pi_i$
and
$\ell_{i,1},\ldots,\ell_{i,m_i}$
are their lengths; in particular, the coefficient is non-zero. We conclude that the coefficient of the term
\[\prod_{i=1}^N s_i^{n_i-1}\prod_{j=1}^{n_i}t_{i,j}\]
in the determinant of
$\mathcal{J}$
is non-zero.
Since the Jacobian determinant is a polynomial that is not identically zero, there exists a choice of positive reals
$s_1,\ldots,s_N$
,
$s_1+\cdots+s_N \lt 1$
, and positive reals
$t_{1,1},\ldots,t_{N,n_N}$
,
$t_{i,1}+\cdots+t_{i,n_{i}} \lt 1$
for every
$i\in [N]$
, such that the Jacobian determinant is non-zero. It follows using the Inverse Function Theorem that the point
$x_0\in [0,1]^{{\mathcal{P}}^L_k}$
such that
\[x_0=d\left(\pi,\Pi^L(s_1,\ldots,s_{N},t_{1,1},\ldots,t_{N,n_{N}})\right)_{\pi\in{\mathcal{P}}^L_k}\]
satisfies the statement of the theorem.
4. Upper bound
We start by proving a lemma on the interplay of the flag product of permutations and Lyndon permutations. Note that Proposition 3 ensures that the decomposition of any permutation
$\pi$
into
$\pi_1,\ldots,\pi_n$
as described in the statement of the next lemma always exists and is unique.
Lemma 7. Let
$\pi$
be a permutation and let
$(\pi_1,\ldots,\pi_n)$
be the unique ordered tuple of permutations such that:
-
(i)
$\pi=\pi_1\oplus\cdots\oplus\pi_n$
; -
(ii) the words
$\overline{\pi_1},\ldots,\overline{\pi_n}$
are Lyndon; and -
(iii) the sequence
$\overline{\pi_1},\ldots,\overline{\pi_n}$
is lexicographically non-increasing, i.e.,
$\pi_1\ge_L\cdots\ge_L\pi_n$
.
If a permutation
$\sigma$
is a constituent in the flag product
$\pi_1\times\cdots\times\pi_n$
and
$\sigma\not=\pi$
, then either:
-
(v)
$\sigma$
has fewer indecomposable blocks than
$\pi$
; or -
(vi)
$\sigma$
and
$\pi$
have the same number of indecomposable blocks and
$\overline{\sigma}$
is lexicographically smaller than
$\overline{\pi}$
.
Proof. Fix permutations
$\pi_1,\ldots,\pi_n$
. Let N be the sum of the sizes of
$\pi_1,\ldots,\pi_n$
, and let
$\sigma$
be a constituent in the flag product
$\pi_1\times\cdots\times\pi_n$
. Hence, there exists a partition of [N] into sets
$J_1,\ldots,J_n$
such that the pattern induced by
$J_i$
in
$\sigma$
is
$\pi_i$
,
$i\in [n]$
. For
$i\in [n]$
, let
$m_i$
be the number of indecomposable blocks of
$\pi_i$
and let
$J_{i,1},\ldots,J_{i,m_i}$
be the unique partition of
$J_i$
into pairwise non-crossing disjoint sets such that
$J_{i,j}$
,
$j\in [m_i]$
, contains the indices that induce in
$\sigma$
the jth indecomposable block of
$\pi_i$
. Observe that each set
$J_{i,j}$
,
$i\in [n]$
and
$j\in [m_i]$
, is a subset of an indecomposable block of
$\sigma$
. Hence, either two different sets
$J_{i,j}$
belong to the same indecomposable block of
$\sigma$
and so
$\sigma$
has fewer indecomposable blocks than
$\pi$
and we arrive at the first conclusion of the lemma, or each set
$J_{i,j}$
,
$i\in [n]$
and
$j\in [m_i]$
, belongs to a different indecomposable block of
$\sigma$
.
In the latter case, since the sets
$J_{i,j}$
partition [N], each of them contains indices of one of the indecomposable blocks of
$\sigma$
; in particular, each set
$J_{i,j}$
is an interval. Therefore, the words
$\overline{\pi_1\oplus\cdots\oplus\pi_n}$
and
$\overline{\sigma}$
have the same length and consist of the same multiset of letters. Moreover, since the sets
$J_{i,1},\ldots,J_{i,m_i}$
appear in the order of their second indices for every
$i\in [n]$
,
$\overline{\sigma}$
is a constituent in the shuffle product
$\overline{\pi_1}\otimes_S\cdots\otimes_S\overline{\pi_n}$
. By Lemma 4, the lexicographically largest constituent in the shuffle product
$\overline{\pi_1}\otimes_S\cdots\otimes_S\overline{\pi_n}$
is
$\overline{\pi_1\oplus\cdots\oplus\pi_n}=\overline{\pi}$
, and so
$\overline{\sigma}$
is lexicographically smaller than
$\overline{\pi}$
unless
$\sigma=\pi$
.
We are now ready to prove the main theorem of this section. As discussed in Section 1, the statement was presented by Borga and the last author in [ Reference Borga and Penaguiao6 ] with a sketch of a possible proof; we now present a different (in our view more elementary) proof for completeness.
Theorem 8. For every integer
$k\ge 2$
, there exists a polynomial function
$f\;:\;[0,1]^{{\mathcal{P}}^L_k}\to [0,1]^{{\mathcal{P}}_k}$
such that
\[f\left(\left(d(\sigma,\Pi)\right)_{\sigma\in{\mathcal{P}}^L_k}\right)=(d(\pi,\Pi))_{\pi\in{\mathcal{P}}_k}\]
for every permuton
$\Pi$
.
Theorem 8 follows from the next lemma (note that
$d(1,\Pi)=1$
for every permuton
$\Pi$
).
Lemma 9. Let
$\pi$
be a permutation of size
$k\ge 2$
. There exists a polynomial
$p_{\pi}$
in variables
$x_{\sigma}$
indexed by non-trivial Lyndon permutations
$\sigma$
of size at most k such that, for every permuton
$\Pi$
, the density
$d(\pi,\Pi)$
of
$\pi$
in
$\Pi$
is equal to the value of
$p_{\pi}$
evaluated at
$\vec x=(d(\sigma,\Pi))_{\sigma\in {\mathcal{P}}_k^L}$
.
Proof. Consider the following linear order on all permutations:
$\pi \lt \tau$
if either
$\lvert\pi\rvert \lt \lvert\tau\rvert$
,
$\lvert\pi\rvert=\lvert\tau\rvert$
and
$\pi$
has fewer indecomposable blocks than
$\tau$
, or
$\lvert\pi\rvert=\lvert\tau\rvert$
,
$\pi$
and
$\tau$
have the same number of indecomposable blocks and
$\pi \lt _L\tau$
. By slightly abusing notation, we extend the statement of the lemma to
$k=1$
(if
$k=1$
, the polynomial
$p_1$
depends on no variables, i.e., it is a constant), and prove the extended statement by induction on the linear order
$ \lt $
. The base of the induction is the permutation
$\pi=1$
and we set
$p_1$
to be constantly equal to 1.
We now present the induction step. Consider a permutation
$\pi$
of size
$k\ge 2$
. If
$\pi$
consists of a single indecomposable block, then
$\pi$
is Lyndon and we set
$p_{\pi}(\vec x)=x_{\pi}$
. In the rest, we assume that
$\pi$
consists of two or more indecomposable blocks and let
$\pi_1,\ldots,\pi_n$
be the Lyndon permutations such that
$\pi=\pi_1\oplus\cdots\oplus\pi_n$
and
$\pi_1\ge_L\cdots\ge_L\pi_n$
; such permutations exist and are unique by Proposition 3. By (2), it holds that
\[d(\pi_1\times\cdots\times\pi_n, \Pi)=d(\pi_1,\Pi)d(\pi_2,\Pi)\cdots d(\pi_n,\Pi).\]
By Lemma 7,
$d(\pi_1\times\cdots\times\pi_n, \Pi)$
is equal to a linear combination (with fixed coefficients) of densities
$d(\sigma,\Pi)$
of permutations
$\sigma$
of size k such that
$\sigma\leq \pi$
. Note that the coefficient of
$d(\pi, \Pi)$
in this linear combination is non-zero.
By induction, for each permutation
$\sigma \lt \pi$
, we can express
$d(\sigma, \Pi)$
as a polynomial in densities of non-trivial Lyndon permutations of size at most k. Substituting these polynomials for all
$\sigma \lt \pi$
in the linear combination of densities
$d(\sigma,\Pi)$
that is equal to
$d(\pi_1\times\cdots\times\pi_n, \Pi)$
, we obtain an identity that contains a term linear in
$d(\pi,\Pi)$
and terms polynomial in densities of non-trivial Lyndon permutations of size at most k. This yields the existence of the sought polynomial
$p_{\pi}$
.
