# A generating tree with a single label for permutations avoiding the vincular
pattern $1-32-4$

Matteo Cervetti Dipartimento di Matematica, Università di Trento.
<EMAIL_ADDRESS>
###### Abstract

In this paper we continue the study of permutations avoiding the vincular
pattern $1-32-4$ by constructing a generating tree with a single label for
these permutations. This construction finally provides a clearer explanation
of why a certain recursive formula found by Callan actually counts these
permutations, insofar as this formula was originally obtained only as a
consequence of a very intricated bijection with a certain class of ordered
rooted trees. This responds to a theoretical issue already raised by Duchi,
Guerrini and Rinaldi. As a byproduct, we also obtain an algorithm to generate
all these permutations and we refine their enumeration according to a simple
statistic, which is the number of right-to-left maxima to the right of 1.

##  1 Introduction

The study of patterns in permutations has grown in the last two decades to one
of the most active trends of research in contemporary combinatorics. The study
of permutations which are constrained by not having one or more subsequences
ordered in various prescribed ways has been historically motivated by the
problem of sorting permutations by means of certain devices. However, nowadays
research on this topic is further fueled by its intrinsic combinatorial
difficulty and from the plentiful appearances of patterns in several very
different disciplines, such as algebra, geometry, analysis, computer science,
mathematical physics and computational biology, and many others. For this
reason, it is reasonable to believe that this field of research will continue
growing for a long time to come.

More recently, the notion of vincular (or generalized) pattern in permutations
has been considered. Whereas an occurrence of a classical pattern $\pi$ in a
permutation $\sigma$ is simply a (non-necessarily consecutive) subsequence of
$\sigma$ whose items are in the same relative order as those in $\pi$, in an
occurrence of a vincular pattern, some items of that subsequence may be
required to be adjacent in the permutation. For instance, the classical
pattern $1234$ simply corresponds to an increasing subsequence of length 4,
whereas an occurrence of the generalized pattern $1-23-4$ would require the
middle two letters of that sequence to be adjacent in $\sigma$. Thus, the
permutation $23145$ contains $1234$ but not $1-23-4$. The study of vincular
patterns provides significant additions to the extensive literature on
classical patterns. In fact, the non-classical vincular patterns are likely to
provide richer connections to other combinatorial structures than the
classical ones do. Other than combinatorics, vincular patterns find
applications in other scientific topics such as, for instance, in the genome
rearrangement problem, which is one of the major trends in bioinformatics and
biomathematics.

The main issue we adress in this paper concerns permutations avoiding a well
known vincular pattern of length $4$, namely the pattern $1-32-4$. The paper
is organized as follows.

In Section 2 we fix the main notations and terminology which we will use
throughout the paper.

In Section 5 we describe our contribution to the study of permutations
avoiding $1-32-4$. Permutations avoiding this pattern were actually enumerated
by Callan in [C], who provided a recursive formula to count them only as a
collateral consequence of a very intricated bijection with a certain class of
ordered rooted trees. The problem of finding a more explicit justification for
the recursive formula obtained by Callan has received some attention in the
past decade (see [DGR]). In Section 5 we construct a generating tree with a
single label for permutations avoiding the vincular pattern $1-32-4$, finally
providing such a justification.

In order to introduct this topic, in Sections 3 and 4 we collect the latest
results about vincular pattern avoidance and we quickly review the ECO method,
which is the framework needed to describe the construction in Section 5.

##  2 The notion of vincular pattern

Let $n\in\mathbb{N}^{*}$ and denote $[n]=\\{1,2,...,n\\}$. For our purposes, a
_permutation of length_ $n$ will be just a word with $n$ distinct letters from
the alphabet $[n]$. The length of a permutation $\sigma$ will be denoted by
$|\sigma|$. We will denote by $\mathcal{S}_{n}$ the set of all permutations of
length $n$ and we will set
$\mathcal{S}=\bigcup_{n\in\mathbb{N}}\mathcal{S}_{n}$ (where by convention we
set $\mathcal{S}_{0}=\\{\varepsilon\\}$ and $|\varepsilon|=0$).

We begin by quickly recalling the classical definition of pattern in a
permutation. In general, given any poset $\mathcal{P}$ and two non-empty words
$\alpha$ and $\beta$ with length $k$ in the alphabet $\mathcal{P}$, we say
that $\alpha$ and $\beta$ are _order isomorphic_ , and we will write
$\alpha\sim\beta$ when, for every $i,j\in[k]$, $\alpha_{i}\leq\alpha_{j}$ if
and only if $\beta_{i}\leq\beta_{j}$. Let now $\sigma,\tau\in\mathcal{S}$ and
suppose $i\in[|\tau|]^{|\sigma|}$. We say that $i$ is an occurrence of
$\sigma$ in $\tau$ when $i_{1}<i_{2}<...<i_{|\sigma|}$ and
$\tau_{i_{1}}\tau_{i_{2}}...\tau_{i_{|\sigma|}}\sim\sigma$. We say that
$\sigma$ _occurs as pattern_ in $\tau$, and we write $\sigma\leq\tau$, when
either $\sigma=\varepsilon$ or one can find an occurrence of $\sigma$ in
$\tau$, we say that $\tau$ avoids $\sigma$ _as a_ pattern otherwise. It is
routine to check that $\leq$ is a partial order relation, turning
$\mathcal{S}$ into a poset, which is called the _permutation pattern poset_.

It is worth noting that the items in an occurrence of a classical pattern in a
permutation are not required to be necessarily consecutive, forcing this
further condition we obtain the consecutive pattern poset on $\mathcal{S}$.
With the notations as above, we say that $i$ is a consecutive occurrence of
$\sigma$ in $\tau$ when $i$ is a occurrence of $\sigma$ in $\tau$ (in the
classical sense) and either $|\sigma|=1$ or $i_{j+1}=i_{j}+1$ for every
$j\in[|\sigma|-1]$. In the same fashion, we say that $\sigma$ _occurs as
consecutive pattern_ in $\tau$ when one can find a consecutive occurrence of
$\sigma$ in $\tau$. The resulting poset on $\mathcal{S}$ will be called the
consecutive pattern poset. Usually, the consecutive pattern poset reveals a
much simpler structure than the classical pattern poset. For instance, the
Möbius function of the consecutive permutation pattern poset is completely
understood, whereas it is largely unknown in the classical case.

Consecutive and classical patterns are special (actually, extremal) cases of
the more general notion of vincular patterns. Vincular patterns were
introduced by Babson and Steingrimsson (under the name of generalized
patterns), and constitute a vast intermediate continent between the two lands
of consecutive patterns and classical patterns. Investigation of this
intermediate notion could hopefully shed some light on differences and
analogies between the extremal cases of consecutive and classical patterns. An
occurrence of a vincular pattern is basically an occurrence of that pattern in
which entries are subject to given adjacency conditions. For a more formal
definition of vincular pattern we follow [BF].

A dashed permutation is a permutation in which some dashes are possibly
inserted between any two consecutive letters. For instance, $5-13-42$ is a
dashed permutation (of length 5). The type of a dashed permutation $\sigma$
such that $|\sigma|\geq 2$ is the $\\{0,1\\}-$vector
$r=(r_{1},...,r_{|\sigma|-1})\in\\{0,1\\}^{|\sigma|-1}$ such that $r_{i}=0$
whenever there is no dash between $\sigma_{i}$ and $\sigma_{i+1}$ and
$r_{i}=1$ whenever there is a dash between $\sigma_{i}$ and $\sigma_{i+1}$,
for every $i\in[|\sigma|-1]$. For example, the above dashed permutation
$5-13-42$ has type $(1,0,1,0)$. Given a dashed permutation $\sigma$, the
underlying permutation of $\sigma$ is the permutation obtained by removing the
dashes from $\sigma$. For instance, the compresed permutation of $5-13-42$ is
the permutation $51342$. Let $\sigma$ be a dashed permutation. With the same
notations as before, given some
$i=(i_{1},...,i_{|\sigma|})\in[|\tau|]^{|\sigma|}$, we say that $i$ is an
occurrence of $\sigma$ in $\tau$ when it is a (classical) occurrence of the
underlying permutation of $\sigma$ and $i_{j+1}=i_{j}+1$ whenever
$j\in[|\sigma|-1]$ and $\sigma_{j}$ and $\sigma_{j+1}$ are not separated by a
dash. We say that $\sigma$ _occurs as a vincular pattern_ in $\tau$ when one
can find an occurrence of $\sigma$ in $\tau$, we say that $\tau$ _avoids_
$\sigma$ _as a vincular pattern_ otherwise. Given a dashed permutation
$\sigma$, the set of all permutations avoiding $\sigma$ will be denoted by
$\mathcal{S}(\sigma)$ and the set of all $\sigma\in\mathcal{S}(\sigma)$ such
that $|\sigma|=n$ will be denoted by $\mathcal{S}_{n}(\sigma)$.

##  3 Previous work on vincular pattern avoidance

In this section we provide a quick overview of the latest results in
enumeration of permutations avoiding a vincular pattern. We refer to [Ki1] and
[Ste] for a more detailed survey on this topic. The first systematic study of
vincular patterns of length 3 was done by Claesson in [Cl] and permutations
avoiding $\pi$ have been enumerated for every vincular pattern $\pi$ of length
3.

It is worth mentioning that the fact that, as it turns out,
$\mathcal{S}(1-23)$ is counted by the Bell numbers shows that the analogous of
the Stanley-Wilf conjecture does not hold for some vincular patterns.
Moreover, the same fact shows that the conjecture of Noonan and Zeilberger
stated in [NZ] is also false for vincular patterns, namely, the number of
permutations avoiding a vincular pattern is not necessarily polynomially
recursive.

As for vincular patterns of length 4, it is stated in [Ste] that there are 48
symmetry classes of vincular patterns of length 4, and computer experiments
show that there are at least 24 Wilf-equivalent classes (although their exact
number seems to be unknown). For vincular non-classical patterns enumerative
results are known for seven Wilf classes (out of at least 24) which are as
follows:

  * •

Elizalde and Noy [EN] gave the exponential generating functions for the number
of occurrences of a consecutive pattern of length $4$ for three out of the
seven Wilf-equivalence classes for consecutive patterns, namely the classes
with representatives 1234, 1243 and 1342.

  * •

Kitaev [Ki2] and Elizalde [E] decomposed the class $\mathcal{S}(\sigma-k)$ in
a suitable boxed product, where $\sigma$ is any consecutive pattern and
$k=|\sigma|+1$. This decomposition allows to provide an expression for the
exponential generating function of $\mathcal{S}(\sigma-k)$ in terms of the
exponential generating function of $\mathcal{S}(\sigma)$. In particular, if
$\sigma$ is any consecutive pattern of length 3, this, together with the
results of Elizalde and Noy [EN], yields an explicit formula for the
exponential generaing function $\mathcal{S}(\sigma-4)$, where $\sigma$ is any
consecutive pattern of length 3. Since there are precisely two Wilf-
equivalence classes of consecutive patterns of length 3, with representatives
$123$ and $132$, the result of Kitaev yields explicit formulas for the
exponential generating functions of $\mathcal{S}(\pi)$ where $\pi$ is any
vincular pattern Wilf-equivalent to $123-4$ or $132-4$. Explicitly, these
formulas are

$\exp\left(\frac{\sqrt{3}}{2}\int_{0}^{x}\frac{e^{\frac{t}{2}}}{\cos\left(\frac{\sqrt{3}}{2}t+\frac{\pi}{6}\right)}\right)\
\ \mathrm{and}\ \
\exp\left(\int_{0}^{x}\frac{dt}{1-\int_{0}^{t}e^{-\frac{u^{2}}{2}}du}\right)$

for a vincular pattern Wilf-equivalent to $123-4$ or $132-4$, respectively.

  * •

Callan gave a recursion for $a_{n}=|\mathcal{S}_{n}(31-4-2)|$, which goes as
follows. Set $a_{0}=c_{1}=1$ and

    * 1.

$a_{n}=\sum_{i=0}^{n-1}a_{i}c_{n-i}$ for $n\geq 1$.

    * 2.

$c_{n}=\sum_{i=0}^{n-1}ia_{(n-1),i}$ for $n\geq 2$.

    * 3.

$a_{n,k}=\begin{cases}\sum_{i=0}^{k}a_{i}\sum_{j=k-i}^{n-1-i}a_{(n-1-i),j}&1\leq
k\leq n-1\\\ a_{n-1}&k=n\end{cases}$

  * •

Finally, Callan also showed in [C] that
$|\mathcal{S}_{n}(1-32-4)|=\sum_{k=1}^{n}u(n,k)$ where, for every $1\leq k\leq
n$, the triangle $u(n,k)$ satisfies the recurrence relation

$u(n,k)=u(n-1,k-1)+k\sum_{j=k}^{n-1}u(n-1,j)$ (1)

with initial conditions $u(0,0)=1$ and $u(n,0)=0$ for every $n\geq 1$.

As far as the author knows, these seem to be the only explicit enumerative
results concerning vincular patterns of length 4. An alternative, and we
believe more explicative, proof of the recursive formula in Equation
$(\ref{Callan})$ will be the main issue of the next sections.

##  4 ECO method

