# Are generic dynamical properties stable under composition with rotations?

Jozef Bobok  ,  Jernej Činč  ,  Piotr Oprocha  and  Serge Troubetzkoy
Department of Mathematics of FCE, Czech Technical University in Prague,
Thákurova 7, 166 29 Prague 6, Czech Republic<EMAIL_ADDRESS>AGH
University of Science and Technology, Faculty of Applied Mathematics, al.
Mickiewicza 30, 30-059 Kraków, Poland. – and – Centre of Excellence
IT4Innovations - Institute for Research and Applications of Fuzzy Modeling,
University of Ostrava, 30. dubna 22, 701 03 Ostrava 1, Czech Republic
<EMAIL_ADDRESS>AGH University of Science and Technology, Faculty of
Applied Mathematics, al. Mickiewicza 30, 30-059 Kraków, Poland. – and – Centre
of Excellence IT4Innovations - Institute for Research and Applications of
Fuzzy Modeling, University of Ostrava, 30. dubna 22, 701 03 Ostrava 1, Czech
Republic<EMAIL_ADDRESS>Aix Marseille Univ, CNRS, I2M, Marseille, France
postal address: I2M, Luminy, Case 907, F-13288 Marseille Cedex 9, France
<EMAIL_ADDRESS>
###### Abstract.

In this paper we provide a detailed topological and measure-theoretic study of
Lebesgue measure-preserving circle maps that are rotated with inner and outer
rotations which are independent of each other. In particular, we analyze the
stability of the locally eventually onto and measure-theoretic mixing
properties.

###### Key words and phrases:

Circle map, Lebesgue measure-preserving, rotation, generic property

###### 2020 Mathematics Subject Classification:

37E05, 37C20

##  1\. Introduction

We study the structure of Lebesgue measure-preserving maps of the circle,
these are one-dimensional versions of volume-preserving maps, or more broadly,
conservative dynamical systems; ergodic maps preserving Lebesgue measure are
the most fundamental examples of maps having a unique physical measure. In
recent years there has been extensive interest in piecewise linear Lebesgue
measure-preserving one dimensional case, the most classical example being
interval exchange transformations (IETs). Ergodic properties of the Lebesgue
measure for IETs are of prime interest. Keane proved the minimality of most
IETs and showed that there is a large class of IETs which are not uniquely
ergodic but Lebesgue measure is ergodic [17],[18], thus initiating questions
about typical properties of IETs or more generally Lebsegue measure-preserving
transformations. These questions have attracted much attention, for example
Masur [20] and Veech [26] proved that typical minimal IETs are uniquely
ergodic. This line of research more recently culminated in the work of Avila
and Forni [5], who proved among other things that typical IETs are weakly
mixing.

The question we study in this article is the following; we consider a
dynamical property and ask for which circle maps $f$ satisfying this property,
when we compose $f$ with circle rotations, this property still holds for the
resulting map $g:=r_{\alpha}\circ f\circ r_{\beta}$.

Such a question was studied for example in [4]. The authors showed that for
any interval exchange transformation $T$ the map $T\circ r_{\beta}$ is
uniquely ergodic for almost every $\beta$. This nice result motivated us to
initiate our study.

We place ourselves in the framework of continuous Lebesgue measure-preserving
maps of the circle, denoted $C_{\lambda}(\mathbb{S}^{1})$. This setting is in
some sense complementary to the setting of IETs: except for rotations, IETs
are invertible piecewise monotone but not continuous while maps in
$C_{\lambda}(\mathbb{S}^{1})$ are not invertible and not piecewise monotone
but continuous. We define an operator
$T_{\alpha,\beta}:C_{\lambda}(\mathbb{S}^{1})\mapsto
C_{\lambda}(\mathbb{S}^{1})$ by $T_{\alpha,\beta}(f)=r_{\alpha}\circ f\circ
r_{\beta}.$ A more precise version of the question we ask is:

> Given a dynamical property, how large is the set of $f\in
> C_{\lambda}(\mathbb{S}^{1})$ such that this property holds for all
> $T_{\alpha,\beta}(f)$.

This question indeed makes sense because $C_{\lambda}(\mathbb{S}^{1})$ is
closed under the operation $T_{\alpha,\beta}$. This is not true anymore in the
setting of circle maps that preserve a non-atomic invariant measure
$\mu\neq\lambda$ with full support. It is also not true in the set of all
continuous circle maps with dense set of periodic points, this result will be
presented in a separate article which is under preparation.

Furthermore, we note that in this paper we do not study the weaker version of
the above question when all is replaced by almost all.

We begin by studying topological dynamical properties. The strongest
topological dynamical property in our setting is the locally eventually onto
(leo) property (in the literature sometimes referred to by topological
exactness). Our first result, which was surprising for us, is

######  Theorem 1.

There is an open dense set of maps $\mathcal{O}\subset
C_{\lambda}(\mathbb{S}^{1})$ such that:

  1. (1)

each $f\in\mathcal{O}$ is leo.

  2. (2)

for each pair $\alpha,\beta\in[0,1)$ and each $f\in\mathcal{O}$ the map
$T_{\alpha,\beta}(f)\in\mathcal{O}$.

According to the usual hierarchy of topological dynamical properties, every
map in $\mathcal{O}$ is also topologically mixing, topologically weakly
mixing, totally transitive and transitive.

Notice that this theorem is stronger than the above mentioned result for
interval exchange transformations [4] in the sense that it holds for all
$\alpha,\beta$, but weaker in the sense that it does not hold for all maps
$f\in C_{\lambda}(\mathbb{S}^{1})$. We show that such a statement can not hold
for all $f\in C_{\lambda}(\mathbb{S}^{1})$; in Section 3 we give an explicit
example of a map $f\in C_{\lambda}(\mathbb{S}^{1})$ for which
$T_{\alpha,\beta}(f)$ is not transitive for an open set of $\alpha,\beta$
(Example 6). This example also shows that
$C_{\lambda}(\mathbb{S}^{1})\setminus\mathcal{O}$ must be nonempty even in the
almost all version of the question.

Next we ask the same question in the measure-theoretic framework. In [10] we
showed that there is a dense set of non-ergodic maps in
$C_{\lambda}(\mathbb{S}^{1})$, thus we can not have a nonempty open set of
maps satisfying nice mixing properties for all $\alpha,\beta$. None the less
we obtain the following (optimal) result.

######  Theorem 2.

There is a dense $G_{\delta}$ subset $\mathcal{G}$ of
$C_{\lambda}(\mathbb{S}^{1})$ such that

  1. (1)

each $g\in\mathcal{G}$ is weakly mixing with respect to $\lambda$, and

  2. (2)

for each pair $\alpha,\beta\in[0,1)$ and each $f\in\mathcal{G}$ the map
$T_{\alpha,\beta}(f)\in\mathcal{G}$.

Another aim of our research is to understand natural conditions when
topological dynamical properties imply the corresponding measure theoretical
properties. There is a nice survey article by Glasner and Weiss with the
following description of the interplay between measure theoretic and
topological dynamics: The two sister branches of the theory of dynamical
systems called ergodic theory (or measurable dynamics) and topological
dynamics $\dots$ describe different but parallel notions in their respective
theories and the surprising fact is that many of the corresponding results are
rather similar [14]. The next two results are of this type in our particular
context. The smoothness assumptions in the next two theorems come directly
from the paper of Li and Yorke [19] and Bowen [12] respectively.

######  Theorem 3.

Let $f\in C_{\lambda}(\mathbb{S}^{1})$ be a piecewise $C^{2}$ map with slope
strictly greater than $1$. Then $f$ is transitive if and only if
$(f,\mathbb{S}^{1},\mathcal{B},\lambda)$ is ergodic.

It is well known that measure-theoretic exactness implies measure-theoretic
strong mixing, and since $\lambda$ is positive on open sets this implies
topological mixing. The next result is a partial converse to this, and is an
important ingredient of the proof of Theorem 2.

######  Theorem 4.

Let $f\in C_{\lambda}(\mathbb{S}^{1})$ be a piecewise $C^{2}$ topological
mixing map. Then $(f,\mathbb{S}^{1},\mathcal{B},\lambda)$ is measure-
theoretically exact (thus also strongly and weakly mixing).

From the proofs it is immediate that Theorems 3 and 4 also hold in the setting
of $C_{\lambda}([0,1])$, which we also could not find in the literature.

To prove Theorem 1 we prove several intermediary results of independent
interest on special dense classes of maps in $C_{\lambda}(\mathbb{S}^{1})$.
The following result is a corollary of the technical Lemma 14. Again notice
that if $f$ satisfies the assumptions of the corollary then
$T_{\alpha,\beta}(f)$ verifies them for all $\alpha,\beta\in[0,1)$.

######  Corollary 5.

If a piecewise affine Lebesgue measure-preserving circle map has different
critical values and slope strictly greater than $4$ then it is leo.

Another important ingredient in the proof of Theorem 1 is the complete
geometric description of periodic arcs for sufficiently expanding piecewise
monotone maps in $C_{\lambda}(\mathbb{S}^{1})$ (Theorem 10).

All our techniques are a priori of one-dimensional nature, but we wonder if
similar results still hold in higher dimensions. In particular, it would be
interesting to know which dynamical properties hold generically or on open
sets of continuous non-invertible volume preserving maps, and if they commute
with rotations on higher dimensional tori.

Dynamical and topological properties of typical continuous Lebesgue measure-
preserving maps in the one dimensional setting have been studied in [8, 9, 10,
11, 13, 25]. In particular, in the setting of $C_{\lambda}(\mathbb{S}^{1})$ we
completely characterized the sets of periodic points of typical maps [10] and
showed in [11] a surprising result that a strong version of shadowing
property, called the s-limit shadowing property, is generic. We have not
investigated if these properties commute with rotations.

##  2\. Preliminaries

###  2.1. Notation and background material

Let $\mathbb{N}:=\\{1,2,3,\ldots\\}$ denote the set of natural numbers and
$\mathbb{Z}:=\\{\ldots,-1,0,1,\ldots\\}$ the set of integers. We denote by
$\mathbb{S}^{1}$ the unit circle. For sets $A,A^{\prime}\in\mathbb{S}^{1}$ we
use notation $\mathrm{dist}(A,A^{\prime})$ to denote the Euclidean distance on
$\mathbb{S}^{1}$ between sets $A$ and $A^{\prime}$. Throughout the article we
will identify $\mathbb{S}^{1}$ with the interval $[0,1)$. Let $\lambda$ denote
_Lebesgue measure_ on the unit interval $[0,1]$ and by the abuse of notation
we also denote by $\lambda$ the _normalized Lebesgue measure_ on
$\mathbb{S}^{1}$. We denote by $C_{\lambda}(\mathbb{S}^{1})\subset
C(\mathbb{S}^{1})$ the family of all continuous Lebesgue measure-preserving
maps of $\mathbb{S}^{1}$ being a proper subset of the family of all continuous
circle maps equipped with the _uniform metric_ $\rho$:

$\rho(f,g):=\sup_{x\in\mathbb{S}^{1}}|f(x)-g(x)|.$

It follows from Proposition 4 from [10] that
$(C_{\lambda}(\mathbb{S}^{1}),\rho)$ is a complete metric space (formally this
theorem was stated for the interval and not the circle, but the proof in the
circle case is analogous).

By arc we mean any subset of $\mathbb{S}^{1}$ which is a homeomorphic image of
$[0,1]$. We denote by $\mathcal{A}$ the set of all subarcs of
$\mathbb{S}^{1}$.

###  2.2. Dynamical properties

We say that $f$ has a periodic arc $A\in\mathcal{A}$ of minimal period
$n\in\mathbb{N}$ if

(1) $f^{i}(A)\neq f^{j}(A)\text{ for }0\leq i<j<n\text{ and }f^{n}(A)=A.$

A map $f\in C_{\lambda}(\mathbb{S}^{1})$ is called

  * •

transitive if for each pair of nonempty open sets $U,V\subset\mathbb{S}^{1}$
there is $n\geq 0$ such that $f^{n}(U)\cap V\neq\emptyset$,

  * •

totally transitive if $f^{n}$ is transitive for all integers $n\geq 1$.

  * •

