# Topological Connectivity of Random Permutation Complexes

Roy Meshulam Department of Mathematics, Technion, Haifa 32000, Israel. e-mail:
<EMAIL_ADDRESS>. Supported by ISF grant 686/20. Omer Moyal Department
of Mathematics, Technion, Haifa 32000, Israel. e-mail:
<EMAIL_ADDRESS>.

###### Abstract

Let $\mathbb{S}_{n}$ denote the symmetric group on $[n]=\\{1,\ldots,n\\}$ with
the uniform probability measure. For a permutation $\pi\in\mathbb{S}_{n}$ let
$X_{\pi}$ denote the simplicial complex on the vertex set $[n]$ whose
simplices are all $\\{i_{0},\ldots,i_{m}\\}\subset[n]$ such that
$i_{0}<\cdots<i_{m}$ and $\pi(i_{0})<\cdots<\pi(i_{m})$. For $r\geq 0$ let
$p_{r}(n)$ denote the probability that $X_{\pi}$ is not topologically
$r$-connected for $\pi\in\mathbb{S}_{n}$. It is shown that for fixed $r\geq 0$
there exist constants $0<C_{r},C_{r}^{\prime}<\infty$ such that

$C_{r}\frac{(\log n)^{r}}{n}\leq p_{r}(n)\leq C_{r}^{\prime}\frac{(\log
n)^{2r}}{n}.$

##  1 Introduction

Let $\mathbb{S}_{n}$ denote the symmetric group on $[n]=\\{1,\ldots,n\\}$ with
the uniform probability measure. For a permutation $\pi\in\mathbb{S}_{n}$ let
$\prec_{\pi}$ denote the partial order on $[n]$ given by $i\prec_{\pi}j$ if
both $i<j$ and $\pi(i)<\pi(j)$. Let $X_{\pi}$ denote the order complex of the
poset $([n],\prec_{\pi})$, i.e. the simplicial complex on the vertex set $[n]$
whose $m$-simplices are all $\\{i_{0},\ldots,i_{m}\\}\subset[n]$ such that
$i_{0}<\cdots<i_{m}$ and $\pi(i_{0})<\cdots<\pi(i_{m})$. The following result
had been proved in an equivalent formulation by Przytycki and Silvero [3], and
independently but later by Chacholski, Levi and Meshulam [2].

######  Theorem 1.1 ([3, 2]).

For any $n\geq 1$ and $\pi\in\mathbb{S}_{n}$ the complex $X_{\pi}$ is either
contractible or is homotopy equivalent to a wedge of spheres

$X_{\pi}\simeq S^{k_{1}}\vee\cdots\vee S^{k_{m}}.$ (1)

Conversely, for any $k_{1},\ldots,k_{m}\geq 0$ there exist an $n\geq 1$ and
$\pi\in\mathbb{S}_{n}$ such that (1) holds.

######  Example 1.2.

Let $\pi=\left(\begin{array}[]{c}1234567\\\ 3254176\end{array}\right).$ Then
$X_{\pi}$ depicted in Figure 1 is homotopy equivalent to $S^{1}\vee S^{2}$.

Figure 1: $X_{\pi}$ for $\pi=\left(\begin{array}[]{c}1234567\\\
3254176\end{array}\right)$

Let $r\geq 0$. Recall that a nonempty space $X$ is $r$-connected if for all
$0\leq i\leq r$, any continuous map from the $i$-sphere $S^{i}$ to $X$ can be
extended continuously to the $(i+1)$-th ball. By convention, any nonempty
space is $(-1)$-connected, while the empty set is not $(-1)$-connected. Note
that $X_{\pi}$ is $r$-connected if either $X_{\pi}$ is contractible, or if $r$
is strictly less than all $k_{i}$’s appearing in the decomposition (1). In
this paper we study the connectivity of $X_{\pi}$ for a random
$\pi\in\mathbb{S}_{n}$. Let

$p_{r}(n):={\rm
Pr}\left[\pi\in\mathbb{S}_{n}:X_{\pi}\text{~{}is~{}not~{}}r\text{-connected}\right].$

It is easy to check (see Claim 4.2) that $p_{0}(n)=\frac{2+o(1)}{n}$. A much
deeper result due to Winkler [5] asserts that asymptotically almost surely the
$1$-skeleton of $X_{\pi}$ has diameter $3$. Let $c_{0}=0$ and for $r\geq 1$
let $c_{r}=\sum_{i=0}^{r-1}\frac{1}{i!}$. Our main result is the following

######  Theorem 1.3.

Let $r\geq 0$ and $n\geq 1$. Then

  * (i)

$p_{r}(n)\leq 40^{r+1}\frac{(\log 3n)^{2r}}{n}.$

  * (ii)

$p_{r}(n)\geq\frac{1}{r!}\frac{(\log n)^{r}}{n}-c_{r}\frac{(\log
n)^{r-1}}{n}.$

For the proof of the upper bound it will be convenient to use an equivalent
model for random permutation complexes (see e.g. [5]). Let $\leq$ be the
standard partial order on ${\twelvebb R}^{2}$, i.e. $q=(a,b)\leq
q^{\prime}=(a^{\prime},b^{\prime})$ if $a\leq a^{\prime}$ and $b\leq
b^{\prime}$. For $n\geq 1$ and an $n$-tuple
$q=(q_{1},\ldots,q_{n})\in({\twelvebb R}^{2})^{n}$ let $Y_{q}$ denote the
order complex of $\\{q_{1},\ldots,q_{n}\\}$, i.e. the simplicial complex on
the vertex set $[n]$ whose $m$-simplices are the subsets
$\\{i_{0},\ldots,i_{m}\\}$ such that $q_{i_{0}}<\cdots<q_{i_{m}}$. Let
$\Omega_{n}=([0,1]^{2})^{n}$ denote the probability space of $n$-tuples
$q=(q_{1},\ldots,q_{n})$ where the $q_{i}$’s are picked independently and
uniformly from $[0,1]^{2}$. Let $\Omega_{n}^{\prime}$ denote the subspace of
all $q=(q_{1},\ldots,q_{n})\in\Omega_{n}$ with $q_{i}=(a_{i},b_{i})$ such that
$|\\{a_{1},\ldots,a_{n}\\}|=|\\{b_{1},\ldots,b_{n}\\}|=n$. For
$q\in\Omega_{n}^{\prime}$ as above let $\alpha,\beta\in\mathbb{S}_{n}$ be the
unique permutations such that $a_{\alpha(1)}<\cdots<a_{\alpha(n)}$ and
$b_{\beta(1)}<\cdots<b_{\beta(n)}$, and let
$\varphi(q)=\beta^{-1}\alpha\in\mathbb{S}_{n}$. Extending $\varphi$
arbitrarily to the whole of $\Omega_{n}$, it is clear that ${\rm
Pr}_{\Omega_{n}}\left[\varphi^{-1}(\pi)\right]=\frac{1}{n!}={\rm
Pr}_{\mathbb{S}_{n}}[\left\\{\pi\right\\}]$. As ${\rm
Pr}_{\Omega_{n}}[\Omega_{n}^{\prime}]=1$ and $Y_{q}\cong X_{\varphi(q)}$ for
all $q\in\Omega_{n}^{\prime}$, it follows that

$p_{r}(n)={\rm
Pr}\left[q\in\Omega_{n}:Y_{q}\text{~{}is~{}not~{}}r\text{-connected}\right].$

The paper is organized as follows. In Section 2 we give a simple nerve type
sufficient condition (Proposition 2.2) for $r$-connectivity of $X_{\pi}$. In
Section 3 we establish an upper bound on a certain integral related to
$p_{r}(n)$ (Proposition 3.1). The results of Sections 2 and 3 are the key
ingredients in the proof of Theorem 1.3(i) given in Section 4. In Section 5 we
prove Theorem 1.3(ii) using a homotopy decomposition of $X_{\pi}$ (Proposition
5.1). We conclude in Section 6 with some remarks and open problems.

##  2 A Sufficient Condition for $r$-Connectivity

Let $K$ be a finite simplicial complex and let
$\mathcal{K}=\\{K_{j}\\}_{j=1}^{m}$ be a family of subcomplexes of $K$ such
that $\bigcup_{j=1}^{m}K_{j}=K$. For a nonempty $J\subset[m]$ let
$K_{J}=\bigcap_{j\in J}K_{j}$. The nerve $N(\mathcal{K})$ of $\mathcal{K}$ is
the simplicial complex on the vertex set $[m]$ whose simplices are all
$J\subset[m]$ such that $K_{J}\neq\emptyset$. As usual, let $\pi_{0}(K)$
denote the set of connected components of $K$ and for $i\geq 1$ let
$\pi_{i}(K)$ denote the $i$-th homotopy group of $K$. We shall need Björner’s
version of the nerve theorem.

######  Theorem 2.1 ([1]).

Let $r\geq 0$. Assume that $K_{J}$ is either empty or $(r-|J|+1)$-connected
for all $\emptyset\neq J\subset[m]$ such that $|J|\leq r+1$. Then
$\pi_{i}(K)\cong\pi_{i}(N(\mathcal{K}))$ for all $0\leq i\leq r$. In
particular, $K$ is $r$-connected iff $N(\mathcal{K})$ is $r$-connected.

Fix $q=(q_{1},\ldots,q_{n})\in\Omega_{n}^{\prime}$ where $q_{i}=(a_{i},b_{i})$
and let

$M(q)=\left\\{i\in[n]:q_{i}\text{~{}is~{}a~{}minimal~{}element~{}of~{}}\\{q_{1},\ldots,q_{n}\\}\right\\}.$

For a subset $S\subset[n]$ let $Y_{q}[S]=\\{\sigma\in Y_{q}:\sigma\subset
S\\}$ denote the induced subcomplex of $Y_{q}$ on the vertex set $S$. For
$1\leq i\neq j\leq n$ let $q_{i}\vee
q_{j}=(\max\\{a_{i},a_{j}\\},\max\\{b_{i},b_{j}\\})$ and let

$Y_{q,ij}=Y_{q}\left[\left\\{\ell:q_{\ell}\geq q_{i}\vee
q_{j}\right\\}\right].$

######  Proposition 2.2.

Let $r\geq 1$. If $Y_{q,ij}$ is $(r-1)$-connected for all distinct $i,j\in
M(q)$ then $Y_{q}$ is $r$-connected.

Proof. Let $K=Y_{q}$ and for $i\in M(q)$ let $K_{i}=Y_{q}\left[\\{j:q_{j}\geq
q_{i}\\}\right]$. Then $K=\bigcup_{i\in M(q)}K_{i}$. Let $\emptyset\neq
J\subset M(q)$ such that $|J|\leq r+1$. If $J=\\{j\\}$ is a singleton, then
$K_{J}=K_{j}$ is a cone with apex $j$, hence contractible and therefore
$\ell$-connected for all $\ell$. Suppose on the other hand that $|J|\geq 2$.
Let $i,j\in J$ satisfy $a_{i}=\max\\{a_{t}:t\in M(q)\\}$ and
$b_{j}=\max\\{b_{t}:t\in M(q)\\}$. Then $K_{J}=Y_{q,ij}$. By assumption
$K_{J}$ is $(r-1)$-connected and thus $(r-|J|+1)$-connected. Therefore
$\\{K_{i}\\}_{i\in M(q)}$ satisfies the conditions of Theorem 2.1. As
$K_{J}\neq\emptyset$ for all $J\subset M(q)$, it follows that the nerve
$N(\\{K_{i}\\}_{i\in M(q)})$ is a simplex and hence $r$-connected. Therefore
$K=Y_{q}$ is $r$-connected as well.

$\Box$

##  3 A Key Estimate

For $k\geq 1$ let $Q_{k}=\\{(x_{1},\ldots,x_{k})\in{\twelvebb R}^{k}:x_{i}\geq
0,\sum_{i=1}^{k}x_{i}\leq 1\\}$ denote the $k$-simplex in ${\twelvebb R}^{k}$
and let $\Delta_{k}=\\{(x_{1},\ldots,x_{k+1})\in{\twelvebb R}^{k+1}:x_{i}\geq
0,\sum_{i=1}^{k+1}x_{i}=1\\}$ denote the $k$-simplex in ${\twelvebb R}^{k+1}$.
Recall (see e.g. Exercise 13, Chapter 10 in [4]) that for any integers
$\alpha_{1},\ldots,\alpha_{k+1}\geq 0$

$\begin{split}&\int_{x\in\Delta_{k}}x_{1}^{\alpha_{1}}\cdots
x_{k+1}^{\alpha_{k+1}}dx=\sqrt{k+1}\,\int_{x\in Q_{k}}x_{1}^{\alpha_{1}}\cdots
x_{k}^{\alpha_{k}}(1-\sum_{i=1}^{k}x_{i})^{\alpha_{k+1}}dx\\\
&=\frac{\sqrt{k+1}\,\alpha_{1}!\cdots\alpha_{k+1}!}{(k+\alpha_{1}+\cdots+\alpha_{k+1})!}.\end{split}$
(2)

In particular, the $k$-dimensional volume of $\Delta_{k}$ is ${\rm
vol}_{k}(\Delta_{k})=\sqrt{k+1}\,{\rm vol}_{k}(Q_{k})=\frac{\sqrt{k+1}}{k!}$.
For $p\geq 1$ let $A_{k,p}=\\{(\alpha_{1},\ldots,\alpha_{p})\in{\twelvebb
Z}^{p}:\alpha_{i}\geq 0,\sum_{i=1}^{p}\alpha_{i}=k\\}$. For $k,\ell\geq 0$
define

$I(k,\ell)={\rm
vol}_{2}(\Delta_{2})^{-2}\int_{(x,y)\in\Delta_{2}^{2}}\left(x_{1}y_{3}+x_{2}(y_{2}+y_{3})+x_{3}(y_{1}+y_{2})\right)^{k}(x_{3}y_{3})^{\ell}dx\,dy.$

The main result of this section is the following estimate.

######  Proposition 3.1.

$I(k,\ell)\leq\frac{40}{k+2}\binom{k+\ell+2}{2}^{-1}\binom{k+\ell}{k}^{-1}(1+\log(k+1)).$
(3)

The proof of Proposition 3.1 depends on some preliminary observations. For
integers $N,t\geq 0$ such that $N\geq 2t$ let

$F(N,t)=\binom{N}{\lceil\frac{N}{2}\rceil+t}\sum_{i=0}^{t}\binom{N}{\lceil\frac{N}{2}\rceil+i}^{-1}.$

######  Claim 3.2.

$F(N,t)\leq 1+\min\left\\{t,\frac{N}{t}\right\\}.$

Proof. The bound $F(N,t)\leq 1+t$ is clear. For the other inequality observe
that if $0\leq i\leq t$ then

$\begin{split}&\binom{N}{\lceil\frac{N}{2}\rceil+t}\binom{N}{\lceil\frac{N}{2}\rceil+i}^{-1}=\frac{\left(\lceil\frac{N}{2}\rceil+i\right)!\left(\lfloor\frac{N}{2}\rfloor-i\right)!}{\left(\lceil\frac{N}{2}\rceil+t\right)!\left(\lfloor\frac{N}{2}\rfloor-t\right)!}\\\
&=\prod_{j=0}^{t-i-1}\frac{\lfloor\frac{N}{2}\rfloor-
i-j}{\lceil\frac{N}{2}\rceil+t-j}\leq\left(\frac{\frac{N}{2}-i}{\frac{N}{2}+t}\right)^{t-i}=\left(1-\frac{t+i}{\frac{N}{2}+t}\right)^{t-i}\\\
&\leq\exp\left(-\frac{(t+i)(t-i)}{\frac{N}{2}+t}\right)\leq\exp\left(-\frac{t^{2}}{N}\right)\cdot\exp\left(\frac{i^{2}}{N}\right).\end{split}$
(4)

Moreover,

$\begin{split}&\sum_{i=0}^{t-1}\exp\left(\frac{i^{2}}{N}\right)\leq\int_{0}^{t}\exp\left(\frac{x^{2}}{N}\right)dx=\int_{0}^{t}\left(\sum_{j=0}^{\infty}\frac{x^{2j}}{N^{j}j!}\right)dx\\\
&=\sum_{j=0}^{\infty}\frac{1}{N^{j}j!}\int_{0}^{t}x^{2j}dx=\sum_{j=0}^{\infty}\frac{t^{2j+1}}{N^{j}j!(2j+1)}\\\
&\leq\frac{N}{t}\sum_{j=0}^{\infty}\frac{t^{2(j+1)}}{N^{j+1}(j+1)!}=\frac{N}{t}\left(\exp\left(\frac{t^{2}}{N}\right)-1\right).\end{split}$
(5)

Combining (4) and (5) it follows that

