2. The relationship between $?(x)$ and Stern’s diatomic sequence

Stern’s diatomic sequence $s(n)$ is defined initially by $s(0)=0$ and $s(1)=1$ , and then for $n\geqslant 1$ , by the recursions

$$ \begin{align*}s(2n)=s(n)\quad\mbox{and}\quad s(2n+1)=s(n)+s(n+1).\end{align*} $$

Stern’s sequence can be used to list the rational numbers in $[0,1]$ , via what is known as the Stern–Brocot tree [Reference Brocot4, Reference Stern15]. Here, the kth level of the Stern–Brocot tree is composed of the finite increasing sequence of rationals

$$ \begin{align*}F_k(n):=\frac{s(n)}{s(2^k+n)},\quad n=0,\ldots,2^k.\end{align*} $$

Though slightly different, $F_k(n)$ is reminiscent of the kth level of the Farey tree and, similarly, in the limit as k goes to infinity, $F_k(n)$ produces all of the rational numbers in $[0,1]$ . It turns out that the points $(n/2^k,F_k(n))$ induce a strictly increasing continuous function $\Phi :[0,1]\to [0,1]$ , that is, $\Phi ({n}/{2^k})=F_k(n)$ for all $k\geqslant 0$ and $n\in \{0,1,\ldots ,2^k\}$ . The function $\Phi (x)$ is a somewhat well-known object, which turns out to be precisely the inverse function of Minkowski’s $?$ -function, a result that has been proved several times and is readily available in the literature. One convenient easy-to-read version was given by Northshield [Reference Northshield11, Section 6]. We have collected the necessary results from Northshield’s paper and record them in the following proposition. The proofs of these results are elementary and we encourage the interested reader to consult [Reference Northshield11].

Proposition 2.1 (Northshield).

The function $\Phi :[0,1]\to [0,1]$ is a strictly increasing continuous function satisfying

$$ \begin{align*}\Phi\bigg(\frac{n+1}{2^k}\bigg)-\Phi\bigg(\frac{n}{2^k}\bigg)=\frac{1}{s(2^k+n+1)s(2^k+n)}\end{align*} $$

for all $k\geqslant 0$ and $n\in \{0,1,\ldots ,2^k-1\}$ . Moreover, $\Phi ^{-1}(x)=\ ?(x)$ .

Since $\Phi (x)$ is a strictly increasing continuous function on $[0,1]$ , it is differentiable almost everywhere on $[0,1]$ . Moreover, using straightforward measure-theoretic arguments, if $\Phi (x)$ is singular continuous, then so is $\Phi ^{-1}(x)=\ ?(x)$ (see, for example, [Reference Berg and Krüppel3, Proposition 3.1]). Another way to see that the inverse of a strictly increasing singular continuous function is also singular continuous is via the length of the graph. The curve of the graphs of such functions that go from $(0,0)$ to $(1,1)$ necessarily (and sufficiently) have length equal to $2$ (see [Reference Dovgoshei and Martio8]). Thus, to prove our main result for Minkowski’s $?$ -function, we need only show that $\Phi (x)$ is singular continuous.

To this end, let us suppose that $\xi \in (0,1)$ is an irrational number for which $\Phi '(\xi )$ exists; the set of such $\xi $ has full Lebesgue measure in $[0,1]$ . Note that $\lfloor 2^n\xi \rfloor $ is the unique integer in $\{0,1,\ldots ,2^n-1\}$ for which $\lfloor 2^n\xi \rfloor /2^n<\xi <(\lfloor 2^n\xi \rfloor +1)/2^n$ . Since this derivative exists,

(2.1) $$ \begin{align} \Phi'(\xi)=\lim_{n\to\infty}\frac{\Phi(\frac{\lfloor 2^n\xi\rfloor+1}{2^n})-\Phi(\frac{\lfloor 2^n\xi\rfloor}{2^n})}{\frac{\lfloor 2^n\xi\rfloor+1}{2^n}-\frac{\lfloor 2^n\xi\rfloor}{2^n}} =\lim_{n\to\infty}\frac{2^n}{s(2^n+\lfloor 2^n\xi\rfloor)s(2^n+\lfloor 2^n\xi\rfloor+1)}. \end{align} $$

