HEXAGONbeta

Non-computable derivatives of the fractional-part autocorrelation

A mix of human-written and AI-generated textHuman understanding: all partscs.CC — Computational Complexity

Contributed by Michael Yampolsky ↗

Version 1 / Nov 10, 2026 / CC BY 4.0

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 xx. We derive these results from an adaptation of our earlier work on computability of Brjuno-like functions.

References

  1. L. Báez-Duarte, M. Balazard, B. Landreau, and E. Saias, Étude de l'autocorrélation multiplicative de la fonction ``partie fractionnaire'' , Ramanujan J. 9 (2005), 215--240. doi:10.1007/s11139-005-0834-4 (https://doi.org/10.1007/s11139-005-0834-4).DOI
  2. L. Báez-Duarte, M. Balazard, B. Landreau, and E. Saias, Sur l'autocorrélation multiplicative de la fonction ``partie fractionnaire'' , detailed companion calculations (2003), arXiv:math/0306251 (https://arxiv.org/abs/math/0306251). Proposition numbers cited in the text refer to this version.arXiv
  3. M. Balazard and B. Martin, Comportement local moyen de la fonction de Brjuno , Fund. Math. 218 (2012), no. 3, 193--224. doi:10.4064/fm218-3-1 (https://doi.org/10.4064/fm218-3-1).DOI
  4. M. Balazard and B. Martin, Sur l'autocorrélation multiplicative de la fonction ``partie fractionnaire'' et une fonction définie par J. R. Wilton , preprint (2013), arXiv:1305.4395 (https://arxiv.org/abs/1305.4395).arXiv
  5. J. R. Shoenfield, On degrees of unsolvability , Ann. of Math. (2) 69 (1959), no. 3, 644--653. doi:10.2307/1970028 (https://doi.org/10.2307/1970028).DOI
  6. J. R. Wilton, An approximate functional equation with applications to a problem of Diophantine approximation , J. reine angew. Math. 169 (1933), 219--237.
  7. M. Yampolsky and I. O. Shevchenko, Computability of Brjuno-like functions , Canad. J. Math., First View, 1--41; published online November 12, 2025.
  8. J.-C. Yoccoz, Théorème de Siegel, nombres de Bruno et polynômes quadratiques , Astérisque, Vol. 231, Société Mathématique de France, Paris, 1995, pp. 3--88.

Version history

  1. v1 · 11 pagesSubmitted by Michael YampolskyInitial depositCurrentNov 09, 2026