\documentclass[11pt,reqno]{amsart}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[hmargin=1.1in,vmargin=1in]{geometry}
\usepackage{mathtools,amssymb,microtype,graphicx,needspace}
\usepackage[hidelinks]{hyperref}
\hypersetup{pdftitle={Non-computable derivatives of the fractional-part autocorrelation}}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\N}{\mathbb N}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\W}{\mathcal W}
\newcommand{\leT}{\leq_{\mathrm T}}
\newcommand{\nleT}{\nleq_{\mathrm T}}
\newcommand{\eqT}{\equiv_{\mathrm T}}
\newcommand{\degT}{\deg_{\mathrm T}}
\newcommand{\zerojump}{\mathbf 0'}
\newcommand{\Irr}{(0,1)\setminus\Q}
\newcommand{\ignore}[1]{}

\title[Non-computable derivatives]{Non-computable derivatives of the\ fractional-part autocorrelation}
% Authorship and affiliation are left for the authors to supply.
\author{Michael Yampolsky}
\date{\today}
\keywords{Computable analysis, fractional-part autocorrelation, Wilton function,
continued fractions, non-computable derivatives}

\begin{document}
\begin{abstract}
We describe a natural new example of non-computability in analysis. Namely,
the multiplicative autocorrelation of the fractional-part function, 
\[
 A(x)=\int_0^\infty \{t\}\{xt\}\,\frac{dt}{t^2},
\]
is computable and differentiable almost everywhere, but its finite derivative
can be non-computable even for a computable $x$. We derive these results from an adaptation of our earlier work \cite{YS} on
computability of Brjuno-like functions. 
\end{abstract}
\maketitle

\section*{The use of AI}
The author acknowledges using an OpenAI model in writing this paper. The author has formulated the problem. The proofs are based on the author's ideas, and, in particular, an earlier work \cite{YS}. The author assumes full responsibility for the content and its correctness.

\section{Introduction and main results}

This paper introduces an interesting new example of a natural non-computable function of a real variable. 
The {\it multiplicative autocorrelation of the fractional-part function} is defined by an absolutely convergent,
nonnegative integral:
\begin{equation}\label{eq:A}
 A(x)=\int_0^\infty \{t\}\{xt\}\,\frac{dt}{t^2},\qquad x\geq 0\text{ where }\{t\}=t-\lfloor t\rfloor.
\end{equation}
The analytic properties of $A$ were studied by B\'aez-Duarte, Balazard,
Landreau, and Saias \cite{BD,BDlong} in the context of analytic number theory.
In particular, $A(x)$ is continuous and differentiable almost everywhere. Its value is effectively computable from the point of evaluation via an explicit approximation process.
Yet, strikingly for such a simple-looking analytic expression,
its derivative $A'(x)$ at a point $x$ may be well-defined, yet  not be computable from $x$.
In fact, non-computability may occur even for a computable value of $x$. 

The connection with our previous work flows from the results of
Balazard and Martin \cite{BM}, who characterized the
differentiability points of $A(x)$  through a continued-fraction series introduced by
Wilton \cite{Wilton}. We combine their identities with the
non-computability theorem for the signed Wilton series obtained in our paper  \cite{YS}, and then
refine the conclusion by constructing computable inputs. Both arguments
require the same effective step: computing the correction terms that relate
the Wilton series to $A'$.

Before stating the theorems, let us introduce several series.
For irrational $x\in(0,1)$, set
\begin{equation}\label{eq:DS}
 D(x)=\sum_{m=1}^{\infty}\frac{\{mx\}-1/2}{m},\qquad
 S(x)=\sum_{m=1}^{\infty}\frac{\tau(m)}m\sin(2\pi mx),
\end{equation}
where $\tau(m)$ is the number of positive divisors of $m$.
%These are ordinary convergent-series values, not values assigned by a summability method.
Further, to define the Wilton function, set
\[
 T(x)=\{1/x\},\qquad x_n=T^n(x),\qquad
 \beta_{-1}(x)=1,\quad \beta_{n-1}(x)=x_0\cdots x_{n-1}\quad(n\geq1),
\]
and let
\begin{equation}\label{eq:W}
 W(x)=\sum_{n=0}^{\infty}(-1)^n\beta_{n-1}(x)\log\frac1{x_n}.
\end{equation}
%All logarithms are natural.
We denote by $\W$ the set of \emph{Wilton
numbers}, namely the irrational $x\in(0,1)$ for which \eqref{eq:W}
converges. Absolute convergence defines the smaller class of {\it Brjuno
numbers} which play a special role in the study of small-divisor problems in holomorphic dynamics \cite{yoccoz1995}.

We use the Cauchy representation of real numbers. {\it An oracle for $x$} is a function which
returns rational approximations to $x$ with error less than $2^{-n}$ on
input $n$. The notation $y\leT x$ means that one oracle algorithm computes $y$
from every Cauchy name of this fixed $x$. A function on a specified domain is {\it computable} if one
oracle algorithm works for every input in that domain. In particular,
$F(x)\nleT x$ is a pointwise obstruction, stronger than the failure of a
single algorithm to work uniformly on the whole domain.

The first result is a direct corollary of the signed Wilton theorem
of \cite{YS}, once we have made effective the known analytic identities for $A'(x)$.

\begin{theorem}\label{thm:main}
The function $A$ is computable on $[0,\infty)$. Every nonempty open interval
$I\subset(0,1)$ contains a point $x\in\W$ at which $A'(x)$ exists as a
finite real number and
\begin{equation}\label{eq:noncomputability}
 A'(x)\nleT x,\qquad D(x)\nleT x,\qquad
 S(x)\nleT x,\qquad W(x)\nleT x.
\end{equation}
Moreover, at every $x\in\W$, the four quantities are mutually computable
relative to $x$: uniformly on this domain,
\begin{equation}\label{eq:joins}
 x\oplus A'(x)\eqT x\oplus D(x)\eqT
 x\oplus S(x)\eqT x\oplus W(x).
\end{equation}
\end{theorem}

The non-computability input here is precisely
\cite[Theorems~5.1 and~5.2]{YS}, applied to their second Wilton function.
Theorem~\ref{thm:main} does not, by itself, assert that the input value $x$
is computable. Our second result supplies computable $x$
and specifies the amount of information in the four values.

A real number is \emph{limit-computable} if it is the limit of a computable
sequence of rationals, without a required computable rate of convergence.
It is \emph{left-computably enumerable (left-c.e.)} if it admits such a
nondecreasing approximation; right-c.e. is defined using nonincreasing
approximations. A c.e. Turing degree is the degree of a computably
enumerable subset of $\N$, and $\zerojump$ denotes the degree of the
halting problem.

\begin{theorem}[{\bf Computable-input refinement}]\label{thm:refined}
Let $r\in(0,1)$ be limit-computable, and let $I\subset(0,1)$ be a nonempty
open interval with rational endpoints. There is a computable $x\in I\cap\W$
such that $A'(x)$ exists and
\begin{equation}\label{eq:degrees}
 A'(x)\eqT D(x)\eqT S(x)\eqT W(x)\eqT r.
\end{equation}
More precisely, the construction gives
\begin{equation}\label{eq:affineW}
 W(x)=(\log2)r+c
\end{equation}
with $c$ computable. Both $x$ and $c$ are computable uniformly from $I$ and
a program producing a convergent rational approximation to $r$.
If the supplied approximation has finite total variation, then $x$ can
be chosen Brjuno. In particular, this applies to a nondecreasing
approximation.
\end{theorem}

\begin{corollary}\label{cor:brjuno}
In every nonempty open subinterval of $(0,1)$ there is a computable Brjuno
number $x$ for which $A'(x),D(x),S(x),W(x)$ are all finite and non-computable.
They can be chosen to have any prescribed nonzero c.e. Turing degree.
\end{corollary}

\Needspace{8\baselineskip}
\begin{theorem}[{\bf Full degree spectrum}]\label{thm:spectrum}
For every nonempty open interval $I\subset(0,1)$ and each
$F\in\{A',D,S,W\}$,
\begin{equation}\label{eq:spectrum}
 \bigl\{\degT F(x):x\in I\cap\W\text{ is computable}\bigr\}
 =\bigl\{\mathbf d:\mathbf d\leq\zerojump\bigr\}.
\end{equation}
Each degree on the right is realized simultaneously by the four quantities
at a single computable point in $I$.
\end{theorem}

The full spectrum concerns Wilton points, not necessarily Brjuno points.
Computable Brjuno points already suffice to realize all c.e. degrees,
including the computable degree.
%At the Brjuno points in Corollary~\ref{cor:brjuno}, the Wilton series is absolutely convergent;
%no assertion of absolute convergence is being made for $D$ or $S$.

Section~\ref{sec:background} presents the basic analytic properties of $A$.
Sections~\ref{sec:effective} and~\ref{sec:transfer} prove the common reduction
\begin{equation}\label{eq:lead-reduction}
 A'(x)=C(x)-\frac{W(x)}{2x}\qquad(x\in\W),
\end{equation}
where $C$ is computable from $x$. Section~\ref{sec:YS} then proves the direct
corollary of \cite{YS}. Section~\ref{sec:refinement} supplies the
adapted realization argument, and Section~\ref{sec:consequences} deduces the
degree spectrum and the one-sided computability statements.

\section{Basic properties of the autocorrelation}
\label{sec:background}

\subsection{Reciprocity and the Hilbert-space interpretation}
Near zero the integrand in \eqref{eq:A} equals $x$, and near infinity it is
bounded by $t^{-2}$, so $A(x)$ is finite for every $x\geq0$. A change of
variables gives
\begin{equation}\label{eq:reciprocity}
 A(x)=xA(1/x)\qquad(x>0).
\end{equation}
This identity will reduce computation on $[0,\infty)$ to computation on
$[0,1]$.

  The name ``autocorrelation'' has a literal Hilbert-space meaning.
  Let $f(t)=\{t\}$. In the Hilbert space $L^2((0,\infty),dt/t^2)$ we have
\[
 A(x)=\langle f,f(x\,\cdot)\rangle,\qquad
 \|f(x\,\cdot)\|_2^2=x\|f\|_2^2.
\]
Cauchy--Schwarz therefore gives
\begin{equation}\label{eq:CS}
 0<A(x)\leq\sqrt{x}\,A(1)\quad(x>0),\qquad
 A(1)=\log(2\pi)-\gamma,
\end{equation}
where $\gamma$ is Euler's constant. The value at $1$ follows by integration
over successive unit intervals and Stirling's formula; see
\cite[Propositions~85 and~87]{BDlong}. Our algorithm below computes $A(1)$
directly from the integral and does not require this special-value formula.

\subsection{Regularity and differentiability}
Balazard and Martin prove that the global modulus of continuity
\[
 \omega_A(h)=\sup_{\substack{x,y\geq0\\|x-y|\leq h}}|A(x)-A(y)|
\]
satisfies
\begin{equation}\label{eq:sharp-modulus}
 \omega_A(h)=\frac12 h\log(1/h)+O(h)\qquad(h\downarrow0);
\end{equation}
see \cite[Proposition~31]{BM}. This describes the regularity of $A$, but
we do not use the unspecified constant in the $O(h)$ term to compute it.
Proposition~\ref{prop:Acomputable} supplies an explicit modulus and an
effective truncation bound for that purpose.

At a positive rational $p/q$ in lowest terms, $A$ has a logarithmic cusp:
\begin{equation}\label{eq:cusp}
 A(p/q+h)-A(p/q)
 =\frac{|h|\log|h|}{2p}+O_{p,q}(|h|)\qquad(h\to0),
\end{equation}
by \cite[Proposition~98]{BDlong}. Thus every positive rational is a strict
local maximum, with infinite one-sided slopes. These singularities explain
the cusps visible in Figure~\ref{fig:A}.

For irrational $x\in(0,1)$, there is an exact criterion: $A'(x)$ exists as a
finite real number if and only if $x\in\W$
\cite[Theorem~1 and Proposition~30]{BM}. The Wilton set has full Lebesgue
measure in $(0,1)$, so $A$ is differentiable almost everywhere there -- and (\ref{eq:reciprocity}) 
extends this conclusion to $(0,\infty)$.
%The pointwise criterion, rather than the almost-everywhere assertion, guarantees
%existence at the inputs used in our non-computability arguments.
The identities for the derivative values are stated in Theorem~\ref{thm:BM}.

\begin{figure}[tbp]
\centering
\includegraphics[width=0.94\textwidth]{autocorrelation_graph.pdf}
\caption{The autocorrelation $A$ on $[0,2]$. Values at mesh points $p/2400$
were computed using the finite cotangent-sum formula of
\cite[Proposition~89]{BDlong} and joined. The graph illustrates the rational
cusps.}
\label{fig:A}
\end{figure}

\section{Effective evaluation of the autocorrelation and the correction}
\label{sec:effective}

\subsection{Computability of the autocorrelation}
We first evaluate truncated integrals at rational arguments, then use an
explicit modulus to pass to arbitrary Cauchy names. 

\begin{proposition}\label{prop:Acomputable}
The function $A$ is computable on $[0,\infty)$. On $[0,1]$, one has
$0\leq A(x)\leq2$, and for each integer $M\geq1$,
\begin{equation}\label{eq:Amodulus}
 |A(x)-A(y)|\leq |x-y|(2+2\log M)+\frac2M,
 \qquad 0\leq x,y\leq1.
\end{equation}
\end{proposition}
\begin{proof}
Let $A_M(x)$ denote the integral in \eqref{eq:A} truncated at $M$.
Its tail lies in $[0,1/M]$, uniformly in $x$.
For rational $x\in(0,1]$, split $[1,M]$ at the finitely many rational
points where $t$ or $xt$ is integral. On an intervening interval,
\[
 \frac{\{t\}\{xt\}}{t^2}
 =\frac{(t-j)(xt-k)}{t^2}
 =x-\frac{k+jx}{t}+\frac{jk}{t^2}.
\]
Integrating uses only rational arithmetic and logarithms of positive
rationals. The contribution of $(0,1)$ is $x$, and $A(0)=0$.
Thus $A$ is uniformly computable at rational inputs.

To pass to arbitrary Cauchy names, suppose $0\leq x<y\leq1$ and write
$h=y-x$. For almost every $t\in[1,M]$,
\[
 |\{yt\}-\{xt\}|
 \leq ht+\sum_{k=1}^{M}\mathbf1_{\{xt<k\leq yt\}}.
\]
Before intersection with $[1,M]$, the support of the $k$th indicator is
$[k/y,k/x)$, with upper endpoint $+\infty$ when $x=0$. Its integral
against $dt/t^2$ is $h/k$. Hence
\[
 |A_M(y)-A_M(x)|
 \leq h\left(1+\log M+\sum_{k=1}^{M}\frac1k\right)
 \leq h(2+2\log M).
\]
Adding the tail bounds gives \eqref{eq:Amodulus}. Given an error tolerance,
first choose $M$ effectively and then approximate $x$ by a sufficiently
close rational in $[0,1]$. This computes $A(x)$ without having to decide
coincidences between discontinuity locations at an arbitrary real input.
The bound $A(x)\leq2$ follows from the contribution $x$ of $(0,1)$ and
the upper bound $1$ for the remaining integral.

Finally, with $m=\max(1,x)$, reciprocity gives
\[
 A(x)=m A(x/m^2),\qquad x/m^2\in[0,1].
\]
All operations here are computable, including $\max$, so the algorithm
extends to $[0,\infty)$ without deciding whether $x=1$.
\end{proof}

\subsection{Computability of the correction term}
The identities in Theorem~\ref{thm:BM} express $A'$, $D$, and $S$ in terms
of $W$ and a correction $G$. We now prove that $G$ is computable on every
irrational input, whether or not $W$ converges. Following
\cite[Section~4.1]{BM}, define
\begin{equation}\label{eq:F}
 F(t)=\frac{t+1}{2}A(1)-A(t)-\frac t2\log t,
 \qquad 0\leq t\leq1,
\end{equation}
where $t\log t=0$ at $0$, and put
\begin{equation}\label{eq:G}
 G(x)=\sum_{n=0}^{\infty}(-1)^n\beta_{n-1}(x)F(x_n),
 \qquad x\in\Irr.
\end{equation}
The  difference from $W$ is the uniform effective tail bound below.

\begin{proposition}\label{prop:Gcomputable}
The function $F$ is computable on $[0,1]$, and $G$ is computable on
$\Irr$. More explicitly, for every integer $K\geq1$,
\begin{equation}\label{eq:Gtail}
 \sum_{n\geq2K}|\beta_{n-1}(x)F(x_n)|\leq5\cdot2^{2-K}.
\end{equation}
\end{proposition}
\begin{proof}
Proposition~\ref{prop:Acomputable} and the computable continuous extension
of $t\log t$ give computability of $F$. At the endpoint, for example,
$0\leq t\leq2^{-m}$ and $m\geq2$ imply
$|t\log t|\leq m2^{-m}\log2$. Also $|F(t)|\leq5$ on $[0,1]$.

Write $x=[0;a_1,a_2,\ldots]$, with convergent denominators
$q_{-1}=0$, $q_0=1$, and
$q_{n+1}=a_{n+1}q_n+q_{n-1}$. The standard identities give
\[
 \beta_{n-1}(x)=\frac1{q_n+x_nq_{n-1}}\leq\frac1{q_n},
 \qquad q_{n+2}\geq2q_n.
\]
In particular, $q_n\geq2^{\lfloor n/2\rfloor}$ and
\[
 \sum_{n\geq2K}\frac1{q_n}
 \leq2\sum_{k\geq K}2^{-k}=2^{2-K}.
\]
This proves \eqref{eq:Gtail}.

The digits of an irrational continued fraction can be computed from its
Cauchy name. At each finite step, the real whose integer part is needed
is not an integer, so increasing precision eventually determines that
digit. Thus every finite term of \eqref{eq:G} is uniformly computable
from $x$. The effective tail bound completes the algorithm.
\end{proof}

\section{Classical identities and an effective transfer principle}
\label{sec:transfer}

The following theorem both identifies the differentiability points and
relates the four values there. In the notation of \cite{BM}, our $D$ is
$\varphi_1$, and $-S/\pi$ is $\psi_1$. Their Bernoulli function is
$B_1(t)=\{t\}-1/2$ off the integers and $B_1(t)=0$ on the integers.
At irrational arguments this convention agrees with \eqref{eq:DS}.

\begin{theorem}[Balazard--Martin]\label{thm:BM}
For $x\in\Irr$, the series $D(x),S(x),W(x)$ converge simultaneously,
and their convergence is equivalent to differentiability of $A$ at $x$.
At such a point,
\begin{align}
 D(x)&=-\frac1\pi S(x)=-\frac12W(x)+G(x),\label{eq:DSW}\\
 xA'(x)&=A(x)-\frac12\bigl(\log x+A(1)\bigr)+D(x).\label{eq:derivative}
\end{align}
\end{theorem}
\begin{proof}[References and the derivative formula]
The convergence assertions and \eqref{eq:DSW} are
\cite[Theorems~1 and~2]{BM}; the additional correction at rational points
in that paper vanishes on our domain. For \eqref{eq:derivative}, use their
identity (6), already established in \cite{BD}:
\begin{equation}\label{eq:integralD}
 A(x)=\frac12\log x+\frac{A(1)+1}{2}
      -x\int_x^\infty D(t)\,\frac{dt}{t^2}.
\end{equation}
In this integral $D$ denotes its periodic integrable representative.
Every Wilton point is a Lebesgue point of $W$
\cite[Proposition~12]{BM}. Since $G$ is continuous at irrational points,
\eqref{eq:DSW} makes it a Lebesgue point of $D$ as well. The derivative
of the integral in \eqref{eq:integralD} is therefore $-D(x)/x^2$ at the
point in question. Differentiating \eqref{eq:integralD} and eliminating
the integral yields \eqref{eq:derivative}.
\end{proof}

The divisor weight in $S$ is also natural. Formally inserting the Fourier
series of $B_1$ into $D$ gives
\[
 D(x)=-\frac1\pi\sum_{m,n\geq1}\frac{\sin(2\pi mnx)}{mn}
     =-\frac1\pi\sum_{k\geq1}\frac{\tau(k)}k\sin(2\pi kx).
\]
The passage from this formal calculation to equality of the ordinarily
convergent series is part of the classical theorem, not an application of
absolute rearrangement.

Define on $\Irr$
\begin{equation}\label{eq:C}
 C(x)=\frac1x\left(A(x)-\frac12(\log x+A(1))+G(x)\right).
\end{equation}
Propositions~\ref{prop:Acomputable} and~\ref{prop:Gcomputable} make $C$
computable. Combining this fact with the classical identities gives the
transfer used in both non-computability arguments.

\begin{proposition}[Effective transfer]\label{prop:transfer}
For every $x\in\W$,
\begin{align}
 A'(x)&=C(x)-\frac{W(x)}{2x},\label{eq:Atransfer}\\
 D(x)&=G(x)-\frac12W(x),\label{eq:Dtransfer}\\
 S(x)&=\frac\pi2 W(x)-\pi G(x).\label{eq:Stransfer}
\end{align}
These identities are uniformly computably invertible when an oracle for
$x$ is available. In particular, \eqref{eq:joins} holds, and
\[
 A'(x)\leT x\ \Longleftrightarrow\ D(x)\leT x
 \ \Longleftrightarrow\ S(x)\leT x
 \ \Longleftrightarrow\ W(x)\leT x.
\]
\end{proposition}
\begin{proof}
The formulas follow from Theorem~\ref{thm:BM}. All correction terms are
computable from $x$, and the coefficients $-1/(2x)$, $-1/2$, and $\pi/2$
are nonzero and computable from $x$. For example,
\[
 W(x)=2x\bigl(C(x)-A'(x)\bigr).
\]
The other inversions are equally explicit.
\end{proof}

\begin{corollary}\label{cor:degrees}
At every computable Wilton point, the finite numbers
$A'(x),D(x),S(x),W(x)$ have the same Turing degree.
\end{corollary}

\section{Direct application of \cite{YS}}
\label{sec:YS}

\begin{theorem}[{\bf Signed Wilton case in \cite{YS}}]\label{thm:YS}
There exists $\xi\in\W$ for which $W(\xi)\nleT\xi$.
\end{theorem}

This is \cite[Theorems~5.1 and~5.2]{YS}, specialized to the second Wilton
function $\mathcal W_2$ defined in their equation (2.3). Their index $i$
corresponds to $n+1$ in \eqref{eq:W}; the sign $(-1)^{i+1}$ is $(-1)^n$,
and the logarithm is $-\log x_n$. Thus the functions agree exactly.
The construction in their Section~5 yields a finite convergent value,
and their definition of non-computability at a point is the oracle-based
notion used here. We use the theorem without reproducing that construction.

For completeness, the following elementary observation supplies the
localization in Theorem~\ref{thm:main}.
%It is a finite change of coordinates, not an additional non-computability construction.

\begin{lemma}\label{lem:prefix}
If $\xi\in\W$ and $W(\xi)\nleT\xi$, every continued-fraction cylinder
in $(0,1)$ contains a point $x\in\W$ with $W(x)\nleT x$.
\end{lemma}
\begin{proof}
Let the cylinder be specified by a finite word $(a_1,\ldots,a_m)$, and
set
\[
 x=h(\xi)=[0;a_1,\ldots,a_m+\xi].
\]
Equivalently, if $\xi=[0;b_1,b_2,\ldots]$, then
$x=[0;a_1,\ldots,a_m,b_1,b_2,\ldots]$. For the convergents of the
fixed prefix,
\begin{equation}\label{eq:Mobius}
 h(t)=\frac{p_m+p_{m-1}t}{q_m+q_{m-1}t},\qquad T^m(x)=\xi.
\end{equation}
The map $h$ and its inverse on the cylinder are computable, so $x\eqT\xi$.
Splitting the Wilton series after $m$ terms gives
\begin{equation}\label{eq:prefixW}
 W(x)=P_m(x)+(-1)^m\beta_{m-1}(x)W(\xi),
\end{equation}
where
\[
 P_m(x)=\sum_{n=0}^{m-1}(-1)^n\beta_{n-1}(x)\log\frac1{x_n}.
\]
Both $P_m(x)$ and the positive coefficient $\beta_{m-1}(x)$ are
computable from $x$. The split series converges because $W(\xi)$ does.
If $W(x)\leT x$, inverting \eqref{eq:prefixW} would compute $W(\xi)$
from $x$, hence from $\xi$, a contradiction.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Computability of $A$ is Proposition~\ref{prop:Acomputable}, and the
uniform reductions are Proposition~\ref{prop:transfer}.
Choose $\xi$ from Theorem~\ref{thm:YS}. Every nonempty open subinterval
of $(0,1)$ contains a continued-fraction cylinder: cylinder diameters tend
to zero, as follows from $q_m\geq2^{\lfloor m/2\rfloor}$.
Lemma~\ref{lem:prefix} gives $x\in I\cap\W$ with $W(x)\nleT x$.
Theorem~\ref{thm:BM} gives existence of all four finite values, and
Proposition~\ref{prop:transfer} gives their non-computability relative to
$x$.
\end{proof}


\section{Refinement of the non-computability argument}
\label{sec:refinement}


\subsection{Effective continued-fraction estimates}

Recall the conventions
\[
 x=[0;a_1,a_2,\ldots],\qquad
 p_{-1}=1,\ p_0=0,\ q_{-1}=0,\ q_0=1,
\]
and use the recurrences
\[
 p_{n+1}=a_{n+1}p_n+p_{n-1},\qquad
 q_{n+1}=a_{n+1}q_n+q_{n-1}.
\]
A computable infinite sequence of positive integer partial quotients
determines a computable irrational. Indeed,
\begin{equation}\label{eq:cferror}
 \left|x-\frac{p_n}{q_n}\right|<\frac1{q_nq_{n+1}},\qquad
 q_n\geq 2^{\lfloor n/2\rfloor}.
\end{equation}
Thus a prescribed precision requires only an effectively determined finite
prefix, irrespective of the sizes of the partial quotients. Conversely,
the continued-fraction digits of an irrational are computable from a Cauchy
name: at each finite step the real whose integer part is required is not
an integer, so increasing the working precision eventually determines it.

\Needspace{11\baselineskip}
\begin{lemma}\label{lem:tails}
Uniformly over all irrational $x\in(0,1)$, the series
\[
 \sum_{n\geq0}\frac1{q_n},\qquad
 \sum_{n\geq0}\frac{\log(2q_n)}{q_n}
\]
have effective tail bounds. In particular, for every integer $K\geq1$,
\begin{equation}\label{eq:tailbounds}
 \sum_{n\geq2K}\frac1{q_n}\leq2^{2-K},\qquad
 \sum_{n\geq2K}\frac{\log(2q_n)}{q_n}
 \leq(K+2)2^{2-K}.
\end{equation}
\end{lemma}
\begin{proof}
The recurrence gives $q_{n+2}\geq2q_n$, hence \eqref{eq:cferror}.
For $n=2k$ or $2k+1$, with $k\geq1$, the function
$t\mapsto\log(2t)/t$ is decreasing for $t\geq2$, so
\[
 \frac{\log(2q_n)}{q_n}
 \leq\frac{(k+1)\log2}{2^k}\leq\frac{k+1}{2^k}.
\]
Summing the two geometric majorants proves the claim.
\end{proof}

Put
\begin{equation}\label{eq:gammaL}
 \gamma_n(x)=\beta_{n-1}(x)\log\frac1{x_n},\qquad
 L_n(x)=\frac{\log q_{n+1}}{q_n}.
\end{equation}
We use the classical comparison estimate
\begin{equation}\label{eq:comparison}
 |\gamma_n(x)-L_n(x)|\leq\frac{\log(2q_n)}{q_n},\qquad n\geq0;
\end{equation}
see \cite[Proposition~1]{BM12}. Also,
\begin{equation}\label{eq:beta}
 \beta_{n-1}(x)=\frac1{q_n+x_nq_{n-1}}\leq\frac1{q_n}.
\end{equation}

\begin{lemma}\label{lem:comparison-effective}
The function
\begin{equation}\label{eq:H}
 H(x)=\sum_{n=0}^\infty(-1)^n\bigl(\gamma_n(x)-L_n(x)\bigr)
\end{equation}
is computable on $(0,1)\setminus\Q$. Consequently, whenever either signed
series converges,
\[
 W(x)=W_q(x)+H(x),\qquad
 W_q(x):=\sum_{n=0}^\infty(-1)^nL_n(x).
\]
Moreover, $x$ is Brjuno if and only if $\sum_nL_n(x)<\infty$.
\end{lemma}
\begin{proof}
Each summand is computable from an irrational $x$.
The absolute tail is bounded by \eqref{eq:tailbounds}, so the series is
effectively convergent, even when $W$ itself is undefined. The remaining
claims follow from the absolute convergence of the difference series.
\end{proof}

\subsection{Realizing a convergent approximation}

\begin{lemma}\label{lem:digit}
Suppose $q\geq1$, $0\leq q'\leq q$, and $d\geq0$ is rational. Set
\[
 k=\lfloor dq\rfloor,\qquad a=2^k,\qquad Q=aq+q'.
\]
Then
\begin{equation}\label{eq:digit}
 \frac{\log Q}{q}=(\log2)d+\varepsilon,
 \qquad |\varepsilon|\leq\frac{\log(2q)}q.
\end{equation}
\end{lemma}
\begin{proof}
We have
\[
 q\varepsilon=
 -(dq-k)\log2+\log q+\log\left(1+\frac{q'}{2^kq}\right).
\]
The first term lies in $(-\log2,0]$ and the last in $[0,\log2]$.
The asserted bound follows.
\end{proof}

\begin{proposition}\label{prop:coding}
Let $(r_j)_{j\geq0}$ be a computable sequence of rationals in $[0,1]$
with $r_0=0$ and $r_j\to r$. Given any finite continued-fraction prefix
of even length, one can compute an irrational $x$ extending that prefix
and a computable real $c$ such that $x\in\W$ and
\[
 W(x)=(\log2)r+c.
\]
For this construction, $x$ is Brjuno if and only if
$\sum_j|r_{j+1}-r_j|<\infty$.
\end{proposition}
\begin{proof}
Let the length of the prescribed prefix be $N=2m$, possibly zero. Put
\[
 \delta_j=r_{j+1}-r_j,\qquad
 \delta_j^+=\max(\delta_j,0),\qquad
 \delta_j^-=\max(-\delta_j,0),
\]
and assign the target terms
\begin{equation}\label{eq:targets}
 h_{N+2j}=\delta_j^+,\qquad
 h_{N+2j+1}=\delta_j^-,\qquad j\geq0.
\end{equation}
Starting after the prescribed prefix, define successively
\begin{equation}\label{eq:construction}
 a_{n+1}=2^{\lfloor h_nq_n\rfloor},\qquad
 q_{n+1}=a_{n+1}q_n+q_{n-1},\qquad n\geq N.
\end{equation}
All floors in this formula are floors of rational numbers, and therefore
are obtained by exact integer arithmetic. Every partial quotient is a
positive integer. Equation~\eqref{eq:cferror} shows that the resulting
infinite continued fraction is a computable irrational, uniformly from
the supplied data. 

Lemma~\ref{lem:digit} gives, for $n\geq N$,
\begin{equation}\label{eq:coding-error}
 L_n=(\log2)h_n+\varepsilon_n,
 \qquad |\varepsilon_n|\leq\frac{\log(2q_n)}{q_n}.
\end{equation}
The sequence $(\varepsilon_n)$ is uniformly computable, and its absolute
sum has the effective tail bound of Lemma~\ref{lem:tails}. Thus
\[
 E=\sum_{n=N}^\infty(-1)^n\varepsilon_n
\]
is a computable real, uniformly from the approximation program and the
prefix.

Because $N$ is even, the sum of the target terms over the first $J$
complete pairs is
\[
 \sum_{n=N}^{N+2J-1}(-1)^nh_n
 =\sum_{j=0}^{J-1}(\delta_j^+-\delta_j^-)=r_J.
\]
A partial sum stopping within the next pair differs by $\delta_J^+$,
which tends to zero since $(r_j)$ converges. Therefore the full signed
series of targets converges to $r$, not just its paired subsequence.
It follows from \eqref{eq:coding-error} that
\[
 W_q(x)=P+(\log2)r+E,\qquad
 P=\sum_{n=0}^{N-1}(-1)^nL_n.
\]
The finite sum $P$ is computable. Lemma~\ref{lem:comparison-effective}
now yields
\[
 W(x)=(\log2)r+c,\qquad c=P+E+H(x),
\]
where $c$ is computable with the asserted uniformity.

Finally, all $L_n$ and $h_n$ are nonnegative, the error in
\eqref{eq:coding-error} is absolutely summable, and
\[
 \sum_{n=N}^\infty h_n=\sum_{j=0}^\infty|\delta_j|.
\]
Thus $\sum_nL_n<\infty$ if and only if the approximation has finite
total variation. Lemma~\ref{lem:comparison-effective} proves the last
claim.
\end{proof}

\begin{remark}\label{rem:prefix}
Every nonempty rational open interval in $(0,1)$ contains a
continued-fraction cylinder of even depth. Such a cylinder can be found
effectively: enumerate finite words of even length, compute their rational
endpoints, and test whether the closed interval between those endpoints
lies inside the given interval. The cylinder diameters tend to zero, so
the search terminates. Prescribing this prefix places the constructed
point in the desired interval. A finite initial segment of an approximation
can always be changed or prepended to arrange $r_0=0$.
\end{remark}

\begin{proof}[Proof of Theorem~\ref{thm:refined}]
Take the supplied computable rational approximation to $r$, clip it to
$[0,1]$, and prepend $0$. Clipping cannot increase total variation,
and prepending one term preserves its finiteness. Choose an even-depth cylinder in $I$ as in
Remark~\ref{rem:prefix}, and apply Proposition~\ref{prop:coding}.
The identity $W(x)=(\log2)r+c$, with computable $c$, gives
$W(x)\eqT r$. Theorem~\ref{thm:BM} and
Corollary~\ref{cor:degrees} supply the other values and reductions.
The assertion concerning Brjuno numbers follows from the total-variation
criterion in Proposition~\ref{prop:coding}.
\end{proof}

\section{Degree spectrum and further consequences}
\label{sec:consequences}

\begin{proof}[Proof of Corollary~\ref{cor:brjuno}]
For a c.e. set $K\subseteq\N$ of the desired nonzero degree, let
\begin{equation}\label{eq:halting}
 r_K=\sum_{e\in K}4^{-(e+1)}.
\end{equation}
This is a left-c.e. real in $(0,1)$, and its separated base-four digits
give $r_K\eqT K$. A computable enumeration of $K$ supplies a
nondecreasing rational approximation. Apply Theorem~\ref{thm:refined}.
In particular, taking $K$ to be the halting set makes all four outputs
Turing equivalent to the halting problem.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:spectrum}]
At a computable irrational input, every finite partial sum of $D,S,W$
is a uniformly computable real. At a convergence point, approximating
the $n$th partial sum to error $2^{-n}$ gives a computable rational
sequence converging to its value. Similarly, at a computable
differentiability point of the computable function $A$, rational
approximations to the difference quotients give a computable convergent
sequence with limit $A'(x)$. Thus all these values are limit-computable,
and their degrees are at most $\zerojump$.

Conversely, every Turing degree at most $\zerojump$ contains a
limit-computable real $r\in(0,1)$, by the limit lemma
\cite{Shoenfield}. For example, apply a computable pointwise approximation
to a set of that degree and encode its bits by separated base-four digits;
a fixed rational translation keeps the resulting real away from the
endpoints. Theorem~\ref{thm:refined} realizes the same degree for all four
quantities in any prescribed rational subinterval. Every open subinterval
contains such a rational subinterval, proving the full assertion.
\end{proof}

\subsection{The one-sided computability of the Brjuno examples}
For a nondecreasing approximation to a left-c.e. real $r$, the proof and
the analytic identities give computable constants $c_W,c_D,c_S,c_A$ with
\begin{align}
 W(x)&=(\log2)r+c_W,\notag\\
 D(x)&=-\frac{\log2}{2}r+c_D,\notag\\
 S(x)&=\frac{\pi\log2}{2}r+c_S,\label{eq:affine-all}\\
 A'(x)&=-\frac{\log2}{2x}r+c_A.\notag
\end{align}
Consequently $W(x)$ and $S(x)$ are left-c.e., while $D(x)$ and $A'(x)$
are right-c.e. When $r$ is non-computable none of these four reals is
computable. These one-sided assertions concern the constructed points;
we do not assert them for arbitrary computable Wilton numbers.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\ignore{
\subsection{What fails to be effective}
There is a useful contrast with bounded-type inputs. If all partial
quotients of $x$ are at most a supplied integer $B$, then
$x_n>1/(B+1)$ for every $n$, and the terms in \eqref{eq:W} are bounded
in absolute value by
$\log(B+1)2^{-\lfloor n/2\rfloor}$. The series for $W$ then has an
effective tail bound, and all four quantities in Theorem~\ref{thm:main}
are computable relative to $x$, uniformly with the bound $B$.
For example, at $\omega=(\sqrt5-1)/2$, the functional equation
$W(\omega)=\log(1/\omega)-\omega W(\omega)$ gives
\[
 W(\omega)=\frac{\log(1/\omega)}{1+\omega},
\]
so $A'(\omega)$ is computable as well.

At a point furnished by Theorem~\ref{thm:main}, or by
Theorem~\ref{thm:refined} with non-computable $r$, every finite partial sum
of $D,S,W$ is computable from $x$, and so are the difference quotients
\[
 \frac{A(x+2^{-n})-A(x)}{2^{-n}}.
\]
All the relevant limits exist. None of these approximation sequences can
have a convergence modulus computable from $x$, since such a modulus
would compute the limit. In contrast, the correction series $G$ and the comparison series $H$
have the explicit effective tails \eqref{eq:Gtail} and
\eqref{eq:tailbounds} on every irrational input, independently of
the convergence of $W$. This is the precise effective distinction
behind both the direct corollary and its refinement. Knowing only
that two functions differ by a bounded, or even continuous, function
would not establish these computability reductions.

The degree-spectrum theorem does not say that differentiation creates
non-computability at every computable point, nor that $A$ is nowhere
differentiable. It identifies all possible degrees of its finite
derivatives at computable differentiability points, while the Brjuno
examples show that absolute convergence of the Wilton series alone
does not make its sum computable.

The example thus separates three issues within a single classical
function: computability of its values, existence of its derivative, and
computability of that derivative from its argument. Its significance is
not an artificially chosen non-computable constant in the definition of
$A$, but the arithmetic information exposed by differentiation of a
computable correlation integral.
}

\begin{thebibliography}{99}

\bibitem{BD}
L.~B\'aez-Duarte, M.~Balazard, B.~Landreau, and E.~Saias,
\emph{\'Etude de l'autocorr\'elation multiplicative de la fonction
``partie fractionnaire''},
Ramanujan J. \textbf{9} (2005), 215--240.
\href{https://doi.org/10.1007/s11139-005-0834-4}{doi:10.1007/s11139-005-0834-4}.

\bibitem{BDlong}
L.~B\'aez-Duarte, M.~Balazard, B.~Landreau, and E.~Saias,
\emph{Sur l'autocorr\'elation multiplicative de la fonction
``partie fractionnaire''},
detailed companion calculations (2003),
\href{https://arxiv.org/abs/math/0306251}{arXiv:math/0306251}.
Proposition numbers cited in the text refer to this version.

\bibitem{BM12}
M.~Balazard and B.~Martin,
\emph{Comportement local moyen de la fonction de Brjuno},
Fund. Math. \textbf{218} (2012), no.~3, 193--224.
\href{https://doi.org/10.4064/fm218-3-1}{doi:10.4064/fm218-3-1}.

\bibitem{BM}
M.~Balazard and B.~Martin,
\emph{Sur l'autocorr\'elation multiplicative de la fonction
``partie fractionnaire'' et une fonction d\'efinie par J.~R.~Wilton},
preprint (2013),
\href{https://arxiv.org/abs/1305.4395}{arXiv:1305.4395}.

\bibitem{Shoenfield}
J.~R.~Shoenfield,
\emph{On degrees of unsolvability},
Ann. of Math. (2) \textbf{69} (1959), no.~3, 644--653.
\href{https://doi.org/10.2307/1970028}{doi:10.2307/1970028}.

\bibitem{Wilton}
J.~R.~Wilton,
\emph{An approximate functional equation with applications to a problem
of Diophantine approximation},
J. reine angew. Math. \textbf{169} (1933), 219--237.

\bibitem{YS}
M.~Yampolsky and I.~O.~Shevchenko,
\emph{Computability of Brjuno-like functions},
Canad. J. Math., First View, 1--41; published online November 12, 2025.


\bibitem{yoccoz1995}
J.-C. Yoccoz, 
\emph{Th\'eor\`eme de Siegel, nombres de Bruno et polyn\^omes quadratiques}, 
Ast\'erisque, Vol. 231, Soci\'et\'e Math\'ematique de France, Paris, 1995, pp. 3--88.

\end{thebibliography}
\end{document}