$\begin{split}F(N,t)&=1+\binom{N}{\lceil\frac{N}{2}\rceil+t}\sum_{i=0}^{t-1}\binom{N}{\lceil\frac{N}{2}\rceil+i}^{-1}\\\
&\leq
1+\exp\left(-\frac{t^{2}}{N}\right)\sum_{i=0}^{t-1}\exp\left(\frac{i^{2}}{N}\right)\\\
&\leq
1+\exp\left(-\frac{t^{2}}{N}\right)\cdot\frac{N}{t}\left(\exp\left(\frac{t^{2}}{N}\right)-1\right)<1+\frac{N}{t}.\end{split}$

$\Box$

######  Corollary 3.3.

For any $\ell,j\geq 0$

$\binom{2\ell+j}{\ell+j}\sum_{i=0}^{j}\binom{2\ell+j}{\ell+i}^{-1}\leq\frac{10(\ell+j+1)}{j+1}.$
(6)

Proof. Write $N=2\ell+j$. Then

$\begin{split}&\sum_{i=0}^{j}\binom{2\ell+j}{\ell+i}^{-1}=\sum_{i=0}^{j}\binom{N}{\lceil\frac{N}{2}\rceil-\lceil\frac{j}{2}\rceil+i}^{-1}\\\
&=\sum_{i=0}^{\lceil\frac{j}{2}\rceil-1}\binom{N}{\lceil\frac{N}{2}\rceil-\lceil\frac{j}{2}\rceil+i}^{-1}+\sum_{i=\lceil\frac{j}{2}\rceil}^{j}\binom{N}{\lceil\frac{N}{2}\rceil-\lceil\frac{j}{2}\rceil+i}^{-1}\\\
&=\sum_{i=1}^{\lceil\frac{j}{2}\rceil}\binom{N}{\lfloor\frac{N}{2}\rfloor+i}^{-1}+\sum_{i=0}^{\lfloor\frac{j}{2}\rfloor}\binom{N}{\lceil\frac{N}{2}\rceil+i}^{-1}\\\
&=2\sum_{i=0}^{\lfloor\frac{j}{2}\rfloor}\binom{N}{\lceil\frac{N}{2}\rceil+i}^{-1}-\frac{1+(-1)^{N}}{2}\binom{N}{\lceil\frac{N}{2}\rceil}^{-1}.\end{split}$

Hence

$\begin{split}&\binom{2\ell+j}{\ell+j}\sum_{i=0}^{j}\binom{2\ell+j}{\ell+i}^{-1}=\binom{N}{\lceil\frac{N}{2}\rceil+\lfloor\frac{j}{2}\rfloor}\sum_{i=0}^{j}\binom{2\ell+j}{\ell+i}^{-1}\\\
&\leq
2\binom{N}{\lceil\frac{N}{2}\rceil+\lfloor\frac{j}{2}\rfloor}\sum_{i=0}^{\lfloor\frac{j}{2}\rfloor}\binom{N}{\lceil\frac{N}{2}\rceil+i}^{-1}=2F(N,\lfloor\frac{j}{2}\rfloor)\\\
&\leq
2+2\min\left\\{\lfloor\frac{j}{2}\rfloor,\frac{N}{\lfloor\frac{j}{2}\rfloor}\right\\}=2+2\min\left\\{\lfloor\frac{j}{2}\rfloor,\frac{2\ell+j}{\lfloor\frac{j}{2}\rfloor}\right\\}\\\
&\leq\frac{10(\ell+j+1)}{j+1}.\end{split}$

$\Box$

######  Claim 3.4.

For integers $\beta_{1},\beta_{2},\beta_{3}\geq 0$

${\rm
vol}_{2}(\Delta_{2})^{-1}\int_{y\in\Delta_{2}}y_{3}^{\beta_{1}}(y_{2}+y_{3})^{\beta_{2}}(y_{1}+y_{2})^{\beta_{3}}dy\leq\frac{2\beta_{1}!\beta_{3}!}{(\beta_{2}+1)(\beta_{1}+\beta_{3}+1)!}.$
(7)

Proof. Applying a change of variables $\phi:\\{(z_{1},z_{2}):0\leq z_{1}\leq
z_{2}\leq 1\\}\rightarrow\Delta_{2}$ given by
$\phi(z_{1},z_{2})=(1-z_{2},z_{2}-z_{1},z_{1})$ with Jacobian
$|J_{\phi}(z_{1},z_{2})|=\sqrt{3}$, we obtain

$\begin{split}&{\rm
vol}_{2}(\Delta_{2})^{-1}\int_{y\in\Delta_{2}}y_{3}^{\beta_{1}}(y_{2}+y_{3})^{\beta_{2}}(y_{1}+y_{2})^{\beta_{3}}dy\\\
&=\sqrt{3}\,{\rm vol}_{2}(\Delta_{2})^{-1}\int_{0\leq z_{1}\leq z_{2}\leq
1}z_{1}^{\beta_{1}}z_{2}^{\beta_{2}}(1-z_{1})^{\beta_{3}}dz_{1}\,dz_{2}\\\
&=2\int_{z_{1}=0}^{1}z_{1}^{\beta_{1}}(1-z_{1})^{\beta_{3}}\left(\int_{z_{2}=z_{1}}^{1}z_{2}^{\beta_{2}}dz_{2}\right)dz_{1}\\\
&\leq\frac{2}{\beta_{2}+1}\int_{z_{1}=0}^{1}z_{1}^{\beta_{1}}(1-z_{1})^{\beta_{3}}dz_{1}\\\
&=\frac{2\beta_{1}!\beta_{3}!}{(\beta_{2}+1)(\beta_{1}+\beta_{3}+1)!}.\end{split}$

$\Box$

Proof of Proposition 3.1.

$\begin{split}&I(k,\ell)={\rm
vol}_{2}(\Delta_{2})^{-2}\int_{(x,y)\in\Delta_{2}^{2}}\left(x_{1}y_{3}+x_{2}(y_{2}+y_{3})+x_{3}(y_{1}+y_{2})\right)^{k}(x_{3}y_{3})^{\ell}dx\,dy\\\
&=\sum_{\alpha\in A_{k,3}}\binom{k}{\alpha_{1};\alpha_{2};\alpha_{3}}{\rm
vol}_{2}(\Delta_{2})^{-2}\int_{(x,y)\in\Delta_{2}^{2}}(x_{1}y_{3})^{\alpha_{1}}(x_{2}(y_{2}+y_{3}))^{\alpha_{2}}(x_{3}(y_{1}+y_{2}))^{\alpha_{3}}(x_{3}y_{3})^{\ell}dx\,dy\\\
&=\sum_{\alpha\in
A_{k,3}}\frac{k!}{\alpha_{1}!\alpha_{2}!\alpha_{3}!}\left({\rm
vol}_{2}(\Delta_{2})^{-1}\int_{x\in\Delta_{2}}x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}x_{3}^{\alpha_{3}+\ell}dx\right)\left({\rm
vol}_{2}(\Delta_{2})^{-1}\int_{y\in\Delta_{2}}y_{3}^{\alpha_{1}+\ell}(y_{2}+y_{3})^{\alpha_{2}}(y_{1}+y_{2})^{\alpha_{3}}dy\right)\\\
&\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{\alpha\in
A_{k,3}}\frac{k!}{\alpha_{1}!\alpha_{2}!\alpha_{3}!}\cdot\left(\frac{2\alpha_{1}!\alpha_{2}!(\alpha_{3}+\ell)!}{(k+\ell+2)!}\right)\cdot\left(\frac{2(\alpha_{1}+\ell)!\alpha_{3}!}{(\alpha_{2}+1)(\alpha_{1}+\alpha_{3}+\ell+1)!}\right)\\\
&=\frac{4k!}{(k+\ell+2)!}\sum_{\alpha\in
A_{k,3}}\frac{(\alpha_{1}+\ell)!(\alpha_{3}+\ell)!}{(\alpha_{2}+1)(\alpha_{1}+\alpha_{3}+\ell+1)!}\\\
&=\frac{4k!}{(k+\ell+2)!}\sum_{j=0}^{k}\frac{1}{(k-j+1)(j+\ell+1)!}\sum_{(\alpha_{1},\alpha_{3})\in
A_{j,2}}(\alpha_{1}+\ell)!(\alpha_{3}+\ell)!\\\
&=\frac{4k!}{(k+\ell+2)!}\sum_{j=0}^{k}\frac{(2\ell+j)!}{(k-j+1)(j+\ell+1)!}\sum_{i=0}^{j}\binom{2\ell+j}{\ell+i}^{-1}\\\
&=\frac{4k!}{(k+\ell+2)!}\sum_{j=0}^{k}\frac{\ell!(\ell+j)!}{(k-j+1)(j+\ell+1)!}\binom{2\ell+j}{\ell+j}\sum_{i=0}^{j}\binom{2\ell+j}{\ell+i}^{-1}\\\
&\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{4k!\ell!}{(k+\ell+2)!}\sum_{j=0}^{k}\frac{1}{(k-j+1)(j+\ell+1)}\cdot\frac{10(\ell+j+1)}{j+1}\\\
&=\frac{40k!\ell!}{(k+2)(k+\ell+2)!}\sum_{j=0}^{k}\left(\frac{1}{k-j+1}+\frac{1}{j+1}\right)\\\
&=\frac{40}{k+2}\binom{k+\ell+2}{2}^{-1}\binom{k+\ell}{k}^{-1}\sum_{j=1}^{k+1}\frac{1}{j}\\\
&\leq\frac{40}{k+2}\binom{k+\ell+2}{2}^{-1}\binom{k+\ell}{k}^{-1}(1+\log(k+1)),\end{split}$

where (a) follows from (2) and (7), and (b) follows from (6).

$\Box$

##  4 The Upper Bound

In this section we prove Theorem 1.3(i). We first obtain a recursive upper
bound on $p_{r}(n)$.

######  Proposition 4.1.

Let $r\geq 1$ and $n\geq 3$. Then

$p_{r}(n)\leq 20\left(1+\log
n\right)\left(\frac{1}{n}+\sum_{k=0}^{n-3}\frac{p_{r-1}(n-2-k)}{k+2}\right).\\\
$ (8)

Proof. For $1\leq i<j\leq n$ and a subset $D\subset[n]\setminus\\{i,j\\}$ let
$R_{i,j,D}$ denote the set of all $q=(q_{1},\ldots,q_{n})\in\Omega_{n}$ such
that

  * (C1)

$i,j\in M(q)$.

  * (C2)

$\\{t\in[n]\setminus\\{i,j\\}:q_{t}\ngeq q_{i}\vee q_{j}\\}=D$.

Fix $c=(a_{1},a_{2},b_{1},b_{2})\in[0,1]^{4}$ such that $a_{1}<a_{2}$ and
$b_{2}<b_{1}$, and let

$\begin{split}E_{-}(c)&=[0,a_{1}]\times[0,b_{1}]\cup[0,a_{2}]\times[0,b_{2}]\setminus\\{(a_{1},b_{1}),(a_{2},b_{2})\\},\\\
E_{+}(c)&=[a_{2},1]\times[b_{1},1],\\\
E(c)&=[0,1]^{2}\setminus\left(E_{-}(c)\cup E_{+}(c)\right).\end{split}$

Figure 2: $E_{-}(c),E(c),E_{+}(c)$

Suppose now that $q=(q_{1},\ldots,q_{n})\in\Omega_{n}$ satisfies
$q_{i}=(a_{1},b_{1}),q_{j}=(a_{2},b_{2})$, see Figure 2. Then $q\in R_{i,j,D}$
iff $q_{t}\in E(c)$ for $t\in D$, and $q_{t}\in E_{+}(c)$ for
$t\in[n]\setminus(\\{i,j\\}\cup D)$. Writing

$\begin{split}x&=(x_{1},x_{2},x_{3})=(a_{1},a_{2}-a_{1},1-a_{2}),\\\
y&=(y_{1},y_{2},y_{3})=(b_{2},b_{1}-b_{2},1-b_{1}),\end{split}$

it follows that

$\begin{split}&{\rm Pr}\left[~{}q=(q_{1},\ldots,q_{n})\in
R_{i,j,D}~{}|~{}q_{i}=(a_{1},b_{1}),q_{j}=(a_{2},b_{2})\right]\\\ &={\rm
vol}_{2}\left(E(c)\right)^{|D|}{\rm vol}_{2}\left(E_{+}(c)\right)^{n-2-|D|}\\\
&=\left(a_{1}(1-b_{1})+(a_{2}-a_{1})(1-b_{2})+(1-a_{2})b_{1}\right)^{|D|}\left((1-a_{2})(1-b_{1})\right)^{n-2-|D|}\\\
&=\left(x_{1}y_{3}+x_{2}(y_{2}+y_{3})+x_{3}(y_{1}+y_{2})\right)^{|D|}\left(x_{3}y_{3}\right)^{n-2-|D|}.\end{split}$
(9)

Combining (9) and (3) and noting that the probability that $q_{i}$ and $q_{j}$
are incomparable is $\frac{1}{2}$ we obtain

$\begin{split}&{\rm Pr}\left[R_{i,j,D}\right]=\frac{1}{2}{\rm
vol}_{2}(\Delta_{2})^{-2}\int_{(x,y)\in\Delta_{2}^{2}}\left(x_{1}y_{3}+x_{2}(y_{2}+y_{3})+x_{3}(y_{1}+y_{2})\right)^{|D|}\left(x_{3}y_{3}\right)^{n-2-|D|}dx\,dy\\\
&=\frac{1}{2}I(|D|,n-2-|D|)\leq\frac{20}{|D|+2}\binom{n}{2}^{-1}\binom{n-2}{|D|}^{-1}\left(1+\log(|D|+1)\right).\end{split}$

Proposition 2.2 implies that if $Y_{q}$ is not $r$-connected then there exist
$1\leq i<j\leq n$ and $D\subset[n]\setminus\\{i,j\\}$ such that $q\in
R_{i,j,D}$ and the induced complex
$Y_{q}\left[[n]\setminus(D\cup\\{i,j\\})\right]$ is not $(r-1)$-connected.
Therefore by the union bound

$\begin{split}&p_{r}(n)\leq\sum_{1\leq i<j\leq
n}\sum_{D\subset[n]\setminus\\{i,j\\}}{\rm Pr}\left[q\in
R_{i,j,D}:Y_{q}\left[[n]\setminus(D\cup\\{i,j\\})\right]\text{~{}is~{}not~{}}(r-1)\text{-connected}\right]\\\
&=\sum_{1\leq i<j\leq n}\sum_{D\subset[n]\setminus\\{i,j\\}}{\rm
Pr}\left[R_{i,j,D}\right]p_{r-1}(n-2-|D|)\\\
&\leq\binom{n}{2}\sum_{k=0}^{n-2}\binom{n-2}{k}\left(\frac{20}{k+2}\binom{n}{2}^{-1}\binom{n-2}{k}^{-1}\left(1+\log
n\right)\right)\cdot p_{r-1}(n-2-k)\\\ &=20\left(1+\log
n\right)\sum_{k=0}^{n-2}\frac{p_{r-1}(n-2-k)}{k+2}\\\ &=20\left(1+\log
n\right)\left(\frac{1}{n}+\sum_{k=0}^{n-3}\frac{p_{r-1}(n-2-k)}{k+2}\right).\end{split}$

$\Box$

We also need the following observation.

######  Claim 4.2.

(i) $\frac{1}{n}\leq p_{0}(n)\leq\frac{4}{n}$ for $n\geq 2$. (ii)
$p_{0}(n)=\frac{2+o(1)}{n}$.

Proof. $X_{\pi}$ is disconnected iff there exists a $1\leq k\leq n-1$ such
that $1\leq\pi(i)\leq n-k$ for all $k+1\leq i\leq n$. It follows that for
$n\geq 5$

$\begin{split}p_{0}(n)&\leq\frac{1}{n!}\sum_{k=1}^{n-1}k!(n-k)!\leq\frac{2}{n}+\frac{4}{n(n-1)}+(n-5)\binom{n}{3}^{-1}\\\
&\leq\min\left\\{\frac{4}{n},\frac{2}{n}+\frac{10}{n(n-1)}\right\\}.\end{split}$

This proves the upper bounds in (i) and (ii). For the lower bounds note that
if $n\geq 2$ then

${\rm Pr}[X_{\pi}{\rm~{}is~{}disconnected~{}}]\geq{\rm
Pr}[\pi(1)=n{\rm~{}or~{}}\pi(n)=1]=\frac{2}{n}-\frac{1}{n(n-1)}.$

$\Box$

Proof of Theorem 1.3(i). We argue by induction on $r$. The induction base
$r=0$ follows from Claim 4.2(i). Assume now that $r\geq 1$. Applying (8) and
the induction hypothesis, it follows that

