text:
# Real polarizable Hodge structures arising from foliations

## Introduction

Consider a smooth foliation $``$ on a connected closed manifold $`X`$. The leafwise cohomology of $``$ is the cohomology of the de Rham complex of smooth forms along the leaves. Even its maximal Hausdorff quotient, the reduced leafwise cohomology $`\overline{H}_{}^{}(X)`$, is a quite subtle invariant of the foliation. In particular it can be infinite dimensional even in degree one.

For general foliations there does not seem to be a good structure theory for $`\overline{H}_{}^{}(X)`$. For Riemannian foliations, the situation is different however. This is mainly due to the smooth Hodge decomposition theorem of Álvarez López and Kordyukov . This theorem expresses $`\overline{H}_{}^{}(X)`$ as the space of smooth global forms on $`X`$ along $``$ whose restrictions to the leaves are harmonic.

Given such a Hodge theorem it is a very natural question whether Hodge–Kähler–Lefschetz theory can be generalized to Riemannian $``$ if the leaves are Kähler manifolds. Of course the Kähler structures should vary smoothly in the transverse direction. In this paper we show that this program can be carried through. In fact it can be done quite easily and the first four sections essentially just formulate the resulting assertions, the proofs being mostly consequences of the classical Kähler–Lefschetz identities on non-compact Kähler manifolds. The results are the same as the usual ones except that our Hodge structures can be infinite dimensional.

As in the classical case the existence of a Kähler structure on a Riemannian foliation imposes a number of restrictions on the structure of $`\overline{H}_{}^{}(X)`$, in particular those implied by the hard Lefschetz theorem.

Incidentally the classical case is contained in the foliation formalism by taking for $``$ the foliation which consists of the leaf $`X`$ only. In this case $`\overline{H}_{}^{}(X)`$ becomes the ordinary cohomology of $`X`$ with real coefficients.

As an application of the Kähler formalism we transfer to $`\overline{H}_{}^{}(X)`$ a result of Serre which establishes an analogue of the Weil conjectures for certain induced “Frobenius”-maps on cohomology, see 4.5.

In  Looijenga and Lunts attach a Lie algebra to each compact Kähler manifold using the Hodge–Kähler–Lefschetz formalism. We extend their construction to Kähler–Riemann foliations. In this way one obtains a possibly infinite dimensional Lie algebra attached to a Kähler–Riemann foliation. In proposition 5.2 we determine its structure in the case where $``$ is a foliation by complex surfaces with a dense leaf.

Finally in section 6 we discuss a class of examples suggested to us by E. Ghys. They are the foliations obtained by projecting the foliations $`S_1\times \{pt\}`$ and $`\{pt\}\times S_2`$ to the quotient $`X=\mathrm{\Gamma }(S_1\times S_2)`$. Here $`S_i=G_i/K_i`$ is a bounded symmetric domain for $`i=1,2`$ and the cocompact lattice $`\mathrm{\Gamma }G_1\times G_2`$ is supposed to act without fixed points on $`S_1\times S_2`$. The case of an irreducible lattice is particularly interesting because then the leaves are dense.

For these and more general Kähler–Riemann foliations we express the reduced leafwise cohomology in representation theoretic terms using $`(𝔤,K)`$-cohomology. The final result gives a description of the Hodge $`(p,q)`$-decomposition of $`\overline{H}_{}^{}(X)`$ in these terms. The cohomology $`\overline{H}_{}^{}(X)`$ in these examples is quite interesting and deserves further study.

In the article we have chosen to work with trivial coefficients only. More generally one may consider a Riemannian vector bundle $`V`$ with a Riemannian flat connection along $``$. Using $`V`$-valued forms along $``$ one defines a version of reduced leafwise cohomology with coefficients in $`V`$. All our results transfer to this setting. This is of interest for a possible generalization of the theory to variations of (polarizable) Hodge structures coming from foliated morphisms.

Although it is not apparent, the original motivation for our paper arose from the number theoretical considerations in  § 3 together with the later observation that the cohomology in question should be analogous to reduced leafwise cohomology  § 4.

We would like to thank Don Blasius for discussions about $`(𝔤,K)`$-cohomology and E. Ghys for a letter pointing out the examples in section 6.

## 1 Complex structures on foliations

Let $``$ be a smooth foliation of the manifold $`X`$. By $`T`$ we denote the subbundle of the tangent bundle $`TX`$ whose fibers $`T_x`$ are the tangent spaces of the leaves and by $`T^{}`$ the dual bundle of $`T`$. Let

$$𝒜_{}^r(X):=\mathrm{\Gamma }(X,\mathrm{\Lambda }^rT^{}_{})$$

be the space of complex valued $`r`$-forms along the leaves.

If the dimension of the leaves is even, we define an almost complex structure on $``$ to be a smooth complex structure $`J`$ on $`T`$. That is, $`J`$ is a smooth real vector bundle automorphism of $`T`$ with $`J^2=\mathrm{id}`$. Given such an almost complex structure, $`T`$ becomes a complex vector bundle which we denote by $`T^c`$. The bundle $`T^{}_{}`$, whose fiber over $`x`$ is the space of $``$-linear maps $`T_x`$ then decomposes as

$$T^{}_{}=T^{1,0}T^{0,1}$$

where the fiber $`T_x^{1,0}`$ consists of the $``$-linear maps $`T_x^c`$ and $`T_x^{0,1}`$ of the anti-linear ones. This leads to a decomposition of exterior algebras

$$\mathrm{\Lambda }^{}T^{}_{}=\mathrm{\Lambda }^{}T^{1,0}_{}\mathrm{\Lambda }^{}T^{0,1}.$$

We obtain, with the notation

$$𝒜_{}^{p,q}(X):=\mathrm{\Gamma }(X,\mathrm{\Lambda }^pT^{1,0}\mathrm{\Lambda }^qT^{0,1}),$$

a bigrading

$$𝒜_{}^{}(X)=\underset{p,q}{}𝒜_{}^{p,q}(X).$$

An almost complex structure $`J`$ on $``$ defines, for each leaf $`\mathrm{}`$, by restriction an almost complex structure $`J_{\mathrm{}}:T\mathrm{}T\mathrm{}`$ on the manifold $`\mathrm{}`$. We have correspondingly a bigrading

$$𝒜^{}(\mathrm{})=\underset{p,q}{}𝒜^{p,q}(\mathrm{})$$

of complex valued differential forms on $`\mathrm{}`$. The following fact is obvious:

###### 1.1

An element $`\alpha 𝒜_{}^r(X)`$ belongs to $`𝒜_{}^{p,q}(X)`$ if and only if the restrictions $`\alpha |\mathrm{}`$ belong to $`𝒜^{p,q}(\mathrm{})`$ for all leaves $`\mathrm{}`$.

If all the $`J_{\mathrm{}}`$ are integrable (which is the case if and only if all the leaves are complex manifolds) we say that $`J`$ is a complex structure on $``$.

The exterior derivative along the leaves,

$$d_{}:𝒜_{}^r(X)𝒜_{}^{r+1}(X),$$

has the property that

$$(d_{}\alpha )|\mathrm{}=d_{\mathrm{}}(\alpha |l)$$

where $`d_{\mathrm{}}`$ is the exterior derivative on the manifold $`\mathrm{}`$.

Hence we conclude from 1.1:

###### 1.2

If $`J`$ is a complex structure on $``$, we obtain a decomposition

$$d_{}=_{}+\overline{}_{}$$

where $`_{}`$ has bidegree $`(1,0)`$ and $`\overline{}_{}`$ has bidegree $`(0,1)`$. With the obvious notations, we have

$`(_{}\alpha )|\mathrm{}`$ $`=`$ $`_{\mathrm{}}(\alpha |\mathrm{}),`$
$`(\overline{}_{}\alpha )|\mathrm{}`$ $`=`$ $`\overline{}_{\mathrm{}}(\alpha |\mathrm{}).`$
###### 1.3

Assume that $`dimX=a`$. A $`2g`$-dimensional foliation $``$ together with a complex structure can be described equivalently as follows. It is given by a maximal atlas of charts:

$$\varphi :U\stackrel{}{}V\times W\text{with}UX,V^g,W^{a2g}\text{all open}$$

such that the coordinate changes take the form:

$$\varphi _2\varphi _1^1(z,w)=(g_1(z,w),g_2(w)).$$

Here $`g_1`$ and $`g_2`$ are $`C^{\mathrm{}}`$ and for every $`w`$ the function $`zg_1(z,w)`$ is holomorphic.

It is clear that such an atlas determines a foliation with a complex structure. The converse follows from the Newlander–Nirenberg theorem with parameters stated on p. 404 of .

###### 1.4

For a smooth foliation $``$ let $`𝒞_{}`$ denote the sheaf of germs of smooth complex valued functions which are locally constant on the leaves. Let $`𝒜_{}^r`$ denote the sheaf of smooth sections of $`\mathrm{\Lambda }^rT^{}_{}`$. The primitive in a star shaped domain constructed in the standard proof of the Poincaré Lemma depends smoothly on parameters. There follows the well known fact that

$$0𝒞_{}𝒜_{}^0\stackrel{d_{}}{}𝒜_{}^1\mathrm{}$$

is a fine resolution of $`𝒞_{}`$. In particular we get an isomorphism

$$H^r(X,𝒞_{})=H^r(𝒜_{}^{}(X),d_{}).$$

The cohomology is called the leafwise cohomology of $``$. Its maximal Hausdorff-quotient with respect to the natural Fréchet topologies on the $`𝒜_{}^r(X)`$’s is called the reduced leafwise cohomology of $``$ with complex coefficients:

$$\overline{H}_{}^r(X,):=\overline{H}^r(X,𝒞_{})=\overline{H}^r(𝒜_{}^{}(X),d_{}).$$

Using real valued forms, one defines in the same way the reduced leafwise cohomology $`\overline{H}_{}^r(X)`$ of $``$ with real coefficients.

If $``$ carries a complex structure, let $`\mathrm{\Omega }_{}^p`$ denote the sheaf of germs of smooth complex valued $`p`$-forms along the leaves which are holomorphic on the leaves. Let $`𝒜_{}^{pq}`$ denote the sheaf of smooth sections of $`\mathrm{\Lambda }^pT^{1,0}\mathrm{\Lambda }^qT^{0,1}`$. Using 1.3 a close inspection of the proof of the $`\overline{}`$-Poincaré Lemma in  p. 25 shows that the primitive constructed there depends smoothly on parameters. If follows that

$$0\mathrm{\Omega }_{}^p𝒜_{}^{p,0}\overline{}𝒜_{}^{p,1}\mathrm{}$$

is a fine resolution of $`\mathrm{\Omega }_{}^p`$. Hence there are natural isomorphisms

$$H^q(X,\mathrm{\Omega }_{}^p)H^q(𝒜_{}^{p,}(X),\overline{}_{}).$$

The reduced versions of these leafwise Dolbeault cohomology groups are again defined by passing to the maximal Hausdorff-quotient:

$$\overline{H}^q(X,\mathrm{\Omega }_{}^p):=\overline{H}^q(𝒜_{}^{p,}(X),\overline{}_{}).$$

## 2 Kähler foliations

We consider a $`2g`$-dimensional foliation $``$ on $`X`$ with a complex structure on $``$. Let $`h`$ be an Hermitian metric on the bundle $`T^c`$. Generalizing the usual notation, we write

$$h=S2i\omega _{}$$

with real forms $`S`$ and $`\omega _{}`$. Then $`S`$ is a Riemannian metric on the bundle $`T`$, and $`\omega _{}𝒜_{}^{1,1}(X)`$. The leafwise $``$-operator

$$_{}:𝒜_{}^{p,q}(X)𝒜_{}^{gq,gp}(X)$$

is the pointwise operator defined by $`(_{}\alpha )|\mathrm{}=_{\mathrm{}}(\alpha |\mathrm{})`$ where $`_{\mathrm{}}`$ is the $``$-operator on the manifold $`\mathrm{}`$ endowed with the Riemannian metric obtained by restricting $`S`$ and with the orientation coming from the complex structure. We introduce the first order differential operators

$`d_{}^{}`$ $`:=`$ $`_{}d_{}_{},`$
$`_{}^{}`$ $`:=`$ $`_{}\overline{}_{}_{},`$
$`\overline{}_{}^{}`$ $`:=`$ $`_{}_{}_{}.`$
Then $`(d_{}^{}\alpha )|\mathrm{}=d_{\mathrm{}}^{}(\alpha |\mathrm{})`$ for each leaf $`\mathrm{}`$, where $`d_{\mathrm{}}^{}`$ is the formal adjoint of $`d_{\mathrm{}}`$, and similarly for the other operators (cf. , Ch. V, Prop. 2.3, Prop. 2.4 and a footnote on p. 191).

We form the Laplacians

