# Some extremal problems for trinomials with fold symmetry

Dmitriy Dmitrishin  Department of Applied Mathematics, Odessa National
Polytechnic University, Odessa, 65044, Ukraine<EMAIL_ADDRESS>,
Daniel Gray  Department of Mathematics, Georgia Southern University,
Statesboro GA, 30460, USA<EMAIL_ADDRESS>and  Alex Stokolos
Department of Mathematics, Georgia Southern University, Statesboro GA, 30460,
USA<EMAIL_ADDRESS>
###### Abstract.

The famous T. Suffridge polynomials have many extremal properties: the
maximality of coefficients when the leading coefficient is maximal; the zeros
of the derivative are located on the unit circle; the maximum radius of
stretching the unit disk with the schlicht normalization $F(0)=0$,
$F^{\prime}(0)=1$; the maximum size of the unit disk contraction in the
direction of the real axis for univalent polynomials with the normalization
$F(0)=0$, $F(1)=1.$ However, under the standard symmetrization method
$\sqrt[T]{F(z^{T})}$, these polynomials go to functions, which are not
polynomials. How can we construct the polynomials with fold symmetry that have
properties similar to those of the Suffridge polynomial? What values will the
corresponding extremal quantities take in the above-mentioned extremal
problems? The paper is devoted to solving these questions for the case of the
trinomials $F(z)=z+az^{1+T}+bz^{1+2T}$. Also, there are suggested hypotheses
for the general case in the work.

Keywords. Suffridge polynomials, polynomials symmetrization, domain of
univalence of trinomials with fold symmetry, extremal univalent trinomials
with fold symmetry.

###### 2000 Mathematics Subject Classification:

30C10,30C25,30C55,30C75

##  1\. Introduction

This work is motivated by problems of classical geometric complex analysis,
which studies various extremal properties of the univalent (or similar in
properties to univalent) in the central unit disk
$\mathbb{D}=\\{z\in\mathbb{C}:|z|<1\\}$ functions $F(z)$ with different
normalizations.

One of the first fundamental works in this theory was the 1916 paper by Ludwig
Bieberbach, in which he proved the exact estimate for the second coefficient
of the univalent in $\mathbb{D}$ functions of the form

(1) $F(z)=z+\sum_{j=2}^{\infty}a_{j}z^{j},$

namely, $|a_{2}|\leq 2$. This estimate immediately implies the famous Koebe
$1/4$ theorem. In that same work, Bieberbach stated in a footnote that in the
general case there must hold $|a_{j}|\leq j$. This innocently-looking
statement became known as the Bieberbach conjecture, which, since then, has
been the engine of the development of geometric complex analysis for 105
years. In 1984, the Bieberbach conjecture was proved by Louis de Branges, who
also showed that the extremal function, up to rotation, is the Koebe function

$K(z)=\frac{z}{(1-z)^{2}}=z+2z^{2}+3z^{3}+\ldots\,.$

Traditionally, the class of univalent in $\mathbb{D}$ functions of the form
(1) is denoted by the symbol $\mathcal{S}$ (from the German word Schlicht).
For each function $F\in\mathcal{S}$, the function
$H(z)=\sqrt[T]{F(z^{T})}\in\mathcal{S}$ ($z\in\mathbb{D}$, $T=1,2,\ldots$) and
maps the unit disk to a domain with $T$-fold symmetry ($T$-fold symmetric
function). G. Szegő suggested that for the coefficients of the $T$-symmetric
univalent function

$F(z)=z+\sum_{j=2}^{\infty}a_{j}z^{1+(j-1)T},$

$\max{|a_{j}|}\leq O\left((1+(j-1)T)^{-1+2/T}\right)$ [1, 2]. However, J.
Littlewood showed [3] that this hypothesis is false for sufficiently large
$T$. The results of N. Makarov [4] imply that the growth rate of coefficients
of $T$-symmetric univalent functions equals $2/T-1$ for $T\leq 2/B(1)$ and
$B(1)-1$ for $T\geq 2/B(1)$, where $B(t)$ is the universal integral means
spectrum for the class of univalent functions. This theorem, together with the
important paper by L. Carleson and P. Jones [5], suggest that G. Szegő’s
conjecture holds for $T\leq 8$ and fails for $T\geq 9$. D. Beliaev and S.
Smirnov [6] proved that the conjecture is indeed wrong for $T\geq 9$. The
general problem of finding the correct estimates is still wide open even for
bounded functions, see, e.g., [7]. Thus, the transfer of the known extremal
properties of general functions, belonging to the class $\mathcal{S}$, to
$T$-symmetric functions of the class $S$ is not, generally, a trivial task.

Even more significant difficulties arise when trying to establish the well-
known properties of univalent polynomials for $T$-symmetric univalent
polynomials.

One of the most famous families of univalent polynomials solving various
extremal problems is the T. Suffridge polynomials [8]:

$S_{k,N}(z)=z+\sum_{j=2}^{N}\sigma_{j,k}z^{j},$
$\sigma_{j,k}=\left(1-\frac{j-1}{N}\right)\frac{\sin{\frac{\pi
kj}{N+1}}}{\sin{\frac{\pi k}{N+1}}},\;k=1,2,\ldots,N.$

Note that Suffridge polynomials are the matter of greater part of the section
on univalent polynomials in the well-known book on univalent functions [9].

It is easy to see that the coefficient $\sigma_{N,k}=\frac{(-1)^{k}}{N}$
possesses the extremal property, since the absolute value of the leading
coefficient of a univalent polynomial, whose first coefficient is equal to
one, can not exceed the value of $1/N$.

T. Suffridge proved that all the polynomials $S_{k,N}(z)$ are univalent in
$\mathbb{D}$. Moreover, the zeros of the derivatives of polynomials
$S_{k,N}(z)$ lie on the unit circle, and the image of the unit circle contains
$N-1$ cusps [10]. Thus, the Suffridge polynomials are quasi-extremal
polynomials in the sense of Ruscheweyh [11].

Also, T. Suffridge showed that the polynomial $S(z):=S_{1,N}(z)$ is extremal,
in the sense that it maximizes the absolute value of each coefficient of any
univalent polynomial of order $N$ with the leading coefficient $1/N$.

In [12], one more extremal property of the polynomial $S(z)$ was established,
namely there was solved the extremal problem of estimating the maximum value
of the modulus of univalent polynomials with real coefficients of the form
$P(z)=z+\sum\limits_{j=2}^{N}a_{j}z^{j}$ in the disk
$\overline{\mathbb{D}}=\\{z\in\mathbb{C}:|z|\leq 1\\}$:

(2)
$\max_{P\in\mathcal{S}}\left\\{\max_{z\in\overline{\mathbb{D}}}\\{|P(z)|\\}\right\\}=S(1)=\frac{1}{4}\left(1+\frac{1}{N}\right)\csc^{2}{\frac{\pi}{2N+2}}.$

The corresponding extremal polynomial is unique up to alternation of signs,
i.e., the polynomials $S(z)$ and $-S(-z)$ are extremal.

The following extremal property of the Suffridge polynomial is related to the
problem of covering intervals and is achieved on the class of the univalent in
$\mathbb{D}$ polynomials with real coefficients $P(z)$ with the normalization
$P(1)=1$. Namely,

(3) $\min_{P}\\{|P(-1)|\\}=\frac{|S(-1)|}{S(1)}=\tan^{2}{\frac{\pi}{2(N+1)}}.$

The polynomial $\frac{1}{S(1)}S(z)$ is again the only extremal polynomial in
this problem [13].

Note that the Suffridge polynomials are used to approximate the Koebe function
[13], some unexpected applications of extremal polynomials to the solution of
control problems in nonlinear discrete systems are also found [14].

Obviously, the $T$-symmetric function $\sqrt[T]{S(z^{T})}$ is not a
polynomial. What polynomial with circlurar symmetry will have the properties
analogous to those of the Suffridge polynomial? What values will the
corresponding extremal quantities take in the considered above extremal
problems? This paper is devoted to a discussion of these issues. Let us note
only that even for $T=2$, that is, in the case of odd polynomials, these
problems are not easy.

The paper is organized as follows. In Section 2, polynomials with fold
symmetry are presented as candidates for an analogue of the Suffridge
polynomials. A number of hypotheses for the extremal properties of these
polynomials, which are inherent in Suffridge polynomials, are put forward. The
third section gives a description of the domain of univalence for trinomials
with fold symmetry in the coefficient plane, using five parametric equations
of the boundary. There are formulated constrained extremum problems for some
functions of two variables, which are test ones for checking the stated
hypotheses. The fourth section is auxiliary, two technical Lemmas are proved
there. Section 5 contains the main Theorem of the paper, from which it follows
that all the formulated hypotheses are true for trinomials with fold symmetry.
The last section is devoted to a short discussion of the obtained results.

##  2\. Problem statement

In [15, 16], there was introduced a new class of $T$-symmetric polynomials of
degree $N=1+(n-1)T$

(4)
$S^{(T)}(z)=z+\sum_{j=2}^{n}\left(1-\frac{(j-1)T}{1+(n-1)T}\right)\prod_{k=1}^{j-1}\frac{\sin{\frac{\pi(2+T(k-1))}{2+T(n-1)}}}{\sin{\frac{\pi
Tk}{2+T(n-1)}}}z^{T(j-1)+1}.$

It is easy to check that $S^{(1)}(z)=S(z)$, $S^{(2)}(z)=-iS_{n,N}(iz)$, where
$N=2n-1$, $i^{2}=-1$. Hence, the polynomial $S^{(2)}(z)$ is univalent. Note
that the leading coefficient of the polynomial $S^{(T)}(z)$ has the maximum
possible value for univalent polynomials of degree $N=1+(n-1)T$ with the first
coefficient equal to one: $\frac{1}{1+(n-1)T}$.

The works [16] [15] presented the results of some numerical experiments,
which, together with the established results, made it possible to propose a
number of hypotheses. Let us consider them.

Denote the class of univalent $T$-symmetric polynomials with real coefficients
of degree $N=1+(n-1)T$ and with the first coefficient equal to one by
$\mathcal{S}_{N}^{T}$. Hypotheses:

a) all the polynomials $S^{(T)}(z)$ are univalent in $\mathbb{D}$;

b) all the polynomials $S^{(T)}(z)$ are quasi-extremal in the sense of
Ruscheweyh;

c) all the polynomials $S^{(T)}(z)$ are extremal, in the sense that they
maximize the absolute value of each coefficient of any polynomial from
$\mathcal{S}_{N}^{T}$ with the leading coefficient $1/N$;

d)
$\max\limits_{P\in\mathcal{S}_{N}^{T}}\left\\{\max\limits_{z\in\overline{\mathbb{D}}}\\{|P(z)|\\}\right\\}=S^{(T)}(1)$;

e)
$\min\limits_{P\in\mathcal{S}_{N}^{T}}\left\\{\frac{1}{P(1)}\left|P\left(e^{i\frac{\pi}{T}}\right)\right|\right\\}=\frac{1}{S^{(T)}(1)}\left|S^{(T)}\left(e^{i\frac{\pi}{T}}\right)\right|$.

Problem: check the truth of the formulated hypotheses for all $T=1,2,\ldots$
and $n=3$. Note that in contrast with the cases $n=1,2$, the problem of
determining the extremal properties of polynomials from different classes even
for small $n\geq 3$ is usually far from trivial [17]. Let us only note that
the problem e) for $T=2$ is solved in [14], where it is established that

$\min_{P\in\mathcal{S}_{N}^{2}}\left\\{\frac{1}{P(1)}\left|P\left(e^{i\frac{\pi}{2}}\right)\right|\right\\}=\frac{1}{S^{(2)}(1)}\left|S^{(2)}\left(e^{i\frac{\pi}{2}}\right)\right|=\left|\frac{S_{n,N}(-1)}{S_{n,N}(i)}\right|=\frac{1}{n},$

and the extremal polynomial is unique.

##  3\. Domain of univalence of $T$-symmetric trinomials in the coefficient
space

In [18], there was considered the problem of constructing the domain of
univalence for the trinomials

$F(z)=z+az^{k}+bz^{m}$

with complex coefficients. Let us present the result of this work for the case
of real coefficients. So, let

$U_{k,m}=\\{(a,b)\in\mathbb{R}^{2}:z+az^{k}+bz^{m}\textit{ is univalent in
}\mathbb{D}\\}.$

Let $\frac{k-1}{m-k}=\frac{p}{q}$ be the fraction after reduction. Define the
following five curves in the plane:

$\displaystyle\Gamma_{1}=\left\\{(x,y):\,x=\frac{\sin{(m-1)t}}{k\sin{(m-k)t}},\,y=\frac{\sin{(k-1)t}}{n\sin{(m-k)t}},\,t\in\mathbb{R}\right\\},$
$\displaystyle\Gamma_{2}^{s}=\\{(x,y):\,kx+(-1)^{qs}my=(-1)^{ps+1}\\},\;s=0,1,$
$\displaystyle\Gamma_{3}^{s}=\left\\{(x,y):\,x=(-1)^{ps+1}\frac{\cos{t}}{\cos{kt}}\frac{\tan{mt}-m\tan{t}}{k\tan{mt}-m\tan{kt}},\right.$
$\displaystyle\left.y=(-1)^{(p+q)s}\frac{\cos{t}}{\cos{mt}}\frac{\tan{kt}-k\tan{t}}{k\tan{mt}-m\tan{kt}},\,t\in\mathbb{R}\right\\},\;s=0,1.$