$\begin{split}&p_{r}(n)\leq 20\left(1+\log
n\right)\left(\frac{1}{n}+\sum_{k=0}^{n-3}\frac{p_{r-1}(n-2-k)}{k+2}\right)\\\
&\leq 20\log
3n\left(\frac{1}{n}+40^{r}\sum_{k=0}^{n-3}\frac{\log(3(n-k-2))^{2(r-1)}}{(k+2)(n-k-2)}\right)\\\
&\leq 20\log 3n\left(\frac{1}{n}+40^{r}(\log
3n)^{2(r-1)}\sum_{k=0}^{n-3}\frac{1}{(k+2)(n-k-2)}\right)\\\ &=20\log
3n\left(\frac{1}{n}+\frac{40^{r}(\log
3n)^{2(r-1)}}{n}\sum_{k=0}^{n-3}\left(\frac{1}{k+2}+\frac{1}{n-k-2}\right)\right)\\\
&=20\log 3n\left(\frac{1}{n}+\frac{40^{r}(\log
3n)^{2(r-1)}}{n}\left(\sum_{k=2}^{n-1}\frac{1}{k}+\sum_{k=1}^{n-2}\frac{1}{k}\right)\right)\\\
&\leq 20\log 3n\left(\frac{1}{n}+\frac{40^{r}(\log 3n)^{2(r-1)}}{n}(1+2\log
n)\right)\\\ &\leq 40^{r+1}\frac{(\log 3n)^{2r}}{n}.\end{split}$

$\Box$

##  5 The Lower Bound

The proof of Theorem 1.3(ii) depends on a homotopy decomposition result for
permutation complexes given in [2]. For $\pi\in\mathbb{S}_{n}$ and a subset
$A\subset[n]$, let $\psi_{A}(\pi)\in\mathbb{S}_{|A|}$ denote the permutation
pattern of $\pi$ restricted to $A$, i.e. if $A=\\{a_{1},\ldots,a_{k}\\}$ where
$a_{1}<\cdots<a_{k}$, then $\psi_{A}(\pi)=\sigma^{-1}$ where
$\sigma\in\mathbb{S}_{k}$ satisfies
$\pi(a_{\sigma(1)})<\cdots<\pi(a_{\sigma(k)})$. For $1\leq t\leq n$ define

$\pi_{t}^{\prime}=\psi_{[n]\setminus\\{t\\}}(\pi)\in\mathbb{S}_{n-1}~{}~{}~{},~{}~{}~{}\pi_{t}^{\prime\prime}=\psi_{[n]\setminus[t]}(\pi)\in\mathbb{S}_{n-t}.$

When $t=n$, we view $\pi_{t}^{\prime\prime}$ as the empty permutation and
define $X_{\pi_{t}^{\prime\prime}}=\emptyset$.

Let $\pi\in\mathbb{S}_{n}$ and let $i=\pi^{-1}(1),j=\pi^{-1}(2)$. As usual,
let $\Sigma X=S^{0}*X$ denote the suspension of a complex $X$.

######  Proposition 5.1 ([2]).

Let $\pi\in\mathbb{S}_{n}$ and let $i=\pi^{-1}(1),j=\pi^{-1}(2)$. Then

  * (i)

If $i<j$ then $X_{\pi}\simeq X_{\pi_{j}^{\prime}}$.

  * (ii)

If $i>j$ then $X_{\pi}\simeq X_{\pi_{i}^{\prime}}\vee\Sigma
X_{\pi_{i}^{\prime\prime}}$.

######  Proposition 5.2.

For $r\geq 1$ and $n\geq 2$

$p_{r}(n)\geq\frac{1}{n}\left(1+\frac{1}{n-1}\sum_{i=1}^{n}(i-1)p_{r-1}(n-i)\right).$
(10)

Proof. Fix $1\leq j<i\leq n$. By Proposition 5.1(ii)

$\begin{split}&{\rm
Pr}\left[\pi\in\mathbb{S}_{n}:\pi^{-1}(1)=i,\pi^{-1}(2)=j,X_{\pi}\text{~{}is~{}not~{}}r\text{-connected}\right]\\\
&\geq{\rm
Pr}\left[\pi\in\mathbb{S}_{n}:\pi^{-1}(1)=i,\pi^{-1}(2)=j,X_{\pi_{i}^{\prime\prime}}\text{~{}is~{}not~{}}(r-1)\text{-connected}\right]\\\
&=\frac{p_{r-1}(n-i)}{n(n-1)}.\end{split}$ (11)

Summing (11) over all $1\leq j<i\leq n$ it follows that

$\begin{split}p_{r}(n)&\geq\sum_{1\leq j<i\leq n}{\rm
Pr}\left[\pi\in\mathbb{S}_{n}:\pi^{-1}(1)=i,\pi^{-1}(2)=j,X_{\pi}\text{~{}is~{}not~{}}r\text{-connected}\right]\\\
&\geq\sum_{1\leq j<i\leq
n}\frac{p_{r-1}(n-i)}{n(n-1)}=\frac{1}{n(n-1)}\sum_{1\leq i\leq
n}(i-1)p_{r-1}(n-i)\\\
&=\frac{1}{n}\left(1+\frac{1}{n-1}\sum_{i=1}^{n-1}(i-1)p_{r-1}(n-i)\right).\end{split}$

$\Box$

Proof of Theorem 1.3(ii). We argue by induction on $r$. The induction base
$r=0$ follows from Claim 4.2(i). Assume now that $r\geq 1$. Applying (10) and
the induction hypothesis we obtain

$\begin{split}p_{r}(n)&\geq\frac{1}{n(n-1)}\sum_{i=1}^{n-1}(i-1)p_{r-1}(n-i)\\\
&=\frac{1}{n(n-1)}\sum_{i=1}^{n-1}(n-1-i)p_{r-1}(i)\\\
&\geq\frac{1}{n(n-1)}\sum_{i=1}^{n-1}(n-1-i)\left(\frac{1}{(r-1)!}\frac{(\log
i)^{r-1}}{i}-c_{r-1}\frac{(\log i)^{r-2}}{i}\right)\\\
&\geq\frac{1}{n}\sum_{i=2}^{n-1}\left(\frac{(\log
i)^{r-1}}{(r-1)!i}-c_{r-1}\frac{(\log
i)^{r-2}}{i}\right)-\frac{1}{(r-1)!n(n-1)}\sum_{i=2}^{n-1}(\log i)^{r-1}\\\
&\geq\frac{1}{(r-1)!n}\int_{1}^{n}\frac{(\log
t)^{r-1}dt}{t}-c_{r-1}\frac{(\log
n)^{r-2}}{n}\sum_{i=2}^{n-1}\frac{1}{i}-\frac{1}{(r-1)!}\frac{(\log
n)^{r-1}}{n}\\\ &\geq\frac{1}{r!}\frac{(\log
n)^{r}}{n}-\left(c_{r-1}+\frac{1}{(r-1)!}\right)\frac{(\log n)^{r-1}}{n}\\\
&=\frac{1}{r!}\frac{(\log n)^{r}}{n}-c_{r}\frac{(\log
n)^{r-1}}{n}.\end{split}$

$\Box$

##  6 Concluding Remarks

In this paper we studied the topological connectivity of the order complex
$Y_{q}$ of a sequence of $n$ random points $q=(q_{1},\ldots,q_{n})$ in the
unit square. More generally, let $Y_{d,q}$ denote the order complex determined
by sequence of $n$ points
$q=(q_{1},\ldots,q_{n})\in\Omega_{d,n}=\left([0,1]^{d}\right)^{n}$. Our work
suggests a number of directions for further research.

  * •

One natural problem is to close the gap between the lower and upper bounds in
Theorem 1.3. It seems likely that the lower bound
$p_{r}(n)=\Omega\left(\frac{(\log n)^{r}}{n}\right)$ is closer to the truth.

  * •

Theorem 1.1 asserts that $Y_{2,q}=Y_{q}$ is a wedge of spheres. Is there a
simple characterization of the homotopy type of $Y_{d,q}$ for general $d$?

  * •

Let $p_{d,r}(n)$ denote the probability that $Y_{d,q}$ is $r$-connected for a
random $q=(q_{1},\ldots,q_{n})\in\Omega_{d,n}$. It would be interesting to
extend Theorem 1.3 to general $d$. Our proof of the upper bound
$p_{2,r}(n)=p_{r}(n)=O\left(\frac{(\log n)^{2r}}{n}\right)$ does not use very
specific properties of two dimensional posets (such as Theorem 1.1 and the
homotopy decomposition in Proposition 5.1), and may thus be relevant to higher
dimensions as well.

Acknowledgement: We would like to thank Russ Woodroofe for bringing reference
[3] to our attention.

## References

  * [1] A. Björner, Nerves, fibers and homotopy groups, J. Combin. Theory Ser. A, 102(2003) 88–93.
  * [2] W. Chacholski, R. Levi and R. Meshulam, On the topology of complexes of injective words, J. Appl. Comput. Topol., 4(2020) 29–44.
  * [3] J. H. Przytycki and M. Silvero, Homotopy type of circle graph complexes motivated by extreme Khovanov homology, J. Algebraic Combin., 48(2018) 119–156.
  * [4] W. Rudin, Principles of mathematical analysis. Third edition. International Series in Pure and Applied Mathematics. McGraw-Hill Book Co., New York-Auckland-Düsseldorf, 1976.
  * [5] P. Winkler, Connectedness and diameter for random orders of fixed dimension, Order, 2(1985) 165–171.


# Complex numbers with a prescribed order of approximation and Zaremba’s
conjecture

Gerardo González Robert  ,  Mumtaz Hussain  and  Nikita Shulga  Department of
Mathematical and Physical Sciences, La Trobe University, Bendigo 3552,
Australia<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Given $b=-A\pm i$ with $A$ being a positive integer, we can represent any
complex number as a power series in $b$ with coefficients in
$\mathcal{A}=\\{0,1,\ldots,A^{2}\\}$. We prove that, for any real $\tau\geq 2$
and any non-empty proper subset $J(b)$ of $\mathcal{A}$, there are uncountably
many complex numbers (including transcendental numbers) that can be expressed
as a power series in $b$ with coefficients in $J(b)$ and with the
irrationality exponent (in terms of Gaussian integers) equal to $\tau$. One of
the key ingredients in our construction is the ‘Folding Lemma’ applied to
Hurwitz continued fractions. This motivates a Hurwitz continued fraction
analogue of the well-known Zaremba’s conjecture. We prove several results in
support of this conjecture.

##  1\. Introduction

Real numbers are commonly represented in integer base expansions. It is thus
natural to consider a similar representation of complex numbers in terms of a
Gaussian integer base. However, this proves to be a more intricate problem
compared to its real number counterpart. Specifically, suppose we have a
Gaussian integer $b$ such that $|b|>1$ and let $\mathcal{A}$ be a system of
representatives $\pmod{b}$. When $\operatorname{Re}(b)$ and
$\operatorname{Im}(b)$ are coprime, we may consider
$\mathcal{A}=\\{0,1,\ldots,|b|^{2}-1\\}$ (see, for example, [2, Theorem
3.10.4])). Under this assumption, Kátai and Szabó showed that for each
Gaussian integer $z$ there exists a unique sequence $(d_{j})_{j\geq 0}$ in
$\mathcal{A}$ satisfying

$\lim_{n\to\infty}d_{j}=0\quad\text{ and }\quad
z=\sum_{j=0}^{\infty}d_{j}b^{j}$

if and only if $b=-A\pm i$ for some $A\in\mathbb{N}$ (see [19, Theorem 1] and
[28] for a generalisation). Furthermore, in the same paper, they proved under
the same assumptions that for each complex number $\zeta$ there is a sequence
$(d_{j})_{j\in\mathbb{Z}}$ in $\mathcal{A}$ satisfying

$\lim_{n\to-\infty}d_{j}=0\quad\text{ and
}\quad\sum_{j\in\mathbb{Z}}^{l}d_{j}b^{-j}.$

These expansions lead to situations not encountered in the real case. For
example, the boundary of the set

$\left\\{\sum_{j\in\mathbb{N}}\frac{d_{j}}{b^{j}}:\forall
j\in\mathbb{N}\;\quad d_{j}\in\\{0,1,\ldots,A^{2}\\}\right\\}$

exhibits a fractal structure with the Hausdorff dimension in the interval
$(1,2)$ (see [1, 11]).

In this paper, we restrict assume that $b=-A\pm i$ for some $A\in\mathbb{N}$.
By $J(b)$ we mean a proper subset of $\\{0,1,\ldots,A^{2}\\}$ and we define
the set

$\mathcal{K}_{J(b)}:=\left\\{\zeta=\sum_{j\in\mathbb{N}}d_{j}b^{-j}:\ \
d_{j}\in J(b)\text{ for all }j\in\mathbb{N}\right\\}.$

Although there are uncountably many complex numbers with more than one
expansion in base $b$, we can easily find non-empty sets
$J(b)\subset\\{0,1,\ldots,A^{2}\\}$ for which $\mathcal{K}_{J(b)}$ is a Cantor
set. Our first goal is to study approximation properties of elements in
$\mathcal{K}_{J(b)}$. To this end, for each positive function
$\Psi:\mathbb{R}_{\geq 1}\to\mathbb{R}_{>0}$, define the set of
$\Psi$-approximable numbers to be

$\mathcal{K}(\Psi):=\left\\{\zeta\in\mathbb{C}:\left|\zeta-\frac{p}{q}\right|<\Psi(|q|)\text{
for infinitely many }\frac{p}{q}\in\mathbb{Q}(i)\right\\}.$

The set of complex numbers exactly approximable to order $\Psi$ is defined to
be

$\operatorname*{Exact}(\Psi):=\mathcal{K}(\Psi)\setminus\bigcup_{k\in\mathbb{N}}\mathcal{K}\left(\left(1-\frac{1}{k+1}\right)\Psi\right).$

The irrationality exponent $\mu(\xi)$ of a complex number
$\xi\in\mathbb{C}\setminus\mathbb{Q}(i)$ is given by

$\mu(\xi):=\sup\left\\{\mu\in\mathbb{R}:\left|\xi-\frac{p}{q}\right|<\frac{1}{|q|^{\mu}}\text{
for infinitely many }\frac{p}{q}\in\mathbb{Q}(i)\right\\}.$

The definitions of $\mathcal{K}(\Psi)$ and $\mu(\xi)$ are obvious analogues of
those for real numbers, where we consider approximations by numbers in
$\mathbb{Q}$ rather than in $\mathbb{Q}(i)$. In this context, a famous problem
by Mahler [24, Section 2] is to determine how well can irrational numbers in
the middle-third Cantor set $K$ be approximated by rationals. Expressed
differently, he asked whether $K$ contains numbers with a prescribed
irrationality exponent $\tau$. Levesley, Salp, and Velani [23] solved Mahler’s
question by showing that the set of real numbers in $K$ whose irrationality
exponent is strictly larger than two, has a positive Hausdorff dimension. They
also gave examples of numbers (in fact transcendental numbers) in $K$ with the
irrationality exponent larger than $\frac{3+\sqrt{5}}{2}$. Shortly afterward,
Bugeaud [5] constructed numbers in $K$ with any prescribed irrationality
exponent $\tau\geq 2$. In the same paper, Bugeaud proposed a stronger version
of Mahler’s problem:

Given a positive function $\Psi$, is
$K\cap\operatorname*{Exact}(\Psi)\neq\varnothing$ true?

In the complex plane, Bugeaud’s strengthening of Mahler’s problem can be
extended as follows:

for $b$ and $J(b)$ as above and a positive function $\Psi$, is the set
$\operatorname*{Exact}(\Psi)\cap\mathcal{K}_{J(b)}$ non-empty?

Our first result extends Bugeaud’s answer to complex numbers for a slightly
weaker problem.

######  Theorem 1.1.

Let $b\in\mathbb{Z}[i]$ be of the form $b=-A\pm i$ with $A\in\mathbb{N}$, let
$J(b)$ be any proper subset of $\\{0,1,\ldots,A^{2}\\}$, and let
$\Psi:\mathbb{R}_{>1}\to\mathbb{R}_{\geq 0}$ be a function such that
$x^{2}\Psi(x)\to 0$ as $x\to\infty$, and $x\mapsto x^{2}\Psi(x)$ is
decreasing. Then, for any number $c\in(0,|b|^{-1})$, the set
$\left(\mathcal{K}(\Psi)\setminus\mathcal{K}(c\Psi)\right)\cap K_{J(b)}$ is
non-empty. Moreover, when $A\geq 2$, the intersection is uncountable.

The set $\operatorname*{Exact}(\Psi)$ in the complex case was considered by He
and Xiong [13, Theorem 1.2]. They calculated its Hausdorff and packing
dimensions for any $\Psi$ satisfying the hypothesis of Theorem 1.1. As stated
above, in the real case, the exact approximation sets were comprehensively
studied by Bugeaud [4, 5, 6] under similar asymptotic conditions on $\Psi$.