$`\mathrm{\Delta }_{}`$ $`:=`$ $`d_{}d_{}^{}+d_{}^{}d_{},`$
$`\mathrm{}_{}`$ $`:=`$ $`_{}_{}^{}+_{}^{}_{},`$
$`\overline{\mathrm{}}_{}`$ $`:=`$ $`\overline{}_{}\overline{}_{}^{}+\overline{}_{}^{}\overline{}_{}.`$
Finally, we define the operators $`L_{}`$ and $`L_{}^{}`$ on $`𝒜_{}^{}(X)`$ by

$`L_{}(\alpha )`$ $`:=`$ $`\alpha \omega _{},`$
$`L_{}^{}`$ $`:=`$ $`_{}^1L_{}_{}.`$
Observe that $`L_{}`$ and $`L_{}^{}`$ are pointwise operators and that $`L_{}^{}`$ is the pointwise adjoint of $`L_{}`$.

A form $`\alpha 𝒜_{}^{}(X)`$ is called harmonic if $`\mathrm{\Delta }_{}(\alpha )=0`$ and primitive if $`L_{}^{}(\alpha )=0`$.

Definition A foliation $``$ is called a Kähler foliation if it is endowed with a complex structure $`J`$ and an Hermitian metric $`h=S2i\omega _{}`$ on $`T^c`$ such that

$$d_{}\omega _{}=0.$$

The leaves of a Kähler foliation are Kähler manifolds, and it is clear that the Kähler identities (, Ch. II, Sections 5 and 6, or , Ch. V, p. 191–195) hold in the foliated context. In particular,

$$\mathrm{\Delta }_{}=2\mathrm{}_{}=2\overline{\mathrm{}}_{}$$

is a real operator of bidegree $`(0,0)`$ which commutes with $`L_{}`$ and $`L_{}^{}`$. Denote by $`_{}^r(X)`$ \[resp. $`_{}^{p,q}(X)`$\] the harmonic forms in $`𝒜_{}^r(X)`$ \[resp. $`𝒜_{}^{p,q}(X)`$\] and by $`_{}^r(X)_0`$ \[resp. $`_{}^{p,q}(X)_0`$\] the primitive elements in $`_{}^r(X)`$ \[resp. $`_{}^{p,q}(X)`$\]. Then as topological vector spaces:

$$_{}^{p,q}(X)_{}^{q,p}(X)_{}^{gq,gp}(X)_{}^{gp,gq}(X).$$

From the Lefschetz decomposition theorem (, Th. 3 on p. 26 or , Th. 3.12 on p. 182) we obtain:

###### 2.1

For a Kähler foliation $``$ of dimension $`2g`$, we have

$$_{}^r(X)=\underset{s\mathrm{max}(rg,0)}{}L_{}^s(_{}^{r2s}(X)_0)$$

and, more precisely,

$$_{}^{p,q}(X)=\underset{s\mathrm{max}(p+qg,0)}{}L_{}^s(_{}^{ps,qs}(X)_0).$$

Since $`L_{}^{gr}`$ is injective on $`𝒜_{}^r(X)`$ for $`r<g`$ (, Th. 3.12.c) on p. 182), 2.1 yields the following version of the hard Lefschetz theorem:

###### 2.2

Let $``$ be a Kähler foliation on $`X`$ of dimension $`2g`$. Then

$$L_{}^{gr}:_{}^r(X)_{}^{2gr}(X)$$

is an isomorphism for $`r<g`$.

## 3 Kähler foliations on closed manifolds

###### 3.1

From now on, we consider foliations on closed manifolds. To fix some notations, we consider for the moment an arbitrary oriented and transversally oriented foliation $``$ on the closed Riemannian manifold $`X`$. We then have star operators $`_{}`$ and $`_{}`$ on the subbundles $`\mathrm{\Lambda }T^{}`$ and $`\mathrm{\Lambda }(T)^{}`$ of $`\mathrm{\Lambda }T^{}X`$. On the manifold $`X`$ we take the orientation for which the volume form is given by

$$\mathrm{vol}=_{}(1)_{}(1).$$

We get a scalar product on $`𝒜_{}^r(X)=\mathrm{\Gamma }(X,\mathrm{\Lambda }^rT^{})`$ by

$$(\alpha ,\beta ):=_X\alpha ,\beta \mathrm{vol}=_X\alpha \overline{\beta }.$$

Here $``$ is the star operator of $`X`$ which is equal to $`_{}_{}`$ up to a sign. This sign is computed in , Lemma 3.2, and is such that

$$(\alpha ,\beta )=_X_{}(1)\alpha _{}(\overline{\beta }).$$

###### 3.2

Now we specialize the situation of 3.1 by taking $``$ to be a Kähler foliation on the closed orientable manifold $``$. Let us retain the notations of section 2. We can extend the Riemannian metric $`S`$ on $`T`$ to a Riemannian metric on $`TX`$ and choose an orientation for $`T^{}`$. The last equation in 3.1 shows that

$$𝒜_{}^r(X)=\underset{p+q=r}{}𝒜_{}^{p,q}(X)$$

is an orthogonal decomposition.

###### 3.3

As in the non-foliated context, we consider a variant $`Q`$ of the scalar product $`(,)`$ on harmonic forms, as follows:
Given $`\xi ,\eta _{}^r(X)`$, write $`\xi =_sL_{}^s\xi _s`$ and $`\eta =_sL_{}^s\eta _s`$ with primitive forms $`\xi _s,\eta _s`$ according to 2.1 and define

$$Q(\xi ,\eta ):=\underset{s}{}(1)^{s+r(r+1)/2}_X_{}(1)L_{}^{gr+2s}(\xi _s\eta _s).$$

Obviously, we have

$$Q(\xi ,\eta )=(1)^rQ(\eta ,\xi ).$$

Denote by $`J`$ the automorphism of $`𝒜_{}^{}(X)`$ which is multiplication by $`i^{pq}`$ on $`𝒜_{}^{p,q}(X)`$. The proof of , Ch. V, Th. 6.1 shows that there are positive constants $`c_s`$ such that

$$Q(\xi ,J\overline{\eta })=\underset{s}{}c_s(L^s\xi _s,L^s\eta _s).$$

In particular, we have $`Q(\xi ,J\overline{\xi })>0`$ for $`\xi 0`$.

Moreover, $`Q(J\xi ,J\eta )=Q(\xi ,\eta )`$.

###### 3.4

As before, let $``$ be a Kähler foliation of complex dimension $`g`$ on the closed manifold $`X`$; we assume now that $`g`$ is even. The bilinear form

$$I(\alpha ,\beta )=_X\alpha \beta $$

on $`_{}^g(X)`$ is symmetric and real. Assume that $`dim_{}^g(X)<\mathrm{}`$. We denote the signature of $`I`$ by sign $``$ and call it the signature of $``$. By 2.2, $`_{}^{\mathrm{even}}`$ is then finite dimensional, and the argument on p. 76–77 of  shows that we have the following version of the Hodge index theorem:

$$\mathrm{sign}()=\underset{pq(2)}{}(1)^pdim_{}^{p,q}(X).$$

## 4 Kähler–Riemann foliations

So far, cohomology has not entered our discussion. To have a Kähler theory on the cohomology of a foliation, we have to restrict our foliations further: Let $`(X,)`$ be any foliation. Recall that a Riemannian metric on $`X`$ is called bundle-like for $``$, if the normal plane field of $``$ is totally geodesic. Equivalently, the metric is bundle-like if for each pair of normal vector fields $`Y`$ and $`Z`$ which are infinitesimal automorphisms of $``$ and for each tangential vector field $`W`$ we have $`WY,Z=0`$. A foliation which admits a bundle-like metric is called Riemannian.

Given an oriented and transversally oriented foliation $``$ on the closed manifold $`X`$ and a bundle-like metric for $``$, our leafwise adjoint $`d_{}^{}`$ is the formal adjoint of the operator $`d_{}`$ on $`X`$ (, Section 3), and a fundamental result of  says that there is an orthogonal Hodge decomposition

(1)
$$𝒜_{}^{}(X)=_{}^{}(X)\overline{\mathrm{im}d_{}}\overline{\mathrm{im}d_{}^{}}.$$

Here, the bar denotes closure in the Fréchet space $`𝒜_{}^{}(X)`$. In particular, the reduced leafwise complex cohomology

$$\overline{H}_{}^{}(X,)=\mathrm{ker}d_{}/\overline{\mathrm{im}d_{}}$$

is isomorphic to $`_{}^{}(X)`$. This Hodge decomposition does not hold in general for non-Riemannian foliations .

Remark Denoting the dimension of $``$ by $`m`$, we get a linear form $`\nu `$ on $`\mathrm{\Gamma }(X,\mathrm{\Lambda }^mT^{})`$ by

$$\nu (\omega ):=_{}(1)\omega =(\omega ,_{}(1)).$$

Since $`d_{}^{}`$ is the formal adjoint of $`d_{}`$, we see that $`\nu (d_{}\beta )=0`$; hence $`\nu `$ induces a (continuous) linear form on $`H_{}^m(X)`$, the leafwise real $`m`$-dimensional cohomology group. This functional in turn induces a linear form

$$\nu :\overline{H}_{}^m(X)$$

on the corresponding reduced group. We get a scalar product on every $`\overline{H}_{}^n(X)`$ by setting:

$`(a,b)`$ $`=`$ $`\nu (a_{}b)`$
$`=`$ $`{\displaystyle _X}(a),(b)_{}\mathrm{vol}.`$
Here $`(a),(b)`$ are the harmonic representatives of $`a`$ and $`b`$ and $`_{}a:=[_{}(a)]`$. In fact under the isomorphism

$$\overline{H}_{}^n(X)_{}^n(X)$$

this scalar product becomes the restriction of the scalar product on forms from 3.1.

The bilinear form

$$(a,b)\nu (ab)$$

on $`\overline{H}_{}^{}(X)`$ is obviously non-degenerate in the sense that for every $`a\overline{H}_{}^{}(X)`$ with $`a0`$, there exists $`b`$ with $`\nu (ab)0`$. If $``$ has a dense leaf, we have $`\overline{H}_{}^m(X)\overline{H}_{}^0(X)`$, and there is the following version of Poincaré duality:

###### 4.1

Let $``$ be an orientable and transversely orientable Riemannian foliation of dimension $`m`$ on the closed manifold $`X`$. Assume that $``$ has a dense leaf. For any isomorphism $`:\overline{H}_{}^m(X)`$, the bilinear form $`(a,b)ab`$ is non-degenerate.

Definition A Kähler foliation $`(X,,h=S2i\omega _{})`$ which is also a Riemannian foliation is called a Kähler–Riemann foliation. A Riemannian metric on $`X`$ is Kähler-bundle-like if it is bundle-like and if its restriction to $`T`$ agrees with $`S`$.

A Kähler–Riemann foliation always admits a Kähler-bundle-like metric. Hence, given a Kähler–Riemann foliation $``$ on the closed orientable manifold $`X`$, we obtain a decomposition

(2)
$$\overline{H}_{}^r(X,)=\underset{p+q=r}{}H^{p,q}$$

where $`H^{p,q}`$ is the image of $`_{}^{p,q}(X)`$ under the natural isomorphism. The subspace $`H^{p,q}`$ is closed in $`\overline{H}_{}^r(X,)`$, and we have $`\overline{H^{p,q}}=H^{q,p}`$; in this equation, the bar denotes complex conjugation.

In particular, a necessary condition for the existence of a Kähler structure on a Riemannian foliation is this: The reduced leafwise cohomology groups in odd degree must be of even dimension if they are finite dimensional.

In particular for Riemannian foliations by (real) surfaces $`dim\overline{H}_{}^1(X)`$ is even if finite since such foliations always carry a Kähler structure: A metric on $`T`$ determines an almost complex structure on $`T`$ which is integrable since the leaves are $`2`$-dimensional. The associated Kähler form is closed for degree reasons.

###### Proposition 4.2

$`H^{p,q}`$ consists of those reduced cohomology classes which can be represented by a cocycle contained in $`𝒜_{}^{p,q}(X)`$. In particular, the decomposition (2) only depends on the complex structure $`J`$ and not on the Kähler form.

Proof Let $`\pi :𝒜_{}^{}(X)_{}^{}(X)`$ be the projection according to (1). Since the decompositions (1) and $`𝒜^{}=_{p,q}𝒜^{p,q}`$ are orthogonal, it is clear that $`\pi (𝒜_{}^{pq}(X))=_{}^{p,q}(X)`$.

Therefore, given an element $`\beta 𝒜_{}^{p,q}(X)`$ with $`d_{}\beta =0`$, the cohomology class of $`\beta `$ is also represented by $`\pi (\beta )`$, hence is contained in $`H^{p,q}`$. The rest of 4.2 is obvious.  $`\mathrm{}`$

For a Kähler–Riemann foliation of dimension $`2g`$ on a closed orientable manifold $`X`$, the results of section 2 and 3 can be translated from forms to cohomology:

Forming the cup product with the reduced Kähler class $`[\omega _{}]\overline{H}_{}^2(X)`$ defines a real operator $`L:\overline{H}_{}^{}(X,)\overline{H}_{}^{}(X,)`$ of bidegree $`(1,1)`$, and 2.2 yields a hard Lefschetz theorem:

###### Proposition 4.3

For $`r<g`$, we have an isomorphism

$$L^{gr}:\overline{H}_{}^r(X,)\overline{H}_{}^{2gr}(X,).$$

In particular, $`[\omega _{}]^g0`$.

Also, 3.4 gives a Hodge index theorem for reduced leafwise cohomology.

We call a class $`a\overline{H}_{}^r(X,)`$ primitive if it corresponds to a primitive harmonic form $`\alpha _{}^r(X)_0`$ under the natural isomorphism $`_{}^r(X)\overline{H}_{}^r(X,)`$. For $`rg`$, the class $`a`$ is primitive iff $`L^{gr+1}a=0`$; for $`r>g`$ there are no non-zero primitive classes.

Denoting the set of primitive $`r`$-classes by $`P_{}^r(X)`$, we have by 2.1:

(3)
$$\overline{H}_{}^r(X,)=\underset{s}{}L^s(P_{}^{r2s}(X)).$$

The bilinear form $`Q`$ introduced in 3.3 yields a bilinear form $`Q`$ on $`\overline{H}_{}^r(X,)`$ which can be described as follows: Given $`a,b\overline{H}_{}^r(X,)`$, write $`a=L^sa_s,b=L^sb_s`$ according to (3). Then we have

$$Q(a,b)=\underset{s}{}(1)^{s+r(r+1)/2}\nu (L^{gr+2s}(a_sb_s))$$

where $`\nu `$ is as in the discussion preceding 4.1.

If $``$ has a dense leaf, the non-zero functional $`\nu `$ on $`\overline{H}_{}^{2g}(X,)`$ is determined up to a constant, and we see that in this case $`Q`$ is essentially determined by the Kähler class $`[\omega _{}]`$.

The preceeding discussion also holds for the reduced leafwise cohomology with real coefficients.

Let $`J`$ be the automorphism of $`\overline{H}_{}^n(X,)`$ which is multiplication by $`i^{pq}`$ on $`H^{pq}`$. It follows from 3.3 that

(4)
$$T(a,b)=Q(a,J\overline{b})$$

defines a scalar product on $`\overline{H}_{}^n(X,)`$.

From 3.3 we also conclude:

###### 4.4

$`Q`$ defines a polarization of weight $`r`$ of the real Hodge structure $`P_{}^r(X)`$.

Here, we define real Hodge structures and their polarizations as Deligne (, (2.1.5), (2.1.16)) except that we do not require that our vector spaces are finite dimensional.

###### 4.5

In this subsection we generalize a theorem of Serre  on a Kähler analogue of the Weil conjectures to our context. So assume that $``$ is a Kähler–Riemann foliation of complex dimension $`g`$ with a dense leaf on the oriented manifold $`X`$.

###### Proposition 4.6

Let $`f:XX`$ be a smooth map which maps leaves of $``$ holomorphically into leaves. Assume that the induced map $`f^{}`$ on $`\overline{H}_{}^{}(X,)`$ satisfies the relation:

$$f^{}[\omega _{}]=q[\omega _{}]$$

for some positive real number $`q>0`$. Then on $`\overline{H}_{}^n(X,)`$ we have:

$$f^{}=q^{n/2}U_n$$

where $`U_n`$ is a unitary endomorphism of $`\overline{H}_{}^n(X,)`$ with respect to the scalar product $`T`$ on cohomology defined by (4). In particular the spectral values of $`f^{}`$ have absolute value $`q^{n/2}`$.

Proof Define an endomorphism $`U`$ of the vector space $`\overline{H}_{}^{}(X,)`$ by setting $`U_n=q^{n/2}f^{}`$ in degree $`n`$. Then $`U`$ is an algebra endomorphism of $`\overline{H}_{}^{}(X,)`$. We know that $`[\omega _{}]^g0`$ by 4.3. Moreover since $``$ has a dense leaf, $`\overline{H}_{}^{2g}(X,)`$ is one dimensional. Hence $`U_{2g}=\mathrm{id}`$. Since $`U`$ commutes with the Lefschetz operator $`L`$, we find

$$Q(Ua,Ub)=Q(a,b).$$

Since $`f^{}`$ respects the real structure $`\overline{H}_{}^{}(X)`$ of $`\overline{H}_{}^{}(X,)`$ and since $`f^{}H^{pq}H^{pq}`$ it follows that $`U`$ commutes with $`J`$ and with complex conjugation. Thus

$$T(Ua,Ub)=T(a,b).$$

$`\mathrm{}`$

###### 4.7

We now connect the spaces $`H^{pq}`$ in $`\overline{H}_{}^n(X,)`$ to the reduced leafwise Dolbeault cohomology groups and make a number of further comments. So let $``$ be as before a Kähler–Riemann foliation on the oriented manifold $`X`$ and fix a Kähler bundle-like metric. Using the equation $`\mathrm{\Delta }_{}=2\overline{\mathrm{}}_{}`$ and passing to $`(p,q)`$-types in the Hodge decomposition of :

$$𝒜_{}^{}(X)=\mathrm{Ker}\mathrm{\Delta }_{}^{}\overline{\mathrm{im}\mathrm{\Delta }_{}^{}},$$

we obtain the orthogonal decomposition:

$$𝒜_{}^{pq}(X)=\mathrm{Ker}\overline{\mathrm{}}_{}^{pq}\overline{\mathrm{im}\overline{\mathrm{}}_{}^{pq}}.$$

Since $`\mathrm{im}\overline{}_{}`$ and $`\mathrm{im}\overline{}_{}^{}`$ are orthogonal, we get the following Hodge decomposition:

$$𝒜_{}^{pq}(X)=_{}^{pq}(X)\overline{\mathrm{im}\overline{}_{}^{p,q1}}\overline{\mathrm{im}(\overline{}_{}^{p,q+1})^{}}.$$

In particular the reduced leafwise Dolbeault cohomology $`\overline{H}^q(X,\mathrm{\Omega }_{}^p)`$ is isomorphic to $`_{}^{pq}(X)`$ and hence to the subspace $`H^{pq}`$ of $`\overline{H}_{}^{p+q}(X,)`$.

The Hodge $`\overline{}_{}`$-operator induces an anti-isomorphism:

$$\overline{H}^q(X,\mathrm{\Omega }_{}^p)\stackrel{}{}\overline{H}^{gq}(X,\mathrm{\Omega }_{}^{gp}).$$

Moreover, it follows in the case of a dense leaf that the $``$-product pairing:

$$\overline{H}^q(X,\mathrm{\Omega }_{}^p)\times \overline{H}^{gq}(X,\mathrm{\Omega }_{}^{gp})\stackrel{}{}\overline{H}^g(X,\mathrm{\Omega }_{}^g)H^{gg}=\overline{H}_{}^{2g}(X)\stackrel{𝜈}{\stackrel{}{}}$$

is non-degenerate, a weak version of Serre duality.

Define the Hodge filtration $`F^i`$ on $`\overline{H}_{}^n(X,)`$ by:

$$F^i=\mathrm{im}(H^n(X,\mathrm{\Omega }_{}^i)\overline{H}^n(X,\mathrm{\Omega }_{}^{})=\overline{H}_{}^n(X,)).$$

Note here that the complex $`\mathrm{\Omega }_{}^{}`$ is quasi-isomorphic to $`𝒞_{}`$.

###### Proposition 4.8

The subspace $`F^i\overline{H}_{}^n(X,)`$ is closed and we have

$$F^i=\underset{pi}{}H^{pq}.$$

Proof The diagram

$$\begin{array}{ccc}\mathrm{\Omega }_{}^i& & \mathrm{\Omega }_{}^{}\\ & & & & \\ s𝒜_{}^{i,}& & s𝒜_{}^{}\end{array}$$

is commutative and the vertical arrows are quasi-isomorphisms as follows from 1.4. Here $`s`$ denotes the associated simple complex of a double complex. Thus $`F^i`$ can be identified with the image of the natural map

$$H^n(\underset{\genfrac{}{}{0pt}{}{p+q=}{pi}}{}𝒜_{}^{pq}(X),d_{})\overline{H}^n(\underset{p+q=}{}𝒜_{}^{pq}(X),d_{}).$$

Its image consists of those cohomology classes that can be represented by closed forms of the type:

$$\underset{\genfrac{}{}{0pt}{}{p+q=n}{pi}}{}\alpha _{pq}\text{with}\alpha _{pq}𝒜_{}^{pq}(X).$$

Passing to the harmonic projections of the $`\alpha _{pq}`$, we see that every form in the image can be represented by a form

$$\underset{\genfrac{}{}{0pt}{}{p+q=n}{pi}}{}h_{pq}\text{with}h_{pq}𝒜_{}^{pq}(X)\text{and}dh_{pq}=0.$$

Hence

$$F^i=\underset{pi}{}H^{pq}$$

and in particular $`F^i`$ is a closed subspace, since the $`H^{pq}`$’s are.  $`\mathrm{}`$

## 5 The Lie algebra attached to a Kähler– <br>Riemann foliation

There is a construction due to Looijenga and Lunts  attaching a Lie algebra to each compact Kähler manifold. We extend this construction to Kähler–Riemann foliations; new phenomena can occur because the cohomology may be of infinite dimension.

In this section we consider only complex Lie algebras.

Let $``$ be a $`2g`$-dimensional Kähler–Riemann foliation of the closed orientable manifold $`X`$. Let $`B`$ be the endomorphism of the graded vector space $`\overline{H}^{}:=\overline{H}_{}^{}(X,)`$ which is multiplication by $`gr`$ on $`\overline{H}^r`$. For $`\omega \overline{H}^2`$, let $`L_\omega `$ be the endomorphism of $`\overline{H}^{}`$ of degree $`2`$ given by $`L_\omega (x)=x\omega `$. By $`𝒦_{}(X)`$ we denote the non-empty set of all those $`\omega \overline{H}^2`$ for which $`L_\omega ^k`$ is an isomorphism of $`\overline{H}^{gk}`$ onto $`\overline{H}^{g+k}`$ for all $`k0`$.

###### 5.1

For $`\omega 𝒦_{}(X)`$, there exists a uniquely determined endomorphism $`\mathrm{\Lambda }_\omega `$ of $`\overline{H}^{}`$ of degree $`2`$ such that

$$[\mathrm{\Lambda }_\omega ,L_\omega ]=B.$$

Proof As observed in , the assertion follows from the Jacobson–Morozov lemma in the finite dimensional case. The general case can be easily deduced.  $`\mathrm{}`$

The two elements $`L_\omega `$ and $`\mathrm{\Lambda }_\omega `$ generate a Lie subalgebra of $`\mathrm{End}(\overline{H}^{})`$ isomorphic to $`𝔰𝔩_2`$.

Let $`𝔤=𝔤()`$ be the Lie algebra generated by all the $`L_\omega `$ and $`\mathrm{\Lambda }_\omega `$ with $`\omega 𝒦_{}(X)`$. If $`dim\overline{H}^{}<\mathrm{}`$ then $`\overline{H}^{}`$ is an $`\overline{H}^2`$-Lefschetz-module in the sense of , that is, $`𝔤`$ is semisimple.

Of course, one can consider the even and the odd parts of $`\overline{H}^{}`$ separately: Let $`𝒦_{\mathrm{even}}`$ be the set of all $`\omega \overline{H}^2`$ with the following property: For all $`k`$ with $`kg(\mathrm{mod}\mathrm{\hspace{0.33em}2}),L_\omega ^k`$ is an isomorphism of $`\overline{H}^{gk}`$ onto $`\overline{H}^{g+k}`$. For $`\omega 𝒦_{\mathrm{even}}`$, there is an associated endomorphism $`\mathrm{\Lambda }_\omega `$ of $`\overline{H}^{\mathrm{even}}`$. Let $`𝔤_{\mathrm{even}}`$ be the Lie subalgebra of $`\mathrm{End}(\overline{H}^{\mathrm{even}})`$ generated by the $`L_\omega `$ and $`\mathrm{\Lambda }_\omega `$ with $`\omega 𝒦_{\mathrm{even}}`$. Similarly, one can define $`𝔤_{\mathrm{odd}}`$.

As an example, let us determine the Lie algebra $`𝔤_{\mathrm{even}}`$ in the case that $`g=2`$ and that $``$ has a dense leaf. In this situation, $`\overline{H}^0=`$ and we can choose an isomorphism $`uu`$ of $`\overline{H}^4`$ onto $``$. We obtain a symmetric bilinear form $`\phi `$ on $`\overline{H}^{\mathrm{even}}`$ by

$`\phi |\overline{H}^k\times \overline{H}^h=0`$ if $`k+h4,`$
$`\phi (u,v)={\displaystyle uv}`$ if $`u\overline{H}^4,v\overline{H}^0,`$
$`\phi (u,v)={\displaystyle uv}`$ if $`u,v\overline{H}^2.`$
Let $`𝔰𝔬(\overline{H}^{\mathrm{even}},\phi )`$ be the Lie algebra of all endomorphisms $`A`$ of $`\overline{H}^{\mathrm{even}}`$ with

