## 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

- V. I. Bogachev,
*Measure theory. Vol. I, II*, Springer-Verlag, Berlin, 2007. MR**2267655**, DOI 10.1007/978-3-540-34514-5 - V. Brattka, J. Miller, and A. Nies,
*Randomness and differentiability*(long version on arxiv). http://arxiv.org/abs/1104.4465. - N. L. Carothers,
*Real analysis*, Cambridge University Press, Cambridge, 2000. MR**1772332**, DOI 10.1017/CBO9780511814228 - O. Demut,
*The differentiability of constructive functions of weakly bounded variation on pseudo numbers*, Comment. Math. Univ. Carolinae**16**(1975), no. 3, 583–599 (Russian). MR**476442** - Rodney G. Downey and Denis R. Hirschfeldt,
*Algorithmic randomness and complexity*, Theory and Applications of Computability, Springer, New York, 2010. MR**2732288**, DOI 10.1007/978-0-387-68441-3 - 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**, DOI 10.1142/S0219061305000468 - 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**, DOI 10.14321/realanalexch.34.1.0127 - 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. - A. Kučera, A. Nies, and C. Porter,
*Demuth’s path to randomness*. To appear in Bull. Symb. Logic, 2014. - 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**, DOI 10.1007/978-3-642-27654-5_{1}2 - Henri Lebesgue,
*Sur les intégrales singulières*, Ann. Fac. Sci. Toulouse Sci. Math. Sci. Phys. (3)**1**(1909), 25–117 (French). MR**1508308**, DOI 10.5802/afst.257 - André Nies,
*Computability and randomness*, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009. MR**2548883**, DOI 10.1093/acprof:oso/9780199230761.001.0001 - A. Nies (editor), Logic Blog 2013. Available at http://arxiv.org/abs/1403.5719, 2013.
- 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**, DOI 10.1090/S0002-9939-2013-11710-7 - Marian B. Pour-El and J. Ian Richards,
*Computability in analysis and physics*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989. MR**1005942**, DOI 10.1007/978-3-662-21717-7 - Walter Rudin,
*Real and complex analysis*, 3rd ed., McGraw-Hill Book Co., New York, 1987. MR**924157** - J. Rute,
*Algorithmic randomness, martingales, and differentiability I*. In preparation, 2012. - 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**, DOI 10.1007/BFb0112458 - 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**22592**, DOI 10.24033/bsmf.1381

## 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