Bienvenu, Laurent ;
Hölzl, Rupert ;
Miller, Joseph S. ;
Nies, André
The Denjoy alternative for computable functions
Abstract
The DenjoyYoungSaks Theorem from classical analysis states that for an arbitrary function f:R>R, the Denjoy alternative holds outside a null set, i.e., for almost every real x, either the derivative of f exists at x, or the derivative fails to exist in the worst possible way: the limit superior of the slopes around x equals +infinity, and the limit inferior infinity. Algorithmic randomness allows us to define randomness notions giving rise to different concepts of almost everywhere. It is then natural to wonder which of these concepts corresponds to the almost everywhere notion appearing in the DenjoyYoungSaks theorem. To answer this question Demuth investigated effective versions of the theorem and proved that Demuth randomness is strong enough to ensure the Denjoy alternative for Markov computable functions. In this paper, we show that the set of these points is indeed strictly bigger than the set of Demuth random reals  showing that Demuth's sufficient condition was too strong  and moreover is incomparable with MartinLöf randomness; meaning in particular that it does not correspond to any known set of random reals. To prove these two theorems, we study densitytype theorems, such as the Lebesgue density theorem and obtain results of independent interest. We show for example that the classical notion of Lebesgue density can be characterized by the only very recently defined notion of difference randomness. This is to our knowledge the first analytical characterization of difference randomness. We also consider the concept of porous points, a special type of Lebesgue nondensity points that are wellbehaved in the sense that the "density holes" around the point are continuous intervals whose length follows a certain systematic rule. An essential part of our proof will be to argue that porous points of effectively closed classes can never be difference random.
BibTeX  Entry
@InProceedings{bienvenu_et_al:LIPIcs:2012:3409,
author = {Laurent Bienvenu and Rupert H{\"o}lzl and Joseph S. Miller and Andr{\'e} Nies},
title = {{The Denjoy alternative for computable functions}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {543554},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3409},
URN = {urn:nbn:de:0030drops34095},
doi = {10.4230/LIPIcs.STACS.2012.543},
annote = {Keywords: Differentiability, Denjoy alternative, density, porosity, randomness}
}
2012
Keywords: 

Differentiability, Denjoy alternative, density, porosity, randomness 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

2012 