The theory of Hurwitz continued fractions tells us that $\mu(\xi)\geq 2$ for
all $\xi\in\mathbb{C}\setminus\mathbb{Q}(i)$ (see statement (3) in Proposition
3.2). Now by considering $\tau\geq 2$, $\Psi(x)=x^{-\tau}(\log(1+x))^{-1}$,
and $J(b)=\\{0,1\\}$, Theorem 1.1 implies that $\mathcal{K}_{J(b)}$ contains
irrational numbers $\xi$ such that $\mu(\xi)=\tau$. The proof of Theorem 1.1
gives us some of those numbers $\xi$ explicitly, which we can formulate in the
following way.

######  Theorem 1.2.

Let $b$ be a Gaussian integer of the form $b=-A\pm i$ with
$A\in\mathbb{N}_{\geq 2}$. For each $\lambda>0$ define

$n_{0}(\lambda,\tau):=1+\max\left\\{\
0,\left\lfloor\frac{\log(3/\lambda)}{\log\tau}\right\rfloor,\frac{\log
3}{\log|b|}\right\\}.$

Then, the complex number

$\xi(\tau,\lambda)=\sum_{n\geq
n_{0}(\lambda,\tau)}\,\frac{1}{b^{\lfloor\lambda\tau^{n}\rfloor}}\in
K_{\\{0,1\\}}$

has irrationality exponent $\mu(\xi(\tau,\lambda))=\tau$. Furthermore, when
$\tau=2$, the numbers $\xi(\tau,\lambda)$ are badly approximable.

######  Corollary 1.3.

Let $\tau\geq 2$ be arbitrary. If $b=-A\pm i$ for some $A\in\mathbb{N}$ and
$J(b)=\\{0,1\\}$, then $\mathcal{K}_{J(b)}$ contains uncountably many complex
numbers with irrationality exponent $\tau$.

######  Remark 1.4.

When $A=1$, we have $\mathcal{K}_{J(b)}=\mathbb{C}$ by [19, Theorem 2]. In
this case, Corollary 1.3 follows trivially.

The proofs of Theorem 1.1 and Theorem 1.2 use the theory of Hurwitz continued
fractions (HCFs). The literature on HCFs is not yet fully developed akin to
regular real continued fractions (RCFs), however, there has been some progress
in developing the metrical properties of HCFs to study sets of complex numbers
defined by Diophantine approximation conditions. When proving Theorems 1.1 and
1.2, we need Gaussian rationals of the form $r/b^{v}$ with $v\in\mathbb{N}$,
whose HCFs satisfy certain properties. This is not an easy task when we impose
an upper bound independent of $b$ on the partial quotients. However, the HCF
analogue of the well-known Zaremba’s conjecture (1971) asserts that we can
always do it.

######  Conjecture 1.5 (Zaremba’s Conjecture for Hurwitz continued fractions).

There exists an absolute constant $\boldsymbol{\eta}\in\mathbb{R}$ with the
following property: for any $b\in\mathbb{Z}[i]\backslash\\{0,\pm 1,\pm i\\}$,
there exists $a\in\mathbb{Z}[i]\backslash\\{0\\}$ with $\gcd(a,b)=1$ and
$a/b\in\mathfrak{F}$, with $\mathfrak{F}$ from (5), such that if
$a/b=[a_{1},\ldots,a_{n}]_{\mathbb{C}}$ is a HCF, then
$\max_{i}|a_{i}|~{}\leq~{}\boldsymbol{\eta}$.

We prove Zaremba’s conjecture in several special cases (in Section 5): for
denominators of the form

  * •

$b=(-3\pm i)^{n},(-2\pm i)^{n},\,n\geq 1$ with $\boldsymbol{\eta}=3\sqrt{2}$,
see Theorems 5.1 and 5.2.

  * •

$b=2^{n},3^{n},\,n\geq 1$ with $\boldsymbol{\eta}=8$, see Theorems 5.3 and
5.6.

  * •

$b=5^{n},\,n\geq 1$ with $\boldsymbol{\eta}=7$, see Theorem 5.7.

In the context of real numbers and regular continued fractions, Niederreiter
proved Zaremba’s Conjecture for powers of $2$ and $3$ with
$\boldsymbol{\eta}=3$ in [27]. In recent years, Zaremba’s conjecture has been
extensively studied. We refer to [3, 16, 25, 26, 29] for some other results on
Zaremba’s conjecture.

Note that the bounds $\boldsymbol{\eta}$ which we got for the HCF analogue of
Zaremba’s conjecture are weaker than their real counterparts. We believe this
should be the case by the nature of HCF. For RCFs, every sequence of natural
numbers is a sequence of partial quotients of some number $x\in\mathbb{R}$.
For a sequence of Gaussian integers and HCFs, analogous statement is not true.
First of all, HCF partial quotients cannot take values from $\\{0,\pm 1,\pm
i\\}$. Furthermore, there are some non-trivial dependence relations between
successive partial quotients, which pose some restrictions disproportionally
affecting partial quotients with small absolute values. As Zaremba’s
conjecture deals with very small partial quotients (in fact, in the real case
it is conjectured that even $\boldsymbol{\eta}=2$ should work for large enough
prime numbers $q$ as denominators), HCF expansions are naturally forced to
take larger partial quotients more often. For more details, see Section 3 and
Remark 5.5 below.

The paper is organised in the following manner. In Section 2, we recall of one
of our key tools: Folding Lemma. Section 3 contains notation, terminology, and
basic facts on HCFs. Theorems 1.1 and 1.2 are proven in Section 4. In Section
5 we give a formal statement and proofs of our results around Zaremba’s
Conjecture for HCFs. Lastly, in Section 6 we check that the continued
fractions obtained by a repeated application of Folding Lemma are indeed HCFs.

Acknowledgments: This research is supported by the Australian Research Council
discovery project grant number 200100994. We are thankful to Johannes
Schleischitz for posing this question during the Trends in Metric Number
Theory Conference.

##  2\. The continued fraction apparatus

A continued fraction is an object of the form

(1) $a_{0}+\cfrac{1}{a_{1}+\cfrac{1}{a_{2}+\cfrac{1}{a_{3}+\ddots}}},$

which can conveniently be denoted as $[a_{0};a_{1},\ldots,a_{n},\ldots]$. When
$a_{0}=0$, we will sometimes write
$[a_{1},\ldots,a_{n},\ldots]:=[0;a_{1},\ldots,a_{n},\ldots]$. The coefficients
$a_{i}$’s in different contexts can be very different things, for example,
positive integers, non-zero integers, polynomials, complex numbers, and many
others. Denote a finite truncation of (1) as

$\frac{p_{n}}{q_{n}}=[a_{0};a_{1},\ldots,a_{n}].$

It is well-known (see, for example, [20, Theorem 1]) that the sequences
$(p_{n})_{n\geq 0}$ and $(q_{n})_{n\geq 0}$ satisfy the following recursion
formulae

(2) $\displaystyle p_{-1}$ $\displaystyle=1,$ $\displaystyle p_{0}$
$\displaystyle=a_{0},$ $\displaystyle p_{n}$
$\displaystyle=a_{n}p_{n-1}+p_{n-2};$ (3) $\displaystyle q_{-1}$
$\displaystyle=0,$ $\displaystyle q_{0}$ $\displaystyle=1,$ $\displaystyle
q_{n}$ $\displaystyle=a_{n}q_{n-1}+q_{n-2}.$

We refer to the sequences $(p_{n})_{n\geq 0}$ and $(q_{n})_{n\geq 0}$ as the
sequences of numerators and denominators of $[a_{0};a_{1},a_{2},\ldots]$
respectively. Next, we gather some properties of continued fractions that can
be found in standard books, see for example [20, Chapter 1].

######  Proposition 2.1.

Take $n\in\mathbb{N}$ and a continued fraction $[a_{0};a_{1},\ldots,a_{n}]$,
then

$\displaystyle q_{n}p_{n-1}-q_{n-1}p_{n}$ $\displaystyle=(-1)^{n},$
$\displaystyle\frac{p_{n}\alpha+p_{n-1}}{q_{n}\alpha+q_{n-1}}$
$\displaystyle=[a_{0};a_{1},\ldots,a_{n},\alpha]\text{ for a variable
}\alpha\neq 0,$ $\displaystyle\frac{q_{n-1}}{q_{n}}$
$\displaystyle=[a_{n},\ldots,a_{1}],$ $\displaystyle x-\frac{q_{n-1}}{q_{n}}$
$\displaystyle=[x;-a_{n},\ldots,-a_{1}]\text{ for a variable }x.$

Next, we state the remarkable folklore result known as the “Folding Lemma”.

######  Lemma 2.2 ([31], Proposition 2).

If $p_{n}/q_{n}=[a_{0};a_{1},\ldots,a_{n}]$, then for any nonzero $x$,we have

(4)
$\frac{p_{n}}{q_{n}}+\frac{(-1)^{n}}{xq_{n}^{2}}=\left[a_{0};a_{1},\ldots,a_{n},x,-a_{n},\ldots,-a_{1}\right].$

Given the importance of this lemma in the proofs to follow, we include its
proof.

###### Proof.

Certainly,

$\displaystyle\frac{p_{n}}{q_{n}}+\frac{(-1)^{n}}{xq_{n}^{2}}$
$\displaystyle=\frac{p_{n}}{q_{n}}+\frac{q_{n}p_{n-1}-q_{n-1}p_{n}}{xq_{n}^{2}}=\frac{xq_{n}p_{n}+q_{n}p_{n-1}-q_{n-1}p_{n}}{xq_{n}^{2}}$
$\displaystyle=\frac{p_{n}(xq_{n}-q_{n-1})+q_{n}+p_{n-1}}{q_{n}(xq_{n})}=\frac{p_{n}(x-q_{n-1}/q_{n})+p_{n-1}}{xq_{n}+q_{n-1}+q_{n-1}}$
$\displaystyle=\frac{p_{n}(x-q_{n-1}/q_{n})+p_{n-1}}{q_{n}(x-q_{n-1}/q_{n})+q_{n-1}}=\left[a_{0};a_{1},\ldots,a_{n},x-\frac{q_{n-1}}{q_{n}}\right]$
$\displaystyle=\left[a_{0};a_{1},\ldots,a_{n},x,-a_{n},\ldots,-a_{1}\right].$

∎

##  3\. Hurwitz Continued Fractions

In this section we introduce Hurwitz continued fractions and some of their
basic properties. Let $\lfloor\,\cdot\,\rfloor:\mathbb{R}\to\mathbb{Z}$ be the
floor function. The nearest Gaussian integer to a given complex number
$z\in\mathbb{C}$ is

$[z]:=\left\lfloor\operatorname{Re}(z)+\frac{1}{2}\right\rfloor+i\left\lfloor\operatorname{Im}(z)+\frac{1}{2}\right\rfloor.$

Let $\mathfrak{F}$ be the the unit square centered given by

(5)
$\mathfrak{F}=\\{z\in\mathbb{C}:[z]=0\\}=\left\\{z\in\mathbb{C}:-\frac{1}{2}\leq\operatorname{Re}(z)<\frac{1}{2},\;-\frac{1}{2}\leq\operatorname{Im}(z)<\frac{1}{2}\right\\}.$

The complex Gauss map, $T:\mathfrak{F}\to\mathfrak{F}$, is the function given
by

$\forall z\in\mathbb{C}\quad T(z)=\begin{cases}z^{-1}-[z^{-1}],\text{ if
}z\neq 0,\\\ 0,\text{ if }z=0.\end{cases}$

Let $T^{0}$ be the identity map on $\mathfrak{F}$ and put $T^{n}:=T\circ
T^{n-1}$ for all $n\in\mathbb{N}$. Define
$a_{1}:\mathfrak{F}\setminus\\{0\\}\to\mathbb{Z}[i]$ by
$a_{1}(z)\colon=[z^{-1}]$ and, while $T^{n-1}(z)\neq 0$, write
$a_{n}(z):=a_{1}(T^{n-1}(z))$. The Hurwitz Continued Fraction of $z$ is
$[a_{1}(z),a_{2}(z),\ldots]_{\mathbb{C}}$. The terms of the sequence
$(a_{n})_{n\geq 1}$ are the partial quotients of $z$. We extend the definition
of HCFs to $\mathbb{C}$ by putting $a_{0}(z)=[z]$ and
$a_{n}(z):=a_{n}(z-a_{0})$, $n\in\mathbb{N}$. When introducing this continued
fraction, Hurwitz showed that a complex number $\zeta$ belongs to
$\mathbb{C}\setminus\mathbb{Q}(i)$ if and only if its sequence of partial
quotients is infinite and, in this case,

$\zeta=\lim_{n\to\infty}\frac{p_{n}}{q_{n}}$

[17]. The partial quotients of an HCF may only take values in the set
$\mathcal{D}:=\mathbb{Z}[i]\setminus\\{0,1,i,-1,-i\\}$ (see for example [8,
Section 6]). We will also use $\mathcal{D}^{+}$ to denote the set of finite
and non-empty sequences on $\mathcal{D}$. We refer to “$a_{i}\in\mathcal{D}$”
as the trivial restriction. For any $n\in\mathbb{N}$ and each
$\mathbf{b}=(b_{1},\ldots,b_{n})\in\mathcal{D}^{n}$, the cylinder of level $n$
based on $\mathbf{b}$ is defined as

$\mathcal{C}_{n}(\mathbf{b}):=\\{z\in\mathfrak{F}:a_{1}(z)=b_{1},\ldots,a_{n}(z)=b_{n}\\}.$

The prototype set based on $\mathbf{b}$ is
$\mathfrak{F}_{n}(\mathbf{b}):=T^{n}\left(\mathcal{C}_{n}(\mathbf{b})\right)$.
By $\mathcal{C}^{\circ}_{n}(\mathbf{b})$ we mean the interior of
$\mathcal{C}_{n}(\mathbf{b})$ and we define
$\mathfrak{F}^{\circ}_{n}(\mathbf{b})$ and $\mathfrak{F}^{\circ}$ analogously.
We say that $\mathbf{b}$ is valid (resp. full) if
$\mathcal{C}_{n}(\mathbf{b})\neq\varnothing$ (resp.
$\mathfrak{F}_{n}^{\circ}(\mathbf{b})=\mathfrak{F}^{\circ}$). Let $\Omega(n)$
(resp. $\mathsf{F}(n)$) be the set of all valid (resp. full) words of length
$n$, thus $\mathsf{F}(n)\subseteq\Omega(n)$. It is easy to check that there
are exactly thirteen different non-empty sets of the form
$\mathfrak{F}^{\circ}_{n}(\mathbf{a})$ (see, for example, [9, Section 2]). We
say that $\mathbf{b}=(b_{1},\ldots,b_{n})\in\Omega(n)$ is reversible if
$\overleftarrow{\mathbf{b}}:=(b_{n},\ldots,b_{1})\in\Omega(n)$.

In general, it might be hard to determine whether a finite sequence is valid
or not. However, this occurs when the digits are large enough.

######  Proposition 3.1 ([7, Proposition 4.3] ).

Let $\mathbf{a}=(a_{j})_{j\geq 1}$ be a sequence in $\mathcal{D}$ such that
$\min_{j}|a_{j}|\geq\sqrt{8}$.

  1. (1)

If $\mathbf{a}$ is finite, say $\mathbf{a}=(a_{1},\ldots,a_{n})$ for
$n\in\mathbb{N}$, then $\mathbf{a}\in\mathsf{F}(n)$; in particular,
$\mathbf{a}\in\Omega(n)$.

  2. (2)

If $\mathbf{a}=(a_{j})_{j\geq 1}$ is infinite, then
$\zeta=[a_{1},a_{2},\ldots]_{\mathbb{C}}$ for some
$\zeta\in\mathbb{C}\setminus\mathbb{Q}(i)$.

Consider $n\in\mathbb{N}$ and let $(a_{1},\ldots,a_{n})\in\mathcal{D}^{n}$ be
such that $\mathcal{C}^{\circ}_{n}(a_{1},\ldots,a_{n})\neq\varnothing$. When
the assumptions of statement (1) in Proposition 3.1 are not met, there might
exist Gaussian integers $a_{n+1}\in\mathcal{D}$ for which
$\mathcal{C}^{\circ}_{n+1}(a_{1},\ldots,a_{n+1})=\varnothing$ or even
$\mathcal{C}_{n+1}(a_{1},\ldots,a_{n+1})=\varnothing$. For example,
$\mathcal{C}_{2}(-1+2i,1+i)=\varnothing$, and
$\mathcal{C}_{2}(-2,1+4i)\neq\varnothing$ but
$\mathcal{C}^{\circ}_{2}(-2,1+4i)=\varnothing$. Table 1, inspired by one in
[14, p. 75], tells us how to choose $a_{n+1}$ so that
$\mathcal{C}^{\circ}_{n+1}(a_{1},\ldots,a_{n+1})\neq\varnothing$.

