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
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?)

  • [1] V. I. Bogachev, Measure theory. Vol. I, II, Springer-Verlag, Berlin, 2007. MR 2267655 (2008g:28002)
  • [2] V. Brattka, J. Miller, and A. Nies,
    Randomness and differentiability (long version on arxiv).
  • [3] N. L. Carothers, Real analysis, Cambridge University Press, Cambridge, 2000. MR 1772332
  • [4] O. Demuth, The differentiability of constructive functions of weakly bounded variation on pseudo numbers, Comment. Math. Univ. Carolinae 16 (1975), no. 3, 583-599 (Russian). MR 0476442 (57 #16005)
  • [5] Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic randomness and complexity, Theory and Applications of Computability, Springer, New York, 2010. MR 2732288 (2012g:03001)
  • [6] Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller, and André Nies, Relativizing Chaitin's halting probability, J. Math. Log. 5 (2005), no. 2, 167-192. MR 2188515 (2007e:68031),
  • [7] Thomas Fowler and David Preiss, A simple proof of Zahorski's description of non-differentiability sets of Lipschitz functions, Real Anal. Exchange 34 (2009), no. 1, 127-138. MR 2527127 (2010e:26003)
  • [8] C. Freer, B. Kjos-Hanssen, A. Nies, and F. Stephan,
    Effective aspects of Lipschitz functions, Computability 3 (2014), 45-61, DOI 10.3233/COM-14025.
  • [9] A. Kučera, A. Nies, and C. Porter,
    Demuth's path to randomness.
    To appear in Bull. Symb. Logic, 2014.
  • [10] Antonín Kučera and André Nies, Demuth's path to randomness, Computation, physics and beyond, Lecture Notes in Comput. Sci., vol. 7160, Springer, Heidelberg, 2012, pp. 159-173. MR 2965521,
  • [11] Henri Lebesgue, Sur les intégrales singulières, Ann. Fac. Sci. Toulouse Sci. Math. Sci. Phys. (3) 1 (1909), 25-117 (French). MR 1508308
  • [12] André Nies, Computability and randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR 2548883 (2011i:03003)
  • [13] A. Nies (editor),
    Logic Blog 2013.
    Available at, 2013.
  • [14] Noopur Pathak, Cristóbal Rojas, and Stephen G. Simpson, Schnorr randomness and the Lebesgue differentiation theorem, Proc. Amer. Math. Soc. 142 (2014), no. 1, 335-349. MR 3119207
  • [15] Marian B. Pour-El and J. Ian Richards, Computability in analysis and physics, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989. MR 1005942 (90k:03062)
  • [16] Walter Rudin, Real and complex analysis, 3rd ed., McGraw-Hill Book Co., New York, 1987. MR 924157 (88k:00002)
  • [17] J. Rute, Algorithmic randomness, martingales, and differentiability I.
    In preparation, 2012.
  • [18] Claus-Peter Schnorr, Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie, Lecture Notes in Mathematics, Vol. 218, Springer-Verlag, Berlin-New York, 1971. MR 0414225 (54 #2328)
  • [19] Zygmunt Zahorski, Sur l'ensemble des points de non-dérivabilité d'une fonction continue, Bull. Soc. Math. France 74 (1946), 147-178 (French). MR 0022592 (9,231a)

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

Joseph S. Miller
Affiliation: Department of Mathematics, University of Wisconsin, Madison, Wisconsin 53706-1388

André Nies
Affiliation: Department of Computer Science, University of Auckland, Private bag 92019, Auckland, New Zealand

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

American Mathematical Society