It is noted further that these curves define the area $U_{k,m}$ in such a way
that the boundary of this area is contained in the union of these five curves.
The set $U_{k,m}$ is a component bounded by these curves, which contains zero.

A thorough analysis of the equations for the boundaries of the area $U_{k,m}$
shows that these equations can be simplified, and we also can identify the
exact intervals of variation for the parameters in the parametric equations
for setting the boundaries. Let us present these equations for the case
$k=1+T$, $m=1+2T$.

We have $\frac{k-1}{m-k}=1$, $p=1$, $q=1$.

$\displaystyle\frac{\cos{t}}{\cos{(1+T)t}}\frac{\tan{(1+2T)t}-(1+2T)\tan{t}}{(1+T)\tan{(1+2T)t}-(1+2T)\tan{(1+T)t}}=$
$\displaystyle=\frac{2T\sin{(2+2T)t}-(2+2T)\sin{2Tt}}{T\sin{(2+3T)t}-(2+3T)\sin{Tt}},$
$\displaystyle\frac{\cos{t}}{\cos{(1+2T)t}}\frac{\tan{(1+T)t}-(1+T)\tan{t}}{(1+T)\tan{(1+2T)t}-(1+2T)\tan{(1+T)t}}=$
$\displaystyle=\frac{T\sin{(2+T)t}-(2+T)\sin{Tt}}{T\sin{(2+3T)t}-(2+3T)\sin{Tt}}.$

Then the domain $U_{T}$ of univalence of the trinomial
$F(z)=z+az^{1+T}+bz^{1+2T}$ is bounded by the curves:

$\displaystyle\Gamma_{1}=\left\\{(x,y):\,x=t,\,y=\frac{1}{1+2T},\right.$
$\displaystyle\left.t\in\left[-2\frac{1+T}{1+2T}\sin{\frac{\pi}{2+2T}},2\frac{1+T}{1+2T}\sin{\frac{\pi}{2+2T}}\right]\right\\},$
$\displaystyle\Gamma_{2}^{+}=\left\\{(x,y):\,x=t,\,y=\frac{(1+T)t-1}{1+2T},\,t\in\left[0,\frac{4}{2+3T}\right]\right\\},$
$\displaystyle\Gamma_{2}^{-}=\left\\{(x,y):\,x=-t,\,y=\frac{(1+T)t-1}{1+2T},\,t\in\left[0,\frac{4}{2+3T}\right]\right\\},$
$\displaystyle\Gamma_{3}^{+}=\left\\{(x,y):\,x=A(t),\,y=B(t),\,t\in\left[0,\frac{\pi}{2+2T}\right]\right\\},$
$\displaystyle\Gamma_{3}^{-}=\left\\{(x,y):\,x=-A(t),\,y=B(t),\,t\in\left[0,\frac{\pi}{2+2T}\right]\right\\},$

where

$\displaystyle
A(t)=\frac{2T\sin{(2+2T)t}-(2+2T)\sin{2Tt}}{T\sin{(2+3T)t-(2+3T)\sin{Tt}}},$
$\displaystyle
B(t)=\frac{T\sin{(2+T)t}-(2+T)\sin{Tt}}{T\sin{(2+3T)t-(2+3T)\sin{Tt}}}.$

The boundaries of the intervals of variation for the parameters in defining
the curves, which determine the boundary of the domain $U_{T}$, are computed
as the roots of the corresponding equations. Note that the domain $U_{1}$ is
defined in [19, 20], and optimization for $U_{1}$ was used in [21]. Therefore,
the current work is a generalization of [21].

To demonstrate how the domain $U_{T}$ contracts with the growth of $T$, let us
picture this area for different $T$ (Fig. 1). In Fig. 2, represent the
boundaries $\Gamma_{1}$, $\Gamma_{2}^{+}$, $\Gamma_{2}^{-}$, $\Gamma_{3}^{+}$,
$\Gamma_{3}^{-}$ and the point that corresponds to the trinomial from family
(4):

(5) $S^{(T)}(z)=z+a^{(0)}z^{1+T}+b^{(0)}z^{1+2T},$

where $a^{(0)}=2\frac{1+T}{1+2T}\sin{\frac{\pi}{2+2T}}$,
$b^{(0)}=\frac{1}{1+2T}$.

Figure 1. Domain $U_{T}$ of univalence of the trinomial
$F(z)=z+az^{1+T}+bz^{1+2T}$ in the parameter plane $(a,b)$ for $T=1$ (the
boundary is shown in black), $T=2$ (the boundary is shown in blue), $T=5$ (the
boundary is shown in red) Figure 2. Curves $\Gamma_{1}$ (blue),
$\Gamma_{2}^{+}$, $\Gamma_{2}^{-}$ (green), $\Gamma_{3}^{+}$, $\Gamma_{3}^{-}$
(red) and the point $C(a^{(0)},b^{(0)})$ for $T=4$

Note some properties of the domain $U_{T}$. This area, considered in the plane
$(a,b)$, has axial symmetry about the line $Ob$; the line $\Gamma_{1}$ defines
polynomials with zeros of the derivative lying on the unit circle (quasi-
extremal polynomials in the sense of Ruscheweyh). Thus, hypotheses a) and b)
for trinomial (5) are confirmed.

To confirm the truth of hypotheses c), d), e), we need to determine the
extreme values of the functions

$L_{1}(x,y)=x,\;L_{2}(x,y)=1+x+y,\;L_{3}(x,y)=\frac{1-x+y}{1+x+y}$

in the domain $U_{T}$.

It is easy to show that these functions do not have stationary points in
$U_{T}$ (points at which both partial derivatives disappear) therefore we can
restrict our attention to the boundary of the region. It will be shown that
the functions $L_{1}(x,y)$ and $L_{2}(x,y)$ increase on the curve
$\Gamma_{3}^{+}$, and the function $L_{3}(x,y)$ decreases on this curve. This
will imply that

$\displaystyle\max_{(x,y)\in
U_{T}}\\{L_{1}(x,y)\\}=L_{1}(a^{(0)},b^{(0)})=a^{(0)}=2\frac{1+T}{1+2T}\sin{\frac{\pi}{2+2T}},$
$\displaystyle\max_{(x,y)\in
U_{T}}\\{L_{2}(x,y)\\}=L_{2}(a^{(0)},b^{(0)})=1+a^{(0)}+b^{(0)}=$
$\displaystyle=\frac{1}{1+2T}\left(1+2(1+T)\sin{\frac{\pi}{2+2T}}\right),$
$\displaystyle\min_{(x,y)\in
U_{T}}\\{L_{3}(x,y)\\}=L_{3}(a^{(0)},b^{(0)})=\frac{1-a^{(0)}+b^{(0)}}{1+a^{(0)}+b^{(0)}}=\left(\frac{1-\sin{\frac{\pi}{2+2T}}}{\cos{\frac{\pi}{2+2T}}}\right)^{2}.$

Though the statement of the extremal problems is rather simple, we will need
to overcome certain technical difficulties to solve them.

##  4\. Auxiliary results

######  Lemma 1.

Let

$H(x,k)=-(1-x)^{2}3^{2k}+(1+x)(3-2x)^{2k}-(1+x)(3-x)+(3-x)(1-2x)^{2k}.$

Then, for $k\geq 3$ and $x\in(0,1/2]$

(6) $H(x,k)<0,$

and

(7) $|H(x,k)|>\frac{1}{(2k+1)(2k+2)}|H(x,k+1)|.$

###### Proof.

Let us start with the proof of (6). It is obvious that
$(1+x)(3-x)>(3-x)(1-2x)^{2k},$ i.e. $-(1+x)(3-x)+(3-x)(1-2x)^{2k}<0.$ Further,

$(1-x)^{2}3^{2k}-(1+x)(3-2x)^{2k}=3^{2k}\left((1-x)^{2}-(1+x)(1-2x/3)^{2k}\right).$

For $k\geq 3$, $x\in(0,1/2]$, the following inequality holds:

$(1-x)^{2}-(1+x)(1-2x/3)^{2k}>(1-x)^{2}-(1+x)(1-2x/3)^{6}.$

The polynomial $(1-x)^{2}-(1+x)(1-2x/3)^{6}$ has two complex conjugate zeros
and five real ones: $x_{1}=-0.71\ldots$, $x_{2}=0$, $x_{3}=0.91\ldots$,
$x_{4}=1.04\ldots$, $x_{5}=3$, moreover, this polynomial is positive for
$x\in(0,0.91)$, hence, for $x\in(0,1/2]$ as well. Therefore,
$-(1-x)^{2}3^{2k}+(1+x)(3-2x)^{2k}<0$. The sum of two negative polynomials is
a negative polynomial. Thus, (6) is proven.

Proof of inequality (7) follows the same ideas. Let us prove a slightly
stronger inequality

$|H(x,k)|>\frac{1}{3k^{2}}|H(x,k+1)|.$

Let us change the inequality

$(1+x)(3-x)-(3-x)(1-2x)^{2k}>\frac{1}{3k^{2}}\left((1+x)(3-x)-(3-x)(1-2x)^{2k}(1-2x)^{2}\right)$

to

$(1+x)>(1-2x)^{2k}\frac{3k^{2}-(1-2x)^{2}}{3k^{2}-1}.$

The above inequality is obvious because the left hand side is an increasing
function while the right hand side is decreasing.

Now, let us show that

$(1-x)^{2}3^{2k}-(1+x)(3-2x)^{2k}>\frac{1}{3k^{2}}\left((1-x)^{2}3^{2k}9-(1+x)(3-2x)^{2k}(3-2x)^{2}\right).$

To do that let us write the inequality in the form

$(1-x)^{2}>(1+x)\left(1-\frac{2x}{3}\right)^{2k}\frac{k^{2}-3\left(1-\frac{2x}{3}\right)^{2}}{k^{2}-3}.$

Now, take into account that for $k\geq 3$ and $x\in(0,1/2]$ we have

$\frac{k^{2}-3\left(1-\frac{2x}{3}\right)^{2}}{k^{2}-3}<1+\frac{4}{k^{2}-3}x\leq
1+\frac{2x}{3}$

and

$\left(1-\frac{2x}{3}\right)^{2k}\leq\left(1-\frac{2x}{3}\right)^{6}.$

Note that the polynomial $(1-x)^{2}-(1+x)(1-2x/3)^{6}(1+2x/3)$ has two
conjugate complex roots and six reals

$x_{1}=-1.67...,x_{2}=-0.27...,x_{3}=0,x_{4}=0.87...,x_{5}=1.05...,x_{5}=2.71...$

Moreover, this polynomial is positive for $x\in(0,0.87),$ hence it is positive
for $x\in(0,1/2].$ Thus, the inequality (7) is valid.

The lemma is proved. ∎

######  Lemma 2.

Let

$\displaystyle
G(\tau,\alpha)=(1+\alpha)\cos{(3-2\alpha)\tau}+(3-\alpha)\cos{(1-2\alpha)\tau}-$
$\displaystyle-(1-\alpha)^{2}\cos{3\tau}-(1+\alpha)(3-\alpha)\cos{\tau}.$

Then $G(\tau,\alpha)>0$ when $\tau\in(0,\pi/2)$, $\alpha\in(0,1/2]$.

###### Proof.

Using the cosine series expansion formula, we can write

(8)
$G(\tau,\alpha)=\sum_{k=0}^{\infty}(-1)^{k}\frac{1}{(2k)!}H(\alpha,k)\tau^{2k}.$

Note that $H(\alpha,0)=H(\alpha,1)=H(\alpha,2)\equiv 0$. By (7), the series
(8) is an alternating series, and $H(\alpha,3)<0$. Using Leibniz’s Theorem on
estimating a function with the partial sums of its alternating series
expansion, we obtain the estimate

$G(\tau,\alpha)>\tau^{6}\left(|H(\alpha,3)|-|H(\alpha,4)|\tau^{2}\right)=|H(\alpha,4)|\tau^{6}\left(\frac{14}{5-4\alpha+2\alpha^{2}}-\tau^{2}\right).$

When $\alpha\in(0,1/2]$,
$\displaystyle\frac{14}{5-4\alpha+2\alpha^{2}}>\frac{14}{5}$. Then

$G(\tau,\alpha)>|H(\alpha,4)|\tau^{6}\left(\frac{14}{5}-\left(\frac{\pi}{2}\right)^{2}\right)>0$

for $\tau\in(0,\pi/2)$. The lemma is proved.

∎

##  5\. Main results

Let us find the extreme values of the functions

$L_{1}(x,y)=x,\;L_{2}(x,y)=1+x+y,\;L_{3}(x,y)=\frac{1-x+y}{1+x+y}$

in the domain $U_{T}$.

######  Theorem 1.

The functions $L_{1}(x,y)$ and $L_{2}(x,y)$ attain the maximum over the region
$U_{T}$ at the upper right corner, while the function $L_{3}(x,y)$ attains its
minimum there.

It follows from the Theorem that hypotheses c), d), e) are true.

Indeed, the point $(x,y)$ in the domain corresponds to a univalent polynomial
$z+xz^{1+T}+yz^{1+2T}.$ In particular, among univalent polynomials
$\displaystyle z+xz^{1+T}+\frac{1}{1+2T}z^{1+2T}$ the polynomial $S^{(T)}(z)$
has the largest coefficients, the corresponding point $(x,y)$ is at the upper
right corner of the region. This proves conjecture c).