In this section we provide a quick digression on ECO method, which proved to
be the most suitable framework for describing the construction in Section 5.
The ECO method (Enumerating Combinatorial Objects method) was introduced by
Barcucci, Del Lungo, Pergola and Pinzani [BDLPP] and it is quite a natural
approach to generation and enumeration of combinatorial classes of objects
according to their size. The main idea of the ECO method consists of looking
for a way to grow objects from smaller to larger ones by making some local
expansions, where each object should be obtained from a unique father so that
this construction gives rise to a tree that allows us to recursively generate
all the objects in the class. If the shape of this tree can be described with
a simple rule there is hope for exact enumeration results, translating this
description into equations for the generating function of the class.

In the following we borrow standard terminology and notation about
combinatorial classes from [FS]. Let $\mathcal{A}$ be a combinatorial class
and denote by $\mathcal{A}_{n}$ the set of all $x\in\mathcal{A}$ such that
$|x|_{\mathcal{A}}=n$ for every $n\in\mathbb{N}$. Let
$\vartheta:\mathcal{A}\longrightarrow 2^{\mathcal{A}}$ be a map. We say that
$\vartheta$ is an ECO operator on $\mathcal{A}$ when for every
$n\in\mathbb{N}$ the following conditions hold:

  * (i)

$\vartheta(\mathcal{A}_{n})\subseteq 2^{\mathcal{A}_{n+1}}$.

  * (ii)

for every $y\in\mathcal{A}_{n+1}$ one can find some $x\in\mathcal{A}_{n}$ such
that $y\in\vartheta(x)$.

  * (iii)

$\vartheta(x_{1})\cap\vartheta(x_{2})=\emptyset$ for every
$x_{1},x_{2}\in\mathcal{A}_{n}$ such that $x_{1}\neq x_{2}$.

In particular $\\{\vartheta(x):\ x\in\mathcal{A}_{n}\\}$ is a partition of
$\mathcal{A}_{n+1}$. In other words, the map $\vartheta$ generates all the
objects of the class $\mathcal{A}$ in such a way that each object in
$\mathcal{A}_{n+1}$ is obtained from a unique object in $\mathcal{A}_{n}$ for
every $n\in\mathbb{N}$. Actually, we can also characterize ECO operators as
follows. We say that a map
$\rho:\mathcal{A}\smallsetminus\mathcal{A}_{0}\longrightarrow\mathcal{A}$ is a
reduction operator on $\mathcal{A}$ when
$\rho(\mathcal{A}_{n+1})\subseteq\mathcal{A}_{n}$ for every $n\in\mathbb{N}$.
The next proposition states that defining an ECO operator is essentially
equivalent to defining a reduction operator. In the following, for a function
$f:A\longrightarrow B$, we will denote by $f^{\longleftarrow}$ the function
$f^{\longleftarrow}:B\longrightarrow 2^{A}$ assigning to each $b\in B$ its
preimage $f^{\longleftarrow}(b)$ under $f$, i.e. the set of all $a\in A$ such
that $f(a)=b$.

######  Proposition 4.1.

Let $\mathcal{A}$ be a combinatorial class and
$\vartheta:\mathcal{A}\longrightarrow 2^{\mathcal{A}}$ be a map. Then
$\vartheta$ is an ECO operator on $\mathcal{A}$ if and only if
$\vartheta=\rho^{\longleftarrow}$ for some reduction operator $\rho$ on
$\mathcal{A}$.

###### Proof.

Suppose $\vartheta$ is an ECO operator and
$y\in\mathcal{A}\smallsetminus\mathcal{A}_{0}$, then $y\in\mathcal{A}_{n+1}$
for some $n\in\mathcal{N}$, hence $y\in\vartheta(x)$ for a unique
$x\in\mathcal{A}_{n}$, because $\vartheta$ is an ECO operator, and we set
$\rho(y)=x$. Let now $\rho:\mathcal{A}\longrightarrow\mathcal{A}$ denote the
map assigning the object $\rho(y)$ to each $y\in\mathcal{A}$. Then by
definition $\rho(\mathcal{A}_{n+1})\subseteq\mathcal{A}_{n}$ for every
$n\in\mathbb{N}$, furthermore, for every $x\in\mathcal{A}$, again by
definition $y\in\vartheta(x)$ if and only if $x=\rho(y)$, equivalently
$y\in\rho^{\longleftarrow}(x)$, hence $\vartheta(x)=\rho^{\longleftarrow}(x)$
and $\vartheta=\rho^{\longleftarrow}$. Conversely, suppose
$\vartheta=\rho^{\longleftarrow}$ for some reduction operator $\rho$ on
$\mathcal{A}$. Take $n\in\mathbb{N}$, $x\in\mathcal{A}_{n}$ and
$y\in\vartheta(x)=\rho^{\longleftarrow}(x)$, then $\rho(y)=x$, hence
$y\in\mathcal{A}_{n+1}$ because
$\rho(\mathcal{A}_{n+1})\subseteq\mathcal{A}_{n}$. Pick now
$y\in\mathcal{A}_{n+1}$ and let $x=\rho(y)\in\mathcal{A}_{n}$, then by
assumption $y\in\rho^{\longleftarrow}(x)=\vartheta(x)$. Finally, suppose
$x_{1},x_{2}\in\mathcal{A}_{n}$ and
$y\in\vartheta(x_{1})\cap\vartheta(x_{2})=\rho^{\longleftarrow}(x_{1})\cap\rho^{\longleftarrow}(x_{2})$,
then $x_{1}=\rho(y)=x_{2}$. This proves that $\vartheta$ is an ECO operator on
$\mathcal{A}$. ∎

Let $\vartheta$ be an ECO operator on $\mathcal{A}$. Say that $\mathcal{A}$ is
rooted when $\mathcal{A}$ contains a unique object with minimum size. Suppose
$\mathcal{A}$ is rooted. In this case, one can represent $\vartheta$ by means
of a tree, called the generating tree of $\vartheta$ and denoted by
$\mathcal{T}_{\vartheta}$, which is a rooted tree having the objects of
$\mathcal{A}$ as nodes, the object in $\mathcal{A}$ with minimum size as root
and such that $\vartheta(x)$ is the set of children of $x$ for every
$x\in\mathcal{A}$. This representation of $\vartheta$ can be useful for
enumeration purpose when $\mathcal{T}_{\vartheta}$ displays enough regularity
to be described by a so-called succession rule. Let $S$ be a set, let $a$ be
an element of $S$, let $e$ be a sequence of maps in $S^{S}$ and let
$p:S\longrightarrow\mathbb{N}$ be a map. The triple $(a,e,p)$ will be called
the succession rule with axiom $a$, production rule $e$ and production
parameter $p$ and it will be denoted by the symbol

$\begin{cases}(a)\\\
(k)\leadsto(e_{1}(k))(e_{2}(k))...(e_{p(k)}(k))\end{cases}$

Let now $\mathcal{T}$ be a rooted tree with set of nodes $T$ and root $R$, let
$\Omega=(a,e,p)$ be a succession rule and let $\ell:T\longrightarrow S$ be a
map. We say that $\ell$ is a $\Omega-\emph{labelling}$ of $\mathcal{T}$ when
$\ell(R)=a$ and, if $v\in T$, then $v$ has $p(\ell(v))$ children
$v_{1},...,v_{p(\ell(v))}$ and $\ell(v_{i})=e_{i}(\ell(v))$ for every
$i\in[p(\ell(v))]$. We say that $\vartheta$ and $\mathcal{A}$ are described by
$\Omega$ when one can find some $\Omega-$labelling of
$\mathcal{T}_{\vartheta}$. Suppose now $S\subseteq\mathbb{N}$ and $\ell$ is an
$\Omega-$labelling of $\mathcal{T}_{\vartheta}$. Denote by $\mathcal{A}(z,u)$
the generating function

$\mathcal{A}(z,u)=\sum_{\sigma\in\mathcal{A}}z^{|\sigma|}u^{\ell(\sigma)}=\sum_{n,k\geq
0}|\mathcal{A}_{n,k}|z^{n}u^{k}$

where $\mathcal{A}_{n,k}$ denotes the set of all $\sigma\in\mathcal{A}_{n}$
such that $\ell(\sigma)=k$ for every $(n,k)\in\mathbb{N}^{2}$. We can
translate the $\Omega-$description of $\mathcal{A}$ into a functional equation
for $\mathcal{A}(z,u)$ as follows. Denote by $L_{\Omega}$ the unique
$\mathbb{Z}[[z]]-$linear map
$L_{\Omega}:\mathbb{Z}[[z,u]]\longrightarrow\mathbb{Z}[[z,u]]$ such that

$L_{\Omega}(u^{k})=\begin{cases}u^{a}&k=0\\\
u^{e_{1}(k)}+...+u^{e_{p(k)}(k)}&k\geq 1\end{cases}$

Then it is easily seen that

$\mathcal{A}(z,u)=\mathcal{A}(0,u)+zL_{\Omega}(\mathcal{A}(z,u)).$

In the luckiest cases, these kind of equations can be solved using kernel type
methods or other standard tools.

##  5 Permutations avoiding the pattern $1-32-4$

The vincular pattern $1-32-4$ is a dashed version of the classical pattern
$1324$, which attracted great attention among combinatorialists, as
enumeration of permutations avoiding this classical pattern has proven to be
one of the hardest open problems in permutation pattern combinatorics.
Hopefully, our insight into the class of permutations avoiding the classical
pattern could benefit from a closer study of permutations avoiding one of its
vincular counterparts. However, these two patterns seem also to display quite
a different behaviour, for instance it is not difficult to see that $1-32-4$
is actually Wilf-equivalent to $1-23-4$ (see [E]), whereas this does not hold
for their classical counterparts.

Permutations avoiding $1-32-4$ are counted by sequence A113227 in [S], whose
first ten terms are 1, 1, 2, 6, 23, 105, 549, 3207, 20577, 143239. As
mentioned in Section 3, an efficient bivariate recursive formula to count
permutations avoiding $1-32-4$ was first discovered by Callan in [C]. This
formula actually relies on a very intricated bijection (involving several
contrived discrete structures defined ad hoc in order to break this
transformation into somewhat simpler steps) between permutations of length $n$
avoiding $1-32-4$ and increasing ordered rooted trees on $n+1$ nodes with
increasing leaves for every $n\geq 1$. An ordered rooted tree on $n+1$ nodes
$\\{0,1,2,...,n\\}$ is increasing when every node is smaller than each of its
children. If in addition its leaves are increasing from left to right we say
that it has increasing leaves. For instance, the figure below shows two
increasing ordered rooted trees, the first has increasing leaves while the
second does not.

3240617895

4260317985

Let $\mathcal{I}$ denote the combinatorial class of such trees. If, for every
$1\leq k\leq n$, we denote by $u(n)$ the number of trees in $\mathcal{I}_{n}$
and by $u(n,k)$ the number of trees in $\mathcal{I}_{n}$ such that the root
has $k$ children, so that $u(n)=\sum_{k=1}^{n}u(n,k)$, then it is easily
proved in [C] that the triangle $u(n,k)$ satisfies the recurrence relation

$u(n,k)=u(n-1,k-1)+k\sum_{j=k}^{n-1}u(n-1,j)$ (2)

when $1\leq k\leq n$, with initial conditions $u(0,0)=1$ and $u(n,0)=0$ for
every $n\geq 1$. Thanks to the bijection established by Callan, this recursive
formula allows also to count permutations of length $n$ avoiding $1-32-4$.
Although the recursive formula given in Equation $(\ref{(1-32-4)-recursion})$
provides an efficient way to enumerate these permutations, we believe it
provides only little insight into their structure, as it is not transparent at
all from the bijection constructed by Callan how to read this recursive
formula directly from a description of these permutations. Actually, it is not
even clear which statistic on these permutations should correspond to the
number of children of the root. Some unsuccesful attempts to read the
recursive formula given in Equation $(\ref{(1-32-4)-recursion})$ directly from
a description of permutations avoiding $1-32-4$ have been made. As far as we
know, the best result in this direction has been achieved by Duchi, Guerrini
and Rinaldi, who constructed a two labels generating tree for this class of
permutations as a consequence of a certain insertion algorithm called
$\mathsf{INSERTPOINT}$ (see [DGR]). However, in the same paper, they suggest
that the recursive formula given in Equation $(\ref{(1-32-4)-recursion})$
appears to be difficult to understand directly on $\mathcal{S}(1-32-4)$.
Additionally, as already pointed out by Callan, sequence A113227 also happens
to count quite a wide variety of combinatorial objects, among which we find
increasing ordered rooted trees with increasing leaves, valley marked Dyck
paths and inversion sequences avoiding the pattern $101$ (see [C] and [CMSW]).
In all these cases, it is instead relatively easy to read the recurrence
relation given in Equation $(\ref{(1-32-4)-recursion})$ from the same
structural description of these objects and it is actually not hard to
construct quite a straightforward bijection between them.

In this section we construct a single label generating tree for permutations
avoiding the pattern $1-32-4$. We believe that this construction finally break
the annoying asimmetry between the aforementioned combinatorial objects and
permutations avoiding $1-32-4$, by providing a better insight into the
structure of these permutations and, compared to Callan’s bijection, a clearer
explanation of why the recursive formula given in Equation
$(\ref{(1-32-4)-recursion})$ actually counts them. As remarkable byproducts of
this construction, we also obtain an explicit algorithm to generate all
permutations avoiding $1-32-4$ and we refine the enumeration of these
permutations according to a simple statistic, which is the number of right-to-
left maxima to the right of 1.

Figure 1: A valley marked Dyck path is a Dyck path in which, for each valley
$DU$, one of the lattice points between the valley vertex and the $x-$axis
inclusive is marked.