topologically mixing if for each pair of nonempty open sets
$U,V\subset\mathbb{S}^{1}$ there is $n_{0}\geq 0$ such that $f^{n}(U)\cap
V\neq\emptyset$ for every $n\geq n_{0}$,

  * •

leo (locally eventually onto) if for every nonempty open set
$U\subset\mathbb{S}^{1}$ there is $n\in{\mathbb{N}}$ such that
$f^{n}(U)=\mathbb{S}^{1}$.

Let $\mathcal{B}$ denote the Borel sets in $\mathbb{S}^{1}$. The measure-
preserving transformation $(f,\mathbb{S}^{1},\mathcal{B},\lambda)$ is

  * •

ergodic if for each $A\in\mathcal{B}$, $f^{-1}(A)=A$ $\lambda$-a.e. implies
$\lambda(A)=0$ or $\lambda(A^{c})=0$.

  * •

weakly mixing, if for every $A,B\in{\mathcal{B}}$,

$\lim_{n\to\infty}\frac{1}{n}\sum_{j=0}^{n-1}|\lambda(f^{-j}(A)\cap
B)-\lambda(A)\lambda(B)|=0.$

  * •

measure-theoretically exact if for every set $A\in\cap_{n\geq
0}f^{-n}(\mathcal{B})$ it holds that $\lambda(A)\lambda(A^{c})=0$.

###  2.3. Piecewise monotone maps

We say that a piecewise monotone map $f\in C_{\lambda}(\mathbb{S}^{1})$ has
slope $>s$ if $\left|\frac{f(x)-f(y)}{x-y}\right|>s$ whenever $x\neq y$ are
points on an arc of monotonicity of $f$.

A _critical point_ (or turning point) of $f\in C(\mathbb{S}^{1})$ is a point
$x\in\mathbb{S}^{1}$ such that $f(x)$ is a strict local extremum. Denote by
$\mathrm{Crit}(f)$ the set of all critical points of $f$. Let
$\mathrm{PA}(\mathbb{S}^{1})\subset C(\mathbb{S}^{1})$ denote the set of
_piecewise affine_ maps; i.e., there exists a finite partition of
$\mathbb{S}^{1}$ so that the map is affine on each element of the partition.
Note that the endpoints of affine pieces are not necessarily critical points
by our definition. Let $\mathrm{PA}_{\lambda}(\mathbb{S}^{1})\subset
C_{\lambda}(\mathbb{S}^{1})$ denote the set of piecewise affine maps that
preserve Lebesgue measure.

###  2.4. Rotations and liftings

For $\alpha\in[0,1)$ we define the map
$r_{\alpha}\colon~{}\mathbb{S}^{1}\to\mathbb{S}^{1}$ as

$r_{\alpha}(x)=x+\alpha\pmod{1},~{}x\in\mathbb{S}^{1}$

and for every $(\alpha,\beta)\in[0,1)^{2}$ the map
$T_{\alpha,\beta}\colon~{}C_{\lambda}(\mathbb{S}^{1})\to
C_{\lambda}(\mathbb{S}^{1})$ by

$T_{\alpha,\beta}(f)=r_{\alpha}\circ f\circ r_{\beta}.$

When there is no confusion about the map that we use we simply write
$T_{\alpha,\beta}=T_{\alpha,\beta}(f)$.

Note that for any $x\in\mathbb{S}^{1}$ and any $\alpha,\beta\in[0,1)$ we have

$|T_{\alpha,\beta}(f)(x)-T_{\alpha,\beta}(g)(x)|=|f(r_{\beta}(x))-g(r_{\beta}(x))|.$

Thus $\rho(T_{\alpha,\beta}(f),T_{\alpha,\beta}(g))=\rho(f,g)$. Therefore,
$T_{\alpha,\beta}$ is an isometry.

Consider a continuous map $f\colon~{}\mathbb{S}^{1}\to\mathbb{S}^{1}$ of
_degree_ $\mathrm{deg}(f)\in\mathbb{Z}$. Let
$F\colon~{}\mathbb{R}\to\mathbb{R}$ be a _lifting_ of $f$, i.e., a continuous
map for which

(2) $\phi\circ F=f\circ\phi\text{ on }\mathbb{R},$

where $\phi\colon~{}\mathbb{R}\to\mathbb{S}^{1}$ is defined by
$\phi(x)=x\pmod{1}$ and $F(x+1)=F(x)+\mathrm{deg}(f)$ for each
$x\in\mathbb{R}$. Note that two liftings of $f$ differ by an integer constant.

###  2.5. Window perturbations

Fix an arc $A\in\mathcal{A}$. Let $\\{A_{i}\in\mathcal{A}:1\leq i\leq m\\}$,
where $m$ is odd, be a finite collection of arcs satisfying
$\cup^{m}_{i=1}A_{i}=A$ and
$\operatorname{int}(A_{i})\cap\operatorname{int}(A_{j})=\emptyset$ when $i\neq
j$, we will refer to this as a partition of $A$.

Fix $f\in C_{\lambda}(\mathbb{S}^{1})$ an arc $A\in\mathcal{A}$ and a
partition of $A$. A map $h=h_{A,\\{A_{i}\\}}$ is an $m$-fold window
perturbation of $f$ with respect to $A$ and the partition $\\{A_{i}\\}$ if

  * •

$h|_{A^{c}}=f|_{A^{c}}$

  * •

for each $1\leq i\leq m$ the map $h|_{A_{i}}$ is an affinely scaled copy of
$f|_{A}$ with the orientation reversed for every second $i$, with $h|_{A_{1}}$
having the same orientation as $f|_{A}$.

The essence of this definition is illustrated by Figure 1.

We call an $m$-fold window perturbation of $f$ regular if all of the $A_{i}$’s
have the same length.

$f$$a$$b$$0$$1$$1$

$h$$0$$1$$1$$a$$b$

Figure 1. For $f\in C_{\lambda}(\mathbb{S}^{1})$ shown on the left, we show on
the right the graph of $h$ which is the regular $3$-fold piecewise affine
window perturbation of $f$ on the interval $[a,b]$.

We collect some facts about window perturbations which were proven or
discussed in [9],[10]. Suppose $A=[a,b]$, and $h=h_{[a,b]}$ is an $m$-fold
window perturbation of $f\in C_{\lambda}(\mathbb{S}^{1})$ with respect to an
arbitrary partition $\\{A_{i}\\}$ of $A$. Then

  1. (1)

$h$ preserves $\lambda$.

  2. (2)

if $m$ is odd then $h$ is continuous, and thus $h\in
C_{\lambda}(\mathbb{S}^{1})$.

  3. (3)

$\rho(h|_{[a,b]},f)\to 0$ when $|b-a|\to 0$.

  4. (4)

if $f\in\mathrm{PA}_{\lambda}(\mathbb{S}^{1})$ then
$h\in\mathrm{PA}_{\lambda}(\mathbb{S}^{1})$.

##  3\. Motivational examples

In this section we give several examples that initially motivated our study.

######  Example 6.

Consider the full tent map $f$ (viewed as a circle map). Obviously, $f\in
C_{\lambda}(\mathbb{S}^{1})$. For $\alpha<-\beta\pmod{1}$ and
$\alpha+\beta>-\frac{1}{2}\pmod{1}$ we define the interval
$J=J_{\alpha,\beta}:=[-2\beta-\alpha,1+\alpha]\pmod{1}$. We obtain that
$T_{\alpha,\beta}(J)=J$. Therefore, $T_{\alpha,\beta}$ is not transitive for
an open subset of $(\alpha,\beta)\in[0,1)^{2}$.

$f$$-\alpha-\beta$$1+\alpha+\beta$$0$$1$$1$

$-2\beta-\alpha$$J$$1+\alpha$$T_{\alpha,\beta}(J)=J$$1+\alpha$$0$$1$$1$

Figure 2.  $\alpha=-1/8$ and $\beta=-3/32$ from Example 6.

On the other hand, the following simple example shows that we can expect maps
from $C_{\lambda}(\mathbb{S}^{1})$ to be leo and measure-theoretically exact
wrt $\lambda$ provided they have slopes big enough even if they have the same
critical values.

######  Example 7.

For the map $g\in C_{\lambda}(\mathbb{S}^{1})$ given on Figure 3 the map
$T_{\alpha,\beta}(g)$ is leo for every $\alpha,\beta\in[0,1)$.
Rotation does not change the slope, so the slope of $T_{\alpha,\beta}(g)$
stays $5$. Fix any arc $A\subset\mathbb{S}^{1}$, let $G$ be a lifting of
$T_{\alpha,\beta}(g)$ and let $J\subset I$ be a lifting of $A$. Note that if
$J$ does not contain at least three critical points of $G$ then
$\operatorname{diam}G(J)\geq\frac{5}{3}\operatorname{diam}J$. But then there
is $n$ such that $G^{n}(J)$ contains three critical points, since distance
between critical points is uniformly bounded. This means that
$T_{\alpha,\beta}(g)^{n}(A)=\mathbb{S}^{1}$.
Applying Theorem 4 shows that the map $T_{\alpha,\beta}(g)$ is measure-
theoretically exact with respect to $\lambda$ for every
$\alpha,\beta\in[0,1)$.

$g$$0$$1$$\frac{1}{5}$$\frac{2}{5}$$\frac{3}{5}$$\frac{4}{5}$$1$ Figure 3.
Lifting of the map $g\pmod{1}$ from Example 7.

##  4\. Topological vs. measure-theoretic dynamical properties

First we show that transitivity and ergodicity are equivalent under some
natural assumptions using the tools developed by Li and Yorke [19]. We recall

See 3

###### Proof.

Throughout the proof, we use standard definitions from [19] without explicitly
redefining them.

Let $F$ denote a lifting of $f$. We define $\hat{F}:=F|_{[0,1)}\pmod{1}$ and
call $\hat{F}$ a representative of $F$. Since $f$ is measure-preserving and
piecewise $C^{2}$, for each Borel set $E\subset[0,1]$ the sets $\hat{F}(E)$
and $\hat{F}^{-1}(E)$ are also Borel and

(3) $\lambda(E)=0\text{ if and only if
}\lambda(\hat{F}(E))=\lambda(\hat{F}^{-1}(E))=0.$

The fact that ergodicity implies transitivity follows since each generic point
for the measure $\lambda$ on $\mathbb{S}^{1}$ is transitive.

Let us show the converse. It follows from [19, Theorem 1] that

(4) $\displaystyle\text{the map }\hat{F}\text{ has exactly one invariant
measure absolutely continuous}$ $\displaystyle\text{ with respect to
}\lambda\text{ which is }\lambda\text{ itself.}$

Assume that for some Borel set $A\subset[0,1]$,

(5) $\hat{F}^{-1}(A)=A,~{}\lambda\text{-a.e.}\text{ and }\lambda(A)\in(0,1).$

Write

$\hat{F}(A)=\hat{F}(A\setminus\hat{F}^{-1}(A))\cup\hat{F}(A\cap\hat{F}^{-1}(A)).$

But by (5) and (3) $\lambda(\hat{F}(A\setminus\hat{F}^{-1}(A)))=0$. Moreover
$\hat{F}(A\cap\hat{F}^{-1}(A))\subset A$ with
$\lambda(A\cap\hat{F}^{-1}(A))=\lambda(A)$ given again by (5). It shows that
$\hat{F}(A)=A$ $\lambda$-a.e., i.e., $A$ is invariant with respect to
$\hat{F}$. So [19, Lemma 2.2] applies: the characteristic function
$\chi_{A}(\cdot)$ is a density of an $\hat{F}$-invariant measure $\mu$ given
for each Borel set $E\subset[0,1]$ by the formula

(6)
$\mu(E)=\frac{1}{\lambda(A)}\int_{E}\chi_{A}(x)\mathrm{d}\lambda(x)=\frac{\lambda(E\cap
A)}{\lambda(A)}.$

Clearly $\mu$ is an $\hat{F}$-invariant measure absolutely continuous with
respect to $\lambda$ and different from $\lambda$, contradicting (4). Thus, in
(5) necessarily $\lambda(A)\in\\{0,1\\}$, and thus $\hat{F}$, resp. $f$ is
ergodic. ∎