If we can show that for almost all of these $\xi $ , the limit (2.1) is equal to zero, then we are done. This is exactly what we will show.

We are led to study the asymptotic behaviour of the sequence $s(n)s(n+1)$ .

3. The structure and growth of $s(n)s(n+1)$

The recursions defining Stern’s sequence, when applied to $f(n):=s(n)s(n+1)$ , yield the recurrences

$$ \begin{align*} f(2n)&=s(2n)s(2n+1)=s(n)(s(n)+s(n+1))=f(n)+s(n)^2 \end{align*} $$

and

$$ \begin{align*} f(2n+1)&=s(2n+1)s(2n+2)=(s(n)+s(n+1))s(n+1)=f(n)+s(n+1)^2. \end{align*} $$

These recurrences allow us to represent the values $f(n)$ as matrix products.

Lemma 3.1. Let f be defined as above,

$$ \begin{align*}\mathbf{A}_0:=\begin{pmatrix}1&0&1\\2&1&1\\0&0&1\end{pmatrix} \quad\mbox{and}\quad\mathbf{A}_1:=\begin{pmatrix}1&1&0\\0&1&0\\2&1&1\end{pmatrix}.\end{align*} $$

If the binary expansion of n is $(n)_2=i_s\cdots i_1i_0$ , then $f(n)=(1\ 0\ 0) \mathbf {A}_{i_0}\mathbf {A}_{i_1}\cdots \mathbf {A}_{i_s}(0\ 1\ 0)^T.$

Proof. This follows directly from the recurrences satisfied by f, noting that

$$ \begin{align*}\begin{pmatrix}f(2n)\\ s(2n+1)^2\\ s(2n)^2\end{pmatrix}=\begin{pmatrix}1&0&1\\2&1&1\\0&0&1\end{pmatrix}\begin{pmatrix}f(n)\\ s(n+1)^2\\ s(n)^2\end{pmatrix}\quad \mbox{and}\quad \begin{pmatrix}f(2n+1)\\ s(2n+2)^2\\ s(2n+1)^2\end{pmatrix}=\begin{pmatrix}1&1&0\\0&1&0\\2&1&1\end{pmatrix}\begin{pmatrix}f(n)\\ s(n+1)^2\\ s(n)^2\end{pmatrix}.\end{align*} $$

The vector $(0\ 1\ 0)^T=(f(0)\ s(0+1)^2\ s(n)^2)^T$ is the vector of initial values and the vector $(1\ 0\ 0)$ pulls off the top entry of the product, which is the value of the function f.

The invariant subspaces of $\mathbf {A}_0$ and $\mathbf {A}_1$ are different, so as a pair, they are irreducible. Since these matrices are also nonnegative, the almost everywhere behaviour of their products is defined by the (maximal) Lyapunov exponent of the pair. The Lyapunov exponent of a finite set of $d\times d$ matrices, $\mathcal {M}:=\{\mathbf {M}_1,\mathbf {M}_2,\ldots , \mathbf {M}_{k}\}$ , is given by the value $\log \bar {\rho }$ , where

$$ \begin{align*} \bar{\rho}=\bar{\rho}(\mathcal{M}):=\lim_{n\to\infty}\bigg(\prod_{1\leqslant i_1,i_2,\ldots,i_{n}\leqslant k}\| \mathbf{M}_{i_1}\mathbf{ M}_{i_2}\cdots\mathbf{M}_{i_{n}}\|^{{1}/{n}}\bigg)^{1/k^n}, \end{align*} $$

where $\|\cdot \|$ is any (submultiplicative) matrix norm. Here, all nonzero entries of almost all sequences of products of $\mathbf {A}_0$ and $\mathbf {A}_1$ have the same asymptotic growth exponent—the (maximal) Lyapunov exponent (see [Reference Protasov12]). In particular, for Lebesgue-almost all $x\in [0,1)$ and any $i,j\in \{1,\ldots ,d\}$ ,

(3.1) $$ \begin{align}c_\xi(n)\cdot \bar{\rho}(\mathbf{A}_0,\mathbf{A}_1)^n\sim\mathbf{e}_i\mathbf{A}_{w_1}\mathbf{ A}_{w_2}\cdots\mathbf{A}_{w_{n}}\mathbf{e}_j,\end{align} $$