Conditions on $a_{n}$ | Maximal subset of $\mathcal{D}$ containing $a_{n+1}$
---|---
$\max\\{|\operatorname{Re}(a_{n})|,|\operatorname{Im}(a_{n})|\\}\geq 3$ | $\mathcal{D}$
$1+i$ | $\\{a\in\mathcal{D}:\operatorname{Im}(a_{n+1})<0<\operatorname{Re}(a_{n+1})\\}$
$2$ | $\\{a\in\mathcal{D}:\operatorname{Re}(a_{n+1})\geq 0\\}$
$2+i$ | either $\mathcal{D}\setminus\\{-1+i\\}$ or $\\{a\in\mathcal{D}:\operatorname{Re}(a)\geq 0\\}$
$-1+2i$ | either $\mathcal{D}\setminus\\{1+i\\}$ or $\\{a\in\mathcal{D}:\operatorname{Re}(a)\leq 0\\}$
Table 1. Non-trivial restrictions.

The table remains true if we multiply both columns by the same integral power
of $i$ or if we apply complex conjugation. Some care is needed in the last two
lines, though. When $|a_{n}|=\sqrt{5}$, the open prototype set
$\mathfrak{F}^{\circ}_{j}(a_{1},\ldots,a_{j})$ may have two different forms.
For instance, for $2+i$ we have

$\mathfrak{F}^{\circ}_{2}(2+2i,2+i)=\mathfrak{F}_{1}^{\circ}(2+i)\quad\text{
and }\quad\mathfrak{F}^{\circ}_{2}(-2+i,2+i)=\mathfrak{F}_{1}^{\circ}(2).$

As a consequence, note that while $(2+2i,2+i,-3+4i)$ is valid,
$(-2+2i,2+i,-3+4i)$ is not.

In the next proposition, we collect some important properties of HCFs.

######  Proposition 3.2.

Take $z\in\mathfrak{F}\setminus\\{0\\}$ and let $(p_{n})_{n\geq 1}$,
$(q_{n})_{n\geq 1}$ be as in (2).

  1. (1)

[8, Theorem 6.1]. The sequence $(|q_{n}|)_{n\geq 0}$ is strictly increasing.

  2. (2)

[8, Proposition 3.3]. If
$z=[a_{1},a_{2},\ldots]_{\mathbb{C}}\in\mathfrak{F}\setminus\mathbb{Q}(i)$,
then

$\text{for all \ }n\in\mathbb{N},\quad
z=\frac{(a_{n+1}+[a_{n+2},a_{n+3},\ldots]_{\mathbb{C}})p_{n}+p_{n-1}}{(a_{n+1}+[a_{n+2},a_{n+3},\ldots]_{\mathbb{C}})q_{n}+q_{n-1}}.$

  3. (3)

[21, Theorem 1]. For every $n\in\mathbb{N}$, we have

$\left|\zeta-\frac{p_{n}}{q_{n}}\right|<\frac{1}{|q_{n}|^{2}}.$

  4. (4)

[13, Lemma 2.2]. Take $p,q\in\mathbb{Z}[i]$ with $q\neq 0$. If

$\left|\zeta-\frac{p}{q}\right|<\frac{1}{4|q|^{2}},$

then $\frac{p}{q}=\frac{p_{n}}{q_{n}}$ for some $n\in\mathbb{N}$.

When restricted to real numbers, HCFs partial quotients may take values in
$\mathbb{Z}\setminus\\{-1,0,1\\}$. Hence, obviously, it may not coincide with
the RCFs expansion. For reference, we state the next remark.

######  Remark 3.3.

Let $\mathbf{a}=(a_{1},\ldots,a_{n})\in\mathbb{Z}[i]^{n}$. The following
statements are true.

  1. (1)

If $[a_{1},\ldots,a_{n}]_{\mathbb{R}}$ is a RCF of a real number $x\in[0,1]$,
then $[a_{n},\ldots,a_{1}]_{\mathbb{R}}$ is also the RCF of some real number
$y\in[0,1]$.

  2. (2)

If $\mathbf{a}\in\Omega(n)$, then in general it is not true that $\mathbf{a}$
is reversible.

  3. (3)

If $\mathbf{a}\in\Omega(n)$ and for all $i$ one has $a_{i}\in\mathbb{Z}$, then
$\mathbf{a}$ is reversible if and only if for every $2\leq k\leq n$ such that
$|a_{k}|=2$, we have $a_{k-1}a_{k}>0$.

  4. (4)

(Corollary of the previous statement) If $\mathbf{a}\in\Omega(n)$ and for all
$1\leq i\leq n$ we have $|a_{i}|\geq 3,a_{i}\in\mathbb{Z}$, then $\mathbf{a}$
is reversible.

The statement (3) of Remark 3.3 can also be seen as a corollary of Proposition
1.1 from [30], where Simmons investigated properties of HCFs the of real
numbers. We refer to his paper for more details.

##  4\. Proofs of Theorem 1.1 and Theorem 1.2

We start off by providing some estimates on the approximation by the $n$th
convergent. Next, we construct a family of complex numbers depending on
certain parameters using Folding Lemma. Finally, we obtain Theorem 1.1 and
Theorem 1.2 by appropriately choosing the values of the parameters and
checking that the conclusions are true.

Lakein [21, Theorem 2] proved that Hurwitz continued fractions provide good
Gaussian rational approximations to a given number $\zeta\in\mathbb{C}$ in the
sense that, for any $n\in\mathbb{N}$,

$|q_{n}\zeta-
p_{n}|=\min\left\\{|q^{\prime}\zeta-p^{\prime}|:p^{\prime},q^{\prime}\in\mathbb{Z}[i],\,|q^{\prime}|\leq|q|\right\\}.$

However, some good approximations might be overlooked by Hurwitz’s algorithm
(see [22] for a short discussion and [30, Section 2]). In Theorem 1.1 and in
Theorem 1.2 under the assumption $\tau>2$, we are considering the
approximation function $\Psi(x)=x^{-\tau}$ satisfying $x^{2}\Psi(x)\to 0$ as
$x\to\infty$. In particular, if $q\in\mathbb{Z}[i]$ has a large absolute
value, then $|q|^{2}\Psi(|q|)<4^{-1}$ and, for a given $\zeta\in\mathbb{C}$,

$\left|\zeta-\frac{p}{q}\right|<\Psi(q)\quad\text{ implies
}\quad\left|\zeta-\frac{p}{q}\right|<\frac{1}{4|q|^{2}}$

so, by Proposition 3.2, $p/q=p_{n}/q_{n}$ for some $n\in\mathbb{N}$. The case
$\tau=2$ in Theorem 1.2 can also be studied using HCFs. Indeed, let
$\zeta\in\mathbb{C}$ be given, then $\mu(\zeta)\geq 2$ in the view of
Proposition 4.4. Whereas, it is known [12, 15] that the Hurwitz partial
quotients of $\zeta$ are bounded if and only if for some constant $c>0$ we
have

(6)
$\forall(p,q)\in\mathbb{Z}[i]\times(\mathbb{Z}[i]\setminus\\{0\\}),\quad\left|\zeta-\frac{p}{q}\right|\geq\frac{c}{|q|^{2}}.$

Hence, the irrationality exponent of such $\zeta$’s is two, that is,
$\mu(\zeta)=2$. A complex number $\zeta\in\mathbb{C}\setminus\mathbb{Q}(i)$
satisfying (6) is called badly approximable.

######  Lemma 4.1.

For every
$\zeta=[c_{0};c_{1},c_{2},\ldots]_{\mathbb{C}}\in\mathbb{C}\setminus\mathbb{Q}(i)$
and for all $n\in\mathbb{N}$, we have

$\left(\frac{2}{2+\sqrt{2}}\right)\,\frac{1}{|q_{n}|^{2}\left(|c_{n+1}|+\frac{\sqrt{2}}{2}\right)}\leq\left|\zeta-\frac{p_{n}}{q_{n}}\right|\leq\left(\frac{4}{2-\sqrt{2}}\right)\,\frac{1}{|c_{n+1}||q_{n}|^{2}}.$

###### Proof.

Take any $n\in\mathbb{N}$. Direct computations give
$|1+q_{n-1}/(c_{n+1}q_{n})|\geq 2-\sqrt{2}/2$ (see [7, Proposition 7.2]).
Then, by part (3) of Proposition 3.2,

$\displaystyle\left|\zeta-\frac{p_{n}}{q_{n}}\right|$
$\displaystyle\leq\left|\zeta-\frac{p_{n+1}}{q_{n+1}}\right|+\left|\frac{p_{n+1}}{q_{n+1}}-\frac{p_{n}}{q_{n}}\right|$
$\displaystyle<\frac{2}{|q_{n}q_{n+1}|^{2}}=\frac{2}{|c_{n+1}q_{n}^{2}|\left|1+\frac{q_{n-1}}{c_{n+1}q_{n}}\right|}<\left(\frac{4}{2-\sqrt{2}}\right)\,\frac{1}{|c_{n+1}||q_{n}|^{2}}.$

For the lower bound, we use part (2) of Proposition 3.2 to get

$\left|\zeta-\frac{p_{n}}{q_{n}}\right|=\left|\frac{[c_{n+1},c_{n+2},\ldots]_{\mathbb{C}}}{q_{n}^{2}\left(1+\frac{q_{n-1}}{q_{n}}[c_{n+1},c_{n+2},\ldots]_{\mathbb{C}}\right)}\right|.$

Hence, the strict growth $(|q_{j}|)_{j\geq 1}$ and
$[c_{n+1},c_{n+2},\ldots]_{\mathbb{C}}\in\mathfrak{F}$ gives us

$\left|1+\frac{q_{n-1}}{q_{n}}[c_{n+1},c_{n+2},\ldots]_{\mathbb{C}}\right|\leq
1+\frac{\sqrt{2}}{2}$

and, because of $[c_{n+2},c_{n+3},\ldots]_{\mathbb{C}}\in\mathfrak{F}$,

$\left|[c_{n+1},c_{n+2},\ldots]_{\mathbb{C}}\right|=\frac{1}{\left|c_{n+1}+[c_{n+2},c_{n+3},\ldots]_{\mathbb{C}}\right|}\geq\frac{1}{\left|c_{n+1}\right|+\frac{\sqrt{2}}{2}}.$

∎

######  Remark 4.2.

For RCFs, the estimates corresponding to Lemma 4.1 are an immediate
consequence of $|\alpha-p_{n}/q_{n}|<(q_{n}q_{n+1})^{-1}$ for all
$n\in\mathbb{N}$. This estimate, however, may fail for HCFs. For instance, if
$q_{1},q_{2}$ are the first two denominators of the HCF of

$\zeta=\left[-2+2i,2+2i,\frac{-1-i}{4\sqrt{2}}\right],$

then $|\zeta-p_{1}/q_{1}|\geq 1/|q_{1}q_{2}|$.

Consider $b=-A+i\in\mathbb{Z}[i]$ with $A\in\mathbb{N}$, a natural number
$v\in\mathbb{N}$, and $r\in\mathbb{Z}[i]$ such that

$\frac{r}{b^{v}}=[a_{1},a_{2},\ldots,a_{h}]_{\mathbb{C}}.$

Assume that both $\mathbf{a}=(a_{1},\ldots,a_{h})$ and
$\overleftarrow{\mathbf{a}}$ belong to $\mathsf{F}(h)$. In this framework, to
each sequence of natural numbers $\mathbf{u}=(u_{n})_{n\geq 1}$ we will
associate a complex number $\xi_{\mathbf{u}}$ by the following procedure.

First, define the sequence $(v_{n})_{n\geq 0}$ of natural numbers by

$v_{0}:=v\qquad\text{ and }\qquad\forall n\in\mathbb{N}\quad
v_{n}=u_{n}+2v_{n-1},$

so $v_{n}\geq 2^{n}$ for $n\in\mathbb{N}$. Consider the sequence of complex
numbers $(\xi^{j}_{\mathbf{u}})_{j\geq 1}$ obtained by a repeated application
of Folding Lemma:

$\xi^{1}_{\mathbf{u}}:=\frac{r}{b^{v}}+\frac{(-1)^{h}}{b^{v_{1}}}\qquad\text{
and }\qquad\forall
n\in\mathbb{N}\quad\xi^{n+1}_{\mathbf{u}}:=\xi^{n}_{\mathbf{u}}+\frac{-1}{b^{v_{n+1}}}.$

Since $|b|>1$, the following limit exists:

$\xi_{\mathbf{u}}:=\lim_{n\to\infty}\xi^{n}_{\mathbf{u}},$

For each $\mathbf{b}:=(b_{1},\ldots,b_{n})\in\mathcal{D}^{n}$,
$n\in\mathbb{N}$, write $-\mathbf{b}:=(-b_{1},\ldots,-b_{n})$. Folding Lemma
gives us the HCF of each $\xi_{\mathbf{u}}^{j}$ and of $\xi_{\mathbf{u}}$
straightaway. Indeed, given $d\in\mathcal{D}$, let
$f_{d}:\mathcal{D}^{+}\to\mathcal{D}^{+}$ be the function mapping
$\mathbf{b}=(b_{1},\ldots,b_{n})\in\mathcal{D}^{+}$ to
$f_{d}(\mathbf{b})=\mathbf{b}\,d\,\overleftarrow{-\mathbf{b}}$. Then, writing
$f_{d_{n}}\cdots f_{d_{1}}:=f_{d_{n}}\circ\cdots\circ f_{d_{1}}$ for any
$n\in\mathbb{N}$ and $d_{1},\ldots,d_{n}\in\mathcal{D}$, we have

$\xi^{1}_{\mathbf{u}}=[f_{b^{u_{1}}}(\mathbf{a})]_{\mathbb{C}},\quad\xi^{2}_{\mathbf{u}}=[f_{b^{u_{2}}}f_{b^{u_{1}}}(\mathbf{a})]_{\mathbb{C}},\quad\xi^{3}_{\mathbf{u}}=[f_{b^{u_{3}}}f_{b^{u_{2}}}f_{b^{u_{1}}}(\mathbf{a})]_{\mathbb{C}},$

and so on. Note that $|f_{d_{n}}\cdots f_{d_{1}}(\mathbf{a})|=2^{n}(h+1)-1$
for all $n\in\mathbb{N}$ and $(\xi_{\mathbf{u}}^{j})_{j\geq 1}$ is indeed
constructed via repeated applications of Folding Lemma. Finally, if we write

$\mathbf{c}:=(c_{n})_{n\geq 1}=\lim_{n\to\infty}f_{b^{u_{n}}}\cdots
f_{b^{u_{1}}}(\mathbf{a}),$

the number $\xi_{\mathbf{u}}$ admits the continued fraction expansion
$\xi_{\mathbf{u}}=[c_{1},c_{2},c_{3},\ldots]$.

######  Remark 4.3.

In general, $[c_{1},c_{2},c_{3},\ldots]$ might not be the HCF of
$\xi_{\mathbf{u}}$. Nevertheless, in this section we will have
$|c_{j}|\geq\sqrt{8}$ for every $j\in\mathbb{N}$ which, by virtue of (2) in
Proposition 3.1, implies
$\xi_{\mathbf{u}}=[c_{1},c_{2},c_{3},\ldots]_{\mathbb{C}}$.

By construction, the number $\xi_{\mathbf{u}}=[c_{1},c_{2},c_{3},\ldots]$ has
the following useful properties.

######  Proposition 4.4.

Let $m\in\mathbb{N}$ be arbitrary. Denote by $d_{m}$ the nearest Gaussian
integer to $b^{v_{k}}\xi_{\mathbf{u}}$. The following assertions hold:

  1. (1)

We have

$c_{2^{m}(h+1)}=c^{u_{m-1}}-1\quad\text{ and
}\quad\frac{p_{2^{m}(h+1)-1}}{q_{2^{m}(h+1)-1}}=\frac{d_{m}}{b^{v_{m}}}.$

  2. (2)

If $j\in\\{2^{m-1}(h+1),\ldots,2^{m}(h+1)-1\\}$, then

$\left|\xi_{\mathbf{u}}-\frac{p_{j-1}}{q_{j-1}}\right|>\left(\frac{2}{2+\sqrt{2}}\right)\,\frac{1}{|q_{j}|^{2}\left(|b|^{u_{m-1}}+\frac{\sqrt{2}}{2}\right)}.$

  3. (3)

We have

$\frac{1}{2}\,\frac{1}{|b|^{v_{m+1}}}\leq\left|\xi_{\mathbf{u}}-\frac{d_{m}}{b^{v_{m}}}\right|\leq\frac{3}{2}\,\frac{1}{|b|^{v_{m+1}}}.$

###### Proof.

  1. (1)

This follows from the definition of $\mathbf{c}$.

  2. (2)