We recall and prove

See 4

###### Proof of Theorem 4.

We can view $f$ as a piecewise continuous piecewise $C^{2}$ interval map.
Since $\lim_{n\to\infty}\lambda(f^{n}(U))=1$ for any open interval $U$ we get
weak mixing of $f$ with respect to $\lambda$ by [12, Theorem 2(a)]. By [12,
Theorem 1] the natural extension of $f$ with respect to $\lambda$ (see e.g.
[22, Section 5.10] for the definition of natural extension in our setting) is
weakly Bernoulli (for the definition of weak Bernoulli see [24] p. 89) and
thus by [24, Theorem 11.2, 11.3 and 12.1] is Bernoulli. This, in particular,
implies that $f$ with respect to $\lambda$ is measure-theoretically exact (see
[23]). ∎

If $f$ is weakly mixing with respect to a fully supported measure, then it is
topologically weak mixing and by Banks and Trotta [7] (cf. Theorem 4.4. from
[15]) it follows that on topological graphs it is topologically mixing. By
Theorem 7.3. [16] a topologically mixing circle map that is not leo needs to
have infinitely many fixed points. Strictly speaking we have the following.

######  Remark 8.

Let $f\in C_{\lambda}(\mathbb{S}^{1})$ be weakly mixing w.r.t. $\lambda$. Then
$f$ is topologically mixing. If $f$ is additionally piecewise monotone, it is
leo.

##  5\. Leo is open

###  5.1. Periodic arcs

We start this subsection with a basic, however very useful lemma.

######  Lemma 9.

Let $f\in C_{\lambda}(\mathbb{S}^{1})$ be a piecewise monotone map with slope
$>2$ and $k$ critical points. Suppose $f$ has a periodic arc
$A=[a_{0},b_{0}]\subset\mathbb{S}^{1}$ of minimal period $n\in\mathbb{N}$.

  * (1)

For each $i,j\in\mathbb{Z}$, $\lambda(f^{i}(A))=\lambda(f^{j}(A))$.

  * (2)

For $[a_{i},b_{i}]:=f^{i+kn}(A)$ for any $k\geq 0$,

    * (i)

$f(c_{i})=a_{i+1}$ and $f(d_{i})=b_{i+1}$ for some critical points
$c_{i},d_{i}\in(a_{i},b_{i})$,

    * (ii)

the points $a_{i},b_{i}$ are not critical and

    * (iii)

$f(\\{a_{i},b_{i}\\})\subset\\{a_{i+1},b_{i+1}\\}$.

  * (3)

$n\leq k$.

###### Proof.

For any $A\in\mathcal{A}$ we have $A\subset f^{-1}(f(A))$, thus since the map
$f$ preserves the Lebesgue measure, we have

$\lambda(A)\leq\lambda(f(A))\leq\cdots\leq\lambda(f^{n-1}(A))\leq\lambda(f^{n}(A))=\lambda(A),$

hence (1) follows. Property (1) easily implies all three properties
(2)(i)-(iii). Our assumption (1) from the definition of periodic arcs together
with the properties (1) and (2)(i) mean that critical points
$d_{i}\in(a_{i},b_{i})$ satisfying $f(d_{i})=b_{i+1}$ are different for
different $i$’s, because $b_{i}\neq b_{j}$ for $0\leq i<j<n$. Therefore, the
period $n$ satisfies $n\leq k$ as stated in (3). ∎

The following theorem shows that the phenomenon from Example 6 cannot be
realized if the slope is strictly greater than $2$.

Let

$\begin{array}[]{lll}E(f)&:=&\big{\\{}(\alpha,\beta):T_{\alpha,\beta}\text{
has a periodic arc}\big{\\}},\\\
E_{1}(f)&:=&\big{\\{}\alpha:T_{\alpha,0}\text{ has a periodic
arc}\big{\\}},\\\ E_{2}(f)&:=&\big{\\{}\beta:T_{0,\beta}\text{ has a periodic
arc}\big{\\}}.\end{array}$

In practice, the following theorem will be used for piecewise linear maps. For
the sake of completeness we state it in a more general form.

######  Theorem 10.

Let $f\in C_{\lambda}(\mathbb{S}^{1})$ be piecewise monotone and piecewise
$C^{2}$ map with slope strictly greater than $2$. Then

  1. (1)

$E_{1}(f)=E_{2}(f)$ are finite sets.

  2. (2)

$E(f)=\\{(\alpha,0)+(\gamma,-\gamma)\pmod{1}:\alpha\in E_{1}(f)\text{ and
}\gamma\in[0,1)\\}$,
i.e., $E(f)$ is a finite union of pairwise disjoint topological circles.

  3. (3)

The following three conditions are equivalent.

    1. (3a)

$T_{\alpha,\beta}$ is leo.

    2. (3b)

$(\alpha,\beta)\notin E(f)$.

    3. (3c)

$T_{\alpha,\beta}$ is exact with respect to $\lambda$.

###### Proof.

(1) To see that sets $E_{1}(f)$ and $E_{2}(f)$ are of equal cardinality notice
that $T_{\alpha,\beta}$ is topologically conjugate through $r_{\gamma}$ to
$T_{\alpha+\gamma,\beta-\gamma}$ for any $\gamma$. In particular for
$\alpha=\theta$, $\beta=0$ and $\gamma=-\theta$ this yields $\theta\in
E_{2}(f)$ provided $\theta\in E_{1}(f)$. For the converse implication take
$\alpha=0$, $\beta=\theta$ and $\gamma=\theta$.

Suppose $\beta\in E_{2}(f)$. Since $r_{\beta}$ is an inner rotation, one can
see that the set of critical values of $T_{0,\beta}$ does not depend on a
concrete value of $\beta\in[0,1)$, denote this common set by $CV(f)$. Note
that by our assumption on the number of critical points of $f$, $|CV(f)|\leq
k$. It follows from Lemma 9(2) that whenever $\beta\in E_{2}(f)$ has a
periodic arc $A_{0}=[a_{0},b_{0}]\subset\mathbb{S}^{1}$ of a minimal period
$n\in\mathbb{N}$ then $\bigcup_{i=0}^{n-1}\\{a_{i},b_{i}\\}\subset CV(f)$ and
there are maximally $\binom{k}{2}$ of such periodic orbits created by arcs
with endpoints in $CV(f)$.

By Lemma 9(2) we additionally have
$T_{0,\beta}(\bigcup_{i=0}^{n-1}\\{a_{i},b_{i}\\})=\bigcup_{i=0}^{n-1}\\{a_{i},b_{i}\\}\subset
CV(f)$. But for any $x\in\mathbb{S}^{1}$ there are only finitely many $\beta$
for which $T_{0,\beta}(x)=f(x+\beta)\in CV(f)$, in particular there are only
finitely many $\beta$ for which $a_{0}$ and $a_{0}+\beta$ are in $CV(f)$. We
have shown the desired result, there can be only finitely many values
$\beta\in[0,1)$ such that $T_{0,\beta}$ has a periodic arc.

(2) This follows from (1) and the conjugacy described in the first part of
this proof.

(3) The implication (3a)$\implies$(3b) follows from the definition of leo
property. Namely, if $T_{\alpha,\beta}$ is leo then it cannot have a periodic
arc. (3c)$\implies$(3a) is a consequence of Remark 8. (3a)$\implies$(3c)
follows from Theorem 4. It remains to prove that (3b)$\implies$(3a).

Thus we only need to show that if $T_{\alpha,\beta}$ is not leo then it has a
periodic arc. Assume that (A1) $f$ is not leo and does not have a periodic
arc. First we will show that $f$ cannot be transitive; assume the contrary
(A2) that $f$ is transitive. Transitive graph map is either totally transitive
or admits periodic decomposition (see Theorem 2.2 in [2], cf. [6]), which in
the case of circle means partition into arcs with disjoint interiors, permuted
by the map. The latter case is excluded by our assumption, hence the map is
totally transitive. But slope $>2$ implies that the map $f$ is not conjugate
with irrational rotation which implies it has periodic points (see [3, Theorem
C]). Then $f$ is topologically mixing (see [3, Theorem A], cf. [15, 16]). But
topologically mixing map which is not leo must have infinitely many fixed
points for $f^{m}$ for some $m$ (see Theorem 7.3 in [16]), which is not the
case for piecewise monotone maps. This is a contradiction of (A2) so $f$ is
not transitive.

Remember that this non-transitive $f$ does not have a periodic arc. Let $U,V$
be nonempty open subsets of $\mathbb{S}^{1}$ such that for each non-negative
integer $n$, $f^{n}(U)\cap V=\emptyset$. Put

$W:=\overline{\bigcup_{n\geq 0}f^{n}(U)}$

and suppose $\overline{W}$ is a connected component of $W.$ By our definition,
there exists $j$ fulfilling $f^{j}(U)\subset\overline{W}$. Since the map $f$
preserves the Lebesgue measure, $\lambda(U)\leq\lambda(f^{i}(U))$ hence

$\lambda(U)\leq\lambda(f^{j}(U))\leq\lambda(\overline{W}).$

Thus there are finitely many connected components of $W$, denote them
$W_{i},1\leq i\leq k$. Using the definition of $W$ and the pigeonhole
principle one can show that there is $i$ and a number $1\leq s\leq k$ such
that

$f^{s}(W_{i})\subset W_{i}.$

But $\lambda(W_{i})\leq\lambda(f^{s}(W_{i}))\leq\lambda(W_{i})$, so in fact
$W_{i}=f^{s}(W_{i})$, that is $W_{i}$ is a periodic arc, contradicting
assumption (A1). ∎

###  5.2. Stably leo piecewise affine maps

######  Lemma 11.

Let $f$ be a piecewise affine Lebesgue measure-preserving circle map and $c$ a
turning point of $f$. Then at least one of the following two properties holds:

  1. (1)

there exists another turning point $c\neq c^{\prime}\in\mathbb{S}^{1}$ such
that $f(c)=f(c^{\prime})$ and if $c$ is a local minimum then $c^{\prime}$ is a
local maximum or vice-versa (see the left-most part of Figure 5),

  2. (2)

there exists a point $x\in\mathbb{S}^{1}$ so that $f(x)=f(c)$ and an open
neighbourhood $U\ni x$ such that $f|_{U}$ is injective (see left part of
Figure 5).

Figure 4. Reduction to Figure 5.

$\varepsilon$$\varepsilon$

$\varepsilon$$\varepsilon$

Figure 5. Perturbation in case when critical values are different type of
extrema.

###### Proof.

Assume that we are not in case 1 and suppose that $f(c)$ is a local maximum.
Consider a small neighbourhood $U:=(f(c)-\delta,f(c)+\delta)$ of $f(c)$ which
contains no other critical value of $f$. Let $U^{-}:=(f(c)-\delta,c]$ and
$U^{+}:=[c,f(c)+\delta)$. The set $f^{-1}(U)$ consists of a finite number of
intervals. Since there is only one critical value in $U$, each such interval
needs to be mapped onto either $U$, $U^{-}$ or $U^{+}$. By the assumption at
least one of them gets mapped onto $U^{-}$ and none of them gets mapped only
onto $U^{+}$. Because $f$ is a Lebesgue measure-preserving circle map at least
one of these intervals needs to be mapped onto $U$. The case when $f(c)$ is a
local minimum is analogous. ∎

######  Lemma 12.

Assume that $f\in\mathrm{PA}_{\lambda}(\mathbb{S}^{1})$. Arbitrarily close to
$f$ we can find a map $h\in\mathrm{PA}_{\lambda}(\mathbb{S}^{1})$ all of whose
critical values are distinct. Furthermore, if absolute values of slopes of $f$
are bounded below by a constant $s$, then $h$ can be chosen to satisfy this as
well.

###### Proof.

Suppose that $c$ is a critical point of $f$, assume without loss of generality
that $y:=f(c)$ is a local maximum. Let $L_{y}$ denote the set of turning
points for which the map $f$ has the critical value $y$. If $|L_{y}|=1$ we
have that $f$ has no pairs of turning points with the critical value $y$ which
is what we want.

