Non-computable derivatives of the fractional-part autocorrelation

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 [7]. The author assumes full responsibility for the content and its correctness.

Introduction and main results

This paper introduces an interesting new example of a natural non-computable function of a real variable. The multiplicative autocorrelation of the fractional-part function is defined by an absolutely convergent, nonnegative integral:

The analytic properties of $A$ were studied by Báez-Duarte, Balazard, Landreau, and Saias [1, 2] 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 [4], who characterized the differentiability points of $A(x)$ through a continued-fraction series introduced by Wilton [6]. We combine their identities with the non-computability theorem for the signed Wilton series obtained in our paper [7], 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

where $\tau(m)$ is the number of positive divisors of $m$. Further, to define the Wilton function, set

and let

We denote by $\mathcal{W}$ the set of Wilton numbers, namely the irrational $x\in(0,1)$ for which (1.3) converges. Absolute convergence defines the smaller class of Brjuno numbers which play a special role in the study of small-divisor problems in holomorphic dynamics [8].

We use the Cauchy representation of real numbers. 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\leq_T x$ means that one oracle algorithm computes $y$ from every Cauchy name of this fixed $x$. A function on a specified domain is computable if one oracle algorithm works for every input in that domain. In particular, $F(x)\not\leq_T 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 [7], once we have made effective the known analytic identities for $A'(x)$.

The non-computability input here is precisely [7 Theorems 5.1 and 5.2], applied to their second Wilton function. Theorem 1.1 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 limit-computable if it is the limit of a computable sequence of rationals, without a required computable rate of convergence. It is 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 $\mathbb{N}$, and $\mathbf{0}'$ denotes the degree of the halting problem.

Corollary 1.3. 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.

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.

Section 2 presents the basic analytic properties of $A$. Sections 3 and 4 prove the common reduction

where $C$ is computable from $x$. Section 5 then proves the direct corollary of [7]. Section 6 supplies the adapted realization argument, and Section 7 deduces the degree spectrum and the one-sided computability statements.

Basic properties of the autocorrelation

Reciprocity and the Hilbert-space interpretation

Near zero the integrand in (1.1) 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

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

Cauchy–Schwarz therefore gives

where $\gamma$ is Euler’s constant. The value at 1 follows by integration over successive unit intervals and Stirling’s formula; see [2 Propositions 85 and 87]. Our algorithm below computes $A(1)$ directly from the integral and does not require this special-value formula.

Regularity and differentiability

Balazard and Martin prove that the global modulus of continuity

satisfies

see [4 Proposition 31]. This describes the regularity of $A$, but we do not use the unspecified constant in the $O(h)$ term to compute it. Proposition 3.1 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:

by [2 Proposition 98]. Thus every positive rational is a strict local maximum, with infinite one-sided slopes. These singularities explain the cusps visible in Figure 1.

!Graph of the autocorrelation $A$ on $[0,2]$ bbox=0.21,0.10,0.84,0.34

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$ [4 Theorem 1 and Proposition 30]. The Wilton set has full Lebesgue measure in $(0,1)$, so $A$ is differentiable almost everywhere there – and (10) extends this conclusion to $(0,\infty)$. The identities for the derivative values are stated in Theorem 4.1.

Effective evaluation of the autocorrelation and the correction

Computability of the autocorrelation

We first evaluate truncated integrals at rational arguments, then use an explicit modulus to pass to arbitrary Cauchy names.

to decide coincidences between discontinuity locations at an arbitrary real input. The bound $A(x) \le2$ 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

All operations here are computable, including max, so the algorithm extends to $[0,\infty)$ without deciding whether $x=1$. □

Computability of the correction term

The identities in Theorem 4.1 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 [4 Section 4.1], define

where $t\log t=0$ at 0, and put

The difference from $W$ is the uniform effective tail bound below.

Proof. Proposition 3.1 and the computable continuous extension of $t\log t$ give computability of $F$. At the endpoint, for example, $0\le t\le2^{-m}$ and $m\ge2$ imply $|t\log t|\le m2^{-m}\log2$. Also $|F(t)|\le5$ 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

In particular, $q_n\ge2^{\lfloor n/2\rfloor}$ and

This proves (3.4).

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 (3.3) is uniformly computable from $x$. The effective tail bound completes the algorithm. □

Classical identities and an effective transfer principle

The following theorem both identifies the differentiability points and relates the four values there. In the notation of [4], 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 (1.2).

References and the derivative formula. The convergence assertions and (4.1) are [4 Theorems 1 and 2]; the additional correction at rational points in that paper vanishes on our domain. For (4.2), use their identity (6), already established in [1]:

In this integral $D$ denotes its periodic integrable representative. Every Wilton point is a Lebesgue point of $W$ [4 Proposition 12]. Since $G$ is continuous at irrational points, (4.1) makes it a Lebesgue point of $D$ as well. The derivative of the integral in (4.3) is therefore $-D(x)/x^2$ at the point in question. Differentiating (4.3) and eliminating the integral yields (4.2). □

The divisor weight in $S$ is also natural. Formally inserting the Fourier series of $B_1$ into $D$ gives

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 $(0,1) \setminus\mathbb{Q}$

Propositions 3.1 and 3.2 make $C$ computable. Combining this fact with the classical identities gives the transfer used in both non-computability arguments.

Proof. The formulas follow from Theorem 4.1. 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,

The other inversions are equally explicit. □

Direct application of YS

This is [7 Theorems 5.1 and 5.2], specialized to the second Wilton function $W_2$ defined in their equation (2.3). Their index $i$ corresponds to $n+1$ in (3); 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 1.1.

Proof. Let the cylinder be specified by a finite word $(a_1,\ldots,a_m)$, and set

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,

The map $h$ and its inverse on the cylinder are computable, so $x\equiv_{\mathrm{T}}\xi$. Splitting the Wilton series after $m$ terms gives

where

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)\le_{\mathrm{T}}x$, inverting (26) would compute $W(\xi)$ from $x$, hence from $\xi$, a contradiction. □

Proof of Theorem 1.1. Computability of $A$ is Proposition 3.1, and the uniform reductions are Proposition 4.2. Choose $\xi$ from Theorem 5.1. Every nonempty open subinterval of $(0,1)$ contains a continued-fraction cylinder: cylinder diameters tend to zero, as follows from $q_m\ge2^{\lfloor m/2\rfloor}$. Lemma 5.2 gives $x\in I\cap\mathcal{W}$ with $W(x)\not\le_{\mathrm{T}}x$. Theorem 4.1 gives existence of all four finite values, and Proposition 4.2 gives their non-computability relative to $x$. □

Refinement of the non-computability argument

Effective continued-fraction estimates

Recall the conventions

and use the recurrences

A computable infinite sequence of positive integer partial quotients determines a computable irrational. Indeed,

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.

Put

We use the classical comparison estimate

see [3 Proposition 1]. Also,

Realizing a convergent approximation

Proof. Let the length of the prescribed prefix be $N=2m$, possibly zero. Put

and assign the target terms

Starting after the prescribed prefix, define successively

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 (27) shows that the resulting infinite continued fraction is a computable irrational, uniformly from the supplied data. Lemma 6.3 gives, for $n\geq N$,

The sequence $(\varepsilon_n)$ is uniformly computable, and its absolute sum has the effective tail bound of Lemma 6.1. Thus

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

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 (36) that

The finite sum $P$ is computable. Lemma 6.2 now yields

where $c$ is computable with the asserted uniformity.

Finally, all $L_n$ and $h_n$ are nonnegative, the error in (36) is absolutely summable, and

Thus $\sum_nL_n<\infty$ if and only if the approximation has finite total variation. Lemma 6.2 proves the last claim. □

Remark 6.5. 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$.

Proof of Theorem 1.2. 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 6.5, and apply Proposition 6.4. The identity $W(x)=(\log2)r+c$, with computable $c$, gives $W(x)\equiv_{\mathrm T}r$. Theorem 4.1 and Corollary 4.3 supply the other values and reductions. The assertion concerning Brjuno numbers follows from the total-variation criterion in Proposition 6.4. □

Degree spectrum and further consequences

Proof of Corollary 1.3. For a c.e. set $K\subseteq\mathbb{N}$ of the desired nonzero degree, let

This is a left-c.e. real in $(0,1)$, and its separated base-four digits give $r_K\equiv_{\mathrm T}K$. A computable enumeration of $K$ supplies a nondecreasing rational approximation. Apply Theorem 1.2. In particular, taking $K$ to be the halting set makes all four outputs Turing equivalent to the halting problem. □

Proof of Theorem 1.4. 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 $\mathbf{0}'$.

Conversely, every Turing degree at most $\mathbf{0}'$ contains a limit-computable real $r\in(0,1)$, by the limit lemma [5]. 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 1.2 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. □

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

Consequently $W(x)$ and $S(x)$ are left-c.e., while $D(x)$ and $A'(x)$ are right-c.e. When $r$ is noncomputable 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.

References