$$\phi (Au,v)+\phi (u,Av)=0$$

for all $`u,v\overline{H}^{\mathrm{even}}`$, and let $`𝔰𝔬_{\mathrm{fin}}(\overline{H}^{\mathrm{even}},\phi )`$ be the Lie subalgebra of $`𝔰𝔬(\overline{H}^{\mathrm{even}},\phi )`$ consisting of all endomorphisms of finite rank.

###### Theorem 5.2

If $`g=2`$ and if $``$ has a dense leaf, we have

$$𝔤_{\mathrm{even}}=𝔰𝔬_{\mathrm{fin}}(\overline{H}^{\mathrm{even}},\phi ).$$

If $`dim\overline{H}^{\mathrm{even}}=\mathrm{}`$, this is a simple Lie algebra.

Proof Let us abbreviate $`𝔰𝔬_{\mathrm{fin}}(\overline{H}^{\mathrm{even}},\phi )`$ by $`𝔤`$. In our situation,

$$𝒦_{\mathrm{even}}=\{\omega \overline{H}^2|\omega ^20\}.$$

For $`\omega 𝒦_{\mathrm{even}}`$, the homomorphism $`\mathrm{\Lambda }_\omega :\overline{H}^4\overline{H}^2`$ is given by $`\mathrm{\Lambda }_\omega (\omega ^2)=2\omega `$, and

$$\mathrm{\Lambda }_\omega :\overline{H}^2=\omega \mathrm{ker}L_\omega \overline{H}^0$$

is given by

$$\begin{array}{c}\mathrm{\Lambda }_\omega (\omega )=2,\hfill \\ \mathrm{ker}(\mathrm{\Lambda }_\omega |\overline{H}^2)=\mathrm{ker}(L_\omega |\overline{H}^2).\hfill \end{array}$$

Since $`L_\omega `$ and $`\mathrm{\Lambda }_\omega `$ have rank $`2`$ on $`\overline{H}^{\mathrm{even}}`$ and since obviously

$$L_\omega ,\mathrm{\Lambda }_\omega 𝔰𝔬(\overline{H}^{\mathrm{even}},\phi ),$$

we see that $`𝔤_{\mathrm{even}}𝔤`$. Now observe the following three points,
using 4.1 for (a):
(a) Given a finite dimensional subspace $`U`$ of $`\overline{H}^{}`$, there exists a finite dimensional subspace $`W`$ of $`\overline{H}^{}`$ containing $`U`$ such that the restriction $`\phi _W`$ of $`\phi `$ to $`W\times W`$ is non-degenerate.
(b) If $`W`$ is a finite dimensional subspace of $`\overline{H}^{}`$ such that $`\phi _W`$ is non-degenerate, there is a decomposition $`\overline{H}^{}=WW^{}`$ where $`W^{}`$ is formed with respect to $`\phi `$. Let

$$𝔤_W:=\{A𝔤|A(W)W\text{and}A|W^{}=0\}.$$

Then $`𝔤_W`$ is a Lie subalgebra of $`𝔤`$ which is isomorphic to $`𝔰𝔬(W,\phi _W)`$.
(c) For $`A𝔤`$ and a finite dimensional subspace $`W`$ of $`\overline{H}^{}`$ containing $`\mathrm{im}A`$ and such that $`\phi _W`$ is non-degenerate, we have $`A𝔤_W`$.

To see that $`𝔤𝔤_{\mathrm{even}}`$, consider an element $`A𝔤`$ and choose a finite dimensional subspace $`W`$ such that $`\phi _W`$ is non-degenerate and $`A𝔤_W`$. We may assume that $`W`$ is of the form $`W=\overline{H}^0W^2\overline{H}^4`$ with $`W^2\overline{H}^2`$. Then $`W`$ is a graded algebra, and it is clear (cf. , the beginning of section 4) that the Lie algebra attached to it is $`𝔰𝔬(W,\phi _W)`$. Hence $`A𝔤_{\mathrm{even}}`$.

To see that $`𝔤`$ is simple if $`dim\overline{H}^{}=\mathrm{}`$, assume that there is a proper ideal $`𝔞`$ of $`𝔤`$. Take elements $`A𝔞,A0`$, and $`C𝔤,C𝔞`$. Let $`W`$ be a finite dimensional subspace of $`\overline{H}^{}`$ containing $`\mathrm{im}A`$ and $`\mathrm{im}C`$ such that $`\phi _W`$ is non-degenerate. Then $`A,C𝔤_W`$. Hence $`𝔞𝔤_W`$ is a proper ideal in $`𝔤_W`$. Assuming that $`dimW>4`$, the Lie algebra $`𝔤_W`$ is simple. This is a contradiction.  $`\mathrm{}`$

###### Remark 5.3

If there is no dense leaf, the situation looks quite different: For example, let $`X=S^1\times S^2`$ with leaves $`\{a\}\times S^2`$. Then

$$𝔤()=𝔰𝔩_2(C^{\mathrm{}}(S^1)),$$

considered as a complex Lie algebra. It has very many ideals.

Even if there is a dense leaf and if $`g3`$, it is not likely that $`𝔤()`$ is always a finite product of simple Lie algebras.

## 6 Examples of Kähler–Riemann foliations

In this section we consider a class of examples that were suggested to us by E. Ghys. We begin with the following general setup which will be specialized to our needs later.

Let $`G`$ be a real Lie group with a discrete subgroup $`\mathrm{\Gamma }`$ and a compact connected subgroup $`K`$ such that $`\mathrm{\Gamma }`$ operates freely on the manifold $`S=G/K`$. Then $`X=\mathrm{\Gamma }S`$ is a manifold as well. Consider a connected normal sub Lie group $`G_1`$ of $`G`$. Then $`K_1=G_1K`$ is a compact normal subgroup of $`K`$.

The orbits of the left $`G_1`$-operation on $`S`$ define a foliation $`_S`$ on $`S`$ of dimension $`dimG_1/K_1`$. This follows because the isotropy groups

$$(G_1)_{gK}=gKg^1G_1=gK_1g^1$$

all have the same dimension, $`G_1`$ being normal in $`G`$,  1.12 iii). The $`\mathrm{\Gamma }`$-operation on $`S`$ carries leaves of $`_S`$ into leaves:

$$\gamma (G_1gK)=G_1\gamma gK,$$

again since $`G_1`$ is normal. Thus $`_S`$ descends to a foliation $``$ on $`X`$ with leaves

$$\mathrm{\Gamma }G_1gK=\mathrm{\Gamma }gG_1K.$$

The space of leaves on $`X`$ is therefore:

(5)
$$X/=\mathrm{\Gamma }G/G_1K.$$

There are natural isomorphisms of vector bundles on $`S`$:

(6)
$$G\times _K𝔤/𝔨\stackrel{}{}TS\text{and}G\times _K𝔤_1/𝔨_1\stackrel{}{}T_S,$$

where $`K`$ acts via $`\mathrm{Ad}`$ on $`𝔤/𝔨`$ and $`𝔤_1/𝔨_1`$. They are given by mapping $`[g,\overline{u}]`$ to $`(T_{\overline{e}}L_g)(\overline{u})`$ where $`L_g`$ denotes left multiplication with $`g`$ on $`S`$ and $`\overline{u}𝔤/𝔨=T_{\overline{e}}(G/K)`$ resp.

$$\overline{u}𝔤_1/𝔨_1=T_{\overline{e}}(G_1/K_1)=T_{\overline{e}}(G_1K/K)=T_{\overline{e}}_S.$$

The isomorphisms (6) are left $`G`$-equivariant and hence induce isomorphisms

(7)
$$(\mathrm{\Gamma }G)\times _K𝔤/𝔨\stackrel{}{}TX\text{and}(\mathrm{\Gamma }G)\times _K𝔤_1/𝔨_1\stackrel{}{}T.$$

From (7) we get isomorphisms

$$\mathrm{\Gamma }(X,TX)\stackrel{}{}C^{\mathrm{}}(\mathrm{\Gamma }G,𝔤/𝔨)^K\text{and}\mathrm{\Gamma }(X,T)\stackrel{}{}C^{\mathrm{}}(\mathrm{\Gamma }G,𝔤_1/𝔨_1)^K.$$

If $`f_A`$ is the $`K`$-invariant function corresponding to the vector field $`A`$ then we have explicitely:

$$f_A(\mathrm{\Gamma }gk^1)=\mathrm{Ad}(k)f_A(\mathrm{\Gamma }g)\text{for all}kK,gG.$$

The map

$$C^{\mathrm{}}(\mathrm{\Gamma }G,𝔤)^KC^{\mathrm{}}(\mathrm{\Gamma }G,𝔤/𝔨)^K$$

has a section since $`K`$ is compact. Hence $`f_A`$ can be lifted to a $`K`$-invariant function $`\stackrel{~}{f}_A:\mathrm{\Gamma }G𝔤`$. Under the isomorphism

$$(\mathrm{\Gamma }G)\times 𝔤\stackrel{}{}T(\mathrm{\Gamma }G)$$

the function $`\stackrel{~}{f}_A`$ corresponds to a vector field $`\stackrel{~}{A}`$ on $`\mathrm{\Gamma }G`$. In these terms we have the formula

(8)
$$f_{[A,B]}(\mathrm{\Gamma }g)=\stackrel{~}{A}(\stackrel{~}{f}_B)(\mathrm{\Gamma }g)\stackrel{~}{B}(\stackrel{~}{f}_A)(\mathrm{\Gamma }g)+[\stackrel{~}{f}_A(\mathrm{\Gamma }g),\stackrel{~}{f}_B(\mathrm{\Gamma }g)]\mathrm{mod}𝔨.$$

Choose any $`K`$-invariant scalar product $`(,)`$ on $`𝔤/𝔨`$. Via (7) it induces a Riemannian metric $`g`$ on $`TX`$ such that:

$$g(A,B)_{\mathrm{\Gamma }gK}=(f_A(\mathrm{\Gamma }g),f_B(\mathrm{\Gamma }g)).$$

The following assertion must be well known:

###### Proposition 6.1

The Riemannian metric $`g`$ is bundle-like for $``$. In particular $``$ is Riemannian.

Proof We have the $`K`$-invariant decomposition:

$$𝔤/𝔨=(𝔤_1+𝔨)/𝔨V$$

where $`V`$ is the orthogonal complement of $`(𝔤_1+𝔨)/𝔨`$.

It induces a $`K`$-invariant decomposition:

(9)
$$𝔤=(𝔤_1+𝔨)V$$

where we have identified $`V`$ with its image in $`𝔤/𝔨`$.

A vector field $`A`$ on $`X`$ is orthogonal to $`T`$ if and only if $`f_A`$ takes values in $`V`$. In this case $`\stackrel{~}{f}_A`$ takes values in $`V`$ as well.

Now assume in addition that $`A`$ normalizes $`T`$. Then for every $`B\mathrm{\Gamma }(X,T)`$ the function $`f_{[A,B]}`$ takes values in $`𝔤_1+𝔨/𝔨`$. Since $`\stackrel{~}{f}_B`$ takes values in $`𝔤_1`$, by formula (8) this means that $`\stackrel{~}{B}(\stackrel{~}{f}_A)`$ takes values in $`𝔤_1+𝔨`$. On the other hand, since $`\stackrel{~}{f}_A`$ is $`V`$-valued, $`\stackrel{~}{B}(\stackrel{~}{f}_A)`$ is $`V`$-valued as well, so that $`\stackrel{~}{B}(\stackrel{~}{f}_A)=0`$ for all $`\stackrel{~}{B}`$. This means that $`\stackrel{~}{f}_A`$ is constant on the foliation of $`\mathrm{\Gamma }G`$ by the cosets of $`G_1K`$. Thus $`\stackrel{~}{f}_A`$ and hence $`f_A`$ is a $`V`$-valued function on $`\mathrm{\Gamma }G/G_1K=X/`$.

Therefore if $`A_1,A_2`$ are two vector fields orthogonal to $`T`$ and normalizing $`T`$ it follows that

$$g(A_1,A_2)=(f_A,f_B)$$

is a basic function. Thus $`g`$ is bundle like.  $`\mathrm{}`$

Let $`C^{}(𝔤,K,V)`$ be the complex calculating $`(𝔤,K)`$-cohomology of $`V`$ c.f.  I § 5.

Using (7) we have natural topological isomorphisms:

$`𝒜_{}^p(X)`$ $`=`$ $`\mathrm{\Gamma }(X,\mathrm{\Lambda }^pT^{})`$
$`=`$ $`C^{\mathrm{}}(\mathrm{\Gamma }G,\mathrm{\Lambda }^p(𝔤_1/𝔨_1)^{})`$
$`=`$ $`\mathrm{Hom}_K(\mathrm{\Lambda }^p(𝔤_1/𝔨_1),C^{\mathrm{}}(\mathrm{\Gamma }G))`$
$`=`$ $`C^p(𝔤_1,K_1,C^{\mathrm{}}(\mathrm{\Gamma }G))^{K/K_1}.`$
One checks that we get a topological isomorphism of complexes

