On Periodic Points in Covering Systems

We consider a continuous mapping $f$: $\mathbb{R}\to\mathbb{R}$, and $k$ closed intervals $I_{1},I_{2},...,I_{k}$. Throughout this paper, $f^{l}$ denotes the $l$-th iterate of $f$. And all the mappings are assumed to be continuous unless otherwise noted.

This concept was first introduced by S. A. Bogatyi and E. T. Shavgulidze in their paper [1], when they tried to obtain an analogue of Sharkovskii’s theorem for an arbitrary tree. They proved the existence of a periodic point of period $\leq g(n)$ in a covering system and established an upper bound for $g(n)$ $(g(n)\leq 2(n^{2}-1)g(n-1)^{n-2})$. Moreover, they showed $g(n)=n$ for $n\leq 4$ and conjectured in the remark that $g(n)=n$ holds for all $n\in\mathbb{N}$, which is proved in this paper as the main theorem.

We will prove this theorem by a discretization method, which reduces the initial problem to a lemma in combinatorics. The main idea is to cut the intervals into small subintervals and perturb the mapping $f$ to get a cyclic permutation. And the proof of the theorem is completed by observing a property of cyclic elements of $S_{n}$.

The proof of the main theorem 1.2 will be divided into several steps and discussed in the following sections. We now state a well-known proposition which will be frequently used in the proof of theorem 1.2.

This fact is an easy consequence of the intermediate value theorem in calculus so we omit the proof. And we will see later that for $k$ larger, most cases can be reduced to this fundamental one.

We would like to end this introduction with the statement of the main lemma used in the proof of theorem 1.2, which studies the properties of cyclic permutations. Actually, this lemma is an extension of a lemma proved in Sharkovskii’s celebrated paper [2]. See the remark below.

Now we can state our main lemma.

We organize the paper as follows. In section 2, we introduce the discretization method and reduce theorem 1.2 in dynamics to a lemma in combinatorics. Then in section 3, we prove the equivalence of the lemma in section 2 and the one stated above. Finally in section 4, we prove lemma 1.6 .

In this section we show that Theorem 1.2 can be proved by solving another discrete problem related to it. The main idea is to divide the initial intervals into smaller subintervals, such that the image of each subinterval under $f$ contains the whole of some other subintervals, not just part of them. However, it may happen that no matter how you divide the intervals, there will be an interval whose image under $f$ contains only part of another interval. What saves us here is that, we can consider perturbation of $f$ if the intervals are cut into enough small pieces. Indeed, we will use the following lemma:

Now we can introduce the discrete problem related to Theorem 1.2. To begin with, we make a technical assumption on the initial covering system in Lemma 2.1. (See remark 2.4 for the reason). Namely, if $I_{j}=[a_{j},b_{j}]$ and $f(I_{j})=[c_{j},d_{j}]$ in the given covering system $(I_{1},I_{2},\ldots,I_{k};f)$, then we can assume $f(\{a_{j},b_{j}\})=\{c_{j},d_{j}\}$ without loss of generality, since we can replace $I_{j}$ by a smaller subinterval if necessary.

Let $a_{1}<b_{1}<a_{2}<b_{2}<\ldots<a_{k}<b_{k}$ be all the end points of the intervals $I_{1},\ldots,I_{k}$ and denote $M_{0}=\{a_{1},b_{1},\ldots,a_{k},b_{k}\}$. Consider their images $f(M_{0})=\{f(a_{1}),\ldots,f(b_{k})\}$ and we eliminate the points which don’t belong to $I_{1}\cup\ldots\cup I_{k}$ to obtain a set $S_{1}\subseteq f(M_{0})$. Put $M_{1}=M_{0}\cup S_{1}$. Inductively, in each step we consider the image of $M_{i}$ under the mapping $f$ and we eliminate those points dropping out of $I_{1}\cup...\cup I_{k}$ to get a set $S_{i+1}\subseteq f(M_{i})$. Then let $M_{i+1}=M_{i}\cup S_{i+1}$.

Finally we obtain a sequence of sets $M_{0}\subseteq M_{1}\subseteq\ldots\subseteq M_{i}\subseteq\ldots$, where each $M_{i}$ contains the images of the initial end point set $M_{0}$ under {$id,f,f^{2},\ldots,f^{i}$} except for those dropping out of $I_{1}\cup\ldots\cup I_{k}$.

Then we can find a sufficiently large integer $N$ such that $\forall x\in M_{N}-M_{N-1}$, $dist(x,M_{N-1})<\delta$, where $\delta$ comes from Lemma 2.1. Such $N$ exists because if not, there will be a sequence of disjoint points in $[a_{1},b_{k}]$ with pairwise distance larger than $\delta$, which is absurd. Therefore, we can take small perturbation of $f$ to get a map $\tilde{f}$ with $\lVert\tilde{f}-f\rVert<\delta$, and $\widetilde{M_{N-1}}=\widetilde{M_{N}}$ for $\tilde{f}$. Indeed, we just move each point $(x_{0},f(x_{0}))\in M_{N-1}\times M_{N}$ on the graph of $f$ to the nearest point $(x_{0},y_{0})\in\{x_{0}\}\times M_{N-1}$ preserving the continuity and the covering property of $f$. For example, in a neighborhood of each $x_{0}\in M_{N}$, we can define $\tilde{f}(x)=f(x)\pm\sigma\phi(x-x_{0})$, where $0\leq\phi\leq 1$ is a cut-off function, $\phi(0)=1$, $\sigma<\delta$ is chosen so that $\tilde{f}(x_{0})\in M_{N-1}$. And for different $x_{0}$ we choose different signs $\pm$ so that $(I_{1},I_{2},\ldots,I_{k};\tilde{f})$ is still a covering system. (See Figure 1 and 2.)

