Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

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

Request Permissions   Purchase Content 
 

 

Randomness and differentiability


Authors: Vasco Brattka, Joseph S. Miller and André Nies
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
Published electronically: May 27, 2015
MathSciNet review: 3413875
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D32, 03F60, 26A27, 26A48, 26A45

Retrieve articles in all journals with MSC (2010): 03D32, 03F60, 26A27, 26A48, 26A45


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
Email: jmiller@math.wisc.edu

André Nies
Affiliation: Department of Computer Science, University of Auckland, Private bag 92019, Auckland, New Zealand
Email: andre@cs.auckland.ac.nz

DOI: https://doi.org/10.1090/tran/6484
Keywords: Computable analysis, algorithmic randomness, differentiability, monotonic function, bounded variation
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
Article copyright: © Copyright 2015 American Mathematical Society