Further, due to symmetry of the region and situation in an upper half-plane we
might assume both $x$ and $y$ to be positive in consideration of conjecture
d). In that case the maximum of the polynomial attains at $z=1,$ i.e.

$\max_{z\in\bar{\mathbb{D}}}\left\\{z+xz^{1+T}+yz^{1+2T}\right\\}=1+x+y.$

The maximum of $1+x+y$ attains at the upper right corner of the domain, hence
the value $|S^{(T)}(1)|$ is the largest one, which proves conjecture d).

Conjecture e) follows by similar argument.

The extremal polynomial that corresponds to hypothesis e) is unique:
$S^{(T)}(z)$; in the problems corresponding to hypotheses c) and d), these are
the polynomials $S^{(T)}(z)$, $-S^{(T)}(-z)$.

Now, let us prove the theorem.

###### Proof.

Because functions $L_{j}(x,y)$ do not have stationary points in $U_{T}$ and
due to the symmetry of the domain $U_{T}$, we can restrict ourselves to the
boundary and to the case $x\geq 0$. Obviously, the functions $L_{1}(x,y)$ and
$L_{2}(x,y)$ increase on the curves $\Gamma_{1}$ and $\Gamma_{2}^{+}$. And the
function $L_{3}(x,y)$ decreases on these curves. It remains to consider the
behavior of these functions on the curve $\Gamma_{3}^{+}$.

Since $\frac{1-x+y}{1+x+y}=1-\frac{2}{1+\frac{1+y}{x}}$, instead of the
initial functions $L_{2}(x,y)$, $L_{3}(x,y)$ it is more convenient to consider
the functions $\hat{L}_{2}(x,y)=y$, $\hat{L}_{3}(x,y)=\frac{1+y}{x}$.

We represent the parametric equations defining the curve $\Gamma_{3}^{+}$ in
the form

$\Gamma_{3}^{+}=\left\\{(x,y):\,x=\frac{U(t)}{W(t)},\,y=\frac{V(t)}{W(t)},\,t\in\left[0,\frac{\pi}{2+2T}\right]\right\\},$

where

$\displaystyle U(t)=2T\sin{(2+2T)t}-(2+2T)\sin{2Tt},$ $\displaystyle
V(t)=T\sin{(2+T)t}-(2+T)\sin{Tt},$ $\displaystyle
W(t)=T\sin{(2+3T)t}-(2+3T)\sin{Tt}.$

Make the substitution $\tau=(1+T)t$, $\alpha=\frac{1}{1+T}$. Then
$\tau\in[0,\pi/2]$, $\alpha\in(0,1/2]$. The functions $U(t)$, $V(t)$, $W(t)$
transform into the functions

$\displaystyle\hat{U}(\tau)=\frac{1}{\alpha}(2\sin{(2(1-\alpha))\tau}-2(1-\alpha)\sin{2\tau}),$
$\displaystyle\hat{V}(\tau)=\frac{1}{\alpha}((1+\alpha)\sin{(1-\alpha)\tau}-(1-\alpha)\sin{(1+\alpha)\tau}),$
$\displaystyle\hat{W}(\tau)=\frac{1}{\alpha}((3-\alpha)\sin{(1-\alpha)\tau}-(1-\alpha)\sin{(3-\alpha)\tau}),$

and

$\Gamma_{3}^{+}=\left\\{(x,y):\,x=\frac{\hat{U}(\tau)}{\hat{W}(\tau)},\,y=\frac{\hat{V}(\tau)}{\hat{W}(\tau)},\,\tau\in\left[0,\frac{\pi}{2}\right]\right\\}.$

Find the derivatives

$\displaystyle\hat{U}^{\prime}(\tau)=\frac{8}{\alpha}(1-\alpha)\sin{\alpha\tau}\sin{(2-\alpha)\tau},$
$\displaystyle\hat{V}^{\prime}(\tau)=\frac{2}{\alpha}(1-\alpha)(1+\alpha)\sin{\alpha\tau}\sin{\tau},$
$\displaystyle\hat{W}^{\prime}(\tau)=\frac{2}{\alpha}(3-\alpha)(1-\alpha)\sin{(2-\alpha)\tau}\sin{\tau}.$

Then

$\displaystyle\left(\frac{\hat{U}(\tau)}{\hat{W}(\tau)}\right)^{\prime}=\frac{2(1-\alpha)\sin{(2-\alpha)\tau}}{\left(\hat{W}(\tau)\right)^{2}}G(\tau,\alpha),$
$\displaystyle\left(\frac{\hat{V}(\tau)}{\hat{W}(\tau)}\right)^{\prime}=\frac{2(1-\alpha)\sin{\tau}}{\left(\hat{W}(\tau)\right)^{2}}G(\tau,\alpha),$
$\displaystyle\left(\frac{\hat{V}(\tau)}{\hat{U}(\tau)}\right)^{\prime}=\frac{2(1-\alpha)\sin{\alpha\tau}}{\left(\hat{U}(\tau)\right)^{2}}G(\tau,\alpha),$
$\displaystyle\left(\frac{\hat{W}(\tau)}{\hat{U}(\tau)}\right)^{\prime}=-\frac{2(1-\alpha)\sin{(2-\alpha)\tau}}{\left(\hat{U}(\tau)\right)^{2}}G(\tau,\alpha),$

and

$\left(\frac{\hat{V}(\tau)+\hat{W}(\tau)}{\hat{U}(\tau)}\right)^{\prime}=-\frac{4}{\left(\hat{U}(\tau)\right)^{2}}(1-\alpha)\cos{\tau}\sin{(1-\alpha)\tau}G(\tau,\alpha).$

By Lemma 2, $G(\tau,\alpha)>0$ when $\tau\in(0,\pi/2)$, $\alpha\in(0,1/2]$.
Therefore,

$\left(\frac{\hat{U}(\tau)}{\hat{W}(\tau)}\right)^{\prime}>0,\;\left(\frac{\hat{V}(\tau)}{\hat{W}(\tau)}\right)^{\prime}>0,\;\left(\frac{\hat{V}(\tau)+\hat{W}(\tau)}{\hat{U}(\tau)}\right)^{\prime}<0.$

Hence, we proved that on the curve $\Gamma_{3}^{+}$:

1) the function $L_{1}(x,y)=x$ increases;

2) the function $\hat{L}_{2}(x,y)=y$ increases;

3) the function $\hat{L}_{3}(x,y)=\frac{1+y}{x}$ decreases.

The theorem is proved. ∎

##  6\. Discussion of the results

Of course, the next problem in the queue for consideration is the case of
polynomials of degree $n=4,$ or more generally, $n\geq 4.$ The domains of
univalence in these cases are not known even for $T=1.$ This does not prevent
considering hypotheses a)-e) in the general situation, but greatly complicates
the solution.

The next natural question is the question about the maximum contraction of the
unit disk in the direction of the real axis for univalent polynomials with the
schlicht normalization $F(0)=0$, $F^{\prime}(0)=1$. Note that in this case the
Suffridge polynomials are not optimal [21, 22]. Thus, changing the
normalization $F(0)=0$, $F^{\prime}(0)=1$ to $F(0)=0$, $F(1)=1$ leads not only
to a change of the extreme value, but also to a change of the extremal
polynomial, which is quite interesting.

In [15], there were introduced the polynomials $s^{(T)}(z)$ that formally
differ from the polynomials $S^{(T)}(z)$ defined by (4). The following
asymptotics was established:

$\frac{1}{s^{(T)}(1)}\left|s^{(T)}\left(e^{i\frac{\pi}{T}}\right)\right|\sim
c_{T}n^{-2/T}$

as $n\rightarrow\infty$, where $c_{T}=\pi^{2/T-1}\Gamma^{2}(1/T+1/2)$,
$\Gamma(\cdot)$ is the gamma function.

However, already [16] introduces and proves, for special cases, the conjecture
that the polynomials $s^{(T)}(z)$ coincide with the polynomials $S^{(T)}(z)$.
In the same work, the following relation was shown:

$\max\limits_{z\in\overline{\mathbb{D}}}\left\\{|s^{(T)}(z)|\right\\}=s^{(T)}(1)\sim\frac{1}{c_{T}2^{2/T}}n^{2/T}$

as $n\rightarrow\infty,$ which is a quantitative refinement of hypothesis d).

##  7\. Acknowledgment

The authors would like to thank Larie Ward for her help in preparation of the
manuscript.

## References

  * [1] J. Basilevitsh.  Zum Koeffizientenproblem der schlichten Funktionen.  Math. Z., 43(2):211–228, 1936.
  * [2] W.I. Lewin.  Ein beitrag zum koeffizientenproblem der schlichten funktionen.  Math. Z., 38:306–311, 1934.
  * [3] J.E. Littlewood.  On the coefficients of schlicht functions.  Q. J. Math., 9(33):14–20, 1938.
  * [4] N.G. Makarov.  Fine structure of harmonic measure.  St. Petersburg Math. J., 10(2):217–268, 1999.
  * [5] L. Carleson, P.W. Jones.  On coefficient problems for univalent functions and conformal dimension.  Duke Math. J., 66:169–206, 1992.
  * [6] D. Beliaev, S. Smirnov.  Harmonic measure on fractal sets.  In European Congress of Mathematics, pages 41–59. Eur. Math. Soc., Zürich, 2005.
  * [7] D. Beliaev, S. Smirnov.  Random conformal snowflakes.  Ann. Math., 172(1):597–615, 2010.
  * [8] T. Suffridge.  On univalent polynomials.  J. London Math. Soc., 44:496–504, 1969.
  * [9] P.L. Duren.  Univalent Functions.  Grundlehren der mathematischen Wissenschaften, 1983.
  * [10] A. Cordova, St. Ruscheweyh.  On maximal ranges of polynomial spaces in the unit disk.  Constr. Approx., 5:309–328, 1989.
  * [11] C. Genthner, St. Ruscheweyh, L. Salinas.  A criterion for quasi-simple plane curves.  Comput. Methods Funct. Theory, 2(1):281–291, 2003.
  * [12] M. Brandt.  Representation formulas for the class of typically real polynomials.  Math. Nachr., 144:29–37, 1989.
  * [13] D. Dimitrov.  Extremal univalent polynomials subordinating the Koebe function.  East J. Approx., 11(1):47–56, 2005.
  * [14] D. Dmitrishin, P. Hagelstein, A. Khamitova, A. Korenovskyi, A. Stokolos .  Fejér polynomials and control of nonlinear discrete systems.  Constr. Approx., 51(2):383–412, 2020.
  * [15] D. Dmitrishin, A. Stokolos, M. Tohaneanu.  Searching for cycles in non-linear autonomous discrete dynamical systems.  N.Y. J. Math., 25:603–626, 2019.
  * [16] D. Dmitrishin, A. Smorodin, A. Stokolos, M. Tohaneanu.  Symmetrization of Suffridge polynomials and approximation of $T$-symmetric Koebe functions.  J. Math. Anal. Appl., 503(2), 2020.
  * [17] S. Ignaciuk, M. Parol.  On the Koebe Quarter Theorem for certain polynomials.  Anal. Math. Phys., 11(2):67–79, 2021.
  * [18] G. Schmieder.  Univalence and zeros of complex polynomials.  In Handbook of complex analysis geometric function theory, volume 2, pages 339–350. Martin-Luther-Universität Halle-Wittenberg, Halle, Germany, Elsevier, 2005.
  * [19] D.A. Brannan.  Coefficient regions for univalent polynomials of small degree.  Mathematika, 14:165–169, 1967.
  * [20] V.F. Cowling, W.C. Royster.  Domains of variability for univalent polynomials.  Proc. Am. Math. Soc., 19:767–772, 1968.
  * [21] K. Dyakonov D. Dmitrishin and A. Stokolos.  Univalent polynomials and koebe’s one-quarter theorem.  Anal. Math. Phys., pages 1–14, 2019.
  * [22] M. Brandt.  Variationsmethoden für in der einheitskreisscheibe schlichte polynome.  PhD thesis. Humboldt-Univ. Berlin, 1987.


model training in a way it only uses domain invariant features. They usually
require no extra step in the target domain. This is a massive benefit in terms
of efficiency. Consequently, they need no labeled data in the target domain,
which is a significant advantage. Adversarial-based DA methods are examples
that use GANs (Gallego et al., 2020; Tzeng et al., 2017; Wang and Jiang,
2020). Still, the final comparison of such techniques with our framework is
required. Our framework fine-tunes APR models for specific projects, which
might be more effective than general DA.

##  8\. Conclusion

In this study, we showed that TFix and CodeXGLUE, two pioneer APR techniques,
are sensitive to the potential domain shift. We proposed a domain adaptation
framework that increases their performance on new projects. We showed the
framework is effective, efficient, and reliable. We discussed the differences
and advantages of three DA methods, FullFineTuning,
TuningWithLightWeightAdapterLayers and CurriculumLearning, on TFix and
concluded that the final choice depends on the exact conditions. Moreover, we
proposed a transformer-based bug generator method that creates synthetic APR
datasets. We showed how effectively the synthetic data can replace a missing
APR dataset in the DA framework. Finally, we expressed the required
modifications to apply our framework to other APR techniques. Finally, We
stated exciting points for future work; bringing domain adaptation to other
software engineering tasks, personalizing APR models, or leveraging the bug
generator method for related downstream.