For $|L_{y}|>1$, by Lemma 11 if we do not have a pair of critical points as in
case (1) then all the points in $L$ are local maxima or local minima as in
case (2). In the latter case we perturb $f$ with a regular $3$-fold
perturbation (see Figure 5), which will create one new critical point with
critical value $y$ and this value necessarily put us back in case (1) of Lemma
11. The corresponding set $L_{y}$ is increased by 1 element.

Choose a critical point $c^{\prime}$ with $f(c^{\prime})=y$ with local minimum
at $c^{\prime}$. For a small enough $\varepsilon>0$ we first apply a $3$-fold
perturbation, as in the dotted red lines middle picture of Figure 5. Note that
the length of the domain of the two adjacent folds from the $3$-fold
perturbations which contain the critical value are required to be of the same
length $\varepsilon$. The final perturbation for this pair of critical points
is the union of the leftmost fold of the $3$-fold perturbations and the flip
of the rest of the $3$-fold perturbations over the critical value axis (as
shown with thick lines on the rightmost picture on Figure 5). Since these two
intervals have the same length $\varepsilon$, the perturbed map preserves
Lebesgue measure and the corresponding set $L_{y}$ is decreased by two
elements.

When we combine the two steps the set $L_{y}$ has decreased by at least one
element (possibly two). Repeating these procedures a finite number of times
produces a map with $|L_{y}|\leq 1$, and then repeating the procedure for
other critical values produces the desired map.

Note that the perturbations we perform can be arbitrarily small, and do not
decrease the absolute value of the slopes of the monotone pieces of $f$ and
preserve Lebesgue measure. ∎

The following statement is proven in [11, Lemma 11].

######  Lemma 13.

Let $F$ be a lifting modulo $1$ of a piecewise affine circle map $f$ with
nonzero slopes and such that its derivative does not exist at a finite set
$E$. Then $f\in C_{\lambda}(\mathbb{S}^{1})$ is equivalent to the property

(7) $\forall~{}y\in[0,1)\setminus F(E)\colon~{}\sum_{x\in
F^{-1}(y)}\frac{1}{|F^{\prime}(x)|}=1.$

Recall that we denote by $\mathcal{A}$ the set of all nondegenerate proper
subarcs of $\mathbb{S}^{1}$. For $f\in C_{\lambda}(\mathbb{S}^{1})$ and
$A\in\mathcal{A}$, a nontrivial connected component $A_{j}$ of
$f^{-1}(A)=\bigcup A_{j}$ satisfies $\lambda(A_{j})>0$. It is always an
element of $\mathcal{A}$.

######  Lemma 14.

If $h\in\mathrm{PA}_{\lambda}(\mathbb{S}^{1})$ has different critical values
and slope strictly greater than $4$ then there are $\delta=\delta(h)>0$ and
$\eta=\eta(h)>0$ such that for every $A\in\mathcal{A}$,

  1. (1)

either $h(A)=\mathbb{S}^{1}$ or $(1+\delta)\lambda(A)<\lambda(h(A))$.

  2. (2)

for any $A\in\mathcal{A}$ whose complement contains at most one critical point
we have $\lambda(H(I))>1+\eta$ where $H$ is a lifting of $h$ and $\phi(I)=A$.

  3. (3)

for each $(\alpha,\beta)$ the constant
$\delta(T_{\alpha,\beta}(h))=\delta(h)$.

  4. (4)

for each $(\alpha,\beta)$ the constant $\eta(T_{\alpha,\beta}(h))=\eta(h)$.

###### Proof.

Let
$\delta:=\inf\\{\frac{\lambda(h(A))}{\lambda(A)}-1:h(A)\neq\mathbb{S}^{1}\\}$.
Since $h$ is measure-preserving we have $\delta\geq 0$. There are arcs
$A_{n}\in\mathcal{A}$ such that $h(A_{n})\neq\mathbb{S}^{1}$ and

$\frac{\lambda(h(A_{n}))}{\lambda(A_{n})}\to 1+\delta,$

as $n\to\infty$.

We may assume that $A^{\prime}:=\lim A_{n}$ in the Hausdorff distance. By way
of contradiction, suppose that $\delta=0$; then
$\lambda(h(A^{\prime}))=\lambda(A^{\prime})$. If an interval $A$ contains at
most one critical point then $\lambda(h(A))/\lambda(A)>4/2=2$. Thus, for all
sufficiently large $n$, the interval $A_{n}$ can not be shorter than the
shortest piece of monotonicity of $h$ and thus $\lambda(A^{\prime})>0$.

We claim that $\lambda(A^{\prime})=1$. Let $h(A^{\prime})=[c,d]$. Suppose by
way of contradiction that $\lambda(A^{\prime})<1$. Since the slope of $h$ is
strictly greater than $4$ and the critical values of $h$ are different it
follows from Lemma 13 that every point has at least 4 preimages. In
particular, the point $y:=h(c)$ has at least 4 preimages, at most one of them
is a critical point, at most two of them are the endpoints of $A^{\prime}$. We
have shown that there is at least one preimage in the interior of $A^{\prime}$
which is not a turning point of $h$. Thus there is an arc $[c^{\prime},c]$
with $c^{\prime}<c$ contained in $h(A^{\prime})$, and so
$h(A^{\prime})\supsetneq[c,d]$, a contradiction. So $\lambda(A^{\prime})=1$,
which finishes the proof of (1).

Let $B_{n}:=\mathbb{S}^{1}\setminus A_{n}$. But then $\lambda(B_{n})\to 0$ and
so we can choose $n_{0}$ so that for $n\geq n_{0}$ the arc $B_{n}$ contains at
most one turning point of $h$. Since each point in $h(B_{n})$ has at most two
preimages in $B_{n}$ it must have at least one preimage in $A_{n}$, in other
words $h(B_{n})\subset h(A_{n})$. But then $h(A_{n})\supset h(B_{n}\cup
A_{n})=h(\mathbb{S}^{1})=\mathbb{S}^{1}$ which is a contradiction.

$y-\varepsilon$$y+\varepsilon$$A_{1}$$A_{2}$$B_{n}$$A_{3}$$h(B_{n})$$0$$1$$1$
Figure 6. Visual aid for Lemmas 14(2) and 15.

Suppose that $A\in\mathcal{A}$ and $B=\mathbb{S}^{1}\setminus A$ contains at
most one critical point. Suppose $I=[a,b]\subset J=[a,a+1]$, so
$\phi(J)=\mathbb{S}^{1}$ (recall that $\phi(I)=A$). In the previous paragraph
we showed that $h(A)=\mathbb{S}^{1}$. In what follows we denote the critical
points of $h$ by $c_{i}$ and corresponding critical points of $H|_{J}$ by
$C_{i}$. Choose the largest interval $[C_{1},C_{2}]\subset I$ where
$C_{1},C_{2}$ are critical points of $H$. The argument of the previous
paragraph shows that if there is a critical point of $h$ in $B$ then $h(c)\in
h(A)$ and thus $H(C)\in H(I)$. All other critical points of $H|_{J}$ are
contained in $[C_{1},C_{2}]$ thus the interval $H([C_{1},C_{2}])$ contains all
the critical values of $H|_{J}$. Furthermore there are distinct critical
points $C_{3},C_{4}\in J$ such that $H([C_{1},C_{2}])=[H(C_{3}),H(C_{4})]$. In
the previous paragraph we showed $h(A)\supset\mathbb{S}^{1}$, thus
$\lambda([H(C_{3}),H(C_{4})])\geq 1$. Since $h$ has distinct critical values
this inequality is strict. It is sufficient to choose $\eta$ to satisfy

$1+\eta:=\min\\{H(C)-H(C^{\prime}):|C-C^{\prime}|<1,C\neq
C^{\prime},H(C)-H(C^{\prime})>1\\},$

where minimum runs over all critical points $C,C^{\prime}$ of $H$. This
finishes the proof of (2) and (4).

We turn to statement (3). Fix $(\alpha,\beta)$ such that $T_{\alpha,\beta}(h)$
is leo. Consider arcs $A_{n}$ such that

$\frac{\lambda(h(A_{n}))}{\lambda(A_{n})}\to 1+\delta(h),$

as $n\to\infty$. Let $A_{n}^{\prime}:=r_{-\beta}A_{n}$. Then since rotations
are measure-preserving we have

$\frac{\lambda(T_{\alpha,\beta}(h)(A^{\prime}_{n}))}{\lambda(A^{\prime}_{n})}=\frac{\lambda(h(A_{n}))}{\lambda(A_{n})}.$

Therefore
$\frac{\lambda(T_{\alpha,\beta}(h)(A^{\prime}_{n}))}{\lambda(A^{\prime}_{n})}\to
1+\delta(h)$ and so $\delta(T_{\alpha,\beta}(h))\leq\delta(h)$. Reversing the
role of the maps proves the desired equality. ∎

Lemma 14 yields the following corollary.

See 5

For $h\in\mathrm{PA}_{\lambda}(\mathbb{S}^{1})$ and $A\in\mathcal{A}$ let

$\tau(A):=\max\\{\mathrm{dist}(A^{\prime},A^{\prime\prime})\colon~{}A^{\prime},A^{\prime\prime}\text{
non-degenerate components of }h^{-1}(A)\\}.$

######  Lemma 15.

Suppose $h\in\mathrm{PA}_{\lambda}(\mathbb{S}^{1})$ is leo with slope strictly
greater than $4$ and different critical values. Let $\kappa(h)$ denote the
minimal distance between the critical values of $h$. If $A\in\mathcal{A}$ and
$\lambda(A)\leq{\kappa(h)}$ then the set $h^{-1}(A)$ has at least two non-
degenerate components. Moreover there exists $\xi(h)>0$ such that

  1. (1)

$\inf_{A\in\mathcal{A},~{}\lambda(A)\leq\kappa}\tau(A)>\xi(h)$

  2. (2)

for each $A\in\mathcal{A}$ with $\lambda(A)\leq\kappa$ there are arcs
$A^{\prime},A^{\prime\prime}\subset\mathcal{A}$ such that
$\mathrm{dist}(A^{\prime},A^{\prime\prime})\geq\xi(h)$ and
$h(A^{\prime})=h(A^{\prime\prime})=A$.

  3. (3)

for each $(\alpha,\beta)$ we have $\xi(T_{\alpha,\beta}(h))=\xi(h)$.

  4. (4)

for each $(\alpha,\beta)$ we have $\kappa(T_{\alpha,\beta}(h))=\kappa(h)$.

###### Proof.

Since rotations are isometries, the constant $\kappa(h)$ does not depend on
$\alpha$ and $\beta$. Let $\zeta$ be the length of the shortest piece of
monotonicity of $h$. Since $h\in\mathrm{PA}_{\lambda}(\mathbb{S}^{1})$ is leo
with slope strictly greater than $4$ and different critical values every point
$y\in\mathbb{S}^{1}$ has at least 4 preimages (see Figure 6), where at most
one of these preimages is a critical point. Thus for
$0<\varepsilon\leq\kappa/3$ there are at least three disjoint arcs
$A_{1},A_{2},A_{3}$ such that
$h(A_{1})=h(A_{2})=h(A_{3})=(y-\varepsilon,y+\varepsilon)$ and $h$ is monotone
on each of these arcs. In particular two of these arcs $A_{i},A_{j}$ are
separated by a piece of monotonicity and so
$\mathrm{dist}(A_{i},A_{j})>\xi(h)$. It is easy to see that $\xi(h)\geq\zeta$.
Clearly $\zeta$ does not depend on $(\alpha,\beta)$ which finishes the proof
of this lemma. ∎

###  5.3. Proof of Theorem 1

Let us recall the statement of the main theorem of this paper. See 1

###### Proof.

We start with a set $\\{h_{n}\\}\in\mathrm{PA}_{\lambda}(\mathbb{S}^{1})$
which is dense in $C_{\lambda}(\mathbb{S}^{1})$, e.g. see Lemma 12 from [11].
By applying arbitrary small $n$-fold perturbations we may assume that the
slopes of maps $h_{n}$ are strictly greater than $4$. By Lemma 12 we may also
assume that every $h_{n}$ has pairwise different critical values. By Corollary
5 each $h_{n}$ is leo and thus also Lemma 14 and Lemma 15 hold for $h_{n}$; we
call the constants corresponding to these two lemmas
$\kappa_{n},\delta_{n},\eta_{n},\gamma_{n}$. We can additionally assume that
$\eta_{n}$ is smaller than the length of the shortest piece of monotonicity of
$h_{n}$ and $\delta_{n}<1$.