Although not explicitly stated in [C], the class $\mathcal{I}$ can be
described by a succession rule as follows. Consider the map
$e:\mathcal{I}\longrightarrow\mathbb{N}$ attaching to every $T\in\mathcal{I}$
the number $e(T)$ of the children of its root. One can easily construct an ECO
operator $\eta$ on the class $\mathcal{I}$ such that $e$ is a
$\Lambda-$labelling of $\mathcal{T}_{\eta}$ where $\Lambda$ is the succession
rule

$\begin{cases}(1)\\\ (k)\leadsto(1)(2)^{2}(3)^{3}...(k)^{k}(k+1)\end{cases}$

The ECO operator $\eta$ is implicitly described by Callan in [C] when he
proves that the class $\mathcal{I}$ is enumerated by the recursive formula in
Equation $(\ref{(1-32-4)-recursion})$, but we omit further details. We will
show that the class $\mathcal{S}(1-32-4)$ can be described by pretty the same
rule, which proves that the combinatorial classes $\mathcal{S}(1-32-4)$ and
$\mathcal{I}$ are isomorphic.

The outline of the proof is as follows. First, we attach to every permutation
$\pi$ a label $\ell(\pi)$ defined as the number of right-to-left maxima of
$\pi$ on the right of $1$ (e.g. $\ell(84617523)=3$ as the right-to-left maxima
of $84617523$ on the right of $1$ are exactly $7,5$ and $3$). Next, we define
an ECO operator $\vartheta$ on the combinatorial class $\mathcal{S}(1-32-4)$
and we show that the map $\ell:\mathcal{S}(1-32-4)\longrightarrow\mathbb{N}$
attaching to every $\pi\in\mathcal{S}(1-32-4)$ the label $\ell(\pi)$ is
actually an $\Omega-$labelling of $\mathcal{T}_{\vartheta}$ where $\Omega$ is
the succession rule

$\begin{cases}(0)\\\ (k)\leadsto(0)(1)^{2}(2)^{3}...(k)^{k+1}(k+1)\end{cases}$
(3)

This is the same as the succession rule

$\begin{cases}(1)\\\ (h)\leadsto(1)(2)^{2}(3)^{3}...(h)^{h}(h+1)\end{cases}$

up to the change of label $h=k+1$. The first 3 levels of the generating tree
defined by the succession rule $\Omega$ are displayed in Figure 2. Observe
also that it actually takes not much effort to deduce Equation
$(\ref{(1-32-4)-recursion})$ directly from the succession rule $\Omega$,
without any reference to increasing ordered rooted trees with increasing
leaves. As a corollary, we find that the recursive relation in Equation
$(\ref{(1-32-4)-recursion})$ for the triangle $u(n,k)$ also allows us to count
permutations of length $n$ avoiding $1-32-4$ with $k-1$ right-to-left maxima
to the right of 1.

Figure 2: The first 3 levels of the labeled tree defined by the succession
rule $\Omega$.

Actually, it is easier to construct our ECO operator $\vartheta$ moving
backwards, i.e. by first defining a reduction operator $\rho$ on
$\mathcal{S}(1-32-4)$ and then setting
$\vartheta(\pi)=\rho^{\longleftarrow}(\pi)$ for every
$\pi\in\mathcal{S}(1-32-4)$. Suppose $\pi$ is a permutation of length $n\geq
1$ avoiding $1-32-4$ such that $\ell(\pi)=k$. As already noted in [E], any
permutation of this kind can be written in the form

$\pi=m_{1}\ell_{11}...\ell_{1k_{1}}m_{2}\ell_{21}...\ell_{2k_{2}}...m_{h}\ell_{h1}...\ell_{hk_{h}}$
(4)

where $m_{1},...,m_{h}$ are the left to right minima of $\pi$ (and of course
$m_{h}=1$) for some $h\geq 1$, while, for every $1\leq i\leq h$, the letters
$\ell_{i1},...,\ell_{ik_{i}}$ (where possibly $k_{i}=0$, with obvious meaning)
denote non-empty increasing sequences such that
$\max(\ell_{ij})>\max(\ell_{i(j+1)})$ for every $j\in[k_{i}-1]$ when
$k_{i}\geq 2$. In particular $k_{h}=k$ by definition of $\ell(\pi)$. Actually,
a permutation that can be written in the form displayed in $(\ref{structure})$
avoids $1-32-4$ if and only if $\max(\ell_{(i+1)1})<\max(\ell_{i(k_{i}-1)})$
whenever $h\geq 2$, $i\in[h-1]$ and $k_{i}\geq 2$. For instance, the
permutation $\pi=(8,9,14,12,5,2,4,10,11,1,3,13,6,7)$ avoids $1-32-4$ and
decomposes as follows

$\begin{matrix}\pi=&(\bf{8},&\framebox{9,14},&\framebox{12},&\bf{5},&\bf{2},&\framebox{4,10,11},&\bf{1},&\framebox{3,13},&\framebox{6,7})\\\
&m_{1}&\ell_{11}&\ell_{12}&m_{2}&m_{3}&\ell_{31}&m_{4}&\ell_{41}&\ell_{42}\end{matrix}$

Figure 3: A plot of the permutation $\pi=(8,9,14,12,5,2,4,10,11,1,3,13,6,7)$
which avoids $1-32-4$. The left-to-right minima of $\pi$ are marked in bold.

where the left-to-right minima of $\pi$ are marked in bold. Note that in this
case $h=4$, while $k_{1}=2$, $k_{2}=0$, $k_{3}=1$ and $k_{4}=k=2$. There is
quite a natural way to reduce $\pi$ to another permutation $\rho(\pi)$ of
length $n-1$ avoiding the pattern $1-32-4$, namely by deleting $1$, performing
some further almost forced operations to restore the avoidance of the pattern
$1-32-4$ and taking the standard reduction of the sequence obtained in this
way (i.e. subtracting $1$ to each item of the sequence). Indeed, we can
distinguish two cases:

  * (i)

Suppose $2$ occurs to the left of $1$ in $\pi$, i.e. $h\geq 2$ and
$m_{h-1}=2$. In this case we say that $\pi$ has type $(2,1)$ and we can
construct $\rho(\pi)$ as follows. We delete $1$ from $\pi$ and restore the
structure displayed in $(\ref{structure})$ by sorting the list
$\ell_{(h-1)1},...,\ell_{(h-1)k_{h-1}},$ $\ell_{h1},...,\ell_{hk_{h}}$ of
increasing sequences to the right of $2$ in such a way that their maximum
elements are in decreasing order from left to right. Finally, we define
$\rho(\pi)$ as the standard reduction of the integer sequence obtained in this
way. It is clear by construction that $\rho(\pi)$ avoids $1-32-4$.

  * (ii)

Suppose $2$ occurs to the right of $1$ in $\pi$, i.e. either $h=1$ or $h\geq
2$ and $m_{h-1}\geq 3$, so that $\ell_{hi}=2\ell^{\prime}_{hi}$ for some
$i\in[k]$ and a possibly empty increasing sequence $\ell^{\prime}_{hi}$. In
this case we say that $\pi$ has type $(1,2)$ and we can construct $\rho(\pi)$
as follows. We delete $1$ and restore the structure displayed in
$(\ref{structure})$ by moving $2$ to the position previously occupied by $1$
(in other words we swap $1$ and $2$ and then delete $1$), thus obtaining the
integer sequence
$m_{1}\ell_{11}...\ell_{1k_{1}}m_{2}\ell_{21}...\ell_{2k_{2}}...2\ell_{h1}...\ell_{hi}^{\prime}...\ell_{hk_{h}}$.
Finally, we define $\rho(\pi)$ as the standard reduction of this sequence.
Again, it is clear by construction that $\rho(\pi)$ avoids $1-32-4$.

######  Example 5.1.

Let us illustrate the previous construction with two examples.

  * (i)

Take the permutation $\pi=(8,9,14,12,5,2,4,10,11,1,3,13,6,7)$ and let us
compute its reduction $\rho(\pi)$. Note that $\pi$ has type $(2,1)$, therefore
we first delete $1$ to obtain the sequence $(8,9,14,12,5,2,4,10,11,3,13,6,7)$,
then we sort the increasing sequences $(4,10,11)$, $(3,13)$ and $(6,7)$ on the
right of $2$ in such a way that their maximum elements $11,13$ and $7$ are in
decreasing order. Therefore the correct order is given by
$(3,13)(4,10,11)(6,7)$, which yields the sequence
$(8,9,14,12,5,2,3,13,4,10,11,6,7)$. Taking the standard reduction of this
sequence returns the permutation $\rho(\pi)=(7,8,13,11,4,1,2,12,3,9,10,5,6)$.

  * (ii)

Take the permutation $\pi=(8,9,14,12,5,3,4,10,11,1,6,13,2,7)$ and let us
compute its reduction $\rho(\pi)$. Note that $\pi$ has type $(1,2)$, hence we
first delete $1$ to obtain the sequence $(8,9,14,12,5,3,4,10,11,6,13,2,7)$,
then we move $2$ to the position previously occupied by $1$, so to obtain the
sequence $(8,9,14,12,5,3,4,10,11,2,6,13,7)$. Taking the standard reduction of
this sequence returns the permutation
$\rho(\pi)=(7,8,13,11,4,2,3,9,10,1,5,12,6)$.

This construction induces a reduction operator $\rho$ on $\mathcal{S}(1-32-4)$
and thus, as mentioned before, an ECO operator $\vartheta$ on
$\mathcal{S}(1-32-4)$. Now we want to show that $\vartheta$ can be described
by the succession rule $\Omega$ given by (3). For this purpose, we will
explicitly describe all the elements of $\vartheta(\pi)$ and compute their
labels by reversing the previous construction. More specifically, we will
expand $\pi$ by appending $0$ at the end of $\pi$, then moving some of the
increasing sequences $\ell_{h1},...,\ell_{hk_{h}}$ to the right of $0$ and
finally normalizing the sequence thus obtained (i.e. adding $1$ to each item
of the sequence). In fact, the range of possibilities to perform this
operation is quite constrained because we have to preserve the avoidance of
the pattern $1-32-4$. First append a $0$ at the end of $\pi$.

  * (i)

Of course, no occurrence of $1-32-4$ will appear if we move the whole sequence
$\ell_{h1}...\ell_{hk_{h}}$ to the right of $0$. In this way we get the
sequence $m_{1}\ell_{11}...\ell_{1k_{1}}...m_{h}0\ell_{h1}...\ell_{hk_{h}}$,
whose normalization is a permutation which we denote by $\pi^{(k)}$. Note that
$\ell(\pi^{(k)})=k$.

  * (ii)

Suppose instead that $k\geq 1$ and we want to move only $i\in\\{0,...,k-1\\}$
increasing sequences among $\ell_{h1},...,\ell_{hk_{h}}$ to the right of $0$.
Then it is easy to see that there is a unique way to perform this operation so
to prevent an occurrence of $1-32-4$ to appear in the resulting expansion of
$\pi$, which is the following way. Choose some $j\in[i+1]$ and move the
$(i+1)^{th}$ suffix $\ell_{h(k_{h}-i)},...,\ell_{hk_{h}}$ of the list
$\ell_{h1},...,\ell_{hk_{h}}$, except for its $j^{th}$ increasing sequence
$\ell_{h(k_{h}-i+j-1)}$, to the right of $0$. In other words, move the
sequence $\ell_{h(k_{h}-i)}...\hat{\ell}_{h(k_{h}-i+j-1)}...\ell_{hk_{h}}$
(where the hat over an item means that it must be omitted) to the right of
$0$, thus obtaining the sequence

$m_{1}\ell_{11}...\ell_{1k_{1}}...m_{h}\ell_{h1}...\ell_{h(k_{h}-i-1)}\ell_{h(k_{h}-i+j-1)}0\ell_{h(k_{h}-i)}...\hat{\ell}_{h(k_{h}-i+j-1)}...\ell_{hk_{h}}.$

Finally normalize this sequence to a permutation, which we denote by
$\pi^{(i,j)}$. Note that $\ell(\pi^{(i,j)})=i$. Hence, this operation produces
$i+1$ children with label $i$, for every $0\leq i\leq k-1$, from a node with
label $k$.

Note that all permutations defined in $(i)$ and $(ii)$ will have type $(2,1)$,
therefore these permutations cannot exhaust the whole class
$\mathcal{S}(1-32-4)$ and we need to construct other expansions of $\pi$ to
include also permutations of type $(1,2)$. To this purpose we also move
$m_{h}=1$ to the right of $0$ and perform some further transformations.

  * (iii)

Of course, no occurrence of $1-32-4$ will appear if we move the whole sequence
$1\ell_{h1}...\ell_{hk_{h}}$ to the right of $0$. In this way, we get the
sequence $m_{1}\ell_{11}...\ell_{1k_{1}}...01\ell_{h1}...\ell_{hk_{h}}$, whose
normalization is a permutation which we denote by $\pi^{[1]}$. More generally,
it is clear that no occurrence of $1-32-4$ will appear if we perform the
following operation. Choose some $i\in[k]$ and move $1$ immediately to the
left of $\ell_{hi}$, then move the sequence
$\ell_{h1}...1\ell_{hi}...\ell_{hk_{h}}$ to the right of $0$. In this way we
obtain the sequence
$m_{1}\ell_{11}...\ell_{1k_{1}}...0\ell_{h1}...1\ell_{hi}...\ell_{hk_{h}}$,
whose normalization is a permutation, which we denote by $\pi^{[i]}$. Note
that $\ell(\pi^{\prime})=k$. Hence, operation $(i)$ and $(iii)$ produce $k+1$
children with label $k$ from a node with label $k$.

  * (iv)