$$𝒜_{}^{}(X)=C^{}(𝔤_1,K_1,C^{\mathrm{}}(\mathrm{\Gamma }G))^{K/K_1}.$$

Since $`K/K_1`$ is a compact group, it follows from this that

(10)
$$\overline{H}_{}^{}(X,)=\overline{H}^{}(𝔤_1,K_1,C^{\mathrm{}}(\mathrm{\Gamma }G))^{K/K_1}.$$

If $`\mathrm{\Gamma }G`$ is compact it carries a unique invariant probability measure. We have the decomposition

$$L^2(\mathrm{\Gamma }G)=\widehat{\underset{\pi \widehat{G}}{}}H(\pi )$$

of the “right regular” representation of $`G`$ on the complex $`L^2`$-space of $`\mathrm{\Gamma }G`$ into isotypic components $`H(\pi )`$. Here $`\pi `$ runs over the unitary dual $`\widehat{G}`$ of $`G`$.

To state the next result let us introduce the following notation. For a topological vector space $`H`$ and linear subspaces $`H_iH`$ the equation

$$H=\overline{\underset{i}{}}H_i$$

by definition means the following:
i) The algebraic direct sum $`\underset{i}{}H_i`$ is a dense subspace of $`H`$.
ii) Every element of $`H`$ can be written as an unconditionally convergent series $`_ih_i`$ with $`h_iH_i`$.

Let $`H(\pi )^{\mathrm{}}`$ be the subspace of smooth vectors in $`H(\pi )`$.

###### Proposition 6.2

If $`\mathrm{\Gamma }G`$ is compact we have

$$\overline{H}^{}(𝔤_1,K_1,C^{\mathrm{}}(\mathrm{\Gamma }G))=\overline{\underset{\pi \widehat{G}}{}}\overline{H}^{}(𝔤_1,K_1,H(\pi )^{\mathrm{}}).$$

Proof A sequence $`(E_i)_{i1}`$ of non-trivial linear subspaces of a Fréchet space $`E`$ is called a Schauder basis of subspaces of $`E`$ if the following conditions hold:
a) Every element $`vE`$ can be written uniquely as a convergent series $`v=_{i=1}^{\mathrm{}}v_i`$ with $`v_iE_i`$.
b) The projections $`EE_i,vv_i`$ resulting from a) are continuous.
If the series in a) converge unconditionally the basis $`(E_i)`$ is called unconditional.

The proof of the following auxiliary result is straightforeward and will be omitted.

###### Lemma 6.2.1

Let $`C^{}`$ be a complex of Fréchet spaces with continuous differentials. Consider closed subcomplexes $`C_i^{}C^{}`$ for $`i1`$ such that for every $`p`$ the sequence $`(C_i^p)_{i1}`$ is an unconditional Schauder basis of subspaces of $`C^p`$. Then we have:

$$\overline{H}^p(C^{})=\overline{\underset{i1}{}}\overline{H}^p(C_i^{}).$$

Using the Sobolev embedding lemma one checks that the subspaces $`H(\pi )^{\mathrm{}}`$ of $`C^{\mathrm{}}(\mathrm{\Gamma }G)=L^2(\mathrm{\Gamma }G)^{\mathrm{}}`$ with $`H(\pi )^{\mathrm{}}0`$ form an unconditional Schauder basis of subspaces of $`C^{\mathrm{}}(\mathrm{\Gamma }G)`$.

Consequently the subcomplexes

$$C^{}(𝔤_1,K_1,H(\pi )^{\mathrm{}})^{K/K_1}$$

of $`C^{}(𝔤_1,K_1,C^{\mathrm{}}(\mathrm{\Gamma }G))^{K/K_1}`$ satisfy the assumptions of the lemma and the assertion of 6.2 follows.  $`\mathrm{}`$

In order to get Kähler–Riemann foliations in the above setting we assume that $`G_1/K_1`$ is a bounded symmetric space. If $`G_1`$ is semisimple then the condition that $`G_1`$ be normal in $`G`$ implies that $`𝔤`$ decomposes into a product $`𝔤=𝔤_1\times 𝔤_2`$. Hence we consider from now on the following setup:
$`G=G_1\times G_2`$ where $`G_1`$ is a connected reductive Lie group in the sense of  0.3.1 with compact center. $`G_2`$ is any Lie group.
$`K=K_1\times K_2`$ where $`K_1`$ is a maximal compact subgroup of $`G_1`$ and $`K_2`$ is a compact subgroup of $`G_2`$.
Let $`\mathrm{\Theta }`$ be the Cartan involution associated to $`K_1`$. We have the $`K_1`$-invariant Cartan decomposition

$$𝔤_1=𝔨_1𝔭_1\text{where}𝔭_1=\{x𝔤|\mathrm{\Theta }(x)=x\}.$$

We assume that $`G_1/K_1`$ carries an invariant complex structure. There is then an element $`z_0`$ in the center of $`𝔨_1`$ such that $`J=\mathrm{ad}z_0|_{𝔭_1}`$ defines a complex structure on $`𝔭`$ which is invariant under $`K_1`$. Hence $`J`$ induces an almost complex structure of $`G_1/K_1`$ which agrees with the given invariant complex structure. The complexification of $`𝔭_1`$ decomposes into the $`\pm i`$-eigenspaces of $`J`$:

$$𝔭_1=𝔭_1^+𝔭_1^{}.$$

Let $`\mathrm{\Gamma }`$ be a cocompact lattice in $`G`$ which acts without fixed points on $`G/K`$. Then

$$X=\mathrm{\Gamma }G/K=\mathrm{\Gamma }G_1\times G_2/K_1\times K_2$$

is a compact manifold. The Riemannian foliation $``$ is given by the images of $`G_1/K_1\times \{g_2K\}`$ for $`g_2KG_2/K_2`$ under the natural projection to $`X`$.

As $`z_0`$ is also in the center of $`𝔨𝔨_1`$, it follows that the complex structure $`J`$ on $`𝔭_1`$ is $`K`$-invariant. Using (7), $`J`$ therefore defines an almost complex structure on $``$. Let $`(,)`$ be any $`K`$-invariant scalar product on $`𝔤/𝔨=𝔭_1𝔤_2/𝔨_2`$ and denote by $`g`$ the corresponding bundle-like metric on $`TX`$, proposition 6.1.

###### Proposition 6.3

$`J`$ defines a complex structure on $``$. The metric $`g`$ is Kähler-bundle like. In particular $``$ is a Kähler–Riemann foliation.

Proof The leaves of $``$ are isomorphic as almost complex manifolds to $`\mathrm{\Gamma }_1G_1/K_1`$ where $`\mathrm{\Gamma }_1`$ is a discrete subgroup of $`G_1`$ which acts without fixed points on $`G_1/K_1`$. It can depend on the leaf in question. Since $`\mathrm{\Gamma }_1G_1/K_1`$ is a complex manifold, the first assertion follows.

As $`(,)`$ is $`K_1`$-invariant, and $`z_0`$ is in the center of $`𝔨_1`$ it follows that

$$g(Jv,w)+g(v,Jw)=0.$$

Hence setting:

$$h(v,w)=g(v,w)+ig(v,Jw)\text{for}v,wT^c$$

we get a hermitian metric on $`T^c`$. The associated $`2`$-form along $``$:

$$\omega _{}(v,w)=\frac{1}{2}g(v,Jw)$$

is closed: Its pullback $`\omega __S`$ to $`G/K`$ is $`G`$-invariant by construction. Hence the restrictions of $`\omega __S`$ to the leaves of $`_S`$ i.e. to $`G_1/K_1\times \{g_2K_2\}`$ are left $`G_1`$-invariant hence closed by a result of E. Cartan. Thus $`d__S\omega __S=0`$ and therefore $`d_{}\omega _{}=0`$.  $`\mathrm{}`$

We will now describe the Hodge structure on the reduced leafwise cohomology of $``$ in terms of the Hodge structure on certain relative Lie algebra cohomologies.

Specializing proposition 6.2 and the isomorphisms (10) to the present context we find:

$$\overline{H}_{}^{}(X,)=\overline{\underset{\pi \widehat{G}}{}}\overline{H}^{}(𝔤_1,K_1,H(\pi )^{\mathrm{}K_2}).$$

Now as $`G`$-representations

$$H(\pi )=M_{\pi ,\mathrm{\Gamma }}V_\pi $$

where $`V_\pi `$ is a fixed representative in the class $`\pi `$ and where $`M_{\pi ,\mathrm{\Gamma }}`$ is the finite dimensional multiplicity space, i.e.

$$M_{\pi ,\mathrm{\Gamma }}=\mathrm{Hom}_G(V_\pi ,L^2(\mathrm{\Gamma }G)).$$

Now since $`\widehat{G}=\widehat{G}_1\times \widehat{G}_2`$ we can take $`V_\pi =V_{\pi _1}\widehat{}V_{\pi _2}`$ if $`\pi =(\pi _1,\pi _2)`$ and hence

$$\overline{H}_{}^{}(X,)=\overline{\underset{\pi _1,\pi _2}{}}M_{\pi ,\mathrm{\Gamma }}\overline{H}^{}(𝔤_1,K_1,(V_{\pi _1}\widehat{}V_{\pi _2}^{K_2})^{\mathrm{}}).$$

We now assume for simplicity that $`G_2`$ is also reductive and that $`K_2`$ is maximal compact in $`G_2`$. A unitary irreducible representation of a reductive group is admissible by a theorem of Harish-Chandra. In particular $`V_{\pi _2}^{K_2}`$ and $`H^{}(𝔤_1,K_1,V_{\pi _1}^{\mathrm{}})`$ are then (clearly) finite-dimensional, so that we get:

$$\overline{H}_{}^{}(X,)=\overline{\underset{\pi _1,\pi _2}{}}M_{\pi ,\mathrm{\Gamma }}H^{}(𝔤_1,K_1,V_{\pi _1}^{\mathrm{}})V_{\pi _2}^{K_2}.$$

Here we have also used that $`V_{\pi _2}^{K_2}`$ consists of smooth vectors. It is clear that in the relative Lie algebra cohomology we can replace $`V_{\pi _1}^{\mathrm{}}`$ by

$$V_{\pi _1,0}=V_{\pi _1}^{\mathrm{}}(V_{\pi _1})_{(K_1)}$$

the intersection being taken with the space $`(V_{\pi _1})_{(K)}`$ of $`K_1`$-finite vectors in $`V_{\pi _1}`$. Then $`V_{\pi _1,0}`$ is a unitary admissible $`(𝔤,K)`$-module in the sense of  II.2.1.

We now assume the following about our $`K`$-invariant scalar product $`(,)`$ on $`𝔤/𝔨=𝔭_1𝔤_2/𝔨_2`$ in order to use results of : Fix a $`G_1`$\- and $`\mathrm{\Theta }`$-invariant non-degenerate symmetric form $`B`$ on $`𝔤_1`$ whose restrictions to $`𝔨_1`$ resp. $`𝔭_1`$ are negative resp. positive definite. Choose $`(,)`$ such that on $`𝔭_1`$ it agrees with $`B`$. We define the Casimir element $`C𝔘(𝔤_1)`$ as in  II.1.3 using $`B`$. It follows from  II.3.1 that

$$H^{}(𝔤_1,K_1,V_{\pi _1,0})=C^{}(𝔤_1,K_1,V_{\pi _1,0})=\mathrm{Hom}_{K_1}(\mathrm{\Lambda }^{}𝔭_1,V_{\pi _1,0})$$

if the central character $`\chi _{\pi _1}`$ is trivial and if the Casimir element $`C`$ acts trivially on $`V_{\pi _1,0}`$.

If one of these conditions is not satisfied, the representation $`V_{\pi _1,0}`$ has no cohomology:

$$H^{}(𝔤_1,K_1,V_{\pi _1,0})=0.$$

See  for a classification of representations with non-zero cohomology.

Until now we have therefore seen the following fact:

###### Theorem 6.4

Under the above conditions we have:

$$\overline{H}_{}^{}(X,)=\overline{\underset{\pi _1,\pi _2}{}}M_{\pi ,\mathrm{\Gamma }}\mathrm{Hom}_{K_1}(\mathrm{\Lambda }^{}𝔭_1,V_{\pi _1,0})V_{\pi _2}^{K_2}.$$

Here the sum runs over $`\pi _1\widehat{G}_1,\pi _2\widehat{G}_2`$ s.t. $`\chi _{\pi _1}=1,d\pi _1(C)=0`$ and $`V_{\pi _2}^{K_2}0`$.

Note that this result generalizes  VII Cor. 3.4 which treats the case $`G_2=1`$, a result essentially due to Matsushima.

The Hodge decomposition of $`\overline{H}_{}^{}(X,)`$ can now be described using representation theory.

###### Theorem 6.5

Under the isomorphism in theorem 6.4 we have

