Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Randomness and differentiability
HTML articles powered by AMS MathViewer

by Vasco Brattka, Joseph S. Miller and André Nies PDF
Trans. Amer. Math. Soc. 368 (2016), 581-605 Request permission

Abstract:

We characterize some major algorithmic randomness notions via differentiability of effective functions.

(1) As the main result we show that a real number $z\in [0,1]$ is computably random if and only if each nondecreasing computable function $[0,1]\rightarrow \mathbb {R}$ is differentiable at $z$.

(2) We prove that a real number $z\in [0,1]$ is weakly 2-random if and only if each almost everywhere differentiable computable function $[0,1]\rightarrow \mathbb {R}$ is differentiable at $z$.

(3) Recasting in classical language results dating from 1975 of the constructivist Demuth, we show that a real $z$ is Martin-Löf random if and only if every computable function of bounded variation is differentiable at $z$, and similarly for absolutely continuous functions.

We also use our analytic methods to show that computable randomness of a real is base invariant and to derive other preservation results for randomness notions.

References
Similar Articles
Additional Information
  • Vasco Brattka
  • Affiliation: Faculty of Computer Science, Universität der Bundeswehr München, 85577 Neubiberg, Germany – and – Department of Mathematics and Applied Mathematics, University of Cape Town, Rondebosch 7701, South Africa
  • Email: Vasco.Brattka@cca-net.de
  • Joseph S. Miller
  • Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388
  • MR Author ID: 735102
  • Email: jmiller@math.wisc.edu
  • André Nies
  • Affiliation: Department of Computer Science, University of Auckland, Private bag 92019, Auckland, New Zealand
  • MR Author ID: 328692
  • Email: andre@cs.auckland.ac.nz
  • Received by editor(s): November 21, 2012
  • Received by editor(s) in revised form: November 22, 2013
  • Published electronically: May 27, 2015
  • Additional Notes: The first author was supported by the National Research Foundation of South Africa
    The second author was supported by the National Science Foundation under grants DMS-0945187 and DMS-0946325, the latter being part of a Focused Research Group in Algorithmic Randomness
    The third author was partially supported by the Marsden Fund of New Zealand, grant no. 08-UOA-187
  • © Copyright 2015 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 368 (2016), 581-605
  • MSC (2010): Primary 03D32, 03F60; Secondary 26A27, 26A48, 26A45
  • DOI: https://doi.org/10.1090/tran/6484
  • MathSciNet review: 3413875