Set $\varepsilon_{n}<\frac{\delta_{n}}{2}\min\\{\eta_{n}/6,\kappa_{n}/3\\}$.
We will show that the conclusions of the theorem hold for

$\mathcal{O}:=\bigcup_{(\alpha,\beta)\in[0,1)^{2}}T_{\alpha,\beta}\Big{(}\bigcup_{n\in\mathbb{N}}B(h_{n},\varepsilon_{n})\Big{)}.$

Let us prove that any $g\in B(h_{n},\varepsilon_{n})$ is leo. Recall that $G$
denotes a lifting of $g$ and $H_{n}$ a lifting of $h_{n}$.

By Lemma 14 and the additional assumption on $\eta_{n}$ we have that for every
$g\in B(h_{n},\varepsilon_{n})$:

  * (p1)

For an interval $I\subset\mathbb{R}$, if $1-\eta_{n}<\lambda(I)<1$ then
$H_{n}(I)>1+\eta_{n}$ and thus $G(I)>1+\eta_{n}-2\varepsilon_{n}>1$ (which
implies that $g(A)=\mathbb{S}^{1}$ for any arc $A\in\mathcal{A}$ satisfying
$1-\eta_{n}<\lambda(A)<1$).

We claim that additionally

  * (p2)

If $A\in\mathcal{A}$ and
$\lambda(A)<\alpha_{n}:=\min\\{\xi_{n}/2,\kappa_{n}/3\\}$ then $g^{-1}(A)$ has
at least two non-degenerate components.

Let us prove (p2). Observe that
$\lambda(B(A,\varepsilon_{n}))=\lambda(A)+2\varepsilon_{n}<\kappa_{n}/3+2\varepsilon_{n}\leq\kappa_{n}$.
So we can apply Lemma 15 (2) to conclude that
$h_{n}^{-1}(B(A,\varepsilon_{n}))$ has at least two non-degenerate components
$A^{\prime}$ and $A^{\prime\prime}$ such that
$h_{n}(A^{\prime})=h_{n}(A^{\prime\prime})=B(A,\varepsilon_{n})$ and
$\mathrm{dist}(A^{\prime},A^{\prime\prime})>\xi_{n}$. Thus since
$\rho(g,h_{n})<\varepsilon_{n}$ we have $A\subset g(A^{\prime})\cap
g(A^{\prime\prime})$. Thus there exist intervals $Q^{\prime}\subset
A^{\prime},Q^{\prime\prime}\subset A^{\prime\prime}$ so that
$g(Q^{\prime})=g(Q^{\prime\prime})=A$ with
$\lambda(Q^{\prime}),\lambda(Q^{\prime\prime})>0$. Furthermore, since
$\mathrm{dist}(A^{\prime},A^{\prime\prime})>\xi_{n}$ and $Q^{\prime}\subset
A^{\prime}$ and $Q^{\prime\prime}\subset A^{\prime\prime}$ we conclude
$\mathrm{dist}(Q^{\prime},Q^{\prime\prime})>\xi_{n}$ as well, i.e.,
$Q^{\prime},Q^{\prime\prime}$ are distinct non-degenerate components of
$g^{-1}(A)$ as required.

Fix $g\in B(h_{n},\varepsilon_{n})$. If $g$ is topologically mixing for every
arc $A\in\mathcal{A}$ we have $\lambda(g^{n}(A))\to 1$. By (p1) we get
$g^{n}(A)=\mathbb{S}^{1}$ for some sufficiently large $n$. Thus we have

$\displaystyle g\text{ is not leo}~{}\implies~{}g~{}\text{is not topologically
mixing}.$

In what follows we will repeatedly use the following fact: if
$Q\in\mathcal{A}$ then $Q\subset g^{-1}(g(Q))$, thus since $g$ is measure-
preserving we have $\lambda(Q)\leq\lambda(g(Q))$.

If $g$ is not topologically mixing then by definition there are arcs
$A,\tilde{A}\in\mathcal{A}$ such that $g^{n_{k}}(A)\cap\tilde{A}=\emptyset$
for an infinite sequence $\\{n_{k}\\}_{k\in\mathbb{N}}$. In particular,
$\lambda(g^{n_{k}}(A))\leq 1-\lambda(\tilde{A})$ for each $k$. By the above
fact, the sequence $\\{\lambda(g^{n_{k}}(A))\\}_{n=0}^{\infty}$ is non-
decreasing, thus since $\mathbb{S}^{1}$ is compact, there exists an arc
$B\in\mathcal{A}$ such that for some subsequence
$\\{{n_{k}}_{i}\\}_{i\in\mathbb{N}}$,

(8) $\lim_{i\to\infty}g^{{n_{k}}_{i}}(A)=B$

satisfying $\lambda(A)\leq\lambda(B)\leq 1-\lambda(\tilde{A})<1$.

Suppose that $a:=\lambda(g(B))-\lambda(B)>0$, then since $g$ is continuous it
follows that there exists a $K\in\mathbb{N}$ such that
$\lambda(g^{{n_{k}}_{i}+1}(A))-\lambda(B)>a/2$ for every $i\geq K$. Again
applying the above fact yields $\lambda(g^{n}(A))-\lambda(B)>a/2$ for every
$n\geq n_{K}$. This holds in particular for all ${n_{k}}_{i}$ for $i$
sufficiently large which contradicts (8). Thus we have shown that

(9) $\lambda(g(B))=\lambda(B)\in(0,1)$

This implies that the set $g^{-1}(g(B))$ has only one non-degenerate
component; hence by (p1) and (p2),

(10) $\alpha_{n}\leq\lambda(B)\leq 1-\eta_{n}.$

Note that by definition $\varepsilon_{n}<\frac{\delta_{n}}{2}$, thus combining
(9), the fact that $g\in B(h_{n},\varepsilon_{n})$, Lemma 14(1) (which we can
apply because of the upper bound in (10)), and the lower estimate of (10)
yields

$\lambda(B)=\lambda(g(B))\geq\lambda(h_{n}(B))-2\varepsilon_{n}\geq(1+\delta_{n})\lambda(B)-2\varepsilon_{n}\geq\lambda(B)+\delta_{n}\alpha_{n}-2\varepsilon_{n}>\lambda(B).$

This contradiction finishes the proof of (1).

Statement (2) follows directly from the definition of $\mathcal{O}$. Namely,
for the proof of (2) it suffices to recall that $T_{\alpha,\beta}$ is an
isometry and thus $g\in
T_{\alpha_{k},\beta_{k}}(B(f_{n_{k}},\varepsilon_{n_{k}}))$ if and only if
$T_{\alpha,\beta}(g)\in
T_{\alpha+\alpha_{k},\beta+\beta_{k}}(B(f_{n_{k}},\varepsilon_{n_{k}}))$. ∎

##  6\. Generic weak-mixing

In [10, Theorem 2] we showed that there is a dense set of interval maps in
$C_{\lambda}([0,1])$ which are not ergodic, the proof works with natural
modifications in $C_{\lambda}(\mathbb{S}^{1})$, thus a strong metric result in
the spirit of Theorem 1 can not hold. Nevertheless we can still obtain the
following theorem.

See 2

###### Proof.

Using Theorem 4 and Corollary 5, if
$h\in\mathrm{PA}_{\lambda}(\mathbb{S}^{1})$ has different critical values and
slope strictly greater than $4$ then it is exact with respect to $\lambda$
(and thus also strongly and weakly mixing with respect to $\lambda$). Thus we
have a dense set of maps $\\{f_{n}:n\in\mathbb{N}\\}\subset
C_{\lambda}(\mathbb{S}^{1})$ such that $T_{\alpha,\beta}(f_{n})$ is weakly
mixing with respect to $\lambda$ for each $\alpha,\beta\in[0,1)$. Let
$\\{h_{j}\\}_{j\geq 1}$ be a countable, dense collection of continuous
functions in $L^{1}(\mathbb{S}^{1}\times\mathbb{S}^{1})$. For any $f\in
C_{\lambda}(\mathbb{S}^{1})$ and $\ell\geq 1$, let

$S^{f}_{\ell}h_{j}(x,y):=\frac{1}{\ell}\sum_{k=0}^{\ell-1}h_{j}\big{(}(f\times
f)^{k}(x,y)\big{)}.$

The map $f$ is weakly mixing if and only if the map $f\times f$ is ergodic,
and by the Birkhoff ergodic theorem, the map $f\times f$ is ergodic if and
only if we have

$\lim_{\ell\to\infty}S^{f}_{\ell}h_{j}(x,y)=\int_{\mathbb{S}^{1}\times\mathbb{S}^{1}}h_{j}(s,t)\,d(\lambda(s)\times\lambda(t))$

for all $j\geq 1$.

For each $n\geq 1$ and $(\alpha,\beta)$ there exists a set
$E_{n,\alpha,\beta}\subset\mathbb{S}^{1}\times\mathbb{S}^{1}$ and a positive
integer $\ell_{n,\alpha,\beta}\geq n$ such that
$\lambda(E_{n,\alpha,\beta})>1-\frac{1}{n}$ and

(11)
$\Big{|}S^{T_{\alpha,\beta}(f_{n})}_{\ell}h_{j}(x,y)-\int_{\mathbb{S}^{1}\times\mathbb{S}^{1}}h_{j}(s,t)\,d(\lambda(s)\times\lambda(t))\Big{|}<\frac{1}{3n}$

for all $(x,y)\in E_{n,\alpha,\beta}$, $1\leq j\leq n$, and
$\ell\geq\ell_{n,\alpha,\beta}$.

For any $\alpha,\beta$, any $\bar{\alpha},\bar{\beta}$ and any $g\in
C_{\lambda}(\mathbb{S}^{1})$ by the triangular inequality we have:

$\begin{array}[]{ll}\Big{|}S^{T_{\alpha,\beta}(g)}_{\ell_{n,\bar{\alpha},\bar{\beta}}}h_{j}(x,y)-\int_{\mathbb{S}^{1}\times\mathbb{S}^{1}}h_{j}(s,t)\,d(\lambda(s)\times\lambda(t))\Big{|}\leq\\\
\qquad\Big{|}S^{T_{\alpha,\beta}(g)}_{\ell_{n,\bar{\alpha},\bar{\beta}}}h_{j}(x,y)-S^{T_{\alpha,\beta}(f_{n})}_{\ell_{n,\bar{\alpha},\bar{\beta}}}h_{j}(x,y)\Big{|}+\\\
\qquad\quad\Big{|}S^{T_{\alpha,\beta}(f_{n})}_{\ell_{n,\bar{\alpha},\bar{\beta}}}h_{j}(x,y)-S^{T_{\bar{\alpha},\bar{\beta}}(f_{n})}_{\ell_{n,\bar{\alpha},\bar{\beta}}}h_{j}(x,y)\Big{|}+\\\
\qquad\quad\quad\Big{|}S^{T_{\bar{\alpha},\bar{\beta}}(f_{n})}_{\ell_{n,\bar{\alpha},\bar{\beta}}}h_{j}(x,y)-\int_{\mathbb{S}^{1}\times\mathbb{S}^{1}}h_{j}(s,t)\,d(\lambda(s)\times\lambda(t))\Big{|}.\end{array}$

We would like to show that the latter is small when $g$ is sufficiently close
to $f_{n}$ and $\alpha,\beta$ is sufficiently close to
$\bar{\alpha},\bar{\beta}$ and $(x,y)\in E_{n,\bar{\alpha},\bar{\beta}}$.