$$H^{pq}=\overline{\underset{\pi _1,\pi _2}{}}M_{\pi ,\mathrm{\Gamma }}\mathrm{Hom}_{K_1}(\mathrm{\Lambda }^p𝔭_1^+\mathrm{\Lambda }^q𝔭_1^{},V_{\pi _1,0})V_{\pi _2}^{K_2}$$

with $`\pi _1,\pi _2`$ as in 6.4.

Proof The assertion is a consequence of the following:

$``$ The Laplacian $`\mathrm{\Delta }_{}`$ on $`𝒜_{}^{}(X)`$ is identified via the isomorphism

$`𝒜_{}^p(X)`$ $`=`$ $`C^p(𝔤_1,K_1,C^{\mathrm{}}(\mathrm{\Gamma }G)^{K_2})`$
$`=`$ $`\overline{{\displaystyle \underset{\pi _1,\pi _2}{}}}M_{\pi ,\mathrm{\Gamma }}C^p(𝔤_1,K_1,V_{\pi _1,0})V_{\pi _2}^{K_2}`$
with the operator

$$\overline{\underset{\pi _1,\pi _2}{}}\mathrm{id}\mathrm{\Delta }_{\pi _1}V_{\pi _2}^{K_2}.$$

Here $`\mathrm{\Delta }_{\pi _1}`$ is the Laplace operator introduced in  II § 2.
$``$ The isomorphism:

$`𝒜_{}^{pq}(X)`$ $`=`$ $`\mathrm{Hom}_{K_1}(\mathrm{\Lambda }^p𝔭_1^+\mathrm{\Lambda }^q𝔭_1^{},C^{\mathrm{}}(\mathrm{\Gamma }G)^{K_2})`$
$`=`$ $`{\displaystyle \underset{\pi _1,\pi _2}{}}M_{\pi ,\mathrm{\Gamma }}\mathrm{Hom}_{K_1}(\mathrm{\Lambda }^p𝔭_1^+\mathrm{\Lambda }^q𝔭_1^{},V_{\pi _1,0})V_{\pi _2}^{K_2}`$
together with proposition 4.2.  $`\mathrm{}`$

One can also describe the Lefschetz operator in representation theoretic terms under the isomorphism of theorem 6.4.

Mathematisches Institut

WWU Münster

Einsteinstr. 62

48149 Münster

Germany

deninge@math.uni-muenster.de

Mathematisches Institut

Universität Düsseldorf

Universitätsstr. 1

40225 Düsseldorf

Germany

singhof@cs.uni-duesseldorf.de


format: text

text:
# Counting occurrences of some subword patterns

## 1. Introduction

Counting the number of words which contain a set of given strings as substrings a certain number of times is a classical problem in combinatorics. This problem can, for example, be attacked using the transfer matrix method (see \[20, Section 4.7\]). In particular, it is a well-known fact that the generating function of such words is always rational. For example, in \[20, Example 4.7.5\] it is shown that the generating function for the number of words in $`[3]^n`$ where neither $`11`$ nor $`23`$ appear as two consecutive digits is given by

$$\frac{3+xx^2}{12xx^2+x^3}.$$

In this paper, we present, in several cases, a complete solution for the problem of the enumeration of words containing a subword pattern (see below for the precise definition) of length $`l`$ exactly $`r`$ times. For example, we find the number of words in $`[3]^n`$ containing the subword pattern $`111`$ exactly $`r`$ times, that is, the number of words which contain $`111`$, $`222`$, and $`333`$ as substrings a total of $`r`$ times.

Régnier and Szpankowski  used a combinatorial approach to study the frequency of occurrences of strings (which they also called a “pattern”) from a given set in a random word, when overlapping copies of the “patterns” are counted separately (see \[18, Theorem 2.1\]). We note that the term “pattern” in  is used to denote an exact string rather than its type with respect to order isomorphism. For example, the “pattern” $`112`$ in  is the actual string $`112`$, whereas in our setting an occurrence of the subword pattern $`112`$ is any substring $`aab`$ of the ambient string with $`a<b`$. Although, in principle, it is possible to deduce our results from the result by Régnier and Szpankowski, our direct derivations are much simpler.

Goulden and Jackson  also consider sequences with distinguished substrings and use the term “pattern of a sequence”. However, their “pattern” is more locally defined than in this paper in that only order relations between adjacent elements of a string are considered, rather than order relations between any pair of elements of a string, as is done in this paper. For example, the pattern “rise, non-rise” (or $`(<,)`$, or $`\pi _1\pi _2`$) as defined in  includes the subword patterns $`121,122,132,231`$ as defined in this paper. However, we show that each of the subword patterns $`121,122,132`$ is avoided by a different number of words (of a given length on a given alphabet) than the other two patterns.

In what follows, we use analytical and combinatorial means to find a complete answer for several cases of counting strings with a specified number of occurrences of certain patterns.

### 1.1. Classical patterns in permutations

Let $`\pi S_n`$ and $`\tau S_m`$ be two permutations. An *occurrence* of $`\tau `$ in $`\pi `$ is a subsequence $`1i_1<i_2<\mathrm{}<i_mn`$ such that $`(\pi (i_1),\mathrm{},\pi (i_m))`$ is order-isomorphic to $`\tau `$. In this context, $`\tau `$ is usually called a *pattern*. We denote the number of occurrences of $`\tau `$ in $`\pi `$ by $`\pi (\tau )`$.

Recently, much attention has been paid to the problem of counting the number of permutations of length $`n`$ containing a given number $`r0`$ of occurrences of a certain pattern $`\tau `$. Most of the authors consider only the case $`r=0`$, thus studying permutations *avoiding* a given pattern. Only a few papers consider the case $`r>0`$, usually restricting themselves to the patterns of length $`3`$. In fact, simple algebraic considerations show that there are only two essentially different cases for $`\tau S_3`$, namely, $`\tau =123`$ and $`\tau =132`$. Noonan  has proved that the number of permutations in $`S_n`$ containing $`123`$ exactly once is given by $`\frac{3}{n}\left(\genfrac{}{}{0pt}{}{2n}{n3}\right)`$. A general approach to the problem was suggested by Noonan and Zeilberger ; they gave another proof of Noonan’s result, and conjectured that the number of permutations in $`S_n`$ containing $`123`$ exactly twice is given by $`\frac{59n^2+117n+100}{2n(2n1)(n+5)}\left(\genfrac{}{}{0pt}{}{2n}{n4}\right)`$ and the number of permutations in $`S_n`$ containing $`132`$ exactly once is given by $`\left(\genfrac{}{}{0pt}{}{2n3}{n3}\right)`$. The first conjecture was proved by Fulmek  and the second conjecture was proved by Bóna in . A general conjecture of Noonan and Zeilberger states that the number of permutations in $`S_n`$ containing $`\tau `$ exactly $`r`$ times is $`P`$-recursive in $`n`$ for any $`r`$ and $`\tau `$. It was proved by Bóna  for $`\tau =132`$. However, as stated in , a challenging question is to describe the number of permutations in $`S_n`$ containing $`\tau S_3`$ exactly $`r`$ times, explicitly for any given $`r`$. Later, Mansour and Vainshtein  suggested a new approach to this problem in the case $`\tau =132`$, which allows one to get an explicit expression for the number of permutations in $`S_n`$ containing $`132`$ exactly $`r`$ times for any given $`r`$.

### 1.2. Generalized patterns in permutations

In , Babson and Steingrímsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. For example, an occurrence of a generalized pattern $`12\text{-}3`$ in a permutation $`\pi =a_1a_2\mathrm{}a_n`$ is a subword $`a_ia_{i+1}a_j`$ of $`\pi `$ such that $`a_i<a_{i+1}<a_j`$.

###### Notation 1.1.

Unfortunately, there is a bit of confusion in denoting classical and generalized patterns. Before generalized patterns were introduced, the hyphens were unnecessary, hence classical patterns (those with all possible hyphens) are often written with no hyphens when generalized patterns are not considered, and with all hyphens when they are. For example, a classical pattern $`123`$ is now denoted by $`1\text{-}2\text{-}3`$ when considered as a generalized pattern (using the notation of ). Unless otherwise stated, all patterns under consideration from now on are generalized patterns.

In  Elizalde and Noy presented the following theorem regarding the distribution of the number of occurrences of any generalized pattern of length $`3`$ without hyphens.

###### Theorem 1.2.

(Elizalde and Noy ) Let $`h(x)=\sqrt{(x1)(x+3)}`$. Then

$`{\displaystyle \underset{n0}{}}{\displaystyle \underset{\pi S_n}{}}x^{\pi (123)}{\displaystyle \frac{t^n}{n!}}`$ $`={\displaystyle \frac{2h(x)e^{\frac{1}{2}(h(x)x+1)t}}{h(x)+x+1+(h(x)x1)e^{h(x)t}}},`$
$`{\displaystyle \underset{n0}{}}{\displaystyle \underset{\pi S_n}{}}x^{\pi (213)}{\displaystyle \frac{t^n}{n!}}`$ $`={\displaystyle \frac{1}{1_0^te^{(x1)z^2/2}𝑑z}},`$
where $`\pi (123)`$ (respectively, $`\pi (213)`$) is the number of occurrences of the *generalized* pattern $`123`$ (respectively, $`213`$) without hyphens in $`\pi `$.

On the other hand, Claesson  gave a complete answer for the number of permutations avoiding a generalized pattern of the form $`xy\text{-}z`$ where $`xyzS_3`$. Later, Claesson and Mansour  presented an algorithm to count the number of permutations containing a generalized pattern of the form $`xy\text{-}z`$ exactly $`r`$ times for any given $`r0`$, where $`xyzS_3`$.

###### Theorem 1.3.

(Claesson and Mansour ) The ordinary generating function for the number of permutations of length $`n`$ avoiding the generalized pattern $`12\text{-}3`$ (or $`23\text{-}1`$) is

$$\underset{k0}{}\frac{x^k}{(1x)(12x)\mathrm{}(1kx)}.$$

The ordinary generating function for the number of permutations of length $`n`$ avoiding the generalized pattern $`2\text{-}13`$ is

$$C(x)=\frac{1\sqrt{14x}}{2x}.$$

The ordinary generating function for the number of permutations of length $`n`$ containing exactly one occurrence of the generalized pattern $`12\text{-}3`$ is

$$\underset{n1}{}\frac{x}{1nx}\underset{k0}{}\frac{kx^{k+n}}{(1x)(12x)\mathrm{}(1(k+n)x)}.$$

The ordinary generating function for the number of permutations of length $`n`$ containing exactly one occurrence of the generalized pattern $`23\text{-}1`$ is

$$\underset{n1}{}\frac{x}{1(n1)x}\underset{k0}{}\frac{kx^{k+n}}{(1x)(12x)\mathrm{}(1(k+n)x)}.$$

The ordinary generating function for the number of permutations of length $`n`$ containing exactly one occurrence of the generalized pattern $`2\text{-}13`$ is

$$\frac{x^3C(x)^7}{1tC(x)^2}.$$

### 1.3. Generalized patterns in words

A *generalized pattern* $`\tau `$ is a (possibly hyphenated) string in $`[\mathrm{}]^m`$ which contains all letters from $`[\mathrm{}]=\{1,\mathrm{},\mathrm{}\}`$. We say that the string $`\sigma [k]^n`$ *contains* a generalized pattern $`\tau `$ exactly $`r`$ times (denoted by $`r=\sigma (\tau )`$) if $`\sigma `$ contains $`r`$ different subsequences isomorphic to $`\tau `$ in which the entries corresponding to consecutive entries of $`\tau `$ not separated by a hyphen must be adjacent. We call the generalized patterns without hyphens *subword patterns*. If $`r=0`$, we say that $`\sigma `$ *avoids* $`\tau `$ and write $`\sigma [k]^n(\tau )`$. Thus, $`[k]^n(\tau )`$ denotes the set of strings in $`[k]^n`$ (i.e., $`n`$-long $`k`$-ary strings) which avoid $`\tau `$. For example, a string $`\pi =a_1a_2\mathrm{}a_n`$ avoids the generalized pattern $`12\text{-}1`$ if $`\pi `$ has no subsequence $`a_ia_{i+1}a_j`$ with $`j>i+1`$ and $`a_i=a_j<a_{i+1}`$.

###### Example 1.4.

Davenport-Schinzel sequences  can be defined in terms of subword pattern avoidance as follows. For any $`d1`$, let $`T_d`$ be the set of all the subword patterns $`\pi =a_1a_2\mathrm{}a_{d+1}[d+1]^{d+1}`$ such that either $`a_{2j}<a_{2j+1}>a_{2j+2}`$ for all $`j`$, or $`a_{2j1}<a_{2j}>a_{2j+1}`$ for all $`j`$. For example, $`T_2=\{121,132,231,212,213,312\}`$. An $`k`$-ary $`n`$-long sequence avoiding the subword pattern $`11`$ (i.e., with no equal consecutive letters) and avoiding all the subword patterns in $`T_d`$ (there are no alternating subwords of length greater than $`d+1`$) is called a Davenport-Schinzel sequence if $`n`$ is maximal.