———–

## References

  * (1)
  * esl (2022) 2022\.  _ESLint, Find and Fix Problems in Your JavaScript code_.  https://eslint.org/
  * lig (2022) 2022\.  _Lightrun, a Developer-Native Observability Platform_.  https://lightrun.com/
  * Abdul-Rauf et al. (2020) Sadaf Abdul-Rauf, José Carlos Rosales, Minh Quang Pham, and François Yvon. 2020\.  Limsi@ wmt 2020. In _Conference on Machine Translation_.
  * Agarap (2018) Abien Fred Agarap. 2018\.  Deep learning using rectified linear units (relu).  _arXiv preprint arXiv:1803.08375_ (2018).
  * Aljundi et al. (2019) Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. 2019\.  Gradient based sample selection for online continual learning.  _Advances in neural information processing systems_ 32 (2019).
  * Allamanis et al. (2017) Miltiadis Allamanis, Marc Brockschmidt, and Mahmoud Khademi. 2017\.  Learning to represent programs with graphs.  _arXiv preprint arXiv:1711.00740_ (2017).
  * Allamanis et al. (2021) Miltiadis Allamanis, Henry Jackson-Flux, and Marc Brockschmidt. 2021\.  Self-supervised bug detection and repair.  _Advances in Neural Information Processing Systems_ 34 (2021), 27865–27876.
  * Amodei et al. (2016) Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. 2016\.  Concrete problems in AI safety.  _arXiv preprint arXiv:1606.06565_ (2016).
  * Bader et al. (2019) Johannes Bader, Andrew Scott, Michael Pradel, and Satish Chandra. 2019.  Getafix: Learning to fix bugs automatically.  _Proceedings of the ACM on Programming Languages_ 3, OOPSLA (2019), 1–27.
  * Bapna et al. (2019) Ankur Bapna, Naveen Arivazhagan, and Orhan Firat. 2019\.  Simple, scalable adaptation for neural machine translation.  _arXiv preprint arXiv:1909.08478_ (2019).
  * Bapna and Firat (2019) Ankur Bapna and Orhan Firat. 2019.  Non-parametric adaptation for neural machine translation.  _arXiv preprint arXiv:1903.00058_ (2019).
  * Barrault et al. (2020) Loïc Barrault, Magdalena Marta Biesialska, Marta Ruiz Costa-Jussà, Fethi Bougares, and Olivier Galibert. 2020.  Findings of the first shared task on lifelong learning machine translation. In _EMNLP 2020, Fifth Conference on Machine Translation: November 19-20, 2020, online: proceedings of the conference_. Association for Computational Linguistics, 56–64.
  * Berabi et al. (2021) Berkay Berabi, Jingxuan He, Veselin Raychev, and Martin Vechev. 2021.  Tfix: Learning to fix coding errors with a text-to-text transformer. In _International Conference on Machine Learning_. PMLR, 780–791.
  * Bhatia et al. (2018) Sahil Bhatia, Pushmeet Kohli, and Rishabh Singh. 2018\.  Neuro-symbolic program corrector for introductory programming assignments. In _2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE)_. IEEE, 60–70.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020\.  Language models are few-shot learners.  _Advances in neural information processing systems_ 33 (2020), 1877–1901.
  * Callison-Burch et al. (2006) Chris Callison-Burch, Miles Osborne, and Philipp Koehn. 2006\.  Re-evaluating the role of BLEU in machine translation research. In _11th conference of the european chapter of the association for computational linguistics_. 249–256.
  * Chai et al. (2022) Yitian Chai, Hongyu Zhang, Beijun Shen, and Xiaodong Gu. 2022\.  Cross-Domain Deep Code Search with Few-Shot Meta Learning.  _arXiv preprint arXiv:2201.00150_ (2022).
  * Chen et al. (2022) Fuxiang Chen, Fatemeh H Fard, David Lo, and Timofey Bryksin. 2022\.  On the Transferability of Pre-trained Language Models for Low-Resource Programming Languages. In _2022 IEEE/ACM 30th International Conference on Program Comprehension (ICPC)_. IEEE, 401–412.
  * Chen et al. (2020) Pinzhen Chen, Nikolay Bogoychev, and Ulrich Germann. 2020\.  Character mapping and ad-hoc adaptation: Edinburgh’s IWSLT 2020 open domain translation system. In _Proceedings of the 17th International Conference on Spoken Language Translation_. 122–129.
  * Chen et al. (2021) Zimin Chen, Vincent J Hellendoorn, Pascal Lamblin, Petros Maniatis, Pierre-Antoine Manzagol, Daniel Tarlow, and Subhodeep Moitra. 2021\.  PLUR: A unifying, graph-based view of program learning, understanding, and repair.  _Advances in Neural Information Processing Systems_ 34 (2021), 23089–23101.
  * Chen et al. (2019) Zimin Chen, Steve Kommrusch, Michele Tufano, Louis-Noël Pouchet, Denys Poshyvanyk, and Martin Monperrus. 2019.  Sequencer: Sequence-to-sequence learning for end-to-end program repair.  _IEEE Transactions on Software Engineering_ 47, 9 (2019), 1943–1959.
  * Chu et al. (2017) Chenhui Chu, Raj Dabre, and Sadao Kurohashi. 2017.  An empirical comparison of domain adaptation methods for neural machine translation. In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_. 385–391.
  * Croft et al. (2022) Roland Croft, Yongzheng Xie, and Muhammad Ali Babar. 2022\.  Data Preparation for Software Vulnerability Prediction: A Systematic Literature Review.  _IEEE Transactions on Software Engineering_ (2022).
  * Currey et al. (2020) Anna Currey, Prashant Mathur, and Georgiana Dinu. 2020\.  Distilling multiple domains for neural machine translation. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. 4500–4511.
  * De Stefano et al. (2021) Manuel De Stefano, Fabiano Pecorelli, Fabio Palomba, and Andrea De Lucia. 2021.  Comparing within-and cross-project machine learning algorithms for code smell detection. In _Proceedings of the 5th International Workshop on Machine Learning Techniques for Software Quality Evolution_. 1–6.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ (2018).
  * Dinella et al. (2020) Elizabeth Dinella, Hanjun Dai, Ziyang Li, Mayur Naik, Le Song, and Ke Wang. 2020\.  Hoppity: Learning graph transformations to detect and fix bugs in programs. In _International Conference on Learning Representations (ICLR)_.
  * Edunov et al. (2018) Sergey Edunov, Myle Ott, Michael Auli, and David Grangier. 2018\.  Understanding back-translation at scale.  _arXiv preprint arXiv:1808.09381_ (2018).
  * Farahani et al. (2021) Abolfazl Farahani, Sahar Voghoei, Khaled Rasheed, and Hamid R Arabnia. 2021.  A brief review of domain adaptation.  _Advances in data science and information engineering_ (2021), 877–894.
  * Farajian et al. (2017) M Amin Farajian, Marco Turchi, Matteo Negri, and Marcello Federico. 2017.  Multi-domain neural machine translation through unsupervised adaptation. In _Proceedings of the Second Conference on Machine Translation_. 127–137.
  * Feng et al. (2020) Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al. 2020\.  Codebert: A pre-trained model for programming and natural languages.  _arXiv preprint arXiv:2002.08155_ (2020).
  * Gallego et al. (2020) Antonio-Javier Gallego, Jorge Calvo-Zaragoza, and Robert B Fisher. 2020.  Incremental unsupervised domain-adversarial training of neural networks.  _IEEE Transactions on Neural Networks and Learning Systems_ 32, 11 (2020), 4864–4878.
  * Gazzola et al. (2017) Luca Gazzola, Daniela Micucci, and Leonardo Mariani. 2017\.  Automatic software repair: A survey.  _IEEE Transactions on Software Engineering_ 45, 1 (2017), 34–67.
  * Guo et al. (2020) Daya Guo, Shuo Ren, Shuai Lu, Zhangyin Feng, Duyu Tang, Shujie Liu, Long Zhou, Nan Duan, Alexey Svyatkovskiy, Shengyu Fu, et al. 2020\.  Graphcodebert: Pre-training code representations with data flow.  _arXiv preprint arXiv:2009.08366_ (2020).
  * Gupta et al. (2017) Rahul Gupta, Soham Pal, Aditya Kanade, and Shirish Shevade. 2017\.  Deepfix: Fixing common c language errors by deep learning. In _Thirty-First AAAI conference on artificial intelligence_.
  * He et al. (2022) Jingxuan He, Luca Beurer-Kellner, and Martin Vechev. 2022\.  On Distribution Shift in Learning-based Bug Detectors.  _arXiv preprint arXiv:2204.10049_ (2022).
  * Hellendoorn et al. (2019) Vincent J Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. 2019\.  Global relational models of source code. In _International conference on learning representations_.
  * Husain et al. (2019) Hamel Husain, Ho-Hsiang Wu, Tiferet Gazit, Miltiadis Allamanis, and Marc Brockschmidt. 2019.  Codesearchnet challenge: Evaluating the state of semantic code search.  _arXiv preprint arXiv:1909.09436_ (2019).
  * Ji et al. (2020) Baijun Ji, Zhirui Zhang, Xiangyu Duan, Min Zhang, Boxing Chen, and Weihua Luo. 2020\.  Cross-lingual pre-training based transfer for zero-shot neural machine translation. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 34. 115–122.
  * Jin (2021) Cong Jin. 2021.  Cross-project software defect prediction based on domain adaptation learning and optimization.  _Expert Systems with Applications_ 171 (2021), 114637.
  * Jin et al. (2020) Di Jin, Zhijing Jin, Joey Tianyi Zhou, and Peter Szolovits. 2020\.  A simple baseline to semi-supervised domain adaptation for machine translation.  _arXiv preprint arXiv:2001.08140_ (2020).
  * Kanade et al. (2020) Aditya Kanade, Petros Maniatis, Gogul Balakrishnan, and Kensen Shi. 2020.  Learning and evaluating contextual embedding of source code. In _International Conference on Machine Learning_. PMLR, 5110–5121.
  * Kim et al. (2021) Sohyung Kim, Arianna Bisazza, and Fatih Turkmen. 2021\.  Using confidential data for domain adaptation of neural machine translation. In _Proceedings of the Third Workshop on Privacy in Natural Language Processing_. 46–52.
  * Kodirov et al. (2015) Elyor Kodirov, Tao Xiang, Zhenyong Fu, and Shaogang Gong. 2015\.  Unsupervised domain adaptation for zero-shot learning. In _Proceedings of the IEEE international conference on computer vision_. 2452–2460.
  * Koehn and Knowles (2017) Philipp Koehn and Rebecca Knowles. 2017.  Six challenges for neural machine translation.  _arXiv preprint arXiv:1706.03872_ (2017).
  * Lambert et al. (2011) Patrik Lambert, Holger Schwenk, Christophe Servan, and Sadaf Abdul-Rauf. 2011.  Investigations on translation model adaptation using monolingual data. In _Sixth Workshop on Statistical Machine Translation_. 284–293.
  * Le Goues et al. (2012) Claire Le Goues, Michael Dewey-Vogt, Stephanie Forrest, and Westley Weimer. 2012.  A systematic study of automated program repair: Fixing 55 out of 105 bugs for 8 each. In _2012 34th International Conference on Software Engineering (ICSE)_. IEEE, 3–13.
  * Le Goues et al. (2011) Claire Le Goues, ThanhVu Nguyen, Stephanie Forrest, and Westley Weimer. 2011.  Genprog: A generic method for automatic software repair.  _Ieee transactions on software engineering_ 38, 1 (2011), 54–72.
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. 2015\.  Deep learning.  _nature_ 521, 7553 (2015), 436–444.
  * Li et al. (2020b) Rumeng Li, Xun Wang, and Hong Yu. 2020b.  MetaMT, a meta learning method leveraging multiple domain data for low resource machine translation. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 8245–8252.
  * Li et al. (2016) Xiaoqing Li, Jiajun Zhang, and Chengqing Zong. 2016\.  One sentence one model for neural machine translation.  _arXiv preprint arXiv:1609.06490_ (2016).
  * Li et al. (2020a) Yi Li, Shaohua Wang, and Tien N Nguyen. 2020a.  Dlfix: Context-based code transformation learning for automated program repair. In _Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering_. 602–614.
  * Li et al. (2022) Yi Li, Shaohua Wang, and Tien N Nguyen. 2022.  DEAR: A Novel Deep Learning-based Approach for Automated Program Repair.  _arXiv preprint arXiv:2205.01859_ (2022).
  * Limsettho et al. (2018) Nachai Limsettho, Kwabena Ebo Bennin, Jacky W Keung, Hideaki Hata, and Kenichi Matsumoto. 2018\.  Cross project defect prediction using class distribution estimation and oversampling.  _Information and Software Technology_ 100 (2018), 87–102.
  * Liu et al. (2019) Chao Liu, Dan Yang, Xin Xia, Meng Yan, and Xiaohong Zhang. 2019.  A two-phase transfer learning model for cross-project defect prediction.  _Information and Software Technology_ 107 (2019), 125–136.
  * Liu et al. (2020) Shigang Liu, Guanjun Lin, Lizhen Qu, Jun Zhang, Olivier De Vel, Paul Montague, and Yang Xiang. 2020.  CD-VulD: Cross-domain vulnerability discovery based on deep domain adaptation.  _IEEE Transactions on Dependable and Secure Computing_ (2020).
  * Lu et al. (2021) Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin Clement, Dawn Drain, Daxin Jiang, Duyu Tang, et al. 2021\.  Codexglue: A machine learning benchmark dataset for code understanding and generation.  _arXiv preprint arXiv:2102.04664_ (2021).
  * Luong and Manning (2015) Minh-Thang Luong and Christopher D Manning. 2015.  Stanford neural machine translation systems for spoken language domains. In _Proceedings of the 12th International Workshop on Spoken Language Translation: Evaluation Campaign_.
  * Lutellier et al. (2020) Thibaud Lutellier, Hung Viet Pham, Lawrence Pang, Yitong Li, Moshi Wei, and Lin Tan. 2020.  Coconut: combining context-aware neural translation models using ensemble for program repair. In _Proceedings of the 29th ACM SIGSOFT international symposium on software testing and analysis_. 101–114.
  * Ma et al. (2012) Ying Ma, Guangchun Luo, Xue Zeng, and Aiguo Chen. 2012\.  Transfer learning for cross-company software defect prediction.  _Information and Software Technology_ 54, 3 (2012), 248–256.
  * Martinez and Monperrus (2016) Matias Martinez and Martin Monperrus. 2016.  Astor: A program repair library for java. In _Proceedings of the 25th International Symposium on Software Testing and Analysis_. 441–444.
  * Mehta et al. (2020) Sneha Mehta, Bahareh Azarnoush, Boris Chen, Avneesh Saluja, Vinith Misra, Ballav Bihani, and Ritwik Kumar. 2020.  Simplify-then-translate: automatic preprocessing for black-box translation. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 8488–8495.
  * Monperrus (2018) Martin Monperrus. 2018\.  Automatic software repair: a bibliography.  _ACM Computing Surveys (CSUR)_ 51, 1 (2018), 1–24.
  * Nam et al. (2013) Jaechang Nam, Sinno Jialin Pan, and Sunghun Kim. 2013.  Transfer defect learning. In _2013 35th international conference on software engineering (ICSE)_. IEEE, 382–391.
  * Nguyen et al. (2019) Van Nguyen, Trung Le, Tue Le, Khanh Nguyen, Olivier DeVel, Paul Montague, Lizhen Qu, and Dinh Phung. 2019\.  Deep domain adaptation for vulnerable code function identification. In _2019 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 1–8.
  * Ni et al. (2017) Chao Ni, Wang-Shu Liu, Xiang Chen, Qing Gu, Dao-Xu Chen, and Qi-Guo Huang. 2017\.  A cluster based feature selection method for cross-project software defect prediction.  _Journal of Computer Science and Technology_ 32, 6 (2017), 1090–1107.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002\.  Bleu: a method for automatic evaluation of machine translation. In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_. 311–318.
  * Patel et al. (2015) Vishal M Patel, Raghuraman Gopalan, Ruonan Li, and Rama Chellappa. 2015.  Visual domain adaptation: A survey of recent advances.  _IEEE signal processing magazine_ 32, 3 (2015), 53–69.
  * Patra and Pradel (2021) Jibesh Patra and Michael Pradel. 2021.  Semantic bug seeding: a learning-based approach for creating realistic bugs. In _Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. 906–918.
  * Peng et al. (2018) Kuan-Chuan Peng, Ziyan Wu, and Jan Ernst. 2018.  Zero-shot deep domain adaptation. In _Proceedings of the European Conference on Computer Vision (ECCV)_. 764–781.
  * Philip et al. (2020) Jerin Philip, Alexandre Berard, Matthias Gallé, and Laurent Besacier. 2020.  Monolingual adapters for zero-shot neural machine translation. In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_. 4465–4470.
  * Poncelas and Way (2019) Alberto Poncelas and Andy Way. 2019.  Selecting artificially-generated sentences for fine-tuning neural machine translation.  _arXiv preprint arXiv:1909.12016_ (2019).
  * Qi et al. (2014) Yuhua Qi, Xiaoguang Mao, Yan Lei, Ziying Dai, and Chengsong Wang. 2014.  The strength of random search on automated program repair. In _Proceedings of the 36th International Conference on Software Engineering_. 254–265.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. 2020\.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ 21, 140 (2020), 1–67.
  * Redko et al. (2019) Ievgen Redko, Emilie Morvant, Amaury Habrard, Marc Sebban, and Younes Bennani. 2019.  _Advances in domain adaptation theory_.  Elsevier.
  * Ren et al. (2020) Shuo Ren, Daya Guo, Shuai Lu, Long Zhou, Shujie Liu, Duyu Tang, Neel Sundaresan, Ming Zhou, Ambrosio Blanco, and Shuai Ma. 2020\.  Codebleu: a method for automatic evaluation of code synthesis.  _arXiv preprint arXiv:2009.10297_ (2020).
  * Salza et al. (2021) Pasquale Salza, Christoph Schwizer, Jian Gu, and Harald C Gall. 2021\.  On the effectiveness of transfer learning for code search.  _arXiv preprint arXiv:2108.05890_ (2021).
  * Saunders (2021) Danielle Saunders. 2021\.  Domain adaptation and multi-domain adaptation for neural machine translation: A survey.  _arXiv preprint arXiv:2104.06951_ (2021).
  * Saunders and Byrne (2020) Danielle Saunders and Bill Byrne. 2020.  Addressing Exposure Bias With Document Minimum Risk Training: Cambridge at the WMT20 Biomedical Translation Task.  _arXiv preprint arXiv:2010.05333_ (2020).
  * Schwenk (2008) Holger Schwenk. 2008\.  Investigations on large-scale lightly-supervised training for statistical machine translation.. In _Proceedings of the 5th International Workshop on Spoken Language Translation: Papers_.
  * Singhal et al. (2001) Amit Singhal et al. 2001\.  Modern information retrieval: A brief overview.  _IEEE Data Eng. Bull._ 24, 4 (2001), 35–43.
  * Sobreira et al. (2018) Victor Sobreira, Thomas Durieux, Fernanda Madeiral, Martin Monperrus, and Marcelo de Almeida Maia. 2018\.  Dissection of a bug dataset: Anatomy of 395 patches from defects4j. In _2018 IEEE 25th International Conference on Software Analysis, Evolution and Reengineering (SANER)_. IEEE, 130–140.
  * Song et al. (2019) Kai Song, Yue Zhang, Heng Yu, Weihua Luo, Kun Wang, and Min Zhang. 2019.  Code-switching for enhancing NMT with pre-specified translation.  _arXiv preprint arXiv:1904.09107_ (2019).
  * Sun et al. (2016) Baochen Sun, Jiashi Feng, and Kate Saenko. 2016.  Return of frustratingly easy domain adaptation. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 30.
  * Tufano et al. (2018) Michele Tufano, Cody Watson, Gabriele Bavota, Massimiliano Di Penta, Martin White, and Denys Poshyvanyk. 2018.  An empirical investigation into learning bug-fixing patches in the wild via neural machine translation. In _Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering_. 832–837.
  * Tufano et al. (2019) Michele Tufano, Cody Watson, Gabriele Bavota, Massimiliano Di Penta, Martin White, and Denys Poshyvanyk. 2019.  An empirical study on learning bug-fixing patches in the wild via neural machine translation.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ 28, 4 (2019), 1–29.
  * Tzeng et al. (2017) Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. 2017\.  Adversarial discriminative domain adaptation. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 7167–7176.
  * Van Der Wees et al. (2017) Marlies Van Der Wees, Arianna Bisazza, and Christof Monz. 2017\.  Dynamic data selection for neural machine translation.  _arXiv preprint arXiv:1708.00712_ (2017).
  * Vasic et al. (2019) Marko Vasic, Aditya Kanade, Petros Maniatis, David Bieber, and Rishabh Singh. 2019.  Neural program repair by jointly learning to localize and repair.  _arXiv preprint arXiv:1904.01720_ (2019).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ 30 (2017).
  * Wang and Sennrich (2020) Chaojun Wang and Rico Sennrich. 2020.  On exposure bias, hallucination and domain shift in neural machine translation.  _arXiv preprint arXiv:2005.03642_ (2020).
  * Wang and Jiang (2020) Jinghua Wang and Jianmin Jiang. 2020.  Adversarial learning for zero-shot domain adaptation. In _European Conference on Computer Vision_. Springer, 329–344.
  * Wang and Deng (2018) Mei Wang and Weihong Deng. 2018.  Deep visual domain adaptation: A survey.  _Neurocomputing_ 312 (2018), 135–153.
  * Wang et al. (2018) Wei Wang, Taro Watanabe, Macduff Hughes, Tetsuji Nakagawa, and Ciprian Chelba. 2018.  Denoising neural machine translation training with trusted data and online data selection.  _arXiv preprint arXiv:1809.00068_ (2018).
  * Yasunaga and Liang (2020) Michihiro Yasunaga and Percy Liang. 2020.  Graph-based, self-supervised program repair from diagnostic feedback. In _International Conference on Machine Learning_. PMLR, 10799–10808.
  * Yasunaga and Liang (2021) Michihiro Yasunaga and Percy Liang. 2021.  Break-it-fix-it: Unsupervised learning for program repair. In _International Conference on Machine Learning_. PMLR, 11941–11952.
  * Ye et al. (2022) He Ye, Matias Martinez, Xiapu Luo, Tao Zhang, and Martin Monperrus. 2022.  SelfAPR: Self-supervised Program Repair with Test Execution Diagnostics.  _arXiv preprint arXiv:2203.12755_ (2022).
  * Zhang et al. (2020) Biao Zhang, Philip Williams, Ivan Titov, and Rico Sennrich. 2020.  Improving massively multilingual neural machine translation and zero-shot translation.  _arXiv preprint arXiv:2004.11867_ (2020).
  * Zhao et al. (2020) Mingjun Zhao, Haijiang Wu, Di Niu, and Xiaoli Wang. 2020\.  Reinforced curriculum learning on pre-trained neural machine translation models. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 9652–9659.