where the base-k expansion of x is $(x)_k=0.w_1w_2\cdots $ and $c_{\xi }(n)$ is subexponential in n.

Protasov and Jungers [Reference Protasov and Jungers13] determined an efficient way to effectively bound the (maximal) Lyapunov exponent of nonnegative matrices—we only use their lower bound. For any $m\in \mathbb {N}$ and any positive vector $v:=(v_1,v_2,\ldots ,v_d)^T\in \mathbb {R}_{>0}^d$ , define

$$ \begin{align*} \beta_m(v):=\min_{j=1,\ldots,d}\bigg(-\log(v_j)+\mathbb{E}\bigg\{\log\bigg(\sum_{i=1}^d a_{ij}v_i\bigg):\mathbf{ M}\in\mathcal{M}^m\bigg\}\bigg), \end{align*} $$

where $\mathcal {M}^m$ is the set of products of m elements of $\mathcal {M}$ and $\mathbb {E}$ denotes expectation. The following result can be found from Protasov and Jungers [Reference Protasov and Jungers13, (12)].

Proposition 3.3 (Protasov and Jungers).

Let $\mathcal {M}$ be a set of $k\geqslant 1$ nonnegative $d\times d$ matrices. Then,

$$ \begin{align*}\log\bar{\rho}\geqslant \sup_{v\in\mathbb{R}_{>0}^d}\beta_m(v).\end{align*} $$

In particular, $\log \bar {\rho }\geqslant \beta _m(v)$ for any single positive real vector v. In what follows, for convenience, we will use $v=(1,1,1)^T$ .

Proof. We apply Proposition 3.3 with $v=(1,1,1)^T$ and $k=2$ . For $\mathcal {A}:=\{\mathbf {A}_0,\mathbf {A}_1\}$ ,

$$ \begin{align*}\mathcal{A}^2=\left\{ \begin{pmatrix} 1&0&2\\ 4&1&4\\0&0&1\end{pmatrix}, \begin{pmatrix} 3&1&2\\ 2&1&1\\4&1&4\end{pmatrix}, \begin{pmatrix} 3&2&1\\ 4&4&1\\2&1&1\end{pmatrix}, \begin{pmatrix} 1&2&0\\ 0&1&0\\4&4&1\end{pmatrix}\right\} .\end{align*} $$

Inspecting the columns in order,

$$ \begin{align*} \!\!\!\!\!\!\!\!\!\!\!\!\!\!\beta_2((1,1,1)^T)=\min\bigg\{\!\frac{\log(5\cdot9\cdot9\cdot5)}{4},\frac{\log(1\cdot3\cdot7\cdot7)}{4},\frac{\log(7\cdot7\cdot3\cdot1)}{4}\!\bigg\}>\log 2. \\[-40pt]\end{align*} $$

4. A new proof of the singularity of $?(x)$

Recall, the singularity of $?(x)$ follows if the limit (2.1) is zero for almost all ${\xi \in [0,1]}$ .

For Lebesgue-almost every $\xi \in [0,1]$ , (3.1) gives

$$ \begin{align*}s(2^n+\lfloor 2^n\xi\rfloor)s(2^n+\lfloor 2^n\xi\rfloor+1)=(1\ 0\ 0) \mathbf{A}_{i_1}\mathbf{A}_{i_2}\cdots \mathbf{A}_{i_n}(0\ 1\ 0)^T\sim c_{\xi}(n)\cdot\bar{\rho}(\mathbf{ A}_0,\mathbf{A}_1)^n,\end{align*} $$

where $c_{\xi }(n)$ grows subexponentially in n and $(\xi )_k=0.i_1i_2\cdots $ in base k. By Lemma 3.4, $\bar {\rho }(\mathbf {A}_0,\mathbf {A}_1)>2$ . Thus, for Lebesgue-almost all $\xi \in [0,1]$ ,

$$ \begin{align*}\Phi'(\xi)=\lim_{n\to\infty}\frac{2^n}{c_{\xi}(n)\cdot\bar{\rho}(\mathbf{A}_0,\mathbf{A}_1)^n}=0.\end{align*} $$

That is, the limit (2.1) is zero for almost all $\xi $ , which finishes the proof.