Thus, if we divide the intervals into small pieces using the points in $\widetilde{M_{N}}$, then $\tilde{f}$ will have the nice property that the image of each subinterval contains entirely another one or more subintervals. In other words, $\tilde{f}$ can be regarded as a discrete mapping from $\{1,2,\ldots,n\}$ to {subsets of $\{1,2,\ldots,n\}$}. Here each number $j$ represents a small piece of interval $J_{j}$. And $j^{\prime}\in f(j)$ if $f(J_{j})\supseteq J_{j^{\prime}}$. Note that the image of some interval may be empty, since we ignore the part outside $I_{1}\cup\ldots\cup I_{k}$. And we only care about the interval determined by $\{f(a),f(b)\}$ if $a,b\in\widetilde{M_{N}}$, although the image $f([a,b])$ may be larger.

It should also be remarked here that the only useful information of $f$ on the so called “gaps” (see [1]) between two adjacent intervals $I_{i}$ and $I_{i+1}$ is the behavior of the end points of each gap. In other words, for the image $f(J_{j})$ of each small subinterval $J_{j}$, we only focus on the part $f(J_{j})\cap(I_{1}\cup\ldots\cup I_{k})$. This is the reason why we eliminate the points outside $I_{1}\cup\ldots\cup I_{k}$ in each step. We will see later that this information is enough for the proof.

To sum up, once we have a mapping $f$ satisfying the conditions in Lemma 2.1, we can find an $\tilde{f}$ close enough to $f$, which also satisfies the conditions but can be viewed as a discrete mapping. Such $f$ and $\tilde{f}$ are counterexamples to Theorem 1.2. Therefore, if we argue by contradiction, we can easily see that Theorem 1.2 is a corollary of the following lemma, whose proof will be discussed later.

Although lemma 2.3 reduces Theorem 1.2 to a discrete problem, it is not satisfactory since it involves something inconvenient to deal with, like convex hull and partition. In the following we will simplify the conditions in lemma 2.3 and find another description of it which only depends on the own property of a permutation. And the main goal of this section is to prove the equivalence of lemma 1.6 and lemma 2.3.

Let $f$ be in lemma 2.3. We can assume further:

(1)$\quad\forall i\neq j$, $f(i)\cap f(j)=\emptyset$.

(2)$\quad\forall i$, $f(i)\neq\emptyset$.

(3)$\quad\forall i$, $f(i)$ contains exactly one element.

(4)$\quad f$ is a cyclic permutation in the symmetric group $S_{n}$, $i.e.$, $f$ can be written as $(i_{1}i_{2}\ldots i_{n})$.

Indeed, (1) can be realized since we can move out the common part of $f(i)$ and $f(j)$ from one of them without changing the property $\bigcup_{i=1}^{n}f(i)=\{1,2,\ldots,n\}$.

(2) is also satisfied because we can eliminate the number $i$ and restrict the mapping $f$ to $\{1,2,\ldots,n\}-\{i\}$ if necessary.

(3) is a consequence of (1), (2) and the condition $\bigcup_{i=1}^{n}f(i)=\{1,2,\ldots,n\}$. Indeed, one can apply the operations in (1) and (2) repeatedly until a minimal case. This couldn’t be an endless process because we are dealing with finite sets. And one can prove that the minimal set cannot be empty because the covering property is preserved.

For (4), note that $f\in S_{n}$ because of (3). Suppose $f$ is not cyclic. Then choose an orbit $(i_{1}\ldots i_{m})$ of $f$ ($m<n$) and restrict both $f$ and the partition $I_{1},\ldots,I_{k}$ to $\{i_{1},\ldots,i_{m}\}$.

In conclusion, we obtain:

Now we turn to the proof of the equivalence of lemma 2.3 and lemma 1.6. (See also Definition 1.4.)

Recall that in one-dimensional dynamics we often consider a directed graph associated to a periodic orbit (For more details, see [3] or chapter 1 of [4]). Namely, if $f$ is a cyclic permutation in Definition 1.4, we can construct a directed graph $\Gamma_{f}$ with $(n-1)$ vertices $\{A_{1},A_{2},\ldots,A_{n-1}\}$, where $A_{i}=\{i,i+1\}$ is defined in 1.4. And there is an edge from $A_{i}$ to $A_{j}$ if and only if $convf(A_{i})\supseteq A_{j}$.

Thus, we see directly from the definition that the following proposition holds:

Using directed graphs, we can complete the proof of the equivalence of the two lemmas.

Therefore, we have reduced the initial problem on the existence of periodic points to a lemma in combinatorics on the properties of cyclic permutations. In the next section, we will prove the lemma and that will complete the proof of theorem 1.2.

We end this section with some examples of cyclic permutations whose characteristic sequences are known.

We finally prove lemma 1.6 in this section. We first recall some definitions and notations from one-dimensional dynamics and linear algebra.

We denote the field $\{0,1\}$ with exactly two elements by $\mathbb{F}_{2}$. And we say $A\equiv B\pmod{2}$ for integer valued matrices $A$ and $B$, when $A=B$ as matrices in $M(\mathbb{F}_{2})$.

A proof of this proposition can be found in [4], Chapter 1, Propositon 20. And for readers’ convenience, we give a sketch of proof here.

We need the following lemma:

With these results, we can compute the characteristic polynomial of $T_{f}$.