Let $`f_{\tau ;r}(n,k)`$ be the number of words $`\sigma [k]^n`$ such that $`\sigma (\tau )=r`$. Denote the corresponding bivariate generating function by $`F_\tau (x,y;k)`$, in other words,

$$F_\tau (x,y;k)=\underset{n0}{}\underset{r0}{}f_{\tau ;r}(n,k)x^ny^r.$$

Burstein  gave a complete answer for the numbers $`f_{\tau ;0}(n,k)`$ where $`\tau `$ is a $`3`$-letter classical pattern. Later, Burstein and Mansour  presented a complete answer for the number $`f_{\tau ;0}(n,k)`$ where $`\tau `$ is a generalized pattern of length $`3`$ (a word of length $`3`$).

In this paper, we present a complete answer for several cases of $`f_{\tau ;r}(n,k)`$ where $`\tau `$ is a subword pattern of length $`l`$ (which is the analogue of the results by Elizalde and Noy in ). In particular, we find a complete answer for the case $`l=3`$.

## 2. Counting a subword pattern of length $`l`$

In this section we find $`F_\tau (x,y;k)`$ for several cases of $`\tau `$. Burstein and Mansour  found $`F_\tau (x,y;k)`$ for the subword pattern $`\tau =11\mathrm{}1[1]^l`$ and proved the following theorem.

###### Theorem 2.1.

(Burstein and Mansour \[6, Th. 2.1\]) Let $`\tau =11\mathrm{}1[1]^l`$ be a subword pattern. Then

$$F_\tau (x,y;k)=\frac{1+(1y)x_{j=0}^{l2}(kx)^j(1y)(k1)_{d=2}^{l1}x^d_{j=0}^{l1d}(kx)^j}{1(k1+y)x(k1)(1y)(1x^{l2})\frac{x^2}{1x}}.$$

### 2.1. The subword pattern $`\tau =11\mathrm{}12`$

Let $`\tau =11\mathrm{}12[2]^l`$ be a subword pattern. Define $`d_{\tau ;r}(n,k)`$ to be the number of words $`\beta [k]^n`$ such that $`(\beta ,k+1)`$ contains $`\tau `$ exactly $`r`$ times, and denote the corresponding generating function by $`D_\tau (x,y;k)=\underset{n,r0}{}d_{\tau ;r}(n,k)x^ny^r`$. Let us find a recurrence for $`F_\tau `$.

Let $`\sigma [k]^n`$ ($`k2`$), with $`\sigma (\tau )=r`$, contain exactly $`d`$ copies of the letter $`k`$. If $`d=0`$, then $`\sigma [k1]^n`$ and $`\sigma (\tau )=r`$. If $`d1`$, then $`\sigma =\sigma _1k\sigma _2`$, where $`\sigma _1[k1]^{n_1}`$, $`\sigma _2[k]^{n_2}`$, $`n_1+n_2+1=n`$ and $`(\sigma _1,k)(\tau )+\sigma _2(\tau )=r`$. Taking generating functions, we see that the above translates into

$$F_\tau (x,y;k)=F_\tau (x,y;k1)+xD_\tau (x,y;k1)F_\tau (x,y;k),$$

or, equivalently,

$$F_\tau (x,y;k)=\frac{F_\tau (x,y;k1)}{1xD_\tau (x,y;k1)}.$$

Let us now find the recurrence for $`D_\tau `$. Let $`\sigma [k]^n`$ be such that $`(\sigma ,k+1)`$ contains $`\tau `$ exactly $`r`$ times, and has exactly $`d`$ letters $`k`$. Then $`\sigma =\sigma _1k\sigma _2k\mathrm{}k\sigma _dk\sigma _{d+1}`$ for some $`\sigma _i[k1]^{n_i}`$, $`1id+1`$, where $`n_1+\mathrm{}+n_{d+1}=nd`$ and

$$(\sigma _1,k)(\tau )+\mathrm{}+(\sigma _d,k)(\tau )+(\sigma _{d+1},k+1)(\tau )+\delta (\sigma \text{ ends on }l1k\text{’s})=r.$$

Taking generating functions, we obtain

$$\begin{array}{c}D_\tau (x,y;k)=\underset{d=0}{\overset{l2}{}}x^dD_\tau ^{d+1}(x,y;k1)\hfill \\ \hfill +\underset{d=l1}{\overset{\mathrm{}}{}}x^d(D_\tau ^{d+1}(x,y;k1)D_\tau ^{(d+1)(l1)}(x,y;k1)\\ \hfill +yD_\tau ^{(d+1)(l1)}(x,y;k1)),\end{array}$$

which, after summing over $`d`$, yields

$$D_\tau (x,y;k1)=\frac{(1x^{l1}(1y))D_\tau (x,y;k1)}{1xD_\tau (x,y;k1)}.$$

These two recurrences, together with $`D_\tau (x,y;0)=F_\tau (x,y;0)=1`$ and induction on $`k`$, yield the following theorem.

###### Theorem 2.2.

Let $`\tau =11\mathrm{}12[2]^l`$ be a subword pattern such that $`l1`$; then

$$F_\tau (x,y;k)=\frac{1y}{1x^{2l}y+x^{2l}(1x^{l1}(1y))^k}.$$

###### Example 2.3.

(see Burstein and Mansour \[6, Th. 3.10\]) Letting $`l=3`$ and $`y=0`$ in Theorem 2.2, we get that the generating function for the number of words in $`[k]^n`$ avoiding the subword pattern $`112`$ is given by

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

In the special case of $`l=3`$, we get from Theorem 2.2 the following result.

###### Corollary 2.4.

The generating function for the number of words in $`[2]^n`$ containing the subword pattern $`112`$ exactly $`r`$ times is given by

$$\frac{x^{3r}}{(1x)^{r+1}(1xx^2)^{r+1}}.$$

###### Proof.

Let $`\tau =112`$ be a subword pattern. It is easy to see that a word $`\sigma [2]^n`$ with $`\sigma (\tau )=r`$ must have the form $`\sigma =\sigma _1\tau \sigma _2\tau \mathrm{}\tau \sigma _{r+1}`$, for some $`\sigma _1,\mathrm{},\sigma _{r+1}[2]^n(\tau )`$. Now, from Example 2.3 with $`k=2`$, we have that $`F_\tau (x;2)=\frac{1}{(1x)(1xx^2)}`$, hence the result follows. ∎

### 2.2. The subword pattern $`\tau =211\mathrm{}112`$

Let $`\tau =211\mathrm{}112[2]^l`$ be a subword pattern. We define $`d_\tau (n,r;k)`$ to be the number of words $`\beta [k]^n`$ such that $`(k+1,\beta ,k+1)`$ contains $`\tau `$ exactly $`r`$ times, and denote the corresponding generating function by $`D_\tau (x,y;k)`$. Let $`\sigma [k]^n`$ such that $`\sigma (\tau )=r`$, and such that $`\sigma `$ contains $`d`$ occurrences of the letter $`k`$. For $`d=0`$, the generating function for the number of such words $`\sigma `$ is given by $`F_\tau (x,y;k1)`$, and for $`d1`$, by $`x^dF_\tau ^2(x,y;k1)D_\tau ^{d1}(x,y;k1)`$ (since in that case $`\sigma =\sigma _0k\sigma _1k\mathrm{}k\sigma _{d1}k\sigma _d`$, where all $`\sigma _i[k1]^{n_i}`$, $`n_i=nd`$, and $`\sigma (\tau )=\sigma _0(\tau )+(k,\sigma _1,k)(\tau )+\mathrm{}+(k,\sigma _{d1},k)(\tau )+\sigma _d(\tau )`$). Hence, if we sum over all $`d0`$, we get

$$F_\tau (x,y;k)=F_\tau (x,y;k1)+\frac{xF_\tau ^2(x,y;k1)}{1xD_\tau (x,y;k1)}.$$

On the other hand, the word $`(k+1,\beta ,k+1)`$, with $`\beta `$ as above, contains an occurrence of $`\tau `$ involving the two letters $`k+1`$ if and only if $`\beta `$ is a constant string of length $`l2`$, otherwise, $`(k+1,\beta ,k+1)(\tau )=\beta (\tau )`$. Taking generating functions, we obtain

$$D_\tau (x,y;k)=kx^{l2}y+F_\tau (x,y;k)kx^{l2}.$$

Therefore, using the initial conditions $`F_\tau (x,y;0)=D_\tau (x,y;0)=1`$ and induction on $`k`$, we get the following theorem.

###### Theorem 2.5.

Let $`\tau =211\mathrm{}112[2]^l`$ be a subword pattern and $`l2`$, then

$$F_\tau (x,y;k)=\frac{1}{1xx_{j=0}^k\frac{1}{1+jx^{l1}(1y)}}.$$

###### Example 2.6.

(Burstein and Mansour \[6, Th. 3.12\]) Letting $`l=3`$ and $`y=0`$ in Theorem 2.5, we get that the generating function for the number of words in $`[k]^n`$ avoiding the subword pattern $`212`$ is given by

$$\frac{1}{1xx_{j=0}^{k1}\frac{1}{1+jx^2}}.$$

### 2.3. The subword pattern $`\tau =m\tau ^{}m`$

###### Theorem 2.7.

Let $`\tau =m\tau ^{}m[m]^l`$ be a subword pattern, where $`\tau ^{}`$ does not contain $`m`$. Then for $`km`$,

$$F_\tau (x,y;k)=\frac{1}{1(m1)xx_{j=m1}^{k1}\frac{1}{1+\left(\genfrac{}{}{0pt}{}{j}{m1}\right)x^{l1}(1y)}}.$$

###### Proof.

Let $`\sigma [k]^n`$. The generating function for the number of words $`\sigma `$ which do not contain $`m`$ and contain $`\tau `$ exactly $`r`$ times is given by $`F_\tau (x,y;k1)`$. Now assume that the leftmost $`m`$ in $`\sigma `$ is at position $`i`$. Then $`\sigma =\sigma _1m\sigma _2`$ and $`\sigma (\tau )=\sigma _1(\tau )+(m,\sigma _2)(\tau )`$, so the generating function for the number of such words $`\sigma `$ is given by $`xF_\tau (x,y;k1)D_\tau (x,y;k)`$, where $`D_\tau (x,y;k)`$ is the generating function for the number of words $`\sigma [k]^n`$ such that $`(m,\sigma )`$ contains $`\tau `$ exactly $`r`$ times. Therefore,

$$F_\tau (x,y;k)=F_\tau (x,y;k1)+xF_\tau (x,y;k1)D_\tau (x,y;k).$$

On the other hand, let $`\sigma ^{}=(m,\sigma )[k]^{n+1}`$. If $`\sigma `$ does not contain $`m`$, then the generating function for the number of such $`\sigma `$ is given by $`F_\tau (x,y;k1)`$. Otherwise, let $`i`$ be the position of the leftmost letter $`m`$ and let $`\sigma |_i`$ be the left prefix of $`\sigma `$ of length $`i`$, then the generating function for these words is given by $`x\left(F_\tau (x,y;k1)x^{l2}\left(\genfrac{}{}{0pt}{}{k1}{m1}\right)\right)D_\tau (x,y;k)`$ if $`(m,\sigma |_i)`$ is not order-isomorphic to $`\tau `$, or by $`xyx^{l2}\left(\genfrac{}{}{0pt}{}{k1}{m1}\right)D_\tau (x,y;k)`$ if $`(m,\sigma |_i)`$ is order-isomorphic to $`\tau `$. Therefore,

$$\begin{array}{cc}\hfill D_\tau (x,y;k)& =F_\tau (x,y;k1)+x\left(F_\tau (x,y;k1)x^{l2}\left(\genfrac{}{}{0pt}{}{k1}{m1}\right)\right)D_\tau (x,y;k)\hfill \\ & +yx^{l1}\left(\genfrac{}{}{0pt}{}{k1}{m1}\right)D_\tau (x,y;k).\hfill \end{array}$$

Hence, from the above two equations, we obtain

$$F_\tau (x,y;k)=\frac{\left(1+x^{l1}\left(\genfrac{}{}{0pt}{}{k1}{m1}\right)(1y)\right)F_\tau (x,y;k1)}{1+x^{l1}\left(\genfrac{}{}{0pt}{}{k1}{m1}\right)(1y)xF_\tau (x,y;k1)},$$

so, by induction on $`k`$ with the initial condition $`F_\tau (x,y;m1)=\frac{1}{1(m1)x}`$, we get the desired result. ∎

###### Example 2.8.

Applying Theorem 2.7 to the subword patterns $`2112`$ and $`3123`$, we get

$`F_{2112}(x,y;k)`$ $`={\displaystyle \frac{1}{1xx_{j=0}^{k1}\frac{1}{1+jx^3(1y)}}},`$
$`F_{3123}(x,y;k)`$ $`={\displaystyle \frac{1}{12xx_{j=2}^{k1}\frac{1}{1+j(j1)x^3(1y)/2}}}.`$
###### Definition 2.9.