Remember that $h_{j}$’s are continuous functions. Since $T_{\alpha,\beta}(g)$
is continuous in both $(\alpha,\beta)$ and $g$, the first term is bounded by
$\frac{1}{3n}$ for a small neighborhood of $(\bar{\alpha},\bar{\beta},g)$.
Since $T_{\alpha,\beta}$ is continuous in $(\alpha,\beta)$ the second term is
bounded by $\frac{1}{3n}$ for a small neighborhood of
$(\bar{\alpha},\bar{\beta})$ in $[0,1)^{2}$. Thus we can choose a small
neighborhood $I_{\bar{\alpha},\bar{\beta}}$ of $(\bar{\alpha},\bar{\beta})$ in
$[0,1)^{2}$ and a small neighborhood
$B(f_{n},\varepsilon_{n,\bar{\alpha},\bar{\beta}})$ in
$C_{\lambda}(\mathbb{S}^{1})$ such that both of the above estimates hold. The
third term is bounded by $\frac{1}{3n}$ by (11), therefore we get for any
point $(x,y)\in E_{n,\bar{\alpha},\bar{\beta}}$, any $(\alpha,\beta)\in
I_{\bar{\alpha},\bar{\beta}}$, and $g\in
B(f_{n},\varepsilon_{n,\bar{\alpha},\bar{\beta}})$ that

(12)
$\Big{|}S^{T_{\alpha,\beta}(g)}_{\ell_{n,\bar{\alpha},\bar{\beta}}}h_{j}(x,y)-\int_{\mathbb{S}^{1}\times\mathbb{S}^{1}}h_{j}(s,t)\,d(\lambda(s)\times\lambda(t))\Big{|}<\frac{1}{n}$

for $1\leq j\leq n$.

Since the torus $[0,1)^{2}$ is compact we can find a finite cover of it by
such sets $I_{n,\bar{\alpha}_{n,i},\bar{\beta}_{n,i}},1\leq i\leq j_{n}$.
Choose
$\varepsilon_{n}:=\min\\{\varepsilon_{n,\bar{\alpha}_{n,i},\bar{\beta}_{n,i}}:1\leq
i\leq j_{n}\\}$.

Consider the set

$\mathcal{G}:=\bigcap_{N\geq
1}\bigcup_{(\alpha,\beta)\in[0,1)^{2}}T_{\alpha,\beta}\Big{(}\bigcup_{n\geq
N}B(f_{n},\varepsilon_{n})\Big{)}.$

The set $\mathcal{G}$ is a dense $G_{\delta}$ set since $T_{\alpha,\beta}$ is
an isometry.

For each $g\in\mathcal{G}$ there are infinite sequences $n_{k}$ and
$(\alpha_{k},\beta_{k})$ and
$(\bar{\alpha}_{n_{k},i_{k}},\bar{\beta}_{n_{k},i_{k}})$ such that $g\in
T_{\alpha_{k},\beta_{k}}(B((f_{n_{k}}),\varepsilon_{n_{k}}))$ and
$(\alpha_{k},\beta_{k})\in
I_{n_{k},\bar{\alpha}_{n_{k},i_{k}},\bar{\beta}_{n_{k},i_{k}}}$. Consider

$\mathcal{E}(g):=\bigcap_{M=1}^{\infty}\bigcup_{k=M}^{\infty}E_{n_{k},\bar{\alpha}_{n_{k},i_{k}},\bar{\beta}_{n_{k},i_{k}}}.$

Since
$\lambda(E_{n_{k},\bar{\alpha}_{n_{k},i_{k}},\bar{\beta}_{n_{k},i_{k}}})>1-\frac{1}{n_{k}}$,
it follows that $\lambda(\mathcal{E}(g))=1$.

We have shown that

(13)
$\Big{|}S^{g}_{\ell_{n_{k}},\bar{\alpha}_{n_{k},i_{k}},\bar{\beta}_{n_{k},i_{k}}}h_{j}(x,y)-\int_{\mathbb{S}^{1}\times\mathbb{S}^{1}}h_{j}(s,t)\,d(\lambda(s)\times\lambda(t))\Big{|}<\frac{1}{n_{k}}$

for all $(x,y)\in
E_{n_{k},\bar{\alpha}_{n_{k},i_{k}},\bar{\beta}_{n_{k},i_{k}}}$ and all $1\leq
j\leq n_{k}$ for each $k\geq 1$.

The $\lim_{\ell\to\infty}S^{g}_{\ell}h_{j}(x,y)$ exists for almost every
$(x,y)$ by the Birkhoff ergodic theorem. Equation (13) holds infinitely often
for every point of $\mathcal{E}(g)$ so we conclude that this limit must equal
$\int_{\mathbb{S}^{1}\times\mathbb{S}^{1}}h_{j}(s,t)\,d(\lambda(s)\times\lambda(t))$
and thus $g\times g$ is ergodic, or equivalently $g$ is weakly mixing.

For the proof of (2) is suffices to note that $g\in
T_{\alpha_{k},\beta_{k}}(B((f_{n_{k}}),\varepsilon_{n_{k}}))$ if and only if
$T_{\alpha,\beta}(g)\in
T_{\alpha+\alpha_{k},\beta+\beta_{k}}(B((f_{n_{k}}),\varepsilon_{n_{k}}))$. ∎

## Acknowledgements

We would like to thank CIRM for hospitality during our research in residence
program where this paper was finalized.
J. Bobok was supported by the European Regional Development Fund, project No.
CZ 02.1.01/0.0/0.0/16_019/0000778. J. Činč was supported by the IDUB program
no. 1484 “Excellence initiative – research university” for the AGH University
of Science and Technology. P. Oprocha was supported by National Science
Centre, Poland (NCN), grant no. 2019/35/B/ST1/02239.

## References

  * [1] J. Aaronson, M. Denker, M. Urbanski, Ergodic theory for Markov fibred systems and parabolic rational maps, Trans. Am. Math. Soc. 337 (1993), 495–548.
  * [2] Ll. Alsedá, M. A. del Río, J. A. Rodríguez, A splitting theorem for transitive maps, J. Math. Anal. Appl. 232(2) (1999), 359–375.
  * [3] Ll. Alsedá, M. A. del Río, J. A. Rodríguez, Survey on the relation between transitivity and dense periodicity for graph maps, Dedicated to Professor Alexander N. Sharkovsky on the occasion of his 65th birthday. J. Difference Equ. Appl. 9 (2003), no. 3-4, 281–288.
  * [4] J.S. Athreya, M. Boshernitzan, Ergodic Properties of Compositions of Interval Exchange Maps and Rotations, Nonlinearity 26 (2013), 417–423.
  * [5] A. Avila, G. Forni, Weak mixing for interval exchange transformations and translation flows, Ann. of Math. (2) 165 (2007), no. 2, 637–664.
  * [6] J. Banks, Regular periodic decompositions for topologically transitive maps, Ergod. Th. Dynam. Sys. 17(3) (1997), 505–529.
  * [7] J. Banks, B. Trotta, Weak mixing implies mixing for maps on topological graphs, J. Difference Equ. Appl., 11(12) (2005), 1071–1080.
  * [8] J. Bobok, On non-differentiable measure preserving functions, Real Analysis Exchange 16(1) (1991) 119-129.
  * [9] J. Bobok, S. Troubetzkoy, Typical properties of interval maps preserving the Lebesgue measure, Nonlinearity 33 (2020), 6461–6479.
  * [10] J. Bobok, J. Činč, P. Oprocha, S. Troubetzkoy, Periodic points and shadowing for generic Lebesgue measure-preserving interval maps, Nonlinearity 35, (2021), 2534–2557.
  * [11] J. Bobok, J. Činč, P. Oprocha, S. Troubetzkoy, S-limit shadowing is generic for continuous Lebesgue measure-preserving circle maps, published online in Ergod. Theory. Dyn. Sys., 1–21, 2021. https://doi.org/10.1017/etds.2021.112.
  * [12] R. Bowen, Bernoulli maps of the interval, Isr. J. Math. 28 (1977), 161–168.
  * [13] J. Činč, P. Oprocha, Parametrized family of pseudo-arc attractors: physical measures and prime ends rotations, Proc. Lond. Math. Soc. (3), 1–40, 2022. http://dx.doi.org/10.1112/plms.12448
  * [14] E. Glasner, B. Weiss, On the interplay between measurable and topological dynamics. Handbook of dynamical systems. Vol. 1B, 597–648, Elsevier B.V., Amsterdam, 2006.
  * [15] G. Harańczyk, D. Kwietniak, P. Oprocha, A note on transitivity, sensitivity and chaos for graph maps, J. Difference Equ. Appl. 17(10) (2011), 1549–1553.
  * [16] G. Harańczyk, D. Kwietniak, P. Oprocha, Topological structure and entropy of mixing graph maps, Ergod. Th. Dynam. Sys. 34(5) (2014), 1587–1614.
  * [17] M. Keane, Interval exchange transformations, Math. Z. 141 (1975), 25–31.
  * [18] M. Keane, Non-ergodic interval exchange transformations, Israel J. Math. 26 (1977), no. 2, 188–196.
  * [19] T. Y. Li, J. A. Yorke, Ergodic transformation from an interval into itself, Trans. Amer. Math. Soc. 235(1978), 183–192.
  * [20] H. Masur, Interval exchange transformations and measured foliations, Ann. of Math. (2) 115 (1982), no. 1, 169–200.
  * [21] M. Misiurewicz, Rotation Theory, https://www.math.iupui.edu/~mmisiure/rotth.pdf.
  * [22] M. Nicol, K. Petersen, Ergodic Theory: Basic Examples and Constructions. In: Meyers R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY, 2009.
  * [23] A. Quas, Ergodicity and Mixing Properties. In: Meyers R. (eds) Mathematics of Complexity and Dynamical Systems. Springer, New York, NY, 2009.
  * [24] P. C. Shields, The Theory of Bernoulli Shifts, University of Chicago Press, 1973, 118 pp.
  * [25] J. Schmeling, R. Winkler, Typical dimension of the graph of certain functions, Monatsh. Math. 119(4) (1995), 303–320.
  * [26] W. A. Veech, Gauss measures for transformations on the space of interval exchange maps, Ann. of Math. (2) 115 (1982), no. 1, 201–242.
  * [27] P. Walters, An Introduction to Ergodic Theory, New York: Springer 1982.