# Composable Constraint Models for Permutation Enumeration

Ruth Hoffmann
School of Computer Science,
University of St Andrews,
Scotland
<EMAIL_ADDRESS>&Özgür Akgün
School of Computer Science,
University of St Andrews,
Scotland
<EMAIL_ADDRESS>&Christopher Jefferson
School of Computer Science and Engineering,
Central South University,
PR China
<EMAIL_ADDRESS>
###### Abstract

Constraint programming (CP) is a powerful tool for modeling mathematical
concepts and objects and finding both solutions or counter examples. One of
the major strengths of CP is that problems can easily be combined or expanded.
In this paper, we illustrate that this versatility makes CP an ideal tool for
exploring problems in permutation patterns.

We declaratively define permutation properties, permutation pattern avoidance
and containment constraints using CP and show how this allows us to solve a
wide range of problems. We show how this approach enables the arbitrary
composition of these conditions, and also allows the easy addition of extra
conditions. We demonstrate the effectiveness of our techniques by modelling
the containment and avoidance of six permutation patterns, eight permutation
properties and measuring five statistics on the resulting permutations. In
addition to calculating properties and statistics for the generated
permutations, we show that arbitrary additional constraints can also be easily
and efficiently added.

This approach enables mathematicians to investigate permutation pattern
problems in a quick and efficient manner. We demonstrate the utility of
constraint programming for permutation patterns by showing how we can easily
and efficiently extend the known permutation counts for a conjecture involving
the class of $1324$ avoiding permutations. For this problem, we expand the
enumeration of $1324$-avoiding permutations with a fixed number of inversions
to permutations of length 16 and show for the first time that in the
enumeration there is a pattern occurring which follows a unique sequence on
the Online Encyclopedia of Integer Sequences.

##  1 Introduction

The concept of permutation pattern classes emerged from an exercise question
in from the Art of Computer Programming Volume 1 (Section 2.2.1, Exercise 5)
by Knuth (1968), in which Knuth explored which permutations can be sorted in a
limited stack-based system, called stack-sortable permutations. Simion and
Schmidt (1985) were among the pioneers in characterizing and enumerating sets
of permutations based on the patterns that they avoid. Further enumeration
results garnered interest because the number of the original set of
permutations, identified in Knuth’s exercise, proved to be the Catalan
numbers.

The enumeration results and subsequent research were primarily motivated by a
conjecture proposed by Herbert Wilf at the 1992 SIAM meeting. This conjecture
stated that every permutation pattern class that avoids one permutation
pattern exhibits an exponential growth rate. Marcus and Tardos (2004) later
confirmed and proved this conjecture.

There are several systems which use computational techniques to assist with
the enumeration of permutation classes and sets, some examples include Permuta
Ardal et al. (2021), PatternClass Albert et al. (2012), Combinatorial
Specification Searcher Émile Nadeau et al. (2021) and PermCode (previously
PermLab) Albert (2012). Permuta is a Python package which supports the
enumeration of permutation classes using the BiSC algorithm by Magnusson and
Ulfarsson (2012). PatternClass is a GAP  package that encodes the permutations
and classes into regular languages, enabling efficient investigation of
permutation sets. Combinatorial Specification Searcher is another Python
package that provides a more exploratory approach by asking the user to define
strategies on how to build combinatorial sets from other sets. It combines
these into a general enumeration algorithm. PermCode is a Java library with a
graphical user interface which allows for the exploration of the sets of
permutations which avoid classical patterns.