We say that the patterns $`\beta `$ and $`\gamma `$ are *strongly Wilf-equivalent*, or are in the same *strong Wilf class*, if the number of words in $`[k]^n`$ containing $`\beta `$ exactly $`r`$ times is the same as the number of words in $`[k]^n`$ containing $`\gamma `$ exactly $`r`$ times, for any $`r0`$.

By Theorem 2.7 and the symmetry operations “reversal” and “complement,” we immediately get the following corollary.

###### Corollary 2.10.

The subword patterns $`1121`$ and $`1221`$ are in the same strong Wilf class.

### 2.4. The subword pattern $`\tau =m\tau ^{}(m+1)`$

Let $`\tau =m\tau ^{}(m+1)`$ be a subword pattern, where $`\tau ^{}`$ does not contain $`m`$ or $`m+1`$. Note that $`\tau `$ is in the same symmetry class as $`r(c(\tau ))=1r(c(\tau ^{}))2`$. This case is treated in a similarl manner as the case of $`\tau =m\tau ^{}m`$. As a result, we obtain the theorem below.

###### Theorem 2.11.

Let $`\tau =m\tau ^{}(m+1)[m+1]^l`$ be a subword pattern, where $`\tau ^{}`$ does not contain $`m`$ or $`m+1`$. Then for $`km`$,

$$F_\tau (x,y;k)=\frac{1}{1(m1)xx_{i=m2}^{k2}_{j=m2}^i\left(1\left(\genfrac{}{}{0pt}{}{j}{m1}\right)x^{l1}(1y)\right)}.$$

## 3. Subword patterns of length $`3`$

The symmetry class representatives of $`3`$-letter subword patterns are $`111`$, $`112`$, $`212`$, $`123`$, $`213`$. In the current subsection, we find explicit formulas for $`F_\tau (x,y;k)`$ for each of these representatives $`\tau `$. Theorem 2.1 yields the answer for the first class.

###### Theorem 3.1.

Let $`\tau =111`$ be a subword pattern. Then, for all $`k0`$, we have

$$F_\tau (x,y;k)=\frac{1+x(1+x)(1y)}{1(k1+y)x(k1)(1y)x^2}.$$

Theorems 2.2 and 2.5 contain already the answers for the second and the third classes, respectively. Let us summarize the corresponding results in the theorem below.

###### Theorem 3.2.

Let $`112`$ and $`212`$ be subword patterns. For $`k0`$,

$$\begin{array}{cc}\hfill F_{112}(x,y;k)& =\frac{1y}{1\frac{1}{x}y+\frac{1}{x}(1x^2(1y))^k},\hfill \\ \hfill F_{212}(x,y;k)& =\frac{1}{1xx_{j=0}^k\frac{1}{1jx^2(1y)}}.\hfill \end{array}$$

Now let us find the generating function for the fourth class, $`F_\tau (x,y;k)`$ where $`\tau =123`$ is a subword pattern. Let $`D_\tau (x,y;k)`$ be the generating function for the number of words $`\sigma [k]^n`$ such that $`(\sigma ,k+1)`$ contains the subword pattern $`123`$ exactly $`r`$ times. Suppose a word $`\sigma [k]^n(\tau )`$ has exactly $`d`$ letters $`k`$. Then $`\sigma =\sigma _0k\sigma _1k\mathrm{}k\sigma _d`$, where all $`\sigma _i[k1]^n`$, and any occurrence of $`\tau `$ in $`\sigma `$ must be either in $`(\sigma _i,k)`$ for some $`i=0,1,\mathrm{},d1`$, or in $`\sigma _d`$. Therefore, the generating function for the number of such words $`\sigma `$ is $`(xD_\tau (x,y;k1))^dF_\tau (x,y;k1)`$, so

$$F_\tau (x,y;k)=\underset{d0}{}(xD_\tau (x,y;k1))^dF_\tau (x,y;k1).$$

On the other hand, suppose $`\sigma [k]^n`$ is counted by $`D_\tau (x,y;k)`$. Then $`(\sigma ,k+1)=\sigma _0k\sigma _1k\mathrm{}k\sigma _dk+1`$ (where $`\sigma _i[k1]^n`$ for all $`i`$) contains the pattern $`\tau `$ exactly $`r`$ times. If $`d=0`$, then $`\sigma [k1]^n`$. If $`d1`$, there are several possibilities. If $`\sigma _d\mathrm{}`$ or $`\sigma _d=\sigma _{d1}=\mathrm{}`$, then all occurrences of the pattern $`\tau `$ in $`(\sigma ,k+1)`$ are in $`(\sigma _i,k)`$ for some $`i=0,1,\mathrm{},d1`$, or in $`(\sigma _d,k+1)`$. If $`\sigma _d=\mathrm{}`$ and $`\sigma _{d1}\mathrm{}`$, then there is one extra occurrence of $`\tau `$ since $`(\sigma ,k+1)`$ ends by $`(a,k,k+1)`$ for some $`a<k`$. Taking generating functions, we obtain

$$\begin{array}{cc}\hfill D_\tau (x,y;k)=& D_\tau (x,y;k1)\hfill \\ & +\underset{d1}{}x^dD_\tau ^d(x,y;k1)(D_\tau (x,y;k1)1)\hfill \\ & +\underset{d1}{}x^dD_\tau ^{d1}(x,y;k1))\hfill \\ & +\underset{d1}{}x^dyD_\tau ^{d1}(x,y;k1)(D_\tau (x,y;k1)1).\hfill \end{array}$$

Hence,

$$\begin{array}{cc}\hfill F_\tau (x,y;k)& =\frac{F_\tau (x,y;k1)}{1xD_\tau (x,y;k1)},\hfill \\ \hfill D_\tau (x,y;k)& =\frac{(1x+xy)D_\tau (x,y;k1)+x(1y)}{1xD_\tau (x,y;k1)}.\hfill \end{array}$$

Together with $`F_\tau (x,y;0)=D_\tau (x,y;0)=1`$, $`F_\tau (x,y;1)=D_\tau (x,y;1)=1/(1x)`$ and induction on $`k`$, this yields the following result.

###### Theorem 3.3.

Let $`\tau =123`$ be a subword pattern. For all $`k2`$, we have

$$F_\tau (x,y;k)=\frac{1}{1kx_{j=3}^k(x)^j\left(\genfrac{}{}{0pt}{}{k}{j}\right)(1y)^{j/2}U_{j3}(y)},$$

where $`U_0(y)=U_1(y)=1`$, $`U_{2n}(y)=(1y)U_{2n1}(y)U_{2n2}(y)`$, and $`U_{2n+1}(y)=U_{2n}(y)U_{2n1}(y)`$. Furthermore, the generating function for $`U_n(y)`$ is given by

$$\underset{n0}{}U_n(y)z^n=\frac{1+z+z^2}{1+(1+y)z^2+z^4}.$$

Finally, Theorem 2.11 for $`l=3`$ and $`m=2`$ provides already the answer for the last class. The corresponding result is summarized below.

###### Theorem 3.4.

Let $`\tau =213`$ be a subword pattern. Then for all $`k2`$, we have

$$F_\tau (x,y;k)=\frac{1}{1xx_{i=0}^{k2}_{j=0}^i(1jx^2(1y))}.$$

## 4. Further results

We say that a subword pattern $`\tau [m]^l`$ is *primitive* if any two distinct occurrences of $`\tau `$ may overlap by at most one letter. For example, the subword patterns $`112`$, $`121`$, $`122`$, $`132`$, $`211`$, $`212`$, $`213`$, $`221`$, $`231`$, and $`312`$ are all the primitive patterns of length three.

###### Theorem 4.1.

Let $`\tau ,\tau ^{}[m]^l`$ be two primitive subword patterns such that there exists a permutation $`\mathrm{\Phi }S_l`$ with $`\mathrm{\Phi }(1)=1`$, $`\mathrm{\Phi }(l)=l`$ and $`\tau ^{}=\mathrm{\Phi }\tau `$. In other words, $`\tau `$ and $`\tau ^{}`$ have the same supply of each letter, the same first letter and the same last letter. Then $`\tau `$ and $`\tau ^{}`$ are in the same strong Wilf class.

###### Proof.

Let $`\sigma [k]^n`$ contain $`\tau `$ exactly $`r`$ times. Since $`\tau `$ is a primitive subword pattern, we can define a function $`f`$ which changes any occurrence of $`\tau `$ in $`\sigma `$ to an occurrence of $`\tau ^{}`$. It is easy to see from the definition of primitive patterns that $`f`$ is a bijection, hence the theorem follows. ∎

An immediate corollary is the following.

###### Corollary 4.2.

The subword patterns $`1232`$ and $`1322`$ are in the same strong Wilf class.

###### Theorem 4.3.

All primitive subword patterns $`\tau [m]^l`$ such that $`\tau (1)=a`$ and $`\tau (l)=b`$, where $`a<b`$, are in the same strong Wilf class.

###### Proof.

Similarly as in the proof of Theorem 2.7, we get

$$F_\tau (x,y;k)=F_\tau (x,y;k1)+xF_\tau (x,y;k1)D_\tau (x,y;k;a),$$

where $`D_\tau (x,y;k;h)`$ is the generating function for the number of words $`\sigma [k]^n`$ such that $`(h,\sigma )`$ contains $`\tau `$ exactly $`r`$ times.

Now let us consider the case $`h=a+p(ba)`$. Let $`\sigma =(\sigma ^{},h+ba,\sigma ^{\prime \prime })`$, where $`\sigma ^{}`$ is a word on the letters in $`[k]`$ which does not contain $`h+ba`$. Using the fact that $`\tau `$ is a primitive subword pattern, we get

$$\begin{array}{cc}& D_\tau (x,y;k;h)=D_\tau (x,y;k1;h)\hfill \\ & +x^{l1}y\left(\genfrac{}{}{0pt}{}{h1}{a1}\right)\left(\genfrac{}{}{0pt}{}{k(h+ba)}{mb}\right)D_\tau (x,y;k;h+ba)\hfill \\ & +x\left[F_\tau (x,y;k1)x^{l2}\left(\genfrac{}{}{0pt}{}{h1}{a1}\right)\left(\genfrac{}{}{0pt}{}{k(h+ba)}{mb}\right)\right]D_\tau (x,y;k;h+ba).\hfill \end{array}$$

Hence, by induction on $`p`$ and $`k`$, using $`F_\tau (x,y;m1)=1/(1(m1)x)`$ and $`D_\tau (x,y;k;h)=0`$ for $`h>k`$, we get the desired result. ∎

Using the proof of the above theorem, we get the following generalization.

###### Corollary 4.4.

Let $`\tau ,\tau ^{}[m]^l`$ be two primitive subword patterns such that $`\tau (1)=\tau ^{}(1)=a`$ and $`\tau (l)=\tau ^{}(l)=b`$, where $`a<b`$. Then the subword patterns

$$\underset{p}{\underset{}{aa\mathrm{}a}}\tau \underset{p}{\underset{}{b\mathrm{}bb}}\text{ and }\underset{p}{\underset{}{aa\mathrm{}a}}\tau ^{}\underset{p}{\underset{}{b\mathrm{}bb}}$$

are in the same strong Wilf class.

Theorem 4.3 implies as well the following corollary.

###### Corollary 4.5.

1. The subword patterns $`1132`$, $`1232`$, $`1322`$, and $`1332`$ are in the same strong Wilf class.
2. The subword patterns $`1432`$ and $`1342`$ are in the same strong Wilf class.

###### Theorem 4.6.

Let $`12\tau 1[m]^{l+3}`$ be a primitive subword pattern, and let $`\tau ^{}`$ be the same pattern $`\tau `$ with $`1`$ replaced by $`2`$. Then the subword patterns $`12\tau 13`$ and $`12\tau ^{}23`$ are in the same strong Wilf class.

###### Proof.

If $`\sigma [k]^n`$ contains $`12\tau 13`$ exactly $`r`$ times, then we define $`\sigma ^{}`$ as follows. If $`(\sigma _i,\mathrm{},\sigma _{i+l+3})`$ is an occurrence of $`12\tau 13`$, then we define $`\sigma _{i+j}^{}=\sigma _i+1`$ for all $`j`$ such that $`\sigma _{i+j}=\sigma _i`$. The function $`f`$ defined by $`f(\sigma )=\sigma ^{}`$ is a bijection since $`12\tau 1`$ is a primitive subword pattern. ∎

###### Corollary 4.7.

The subword patterns $`1213`$ and $`1223`$ are in the same strong Wilf class.

Acknowledgement

The authors would like to thank the anonymous referee for bringing several references, particularly , to their attention. The final version of this paper was written while the second author (T.M.) was visiting University of Haifa, Israel in January 2003. He thanks the HIACS Research Center and the Caesarea Edmond Benjamin de Rothschild Foundation Institute for Interdisciplinary Applications of Computer Science for financial support, and professor Alek Vainshtein for his generosity.