11institutetext: Department of Computer Science
Emory University
Atlanta, USA
11email: {kaustubh.dhole<EMAIL_ADDRESS>
# GenQREnsemble: Zero-Shot LLM Ensemble Prompting for Generative Query
Reformulation

Kaustubh D. Dhole  Eugene Agichtein

###### Abstract

Query Reformulation(QR) is a set of techniques used to transform a user’s
original search query to a text that better aligns with the user’s intent and
improves their search experience. Recently, zero-shot QR has been shown to be
a promising approach due to its ability to exploit knowledge inherent in large
language models. By taking inspiration from the success of ensemble prompting
strategies which have benefited many tasks, we investigate if they can help
improve query reformulation. In this context, we propose an ensemble based
prompting technique, GenQREnsemble which leverages paraphrases of a zero-shot
instruction to generate multiple sets of keywords ultimately improving
retrieval performance. We further introduce its post-retrieval variant,
GenQREnsembleRF to incorporate pseudo relevant feedback. On evaluations over
four IR benchmarks, we find that GenQREnsemble generates better reformulations
with relative nDCG@10 improvements up to 18% and MAP improvements upto 24%
over the previous zero-shot state-of-art. On the MSMarco Passage Ranking task,
GenQREnsembleRF shows relative gains of 5% MRR using pseudo-relevance
feedback, and 9% nDCG@10 using relevant feedback documents.

###### Keywords:

Query Reformulation Zero-Shot Prompting Relevance Feedback

##  1 Introduction

Users searching for relevant documents might not always be able to accurately
express their information needs in their initial queries. This could result in
queries being vague or ambiguous or lacking the necessary domain vocabulary.
Query Reformulation (QR) is a set of techniques used to transform a user’s
original search query to a text that better aligns with the user’s intent and
improves their search experience. Such reformulation alleviates the vocabulary
mismatch problem by expanding the query with related terms or paraphrasing it
into a suitable form by incorporating additional context.

Recently, with the success of large language models (LLMs) [5, 23], a plethora
of QR approaches have been developed. The generative capabilities of LLMs have
been exploited to produce novel queries [22], as well as useful keywords to be
appended to the users’ original queries [29]. By gaining exposure to enormous
amounts of text during pre-training, prompting has become a promising avenue
for utilizing knowledge inherent in an LLM for the benefit of subsequent
downstream tasks [27] especially QR [14, 32].

Unlike training or few-shot learning, zero-shot prompting does not rely on any
labeled examples. The advantage of a zero-shot approach is the ease with which
a standalone generative model can be used to reformulate queries by prompting
a templated piece of instruction along with the original query. Particularly,
zero-shot QR can be used to generate keywords by prompting the user’s original
query along with an instruction that defines the task of query reformulation
in natural language like Generate useful search terms for the given
query:‘List all the breweries in Austin’.

Instruction | Expansions Generated
---|---
Increase the search efficacy by offering | age goldfish grow outsmart outlive
beneficial expansion keywords for the query | ageing species…
Enhance search outcomes by recommending beneficial | Goldfish breed sizes What kind of
expansion terms to supplement the query | goldfish grows the fastest…

Figure 1: Keywords generated for the query (“do goldfish grow”) differ
drastically when generated from two paraphrastic instructions prompted to
flan-t5-xxl [7].

However, such a zero-shot prompting approach is still contingent on the exact
instruction appearing in the prompt providing plenty of avenues of
improvement. While LLMs have been known to vary significantly in performance
across different prompts [36, 8] and generation settings [33], many natural
language tasks have benefited by exploiting such variation via ensembling
multiple prompts or generating diverse reasoning paths [16, 3, 31]. Whether
such improvements also transfer to tasks like QR is yet to be determined. In
Figure 1, a vast difference is noticed in the keywords generated when the
input instruction is altered to a semantically similar variant. We hypothesize
that QR might naturally benefit from such variation – An ensemble of zero-shot
reformulators with paraphrastic instructions can be tasked to look at the
input query in diverse ways so as to elicit different expansions. This work
proposes the following contributions:

  * •

We propose a novel method,GenQREnsemble – a zero-shot Ensemble based
Generative Query Reformulator which exploits multiple zero-shot instructions
for QR to generate a more effective query reformulation than possible with an
individual instruction. (Section 3)

  * •

We further introduce an extension GenQREnsembleRF to incorporate Relevance
Feedback into the process. (Section 3)

  * •

We evaluate the proposed methods over four standard IR benchmarks,
demonstrating significant relative improvements vs. recent state of the art,
of up to 18% on nDCG@10 in pre-retrieval settings, and of up to 9% nDCG@10 on
post-retrieval (feedback) settings, demonstrating increased generalizability
of our approach.

Next, we summarize the prior work to place our contributions in context.

##  2 Related Work

Query reformulation has been shown to be effective in many settings [6]. It
can be done pre-retrieval, or post-retrieval, via incorporating evidence from
feedback, obtained either from a user or from top-ranked results in the sparse
retrieval setting [15], and in the dense retrieval setting [30, 35].

Recently, zero-shot approaches to query reformulation have received
considerable attention. Wang et al. [29] design a query reformulator by fine-
tuning a sequence-to-sequence transformer, T5 [25] on pairs of raw and
transformed queries. Their zero-shot prompting approach uses an instruction-
tuned model, FlanT5 [7] to generate keywords for query expansion and
incorporating PRF. Jagerman et al. [14] demonstrate LLMs can be more powerful
than traditional methods for query expansion. Mo et al. [19] propose a
framework to reformulate conversational search queries using LLMs. Gao et al.
[11]’s framework performs retrieval through fake documents generated by
prompting LLMs with user queries. Alaofi et al. [2] prompt LLMs with
information descriptions to generate query variants.

However, using a single query reformulation can sometimes degrade performance
compared to the original query. To address this drawback, prior efforts have
incorporated ensemble strategies via keywords from numerous sources or fusing
documents from different queries. Gao et al. [10], combine features derived
from various translation models to generate better query rewrites. Si et al.
[26] perform QR by utilizing multiple external biomedical resources. Hsu and
Taksa [13] present a data fusion framework suggesting that diverse query
formulations represent distinct evidence sources for inferring document
relevance. Later, Mohankumar et al. [20] generated diverse queries by
introducing a diversity-driven RL algorithm. For other tasks, recent works
demonstrated the benefits of ensemble strategies for prompting LLMs, including
self-consistency [31] for arithmetic and common sense tasks, Chain of
Verification [9] for improving factuality, and Diverse [16] for question
answering. However, zero-shot based ensemble methods for LLM have not been
explored for the Query Reformulation task, as we propose in this paper.

##  3 Proposed Approach: GenQREnsemble

In this section, we describe two variations of our proposed approach, for the
pre- and post-retrieval settings. In the pre-retrieval setting, a Query
Reformulation $R$ transforms a user’s expressed query $q_{0}$ into a novel
reformulated version $q_{r}$ to improve retrieval effectiveness for a given
search task (e.g., passage or document retrieval). We also consider the post-
retrieval setting, wherein the reformulator can incorporate additional
contextual information like document or passage-level feedback.

Figure 2: The complete flow and algorithm shown on the top right.

Pre-retrieval: We propose GenQREnsemble – an ensemble prompting based query
reformulator which uses $N$ diverse paraphrases of a QR instruction to enhance
retrieval. Specifically, we first use an LLM to paraphrase the instruction
$I_{1}$ to create $N$ instructions with different surface forms viz. $I_{1}$
to $I_{N}$. This is required to be done once. Each instruction is then
prompted along with the user’s query $q_{0}$ to generate instruction-specific
keywords. All the keywords are then appended to the original query, resulting
in a reformulated query, which is then executed against a document index $D$
to retrieve relevant documents $D^{r}$. The complete process and algorithm are
shown in Figure 2.

Post-retrieval: To assess how well our method can incorporate additional
context like document feedback, we introduce GenQREnsembleRF. Here, we prepend
the $N$ instructions described earlier with a fixed context capturing string
“Based on the given context information {C},” used111We found prepending the
string in the prompt performs better than appending it at the end in [29] to
create their PRF counterparts – where C is a space (‘ ’) delimited
concatenation of feedback documents C $=d_{1}+\ldots+d_{m}$, obtained either
as pseudo-relevance feedback from initial retrieval or manually chosen by the
user.

##  4 Experiments

# | Instruction
---|---
1 | Improve the search effectiveness by suggesting expansion terms for the query
2 | Recommend expansion terms for the query to improve search results
3 | Improve the search effectiveness by suggesting useful expansion terms for the query
4 | Maximize search utility by suggesting relevant expansion phrases for the query
5 | Enhance search efficiency by proposing valuable terms to expand the query
6 | Elevate search performance by recommending relevant expansion phrases for the query
7 | Boost the search accuracy by providing helpful expansion terms to enrich the query
8 | Increase the search efficacy by offering beneficial expansion keywords for the query
9 | Optimize search results by suggesting meaningful expansion terms to enhance the query
10 | Enhance search outcomes by recommending beneficial expansion terms to supplement the query

Figure 3: Reformulation instructions generated ($N$=10).

We now describe the experiments and analysis performed for different retrieval
settings.

To instruct the LLM to generate query reformulations, we start with the
instruction empirically chosen by Wang et al. [29] – as our base QR
instruction $I_{1}$. We use this instruction to generate $N$ paraphrases of
the instruction ($N=10$). To this aim, we invoke GPT-3.5 API with the
paraphrase generating prompt, namely, $I_{p}$=Generate 10 paraphrases for the
following instruction:– and the base QR instruction $I_{1}$ to obtain $I_{2}$
to $I_{10}$. These paraphrases serve as our instruction set for subsequent
experiments.

For generating the actual query reformulations, we employ flan-t5-xxl [7], an
instruction-tuned model. The FlanT5 set of models is created by fine-tuning
the text-to-text transformer model, T5 [25] on instruction data of a variety
of NL tasks. We use the checkpoint222https://huggingface.co/google/flan-t5-xxl
provided through HuggingFace’s Transformers library [34]. Nucleus sampling is
performed with a cutoff probability of 0.92 keeping the top 200 tokens (top_k)
and a repetition penalty of 1.2.

For evaluation, we use four popular benchmarks through IRDataset [17]’s
interface: 1)TP19: TREC 19 Passage Ranking which uses the MSMarco dataset [21,
14] consisting of search engine queries. 2)TR04: TREC Robust 2004 Track, a
task intended for testing poorly performing topics. In our experiments, we use
the Title as our choice of query. And two tasks from the BEIR [28] benchmark
3)WT: Webis Touche [4] for argument retrieval 4)DE: DBPedia Entity Retrieval
[12].

###  4.1 Baselines:

We compare our work against the following using the Pyterrier [18] framework.
For all the post-retrieval experiments, we use 5 documents as feedback.
With BM25 Retriever:

  * •

BM25: Here, we retrieve using raw queries without any reformulation

  * •

FlanQR [29]: We implement Wang et al’s single-instruction zero-shot QR [29]
which is also a specific case of GenQREnsemble when N=1

  * •