By construction of $\mathbf{c}$, for each
$j\in\\{2^{m-1}(h+1),\ldots,2^{m}(h+1)-1\\}$ we have
$|c_{j}|\leq|b|^{u_{m-1}}$ and, by Lemma 4.1,

$\left|\xi_{\mathbf{u}}-\frac{p_{j-1}}{q_{j-1}}\right|>\left(\frac{2}{2+\sqrt{2}}\right)\,\frac{1}{|q_{j}|^{2}\left(|b|^{u_{m-1}}+\frac{\sqrt{2}}{2}\right)}.$

  3. (3)

From $4<|b|^{u_{m+2}+v_{m+1}}$ we obtain

$\left|\sum_{j=2}^{\infty}\frac{1}{b^{v_{m+j}}}\right|\leq\sum_{j=2}^{\infty}\frac{1}{|b|^{v_{m+j}}}<\frac{1}{|b|^{v_{m+2}}-1}<\frac{2}{|b|^{v_{m+2}}}<\frac{1}{2|b|^{v_{m+1}}}.$

As a consequence, we have

$\frac{1}{2|b|^{v_{m+1}}}<\left|\sum_{j=1}^{\infty}\frac{1}{b^{v_{m+j}}}\right|<\frac{3}{2|b|^{v_{m+1}}},\quad\text{
so
}\quad\frac{|b|^{v_{m}}}{2|b|^{v_{m+1}}}<\left|b^{v_{m}}\xi_{\mathbf{u}}-d_{m}\right|<\frac{3|b|^{v_{m}}}{2|b|^{v_{m+1}}}.$

∎

The proofs of Theorem 1.1 and 1.2 follow the lines of Bugeaud’s argument for
RCFs [5]. We first observe that for any
$\xi\in\mathbb{C}\setminus\mathbb{Q}(i)$ and all
$c\in\mathbb{Z}[i]\setminus\\{0\\}$, $r\in\mathbb{Q}(i)$ we have
$\mu\left(c\xi+r\right)=\mu(\xi)$.

###### Proof of Theorem 1.1.

Let $v\in\mathbb{N}$ such that $|b|^{v}\geq\sqrt{8}$, then for every
$z\in\mathbb{Z}[i]$ with $|z|\geq\sqrt{8}$ we have
$(b^{v},z,-b^{v}),(-b^{v},z,b^{v})\in\mathsf{F}(3)$ and, by Folding Lemma,

$\frac{1}{b^{v}}-\frac{1}{zb^{2v}}=[b^{v},z,-b^{v}]_{\mathbb{C}}.$

Define $u_{1}:=1$ and for $n\in\mathbb{N}$ let $u_{n+1}$ be the minimum
integer $u$ satisfying $2<|b|^{u_{n+1}}|b|^{2v_{n}}\Psi(|b|^{v_{n}})$, and
hence

(7) $\forall n\in\mathbb{N}\quad
2<|b|^{v_{n+1}}\Psi\left(|b|^{v_{n}}\right)\leq 2|b|\;\text{ and
}\;\sqrt{8}\leq b^{v_{n}}.$

From statement (3) of Proposition 4.4, we conclude that

$\frac{\Psi\left(|b|^{v_{k}}\right)}{4|b|}\leq\left|\xi_{\mathbf{u}}-\frac{d_{k}}{b^{v_{k}}}\right|<\Psi\left(|b|^{v_{k}}\right).$

The sequence $\mathbf{u}$ is strictly increasing, because $(v_{n})_{n\geq 1}$
is strictly increasing and $x\mapsto x^{2}\Psi(x)$ is strictly decreasing. If
$j\in\mathbb{N}$ and $m\in\mathbb{N}$ is such that $2^{m-1}(h+1)\leq j$, then
$|b|^{v_{m-1}}\leq|q_{j}|$. As a consequence, in the view of Proposition 4.4,
for any $\delta>0$ and any large $j\in\mathbb{N}$ we have

$\displaystyle\left(|b|^{u_{m-1}}+\frac{\sqrt{2}}{2}\right)|q_{j}|^{2}\Psi(|q_{j}|)$
$\displaystyle\leq(|b|^{u_{m-1}}+1)|q_{j}|^{2}\Psi(|q_{j}|)$
$\displaystyle\leq(|b|^{u_{m-1}}+1)|b|^{2v_{m-1}}\Psi\left(|b|^{v_{m-1}}\right)$
$\displaystyle\leq 2(|b|^{u_{m-1}}+1)|b|^{1-u_{m}}$
$\displaystyle\leq\frac{2}{\sqrt{2}}(|b|+\delta).$

In the last step we have used $|b|>\sqrt{2}$ and $|b|^{-u_{m}}\to 0$ when
$m\to\infty$. In particular, when $\delta>0$ satisfies $(|b|+2\delta)^{-1}>c$,
the third part of Proposition 4.4 tells us that

$\left|\xi_{\mathbf{u}}-\frac{d_{m}}{b^{u_{m}}}\right|>\frac{\Psi(|q_{j}|)}{|b|+2\delta}>c\Psi(|q_{j}|).$

We conclude that
$\xi_{\mathbf{u}}\in\mathcal{K}(\Psi)\setminus\mathcal{K}(c\Psi)$. In order to
get uncountably many numbers when $A\geq 2$, consider sequences
$\mathbf{w}=(w_{n})_{n\geq 1}$ determined satisfying $w_{1}=1$,
$w_{2n+1}=u_{n}$, and $w_{2n}\in\\{1,2\\}$ for $n\in\mathbb{N}$ and apply the
above construction. ∎

###### Proof of Theorem 1.2.

Take $\lambda>0$ and $\tau\geq 2$. The estimate
$\mu(\xi_{\lambda,\tau})\geq\tau$ can be obtained approximating
$\xi_{\lambda,\tau}$ by the partial sums of the series defining it. In order
to show $\mu(\xi_{\lambda,\tau})\leq\tau$, define
$v_{0}:=\lfloor\lambda\tau^{3+n_{0}(\tau,\lambda)}\rfloor$ and let
$\mathbf{u}=(u_{n})_{n\geq 1}$ be given by

$\forall n\in\mathbb{N}\quad
u_{n}:=\left\lfloor\lambda\tau^{n+3+n_{0}(\tau,\lambda)}\right\rfloor-2\left\lfloor\lambda\tau^{n+2+n_{0}(\tau,\lambda)}\right\rfloor.$

It can be readily checked that

$\forall n\in\mathbb{N}\quad
v_{n}=\left\lfloor\lambda\tau^{n+3+n_{0}(\tau,\lambda)}\right\rfloor.$

Take any $j\in\mathbb{N}$ and pick $m\in\mathbb{N}$ such that
$2^{m}(h+1)-1\leq j<2^{m+1}(h+1)-1$, then

$|q_{j-1}|\leq|b|^{v_{m+1}}=|b|^{\lfloor\lambda\tau^{4+m+n_{0}(\lambda,\tau)}\rfloor}\leq|b|^{\lambda\tau^{4+m+n_{0}(\lambda,\tau)}},$

so

$|q_{j-1}|^{\tau-2}\leq b^{(\tau-2)(\lambda\tau^{4+m+n_{0}(\lambda,\tau)})}.$

By definition of $u_{m-1}$, we have

$|b|^{u_{m-1}}\leq|b|\frac{|b|^{\lambda\tau^{2+m+n_{0}(\tau,\lambda)}}}{|b|^{2\lambda\tau^{m+1+n_{0}(\tau,\lambda))}}}=|b|\,|b|^{(\tau-2)\lambda^{2+m+n_{0}(\tau,\lambda)}}\leq|b|\,|b|^{(\tau-2)\lambda^{4+m+n_{0}(\tau,\lambda)}}.$

in the view of Lemma 4.1, for some constants depending on $b$ (implied by
$\gg_{b}$),

$\left|\xi_{\lambda,\tau}-\frac{p_{j-1}}{q_{j-1}}\right|\gg_{b}\frac{1}{|q_{j-1}|^{2}|b|^{u_{m-1}}}\gg_{b}\frac{1}{|q_{j-1}|^{\tau}},$

therefore $\mu(\xi_{\lambda,\tau})\leq\tau$.

A similar argument holds when $\tau=2$, but we need to be careful. In this
case, we have

$\forall k\in\mathbb{N}\quad\varepsilon_{k}:=\lfloor\lambda
2^{k+1}\rfloor-2\lfloor\lambda 2^{k}\rfloor\in\\{0,1\\}.$

Folding Lemma gives a continued fraction of the form
$[a_{1},\ldots,a_{n},1,-a_{n},-a_{n-1},\ldots,a_{1}]$, which is not a HCF.
However, using the well-known identity

(8)
$x_{1}+\cfrac{1}{1+\cfrac{1}{x_{2}+x_{3}}}=x_{1}+1+\cfrac{1}{-(x_{2}+1)-x_{3}}$

(see, for example, [18, p. 258]), we obtain the HCF

(9) $[a_{1},\ldots,a_{n-1},a_{n}+1,a_{n}-1,a_{n-1},\ldots,a_{1}]_{\mathbb{C}}$

(see Proposition 3.1). Moreover, $\mu(\xi_{2,\tau})=2$ because the partial
quotients are bounded. ∎

##  5\. Zaremba conjecture for powers of small numbers

First, let us introduce some useful notation. For
$z\in\mathbb{Q}(i)\cap\mathfrak{F}$ with a HCF
$z=[a_{1}(z),\ldots,a_{n}(z)]_{\mathbb{C}}$, we define

$K_{\mathbb{C}}(z)=\max(|a_{1}(z)|,\ldots,|a_{n}(z)|)$

and $a_{last}=a_{last}(z)$ to be the last partial quotient in HCF of $z$ (in
this case $a_{last}(z)=a_{n}(z)$).

In the previous section in proofs of Theorem 1.1 and Theorem 1.2 we have
considered denominators of the form $b^{k}$, where $b=-A\pm i$ for some
$A,k\in\mathbb{N}$. Using Folding Lemma we can show that if we fix $A$ to be a
small integer, we can always find HCF with bounded partial quotients. For
$A=3$ we have the following theorem.

######  Theorem 5.1.

If $m=(-3\pm i)^{k},k\geq 1$, then there exists a Gaussian integer $a$ with
$\gcd(a,m)=1$, $a/m\in\mathfrak{F}$, such that $K_{\mathbb{C}}(a/m)\leq
3\sqrt{2}$.

###### Proof.

For the base of inductive procedure consider the following HCFs.

$\displaystyle\frac{1}{-3\pm i}=[-3\pm i]_{\mathbb{C}},\quad\frac{2\pm
3i}{(-3\pm i)^{2}}=[\mp 3i,-2\mp 3i]_{\mathbb{C}}.$

Then for even powers of $-3\pm i$ we apply Lemma 2.2 with $x=1$, so the
resulting fraction will be of the form

$[a_{1},\ldots,a_{last-1},a_{last}+1,a_{last}-1,a_{last-1},\ldots,a_{1}]_{\mathbb{C}}.$

Note that we will only change the real part of the last partial quotient by
$\pm 1$ on each step of the iteration and as one can see, it will not impose
any non-trivial restrictions on the partial quotients as for every $i$ we have
$|a_{i}|\geq\sqrt{8}.$

For odd powers of $-3\pm i$, we apply Lemma 2.2 with $x=(-3\pm i)$, so the
resulting fraction will be of the form

$[a_{1},\ldots,a_{last},-3\pm i,-a_{last},\ldots,-a_{1}]_{\mathbb{C}}$

and once again for every partial quotient we have $|a_{i}|\geq\sqrt{8}$, so
there are no non-trivial restrictions on the partial quotients.

Note that for both odd and even powers, the maximum absolute value of partial
quotients will be not greater than $3\sqrt{2}.$ Continuing the procedure, we
will generate HCFs for every power of $-3\pm i$. ∎

We also have a similar statement for $b=-2\pm i$.

######  Theorem 5.2.

If $m=(-2\pm i)^{k},k\geq 1$, then there exists a Gaussian integer $a$ with
$\gcd(a,m)=1$, $a/m\in\mathfrak{F}$, such that $K_{\mathbb{C}}(a/m)\leq
3\sqrt{2}$.

###### Proof.

For the base of inductive procedure consider the following HCFs.

$\displaystyle\frac{1}{-2\pm i}=[-2\pm i]_{\mathbb{C}},\quad\frac{\pm
2i}{(-2\pm i)^{2}}=[-2\mp i,\pm 2i]_{\mathbb{C}},\quad\frac{2\mp 4i}{(-2\pm
i)^{3}}=[-2\pm i,-2\pm i,2\mp i]_{\mathbb{C}},$ $\displaystyle\frac{5\mp
6i}{(-2\pm i)^{4}}=[2\mp 3i,-1\mp 2i,-3\pm i]_{\mathbb{C}},\quad\frac{13\mp
11i}{(-2\pm i)^{5}}=[\pm 3i,1\mp 3i,2\mp i,-2\mp 2i]_{\mathbb{C}},$
$\displaystyle\frac{27\mp 38i}{(-2\pm i)^{6}}=[-1\mp 3i,1\mp 2i,1\mp 2i,-3\mp
2i,2\mp 3i]_{\mathbb{C}},$ $\displaystyle\frac{\mp 97i}{(-2\pm i)^{7}}=[\pm
3i,3\pm 3i,-2\mp 2i,\pm 3i,1\mp 3i]_{\mathbb{C}}.$

Note that in all fractions $p_{n}/(-2\pm i)^{n},\,n\geq 4$, all partial
quotients satisfy

(10) $\sqrt{5}\leq\left|a_{i}\left(\frac{p_{n}}{(-2\pm
i)^{n}}\right)\right|\leq 3\sqrt{2}$

and that the first and the last partial quotients satisfy

(11) $\sqrt{5}\leq\left|a_{i}\left(\frac{p_{n}}{(-2\pm i)^{n}}\right)\pm
1\right|\leq 3\sqrt{2}\quad\text{for }i\in\\{1,\rm last\\}.$

Note that if $a_{i}>\sqrt{5}$, then there are no non-trivial restrictions on
$a_{i+1}$. When $a_{i}=\sqrt{5}$, as per comments after Table 1 we need to be
careful in regards to whether the resulting fraction is a valid HCF. We will
check the validity in Section 6.

For even powers of $(-2\pm i)^{2k},\,k\geq 4$ we apply Lemma 2.2 with $x=1$
and $q_{n}=(-2\pm i)^{k}$, where by induction we already have a suitable HCF
for $q_{n}=(-2\pm i)^{k}$. The resulting fraction will be of the form

$\frac{p^{\prime}}{(-2\pm
i)^{2k}}=[a_{1},\ldots,a_{last-1},a_{last}+1,a_{last}-1,a_{last-1},\ldots,a_{1}]_{\mathbb{C}}.$

It is easy to see that properties (10) and (11) are preserved under the
application of Lemma 2.2 for this fraction, hence we can continue the
inductive procedure.

For odd powers of $(-2\pm i)^{2k+1},\,k\geq 4$, we apply Lemma 2.2 with
$x=(-2\pm i)$, so the resulting fraction will be of the form

$\frac{p^{\prime}}{(-2\pm i)^{2k+1}}=[a_{1},\ldots,a_{last},-2\pm
i,-a_{last},\ldots,-a_{1}]_{\mathbb{C}}$

Once again, properties (10) and (11) are preserved. Continuing the procedure,
we will generate continued fractions for every power of $-2\pm i$ with partial
quotients bounded by $3\sqrt{2}.$ The final step is to show that the resulting
fractions provided by Folding Lemma are indeed valid HCFs. As the proof of
this fact is very technical, we provide details in a separate Section 6. ∎

Due to the statements (3) and (4) of Remark 3.3, we can deal with HCFs of real
rational numbers, too.

######  Theorem 5.3.

If $m=2^{k},k\geq 1$, then there exists an odd integer $1\leq a<m$ such that
$K_{\mathbb{C}}(a/m)\leq~{}8$.

###### Proof.

First, note that

$\displaystyle-\frac{1}{2^{1}}=[-2]_{\mathbb{C}},\quad\frac{1}{2^{2}}=[4]_{\mathbb{C}},\quad\frac{3}{2^{3}}=[3,-3]_{\mathbb{C}},\quad\frac{5}{2^{4}}=[3,5]_{\mathbb{C}},\quad\frac{9}{2^{5}}=[4,-2,-4]_{\mathbb{C}},\quad\frac{17}{2^{6}}=[4,-4,-4]_{\mathbb{C}},$
$\displaystyle\frac{19}{2^{7}}=[7,-4,5]_{\mathbb{C}},\quad\frac{79}{2^{8}}=[3,4,6,3]_{\mathbb{C}},\quad\frac{71}{2^{9}}=[7,5,-4,-4]_{\mathbb{C}},\quad\frac{165}{2^{10}}=[6,5,-7,5]_{\mathbb{C}},$
$\displaystyle\frac{423}{2^{11}}=[5,-6,-3,-5,-4]_{\mathbb{C}},\quad\frac{557}{2^{12}}=[7,3,-6,5,-7]_{\mathbb{C}},\quad\frac{1453}{2^{13}}=[6,-3,4,5,-5,-5].$