Constraint programming (CP) is a generic and powerful paradigm that allows the
expression of complex combinatorial problems in a declarative manner. In CP
problems are expressed declaratively by giving a list of variables whose
values must be found, and stating relationships between variables in the form
of constraints. This declarative expression is called a model. CP solvers take
this declarative version of the problem and use a range of different
algorithms to solve the problem efficiently. The primary advantage of CP is
that it allows the user to focus on the problem formulation, while the
computer takes responsibility for the problem-solving methodology.

In the context of studying permutation patterns, constraint programming can
offer significant benefits. Permutation patterns provide a prominent and
widely researched topic within the domain of combinatorial mathematics. These
patterns, which involve the arrangement of numbers in a certain order, exhibit
intricate and complex structures. Constraint programming allows us to model
these structures and constraints explicitly, enabling systematic and efficient
exploration of the solution space.

In this paper we express problems in the high-level constraint language
Essence by Frisch et al. (2008). Essence, as implemented by the system Conjure
by Akgün et al. (2022), provides more abstract representation of combinatorial
problems. Conjure converts high-level specifications given in Essence into a
range of different formats, allowing many different constraint solvers (and
related technologies, such as Mixed Integer Programming and Boolean
Satisfiability) to be used when solving. This automation not only reduces the
possibility of errors in translation but also frees the user to concentrate on
the higher-level aspects of problem modelling. In this paper, we mainly use
the constraint solver Minion created by Gent et al. (2006), which has been
used to solve several large scale combinatorial problems in the past,
including the number of semi-groups of order 10 Distler et al. (2012) and for
the enumeration of set-theoretic solutions to the Yang-Baxter equation Akgün
et al. (2022).

In this paper we show how CP can aid the research in permutation patterns
through the following contributions:

  1. 1.

A systematic and comprehensive treatment of 6 kinds of permutation pattern (as
both avoidance and containment) as well as 13 properties and 5 statistics.
Each one is implemented as a standalone constraint model. This is presented in
Section 2.

  2. 2.

The models of the patterns, properties and statistics are structured in a way
that allows seamless composition of the individual models. Section 3
illustrates this compositionality.

  3. 3.

An evaluation of the flexible compositional constraint programming approach in
2 settings, one extended illustrative example and one example showing how
composable CP models can extend current results such as a conjecture in
Claesson et al. (2012). In Section 3.1 and Section 3.2 we present the
examples.

  4. 4.

2 new conjectures resulting from the model enumerating $1324$-avoiding
permutations with a fixed number of inversions which come from extending the
computational results in Claesson et al. (2012).

We believe our library of models, which can be easily composed in a "pick and
mix" fashion, will further the research in permutation patterns by allowing
for more efficient computational experimentation and exhaustive search as the
constraint programming approach avoids the need for the traditional "generate-
and-test" approach, which generates intermediate assignments that only satisfy
some of the properties for later filtering.

This "generate-and-test" approach, which requires specialised algorithms to be
created to find all permutations which satisfy some given property, can work
very well for that property but this approach is difficult to extend and
requires considerable expertise in programming to add new properties. On the
other hand, combining CP models can immediately allow highly efficient
searching for a combination of properties, and our experience is adding new
patterns in CP is significantly easier than create new bespoke state-of-the-
art programs for searching for new patterns.

##  2 Library of Models

We will consider a _permutation_ $\sigma$ to be an arrangement of the set
$\\{1,2,\ldots,n\\}$ for some $n\in\mathbb{N}$. The size of the set a
permutation $\sigma$ is defined on is called the length of the permutation and
is denoted $|\sigma|$. $S_{n}$ is used to denote for the set of all
permutations of length $n$. $\sigma$ can be viewed as a bijective function,
where $\sigma(i)$ denotes the $i$th member of the permutation and
$\sigma^{-1}(j)$ gives the index where $j$ occurs in the permutation.

Two sequences $\pi=\pi(1),\ldots,\pi(n)$ and
$\sigma=\sigma(1),\ldots,\sigma(n)$ of the same length are said to be _order
isomorphic_ Atkinson (1999) if $\forall i,j,\pi(i)\leq\pi(j)$ if and only if
$\sigma(i)\leq\sigma(j)$.

We will represent permutations by giving the arrangement of the set (often
called sequence notation) and as a permutation plot. Figure 1 gives an example
of a permutation plot.

Figure 1: Plot representation of the permutation $521634$. The x-axis
represents the indexes of the permutation, and the y-axis represents the
values. Reading left to right, the location of the dot in the $i$th column
represents the $i$th value in the permutation.

The rest of this Section defines the patterns, properties and statistics which
we have currently implemented. These terms are summarised in Table 1.

All CP models from the upcoming sections with definitions can be found in a
supplementary repository Özgür Akgün et al. (2023). This repository contains
executable CP models, sample parameter files, raw data for our computational
experimens and scripts that can be used to fully rerun the experiments. In
addition, the repository contains a Jupyter notebook that can be used to
interactively run model frangments through Conjure. The notebook also contains
the example scenarios from Section 3.

Conditions | Statistics
---|---
Pattern Avoidance/Containment | Properties | Number of
Classic | Simple | Inversions
Vincular | Plus-Decomposable | Ascents
Bivincular | Minus-Decomposable | Descents
Mesh | Blockwise Simple | Excedances
Boxed Mesh | Derangement | Major Index
Consecutive | Non-Derangement |
| Involution |
| Parity |
Table 1: Table of all permutation patterns, properties and statistics modelled

###  2.1 Pattern types

A permutation pattern identifies a subsequence of a permutation which
satisfies a list of constraints. If a subsequence of a permutation satisfies
the requirements of a given permutation pattern, it is said to _involve_ or
_contain_ the pattern. If no part of a permutation matches a permutation
pattern then it _avoids_ the pattern. There are many types of permutation
patterns, in this section we introduce the ones considered in this paper.

We say that a permutation $\pi=\pi(1)\ldots\pi(k)$ is _classically contained_
in a permutation $\sigma=\sigma(1)\ldots\sigma(m)$, where $k\leq m$, if there
is a subsequence $\sigma(i_{1})\ldots\sigma(i_{k})$ in $\sigma$ that is order
isomorphic to $\pi$. For example, the permutation $\pi=123$ can be found in
$\sigma=521634$ as the order isomorphic subsequence
$134=\sigma(3)\sigma(5)\sigma(6)$. Being _classically contained_ is a partial
order on the set of permutations Brignall (2010). In Figure 2(a) on the left
is the pattern permutation, on the right we have highlighted an occurrence of
the classical pattern by circling the elements. The other patterns we discuss
all extend classical patterns by adding further conditions.

_Vincular patterns_ (introduced by Babson and Steingrímsson (2000)) specify
adjacency conditions. Let $\pi=\pi(1)\ldots\pi(k)$,
$\sigma=\sigma(1)\ldots\sigma(m)$ and let $A\subseteq\\{0,\ldots,k\\}$. To
simplify the pattern definition, we define $\pi(0)=0$ and $\pi(k+1)=k+1$. An
occurrence of the vincular pattern $(\pi,A)$ in $\sigma$ is a subsequence
$\sigma(i_{1})\ldots\sigma(i_{k})$ of $\sigma$ such that
$\sigma(i_{1})\ldots\sigma(i_{k})$ is an occurrence of $\pi$ in the classical
sense, and $\forall a\in A.\ i_{a+1}=i_{a}+1$. We call $A$ the set of
_adjacencies_.

For example, the vincular pattern $(132,\\{1\\})$ can be found in
$\sigma=521634$ as the subsequence $164=\sigma(3)\sigma(4)\sigma(6)$. Figure
2(b) shows an example of a vincular pattern by showing the pattern with the
order isomorphic subsequence and highlights the adjacency requirement by
shading the column between the indices both in the pattern and the permutation
which contains the pattern.

_Bivincular patterns_ (as introduced in Bousquet-Mélou et al. (2010)) are
vincular patterns which have an additional set defining which values have to
be adjacent.

More formally, an occurrence of the bivincular pattern $(\pi,A,B)$ in
$\sigma$, with $A,B\subseteq\\{0,\ldots,k\\}$ and $|\pi|=k$, is a subsequence
$\sigma(i_{1})\ldots\sigma(i_{k})$ of $\sigma$ such that the following all
hold:

  * •

$\sigma(i_{1})\ldots\sigma(i_{k})$ is an occurrence of $\pi$ in the classical
sense,

  * •

$\forall a\in A.\ i_{a+1}=i_{a}+1$

  * •

$\forall b\in B.\ j_{b+1}=j_{b}+1$

where $\\{\sigma(i_{1}),\ldots,\sigma(i_{k})\\}=\\{j_{1},\ldots,j_{k}\\}$ and
$j_{1}<j_{2}<\cdots<j_{k}$. By convention $i_{0}=j_{0}=0$ and
$i_{k+1}=j_{k+1}=n+1$. As with vincular patterns, $A$ is the set of
adjacencies of indexes, but now the set $B$ defines the adjacencies of values.
For example, the bivincular pattern $(312,\\{2\\},\\{2\\})$ can be found in
$\sigma=521634$ as the subsequence $534=\sigma(1)\sigma(5)\sigma(6)$. Figure
2(c) illustrates this bivincular containment with the pattern permutation and
the shading of the adjacency in values (rows) and indices (columns)
highlighted.

All of the above patterns can be generalised as _mesh patterns_ , which were
introduced in Brändén and Claesson (2011). A mesh pattern of length $k$ is a
pair $(\pi,R)$ with $\pi\in S_{k}$ and $R\subseteq[0,k]\times[0,k]$, a set of
pairs of integers. The elements of $R$ identify the lower left corners of unit
squares in the plot of $\pi$ and specify forbidden regions. An occurrence of a
mesh pattern $(\pi,R)$ in a permutation $\sigma$ is a subsequence
$\sigma(i_{1})\ldots\sigma(i_{k})$ such that the following holds

  * •

$\sigma(i_{1})\ldots\sigma(i_{k})$ is order isomorphic to $\pi$

  * •

$(x,y)\in R\Rightarrow$ there does not exist
$i\in\\{1,\ldots,n\\}:i_{x}<i<i_{x+1}\land\sigma(i_{\pi^{-1}(y)})<\sigma(i)<\sigma(i_{\pi^{-1}(y+1)})$.

For this definition we extend the subsequence $i_{j}$, $\sigma$ and $\pi$ with
$i_{0}=0$, $i_{k+1}=n+1$, $\pi(0)=0$, $\pi(k+1)=k+1$, $\sigma(0)=0$ and
$\sigma(n+1)=n+1$. The extra terms for $i_{j}$, $\sigma$ and $\pi$ in the
second part of the definition above allow mesh patterns to constrain a
permutation outside of the pattern. An example of a mesh pattern in
$\sigma=521634$ is $(132,(0,0),(2,1),(2,2))$, which can be found as the
subsequence $263=\sigma(2)\sigma(4)\sigma(5)$. This example is illustrated in
Figure 2(d), where each of the forbidden regions/squares is shaded.

A _boxed mesh pattern_ (or _boxed pattern_ , as introduced in Avgustinovich et
al. (2013)), is a special case of a mesh pattern $P=(\pi,R)$ where $\pi$ is a
permutation of length $k$ and $R=[1,k-1]\times[1,k-1]$. $P$ is then denoted by
$\pi$. For example the boxed pattern $231$ is contained in the permutation
$236514$ as the subsequence $351=\sigma(2)\sigma(4)\sigma(5)$. Figure 2(e)
shows this example, and illustrates that for a boxed mesh pattern the box
inside the permutation is the forbidden region.

_Consecutive patterns_ are a special case of vincular patterns, where it is
necessary that _all_ entries are adjacent. For example, the consecutive
pattern $(312,\\{1,2\\})$ can be found inside $152463$ as the subsequence
$524=\sigma(2)\sigma(3)\sigma(4)$. This example is shown in Figure 2(f).

We say a permutation $\sigma$ _avoids_ any of the above pattern types, if the
permutation $\pi$ of the pattern is classically avoided in $\sigma$, or it is
classically contained in $\sigma$ but for every occurrence of the classical
pattern the additional constraints on indices or values are not upheld.

So for example the permutation $\sigma=12345$ avoids the classic pattern
$\pi=21$, as there are no occurrences of it. Figure 3(a) attempts to
illustrate this avoidance. Similarly, the permutation $\sigma=12345$ avoids
the mesh pattern $(132,(0,0),(2,0),(2,1),(2,2))$ as there is no classical
occurrence of $132$ in $\sigma$, as can be seen from Figure 3(b). Finally,
$(132,(0,0),(2,0),(2,1),(2,2))$ is not contained in the permutation
$\sigma=652413$ even though there is an occurrence of $132$ in the $\sigma$,
namely as $243=\sigma(3)\sigma(4)\sigma(6)$, but there is an element of the
permutation that violates the forbidden region. In Figure 3(c) we can see that
the element $1=\sigma(5)$ is in the $(2,0)$ shaded/forbidden region.

(a) Classic Pattern

(b) Vincular Pattern

(c) Bivincular Pattern

(d) Mesh Pattern

(e) Boxed Mesh Pattern

(f) Consecutive Pattern