BM25+RM3 [1]: BM25 retrieval with RM3 expanded queries (#feedback terms=10)

  * •

BM25+FlanPRF [29]: BM25 retrieval with FlanPRF expanded queries

With Neural Reranking: Here, we re-evaluate the above settings in conjunction
with a MonoT5 neural reranker [24] with all other parameters constant.

  * •

BM25+MonoT5: BM25 retrieval using raw queries, re-ranked with MonoT5 model
[24]

  * •

FlanQR+MonoT5: BM25 retrieval with FlanQR reformulations, re-ranked with
MonoT5 model

  * •

BM25+RM3+MonoT5: BM25 retrieval with RM3 expanded queries, re-ranked with
MonoT5 model

  * •

BM25+FlanPRF+MonoT5: BM25 retrieval with FlanPRF expanded queries, re-ranked
with MonoT5 model

##  5 Results and Analysis

We now report the results of query reformulation for pre- and post-retrieval
settings.

###  5.1 Pre-Retrieval Performance

Figure 4: nDCG@10 Scores of GenQREnsemble and FlanQR relative to BM25

We first compare the retrieval performances of raw queries and reformulations
from FlanQR, and GenQREnsemble in Table 1.GenQREnsemble outperforms the raw
queries as well as generates better reformulations than FlanQR’s reformulated
queries across all the four benchmarks over a BM25 retriever, indicating the
usefulness of paraphrasing initial instructions. On TP19, nDCG@10 and MAP
improve significantly with relative improvements of 18% and 24% respectively.
This is further validated through the querywise analysis shown in Figure 4 –
Relative to BM25, nDCG@10 scores of GenQREnsemble (shown in green) are overall
better than FlanQR (shown in blue).GenQREnsemble seems more robust too as it
avoids drastic degradation in at least 6 queries on which FlanQR fails.

Table 1: Performance of GenQREnsemble on the four benchmarks. $\alpha$ denotes
significant improvements (paired t-test with Holm-Bonferroni correction,
$p<0.05$) over FlanQR. +% indicates % improvements relative to FlanQR (as
whole numbers).

Evaluation Set | TREC Passage 19 | TREC Robust 04 | Webis Touche | DBpedia Entity
---|---|---|---|---
Setting | nDCG@10 | MAP | MRR | P@10 | nDCG@10 | MRR | nDCG@10 | MAP | MRR | nDCG@10 | MAP | MRR
BM25 | .480 | .286 | .642 | .426 | .434 | .154 | .260 | .206 | .454 | .321 | .168 | .297
FlanQR | .477 | .302 | .593 | .473 | .483 | .151 | .315 | .241 | .511 | .342 | .196 | .345
FlanQRβ=.05 | .511 | .323 | .621 | .469 | .477 | .150 | .276 | .221 | .476 | .353 | .188 | .339
GenQREnsemble |  .564α+18% |  .375α+24% |  .706+19% |  .500α+6% |  .513α+6% |  .159+6% |  .317+1% |  .257+6% |  .555+9% |  .374α+9% |  .212α+8% |  .376α+9%
GenQREnsembleβ=.05 | .575α | .377α | .714 | .502α | .512α | .159 | .292 | .242 | .489 | .377α | .212α | .380α
BM25+MonoT5 | .718 | .477 | .881 | .492 | .513 | .173 | .299 | .216 | .525 | .414 | .249 | .444
FlanQR+MonoT5 | .707 | .486 | .847 | .490 | .510 | .170 | .292 | .215 | .530 | .415 | .255 | .446
GenQREnsemble+MonoT5 |  .722+2% |  .503+3% | .862+2% | .484-1% | .506-1% | .170 | .298+3% |  .219+2% |  .548+3% |  .420+1% |  .258+1% |  .450+1%

We further look at GenQREnsemble under the neural reranker setting shown at
the bottom half of Table 1. In three of the four settings, viz., TP19, WT, and
DE, GenQREnsemble is preferable to its zero-shot variant, FlanQR. Evidently,
the gains of both the zero-shot approaches in the traditional setting are
stronger vis-à-vis the neural setting. We hypothesize this could be due to
GenQREnsemble and FlanQR both expanding the query via incorporating
semantically similar but lexically different keywords. Comparatively, neural
models are adept at capturing notions of semantic similarity and might benefit
less with query expansion. This also is in line with Weller et al.’s [32]
recent analysis on the non-ensemble variant.

###  5.2 Post-Retrieval Performance

Table 2: Comparison of PRF performance on the TREC 19 Passage Ranking Task

| With BM25 Retriever | With Neural Reranking
---|---|---
Setting | nDCG@10 | nDCG@20 | MAP | MRR | nDCG@10 | nDCG@20 | MAP | MRR
BM25 | .480 | .473 | .286 | .642 | .718 | .696 | .477 | .881
RM3 | .504 | .496 | .311 | .595 | .716 | .699 | .480 | .858
FlanPRF | .576 | .553 | .363 | .715 | .722 | .703 | .486 | .874
GenQREnsembleRF |  .585+2% |  .560+1% |  .373+3% |  .753+5% |  .729+1% |  .706+1% |  .501+3% |  .894+2%
FlanPRF (Oracle) | .753 | .728 | .501 | .936 | .742 | .734 | .545 | .881
GenQREnsembleRF (Oracle) |  .820α+9% |  .773+6% |  .545+9% |  .977+4% |  .756+2% |  .751+2% | .545 |  .897+2%

We now investigate if GenQREnsembleRF can effectively incorporate PRF in Table
2. We find that GenQREnsembleRF improves retrieval performance as compared to
other PRF approaches and is able to incorporate feedback from a BM25 retriever
better than RM3 as well as its zero-shot counterpart. To assess if
GenQREnsembleRF and FlanPRF can at all benefit from incorporating relevant
documents, we perform oracle testing by providing the highest relevant gold
documents as context. We find that GenQREnsembleRF is able to improve over
GenQREnsemble (without feedback) showing that it is able to capture context
effectively as well as benefit from it. Further, it can incorporate relevant
feedback better than its single-instruction counterpart FlanPRF. We notice
improvements even under the neural reranker setting as GenQREnsembleRF
outperforms RM3 and FlanPRF. Besides, the oracle improvements are higher with
only a BM25 retriever as compared to when a neural reranker is introduced.

Figure 5: Effect of feedback documents under sparse (BM25) and neural (MonoT5)
rankers

We further evaluate the effect of varying the number of feedback documents
from 0 to 5. We notice that resorting to an ensemble approach is highly
beneficial. In the BM25 setting, the ensemble approach seems always
preferable. Under the neural reranker setting too,GenQREnsembleRF almost
always outperforms FlanPRF.

##  6 Conclusions

Zero-shot QR is advantageous since it does not rely on any labeled relevance
judgements and allows eliciting pre-trained knowledge in the form of keywords
by prompting the model with the original query and appropriate instruction. By
introducing GenQREnsemble, we show that zero-shot performance can be further
enhanced by using multiple views of the initial instruction. We also show that
the extension GenQREnsembleRF is able to effectively incorporate relevance
feedback, either automated or from users. While generative QR greatly benefits
from our ensemble approach, the proposed methods come at a cost of potentially
increased latency, but this is becoming less problematic with the increased
availability of batch inference for LLMs. The proposed ensemble approach could
also be applied to other settings, for example, to address different aspects
of queries or metrics to optimize, or to better control the generated
reformulations.

## References

  * [1] Abdul-Jaleel, N., Allan, J., Croft, W.B., Diaz, F., Larkey, L., Li, X., Smucker, M.D., Wade, C.: Umass at trec 2004: Novelty and hard. Computer Science Department Faculty Publication Series p. 189 (2004)
  * [2] Alaofi, M., Gallagher, L., Sanderson, M., Scholer, F., Thomas, P.: Can generative llms create query variants for test collections? an exploratory study. In: Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’23). pp. 1869–1873. Association for Computing Machinery, New York, NY, USA (2023). https://doi.org/10.1145/3539618.3591960
  * [3] Arora, S., Narayan, A., Chen, M.F., Orr, L., Guha, N., Bhatia, K., Chami, I., Re, C.: Ask me anything: A simple strategy for prompting language models. In: The Eleventh International Conference on Learning Representations (2022)
  * [4] Bondarenko, A., Fröbe, M., Beloucif, M., Gienapp, L., Ajjour, Y., Panchenko, A., Biemann, C., Stein, B., Wachsmuth, H., Potthast, M., et al.: Overview of touché 2020: argument retrieval. In: Experimental IR Meets Multilinguality, Multimodality, and Interaction: 11th International Conference of the CLEF Association, CLEF 2020, Thessaloniki, Greece, September 22–25, 2020, Proceedings 11. pp. 384–395. Springer (2020)
  * [5] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J.D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.: Language models are few-shot learners. Advances in neural information processing systems 33, 1877–1901 (2020)
  * [6] Carpineto, C., Romano, G.: A survey of automatic query expansion in information retrieval. Acm Computing Surveys (CSUR) 44(1), 1–50 (2012)
  * [7] Chung, H.W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fedus, W., Li, Y., Wang, X., Dehghani, M., Brahma, S., et al.: Scaling instruction-finetuned language models. arXiv preprint arXiv:2210.11416 (2022)
  * [8] Dhole, K., Gangal, V., Gehrmann, S., Gupta, A., Li, Z., Mahamood, S., Mahadiran, A., Mille, S., Shrivastava, A., Tan, S., et al.: Nl-augmenter: A framework for task-sensitive natural language augmentation. Northern European Journal of Language Technology 9(1) (2023)
  * [9] Dhuliawala, S.Z., Komeili, M., Xu, J., Raileanu, R., Li, X., Celikyilmaz, A., Weston, J.E.: Chain-of-verification reduces hallucination in large language models (2023)
  * [10] Gao, J., Xie, S., He, X., Ali, A.: Learning lexicon models from search logs for query expansion. In: Tsujii, J., Henderson, J., Paşca, M. (eds.) Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. pp. 666–676. Association for Computational Linguistics, Jeju Island, Korea (Jul 2012), https://aclanthology.org/D12-1061
  * [11] Gao, L., Ma, X., Lin, J., Callan, J.: Precise zero-shot dense retrieval without relevance labels. In: Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1762–1777 (2023)
  * [12] Hasibi, F., Nikolaev, F., Xiong, C., Balog, K., Bratsberg, S.E., Kotov, A., Callan, J.: Dbpedia-entity v2: a test collection for entity search. In: Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 1265–1268 (2017)
  * [13] Hsu, F.D., Taksa, I.: Comparing rank and score combination methods for data fusion in information retrieval. Information Retrieval 8(3), 449–480 (2005)
  * [14] Jagerman, R., Zhuang, H., Qin, Z., Wang, X., Bendersky, M.: Query expansion by prompting large language models. arXiv preprint arXiv:2305.03653 (2023)
  * [15] Li, H., Mourad, A., Zhuang, S., Koopman, B., Zuccon, G.: Pseudo relevance feedback with deep language models and dense retrievers: Successes and pitfalls. ACM Transactions on Information Systems 41(3), 1–40 (2023)
  * [16] Li, Y., Lin, Z., Zhang, S., Fu, Q., Chen, B., Lou, J.G., Chen, W.: Making language models better reasoners with step-aware verifier. In: Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 5315–5333 (2023)
  * [17] MacAvaney, S., Yates, A., Feldman, S., Downey, D., Cohan, A., Goharian, N.: Simplified data wrangling with ir_datasets. In: Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 2429–2436 (2021)
  * [18] Macdonald, C., Tonellotto, N., MacAvaney, S., Ounis, I.: Pyterrier: Declarative experimentation in python from bm25 to dense retrieval. In: Proceedings of the 30th acm international conference on information & knowledge management. pp. 4526–4533 (2021)
  * [19] Mo, F., Mao, K., Zhu, Y., Wu, Y., Huang, K., Nie, J.Y.: Convgqr: Generative query reformulation for conversational search. In: Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 4998–5012 (2023)
  * [20] Mohankumar, A.K., Begwani, N., Singh, A.: Diversity driven query rewriting in search advertising. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. pp. 3423–3431 (2021)
  * [21] Nguyen, T., Rosenberg, M., Song, X., Gao, J., Tiwary, S., Majumder, R., Deng, L.: Ms marco: A human-generated machine reading comprehension dataset (2016)
  * [22] Nogueira, R., Lin, J., Epistemic, A.: From doc2query to doctttttquery. Online preprint 6(2) (2019)
  * [23] Peng, B., Li, C., He, P., Galley, M., Gao, J.: Instruction tuning with gpt-4. arXiv preprint arXiv:2304.03277 (2023)
  * [24] Pradeep, R., Nogueira, R., Lin, J.: The expando-mono-duo design pattern for text ranking with pretrained sequence-to-sequence models. arXiv preprint arXiv:2101.05667 (2021)
  * [25] Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., Liu, P.J.: Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research 21(140), 1–67 (2020)
  * [26] Si, L., Lu, J., Callan, J.: Combining multiple resources, evidences and criteria for genomic information retrieval. In: TREC (November 2006)
  * [27] Srivastava, A., Rastogi, A., Rao, A., Shoeb, A.A.M., Abid, A., Fisch, A., Brown, A.R., Santoro, A., Gupta, A., Garriga-Alonso, A., et al.: Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research (2023)
  * [28] Thakur, N., Reimers, N., Rücklé, A., Srivastava, A., Gurevych, I.: Beir: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In: Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2) (2021)
  * [29] Wang, X., MacAvaney, S., Macdonald, C., Ounis, I.: Generative query reformulation for effective adhoc search. arXiv preprint arXiv:2308.00415 (2023)
  * [30] Wang, X., Macdonald, C., Tonellotto, N., Ounis, I.: Colbert-prf: Semantic pseudo-relevance feedback for dense passage and document retrieval. ACM Transactions on the Web 17(1), 1–39 (2023)
  * [31] Wang, X., Wei, J., Schuurmans, D., Le, Q.V., Chi, E.H., Narang, S., Chowdhery, A., Zhou, D.: Self-consistency improves chain of thought reasoning in language models. In: The Eleventh International Conference on Learning Representations (2022)
  * [32] Weller, O., Lo, K., Wadden, D., Lawrie, D., Van Durme, B., Cohan, A., Soldaini, L.: When do generative query and document expansions fail? a comprehensive study across methods, retrievers, and datasets. In: Graham, Y., Purver, M. (eds.) Findings of the Association for Computational Linguistics: EACL 2024. pp. 1987–2003. Association for Computational Linguistics, St. Julian’s, Malta (Mar 2024), https://aclanthology.org/2024.findings-eacl.134
  * [33] Wiher, G., Meister, C., Cotterell, R.: On decoding strategies for neural text generators. Transactions of the Association for Computational Linguistics 10, 997–1012 (2022)
  * [34] Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., et al.: Transformers: State-of-the-art natural language processing. In: Proceedings of the 2020 conference on empirical methods in natural language processing: system demonstrations. pp. 38–45 (2020)
  * [35] Yu, H., Xiong, C., Callan, J.: Improving query representations for dense retrieval with pseudo relevance feedback. In: Proceedings of the 30th ACM International Conference on Information & Knowledge Management. pp. 3592–3596 (2021)
  * [36] Zhao, Z., Wallace, E., Feng, S., Klein, D., Singh, S.: Calibrate before use: Improving few-shot performance of language models. In: International conference on machine learning. pp. 12697–12706. PMLR (2021)