Note that all rational numbers $r/2^{k},k\geq 6$ listed above satisfy the
conditions of the statement (4) of Remark 3.3, and so these HCFs are
reversible; we also have $3\leq|a_{1}(r/2^{k})|,|a_{last}(r/2^{k})|\leq 7$.

To prove the statement of this theorem, it is remaining to introduce an
inductive procedure, which will generate valid HCF expansions for the
fractions $g/2^{N}$ for some $g<2^{N-1}$ and all $N\geq 14.$

We are using the following inductive procedure: for every odd integer
$N=2k+3\geq 15$ we will apply Lemma 2.2 with $x=8$ and $q_{n}=2^{k}$. We get
that $k\geq 6$ and by the induction hypothesis there exists a reduced fraction
$r/2^{k}$ with $K_{\mathbb{C}}(r/2^{k})\leq 8$ and
$3\leq|a_{1}(r/2^{k})|,|a_{last}(r/2^{k})|\leq 7$, so we also let $p_{n}=r$.
Then the right-hand side in (4) is a fraction with denominator
$xq_{n}^{2}=2^{3}\cdot 2^{2k}=2^{N},$ and its continued fraction expansion is

(12)
$\frac{r^{\prime}}{2^{N}}=[a_{1},\ldots,a_{last},8,-a_{last},\ldots,-a_{1}]_{\mathbb{C}}.$

Note that this is indeed a valid HCF, because, as we said previously,
$[a_{1},\ldots,a_{last}]_{\mathbb{C}}$ is reversible,
$3\leq|a_{1}(r/2^{k})|,|a_{last}(r/2^{k})|\leq 7$ and we added new partial
quotients equal to $8$ in the middle, which does not impose any restrictions
as per Remark 3.3. Notice that the continued fraction (12) preserves the
property $3\leq|a_{1}(r^{\prime}/2^{N})|,|a_{last}(r^{\prime}/2^{N})|\leq 7$
and $K_{\mathbb{C}}(r^{\prime}/2^{N})\leq 8$, so we indeed can continue our
inductive procedure.

For every even integer $N=2k+2\geq 14$, we will apply Lemma 2.2 with $x=4$ and
$q_{n}=2^{k}$. Note that in this case we also have $k\geq 6$ and by induction,
there exists a reduced fraction $r/2^{k}$ with $K_{\mathbb{C}}(r/2^{k})\leq 8$
and $3\leq|a_{1}(r/2^{k})|,|a_{last}(r/2^{k})|\leq 7$, so we also let
$p_{n}=r$. This means that the application of Folding Lemma will generate a
valid HCF expansion. The right-hand side in (4) is a fraction with denominator
$xq_{n}^{2}=2^{2}\cdot 2^{2k}=2^{N},$ and its continued fraction expansion is

$\frac{r^{\prime}}{2^{N}}=[a_{1},\ldots,a_{last},4,-a_{last},\ldots,-a_{1}]_{\mathbb{C}},$

so this continued fraction preserves the property
$3\leq|a_{1}(r^{\prime}/2^{N})|,|a_{last}(r^{\prime}/2^{N})|\leq 7$ and also
$K_{\mathbb{C}}(r^{\prime}/2^{N})\leq 8$, so once again we can continue the
procedure. ∎

######  Remark 5.4.

This is similar to the idea of Niederreiter [27] for the case of RCFs of real
numbers, however due to statement (1) of Remark 3.3, in that case, one does
not need to worry about reversibility as there are no non-trivial restrictions
on partial quotients in RCFs. We also note that Zaremba’s conjecture for
powers of $2$ in the case of RCFs can be reformulated and proved in terms of
Minkowski question mark function $?(x)$, see [10].

######  Remark 5.5.

Note that we cannot let $x=2$ or $x=-2$ in the proof of Theorem 5.3, because
by Folding Lemma we would have $[\ldots,a_{last},\pm 2,-a_{last},\ldots]$ in
the middle, which is not reversible. This is due to the fact that there are
numbers of different signs around $\pm 2$ and hence by statement (3) of Remark
3.3 (or by Table 1) it is not reversible.

Similarly, we provide a result for powers of $3$.

######  Theorem 5.6.

If $m=3^{k},k\geq 1$, then there exists an integer $1\leq a<m$ with
$\gcd(a,3)=1$, such that $K_{\mathbb{C}}(a/m)\leq 8$.

###### Proof.

First, we see that

$\displaystyle\frac{1}{3^{1}}=[3]_{\mathbb{C}},\quad\frac{4}{3^{2}}=[2,4]_{\mathbb{C}},\quad\frac{10}{3^{3}}=[3,-3,-3]_{\mathbb{C}},\quad\frac{19}{3^{4}}=[4,4,-5]_{\mathbb{C}},$
$\displaystyle\frac{50}{3^{5}}=[5,-7,-7]_{\mathbb{C}},\quad\frac{107}{3^{6}}=[7,-5,-3,7]_{\mathbb{C}},\quad\frac{323}{3^{7}}=[7,-4,-3,4,-7]_{\mathbb{C}}.$

Note that all fractions with denominators $3^{k}$ for $k=4,5,6,7$ listed above
satisfy the condition of statement (4) of Remark 3.3 and so the reversed
continued fraction is also a valid HCF.

Once again, we will use two inductive procedures: one for odd powers and one
for even powers.

For $N=2k\geq 8$ we will apply Lemma 2.2 with $x=1$ and $q_{n}=3^{k}$. Note
that in this case $k\geq 4$ and by the induction hypothesis there exists a
reduced fraction $r/3^{k}$ with $K_{\mathbb{C}}(r/3^{k})\leq 8$ and
$4\leq|a_{1}(r/3^{k})|,|a_{last}(r/3^{k})|\leq 7$.

So applying Lemma 2.2, we get that the right-hand side in (4) is a fraction
with denominator $xq_{n}^{2}=1\cdot 3^{2k}=3^{N}$, and by the identity (8) its
Hurwitz continued fractions expansion is

(13)
$\frac{r^{\prime}}{3^{N}}=[a_{1},\ldots,a_{last-1},a_{last}+1,a_{last}-1,a_{last-1},\ldots,a_{1}]_{\mathbb{C}}.$

We note that
$a_{1}(r^{\prime}/3^{N})=a_{last}(r^{\prime}/3^{N})=a_{1}(r/3^{k})$ and so
$4\leq|a_{1}(r^{\prime}/3^{N})|,|a_{last}(r^{\prime}/3^{N})|\leq 7$, so this
property of $a_{1}(z)$ and $a_{last}(z)$ preserves under this procedure.
Because of the statement (4) in Remark 3.3, we see that this continued
fraction is also reversible as a HCF. Also, note that from the explicit form
of the continued fraction (13), it is clear that
$K_{\mathbb{C}}(r^{\prime}/3^{N})=\max(K_{\mathbb{C}}(r/3^{k}),|a_{last}(r/3^{k})|+1)\leq
8$.

For $N=2k+1\geq 9$ we will apply Lemma 2.2 with $x=3$ and $q_{n}=3^{k}$. Note
that in this case $k\geq 4$ and by the induction hypothesis there exists a
reduced fraction $r/3^{k}$ with $K_{\mathbb{C}}(r/3^{k})\leq 8$ and
$4\leq|a_{1}(r/3^{k})|,|a_{last}(r/3^{k})|\leq 7$.

So applying Lemma 2.2, we get that the right-hand side in (4) is a fraction
with denominator $xq_{n}^{2}=3\cdot 3^{2k}=3^{N}$, and its Hurwitz continued
fractions expansion is

(14)
$\frac{r^{\prime}}{3^{N}}=[a_{1},\ldots,a_{last},3,-a_{last},\ldots,-a_{1}]_{\mathbb{C}}.$

We note that
$a_{1}(r^{\prime}/3^{N})=-a_{last}(r^{\prime}/3^{N})=a_{1}(r/3^{k})$ and so
$4\leq|a_{1}(r^{\prime}/3^{N})|,|a_{last}(r^{\prime}/3^{N})|\leq 7$, so this
property of $a_{1}(z)$ and $a_{last}(z)$ preserves under this procedure.
Because of the statement (4) in Remark 3.3, we see that this continued
fraction is also reversible as a HCF. Also, note that from the explicit form
of the continued fraction (14), it is clear that
$K_{\mathbb{C}}(r^{\prime}/3^{N})=K_{\mathbb{C}}(r/3^{k})\leq 8$.

Hence, continuing this procedure, we can get valid HCF expansions for
denominators of the form $3^{k},k\geq 1$ with $K_{\mathbb{C}}(r/3^{k})\leq 8$.
∎

For powers of $5$ we have a slightly better statement.

######  Theorem 5.7.

If $m=5^{k},k\geq 1$, then there exists an integer $1\leq a<m$ with
$\gcd(a,5)=1$, such that $K_{\mathbb{C}}(a/m)\leq 7$.

###### Proof.

We start with seed fractions

$\frac{1}{5}=[5]_{\mathbb{C}},\quad\frac{6}{25}=[4,6]_{\mathbb{C}}$

and then proceed as in Theorem 5.6 with $x=5$ for odd powers and $x=1$ for
even powers. ∎

##  6\. Verification of the validity of the sequences for powers of $(-2+i)$

We focus on $(-2+i)^{4}$, the other powers are handled similarly. In Section
3, we said that for a given valid sequence $\mathbf{a}=(a_{1},\ldots,a_{n})$,
$n\in\mathbb{N}$, and any $b\in\mathcal{D}$ the validity of $\mathbf{a}b$ may
depend on the entire sequence $\mathbf{a}$. Nevertheless, if
$\mathfrak{F}^{\circ}_{j}(a_{1},\ldots,a_{j+1})=\mathfrak{F}^{\circ}$ for some
$j\in\\{1,\ldots,n-1\\}$, the values of $b$ making $\mathbf{a}b$ valid are
independent of $(a_{1},\ldots,a_{j})$. This observation—a trivial corollary of
part (1) of Proposition 6.1 below—lies in the heart of our proof. The first
point in Proposition 6.1 follows directly from the definition of cylinders and
prototype sets (cfr. [13, Lemma 2.3]). Furthermore, since the functions
$\tau_{b}$, for $b\in\mathcal{D}$, and $\iota$ are homeomorphisms, we can
replace $\mathfrak{F}$ and $\mathcal{C}$ with $\mathfrak{F}^{\circ}$ and
$\mathcal{C}^{\circ}$, respectively. The second point is contained in the
proof of [7, Proposition 4.5].

######  Proposition 6.1.

Take $m\in\mathbb{N}$ and ${\mathbf{x}}=(x_{1},\ldots,x_{m})\in\Omega(m)$.

  1. (1)

We have
$\mathfrak{F}_{m}({\mathbf{x}})=\tau_{-x_{m}}\iota(\mathfrak{F}_{m-1}(x_{1},\ldots,x_{m-1})\cap\mathcal{C}_{1}(x_{m}))$.

  2. (2)

If $\mathfrak{F}^{\circ}_{m}({\mathbf{x}})=\mathfrak{F}^{\circ}$, then
$\mathfrak{F}^{\circ}_{m}(\overleftarrow{-\mathbf{x}})=\mathfrak{F}^{\circ}_{m}(\overline{x_{1}},\ldots,\overline{x_{m}})=\mathfrak{F}^{\circ}$.

######  Remark 6.2.

Given $a,b\in\mathcal{D}$, we may compute $\mathfrak{F}^{\circ}_{2}(a,c)$
using part (1) of Proposition 6.1 and
$\iota(\mathcal{C}^{\circ}_{1}(b))=\iota(\mathfrak{F})\cap\tau_{b}(\mathfrak{F})$.

For each ${\mathbf{x}}=(x_{1},\ldots,x_{last})\in\mathcal{D}^{+}$, let
$|\mathbf{x}|$ be the length of ${\mathbf{x}}$, and denote

$\displaystyle{\mathbf{x}}^{+}:=(x_{1},\ldots,x_{last-1},x_{last}+1),$
$\displaystyle{\mathbf{x}}_{-}:=(x_{1}-1,x_{2}\ldots,x_{last}),$
$\displaystyle\overleftarrow{\mathbf{x}}_{-}:=\left(\overleftarrow{\mathbf{x}}\right)_{-}.$

Consider $d=-2+i$, $f(\mathbf{x}):={f_{d}(\mathbf{x})}$ and
$g(\mathbf{x}):={\mathbf{x}}^{+}\overleftarrow{\mathbf{x}}_{-}$. For
$h_{1},\ldots,h_{n}\in\\{f,g\\}$, we write $h_{n}\cdots
h_{1}:=h_{n}\circ\cdots\circ h_{1}$. Let ${\mathbf{a}}=(a_{1},a_{2},a_{3})$ be
the partial quotients of $(5-6i)/(-2+i)^{4}$; that is

${\mathbf{a}}:=(2-3i,-1-2i,-3+i).$

From Table 1 we get
$\mathfrak{F}^{\circ}_{3}(\overleftarrow{\mathbf{a}})=\mathfrak{F}^{\circ}$
and we can easily check that
$\mathfrak{F}^{\circ}_{3}(\overleftarrow{\mathbf{a}})=\mathfrak{F}^{\circ}$.
Consider ${\mathbf{c}}=(c_{1},\ldots,c_{7})$ given by

${\mathbf{c}}:=f({\mathbf{a}})=(2-3i,-1-2i,-3+i,-2+i,3-i,1+2i,-2+3i),$

From $\mathfrak{F}^{\circ}_{3}(2-3i,-1-2i,-3+i)=\mathfrak{F}^{\circ}$,
$\mathfrak{F}^{\circ}_{2}(-2+i,3-i)=\mathfrak{F}^{\circ}$, and
$\mathfrak{F}^{\circ}_{2}(1+2i,-2+3i)=\mathfrak{F}^{\circ}$ we obtain
$\mathfrak{F}^{\circ}_{|f({\mathbf{a}})|}({f({\mathbf{a}})})=\mathfrak{F}^{\circ}$.
Indeed, using part (1) of Proposition 6.1, we arrive at

$\displaystyle\mathfrak{F}^{\circ}_{4}(c_{1},c_{2},c_{3},c_{4})$
$\displaystyle=\tau_{-c_{4}}\iota\left(\mathfrak{F}^{\circ}_{3}(c_{1},c_{2},c_{3})\cap\mathcal{C}^{\circ}_{1}(c_{4})\right)$
$\displaystyle=\tau_{-c_{4}}\iota\left(\mathfrak{F}^{\circ}_{3}(2-3i,-1-2i,-3+i)\cap\mathcal{C}^{\circ}_{1}(-2+i)\right)=\mathfrak{F}^{\circ}_{1}(-2+i),$

hence

$\displaystyle\mathfrak{F}^{\circ}_{5}(c_{1},c_{2},c_{3},c_{4},c_{5})$
$\displaystyle=\tau_{-c_{5}}\iota\left(\mathfrak{F}^{\circ}_{4}(c_{1},c_{2},c_{3},c_{4})\cap\mathcal{C}^{\circ}_{1}(c_{5})\right)$
$\displaystyle=\tau_{-c_{5}}\iota\left(\mathfrak{F}^{\circ}_{1}(-2+i)\cap\mathcal{C}^{\circ}_{1}(3-i)\right)=\mathfrak{F}^{\circ}_{2}(-2+i,3-i)=\mathfrak{F}^{\circ}$

and

$\displaystyle\mathfrak{F}^{\circ}_{7}(\mathbf{c})$
$\displaystyle=\tau_{-c_{7}}\iota\left(\mathfrak{F}^{\circ}_{6}(c_{1},\ldots,c_{6})\cap\mathcal{C}^{\circ}_{1}(c_{7})\right)$
$\displaystyle=\tau_{-c_{7}}\iota\left(\tau_{-c_{6}}\iota\left(\mathfrak{F}^{\circ}_{5}(c_{1},\ldots,c_{5})\cap\mathcal{C}^{\circ}_{1}(c_{6})\right)\cap\mathcal{C}^{\circ}_{1}(c_{7})\right)$
$\displaystyle=\tau_{-c_{7}}\iota\left(\mathfrak{F}^{\circ}_{1}(c_{6})\cap\mathcal{C}^{\circ}_{1}(c_{7})\right)=\mathfrak{F}_{2}(c_{6},c_{7})=\mathfrak{F}^{\circ}_{2}(1+2i,-2+3i)=\mathfrak{F}^{\circ}.$