Figure 2: Examples of all patterns and for each an example containment in a
larger permutation. In each subfigure the pattern is on the left and an
occurrence of the pattern is indicated in the right permutation. We highlight
a classic occurrence (the elements that are order isomorphic to the pattern
permutation) with circles around the nodes. All additional constraints (in
terms of adjacency in index or values, or the forbidden cells/regions) are
shaded. In the target permutation the shaded regions scale with respect to the
elements which are representative of the classic pattern.

(a) $12345$ avoids the classic pattern $21$.

(b) $652413$ avoids the mesh pattern $(132,(2,0),(2,1),(2,2))$.

(c) $652413$ avoids the mesh pattern $(132,(2,0),(2,1),(2,2))$.

Figure 3: Examples of pattern avoidance. In subfigures (a) and (b) there is no
subsequence in the target permutation which is order isomorphic to the pattern
permutation (i.e. there is no occurrence of the classic pattern in the target
permutation). Subfigure (c) avoids the mesh pattern even though the pattern
permutation is contained classically, in each occurrence (there is only one)
there are (at least one) elements in the target permutation which lie in the
shaded/forbidden region.

###  2.2 Permutation Properties

In addition to containing (or avoiding) patterns in permutations and
enumerating these permutations, permutations can have certain structural
properties. We give some of the most common properties here, all of which we
will model with CP. Table 1 contains a list of the properties which we have
modelled thus far. For each property, we can require solutions to either do,
or do not, satisfy the property.

An _interval_ of a permutation $\pi$ corresponds to a set of contiguous
indices $I=[a,b]$ such that the set of values $\pi(I)=\\{\pi(i):i\in I\\}$ is
also contiguous. Every permutation of length $n$ has intervals of lengths 0, 1
and $n$. If a permutation $\pi$ has no other intervals, then $\pi$ is said to
be _simple_ Brignall (2010). For example, $\pi=1632547$ is not simple as it
contains the intervals $\pi(3)\pi(4)$, $\pi(5)\pi(6)$,
$\pi(3)\pi(4)\pi(5)\pi(6)$, $\pi(2)\pi(3)\pi(4)\pi(5)\pi(6)$,
$\pi(2)\pi(3)\pi(4)\pi(5)\pi(6)\pi(7)$ and
$\pi(1)\pi(2)\pi(3)\pi(4)\pi(5)\pi(6)$, as indicated in Figure 4(a) through
bold boxes around the intervals. The permutation $246135$ in Figure 4(d) is
simple, as the only intervals it contains are of length 0, 1 or the whole
permutation.

Given a permutation $\sigma=\sigma(1)\ldots\sigma(m)$ of length $m$ and non-
empty permutations $\alpha_{1},\ldots,\alpha_{m}$ the _inflation_ of $\sigma$
by $\alpha_{1},\ldots,\alpha_{m}$, written as
$\sigma[\alpha_{1},\ldots,\alpha_{m}]$, is the unique permutation obtained by
replacing each entry $\sigma(i)$ by an interval that is order isomorphic to
$\alpha_{i}$, where the relative ordering of the intervals corresponds to the
ordering of the entries of $\sigma$. Conversely, a _block-decomposition_ or
_deflation_ of a permutation $\pi$ is any expression of $\pi$ written as an
inflation $\pi=\sigma[\alpha_{1},\ldots,\alpha_{m}]$. For example $521634$ can
be decomposed as $3142[1,21,1,12]$. In Figure 4(e) we have highlighted the
blocks of the permutation $521634$, we can observe that the blocks are placed
order isomorphic to $3142$.

A permutation $\pi$ is _plus-decomposable_ if it has a block-decomposition of
the form $\pi=12[\alpha_{1},\alpha_{2}]$ for non-empty permutations
$\alpha_{1}$ and $\alpha_{2}$. For example $213654$ is a plus-decomposable
permutation, but $546123$ or $521634$ (which is also not simple) are not.
Figure 4(b) shows the blocks of $213654$, plus-decomposable permutations will
always be in this layout (elements in the bottom left quadrant, and elements
in the top right quadrant).

A permutation $\pi$ is _minus-decomposable_ if it has a block-decomposition of
the form $\pi=21[\alpha_{1},\alpha_{2}]$ for non-empty permutations
$\alpha_{1}$ and $\alpha_{2}$. For example $546123$ is a minus-decomposable
permutation. But $213654$ (which is plus-decomposable) or $236145$ (which is
not simple) are not. Figure 4(c) contains the minus-decomposable permutation
$546123$. All minus-decomposable permutations will have a similar layout, with
elements in the top left quadrant, followed by elements in the bottom right
quadrant.

A permutation $\pi\in S_{n}$ is _block-wise simple_ if and only if it has no
interval which can be decomposed into $12[\alpha_{1},\alpha_{2}]$ or
$21[\alpha_{1},\alpha_{2}]$. This property was introduced in Bagno et al.
(2023) alongside an equivalent recursive recursive definition. For example
$2413[3142,1,1,1]=4253716$ is block-wise simple (Figure 4(f)), but $24513$ is
not as the interval $45$ can be decomposed into $12[1,1]$ (Figure 4(g)).

A fixed point of a permutation $\pi$ is an integer $i$ such that $\pi(i)=i$. A
_derangement_ is a permutation with no fixed points. $4312$ is a derangement
whereas $1234$ is not. As shown in Figure 4(i) none of the elements of the
permutation $4312$ are on the red diagonal (which represents $\pi(i)=i$).

Similarly, a _nonderangement_ is a permutation with at least one fixed point.
$2431$ is a non-derangement whereas $4321$ is not. The plot of $2431$ in
Figure 4(j) shows $\pi(3)=3$ lies on the diagonal.

A permutation $\pi\in S_{n}$ is called an _involution_ if $\pi=\pi^{-1}$, or
equivalently if $\forall i,j.\ \pi(i)=j\iff\pi(j)=i$. $1243$ is an involution
but $2431$ is not. Figure 4(h) contains the plot of the involution $1243$.

A permutation $\pi\in S_{n}$ is said to have _parity_ if the values at odd
indexes are odd and the values in even indexes are even, i.e. $\pi(i)=i\mod
2,\ \forall i\in\\{1,\ldots,n\\}$. For example the permutation $3412$ has
parity, whereas $2413$ as in the latter for example the value $2$ (even) is at
index $1$ which is odd. Figure 4(k) and Figure 4(l) show the plots of the two
example permutations.

(a) Intervals in a permutation

(b) Plus-decomposable permutation

(c) Minus-decomposable permutation

(d) Simple permutation

(e) Block-decomposition of a permutation

(f) Block-wise simple permutation

(g) Not block-wise simple permutation

(h) Involution

(i) Derangement

(j) Non-derangement

(k) Parity

(l) Non-parity

Figure 4: Examples permutation properties. Intervals (of length 1 and up to
$n$-1, where $n$ is the length of the permutation) and blocks are indicated
using squares around the nodes that contain them. The red diagonal line for
the derangement/non-derangement indicates the $\pi(i)=i$ fixed point property.

###  2.3 Permutation Statistics

Currently we support 5 different permutation statistics, where we count the
occurrences of some property of the elements of the permutation. The
constraint solvers will output the statistics alongside the solution
permutations. The statistics we currently consider are ascents, descents,
inversions, excedances and the Major index (as listed in Table 1).

These statistics can be collected as part of finding the solutions, or
constrained. These constraints on the statistics can be arbitrary arithmetic
statements, for example permutations with 5 descents, or the number of
descents and ascents added together is a multiple of three.

An _ascent_ in a permutation $\sigma$ is an index $i$ such that
$\sigma(i)<\sigma(i+1)$. Similarly, a _descent_ is an . An _excedance_ is an
index where $\sigma(i)>i$. So for a permutation $\sigma$ the statistics are

  * •

the number of _inversions_ inv$(\sigma)=|\\{(i,j):i<j\text{ and
}\sigma(i)>\sigma(j)\\}|$

  * •

the number of _descents_ des$(\sigma)=|\\{i:\sigma(i)>\sigma(i+1)\\}|$

  * •

the number of _ascents_ asc$(\sigma)=|\\{i:\sigma(i)<\sigma(i+1)\\}|$

  * •

the number of _excedances_ exc$(\sigma)=|\\{i:\sigma(i)>i\\}|$.

  * •

the _Major index_ , which is the sum of the positions of the descents
maj$(\sigma)=\sum_{\sigma(i)>\sigma(i+1)}i$.

As an example, in the permutation $\sigma=7164523$, inv$(\sigma)=14$,
des$(\sigma)=3$, asc$(\sigma)=3$, exc$(\sigma)=2$ and maj$(\sigma)=9$.

##  3 Composability in Action

We demonstrate the composability of the models using an illustrative (albeit
hypothetical) example scenarios and one example which extends the enumeration
of solutions to a conjecture in Claesson et al. (2012). The latter model gives
rise to 2 new conjectures.

###  3.1 Hypothetical Example

Suppose we are a permutation pattern researcher seeking insights into the set
of permutations that classically avoid the permutation $1324$. It is worth
noting that the growth function for this set of permutations has yet to be
discovered; see OEIS (OEIS Foundation Inc., 2023, A061552). A mathematician
working on this problem will adopt some assumptions, enumerate permutations
under these assumptions and refine these assumptions by studying the
enumeration. Given the rapid growth of the numbers, we examine prevalent
patterns and properties within our permutations, either contained or avoided,
and aim to filter them out. To illustrate how the CP approach easily cuts down
the number of solutions without having to go through generating permutations
and then filtering them we have split this example into 4 steps, in each step
we add more constraints (patterns and/or properties). We then show how many
solution permutations are found at each step in Table 2, with step 4
containing all properties (which is the full model for our example problem).
As the permutation pattern researcher we would only work with step 4, rather
than illustrative which contain fewer constraints.

In the context of exploring permutations that traditionally avoid the
permutation $1324$, let us assume we have finished exploring permutations that
contain the following mesh pattern:
$(213,(0,0),(0,1),(1,0),(1,0))$, so from now on we want to focus on
permutations which avoid this pattern (step 1,
Av($\\{1324,(213,(0,0),(0,1),(1,0),(1,0))\\}$)). Consider that we decide to
look at permutations which contain both the classic pattern $132$ and the mesh
pattern $(123,(1,2),(2,1),(1,3),(3,1))$ (step 2,
Co($\\{132,(123,(1,2),(2,1),(1,3),(3,1))\\}$)).

We instantiate a constraint programming model that combines the four patterns
above. We can also add properties, for example: minus-decomposable and
involution (step 3, minus-decomposable; step 4, involution).

Existing approaches allow a limited form of compositionality: they support the
enumeration of permutations that avoid a set of (mesh) patterns
simultaneously, as every pattern type can be turned into a mesh pattern. So
the traditional approach would be to enumerate the set of permutations which
avoid the two patterns $1324$ and $(213,(0,0),(0,1),(1,0),(1,0))$. We would
then need to iterate over this enumeration and filter permutations to identify
those containing the patterns $132$ and $(123,(1,2),(2,1),(1,3),(3,1))$.

As an example, for length $9$ there are $9!=362880$ permutations of which,
4862 avoid the two patterns (step 1). 2841 of these permutations then contain
the other two patterns (step 2). 1865 of these are minus-decomposable (step 3)
and finally only 19 are also involutions (step 4). Using a composed constraint
programming model for this problem we are able to directly enumerate the $19$
permutations of interest without going through several levels of generate-and-
test. We conduct the same experiment on permutation lengths ranging from 5 to
16. Table 2 shows the number of permutations enumerated at each step. This
table demonstrates that this technique is more efficient than generate-and-
test based methods, as the numbers between the columns/steps decrease rapidly.
For some permutation lengths (14–16), generate-and-test is not feasible
because earlier steps cannot be fully enumerated within the 1-hour time limit
we gave to Minion (a CP solver) Gent et al. (2006), but the combination of all
properties can be enumerated.

In addition to only enumerating permutations of interest, we can ask for
permutation statistics to be listed together with the enumeration as well. For
example we can request the number of descents and the number of inversions for
each the permutations in the final set within the same constraint programming
model.

Length | Number of permutations found [b]
---|---
Step 1 | Step 2 | Step 3 | Step 4
5 | 42 | 8 | 2 | 0 [t]
6 | 132 | 41 | 19 | 1
7 | 429 | 180 | 102 | 2
8 | 1,430 | 730 | 455 | 9
9 | 4,862 | 2,841 | 1,865 | 19
10 | 16,796 | 10,815 | 7,321 | 53
11 | 58,786 | 40,700 | 28,096 | 106
12 | 208,012 | 152,325 | 106,555 | 255
13 | 742,900 | 568,883 | 401,729 | 493
14 | - | - | - | 1,118
15 | - | - | - | 2,120
16 | - | - | - | 4,664
Table 2: Running the 4 steps on various permutation lengths. Dash indicates
timeout after 1-hour of Minion search

###  3.2 1324-avoiding permutations with a fixed number of inversions

Let us now look at the impact the constraint programming approach has on a
combination of property type and property that was investigated by Claesson et
al. (2012). We will focus on the conjecture 13 stated in Claesson et al.
(2012). This involves combining the 1324 classical pattern avoidance with a
fixed number of inversions.

######  Conjecture 1.

Claesson et al. (2012)