Finally, we have a last possibility to transform $\pi$ and prevent an
occurrence of $1-32-4$ to appear. Move $1$ back to the right of
$\ell_{hk_{h}}$, then move the sequence $\ell_{h1}...\ell_{hk_{h}}1$ to the
right of $0$. In this way we obtain the sequence
$m_{1}\ell_{11}...\ell_{1k_{1}}...0\ell_{h1}...\ell_{hk_{h}}1$ and normalize
it to a permutation, which we denote by $\pi^{[k+1]}$. Note that in this case,
unlike in the previous one, we have $\ell(\pi^{[k+1]})=k+1$. Hence, this
operation will produces a unique child with label $k+1$ from a node with label
$k$. Note that this last possibility could actually be regarded as a special
case of $(iii)$ if we let $\pi$ terminate with an additional empty increasing
sequence $\ell_{(h+1)k_{h+1}}$.

Note that all permutations defined in $(iii)$ and $(iv)$ have type $(1,2)$.

######  Example 5.2.

Let us take $\pi=({\bf{5}},9,14,10,12,{\bf{1}},2,7,13,6,11,3,8,4)$ as a
working example to illustrate some of the previous constructions. Note that in
this case $\pi$ has the form
$m_{1}\ell_{11}\ell_{12}m_{2}\ell_{21}\ell_{22}\ell_{23}\ell_{24}$ where
$m_{1}=5$, $\ell_{12}=(9,14)$ and $\ell_{12}=(10,12)$, while $m_{2}=1$,
$\ell_{21}=(2,7,13)$, $\ell_{22}=(6,11)$, $\ell_{23}=(3,8)$ and
$\ell_{24}=(4)$, in particular $\ell(\pi)=4$. First we insert a $0$ at the end
of $\pi$ to obtain the sequence $(5,9,14,10,12,1,2,7,13,6,11,3,8,4,0)$.

  * (i)

We start by constructing $\pi^{(4)}$. We move the sequence
$(2,7,13,6,11,3,8,4)$ to the right of $0$, thus obtaining the sequence
$(5,9,14,10,12,1,0,2,7,13,6,11,3,8,4)$, whose normalization is given by the
permutation $\pi^{(4)}=(6,10,15,11,13,2,1,3,8,14,7,12,4,9,5)$.

  * (ii)

Now let us construct the permutation $\pi^{(2,2)}$. We move the suffix
$(6,11)(3,8)(4)$ of the list $(2,7,13)(6,11)(3,8)(4)$, except for its $2^{nd}$
element $(3,8)$, to the right of $0$, thus obtaining the sequence
$(5,9,14,10,12,1,2,7,13,3,8,0,6,11,4)$, whose normalization is given by the
permutation $\pi^{(2,2)}=(6,10,15,11,13,2,3,8,14,4,9,1,7,12,5)$.

  * (iii)

Let us now construct the permutation $\pi^{[3]}$. We move the sequence
$(1,2,7,13,6,11,3,8,4)$ to the right of $0$ and move $1$ immediately to the
left of $(3,8)$, thus obtaining the sequence
$(5,9,14,10,12,0,2,7,13,6,11,1,3,8,4)$, whose normalization is given by the
permutation $\pi^{[3]}=(6,10,15,11,13,1,3,8,14,7,12,2,4,9,5)$.

  * (iv)

Finally we construct the permutation $\pi^{[4]}$. We move the sequence
$(1,2,7,13,6,11,3,8,4)$ to the right of $0$ and move $1$ immediately to the
right of $(4)$, thus obtaining the sequence
$(5,9,14,10,12,0,2,7,13,6,11,3,8,4,1)$, whose normalization is given by the
permutation $\pi^{[3]}=(6,10,15,11,13,,1,3,8,14,7,12,4,9,5,2)$.

Figure 4: The first 3 levels of the generating tree for permutations avoiding
the pattern $1-32-4$, where each node $\pi\in\mathcal{S}(1-32-4)$ is labeled
by $(\ell(\pi))$.

Now we are in a position to state and prove the main result.

######  Theorem 5.1.

Suppose $\pi\in\mathcal{S}(1-32-4)$ and $k=\ell(\pi)$.

  * (i)

If $k=0$, then $\vartheta(\pi)=\\{\pi^{(0)},\pi^{[1]}\\}$.

  * (ii)

If $k\geq 1$, then $\vartheta(\pi)=\\{\pi^{(k)},\pi^{(i,j)},\pi^{[p]}:\ 0\leq
i\leq k-1,1\leq j\leq i+1,1\leq p\leq k+1\\}$.

  * (iii)

The map $\ell$ is an $\Omega-$labelling of $\mathcal{T}_{\vartheta}$.

###### Proof.

It is mere routine to check that $\rho(\pi^{(0)})=\rho(\pi^{[1]})=\pi$ when
$k=0$ and that $\rho(\pi^{(k)})=\rho(\pi^{(i,j)})=\rho(\pi^{[p]})=\pi$ when
$k\geq 1$, $0\leq i\leq k-1,1\leq j\leq i+1$ and $1\leq p\leq k+1$.
Conversely, assume $\sigma\in\vartheta(\pi)$ and write $\sigma$ in the form
$m_{1}\ell_{11}...\ell_{1k_{1}}...m_{h}\ell_{h1}...\ell_{hk_{h}}$ as in
Equation $(\ref{structure})$. Suppose first that $\sigma$ has type $(2,1)$. If
$2$ and $1$ occur consecutively in $\pi$, then it is immediate to see that
$\sigma=\pi^{(k)}$. Otherwise, it is also fairly easy to check that
$\sigma=\pi^{(i,j)}$ where $i=\ell(\sigma)$, while $j=1$ in case
$\max(\ell_{h1})<\max(\ell_{(h-1)k_{h-1}})$ and
$j=\max\\{j\in\\{2,3,...,i+1\\}:\
\max(\ell_{h(j-1)})>\max(\ell_{(h-1)k_{h-1}})\\}$ otherwise. Suppose now
$\sigma$ has type $(1,2)$. Then it is also easy to check that
$\sigma=\pi^{[p]}$ where $p$ is the unique $p\in[k_{h}]$ such that $2$ occurs
in the increasing sequence $\ell_{hp}$. This proves $(i)$ and $(ii)$. Finally,
$(iii)$ holds because we know that $\ell(\pi^{(0)})=0$ and $\ell(\pi^{[1]})=1$
when $k=0$, while $\ell(\pi^{(i,j)})=i$, $\ell(\pi^{(k)})=\ell(\pi^{[p]})=k$
and $\ell(\pi^{[k+1]})=k+1$ when $k\geq 1$, $0\leq i\leq k-1,1\leq j\leq i+1$
and $1\leq p\leq k$. ∎

We observe once again that the construction above actually provides an
algorithm to generate all permutations avoiding $1-32-4$. The permutations
generated this way up to length $4$ are displayed in Figure 4. We end this
section with the following corollary summarizing the further byproduct of the
previous construction, which is the refined enumeration of permutations
avoiding $1-32-4$ according to the number of right-to-left maxima to the right
of 1.

######  Corollary 5.1.

For every $0\leq k\leq n-1$ denote by $v(n,k)$ the number of permutations
avoiding $1-32-4$ with length $n$ and $k$ right-to-left maxima to the right of
$1$. Then the triangle $v(n,k)$ satisfies the recurrence relation

$v(n,k)=v(n-1,k-1)+(k+1)\sum_{j=k}^{n-2}v(n-1,j)$

where we agree that $v(0,-1)=1$ and $v(n,-1)=0$ for every $n\geq 1$.

$n\backslash k$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---|---|---
1 | 1 |  |  |  |  |  |  |
2 | 1 | 1 |  |  |  |  |  |
3 | 2 | 3 | 1 |  |  |  |  |
4 | 6 | 10 | 6 | 1 |  |  |  |
5 | 23 | 40 | 31 | 10 | 1 |  |  |
6 | 105 | 187 | 166 | 75 | 15 | 1 |  |
7 | 549 | 993 | 958 | 530 | 155 | 21 | 1 |
8 | 3207 | 5865 | 5988 | 3786 | 1415 | 287 | 28 | 1
Table 1: The triangle $v(n,k)$ counting permutations avoiding $1-32-4$ with
length $n$ and $k$ right-to-left maxima to the right of $1$, for $1\leq n\leq
8$ and $0\leq k\leq n-1$.

##  6 Conclusion and further work

In this paper we finally succeded in describing a generating tree with single
label for permutations avoiding $1-32-4$. However, as pointed out in Section
5, the sequence counting these permutations also happens to count other
combinatorial structures, such as increasing ordered rooted trees with
increasinig leaves or valley marked Dyck paths, and describing a clear
bijection between these structures would have a great combinatorial
significance. Although a bijection was already established by Callan in [C]
through a sequence of non-trivial steps and despite the remarkable advances in
[DGR] to make more explicit the connection between these objects, we believe
it is worth looking for a bijection admitting a reasonably simpler
description. Using the generating tree described in this paper, it is likely
that one can recursively construct some other bijection, preserving the
respective labels, and we hope this could eventually lead to a significant
advance in this direction.

As for a more generic issue, we observe that permutations avoiding the
classical pattern $1324$ form a subclass of permutations avoiding the vincular
pattern $1-32-4$. Hence, it might be interesting to investigate in which cases
the ECO operator $\vartheta$ fails to expand a permutation avoiding the
classical pattern $1324$ to another permutation avoiding the same pattern,
causing an occurrence of $1324$ to appear.

Furthermore, we believe it is worth investigating whether the construction
provided in this paper to generate all permutations avoiding $1-32-4$ can be
adapted to generate all permutations avoiding the vincular pattern
$1-(\pi+1)-(|\pi|+2)$, for some particular consecutive patterns $\pi$ other
than $12$ or $21$ (where $\pi+1$ denotes the permutation obtained from $\pi$
by adding $1$ to each item of $\pi$). In this case there would be hope to find
a recurrence relation to count these permutations.

In general, the fast recurrence for permutations avoiding $1-32-4$ provided in
[C] suggests to look for nonobvious recurrences counting other similar
patterns. For instance, note that a kind of structural description for
permutations avoiding $12-34$ is given in [E], hence there may be hope to find
a nice generating tree and deduce some reasonable recurrence relation, just
like we did in the case of permutations avoiding $1-23-4$.

Finally, still concerning enumeration of permutations avoiding $1-32-4$,
although the recursive formula found by Callan provides quite an efficient and
elegant way to count them, a closed formula would clearly be a more
satisfactory answer. In this regard, the generating function $u(z)$ of
permutations avoiding $1-32-4$ can be recursively described as a continued
fraction $u(z)=1-z(U(0)-z)$ where $U(n)=1-z^{n}-z/U(n+1)$ for every
$n\in\mathbb{N}$ (see [S]). However, this description can hardly be considered
a closed formula. The succession rule describing permutations avoiding
$1-32-4$ can also be translated into a functional equation for the generating
function $u(z,t)$ of these permutations (where $z$ keeps track of the length
and $t$ keeps track of the label), as explained at the very end of Section 4.
This equation is actually a linear PDE of the form

$(1-t)zt^{2}\frac{\partial u}{\partial
t}(z,t)+((1-t)^{2}(1-zt)+zt)u(z,t)=zt(1-t)^{2}+ztu(z,1).$ (5)

However, we do not know whether Equation $(\ref{PDE})$ provides enough
information to find some closed form expression for $u(z,t)$. Further research
in this direction could improve our understanding of sequence A113227.

### Acknowledgement

The author whishes to thank Luca Ferrari for kindly reviewing some technical
details related to the construction illustrated in this paper and for his
valuable suggestions to improve the organization of its content.