Similarly,
$\mathfrak{F}^{\circ}_{7}\left(\overleftarrow{\mathbf{c}}\right)=\mathfrak{F}^{\circ}$
is implied by

$\mathfrak{F}^{\circ}_{3}(-3+i,-1-2i,2-3i)=\mathfrak{F}^{\circ},\quad\mathfrak{F}^{\circ}_{2}(-2+i,-3+i)=\mathfrak{F}^{\circ},\quad\mathfrak{F}^{\circ}_{2}(-1-2i,2-3i)=\mathfrak{F}^{\circ}.$

We may show
$\mathfrak{F}^{\circ}_{6}({g(\mathbf{a})})=\mathfrak{F}^{\circ}_{6}(2-3i,-1-2i,-2+i,-4+i,-1-2i,2-3i)=\mathfrak{F}^{\circ}$
using

$\mathfrak{F}^{\circ}_{2}(2-3i,-1-2i)=\mathfrak{F}^{\circ}(-1-2i),\quad\mathfrak{F}^{\circ}_{2}(-1-2i,-2+i)=\mathfrak{F}^{\circ}(-2+i),$
$\mathfrak{F}^{\circ}_{2}(-2+i,-4+i)=\mathfrak{F}^{\circ},\quad\mathfrak{F}^{\circ}_{2}(-1-2i,2-3i)=\mathfrak{F}^{\circ}.$

Finally,
$\mathfrak{F}^{\circ}_{6}(\overleftarrow{g(\mathbf{a})})=\mathfrak{F}^{\circ}$
is a consequence of

$\mathfrak{F}^{\circ}_{2}(2-3i,-1-2i)=\mathfrak{F}^{\circ}_{1}(-1-2i),\quad\mathfrak{F}^{\circ}_{2}(-1-2i,-4+i)=\mathfrak{F}^{\circ},\quad$
$\mathfrak{F}^{\circ}_{2}(-2+i,-1-2i)=\mathfrak{F}^{\circ}_{1}(-1-2i),\quad\mathfrak{F}^{\circ}_{2}(-1-2i,2-3i)=\mathfrak{F}^{\circ}.$

Let $N\in\mathbb{N}_{\geq 2}$. For $j\in\\{1,\ldots,N\\}$ and
$\mathbf{h}=(h_{1},\ldots,h_{j})\in\\{f,g\\}^{j}$, put
$\mathbf{h}({\mathbf{a}}):=h_{j}\cdots h_{1}(\mathbf{a})$ and
$n(\mathbf{h})=|\mathbf{h}({\mathbf{a}})|$. Assume that

(15) $\forall
j\in\\{1,\ldots,N\\}\quad\forall\mathbf{h}\in\\{f,g\\}^{j}\quad\mathfrak{F}^{\circ}_{n(\mathbf{h})}\left(\mathbf{h}({\mathbf{a}})\right)=\mathfrak{F}^{\circ}\quad\text{
and
}\quad\mathfrak{F}^{\circ}_{n(\mathbf{h})}\left(\overleftarrow{-\mathbf{h}(\mathbf{a})}\right)=\mathfrak{F}^{\circ}.$

Take any $\mathbf{h}=(h_{1},\ldots,h_{N})\in\\{f,g\\}^{N}$ and
$h\in\\{f,g\\}$. Let us show that (15) will also hold for $N+1$. Note that the
equality for $\overleftarrow{\mathbf{h}(\mathbf{a})}$ is equivalent to the
equality for $\overleftarrow{-\mathbf{h}({\mathbf{a}})}$ by part (2) of
Proposition 6.1.

For the rest of the paper, we write ${\mathbf{b}}=h_{N-1}\cdots
h_{1}({\mathbf{a}})$. We consider four cases.

  1. (1)

Case $(h_{N},h)=(f,f)$. Consider
${\mathbf{c}}:={ff(\mathbf{b})}=\mathbf{b}\,d\,\overleftarrow{-\mathbf{b}}\,d\,\mathbf{b}\,(-d)\,\overleftarrow{-\mathbf{b}}$.
By (15), we have

$\mathfrak{F}^{\circ}_{n(\mathbf{h})}\left(f(\mathbf{b})\right)=\mathfrak{F}^{\circ}\quad\text{
and
}\quad\mathfrak{F}^{\circ}_{n(\mathbf{h})}\left(\overleftarrow{-f(\mathbf{b})}\right)=\mathfrak{F}^{\circ}.$

The first term of ${\mathbf{b}}$ is $a_{1}$ and, since
$\mathfrak{F}^{\circ}_{2}(d,a_{1})=\mathfrak{F}^{\circ}_{2}(-2+i,2-3i)=\mathfrak{F}^{\circ}$,
we conclude from statement (1) of Proposition 6.1. that
$\mathfrak{F}_{n(\mathbf{h}f)}({\mathbf{h}f(\mathbf{a})})=\mathfrak{F}^{\circ}$.
In order to prove
$\mathfrak{F}^{\circ}_{n(\mathbf{h}f)}(\overleftarrow{-\mathbf{c}})=\mathfrak{F}^{\circ}$,
we note that
$\overleftarrow{-\mathbf{c}}={\mathbf{b}}\,d\,\overleftarrow{-\mathbf{b}}\,(-d)\,{\mathbf{b}}\,(-d)\,\overleftarrow{-\mathbf{b}}$,
that
$\mathfrak{F}^{\circ}_{2}(-d,a_{1})=\mathfrak{F}^{\circ}_{2}(2-i,2-3i)=\mathfrak{F}^{\circ}$,
and then argue as we did for $\mathbf{c}$.

  2. (2)

Case $(h_{N},h)=(g,f)$. Consider
${\mathbf{c}}:=fg(\mathbf{b})=g(\mathbf{b})\,d\,\overleftarrow{-g(\mathbf{b})}$.
In order get
$\mathfrak{F}^{\circ}_{n(\mathbf{h}f)}(\mathbf{h}f(\mathbf{a}))=\mathfrak{F}^{\circ}$,
first observe that

(16)
$\mathfrak{F}^{\circ}_{n(\mathbf{h})}(g(\mathbf{b}))=\mathfrak{F}^{\circ},\quad\mathfrak{F}^{\circ}_{n(\mathbf{h})}\left(\overleftarrow{-g(\mathbf{b})}\right)=\mathfrak{F}^{\circ},$

by (15). Since the last letter of $\overleftarrow{\mathbf{b}}_{-}$ is $a_{1}$,
the first letter of
$\overleftarrow{({\mathbf{b}}^{+}\overleftarrow{\mathbf{b}}_{-})}_{-}$ is
$-a_{1}$ and the desired equality follows from (16) and
$\mathfrak{F}^{\circ}_{2}(d,-a_{1})=\mathfrak{F}^{\circ}_{2}(-2+i,-2+3i)=\mathfrak{F}^{\circ}$.
The same observations and
$\mathfrak{F}^{\circ}_{2}(-d,-a_{1})=\mathfrak{F}^{\circ}_{2}(2-i,-2+3i)=\mathfrak{F}^{\circ}$
imply
$\mathfrak{F}^{\circ}_{n(\mathbf{h}f)}(\overleftarrow{-\mathbf{c}})=\mathfrak{F}^{\circ}$.

  3. (3)

Case $(h_{N},h)=(f,g)$. Write $\mathbf{c}:=gf(\mathbf{b})$, so

$\mathbf{c}=f(\mathbf{b})^{+}\,\overleftarrow{f(\mathbf{b})}_{-}.$

Therefore, in order to show
$\mathfrak{F}^{\circ}(\mathbf{c})=\mathfrak{F}^{\circ}$ it suffices to verify

(17)
$\mathfrak{F}^{\circ}_{n(\mathbf{h})}(f(\mathbf{b})^{+})=\mathfrak{F}^{\circ}\quad\text{
and
}\quad\mathfrak{F}^{\circ}_{n(\mathbf{h})}(\overleftarrow{f(\mathbf{b})}_{-})=\mathfrak{F}^{\circ}.$

By (15), we have
$\mathfrak{F}^{\circ}_{n(\mathbf{h})}(f(\mathbf{b}))=\mathfrak{F}^{\circ}$;
hence, by statement (1) of Proposition 6.1,

$\mathfrak{F}^{\circ}_{2n(\mathbf{h})}(\mathbf{b}\,d\,(-b_{last},\ldots,-b_{2}))\neq\varnothing\;\text{
and
}\;\mathfrak{F}^{\circ}_{2n(\mathbf{h})-1}(\mathbf{b}\,d\,(-b_{last},\ldots,-b_{3},))\neq\varnothing.$

Since the last terms of $f(\mathbf{b})$ are
$(-b_{3},-b_{2},-b_{1})=(-a_{3},-a_{2},-a_{1})$, the last terms of
$f(\mathbf{b})^{+}$ are $(-a_{3},-a_{2},-a_{1}+1)$. Then, in the view of
$-a_{3}=3-i$, we have

$\mathfrak{F}^{\circ}_{2n(\mathbf{h})-1}(\mathbf{b}\,d\,(-b_{last},\ldots,-b_{3}))=\mathfrak{F}^{\circ},\quad\text{thus,
}\quad\mathfrak{F}^{\circ}_{2n(\mathbf{h})}(\mathbf{b}\,d\,(-b_{last},\ldots,-b_{2}))=\mathfrak{F}^{\circ}_{1}(-b_{2}).$

Lastly, because of
$\mathfrak{F}^{\circ}_{2}(-a_{2},-a_{1}+1)=\mathfrak{F}^{\circ}_{2}(1+2i,-1+3i)=\mathfrak{F}^{\circ}$,
we may conclude
$\mathfrak{F}^{\circ}_{n(\mathbf{h})}(f(\mathbf{b})^{+})=\mathfrak{F}^{\circ}$.
The second equality in (16) follows from a similar observations and

$\mathfrak{F}^{\circ}_{n(\mathbf{h})}(-b_{1},\ldots,-b_{last-1},-b_{last}+1)=\mathfrak{F}^{\circ}.$

Consider $\mathbf{d}=\overleftarrow{f(\mathbf{b})}_{-}$. We have
$\mathfrak{F}^{\circ}_{n(\mathbf{h})}(\mathbf{d})=\mathfrak{F}^{\circ}$ from
$-b_{1}-1=-a_{1}-1$,
$\mathfrak{F}^{\circ}_{1}(-a_{1})=\mathfrak{F}^{\circ}_{1}(-a_{1}-1)=\mathfrak{F}^{\circ}$
and statement (2) of Proposition 6.1. The same observations and (15) yield
$\mathfrak{F}^{\circ}_{n(\mathbf{h})}(\overleftarrow{\mathbf{d}})=\mathfrak{F}^{\circ}$.

  4. (4)

Case $(h_{N},h)=(g,g)$. Put $\mathbf{c}:=gg(\mathbf{b})$. As before, it
suffices to show

$\mathfrak{F}^{\circ}_{n(\mathbf{h})}\left(g(\mathbf{b})^{+}\right)=\mathfrak{F}^{\circ}_{n(\mathbf{h})}\left(\overleftarrow{g(\mathbf{b})^{+}}\right)=\mathfrak{F}^{\circ}\quad\text{
and
}\quad\mathfrak{F}^{\circ}_{n(\mathbf{h})}\left(\overleftarrow{g(\mathbf{b})}_{-}\right)=\mathfrak{F}^{\circ}_{n(\mathbf{h})}\left(\overleftarrow{\overleftarrow{g(\mathbf{b})}_{-}}\right)=\mathfrak{F}^{\circ}.$

These identities are proven as in the previous case.

This shows (15) for $N+1$. Therefore, if
$\mathbf{c}=(c_{1},\ldots,c_{last})=\mathbf{h}(\mathbf{a})$ for some
$\mathbf{h}\in\\{f,g\\}^{n}$, $n\in\mathbb{N}$, then

$\iota\tau_{c_{last}}\cdots\iota\tau_{c_{1}}(0)=[c_{1},c_{2},\ldots,c_{last}]\in\mathcal{C}^{\circ}_{n(\mathbf{h})}(\mathbf{c})\subseteq\mathfrak{F}^{\circ}$

and $\mathbf{c}$ is valid.

## References

  * [1] S. Akiyama and J. M. Thuswaldner.  A survey on topological properties of tiles related to number systems.  Geom. Dedicata, 109:89–105, 2004.
  * [2] J.-P. Allouche and J. Shallit.  Automatic sequences.  Cambridge University Press, Cambridge, 2003.  Theory, applications, generalizations.
  * [3] J. Bourgain and A. Kontorovich.  On Zaremba’s conjecture.  Ann. of Math. (2), 180(1):137–196, 2014.
  * [4] Y. Bugeaud.  Sets of exact approximation order by rational numbers.  Math. Ann., 327(1):171–190, 2003.
  * [5] Y. Bugeaud.  Diophantine approximation and Cantor sets.  Math. Ann., 341(3):677–684, 2008.
  * [6] Y. Bugeaud.  Sets of exact approximation order by rational numbers. II.  Unif. Distrib. Theory, 3(2):9–20, 2008.
  * [7] Y. Bugeaud, G. González Robert, and M. Hussain.  Metrical properties of hurwitz continued fractions.  Preprint: arXiv:2306.08254, 2023.
  * [8] S. G. Dani and A. Nogueira.  Continued fractions for complex numbers and values of binary quadratic forms.  Trans. Amer. Math. Soc., 366(7):3553–3583, 2014.
  * [9] H. Ei, S. Ito, H. Nakada, and R. Natsui.  On the construction of the natural extension of the Hurwitz complex continued fraction map.  Monatsh. Math., 188(1):37–86, 2019.
  * [10] D. Gayfulin and N. Shulga.  Diophantine properties of fixed points of Minkowski question mark function.  Acta Arith., 195(4):367–382, 2020.
  * [11] W. J. Gilbert.  The fractal dimension of sets derived from complex bases.  Canad. Math. Bull., 29(4):495–500, 1986.
  * [12] G. González Robert.  Purely periodic and transcendental complex continued fractions.  Acta Arith., 194(3):241–265, 2020.
  * [13] Y. He and Y. Xiong.  Sets of exact approximation order by complex rational numbers.  Math. Z., 301(1):199–223, 2022.
  * [14] D. Hensley.  Continued fractions.  World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2006.
  * [15] R. Hines.  Badly approximable numbers over imaginary quadratic fields.  Acta Arith., 190(2):101–125, 2019.
  * [16] S. Huang.  An improvement to Zaremba’s conjecture.  Geom. Funct. Anal., 25(3):860–914, 2015.
  * [17] A. Hurwitz.  Über die Entwicklung complexer Grössen in Kettenbrüche.  Acta Math., 11(1-4):187–200, 1887.
  * [18] M. Iosifescu and C. Kraaikamp.  Metrical theory of continued fractions, volume 547 of Mathematics and its Applications.  Kluwer Academic Publishers, Dordrecht, 2002.
  * [19] I. Kátai and J. Szabó.  Canonical number systems for complex integers.  Acta Sci. Math. (Szeged), 37(3-4):255–260, 1975.
  * [20] A. Khinchin.  Continued fractions.  The University of Chicago Press, Chicago, Ill.-London, 1964.
  * [21] R. B. Lakein.  Approximation properties of some complex continued fractions.  Monatsh. Math., 77:396–403, 1973.
  * [22] W. J. LeVeque.  Continued fractions and approximations in $k(i)$. I, II.  Indag. Math., 14:526–535, 536–545, 1952.  Nederl. Akad. Wetensch. Proc. Ser. A 55.
  * [23] J. Levesley, C. Salp, and S. L. Velani.  On a problem of K. Mahler: Diophantine approximation and Cantor sets.  Math. Ann., 338(1):97–118, 2007.
  * [24] K. Mahler.  Some suggestions for further research.  Bull. Austral. Math. Soc., 29(1):101–108, 1984.
  * [25] N. Moshchevitin, B. Murphy, and I. Shkredov.  Popular products and continued fractions.  Israel J. Math., 238(2):807–835, 2020.
  * [26] N. Moshchevitin and I. Shkredov.  On a modular form of Zaremba’s conjecture.  Pacific J. Math., 309(1):195–211, 2020.
  * [27] H. Niederreiter.  Dyadic fractions with small partial quotients.  Monatsh. Math., 101(4):309–315, 1986.
  * [28] A. Pethő and J. Thuswaldner.  Number systems over orders.  Monatsh. Math., 187(4):681–704, 2018.
  * [29] N. Shulga.  Radical bound for Zaremba’s conjecture.  https://arxiv.org/pdf/2310.09801.pdf, preprint, 2023.
  * [30] D. Simmons.  The Hurwitz continued fraction expansion as applied to real numbers.  Enseign. Math., 62(3-4):475–485, 2016.
  * [31] A. J. van der Poorten and J. Shallit.  Folded continued fractions.  J. Number Theory, 40(2):237–250, 1992.