For all nonnegative integers $n$ and $k$, we have $S_{n}^{k}(1324)\leq
S_{n+1}^{k}(1324)$ (where $S_{n}^{k}(1324)$ is the set of permutations of
length $n$ with $k$ inversions and which avoid $1324$).

For example, the set $S_{5}^{9}(1324)=\\{45321,53421,54231,54312\\}$ is the
set of permutations of length 5 with each with 9 inversions and avoiding 1324
classically.

In the paper Claesson et al. (2012) present results of an exhaustive
enumeration algorithm, which found results of all inversions for permutations
up to length 15. Unfortunately, the authors do not disclose how the algorithm
worked, but we hypothesise that it might have been a generate and test
approach. Which first generates all 1324 avoiding permutations and then
filtered for the number of inversions.

As discussed before the constraint programming approach avoids this and thus
we have been able to expand the enumeration further, and give additional
insights into the conjecture. Further, there was no need for a specialised
algorithm or coding to test this conjecture, we only had to combine our
previously created model pieces for classical avoidance and counting
inversions. While we are unable to fully prove the conjecture, our results
demonstrate further support for the result.

Looking at Table 3 (this is a pattern that can be observed in Claesson et al.
(2012) as well) there is a point at which the number of permutations per
inversion count does not change. In other words, there is a point at which it
does not matter what the length ($n$) of the permutation is the number of
permutations which avoid 1324 and have a given number of inversion is the same
as $n+1$. To confirm this we have expanded the calculations to the
permutations of length 16 and all possible number of inversions. Further, we
are able to strongly suggest at which point this enumeration does not change,
up to 20 inversions.

We enumerated the permutations for this problem for permutation lengths from 1
to 25 and for the number of inversions ranging from 0 to 20. We used a large
compute server with 256 cores and 1TB of memory for this task. Each
enumeration is allowed to use up to 250 cores on this machine. The longest
running instance (length 23 and number of inversions 20) took just over 5 days
in this parallel computing setting, which is the equivalent of running the
same enumeration on a single core for 3.5 years. This parallel setting
highlights a significant advantage of employing CP: the feasibility of
leveraging high-performance, parallel CP solvers, such as Minion, which can
take advantage of the widely accessible multi-core machine without requiring
any special development.

Table 3 only contains some of these results, the full enumeration of up to
length 16 (over all inversions) and up to length 23 (up to 20 inversions) can
be found in our repository Özgür Akgün et al. (2023).

######  Conjecture 2.

Let $k$ be a given number of inversions, the number of permutations in
$S_{n}^{k}(1324)$ will grow as long as $n\leq k+2$.

Further we have evidence that there is an identifiable sequence which the
stabilising points create.

######  Conjecture 3.

Let $n$ be a given length of permutations, then $S_{n}^{k}(1324)$ for
$k\in\\{0,\ldots,n-2\\}$ will be the first $n-1$ entries of (OEIS Foundation
Inc., 2023, A000712).

##  4 Conclusion

In this paper, we have presented a new approach to enumerating permutations
under multiple conditions by leveraging constraint programming. This approach
allows for a declarative definition of permutations properties and pattern
avoidance/containment conditions. Conditions and properties can be arbitrarily
composed. We have demonstrated the versatility of this approach by modelling
the pattern avoidance/containment by applying it to 2 examples, one of which
demonstrates how the constraint programming approach avoids having to generate
a large number of permutations before filtering for the ones based on the
additional properties/constraints.

In the second example this paper demonstrated the utility of the library of
constraint models by extending the computational results from Claesson et al.
(2012), to find more evidence towards their conjecture as well as identifying
2 new conjectures. This allowed us to leverage the parallel support of modern
CP solvers to solve in 5 days what would have taken 3.5 years on a single CPU
core.

This work contributes to the growing body of research on permutation
enumeration. The constraint programming based approach complements existing
computational tools, offering an alternative method that allows for greater
flexibility when solving non-standard permutation enumeration problems.

The application of constraint programming to this important field in
mathematics empowers mathematicians with a new flexible tool for investigating
complex permutation enumeration problems. We expect our approach to inspire
further research in this area and potentially lead to new mathematical
discoveries.

Length | Number of permutations found with a fixed number of inversions [b]
---|---
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
1 | 1 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
2 | 1 | 1 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
3 | 1 | 2 | 2 | 1 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
4 | 1 | 2 | 5 | 6 | 5 | 3 | 1 |  |  |  |  |  |  |  |  |  |  |  |  |  |
5 | 1 | 2 | 5 | 10 | 16 | 20 | 20 | 15 | 9 | 4 | 1 |  |  |  |  |  |  |  |  |  |
6 | 1 | 2 | 5 | 10 | 20 | 32 | 51 | 67 | 79 | 80 | 68 | 49 | 29 | 14 | 5 | 1 |  |  |  |  |
7 | 1 | 2 | 5 | 10 | 20 | 36 | 61 | 96 | 148 | 208 | 268 | 321 | 351 | 347 | 308 | 241 | 165 | 98 | 49 | 20 | 6
8 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 106 | 171 | 262 | 397 | 568 | 784 | 1019 | 1264 | 1478 | 1628 | 1681 | 1619 | 1441 | 1173
9 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 181 | 286 | 443 | 664 | 985 | 1416 | 1988 | 2715 | 3589 | 4579 | 5631 | 6654 | 7559
10 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 296 | 467 | 714 | 1077 | 1582 | 2305 | 3284 | 4617 | 6374 | 8665 | 11521 | 15012
11 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 477 | 738 | 1127 | 1682 | 2477 | 3584 | 5134 | 7240 | 10100 | 13915 | 18976
12 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 748 | 1151 | 1732 | 2577 | 3768 | 5450 | 7766 | 10976 | 15312 | 21171
13 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1161 | 1756 | 2627 | 3868 | 5634 | 8098 | 11526 | 16216 | 22632
14 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1766 | 2651 | 3918 | 5734 | 8282 | 11858 | 16786 | 23568
15 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1770 | 2661 | 3942 | 5784 | 8382 | 12042 | 17118 | 24138
16 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1770 | 2665 | 3952 | 5808 | 8432 | 12142 | 17302 | 24470
17 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1770 | 2665 | 3956 | 5818 | 8456 | 12192 | 17402 | 24654
18 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1770 | 2665 | 3956 | 5822 | 8466 | 12216 | 17452 | 24754
19 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1770 | 2665 | 3956 | 5822 | 8470 | 12226 | 17476 | 24804
20 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1770 | 2665 | 3956 | 5822 | 8470 | 12230 | 17486 | 24828
21 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1770 | 2665 | 3956 | 5822 | 8470 | 12230 | 17490 | 24838
22 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1770 | 2665 | 3956 | 5822 | 8470 | 12230 | 17490 | 24842
23 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1770 | 2665 | 3956 | 5822 | 8470 | 12230 | 17490 | 24842
A000712 | 1 | 2 | 5 | 10 | 20 | 36 | 65 | 110 | 185 | 300 | 481 | 752 | 1165 | 1770 | 2665 | 3956 | 5822 | 8470 | 12230 | 17490 | 24842
Table 3: The enumeration of permutations avoiding 1324 classically and
containing a fixed number of inversions. The rows are the length of the
permutation, the columns the number of inversions. The full results can be
found in the supplementary repository Özgür Akgün et al. (2023). The last row
shows the first 21 elements of the sequence A000712 (OEIS Foundation Inc.,
2023, A000712).

## References

  * Akgün et al. (2022) Ö. Akgün, A. M. Frisch, I. P. Gent, C. Jefferson, I. Miguel, and P. Nightingale.  Conjure: Automatic generation of constraint models from problem specifications.  _Artificial Intelligence_ , 310:103751, 2022.
  * Akgün et al. (2022) Ö. Akgün, M. Mereb, and L. Vendramin.  Enumeration of set-theoretic solutions to the yang-baxter equation.  _Math. Comput._ , 91(335):1469–1481, 2022.  doi:10.1090/MCOM/3696.  URL https://doi.org/10.1090/mcom/3696.
  * Albert (2012) M. Albert.  Permlab: Software for permutation patterns, 2012.  URL https://github.com/mchllbrt/PermCode.
  * Albert et al. (2012) M. Albert, S. Linton, and R. Hoffmann.  Patternclass–permutation pattern classes, 2012.  URL https://gap-packages.github.io/PatternClass/.
  * Ardal et al. (2021) R. P. Ardal, T. K. Magnusson, Émile Nadeau, B. J. Kristinsson, B. A. Gudmundsson, C. Bean, H. Ulfarsson, J. S. Eliasson, M. Tannock, A. B. Bjarnason, J. Pantone, and A. B. Arnarson.  Permuta, Apr. 2021.  URL https://doi.org/10.5281/zenodo.4725759.
  * Atkinson (1999) M. D. Atkinson.  Restricted permutations.  _Discret. Math._ , 195(1-3):27–38, 1999.  doi:10.1016/S0012-365X(98)00162-9.  URL https://doi.org/10.1016/S0012-365X(98)00162-9.
  * Avgustinovich et al. (2013) S. Avgustinovich, S. Kitaev, and A. Valyuzhenich.  Avoidance of boxed mesh patterns on permutations.  _Discrete Applied Mathematics_ , 161(1-2):43–51, Jan. 2013.  ISSN 0166-218X.  doi:10.1016/j.dam.2012.08.015.
  * Babson and Steingrímsson (2000) E. Babson and E. Steingrímsson.  Generalized permutation patterns and a classification of the mahonian statistics.  _Séminaire Lotharingien de Combinatoire [electronic only]_ , 44:B44b–18, 2000.
  * Bagno et al. (2023) E. Bagno, E. Eisenberg, S. Reches, and M. Sigron.  Blockwise simple permutations, 2023.
  * Bousquet-Mélou et al. (2010) M. Bousquet-Mélou, A. Claesson, M. Dukes, and S. Kitaev.  (2+ 2)-free posets, ascent sequences and pattern avoiding permutations.  _Journal of Combinatorial Theory, Series A_ , 117(7):884–909, 2010.
  * Brändén and Claesson (2011) P. Brändén and A. Claesson.  Mesh patterns and the expansion of permutation statistics as sums of permutation patterns.  _The Electronic Journal of Combinatorics_ , pages P5–P5, 2011.
  * Brignall (2010) R. Brignall.  A survey of simple permutations.  _Permutation patterns_ , 376:41–65, 2010.
  * Claesson et al. (2012) A. Claesson, V. Jelínek, and E. Steingrímsson.  Upper bounds for the stanley–wilf limit of 1324 and other layered patterns.  _Journal of Combinatorial Theory, Series A_ , 119(8):1680–1691, 2012.  ISSN 0097-3165.  doi:https://doi.org/10.1016/j.jcta.2012.05.006.  URL https://www.sciencedirect.com/science/article/pii/S0097316512000891.
  * Distler et al. (2012) A. Distler, C. Jefferson, T. Kelsey, and L. Kotthoff.  The semigroups of order 10.  In M. Milano, editor, _Principles and Practice of Constraint Programming_ , pages 883–899, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.  ISBN 978-3-642-33558-7.
  * Frisch et al. (2008) A. M. Frisch, W. Harvey, C. Jefferson, B. Martínez-Hernández, and I. Miguel.  Essence: A constraint language for specifying combinatorial problems.  _Constraints_ , 13(3):268–306, 2008.
  * (16) GAP.  _GAP – Groups, Algorithms, and Programming, Version 4.12.2_.  The GAP Group, 2022.  URL https://www.gap-system.org.
  * Gent et al. (2006) I. P. Gent, C. Jefferson, and I. Miguel.  Minion: A fast scalable constraint solver.  In _ECAI_ , pages 98–102, 2006.
  * Knuth (1968) D. E. Knuth.  _The Art of Computer Programming, Volume I: Fundamental Algorithms_.  Addison-Wesley, 1968.
  * Magnusson and Ulfarsson (2012) H. Magnusson and H. Ulfarsson.  Algorithms for discovering and proving theorems about permutation patterns.  _arXiv preprint arXiv:1211.7110_ , 2012.
  * Marcus and Tardos (2004) A. Marcus and G. Tardos.  Excluded permutation matrices and the stanley–wilf conjecture.  _Journal of Combinatorial Theory, Series A_ , 107(1):153–160, 2004.
  * Nightingale et al. (2017) P. Nightingale, Ö. Akgün, I. P. Gent, C. Jefferson, I. Miguel, and P. Spracklen.  Automatically improving constraint models in savile row.  _Artificial Intelligence_ , 251:35–61, 2017.
  * OEIS Foundation Inc. (2023) OEIS Foundation Inc.  The On-Line Encyclopedia of Integer Sequences, 2023.  Published electronically at http://oeis.org.
  * Simion and Schmidt (1985) R. Simion and F. W. Schmidt.  Restricted permutations.  _European Journal of Combinatorics_ , 6(4):383–406, 1985.
  * Émile Nadeau et al. (2021) Émile Nadeau, C. Bean, H. Ulfarsson, J. S. Eliasson, and J. Pantone.  Combinatorial specification searcher (permutaTriangle/comb_spec_searcher): Version 4.0.0, June 2021.  URL https://doi.org/10.5281/zenodo.4946832.
  * Özgür Akgün et al. (2023) Özgür Akgün, R. Hoffmann, and C. Jefferson.  stacs-cp/composable-permutation-patterns, Nov. 2023.  URL https://doi.org/10.5281/zenodo.10215929.