## References

  * [B1] M. Bona.  _Combinatorics of Permutations_. Chapman $\&$ Hall/CRC, Boca Raton, FL, 2004.
  * [B2] M. Bona.  _Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps_. J. Combin. Theory Ser. A, 80(2):257–272, 1997\.
  * [BDLPP] E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani.  _ECO: a methodology for the enumeration of combinatorial objects_. J.Differ. Equations Appl.5(1999), no. 4-5, 435–490.
  * [BF] A. Bernini and L. Ferrari.  _Vincular pattern posets and the Möbius function of the quasiconsecutive pattern poset_. Ann. Combin. 21 (2017) 519-534.
  * [C] D.Callan.  _A bijection to count (1-23-4)-avoiding permutations_. Preprint, 2010. Available at http://arxiv.org/abs/1008.2375.
  * [Cl] A. Claesson.  _Generalized pattern avoidance_. European J. Combin., 22(7):961 – 971, 2001.
  * [CMSW] S. Corteel, M. A. Martinez, C. D. Savage, and M. Weselcouch.  _Patterns in inversion sequences I_. Discrete Math. Theor. Comput. Sci. 18 (2016).
  * [DGR] E. Duchi, V. Guerrini, S. Rinaldi.  _A generating tree for permutations avoiding the pattern $122^{+}3$_. Fundamenta Informaticae, vol 163, n. 1, 21-39, (2018).
  * [E] S. Elizalde.  _Asymptotic enumeration of permutations avoiding generalized patterns_. Adv. in Appl.Math., 36(2):138–155, 2006.
  * [EN] S. Elizalde and M. Noy.  _Consecutive patterns in permutations_. Adv. in Appl. Math., 30(1-2):110 – 125, 2003.
  * [FS] Flajolet R., Sedgewick R.  _Analytic Combinatorics_. Cambridge University Press, Cambridge (2009).
  * [Ki1] S. Kitaev.  _Patterns in Permutations and Words_. Monographs in Theoretical Computer Science. Springer, Heidelberg, 2011.
  * [Ki2] S. Kitaev.  _Partially ordered generalized patterns_. Discrete Math., 298(1-3):212 – 229, 2005.
  * [NZ] J. Noonan and D. Zeilberger.  _The enumeration of permutations with a prescribed number of forbidden patterns_. Adv. in Appl. Math., 17(4):381 – 407,1996.
  * [S] N. J. A. Sloane. _The On-line Encyclopedia of Integer Sequences_ , at oeis.org.
  * [St1] R. P. Stanley.  _Enumerative combinatorics. Vol. I_. The Wadsworth $\&$ Brooks/Cole Mathematics Series.Wadsworth $\&$ Brooks/Cole Advanced Books $\&$ Software, Monterey, 1986. With a foreword by Gian-Carlo Rota.
  * [St2] R. P. Stanley.  _Enumerative combinatorics. Vol. II_ , volume 62 of _Cambridge Studies in Advanced Mathematics_. Cambridge University Press, Cambridge, 1999\. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
  * [Ste] E. Steingrímsson.  _Generalized permutation patterns – a short survey_. Permutation Patterns, vol. 376 of London Math. Soc. Lecture Note Series, pages 137 – 152, Cambridge University Press, Cambridge, 2010.


# The Baker-Schmidt problem for dual approximation and some classes of
functions

Mumtaz Hussain  Mumtaz Hussain, Department of Mathematical and Physical
Sciences, La Trobe University, Bendigo 3552, Australia.
<EMAIL_ADDRESS>and  Johannes Schleischitz  Middle East Technical
University, Northern Cyprus Campus, Kalkanli, Güzelyurt<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The Generalised Baker-Schmidt Problem (1970) concerns the Hausdorff
$f$-measure of the set of $\Psi$-approximable points on a nondegenerate
manifold. We refine and extend our previous work [Int. Math. Res. Not. IMRN
2021, no. 12, 8845–8867] in which we settled the problem (for dual
approximation) for hypersurfaces. We verify the GBSP for certain classes of
nondegenerate submanifolds of codimension greater than $1$. Concretely, for
codimension two or three, we provide examples of manifolds where the dependent
variables can be chosen as quadratic forms. Our method requires the manifold
to have even dimension at least the minimum of four and half the dimension of
the ambient space. We conjecture that these restrictions on the dimension of
the manifold are sufficient to provide similar examples in general.

##  1\. Dual Diophantine approximation on manifolds

Let $n\geq 1$ be a fixed integer,
$\mathbf{q}:=(q_{1},\ldots,q_{n})\in\mathbb{Z}^{n}$, and
$\mathbf{x}=(x_{1},\dots,x_{n})\in\mathbb{R}^{n}$. Let
$\Psi:\mathbb{Z}^{n}\to[0,\infty)$ be a _multivariable approximating function_
, that is, $\Psi$ has the property that $\Psi(\mathbf{q})\rightarrow~{}0\text{
as }\|\mathbf{q}\|:=\max(|q_{1}|,\ldots,|q_{n}|)\rightarrow~{}\infty.$ Let
$\theta$ be an arbitrary real number111 We remark that, in fact, our results
still apply for any sufficiently smooth function $\theta(\mathbf{x})$, as in
[9], see Remark 1 below.. Consider the set

$\mathcal{D}_{n}^{\theta}(\Psi):=\left\\{\mathbf{x}\in\mathbb{R}^{n}:\begin{array}[]{l}|\mathbf{q}\cdot\mathbf{x}+p+\theta|<\Psi(\mathbf{q})\
\text{for}\ {\rm i.m.}\
(p,\mathbf{q})\in\mathbb{Z}\times\mathbb{Z}^{n}\end{array}\right\\},$

where ‘i.m.’ stands for ‘infinitely many’. A vector
$\mathbf{x}\in\mathbb{R}^{n}$ will be called _$(\Psi,\theta)$ -approximable_
if it lies in the set $\mathcal{D}_{n}^{\theta}(\Psi)$. When $\theta=0$, the
problem reduces to the _homogeneous_ setting. We are interested in the ‘size’
of the set $\mathcal{D}_{n}^{\theta}(\Psi)$ with respect to the
$f$-dimensional Hausdorff measure $\mathcal{H}^{f}$ for some dimension
function $f$. By a dimension function $f$ we mean an increasing continuous
function $f:\mathbb{R}\to\mathbb{R}$ with $f(0)=0$.

Diophantine approximation on manifolds concerns the study of approximation
properties of points in $\mathbb{R}^{n}$ which are functionally related or in
other words restricted to a submanifold $\mathcal{M}$ of $\mathbb{R}^{n}$. To
estimate the size of sets of points $\mathbf{x}\in\mathbb{R}^{n}$ which lie on
a $k$-dimensional, nondegenerate222In this context ‘nondegenerate’ means
suitably curved, see [4, 11] for precise formulations, analytic submanifold
$\mathcal{M}\subseteq\mathbb{R}^{n}$ is an intricate and challenging problem.
The fundamental aim is to estimate the size of the set
$\mathcal{M}\cap\mathcal{D}_{n}^{\theta}(\Psi)$ in terms of Lebesgue measure,
Hausdorff measure, and Hausdorff dimension. When asking such questions it is
natural to phrase them in terms of a suitable measure supported on the
manifold, since when $k<n$ the $n$-dimensional Lebesgue measure is zero
irrespective of the approximating functions. For this reason, results in the
dependent Lebesgue theory (for example, Khintchine-Groshev type theorems for
manifolds) are posed in terms of the $k$-dimensional Lebesgue measure
(equivalent to the Hausdorff measure) on $\mathcal{M}$.

In full generality, a complete Hausdorff measure treatment for manifolds
$\mathcal{M}$ represents a deep open problem referred to as the Generalised
Baker-Schmidt Problem (GBSP) inspired by the pioneering work of Baker and
Schmidt [3]. There are two variants of this problem, concerning simultaneous
and dual approximation. In this paper we are concerned with the dual
approximation only. Ideally one would want to solve the following problem in
full generality.

######  Generalised Baker-Schmidt Problem for Hausdorff Measure: dual setting.

Let $\mathcal{M}$ be a nondegenerate submanifold of $\mathbb{R}^{n}$ with
$\dim\mathcal{M}=k$ and $n\geq 2$. Let $\Psi$ be a multivariable approximating
function. Let $f$ be a dimension function such that $r^{-k}f(r)\to\infty$ as
$r\to 0.$ Assume that $r\mapsto r^{-k}f(r)$ is decreasing and $r\mapsto
r^{1-k}f(r)$ is increasing. Prove that

