Hausdorff Dimension of closure of cycles in $d$ -maps on the circle

Nicholas Payne Northeastern University, Boston, MA 02115, USA [email protected] and Mrudul Thatte Columbia University, New York, NY 10027, USA [email protected]

Abstract.

We study the dynamics of the map $x\mapsto dx(\text{mod }1)$ on the unit circle. We characterize the invariant finite subsets of this map which are called cycles and are graded by their degrees. By looking at the combinatorial properties of the base-d expansion of the elements in the cycles, we prove a conjecture of Curt McMullen that the Hausdorff dimension of the closure of degree-m cycles is equal to $\log m/\log d$ .

1. Introduction

Degree- $d$ maps on the unit disk have many interesting geometric, topological and analytic properties, which are closely related to hyperbolic geometry. The dynamics of these maps has an important application in classifying dynamical systems generated by polynomials in single complex variable [goldberg1992fixed] and it provides useful information about Julia sets and Mandelbrot sets [keller2000invariant, douady1984etude]. To get an understanding of this family of maps, people studied the behaviour of these maps restricted to the boundary unit circle [goldberg1992fixed, goldberg1993fixed]. In the paper [mcmullen2010dynamics], McMullen gave a complete description of simple (i.e. degree 1) cycles of these boundary maps, showing that those simple cycles are an analogue of simple closed geodesics on hyperbolic surfaces in the sense that the closure of union of simple cycles has Hausdorff Dimension 0 and the closure of union of simple closed geodesics has Hausdorff Dimension 1.

Here we consider degree- $d$ holomorphic maps from the unit disk onto itself. We focus on one such map $z\mapsto z^{d}$ . The restriction of this map to the boundary circle is equivalent to the map $x\mapsto dx\ \text{(mod 1)}$ on $\mathbb{R}/\mathbb{Z}.$ Combinatorial features of this map has been studied recently in [PZ, zakeri2021cyclic, tan2022counting]. In this paper, we study cycles of higher degrees in this map, and in particular, calculate the Hausdorff dimension of their closure, which confirms a conjecture of McMullen.

Definition 1 ( $d$ -map).

Let $d\in\mathbb{N}$ . We define a $d$ -map to be the map on the unit circle $S^{1}=\mathbb{R}/\mathbb{Z}$ given by

(1)

x\mapsto dx\ \text{(mod 1)},\forall x\in S^{1}.

In other words, if the base- $d$ expansion of a point is $(0.b_{1}b_{2}b_{3}....)_{d}$ , then $d$ -map takes it to the point whose base- $d$ expansion is $(0.b_{2}b_{3}b_{4}....)_{d}$ .

We say that a $d$ -map has degree $d$ .

Definition 2 (Cycle).

Let $d$ be a positive integer greater than 1. A finite set $C\subset S^{1}$ is called a cycle for the $d$ -map if and only if the $d$ -map restricted to $C$ is a transitive permutation. In terms of the base- $d$ expansion, $C$ is given by

(2)

C=\{(0.\overline{b_{i}b_{i+1}....b_{n}b_{1}b_{2}....b_{i-1}})_{d}|1\leq i\leq n\},

where $n$ is the size of the cycle and $b_{1},b_{2},...,b_{n}$ are fixed digits in $\{0,1,...,d-1\}$ .

Here are some examples of cycles. Consider the case $d=2$ . Here, $\{0\}=\{(0.\overline{0})_{2}\}$ is the only 1-element cycle and $\{\frac{1}{3},\frac{2}{3}\}=\{(0.\overline{01})_{2},(0.\overline{10})_{2}\}$ is the only 2-element cycle. For an integer $n>2$ , there are multiple $n$ -element cycles. For example, there are two 3-element cycles: $\{\frac{1}{7},\frac{2}{7},\frac{4}{7}\}$ and $\{\frac{3}{7},\frac{5}{7},\frac{6}{7}\}$ .

Now we define an important invariant of a cycle, called degree.

Definition 3 (Degree of a cycle).

Let $d$ be a positive integer greater than 1. Let $C$ be a cycle for $d$ -map. The degree of $C$ is the smallest non-negative integer $m$ for which there exists a degree- $m$ map $f:S^{1}\rightarrow S^{1}$ such that $f$ and the $d$ -map agree on $C$ . It is denoted by $deg(C)$ .

Remark 1.

Note that $0\leq deg(C)\leq d$ by definition.

Remark 2.

The cycles which contain only one element are fixed points of $d$ -map and have degree 0. All other cycles have positive degree.

Now, we give two examples.

Example 1.

Consider $d=2$ and $C=\{\frac{3}{7},\frac{5}{7},\frac{6}{7}\}$ . Under the 2-map,

\frac{3}{7}\mapsto\frac{6}{7},\ \frac{5}{7}\mapsto\frac{3}{7},\ \frac{6}{7}\mapsto\frac{5}{7}.

Here the cyclic order of the points in $C$ is preserved. As we jump on the points in the cycle from $\frac{3}{7}\rightarrow\frac{5}{7}\rightarrow\frac{6}{7}$ (jump over 0) and back to $\frac{3}{7}$ , we complete one full circle. As we jump on the images of these points, $\frac{6}{7}\rightarrow$ (jump over 0 to) $\frac{3}{7}\rightarrow\frac{5}{7}$ and back to $\frac{6}{7}$ , again we complete one circle. This means that the degree of $C$ is 1. We can show this by explicitly constructing a suitable map $f:S^{1}\to S^{1}$ as follows:

f(x)=\left\{\begin{array}[]{l l}x+\frac{3}{7}&\quad\text{if $x\in\left[\frac{3}{7},\frac{4}{7}\right]$}\\ &\\ 3\left(x-\frac{4}{7}\right)&\quad\text{if $x\in\left[\frac{4}{7},\frac{5}{7}\right]$}\\ &\\ 2x-1&\quad\text{if $x\in\left[\frac{5}{7},\frac{6}{7}\right]$}\\ &\\ \frac{5}{7}+\frac{1}{4}\left(x-\frac{6}{7}\right)&\quad\text{if $x\in\left[\frac{6}{7},\frac{10}{7}\right]$}\\ \end{array}\right.

Observe that $f$ agrees with the 2-map, and it is of degree 1. As there are no maps with smaller degree, $deg(C)=1$ .

Example 2.

Consider $d=3$ and $C=\{\frac{1}{5},\frac{2}{5},\frac{3}{5},\frac{4}{5}\}$ . Under the 3-map,

\frac{1}{5}\mapsto\frac{3}{5},\ \frac{2}{5}\mapsto\frac{1}{5},\ \frac{3}{5}\mapsto\frac{4}{5},\ \frac{4}{5}\mapsto\frac{2}{5}.

So, as we jump on the points in the cycle from $\frac{1}{5}\rightarrow\frac{2}{5}\rightarrow\frac{3}{5}\rightarrow\frac{4}{5}$ (jump over 0) and back to $\frac{1}{5}$ , we complete one full circle. As we jump on the images of these points, $\frac{3}{5}\rightarrow$ (jump over 0 to) $\frac{1}{5}\rightarrow\frac{4}{5}\rightarrow$ (jump over 0 to) $\frac{2}{5}$ and back to $\frac{3}{5}$ , we complete two circles. So, the degree of $C$ is 2. We can show this by explicitly constructing a suitable map $f:S^{1}\to S^{1}$ as follows:

f(x)=\left\{\begin{array}[]{l l}\frac{3}{5}+4(x-\frac{1}{5})&\quad\text{if $x\in\left[\frac{1}{5},\frac{3}{10}\right]$}\\ &\\ 2(x-\frac{3}{10})&\quad\text{if $x\in\left[\frac{3}{10},\frac{2}{5}\right]$}\\ &\\ 3x-1&\quad\text{if $x\in\left[\frac{2}{5},\frac{3}{5}\right]$}\\ &\\ \frac{4}{5}+2(x-\frac{3}{5})&\quad\text{if $x\in\left[\frac{3}{5},\frac{7}{10}\right]$}\\ &\\ 4(x-\frac{7}{10})&\quad\text{if $x\in\left[\frac{7}{10},\frac{4}{5}\right]$}\\ &\\ \frac{2}{5}+\frac{1}{2}\left(x-\frac{4}{5}\right)&\quad\text{if $x\in\left[\frac{4}{5},\frac{6}{5}\right]$}\\ \end{array}\right.

Observe that $f$ agrees with the 3-map, and it is of degree 2. As there are no maps with smaller degree, $deg(C)=2$ .

Definition 4 (Closure of cycles).

Let $m,d\in\mathbb{N}$ with $1<d$ and $1\leq m\leq d$ . We define $E_{m,d}$ as the closure of the union of degree- $m$ cycles for $d$ -map.

(3)

E_{m,d}=\overline{\{c\in S^{1}|c\text{ is in a cycle of degree-$m$ for the $d$-map}\}}

Curtis McMullen discussed in [mcmullen2010dynamics] the simple (i.e. degree 1) cycles for the $d$ -map and and computed the Hausdorff Dimension of their closure $E_{1,d}$ . Recall that Hausdorff Dimension is defined as follows.

Definition 5 (Hausdorff Dimension).

The Hausdorff Dimension of a set $E$ is defined as

(4)

dim_{H}(E)=\inf\ \{\delta\geq 0|\ \inf\ \{\sum{r_{i}^{\delta}|E\subset\bigcup{B(x_{i},r_{i})}}\}=0\}.

Theorem 1 (McMullen).

Let $d$ be a positive integer greater than 1. Then $dim_{H}(E_{1,d})=0.$

In this paper, we generalize the above results by showing the following.

Theorem 2.

Let $m,d\in\mathbb{N}$ with $1<d$ and $1\leq m\leq d$ . Then,

dim_{H}(E_{m,d})=\frac{\log m}{\log d}.

This paper is organized in the following way:

In Section 2, we get a lower bound on the Hausdorff Dimension of $E_{m,d}$ by calculating the Hausdorff Dimension of a subset of $E_{m,d}$ .

In Section 3, we prove the upper bound by imitating the proof of Theorem 1 in paper [mcmullen2010dynamics] using combinatorial arguments, and conclude by proving Theorem 2.

2. Lower Bound

In this section, we define and study two useful invariants of a cycle called crossing number and Digit Portrait, which are directly related to the degree of the cycle. Then we use these properties to construct a subset of $E_{m,d}$ which has Hausdorff Dimension $\frac{\log m}{\log d}$ .

Definition 6 (Crossing).

Let $d$ be a positive integer greater than 1. Let $C=\{c_{1},c_{2},...,c_{n}\}$ be a cycle for $d$ -map such that

0<c_{1}<c_{2}<....<c_{n}<1

Let $c_{n+1}=c_{1}$ . For any $1\leq i\leq n$ , the pair $(c_{i},c_{i+1})$ is called a crossing generated by $\mathbf{C}$ (or simply a crossing) iff

(5)

0<dc_{i+1}\text{(mod 1)}<dc_{i}\text{(mod 1)}<1

The total number of such crossings is called the crossing number of C.

(6)

\eta(C)=\text{\# (crossings generated by C)}

Remark 3.

If $n=1$ , then there are no crossings. The crossing number is 0 which is the degree of 1-element cycles.

Remark 4.

As we jump on $S^{1}$ in the counterclockwise direction and trace the points of the cycle from $c_{1}\rightarrow c_{2}\rightarrow....\rightarrow c_{n}$ and (jump over 0) back to $c_{1}$ , we complete one full circle. When we trace the images of these points, $dc_{1}\text{(mod 1)}\rightarrow dc_{2}\text{(mod 1)}\rightarrow......\rightarrow dc_{n}\text{(mod 1)}$ and back to $dc_{1}\text{(mod 1)}$ , we may jump over 0 multiple times. Each time we jump over 0, we have a crossing. The crossing number of the cycle is equal to its degree. We provide a rigorous proof of this intuitive result below.

Lemma 1.

Let $d$ be a positive integer greater than 1. Let $C=\{c_{1},c_{2},...,c_{n}\}$ be a cycle for $d$ -map with $0<c_{1}<c_{2}<....<c_{n}<1$ . Then, the crossing number of $C$ is equal to its degree or

\eta(C)=deg(C)

Proof.

The case $n=1$ is obvious, so assume $n>1$ and let $c_{n+k}=c_{k}$ , for all $k\in\mathbb{N}.$

Let $1\leq i_{1}<i_{2}<...<i_{\eta(C)}\leq n$ be such that for all $1\leq t\leq\eta(C)$ , the pair $(c_{i_{t}},c_{i_{t}+1})$ is a crossing generated by $C$ .

First, we prove $deg(C)\geq\eta(C)$ . Assume for the sake of argument that $\eta(C)>deg(C)$ . We can divide $S^{1}$ or $[0,1)$ in intervals $I_{1},I_{2},...,I_{deg(C)}$ such that on each $I_{r}$ , there exists a continuous non-decreasing map $g_{r}$ to $[0,1)$ which agrees with the $d$ -map on $I_{r}\cap C$ .

Note that there are exactly $\eta(C)$ sets of the type $\{c_{i_{t}},c_{i_{t}+1},...c_{i_{t+1}}\}.$ By our assumption that $\eta(C)>deg(C),$ we can find a $t$ such that $\{c_{i_{t}},c_{i_{t}+1},...c_{i_{t+1}}\}\subset I_{r}$ for some $r$ . In other words,

0<g_{r}(c_{i_{t}+1})=dc_{i_{t}+1}\text{(mod 1)}<dc_{i_{t}}\text{(mod 1)}=g_{r}(c_{i_{t}})<1,

a contradiction of the non-decreasing nature of $g_{r}$ . Thus, $deg(C)\geq\eta(C)$ .

Now we prove that $deg(C)\leq\eta(C)$ by constructing an appropriate map $f:S^{1}\rightarrow S^{1}$ of degree $\eta(C)$ . To start, we divide $S^{1}$ into $\eta(C)$ intervals of the type $\left[\frac{c_{i_{t}}+c_{i_{t}+1}}{2},\frac{c_{i_{t+1}}+c_{{i_{t+1}}+1}}{2}\right]$ , each of which is mapped onto $S^{1}.$ We take the endpoints of each such interval to 0, and points of $C$ to their images under the $d$ -map. In between, we make $f$ linear. We define

f(x)=\left\{\begin{array}[]{l l}\frac{dc_{i_{t}+1}\text{(mod 1)}}{\frac{c_{i_{t}+1}-c_{i_{t}}}{2}}\ (x-\frac{c_{i_{t}}+c_{i_{t}+1}}{2})&\quad\text{if $x\in\left[\frac{c_{i_{t}}+c_{i_{t}+1}}{2},c_{i_{t}+1}\right]$}\\ &\\ dc_{i}\text{(mod 1)}+{\frac{dc_{i+1}\text{(mod 1)}-dc_{i}\text{(mod 1)}}{c_{i+1}-c_{i}}}\ (x-c_{i})&\quad\text{if $x\in\left[c_{i},c_{i+1}\right]\subset\left[c_{i_{t}+1},c_{i_{t+1}}\right]$}\\ &\\ dc_{i_{t+1}}\text{(mod 1)}+{\frac{1-dc_{i_{t+1}}\text{(mod 1)}}{\frac{c_{i_{t+1}+1}-c_{i_{t+1}}}{2}}}\ (x-c_{i_{t+1}})&\quad\text{if }x\in\left[c_{i_{t+1}},\frac{c_{i_{t+1}}+c_{{i_{t+1}}+1}}{2}\right]\end{array}\right.

where intervals are taken in counter-clockwise direction.

So, $f$ is a continuous function for all $t$ , and the restriction of $f$ gives a bijection

\left[\frac{c_{i_{t}}+c_{i_{t}+1}}{2},\frac{c_{i_{t+1}}+c_{{i_{t+1}}+1}}{2}\right)\leftrightarrow S^{1}.

Since $f$ has degree $\eta(C)$ and $f|_{C}$ agrees with the $d$ -map, by Definition 3, $deg(C)\leq\eta(C).$ This, combined with above, completes the proof.

∎

Now that we have established the relation between the degree and the crossing number of a cycle, we need a tool to estimate the crossing number. We observe that the crossing number of a cycle is related to the order of points in the cycle, and hence the digits in the base- $d$ expansion of points of the cycle. We define an invariant of the cycle called Digit Portrait which characterizes these digits.

Definition 7 (Digit Portrait).

Let $d$ be a positive integer greater than 1. Let $C$ be a cycle for $d$ -map. The Digit Portrait of $C$ is the non-decreasing map $F:\{0,1,2,...,(d-1)\}\rightarrow\{0,1,2,...,|C|\}$ which satisfies

F(j)=|\ C\ \cap\ [0,(j+1)/d)\ |\ \ \forall\ 0\leq j\leq(d-1)

F(j)=\text{\# (elements of $C$ whose base-$d$ expansion starts with a digit less than $j+1$)}.

Let $dig(C)$ be the number of distinct positive values taken by $F$ . Note that if a digit $j$ is absent in the base- $d$ expansion of a point in $C$ , then $F(j)=0$ or $F(j)=F(j-1)$ . So, $dig(C)$ is also the number of distinct digits which appear in the base- $d$ expansion of any point in $C$ . To estimate the crossing number of $C$ , we need the second interpretation of $dig(C)$ .

Example 3.

Consider $d=4$ and the cycle $C=\{(0.\overline{0012})_{4},(0.\overline{0120})_{4},(0.\overline{1200})_{4},(0.\overline{2001})_{4}\}$ . Note that

0=(0.0)_{4}<(0.\overline{0012})_{4}<(0.\overline{0120})_{4}<\frac{1}{4}=(0.1)_{4}<(0.\overline{1200})_{4}<\frac{2}{4}=(0.2)_{4}<(0.\overline{2001})_{3}<\frac{3}{4}=(0.3)_{4}

The Digit Portrait of $C$ is the map $F:\{0,1,2,3\}\rightarrow\{0,1,2,3,4\}$ given by:

F(0)=2,F(1)=3,F(2)=4,F(3)=4.

$F$ takes the values 2, 3 and 4. So, $dig(C)$ is 3. There are exactly 3 digits (0, 1 and 2) which appear in the base-4 expansion of the points in $C$ .

Now we establish the relation between $dig(C)$ and the crossing number of $C$ .

Lemma 2.

Let $d$ be a positive integer greater than 1, and $C=\{c_{1},c_{2},...,c_{n}\}$ be a cycle for the $d$ -map with $0<c_{1}<c_{2}<....<c_{n}<1$ and $n>1$ . Then, the crossing number of $C$ is at most the number of distinct digits which appear in the base- $d$ expansion of a point in $C$ . In other words,

\eta(C)\leq dig(C).

Proof.

Let $1\leq i<n$ . Let $c_{i}\in[j_{1}/d,(j_{1}+1)/d)$ and $c_{i+1}\in[j_{2}/d,(j_{2}+1)/d)$ . In other words, the base- $d$ expansions of $c_{i}$ and $c_{i+1}$ begin with the digits $j_{1}$ and $j_{2},$ respectively. Note that $j_{1}\leq j_{2}$ because $c_{i}<c_{i+1}$ .

If $j_{1}=j_{2}=j$ , then

0<dc_{i}\text{(mod 1)}=dc_{i}-j<dc_{i+1}-j=dc_{i+1}\text{(mod 1)}<1.

In this case, $(c_{i},c_{i+1})$ cannot be a crossing. So, $(c_{i},c_{i+1})$ is a crossing only if $j_{1}<j_{2},$ i.e., $c_{i}$ is the largest element of $C\cap\ [j_{1}/d,(j_{1}+1)/d)$ and $c_{i+1}$ is the smallest element of $C\ \cap\ [j_{2}/d,(j_{2}+1)/d)$ .

Thus, there are at most $(dig(C)-1)\ i$ ’s for which $1\leq i<n$ and $(c_{i},c_{i+1})$ is a crossing. For some cycles, $(c_{n},c_{1})$ is an additional crossing. So, there are at most $dig(C)\ i$ ’s for which $1\leq i\leq n$ and $(c_{i},c_{i+1})$ is a crossing. ∎

Together, Lemma 1 and Lemma 2 give a way of estimating the degree of a cycle by looking at the digits in the base- $d$ expansion of a point in the cycle. Now we use this to get a sufficient condition for a point to be in the closure of the cycles of fixed degree.

Lemma 3.

Let $m,d\in\mathbb{N}$ with $1\leq m\leq d$ and $1<d$ . Then, any point in $S^{1}$ whose base- $d$ expansion contains at most $m$ distinct digits lies in $E_{m,d}$ .

Proof.

Let $\alpha\in S^{1}.$ Let $\alpha={(0.\alpha_{1}\alpha_{2}\alpha_{3}.....)}_{d}$ such that $\forall\ r,\alpha_{r}\in\{b_{1},b_{2},...,b_{m}\}\subset\{0,1,...,(d-1)\}.$ Here, $b_{1},b_{2},...,b_{m}$ are fixed digits in base- $d$ such that $b_{1}<b_{2}<...<b_{m}.$

To prove that $\alpha$ lies in $E_{m,d}$ , we will show that for all $q\in\mathbb{N},$ there exists a degree- $m$ cycle $C$ for the $d$ -map that intersects $d^{-q}$ neighborhood of $\alpha$ . Any periodic point whose base- $d$ expansion contains exactly $m$ distinct digits is in a cycle of degree at most $m$ . To get the maximum possible degree, we need maximum possible crossings. This can be achieved with the following construction:

Let $N\in\mathbb{N}$ such that for all $1\leq t\leq m,$ $N$ is greater than the number of times $b_{t}$ appears in the first $q$ digits of $\alpha$ . Let $\langle b_{t}\rangle$ denote $b_{t}b_{t}b_{t}...b_{t}\ \ (N\text{\ times})$ . Consider the following point:

(7)

c={(0.\overline{\alpha_{1}\alpha_{2}\alpha_{3}...\alpha_{q}\langle b_{m}\rangle\langle b_{1}\rangle\langle b_{m-1}\rangle\langle b_{1}\rangle....\langle b_{2}\rangle\langle b_{1}\rangle b_{m}})}_{d}

Clearly, $c$ is in $d^{-q}$ neighborhood of $\alpha$ . It is a point of cycle $C=\{c_{1},c_{2},...c_{q+2N(m-1)+1}\}$ for the $d$ -map with $0<c_{1}<c_{2}<...<c_{q+2N(m-1)+1}$ .

Now we need to prove that $deg(C)=m$ . For each $1\leq t\leq m$ , let $i_{t}$ be such that the largest element of $C$ whose base- $d$ expansion starts with the digit $b_{t}$ is $c_{i_{t}}$ . Note that $c_{i_{1}}$ is at least ${(0.b_{1}b_{m})}_{d}$ . For $t>1$ , $\ c_{i_{t}}$ is at least ${(0.\langle b_{t}\rangle)}_{d}$ . For each $1\leq t<m,\ c_{i_{t}+1}$ is the smallest element of $C$ whose base- $d$ expansion starts with the digit $b_{t+1}$ . Note that the base- $d$ expansion of $c_{i_{t}+1}$ starts with $0.b_{t}\langle b_{1}\rangle$ .

So, for all $1\leq t<m$ ,

0<dc_{i_{t}+1}\text{(mod 1)}<dc_{i_{t}}\text{(mod 1)}<1,

i.e., $(c_{i_{t}},c_{i_{t}+1})$ is a crossing.

Note that $c_{q+2N(m-1)+1}=c_{i_{m}}$ and $c_{i_{m}+1}=c_{1}=c_{i_{1}}$ . So,

0<dc_{i_{m}+1}\text{(mod 1)}<{(0.b_{2})}_{d}<dc_{i_{m}}\text{(mod 1)}<1,

i.e., $(c_{i_{m}},c_{i_{m}+1})$ is a crossing.

Thus, the crossing number of $C$ is at least $m$ .

\eta(C)\geq m

From Lemma 2, we know that the crossing number of $C$ is at most the number of distinct digits in the base- $d$ expansion of a point $C$ , which in this case, is $m$ .

\eta(C)\leq dig(C)=m

Therefore, $\deg(C)=\eta(C)=m$ .
∎

The following result follows immediately.

Proposition 1.

$E_{d,d}=S^{1}$ . Thus, $dim_{H}(E_{d,d})=1=\frac{\log d}{\log d}.$

Proof.

Note that since base- $d$ has only $d$ digits, the set of all points of $S^{1}$ whose base- $d$ expansion contains at most $d$ distinct digits is $S^{1}$ itself. So, we have $S^{1}\subset E_{d,d}\subset S^{1}$ or $E_{d,d}=S^{1}.$

∎

Now, we use Lemma 3 to construct a subset of $E_{m,d}$ . Let $m$ and $d$ be positive integers with $d>1$ and $1\leq m\leq d$ , and let $A_{m,d}$ be the set of points in $S^{1}$ whose base- $d$ expansion contains the digits from 0 to $(m-1)$ only. Clearly, $A_{m,d}\subset E_{m,d}$ .

The structure of $A_{m,d}$ is similar to the structure of Cantor’s set. Here, we start with $X_{0}=[0,1]$ . Write $X_{0}$ in $d$ closed intervals of length $1/d$ . Let $X_{1}$ be union of first $m$ of these intervals.

X_{1}=\bigcup_{i=0}^{m-1}{[i/d,{(i+1)}/d]}

$X_{1}$ is the union of $m$ intervals of length $1/d$ . Divide each such interval in $d$ equal parts and take the first $m$ in $X_{2}.\ X_{2}$ is the union of $m^{2}$ intervals of length $1/{d^{2}}$ .

Repeat the process. If $X_{i}$ is the union of $m^{i}$ intervals of length $d^{-i}$ , then divide each such interval in $d$ equal parts and take the first $m$ in $X_{i+1}$ .

A_{m,d}=\bigcap_{i=0}^{\infty}{X_{i}}

Now we calculate the Hausdorff Dimension of $A_{m,d}$ .

Lemma 4.

$dim_{H}(A_{m,d})=\frac{\log m}{\log d}$ .

Proof.

First, we prove that the Hausdorff dimension of $A_{m,d}$ is at most $\frac{\log m}{\log d}$ . Let $\beta>0$ . Note that for all $i,A_{m,d}\subset X_{i}$ . So, for each $i$ , we have $m^{i}$ intervals of length $d^{-i}$ that form a covering of $A_{m,d}$ . Letting $\beta=\frac{\log m}{\log d}+\varepsilon$ for some $\varepsilon>0$ ,

\lim_{i\to\infty}{m^{i}{(d^{-i})}^{\beta}}=\lim_{i\to\infty}{m^{i}(d^{-i\varepsilon})((d^{\frac{\log m}{\log d}})^{-i})}=\lim_{i\to\infty}{d^{-i\varepsilon}}=0

This means that, for any $\beta>\frac{\log m}{\log d}$ , we can cover $A_{m,d}$ such that the summation of $\beta$ powers of the lengths of the intervals in the cover is as small as we like. So,

dim_{H}(A_{m,d})\leq\frac{\log m}{\log d}.

Now we need to show that the Hausdorff dimension of $A_{m,d}$ is at least $\frac{\log m}{\log d}$ . Note that we can consider $A_{m,d}$ as a subset of $[0,m/d],$ a compact set. So, for any countable cover $(U_{r})$ of $A_{m,d}$ , we can find finitely many open sets $V_{1},V_{2},...,V_{p}$ such that

\bigcup_{r=0}^{\infty}{U_{r}}\subset\bigcup_{r=0}^{p}{V_{r}}\text{\quad and}

\sum_{r=0}^{p}{|V_{r}|^{\beta}}\leq\sum_{r=0}^{\infty}{|U_{r}|^{\beta}}.

We next get a lower bound on $\sum_{r=0}^{p}{|V_{r}|^{\beta}}$ . Let $b\in\mathbb{N}$ such that for all $r,d^{-b}\leq|V_{r}|$ . Additionally, for all $1\leq i\leq b$ , let $N_{i}$ be the number of $V_{r}$ ’s which satisfy $d^{-i}\leq|V_{r}|<d^{-i+1}$ . Observe that if $|V_{r}|<d^{-i+1}$ , then $V_{r}$ can intersect at most two intervals in $X_{i-1}$ . Hence, $V_{r}$ can contain at most $2m^{b-i+1}$ intervals in $X_{b}$ , which has $m^{b}$ intervals. So,

\sum_{i=0}^{b}{2m^{b-i+1}N_{i}}\geq m^{b}

\sum_{i=0}^{b}{m^{-i}N_{i}}\geq\frac{1}{2m}

For $\beta=\frac{\log m}{\log d}$ ,

\sum_{r=0}^{p}{|V_{r}|^{\beta}}\geq\sum_{i=0}^{b}{{(d^{-i})}^{\beta}N_{i}}=\sum_{i=0}^{b}{m^{-i}N_{i}}\geq\frac{1}{2m}.

In other words, the summation of $\frac{\log m}{\log d}$ powers of the lengths of the intervals which form a cover of $A_{m,d}$ has a positive lower bound. Thus,

dim_{H}(A_{m,d})\geq\frac{\log m}{\log d}.

∎

Since $A_{m,d}\subset E_{m,d},$ we immediately get a lower bound on the Hausdorff Dimension of $E_{m,d}:$

Theorem 3.

Let $m,d\in\mathbb{N}$ with $1<d$ and $1\leq m\leq d$ . Then,

dim_{H}(E_{m,d})\geq\frac{\log m}{\log d}

∎

3. Upper Bound

In this section, we first find an upper bound on the number of degree- $m$ cycles for $d$ -map which have $n$ elements. We extend this result to precycles. Then, we find an appropriate covering of $E_{m,d}$ to prove that its Hausdorff Dimension is at most $\frac{\log m}{\log d}$ .

Definition 8 (Partition generated by a cycle).

Let $C=\{c_{1},c_{2},...,c_{n}\}$ be a degree- $m$ cycle for $d$ -map such that $0<c_{1}<c_{2}<....<c_{n}<1$ . Let $\sigma$ be the map on $\{1,2,....,n\}$ which satisfies:

dc_{r}\text{(mod 1)}=c_{\sigma(r)},\forall\ 1\leq r\leq n

Note that $\sigma$ is a permutation of $\{1,2,....,n\}$ because $C$ is a cycle.

Let $1\leq i_{1}<i_{2}<...<i_{m}\leq n$ be such that for all $1\leq t\leq m,(c_{i_{t}},c_{i_{t}+1})$ is a crossing generated by $C$ . From the ordering of the elements of $C$ and the definition of crossing, we conclude that:

\sigma(i_{t})>\sigma(i_{t}+1)\text{ and }\sigma(i_{t}+1)<\sigma(i_{t}+2)<...<\sigma(i_{t+1}),\ \forall\ 1\leq t<m

and

\sigma(i_{m})>\sigma(i_{m}+1)\text{ and }\sigma(i_{m}+1)<...<\sigma(n)<\sigma(1)<...<\sigma(i_{1})

Now we construct a partition of $\{1,2,..,n\}$ using the above property of $\sigma$ .

P_{t}=\left\{\begin{array}[]{l l}\{\sigma(r)|i_{t}<r\leq i_{t+1}\}&\quad\text{if $1\leq t<m$}\\ \{\sigma(r)|i_{m}<r\leq n\}\cup\{\sigma(r)|1\leq r\leq i_{1}\}&\quad\text{if $t=m$}\end{array}\right.

$\{P_{t}|1\leq t\leq m\}$ is a partition of $\{1,2,..,n\}$ , called as the partition generated by $C$ and it is denoted by $P(C)$ .

Remark 5.

Both $P(C)$ and the map $\sigma$ are useful counting $n$ -element degree- $m$ cycles, as we show below.

Example 4.

Let us consider the instance where $d=3$ and

C=\{(0.\overline{00102})_{3},(0.\overline{01020})_{3},(0.\overline{02001})_{3},(0.\overline{10200})_{3},(0.\overline{20010})_{3}\}.

Note that here, $n=5$ . Under the 3-map,

	$\displaystyle c_{1}$	$\displaystyle=(0.\overline{00102})_{3}\mapsto(0.\overline{01020})_{3}=c_{2}$
	$\displaystyle c_{2}$	$\displaystyle=(0.\overline{01020})_{3}\mapsto(0.\overline{10200})_{3}=c_{4}$
	$\displaystyle c_{3}$	$\displaystyle=(0.\overline{02001})_{3}\mapsto(0.\overline{20010})_{3}=c_{5}$
	$\displaystyle c_{4}$	$\displaystyle=(0.\overline{10200})_{3}\mapsto(0.\overline{02001})_{3}=c_{3}$
	$\displaystyle c_{5}$	$\displaystyle=(0.\overline{20010})_{3}\mapsto(0.\overline{00102})_{3}=c_{1}$

So, $\sigma$ is the permutation of $\{1,2,3,4,5\}$ which takes 1, 2, 3, 4, 5 to 2, 4, 5, 3, 1 respectively. $(c_{3},c_{4})$ and $(c_{4},c_{5})$ are the crossings generated by the cycle. So, $i_{1}=3$ and $i_{2}=4$ , and the partition generated by $C$ is given by:

P(C)=\{P_{1},P_{2}\}\text{ where }P_{1}=\{\sigma(r)|3<r\leq 4\},P_{2}=\{\sigma(r)|4<r\leq 5\}\cup\{\sigma(r)|1\leq r\leq 3\}

P(C)=\{\{3\},\{1,2,4,5\}\}

Now, we will show that if some properties of a cycle such as degree, the partition it generates and its digit portrait are given, then we can construct the cycle (find its points). Later, we will use this result to count the number of cycles of fixed degree and cardinality.

Lemma 5.

Given positive integers $d,m,n$ , $P=\{P_{1},P_{2},...,P_{m}\}$ which is a partition of $\{1,2,...,n\}$ , positive integer $i_{1}<|P_{m}|$ and a non-decreasing map $F:\{0,1,2,...,(d-1)\}\rightarrow\{0,1,2,...,n\}$ with $F(d-1)=n$ , there exists at most one cycle $C$ for $d$ -map such that:

(1)

$C=\{c_{1},c_{2},...,c_{n}\}$ with $0<c_{1}<c_{2}<....<c_{n}<1$
(2)

$deg(C)=m$
(3)

$P(C)=P$ or $P$ is the partition generated by $C$
(4)

If, for all $1<t\leq m$ , $i_{t}=i_{t-1}+|P_{t}|$ , then $(c_{i},c_{i+1})$ is a crossing for all $i\in\{i_{1},i_{2},...,i_{m}\}$ .
(5)

$F$ is the Digit Portrait of $C$ .

Proof.

Suppose $C$ is a cycle for $d$ -map which satisfies all the conditions above, and let $\sigma$ be the map on $\{1,2,....,n\}$ given by:

\sigma(r)=\left\{\begin{array}[]{l l}{(r-i_{t})}^{\text{th}}\text{ element of }P_{t}&\quad\text{if $i_{t}<r\leq i_{t+1}$ and $1\leq t<m$}\\ {(r-i_{m})}^{\text{th}}\text{ element of }P_{m}&\quad\text{if $i_{m}<r$}\\ {(r+n-i_{m})}^{\text{th}}\text{ element of }P_{m}&\quad\text{if $r<i_{1}$}\\ \end{array}\right.

where, for all $1\leq t\leq m$ , the elements of $P_{t}$ are in increasing order. Note that $\sigma$ is uniquely determined by $m,n,P$ and $i_{1}$ . Comparing this with the definition of partition generated by a cycle, we conclude that

dc_{r}\text{(mod 1)}=c_{\sigma(r)},\forall\ 1\leq r\leq n

Let $b:\{1,2,....,n\}\rightarrow\{0,1,2,....,(d-1)\}$ given by:

b(r)=\left\{\begin{array}[]{l l}0&\quad\text{if $r<F(0)$}\\ j&\quad\text{if $F(j-1)<r\leq F(j)$ and $1\leq j\leq(d-1)$}\end{array}\right.

Note that $b$ is uniquely determined by $n,d$ and $k$ . Comparing this with the definition of Digit Portrait, we conclude that

c_{r}\in[\ \frac{b(r)}{d},\frac{b(r)+1}{d}\ ),\ \forall\ 1\leq r\leq n

b(r)=\text{the first digit in the base-}d\text{ expansion of }c_{r},\text{for all}\ 1\leq r\leq n

Also,

b(\sigma(r))=\text{the first digit in the base-}d\text{ expansion of }c_{\sigma(r)}

\quad\quad=\text{ the second digit in the base-}d\text{ expansion of }c_{r}

Thus, we conclude that

c_{r}={(0.\overline{b(r)b(\sigma(r))b(\sigma^{2}(r)).....b(\sigma^{d-1}(r))}\ )}_{d}

In other words, the cycle $C$ is uniquely determined by $\sigma$ and $b$ .
∎

Remark 6.

$(c_{i},c_{i+1})$ can be a crossing only if the first digits of the base- $d$ expansions of $c_{i}$ and $c_{i+1}$ differ. So, cycle $C$ satisfying all conditions in the above lemma can exist only if

\{F(0),F(1),...,F(d-1)\}\subset\{i_{1},i_{2},...i_{m}\}\cup\{n\}

We will use this in the proof of the following lemma.

Lemma 6.

Let $d,m,n\in\mathbb{N}$ with $1\leq m\leq d$ and $n,d>1$ . Then the number of cycles $C$ for $d$ -map satisfying $|C|=n$ and $deg(C)=m$ is at most $O(n^{d-m+1}m^{n-1}).$

Proof.

$d,m,n$ are given. Now we need $P=\{P_{1},P_{2},...,P_{m}\}$ which is a partition of $\{1,2,...,n\}$ , positive integer $i_{1}<|P_{m}|$ and a non-decreasing map $F:\{0,1,2,...,(d-1)\}\rightarrow\{0,1,2,...,n\}$ with $F(d-1)=n$ to fix a degree- $m$ , $n$ -element cycle.

Let $T$ be the set of ordered $(m+1)$ -tuples $(P_{1},P_{2},...,P_{m},i_{1})$ such that $P=\{P_{1},P_{2},...,P_{m}\}$ is a partition of $\{1,2,...,n\}$ , $i_{1}\in\mathbb{N}$ and $i_{1}\leq|P_{m}|$ . We want an upper bound on the size of T, denoted here as $\#(T)$ .

	$\displaystyle\#(T)$	$\displaystyle=\sum_{\begin{subarray}{c}a_{1}+a_{2}+...+a_{m}=n\\ a_{i}\in\mathbb{N}\end{subarray}}{a_{m}\ {n\choose{a_{1}}}{{n-a_{1}}\choose{a_{2}}}...{{{n-a_{1}-a_{2}-...-a_{m-1}}\choose{a_{m}}}}}$
		$\displaystyle=\sum_{\begin{subarray}{c}a_{1}+a_{2}+...+a_{m}=n\\ a_{i}\in\mathbb{N}\end{subarray}}{a_{m}\cdot\frac{n!}{a_{1}!\ a_{2}!\ ....a_{m}!}}$
		$\displaystyle=\sum_{\begin{subarray}{c}a_{1}+a_{2}+...+a_{m}=n\\ a_{i}\in\mathbb{N}\end{subarray}}{\frac{n!}{a_{1}!\ a_{2}!\ ....a_{m-1}!\ (a_{m}-1)!}}$
		$\displaystyle\leq\sum_{\begin{subarray}{c}a_{1}+a_{2}+...+a_{m-1}+(a_{m}-1)=n-1\\ a_{i}\in\mathbb{N}\cup\{0\}\end{subarray}}{n\cdot\frac{(n-1)!}{a_{1}!\ a_{2}!\ ....a_{m-1}!\ (a_{m}-1)!}}$
		$\displaystyle=n\cdot m^{n-1}$

After fixing an element of $T$ , we need to fix a non-decreasing map $F$ from $\{0,1,2,...,(d-1)\}$ to $\{0,1,2,...,n\}$ with $F(d-1)=n$ and $\{F(0),F(1),...,F(d-1)\}\subset\{i_{1},i_{2},...i_{m}\}\cup\{n\}$ . Observe that there are $(n+1)^{(d-m-1)}$ or $(n+1)^{(d-m)}$ choices for $F$ , depending on if $n$ is in $\{i_{1},i_{2},...i_{m}\}$ or not.

Using Lemma 5, we conclude that the number of degree- $m$ $n$ -element cycles for $d$ -map is at most $O(n^{d-m+1}m^{n-1})$ .

∎

To conclude this section (and to show our desired result), we first introduce precycles.

Definition 9 (Precycle).

Let $d$ be a positive integer greater than 1. A finite set $C_{P}\subset S^{1}$ is called a precycle for $d$ -map, if and only if $C_{P}=\{c\cdot d^{i}\text{ (mod 1)}|i\in\mathbb{N}\cup\{0\}\}$ for some $c\in S^{1}$ . In other words, a precycle is the forward orbit of a rational point in $S^{1}$ . It can be written in terms of base- $d$ expansion of its points as

C_{P}=\{(0.b_{r}b_{r+1}...b_{n_{1}}\overline{b_{1}^{\prime}b_{2}^{\prime}....b_{n_{2}}^{\prime}})_{d}|1\leq r\leq n_{1}\}\cup\{(0.\overline{b_{k}^{\prime}b_{k+1}^{\prime}...b_{n_{2}}b_{1}^{\prime}....b_{k-1}^{\prime}})_{d}|1\leq k\leq n_{2}\},

where $n_{1}$ is a fixed non-negative integer, $n_{2}$ is a fixed positive integer and all $b_{r},b_{k}^{\prime}$ are fixed digits in $\{0,1,2,...,d-1\}$ .

Remark 7.

Every precycle $C_{P}$ includes a cycle. If $n_{1}=0$ , then $C_{P}$ itself is a cycle.

Example 5.

Consider $d=2$ and $C_{P}=\{\frac{1}{3},\frac{2}{3},\frac{5}{6}\}$ . $C_{P}$ can be written as

C_{P}=\{\frac{5}{6}\cdot d^{i}\text{(mod 1)}|i\in\mathbb{N}\cup\{0\}\}

C_{P}=\{\frac{5}{6}\}\cup\{\frac{1}{3},\frac{2}{3}\}=\{(0.1\overline{10})_{2}\}\cup\{(0.\overline{01})_{2},(0.\overline{10})_{2}\}

Remark 8.

We can define degree, crossing, crossing number, digit portrait and partition for a precycle simply by replacing $C$ by $C_{P}$ in the respective definitions.
In the case where $C_{P}$ is a precycle but not a cycle, the map $\sigma$ in the definition of partition (Definition 8) is not a permutation. Under $\sigma$ , one element of $\{1,2,...,n\}$ has no preimages, one has two preimages and all other elements have exactly one preimage.

Lemma 7.

Let $d,m,n\in\mathbb{N}$ with $1\leq m\leq d$ . Then the number of precycles $C_{P}$ for the $d$ -map satisfying $|C_{P}|=n$ and $deg(C_{P})=m$ is at most $O(n^{d-m+3}m^{n-1})$ .

Proof.

Similar to the argument used to prove Lemma 6. Note that the increase in the exponent of $n$ is due to the small change in the nature of the map $\sigma$ in the definition of partition (Definition 8).
∎

Finally, we find a suitable covering of $E_{m,d}$ and get an upper bound on its Hausdorff Dimension, as desired.

Theorem 4.

Let $m,d\in\mathbb{N}$ with $1<d$ and $1\leq m\leq d$ . Then

dim_{H}(E_{m,d})\leq\frac{\log m}{\log d}

Proof.

Fix a positive integer $n>1$ , and let

\mathscr{C}_{P}(n)=\{C_{P}|C_{P}\text{ is a precycle for $d$-map},deg(C_{P})\leq m,|C_{P}|\leq n\}.

From Lemma 7, we have $|\mathscr{C}_{P}|$ is at most $O(n^{d-m+4}m^{n})$ (note the change in exponent due to the inequality).

Let $C$ be a degree- $m$ cycle for $d$ -map, and $c\in C$ . There exists a degree- $m$ map $f:S^{1}\rightarrow S^{1}$ which agrees with $d$ -map on $C$ . Letting $f^{n}$ denote $f$ composed $n$ times, we note that $|(f^{n})^{\prime}(c)|=d^{n}$ . See McMullen [mcmullen2010dynamics] for details. It follows there exists a point $x$ in $O(d^{-n})$ neighborhood of $c$ for which two of $x,f(x),f^{2}(x),...,f^{n}(x)$ coincide. Generalizing, each point of any degree- $m$ cycle for the $d$ -map lies in $O(d^{-n})$ neighborhood of an element in $\mathscr{C}_{P}$ . Thus, $E_{m,d}$ lies in a $O(d^{-n})$ neighborhood of $\mathscr{C}_{P}$ which has at most $O(n^{d-m+4}m^{n})$ elements.

Let $\beta=\frac{\log m}{\log d}+\varepsilon$ for some $\varepsilon>0.$

	$\displaystyle\lim_{n\to\infty}{{(d^{-n})}^{\beta}n^{d-m+4}m^{n}}$	$\displaystyle=\lim_{n\to\infty}{(d^{\frac{\log m}{\log d}})^{-n}d^{-n\varepsilon}n^{d-m+4}m^{n}}$
		$\displaystyle=\lim_{n\to\infty}{d^{-n\varepsilon}n^{d-m+4}}$
		$\displaystyle=0$

For any $\beta>\frac{\log m}{\log d}$ , we can cover $E_{m,d}$ such that the summation of $\beta$ powers of the lengths of the intervals in the cover is as small as we like. So, $dim_{H}(E_{m,d})\leq\frac{\log m}{\log d}$ .

∎

We are now ready to prove Theorem 2.

Theorem 2.

Let $m,d\in\mathbb{N}$ with $1<d$ and $1\leq m\leq d$ . Then,

dim_{H}(E_{m,d})=\frac{\log m}{\log d}.

Proof.

Follows from Theorems 3 and 4. ∎

Acknowledgment

The authors would like to thank Prof. Curtis McMullen for suggesting the problems and giving valuable comments. This project was undertaken by M.T. in SPUR (the Summer Program in Undergraduate Research) at MIT Mathematics Department in Summer 2014. M.T. would like to thank Prof. David Jerison and Prof. Pavel Etingof for their guidance and insightful discussions during the program. We also thank our mentor Xuwen Zhu for her help and support for completing this paper.

Hausdorff Dimension of closure of cycles in dd-maps on the circle

Abstract.

1. Introduction

Definition 1 (dd-map).

Definition 2 (Cycle).

Definition 3 (Degree of a cycle).

Remark 1.

Remark 2.

Example 1.

Example 2.

Definition 4 (Closure of cycles).

Definition 5 (Hausdorff Dimension).

Theorem 1 (McMullen).

Theorem 2.

2. Lower Bound

Definition 6 (Crossing).

Remark 3.

Remark 4.

Lemma 1.

Proof.

Definition 7 (Digit Portrait).

Example 3.

Lemma 2.

Proof.

Lemma 3.

Proof.

Proposition 1.

Proof.

Lemma 4.

Proof.

Theorem 3.

3. Upper Bound

Definition 8 (Partition generated by a cycle).

Remark 5.

Example 4.

Lemma 5.

Proof.

Remark 6.

Lemma 6.

Proof.

Definition 9 (Precycle).

Remark 7.

Example 5.

Remark 8.

Lemma 7.

Proof.

Theorem 4.

Proof.

Theorem 2.

Proof.

Acknowledgment

References

Hausdorff Dimension of closure of cycles in $d$ -maps on the circle

Definition 1 ( $d$ -map).