$\mathcal{H}^{f}(\mathcal{D}_{n}^{\theta}(\Psi)\cap\mathcal{M})=\left\\{\begin{array}[]{cl}0&{\rm
if}\quad\sum\limits_{\mathbf{q}\in\mathbb{Z}^{n}\setminus\\{\mathbf{0}\\}}\|\mathbf{q}\|^{k}\Psi(\mathbf{q})^{1-k}f\left(\frac{\Psi(\mathbf{q})}{\|\mathbf{q}\|}\right)<\infty;\\\\[12.91663pt]
\infty&{\rm
if}\quad\sum\limits_{\mathbf{q}\in\mathbb{Z}^{n}\setminus\\{\mathbf{0}\\}}\|\mathbf{q}\|^{k}\Psi(\mathbf{q})^{1-k}f\left(\frac{\Psi(\mathbf{q})}{\|\mathbf{q}\|}\right)=\infty.\end{array}\right.$

Note that $\mathcal{H}^{f}$ is proportional to the standard Lebesgue measure
when $f(r)=r^{n}$. In fact, the GBSP is stated in the most idealistic format
and solving it in this form is extremely challenging. The main difficulties
lie in the convergence case and therein constructing a suitable nice cover for
the set $\mathcal{D}_{n}^{\theta}(\Psi)\cap\mathcal{M}$. Recently (2021), the
authors with David Simmons settled the GBSP for hypersurfaces for both
homogeneous and inhomogeneous settings with non-monotonic multivariable
approximating functions [9]. We also proved several results for the one-
dimensional manifolds such as nondegenerate planar curves or for Veronese
curves in [10] under some regularity conditions on the dimension function. In
this paper we refine our framework set out in [9] and extend those results to
certain classes of nondegenerate manifolds of higher codimension.

We refer the reader to [9, Subsection 1.1] for a description of historical
progression towards the GBSP. Specifically, we refer the reader to [2, 3, 6,
7, 8, 10, 11]. For the recent developments of the GBSP for the simultaneous
approximation, we refer the reader to [9, Remark 1.1] or [6].

###  1.1. Setup and main result

We first state some regularity conditions on the manifold $\mathcal{M}$ and
the dimension function $f$. Let $n\geq 2$ be an integer and $\mathcal{M}$ be a
manifold of codimension $l\geq 1$ in $\mathbb{R}^{n}$. Assume more precisely
that $\mathcal{M}$ is a surface of a $C^{2}$-map $g:U\to\mathbb{R}^{l}$, where
$U\subset\mathbb{R}^{n-l}$ is a connected bounded open set. We denote this as
$\mathcal{M}=\Gamma(g)$. By default we will assume that vectors are line
vectors, and use superscript $t$ for their transpose. Let $\mathcal{M}$ be
parametrised by

$\mathcal{M}=\\{(x_{1},\ldots,x_{n-l},g_{1}(\mathbf{x}),\ldots,g_{l}(\mathbf{x})):\;\mathbf{x}=(x_{1},\ldots,x_{n-l})\in
U\subseteq\mathbb{R}^{n-l}\\}.$ (1)

Our conditions read as follows:

  * (I)

Let $f$ be a dimension function satisfying

$f(xy)\lesssim x^{s}f(y),\qquad\text{ for all }y<1<x$ (2)

for some $s<2(n-l-1)$.

  * (II)

The real symmetric $(n-l)\times(n-l)$ matrix
$\Lambda=\Lambda(g,\boldsymbol{s},\mathbf{x})$ with entries

$\Lambda_{j,i}=\sum_{u=1}^{l}s_{u}\cdot\frac{\partial^{2}g_{u}}{\partial
x_{i}\partial x_{j}}(\mathbf{x}),\qquad 1\leq i,j\leq n-l,$

for $g$ as above is regular for any choice of real
$\boldsymbol{s}=(s_{1},s_{2},\ldots,s_{l})\neq\mathbf{0}$ and all
$\mathbf{x}\in U\setminus S_{\mathcal{M}}$ outside a set $S_{\mathcal{M}}$ of
$f$-measure $0$.

While (II) turns out to be rather complicated, we point out that (I) holds as
soon as the manifold has dimension at least three, as in [9]. Section 2 of
this paper is reserved for a more detailed discussion on the conditions,
followed by examples of manifolds satisfying the hypotheses in Section 3. Our
new criterion for the convergence part of the GBSP, proved in Section 4, reads
as follows.

######  Theorem 1.1.

Let $\Psi$ be a multivariable approximating function. Let $f$ be a dimension
function satisfying (I) and let $g:\mathbb{R}^{n-l}\to\mathbb{R}^{l}$ be a
$C^{2}$-function satisfying (II). Then if $\mathcal{M}$ is given via $g$ by
(1), then

$\mathcal{H}^{f}(\mathcal{D}_{n}^{\theta}(\Psi)\cap\mathcal{M})=0$

if the series

$\sum\limits_{\mathbf{q}\in\mathbb{Z}^{n}\setminus\\{\mathbf{0}\\}}\|\mathbf{q}\|^{n-l}\Psi(\mathbf{q})^{l+1-n}f\left(\frac{\Psi(\mathbf{q})}{\|\mathbf{q}\|}\right)$

converges.

######  Remark 1.

It is possible to formulate a variant of Theorem 1.1 with a functional smooth
inhomogenity $\theta(\mathbf{x})$ as in [9].

###  1.2. Corollaries (from a combination with the divergence results)

In this section, we detail some of the corollaries of our theorem along with
some of the consequences. We begin by summarising the notation used.

Notation. In the case where the dimension function is of the form
$f(r):=r^{s}$ for some $s<k$, $\mathcal{H}^{f}$ is simply denoted as
$\mathcal{H}^{s}$. On occasions we will consider functions of the form
$\Psi(\mathbf{q})=\psi(\|\mathbf{q}\|)$, and in this case we use
$W_{n}^{\theta}(\psi)$ as a shorthand for $W_{n}^{\theta}(\Psi)$. The function
$\psi:\mathbb{R}_{>0}\to\mathbb{R}_{>0}$ is called a _single-variable
approximating function_. $B_{n}(\mathbf{x},r)$ denotes a ball centred at the
point $\mathbf{x}\in\mathbb{R}^{n}$ of radius $r$. For real quantities $A,B$
and a parameter $t$, we write $A\lesssim_{t}B$ if $A\leq c(t)B$ for a constant
$c(t)>0$ that depends on $t$ only (while $A$ and $B$ may depend on other
parameters). We write $A\asymp_{t}B$ if $A\lesssim_{t}B\lesssim_{t}A$. If the
constant $c>0$ depends only on parameters that are constant throughout a
proof, we simply write $A\lesssim B$ and $B\asymp A$.

The divergence part of the GBSP was proved by Badziahin-Beresnevich-Velani [1]
for the $s$-dimensional Hausdorff measure333It is to be noted that the
techniques used in proving [1, Theorem 2] also work for the $f$-dimensional
Hausdorff measure situation.  and for multivariable approximating functions
satisfying a certain property $\mathbf{P}$ for any nondegenerate manifolds.
Following the terminology of [1], we say that an approximating function $\Psi$
satisfies property $\mathbf{P}$ if it is of the form
$\Psi(\mathbf{q})=\psi(\|\mathbf{q}\|_{\mathbf{v}})$ for a monotonically
decreasing function $\psi:\mathbb{R}_{>0}\to\mathbb{R}_{>0}$ (single-variable
approximation function), $\mathbf{v}=(v_{1},\ldots,v_{n})$ with $v_{i}>0$ and
$\sum_{1\leq i\leq n}v_{i}=n$, and $\|\cdot\|_{\mathbf{v}}$ defined as the
quasi-norm $\|\mathbf{q}\|_{\mathbf{v}}=\max_{i}|q_{i}|^{1/v_{i}}$. When
combined with Theorem 1.1 we obtain the following implication on the GBSP
problem for nondegenerate (see [1]) manifolds for dimensions not less than
$3$.

######  Corollary 1.2.

Let $\Psi$ be a decreasing multivariable approximating function satisfying
property $\mathbf{P}$. Let $f$ be a dimension function satisfying (I) and let
$g$ be a $C^{2}$-function satisfying (II). Let $\mathcal{M}$ be a
nondegenerate manifold in $\mathbb{R}^{n}$ of dimension $n-l$, given via $g$
by (1). Then

$\mathcal{H}^{f}(\mathcal{D}_{n}^{\theta}(\Psi)\cap\mathcal{M})=\begin{cases}0&{\rm
if}\quad\sum\limits_{\mathbf{q}\in\mathbb{Z}^{n}\setminus\\{\mathbf{0}\\}}\|\mathbf{q}\|^{n-l}\Psi(\mathbf{q})^{l+1-n}f\left(\frac{\Psi(\mathbf{q})}{\|\mathbf{q}\|}\right)<\infty;\\\\[12.91663pt]
\infty&{\rm
if}\quad\sum\limits_{\mathbf{q}\in\mathbb{Z}^{n}\setminus\\{\mathbf{0}\\}}\|\mathbf{q}\|^{n-l}\Psi(\mathbf{q})^{l+1-n}f\left(\frac{\Psi(\mathbf{q})}{\|\mathbf{q}\|}\right)=\infty.\end{cases}$

We emphasise again that only the divergence case, treated in [1], assumes
monotonicity on the approximating function $\Psi$.

######  Corollary 1.3.

Let $\mathcal{M}$ and $\Psi$ be as in Corollary 1.2 and let $s$ be a real
number satisfying $s<2(n-l-1)$. Then

$\mathcal{H}^{s}(\mathcal{D}_{n}^{\theta}(\Psi)\cap\mathcal{M})=\begin{cases}0&{\rm
if}\quad\sum\limits_{\mathbf{q}\in\mathbb{Z}^{n}\setminus\\{\mathbf{0}\\}}\|\mathbf{q}\|\left(\frac{\Psi(\mathbf{q})}{\|\mathbf{q}\|}\right)^{s+l+1-n}<\infty;\\\\[12.91663pt]
\infty&{\rm
if}\quad\sum\limits_{\mathbf{q}\in\mathbb{Z}^{n}\setminus\\{\mathbf{0}\\}}\|\mathbf{q}\|\left(\frac{\Psi(\mathbf{q})}{\|\mathbf{q}\|}\right)^{s+l+1-n}=\infty,\end{cases}.$

For $l=1,n=2$ where $\mathcal{M}$ is a planar curve, while the corollary and
its proof are formally valid, the involved parameter range for $s$ is empty.
We refer the reader to [10] for the GBSP type results on nondegenerate curves
such as Veronese curves, i.e. sets of the form
$\\{(x,x^{2},\ldots,x^{n}):x\in\mathbb{R}\\}$. We remark that in view of
Corollary 1.3, Conjecture 1 below would imply the GBSP for a large class of
manifolds and any $\Psi$ with property $\mathbf{P}$.

One of the consequences of Corollary 1.3 is the following Hausdorff dimension
result. Let $\tau_{\Psi}$ be the lower order at infinity of $1/\Psi$, that is,

$\tau_{\Psi}:=\liminf_{t\to\infty}\frac{\log(1/\Psi(t))}{\log t},\ \
\text{where}\ \ \Psi(t)=\inf_{\mathbf{x}\in\mathbb{R}^{n}:\|\mathbf{x}\|\leq
t}\Psi(\mathbf{x}),$

and we may assume $\tau_{\Psi}\geq n>0$. Then from the definition of Hausdorff
measure, Theorem 1.1 implies that for any approximating function $\Psi$ with
lower order at infinity $\tau_{\Psi}$ and for $\mathcal{M}$ as above (that is,
with property (II)) of dimension $\dim\mathcal{M}\geq 3$, we have

$\dim_{\mathcal{H}}(W_{n}^{\theta}(\Psi)\cap\mathcal{M})\leq\dim\mathcal{M}-1+\frac{n+1}{\tau_{\Psi}+1}.$

This Hausdorff dimension result was previously only known for either the
planar curve [2, 8, 6], Veronese curve [5], or for the hypersurface [9].

Acknowledgments. The research of Mumtaz Hussain is supported by the Australian
Research Council Discovery Project (200100994).

##  2\. On conditions (I) and (II)

###  2.1. On Condition (I)

Note that in the statement of the GBSP, the standard condition on the
dimension function $f$ that $f(q)q^{-(n-l)}$ (recall $n-l=\dim\mathcal{M}$) is
decreasing is assumed. With this condition in hand, the condition (I) is
satisfied as soon as

$n-l\geq 3.$

From the aforementioned decay property we see that $f(xy)\leq x^{n-l}f(y)$ for
$y<1<x$. Since $n-l<2(n-l-1)$ as soon as $n-l\geq 3$, indeed we infer that (2)
holds in the non-empty parameter range $s\in[n-l,2(n-l-1))$. On the other
hand, condition (I) excludes all curves (one dimensional manifolds), as well
as all two dimensional manifolds, for many interesting functions $f$.

###  2.2. On Condition (II)

Condition (II) is more delicate. It replaces and generalises the non-vanishing
of the determinant of the Hessian
$\nabla^{2}g\in\mathbb{R}^{(n-1)\times(n-1)}$ condition within $U$ from [9]
when $l=1$. Fixing $\mathbf{x}\in U$, the determinant of $\Lambda$ in (II)
becomes a multivariate, homogeneous polynomial $P$ of total degree $n-l$ in
the variables $s_{1},\ldots,s_{l}$. Its coefficients are functions in the
$\ell\cdot\binom{n-l+1}{2}$ second order partial derivatives of $g$ (using
symmetry of $\Lambda$), evaluated at $\mathbf{x}\in U$. In other words, for
(II) we need that some form of degree $n-l$ in $l$ variables is positive (or
negative) definite at any point in $U$. This definiteness problem of forms
seems related to Hilbert’s XVII-th problem, whose positive answer in
particular implies that $P$ above must have a presentation as a sum of
squares. It is evident that the complexity of the problem increases fast as
$l$ and $n$ grow.

A priori, it is not clear if, generally, $g$ satisfying hypothesis (II) exists
when $l\geq 2$. However, for certain pairs $(l,n)$ we provide examples below.
It is evident from the form of $\Lambda$ that, provided that examples exists
at all, we can choose the coordinate functions $g_{j}$ as quadratic forms,
defined on the entire space $U=\mathbb{R}^{n-l}$. Moreover, we can perturb any
such example by adding any functions with small enough second order
derivatives by absolute value uniformly on $\mathbb{R}^{n-l}$ to the $g_{j}$.
For simplicity of presentation, we introduce the following notion.

######  Definition 2.1.

Call a pair of integers $(l,n)$ with $n>l\geq 1$ a good pair if (II) holds for
some $g:\mathbb{R}^{n-l}\to\mathbb{R}^{l}$ as in the introduction.

By the above observation, the induced $g$ of any good pair can be taken a
quadratic form defined globally. It is obvious that any pair $(1,n)$ is good.
For larger $l$, the following general going-up and going-down properties for
good pairs are straightforward.

######  Proposition 2.2.

If $(l,n)$ is a good pair, then so is

  * (i)

the pair $(l-t,n-t)$ for any integer $0\leq t\leq l-1$.

  * (ii)

the pair $(l,\tilde{n})$ with $\tilde{n}=n+t(n-l)$ for any integer $t\geq 0$.

Claim (i) can be seen by specialisation of $t$ variables, for example via
putting $s_{1}~{}=~{}\cdots=~{}s_{t+1}$. The proof of (ii) will become
apparent from the examples in Section 3. On the other hand, it is in general
unclear if $(l,n)$ being a good pair will imply the same for $(l,\tilde{n})$
with a general larger $\tilde{n}>n$, even if $\tilde{n}-l$ is even (see
Obstruction 1 below).

On the other hand, condition (II) has some natural limitations, as captured in
the following obstructions.

Obstruction 1: If $l\geq 2$ and $n-l$ is odd, then $(l,n)$ is not a good pair,
that is, the condition (II) cannot hold.

While a short proof seems to follow directly from the positive answer to
Hilbert’s XVII’th problem, we want to explicitly explain how this special case
can be handled. First assume $l=2$. Indeed, if either the coefficient of
$x_{1}^{n-l}$ or $x_{2}^{n-l}$ of the polynomial $P(x_{1},x_{2})$ defined
above vanishes, then we may take $x_{1}$ arbitrary and $x_{2}=0$ or vice
versa, hence we get non-trivial solutions for $\det\Lambda=P(x_{1},x_{2})=0$.
If otherwise both coefficients are not $0$, then by choosing any $x_{2}\neq 0$
we get a single-variable polynomial in $x_{1}$ of odd degree with non-zero
constant term, again inducing a non-trivial solution for
$\det\Lambda=P(x_{1},x_{2})=0$. Finally if $l>2$, by specialising $l-2$
variables $x_{3}=\cdots=x_{l}=0$, we get a polynomial $Q(x_{1},x_{2})$ in two
variables. Regardless if $Q\equiv 0$ is the constant $0$ polynomial or not, by
the observations for $l=2$ above, we may choose at least one of $x_{1},x_{2}$
(almost) arbitrary for a solution of $\det\Lambda=0$. Thus we again find a
non-trivial solution for $\det\Lambda=0$ in $s_{1},\ldots,s_{l}$.

Obstruction 2: We require $n\geq 2l$ for $(l,n)$ being a good pair.

Otherwise if $n-l<l$ then we can annihilate a line of $\Lambda$ on a linear
subspace of dimension at least $1$ of $\boldsymbol{s}\in\mathbb{R}^{l}$
obtained from intersecting $n-l$ hyperplanes of $\mathbb{R}^{l}$, regardless
of the choice of $g,\mathbf{x}$.

Obstruction 2 means that the manifold must have at least half the dimension of
the ambient space. We believe that these are the only obstructions. In view of
Theorem 1.1 and the observations in Section 2.1 we therefore go on to state
the following conjecture.

######  Conjecture 1.

The following claims hold

  * (i)

If $l\geq 2$ and $n\geq 2l$ and $n-l$ is even, then $(l,n)$ is a good pair.

  * (ii)

If $l\geq 2$ and $n\geq 2l$ and $n-l\geq 4$ is even, then there exists $g$
with coordinate functions $g_{j}$ quadratic forms such that (I), (II) holds on
$\mathbb{R}^{n-l}$, hence the convergence part of the GBSP holds for the
induced manifolds.

Clearly it would suffice to verify (i), claim (ii) is just stated for
completeness. We will verify the conjecture for $l=2$ in Section 3. Moreover,
for $l=3$ we establish the partial result that $n-l$ being a positive multiple
of $4$ is sufficient. The simplest cases where Conjecture 1 remains open are
$l=3,n=9$ and $l=4,n=8$.

##  3\. Examples

###  3.1. Special case $l=2$

We start with an example to illustrate condition (II) in the case $n=4,l=2$.
Unfortunately, since $\dim\mathcal{M}=2$, condition (I) does not hold in this
context, see Section 2.1.

######  Example 3.1.

Let $l=2$, $n=4$, so that $\mathcal{M}$ is a two-dimensional manifold with
codimension two. Using multilinearity of the determinant and after some
calculations, we see that the polynomial representing $\det\Lambda$ becomes

$P(s_{1},s_{2})=s_{1}^{2}A_{1}(g,\mathbf{x})+s_{2}^{2}A_{2}(g,\mathbf{x})+s_{1}s_{2}A_{3}(g,\mathbf{x})$

where

$A_{1}(g,\mathbf{x})=\frac{\partial^{2}g_{1}}{\partial^{2}x_{1}}(\mathbf{x})\cdot\frac{\partial^{2}g_{1}}{\partial^{2}x_{2}}(\mathbf{x})-(\frac{\partial^{2}g_{1}}{\partial
x_{1}\partial x_{2}}(\mathbf{x}))^{2},$
$A_{2}(g,\mathbf{x})=\frac{\partial^{2}g_{2}}{\partial^{2}x_{1}}(\mathbf{x})\cdot\frac{\partial^{2}g_{2}}{\partial^{2}x_{2}}(\mathbf{x})-(\frac{\partial^{2}g_{2}}{\partial
x_{1}\partial x_{2}}(\mathbf{x}))^{2},$

and

$A_{3}(g,\mathbf{x})=\frac{\partial^{2}g_{1}}{\partial^{2}x_{1}}(\mathbf{x})\cdot\frac{\partial^{2}g_{2}}{\partial^{2}x_{2}}(\mathbf{x})-2\frac{\partial^{2}g_{1}}{\partial
x_{1}\partial x_{2}}(\mathbf{x})\cdot\frac{\partial^{2}g_{2}}{\partial
x_{1}\partial
x_{2}}(\mathbf{x})+\frac{\partial^{2}g_{2}}{\partial^{2}x_{1}}(\mathbf{x})\cdot\frac{\partial^{2}g_{1}}{\partial^{2}x_{2}}(\mathbf{x}).$

By the criterion of minors to test definiteness of a quadratic form with
respect to the corresponding symmetric matrix with rows
$(A_{1}(g,\mathbf{x}),A_{3}(g,\mathbf{x})/2)$ and
$(A_{3}(g,\mathbf{x})/2,A_{2}(g,\mathbf{x}))$, then the criterion of condition
(II) that $P$ is positive (or negative) definite becomes

$A_{3}(g,\mathbf{x})^{2}<4A_{1}(g,\mathbf{x})A_{2}(g,\mathbf{x}).$ (3)

A sufficient criterion for second order derivatives is given by

$\frac{\partial^{2}g_{1}}{\partial^{2}x_{1}}(\mathbf{x})\cdot\frac{\partial^{2}g_{1}}{\partial^{2}x_{2}}(\mathbf{x})=\frac{\partial^{2}g_{2}}{\partial^{2}x_{1}}(\mathbf{x})\cdot\frac{\partial^{2}g_{2}}{\partial^{2}x_{2}}(\mathbf{x})<0,\qquad\frac{\partial^{2}g_{1}}{\partial
x_{1}\partial x_{2}}(\mathbf{x})\neq\frac{\partial^{2}g_{2}}{\partial
x_{1}\partial x_{2}}(\mathbf{x})$

as then we may write inequality (3) equivalently as

$4\frac{\partial^{2}g_{2}}{\partial^{2}x_{1}}(\mathbf{x})\cdot\frac{\partial^{2}g_{2}}{\partial^{2}x_{2}}(\mathbf{x})\cdot\left(\frac{\partial^{2}g_{1}}{\partial
x_{1}\partial x_{2}}(\mathbf{x})-\frac{\partial^{2}g_{2}}{\partial
x_{1}\partial x_{2}}(\mathbf{x})\right)^{2}<0.$

Specialising further, if for example, we can take at some $\mathbf{x}\in U$
the derivates

$\displaystyle\frac{\partial^{2}g_{1}}{\partial^{2}x_{1}}(\mathbf{x})=\frac{\partial^{2}g_{2}}{\partial^{2}x_{1}}(\mathbf{x})=2,$
$\displaystyle\frac{\partial^{2}g_{1}}{\partial^{2}x_{2}}(\mathbf{x})=\frac{\partial^{2}g_{2}}{\partial^{2}x_{2}}(\mathbf{x})=-2,$
$\displaystyle\frac{\partial^{2}g_{1}}{\partial x_{1}\partial
x_{2}}(\mathbf{x})\neq\frac{\partial^{2}g_{2}}{\partial x_{1}\partial
x_{2}}(\mathbf{x}),$

then it will be true in some neighbourhood of $\mathbf{x}$. For example when
$n=4,l=2$ and $\delta\neq 0$, then

$g(\mathbf{x})=g(x,y)=(x^{2}-y^{2}+\delta xy,x^{2}-y^{2})$

satisfies this for all $(x,y)$ in $\mathbb{R}^{2}$. The arising parametrised
manifolds becomes

$\mathcal{M}_{\delta}=\\{(x,y,x^{2}-y^{2}+\delta
xy,x^{2}-y^{2}):x,y\in\mathbb{R}\\},\ {\rm where}\ \delta\neq 0.$ (4)

We remark that $\delta\neq 0$ is necessary for the convergence part of GBSP as
otherwise the manifold lies in the rational subspace of $\mathbb{R}^{4}$
defined by $x_{3}=x_{4}$.

We now present some examples satisfying both (I) and (II). Keeping $l=2$, we
can extend the previous example to general even $n\geq 6$ by essentially
building Cartesian products. A possible class of manifolds derived from this
method that verifies Conjecture 1 for $l=2$ is captured in the following
example.

######  Example 3.2.

Let $l=2,n-l=2t$ for $t\geq 2$. Then for any $\delta_{1},\ldots,\delta_{t}\neq
0$ the manifold

$\mathcal{M}=\left\\{\left(x_{1},y_{1},\ldots,x_{t},y_{t},\sum_{u=1}^{t}x_{u}^{2}-y_{u}^{2}+\delta_{u}x_{u}y_{u},\sum_{u=1}^{t}x_{u}^{2}-y_{u}^{2}\right):\;\;x_{i},y_{i}\in\mathbb{R}\right\\},$

satisfies (I) and (II). Hence the GBSP holds for any decreasing $\Psi$ with
property $\mathbf{P}$.

Indeed, the critical determinant $\det(\Lambda)$ in Example 3.2 decomposes as
a product of $t$ determinants as in Example 3.1, which we found all to be non-
zero, so (II) holds. Since $n-l\geq 4$ condition (I) holds too. Clearly
Example 3.2 can be generalised in terms of parameter ranges for the
coefficients of the quadratic forms. By Obstruction 1, the condition that
$n-l$ is even is necessary for (II) (unless $n-l=1$, the hypersurface case). A
similar argument proves Proposition 2.2.

###  3.2. The case $l>2$

Now let us consider $l>2$. Together with the restrictions

$n-l\equiv 0\bmod 2,\qquad n-l\geq 3,\qquad n\geq 2l,$

from Section 2.1 and Obstructions 1 and 2, the easiest example is $l=3,n=7$.

The following general criterion for (II), or good pairs, involving “definite
determinants” essentially comes from specialising certain variables (second
order derivatives of $g$).

######  Lemma 3.3.

Let $n>l\geq 1$ be integers. Assume there exists a symmetric
$(n-l)\times(n-l)$ matrix $M_{l,n}$ with the entries

$M_{l,n}(i,j)\in\\{0,\pm z_{1},\ldots,\pm z_{l}\\},\qquad 1\leq i,j\leq n-l,$

for formal variables $z_{v}$, $1\leq v\leq l$, so that $\det M_{l,n}\neq 0$
for any choice of real $z_{v}$ not all $0$. Then $(l,n)$ is a good pair.

Hence the existence of $M_{l,n}$ as in the lemma implies that there exist
$(n-l)$-dimensional submanifolds of $\mathbb{R}^{n}$, defined as in (1) via
$g=(g_{1},\ldots,g_{l})$ with $g_{j}(\mathbf{x})$ real quadratic forms, that
satisfy (II) on $U=\mathbb{R}^{n-l}$. Again, the hypothesis of Lemma 3.3
forces $n\geq 2l$ and $n-l$ to be even.

######  Remark 2.

More generally, instead of $M_{l,n}(i,j)=\pm z_{v}$ or $0$, we may take the
matrix entries arbitrary linear combinations of the $z_{v}$, for the same
conclusion. This generalised condition is in fact equivalent to (II). The
proof is essentially the same as below.

###### Proof of Lemma 3.3.

Choose any set of $l$ linearly independent (over $\mathbb{R}$) vectors
$L_{v}=(a_{1,v},\ldots,a_{l,v})$, $1\leq v\leq l$, in $\mathbb{R}^{l}$ and
define the linear forms in $l$ variables $s_{1},\ldots,s_{l}$

$L_{v}\cdot\boldsymbol{s}=a_{1,v}s_{1}+\cdots+a_{l,v}s_{l},\quad 1\leq v\leq
l.$

Given $M_{l,n}$ as in the lemma, we construct a matrix $M_{l,n}^{\prime}$ with
entries in formal variables $s_{1},\ldots,s_{l}$ as follows: We identify
$z_{v}$ with $L_{v}\cdot\boldsymbol{s}$, that is, if for a pair $(i,j)$ the
index $v=v(i,j)$ is so that $M_{l,n}(i,j)=\pm z_{v}$, then we choose the entry
at position $(i,j)$ of $M_{l,n}^{\prime}$ equal to
$M_{l,n}^{\prime}(i,j)=L_{v}\cdot\boldsymbol{s}$. Else if $M_{l,n}(i,j)=0$
then keep the value $M_{l,n}^{\prime}(i,j)=0$. Then $M_{l,n}^{\prime}$ is
well-defined and depends on $s_{1},\ldots,s_{l}$. By linear independence of
the $L_{v}$ and the hypothesis of the lemma, for any non-trivial choice of
real numbers $s_{1},\ldots,s_{l}$, the matrix $M_{l,n}^{\prime}$ has non-zero
determinant. We finally notice that there is a one-to-one correspondence
between any such collection of coefficient vectors $L_{v}$ and a collection of
quadratic forms $g_{1},\ldots,g_{l}$ via identifying for $v=v(i,j)$ as above
$a_{u,v}=\partial^{2}g_{u}/\partial x_{i}\partial x_{j}$ for $1\leq u\leq l$.
In other words, $a_{u,v}x_{i}x_{j}$ if $i\neq j$ and $(a_{u,v}/2)x_{i}^{2}$ if
$i=j$ is the term containing $x_{i}x_{j}$ resp. $x_{i}^{2}$ in the quadratic
form $g_{u}(\mathbf{x})=\sum_{i,j}a_{u,v}x_{i}x_{j}$. Hence (II) holds for the
globally defined function $g=(g_{1},\ldots,g_{l})$, so $(l,n)$ is a good pair.
∎

In the proof, we may just let $L_{v}$ the canonical base vectors in
$\mathbb{R}^{l}$ for $1\leq v\leq l$ so that essentially $z_{v}$ equals
$s_{v}$, however the proof contains more information.

Hence the problem (II) can be relaxed to finding suitable matrices $M_{l,n}$
as in the lemma. For $l=2,n=4$ we can take the matrix

$M_{2,4}=\begin{pmatrix}z_{1}&z_{2}\\\ z_{2}&-z_{1}\end{pmatrix}$

which leads to Example 3.1. More generally, for $l=2$ and $n=2v$ with $v\geq
2$ an even integer, we may take a matrix consisting of $v-1$ copies of
$2\times 2$ “diagonal” blocks as above and zeros elsewhere, similar to Example
3.2 and Proposition 2.2.

For $l=3,n=7$ we can take

$M_{3,7}=\begin{pmatrix}z_{1}&z_{2}&z_{3}&-z_{3}\\\
z_{2}&-z_{1}&z_{3}&z_{3}\\\ z_{3}&z_{3}&z_{1}&z_{2}\\\
-z_{3}&z_{3}&z_{2}&-z_{1}\end{pmatrix}$ (5)

which has determinant $\det(M_{3,7})=(z_{1}^{2}+z_{2}^{2})^{2}+4z_{3}^{4}$.
Our construction leads to the following example.

######  Example 3.4.

Let $l=3,n=7$. Taking the linear forms $L_{v}$ from the proof of Lemma 3.3 the
canonical base vectors $(1,0,0),(0,1,0),(0,0,1)$ of $\mathbb{R}^{3}$ and
inserting for the $z_{v}$ in $M_{3,7}$ from (5), leads to
$g=(g_{1},g_{2},g_{3})$ with quadratic form entries
$g_{u}(\mathbf{x})=g_{u}(x_{1},x_{2},x_{3},x_{4})$ given by

$\displaystyle
g_{1}(\mathbf{x})=\frac{x_{1}^{2}-x_{2}^{2}+x_{3}^{2}-x_{4}^{2}}{2},$
$\displaystyle g_{2}(\mathbf{x})=x_{1}x_{2}+x_{3}x_{4},$ $\displaystyle
g_{3}(\mathbf{x})=x_{1}x_{3}+x_{2}x_{3}+x_{2}x_{4}-x_{1}x_{4}.$

So, the manifold becomes

$\mathcal{M}=\\{(x_{1},x_{2},x_{3},x_{4},g_{1}(\mathbf{x}),g_{2}(\mathbf{x}),g_{3}(\mathbf{x}):x_{i}\in\mathbb{R}\\},$

which satisfies (I) and (II), and thus GBSP for any decreasing $\Psi$ with
property $\mathbf{P}$.

For $l=3$ we may take any $n\in\\{7,11,15,19,\ldots\\}$ again by repeating
this $4\times 4$-block matrix $M_{3,7}$ along the “diagonal”. It is unclear if
$l=3$ and $n\in\\{9,13,17,\ldots\\}$ can be achieved. It would suffice to
verify this for $n=9$ to infer the claim for all $n$ in the list by
considering matrices decomposing into two types of diagonal blocks, $M_{3,7}$
and the vacant $M_{3,9}$. This would confirm Conjecture 1 for $l=3$ as well.
Unfortunately, we are unable to find a suitable matrix $M_{3,9}$.

The above discussion on Lemma 3.3 motivates the following problem implicitly
stated within Conjecture 1.

######  Problem 1.

Given $l\geq 3$, what is the minimum $n$ so that a matrix $M_{l,n}$ as in
Lemma 3.3 exists? Equivalently, given even $n-l$, what is the largest $l$ for
which the hypothesis holds for some matrix.

It is unclear if such $n$ exists at all if $l\geq 4$. As remarked in Section
2.2, in all examples of Section 3, we can manipulate the manifold by adding
any functions with uniformly (in absolute value) small enough second order
derivatives to the $l$ functionally dependent variables. In particular, for
any analytic functions defined on a neighbourhood of
$\mathbf{0}\in\mathbb{R}^{n-l}$ with quadratic terms as in our examples above,
GBSP holds upon possibly shrinking the neighbourhood.

##  4\. Proof of Theorem 1.1

Let us first clarify some notation. Recall that by default all vectors are row
vectors, and we indicate with superscipt $t$ the transpose (thus a column
vector). In particular, for $g$ as above we consider

$g(\mathbf{x})=(g_{1}(\mathbf{x}),\ldots,g_{l}(\mathbf{x}))\in\mathbb{R}^{l},\qquad\mathbf{x}\in
U,$

as a row vector. Consequently the gradient $\nabla h$ of any multivariate
function $h$ with scalar output will be viewed as a line vector as well, and
accordingly the columns of its Hesse matrix $\nabla^{2}h$ are formed by the
partial derivatives of the corresponding fixed component function of the
gradient $\nabla h$.

The proof is a refinement and extension of arguments presented in our previous
paper [9]. Here we only detail some modifications and other necessary details.

For any $\mathbf{q}\in\mathbb{Z}^{n}$ and $p\in\mathbb{Z}$, analogously to [9]
we define

$S(\mathbf{q},p)=S_{\Psi,\theta}(\mathbf{q},p)=\\{\mathbf{x}\in
K:|\mathbf{q}\cdot(\mathbf{x},g(\mathbf{x}))^{t}-p-\theta|<\Psi(\mathbf{q})\\},$

where $K$ is a compact subset of $U$. However, notice that our $g(\mathbf{x})$
is a vector here. Write $\mathbf{q}=\tilde{q}\cdot(\mathbf{r},\boldsymbol{s})$
for

$\tilde{q}=\max_{n-l+1\leq i\leq n}|q_{i}|$

and some $\mathbf{r}\in\mathbb{Q}^{n-l}$, $\boldsymbol{s}\in\mathbb{Q}^{l}$
and let $a=a(\mathbf{q})=(p+\theta)/\tilde{q}$ and
$\rho=\Psi(\mathbf{q})/|\tilde{q}|$ if $\tilde{q}\neq 0$ (assume this for
now). Then $\|\boldsymbol{s}\|=1$, and $\tilde{q}\leq\|\mathbf{q}\|$ by
definition. For any $\mathbf{q}\in\mathbb{Z}^{n}$ and $p\in\mathbb{Z}$, we
will bound the size of this set which is equivalently given as

$S(\mathbf{q},p)=\\{\mathbf{x}\in
K:|\mathbf{r}\cdot\mathbf{x}^{t}+\boldsymbol{s}\cdot
g(\mathbf{x})^{t}-a|<\rho\\}.$

Similarly as in [9], for fixed $p$ and $\mathbf{q}$, define a function
$h:\mathbb{R}^{n-l}\to\mathbb{R}$ by

$h(\mathbf{x})=\mathbf{r}\cdot\mathbf{x}^{t}+\boldsymbol{s}\cdot
g(\mathbf{x})^{t}-a,$

for $\mathbf{r},\boldsymbol{s},a$ induced by $\mathbf{q},p$ as above. Finally
in case $\tilde{q}=0$, we instead let

$\mathbf{r}=(q_{1},\ldots,q_{n-l}),\qquad
h(\mathbf{x})=\mathbf{r}\cdot\mathbf{x}^{t}-p-\theta,\qquad\rho=\Psi(\mathbf{q}).$

As in [9] we see that in either case

$S(\mathbf{q},p)=\\{\mathbf{x}\in K:|h(\mathbf{x})|<\rho\\}.$

We now identify $\nabla^{2}h$ with the matrix $\Lambda$ of the theorem by the
following calculation: If $\tilde{q}\neq 0$, writing $\boldsymbol{s}\cdot
g(\mathbf{x})^{t}=s_{1}g_{1}(\mathbf{x})+\cdots+s_{l}g_{l}(\mathbf{x})$, for
$1\leq i\leq n-l$, the $i$-th entry of the line vector $\nabla h(\mathbf{x})$
equals $r_{i}+\boldsymbol{s}\cdot G_{i}(\mathbf{x})^{t}$ with

$G_{i}(\mathbf{x})=(\partial g/\partial x_{i})(\mathbf{x})=(\partial
g_{1}/\partial x_{i}(\mathbf{x}),\ldots,\partial g_{l}/\partial
x_{i}(\mathbf{x})),$

and this entry being simply $r_{i}$ if otherwise $\tilde{q}=0$. In the sequel
we assume $\tilde{q}\neq 0$, else similarly the argument is analogous to [9].
So this $i$-th entry of $\nabla h(\mathbf{x})$, denote it by $\nabla
h(\mathbf{x})_{i}$, reads

$\nabla h(\mathbf{x})_{i}=r_{i}+\boldsymbol{s}\cdot\left(\frac{\partial
g}{\partial
x_{i}}(\mathbf{x})\right)^{t}=r_{i}+\sum_{u=1}^{l}s_{u}\cdot(\partial
g_{u}/\partial x_{i}(\mathbf{x})),\qquad 1\leq i\leq n-l.$

Then

$\nabla
h(\mathbf{x})-\sum_{i=1}^{n-l}r_{i}\mathbf{e}_{i}=\sum_{i=1}^{n-l}\boldsymbol{s}\cdot\left(\frac{\partial
g}{\partial
x_{i}}(\mathbf{x})\right)^{t}\cdot\mathbf{e}_{i}=\sum_{i=1}^{n-l}\sum_{u=1}^{l}s_{u}\cdot(\partial
g_{u}/\partial x_{i}(\mathbf{x}))\cdot\mathbf{e}_{i},$

with $\mathbf{e}_{i}$ the canonical base vectors in $\mathbb{R}^{n-l}$. Hence
the symmetric quadratic matrix $\nabla^{2}h(\mathbf{x})$ with $j$-th column
$\partial\nabla h(\mathbf{x})/\partial x_{j}$ has entries

$\nabla^{2}h(\mathbf{x})_{i,j}=\sum_{u=1}^{l}s_{u}\cdot\frac{\partial^{2}g_{u}}{\partial
x_{i}\partial x_{j}}(\mathbf{x}),\qquad 1\leq i,j\leq n-l,$ (6)

(and vanishes if $\tilde{q}=0$). Thus indeed we may identify $\nabla^{2}h$
with $\Lambda$. In contrast to [9], the matrix $\nabla^{2}h(\mathbf{x})$ now
also depends on $\mathbf{q}\in\mathbb{Z}^{n}$ via its dependence on the
induced rational unit vector $\boldsymbol{s}$, however by a compactness
argument we will deal with this issue.

By assumption of (II), for any unit vector $\boldsymbol{s}\in\mathbb{R}^{l}$
and any $\mathbf{x}\in K$, the determinant of $\nabla^{2}h(\mathbf{x})$ does
not vanish. For simplicity assume for the moment $\mathbf{q}$ and thus
$\boldsymbol{s}$ are fixed. Then as in [9], for some $\varepsilon>0$, the
matrices $\nabla^{2}h(\mathbf{x})$ with $\mathbf{x}\in K$ belong to a compact,
convex set of matrices (identified with $\mathbb{R}^{(n-l)\times(n-l)}$) with
determinants at least $\varepsilon$. Now the same argument as in [9] based on
the mean value inequality gives the analogue of [9, Claim 2.3], which reads:

$\mathbf{Claim}$: If the norm of $\mathbf{q}\in\mathbb{Z}^{n}$ is large
enough, then either there exists $\mathbf{v}\in\mathbb{R}^{n-l}$ such that

$\|\nabla h(\mathbf{x})\|\asymp\|\mathbf{x}-\mathbf{v}\|,\qquad\mathbf{x}\in
K,$

or

$\|\nabla
h(\mathbf{x})\|\asymp\|(\mathbf{r},\boldsymbol{s})\|\asymp\|(\mathbf{r},1)\|,\qquad\mathbf{x}\in
K.$

Either way, we have $\|\nabla h(\mathbf{x})\|\ll 1$ for all $\mathbf{x}\in K$.

We remark that the last claim is obvious by $\|\boldsymbol{s}\|=1$ and (6). It
should be pointed out that following the proof in [9], the implied constants
in the lemma will still depend on $\mathbf{q}$ in the form of the dependence
on $\boldsymbol{s}$. However, by the continuous dependence of
$\nabla^{2}h(\mathbf{x})$ on $\boldsymbol{s}$ and the compactness of the set
$\\{\boldsymbol{s}\in\mathbb{R}^{l}:\|\boldsymbol{s}\|=1\\}$, it is easily
seen that we can find uniform constants.

The remainder of the proof of Theorem 1.1 works analogously as in [9], where
we consider two cases and we replace $n$ by $n-l+1$ consistently and omit
$\nabla\theta(\mathbf{x})$ and $\nabla^{2}\theta(\mathbf{x})$, as we consider
$\theta$ constant. It is worth noticing that in Case 1 we apply the analogue
of [9, Lemma 2.4], which we again want to state explicitly for convenience:

######  Lemma 4.1 (Hussain, Schleischitz, Simmons).

Assume $n,l$ are positive integers satisfying $n>l+1$. Let
$\phi:U\subset\mathbb{R}^{n-l}\to\mathbb{R}$ be a $C^{2}$ function. Fix
$\alpha>0$, $\delta>0$, and $\mathbf{x}\in U$ such that
$B_{n-l}(\mathbf{x},\alpha)\subset U$. There exists a constant $C>0$ depending
only on $n$ such that if

$\|\nabla\phi(\mathbf{x})\|\geq C\alpha\sup_{\mathbf{z}\in
U}\|\nabla^{2}\phi(\mathbf{z})\|,$ (7)

then the set

$S(\phi,\delta)=\\{\mathbf{y}\in
B_{n-l}(\mathbf{x},\alpha):|\phi(\mathbf{y})|<\|\nabla\phi(\mathbf{x})\|\delta\\}$

can be covered by $\asymp(\alpha/\delta)^{n-l-1}$ balls of radius $\delta$.

Indeed, this is precisely [9, Lemma 2.4], upon replacing $n$ by $n-l+1$. Now
following the proof from [9] with the change of dimensions mentioned above,
and taking into account our observation that the implied constants in the
Claim above can be considered independent of $p,\mathbf{q}$ (or
$\boldsymbol{s}$), indeed this ultimately leads to the sufficient condition
$s<2(n-l-1)$ in place of $s<2n-2$ from [9]. This agrees with condition (I).

## References

  * [1] Dzmitry Badziahin, Victor Beresnevich, and Sanju Velani, _Inhomogeneous theory of dual Diophantine approximation on manifolds_ , Adv. Math. 232 (2013), 1–35. MR 2989975
  * [2] Dzmitry Badziahin, Stephen Harrap, and Mumtaz Hussain, _An inhomogeneous Jarník type theorem for planar curves_ , Math. Proc. Cambridge Philos. Soc. 163 (2017), no. 1, 47–70. MR 3656348
  * [3] A. Baker and Wolfgang M. Schmidt, _Diophantine approximation and Hausdorff dimension_ , Proc. London Math. Soc. (3) 21 (1970), 1–11. MR 0271033
  * [4] Victor Beresnevich, _A Groshev type theorem for convergence on manifolds_ , Acta Math. Hungar. 94 (2002), no. 1-2, 99–130. MR 1905790
  * [5] Vasilii Bernik, _Application of the Hausdorff dimension in the theory of Diophantine approximations_ , Acta Arith. 42 (1983), no. 3, 219–253. MR 729734
  * [6] Jing-Jing Huang, _Hausdorff theory of dual approximation on planar curves_ , J. Reine Angew. Math. 740 (2018), 63–76. MR 3824783
  * [7] by same author, _The density of rational points near hypersurfaces_ , Duke Math. J. 169 (2020), no. 11, 2045–2077. MR 4132580
  * [8] Mumtaz Hussain, _A Jarník type theorem for planar curves: everything about the parabola_ , Math. Proc. Cambridge Philos. Soc. 159 (2015), no. 1, 47–60. MR 3349331
  * [9] Mumtaz Hussain, Johannes Schleischitz, and David Simmons, _The Generalized Baker–Schmidt Problem on Hypersurfaces_ , Int. Math. Res. Not. IMRN (2021), no. 12, 8845–8867. MR 4276306
  * [10] Mumtaz Hussain, Johannes Schleischitz, and David Simmons, _Diophantine approximation on curves_ , https://arxiv.org/abs/arXiv:1902.02094, preprint 2018.
  * [11] Dmitry Kleinbock and Gregory Margulis, _Flows on homogeneous spaces and Diophantine approximation on manifolds_ , Ann. of Math. (2) 148 (1998), no. 1, 339–360. MR 1652916